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 #include "GraphBuilder.h"
12 
13 #include "llvm/BinaryFormat/ELF.h"
14 #include "llvm/DebugInfo/DWARF/DWARFContext.h"
15 #include "llvm/MC/MCAsmInfo.h"
16 #include "llvm/MC/MCContext.h"
17 #include "llvm/MC/MCDisassembler/MCDisassembler.h"
18 #include "llvm/MC/MCInst.h"
19 #include "llvm/MC/MCInstPrinter.h"
20 #include "llvm/MC/MCInstrAnalysis.h"
21 #include "llvm/MC/MCInstrDesc.h"
22 #include "llvm/MC/MCInstrInfo.h"
23 #include "llvm/MC/MCObjectFileInfo.h"
24 #include "llvm/MC/MCRegisterInfo.h"
25 #include "llvm/MC/MCSubtargetInfo.h"
26 #include "llvm/Object/Binary.h"
27 #include "llvm/Object/COFF.h"
28 #include "llvm/Object/ELFObjectFile.h"
29 #include "llvm/Object/ObjectFile.h"
30 #include "llvm/Support/Casting.h"
31 #include "llvm/Support/CommandLine.h"
32 #include "llvm/Support/Error.h"
33 #include "llvm/Support/FormatVariadic.h"
34 #include "llvm/Support/MemoryBuffer.h"
35 #include "llvm/Support/TargetRegistry.h"
36 #include "llvm/Support/TargetSelect.h"
37 #include "llvm/Support/raw_ostream.h"
38 
39 #include <functional>
40 
41 using Instr = llvm::cfi_verify::FileAnalysis::Instr;
42 
43 namespace llvm {
44 namespace cfi_verify {
45 
46 static cl::opt<bool> IgnoreDWARF(
47     "ignore-dwarf",
48     cl::desc(
49         "Ignore all DWARF data. This relaxes the requirements for all "
50         "statically linked libraries to have been compiled with '-g', but "
51         "will result in false positives for 'CFI unprotected' instructions."),
52     cl::init(false));
53 
54 cl::opt<unsigned long long> DWARFSearchRange(
55     "dwarf-search-range",
56     cl::desc("Address search range used to determine if instruction is valid."),
57     cl::init(0x10));
58 
59 Expected<FileAnalysis> FileAnalysis::Create(StringRef Filename) {
60   // Open the filename provided.
61   Expected<object::OwningBinary<object::Binary>> BinaryOrErr =
62       object::createBinary(Filename);
63   if (!BinaryOrErr)
64     return BinaryOrErr.takeError();
65 
66   // Construct the object and allow it to take ownership of the binary.
67   object::OwningBinary<object::Binary> Binary = std::move(BinaryOrErr.get());
68   FileAnalysis Analysis(std::move(Binary));
69 
70   Analysis.Object = dyn_cast<object::ObjectFile>(Analysis.Binary.getBinary());
71   if (!Analysis.Object)
72     return make_error<UnsupportedDisassembly>("Failed to cast object");
73 
74   Analysis.ObjectTriple = Analysis.Object->makeTriple();
75   Analysis.Features = Analysis.Object->getFeatures();
76 
77   // Init the rest of the object.
78   if (auto InitResponse = Analysis.initialiseDisassemblyMembers())
79     return std::move(InitResponse);
80 
81   if (auto SectionParseResponse = Analysis.parseCodeSections())
82     return std::move(SectionParseResponse);
83 
84   return std::move(Analysis);
85 }
86 
87 FileAnalysis::FileAnalysis(object::OwningBinary<object::Binary> Binary)
88     : Binary(std::move(Binary)) {}
89 
90 FileAnalysis::FileAnalysis(const Triple &ObjectTriple,
91                            const SubtargetFeatures &Features)
92     : ObjectTriple(ObjectTriple), Features(Features) {}
93 
94 bool FileAnalysis::isIndirectInstructionCFIProtected(uint64_t Address) const {
95   const Instr *InstrMetaPtr = getInstruction(Address);
96   if (!InstrMetaPtr)
97     return false;
98 
99   const auto &InstrDesc = MII->get(InstrMetaPtr->Instruction.getOpcode());
100 
101   if (!InstrDesc.mayAffectControlFlow(InstrMetaPtr->Instruction, *RegisterInfo))
102     return false;
103 
104   if (!usesRegisterOperand(*InstrMetaPtr))
105     return false;
106 
107   auto Flows = GraphBuilder::buildFlowGraph(*this, Address);
108 
109   if (!Flows.OrphanedNodes.empty())
110     return false;
111 
112   for (const auto &BranchNode : Flows.ConditionalBranchNodes) {
113     if (!BranchNode.CFIProtection)
114       return false;
115   }
116 
117   return true;
118 }
119 
120 const Instr *
121 FileAnalysis::getPrevInstructionSequential(const Instr &InstrMeta) const {
122   std::map<uint64_t, Instr>::const_iterator KV =
123       Instructions.find(InstrMeta.VMAddress);
124   if (KV == Instructions.end() || KV == Instructions.begin())
125     return nullptr;
126 
127   if (!(--KV)->second.Valid)
128     return nullptr;
129 
130   return &KV->second;
131 }
132 
133 const Instr *
134 FileAnalysis::getNextInstructionSequential(const Instr &InstrMeta) const {
135   std::map<uint64_t, Instr>::const_iterator KV =
136       Instructions.find(InstrMeta.VMAddress);
137   if (KV == Instructions.end() || ++KV == Instructions.end())
138     return nullptr;
139 
140   if (!KV->second.Valid)
141     return nullptr;
142 
143   return &KV->second;
144 }
145 
146 bool FileAnalysis::usesRegisterOperand(const Instr &InstrMeta) const {
147   for (const auto &Operand : InstrMeta.Instruction) {
148     if (Operand.isReg())
149       return true;
150   }
151   return false;
152 }
153 
154 const Instr *FileAnalysis::getInstruction(uint64_t Address) const {
155   const auto &InstrKV = Instructions.find(Address);
156   if (InstrKV == Instructions.end())
157     return nullptr;
158 
159   return &InstrKV->second;
160 }
161 
162 const Instr &FileAnalysis::getInstructionOrDie(uint64_t Address) const {
163   const auto &InstrKV = Instructions.find(Address);
164   assert(InstrKV != Instructions.end() && "Address doesn't exist.");
165   return InstrKV->second;
166 }
167 
168 bool FileAnalysis::isCFITrap(const Instr &InstrMeta) const {
169   return MII->getName(InstrMeta.Instruction.getOpcode()) == "TRAP";
170 }
171 
172 bool FileAnalysis::canFallThrough(const Instr &InstrMeta) const {
173   if (!InstrMeta.Valid)
174     return false;
175 
176   if (isCFITrap(InstrMeta))
177     return false;
178 
179   const auto &InstrDesc = MII->get(InstrMeta.Instruction.getOpcode());
180   if (InstrDesc.mayAffectControlFlow(InstrMeta.Instruction, *RegisterInfo))
181     return InstrDesc.isConditionalBranch();
182 
183   return true;
184 }
185 
186 const Instr *
187 FileAnalysis::getDefiniteNextInstruction(const Instr &InstrMeta) const {
188   if (!InstrMeta.Valid)
189     return nullptr;
190 
191   if (isCFITrap(InstrMeta))
192     return nullptr;
193 
194   const auto &InstrDesc = MII->get(InstrMeta.Instruction.getOpcode());
195   const Instr *NextMetaPtr;
196   if (InstrDesc.mayAffectControlFlow(InstrMeta.Instruction, *RegisterInfo)) {
197     if (InstrDesc.isConditionalBranch())
198       return nullptr;
199 
200     uint64_t Target;
201     if (!MIA->evaluateBranch(InstrMeta.Instruction, InstrMeta.VMAddress,
202                              InstrMeta.InstructionSize, Target))
203       return nullptr;
204 
205     NextMetaPtr = getInstruction(Target);
206   } else {
207     NextMetaPtr =
208         getInstruction(InstrMeta.VMAddress + InstrMeta.InstructionSize);
209   }
210 
211   if (!NextMetaPtr || !NextMetaPtr->Valid)
212     return nullptr;
213 
214   return NextMetaPtr;
215 }
216 
217 std::set<const Instr *>
218 FileAnalysis::getDirectControlFlowXRefs(const Instr &InstrMeta) const {
219   std::set<const Instr *> CFCrossReferences;
220   const Instr *PrevInstruction = getPrevInstructionSequential(InstrMeta);
221 
222   if (PrevInstruction && canFallThrough(*PrevInstruction))
223     CFCrossReferences.insert(PrevInstruction);
224 
225   const auto &TargetRefsKV = StaticBranchTargetings.find(InstrMeta.VMAddress);
226   if (TargetRefsKV == StaticBranchTargetings.end())
227     return CFCrossReferences;
228 
229   for (uint64_t SourceInstrAddress : TargetRefsKV->second) {
230     const auto &SourceInstrKV = Instructions.find(SourceInstrAddress);
231     if (SourceInstrKV == Instructions.end()) {
232       errs() << "Failed to find source instruction at address "
233              << format_hex(SourceInstrAddress, 2)
234              << " for the cross-reference to instruction at address "
235              << format_hex(InstrMeta.VMAddress, 2) << ".\n";
236       continue;
237     }
238 
239     CFCrossReferences.insert(&SourceInstrKV->second);
240   }
241 
242   return CFCrossReferences;
243 }
244 
245 const std::set<uint64_t> &FileAnalysis::getIndirectInstructions() const {
246   return IndirectInstructions;
247 }
248 
249 const MCRegisterInfo *FileAnalysis::getRegisterInfo() const {
250   return RegisterInfo.get();
251 }
252 
253 const MCInstrInfo *FileAnalysis::getMCInstrInfo() const { return MII.get(); }
254 
255 const MCInstrAnalysis *FileAnalysis::getMCInstrAnalysis() const {
256   return MIA.get();
257 }
258 
259 Error FileAnalysis::initialiseDisassemblyMembers() {
260   std::string TripleName = ObjectTriple.getTriple();
261   ArchName = "";
262   MCPU = "";
263   std::string ErrorString;
264 
265   ObjectTarget =
266       TargetRegistry::lookupTarget(ArchName, ObjectTriple, ErrorString);
267   if (!ObjectTarget)
268     return make_error<UnsupportedDisassembly>(
269         (Twine("Couldn't find target \"") + ObjectTriple.getTriple() +
270          "\", failed with error: " + ErrorString)
271             .str());
272 
273   RegisterInfo.reset(ObjectTarget->createMCRegInfo(TripleName));
274   if (!RegisterInfo)
275     return make_error<UnsupportedDisassembly>(
276         "Failed to initialise RegisterInfo.");
277 
278   AsmInfo.reset(ObjectTarget->createMCAsmInfo(*RegisterInfo, TripleName));
279   if (!AsmInfo)
280     return make_error<UnsupportedDisassembly>("Failed to initialise AsmInfo.");
281 
282   SubtargetInfo.reset(ObjectTarget->createMCSubtargetInfo(
283       TripleName, MCPU, Features.getString()));
284   if (!SubtargetInfo)
285     return make_error<UnsupportedDisassembly>(
286         "Failed to initialise SubtargetInfo.");
287 
288   MII.reset(ObjectTarget->createMCInstrInfo());
289   if (!MII)
290     return make_error<UnsupportedDisassembly>("Failed to initialise MII.");
291 
292   Context.reset(new MCContext(AsmInfo.get(), RegisterInfo.get(), &MOFI));
293 
294   Disassembler.reset(
295       ObjectTarget->createMCDisassembler(*SubtargetInfo, *Context));
296 
297   if (!Disassembler)
298     return make_error<UnsupportedDisassembly>(
299         "No disassembler available for target");
300 
301   MIA.reset(ObjectTarget->createMCInstrAnalysis(MII.get()));
302 
303   Printer.reset(ObjectTarget->createMCInstPrinter(
304       ObjectTriple, AsmInfo->getAssemblerDialect(), *AsmInfo, *MII,
305       *RegisterInfo));
306 
307   return Error::success();
308 }
309 
310 Error FileAnalysis::parseCodeSections() {
311   if (!IgnoreDWARF) {
312     DWARF.reset(DWARFContext::create(*Object).release());
313     if (!DWARF)
314       return make_error<StringError>("Could not create DWARF information.",
315                                      inconvertibleErrorCode());
316 
317     bool LineInfoValid = false;
318 
319     for (auto &Unit : DWARF->compile_units()) {
320       const auto &LineTable = DWARF->getLineTableForUnit(Unit.get());
321       if (LineTable && !LineTable->Rows.empty()) {
322         LineInfoValid = true;
323         break;
324       }
325     }
326 
327     if (!LineInfoValid)
328       return make_error<StringError>(
329           "DWARF line information missing. Did you compile with '-g'?",
330           inconvertibleErrorCode());
331   }
332 
333   for (const object::SectionRef &Section : Object->sections()) {
334     // Ensure only executable sections get analysed.
335     if (!(object::ELFSectionRef(Section).getFlags() & ELF::SHF_EXECINSTR))
336       continue;
337 
338     StringRef SectionContents;
339     if (Section.getContents(SectionContents))
340       return make_error<StringError>("Failed to retrieve section contents",
341                                      inconvertibleErrorCode());
342 
343     ArrayRef<uint8_t> SectionBytes((const uint8_t *)SectionContents.data(),
344                                    Section.getSize());
345     parseSectionContents(SectionBytes, Section.getAddress());
346   }
347   return Error::success();
348 }
349 
350 DILineInfoTable FileAnalysis::getLineInfoForAddressRange(uint64_t Address) {
351   if (!hasLineTableInfo())
352     return DILineInfoTable();
353 
354   return DWARF->getLineInfoForAddressRange(Address, DWARFSearchRange);
355 }
356 
357 bool FileAnalysis::hasValidLineInfoForAddressRange(uint64_t Address) {
358   return !getLineInfoForAddressRange(Address).empty();
359 }
360 
361 bool FileAnalysis::hasLineTableInfo() const { return DWARF != nullptr; }
362 
363 void FileAnalysis::parseSectionContents(ArrayRef<uint8_t> SectionBytes,
364                                         uint64_t SectionAddress) {
365   MCInst Instruction;
366   Instr InstrMeta;
367   uint64_t InstructionSize;
368 
369   for (uint64_t Byte = 0; Byte < SectionBytes.size();) {
370     bool ValidInstruction =
371         Disassembler->getInstruction(Instruction, InstructionSize,
372                                      SectionBytes.drop_front(Byte), 0, nulls(),
373                                      outs()) == MCDisassembler::Success;
374 
375     Byte += InstructionSize;
376 
377     uint64_t VMAddress = SectionAddress + Byte - InstructionSize;
378     InstrMeta.Instruction = Instruction;
379     InstrMeta.VMAddress = VMAddress;
380     InstrMeta.InstructionSize = InstructionSize;
381     InstrMeta.Valid = ValidInstruction;
382 
383     // Check if this instruction exists in the range of the DWARF metadata.
384     if (hasLineTableInfo() && !hasValidLineInfoForAddressRange(VMAddress))
385       continue;
386 
387     addInstruction(InstrMeta);
388 
389     if (!ValidInstruction)
390       continue;
391 
392     // Skip additional parsing for instructions that do not affect the control
393     // flow.
394     const auto &InstrDesc = MII->get(Instruction.getOpcode());
395     if (!InstrDesc.mayAffectControlFlow(Instruction, *RegisterInfo))
396       continue;
397 
398     uint64_t Target;
399     if (MIA->evaluateBranch(Instruction, VMAddress, InstructionSize, Target)) {
400       // If the target can be evaluated, it's not indirect.
401       StaticBranchTargetings[Target].push_back(VMAddress);
402       continue;
403     }
404 
405     if (!usesRegisterOperand(InstrMeta))
406       continue;
407 
408     IndirectInstructions.insert(VMAddress);
409   }
410 }
411 
412 void FileAnalysis::addInstruction(const Instr &Instruction) {
413   const auto &KV =
414       Instructions.insert(std::make_pair(Instruction.VMAddress, Instruction));
415   if (!KV.second) {
416     errs() << "Failed to add instruction at address "
417            << format_hex(Instruction.VMAddress, 2)
418            << ": Instruction at this address already exists.\n";
419     exit(EXIT_FAILURE);
420   }
421 }
422 
423 UnsupportedDisassembly::UnsupportedDisassembly(StringRef Text) : Text(Text) {}
424 
425 char UnsupportedDisassembly::ID;
426 void UnsupportedDisassembly::log(raw_ostream &OS) const {
427   OS << "Could not initialise disassembler: " << Text;
428 }
429 
430 std::error_code UnsupportedDisassembly::convertToErrorCode() const {
431   return std::error_code();
432 }
433 
434 } // namespace cfi_verify
435 } // namespace llvm
436