一种多项式时间的路径敏感的污点分析方法  

A Polynomial Time Path-Sensitive Taint Analysis Method

作　　者：李佳静[1,2,3] 王铁磊[2,3] 韦韬[2,3] 凤旺森[2,4] 邹维[2,3] 

机构地区：[1]中国矿业大学(北京)机电与信息工程学院,北京100083 [2]网络与软件安全保障教育部重点实验室(北京大学),北京100871 [3]北京大学计算机科学技术研究所,北京100871 [4]北京大学计算中心,北京100871

出　　处：《计算机学报》2009年第9期1845-1855,共11页Chinese Journal of Computers

基　　金：国家发改委信息安全专项(发改办高技[2007]2035);教育部科技创新工程重大项目培育资金项目(707001)资助~~

摘　　要：提出了一种解决静态污点分析方法在进行路径敏感的分析时面临的路径爆炸的问题的方法.该方法将污点分析问题转化为加权下推自动机的广义下推后继问题,进一步利用污点数据在程序中的可达性,减少后续分析中需要精确执行的路径数.从而该方法能够以多项式的时间复杂度实现程序状态空间遍历,并能在发现程序违反安全策略时自动生成反例路径.设计实验使用该方法对击键记录行为进行了刻画,对恶意代码程序和合法软件进行了两组分析实验,并与现有的方法进行了对比分析.实验证明本文的方法可以有效地对具有较多分支的程序进行路径敏感的污点分析。This paper proposes a method to solve the path explosion problem in path-sensitive taint analysis. The method transformed the taint analysis problem into a generalized pushdown successor problem by bringing the weighted pushdown system theory into taint analysis, so it could reduce the number of paths to be accurately executed. With this method, taint analysis can be performed in a polynomial time, and counter paths can be automatically generated. The authors designed experiments based on this method to model and detect keylogging behaviors. By comparing the authors＇ work with existing methods such as the raw traversal method and the full point-wise method, it is found to have exceptional efficiency in processing complex binary programs with a lot of branches, and has both a smaller time expense and a smaller space expense.

关 键 词：加权下推自动机 数据流分析 污点分析 恶意行为 击键记录 

分 类 号：TP309[自动化与计算机技术—计算机系统结构]