Gitiles
Code Review Sign In
gerrit-public.fairphone.software / toolchain / llvm-project / a8b32dec677b28abe348984945e69c4d7e63125c / . / llvm / unittests / tools / llvm-cfi-verify / GraphBuilder.cpp
blob: a7d09b547814a6c178938469ed2c8b431a6d0231 [file] [log] [blame]
Mitch Phillips99fa1402017-10-23 20:25:19 +0000[diff] [blame]1//===- llvm/unittests/llvm-cfi-verify/GraphBuilder.cpp --------------===//
2//
3// The LLVM Compiler Infrastructure
4//
5// This file is distributed under the University of Illinois Open Source
6// License. See LICENSE.TXT for details.
7//
8//===----------------------------------------------------------------------===//
9
10#include "../tools/llvm-cfi-verify/lib/GraphBuilder.h"
11#include "../tools/llvm-cfi-verify/lib/FileAnalysis.h"
12#include "gmock/gmock.h"
13#include "gtest/gtest.h"
14
15#include "llvm/BinaryFormat/ELF.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/Object/Binary.h"
28#include "llvm/Object/COFF.h"
29#include "llvm/Object/ELFObjectFile.h"
30#include "llvm/Object/ObjectFile.h"
31#include "llvm/Support/Casting.h"
32#include "llvm/Support/CommandLine.h"
33#include "llvm/Support/Error.h"
34#include "llvm/Support/MemoryBuffer.h"
35#include "llvm/Support/TargetRegistry.h"
36#include "llvm/Support/TargetSelect.h"
37#include "llvm/Support/raw_ostream.h"
38
39#include <cstdlib>
40#include <sstream>
41
42using Instr = ::llvm::cfi_verify::FileAnalysis::Instr;
43using ::testing::AllOf;
44using ::testing::Each;
45using ::testing::ElementsAre;
46using ::testing::Eq;
47using ::testing::Field;
48using ::testing::IsEmpty;
49using ::testing::Matches;
50using ::testing::Pair;
51using ::testing::PrintToString;
52using ::testing::Property;
53using ::testing::SizeIs;
54using ::testing::UnorderedElementsAre;
55using ::testing::Value;
56
57namespace llvm {
58namespace cfi_verify {
59// Printing helpers for gtest.
60std::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
76void 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
83void 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
109namespace {
110class ELFx86TestFileAnalysis : public FileAnalysis {
111public:
112 ELFx86TestFileAnalysis()
113 : FileAnalysis(Triple("x86_64--"), SubtargetFeatures()) {}
114
115 // Expose this method publicly for testing.
116 void parseSectionContents(ArrayRef<uint8_t> SectionBytes,
117 uint64_t SectionAddress) {
118 FileAnalysis::parseSectionContents(SectionBytes, SectionAddress);
119 }
120
121 Error initialiseDisassemblyMembers() {
122 return FileAnalysis::initialiseDisassemblyMembers();
123 }
124};
125
126class BasicGraphBuilderTest : public ::testing::Test {
127protected:
128 virtual void SetUp() {
Mitch Phillipsc15bdf52017-11-03 20:54:26 +0000[diff] [blame]129 IgnoreDWARFFlag = true;
Mitch Phillipsd9af3832017-10-23 20:54:01 +0000[diff] [blame]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 });
Mitch Phillips99fa1402017-10-23 20:25:19 +0000[diff] [blame]138 }
139 }
140
Mitch Phillipsd9af3832017-10-23 20:54:01 +0000[diff] [blame]141 bool SuccessfullyInitialised;
Mitch Phillips99fa1402017-10-23 20:25:19 +0000[diff] [blame]142 ELFx86TestFileAnalysis Analysis;
143};
144
145MATCHER_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
151TEST_F(BasicGraphBuilderTest, BuildFlowGraphTestSinglePathFallthroughUd2) {
Mitch Phillipsd9af3832017-10-23 20:54:01 +0000[diff] [blame]152 if (!SuccessfullyInitialised)
153 return;
Mitch Phillips99fa1402017-10-23 20:25:19 +0000[diff] [blame]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);
161 const auto Result = GraphBuilder::buildFlowGraph(Analysis, 0xDEADBEEF + 4);
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
177TEST_F(BasicGraphBuilderTest, BuildFlowGraphTestSinglePathJumpUd2) {
Mitch Phillipsd9af3832017-10-23 20:54:01 +0000[diff] [blame]178 if (!SuccessfullyInitialised)
179 return;
Mitch Phillips99fa1402017-10-23 20:25:19 +0000[diff] [blame]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);
187 const auto Result = GraphBuilder::buildFlowGraph(Analysis, 0xDEADBEEF + 2);
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
203TEST_F(BasicGraphBuilderTest, BuildFlowGraphTestDualPathDualUd2) {
Mitch Phillipsd9af3832017-10-23 20:54:01 +0000[diff] [blame]204 if (!SuccessfullyInitialised)
205 return;
Mitch Phillips99fa1402017-10-23 20:25:19 +0000[diff] [blame]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);
216 const auto Result = GraphBuilder::buildFlowGraph(Analysis, 0xDEADBEEF + 3);
217
218 EXPECT_THAT(Result.OrphanedNodes, IsEmpty());
219 EXPECT_THAT(Result.ConditionalBranchNodes, SizeIs(2));
220 EXPECT_THAT(Result.ConditionalBranchNodes,
221 Each(Field(&ConditionalBranchNode::CFIProtection, Eq(true))));
222 EXPECT_THAT(
223 Result.ConditionalBranchNodes,
224 Contains(AllOf(
225 Field(&ConditionalBranchNode::Address, Eq(0xDEADBEEF)),
226 Field(&ConditionalBranchNode::Fallthrough,
227 HasPath(Result, ElementsAre(0xDEADBEEF + 2, 0xDEADBEEF + 3))),
228 Field(&ConditionalBranchNode::Target,
229 HasPath(Result, ElementsAre(0xDEADBEEF + 5))))))
230 << PrintToString(Result);
231 EXPECT_THAT(
232 Result.ConditionalBranchNodes,
233 Contains(AllOf(
234 Field(&ConditionalBranchNode::Address, Eq(0xDEADBEEF + 7)),
235 Field(&ConditionalBranchNode::Fallthrough,
236 HasPath(Result, ElementsAre(0xDEADBEEF + 9))),
237 Field(&ConditionalBranchNode::Target,
238 HasPath(Result, ElementsAre(0xDEADBEEF + 2, 0xDEADBEEF + 3))))))
239 << PrintToString(Result);
240}
241
242TEST_F(BasicGraphBuilderTest, BuildFlowGraphTestDualPathSingleUd2) {
Mitch Phillipsd9af3832017-10-23 20:54:01 +0000[diff] [blame]243 if (!SuccessfullyInitialised)
244 return;
Mitch Phillips99fa1402017-10-23 20:25:19 +0000[diff] [blame]245 Analysis.parseSectionContents(
246 {
247 0x75, 0x05, // 0: jne 7 [+5]
248 0x90, // 2: nop
249 0xff, 0x10, // 3: callq *(%rax)
250 0x75, 0xfb, // 5: jne 2 [-5]
251 0x0f, 0x0b, // 7: ud2
252 },
253 0xDEADBEEF);
254 GraphResult Result = GraphBuilder::buildFlowGraph(Analysis, 0xDEADBEEF + 3);
255
256 EXPECT_THAT(Result.OrphanedNodes, IsEmpty());
257 EXPECT_THAT(Result.ConditionalBranchNodes, SizeIs(2));
258 EXPECT_THAT(Result.ConditionalBranchNodes,
259 Each(Field(&ConditionalBranchNode::CFIProtection, Eq(true))));
260 EXPECT_THAT(
261 Result.ConditionalBranchNodes,
262 Contains(AllOf(
263 Field(&ConditionalBranchNode::Address, Eq(0xDEADBEEF)),
264 Field(&ConditionalBranchNode::Fallthrough,
265 HasPath(Result, ElementsAre(0xDEADBEEF + 2, 0xDEADBEEF + 3))),
266 Field(&ConditionalBranchNode::Target,
267 HasPath(Result, ElementsAre(0xDEADBEEF + 7))))))
268 << PrintToString(Result);
269 EXPECT_THAT(
270 Result.ConditionalBranchNodes,
271 Contains(AllOf(
272 Field(&ConditionalBranchNode::Address, Eq(0xDEADBEEF + 5)),
273 Field(&ConditionalBranchNode::Fallthrough,
274 HasPath(Result, ElementsAre(0xDEADBEEF + 7))),
275 Field(&ConditionalBranchNode::Target,
276 HasPath(Result, ElementsAre(0xDEADBEEF + 2, 0xDEADBEEF + 3))))))
277 << PrintToString(Result);
278}
279
280TEST_F(BasicGraphBuilderTest, BuildFlowGraphFailures) {
Mitch Phillipsd9af3832017-10-23 20:54:01 +0000[diff] [blame]281 if (!SuccessfullyInitialised)
282 return;
Mitch Phillips99fa1402017-10-23 20:25:19 +0000[diff] [blame]283 Analysis.parseSectionContents(
284 {
285 0x90, // 0: nop
286 0x75, 0xfe, // 1: jne 1 [-2]
287 },
288 0xDEADBEEF);
289 GraphResult Result = GraphBuilder::buildFlowGraph(Analysis, 0xDEADBEEF);
290 EXPECT_THAT(Result.OrphanedNodes, IsEmpty());
291 EXPECT_THAT(Result.ConditionalBranchNodes, IsEmpty());
292
293 Result = GraphBuilder::buildFlowGraph(Analysis, 0xDEADBEEF + 1);
294 EXPECT_THAT(Result.OrphanedNodes, IsEmpty());
295 EXPECT_THAT(Result.ConditionalBranchNodes, IsEmpty());
296
297 Result = GraphBuilder::buildFlowGraph(Analysis, 0xDEADC0DE);
298 EXPECT_THAT(Result.OrphanedNodes, IsEmpty());
299 EXPECT_THAT(Result.ConditionalBranchNodes, IsEmpty());
300}
301
302TEST_F(BasicGraphBuilderTest, BuildFlowGraphNoXrefs) {
Mitch Phillipsd9af3832017-10-23 20:54:01 +0000[diff] [blame]303 if (!SuccessfullyInitialised)
304 return;
Mitch Phillips99fa1402017-10-23 20:25:19 +0000[diff] [blame]305 Analysis.parseSectionContents(
306 {
307 0xeb, 0xfe, // 0: jmp 0 [-2]
308 0xff, 0x10, // 2: callq *(%rax)
309 },
310 0xDEADBEEF);
311 GraphResult Result = GraphBuilder::buildFlowGraph(Analysis, 0xDEADBEEF + 2);
312 EXPECT_THAT(Result.ConditionalBranchNodes, IsEmpty());
313 EXPECT_THAT(Result.OrphanedNodes, ElementsAre(0xDEADBEEF + 2));
314 EXPECT_THAT(Result.IntermediateNodes, IsEmpty());
315}
316
317TEST_F(BasicGraphBuilderTest, BuildFlowGraphConditionalInfiniteLoop) {
Mitch Phillipsd9af3832017-10-23 20:54:01 +0000[diff] [blame]318 if (!SuccessfullyInitialised)
319 return;
Mitch Phillips99fa1402017-10-23 20:25:19 +0000[diff] [blame]320 Analysis.parseSectionContents(
321 {
322 0x75, 0xfe, // 0: jne 0 [-2]
323 0xff, 0x10, // 2: callq *(%rax)
324 },
325 0xDEADBEEF);
326 GraphResult Result = GraphBuilder::buildFlowGraph(Analysis, 0xDEADBEEF + 2);
327 EXPECT_THAT(Result.OrphanedNodes, IsEmpty());
328 EXPECT_THAT(Result.ConditionalBranchNodes, SizeIs(1));
329 EXPECT_THAT(
330 Result.ConditionalBranchNodes,
331 Each(AllOf(Field(&ConditionalBranchNode::CFIProtection, Eq(false)),
332 Field(&ConditionalBranchNode::Target,
333 HasPath(Result, ElementsAre(0xDEADBEEF))),
334 Field(&ConditionalBranchNode::Fallthrough,
335 HasPath(Result, ElementsAre(0xDEADBEEF + 2))))))
336 << PrintToString(Result);
337}
338
339TEST_F(BasicGraphBuilderTest, BuildFlowGraphUnconditionalInfiniteLoop) {
Mitch Phillipsd9af3832017-10-23 20:54:01 +0000[diff] [blame]340 if (!SuccessfullyInitialised)
341 return;
Mitch Phillips99fa1402017-10-23 20:25:19 +0000[diff] [blame]342 Analysis.parseSectionContents(
343 {
344 0x75, 0x02, // 0: jne 4 [+2]
345 0xeb, 0xfc, // 2: jmp 0 [-4]
346 0xff, 0x10, // 4: callq *(%rax)
347 },
348 0xDEADBEEF);
349 GraphResult Result = GraphBuilder::buildFlowGraph(Analysis, 0xDEADBEEF + 4);
350 EXPECT_THAT(Result.OrphanedNodes, IsEmpty());
351 EXPECT_THAT(Result.ConditionalBranchNodes, SizeIs(1));
352 EXPECT_THAT(
353 Result.ConditionalBranchNodes,
354 Contains(
355 AllOf(Field(&ConditionalBranchNode::Address, Eq(0xDEADBEEF)),
356 Field(&ConditionalBranchNode::Fallthrough,
357 HasPath(Result, ElementsAre(0xDEADBEEF + 2, 0xDEADBEEF))),
358 Field(&ConditionalBranchNode::Target,
359 HasPath(Result, ElementsAre(0xDEADBEEF + 4))))))
360 << PrintToString(Result);
361}
362
363TEST_F(BasicGraphBuilderTest, BuildFlowGraphNoFlowsToIndirection) {
Mitch Phillipsd9af3832017-10-23 20:54:01 +0000[diff] [blame]364 if (!SuccessfullyInitialised)
365 return;
Mitch Phillips99fa1402017-10-23 20:25:19 +0000[diff] [blame]366 Analysis.parseSectionContents(
367 {
368 0x75, 0x00, // 0: jne 2 [+0]
369 0xeb, 0xfc, // 2: jmp 0 [-4]
370 0xff, 0x10, // 4: callq *(%rax)
371 },
372 0xDEADBEEF);
373 GraphResult Result = GraphBuilder::buildFlowGraph(Analysis, 0xDEADBEEF + 4);
374 EXPECT_THAT(Result.OrphanedNodes, ElementsAre(0xDEADBEEF + 4));
375 EXPECT_THAT(Result.ConditionalBranchNodes, IsEmpty());
376}
377
378TEST_F(BasicGraphBuilderTest, BuildFlowGraphLengthExceededUpwards) {
Mitch Phillipsd9af3832017-10-23 20:54:01 +0000[diff] [blame]379 if (!SuccessfullyInitialised)
380 return;
Mitch Phillips99fa1402017-10-23 20:25:19 +0000[diff] [blame]381 Analysis.parseSectionContents(
382 {
383 0x75, 0x06, // 0: jne 8 [+6]
384 0x90, // 2: nop
385 0x90, // 3: nop
386 0x90, // 4: nop
387 0x90, // 5: nop
388 0xff, 0x10, // 6: callq *(%rax)
389 0x0f, 0x0b, // 8: ud2
390 },
391 0xDEADBEEF);
392 uint64_t PrevSearchLengthForConditionalBranch =
393 SearchLengthForConditionalBranch;
394 SearchLengthForConditionalBranch = 2;
395
396 GraphResult Result = GraphBuilder::buildFlowGraph(Analysis, 0xDEADBEEF + 6);
397 EXPECT_THAT(Result.OrphanedNodes, SizeIs(1));
398 EXPECT_THAT(Result.OrphanedNodes,
399 Each(HasPath(Result, ElementsAre(0xDEADBEEF + 4, 0xDEADBEEF + 5,
400 0xDEADBEEF + 6))))
401 << PrintToString(Result);
402 EXPECT_THAT(Result.ConditionalBranchNodes, IsEmpty());
403
404 SearchLengthForConditionalBranch = PrevSearchLengthForConditionalBranch;
405}
406
407TEST_F(BasicGraphBuilderTest, BuildFlowGraphLengthExceededDownwards) {
Mitch Phillipsd9af3832017-10-23 20:54:01 +0000[diff] [blame]408 if (!SuccessfullyInitialised)
409 return;
Mitch Phillips99fa1402017-10-23 20:25:19 +0000[diff] [blame]410 Analysis.parseSectionContents(
411 {
412 0x75, 0x02, // 0: jne 4 [+2]
413 0xff, 0x10, // 2: callq *(%rax)
414 0x90, // 4: nop
415 0x90, // 5: nop
416 0x90, // 6: nop
417 0x90, // 7: nop
418 0x0f, 0x0b, // 8: ud2
419 },
420 0xDEADBEEF);
421 uint64_t PrevSearchLengthForUndef = SearchLengthForUndef;
422 SearchLengthForUndef = 2;
423
424 GraphResult Result = GraphBuilder::buildFlowGraph(Analysis, 0xDEADBEEF + 2);
425 EXPECT_THAT(Result.OrphanedNodes, IsEmpty());
426 EXPECT_THAT(
427 Result.ConditionalBranchNodes,
428 Each(AllOf(
429 Field(&ConditionalBranchNode::CFIProtection, Eq(false)),
430 Field(&ConditionalBranchNode::Address, Eq(0xDEADBEEF)),
431 Field(&ConditionalBranchNode::Target,
432 HasPath(Result, ElementsAre(0xDEADBEEF + 4, 0xDEADBEEF + 5))),
433 Field(&ConditionalBranchNode::Fallthrough,
434 HasPath(Result, ElementsAre(0xDEADBEEF + 2))))))
435 << PrintToString(Result);
436
437 SearchLengthForUndef = PrevSearchLengthForUndef;
438}
439
440// This test ensures when avoiding doing repeated work we still generate the
441// paths correctly. We don't need to recalculate the flow from 0x2 -> 0x3 as it
442// should only need to be generated once.
443TEST_F(BasicGraphBuilderTest, BuildFlowGraphWithRepeatedWork) {
Mitch Phillipsd9af3832017-10-23 20:54:01 +0000[diff] [blame]444 if (!SuccessfullyInitialised)
445 return;
Mitch Phillips99fa1402017-10-23 20:25:19 +0000[diff] [blame]446 Analysis.parseSectionContents(
447 {
448 0x75, 0x05, // 0: jne 7 [+5]
449 0x90, // 2: nop
450 0xff, 0x10, // 3: callq *(%rax)
451 0x75, 0xfb, // 5: jne 2 [-5]
452 0x0f, 0x0b, // 7: ud2
453 },
454 0xDEADBEEF);
455 GraphResult Result = GraphBuilder::buildFlowGraph(Analysis, 0xDEADBEEF + 3);
456 EXPECT_THAT(Result.OrphanedNodes, IsEmpty());
457 EXPECT_THAT(Result.ConditionalBranchNodes, SizeIs(2));
458 EXPECT_THAT(
459 Result.ConditionalBranchNodes,
460 Contains(AllOf(
461 Field(&ConditionalBranchNode::CFIProtection, Eq(true)),
462 Field(&ConditionalBranchNode::Address, Eq(0xDEADBEEF)),
463 Field(&ConditionalBranchNode::Target,
464 HasPath(Result, ElementsAre(0xDEADBEEF + 7))),
465 Field(&ConditionalBranchNode::Fallthrough,
466 HasPath(Result, ElementsAre(0xDEADBEEF + 2, 0xDEADBEEF + 3))))))
467 << PrintToString(Result);
468 EXPECT_THAT(
469 Result.ConditionalBranchNodes,
470 Contains(AllOf(
471 Field(&ConditionalBranchNode::CFIProtection, Eq(true)),
472 Field(&ConditionalBranchNode::Address, Eq(0xDEADBEEF + 5)),
473 Field(&ConditionalBranchNode::Target,
474 HasPath(Result, ElementsAre(0xDEADBEEF + 2, 0xDEADBEEF + 3))),
475 Field(&ConditionalBranchNode::Fallthrough,
476 HasPath(Result, ElementsAre(0xDEADBEEF + 7))))))
477 << PrintToString(Result);
478 EXPECT_THAT(Result.IntermediateNodes, SizeIs(1));
479 EXPECT_THAT(Result.IntermediateNodes,
480 UnorderedElementsAre(Pair(0xDEADBEEF + 2, 0xDEADBEEF + 3)));
481}
482
483TEST_F(BasicGraphBuilderTest, BuildFlowGraphComplexExample) {
Mitch Phillipsd9af3832017-10-23 20:54:01 +0000[diff] [blame]484 if (!SuccessfullyInitialised)
485 return;
Mitch Phillips99fa1402017-10-23 20:25:19 +0000[diff] [blame]486 // The following code has this graph:
487 // +----------+ +--------------+
488 // | 20 | <--- | 0 |
489 // +----------+ +--------------+
490 // | |
491 // v v
492 // +----------+ +--------------+
493 // | 21 | | 2 |
494 // +----------+ +--------------+
495 // | |
496 // v v
497 // +----------+ +--------------+
498 // | 22 (ud2) | +-> | 7 |
499 // +----------+ | +--------------+
500 // ^ | |
501 // | | v
502 // +----------+ | +--------------+
503 // | 4 | | | 8 |
504 // +----------+ | +--------------+
505 // | | |
506 // v | v
507 // +----------+ | +--------------+ +------------+
508 // | 6 | -+ | 9 (indirect) | <- | 13 |
509 // +----------+ +--------------+ +------------+
510 // ^ |
511 // | v
512 // +--------------+ +------------+
513 // | 11 | | 15 (error) |
514 // +--------------+ +------------+
515 // Or, in image format: https://i.imgur.com/aX5fCoi.png
516
517 Analysis.parseSectionContents(
518 {
519 0x75, 0x12, // 0: jne 20 [+18]
520 0xeb, 0x03, // 2: jmp 7 [+3]
521 0x75, 0x10, // 4: jne 22 [+16]
522 0x90, // 6: nop
523 0x90, // 7: nop
524 0x90, // 8: nop
525 0xff, 0x10, // 9: callq *(%rax)
526 0xeb, 0xfc, // 11: jmp 9 [-4]
527 0x75, 0xfa, // 13: jne 9 [-6]
528 0xe8, 0x78, 0x56, 0x34, 0x12, // 15: callq OUTOFBOUNDS [+0x12345678]
529 0x90, // 20: nop
530 0x90, // 21: nop
531 0x0f, 0x0b, // 22: ud2
532 },
533 0x1000);
534 uint64_t PrevSearchLengthForUndef = SearchLengthForUndef;
535 SearchLengthForUndef = 5;
536
537 GraphResult Result = GraphBuilder::buildFlowGraph(Analysis, 0x1000 + 9);
538
539 EXPECT_THAT(Result.OrphanedNodes, SizeIs(1));
540 EXPECT_THAT(Result.ConditionalBranchNodes, SizeIs(3));
541
542 EXPECT_THAT(
543 Result.OrphanedNodes,
544 Each(AllOf(Eq(0x1000u + 11),
545 HasPath(Result, ElementsAre(0x1000 + 11, 0x1000 + 9)))))
546 << PrintToString(Result);
547
548 EXPECT_THAT(Result.ConditionalBranchNodes,
549 Contains(AllOf(
550 Field(&ConditionalBranchNode::CFIProtection, Eq(true)),
551 Field(&ConditionalBranchNode::Address, Eq(0x1000u)),
552 Field(&ConditionalBranchNode::Target,
553 HasPath(Result, ElementsAre(0x1000 + 20, 0x1000 + 21,
554 0x1000 + 22))),
555 Field(&ConditionalBranchNode::Fallthrough,
556 HasPath(Result, ElementsAre(0x1000 + 2, 0x1000 + 7,
557 0x1000 + 8, 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 + 4)),
564 Field(&ConditionalBranchNode::Target,
565 HasPath(Result, ElementsAre(0x1000 + 22))),
566 Field(&ConditionalBranchNode::Fallthrough,
567 HasPath(Result, ElementsAre(0x1000 + 6, 0x1000 + 7,
568 0x1000 + 8, 0x1000 + 9))))))
569 << PrintToString(Result);
570
571 EXPECT_THAT(
572 Result.ConditionalBranchNodes,
573 Contains(AllOf(Field(&ConditionalBranchNode::CFIProtection, Eq(false)),
574 Field(&ConditionalBranchNode::Address, Eq(0x1000u + 13)),
575 Field(&ConditionalBranchNode::Target,
576 HasPath(Result, ElementsAre(0x1000 + 9))),
577 Field(&ConditionalBranchNode::Fallthrough,
578 HasPath(Result, ElementsAre(0x1000 + 15))))))
579 << PrintToString(Result);
580
581 SearchLengthForUndef = PrevSearchLengthForUndef;
582}
583
584} // anonymous namespace
585} // end namespace cfi_verify
586} // end namespace llvm