基于特征字符串動態(tài)引用頻率的庫引用識別

蔡建章 ，魏 強(qiáng) ，史建忠

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

1.解放軍信息工程大學(xué)，鄭州 450002

2.北方計(jì)算中心，北京 100094

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

2.North Computing Center,Beijing 100094,China

1 引言

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

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

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

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

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

軟件相似性識別采用相似性函數(shù)對程序胎記進(jìn)行計(jì)算，其描述如下：

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

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

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

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

2 相關(guān)工作

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

3 特征字符串動態(tài)引用頻率提取和相似性函數(shù)

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

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

4 算法實(shí)現(xiàn)

4.1 特征字符串提取Cq′

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

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

4.2 生成輸入集合I′

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

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

4.3 構(gòu)建ek和 fk

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

圖1 構(gòu)建ek和 fk

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

4.4 生成和

對于文件ek和 fk，通過函數(shù)GenerateSet生成程序胎記和，GenerateSet由簡單的unix腳本文件實(shí)現(xiàn)，其設(shè)計(jì)如下：

sed'/^$/d'刪除ek和 fk中的空行；sort實(shí)現(xiàn)排序；uniq-c實(shí)現(xiàn)重復(fù)字符串的計(jì)數(shù)統(tǒng)計(jì)；comm-12實(shí)現(xiàn)集合的匹配。

4.5 相似性函數(shù)定義

5 實(shí)例分析

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

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

6 結(jié)論

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

[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.