基于QIS的二值覆盖表生成方法

基于qis的二值覆盖表生成方法
技术领域
1.本发明涉及软件或硬件测试技术领域，具体为基于qis的二值覆盖表生成方法。


背景技术：

2.现今，有越来越多软件的输入参数的取值都是离散的，参数间的不同离散取值组合影响、控制这软件的行为，软件故障通常由这些参数的取值组合触发，如果希望通过软件测试来保障软件的质量，需要尽可能多地测试这些参数的取值组合，然而，组合的个数随着参数个数和各个参数取值个数的增加而呈指数增长，测试空间将是巨大的，要想穷尽地测试是不现实的，实际中，80％以上的故障是由两个或者三个参数的取值组合触发，因而只需测试部分组合即能达到很好的测试效果。
3.组合测试即测试组合的方法，一般事先指定要测试的组合的大小，即测试强度t，然后生成t-way覆盖表，使得任一大小为t的组合至少能出现在覆盖表的某一行，即实现t-way覆盖。t-way覆盖表能测出所有大小为t以及小于t的故障组合，有效性很高，在工业界具有广泛的应用，测试人员总是期望生成尽可能小的覆盖表，但最小覆盖表的生成是一个np-hard问题。
4.现有的覆盖表生成算法大多是基于贪心策略，每次生成一条测试用例，选择测试用例的标准是尽可能覆盖最多的未覆盖的组合，这种一次一行的方法生成的覆盖表通常较大，而forbes等人提出的ipog-f算法[1]则采用一次一列的策略，逐次增加列数，在ipog-f算法中，确定覆盖力度t之后，1)生成t列来覆盖t个参数的所有t-way组合；2)增加一列，增加的列长度与已有的矩阵行数相同，同时增加的列要能覆盖尽可能多的组合；3)如果当前生成的矩阵覆盖了所有需要覆盖的组合，则继续第二步进行水平方向上的拓展，否则，进行垂直方向上的拓展，增加一行测试用例来尽可能覆盖更多的未被覆盖的组合，然后重复第三步，直到生成指定列数的覆盖表。
[0005]
ipog-f算法的一次一列策略能大大减少组合搜索的空间，在时间开销得到显著缩小的同时，生成的大部分覆盖表是已知最小的，但本质上，ipog-f算法仍需维持一个未覆盖组合表，据此通过贪心算法来生成具有最大组合覆盖数的列或者行，容易陷入局部最优，因此，如何生成一个尽可能小的覆盖表一直是组合测试的重要研究领域，针对上述问题，发明人提出基于qis的二值覆盖表生成方法用于解决上述问题。


技术实现要素：

[0006]
(一)解决的技术问题
[0007]
为了解决如何能生成更加小的覆盖表，在实际中保证测试效果的同时能更好地减少测试成本的问题；本发明的目的在于提供基于qis的二值覆盖表生成方法。
[0008]
(二)技术方案
[0009]
为解决上述技术问题，本发明采用如下技术方案：基于qis的二值覆盖表生成方法，包括以下步骤：
[0010]
sa1、本方法是基于集合学中的qualitatively independent set，对于大小为n的集合s，其有两个子集a、b，如果a∩b、皆不为空，则称a、b是2-independent的；
[0011]
sa2、若集合f中的元素为s的子集，且f中的任意两个子集都是2-independent的，则称f为2-qualitatively independent的，显然，可以根据2-qualitatively independent的f构造一个0/1矩阵，大小为n
×
|f|，f中的子集对应各个列，如果f中第i个子集中含有元素j，则矩阵的i列j行取值为0，否则取值为1；
[0012]
sa3、当|f|在n固定时达到最大，此0/1矩阵则能在行数一定时覆盖最多的二值参数，也即用最少的行数覆盖|f|个参数的2-way组合，最大的|f|与n的大小关系已有公式给出[2]，但对于一般情况的t-qualitatively independent中t》2的情形未有准确的公式和结论，是np-hard问题。
[0013]
sb1、我们首先需要确定s的大小n，即确定覆盖表的行数，然后选择搜索范围，即确定s的哪些子集作为搜索目标，称其为备选子集，它们构成备选集p；
[0014]
sb2、接着指定p中若干s的子集作为种子子集，当然也可以不指定种子子集，指定种子后检查这些种子是否满足pseudo-t-qualitatively independent的性质，如果不满足则重新指定种子或者不指定种子，满足则继续下一步；
[0015]
sb3、接下来确定搜索深度depth，每次从p中选择depth个备选子集，先检查这depth个备选子集是否满足pseudo-t-qualitatively independent的性质，如果不满足，则重新选下一组depth个备选子集；如果是，则将这depth个备选子集与种子一起加入空的t-qi集，然后遍历p中的备选子集进行搜索，每次选择一个不在t-qi集中的备选子集，检查其与t-qi集中的任两个子集是否满足pseudo-t-independent关系，如果满足，则将其加入t-qi集，不满足则不添加，然后继续遍历p中剩余的备选子集；
[0016]
sb4、直到所有的备选子集都被遍历一遍，则结束此次搜索，然后记录t-qi集的大小和其中的备选子集，这样当p中每depth个备选子集组合都被搜索完后，选择最大的3-qi集来构造3-way二值覆盖表；
[0017]
sb5、构造方法同2-qualitatively independent情况类似，t-qi集中的每一个备选子集对应每一列，备选子集中含有的数字对应的行赋值0，否则赋值为1，最后加上一行全0和一行全1，从而最终生成有(n+2)行的t-way二值覆盖表。
[0018]
本方法涉及的相关名词如下：
[0019]
sc1、|f|：即集合f的大小；
[0020]
sc2、备选子集：即选择作为搜索目标的s的子集，这些子集构成备选集p，选择s的部分子集作为搜索目标，可以有效减少搜索范围，减少搜索时间；
[0021]
sc3、pseudo-t-independent：以t＝3为例，若集合a、b、c∈s，其independent：以t＝3为例，若集合a、b、c∈s，其皆不为空，称a、b、c满足pseudo-3-independent关系，从组合覆盖的角度讲，a、b、c满足pseudo-3-independent关系指a、b、c对应的0/1矩阵的三列之间的001、010、011、100、101、110组合都能被覆盖到，同理，
对于pseudo-t-independent，若集合a1、a2、
…
、a
t
∈s，令bi＝ai若(2
t-2)个交集皆不为空，则称a1、a2、
…
、a
t
满足pseudo-t-independent关系；
[0022]
sc4、pseudo-t-qualitatively independent：若集合f中任意t个组合都满足pseudo-t-independent关系，称f是pseudo-t-qualitatively independent的；
[0023]
3-sc5、t-qi集：即满足pseudo-t-qualitatively independent性质的子集集合，算法最终用其来生成t-way二值覆盖表。
[0024]
(三)有益效果
[0025]
与现有技术相比，本发明的有益效果在于：
[0026]
1、采用一次一列的策略，基于集合学中的qualitatively independent set数学方法，进行水平方向上的拓展，在固定行数情况下，采用搜索算法而非贪心算法来搜索最大的列数，能获得很小的覆盖表，与ipog-f算法相比，我们的算法能生成更小的覆盖表。
[0027]
2、本方法能在现有算法基础上进一步生成更小的覆盖表，在保障测试有效性的同时减少测试开销，表1给出了本方法与现有的ipog-f算法在生成覆盖表性能上的比较，表中的生成的覆盖表的行数从10开始，比较在相同行数下能覆盖的参数能有多大，这里每个参数有2个不同取值，覆盖表的覆盖强度为3，这些覆盖表实例是比较覆盖表生成算法性能时常用的实例，这里均使用ipog-f方法[1]生成，具体的覆盖表可以从[3]处获得，本方法选定的搜索深度为3，未指定种子备选组合，从表1可以看出，本方法在性能上较现有技术有显著的提升，生成的覆盖表比现有技术都要小不少，且随着n的增加，提升的效果越明显。
附图说明
[0028]
为了更清楚地说明本发明实施例或现有技术中的技术方案，下面将对实施例或现有技术描述中所需要使用的附图作简单地介绍，显而易见地，下面描述中的附图仅仅是本发明的一些实施例，对于本领域普通技术人员来讲，在不付出创造性劳动的前提下，还可以根据这些附图获得其他的附图。
[0029]
图1为本发明流程图。
具体实施方式
[0030]
下面将结合本发明实施例中的附图，对本发明实施例中的技术方案进行清楚、完整地描述，显然，所描述的实施例仅仅是本发明一部分实施例，而不是全部的实施例。基于本发明中的实施例，本领域普通技术人员在没有做出创造性劳动前提下所获得的所有其他实施例，都属于本发明保护的范围。
[0031]
如图1所示，本发明提供了基于qis的二值覆盖表生成方法，包括以下步骤：
[0032]
sa1、本方法是基于集合学中的qualitatively independent set，对于大小为n的集合s，其有两个子集a、b，如果a∩b、皆不为空，则称a、b是2-independent的。
[0033]
sa2、若集合f中的元素为s的子集，且f中的任意两个子集都是2-independent的，则称f为2-qualitatively independent的，显然，可以根据2-qualitatively independent
的f构造一个0/1矩阵，大小为n
×
|f|，f中的子集对应各个列，如果f中第i个子集中含有元素j，则矩阵的i列j行取值为0，否则取值为1。
[0034]
sa3、当|f|在n固定时达到最大，此0/1矩阵则能在行数一定时覆盖最多的二值参数，也即用最少的行数覆盖|f|个参数的2-way组合，最大的|f|与n的大小关系已有公式给出[2]，但对于一般情况的t-qualitatively independent中t》2的情形未有准确的公式和结论，是np-hard问题。
[0035]
sb1、我们首先需要确定s的大小n，即确定覆盖表的行数，然后选择搜索范围，即确定s的哪些子集作为搜索目标，称其为备选子集，它们构成备选集p。
[0036]
sb2、接着指定p中若干s的子集作为种子子集，当然也可以不指定种子子集，指定种子后检查这些种子是否满足pseudo-t-qualitatively independent的性质，如果不满足则重新指定种子或者不指定种子，满足则继续下一步。
[0037]
sb3、接下来确定搜索深度depth，每次从p中选择depth个备选子集，先检查这depth个备选子集是否满足pseudo-t-qualitatively independent的性质，如果不满足，则重新选下一组depth个备选子集；如果是，则将这depth个备选子集与种子一起加入t-qi集，然后遍历p中的备选子集进行搜索，每次选择一个不在t-qi集中的备选子集，检查其与t-qi集中的任两个子集是否满足pseudo-t-independent关系，如果满足，则将其加入t-qi集，不满足则不添加，然后继续遍历p中剩余的备选子集。
[0038]
sb4、直到所有的备选子集都被遍历一遍，则结束此次搜索，然后记录t-qi集的大小和其中的备选子集，这样当p中每depth个备选子集组合都被搜索完后，选择最大的t-qi集来构造t-way二值覆盖表。
[0039]
sb5、构造方法同2-qualitatively independent情况类似，t-qi集中的每一个备选子集对应每一列，备选子集中含有的数字对应的行赋值0，否则赋值为1，最后加上一行全0和一行全1，从而最终生成有(n+2)行的t-way二值覆盖表。
[0040]
本方法涉及的相关名词如下：
[0041]
sc1、|f|：即集合f的大小。
[0042]
sc2、备选子集：即选择作为搜索目标的s的子集，这些子集构成备选集p，选择s的部分子集作为搜索目标，可以有效减少搜索范围，减少搜索时间。sc3、pseudo-t-independent：以t＝3为例，若集合a、b、c∈s，其3为例，若集合a、b、c∈s，其皆不为空，称a、b、c满足pseudo-3-independent关系，从组合覆盖的角度讲，a、b、c满足pseudo-3-independent关系指a、b、c对应的0/1矩阵的三列之间的001、010、011、100、101、110组合都能被覆盖到，同理，对于pseudo-t-independent，若集合a1、a2、
…
、a
t
∈s，令bi＝ai若(2
t-2)个交集皆不为空，则称a1、a2、
…
、a
t
满足pseudo-t-independent关系。
[0043]
sc4、pseudo-t-qualitatively independent：若集合f中任三个组合都满足pseudo-t-independent关系，称f是pseudo-t-qualitatively independent的。
[0044]
sc5、t-qi集：即满足pseudo-t-qualitatively independent性质的子集集合，算法最终用其来生成t-way二值覆盖表。
[0045]
综上所述，对于大小为(n+2)
×
k的t-way二值覆盖表，将其最后的两行，分别取为
全0和全1，则除去最后的两行，表中的每一列取值为0的行号构成的集合可以看作大小为n的集合s＝{1，2，..，n}的子集，且这k个子集构成的集合f满足pseudo-t-qualitatively independent性质，本方法就是通过搜索s的子集来寻找最大的f，从而构造最小的t-way二值覆盖表，这一逐列搜索的方法流程图参见图1，具体步骤如下：
[0046]
1)选定t，确定要生成的二值覆盖表的覆盖强度为t。
[0047]
2)选定n，确定要生成的t-way覆盖表的行数为(n+2)。
[0048]
3)确定搜索范围，选取集合s＝{1，2，..，n}的部分子集作为备选子集，构成备选集p。
[0049]
4)确定是否要选择s的部分子集作为搜索种子，如果要选取s的子集作为种子，则进入步骤5)，否则进入步骤6)。
[0050]
5)令种子个数为c，若c小于t，则检查这c个种子是否满足pseudo-c-independent关系，如果满足，则进入步骤6)，否则回到步骤4)；如果c不小于t，则检查这些种子是否是pseudo-t-qualitatively independent的，如果是则进入步骤6)，否则回到步骤4)。
[0051]
6)如果有指定的合法种子，则将p中含有的种子子集删除。
[0052]
7)确定搜索深度depth，将p中每个子集标上序号，序号从1开始，然后生成集合{1，2，
…
，|p|}的所有大小为depth的子集，这里的每一个大小为depth的子集称为搜索子集，它们构成搜索集d。
[0053]
8)创建max-t-qi集，令其为空。
[0054]
9)判断搜索集d是否为空，是则进入步骤13)；否则进入步骤10)。
[0055]
10)令t-qi集为空，如果有合法种子，则将其加入t-qi集，然后在d中选择一个搜索子集，将其对应的p中的备选子集加入t-qi集，并将d中的此搜索子集删除，接着检查此时的t-qi集是否合法。令当前t-qi集大小为g，若g小于t，则检查这g个子集是否满足pseudo-g-independent关系,如果不是则非法，回到步骤9)，是则合法，进入步骤11)；若g不小于t，则检查这些子集是否是pseudo-t-qualitatively independent的，如果不是则非法，回到步骤9)，是则合法，进入步骤11)。
[0056]
11)从序号1开始，遍历p中每一个备选子集：如果当前子集存在于t-qi集中，则遍历下一个备选子集；否则令当前t-qi集大小为h，若h小于(t-1)，则检查这h个子集与当前遍历的子集是否满足pseudo-(h+1)-independent关系,如果不是则放弃当前子集，遍历下一个子集，否则将此子集加入t-qi集中，然后继续遍历；若h不小于(t-1)，则检查当前子集与t-qi集中任意(t-1)个子集是否都满足pseudo-t-independent关系，不是则放弃当前子集，继续遍历，否则将当前子集加入t-qi集中，继续遍历。这样一直遍历p中每一个子集，遍历完后，进入步骤12)。
[0057]
12)当前t-qi集大小是否大于max-t-qi集的大小，是则将当前t-qi集作为新的max-t-qi集，回到步骤9)。
[0058]
13)依据max-t-qi集构造覆盖表。令k为max-t-qi集的大小，构造大小为n
×
k的矩阵，max-t-qi集中的每一个元素对应矩阵中的每一列，若max-t-qi集的第j个子集中含有数字i，则在矩阵的i行j列位置上赋值为0，否则赋值为1，最后加上一行全0和一行全1，即构成了一个t-way二值覆盖表。
[0059]
14)停止。
[0060]
实施操作：
[0061]
不妨设定n＝8，覆盖强度t为3，下面用本方法生成行数为n+2＝10的3-way二值覆盖表。
[0062]
选定搜索范围为集合s＝{1，2，..，8}的所有大小为4的子集，则备选集p的大小为确定种子子集为{{1，2，3，4}}，因选取的种子中只有一个子集，可直接使用。将p中含有的种子删除，然后给p中每个子集从1开始排序，这里依据子集的自然顺序排序，因而p中的子集{1，2，3，5}的序号为1，{1，2，3，6}的序号为2，
…
，{5，6，7，8}的序号为69，搜索深度depth选为2，则搜索集d的大小为d中集合依次为{1，2}、{1，3}、
…
、{68，69}。
[0063]
种子子集为{{1，2，3，4}}，大小为1，显然是合法的种子集，不用重新选择种子。
[0064]
开始进行搜索，选择搜索集中第一个集合{1，2}，并将其从d中删除。此搜索子集对应的p中子集为{{1，2，3，5}，{1，2，3，6}}。构建3-qi集并令其为空，将种子{{1，2，3，4}}和搜索子集{1，2}对应的p中的子集{{1，2，3，5}，{1，2，3，6}}加入3-qi集中，其大小为3，接下来检查3-qi集是否是pseudo-3-qualitatively independent的。
[0065]
集合{1，2，3，4}的补集为{5，6，7，8}；集合{1，2，3，5}的补集为{4，6，7，8}；集合{1，2，3，6}的补集为{4，5，7，8}。发现{1，2，3，4}与{1，2，3，5}和{4，5，7，8}的交集为空，不满足pseudo-3-independent关系，因此结束搜索子集{1，2}的搜索，选择下一个搜索子集{1，3}进行搜索，并将其从d中删除。
[0066]
搜索子集{1，3}对应的初始3-qi集为{{1，2，3，4}，{1，2，3，5}，{1，2，3，7}}，检查发现其不满足pseudo-3-independent关系，因此结束搜索子集{1，3}的搜索，选择下一个搜索子集{1，4}进行搜索，并将其从d中删除。
[0067]
…
[0068]
搜索子集{10，21}对应的初始3-qi集为{{1，2，3，4}，{1，2，5，6}，{1，3，5，7}}，对应的补集分别为{5，6，7，8}、{3，4，7，8}、{2，4，6，8}，发现：
[0069]
{1，2，3，4}∩{1，2，5，6}∩{2，4，6，8}＝{2}，
[0070]
{1，2，3，4}∩{3，4，7，8}∩{1，3，5，7}＝{3}，
[0071]
{1，2，3，4}∩{3，4，7，8}∩{2，4，6，8}＝{4}，
[0072]
{5，6，7，8}∩{1，2，5，6}∩{1，3，5，7}＝{5}，
[0073]
{5，6，7，8}∩{1，2，5，6}∩{2，4，6，8}＝{6}，
[0074]
{5，6，7，8}∩{3，4，7，8}∩{1，3，5，7}＝{7}，
[0075]
这6个交集皆不为空，此时3-qi集是pseudo-3-qualitatively independent的，可以进入下一步的遍历搜索。
[0076]
遍历从编号1的备选子集{1，2，3，5}开始，其不在3-qi集中，但其与3-qi集中的{1，2，3，4}，{1，2，5，6}不满足pseudo-3-independent关系，因此直接遍历下一个备选子集；
[0077]
选择编号为2的备选子集{1，2，3，6}
…
[0078]
…
[0079]
选择编号为29的备选子集{1，4，6，7}，其补集为{2，3，5，8}，检查其与3-qi集中任两个子集是否满足pseudo-3-independent关系，如下：
[0080]
{1，2，3，4}∩{1，2，5，6}∩{2，3，5，8}＝{2}，
[0081]
{1，2，3，4}∩{3，4，7，8}∩{1，4，6，7}＝{4}，
[0082]
{1，2，3，4}∩{3，4，7，8}∩{2，3，5，8}＝{3}，
[0083]
{5，6，7，8}∩{1，2，5，6}∩{1，4，6，7}＝{6}，
[0084]
{5，6，7，8}∩{1，2，5，6}∩{2，3，5，8}＝{5}，
[0085]
{5，6，7，8}∩{3，4，7，8}∩{1，4，6，7}＝{7}，
[0086]
{1，2，3，4}∩{1，3，5，7}∩{2，3，5，8}＝{3}，
[0087]
{1，2，3，4}∩{2，4，6，8}∩{1，4，6，7}＝{4}，
[0088]
{1，2，3，4}∩{2，4，6，8}∩{2，3，5，8}＝{2}，
[0089]
{5，6，7，8}∩{1，3，5，7}∩{1，4，6，7}＝{7}，
[0090]
{5，6，7，8}∩{1，3，5，7}∩{2，3，5，8}＝{5}，
[0091]
{5，6，7，8}∩{2，4，6，8}∩{1，4，6，7}＝{6}，
[0092]
{1，2，5，6}∩{1，3，5，7}∩{2，3，5，8}＝{5}，
[0093]
{1，2，5，6}∩{2，4，6，8}∩{1，4，6，7}＝{6}，
[0094]
{1，2，5，6}∩{2，4，6，8}∩{2，3，5，8}＝{2}，
[0095]
{3，4，7，8}∩{1，3，5，7}∩{1，4，6，7}＝{7}，
[0096]
{3，4，7，8}∩{1，3，5，7}∩{2，3，5，8}＝{3}，
[0097]
{3，4，7，8}∩{2，4，6，8}∩{1，4，6，7}＝{4}，
[0098]
这些交集皆不为空，因而编号为29的备选子集{1，4，6，7}与3-qi中任两个子集都满足pseudo-3-independent关系，所以可以将其加入3-qi集，继续遍历下一个备选子集。
[0099]
…
[0100]
结束这一次遍历后，再从d中选择一个搜索子集，并将其从d中删除，然后继续此次搜索。
[0101]
…
[0102]
直到将d中所有的搜素集都搜索过后，结束搜索。
[0103]
最后得到的max-3-qi集为{{1，2，3，4}，{1，2，5，6}，{1，4，5，7}，{2，4，5，8}，{3，6，7，8}}，其大小为5，据此，我们可以构建如下大小为10
×
5的3-way二值覆盖表：
[0104]
表1覆盖表生成方法的性能比较
[0105][0106]
表2一个3-way二值覆盖表
[0107] p1p2p3p4p5r100011r200101r301110
r401001r510001r610110r711010r811100r900000r
10
11111
[0108]
表2的3-way二值覆盖表能覆盖5个参数，只需10行，比ipog-f算法所需的12行要小2行，因而本方法在这一实例上性能更优。
[0109]
引用文献：
[0110]
[1].forbes m，lawrence j，lei y，et al.refining the in-parameter-order strategy for constructing covering arrays[j].journal of research of the national institute of standards and technology，2008，113(5)：287-297
[0111]
[2].kleitman d j，spencer j.families of k-independent sets[j].discrete mathematics，1973，6(3)：255-262.
[0112]
[3].covering arrays generated by ipog-f.
[0113]
显然，本领域的技术人员可以对本发明进行各种改动和变型而不脱离本发明的精神和范围。这样，倘若本发明的这些修改和变型属于本发明权利要求及其等同技术的范围之内，则本发明也意图包含这些改动和变型在内。

技术特征：
1.基于qis的二值覆盖表生成方法，其特征性在于：包括以下步骤：sa1、本方法是基于集合学中的qualitatively independent set，对于大小为n的集合s，其有两个子集a、b，如果a∩b、皆不为空，则称a、b是2-independent的；sa2、若集合f中的元素为s的子集，且f中的任意两个子集都是2-independent的，则称f为2-qualitatively independent的，显然，可以根据2-qualitatively independent的f构造一个0/1矩阵，大小为n
×
|f|
，f中的子集对应各个列，如果f中第i个子集中含有元素j，则矩阵的i列j行取值为0，否则取值为1；sa3、当|f|在n固定时达到最大，此0/1矩阵则能在行数一定时覆盖最多的二值参数，也即用最少的行数覆盖|f|个参数的2-way组合，最大的|f|与n的大小关系已有公式给出[2]，但对于一般情况的t-qualitatively independent中t＞2的情形未有准确的公式和结论，是np-hard问题。2.如权利要求1所述的基于qis的二值覆盖表生成方法，其特征在于，具体操作如下：sb1、我们首先需要确定s的大小n，即确定覆盖表的行数，然后选择搜索范围，即确定s的哪些子集作为搜索目标，称其为备选子集，它们构成备选集p；sb2、接着指定p中若干s的子集作为种子子集，当然也可以不指定种子子集，指定种子后检查这些种子是否满足pseudo-t-qualitatively independent的性质，如果不满足则重新指定种子或者不指定种子，满足则继续下一步；sb3、接下来确定搜索深度depth，每次从p中选择depth个备选子集，先检查这depth个备选子集是否满足pseudo-t-qualitatively independent的性质，如果不满足，则重新选下一组depth个备选子集；如果是，则将这depth个备选子集与种子一起加入空的t-qi集，然后遍历p中的备选子集进行搜索，每次选择一个不在t-qi集中的备选子集，检查其与t-qi集中的任两个子集是否满足pseudo-t-independent关系，如果满足，则将其加入t-qi集，不满足则不添加，然后继续遍历p中剩余的备选子集；sb4、直到所有的备选子集都被遍历一遍，则结束此次搜索，然后记录t-qi集的大小和其中的备选子集，这样当p中每depth个备选子集组合都被搜索完后，选择最大的t-qi集来构造t-way二值覆盖表；sb5、构造方法同2-qualitatively independent情况类似，t-qi集中的每一个备选子集对应每一列，备选子集中含有的数字对应的行赋值0，否则赋值为1，最后加上一行全0和一行全1，从而最终生成有(n+2)行的t-way二值覆盖表。3.如权利要求2所述的基于qis的二值覆盖表生成方法，其特征在于，本方法涉及的相关名词如下：sc1、|f|：即集合f的大小；sc2、备选子集：即选择作为搜索目标的s的子集，这些子集构成备选集p，选择s的部分子集作为搜索目标，可以有效减少搜索范围，减少搜索时间；sc3、pseudo-t-independent：以t＝3为例，若集合a、b、c∈s，其independent：以t＝3为例，若集合a、b、c∈s，其皆不为空，称a、b、c满足pseudo-3-independent关系，从组合覆盖的角度讲，a、b、c满足pseudo-3-independent关系
指a、b、c对应的0/1矩阵的三列之间的001、010、011、100、101、110组合都能被覆盖到，同理，对于pseudo-t-independent，若集合a1、a2、...、a
t
∈s，令b
i
＝a
i
或若(2
t-2)个交集皆不为空，则称a1、a2、...、a
y
满足pseudo-t-independent关系；sc4、pseudo-t-qualitatively independent：若集合f中任意t个组合都满足pseudo-t-independent关系，称f是pseudo-t-qualitatively independent的；sc5、t-qi集：即满足pseudo-t-qualitatively independent性质的子集集合，算法最终用其来生成t-way二值覆盖表。

技术总结
本发明公开了基于QIS的二值覆盖表生成方法，涉及软件或硬件测试技术领域；而本发明包括以下步骤：SA1、本方法是基于集合学中的Qualitatively Independent Set，SA2、若集合F中的元素为S的子集，且F中的任意两个子集都是2-independent的，则称F为2-Qualitatively Independent的，SA3、当|F|在n固定时达到最大，此0/1矩阵则能在行数一定时覆盖最多的二值参数，也即用最少的行数覆盖|F|个参数的2-way组合，最大的|F|与n的大小关系已有公式给出[2]，但对于一般情况的t-Qualitatively Independent中t＞2的情形未有准确的公式和结论，是NP-hard问题。本发明，能生成更加小的覆盖表，在实际中保证测试效果的同时能更好地减少测试成本。少测试成本。少测试成本。


技术研发人员：钮鑫涛 周成乘 吴化尧 聂长海
受保护的技术使用者：南京大学
技术研发日：2023.03.31
技术公布日：2023/8/4