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.
HexStringifyContainer(const std::vector<uint64_t> & C)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
PrintTo(const ConditionalBranchNode & BranchNode,::std::ostream * os)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
PrintTo(const GraphResult & Result,::std::ostream * os)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:
ELFx86TestFileAnalysis()111 ELFx86TestFileAnalysis()
112 : FileAnalysis(Triple("x86_64--"), SubtargetFeatures()) {}
113
114 // Expose this method publicly for testing.
parseSectionContents(ArrayRef<uint8_t> SectionBytes,object::SectionedAddress Address)115 void parseSectionContents(ArrayRef<uint8_t> SectionBytes,
116 object::SectionedAddress Address) {
117 FileAnalysis::parseSectionContents(SectionBytes, Address);
118 }
119
initialiseDisassemblyMembers()120 Error initialiseDisassemblyMembers() {
121 return FileAnalysis::initialiseDisassemblyMembers();
122 }
123 };
124
125 class BasicGraphBuilderTest : public ::testing::Test {
126 protected:
SetUp()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
TEST_F(BasicGraphBuilderTest,BuildFlowGraphTestSinglePathFallthroughUd2)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
TEST_F(BasicGraphBuilderTest,BuildFlowGraphTestSinglePathJumpUd2)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
TEST_F(BasicGraphBuilderTest,BuildFlowGraphTestDualPathDualUd2)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
TEST_F(BasicGraphBuilderTest,BuildFlowGraphTestDualPathSingleUd2)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
TEST_F(BasicGraphBuilderTest,BuildFlowGraphFailures)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
TEST_F(BasicGraphBuilderTest,BuildFlowGraphNoXrefs)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
TEST_F(BasicGraphBuilderTest,BuildFlowGraphConditionalInfiniteLoop)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
TEST_F(BasicGraphBuilderTest,BuildFlowGraphUnconditionalInfiniteLoop)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
TEST_F(BasicGraphBuilderTest,BuildFlowGraphNoFlowsToIndirection)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
TEST_F(BasicGraphBuilderTest,BuildFlowGraphLengthExceededUpwards)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
TEST_F(BasicGraphBuilderTest,BuildFlowGraphLengthExceededDownwards)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.
TEST_F(BasicGraphBuilderTest,BuildFlowGraphWithRepeatedWork)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
TEST_F(BasicGraphBuilderTest,BuildFlowGraphComplexExample)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
599
