軟體測試過程中經常以覆蓋標準衡量測試之完整度，而修正條件/決策覆蓋(Modified Condition/Decision Coverage, MC/DC)即為常見的覆蓋標準之一。事實上，MC/DC覆蓋較其他覆蓋標準嚴格許多，針對相同的受測程式，滿足此覆蓋標準的測試套件亦較難生成。因此，如何有效地評估現有的測試套件的MC/DC覆蓋率並補齊缺少的測試案例是相當重要的研究議題。美國國家航空暨太空總署(NASA)所提出的邏輯閘觀念雖能快速評估測試套件的MC/DC覆蓋率，但遇到條件(Conditions)數較高的決策點(Branch)時無法確保達成百分之百的覆蓋率；另一種奠基於高維立方體整合格雷碼(Gray Code)概念的方法可克服NASA方法的缺點，但其面對條件數較高的決策點時耗費的成本過高。本研究擬以高維立方體整合格雷碼之概念為基礎，提出新演算法以補強現有方法之不足。我們提出之作法擬以原有測試案例之對角點和平移點為起點，更有效地找尋缺少的測試案例，且更有效率地評估測試套件的覆蓋率。最後，實驗結果證實，此方法確實能較有效地評估測試套件的MC/DC覆蓋程度，並生成滿足MC/DC覆蓋標準的測試套件。

Modified Condition/Decision Coverage (MC/DC) is one of the common coverage criteria to evaluate the completeness of the tests during software testing. Compared with other coverage criteria, it is more difficult to generate a test suite that satisfies 100% MC/DC coverage rate for a subject program. Thus, it is important to efficiently evaluate the MC/DC coverage of test suite, and generate the remaining test cases to achieve 100% coverage rate. National Aeronautics and Space Administration (NASA) proposed an approach, based on the concept of logical gates, to solve this problem. However, it may not achieve 100% coverage rate for the branches that consists of a lot of conditions. Later, a method called N-cube combined with Gray code are proposed to address this problems, but the time consumption is considerable, especially for the branch with a lot of conditions. Therefore, in this thesis, we will propose an algorithm to enhance the performance of the N-cube combined with Gray code. The performance and effectiveness of the proposed algorithm are justified via some simulated data sets and three real data sets. The experimental results indicate that, in comparison to other approaches, the proposed algorithm performs better in evaluating the coverage of a test suite and generating the remaining test cases.

摘要 i
Abstract ii
致謝 iii
目錄 iv
表目錄 vii
圖目錄 viii
第1章 前言 1
第2章 相關研究 4
2.1 MC/DC之定義 4
2.2 奠基於MC/DC覆蓋標準之現有測試套件生成方法 6
2.2.1 NASA方法 6
2.2.2 高維立方體整合格雷碼方法 8
第3章 新評估與生成方法 12
3.1 現有方法之缺點與改進動機 12
3.2 新評估與生成方法 13
3.2.1 步驟一—評估需求案例的MC/DC配對 14
3.2.2 步驟二—由最高權重的需求案例尋找與之成MC/DC配對之測試案例 17
3.2.3 步驟三—由其他高權重的需求案例尋找與之成MC/DC配對之測試案例 18
3.2.4 步驟四—藉需求案例之對角點和平移點尋找不足的測試案例 20
3.2.4.1 藉需求案例之對角點尋找不足的測試案例 20
3.2.4.2 藉需求案例之平移點尋找不足的測試案例 22
3.2.5 步驟五—從隨機點尋找不足的測試案例 25
3.3 測試條件限制 25
第4章 實驗與分析 27
4.1 案例分析1：模擬資料 27
4.1.1 實驗設定 27
4.1.2 實驗分析 31
4.1.2.1 測試套件分析 31
4.1.2.1 效率分析 31
4.1.2.2 其他分析 34
4.2 案例分析2：標準資料 37
4.2.1 實驗設定 37
4.2.2 實驗分析 38
4.2.2.1 測試套件分析 38
4.2.2.2 效率分析 39
4.3 案例分析3：實際程式 40
4.3.1 實驗設定 40
4.3.2 實驗分析 40
4.3.2.1 測試套件分析 40
4.3.2.2 效率分析 41
第5章 結論及未來研究方向 43
參考文獻 44

[1] I. Alsmadi, “Using Genetic Algorithms for Ttest Case Generation and Selection Optimization,” Proceedings of the 23th Canadian Conference on Electrical and Computer Engineering (CCECE), pp. 1-4, 2010.

[2] J. R. Chang and C. Y. Huang, “A Study of Enhanced MC/DC Coverage Criterion for Software Testing,” Proceedings of 31th Annual International Computer Software and Applications Conference, pp. 457–464, 2007.

[3] T. Y. Chen, M. F. Lau, and Y. T. Yu, “MUMCUT: A Fault-Based Strategy for Testing Boolean Specifications,” Proceedings of sixth Asia Pacific Software Engineering Conference (APSEC), pp. 606-613, 1999.

[4] Y. Chen and Y. Zhong, “Automatic Path-Oriented Test Data Generation Using a Multi-population Genetic Algorithm,” Proceedings of the fourth International Conference on Natural Computation, Vol. 1, pp. 566-570, 2008.

[5] K. T. Cheng and A. S. Krishnakumar, “Automatic Functional Test Generation Using the Extended Finite State Machine Model,” Proceedings of the 30th International Design Automation Conference, pp. 86-91, 1993.

[6] J. J. Chilenski, “An Investigation of Three Forms of the Modified Condition Decision Coverage (MCDC) Criterion,” FAA Tech Center Report DOT/FAA/AR-01/18, April 2001.

[7] J. J. Chilenski and S. P. Miller, “Applicability of Modified Condition/Decision Coverage to Software Testing,” Software Engineering Journal, Vol. 9, No. 5, pp. 193-200, Sep 1994.

[8] L. A. Clarke, A. Podgurski, D. J. Richardson, and S. J. Zeil, “A Formal Evaluation of Data Flow Path Selection Criteria,” IEEE Trans. on Software Engineering, Vol. 15, No. 11, pp. 1318-1332, 1989.

[9] A. Dupuy and N. Leveson, “An Empirical Evaluation of the MC/DC Coverage Criterion on the HETE-2 Satellite Software,” Proceeding of 19th Digital Avionics Systems Conference, Vol. 1, pp. 1B6/1-1B6/7, 2000.

[10] D. G. Firesmith, “Testing Object-Oriented Software,” Software Engineering Strategies, November/December 1993.

[11] A. Gargantini, “Dealing with Constraints in Boolean Expression Testing,” Proceedings of the forth IEEE International Conference on Software Testing, Verification and Validation Workshops (ICSTW), pp. 322-327, 2011.

[12] K. Ghani and J. A. Clark, “Automatic Test Data Generation for Multiple Condition and MCDC Coverage,” Proceedings of the fourth International Conference on Software Engineering Advances, pp. 152-157, 2009.

[13] K. J. Hayhurst, D. S. Veerhusen, J. J. Chilenski, and L. K. Rierson, “A Practical Approach to Modified Condition/Decision Coverage”, Technical Report: NASA-2001-tm210876, 2001.

[14] K. J. Hayhurst, D. S. Veerhusen, J. J. Chilenski, and L. K. Rierson, “A Practical Tutorial on Modified Condition/Decision Coverage,” Report NASA/TM-2001-210876, NASA, May 2001.

[15] M. P. E. Heimdahl and D. George, “Test-Suite Reduction for Model Based Tests: Effects on Test Quality and Implications for Testing,” Proceeding of the 19th International Conference on Automated Software Engineering, pp. 176-185, 2004.

[16] J. A. Jones and M. J. Harrold, “Test-Suite Reduction and Prioritization for Modified Condition/Decision Coverage,” Proceeding of the IEEE International Conference on Software Maintenance, pp. 92-101, 2001.

[17] K. Kapoor and J. Bowen, “Experimental Evaluation of the Variation in Effectiveness for DC, FPC and MC/DC Test Criteria,” Proceeding of the International Symposium on Empirical Software Engineering (ISESE), pp. 185-194, 2003.

[18] M. Khandai, A. A. Acharya, and D. P. Mohapatra, “A Novel Approach of Test Case Generation for Concurrent Systems Using UML Sequence Diagram,” Proceedings of the third International Conference on Electronics Computer Technology (ICECT), Vol. 1, pp. 157-161, 2011.

[19] Z. Kohavi, R. W. Hamming, and E. A. Feigenbaum, “Switching and Finite Automata Theory,” Computer Science Series, McGraw-Hill Higher Education, 1990.

[20] Y. Y. Li, “Structural Test Cases Analysis and Implementation,” Proceedings of the 42nd Midwest Symposium on Circuits and Systems, pp. 882-885, 1999.

[21] T. A. Majchrzak and H. Kuchen, “Automated Test Case Generation Based on Coverage Analysis,” Proceedings of the third IEEE International Symposium on Theoretical Aspects of Software Engineering, pp. 259-266, 2009.

[22] G. J. Myers, “The Art of Software Testing,” New York: Wiley, 1979.

[23] J. Pan, “Software Testing,” In the Proceedings of the Software Engineering Institute, Carnegie Mellon University, http://www.ece.cmu.edu/~koopman/des_s99/sw_testing/, 1999.

[24] L. Pan, B. Zou, J. Li, and H. Chen, “Bi-Objective Model for Test-Suite Reduction Based on Modified Condition/Decision Coverage,” Proceedings of the 11th Pacific Rim International Symposium on Dependable Computing, pp. 7-13, 2005.

[25] J. Prabhu, N. Malmurugan, G. Gunasekaran, and R. Gowtham, “Study of ERP Test-Suite Reduction Based on Modified Condition/Decision Coverage,” Proceedings of Second International Conference on Computer Research and Development, pp. 373-378, 2010.

[26] M. Sharma, D. Kundu, and R. Mall, ”Automatic Test Case Generation from UML Sequence Diagram,” Proceedings of the International Conference on Advance Computing and Communication, pp.60-67, 2007.

[27] S. A. Vilkomir and J. P. Bowcn, “Formalization of Control-flow Criteria of Software Testing,” Technical Report SBU-CISM-01-01, SCISM, South Bank University, London, UK, January, 2001.

[28] E. Weyuker, T. Goradia, and A. Singh “Automatically Generating Test Data from a Boolean Specification,” IEEE Transactions on Software Engineering, Vol. 20, No.5, pp. 353-363, 1994.

[29] A. L. White, “Comments on Modified Condition/Decision Coverage for Software Testing,” Proceedings of the IEEE Aerospace Conference, Vol. 6, pp. 2821-2827, 2001.

[30] RCTA. DO-178-B, “Software Considerations in Airborne Systems and Equipment Certification,” RCTA, July 1992.

[31] “Software-artifact Infrastructure Repository (SIR)”, Site: http://sir.unl.edu/portal, Available Date: 2012/07/12.