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

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

Abstract

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

CLC Number:

TP393

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.

Figures/Tables 14

References 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.

Metrics

Recommended 0

No Suggested Reading articles found!

文件标号	文件原名	函数数量
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不同的函数数量。

Method for constructing function correspondence between firmware based on candidate function group

RichHTML

PDF下载

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 14

References 25

Related Articles 2

Metrics

Recommended 0

策略	差异匹配数量/个	本文方法正确数量/个	Bindiff正确数量/个	两种方法都判别错误数量/个	人工无法鉴定两种方法哪种正确
父节点已匹配	500	433	5	40	22
子节点已匹配	500	402	13	60	24
连续地址	500	435	2	27	36
未匹配区间	500	351	2	64	82
统计特征	215	210	0	4	1

策略	差异匹配数量	本文方法正确数量	Bindiff正确数量	两种方法都判别错误数量	人工无法鉴定两种方法哪种正确
父节点已匹配	100	66	3	16	15
子节点已匹配	100	71	4	16	9
连续地址	100	77	0	10	13
未匹配区间	89	73	0	16	0
统计特征	77	68	0	8	1

[1]	Anxiang HU, Da XIAO, Shichen GUO, Shengli LIU. Hard-coded backdoor detection method based on semantic conflict [J]. Chinese Journal of Network and Information Security, 2023, 9(1): 150-157.
[2]	Peng-hui ZHANG,Xi TIAN,Kang-wei LOU. Firmware vulnerability analysis based on formal verification of software and hardware [J]. Chinese Journal of Network and Information Security, 2016, 2(7): 59-68.