基于遺傳算法的航空機載軟件測試用例優先級技術研究

馮廷智 成紅芳

摘要：為了提高航空機載軟件回歸測試效率、降低回歸測試成本，提出應用遺傳算法實現測試用例優先級排序的方法。該方法將統一建模語言（UML）活動圖轉化為控制流圖（CFG），對控制流圖中各判定節點進行二進制編碼生成初始種群，并通過選擇、交叉和突變等操作搜索適應度最高的個體進行優先測試。以某型飛機機載環控系統綜合控制器軟件貨艙供氣旁路調節閥控制率計算功能為案例，證明該方法能夠實現測試用例的優先級排序，可用于基于模型的機載軟件自動化測試。

關鍵詞：機載軟件;遺傳算法;測試用例優先級;回歸測試;基于模型的測試

中圖分類號：V219 文獻標識碼：A

隨著現代航空機載軟件規模和復雜度的不斷增加，給軟件測試帶來了諸多挑戰。由于功能完善、性能優化、錯誤修復等原因，軟件往往處于動態演化中，會積累大量的冗余測試用例，使測試用例集的管理和維護成本增加[1]。執行回歸測試時，測試人員從已有的測試用例集中選擇可復用的用例子集，盡可能地滿足測試需求。然而，選擇的測試用例，其檢錯能力或覆蓋能力有所不同，且仍可能包含冗余測試用例。若將其按照一定的準則進行排序后再執行，有助于在較短的時間內盡可能多地發現錯誤，并盡快達到覆蓋率要求，這便是測試用例優先級技術[2]。

測試用例優先級是一種高效的回歸測試技術，能在時間、環境等資源受限的情況下執行更多的有效測試用例，從而保證軟件質量[3]。研究者提出了多種實現測試用例優先級排序的方法。李龍澍[4]等提出了多種群遺傳算法實現測試用例優先級排序的方法。張娜[5]等設計的基于多目標優化的測試用例優先級方法，能利用測試過程中的反饋信息，在線調整測試用例優先級。常龍輝[6]等提出了能動態自適應地調整測試用例優先級的技術。鄭錦勤[7]等結合了測試用例選擇和測試用例優先級技術，對排序結果進行再選擇，進一步縮小了回歸測試用例集。

為了進一步提高測試效率和測試質量，產生了基于模型的自動化軟件測試方法。根據軟件開發文檔對被測系統進行形式化建模，通過算法由模型自動生成測試用例，能夠顯著提高軟件測試的充分性和自動化程度。統一建模語言（Unified Modeling Language，UML）是一種可被用于自動化測試的典型模型，尹建月等[$1提出了一種基于UML活動圖模型生成測試用例的方法，結合深度優先搜索生成了測試路徑。Sabharwal[9]等和Nejad[10]等將遺傳算法應用于基于UML模型的測試，實現了測試用例的優先級排序。

本文將遺傳算法應用于航空機載軟件測試用例優先級技術中，以某型飛機機載環控系統綜合控制器軟件貨艙供氣旁路調節閥控制律計算功能為案例，以該功能的UML活動圖為輸入，將其轉化為控制流圖（Control Flow Graph，CFG），用遺傳算法實現測試用例的優先級排序，并討論該方法在機載軟件回歸測試中的應用前景。

1 基于遺傳算法的測試用例優先級技術

1.1 遺傳算法

遺傳算法[11]是一種模擬自然界遺傳機制和生物進化論而形成的搜索最優解的方法，具有自適應的特點，能夠處理復雜的非結構化問題，且操作步驟規范，便于具體實施[12]。遺傳算法的處理對象為一定數量的染色體，染色體是一串二進制數字，每個數字代表基因。遺傳算法的基本執行過程如圖1所示，簡述如下：

（1）初始化

確定種群規模、交叉概率、突變概率和終止進化的條件，并隨機生成一定數量的個體作為初始種群。

（2）個體評價

計算種群中每個個體的適應度，適應度可以定義為個體在環境中的生存能力或再生能力。

（3）種群進化

種群進化過程中主要執行三種操作：選擇（Selection）、交叉（Crossover）和突變（Mutation）。首先，選擇適應度高的個體作為母體。其次，依據一定的概率，互換兩個個體的基因或序列生成新的種群，這就是交叉或重組。最后，依據一定的概率，使個體的基因發生突變，引入新的基因特征，保持種群的多樣性。

（4）終止進化

再次評價個體適應度，如果已經滿足優化準則，則輸出適應度最大的個體作為最優解;否則，返回第（3）步。

1.2 用遺傳算法實現測試用例優先級排序的步驟

UML活動圖能通過模擬一個活動到其他活動的控制流描述出系統功能，本文以活動圖為輸入，用個體適應度表征測試用例的優先級，通過遺傳算法搜索種群中適應度最高的個體，找出最重要、最復雜的路徑進行優先測試，防止錯誤在后續過程中增殖或傳播。下面為具體的實現步驟：

（1）將活動圖轉換為控制流圖（CFG）

在控制流圖中，節點表示活動。

（2）采用基于堆棧的內存分配方法和IF模型為CFG中各節點分配權重

堆棧具有“后進先出”的存取特性，只能在棧頂對數據進行插入和刪除，訪問或修改某一元素時，需要刪除其上方的數據。基于堆棧的內存分配方法中，對CFG各節點分配的權重（w_SB）與在堆棧中訪問該節點的操作數相關。訪問某一節點的操作數越高，分配的權重越高，該節點的復雜度也越高。同時，訪問該節點的成本亦會逐漸升高。在IF模型中，將信息流應用于系統的元件設計。本文將CFG中的節點作為元件，計算了CFG中每個節點的IF值。以A節點為例，其IF值的計算公式如下：式中FAN-IN（A）為A節點的扇入，FAN-OUT（A）為A節點的扇出。CFG中節點的總權重為基于堆棧的權重與IF值的和。

（3）選擇

遺傳算法的處理對象為二進制編碼組成的染色體，通過對CFG中的判定節點進行編碼生成染色體或個體，編碼的位數與CFG中判定節點的數量相關。例如，CFG中有4個判定節點，染色體的編碼由4位二進制數組成，每位二進制數代表一個基因。每個基因可以取1或0，1表示該判定節點選擇了為真的路徑，0則表示選擇了為假的路徑。圖2為某個染色體，該染色體對應的CFG中有4個判定節點，分別為第2、5、7和10節點;4位編碼按照左右順序分別與各判定節點的取值一一對應。

評估個體的適應度后，選擇適應度較高的染色體作為母體進行再生。每個染色體的適應度由式（2）計算得到：式中：w_i為目標路徑中第i個節點的權重，n是該路徑中的節點數。第i個節點的權重為IF值和基于堆棧的權重之和：

（4）交叉或重組

基因的交叉和重組的實質是交換兩個個體的基因或編碼序列。本文設定交叉或重組的可能性為80%[9]。種群進化過程中，給定一個隨機數R（0

（5）突變

為了避免搜索過程陷人局部最優解，需要通過突變引入新的特征，保持種群的多樣性。發生突變時，染色體的編碼會在0和1之間跳轉。本文設定突變的概率為20%[9]，當R小于20%時，對該染色體執行突變操作。

2 機載環控系統綜合控制器軟件應用案例

某型飛機機載環控系統綜合控制器軟件貨艙供氣旁路調節閥控制率計算功能的活動圖如圖3所示，該功能根據駕駛艙供氣流量實測值，計算出目標值與實測值之間的系統控制誤差，再依據控制邏輯輸出調節閥的占空比，以實現對駕駛艙入口流量的控制。

根據1.2節所述的采用遺傳算法實現測試用例優先級排序的方法，首先將圖3所示的活動圖轉化為CFG，如圖4所示。采用基于堆棧的內存分配方法，為各節點分配權重，見表1。k表示當前節點之前的節點數;s表示插入當前節點后堆棧的大小，因此，堆棧的最大容量s^max為12。w_SB表示為該節點分配的基于堆棧的權重，通過w_SB=s^max-k計算得到。例如，CFG中節點1是第一個插入堆棧的節點，其權重為w_SB=12-0=12，類似地，節點2之前的節點數為1，其權重為w_SB=12-1=11.從表1可以看出，節點1的權重最大，意味著訪問或修改節點1需要的操作數最多。

表2為各節點的復雜度。A為基于堆棧中刪除操作的復雜度，由表1查得。例如節點8，其權重為7，則基于刪除操作的復雜度為8;節點9的權重為6或7，則基于刪除操作的復雜度為6+7=13。B為節點的IF值，通過式（1）計算得到。各節點的總復雜度等于該節點基于刪除操作的復雜度與IF值的和，即A+B。

從圖4可以看出，該CFG有5個判定節點，分別為4，6、10、13、14。使用5位二進制數對這5個節點進行編碼，即可生成染色體或個體。例如，5個判定節點都取0時，該染色體為00000，對應的路徑將歷經節點1、2、3、4、6、8、9、10、12、14、18、19;該測試用例的適應度為路徑中各節點復雜度的和，即12+12+11+11+10+8+15+13+10+9+6+7=124。

根據遺傳算法的執行步驟，首先隨機生成初始種群，由4個個體組成：11111、10000、00001、11100，見表3。表3中X為隨機生成的染色體或個體，代表測試用例。F（X）為該染色體的適應度。以該案例中隨機生成的個體為例，11111代表的測試用例為節點1、2、3、4、5、9、10、11、13、15、19所在的路徑，其適應度為115;10000代表的測試用例為節點1、2、3、4、5、9、10、12、14、18、19所在的路徑，其適應度為115;00001代表的測試用例為節點1、2、3、4、6、8、9、10、12、14、17、19所在的路徑，其適應度為124;11100代表的測試用例為節點1、2、3、4、5、9、10、11、13、16、19所在的路徑，其適應度為115。R為隨機生成的0到1之間的數;C和M分別表示交叉和突變操作后的個體，當R小于80%時執行交叉操作;當R小于20%時，執行突變操作。F'（Al為執行遺傳操作后生成的新個體的適應度。表3～表6為每次迭代后的結果。每次迭代后，將種群中的個體按其適應度重新排序。

如表6所示，該案例中生成的初始種群經8次迭代后，其適應度已達到最大值，且不再發生明顯變化。可以認為，表6所示的個體或測試用例的優先級最高，應最先對其進行測試。染色體00101和01111表示節點1、2、3、4、6、8、9、10、11、13、16、19所在的路徑，染色體01100表示節點1、2、3、4、6、7、9、10、12、14、18、19所在的路徑，染色體00001表示節點1、2、3、4、6、8、9、10、12、14、18、19所在的路徑。分析上述4個個體可知，優先級較高的染色體都是節點6所在的路徑。實質上，從節點6至節點7和節點8的路徑是對稱的，從節點10至節點11和節點12的路徑也是對稱的，判定節點6、10、13、14的取值不會影響染色體的適應度。因此，決定染色體適應度的關鍵判定節點為節點4，節點4取值為0的路徑優先級較高。

出現上述現象的原因主要是本文所選案例相對簡單，活動圖中有三處對稱結構。然而，以環控系統綜合控制器軟件為例的現代航空機載軟件中存在大量的復雜邏輯，判定節點多，如果僅依賴人工生成測試用例，不僅效率低下，且難以保證測試充分性，無法實現測試用例優先級。綜上所述，該案例已經證明，本文提出的方法和步驟能夠通過遺傳算法實現測試用例的優先級排序。

3 結論

本文提出了應用遺傳算法實現航空機載軟件測試用例優先級排序的方法。以某型飛機機載環控系統綜合控制器軟件貨艙供氣旁路調節閥控制率計算功能為例，以其UML活動圖為輸入，通過選擇、交叉和突變等遺傳操作搜索出適應度最高的個體進行優先測試。證明基于遺傳算法的測試用例優先級技術，可被用于基于模型的機載軟件測試。在后續工作中，將對比分析遺傳算法與其他算法的優化速率，并研究通過遺傳算法實現機載軟件測試用例優先級排序的自動化工具。

參考文獻

[1]張智軼，陳振宇，徐寶文，等.測試用例演化研究進展明.軟件學報，2013，24（4）：663-674.

[2]Yoo S，Harman M.Regression testing minimization，selectionand prioritization：A survey [J].Software Testing，Verificationand Reliability，2012，22（2）：67-120.（in Chinese）

[3]曲波，聶長海，徐寶文.回歸測試中測試用例優先級技術研究綜述[J].計算機科學與探索，2009，3（3）：225-233.

[4]李龍澎，李森，廖敏，等.基于多種群遺傳算法測試用例優先級技術研究[J].計算機技術與發展，2011，21（4），112-119.

[5]張娜，姚瀾，包曉安，等.多目標優化的測試用例優先級在線調整策略[J].軟件學報，2015，26（10）：2451-2464.

[6]常龍輝，繆淮扣，肖蕾.基于歷史信息的自適應測試用例優先級技術明.計算機科學，2015，42（9）：154-158.

[7]鄭錦勤，牟永敏.基于函數調用路徑的回歸測試用例選擇排序方法研究[J].計算機應用研究，2016，33（7）：2063-2067.

[8]尹建月，周萌，陳升來.基于uML活動圖的測試用例生成方法設計[J].信息化研究，2014，40（3）：28-32.

[9]Sangeeta S，Ritu S，Chayanika S.Applying genetic algorithmfor prioritization of test case scenarios derived from UMLdiagrams[J].International Journal of Computer Science Issues，2011，8（3）：433-444.

[10]Fatemeh M N，Reza A，Mohammad M D.Using memeticalgorithms for test case prioritization in model based softwaretesting[C]//1”Conference on Swarm Intelligence andEvolutionary Computation（CSIEC 2016），Higher EducationComplex of Bam，Iran，2016.

[11]Holland J H.Adaptation in natural and artificial systems[M].AnnArbor：University of Michigan Press，1975.

[12]葛繼科，邱玉輝，吳春明，等.遺傳算法研究綜述[J].計算機應用研究，2008，25（10）：2911-2916.