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>();
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<StringError>(Twine("Couldn't find target \"") +
228                                        ObjectTriple.getTriple() +
229                                        "\", failed with error: " + ErrorString,
230                                    inconvertibleErrorCode());
231 
232   RegisterInfo.reset(ObjectTarget->createMCRegInfo(TripleName));
233   if (!RegisterInfo)
234     return make_error<StringError>("Failed to initialise RegisterInfo.",
235                                    inconvertibleErrorCode());
236 
237   AsmInfo.reset(ObjectTarget->createMCAsmInfo(*RegisterInfo, TripleName));
238   if (!AsmInfo)
239     return make_error<StringError>("Failed to initialise AsmInfo.",
240                                    inconvertibleErrorCode());
241 
242   SubtargetInfo.reset(ObjectTarget->createMCSubtargetInfo(
243       TripleName, MCPU, Features.getString()));
244   if (!SubtargetInfo)
245     return make_error<StringError>("Failed to initialise SubtargetInfo.",
246                                    inconvertibleErrorCode());
247 
248   MII.reset(ObjectTarget->createMCInstrInfo());
249   if (!MII)
250     return make_error<StringError>("Failed to initialise MII.",
251                                    inconvertibleErrorCode());
252 
253   Context.reset(new MCContext(AsmInfo.get(), RegisterInfo.get(), &MOFI));
254 
255   Disassembler.reset(
256       ObjectTarget->createMCDisassembler(*SubtargetInfo, *Context));
257 
258   if (!Disassembler)
259     return make_error<StringError>("No disassembler available for target",
260                                    inconvertibleErrorCode());
261 
262   MIA.reset(ObjectTarget->createMCInstrAnalysis(MII.get()));
263 
264   Printer.reset(ObjectTarget->createMCInstPrinter(
265       ObjectTriple, AsmInfo->getAssemblerDialect(), *AsmInfo, *MII,
266       *RegisterInfo));
267 
268   return Error::success();
269 }
270 
271 Error FileAnalysis::parseCodeSections() {
272   for (const object::SectionRef &Section : Object->sections()) {
273     // Ensure only executable sections get analysed.
274     if (!(object::ELFSectionRef(Section).getFlags() & ELF::SHF_EXECINSTR))
275       continue;
276 
277     StringRef SectionContents;
278     if (Section.getContents(SectionContents))
279       return make_error<StringError>("Failed to retrieve section contents",
280                                      inconvertibleErrorCode());
281 
282     ArrayRef<uint8_t> SectionBytes((const uint8_t *)SectionContents.data(),
283                                    Section.getSize());
284     parseSectionContents(SectionBytes, Section.getAddress());
285   }
286   return Error::success();
287 }
288 
289 void FileAnalysis::parseSectionContents(ArrayRef<uint8_t> SectionBytes,
290                                         uint64_t SectionAddress) {
291   MCInst Instruction;
292   Instr InstrMeta;
293   uint64_t InstructionSize;
294 
295   for (uint64_t Byte = 0; Byte < SectionBytes.size();) {
296     bool ValidInstruction =
297         Disassembler->getInstruction(Instruction, InstructionSize,
298                                      SectionBytes.drop_front(Byte), 0, nulls(),
299                                      outs()) == MCDisassembler::Success;
300 
301     Byte += InstructionSize;
302 
303     uint64_t VMAddress = SectionAddress + Byte - InstructionSize;
304     InstrMeta.Instruction = Instruction;
305     InstrMeta.VMAddress = VMAddress;
306     InstrMeta.InstructionSize = InstructionSize;
307     InstrMeta.Valid = ValidInstruction;
308     addInstruction(InstrMeta);
309 
310     if (!ValidInstruction)
311       continue;
312 
313     // Skip additional parsing for instructions that do not affect the control
314     // flow.
315     const auto &InstrDesc = MII->get(Instruction.getOpcode());
316     if (!InstrDesc.mayAffectControlFlow(Instruction, *RegisterInfo))
317       continue;
318 
319     uint64_t Target;
320     if (MIA->evaluateBranch(Instruction, VMAddress, InstructionSize, Target)) {
321       // If the target can be evaluated, it's not indirect.
322       StaticBranchTargetings[Target].push_back(VMAddress);
323       continue;
324     }
325 
326     if (!usesRegisterOperand(InstrMeta))
327       continue;
328 
329     IndirectInstructions.insert(VMAddress);
330   }
331 }
332 
333 void FileAnalysis::addInstruction(const Instr &Instruction) {
334   const auto &KV =
335       Instructions.insert(std::make_pair(Instruction.VMAddress, Instruction));
336   if (!KV.second) {
337     errs() << "Failed to add instruction at address "
338            << format_hex(Instruction.VMAddress, 2)
339            << ": Instruction at this address already exists.\n";
340     exit(EXIT_FAILURE);
341   }
342 }
343 
344 char UnsupportedDisassembly::ID;
345 void UnsupportedDisassembly::log(raw_ostream &OS) const {
346   OS << "Dissassembling of non-objects not currently supported.\n";
347 }
348 
349 std::error_code UnsupportedDisassembly::convertToErrorCode() const {
350   return std::error_code();
351 }
352 
353 } // namespace cfi_verify
354 } // namespace llvm
355