Index: tools/llvm-cfi-verify/CMakeLists.txt =================================================================== --- tools/llvm-cfi-verify/CMakeLists.txt +++ tools/llvm-cfi-verify/CMakeLists.txt @@ -13,4 +13,6 @@ add_llvm_tool(llvm-cfi-verify llvm-cfi-verify.cpp + FileVerifier.cpp + GraphBuilder.cpp ) Index: tools/llvm-cfi-verify/FileVerifier.h =================================================================== --- /dev/null +++ tools/llvm-cfi-verify/FileVerifier.h @@ -0,0 +1,179 @@ +//===- FileVerifier.h -------------------------------------------*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_CFI_VERIFY_FILE_VERIFIER_H +#define LLVM_CFI_VERIFY_FILE_VERIFIER_H + +#include "llvm/BinaryFormat/ELF.h" +#include "llvm/MC/MCAsmInfo.h" +#include "llvm/MC/MCContext.h" +#include "llvm/MC/MCDisassembler/MCDisassembler.h" +#include "llvm/MC/MCInst.h" +#include "llvm/MC/MCInstPrinter.h" +#include "llvm/MC/MCInstrAnalysis.h" +#include "llvm/MC/MCInstrDesc.h" +#include "llvm/MC/MCInstrInfo.h" +#include "llvm/MC/MCObjectFileInfo.h" +#include "llvm/MC/MCRegisterInfo.h" +#include "llvm/MC/MCSubtargetInfo.h" +#include "llvm/Object/Binary.h" +#include "llvm/Object/COFF.h" +#include "llvm/Object/ELFObjectFile.h" +#include "llvm/Object/ObjectFile.h" +#include "llvm/Support/Casting.h" +#include "llvm/Support/CommandLine.h" +#include "llvm/Support/Error.h" +#include "llvm/Support/MemoryBuffer.h" +#include "llvm/Support/TargetRegistry.h" +#include "llvm/Support/TargetSelect.h" +#include "llvm/Support/raw_ostream.h" + +#include +#include +#include +#include + +namespace llvm { +namespace cfi_verify { + +// This class is used to verify CFI instrumentation of a single file. +class FileVerifier { +public: + // A metadata struct for an instruction. + struct Instr { + uint64_t VMAddress; // Virtual memory address of this instruction. + MCInst Instruction; // Instruction. + uint64_t InstructionSize; // Size of this instruction. + std::string SectionName; // Section this instruction is found in. + bool Bad; // Is this instruction bad (in which case, Instr::Instruction is + // invalid). + }; + + // Construct a FileVerifier from a file path. + static Expected Create(StringRef Filename); + + // Construct and take ownership of the supplied object. Do not use this + // constructor, prefer to use FileVerifier::Create instead. + FileVerifier(object::OwningBinary Binary); + FileVerifier() = delete; + FileVerifier(const FileVerifier &) = delete; + FileVerifier(FileVerifier &&Other) = default; + + Error printIndirectCFInstructions() const; + + // Returns the instruction at the provided address. Returns nullptr if there + // is no instruction at the provided address. + const Instr *getInstruction(uint64_t Address) const; + + // Returns the instruction at the provided adress, dying if the instruction is + // not found. + const Instr &getInstructionOrDie(uint64_t Address) const; + + // Returns a pointer to the previous/next instruction in sequence, + // respectively. Retusn nullptr if the next/prev instruction doesn't exist, or + // if the provided instruction doesn't exist. + const Instr *getPrevInstructionSequential(const Instr &InstrMeta) const; + const Instr *getNextInstructionSequential(const Instr &InstrMeta) const; + + // Returns whether this instruction is an undefined instruction (used in + // branch-to-undefined CFI protections). + bool isUndefinedInstruction(const Instr &InstrMeta) const; + + // Returns whether this function can fall through to the next instruction. + // Undefined (and bad) instructions cannot fall through, and instruction that + // modify the control flow can only flow through if they are conditional + // branches or calls. + bool canFallThrough(const Instr &InstrMeta) const; + + // Returns the definitive next instruction. This is different from the next + // instruction sequantially as it will follow unconditional branches (assuming + // they can be resolved at compile time, i.e. not indirect). This instruction + // returns nullptr if the provided instruction does not transfer control flow + // to exactly one instruction that is known deterministically at compile time. + // Also returns nullptr if the deterministic target does not exist in this + // file. + const Instr *getDefiniteNextInstruction(const Instr &InstrMeta) const; + + // Get a list of deterministic control flows that lead to the provided + // instruction. This list includes all static control flow cross-references as + // well as the previous instruction if it can fall through. + std::set getControlFlowXRefs(const Instr &InstrMeta) const; + + const std::set &getIndirectInstructions() const; + const MCRegisterInfo *getRegisterInfo() const; + const MCInstrInfo *getMCInstrInfo() const; + const MCInstrAnalysis *getMCInstrAnalysis() 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. + FileVerifier(const Triple &ObjectTriple, const SubtargetFeatures &Features); + + // Add an instruction to this object. + void addInstruction(const Instr &Instruction); + + // Disassemble and parse the provided bytes into this object. Instruction + // address calculation is done relative to the provided SectionAddress, and + // instruction metadata is populated with the given section name. + void parseSectionContents(ArrayRef SectionBytes, + uint64_t SectionAddress, StringRef SectionName); + + // Constructs and initialises members required for disassembly. + Error initialiseDisassemblyMembers(); + + // Parses code sections from the internal object file. Saves them into the + // internal members. Should only be called once by Create(). + Error parseCodeSections(); + +private: + // Members that describe the input file. + object::OwningBinary Binary; + const object::ObjectFile *Object = nullptr; + Triple ObjectTriple; + std::string ArchName; + std::string MCPU; + const Target *ObjectTarget = nullptr; + SubtargetFeatures Features; + + // Members required for disassembly. + std::unique_ptr RegisterInfo; + std::unique_ptr AsmInfo; + std::unique_ptr SubtargetInfo; + std::unique_ptr MII; + MCObjectFileInfo MOFI; + std::unique_ptr Context; + std::unique_ptr Disassembler; + std::unique_ptr MIA; + std::unique_ptr Printer; + + // A mapping between the virtual memory address to the instruction metadata + // struct. + std::map Instructions; + + // Contains a mapping between a specific address, and a list of instructions + // that use this address as a branch target (including call instructions). + std::unordered_map> StaticBranchTargetings; + + // A list of addresses of indirect control flow instructions. + std::set IndirectInstructions; +}; + +class UnsupportedDisassembly : public ErrorInfo { +public: + static char ID; + + void log(raw_ostream &OS) const override; + std::error_code convertToErrorCode() const override; +}; + +} // namespace cfi_verify +} // namespace llvm + +#endif // LLVM_CFI_VERIFY_FILE_VERIFIER_H Index: tools/llvm-cfi-verify/FileVerifier.cpp =================================================================== --- /dev/null +++ tools/llvm-cfi-verify/FileVerifier.cpp @@ -0,0 +1,380 @@ +#include "FileVerifier.h" + +#include "llvm/BinaryFormat/ELF.h" +#include "llvm/MC/MCAsmInfo.h" +#include "llvm/MC/MCContext.h" +#include "llvm/MC/MCDisassembler/MCDisassembler.h" +#include "llvm/MC/MCInst.h" +#include "llvm/MC/MCInstPrinter.h" +#include "llvm/MC/MCInstrAnalysis.h" +#include "llvm/MC/MCInstrDesc.h" +#include "llvm/MC/MCInstrInfo.h" +#include "llvm/MC/MCObjectFileInfo.h" +#include "llvm/MC/MCRegisterInfo.h" +#include "llvm/MC/MCSubtargetInfo.h" +#include "llvm/Object/Binary.h" +#include "llvm/Object/COFF.h" +#include "llvm/Object/ELFObjectFile.h" +#include "llvm/Object/ObjectFile.h" +#include "llvm/Support/Casting.h" +#include "llvm/Support/CommandLine.h" +#include "llvm/Support/Error.h" +#include "llvm/Support/FormatVariadic.h" +#include "llvm/Support/MemoryBuffer.h" +#include "llvm/Support/TargetRegistry.h" +#include "llvm/Support/TargetSelect.h" +#include "llvm/Support/raw_ostream.h" + +#include + +using Instr = llvm::cfi_verify::FileVerifier::Instr; + +namespace llvm { +namespace cfi_verify { + +Expected FileVerifier::Create(StringRef Filename) { + // Open the filename provided. + Expected> BinaryOrErr = + object::createBinary(Filename); + if (!BinaryOrErr) + return BinaryOrErr.takeError(); + + // Construct the object and allow it to take ownership of the binary. + object::OwningBinary Binary = std::move(BinaryOrErr.get()); + FileVerifier Verifier(std::move(Binary)); + + Verifier.Object = dyn_cast(Verifier.Binary.getBinary()); + if (!Verifier.Object) + return make_error(); + + Verifier.ObjectTriple = Verifier.Object->makeTriple(); + Verifier.Features = Verifier.Object->getFeatures(); + + // Init the rest of the object. + auto InitResponse = Verifier.initialiseDisassemblyMembers(); + if (InitResponse) + return std::move(InitResponse); + + auto SectionParseResponse = Verifier.parseCodeSections(); + if (SectionParseResponse) + return std::move(SectionParseResponse); + + return std::move(Verifier); +} + +FileVerifier::FileVerifier(object::OwningBinary Binary) + : Binary(std::move(Binary)) {} + +FileVerifier::FileVerifier(const Triple &ObjectTriple, + const SubtargetFeatures &Features) + : ObjectTriple(ObjectTriple), Features(Features) {} + +Error FileVerifier::printIndirectCFInstructions() const { + for (const auto &Address : IndirectInstructions) { + const auto &InstructionKV = Instructions.find(Address); + if (InstructionKV == Instructions.end()) + return make_error( + formatv("No instruction found at address {0:x}", Address), + inconvertibleErrorCode()); + + const auto &InstrMeta = InstructionKV->second; + outs() << format_hex(Address, 2) << " [" << InstrMeta.SectionName + << "] = " << MII->getName(InstrMeta.Instruction.getOpcode()) << " "; + InstrMeta.Instruction.print(outs()); + outs() << "\n"; + } + + return Error::success(); +} + +const Instr * +FileVerifier::getPrevInstructionSequential(const Instr &InstrMeta) const { + std::map::const_iterator KV = + Instructions.find(InstrMeta.VMAddress); + if (KV == Instructions.end() || KV == Instructions.begin()) + return nullptr; + + if ((--KV)->second.Bad) + return nullptr; + + return &KV->second; +} + +const Instr * +FileVerifier::getNextInstructionSequential(const Instr &InstrMeta) const { + std::map::const_iterator KV = + Instructions.find(InstrMeta.VMAddress); + + if (KV++ == Instructions.end() || KV == Instructions.end()) + return nullptr; + + if (KV->second.Bad) + return nullptr; + + return &KV->second; +} + +const Instr *FileVerifier::getInstruction(uint64_t Address) const { + const auto &InstrKV = Instructions.find(Address); + if (InstrKV == Instructions.end()) + return nullptr; + + return &InstrKV->second; +} + +const Instr &FileVerifier::getInstructionOrDie(uint64_t Address) const { + const auto &InstrKV = Instructions.find(Address); + assert(InstrKV != Instructions.end() && "Address doesn't exist."); + return InstrKV->second; +} + +bool FileVerifier::isUndefinedInstruction(const Instr &InstrMeta) const { + return MII->getName(InstrMeta.Instruction.getOpcode()) == "TRAP"; +} + +bool FileVerifier::canFallThrough(const Instr &InstrMeta) const { + if (InstrMeta.Bad) + return false; + + if (isUndefinedInstruction(InstrMeta)) + return false; + + const auto &InstrDesc = MII->get(InstrMeta.Instruction.getOpcode()); + if (InstrDesc.mayAffectControlFlow(InstrMeta.Instruction, *RegisterInfo)) + return InstrDesc.isConditionalBranch(); + + return true; +} + +const Instr * +FileVerifier::getDefiniteNextInstruction(const Instr &InstrMeta) const { + if (InstrMeta.Bad) + return nullptr; + + if (isUndefinedInstruction(InstrMeta)) + return nullptr; + + const auto &InstrDesc = MII->get(InstrMeta.Instruction.getOpcode()); + if (InstrDesc.mayAffectControlFlow(InstrMeta.Instruction, *RegisterInfo)) { + if (InstrDesc.isConditionalBranch()) + return nullptr; + + uint64_t Target; + if (!MIA->evaluateBranch(InstrMeta.Instruction, InstrMeta.VMAddress, + InstrMeta.InstructionSize, Target)) + return nullptr; + + const auto &NextKV = Instructions.find(Target); + if (NextKV == Instructions.end()) + return nullptr; + + return &NextKV->second; + } + + const auto &NextKV = + Instructions.find(InstrMeta.VMAddress + InstrMeta.InstructionSize); + if (NextKV == Instructions.end()) + return nullptr; + + if (NextKV->second.Bad) + return nullptr; + + return &NextKV->second; +} + +std::set +FileVerifier::getControlFlowXRefs(const Instr &InstrMeta) const { + std::set CFCrossReferences; + const Instr *PrevInstruction = getPrevInstructionSequential(InstrMeta); + + if (PrevInstruction && canFallThrough(*PrevInstruction)) + CFCrossReferences.insert(PrevInstruction); + + const auto &TargetRefsKV = StaticBranchTargetings.find(InstrMeta.VMAddress); + if (TargetRefsKV == StaticBranchTargetings.end()) + return CFCrossReferences; + + for (uint64_t SourceInstrAddress : TargetRefsKV->second) { + const auto &SourceInstrKV = Instructions.find(SourceInstrAddress); + if (SourceInstrKV == Instructions.end()) { + errs() << "Failed to find source instruction at address " + << format_hex(SourceInstrAddress, 2) + << " for the cross-reference to instruction at address " + << format_hex(InstrMeta.VMAddress, 2) << ".\n"; + continue; + } + + CFCrossReferences.insert(&SourceInstrKV->second); + } + + return CFCrossReferences; +} + +const std::set &FileVerifier::getIndirectInstructions() const { + return IndirectInstructions; +} + +const MCRegisterInfo *FileVerifier::getRegisterInfo() const { + return RegisterInfo.get(); +} + +const MCInstrInfo *FileVerifier::getMCInstrInfo() const { return MII.get(); } + +const MCInstrAnalysis *FileVerifier::getMCInstrAnalysis() const { + return MIA.get(); +} + +Error FileVerifier::initialiseDisassemblyMembers() { + std::string TripleName = ObjectTriple.getTriple(); + ArchName = ""; + MCPU = ""; + + std::string ErrorString; + + ObjectTarget = + TargetRegistry::lookupTarget(ArchName, ObjectTriple, ErrorString); + + if (!ObjectTarget) + return make_error(Twine("Couldn't find target \"") + + ObjectTriple.getTriple() + + "\", failed with error: " + ErrorString, + inconvertibleErrorCode()); + + RegisterInfo.reset(ObjectTarget->createMCRegInfo(TripleName)); + if (!RegisterInfo) + return make_error("Failed to initialise RegisterInfo.", + inconvertibleErrorCode()); + + AsmInfo.reset(ObjectTarget->createMCAsmInfo(*RegisterInfo, TripleName)); + if (!AsmInfo) + return make_error("Failed to initialise AsmInfo.", + inconvertibleErrorCode()); + + SubtargetInfo.reset(ObjectTarget->createMCSubtargetInfo( + TripleName, MCPU, Features.getString())); + if (!SubtargetInfo) + return make_error("Failed to initialise SubtargetInfo.", + inconvertibleErrorCode()); + + MII.reset(ObjectTarget->createMCInstrInfo()); + if (!MII) + return make_error("Failed to initialise MII.", + inconvertibleErrorCode()); + + Context.reset(new MCContext(AsmInfo.get(), RegisterInfo.get(), &MOFI)); + + Disassembler.reset( + ObjectTarget->createMCDisassembler(*SubtargetInfo, *Context)); + + if (!Disassembler) + return make_error("No disassembler available for target", + inconvertibleErrorCode()); + + MIA.reset(ObjectTarget->createMCInstrAnalysis(MII.get())); + + Printer.reset(ObjectTarget->createMCInstPrinter( + ObjectTriple, AsmInfo->getAssemblerDialect(), *AsmInfo, *MII, + *RegisterInfo)); + + return Error::success(); +} + +Error FileVerifier::parseCodeSections() { + for (const object::SectionRef &Section : Object->sections()) { + // Ensure only executable sections get analysed. + if (!(object::ELFSectionRef(Section).getFlags() & ELF::SHF_EXECINSTR)) + continue; + + StringRef SectionContents; + if (Section.getContents(SectionContents)) + return make_error("Failed to retrieve section contents", + inconvertibleErrorCode()); + + StringRef SectionName; + if (Section.getName(SectionName)) + SectionName = "UNKNOWN"; + + ArrayRef SectionBytes((const uint8_t *)SectionContents.data(), + Section.getSize()); + parseSectionContents(SectionBytes, Section.getAddress(), SectionName); + } + return Error::success(); +} + +void FileVerifier::parseSectionContents(ArrayRef SectionBytes, + uint64_t SectionAddress, + StringRef SectionName) { + MCInst Instruction; + Instr InstrMeta; + uint64_t InstructionSize; + + for (uint64_t Byte = 0; Byte < SectionBytes.size();) { + bool BadInstruction = false; + + SectionBytes.drop_front(Byte); + + // Disassemble the instruction. + if (Disassembler->getInstruction(Instruction, InstructionSize, + SectionBytes.drop_front(Byte), 0, nulls(), + outs()) != MCDisassembler::Success) + BadInstruction = true; + + Byte += InstructionSize; + + uint64_t VMAddress = SectionAddress + Byte - InstructionSize; + InstrMeta.Instruction = Instruction; + InstrMeta.VMAddress = VMAddress; + InstrMeta.InstructionSize = InstructionSize; + InstrMeta.SectionName = SectionName; + InstrMeta.Bad = false; + + if (BadInstruction) { + InstrMeta.Bad = true; + addInstruction(InstrMeta); + continue; + } + + addInstruction(InstrMeta); + + // Skip additional parsing for instructions that do not affect the control + // flow. + const auto &InstrDesc = MII->get(Instruction.getOpcode()); + if (!InstrDesc.mayAffectControlFlow(Instruction, *RegisterInfo)) + continue; + + uint64_t Target; + if (MIA->evaluateBranch(Instruction, VMAddress, InstructionSize, Target)) { + // If the target can be evaluated, it's not indirect. + StaticBranchTargetings[Target].push_back(VMAddress); + continue; + } + + // Skip instructions that do not operate on register operands. + bool UsesRegisterOperand = false; + for (const auto &Operand : Instruction) { + if (Operand.isReg()) + UsesRegisterOperand = true; + } + + if (!UsesRegisterOperand) + continue; + + IndirectInstructions.insert(VMAddress); + } +} + +void FileVerifier::addInstruction(const Instr &Instruction) { + Instructions[Instruction.VMAddress] = Instruction; +} + +char UnsupportedDisassembly::ID; +void UnsupportedDisassembly::log(raw_ostream &OS) const { + OS << "Dissassembling of non-objects not currently supported.\n"; +} + +std::error_code UnsupportedDisassembly::convertToErrorCode() const { + return std::error_code(); +} + +} // namespace cfi_verify +} // namespace llvm Index: tools/llvm-cfi-verify/GraphBuilder.h =================================================================== --- /dev/null +++ tools/llvm-cfi-verify/GraphBuilder.h @@ -0,0 +1,114 @@ +//===- GraphBuilder.h -------------------------------------------*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_CFI_VERIFY_GRAPH_BUILDER_H +#define LLVM_CFI_VERIFY_GRAPH_BUILDER_H + +#include "FileVerifier.h" + +#include "llvm/BinaryFormat/ELF.h" +#include "llvm/MC/MCAsmInfo.h" +#include "llvm/MC/MCContext.h" +#include "llvm/MC/MCDisassembler/MCDisassembler.h" +#include "llvm/MC/MCInst.h" +#include "llvm/MC/MCInstPrinter.h" +#include "llvm/MC/MCInstrAnalysis.h" +#include "llvm/MC/MCInstrDesc.h" +#include "llvm/MC/MCInstrInfo.h" +#include "llvm/MC/MCObjectFileInfo.h" +#include "llvm/MC/MCRegisterInfo.h" +#include "llvm/MC/MCSubtargetInfo.h" +#include "llvm/Object/Binary.h" +#include "llvm/Object/COFF.h" +#include "llvm/Object/ELFObjectFile.h" +#include "llvm/Object/ObjectFile.h" +#include "llvm/Support/Casting.h" +#include "llvm/Support/CommandLine.h" +#include "llvm/Support/Error.h" +#include "llvm/Support/MemoryBuffer.h" +#include "llvm/Support/TargetRegistry.h" +#include "llvm/Support/TargetSelect.h" +#include "llvm/Support/raw_ostream.h" + +#include +#include +#include +#include + +using Instr = llvm::cfi_verify::FileVerifier::Instr; + +namespace llvm { +namespace cfi_verify { + +extern uint64_t SearchLengthForUndef; +extern uint64_t SearchLengthForConditionalBranch; + +struct ControlFlowNode { + ControlFlowNode *Next; + uint64_t InstructionAddress; + uint64_t FlowLength; +}; + +struct ConditionalBranchNode { + ControlFlowNode *Target; + ControlFlowNode *Fallthrough; + uint64_t InstructionAddress; + // Does this conditional branch successfully instrument CFI protections. + bool CFIProtection; +}; + +// Print the provided node to standard output. +void printConditionalBranchNode(const ConditionalBranchNode *Node); +void printControlFlowNode(const ControlFlowNode *Node, unsigned depth); +std::vector +flattenControlFlowNodeAddresses(const ControlFlowNode *Node); + +struct GraphResult { + ~GraphResult(); + + uint64_t BaseInstructionAddress; + std::vector BranchNodes; + std::vector OrphanedNodes; +}; + +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 provide + // them, fully evaulated, in GraphResult::BranchNodes. It will also provide + // any orphaned (i.e. did not make it to a branch node) flows to the provided + // node in GraphResult::OrphanedNodes. + static GraphResult buildFlowGraph(const FileVerifier &Verifier, + uint64_t Address); + +protected: + // Utilised by buildFlowGraph to build the tree out from the provided + // conditional branch node to an undefined instruction. The provided + // conditional branch node must have exactly one of its subtrees set, and will + // update the node's CFIProtection field if a deterministic flow can be found + // to an undefined instruction. + static void buildFlowsToUndefined(const FileVerifier &Verifier, + ConditionalBranchNode *BranchNode); + + // Creates a control flow node with the information from the parent, and links + // it to the provided child. + static ControlFlowNode *createParentNode(const Instr &ParentMeta, + ControlFlowNode *ChildNode); + +private: + static void + buildFlowGraphImpl(const FileVerifier &Verifier, ControlFlowNode *Node, + std::vector *BranchNodes, + std::vector *OrphanedNodes); +}; + +} // end namespace cfi_verify +} // end namespace llvm + +#endif // LLVM_CFI_VERIFY_GRAPH_BUILDER_H Index: tools/llvm-cfi-verify/GraphBuilder.cpp =================================================================== --- /dev/null +++ tools/llvm-cfi-verify/GraphBuilder.cpp @@ -0,0 +1,365 @@ +#include "GraphBuilder.h" + +#include "llvm/BinaryFormat/ELF.h" +#include "llvm/MC/MCAsmInfo.h" +#include "llvm/MC/MCContext.h" +#include "llvm/MC/MCDisassembler/MCDisassembler.h" +#include "llvm/MC/MCInst.h" +#include "llvm/MC/MCInstPrinter.h" +#include "llvm/MC/MCInstrAnalysis.h" +#include "llvm/MC/MCInstrDesc.h" +#include "llvm/MC/MCInstrInfo.h" +#include "llvm/MC/MCObjectFileInfo.h" +#include "llvm/MC/MCRegisterInfo.h" +#include "llvm/MC/MCSubtargetInfo.h" +#include "llvm/Object/Binary.h" +#include "llvm/Object/COFF.h" +#include "llvm/Object/ELFObjectFile.h" +#include "llvm/Object/ObjectFile.h" +#include "llvm/Support/Casting.h" +#include "llvm/Support/CommandLine.h" +#include "llvm/Support/Error.h" +#include "llvm/Support/FormatVariadic.h" +#include "llvm/Support/MemoryBuffer.h" +#include "llvm/Support/TargetRegistry.h" +#include "llvm/Support/TargetSelect.h" +#include "llvm/Support/raw_ostream.h" + +#include + +using Instr = llvm::cfi_verify::FileVerifier::Instr; + +namespace llvm { +namespace cfi_verify { + +uint64_t SearchLengthForUndef; +uint64_t SearchLengthForConditionalBranch; + +static cl::opt SearchLengthForUndefArg( + "search-length-undef", + cl::desc("Specify the maximum amount of instructions " + "to inspect when searching for an undefined " + "instruction from a conditional branch."), + cl::location(SearchLengthForUndef), cl::init(2)); + +static cl::opt SearchLengthForConditionalBranchArg( + "search-length-cb", + cl::desc("Specify the maximum amount of instructions " + "to inspect when searching for a conditional " + "branch from an indirect control flow."), + cl::location(SearchLengthForConditionalBranch), cl::init(20)); + +GraphResult::~GraphResult() { + std::set CFNs; + std::set CBNs; + for (const auto &BranchNode : BranchNodes) { + CBNs.insert(BranchNode); + for (ControlFlowNode *FlowNode = BranchNode->Target; FlowNode; + FlowNode = FlowNode->Next) + CFNs.insert(FlowNode); + + for (ControlFlowNode *FlowNode = BranchNode->Fallthrough; FlowNode; + FlowNode = FlowNode->Next) + CFNs.insert(FlowNode); + } + + for (const auto &FlowNode : OrphanedNodes) + CFNs.insert(FlowNode); + + for (const auto &Node : CFNs) + delete Node; + + for (const auto &Node : CBNs) + delete Node; +} + +void printControlFlowNode(const ControlFlowNode *Node, unsigned depth) { + assert(Node && "Null pointer provided to printControlFlowNode."); + for (unsigned i = 0; i < depth; ++i) + outs() << " "; + + outs() << "[" << Node->FlowLength << "] " + << format_hex(Node->InstructionAddress, 2) << "\n"; + if (Node->Next) + printControlFlowNode(Node->Next, depth + 1); +} + +void printConditionalBranchNode(const ConditionalBranchNode *Node) { + assert(Node && "Null pointer provided to printConditionalBranchNode."); + outs() << format_hex(Node->InstructionAddress, 2) << "\n"; + outs() << " Target:\n"; + if (Node->Target) + printControlFlowNode(Node->Target, 1); + else + outs() << " ???\n"; + + outs() << " Fallthrough:\n"; + if (Node->Fallthrough) + printControlFlowNode(Node->Fallthrough, 1); + else + outs() << " ???\n"; +} + +std::vector +flattenControlFlowNodeAddresses(const ControlFlowNode *Node) { + std::vector Addresses; + while (Node != nullptr) { + Addresses.push_back(Node->InstructionAddress); + Node = Node->Next; + } + return Addresses; +} + +GraphResult GraphBuilder::buildFlowGraph(const FileVerifier &Verifier, + uint64_t Address) { + GraphResult Result; + Result.BaseInstructionAddress = Address; + + const auto &IndirectInstructions = Verifier.getIndirectInstructions(); + + if (IndirectInstructions.find(Address) == IndirectInstructions.end()) + return Result; + + ControlFlowNode *Node = new ControlFlowNode(); + Node->Next = nullptr; + Node->InstructionAddress = Address; + Node->FlowLength = 0; + + buildFlowGraphImpl(Verifier, Node, &Result.BranchNodes, + &Result.OrphanedNodes); + return Result; +} + +void GraphBuilder::buildFlowsToUndefined(const FileVerifier &Verifier, + ConditionalBranchNode *BranchNode) { + assert(BranchNode && "Null pointer provided to buildFlowsToUndefined."); + assert(SearchLengthForUndef > 0 && + "Search length for undefined flow must be greater than zero."); + + // Resolve the metadata for the provided node. + const auto &BranchInstrMetaPtr = + Verifier.getInstruction(BranchNode->InstructionAddress); + if (!BranchInstrMetaPtr) { + errs() << "Failed to build flows from instruction with address" + << format_hex(BranchNode->InstructionAddress, 2) << ".\n"; + return; + } + const auto &BranchInstrMeta = *BranchInstrMetaPtr; + + // Start setting up the next node in the chain. + const Instr *NextMetaPtr; + ControlFlowNode *NextNode = new ControlFlowNode(); + NextNode->Next = nullptr; + NextNode->FlowLength = 1; + + // Find out the next instruction in the chain and add it to the new node. + if (BranchNode->Target && !BranchNode->Fallthrough) { + // We know the target of the branch, find the fallthrough. + NextMetaPtr = Verifier.getNextInstructionSequential(BranchInstrMeta); + if (!NextMetaPtr) { + errs() << "Failed to get next instruction from " + << format_hex(BranchNode->InstructionAddress, 2) << ".\n"; + delete NextNode; + return; + } + + NextNode->InstructionAddress = NextMetaPtr->VMAddress; + BranchNode->Fallthrough = NextNode; // Add the new node to the branch head. + } else if (BranchNode->Fallthrough && !BranchNode->Target) { + // We already know the fallthrough, evaluate the target. + uint64_t Target; + if (!Verifier.getMCInstrAnalysis()->evaluateBranch( + BranchInstrMeta.Instruction, BranchInstrMeta.VMAddress, + BranchInstrMeta.InstructionSize, Target)) { + errs() << "Failed to get branch target for conditional branch at address " + << format_hex(BranchInstrMeta.VMAddress, 2) << ".\n"; + delete NextNode; + return; + } + + // Resolve the meta pointer for the target of this branch. + NextMetaPtr = Verifier.getInstruction(Target); + if (!NextMetaPtr) { + errs() << "Failed to find instruction at address " + << format_hex(Target, 2) << ".\n"; + delete NextNode; + return; + } + + NextNode->InstructionAddress = Target; + BranchNode->Target = NextNode; // Add the new node to the branch head. + } else { + errs() << "ControlBranchNode supplied to buildFlowsToUndefined should " + "provide Target xor Fallthrough.\n"; + delete NextNode; + return; + } + + ControlFlowNode *CurrentNode = NextNode; + const Instr *CurrentMetaPtr = NextMetaPtr; + + // Now the branch head has been set properly, complete the rest of the chain. + for (uint64_t i = 1; i < SearchLengthForUndef; ++i) { + // Check to see whether the chain should die. + if (Verifier.isUndefinedInstruction(*CurrentMetaPtr)) { + BranchNode->CFIProtection = true; + return; + } + + // Find the metadata of the next instruction. + NextMetaPtr = Verifier.getDefiniteNextInstruction(*CurrentMetaPtr); + if (!NextMetaPtr) + return; + + // Setup the next node. + NextNode = new ControlFlowNode(); + NextNode->Next = nullptr; + NextNode->InstructionAddress = NextMetaPtr->VMAddress; + NextNode->FlowLength = CurrentNode->FlowLength + 1; + CurrentNode->Next = NextNode; + + // Finalise ready for the next loop. + CurrentMetaPtr = NextMetaPtr; + CurrentNode = NextNode; + } + + // Final check of the last thing we added to the chain. + if (Verifier.isUndefinedInstruction(*CurrentMetaPtr)) + BranchNode->CFIProtection = true; +} + +ControlFlowNode *GraphBuilder::createParentNode(const Instr &ParentMeta, + ControlFlowNode *ChildNode) { + assert(ChildNode && "Null pointer provided to createParentNode"); + ControlFlowNode *ParentNode = new ControlFlowNode(); + ParentNode->Next = ChildNode; + ParentNode->InstructionAddress = ParentMeta.VMAddress; + ParentNode->FlowLength = ChildNode->FlowLength + 1; + return ParentNode; +} + +void GraphBuilder::buildFlowGraphImpl( + const FileVerifier &Verifier, ControlFlowNode *ChildNode, + std::vector *BranchNodes, + std::vector *OrphanedNodes) { + assert(ChildNode && BranchNodes && OrphanedNodes && + "Null pointer provided to buildFlowGraphImpl."); + + // If we've exceeded the flow length, terminate. + if (ChildNode->FlowLength >= SearchLengthForConditionalBranch) { + OrphanedNodes->push_back(ChildNode); + return; + } + + // Get the metadata for the node instruction. + const auto &InstrMetaPtr = + Verifier.getInstruction(ChildNode->InstructionAddress); + if (!InstrMetaPtr) { + errs() << "Failed to build flow graph for instruction at address " + << format_hex(ChildNode->InstructionAddress, 2) << ".\n"; + OrphanedNodes->push_back(ChildNode); + return; + } + const auto &ChildMeta = *InstrMetaPtr; + + std::set CFCrossRefs = Verifier.getControlFlowXRefs(ChildMeta); + + bool HasValidCrossRef = false; + + for (const auto *ParentMetaPtr : CFCrossRefs) { + assert(ParentMetaPtr && "CFCrossRefs returned nullptr."); + const auto &ParentMeta = *ParentMetaPtr; + const auto &ParentDesc = + Verifier.getMCInstrInfo()->get(ParentMeta.Instruction.getOpcode()); + + if (!ParentDesc.mayAffectControlFlow(ParentMeta.Instruction, + *Verifier.getRegisterInfo())) { + // If this cross reference doesn't affect CF, continue the graph. + buildFlowGraphImpl(Verifier, createParentNode(ParentMeta, ChildNode), + BranchNodes, OrphanedNodes); + HasValidCrossRef = true; + continue; + } else { + // Evaluate the branch target to ascertain whether this XRef is the result + // of a fallthrough or the target of a branch. + uint64_t BranchTarget; + if (!Verifier.getMCInstrAnalysis()->evaluateBranch( + ParentMeta.Instruction, ParentMeta.VMAddress, + ParentMeta.InstructionSize, BranchTarget)) { + errs() << "Failed to evaluate branch target for instruction at address " + << format_hex(ParentMeta.VMAddress, 2) << ".\n"; + OrphanedNodes->push_back(createParentNode(ParentMeta, ChildNode)); + continue; + } + + // Allow unconditional branches to be part of the upwards traversal. + // Ensures that the unconditional branch is actually an XRef to the child. + if (ParentDesc.isUnconditionalBranch()) { + if (BranchTarget == ChildMeta.VMAddress) { + // Ensure the unconditional branch can't fall back on itself. Check + // the current tree. + bool IsUniqueInTree = true; + for (const auto &InstructionAddressInTree : + flattenControlFlowNodeAddresses(ChildNode)) { + if (InstructionAddressInTree == ParentMeta.VMAddress) { + IsUniqueInTree = false; + break; + } + } + + if (!IsUniqueInTree) { + OrphanedNodes->push_back(createParentNode(ParentMeta, ChildNode)); + continue; + } + + ControlFlowNode *NewNode = new ControlFlowNode(); + NewNode->Next = ChildNode; + NewNode->InstructionAddress = ParentMeta.VMAddress; + NewNode->FlowLength = ChildNode->FlowLength + 1; + + buildFlowGraphImpl(Verifier, NewNode, BranchNodes, OrphanedNodes); + HasValidCrossRef = true; + continue; + } else { + errs() << "Control flow to " << format_hex(ChildMeta.VMAddress, 2) + << ", but target resolution of " + << format_hex(ParentMeta.VMAddress, 2) + << " is not this address?\n"; + OrphanedNodes->push_back(createParentNode(ParentMeta, ChildNode)); + continue; + } + } + + // Ensure that any unknown CFs are caught. + if (!ParentDesc.isConditionalBranch()) { + errs() << "Unknown control flow encountered when building graph at " + << format_hex(ChildMeta.VMAddress, 2) << "\n."; + OrphanedNodes->push_back(createParentNode(ParentMeta, ChildNode)); + continue; + } + + // Only direct conditional branches should be present at this point. Setup + // a conditional branch node and build flows to the ud2. + ConditionalBranchNode *BranchNode = new ConditionalBranchNode(); + BranchNode->InstructionAddress = ParentMeta.VMAddress; + BranchNode->Target = nullptr; + BranchNode->Fallthrough = nullptr; + BranchNode->CFIProtection = false; + BranchNodes->push_back(BranchNode); + + if (BranchTarget == ChildMeta.VMAddress) + BranchNode->Target = ChildNode; + else + BranchNode->Fallthrough = ChildNode; + + HasValidCrossRef = true; + buildFlowsToUndefined(Verifier, BranchNode); + } + } + + if (!HasValidCrossRef) + OrphanedNodes->push_back(ChildNode); +} + +} // namespace cfi_verify +} // namespace llvm Index: tools/llvm-cfi-verify/llvm-cfi-verify.cpp =================================================================== --- tools/llvm-cfi-verify/llvm-cfi-verify.cpp +++ tools/llvm-cfi-verify/llvm-cfi-verify.cpp @@ -17,67 +17,22 @@ // //===----------------------------------------------------------------------===// -#include "llvm/MC/MCAsmInfo.h" -#include "llvm/MC/MCContext.h" -#include "llvm/MC/MCDisassembler/MCDisassembler.h" -#include "llvm/MC/MCInst.h" -#include "llvm/MC/MCInstPrinter.h" -#include "llvm/MC/MCInstrAnalysis.h" -#include "llvm/MC/MCInstrDesc.h" -#include "llvm/MC/MCInstrInfo.h" -#include "llvm/MC/MCObjectFileInfo.h" -#include "llvm/MC/MCRegisterInfo.h" -#include "llvm/MC/MCSubtargetInfo.h" -#include "llvm/Object/Binary.h" -#include "llvm/Object/COFF.h" -#include "llvm/Object/ObjectFile.h" -#include "llvm/Support/Casting.h" +#include "FileVerifier.h" + +#include "llvm/BinaryFormat/ELF.h" #include "llvm/Support/CommandLine.h" -#include "llvm/Support/MemoryBuffer.h" -#include "llvm/Support/TargetRegistry.h" -#include "llvm/Support/TargetSelect.h" -#include "llvm/Support/raw_ostream.h" +#include "llvm/Support/Error.h" -#include #include using namespace llvm; using namespace llvm::object; +using namespace llvm::cfi_verify; -cl::opt ArgDumpSymbols("sym", cl::desc("Dump the symbol table.")); cl::opt InputFilename(cl::Positional, cl::desc(""), cl::Required); -static void printSymbols(const ObjectFile *Object) { - for (const SymbolRef &Symbol : Object->symbols()) { - outs() << "Symbol [" << format_hex_no_prefix(Symbol.getValue(), 2) - << "] = "; - - auto SymbolName = Symbol.getName(); - if (SymbolName) - outs() << *SymbolName; - else - outs() << "UNKNOWN"; - - if (Symbol.getFlags() & SymbolRef::SF_Hidden) - outs() << " .hidden"; - - outs() << " (Section = "; - - auto SymbolSection = Symbol.getSection(); - if (SymbolSection) { - StringRef SymbolSectionName; - if ((*SymbolSection)->getName(SymbolSectionName)) - outs() << "UNKNOWN)"; - else - outs() << SymbolSectionName << ")"; - } else { - outs() << "N/A)"; - } - - outs() << "\n"; - } -} +ExitOnError ExitOnErr; int main(int argc, char **argv) { cl::ParseCommandLineOptions(argc, argv); @@ -87,155 +42,8 @@ InitializeAllAsmParsers(); InitializeAllDisassemblers(); - Expected> BinaryOrErr = createBinary(InputFilename); - if (!BinaryOrErr) { - errs() << "Failed to open file.\n"; - return EXIT_FAILURE; - } - - Binary &Binary = *BinaryOrErr.get().getBinary(); - ObjectFile *Object = dyn_cast(&Binary); - if (!Object) { - errs() << "Disassembling of non-objects not currently supported.\n"; - return EXIT_FAILURE; - } - - Triple TheTriple = Object->makeTriple(); - std::string TripleName = TheTriple.getTriple(); - std::string ArchName = ""; - std::string ErrorString; - - const Target *TheTarget = - TargetRegistry::lookupTarget(ArchName, TheTriple, ErrorString); - - if (!TheTarget) { - errs() << "Couldn't find target \"" << TheTriple.getTriple() - << "\", failed with error: " << ErrorString << ".\n"; - return EXIT_FAILURE; - } - - SubtargetFeatures Features = Object->getFeatures(); - - std::unique_ptr RegisterInfo( - TheTarget->createMCRegInfo(TripleName)); - if (!RegisterInfo) { - errs() << "Failed to initialise RegisterInfo.\n"; - return EXIT_FAILURE; - } - - std::unique_ptr AsmInfo( - TheTarget->createMCAsmInfo(*RegisterInfo, TripleName)); - if (!AsmInfo) { - errs() << "Failed to initialise AsmInfo.\n"; - return EXIT_FAILURE; - } - - std::string MCPU = ""; - std::unique_ptr SubtargetInfo( - TheTarget->createMCSubtargetInfo(TripleName, MCPU, Features.getString())); - if (!SubtargetInfo) { - errs() << "Failed to initialise SubtargetInfo.\n"; - return EXIT_FAILURE; - } - - std::unique_ptr MII(TheTarget->createMCInstrInfo()); - if (!MII) { - errs() << "Failed to initialise MII.\n"; - return EXIT_FAILURE; - } - - MCObjectFileInfo MOFI; - MCContext Context(AsmInfo.get(), RegisterInfo.get(), &MOFI); - - std::unique_ptr Disassembler( - TheTarget->createMCDisassembler(*SubtargetInfo, Context)); - - if (!Disassembler) { - errs() << "No disassembler available for target."; - return EXIT_FAILURE; - } - - std::unique_ptr MIA( - TheTarget->createMCInstrAnalysis(MII.get())); - - std::unique_ptr Printer( - TheTarget->createMCInstPrinter(TheTriple, AsmInfo->getAssemblerDialect(), - *AsmInfo, *MII, *RegisterInfo)); - - if (ArgDumpSymbols) - printSymbols(Object); - - for (const SectionRef &Section : Object->sections()) { - outs() << "Section [" << format_hex_no_prefix(Section.getAddress(), 2) - << "] = "; - StringRef SectionName; - - if (Section.getName(SectionName)) - outs() << "UNKNOWN.\n"; - else - outs() << SectionName << "\n"; - - StringRef SectionContents; - if (Section.getContents(SectionContents)) { - errs() << "Failed to retrieve section contents.\n"; - return EXIT_FAILURE; - } - - MCInst Instruction; - uint64_t InstructionSize; - - ArrayRef SectionBytes((const uint8_t *)SectionContents.data(), - Section.getSize()); - - for (uint64_t Byte = 0; Byte < Section.getSize();) { - bool BadInstruction = false; - - // Disassemble the instruction. - if (Disassembler->getInstruction( - Instruction, InstructionSize, SectionBytes.drop_front(Byte), 0, - nulls(), outs()) != MCDisassembler::Success) { - BadInstruction = true; - } - - Byte += InstructionSize; - - if (BadInstruction) - continue; - - // Skip instructions that do not affect the control flow. - const auto &InstrDesc = MII->get(Instruction.getOpcode()); - if (!InstrDesc.mayAffectControlFlow(Instruction, *RegisterInfo)) - continue; - - // Skip instructions that do not operate on register operands. - bool UsesRegisterOperand = false; - for (const auto &Operand : Instruction) { - if (Operand.isReg()) - UsesRegisterOperand = true; - } - - if (!UsesRegisterOperand) - continue; - - // Print the instruction address. - outs() << " " - << format_hex(Section.getAddress() + Byte - InstructionSize, 2) - << ": "; - - // Print the instruction bytes. - for (uint64_t i = 0; i < InstructionSize; ++i) { - outs() << format_hex_no_prefix(SectionBytes[Byte - InstructionSize + i], - 2) - << " "; - } - - // Print the instruction. - outs() << " | " << MII->getName(Instruction.getOpcode()) << " "; - Instruction.dump_pretty(outs(), Printer.get()); - - outs() << "\n"; - } - } + FileVerifier Verifier = ExitOnErr(FileVerifier::Create(InputFilename)); + ExitOnErr(Verifier.printIndirectCFInstructions()); return EXIT_SUCCESS; } Index: tools/llvm-cfi-verify/unittests/CMakeLists.txt =================================================================== --- /dev/null +++ tools/llvm-cfi-verify/unittests/CMakeLists.txt @@ -0,0 +1,18 @@ +set(LLVM_LINK_COMPONENTS + AllTargetsAsmPrinters + AllTargetsAsmParsers + AllTargetsDescs + AllTargetsDisassemblers + AllTargetsInfos + MC + Object + MCParser + Object + Support + ) + +add_llvm_unittest(CFIVerifyTests + FileVerifier.cpp + GraphBuilder.cpp + ../GraphBuilder.cpp + ../FileVerifier.cpp) Index: tools/llvm-cfi-verify/unittests/FileVerifier.cpp =================================================================== --- /dev/null +++ tools/llvm-cfi-verify/unittests/FileVerifier.cpp @@ -0,0 +1,490 @@ +//===- llvm/tools/llvm-cfi-verify/unittests/FileVerifier.cpp --------------===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// + +#include "../FileVerifier.h" +#include "gmock/gmock.h" +#include "gtest/gtest.h" + +#include "llvm/BinaryFormat/ELF.h" +#include "llvm/MC/MCAsmInfo.h" +#include "llvm/MC/MCContext.h" +#include "llvm/MC/MCDisassembler/MCDisassembler.h" +#include "llvm/MC/MCInst.h" +#include "llvm/MC/MCInstPrinter.h" +#include "llvm/MC/MCInstrAnalysis.h" +#include "llvm/MC/MCInstrDesc.h" +#include "llvm/MC/MCInstrInfo.h" +#include "llvm/MC/MCObjectFileInfo.h" +#include "llvm/MC/MCRegisterInfo.h" +#include "llvm/MC/MCSubtargetInfo.h" +#include "llvm/Object/Binary.h" +#include "llvm/Object/COFF.h" +#include "llvm/Object/ELFObjectFile.h" +#include "llvm/Object/ObjectFile.h" +#include "llvm/Support/Casting.h" +#include "llvm/Support/CommandLine.h" +#include "llvm/Support/Error.h" +#include "llvm/Support/MemoryBuffer.h" +#include "llvm/Support/TargetRegistry.h" +#include "llvm/Support/TargetSelect.h" +#include "llvm/Support/raw_ostream.h" + +#include + +using Instr = ::llvm::cfi_verify::FileVerifier::Instr; +using ::testing::Eq; +using ::testing::Field; + +namespace llvm { +namespace cfi_verify { +namespace { +class ELFx86TestFileVerifier : public FileVerifier { +public: + ELFx86TestFileVerifier() + : FileVerifier(Triple("x86_64--"), SubtargetFeatures()) {} + + // Expose this method publicly for testing. + void parseSectionContents(ArrayRef SectionBytes, + uint64_t SectionAddress, StringRef SectionName) { + FileVerifier::parseSectionContents(SectionBytes, SectionAddress, + SectionName); + } + + Error initialiseDisassemblyMembers() { + return FileVerifier::initialiseDisassemblyMembers(); + } +}; + +class BasicFileVerifierTest : public ::testing::Test { +protected: + virtual void SetUp() { + if (Verifier.initialiseDisassemblyMembers()) { + exit(EXIT_FAILURE); + } + } + + ELFx86TestFileVerifier Verifier; +}; + +TEST_F(BasicFileVerifierTest, BasicDisassemblyTraversalTest) { + Verifier.parseSectionContents( + { + 0x90, // 0: nop + 0xb0, 0x00, // 1: mov $0x0, %al + 0x48, 0x89, 0xe5, // 3: mov %rsp, %rbp + 0x48, 0x83, 0xec, 0x18, // 6: sub $0x18, %rsp + 0x48, 0xbe, 0xc4, 0x07, 0x40, + 0x00, 0x00, 0x00, 0x00, 0x00, // 10: movabs $0x4007c4, %rsi + 0x2f, // 20: (bad) + 0x41, 0x0e, // 21: rex.B (bad) + 0x62, 0x72, 0x65, 0x61, 0x6b, // 23: (bad) {%k1} + }, + 0xDEADBEEF, "Test"); + + EXPECT_EQ(nullptr, Verifier.getInstruction(0x0)); + EXPECT_EQ(nullptr, Verifier.getInstruction(0x1000)); + + // 0xDEADBEEF: nop + const auto *InstrMeta = Verifier.getInstruction(0xDEADBEEF); + EXPECT_NE(nullptr, InstrMeta); + EXPECT_EQ(0xDEADBEEF, InstrMeta->VMAddress); + EXPECT_EQ(1, InstrMeta->InstructionSize); + EXPECT_EQ("Test", InstrMeta->SectionName); + EXPECT_FALSE(InstrMeta->Bad); + + const auto *NextInstrMeta = Verifier.getNextInstructionSequential(*InstrMeta); + EXPECT_EQ(nullptr, Verifier.getPrevInstructionSequential(*InstrMeta)); + const auto *PrevInstrMeta = InstrMeta; + + // 0xDEADBEEF + 1: mov $0x0, %al + InstrMeta = Verifier.getInstruction(0xDEADBEEF + 1); + EXPECT_NE(nullptr, InstrMeta); + EXPECT_EQ(NextInstrMeta, InstrMeta); + EXPECT_EQ(0xDEADBEEF + 1, InstrMeta->VMAddress); + EXPECT_EQ(2, InstrMeta->InstructionSize); + EXPECT_EQ("Test", InstrMeta->SectionName); + EXPECT_FALSE(InstrMeta->Bad); + + NextInstrMeta = Verifier.getNextInstructionSequential(*InstrMeta); + EXPECT_EQ(PrevInstrMeta, Verifier.getPrevInstructionSequential(*InstrMeta)); + PrevInstrMeta = InstrMeta; + + // 0xDEADBEEF + 3: mov %rsp, %rbp + InstrMeta = Verifier.getInstruction(0xDEADBEEF + 3); + EXPECT_NE(nullptr, InstrMeta); + EXPECT_EQ(NextInstrMeta, InstrMeta); + EXPECT_EQ(0xDEADBEEF + 3, InstrMeta->VMAddress); + EXPECT_EQ(3, InstrMeta->InstructionSize); + EXPECT_EQ("Test", InstrMeta->SectionName); + EXPECT_FALSE(InstrMeta->Bad); + + NextInstrMeta = Verifier.getNextInstructionSequential(*InstrMeta); + EXPECT_EQ(PrevInstrMeta, Verifier.getPrevInstructionSequential(*InstrMeta)); + PrevInstrMeta = InstrMeta; + + // 0xDEADBEEF + 6: sub $0x18, %rsp + InstrMeta = Verifier.getInstruction(0xDEADBEEF + 6); + EXPECT_NE(nullptr, InstrMeta); + EXPECT_EQ(NextInstrMeta, InstrMeta); + EXPECT_EQ(0xDEADBEEF + 6, InstrMeta->VMAddress); + EXPECT_EQ(4, InstrMeta->InstructionSize); + EXPECT_EQ("Test", InstrMeta->SectionName); + EXPECT_FALSE(InstrMeta->Bad); + + NextInstrMeta = Verifier.getNextInstructionSequential(*InstrMeta); + EXPECT_EQ(PrevInstrMeta, Verifier.getPrevInstructionSequential(*InstrMeta)); + PrevInstrMeta = InstrMeta; + + // 0xDEADBEEF + 10: movabs $0x4007c4, %rsi + InstrMeta = Verifier.getInstruction(0xDEADBEEF + 10); + EXPECT_NE(nullptr, InstrMeta); + EXPECT_EQ(NextInstrMeta, InstrMeta); + EXPECT_EQ(0xDEADBEEF + 10, InstrMeta->VMAddress); + EXPECT_EQ(10, InstrMeta->InstructionSize); + EXPECT_EQ("Test", InstrMeta->SectionName); + EXPECT_FALSE(InstrMeta->Bad); + + EXPECT_EQ(nullptr, Verifier.getNextInstructionSequential(*InstrMeta)); + EXPECT_EQ(PrevInstrMeta, Verifier.getPrevInstructionSequential(*InstrMeta)); + PrevInstrMeta = InstrMeta; + + // 0xDEADBEEF + 20: (bad) + InstrMeta = Verifier.getInstruction(0xDEADBEEF + 20); + EXPECT_NE(nullptr, InstrMeta); + EXPECT_EQ(0xDEADBEEF + 20, InstrMeta->VMAddress); + EXPECT_EQ(1, InstrMeta->InstructionSize); + EXPECT_EQ("Test", InstrMeta->SectionName); + EXPECT_TRUE(InstrMeta->Bad); + + EXPECT_EQ(nullptr, Verifier.getNextInstructionSequential(*InstrMeta)); + EXPECT_EQ(PrevInstrMeta, Verifier.getPrevInstructionSequential(*InstrMeta)); + + // 0xDEADBEEF + 21: rex.B (bad) + InstrMeta = Verifier.getInstruction(0xDEADBEEF + 21); + EXPECT_NE(nullptr, InstrMeta); + EXPECT_EQ(0xDEADBEEF + 21, InstrMeta->VMAddress); + EXPECT_EQ(2, InstrMeta->InstructionSize); + EXPECT_EQ("Test", InstrMeta->SectionName); + EXPECT_TRUE(InstrMeta->Bad); + + EXPECT_EQ(nullptr, Verifier.getNextInstructionSequential(*InstrMeta)); + EXPECT_EQ(nullptr, Verifier.getPrevInstructionSequential(*InstrMeta)); + + // 0xDEADBEEF + 6: (bad) {%k1} + InstrMeta = Verifier.getInstruction(0xDEADBEEF + 23); + EXPECT_NE(nullptr, InstrMeta); + EXPECT_EQ(0xDEADBEEF + 23, InstrMeta->VMAddress); + EXPECT_EQ(5, InstrMeta->InstructionSize); + EXPECT_EQ("Test", InstrMeta->SectionName); + EXPECT_TRUE(InstrMeta->Bad); + + EXPECT_EQ(nullptr, Verifier.getNextInstructionSequential(*InstrMeta)); + EXPECT_EQ(nullptr, Verifier.getPrevInstructionSequential(*InstrMeta)); +} + +TEST_F(BasicFileVerifierTest, PrevAndNextFromBadInst) { + Verifier.parseSectionContents( + { + 0x90, // 0: nop + 0x2f, // 1: (bad) + 0x90 // 2: nop + }, + 0xDEADBEEF, "Test"); + const auto &BadInstrMeta = Verifier.getInstructionOrDie(0xDEADBEEF + 1); + const auto *GoodInstrMeta = + Verifier.getPrevInstructionSequential(BadInstrMeta); + EXPECT_NE(nullptr, GoodInstrMeta); + EXPECT_EQ(0xDEADBEEF, GoodInstrMeta->VMAddress); + EXPECT_EQ(1, GoodInstrMeta->InstructionSize); + + GoodInstrMeta = Verifier.getNextInstructionSequential(BadInstrMeta); + EXPECT_NE(nullptr, GoodInstrMeta); + EXPECT_EQ(0xDEADBEEF + 2, GoodInstrMeta->VMAddress); + EXPECT_EQ(1, GoodInstrMeta->InstructionSize); +} + +TEST_F(BasicFileVerifierTest, UndefinedInstructionTest) { + Verifier.parseSectionContents( + { + 0x90, // 0: nop + 0xb0, 0x00, // 1: mov $0x0, %al + 0x48, 0x89, 0xe5, // 3: mov %rsp, %rbp + 0x48, 0x83, 0xec, 0x18, // 6: sub $0x18, %rsp + 0x48, 0xbe, 0xc4, 0x07, 0x40, + 0x00, 0x00, 0x00, 0x00, 0x00, // 10: movabs $0x4007c4, %rsi + 0x2f, // 20: (bad) + 0x41, 0x0e, // 21: rex.B (bad) + 0x62, 0x72, 0x65, 0x61, 0x6b, // 23: (bad) {%k1} + 0x0f, 0x0b // 28: ud2 + }, + 0xDEADBEEF, "Test"); + + EXPECT_FALSE(Verifier.isUndefinedInstruction( + Verifier.getInstructionOrDie(0xDEADBEEF))); + EXPECT_FALSE(Verifier.isUndefinedInstruction( + Verifier.getInstructionOrDie(0xDEADBEEF + 3))); + EXPECT_FALSE(Verifier.isUndefinedInstruction( + Verifier.getInstructionOrDie(0xDEADBEEF + 6))); + EXPECT_FALSE(Verifier.isUndefinedInstruction( + Verifier.getInstructionOrDie(0xDEADBEEF + 10))); + EXPECT_FALSE(Verifier.isUndefinedInstruction( + Verifier.getInstructionOrDie(0xDEADBEEF + 20))); + EXPECT_FALSE(Verifier.isUndefinedInstruction( + Verifier.getInstructionOrDie(0xDEADBEEF + 21))); + EXPECT_FALSE(Verifier.isUndefinedInstruction( + Verifier.getInstructionOrDie(0xDEADBEEF + 23))); + EXPECT_TRUE(Verifier.isUndefinedInstruction( + Verifier.getInstructionOrDie(0xDEADBEEF + 28))); +} + +TEST_F(BasicFileVerifierTest, FallThroughTest) { + Verifier.parseSectionContents( + { + 0x90, // 0: nop + 0xb0, 0x00, // 1: mov $0x0, %al + 0x2f, // 3: (bad) + 0x0f, 0x0b, // 4: ud2 + 0xff, 0x20, // 6: jmpq *(%rax) + 0xeb, 0x00, // 8: jmp +0 + 0xe8, 0x45, 0xfe, 0xff, 0xff, // 10: callq [some loc] + 0xff, 0x10, // 15: callq *(rax) + 0x75, 0x00, // 17: jne +0 + 0xc3, // 19: retq + }, + 0xDEADBEEF, "Test"); + + EXPECT_TRUE( + Verifier.canFallThrough(Verifier.getInstructionOrDie(0xDEADBEEF))); + EXPECT_TRUE( + Verifier.canFallThrough(Verifier.getInstructionOrDie(0xDEADBEEF + 1))); + EXPECT_FALSE( + Verifier.canFallThrough(Verifier.getInstructionOrDie(0xDEADBEEF + 3))); + EXPECT_FALSE( + Verifier.canFallThrough(Verifier.getInstructionOrDie(0xDEADBEEF + 4))); + EXPECT_FALSE( + Verifier.canFallThrough(Verifier.getInstructionOrDie(0xDEADBEEF + 6))); + EXPECT_FALSE( + Verifier.canFallThrough(Verifier.getInstructionOrDie(0xDEADBEEF + 8))); + EXPECT_FALSE( + Verifier.canFallThrough(Verifier.getInstructionOrDie(0xDEADBEEF + 10))); + EXPECT_FALSE( + Verifier.canFallThrough(Verifier.getInstructionOrDie(0xDEADBEEF + 15))); + EXPECT_TRUE( + Verifier.canFallThrough(Verifier.getInstructionOrDie(0xDEADBEEF + 17))); + EXPECT_FALSE( + Verifier.canFallThrough(Verifier.getInstructionOrDie(0xDEADBEEF + 19))); +} + +TEST_F(BasicFileVerifierTest, DefiniteNextInstructionTest) { + Verifier.parseSectionContents( + { + 0x90, // 0: nop + 0xb0, 0x00, // 1: mov $0x0, %al + 0x2f, // 3: (bad) + 0x0f, 0x0b, // 4: ud2 + 0xff, 0x20, // 6: jmpq *(%rax) + 0xeb, 0x00, // 8: jmp 10 [+0] + 0xeb, 0x05, // 10: jmp 17 [+5] + 0xe8, 0x00, 0x00, 0x00, 0x00, // 12: callq 17 [+0] + 0xe8, 0x78, 0x56, 0x34, 0x12, // 17: callq 0x1234569f [+0x12345678] + 0xe8, 0x04, 0x00, 0x00, 0x00, // 22: callq 31 [+4] + 0xff, 0x10, // 27: callq *(rax) + 0x75, 0x00, // 29: jne 31 [+0] + 0x75, 0xe0, // 31: jne 1 [-32] + 0xc3, // 33: retq + 0xeb, 0xdd, // 34: jmp 1 [-35] + 0xeb, 0xdd, // 36: jmp 3 [-35] + 0xeb, 0xdc, // 38: jmp 4 [-36] + }, + 0xDEADBEEF, "Test"); + + const auto *Current = Verifier.getInstruction(0xDEADBEEF); + const auto *Next = Verifier.getDefiniteNextInstruction(*Current); + EXPECT_NE(nullptr, Next); + EXPECT_EQ(0xDEADBEEF + 1, Next->VMAddress); + + Current = Verifier.getInstruction(0xDEADBEEF + 1); + EXPECT_EQ(nullptr, Verifier.getDefiniteNextInstruction(*Current)); + + Current = Verifier.getInstruction(0xDEADBEEF + 3); + EXPECT_EQ(nullptr, Verifier.getDefiniteNextInstruction(*Current)); + + Current = Verifier.getInstruction(0xDEADBEEF + 4); + EXPECT_EQ(nullptr, Verifier.getDefiniteNextInstruction(*Current)); + + Current = Verifier.getInstruction(0xDEADBEEF + 6); + EXPECT_EQ(nullptr, Verifier.getDefiniteNextInstruction(*Current)); + + Current = Verifier.getInstruction(0xDEADBEEF + 8); + Next = Verifier.getDefiniteNextInstruction(*Current); + EXPECT_NE(nullptr, Next); + EXPECT_EQ(0xDEADBEEF + 10, Next->VMAddress); + + Current = Verifier.getInstruction(0xDEADBEEF + 10); + Next = Verifier.getDefiniteNextInstruction(*Current); + EXPECT_NE(nullptr, Next); + EXPECT_EQ(0xDEADBEEF + 17, Next->VMAddress); + + Current = Verifier.getInstruction(0xDEADBEEF + 12); + Next = Verifier.getDefiniteNextInstruction(*Current); + EXPECT_NE(nullptr, Next); + EXPECT_EQ(0xDEADBEEF + 17, Next->VMAddress); + + Current = Verifier.getInstruction(0xDEADBEEF + 17); + // Note, definite next instruction address is out of range and should fail. + EXPECT_EQ(nullptr, Verifier.getDefiniteNextInstruction(*Current)); + Next = Verifier.getDefiniteNextInstruction(*Current); + + Current = Verifier.getInstruction(0xDEADBEEF + 22); + Next = Verifier.getDefiniteNextInstruction(*Current); + EXPECT_NE(nullptr, Next); + EXPECT_EQ(0xDEADBEEF + 31, Next->VMAddress); + + Current = Verifier.getInstruction(0xDEADBEEF + 27); + EXPECT_EQ(nullptr, Verifier.getDefiniteNextInstruction(*Current)); + Current = Verifier.getInstruction(0xDEADBEEF + 29); + EXPECT_EQ(nullptr, Verifier.getDefiniteNextInstruction(*Current)); + Current = Verifier.getInstruction(0xDEADBEEF + 31); + EXPECT_EQ(nullptr, Verifier.getDefiniteNextInstruction(*Current)); + Current = Verifier.getInstruction(0xDEADBEEF + 33); + EXPECT_EQ(nullptr, Verifier.getDefiniteNextInstruction(*Current)); + + Current = Verifier.getInstruction(0xDEADBEEF + 34); + Next = Verifier.getDefiniteNextInstruction(*Current); + EXPECT_NE(nullptr, Next); + EXPECT_EQ(0xDEADBEEF + 1, Next->VMAddress); + + Current = Verifier.getInstruction(0xDEADBEEF + 36); + Next = Verifier.getDefiniteNextInstruction(*Current); + EXPECT_NE(nullptr, Next); + EXPECT_EQ(0xDEADBEEF + 3, Next->VMAddress); + + Current = Verifier.getInstruction(0xDEADBEEF + 38); + Next = Verifier.getDefiniteNextInstruction(*Current); + EXPECT_NE(nullptr, Next); + EXPECT_EQ(0xDEADBEEF + 4, Next->VMAddress); +} + +TEST_F(BasicFileVerifierTest, ControlFlowXRefsTest) { + Verifier.parseSectionContents( + { + 0x90, // 0: nop + 0xb0, 0x00, // 1: mov $0x0, %al + 0x2f, // 3: (bad) + 0x0f, 0x0b, // 4: ud2 + 0xff, 0x20, // 6: jmpq *(%rax) + 0xeb, 0x00, // 8: jmp 10 [+0] + 0xeb, 0x05, // 10: jmp 17 [+5] + 0xe8, 0x00, 0x00, 0x00, 0x00, // 12: callq 17 [+0] + 0xe8, 0x78, 0x56, 0x34, 0x12, // 17: callq 0x1234569f [+0x12345678] + 0xe8, 0x04, 0x00, 0x00, 0x00, // 22: callq 31 [+4] + 0xff, 0x10, // 27: callq *(rax) + 0x75, 0x00, // 29: jne 31 [+0] + 0x75, 0xe0, // 31: jne 1 [-32] + 0xc3, // 33: retq + 0xeb, 0xdd, // 34: jmp 1 [-35] + 0xeb, 0xdd, // 36: jmp 3 [-35] + 0xeb, 0xdc, // 38: jmp 4 [-36] + }, + 0xDEADBEEF, "Test"); + const auto *InstrMetaPtr = &Verifier.getInstructionOrDie(0xDEADBEEF); + std::set XRefs = Verifier.getControlFlowXRefs(*InstrMetaPtr); + EXPECT_TRUE(XRefs.empty()); + + InstrMetaPtr = &Verifier.getInstructionOrDie(0xDEADBEEF + 1); + XRefs = Verifier.getControlFlowXRefs(*InstrMetaPtr); + EXPECT_THAT(XRefs, UnorderedElementsAre( + Field(&Instr::VMAddress, Eq(0xDEADBEEF)), + Field(&Instr::VMAddress, Eq(0xDEADBEEF + 31)), + Field(&Instr::VMAddress, Eq(0xDEADBEEF + 34)))); + + InstrMetaPtr = &Verifier.getInstructionOrDie(0xDEADBEEF + 3); + XRefs = Verifier.getControlFlowXRefs(*InstrMetaPtr); + EXPECT_THAT(XRefs, UnorderedElementsAre( + Field(&Instr::VMAddress, Eq(0xDEADBEEF + 1)), + Field(&Instr::VMAddress, Eq(0xDEADBEEF + 36)))); + + InstrMetaPtr = &Verifier.getInstructionOrDie(0xDEADBEEF + 4); + XRefs = Verifier.getControlFlowXRefs(*InstrMetaPtr); + EXPECT_THAT(XRefs, UnorderedElementsAre( + Field(&Instr::VMAddress, Eq(0xDEADBEEF + 38)))); + + InstrMetaPtr = &Verifier.getInstructionOrDie(0xDEADBEEF + 6); + EXPECT_TRUE(Verifier.getControlFlowXRefs(*InstrMetaPtr).empty()); + + InstrMetaPtr = &Verifier.getInstructionOrDie(0xDEADBEEF + 8); + XRefs = Verifier.getControlFlowXRefs(*InstrMetaPtr); + EXPECT_TRUE(Verifier.getControlFlowXRefs(*InstrMetaPtr).empty()); + + InstrMetaPtr = &Verifier.getInstructionOrDie(0xDEADBEEF + 10); + XRefs = Verifier.getControlFlowXRefs(*InstrMetaPtr); + EXPECT_THAT(XRefs, UnorderedElementsAre( + Field(&Instr::VMAddress, Eq(0xDEADBEEF + 8)))); + + InstrMetaPtr = &Verifier.getInstructionOrDie(0xDEADBEEF + 12); + XRefs = Verifier.getControlFlowXRefs(*InstrMetaPtr); + EXPECT_TRUE(Verifier.getControlFlowXRefs(*InstrMetaPtr).empty()); + + InstrMetaPtr = &Verifier.getInstructionOrDie(0xDEADBEEF + 17); + XRefs = Verifier.getControlFlowXRefs(*InstrMetaPtr); + EXPECT_THAT(XRefs, UnorderedElementsAre( + Field(&Instr::VMAddress, Eq(0xDEADBEEF + 10)), + Field(&Instr::VMAddress, Eq(0xDEADBEEF + 12)))); + + InstrMetaPtr = &Verifier.getInstructionOrDie(0xDEADBEEF + 22); + XRefs = Verifier.getControlFlowXRefs(*InstrMetaPtr); + EXPECT_TRUE(Verifier.getControlFlowXRefs(*InstrMetaPtr).empty()); + + InstrMetaPtr = &Verifier.getInstructionOrDie(0xDEADBEEF + 27); + XRefs = Verifier.getControlFlowXRefs(*InstrMetaPtr); + EXPECT_TRUE(Verifier.getControlFlowXRefs(*InstrMetaPtr).empty()); + + InstrMetaPtr = &Verifier.getInstructionOrDie(0xDEADBEEF + 29); + XRefs = Verifier.getControlFlowXRefs(*InstrMetaPtr); + EXPECT_TRUE(Verifier.getControlFlowXRefs(*InstrMetaPtr).empty()); + + InstrMetaPtr = &Verifier.getInstructionOrDie(0xDEADBEEF + 31); + XRefs = Verifier.getControlFlowXRefs(*InstrMetaPtr); + EXPECT_THAT(XRefs, UnorderedElementsAre( + Field(&Instr::VMAddress, Eq(0xDEADBEEF + 22)), + Field(&Instr::VMAddress, Eq(0xDEADBEEF + 29)))); + + InstrMetaPtr = &Verifier.getInstructionOrDie(0xDEADBEEF + 33); + XRefs = Verifier.getControlFlowXRefs(*InstrMetaPtr); + EXPECT_THAT(XRefs, UnorderedElementsAre( + Field(&Instr::VMAddress, Eq(0xDEADBEEF + 31)))); + + InstrMetaPtr = &Verifier.getInstructionOrDie(0xDEADBEEF + 34); + XRefs = Verifier.getControlFlowXRefs(*InstrMetaPtr); + EXPECT_TRUE(Verifier.getControlFlowXRefs(*InstrMetaPtr).empty()); + + InstrMetaPtr = &Verifier.getInstructionOrDie(0xDEADBEEF + 36); + XRefs = Verifier.getControlFlowXRefs(*InstrMetaPtr); + EXPECT_TRUE(Verifier.getControlFlowXRefs(*InstrMetaPtr).empty()); + + InstrMetaPtr = &Verifier.getInstructionOrDie(0xDEADBEEF + 38); + XRefs = Verifier.getControlFlowXRefs(*InstrMetaPtr); + EXPECT_TRUE(Verifier.getControlFlowXRefs(*InstrMetaPtr).empty()); +} + +} // anonymous namespace +} // end namespace cfi_verify +} // end namespace llvm + +int main(int argc, char **argv) { + ::testing::InitGoogleTest(&argc, argv); + llvm::cl::ParseCommandLineOptions(argc, argv); + + llvm::InitializeAllTargetInfos(); + llvm::InitializeAllTargetMCs(); + llvm::InitializeAllAsmParsers(); + llvm::InitializeAllDisassemblers(); + + return RUN_ALL_TESTS(); +} Index: tools/llvm-cfi-verify/unittests/GraphBuilder.cpp =================================================================== --- /dev/null +++ tools/llvm-cfi-verify/unittests/GraphBuilder.cpp @@ -0,0 +1,505 @@ +//===- llvm/tools/llvm-cfi-verify/unittests/GraphBuilder.cpp --------------===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// + +#include "../GraphBuilder.h" +#include "../FileVerifier.h" +#include "gmock/gmock.h" +#include "gtest/gtest.h" + +#include "llvm/BinaryFormat/ELF.h" +#include "llvm/MC/MCAsmInfo.h" +#include "llvm/MC/MCContext.h" +#include "llvm/MC/MCDisassembler/MCDisassembler.h" +#include "llvm/MC/MCInst.h" +#include "llvm/MC/MCInstPrinter.h" +#include "llvm/MC/MCInstrAnalysis.h" +#include "llvm/MC/MCInstrDesc.h" +#include "llvm/MC/MCInstrInfo.h" +#include "llvm/MC/MCObjectFileInfo.h" +#include "llvm/MC/MCRegisterInfo.h" +#include "llvm/MC/MCSubtargetInfo.h" +#include "llvm/Object/Binary.h" +#include "llvm/Object/COFF.h" +#include "llvm/Object/ELFObjectFile.h" +#include "llvm/Object/ObjectFile.h" +#include "llvm/Support/Casting.h" +#include "llvm/Support/CommandLine.h" +#include "llvm/Support/Error.h" +#include "llvm/Support/MemoryBuffer.h" +#include "llvm/Support/TargetRegistry.h" +#include "llvm/Support/TargetSelect.h" +#include "llvm/Support/raw_ostream.h" + +#include + +using Instr = ::llvm::cfi_verify::FileVerifier::Instr; +using ::testing::Each; +using ::testing::ElementsAre; +using ::testing::Eq; +using ::testing::Field; +using ::testing::IsEmpty; +using ::testing::ResultOf; +using ::testing::SizeIs; + +namespace llvm { +namespace cfi_verify { +// Custom node printers for gtest. +void PrintControlFlowNode(ControlFlowNode *Node, unsigned depth, + ::std::ostream *os) { + for (unsigned i = 0; i < depth; ++i) + *os << " "; + + if (Node == nullptr) { + *os << "nullptr"; + return; + } + + *os << "[" << Node->FlowLength << "] 0x" << std::hex + << Node->InstructionAddress << std::dec; + if (Node->Next) { + *os << "\n"; + PrintControlFlowNode(Node->Next, depth + 1, os); + } +} + +void PrintTo(ControlFlowNode *Node, ::std::ostream *os) { + *os << "\nControl Flow Node:\n"; + PrintControlFlowNode(Node, 0, os); +} + +void PrintTo(ConditionalBranchNode *Node, ::std::ostream *os) { + *os << "\nConditional Branch Node:\n"; + if (Node == nullptr) { + *os << "nullptr"; + return; + } + + *os << "0x" << std::hex << Node->InstructionAddress << std::dec << "\n"; + *os << " Target:\n"; + if (Node->Target) { + PrintControlFlowNode(Node->Target, 1, os); + *os << "\n"; + } else { + *os << " ???\n"; + } + + *os << " Fallthrough:\n"; + if (Node->Fallthrough) { + PrintControlFlowNode(Node->Fallthrough, 1, os); + } else { + *os << " ???"; + } +} + +namespace { +class ELFx86TestFileVerifier : public FileVerifier { +public: + ELFx86TestFileVerifier() + : FileVerifier(Triple("x86_64--"), SubtargetFeatures()) {} + + // Expose this method publicly for testing. + void parseSectionContents(ArrayRef SectionBytes, + uint64_t SectionAddress, StringRef SectionName) { + FileVerifier::parseSectionContents(SectionBytes, SectionAddress, + SectionName); + } + + Error initialiseDisassemblyMembers() { + return FileVerifier::initialiseDisassemblyMembers(); + } +}; + +class BasicGraphBuilderTest : public ::testing::Test { +protected: + virtual void SetUp() { + if (Verifier.initialiseDisassemblyMembers()) { + exit(EXIT_FAILURE); + } + } + + ELFx86TestFileVerifier Verifier; +}; + +TEST_F(BasicGraphBuilderTest, BuildFlowGraphTestSinglePathFallthroughUd2) { + Verifier.parseSectionContents( + { + 0x75, 0x02, // 0: jne 4 [+2] + 0x0f, 0x0b, // 2: ud2 + 0xff, 0x10, // 4: callq *(%rax) + }, + 0xDEADBEEF, "Test"); + const auto Result = GraphBuilder::buildFlowGraph(Verifier, 0xDEADBEEF + 4); + + EXPECT_THAT(Result.OrphanedNodes, IsEmpty()); + EXPECT_THAT(Result.BranchNodes, SizeIs(1)); + EXPECT_THAT(Result.BranchNodes, + Each(Field(&ConditionalBranchNode::CFIProtection, Eq(true)))); + EXPECT_THAT(Result.BranchNodes, + Contains(AllOf(Field(&ConditionalBranchNode::InstructionAddress, + Eq(0xDEADBEEF)), + Field(&ConditionalBranchNode::Fallthrough, + ResultOf(flattenControlFlowNodeAddresses, + ElementsAre(0xDEADBEEF + 2))), + Field(&ConditionalBranchNode::Target, + ResultOf(flattenControlFlowNodeAddresses, + ElementsAre(0xDEADBEEF + 4)))))); +} + +TEST_F(BasicGraphBuilderTest, BuildFlowGraphTestSinglePathJumpUd2) { + Verifier.parseSectionContents( + { + 0x75, 0x02, // 0: jne 4 [+2] + 0xff, 0x10, // 2: callq *(%rax) + 0x0f, 0x0b, // 4: ud2 + }, + 0xDEADBEEF, "Test"); + const auto Result = GraphBuilder::buildFlowGraph(Verifier, 0xDEADBEEF + 2); + + EXPECT_THAT(Result.OrphanedNodes, IsEmpty()); + EXPECT_THAT(Result.BranchNodes, SizeIs(1)); + EXPECT_THAT(Result.BranchNodes, + Each(Field(&ConditionalBranchNode::CFIProtection, Eq(true)))); + EXPECT_THAT(Result.BranchNodes, + Contains(AllOf(Field(&ConditionalBranchNode::InstructionAddress, + Eq(0xDEADBEEF)), + Field(&ConditionalBranchNode::Fallthrough, + ResultOf(flattenControlFlowNodeAddresses, + ElementsAre(0xDEADBEEF + 2))), + Field(&ConditionalBranchNode::Target, + ResultOf(flattenControlFlowNodeAddresses, + ElementsAre(0xDEADBEEF + 4)))))); +} + +TEST_F(BasicGraphBuilderTest, BuildFlowGraphTestDualPathDualUd2) { + Verifier.parseSectionContents( + { + 0x75, 0x03, // 0: jne 5 [+3] + 0x90, // 2: nop + 0xff, 0x10, // 3: callq *(%rax) + 0x0f, 0x0b, // 5: ud2 + 0x75, 0xf9, // 7: jne 2 [-7] + 0x0f, 0x0b, // 9: ud2 + }, + 0xDEADBEEF, "Test"); + const auto Result = GraphBuilder::buildFlowGraph(Verifier, 0xDEADBEEF + 3); + + EXPECT_THAT(Result.OrphanedNodes, IsEmpty()); + EXPECT_THAT(Result.BranchNodes, SizeIs(2)); + EXPECT_THAT(Result.BranchNodes, + Each(Field(&ConditionalBranchNode::CFIProtection, Eq(true)))); + EXPECT_THAT( + Result.BranchNodes, + Contains(AllOf( + Field(&ConditionalBranchNode::InstructionAddress, Eq(0xDEADBEEF)), + Field(&ConditionalBranchNode::Fallthrough, + ResultOf(flattenControlFlowNodeAddresses, + ElementsAre(0xDEADBEEF + 2, 0xDEADBEEF + 3))), + Field(&ConditionalBranchNode::Target, + ResultOf(flattenControlFlowNodeAddresses, + ElementsAre(0xDEADBEEF + 5)))))); + EXPECT_THAT( + Result.BranchNodes, + Contains(AllOf( + Field(&ConditionalBranchNode::InstructionAddress, Eq(0xDEADBEEF + 7)), + Field(&ConditionalBranchNode::Fallthrough, + ResultOf(flattenControlFlowNodeAddresses, + ElementsAre(0xDEADBEEF + 9))), + Field(&ConditionalBranchNode::Target, + ResultOf(flattenControlFlowNodeAddresses, + ElementsAre(0xDEADBEEF + 2, 0xDEADBEEF + 3)))))); +} + +TEST_F(BasicGraphBuilderTest, BuildFlowGraphTestDualPathSingleUd2) { + Verifier.parseSectionContents( + { + 0x75, 0x05, // 0: jne 7 [+5] + 0x90, // 2: nop + 0xff, 0x10, // 3: callq *(%rax) + 0x75, 0xfb, // 5: jne 2 [-5] + 0x0f, 0x0b, // 7: ud2 + }, + 0xDEADBEEF, "Test"); + GraphResult Result = GraphBuilder::buildFlowGraph(Verifier, 0xDEADBEEF + 3); + + EXPECT_THAT(Result.OrphanedNodes, IsEmpty()); + EXPECT_THAT(Result.BranchNodes, SizeIs(2)); + EXPECT_THAT(Result.BranchNodes, + Each(Field(&ConditionalBranchNode::CFIProtection, Eq(true)))); + EXPECT_THAT( + Result.BranchNodes, + Contains(AllOf( + Field(&ConditionalBranchNode::InstructionAddress, Eq(0xDEADBEEF)), + Field(&ConditionalBranchNode::Fallthrough, + ResultOf(flattenControlFlowNodeAddresses, + ElementsAre(0xDEADBEEF + 2, 0xDEADBEEF + 3))), + Field(&ConditionalBranchNode::Target, + ResultOf(flattenControlFlowNodeAddresses, + ElementsAre(0xDEADBEEF + 7)))))); + EXPECT_THAT( + Result.BranchNodes, + Contains(AllOf( + Field(&ConditionalBranchNode::InstructionAddress, Eq(0xDEADBEEF + 5)), + Field(&ConditionalBranchNode::Fallthrough, + ResultOf(flattenControlFlowNodeAddresses, + ElementsAre(0xDEADBEEF + 7))), + Field(&ConditionalBranchNode::Target, + ResultOf(flattenControlFlowNodeAddresses, + ElementsAre(0xDEADBEEF + 2, 0xDEADBEEF + 3)))))); +} + +TEST_F(BasicGraphBuilderTest, BuildFlowGraphFailures) { + Verifier.parseSectionContents( + { + 0x90, // 0: nop + 0x75, 0xfe, // 1: jne 1 [-2] + }, + 0xDEADBEEF, "Test"); + GraphResult Result = GraphBuilder::buildFlowGraph(Verifier, 0xDEADBEEF); + EXPECT_THAT(Result.OrphanedNodes, IsEmpty()); + EXPECT_THAT(Result.BranchNodes, IsEmpty()); + + Result = GraphBuilder::buildFlowGraph(Verifier, 0xDEADBEEF + 1); + EXPECT_THAT(Result.OrphanedNodes, IsEmpty()); + EXPECT_THAT(Result.BranchNodes, IsEmpty()); + + Result = GraphBuilder::buildFlowGraph(Verifier, 0xDEADC0DE); + EXPECT_THAT(Result.OrphanedNodes, IsEmpty()); + EXPECT_THAT(Result.BranchNodes, IsEmpty()); +} + +TEST_F(BasicGraphBuilderTest, BuildFlowGraphNoXrefs) { + Verifier.parseSectionContents( + { + 0xeb, 0xfe, // 0: jmp 0 [-2] + 0xff, 0x10, // 2: callq *(%rax) + }, + 0xDEADBEEF, "Test"); + GraphResult Result = GraphBuilder::buildFlowGraph(Verifier, 0xDEADBEEF + 2); + EXPECT_THAT(Result.OrphanedNodes, SizeIs(1)); + EXPECT_THAT(Result.BranchNodes, IsEmpty()); + EXPECT_THAT(Result.OrphanedNodes, + Contains(AllOf(Field(&ControlFlowNode::InstructionAddress, + Eq(0xDEADBEEF + 2)), + Field(&ControlFlowNode::Next, Eq(nullptr))))); +} + +TEST_F(BasicGraphBuilderTest, BuildFlowGraphConditionalInfiniteLoop) { + Verifier.parseSectionContents( + { + 0x75, 0xfe, // 0: jne 0 [-2] + 0xff, 0x10, // 2: callq *(%rax) + }, + 0xDEADBEEF, "Test"); + GraphResult Result = GraphBuilder::buildFlowGraph(Verifier, 0xDEADBEEF + 2); + EXPECT_THAT(Result.OrphanedNodes, IsEmpty()); + EXPECT_THAT(Result.BranchNodes, SizeIs(1)); + EXPECT_THAT( + Result.BranchNodes, + Each(AllOf(Field(&ConditionalBranchNode::CFIProtection, Eq(false)), + Field(&ConditionalBranchNode::Target, + ResultOf(flattenControlFlowNodeAddresses, + ElementsAre(0xDEADBEEF))), + Field(&ConditionalBranchNode::Fallthrough, + ResultOf(flattenControlFlowNodeAddresses, + ElementsAre(0xDEADBEEF + 2)))))); +} + +TEST_F(BasicGraphBuilderTest, BuildFlowGraphUnconditionalInfiniteLoop) { + Verifier.parseSectionContents( + { + 0x75, 0x02, // 0: jne 4 [+2] + 0xeb, 0xfc, // 2: jmp 0 [-4] + 0xff, 0x10, // 4: callq *(%rax) + }, + 0xDEADBEEF, "Test"); + GraphResult Result = GraphBuilder::buildFlowGraph(Verifier, 0xDEADBEEF + 4); + EXPECT_THAT(Result.OrphanedNodes, IsEmpty()); + EXPECT_THAT(Result.BranchNodes, SizeIs(1)); + EXPECT_THAT( + Result.BranchNodes, + Contains(AllOf( + Field(&ConditionalBranchNode::InstructionAddress, Eq(0xDEADBEEF)), + Field(&ConditionalBranchNode::Fallthrough, + ResultOf(flattenControlFlowNodeAddresses, + ElementsAre(0xDEADBEEF + 2, 0xDEADBEEF))), + Field(&ConditionalBranchNode::Target, + ResultOf(flattenControlFlowNodeAddresses, + ElementsAre(0xDEADBEEF + 4)))))); +} + +TEST_F(BasicGraphBuilderTest, BuildFlowGraphNoFlowsToIndirection) { + Verifier.parseSectionContents( + { + 0x75, 0x00, // 0: jne 2 [+0] + 0xeb, 0xfc, // 2: jmp 0 [-4] + 0xff, 0x10, // 4: callq *(%rax) + }, + 0xDEADBEEF, "Test"); + GraphResult Result = GraphBuilder::buildFlowGraph(Verifier, 0xDEADBEEF + 4); + EXPECT_THAT(Result.OrphanedNodes, SizeIs(1)); + EXPECT_THAT(Result.OrphanedNodes, + Contains(AllOf(Field(&ControlFlowNode::InstructionAddress, + Eq(0xDEADBEEF + 4)), + Field(&ControlFlowNode::Next, Eq(nullptr))))); + EXPECT_THAT(Result.BranchNodes, IsEmpty()); +} + +TEST_F(BasicGraphBuilderTest, BuildFlowGraphLengthExceededUpwards) { + Verifier.parseSectionContents( + { + 0x75, 0x06, // 0: jne 8 [+6] + 0x90, // 2: nop + 0x90, // 3: nop + 0x90, // 4: nop + 0x90, // 5: nop + 0xff, 0x10, // 6: callq *(%rax) + 0x0f, 0x0b, // 8: ud2 + }, + 0xDEADBEEF, "Test"); + uint64_t PrevSearchLengthForConditionalBranch = + SearchLengthForConditionalBranch; + SearchLengthForConditionalBranch = 2; + + GraphResult Result = GraphBuilder::buildFlowGraph(Verifier, 0xDEADBEEF + 6); + EXPECT_THAT(Result.OrphanedNodes, SizeIs(1)); + EXPECT_THAT(Result.OrphanedNodes, + Each(ResultOf(flattenControlFlowNodeAddresses, + ElementsAre(0xDEADBEEF + 4, 0xDEADBEEF + 5, + 0xDEADBEEF + 6)))); + EXPECT_THAT(Result.BranchNodes, IsEmpty()); + + SearchLengthForConditionalBranch = PrevSearchLengthForConditionalBranch; +} + +TEST_F(BasicGraphBuilderTest, BuildFlowGraphLengthExceededDownwards) { + Verifier.parseSectionContents( + { + 0x75, 0x02, // 0: jne 4 [+2] + 0xff, 0x10, // 2: callq *(%rax) + 0x90, // 4: nop + 0x90, // 5: nop + 0x90, // 6: nop + 0x90, // 7: nop + 0x0f, 0x0b, // 8: ud2 + }, + 0xDEADBEEF, "Test"); + uint64_t PrevSearchLengthForUndef = SearchLengthForUndef; + SearchLengthForUndef = 2; + + GraphResult Result = GraphBuilder::buildFlowGraph(Verifier, 0xDEADBEEF + 2); + EXPECT_THAT(Result.OrphanedNodes, IsEmpty()); + EXPECT_THAT( + Result.BranchNodes, + Each(AllOf( + Field(&ConditionalBranchNode::CFIProtection, Eq(false)), + Field(&ConditionalBranchNode::InstructionAddress, Eq(0xDEADBEEF)), + Field(&ConditionalBranchNode::Target, + ResultOf(flattenControlFlowNodeAddresses, + ElementsAre(0xDEADBEEF + 4, 0xDEADBEEF + 5))), + Field(&ConditionalBranchNode::Fallthrough, + ResultOf(flattenControlFlowNodeAddresses, + ElementsAre(0xDEADBEEF + 2)))))); + + SearchLengthForUndef = PrevSearchLengthForUndef; +} + +TEST_F(BasicGraphBuilderTest, BuildFlowGraphComplexExample) { + // The following code has this graph (in DOT format): + // digraph G { + // "0" -> "20" + // "0" -> "2" + // "20" -> "21" + // "4" -> "22 (ud2)" + // "21" -> "22 (ud2)" + // "4" -> "6" + // "6" -> "7" + // "2" -> "7" + // "7" -> "8" + // "8" -> "9 (indirect)" + // "13" -> "15 (error)" + // "13" -> "9 (indirect)" + // "11" -> "9 (indirect)" + // } + // Or, in image format: https://i.imgur.com/aX5fCoi.png + + Verifier.parseSectionContents( + { + 0x75, 0x12, // 0: jne 20 [+18] + 0xeb, 0x03, // 2: jmp 7 [+3] + 0x75, 0x10, // 4: jne 22 [+16] + 0x90, // 6: nop + 0x90, // 7: nop + 0x90, // 8: nop + 0xff, 0x10, // 9: callq *(%rax) + 0xeb, 0xfc, // 11: jmp 9 [-4] + 0x75, 0xfa, // 13: jne 9 [-6] + 0xe8, 0x78, 0x56, 0x34, 0x12, // 15: callq OUTOFBOUNDS [+0x12345678] + 0x90, // 20: nop + 0x90, // 21: nop + 0x0f, 0x0b, // 22: ud2 + }, + 0x1000, "Test"); + uint64_t PrevSearchLengthForUndef = SearchLengthForUndef; + SearchLengthForUndef = 5; + + GraphResult Result = GraphBuilder::buildFlowGraph(Verifier, 0x1000 + 9); + + EXPECT_THAT(Result.OrphanedNodes, SizeIs(1)); + EXPECT_THAT(Result.BranchNodes, SizeIs(3)); + + EXPECT_THAT( + Result.OrphanedNodes, + Each(AllOf(Field(&ControlFlowNode::InstructionAddress, Eq(0x1000 + 11)), + ResultOf(flattenControlFlowNodeAddresses, + ElementsAre(0x1000 + 11, 0x1000 + 9))))); + + EXPECT_THAT( + Result.BranchNodes, + Contains(AllOf( + Field(&ConditionalBranchNode::CFIProtection, Eq(true)), + Field(&ConditionalBranchNode::InstructionAddress, Eq(0x1000)), + Field(&ConditionalBranchNode::Target, + ResultOf(flattenControlFlowNodeAddresses, + ElementsAre(0x1000 + 20, 0x1000 + 21, 0x1000 + 22))), + Field(&ConditionalBranchNode::Fallthrough, + ResultOf(flattenControlFlowNodeAddresses, + ElementsAre(0x1000 + 2, 0x1000 + 7, 0x1000 + 8, + 0x1000 + 9)))))); + + EXPECT_THAT( + Result.BranchNodes, + Contains(AllOf( + Field(&ConditionalBranchNode::CFIProtection, Eq(true)), + Field(&ConditionalBranchNode::InstructionAddress, Eq(0x1000 + 4)), + Field(&ConditionalBranchNode::Target, + ResultOf(flattenControlFlowNodeAddresses, + ElementsAre(0x1000 + 22))), + Field(&ConditionalBranchNode::Fallthrough, + ResultOf(flattenControlFlowNodeAddresses, + ElementsAre(0x1000 + 6, 0x1000 + 7, 0x1000 + 8, + 0x1000 + 9)))))); + + EXPECT_THAT( + Result.BranchNodes, + Contains(AllOf( + Field(&ConditionalBranchNode::CFIProtection, Eq(false)), + Field(&ConditionalBranchNode::InstructionAddress, Eq(0x1000 + 13)), + Field(&ConditionalBranchNode::Target, + ResultOf(flattenControlFlowNodeAddresses, + ElementsAre(0x1000 + 9))), + Field(&ConditionalBranchNode::Fallthrough, + ResultOf(flattenControlFlowNodeAddresses, + ElementsAre(0x1000 + 15)))))); + + SearchLengthForUndef = PrevSearchLengthForUndef; +} + +} // anonymous namespace +} // end namespace cfi_verify +} // end namespace llvm Index: unittests/CMakeLists.txt =================================================================== --- unittests/CMakeLists.txt +++ unittests/CMakeLists.txt @@ -27,3 +27,4 @@ add_subdirectory(Target) add_subdirectory(Transforms) add_subdirectory(XRay) +add_subdirectory(../tools/llvm-cfi-verify/unittests ../tools/llvm-cfi-verify/unittests)