一种多项式时间的路径敏感的污点分析方法-计算机学报.PDF

第卷第期 计 算 机 学 报 ３２ ９ 　　　　　　　　 　 Ｖｏｌ．３２Ｎｏ．９ 年月 ２００９９ Ｓｅｔ．２００９ ＣＨＩＮＥＳＥＪＯＵＲＮＡＬＯＦＣＯＭＰＵＴＥＲＳ ｐ 　 一种多项式时间的路径敏感的污点分析方法 ），），） ），） ），） ），） ），） １２３ ２３ ２３ ２４ ２３ 李佳静 王铁磊 韦韬 凤旺森 邹维 　 　　 　 　　 ） １（中国矿业大学（北京）机电与信息工程学院北京 ） １０００８３ 　 　 ） ２网络与软件安全保障教育部重点实验室北京大学北京 （ （ ） ） １００８７１ 　 　 ） ３北京大学计算机科学技术研究所北京 （ ） １００８７１ 　 　 ） ４北京大学计算中心北京 （ ） １００８７１ 　 　 摘要提出了一种解决静态污点分析方法在进行路径敏感的分析时面临的路径爆炸的问题的方法该方法将污 ． 　　 点分析问题转化为加权下推自动机的广义下推后继问题，进一步利用污点数据在程序中的可达性，减少后续分析 中需要精确执行的路径数从而该方法能够以多项式的时间复杂度实现程序状态空间遍历，并能在发现程序违反 ． ， 安全策略时自动生成反例路径设计实验使用该方法对击键记录行为进行了刻画对恶意代码程序和合法软件进 ． 行了两组分析实验，并与现有的方法进行了对比分析实验证明本文的方法可以有效地对具有较多分支的程序进 ．