基于特征字符串动态引用频率的库引用识别

蔡建章 ，魏 强 ，史建忠

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.