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

摘 要 提出一种基于GCC（GNU Compiler Collection）抽象语法树建立程序特征文本的方法,消除抽象语法树中与程序无关的结点,从消除冗余后的抽象语法树文本中提取可以表达程序语义的可用结点；之后对其进行信息提取,从而高效地生成程序特征文本.通过实验证明了该方法的正确性与实用性.

【关 键 词 】抽象语法树 信息提取 程序代码 特征文本

1.引言

目前主流的程序代码抄袭检测系统JPlag[1]和YAP3[2]都采用字符串比较技术,这种技术核心问题之一是提取可以表示源程序的特征[3],即能够代表该程序内容和结构信息的字符串,该字符串是一个线性串,其包含的程序结构信息的多少,将直接影响结果的准确性.针对上述问题,本文提出了一种程序特征提取方法.该方法借助GCC（GNU Compiler Collection）编译器,将程序转换成抽象语法树（Abstract syntax tree）,重点分析AST结构,从中提取表达程序语义的信息.

1.1 AST结构

GCC 编译器以源程序的过程为单位生成AST,而且包含整个编译单元的完整表示, 比较直观地表示出源程序的语法结构,并含有源程序结构显示所需的全部静态信息.AST是GCC编译器前端的中心数据结构,AST的结点类型包括以下7种：①标识符结点（identifiers）,②类型结点（types）,③声明结点（declarations）,④函数结点（functions）,⑤范围结点（scope）,⑥语句结点（statements）,⑦表达式结点（expressions）.从GCC编译器3.0版本开始,用编译参数-fdump-translation-unit[4]可以得到*.tu的以文本形式输出的AST文件,其中*为源程序名,部分AST文件如图1所示,一个结点的AST结构如图2所示,一个AST文本有若干个这样的结点组.

1.2 AST包含的静态信息

AST中包含的静态信息主要有文件、函数、变量、表达式等从大到小几个层次的基本信息,如文件的信息主要为文件名；函数的基本信息主要有函数名、函数的类型、函数的参数个数及对应的参数类型、函数包括哪些局部变量；变量的基本信息主要是变量的个数、变量名、变量类型.

对抽象语法树提取静态信息主要通过标识符结点、函数结点、类型结点、表达式结点等结点类型来提取静态信息,每种结点类型都对应多个抽象语法树结点,如表达式结点对应的有：

①real_cst结点描述常量的表现形式；

②parm_decl结点描述函数的参数；

③var_decl结点代表变量,包括静态数据成员；

④nop_expr结点描述不需要任何代码产生的变换,既表示单个运算数可以被转变；

⑤modify_expr结点描述任务,操作对象有变量、指针指向对象等.这些结点用来描述不仅有赋值“等于”操作,还有“+等于”操作,既i+等于3,i等于i+3.

2基于GCC抽象语法树的程序特征提取

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

2.1 AST优化

为了提高从GCC抽象语法树中提取静态信息的效率,优化的目标是消除抽象语法树中所有不能表达程序含义的信息,既消除抽象语法树文本中与程序无关的抽象语法树结点.利用文献[5]中提到的对AST消除结点冗余的方法,同时,对结点进行结点编号映射.

2.2 提取目标

生成AST后,源程序中包含的语义都概括到了AST的各个结点当中,经过消除冗余所生成的AST文本中每个结点都独立表示各自的含义,例如变量结点（var_decl）所含的结点信息不完整,叶子结点所含的结点信息单一.而且,原来父子结点之间继承的关系被破坏,这样一个发散的结点集合不能表达程序语义,所以需要对规范的AST文本进行信息提取[6,7,8],使得一个结点含有多种信息.

2.3 提取方法

在优化阶段时选择AST中有用的结点,这些结点的信息不完整,结点含有多个标记签,标记签的值用一个结点编号表示,真实的标记值由另外一个结点表示.虽然优化破坏了结点的继承关系,但是通过优化时建立的结点映射,将标记签的值由其对应的叶子结点替换.

AST结点中含有多种信息,在提取AST过程中,用叶子结点替换有用结点的标记值,在替换的同时,叶子结点中的标识符（identifier_node）、描述结点名称的（strg）,以及描述结点长度（lngt）等字段同时也被提取出来,而且结点中原本包含的的结点编号、srcp、algn、size、use等标记签,这些信息会产生噪声,所以在提取后消除这些字段,保证提取信息的可用性.

3实验分析

在Dev-C++_4.9.9.2环境中实现以上算法,产生的部分程序特征文本如图3所示.图3与图1相比可以看出,总体上效果达到了预计的目标,较好地提取了AST中与程序有关的信息,该文本是以计算10个整数和的平均值为例,取部分结构特征.

4.结束语

本文提出的方法达到了很好的效果并且具有较低的时间复杂度与空间复杂度.作为改善程序代码相似度计算的重要一步,现已用到程序代码抄袭检测系统中,取得了良好的效果.与传统线性字符串匹配法相比,该文本具有更好的检测准确性与可靠性. 参考文献

[1] Prechelt L, Malpohl G, Philippsen M.Finding Plagiaris among a Set of Programs with JPlag[J].Journal of Universal Computer Science,2002,8（11）：1016-1038.

[2] Wise M J. YAP3： Improvement Detection of Similarities in Computer Program and Other Texts[A]. Proceedings of the 27th SIGCSE Technical Symposium on Computer Science Education[C].New York： Association for Computing Machinery, 1996, 28（1）： 130-134.

[3]赵彦博.基于抽象语法树的程序代码抄袭检测技术研究[D] .内蒙古师范大学,2010：2-11.

[4]GCC Command Options.Available[OL].

http：//gcc.gnu./onlinedocs/gcc-3.0.4/gcc.,2012-2-1.

[5]李鑫,王甜甜,苏小红等.消除GCC抽象语法树文本中冗余信息的算法研究[J].计算机科学,2008,35（10）：170-172

[6]刘文伟,刘坚.一个重建GCC抽象语法树的方法[J].计算机工程与应用,2004,18：125-128.

[7]石峰,刘坚.一种解析GCC抽象语法树的方法[J].计算机应用,2004,24（3）：115-116.

[8]王相懂,张毅坤.基于GCC抽象语法树对C++源程序结构的分析[J].计算机工程与应用,2006,23：97-100.

作者简介

张良德（1978-）,男,内蒙古兴安盟人,讲师,硕士.研究方向：计算机辅助教学.

赵彦博（1980—）,男,内蒙古鄂尔多斯人,工程师,硕士.研究方向：数据挖掘,电力信息分析与处理.

作者单位

1. 内蒙古职业学院 内蒙古自治区呼和浩特市 010051

2. 呼和浩特供电局调度管理处 内蒙古自治区呼和浩特市 010050