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