二進(jìn)制代碼內(nèi)聯(lián)庫函數(shù)識(shí)別

邱景　蘇小紅　馬培軍

摘 要：內(nèi)聯(lián)庫函數(shù)識(shí)別是二進(jìn)制代碼分析的難點(diǎ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ù)識(shí)別問題轉(zhuǎn)化為執(zhí)行流圖子圖同構(gòu)測(cè)試問題。實(shí)驗(yàn)中，對(duì)四個(gè)常被編譯器內(nèi)聯(lián)的字符串操作函數(shù)，使用MSVC10和ICC14這兩個(gè)編譯器在5個(gè)開源軟件中進(jìn)行內(nèi)聯(lián)庫函數(shù)識(shí)別測(cè)試。實(shí)驗(yàn)結(jié)果表明，本文方法可以有效識(shí)別二進(jìn)制代碼中的內(nèi)聯(lián)庫函數(shù)。

關(guān)鍵詞：二進(jìn)制代碼分析；內(nèi)聯(lián)庫函數(shù)識(shí)別；子圖同構(gòu)

中圖分類號(hào)：TP311 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：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ì)算機(jī)軟件業(yè)的不斷發(fā)展，計(jì)算機(jī)軟件安全日益引起人們關(guān)注。二進(jìn)制代碼分析是計(jì)算機(jī)軟件安全領(lǐng)域的一個(gè)重要手段。在分析某些無法獲取源代碼的軟件時(shí)，分析其二進(jìn)制代碼幾乎是唯一手段。人們很少直接分析二進(jìn)制代碼，因此一般都是先將機(jī)器代碼反匯編成匯編代碼。庫函數(shù)識(shí)別的作用在于可以直接將反匯編代碼中的大段代碼替換成可理解的符號(hào)（函數(shù)名），便于分析人員理解整個(gè)程序的反匯編代碼。在編譯優(yōu)化的作用下，內(nèi)聯(lián)庫函數(shù)在內(nèi)聯(lián)到目標(biāo)代碼后，形態(tài)可能發(fā)生變化。因此，內(nèi)聯(lián)庫函數(shù)識(shí)別存在兩個(gè)難點(diǎn)要解決。首先，為了對(duì)齊指令地址，或指令流水優(yōu)化，編譯器可能會(huì)調(diào)整一個(gè)函數(shù)的某些指令順序，造成內(nèi)聯(lián)庫函數(shù)字節(jié)不連續(xù)。其次，編譯器寄存器分配策略也會(huì)影響內(nèi)聯(lián)后的指令，使其發(fā)生變化。針對(duì)這兩個(gè)問題，本文基于執(zhí)行流圖來識(shí)別內(nèi)聯(lián)庫函數(shù)。

1 庫函數(shù)識(shí)別

1.1 執(zhí)行流圖

執(zhí)行流圖EFG （Execution Flow Graph） ，V代表指令集合， 代表指令之間執(zhí)行依賴關(guān)系。邊（vi， vj）表明vi早于vj的執(zhí)行。使用R/W 表示指令讀/寫的變量集合，D 表示指令的地址。

一個(gè)EFG中的邊有兩類。第一類邊在基本塊（單進(jìn)單出的指令序列）內(nèi)。對(duì)于基本塊內(nèi)的兩個(gè)點(diǎn)a， b， 如果滿足 ， ， 或者b為控制流轉(zhuǎn)移指令，則存在a到b的邊。 另一類在基本塊間。邊（a， b）滿足：（1） a和b分別在不同的基本塊B1和B2內(nèi)；（2） a可以在基本塊B1 中最后執(zhí)行，b可以在基本塊B2中第一個(gè)執(zhí)行；（3） 在控制流圖中，B2是B1的后繼。

EFG的構(gòu)造分為兩步。首先，劃分函數(shù)的基本塊，構(gòu)造控制流圖。然后，在基本塊內(nèi)進(jìn)行數(shù)據(jù)依賴分析，得到局部EFG。最后，對(duì)于每對(duì)在控制流圖中直接相連的基本塊，連接其所對(duì)應(yīng)局部EFG中的出口點(diǎn)和入口點(diǎn)。對(duì)于局部EFG中的任意三點(diǎn)A， B， C，如果存在三條邊（A， B）， （B， C）， （A， C），則刪除邊（A， C），因?yàn)檫@條邊是冗余的。

1.2 指令編碼

指令編碼用來將一個(gè)指令轉(zhuǎn)換到一個(gè)標(biāo)準(zhǔn)形式。首先，一條指令通過下列步驟規(guī)范化來消除指令差別：

（1） 指令規(guī)范化。 使用reg1來表示指令操作數(shù)中的第一個(gè)寄存器，reg2表示第二個(gè)寄存器，以此類推。如“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)換為一個(gè)32位數(shù)字，稱為此指令的ID。Hash（）是一個(gè)字符串函數(shù)，將不同的指令助記符映射到不同的16位整數(shù)。在同構(gòu)測(cè)試時(shí)，指令只要有相同的ID，即認(rèn)為它們是相等的。

1.3 識(shí)別

在庫函數(shù)集合F中識(shí)別識(shí)別目標(biāo)函數(shù)fT的過程如下：（1） 反匯編fT ，（2） 構(gòu)造fT的CFG，（3） 對(duì)于F每個(gè)內(nèi)聯(lián)庫函數(shù)fL：

構(gòu)造fT的EFG；

檢測(cè)GT中所有與fL的EFG同構(gòu)的子圖；

檢測(cè)每個(gè)檢測(cè)到的子圖是否可以外聯(lián)（參見本文之前的工作[1]）；

④ 報(bào)告每個(gè)檢測(cè)到的可以外聯(lián)的子圖為一個(gè)庫函數(shù)。

2 實(shí)驗(yàn)

2.1 設(shè)置

實(shí)驗(yàn)所用開源程序列表如表2所示。相應(yīng)地，分別使用Microsoft Visual C++ 10 （MSVC）和Intel Compiler XE 14 （ICC）編譯，并生成調(diào)試信息。

由于源代碼和二進(jìn)制代碼間存在巨大差異，二進(jìn)制代碼中的內(nèi)聯(lián)函數(shù)的真實(shí)信息幾乎不可能獲知。內(nèi)聯(lián)函數(shù)和其余代碼之間沒有明顯分界。任何代碼片段都可以視為某個(gè)內(nèi)聯(lián)函數(shù)的實(shí)例。但由于實(shí)驗(yàn)對(duì)象是開源軟件，因此在一個(gè)內(nèi)聯(lián)函數(shù)之后可以插入一些特殊代碼，就可以定位到內(nèi)聯(lián)函數(shù)的真實(shí)信息且不會(huì)影響內(nèi)聯(lián)函數(shù)的EFG。

從源代碼編譯得到的二進(jìn)制文件稱為原始文件集。從修改后的源代碼編譯得到的可執(zhí)行文件稱為修改的文件集。在修改的源代碼中，一些函數(shù)的隨機(jī)位置被插入宏“LIBV（P）”。P是一個(gè)指針或者一個(gè)變量的地址。在宏里，輸出庫函數(shù)的結(jié)果到屏幕，使得插入代碼不會(huì)被當(dāng)成死代碼。然后修改宏的定義來生成修改的二進(jìn)制文件集。strlen（）的定義為“#define LIBV（P） printf（"libvcode＼%d"， strlen（（char*）（P）））”。其他函數(shù)類似。printf的特殊格式有助于在匯編代碼中識(shí)別插入的代碼。 比如在識(shí)別strlen（）中，代碼

在反匯編代碼中為

其中，位于loc_40B600和push eax之間的代碼是strlen（）的一個(gè)實(shí)例。

實(shí)驗(yàn)中的內(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)的代碼。

對(duì)于原始文件集，如果識(shí)別出的內(nèi)聯(lián)函數(shù)在源代碼中能找到，則認(rèn)為識(shí)別結(jié)果是正確的。原型工具在原始二進(jìn)制文件集中識(shí)別所有4個(gè)內(nèi)聯(lián)函數(shù)。函數(shù)strlen（）， strcpy（）， strcmp（）在C/C++程序中常見。在C++中標(biāo)準(zhǔn)字符串類的操作包含了這些C字符串函數(shù)。在原始二進(jìn)制文件集的實(shí)驗(yàn)中，這些識(shí)別結(jié)果也會(huì)被認(rèn)為是正確的，即使識(shí)別出的函數(shù)沒有在源代碼中顯式使用。對(duì)于修改的文件集，只統(tǒng)計(jì)以“l(fā)ibvcode%d”為格式化字符串的printf結(jié)尾的識(shí)別結(jié)果。內(nèi)聯(lián)函數(shù)的真實(shí)情況由IDA的一個(gè)插件來統(tǒng)計(jì)，通過掃描以“l(fā)ibvcode%d”為格式化字符串的printf得到。

由表3中可見，除了WinMerge，其余程序的每種內(nèi)聯(lián)函數(shù)數(shù)量都不相同。因?yàn)橐环N內(nèi)聯(lián)函數(shù)的文件集是通過改變插入宏的定義來生成的，這就使得理論上不同內(nèi)聯(lián)函數(shù)的數(shù)量應(yīng)該一致。但是，一個(gè)內(nèi)聯(lián)函數(shù)實(shí)例的數(shù)量在沒有檢查二進(jìn)制代碼前是不確定的，因?yàn)槟承┍徊迦牒甑亩痰哪繕?biāo)函數(shù)可能會(huì)被編譯器內(nèi)聯(lián)。另一方面，源代碼中插入的宏在編譯預(yù)處理階段被展開，增加了一個(gè)目標(biāo)函數(shù)的大小。因此，一些目標(biāo)函數(shù)在宏定義為一種內(nèi)聯(lián)函數(shù)時(shí)會(huì)被內(nèi)聯(lián)，而在宏定義為另一種內(nèi)聯(lián)庫函數(shù)時(shí)則不會(huì)被內(nèi)聯(lián)。

2.2 實(shí)驗(yàn)結(jié)果

表4和表5分別給出了MSVC和ICC在原始文件集上 查準(zhǔn)率。表中的'-'表示無法計(jì)算值。原始文件集里的內(nèi)聯(lián)庫函數(shù)的真實(shí)情況未知。因此在表4和表5中查全率無法給出。表6給出了MSVC編譯的修改的文件集的查全率和查準(zhǔn)率。WinMerge中的strcmp的查準(zhǔn)率是空的，因?yàn)閟trcmp在WinMerge中沒有被內(nèi)聯(lián)。ICC編譯的修改的文件集的實(shí)驗(yàn)結(jié)果沒有列出，因?yàn)闆]有發(fā)現(xiàn)任何結(jié)果。

2.3 討論

2.3.1 查準(zhǔn)率

表4表明原型工具可以準(zhǔn)確地識(shí)別內(nèi)聯(lián)函數(shù)。在原始文件集中僅有少數(shù)誤報(bào)。誤報(bào)是因?yàn)楣ぞ邿o法區(qū)分字符串函數(shù)的寬字節(jié)版本和非寬字節(jié)版本。類似wscmp（）被誤認(rèn)為strcmp（）。兩者之間代碼的差別就在于操作數(shù)的大小（寬字節(jié)版本16位，非字節(jié)版本8位）不同。而在指令編碼中，不考慮操作數(shù)的大小，因此導(dǎo)致了上述誤報(bào)。

2.3.2 查全率

如表6所示，在修改的文件集中，除了memcmp（），查準(zhǔn)率都很高。這是因?yàn)閙emcmp（）的指令發(fā)生了改變。代碼如下所示。

而從編譯器提取的memcmp（）的代碼如下。

通常，有三個(gè)原因造成漏報(bào)。首先，函數(shù)的反匯編代碼可能是不完整的。在反匯編中，工具在遇到間接跳轉(zhuǎn)時(shí)停止反匯編。在修改的文件集中，有些代碼是插入到了一個(gè)case語句中。因?yàn)閟witch/case語句常被編譯器翻譯為間接跳轉(zhuǎn)，因此這些內(nèi)聯(lián)函數(shù)沒有被工具識(shí)別。

其次，在編譯器優(yōu)化后，一個(gè)內(nèi)聯(lián)函數(shù)可能有不同的指令序列。大多數(shù)的漏報(bào)都是由于這個(gè)原因。比如，編譯器可能將一條指令替換為語義等價(jià)的指令。如test eax， eax可以替換為cmp eax， ebx，當(dāng)ebx值為0時(shí)。內(nèi)聯(lián)函數(shù)的參數(shù)可以通過寄存器或內(nèi)存來傳遞。傳遞方式也會(huì)影響一個(gè)內(nèi)聯(lián)函數(shù)的指令。memcmp（）參數(shù)count保存到了局部變量var_268中，而在庫函數(shù)中則是一個(gè)寄存器中。其他優(yōu)化，如循環(huán)判斷外提和循環(huán)展開也會(huì)影響識(shí)別結(jié)果。

特別地，一個(gè)內(nèi)聯(lián)函數(shù)可能消失在二進(jìn)制代碼中。一個(gè)表達(dá)式的結(jié)果可能會(huì)在編譯時(shí)被編譯器計(jì)算出。如strlen（）的參數(shù)是一個(gè)固定字符串，編譯器會(huì)直接計(jì)算出字符串的長(zhǎng)度，而不會(huì)生成調(diào)用strlen（）的代碼。因此，一些內(nèi)聯(lián)函數(shù)可能在修改后的文件集中沒有出現(xiàn)在期望的位置，也就沒被工具發(fā)現(xiàn)。

最后，一個(gè)內(nèi)聯(lián)函數(shù)在不同的編譯器編譯后可能有不同的指令序列。在實(shí)驗(yàn)中，因?yàn)閮?nèi)聯(lián)函數(shù)的代碼是從MSVC中提取，這些代碼可能會(huì)和其他編譯器編譯的完全不同。在ICC編譯的代碼里， 由于某些未知原因，strlen（）和strcpy（）不總是內(nèi)聯(lián)。memcmp（）和strcmp（）被ICC內(nèi)聯(lián)，但是對(duì)其編譯后的二進(jìn)制代碼卻與MSVC編譯的有所不同。因此，和MSVC編譯的原始文件集的實(shí)驗(yàn)結(jié)果對(duì)比，ICC編譯的原始文件集中卻只有很少的內(nèi)聯(lián)函數(shù)獲得識(shí)別，如表5所示。

3 相關(guān)工作

最負(fù)盛名的的庫函數(shù)識(shí)別技術(shù)是IDA FLIRT[2]。使用字節(jié)模式匹配算法來判斷一個(gè)目標(biāo)函數(shù)是否與IDA 已知的簽名匹配。DCC[3]類似于FLIRT。Hancock[4]擴(kuò)展了FLIRT技術(shù)，提出一個(gè)庫函數(shù)引用啟發(fā)規(guī)則，認(rèn)為一個(gè)函數(shù)如果在一個(gè)庫函數(shù)中被靜態(tài)調(diào)用，那么該函數(shù)也是庫函數(shù)。這些方法的主要缺陷在于一個(gè)函數(shù)只有頭n個(gè)字節(jié)作為匹配模式。盡管通過增大n的大小，精度可以很容易獲得提高。但是不能保證導(dǎo)入所有庫函數(shù)。UNSTRIP[5]通過系統(tǒng)調(diào)用接口即可識(shí)別在二進(jìn)制代碼中的包裹函數(shù)（Wrapper Function）。盡管如此，這個(gè)方法卻只是局限于識(shí)別包裹函數(shù)，因?yàn)橐粋€(gè)庫函數(shù)可能沒有call指令。

最近，文獻(xiàn)[6]提出了一個(gè)二進(jìn)制代碼搜索的技術(shù)。為了計(jì)算函數(shù)間的相似性，即將函數(shù)分解為連續(xù)，且簡(jiǎn)短的代碼序列。本文方法和該文獻(xiàn)中的方法都需要和編譯器優(yōu)化。而且，文獻(xiàn)[6]中的方法的最大限制是可能產(chǎn)生差的結(jié)果，當(dāng)匹配擁有低于100基本塊的函數(shù)。

Saed等人提出了一個(gè)通過匹配語義整合圖的短路徑（軌跡）識(shí)別二進(jìn)制代碼中復(fù)用函數(shù)的新技術(shù)[7]。一個(gè)語義整合圖整合了控制流圖，寄存器流圖，函數(shù)調(diào)用圖。盡管這一方法和本文方法相同之處都是基于圖，但是其中的匹配過程卻和本文完全不同。另外，該法在圖上定義了不同類型的軌跡，并且是使用圖編輯距離來衡量?jī)蓚€(gè)圖的相似度。

4 結(jié)束語

識(shí)別不連續(xù)字節(jié)或有多個(gè)變種的庫函數(shù)是困難的。本文介紹了一個(gè)識(shí)別內(nèi)聯(lián)庫函數(shù)的新方法。方法的新穎性在于將庫函數(shù)識(shí)別問題轉(zhuǎn)化為EFG子圖同構(gòu)問題。在一些流行軟件上設(shè)計(jì)了一定仿真，從而驗(yàn)證了本文方法的有效性。如何加速子圖同構(gòu)測(cè)試將是本文下一步的重點(diǎn)研究工作。

參考文獻(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.