1 //===- GraphBuilder.h -------------------------------------------*- 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 #ifndef LLVM_CFI_VERIFY_GRAPH_BUILDER_H 10 #define LLVM_CFI_VERIFY_GRAPH_BUILDER_H 11 12 #include "FileAnalysis.h" 13 14 #include "llvm/ADT/DenseMap.h" 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 <functional> 40 #include <set> 41 #include <string> 42 #include <unordered_map> 43 44 using Instr = llvm::cfi_verify::FileAnalysis::Instr; 45 46 namespace llvm { 47 namespace cfi_verify { 48 49 extern uint64_t SearchLengthForUndef; 50 extern uint64_t SearchLengthForConditionalBranch; 51 52 struct ConditionalBranchNode { 53 uint64_t Address; 54 uint64_t Target; 55 uint64_t Fallthrough; 56 // Does this conditional branch look like it's used for CFI protection? i.e. 57 // - The exit point of a basic block whos entry point is {target|fallthrough} 58 // is a CFI trap, and... 59 // - The exit point of the other basic block is an undirect CF instruction. 60 bool CFIProtection; 61 bool IndirectCFIsOnTargetPath; 62 }; 63 64 // The canonical graph result structure returned by GraphBuilder. The members 65 // in this structure encapsulate all possible code paths to the instruction 66 // located at `BaseAddress`. 67 struct GraphResult { 68 uint64_t BaseAddress; 69 70 // Map between an instruction address, and the address of the next instruction 71 // that will be executed. This map will contain all keys in the range: 72 // - [orphaned node, base address) 73 // - [conditional branch node {target|fallthrough}, base address) 74 DenseMap<uint64_t, uint64_t> IntermediateNodes; 75 76 // A list of orphaned nodes. A node is an 'orphan' if it meets any of the 77 // following criteria: 78 // - The length of the path from the base to this node has exceeded 79 // `SearchLengthForConditionalBranch`. 80 // - The node has no cross references to it. 81 // - The path from the base to this node is cyclic. 82 std::vector<uint64_t> OrphanedNodes; 83 84 // A list of top-level conditional branches that exist at the top of any 85 // non-orphan paths from the base. 86 std::vector<ConditionalBranchNode> ConditionalBranchNodes; 87 88 // Returns an in-order list of the path between the address provided and the 89 // base. The provided address must be part of this graph, and must not be a 90 // conditional branch. 91 std::vector<uint64_t> flattenAddress(uint64_t Address) const; 92 93 // Print the DOT representation of this result. 94 void printToDOT(const FileAnalysis &Analysis, raw_ostream &OS) const; 95 }; 96 97 class GraphBuilder { 98 public: 99 // Build the control flow graph for a provided control flow node. This method 100 // will enumerate all branch nodes that can lead to this node, and place them 101 // into GraphResult::ConditionalBranchNodes. It will also provide any orphaned 102 // (i.e. the upwards traversal did not make it to a branch node) flows to the 103 // provided node in GraphResult::OrphanedNodes. 104 static GraphResult buildFlowGraph(const FileAnalysis &Analysis, 105 object::SectionedAddress Address); 106 107 private: 108 // Implementation function that actually builds the flow graph. Retrieves a 109 // list of cross references to instruction referenced in `Address`. If any of 110 // these XRefs are conditional branches, it will build the other potential 111 // path (fallthrough or target) using `buildFlowsToUndefined`. Otherwise, this 112 // function will recursively call itself where `Address` in the recursive call 113 // is now the XRef. If any XRef is an orphan, it is added to 114 // `Result.OrphanedNodes`. `OpenedNodes` keeps track of the list of nodes 115 // in the current path and is used for cycle-checking. If the path is found 116 // to be cyclic, it will be added to `Result.OrphanedNodes`. 117 static void buildFlowGraphImpl(const FileAnalysis &Analysis, 118 DenseSet<uint64_t> &OpenedNodes, 119 GraphResult &Result, uint64_t Address, 120 uint64_t Depth); 121 122 // Utilised by buildFlowGraphImpl to build the tree out from the provided 123 // conditional branch node to an undefined instruction. The provided 124 // conditional branch node must have exactly one of its subtrees set, and will 125 // update the node's CFIProtection field if a deterministic flow can be found 126 // to an undefined instruction. 127 static void buildFlowsToUndefined(const FileAnalysis &Analysis, 128 GraphResult &Result, 129 ConditionalBranchNode &BranchNode, 130 const Instr &BranchInstrMeta); 131 }; 132 133 } // end namespace cfi_verify 134 } // end namespace llvm 135 136 #endif // LLVM_CFI_VERIFY_GRAPH_BUILDER_H 137