因果图法的改进及算法实现

张 志,王 敏

(湖北广播电视大学电信工程学院,湖北 武汉 430074)

0 引 言

提高开发效率、降低软件成本是软件工程追求的目标。作为软件开发过程的重要组成部分，软件测试是软件质量保证的重要手段，在大型软件开发项目中，软件测试甚至会占据整个项目周期的一半时间[1]。软件测试的效率将直接影响软件项目的效率和成本，因此如何提高软件测试效率是研究者们一直探索的问题[2-10]。

针对多条件组合问题常常采用因果图法进行测试用例设计，但当组合条件太多，存在较复杂的因果关系和约束的情况下，测试用例设计过程较复杂、设计效率较低下，故人们对因果图法的测试用例自动生成进行了一系列的研究。20世纪90年代曾提出依据因果图得出关系或约束的逻辑表达式来自动生成测试用例[11]，以及用条件公式和卡若图来化简决策表等[12]，在一定程度上实现了测试用例设计的自动化。随着软件工程和可视化编程技术的发展，早期的这些方法在可操作性和易用性上已不能满足测试用例设计者的需求。为此，人们又提出了采用逐级模式转换的方式生成测试用例[13]，根据人工分析得到条件组合表达式来实现决策表的化简等方法[14]。但迄今为止的成果尚局限于因果图法的思路,且未实现测试用例设计全过程的自动化。为此，抛开传统的因果图法设计思路，提出采用符号机制[15],用由字符组成的因果表达式取代因果图来进行测试用例设计。

为实现上述目标，需要定义能取代因果图的因果表达式的语法规则，并设计一种数据结构来存储和操作决策表，在此基础上结合测试用例设计的需求实现基于因果表达式的测试用例设计工具。

1 因果表达式

在软件工程领域，很多设计均以图形化的方式呈现，其优点是直观、易于理解，但将图形化呈现的数据作为计算机处理的输入，其处理复杂度将会高于对线性字符的处理。于是本文设想将因果图演变为因果表达式来描述关系和约束，将对复杂图形的处理转化为对字符表达式的分析处理，可以降低算法实现的复杂程度。为此，首先需确立能替代因果图的因果表达式的语法规则。

因果图含4种关系图(如图1所示)和5种约束图(如图2所示)[16]，因此需要定义若干表达式来描述这9类因果图。

图1 因果图的关系图

图2 因果图的约束图

首先给出因果表达式的定义：

定义1采用字符、数字来表示因果图中的各种关系和约束的表达式，叫做因果表达式。其中表示约束语义的为约束表达式，表示关系语义的为关系表达式。

设被测对象的规格说明中含n个原因、m个结果、k个约束、q个关系，对应的语法规则为：C[i](i为原因编号，1≦i≦n)表示编号为i的原因，E[i](i为结果编号，1≦i≦m)表示编号为i的结果，Y[i](i为约束编号，1≦i≦k)表示编号为i的约束表达式，R[i](i为关系编号，1≦i≦q)表示编号为i的关系表达式。

与图1(a)～图1(d)对应，制定关系表达式的语法规则如下：

1)恒等。记为C[i]=E[j]，表示原因C[i]成立，则有结果E[j],对应图1(a)。

2)非。记为NEG(C[i])=E[j]，可表示2层意思：①原因C[i]不成立，则有结果E[j]；②原因C[i]成立，则没有结果E[j]。为了方便后续编程实现，表达式均要求以有对应结果的方式进行描述，故这里取意思①，对应图1(b)，NEG为非运算符。

3)或。记为OR(C[i]，…,C[n])=E[j]，表示参与运算的任一原因成立，则有结果E[j],对应图1(c)，OR为或运算符。

4)与。记为AND(C[i]，…,C[n])=E[j],表示参与运算的原因全部成立，则有结果E[j],对应图1(d)，AND为与运算符。

以上为与因果图中的关系图对应的关系表达式，为表达式描述更加直观、简洁且便于后续实现，在此定义2种扩展的语法规则：①允许对AND和OR运算内的参数进行NEG运算来表示原因不成立的语义，如：AND(NEG(C[i]),C[k])=E[j]，其语义为C[i]不成立且C[k]成立，则有结果E[j]；②允许关系表达式等号右侧为多个结果的列表,将多个结果用逗号分隔置于单括弧中，表示由某些原因组合可有多个结果，如：AND(C[i]，C[n])=(E[j],E[m]),表示原因C[i]和C[n]同时成立，则有E[j]和E[m]这2个结果。

与图2(a)～图2(e)对应，制定约束表达式的语法规则如下：

1)互斥。记为E(C[i],…，C[j]，…,C[n]),表示括弧内的原因最多只有一个成立，对应图2(a)。

2)包含。记为I(C[i],…，C[j]，…,C[n]),表示括弧内的原因至少有一个必须成立，对应图2(b)。

3)唯一。记为O(C[i],…，C[j]，…,C[n]),表示括弧内的原因有且仅有一个成立，对应图2(c)。

4)要求。记为R(C[i],C[j]),表示C[i]成立则C[j]也必须成立，对应图2(d)。

5)强制。记为M(E[i],E[j]),表示若有结果E[i]，则不可能有结果E[j]，对应图2(e)。

确立了与因果图对应的因果表达式及其扩展表达式的语法规则，即可将测试用例设计条件以字符表达式的方式输入计算机，接下来探索测试用例设计的实现方法。

2 决策表的数据结构

多条件组合问题的测试用例设计最终要转化为决策表，通过对因果图约束的分析可以确定决策表中不可能存在的规则，从而减少决策表的规则数，即减少测试用例数。因此，探索基于因果表达式的测试用例生成算法，首先需要确定决策表的数据结构。

2.1 决策表的数据存储

相较于传统的因果图法，采用因果表达式不再需要中间状态作为过渡。在此定义新的决策表结构，假设被测对象含3个原因、4个结果，其决策表结构如表1所示(表中数据为初始数据)。与因果图法的决策表结构相比，减少了中间状态，增加了一行有效性数据，此行数据用于在生成测试用例过程中标识规则的有效性(1表示有效规则,非1表示被约束排除或合并化简的无效规则)。

表1 新决策表结构

规则编号12345678有效性11111111C[1]00001111C[2]00110011C[3]01010101E[1]00000000E[2]00000000E[3]00000000E[4]00000000

为此，给出新的决策表定义：

定义2将以规则编号、有效性、原因和结果为行，规则为列，用于存储规则编号、规则有效性、原因值和结果值的二维数据表，叫决策表。

若某被测对象含有n个原因(条件)、m个结果，则决策表为(m+n+2)×(2n+1)的二维数据表(如表1之标注所示)。确立了决策表的数据结构，测试用例的设计即演化为对二维数据表的操作。

2.2 决策表的数据操作

利用决策表进行测试用例设计含以下操作步骤：

Step1根据规格说明确定原因和结果；

Step2根据规格说明列出因果(关系和约束)表达式；

Step3生成初始决策表；

Step4根据关系表达式确定结果值；

Step5根据约束表达式排除不可能规则；

Step6合并化简；

Step7测试用例生成。

传统因果图法的化简是指“如果2条或多条规则的结果(动作项)完全相同，原因(条件项)只有一项不同，则可以将这些规则合并为一条规则”,化简实际上就是合并相似规则的操作，可减少规则数，也即减少测试用例数。根据约束排除不可能规则也是为了减少测试用例数，因此，对化简做以下扩展定义。

定义3根据约束表达式排除决策表中不可能存在的规则，或合并决策表相似规则的处理，叫做化简。

根据化简方式的不同，将化简分为约束化简和合并化简。根据约束表达式排除不可能规则的化简叫约束化简；合并决策表相似规则的化简叫合并化简。

以上7个步骤中Step1～Step2可通过对规格说明书的分析将测试输入直接通过键盘输入到计算机，Step3即按表1的规则初始化决策表数据，步骤Step4～Step6是测试用例自动生成的核心步骤，实现将初始决策表精简为少量有效规则，Step7将化简后的决策表转换为描述性的测试用例。对决策表的操作主要着眼于Step3～Step7。

下面以一个经典案例来分析采用因果表达式进行测试用例设计的决策表操作。

案例1某软件规格说明要求：第一个字符必须是#或*，第二个字母必须是数字，在此情况下进行文件的修改，如果第一个字符不是#或*，则输出信息“N”，如果第二个字符不是数字，则给出信息“M”。

根据以上规格说明,按上述步骤进行测试用例设计:

1)根据规格说明确定原因和结果。

C[1]：第一个字符是#；

C[2]：第一个字符是*；

C[3]：第二个字母必须是数字。

E[1]：进行文件的修改；

E[2]：输出信息“N”；

E[3]：输出信息“M”。

算法实现：定义原因数组C和结果数组E。

2)根据规格说明列出因果表达式。

约束表达式：

Y[1]：E(C[1]，C[2])

算法实现：定义约束表达式数组Y。

关系表达式：

R[1]：AND(C[1]，C[3])=E[1]

R[2]：AND(C[2]，C[3])=E[1]

R[3]：AND(NEG(C[1])，NEG(C[2]))=E[2]

R[4]：NEG(C[3])=E[3]

算法实现：定义关系表达式数组R。

3)生成初始决策表，即决策表的初始化。第1行数据初始化为规则编号；第2行数据初始化为“1”，表示全部规则有效；假设有n个原因，则n行原因数据的初始化规则为：将0～(2n-1)的2n个数值转换为二进制数，以“0”和“1”逐位填写到对应行列中。案例含3个原因，则将0～7的二进制代码一次填入表2的3～5列；结果行数据初始化为0，表示无结果。如表2所示。

表2 初始决策表

规则12345678有效性11111111C[1]00001111C[2]00110011C[3]01010101E[1]00000000E[2]00000000E[3]00000000

4)根据关系表达式确定结果值。

如图3所示，设关系表达式数组R的下标变量为k，决策表D的列下标变量分别为j；以关系表达式作为外循环，规则作为内循环，逐一进行结果值设定，判断决策表规则的原因值是否满足关系表达式左边原因值，若满足则依据关系表达式右边的结果列表，将该规则对应的结果值设为“1”。如案例1，当关系R[1]对规则进行循环时，若规则C[1]=“1”，C[3]=“1”，则将对应规则的结果值E[1]设为“1”，如表3所示。

图3 结果值设定处理流程

5)根据约束表达式进行约束化简。

与上面测试用例设计4的处理类似，以约束表达式作为外循环，规则作为内循环，逐一判断决策表规则的原因值或结果值(强制)是否满足约束表达式的制约，若满足则将该规则的有效性设为对应约束编号“Y[i]”。如案例中的Y[1]，规则7,8的C[1]=“1”，C[2]=“1”，满足Y[1]制约，则将其有效性设为“Y[1]”，如表3所示。

表3 化简后的决策表

规则12345678有效性111111Y[1]Y[1]C[1]00001111C[2]00110011C[3]01010101E[1]00010101E[2]11000000E[3]10101010

6)合并化简。

按结果值进行筛选，结果值一致的规则分为一组，然后按组进行循环，同一组数据中，按冒泡方式进行合并，若满足合并条件，则将规则编号较大规则的有效性设为“H”，表示合并化简操作被合并的规则，并将不同的原因(条件项)项设为“-”，该规则可继续参与冒泡合并。

案例不存在可合并的规则，故决策表不能被进一步化简。于是得到化简后的最终决策表，如表3所示，规则1～6为有效规则。

7)测试用例生成。

根据化简后的决策表，1条有效规则对应生成1条测试用例。

3 算法的工具化实现

确立了因果表达式及决策表的数据结构，便可实现包含测试条件输入、测试用例自动生成以及测试用例维护功能的基于多条件组合的测试用例自动生成工具。在此，选用C#,.Net可视化编程平台，将决策表定义为该平台现有的数据类型DataTable类型，并通过与DataGridView控件绑定，来直观地呈现数据。

3.1 界面设计

将工具设计为2个界面：设计界面和设计过程显示界面。设计界面如图4所示，界面分为2个区域：测试输入编辑区如图4(a)所示、测试用例显示及编辑区如图4(b)所示，为简化描述，将部分控件Text属性的初始值设成控件类型，设计采用了数组型列表框控件(ListBox)来显示原因、结果、约束表达式和关系表达式列表，既方便查看系列数据又便于在编程中利用index属性作为循环变量和使用列表框中的元素。

(a) 测试输入编辑区 (b) 测试用例显示及编辑区图4 测试用例设计界面

通过单击图4的【过程查看】按钮打开设计过程显示界面(如图5为案例执行的过程数据)。

图5 设计过程显示界面

3.2 功能设计

工具含测试输入编辑、测试用例生成、测试信息维护和测试用例编辑功能，详细设计如下：

1)测试输入编辑功能。

实现被测对象原因、结果和因果表达式的输入和编辑。在输入编辑框(TextBox)对原因、结果和因果表达式的内容进行编辑，可对列表框(ListBox)中的内容进行追加、更新和删除处理。

例如：输入原因“投入2元硬币”，单击【追加】按钮会自动生成原因标识C[n](n为原因编号值)，并以“C[n]：投入2元硬币”的形式向列表框中追加一条数据。

2)测试用例生成功能。

测试用例生成功能是工具实现的核心，它由决策表数据结构对应的操作来完成，包含根据测试输入初始化决策表、结果值设定、化简(约束化简和合并化简)和测试用例生成。

3)测试信息维护功能。

设计图4(a)的功能按钮【用例导入】和【用例导出】单击事件实现测试用例设计信息和结果信息的导入和导出。其中导出功能实现将界面中的信息保存于XML格式的文件中，保存的信息可用于后续测试用例的维护；导入功能实现将现存XML文件中的测试信息导入到界面，通过界面对测试信息进行编辑，实现测试用例的维护。

XML文件中可保存含原因、结果、约束、关系和测试用例的相关数据，采用XML的文件格式保存测试信息，既便于测试用例的维护又方便测试用例数据在不同平台间的传送和呈现。其基本格式设计如下：

…

…

在根节点对之间包含,,,,这5组分类节点，对应原因、结果、约束、关系和测试用例信息，其中原因、结果、约束和关系节点内含由编号和内容组成的多条数据记录，测试用例节点内含由编号、输入原因和预期结果组成的多条数据记录。

4)测试用例编辑功能。

考虑到采用任何测试用例设计方法设计的测试用例都是测试用例全集(穷举测试)的子集，均需要人工进行测试用例的补充设计，因此，图4(b)除了用于呈现自动生成的测试用例外，还设计了测试用例编辑功能，用于编辑人工追加的测试用例。

3.3 结果验证

在此，通过2个因果法的经典案例来验证采用因果表达式算法的正确性。

案例2“自动贩卖机”软件的测试用例设计

图6(a)为设计输入和测试用例生成界面，图6(b)为设计过程显示界面。

(a) 测试输入和生成的测试用例

(b) 设计过程数据图6 案例2验证结果

导出测试用例的XML文件如下(鉴于文件过长，省略了部分相似内容)：

…

…

…

…

案例3“中国象棋中走马”的测试用例设计

图7(a)为设计输入和测试用例生成界面，测试输入编辑区因界面篇幅的原因，关系表达式未能全部显示，关系ListBox的实际内容如下：

R[1]：OR(C[1]，C[2]，C[3]，C[4])=E[1]

R[2]：AND(NEG(C[1])，NEG(C[2])，NEG(C[3])，NEG(C[4])，C[5])=E[2]

R[3]：AND(NEG(C[1])，NEG(C[2])，NEG(C[3])，NEG(C[4])，C[6])=(E[2]，E[3])

R[4]：AND(NEG(C[1])，NEG(C[2])，NEG(C[3])，NEG(C[4])，C[7])=(E[2]，E[4])

测试用例显示及编辑区，工具设计考虑了案例描述方式的不同需求，这里与案例2不同，选勾了“全输入描述”，输入原因被全部描述，描述中用“√”代表原因成立，“×”代表原因不成立，“○”代表原因取任意值，图7(b)为测试用例滚动显示结果。

图7(c)为设计过程的部分数据，由于案例3包含7个原因，因此初始决策表含128(27)条规则，界面中未能完全显示，勾选“仅显示有效规则”，结果如图7(d)所示。

采用因果表达式的方法自动生成的测试用例与人工采用传统的因果图法设计的结果一致。由于算法实现主要针对由原因组合而成的规则进行处理，算法分析中通过对3原因8规则、4原因16规则、5原因32规则关系和约束类似的模拟被测对象进行了测试用例设计，平均耗时分别为11.88 ms,16.18 ms,25.57 ms。假设一个单位时间(ms)执行一次循环，设被测对象规则规模为n，可得该算法的时间复杂度T(n)为O(n)。

(a) 测试输入和生成的测试用例

(b) 测试用例滚动显示结果

(c) 设计过程数据

(d) 设计过程数据的有效规则图7 案例3验证结果

3.4 方法比较

采用因果表达式进行测试用例设计与因果图法具有同样的结果，但采用因果表达式有以下优势：

1)采用因果表达式降低了设计难度。

采用因果表达式不用绘制因果图，因此不用分析复杂条件组合的中间状态，只需要书写约束和关系表达式，减少了测试用例设计的工作量和设计难度。

作为对比，因果图法较为繁琐，中间状态的分析及因果图的绘制增加了测试用例设计人员的负担，尤其是对较复杂的因果关系，设计难度较大。

2)采用因果表达式易于算法实现。

表达式由键盘符号构成，便于向计算机输入，通过对表达式进行语法分析，采用基本数据类型就能实现测试用例设计。而因果图输入计算机困难，测试用例设计需要进行图的遍历，需要自定义较复杂的数据类型来分析因果图，算法实现难度较大。

3)采用因果表达式设计效率高。

因果表达式法易于向算法转化，能实现测试用例自动生成工具，实现含测试用例设计和维护全过程的自动化，使测试用例设计和维护效率得以提高。

但迄今为止，还没有基于因果图法的、能实现测试用例设计全过程自动化的工具，现有成果针对因果图的部分操作尚需要人工完成，设计效率较低。

4 结束语

本文提出了一种因果图法测试用例设计的改进方法,把对图的处理转化为对由字符组成的因果表达式的处理，简化了算法实现的复杂程度。将传统的决策表采用数组型数据表来存储，把对规则的化简处理转化为数组型数据的处理，给算法实现和数据呈现都带来了方便。通过XML文件来存储测试用例，既便于测试用例的维护，还能跨平台使用数据，且可以定义不同的CSS样式在不同平台呈现数据。本文研究着眼于测试用例设计的自动化技术，后续将在此基础上针对多条件组合问题测试用例的自动执行进行研究，以进一步提高多条件组合问题的测试效率。

[1] 解筱梦. 面向云测试的并行测试用例自动生成方法研究[D]. 上海:东华大学， 2015.

[2] Son H S, Kim W Y, Kim J S, et al. Automatic test case generation using multiple condition control flow graph[J]. Information Technology and Computer Science, 2012(13):105-109.

[3] 王敏,陈少敏,陈亚光. 基本路径测试用例设计算法[J]. 计算机应用, 2013,33(11):3262-3266.

[4] 张卫祥,刘文红. 基于故障树分析与组合测试的测试用例生成方法[J]. 计算机科学, 2014,41(S2):375-378.

[5] 宋蕾. 基于场景的测试用例自动生成方法[J]. 计算机与数字工程, 2015,43(5):844-848.

[6] 王敏,陈亚光. 用于基本路径测试的路径字符串组合算法[J]. 计算工程与科学, 2013,35(12):134-140.

[7] 王敏,王智超,余杨. 基于QTP的数据库系统测试框架[J]. 计算机与数字工程, 2014,42(1):117-121.

[8] 王敏,张莉萍,王一平. 用于GUI软件的测试工具[J]. 计算机与数字工程, 2014,42(2):346-350.

[9] Lemos O A L, Ferrari F C, Eler M M, et al. Evaluation studies of software testing research in the brazilian symposium on software engineering[C]// Proceedings of 2011 the 25th Brazilian Symposium on Software Engineering. 2011:56-65.

[10] 张伟,吴黎明. 基于因果图的软件自动化测试方法研究[J]. 计算机与现代化, 2011(12):78-81.

[11] 张福源,杨云. 基于因果图的软件测试工具的研究与设计[J]. 计算机学报, 1993(3):219-224.

[12] 韩坚华. 一种化简判定表的方法[J]. 计算机工程与应用, 1995(4):36-40.

[13] Son H S, Kim R Y C, Park Y B. Test case generation from cause-effect graph based on model transformation[C]// 2014 International Conference on Information Science and Applications(ICISA). 2014:1891-1894.

[14] 毛养红. 测试用例设计中的判定表自动生成研究[J]. 无线互联科技, 2015(16):114-115.

[15] 王江晴. 符号智能与计算智能[M]. 武汉:湖北科学技术出版社, 2002.

[16] 宫云战,赵瑞莲,张威,等. 软件测试教程[M]. 北京:机械工业出版社, 2016.