Partition-based binary file similarity comparison method

doi:10.11772/j.issn.1001-9081.2015.10.2896

Abstract

Abstract: Focusing on the huge consumption of time and space and the absolute comparison result of Basic Block (BB) resulted from one-to-one mapping of basic block in traditional file structural similarity detection technique, a method based on dividing thought was proposed to accomplish structural comparison of binary file. Firstly, the small primes algorithm which is used to compare the basic block was improved to classify the basic blocks in a function, then the similar rates of basic blocks were obtained by combining with the weights of basic block signature and attribute, so as to get the final function similar rate and final file similar rate. In the comparison with the absolute comparison method which does not consider the partition at the similar rates of function, this proposed method has certain advantages in efficiency and accuracy. The experimental show that the proposed method improves the accuracy of comparison, and reduces the comparison time, it is more feasible in similarity comparison of binary files.

Key words: partition, Basic Block (BB), small primes algorithm, signature, binary file

摘要： 针对传统文件结构化相似性比较法中采用基本块(BB)一对一映射而造成的巨大时空消耗及基本块比较结果的绝对化问题,提出一种基于划分思想的文件结构化相似性比较方法。该方法首先对用于基本块比较的小素数积法进行改进,通过改进方法将函数内的基本块进行分类,再结合基本块签名与属性的权重求得基本块间的相似率,从而计算出最终的函数相似率及文件相似率。通过函数相似率比较实验分析,与未考虑划分思想的绝对化基本块比较算法相比,该方法在比较效率及准确率上均有所提升。实验结果表明,该方法在减少比较时间的同时提高了比较准确率,在实际二进制文件相似性比较的应用中更可行。

关键词: 划分, 基本块, 小素数积法, 签名, 二进制文件

CLC Number:

TP301.6

DONG Qihai, WANG Yagang. Partition-based binary file similarity comparison method[J]. Journal of Computer Applications, 2015, 35(10): 2896-2900.

董启海, 王亚刚. 基于划分的二进制文件相似性比较方法[J]. 计算机应用, 2015, 35(10): 2896-2900.

References

[1] XIONG H, YAN H, GUO T, et al. Code similarity detection: a survey [J]. Computer Science, 2010,37(8):9-14,76.(熊浩,晏海华,郭涛,等.代码相似性检测技术:研究综述[J].计算机科学, 2010,37(8):9-14,76.)
[2] CUI B, LI J, GUO T, et al. Code comparison system based on abstract syntax tree[C]//Proceedings of the 2010 3rd IEEE International Conference on Broadband Network and Multimedia Technology. Piscataway: IEEE Press, 2010:668-673.
[3] YU Y, LI J, WU W, et al. On the security of an identity-based signature scheme[J]. Chinese Journal of Computers,2014,37(5):1025-1029.(禹勇,李继国,伍玮,等. 基于身份签名方案的安全性分析[J].计算机学报,2014, 37(5):1025-1029.)
[4] SHI Q, MENG F, ZHANG L, et al. Survey of research on code clone technique[J]. Application Research of Computers,2013,30(6):1617-1623. (史庆庆,孟繁军,张丽萍,等.克隆代码技术研究综述[J].计算机应用研究,2013,30(6):1617-1623.)
[5] WANG J, YANG F, HAN F. Instruction merging optimization algorithm in binary files comparison[J]. Computer Applications and Software, 2013, 30(12):40-42,126.(王建新,杨凡,韩锋.二进制文件比对中的指令归并优化算法[J].计算机应用与软件, 2013, 30(12):40-42,126.)
[6] CHE H, GUO T, CUI B, et al. Comparison and analysis on binary file similarity detection technique[J]. Computer Engineering and Applications, 2012,48(33):79-84.(陈慧,郭涛,崔宝江,等.二进制文件相似性检测技术对比分析[J].计算机工程与应用, 2012,48(33):79-84.)
[7] FLAKE H. Structural comparison of executable objects [EB/OL]. [2015-03-15]. http://citeseerx.ist.psu.Edu/viewdoc/download?doi=10.1.1.83.6632&rep=rep1&type=pdf.
[8] FU J, QIAO W, GAO D. Comparison of executable objects based on singatures and properties [J]. Journal of Computer Research and Development, 2009,46(11):1868-1876.(傅建明,乔伟,高德斌.一种基于签名和属性的可执行文件比较[J].计算机研究与发展, 2009,46(11):1868-1876.)
[9] DOU Z, WANG Z, CHEN N, et al. Control flow analysis based on intermediate representation of executable code [J]. Computer Engineering, 2010,36(21):31-36.(窦增杰,王震宇,陈楠,等.基于可执行代码中间表示的控制流分析[J].计算机工程,2010,36(21):31-36.)
[10] WANG M, WEI Q, WU H. Research on structural comparing of binary files based on directed graph[J]. Computer Engineering and Design, 2006,27(9):1640-1641. (王猛,魏强,吴灏.基于有向图的二进制文件结构化比较机制研究[J].计算机工程与设计,2006,27(9):1640-1641.)
[11] GUO X, WANG P. Technique of cooperative reverse reasoning in related path static analysis[J]. Journal of Software,2014,26(1):1-13.(郭曦,王盼.相关路径静态分析中协同式逆向推理方法[J].软件学报,2014,26(1):1-13.)
[12] LIU C, GUO T, CHI B, et al. Similarity computation for executable objects homology detection based on structural signature[J]. Journal of Beijing University of Posts and Telecommunications, 2012, 35(3):56-60.(刘春红,郭涛,崔宝江,等.二进制文件同源性检测的结构化相似度计算[J].北京邮电大学学报,2012,35(3):56-60.)
[13] LUO Q, SHU H, ZENG Y. A parallel algorithm for structural comparison of executable objects[J]. Journal of Computer Applications, 2007, 27(5):1260-1263.(罗谦,舒辉,曾颖.二进制文件结构化比较的并行算法实现[J].计算机应用, 2007, 27(5):1260-1263.)
[14] SHE Y, ZHAO R, WANG X, et al. Instruction normalization algorithm in binary patch comparison[J].Computer Engineering, 2010,36(15):46-48.(沈亚楠,赵荣彩,王小芹,等.二进制补丁比对中的指令归一化算法[J].计算机工程, 2010,36(15):46-48.)
[15] XIE Y, ZENG Y, SHU H. Improved graph-based comparison algorithm of executable objects[J]. Computer Engineering and Design, 2007, 28(2):257-260.(谢余强,曾颖,舒辉.改进的基于图的可执行文件比较算法[J].计算机工程与设计, 2007, 28(2):257-260.)
[16] CUI B, MA D, HAO Y, et al. Comparison of executable objects based on block signatures and jump relations [J]. Journal of Tsinghua University: Science and Technology, 2011, 51(10):1351-1356.(崔宝江,马丁,郝永乐,等.基于基本块签名和跳转关系的二进制文件比对技术[J].清华大学学报:自然科学版, 2011,51(10):1351-1356.)