基于代數的軟件路徑的自動生成

李肇明

(安徽國際商務職業學院 信息工程學院，安徽 合肥 230000)

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

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

1 相關概念

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

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

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

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

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

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

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

2 路徑生成

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

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

3 構造控制流圖

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

3.1 路徑表達式生成

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

然后，使用代數方法將其轉換成路徑表達式，方法步驟如下：

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

圖3的轉換過程如圖4所示。

3.2 循環展開

路徑表達式中的每一條路徑積都應該在一個合適的循環下展開。如果循環次數過多，產生的路徑數量將急劇增加，將產生路徑爆炸問題。

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

3.3 算法實現

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

表1 算法偽碼

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

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

● 算法第22～27行對路徑表達式中的循環做處理。

表1續表

4 案例研究

為了驗證該方法的準確性，首先對兩個小規?；鶞食绦蜻M行路徑生成。程序規模較小，便于手工生成路徑，并與文中方法比較。為了驗證本方法的有效性，通過案例來說明。

4.1 案例1

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

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

生成，結果如表2所示。

表2 實驗結果

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

4.2 案例2

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

表3 5個經典案例實驗結果

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

5 結語

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