| 主权项 |
1.一种两两覆盖组合软件测试用例集生成方法，其特征在于主要包括以下步骤：(1)在软件测试中，测试人员根据待测软件系统SUT的需求规格说明书，确定相应的测试需求说明书，在软件测试需求说明书中可以获得影响待测软件系统SUT的各种因素和因素之间的约束限制，这些因素可以用集合F表示为F＝{f<sub>1</sub>，f<sub>2</sub>，…，f<sub>i</sub>，…，f<sub>n</sub>}，n为影响待测软件系统的因素的个数，i为1到n中的任意一个值，其中因素f<sub>i</sub>假设经过等价类划分后包含p<sub>i</sub>个离散的值，则因素f<sub>i</sub>可能的取值可以用集合V<sub>i</sub>表示<img file="FSA00000449626400011.GIF" wi="541" he="91" />其中v<sub>i1</sub>表示因素f<sub>i</sub>的第一个离散值，v<sub>i2</sub>表示因素f<sub>i</sub>的第二个离散值，<img file="FSA00000449626400012.GIF" wi="71" he="59" />表示因素f<sub>i</sub>的第p<sub>i</sub>个离散值，则该待测软件系统SUT因素的所有离散值共有P个<img file="FSA00000449626400013.GIF" wi="250" he="117" />约束限制集合可以用C表示C＝{c<sub>1</sub>，c<sub>2</sub>，…，c<sub>m</sub>}，m为约束限制的个数，待测软件系统SUT的一个测试用例test可以用n元组表示为test＝(v<sub>1</sub>，v<sub>2</sub>，…，v<sub>n</sub>)，其中v<sub>1</sub>∈V<sub>1</sub>，v<sub>2</sub>∈V<sub>2</sub>，v<sub>n</sub>∈V<sub>n</sub>且满足约束限制C；(2)对待测软件系统SUT因素的所有离散值按照因素从左到右的顺序进行编号，第一个因素f<sub>1</sub>的第一个离散值v<sub>11</sub>编号为1，第二个离散值v<sub>12</sub>的编号为2，第p<sub>i</sub>个离散值<img file="FSA00000449626400014.GIF" wi="67" he="55" />编号为p<sub>i</sub>，依次类推，第i个因素f<sub>i</sub>的第一个离散值v<sub>i1</sub>编号为因素f<sub>1</sub>到f<sub>i-1</sub>的离散值个数之和加1，最后一个因素f<sub>n</sub>的最后一个离散值的编号为P，因此第i个因素f<sub>i</sub>的离散值的编号集合可以用集合H<sub>i</sub>表示为<img file="FSA00000449626400015.GIF" wi="493" he="64" />这样我们就可以用编号来代表该待测软件系统所有的可能离散取值；(3)考虑到待测软件系统SUT中任意两个因素间的相互作用，都可能对系统产生重要影响，测试用例集TS需要保证覆盖任意两个因素间所有的取值组合且满足约束限制，待测软件系统SUT中任意两个因素覆盖对可以用二元关系矩阵T＝(t<sub>i，j</sub>)<sub>P×P</sub>表示，其中P表示待测软件系统的因素的全部离散值个数，i，j为离散值的编号，t<sub>i，j</sub>表示第i个离散值和第j个离散值覆盖对是否要覆盖，t<sub>i，j</sub>＝1表明第i个离散值和第j个离散值对需要覆盖，t<sub>i，j</sub>＝0表明第i个离散值和第j个离散值对不需要覆盖，不需要覆盖的原因可以是同一因素内部的离散值对，也可以是违背了约束限制C的不同因素之间的离散值对；(3)对上述待测软件系统SUT，在粒子群中每个粒子代表一个生成的测试用例集，则粒子群中第i个粒子l<sub>i</sub>的编码为：l<sub>i</sub>＝<(l<sub>i11</sub>，l<sub>i12</sub>，…，l<sub>i1n</sub>)，(l<sub>i21</sub>，l<sub>i22</sub>，…，l<sub>i2n</sub>)，…，(l<sub>iq1</sub>，l<sub>iq2</sub>，…，l<sub>iqn</sub>)>，其中l<sub>ijk</sub>∈{V<sub>k</sub>中离散值的编号}，q是要生成的测试用例集中的测试用例的数量，该编码的长度为q×n，(l<sub>i11</sub>，l<sub>i12</sub>，…，l<sub>i1n</sub>)代表该测试用例集中的第1个测试用例，(l<sub>i21</sub>，l<sub>i22</sub>，…，l<sub>i2n</sub>)代表该测试用例集中的第2个测试用例，(l<sub>iq1</sub>，l<sub>iq2</sub>，…，l<sub>iqn</sub>)代表该测试用例集中的第q个测试用例；(4)设定基于离散粒子群算法的参数，所述的参数包括粒子群中粒子的数量N，生成的测试用例集中测试用例的个数q，随机选取各因素可取离散值初始化每个粒子的位置，令迭代次数t＝1，开始两两覆盖组合软件测试用例集生成；(5)若粒子l<sub>i</sub>其编码为：l<sub>i</sub>＝<(l<sub>i11</sub>，l<sub>i12</sub>，…，l<sub>i1n</sub>)，(l<sub>i21</sub>，l<sub>i22</sub>，…，l<sub>i2n</sub>)，…，(l<sub>iq1</sub>，l<sub>iq2</sub>，…，l<sub>iqn</sub>)>，其对应的二元覆盖关系矩阵T＝(t<sub>i，j</sub>)<sub>P×P</sub>，从l<sub>i</sub>的编码中可以准确地获得该粒子所代表的测试用例集所覆盖的两两覆盖对以及其出现的次数，若覆盖对<i，j>出现w次，则将关系矩阵T中的t<sub>i，j</sub>的值减去w，计算关系矩阵T中值为1的元素的个数<img file="FSA00000449626400021.GIF" wi="453" he="127" />若t<sub>i，j</sub>＝1就是该粒子代表的测试用例集没有覆盖的对数，则每个粒子所代表的生成的测试用例集的适应值f(l<sub>i</sub>)＝UnCount(l<sub>i</sub>)；(6)对每个粒子，将当前适应值和该粒子局部最优位置的适应值l<sub>i</sub>Best进行比较，若其值小于l<sub>i</sub>Best，则将粒子的当前位置其作为该粒子当前的局部最优位置LocBest<sub>i</sub>＝l<sub>i</sub>，且该粒子的当前适应值作为该粒子的局部最优适应值l<sub>i</sub>Best＝f(l<sub>i</sub>)＝UnCount(l<sub>i</sub>)；(7)对每个粒子，将其局部最优适应值l<sub>i</sub>Best和全局经历过的最优位置的适应值LGBest进行比较，若第i个粒子l<sub>i</sub>的局部最优值l<sub>i</sub>Best小于LGBest，则将其局部最优位置作为当前粒子群的全局最优位置GBest＝l<sub>i</sub>，该粒子的局部最优适应值作为粒子群的全局最优适应值LGBest＝l<sub>i</sub>Best；(8)根据下面的方法更新每个粒子的各维的位置，粒子l<sub>i</sub>当前位置为l<sub>i</sub>＝<(l<sub>i11</sub>，l<sub>i12</sub>，…，l<sub>i1n</sub>)，(l<sub>i21</sub>，l<sub>i22</sub>，…，l<sub>i2n</sub>)，…，(l<sub>iq1</sub>，l<sub>iq2</sub>，…，l<sub>iqn</sub>)>，更新之后的位置为l<sub>i</sub>′＝<(l<sub>i11</sub>′，l<sub>i12</sub>′，…，l<sub>i1n</sub>′)，(l<sub>i21</sub>′，l<sub>i22</sub>′，…，l<sub>i2n</sub>′)，…，(l<sub>iq1</sub>′，l<sub>iq2</sub>′，…，l<sub>iqn</sub>′)>更新的方法为：计算各个离散值出现的次数，l<sub>ijk</sub>出现的次数为num(l<sub>ijk</sub>)则<maths num="0001"><![CDATA[<math><mrow><msup><msub><mi>l</mi><mi>ijk</mi></msub><mo>′</mo></msup><mo>=</mo><mfenced open='{' close=''><mtable><mtr><mtd><mi>Rand</mi><mrow><mo>(</mo><mi>prob</mi><mrow><mo>(</mo><msub><mi>h</mi><mrow><mi>k</mi><mn>1</mn></mrow></msub><mo>)</mo></mrow><mo>,</mo><msub><mi>h</mi><mrow><mi>k</mi><mn>1</mn></mrow></msub><mo>)</mo></mrow></mtd></mtr><mtr><mtd><mi>Rand</mi><mrow><mo>(</mo><mi>prob</mi><mrow><mo>(</mo><msub><mi>h</mi><mrow><mi>k</mi><mn>2</mn></mrow></msub><mo>)</mo></mrow><mo>,</mo><msub><mi>h</mi><mrow><mi>k</mi><mn>2</mn></mrow></msub><mo>)</mo></mrow></mtd></mtr><mtr><mtd><mo>.</mo><mo>.</mo><mo>.</mo></mtd></mtr><mtr><mtd><mi>Rand</mi><mrow><mo>(</mo><mi>prob</mi><mrow><mo>(</mo><msub><mi>h</mi><msub><mi>kp</mi><mi>k</mi></msub></msub><mo>)</mo></mrow><mo>,</mo><msub><mi>h</mi><msub><mi>kp</mi><mi>k</mi></msub></msub><mo>)</mo></mrow></mtd></mtr></mtable></mfenced><mo>,</mo></mrow></math>]]></maths>Rand(prob(h<sub>k1</sub>)，h<sub>k1</sub>)表示以prob(h<sub>k1</sub>)为概率随机取h<sub>k1</sub>，Rand(prob(h<sub>k2</sub>)，h<sub>k2</sub>)表示以prob(h<sub>k2</sub>)为概率随机取h<sub>k2</sub>，…，<img file="FSA00000449626400032.GIF" wi="523" he="60" />表示以<img file="FSA00000449626400033.GIF" wi="240" he="61" />为概率随机取<img file="FSA00000449626400034.GIF" wi="144" he="89" /><img file="FSA00000449626400035.GIF" wi="1560" he="169" /><img file="FSA00000449626400036.GIF" wi="973" he="160" />其中n为该粒子代表的测试用例集中包含的测试用例的个数，p<sub>k</sub>为第k个因素的离散值的个数，num(h<sub>kj</sub>)粒子中第h<sub>kj</sub>个离散值出现的次数；(9)如果当前的迭代次数t等于最大迭代次数MAX，或者当前粒子群的LGBest的UnCount达到期望的值0，则全局最优值PGBest所对应的粒子所代表的测试用例集即为两两覆盖组合软件测试用例集生成方法生成的最优测试用例集，结束循环；否则，t＝t+1，返回第(5)步。 |
