基于覆蓋準則的多輪測試用例優先排序方法何展翔

關鍵詞：回歸測試;覆蓋準則;鯨魚優化算法;擴展有限狀態機

中圖分類號：TP311.5 文獻標志碼：A

0 引言（Introduction）

擴展有限狀態機[1]（EFSM）在刻畫軟件行為和結構方面展現出顯著優勢，因此近年來基于EFSM的測試用例優先排序技術逐漸成為主流。大多數測試用例優先排序技術[2]都基于覆蓋率相關信息對測試用例進行排序。然而，過去的研究大多使用單一覆蓋準則進行排序，少數研究雖然使用多種覆蓋準則，但是也都是依靠人工經驗選擇所使用的覆蓋準則。這種方式可能受到測試人員經驗和知識的限制，無法涵蓋所有可能的測試場景和覆蓋需求，導致選擇的覆蓋準則可能并不全面或不足以應對所有情況。同時，測試需求和環境可能會隨著時間的推移而發生變化，而人工選擇的覆蓋準則可能難以及時更新和調整以適應新的需求和變化，導致測試方法存在局限性和過時性。因此，急需尋找一種高效的方法解決此問題。

1 相關理論（Related theory）

1.1 擴展有限狀態機模型

擴展有限狀態機模型是由一個六元組M =（S，S₁，V，I，O，T）組成的，其中S是狀態集合，S₁∈S是模型的初始狀態，狀態是描述系統在不同時間點的運行狀態。每個狀態都代表系統在特定條件下的一種行為。V是模型變量集合，I和O分別是輸入集合、輸出集合。T是變遷的有限集合，變遷定義了狀態之間的切換規則，即系統從一個狀態轉移到另一個狀態的條件和動作。

1.4 突變分析

針對實驗使用的每個擴展有限狀態機，研究人員使用突變測試技術[5]生成相應的故障版本，該技術通過向正在測試的EFSM注入故障生成變異體。盡管真實的有故障EFSM 可能包含多個故障，但是本文每個變異體中只植入一個故障。這樣做是為了便于研究TCP（測試用例優先排序）方法對每個真實故障的檢測能力，從而避免掩蓋效應。

具體而言，本文采用突變操作符模擬真實的故障。在故障注入過程中，使用了3種常見類型的突變，即值突變、決策突變和語句突變。值突變涉及修改參數或常量的值，包括添加或減去值等操作。決策突變涉及更改轉換中的條件表達式，例如將“gt;”替換為“lt;”。語句突變涉及修改轉換中包含的語句，包括添加或刪除語句部分內容，重新排列語句的相對位置等。這些突變涵蓋了經典的突變操作符：條件運算符替換、關系運算符替換、表達式值替換、字面值替換、單語句刪除和算術運算符替換。此外，應用了單傳遞故障操作符，即將轉換的尾狀態修改為不同狀態，用于生成變異體。這些突變操作是由研究人員先前開發的EFSM模型解析工具自動生成的[6]。對于正在測試的EFSM的每個變異體，需要執行該模型的測試套件以確定測試是否通過。具體而言，將正在測試的模型視為正確版本。測試用例在其相應的變異體上執行，并通過比較它們的輸出的差異得出最終的測試判定。

3 實驗和結果（Experiment and result）

3.1 實驗目標模型

我們設計了一系列的實驗，將提出的方法應用于實際的EFSM模型，用來檢驗CWTCP方法的故障檢錯率。CWTCP方法利用Python語言實現，實驗運行的平臺是Windows10的64位操作系統。為了使實驗結果更具一般性，本文選擇了5個典型的EFSM 模型，分別是Monitor、INRES、Class Ⅱ、OLSR、SCP。以上目標模型收集自目前已有的研究，表1列出了5個目標模型對應的屬性，“狀態數”欄是指目標模型存在的狀態數量，“變遷數”欄是指 EFSM 模型中遷移的數量，“測試用例數”欄是實驗使用的測試用例數量，“變異數”欄是實驗使用的變異體數量。

3.2 實驗研究問題

RQ1：基于覆蓋準則的優先排序相對于隨機排序在故障檢測率方面是否具有顯著優勢？ 這個問題可以確定在EFSM 模型中引入基于覆蓋準則的優先排序是否有效。

RQ2：CWTCP方法在故障檢測率方面是否具有顯著優勢？ 這個問題可以確定CWTCP方法是否有效。

3.3 實驗結果與分析

針對RQ1，以APFD值作為故障檢測能力的評價指標設計了實驗1，其實驗結果如圖2所示。從圖2中可以直觀地觀察到，在每個EFSM 中基于覆蓋準則的平均APFD值均大于隨機排序。基于覆蓋準則的優先排序的最小APFD值為0.647，遠高于隨機排序（0.386）。基于覆蓋準則的平均APFD值為0.892，比隨機排序高16.4%。在M1中，SC的平均值和最大值表現最好，TC和TPC的表現相似;在M2中，TC的平均值和標準差表現更好;在M3和M4中，TC表現最好;在M5中，TC和TPC表現相似，這可能是因為模型變遷較少而導致的。

總體看來，TC的最小APFD值比OLP高13.4%，平均APFD值比SC高7.34%，標準差比TPC低9.4%。可以看出，TC在每個EFSM 中的性能最好，TPC次之，而LFP和OLP具有相似的性能。這些對比結果表明，相較于隨機排序，基于覆蓋準則的優先排序在APFD值方面有了顯著的提升。造成這一差異的原因可能是基于覆蓋準則的優先排序能充分利用了來自EFSM的信息。因此，將基于覆蓋準則的優先排序技術引入MBTCP是可行的。

針對RQ2，以APFD值作為故障檢測能力的評價指標設計了實驗2，實驗2中，鯨魚優化算法的相關參數均設置為與原論文（The Whale Optimization Algorithm）相同，Random為隨機選擇覆蓋準則進行多輪排序，其實驗結果如圖3所示。從圖3中可以直觀地觀察到，CWTCP方法相比于隨機選擇覆蓋準則，可以有效地提高故障檢錯率。CWTCP的最小APFD值為0.797，高于隨機選擇（0.722），平均APFD值為0.918，比隨機排序高1.8%。在M1中，CWTCP的最大APFD值為0.951，平均APFD 值為0.904，比Random 高2.2%，平均值比Random高2.6%;在M2和M4中，CWTCP的各項指標都比隨機選擇高;在M5中，CWTCP與隨機選擇有相同的最大值。這些對比結果表明，相較于隨機選擇，CWTCP在APFD值方面取得了顯著的提升。與隨機選擇相比，這種差異的根源在于鯨魚優化算法的有效性。該算法能夠有效地發現具有顯著差異的覆蓋準則。因此，在多輪排序中采用不同的覆蓋準則，可以更有效地提高故障檢測率。

4 結論（Conclusion）

本研究提出了一種基于EFSM 模型的測試用例優先排序方法CWTCP，通過引入鯨魚優化算法，該方法能夠有效挑選出差異性較大的覆蓋準則序列，從而優化測試用例的執行順序，并顯著提高了故障檢測率。該方法的創新性在于將優化算法與測試用例排序相結合，充分利用了EFSM模型的特性。實驗結果表明，CWTCP方法相對于傳統方法具有明顯的優勢，為軟件測試過程的改進提供了有力支持。未來的研究將重點關注更多的覆蓋準則，并探索針對更大規模和更復雜EFSM的測試用例優先排序策略，以進一步提升故障檢測的準確性和效率。

作者簡介：

何展翔（1998-），男，碩士生。研究領域：軟件測試。

舒挺（1979-），男，博士，副教授。研究領域：軟件測試，網絡協議測試。