1 //===- GraphBuilder.cpp -----------------------------------------*- C++ -*-===//
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 "GraphBuilder.h"
10 
11 #include "llvm/BinaryFormat/ELF.h"
12 #include "llvm/MC/MCAsmInfo.h"
13 #include "llvm/MC/MCContext.h"
14 #include "llvm/MC/MCDisassembler/MCDisassembler.h"
15 #include "llvm/MC/MCInst.h"
16 #include "llvm/MC/MCInstPrinter.h"
17 #include "llvm/MC/MCInstrAnalysis.h"
18 #include "llvm/MC/MCInstrDesc.h"
19 #include "llvm/MC/MCInstrInfo.h"
20 #include "llvm/MC/MCObjectFileInfo.h"
21 #include "llvm/MC/MCRegisterInfo.h"
22 #include "llvm/MC/MCSubtargetInfo.h"
23 #include "llvm/Object/Binary.h"
24 #include "llvm/Object/COFF.h"
25 #include "llvm/Object/ELFObjectFile.h"
26 #include "llvm/Object/ObjectFile.h"
27 #include "llvm/Support/Casting.h"
28 #include "llvm/Support/CommandLine.h"
29 #include "llvm/Support/Error.h"
30 #include "llvm/Support/MemoryBuffer.h"
31 #include "llvm/Support/TargetRegistry.h"
32 #include "llvm/Support/TargetSelect.h"
33 #include "llvm/Support/raw_ostream.h"
34 
35 
36 using Instr = llvm::cfi_verify::FileAnalysis::Instr;
37 
38 namespace llvm {
39 namespace cfi_verify {
40 
41 uint64_t SearchLengthForUndef;
42 uint64_t SearchLengthForConditionalBranch;
43 
44 static cl::opt<uint64_t, true> SearchLengthForUndefArg(
45     "search-length-undef",
46     cl::desc("Specify the maximum amount of instructions "
47              "to inspect when searching for an undefined "
48              "instruction from a conditional branch."),
49     cl::location(SearchLengthForUndef), cl::init(2));
50 
51 static cl::opt<uint64_t, true> SearchLengthForConditionalBranchArg(
52     "search-length-cb",
53     cl::desc("Specify the maximum amount of instructions "
54              "to inspect when searching for a conditional "
55              "branch from an indirect control flow."),
56     cl::location(SearchLengthForConditionalBranch), cl::init(20));
57 
flattenAddress(uint64_t Address) const58 std::vector<uint64_t> GraphResult::flattenAddress(uint64_t Address) const {
59   std::vector<uint64_t> Addresses;
60 
61   auto It = IntermediateNodes.find(Address);
62   Addresses.push_back(Address);
63 
64   while (It != IntermediateNodes.end()) {
65     Addresses.push_back(It->second);
66     It = IntermediateNodes.find(It->second);
67   }
68   return Addresses;
69 }
70 
printPairToDOT(const FileAnalysis & Analysis,raw_ostream & OS,uint64_t From,uint64_t To)71 void printPairToDOT(const FileAnalysis &Analysis, raw_ostream &OS,
72                           uint64_t From, uint64_t To) {
73   OS << "  \"" << format_hex(From, 2) << ": ";
74   Analysis.printInstruction(Analysis.getInstructionOrDie(From), OS);
75   OS << "\" -> \"" << format_hex(To, 2) << ": ";
76   Analysis.printInstruction(Analysis.getInstructionOrDie(To), OS);
77   OS << "\"\n";
78 }
79 
printToDOT(const FileAnalysis & Analysis,raw_ostream & OS) const80 void GraphResult::printToDOT(const FileAnalysis &Analysis,
81                              raw_ostream &OS) const {
82   std::map<uint64_t, uint64_t> SortedIntermediateNodes(
83       IntermediateNodes.begin(), IntermediateNodes.end());
84   OS << "digraph graph_" << format_hex(BaseAddress, 2) << " {\n";
85   for (const auto &KV : SortedIntermediateNodes)
86     printPairToDOT(Analysis, OS, KV.first, KV.second);
87 
88   for (auto &BranchNode : ConditionalBranchNodes) {
89     for (auto &V : {BranchNode.Target, BranchNode.Fallthrough})
90       printPairToDOT(Analysis, OS, BranchNode.Address, V);
91   }
92   OS << "}\n";
93 }
94 
buildFlowGraph(const FileAnalysis & Analysis,object::SectionedAddress Address)95 GraphResult GraphBuilder::buildFlowGraph(const FileAnalysis &Analysis,
96                                          object::SectionedAddress Address) {
97   GraphResult Result;
98   Result.BaseAddress = Address.Address;
99   DenseSet<uint64_t> OpenedNodes;
100 
101   const auto &IndirectInstructions = Analysis.getIndirectInstructions();
102 
103   // check that IndirectInstructions contains specified Address
104   if (IndirectInstructions.find(Address) == IndirectInstructions.end()) {
105     return Result;
106   }
107 
108   buildFlowGraphImpl(Analysis, OpenedNodes, Result, Address.Address, 0);
109   return Result;
110 }
111 
buildFlowsToUndefined(const FileAnalysis & Analysis,GraphResult & Result,ConditionalBranchNode & BranchNode,const Instr & BranchInstrMeta)112 void GraphBuilder::buildFlowsToUndefined(const FileAnalysis &Analysis,
113                                          GraphResult &Result,
114                                          ConditionalBranchNode &BranchNode,
115                                          const Instr &BranchInstrMeta) {
116   assert(SearchLengthForUndef > 0 &&
117          "Search length for undefined flow must be greater than zero.");
118 
119   // Start setting up the next node in the block.
120   uint64_t NextAddress = 0;
121   const Instr *NextMetaPtr;
122 
123   // Find out the next instruction in the block and add it to the new
124   // node.
125   if (BranchNode.Target && !BranchNode.Fallthrough) {
126     // We know the target of the branch, find the fallthrough.
127     NextMetaPtr = Analysis.getNextInstructionSequential(BranchInstrMeta);
128     if (!NextMetaPtr) {
129       errs() << "Failed to get next instruction from "
130              << format_hex(BranchNode.Address, 2) << ".\n";
131       return;
132     }
133 
134     NextAddress = NextMetaPtr->VMAddress;
135     BranchNode.Fallthrough =
136         NextMetaPtr->VMAddress; // Add the new node to the branch head.
137   } else if (BranchNode.Fallthrough && !BranchNode.Target) {
138     // We already know the fallthrough, evaluate the target.
139     uint64_t Target;
140     if (!Analysis.getMCInstrAnalysis()->evaluateBranch(
141             BranchInstrMeta.Instruction, BranchInstrMeta.VMAddress,
142             BranchInstrMeta.InstructionSize, Target)) {
143       errs() << "Failed to get branch target for conditional branch at address "
144              << format_hex(BranchInstrMeta.VMAddress, 2) << ".\n";
145       return;
146     }
147 
148     // Resolve the meta pointer for the target of this branch.
149     NextMetaPtr = Analysis.getInstruction(Target);
150     if (!NextMetaPtr) {
151       errs() << "Failed to find instruction at address "
152              << format_hex(Target, 2) << ".\n";
153       return;
154     }
155 
156     NextAddress = Target;
157     BranchNode.Target =
158         NextMetaPtr->VMAddress; // Add the new node to the branch head.
159   } else {
160     errs() << "ControlBranchNode supplied to buildFlowsToUndefined should "
161               "provide Target xor Fallthrough.\n";
162     return;
163   }
164 
165   uint64_t CurrentAddress = NextAddress;
166   const Instr *CurrentMetaPtr = NextMetaPtr;
167 
168   // Now the branch head has been set properly, complete the rest of the block.
169   for (uint64_t i = 1; i < SearchLengthForUndef; ++i) {
170     // Check to see whether the block should die.
171     if (Analysis.isCFITrap(*CurrentMetaPtr)) {
172       BranchNode.CFIProtection = true;
173       return;
174     }
175 
176     // Find the metadata of the next instruction.
177     NextMetaPtr = Analysis.getDefiniteNextInstruction(*CurrentMetaPtr);
178     if (!NextMetaPtr)
179       return;
180 
181     // Setup the next node.
182     NextAddress = NextMetaPtr->VMAddress;
183 
184     // Add this as an intermediate.
185     Result.IntermediateNodes[CurrentAddress] = NextAddress;
186 
187     // Move the 'current' pointers to the new tail of the block.
188     CurrentMetaPtr = NextMetaPtr;
189     CurrentAddress = NextAddress;
190   }
191 
192   // Final check of the last thing we added to the block.
193   if (Analysis.isCFITrap(*CurrentMetaPtr))
194     BranchNode.CFIProtection = true;
195 }
196 
buildFlowGraphImpl(const FileAnalysis & Analysis,DenseSet<uint64_t> & OpenedNodes,GraphResult & Result,uint64_t Address,uint64_t Depth)197 void GraphBuilder::buildFlowGraphImpl(const FileAnalysis &Analysis,
198                                       DenseSet<uint64_t> &OpenedNodes,
199                                       GraphResult &Result, uint64_t Address,
200                                       uint64_t Depth) {
201   // If we've exceeded the flow length, terminate.
202   if (Depth >= SearchLengthForConditionalBranch) {
203     Result.OrphanedNodes.push_back(Address);
204     return;
205   }
206 
207   // Ensure this flow is acyclic.
208   if (OpenedNodes.count(Address))
209     Result.OrphanedNodes.push_back(Address);
210 
211   // If this flow is already explored, stop here.
212   if (Result.IntermediateNodes.count(Address))
213     return;
214 
215   // Get the metadata for the node instruction.
216   const auto &InstrMetaPtr = Analysis.getInstruction(Address);
217   if (!InstrMetaPtr) {
218     errs() << "Failed to build flow graph for instruction at address "
219            << format_hex(Address, 2) << ".\n";
220     Result.OrphanedNodes.push_back(Address);
221     return;
222   }
223   const auto &ChildMeta = *InstrMetaPtr;
224 
225   OpenedNodes.insert(Address);
226   std::set<const Instr *> CFCrossRefs =
227       Analysis.getDirectControlFlowXRefs(ChildMeta);
228 
229   bool HasValidCrossRef = false;
230 
231   for (const auto *ParentMetaPtr : CFCrossRefs) {
232     assert(ParentMetaPtr && "CFCrossRefs returned nullptr.");
233     const auto &ParentMeta = *ParentMetaPtr;
234     const auto &ParentDesc =
235         Analysis.getMCInstrInfo()->get(ParentMeta.Instruction.getOpcode());
236 
237     if (!ParentDesc.mayAffectControlFlow(ParentMeta.Instruction,
238                                          *Analysis.getRegisterInfo())) {
239       // If this cross reference doesn't affect CF, continue the graph.
240       buildFlowGraphImpl(Analysis, OpenedNodes, Result, ParentMeta.VMAddress,
241                          Depth + 1);
242       Result.IntermediateNodes[ParentMeta.VMAddress] = Address;
243       HasValidCrossRef = true;
244       continue;
245     }
246 
247     // Call instructions are not valid in the upwards traversal.
248     if (ParentDesc.isCall()) {
249       Result.IntermediateNodes[ParentMeta.VMAddress] = Address;
250       Result.OrphanedNodes.push_back(ParentMeta.VMAddress);
251       continue;
252     }
253 
254     // Evaluate the branch target to ascertain whether this XRef is the result
255     // of a fallthrough or the target of a branch.
256     uint64_t BranchTarget;
257     if (!Analysis.getMCInstrAnalysis()->evaluateBranch(
258             ParentMeta.Instruction, ParentMeta.VMAddress,
259             ParentMeta.InstructionSize, BranchTarget)) {
260       errs() << "Failed to evaluate branch target for instruction at address "
261              << format_hex(ParentMeta.VMAddress, 2) << ".\n";
262       Result.IntermediateNodes[ParentMeta.VMAddress] = Address;
263       Result.OrphanedNodes.push_back(ParentMeta.VMAddress);
264       continue;
265     }
266 
267     // Allow unconditional branches to be part of the upwards traversal.
268     if (ParentDesc.isUnconditionalBranch()) {
269       // Ensures that the unconditional branch is actually an XRef to the child.
270       if (BranchTarget != Address) {
271         errs() << "Control flow to " << format_hex(Address, 2)
272                << ", but target resolution of "
273                << format_hex(ParentMeta.VMAddress, 2)
274                << " is not this address?\n";
275         Result.IntermediateNodes[ParentMeta.VMAddress] = Address;
276         Result.OrphanedNodes.push_back(ParentMeta.VMAddress);
277         continue;
278       }
279 
280       buildFlowGraphImpl(Analysis, OpenedNodes, Result, ParentMeta.VMAddress,
281                          Depth + 1);
282       Result.IntermediateNodes[ParentMeta.VMAddress] = Address;
283       HasValidCrossRef = true;
284       continue;
285     }
286 
287     // Ensure that any unknown CFs are caught.
288     if (!ParentDesc.isConditionalBranch()) {
289       errs() << "Unknown control flow encountered when building graph at "
290              << format_hex(Address, 2) << "\n.";
291       Result.IntermediateNodes[ParentMeta.VMAddress] = Address;
292       Result.OrphanedNodes.push_back(ParentMeta.VMAddress);
293       continue;
294     }
295 
296     // Only direct conditional branches should be present at this point. Setup
297     // a conditional branch node and build flows to the ud2.
298     ConditionalBranchNode BranchNode;
299     BranchNode.Address = ParentMeta.VMAddress;
300     BranchNode.Target = 0;
301     BranchNode.Fallthrough = 0;
302     BranchNode.CFIProtection = false;
303     BranchNode.IndirectCFIsOnTargetPath = (BranchTarget == Address);
304 
305     if (BranchTarget == Address)
306       BranchNode.Target = Address;
307     else
308       BranchNode.Fallthrough = Address;
309 
310     HasValidCrossRef = true;
311     buildFlowsToUndefined(Analysis, Result, BranchNode, ParentMeta);
312     Result.ConditionalBranchNodes.push_back(BranchNode);
313   }
314 
315   // When using cross-DSO, some indirect calls are not guarded by a branch to a
316   // trap but instead follow a call to __cfi_slowpath.  For example:
317   // if (!InlinedFastCheck(f))
318   //    call *f
319   //  else {
320   //    __cfi_slowpath(CallSiteTypeId, f);
321   //    call *f
322   //  }
323   // To mark the second call as protected, we recognize indirect calls that
324   // directly follow calls to functions that will trap on CFI violations.
325   if (CFCrossRefs.empty()) {
326     const Instr *PrevInstr = Analysis.getPrevInstructionSequential(ChildMeta);
327     if (PrevInstr && Analysis.willTrapOnCFIViolation(*PrevInstr)) {
328       Result.IntermediateNodes[PrevInstr->VMAddress] = Address;
329       HasValidCrossRef = true;
330     }
331   }
332 
333   if (!HasValidCrossRef)
334     Result.OrphanedNodes.push_back(Address);
335 
336   OpenedNodes.erase(Address);
337 }
338 
339 } // namespace cfi_verify
340 } // namespace llvm
341