嚴(yán)悍等
摘 要: 針對(duì)場(chǎng)景測(cè)試法中多場(chǎng)景切換代價(jià)優(yōu)化問(wèn)題,在復(fù)合狀態(tài)分析、邏輯蘊(yùn)含概念基礎(chǔ)上,從測(cè)試場(chǎng)景結(jié)構(gòu)分解的角度,給出狀態(tài)蘊(yùn)含和場(chǎng)景蘊(yùn)含關(guān)系的定義及推論,由場(chǎng)景蘊(yùn)含形成場(chǎng)景蘊(yùn)含圖SIG,然后采用圖論方法求解優(yōu)化路徑。給出系統(tǒng)化處理方法,并與其他方法比較。最后實(shí)例驗(yàn)證該方法的有效性。
關(guān)鍵字: 場(chǎng)景測(cè)試法; 蘊(yùn)含關(guān)系; 路徑優(yōu)化; 場(chǎng)景蘊(yùn)含圖; 狀態(tài)蘊(yùn)含
中圖分類(lèi)號(hào): TN911?34; TP311 文獻(xiàn)標(biāo)識(shí)碼: A 文章編號(hào): 1004?373X(2015)12?0118?05
0 引 言
場(chǎng)景測(cè)試法[1](Scenario Test)也稱(chēng)為用例測(cè)試法(Use Case Test),是一種軟件黑盒測(cè)試方法,廣泛用于復(fù)雜交互式軟件測(cè)試,尤其適用于嵌入式軟件的分布式測(cè)試。分布式測(cè)試中人員、設(shè)備和測(cè)試對(duì)象都具有特定的地理分布要求,導(dǎo)致測(cè)試場(chǎng)景的構(gòu)建和撤銷(xiāo)代價(jià)較大。如何通過(guò)減少場(chǎng)景數(shù)量、避免重建場(chǎng)景、優(yōu)化場(chǎng)景切換路徑來(lái)減少代價(jià),提高測(cè)試效率,已成為一個(gè)重要且亟待解決的問(wèn)題。場(chǎng)景測(cè)試法依據(jù)測(cè)試需求形成多個(gè)不同測(cè)試場(chǎng)景。測(cè)試實(shí)施中先建立場(chǎng)景、執(zhí)行測(cè)試用例、撤銷(xiāo)場(chǎng)景,再建下一個(gè)場(chǎng)景,如此循環(huán)直到完成所有場(chǎng)景。對(duì)于多場(chǎng)景執(zhí)行次序目前缺乏科學(xué)有效的定義和方法指導(dǎo)。多場(chǎng)景執(zhí)行次序如果選擇不當(dāng),將導(dǎo)致重復(fù)建設(shè)和浪費(fèi)。當(dāng)測(cè)試失敗時(shí)往往需要重建多個(gè)場(chǎng)景后重測(cè),代價(jià)更大。
Jacobson在文獻(xiàn)[2?3]中提出用例驅(qū)動(dòng)的軟件工程思想,在此基礎(chǔ)上IBM Rational公司在RUP2000中提出場(chǎng)景測(cè)試法。該方法未說(shuō)明多場(chǎng)景執(zhí)行的次序。文獻(xiàn)[4]采用用例行為矩陣度量場(chǎng)景的優(yōu)先級(jí),通過(guò)該優(yōu)先級(jí)對(duì)多個(gè)場(chǎng)景進(jìn)行排序和路徑合并,從而減少測(cè)試代價(jià)。文獻(xiàn)[5]先依據(jù)用例事件流建立事件有向樹(shù),然后對(duì)該樹(shù)進(jìn)行路徑搜索,最后合并子路徑,提高場(chǎng)景重用率。文獻(xiàn)[6]依據(jù)業(yè)務(wù)流選擇部分場(chǎng)景優(yōu)先測(cè)試,減少測(cè)試代價(jià)的同時(shí)保證功能可用性。以上研究大多側(cè)重于測(cè)試場(chǎng)景的行為特征,而忽視場(chǎng)景結(jié)構(gòu)特性。本文通過(guò)研究測(cè)試場(chǎng)景結(jié)構(gòu)、復(fù)合狀態(tài)分析、邏輯蘊(yùn)含概念,通過(guò)狀態(tài)蘊(yùn)含和場(chǎng)景蘊(yùn)含關(guān)系,探索一種新思路來(lái)減少多場(chǎng)景切換代價(jià)。
1 測(cè)試場(chǎng)景的構(gòu)成與場(chǎng)景蘊(yùn)含
首先分析場(chǎng)景簡(jiǎn)單切換的問(wèn)題,給出狀態(tài)蘊(yùn)含和場(chǎng)景蘊(yùn)含的關(guān)系。
1.1 測(cè)試場(chǎng)景的簡(jiǎn)單切換
在一般場(chǎng)景測(cè)試法中,測(cè)試一個(gè)場(chǎng)景s1前構(gòu)建該場(chǎng)景,測(cè)試完成后需撤銷(xiāo)該場(chǎng)景。場(chǎng)景切換就是撤銷(xiāo)前一個(gè)場(chǎng)景并構(gòu)建下一個(gè)場(chǎng)景的過(guò)程,如圖1所示。
圖1中假設(shè)場(chǎng)景s1的構(gòu)建代價(jià)為b1,撤銷(xiāo)代價(jià)為d1,場(chǎng)景s2的構(gòu)建代價(jià)為b2,撤銷(xiāo)代價(jià)為d2,那么在由s1切換到s2時(shí),切換代價(jià)可量化為d1+b2,由s2切換到s1時(shí),代價(jià)為d2+b1。這種切換稱(chēng)為簡(jiǎn)單切換。這種切換可能導(dǎo)致重復(fù)構(gòu)建/撤銷(xiāo)。以s1切換到s2為例,如果s1中的部分對(duì)象在s2中也要使用,那么切換時(shí)就額外增加了撤銷(xiāo)和重建的代價(jià)。
簡(jiǎn)單切換的好處是可在任意兩個(gè)場(chǎng)景之間進(jìn)行切換,缺點(diǎn)是代價(jià)高。
將場(chǎng)景作為結(jié)點(diǎn),簡(jiǎn)單切換作為有向邊,切換代價(jià)作為邊權(quán)值,就可形成一個(gè)賦權(quán)有向圖,而且該圖是有向完全圖。基于該圖選擇任何路徑都無(wú)法得到優(yōu)化,原因是簡(jiǎn)單切換邊不能表示場(chǎng)景之間內(nèi)在的蘊(yùn)含關(guān)系。
1.2 場(chǎng)景和狀態(tài)蘊(yùn)含關(guān)系
定義1:測(cè)試場(chǎng)景。一個(gè)測(cè)試場(chǎng)景s是針對(duì)一個(gè)或幾個(gè)用例的測(cè)試需求,由一組語(yǔ)境對(duì)象組成的執(zhí)行環(huán)境,這些對(duì)象具有特定的類(lèi)型、個(gè)體及其狀態(tài)的要求。場(chǎng)景s的語(yǔ)境對(duì)象的集合記為c(s)。
圖2表示測(cè)試場(chǎng)景中的語(yǔ)境對(duì)象的性質(zhì)。
圖2 測(cè)試場(chǎng)景的構(gòu)成
圖2中一個(gè)測(cè)試場(chǎng)景包含一個(gè)或多個(gè)語(yǔ)境對(duì)象,而且每個(gè)語(yǔ)境對(duì)象都具有類(lèi)型、個(gè)體及其狀態(tài)的限定。語(yǔ)境對(duì)象按類(lèi)別可劃分為:測(cè)試人員、測(cè)試設(shè)備、測(cè)試對(duì)象。其中,測(cè)試對(duì)象可能是一套受測(cè)軟件,或者一組構(gòu)件,或者一組對(duì)象,或者單個(gè)對(duì)象(最簡(jiǎn)單場(chǎng)景)。
由定義1可知,兩個(gè)測(cè)試場(chǎng)景之間的差別就是其語(yǔ)境對(duì)象之間的差別,即對(duì)象類(lèi)型、對(duì)象個(gè)體及其狀態(tài)的差別。下面分析對(duì)象狀態(tài)之間關(guān)系及其對(duì)測(cè)試用例(test case,下稱(chēng)測(cè)例)執(zhí)行的作用機(jī)制。
UML狀態(tài)機(jī)定義了一個(gè)對(duì)象的2個(gè)狀態(tài)s1s2之間可能具有子狀態(tài)的復(fù)合關(guān)系。假設(shè)s1是s2的一個(gè)子狀態(tài),若處于s1態(tài)則必處于s2態(tài),反之不然[7]。
定義2:狀態(tài)蘊(yùn)含。設(shè)一個(gè)語(yǔ)境對(duì)象有狀態(tài)s1和s2,若s1是s2的一個(gè)子狀態(tài),則s1s2有狀態(tài)蘊(yùn)含關(guān)系,記作s1→s2。
直觀理解,若s1→s2,則s2態(tài)表示較簡(jiǎn)單場(chǎng)景,s1態(tài)較復(fù)雜且具有更多屬性限制要求,即針對(duì)s1態(tài)測(cè)試的判定斷言比針對(duì)s2更多。
推論1:一個(gè)測(cè)例tc對(duì)s1s2態(tài)分別測(cè)試,有s1→s2,若s2測(cè)試失敗,則s1也失敗,記為fail(tc,s2)→fail(tc,s1)。
直觀理解,若較簡(jiǎn)單場(chǎng)景測(cè)試失敗,則較復(fù)雜場(chǎng)景也失敗。
證明,因s1→s2,s1驗(yàn)證需要比s2更多判定斷言,且增加的斷言(記為s1.newAssert)都以合取式出現(xiàn)。假設(shè)s2的斷言為s2.assert,那么s1的斷言式為s2.assert∧s1.newAssert。若s2測(cè)試失敗,則s2.assert為假,此時(shí)s1的斷言式也為假,故s1測(cè)試也失敗,證畢。
該推論的逆否形式也成立,若s1測(cè)試成功,則s2也成功,記為success(tc,s1)→succss(tc,s2)。
推論2:一個(gè)測(cè)例tc在s1s2兩個(gè)狀態(tài)分別測(cè)試,且有s1→s2,則應(yīng)先創(chuàng)建s2場(chǎng)景測(cè)試,再切換到s1場(chǎng)景測(cè)試。
這是推論1的一個(gè)簡(jiǎn)單延伸。先測(cè)試簡(jiǎn)單場(chǎng)景s2,后測(cè)試較復(fù)雜場(chǎng)景s1。若s2測(cè)試成功,再測(cè)試s1。若s2測(cè)試失敗,由推論1知,s1也推定失敗而無(wú)需再切換到更復(fù)雜場(chǎng)景,從而減少代價(jià)。該推論為多場(chǎng)景測(cè)試提供了優(yōu)化依據(jù):從較簡(jiǎn)單到復(fù)雜場(chǎng)景逐步測(cè)試,若測(cè)試成功則進(jìn)入子狀態(tài)來(lái)測(cè)試更復(fù)雜場(chǎng)景,而未撤銷(xiāo)任何語(yǔ)境對(duì)象,直接減少代價(jià);若測(cè)試失敗則可立即斷定從成功場(chǎng)景到失敗場(chǎng)景的新加斷言失敗,范圍小易分析原因,也減少測(cè)試代價(jià)。
推論3:設(shè)有兩個(gè)不同測(cè)例tc1,tc2,若tc1需測(cè)試狀態(tài)s1,tc2需測(cè)試狀態(tài)s2,且有s1→s2,則只需狀態(tài)s1就能滿(mǎn)足tc1和tc2的測(cè)試要求。
實(shí)際上,tc2測(cè)試s1與測(cè)試s2具有相同的判定斷言的結(jié)果。
證明:因tc2針對(duì)s2態(tài)測(cè)試,故tc2僅持有s2的判定斷言s2.assert。而tc1持有斷言為s2.assert∧s1.newAssert。由推理1,success(tc2,s1)→succss(tc2,s2),即tc2測(cè)試s1若成功,則測(cè)試s2也成功。若tc2測(cè)試s1失敗,則其斷言s2.assert判定為假,故此測(cè)試s2也失敗。兩者斷言判定結(jié)果相同,證畢。
由推論3可能將兩個(gè)測(cè)試場(chǎng)景合并為一個(gè),能同時(shí)滿(mǎn)足多個(gè)測(cè)例需求,減少測(cè)試場(chǎng)景數(shù)量,也就減少測(cè)試代價(jià)。
1.3 場(chǎng)景蘊(yùn)含關(guān)系
定義3:場(chǎng)景差。設(shè)s1,s2是2個(gè)測(cè)試場(chǎng)景,場(chǎng)景差是從場(chǎng)景s1切換到s2的語(yǔ)境對(duì)象的差別,記為c(s2)-c(s1)。
定義4:場(chǎng)景蘊(yùn)含。設(shè)s1,s2是兩個(gè)測(cè)試場(chǎng)景,c(s2)-c(s1)=M,若M=[?],或M非空,且M僅包含新建對(duì)象;或至少一個(gè)語(yǔ)境對(duì)象從場(chǎng)景s1到s2轉(zhuǎn)換為其一個(gè)子狀態(tài),即有狀態(tài)蘊(yùn)涵;前兩種情形兼有,則稱(chēng)場(chǎng)景s2蘊(yùn)含s1,記為s2→s1。
若c(s1)-c(s2)=[?],表示2個(gè)場(chǎng)景具有相同的對(duì)象類(lèi)別、數(shù)量和狀態(tài),此時(shí)2個(gè)場(chǎng)景s1s2互相蘊(yùn)含,語(yǔ)義上表示從測(cè)試等價(jià)類(lèi)角度看,這2個(gè)場(chǎng)景屬于同一類(lèi)。
直觀理解,兩個(gè)場(chǎng)景之間的蘊(yùn)含關(guān)系有4種情形:
(1) 相互蘊(yùn)含;
(2) 后場(chǎng)s2加入新對(duì)象;
(3) 后場(chǎng)s2中一個(gè)或多個(gè)語(yǔ)境對(duì)象轉(zhuǎn)入其子狀態(tài),往往添加屬性值或關(guān)聯(lián);
(4) 情形(2)、(3)并存。
推論4:場(chǎng)景蘊(yùn)涵關(guān)系是一種偏序關(guān)系。
證明:
(1) 自反。對(duì)于任一個(gè)場(chǎng)景s1,s1蘊(yùn)含s1,即s1→s1成立,證明略。
(2) 反對(duì)稱(chēng)。對(duì)于任意2個(gè)不同場(chǎng)景s1和s2,若s1→s2,則s2→s1不成立。
證明:反證法,假設(shè)s1→s2成立時(shí),s2→s1也成立,則由定義4可得c(s2)-c(s1)=M,c(s1)-c(s2)=M,則c(s1)=c(s2),s1與s2是相同場(chǎng)景,與前提矛盾,證畢。
(3) 傳遞性。對(duì)于任意3個(gè)不同場(chǎng)景s1、s2和s3,若s1→s2,s2→s3,則s1→s3。
證明:由定義4,可得c(s1)-c(s2)=M1,c(s2)-c(s3)=M2,兩式相加,得c(s1)-c(s3)=M1+M2,M1+M2滿(mǎn)足定義4中M的條件(子狀態(tài)的復(fù)合關(guān)系有傳遞性),故s1→s3成立。
2 路徑優(yōu)化方法
定義5:場(chǎng)景蘊(yùn)含圖SIG(Scenario Implication Graph)。一個(gè)場(chǎng)景蘊(yùn)含圖G={V,E}是一個(gè)有向圖,其中V是場(chǎng)景集合,E是有向邊集合,若e=
場(chǎng)景蘊(yùn)含圖中有向邊表示兩個(gè)場(chǎng)景之間的逆蘊(yùn)含關(guān)系,直觀理解為從較簡(jiǎn)單場(chǎng)景指向較復(fù)雜場(chǎng)景,但圖中取消了自反所導(dǎo)致的自回路。
推論5:場(chǎng)景蘊(yùn)含圖不存在回路。
證明:由推論4,場(chǎng)景蘊(yùn)含關(guān)系是一種偏序關(guān)系,在取消自回路的前提下,場(chǎng)景蘊(yùn)含圖是哈斯圖,哈斯圖無(wú)回路[8]。
推論6:一個(gè)場(chǎng)景蘊(yùn)含圖作為有向無(wú)環(huán)圖,若存在一條哈密爾頓路徑[8](Hamilton Path,簡(jiǎn)稱(chēng)H路徑),則該路徑就是優(yōu)化的場(chǎng)景切換路徑。
證明:
(1) 由H路徑定義可知,覆蓋所有場(chǎng)景一次且僅一次;
(2) H路徑從簡(jiǎn)單場(chǎng)景到復(fù)雜場(chǎng)景,由推論2可知,沿該路徑測(cè)試無(wú)論成功或失敗,場(chǎng)景切換代價(jià)都可控制到最低。
一個(gè)場(chǎng)景蘊(yùn)含圖不一定存在H路徑。若不連通則不存在H路徑。即便連通也不一定存在H路徑。對(duì)于一個(gè)有向無(wú)環(huán)圖,難以簡(jiǎn)單求解H路徑。文獻(xiàn)[9]給出一種復(fù)雜的求解方法。
因此本文主張,對(duì)有向無(wú)環(huán)圖先求其最長(zhǎng)路徑,嘗試覆蓋盡可能多的場(chǎng)景結(jié)點(diǎn)。若能覆蓋所有結(jié)點(diǎn)則得到一條H路徑;若不能覆蓋,所得到的最長(zhǎng)路徑也可作為次優(yōu)解。
推論7:場(chǎng)景蘊(yùn)含圖中存在入度為0的場(chǎng)景結(jié)點(diǎn)。證明略。
選擇入度為0的一個(gè)或多個(gè)場(chǎng)景作為起始結(jié)點(diǎn),尋求最長(zhǎng)路徑,再判斷處理。
如果圖中只有一個(gè)入度為0的結(jié)點(diǎn),則作為單源最長(zhǎng)路徑求解;如果有多個(gè)入度為0的結(jié)點(diǎn),則分別作為源結(jié)點(diǎn)求最長(zhǎng)路徑,然后在多條路徑中選擇最長(zhǎng)路徑。
下面算法是對(duì)無(wú)環(huán)有向圖求單源最長(zhǎng)路徑,采用廣度優(yōu)先搜索。然后找出最長(zhǎng)路徑。算法如下:
(1) 根據(jù)廣度優(yōu)先算法標(biāo)記每一個(gè)結(jié)點(diǎn)到源結(jié)點(diǎn)的距離并按距離的大小形成隊(duì)列。具體過(guò)程略。
(2) 從距離最大的結(jié)點(diǎn)開(kāi)始按距離遞減順序搜索父結(jié)點(diǎn),直至到源結(jié)點(diǎn),形成路徑。
輸入:排序后的場(chǎng)景隊(duì)列,按開(kāi)始場(chǎng)景的距離降序排列;
輸出:最長(zhǎng)路徑。
過(guò)程:path(R)
1. P := [?]
2. ENQUEUE(P,R.first)
3. d := R.first.d
4. for each vertex u in R
5. d := d-1
6. if u.d == d && u == P.last.super then
7. ENQUEUE(P,u)
8. end if
9. end for
10. return P
3 討論與比較
對(duì)一個(gè)場(chǎng)景蘊(yùn)含圖G的系統(tǒng)化處理方法如下:
情形1,不連通。有2種方案可選:
方案1:子圖分割,形成多個(gè)連通子圖,再分別對(duì)各連通子圖按情形2處理。
方案2:在圖中添加第2.1節(jié)討論的簡(jiǎn)單切換邊,每條邊添加邊權(quán)值,邊權(quán)值表示切換代價(jià),蘊(yùn)含邊的權(quán)值是新建對(duì)象和轉(zhuǎn)入子狀態(tài)操作的代價(jià),形成一個(gè)賦權(quán)有向圖,再求解貨郎擔(dān)問(wèn)題,即遍歷所有場(chǎng)景一次且僅一次,而且路徑邊權(quán)之和最小。
情形2,連通。求最長(zhǎng)路徑P,然后在圖G中去掉P中結(jié)點(diǎn)和邊,剩下子圖若連通則繼續(xù)求最長(zhǎng)路徑,若不連通則按情形1的子圖分割處理。
與其他相關(guān)方法進(jìn)行比較見(jiàn)表1。
4 實(shí)例驗(yàn)證
將該方法應(yīng)用于一個(gè)軟件測(cè)試實(shí)例,被測(cè)功能是開(kāi)發(fā)人員持續(xù)上傳新版本移動(dòng)應(yīng)用程序,使移動(dòng)用戶(hù)能持續(xù)更新版本。
功能需求:對(duì)于一個(gè)移動(dòng)應(yīng)用程序,服務(wù)器僅保留最新版本,包括一個(gè)apk文件,一個(gè)xml文件記錄當(dāng)前版本號(hào)以及版本說(shuō)明。apk的版本號(hào)應(yīng)與xml中版本號(hào)一致。開(kāi)發(fā)人員上傳新版本時(shí),應(yīng)在頁(yè)面上輸入新版本號(hào)及版本說(shuō)明,然后上傳apk文件。頁(yè)面輸入信息將記錄到xml文件中。
根據(jù)以上功能需求可識(shí)別該測(cè)試的基本流與備選流,描述如表2所示。
將基本流和備選流組合形成9個(gè)測(cè)試場(chǎng)景,如表3所示。分析場(chǎng)景間蘊(yùn)含關(guān)系,形成場(chǎng)景蘊(yùn)含圖,如圖3所示。為展示清楚,省略一些間接蘊(yùn)含關(guān)系。對(duì)圖3計(jì)算最長(zhǎng)路徑:場(chǎng)景6→場(chǎng)景5→場(chǎng)景7→場(chǎng)景1→場(chǎng)景4→場(chǎng)景8→場(chǎng)景9。該路徑未覆蓋場(chǎng)景3和2。根據(jù)第3節(jié)討論應(yīng)構(gòu)建賦權(quán)有向圖。
先確定權(quán)值量化規(guī)則如下:
(1) 添加或修改一個(gè)頁(yè)面屬性權(quán)值為1;
(2) 打包apk權(quán)值為5;
(3) 設(shè)置網(wǎng)絡(luò)權(quán)值為3。
然后構(gòu)建賦權(quán)有向圖,如圖4所示。
對(duì)圖4再計(jì)算路徑:場(chǎng)景6→場(chǎng)景5→場(chǎng)景7→場(chǎng)景1→場(chǎng)景4→場(chǎng)景8→場(chǎng)景3→場(chǎng)景2→場(chǎng)景9,此路徑邊權(quán)和為37。若9個(gè)場(chǎng)景簡(jiǎn)單隨機(jī)選擇,經(jīng)計(jì)算其平均邊權(quán)和為106。此實(shí)例的優(yōu)化率為[106-37106]=65%。采用文獻(xiàn)[5]的優(yōu)化率為44%。
5 結(jié) 語(yǔ)
本文從測(cè)試場(chǎng)景的結(jié)構(gòu)特征的角度,定義了場(chǎng)景蘊(yùn)含關(guān)系,基于蘊(yùn)含關(guān)系提出一種多場(chǎng)景測(cè)試路徑優(yōu)化方法,并給出針對(duì)場(chǎng)景蘊(yùn)含圖SIG的系統(tǒng)化解決方法。該方法適用于多場(chǎng)景測(cè)試,尤其是場(chǎng)景切換代價(jià)較大的嵌入式分布式系統(tǒng)測(cè)試。
參考文獻(xiàn)
[1] 杜慶峰.高級(jí)軟件測(cè)試技術(shù)[M].北京:清華大學(xué)出版社,2011.
[2] JACOBSON I. Object oriented software engineering: a use case driven approach [M]. USA: ACM Press, 1992.
[3] JACOBSON I. Basic use?case modeling [J]. The Road to the Unified Software Development Process, 2000, 18: 167?172.
[4] KIM Y, CARLSON C R. Scenario based integration testing for object?oriented software development [C]// Proceedings of 1999 Eighth Asian Test Symposium. [S.l.]: IEEE, 1999: 283?288.
[5] 潘建勇,陳邦興.基于場(chǎng)景的測(cè)試用例設(shè)計(jì)方法研究[J].通信技術(shù),2012,44(12):77?80.
[6] 劉春玲,雷海紅.基于場(chǎng)景的信息系統(tǒng)黑盒測(cè)試方法[J].信息與電子工程,2012,10(4):509?512.
[7] 劉佳,尹治本.基于對(duì)象狀態(tài)的面向?qū)ο筌浖y(cè)試方法研究[J].電腦知識(shí)與技術(shù),2008,4(35):2169?2170.
[8] 方世昌.離散數(shù)學(xué)[M].北京:高等教育出版社,2000.
[9] ADLEMAN L M. Molecular computation of solutions to combinatorial problems [J]. Science?AAAS?Weekly Paper, 1994, 266(5187): 1021?1023.