基于自然语言处理的在线考试系统的设计和开发文献综述

一、文献综述

（一）国内外研究现状

Weiser最早提出程序切片可以用于程序理解和软件调试之后[1]，研究人员发现动态切片[2]更适用于错误定位与理解。除此之外，早期的研究者也使用过基于变量变化情况的方法：他们试图创造两个相似的程序输入，一个可以导致程序成功执行而另一个会导致程序执行失败。他们假设相似的输入会导致相似的执行过程，通过观察一个变量在错误代码和正确代码中的变化情况得到两个变量值的序列，进而可以通过比较得到的多个序列来定位程序的错误位置。近年来，计算机性能的高速提升和网络通信费用的大幅度下降，使得搜集程序执行信息和操纵程序执行状态成为可能。自2002年以来，自动化错误定位技术逐渐成为软件工程界的研究热点，表1按照时间顺序，列出了部分典型的错误定位技术以及相关的研究机构和论文发表的会议或期刊，简要地描述了软件错误定位的技术研究历史[6]。

表1中列出的这些技术，大多通过(半)自动化开发人员日常调试时采用的策略，最终给出错误可能存在的位置。有的是通过类似二分查找的方式，缩小引发错误的条件[20]；有的寻找和给定的失败执行最相似的成功执行，然后比较找出不同；有的认为经常出现在失败执行中的程序实体更值得怀疑；有的观察程序谓词在成功执行和失败执行中的取值模式的异常；还有的修改程序运行时状态来寻找对测试执行结果有影响的谓词或语句等等。

（二）研究主要成果

按照使用和操纵的程序执行信息的不同，目前的错误定位方法可以划分为3类：基于行为特征对比的方法、基于程序状态修改的方法和基于程序依赖关系的方法。

1. 基于行为特性对比的方法

Harrold等人对此做了大量的实验[21]。实验结果表明，程序出现异常的行为特征未必意味着代码中存在缺陷，但是错误的程序运行往往会表现出异常的行为特征。

1. 基于语句或基本块

2003年，Renieres和Reiss提出使用相似的程序光谱来进行错误定位。NNQ(Nearest Neighbor Queries)法假设存在一个失败的执行和很多成功的执行，然后根据距离准则挑选出一个程序光谱和失败运行最相似的成功运行(即失败执行的最近邻居)，进而比较它们光谱的不同之处以分离软件错误。NNQ法认为那些出现在成功执行中的程序实体不应该被怀疑，与此不同，Jones和Harrold提出的Tarantula法认为只要是主要被失败用例执行的程序实体就值得怀疑，同时它也容忍出错的程序实体偶尔地被成功用例执行。他们使用常用的信息来辅助错误定位，包括每个测试用例的执行结果、程序实体(语句、分支或函数等)被每个测试用例覆盖的信息以及程序的源代码。对于程序实体e，它的怀疑度计算公式如下：

其中，failed(e)和passed(P)分别表示失败用例和通过用例执行程序实体e的个数，|T_f|和|T_p|表示测试组件中所有失败用例和通过用例的个数．e的怀疑度取值范围从0到1数值越大，出错的可能性越大，开发人员可以按照怀疑度从大到小的顺序审查源代码。

与上述方法不同，Hao等人提出应该考虑测试用例的相似性，并消除相似的测试用例对于定位结果的影响．他们提出一种名为SAFL(Similarity—Aware Fault Localization)的方法．覆盖信息和测试结果使用执行矩阵E=(e_ij)来表示．其中e_ij，表示第j条语句被第i个测试用例覆盖的信息，e_{i（m 1）}表示第i个测试用例的状态信息．SAFL方法认为每个语句块对于测试用例状态的贡献是相同的．根据执行矩阵，可得到量化矩阵F=( f_ij)，其中，表示第j条语句对第i个测试用例的状态的贡献度．根据模糊集理论，第j条语句的怀疑度通过其在失败用例和所有用例中的贡献度的比值确定，即

本质上，SAFL方法计算的是每个语句块属于失败用例集合的隶属度和属于所有用例集合的隶属度的比值，比值越大，认为其出错的可能性就越大．

1. 基于谓词

与Tarantula面向内部测试(in-house testing)不同，Liblit和他的同事提出了CBI(Cooperative Bug Isolation)技术用于定位已部署软件(deployed software)中的错误。他们的基本想法是搜集用户在使用软件时产生的执行信息，进而通过分析这些数据将软件缺陷分离出来。与现有的系统通常只搜集崩溃时的报告不同，程序执行信息更好地刻画了软件实际使用时的场景。然而搜集执行信息肯定会对用户使用的软件性能有一定的影响。为了解决这个问题，Liblit等人通过在源代码上的变换，使用稀疏的随机抽样，较好地控制了客户端的性能并返回执行时的摘要信息。他们的抽样方法如下：程序中任何语句的集合都可以被认为是一个插桩点，进而被设计为可供采样的而不是无条件运行的。即每次程序执行到插桩点时，随机决定是否要执行插桩。为了捕获可以辅助缺陷定位的程序行为，Liblit等人对于C程序采用了分支、返回值和标量对3种插桩方案。为了识别和程序故障相关的谓词，对于一个谓词P，令F(P)和S(P)分别表示P被观察到的在失败和成功执行中取值为真的次数，Fo(P)和S。(P)分别表示P被观察到的在失败和成功执行中出现的次数，则P的怀疑度被计算如下：

这个计算公式本质是求一个调和平均数，用以有效地平衡两方面的因素：谓词的特异性(specificity)和谓词的灵敏性(sensitivity)。和信息抽取中查准率(precision)及查全率(recal1)的概念类似，特异性是指在成功执行中谓词没有错误地预测存在故障，而灵敏性是指在失败执行中谓词被观察到的比例。

1. 基于方法

对于面向对象的语言，Dallmeier等人认为在失败执行中调用了与通过执行中不同的方法的类更值得怀疑．他们提出了基于方法调用序列的AMPIE技术，认为只出现在通过执行或失败执行中的方法调用子序列应该被怀疑。与在通过和失败执行中都出现的子序列相比，这些子序列被分配较大的怀疑度值．遗失或增添的子序列都值得怀疑，因为它们都可能引发程序故障。

给定一个类C以及相关的一个失败执行c，和一个通过执行C．对于给定长度k，两个执行产生的子序列集分别为S(c_f)和S(c_p)．对于没有同时出现在两个执行中的子序列s，其怀疑度w(s)赋值为1，否则赋值为0．则类C的怀疑度可以用它包含的子序列的怀疑度的平均值来计算，即

AMPIE技术也可以使用多组通过执行来得到子序列集S(c)并用于计算怀疑度值。进一步的研究表明，子序列长度k的取值会影响定位结果的灵敏性，k通常取值在5～10之间较好。

与Ample技术不同，Yilmaz等人提出使用时间光谱作为程序执行特征的抽象。时间光谱是程序实体(比如方法、函数)运行的时间特征信息，通常用于程序性能的评价和优化。他们提出一种叫做TwT(Time Will Tel1)的方法，首先收集成功执行和失败执行的时问光谱，接着基于成功执行的时间光谱建立程序行为模型，然后使用这个模型来识别失败执行和成功执行的偏离程度。比如，一种方法如果在失败执行中花费了比通过执行值得怀疑的较长或较短的时间，那么这种方法可能就和程序错误相关。TwT技术选取的是方法的执行时间作为时间光谱，因为方法提供了合适的粒度水平和功能的界限。对每个方法，基于通过执行的时间光谱创建一个高斯混合模型。这是个多维概率密度模型，首先识别出数据聚成的类，然后对每个类使用高斯分布建模。对于一个给定的失败执行，以它和聚类中心点的偏离程度作为怀疑度的得分，距离越远，怀疑度越大。

1. 基于程序状态修改的方法

基于程序状态修改的方法通常在程序执行时，获得并修改程序的状态，然后观察修改后的测试结果(成功／失败)，进而找出对测试结果有影响的关键谓词或语句。由于程序运行时的状态有多种可能，这类方法往往需要采用一些简化策略，提高定位的效率。

Delta Debugging方法是由Zeller提出的一种能自动缩小程序的成功运行过程和失败运行过程之间区别的技术。在实现层面，它采用分治思想，把软件配置(测试输入、源程序等)变动的集合进行划分，然后分别进行测试，结果可以为通过、失败和无解。然后递归地把导致失败配置的集合并入结果为通过配置的集合。通过逐渐减小两个集合之间的差异，最终确认成功配置和失败配置差别的一个最小子集。首先，通过得到程序所有变量以及它们的值构成的集合，产生程序状态图。进而，使用计算公共子图的算法来识别成功与失败程序状态之间的差异。最后，将差异应用到程序状态，找到导致故障的变量，并跟踪这些变量的值，一直到产生错误的语句。识别对运行时的程序状态做哪些修改可以使得失败执行变成成功执行是一种通用而且有效的自动化调试方法。然而由于程序状态的数目极其巨大，漫无目的搜索所有可能的程序状态的变化是不现实的。Zhang等人的研究表明，在运行时强制对一个谓词改变取值结果并因此改变程序的控制流，不仅代价较低，而且往往可以使一次失败执行变成成功执行。通过检查被切换的谓词，也就是关键谓词，可以识别故障的根源。由于一个谓词的取值只能有两种可能，因此需要修改的状态数要远小于所有可能的程序状态数。实验结果显示这种方法既实用又有效。进一步的研究表明关于关键谓词的双向的动态切片可以有效地捕捉出错的代码。改变分支的取值结果是改变运行时变量的值的一种特殊情形。Jeffrey等人提出了Value Replacement方法：首先尝试改变运行时变量的值得到成功用例，进而将这种信息用于错误定位。具体地，首先寻找感兴趣的变量映射对IVMP(Interesting Value Mapping Pair)，然后对包含IVMP的语句使用Tarantula公式计算怀疑度值并进行排序。IVMP由一个变量的原始值和替换值组成，并且将变量更改为替换值后可以将一次失败执行变成通过执行，给定一次失败运行，寻找IVMP的方法是直接的：一次只考虑一条在失败运行中执行的语句，然后将使用的值替换成另一个，并观察是否会产生正确结果。为了有效地获得IVMP，仅考虑了4种类型的值作为替换值。实验表明，Value Replacement方法可以有效地定位出错语句或和出错语句存在直接依赖关系的语句。

1. 基于程序依赖关系的方法

基于程序依赖关系的方法侧重于使用程序的动态依赖关系给出值得怀疑的语句的集合，这个集合除了包含错误语句外，还提供了一个供程序员理解的调试上下文。但通常这类集合也会包含一些冗余的语句，需要使用一些技术来化简集合。

程序切片最早是由Weiser提出，用于描述影响程序某个执行点上特定变量的语句集合。后来的研究者通过考虑不同的依赖关系，以解决错误定位中的遇到的各种问题。Zhang等人，从动态角度提出隐式依赖(implicit dependence)的概念，它只会将已经观测到的发生在谓词和变量使用上的依赖关系加入切片中。Zhang等人进一步使用一种需求驱动的策略来减小探测隐式依赖的开销。实验表明，在仅增加一小部分的检查和很少的隐式依赖的情况下，就可以有效地捕捉遗漏语句这种类型的错误。为了减小动态切片的规模，研究者提出了许多种化简策略。Gupta等人整合了Delta Debugging技术以及前、后向切片的优势用于缩小搜索出错代码的范围。他们首先使用Delta Debugging技术来识别一个最小化的故障相关的输入，然后基于这个输入计算动态前向切片并与以错误输出为准则产生的动态后向切片取交集，作为引发故障的砍片(chop)。实验表明，引发故障的砍片和动态切片比，规模有了极大的减小同时并未显著降低定位错误代码的能力。Zhang等人观察到失败执行中出现的语句也有可能卷入到成功执行中。因此他们使用值的概要分析文件(value profile)来计算每条可执行语句的信赖度值，数值越大表明语句产生正确值的概率越大。进一步的实验表明，给定程序故障的一个失败运行，通过只剪除信赖度值为1的语句就可以有效地缩减动态切片的规模，同时将出错语句保留在切片内。此外，研究发现以信赖度值递增的方式检查语句是一个有效的降低错误定位成本的策略。

Baah等人扩展了程序依赖图，通过测试用例的执行信息估计节点间的统计依赖，建立了概率程序依赖图PPDG(Probabilistic Program Dependence Graph)。它基于概率图模型的框架，首先产生程序依赖图，然后得到标记了子节点和父亲节点之间条件概率的变换程序依赖图。同时，插桩源程序得到测试用例的执行信息。通过学习执行信息中的数据，最终得到PPDG。PPDG可以有多种应用，包括错误定位和错误理解。在用于错误定位时，首先使用PPDG分析一次失败执行的信息，然后对PPDG上的节点按照怀疑度进行排序。一个节点的条件概率值被认为是它的怀疑度，基于其父节点的值计算得到，条件概率值越低，怀疑度越高。由于PPDG直观上显示了失败执行和成功执行的不同，并提供了相关的上下文信息，因此可以用于辅助理解为什么某个特定语句是值得怀疑的。与PPDG学习的是程序中每个语句的依赖关系的分布不同，Feng和Gupta为每种指令类型建立了通用模型。给定一组程序的执行轨迹，并包括至少一个成功执行和至少一个失败执行，可以基于动态依赖图建立基于贝叶斯网络的错误流图(Error Flow Graph)和通用的概率模型。然后使用标准的推理算法从叶节点沿着错误流后向追溯寻找出错可能性最大的可执行语句。实验表明，即使只使用很少的成功执行，错误流图依然可以有效地定位错误。

（三）发展趋势

一、测试组件的影响

测试组件(test suite)的组成会对错误定位技术的有效性产生影响。当前的错误定位技术通常假设测试用例集合满足测试充分性准则，足以满足错误定位的需要。然而，这个假设没有被实验验证过又缺乏直观的考虑。事实上，减少测试工作量意味着产生一个满足准则的最小测试用例集。然而，错误定位技术又需要尽可能多的测试用例的执行信息。为了解决这个两难问题，Baudry等人通过分析用于有效错误定位时所需的信息类型，识别出动态基本对于定位算法准确性的影响，并基于动态基本块，提出了用于诊断的测试(Test-For-Diagnosis，TFD)准则。因此，减少测试用例数和提高错误定位有效性的两难问题，可以通过挑选专门用于定位的测试用例子集得到部分的解决。Yu等人实验研究了测试组件的缩减对定位有效性的影响。结果表明错误定位技术的有效性取决于所使用的缩减策略。此外，Jiang等人还研究了测试组件的优先级技术(test case prioritization)对基于行为特征对比的定位技术有效性的影响。

二、多个缺陷的定位

错误定位技术通常假设出错程序中只包含一个缺陷，而实际情况并非如此。多个缺陷的存在可能从两方面影响错误定位技术的有效性：一是当程序出错时，缺陷的数目通常是未知的；二是某些缺陷可能会掩盖或混淆其它缺陷。近年来，研究者对如何定位包含多个缺陷的错误程序进行了研究。Jones等人提出了并行调试的模型，通过自动化的产生面向单个错误的专门的测试组件，为多个开发人员同时调试包含多重缺陷的程序提供了一种途径。与Jones等人仅使用程序特征行为的信息不同，Abreu等人提出了一种包含逻辑推理的混合框架。他们既使用了程序执行的特征信息，又使用贝叶斯推理来推断存在多个缺陷时值得怀疑的程序实体以及它们的可疑度的大小。使用贝叶斯推理的一个特性是它可 以很好地解释多个缺陷为何间歇的出现而导致程序出错。

（四）存在的问题

自动化错误定位技术在过去十年间取得了长足的进步，但是仍有很多问题需要研究，例如缺乏用户研究来理解开发者是如何调试的；现有的评测标准数据集合不能完全反映现代语言中缺陷的存在和表现情况；错误定位技术不能很好地与开发环境相结合供开发者使用。同时，测试组件的影响、多重缺陷的定位、定位结果的理解以及错误修复的建议将是进行扩展的热点方向。对这些问题的深入研究，将帮助开发者更快地开发高质量的软件。

二、查阅中外文献资料目录

1. M. Weiser, “Program Slicing [C],” IEEE Transactions on Software Engineering, Vol. 16, No. 5, 1984,pp. 498-509．
2. Korel B , Laski J . Dynamic program slicing[J]. Information Processing Letters, 1988, 29(3):155-163.
3. Demillo R A, Pan H, Spafford E H. Critical slicing for software fault localization[J]. Acm Sigsoft Software Engineering Notes, 1996, 21(3):121-134.
4. Agrawal H, Horgan J R. Dynamic program slicing[J]. Acm Sigplan Notices, 1990, 25(6):246-256.
5. Tibor Gyimoacute;thy. An efficient relevant slicing method for debugging[C]// European Software Engineering Conference Held Jointly with the Acm Sigsoft International Symposium on Foundations of Software Engineering. 1999.
6. 虞凯, 林梦香. 自动化软件错误定位技术研究进展[J]. 计算机学报, 2011, 34(8):1411-1422.
7. 王克朝, 王甜甜, 苏小红, et al. 软件错误自动定位关键科学问题及研究进展[J]. 计算机学报, 2015(11):2262-2278.
8. Schleimer S, Wilkerson D S, Aiken A. Winnowing: local algorithms for document fingerprinting[C]//Proceedings of the 2003 ACM SIGMOD international conference on Management of data. ACM, 2003: 76-85.
9. Navarro, Gonzalo. A guided tour to approximate string matching. ACM Computing Surveys. 1 March 2001, 33 (1): 31–88 [19 March 2015].
10. 周汉平. Levenshtein 距离在编程题自动评阅中的应用研究[J]. 计算机应用与软件, 2011,28(5):209-212.
11. Allen F E. Control flow analysis[J]. Acm Sigplan Notices, 1970, 5(7):1-19.
12. 张志祥, 李庆华, 罗建明. 改进的基于分解的子图同构算法[J]. 计算机科学, 2006, 33(1):260-263.
13. Cook, S. A. 'The complexity of theorem-proving procedures', Proc. 3rd ACM Symposium on Theory of Computing, pp. 151–158, CiteSeerX 10.1.1.406.395
14. Ullmann, Julian R. 'An algorithm for subgraph isomorphism', Journal of the ACM, 23 (1): 31–42, CiteSeerX 10.1.1.361.7741, doi:10.1145/321921.321925
15. Cordella, Luigi P. 'A (sub) graph isomorphism algorithm for matching large graphs', IEEE Transactions on Pattern Analysis and Machine Intelligence, 26 (10): 1367–1372, doi:10.1109/tpami.2004.75
16. Bonnici, V.; Giugno, R. 'A subgraph isomorphism algorithm and its application to biochemical data', BMC Bioinformatics, 14(Suppl7) (13): S13, doi:10.1186/1471-2105-14-s7-s13, PMC 3633016
17. 赵长海, 晏海华, 金茂忠. 基于编译优化和反汇编的程序相似性检测方法[J]. 北京航空航天大学学报, 2008, 34(6):711-715.
18. Oliphant T E. Python for Scientific Computing[J]. Computing in Science amp; Engineering, 2007, 9(3):10-
19. Giacomo M D. MySQL: Lessons Learned on a Digital Library[J]. IEEE Software, 2005, 22(3):10-13.
20. Cleve H，Zeller A. Locating causes of program failures／／Proceedings of the 27th International Conference on Software Engineering(ICSErsquo;05)．St．Louis，M0，USA，2005：342—35]
21. Harrold M J，Rothermel G，Sayre K，Wu R，Yi L．Anampirical investigation of thee lationship between spectra differences and regression faults．Software Testing Verification and Reliability，2000，10(3)：171-194

资料编号：[596141]

一、文献综述

（一）国内外研究现状

Weiser最早提出程序切片可以用于程序理解和软件调试之后[1]，研究人员发现动态切片[2]更适用于错误定位与理解。除此之外，早期的研究者也使用过基于变量变化情况的方法：他们试图创造两个相似的程序输入，一个可以导致程序成功执行而另一个会导致程序执行失败。他们假设相似的输入会导致相似的执行过程，通过观察一个变量在错误代码和正确代码中的变化情况得到两个变量值的序列，进而可以通过比较得到的多个序列来定位程序的错误位置。近年来，计算机性能的高速提升和网络通信费用的大幅度下降，使得搜集程序执行信息和操纵程序执行状态成为可能。自2002年以来，自动化错误定位技术逐渐成为软件工程界的研究热点，表1按照时间顺序，列出了部分典型的错误定位技术以及相关的研究机构和论文发表的会议或期刊，简要地描述了软件错误定位的技术研究历史[6]。

您可能感兴趣的文章

• 基于BP神经网络的车牌识别及应用文献综述
• 基于物联网技术的家用电力管理系统-数据采集子系统文献综述
• 基于Android的电子竞价系统的设计与实现文献综述
• 基于Android的校园导航系统开发文献综述
• 基于web的医院药品库存管理系统设计与实现文献综述
• 基于深度卷积网络学习的人脸表情识别研究文献综述
• 学校在线二手交易平台开发文献综述
• 基于B/S架构的电子商城系统文献综述
• 基于Android的南信大食堂意见反馈系统的设计与实现文献综述
• 塔吊脚手架网设计与开发（PC web端）文献综述