[cfi-verify] Add DOT graph printing for GraphResult objects.

[hctim]

Summary

Allows users to view GraphResult objects in a DOT directed-graph format. This feature can be turned on through the --print-graphs flag.

Also enabled pretty-printing of instructions in output. Together these features make analysis of unprotected CF instructions much easier by providing a visual control flow graph.

[hctim]

Minor formatting changes.

[pcc]

Test case?

[hctim]

Updated with a graph printing test.

[pcc]

test/tools/llvm-cfi-verify/X86/dot-printing.s

8

It is hard to get a clear picture of what this test is testing for. Can you show me what your actual output is for this test?

13

I wouldn't test for this, presumably you have other tests for this functionality.

[hctim]

Addressed Peter's comments: Updated dot printing integration test to be more descriptive.

[pcc]

test/tools/llvm-cfi-verify/X86/dot-printing.s

13

Can you make the code deterministic by sorting the keys of IntermediateNodes before enumerating them? Then you can be more explicit in this test.

[hctim]

test/tools/llvm-cfi-verify/X86/dot-printing.s

13

I'd be very worried about the perf implications of this - with --print_graphs every single CFG would be sorted, O(n . log n) over 100,000 elements with ~10 elements each would be extremely expensive.

[pcc]

test/tools/llvm-cfi-verify/X86/dot-printing.s

13

This is a debugging feature, so the perf isn't too important. I wouldn't realistically expect people to render such large graphs, anyway.

[hctim]

Sorted intermediate nodes before printing graphs to DOT format - making the output deterministic.

[hctim]

... and merged in master.

[pcc]

LGTM

[hctim]

Merged in master in preparation for submission.

test/tools/llvm-cfi-verify/X86/dot-printing.s

+# RUN: llvm-mc %S/Inputs/protected-lineinfo.s -filetype obj \
+# RUN:         -triple x86_64-linux-elf -o %t.o
+# RUN: llvm-cfi-verify -print-graphs %t.o | FileCheck %s
+
+# The expected output is as follows:
+#   P 0x7b |  callq *%rax
+#   digraph graph_0x7b {
+#     "0x77:  jbe 2" -> "0x7b:  callq *%rax"
+#     "0x77:  jbe 2" -> "0x79:  ud2"
+#   }
+#   0x7b = tiny.cc:11:3 (main)
+
+# CHECK: {{^P.*callq +\*%rax.*$}}
+# CHECK-NEXT: digraph
+# CHECK-NEXT: {{^.*jbe.*->.*callq \*%rax}}
+# CHECK-NEXT: {{^.*jbe.*->.*ud2}}
+# CHECK-NEXT: }
+# CHECK-NEXT: tiny.cc:11

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

public:
 
   // Returns the inlining information for the provided address.
   Expected<DIInliningInfo> symbolizeInlinedCode(uint64_t Address);
 
   // Returns whether the provided Graph represents a protected indirect control
   // flow instruction in this file.
   CFIProtectionStatus validateCFIProtection(const GraphResult &Graph) const;
 
+  // Prints an instruction to the provided stream using this object's pretty-
+  // printers.
+  void printInstruction(const Instr &InstrMeta, raw_ostream &OS) const;
+
 protected:
   // Construct a blank object with the provided triple and features. Used in
   // testing, where a sub class will dependency inject protected methods to
   // allow analysis of raw binary, without requiring a fully valid ELF file.
   FileAnalysis(const Triple &ObjectTriple, const SubtargetFeatures &Features);
 
   // Add an instruction to this object.
   void addInstruction(const Instr &Instruction);

tools/llvm-cfi-verify/lib/FileAnalysis.cpp

FileAnalysis::validateCFIProtection(const GraphResult &Graph) const {
   for (const auto &BranchNode : Graph.ConditionalBranchNodes) {
     if (!BranchNode.CFIProtection)
       return CFIProtectionStatus::FAIL_BAD_CONDITIONAL_BRANCH;
   }
 
   return CFIProtectionStatus::PROTECTED;
 }
 
+void FileAnalysis::printInstruction(const Instr &InstrMeta,
+                                    raw_ostream &OS) const {
+  Printer->printInst(&InstrMeta.Instruction, OS, "", *SubtargetInfo.get());
+}
+
 Error FileAnalysis::initialiseDisassemblyMembers() {
   std::string TripleName = ObjectTriple.getTriple();
   ArchName = "";
   MCPU = "";
   std::string ErrorString;
 
   Symbolizer.reset(new LLVMSymbolizer());
 

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

struct GraphResult {
   // A list of top-level conditional branches that exist at the top of any
   // non-orphan paths from the base.
   std::vector<ConditionalBranchNode> ConditionalBranchNodes;
 
   // Returns an in-order list of the path between the address provided and the
   // base. The provided address must be part of this graph, and must not be a
   // conditional branch.
   std::vector<uint64_t> flattenAddress(uint64_t Address) const;
+
+  // Print the DOT representation of this result.
+  void printToDOT(const FileAnalysis &Analysis, raw_ostream &OS) const;
 };
 
 class GraphBuilder {
 public:
   // Build the control flow graph for a provided control flow node. This method
   // will enumerate all branch nodes that can lead to this node, and place them
   // into GraphResult::ConditionalBranchNodes. It will also provide any orphaned
   // (i.e. the upwards traversal did not make it to a branch node) flows to the

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

std::vector<uint64_t> GraphResult::flattenAddress(uint64_t Address) const {
 
   while (It != IntermediateNodes.end()) {
     Addresses.push_back(It->second);
     It = IntermediateNodes.find(It->second);
   }
   return Addresses;
 }
 
+void printPairToDOT(const FileAnalysis &Analysis, raw_ostream &OS,
+                          uint64_t From, uint64_t To) {
+  OS << "  \"" << format_hex(From, 2) << ": ";
+  Analysis.printInstruction(Analysis.getInstructionOrDie(From), OS);
+  OS << "\" -> \"" << format_hex(To, 2) << ": ";
+  Analysis.printInstruction(Analysis.getInstructionOrDie(To), OS);
+  OS << "\"\n";
+}
+
+void GraphResult::printToDOT(const FileAnalysis &Analysis,
+                             raw_ostream &OS) const {
+  std::map<uint64_t, uint64_t> SortedIntermediateNodes(
+      IntermediateNodes.begin(), IntermediateNodes.end());
+  OS << "digraph graph_" << format_hex(BaseAddress, 2) << " {\n";
+  for (const auto &KV : SortedIntermediateNodes)
+    printPairToDOT(Analysis, OS, KV.first, KV.second);
+
+  for (auto &BranchNode : ConditionalBranchNodes) {
+    for (auto &V : {BranchNode.Target, BranchNode.Fallthrough})
+      printPairToDOT(Analysis, OS, BranchNode.Address, V);
+  }
+  OS << "}\n";
+}
+
 GraphResult GraphBuilder::buildFlowGraph(const FileAnalysis &Analysis,
                                          uint64_t Address) {
   GraphResult Result;
   Result.BaseAddress = Address;
   DenseSet<uint64_t> OpenedNodes;
 
   const auto &IndirectInstructions = Analysis.getIndirectInstructions();
 

tools/llvm-cfi-verify/llvm-cfi-verify.cpp

 using namespace llvm::object;
 using namespace llvm::cfi_verify;
 
 cl::opt<std::string> InputFilename(cl::Positional, cl::desc("<input file>"),
                                    cl::Required);
 cl::opt<std::string> BlacklistFilename(cl::Positional,
                                        cl::desc("[blacklist file]"),
                                        cl::init("-"));
+cl::opt<bool> PrintGraphs(
+    "print-graphs",
+    cl::desc("Print graphs around indirect CF instructions in DOT format."),
+    cl::init(false));
 
 ExitOnError ExitOnErr;
 
 void printIndirectCFInstructions(FileAnalysis &Analysis,
                                  const SpecialCaseList *SpecialCaseList) {
   uint64_t ExpectedProtected = 0;
   uint64_t UnexpectedProtected = 0;
   uint64_t ExpectedUnprotected = 0;
CFIProtectionStatus ProtectionStatus =
         Analysis.validateCFIProtection(Graph);
     bool CFIProtected = (ProtectionStatus == CFIProtectionStatus::PROTECTED);
 
     if (CFIProtected)
       outs() << "P ";
     else
       outs() << "U ";
 
-    outs() << format_hex(Address, 2) << " | "
-           << Analysis.getMCInstrInfo()->getName(
-                  InstrMeta.Instruction.getOpcode())
-           << " \n";
+    outs() << format_hex(Address, 2) << " | ";
+    Analysis.printInstruction(InstrMeta, outs());
+    outs() << " \n";
+
+    if (PrintGraphs)
+      Graph.printToDOT(Analysis, outs());
 
     if (IgnoreDWARFFlag) {
       if (CFIProtected)
         ExpectedProtected++;
       else
         UnexpectedUnprotected++;
       continue;
     }