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