134 lines · c
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-exception6//7//===----------------------------------------------------------------------===//8 9#ifndef LLVM_CFI_VERIFY_GRAPH_BUILDER_H10#define LLVM_CFI_VERIFY_GRAPH_BUILDER_H11 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 41using Instr = llvm::cfi_verify::FileAnalysis::Instr;42 43namespace llvm {44namespace cfi_verify {45 46extern uint64_t SearchLengthForUndef;47extern uint64_t SearchLengthForConditionalBranch;48 49struct ConditionalBranchNode {50 uint64_t Address;51 uint64_t Target;52 uint64_t Fallthrough;53 // Does this conditional branch look like it's used for CFI protection? i.e.54 // - The exit point of a basic block whos entry point is {target|fallthrough}55 // is a CFI trap, and...56 // - The exit point of the other basic block is an undirect CF instruction.57 bool CFIProtection;58 bool IndirectCFIsOnTargetPath;59};60 61// The canonical graph result structure returned by GraphBuilder. The members62// in this structure encapsulate all possible code paths to the instruction63// located at `BaseAddress`.64struct GraphResult {65 uint64_t BaseAddress;66 67 // Map between an instruction address, and the address of the next instruction68 // that will be executed. This map will contain all keys in the range:69 // - [orphaned node, base address)70 // - [conditional branch node {target|fallthrough}, base address)71 DenseMap<uint64_t, uint64_t> IntermediateNodes;72 73 // A list of orphaned nodes. A node is an 'orphan' if it meets any of the74 // following criteria:75 // - The length of the path from the base to this node has exceeded76 // `SearchLengthForConditionalBranch`.77 // - The node has no cross references to it.78 // - The path from the base to this node is cyclic.79 std::vector<uint64_t> OrphanedNodes;80 81 // A list of top-level conditional branches that exist at the top of any82 // non-orphan paths from the base.83 std::vector<ConditionalBranchNode> ConditionalBranchNodes;84 85 // Returns an in-order list of the path between the address provided and the86 // base. The provided address must be part of this graph, and must not be a87 // conditional branch.88 std::vector<uint64_t> flattenAddress(uint64_t Address) const;89 90 // Print the DOT representation of this result.91 void printToDOT(const FileAnalysis &Analysis, raw_ostream &OS) const;92};93 94class GraphBuilder {95public:96 // Build the control flow graph for a provided control flow node. This method97 // will enumerate all branch nodes that can lead to this node, and place them98 // into GraphResult::ConditionalBranchNodes. It will also provide any orphaned99 // (i.e. the upwards traversal did not make it to a branch node) flows to the100 // provided node in GraphResult::OrphanedNodes.101 static GraphResult buildFlowGraph(const FileAnalysis &Analysis,102 object::SectionedAddress Address);103 104private:105 // Implementation function that actually builds the flow graph. Retrieves a106 // list of cross references to instruction referenced in `Address`. If any of107 // these XRefs are conditional branches, it will build the other potential108 // path (fallthrough or target) using `buildFlowsToUndefined`. Otherwise, this109 // function will recursively call itself where `Address` in the recursive call110 // is now the XRef. If any XRef is an orphan, it is added to111 // `Result.OrphanedNodes`. `OpenedNodes` keeps track of the list of nodes112 // in the current path and is used for cycle-checking. If the path is found113 // to be cyclic, it will be added to `Result.OrphanedNodes`.114 static void buildFlowGraphImpl(const FileAnalysis &Analysis,115 DenseSet<uint64_t> &OpenedNodes,116 GraphResult &Result, uint64_t Address,117 uint64_t Depth);118 119 // Utilised by buildFlowGraphImpl to build the tree out from the provided120 // conditional branch node to an undefined instruction. The provided121 // conditional branch node must have exactly one of its subtrees set, and will122 // update the node's CFIProtection field if a deterministic flow can be found123 // to an undefined instruction.124 static void buildFlowsToUndefined(const FileAnalysis &Analysis,125 GraphResult &Result,126 ConditionalBranchNode &BranchNode,127 const Instr &BranchInstrMeta);128};129 130} // end namespace cfi_verify131} // end namespace llvm132 133#endif // LLVM_CFI_VERIFY_GRAPH_BUILDER_H134