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

• 学术论文 • 上一篇    下一篇

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

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

  1. 1 中国科学院计算技术研究所,北京 100080
    2 中国科学院研究生院,北京 100039
    3 中国科学院信息工程研究所,北京 100093
  • 出版日期:2016-11-25 发布日期:2016-11-30
  • 基金资助:
    国家自然科学基金资助项目;国家高技术研究发展计划(“863”计划)基金资助项目;国家高技术研究发展计划(“863”计划)基金资助项目;国家242信息安全计划基金资助项目;中国科学院战略性科技先导专项基金资助项目

Fast reused code tracing method based on simhash and inverted index

Yan-chen QIAO1,2,3,Xiao-chun YUN1,2,3,Yu-peng TUO2,3(),Yong-zheng ZHANG2,3   

  1. 1 Institute of Computing Technology, Chinese Academy of Sciences, Beijing 100080, China
    2 Graduate School, Chinese Academy of Sciences, Beijing 100039, China
    3 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

摘要:

提出了一种新颖的复用代码精确快速溯源方法。该方法以函数为单位,基于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