tools/llvm-cfi-verify/lib/GraphBuilder.h

   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