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                             uint64_t SectionAddress) {
 117     FileAnalysis::parseSectionContents(SectionBytes, SectionAddress);
 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);
 160   const auto Result = GraphBuilder::buildFlowGraph(Analysis, 0xDEADBEEF + 4);
 161
 162   EXPECT_THAT(Result.OrphanedNodes, IsEmpty());
 163   EXPECT_THAT(Result.ConditionalBranchNodes, SizeIs(1));
 164   EXPECT_THAT(Result.ConditionalBranchNodes,
 165               Each(Field(&ConditionalBranchNode::CFIProtection, Eq(true))));
 166   EXPECT_THAT(
 167       Result.ConditionalBranchNodes,
 168       Contains(AllOf(Field(&ConditionalBranchNode::Address, Eq(0xDEADBEEF)),
 169                      Field(&ConditionalBranchNode::Target,
 170                            HasPath(Result, ElementsAre(0xDEADBEEF + 4))),
 171                      Field(&ConditionalBranchNode::Fallthrough,
 172                            HasPath(Result, ElementsAre(0xDEADBEEF + 2))))))
 173       << PrintToString(Result);
 174 }
 175
 176 TEST_F(BasicGraphBuilderTest, BuildFlowGraphTestSinglePathJumpUd2) {
 177   if (!SuccessfullyInitialised)
 178     return;
 179   Analysis.parseSectionContents(
 180       {
 181           0x75, 0x02, // 0: jne 4 [+2]
 182           0xff, 0x10, // 2: callq *(%rax)
 183           0x0f, 0x0b, // 4: ud2
 184       },
 185       0xDEADBEEF);
 186   const auto Result = GraphBuilder::buildFlowGraph(Analysis, 0xDEADBEEF + 2);
 187
 188   EXPECT_THAT(Result.OrphanedNodes, IsEmpty());
 189   EXPECT_THAT(Result.ConditionalBranchNodes, SizeIs(1));
 190   EXPECT_THAT(Result.ConditionalBranchNodes,
 191               Each(Field(&ConditionalBranchNode::CFIProtection, Eq(true))));
 192   EXPECT_THAT(
 193       Result.ConditionalBranchNodes,
 194       Contains(AllOf(Field(&ConditionalBranchNode::Address, Eq(0xDEADBEEF)),
 195                      Field(&ConditionalBranchNode::Target,
 196                            HasPath(Result, ElementsAre(0xDEADBEEF + 4))),
 197                      Field(&ConditionalBranchNode::Fallthrough,
 198                            HasPath(Result, ElementsAre(0xDEADBEEF + 2))))))
 199       << PrintToString(Result);
 200 }
 201
 202 TEST_F(BasicGraphBuilderTest, BuildFlowGraphTestDualPathDualUd2) {
 203   if (!SuccessfullyInitialised)
 204     return;
 205   Analysis.parseSectionContents(
 206       {
 207           0x75, 0x03, // 0: jne 5 [+3]
 208           0x90,       // 2: nop
 209           0xff, 0x10, // 3: callq *(%rax)
 210           0x0f, 0x0b, // 5: ud2
 211           0x75, 0xf9, // 7: jne 2 [-7]
 212           0x0f, 0x0b, // 9: ud2
 213       },
 214       0xDEADBEEF);
 215   const auto Result = GraphBuilder::buildFlowGraph(Analysis, 0xDEADBEEF + 3);
 216
 217   EXPECT_THAT(Result.OrphanedNodes, IsEmpty());
 218   EXPECT_THAT(Result.ConditionalBranchNodes, SizeIs(2));
 219   EXPECT_THAT(Result.ConditionalBranchNodes,
 220               Each(Field(&ConditionalBranchNode::CFIProtection, Eq(true))));
 221   EXPECT_THAT(
 222       Result.ConditionalBranchNodes,
 223       Contains(AllOf(
 224           Field(&ConditionalBranchNode::Address, Eq(0xDEADBEEF)),
 225           Field(&ConditionalBranchNode::Fallthrough,
 226                 HasPath(Result, ElementsAre(0xDEADBEEF + 2, 0xDEADBEEF + 3))),
 227           Field(&ConditionalBranchNode::Target,
 228                 HasPath(Result, ElementsAre(0xDEADBEEF + 5))))))
 229       << PrintToString(Result);
 230   EXPECT_THAT(
 231       Result.ConditionalBranchNodes,
 232       Contains(AllOf(
 233           Field(&ConditionalBranchNode::Address, Eq(0xDEADBEEF + 7)),
 234           Field(&ConditionalBranchNode::Fallthrough,
 235                 HasPath(Result, ElementsAre(0xDEADBEEF + 9))),
 236           Field(&ConditionalBranchNode::Target,
 237                 HasPath(Result, ElementsAre(0xDEADBEEF + 2, 0xDEADBEEF + 3))))))
 238       << PrintToString(Result);
 239 }
 240
 241 TEST_F(BasicGraphBuilderTest, BuildFlowGraphTestDualPathSingleUd2) {
 242   if (!SuccessfullyInitialised)
 243     return;
 244   Analysis.parseSectionContents(
 245       {
 246           0x75, 0x05, // 0: jne 7 [+5]
 247           0x90,       // 2: nop
 248           0xff, 0x10, // 3: callq *(%rax)
 249           0x75, 0xfb, // 5: jne 2 [-5]
 250           0x0f, 0x0b, // 7: ud2
 251       },
 252       0xDEADBEEF);
 253   GraphResult Result = GraphBuilder::buildFlowGraph(Analysis, 0xDEADBEEF + 3);
 254
 255   EXPECT_THAT(Result.OrphanedNodes, IsEmpty());
 256   EXPECT_THAT(Result.ConditionalBranchNodes, SizeIs(2));
 257   EXPECT_THAT(Result.ConditionalBranchNodes,
 258               Each(Field(&ConditionalBranchNode::CFIProtection, Eq(true))));
 259   EXPECT_THAT(
 260       Result.ConditionalBranchNodes,
 261       Contains(AllOf(
 262           Field(&ConditionalBranchNode::Address, Eq(0xDEADBEEF)),
 263           Field(&ConditionalBranchNode::Fallthrough,
 264                 HasPath(Result, ElementsAre(0xDEADBEEF + 2, 0xDEADBEEF + 3))),
 265           Field(&ConditionalBranchNode::Target,
 266                 HasPath(Result, ElementsAre(0xDEADBEEF + 7))))))
 267       << PrintToString(Result);
 268   EXPECT_THAT(
 269       Result.ConditionalBranchNodes,
 270       Contains(AllOf(
 271           Field(&ConditionalBranchNode::Address, Eq(0xDEADBEEF + 5)),
 272           Field(&ConditionalBranchNode::Fallthrough,
 273                 HasPath(Result, ElementsAre(0xDEADBEEF + 7))),
 274           Field(&ConditionalBranchNode::Target,
 275                 HasPath(Result, ElementsAre(0xDEADBEEF + 2, 0xDEADBEEF + 3))))))
 276       << PrintToString(Result);
 277 }
 278
 279 TEST_F(BasicGraphBuilderTest, BuildFlowGraphFailures) {
 280   if (!SuccessfullyInitialised)
 281     return;
 282   Analysis.parseSectionContents(
 283       {
 284           0x90,       // 0: nop
 285           0x75, 0xfe, // 1: jne 1 [-2]
 286       },
 287       0xDEADBEEF);
 288   GraphResult Result = GraphBuilder::buildFlowGraph(Analysis, 0xDEADBEEF);
 289   EXPECT_THAT(Result.OrphanedNodes, IsEmpty());
 290   EXPECT_THAT(Result.ConditionalBranchNodes, IsEmpty());
 291
 292   Result = GraphBuilder::buildFlowGraph(Analysis, 0xDEADBEEF + 1);
 293   EXPECT_THAT(Result.OrphanedNodes, IsEmpty());
 294   EXPECT_THAT(Result.ConditionalBranchNodes, IsEmpty());
 295
 296   Result = GraphBuilder::buildFlowGraph(Analysis, 0xDEADC0DE);
 297   EXPECT_THAT(Result.OrphanedNodes, IsEmpty());
 298   EXPECT_THAT(Result.ConditionalBranchNodes, IsEmpty());
 299 }
 300
 301 TEST_F(BasicGraphBuilderTest, BuildFlowGraphNoXrefs) {
 302   if (!SuccessfullyInitialised)
 303     return;
 304   Analysis.parseSectionContents(
 305       {
 306           0xeb, 0xfe, // 0: jmp 0 [-2]
 307           0xff, 0x10, // 2: callq *(%rax)
 308       },
 309       0xDEADBEEF);
 310   GraphResult Result = GraphBuilder::buildFlowGraph(Analysis, 0xDEADBEEF + 2);
 311   EXPECT_THAT(Result.ConditionalBranchNodes, IsEmpty());
 312   EXPECT_THAT(Result.OrphanedNodes, ElementsAre(0xDEADBEEF + 2));
 313   EXPECT_THAT(Result.IntermediateNodes, IsEmpty());
 314 }
 315
 316 TEST_F(BasicGraphBuilderTest, BuildFlowGraphConditionalInfiniteLoop) {
 317   if (!SuccessfullyInitialised)
 318     return;
 319   Analysis.parseSectionContents(
 320       {
 321           0x75, 0xfe, // 0: jne 0 [-2]
 322           0xff, 0x10, // 2: callq *(%rax)
 323       },
 324       0xDEADBEEF);
 325   GraphResult Result = GraphBuilder::buildFlowGraph(Analysis, 0xDEADBEEF + 2);
 326   EXPECT_THAT(Result.OrphanedNodes, IsEmpty());
 327   EXPECT_THAT(Result.ConditionalBranchNodes, SizeIs(1));
 328   EXPECT_THAT(
 329       Result.ConditionalBranchNodes,
 330       Each(AllOf(Field(&ConditionalBranchNode::CFIProtection, Eq(false)),
 331                  Field(&ConditionalBranchNode::Target,
 332                        HasPath(Result, ElementsAre(0xDEADBEEF))),
 333                  Field(&ConditionalBranchNode::Fallthrough,
 334                        HasPath(Result, ElementsAre(0xDEADBEEF + 2))))))
 335       << PrintToString(Result);
 336 }
 337
 338 TEST_F(BasicGraphBuilderTest, BuildFlowGraphUnconditionalInfiniteLoop) {
 339   if (!SuccessfullyInitialised)
 340     return;
 341   Analysis.parseSectionContents(
 342       {
 343           0x75, 0x02, // 0: jne 4 [+2]
 344           0xeb, 0xfc, // 2: jmp 0 [-4]
 345           0xff, 0x10, // 4: callq *(%rax)
 346       },
 347       0xDEADBEEF);
 348   GraphResult Result = GraphBuilder::buildFlowGraph(Analysis, 0xDEADBEEF + 4);
 349   EXPECT_THAT(Result.OrphanedNodes, IsEmpty());
 350   EXPECT_THAT(Result.ConditionalBranchNodes, SizeIs(1));
 351   EXPECT_THAT(
 352       Result.ConditionalBranchNodes,
 353       Contains(
 354           AllOf(Field(&ConditionalBranchNode::Address, Eq(0xDEADBEEF)),
 355                 Field(&ConditionalBranchNode::Fallthrough,
 356                       HasPath(Result, ElementsAre(0xDEADBEEF + 2, 0xDEADBEEF))),
 357                 Field(&ConditionalBranchNode::Target,
 358                       HasPath(Result, ElementsAre(0xDEADBEEF + 4))))))
 359       << PrintToString(Result);
 360 }
 361
 362 TEST_F(BasicGraphBuilderTest, BuildFlowGraphNoFlowsToIndirection) {
 363   if (!SuccessfullyInitialised)
 364     return;
 365   Analysis.parseSectionContents(
 366       {
 367           0x75, 0x00, // 0: jne 2 [+0]
 368           0xeb, 0xfc, // 2: jmp 0 [-4]
 369           0xff, 0x10, // 4: callq *(%rax)
 370       },
 371       0xDEADBEEF);
 372   GraphResult Result = GraphBuilder::buildFlowGraph(Analysis, 0xDEADBEEF + 4);
 373   EXPECT_THAT(Result.OrphanedNodes, ElementsAre(0xDEADBEEF + 4));
 374   EXPECT_THAT(Result.ConditionalBranchNodes, IsEmpty());
 375 }
 376
 377 TEST_F(BasicGraphBuilderTest, BuildFlowGraphLengthExceededUpwards) {
 378   if (!SuccessfullyInitialised)
 379     return;
 380   Analysis.parseSectionContents(
 381       {
 382           0x75, 0x06, // 0: jne 8 [+6]
 383           0x90,       // 2: nop
 384           0x90,       // 3: nop
 385           0x90,       // 4: nop
 386           0x90,       // 5: nop
 387           0xff, 0x10, // 6: callq *(%rax)
 388           0x0f, 0x0b, // 8: ud2
 389       },
 390       0xDEADBEEF);
 391   uint64_t PrevSearchLengthForConditionalBranch =
 392       SearchLengthForConditionalBranch;
 393   SearchLengthForConditionalBranch = 2;
 394
 395   GraphResult Result = GraphBuilder::buildFlowGraph(Analysis, 0xDEADBEEF + 6);
 396   EXPECT_THAT(Result.OrphanedNodes, SizeIs(1));
 397   EXPECT_THAT(Result.OrphanedNodes,
 398               Each(HasPath(Result, ElementsAre(0xDEADBEEF + 4, 0xDEADBEEF + 5,
 399                                                0xDEADBEEF + 6))))
 400       << PrintToString(Result);
 401   EXPECT_THAT(Result.ConditionalBranchNodes, IsEmpty());
 402
 403   SearchLengthForConditionalBranch = PrevSearchLengthForConditionalBranch;
 404 }
 405
 406 TEST_F(BasicGraphBuilderTest, BuildFlowGraphLengthExceededDownwards) {
 407   if (!SuccessfullyInitialised)
 408     return;
 409   Analysis.parseSectionContents(
 410       {
 411           0x75, 0x02, // 0: jne 4 [+2]
 412           0xff, 0x10, // 2: callq *(%rax)
 413           0x90,       // 4: nop
 414           0x90,       // 5: nop
 415           0x90,       // 6: nop
 416           0x90,       // 7: nop
 417           0x0f, 0x0b, // 8: ud2
 418       },
 419       0xDEADBEEF);
 420   uint64_t PrevSearchLengthForUndef = SearchLengthForUndef;
 421   SearchLengthForUndef = 2;
 422
 423   GraphResult Result = GraphBuilder::buildFlowGraph(Analysis, 0xDEADBEEF + 2);
 424   EXPECT_THAT(Result.OrphanedNodes, IsEmpty());
 425   EXPECT_THAT(
 426       Result.ConditionalBranchNodes,
 427       Each(AllOf(
 428           Field(&ConditionalBranchNode::CFIProtection, Eq(false)),
 429           Field(&ConditionalBranchNode::Address, Eq(0xDEADBEEF)),
 430           Field(&ConditionalBranchNode::Target,
 431                 HasPath(Result, ElementsAre(0xDEADBEEF + 4, 0xDEADBEEF + 5))),
 432           Field(&ConditionalBranchNode::Fallthrough,
 433                 HasPath(Result, ElementsAre(0xDEADBEEF + 2))))))
 434       << PrintToString(Result);
 435
 436   SearchLengthForUndef = PrevSearchLengthForUndef;
 437 }
 438
 439 // This test ensures when avoiding doing repeated work we still generate the
 440 // paths correctly. We don't need to recalculate the flow from 0x2 -> 0x3 as it
 441 // should only need to be generated once.
 442 TEST_F(BasicGraphBuilderTest, BuildFlowGraphWithRepeatedWork) {
 443   if (!SuccessfullyInitialised)
 444     return;
 445   Analysis.parseSectionContents(
 446       {
 447           0x75, 0x05, // 0: jne 7 [+5]
 448           0x90,       // 2: nop
 449           0xff, 0x10, // 3: callq *(%rax)
 450           0x75, 0xfb, // 5: jne 2 [-5]
 451           0x0f, 0x0b, // 7: ud2
 452       },
 453       0xDEADBEEF);
 454   GraphResult Result = GraphBuilder::buildFlowGraph(Analysis, 0xDEADBEEF + 3);
 455   EXPECT_THAT(Result.OrphanedNodes, IsEmpty());
 456   EXPECT_THAT(Result.ConditionalBranchNodes, SizeIs(2));
 457   EXPECT_THAT(
 458       Result.ConditionalBranchNodes,
 459       Contains(AllOf(
 460           Field(&ConditionalBranchNode::CFIProtection, Eq(true)),
 461           Field(&ConditionalBranchNode::Address, Eq(0xDEADBEEF)),
 462           Field(&ConditionalBranchNode::Target,
 463                 HasPath(Result, ElementsAre(0xDEADBEEF + 7))),
 464           Field(&ConditionalBranchNode::Fallthrough,
 465                 HasPath(Result, ElementsAre(0xDEADBEEF + 2, 0xDEADBEEF + 3))))))
 466       << PrintToString(Result);
 467   EXPECT_THAT(
 468       Result.ConditionalBranchNodes,
 469       Contains(AllOf(
 470           Field(&ConditionalBranchNode::CFIProtection, Eq(true)),
 471           Field(&ConditionalBranchNode::Address, Eq(0xDEADBEEF + 5)),
 472           Field(&ConditionalBranchNode::Target,
 473                 HasPath(Result, ElementsAre(0xDEADBEEF + 2, 0xDEADBEEF + 3))),
 474           Field(&ConditionalBranchNode::Fallthrough,
 475                 HasPath(Result, ElementsAre(0xDEADBEEF + 7))))))
 476       << PrintToString(Result);
 477   EXPECT_THAT(Result.IntermediateNodes, SizeIs(1));
 478   EXPECT_THAT(Result.IntermediateNodes,
 479               UnorderedElementsAre(Pair(0xDEADBEEF + 2, 0xDEADBEEF + 3)));
 480 }
 481
 482 TEST_F(BasicGraphBuilderTest, BuildFlowGraphComplexExample) {
 483   if (!SuccessfullyInitialised)
 484     return;
 485   // The following code has this graph:
 486   //  +----------+      +--------------+
 487   //  |    20    | <--- |      0       |
 488   //  +----------+      +--------------+
 489   //    |                 |
 490   //    v                 v
 491   //  +----------+      +--------------+
 492   //  |    21    |      |      2       |
 493   //  +----------+      +--------------+
 494   //    |                 |
 495   //    v                 v
 496   //  +----------+      +--------------+
 497   //  | 22 (ud2) |  +-> |      7       |
 498   //  +----------+  |   +--------------+
 499   //    ^           |     |
 500   //    |           |     v
 501   //  +----------+  |   +--------------+
 502   //  |    4     |  |   |      8       |
 503   //  +----------+  |   +--------------+
 504   //    |           |     |
 505   //    v           |     v
 506   //  +----------+  |   +--------------+    +------------+
 507   //  |    6     | -+   | 9 (indirect) | <- |     13     |
 508   //  +----------+      +--------------+    +------------+
 509   //                      ^                   |
 510   //                      |                   v
 511   //                    +--------------+    +------------+
 512   //                    |      11      |    | 15 (error) |
 513   //                    +--------------+    +------------+
 514   // Or, in image format: https://i.imgur.com/aX5fCoi.png
 515
 516   Analysis.parseSectionContents(
 517       {
 518           0x75, 0x12,                   // 0: jne 20 [+18]
 519           0xeb, 0x03,                   // 2: jmp 7 [+3]
 520           0x75, 0x10,                   // 4: jne 22 [+16]
 521           0x90,                         // 6: nop
 522           0x90,                         // 7: nop
 523           0x90,                         // 8: nop
 524           0xff, 0x10,                   // 9: callq *(%rax)
 525           0xeb, 0xfc,                   // 11: jmp 9 [-4]
 526           0x75, 0xfa,                   // 13: jne 9 [-6]
 527           0xe8, 0x78, 0x56, 0x34, 0x12, // 15: callq OUTOFBOUNDS [+0x12345678]
 528           0x90,                         // 20: nop
 529           0x90,                         // 21: nop
 530           0x0f, 0x0b,                   // 22: ud2
 531       },
 532       0x1000);
 533   uint64_t PrevSearchLengthForUndef = SearchLengthForUndef;
 534   SearchLengthForUndef = 5;
 535
 536   GraphResult Result = GraphBuilder::buildFlowGraph(Analysis, 0x1000 + 9);
 537
 538   EXPECT_THAT(Result.OrphanedNodes, SizeIs(1));
 539   EXPECT_THAT(Result.ConditionalBranchNodes, SizeIs(3));
 540
 541   EXPECT_THAT(
 542       Result.OrphanedNodes,
 543       Each(AllOf(Eq(0x1000u + 11),
 544                  HasPath(Result, ElementsAre(0x1000 + 11, 0x1000 + 9)))))
 545       << PrintToString(Result);
 546
 547   EXPECT_THAT(Result.ConditionalBranchNodes,
 548               Contains(AllOf(
 549                   Field(&ConditionalBranchNode::CFIProtection, Eq(true)),
 550                   Field(&ConditionalBranchNode::Address, Eq(0x1000u)),
 551                   Field(&ConditionalBranchNode::Target,
 552                         HasPath(Result, ElementsAre(0x1000 + 20, 0x1000 + 21,
 553                                                     0x1000 + 22))),
 554                   Field(&ConditionalBranchNode::Fallthrough,
 555                         HasPath(Result, ElementsAre(0x1000 + 2, 0x1000 + 7,
 556                                                     0x1000 + 8, 0x1000 + 9))))))
 557       << PrintToString(Result);
 558
 559   EXPECT_THAT(Result.ConditionalBranchNodes,
 560               Contains(AllOf(
 561                   Field(&ConditionalBranchNode::CFIProtection, Eq(true)),
 562                   Field(&ConditionalBranchNode::Address, Eq(0x1000u + 4)),
 563                   Field(&ConditionalBranchNode::Target,
 564                         HasPath(Result, ElementsAre(0x1000 + 22))),
 565                   Field(&ConditionalBranchNode::Fallthrough,
 566                         HasPath(Result, ElementsAre(0x1000 + 6, 0x1000 + 7,
 567                                                     0x1000 + 8, 0x1000 + 9))))))
 568       << PrintToString(Result);
 569
 570   EXPECT_THAT(
 571       Result.ConditionalBranchNodes,
 572       Contains(AllOf(Field(&ConditionalBranchNode::CFIProtection, Eq(false)),
 573                      Field(&ConditionalBranchNode::Address, Eq(0x1000u + 13)),
 574                      Field(&ConditionalBranchNode::Target,
 575                            HasPath(Result, ElementsAre(0x1000 + 9))),
 576                      Field(&ConditionalBranchNode::Fallthrough,
 577                            HasPath(Result, ElementsAre(0x1000 + 15))))))
 578       << PrintToString(Result);
 579
 580   SearchLengthForUndef = PrevSearchLengthForUndef;
 581 }
 582
 583 } // anonymous namespace
 584 } // end namespace cfi_verify
 585 } // end namespace llvm