基于特征字符串動態引用頻率的庫引用識別

蔡建章 ，魏 強 ，史建忠

CAI Jianzhang1，2,WEI Qiang1，2,SHI Jianzhong2

1.解放軍信息工程大學，鄭州 450002

2.北方計算中心，北京 100094

1.Information Engineering University of PLA,Zhengzhou 450002,China

2.North Computing Center,Beijing 100094,China

1 引言

庫引用可以有效減少軟件開發成本、提高軟件開發效率，但在軟件的升級和維護方面存在劣勢，同時被引用庫的漏洞會導致生成的二進制軟件存在安全隱患，因此有效識別庫引用在知識產權保護、二進制軟件的安全測試等方面都具有重要的意義。目前庫引用識別主要采用特征字符串、標準壓縮距離、控制流程圖[1]、庫中函數的數字簽名等方法進行識別（http：//www.hex-rays.com/products/ida/flirt.shtml），但上述方法前期工作量大，且對壓縮、混淆技術敏感。

程序胎記作為程序獨一無二的特征用于代碼剽竊、軟件專利保護、惡意代碼的變種、代碼克隆等軟件相似性的識別[2]，其描述如下：

定義1設 f為程序的特征提取函數，p，q為程序，則 f(p)稱為程序 p的胎記需滿足如下條件：

（1）f(p)只能 p本身獲得；

（2）q如果是 p的拷貝，則 f(p)=f(q)。

軟件相似性識別采用相似性函數對程序胎記進行計算，其描述如下：

定義2設程序 p，q的胎記為 f(p)=a，f(q)=b，函數sim(a，b)∈[0，1]描述a和b之間的相似性，則軟件相似性識別定義為程序胎記提取過程和相似性識別過程，記作：（1）f(p)=a ，f(q)=b ；（2）sim(a，b)∈[0，1]。

庫引用識別可以看作程序包容性問題，可以采用軟件相似性進行描述，即通過相似性函數對程序胎記進行相似度的計算從而識別庫引用，但庫引用識別的相似性函數跟定義2描述的相似性函數有所區別。如果二進制程序 p引用了源碼庫q，則相同的程序胎記提取函數f使得 f(p)=a，f(q′)=b（q′是q編譯生成的二進制），那么必須滿足a∩b≈b，因此庫引用識別可作如下描述：

定義3對于目標二進制 p和要判定的引用庫q，設 f(p)=a、f(q′)=b是 p和 q′的胎記（q′是 q編譯生成的二進制），函數 sim((a∩b)，b)∈[0，1]描述 a∩b和 b之間的相似性，則庫引用識別定義為程序胎記提取過程和相似性識別過程，記作：（1）f(p)=a ，f(q′)=b ；（2）sim((a∩b)，b)∈[0，1]。

本文提出的程序胎記為引用庫中的特征字符串及特征字符串在程序動態執行路徑中出現的頻率組成的向量集合，其提取過程和用于庫引用識別的相似函數如下：以strings腳本提取引用庫q′中的可打印字符串集合{S1,S2,…,Sn}；對于給定的輸入集合 I={I1,I2,…,Ik}，通過動態二進制插樁分析其能夠達到最大代碼覆蓋率的最小輸入集合 I′={I′1,I′2,…,I′k} ；通過動態二進制插樁分別獲得 p對應I′中元素的k個向量集合，其中 S為字符串集合i{S1,S2,…，Sn}中的元素，Ci為Si在 p執行路徑中出現的頻數，q′對應I′中元素的k個向量集合，Sj為字符串集合{S1,S2,…，Sn}中的元素，Cj為Sj在q′執行路徑中出現的頻數；相似性函數采用輸入集合 {I′1,I′2,…,I′k}對應的向量集合之間的相似度，將相似度的均值作為庫引用的最終識別，即分別計算：

2 相關工作

庫引用可以看作程序包容性問題，可以采用軟件相似性進行描述，現有的軟件相似性識別技術從程序分析的角度大體可以劃分為六類，其程序胎記和相似性函數如下：基于字節碼級的識別技術[3]，通過標準壓縮距離對惡意軟件進行分類，基本思想是如果惡意軟件具有相似性，則在壓縮函數的滑動窗口能夠容納比較的二者的情況下其壓縮包的大小接近于單個程序的壓縮包；基于指令級的識別技術[4-6]，文獻[4]通過k-gram算法構建滑動窗口為k的指令序列集合，采用Dice系數進行集合相似度的判定，文獻[5]采用變化域中的常量值集合、函數調用序列集合、繼承關系集合、引用類集合作為程序胎記，其中變化域中的常量值集合是指令的操作數集合，采用Dice系數進行集合相似度的判定，文獻[6]采用抽象語法樹作為程序胎記進行代碼剽竊的檢測，相似性算法包括樹編輯距離和最大公共子樹；基于基本塊的識別技術[7]，在無壓縮、混淆的情況下忽略控制流程圖邊得到的基本塊集合的編輯距離識別函數的相似性；基于API調用序列的識別技術[8-9]，文獻[8]通過每個函數k深度的API調用組成一個集合，函數的相似性利用API調用的個數占通常的API函數的比率進行識別，程序的相似性識別通過函數相似性矩陣進行測量，文獻[9]通過動態API的調用及其頻數構建序列集合作為程序胎記；基于控制流程圖的識別技術[10-13]，文獻[10]通過函數控制流程圖中基本塊的個數，連接基本塊的邊數，基本塊中子函數調用的個數作為函數簽名來逐步完善函數的映射集合實現二進制相似性比較，文獻[11]利用最大公共誘導子圖實現程序識別，文獻[12]通過控制流程圖的結構化信息檢測蠕蟲的變種，并通過k個節點子圖的截取和對14種指令的著色改進匹配的效率和可靠性，文獻[13]通過動態執行程序得到執行路徑經過SEQUITUR壓縮得到的上下文無關文法，從中得到一個有向無環圖作為程序胎記，采用最大公共子圖進行相似性判定；基于數據流的識別技術[14]，通過值集合分析（Value Set Analysis）識別和歸類惡意代碼，其選擇庫調用、跳轉、函數入口其中的一個或者多個的組合生成的值集合作為程序胎記。

3 特征字符串動態引用頻率提取和相似性函數

利用現有的程序胎記和相似性函數進行庫引用識別有以下不足之處：一是現有靜態程序胎記無法有效應對混淆技術，對編譯優化敏感；二是現有的動態程序胎記由于單條程序執行路徑導致識別的可信性不足；三是現有的相似性函數無法準確描述庫引用識別的特征。本文提出以特征字符串動態引用頻率作為程序胎記，其能夠有效刻畫程序的語義特征，相對于現有的程序胎記其可靠性和識別率均有很大提高，庫引用識別的相似性函數則對集合包容性識別算法加以改進，通過代碼覆蓋率的提高增強庫引用識別的可信性。庫引用識別的算法描述如下：p代表待檢測的二進制應用；q代表待檢測的引用庫；q′代表引用庫生成的二進制文件；Cq′={string1，string2，…，stringm}代表引用庫的特征字符串；I={I1,I2,…,Ik}代表輸入集合。

算法形式化描述分為以下部分：第一是將q編譯為q′，然后從q′中提取可打印字符串Cq′作為特征字符串；第二是通過dbi的基本塊操作獲得輸入集合I能夠達到q′的最大代碼覆蓋率的輸入集合 I′；第三是對應 I′集合的每個元素i，如果特定指令的特定操作數指向的內容屬于Cq′中的元素，則將其寫入 p、q′對應的文件ek和 fk；第四是通過對ek和 fk文件內容的排序后的頻數統計形成向量＜Si，Ci＞，＜Sj，Cj＞的集合和；第五是采用引言中描述的程序包容性識別算法的改進實現相似性函數，并取m個集合對的相似度的均值作為最終庫引用識別的判定。

4 算法實現

4.1 特征字符串提取Cq′

選取引用庫q的目標二進制文件q′的可打印字符串作為特征字符串的初始集合。引用庫q中常量值、提示字符串以及函數參數中的指示字符串是q′可打印字符串的子集，如果 p庫引用q，則無論 p采用什么類型的混淆和編譯優化技術，對于相同的輸入I在 p、q′程序的動態執行路徑中指令的操作數的集合和q′可打印字符串的交集近似相等。若 p引用庫q，則對于q′中可打印字符串作為匹配集合有以下要注意的問題：若p引用庫q，則對于q源碼級的大規模的增刪不具可操作性，這意味著q′中可打印字符串集合在 p中出現的概率大；對于q源碼級的小部分改動，識別率不會出現顯著降低，輸入集合產生的多條動態執行路徑也可以對識別率進行平衡；壓縮混淆、編譯器優化不會對識別產生影響。

類unix命令strings可以提取q′可打印字符串集合Cq′，記作 Cq′=strings(q′)。

4.2 生成輸入集合I′

代碼覆蓋率作為測試領域中的一個常見度量手段，衡量著目標程序的代碼執行路徑在測試過程中所覆蓋的范圍，對軟件相似性而言代碼覆蓋率高的動態程序胎記則意味著識別的可靠性。輸入集合I′的生成運用dbi的基本塊和執行路徑操作，結合貪心算法，生成樣本集合中能夠達到最大代碼覆蓋率的最小樣本集合I′，并能夠測試最小樣本集合I′針對特定模塊的代碼覆蓋率。

其中函數dbi(S[i])用于生成每個樣本所遍歷的基本塊組成的執行路徑，通過基本塊的首地址對其進行識別，并紀錄到對應的樣本執行路徑文件bblocks.out中；函數findbblmax返回所有執行路徑中包含基本塊最多的樣本文件maxbblsample；函數loadBlocks則返回樣本文件對應的執行路徑中所有的基本塊集合；delta返回在第一個基本塊集合中存在而不在下一個基本塊集合中存在的元素集合；函數append則將樣本或者基本塊加入到對應的集合；coveredBlock在某個模塊中的元素個數跟模塊的總的基本塊個數的比率作為某個模塊代碼覆蓋率的參考標準。

4.3 構建ek和 fk

對于輸入i∈I′，ek和 fk的構建基于DynamoRIO的基本塊方法。對于IA-32體系結構，在 p、q′對應的模塊地址中，Cq′中元素作為程序動態執行路徑中的指令操作數，其典型的指令應用集合為{mov、push}，操作數為mov指令的內存引用源操作數和push指令的立即操作數，如果得到的mov指令源操作數地址范圍屬于 p、q′模塊地址范圍且其指向的內容在字符串在集合Cq′中，或者push指令的立即操作數屬于 p、q′模塊地址范圍且以其為指針指向的內容在字符串在集合Cq′中，則將源操作數指向的內容寫入對應的文件ek和 fk，上述算法刻畫的指令如下：

圖1 構建ek和 fk

不同的編譯器和編譯選項對Cq′中的元素引用基本符合上述兩種指令，對于壓縮混淆方法上述算法也能夠有效應對。依據以上模塊地址區間、指令條件，操作數的條件設計如下：指令選取pus，mov；選擇push指令的立即操作數、mov指令的內存引用操作數，操作數限制在4字節；將指令地址、內存引用操作數的地址、立即操作數的值限制在 p、q′對應的可執行模塊中，插件設計如圖1所示。

4.4 生成和

對于文件ek和 fk，通過函數GenerateSet生成程序胎記和，GenerateSet由簡單的unix腳本文件實現，其設計如下：

sed'/^$/d'刪除ek和 fk中的空行；sort實現排序；uniq-c實現重復字符串的計數統計；comm-12實現集合的匹配。

4.5 相似性函數定義

5 實例分析

本文選擇某款引用庫xpdf3.0.2實現pdf文檔解析的商業二進制軟件 p進行程序胎記和相似性函數的驗證。選擇10個構造良好的樣本文件pdf文件，xpdf3.0.2的 xpdftotext.exe（vs2008）的基本塊個數為 23 801，10個樣本文件在xpdftotext.exe的基本塊個數為11 641，樣本集合的代碼覆蓋率為48.90%。本文采用特征字符串集合、二進制編輯距離、控制流程圖三種靜態程序胎記以及特征字符串的動態引用頻率作為程序胎記對 p進行庫引用的檢測，實驗結果表明特征字符串動態引用頻率的程序胎記有較高的庫引用識別率，對編譯優化、壓縮混淆技術有較強的應對能力，實驗結果如表1所示。

表1 庫引用識別率的比較 （%）

6 結論

本文提出了一種動態程序胎記，設計了其提取算法并分析了其應對編譯優化和壓縮混淆技術的能力，提出了用于庫引用識別的相似性函數，并成功運用動態程序胎記和庫引用的相似性函數對某商業軟件進行了庫引用的識別，實驗表明基于特征字符串動態引用頻率的程序胎記在庫引用識別中能夠有效對抗編譯優化、壓縮混淆。

[1]Hemel A，Kalleberg K T，Vermaas R，et al.Finding software license violations through binary code clone detection[C]//Proceedings of the 8th Working Conference on Mining Software Repositories，2011：63-72.

[2]Cesare S，Xiang Y.Software similarity and classification[M].[S.l.]：Springer，2012.

[3]Wehner S.Analyzing worms and network traffic using compression[J].Journal of Computer Security，2007，15（3）：303-320.

[4]Myles G，Collberg C.K-gram based software birthmarks[C]//Proceedings of the 2005 ACM Symposium on Applied Computing，2005：314-318.

[5]Tamada H，Nakamura M，Monden A，et al.Design and evaluation of birthmarks for detecting theft of java programs[C]//IASTED Conf on Software Engineering，2004：569-574.

[6]Son J W，Park S B，Park S Y.Program plagiarism detection using parse tree kernels[C]//PRICAI 2006：Trends in Artificial Intelligence.Berlin Heidelberg：Springer，2006：1000-1004.

[7]Gheorghescu M.An automated virus classification system[C]//Virus Bulletin Conference，2005：294-300.

[8]Choi S，Park H，Lim H，et al.A static birthmark of binary executables based on API call structure[C]//Advances in Computer Science.Berlin Heidelberg：Springer，2007：2-16.

[9]Tamada H，Okamoto K，Nakamura M，et al.Dynamic software birthmarks to detect the theft of windows applications[C]//International Symposium on Future Software Technology，2004.

[10]Flake H.Structural comparison of executable objects[C]//Proceedings of Detection of Intrusions and Malware&Vulnerability Assessment DIMVA，2004：161-173.

[11]Dullien T，Rolles R.Graph-based comparison of executable objects（English version）[C]//SSTIC，2005：1-3.

[12]Gao D，Reiter M K，Song D.Binhunt：automatically finding semantic differences in binary programs[C]//Information Systems Security.Berlin Heidelberg：Springer，2008：238-255.

[13]Myles G，Collberg C.Detecting software theft via whole program path birthmarks[C]//Information Security.Berlin Heidelberg：Springer，2004：404-415.

[14]Jhi Y C，Wang X，Jia X，et al.Value-based program characterization and its application to software plagiarism detection[C]//Proceedings of the 33rd International Conference on Software Engineering，2011：756-765.