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

《基于gcc抽象语法树文本的c源程序语义分析方法研究》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

硕士学位论文基于GCC抽象语法树文本的C源程序语义分析方法研究RESEARCHONSEMANTICANALYSISOFCPROGRAMBASEDONGCCABSTRACTSYNTAXTREETEXT封战胜2009年6月 国内图书分类号：TP311.5国际图书分类号：681学校代码：10213密级：公开硕士学位论文基于GCC抽象语法树文本的C源程序语义分析方法研究硕士研究生：封战胜导师：苏小红教授申请学位：工学硕士学科：计算机科学与技术所在单位：计算机科学与技术答辩日期：2009年6月授予学位单位：哈尔滨工业大学 ClassifiedIndex:TP311.5U.D.C:681DissertationfortheMasterDegreeinEngineeringRESEARCHONSEMANTICANALUSISOFCPROGRAMBASEDONGCCABSTRACTSYNTAXTREETEXTCandidate：Supervisor：AcademicDegreeAppliedfor：Speciality：Affiliation：DateofDefence：FengZhanshengProf.SuXiaohongMasterofEngineeringComputerScienceandTechnologySchoolofComputerScinenceandTechnologyJune,2009Degree-Conferring-Institution：HarbinInstituteofTechnology 哈尔滨工业大学工学硕士学位论文摘要本文致力于完成C语言源程序的系统依赖图的构造，系统依赖图是静态分析工具的基础，在逆向工程中具有重要意义。系统依赖图的构造可以归结为控制流分析和数据流分析，控制流分析主要是求取语句间的控制依赖关系，可以归结为父亲-孩子关系的求解。数据流分析主要是求取语句间的数据依赖关系，可以归结为到达-定值信息的求解。本文提出了一种基于GCC抽象语法树文本的构造系统依赖图的新方法，首先，对GCC抽象语法树进行了深入的研究，统计出GCC抽象语法树中各个符号的含义，为后续研究奠定了基础。其次，对GCC抽象语法树文本进行了标准化及消除文本中与控制流分析和数据流分析无关的冗余信息。再次，用面向对象的思想来进行静态信息提取。最后，在构造系统依赖图时，本文没有采用传统构造系统依赖图的流程，而是首先建立了控制依赖图，其次在控制依赖图的基础上构建控制流图，再次在控制流图的基础上构建数据流图。同时本文给出了各个步骤的具体算法描述，其中包含了自己的算法及对以往算法的改进。为了提高数据流的精度，介绍了一些提高数据流精度的方法，比如指针分析、变量别名分析等等。另外，本文在设计系统时，也对每个过程的相关信息进行了统计，为用户查询模块奠定了基础。本文最后一章给出了系统的详细设计，并对源程序进行了测试，验证了算法的可行性，通过与以往研究的对比，说明了该方法的优越性。关键词：GCC抽象语法树；控制流分析；数据流分析；控制流图；系统依赖图I 哈尔滨工业大学工学硕士学位论文AbstractInthispaper,systemdependencegraphontheCprogramminglanguageisconstructed,whichisthebasisofstaticanalysistoolandplaysanimportantroleinthereverseengineering.Theconstructionofsystemdependencegraphcanbeattributedtothecontrolflowanalysisanddataflowanalysis.Thecontroldependencerelationshipamongstatementsisobtainedbycontrolflowanalysis,whichcanbeattributedtoobtainthefather-childrelationship.Thedatadependencerelationshipamongstatementsisobtainedbydataflowanalysis,whichcanbeattributedtoobtaintheglobalinformationabouthowaprogramdefines,changesandusesdatavalues.Themethodthathowtoconstructthesystemdependencegraphbasedontheabstractsyntaxtreetextisputforward.Firstly,theabstractsyntaxtreeisstudied,andthemeaningofsymbolsinabstractsyntaxtreeisobtained,whichlaysagoodfoundationforthefollowingstudy.Secondly,theabstractsyntaxtreetextisstandardizedandtheredundantinformationunrelatedtothecontrolflowanalysisanddataflowanalysisiseliminated.Thirdly,theobject-orientedthinkingisintroducedtoextractthestaticinformation.Finally,thetraditionalprocessisnotfollowedwhenconstructingthesystemdependencegraph.Controlflowgraphisconstructedbasedoncontroldependencegraphanddataflowgraphisconstructedbasedoncontrolflowgraph.Also,thedescriptionofspecificalgorithmoneverystepisgiven,whichincludesourownalgorithmandtheimprovedalgorithm.Inordertoimprovetheaccuracyofthedataflowanalysis,somemethodsareintroduced,suchaspointeranalysis,aliasanalysisandsoon.Inaddition,therelevantstatisticalinformationforeachprocessisobtained,whichlaysagoodfoundationfortheuser’squerymodule.Inthefinalchapterofthispaper,thedetaileddesignisgiven,andsomeexamplesaretestedtoverifythefeasibilityofouralgorithm.Inaddition,bycontrastwiththepreviousstudies,theresultshowsthesuperiorityofthismethod.Keywords:GCCabstractsyntaxtree,controlflowanalysis,dataflowanalysis,controlflowgraph,systemdependencegraphII 哈尔滨工业大学工学硕士学位论文目录摘要.......................................................................................................................................................IAbstract................................................................................................................................................II第1章绪论......................................................................................................................11.1课题研究的背景与意义......................................................................................11.2基于程序语义分析方法的静态分析工具国内外研究现状..............................21.2.1程序缺陷检测工具国内外研究综述.........................................................21.2.2程序切片工具国内外研究综述.................................................................41.3课题研究的主要内容及章节安排......................................................................5第2章课题相关的理论基础..........................................................................................72.1GCC文本抽象语法树..........................................................................................72.1.1GCC抽象语法树结构................................................................................72.1.2GCC抽象语法树分类及常见符号含义....................................................82.2控制流图..............................................................................................................82.2.1控制流图概述............................................................................................82.2.2语句的控制流图描述................................................................................92.3系统依赖图SDG................................................................................................122.4面向对象系统依赖图及分层切片模型............................................................132.5标准模板库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章程序系统依赖图生成方法研究........................................................................234.1生成系统依赖图的总体流程............................................................................234.2预处理.................................................................................................................244.2.1确定语句范围..........................................................................................244.2.2switch语句标准化....................................................................................254.2.3for语句标准化.........................................................................................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、GEN和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结论..................................................................................................................................56参考文献..........................................................................................................................58攻读学位期间发表的学术论文......................................................................................61哈尔滨工业大学硕士学位论文原创性声明..................................................................62哈尔滨工业大学硕士学位论文使用授权书..................................................................62致谢..................................................................................................................................63IV 哈尔滨工业大学工学硕士学位论文第1章绪论1.1课题研究的背景与意义随着软件规模的扩大，软件的可靠性显得越来越重要，对软件进行测试是保证软件质量的重要环节，由于在软件的开发后期发现错误进行修改是早期发现错误进行修改所需成本的很多倍，因此在动态测试前对软件进行静态测试可以尽早的发现软件中的缺陷，提高产品的质量，加快开发速度，减少软件的开发成本。静态分析主要包括代码检查、静态结构分析、代码质量度量等等，而软件维护、程序分析、逆向工程和转换工具几乎都依靠静态源代码分析作为基础。因此，研究促进程序理解的软件工程方法和工具就显得非常必要，逆向工程正是在这种需要下产生的软件工程方法。逆向工程着眼于分析软件并用抽象形式将其表现出来，使其便于理解。逆向工程可用于软件维护、再工程、重用以及文档化等许多用途。理解现有的软件系统，一般需要静态和动态两方面的信息。静态信息描述软件在源代码中的结构，动态信息描述程序运行期间的行为。静态和动态分析的结果是对软件组件及组件之间关系的信息描述。通过从目标软件还原设计模式可以帮助开发人员和维护人员进行程序理解，这种逆向工程方法同样适用于从高层设计信息构造软件，如正向工程。被抽取的静态模型可以用于保证体系结构严格按照方案进行以及获得软件当前阶段的整个视图，而动态模型则可以用于支持调试，找出错误代码，以及理解软件当前行为。源程序静态信息提取需要对源程序进行编译，但是不需要运行。需要经过词法分析、语法分析的过程，这就要要有针对源程序语言的词法分析器、语法分析器和相应的输出信息接口。对源程序进行静态信息提取主要有以下两种方式：(1)直接编写针对源程序语言的词法分析器、语法分析器，对源程序进行静态分析，得到源程序的静态信息；(2)利用开源编译器GCC(GNUCompilerCollection)或者词法分析器LEX(LexicalCompiler)和语法分析器YACC(YetAnotherCompilerCompiler)或者语言识别工具ANTLR(AnotherToolforLanguageRecognition)[1]达到对源程序进行信息提取的目的。对于第一种方式，这类静态分析器使用语法制导分析源代码，特点是语法识别准确，提取的源代码信息比较准确，编写静态信息输出接口也有利于实现交互，但是由于语言描述比较复杂，实现难度比较大。对于第二种方式，YACC生成的编译器主要是用C语言写成的语法分析器(Parser)，需要与词法分析器LEX一起使-1- 哈尔滨工业大学工学硕士学位论文用，再把两部分产生出来的C程序一并编译。语言识别工具ANTLR可以接受文法语言描述，并产生识别这些语言的语句的程序，作为翻译程序的一部分，可以使用简单的操作符和动作来参数化文法，告诉它如何去创建抽象语法树和如何产生输出，但是这种工具主要是针对JAVA,C++,C#和Python语言的。如果利用GCC编译器的话，可以修改GCC编译器前端的源码，添加静态信息输出接口，以便输出源程序的静态信息；或者利用其产生的抽象语法树AST(AbstractSyntaxTree)层或者寄存器存储转换语言RTL(RegisterTransferLanguage)中间文件，提取源程序的静态信息。然而GCC源代码规模庞大，结构关系复杂，因此直接修改GCC前端的源码不太现实。另外，由于RTL文件中含有大量编译器后端的信息，而这部分信息对源程序结构分析所需提取的信息来说含有大量冗余的信息，并且程序间的结构不清晰。所以，本文给出一种基于GCC的AST中间文件提取源程序静态信息的方法。目前解析GCC产生的抽象语法树文本是一个相对比较新的研究课题。国内外对GCC抽象语法树解析研究比较晚，最早的文献是2002年的JamesF.Power的文章[2]，AST文本解析方法可分为两种：一是通过编译的方法构造分析器对抽象语法树文本进行解析[3]，在分析抽象语法树结构的基础上，把文本抽象语法树当作一种特殊的语言来识别，构造相应的词法规则和语法规则，使用flex和bison工具[4]生成的解析器能够有效地对抽象语法树进行解析；二是基于XML或是GXL的解析方法[5-8]，这种解析方法相对多一些，因为XML是一种很通用的信息格式，现有的对XML文档进行解析的工具很多也非常成熟。将文本抽象语法树转换为XML文档，再由XML文档解析器构造出具有某种存储结构的抽象语法树。1.2基于程序语义分析方法的静态分析工具国内外研究现状1.2.1程序缺陷检测工具国内外研究综述静态分析工具根据软件的结构、内容或文档来评价软件系统，而不需要执行程序。因此可以较早地发现程序代码中的缺陷，这使得后面的软件开发阶段可以着重分析复杂功能以及算法的错误。静态分析工具可以在软件工程人员审查、测试之前查找软件中的缺陷,也可结合到整个软件开发过程中。静态分析工具可以自动识别特定的软件缺陷，通常采用的方法是扫描并分析程序的源代码来查找代码中特定模式集合。其中最大的优点在于：它们不必执行目标程序就可以推论出可应用于所有可能执行路径上的结果。按照采用的分析技术的不同可以分为四类：第一类主要是基于字符串匹配技术它把注释、字符、声明以及函数调用都当作字符流进行匹配，不能理解所扫描的文件，准确率很低；第二类静态分析工具采用了基本的词法分析方法它们将源文件预处理为Token流，然后将-2- 哈尔滨工业大学工学硕士学位论文Token流与库中的缺陷结构进行匹配。尽管词法分析工具有了很大的进步,但它们仍然没有考虑源代码的语义，不能理解程序的执行行为，因此误检率仍然很高；第三类静态分析工具采用了程序语义分析方法。这些工具通过分析程序的控制流和数据流，以及函数调用关系等考虑程序的基本语义。这些工具大多专用于检查特定的缺陷；第四类静态分析工具将数据挖掘技术与程序分析相结合。不需要预先定义模式或规则,而用数据挖掘方法挖掘编程模式。例如CP–Miner[9]使用数据挖掘技术识别大型软件中的拷贝-粘贴代码,并检测与拷贝-粘贴代码相关的软件缺陷；PR–Miner[10]使用频繁项集合挖掘来抽取软件代码中隐含的编程规则。下面重点介绍一下基于程序语义分析方法的静态分析工具：(1)BOON[11]应用整数范围分析,确定C程序中是否有数组越界。尽管它能检测到很多词法工具检测不到的缺陷,但没有考虑语句顺序和指针别名,也不能对过程间依赖进行建模。(2)CQual[12]使用类型验证检查类型标识符,可以检查C程序中字符串使用缺陷和锁缺陷,它需要程序员对一些变量进行注释。(3)xg++[13]使用模板驱动的编译器扩展来查找Linux与OpenBSD内核的缺陷,可以检测没有释放动态分配的内存、内核死锁等缺陷。(4)MOPS[14]采用模型检查方法,查找与安全属性相关的缺陷,如优先级管理错误、文件访问竞争等。(5)Splint[15]用程序员提供的注释辅助程序分析。可以查找使用未初始化的变量、数组下标越界等缺陷。(6)FindBug[16,17]使用缺陷模式检查器,检查Java程序中的缺陷,如空指针异常、死锁、线程问题等。(7)PREfix[18]基于程序调用图进行分析,通过分析程序中很多路径,跟踪变量和内存状态,查找C与C++程序中常见的动态错误。PREfast是PRE2fix工具的一个”fast”版本,有些PREfast的分析基于C/C++程序的抽象模式匹配来查找简单的编程错误。PREfast/PREfix可以用于检测未初始化的变量、空指针脱引用、使用未初始化的内存、重复释放资源等缺陷。(8)SLAM[19]将程序抽象成布尔程序,并研究它的可达状态。如果布尔程序到达了一个错误状态。则可能是一个不可行的路径,在这种情况下,重新分析布尔程序。SLAM被用于查找Windows驱动程序中缺陷。(9)Flexelint(www.gimpel.com/html/products.htm)检查C/C++源代码中的错误、不一致性、不可移植的常量以及冗余代码等。(10)Reasoning’sIlluma(www.reasoning.com)可以查找C/C++应用中的缺陷。代-3- 哈尔滨工业大学工学硕士学位论文码发送到Rea2soning，Reasoning执行静态分析,消除虚假报警并生成报告。Illuma识别可导致应用程序崩溃的可靠性缺陷,包括空指针脱引用、数组访问越界、内存泄露、错误的再分配以及未初始化的变量。(11)Klocwork(www.klocwork.com)有两个静态分析工具，即inForce与GateKeeper。inForce分析工具执行源代码静态分析来识别潜在的缺陷和安全漏洞。Gate2Keeper分析工具分析了源代码体系结构的优点与缺点并评价代码质量、缺陷和维护开销。缺陷类型包括模块间的关系、代码聚合、高风险的代码文件与函数的逻辑错误等。(12)CodeSurfer[20]计算很多种程序的语义表示,如调用图和依赖图,来辅助软件审查。整个程序的指针分析确保了指针别名分析的表示是准确的。在依赖图上进行查询使得审查者能够回答程序的语义问题。通过对程序进行模型检查,可以查找软件缺陷。但它的缺点是创建依赖图的开销太大,不适合应用于大型程序。(13)PG–Relief[21]是南京大学与日本富士通公司合作开发的自动静态分析系统。通过静态分析用C/C++语言编写的源程序及头文件,寻找程序的潜在缺陷,并统计程序的复杂度和规模。分析的缺陷包括潜在的逻辑错误(信赖性缺陷)、设计艰涩以至妨碍程序理解的缺陷(维护性缺陷)、因为编译器的不同而可能有不同解释的缺陷(移植性缺陷)、有可能增加程序目标代码规模和执行步骤的缺陷(效率性缺陷)等。对程序语义分析方法进行研究的还有我国的合肥工业大学[22]、西安电子科技大学[23-25]等。1.2.2程序切片工具国内外研究综述程序切片是由M.Weiser1979年在他的博士论文[26]中优先建立起来的一种程序分析技术，1984年，M.Weiser在IEEETransationsonSoftwareEngineering上进一步阐述了程序切片技术的思想[27]。程序切片技术在软件分析、理解、调试、测试、度量、软件质量保证、逆向工程等许多方面有着广泛的应用。在软件调试过程中，定位程序中存在的错误是一项困难的工作，程序切片可以帮助程序员很容易地进行错误定位。软件维护是软件生命周期的重要组成部分，其个占整个系统费用的一半及以上。软件维护的主要挑战来自对现实对现有系统的理解和确保修改系统不会引发新的错误，分解切片捕获与程序中某个变量在所有计算位置的值的相关的程序信息，将对程序的修改引起的影响控制在一定的范围内。当软件系统修改后，为了保证系统的正确性以及修改不会带来副作用，需要对其进行重新测试，即回归测试。只有那些受影响的代码需要重新测试，通过程序切片技术可以避免完全重新测试。实际上，程序切片的应用非常广泛，在软件开发的各个阶段都可以发挥程序切片的巨大作-4- 哈尔滨工业大学工学硕士学位论文用。在程序分析中引入基于系统依赖图和图形可达性的程序切片方法，可以降低程序分析的复杂度。控制依赖信息统计谓词语句(条件语句和循环语句)对程序行为的影响，数据依赖信息统计数据交互行为对程序行为的影响。程序切片就是使用SDG的控制依赖信息和数据依赖信息来搜集在语义上影响一条语句的所有语句的集合。目前，实用的程序切片工具和环境很多，按照切片对象的程序设计语言的不同可以分为以下几类：(1)支持C语言的PSTWisconsion程序切片工具Version1.1是一个支持对C程序操作操作的软件系统。它包括后向切片、前向切片和消片三种功能，它们能帮助用户获得对一个程序正在做什么和如何做的理解。ChopShop是由CarnegieMellon大学的计算机科学学院最初开发的一种逆向工程工具，可以用来帮助程序员理解不熟悉的C代码，它接受完全的ANSI，以文本和图形两种形式产生程序切片，并进行化名分析、处理所有的语言特性，它是第一个为过程提供数据抽象机制的程序切片工具。Chinsu是Florida大学计算机和信息科学系开发，受到软件工程研究中心(SERC)基金资助的一个集成了许多工具的程序切片环境，可以在软件工程的许多活动中，主要是维护活动过程中期辅助作用。Unravel是一个原型程序切片工具，可以用来使用程序切片静态的估计ANSIC源代码。(2)支持Ada语言的PSTPSS/Ada系统是由杨洪等人设计的一个Ada程序的静态切片生成原型系统，它是一个Ada软件测试、排错、分析、理解和维护工具，在Ada程序的并行性检查、波动性分析、复杂性度量等方面也提供一定范围的支持。(3)支持Java语言的PSTIndus是美国勘萨州州立大学的V.P.Ranganath小组开发一个比较完整的Java程序切片工具。(4)其他PSTCodeSurfer是以一种新的方式来分析、理解和浏览源代码，它是一个具有突破性的软件开发和维护工具，工程师用来浏览和理解源代码中详细的依赖关系。它提供了一种相对比较便利的访问程序深层结构的方法，即通过全局程序分析发现语义特性和关系。1.3课题研究的主要内容及章节安排论文中主要涉及到的理论方面的研究有：(1)分析源程序调用GCC编译器生成的抽象语法树文本的结构。(2)消除抽象语法树文本中的有助于编译的细节信息，提取出与源程序结构相关的信息。(3)如何结合面向对象思想把程序设计语言正确分类，涵盖程序设计语言中的所-5- 哈尔滨工业大学工学硕士学位论文有语句，表达式及变量，保证信息提取的完整性。(4)如何建立标准的控制依赖图，正确的表示语句之间的控制依赖关系。(5)如何建立标准的数据流图，正确的表示语句之间的数据依赖关系。(6)如何保证源程序结构信息输出的规范性。(7)是否能在系统依赖图的基础上扩展来表示C++面向对象语言。(8)该研究的主要应用。本文共分为5个部分：第1章主要介绍了课题研究背景和意义，介绍了基于GCC抽象语法树文本解析源程序的国内外现状，并介绍了基于程序语义分析方法的程序缺陷检测工具和程序切片工具在国内外的研究现状。第2章主要介绍了和课题相关的一些理论基础，GCC抽象语法树结构、控制流图等等，并延伸了SDG，介绍了面向对象的系统依赖图OOSDG。第3章主要介绍了基于GCC抽象语法树文本的源程序静态信息提取方法。第4章主要介绍了基于GCC抽象语法树解析的程序系统依赖图生成方法。第5章主要介绍了系统的详细设计和测试结果分析。-6- 哈尔滨工业大学工学硕士学位论文第2章课题相关的理论基础2.1GCC文本抽象语法树2.1.1GCC抽象语法树结构GCC编译系统是由美国自由软件基金会(FreeSoftwareFoundation)开发，可以编译多种程序设计语言，支持多平台编译的编译程序集合，是Linux/Unix下最稳定和成熟的编译器。GCC编译系统主要由三部分组成：与程序设计语言相关的前端、与程序设计语言无关的后端和与机器相关的机器描述部分。为了支持多平台编译，GCC前端需要一种中间表示，能够向上支撑多种程序设计语言到中间代码的映射，向下支持跨平台代码转换并且适合在多种平台下进行优化。为此GCC编译系统使用两个层次的中间表示，分别为抽象语法树AST层和寄存器转移语言RTL层。抽象语法树作为一种通用的中间表示，不仅包含各种语言共有的语法结构，某些特定类型的树结点还可以表示一些语言特有的语法结构。抽象语法树易于转换成寄存器转移语言，而寄存器转移语言适合在不同平台下进行优化，这使得GCC的两层中间表示具有良好的通用性。AST是程序的一种中间表示形式。GCC编译系统以程序的过程为单位生成抽象语法树，抽象语法树与过程一一对应。AST能够包含整个编译单元的完整表示，比较直观的表示出源程序的语法结构，并含有源程序结构显示所需要的全部静态信息。在抽象语法树中，以”::Function”开始的行代表该语法树的开始，该行下面是抽象语法树的所有结点列表。每个结点的列表如：@3function_declname@4type@5srcpex8.c:19chan@6Cexternbody@7其中@3称作结点标号，用符号@和阿拉伯数字表示，它是抽象语法树上区分该结点的唯一标志，也是访问该结点的索引。其后是结点标识符IDENT和结点标记的序列TAGLIST。结点标识符是该结点的名称，代表了该结点的含义，@3结点的结点标识符为function_decl，其余部分为结点标记的列表，每个结点标记形如：name@4。结点标记的列表记录了该结点连接到其他结点的所有分支，每个结点标记对应了一个分支。结点标记有标记标签TAGLABEL和标记值TAGVALUE组成，标记标签是该分支的名称，标记值是该分支连接的目标，标记值可以为空。@3的第一个结点标记是name@4,name为标记标签，@4为标记值，代表该结点的第一个分支是name分支，其连-7- 哈尔滨工业大学工学硕士学位论文接到目标为@4的结点。2.1.2GCC抽象语法树分类及常见符号含义根据GCC抽象语法树结点所代表的对象类型的不同，以C程序产生的AST为例，主要分为以下6类：(1)常量结点：后缀往往是_cst；(2)类型结点：后缀往往是_type；(3)声明结点：后缀往往是_decl；(4)函数结点：GCC抽象语法树中的function_decl类型结点与之对应；(5)语句结点：后缀往往是_stmt；(6)表达式结点：后缀往往是_expr。2.2控制流图2.2.1控制流图概述控制流图是一个有向图G=(V,E)，其中V是结点的集合，E是有向边的集合。其中结点表示语句，边表示语句间的控制流关系。令(x,y)∈E表示控制流图中的边x→y，称x是y的前趋，y为x的后继。另外，为G增加了两个特殊的结点:Entry称为入口结点，它没有前趋，从它可到达流图中的每个结点，Exit称为出口结点，它没有后继，每个结点都可到达它。为了保证控制流图中终点的唯一性，将所有结束语句对应的结点都指向Exit的虚结点。为了便于求控制依赖边，加入一条从Entry到Exit的边，这样在求控制依赖时就不用再扩充一个谓词结点了。C语言中语句基本上可分为以下4种类型:(1)简单语句expr_stmt、decl_stmt、输入输出语句等；(2)复合语句if_stmt、switch_stmt、while_stmt、for_stmt、do_stmt等等，这些语句影响整个程序中的控制流程；(3)谓词部分即条件语句和循环语句的判断条件，为了方便处理，在建立结点时可以将谓词部分信息加入到复合语句结点里，并将这种复合语句称为谓词结点；(4)跳转语句break_stmt、continue_stmt、return_stmt和goto_stmt。这里把方法调用语句当成简单语句来处理。当控制流图的边离开谓词结点时标记为T或F，否则没有标记。-8- 哈尔滨工业大学工学硕士学位论文表1GCC抽象语法树常用符号及其含义AST中符号function_decldecl_stmtexpr_stmtif_stmtswitch_stmtfor_stmtwhile_stmtdo_stmtcase_stmtbreak_stmtcontinue_stmtreturn_stmtcompound_stmtscope_stmtmodify_exprplus_exprminus_exprmult_exprtrunk_div_exprtrunk_mod_exprrdiv_exprmin_exprmax_exprabs_exprlshift_exprrshift_exprbit_ior_exprbit_xor_exprbit_and_exprbit_not_exprtruth_andif_exprtruth_orif_exprtruth_not_exprlt_exprle_exprgt_expr含义函数声明语句声明语句表达式语句if语句switch语句for语句while语句do_while语句case语句break语句continue语句return语句大括号语句的范围=+-*/（整数间）%/（实数间）两者取小者两者取大者取绝对值<<>>|^&~&&||!<<=>AST中符号ge_expreq_exprne_exprpreincrement_exprpostincrement_exppredecrement_exprpostdecrement_exprconvert_exprnop_expraddr_exprcomponent_refindirect_refcall_exprinit_exprcond_exprfloat_exprfix_trunc_exprnon_lvalue_exprinteger_cstreal_cststring_cstvoid_typeinteger_typereal_typeenumeral_typearray_typepointer_typerecord_typeunion_typefunction_typevar_declparm_declfield_decltype_declconstrctor含义>===!=++ii++--ii--数组元素转换地址不产生任何代码的转换取地址.结构体和联合用到*函数调用return语句的返回值:?转换成实数转换成整数空转换整型常量实型常量字符串常量void类型int/short/char类型real/float类型枚举类型数组类型指针类型结构体类型联合体类型函数类型变量声明参数声明复合结构中的变量声明自定义声明数组初始化2.2.2语句的控制流图描述(1)顺序语句顺序语句的控制流图形式最简单，只需用一条没有标记的边将一个结点连向下一个结点就可以了，如图2-1所示。其中A、B为语句标号，用来代表该行语句。-9- 哈尔滨工业大学工学硕士学位论文A：a=1;B：b=a+1;图2-1顺序语句的控制流图(2)if语句if语句的控制流图有两个出边：一条标记为T,指向条件为真时的if_stmt，另一条标记为F，指向条件为假时的else_stmt。A:B:C:D:if(a>0){b=1;}else{b=2;}returnb;图2-2if语句的控制流图(3)while语句连接while条件结点语句至少有三条边，一条是由循环形成的入边，另外两条是出边分别标记为T和F，标记T的边指向while的第一个孩子结点，标记为F的边指向while的右兄弟结点。……..A:while(i<10){B:sum+=i;}C:returnsum;图2-3while语句控制流图(4)do-while语句do-while语句的控制流图与while语句的控制流图类似，只是控-10- 哈尔滨工业大学工学硕士学位论文制流进入语句的位置不同。在while语句中控制流先流进条件语句，再进入循环体；而在do-while语句中，控制流的进入的顺序刚好相反。……….do{A:sum+=i;B:}while(i<10)C:returnsum;图2-4do-while语句控制流图(5)goto语句goto语句的控制流图为从goto语句连向标号名字相同的语句。L:a++;A:if(a>0){B:sum+=a;}else{C:gotoL;}D:returnsum;图2-5goto语句控制流图(6)continue语句该语句用语使其所在的for、while或do-while语句进入下一次循环。A:while(i<10){B:if(a=F1)&&(S2<=F2))if(!case_stmt)重新确定LIST列表末语句的结束范围；else(case_stmt)while(下一条语句是case_stmt)当前case_stmt与上一条case_stmt或者CaseUnit合并成新的CaseUnit；用跳出循环的语句结束范围赋值给CaseUnit语句结束范围；endwhileendifendwhile更新函数语句列表；endwhileend图4-3switch语句标准化及确定case_stmt范围的算法4.2.3for语句标准化for语句的表达式1可能是多个声明语句，多个表达式语句，或者是一个变量，本文把表达式1的各个语句依次放到for语句的左兄弟位置，表达式1标准化算法如图4-4所示；for语句的表达式3可能是多个表达式语句，本文把表达式3的各个语句依次放到for语句的最右孩子结点位置，这样for_stmt就和while_stmt一样了，消除了循环语句的多样性，表达式3标准化算法如图4-5所示：4.2.4函数调用语句标准化函数调用结点标准化主要是针对实参中存在表达式或者函数调用，函数调用结点主要存在存在于声明语句和表达式语句中，及条件语句、循环语句、return语句-26- 哈尔滨工业大学工学硕士学位论文的表达式中，还可能存在与函数调用结点的实际参数中。算法：for语句表达式1标准化输入：函数语句列表输出：for语句表达式1标准化后的函数语句列表beginwhile((函数列表非空)&&(for_stmt列表非空))在函数列表中找到未处理的for_stmt；while(for语句的表达式1列表非空)if(expr_stmt)建立表达式语句，并插入到函数语句列表中对应的for语句的前面；endifif(decl_stmt)建立声明语句，并插入到函数语句列表中对应for语句的前面；endifendwhileendwhileend图4-4for语句表达式1标准化算法算法：for语句表达式3标准化输入：控制依赖子图输出：for语句标准化后的控制依赖子图beginwhile（(函数列表非空)&&（for_stmt列表非空））在函数列表中找到未处理的for_stmt；while(for语句的表达式3列表非空)建立表达式语句，开始遍历控制依赖子图找到表达式插入的位置，一般是for语句的最右孩子结点的后面，并更新表达式3的父亲结点列表和for语句的孩子结点列表。endwhileendwhileend图4-5for语句表达式3标准化算法针对函数嵌套情况，本文把嵌套的函数从内到外拆分成多个函数调用结点，并对函数调用结点中的实参进行了标准化，针对表达式实参，把其表达式实参和自定义变量作为声明语句插入到函数语句列表的适当位置。这样存在一个缺陷，就是可-27- 哈尔滨工业大学工学硕士学位论文能引入了变量别名，后续章节将介绍变量别名分析的思想。如果把所有的实参标准化，那么引入的变量别名将大大增加，造成数据流分析的困难，极大的影响了数据流分析的精度。算法：函数调用语句标准化输入：函数语句列表输出：函数调用语句标准化后的函数语句列表声明：TraverseExp（classExprBase*）//遍历声明语句的表达式，并放入InOrderStack中,并记录函数调用个数(callnum)beginwhile(函数语句列表非空)TraverseExp(语句的表达式部分);if(callnum>=1)while(!InOrderStack.empty())if(该语句仅有一个函数调用结点)生成函数调用结点，对函数调用结点中的表达式实参进行标准化，删除该语句，调整函数语句列表。else(该语句有嵌套函数或者有多个函数调用结点)生成函数调用结点，对函数调用结点中的表达式实参进行标准化,更新该语句，调整函数语句列表。endifendwhileendifendwhileend图4-6函数调用语句标准化算法4.2.5语句排序因为提取出的函数语句列表基本上已经有序（按语句开始范围），由于GCC中把if语句的肯定分支语句和否定分支语句合并成一条语句进行处理，本文是把其拆分成两个语句，这样函数语句列表中的语句就存在不是按控制流图顺序排放的，为了保证相同语句的先后顺序，该研究采用稳定排序算法进行排序，稳定排序主要有冒泡排序、插入排序、基数排序等等，考虑到基数排序占用的空间比较大，这里采用了冒泡排序算法。-28- 哈尔滨工业大学工学硕士学位论文4.3控制依赖分析和控制依赖子图生成控制依赖主要是由分支语句和循环语句等引起的。设u和v为程序中的两条语句，若在u执行中对其控制条件的不同取值直接决定着v是否执行，则u和v之间有一条控制依赖边，可以说两条语句之间存在控制依赖关系。4.3.1控制依赖子图控制依赖子图指的是单个函数的各个语句之间的控制依赖关系图，这个步骤先不考虑break_stmt、continute_stmt、goto_stmt的跳转位置，确定各条语句之间的控制依赖关系，即加入父亲结点列表和儿子结点列表。算法：生成控制依赖子图输入：函数语句列表输出：控制依赖子图begin函数语句列表的首结点进栈while(栈非空)栈顶语句范围为F1-F2读取函数列表中的下一条语句，范围为S1-S2;if(!scope_stmt)if(S2<=F2)该语句为栈中复合语句的孩子结点；if(复合语句)该语句进栈；else出栈；while(栈非空)栈顶语句范围为F1-F2；if(S2<=F2)该语句为栈中复合语句的孩子结点；if(复合语句)该语句进栈；else出栈endifendwhileendifelse栈顶的复合语句出栈endifendwhileend图4-7生成控制依赖子图算法-29- 哈尔滨工业大学工学硕士学位论文4.3.2跳转语句的处理跳转语句处理主要是找到break_stmt、continue_stmt、goto_stmt要跳转到的语句位置。continue用于使其所在最内层的循环语句开始下一次循环。break语句用于立即从最内层的循环语句或者switch语句中退出。continue_stmt跳转位置处理算法基本思想：遍历他的祖先结点，从父亲结点开始，第一个包括其范围的循环语句就是要跳到的地方。goto_stmt跳转位置处理算法基本思想：遍历存放标号的列表，找到相同的标记名称，该标号语句为其要跳到的地方。break_stmt跳转位置处理算法具体描述如图4-8所示：算法：break_stmt跳转位置输入：没有处理跳转语句的控制依赖子图输出：处理完跳转语句的控制依赖子图beginwhile(break_stmt列表非空)遍历该语句的祖先结点，从父结点开始，找到第一个包括其范围的循环语句，取该循环语句的父亲结点；find=false;while(!find)switch(当前语句的类型)case循环语句if(当前语句有右兄弟结点)跳转位置为右兄弟语句,find=trueelse跳转位置为父亲语句,find=true；case条件语句if(当前语句有右兄弟结点)跳转位置为右兄弟语句,find=trueelse当前语句为下一个祖先结点。casefunction_declCallnodeif(当前语句有右兄弟结点)跳转位置为右兄弟语句,find=trueelse跳转位置为NULL,find=trueendswitchendwhileendwhileend图4-8break_stmt跳转位置算法-30- 哈尔滨工业大学工学硕士学位论文4.4控制流图的生成控制流图是一个有向图G=(V,E)，V是结点的集合，E是有向边的集合。其中结点表示语句，边表示语句间的控制流关系。控制流图的生成主要是求出每条语句的前驱集合和后继集合，其实就是求结点的入边集合和出边集合。令(x,y)∈E表示控制流图中的边x→y，称x是y的前驱，y为x的后继，或者称x的出边是y,y的入边是x。在控制流图中本文对分支语句进行了标准化，即分支语句的出度都为2，每个分支语句都包含肯定分支和否定分支，从而消除了分支语句的多样性。大多研究一般是在控制流图的基础上进行控制依赖分析和数据依赖分析，本文先建立控制依赖图，在控制依赖图基础上建立控制流图，然后在控制流图上进行数据流分析。控制流图的生成算法具体描述如图4-9所示：4.5数据依赖分析和数据依赖子图生成数据流依赖边一般表示变量之间的定义-引用关系，它包括直接数据流依赖和间接数据流依赖。设语句s定义了变量v,标记为DEF(s,v)，语句t在执行时使用了v，标记为REF(t,v),s与t之间存在一条路径，且在此路径上没有其他语句对v进行重定义，则称语句s关于变量v数据流直接依赖于t，标记为DDE(s,t)。为了包括间接数据流依赖关系，本文定义了广义数据流依赖关系GDDE(s,t)。设s与t是程序中的两个语句，GDDE(s,t)如下：GDDE(s,t)成立当且仅当如下两个条件之一成立时：(1)DDE(s,t)；(2)存在语句e，且同时满足DDE(s,e)和GDDE(e,t)。数据依赖是结点表示的语句之间数据的定义和使用关系。数据依赖可以被区分为不同的类型，如流依赖、输出依赖和反依赖、声明依赖等等。本文用到流依赖、反依赖、声明依赖边。数据依赖子图的构造实际上就是建立流依赖边、反依赖边和声明依赖边的过程，它可以归结到程序中到达-定值信息的求解。由于控制依赖子图包含控制流信息，可通过结合控制流图和控制依赖子图获得各个结点的到达-定值信息，因此可以在创建完控制依赖子图和控制流图后对其执行数据流分析，创建数据依赖子图。传统的数据流分析算法有两种：迭代算法和消除算法。本文改写了编译器代码优化领域中经典的迭代的数据流分析算法，利用控制依赖子图和控制流图来计算数据依赖信息，建立数据依赖子图。4.5.1到达—定值信息相关概念要建立各种数据依赖边应该首先求结点间的到达-定值信息。到达-定值的相关-31- 哈尔滨工业大学工学硕士学位论文算法：生成控制流图输入：控制依赖子图输出：控制流图beginfor(控制依赖子图中的每条语句W)switch(语句类别)caseexpr_stmt:casedecl_stmt:caseCallNode:如果W不是循环或者分支语句内的最右孩子结点，则把下一条语句N加入W的OUTEDGE中，语句N的INEDGE中加入W；casebreak_stmt:casecontinue_stmt:casegoto_stmt:把跳转位置N加入W的OUTEDGE中，语句N的INEDGE中加入W；casefor_stmt:casewhile_stmt:casedo_stmt:取W的第一个孩子结点N加入W的OUTENDGE中，并标记为T，在语句N的INEDGE中加入W；取跳出循环要执行的第一条语句M加入W的OUTENDGE中，并标记为F，并在M的INEDGE中加入W。如果W的最右孩子结点R不为break_stmt，则R的OUTEDGE加入W，在W的INEDGE中加入R。caseswitch_stmt:取W的第一个孩子结点N加入W的OUTENDGE中，在N的INEDGE中加入W。casecase_stmt取W的第一个孩子结点N加入OUTENDGE中，并标记为T，在语句N的INEDGE中加入W；找到判断条件不为真的时要执行的第一条语句M，加入W的OUTENDGE中，并标记为F，在M的INEDGE中加入W。如果最右孩子结点不为break_stmt,处理最右孩子结点。caseif_stmt:取W的第一个孩子结点N加入W的OUTENDGE中，并标记为T，在N的INEDGE中加入W；找到判断条件不为真的时要执行的第一条语句M，加入OUTENDGE中，并标记为F。如果最右孩子结点M为expr_stmt或者decl_stmt，则找到执行完M后下一条要执行的语句S，在M的OUTEDGE中加入S，并在S的INEDGE中加入M。caseelse_stmt:把W的第一个孩子结点N加入W的OUTEDGE中，语句N的INEDGE加入W；如果其最右孩子结点M为expr_stmt或者decl_stmt，则找到执行完M后下一条要执行的语句S加入其OUTEDGE中，并在S的INEDGE中加入M。endswitchendforend图4-9生成控制流图的算法-32- 哈尔滨工业大学工学硕士学位论文概念如下：(1)变量x的定值是一个语句，它赋值或可能赋值给x。常见的定值是对x的赋值或者读值到x中的语句。(2)如果存在路径x能到达结点P，并且在这条路径上d没有被注销，则定值d到达P。如果某个变量x的定值d到达点P，那么P引用x的最新定值可能在d点。(3)如果沿着这条路径的某两点间是读x或对x的赋值，那么本文注销变量x的定值d。为了计算到达程序中每个语句的定值的集合，首先计算局部的定值信息，然后通过控制依赖边进行传播。数据流信息可以由建立和解方程来收集，这些方程联系程序不同点的信息。公式(4-1)是经典的数据流方程：OUT[N]=GEN[N]∪(IN[N]-KILL[N])(4-1)式中GEN[N]——控制流图中结点N对应的语句产生的定值集合；KILL[N]——控制流图中结点N对应的语句注销的定值集合；IN[N]——控制流图中结点N的前驱结点的到达-定值集合；OUT[N]——控制流图中结点N的后继结点的到达-定值集合这个方程的意思是，当控制流通过一个语句时，语句末尾的信息是在这个语句中产生的信息，或是进入语句的信息并且没有被这个语句注销的信息。该方程叫做数据流方程。由数据流方程可看出，算法的关键在于各个控制流结点的GEN和KILL集合的计算。而生成GEN和KILL集合则需要知道各个结点定值和使用了哪些变量，这里用DEF和REF集合来表示。数据依赖分析主要有以下3个难题：(1)GEN和KILL的信息依赖于所需要的信息，即数据流方程所要解决的问题，而且对于某些情况，不是沿着控制流前进和有IN[N]来定义OUT[N]，而是反向前进和由OUT[N]来定义IN[N]。(2)数据流沿着控制流路径流动，因此数据流分析受程序控制流的影响。(3)数据流精度的需求，加强对指针分析、数组变量分析、变量别名分析及过程调用数据流的处理可以提高数据流分析的精度。4.5.2计算语句的REF、DEF、GEN和KILL集合控制流图中结点的GEN、KILL、IN和OUT集合的计算都是基于各结点的REF与DEF信息的，所以如何从控制流图的结点中收集REF与DEF信息对于到达-定值的计算是十分关键的。控制流图中每个结点都有一个REF和DEF集合。一个结点的REF集合包含了-33- 哈尔滨工业大学工学硕士学位论文该结点进行计算时引用的所有变量，DEF集合包含了该结点定义和计算的变量。常见的DEF和REF集合如表4-1所示：表4-1常见结点的DEF和REF集合结点类型常数(const)变量(var)一元表达式(exp)二元表达式(exp1opexp2)赋值语句(var=exp)scanf(var_i,…,var_j)printf(var_i,…,var_j)rerutn_stmtCallNode(exp_i,…,exp_j)函数声明(var_i,…var_j)跳转语句谓词语句(exp)开始、结束结点DEF集合Φ(空)φ++/−−DEF(exp)¢DEF(exp1)∪DEF(exp2){var}∪DEF(exp){var_i,…,var_j}φDEF(exp)DEF(exp_i)∪…∪DEF(exp_j){var_i,…,var_j}φDEF(exp)φREF集合φ{var}REF(exp)REF(exp1)∪REF(exp2)REF(exp)φ{var_i,…,var_j}REF(exp)REF(exp_i)∪…∪REF(exp_j)φφREF(exp)φ结点N的GEN集合由N中的定值组成的，GEN[N]={|N定值了x}。结点N的KILL集合是由程序中其它结点对GEN[N]集合中变量的定值组成的，如果到达IN[N]的变量x在N内被重新定值，则IN[N]中的x的定值不能到达OUT[N]，这种情况称为变量的定值点在N中被注销，所有这样定值的集合用KILL[N]表示，KILL[N]={|M和N分别定值了x，M!=N且M可到达N}。一般谓词结点既没有GEN集合也没有KILL集合。在获得控制依赖子图中各个结点的REF和DEF集合信息后，GEN集合的生成将十分简单：在遍历函数语句列表时，如果当前结点是赋值语句结点或scanf语句结点，-34-{others 哈尔滨工业大学工学硕士学位论文则根据它的DEF集合，由当前的结点号和DEF中的变量名组成GEN集合中一个元素，从而建立GEN集合。KILL集合的生成需要多次遍历控制依赖子图，具体算法描述[35]如图4-10所示：算法：生成各个语句结点的KILL集合输入：控制依赖子图输出：求得各个语句结点的KILL集合的控制依赖子图begin遍历控制依赖子图，将结点N的所有前驱结点，即所有在N之前执行的结点加入到LeftNodeList列表中；while(控制依赖子图非空)for(语句N的LeftNodeList中的每个结点P)if((P是赋值语句)||(P是scanf语句))检查DEF[P]中是否有GEN[N]中的变量，如果有，假设为x，则在KILL[N]中加入二元组endifif(P是循环语句结点)遍历结点P在控制依赖子图中的子图，检查其赋值语句子结点或者scanf语句子结点Q的DEF[Q]中是否有GEN[N]中的变量，若有，假设为x,则在KILL[N]中加入二元组endifendforendwhileend图4-10生成各个语句结点的KILL集合的算法-1一般，过高的估计某一点的定值集合，不会引起数据流安全问题，相反过低估计某一点的定值集合则会导致致命的数据流安全问题，它可能引起改变程序计算结果的变换。对GEN和KILL的估计，超集对GEN时安全的，子集对KILL时安全的，直观上说，增大GEN即加大了到达某一点的定值的集合，但是没有遗漏真正会到达该点的任何定值。同样的道理，减少某一点的KILL集合，也只会增大达到某点的定值集合，这样做是可以保证数据流安全的。当然可以根据实际需要来选取KILL的超集或者子集。为了避免多次遍历控制依赖子图的时间开支，本文在实现时选取了KILL的超集，因为IN集合和OUT集合是在控制流图基础上进行计算的，假设多计算的KILL元素并不会在对应的结点的IN集合中出现，那么数据流也是安全的。具体算法如图4-11所示：-35- 哈尔滨工业大学工学硕士学位论文算法：生成各个语句的KILL集合输入：控制流图输出：求得各个语句结点的KILL集合的控制流图beginfor(每个控制流图G)将控制流图中的所有语句的GEN集合取并集，保存在AllGenList中for(控制流图G的每个语句结点N)for(结点N的GEN集合元素X)if(AllGenList中存在X)把除自身的对X的定值以外的所有元素放入KILL[N]中endifendforendforendforend图4-11生成各个语句结点的KILL集合的算法-24.5.3计算语句的IN、OUT集合为了传播数据流信息，在计算到达-定值信息时需要使用IN和OUT集合。一个结点的IN集合由到达该结点的前一点的定值组成。OUT集合由到达该结点下一点的定值组成。由于一个语句结点的IN和OUT集合可能不同，本文为控制流图中的每个语句结点都计算这两个集合。一般都是采用迭代法求各个结点的IN和OUT集合。在每次迭代时对控制流图中每个结点N，使用KILL和GEN集合计算IN与OUT集合。IN[N]等于结点N在控制流图中前驱结点的OUT集合，OUT[N]是用IN[N]、GEN[N]和KILL[N]生成的。本文对计算IN和OUT集合的算法进行了改进，首先把程序分成基本块，连续的不在循环语句内和分支语句内的简单语句合并成一个基本块，两个基本块之间的语句划为一个基本块，这样当一个基本块内的所有语句的OUT[N]都不再变化则意味着该基本块达到稳定，后续的迭代中不需要再重新计算该基本块。这个算法的迭代次数未知，但是这个算法的迭代次数的上限是控制流图中结点的个数。所以如果对数据流精度要求不是很高的情况下，可以参考程序内的循环语句的最大嵌套深度加上2和条件语句的最大嵌套深度加上2的较大值来人为设定一个阈值，减少时间开销。计算语句的IN和OUT集合的具体算法描述如图4-12所示：-36- 哈尔滨工业大学工学硕士学位论文算法：生成各个语句的IN和OUT集合输入：已知各个结点的DEF、REF、GEN和KILL集合的控制流图输出：求得各个结点的IN和OUT集合的控制流图声明：iternum为迭代次数，maxnum为最大迭代次数。beginfor(每个控制流图G)for(控制流图G中的每个结点N)IN[N]=φOUT[N]=GEN[N]endforchange=true;iternum=0;while(change)&&(iternum<=maxnum)chang=falsefor(控制流图中的每个结点N(结点N所在的基本块没有达到稳定))IN[N]=∪OUT[P]//P是N的前驱结点OLDOUT=OUT[N]OUT[N]=GEN[N]∪(IN[N]-KILL[N])if(OUT[N]!=OLDOUT[N])change=trueendifendforiternum++;endwhileendforend图4-12生成各个语句的IN和OUT集合算法4.5.4建立数据依赖边在获得了各个结点的IN和OUT集合后，利用各结点的IN集合和REF集合即可获得结点间的数据依赖关系。具体的规则是如果当前结点N的REF集合中某个变量名和IN集合中某个二元组中的变量名相同，则认为当前结点和IN集合同一个二元组中给出的结点之间存在数据流依赖关系，并将生成的数据流依赖关系放入表中存储。建立流依赖边、反依赖边和声明依赖边的算法如图4-13所示：4.5.5计算过程间的数据流对每个过程P可以定义集合CHANGE[P]，它的值是在执行P期间可能改变的-37- 哈尔滨工业大学工学硕士学位论文算法：建立流依赖边、反依赖边和声明依赖边输入：求得每个结点的到达-定值信息的控制流图输出：建立了流依赖边、反依赖边和声明依赖边的系统依赖图beginfor(每个控制流图G)for(控制流图G中每个结点N)if(REF[N]不空)for(REF[N]中的每个变量x)for(IN[N]中每个二元组)if(y==x)建立从结点M到结点N的流依赖边建立从结点N到结点M的反依赖边endifendforendforendifendforfor(控制流图中的每个声明语句N)对DEF[N]中的变量x，在控制流图的定值集合中查找变量x,如果找到的话，在N的声明依赖边集合中加入该声明依赖边。endforendforend图4-13建立流依赖边、反依赖边和声明依赖边的算法全局变量和P的形式参数的集合。目前不考虑由于变量的别名等价类中的一个变量改变而引起该变量改变的情况，如果存在环，即存在递归，那么函数调用结点必须特殊处理；如果调用图不存在环，假定只有ilistlistlistlistlistlistlistlistlistlistlistlistlistlistlistlistlistlistlist-44-注释函数返回值类型函数开始的行号函数结束的行号函数名称函数来源于哪个源文件函数参数列表函数内部语句列表函数内部调用的函数名字函数的孩子结点列表函数内的decl_stmt列表函数内的expr_stmt列表函数内的if_stmt肯定分支列表函数内的if_stmt的否定分支列表函数内的switch_stmt列表函数内的case_stmt列表case_stmt合并后的列表函数内的for_stmt列表函数内的while_stmt列表函数内的do_stmt列表函数内的break_stmt列表函数内的continue_stmt列表函数内的return_stmt列表函数内的goto_stmt列表函数内的label_decl列表函数内的CallNode列表 哈尔滨工业大学工学硕士学位论文表5-2StmtBase类的设计变量名称stmtIDstntidstmtKindIsVisitstmtBegstmtEndFatherStmtListChildStmtListInEdgeListOutEdgeListStmtRefListStmtDefListStmtGenMapStmtKillMapStmtInMapStmtOutMapDataEdgeMap变量类型intintintintintintlistlistlistlistlistlistmultimapmultimapmultimapmultimapmap注释对应的AST文本中结点所在行号函数内的第几条语句语句种别码访问标记语句的开始行号语句的结束行号控制依赖图中父亲结点列表控制依赖图中孩子结点列表控制流图结点的入边列表控制流图结点的出边列表语句内引用的变量语句内定义的变量语句内产生的定值集合语句内注销的定值集合流入语句内的变量集合流出语句的变量集合语句的数据流边集合表5-3VarBase类的设计变量名称varKindvarUsedvarInitscpfucIDvarIDischangedpointerDepvarData_1varNamevarData_2srcp_fileArrayDepVecVarAttrvarLink变量类型intintintintintintintintstringstringstringvectorvectorclassVarBase*注释类型种别码是否被使用过是否被初始化来源于哪个函数变量的ID是否是++/--一元表达式指针深度常量值变量名称字符串值该变量来源于哪个源文件数组各个维的大小变量属性:全局、局部、static、unsigned复合结构时候用到-45- 哈尔滨工业大学工学硕士学位论文表5-4StmtBase派生类的设计派生类名称DeclStmtDeclStmtExprStmtIfStmtIfStmtIfStmtElseStmtElseStmtSwitchStmtCaseStmtForStmtForStmtForStmtForStmtWhileStmtDoStmtContinueStmtBreakStmtGotoStmtLabelStmtCallNodeCallNodeCallNodeCallNodeCallNodeCallNodeCallNodeScopeStmtReturnStmt变量名称DeclStmtVarDeclStmtExpExprStmtExprthenBegLinethenBegLineif_condExpelseBegLineelseEndLineswit_condExpcaseValueListexp1_kindfor_condExpfor_exprExpfor_initListwhi_condExpdo_condExpPToNextStmtPToNextStmtPToNextStmtlabelNameretptdFuccallfucNamerealParmListrealVarListParmEdgeMapRetEdgeMapattributeretn_initExp变量类型VarBase*ExprBase*ExprBase*intintExprBase*intintExprBase*listintExprBase*ExprBase*listExprBase*ExprBase*StmtBase*StmtBase*StmtBase*stringVarBase*StmtBase*stringlistlistmapmapintExprBase*注释声明变量声明语句的表达式表达式语句的表达式肯定分支开始行号肯定分支结束行号条件表达式否定分支开始行号否定分支结束行号表达式部分常量值集合标记表达式1的类型表达式2表达式3表达式1列表条件表达式条件表达式跳转位置跳转位置跳转位置标记名称函数返回值记录系统函数的名字指向自定义函数的入口实际参数列表参数标准化后的列表形参和实参之间的边返回值和函数调用之间的边标记是范围开始还是范围结束返回值表5-5ExprBase类的设计变量名称opkindexpOP0expOP1expOP2expOP3变量类型intclassVarBase*classVarBase*classExprBase*classExprBase*-46-注释表达式种别码变量1变量2表达式1表达式2 哈尔滨工业大学工学硕士学位论文图5-1类之间的调用关系图5.2系统应用环境软件平台：WindowsXPProfessional2002操作系统VC++6.0集成开发环境MinGW3.1.0硬件平台：Intel(R)Pentium(R)4CPU2.50GHz2.49GHz,512MB内-47- 哈尔滨工业大学工学硕士学位论文5.3系统测试与分析5.3.1源程序1的测试与分析1234567891011intmain(){inta=0;intb=10;inti=0;while(i<=10){if(a>=b){i++;break;1213141516171819202122}}else{a++;b--;i++;continue;}}return0;图5-2源程序1本文在建立控制依赖图的时候，把控制依赖关系归结为求语句的父亲—孩子关系，其中跳转语句没有孩子结点，但是有跳转位置，在表5-6中，我们用[跳转到的结点行号]来表示。在建立控制流图时，归结为求语句结点的前驱结点和后继结点，即INEDGE和OUTEDGE。REF就是语句中引用的定值集合，GEN就是语句结点产生的定制集合，KILL就是语句结点中注销的定值集合，相关分析如表5-6所示：表5-6计算源程序1的控制依赖图、控制流图、REF、GEN和KILL结点1父亲¢孩子{3,4,5,INEDGE¢OUTEDGE{3}¢REF¢GEN¢KILL6,21}345681011{1}{1}{1}{1}{6}{8}{8}¢¢¢{8,13}{10,11}¢[21]{1}{3}{4}{5,18}{6}{8}{10}{4}{5}{6}{8,21}{10,15}{11}{21}¢¢¢{(6,i)}{(8,a),(8,b)}{(10,i)}¢{(3,a)}{(4,b)}{(5,i)}¢¢{(10,i)}¢{(15,a)}{(16,b)}{(10,i),(17,i)}¢¢{(5,i),(17,i)}¢13{6}{15,16,17,18}1516171821{13}{13}{13}{13}{1}¢¢¢[6]¢{8}{15}{16}{17}{6,11}{16}{17}{18}{6}¢{(15,a)}{(16,b)}{(17,i)}¢¢{(15,a)}{(16,b)}{(17,i)}¢¢{(3,a)}{(4,b)}{(5,i),(10,i)}¢¢-48- 哈尔滨工业大学工学硕士学位论文本文在建立数据流图的时候，归结为多次遍历控制流图求语句的IN集合和OUT集合，直到函数内的所有语句的OUT集合不再发生变化为止，本文引入了基本块，只要语句所在的基本快达到稳定，加入还存在没有稳定的基本块，那么已经稳定的基本块在下一次迭代时候不需要重新计算。在迭代开始之前，把语句结点的IN集合赋值为空，OUT集合为语句的GEN集合。具体分析如表5-7所示：表5-7计算源程序1的IN、OUT集合结第1次迭代第2次迭代点134IN集合¢¢{(3,a)}{(3,a),(4,b)}OUT集合¢{(3,a)}{(3,a),(4,b)}{(3,a),(4,b),IN集合¢¢{(3,a)}{(3,a),(4,b)}OUT集合¢{(3,a)}{(3,a),(4,b)}{(3,a),(4,b),(5,i)}5(5,i)}6810{(3,a),(4,b),(5,i)}{(3,a),(4,b),(5,i)}{(3,a),(4,b),(5,i)}{(3,a),(4,b),(10,i{(3,a),(4,b),(5,i)}{(3,a),(4,b),(5,i)}{(3,a),(4,b),(10,i)}{(3,a),(4,b),{(3,a),(4,b),(5,i),(15,a),(16,b),(17,i)}{(3,a),(4,b),(5,i),(15,a),(16,b),(17,i)}{(3,a),(4,b),(5,i),(15,a),(16,b),(17,i)}{(3,a),(4,b),(10,i),{(3,a),(4,b),(5,i),(15,a),(16,b),(17,i)}{(3,a),(4,b),(5,i),(15,a),(16,b),(17,i)}{(3,a),(4,b),(10,i),(15,a),(16,b)}{(3,a),(4,b),(10,i),11)}(10,i)}(15,a),(16,b)}(15,a),(16,b)}15{(3,a),(4,b),(5,i)}{(4,b),(5,i),{(4,b),(5,i),(15,a)}{(5,i),(15,a),{(3,a),(4,b),(5,i),(15,a),(16,b),(17,i)}{(4,b),(5,i),(15,a),{(4,b),(5,i),(15,a),(16,b),(17,i)}{(5,i),(15,a),(16,b),16171821(15,a)}{(5,i),(15,a),(16,b)}{(15,a),(16,b),(17,i)}{(3,a),(4,b),(5,i),(10,i)}(16,b)}{(15,a),(16,b),(17,i)}{(15,a),(16,b),(17,i)}{(3,a),(4,b),(5,i),(10,i)}(16,b),(17,i)}{(5,i),(15,a),(16,b),(17,i)}{(15,a),(16,b),(17,i)}{(3,a),(4,b),(5,i),(10,i),(15,a),(16,b),(17,i)}{(15,a),(16,b),(17,i)}{(15,a),(16,b),(17,i)}{(3,a),(4,b),(5,i),(10,i),(15,a),(16,b),(17,i)}(17,i)}当所有语句的OUT集合稳定后，计算数据流依赖边，只需要根据表5-6中的REF集合和表5-7中的第三次迭代(表5-7省略了第三次迭代过程)后的IN集合来计算，具体规则是如果REF集合中的定值在IN集合中，则两个语句结点之间存在数据依赖边，源程序1的数据依赖边为{(3,8),(3,15),(4,8),(4,16),(5,6),(5,10),(5,17),(15,8),(15,15),(16,8),(16,16),(17,6),(17,10),(17,17)}。生成的系统依赖图的图形表示如图5-3所示：-49- 哈尔滨工业大学工学硕士学位论文控制依赖边数据依赖边跳转边图5-35.3.2源程序2的测试与分析源程序1对应的系统依赖图123456789101112131415161718intsearch(inta[],intkey,intn){intlow=1;inthigh=n;intmid;while(low<=high){mid=(low+high)/2;if(key>a[mid]){low=mid+1;}else{if(keysecond++;if(t->second==60){t->second=0;t->minute++;}if(t->minute==60){t->minute=0;t->hour++;19}20if(t->hour==24)21{22t->hour=0;23}24}25voidDisplay(CLOCK*T)26{27printf(“%2d:2d%:2dr”,t->hour,t->minute,t->second)28}29voidDelay()30{31longt=0;32while(t<50000000)33{34t++;}353637383940414243444546474849505152}intmain(){longi=0;CLOCKm;m.hour=0;m.minute=0;m.second=0;while(i<1000000){Update(&m);Display(&m);Delay();i++}return0;}图5-6源程序3-53- 哈尔滨工业大学工学硕士学位论文图5-7源程序3对应的控制流图控制依赖边数据依赖边调用边声明依赖边图5-8源程序3对应的系统依赖图-54- 哈尔滨工业大学工学硕士学位论文5.3.4实验结果对比分析李鑫[36]的研究是基于GCC抽象语法树文本的，遗憾的是只给出了控制依赖子图的生成方法，李永浩[34]、王甜甜[35]的研究是基于自己编写的词法分析器和语法分析器的,编写的编译器功能不是很强大，而且他们的研究没有建立控制流图，是在控制依赖子图的基础上进行的数据流分析，在对分支语句和循环语句的处理上存在缺陷，只计算了分支、循环语句中的部分语句，并且不能处理复杂的语法语句，导致数据流精度很低。另外，他们研究的主要目的是应用在C语言自动评分系统中，给出的方法在处理大型程序时存在缺陷。国内外的其它研究大多是在控制流图的基础上建立控制依赖图和数据流图，它的缺陷是如果用户需不需要数据流图都必须建立控制流图，增加了冗余的中间表示。本文没有采用这一惯性思维方法，立足于方便用户的角度，先建立控制依赖图，在控制依赖图的基础上建立控制流图，在控制流图的基础上建立数据流图，这样建立的优点是只有用户需要数据流图时才建立控制流图，减少了中间表示。本文的研究是基于GCC抽象语法树文本的，借鉴了李鑫的研究，可是说是对李鑫研究的后续，最终给出了系统依赖图。由于调用功能强大的GCC编译器，比手写的编译器功能要完善的多，避免了词法分析和语法分析等难题。另外，本文是在控制流图的基础上实现数据流分析的，可以更好地处理分支、循环语句，能够处理较复杂的语法语句，提高了数据流分析的精度，另外本文还介绍了指针分析，变量别名分析，数组变量分析等等提高数据流精度的方法。用户可以根据实际需要权衡数据流精度和时间消耗。通过上述实验，也充分说明了本文算法的可行性和优越性。5.4本章小结本章重点介绍了实现系统时候的详细设计和对C语言程序的测试分析，验证了前面章节讲述的系统依赖图生成算法的可行性，通过和以前研究的对比，说明了本文研究的方法的优越性。本系统只讲述了指针分析和变量别名分析的思想，没有把其实现，可能会影响数据流的精度。另外本系统是以文本的形式输出结果，没有给用户一个直观的图形表示。-55- 哈尔滨工业大学工学硕士学位论文结论本文提出了基于GCC抽象语法树文本建立系统依赖图的方法，该方法没有采用传统的构建系统依赖图的流程，词法分析和语法分析部分由GCC编译器来完成，首先在抽象语法树文本的基础上构建控制依赖子图，然后在控制依赖子图的基础上构建控制流图，最后在控制流图的基础上建立数据流图，进一步完善系统依赖图。本文在设计时从方便用户和节省时空开支的角度综合考虑，给予用户是否需要数据流分析模块和数据流分析精度的控制权，同时对每个过程的相关信息进行了统计，为用户查询模块奠定了基础。本文主要完成的工作及特点如下：(1)对GCC编译器产生的抽象语法树文本的结构进行了深入的研究，并提出了基于GCC抽象语法树文本构建系统依赖图的方法。(2)对GCC抽象语法树文本进行了标准化，并消除了抽象语法树文本中与控制依赖分析和数据依赖分析无关的结点，使抽象语法树文本减小到原来的几十分之一，或者更小。(3)结合面向对象的思想进行源程序静态信息提取，保证静态信息的规范性和完整性。(4)从方便用户的角度出发，给与用户更多的控制权，提出了构建系统依赖图的新流程，先建控制依赖子图，然后在控制依赖子图的基础上构建控制流图，最后在控制流图的基础上构建数据流图。如果用户不需要数据流分析，后续的控制流图和数据流图工作就不需要了，如果用户对数据流精度有所要求的话，那么可以结合人工控制，满足用户需求。(5)提出了抽象语法树文本标准化、消除抽象语法树文本中的冗余信息、静态信息提取、建立控制依赖图、建立控制流图的新方法，并对传统的构建数据流图的方法进行了改进。另外，本文还阐述了提高数据流精度的思想。实验证明，本文提出的方法具有可行性，通过与以往研究的对比，说明了该方法在时空效率上有很强的优越性，并且能应用到大型程序分析中，为静态分析工具和C语言自动评分系统奠定了基础。由于时间和个人能力的限制，该系统还有需要完善的地方，这也是后续研究的主要工作，总结如下：(1)本文只阐述了提高数据流精度的思想，如指针分析、变量别名分析等等，系统中没有实现。-56- 哈尔滨工业大学工学硕士学位论文(2)系统实现时只对每个过程的相关信息进行了统计，没有实现查询模块。(3)系统输出结果不是图形表示，只输出了用于建立系统依赖图的结点和结点之间的关系的静态信息。-57- 哈尔滨工业大学工学硕士学位论文参考文献12345678910111213T.J.ParrandR.W.Quong.ANTLR:APredicated-LL(k)ParserGenerator.SoftwarePracticeandExperience,25(7):789-810,July1995.R.Holt,A.Winter,andS.Sim,GXL:Towardsastandardexchangeformat,inProceedingsofIEEEWorkingConferenceonReverseEngineering,IEEEPress,November2000:1301~1333.石峰等.一种解析GCC抽象语法树的方法.计算机应用.2004,(24)3:115~116.LiWX,GuoW.PekingUniversityonlinejudgeanditsapplications.JournalofChangchunPostandTelecommunicationInstitute,2005,23(2):170-177G.Antoniol,XML-OrientedGCCASTAnalysisandTransformations,inProceedingsoftheThirdIEEEInternationalWorkshoponSourceCodeAnalysisandManipulation,2005,7:869~901刘文伟等.一个重建GCC抽象语法树的方法.计算机工程与应用.2004,8:125~128.JamesF.Power.ProgramannotationinXML:aparse-treebasedapproach,inProceedingsoftheNinthWorkingConferenceonReverseEngineering1095-1350.2002,6.王相懂等.基于GCC抽象语法树对C++源程序结构的分析.计算机工程与应用,2006,6:97~100.Z.Li,S.Lu,S.Myagmar,etal.CP-Miner:FindingCopy-PasteandRelatedBugsinLarge-ScaleSoftwareCode.IEEETransactionsonSoftwareEngineering,2006:32(3):176-192.Z.Li,Y.Zhou.PR-Miner:AutomaticallyExtractingImplicitProgrammingRulesandDetectingViolationsinLargeSoftwareCode.ACMSIGSOFTSoftwareEngineeringNotes,2005,30(5):306–315D.Wagner.AFirstStepTowardsAutomatedDetectionofBufferOverrunVulnerabilities.Proc.7thNetworkandDistributedSystemSecuritySymp,InternetSoc,2002:3-17.J.Foster.Flow-SensitiveTypeQualifiers.Proc.ACMConf.ProgrammingLanguageDesignandImplementation(PLDI02),ACMPress,pp,2002:1-12.K.Ashcraft,D.Engler.UsingProgrammer-WrittenCompilerExtensionstoCatchSecurityHoles.Proc.IEEESymp.SecurityandPrivacy,IEEECSPress,2002:131-147.-58- 哈尔滨工业大学工学硕士学位论文14H.Chen,D.Wagner.MOPS:AnInfrastructureforExaminingSecurityPropertiesofSoftware.Proc.9thACMConf.ComputerandCommunicationsSecurity(CCS02),ACMPress,2002:235-244.15D.Larochelle,D.Evans.StaticallyDetectingLikelyBufferOverflowVulnerabilities.Proc.10thUsenixSecuritySymp.(Usenix01),UsenixAssoc.2001,177-189.16D.Hovemeyer,W.PughDec.FindingBugsisEasy.ACMSIGPLANNotices,2004,39(12):92-106.17D.Hovemeyer,J.Spacco,W.Pugh.The6thACMSIGPLAN-SIGSOFTworkshoponProgramanalysisforsoftwaretoolsandengineering,2006,13-19.18W.R.Bush,J.D.Pincus,D.J.Sielaff.AStaticAnalyzerforFindingDynamicProgrammingErrors.Software-Practice&Experience,2000,(30):775-802.19T.Ball,S.K.Rajamani.TheSLAMproject:DebuggingSystemSoftwareviaStaticAnalysis.InProceedingsofthe29thAnnualACMSIGPLAN-SIGACTSymposiumonPrinciplesofProgrammingLanguages,Portland,Oregon,2002,1-3.20P.Anderson,T.Reps,T.Teitelbaum.DesignandImplementationofaFine-GrainedSoftwareInspectionTool.IEEETransactionsonSoftwareEngineering,2003,29(8):721-733.21蔡志.软件静态分析的研究与实现[D]:[硕士学位论文].南京:南京大学,2002.22李心科.软件故障分析及质量评估方法的研究[D]:[博士学位论文].合肥:合肥工业大学,2001.23李建平.C++程序安全漏洞及检测方法的研究[D]:[硕士学位论文].西安:西安电子科技大学,2004.24吕维梅,刘坚.C程序类型隐式转换漏洞的静态检测[J].计算机工程与应用,2005,41(11):80-82.25杨小龙,刘坚.C/C++源程序缓冲区溢出漏洞的静态检测[J].计算机工程与应用.2004,40(20):108-110.26MarkWeiser.Programslices:formal,psychological,andpracticalinvestigationsofanautomaticprogramabstractionmethod.PhDThesis,UniversityofMichigan,AnnArbor,197927WeiserM.1984.Programslicing.IEEETransactiononSoftwareEngineering.10(4):352~35728ChenZ,XuB.2001.Slicingobiect-orientedjavaprograms.ACMSIGPLANNotices,36(4):33-4029SteindlC.1998.Inter-modularslicingofobject-orientedprograms.In:ProceedingsoftheInternationalConferenceonCompilerConstruction,LectureNotesinComputerScience1383,264~267-59- 哈尔滨工业大学工学硕士学位论文30KorelB,LaskiJ.1988Dynamicslicing.InformationProcessingLetters.29(3):155~16331KorelB,LaskiJ.1990Dynamicslicingincomputerprograms.TheJournalofSystemsandSoftware.13(3):187~19532李必信，刘小东，郑滔等.一种面向对象程序的分层切片方法.软件学报.2001,12,12(12).pp.1810~181733李必信，王云峰，张勇翔等.基于简化系统依赖图的静态粗粒度切片方法.软件学报.2001,12,02.pp.0204~0834李永浩.基于程序理解的编程题自动评分系统研究与应用.哈尔滨工业大学硕士论文.2004:1~6035王甜甜.基于语义相似度的编程题自动评分系统研究与应用.哈尔滨工业大学硕士论文.2005:1~5336李鑫.GCC抽象语法树的解析及控制依赖子图的建立方法研究.哈尔滨工业大学硕士论文.2008:1~4537王甜甜.结构语义等价的程序识别方法的研究.哈尔滨工业大学博士论文.2009:20~4838王甜甜,郭全萍,马培军,苏小红.用指针实现的程序的标准化及其应用.哈尔滨工业大学学报.2009,41(3):48~52(EI刊源)39LiWX,GuoW.PekingUniversityonelinejudgeanditsapplications.JournalofChangchunPostandTelecommunicationInstitute,2005,23(2):170-177.40AllowattA,EdwardsS.IDEsupportfortestdrivendevelopmentandautomatedgradinginbothJavaandC++.In:OOPSLA’05ETXWorkshop.California,2005.41WangH,XiaoJ,FengG.Implementationofatestingsystemonweb-basedcourseofCprogramminglanguage.Computer&DigitalEngineering,2003,31(1):37-41.42M.Harman,C.Fox,R.Hierons,L.Hu,S.Danicic,J.Wegener.VADA:ATransformation-basedSystemforVariableDependenceAnalysis.ProceedingsofthesecondIEEEworkshoponSourceCodeAnalysisandManipulation,LosAngeles,IEEE,2002:55~6443陈彦刚.基于系统依赖图的JAVA程序静态信息抽取.吉林大学硕士论文.2001:1~4444李慧贤.面向对象程序切片中的控制流分析.西安电子科技大学硕士论文.2003:1~6045陆仲达.面向对象程序切片中的控制流分析.西安电子科技大学硕士论文.2003:1~20-60- 哈尔滨工业大学工学硕士学位论文攻读学位期间发表的学术论文-61- 哈尔滨工业大学工学硕士学位论文哈尔滨工业大学硕士学位论文原创性声明本人郑重声明：此处所提交的硕士学位论文《基于GCC抽象语法树文本的C源程序语义分析方法研究》，是本人在导师指导下，在哈尔滨工业大学攻读硕士学位期间独立进行研究工作所取得的成果。据本人所知，论文中除已注明部分外不包含他人已发表或撰写过的研究成果。对本文的研究工作做出重要贡献的个人和集体，均已在文中以明确方式注明。本声明的法律结果将完全由本人承担。作者签名：日期：2009年6月28日哈尔滨工业大学硕士学位论文使用授权书《基于GCC抽象语法树文本的C源程序语义分析方法研究》系本人在哈尔滨工业大学攻读硕士学位期间在导师指导下完成的硕士学位论文。本论文的研究成果归哈尔滨工业大学所有，本论文的研究内容不得以其它单位的名义发表。本人完全了解哈尔滨工业大学关于保存、使用学位论文的规定，同意学校保留并向有关部门送交论文的复印件和电子版本，允许论文被查阅和借阅，同意学校将论文加入《中国优秀博硕士学位论文全文数据库》和编入《中国知识资源总库》。本人授权哈尔滨工业大学，可以采用影印、缩印或其他复制手段保存论文，可以公布论文的全部或部分内容。本学位论文属于（请在以上相应方框内打“√”）：保密□，在不保密□年解密后适用本授权书作者签名：导师签名：-62-日期：日期：2009年6月28日2009年6月28日 哈尔滨工业大学工学硕士学位论文致谢在此论文完成之际，谨向给与我帮助的人们致以最衷心的谢意!首先向我的导师苏小红老师、马培军老师表示衷心的感谢。在两年的研究生期间，他们在研究上给予我很多鼓励，多次给我指点迷津，提出了许多宝贵的建议，对我今后的科研方面有很大的帮助。在生活上两位老师以身作则，教导本文踏踏实实的做人，认认真真的做事。两位老师渊博的学识、严谨的治学态度、忘我的工作精神和这两年对我的谆谆教诲都使我终身受益。感谢王甜甜师姐、李鑫师哥，实验室的所有同学，他们在课题研究上给予我很多的帮助，提出了很多宝贵的建议，激励我不断努力，在此表示衷心的感谢！-63-