基于源代码的指针分析算法的安全性改进.pdfVIP

第25卷第 l2期 计算机应用与软件 Vo1．25No．12 2008年 12月 ComputerApplicationsandSoftware Dec．2008 基于源代码的指针分析算法的安全性改进 魏 磊 谢 立 (南京大学计算机软件新技术国家重点实验室，南京大学计算机科学与技术系 江苏 南京210093) 摘 要 提出了一种安全性更强的指针分析算法。通过对四种常用的指针分析算法的综合分析，选取了Steensgaard算法进行安 全性改进，在该算法的基础上通过添加强制类型转换的语义并对算法的类型系统的推导规则进行改进，使其避免了因精确性损耗而 导致的攻击的漏报，同时还保持 了原有算法复杂度不变。 关键词 指针分析 算法 类型系统 函数标签 SECURITY IMPRoVEM ENT OF PoINTER ANALYSISALGORITHM BASED oN SoURCE CoDE WeiLei XieLi (StateKeyLaboratoryforNovelSoftwareTechnology，DepartmentofCo，uterScienceandTechnology，Na ngUniversity，Na ng210093，Jiangsu，China) Abstract Inthepaperitputsforwardanew pointeranalysismethodwithhighersecurity．ItselectstheSteensgaardalgorithm aftercorn— prehensivelyanalyzedfourcommonpointeranalysisalgorithmsandimprovesitssecurity．Basedonit，throughaddingsemanticsofcompulsory typeconversionandfurthermodifyingtheinferencerulesoftypesystem ，themissingreport ofattackscausedbyprecisionlossesisavoided． Meanwhileitkeepstheoriginalalgorithm complexityconstant． Keywords Pointeranalysis Algorithm Typesystem Functiontag 唯一的一个集合，作为所有地址的别名集合 ，任何一个指针被看 0 引 言 作可以指向其中任何一个地址。这样的方法 比较简单可行，时 间复杂度为O(n)，但与此同时由于它将所有的被取地址的对 指针分析的研究是从上个世纪70年代末期开始的。指针 象都作为一个集合看待，在很多情况下它的精确度的损失会 分析是一种在编译时刻决定一个程序的指针的可能指向的程序 很大。 分析方法。由于这样的一个分析在本质上是不可判定的，所 以 ·Steensgaard算法：这是一种合并查找的指针分析方法，其 目前很多方法都对这个问题做 了一定程度上的近似 ，在精度和 基本思想是合并两个可能被同一个指针指向的内存对象为一个 效率方面作出不同的偏向和平衡。因此需要对不同的指针分析 内存对象。由于合并查找的算法的代价本身很低 ，且该方法只 方法进行综合分析以选取一种合适的算法。 需要扫描程序源码一趟，所以这个算法的复杂度是近乎线性的。 本文通过对 目前已有的四种指针分析方法的精确度、效率 它本身是流非敏感的算法 ，经过适当扩充可以成为上下文敏感 和可扩展性