一种基于修改影响分析的回归测试用例生成方法

摘要

本发明提出了一种基于修改影响分析的回归测试用例生成方法。首先对程序建模构造出源代码的中间表示，理解源代码中各元素之间的依赖关系，辅助程序理解；然后对程序的修改信息，利用特征定位技术识别修改点在源代码中对应的修改位置，并将该位置与源代码的中间表示一一对应起来从而得到修改集；在源代码的中间表示和修改集的基础之上，通过修改影响分析技术计算得到影响集；进而利用修改集和影响集生成回归测试用例的判定表；最后利用判定表生成测试路径集，并将测试路径集约简，将测试路径中的输入作为测试用例，最终得到一个能充分覆盖修改给程序带来的影响的测试用例集合。

说明书

技术领域

本发明提出了一种新型的回归测试用例生成方法，主要是利用修改影响分析 评估软件修改所带来的影响进行回归测试用例的生成，属于软件测试中回归测试 用例生成领域。

背景技术

软件系统为了满足人们的需求、性能的改进、功能的增强或者处理系统中发 现的故障等等，都可能需要对系统进行相应的修改。在现代软件系统的生命周期 内，软件缺陷修复，功能增强，性能改进，需求增加，运行环境改变等均要求软 件系统具有较强的演化能力，从而要求软件工程人员能够快速适应改变，减少软 件维护的代价。软件维护活动的核心是进行软件修改。由于修改肯定会对软件的 其他部分造成一些潜在影响，从而带来软件的不一致。所以在对软件进行修改之 后，需要对软件系统进行再测试以保证修改之后的软件系统仍然是安全的，这个 过程就是回归测试。

在对软件实施一系列的修改过程中，可以得到此次软件维护活动的修改集合。在 修改过程中，一些修改又可能给系统带来新的影响和波动，这就需要对这些修改 能传播到的范围进行再次检查，确认是否需要继续实施修改或者进行二次修改。 这样，修改对软件系统影响范围内的内容就构成了此次修改所带来的影响集合， 这个过程就是修改影响分析。为了验证修改之后软件是否满足一致性和正确性， 需要对软件系统进行再测试，也就是回归测试。在这个过程中，首先需要产生回 归测试用例集。测试用例集需要满足的基本条件是：测试用例在回归测试的时候 能够覆盖软件修改的部分，同时也需要覆盖修改对软件造成影响的部分。这样， 回归测试才能够较充分地验证修改后的软件系统的一致性和正确性。为了便于对 软件进行修改影响分析，需要将源代码抽象成一定层次的抽象模型，提取源代码 的基本信息构造方法调用图是对程序建模常用的方法。方法调用图能够有效地表 示程序控制流关系，且抽象粒度适中、便于程序分析和软件工程人员的理解。 修改影响分析可以用在软件维护过程中修改方案的评估和软件实施修改后的影 响传播分析，本发明主要利用修改影响分析对软件修改带来的影响进行评估，然 后利用修改影响分析的结果进行回归测试用例生成，使得生成的回归测试用例集 合能够覆盖修改所带来的影响范围，从而验证修改后的软件的正确性和一致性。

发明内容

本发明的目的在于提出了一种基于修改影响分析的回归测试用例生成方法， 该方法利用修改影响分析计算得到影响集并根据测试路径覆盖规则高效地生成 测试用例，用尽量少的测试用例覆盖尽量多的修改影响范围。

实现上述目的，本发明采用技术方案如下：一种基于修改影响分析的回归测 试用例生成方法，包括如下步骤：

1）将源代码转换成方法调用图，通过特征定位将程序中的修改信息映射到 方法调用图中的对应元素，映射的元素组成的修改集将作为修改影响分析的输 入；

2）在方法调用图中进行修改影响分析，得到影响集；

3）利用修改集和影响集构造判定表，判定表的定义为TS={□|□∈CS×IS}， 其中CS为修改集、IS为影响集，□为CS和IS笛卡尔积中的元素；修改集和影 响集中的元素都是基于方法的，故判定表中的每一项表示了影响集中的方法是否 受到了被修改的方法的影响；

4）利用判定表生成测试路径集合，方法如下：

在方法调用图中选取CS(j)和IS(k)间的可达路径，构造测试路径集合 Test-Path-Set，测试路径集合是由CS(j)和IS(k)之间所有可达路径的并集构 成，若无法找到判定表中第i行CS(j)和IS(k)之间的可达路径，那么将判定表 该行删除；其中，对于判定表中的第i行，基本覆盖条件TS(i)={(CS(j),IS(k)) 1≤j≤|CS|,1≤k≤|IS|}，其中CS(j)为判定表第i行对应的修改集中的元 素，IS(k)为判定表第i行对应的影响集中的元素；

5）若测试路径集合中的路径的第一个元素在方法调用图中的出度为1或0， 且该路径是其他路径的子路径，即该路径包含在其他路径中，那么就将该路径从 测试路径集合中删除，从而得到测试路径约简后的集合；

6）利用测试路径约简集合生成测试用例：

6.1）对于某一测试路径test-path={v₀,v₁,v₂，..v_k}，其中test-path为方法 集合，对该测试路径的每个方法单独进行测试，得到该方法的输入域划分和对应 的输出域{input(v_i),output(v_i)}(0≤i≤k)；由于v_i+1的输入域和v_i的输出域相 关联，那么由v_i+1的输入域和v_i的输出域关联分析逆推得到v_i的输入域，依次逆 推就可以得到v₀的输出域；

6.2）以方法v₀的输入作为测试用例就能对测试路径 test-path={v₀,v₁,v₂,..v_k}进行覆盖测试；

最后，对每条测试路径中的第一个方法按步骤6.1）与步骤6.2）的方法产 生测试输入，就得到了测试用例集。

有益效果：本发明提出了一种基于修改影响分析的回归测试用例生成方法， 在方法层次上进行修改影响分析，并利用路径覆盖判定生成测试用例集，主要有 以下一些优点：

（1）基于方法层次的修改影响分析能有效地表示程序的修改信息和程序受到 潜在影响的部分。在计算影响集的时候，考虑了多处修改的关联关系，这使得影 响集的结果更加精确；

（2）利用修改影响分析过程中的修改集和影响集生成的判定表有效地表示了 回归测试用例生成的基本覆盖条件。在测试用例生成的过程中，判定表使得测试 用例生成简单、高效；

（3）利用判定表生成测试路径集合，便于在方法层次上进行回归测试，同时 也使得测试用例生成更加便捷。测试路径集合完全覆盖了受到修改影响的方法， 使得测试能够更加充分。

附图说明：

图1是基于修改影响分析的回归测试用例生成框架。

图2是基于修改影响分析的回归测试用例生成的一般过程。

图3是修改影响分析法的一般过程。

图4是利用修改影响分析的结果构造判定表生成测试用例的过程示意图。

图5是本发明实施例中程序的方法调用图示例。

图6是本发明实施例中程序修改操作示例。

具体实施方式：

下面结合附图对本发明的技术方案进行详细说明。

修改影响分析主要的任务是将修改后的程序和原程序进行比较得到修改信 息，其中主要包括源代码的添加、删除、替换等操作，然后对原程序进行影响分 析并计算得到程序受影响的部分。在回归测试阶段，需要重新生成一些测试用例 来覆盖程序修改后功能更改或新增加特性的部分，同时也应该覆盖原程序中受到 影响的部分，使得修改后的程序和原程序的功能和行为能够保持一致。

本发明主要利用修改影响分析的结果生成判定表，并利用判定表来寻找最优 覆盖路径来生成测试用例，使得回归测试用例生成简单高效。

图1给出了基于修改影响分析的回归测试用例生成的一般过程示意图。这里 的回归测试用例生成主要由两部分组成：修改影响分析和测试路径覆盖分析。修 改影响分析是根据原程序修改点分析程序中受到修改影响的部分。在程序修改信 息不知的情况下，通常将原程序和修改后的程序进行比较，利用语句或控制流等 进行差异分析。在本发明中，程序修改信息通过软件特征定位方法获得，在实际 软件维护中，修改信息也可以通过版本控制等手段获知。测试路径覆盖分析考虑 如何生成测试用例将程序修改点及其受到影响部分进行覆盖。这里，如果我们识 别出的程序修改信息是方法，那么就要对相应的方法进行覆盖分析，才能得到需 要重新运行的测试用例。

图4给出了利用修改影响分析后的结果选取测试路径进行测试路径覆盖分 析的过程示意图。

结合图2中的回归测试用例生成流程，下面对流程中的步骤给予具体的说 明。

1）通过特征定位技术将程序的修改点定位到程序的方法中。 对程序源代码来讲，一般不利于软件开发人员理解和分析。所以需要先对源代码 进行转换并建模成人们易于理解的模型，常见的有类与方法之间的依赖图或者方 法调用图模型。本发明在修改影响分析中使用的模型是方法调用图。方法调用图 能清楚地描述程序的控制转移流程，以及方法之间的控制依赖关系，便于理解和 分析程序。特征定位应用到修改影响分析中就是将程序的修改点映射到模型中的 元素上，这样就便于后面要进行的修改影响分析。在本发明中，由于所使用的抽 象模型为方法调用图，所以将程序的修改信息映射到方法中得到的方法集合即为 程序的修改集（Change Set,CS）。

2）利用修改影响分析技术计算程序受到修改影响的部分。 修改影响分析的目的是分析程序受到修改影响的程度。附图3是修改影响分析的 一般过程，给出程序的修改集，通过修改影响分析得到了程序潜在受到影响的部 分也就是影响集（Impact Set,IS）。本发明使用的修改影响分析技术是基于方 法调用图的，修改影响分析的输入和输出均是方法集合。修改集中的元素可以很 方便的标记到方法调用图中，通过影响分析算法在调用图中进行向上可达遍历得 到的方法集合就是影响集。

3）利用第1）和第2）步中得到修改集和影响集构造判定表。 影响集（IS）是修改影响分析在修改集（CS）的基础上计算得到的。判定表的定 义为TS={□|□∈CS×IS}。判定表中包括了修改集中每个修改元素对影响集中每 个受影响元素的影响关系。由于修改集和影响集中的元素都是基于方法粒度的， 故判定表中的每一项表示了影响集中的方法是否受到了被修改的方法的影响。

4）利用判定表生成测试路径集合，对程序受到修改影响的内容进行覆盖判定。 判定表中的每一行为一个测试用例基本覆盖条件，代表一个测试用例能够覆盖最 少方法的情况，即该测试用例至少覆盖一个被修改的方法和它所能影响的一个方 法。

在下面实施例中的表1是一个判定表的例子。

对判定表中的第i行，基本覆盖条件TS(i)={(CS(j),IS(k))|1≤j≤|CS|, 1≤k≤|IS|}，其中CS为修改集，CS(j)为判定表第i行对应的修改集中的元 素，IS为影响集，IS(k)为判定表第i行对应的影响集中的元素。在方法调用图 中选取CS(j)和IS(k)间的可达路径，构造测试路径集合Test-Path-Set。测试 路径集合时由CS(j)和IS(k)之间所有可达路径的并集构成。若无法找到判定表 中第i行CS(j)和IS(k)之间的可达路径，那么需要将判定表该行删除。利用判 定表生成测试路径，有一定的顺序，首先需要先考虑修改集中修改操作为“修改” 的元素，然后是修改操作为“增加”的元素，最后是修改操作为“删除”的元素， 因为一个方法删除后，就不会再对该方法进行测试了。

5）删除测试路径集合中的冗余测试路径。

由于许多方法都被包含在测试路径集合Test-Path-Set中的多条测试路径 中，对于测试路径集合中的路径的第一个元素v₀，若元素v₀在调用图中的出度 为1或0，且该路径是其他路径的子路径，即该路径包含在其他路径中，那么就 将该路径从测试路径集合中删除。

6）生成测试用例集合。

对于某一测试路径test-path={v₀,v₁,v₂，..v_k}，其中v₀∈IS，v_k∈CS。在单元测 试的时候，由于对每个方法单独进行了测试，知道了该方法的输入域划分和对应 的输出域{input(v_i),output(v_i)}(0≤i≤k)。v_i+1的输入域和v_i的输出域相关联， 由v_i+1的输入域和v_i的输出域关联分析逆推得到v_i的输入域，依次逆推就可以得 到v₀的输出域。这样，以方法v0的输入作为测试用例就能对测试路径 {v₀,v₁,v₂,..v_k}进行覆盖测试。

对每条测试路径中的第一个方法按上面所述的步骤产生测试输入，就得到了 测试用例集。其中概念测试用例集TestSuit={t|t∈input(v₀)∧v₀∈test-path∧ test-path∈Test-Path-Set}。

实施例：

为了方便描述，我们假定有如下简化的应用实例：

假定程序P中有13个方法，分别是{M1,M2,M3,M4,M5,M6,M7,M8,M9, M10,M11,M12,M13}。程序P的方法调用图见附图5。

当对程序实施修改后，通过特征定位将每个修改操作定位到方法中得到修改集 Change Set={M2,M3,M14}，其中包括了方法的修改、删除和增加。本例中方法 M2被修改，方法M3被删除，添加了方法M14，修改后的方法调用图见附图6。 通过修改影响分析技术（已公知技术不进一步描述）计算得到影响集Impact  Set={M1,M4,M5,M6,M7,M11,M13}。

现在利用修改集和影响集生成如下的判定表：

表1：程序P的判定表

下面，先从判定表中依次取基本测试覆盖条件，再从方法调用图中获得测试路径 集合。

1）TS(1)={M2,M1}

M2是M1的祖先，添加M2到M1的路径

Test-Path-Set={{M2,M1}}

2）TS(2)={M2,M4}

M4是M2的祖先，添加M4到M2的路径

Test-Path-Set={{M2,M1},{M4,M2}}

3）TS(3)={M2,M5}

M5是M2的祖先，添加M5到M2的路径

Test-Path-Set={{M2,M1},{M4,M2},{M5,M4,M2}}

4）TS(4)={M2,M6}

M6不是M2的祖先并且没有从M6到M2的路径，故Test-Path-Set保持不变。

Test-Path-Set={{M2,M1},{M4,M2},{M5,M4,M2}}

5）TS(5)={M2,M7}

M7是M2的祖先，添加M7到M2的路径

Test-Path-Set={{M2,M1},{M4,M2},{M5,M4,M2},{M7,M5,M4,M2}}

6）TS(6)={M2,M11}

M11是M2的祖先，添加M11到M2的路径

Test-Path-Set={{M2,M1},{M4,M2},{M5,M4,M2},{M7,M5,M4,M2},{M11,M7, M5,M4,M2}}

7）TS(7)={M2,M13}

M13是M2的祖先，添加M13到M2的路径

Test-Path-Set={{M2,M1},{M4,M2},{M5,M4,M2},{M7,M5,M4,M2},{M11,M7, M5,M4,M2},{M13,M7,M5,M4,M2},{M13,M11,M7,M5,M4,M2}}

8）TS(8)={M14,M1}

同4）Test-Path-Set保持不变。

9）TS(9)={M14,M4}

同4）Test-Path-Set保持不变。

10）TS(10)={M14,M5}

M5是M14的祖先，添加M5到M14的路径

Test-Path-Set={{M2,M1},{M4,M2},{M5,M4,M2},{M7,M5,M4,M2},{M11,M7, M5,M4,M2},{M13,M7,M5,M4,M2},{M13,M11,M7,M5,M4,M2},{M5,M14}}

11）TS(11)={M14,M6}

同4）Test-Path-Set保持不变。

12）TS(12)={M14,M7}

M7是M14的祖先，添加M7到M14的路径

Test-Path-Set={{M2,M1},{M4,M2},{M5,M4,M2},{M7,M5,M4,M2},{M11,M7, M5,M4,M2},{M13,M7,M5,M4,M2},{M13,M11,M7,M5,M4,M2},{M5,M14},{M7,M14}}

13）TS(13)={M14,M11}

M11是M14的祖先，添加M11到M14的路径

Test-Path-Set={{M2,M1},{M4,M2},{M5,M4,M2},{M7,M5,M4,M2},{M11,M7, M5,M4,M2},{M13,M7,M5,M4,M2},{M13,M11,M7,M5,M4,M2},{M5,M14},{M7, M14},{M11,M7,M14}}

14）TS(14)={M14,M13}

M13是M14的祖先，添加M13到M14的路径

Test-Path-Set={{M2,M1},{M4,M2},{M5,M4,M2},{M7,M5,M4,M2},{M11,M7, M5,M4,M2},{M13,M7,M5,M4,M2},{M13,M11,M7,M5,M4,M2},{M5,M14},{M7, M14},{M11,M7,M14},{M13,M7,M14},{M13,M11,M7,M14}}

15）TS(15)={M3,M1}

同4）Test-Path-Set保持不变。

16）TS(16)={M3,M4}

M4是M3的祖先，添加M4到M3的路径，同时去掉路径末尾的M3

Test-Path-Set={{M2,M1},{M4,M2},{M5,M4,M2},{M7,M5,M4,M2},{M11,M7, M5,M4,M2},{M13,M7,M5,M4,M2},{M13,M11,M7,M5,M4,M2},{M5,M14},{M7, M14},{M11,M7,M14},{M13,M7,M14},{M13,M11,M7,M14},{M4}}

17）TS(17)={M3,M5}

M5是M3的祖先，添加M5到M3的路径，同时去掉路径末尾的M3

Test-Path-Set={{M2,M1},{M4,M2},{M5,M4,M2},{M7,M5,M4,M2},{M11,M7, M5,M4,M2},{M13,M7,M5,M4,M2},{M13,M11,M7,M5,M4,M2},{M5,M14},{M7, M14},{M11,M7,M14},{M13,M7,M14},{M13,M11,M7,M14},{M4},{M5}}

18）TS(18)={M3,M6}

同4）Test-Path-Set保持不变。

19）TS(19)={M3,M7}

M7是M3的祖先，添加M7到M3的路径，同时去掉路径末尾的M3

Test-Path-Set={{M2,M1},{M4,M2},{M5,M4,M2},{M7,M5,M4,M2},{M11,M7, M5,M4,M2},{M13,M7,M5,M4,M2},{M13,M11,M7,M5,M4,M2},{M5,M14},{M7, M14},{M11,M7,M14},{M13,M7,M14},{M13,M11,M7,M14},{M4},{M5},{M7}}

20）TS(20)={M3,M11}

M11是M3的祖先，添加M11到M3的路径，同时去掉路径末尾的M3

Test-Path-Set={{M2,M1},{M4,M2},{M5,M4,M2},{M7,M5,M4,M2},{M11,M7, M5,M4,M2},{M13,M7,M5,M4,M2},{M13,M11,M7,M5,M4,M2},{M5,M14},{M7, M14},{M11,M7,M14},{M13,M7,M14},{M13,M11,M7,M14},{M4},{M5},{M7},{M11,M 7}}

21）TS(21)={M3,M13}

M13是M3的祖先，添加M13到M3的路径，同时去掉路径末尾的M3

Test-Path-Set={{M2,M1},{M4,M2},{M5,M4,M2},{M7,M5,M4,M2},{M11,M7, M5,M4,M2},{M13,M7,M5,M4,M2},{M13,M11,M7,M5,M4,M2},{M5,M14},{M7, M14},{M11,M7,M14},{M13,M7,M14},{M13,M11,M7,M14},{M4},{M5},{M7},{M11,M 7},{M13,M7},{M13,M11,M7}}

去掉测试路径集合Test-Path-Set中的冗余路径得到新的测试路径集合

Test-Path-Set’={{M2,M1},{M4,M2},{M5,M4,M2},{M7,M5,M4,M2},{M11,M7, M5,M4,M2},{M13,M7,M5,M4,M2},{M13,M11,M7,M5,M4,M2},{M5,M14},{M7, M14},{M11,M7,M14},{M13,M7,M14},{M13,M11,M7,M14},{M5},{M7},{M11,M7},{M 13,M7},{M13,M11,M7}}

根据测试输入等价类划分的方法得到每个测试路径的测试输入TestSuit= {input(M2),input(M4),input(M5),inputM7)inputM11),inputM13), input(M13),input(M5),input(M7),input(M11),input(M13),inputM13), input(M5),input(M7),input(M11),input(M13)input(M13)}。