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

   1 //===- FileAnalysis.cpp -----------------------------------------*- C++ -*-===//
   2 //
   3 //                      The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9
  10 #include "FileAnalysis.h"
  11
  12 #include "llvm/BinaryFormat/ELF.h"
  13 #include "llvm/MC/MCAsmInfo.h"
  14 #include "llvm/MC/MCContext.h"
  15 #include "llvm/MC/MCDisassembler/MCDisassembler.h"
  16 #include "llvm/MC/MCInst.h"
  17 #include "llvm/MC/MCInstPrinter.h"
  18 #include "llvm/MC/MCInstrAnalysis.h"
  19 #include "llvm/MC/MCInstrDesc.h"
  20 #include "llvm/MC/MCInstrInfo.h"
  21 #include "llvm/MC/MCObjectFileInfo.h"
  22 #include "llvm/MC/MCRegisterInfo.h"
  23 #include "llvm/MC/MCSubtargetInfo.h"
  24 #include "llvm/Object/Binary.h"
  25 #include "llvm/Object/COFF.h"
  26 #include "llvm/Object/ELFObjectFile.h"
  27 #include "llvm/Object/ObjectFile.h"
  28 #include "llvm/Support/Casting.h"
  29 #include "llvm/Support/CommandLine.h"
  30 #include "llvm/Support/Error.h"
  31 #include "llvm/Support/FormatVariadic.h"
  32 #include "llvm/Support/MemoryBuffer.h"
  33 #include "llvm/Support/TargetRegistry.h"
  34 #include "llvm/Support/TargetSelect.h"
  35 #include "llvm/Support/raw_ostream.h"
  36
  37 #include <functional>
  38
  39 using Instr = llvm::cfi_verify::FileAnalysis::Instr;
  40
  41 namespace llvm {
  42 namespace cfi_verify {
  43
  44 Expected<FileAnalysis> FileAnalysis::Create(StringRef Filename) {
  45   // Open the filename provided.
  46   Expected<object::OwningBinary<object::Binary>> BinaryOrErr =
  47       object::createBinary(Filename);
  48   if (!BinaryOrErr)
  49     return BinaryOrErr.takeError();
  50
  51   // Construct the object and allow it to take ownership of the binary.
  52   object::OwningBinary<object::Binary> Binary = std::move(BinaryOrErr.get());
  53   FileAnalysis Analysis(std::move(Binary));
  54
  55   Analysis.Object = dyn_cast<object::ObjectFile>(Analysis.Binary.getBinary());
  56   if (!Analysis.Object)
  57     return make_error<UnsupportedDisassembly>("Failed to cast object");
  58
  59   Analysis.ObjectTriple = Analysis.Object->makeTriple();
  60   Analysis.Features = Analysis.Object->getFeatures();
  61
  62   // Init the rest of the object.
  63   if (auto InitResponse = Analysis.initialiseDisassemblyMembers())
  64     return std::move(InitResponse);
  65
  66   if (auto SectionParseResponse = Analysis.parseCodeSections())
  67     return std::move(SectionParseResponse);
  68
  69   return std::move(Analysis);
  70 }
  71
  72 FileAnalysis::FileAnalysis(object::OwningBinary<object::Binary> Binary)
  73     : Binary(std::move(Binary)) {}
  74
  75 FileAnalysis::FileAnalysis(const Triple &ObjectTriple,
  76                            const SubtargetFeatures &Features)
  77     : ObjectTriple(ObjectTriple), Features(Features) {}
  78
  79 const Instr *
  80 FileAnalysis::getPrevInstructionSequential(const Instr &InstrMeta) const {
  81   std::map<uint64_t, Instr>::const_iterator KV =
  82       Instructions.find(InstrMeta.VMAddress);
  83   if (KV == Instructions.end() || KV == Instructions.begin())
  84     return nullptr;
  85
  86   if (!(--KV)->second.Valid)
  87     return nullptr;
  88
  89   return &KV->second;
  90 }
  91
  92 const Instr *
  93 FileAnalysis::getNextInstructionSequential(const Instr &InstrMeta) const {
  94   std::map<uint64_t, Instr>::const_iterator KV =
  95       Instructions.find(InstrMeta.VMAddress);
  96   if (KV == Instructions.end() || ++KV == Instructions.end())
  97     return nullptr;
  98
  99   if (!KV->second.Valid)
 100     return nullptr;
 101
 102   return &KV->second;
 103 }
 104
 105 bool FileAnalysis::usesRegisterOperand(const Instr &InstrMeta) const {
 106   for (const auto &Operand : InstrMeta.Instruction) {
 107     if (Operand.isReg())
 108       return true;
 109   }
 110   return false;
 111 }
 112
 113 const Instr *FileAnalysis::getInstruction(uint64_t Address) const {
 114   const auto &InstrKV = Instructions.find(Address);
 115   if (InstrKV == Instructions.end())
 116     return nullptr;
 117
 118   return &InstrKV->second;
 119 }
 120
 121 const Instr &FileAnalysis::getInstructionOrDie(uint64_t Address) const {
 122   const auto &InstrKV = Instructions.find(Address);
 123   assert(InstrKV != Instructions.end() && "Address doesn't exist.");
 124   return InstrKV->second;
 125 }
 126
 127 bool FileAnalysis::isCFITrap(const Instr &InstrMeta) const {
 128   return MII->getName(InstrMeta.Instruction.getOpcode()) == "TRAP";
 129 }
 130
 131 bool FileAnalysis::canFallThrough(const Instr &InstrMeta) const {
 132   if (!InstrMeta.Valid)
 133     return false;
 134
 135   if (isCFITrap(InstrMeta))
 136     return false;
 137
 138   const auto &InstrDesc = MII->get(InstrMeta.Instruction.getOpcode());
 139   if (InstrDesc.mayAffectControlFlow(InstrMeta.Instruction, *RegisterInfo))
 140     return InstrDesc.isConditionalBranch();
 141
 142   return true;
 143 }
 144
 145 const Instr *
 146 FileAnalysis::getDefiniteNextInstruction(const Instr &InstrMeta) const {
 147   if (!InstrMeta.Valid)
 148     return nullptr;
 149
 150   if (isCFITrap(InstrMeta))
 151     return nullptr;
 152
 153   const auto &InstrDesc = MII->get(InstrMeta.Instruction.getOpcode());
 154   const Instr *NextMetaPtr;
 155   if (InstrDesc.mayAffectControlFlow(InstrMeta.Instruction, *RegisterInfo)) {
 156     if (InstrDesc.isConditionalBranch())
 157       return nullptr;
 158
 159     uint64_t Target;
 160     if (!MIA->evaluateBranch(InstrMeta.Instruction, InstrMeta.VMAddress,
 161                              InstrMeta.InstructionSize, Target))
 162       return nullptr;
 163
 164     NextMetaPtr = getInstruction(Target);
 165   } else {
 166     NextMetaPtr =
 167         getInstruction(InstrMeta.VMAddress + InstrMeta.InstructionSize);
 168   }
 169
 170   if (!NextMetaPtr || !NextMetaPtr->Valid)
 171     return nullptr;
 172
 173   return NextMetaPtr;
 174 }
 175
 176 std::set<const Instr *>
 177 FileAnalysis::getDirectControlFlowXRefs(const Instr &InstrMeta) const {
 178   std::set<const Instr *> CFCrossReferences;
 179   const Instr *PrevInstruction = getPrevInstructionSequential(InstrMeta);
 180
 181   if (PrevInstruction && canFallThrough(*PrevInstruction))
 182     CFCrossReferences.insert(PrevInstruction);
 183
 184   const auto &TargetRefsKV = StaticBranchTargetings.find(InstrMeta.VMAddress);
 185   if (TargetRefsKV == StaticBranchTargetings.end())
 186     return CFCrossReferences;
 187
 188   for (uint64_t SourceInstrAddress : TargetRefsKV->second) {
 189     const auto &SourceInstrKV = Instructions.find(SourceInstrAddress);
 190     if (SourceInstrKV == Instructions.end()) {
 191       errs() << "Failed to find source instruction at address "
 192              << format_hex(SourceInstrAddress, 2)
 193              << " for the cross-reference to instruction at address "
 194              << format_hex(InstrMeta.VMAddress, 2) << ".\n";
 195       continue;
 196     }
 197
 198     CFCrossReferences.insert(&SourceInstrKV->second);
 199   }
 200
 201   return CFCrossReferences;
 202 }
 203
 204 const std::set<uint64_t> &FileAnalysis::getIndirectInstructions() const {
 205   return IndirectInstructions;
 206 }
 207
 208 const MCRegisterInfo *FileAnalysis::getRegisterInfo() const {
 209   return RegisterInfo.get();
 210 }
 211
 212 const MCInstrInfo *FileAnalysis::getMCInstrInfo() const { return MII.get(); }
 213
 214 const MCInstrAnalysis *FileAnalysis::getMCInstrAnalysis() const {
 215   return MIA.get();
 216 }
 217
 218 Error FileAnalysis::initialiseDisassemblyMembers() {
 219   std::string TripleName = ObjectTriple.getTriple();
 220   ArchName = "";
 221   MCPU = "";
 222   std::string ErrorString;
 223
 224   ObjectTarget =
 225       TargetRegistry::lookupTarget(ArchName, ObjectTriple, ErrorString);
 226   if (!ObjectTarget)
 227     return make_error<UnsupportedDisassembly>(
 228         (Twine("Couldn't find target \"") + ObjectTriple.getTriple() +
 229         "\", failed with error: " + ErrorString).str());
 230
 231   RegisterInfo.reset(ObjectTarget->createMCRegInfo(TripleName));
 232   if (!RegisterInfo)
 233     return make_error<UnsupportedDisassembly>(
 234         "Failed to initialise RegisterInfo.");
 235
 236   AsmInfo.reset(ObjectTarget->createMCAsmInfo(*RegisterInfo, TripleName));
 237   if (!AsmInfo)
 238     return make_error<UnsupportedDisassembly>("Failed to initialise AsmInfo.");
 239
 240   SubtargetInfo.reset(ObjectTarget->createMCSubtargetInfo(
 241       TripleName, MCPU, Features.getString()));
 242   if (!SubtargetInfo)
 243     return make_error<UnsupportedDisassembly>(
 244         "Failed to initialise SubtargetInfo.");
 245
 246   MII.reset(ObjectTarget->createMCInstrInfo());
 247   if (!MII)
 248     return make_error<UnsupportedDisassembly>("Failed to initialise MII.");
 249
 250   Context.reset(new MCContext(AsmInfo.get(), RegisterInfo.get(), &MOFI));
 251
 252   Disassembler.reset(
 253       ObjectTarget->createMCDisassembler(*SubtargetInfo, *Context));
 254
 255   if (!Disassembler)
 256     return make_error<UnsupportedDisassembly>(
 257         "No disassembler available for target");
 258
 259   MIA.reset(ObjectTarget->createMCInstrAnalysis(MII.get()));
 260
 261   Printer.reset(ObjectTarget->createMCInstPrinter(
 262       ObjectTriple, AsmInfo->getAssemblerDialect(), *AsmInfo, *MII,
 263       *RegisterInfo));
 264
 265   return Error::success();
 266 }
 267
 268 Error FileAnalysis::parseCodeSections() {
 269   for (const object::SectionRef &Section : Object->sections()) {
 270     // Ensure only executable sections get analysed.
 271     if (!(object::ELFSectionRef(Section).getFlags() & ELF::SHF_EXECINSTR))
 272       continue;
 273
 274     StringRef SectionContents;
 275     if (Section.getContents(SectionContents))
 276       return make_error<StringError>("Failed to retrieve section contents",
 277                                      inconvertibleErrorCode());
 278
 279     ArrayRef<uint8_t> SectionBytes((const uint8_t *)SectionContents.data(),
 280                                    Section.getSize());
 281     parseSectionContents(SectionBytes, Section.getAddress());
 282   }
 283   return Error::success();
 284 }
 285
 286 void FileAnalysis::parseSectionContents(ArrayRef<uint8_t> SectionBytes,
 287                                         uint64_t SectionAddress) {
 288   MCInst Instruction;
 289   Instr InstrMeta;
 290   uint64_t InstructionSize;
 291
 292   for (uint64_t Byte = 0; Byte < SectionBytes.size();) {
 293     bool ValidInstruction =
 294         Disassembler->getInstruction(Instruction, InstructionSize,
 295                                      SectionBytes.drop_front(Byte), 0, nulls(),
 296                                      outs()) == MCDisassembler::Success;
 297
 298     Byte += InstructionSize;
 299
 300     uint64_t VMAddress = SectionAddress + Byte - InstructionSize;
 301     InstrMeta.Instruction = Instruction;
 302     InstrMeta.VMAddress = VMAddress;
 303     InstrMeta.InstructionSize = InstructionSize;
 304     InstrMeta.Valid = ValidInstruction;
 305     addInstruction(InstrMeta);
 306
 307     if (!ValidInstruction)
 308       continue;
 309
 310     // Skip additional parsing for instructions that do not affect the control
 311     // flow.
 312     const auto &InstrDesc = MII->get(Instruction.getOpcode());
 313     if (!InstrDesc.mayAffectControlFlow(Instruction, *RegisterInfo))
 314       continue;
 315
 316     uint64_t Target;
 317     if (MIA->evaluateBranch(Instruction, VMAddress, InstructionSize, Target)) {
 318       // If the target can be evaluated, it's not indirect.
 319       StaticBranchTargetings[Target].push_back(VMAddress);
 320       continue;
 321     }
 322
 323     if (!usesRegisterOperand(InstrMeta))
 324       continue;
 325
 326     IndirectInstructions.insert(VMAddress);
 327   }
 328 }
 329
 330 void FileAnalysis::addInstruction(const Instr &Instruction) {
 331   const auto &KV =
 332       Instructions.insert(std::make_pair(Instruction.VMAddress, Instruction));
 333   if (!KV.second) {
 334     errs() << "Failed to add instruction at address "
 335            << format_hex(Instruction.VMAddress, 2)
 336            << ": Instruction at this address already exists.\n";
 337     exit(EXIT_FAILURE);
 338   }
 339 }
 340
 341 UnsupportedDisassembly::UnsupportedDisassembly(StringRef Text) : Text(Text) {}
 342
 343 char UnsupportedDisassembly::ID;
 344 void UnsupportedDisassembly::log(raw_ostream &OS) const {
 345   OS << "Could not initialise disassembler: " << Text;
 346 }
 347
 348 std::error_code UnsupportedDisassembly::convertToErrorCode() const {
 349   return std::error_code();
 350 }
 351
 352 } // namespace cfi_verify
 353 } // namespace llvm