（计算机软件与理论专业论文）基于二叉决策图的别名分析研究.pdf

摘要 别名是 c/c+程序的典型特征之一，通过别名分析可以提高数据流分析的准 确性并且将有助于构建性能良好的程序分析工具。本文在综述别名分析的作用及 研究现状的基础上，对别名信息的收集、记录以及基于别名信息的推导进行了研 究，设计并实现了一个以二叉决策图为基础的别名分析框架。 首先，阐述了采用二叉决策图作为别名信息记录方式的优势，并给出了二叉 决策图的构造及操作算法，在此基础上根据逻辑编程语言 datalog 的基本语义， 详细设计了别名信息表示与推导规则。其次，为了收集准确的别名信息，设计了 一种交替进行过程内和过程间别名分析的机制，过程内采用流敏感、域敏感、路 径敏感的分析方法，并且对于数组类型以及类型信息进行了处理，过程间采用基 于总结的上下文敏感分析方法， 这种机制的主要优点是提高了别名信息的准确性， 减少了函数体的分析次数及时间开销。最后，本文论述了基于别名分析能够完成 的部分安全检查。该别名分析方法已在 c/c+安全检查工具中实现，实验证明此 方法是有效的。 关键词：别名分析 流敏感 域敏感 基于总结的上下文敏感 二叉决策图 abstract one of the typical characteristic of c/c+ program is the existence of alias.with the help of alias analysis, the accuracy of data-flow analysis can be improved and program analyzing tools will be more powerful. based on the summary of alias analysis effection and current research background, this paper studies the collection of the alias information and designs a binary decision diagram-based alias analysis framework. firstly, this paper describes the advantages of the use of binary decision diagram as an alias of information record, and gives the algorithms of the structure and operation of the binary decision diagram. on this basis, using the semantics of the basic logic programming language datalog, we design the alias information representation and derivation rules.secondly, in order to collect accurate alias information, this paper designs a mechanism of analyzing the the intraprocedural and interprocedural alias information alternately. the intraprocedural alias analysis presents the way of flow sensitive, field sensitive, path sensitive and type safe analysis. the interprocedural alias analysis uses summary-based context sensitive analysis. the main advantage of such a mechanism is that not only the accuracy of the information can be improved but also the analysis time of the function body and the time expenses can be reduced. finally, this paper presents the security check based on the alias analysis. this method has been implemented in a safety checking tool for c/c+ programs, and experimental results illustrate that the method is effective. keyword: alias analysis flow-sensitivity field-sensitivity summary-based context-sensitivity binary decision diagram 创新性声明 本人声明所呈交的论文是我个人在导师的指导下进行的研究工作及取得的研 究成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中 不包含其他人已经发表或撰写过的研究成果，也不包含为获得西安电子科技大学 或其他教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究工 作所做的任何贡献均已在论文中作了明确的说明并表示了谢意。 申请学位论文若有不实之处，本人承担一切相关责任。 本人签名： 日期： 关于论文使用授权的说明 本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：研究 生在校攻读学位期间论文工作的知识产权单位属西安电子科技大学。本人保证毕 业离校后，发表论文或使用论文工作成果时署名单位仍然为西安电子科技大学。 学校有权保留送交论文的复印件，允许查阅和借阅论文；学校可以公布论文的全 部或部分内容，可以允许采用影印、缩印或其他复制手段保存论文。 （保密的论文 在解密后遵守此规定） 本学位论文属于保密在_年解密后适用本授权书。 本人签名： 日期： 导师签名： 日期： 第一章 绪论 1 第一章 绪论 1.1 研究背景 1.1.1 c/c+程序安全检查的现状 c/c+程序设计语言由于灵活高效、功能强大的特点，在软件开发领域中得 到了广泛的应用， 但在提供灵活控制能力的同时也带来了一些潜在的安全性问题， c/c+程序中易出现如内存泄漏、缓冲区溢出、指针非法引用等安全漏洞，这些 安全漏洞的存在极大地威胁着系统的稳定性和可靠性1。 针对 c/c+程序中可能存在的安全漏洞，目前学术研究领域中已经提出了多 种程序安全检查方法，如模型检验2（model checking） 、进化测试3（evolutionary testing） 、程序分析（program analysis）等。其中程序分析是目前主流的验证软 件安全性的方法之一，包括静态分析和动态分析方法。 静态分析通过分析源代码或机器代码来检查程序中的安全漏洞， 在词法分析、 语法分析和语义分析过程中找出能够导致程序错误的结构异常、控制流异常及数 据流异常，无需执行被分析程序。目前用于 c/c+程序的静态程序安全检查工具 有很多，如通过构建所有权类型系统检测内存泄漏安全漏洞的 clouseau4，通过 使用前置条件和后置条件定义 c/c+程序中各种语句的安全性条件并利用该条件 执行安全检查的 prefix5，通过程序员向程序中手工加入注释信息的方法进行程 序安全检查的 splint6和 pclint7等。 动态分析需要设计一组或多组测试数据，通过向程序中植入分析代码，并实 际运行被测程序，根据程序的运行结果检查程序中的安全漏洞，由于动态分析运 行被测程序，因此检查精度较高，但由于设计的测试数据很难覆盖程序的所有运 行情况，并且仅考虑程序中的单条执行路径，导致某些漏洞无法被检测出来，其 分析是不完备的。采用动态分析技术实现的 c/c+程序安全检查工具有 purify8、 valgrind9等。 本文源于某实际科研项目，该项目专注于提供一组针对 c/c+程序设计的安 全规范， 并在此安全规范的基础上实现一个针对 c/c+程序的静态安全检查工具。 该项目希望通过为 c/c+程序员引入自动化安全检查手段，帮助其检查和避免安 全漏洞10,11，从而保证软件系统的安全和可信12。 基于二叉决策图的别名分析研究 2 1.1.2 别名分析在程序安全分析中的作用及研究现状 别名是众多高级语言的特征之一，这就使得别名分析成为数据流分析的重要 模块，并且程序安全分析依赖于的数据流分析，特别是对 c/c+程序进行数据流 分析时，由于指针类型和引用类型的存在，若预先不对这些变量的别名信息进行 分析，所有分析结果都必须采用保守的估计，比如假设指针指向所有相同类型的 变量，这种假设可能会影响分析结果的可信度，甚至会导致分析完全不正确，并 最终使程序安全分析的准确度大大降低。因此，别名分析对程序分析起着十分重 要的作用，选择合适的分析算法，可以减小别名的存在对程序安全分析结果的影 响，提高分析的精度。 别名分析的研究是从上个世纪 70 年代开始的， 到目前为止， 存在很多种分析 算法13-16。这些算法常常需要在分析效率和处理结果精度上进行折衷，它们按照 处理方式不同，如是否考虑过程中的控制流信息、是否考虑函数调用上下文、对 复杂类型的数据结构是否作为整体处理等，进而形成不同的分析算法。目前衡量 分析结果的主要因素有：上下文敏感、流敏感、路径敏感、域敏感和类型安全。 特别是在 c/c+程序中，由于复杂数据结构及多种控制结构的存在，使得实际的 别名分析比较复杂，函数调用的存在尤其加剧了这种复杂性。但目前大多数研究 成果为了追最求高速度，忽略了这些因素或者仅仅关注上下文敏感等少数几个因 素，这些分析的结果都是不准确的，对于复杂程序安全的分析，会产生大量的误 报或者漏报。 由于别名信息是其他分析的基础，在敏感分析的基础上，每个不同的关键点 都需要信息的备份。对于大量别名信息的存储和操作，直接影响整个安全检查的 效率。在众多别名信息表示方法中，国外学者 emami 和 wilson 提出的方法影响 较大，emami 首次提出了指针别名信息的指向（point-to）表示法17，改进了已有 的别名对表示法，能比较有效的表示指针别名信息，并且他们还引入了一个上下 文敏感的跨过程指针分析框架。 随着二叉决策图 （binary decision diagram， bdd） 在模型领域的广泛应用，jianwen zhu 和 silvian calman 对已有的方法进行了改 进，引入布尔代数中的二叉决策图18-20来获取函数调用点及被调用函数处的程序 状态和指针指向关系，该方法可得到较为准确的别名信息并且效率较高。为了便 于别名信息的求取，john whaley 和 monica s. lam 简化了信息的收集方式20，他 们使用逻辑编程语言 datalog，根据已有的别名信息来推导出新的信息集合。 第一章 绪论 3 1.2 c/c+静态安全检查工具及别名分析 1.2.1 工具的整体框架 本课题研究的 c/c+静态安全检查工具的整体框架如图 1.1 所示，工具分为 前端和后端两个部分。前端通过对 c/c+程序源代码进行分析，为后端提供分析 需要的符号信息、抽象语法树信息、控制流信息和函数拓扑排序序列。前端主要 包括以下四个部分： 图 1.1 c/c+程序的静态安全检查工具框架 基于二叉决策图的别名分析研究 4 (1) 预处理器：基于 antlr lexer 与 parser 开发完成，实现对 c/c+程序的 预处理，生成“*.i”文件，供后续语法分析使用； (2) 语法分析器：基于 antlr lexer 与 parser 开发完成，实现对“*.i”文件 的语法分析，构造符号表及对应的抽象语法树，完成模板处理与抽象语法树 （abstract syntax tree，ast）结点中的名字解析等工作； (3) 控制流图分析器：通过遍历抽象语法树生成携带抽象语法树信息的控制 流图，为后端分析提供必要的信息； (4) 函数依赖分析器：遍历控制流图获取函数调用依赖关系，根据此依赖关 系产生函数调用的拓扑排序序列，用于后续分析。 后端从前端获取符号表、抽象语法树和控制流图等的信息，进行数据流分析 器和安全分析，从而找出安全漏洞。主要包括两个部分： (1) 数据流分析器：基于函数拓扑排序序列，依次扫描控制流图，通过数据 流方程21计算完成指针别名分析与操作对象 （变量与对象） 可能状态集合的计算， 计算结果挂在对应的控制流图结点上； (2) 安全分析器：基于函数拓扑排序序列，自下而上依次扫描控制流图，利 用结点上的别名信息与操作对象可能状态集合检查是否出现违反安全规则的现 象，如果是，则报告安全漏洞。 1.2.2 别名分析模块 别名分析是指通过对程序的静态分析来近似地求取出程序中出现的别名表达 式所指向的目标。互为别名的表达式由于指向同一块内存空间，通过其中的任何 一个表达式操作该内存空间都会影响到其它的表达式，也就是说互为别名的各表 达式的状态会相互影响。 别名分析从类型上可以分为引用别名分析和指针别名分析，引用别名分析产 生引用关系，指针别名分析产生指向关系，其中引用别名信息的形成仅仅发生在 引用初始化语句，并且引用别名操作简单，因此引用别名分析可以看作指针别名 分析的一个子集，用指针别名分析涵盖所有的别名分析操作。在这里，别名表达 式中的指针表达式是指表达式的类型求值结果为指针类型的表达式，之所以说指 针表达式而不说指针变量，这是由 c/c+语言数据结构的复杂性所决定的，实际 上变量只是表达式的一个特例。例如对于一个结构变量 s 内指针类型的域 f， s.f 是指针表达式而不是指针变量。 别名分析不但有助于提高数据流分析的准确性、提高程序优化的效果以及增 强对程序并行性的检测能力，还有助于构建性能良好的程序调试工具与程序分析 工具。因此，别名分析对程序分析起着十分重要的作用，不进行别名分析或分析 第一章 绪论 5 算法选择不当，可能会影响分析结果的可信度，甚至会导致分析结果的完全不正 确。 本安全检查工具中的别名分析模块主要解决以下几点问题：第一点，通过哪 些算法以及如何应用这些算法收集别名信息；第二点，如何记录收集到的海量别 名信息；第三点，在别名分析的基础上，如何进行安全检查；第四点，如何运用 已有的别名信息推导出新的信息。本文工作的重点是上述的前三点问题，第四点 问题主要是为了后续模块分析提供基于别名分析的有用信息。 1.3 论文的研究内容和论文的组织 本文的工作是别名分析的设计与实现，在研究前人的理论成果的基础上，设 计数据结构和相关算法，主要内容如下： (1) 设计并实现了别名分析的总体框架； (2) 别名信息采用二叉决策图进行存储，将别名信息操作转化为集合操作， 有效的降低内存使用，提高了执行效率； (3) 利用逻辑编程语言 datalog22可以将别名信息的收集和后续的分析相分 离，便于程序的后续扩展； (4) 将别名分析分为过程内和过程间两个模块，过程内别名分析采用流敏感、 路径敏感、域敏感和类型安全的分析方法；在过程间别名分析采用基于总结的上 下文敏感分析方法21。在遍历控制流图和抽象语法树的过程中，交替对过程内和 过程间的别名信息进行分析； (5) 对过程内需处理的各种语句进行分类，包括指针赋值语句、含初始化的 别名类型声明语句、控制流语句等，并针对每一个分类均进行了有效的处理； (6) 将基于总结的上下文敏感过程间别名分析所需处理的问题细化为几个阶 段，并依次进行解决。 论文的组织结构如下： 第一章为绪论，分析了静态程序安全分析的研究现状，讨论了别名分析在静 态程序安全分析中的作用及相关的研究现状，并介绍了本课题研究的 c/c+静态 安全检查工具的整体框架及系统功能。 第二章首先阐述了别名分析的相关技术，包括抽象语法树的结构描述和遍历 方法、符号表的结构和操作方法、控制流图的结构描述和遍历方法等；分析了别 名信息表示手段及典型别名分析方法，设计了一种流敏感、上下文敏感的别名分 析方法，并给出了别名分析框架的整体设计。 第三章论述用于别名信息表示的二叉决策图定义及使用的基本关系操作，用 于别名信息推导的 datalog 基本语义和推导规则，并在此基础上给出了别名信息 基于二叉决策图的别名分析研究 6 表示与推导规则的详细设计。 第四章论述过程内别名分析的详细设计与实现，分小节分别论述了域敏感、 流敏感、路径敏感等过程内别名分析方法，讨论了分析过程中对于数组类型的处 理以及类型信息的收集方法，并结合具体的抽象语法树结构给出了详细的算法描 述。 第五章为过程间别名分析的关键技术及其实现，详细描述了基于总结的上下 文敏感的别名分析算法，并说明过程内和过程间别名分析的衔接问题。最后，通 过有代表性的实例验证了论文所采用的别名分析算法的正确性和有效性。 第六章论述了基于别名分析能够完成的部分安全检查，包括内存泄露、数组 访问越界等。 第七章对本文工作进行了概括和总结。 第二章 别名分析的整体设计 7 第二章 别名分析的整体设计 当程序中有两个或两个以上的表达式指向同一块内存空间时，则这些表达式 关于该内存空间形成别名关系。根据表达式类型的不同，又分为指针别名和引用 别名。别名分析旨在确定何时两个表达式会指向同样的存储空间，并对该别名关 系进行记录。 别名分析是一种典型的数据流分析，该分析基于项目前端生成的完整程序中 间表示及函数调用拓扑序列进行，将整个分析过程分为前期别名关系收集和后期 信息推导两个阶段。前期分析过程涉及过程内分析与过程间分析两个层次，本章 在分析程序中间表示结构、别名信息表示手段及典型别名分析方法的基础上，给 出了一种流敏感、上下文敏感的别名分析方法，然后给出了别名分析框架的整体 设计。 2.1 别名分析的相关技术 项目前端借助程序分析器生成工具 antlr 生成识别目标语言的语法分析 器，扫描目标语言的源代码，生成包括抽象语法树、符号表及控制流图等在内的 完整程序中间表示。别名分析在前端生成的中间表示基础上进行，下面首先对这 些中间结构依次进行介绍。 2.1.1 antlr 和抽象语法树 2.1.1.1 antlr antlr 23,24 （another tool for language recognition）是由 san francisco 大 学的 terence parr 等人开发的一种程序分析器自动生成工具，它生成支持 ll(k) 的预测分析器。利用 antlr 可以生成词法分析器、语法分析器和抽象语法树遍 历框架（tree walker） 。它采用 ebnf（扩展巴克斯范式）来描述词法规则、语法 规则和抽象语法树结构，并且支持在同一个文件中描述词法规则、语法规则和抽 象语法树结构，易于使用、阅读和维护。 2.1.1.2 抽象语法树 基于二叉决策图的别名分析研究 8 在程序分析中，抽象语法树作为一种重要的程序中间表示，是后期程序分析 的基础。与源程序的线性结构相比，ast 的树状结构便于语言结构的遍历和信息 的获取。以抽象语法树为分析基础的原因是：抽象语法树作为程序中间表示的一 个抽象层次，可以较好的表示各种语言的语法特征；对抽象语法树的遍历过程相 当于源程序的语法分析过程，遍历过程中对特定树节点的处理操作相当于语法分 析过程中的语义动作，保留了源程序所有的完整信息，可以提取符号信息，实现 对语言特性的处理；同时 antlr 提供了遍历抽象语法树的框架和操作接口，使 得遍历抽象语法树的过程简单、有效。 但是 ast 的树结构无法表示一些复杂的控制流信息，例如：跳转语句 go、 break 和 continue 等，一般使用控制流图（control flow graph，cfg）来表示程序 的控制流信息。在实际的程序分析中，采用 ast 和 cfg 相结合的方法表示程序 的结构，ast 表示表达式的结构，cfg 表示程序的顺序、分支和循环结构。 (一) antlr 中抽象语法树的结构 父节点 子节点子节点 父子边 兄弟边 图 2.1 antlr 中 ast 结构 antlr 中 ast 的结构如图 2.1 所示，与传统的 ast 结构不同，antlr 采 用任意树的二叉树表示方式描述 ast 的结构，每个 ast 节点最多有两个出边： 节点的第一个孩子和兄弟；传统的 ast 节点的出边为其孩子，且孩子的个数没有 限制，因此孩子的个数是不确定的，结构比较复杂。通过在语言的文法中添加标 记，antlr 就可以在语法分析时生成程序的 ast，antlr 中 ast 的结构是 antlr 实现自动生成和遍历 ast 的基础。 (二) 抽象语法树的存储和遍历 整个程序的 ast 结构是比较庞大的，遍历 ast 生成程序的 cfg 之后，将表 达式的 ast 节点绑定到对应的 cfg 节点上，其他的 ast 节点在前端分析过程中 逐步释放。后续程序分析在遍历 cfg 的过程中，可通过 cfg 中节点提供的方法 获取绑定到该节点上的 ast 的根节点，从而得到具体的语言结构信息，在此基础 上进行相应的处理。 第二章 别名分析的整体设计 9 若要从 ast 上获取信息， 需要遍历 ast。 antlr 提供了方便的 ast 遍历机 制，它考虑每棵 ast 其实就是一个记号流，而这些记号流满足一定 ast 语法规 则，所以 antlr 提供了根据 ast 语法规则自动生成 ast 遍历框架 treeparser 的机制。 treeparser 能正确的遍历符合该文法中语法结构的 ast， 对不符合的 ast 在遍历时报错。生成 ast 遍历框架的语法规则是一组含有语义动作、语法谓词、 语义谓词的 ebnf 规则，例如： rule: alternative1 | alternative2 . | alternativen; 每个候选项形如：# (root-token child1 child2 . childm) ，意味着该候选项表示 一个 ast， 并且有 m 个孩子， 其中树根为 root-token， 孩子分别为 child1、 child2、 、 childm。在语法规则描述中可以方便的嵌入语义动作，这些语义动作实际上就是 目标语言的代码。例如上面文法规则中若某个候选项如下： # (root-token /*语义动作 0*/ child1 /*语义动作 1*/ child2 . childm ) 表示如果treeparser遍历该候选项表示的ast， 则首先匹配根节点root-token， 然后执行语义动作 0；接着遍历孩子 child1，然后执行语义动作 1；再遍历孩子 child2、childm。 (三) 别名分析关注的 ast 抽象语法树节点繁多，没有必要逐一处理。根据别名分析的需要，从中抽取 一些重要节点作为分析的切入点，由切入点开始搜集信息。这些节点主要反映重 要的控制流和数据流变化，大致分为如下几大类： (1) 声明节点：本文主要关注的是包含指针或引用类型的变量声明； (2) 表达式节点：函数调用表达式，赋值表达式； (3) 控制流语句节点：本文可以处理的控制流语句包括：分支语句和循环语 句。控制流语句在程序的执行过程中依赖上下文环境，在程序执行路径上具有不 确定性，因而遇到这类语句节点，需要做特殊的分析处理。 本文在程序分析时，主要从上述三类节点入手，根据产生式和节点的类型， 采用相应的算法，完成别名分析的任务。 基于二叉决策图的别名分析研究 10 2.1.2 符号表系统 在对程序的分析过程中，需要用符号表记录符号信息来协助进行上下文相关 的检查，同时为安全检查工具后端安全漏洞的检查提供需要的符号信息。 符号表系统，作为中间表示的一部分被其他模块使用。负责完成两个任务： (1) 分析给定的源代码，保存符号信息到符号表子系统中，允许后续分析子 系统检索上述信息； (2) 提供一组操作接口，简化后续的安全检查模块的实现工作。 (一) 符号表结构 整个符号表系统分为两部分：主符号表和作用域符号表，主符号表中记录着 整个符号表系统中的所有符号，通过符号的内部名字进行存储；作用域符号表是 各个具体作用域的一个公共基类，它表示了各类作用域的共同的属性。每个作用 域条目上面都附有一个唯一的作用域域值来表述相应的作用域空间，当离开相应 作用域空间时候，方便消除在这个作用域空间内的临时别名关系。 (二) 符号条目类层次结构 符号表中记录的是符号条目，其中所有的符号条目都继承于父类 symbolitem。本文重点关注其中的变量条目（variableitem） 、类型条目（type） 、 函数符号条目（funcsymbolitem）等，在每个相应的条目上都附有一个唯一的域 值。 在别名分析的过程中， 就可以通过抽象语法树来得到相应符号条目上的域值， 来构造相应的基于二叉决策图的 datalog 谓词关系。 在本文的研究中，主要关注的是引用变量和指针变量信息，特别是对于多级 指针，引入扩充变量的概念，保证了跨过程分析中的别名信息的相容性。扩充变 量的域值信息直接保存在相应的多级指针变量符号条目上，保证了别名分析的一 致性，既避免了相同信息的重复记录，又方便了变量状态的获取，大大提供了检 测的效率。 2.1.3 控制流图 控制流图25,26是一种通用的程序结构表示方法，它反映了程序中语句、模块 之间的执行顺序和相互调用关系，是数据流分析、控制流分析、函数依赖分析等 的基础。程序中每条语句在控制流图中有相应的节点对应，在控制流图对应的数 第二章 别名分析的整体设计 11 据结构中通常为每个节点分配唯一的节点编号，控制流图中的边通常表示程序中 语句间的控制流程。 定义 2.1 控制流图是一个有向图 g = (v, e )， v 是节点的集合， e 是有向边的 集合。其中节点表示语句 w，边 u v 表示从 u 到 v 可能的控制流。 令(u, v)表示控制流图中的边 u v ，则称 u 是 v 的前驱，v 是 u 的后继；节点 n 的所有前驱组成的集合称为 n 的直接前驱集，记为 p r e d ( n ) ，节点 n 的所有后继 组成的集合称为 n 的直接后继集， 记为 s u c c ( n ) 。 为 g增加两个特殊的节点： s t a r t 称为开始节点或入口，它没有前驱；s t o p称为退出节点或出口，从每个节点都 可到达它。一个程序可能有几个出口（即结束语句） ，在控制流图中加入一个虚节 点 s t o p是为了保证程序控制流图 g出口的唯一性，并令所有结束语句对应的节 点都指向它。 控制流图有唯一的入口节点 s t a r t和唯一的出口节点 s t o p ，每个节点可以 有多个后继节点。通常有两个后继的控制流图节点有属性“t ” （真）和“f ” （假） ， 这些属性和节点的出边关联。对于 g中的任意节点 n ，分别存在一条从 s t a r t 到 n 的路径和从 n 到 s t o p的路径。为模拟程序的执行流程，别名分析采用深度 优先的遍历方式遍历控制流图，在遍历过程中对各种语句进行处理。 2.2 别名信息表示方法 设计任何一种别名分析算法首先必须面对的问题便是别名信息表示法的选 择，特别是在分析大型系统程序中，对于收集到的海量信息的存储和操作。常见 的别名信息表示法有两种：别名对表示法和指向表示法。别名对表示法把互为别 名的表达式用一个二元组来表示。指向表示法用一个由指针表达式与指针表达式 所指向的目标表达式构成的二元组表示别名信息。这些方法虽然可以直观地表示 别名信息，但是信息冗余并且信息量太少。 二叉决策图是逻辑布尔函数的一种高效表示方法，在计算机科学以及数字电 路与系统等领域中有广泛的应用，并且在模型检查领域展现了强大的高效性。因 此，本文利用二叉决策图的优点将其应用到别名信息的表示上，把别名分析的底 层数据结构的操作问题转化为集合问题，有效解决别名信息存储和操作的执行效 率。同时，利用二叉决策图表示的别名信息可以应用到逻辑编程语言 d a t a l o g的 谓词关系中，根据 d a t a l o g 的规则，可以推导出所需的规则信息。 在图 2 . 2的语句序列中，堆对象由每行句首的字母表示，所以程序产生了堆 对象 h 、i 和 j 。根据流敏感的分析，得到语句结束后的别名关系如下： 采用别名对表示法，则可以表示为 ( a , b ) , ( a , c ) , ( b , c ) , ( * a , i ) , ( * b , i ) , ( * c , i ) ； 采用指向表示法，则可以表示为 ( a , i ) , ( b , i ) , ( c , i ) ； 基于二叉决策图的别名分析研究 1 2 图 2 . 2 程序示例 采用二叉决策图的关系元组( v , h ) 表示，元组中用 v域表示变量域，h域表 示堆对象域，每个域中分别含有两个变元 v1、v0和 h1、h0。将 v和 h中的每一 个变元用 0 和 1 表示，表述方法为：0 0 表示 a 和 h ，0 1 表示 b 和 i ，1 0 表示 c 和 j ，这个指向关系可以用变元位表示为 0 0 0 1 , 0 1 0 1 , 1 0 0 1 ，用布尔代数中的析取范 式表示为( v1v0h1h0) ( v1v0h1h0) ( v1v0h1 h0) 。 从表示方法中可以看出， 别名对表示法相对于其他两种表示有着明显的冗余。 虽然指向表示法在表示指向信息时简单明了，但是在存储数据时候，每个变量对 应一个记录条目，有 2 n 个变量则有 2 n 个条目。而采用二叉决策图表示时，虽然布 尔代数的表示晦涩难懂，但是变量用元组域中的变元表示时，2 n 个变量用 n 个变 元就可以表示，在实际存储中大大减少了内存空间占用，适合海量数据的存储。 通过上面代码的分析，就可以得出二叉决策图是一种表示别名信息的合适方 法，并且在第三章详细说明如何由已得到的析取范式转换成二叉决策图的记录。 在论文后面的例子说明中，采用简单易懂的指向表示法说明别名关系，但是工具 中实际采用二叉决策图存储别名信息。 2.3 别名分析方法的选择 别名分析方法分为过程内和过程间两个层次，每个层次都有多种不同的分析 方法，根据这些方法可以得到符合规则的部分别名信息，下面分层次说明选择那 种分析方法可以得到更加精确的别名信息，以及如何得到更加完整的信息。 2 . 3 . 1 过程内分析方法 过程内的分析方法主要是考虑数据流分析方法。而数据流分析方法分为流非 敏感的 2 7 和流敏感的 2 8 , 3 0 ，别名分析也是数据流分析的内容之一。流非敏感的分 析方法不考虑控制流信息，流敏感的分析方法在分析过程中考虑过程内的控制流 信息，也就是说在流敏感的分析方法中将过程作为一个语句序列处理，而流非敏 感的分析方法中将过程作为一个语句集合处理。流非敏感的分析方法在过程级产 第二章 别名分析的整体设计 1 3 生分析结果，而流敏感的分析方法在语句级产生分析结果。流非敏感的分析方法 仅仅产生新的别名信息，但不会注销已有的信息，而流敏感的分析方法不仅产生 新的别名关系并且会注销部分别名信息。通常流敏感的分析方法较流非敏感的分 析方法更精确，但时间和空间效率较低。 在图 2 . 3 中的示例代码段中，假定在语句 s 1 前不存在别名信息，采用流敏感 和流非敏感的指针别名分析方法得到的分析结果如图所示，此图描述了流敏感和 流非敏感两种指针别名分析方法的主要区别。 图 2 . 3 程序示例 图 2 . 3 中 s 4 处不存在修改任何别名信息的语句，语句 s 5 经过流敏感的分析 后会得到指向关系 ( p , r ) , ( q , t ) ，而经过流非敏感的分析将会得到指向关系 ( p , r ) , ( q , r ) , ( q , s ) , ( q , t ) 。在语句 s 5 处对 q 的赋值时，流敏感的分析方法注销了到达语 句 s 5时 q所有的别名指向关系，符合程序实际的执行情况。该例表明流敏感的 分析较流非敏感的分析可以提供精度更高的分析结果。 2 . 3 . 2 过程间分析方法 函数调用可能会引起全局变量别名信息的修改，也可能会通过对多级指针类 型或引用类型的形参所指向的目标的修改而间接地修改调用点实参的别名信息； 反过来，被调用函数可能会依据函数调用点处别名信息的不同而有不同的分析结 果。因此在对 c / c + + 程序进行别名分析时，必须进行跨过程的别名信息的求取。 过程间别名分析方法按所求取信息的准确程度可分为两类：上下文非敏感 （c o n t e x t - i n s e n s i t i v e ）的分析方法 3 0 , 3 1 和上下文敏感（c o n t e x t - s e n s i t i v e ）的分析 方法 1 6 - 2 0 。上下文非敏感的分析方法对同一函数的不同调用只产生一个唯一的近 似结果，该方法将调用点处所有的可能的别名信息均传入被调函数，每个函数体 仅分析一次，由被调用函数返回的别名信息传播到所有的调用点；而上下文敏感 基于二叉决策图的别名分析研究 1 4 的分析方法依据同一函数不同调用点别名模式的不同而产生不同的分析结果，同 一函数的不同调用上下文都将导致对此函数的一次重新分析。 进行上下文非敏感的分析方法不考虑具体的上下文，效率比较高，但分析结 果不精确，会产生一些额外的别名信息；上下文敏感的分析可求得比较精确的分 析结果，但时间上开销较大。因此，本文在上下文敏感的分析的基础上，给出了 一种基于总结的上下文敏感分析，这种分析方法对于函数入口模式进行比较，如 果入口模式相容，则无需重新分析该函数体，节省了分析方法在时间上的开销。 2 . 3 . 3 完善别名信息的推导 本文通过程序分析器自动生成工具解析源代码，生成的中间表示包含抽象语 法树、符号表等，别名分析在抽象语法树的语法结构处添加相应的语义动作来得 到符合规则的别名信息。所获取的别名信息仅是符合规则的直接数据，这些信息 并不能满足后端安全检查模块的需求，如代码中内存泄露位置的获取等。为了得 到更加完善的别名信息有以下两种方式： ( 1 ) 在已有的语义动作基础上，修改并添加相应的语义规则来获取新的别名 信息； ( 2 ) 在已有的别名分析模块基础上，添加一个信息推导模块，根据所获得的 别名信息推导出新的信息。 综合分析后，第一种方式必须根据后端模块的需求来不断更改已有的语义规 则代码，并且随着程序规模的扩大，这种方式的修改量就急剧增加，会发生很多 遗漏现象；第二种方式将别名信息的收集过程和后续信息的推导过程相分离，在 后端模块有新的需求时， 通过添加信息推导模块的规则就可以获取新的别名信息。 因此，第二种的过程分离方法具有低耦合的特点，不需要改动已有的语义动作， 节省了分析方法在时间上的开销，提高了代码的复用性。 在后续的检查中，安全检查模块需要较为精确的别名信息，否则会产生很多 误报，根据以上论述，本文采用流敏感和基于总结的上下文敏感分析方法作为别 名分析的主要方法来获取基本别名信息，并且添加一个别名信息推导模块以得到 完整的信息。 2.4 别名分析的框架 基于上述分析，本文将别名分析的过程分为别名关系收集模块和信息推导模 块两个主要阶段，别名分析框架流图如图 2 . 4 所示。 第二章 别名分析的整体设计 1 5 图 2 . 4 别名分析框架流图 在图 2 . 4中，关系收集模块为主要分析点，这个模块包括三个子模块，它们 分别为全局分析模块、过程间分析模块和过程内分析模块，全局分析模块结束后 得到全局别名信息， 过程间分析模块和过程内分析模块相互嵌套得到每个 c f g节 点的别名信息，最后关系收集模块得到最终的别名信息；信息推导模块是为了实 基于二叉决策图的别名分析研究 1 6 现后续项目的扩充和别名信息的收集相分离，在不更改关系收集模块的情况下， 应用 d a t a l o g 规则根据已有的别名信息推导出新的信息。 在获取程序调用图的基础上，别名分析采用自顶向下的分析方法，基于程序 分析器前端生成的抽象语法树 a s t和控制流图 c f g ，计算每个过程的别名信息 集，此外对同一函数的不同调用上下文都将导致对此函数的重新分析。由别名信 息构成的集合称为别名信息集（p o i n t e r - a l i a s s e t ，p s ） ，关系收集模块中的基本别 名信息收集算法如下。 算法 2 . 1 关系收集模块中的别名信息收集 输入：全局符号表和所有待分析函数的 c f g 输出：过程间和过程内的别名信息 方法： 计算全局的初始化别名信息集; f o r 入口函数列表中的每个过程 f l o o p i f f 未被分析过 t h e n 以全局的初始别名信息集作为过程入口处成立的别名关系; f o r c f g中的每个节点 c l o o p i f c 包含函数调用语句 t h e n 过程间别名分析算法得出该调用点之后的别名信息集; e l s e 过程内别名分析算法分析 c 节点; e n d i f e n d f o r e n d i f e n d f o r 上述框架中， 依据函数依赖分析得到的函数调用拓扑序列自顶向下进行分析， 首先分析对其他函数依赖最大的函数，即程序入口函数（比如 m a i n 函数） ，将全 局的初始别名信息集作为其入口处成立的别名关系。此框架最显著的特点是交叉 进行过程内分析阶段和过程间分析阶段，在过程内分析中若遇到函数调用语句， 则需进行过程间别名分析，获取调用点之后的别名信息集。此外，对每个过程的 一次分析会产生两个附加的别名信息集，即过程入口处成立的别名信息集和过程 出口处成立的别名信息集。 在后面的章节中，会详细说明各个模块的原理和作用，其中全局分析模块是 处理全局变量别名信息的过程，它和过程内分析模块的处理动作相似，具体介绍 就合并到过程内初始化别名分析中。 第三章 别名信息的表示与推导 1 7 第三章 别名信息的表示与推导 程序中收集到的别名信息集是海量的，并且随着程序复杂度的增加，别名信 息集中的数据量呈现非线性增长，而基于布尔代数的二叉决策图对于集合的处理 在时间、空间和效率上都有很大的优势，因此，本文采用二叉决策图作为别名分 析的底层数据结构来表示别名信息，对于别名信息的合并和消除操作转换为集合 的并、交和差操作。 根据关系收集模块得到的别名信息集仅是程序中语义规则所反映的部分直接 信息，而项目后续分析需要完整的信息集合，为了保证关系收集模块的独立完整 性，本文采用 d a t a l o g 语言来表述推导信息的基本过程。 本章主要详细论述用于别名信息表示的二叉决策图定义及使用的基本关系操 作，以及用于别名信息推导的 d a t a l o g基本语义和推导规则，并在此基础上给出 了别名信息表示与推导规则的详细设计。 3.1 基于二叉决策图的别名信息表示 在上一章中，本文讨论了别名信息的二叉决策图表示法相对于其它方法的优 势。基于上述讨论，别名信息可以用二叉决策图的元组集合来表示，这种集合可 以转换为变元的析取范式。本节首先说明如何利用 i f - t h e n - e l s e 操作符将表示别名 信息的析取范式构造为二叉决策树，然后介绍如何将二叉决策树化简为表示别名 信息的二叉决策图；最后给出二叉决策图的定义和操作算法。 3 . 1 . 1 二叉决策图的构造方法 在 i f - t h e n - e l s e 操作符的定义下，x y 0, y1表达式被定义为公式： x y 0, y1 = ( x y 0) ( x y 1) 式( 3 - 1 ) 在表达式 t t 0, t1中，如果 t 和 t0的值都为真或者 t 为假并且 t1为真，则整个 表达式的值才为真，其中 t 可以称为测试表达式。在这个表达式中的所有运算符 号为 i f - t h e n - e l s e 运算或者为常量 t u r e 和 f a l s e 。为了构造二叉决策树，所有变元必 须以 i f - t h e n - e l s e 的形式表现，因此布尔表达式 x 可以被看做 x 1 , 0 ，x 被看做 x 0 , 1 ，而 x y 被看做 x ( y 1 , 0 ) , ( y 0 , 1 ) 。 定义 3 . 1 i f - t h e n - e l s e 正规式（i n f ）是一个布尔表达式，并且这个表达式是由 i f - t h e n - e l s e 操作、常量 0 和 1 以及变元组成。 基于二叉决策图的别名分析研究 1 8 表达式 t 0 / x 表示把在 t 中出现的 x 替换为 0 ，则可以根据香浓展开定理推导 出下面一个公式： t = x t 1 / x , t 0 / x 式( 3 - 2 ) 通过展开操作使得一个表达式变为两个表达式的或操作，而新产生的表达式 中变元个数减少了一个，降低了表达式的复杂性。这个等式可以从任何表达式 t 产生一个 i f - t h e n - e l s e 正规式。如果 t 没有包含任何变元，则 t 的值等于 0 或者 1 ， 因此表达式 t 是一个 i n f 。否则，可以将表达式 t 中的任何一个变元 x 通过香浓展 开定理来消除。表达式 t 0 / x （简写为 t 0）和 t