基于LLVM編譯器的IDA自動結構體分析插件
這篇文章旨在介紹一款對基于LLVM的retdec開源反編譯器工具進行二次開發的IDA自動結構體識別插件實現原理分析。
筆者在一款基于LLVM編譯器架構的retdec開源反編譯器工具的基礎上，融合了klee符號執行工具，通過符號執行(Symbolic Execution)引擎動態模擬反編譯后的llvm的ir(中間指令集)運行源程序的方法，插樁所有的對x86指令集的thiscall類型函數對this指針結構體(也就是rcx寄存器，簡稱this結構)偏移量引用，經行分析匯總后自動識別this結構體的具體內容，并自動集成導入ida工具輔助分析。
源碼分析
1、LLVM編譯器簡介
LLVM 命名最早源自于底層虛擬機（Low Level Virtual Machine）的縮寫，由于命名帶來的混亂，LLVM就是該項目的全稱。LLVM 核心庫提供了與編譯器相關的支持，可以作為多種語言編譯器的后臺來使用。能夠進行程序語言的編譯器優化、鏈接優化、在線編譯優化、代碼生成。
LLVM的項目是一個模塊化和可重復使用的編譯器和工具技術的集合.LLVM是伊利諾伊大學的一個研究項目，提供一個現代化的，基于SSA(static single assignment靜態單一賦值)的編譯策略能夠同時支持靜態和動態的任意編程語言的編譯目標。自那時以來，已經成長為LLVM的主干項目，由不同的子項目組成，其中許多是正在生產中使用的各種 商業和開源的項目，以及被廣泛用于學術研究。本文介紹的幾款相關工具都是基于LLVM編譯器架構。
2、Retdec源碼分析
retdec是一款基于LLVM編譯器架構的支持多種機器碼環境的跨平臺反編譯工具，輸入為任意支持的二進制可執行文件,目標輸出為一個可以再次編譯的C語言的源碼文件。
克隆git倉庫后使用Cmake GUI工具使用如下圖配置將源工程及LLVM依賴工程轉為Visual Studio 2017工程，筆者提供的工程已經是轉換后的vs工程,可以直接在vs中打開編譯。
筆者的工程包含2個主要項目，一個是retdec-decompiler用于反編譯輸入二進制文件至c語言的源碼輸出文件，另外一個是IDA自動結構體識別插件，這2個都是依賴于llvm的獨立項目。
x86指令集的__thiscall)調用約定不同于__stdcall)參數從右向左被推入堆棧，而this指針由寄存器rcx傳遞而不是堆棧,也就是說rcx指向this結構體指針，一般是在類構造函數中申請的類結構體指針的地址，申請大小固定后不會改變。
這個結構體由從派生類到基類的順序疊加在一起，每個類的指針首地址指向一個vftable虛表函數結構體包含了當前類所有的包括重寫虛函數在內的類成員函數數組，而這個vftable的地址減去一個sizeof(void*)大小后指向一個RTTICompleteObjectLocator結構體，它的相關結構體描述了這個類C++的所有多態性（運行時）相關信息，具體可以參考dynamic_cast實現原理相關文章。
相關結構體如下，retdec原有代碼分析x64的rtti結構體有問題，主要出在偏移量為int32類型是基于模塊基址的偏移而不是絕對地址，這個問題筆者已修復。
typedef struct TypeDescriptor{ void * pVFTable; // Field overloaded by RTTI void * spare; // reserved, possible for RTTI char name[]; // The decorated name of the type; 0 terminated.類名稱} TypeDescriptor;struct PMD{ ptrdiff_t mdisp; //member displacement vftable offset ptrdiff_t pdisp; //vftable displacement vftable offset ptrdiff_t vdisp; //displacement within vftable offset(for virtual base class)};typedef const struct _s_RTTIBaseClassDescriptor{ TypeDescriptor *pTypeDescriptor; DWORD numContainedBases; PMD where; DWORD attributes;} _RTTIBaseClassDescriptor;typedef const struct _s_RTTIBaseClassArray{ _RTTIBaseClassDescriptor* arrayOfBaseClassDescriptors[3];}_RTTIBaseClassArray;typedef const struct _s_RTTIClassHierarchyDescriptor{ DWORD signature; DWORD attributes; DWORD numBaseClasses; _RTTIBaseClassArray *pBaseClassArray;}_RTTIClassHierarchyDescriptor;typedef const struct _s_RTTICompleteObjectLocator{ DWORD signature; DWORD offset; //vftbl相對this的偏移 DWORD cdOffset; //constructor displacement TypeDescriptor *pTypeDescriptor; _RTTIClassHierarchyDescriptor *pClassDescriptor;}_RTTICompleteObjectLocator;typedef struct TypeDescriptor{#if defined(_WIN64) || defined(_RTTI) || defined(BUILDING_C1XX_FORCEINCLUDE) const void * pVFTable; // Field overloaded by RTTI#else unsigned long hash; // Hash value computed from type's decorated name#endif void * spare; // reserved, possible for RTTI char name[]; // The decorated name of the type; 0 terminated. } TypeDescriptor;
在缺少調試符號和dll導出函數名的情況下，一般最多只能通過解析二進制程序內的rtti結構體獲得有限的可用信息,比如類名稱和繼承關系等，ida默認會自動識別基于ms和gcc等編譯器生成的rtti結構體，如果用戶覺得不夠全面可以使用classinformer這款ida插件暴力搜索所有符合條件的rtti結構體，提供匯總分析功能。
筆者工具中也提供一個功能將vftable所有的包含函數加入分析器統一分析，類似的功能還有對MFC窗口的AFX_MSGMAP_ENTRY結構體包含的相關目標函數分析。
由于這些成員函數都是thiscall類型,所以rcx總是指向同一個派生類結構體，把這些函數根據vftable地址分類進行分析顯然是個很好的辦法。這些功能在工具中集成進了ida提供添加目標函數加入分析隊列，具體使用方法見工具使用介紹節。
LLVM整體架構，前端用的是clang,廣義的LLVM是指整個LLVM架構，一般狹義的LLVM指的是LLVM后端（包含代碼優化和目標二進制代碼生成)，前端clang用于分析高級語言源代碼產生后端的LLVM IR中間指令表示。
LLVM IR中間指令是一種“通用中間語言”采用SSA形式，可以擁有無限多個虛擬寄存器且是抽象與高級語言和目標最終編譯輸出二進制文件架構約束無關，它通過提供類型信息可以用于進一步提供優化轉化為目標代碼生成也可以反過來轉化成類似c的高級語言表示。
編譯為目標二進制代碼生成的功能不在本文的討論范圍，文本主要討論反編譯過程和模擬LLVM IR中間指令執行分析獲得this結構體的相關信息實現方式。retdec工具使用的反編譯引擎是capstone2llvmir，主要由"retdec-decoder"這個llvm Passe負責將源程序二進制匯編ASM代碼轉化成LLVM IR中間指令，在轉換初始化之前從程序入口、調試信息和Vftables獲取靜態已知的跳轉目標JumpTargets用于構造整個程序的LLVM IR Selection DAG(directed acyclic graph有向無環圖),對后續的跳轉目標進行指令集順序上的調度優化轉化為retdec的等價DAG的節點CFGNode及其組織架構。
//獲取靜態已知的跳轉目標JumpTargetsvoid Decoder::initJumpTargets(){ initJumpTargetsConfig(); initStaticCode(); initJumpTargetsEntryPoint(); initJumpTargetsExterns(); initJumpTargetsImports(); initJumpTargetsDebug(); initJumpTargetsSymbols(); initJumpTargetsExports(); initVtables();}//遞歸解析每個跳轉目標JumpTarget直到沒有跳轉目標void Decoder::decode(){ JumpTarget jt; while (getJumpTarget(jt)) { decodeJumpTarget(jt); }}//遞歸解析每個跳轉目標JumpTargetvoid Decoder::decodeJumpTarget(const JumpTarget& jt){ //使用反編譯引擎capstone2llvmir轉換ASM指令 auto res = translate(bytes, addr, irb); llvm::CallInst*& pCall = res.branchCall; //處理所有call類型及其條件call類型 if (_c2l->isCallFunctionCall(pCall)||_c2l->isBranchFunctionCall(pCall)||_c2l->isCondBranchFunctionCall(pCall)) { auto t = getJumpTarget(addr, pCall, pCall->getArgOperand(0)){ //生成SymbolicTree auto st = SymbolicTree::OnDemandRda(val, 20); //獲取跳轉目標JumpTarget的常量值 llvm::ConstantInt* ci = nullptr; if (match(st, m_ConstantInt(ci))) { return ci->getZExtValue(); } } //處理分支跳轉條件表addrTblCi和索引計算獲取所有跳轉cases加入JumpTarget getJumpTargetSwitch(addr, branchCall, val, st){ if(match(st, m_Load( m_c_Add( m_CombineOr( m_c_Mul(m_Value(), m_ConstantInt(mulShlCi), &mulOp), m_Shl(m_Value(), m_ConstantInt(mulShlCi), &shlOp)), m_ConstantInt(addrTblCi))))){ llvm::Value* idx = mulOp ? mulOp->getOperand(0) : shlOp->getOperand(0); std::vector
cases; while (true) { Address item = addrTblCi->getZExtValue(); addrTblCi += pointersize; cases.push_back(item); } for (auto c : cases) { _jumpTargets.push( c, JumpTarget::eType::CONTROL_FLOW_SWITCH_CASE, _c2l->getBasicMode(), // mode should not change here addr); } } }; _jumpTargets.push(t,JumpTarget::eType::CONTROL_FLOW_CALL_TARGET,determineMode(tr.capstoneInsn, t),addr); }else if (_c2l->isReturnFunctionCall(pCall)) { //如果是返回指令類型直接創建ReturnInst transformToReturn(pCall); }
}
retdec-decoder反編譯模塊遞歸解析每個跳轉目標JumpTarget，調用capstone2llvmir::translate函數將匯編指令轉化成LLVM IR中間指令，在解析跳轉目標的過程中又可以根據其分支類型，主要有call類型及其(分支)條件call類型和返回指令類型，從中獲取新的跳轉目標加入到待處理的列表中，,直到沒有跳轉目標完成整個程序的反編譯解碼過程。
capstone2llvmir::Capstone2LlvmIrTranslator::TranslationResultOne Decoder::translate(ByteData& bytes, common::Address& addr, llvm::IRBuilder<>& irb){cs_insn* insn = cs_malloc(_handle);//調用capstone將二進制代碼數據轉換為cs_insnbool disasmRes = cs_disasm_iter(_handle, &bytes, &size, &address, insn);translateInstruction(insn, irb);}
void Capstone2LlvmIrTranslatorX86_impl::translateInstruction( cs_insn* i, llvm::IRBuilder<>& irb){//函數入口地址pc保存在"asm_program_counter"這個全局變量中retdec::common::Address a = i->address;auto* s = irb.CreateStore(llvm::ConstantInt::get(gv->getValueType(), a, false), asm_program_counter, true);//這個表維護了所有可以轉化的X86匯編指令Capstone2LlvmIrTranslatorX86_impl::_i2fm ={...{X86_INS_ADD, &Capstone2LlvmIrTranslatorX86_impl::translateAdd},{X86_INS_MOV, &Capstone2LlvmIrTranslatorX86_impl::translateMov},...}auto fIt = _i2fm.find(i->id);if (fIt != _i2fm.end() && fIt->second != nullptr){ auto f = fIt->second; //就是調用Capstone2LlvmIrTranslatorX86_impl::translateXXX (this->*f)(i, xi, irb);}else{//轉換函數調用void Capstone2LlvmIrTranslator_impl::translatePseudoAsmGeneric( cs_insn* i, CInsn* ci, llvm::IRBuilder<>& irb) { llvm::Function* fnc = getPseudoAsmFunction( i, retType, types); auto* c = irb.CreateCall(fnc, vals); //根據OperandAccess獲取Call的返回值類型 llvm::Value* val = retType->isVoidTy() ? llvm::cast( llvm::UndefValue::get(getRegisterType(r))) : llvm::cast(c); storeRegister(r, val, irb); } } }//對應轉換函數void Capstone2LlvmIrTranslatorX86_impl::translateXXX(cs_insn* i, cs_x86* xi, llvm::IRBuilder<>& irb){ //創建匯編代碼的對應指令 std::tie(op0, op1) = loadOpXXX(xi, irb, eOpConv::SEXT_TRUNC_OR_BITCAST); auto* add = irb.CreateXXX(op0, op1); //生成指令操作 op1 = loadOp(xi->operands[1], irb); storeOp(xi->operands[0], add, irb); if (i->id == X86_INS_XADD) { storeOp(xi->operands[1], op0, irb); }}
cs_malloc分配capstone的handle，用這個handle通過cs_disasm_iter把二進制翻譯為匯編生成capstone的insn結構，并把函數入口地址pc保存在“asm_program_counter”這個全局變量中，這只是起到的標識的作用,在后面的pass會自動把這個優化掉。
然后調用translateInstruction從_i2fm這張全局指令解析表中獲取對應的translateXXX轉換函數將cs_insn轉化成LLVM IR中間指令，如果不在表中則生成Function函數調用構造相關參數。
int main(int argc, char *argv[]){ std::vector CODE = retdec::utils::hexStringToBytes("80 05 78 56 34 12 11 00"); ProgramOptions po(argc, argv); llvm::LLVMContext ctx; llvm::Module module("test", ctx); auto* f = llvm::Function::Create( llvm::FunctionType::get(llvm::Type::getVoidTy(ctx), false), llvm::GlobalValue::ExternalLinkage, "root", &module); llvm::BasicBlock::Create(module.getContext(), "entry", f); llvm::IRBuilder<> irb(&f->front()); auto* ret = irb.CreateRetVoid(); irb.SetInsertPoint(ret); auto c2l = Capstone2LlvmIrTranslator::createArch( po.arch, &module, po.basicMode, po.extraMode); //調用capstone轉換函數 auto res=c2l->translate(po.code.data(), po.code.size(), po.base, irb); return EXIT_SUCCESS;}
retdec為我們提供了一個demo工具capstone2llvmirtool用于將指定二進制代碼通過16進制字符串在命令行傳入測試translate功能并輸出結果，有興趣的讀者可以自己研究下。
bool HLLWriter::emitTargetCode(ShPtr module) {...//輸出模塊靜態引用相關信息if (emitXXXHeader()) {}.... emitFunctions();...}//輸出函數主體bool HLLWriter::emitFunctions() { FuncVector funcs(module->func_definition_begin(), module->func_definition_end()); sortFuncsForEmission(funcs); bool somethingEmitted = false; for (const auto &func : funcs) { if (somethingEmitted) { // To produce an empty line between functions. out->newLine(); } somethingEmitted |= emitFunction(func); } return somethingEmitted;}void CHLLWriter::visit(ShPtr func) { if (func->isDeclaration()) { emitFunctionPrototype(func); } else { emitFunctionDefinition(func); }}void CHLLWriter::emitFunctionDefinition(ShPtr func) { PRECONDITION(func->isDefinition(), "it has to be a definition");
out->addressPush(func->getStartAddress()); emitFunctionHeader(func); out->space(); emitBlock(func->getBody()); out->addressPop(); out->newLine();}//輸出塊主體void CHLLWriter::emitBlock(ShPtr stmt) { out->punctuation('{'); out->newLine(); increaseIndentLevel(); // Emit the block, statement by statement. do { out->addressPush(stmt->getAddress()); emitGotoLabelIfNeeded(stmt);
// Are there any metadata? std::string metadata = stmt->getMetadata(); if (!metadata.empty()) { emitDebugComment(metadata); } stmt->accept(this); out->addressPop(); //遞歸后繼直到沒有后繼 stmt = stmt->getSuccessor(); } while (stmt);
decreaseIndentLevel(); out->space(getCurrentIndent()); out->punctuation('}');}
retdec內部構造的一個和LLVM IR中間指令等價的指令結構，這些指令又構成了和llvm::BasicBlock類等價的Statement等價結構，由CFGNode類負責管理每個Function的前驅后繼和分支邊。
在CHLLWriter這個類中完成所有模塊中的結構體和函數生成C語言高級代碼的工作，從Module輸出了模塊的依賴結構體后,在emitFunctions環節CHLLWriter使用一個類Visitor->visit重載函數遞歸解析Function及其包含的內部Statement分支結構，遞歸Statement的所有后繼和和分支邊，直到沒有后繼子分支，在這個過程中輸出內部變量retdec指令,至此全部反編譯流程完成并輸出至目標c文件。
3、Klee源碼分析
隨著現代軟件規模的加大、復雜度不斷增加,對軟件安全性的需求也不斷上升，傳統的分析測試技術因自身的局限已無法滿足當前的軟件安全性的需求。而符號執行技術因自身具有的優異特性在軟件測試領域中受到了廣泛的關注，常見和符號執行工具如angr(基于python),klee(基于llvm),Triton(也是基于llvm)等。
Klee對約束求解進行優化策略，將自身的STP求解器與微軟公司開發的Z3求解器結合并行化工作，特點是具有自動化測試用例生成，程序路徑覆蓋率高，無需人工操作等優點，受到了當前眾多高校和科技公司的關注。隨著許多符號執行工具不斷出現,在實際應用中取得了很好的成績。
但是符號執行技術還存在著一些需要亟待解決的關鍵問題如路徑爆炸，指針計算以及約束求解等問題。Klee中的符號執行過程稱為狀態機(state machine)機制，通過將LLVMIR中間指令解釋成Klee內建指令，并將代碼中指令映射為約束條件的符號變量值(Symbolic Variable Value)，通過模擬程序執行流程構建單元代碼的控制流圖，當選擇代碼路徑遇到分支語句時，提取并存儲不同分支的約束條件，使用約束求解器求解進入某一分支所要滿足的約束，最后根據路徑調度算法來對控制流圖中的所有路徑進行遍歷分析，代入滿足約束條件的值以進入該分支，并對執行過的程序路徑進行記錄。
下一次執行到該分支時選擇未進入的分支執行，這樣逐步對程序中所有的可行路徑進行遍歷。用程序的語言表述是Klee在測試用例的入口處將一個配置好的初始狀態(initial state)放入池中，循環地從狀態池里選擇狀態，并在那個狀態下符號化地執行每條指令。直到狀態池里沒有狀態了，或者時間超過了用戶設定的。
與普通進程不同，狀態寄存器、堆棧和堆對象的存儲位置指的是Klee表達式（樹），而不是原始數據值。表達式的葉子節點是符號變量或常量，內部節點是LLVM IR中間指令的操作符（例如算術操作、按位操作、比較和內存訪問），存儲常量表達式的存儲內容是實際的整形常數值，變量的存儲是嵌套的表達式樹引用。
由于我們沒有去解析要分析的目標二進制相關的依賴文件模塊，也在無法創建真實的進程環境而是采用符號執行的方法模擬一個函數執行，這過程必然會丟失或者欠缺真實運行環境實際存在在內存中的一些東西，所以這種方法不能被當作虛擬化環境分析目標二進制程序(emulating execution in a virtual (emulated) environment)而是近似模擬符號執行，簡單的說就是沒有虛擬層。
每當一次state迭代結束，state的出口條件分支是布爾表達式，Klee會去查詢約束求解器來確定當前路徑上的分支條件是否恒為真或假。如果恒為真或假，就更新指令指針到預計的位置，fork出一個新的state。
反之兩種分支都有可能，然后KLEE路徑調度算法就會去復制當前狀態，并從這個狀態fork出兩個新的state,這樣就可以同時探索兩條路徑，,并且同時更新指令指針和路徑條件。
bool SymbolicTypeReconstructor::runOnModule(llvm::Module& m){for (auto addr : image->getRtti().getVtablesMsvc()){ const Interpreter::InterpreterOptions opt; RetdecInterpreterHandler interpreterHandlerPtr = new RetdecInterpreterHandler(M); interpreter = Interpreter::create(ctx, opt, interpreterHandlerPtr); _config = ConfigProvider::getConfig(M); _module = _config->_module; interpreter->initSingleModule(M); DataLayout TD = _module->getDataLayout(); Context::initialize(TD.isLittleEndian(), static_cast(TD.getPointerSizeInBits())); llvm::Function* func = _config->getLlvmFunction(addr); char * argv = nullptr; char * env = nullptr; //構建runFunctionAsMain執行每個要分析的函數 interpreter->runFunctionAsMain(func, 0, &argv, &env); }} //重構函數入口處執行void Executor::runFunctionAsMain(Function *f, int argc, char **argv, char **envp) { std::vector > arguments;{ExecutionState *state = new ExecutionState(kmodule->functionMap[f]);MemoryManager* memory = new MemoryManager(NULL);//構建參數內存對象MemoryObject* argvMO = memory->allocate((argc + 1 + envc + 1 + 1) * NumPtrBytes, /*isLocal=*/false, /*isGlobal=*/true, /*allocSite=*/first, /*alignment=*/8);//初始化全局變量:initializeGlobals(*state); void Executor::run(ExecutionState &state){searcher = constructUserSearcher(*this);std::vector newStates(states.begin(), states.end());searcher->update(0, newStates, std::vector());while (!states.empty() && !haltExecution) {ExecutionState &state = searcher->selectState();KInstruction *ki = state.pc;stepInstruction(state);executeInstruction(state, ki);updateStates(&state);}
ExecutionState由一個傳入的Function構造初始狀態，然后迭代執行里面的Instruction，具體工作由executeInstruction函數完成，內部分類模擬處理了所有指令類型，Function的自帶參數被分配在它的StackFrame->locals字段,對應的是llvm::.Function::.Argument字段，從x86架構來講32位的函數參數由esp傳遞，64位由rcx等寄存器和rsp傳遞，在初始化狀態這些寄存器都被映射到對應的全局變量，也就是說是運行時賦值的，盡管llvm的Function構造時反編譯程序已將關聯的虛擬寄存器Value映射到這些參數。
由于我們不知道要分析之前的函數實際運行時的參數值，我們只能構造一個偽造的預先分配rcx結構體和rsp棧結構體處理這些參數。這里我們要用到klee里有個很重要的概念就是內存模型。
前面我們講到klee的每個狀態由ExecutionState解釋執行，它的AddressSpace字段維護了所有運行時內存分配與調度，AddressSpace內部實際上維護的是一對MemoryObject和ObjectState組成的ObjectPair數組Map字典，這兩個對象成對出現和使用描述的是同一塊內存區域。
在Memory.h定義文件里，我們可以看見有MemoryObject的定義，包含以下屬性，包括id，地址，內存對象的大小等，這些信息僅供描述內存分配信息使用，而實際內存讀寫操作由ObjectState參與完成，它的地址由MemoryManager->allocate根據申請的大小分配相對映射地址，這個大小在申請時確定不能重分配。
對應64位進程分析32位進程，為了實現等價的32位地址分配，筆者無法在windows實現源碼中實現mmap類似功能在64位系統申請32位長度地址，而是改用std::map字典映射32地址和64實際分配地址，具體實現方式參考筆者代碼。
盡管每對ObjectPair的兩個對象維護相同大小的內存區域，實際上只有ObjectState在內部concreteStore字段維護了實際分配的內存數據，當ExecutionState需要執行內存操作時先調用符號執行解釋器(solver)采用符號化的方式求出需要操作ObjectPair，然后求出相對偏移量執行符號化的讀寫操作。
//造一個偽造的預先分配rcx結構體和rsp棧結構體處理Function的參數void Executor::initializeGlobalObjects(ExecutionState &state) {...if (isStackPointer(&v)){ initializePreAllocedGlobalObjects(state, &op, v, true);}if (isThisPointer(&v)){ MemoryObject *that=initializePreAllocedGlobalObjects(state, &op, v, false); interpreterHandler->setThisPointerMemoryObject(that);}...}MemoryObject * Executor::initializePreAllocedGlobalObjects(ExecutionState &state, ObjectPair *op, const GlobalVariable &v, bool negative){ const MemoryObject *mo = op->first; ObjectState *os = const_cast(op->second); std::size_t allocationAlignment = getAllocationAlignment(&v); MemoryObject *mo1 = memory->allocate(fixedStackSize, /*isLocal=*/false, /*isGlobal=*/true, /*allocSite=*/&v,/*alignment=*/allocationAlignment); ObjectState *os1 = bindObjectInState(state, mo1, false); uint64_t stackptr = negative ? mo1->address + (mo1->size / 2) - mo->size : mo1->address; ref stackexp = ConstantExpr::create(stackptr, Context::get().getPointerWidth()); os->write(0, stackexp); return mo1;}void Executor::transferToBasicBlock(BasicBlock *dst, BasicBlock *src, KFunction *kf = state.stack.back().kf; unsigned entry = kf->basicBlockEntry[dst]; state.pc = &kf->instructions[entry]; if (state.pc->inst->getOpcode() == Instruction::PHI) { PHINode *first = static_cast(state.pc->inst); state.incomingBBIndex = first->getBasicBlockIndex(src); }}void Executor::executeInstruction(ExecutionState &state, KInstruction *ki) { Instruction *i = ki->inst; switch (i->getOpcode()) { ... case Instruction::Br: { case Instruction::IndirectBr: { transferToBasicBlock(bi->getSuccessor(0), bi->getParent(), state); } //讀操作 case Instruction::Load: { ref base = eval(ki, 0, state).value; executeMemoryOperation(state, false, base, 0, ki); break; } //寫操作 case Instruction::Store: { ref base = eval(ki, 1, state).value; ref value = eval(ki, 0, state).value; executeMemoryOperation(state, true, base, value, 0); break; }void Executor::executeMemoryOperation(ExecutionState &state, bool isWrite, ref address, ref value /* undef if read */, KInstruction *target /* undef if write */) { ObjectPair op;//MemoryObject* mo 和ObjectState* os //調用符號執行解釋器(solver)采用符號化的方式求出需要操作ObjectPair bool success=state.addressSpace.resolveOne(state, solver, address, op, success)) ; ref offset = mo->getOffsetExpr(address); if (isWrite) { ObjectState *wos = state.addressSpace.getWriteable(mo, os); wos->write(offset, value); } else { ref result = os->read(offset, type); } ref resultoffset; bool successoffset = solver->getValue(state.constraints, offset, resultoffset,state.queryMetaData); uint64_t offsetInBits = resultoffset->getZExtValue() * 8; //筆者的內存插樁操作,判斷mo是不是rcx的MemoryObject interpreterHandler->instrumentMemoryOperation(isWrite, mo, offsetInBits, type);
}
具體內存結構思維導圖如下:
Function└── ExecutionState └── AddressSpace ├── ObjectState │ ├── Size │ ├── ConcreteStore │ └──UpdateList │ ├── Index │ └── ValueMemoryManager-> └── MemoryObject ├── Address └── Size
ObjectState在內部有concreteStore字段維護了實際分配的內存數據，和對應concreteMask位圖標記指定偏移量實際數據狀態，當位圖位設置表示實際存在數據，當未設置表示轉為符號化數據.每次內存操作刷新UpdateList鏈表后把當前表達式壓入UpdateList。
class UpdateNode { const ref next; ref index, value; UpdateNode::UpdateNode(const ref &_next, const ref &_index, const ref &_value) : next(_next), index(_index), value(_value) { size = next ? next->size + 1 : 1;}}class UpdateList { const Array *root; ref head;UpdateList::UpdateList(const Array *_root, const ref &_head) : root(_root), head(_head) {}void UpdateList::extend(const ref &index, const ref &vlue) { head = new UpdateNode(head, index, value);}}const UpdateList &ObjectState::getUpdates() const { if (!updates.root) { unsigned NumWrites = updates.head ? updates.head->getSize() : 0; std::vector< std::pair< ref, ref > > Writes(NumWrites); const auto *un = updates.head.get(); //從后至前反過來調用構造鏈表 for (unsigned i = NumWrites; i != 0; un = un->next.get()) { --i; Writes[i] = std::make_pair(un->index, un->value); } std::vector< ref > Contents(size); for (unsigned i = 0, e = size; i != e; ++i) Contents[i] = ConstantExpr::create(0, Expr::Int8); unsigned Begin = 0, End = Writes.size(); //從前至后構造執行鏈表操作 for (; Begin != End; ++Begin) { ConstantExpr *Index = dyn_cast(Writes[Begin].first); if (!Index) break; ConstantExpr *Value = dyn_cast(Writes[Begin].second); if (!Value) break; Contents[Index->getZExtValue()] = Value; } static unsigned id = 0; const Array *array = getArrayCache()->CreateArray( "const_arr" + llvm::utostr(++id), size, &Contents[0], &Contents[0] + Contents.size()); //鏈表重構一遍 updates = UpdateList(array, 0); for (; Begin != End; ++Begin) updates.extend(Writes[Begin].first, Writes[Begin].second); }
return updates;}
UpdateList中的表達式數據被描述成Kquery語法格式，在符號執行解釋器(solver)和Kquery語言之間提供了一個抽象層，每種類型的解釋器都繼承了SolverImpl基類，提供統一的重載實現函數模擬求值。
由解釋器生成的ExprEvaluator->visit及其派生類的查詢分析約束條件集合使用，并將結果保存在當前ExecutionState的ConstraintManage表達式空間容器中。
//解釋器(solver)實現,解析表達式bool Z3SolverImpl::internalRunSolver( const Query &query, const std::vector *objects, std::vector > *values, bool &hasSolution) { Z3_solver theSolver = Z3_mk_solver(builder->ctx); //當前ExecutionState的ConstraintManage表達式空間容器 ConstantArrayFinder constant_arrays_in_query; for (auto const &constraint : query.constraints) { Z3_solver_assert(builder->ctx, theSolver, builder->construct(constraint)); constant_arrays_in_query.visit(constraint); Z3ASTHandle z3QueryExpr = Z3ASTHandle(builder->construct(query.expr), builder->ctx); //被描述成Kquery語法格式 constant_arrays_in_query.visit(query.expr);SolverRunStatus runStatusCode = handleSolverResponse(theSolver, satisfiable, objects, values, hasSolution); return true; }
當數據未被刷新時UpdateList中存的是表達式鏈表，每次刷新這個鏈表從最早一個表達式至最后一個表達式更新內存區域Contents[offset]=value，這個效果就像拉鏈一樣一拉從前至后將內存數據寫入一遍，最后把生成Contents數組重新構造鏈表，這樣既保證了順序也保證了準確性。
實際上要確定this結構體的具體內容只需要判斷這個MemoryObject是不是rcx的MemoryObject，筆者在內存操作完成后進行插樁操作，就可以從內存操作的參數中獲取到偏移量與操作數大小，生成后的結構體數據經RetdecInterpreterHandler.::FinalizeStructType進行排序匯總后就可以得到一個實際的llvm.::StructType結構體對象，這里還需要處理不完整的結構體數據。
筆者使用的替代方案是，當結構體體頭部存在空隙時，,生成當前指針大小的int類型數組填充空隙，直到空隙小于指針大小，并用這個大小生成對應的int字段填充剩余空隙，對于結構體中間存在的空隙，也是采用同樣的方法擴展空隙前的一個字段為數組類型直到到空隙小于字段大小，,同樣用這個剩余大小生成對應的int字段填充剩余空隙，具體實現見筆者工程源碼（https://gitee.com/cbwang505/llvmanalyzer/blob/master/retdec-master-build/LLVMSymbolicExecution/lib/Support/RetdecInterpreterHandler.cpp）。
//插樁操作void RetdecInterpreterHandler::instrumentMemoryOperation(bool isWrite, const MemoryObject *mo, uint64_t offset, uint64_t width){ if (mo->address == thisptr->address) { if (isWrite) { klee_message("This point struct [operation:=>store] offset :=> %d , length :=> %d", offset, width); } else { klee_message("This point struct [operation:=>load ] offset :=> %d , length :=> %d", offset, width); }//模擬的結構體類型 llvm::Type* tp = llvm::Type::getIntNTy(_module->getContext(), width); POverlappedEmulatedType typeEmu = new OverlappedEmulatedType{ offset,width,tp }; classtp->typesct->emplace_back(typeEmu); }};
這里要修復的問題是Klee默認提供了幾個內置調用函數接口(SpecialFunctionHandler)如malloc等用于模擬執行外部函數調用操作，如果執行模擬調用失敗,存在未對當前當前函數返回值的虛擬寄存器賦值導致下條指令解析時綁定這個寄存器失敗的斷鏈問題，解決方法是當執行call失敗時構造一個0值常量賦值給函數返回值的虛擬寄存器，就解決了模擬執行掉鏈問題的導致的當前state被終止執行.具體解決方法如下:
//模擬執行call指令void Executor::callExternalFunction(ExecutionState &state, KInstruction *target, Function *function, std::vector< ref > &arguments) {//調用內置調用函數接口(SpecialFunctionHandler)if (specialFunctionHandler->handle(state, function, target, arguments)) return; bool success = externalDispatcher->executeCall(function, target->inst, args); if (!success) { klee_warning("failed external call: %s ,try to skip" , function->getName().str().c_str()); //當前函數返回值的虛擬寄存器賦 Type *resultType = target->inst->getType(); if (resultType != Type::getVoidTy(function->getContext())) { //構造默認的0返回值 ref e = ConstantExpr::create(0, getWidthForLLVMType(resultType)); bindLocal(target, state, e); } } }
4、IDA插件開發分析
IDA Pro是一款交互式的、可編程的、可擴展的、多處理器的，交叉Windows或Linux MacOS平臺主機來分析程序，被公認為最好的花錢可以買到的逆向工程利器。IDA的插件開發默認支持c++和python模式，有興趣的讀者可以參考相關入門文章。下面的代碼展示了讓retdec與ida掛鉤生成ida結構體的功能。
bool IDAStructWriter::emitTargetCode(ShPtr module){ShPtr usedTypes(UsedTypesVisitor::getUsedTypes(module));for (const auto &structType : usedStructTypes) { emitStructIDA(structType){ tid_t strucval = 0; //通過名稱匹配 std::regex vtblreg("Class_vtable_(.+)_type"); auto i = structNames.find(structType); if (i != structNames.end()) { std::string rawname = i->second; uint64_t vtbladdr = 0; std::cmatch results; std::regex express(vtblreg); if (std::regex_search(rawname.c_str(), results, express)) { if (results.size() == 2) { std::string vtbstr = results[1]; vtbladdr = strtoull(vtbstr.c_str(), 0, 16); } } strucval = get_struc_id(rawname.c_str()); if (strucval != BADADDR) { struc_t* sptr = get_struc(strucval); del_struc(sptr); } //生成結構體 strucval = add_struc(BADADDR, rawname.c_str()); Address field_offset = 0; const StructType::ElementTypes& elements = structType->getElementTypes(); for (StructType::ElementTypes::size_type i = 0; i < elements.size(); ++i) {
ShPtr elemType(elements.at(i)); uint64_t elelen = emitVarWithType(Variable::create("field_" + field_offset.toHexString(), elemType), strucval, field_offset.getValue()); field_offset += elelen; } INFO_MSG("Create Vtable Struct : " << rawname << " ,Size :"<< field_offset << std::endl); } }}uint64_t IDAStructWriter::emitVarWithType(ShPtr var, tid_t strucval, Address field_offset){ struc_t* sptr = get_struc(strucval); ShPtr varType(var->getType()); uint64_t elelen = DetermineTypeSize(varType); var->accept(this); flags_t flag = byte_flag(); flags_t flag2 = byte_flag(); std::string filename = var->getName(); if (isa(varType)) { ... } else { if (elelen == 1) { flag = byte_flag(); } else if (elelen == 2) { flag = word_flag(); } else if (elelen == 4) { flag = dword_flag(); } else if (elelen == 6) { flag = word_flag(); flag2 = word_flag(); } else if (elelen == 8) { flag = qword_flag(); } if (elelen == 6) { //添加結構體成員 std::string filename2 = filename+"_"; add_struc_member(sptr, filename.c_str(), BADADDR, flag, nullptr, elelen-2); add_struc_member(sptr, filename2.c_str(), BADADDR, flag2, nullptr, elelen-4); } else { add_struc_member(sptr, filename.c_str(), BADADDR, flag, nullptr, elelen); } } return elelen;}//注冊ida的F5按鍵hexrays回調install_hexrays_callback(my_hexrays_cb_t, nullptr);ida_dll_data int idaapi my_hexrays_cb_t(void *ud, hexrays_event_t event, va_list va){ switch (event) { case hxe_open_pseudocode: { vdui_t* vu = va_arg(va, vdui_t *); cfuncptr_t cfunc = vu.cfunc; ea_t vtaddrreal=vtbl2fns.find(cfunc->entry_ea).first; rawname.sprnt("Class_vtable_%x_type", vtaddrreal); tid_t strucval = get_struc_id(rawname.c_str()); if (strucval) { tinfo_t new_type = create_typedef(rawname.c_str()); tinfo_t new_type_ptr = make_pointer(new_type); for (lvar_t& vr : *cfunc->get_lvars()) { qstring nm = vr.name; //設置為分析出來的結構體引用 vr.set_lvar_type(new_type_ptr); vu.refresh_view(false); return; } }
通過先在retdec注冊pass回調，在回調中在獲取Module所有生成的結構體對象，對生成的結構體對象調用ida的api相關函數創建add_struc，設置結構體成員add_struc_member這樣就可以在ida中創造結構體了。
注冊ida的F5按鍵hexrays回調從當前函數的cfunc->entry_ea地址從addr2vftable字典(這個也是在retdec分析rtti的時候解析出來的)中找到對應結構體，把函數簽名的第一個變量類型更新為我們分析出來的結構體，就實現了ida插件的自動分析功能。
//生成x86架構的Coff文件格式的功能的passbool BinWriter::runOnModule(llvm::Module& m){ SMDiagnostic Err; _config = ConfigProvider::getConfig(_module); std::string TheTriple = _module->getTargetTriple(); Triple ModuleTriple(TheTriple); _module->setTargetTriple(TheTriple); char *ErrorMsg = 0; std::string Error; const Target *TheTarget = TargetRegistry::lookupTarget(TheTriple, Error); TargetOptions opt; std::unique_ptr Target_Machine(TheTarget->createTargetMachine( TheTriple, "", "", opt, None, None, CodeGenOpt::None)); llvm::legacy::PassManager pm; TargetLibraryInfoImpl TLII(ModuleTriple); TLII.disableAllFunctions(); pm.add(new TargetLibraryInfoWrapperPass(TLII)); \ std::error_code EC; _module->setDataLayout(Target_Machine->createDataLayout()); bool usefile = false; bool ret = false; std::string binOut = _config->getConfig().parameters.getOutputBinFile(); usefile = false; SmallVector Buffer; raw_svector_ostream OS(Buffer); MCContext *Ctx; cantFail(_module->materializeAll()); //編譯代碼到輸出流 ret = Target_Machine->addPassesToEmitMC(pm, Ctx, OS); pm.run(*_module); size_t len = Buffer.size(); std::unique_ptr CompiledObjBuffer( new SmallVectorMemoryBuffer(std::move(Buffer))); Expected> LoadedObject = object::ObjectFile::createObjectFile(CompiledObjBuffer->getMemBufferRef()); RTDyldMM = new SectionMemoryManager(); //生成coff結構 Dyld = new RuntimeDyld(*static_cast(this), *static_cast(this)); LoadedObjectPtr = LoadedObject->get(); std::unique_ptr L = Dyld->loadObject(*LoadedObjectPtr); this->remapSecLoadAddress(); Dyld->resolveRelocations(); this->remapGlobalSymbolTable(Dyld->getSymbolTable()); Dyld->registerEHFrames(); this->finalizeMemory(); size_t len_org = CompiledObjBuffer->getBufferSize(); for (auto sec : LoadedObjectPtr->sections()) { if (sec.isText() && !sec.isData()) { auto pair = realSecBuf.find(sec.getIndex()); if (pair != realSecBuf.end()) { std::uint8_t* buffer_start = reinterpret_cast(pair->second); size_t len = sec.getSize(); outbuf->reserve(len); outbuf->clear(); for (int i = 0; i < len; i++) { outbuf->emplace_back(static_cast(*(buffer_start + i))); } break; } } } size_t rawlen = outbuf->size(); std::ostringstream logstr; logstr << "target compiler generate function binary buff :=> total size "; logstr << std::hex << len_org; logstr <<" bytes , raw size "; logstr << std::hex << rawlen; logstr << " bytes"; io::Log::phase(logstr.str(), io::Log::SubPhase); return !ret;}//復制到ida新建的Segmentstatic bool idaapi moveBufferToSegment(LLVMFunctionTable* tbl, std::vector& outBuff, int i){put_bytes(tbl->raw_fuc[tbl->num_func].start_fun, outBuff.data(), len);}
筆者的插件提供了另外一個功能將retdec反編譯出來的代碼，調用LLVM后端編譯功能再次生成機器碼，筆者只實現了到生成x86架構的Coff文件格式的功能，并自動拷貝至ida新建的Segment，對生成的目標地址右鍵點擊Create Function后可以按F5反編譯輔助分析。
工具安裝方法
第一種方法，自動安裝只支持Ida Pro 7.0默認安裝目錄:運行Release\Install.bat文件
第二種方法：手動安裝
- 將筆者插件編譯后Release文件解壓至ida安裝目錄"C:\Program Files\IDA 7.0\plugins"
- 在plugins目錄下plugins.cfg文件中添加以下兩行:
LLVMAnalyzer32 LLVMAnalyzer32 Ctrl+Shift+P 0 WIN
LLVMAnalyzer64 LLVMAnalyzer64 Ctrl+Shift+P 0 WIN
- 在點擊ida菜單中"Edit->Plugins->LLVMAnalyzer"啟動插件
工具使用介紹
第一種方法，分析速度較慢：點擊菜單"File/Produce file/Full decompilation program"選擇輸出文件直接分析整個程序集
第二種方法，分析速度較快：
1.在ida窗口對函數或其地址右鍵點擊"Add function to Analyze"添加至分析列表
2.也可以在ida反匯編窗口對vftable右鍵點擊 "Add virtual table to Analyze"成員函數添加至分析列表
3.也可以在ida反匯編窗口對MFC窗口的AFX_MSGMAP_ENTRY結構體地址右鍵點擊 "Add windows message entry to Analyze"成員函數添加至分析列表
4.點擊菜單"Edit/Functions/Analyze Selected Function"選擇要分析的函數和輸出文件開始分析
5.分析完成后在[Local Types]窗口查看帶Class_vtable開頭的已識別結構體
6.對已分析過的函數匯編代碼按F5自動反匯編可以看到this指針及其引用已正確被替換成已識別的結構體
工作支持環境
Ida Pro 7.0
只支持Windows操作系統,X86架構輸入文件
編譯環境 Visual Studio 2017
QT環境版本5.6.0及vs插件
源代碼編譯方法
將git倉庫代碼克隆后復制至E:\git\WindowsResearch目錄，使用Visual Studio 2017打開"\retdec-master-build\retdec.sln"工程文件。
由于cmake生成緩存的原因,先生成下項目再還原代碼再次生成就可以重新編譯。若發現缺少文件則從llvmanalyzer.7z備份文件中還原丟失文件。
工具使用效果
分析之前：
分析之后：
