一种计算机软件白盒测试的实现方法及系统

摘要

本发明涉及一种计算机软件白盒测试的实现方法及系统。该实现方法包括：步骤1，求解判定布尔表达式中各个条件的独立对；步骤2，基于各个条件对应的独立对求解判定最小独立对集合，求解判定出的最小独立对集合构成参考用例集合；步骤3，选择参考用例集合中一个最小独立对集合，并生成与该最小独立对集合对应的测试用例集合，该测试用例集合即为最小测试集；步骤4，用最小测试集对源程序进行修正条件/判定覆盖测试。本发明可以减少修正条件/判定覆盖(MC/DC)测试的成本，避免了生成大量的测试用例以及对测试用例进行精简的过程。

权利要求

1.一种计算机软件白盒测试的实现方法，其特征在于，包括：

步骤1，求解判定布尔表达式中各个条件的独立对；

步骤2，基于各个条件对应的独立对求解判定最小独立对集合，求解判定出的最小独立对集合构成参考用例集合；求解最小独立对集合，采用从每个条件对应的独立对中选择一个进行组合生成独立对集合，并选择独立对集合中元素最少的独立对集合作为最小独立对集合；

步骤3，在参考用例集合中选取一个最小独立对集合，并生成与该最小独立对集合对应的测试用例集合，该测试用例集合即为最小测试集；

步骤4，用最小测试集对源程序进行修正条件/判定覆盖测试；

最小独立对集合满足下述条件：

给定一个判定Z，该判定含有N个条件，N个条件中含有M个不相等条件，M≤N，M个不M M相等条件的真值表中的2 个用例Ci组成用例集合S，i∈[1，2]；每一个条件对应一个非空有限独立对结果集合Rk，Rk中的元素为独立对P，独立对P包含两个用例Ci、Cj，i，j∈[1，M

2]；由N个独立对Pk中的所有用例构成集合D，任意Pk∈Rk，k∈[1，N]；满足集合元素个数|D|最小的D为最小独立对集合。

2.如权利要求1所述的计算机软件白盒测试的实现方法，其特征在于，步骤1中，根据唯一原因法或者屏蔽法求解各个条件对应的独立对。

3.如权利要求1所述的计算机软件白盒测试的实现方法，其特征在于，步骤4中，统计最小测试集的修正条件/判定覆盖的覆盖率；如果根据覆盖率判定需要补充测试用例，则在剩余的最小独立对集合选取至少一个并执行步骤3，生成对应的测试用例作为补充。

4.一种计算机软件白盒测试的实现系统，其特征在于，包括：

独立对求解模块，用于求解判定布尔表达式中各个条件的独立对；

最小独立对集合求解模块，用于基于各个条件对应的独立对求解判定最小独立对集合，求解判定出的最小独立对集合构成参考用例集合；求解最小独立对集合，采用从每个条件对应的独立对中选择一个进行组合生成独立对集合，并选择独立对集合中元素最少的独立对集合作为最小独立对集合；

测试用例生成模块，用于选择参考用例集合中的一个最小独立对集合，并生成与该最小独立对集合对应的测试用例集合，该测试用例集合即为最小测试集；

修正条件/判定覆盖测试模块，用于用最小测试集对源程序进行修正条件/判定覆盖测试；

最小独立对集合满足下述条件：

给定一个判定Z，该判定含有N个条件，N个条件中含有M个不相等条件，M≤N，M个不M M相等条件的真值表中的2 个用例Ci组成用例集合S，i∈[1，2]；每一个条件对应一个非空有限独立对结果集合Rk，Rk中的元素为独立对P，独立对P包含两个用例Ci、Cj，i，j∈[1，M

2]；由N个独立对Pk中的所有用例构成集合D，任意Pk∈Rk，k∈[1，N]；满足集合元素个数|D|最小的D为最小独立对集合；M、N为自然数。

5.如权利要求4所述的计算机软件白盒测试的实现系统，其特征在于，独立对求解模块，用于根据唯一原因法或者屏蔽法求解各个条件对应的独立对。

6.如权利要求4所述的计算机软件白盒测试的实现系统，其特征在于，修正条件/判定覆盖测试模块，还用于统计最小测试集的修正条件/判定覆盖的覆盖率；如果根据覆盖率判定需要补充测试用例，则在剩余的最小独立对集合选取至少一个通知测试用例生成模块生成对应的测试用例作为补充。

说明书

一种计算机软件白盒测试的实现方法及系统

技术领域

[0001] 本发明涉及计算机软件领域，尤其涉及一种计算机软件白盒测试的实现方法及系统。

背景技术

[0002] 软件测试是软件工程中的重要环节，由于测试目标的不同，存在不同的测试标准。修正条件/判定覆盖(Modified Condition/Decision Coverage，简称MC/DC)，是软件白盒测试领域逻辑覆盖测试技术中的一种测试标准。该标准最早是在1994年由John Joseph Chilenski和Steven P.Miller两位工程师在DO-178B标准中首次提出。DO-178B标准由航空无线电技术协会制定，美国联邦航空局将其用于测试所有新开发的航空软件，时至今日已经成为航空软件以及关键安全领域软件测试中一个广泛应用的测试标准。在DO-178B中阐明了MC/DC的意义：对于关键性的实时程序而言，超过半数的可执行代码可能都与布尔运算表达式有关，表达式的复杂性应得到关注。MC/DC测试标准主要是为了检测程序中布尔表达式当中可能存在的错误。

[0003] 修正条件/判定覆盖中的条件(condition)表示不含有逻辑操作符的布尔表达式，例如(x＞20)、(x＞y＞10)；如果同一个布尔表达式在一个判定中出现了多次，那么该表达式应算作多个条件。判定(decision)表示由条件和零个或者多个逻辑操作符所组成的一个布尔表达式，例如Z＝((x＞20)or(y＞20))and((x＞20)or(z＜20))代表了一个判定，这个判定可以简写为：(A or B)and(A orD)。该判定中有四个条件：A、B、A、D。MC/DC测试标准有四条准则：

[0004] a)程序的入口点和出口点都要被执行到；

[0005] b)程序中每一个判定的所有可能结果都要被执行到；

[0006] c)程序中每一个判定中的每一个条件的所有可能结果都要被执行到；

[0007] d)判定中的每一个条件都能独立影响判定的结果。

[0008] MC/DC标准中最重要的一条准则就是：判定中的每一个条件都能独立影响判定的结果。若一组两个测试用例中对于某个条件的取值相反，而保持其他条件取值不变，如果判定的结果也相反，则表明此条件能够独立的影响判定的结果，说明该条件在逻辑上是有效的，同时这样的一对测试用例可以构成该条件在MC/DC测试标准中的独立影响对(简称为独立对)。例如布尔取值组合(true，true)(false，true)可以作为判定(A and B)中条件A的独立对，为简单起见，下文中都将以大写字母T表示true，大写字母F表示false。输入上述的取值组合，判定的结果由T变为F，条件A改变的同时，保持了条件B的取值。应用MC/DC测试标准，关键就是计算判定中每个条件的独立对。

[0009] 在MC/DC独立对的实际求解过程中，还需要考虑两个问题，一个是布尔运算中的短路计算；另外一个是判定表达式中条件之间的耦合关系。

[0010] 所谓布尔表达式的短路计算是指无需对表达式中全部的操作数和操作符进行计算就可得到表达式的布尔值。例如对于布尔表达式：Z＝(A and B)，若A为false，则无需计算B的值就能确定Z必为false。此判定中在A的值为false的时候，可以进行短路计算；反之，若A的值为true，则还需计算B的值。

[0011] 此外，在实际测试过程中，由于判定中条件之间可能存在耦合关系，改变一个条件的取值而保持其他条件取值不变这个原则有时并不能保证。条件之间的耦合关系可以分为以下两类：

[0012] a)强耦合：指改变一个条件的取值，必然会改变其他某些条件的取值，例如判定：(x＞0)and(y＞10)or(x＜＝0)中的条件(x＞0)和(x＜＝0)；两个条件的取值必然相反。

[0013] b)弱耦合：指改变一个条件的取值，可能改变其他一些条件的取值，例如判定：(x＞0)and(x＞20)中的两个条件。弱耦合也能导致某些取值组合无法得到，若(x＞20)为true，则(x＞0)必然为true，因此(x＞0)为false，而(x＞20)为true的取值组合无法获得。

[0014] 条件之间存在这样的耦合关系导致在求解独立对的时候，改变一个条件的取值的同时并不能保证其他条件取值保持不变，则此时需要对独立对的定义和求解方式作相应修改。目前应用中主要有两种形式的独立对定义，对应不同的求解方式，即：唯一原因法(unique-cause method)和屏蔽法(maskingmethod)。

[0015] 所谓唯一原因法，就是按照独立对的初始定义求解独立对。亦即在改变当前条件的布尔取值时，保持判定中其他条件的取值不变，若结果改变，则说明改变前后的两个case构成了当前条件的独立对；

[0016] 所谓屏蔽法，就是在求解独立对的过程中，屏蔽掉耦合条件的取值，如判定((A1 and B)‖(A2 and C))中，A1、A2是相同的条件(下标表示条件在判定中的不同位置)。求解条件A1的独立对时，保持子表达式(A2 and C)的取值为false(意味着保持条件C的取值为false)即可屏蔽掉A2对A1的影响。

[0017] 通常在求解独立对的过程中，一般采用短路计算；在判定表达式中无条件耦合的情况下采用唯一原因法，若存在耦合，则采用屏蔽法求解独立对。

[0018] 不论采用哪种方法，求解独立对的最终目的都是为了从独立对结果出发，指导测试用例的生成，对源程序测试其MC/DC覆盖率，依此检测出源程序中布尔表达式的错误。

[0019] MC/DC测试标准是广泛应用在航空、国防等关键安全领域的软件测试标准，主要用于检测程序中布尔表达式的错误。在测试过程中，传统的流程如下：

[0020] 第1步：先求解判定表达式中各个条件的独立对：在无条件耦合的情况下，采用唯一原因法求解独立对；若判定中各个条件之间存在耦合(特别是强耦合)的情况，则采用屏蔽法求解独立对。

[0021] 第2步：根据独立对的求解结果生成测试用例：由于每一个独立对包含两个case，对每一个case生成相应的测试用例。

[0022] 第3步：在第2步中，各条件对应的独立对结果在某些情况下会很多，例如采用屏蔽法求解的时候。此时将会生成大量的测试用例，特别在对整个程序测试的时候，程序中大量的判定将会生成海量的测试用例，为了节约测试成本、降低测试难度，需要对大量的测试用例进行精简，以求得到一个最小的测试用例集合(亦即最小测试集)。

[0023] 第4步：将最小测试集作为输入，检测程序中布尔表达式相关的错误。

[0024] 传统的流程总体来说是先求解判定表达式中条件的独立对，根据独立对生成测试用例。由于大量的测试用例中往往存在冗余的部分，而且为了减少测试工作量，通常需要对测试用例进行精简以得到最小测试集。如果能够从独立对结果出发，求解得到一个最小的独立对集合，用最小独立对集合指导生成最小测试集。则可以避免了生成大量的测试用例以及对测试用例进行精简的过程。目前尚未发现有直接求解此类最小(或最优)的独立对集合的方法。

发明内容

[0025] 为了解决上述的技术问题，本发明提供了一种计算机软件白盒测试的实现方法及系统，主要是针对MC/DC测试标准。其目的在于，避免生成大量的测试用例以及对测试用例进行精简的过程。

[0026] 本发明提供了一种计算机软件白盒测试的实现方法，包括：

[0027] 步骤1，求解判定布尔表达式中各个条件对应的独立对；

[0028] 步骤2，基于各个条件对应的独立对求解判定最小独立对集合，求解判定出的最小独立对集合构成参考用例集合；

[0029] 步骤3，在参考用例集合中选取一个最小独立对集合，并生成与该最小独立对集合对应的测试用例集合，该测试用例集合即为最小测试集；

[0030] 步骤4，用最小测试集对源程序进行修正条件/判定覆盖测试；

[0031] 最小独立对集合满足下述条件：

[0032] 给定一个判定Z，该判定含有N个条件，N个条件中含有M个不相等条件，M个不相M M等条件的真值表中的2 个用例Ci组成用例集合S，i∈[1，2]；每一个条件对应一个非空有限独立对结果集合Rk(i∈[1，N])，Rk中的元素为独立对P，独立对P包含两个用例Ci、M
Cj，i，j∈[1，2]；由N个独立对Pk中的所有用例构成集合D，任意Pk∈Rk，k∈[1，N]；满足集合元素个数|D|最小的D为最小独立对集合。

[0033] 步骤1中，根据唯一原因法或者屏蔽法求解各个条件对应的独立对。

[0034] 步骤2中，从每个条件对应的独立对中选择一个进行组合生成独立对集合，并选择独立对集合中元素最少的独立对集合作为最小独立对集合。

[0035] 步骤4中，统计最小测试集的修正条件/判定覆盖的覆盖率；如果根据覆盖率判定需要补充测试用例，则在剩余的最小独立对集合选取至少一个并执行步骤3，生成对应的测试用例作为补充。

[0036] 本发明提供了一种计算机软件白盒测试的实现系统，包括：

[0037] 独立对求解模块，用于求解判定布尔表达式中各个条件的独立对；

[0038] 最小独立对集合求解模块，用于基于各个条件对应的独立对求解判定最小独立对集合，求解判定出的最小独立对集合构成参考用例集合；

[0039] 测试用例生成模块，用于选择参考用例集合中的一个最小独立对集合，并生成与该最小独立对集合对应的测试用例集合，该测试用例集合即为最小测试集；

[0040] 修正条件/判定覆盖测试模块，用于用最小测试集对源程序进行修正条件/判定覆盖测试；

[0041] 最小独立对集合满足下述条件：

[0042] 给定一个判定Z，该判定含有N个条件，N个条件中含有M个不相等条件，M个不相M M等条件的真值表中的2 个用例Ci组成用例集合S，i∈[1，2]；每一个条件对应一个非空有限独立对结果集合Rk(i∈[1，N])，Rk中的元素为独立对P，独立对P包含两个用例Ci、Cj，M
i，j ∈[1，2]；由N个独立对Pk中的所有用例构成集合D，任意Pk∈Rk，k∈[1，N]；满足集合元素个数|D|最小的D为最小独立对集合；M、N为自然数。

[0043] 独立对求解模块，用于根据唯一原因法或者屏蔽法求解各个条件对应的独立对。

[0044] 最小独立对集合求解模块，用于从每个条件对应的独立对中选择一个进行组合生成独立对集合，并选择独立对集合中元素最少的独立对集合作为最小独立对集合。

[0045] 修正条件/判定覆盖测试模块，还用于统计最小测试集的修正条件/判定覆盖的覆盖率；如果根据覆盖率判定需要补充测试用例，则在剩余的最小独立对集合选取至少一个通知测试用例生成模块生成对应的测试用例作为补充。

[0046] 本发明具备较高的效率，可以大幅度减少MC/DC测试的成本，避免了生成大量的测试用例以及对测试用例进行精简的过程。

附图说明

[0047] 图1是本发明提供的示例判定(A and B or C)的MC/DC最小独立对集合求解过程；

[0048] 图2是本发明提供的处理流程以及处理结果；

[0049] 图3是本发明提供的判定(A and B)or(C and D)的表达式树表示；

[0050] 图4是本发明提供的函数process(condition_index，OPT_LIST)的流程图；

[0051] 图5是本发明提供的一种计算机软件白盒测试的实现方法流程图。

具体实施方式

[0052] 下面结合附图，对本发明做进一步的详细描述。

[0053] 在一个判定中，不论采用何种求解方法，最终得到的结果中，每一个条件的独立对的数量可能会比较多(特别是采用屏蔽法求解的时候)，如附图1的示例程序所示(括号中的一对数字分别对应判定真值表中的索引值，每一个索引值代表各个条件的一个布尔取值组合，称为一个用例(case)，以此与实际生成的测试用例相区分)。前文提到，在MC/DC测试中，根据独立对的求解结果生成测试用例，但是由于生成测试用例本身是一个复杂的过程，而且独立对的结果众多，如果对每一对独立对都生成两个测试用例，势必会大幅度提高测试成本。与此同时，不难发现不同条件的独立对结果之间存在一些重复，因此在生成测试用例之后，通常还需要对测试用例进行精化，以求找到一个最小测试集。但现有的寻找最小测试集的技术方案所能达到的效果都不理想。如上所述，测试过程中，往往是先利用独立对求解结果生成测试用例，之后再对测试用例进行精简，以获得最小测试集。如果能够从已有的独立对结果中找到一个最小的独立对集合，在这个最小独立对集合中，判定中每一个条件都能从这个集合中找到自己的独立对，然后由这个最小独立对集合出发生成测试用例，这样可以直接得到最小测试集。如果当前的最小独立对集合各个条件的取值由于存在强弱耦合的情况而不能产生测试用例，也只需要补充少量的测试用例即可。

[0054] 正是基于上述原因，本发明提出了一种基于MC/DC测试标准的软件白盒测试的实现方法，并且给出了具体的实施步骤以及系统。在此实现方法中，提出了MC/DC最小独立对集合的概念，与以往的实现方法不同的是，我们先由各个条件的独立对结果求得判定的最小独立对集合，由最小独立对集合直接指导生成最小测试集。该方法的结果如图2所示。首先给出MC/DC最小独立对集合的定义：

[0055] 给定一个判定Z，该判定含有N个条件(其中含有M个不相等的条件，亦即任意两M M个条件之间不存在强耦合，M≤N)：其真值表中的2 个用例Ci(i∈[1，2])组成用例集合S；每一个条件对应一个非空有限独立对结果集合Ri(i∈[1，N])，Ri中的元素即独立对PM
包含两个用例Ci，Cj(i，j∈[1，2])。由N个独立对Pi(任意Pi∈Ri，i∈[1，N])中的所有用例构成集合D。满足集合元素个数|D|最小的D称为当前判定的MC/DC最小独立对集合。如果选取的独立对Pi之间没有重复的用例，则|D|达到最大值2N；反之，如果抽取的任意两个独立对Pi之间都存在重复的用例，则|D|达到最小值N+1，参考图1的示例。

[0056] 在此有必要说明一下最小测试集和最小独立对集合之间的区别和联系。所谓最小测试集，非形式化的定义是：在此测试集中，每一个条件的独立对都能从中找到，以此来保证能对判定中每一个条件进行有效地测试，而且要求最小测试集中的测试用例数量最少。在某些学术文章中，也把本发明所提的最小独立对集合称之为最小测试集；本发明中最小测试集特指最小测试用例集合，一般而言，最小独立对集合中的用例与最小测试集中的测试用例一一对应，少数情况下需要在最小测试集中补充部分测试用例。从最小独立对集合到最小测试用例集合之间只需测试用例生成这一过程，目前已有相关的工具和方法可以直接完成此过程，例如基于模型检测的测试用例生成方法等。在本发明中，视最小独立对集合和最小测试集为两个不同的概念。

[0057] 本发明提出的支持最小测试集生成的MC/DC最小独立对集合及其求解方法有如下特点：

[0058] 1)MC/DC最小独立对集合的求解基于所有条件的独立对结果，与具体的求解方法无关(不论是采用唯一原因法还是屏蔽法)，因此该方法具有广泛适用性；

[0059] 2)最终求解得到的MC/DC最小独立对集合有多个可选，如果由于条件取值之间存在耦合的关系，当前选用的MC/DC最小独立对集合生成的最小测试集不能满足测试要求，既可增加若干测试用例补充当前的测试集，也可选其他MC/DC最小独立对集合作为参考。为生成最终的最小测试集提供支持；

[0060] 3)本发明是以搜索遍历的方式查找最优也即最小的独立对集合，求解方法本身的特点可以保证得到最小的集合。

[0061] 在本发明中，独立对的表示形式是基于判定的真值表索引，一个形如(Aand B or C)这样的判定，它的真值表的形式如图1中所示。一个条件数量为N(前提是条件之间不存N N在强耦合)的判定的真值表中有2 项，本发明称之为2 个用例(case)。对于上述的判定，不难知道{(A＝F、B＝T、C＝F)；(A＝T、B＝T、C＝F)}这一对取值组合构成了当前判定中条件A以唯一原因法求解的一对MC/DC独立对；对应真值表中的1和6两个用例，所以也可以用(1，6)表示条件A的一对MC/DC独立对，下文中都将以这种方式来表述独立对。
实际上，在求解MC/DC独立对的过程中，可以不需要基于真值表来分析，采用判定的表达式树也同样可以基于不同的方法来求解MC/DC独立对。例如判定(A andB)or(C and D)的表达式树如附图3所示。如果采用唯一原因法求解独立对，则条件A的独立对可以表示为：

[0062]

[0063] 不过，上述的独立对形式仍然可以与其真值表(表1)对应起来：

[0064] (T and T)or？与真值表中的(13、14、15、16)对应；

[0065] (F and？)or F与真值表中的(1、2、3、5、6、7)对应。

[0066] 所以，本发明采用真值表的索引号来表示独立对具备一般性和通用性。

[0067] 表1判定((A and B)or(C and D))的真值表

[0068]CASE A B C D RESULT
1 F F F F F
2 F F F T F
3 F F T F F
4 F F T T T
5 F T F F F
6 F T F T F
7 F T T F F
8 F T T T T
9 T F F F F
10 T F F T F
11 T F T F F
12 T F T T T
13 T T F F T
14 T T F T T
15 T T T F T
16 T T T T T

[0069] 在通过不同的方法(唯一原因法或者屏蔽法)得到判定中各个条件的独立对之后，独立对将以配对的形式(A，B)保存下来。不论采用何种分析方法，最终所得到的独立对的结果均可以表示成类似的形式，如附图1所示。如果其中某个条件不存在独立对(这种情况特别是在采用唯一原因法求解独立对时会出现)，则此方法首先给出警告信息，说明判定中某个条件的独立对不存在，接下来对余下所有条件求解相应的MC/DC最小独立对集合。

[0070] 求解MC/DC最小独立对集合的过程中遍历搜索所有条件的独立对，遍历的方式可以基于采用循环的方式也可以采用递归的方式。在计算的过程中同时维护一个工作集(WORK_LIST)保存搜索结果，同时维护一个工作集的集合用于存储找到的所有可能的MC/DC最小独立对集合。工作集中的元素是整数，对应真值表中的索引号，基本的数据结构如下：

[0071] OPT_LIST：一个工作集(WORK_LIST)，称为临时工作集，用来保存计算过程中找到的所有用例。一遍搜索完成之后，临时工作集中的元素表示当前这一遍搜索过程中所找到的MC/DC最小独立对集合。

[0072] LIST_SET：实际上代表了一个WORK_LIST的数组，也是一个MC/DC最小独立对集合的集合，其中的一个元素代表一个最小独立对集合。由于求得的MC/DC最小独立对集合可能会有多个，此集合用来保存搜索过程中找到的所有的MC/DC最小独立对集合。

[0073] OPT_SIZE：为简单起见，本发明称其为优化量。用来记录当前搜索过程中临时工作集中的元素个数。这个值在理想状况下的最小值是N+1(其中N表示判定中条件的数量)，最大为2N，因此OPT_SIZE∈[N+1，2N]。

[0074] 搜索算法 的主要流程 如图4所示，这 是一个递归 调用处理函 数Process(condition_index，OPT_LIST)的过程，该递归函数包括两个参数：condition_index代表条件的索引，取值范围是[1，N]；OPT_LIST就是临时工作集。具体的求解步骤如下：

[0075] 步骤1：进行数据结构的初始化操作：将临时工作集OPT_LIST和工作集数组LIST_SET初始化为空，将优化量OPT_SIZE初始化为一个预先设定的大数G(G＞＞2N)，确保OPT_SIZE在初始时一定大于2N。

[0076] 步骤2：递归调用搜索函数，具体步骤可以分为：

[0077] 步骤2.1：由于搜索算法Process()是一个递归的过程，如果当前传入的条件的索引值超过了判定中条件的总数，说明当前OPT_LIST中的元素已经装满，转步骤3进行处理。

[0078] 步骤2.2：尝试从当前条件的独立对结果中选取第i对独立对，i是用在遍历当前条件独立对结果过程中的一个计数器，亦即独立对结果的索引。若i已经超出了结果中独立对的总数，则说明当前条件独立对结果中的所有独立对已经遍历过了，程序返回；否则程序继续执行。

[0079] 步骤2.3：将选取的独立对中的两个元素加入到OPT_LIST中，条件索引值condition_index加一，即处理下一个条件。继续递归调用函数Process()，之后将之前加入的两个元素从OPT_LIST中删除。独立对结果索引值i加1，转步骤2.1。

[0080] 步骤3：搜索的中间结果保存在OPT_LIST中，一次遍历的结果需要首先进行判断才能加入到工作集数组LIST_SET中，具体步骤可以分为：

[0081] 步骤3.1：如果OPT_LIST中的元素个数不大于优化量OPT_SIZE，则说明当前这一次遍历找到的MC/DC最小独立对集合优于或者等于前面已经找到的最小集合。否则说明此次遍历一无所获，程序返回。

[0082] 步骤3.2：进一步判断，如果OPT_LIST中的元素个数小于优化量OPT_SIZE，则说明找到了更小更优的集合，因此，将LIST_SET中已经存储的LIST全部清空，更新OPT_SIZE的值。否则直接转步骤3.3。

[0083] 步骤3.3：将新的OPT_LIST拷贝添加到工作集数组LIST_SET中，此次遍历结束，程序返回。

[0084] 搜索算法的详细流程包括：

[0085] 步骤401，判断当前条件索引值是否大于条件总数，如果是，执行步骤407，否则执行步骤402；

[0086] 步骤402，独立对结果索引值初始化为1；

[0087] 步骤403，判断独立对结果索引值是否已经超出当前条件的独立对总数，如果是，返回，否则执行步骤404；

[0088] 步骤404，从当前条件的独立对结果中取出独立对结果索引值对应的独立对；将其中的两个元素加入临时工作集中；

[0089] 步骤405，条件索引值加一，同时自递归调用本函数；

[0090] 步骤406，将之前加入的两个元素从临时工作集中删除；独立对结果索引值加一，执行步骤403；

[0091] 步骤407，判断临时工作集中的元素个数是否小于等于优化量，如果是，执行步骤408，否则返回；

[0092] 步骤408，判断临时工作集中的元素个数是否小于优化量，如果是，执行步骤409，否则执行步骤410；

[0093] 步骤409，遇到更优的最小集合，此时将工作集数组清空；将优化量设置为临时工作集中元素个数大小；

[0094] 步骤410，拷贝并且将临时工作集加入到工作集数组中，返回。

[0095] 本发明提出的基于MC/DC测试标准的测试方法的实现如下：

[0096] 步骤501，根据独立对的定义，采用唯一原因法或者屏蔽法求解判定表达式中各个条件的独立对；

[0097] 步骤502，调用搜索算法求解判定的最小独立对集合；

[0098] 步骤503，任意选用最小独立对集合中的一个，最小独立对集合是一个用例(case)集合，为该集合中的每一个用例(case)生成对应的测试用例，这一步可以采用基于模型检测的方法实现；得到一个最小测试集；

[0099] 步骤504，用最小测试集对源程序进行MC/DC测试，统计其MC/DC覆盖率，若覆盖率没有达到测试要求(如没有100％的覆盖到判定中的所有条件)则说明覆盖不充分，此时需补充测试用例，可在剩余的最小独立对集合中，按需选取一个或者若干集合，提取这些集合中与未覆盖条件相关的独立对生成测试用例作为当前最小测试集的补充。

[0100] 为了更直观的阐述MC/DC最小独立对集合的求解流程，可以参考图2中的流程以及图1中对于示例判定(A and B or C)求解MC/DC最小独立对集合的结果。

[0101] 本发明还提供了一种计算机软件白盒测试的实现系统，包括：

[0102] 独立对求解模块，用于求解判定布尔表达式中各个条件的独立对；

[0103] 最小独立对集合求解模块，用于基于各个条件对应的独立对求解判定最小独立对集合，求解判定出的最小独立对集合构成参考用例集合；

[0104] 测试用例生成模块，用于选择参考用例集合中的一个最小独立对集合，并生成与该最小独立对集合对应的测试用例集合，该测试用例集合即为最小测试集；

[0105] 修正条件/判定覆盖测试模块，用于用最小测试集对源程序进行修正条件/判定覆盖测试；

[0106] 最小独立对集合满足下述条件：

[0107] 给定一个判定Z，该判定含有N个条件，N个条件中含有M个不相等条件，M个不相M M等条件的真值表中的2 个用例Ci组成用例集合S，i∈[1，2]；每一个条件对应一个非空有限独立对结果集合Rk(i∈[1，N])，Rk中的元素为独立对P，独立对P包含两个用例Ci、M
Cj，i，j∈[1，2]；由N个独立对Pk中的所有用例构成集合D，任意Pk∈Rk，k∈[1，N]；满足集合元素个数|D|最小的D为最小独立对集合；M、N为自然数。

[0108] 本领域的技术人员在不脱离权利要求书确定的本发明的精神和范围的条件下，还可以对以上内容进行各种各样的修改。因此本发明的范围并不仅限于以上的说明，而是由权利要求书的范围来确定的。