基于gcc抽象语法树文本的c源程序语义分析方法研究

1、硕士学位论文基于 GCC 抽象语法树文本的 C 源程序语义分析方法研究RESEARCH ON SEMANTIC ANALYSISOF C PROGRAM BASED ON GCC ABSTRACTSYNTAX TREE TEXT封战胜2009 年 6 月国内图书分类号：TP311.5国际图书分类号：681学校代码：10213密级：公开硕士学位论文基于 GCC 抽象语法树文本的 C 源程序语义分析方法研究硕 士 研 究 生：封战胜导师：苏小红教授申 请 学 位：工学硕士学科：计算机科学与技术所 在 单 位：计算机科学与技术答 辩 日 期： 2009 年 6 月授予学位单位：哈尔滨工业大学Clas

2、sified Index: TP311.5U.D.C:681Dissertation for the Master Degree in EngineeringRESEARCH ON SEMANTIC ANALUSISOF C PROGRAM BASED ON GCC ABSTRACTSYNTAX TREE TEXTCandidate：Supervisor：Academic Degree Applied for：Speciality：Affiliation：Date of Defence：Feng ZhanshengProf.Su XiaohongMaster of EngineeringCom

3、puter Science and TechnologySchool of Computer Scinence andTechnologyJune, 2009Degree-Conferring-Institution： Harbin Institute of Technology哈尔滨工业大学工学硕士学位论文摘要本文致力于完成 C 语言源程序的系统依赖图的构造，系统依赖图是静态分析工具的基础，在逆向工程中具有重要意义。系统依赖图的构造可以归结为控制流分析和数据流分析，控制流分析主要是求取语句间的控制依赖关系，可以归结为父亲-孩子关系的求解。数据流分析主要是求取语句间的数据依赖关系，可以归结为到

4、达-定值信息的求解。本文提出了一种基于 GCC 抽象语法树文本的构造系统依赖图的新方法，首先，对 GCC 抽象语法树进行了深入的研究，统计出 GCC 抽象语法树中各个符号的含义，为后续研究奠定了基础。其次，对 GCC 抽象语法树文本进行了标准化及消除文本中与控制流分析和数据流分析无关的冗余信息。再次，用面向对象的思想来进行静态信息提取。最后，在构造系统依赖图时，本文没有采用传统构造系统依赖图的流程，而是首先建立了控制依赖图，其次在控制依赖图的基础上构建控制流图，再次在控制流图的基础上构建数据流图。同时本文给出了各个步骤的具体算法描述，其中包含了自己的算法及对以往算法的改进。为了提高数据流的精度

5、，介绍了一些提高数据流精度的方法，比如指针分析、变量别名分析等等。另外，本文在设计系统时，也对每个过程的相关信息进行了统计，为用户查询模块奠定了基础。本文最后一章给出了系统的详细设计，并对源程序进行了测试，验证了算法的可行性，通过与以往研究的对比，说明了该方法的优越性。关键词：GCC 抽象语法树；控制流分析；数据流分析；控制流图；系统依赖图I哈尔滨工业大学工学硕士学位论文AbstractIn this paper, system dependence graph on the C programming language isconstructed, which is the basis of

6、 static analysis tool and plays an important role in thereverse engineering. The construction of system dependence graph can be attributed tothe control flow analysis and data flow analysis. The control dependence relationshipamong statements is obtained by control flow analysis, which can be attrib

7、uted to obtainthe father-child relationship. The data dependence relationship among statements isobtained by data flow analysis, which can be attributed to obtain the global informationabout how a program defines, changes and uses data values.The method that how to construct the system dependence gr

8、aph based on theabstract syntax tree text is put forward. Firstly, the abstract syntax tree is studied, and themeaning of symbols in abstract syntax tree is obtained, which lays a good foundation forthe following study. Secondly, the abstract syntax tree text is standardized and theredundant informa

9、tion unrelated to the control flow analysis and data flow analysis iseliminated. Thirdly, the object-oriented thinking is introduced to extract the staticinformation. Finally, the traditional process is not followed when constructing the systemdependence graph. Control flow graph is constructed base

10、d on control dependence graphand data flow graph is constructed based on control flow graph. Also, the description ofspecific algorithm on every step is given, which includes our own algorithm and theimproved algorithm. In order to improve the accuracy of the data flow analysis, somemethods are intr

11、oduced, such as pointer analysis, alias analysis and so on. In addition, therelevant statistical information for each process is obtained, which lays a goodfoundation for the users query module.In the final chapter of this paper, the detailed design is given, and some examplesare tested to verify th

12、e feasibility of our algorithm. In addition, by contrast with theprevious studies, the result shows the superiority of this method.Keywords: GCC abstract syntax tree, control flow analysis, data flow analysis, controlflow graph, system dependence graphII哈尔滨工业大学工学硕士学位论文目录摘要 . IAbstract . II第 1 章 绪论 .

13、 11.1 课题研究的背景与意义 . 11.2 基于程序语义分析方法的静态分析工具国内外研究现状 . 21.2.1 程序缺陷检测工具国内外研究综述 . 21.2.2 程序切片工具国内外研究综述 . 41.3 课题研究的主要内容及章节安排 . 5第 2 章 课题相关的理论基础 . 72.1 GCC文本抽象语法树 . 72.1.1 GCC抽象语法树结构 . 72.1.2 GCC抽象语法树分类及常见符号含义 . 82.2 控制流图 . 82.2.1 控制流图概述 . 82.2.2 语句的控制流图描述 . 92.3 系统依赖图SDG . 122.4 面向对象系统依赖图及分层切片模型 . 132.5 标

14、准模板库STL . 162.6 本章小结 . 17第 3 章 程序静态信息提取研究 . 183.1 抽象语法树文本标准化 . 183.1.1 抽象语法树文本标准化的原因 . 183.1.2 标准化抽象语法树文本算法描述 . 183.2 消除抽象语法树文本中的冗余信息 . 183.2.1 消除AST文本中冗余信息的原因. 183.2.2 消除AST文本中冗余信息算法描述. 193.3 基于面向对象技术的源程序静态信息提取 . 203.3.1 采用面向对象技术的原因 . 203.3.2 对源程序设计语言的分类 . 213.3.3 类之间的调用关系 . 213.4 本章小结 . 21第 4 章 程序

15、系统依赖图生成方法研究 . 234.1 生成系统依赖图的总体流程 . 234.2 预处理 . 244.2.1 确定语句范围 . 244.2.2 switch语句标准化. 254.2.3 for语句标准化 . 26III哈尔滨工业大学工学硕士学位论文4.2.4 函数调用语句标准化 . 264.2.5 语句排序 . 284.3 控制依赖分析和控制依赖子图生成 . 294.3.1 控制依赖子图 . 294.3.2 跳转语句的处理 . 304.4 控制流图的生成 . 314.5 数据依赖分析和数据依赖子图生成 . 314.5.1 到达定值信息相关概念 . 314.5.2 计算语句的REF、DEF 、G

16、EN和KILL集合 . 334.5.3 计算语句的IN、OUT集合. 364.5.4 建立数据依赖边 . 374.5.5 计算过程间的数据流 . 374.5.6 指针分析 . 394.5.7 变量别名分析和数组变量分析 . 434.6 本章小结 . 43第 5 章 系统实现及测试分析 . 445.1 系统总体设计与实现 . 445.2 系统应用环境 . 475.3 系统测试与分析 . 485.3.1 源程序 1 的测试与分析 . 485.3.2 源程序 2 的测试与分析 . 505.3.3 源程序 3 的测试与分析 . 535.3.4 实验结果对比分析 . 555.4 本章小结 . 55结论

17、. 56参考文献 . 58攻读学位期间发表的学术论文 . 61哈尔滨工业大学硕士学位论文原创性声明 . 62哈尔滨工业大学硕士学位论文使用授权书 . 62致谢 . 63IV哈尔滨工业大学工学硕士学位论文第 1 章 绪论1.1 课题研究的背景与意义随着软件规模的扩大，软件的可靠性显得越来越重要，对软件进行测试是保证软件质量的重要环节，由于在软件的开发后期发现错误进行修改是早期发现错误进行修改所需成本的很多倍，因此在动态测试前对软件进行静态测试可以尽早的发现软件中的缺陷，提高产品的质量，加快开发速度，减少软件的开发成本。静态分析主要包括代码检查、静态结构分析、代码质量度量等等，而软件维护、程序分析

18、、逆向工程和转换工具几乎都依靠静态源代码分析作为基础。因此，研究促进程序理解的软件工程方法和工具就显得非常必要，逆向工程正是在这种需要下产生的软件工程方法。逆向工程着眼于分析软件并用抽象形式将其表现出来，使其便于理解。逆向工程可用于软件维护、再工程、重用以及文档化等许多用途。理解现有的软件系统，一般需要静态和动态两方面的信息。静态信息描述软件在源代码中的结构，动态信息描述程序运行期间的行为。静态和动态分析的结果是对软件组件及组件之间关系的信息描述。通过从目标软件还原设计模式可以帮助开发人员和维护人员进行程序理解，这种逆向工程方法同样适用于从高层设计信息构造软件，如正向工程。被抽取的静态模型可以

19、用于保证体系结构严格按照方案进行以及获得软件当前阶段的整个视图，而动态模型则可以用于支持调试，找出错误代码，以及理解软件当前行为。源程序静态信息提取需要对源程序进行编译，但是不需要运行。需要经过词法分析、语法分析的过程，这就要要有针对源程序语言的词法分析器、语法分析器和相应的输出信息接口。对源程序进行静态信息提取主要有以下两种方式：(1)直接编写针对源程序语言的词法分析器、语法分析器，对源程序进行静态分析，得到源程序的静态信息；(2)利用开源编译器GCC(GNU Compiler Collection)或者词法分析器LEX(Lexical Compiler)和语法分析器YACC(Yet Ano

20、ther Compiler Compiler)或者语言识别工具ANTLR(Another Tool for Language Recognition)1达到对源程序进行信息提取的目的。对于第一种方式，这类静态分析器使用语法制导分析源代码，特点是语法识别准确，提取的源代码信息比较准确，编写静态信息输出接口也有利于实现交互，但是由于语言描述比较复杂，实现难度比较大。对于第二种方式，YACC生成的编译器主要是用 C语言写成的语法分析器 (Parser)，需要与词法分析器 LEX一起使-1-哈尔滨工业大学工学硕士学位论文用，再把两部分产生出来的 C程序一并编译。语言识别工具ANTLR可以接受文法语言描

21、述，并产生识别这些语言的语句的程序，作为翻译程序的一部分，可以使用简单的操作符和动作来参数化文法，告诉它如何去创建抽象语法树和如何产生输出，但是这种工具主要是针对JAVA,C+,C#和Python语言的。如果利用GCC编译器的话，可以修改GCC编译器前端的源码，添加静态信息输出接口，以便输出源程序的静态信息；或者利用其产生的抽象语法树AST(Abstract Syntax Tree)层或者寄存器存储转换语言RTL(Register Transfer Language)中间文件，提取源程序的静态信息。然而GCC源代码规模庞大，结构关系复杂，因此直接修改GCC前端的源码不太现实。另外，由于RTL文

22、件中含有大量编译器后端的信息，而这部分信息对源程序结构分析所需提取的信息来说含有大量冗余的信息，并且程序间的结构不清晰。所以，本文给出一种基于GCC的AST中间文件提取源程序静态信息的方法。目前解析GCC产生的抽象语法树文本是一个相对比较新的研究课题。国内外对GCC抽象语法树解析研究比较晚，最早的文献是2002年的James F. Power的文章2，AST文本解析方法可分为两种：一是通过编译的方法构造分析器对抽象语法树文本进行解析3，在分析抽象语法树结构的基础上，把文本抽象语法树当作一种特殊的语言来识别，构造相应的词法规则和语法规则，使用flex和bison工具4生成的解析器能够有效地对抽象

23、语法树进行解析；二是基于XML或是GXL的解析方法5-8，这种解析方法相对多一些，因为XML是一种很通用的信息格式，现有的对XML文档进行解析的工具很多也非常成熟。将文本抽象语法树转换为XML文档，再由XML文档解析器构造出具有某种存储结构的抽象语法树。1.2 基于程序语义分析方法的静态分析工具国内外研究现状1.2.1 程序缺陷检测工具国内外研究综述静态分析工具根据软件的结构、内容或文档来评价软件系统，而不需要执行程序。因此可以较早地发现程序代码中的缺陷，这使得后面的软件开发阶段可以着重分析复杂功能以及算法的错误。静态分析工具可以在软件工程人员审查、测试之前查找软件中的缺陷,也可结合到整个软件

24、开发过程中。静态分析工具可以自动识别特定的软件缺陷，通常采用的方法是扫描并分析程序的源代码来查找代码中特定模式集合。其中最大的优点在于：它们不必执行目标程序就可以推论出可应用于所有可能执行路径上的结果。按照采用的分析技术的不同可以分为四类：第一类主要是基于字符串匹配技术 它把注释、字符、声明以及函数调用都当作字符流进行匹配，不能理解所扫描的文件，准确率很低；第二类静态分析工具采用了基本的词法分析方法 它们将源文件预处理为Token流，然后将-2-哈尔滨工业大学工学硕士学位论文Token流与库中的缺陷结构进行匹配。尽管词法分析工具有了很大的进步,但它们仍然没有考虑源代码的语义，不能理解程序的执行

25、行为，因此误检率仍然很高；第三类静态分析工具采用了程序语义分析方法。这些工具通过分析程序的控制流和数据流，以及函数调用关系等考虑程序的基本语义。这些工具大多专用于检查特定的缺陷；第四类静态分析工具将数据挖掘技术与程序分析相结合。不需要预先定义模式或规则,而用数据挖掘方法挖掘编程模式。例如CPMiner9使用数据挖掘技术识别大型软件中的拷贝- 粘贴代码,并检测与拷贝- 粘贴代码相关的软件缺陷；PRMiner10使用频繁项集合挖掘来抽取软件代码中隐含的编程规则。下面重点介绍一下基于程序语义分析方法的静态分析工具：(1)BOON11 应用整数范围分析,确定C程序中是否有数组越界。尽管它能检测到很多词

26、法工具检测不到的缺陷,但没有考虑语句顺序和指针别名,也不能对过程间依赖进行建模。(2)CQual12 使用类型验证检查类型标识符,可以检查C程序中字符串使用缺陷和锁缺陷,它需要程序员对一些变量进行注释。(3)xg+13 使用模板驱动的编译器扩展来查找Linux与OpenBSD内核的缺陷,可以检测没有释放动态分配的内存、内核死锁等缺陷。(4)MOPS14 采用模型检查方法,查找与安全属性相关的缺陷,如优先级管理错误、文件访问竞争等。(5)Splint15 用程序员提供的注释辅助程序分析。可以查找使用未初始化的变量、数组下标越界等缺陷。(6)FindBug16,17 使用缺陷模式检查器,检查Jav

27、a程序中的缺陷,如空指针异常、死锁、线程问题等。(7)PREfix18 基于程序调用图进行分析,通过分析程序中很多路径,跟踪变量和内存状态,查找C与C+程序中常见的动态错误。PREfast是PRE2fix工具的一个”fast”版本,有些PREfast的分析基于C/C+程序的抽象模式匹配来查找简单的编程错误。PREfast/PREfix可以用于检测未初始化的变量、空指针脱引用、使用未初始化的内存、重复释放资源等缺陷。(8)SLAM19 将程序抽象成布尔程序,并研究它的可达状态。如果布尔程序到达了一个错误状态。则可能是一个不可行的路径,在这种情况下,重新分析布尔程序。SLAM被用于查找Window

28、s驱动程序中缺陷。(9)Flexelint (www. gimpel. com /html/products.htm) 检查C/C+源代码中的错误、不一致性、不可移植的常量以及冗余代码等。(10)Reasonings Illuma (www. reasoning. com) 可以查找C/C+应用中的缺陷。代-3-哈尔滨工业大学工学硕士学位论文码发送到Rea2soning，Reasoning执行静态分析,消除虚假报警并生成报告。Illuma识别可导致应用程序崩溃的可靠性缺陷,包括空指针脱引用、数组访问越界、内存泄露、错误的再分配以及未初始化的变量。(11)Klocwork () 有 两 个 静

29、态 分 析 工 具 ， 即 inForce 与GateKeeper。inForce分析工具执行源代码静态分析来识别潜在的缺陷和安全漏洞。Gate2Keeper分析工具分析了源代码体系结构的优点与缺点并评价代码质量、缺陷和维护开销。缺陷类型包括模块间的关系、代码聚合、高风险的代码文件与函数的逻辑错误等。(12)CodeSurfer20 计算很多种程序的语义表示,如调用图和依赖图,来辅助软件审查。整个程序的指针分析确保了指针别名分析的表示是准确的。在依赖图上进行查询使得审查者能够回答程序的语义问题。通过对程序进行模型检查,可以查找软件缺陷。但它的缺点是创建依赖图的开销太大,不适合应用于大型程序。(

30、13)PGRelief21 是南京大学与日本富士通公司合作开发的自动静态分析系统。通过静态分析用C/C+语言编写的源程序及头文件,寻找程序的潜在缺陷,并统计程序的复杂度和规模。分析的缺陷包括潜在的逻辑错误(信赖性缺陷)、设计艰涩以至妨碍程序理解的缺陷(维护性缺陷)、因为编译器的不同而可能有不同解释的缺陷(移植性缺陷)、有可能增加程序目标代码规模和执行步骤的缺陷(效率性缺陷)等。对程序语义分析方法进行研究的还有我国的合肥工业大学22、西安电子科技大学23-25等。1.2.2 程序切片工具国内外研究综述程序切片是由M.Weiser 1979年在他的博士论文26中优先建立起来的一种程序分析技术，19

31、84年，M.Weiser在IEEE Transations on Software Engineering上进一步阐述了程序切片技术的思想27。程序切片技术在软件分析、理解、调试、测试、度量、软件质量保证、逆向工程等许多方面有着广泛的应用。在软件调试过程中，定位程序中存在的错误是一项困难的工作，程序切片可以帮助程序员很容易地进行错误定位。软件维护是软件生命周期的重要组成部分，其个占整个系统费用的一半及以上。软件维护的主要挑战来自对现实对现有系统的理解和确保修改系统不会引发新的错误，分解切片捕获与程序中某个变量在所有计算位置的值的相关的程序信息，将对程序的修改引起的影响控制在一定的范围内。当软件

32、系统修改后，为了保证系统的正确性以及修改不会带来副作用，需要对其进行重新测试，即回归测试。只有那些受影响的代码需要重新测试，通过程序切片技术可以避免完全重新测试。实际上，程序切片的应用非常广泛，在软件开发的各个阶段都可以发挥程序切片的巨大作-4-哈尔滨工业大学工学硕士学位论文用。在程序分析中引入基于系统依赖图和图形可达性的程序切片方法，可以降低程序分析的复杂度。控制依赖信息统计谓词语句(条件语句和循环语句)对程序行为的影响，数据依赖信息统计数据交互行为对程序行为的影响。程序切片就是使用SDG的控制依赖信息和数据依赖信息来搜集在语义上影响一条语句的所有语句的集合。目前，实用的程序切片工具和环境很

33、多，按照切片对象的程序设计语言的不同可以分为以下几类：(1)支持C语言的PST Wisconsion程序切片工具Version1.1是一个支持对C程序操作操作的软件系统。它包括后向切片、前向切片和消片三种功能，它们能帮助用户获得对一个程序正在做什么和如何做的理解。ChopShop是由Carnegie Mellon大学的计算机科学学院最初开发的一种逆向工程工具，可以用来帮助程序员理解不熟悉的C代码，它接受完全的ANSI，以文本和图形两种形式产生程序切片，并进行化名分析、处理所有的语言特性，它是第一个为过程提供数据抽象机制的程序切片工具。Chinsu是Florida大学计算机和信息科学系开发，受到

34、软件工程研究中心(SERC)基金资助的一个集成了许多工具的程序切片环境，可以在软件工程的许多活动中，主要是维护活动过程中期辅助作用。Unravel是一个原型程序切片工具，可以用来使用程序切片静态的估计ANSI C源代码。(2)支持Ada语言的PST PSS/Ada系统是由杨洪等人设计的一个Ada程序的静态切片生成原型系统，它是一个Ada软件测试、排错、分析、理解和维护工具，在Ada程序的并行性检查、波动性分析、复杂性度量等方面也提供一定范围的支持。(3)支持Java语言的PST Indus是美国勘萨州州立大学的V.P.Ranganath小组开发一个比较完整的Java程序切片工具。(4)其他PS

35、T CodeSurfer是以一种新的方式来分析、理解和浏览源代码，它是一个具有突破性的软件开发和维护工具，工程师用来浏览和理解源代码中详细的依赖关系。它提供了一种相对比较便利的访问程序深层结构的方法，即通过全局程序分析发现语义特性和关系。1.3 课题研究的主要内容及章节安排论文中主要涉及到的理论方面的研究有：(1)分析源程序调用GCC编译器生成的抽象语法树文本的结构。(2)消除抽象语法树文本中的有助于编译的细节信息，提取出与源程序结构相关的信息。(3)如何结合面向对象思想把程序设计语言正确分类，涵盖程序设计语言中的所-5-哈尔滨工业大学工学硕士学位论文有语句，表达式及变量，保证信息提取的完整性

36、。(4)如何建立标准的控制依赖图，正确的表示语句之间的控制依赖关系。(5)如何建立标准的数据流图，正确的表示语句之间的数据依赖关系。(6)如何保证源程序结构信息输出的规范性。(7)是否能在系统依赖图的基础上扩展来表示C+面向对象语言。(8)该研究的主要应用。本文共分为5个部分：第1章主要介绍了课题研究背景和意义，介绍了基于GCC抽象语法树文本解析源程序的国内外现状，并介绍了基于程序语义分析方法的程序缺陷检测工具和程序切片工具在国内外的研究现状。第2章主要介绍了和课题相关的一些理论基础，GCC抽象语法树结构、控制流图等等，并延伸了SDG，介绍了面向对象的系统依赖图OOSDG。第3章主要介绍了基于

37、GCC抽象语法树文本的源程序静态信息提取方法。第4章主要介绍了基于GCC抽象语法树解析的程序系统依赖图生成方法。第5章主要介绍了系统的详细设计和测试结果分析。-6-哈尔滨工业大学工学硕士学位论文第 2 章 课题相关的理论基础2.1 GCC 文本抽象语法树2.1.1 GCC 抽象语法树结构GCC编译系统是由美国自由软件基金会(Free Software Foundation)开发，可以编译多种程序设计语言，支持多平台编译的编译程序集合，是Linux/Unix下最稳定和成熟的编译器。GCC编译系统主要由三部分组成：与程序设计语言相关的前端、与程序设计语言无关的后端和与机器相关的机器描述部分。为了支

38、持多平台编译，GCC前端需要一种中间表示，能够向上支撑多种程序设计语言到中间代码的映射，向下支持跨平台代码转换并且适合在多种平台下进行优化。为此GCC编译系统使用两个层次的中间表示，分别为抽象语法树AST层和寄存器转移语言RTL层。抽象语法树作为一种通用的中间表示，不仅包含各种语言共有的语法结构，某些特定类型的树结点还可以表示一些语言特有的语法结构。抽象语法树易于转换成寄存器转移语言，而寄存器转移语言适合在不同平台下进行优化，这使得GCC的两层中间表示具有良好的通用性。AST是程序的一种中间表示形式。GCC编译系统以程序的过程为单位生成抽象语法树，抽象语法树与过程一一对应。AST能够包含整个编译单元的完整表示，比较直观的表示出源程序