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