臺灣博碩士論文加值系統

軟體開發與維護其中一個重要項目為測試，隨著軟體功能的增加與版本的更新，測試個案數量也會隨之增加，雖然測試自動化已經大量減少了開發時的人力成本，測試個案若要全部執行完成仍會花費過多時間，軟體開發的進度因而延後。為了縮短測試進行的時間，且在不減少測試效益的前提下，測試團隊必須從測試套件中選擇適當測試個案來執行，此研究議題稱為測試套件精簡(Test Suite Reduction)，在軟體工程中為重要議題。雖然測試套件精簡可以減少軟體測試的時間，但是此過程也會花費時間。隨著平行運算與雲端運算的流行，其中通用計算圖形處理器(General-purpose Computing on Graphics Processing Units，簡稱GPU)可同時執行多個執行緒，在平行化處理大量資料有顯著的效果。因此，本論文將在GPU平行運算的條件下重新架構與組合現有演算法，利用GPU的運算能力來縮短測試套件精簡的時間，從而減少軟體開發的時間。

Testing is important to software development and maintenance. With the version evolves and increase software functionality of software, the number of test cases will also increase. If software developers adopt test automation, the costs of development and maintenance will significantly decrease. Running all of test cases will take too much time and the progress of software development will be delayed. In order to short the test time and without reduce the test benefit. The test team must select the appropriate test case from the test suite to run. This research is called Test Suite Reduction and it is an important issue in software engineering. Yet, reducing the test suite is a time-consuming process. Performing test suite reduction is also an extra cost of regression testing. With the popularity of parallel computing and cloud computing, General-purpose Computing on Graphics Processing Units (GPUs) can execute multiple threads simultaneously. GPU has significant effect on parallel processing large amounts of data. Thus, this paper aims to reconstruct and combine test suite reduction method using GPUs. We can shorten the time of software development by reducing the time for test suite reduction using the GPU.

摘要 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.