馮廷智 成紅芳

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

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

中圖分類(lèi)號(hào)：V219 文獻(xiàn)標(biāo)識(shí)碼：A

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

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

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

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

1 基于遺傳算法的測(cè)試用例優(yōu)先級(jí)技術(shù)

1.1 遺傳算法

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

（1）初始化

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

（2）個(gè)體評(píng)價(jià)

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

（3）種群進(jìn)化

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

（4）終止進(jìn)化

再次評(píng)價(jià)個(gè)體適應(yīng)度，如果已經(jīng)滿足優(yōu)化準(zhǔn)則，則輸出適應(yīng)度最大的個(gè)體作為最優(yōu)解;否則，返回第（3）步。

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

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

（1）將活動(dòng)圖轉(zhuǎn)換為控制流圖（CFG）

在控制流圖中，節(jié)點(diǎn)表示活動(dòng)。

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

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

（3）選擇

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

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

（4）交叉或重組

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

（5）突變

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

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

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

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

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

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

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

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

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

3 結(jié)論

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

參考文獻(xiàn)

[1]張智軼，陳振宇，徐寶文，等.測(cè)試用例演化研究進(jìn)展明.軟件學(xué)報(bào)，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]曲波，聶長(zhǎng)海，徐寶文.回歸測(cè)試中測(cè)試用例優(yōu)先級(jí)技術(shù)研究綜述[J].計(jì)算機(jī)科學(xué)與探索，2009，3（3）：225-233.

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

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

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

[7]鄭錦勤，牟永敏.基于函數(shù)調(diào)用路徑的回歸測(cè)試用例選擇排序方法研究[J].計(jì)算機(jī)應(yīng)用研究，2016，33（7）：2063-2067.

[8]尹建月，周萌，陳升來(lái).基于uML活動(dòng)圖的測(cè)試用例生成方法設(shè)計(jì)[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].計(jì)算機(jī)應(yīng)用研究，2008，25（10）：2911-2916.