臺灣博碩士論文加值系統

迴歸測試經常執行在主要、次要以及甚至僅更正臭蟲的軟體或韌體的新版本發行。舉例來說，在思科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.

1 INTRODUCTION 1
1.1 MOTIVATION 1
1.2 RELATED WORKS 1
1.3 CONTRIBUTION 3
2 NOTATION DEFINITION AND PROBLEMS 5
2.1 NOTATION DEFINITION 5
2.2 SIX PROBLEMS 7
3 DESIGNING SIX ALGORITHMS 10
3.1 PDF-SA ALGORITHM 10
3.2 CW-NUMMIN, CW-COSTMIN AND CW-COSTCOVB ALGORITHMS 10
3.3 CW-COVMAX ALGORITHM 13
3.4 CW-COSTMIN-C ALGORITHM 14
4 SYSTEM DESIGN AND IMPLEMENTATION 16
4.1 TESTING SERVER 16
4.2 RFC CONVERTER AND IMPORTER 17
4.3 RFC DATABASE 17
4.4 RFC VIEWER 18
5 EXPERIMENTAL RESULTS 19
5.1 CHARACTERISTICS OF THE TEST-FUNCTION MAPPINGS 19
5.2 RESULT ANALYSIS 23
5.2.1 The impact of different test intensity threshold 23
5.2.2 Inside the results 24
5.2.3 CW-NumMin and CW-CostMin results 25
5.2.4 CW-CostCovB Results 25
5.2.5 CW-CovMax Results 26
5.2.6 CW-CostMin-C results 28
5.2.7 PDF-SA Results 29
6 CONCLUSIONS 32
7 REFERENCE 34

[1] W. E. Wong, J. Horgan, S. London, and A. Mathur, “Effect of test set minimization on fault detection effectiveness.” Software – Practice and Experience, 28(4):347-369, Apr. 1998
[2] G. Rothermel, M. J. Harrold, J. Ostrin, and C. Hong, “An empirical study of the effects of minimization on the fault detection capabilities of test suites,” in Proceedings of International Conference on Software Maintenance, pp.34-43, 1998
[3] H. K. N. Leung and L. White, “Insights into regression testing,” in Proceedings of International Conference on Software Maintenance, Miami, FL, USA, Oct. 1989, pp.60-69
[4] M. R. Garey and D. S. Johnson, “Computers and intractability: a guide to the theory of NP-completeness,” W. H. Freeman, Jan. 1979
[5] M. J. Harrold, R. Gupta, and M. L. Soffa, “A methodology for controlling the size of a test suite,” ACM Transactions on Software Engineering and Methodology, Vol. 2, No. 3, 1993, pp. 270-285
[6] D. Jeffrey and N. Gupta, “Test suite reduction with selective redundancy,” International Conference on Software Maintenance, 2002. Proceedings., Sep. 2005
[7] D. Jeffrey and N. Gupta, “Improving fault detection capability by selectively retaining test cases during test suite reduction,” IEEE Transactions on Software Engineering, Vol. 33, Feb. 2007
[8] T. Y. Chen and M. F. Lau, “A new heuristic for test suite reduction,” Information and Software Technology, Vol. 40, No. 5, 1998, pp. 347-354
[9] T. G. Whitten, C. Springs and Colo, “Method and computer program product for generating a computer program product test that includes an optimized set of computer program product test cases, and method for selecting same,” United States Patent[5,805,795], Sep. 1998
[10] X. Y. Ma, Z. F. He, B. K. Sheng, and C. Q. Ye, “A genetic algorithm for test-suite reduction”, 2005 IEEE International Conference on Systems, Man and Cybernetics, Vol. 1, Oct. 2005, pp.133-139
[11] N. Mansour and K. El-Fakin, “Simulated annealing and genetic algorithms for optimal regression testing,”, Journal of Software Maintenance: Research and Practice, Vol. 11, No. 1, 1999, pp. 19-34
[12] J. Black, E Melachrinoudis, and D. Kaeli, “Bi-criteria models for all-uses test suite reduction,” International Conference on Software Engineering, 2004, pp. 106-115
[13] H. Zhong, L. Zhang, H. Mei, “An experimental comparison of four test suite reduction techniques,” POSTER SESSION: Far east experience papers, pp.636-640
[14] T. Y. Chen and M. F. Lau, “A simulation study on some heuristics for test suite reduction,” Information and Software Technology, Vol. 40, no. 13, Nov. 1998, pp. 777-787
[15] G. Rothermel, R. H. C. Chu and M. J. Harrold, “Prioritizing test cases for regression testing,” IEEE Transactions on Software Engineering, Vol. 27, Oct. 2001
[16] A. G. Malishevsky, G. Rothermel, and S. Elbaum, “Modeling the cost-benefits tradeoffs for regression testing techniques.” In Int’l. Conf. Softw. Maint., Oct. 2002, pp. 230–240
[17] W. E. Wong, J. Horgan, A. Mathur, and A. Pasquini, “Test set size minimization and fault detection effectiveness: A case study in a space application,” Journal of Systems and Software, 48:79-89, Oct. 1999
[18] G. Rothermel, M. J. Harrold, J. von Ronne, and C. Hong, “Empirical studies of test-suite reduction,” Software Testing Verification and Reliability, Vol. 12, No. 4, 2002, pp. 219-249
[19] Testwell CTC++, [online], available from World Wide Web: http://www.testwell.fi/ctcdesc.html
[20] Deitel, Deitel, Nieto & McPhie perl, “Perl: how to program,” Prentice-Hall, 2001
[21] The Perl Directory, [online], available from World Wide Web: http://www.perl.org
[22] SQL語法教學, [online], available from World Wide Web: http://www.1keydata.com/tw/sql/sql.html
[23] 朝井淳, “SQL語法範例辭典,” 旗標出版股份有限公司, Feb. 2007
[24] 陳俊宏, “PHP5 & MySQL 徹底研究,” 旗標出版股份有限公司, June 2004
[25] M. Kofler, “The definitive guide to MySQL 5, 3rd ed.,” Apress L.P., 2006
[26] The phpMyAdmin Project, [online], available from World Wide Web: http://www.phpmyadmin.net/home_page/index.php
[27] AppServ Open Project, [online], available from World Wide Web: http://www.appservnetwork.com/
[28] MySQL, [online], available from World Wide Web: http://www.mysql.com/
[29] PHP, [online], available from World Wide Web: http://www.php.net/
[30] 葉昌福, “PHP函示庫參考手冊,” 旗標出版股份有限公司, Dec. 2004