臺灣博碩士論文加值系統

軟體產品在發佈前需經過白箱測試及黑箱測試兩個階段的測試，盡可能在不同的執行情況下，找出可能潛在的錯誤或缺陷，提升軟體品質，因此需不斷執行迴歸測試，然而迴歸測試是一個昂貴耗時的測試程序，需不斷地執行測試案例，在時間、成本以及人力…等限制下，如何有效地執行迴歸測試便成為一個重要議題，其中，測試案例優先順序技術是一個常見的技術，透過將測試案例進行排序，期望能達到所設定的測試效力。
過去文獻探討之排序因子多為成本、需求、錯誤個數、嚴重度…等考量，尚未考慮相互依賴性。有別於過去探討的測試案例優先順序問題，本研究提出黑箱測試環境下測試案例的優先順序排序技術，以嚴重度（Severity）、複雜度（Complexity）以及相互依賴性（Inter-dependency）三項因子做為排序的考量，運用蟻群最佳化演算法，結合最大部分排序法及隨意插入法（MPO/AI）兩者，使產生的測試案例優先順序具有先後限制，而並非只是一組測試案例執行順序的組合解。
本研究將提出之方法與其他求解排序問題的方法進行比較，實驗結果指出，本研究提出之方法在於求解SOP問題，產生之結果近似於其他演算法，而執行時間相較於其他演算法有明顯縮短，此外，在於求解TCP問題時，本研究求得的測試案例優先順序解優於所比較之方法，實際運用於本研究設計之圖形使用者介面(GUI)測試，其所產生的測試效力亦優於所比較之方法，因此，由實驗結果說明，本研究考量之投入因子以及所提出之蟻群演算法結合MPO/AI的排序方法，可有效找出測試案例的優先順序。

A mature software products have to pass two testing processes before being released, white-box testing and black-box testing, as much as possible to implement testing in different scenarios, to identify potential faults and defects. In order to improve software quality, testing engineers should perform regression testing for each software release. However, regression testing is a time consuming and expensive testing procedure, required to execute numerous test cases. Due to time, cost and labor constraints, how to effectively perform regression testing has become an important issue. In such case, test case prioritization technique is one of effective technologies. Test case prioritizaiton techniques schedule test cases in an order that attempts to maximize the effectiveness in terms of meeting some performance goals.
In previous literatures, test case prioritization techniques considered prioritization factors based on costs, requirements, number of faults, faults severities, and so on; the researches have never considered the inter-dependency between test cases. Unlike past researches of the test case prioritization problem, we proposed the test case prioritization techniques based on severity, complexity and inter-dependency in black-box testing. Based ant colony optimization, and combined with the Maximum Partial Order/Arbitrary Insertion（MPO/AI）method, we generated test case execution order with precedence constraints.
In this study, the method we proposed to solve scheduling problem is compared with the other algorithms. To solve the SOP problem, experimantal results indicate that our proposed technique yields a comparable value to other algorithms, and execute time is shortened significantly. To solve the TCP problem, we obtain better result than the comparison algorithms. Using in practical application of our graphical user interface（GUI）testing, the testing effectiveness is superior to the comparison algorithms. Therefore, the experimental results show that, our proposed technique is useful to prioritizate test cases.

摘要 I
Abstract II
致謝 III
目錄 IV
圖目錄 VI
表目錄 VII
第一章 緒論 1
1.1 研究背景 1
1.2 研究動機 3
1.3 研究目的 4
1.4 研究流程 5
1.5 論文組織及架構 6
第二章 文獻探討 7
2.1測試套件最小化（Test Suite Minimization） 7
2.2選擇測試案例（Test Case Selection） 8
2.3測試案例優先順序（Test Case Prioritization） 8
2.3.1測試案例優先順序問題定義 8
2.3.2測試案例優先順序相關技術 9
2.3.3有效性測量 14
2.4 GUI測試 17
2.5序列排序問題（Sequential Ordering Problem） 18
2.5.1排序方法 19
2.6蟻群最佳化演算法 21
2.6.1搜尋原理 23
2.6.2搜尋特性 23
2.6.3蟻群最佳化演算法基本架構 24
第三章 研究方法與設計 28
3.1 測試案例優先順序問題 28
3.1.1 假設與限制 28
3.1.2 數學模式 28
3.2 功能性需求之測試案例設計 29
3.3 優先順序探討因子（Prioritization factors） 31
3.4優先順序技術（Prioritization technique） 34
3.4.1排序方法 34
3.4.2求解流程 36
3.5研究架構 40
第四章 實驗設計與討論 41
4.1測試環境 41
4.2 TerpPaint應用程式簡述 41
4.3產生測試案例 42
4.3.1使用案例 42
4.3.2軟體需求規範 45
4.3.3測試案例 46
4.4測試案例分數設計 47
4.5結果驗證 49
4.5.1 SOP問題比較結果 49
4.5.2 TCP問題比較結果 54
4.6敏感度分析 57
第五章 結論與建議 63
5.1 研究結論 63
5.2 研究貢獻 64
5.3 研究建議與未來發展 64
參考文獻 66
附錄一、軟體需求規範 70
附錄二、測試案例 73

圖1-1：軟體開發週期 1
圖2-1：置換技術與成本計算方法 13
圖2-2：GUI測試過程 17
圖2-3：MPO過程之範例 20
圖2-4：蟻群搜尋食物之路徑圖 23
圖2-5：蟻群最佳化演算法流程圖 27
圖3-1：使用案例圖之範例 30
圖3-2：測試案例產生概念 31
圖3-3：測試案例關係圖 33
圖3-4：相互依賴性矩陣 34
圖3-5：相互依賴性矩陣圖 35
圖3-6：子路徑排序圖 35
圖3-7：任意插入法（AI） 36
圖3-8：求解流程圖 39
圖3-9：研究架構圖 40
圖4-1：TerpPaint使用介面 42
圖4-2：TerpPaint5.0應用程式使用案例圖 43
圖4-3：測試案例關係圖 48
圖4-4：最佳解比較結果直方圖 52
圖4-5：執行時間比較結果直方圖 53
圖4-6：本研究與最佳解平均值比較之折線圖 54
圖4-7：本研究與執行時間平均值比較之折線圖 54
圖4-8：AppPerfect App Test軟體測試工具執行範例 55
圖4-9：以ACO+MPO/AI求得之測試案例優先順序執行之結果 56
圖4-10：以GA+MPO/AI求得之測試案例優先順序執行之結果 56
圖4-11：改變總螞蟻數（m）對最佳解之影響 57
圖4-12：改變總螞蟻數（m）對求解時間之影響 58
圖4-13：改變費洛蒙殘留係數ρ對最佳解之影響 59
圖4-14：改變費洛蒙殘留係數ρ對求解時間之影響 59
圖4-15：改變α值對最佳解之影響 60
圖4-16：改變α值對求解時間之影響 60
圖4-17：改變β值對最佳解之影響 61
圖4-18：改變β值對求解時間之影響 62

表2-1：蟻群演算法相關應用分類表 22
表3-1：使用於需求規範之優先性等級及說明 32
表4-1：圖4-2中使用案例說明 44
表4-2：軟體需求規範及其優先性等級 45
表4-3：測試案例範例 46
表4-4：ACO+MPO/AI參數設定 49
表4-5：ACO+MPO/AI、GA+MPO/AI及 HAS-SOP三種方法求解SOP問題之結果 50
表4-6：最佳解比較結果 51
表4-7：執行時間比較結果 52
表4-8：GA+MPO/AI參數設定 55
表4-9：ACO+MPO/AI及GA+MPO/AI求解TCP問題之結果比較 56
表4-10：敏感度分析之總螞蟻數（m）設定 57
表4-11：敏感度分析之費洛蒙殘留係數（ρ）設定 58
表4-12：敏感度分析之費洛蒙濃度相對重要性（α）參數設定 59
表4-13：敏感度分析之啟發式函數相對重要性（β）參數設定 61

Bennet, Simon, Steve McRobb, and Ray Farmer. 2002. Object-oriented systems analysis and design using UML. 2nd ed.London : McGraw-Hill c2002.
Chen, S., and S. F. Smith. 1996. Commonality and genetic algorithmsCiteseer.
Colorni, A., M. Dorigo, and V. Maniezzo. 1992. An investigation of some properties of an ant algorithm. Paper presented at Proceedings of the Parallel Problem Solving from Nature Conference.
Dorigo, M., and L. M. Gambardella. 1997. Ant colony system: A cooperative learning approach to the traveling salesman problem. Evolutionary Computation, IEEE Transactions 1 (1): 53-66.
Dorigo, M., V. Maniezzo, and A. Colorni. 1996. Ant system: Optimization by a colony of cooperating agents. Systems, Man, and Cybernetics, Part B: Cybernetics, IEEE Transactions 26 (1): 29-41.
Elbaum, S., A. Malishevsky, and G. Rothermel. 2001. Incorporating varying test costs and fault severities into test case prioritization. Paper presented at Proceedings of the 23rd International Conference on Software Engineering.
Elbaum, S., A. G. Malishevsky, and G. Rothermel. 2000. Prioritizing test cases for regression testing. ACM SIGSOFT Software Engineering Notes 25 (5): 102-12.
Escudero, L. F. 1988. An inexact algorithm for the sequential ordering problem. European Journal of Operational Research 37 (2): 236-49.
Gambardella, L. M., and M. Dorigo. 2000. An ant colony system hybridized with a new local search for the sequential ordering problem. INFORMS Journal on Computing 12 (3): 237-55.
Gambardella, L. M., ED Taillard, and M. Dorigo. 1999. Ant colonies for the quadratic assignment problem. Journal of the Operational Research Society 50 (2): 167-76.
Hla, K. H. S., Y. S. Choi, and J. S. Park. 2008. Applying particle swarm optimization to prioritizing test cases for embedded real time software retesting. Paper presented at Computer and Information Technology Workshops, 2008.
Huang, C. Y., J. R. Chang, and Y. H. Chang. 2010. Design and analysis of GUI test-case prioritization using weight-based methods. Journal of Systems and Software 83 (4): 646-59.
Huang, Y. C., C. Y. Huang, J. R. Chang, and T. Y. Chen. 2010. Design and analysis of cost-cognizant test case prioritization using genetic algorithm with test history. Paper presented at 2010 34th Annual IEEE Computer Software and Applications Conference.
Krishnamoorthi, R., and SA Sahaaya Arul Mary. 2009. Factor oriented requirement coverage based system test case prioritization of new and regression test cases. Information and Software Technology 51 (4): 799-808.
Last, M., S. Eyal, and A. Kandel. 2006. Effective black-box testing with genetic algorithms. Hardware and Software, Verification and Testing: 134-48.
Li, Z., M. Harman, and R. M. Hierons. 2007. Search algorithms for regression test case prioritization. IEEE Transactions on Software Engineering: 225-37.
Lima, L., J. Iyoda, and A. Sampaio. 2008. A permutation technique for test case prioritization in a black-box environment. Paper presented at 2nd Brazilian Workshop on Systematic and Automated Software Testing (SAST 2008) .
Malishevsky, A. G., J. R. Ruthruff, G. Rothermel, and S. Elbaum. 2006. Cost-cognizant test case prioritization. Department of Computer Science and Engineering, University of Nebraska-Lincoln, Techical Report.
Memon, A. M. 2001. A Comprehensive Framework for Testing Graphical User Interfaces.
Onoma, A. K., W. T. Tsai, M. Poonawala, and H. Suganuma. 1998. Regression testing in an industrial environment. Communications of the ACM 41 (5): 81-6.
Pressman, Roger S. 2010. Software engineering : A practitioner's approach. 7th ed.New York : McGraw-Hill Higher Education c2010.
Qu, B., C. Nie, B. Xu, and X. Zhang. 2007. Test case prioritization for black box testing.
Rothermel, G., and M. J. Harrold. 1997. A safe, efficient regression test selection technique. ACM Transactions on Software Engineering and Methodology (TOSEM) 6 (2): 173-210.
Rothermel, G., and M. J. Harrold. 1996. Analyzing regression test selection techniques. Software Engineering, IEEE Transactions on 22 (8): 529-51.
Rothermel, G., M. J. Harrold, J. Von Ronne, and C. Hong. 2002. Empirical studies of test‐suite reduction. Software Testing, Verification and Reliability 12 (4): 219-49.
Rothermel, G., R. H. Untch, C. Chu, and M. J. Harrold. 1999. Test case prioritization: An empirical study. Paper presented at Software Maintenance, 1999.(ICSM'99) Proceedings.
Singh, Y., A. Kaur, and B. Suri. 2010. Test case prioritization using ant colony optimization. ACM SIGSOFT Software Engineering Notes 35 (4): 1-7.
Software & Systems Engineering Standards Committee. 2008. IEEE std 829™-2008 IEEE standard for software and system test documentation. IEEE Computer Society (18 July).
Software & Systems Engineering Standards Committee. 1998. IEEE std 830-1998 IEEE Recommended Practice for Software Requirements Specifications. IEEE Computer Society (20 Oct.).

Srikanth, H., and L. Williams. 2002. Requirements-based test case prioritization. IEEE Trans.on Software Engineering 28 .
Srikanth, H., L. Williams, and J. Osborne. 2005. System test case prioritization of new and regression test cases. Paper presented at Empirical Software Engineering, 2005.
Srivastva, P. R., K. Kumar, and G. Raghurama. 2008. Test case prioritization based on requirements and risk factors. ACM SIGSOFT Software Engineering Notes 33 (4): 1-5.
U.S. Atif Memon's software engineering students. 2006. TerpOffice, http://www.cs.umd.edu/~atif/TerpOfficeWeb/TerpOfficeV5.0/index.html.(Access June,2011).
Zhang, X., C. Nie, B. Xu, and B. Qu. 2007. Test case prioritization based on varying testing requirement priorities and test case costs. Paper presented at Quality Software, 2007. QSIC'07.
參考文獻
英文部分
Bennet, Simon, Steve McRobb, and Ray Farmer. 2002. Object-oriented systems analysis and design using UML. 2nd ed.London : McGraw-Hill c2002.
Chen, S., and S. F. Smith. 1996. Commonality and genetic algorithmsCiteseer.
Colorni, A., M. Dorigo, and V. Maniezzo. 1992. An investigation of some properties of an ant algorithm. Paper presented at Proceedings of the Parallel Problem Solving from Nature Conference.
Dorigo, M., and L. M. Gambardella. 1997. Ant colony system: A cooperative learning approach to the traveling salesman problem. Evolutionary Computation, IEEE Transactions 1 (1): 53-66.
Dorigo, M., V. Maniezzo, and A. Colorni. 1996. Ant system: Optimization by a colony of cooperating agents. Systems, Man, and Cybernetics, Part B: Cybernetics, IEEE Transactions 26 (1): 29-41.
Elbaum, S., A. Malishevsky, and G. Rothermel. 2001. Incorporating varying test costs and fault severities into test case prioritization. Paper presented at Proceedings of the 23rd International Conference on Software Engineering.
Elbaum, S., A. G. Malishevsky, and G. Rothermel. 2000. Prioritizing test cases for regression testing. ACM SIGSOFT Software Engineering Notes 25 (5): 102-12.
Escudero, L. F. 1988. An inexact algorithm for the sequential ordering problem. European Journal of Operational Research 37 (2): 236-49.
Gambardella, L. M., and M. Dorigo. 2000. An ant colony system hybridized with a new local search for the sequential ordering problem. INFORMS Journal on Computing 12 (3): 237-55.
Gambardella, L. M., ED Taillard, and M. Dorigo. 1999. Ant colonies for the quadratic assignment problem. Journal of the Operational Research Society 50 (2): 167-76.
Hla, K. H. S., Y. S. Choi, and J. S. Park. 2008. Applying particle swarm optimization to prioritizing test cases for embedded real time software retesting. Paper presented at Computer and Information Technology Workshops, 2008.
Huang, C. Y., J. R. Chang, and Y. H. Chang. 2010. Design and analysis of GUI test-case prioritization using weight-based methods. Journal of Systems and Software 83 (4): 646-59.
Huang, Y. C., C. Y. Huang, J. R. Chang, and T. Y. Chen. 2010. Design and analysis of cost-cognizant test case prioritization using genetic algorithm with test history. Paper presented at 2010 34th Annual IEEE Computer Software and Applications Conference.
Krishnamoorthi, R., and SA Sahaaya Arul Mary. 2009. Factor oriented requirement coverage based system test case prioritization of new and regression test cases. Information and Software Technology 51 (4): 799-808.
Last, M., S. Eyal, and A. Kandel. 2006. Effective black-box testing with genetic algorithms. Hardware and Software, Verification and Testing: 134-48.
Li, Z., M. Harman, and R. M. Hierons. 2007. Search algorithms for regression test case prioritization. IEEE Transactions on Software Engineering: 225-37.
Lima, L., J. Iyoda, and A. Sampaio. 2008. A permutation technique for test case prioritization in a black-box environment. Paper presented at 2nd Brazilian Workshop on Systematic and Automated Software Testing (SAST 2008) .
Malishevsky, A. G., J. R. Ruthruff, G. Rothermel, and S. Elbaum. 2006. Cost-cognizant test case prioritization. Department of Computer Science and Engineering, University of Nebraska-Lincoln, Techical Report.
Memon, A. M. 2001. A Comprehensive Framework for Testing Graphical User Interfaces.
Onoma, A. K., W. T. Tsai, M. Poonawala, and H. Suganuma. 1998. Regression testing in an industrial environment. Communications of the ACM 41 (5): 81-6.
Pressman, Roger S. 2010. Software engineering : A practitioner's approach. 7th ed.New York : McGraw-Hill Higher Education c2010.
Qu, B., C. Nie, B. Xu, and X. Zhang. 2007. Test case prioritization for black box testing.
Rothermel, G., and M. J. Harrold. 1997. A safe, efficient regression test selection technique. ACM Transactions on Software Engineering and Methodology (TOSEM) 6 (2): 173-210.
Rothermel, G., and M. J. Harrold. 1996. Analyzing regression test selection techniques. Software Engineering, IEEE Transactions on 22 (8): 529-51.
Rothermel, G., M. J. Harrold, J. Von Ronne, and C. Hong. 2002. Empirical studies of test‐suite reduction. Software Testing, Verification and Reliability 12 (4): 219-49.
Rothermel, G., R. H. Untch, C. Chu, and M. J. Harrold. 1999. Test case prioritization: An empirical study. Paper presented at Software Maintenance, 1999.(ICSM'99) Proceedings.
Singh, Y., A. Kaur, and B. Suri. 2010. Test case prioritization using ant colony optimization. ACM SIGSOFT Software Engineering Notes 35 (4): 1-7.
Software & Systems Engineering Standards Committee. 2008. IEEE std 829™-2008 IEEE standard for software and system test documentation. IEEE Computer Society (18 July).
Software & Systems Engineering Standards Committee. 1998. IEEE std 830-1998 IEEE Recommended Practice for Software Requirements Specifications. IEEE Computer Society (20 Oct.).

Srikanth, H., and L. Williams. 2002. Requirements-based test case prioritization. IEEE Trans.on Software Engineering 28 .
Srikanth, H., L. Williams, and J. Osborne. 2005. System test case prioritization of new and regression test cases. Paper presented at Empirical Software Engineering, 2005.
Srivastva, P. R., K. Kumar, and G. Raghurama. 2008. Test case prioritization based on requirements and risk factors. ACM SIGSOFT Software Engineering Notes 33 (4): 1-5.
U.S. Atif Memon's software engineering students. 2006. TerpOffice, http://www.cs.umd.edu/~atif/TerpOfficeWeb/TerpOfficeV5.0/index.html.(Access June,2011).
Zhang, X., C. Nie, B. Xu, and B. Qu. 2007. Test case prioritization based on varying testing requirement priorities and test case costs. Paper presented at Quality Software, 2007. QSIC'07.

 
中文部分
李永祥，「產生非功能性需求測試案例之方法」，國立中正大學電機工程學系，碩士論文，民國92年7月。
陳世泓，「應用蟻群最佳化演算法於自動化倉儲系統之動線規劃」，佛光人文社會學院資訊學系，碩士論文，95年6月。
經營情報硏究會（Mint）著；周明憲譯，軟體工程實務 : 系統分析、設計與測試 = Software engineering in practical.，臺北縣汐止市 : 博碩文化，2004年。
鄭炳強著，軟體工程:從實務出發 = Software engineering : A perspective from practices.，臺北市: 智勝文化事業有限公司，民國96年。