臺灣博碩士論文加值系統

軟體測試是軟體系統開發過程中重要且耗費成本的一個程序，即使並沒有增加任何的系統功能，卻經常是要耗費50%以上的整體成本，而產生測試資料以找出程式錯誤更是其中重要而且費時費力的一個項目。如果測試資料可以有效的自動產生，除了可以節省人力經費之外，更可以提昇軟體的正確性。已有學者針對測試資料的產生提出一些自動化的方法，來節省人力經費並提昇軟體的正確性。這些方法主要是把軟體測試的問題轉換成測試資料的搜尋問題，再以泛導式搜尋法為基礎來找尋會讓程式發生錯誤的測試資料。軟體的複雜性以及多變性使得這樣的軟體自動測試方法仍然比一般利用泛導式搜尋法解決的搜尋問題複雜以及困難許多。而目前這些被提出的法只提供了一個基礎的架構，對於如何依照軟體特性來更有效率的找到測試資料並沒有提出適當的方法。
本論文主要是延伸目前軟體自動測試方法的架構，以Tabu搜尋法為基礎，依據軟體的特性來設計適當的策略，以更有效提昇軟體自動測試的效率。本論文提出的策略主要包括：利用成本值來決定下次移動距離、利用距離移動效用來決定下次移動距離、成本值平原狀態的解決策略與變數交差變化等。並利用這些策略的組合來有效提昇整體的執行效率。而透過實驗的結果發現，這些策略對於軟體錯誤找尋的效率提昇有很顯著的效果。

Software testing is an expensive process, typically consuming at least 50 percent of the total costs involved in developing software, while adding nothing to the functionality of the product. One of the major costs in a software project is the construction of test-data. If test-data can effectively construction, it can reduce the software development cost. Many techniques for automated test data construction have been developed. Their main idea is transforming the software testing problem into a test data searching problem, and then employing meta-heuristic algorithms to find out target test data effectively. As the complexity and variety of software, the new search problem is more complex and harder than other searching problems employing meta-heuristic algorithms. Most current methods propose only a basic structure for automatic software testing, they does not discuss how to making use of special properties of software to effectively guiding the searching process.
The thesis develops a method that extends currently proposed automatic software testing methods. The method employs Tabu search as basis and proposes some strategies based on software properties to improve the effectiveness of automatic test data generation. The strategies proposed include: calculating next move using current cost, calculating next move using distance effectiveness, a strategy for solving cost plateau, and input variable selection. Many combinations of these strategies are also experimented to improve flaw-finding efficiency.

授權書 I
中文摘要 II
英文摘要 III
誌謝 IV
表目錄 VII
圖目錄 VIII
第一章 緒論 1
第一節 研究背景與動機 1
第二節 研究目的 5
第三節 論文架構 7
第二章 文獻探討 8
第一節 軟體測試的方法 8
第二節 測試資料的産生方式 12
第三節 泛導引式(Meta-Heuristic)搜尋法 15
2.3.1塔布搜尋法(Tabu Search) 15
2.3.2模擬退火演算法(Simulated Annealinig algorithm,SA) 19
2.2.3 基因演算法 20
2.3.4螞蟻族群最佳化(Ant Colony Optimization) 24
第四節 泛導引式搜尋法在自動化軟體測試上的應用方式 27
第三章 研究方法與架構 34
第一節 研究步驟 34
3.1.1文獻搜集與整理 34
3.1.2提出研究架構 34
3.1.3研究處理階段 36
3.1.4研究結論 36
第二節 研究架構 37
第四章 結合策略性方法之Tabu演算法設計 39
第一節 使用Tabu搜尋法建構測試系統 39
第二節 利用成本值決定下次的移動距離 43
第三節 利用距離移動的效用來決定下次移動距離 47
第四節 成本值平原狀態的解決策略 51
第五節 不同變數交差變化時的考量 55
第五章 策略與策略組合之實驗與分析 57
第一節 實驗步驟 57
第二節 程式描述 59
5.2.1受測程式Tomorrow 程式說明 59
5.2.2受測程式Triangle_Type 程式說明 62
5.2.3受測程式RectOverLine 程式說明 64
第三節 策略與策略組合之實驗 67
第四節 使用Tabu搜尋法之實驗 73
第五節 考量不同成本值變化策略之實驗 77
第六節 部份距離移動效用之實驗 82
第六章 結論 87
第一節 研究結論與研究貢獻 87
第二節 未來發展方向 89
參考文獻 90
中文部分 90
英文部分 90
附錄 94

中文部分
[張明洲00] 張明洲，「基因演算法在物流中心品項儲位指派問題之應用」，國立灣科技大學工業管理研究所碩士論文，2000。
[微軟01] http://www.microsoft.com/taiwan/press/2001/1005.htm
英文部分
[softwareqatest00] http://www.softwareqatest.com/TOP
[Glover89] F. Glover, “Tabu search — Part I,”ORSA J. Comput., Vol1, pp.190-206, 1989.
[Jornsten97] K. Jornsten and A. Lokketangen, “Tabu search for weighted k-cardinality trees,”Asia-Pacific Journal of Operating Research, Vol.14, No.2, pp.9-26, 1997.
[Skorin-Kapov90] J. Skorin-Kapov, “Tabu search applied to the quadratic assignment problem,”ORSA Journal on Computing, Vol.2, No.1, pp.33-45, 1990.
[Widmer91] M. Widmer, “The job-shop scheduling with tooling constraints: a tabu search approach,”Journal of Operating Research, Vol.42, pp.75-82, 1991.
[Glover 97] F. Glover and Manuel Laguna, ”TABU SEARCH” p25-p26, 1997.
[Kirkpatrick83] Kirkpatrick,S., Gelatt jr. C. D., and M. P. Vecchi, ”Optimization by simulated annealing,”Science Vol.220 , p671-p680, 1983.
[Metropolis53] Metropolis, N., Rosenbluth, A. rosenbluth, M., Teller A. and Teller, E., “Equation of State Calculations by Fast Computing MachInes” Jurnal of Chem . Physics, Vol. 21, p1087-p1092, 1953.
[Kirkpatrick82] Kirkpatrick, S., Gelatt Jr., C.D. and Vecchi, M.P., “Optimization by simulated Annealing,” IBM Research Report RC9355, 1982.
[Kirkpatrick84] Kirkpatrick, S., “Optimization by Simulated Annealing: Quantitative Studies,” Journal of Statis. Phys., vol. 34, p975-p986, 1984.
[Kirkpatrick83] Kirkpatrick, S., Gelatt Jr., C.D. and Vecchi, M.P., “Optimization by Simulated Annealing,”Science, Vol. 220, No. 4598, p671-p680,1983.
[Goldberg89] Goldberg D.E., “Genetic Algorithms In Search, Optimization and Machine Learning,” Addison-Wesley, Reading, MA, 1989.
[Kenji95] Kenji,Y. and Osamu, I. “NewEvolutionary Direction Operator for GeneticAlgorithms,” AiAA Journal , Vol.33, No.10, 1995.
[Dorigo99] Dorigo, M. and Gambardell, L.M., “Ant Colonies for the Traveling Salesman Problem” BioSystems, vol. 43, p73-p81, 1999.
[Maniezzo 97] Maniezzo, V. and Colorni, A., “The Ant System Applied to the Quadratic Assignment Problem,”IEEE Transactions on Knowledge and Data Engineering,1999.
[Dorigo 97] Marco Dorigo, Luca Maria Gambardella “Ant Colony System:A Cooperative Learning Approach to the Traveling Salesman Problem,”IEEE Transactions on Evolutionary Computation,1997.
[Li98] Li E. Y., “software Testing In A system Development Process：A Life Cycle Perspective,”Journal of Systems Management, Aug 1990.
[Patton 00] R. Patton, “Software Testing,”Sams, 2000.
[Sommerville00] I. Sommerville, “Software Engineering,” 6th edition, Addison-Wesley, 2000.
[Tracey98] N. Tracey, J. Clark, and K. Mander, “Automated program flaw finding using simulated annealing,” Proceedings of ACM SIGSOFT international symposium on Software testing and analysis, p73-p81, 1998.
[Barnes97] J. Barnes, “High Integrity Ada: The SPARK Approach, Addison-Wesley,” 1997.
[Chu95 ] Huey-Der Chu “An Evaluation Scheme of Software Testing Techniques,” 1995.
[VLIET94] VLIET,H.“Software engineering : principles and practice,”John Wiley &Sons,1994.
[King76] J. King, “Symbolic execution and program testing,” Comm. Of ACM, Vol.19, No.7, p385-p394, 1976.
[Clarke76] L. Clarke, “A system to generate test data and symbolically execute programs,” IEEE Trans. on Software Engineering, pp.215-222, 1976.
[DeMilo87] Richard A. DeMillo,W.Michael McCracken,R.J.Martin,John F. Passafiume “Software Testing and Evaluation,”The Benjamin/Cummings Publishing Company,1987.
[Tracey00] N. Tracey, J. Clark , K. Mander and J. McDermid, “Automated test-data generation for exception conditions,”SOFTWARE-PRACTICE AND EXPERIENCE 2000.
[Tracey01] Nigel Tracey , John clark Keith Mander , John McDermid,”An Automated Framework for Structural Test-Data Generation,”2001.
[Miller76] Miller W, Spooner.D. “Automatic generation of floating-point test data,” IEEE Transactions on Software Engineering, 1976.
[Korel96] Korel B. “Automated test data generation for programs with procedures,” International Symposium on software Testing and Analysis:ACM/SIGSOFT, 1996.
[Jones96-1] B. Jones, H. Sthamer, and D. Eyres. “Automatic structural testing using genetic algorithms”, Software Engineering Journal11(5), p299-p306, 1996.
[Jones96-2] B. F. Jones, H. H. Sthamer, and D. E. Eyres. “Generating test-date for Ada procedures using gentic algorithms. In Genetic Algorithms in Engineering System,”Innovations and Applications, p65-p70, September 1995.
[Tracey98] N. Tracey, J. Clark, and K. Mander, “Automated program flaw finding using simulated annealing,” Proceedings of ACM SIGSOFT international symposium on Software testing and analysis, p73-p81, 1998.
[Beizer90] B. Beizer, “Software Testing Techniques,” Thomson Computer Press, 2nd edition, 1990.
[Wegener01] Joachim Wegener ,“Overview of Evolutionary Testing,” IEEE Seminal Workshop, 14 May 2001.
[Marick99] Brian Marick, “New Models for Test Development,” Quality Week 1999.
[Whittaker00] James A. Whittaker,”What Is Software Testing? And Why Is It So Hard?”IEEE SOFTWARE January/February, 2000.
[Meudec97] Christophe Meudec，”Automatic Generation of Software Tests From Formal Specifications,”A Thesis for the Degree of Doctor of Philosophy in the Faculty of Science of The Queen’s University of Belfast.