一种基于gcc抽象语法树程序特征提取方法

《一种基于gcc抽象语法树程序特征提取方法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、一种基于GCC抽象语法树程序特征提取方法　　摘要提出一种基于GCC（GNUCompilerCollection）抽象语法树建立程序特征文本的方法，消除抽象语法树中与程序无关的结点，从消除冗余后的抽象语法树文本中提取可以表达程序语义的可用结点；之后对其进行信息提取，从而高效地生成程序特征文本。通过实验证明了该方法的正确性与实用性。【关键词】抽象语法树信息提取程序代码特征文本1引言目前主流的程序代码抄袭检测系统JPlag[1]和YAP3[2]都采用字符串比较技术，这种技术核心问题之一是提取可以表示源

2、程序的特征[3]，即能够代表该程序内容和结构信息的字符串，该字符串是一个线性串，其包含的程序结构信息的多少，将直接影响结果的准确性。针对上述问题，本文提出了一种程序特征提取方法。该方法借助GCC（GNUCompilerCollection）编译器，将程序转换成抽象语法树（Abstractsyntaxtree），重点分析AST结构，从中提取表达程序语义的信息。1.1AST结构GCC7编译器以源程序的过程为单位生成AST，而且包含整个编译单元的完整表示，比较直观地表示出源程序的语法结构，并含有源程序

3、结构显示所需的全部静态信息。AST是GCC编译器前端的中心数据结构，AST的结点类型包括以下7种：①标识符结点（identifiers），②类型结点（types），③声明结点（declarations），④函数结点（functions），⑤范围结点（scope），⑥语句结点（statements），⑦表达式结点（expressions）。从GCC编译器3.0版本开始，用编译参数-fdump-translation-unit[4]可以得到*.tu的以文本形式输出的AST文件，其中*为源程序名，部分

4、AST文件如图1所示，一个结点的AST结构如图2所示，一个AST文本有若干个这样的结点组。1.2AST包含的静态信息AST中包含的静态信息主要有文件、函数、变量、表达式等从大到小几个层次的基本信息，如文件的信息主要为文件名；函数的基本信息主要有函数名、函数的类型、函数的参数个数及对应的参数类型、函数包括哪些局部变量；变量的基本信息主要是变量的个数、变量名、变量类型。对抽象语法树提取静态信息主要通过标识符结点、函数结点、类型结点、表达式结点等结点类型来提取静态信息，每种结点类型都对应多个抽象语法树

5、结点，如表达式结点对应的有：7①real_cst结点描述常量的表现形式；②parm_decl结点描述函数的参数；③var_decl结点代表变量，包括静态数据成员；④nop_expr结点描述不需要任何代码产生的变换，既表示单个运算数可以被转变；⑤modify_expr结点描述任务，操作对象有变量、指针指向对象等。这些结点用来描述不仅有赋值“=”操作，还有“+=”操作，既i+=3，i=i+3。2基于GCC抽象语法树的程序特征提取编译器的目的是将高级语言转化为汇编代码，故而GCC产生的抽象语法树文本中

6、包含许多有助于编译的细节信息，例如由#include命令产生的未被源程序用到的函数及结构，以及编译过程中产生的一些内部函数、类型声明、出错信息、常量等，这些信息与程序无关，属于无用信息。在数量上，一个七行代码的加法运算程序，能产生三千五百多个结点的抽象语法树文本，如果直接解析抽象语法树文本，最终产生的AST会占据整个内存，产生内存“泄漏”。因此，GCC产生的抽象语法树文本规模庞大，不适合直接提取静态信息，所以需要先消除抽象语法树文本中的冗余信息，过滤跟源程序无关的结点，方便静态信息提取。2.1A

7、ST优化7为了提高从GCC抽象语法树中提取静态信息的效率，优化的目标是消除抽象语法树中所有不能表达程序含义的信息，既消除抽象语法树文本中与程序无关的抽象语法树结点。利用文献[5]中提到的对AST消除结点冗余的方法，同时，对结点进行结点编号映射。2.2提取目标生成AST后，源程序中包含的语义都概括到了AST的各个结点当中，经过消除冗余所生成的AST文本中每个结点都独立表示各自的含义，例如变量结点（var_decl）所含的结点信息不完整，叶子结点所含的结点信息单一。而且，原来父子结点之间继承的关系被

8、破坏，这样一个发散的结点集合不能表达程序语义，所以需要对规范的AST文本进行信息提取[6，7，8]，使得一个结点含有多种信息。2.3提取方法在优化阶段时选择AST中有用的结点，这些结点的信息不完整，结点含有多个标记签，标记签的值用一个结点编号表示，真实的标记值由另外一个结点表示。虽然优化破坏了结点的继承关系，但是通过优化时建立的结点映射，将标记签的值由其对应的叶子结点替换。7AST结点中含有多种信息，在提取AST过程中，用叶子结点替换有用结点的标记值，在替换的同时，叶子结点中的标识符（ident