基于源码动态分析的软件错误分析.docx

1、 毕业设计(论文)毕 业 设 计 （ 论 文 ）题 目 基于源码动态分析的软件错误分析专 业 计算机科学与技术毕业设计(论文)摘 要动态切片是一种重要的程序调试方法，由于只考虑程序的输入特定执行情况，程序中相关信息，因此，与静态切片相比，动态切片的结果会更加精确。目前，计算动态切片的方法比较多，比如；前向切片，后向切片，双向切片等。由于切片剔除了与程序执行无关的部分，所以当程序执行发生错误时，将错误语句的搜索空间压缩为切片序列，往往会节省大量的时间和尽量。目前在错误定位方面主要的研究内容是自动化错误定位，这类方法主要借助于良好的测试用例集，然后通过程序语句的覆盖信息计算出程序语句的可疑度，最后

2、根据可疑度的大小决定哪些语句应该检查。但是，仅仅通过程序的切片序列却忽略了程序本身的结构所包含的信息。所以在可疑度已经算出的基础上，再次利用程序中函数之间的耦合度，修正程序语句的可疑度。本文采用基于程序切片谱的错误定位方法计算语句的可疑度，在计算函数的耦合度时，首先设计了一个理论上可以使用的双向切片方法，以此得到程序间相互关联的变量。然后通过已有的算法计算出函数的耦合度，最后将耦合度与先前的怀疑度输入一个函数结合起来做为最终的怀疑度。关键词：动态切片；程序谱；可疑度；程序耦合度；双向切片毕业设计(论文)ABSTRACTDynamic slicing is an important method

3、 of program debugging，Because only the input specific implementation of the program and related information in the program is considered，therefore, compared with the static slicing, the result of the dynamic slicing is more accurate. At present, there are many methods to calculate the dynamic slicin

4、g, such as the forward slicing, the backward slicing, the bidirectional slicing, etc.Due to slice removing program implementation independent parts, so when program execution error occurred. The Error statement search space compression for serial slices, tending to save a lot of time. The positionin

5、g error in the main research content is automatic fault localization, this kind of method mainly by in good test case set, and then through a program statement coverage information calculated suspicious degree of program statements, finally, according to the suspicious degree determines which statem

6、ents should check。However, the structure of the program itself is ignored only through the programs slicing sequence. So suspicious degree should have been calculated, based on the coupling between the function of the program again, that is called the correction of the degree of the program statemen

7、t suspicious.The suspicious degree of fault location method based on program slicing spectrum calculation statement, are calculated as a function of coupling degree. Firstly, design the method of bidirectional slice a theory can be used, in order to get the program interrelated variables .Then, the

8、coupling degree of the function is calculated by the existing algorithm, and finally the degree of the coupling degree is combined with the previous degree of skepticism as the final degree of skepticism.keywords：dynamic slicing; Spectrum program; Suspicious degree; Coupling degree program; Bidirect

9、ional sliced毕业设计（论文）- 4 -第一章 程序切片技术1.1 程序切片技术的概述1.1.1 程序切片技术的背景程序切片技术是 M.Weiser 在他的 1979 年的博士论文中首次提出的一种程序分解技术。主要通过寻找程序内部的相关特性，从而分解程序，然后对分解所得的程序切片进行分析研究，以此达到对整个程序理解和认识的目的。后来在 1981 年和 1984 年，M.Weiser博士又发表了两篇论文对这种技术进行推广和完善。后来切片技术引起了研究者们广泛的关注，由于它起到了其他技术无可替代的作用，因此可以说是程序分解领域的一场大变革，无论在程序的分析和理解、调试还是测试和维护过程都

10、起到了巨大的作用，另外切片技术还在硬件描述语言和其他规约语言以及形式化模型等方面的分析有至关重要的作用，因此它的研究具有极其重要的理论和实际意义。程序切片主要通过寻找程序内部的相关特性，从而分解程序，然后对分解所得的程序切片进行分析研究，以此达到对整个程序理解和认识的目的。而动态程序切片主要是指在某个给定输入的条件下，源程序执行路径上所有对程序某条语句或兴趣点上的变量有影响的语句。程序切片的具体实现可以用 S（V，N ）的形式表示，其中 V 表示程序中的某一个变量或是变量的集合，N 表示在程序中的某一个位置（变量 V 所在的语句） 。S（V，N）的含义是“一个程序切片是由程序中的一些语句所组成

11、的集合，这些语句可能会影响到在程序的某个位置 N 处所定义或引用的变量或变量的集合 V 的状态” 。S（V，N）是程序切片最基本的形态，任何形式的程序切片都可以通过对这个标准进行扩展而得到。1.1.2 程序切片技术的发展阶段目前为止主要有以下几种方法：1）基于数据流的程序切片M.weiser 提出一种基于数据流方程的静态切片算法，他把数据流分析定义为对一个程序 CFG 的分析。这种方法通过迭代计算 CFG 中每个节点相关变量的集合来获得程序切片。给定切片准则 C,M.weiser 方法的计算步骤如下：1 进行第一次循环，计算直接相关变量和语句。2 进行迭代进行计算间接相关变量和相关间接语句。不

12、过他的程序切片属于静态切片的一种，但是由于历史的原因，他的方法只能解决简单的只包含三种基本结构的顺序切片问题，对模块化程序设计中出现的过程与过程调用等问题无能为力。2）基于程序依赖图（pdg）的程序切片程序 P 的 PDG 称为 Gp, Gp 的结点表示出现在程序 P 中的赋值语句和控制谓词。Gp 是多重图，两个结点之间不仅有多重边，而且有多类边。 Gp 中的边表示程序组件间的依赖，一条边表示控制依赖或数据依赖（流依赖） 。PDG 反映的是过程内的依赖关系。毕业设计（论文）- 5 -3）基于系统依赖图（SDG）的程序切片SDG 不仅要考虑过程内语句的相互依赖关系，而且还要考虑过程与过程之间的调

13、用关系，过程间参数的传递关系等。他是由一组过程间控制依赖边和流依赖边连接起来的过程依赖图（PrDG）组成。SDG 类似于 PDG，但它还包括表示由于调用而形成的调用语句、参数传递、可传递流依赖的顶点和边。SDG 反映的是过程内的依赖关系。1.1.3 程序切片技术的应用由于是程序切片，与程序有关，因此毫无疑问在软件的编码和调试阶段用处是最明显的。尤其在调试阶段，当出现错误时通过程序切片可以快速对程序中的错误进行定位，这样引起错误的代码就被限定在这个程序切片里，从而方便了程序员调试。在软件测试中主要用于回归测试，在软件开发过程中，当系统修改了一处或多处后需要对整个软件重新测试，以防止修改不会带来其

14、他模块的问题、一周此工作量是非常大的，而且也会消耗大量的人力物力。由于在回归测试时，软件只有小部分代码被修改，因此只要通过程序切片技术获得源程序中受到修改代码影响的所有其他代码，这样只要对这些受影响的代码进行测试。对于软件度量，可以利用软件体系结构的切片技术验证体系结构是否正确，从而保证按照这个体系结构设计出的软件是正确可靠的，同时在设计阶段利用模块间的切片技术也可以设计出高内聚低祸合的模块，从而为软件的重用性起到大的作用。此外，程序切片技术还应用于软件安全方面和软件测试方面。1.2 基本术语1.2.1 程序依赖图和静态切片程序中的每一条简单语句（如写语句、读语句、赋值语句等）程序依赖图中都有

15、一个节点与之对应，每一个控制谓词表达式（如 if-then-else，while-do 语句中的条件表达式等） ，也有一个节点与之对应，就不能用只用一个节点与之对应。依赖图有两种类型的有向边，即数据依赖边和控制依赖边。从节点 n 到节点 m 的数据依赖边表示节点 n 的直线直接依赖于节点 m 出的左值，并且在节点 m 与 n 之间不存在该值得重新定义。从节点 n到节点 m 的控制依赖边表示节点 n 的执行与否受到节点 m 的节制。图 3.2 是例子程序 1所对应的程序依赖图毕业设计（论文）- 6 -Figure 1.1 例子程序 1 Figure 1.2 程序 1 所对应的 PDG程序 P 的

16、一个与节点 n 和变量 v 相关的静态后向切片是由程序 P 中所有可能影响变量v 在节点 n 的值得语句和控制谓词构成的集合。具体步骤如下：（1）查找节点 n 处变量v 的所有可到达定义节点，然后以这些节点为起点变量程序依赖图，变量过程所访问到的节点就构成了所需的静态切片。例如，对语句 10 的变量 Y 切片的结果如图 3.2 所示。1.2.2 执行历史和动态切片准则执行历史是控制流图中的一个可执行路径，他是个动态概念，执行历史有程序执行时所经过的节点组成。和静态切片不同的是，EH 中包含的语句的顺序和程序中被执行的顺序相同。例如当输入 N=2 时，程序 2 的执行历史为 1,2,3,4,51

17、 ,61,71,81,52,62,72,82,53,9Figure 1.3 例子程序 21.3 动态切片1.3.1 动态切片方法 1毕业设计（论文）- 7 -基本步骤: (1) 根据程序建立程序依赖图（2）将被执行的语句在程序依赖图中标记出来(3) 从图中被标记的节点开始遍历，遍历所经过的节点构成的集合就是所需的 切片优缺点： 方法简单，但是可能会包含没有影响的多余语句1.3.2 动态切片方法 2基本步骤: (1) 根据程序建立程序依赖图（2）将程序执行时的依赖关系在程序依赖图中标记出来(3) 从图中被标记的节点开始遍历，但是仅仅沿着被标记的依赖边进行遍历，遍历所经过的节点构成的集合就是所需的

18、 切片优缺点： 对方法 1 是种改进，但是由于一条语句在执行的历史过程中可能出现多次，但是依赖图确不缺乏这种语句执行的不同。1.3.3 动态切片方法 3基本步骤: (1) 为执行历史中的语句的每一次出现创建一个节点，并且只对与这一次出现有依赖关系的那些语句添加依赖边构成一致新的依赖图(2) 从所需节点开始遍历，遍历所经过的节点构成的集合就是所需的 切片优缺点： 切片比较准确，但是所需的临时空间比较大Figure 1.4 例子程序 3 Figure 1.5 程序 3 的动态切片毕业设计（论文）- 8 -1.3.4 动态切片方法 4基本步骤: (1) 在执行历史中，如果该语句没有出现或者与前面节点

19、的依赖关系不同，才 为该语句创建节点，构成依赖图(2) 从所需节点开始遍历，遍历所经过的节点构成的集合就是所需的 切片优缺点：切片比较准确，所需的临时空间也小，但是建依赖图所需的时间复杂度比较大Figure 1.5 程序 3 的简化的动态切片小 结本章主要讨论了三种切片方法：静态切片，执行历史切片，以及动态切片，其中静态切片方法以及动态切片方法 1,2 是基于程序的依赖图，简单高效但不够准确，执行历史切片以及动态切片方法 3,4 是基于进程的执行历史所建立的依赖图，比较准确，但是在时间和空间的优越性无法兼得。虽然如此，但仍是最优秀的切片方法。毕业设计（论文）- 9 -第二章 频谱故障定位技术2

20、.1 频谱故障定位技术的研究2.1.1 频谱故障定位方法的基本思想如果程序试题被越多的失效测试用例覆盖，则改程序试题是故障的可能性就越高；如果程序实体被越多的正确测试用例覆盖，则该程序实体是故障的可能性就越低。2.1.2 基于风险评估函数的故障定位方法为了便于说明，我们对频谱故障定位采用了如下文所示的形式化描述：设程序 PG=s1,s2,sn包含 n 个程序实体，PGi （1i n）为第 i 个程序实体；测试用例集 TS=t1,t2,tm包含有 m 个测试用例，设 TSj（1jm）为 TS 的第 j 个测试用例。矩阵 RE 表示测试用例集 TS 在程序 PG 执行的测试结果， REj=p（1j

21、 m ）表示测试用例 TSj 执行结果为 pass，REj=f（1jm）表示测试用例 TSj 执行结果为 fail。矩阵 MS 表示测试用例 TS 在程序 PG 的特定方面的执行信息，执行剖面 MSi,j=1 表示TS 中第 j 个测试用例在程序执行过程中至少一次执行了 PG 中第 i 个程序实体，MSi ,j=01表示 TS 中第 j 个测试用例在程序执行过程中没有执行 PG 中第 i 个程序实体。向量 Ai=aief, aiep, ainf, ainp表示程序实体 si 的测试用例集 TS 在程序 PG 执行的频谱情况，矩阵 MA 中的第 i 行即表示 Ai。其中 aief, aiep, ainf, ainp 的定义如下：毕业设计（论文）- 10 -频谱故障定位技术基本元素之间关系：Figure 2.1 频谱故障定位技术基本元素之间关系目前常见的风险评估函数：