邱景 蘇小紅 馬培軍
摘 要:內(nèi)聯(lián)庫函數(shù)識別是二進(jìn)制代碼分析的難點問題之一。主要的挑戰(zhàn)來自在編譯優(yōu)化的作用下,內(nèi)聯(lián)庫函數(shù)在目標(biāo)函數(shù)中存在多態(tài)性和不連續(xù)性。本文構(gòu)建函數(shù)的執(zhí)行流圖,將內(nèi)聯(lián)庫函數(shù)識別問題轉(zhuǎn)化為執(zhí)行流圖子圖同構(gòu)測試問題。實驗中,對四個常被編譯器內(nèi)聯(lián)的字符串操作函數(shù),使用MSVC10和ICC14這兩個編譯器在5個開源軟件中進(jìn)行內(nèi)聯(lián)庫函數(shù)識別測試。實驗結(jié)果表明,本文方法可以有效識別二進(jìn)制代碼中的內(nèi)聯(lián)庫函數(shù)。
關(guān)鍵詞:二進(jìn)制代碼分析;內(nèi)聯(lián)庫函數(shù)識別;子圖同構(gòu)
中圖分類號:TP311 文獻(xiàn)標(biāo)識碼:A 文章編號:2095-2163(2015)05-
Inline Library Functions Identification in Binary Code
QIU Jing, SU Xiaohong, MA Peijun
(School of Computer Science and Technology, Harbin Institute of Technology, Harbin 150001,China)
Abstract: Inline library functions identification is one of the difficult issues in binary code analysis. The main challenge comes from the polymorphism and discontinuity of inlined functions due to compiler optimizations. The paper builds execution flow graphs of functions, converting inline library functions identification to subgraph isomorphism testings. In the evaluation, four string operation functions, which are often inlined by a compiler, are evaluated by using MSVC10 and ICC14 with five open source programs. Experimental results show that the proposed approach is effective in inline library functions identification.
Keywords: Binary Code Analysis; Inline Library Functions Identification; Subgraph Isomorphism
0 引 言
隨著計算機(jī)軟件業(yè)的不斷發(fā)展,計算機(jī)軟件安全日益引起人們關(guān)注。二進(jìn)制代碼分析是計算機(jī)軟件安全領(lǐng)域的一個重要手段。在分析某些無法獲取源代碼的軟件時,分析其二進(jìn)制代碼幾乎是唯一手段。人們很少直接分析二進(jìn)制代碼,因此一般都是先將機(jī)器代碼反匯編成匯編代碼。庫函數(shù)識別的作用在于可以直接將反匯編代碼中的大段代碼替換成可理解的符號(函數(shù)名),便于分析人員理解整個程序的反匯編代碼。在編譯優(yōu)化的作用下,內(nèi)聯(lián)庫函數(shù)在內(nèi)聯(lián)到目標(biāo)代碼后,形態(tài)可能發(fā)生變化。因此,內(nèi)聯(lián)庫函數(shù)識別存在兩個難點要解決。首先,為了對齊指令地址,或指令流水優(yōu)化,編譯器可能會調(diào)整一個函數(shù)的某些指令順序,造成內(nèi)聯(lián)庫函數(shù)字節(jié)不連續(xù)。其次,編譯器寄存器分配策略也會影響內(nèi)聯(lián)后的指令,使其發(fā)生變化。針對這兩個問題,本文基于執(zhí)行流圖來識別內(nèi)聯(lián)庫函數(shù)。
1 庫函數(shù)識別
1.1 執(zhí)行流圖
執(zhí)行流圖EFG (Execution Flow Graph) ,V代表指令集合, 代表指令之間執(zhí)行依賴關(guān)系。邊(vi, vj)表明vi早于vj的執(zhí)行。使用R/W 表示指令讀/寫的變量集合,D 表示指令的地址。
一個EFG中的邊有兩類。第一類邊在基本塊(單進(jìn)單出的指令序列)內(nèi)。對于基本塊內(nèi)的兩個點a, b, 如果滿足 , , 或者b為控制流轉(zhuǎn)移指令,則存在a到b的邊。 另一類在基本塊間。邊(a, b)滿足:(1) a和b分別在不同的基本塊B1和B2內(nèi);(2) a可以在基本塊B1 中最后執(zhí)行,b可以在基本塊B2中第一個執(zhí)行;(3) 在控制流圖中,B2是B1的后繼。
EFG的構(gòu)造分為兩步。首先,劃分函數(shù)的基本塊,構(gòu)造控制流圖。然后,在基本塊內(nèi)進(jìn)行數(shù)據(jù)依賴分析,得到局部EFG。最后,對于每對在控制流圖中直接相連的基本塊,連接其所對應(yīng)局部EFG中的出口點和入口點。對于局部EFG中的任意三點A, B, C,如果存在三條邊(A, B), (B, C), (A, C),則刪除邊(A, C),因為這條邊是冗余的。
1.2 指令編碼
指令編碼用來將一個指令轉(zhuǎn)換到一個標(biāo)準(zhǔn)形式。首先,一條指令通過下列步驟規(guī)范化來消除指令差別:
(1) 指令規(guī)范化。 使用reg1來表示指令操作數(shù)中的第一個寄存器,reg2表示第二個寄存器,以此類推。如“mov eax, ecx” “mov reg1, reg2”,“xor eax, eax” “xor reg1, reg1”。
(2) 內(nèi)存規(guī)范化。 使用M表示訪存操作數(shù),如“mov eax, [ebx]” “mov reg1, M”。
其次,用二元組SR=(m, r)表示消除差異后的指令,其中m表示指令助記符,r為操作數(shù)特征值。r中的數(shù)字,從高到低,表示操作數(shù)的類型。如r=1表示“op reg1”, r=11表示“op reg1, reg1”, r=21表示“op reg1, reg2”。表1給出了指令的所有可能特征值。
最后,SR=(m, r)通過調(diào)用函數(shù)ID(SR)=Hash(m) | (r<<16)轉(zhuǎn)換為一個32位數(shù)字,稱為此指令的ID。Hash()是一個字符串函數(shù),將不同的指令助記符映射到不同的16位整數(shù)。在同構(gòu)測試時,指令只要有相同的ID,即認(rèn)為它們是相等的。
1.3 識別
在庫函數(shù)集合F中識別識別目標(biāo)函數(shù)fT的過程如下:(1) 反匯編fT ,(2) 構(gòu)造fT的CFG,(3) 對于F每個內(nèi)聯(lián)庫函數(shù)fL:
構(gòu)造fT的EFG;
檢測GT中所有與fL的EFG同構(gòu)的子圖;
檢測每個檢測到的子圖是否可以外聯(lián)(參見本文之前的工作[1]);
④ 報告每個檢測到的可以外聯(lián)的子圖為一個庫函數(shù)。
2 實驗
2.1 設(shè)置
實驗所用開源程序列表如表2所示。相應(yīng)地,分別使用Microsoft Visual C++ 10 (MSVC)和Intel Compiler XE 14 (ICC)編譯,并生成調(diào)試信息。
由于源代碼和二進(jìn)制代碼間存在巨大差異,二進(jìn)制代碼中的內(nèi)聯(lián)函數(shù)的真實信息幾乎不可能獲知。內(nèi)聯(lián)函數(shù)和其余代碼之間沒有明顯分界。任何代碼片段都可以視為某個內(nèi)聯(lián)函數(shù)的實例。但由于實驗對象是開源軟件,因此在一個內(nèi)聯(lián)函數(shù)之后可以插入一些特殊代碼,就可以定位到內(nèi)聯(lián)函數(shù)的真實信息且不會影響內(nèi)聯(lián)函數(shù)的EFG。
從源代碼編譯得到的二進(jìn)制文件稱為原始文件集。從修改后的源代碼編譯得到的可執(zhí)行文件稱為修改的文件集。在修改的源代碼中,一些函數(shù)的隨機(jī)位置被插入宏“LIBV(P)”。P是一個指針或者一個變量的地址。在宏里,輸出庫函數(shù)的結(jié)果到屏幕,使得插入代碼不會被當(dāng)成死代碼。然后修改宏的定義來生成修改的二進(jìn)制文件集。strlen()的定義為“#define LIBV(P) printf("libvcode\%d", strlen((char*)(P)))”。其他函數(shù)類似。printf的特殊格式有助于在匯編代碼中識別插入的代碼。 比如在識別strlen()中,代碼
在反匯編代碼中為
其中,位于loc_40B600和push eax之間的代碼是strlen()的一個實例。
實驗中的內(nèi)聯(lián)庫函數(shù)有strlen(), strcpy(), strcmp(), memcmp()。這些函數(shù)經(jīng)常被MSVC內(nèi)聯(lián)。相應(yīng)的源代碼來自“\Microsoft Visual Studio 10.0\VC\crt\src”。匯編代碼來自Visual C++ 10,使用參數(shù)/FAcs編譯(輸出匯編代碼,機(jī)器代碼和源代碼)。編譯使用這些庫函數(shù)的樣本代碼并提取內(nèi)聯(lián)的代碼。
對于原始文件集,如果識別出的內(nèi)聯(lián)函數(shù)在源代碼中能找到,則認(rèn)為識別結(jié)果是正確的。原型工具在原始二進(jìn)制文件集中識別所有4個內(nèi)聯(lián)函數(shù)。函數(shù)strlen(), strcpy(), strcmp()在C/C++程序中常見。在C++中標(biāo)準(zhǔn)字符串類的操作包含了這些C字符串函數(shù)。在原始二進(jìn)制文件集的實驗中,這些識別結(jié)果也會被認(rèn)為是正確的,即使識別出的函數(shù)沒有在源代碼中顯式使用。對于修改的文件集,只統(tǒng)計以“l(fā)ibvcode%d”為格式化字符串的printf結(jié)尾的識別結(jié)果。內(nèi)聯(lián)函數(shù)的真實情況由IDA的一個插件來統(tǒng)計,通過掃描以“l(fā)ibvcode%d”為格式化字符串的printf得到。
由表3中可見,除了WinMerge,其余程序的每種內(nèi)聯(lián)函數(shù)數(shù)量都不相同。因為一種內(nèi)聯(lián)函數(shù)的文件集是通過改變插入宏的定義來生成的,這就使得理論上不同內(nèi)聯(lián)函數(shù)的數(shù)量應(yīng)該一致。但是,一個內(nèi)聯(lián)函數(shù)實例的數(shù)量在沒有檢查二進(jìn)制代碼前是不確定的,因為某些被插入宏的短的目標(biāo)函數(shù)可能會被編譯器內(nèi)聯(lián)。另一方面,源代碼中插入的宏在編譯預(yù)處理階段被展開,增加了一個目標(biāo)函數(shù)的大小。因此,一些目標(biāo)函數(shù)在宏定義為一種內(nèi)聯(lián)函數(shù)時會被內(nèi)聯(lián),而在宏定義為另一種內(nèi)聯(lián)庫函數(shù)時則不會被內(nèi)聯(lián)。
2.2 實驗結(jié)果
表4和表5分別給出了MSVC和ICC在原始文件集上 查準(zhǔn)率。表中的'-'表示無法計算值。原始文件集里的內(nèi)聯(lián)庫函數(shù)的真實情況未知。因此在表4和表5中查全率無法給出。表6給出了MSVC編譯的修改的文件集的查全率和查準(zhǔn)率。WinMerge中的strcmp的查準(zhǔn)率是空的,因為strcmp在WinMerge中沒有被內(nèi)聯(lián)。ICC編譯的修改的文件集的實驗結(jié)果沒有列出,因為沒有發(fā)現(xiàn)任何結(jié)果。
2.3 討論
2.3.1 查準(zhǔn)率
表4表明原型工具可以準(zhǔn)確地識別內(nèi)聯(lián)函數(shù)。在原始文件集中僅有少數(shù)誤報。誤報是因為工具無法區(qū)分字符串函數(shù)的寬字節(jié)版本和非寬字節(jié)版本。類似wscmp()被誤認(rèn)為strcmp()。兩者之間代碼的差別就在于操作數(shù)的大小(寬字節(jié)版本16位,非字節(jié)版本8位)不同。而在指令編碼中,不考慮操作數(shù)的大小,因此導(dǎo)致了上述誤報。
2.3.2 查全率
如表6所示,在修改的文件集中,除了memcmp(),查準(zhǔn)率都很高。這是因為memcmp()的指令發(fā)生了改變。代碼如下所示。
而從編譯器提取的memcmp()的代碼如下。
通常,有三個原因造成漏報。首先,函數(shù)的反匯編代碼可能是不完整的。在反匯編中,工具在遇到間接跳轉(zhuǎn)時停止反匯編。在修改的文件集中,有些代碼是插入到了一個case語句中。因為switch/case語句常被編譯器翻譯為間接跳轉(zhuǎn),因此這些內(nèi)聯(lián)函數(shù)沒有被工具識別。
其次,在編譯器優(yōu)化后,一個內(nèi)聯(lián)函數(shù)可能有不同的指令序列。大多數(shù)的漏報都是由于這個原因。比如,編譯器可能將一條指令替換為語義等價的指令。如test eax, eax可以替換為cmp eax, ebx,當(dāng)ebx值為0時。內(nèi)聯(lián)函數(shù)的參數(shù)可以通過寄存器或內(nèi)存來傳遞。傳遞方式也會影響一個內(nèi)聯(lián)函數(shù)的指令。memcmp()參數(shù)count保存到了局部變量var_268中,而在庫函數(shù)中則是一個寄存器中。其他優(yōu)化,如循環(huán)判斷外提和循環(huán)展開也會影響識別結(jié)果。
特別地,一個內(nèi)聯(lián)函數(shù)可能消失在二進(jìn)制代碼中。一個表達(dá)式的結(jié)果可能會在編譯時被編譯器計算出。如strlen()的參數(shù)是一個固定字符串,編譯器會直接計算出字符串的長度,而不會生成調(diào)用strlen()的代碼。因此,一些內(nèi)聯(lián)函數(shù)可能在修改后的文件集中沒有出現(xiàn)在期望的位置,也就沒被工具發(fā)現(xiàn)。
最后,一個內(nèi)聯(lián)函數(shù)在不同的編譯器編譯后可能有不同的指令序列。在實驗中,因為內(nèi)聯(lián)函數(shù)的代碼是從MSVC中提取,這些代碼可能會和其他編譯器編譯的完全不同。在ICC編譯的代碼里, 由于某些未知原因,strlen()和strcpy()不總是內(nèi)聯(lián)。memcmp()和strcmp()被ICC內(nèi)聯(lián),但是對其編譯后的二進(jìn)制代碼卻與MSVC編譯的有所不同。因此,和MSVC編譯的原始文件集的實驗結(jié)果對比,ICC編譯的原始文件集中卻只有很少的內(nèi)聯(lián)函數(shù)獲得識別,如表5所示。
3 相關(guān)工作
最負(fù)盛名的的庫函數(shù)識別技術(shù)是IDA FLIRT[2]。使用字節(jié)模式匹配算法來判斷一個目標(biāo)函數(shù)是否與IDA 已知的簽名匹配。DCC[3]類似于FLIRT。Hancock[4]擴(kuò)展了FLIRT技術(shù),提出一個庫函數(shù)引用啟發(fā)規(guī)則,認(rèn)為一個函數(shù)如果在一個庫函數(shù)中被靜態(tài)調(diào)用,那么該函數(shù)也是庫函數(shù)。這些方法的主要缺陷在于一個函數(shù)只有頭n個字節(jié)作為匹配模式。盡管通過增大n的大小,精度可以很容易獲得提高。但是不能保證導(dǎo)入所有庫函數(shù)。UNSTRIP[5]通過系統(tǒng)調(diào)用接口即可識別在二進(jìn)制代碼中的包裹函數(shù)(Wrapper Function)。盡管如此,這個方法卻只是局限于識別包裹函數(shù),因為一個庫函數(shù)可能沒有call指令。
最近,文獻(xiàn)[6]提出了一個二進(jìn)制代碼搜索的技術(shù)。為了計算函數(shù)間的相似性,即將函數(shù)分解為連續(xù),且簡短的代碼序列。本文方法和該文獻(xiàn)中的方法都需要和編譯器優(yōu)化。而且,文獻(xiàn)[6]中的方法的最大限制是可能產(chǎn)生差的結(jié)果,當(dāng)匹配擁有低于100基本塊的函數(shù)。
Saed等人提出了一個通過匹配語義整合圖的短路徑(軌跡)識別二進(jìn)制代碼中復(fù)用函數(shù)的新技術(shù)[7]。一個語義整合圖整合了控制流圖,寄存器流圖,函數(shù)調(diào)用圖。盡管這一方法和本文方法相同之處都是基于圖,但是其中的匹配過程卻和本文完全不同。另外,該法在圖上定義了不同類型的軌跡,并且是使用圖編輯距離來衡量兩個圖的相似度。
4 結(jié)束語
識別不連續(xù)字節(jié)或有多個變種的庫函數(shù)是困難的。本文介紹了一個識別內(nèi)聯(lián)庫函數(shù)的新方法。方法的新穎性在于將庫函數(shù)識別問題轉(zhuǎn)化為EFG子圖同構(gòu)問題。在一些流行軟件上設(shè)計了一定仿真,從而驗證了本文方法的有效性。如何加速子圖同構(gòu)測試將是本文下一步的重點研究工作。
參考文獻(xiàn):
[1] QIU J, SU X, MA P. Library functions identification in binary code by using graph isomorphism testings[C]//Software Analysis, Evolution and Reengineering (SANER), 2015 IEEE 22nd International Conference on, Montreal, Canada: IEEE, 2015: 261-270.
[2] Hex-Rays. Fast library identification and recognition technology[OL/EB]. (1997) [2015-7-17]. https://www.hex-rays.com/products/ida/tech/flirt/in_depth.shtml.
[3] Van Emmerik M. Signatures for library functions in executable files[M]. Brisbane, Australia: Queensland University of Technology, 1994.
[4] GRIFFIN K, SCHNEIDER S, HU X, et al. Automatic generation of string signatures for malware detection[C]//Recent Advances in Intrusion Detection, Saint-Malo, France: Springer Berlin Heidelberg, 2009: 101-120.
[5] JACOBSON E R, ROSENBLUM N, MILLER B P. Labeling library functions in stripped binaries[C]//Proceedings of the 10th ACM SIGPLAN-SIGSOFT workshop on Program analysis for software tools, New York, NY, USA: ACM, 2011: 1-8.
[6] DAVID Y, YAHAV E. Tracelet-based code search in executables[C]// Proceedings of the 35th ACM SIGPLAN Conference on Programming Language Design and Implementation, New York, NY, ACM, 2014, 49(6): 349-360.
[7] ALRABAEE S, SHIRANI P, WANG L, et al. SIGMA: A semantic integrated graph matching approach for identifying reused functions in binary code[J]. Digital Investigation, 2015, 12: S61-S71.