基于提交排序和預測模型的測試套件選擇方法

劉美英，楊秋輝，王瀟，蔡創

（四川大學計算機學院，成都 610065）

0 引言

持續集成（Continuous Integration，CI）是一種軟件開發實踐，每次集成都通過自動化的構建和測試進行驗證，保證頻繁變更的代碼快速安全地集成到主線代碼庫，而隨著版本的快速變更所需要的測試資源也在不斷增長［1］。例如在Google 中，平均每秒觸發的測試執行次數多達1.5 億［2］。因此，提升CI 環境中的回歸測試效率是至關重要的。

CI 環境中的回歸測試，主要問題是大量提交導致的頻繁構建和測試導致的測試資源過于龐大、反饋周期較長［3］。為此，Liang 等［4］提出對CI 環境中的提交進行優先級排序，可以提高故障檢測率，但不能降低測試成本。另外Machalica 等［5］采用人工智能領域技術對測試進行選擇以加快測試反饋。該方法雖然能降低測試成本，但沒有考慮CI 中大量提交到達的情況，忽略了密集提交的順序對排序質量的影響。

在CI 中，為了對不斷到達的變更提交進行回歸測試，在保證故障檢測率的同時降低測試成本，滿足持續集成的質量和速度需求。綜合考慮故障檢測路和測試成本，提出CI 中一種新的回歸測試選擇方法：基于提交排序和預測模型的測試套件選擇方法。本文方法包含提交排序和測試套件選擇兩個階段。首先根據各個提交的歷史失敗率和執行率進行排序；之后對提交包含的測試套件采用XGboost 算法構建失敗率預測模型，選擇高失敗率測試套件執行。在Google 的共享數據集上進行評估，在開銷感知平均故障檢測率（Average Percentage of Faults Detected per cost，APFDc）、選擇率（SelectionRate）、測試召回（TestRecall）、變更召回（ChangeRecall）四個指標上本文方法比文獻［4-5］方法有更好的表現。

1 相關工作

文獻［6-11］基于歷史執行信息，研究了歷史測試數據對優先級技術效率的影響，證實了歷史執行數據對測試用例優先級（Test Case Priorization，TCP）排序技術研究的重要性。文獻［12］基于歷史日志信息設計了回歸測試優先級排序算法，優化了持續集成測試流程。Do 等［13］評估了時間限制對TCP 技術的成本和收益的影響，從經濟有效的回歸測試角度給予了測試工程師啟示。Liang 等［4］提出基于提交的排序技術（Continuous，Commit-Based Prioritization，CCBP），該方法使用測試套件失敗和執行信息對CI 中持續到達的提交進行優先級排序；但該方法仍然需要執行提交中的全部測試套件，測試成本并未得到有效降低。

文獻［14-18］根據回歸測試歷史信息提出了一系列測試選擇技術，證實了執行歷史對回歸測試選擇（Regression Test Selection，RTS）技術研究的重要性。Machalica 等［5］提出一種新的預測測試選擇策略，基于歷史執行信息對測試套件進行失敗率預測和選擇。但該方法并沒考慮到密集提交環境中多個提交間的序列對故障檢測率的影響。

另外，現有研究也包含TCP 和RTS 混合優化技術。Elbaum 等［19］提出在測試預提交階段使用RTS 技術選擇測試套件的子集，在提交后的測試階段使用TCP 技術確保故障快速反饋。Spieker 等［20］介紹了Rerecs，一種能自動學習CI 中TCP 和RTS 的新方法，旨在最大限度減少反饋時間。Najafi等［21］根據先驗的TCP 和RTS 方法，確認了測試執行歷史中失敗信息的價值。本文參考以上文獻，提出基于提交排序和預測模型相結合的回歸測試選擇方法，是一種歷史數據驅動的回歸測試優化方法。

2 本文方法

本文提出了一種提交排序和測試套件選擇相結合的持續集成回歸測試優化方法，可以提高故障檢測率，同時降低測試成本。本文方法的流程如圖1 所示。

圖1 本文方法的流程Fig.1 Flowchart of the proposed method

提交排序階段，對等待隊列中的所有提交，根據其相關測試套件在版本控制儲存庫中的執行歷史，進行失敗率和執行率計算，然后對當前版本的提交進行排序。測試套件選擇階段，對于已排序的各個提交作如下處理：對當前提交所包含的測試套件，使用預先構建好的模型進行測試套件選擇。而測試套件選擇模型是在執行回歸測試前，使用版本控制數據庫中的歷史信息構建的。為了提高效率，測試套件失敗率預測和選擇模型的構建可以周期性地，每一周或者幾天更新，其構建過程包括收集版本控制庫中的歷史提交和執行數據，然后進行數據預處理，最后建模。

2.1 提交排序

CI 環境下存在多個開發人員持續發起提交，每次測試結果也隨之更新，此時優先級排序方法要求必須是輕量級并且能快速持續進行。一段時間內可能對相同隊列進行多次排序，導致傳統的代碼插裝和變更分析技術不再適用。文獻［4］認為在提交級別針對多個提交進行優先級排序后的測試表現更符合CI 環境的測試特點。本文根據動態的提交和測試結果信息采用基于提交的排序方法。

該過程涉及三類數據：1）提交本身，包含該提交到達的時間及相關聯的測試套件集。另外還需人為計算一組屬性，包括提交的預期故障率（基于提交的測試套件失敗的概率）和執行率（提交的測試套件最近未執行的概率），分別用于優先級排序；2）待執行的提交（commitQ）隊列。到達的提交會添加到commitQ 中，執行中的提交會從commitQ 中移除，當資源可用，就對commitQ 進行優先級排序；3）失敗窗口的大小（failWindowSize）和執行窗口的大小（exeWindowSize），可根據提交的數量衡量，在本次實驗中設定為固定值，實際環境中也可根據不同條件進行調整。

提交排序的基本思想是，當新的提交到達時先加入等待隊列，只有當隊列不為空且測試資源可用時，才對等待隊列中的所有提交分別計算所包含的測試套件的歷史失敗率和執行率，歷史失敗率指在最近歷史中該提交的失敗測試套件數占測試套件總數的比例，執行率指在最近歷史中該提交執行過的測試套件數占測試套件總數的比例。最近歷史由失敗窗口和執行窗口限制，例如失敗窗口和執行窗口大小為5，最近歷史為距本次提交最近的5 次提交的測試套件的失敗和執行歷史。首先比較提交的失敗率，失敗率更高則優先級更高；失敗率相同則比較執行率，執行率低的測試套件對應的提交優先級更高，以此得到最高優先級提交，將其移出等待隊列并釋放資源。提交優先級排序算法的偽代碼如下。

算法1 提交排序算法。

輸入按時間先后到達的提交集合commitQueue，包含多個commit，每個commit 的測試套件集testSuites，包含多個測試套件。

輸出最高優先級提交。

2.2 基于預測模型的測試套件選擇

CI 中記錄了項目中受變更影響的測試套件的執行結果，因此可以通過歷史結果信息構建預測模型，對測試套件進行失敗率預測，從而選擇失敗可能性較高的測試套件。

2.2.1 數據收集和預處理

為收集CI 中的項目數據，可從版本控制庫和CI 服務器中通過提交日志和構建日志獲取相關的提交和測試數據。如提交的執行結果、提交包含的測試套件集、各測試套件執行結果，最后將關聯信息通過進行人工或統計程序分析得到各測試套件失敗次數、執行次數，合并數據得到樣本數據集。數據預處理部分采用基于包裝器Wrapper［22］的特征選擇方法。使用XGboost 作為特征選擇的基模型，通過枚舉法進行特征子集遍歷，將去掉該特征的特征集與全特征集的選擇率selectionRate的比值作為分類度量，數量閾值numberThreshold作為排名度量，探索去掉某一特征集對模型的影響。分類度量、排名度量大于1 則表示有積極影響，選擇該類特征作為最終特征子集。

2.2.2 預測模型構建

使用XGboost 算法［23］構造測試套件失敗率預測模型學習器，變更提交c和與之相關的測試套件集作為輸入，失敗的測試套件標記為正例，反之為負例。XGboost 學習器相當于一個函數，根據輸入返回一個區間在［0，1］的分數score（c，t），表示測試套件t在提交c中的失敗概率。測試套件選擇策略由預先定義的分數閾值scoreThreshold和數量閾值numberThreshold控制。兩個參數閾值的確定方法基于文獻［5］中通過反復評估模型性能不斷調整得到，模型評估時先定義需要達到的測試召回和變更召回標準，再調整兩個參數的值。模型構建的流程如圖2 所示。

圖2 測試套件失敗率預測和選擇模型構建流程Fig.2 Construction flowchart of test suite failure rate prediction and selection model

2.2.3 測試套件失敗率預測和選擇

用構建的模型進行測試套件失敗率預測和選擇。首先對提交的測試套件進行數據預處理，得到符合XGboost 學習器輸入的特征值的集合作為待預測樣本輸入；然后學習器進行預測，預測后返回每個測試套件的分數score（c，t）；最后選擇score（c，t）≥scoreThreshold的測試套件t，且選擇的測試套件總數量不超過numberThreshold。

3 實驗驗證

3.1 實驗數據

本文使用Google 共享數據集［24］，包含15 d 內收集的超過2 506 926 個測試套件的執行信息。原始數據集的相關統計信息如表1 所示。

3.2 評估指標

為綜合考慮選擇質量和故障檢測率，故使用測試召回（TestRecall）、變更召回（ChangeRecall）、選擇率（SelectionRate）、開銷感知平均故障檢測率APFDc四個指標評估本文方法。本文引用文獻［5］中的三個度量標準來優化選擇模型和評估質量。設C是一組變更提交，FC是更改c中失敗測試套件集，，SelectedTests（c）是更改c中選擇的測試套件集，AllTests（c）是更改c相關的所有測試套件。測試召回（TestRecall）：表示選擇的測試套件屬于失敗測試套件集的概率，其定義見式（1）。變更召回（ChangeRecall）：表示選擇的測試套件屬于包含失敗測試套件的變更提交的概率，其定義見式（2）。選擇率（SelectionRate）：表示選擇的測試套件與提交包含的所有測試套件的比例，其定義見式（3）。其中TestRecall、ChangeRecall的值越高，SelectionRate越低，則回歸測試選擇的質量越好。

為評估故障檢測率，使用了改進的APFDc度量標準［4］。APFDc是基于成本的平均故障率表示，與傳統的基于測試用例級別的APFDc［25］不同，改進后的APFDc考慮的是測試套件的執行過程，對測試套件的故障檢測率進行評估。APFDc的計算公式見式（4）：

其中：T為有序的測試套件集；n為T中的測試套件總數；F為有故障的測試套件集；m為F中的測試套件數；TFi為首次檢測到F中第i個有故障的測試套件在T中的次序；tj為第j個測試套件的執行開銷。

3.3 構建失敗率預測和選擇模型

為在Google 開源數據集應用本文方法，首先根據文獻［4］將窗口大小設為10，測試資源設為1，即最近歷史限制為考慮最近的10 次提交的測試信息，且整個流程中測試資源只能被一個提交所使用即同一時間只考慮單個提交的測試執行。使用Java 多線程模擬提交的到達和優先級排序。

根據文獻［5，26］使用的特征在原始數據集上增加了一些需計算得到的特征，其中包含提交觸發的測試套件數（Test suite cardinality）、測試套件的歷史失敗率（History failure rate）、測試套件的歷史執行率（History execution rate）。基于包裝器Wrapper 方法，在TestRecall=0.9 時計算模型的分類度量和排名度量，最后選擇分類度量和排名度量大于1 的特征得到構建模型的特征子集：History failure rate、History execution rate、Size 和Language。

最后將原始數據集按6∶2∶2 劃分為訓練集、驗證集和測試集。在訓練集上構建初步模型觀察得到學習率為0.05，故設置選擇策略的參數scoreThreshold=0.05，numberThreshold=10。在驗證集上評估模型調整兩個參數值，在該過程中將模型標準定位測試召回設為0.9 以上，變更召回設為0.95 以上，分別計算測試召回在scoreThreshold和變更召回在numberThreshold的依賴性。最終得到在GooglePre 驗證集上scoreThreshold≈0.35，numberThreshold≈362；在 GooglePost 驗證集上scoreThreshold≈0.32，numberThreshold≈240。

3.4 對比實驗及結果分析

本文方法先對提交進行優先級排序再選擇測試套件執行，因此與同樣采用提交排序的文獻［4］方法、采用測試套件選擇的文獻［5］方法作對比實驗驗證方法的有效性。在Google 共享數據集上：對文獻［4］方法進行重現并獲得實驗結果；對于文獻［5］，由于Google 開源數據集與文獻［5］方法所使用的私有數據集相比缺少一些特征，如涉及到源代碼的文件數、作者名及文件間的依賴性，導致模型在構建時的輸入特征有差異，因此本文對文獻［5］的核心算法進行實現。

1）故障檢測率對比。為對比方法的故障檢測速度，不限制測試成本，分別記錄三種方法在Google 共享數據集上的測試執行時間和包含失敗測試套件的提交執行比例，統計分別在執行時間到達25%、50%以及75%時執行的包含失敗測試套件的提交比例，并計算各自的APFDc值。

GooglePre 數據集上的結果如表2 所示。由表2 可知，本文方法的包含失敗測試套件提交的執行比例即揭錯率在各時間節點的表現都優于另兩種方法。其中本文方法比文獻［4］方法的揭錯率提高了17.9%～30.2%，比文獻［5］方法的揭錯率提高了4.8%～32.0%。

表2 不同時間執行率下不同方法的揭錯率對比 單位：%Tab.2 Comparison of error revealing rate under different methods unit：%

GooglePost 數據集上結果如表2 所示。由表2 可知，本文方法的揭錯率在各個時間節點的表現都優于文獻［5］方法，其中本文方法比文獻［5］方法揭錯率提高了11.5%～104.4%。與文獻［4］方法相比，雖然執行時間在25%節點時，本文方法表現略差，但隨著時間的增加，本文方法的提交執行比例逐步超過文獻［4］方法，執行時間在75%節點時揭錯率提高了7.4%。從以上結果可知，經過提交優先級排序的測試選擇技術能更早檢測到更多的缺陷。

APFDc值對比結果如表3 所示。在GooglePre 數據集上，本文方法的APFDc值比文獻［4］方法高0.126 2，比文獻［5］方法高0.098 7。在GooglePost 數據集上，本文方法的APFDc值比文獻［4］方法高0.005 6，比文獻［5］方法高0.014 5。因此本文方法最高在現有方法的結果基礎上提高了1%～27%。通過測試的揭錯率和APFDc值的比較，本文的方法可以提高基于成本的故障檢測率，更早地檢測到更多的缺陷。

表3 不同方法的APFDc值對比Tab.3 APFDc value comparison

2）為評估選擇的質量，限制測試成本。三種方法的測試成本為文獻［4］方法＞本文方法＞文獻［5］方法，以本文方法的測試成本為基準，三種方法在測試過程中時間到達則停止測試。統計三種方法選擇的測試套件數、包含失敗的測試套件數、包含失敗測試套件的變更提交數，并計算各自的測試召回、變更召回和選擇率。

由圖3 可知與文獻［4］方法相比，在GooglePre 數據集上，本文的TestRecall、ChangeRecall的值比文獻［4］方法的值分別高38.16、15.67 個百分點，SelectionRate的值比文獻［4］方法低6.2 個百分點。由圖4 可知在GooglePost 數據集上，本文的TestRecall、ChangeRecall的值比文獻［4］方法的值分別高33.33、24.52 個百分點。SelectionRate的值比文獻［4］方法低6.33 個百分點。

圖3 GooglePre數據集上TestChange、ChangeRecall和SelectionRate的對比Fig.3 Comparison of TestChange，ChangeRecall and SelectionRate on GooglePre dataset

圖4 GooglePost數據集上TestChange、ChangeRecall和SelectionRate的對比Fig.4 Comparison chart of TestChange，ChangeRecall and SelectionRate on GooglePost dataset

TestRecall和ChangeRecall高是因為受測試成本影響，文獻［4］方法做實驗時丟失了一部分失敗測試套件。文獻［4］方法選擇率高是因為在同樣的時間成本下執行的測試套件的數量更多。

與文獻［5］方法相比，本文方法的TestRecall、ChangeRecall的值略高一些，由于經過提交排序后的一些測試套件集的特征值History failure rate 更高，失敗率預測的分數更大使被選擇的失敗測試套件集更多。雖然本文方法與文獻［5］方法構建模型的特征略有差異，導致選擇的質量并不夠理想，但本文綜合使用提交排序和測試套件選擇的方法比文獻［5］方法只使用測試套件選擇的方法效果更好。從構建模型的角度出發，更多有效的信息來源，如代碼更改的歷史，都能以附加特征的形式納入測試選擇模型中以提高選擇的性能，這一點在未來工作中是值得探索的。總的來說，本文方法在給定的測試成本下，選擇了相對較少的測試套件，提高了測試套件的測試召回和變更召回。

綜合上述結果，在不限測試成本情況下，本文方法的APFDc值更高，即提高了故障檢測率的速度；以本文測試成本為統一基準，本文方法的TestRecall和ChangeRecall值更高，SelectionRate值更低，即降低了測試成本。因此將提交優先級排序和測試選擇套件選擇相結合的方法提高了故障檢測率，并降低了測試成本。

4 結語

為在持續集成環境中取得反饋速度和測試成本間的平衡，本文提出了一種結合提交優先級排序和測試套件選擇的方法。該方法分兩階段：第一階段對提交進行優先級排序，并對提交等待隊列進行持續的優先級排序，提交排序方法作為只考慮失敗率和執行率的輕量級方法，在CI 環境中能快速完成排序；第二階段對前一階段得到的最高優先級提交包含的測試套件采用構建的失敗率預測模型預測，選擇高失敗率測試套件執行。通過對比實驗，驗證了本文方法的有效性。

本文綜合考慮故障檢測率和測試成本，解決在持續集成環境中測試成本過高、提交序列影響測試反饋速度的問題，但還存在不足之處。比如：在提交優先級排序技術中，沒有關注提交之間的依賴關系，且只考慮了單個測試資源可用的情況，未來可研究基于上述情況動態調整排序算法，輸出多個優先級較高的提交。構建測試套件選擇模型中，對于特征集子集的選擇未來可使用更多變更影響技術分析得到最具代表性的特征子集。對于一些新代碼的提交，包含的歷史信息較少，本文方法可能并不適用。