基于动态检测与静态分析的自动评分方法研究

薛 斌，胡建鹏

（上海工程技术大学 电子电气工程学院，上海 201620）

0 引言

C 语言是高校中工科专业的必修基础课程，也是国际上广为流行的高级程序设计语言。在C 语言程序设计课程中，考核学生知识掌握程度的重要手段之一就是对编程能力的考察，学生只有通过大量的上机代码实践，才能更好地理解C 语言程序的精髓。目前，高校普遍采用线上系统对C 语言编程题进行上机考试，但此类系统大多仅有通过与错误两种运行结果。只关注程序运行的结果，而忽视程序本身，这既不能合理地考察学生对知识的掌握程度，也不能让学生得到及时有效的反馈。为了对运行结果异常以及不能运行的学生程序进行评分，教师仍需要把学生编写的答案打印出来，进行人工评分，不仅效率低下，而且评分结果可能会受到阅卷老师的主观因素影响。

本文结合动态检测与静态分析策略，设计了一种新型的C 语言自动评分方法，并将该方法融合到线上实验系统中。首先，进行动态检测，利用KMP算法执行关键字匹配，若匹配相似度落入预期值区间，再将学生程序代码转换为可执行文件，通过预先设置的测试用例来驱动评分。若关键字匹配未通过、程序无法运行以及运行期间出现异常，则进行静态分析，对学生源程序代码和模板程序代码进行标准化，通过控制结构子树的匹配相似度来综合评分。

1 动态检测方案设计

基于动态检测的自动评分方法属于软件自动化测试方法［1］，其核心的检测步骤如下：预先设置好测试用例作为输入数据；把源程序转换为可执行文件并运行；通过判断期望值与输出数据是否相等来进行自动评分。但是对于某些编程题来说，学生可以对照测试用例来编写代码，以达到欺骗系统并获取得分的目的。为了杜绝此类状况，并减少系统无效运行的次数，本系统在执行动态检测时，首先会通过Knuth－Morri－Pratt［2］（简称KMP）算法进行关键字的匹配，当整体匹配相似度落入预期值区间时，便执行后续步骤，否则转入静态检测流程［3］。

1.1 基于KMP 算法的关键字检测

本系统主要针对非计算机专业的学生群体，编程考题相对简单，而且很多C 语言关键字也不在教学使用范围内，如register、auto、volatile，故本文在原有关键字范围基础上做一些删减，并增加了有利于考察代码逻辑的特征词，如stdio.h、stdlib.h、sqrt（）、abs（）等。针对关键字检测的操作步骤如下：

（1）从头至尾扫描程序代码，删掉代码中所有的空格、空行以及注释；

（2）对学生源程序进行词法分析，检查程序的token 流，剔除掉所有的变量与自定义的函数名，剩下的即为C 语言关键字所组成的字符串，把这些字符串作为关键字匹配的特征字符串；

（3）利用KMP 算法对源程序模式串和预设的主特征字符串进行匹配并记录匹配结果，最终计算出整体的相似度。

1.2 动态检测执行

基于动态检测的评分方法主要解决的问题包括：设置合理的测试用例，尽可能完整地覆盖代码的执行路径；配置系统程序的沙盒安全保护机制；检测数据结果的分析。动态检测的整体步骤如下：

（1）关键字匹配：使用KMP 算法对源程序与模板程序中的关键字进行匹配操作；

（2）预处理：读取系统配置文件、读取编程题目信息以及测试用例数据；

（3）编译：对程序进行编译并检查语法，以生成可执行程序；

（4）执行：运行程序，依次输入全部测试数据，监控代码的执行状态；

（5）测试：获取学生程序的执行结果，包括正常执行的输出结果或程序异常结束的结果，若正常执行并退出，则将程序的输出数据与模板的标准数据进行对比并评定分数。基于动态检测的自动评分模型如图1 所示。

图1 动态检测评分模型Fig.1 Dynamic detection scoring model

2 静态分析方案设计

通过对程序进行词法分析、语法分析等预处理操作，输出程序的中间转换形式——抽象语法树（Abstract Syntax Tree，AST）［3］，继而模拟人工评分的思路：

（1）首先在组建编程题库时对每道题目提供得分点，本文选取控制结构作为静态评分的关键因素；

（2）对抽象语法树进行标准化处理，以消除程序语义的多样性，减少答案模板的数量，然后根据AST 中结点的类型提取出对应的控制结构子树；

（3）利用基于结点权值的树编辑距离算法来匹配标准化后的源程序与模板程序的控制结构子树，并计算其相似度［4］；求解控制结构各个模块的得分值（模块的预设总分值乘以对应模块的相似度）；最后，综合各模块的评分结果求和并得出静态分析的最终评分结果。

2.1 程序标准化

抽象语法树作为一种数据载体，不仅包含了源程序对应结点的所有信息，还包括了结点之间的结构关系。针对抽象语法树进行标准化，包含两个部分：

（1）利用基于关键词Trie 树的GCC 抽象语法树消除冗余算法，对抽象语法树进行冗余优化处理［5］，冗余优化示意如图2 所示；

图2 冗余优化整体示意图Fig.2 Overall schematic of redundancy optimization

（2）通过对程序运用一系列标准化规则，在抽象语法树的基础上，将不同表现形式的程序语法树转换成统一的表现形式，这样不仅可以消除学生源程序代码的多样性、减少标准答案模板的数量，还能提高相似度匹配的准确率。

为了后续更好地实现程序控制结构的相似度匹配，本文在程序标准化环节主要对程序控制结构进行标准化转换。在C 语言中有3 种基本的控制结构：顺序结构、选择结构和循环结构。每一种控制结构都可能有多种代码书写形式，这为源程序和模板程序的匹配带来困难，所以需要对控制结构进行标准化。

2.1.1 选择结构的标准化

实现选择结构可采用if 语句或switch 语句，if语句对应的抽象语法树有如下结构特点：if 结点有3个孩子结点，从左至右依次排开，分别是条件表达式结点、执行语句结点和else 语句结点；而在switch 语句中，switch 结点则可能有多个孩子结点，switch 括号内的表达式结点在最左边，default 结点在最右边。

针对选择结构的两种不同形式的抽象语法树，首先转换为统一的语法树形式，再进行标准化处理，包括：删除得不到执行的分支、删除空分支、提取各分支中的公共表达式、合并选择结构、将各分支深层次的嵌套结构转换为多分支选择结构。标准语法树形式以及深层次嵌套结构转换如图3 所示。

图3 选择结构标准语法树以及深层次嵌套结构转换示意图Fig.3 The standard syntax tree of the selected structure and the conversion diagram of the deep nested structure

2.1.2 循环结构的标准化

实现循环结构可采用while 语句、for 语句和do…while 语句。相对while 语句，do…while 语句至少会执行一次循环体，本文在语法分析阶段对do…while 语句做了预处理，将其循环体拷贝一次后，再转换为while 语句。因此，只讨论对while 语句和for语句所对应的循环结构进行标准化。

针对上述两种循环语句所对应不同形式的抽象语法树，首先统一其表现形式，将循环语句的结点均表示为Loop结点，并对其分支结构进行统一的规范化处理和标准化转换，包括：重新排列各层循环的顺序、删除条件表达式恒为假的循环分支、将循环体中值不会发生改变的语句提取到循环体外等。

另外，for 语句需要进行额外的处理：将初始化表达式插入到Loop结点之前，条件表达式的位置保持不变，再将递增递减表达式放到循环体中。因为大多数条件表达式属于关系表达式，所以可对其进行适当的处理，如：i≤N↔i ＜N ＋1。

2.2 基于树编辑距离的控制结构子树匹配

控制结构子树主要包含选择结构子树（if、switch 语句）以及循环结构子树（while、for 语句），因此选取这两种控制结构作为主要得分点来进行相似度匹配。在求解树编辑距离时，需要让对应的整棵树进行分解，并生成一系列子树的集合，再去计算集合中每一棵子树与其对应模板子树的树编辑距离，递归地重复上述计算与分解步骤，直到集合中的子树不能再分解为止。

2.2.1 树编辑距离算法

树编辑距离指的是完成从有序树T1到有序树T2的树映射f（T1→T2）所需要进行的树编辑操作的最小代价。其中，树编辑操作包含树结点的插入、删除以及替换操作，并且每一个编辑操作都有相应的代价，用公式（3）表示：

其中，μ（f（T1→T2））是完成有序树之间的映射f（T1→T2）所需要的编辑操作的代价，而参数d（T1，T2）则用来衡量两棵树之间的异构程度。

如图4 所示，用虚线连接与编辑操作无关的树结点，同时参照各个考核点的重要程度来标注出对应结点的权值大小。因此，可以利用树编辑距离来衡量树之间的匹配相似度。编辑操作包括删除结点decl2、插入结点expr2，由树编辑距离的定义可知：d(T1，T2)＝2，并且当两棵树之间的树编辑距离越大，说明两棵树之间映射所需要的编辑操作越多，因而两棵树之间的匹配相似度越小。

图4 T1 →T2 的映射Fig.4 Mapping between T1 and T2

2.2.2 匹配子树并计算相似度

在实际考试中每道编程题所要考核的重点内容会有所不同，为了更好地完成特定的教学目标，本文在静态分析阶段对子树中的每个结点赋予了不同的权值以反映其对应考察点的难易性与重要程度。结点的权值越大，则代表该结点所对应考核的内容越重要或者难度越大。本文通过利用树中各结点所赋予的权值大小，来计算源程序与模板程序之间的匹配相似度。该算法描述见表1。

表1 算法描述Tab.1 Algorithm Description

根据算法得出加权树之间的编辑距离（即wEdist ＝M[m][n] ），同时，利用基于结点权值的树编辑距离公式（4）来求解源程序与模板程序之间的匹配相似度：

以图4 中的有序树映射f（T1→T2）为例，由上述算法可知，加权树T1与T2之间的树编辑距离为4，由公式（4）计算得到匹配相似度为0.74。

3 系统实验结果与分析

为测试本系统的有效性和准确率，请80 名学生使用本系统进行编程考核。系统模板试题库一共选取了10 道具有代表性的编程题目，每一位学生会随机抽取一道题目进行解答，每道编程题的分值为10分。使用了动态检测与静态分析相结合的自动评分方案，该方案所采用的评分标准见表2。

表2 编程题的评分标准Tab.2 Scoring criteria for programming questions

评分标准中首先进行关键字检测，若检测未通过则直接扣除4 分，若检测通过便动态执行源程序，执行期间若出现异常或不能正常运行，则扣除2 分。动态检测阶段完成后执行静态分析，结合控制结构匹配相似度进行综合评分。

为更好地对比自动评分与人工评分之间的差异，本文使用绝对误差与相对误差来衡量。

同时，每个试题编号所对应的学生抽取人数，见表3。

表3 各编程试题的抽取人数Tab.3 The number of students drawn for each program problem

对于第k个编程试题，Tk代表人工评分所得到的分值；Mk代表自动评分得到的分值；n表示抽取到第k个试题的学生人数。利用绝对误差Δ与相对误差δ的数学公式（5）进行计算，得出的误差统计数据，见表4。

表4 自动评分方案的误差统计Tab.4 Error statistics of automatic scoring scheme

根据表4 可知，自动评分方案符合人工评分的思路，并且误差值也均在合理的范围内，这说明自动评分方案具有较高的准确率，同时大大提高了评分的效率，具有很高的实用价值。

4 结束语

本文提出一种基于动态检测与静态分析相结合的评分方法，该方法已经实现并被集成到在线实验系统中。实验结果表明，本系统评分准确率较高，系统稳定高效，基本满足学生编程题的自动评分需求，达到预期效果。