李肇明

(安徽國際商務(wù)職業(yè)學(xué)院 信息工程學(xué)院，安徽 合肥 230000)

軟件測試是軟件開發(fā)周期中的一個關(guān)鍵階段[1]，在此階段可以發(fā)現(xiàn)潛在的軟件缺陷和故障，并確保這些問題能及時得到解決，從而提高軟件質(zhì)量。白盒測試，又稱結(jié)構(gòu)測試和邏輯驅(qū)動測試，是軟件測試中一種強(qiáng)大的技術(shù)，其目的是對要測試的軟件的內(nèi)部結(jié)構(gòu)進(jìn)行測試[2]。該方法在對軟件可靠性有較高要求的領(lǐng)域獲得廣泛運用，如軍事、金融和航空領(lǐng)域等。其中路徑測試是白盒測試中應(yīng)用最為廣泛的方法之一。路徑測試的過程通常被分為代碼分析、控制流圖生成、路徑生成和測試用例四個部分[3]。因此，路徑測試的準(zhǔn)確性與路徑生成密切相關(guān)。然而，隨著軟件規(guī)模的不斷增加，軟件系統(tǒng)中的循環(huán)結(jié)構(gòu)出現(xiàn)次數(shù)也隨之增多，路徑成爆炸式增長，目前已有的軟件路徑生成方法代價大且困難。文獻(xiàn)[4-7]中對于軟件路徑的自動生成問題均提出了相關(guān)算法，但這些算法只生成了軟件的基本路徑集，并沒有生成軟件的完整路徑。文獻(xiàn)[8]提出了一種基于狀態(tài)圖自動生成軟件路徑的方法，并實現(xiàn)了對路徑的優(yōu)化，但該方法未對程序中循環(huán)結(jié)構(gòu)的出現(xiàn)次數(shù)進(jìn)行約束，致使該方法的工作量增加。

本研究提出了一種基于代數(shù)的軟件路徑生成方法，該方法對源代碼進(jìn)行分析，生成控制流圖；然后通過代數(shù)表示將控制流圖轉(zhuǎn)換為路徑表達(dá)式，并對路徑表達(dá)式中的循環(huán)進(jìn)行展開，從而獲得軟件路徑。

1 相關(guān)概念

定義1 控制流圖(CFG)[9]:G=(N,E,b,f)，N表示CFG中的節(jié)點集，每個節(jié)點n(n∈N)代表源程序的一個語句塊；E代表CFG中的有向邊集。每一條有向邊e(e∈E)對應(yīng)源程序兩個節(jié)點之間的數(shù)據(jù)流向；b代表CFG中的入口節(jié)點；f代表CFG中的出口節(jié)點。CFG的入口和出口節(jié)點都只有一個。

定義2 軟件路徑：軟件路徑(Path)是指在一個軟件的CFG中程序執(zhí)行控制流從b到f的一條路徑。其表示為邊的序列：P=ebe2…enef。其中eb表示入口節(jié)點b的出邊，ef表示出口節(jié)點f的入邊。

CFG是一個程序的抽象表示，表示一個程序在執(zhí)行過程中可能會遍歷到的所有路徑。CFG一般通過圖的形式表示，但它也可以通過非圖示的形式表示，其中一種有效的方法是代數(shù)表示。在圖的代數(shù)表示中，首先給每一條邊唯一的標(biāo)簽，使用小寫字母作為邊的標(biāo)簽。'×'操作符表示串聯(lián)。當(dāng)邊a連接邊c時，可被表示為ac，操作符'×'省略。'+'操作符表示選擇，當(dāng)選擇邊a和邊c時，將其表示為a+c。當(dāng)一系列的邊組成一條路徑時，把這條邊序列稱為路徑積。由路徑積和零或者更多的'+'操作符構(gòu)成的表達(dá)式為路徑表達(dá)式。

其中路徑積是沒有加法操作的路徑表達(dá)式的特殊情況。圖1是兩個控制流圖，圖1(a)有三條路徑：abdfi;abegi;achi;

圖1(b)包含循環(huán)路徑，所以無法把它的全部執(zhí)行序列出來，下面是其中4條序列：abef;abcbef;abcbcbef;adf;

在圖的代數(shù)表示中，如果一條邊、路徑積或路徑表達(dá)式被循環(huán)遍歷，可以通過指數(shù)表示循環(huán)次數(shù)。即a2=aa,a3=aaa,a*=aaa…a。

與標(biāo)準(zhǔn)代數(shù)不同，路徑積不滿足交換律，即ab≠ba，這是由于它們具有先后連接的順序。但是它滿足結(jié)合律，即a(bc)=(ab)c=abc。圖1(a)中的所有路徑可以用abdfi+abegi+achi表示從，有'+'操作符連接的路徑都可以看作是獨立的軟件路徑。

2 路徑生成

提出一種基于代數(shù)的軟件路徑自動生成方法。其框架構(gòu)圖如圖2所示。該方法可分為3個階段：第1階段，通過對軟件的源程序進(jìn)行分析，構(gòu)造控制流圖；第2階段，對控制流圖中的每一條邊進(jìn)行標(biāo)記，通過代數(shù)方法把控制流圖轉(zhuǎn)換

為路徑表達(dá)式；第3階段，對路徑表達(dá)式中的循環(huán)展開，得到軟件路徑。

3 構(gòu)造控制流圖

源程序生成控制流圖通常分為3個過程：詞法分析、語法分析和構(gòu)造控制流圖。本研究使用Antlr工具實現(xiàn)詞法分析和語法分析。用戶所提交的語法文件通過Antlr自動生成相應(yīng)的詞法分析器和語法分析器。在詞法分析過程中，源程序被分解為離散的字符組，也就是Tokens(標(biāo)識符、關(guān)鍵字、操作符和符號等)。在語法分析過程中，語法分析其將通過詞法分析獲得的Tokens組織起來，并轉(zhuǎn)換為ATS(Abstract Syntax Tree, 抽象語法樹)。ATS上的每個節(jié)點都代表源代碼中的一種結(jié)構(gòu)，通過對ATS遍歷以構(gòu)造控制流圖。

3.1 路徑表達(dá)式生成

首先對邊標(biāo)記，然后將源程序轉(zhuǎn)換為軟件路徑表達(dá)式。在控制流圖中，通過小寫字母依次對邊標(biāo)記，如圖3所示。

然后，使用代數(shù)方法將其轉(zhuǎn)換成路徑表達(dá)式，方法步驟如下：

(1)合并所有連續(xù)邊，相乘邊的標(biāo)簽。(2)合并所有平行的邊，用'+'操作符相加平行邊的標(biāo)簽從而作為合并之后邊的標(biāo)簽。(3)通過創(chuàng)建一個新“啞節(jié)點”引入一條含有指數(shù)操作符'*'邊的方法消除具有自循環(huán)的節(jié)點，隨后通過乘法來合并這三條邊。(4)選擇移除節(jié)點。(5)第一步到第四步被循環(huán)執(zhí)行直到圖中只有一條邊。

圖3的轉(zhuǎn)換過程如圖4所示。

3.2 循環(huán)展開

路徑表達(dá)式中的每一條路徑積都應(yīng)該在一個合適的循環(huán)下展開。如果循環(huán)次數(shù)過多，產(chǎn)生的路徑數(shù)量將急劇增加，將產(chǎn)生路徑爆炸問題。

采用Z路徑覆蓋思想，只考慮循環(huán)0次和1次兩種情況。即針對代數(shù)表達(dá)式中的循環(huán)指數(shù)，考慮操作符'*'為0和1兩種情況。圖4中路徑表達(dá)式abde*f(gde*f)*hi+ acde*f(gde*f)*hi展開為abdefgdefhi,abdefgdfhi,abdefhi,abdfgdefhi,abdfgdfhi,abdfhi,acdefgdefhi,acdefgdfhi,acdefhi,acdfgdefhi,acdfgdfhi,acdfhi。

3.3 算法實現(xiàn)

具體算法偽碼如表1所示。

表1 算法偽碼

● 算法的輸入為CFG，輸出為軟件路徑；

● 算法第2～21行CFG約簡為路徑表達(dá)式；

● 算法第22～27行對路徑表達(dá)式中的循環(huán)做處理。

表1續(xù)表

4 案例研究

為了驗證該方法的準(zhǔn)確性，首先對兩個小規(guī)?；鶞?zhǔn)程序進(jìn)行路徑生成。程序規(guī)模較小，便于手工生成路徑，并與文中方法比較。為了驗證本方法的有效性，通過案例來說明。

4.1 案例1

三角形分類旨在確定3個輸入邊是否能形成一個三角形，及它們能形成什么類型的三角形；冒泡排序是一種排序算法，它將待排序的數(shù)據(jù)元素從大到小或從小到大排序。三角形分類控制流圖如圖5(a)所示，冒泡排序控制流圖如圖5(b)所示。

通過本方法對三角形判別和冒泡排序進(jìn)行路徑

生成，結(jié)果如表2所示。

表2 實驗結(jié)果

圖5(a)中共有4條路徑，從表2可以看出該方法生成三角形分類的全部路徑。圖5(b)中存在兩個循環(huán)，從表2中可以看出該方法生成的4條路徑對這兩個循環(huán)分別執(zhí)行0次和1次，實現(xiàn)對路徑的覆蓋。

4.2 案例2

選擇5個經(jīng)典案例進(jìn)行實驗。在實驗環(huán)境不變的條件下對這5個經(jīng)典案例分別運行10次并計算出平均運行時間。由于從源程序轉(zhuǎn)換為控制流圖是通過工具輔助生成，其時間無法度量，所以該運行時間只包含將控制流圖轉(zhuǎn)換成軟件路徑所需時間，而且傳統(tǒng)方法求路徑集也需要人工生成控制流圖，時間也無法度量，因此不存在可比性。表3給出了案例的相關(guān)描述，該算法能有效生成5個案例的路徑。

表3 5個經(jīng)典案例實驗結(jié)果

圖6中，對算法進(jìn)行比較，能夠看出，當(dāng)代碼量迅速增大時，該算法生成軟件路徑所消耗的時間并未隨著快速增加，而是較為平緩增長。

5 結(jié)語

本研究提出一種基于代數(shù)的軟件路徑生成方法，該方法通過代數(shù)表示將控制流圖轉(zhuǎn)換為路徑表達(dá)式，并對循環(huán)展開0到1次以獲得軟件路徑。該方法最終有效地生成了軟件路徑。但是，該方法未考慮軟件中不可達(dá)路徑的問題，而且針對循環(huán)問題只考慮了0次和兩次循環(huán)這兩種情況。下一步工作將開展對不可達(dá)路徑檢測工作。