题目：基于数据链的故障定位和测试用例生成研究

有统计表明软件调试在软件开发过程中占据了大概70%的时间，故障定位和检查故障修复是软件调试中两个重要的任务。故障定位通常用来分析导致软件失效的责任代码，如何提高故障定位的效率是目前研究领域普遍关注的问题。验证故障修复情况旨在检验故障是否被修复或者是否引入新的故障，此时有可能需要补充新的测试用例，如何在此阶段生成具有针对性的测试用例也是目前关注的研究问题。

软件中存在的故障很多与数据流紧密相关，而数据流与变量有着密切的关系，因此在程序调试中需要分析变量的定义-使用关系和变量间的依赖关系，并跟踪程序运行时各种操作对变量值的影响，即变量操作状态的变化等基本信息。现有的故障定位方法都没有同时考虑这些基本信息。虽然变量定义-使用对(DU-Pairs)覆盖率和程序切片故障定位等方法也考虑到变量的变化情况，但是，基于变量定义-使用对的方法不考虑变量之间的依赖关系，因而难以对导致程序运行中计算结果错误的故障进行准确的定位；仅利用程序切片技术进行故障定位得到的疑似故障的语句集合没有排序，这使得在获得疑似语句集合之后，仍需要花费很多的时间去寻找真正的故障所在。

针对上述的分析，本文综合考虑了变量定义-使用对覆盖率方法和程序切片方法的长处，并且借鉴了人工程序调试中需要利用的变量信息，提出了一种用来描述程序运行时变量操作状态变化以及变量操作状态间依赖关系的模型，称作数据链模型。该模型通过引入变量的操作状态概念，用以描述变量的取值变化，即变量操作状态的转移，并在不同变量操作状态之间建立依赖关系来描述变量取值时的依赖。在此基础上，本文提出了基于数据链的故障定位方法，该方法通过分析变量自身操作状态的变化以及变量操作状态之间的依赖关系，寻找出一组按照疑似度排序的语句集合。还考虑到验证修复阶段可能需要补充新的测试用例的情况，本文还进一步研究了如何利用数据链来自动生成具有针对性的测试用例。

本文围绕基于数据链的故障定位问题展开研究，其主要的目标是提出基于数据链的故障定位方法 DCFL（Data Chain based Fault Location）和基于数据链的测试用例自动生成方法DCTG（Data Chain based Test Case Generation）。基于上述目标，本文完成了如下三个方面的研究工作：

1．提出了一种能够综合考虑变量操作状态变化以及变量操作状态间依赖关系的数据链模型，为了能够反应程序中变量的变化情况，将变量在程序执行中的每一次赋值看作是对其操作状态的一次改变。此外，变量之间可能还存在依赖关系，即变量的操作状态之间的引用关系。这两个方面是数据链模型中描述的核心内容。并且基于对程序运行时变量操作状态变化以及变量间依赖关系信息的采集和分析，给出了自动构建数据链模型的方法。

2． 针对数据链模型中变量操作状态变化以及变量操作状态之间依赖关系的不确定性特点，提出了一种概率数据链模型，利用概率数据链模型，提出了相应的故障定位方法。该方法通过计算变量操作状态在执行失败和执行成功中的条件概率，来对在执行失败中出现的变量操作状态可能存在故障的程度进行排序，从而生成对应的故障定位报告。

3．在测试用例生成方法方面，提出了一种基于数据链的测试用例生成方法。该方法在测试用例生成过程中利用故障相关的数据链信息，构造出能够覆盖故障修复过程中受到直接影响的程序片段，来帮助生成测试用例。

本文的主要研究成果均经过了相应的实验验证，其中所提出的基于数据链的故障定位方法的定位结果与基于定义-使用对、基于程序切片、基于概率依赖图和基于语句覆盖这四种典型的故障定位方法进行了对比，取得了更好的定位效果。本文所提出的基于数据链的测试用例生成方法，能够很好地指导修复故障后测试用例的补充生成。此外，本文还详细地描述了支持工具的实现，从而为后续的相关研究提供了一定的基础。