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