臺灣博碩士論文加值系統

軟體的使用和人們的日常生活密不可分，因此開發者須嚴謹地進行軟體開發。為了軟體的正確性，在開發過程中，審慎地執行軟體測試是必要的。隨著軟體系統的功能因為客製化需求而持續的更新，新的測試個案會被生成並納入既有的測試個案池中，最後，測試個案池將會變得非常龐大，導致測試人員要花費大量的時間來做低效率的回歸測試。測試個案精簡為其中一種知名的議題，其做法為藉由移除冗餘的測試個案來解決上述之問題，經移除後，測試個案池的大小將被壓縮，但剩餘的測試個案群仍能保持和原先測試個案池相同的覆蓋率。然而，大多數既有的傳統測試個案精簡方法中，僅考慮單一，或者兩個不對等的評估標準。在本研究中，我們提出三種改良後的權重組合演算法，可以彈性並同時去考量兩種不同類別的評估標準。除此之外，我們亦利用基因演算法來找出每種評估標準最適合配置的權重值。實驗結果顯示，使用本方法能保持幾乎相同的測試套件大小精簡比率，但卻能大幅提升所挑選之測試個案子集的偵錯能力。

Using software has become a very important part of our daily life. Therefore, strict and rigorous development of software is necessary for developers. Software testing should be conducted carefully in the development process for minimal errors and ease of product usability. With the continuous functionality updating of software systems according to customized requirements, new test cases have been generated and included in the existing test pool. Finally, the size of test pool has often been too large, which costs large amounts of time to produce inefficient regression testing. Test suite reduction is one of the well-known issues, which is used to solve the size problem by removing redundant test cases. Following such, the test pool size can be reduced, while the remaining test cases are still able to provide the same coverage as the original test pool. However, most of the existing test suite reduction methods have considered only one or two testing criteria with no equivalence between them. In this paper, we propose three modified weighted combinatorial algorithms to flexibly and simultaneously consider two different types of testing criteria. Further, we also use a genetic algorithm to find the best weighting factor value assignment for each testing criterion. Experimental results show that our approach can keep nearly the same suite size reduction percentage, while significantly enhance the fault detection effectiveness in the selected representative test suite subset.

Abstract in Chinese 1
Abstract 2
Acknowledgement 3
Contents 4
List of Tables 7
List of Figures 8
Chapter 1 Introduction 9
Chapter 2 Background and Related Works 12
2.1 Test Suite Reduction 12
2.1.1 Review of Test Suite Reduction 12
2.1.2 The Well-known Existing Solutions 14
2.2 Combination of Structural Testing Criteria 21
Chapter 3 Weighted Combinatorial Algorithms 25
3.1 Weighted Statistical Means 25
3.2 Evaluation Metric 28
3.3 Proposed Weighted Combinatorial Algorithms 34
3.3.1 WC-Greedy: The Modified Weighted Combinatorial Greedy Algorithm 35
3.3.2 WC-HGS: The Modified Weighted Combinatorial HGS Algorithm 37
3.3.3 WC-GRE: The Modified Weighted Combinatorial GRE Algorithm 40
3.4 Weighting Factor Assignment 45
Chapter 4 Experiments and Analysis 48
4.1 Experimental Setup and Subject Programs 48
4.2 Comparison Criteria 51
4.3 Experimental Results of Applying the WC-Greedy Algorithm 52
4.3.1 Suite Size Reduction 53
4.3.2 Fault Detection Effectiveness Loss 54
4.3.3 A t-test for Matched Pairs 55
4.3.4 Fault-to-test Ratio 56
4.4 Experimental Results of WC-HGS 57
4.4.1 Suite Size Reduction 58
4.4.2 Fault Detection Effectiveness Loss 58
4.4.3 A t-test for Matched Pairs 59
4.4.4 Fault-to-test Ratio 60
4.5 Experimental Results of WC-GRE 62
4.5.1 Suite Size Reduction 62
4.5.2 Fault Detection Effectiveness Loss 62
4.5.3 A t-test for Matched Pairs 64
4.5.4 Fault-to-test Ratio 64
4.6 Overall Comparison of FDE Loss Improvement 66
4.7 Discussions and Observations 69
Chapter 5 Conclusions and Future Works 72
References 74
Appendixes 79
Appendix A. Comparisons between the Greedy and WC-Greedy algorithms 79
A-1. Suite Size Reduction 79
A-2. Fault Detection Effectiveness Loss 81
A-3. Faults-to-test Ratio 83
Appendix B. Comparisons between the HGS and WC-HGS algorithms 85
B-1. Suite Size Reduction 85
B-2. Fault Detection Effectiveness Loss 87
B-3. Faults-to-test Ratio 89
Appendix C. Comparisons between the GRE and WC-GRE algorithms 91
C-1. Suite Size Reduction 91
C-2. Fault Detection Effectiveness Loss 93
C-3. Faults-to-test Ratio 95

[1] P. Ammann and J. Offutt. Introduction to Software Testing, Cambridge University Press, 2008.
[2] E. Rogstad, L. C. Briand, and R. Torkar, “Test case selection for black-box regression testing of database applications,” Information & Software Technology, Vol. 55, Issue 10, pp. 1781–1795, 2013.
[3] P. G. Sapna and A. Balakrishnan, “An Approach for Generating Minimal Test Cases for Regression Testing,” Information & Software Technology, Vol. 47, pp. 188–196, 2015.
[4] M. J. Harrold, D. Rosenblum, G. Rothermel, and E. Weyuker, “Empirical studies of a prediction model for regression test selection,” IEEE Transactions on Software Engineering, Vol. 27, Issue 3, pp. 248–263, 2001.
[5] S. Mirarab, S. Akhlaghi, and L. Tahvildari, “Size-Constrained Regression Test Case Selection Using Multi-Criteria Optimization,” IEEE Transactions on Software Engineering, Vol. 38, Issue 4, pp. 936–956, Jul./Aug. 2012.
[6] D. Binkley, “Semantics guided regression test cost reduction,” IEEE Transactions on Software Engineering, Vol. 23, Issue 8, pp. 498–516, 1997.
[7] H. Zhong, L. Zhang and H. Mei, “An experimental study of four typical test suite reduction techniques,” Information & Software Technology, Vol. 50, Issue 6, pp. 534–546, 2008.
[8] S. Yoo and M. Harman, “Regression testing minimization, selection and prioritization: A survey,” Software Testing, Verification & Reliability, Vol. 22, Issue 2, pp. 67–120, 2012.
[9] M. J. Harrold, R. Gupta, and M. L. Soffa, “A Methodology for Controlling the Size of a Test Suite,” ACM Transactions on Software Engineering & Methodology, Vol. 2, Issue 3, pp. 270–285, 1993.
[10] H. Y. Hsu and A. Orso, “MINTS: A General Framework and Tool for Supporting Test-Suite Minimization,” Proc. 31st and ACM SIGSOFT Int’l Conf. Software Engineering, pp. 419–429, 2009.
[11] D. Jeffrey and N. Gupta, “Test Suite Reduction with Selective Redundancy,” Proc. IEEE Int’l Conf. Software Maintenance, pp. 549–558, 2005.
[12] J. W. Lin and C. Y. Huang, “Analysis of Test Suite Reduction with Enhanced Tie-Breaking Techniques,” Inforfaultmation & Software Technology, Vol. 51, Issue 11, pp. 679–690, 2008.
[13] W. Masri and M. El-Ghali, “Test Case Filtering and Prioritization Based on Coverage of Combinations of Program Elements,” Proc. 7th Int’l Workshop Dynamic Analysis, pp. 29–34, 2009.
[14] C. T. Lin, K. W. Tang, and G. M. Kapfhammer, “Test Suite Reduction Methods that Decrease Regression Testing Costs by Identifying Irreplaceable Tests,” Information & Software Technology, Vol. 56, Issue 10, pp. 1322–1344, 2014.
[15] H. K. N. Leung and L. J. White, “Insights into Regression Testing,” Proc. Int’l Conf. Software Maintenance, pp. 60–69, 1989.
[16] J. Black, E. Melachrinoudis, and D. Kaeli, “Bi-criteria models for all-uses test suite reduction,” Proc. 26th Int’l Conf. Software Engineering, pp. 106–115, 2004.
[17] G. Rothermel, M. J. Harrold, J. von Ronne and C. Hong, “Empirical studies of test suite reduction,” Software Testing, Verification & Reliability, Vol. 12, Issue 4, pp. 219–249, 2002.
[18] 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,” Proc. 14th Int’l Conf. Software Maintenance, pp. 34–43, 1998.
[19] 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, Issue 2, pp. 108–123, 2007.
[20] S. Sampath and R.C. Bryce, “Improving the Effectiveness of Test Suite Reduction for User-Session-Based Testing of Web Applications,” Information & Software Technology, Vol. 54, Issue 7, pp. 724–738, 2012.
[21] M. Hutchins, H. Foster, T. Goradia, and T. Ostrand, “Experiments on the effectiveness of dataflow- and controlflow-based test adequacy criteria,” Proc. 16th Int’l Conf. Software Engineering, pp. 191–200, 1994.
[22] G. Rothermel, R. H. Untch, C. Chu, and M. J. Harrold, “Prioritizing test cases for regression testing,” IEEE Transactions on Software Engineering, Vol. 27, Issue 10, pp. 929–948, 2001.
[23] C. J. Hsu and C. Y. Huang, “Optimal Weighted Combinational Models for Software Reliability Estimation and Analysis,” IEEE Transactions on Reliability, Vol. 63, Issue 3, pp. 731–749, Sep. 2014.
[24] C. T. Lin, K. W. Tang, C. D. Chen, and G. M. Kapfhammer, “Reducing the cost of regression testing by identifying irreplaceable test cases,” Proc. 6th Int’l Conf. Genetic and Evolutionary Computing, pp. 257–260, Aug. 2012.
[25] R. M. Karp. Reducibility among Combinatorial Problems, Complexity of Computer Computations, Plenum Press, pp. 85–103, 1972.
[26] V. Chvatal, “A Greedy heuristic for the set-covering problem,” Mathematics of Operations Research, Vol. 4, Issue 3, pp. 233–235, 1979.
[27] H. Zhong, L. Zhang, and H. Mei, “An experimental comparison of four test suite reduction techniques,” Proc. 28th ACM/IEEE Int’l Conf. Software Engineering, pp. 636–640, 2006.
[28] T. Y. Chen and M. F. Lau, “A new heuristic for test suite reduction,” Information & Software Technology, Vol. 40, Issue 5–6, pp. 347–354, 1998.
[29] T. Y. Chen and M. F. Lau, “A simulation study on some heuristics for test suite reduction,” Information & Software Technology, Vol. 40, Issue 13, pp 777–787, 1998.
[30] W. E. Wong, J. R. Horgan, S. London, and A. P. Mathur, “Effect of Test Set Minimization on Fault Detection Effectiveness,” Software: Practice and Experience, Vol. 28, Issue 4, pp. 347–369, 1998.
[31] S. Yoo and M. Harman, “Using hybrid algorithm for Pareto efficient multi-objective test suite minimization,” Journal of Systems and Software, Vol. 83, Issue 4, pp 689–701, 2010.
[32] A. Panichella and M. Di Penta, “Improving multi-objective test case selection by injecting diversity in genetic algorithms,” IEEE Transactions on Software Engineering, Vol. 41, Issue 4, pp. 358–383, 2015.
[33] Y. C. Huang, C. Y. Huang, J. R. Chang, and T. Y. Chen, “Design and Analysis of Cost-Cognizant Test Case Prioritization Using Genetic Algorithm with Test History,” Proc. 34th IEEE Ann. Conf. Computer Software and Applications, pp. 413–418, Jul. 2010.
[34] K. R. Walcott, M. L. Soffa, G. M. Kapfhammer, and R. Roos, “Time-Aware Test Suite Prioritization,” Proc. Int’l Symp. Software Testing and Analysis, pp. 1–12, Jul. 2006.
[35] N. Mansour and K. El-Fakih, “Simulated annealing and genetic algorithms for optimal regression testing,” Journal of Software Maintenance, Vol. 11, Issue 1, pp. 19–34, 1999.
[36] H. Williams. Model Building in Mathematical Programming, 3rd edition, John Wiley, New York, 1993.
[37] H. Zhu, “A formal analysis of the subsume relation between software test adequacy criteria,” IEEE Transactions on Software Engineering, Vol. 22, Issue 4, pp. 248–255, 1996.
[38] W. E. Howden, “Reliability of the Path Analysis Testing Strategy,” IEEE Transactions on Software Engineering, SE–2, Jul. 1976.
[39] J. C. Huang, “An Approach to Program Testing,” ACM Computing Surveys, Vol. 7, Issue 3, pp. 113–128, Sep. 1975.
[40] H. Schiller. Using MEMIMAP to measure the extent of program testing, IBM Systems Development Division, Poughkeepsie, New York, Feb. 1969.
[41] P. G. Frankl, S. N. Weiss, and E. J. Weyuker, “ASSET: A System to Select and Evaluate Tests,” Proc. Conf. Software Tools, Apr. 1985.
[42] J. R. Horgan and S. London, “Data Flow Coverage and the C Language,” Proc. 14th Symp. Testing, Analysis, and Verification, pp. 87–97, 1991.
[43] J. Laski, “Data Flow Testing in STAD,” Journal of Systems and Software, Vol 12, Issue 1, pp 3–14, 1990.
[44] T. J. Ostrand and E. J. Weyuker, “Data Flow-Based Adequacy Analysis for Languages with Pointers,” Proc. 4th ACM Symp. Testing, Analysis, and Verification, pp 74–86, 1991.
[45] H. A. Taboada, J. F. Espiritu, and D. W. Coit, “MOMS-GA: A multi-objective multi-state genetic algorithm for system reliability optimization design problems,” IEEE Transactions on Reliability, Vol. 57, Issue 1, pp. 182–191, Mar. 2008.
[46] C. Y. Huang, M. R. Lyu, and S. Y. Kuo, “A Unified scheme of some nonhomogenous poisson process models for software reliability estimation,” IEEE Transactions on Software Engineering, Vol. 29, Issue 3, pp. 261–269, Mar. 2003.
[47] P. S. Bullen. Handbook of Means and Their Inequalities, 2nd edition, Kluwer Academic Publishers, New York, 2003.
[48] http://sir.unl.edu/portal/, Software-artifact Infrastructure Repository, 2008. Accessed on 20 Jun. 2015.
[49] J. A. Jones and M. J. Harrold, “Test-suite reduction and prioritization for modified condition/decision coverage,” IEEE Transactions on Software Engineering, Vol 29, Issue 3, pp 195–209, 2003.
[50] B. Jiang, K. Zhai, W. K. Chan, T. H. Tse, and Z. Zhang, “On the adoption of MC/DC and control-flow adequacy for a tight integration of program testing and statistical fault localization,” Information & Software Technology, Vol. 55, Issue 5, pp. 897–917, May 2013.
[51] J. von Ronne. Test Suite Minimization: An Empirical Investigation, University Honors College Thesis, Oregon State University, Corvallis, USA, 1999.
[52] S. J. Huang and N. H. Chiu, “Optimization of analogy weights by genetic algorithm for software effort estimation,” Information & Software Technology, Vol. 48, Issue 11, pp. 1034–1045, Nov. 2006.
[53] H. Y. Jiang, C. K. Chang, D. Zhu, and S. Cheng, “A Foundational study on the applicability of genetic algorithm to software engineering problems,” Proc. IEEE Congress Evol. Comput. (CEC 2007), pp. 2210–2219, Sep. 2007.
[54] D. E. Goldberg. Genetic Algorithms in Search, Optimization and Machine Learning, Addison-Wesley, New York, USA, 1989.
[55] J. Clarke, J. J. Dolado, M. Harman, R. Hierons, B. Jones, M. Lumkin, B. Mitchell, S. Mancoridis, K. Rees, M. Roper, and M. Shepperd, “Reformulating software engineering as a search problem,” Proc. IEEE Software, Vol. 150, Issue 3, pp. 161–175, Jun. 2003.
[56] M. Mitchell. An Introduction to Genetic Algorithms, The MIT Press, Cambridge, MA, USA, 1998.
[57] X. Y. Ma, Z. F. He, B. K. Sheng, and C. Q. Ye, “A genetic algorithm for test-suite reduction,” Proc. Int’l Conf. Systems, Man and Cybernetics, pp. 133–139, Oct. 2005.
[58] A. M. Smith and G. M. Kapfhammer, “An empirical study of incorporating cost into test suite reduction and prioritization,” Proc. 24th ACM Symp. Applied Computing, pp. 461–467, Mar. 2009.
[59] F. I. Vokolos and P.G. Frankl, “Empirical evaluation of the textual differencing regression testing technique,” Proc. 14th Int’l Conf. Software Maintenance, pp. 44–53, 1998.
[60] G. Keller and B. Warrack. Statistics for Management and Economics, Thomson, 2003.
[61] A. Arcuri and L. Briand, “A practical guide for using statistical tests to assess randomized algorithms in software engineering,” Proc. 33rd ACM/IEEE Int’l Conf. Software Engineering, pp. 1–10, May 2011.
[62] S. Kpodjedo, F. Ricca, G. Antoniol and P. Galinier, “Evolution and search based metrics to improve defects prediction,” Proc. 1st Int’l Symp. Search Based Software Engineering, pp. 23–32, May 2009.
[63] J. Ferrer, P. M. Kruse, F. Chicano and E. Alba, “Search based algorithms for test sequence generation in functional testing,” Information & Software Technology, Vol 58, pp. 419–432, Feb. 2015.
[64] W. Afzal, R. Torkar, and R. Feldt, “A systematic review of search-based testing for non-functional system properties,” Information & Software Technology, Vol. 51, Issue 6, pp. 957–976, Jun. 2009.
[65] M. Harman and B. F. Jones, “Search-Based Software Engineering,” Information & Software Technology, Vol. 43, pp. 833–839, 2001.
[66] S. Rapps and E. J. Weyuker, “Data flow analysis techniques for program test data selection,” Proc. 6th Int. Conf. Software Engineering, pp. 272–278, Sep. 1982.
[67] S. Sampath, S. Sprenkle, E. Gibson, and L. Pollock, “Integrating Customized Test Requirements with Traditional Requirements in Web Application Testing,” Proc. Workshop Testing, Analysis, & Verification of Web Services & Applications, pp. 23–32, 2006.
[68] G. J. Myers. The Art of Software Testing, 2nd edition, Wiley, 2004.