|
121
|
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
|
|
|
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.
|
|
|
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
|
|
|
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
|
|
|
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:
|
|
|
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
|
|
|
126 class BasicGraphBuilderTest : public ::testing::Test {
|
|
|
127 protected:
|
|
|
128 virtual void SetUp() {
|
|
|
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
|
|
|
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);
|
|
|
160 const auto Result = GraphBuilder::buildFlowGraph(Analysis, 0xDEADBEEF + 4);
|
|
|
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 return;
|
|
|
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);
|
|
|
186 const auto Result = GraphBuilder::buildFlowGraph(Analysis, 0xDEADBEEF + 2);
|
|
|
187
|
|
|
188 EXPECT_THAT(Result.OrphanedNodes, IsEmpty());
|
|
|
189 EXPECT_THAT(Result.ConditionalBranchNodes, SizeIs(1));
|
|
|
190 EXPECT_THAT(Result.ConditionalBranchNodes,
|
|
|
191 Each(Field(&ConditionalBranchNode::CFIProtection, Eq(true))));
|
|
|
192 EXPECT_THAT(
|
|
|
193 Result.ConditionalBranchNodes,
|
|
|
194 Contains(AllOf(Field(&ConditionalBranchNode::Address, Eq(0xDEADBEEF)),
|
|
|
195 Field(&ConditionalBranchNode::Target,
|
|
|
196 HasPath(Result, ElementsAre(0xDEADBEEF + 4))),
|
|
|
197 Field(&ConditionalBranchNode::Fallthrough,
|
|
|
198 HasPath(Result, ElementsAre(0xDEADBEEF + 2))))))
|
|
|
199 << PrintToString(Result);
|
|
|
200 }
|
|
|
201
|
|
|
202 TEST_F(BasicGraphBuilderTest, BuildFlowGraphTestDualPathDualUd2) {
|
|
|
203 if (!SuccessfullyInitialised)
|
|
|
204 return;
|
|
|
205 Analysis.parseSectionContents(
|
|
|
206 {
|
|
|
207 0x75, 0x03, // 0: jne 5 [+3]
|
|
|
208 0x90, // 2: nop
|
|
|
209 0xff, 0x10, // 3: callq *(%rax)
|
|
|
210 0x0f, 0x0b, // 5: ud2
|
|
|
211 0x75, 0xf9, // 7: jne 2 [-7]
|
|
|
212 0x0f, 0x0b, // 9: ud2
|
|
|
213 },
|
|
|
214 0xDEADBEEF);
|
|
|
215 const auto Result = GraphBuilder::buildFlowGraph(Analysis, 0xDEADBEEF + 3);
|
|
|
216
|
|
|
217 EXPECT_THAT(Result.OrphanedNodes, IsEmpty());
|
|
|
218 EXPECT_THAT(Result.ConditionalBranchNodes, SizeIs(2));
|
|
|
219 EXPECT_THAT(Result.ConditionalBranchNodes,
|
|
|
220 Each(Field(&ConditionalBranchNode::CFIProtection, Eq(true))));
|
|
|
221 EXPECT_THAT(
|
|
|
222 Result.ConditionalBranchNodes,
|
|
|
223 Contains(AllOf(
|
|
|
224 Field(&ConditionalBranchNode::Address, Eq(0xDEADBEEF)),
|
|
|
225 Field(&ConditionalBranchNode::Fallthrough,
|
|
|
226 HasPath(Result, ElementsAre(0xDEADBEEF + 2, 0xDEADBEEF + 3))),
|
|
|
227 Field(&ConditionalBranchNode::Target,
|
|
|
228 HasPath(Result, ElementsAre(0xDEADBEEF + 5))))))
|
|
|
229 << PrintToString(Result);
|
|
|
230 EXPECT_THAT(
|
|
|
231 Result.ConditionalBranchNodes,
|
|
|
232 Contains(AllOf(
|
|
|
233 Field(&ConditionalBranchNode::Address, Eq(0xDEADBEEF + 7)),
|
|
|
234 Field(&ConditionalBranchNode::Fallthrough,
|
|
|
235 HasPath(Result, ElementsAre(0xDEADBEEF + 9))),
|
|
|
236 Field(&ConditionalBranchNode::Target,
|
|
|
237 HasPath(Result, ElementsAre(0xDEADBEEF + 2, 0xDEADBEEF + 3))))))
|
|
|
238 << PrintToString(Result);
|
|
|
239 }
|
|
|
240
|
|
|
241 TEST_F(BasicGraphBuilderTest, BuildFlowGraphTestDualPathSingleUd2) {
|
|
|
242 if (!SuccessfullyInitialised)
|
|
|
243 return;
|
|
|
244 Analysis.parseSectionContents(
|
|
|
245 {
|
|
|
246 0x75, 0x05, // 0: jne 7 [+5]
|
|
|
247 0x90, // 2: nop
|
|
|
248 0xff, 0x10, // 3: callq *(%rax)
|
|
|
249 0x75, 0xfb, // 5: jne 2 [-5]
|
|
|
250 0x0f, 0x0b, // 7: ud2
|
|
|
251 },
|
|
|
252 0xDEADBEEF);
|
|
|
253 GraphResult Result = GraphBuilder::buildFlowGraph(Analysis, 0xDEADBEEF + 3);
|
|
|
254
|
|
|
255 EXPECT_THAT(Result.OrphanedNodes, IsEmpty());
|
|
|
256 EXPECT_THAT(Result.ConditionalBranchNodes, SizeIs(2));
|
|
|
257 EXPECT_THAT(Result.ConditionalBranchNodes,
|
|
|
258 Each(Field(&ConditionalBranchNode::CFIProtection, Eq(true))));
|
|
|
259 EXPECT_THAT(
|
|
|
260 Result.ConditionalBranchNodes,
|
|
|
261 Contains(AllOf(
|
|
|
262 Field(&ConditionalBranchNode::Address, Eq(0xDEADBEEF)),
|
|
|
263 Field(&ConditionalBranchNode::Fallthrough,
|
|
|
264 HasPath(Result, ElementsAre(0xDEADBEEF + 2, 0xDEADBEEF + 3))),
|
|
|
265 Field(&ConditionalBranchNode::Target,
|
|
|
266 HasPath(Result, ElementsAre(0xDEADBEEF + 7))))))
|
|
|
267 << PrintToString(Result);
|
|
|
268 EXPECT_THAT(
|
|
|
269 Result.ConditionalBranchNodes,
|
|
|
270 Contains(AllOf(
|
|
|
271 Field(&ConditionalBranchNode::Address, Eq(0xDEADBEEF + 5)),
|
|
|
272 Field(&ConditionalBranchNode::Fallthrough,
|
|
|
273 HasPath(Result, ElementsAre(0xDEADBEEF + 7))),
|
|
|
274 Field(&ConditionalBranchNode::Target,
|
|
|
275 HasPath(Result, ElementsAre(0xDEADBEEF + 2, 0xDEADBEEF + 3))))))
|
|
|
276 << PrintToString(Result);
|
|
|
277 }
|
|
|
278
|
|
|
279 TEST_F(BasicGraphBuilderTest, BuildFlowGraphFailures) {
|
|
|
280 if (!SuccessfullyInitialised)
|
|
|
281 return;
|
|
|
282 Analysis.parseSectionContents(
|
|
|
283 {
|
|
|
284 0x90, // 0: nop
|
|
|
285 0x75, 0xfe, // 1: jne 1 [-2]
|
|
|
286 },
|
|
|
287 0xDEADBEEF);
|
|
|
288 GraphResult Result = GraphBuilder::buildFlowGraph(Analysis, 0xDEADBEEF);
|
|
|
289 EXPECT_THAT(Result.OrphanedNodes, IsEmpty());
|
|
|
290 EXPECT_THAT(Result.ConditionalBranchNodes, IsEmpty());
|
|
|
291
|
|
|
292 Result = GraphBuilder::buildFlowGraph(Analysis, 0xDEADBEEF + 1);
|
|
|
293 EXPECT_THAT(Result.OrphanedNodes, IsEmpty());
|
|
|
294 EXPECT_THAT(Result.ConditionalBranchNodes, IsEmpty());
|
|
|
295
|
|
|
296 Result = GraphBuilder::buildFlowGraph(Analysis, 0xDEADC0DE);
|
|
|
297 EXPECT_THAT(Result.OrphanedNodes, IsEmpty());
|
|
|
298 EXPECT_THAT(Result.ConditionalBranchNodes, IsEmpty());
|
|
|
299 }
|
|
|
300
|
|
|
301 TEST_F(BasicGraphBuilderTest, BuildFlowGraphNoXrefs) {
|
|
|
302 if (!SuccessfullyInitialised)
|
|
|
303 return;
|
|
|
304 Analysis.parseSectionContents(
|
|
|
305 {
|
|
|
306 0xeb, 0xfe, // 0: jmp 0 [-2]
|
|
|
307 0xff, 0x10, // 2: callq *(%rax)
|
|
|
308 },
|
|
|
309 0xDEADBEEF);
|
|
|
310 GraphResult Result = GraphBuilder::buildFlowGraph(Analysis, 0xDEADBEEF + 2);
|
|
|
311 EXPECT_THAT(Result.ConditionalBranchNodes, IsEmpty());
|
|
|
312 EXPECT_THAT(Result.OrphanedNodes, ElementsAre(0xDEADBEEF + 2));
|
|
|
313 EXPECT_THAT(Result.IntermediateNodes, IsEmpty());
|
|
|
314 }
|
|
|
315
|
|
|
316 TEST_F(BasicGraphBuilderTest, BuildFlowGraphConditionalInfiniteLoop) {
|
|
|
317 if (!SuccessfullyInitialised)
|
|
|
318 return;
|
|
|
319 Analysis.parseSectionContents(
|
|
|
320 {
|
|
|
321 0x75, 0xfe, // 0: jne 0 [-2]
|
|
|
322 0xff, 0x10, // 2: callq *(%rax)
|
|
|
323 },
|
|
|
324 0xDEADBEEF);
|
|
|
325 GraphResult Result = GraphBuilder::buildFlowGraph(Analysis, 0xDEADBEEF + 2);
|
|
|
326 EXPECT_THAT(Result.OrphanedNodes, IsEmpty());
|
|
|
327 EXPECT_THAT(Result.ConditionalBranchNodes, SizeIs(1));
|
|
|
328 EXPECT_THAT(
|
|
|
329 Result.ConditionalBranchNodes,
|
|
|
330 Each(AllOf(Field(&ConditionalBranchNode::CFIProtection, Eq(false)),
|
|
|
331 Field(&ConditionalBranchNode::Target,
|
|
|
332 HasPath(Result, ElementsAre(0xDEADBEEF))),
|
|
|
333 Field(&ConditionalBranchNode::Fallthrough,
|
|
|
334 HasPath(Result, ElementsAre(0xDEADBEEF + 2))))))
|
|
|
335 << PrintToString(Result);
|
|
|
336 }
|
|
|
337
|
|
|
338 TEST_F(BasicGraphBuilderTest, BuildFlowGraphUnconditionalInfiniteLoop) {
|
|
|
339 if (!SuccessfullyInitialised)
|
|
|
340 return;
|
|
|
341 Analysis.parseSectionContents(
|
|
|
342 {
|
|
|
343 0x75, 0x02, // 0: jne 4 [+2]
|
|
|
344 0xeb, 0xfc, // 2: jmp 0 [-4]
|
|
|
345 0xff, 0x10, // 4: callq *(%rax)
|
|
|
346 },
|
|
|
347 0xDEADBEEF);
|
|
|
348 GraphResult Result = GraphBuilder::buildFlowGraph(Analysis, 0xDEADBEEF + 4);
|
|
|
349 EXPECT_THAT(Result.OrphanedNodes, IsEmpty());
|
|
|
350 EXPECT_THAT(Result.ConditionalBranchNodes, SizeIs(1));
|
|
|
351 EXPECT_THAT(
|
|
|
352 Result.ConditionalBranchNodes,
|
|
|
353 Contains(
|
|
|
354 AllOf(Field(&ConditionalBranchNode::Address, Eq(0xDEADBEEF)),
|
|
|
355 Field(&ConditionalBranchNode::Fallthrough,
|
|
|
356 HasPath(Result, ElementsAre(0xDEADBEEF + 2, 0xDEADBEEF))),
|
|
|
357 Field(&ConditionalBranchNode::Target,
|
|
|
358 HasPath(Result, ElementsAre(0xDEADBEEF + 4))))))
|
|
|
359 << PrintToString(Result);
|
|
|
360 }
|
|
|
361
|
|
|
362 TEST_F(BasicGraphBuilderTest, BuildFlowGraphNoFlowsToIndirection) {
|
|
|
363 if (!SuccessfullyInitialised)
|
|
|
364 return;
|
|
|
365 Analysis.parseSectionContents(
|
|
|
366 {
|
|
|
367 0x75, 0x00, // 0: jne 2 [+0]
|
|
|
368 0xeb, 0xfc, // 2: jmp 0 [-4]
|
|
|
369 0xff, 0x10, // 4: callq *(%rax)
|
|
|
370 },
|
|
|
371 0xDEADBEEF);
|
|
|
372 GraphResult Result = GraphBuilder::buildFlowGraph(Analysis, 0xDEADBEEF + 4);
|
|
|
373 EXPECT_THAT(Result.OrphanedNodes, ElementsAre(0xDEADBEEF + 4));
|
|
|
374 EXPECT_THAT(Result.ConditionalBranchNodes, IsEmpty());
|
|
|
375 }
|
|
|
376
|
|
|
377 TEST_F(BasicGraphBuilderTest, BuildFlowGraphLengthExceededUpwards) {
|
|
|
378 if (!SuccessfullyInitialised)
|
|
|
379 return;
|
|
|
380 Analysis.parseSectionContents(
|
|
|
381 {
|
|
|
382 0x75, 0x06, // 0: jne 8 [+6]
|
|
|
383 0x90, // 2: nop
|
|
|
384 0x90, // 3: nop
|
|
|
385 0x90, // 4: nop
|
|
|
386 0x90, // 5: nop
|
|
|
387 0xff, 0x10, // 6: callq *(%rax)
|
|
|
388 0x0f, 0x0b, // 8: ud2
|
|
|
389 },
|
|
|
390 0xDEADBEEF);
|
|
|
391 uint64_t PrevSearchLengthForConditionalBranch =
|
|
|
392 SearchLengthForConditionalBranch;
|
|
|
393 SearchLengthForConditionalBranch = 2;
|
|
|
394
|
|
|
395 GraphResult Result = GraphBuilder::buildFlowGraph(Analysis, 0xDEADBEEF + 6);
|
|
|
396 EXPECT_THAT(Result.OrphanedNodes, SizeIs(1));
|
|
|
397 EXPECT_THAT(Result.OrphanedNodes,
|
|
|
398 Each(HasPath(Result, ElementsAre(0xDEADBEEF + 4, 0xDEADBEEF + 5,
|
|
|
399 0xDEADBEEF + 6))))
|
|
|
400 << PrintToString(Result);
|
|
|
401 EXPECT_THAT(Result.ConditionalBranchNodes, IsEmpty());
|
|
|
402
|
|
|
403 SearchLengthForConditionalBranch = PrevSearchLengthForConditionalBranch;
|
|
|
404 }
|
|
|
405
|
|
|
406 TEST_F(BasicGraphBuilderTest, BuildFlowGraphLengthExceededDownwards) {
|
|
|
407 if (!SuccessfullyInitialised)
|
|
|
408 return;
|
|
|
409 Analysis.parseSectionContents(
|
|
|
410 {
|
|
|
411 0x75, 0x02, // 0: jne 4 [+2]
|
|
|
412 0xff, 0x10, // 2: callq *(%rax)
|
|
|
413 0x90, // 4: nop
|
|
|
414 0x90, // 5: nop
|
|
|
415 0x90, // 6: nop
|
|
|
416 0x90, // 7: nop
|
|
|
417 0x0f, 0x0b, // 8: ud2
|
|
|
418 },
|
|
|
419 0xDEADBEEF);
|
|
|
420 uint64_t PrevSearchLengthForUndef = SearchLengthForUndef;
|
|
|
421 SearchLengthForUndef = 2;
|
|
|
422
|
|
|
423 GraphResult Result = GraphBuilder::buildFlowGraph(Analysis, 0xDEADBEEF + 2);
|
|
|
424 EXPECT_THAT(Result.OrphanedNodes, IsEmpty());
|
|
|
425 EXPECT_THAT(
|
|
|
426 Result.ConditionalBranchNodes,
|
|
|
427 Each(AllOf(
|
|
|
428 Field(&ConditionalBranchNode::CFIProtection, Eq(false)),
|
|
|
429 Field(&ConditionalBranchNode::Address, Eq(0xDEADBEEF)),
|
|
|
430 Field(&ConditionalBranchNode::Target,
|
|
|
431 HasPath(Result, ElementsAre(0xDEADBEEF + 4, 0xDEADBEEF + 5))),
|
|
|
432 Field(&ConditionalBranchNode::Fallthrough,
|
|
|
433 HasPath(Result, ElementsAre(0xDEADBEEF + 2))))))
|
|
|
434 << PrintToString(Result);
|
|
|
435
|
|
|
436 SearchLengthForUndef = PrevSearchLengthForUndef;
|
|
|
437 }
|
|
|
438
|
|
|
439 // This test ensures when avoiding doing repeated work we still generate the
|
|
|
440 // paths correctly. We don't need to recalculate the flow from 0x2 -> 0x3 as it
|
|
|
441 // should only need to be generated once.
|
|
|
442 TEST_F(BasicGraphBuilderTest, BuildFlowGraphWithRepeatedWork) {
|
|
|
443 if (!SuccessfullyInitialised)
|
|
|
444 return;
|
|
|
445 Analysis.parseSectionContents(
|
|
|
446 {
|
|
|
447 0x75, 0x05, // 0: jne 7 [+5]
|
|
|
448 0x90, // 2: nop
|
|
|
449 0xff, 0x10, // 3: callq *(%rax)
|
|
|
450 0x75, 0xfb, // 5: jne 2 [-5]
|
|
|
451 0x0f, 0x0b, // 7: ud2
|
|
|
452 },
|
|
|
453 0xDEADBEEF);
|
|
|
454 GraphResult Result = GraphBuilder::buildFlowGraph(Analysis, 0xDEADBEEF + 3);
|
|
|
455 EXPECT_THAT(Result.OrphanedNodes, IsEmpty());
|
|
|
456 EXPECT_THAT(Result.ConditionalBranchNodes, SizeIs(2));
|
|
|
457 EXPECT_THAT(
|
|
|
458 Result.ConditionalBranchNodes,
|
|
|
459 Contains(AllOf(
|
|
|
460 Field(&ConditionalBranchNode::CFIProtection, Eq(true)),
|
|
|
461 Field(&ConditionalBranchNode::Address, Eq(0xDEADBEEF)),
|
|
|
462 Field(&ConditionalBranchNode::Target,
|
|
|
463 HasPath(Result, ElementsAre(0xDEADBEEF + 7))),
|
|
|
464 Field(&ConditionalBranchNode::Fallthrough,
|
|
|
465 HasPath(Result, ElementsAre(0xDEADBEEF + 2, 0xDEADBEEF + 3))))))
|
|
|
466 << PrintToString(Result);
|
|
|
467 EXPECT_THAT(
|
|
|
468 Result.ConditionalBranchNodes,
|
|
|
469 Contains(AllOf(
|
|
|
470 Field(&ConditionalBranchNode::CFIProtection, Eq(true)),
|
|
|
471 Field(&ConditionalBranchNode::Address, Eq(0xDEADBEEF + 5)),
|
|
|
472 Field(&ConditionalBranchNode::Target,
|
|
|
473 HasPath(Result, ElementsAre(0xDEADBEEF + 2, 0xDEADBEEF + 3))),
|
|
|
474 Field(&ConditionalBranchNode::Fallthrough,
|
|
|
475 HasPath(Result, ElementsAre(0xDEADBEEF + 7))))))
|
|
|
476 << PrintToString(Result);
|
|
|
477 EXPECT_THAT(Result.IntermediateNodes, SizeIs(1));
|
|
|
478 EXPECT_THAT(Result.IntermediateNodes,
|
|
|
479 UnorderedElementsAre(Pair(0xDEADBEEF + 2, 0xDEADBEEF + 3)));
|
|
|
480 }
|
|
|
481
|
|
|
482 TEST_F(BasicGraphBuilderTest, BuildFlowGraphComplexExample) {
|
|
|
483 if (!SuccessfullyInitialised)
|
|
|
484 return;
|
|
|
485 // The following code has this graph:
|
|
|
486 // +----------+ +--------------+
|
|
|
487 // | 20 | <--- | 0 |
|
|
|
488 // +----------+ +--------------+
|
|
|
489 // | |
|
|
|
490 // v v
|
|
|
491 // +----------+ +--------------+
|
|
|
492 // | 21 | | 2 |
|
|
|
493 // +----------+ +--------------+
|
|
|
494 // | |
|
|
|
495 // v v
|
|
|
496 // +----------+ +--------------+
|
|
|
497 // | 22 (ud2) | +-> | 7 |
|
|
|
498 // +----------+ | +--------------+
|
|
|
499 // ^ | |
|
|
|
500 // | | v
|
|
|
501 // +----------+ | +--------------+
|
|
|
502 // | 4 | | | 8 |
|
|
|
503 // +----------+ | +--------------+
|
|
|
504 // | | |
|
|
|
505 // v | v
|
|
|
506 // +----------+ | +--------------+ +------------+
|
|
|
507 // | 6 | -+ | 9 (indirect) | <- | 13 |
|
|
|
508 // +----------+ +--------------+ +------------+
|
|
|
509 // ^ |
|
|
|
510 // | v
|
|
|
511 // +--------------+ +------------+
|
|
|
512 // | 11 | | 15 (error) |
|
|
|
513 // +--------------+ +------------+
|
|
|
514 // Or, in image format: https://i.imgur.com/aX5fCoi.png
|
|
|
515
|
|
|
516 Analysis.parseSectionContents(
|
|
|
517 {
|
|
|
518 0x75, 0x12, // 0: jne 20 [+18]
|
|
|
519 0xeb, 0x03, // 2: jmp 7 [+3]
|
|
|
520 0x75, 0x10, // 4: jne 22 [+16]
|
|
|
521 0x90, // 6: nop
|
|
|
522 0x90, // 7: nop
|
|
|
523 0x90, // 8: nop
|
|
|
524 0xff, 0x10, // 9: callq *(%rax)
|
|
|
525 0xeb, 0xfc, // 11: jmp 9 [-4]
|
|
|
526 0x75, 0xfa, // 13: jne 9 [-6]
|
|
|
527 0xe8, 0x78, 0x56, 0x34, 0x12, // 15: callq OUTOFBOUNDS [+0x12345678]
|
|
|
528 0x90, // 20: nop
|
|
|
529 0x90, // 21: nop
|
|
|
530 0x0f, 0x0b, // 22: ud2
|
|
|
531 },
|
|
|
532 0x1000);
|
|
|
533 uint64_t PrevSearchLengthForUndef = SearchLengthForUndef;
|
|
|
534 SearchLengthForUndef = 5;
|
|
|
535
|
|
|
536 GraphResult Result = GraphBuilder::buildFlowGraph(Analysis, 0x1000 + 9);
|
|
|
537
|
|
|
538 EXPECT_THAT(Result.OrphanedNodes, SizeIs(1));
|
|
|
539 EXPECT_THAT(Result.ConditionalBranchNodes, SizeIs(3));
|
|
|
540
|
|
|
541 EXPECT_THAT(
|
|
|
542 Result.OrphanedNodes,
|
|
|
543 Each(AllOf(Eq(0x1000u + 11),
|
|
|
544 HasPath(Result, ElementsAre(0x1000 + 11, 0x1000 + 9)))))
|
|
|
545 << PrintToString(Result);
|
|
|
546
|
|
|
547 EXPECT_THAT(Result.ConditionalBranchNodes,
|
|
|
548 Contains(AllOf(
|
|
|
549 Field(&ConditionalBranchNode::CFIProtection, Eq(true)),
|
|
|
550 Field(&ConditionalBranchNode::Address, Eq(0x1000u)),
|
|
|
551 Field(&ConditionalBranchNode::Target,
|
|
|
552 HasPath(Result, ElementsAre(0x1000 + 20, 0x1000 + 21,
|
|
|
553 0x1000 + 22))),
|
|
|
554 Field(&ConditionalBranchNode::Fallthrough,
|
|
|
555 HasPath(Result, ElementsAre(0x1000 + 2, 0x1000 + 7,
|
|
|
556 0x1000 + 8, 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 + 4)),
|
|
|
563 Field(&ConditionalBranchNode::Target,
|
|
|
564 HasPath(Result, ElementsAre(0x1000 + 22))),
|
|
|
565 Field(&ConditionalBranchNode::Fallthrough,
|
|
|
566 HasPath(Result, ElementsAre(0x1000 + 6, 0x1000 + 7,
|
|
|
567 0x1000 + 8, 0x1000 + 9))))))
|
|
|
568 << PrintToString(Result);
|
|
|
569
|
|
|
570 EXPECT_THAT(
|
|
|
571 Result.ConditionalBranchNodes,
|
|
|
572 Contains(AllOf(Field(&ConditionalBranchNode::CFIProtection, Eq(false)),
|
|
|
573 Field(&ConditionalBranchNode::Address, Eq(0x1000u + 13)),
|
|
|
574 Field(&ConditionalBranchNode::Target,
|
|
|
575 HasPath(Result, ElementsAre(0x1000 + 9))),
|
|
|
576 Field(&ConditionalBranchNode::Fallthrough,
|
|
|
577 HasPath(Result, ElementsAre(0x1000 + 15))))))
|
|
|
578 << PrintToString(Result);
|
|
|
579
|
|
|
580 SearchLengthForUndef = PrevSearchLengthForUndef;
|
|
|
581 }
|
|
|
582
|
|
|
583 } // anonymous namespace
|
|
|
584 } // end namespace cfi_verify
|
|
|
585 } // end namespace llvm
|
