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