ISSN 1000-1239 CN 11-1777/TP

计算机研究与发展 ›› 2022, Vol. 59 ›› Issue (1): 209-235.doi: 10.7544/issn1000-1239.20200778

• 软件技术 • 上一篇    下一篇

基于社团检测算法的固件二进制比对技术

肖睿卿,费金龙,祝跃飞,蔡瑞杰,刘胜利   

  1. (数学工程与先进计算国家重点实验室 郑州 450001) (xiao_paper@126.com)
  • 出版日期: 2022-01-01
  • 基金资助: 
    国家重点研发计划项目(2019QY1300);科技委基础加强项目(2019-JCJQ-ZD-113) Commission (2019-JCJQ-ZD-113).

Firmware Binary Comparison Technology Based on Community Detection Algorithm

Xiao Ruiqing, Fei Jinlong, Zhu Yuefei, Cai Ruijie, Liu Shengli   

  1. (State Key Laboratory of Mathematical Engineering and Advanced Computing, Zhengzhou 450001)
  • Online: 2022-01-01
  • Supported by: 
    This work was supported by the National Key Research and Development Plan of China (2019QY1300) and the Foundation Enhancement Project of Science and Technology

摘要: 固件比对是二进制比对技术的重要分支.然而,既往研究关注于函数的表示方法的优化却忽略了对过滤器的设计优化,导致固件常因包含同构函数引发误匹配,以致现有二进制比对技术应用于固件比对时效果不够理想.为此,提出基于社团检测算法的固件比对技术,首次将复杂网络相关理论应用于二进制比对领域.通过社团检测算法将固件内的函数划分为若干社团,利用社团匹配实现过滤器的功能,再根据匹配社团寻找匹配函数;此外,优化了函数相似度计算方法,设计了操作数相似性计算方法.在实现原型系统后,使用1382个固件构建2个数据集进行实验,验证了可行性,分析了基于社团检测算法的固件比对方法的性能,确定了各参数的合理取值,设计了评估指标可信匹配率,并比较了该方法与Bindiff的比对效果.实验表明:该方法可以提升Bindiff比对结果5%~11%的正确率.

关键词: 固件比对, 社团检测, 复杂网络, 函数相似性, BGLL算法

Abstract: Firmware comparison is an important branch of binary comparison technology. However, the existing binary comparison technology is not ideal when applied to firmware comparison. Previous studies focused on the optimization of the function representation method, but neglected the design and improvement of filters, which led to mismatches caused by firmware containing isomorphic functions. For this reason, this paper proposes a firmware comparison technology based on community detection algorithms, and applies complex network related theories to the field of binary comparison for the first time. Divide the function in the firmware into several communities through the community detection algorithm, use community matching to realize the filter function, and then find the matching function according to the matching community; In addition, this paper optimizes the function similarity calculation method, and designs the operand similarity calculation method. After the prototype system is implemented, this paper uses 1382 firmware to construct two data sets for experiments to verify the feasibility, analyze the performance of the method in this paper, and determine the reasonable value of each parameter, design the credible matching rate as the evaluation index, and compare the method in this paper and Bindiff. Experiments show that this method can improve the accuracy of Bindiff comparison results by 5% to 11%.

Key words: firmware comparison, community detection, complex network, function similarity, BGLL algorithm

中图分类号: