相关路径静态分析中协同式逆向推理方法
作者:
基金项目:

国家自然科学基金(61173138, 61272452, 91118003, 61003268); 湖北省自然科学基金(2014CFB144); 中央高校基本科研业务费专项资金(0900206154); 武汉大学博士研究生短期出国(境)研修专项经费


Technique of Cooperative Reverse Reasoning in Related Path Static Analysis
Author:
  • 摘要
  • | |
  • 访问统计
  • |
  • 参考文献 [18]
  • |
  • 相似文献 [20]
  • |
  • 引证文献
  • | |
  • 文章评论
    摘要:

    相关路径生成,是程序动态分析中的一种重要方法.通过对目标执行路径的获取和分析来生成与其相关的近邻执行路径,在程序行为特征分析、编译优化和调试等研究方向有重要的作用.现有的方法主要通过改变路径节点序列来生成近邻的路径集合,由于缺乏关键节点的路径引导信息,导致生成大量冗余或者无效的路径集合.提出采用协同式逆向分析的近邻路径生成方法,针对目标路径的后置条件,采用逆向符号分析方法产生程序各个基本块的前置条件作为执行路径的引导信息.同时,通过调整距离因子k的取值,可以有针对性地生成与目标路径的编辑距离不超过k的近邻路径集合.实验结果表明:与现有方法相比,该方法在准确性和效率方面有明显的优势.

    Abstract:

    Related execution path generation, which generates the similar execution path according to the acquisition and analysis of the target execution path, is a key technique in the dynamic program analysis, and it is important to the domain of program characteristic analysis, compilation optimization and debugging. Current analysis mainly generates the similar execution path by altering the node list of the path, but lacks the guiding information of the key node, and thus a lot of redundant and infeasible paths are generated. A technique of k similar paths generation based on cooperative reverse analysis is proposed. Aiming at the post-condition of the target paths, the pre-condition of the basic block of the program is calculated by the reverse symbolic analysis, which can be used as the guidance information of the execution paths. Meanwhile, the similar paths that are k distance from the target execution path can be obtained. Experimental results show that the proposed method has an obvious advantage in the aspects of accuracy and efficiency.

    参考文献
    [1] Wang R, Feng DG, Yang Y, Su PR. Semantics-Based malware behavior signature extraction and detection method. Ruan Jian Xue Bao/Journal of Software, 2012,23(2):378-393 (in Chinese with English abstract). http://www.jos.org.cn/1000-9825/3953.htm [doi: 10.3724/SP.J.1001.2012.03953]
    [2] Wang Z, Pierce K, McFarling S. BMAT—A binary matching tool for stale profile propagation. Journal of Instruction-Level Parallelism, 2000,2(1):23-43.
    [3] Bayer U, Comparetti PM, Hlauscheck C, Kruegel C, Kirda E. Scalable, behavior-based malware clustering. In: Proc. of the Network and Distributed System Security Symp. (NDSS 2009). San Diego: NDSS Association, 2009. 8-11. http://www.isoc.org/ isoc/conferences/ndss/09/slides/11.pdf
    [4] King J. Symbolic execution and program testing. Communications of the ACM, 1976,19(7):385-394. [doi: 10.1145/360248. 360252]
    [5] Dijstra E. A Discipline of Programming, Vol.1. Englewood Cliffs: Prentice Hall, 1976. 12-25.
    [6] Nipkow T, Paulson L. Isabelle/HOL: A proof assistant for higher-order logic. LNCS, 2002,2283:120-131. http://www21.in.tum.de/ ~nipkow/LNCS2283/
    [7] Clarke M, Grumberg O, Peled D. Model Checking. 3rd ed., Cambridge: The MIT Press, 1999. 9-15.
    [8] Cruz J. Constraint Reasoning for Differential Models. 5th ed., Amsterdam: The IOS Press, 2005. 63-77.
    [9] Rabek JC, Khazan RI, Lewandowski SM, Cunningham RK. Detection of injected, dynamically generated, and obfuscated malicious code. In: Proc. of the 2003 ACM Workshop on Rapid Malcode. New York: Association for Computing Machinery, 2003. 76-82. [doi: 10.1145/948187.948201]
    [10] Flake H. Structural comparison of executable objects. In: Proc. of the Int'l Conf. on Detection of Intrusions and Malware & Vulnerability Assessment (DIMVA 2004). Dortmund: Association for Computing Machinery, 2004. 83-97. http://citeseerx.ist. psu.edu/viewdoc/summary?doi=10.1.1.83.6632
    [11] Gao DB, Reiter MK, Song D. Binhunt: Automatically finding semantic differences in binary programs. In: Proc. of the Int'l Conf. on Information and Communications Security. Berlin, Heidelberg: Springer-Verlag, 2008. 238-255. [doi: 10.1007/978-3-540- 88625-9_16]
    [12] Bailey M, Oberheide J, Andersen J, Mao ZM, Jahanian F, Nazario J. Automated classification and analysis of Internet malware. In: Kruegel C, Lippmann R, Clark A, eds. Proc. of the 10th Int'l Conf. on Recent Advances in Intrusion Detection. Berlin, Heidelberg: Springer-Verlag, 2007. 178-197. [doi: 10.1007/978-3-540-74320-0_10]
    [13] Manevich R, Sridharan M, Adams S. PSE: Explaining program failures via postmortem static analysis. In: Proc. of the 7th Fundamental Approaches to Software Engineering (FASE 2004). Barcelona: Association for Computing Machinery, 2004. 63-72. [doi: 10.1145/1029894.1029907]
    [14] Flanagan C, Leino K, Lillibridge M, Nelson G, Saxe JB, Stata R. Extended static checking for Java. In: Proc. of the 23rd Int'l Conf. on Programming Language Design and Implementation (PLDI 2002). New York: Association for Computing Machinery, 2002. 234-245. [doi: 10.1145/512529.512558]
    [15] Csallner C, Smaragdakis Y, Xie T. Dsd-Crasher: A hybrid analysis tool for bug finding. ACM Trans. on Software Engineering and Methodology, 2008,17(2):1-37. [doi: 10.1145/1348250.1348254]
    [16] Gu ZX, Barr ET, Hamilton DJ, Su ZD. Has the bug really been fixed. In: Proc. of the 32nd Int'l Conf. on Software Engineering (ICSE 2010). Cape Town: IEEE Computer Society, 2010. 55-64. [doi: 10.1145/1806799.1806812]
    [17] Jaffar J, Murali V, Jorge A, Andrew E. TRACER: A symbolic execution tool for verification. In: Proc. of the 24th Int'l Conf. on Computer Aided Verification (CAV 2012). Berkeley: Springer-Verlag, 2012. 758-766. [doi: 10.1007/978-3-642-31424-7_61]
    [18] Li Y. Termination analysis of nonlinear loops. Ruan Jian Xue Bao/Journal of Software, 2012,23(5):1045-1052 (in Chinese with English abstract). http://www.jos.org.cn/1000-9825/3982.htm [doi: 10.3724/SP.J.1001.2012.03982]
    网友评论
    网友评论
    分享到微博
    发 布
引用本文

郭曦,王盼.相关路径静态分析中协同式逆向推理方法.软件学报,2015,26(1):1-13

复制
分享
文章指标
  • 点击次数:
  • 下载次数:
  • HTML阅读次数:
  • 引用次数:
历史
  • 收稿日期:2014-02-08
  • 最后修改日期:2014-04-03
  • 在线发布日期: 2014-08-22
文章二维码
您是第19932852位访问者
版权所有:中国科学院软件研究所 京ICP备05046678号-3
地址:北京市海淀区中关村南四街4号,邮政编码:100190
电话:010-62562563 传真:010-62562533 Email:jos@iscas.ac.cn
技术支持:北京勤云科技发展有限公司

京公网安备 11040202500063号