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