在數量極大的程式碼中解決測試覆蓋度的最佳化問題

Abstract

迴歸測試經常執行在主要、次要以及甚至僅更正臭蟲的軟體或韌體的新版本發行。舉例來說，在思科IOS的一部份原始碼中，總共有2,320個測試用例用來檢查57,758個函式，若在任一次的新版本發行中，將所有的測試用例執行過，則需要36天。在以前的減少測試演算法的研究中，基於聲明程度的條件/分歧的測試覆蓋度資訊並無法適用於較大的程式，因此難以套用於真實的產品系統中。在本文裡，我們將根據某測試用例測到某函式的覆蓋度資訊，致力於開發真實測試方法。當測試資訊的詳細度從條件/分歧減少為函式時，可降低很多複雜度並且能夠有好的延展性。首先，我們定義一個測試用例的函式可達度（一個測試用例可以測到多少百分比的函式）以及一個函式的測試強度（百分之多少的測試用例可以測到特定函式）。透過這兩個標準，覆蓋度的資訊就可被特徵化。然後我們透過或不透過安全模式來應用貪婪演算法去選取測試用例，所謂安全模式是指，凡是含有修改過函式的測試例都會被選取出來。在不使用安全模式的情形中，從部份IOS的平均結果看來，我們能夠減少測試成本（時間）為原本的1/91。透過安全模式，降低的比例隨著修改過的函式以及它們的測試強度增加而降低。大多數的更正臭蟲的新版本發行僅修改一個或很少的函式並且它們的測試強度很低，在此我們的方法能夠應用的更安全及更有效率。

Regression testing is conducted frequently on major, minor, and even bug-fix software or firmware releases. For example, as a part of Cisco IOS source codes with 57,758 functions checked by 2,320 test cases, it requires 36 days if all test cases are run on a release. Previous research works on test reduction algorithms select test cases based on the test coverage information of statement-level conditions/branches and could not scale to larger programs, and thus are difficult to apply in real production systems. In this work, we aim to develop a practical test reduction approach based on the coverage information of which test cases "touch" which functions. Since the granularity of coverage information is reduced from condition/branch to function, the complexity is much reduced and could scale well. We first define function reachability of a test (the percentage of functions that a specific test could touch) and test intensity of a function (the percentage of tests that touch a specific function). With these two metrics, the coverage information is characterized. We then apply greedy algorithms to select test cases, with or without a safe mode that selects all test cases touching modified functions. The results from instrumenting parts of IOS show that we could reduce the test cost (time) to 1/91, on the average, without a safe mode. With a safe mode, the reduction ratio drops as the number of modified functions and their test intensities increase. Numerous bug-fix releases modify only one or very few functions with low test intensity, where our approach can be applied safely and effectively.