馮廷智 成紅芳

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

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

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

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

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

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

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

1 基于遺傳算法的測試用例優(yōu)先級技術

1.1 遺傳算法

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

（1）初始化

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

（2）個體評價

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

（3）種群進化

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

（4）終止進化

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

1.2 用遺傳算法實現(xiàn)測試用例優(yōu)先級排序的步驟

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

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

在控制流圖中，節(jié)點表示活動。

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

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

（3）選擇

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

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

（4）交叉或重組

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

（5）突變

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

2 機載環(huán)控系統(tǒng)綜合控制器軟件應用案例

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

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

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

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

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

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

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

3 結論

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

參考文獻

[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]曲波，聶長海，徐寶文.回歸測試中測試用例優(yōu)先級技術研究綜述[J].計算機科學與探索，2009，3（3）：225-233.

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

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

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

[7]鄭錦勤，牟永敏.基于函數(shù)調用路徑的回歸測試用例選擇排序方法研究[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.