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

作者：李佳静; 王铁磊; 韦韬; 凤旺森; 邹维

来源：计算机学报, 2009, (09): 1845-1855.

• 加权下推自动机
• 数据流分析
• 污点分析
• 恶意行为
• 击键记录 weighted pushdown system
• dateflow analysis
• taint analysis
• malicious behavior
• keylogger

提出了一种解决静态污点分析方法在进行路径敏感的分析时面临的路径爆炸的问题的方法.该方法将污点分析问题转化为加权下推自动机的广义下推后继问题,进一步利用污点数据在程序中的可达性,减少后续分析中需要精确执行的路径数.从而该方法能够以多项式的时间复杂度实现程序状态空间遍历,并能在发现程序违反安全策略时自动生成反例路径.设计实验使用该方法对击键记录行为进行了刻画,对恶意代码程序和合法软件进行了两组分析实验,并与现有的方法进行了对比分析.实验证明本文的方法可以有效地对具有较多分支的程序进行路径敏感的污点分析,同时具有较小的时间复杂度和空间复杂度

• 单位
  北京大学; 北京大学王选计算机研究所; 中国矿业大学（北京）