unittests/tools/llvm-cfi-verify/GraphBuilder.cpp

   1 //===- llvm/unittests/llvm-cfi-verify/GraphBuilder.cpp --------------===//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8
   9 #include "../tools/llvm-cfi-verify/lib/GraphBuilder.h"
  10 #include "../tools/llvm-cfi-verify/lib/FileAnalysis.h"
  11 #include "gmock/gmock.h"
  12 #include "gtest/gtest.h"
  13
  14 #include "llvm/BinaryFormat/ELF.h"
  15 #include "llvm/MC/MCAsmInfo.h"
  16 #include "llvm/MC/MCContext.h"
  17 #include "llvm/MC/MCDisassembler/MCDisassembler.h"
  18 #include "llvm/MC/MCInst.h"
  19 #include "llvm/MC/MCInstPrinter.h"
  20 #include "llvm/MC/MCInstrAnalysis.h"
  21 #include "llvm/MC/MCInstrDesc.h"
  22 #include "llvm/MC/MCInstrInfo.h"
  23 #include "llvm/MC/MCObjectFileInfo.h"
  24 #include "llvm/MC/MCRegisterInfo.h"
  25 #include "llvm/MC/MCSubtargetInfo.h"
  26 #include "llvm/Object/Binary.h"
  27 #include "llvm/Object/COFF.h"
  28 #include "llvm/Object/ELFObjectFile.h"
  29 #include "llvm/Object/ObjectFile.h"
  30 #include "llvm/Support/Casting.h"
  31 #include "llvm/Support/CommandLine.h"
  32 #include "llvm/Support/Error.h"
  33 #include "llvm/Support/MemoryBuffer.h"
  34 #include "llvm/Support/TargetRegistry.h"
  35 #include "llvm/Support/TargetSelect.h"
  36 #include "llvm/Support/raw_ostream.h"
  37
  38 #include <cstdlib>
  39 #include <sstream>
  40
  41 using Instr = ::llvm::cfi_verify::FileAnalysis::Instr;
  42 using ::testing::AllOf;
  43 using ::testing::Each;
  44 using ::testing::ElementsAre;
  45 using ::testing::Eq;
  46 using ::testing::Field;
  47 using ::testing::IsEmpty;
  48 using ::testing::Matches;
  49 using ::testing::Pair;
  50 using ::testing::PrintToString;
  51 using ::testing::Property;
  52 using ::testing::SizeIs;
  53 using ::testing::UnorderedElementsAre;
  54 using ::testing::Value;
  55
  56 namespace llvm {
  57 namespace cfi_verify {
  58 // Printing helpers for gtest.
  59 std::string HexStringifyContainer(const std::vector<uint64_t> &C) {
  60   std::stringstream Stream;
  61   if (C.empty()) {
  62     return "{ }";
  63   }
  64
  65   Stream << "{ ";
  66   const auto &LastElemIt = std::end(C) - 1;
  67
  68   for (auto It = std::begin(C); It != LastElemIt; ++It) {
  69     Stream << "0x" << std::hex << *It << ", ";
  70   }
  71   Stream << "0x" << std::hex << *LastElemIt << " }";
  72   return Stream.str();
  73 }
  74
  75 void PrintTo(const ConditionalBranchNode &BranchNode, ::std::ostream *os) {
  76   *os << "ConditionalBranchNode<Address: 0x" << std::hex << BranchNode.Address
  77       << ", Target: 0x" << BranchNode.Target << ", Fallthrough: 0x"
  78       << BranchNode.Fallthrough
  79       << ", CFIProtection: " << BranchNode.CFIProtection << ">";
  80 }
  81
  82 void PrintTo(const GraphResult &Result, ::std::ostream *os) {
  83   *os << "Result BaseAddress: 0x" << std::hex << Result.BaseAddress << "\n";
  84
  85   if (Result.ConditionalBranchNodes.empty())
  86     *os << "  (No conditional branch nodes)\n";
  87
  88   for (const auto &Node : Result.ConditionalBranchNodes) {
  89     *os << "  ";
  90     PrintTo(Node, os);
  91     *os << "\n    Fallthrough Path: " << std::hex
  92         << HexStringifyContainer(Result.flattenAddress(Node.Fallthrough))
  93         << "\n";
  94     *os << "    Target Path: " << std::hex
  95         << HexStringifyContainer(Result.flattenAddress(Node.Target)) << "\n";
  96   }
  97
  98   if (Result.OrphanedNodes.empty())
  99     *os << "  (No orphaned nodes)";
 100
 101   for (const auto &Orphan : Result.OrphanedNodes) {
 102     *os << "  Orphan (0x" << std::hex << Orphan
 103         << ") Path: " << HexStringifyContainer(Result.flattenAddress(Orphan))
 104         << "\n";
 105   }
 106 }
 107
 108 namespace {
 109 class ELFx86TestFileAnalysis : public FileAnalysis {
 110 public:
 111   ELFx86TestFileAnalysis()
 112       : FileAnalysis(Triple("x86_64--"), SubtargetFeatures()) {}
 113
 114   // Expose this method publicly for testing.
 115   void parseSectionContents(ArrayRef<uint8_t> SectionBytes,
 116                             object::SectionedAddress Address) {
 117     FileAnalysis::parseSectionContents(SectionBytes, Address);
 118   }
 119
 120   Error initialiseDisassemblyMembers() {
 121     return FileAnalysis::initialiseDisassemblyMembers();
 122   }
 123 };
 124
 125 class BasicGraphBuilderTest : public ::testing::Test {
 126 protected:
 127   virtual void SetUp() {
 128     IgnoreDWARFFlag = true;
 129     SuccessfullyInitialised = true;
 130     if (auto Err = Analysis.initialiseDisassemblyMembers()) {
 131       handleAllErrors(std::move(Err), [&](const UnsupportedDisassembly &E) {
 132         SuccessfullyInitialised = false;
 133         outs()
 134             << "Note: CFIVerifyTests are disabled due to lack of x86 support "
 135                "on this build.\n";
 136       });
 137     }
 138   }
 139
 140   bool SuccessfullyInitialised;
 141   ELFx86TestFileAnalysis Analysis;
 142 };
 143
 144 MATCHER_P2(HasPath, Result, Matcher, "has path " + PrintToString(Matcher)) {
 145   const auto &Path = Result.flattenAddress(arg);
 146   *result_listener << "the path is " << PrintToString(Path);
 147   return Matches(Matcher)(Path);
 148 }
 149
 150 TEST_F(BasicGraphBuilderTest, BuildFlowGraphTestSinglePathFallthroughUd2) {
 151   if (!SuccessfullyInitialised)
 152     return;
 153   Analysis.parseSectionContents(
 154       {
 155           0x75, 0x02, // 0: jne 4 [+2]
 156           0x0f, 0x0b, // 2: ud2
 157           0xff, 0x10, // 4: callq *(%rax)
 158       },
 159       {0xDEADBEEF, 0x0});
 160   const auto Result =
 161       GraphBuilder::buildFlowGraph(Analysis, {0xDEADBEEF + 4, 0x0});
 162
 163   EXPECT_THAT(Result.OrphanedNodes, IsEmpty());
 164   EXPECT_THAT(Result.ConditionalBranchNodes, SizeIs(1));
 165   EXPECT_THAT(Result.ConditionalBranchNodes,
 166               Each(Field(&ConditionalBranchNode::CFIProtection, Eq(true))));
 167   EXPECT_THAT(
 168       Result.ConditionalBranchNodes,
 169       Contains(AllOf(Field(&ConditionalBranchNode::Address, Eq(0xDEADBEEF)),
 170                      Field(&ConditionalBranchNode::Target,
 171                            HasPath(Result, ElementsAre(0xDEADBEEF + 4))),
 172                      Field(&ConditionalBranchNode::Fallthrough,
 173                            HasPath(Result, ElementsAre(0xDEADBEEF + 2))))))
 174       << PrintToString(Result);
 175 }
 176
 177 TEST_F(BasicGraphBuilderTest, BuildFlowGraphTestSinglePathJumpUd2) {
 178   if (!SuccessfullyInitialised)
 179     return;
 180   Analysis.parseSectionContents(
 181       {
 182           0x75, 0x02, // 0: jne 4 [+2]
 183           0xff, 0x10, // 2: callq *(%rax)
 184           0x0f, 0x0b, // 4: ud2
 185       },
 186       {0xDEADBEEF, 0x0});
 187   const auto Result =
 188       GraphBuilder::buildFlowGraph(Analysis, {0xDEADBEEF + 2, 0x0});
 189
 190   EXPECT_THAT(Result.OrphanedNodes, IsEmpty());
 191   EXPECT_THAT(Result.ConditionalBranchNodes, SizeIs(1));
 192   EXPECT_THAT(Result.ConditionalBranchNodes,
 193               Each(Field(&ConditionalBranchNode::CFIProtection, Eq(true))));
 194   EXPECT_THAT(
 195       Result.ConditionalBranchNodes,
 196       Contains(AllOf(Field(&ConditionalBranchNode::Address, Eq(0xDEADBEEF)),
 197                      Field(&ConditionalBranchNode::Target,
 198                            HasPath(Result, ElementsAre(0xDEADBEEF + 4))),
 199                      Field(&ConditionalBranchNode::Fallthrough,
 200                            HasPath(Result, ElementsAre(0xDEADBEEF + 2))))))
 201       << PrintToString(Result);
 202 }
 203
 204 TEST_F(BasicGraphBuilderTest, BuildFlowGraphTestDualPathDualUd2) {
 205   if (!SuccessfullyInitialised)
 206     return;
 207   Analysis.parseSectionContents(
 208       {
 209           0x75, 0x03, // 0: jne 5 [+3]
 210           0x90,       // 2: nop
 211           0xff, 0x10, // 3: callq *(%rax)
 212           0x0f, 0x0b, // 5: ud2
 213           0x75, 0xf9, // 7: jne 2 [-7]
 214           0x0f, 0x0b, // 9: ud2
 215       },
 216       {0xDEADBEEF, 0x0});
 217   const auto Result =
 218       GraphBuilder::buildFlowGraph(Analysis, {0xDEADBEEF + 3, 0x0});
 219
 220   EXPECT_THAT(Result.OrphanedNodes, IsEmpty());
 221   EXPECT_THAT(Result.ConditionalBranchNodes, SizeIs(2));
 222   EXPECT_THAT(Result.ConditionalBranchNodes,
 223               Each(Field(&ConditionalBranchNode::CFIProtection, Eq(true))));
 224   EXPECT_THAT(
 225       Result.ConditionalBranchNodes,
 226       Contains(AllOf(
 227           Field(&ConditionalBranchNode::Address, Eq(0xDEADBEEF)),
 228           Field(&ConditionalBranchNode::Fallthrough,
 229                 HasPath(Result, ElementsAre(0xDEADBEEF + 2, 0xDEADBEEF + 3))),
 230           Field(&ConditionalBranchNode::Target,
 231                 HasPath(Result, ElementsAre(0xDEADBEEF + 5))))))
 232       << PrintToString(Result);
 233   EXPECT_THAT(
 234       Result.ConditionalBranchNodes,
 235       Contains(AllOf(
 236           Field(&ConditionalBranchNode::Address, Eq(0xDEADBEEF + 7)),
 237           Field(&ConditionalBranchNode::Fallthrough,
 238                 HasPath(Result, ElementsAre(0xDEADBEEF + 9))),
 239           Field(&ConditionalBranchNode::Target,
 240                 HasPath(Result, ElementsAre(0xDEADBEEF + 2, 0xDEADBEEF + 3))))))
 241       << PrintToString(Result);
 242 }
 243
 244 TEST_F(BasicGraphBuilderTest, BuildFlowGraphTestDualPathSingleUd2) {
 245   if (!SuccessfullyInitialised)
 246     return;
 247   Analysis.parseSectionContents(
 248       {
 249           0x75, 0x05, // 0: jne 7 [+5]
 250           0x90,       // 2: nop
 251           0xff, 0x10, // 3: callq *(%rax)
 252           0x75, 0xfb, // 5: jne 2 [-5]
 253           0x0f, 0x0b, // 7: ud2
 254       },
 255       {0xDEADBEEF, 0x0});
 256   GraphResult Result =
 257       GraphBuilder::buildFlowGraph(Analysis, {0xDEADBEEF + 3, 0x0});
 258
 259   EXPECT_THAT(Result.OrphanedNodes, IsEmpty());
 260   EXPECT_THAT(Result.ConditionalBranchNodes, SizeIs(2));
 261   EXPECT_THAT(Result.ConditionalBranchNodes,
 262               Each(Field(&ConditionalBranchNode::CFIProtection, Eq(true))));
 263   EXPECT_THAT(
 264       Result.ConditionalBranchNodes,
 265       Contains(AllOf(
 266           Field(&ConditionalBranchNode::Address, Eq(0xDEADBEEF)),
 267           Field(&ConditionalBranchNode::Fallthrough,
 268                 HasPath(Result, ElementsAre(0xDEADBEEF + 2, 0xDEADBEEF + 3))),
 269           Field(&ConditionalBranchNode::Target,
 270                 HasPath(Result, ElementsAre(0xDEADBEEF + 7))))))
 271       << PrintToString(Result);
 272   EXPECT_THAT(
 273       Result.ConditionalBranchNodes,
 274       Contains(AllOf(
 275           Field(&ConditionalBranchNode::Address, Eq(0xDEADBEEF + 5)),
 276           Field(&ConditionalBranchNode::Fallthrough,
 277                 HasPath(Result, ElementsAre(0xDEADBEEF + 7))),
 278           Field(&ConditionalBranchNode::Target,
 279                 HasPath(Result, ElementsAre(0xDEADBEEF + 2, 0xDEADBEEF + 3))))))
 280       << PrintToString(Result);
 281 }
 282
 283 TEST_F(BasicGraphBuilderTest, BuildFlowGraphFailures) {
 284   if (!SuccessfullyInitialised)
 285     return;
 286   Analysis.parseSectionContents(
 287       {
 288           0x90,       // 0: nop
 289           0x75, 0xfe, // 1: jne 1 [-2]
 290       },
 291       {0xDEADBEEF, 0x0});
 292   GraphResult Result =
 293       GraphBuilder::buildFlowGraph(Analysis, {0xDEADBEEF, 0x0});
 294   EXPECT_THAT(Result.OrphanedNodes, IsEmpty());
 295   EXPECT_THAT(Result.ConditionalBranchNodes, IsEmpty());
 296
 297   Result = GraphBuilder::buildFlowGraph(Analysis, {0xDEADBEEF + 1, 0x0});
 298   EXPECT_THAT(Result.OrphanedNodes, IsEmpty());
 299   EXPECT_THAT(Result.ConditionalBranchNodes, IsEmpty());
 300
 301   Result = GraphBuilder::buildFlowGraph(Analysis, {0xDEADC0DE, 0x0});
 302   EXPECT_THAT(Result.OrphanedNodes, IsEmpty());
 303   EXPECT_THAT(Result.ConditionalBranchNodes, IsEmpty());
 304 }
 305
 306 TEST_F(BasicGraphBuilderTest, BuildFlowGraphNoXrefs) {
 307   if (!SuccessfullyInitialised)
 308     return;
 309   Analysis.parseSectionContents(
 310       {
 311           0xeb, 0xfe, // 0: jmp 0 [-2]
 312           0xff, 0x10, // 2: callq *(%rax)
 313       },
 314       {0xDEADBEEF, 0x0});
 315   GraphResult Result =
 316       GraphBuilder::buildFlowGraph(Analysis, {0xDEADBEEF + 2, 0x0});
 317   EXPECT_THAT(Result.ConditionalBranchNodes, IsEmpty());
 318   EXPECT_THAT(Result.OrphanedNodes, ElementsAre(0xDEADBEEF + 2));
 319   EXPECT_THAT(Result.IntermediateNodes, IsEmpty());
 320 }
 321
 322 TEST_F(BasicGraphBuilderTest, BuildFlowGraphConditionalInfiniteLoop) {
 323   if (!SuccessfullyInitialised)
 324     return;
 325   Analysis.parseSectionContents(
 326       {
 327           0x75, 0xfe, // 0: jne 0 [-2]
 328           0xff, 0x10, // 2: callq *(%rax)
 329       },
 330       {0xDEADBEEF, 0x0});
 331   GraphResult Result =
 332       GraphBuilder::buildFlowGraph(Analysis, {0xDEADBEEF + 2, 0x0});
 333   EXPECT_THAT(Result.OrphanedNodes, IsEmpty());
 334   EXPECT_THAT(Result.ConditionalBranchNodes, SizeIs(1));
 335   EXPECT_THAT(
 336       Result.ConditionalBranchNodes,
 337       Each(AllOf(Field(&ConditionalBranchNode::CFIProtection, Eq(false)),
 338                  Field(&ConditionalBranchNode::Target,
 339                        HasPath(Result, ElementsAre(0xDEADBEEF))),
 340                  Field(&ConditionalBranchNode::Fallthrough,
 341                        HasPath(Result, ElementsAre(0xDEADBEEF + 2))))))
 342       << PrintToString(Result);
 343 }
 344
 345 TEST_F(BasicGraphBuilderTest, BuildFlowGraphUnconditionalInfiniteLoop) {
 346   if (!SuccessfullyInitialised)
 347     return;
 348   Analysis.parseSectionContents(
 349       {
 350           0x75, 0x02, // 0: jne 4 [+2]
 351           0xeb, 0xfc, // 2: jmp 0 [-4]
 352           0xff, 0x10, // 4: callq *(%rax)
 353       },
 354       {0xDEADBEEF, 0x0});
 355   GraphResult Result =
 356       GraphBuilder::buildFlowGraph(Analysis, {0xDEADBEEF + 4, 0x0});
 357   EXPECT_THAT(Result.OrphanedNodes, IsEmpty());
 358   EXPECT_THAT(Result.ConditionalBranchNodes, SizeIs(1));
 359   EXPECT_THAT(
 360       Result.ConditionalBranchNodes,
 361       Contains(
 362           AllOf(Field(&ConditionalBranchNode::Address, Eq(0xDEADBEEF)),
 363                 Field(&ConditionalBranchNode::Fallthrough,
 364                       HasPath(Result, ElementsAre(0xDEADBEEF + 2, 0xDEADBEEF))),
 365                 Field(&ConditionalBranchNode::Target,
 366                       HasPath(Result, ElementsAre(0xDEADBEEF + 4))))))
 367       << PrintToString(Result);
 368 }
 369
 370 TEST_F(BasicGraphBuilderTest, BuildFlowGraphNoFlowsToIndirection) {
 371   if (!SuccessfullyInitialised)
 372     return;
 373   Analysis.parseSectionContents(
 374       {
 375           0x75, 0x00, // 0: jne 2 [+0]
 376           0xeb, 0xfc, // 2: jmp 0 [-4]
 377           0xff, 0x10, // 4: callq *(%rax)
 378       },
 379       {0xDEADBEEF, 0x0});
 380   GraphResult Result =
 381       GraphBuilder::buildFlowGraph(Analysis, {0xDEADBEEF + 4, 0x0});
 382   EXPECT_THAT(Result.OrphanedNodes, ElementsAre(0xDEADBEEF + 4));
 383   EXPECT_THAT(Result.ConditionalBranchNodes, IsEmpty());
 384 }
 385
 386 TEST_F(BasicGraphBuilderTest, BuildFlowGraphLengthExceededUpwards) {
 387   if (!SuccessfullyInitialised)
 388     return;
 389   Analysis.parseSectionContents(
 390       {
 391           0x75, 0x06, // 0: jne 8 [+6]
 392           0x90,       // 2: nop
 393           0x90,       // 3: nop
 394           0x90,       // 4: nop
 395           0x90,       // 5: nop
 396           0xff, 0x10, // 6: callq *(%rax)
 397           0x0f, 0x0b, // 8: ud2
 398       },
 399       {0xDEADBEEF, 0x0});
 400   uint64_t PrevSearchLengthForConditionalBranch =
 401       SearchLengthForConditionalBranch;
 402   SearchLengthForConditionalBranch = 2;
 403
 404   GraphResult Result =
 405       GraphBuilder::buildFlowGraph(Analysis, {0xDEADBEEF + 6, 0x0});
 406   EXPECT_THAT(Result.OrphanedNodes, SizeIs(1));
 407   EXPECT_THAT(Result.OrphanedNodes,
 408               Each(HasPath(Result, ElementsAre(0xDEADBEEF + 4, 0xDEADBEEF + 5,
 409                                                0xDEADBEEF + 6))))
 410       << PrintToString(Result);
 411   EXPECT_THAT(Result.ConditionalBranchNodes, IsEmpty());
 412
 413   SearchLengthForConditionalBranch = PrevSearchLengthForConditionalBranch;
 414 }
 415
 416 TEST_F(BasicGraphBuilderTest, BuildFlowGraphLengthExceededDownwards) {
 417   if (!SuccessfullyInitialised)
 418     return;
 419   Analysis.parseSectionContents(
 420       {
 421           0x75, 0x02, // 0: jne 4 [+2]
 422           0xff, 0x10, // 2: callq *(%rax)
 423           0x90,       // 4: nop
 424           0x90,       // 5: nop
 425           0x90,       // 6: nop
 426           0x90,       // 7: nop
 427           0x0f, 0x0b, // 8: ud2
 428       },
 429       {0xDEADBEEF, 0x0});
 430   uint64_t PrevSearchLengthForUndef = SearchLengthForUndef;
 431   SearchLengthForUndef = 2;
 432
 433   GraphResult Result =
 434       GraphBuilder::buildFlowGraph(Analysis, {0xDEADBEEF + 2, 0x0});
 435   EXPECT_THAT(Result.OrphanedNodes, IsEmpty());
 436   EXPECT_THAT(
 437       Result.ConditionalBranchNodes,
 438       Each(AllOf(
 439           Field(&ConditionalBranchNode::CFIProtection, Eq(false)),
 440           Field(&ConditionalBranchNode::Address, Eq(0xDEADBEEF)),
 441           Field(&ConditionalBranchNode::Target,
 442                 HasPath(Result, ElementsAre(0xDEADBEEF + 4, 0xDEADBEEF + 5))),
 443           Field(&ConditionalBranchNode::Fallthrough,
 444                 HasPath(Result, ElementsAre(0xDEADBEEF + 2))))))
 445       << PrintToString(Result);
 446
 447   SearchLengthForUndef = PrevSearchLengthForUndef;
 448 }
 449
 450 // This test ensures when avoiding doing repeated work we still generate the
 451 // paths correctly. We don't need to recalculate the flow from 0x2 -> 0x3 as it
 452 // should only need to be generated once.
 453 TEST_F(BasicGraphBuilderTest, BuildFlowGraphWithRepeatedWork) {
 454   if (!SuccessfullyInitialised)
 455     return;
 456   Analysis.parseSectionContents(
 457       {
 458           0x75, 0x05, // 0: jne 7 [+5]
 459           0x90,       // 2: nop
 460           0xff, 0x10, // 3: callq *(%rax)
 461           0x75, 0xfb, // 5: jne 2 [-5]
 462           0x0f, 0x0b, // 7: ud2
 463       },
 464       {0xDEADBEEF, 0x0});
 465   GraphResult Result =
 466       GraphBuilder::buildFlowGraph(Analysis, {0xDEADBEEF + 3, 0x0});
 467   EXPECT_THAT(Result.OrphanedNodes, IsEmpty());
 468   EXPECT_THAT(Result.ConditionalBranchNodes, SizeIs(2));
 469   EXPECT_THAT(
 470       Result.ConditionalBranchNodes,
 471       Contains(AllOf(
 472           Field(&ConditionalBranchNode::CFIProtection, Eq(true)),
 473           Field(&ConditionalBranchNode::Address, Eq(0xDEADBEEF)),
 474           Field(&ConditionalBranchNode::Target,
 475                 HasPath(Result, ElementsAre(0xDEADBEEF + 7))),
 476           Field(&ConditionalBranchNode::Fallthrough,
 477                 HasPath(Result, ElementsAre(0xDEADBEEF + 2, 0xDEADBEEF + 3))))))
 478       << PrintToString(Result);
 479   EXPECT_THAT(
 480       Result.ConditionalBranchNodes,
 481       Contains(AllOf(
 482           Field(&ConditionalBranchNode::CFIProtection, Eq(true)),
 483           Field(&ConditionalBranchNode::Address, Eq(0xDEADBEEF + 5)),
 484           Field(&ConditionalBranchNode::Target,
 485                 HasPath(Result, ElementsAre(0xDEADBEEF + 2, 0xDEADBEEF + 3))),
 486           Field(&ConditionalBranchNode::Fallthrough,
 487                 HasPath(Result, ElementsAre(0xDEADBEEF + 7))))))
 488       << PrintToString(Result);
 489   EXPECT_THAT(Result.IntermediateNodes, SizeIs(1));
 490   EXPECT_THAT(Result.IntermediateNodes,
 491               UnorderedElementsAre(Pair(0xDEADBEEF + 2, 0xDEADBEEF + 3)));
 492 }
 493
 494 TEST_F(BasicGraphBuilderTest, BuildFlowGraphComplexExample) {
 495   if (!SuccessfullyInitialised)
 496     return;
 497   // The following code has this graph:
 498   //  +----------+      +--------------+
 499   //  |    20    | <--- |      0       |
 500   //  +----------+      +--------------+
 501   //    |                 |
 502   //    v                 v
 503   //  +----------+      +--------------+
 504   //  |    21    |      |      2       |
 505   //  +----------+      +--------------+
 506   //    |                 |
 507   //    v                 v
 508   //  +----------+      +--------------+
 509   //  | 22 (ud2) |  +-> |      7       |
 510   //  +----------+  |   +--------------+
 511   //    ^           |     |
 512   //    |           |     v
 513   //  +----------+  |   +--------------+
 514   //  |    4     |  |   |      8       |
 515   //  +----------+  |   +--------------+
 516   //    |           |     |
 517   //    v           |     v
 518   //  +----------+  |   +--------------+    +------------+
 519   //  |    6     | -+   | 9 (indirect) | <- |     13     |
 520   //  +----------+      +--------------+    +------------+
 521   //                      ^                   |
 522   //                      |                   v
 523   //                    +--------------+    +------------+
 524   //                    |      11      |    | 15 (error) |
 525   //                    +--------------+    +------------+
 526   // Or, in image format: https://i.imgur.com/aX5fCoi.png
 527
 528   Analysis.parseSectionContents(
 529       {
 530           0x75, 0x12,                   // 0: jne 20 [+18]
 531           0xeb, 0x03,                   // 2: jmp 7 [+3]
 532           0x75, 0x10,                   // 4: jne 22 [+16]
 533           0x90,                         // 6: nop
 534           0x90,                         // 7: nop
 535           0x90,                         // 8: nop
 536           0xff, 0x10,                   // 9: callq *(%rax)
 537           0xeb, 0xfc,                   // 11: jmp 9 [-4]
 538           0x75, 0xfa,                   // 13: jne 9 [-6]
 539           0xe8, 0x78, 0x56, 0x34, 0x12, // 15: callq OUTOFBOUNDS [+0x12345678]
 540           0x90,                         // 20: nop
 541           0x90,                         // 21: nop
 542           0x0f, 0x0b,                   // 22: ud2
 543       },
 544       {0x1000, 0x0});
 545   uint64_t PrevSearchLengthForUndef = SearchLengthForUndef;
 546   SearchLengthForUndef = 5;
 547
 548   GraphResult Result =
 549       GraphBuilder::buildFlowGraph(Analysis, {0x1000 + 9, 0x0});
 550
 551   EXPECT_THAT(Result.OrphanedNodes, SizeIs(1));
 552   EXPECT_THAT(Result.ConditionalBranchNodes, SizeIs(3));
 553
 554   EXPECT_THAT(
 555       Result.OrphanedNodes,
 556       Each(AllOf(Eq(0x1000u + 11),
 557                  HasPath(Result, ElementsAre(0x1000 + 11, 0x1000 + 9)))))
 558       << PrintToString(Result);
 559
 560   EXPECT_THAT(Result.ConditionalBranchNodes,
 561               Contains(AllOf(
 562                   Field(&ConditionalBranchNode::CFIProtection, Eq(true)),
 563                   Field(&ConditionalBranchNode::Address, Eq(0x1000u)),
 564                   Field(&ConditionalBranchNode::Target,
 565                         HasPath(Result, ElementsAre(0x1000 + 20, 0x1000 + 21,
 566                                                     0x1000 + 22))),
 567                   Field(&ConditionalBranchNode::Fallthrough,
 568                         HasPath(Result, ElementsAre(0x1000 + 2, 0x1000 + 7,
 569                                                     0x1000 + 8, 0x1000 + 9))))))
 570       << PrintToString(Result);
 571
 572   EXPECT_THAT(Result.ConditionalBranchNodes,
 573               Contains(AllOf(
 574                   Field(&ConditionalBranchNode::CFIProtection, Eq(true)),
 575                   Field(&ConditionalBranchNode::Address, Eq(0x1000u + 4)),
 576                   Field(&ConditionalBranchNode::Target,
 577                         HasPath(Result, ElementsAre(0x1000 + 22))),
 578                   Field(&ConditionalBranchNode::Fallthrough,
 579                         HasPath(Result, ElementsAre(0x1000 + 6, 0x1000 + 7,
 580                                                     0x1000 + 8, 0x1000 + 9))))))
 581       << PrintToString(Result);
 582
 583   EXPECT_THAT(
 584       Result.ConditionalBranchNodes,
 585       Contains(AllOf(Field(&ConditionalBranchNode::CFIProtection, Eq(false)),
 586                      Field(&ConditionalBranchNode::Address, Eq(0x1000u + 13)),
 587                      Field(&ConditionalBranchNode::Target,
 588                            HasPath(Result, ElementsAre(0x1000 + 9))),
 589                      Field(&ConditionalBranchNode::Fallthrough,
 590                            HasPath(Result, ElementsAre(0x1000 + 15))))))
 591       << PrintToString(Result);
 592
 593   SearchLengthForUndef = PrevSearchLengthForUndef;
 594 }
 595
 596 } // anonymous namespace
 597 } // end namespace cfi_verify
 598 } // end namespace llvm