一類最優(yōu)混合水平定位陣*

史冊(cè)， 陳光周, 曹勐

(1.上海立信會(huì)計(jì)金融學(xué)院 統(tǒng)計(jì)與數(shù)學(xué)學(xué)院，上海 201209；2.河南師范大學(xué) 數(shù)學(xué)與信息學(xué)院，河南 新鄉(xiāng) 453007;3.吉林大學(xué) 數(shù)學(xué)學(xué)院,吉林 長(zhǎng)春 130012)

1 引 言

在基于組件的軟件系統(tǒng)中,軟件故障通常是由于組件(因子)間交互作用而產(chǎn)生的.軟件系統(tǒng)可以看作一個(gè)復(fù)雜的邏輯系統(tǒng)，其正常工作會(huì)受到系統(tǒng)配置、系統(tǒng)內(nèi)部事件及外部輸入等諸多因素的影響;除此之外，這些因素之間的交互作用也可能會(huì)影響軟件系統(tǒng)的正常運(yùn)行.考慮一個(gè)具有k因素 (因子)的待測(cè)軟件系統(tǒng)(software under test，簡(jiǎn)稱SUT)，這些因子分別有vi種可能的水平選擇，其取值集合Vi=[0,vi-1],其中1≤i≤k. 稱一個(gè)k元組(a1,a2,…,ak)(ai∈Vi,1≤i≤k)為SUT的一條測(cè)試用例(test case).相應(yīng)的，稱由多個(gè)這樣的k元組所構(gòu)成的集合為SUT的一個(gè)測(cè)試用例集(test suite).

設(shè)N,t,k均為正整數(shù)且2≤t

定義1.1一個(gè)陣列A=(aij)(i∈IN,j∈Ik)稱為混合覆蓋陣(mixed covering arrays,MCA),簡(jiǎn)記為MCAλ(N;t,k,(v1,v2,…,vk)),若對(duì)每個(gè)t-維交互T，|ρA(T)|≥λ.換句話說(shuō),由列i1×i2×…×it標(biāo)定的N×t子陣列含Vi1×Vi2×…×Vit中每一個(gè)作為行向量的t-元組至少λ次,其中1≤i1

當(dāng)λ=1,省略其下標(biāo).不失一般性,總假定2≤v1≤v2≤…≤vk. 指數(shù)型記號(hào)v1s1v2s2…vksk用來(lái)表示有si個(gè)因子其水平數(shù)為vi. 當(dāng)混合覆蓋陣定義中任意t列包含每個(gè)有序t元組至少λ次替換為任意t列包含每個(gè)有序t元組重復(fù)同樣次數(shù)時(shí)，就給出了混合正交表定義，用MOAλ(N;t,k,(v1,v2,…,vk))[6]表示.

設(shè)混合覆蓋陣MCA(N;t,k,(v1,v2,…,vk))存在，不妨設(shè)為A. 對(duì)于具有k個(gè)因素，每個(gè)因素取值為vi(1≤i≤k)的待測(cè)軟件系統(tǒng)，按照如下方式生成一個(gè)測(cè)試用例集.A的每一個(gè)列對(duì)應(yīng)這個(gè)軟件系統(tǒng)的每一個(gè)因素，其每一個(gè)行向量對(duì)應(yīng)一條測(cè)試用例.因A含有N行，故含有N條測(cè)試用例，從而形成一個(gè)測(cè)試用例集.利用混合覆蓋陣作為測(cè)試用例集，其能夠根據(jù)測(cè)試結(jié)果獲取錯(cuò)誤的存在與否,這是發(fā)現(xiàn)軟件故障的重要一步，但其不能夠根據(jù)測(cè)試結(jié)果準(zhǔn)確獲取具體的錯(cuò)誤信息.從實(shí)際應(yīng)用角度來(lái)看，根據(jù)測(cè)試結(jié)果能夠確定出故障的具體位置是非常有意義的,因此2008年Colbourn和McClary[7]引入了定位陣(locating arrays，LA)的概念.

定義1.2[7]混合覆蓋陣MCAλ(N;t,k,(v1,v2,…,vk)),A=(aij) 稱為定位陣，記作(d,t)-LA(N;k,(v1,v2,…,vk)),若ρA(T1)=ρA(T2)?T1=T2,其中T1和T2是一個(gè)勢(shì)為d的t-維交互集合.

若v1=v2=…=vk=v,(d,t)-LA(N;k,(v1,v2,…,vk))簡(jiǎn)記為(d,t)-LA(N;k,v). 定位陣數(shù)(locating array number,LAN)是定位陣(d,t)-LA(N;k,(v1,v2,…,vk))存在的最小N,用(d,t)-LAN(k,(v1,v2,…,vk))表示.若混合水平定位陣中的N=(d,t)-LAN(k,(v1,v2,…,vk)),則稱之為最優(yōu)的(optimal).當(dāng)用(d,t)-LA(N;k,(v1,v2,…,vk))作為測(cè)試用例集時(shí)，若軟件故障恰好是由d個(gè)t-維交互觸發(fā)的，則這些錯(cuò)誤均能從測(cè)試結(jié)果完全被確定出來(lái).定位陣不但應(yīng)用于定位軟件系統(tǒng)因子交互引起的錯(cuò)誤故障，而且還應(yīng)用于度量、測(cè)試以及無(wú)線網(wǎng)絡(luò)測(cè)試等[8-9].

最近,TANG等人建立了(1,t)-LAN(k,v)的下界，并刻畫了達(dá)到這個(gè)下界的最優(yōu)定位陣的組合特征[10].但在現(xiàn)實(shí)生活中，軟件系統(tǒng)的不同因子的水平取值可能是不相同的.從實(shí)際應(yīng)用角度考慮，定位陣(d,t)-LA(N;k,(v1,v2,…,vk))具有更強(qiáng)的適用性.定位陣(d,t)-LA(N;k,(v1,v2,…,vk))還沒(méi)有被系統(tǒng)研究.事實(shí)上，其存在的下界無(wú)從知曉.本文將研究定位陣(1,t)-LA(N;k,(v1,v2,…,vk)),其中2

2 最優(yōu)性和組合刻畫

稱達(dá)到引理2.1的定位陣為最優(yōu)的.為了描述最優(yōu)混合水平定位陣的組合特性，需要給出指標(biāo)兩兩不同的混合正交表的定義.

定義2.1設(shè)A是混合正交表MOA(N;t,k,(v1,v2,…,vk)),其中2

利用這類混合正交表可以產(chǎn)生如下定位陣.

定理2.1若MOA*(N;t,k,(v1,v2,…,vk))存在，其中2

證明假設(shè)A是混合正交表MOA*(N;t,k,(v1,v2,…,vk)),則對(duì)于任意兩個(gè)不同t-維交互T1和T2,若T1和T2的列指標(biāo)集合相同，則ρA(T1)≠ρA(T2)；若T1和T2的列指標(biāo)集合不同，則|ρA(T1)|≠|(zhì)ρA(T2)|,進(jìn)而ρA(T1)≠ρA(T2).顯然,T1=T2?ρA(T1)=ρA(T2).因而ρA(T1)=ρA(T2)?T1=T2. 證畢.

證明由定理2.1知，定位陣(1,t)-LA(N;k,(v1,v2,…,vk))存在.其最優(yōu)性由引理2.1得到.證畢.

3 主要結(jié)果

本節(jié)將利用定理2.2給出若干最優(yōu)定位(1,t)-LA(N;k,(v1,v2,…,vk))的存在性結(jié)果.因?yàn)樵趯?shí)際應(yīng)用中,主要關(guān)注強(qiáng)度為2和3的定位陣，因此，我們給出強(qiáng)度為2和3的混合正交表MOA(N;t,k,(v1,v2,…,vk))的存在性結(jié)果.下文中記號(hào)l.c.m表示最小公倍數(shù).

引理3.1[6]設(shè)2≤v1≤v2≤v3. 則

(1)MOA(N;2,2,(v1,v2))存在當(dāng)且僅當(dāng)v1v2|N;

(2)MOA(N;2,3,(v1,v2,v3))存在當(dāng)且僅當(dāng)M|N,其中M=l.c.m{v1v2,v1v3,v2v3}.

引理3.2[11-12]設(shè)2

(1)MOA*(N;2,4,(v1,v2,v3,v4))存在當(dāng)且僅當(dāng)M1|N,其中M1=l.c.m{αβ：{α,β}?{v1,v2,v3,v4}};

(2)MOA*(N;2,5,(v1,v2,v3,v4,v5))存在當(dāng)且僅當(dāng)M2|N,其中M2=l.c.m{αβ：{α,β}?{v1,v2,v3,v4,v5}};

(3)MOA*(N;2,6,(v1,v2,v3,v4,v5,v6))存在當(dāng)且僅當(dāng)M3|N,其中M3=l.c.m{αβ：{α,β}?{v1,v2,v3,v4,v5,v6}}.

引理3.4[13]設(shè)2

利用定理2.2和引理3.1-3.4可以得到如下最優(yōu)混合水平定位陣.

定理3.1設(shè)2

(1) (1,2)-LA(v2v3;3,(v1,v2,v3))存在，其中v2v3=l.c.m{v1v2,v1v3,v2v3};

(2) (1,2)-LA(v3v4;4,(v1,v2,v3,v4))存在，其中v3v4=l.c.m{αβ：{α,β}?{v1,v2,v3,v4}}; (3) (1,2)-LA(v4v5;5,(v1,v2,v3,v4,v5))存在，其中v4v5=l.c.m{αβ：{α,β}?{v1,v2,v3,v4,v5}};

(4) (1,2)-LA(v5v6;6,(v1,v2,v3,v4,v5,v6))存在，其中v5v6=l.c.m{αβ：{α,β}?{v1,v2,v3,v4,v5,v6}}.

定理3.3設(shè)2