基于划分的二进制文件相似性比较方法

doi:10.11772/j.issn.1001-9081.2015.10.2896

计算机应用 ›› 2015, Vol. 35 ›› Issue (10): 2896-2900.DOI: 10.11772/j.issn.1001-9081.2015.10.2896

基于划分的二进制文件相似性比较方法

董启海, 王亚刚

西安邮电大学计算机学院, 西安 710121

收稿日期:2015-05-22 修回日期:2015-08-18 出版日期:2015-10-10 发布日期:2015-10-14
通讯作者: 董启海(1988-),男,山东高唐人,硕士研究生,主要研究方向:信息安全、嵌入式系统,dongqihaia@126.com
作者简介:王亚刚(1972-),男,陕西乾县人,副教授,博士,CCF会员,主要研究方向:信息安全、嵌入式系统、编译器与并行计算。
基金资助:
国家自然科学基金资助项目(61136002);陕西省教育厅科研计划项目(14JK1674)。

Partition-based binary file similarity comparison method

DONG Qihai, WANG Yagang

School of Computer Science and Technology, Xi'an University of Posts and Telecommunications, Xi'an Shaanxi 710121, China

Received:2015-05-22 Revised:2015-08-18 Online:2015-10-10 Published:2015-10-14

摘要/Abstract

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

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

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

中图分类号:

TP301.6

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

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

参考文献

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

基于划分的二进制文件相似性比较方法

Partition-based binary file similarity comparison method

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

[1]	杨龙海, 王学渊, 蒋和松. 改进SM2签名方法的区块链数字签名方案[J]. 计算机应用, 2021, 41(7): 1983-1988.
[2]	谷正川, 郭渊博, 方晨. 基于代理重加密的消息队列遥测传输协议端到端安全解决方案[J]. 计算机应用, 2021, 41(5): 1378-1385.
[3]	姜琨, 刘征, 朱磊, 李晓星. 基于有向无环图的倒排链等字长划分压缩算法[J]. 计算机应用, 2021, 41(3): 727-732.
[4]	王家亮, 李树华, 张海涛. 基于贝叶斯估计与区域划分遍历的四轴飞行器避障路径规划算法[J]. 计算机应用, 2021, 41(2): 384-389.
[5]	李文霞, 刘林忠, 代存杰, 李玉. 基于多种群组合策略的人工蜂群算法[J]. 《计算机应用》唯一官方网站, 2021, 41(11): 3113-3119.
[6]	张驰, 李铸洪, 刘舟, 沈未名. 基于场景图划分的无人机影像定位算法[J]. 计算机应用, 2021, 41(10): 3004-3009.
[7]	王韫烨, 程亚歌, 贾志娟, 付俊俊, 杨艳艳, 何宇矗, 马威. 基于安全多方的区块链可审计签名方案[J]. 计算机应用, 2020, 40(9): 2639-2645.
[8]	李靖, 景旭, 杨会君. 基于实用拜占庭容错算法的区块链电子计票方案[J]. 计算机应用, 2020, 40(4): 954-960.
[9]	王松伟, 赵秋阳, 王宇航, 饶小平. 基于深度学习的脑片图像区域划分方法[J]. 计算机应用, 2020, 40(4): 1202-1208.
[10]	刘惠剑, 刘峻松, 王佳伟, 薛岗. 基于过程划分技术的服务组合拆分方法[J]. 计算机应用, 2020, 40(3): 799-805.
[11]	吕一可, 徐凯, 黄振强. 基于面积划分的轨迹相似性度量方法[J]. 计算机应用, 2020, 40(2): 578-583.
[12]	杨程, 陆佳民, 冯钧. 分布式环境下大规模资源描述框架数据划分方法综述[J]. 计算机应用, 2020, 40(11): 3184-3191.
[13]	余林芳, 邓伏虎, 秦少威, 秦志光. 基于眼底图像层次特征的分类方法[J]. 计算机应用, 2019, 39(9): 2575-2579.
[14]	程亚歌, 贾志娟, 胡明生, 公备, 王利朋. 适用于区块链电子投票场景的门限签名方案[J]. 计算机应用, 2019, 39(9): 2629-2635.
[15]	高建, 毛莺池, 李志涛. 基于高斯混合时间序列模型的轨迹预测[J]. 计算机应用, 2019, 39(8): 2261-2270.