基于歷史覆蓋信息的回歸測試用例動態生成

栗曉雪， 趙逢禹

（1 上海理工大學光電信息與計算機工程學院， 上海 200093；2 上海出版與印刷高等專科學校信息與智能工程系， 上海 200093）

0 引 言

在軟件的演化和維護過程中，往往需要修改軟件中的錯誤、增加新的功能、調整軟件的配置等需求，導致代碼不斷被修改。 在代碼修改完后，需要使用回歸測試來檢查軟件中的缺陷，避免代碼的修改給軟件帶來新的錯誤。 此外，當已有測試用例集不充分時，還需要針對新的功能與代碼部分設計新的測試用例。 因此，在軟件的持續演化過程中，測試用例集合的規模逐漸擴大，導致回歸測試用例集的構建成為一項復雜的工作。 有研究表明，回歸測試的開銷占整個軟件測試預算的80%以上，并占整體維護預算的50%以上［1］。 因而，研究并提出一套有效且經濟的回歸測試用例集的構建方案是十分有意義的。

不管是回歸測試用例的選擇還是回歸測試用例的生成都是國內外學者關注的課題。 文獻［2］提出了一套基于測試用例能夠檢測的故障程度來選擇回歸測試用例的方法，該文首先運行已有的測試用例，將發現的故障與故障程度記錄在日志文件中，然后選擇故障程度較高的測試用例進入下一輪的回歸測試。 文獻［3］提出一種根據回歸測試目標自動調整優化策略的測試用例選擇方法。 該方法將測試用例加上標識屬性，如缺陷檢測數表示該測試用例歷史執行中失敗的總次數，用重要性因子表示該測試用例對于當前測試需求的重要程度，新舊功能標識表示了該測試用例是否屬于新增或刪除模塊。 根據階段的回歸測試目標，將測試用例按照屬性標識自動優化排序，根據優化排序結果選擇測試用例集。 文獻［4］提出了一種靜態多重關聯的回歸測試用例構造方案，通過分析方法間的調用關聯和隱式數據關聯進而構建多重方法關聯圖，并依據該圖中的關聯關系，選擇因代碼更改而受影響的回歸測試用例集。文獻［5］提出基于偶然正確性概率的回歸測試選擇方法，刪減掉可能發生偶然正確性現象的測試用例，提高測試用例的檢錯能力，進一步縮減回歸測試用例集的規模。 所謂偶然正確性是指程序中包含錯誤的語句被執行但仍通過了測試的現象。

當回歸測試中選擇的測試用例不充分時，需要生成新的測試用例。 符號執行作為一種重要的程序分析技術，可以為程序測試提供高覆蓋率的測試用例［6］。 符號執行又分為靜態符號執行和動態符號執行。 靜態符號執行使用符號值代替一類實際數值，作為程序的輸入并執行程序，在程序執行的過程中收集路徑約束和符號狀態。 最終，在程序執行結束后，得到一條完整的路徑約束方程，使用約束求解器對其求解便可得到一條與符號執行時相同路徑的測試用例。 隨著程序的復雜化，出現了“路徑爆炸”和復雜的外部調用等導致靜態符號執行收集到的路徑約束方程無法進行求解。 為了解決上述問題，Cristian Cadar［7］提出了動態符號執行的技術。 當靜態符號執行遇到約束方程無法求解的情況，利用具體值代替符號值，也就是結合具體值與符號值共同執行程序。 Artzi 等人［8］開發的web 缺陷檢測工具Apollo，就使用了動態符號執行的技術生成缺陷檢錯能力更高的測試用例集。 在Apollo 工具中，Artzi等對動態符號執行技術做了改進，為了解決動態符號執行中路徑爆炸和生成冗余測試用例的問題，對路徑約束相似的路徑進行剪枝處理，對由約束求解器求得的相似測試用例進行判斷是否冗余，縮小了測試用例的規模，提高軟件測試的效率。

當前的回歸測試用例生成技術多集中于如何高效地從已有測試用例集中選擇測試用例來覆蓋程序的改動部分。 但是，由于代碼的修改可能會調整代碼的邏輯，僅從歷史測試用例集中選取部分測試用例還是不夠的，需要在所選測試用例集的基礎上，進一步完善測試用例。 而實際上，已有測試用例集的執行信息包含了覆蓋路徑、路徑約束等信息，基于這些信息更能夠準確地分析所選測試用例集覆蓋程序的不完全性，進而構建更完善、準確的回歸測試用例集。

本文提出的基于測試用例的執行信息構建回歸測試用例集方法，首先從原測試用例集中，根據測試執行時，測試用例覆蓋程序的方法，選擇一部分覆蓋改動方法的測試用例作為回歸測試用例選擇集；然后，對修改的部分源程序進行插樁，并執行所有已選擇的測試用例，由插樁語句獲取回歸測試用例選擇集的動態執行信息；最后，整理并分析插樁得到的信息，找出未覆蓋的程序路徑，提取未覆蓋路徑的邏輯表達式組成該路徑下的路徑約束表達式，并對其進行求解，得到的結果即是新的測試用例。

1 方法描述

1.1 回歸測試用例集選擇

由于已有的測試用例是已經執行過的，所以本文假設已經獲得了已有測試用例覆蓋程序方法的信息，根據此信息構建測試用例覆蓋程序方法的矩陣。而代碼經過修改后，形成了代碼的變更信息，可以得到改動后的方法集合。 又因為程序代碼的修改會導致程序的調用發生變化，所以所有直接或間接調用修改方法（包括增加的新方法）的方法，也屬于變更的方法，都應該在回歸測試中被重新測試。 本文將改動方法與受改動方法影響的方法集合稱為該改動相關方法集。

假設在已有的測試用例庫T 中，存在某一測試用例ti（ti∈T），程序方法mi（mi∈M），若執行ti 的測試路徑覆蓋mi，測試用例覆蓋程序方法矩陣中對應值則為1，否則為0。 覆蓋改動相關方法集的所有測試用例構成回歸測試用例選擇集。 表1 給出了一個從已有測試用例中選擇測試用例的示例。

表1 測試用例覆蓋程序方法矩陣Tab. 1 Test case overlay method matrix

假設方法m3 是程序經過維護后修改的方法，而受調用關系，m2 和m5 是方法m3 的相關方法，所以選擇的測試用例集需要覆蓋的方法集合是｛m2，m3，m5｝。 最終，回歸測試用例選擇集為｛t2，t3，t5，t6 ｝。

1.2 動態執行信息的收集

程序經過修改后，代碼邏輯發生改變，從已有測試用例集中選擇的測試用例很有可能不能完全覆蓋程序所有的路徑，導致構建的回歸測試用例選擇集不充分。 為了建立更完整的測試用例集，需要先執行回歸測試用例選擇集，通過動態執行信息分析是否存在未覆蓋的程序路徑，并基于執行結果生成新的測試用例。 所以，收集選擇測試用例動態執行信息的目的有兩個，一是分析回歸測試用例選擇集是否有未覆蓋的程序路徑；二是獲取未覆蓋路徑的路徑約束表達式，通過求解生成新的測試用例。

為了收集回歸測試用例選擇集的動態執行信息，首先需要對源程序進行靜態分析識別出程序修改的部分，然后在修改的部分程序中按照一定的規則進行代碼插樁，插樁輸出的結果包括執行測試用例的執行語句編號、邏輯表達式、邏輯表達式的值、邏輯表達式中各變量的值。 本文定義了以下插樁規則以獲得和記錄上述信息。

為了實現插樁的功能，插樁位置需要設置在修改后的部分程序中的邏輯判斷語句處和代碼中順序執行的多個語句后。 需要特別說明的是，對于沒有改動的部分程序來說，即使存在邏輯判斷表達式或循環語句也不需要對此進行插樁。

插樁規則：

（1）順序執行的語句塊：輸出語句塊標識。

（2）分支語句：輸出執行語句編號、邏輯表達式、邏輯表達式的值、邏輯表達式的各變量值。

（3）循環語句：輸出執行語句編號、循環中的邏輯表達式、循環中邏輯表達式的值、循環中的變量值。

以下是一段簡單的程序代碼，并假設testme 方法中的if 判斷語句即第6 行代碼發生了更改。 下面以此例展示本文的插樁方法以及插樁后輸出的信息。

由于第6 行代碼是更改后的語句，所以testme是變更方法。 受調用關系影響，主方法main 是變更方法的相關方法，所以方法testme 和方法main 都需要重新被測試，由此選擇的部分測試用例也必須覆蓋上述兩個方法，所以這兩個方法也是選擇進行插樁的部分程序。

根據插樁規則，main 屬于順序執行的語句塊，即在該方法的出口處進行插樁輸出該方法的方法塊標識。 而testme 方法中調用的twice 方法不受更改代碼的影響，所以不進行插樁處理。 最終，testme 方法中需要進行插樁的地方是代碼第6、7、8、9、11 行處，由于上述代碼行屬于邏輯判斷結構，所以由插樁語句輸出執行語句編號、邏輯表達式、邏輯表達式的值、邏輯表達式值中各變量的值即可。 最終testme方法經過插樁后的部分代碼如下所示。

以測試用例｛x＝30，y＝15｝ 作為輸入，執行上述插樁后的程序，得到的插樁結果如下方代碼所示：

如第一行輸出數據中，6 表示了當前執行的選擇測試用例的語句編號，“z＝＝x” 是執行的邏輯表達式，T表示該邏輯表達式的值為真，“z＝30，x＝30” 是邏輯表達式中的變量值。

1.3 回歸測試用例集生成

本文基于插樁獲得的信息分析回歸測試用例選擇集中各測試用例所覆蓋程序路徑的情況，通過算法比對得出未覆蓋的程序路徑，然后對未覆蓋的路徑生成新的測試用例，形成回歸測試用例生成集。

為了找出回歸測試用例選擇集未覆蓋的程序路徑，首先需要對插樁得到的信息進行整理，分析被修改的方法中所有邏輯表達式的真假分支是否都被執行，而沒有執行的分支就組成了未覆蓋的程序路徑。

得到未覆蓋的程序路徑之后，需要根據回歸測試用例選擇集的動態執行信息，比對、查找出未覆蓋路徑上的邏輯表達式與邏輯表達式的值。 假如未覆蓋路徑所對應的邏輯表達式的值為T，那么只需要令當前邏輯表達式為T，然后對該約束求解，找出滿足該約束表達式的各變量值。

通過求解路徑約束表達式，可以得到各變量具體的值，進而構建測試用例，使之能測試執行到未覆蓋的程序路徑。 但是，在一些特殊的情況下，例如在路徑約束表達式中的變量需要一系列復雜計算或者該變量取值網絡上的數據時，在生成測試用例的輸入值時，需要進一步分析如何確保路徑約束表達式中的變量能夠取到限定值，使測試執行到未覆蓋路徑。

下面以1.2 節中的程序為例，說明生成新測試用例的過程。 現假設表2 是上述程序經過修改后，通過選擇形成的回歸測試用例選擇集。 將這些測試用例作為輸入，執行插樁后的程序，然后對插樁輸出結果進行處理，得到如表3 所示的動態執行信息表。

表2 回歸測試用例選擇集信息Tab. 2 Information about selected test cases

表3 回歸測試用例選擇集的動態執行信息Tab. 3 Test case execution information

從表3 中可以看到，插樁信息中出現了兩個邏輯表達式分別為A（z＝＝x） 和B（x ＞y＋10），其中邏輯表達式A（z＝＝x）出現了A（F）和A（T）兩個邏輯表達式的值，說明該邏輯表達式中的真假分支均已被執行到，而邏輯表達式B（x ＞y＋10）只出現了B（T） 說明該邏輯表達式只有邏輯為真的分支被執行到，邏輯為假的分支B（F） 并沒有被執行到，所以回歸測試用例選擇集未覆蓋的程序路徑包含該B（F） 分支。

為了得到完整的未覆蓋路徑的約束表達式，可基于回歸測試用例選擇集的動態執行信息構建路徑覆蓋圖，基于路徑覆蓋圖查找該部分程序塊中所有使程序執行到未覆蓋路徑的邏輯表達式。 以表3 為例，構建的路徑覆蓋如圖1 所示。 由圖1 可知， 程序執行到未覆蓋的路徑經歷了兩個邏輯表達式分別為A（z＝＝x） 和B（x ＞y＋10），對應的邏輯表達式的值分別為T 和F，所以最終組成的未覆蓋路徑的約束表達式為（z＝＝x）∧［?（x ＞y＋10）］，對此進行求解即可得到一組使測試執行到未覆蓋路徑的變量值，如｛x＝20，y＝10｝。

圖1 路徑覆蓋圖Fig. 1 Path coverage diagram

2 實驗研究

2.1 實驗對象

前文給出了對修改代碼路徑覆蓋的回歸測試用例集生成方法。 為了驗證本文所提方法的有效性，選取了4 個C 語言編寫的基準程序和兩個C＃語言編寫的web 程序構建實驗，這些程序常被用于軟件測試研究領域［9－10］。 以上程序均采用了不同的維護方法，形成了各試驗程序的不同版本。 表4 列出了每一個實驗程序的名稱、簡要概述、方法個數、代碼行數、測試用例數和維護類型。

表4 實驗程序信息Tab. 4 Experimental program information

2.2 實驗設計與分析

回歸測試用例集生成方法主要有兩部分，一部分是當程序經過變更后，從已有測試用例集中選擇能夠覆蓋全部改動方法的測試用例。 另一部分是對已選測試用例集所未能覆蓋的程序路徑生成新的測試用例。 所以實驗需要驗證的目標有兩個，一是回歸測試用例選擇集的合理性；二是針對于程序未覆蓋的路徑，是否能夠生成新的且正確又有效的測試用例，即回歸測試用例生成集的正確性。

2.2.1 回歸測試用例選擇集的合理性

回歸測試用例選擇集的合理性是指凡是覆蓋程序改動相關方法的測試用例都應該被選入回歸測試用例選擇集，否則不應該選入回歸測試用例選擇集。

實驗步驟：

（1）根據已有測試用例集的歷史執行信息構建已有測試用例集覆蓋程序方法的矩陣。

（2）根據程序代碼的變更信息定位程序改動的方法，并通過分析方法間的調用關系，找出所有與改動相關的方法。

（3）從已有測試用例覆蓋程序的矩陣中選擇覆蓋程序改動部分的測試用例進入回歸測試用例選擇集。

實驗結果：

表5 是回歸測試用例選擇集的結果，主要展示信息有：程序的名稱、原測試用例集的數量、回歸測試用例選擇集的數量，其中，回歸測試用例選擇是在已有測試用例集合的基礎上，選擇覆蓋程序改動部分的測試用例。 例如Financial management 程序，在對程序進行增加類型的維護后，受更改影響的相關方法共有4 個，根據已有測試用例覆蓋程序方法的關系共選擇了90 個測試用例進入回歸測試。

表5 回歸測試用例選擇集信息Tab.5 Test case selection set information

驗證分析：

為了驗證前文所提測試用例選擇方法的合理性，實驗采取了對部分改動程序插樁的方法以記錄回歸測試用例選擇集的執行信息，如果回歸測試用例選擇集中的所有測試用例都執行了程序的改動部分并且未選的測試用例都不執行程序的改動部分，便認為回歸測試用例選擇集是合理的。

表6 是測試用例選擇集的結果驗證，主要信息有程序名稱、代碼改動指因改動而受影響的程序部分、回歸測試選擇集覆蓋的方法集合。 通過收集回歸測試用例選擇集的執行信息即覆蓋程序改動方法的情況，得出了回歸測試用例選擇集中所有的測試用例都執行了程序的改動部分。 并且實驗采取了相同的方法收集了未選入回歸測試用例選擇集的測試用例集合的執行信息，結果顯示未入選的測試用例集合皆未執行程序的改動部分。 由此得出回歸測試用例選擇集是合理的。

表6 回歸測試用例選擇結果驗證Tab. 6 Test case selection verifies results

2.2.2 回歸測試用例生成集的正確性

回歸測試用例生成集的正確性指生成的測試用例集覆蓋了測試用例選擇集中沒有覆蓋的全部路徑。因而，通過執行回歸測試用例生成集，并記錄其執行的路徑便可驗證回歸測試用例生成集的正確性。

實驗步驟：

（1）整理回歸測試用例選擇集的動態執行信息，并通過對動態執行信息的分析找出未覆蓋的程序路徑。

（2）對程序進行向上回溯，找到所有使程序執行到未覆蓋路徑的邏輯判斷表達式構建未覆蓋程序路徑的約束表達式。

（3）求解得到的路徑約束表達式，若有解即是一條新的測試用例。

實驗結果：

表7 是回歸測試用例生成集的結果，主要信息有實驗程序名稱、未覆蓋路徑、回歸測試用例生成集、回歸測試用例生成集覆蓋的路徑。 從表7 中可以看出，前文的測試用例生成方法針對于每個實驗程序中的未覆蓋路徑都有新生成的測試用例。 通過執行新生成的測試用例并記錄其執行信息，得到了測試用例的路徑覆蓋情況。 實驗證實，新生成的測試用例所覆蓋的路徑皆是回歸測試選擇集沒有執行過的程序路徑。

表7 回歸測試用例生成集結果Tab. 7 Test case generation set results

3 結束語

本文提出了一套包含測試用例選擇和測試生成的回歸測試用例構建方案，通過該方法選擇的測試用例集不僅能夠完全覆蓋程序的改動部分，還保持了較小的數據集，能夠一定程度上降低回歸測試選擇集的冗余度。 而生成的新測試用例能夠彌補已有測試用例的覆蓋不足，增加回歸測試的檢錯能力，提高回歸測試的效率。

本文實驗的程序集規模與程序邏輯都不太復雜，約束方程的求解較容易，但隨著實驗程序的規模與復雜性的增加，特別是在有復雜的外部調用或者頻繁的數據庫交互時，會導致約束方程求解困難，使新測試用例生成難度加大。 所以本文方法還需要在約束方程的求解方面進一步完善。