摘要 i
Abstract ii
目錄 iv
表目錄 viii
圖目錄 ix
第1章 前言 1
第2章 背景與相關研究 4
2.1 測試套件精簡 4
2.2 基於啟發式演算法測試套件精簡 5
2.2.1 基於貪婪演算法測試套件精簡 6
2.2.2 基於比例度量法測試套件精簡 8
2.2.3 基於效率度量法測試套件精簡 10
2.3 基於基因演算法測試套件精簡 12
2.3.1 使用貪婪法作為基因演算法的適應度函式 20
2.3.2 使用比例演算法作為基因演算法的適應度函式 21
2.3.3 使用效率度量演算法作為基因演算法的適應度函式 22
2.4 基於交替變量法測試套件精簡 24
2.4.1 使用貪婪法作為交替變量法的目標函式 27
2.4.2 使用比例法作為交替變量法的目標函式 28
2.4.3 使用效率度量法作為交替變量法的目標函式 29
第3章 研究方法 30
3.1 研究方法說明 30
3.2 以GPU加速啟發式測試套件精簡 31
3.2.1 以GPU加速貪婪演算法測試套件精簡 33
3.2.2 以GPU加速比例度量演算法測試套件精簡 34
3.2.3 以GPU加速效率度量演算法測試套件精簡 35
3.3 以GPU加速基因演算法測試套件精簡 37
3.3.1 以GPU加速基因(貪婪演算法作為適應度函式)測試套件精簡 37
3.3.2 以GPU加速基因(比例演算法作為適應度函式)測試套件精簡 39
3.3.3 以GPU加速基因(效率演算法作為適應度函式)測試套件精簡 42
3.4 以GPU加速交替變量法測試套件精簡 46
3.4.1 以GPU加速AVM(貪婪演算法作為目標函式)測試套件精簡 47
3.4.2 以GPU加速AVM(比例演算法作為目標函式)測試套件精簡 48
3.4.3 以GPU加速AVM(效率演算法作為目標函式)測試套件精簡 49
第4章 實驗與分析 52
4.1 實驗設計 52
4.1.1 實驗環境與受測程式 52
4.1.2 實驗步驟 53
4.1.3 評估指標 54
4.1.4 實驗探討議題 54
4.2 實驗結果與討論 56
4.2.1 啟發式演算法討論 56
4.2.2 基因演算法討論 63
4.2.3 AVM演算法討論 68
4.2.4 實驗討論總結 71
4.2.5 實驗討論問題總結 73
4.3 實驗有效性威脅 74
第5章 結論與未來研究 75
第6章 參考文獻 77

[1] C. T. Lin, K. W. Tang, and G. M. Kapfhammer, “Test Suite Reduction Methods that Decrease Regression Testing Costs by Identifying Irreplaceable Tests,” Information and Software Technology, Vol. 56, No. 10, pp. 1322-1344, October 2014.
[2] D. Binkley, “Semantics Guided Regression Test Cost Reduction,” IEEE Trans. on Software Engineering, Vol. 23, No. 8, pp. 498-516, August 1997.
[3] A. Leitner, M. Oriol, A. Zeller, I. Ciupa and B. Meyer, “Efficient Unit Test Case Minimization,” Proceedings of the Twenty-Second IEEE/ACM International Conference on Automated Software Engineering, pp. 417-420, November 2007.
[4] M. Prasanna, S. N. Sivanandam, R. Venkatesan and R. Sundarrajan, “A Survey on Automatic Test Case Generation,” Academic Open Internet Journal,Vol. 15, 2005.
[5] “Continuous Integration (CI),” Available at: http://www.dotblogs.com.tw/ hatelove/archive/2011/12/25/introducing-continuous-integration.aspx, Access date: 2015/01/22.
[6] Y. Yu, J. Jones and M. J. Harrold,” An Empirical Study of the Effects of Test-Suite Reduction on Fault Localization,” Proceedings of the 30th International Conference on Software Engineering, pp. 201-210, 2008.
[7] 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, No. 3, pp.248-263, March 2001.
[8] G. Rothermel and M. J. Harrold, “Analyzing Regression Test Selection Techniques,” IEEE Transactions on Software Engineering, Vol. 22, No. 8, pp. 529-551, August 1996.
[9] R. Abreu, P. Zoeteweij, R. Golsteijn and A. J. C. van Gemund, “A Practical Evaluation of Spectrum-Based Fault Localization,” Journal of Systems and Software, Vol. 82, No. 11, pp. 1780-1792, November 2009.
[10] J. Offutt, J. Pan and J. M. Voas, “Procedures for Reducing the Size of Coverage-Based Test Sets,” Proceedings of the International Conference on Testing Computer Software, pp. 111-123, June 1995.
[11] 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,No 2, pp. 108-123, February 2007.
[12] S. Elbaum, A. G. Malishevsky and G. Rothermel, “Test Case Prioritization: A Family of Empirical Studies,” IEEE Transaction on Software Engineering, Vol. 28, No. 22, pp. 159-182, February 2002.
[13] G. Rothermel, R. H. Untch, C. Chu and M. J. Harrold, “Prioritizing Test Cases for Regression Testing,” IEEE Transaction on Software Engineering, Vol. 27, No. 10, pp. 929-948, October 2001.
[14] “CPU vs GPU,” Available at: https://www.cs.uaf. edu/2007/fall/cs441/proj1note
s/favier/, Access date: 2016/01/14.
[15] S. Yoo, M. Harman and S. Ur, “GPGPU Test Suite Minimisation: Search Based Software Engineering Performance Improvement Using Graphics Cards,” Journal of Empirical Software Engineering, Vol. 18, pp. 550-593, June 2013.
[16] M. J. Harrold, R. Gupta, and M. L. Soffa, “A Methodology for Controlling the Size of a Test Suite,” ACM Trans. on Software Engineering and Methodology, Vol. 2, No. 3, pp. 270-285, July 1993.
[17] J. W. Lin and C. Y. Huang, “Analysis of Test Suite Reduction with Enhanced Tie-Breaking Techniques,” Information and Software Technology, Vol. 51,No 4, pp. 679-690, April 2009.
[18] V. Chvatal, “A Greedy Heuristic for the Set-Covering Problem,” Mathematics of Operations Research, Vol. 4, No 3, pp. 233-235, August 1979.
[19] T. Y. Chen and M. F. Lau, “A New Heuristic for Test Suite Reduction,” Information and Software Technology, Vol. 40, No. 5-6, pp. 347-354, July 1998.
[20] S. Yoo and M. Harman, Regression Testing Minimisation, Selection and Prioritisation, TR-09-09, Technical Report, King’s College London, October 2009.
[21] T. Mücke and M. Huhn, “Minimizing Test Execution Time during Test Generation,” International Federation for Information Processing, Vol. 227, pp. 223-235, 2007.
[22] A. M. Smith and G. M. Kapfhammer, “An Empirical Study of Incorporating Cost into Test Suite Reduction and Prioritization,” Proceedings of the 24th ACM SIGAPP Symposium on Applied Computing, Software Engineering Track, pp. 461-467, Honolulu, USA, March 2009.
[23] J. A. Jones and M. J. Harrold, “Test-Suite Reduction and Prioritization for Modified Condition/Decision Coverage,” IEEE Trans. on Software Engineering, Vol. 29 No. 3, pp. 195-209, March 2003.
[24] B.F. Jones, D.E. Eyres and H.-H. Sthamer, “Automatic Structural Testing Using Genetic Algorithms,” The Institution of Electrical Engineers, Vol. 11, pp. 299-306, September 1996.
[25] R. P. Pargas, M. J. Harrold and R. R. Peck, “Test‐Data Generation Using Genetic Algorithms,” Software Testing, Verification, & Reliability, Vol. 9, pp. 263-282, December 1999.
[26] R. M. Karp, “Reducibility among Combinatorial Problems,” Complexity of Computer Computations, Plenum Press, pp. 85-103, 1972.
[27] N. Mansour and K. El-Fakih, “Simulated Annealing and Genetic Algorithms for Optimal Regression Testing,” Journal of Software Maintenance, Vol. 11, No. 1, pp. 19-34, January 1999.
[28] X. Ma, B. Sheng and C. Ye, “Test-Suite Reduction Using Genetic Algorithm,” Proceedings of the 6th International Conference on Advanced Parallel Processing Technologies, pp. 253-262, October 2005.
[29] S. Yoo and M. Harman, “Using Hybrid Algorithm for Pareto Efficient Multi-Objective Test Suite Minimisation,” Journal of Systems and Software, Vol. 83, pp. 689-701, April 2010.
[30] H. Zhong, L. Zhang and H. Mei, “An Experimental Comparison of Four Test Suite Reduction Techniques,” Proceedings of the 28th International Conference on Software Engineering, pp. 636-640, May 2006, Shanghai, China.
[31] P. McMinn, and G. M. Kapfhammer, “AVMf: An Open-Source Framework and Implementation of the Alternating Variable Method,” International Symposium on Search-Based Software Engineering, Lecture Notes in Computer Science, Vol. 9962, pp. 259–266, 2016.
[32] P. McMinn, C. J. Wright, and G. M. Kapfhammer. “The Effectiveness of Test Coverage Criteria for Relational Database Schema Integrity Constraints,” ACM Transactions on Software Engineering and Methodology, Vol. 25, no. 1, pp. 8:1–8:49, 2015.
[33] M. Harman, and P. McMinn. “A Theoretical and Empirical Study of Search Based Testing: Local, Global and Hybrid Search,” IEEE Transactions on Software Engineering, Vol. 36, no. 2, pp. 226–247, 2010.
[34] J. Kempka, P. McMinn and D. Sudholt. “Design and Analysis of Different Alternating Variable Searches for Search-Based Software Testing,” Theoretical Computer Science, Vol. 605, pp. 1–20, 2015.
[35] “Freely Available for Use under the MIT Licence” Available at: http://avmframework.org/, Access date: 2019/05/22.
[36] “Software-artifact Infrastructure Repository (SIR),” Available at: http://sir.unl.edu/portal, Access date: 2016/03/28.
[37] “The Green500 List News And Submitted Items”, Available at: http://www.green500.org/, Access date: 2014/12/05.
[38] S. M. Teng, Auto-Tuning for GPGPU Applications Using Performance and Energy Model, Master Thesis, National Chung Cheng University, June 2013.
[39] S. W. Thomas, H. Hemmati, A. E. Hassan and D. Blostein, “Static Test Case Prioritization Using Topic Models,” Journal of Empirical Software Engineering, Vol. 19, pp. 182-212, February 2014.
[40] S. Mirarab, S. Akhlaghi and L. Tahvildari, “Size-Constrained Regression Test Case Selection Using Multicriteria Optimization,” IEEE Transactions on Software Engineering, Vol. 38, No. 4, pp.936-956, July 2012.
[41] X. Zhao, Z. Wang and X. Fan, “A Clustering – Bayesian Network Based Approach for Test Case Prioritization,” Proceedings of the 39th IEEE Annual International Computers, Software & Applications Conference, pp. 542-547, July 2015.
[42] C. Zhang, A. Groce and M. A. Alipour, “Using Test Case Reduction and Prioritization to Improve Symbolic Execution,” Proceedings of the 2014 International Symposium on Software Testing and Analysisa, pp. 160-170, July 2014.
[43] F. C. Ferrari, J. C. Maldonado and A. Rashid, “Mutation Testing for Aspect-Oriented Programs,” Proceedings of the 2008 International Conference on Software Testing, Verification, and Validation, pp. 52-61, April 2008.