殷 脂

(上海電力大學(xué) 計算機科學(xué)與技術(shù)學(xué)院, 上海 200090)

軟件的可測試性是指軟件測試過程中,在給定的若干組輸入條件下,能夠發(fā)現(xiàn)錯誤的概率。對軟件可測試性的研究有助于確定軟件需要測試的程度,并以最合理的方式分配測試資源,設(shè)計測試策略,提高測試效率。此外,在軟件開發(fā)生命周期的早期階段,可測試性分析還可以為軟件結(jié)構(gòu)的設(shè)計過程提供指導(dǎo),從而降低測試成本,提高測試的可行性,進(jìn)而提高軟件的可靠性。

本文結(jié)合隨機圖理論,首先描述了面向?qū)ο蟮臄U展軟件可測試性模型;然后基于擴散感染免疫理論建立了軟件隨機圖模型;最后給出了軟件的可測試性形式化表達(dá),并提出了計算方法。

1 擴展的基于故障/失效模型的PIE技術(shù)

1.1 可測試性分析方法

從國際學(xué)術(shù)論文的理論角度來說,可測試性分析方法主要分為以下4種。

(1) 主要根據(jù)某一類流圖計算出圖中的各類結(jié)構(gòu)信息(結(jié)點、邊、環(huán)等),獨立于所選擇的測試策略以及程序的執(zhí)行,并利用測試結(jié)果對軟件的關(guān)鍵測試部分進(jìn)行識別和改進(jìn)[1]。

(2) 基于信息論和信息流圖,根據(jù)模塊的輸入輸出信息,對模塊的可控性和可觀測性進(jìn)行定量計算,以確定模塊的可測試性。

(3) 以PIE(Propagation analysis,Infection analysis and Execution analysis)技術(shù)為基本原型,分析程序的某個位置,計算其故障檢測概率,以反映可測試性。

(4) 基于UML類圖的面向?qū)ο筌浖治黾夹g(shù),主要利用UML類圖作為分析對象,通過掌握類之間復(fù)雜的依存關(guān)系來分析可測試性,并進(jìn)一步改進(jìn)UML類圖以提升軟件的可測試性。

1.2 基于故障/失效模型的PIE技術(shù)分析

根據(jù)VOAS M[2]提出的故障/失效模型,軟件失效只有在以下3個條件都發(fā)生時才會產(chǎn)生:輸入引起故障執(zhí)行;故障導(dǎo)致了錯誤的數(shù)據(jù)狀態(tài);數(shù)據(jù)狀態(tài)進(jìn)而傳導(dǎo)至輸出狀態(tài),使得用戶獲得非預(yù)期的結(jié)果。本文結(jié)合面向?qū)ο筌浖奶卣?以PIE技術(shù)為基礎(chǔ)原型,并將PIE技術(shù)中的位置概念擴展為對象,構(gòu)造軟件測試的故障/失效模型。

PIE技術(shù)的基礎(chǔ)模型及簡單分析如下。

(1)P表示若數(shù)據(jù)狀態(tài)更改不正確,則該更改將影響程序輸出的概率。在估算P值時,對跟蹤語句中的變量進(jìn)行賦值,以便在后繼執(zhí)行中使用,直至到達(dá)輸出結(jié)點,并記錄全部語句。這些語句的I值乘積即為P值。如果無法到達(dá)輸出節(jié)點,則P值為零。

(2)I表示如果程序的一部分發(fā)生了變化,那么這種變化將錯誤地改變數(shù)據(jù)狀態(tài)的概率。對于輸入或輸出語句,I通常設(shè)置為1;表達(dá)式語句有更復(fù)雜的I計算規(guī)則,根據(jù)所包含的操作符、變量和常量的數(shù)量和類型,每一個元素都有自己的I值,通過加權(quán)平均計算后獲得該條語句的I值。當(dāng)常量作為操作數(shù)時,I的值為1;當(dāng)變量作為操作數(shù)時,I值為這一變量所在的最后一條語句I值。

(3)E表示在假設(shè)輸入是均勻分布的情況下,程序的某個部分被執(zhí)行的概率,上限是1。順序結(jié)構(gòu)語句的E值為1,因為它們通常均被執(zhí)行;另一方面,通常必須對分支語句進(jìn)行評估,以確定它們是否被執(zhí)行,或者用整體平均值來代替[2-3]。

1.3 擴展至軟件對象粒度級上的PIE模型

基于PIE技術(shù)原型,在本文的擴展模型中,將軟件系統(tǒng)的對象抽象為可測試性的位置概念,修改基本模型中的檢測粒度,并給出3個假設(shè)前提。

假設(shè)1I的取值范圍為[0,1]。對于一個對象,每一對輸入/輸出都有相應(yīng)的I值。這與對象內(nèi)部的處理邏輯相關(guān),一般來說,對象越復(fù)雜,越有可能隱匿故障。E的取值范圍為[0,1],其值是對象執(zhí)行的概率數(shù)據(jù)。

假設(shè)2 由于面向?qū)ο笤O(shè)計(Object Oriented Design,OOD)的軟件使用有效性量化的框架,因此每個OOD指標(biāo)都會影響某些質(zhì)量因素,該框架如圖1所示。根據(jù)所選自變量的值,即數(shù)據(jù)訪問度量(Data Access Metrics,DAM)、功能抽象度量(Measure of Functional Abstraction,MFA)、直接類耦合度量(Direct Class Coupling,DCC)、方法內(nèi)聚度量(Cohesion Among Method,CAM)、多態(tài)方法數(shù)量(Number of Polymorphic methods,NOP),進(jìn)行線性組合計算[4]。

圖1 面向?qū)ο笤O(shè)計的量化框架

I實例的計算公式為

I=[α0±(α1×Encapsulation)±

(α2×Inheritance)±(α3×Coupling)±

(α4×Cohesion)]

(1)

選擇MFA,DCC,CAM來計算復(fù)雜度,使用SPSS數(shù)據(jù)分析軟件對系數(shù)進(jìn)行回歸性分析。其中,模型系數(shù)如表1所示,得到復(fù)雜度的計算系數(shù)

表1 模型系數(shù)

Complexity=2.192-0.896×Inheritance-0.096×Coupling-0.078×Cohesion

(2)

假設(shè)3 在計算P值時,跟蹤該對象在后續(xù)執(zhí)行中產(chǎn)生故障的情況。當(dāng)系統(tǒng)發(fā)生故障時,記錄中間過程傳遞的所有K個對象,K個對象的I值的乘積為P值,即

(3)

如果未到達(dá)故障暴露的結(jié)點,則將P值設(shè)置為零。當(dāng)分析計算分別獲得對象的E值、I值和P值時,對象模塊的可測試性即為三者的乘積。該方法注重分析軟件系統(tǒng)的結(jié)構(gòu),對象的I值計算為非精確性數(shù)據(jù),著重對類中的程序進(jìn)行邏輯分析,充分運用了基礎(chǔ)的PIE模型[4-5]。

2 應(yīng)用隨機圖理論的軟件可測試性計算模型

2.1 軟件系統(tǒng)的隨機圖抽象

BRIAND L[1]提出將軟件系統(tǒng)用圖進(jìn)行抽象表達(dá),任何軟件系統(tǒng)均可以抽象為結(jié)點的集合以及結(jié)點之間的若干類型邊的集合。本文軟件圖中的結(jié)點表示對象,即為類、若干行代碼或相應(yīng)的文檔。將結(jié)點之間的若干連接均抽象為邊,如具有繼承關(guān)系的兩個類。依據(jù)以上理論,將面向?qū)ο蟮能浖到y(tǒng)抽象為隨機圖[6-7],其中包含弱結(jié)點和強結(jié)點兩類結(jié)點。軟件系統(tǒng)中的故障經(jīng)過弱結(jié)點進(jìn)行傳播、感染和擴散,其特征可以運用凱萊樹(Cayley Tree)的滲透模型[8]進(jìn)行表征。

假定消息能雙向傳遞,即構(gòu)造隨機無向圖G有N個結(jié)點和Q條邊。有兩種基本的概率結(jié)構(gòu)來表示隨機圖,如文獻(xiàn)[8]中的模型A。在該模型中,Q為一隨機生成的變量,假設(shè)被連接的每對結(jié)點i和j的概率相等,其概率取值為p,并且這些概率之間彼此獨立。若某圖有N個結(jié)點,即存在N(N-1)條可能的邊,則隨機變量Q就以一個均值為〈Q〉的二項隨機變量分布。均值的計算公式為

(4)

據(jù)此能以概率p和結(jié)點數(shù)目表示一個隨機圖,即G=G(Q,p)。

定理1從隨機圖的某結(jié)點i出發(fā),其邊數(shù)ri為結(jié)點i的次數(shù),所有次數(shù)之和為2倍的邊數(shù),即

(5)

定理2若圖的全部結(jié)點均具有相同的次數(shù)r,則此圖被稱為r次正則圖。在模型A中,當(dāng)N為最大值時,次數(shù)的平均值為

(6)

若N取某一較大值時,假定概率p為常量,則任何隨機圖G=G(Q,p)均趨向正則[7]。

軟件模型圖是否缺乏正則和統(tǒng)一的本質(zhì)特性,可以從以下3個方面進(jìn)行分析。第一,確定軟件系統(tǒng)的經(jīng)驗關(guān)聯(lián)分析,并在概率的基礎(chǔ)上對軟件系統(tǒng)進(jìn)行圖形化抽象,但這方面還需要進(jìn)一步的研究。第二,軟件系統(tǒng)雖非正則,但若采用近似隨機表達(dá),則理論上為局部性正則。因此,大型軟件系統(tǒng)可以分解為若干個連通子圖,子圖則可以被當(dāng)作大型軟件系統(tǒng)的子模塊,若干連通子圖為近似正則。第三,隨機圖理論對圖的拓?fù)渥兓哂泻軓姷聂敯粜?即改變鏈接或加強結(jié)點不會從根本上改變隨機圖的基本性質(zhì)。因此,本文先將整個軟件系統(tǒng)抽象成隨機圖,為軟件故障傳播建立量化規(guī)則做準(zhǔn)備。

2.2 應(yīng)用傳播感染免疫理論的軟件隨機圖模型

具有傳染性的軟件系統(tǒng)故障感染可以用隨機圖的方式來表達(dá)。參考PIE模型,若測試輸入均勻進(jìn)行,對象發(fā)生突變,并經(jīng)過隨機圖中的邊進(jìn)行故障傳播,則引入免疫的概念。

軟件故障隨機圖中有弱結(jié)點和強結(jié)點兩種互斥結(jié)點。弱結(jié)點受故障影響時易受感染,則表示故障隱蔽性強;強結(jié)點的可測試性較好,對故障傳播有很強的免疫力,即表示故障較易暴露。在單元可測試性分析過程中或軟件測試期間可依次對兩種結(jié)點進(jìn)行分辨。為了提高軟件的質(zhì)量,進(jìn)而對弱結(jié)點單元進(jìn)行改進(jìn),假設(shè)故障從弱結(jié)點開始,則傳染操作在弱結(jié)點發(fā)生,程序在強結(jié)點失效,故障得以暴露。

某軟件系統(tǒng)擁有N個結(jié)點,包括S個強結(jié)點和W個弱結(jié)點。設(shè)q=W/N,對于任意給定的結(jié)點,則其想要連通的結(jié)點為弱結(jié)點的概率約為q。對于任意給定的結(jié)點x和y,設(shè)故障從x傳播到y(tǒng)的概率為s。q和s是反映不同類型軟件系統(tǒng)特性的統(tǒng)計參數(shù)。

設(shè)q和s的值均較小且彼此獨立,如上所述,大規(guī)模圖一般為近似正則,即r次正則。若故障發(fā)生在強結(jié)點,則故障暴露率非常高,且故障將停止傳播。但在弱結(jié)點發(fā)生故障時,則可能會導(dǎo)致相應(yīng)的一系列故障,最后在途經(jīng)強結(jié)點時被暴露出來。

用C記錄故障鏈中包含的結(jié)點數(shù)。C的概率分布情況用F(x)表示,即

F(x)=p(C≤x)

(7)

式中:p——概率。

由于系統(tǒng)的次數(shù)為r,故有r個結(jié)點與故障狀態(tài)的結(jié)點連通。這r個連通結(jié)點是弱結(jié)點的概率為q,連通弱結(jié)點能被傳播故障的概率為s,則若干對象之間故障將會以概率qs傳播,最終故障會引起系統(tǒng)失效。受到故障感染的所有弱結(jié)點個數(shù)為W項總和,各項分布均為F。

這里一個關(guān)鍵的簡化是假設(shè)一個弱結(jié)點上的故障在沒有循環(huán)的情況下通過樹傳播。下面是對這一假設(shè)有效性的簡短證明。

根據(jù)隨機圖的理論,給出一個臨界點,此臨界點以下,圖大概率是以樹的形式呈現(xiàn)。若某一圖中有N個結(jié)點,則連通分量中出現(xiàn)環(huán)的概率為1/N。在一個規(guī)模較大的隨機圖中,結(jié)點之間能連通的概率小于1/N時,則圖大概率是以樹的形式呈現(xiàn)。在本文中,兩個結(jié)點通過故障傳播連接的概率為pqs,所以,若這個假設(shè)是合理的,即僅需符合pqs≤1/N。故障經(jīng)由樹進(jìn)行傳播,則該過程可表達(dá)為在連通概率為t=qs、分支數(shù)為r的凱萊樹上傳播。事實上,在軟件運行時,故障可以通過概率qs傳播到r個相鄰結(jié)點之一,并且不生成環(huán),而故障傳播的每一步,都會在r個非交叉的路徑中選擇。凱萊樹是固定步長分支的圖形拓?fù)浣Y(jié)構(gòu),因此上述連通樹中包括所有原始結(jié)點,結(jié)點數(shù)C為隨機值,其平均值為

(8)

2.3 基于對象粒度的軟件可測試性計算模型

基于對象粒度構(gòu)建改進(jìn)的PIE計算模型。若I為弱結(jié)點的變異故障率,E為其執(zhí)行概率,則根據(jù)式(3),其P值的平均概率表示為

(9)

在故障傳播的路徑中,第i個對象模塊的變異故障率為Ii,其可測試性計算式為

(10)

上述計算模型的相對值可以評價軟件可測試性的差異程度,但絕對值的意義不大。

3 結(jié) 語

軟件可測試性是軟件有效測試難度的一個指標(biāo)。如果可以用特定的值來量化可測試性,則可以更方便地評估軟件測試的難度,也可以更準(zhǔn)確地衡量測試工作量。本文結(jié)合隨機圖理論和擴展PIE模型來分析面向?qū)ο筌浖目蓽y試性,獲得的數(shù)據(jù)可以反映對象的可測試性,提供了最可靠的數(shù)值依據(jù)來判斷模塊是否需要重構(gòu),以實現(xiàn)對軟件開發(fā)過程的輔助決策。