基于simhash与倒排索引的复用代码快速溯源方法

doi:10.11959/j.issn.1000-436x.2016225

通信学报 ›› 2016, Vol. 37 ›› Issue (11): 104-113.doi: 10.11959/j.issn.1000-436x.2016225

基于simhash与倒排索引的复用代码快速溯源方法

乔延臣^1,^2,³,云晓春^1,^2,³,庹宇鹏^2,³(),张永铮^2,³

¹ 中国科学院计算技术研究所，北京 100080
² 中国科学院研究生院，北京 100039
³ 中国科学院信息工程研究所，北京 100093

出版日期:2016-11-25 发布日期:2016-11-30
基金资助:
国家自然科学基金资助项目;国家高技术研究发展计划（“863”计划）基金资助项目;国家高技术研究发展计划（“863”计划）基金资助项目;国家242信息安全计划基金资助项目;中国科学院战略性科技先导专项基金资助项目

Fast reused code tracing method based on simhash and inverted index

Yan-chen QIAO^1,^2,³,Xiao-chun YUN^1,^2,³,Yu-peng TUO^2,³(),Yong-zheng ZHANG^2,³

¹ Institute of Computing Technology, Chinese Academy of Sciences, Beijing 100080, China
² Graduate School, Chinese Academy of Sciences, Beijing 100039, China
³ Institute of Information Engineering, Chinese Academy of Sciences, Beijing 100093, China

Online:2016-11-25 Published:2016-11-30
Supported by:
The National Natural Science Foundation of China;The National High Technology Research and Development Program of China (863 Program);The National High Technology Research and Development Program of China (863 Program);The National 242 Information Secu-rity Research Program of China;The Strategic Priority Research Program of the Chinese Academy of Sciences

摘要/Abstract

摘要：

提出了一种新颖的复用代码精确快速溯源方法。该方法以函数为单位，基于simhash与倒排索引技术，能在海量代码中快速溯源相似函数。首先基于simhash利用海量样本构建具有三级倒排索引结构的代码库。对于待溯源函数，依据函数中代码块的simhash值快速发现相似代码块，继而倒排索引潜在相似函数，依据代码块跳转关系精确判定是否相似，并溯源至所在样本。实验结果表明，该方法在保证高准确率与召回率的前提下，基于代码库能快速识别样本中的编译器插入函数与复用函数。

关键词: 网络安全, 复用代码, 快速溯源, 同源判定, 恶意代码

Abstract:

A novel method for fast and accurately tracing reused code was proposed. Based on simhash and inverted in-dex, the method can fast trace similar functions in massive code. First of all, a code database with three-level inverted in-dex structures was constructed. For the function to be traced, similar code blocks could be found quickly according to simhash value of the code block in the function code. Then the potential similar functions could be fast traced using in-verted index. Finally, really similar functions could be identified by comparing jump relationships of similar code blocks. Further, malware samples containing similar functions could be traced. The experimental results show that the method can quickly identify the functions inserted by compilers and the reused functions based on the code database under the premise of high accuracy and recall rate.

Key words: network security, reused code, retrieval method, homology identification, malware

乔延臣,云晓春,庹宇鹏,张永铮. 基于simhash与倒排索引的复用代码快速溯源方法[J]. 通信学报, 2016, 37(11): 104-113.

Yan-chen QIAO,Xiao-chun YUN,Yu-peng TUO,Yong-zheng ZHANG. Fast reused code tracing method based on simhash and inverted index[J]. Journal on Communications, 2016, 37(11): 104-113.

图/表 12

图1

图2

表1

表2

图3

图4

图5

图6

表3

表4

表5

表6

参考文献 24

[1]	董志强，肖新光，张栗伟 . 编码心理学分析病毒同源性[J]. 信息安全与通信保密, 2005(8):55-59. DONG Z Q , XIAO X G , ZHANG S W . Malware homology identifica-tion based on programming psychology[J]. China Information Security, 2005(8):55-59.
[2]	GReAT . Gauss: abnormal distribution 2012[R/OL].
[3]	YURY Y , NAMESTNIKOV V K , OLEG K . Chthonic: a new modification of ZeuS 2014[R/OL]. .
[4]	SKELORU V . Visgean/Zeus[EB/OL]. .
[5]	GREAT . A fanny equation: “i am your father, stuxnet”2015[EB/OL]. .
[6]	QIAO Y C , YUN X , ZHANG Y . Fast reused function retrieval method based on simhash and inverted index[C]// 2016 15th IEEE Interna-tional Conference on Trust, Security and Privacy in Computing and Communications. 2016.
[7]	BENCSATH B , PEK G , BUTTYAN L , et al Duqu: a stuxnet-like malware found in the wild[R]. CrySyS Lab Technical Report. 2011.
[8]	GREAT . Cloud Atlas: RedOctober APT is back in style 2014[R/OL]. .
[9]	LABS F S . PITOU: The “silent” resurrection of the notorious Srizbi kernel spambot[R]. . 2014.
[10]	MYLES G , COLLBERG C , K-gram based software birthmarks[C]// Proceedings of the 2005 ACM Symposium on Applied Computing. 2005:314-318.
[11]	S?BJ?RNSEN A , WILLCOCK J , PANAS T , et al. Detecting code clones in binary executables[C]// 18th International Symposium on Software Testing and Analysis. 2009:117-128.
[12]	LAKHOTIA A , PREDA M D , GIACOBAZZI R . Fast location of similar code fragments using semantic'juice'[C]// 2nd ACM SIGPLAN Program Protection and Reverse Engineering Workshop. 2013:1-6.
[13]	RUTTENBERG B , MILES C , KELLOGG L , et al. Identifying shared software components to support malware forensics[J]. Detection of In-trusions and Malware, and Vulnerability Assessment: Springer, 2014,21-40.
[14]	OUELLETTE J , PFEFFER A , LAKHOTIA A , et al. Countering malware evolution using cloud-based learning[C]// 2013 8th International Con-ference on Malicious and Unwanted Software, 2013.
[15]	DAVID Y , YAHAV E , Tracelet-based code search in executables[C]// ACM SIGPLAN Notices. 2014.
[16]	ALRABAEE S , SHIRANI P , WANG L , et al. SIGMA: a semantic inte-grated graph matching approach for identifying reused functions in binary code[J]. Digital Investigation, 2015,12:S61-S71.
[17]	CHARIKAR M S . Similarity estimation techniques from rounding algorithms[C]// 34th Annual ACM Symposium on Theory of Comput-ing. 2002.
[18]	MANKU G S , JAIN A , SARMA A D . Detecting near-duplicates for web crawling[C]// 16th International Conference on World Wide Web. Banff, Alberta, Canada, 2007:141-50.
[19]	UDDIN M S , ROY C K , SCHNEIDER K A , et al. On the effectiveness of simhash for detecting near-miss clones in large scale software sys-tems[C]// 2011 18th Working Conference on Reverse Engineering(WCRE), 2011.
[20]	郭颖，陈峰宏，周明辉 . 大规模代码克隆的检测方法[J]. 计算机科学与探索, 2014(4):417-426. GUO Y , CHEN F H , ZHOU M H . Code clone detection method for large scale source code[J]. Journal of Frontiers of Computer Science ＆Technology, 2014(4):417-426.
[21]	TIMO J , RINNE S L . ssh-3.2.9.1 2003[EB/OL]. .
[22]	VX Heaven[EB/OL]. .
[23]	Wikipedia . Agobot 2016[EB/OL]. .
[24]	KHOO W M , MYCROFT A , ANDERSON R , et al. Rendezvous: a search engine for binary code[C]// Proceedings of the 10th Working Confer-ence on Mining Software Repositories. 2013.

代码块名称	内容
	push esi
	mov esi, [esp+4+arg_0]
	push 0
loc_4023BC	and dword ptr [esi], 0
	call ds:GetModuleHandleA
	cmp word ptr [eax], 5A4Dh
	jnz short loc_4023E7
	pop esi
loc_4023E7
	retn

原代码块	标准化处理代码块
push esi	push REG32
mov esi, [esp+4+arg_0]	mov REG32, MEM
push 0	push VAL
and dword ptr [esi], 0	and MEM, VAL
call ds:GetModuleHandleA	call GetModuleHandleA
cmp word ptr [eax], 5A4Dh	cmp MEM, VAL
jnz short loc_4023E7	jnz loc_xxx

已知	溯源	未溯源
相似	1 486	62
不相似	131	—

编译器函数	WinXP系统文件中的相似函数
sub_40451A	imjputyc.dll中的___old_sbh_decommit_pages等
sub_402A5B	TPPS.DLL中的sub_10005660等
sub_4023E9	TPVMW32.dll中的sub_10006046等
sub_4044C4	MSCOMCTL.OCX中的sub_27608F15等
sub_4023BC	tprdpw32.dll中的sub_10009720等
sub_404380	imjpuex.exe中的___old_sbh_new_region等
sub_4045DC	tprdpw32.dll中的sub_1000A73D等
sub_404880	msvcr70.dll中的___old_sbh_alloc_block_from_page等
sub_402531	tprdpw32.dll中的sub_10009895等
sub_404678	imjpdct.dll中的___old_sbh_alloc_block等
sub_402E2A	imjprw.exe中的_calloc等
sub_403BA2	imjpmig.exe中的___sbh_free_block等
sub_40292A	imjpcus.dll中的__heap_alloc等
sub_402799	imskdic.dll中的__NMSG_WRITE等
sub_404633	TPVMW32.dll中的sub_1000708D等
sub_401233	tprdpw32.dll中的sub_1000F109等

非Agobot家族样本	相似函数数量	总指令数
Net-Worm.Win32.Kolabc.eph	44	2 411
Trojan-Spy.Win32.SCKeyLog.fp	44	1 048
Trojan-Spy.Win32.SCKeyLog.ij	43	1 141
Backdoor.Win32.IRCBot.ol	40	4 036
Trojan-Dropper.Win32.Agent.tif	31	712
Trojan-Spy.Win32.SCKeyLog.fb	29	669
Trojan-Downloader.Win32.Delf.gij	28	711
Backdoor.Win32.SuperSpy.b	28	665
Trojan-Downloader.Win32.Realtens.h	28	619
Trojan-PSW.Win32.Zombie.10	26	646

基于simhash与倒排索引的复用代码快速溯源方法

Fast reused code tracing method based on simhash and inverted index

在线阅读

PDF下载

可视化

摘要/Abstract

引用本文

使用本文

图/表 12

参考文献 24

相关文章 15

Metrics

推荐阅读 0

恶意代码家族	关联样本数量
Trojan.Win32.Vapsup	2 566
Trojan.Win32.Agent	124
Trojan-Downloader.Win32.Agent	114
Trojan-Clicker.Win32.Agent	69
Trojan-Ransom.Win32.Hexzone	58
Trojan-GameThief.Win32.OnLineGames	47
Backdoor.Win32.Rbot	45
Backdoor.Win32.Agent	43
Trojan.Win32.BHO	40
Backdoor.Win32.SdBot	25

[1]	黄韬, 刘江, 汪硕, 张晨, 刘韵洁. 未来网络技术与发展趋势综述[J]. 通信学报, 2021, 42(1): 130-150.
[2]	罗智勇,杨旭,刘嘉辉,许瑞. 基于贝叶斯攻击图的网络入侵意图分析模型[J]. 通信学报, 2020, 41(9): 160-169.
[3]	吴武飞,李仁发,曾刚,谢勇,谢国琪. 智能网联车网络安全研究综述[J]. 通信学报, 2020, 41(6): 161-174.
[4]	李涛,郭渊博,琚安康. 融合对抗主动学习的网络安全知识三元组抽取[J]. 通信学报, 2020, 41(10): 80-91.
[5]	周翰逊,陈晨,冯润泽,熊俊坤,潘宏,郭薇. 基于值导数GRU的移动恶意软件流量检测方法[J]. 通信学报, 2020, 41(1): 102-113.
[6]	蒋侣,张恒巍,王晋东. 基于信号博弈的移动目标防御最优策略选取方法[J]. 通信学报, 2019, 40(6): 128-137.
[7]	罗智勇, 杨旭, 孙广路, 谢志强, 刘嘉辉. 基于马尔可夫的有限自动机入侵容忍系统模型[J]. 通信学报, 2019, 40(10): 79-89.
[8]	黄世锐,张恒巍,王晋东,窦睿彧. 基于定性微分博弈的网络安全威胁预警方法[J]. 通信学报, 2018, 39(8): 29-36.
[9]	臧小东,龚俭,胡晓艳. 基于AGD的恶意域名检测[J]. 通信学报, 2018, 39(7): 15-25.
[10]	刘亚姝,王志海,严寒冰,侯跃然,来煜坤. 抗混淆的恶意代码图像纹理特征描述方法[J]. 通信学报, 2018, 39(11): 44-53.
[11]	赵炳麟,孟曦,韩金,王婧,刘福东. 基于图结构的恶意代码同源性分析[J]. 通信学报, 2017, 38(Z2): 86-93.
[12]	石乐义,孙慧,崔玉文,郭宏彬,李剑蓝. 抵御DoS攻击的端信息跳变Web插件机制[J]. 通信学报, 2017, 38(Z1): 19-24.
[13]	王涛,陈鸿昶,程国振. 软件定义网络及安全防御技术研究[J]. 通信学报, 2017, 38(11): 133-160.
[14]	尹涛,李世淙,庹宇鹏,张永铮. 强抗毁性社交僵尸网络的构建及其防御[J]. 通信学报, 2017, 38(1): 97-105.
[15]	吕少卿,张玉清,刘东航,张光华. 在线社交网络中Spam相册检测方案[J]. 通信学报, 2016, 37(9): 75-91.