一种基于哈明距离的测试用例生成方法的设计与实现
|
摘要
在软件工程领域,软件测试越来越成为软件质量保证,项目顺利完成的重要步骤,在诸如航天,银行等任务关键系统中,测试显得尤为重要。
而在这样的系统中,对于布尔表达式的测试在任务关键系统的测试工作中有着特殊的意义。因为业务逻辑,操作流程等都存在大量的逻辑判断来流转,这些逻辑也就成为信息系统是否正确实现的关键环节。针对布尔表达式的测试就是用来解决这样的问题。而自动化的生成测试用例无论在实际工作中,还是在理论上都有重要的意义。
本文详细介绍了针对布尔表达式,基于哈明距离的测试用例生成方法,设计并实现了三种不同的算法:顺序查找算法,基于表达式的算法,以及基于空间结构的算法;并分析了不同实现的时间复杂度。比较了不同算法之间,对于生成测试用例在时间上的影响。对于已经存在的MC/DC以及MUMCUT方法,我们针对它们的测试用例生成结果进行了分析。并对这三种方法相互之间的关系进行了研究。为了研究,我们分别实现了MC/DC以及MUMCUT方法。
通过实例研究,我们证明了MC/DC和MUMCUT方法的在检测错误上的不足,而基于哈明距离的方法有更强的检测错误的能力,我们给出了实例,并在理论上给出了证明。
经过对比研究,我们认为基于哈明距离的测试用例生成方法,无论在理论上,还是实际测试用例的生成上,都可以覆盖MC/DC和MUMCUT这两个方法,并且在理论上可以解释已经广泛使用的两种方法。基于哈明距离的方法的测试用例生成的过程可以根据需要进行裁剪,来节省测试成本,这也是MC/DC和MUMCUT方法所不具备的能力。
In the software engineering, software testing is playing an very important role of software quality assurance. In the mission critical system, such as banking and aeronautics systems.
Testing of Boolean expressions in the mission-critical system has a significant meaning. Because there are many logical decisions in the business logic, operational procedures, all this logical decisions is the key point of implementation of the system. Boolean expressions based testing can solve this problems. Not only in the industry production, but also in the theoretical, automatic test case generation has a significant meaning.
This paper introduce the method of test case generation of Boolean expression based on hamming distance. We design and implement three different algorithms for it: sequence generation algorithm, expression based algorithm and topology based algorithm, analyze the computation complexity of the algorithms. For the existing method such as MC/DC and MUMCUT, we analyze the result of the two methods. Finally we study the relationship of the three methods. we implement the method MC/DC and MUMCUT for the research purpose.
In the study , we prove that the MC/DC and MUMCUT has the disadvantages in detecting the fault implementation of Boolean expression. And we found that the method based on hamming distance can detect more faults. We provide some examples and prove it.
After comparison study, we think the hamming distance method subsume the MC/DC and MUMCUT, and can be explained by the theory of the hamming distance. Also the method can be tailored by the requirement to save the testing cost, this is the ability other two method don't have.
而在这样的系统中,对于布尔表达式的测试在任务关键系统的测试工作中有着特殊的意义。因为业务逻辑,操作流程等都存在大量的逻辑判断来流转,这些逻辑也就成为信息系统是否正确实现的关键环节。针对布尔表达式的测试就是用来解决这样的问题。而自动化的生成测试用例无论在实际工作中,还是在理论上都有重要的意义。
本文详细介绍了针对布尔表达式,基于哈明距离的测试用例生成方法,设计并实现了三种不同的算法:顺序查找算法,基于表达式的算法,以及基于空间结构的算法;并分析了不同实现的时间复杂度。比较了不同算法之间,对于生成测试用例在时间上的影响。对于已经存在的MC/DC以及MUMCUT方法,我们针对它们的测试用例生成结果进行了分析。并对这三种方法相互之间的关系进行了研究。为了研究,我们分别实现了MC/DC以及MUMCUT方法。
通过实例研究,我们证明了MC/DC和MUMCUT方法的在检测错误上的不足,而基于哈明距离的方法有更强的检测错误的能力,我们给出了实例,并在理论上给出了证明。
经过对比研究,我们认为基于哈明距离的测试用例生成方法,无论在理论上,还是实际测试用例的生成上,都可以覆盖MC/DC和MUMCUT这两个方法,并且在理论上可以解释已经广泛使用的两种方法。基于哈明距离的方法的测试用例生成的过程可以根据需要进行裁剪,来节省测试成本,这也是MC/DC和MUMCUT方法所不具备的能力。
In the software engineering, software testing is playing an very important role of software quality assurance. In the mission critical system, such as banking and aeronautics systems.
Testing of Boolean expressions in the mission-critical system has a significant meaning. Because there are many logical decisions in the business logic, operational procedures, all this logical decisions is the key point of implementation of the system. Boolean expressions based testing can solve this problems. Not only in the industry production, but also in the theoretical, automatic test case generation has a significant meaning.
This paper introduce the method of test case generation of Boolean expression based on hamming distance. We design and implement three different algorithms for it: sequence generation algorithm, expression based algorithm and topology based algorithm, analyze the computation complexity of the algorithms. For the existing method such as MC/DC and MUMCUT, we analyze the result of the two methods. Finally we study the relationship of the three methods. we implement the method MC/DC and MUMCUT for the research purpose.
In the study , we prove that the MC/DC and MUMCUT has the disadvantages in detecting the fault implementation of Boolean expression. And we found that the method based on hamming distance can detect more faults. We provide some examples and prove it.
After comparison study, we think the hamming distance method subsume the MC/DC and MUMCUT, and can be explained by the theory of the hamming distance. Also the method can be tailored by the requirement to save the testing cost, this is the ability other two method don't have.
引文
[1]. J. J. Chilenski, “An Investigation of Three Forms of the Modified Condition Decision Coverage Criterion”, Report DOT/FAA/AR-01/18, Federal Aviation Administration, USA, April 2001.
[2]. J. J. Chelenski and S.P. Miller, “Applicability of Modified Condition/Decision Coverage to Software Testing”, Software Engineering Journal, Vol. 9, No. 5, Sept. 1994, pp. 193-200.
[3]. T. Y. Chen and M. F. Lau, “Two Test Cases Selection Strategies Towards Testing of Boolean Specifications”, in Proceedings of the 21st Annual International Computer Software and Applications Conference (COMPSAC’97), pp. 608-611.
[4]. T. Y. Chen and M. F. Lau, “Test Cases Selection Strategies based on Boolean Specifications”, Software Testing, Verification and Reliability, Sep. 2001, Vol. 11, No. 3. pp.165-180.
[5]. T. Y. Chen , M. F. Lau and Y. T. Yu, “MUMCUT: A Fault-based Strategy for Testing Boolean Specifications“, in Proceedings of 1999 Asia-Pacific Conference on Software Engineering (APSEC’99), Dec. 1999, pp. 606-613.
[6]. A. Dupuy and N. Leveson, “An Empirical Evaluation of the MC/DC Coverage Criterion on the HETE-2 Satellite Software”, in Proceedings of The 19th Digital Aviation Systems Conference, Oct. 2000, Vol. 1, pp.1B6/1-1B6/7.
[7]. K. A. Foster, “Sensitive Test Data for Logic Expressions”, ACM SIGSOFT Software Engineering Notes, 1984, Vol. 9, No. 2, pp. 120-125.
[8]. J. A. Jones and M. J. Harrold, “Test-Suite Reduction and Prioritization for Modified Condition/Decision Coverage”, IEEE Transactions on Software Engineering, Vol. 29, No. 3, Mar. 2003, pp.195-209.
[9]. D. R. Kuhn, “Fault Classes and Error Detection Capability of Specification-based Testing”, ACM Transactions on Software Engineering and Methodology, Vol. 8, No. 4,Oct. 1999, pp.411-424.
[10]. M. F. Lau and Y. T. Yu, “On the Relationships of Faults by for Boolean Specification based Testing”, In Proceedings of 2001 Australian Software Engineering Conference (ASWEC2001). Aug. 2001, pp.21-28.
[11]. G. J. Myers, The Art of Software Testing, Wiley, 1979.
[12]. “Software Considerations in Airborne Systems and Equipment Certification”, Document RTCA/DO-178B, RTCA, Inc., December 1992.
[13]. K. H. Rosen, Discrete Mathematics and Its Applications, McGraw Hill, Fifth edition, 2003.
[14]. K.C. Tai, H.K. Su, “Test Generation for Boolean Expressions”, in Proceedings of The 11th Annual International Computer Software and Application Conference (COMPSAC 87), 1987, pp. 278-284.
[15]. K.C. Tai, “Condition-based Software Testing Strategies”, in Proceedings of The 14th Annual International Computer Software and Application Conference (COMPSAC 90), 1990, pp. 564-569.
[16]. K.C. Tai, “Theory of Fault-based Predicate Testing for Computer Programs”, IEEE Transactions on Software Engineering 1996, Vol. 22, No. 8, pp. 552-562.
[17]. W. T. Tsai, R. Paul, Z. Cao, L. Yu, A. Saimi and B. Xiao. “Verification of Web Services Using an Enhanced UDDI Server”, Proceedings of IEEE Workshop on Object-oriented Real-time Dependable Systems (WORDS), 2003, pp. 131-138.
[18]. W. T. Tsai, R. Paul, L. Yu, X. Wei, and F. Zhu, “Rapid Pattern-Oriented Scenario-Based Testing for Embedded Systems” to appear in Software Evolution with UML and XML, edited by H. Yang, 2004.
[19]. W. T. Tsai, L. Yu, F. Zhu and R. Paul. “Rapid Verification of Embedded Systems Using Patterns”, Proceedings of IEEE Annual International Computer Software and Applications Conference (COMPSAC), 2003. pp. 466-471.
[20]. W. T. Tsai, F. Zhu, L. Yu, R. Paul, and C. Fan, “Verification Patterns for Rapid Embedded System Verification”, Proceedings of International Conference on Embedded Systems and Applications (ESA), 2003. pp. 310-316.
[21]. T. Tsuchiya and T. Kikuno, “On Fault Classes and Error Detection Capability of Specification-based Testing”, ACM Transactions on Software Engineering and Methodology, Vol. 11, No. 1, 2002, pp. 58-62.
[22]. E. J. Weyuker, T. Goradia, and A. Singh, “Automatically Generating Test Data from a Boolean Specification”, IEEE Transactions on Software Engineering, Vol.20, No. 5, May 1994, pp.353-363.
[23]. Paradkar, A., Tai, K.C., Vouk, M.A., 1996. Automatic test-generation for predicates. IEEE Transactions on Reliability 45 (4), 515–530.
[24]. Tai, K.C., 1996. Theory of fault-based predicate testing for computer programs. IEEE Transactions on Software Engineering 22 (8), 552–562.
[25]. Tai, K.-C., Su, H.-K., 1987. Test generation for Boolean expressions.In: Proceedings of the Eleventh Annual International Computer Software and Applications Conference (COMPSAC87). IEEE Computer Society Press, pp. 278–284.
[26]. Tsuchiya, T., Kikuno, T., 2002. On fault classes and error detection capability of specification-based testing. ACM Transactions on Software Engineering and Methodology 11 (1), 58–62.
[27]. Vouk, M.A., Tai, K.C., Paradkar, A., 1994. Empirical studies of predicate-based software testing. In: Proceedings of 1994 International Symposium on Software Reliability Engineering. IEEE Computer Society Press, pp. 55–64.
[28]. Weyuker, E., Goradia, T., Singh, A., 1994. Automatically generating test data from a Boolean specification. IEEE Transactions on Software Engineering 20 (5), 353–363.
[29]. Yu, Y.T., Lau, M.F., 2004. Comparing several coverage criteria for detectingfaults in logical decisions. In: Proceedings of the Fourth
[30]. International Conference on Quality Software (QSIC 2004). IEEE Computer Society Press, pp. 14–21.
[31]. Yu, Y.T., Lau, M.F., Chen, T.Y., 2003. Using the incremental approach to generate test sets: a case study. In: Proceedings of the Third International Conference on Quality Software (QSIC 2003). IEEE Computer Society Press, pp. 263–270.
[32]. Zhu, H., 1996. A formal analysis of the subsume relation between software test adequacy criteria. IEEE Transactions on Software Engineering 22 (4), 248–255.
[2]. J. J. Chelenski and S.P. Miller, “Applicability of Modified Condition/Decision Coverage to Software Testing”, Software Engineering Journal, Vol. 9, No. 5, Sept. 1994, pp. 193-200.
[3]. T. Y. Chen and M. F. Lau, “Two Test Cases Selection Strategies Towards Testing of Boolean Specifications”, in Proceedings of the 21st Annual International Computer Software and Applications Conference (COMPSAC’97), pp. 608-611.
[4]. T. Y. Chen and M. F. Lau, “Test Cases Selection Strategies based on Boolean Specifications”, Software Testing, Verification and Reliability, Sep. 2001, Vol. 11, No. 3. pp.165-180.
[5]. T. Y. Chen , M. F. Lau and Y. T. Yu, “MUMCUT: A Fault-based Strategy for Testing Boolean Specifications“, in Proceedings of 1999 Asia-Pacific Conference on Software Engineering (APSEC’99), Dec. 1999, pp. 606-613.
[6]. A. Dupuy and N. Leveson, “An Empirical Evaluation of the MC/DC Coverage Criterion on the HETE-2 Satellite Software”, in Proceedings of The 19th Digital Aviation Systems Conference, Oct. 2000, Vol. 1, pp.1B6/1-1B6/7.
[7]. K. A. Foster, “Sensitive Test Data for Logic Expressions”, ACM SIGSOFT Software Engineering Notes, 1984, Vol. 9, No. 2, pp. 120-125.
[8]. J. A. Jones and M. J. Harrold, “Test-Suite Reduction and Prioritization for Modified Condition/Decision Coverage”, IEEE Transactions on Software Engineering, Vol. 29, No. 3, Mar. 2003, pp.195-209.
[9]. D. R. Kuhn, “Fault Classes and Error Detection Capability of Specification-based Testing”, ACM Transactions on Software Engineering and Methodology, Vol. 8, No. 4,Oct. 1999, pp.411-424.
[10]. M. F. Lau and Y. T. Yu, “On the Relationships of Faults by for Boolean Specification based Testing”, In Proceedings of 2001 Australian Software Engineering Conference (ASWEC2001). Aug. 2001, pp.21-28.
[11]. G. J. Myers, The Art of Software Testing, Wiley, 1979.
[12]. “Software Considerations in Airborne Systems and Equipment Certification”, Document RTCA/DO-178B, RTCA, Inc., December 1992.
[13]. K. H. Rosen, Discrete Mathematics and Its Applications, McGraw Hill, Fifth edition, 2003.
[14]. K.C. Tai, H.K. Su, “Test Generation for Boolean Expressions”, in Proceedings of The 11th Annual International Computer Software and Application Conference (COMPSAC 87), 1987, pp. 278-284.
[15]. K.C. Tai, “Condition-based Software Testing Strategies”, in Proceedings of The 14th Annual International Computer Software and Application Conference (COMPSAC 90), 1990, pp. 564-569.
[16]. K.C. Tai, “Theory of Fault-based Predicate Testing for Computer Programs”, IEEE Transactions on Software Engineering 1996, Vol. 22, No. 8, pp. 552-562.
[17]. W. T. Tsai, R. Paul, Z. Cao, L. Yu, A. Saimi and B. Xiao. “Verification of Web Services Using an Enhanced UDDI Server”, Proceedings of IEEE Workshop on Object-oriented Real-time Dependable Systems (WORDS), 2003, pp. 131-138.
[18]. W. T. Tsai, R. Paul, L. Yu, X. Wei, and F. Zhu, “Rapid Pattern-Oriented Scenario-Based Testing for Embedded Systems” to appear in Software Evolution with UML and XML, edited by H. Yang, 2004.
[19]. W. T. Tsai, L. Yu, F. Zhu and R. Paul. “Rapid Verification of Embedded Systems Using Patterns”, Proceedings of IEEE Annual International Computer Software and Applications Conference (COMPSAC), 2003. pp. 466-471.
[20]. W. T. Tsai, F. Zhu, L. Yu, R. Paul, and C. Fan, “Verification Patterns for Rapid Embedded System Verification”, Proceedings of International Conference on Embedded Systems and Applications (ESA), 2003. pp. 310-316.
[21]. T. Tsuchiya and T. Kikuno, “On Fault Classes and Error Detection Capability of Specification-based Testing”, ACM Transactions on Software Engineering and Methodology, Vol. 11, No. 1, 2002, pp. 58-62.
[22]. E. J. Weyuker, T. Goradia, and A. Singh, “Automatically Generating Test Data from a Boolean Specification”, IEEE Transactions on Software Engineering, Vol.20, No. 5, May 1994, pp.353-363.
[23]. Paradkar, A., Tai, K.C., Vouk, M.A., 1996. Automatic test-generation for predicates. IEEE Transactions on Reliability 45 (4), 515–530.
[24]. Tai, K.C., 1996. Theory of fault-based predicate testing for computer programs. IEEE Transactions on Software Engineering 22 (8), 552–562.
[25]. Tai, K.-C., Su, H.-K., 1987. Test generation for Boolean expressions.In: Proceedings of the Eleventh Annual International Computer Software and Applications Conference (COMPSAC87). IEEE Computer Society Press, pp. 278–284.
[26]. Tsuchiya, T., Kikuno, T., 2002. On fault classes and error detection capability of specification-based testing. ACM Transactions on Software Engineering and Methodology 11 (1), 58–62.
[27]. Vouk, M.A., Tai, K.C., Paradkar, A., 1994. Empirical studies of predicate-based software testing. In: Proceedings of 1994 International Symposium on Software Reliability Engineering. IEEE Computer Society Press, pp. 55–64.
[28]. Weyuker, E., Goradia, T., Singh, A., 1994. Automatically generating test data from a Boolean specification. IEEE Transactions on Software Engineering 20 (5), 353–363.
[29]. Yu, Y.T., Lau, M.F., 2004. Comparing several coverage criteria for detectingfaults in logical decisions. In: Proceedings of the Fourth
[30]. International Conference on Quality Software (QSIC 2004). IEEE Computer Society Press, pp. 14–21.
[31]. Yu, Y.T., Lau, M.F., Chen, T.Y., 2003. Using the incremental approach to generate test sets: a case study. In: Proceedings of the Third International Conference on Quality Software (QSIC 2003). IEEE Computer Society Press, pp. 263–270.
[32]. Zhu, H., 1996. A formal analysis of the subsume relation between software test adequacy criteria. IEEE Transactions on Software Engineering 22 (4), 248–255.