基于候选函数组的固件间函数对应关系构建方法

doi:10.11959/j.issn.2096-109x.2021018

摘要/Abstract

摘要：

由于固件的特点，传统二进制比对方法在匹配函数节点传播匹配的过程中易产生误匹配。针对匹配函数传播效果不理想的问题，设计了基于候选函数组的函数对应关系构建方法，并引入了函数n层局部网络匹配的概念。然后，结合3种候选函数组构造策略形成候选函数组构造方法及候选函数组匹配方法，并分析了时间开销。最后，基于所提方法实现了原型系统，并与 Bindiff 进行比较。通过随机抽样和人工核对，所提方法匹配结果的86.04%与Bindiff匹配结果一致，所提方法匹配结果的11.3%可以修正Bindiff的匹配错误，缓解了传播带来的误匹配问题。

关键词: 固件, 二进制比对, 函数匹配, 候选函数组

Abstract:

Due to the characteristics of firmware, traditional binary comparison methods are prone to mismatches during the propagation of the matching function.Aiming at the problem that the matching function propagation algorithm is not ideal, a method for constructing function correspondence based on candidate function groups was designed, and the concept of function matching in n layer local network is supplemented.Then, three candidate function group construction strategies and candidate function group matching methods are proposed, and the time overhead were analyzed.Finally, a prototype system was implemented based on the method and compared with Bindiff.Through random sampling and manual check, 86.04% of the matching results of the proposed method are consistent with Bindiff matching results, while 11.3% can correct Bindiff matching errors.

Key words: firmware, binary comparison, function matching, candidate function group

中图分类号:

TP393

肖睿卿, 祝跃飞, 刘胜利, 芦斌. 基于候选函数组的固件间函数对应关系构建方法[J]. 网络与信息安全学报, 2021, 7(2): 110-125.

Ruiqing XIAO, Yuefei ZHU, Shengli LIU, Bin LU. Method for constructing function correspondence between firmware based on candidate function group[J]. Chinese Journal of Network and Information Security, 2021, 7(2): 110-125.

图/表 14

图1

图2

图3

图4

图5

图6

图7

表1

表2

表3

表4

表5

表6

表7

参考文献 25

[1]	A survey of binary code similarity[R]. 2019.
[2]	GAO J , YANG X , FU Y ,et al. VulSeeker:a semantic learning based vulnerability seeker for cross-platform binary[C]// Conference on Automated Software Engineering(ASE 2018). 2018.
[3]	FENG Q , ZHOU R , XU C ,et al. Scalable graph-based bug search for firmware images[C]// Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security. 2016: 480-491.
[4]	XU X , LIU C , FENG Q ,et al. Neural network-based graph embedding for cross-platform binary code similarity detection[C]// Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security. 2017: 363-376.
[5]	HU Y , ZHANG Y , LI J ,et al. Cross-architecture binary semantics understanding via similar code comparison[C]// 2016 IEEE 23rd International Conference on Software Analysis,Evolution,and Reengineering (SANER). 2016: 57-67.
[6]	刘春红, 郭涛, 崔宝江 ,等. 二进制文件同源性检测的结构化相似度计算[J]. 北京邮电大学学报, 2012,35(3): 56-60.
	LIU C H , GUO T , CUI B J ,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.
[7]	CESARE S , XIANG Y . Classification of malware using structured control flow[C]// Proceedings of the Eighth Australasian Symposium on Parallel and Distributed Computing-Volume 107. 2010: 61-70.
[8]	PEWNY J , GARMANY B , GAWLIK R ,et al. Cross-architecture bug search in binary executables[C]// 2015 IEEE Symposium on Security and Privacy. 2015: 709-724.
[9]	ESCHWEILER S , YAKDAN K GERHARDS-PADILLA E . DiscovRE:efficient cross-architecture identification of bugs in binary code[C]// NDSS. 2016.
[10]	Flake H , . Structural comparison of executable objects[C]// Proc of the International GI Workshop on Detection of Intrusions and Malware ＆ Vulnerability Assessment. 2004: 161-174.
[11]	DULLIEN T , ROLLES R . Graph-based comparison of executable objects[J]. SSTIC, 2005,5(1): 3.
[12]	王建新, 杨凡, 韩锋 . 二进制文件比对中的指令归并优化算法[J]. 计算机应用与软件, 2013,30(12): 40-42+126.
	WANG J X , YANG F , HAN F . Instruction merging optimization algorithm in binary files comparison[J]. Computer Applications and Software, 2013,30(12): 40-42+126.
[13]	KHOO W M , MYCROFT A , ANDERSON R . Rendezvous:a search engine for binary code[C]// Proceedings of the 10th Working Conference on Mining Software Repositories. 2013: 329-338.
[14]	BOURQUIN M , KING A , ROBBINS E . Binslayer:accurate comparison of binary executables[C]// Proceedings of the 2nd ACM SIGPLAN Program Protection and Reverse Engineering Workshop. 2013:4.
[15]	HU X , CHIUEH T , SHIN K G . Large-scale malware indexing using function-call graphs[C]// Proceedings of the 16th ACM Conference on Computer and Communications Security. 2009: 611-620.
[16]	刘星, 唐勇 . 恶意代码的函数调用图相似性分析[J]. 计算机工程与科学, 2014,36(3): 481-486.
	LIU X , TANG Y . Similarity analysis of malware's function-call graphs[J]. Computer Engineering ＆ Science, 2014,36(3): 481-486.
[17]	KOSTAKIS O , KINABLE J , MAHMOUDI H ,et al. Improved call graph comparison using simulated annealing[C]// Proceedings of the 2011 ACM Symposium on Applied Computing. 2011: 1516-1523.
[18]	孙贺, 吴礼发, 洪征 ,等. 基于函数调用图的二进制程序相似性分析[J]. 计算机工程与应用, 2016,52(21): 126-133.
	SUN H , WU L F , HONG Z ,et al. Research on function call graph based method for similarity analysis of binary files[J]. Computer Engineering and Applications, 2016,52(21): 126-133.
[19]	JANG J , AGRAWAL A , BRUMLEY D . ReDeBug:finding unpatched code clones in entire OS distributions[C]// 2012 IEEE Symposium on Security and Privacy. 2012: 48-62.
[20]	DAVID Y , YAHAV E . Tracelet-based code search in executables[J]. ACM Sigplan Notices, 2014,49(6): 349-360.
[21]	PEWNY J , SCHUSTER F , BERNHARD L ,et al. Leveraging semantic signatures for bug search in binary programs[C]// Proceedings of the 30th Annual Computer Security Applications Conference. 2014: 406-415.
[22]	Cisco 2600 Series Multiservice Platforms - Retirement Notification[EB].
[23]	Bindiff5[EB]. 2019.
[24]	COSTIN A , ZADDACH J , FRANCILLON A ,et al. A large-scale analysis of the security of embedded firmwares[C]// 23rd {USENIX}Security Symposium ({USENIX} Security 14). 2014: 95-110.
[25]	肖睿卿, 刘胜利, 颜猛 ,等. 节点层次化的二进制文件比对技术[J]. 计算机工程与应用, 2017,53(21): 144-150.
	XIAO R Q , LIU S L , YAN M ,et al. Comparison technology of binary files based on hierarchical nodes[J]. Computer Engineering and Applications, 2017,53(21): 144-150.

文件标号	文件原名	函数数量
A1	c2600-advipservicesk9-mz.124-15.t4	187 365
A2	c2600-advsecurityk9-mz.123-14.t7	85 864
A3	c2600-ds-mz.121-5.t7	57 947
A4	c2600-entbase-mz.123-11.t	79 355
A5	c2600-ik9s-mz.122-26	61 916
A6	c2600-io3-mz.121-7	26 619
A7	c2600-ipbase-mz.123-6f	53 877
A8	c2600-is-mz.122-2.xt	68 918
A9	c2600-ix-mz.122-11.t11	41 452
A10	c2600-jk9o3s-mz.122-28	73 856
B1	c2600-advipservicesk9-mz.123-11.t8	125 416
B2	c2600-advipservicesk9-mz.123-8.t	125 781
B3	c2600-advipservicesk9-mz.124-8	140 723
B4	c2600-advsecurityk9-mz.124-23	873 57
B5	c2600-i-mz.123-18	46 303
B6	c2600-ipbase-mz.124-5	66 091
B7	c2600-is56i-mz.121-14	46 830
B8	c2600-ix-mz.123-11.t	59 583
B9	c2600-j1s3-mz.123-24	91 589
B10	c2600-jsx-mz.123-11.t	120 031
C1	c800-universalk9-mz.SPA.154-3.M10	388 468
C2	c800-universalk9-mz.SPA.155-3.M5	420 071
C3	c800-universalk9-mz.SPA.156-3.M4	435 324
C4	c800-universalk9-mz.SPA.157-3.M	434 759

K			δ
K	70%	80%		90%	100%
1	2.2（2249727/1022386）	2.05（2142435/1046574）		2.24（1869028/835100）	2.57（1572394/610913）
10	2.25（2268523/1006288）	2.28（2159454/945639）		2.24（1886530/841410）	2.58（1578812/611188）
50	2.44（2273280/932350）	2.23（2162729/967990）		2.27（1904032/840368）	1.88（1584180/841044）
100	2.19（2279676/1042411）	2.65（2104008/794232）		2.28（1909337/836784）	2.3（1589379/691464）
500	2.56（2299658/899247）	2.3（2193307/954281）		2.09（1930581/922702）	2.1（1609010/765023）
注：每一单元格表示，在相应参数下，比对100对样例后，匹配量、时间开销的总和，单位是个数和秒。

策略	时耗/s	匹配数量	匹配轮次	失败时耗/s	失败轮次
调用关系	759 176	1 325 891	1 651	4 438	525
连续地址	215 337	816 915	392	2	31
未匹配区间	25 920	52 016	564	12 123	271
统计特征	3 015	9 511	99	0	0
注：轮次表示候选函数组匹配的次数，失败表示一轮匹配未产生新的匹配节点。

策略	时耗/s	匹配数量	匹配轮次	失败时耗	失败轮次
调用关系	759 176	1 325 891	1 651	4 438	525
兄弟节点	565 724	950 268	14 372	96 458	5 220
父节点已匹配	129 327	537 577	28 744	8 308	9 942
子节点已匹配	508 578	788 314	28 744	168 168	13 064

策略	差异匹配数量	占该法匹配总量百分比	函数平均指令数
父节点已匹配	10 094	1.87%	21
子节点已匹配	20 094	2.55%	26
连续地址	244 166	31.19%	14
未匹配区间	33 133	64.70%	10
统计特征	215	2.26%	121
注：差异匹配数量，本文匹配结果与Bindiff5不同的函数数量。