Design and Analysis of Cost-Cognizant Test Case Prioritization Using Genetic Algorithm with Test History

運用基因演算法與測試歷史於成本認知的測試個案排序之設計與分析

黃昱齊(Yu-Chi Huang)

指導教授 ： 黃慶育

國立清華大學/電機資訊學院/資訊工程學系/碩士(2009年)

https://doi.org/10.6843/NTHU.2009.00647

摘要

Regression testing is an expensive testing process used to assure the quality of modified software. Test case prioritization techniques schedule test cases for regres-sion testing in an order that attempts to increase the effectiveness in terms of meeting some performance goal. The most general performance goal, the rate of fault detection, measures how quickly faults are detected within the testing process. It assumes all test case costs and fault severities are uniform. However, test case costs and fault sever-ities are usually vary. In order to produce a more satisfactory order, the cost-cognizant metric that incorporates varying test case costs and fault severities is proposed. In this thesis, we propose a cost-cognizant test case prioritization technique based on the use of historical records. We gather historical records from the latest regression testing and then use a genetic algorithm to determine the most effective order. We run a con-trolled experiment to evaluate the proposed technique’s effectiveness. We compare the proposed technique with five existing techniques, and with two techniques that serve as an experiment control. Experimental results indicate that our proposed technique frequently yields a higher Average Percentage of Faults Detected per Cost (APFDc). The results also show that our proposed technique is also useful in terms of APFDc when all test case costs and fault severities are uniform.

關鍵字

回歸測試 ； 成本認知測試個案排序 ； 測試個案成本 ； 錯誤嚴重度 ； 偵錯速率 ； APFDc

並列摘要

回歸測試是一個昂貴的測試程序，他常用來確保經過修改後的軟體之品質。測試個案優先排序技術排定測試個案在回歸測試中被執行之優先順序，期望能增加測試的效力並達到所設定的效能目標。最常見的效能目標是偵測錯誤之速度，也就是在測試過程中，錯誤能多快地被找到。此效能目標假設所有測試個案之執行成本以及所找到的錯誤之嚴重程度都是一致的。然而，測試個案之執行成本以及所找到的錯誤之嚴重程度往往是不同的。為了產生更符合現實的測試個案執行順序，具成本認知的效能目標被提出。他在評估測試效力時，將測試個案之執行成本以及所找到的錯誤之嚴重程度納入考量。
在本篇論文中，我們提出了一個以測試歷史導向並具成本認知的測試個案優先排序技術。我們收集上一次回歸測試所留下來的測試歷史紀錄，接著運用基因演算法結合這些歷史紀錄找出在過去具有最高效能的測試個案執行順序。此外 ，我們利用受控實驗來評估所提出的方法之測試效果。我們將其與其他五個已存在的測試個案優先排序技術及兩個作為實驗控制的測試個案優先排序技術做比較。實驗結果指出，我們所提出來的方法經常能產生具有較高Average Percentage of Faults Detected per Cost (APFDc)值的測試個案優先排序。實驗結果也顯示，即使測試過程中所有測試個案之執行成本以及所找到的錯誤之嚴重程度都是一致的，所提出的方法依然能找出有效的測試個案優先排序。

並列關鍵字

regression testing ； cost-cognizant test case prioritization ； test cost ； fault severity ； rate of fault detection ； Average Percentage of Faults Detected per Cost

參考文獻

[1] J.M. Kim, A. Porter, and G. Rothermel, “An Empirical Study of Regression Test Application Frequency,” Proc. 22nd Int’l Conf. Software Eng., pp. 126-135, June 2000

[2] D. Binkley, “Semantics Guided Regression Test Cost Reduction,” IEEE Trans. Software Eng., vol. 23, no.8, pp. 498-516, Aug. 1997

[4] H.K.N. Leung and L.J. White, “A Study of Integration Testing and Software Re-gression at the Integration Level,” Proc. Conf. Software Maintenance, pp. 290-300, Nov. 1990.

[5] G.. Rothermel and M.J. Harrold, “A Safe, Efficient Regression Test Selection Technique,” ACM Trans. Software Eng. And Methodology, vol. 6, no. 2, pp. 173-210, Apr. 1997.

[6] T.L. Graves, M.J. Harrold, J.M. Kim, A.Porter, and G. Rothermel, “An Empirical Study of Regression Test Selection Techniques,” ACM Trans. Software Eng. And Methodology, vol 10, no. 2, pp. 184-208, Apr. 2001.