基于UML Statechart图的软件测试用例自动生成技术研究
|
摘要
随着软件规模的不断扩大，软件错误也越来越容易产生。尽早地检测软件中的错误是软件开发过程中的一个重要任务，也是降低软件开发成本的主要手段。特别是针对人机交互操作较多的软件，如：CAD软件，人们希望能通过自动产生测试用例来对其进行测试，因此研究自动产生软件测试用例是非常有意义的。
本课题研究以国家863基础类研究课题“三维数字化设计系统自动测试技术研究与系统实现(课题编号：2002AA411510)”为背景，研究了基于UML Statechart图的软件测试用例自动生成技术。论文从UML Statechart图的操作语义出发，结合其层次结构的特点，讨论了UML Statechart图的测试用例自动生成的问题。主要工作如下：
(1) 以李留英等人对UML Statechart图的形式化操作语义为基础，在形式化的语义定义中，增加对junction伪状态连接的迁移关系的定义，并将迁移定义成迁移结构，使得它更适合软件测试且形式化语义更加容易被扩充。
(2) 根据迁移关系的结构化定义，提出了对fork、join、junction、choice等伪状态连接的复合迁移关系的测试方法。
(3) 根据UML Statechart图的层次结构，提出了对UML Statechart图分层产生测试用例的测试用例生成方法。根据状况的使能迁移关系集中存在迁移关系冲突而导致测试无法正确执行的情况，给出了插入测试子序列来避免迁移冲突的测试方法。
(4) 根据状态覆盖测试准则、迁移关系覆盖测试准则、迁移关系谓词覆盖测试准则、迁移关系全谓词覆盖测试准则、迁移关系谓词划分覆盖测试准则的需要，给出了相应的测试用例自动生成算法。为了辅助迁移关系划分覆盖测试准则自动产生测试用例，提出了分裂树的算法来产生谓词的DNF范式。
(5) 以上述研究工作为基础，实现了符合上述测试准则的测试用例自动生成原型系统。
With the development of all kinds of large software systems, the number of errors resulted from them have also increased. So it is necessary to explore some methods to inspect these errors, which are called as software test. And software test plays a very important role in reducing the cost of software development, and it is also a key part in Software Engineering. Especially in some software systems with a lot of human-machine interactive operations, such as CAD system, auto-generating test cases are one of the best methods to test them
Our research is supported by a national 863 research project which is named as Research on Automatic Test Technology for 3-Dimensions CAD System (Project No. is 2002AA411510). And in this thesis we present our methods to generate software test cases automaticlly, which are based on UML Statecharts specification of software. And the operational semantics about UML Statecharts and its hierarchy structure are described in this thesis. Our main works are listed as follows,
(1) On the bases of Li LiuYing's definitions on operational semantics of UML Statecharts, we add some definitions on transition linked by junction pseudostate, and describe the transition definition as transition structure, which will make it more suitable for software testing and the formal semantics, and these definitions are much easier to be expanded.
(2) Based on structural definition of transition relationship, we present our methods used in testing compound transition linked by fork, join, junction, choice pseudostate etc. in this thesis.
(3) Based on hierarchical structure of UML Statechart, a hierachical test cases generation method for UML Statechart according to its hierarchy is presented. Conflicted transitions in statues' enabled transition set may influence test cases execution. Accordingly, a new method that inserting sub-sequence in test case is set forth to deal with this problem.
(4) In order to satisfy testing requirements, state coverage criterion, transition
coverage criterion, predicate coverage criterion, full predicate coverage criterion and predicate partition coverage criterion are defined. With these coverage criterions, algorithms for automatic generating test cases are brought forward. To assist test case generation, split tree algorithm for DNF formal is presented in the thesis.
(5) Based on research work listed upon, the author implemented an automatic test cases generation system for UML Statecharts.
本课题研究以国家863基础类研究课题“三维数字化设计系统自动测试技术研究与系统实现(课题编号：2002AA411510)”为背景，研究了基于UML Statechart图的软件测试用例自动生成技术。论文从UML Statechart图的操作语义出发，结合其层次结构的特点，讨论了UML Statechart图的测试用例自动生成的问题。主要工作如下：
(1) 以李留英等人对UML Statechart图的形式化操作语义为基础，在形式化的语义定义中，增加对junction伪状态连接的迁移关系的定义，并将迁移定义成迁移结构，使得它更适合软件测试且形式化语义更加容易被扩充。
(2) 根据迁移关系的结构化定义，提出了对fork、join、junction、choice等伪状态连接的复合迁移关系的测试方法。
(3) 根据UML Statechart图的层次结构，提出了对UML Statechart图分层产生测试用例的测试用例生成方法。根据状况的使能迁移关系集中存在迁移关系冲突而导致测试无法正确执行的情况，给出了插入测试子序列来避免迁移冲突的测试方法。
(4) 根据状态覆盖测试准则、迁移关系覆盖测试准则、迁移关系谓词覆盖测试准则、迁移关系全谓词覆盖测试准则、迁移关系谓词划分覆盖测试准则的需要，给出了相应的测试用例自动生成算法。为了辅助迁移关系划分覆盖测试准则自动产生测试用例，提出了分裂树的算法来产生谓词的DNF范式。
(5) 以上述研究工作为基础，实现了符合上述测试准则的测试用例自动生成原型系统。
With the development of all kinds of large software systems, the number of errors resulted from them have also increased. So it is necessary to explore some methods to inspect these errors, which are called as software test. And software test plays a very important role in reducing the cost of software development, and it is also a key part in Software Engineering. Especially in some software systems with a lot of human-machine interactive operations, such as CAD system, auto-generating test cases are one of the best methods to test them
Our research is supported by a national 863 research project which is named as Research on Automatic Test Technology for 3-Dimensions CAD System (Project No. is 2002AA411510). And in this thesis we present our methods to generate software test cases automaticlly, which are based on UML Statecharts specification of software. And the operational semantics about UML Statecharts and its hierarchy structure are described in this thesis. Our main works are listed as follows,
(1) On the bases of Li LiuYing's definitions on operational semantics of UML Statecharts, we add some definitions on transition linked by junction pseudostate, and describe the transition definition as transition structure, which will make it more suitable for software testing and the formal semantics, and these definitions are much easier to be expanded.
(2) Based on structural definition of transition relationship, we present our methods used in testing compound transition linked by fork, join, junction, choice pseudostate etc. in this thesis.
(3) Based on hierarchical structure of UML Statechart, a hierachical test cases generation method for UML Statechart according to its hierarchy is presented. Conflicted transitions in statues' enabled transition set may influence test cases execution. Accordingly, a new method that inserting sub-sequence in test case is set forth to deal with this problem.
(4) In order to satisfy testing requirements, state coverage criterion, transition
coverage criterion, predicate coverage criterion, full predicate coverage criterion and predicate partition coverage criterion are defined. With these coverage criterions, algorithms for automatic generating test cases are brought forward. To assist test case generation, split tree algorithm for DNF formal is presented in the thesis.
(5) Based on research work listed upon, the author implemented an automatic test cases generation system for UML Statecharts.
引文
[1] Heiser J E. An overview of software testing. In: Autotestcon Proceedings, 1997 IEEE (AUTOTESTCON'97). Washington, DC: IEEE CS Press, 1997, 204 - 211
[2] 齐治昌，谭庆平，宁洪．软件工程．第一版．北京：高等教育出版社，1997(2000重印)，11—22
[3] 单景辉．面向路径的测试数据自动生成方法研究：[国防科学技术大学博士学位论文]．长沙：国防科学技术大学，2002，1—85
[4] Beizer B. Software Testing Techniques. 2th edition. Van Nostrand Reinhold, 1990
[5] H Zhu, P Hall, J May. Software unit testing coverage and adequacy. ACM Computing Surveys, 1997, 29(4):366—427
[6] Spivey J M. the Z Notation: A Reference Manual. 2th edition. Prentice-Hall, 1992
[7] Simon Burton. Automated Testing From Z Specifications. http://www.cs.york.ac.uk/ftpdir/reports/YCS-2000-329.pdf, 1998-11-02
[8] S Helke, T Neustupny, T Santen. Automating Test Case Generation from Z Specifications with Isabelle. In: ZUM'97 - The Z Formal Specification Notation. Springer, 1997, 52-71
[9] Robert M Hierons. Testing from a Z specification. The Journal of Software Testing, Verification, and Reliability, 1997, 7(1): 19-33
[10] Stocks P A, Carrington D A. Test templates: a specification-based testing framework. In: Proceedings of the 15th International Conference on Software Engineering. Washington, DC: IEEE CS Press, 1993, 405-414
[11] 兰毓华，毛法尧，曹化工．基于Z规格说明的软件测试用例自动生成．计算机学报，1999，22(9)：963-969
[12] 胡芸，缪淮扣，刘玲．从测试规格说明到测试用例的自动生成方法．同济大学学报，2002，30(10)：1226-1231
[13] B Mahony, J S Dong. Blending Object-Z and Timed CSP: An introduction to TCOZ. In: Proceedings of the 20th International Conference on Software Engineering (ICSE'98). Washington, DC: IEEE CS Press, 1998, 95-104
[14] 袁晓东，郑国梁．Z的面向对象的扩充COOZ的设计．软件学报，1997，8(9)：694—700
[15] Christophe Meudec. Automatic Generation of Software Test Cases from Formal Methods. [PhD thesis]. Belfast University. 1997
[16] Richard Atterer. Automatic Test Data Generation from VDM-SL Specification. http://home.in.tum.de/～atterer/uni/sep/vdmpart-1.0.0.pdf. 2002-07-06
[17] 顾玉良，王立福．界面类对象测试建模技术研究．计算机工程，1999，25(7)：21-23
[18] 杜栓柱，谭建荣，陆国栋．基于界面构建关联图的软件功能测试技术．计算机研究与发展，2002，39(2)：148-152
[19] Atif M Memon, Martha E Pollack, Mary Lou Soffa. Automated test oracles for GUIs. In: Proceedings of the 8th ACM SIGSOFT international symposium on Foundations of software engineering. New York: ACM Press, 2000, 30 - 39
[20] Atif Memon, Ishan Banerjee, Nada Hashmi et al. DART: A Framework for Regression Testing "Nightly/daily Builds" of GUIApplications. In: Proceedings of the International Conference on Software Maintenance (ICSM'03). Washington, DC: IEEE CS Press, 2003
[21] Atif M Memon, Mary Lou Soffa, Martha E Pollack. Coverage criteria for GUI testing. In: Proceedings of the 8th European software engineering conference held jointly with 9th ACM SIGSOFT. New York: ACM Press, 2001, 256 - 267
[22] Atif M Memon, Martha E Pollack, Mary Lou Soffa. Hierarchical GUI Test Case Generation Using Automated Planning. IEEE Transactions on Software Engineering, 2001, 27(2):144-155
[23] Atif M Memon, Mary Lou Soffa. Regression testing of GUIs. in:Proceedings of the 9th European software engineering conference held jointly with 10th ACM SIGSOFT, New York: ACM Press, 2003, 118 - 127
[24] Atif M Memon, Ishan Banerjee, Adithya Nagarajan. What Test Oracle Should Ⅰ Use for Effective GUI Testing?. In: Proceedings of the 18th IEEE Conference on Automated Software Engineering (ASE'03). Washington, DC: IEEE CS Press,2003,164-173
[25] Latella D, Majzik I, Massink M. Towards a formal operational semantics of UML Statechart diagrams. In: Proceedings of the 3rd International Conference on Formal Methods for Open Object-Oriented Distributed Systems. Boston: Kluwer Academic Publishers, 1999, 15-18
[26] Latella D, Majzik I, Massink M. A Formal Testing Framework for UML Statechart Diagrams Behaviours: From Theory to Automatic Verification. In: The Sixth IEEE International Symposium on High Assurance Systems
Engineering. Washington, DC: IEEE CS Press, 2001, 11-22
[27] D Latella,M Massink. On testing and conformance relations of UML Statechart Diagrams Behaviours. In: Proceedings of the ACM SIGSOFT 2002 International Symposium on Software Testing and Analysis. New York: ACM Press, 2002, 144-153
[28] David Harel, Eran Gery. Executable object modeling with statecharts. IEEE Computer, 1997, 30(7): 31-42
[29] E Mikk, Y Lakhnech, and M Siegel. Hierarchical automata as model for statecharts. In: 3rd Asian Computing Science Conference (ASIAN'97). Berlin: Springer-Verlag, 1997, 181-196
[30] 李留英，王戟，齐治昌．UML Statechart图的操作语义．软件学报，2001，12(12)：1864-1873
[31] 李留英，王戟，齐治昌．UML Statecharts的测试用例生成方法．计算机研究与发展，2001，38(6)：691-697
[32] Liuying Li, ZhiChang Qi. Test selection from UML Statecharts. in: 31st International Conference on Technology of Object-Oriented Language and Systems. Washington, DC: IEEE CS Press, 1999, 273-279
[33] Jeff Offutt, Shaoying Liu, Aynur Abdurazik et al. Generating Test Data From State-based Specifications. The Journal of Software Testing, Verification and Reliability, 2003.13(1):25-53
[34] Jeff Offutt, Yiwei Xiong, Shaoying Liu. Criteria for Generating Specification-based Tests. in: Fifth IEEE International Conference on Engineering of Complex Computer Systems (ICECCS '99), Washington, DC: IEEE CS Press, 1999, 119-131
[35] Jeff Offutt, Aynur Abdurazik. Generating Tests from UML Specifications. In: Second International Conference on the Unified Modeling Language (UML99). 1999, 416-429
[36] Jeff Offutt, Shaoying Liu. Generating Test Data from SOFL Specifications. The Journal of Systems and Software, 1999, 49(1):49-62
[37] Jeff Offutt, Aynur Abdurazik. Using UML Collaboration Diagrams for Static Checking and Test Generation. In: The Third International Conference on the Unified Modeling Language (UML'00). 2000, 383-395
[38] Aynur Abdurazik, Paul Ammann, Wei Ding et al. Evaluation of Three Specification-based Testing Criteria. In: Sixth IEEE International Conference on Engineering of Complex Computer Systems (ICECCS '00). Washington, DC:
IEEE CS Press, 2000, 179-187
[39] John Anil Saldhana, Sol M Shatz, ZhaoXia Hu. Formalization of object behavior and interactions from UML models. International Journal of Software Engineering Knowledge Engineering, 2001, 11(6): 643-673
[40] M Vieira, M Dias, D Richardson. Object-Oriented Specification-Based Testing Using UML Statechart Diagrams. In: Proceedings of the 22nd International Conference on Software Engineering (ICSE 2000). New York: ACM Press, 2000
[41] C Crichton, A Cavarra, J Davies. Using UML for Automatic Test Generation. http ://www.agedis.de/documents/d133_1/ASE2001.pdf
[42] Kim Y G, Hong H S, Bae D H et al. Test cases generation from UML state diagrams. Software, IEE Proceedings, 1999, 146(4):187-192
[43] OMG unified modeling language specification (Version 1.4). Needham: Object Management Group, Inc., 2001
[44] [美]Brett McLaughlin．JAVA与XML．孙照林，汪东，王鹏 译．北京：中国电力出版社，2001
[45] [美]Tom Myers，Alexander Nakhimovsky．Java XML编程指南．王辉，张晓辉等译．北京：电子工业出版社，2001
[46] OMG XML Metadata Interchange (XMI) Specification (version 1.2). An Adopted Specification of the Object Management Group, Inc.,2002
[47] [美]Meilir Page-Jones．UML面向对象设计基础．包晓露，赵晓玲，叶天军 et al 译．第一版．北京：人民邮电出版社，2001年，94—129
[48] [美]Grady Booch，James Rumbaugh，Ivar Jacobson．UML用户指南．邵维忠， 张文娟，孟祥文 译．第一版．北京：机械工业出版社，2001
[49] [美]Boggs W，Boggs M．UML与Rational Rose 2002从入门到精通．邱仲潘 等译．第一版．北京：电子工业出版社，2002
[50] [美]Robert V Binder．面向对象系统的测试．华庆一，王斌君，陈莉 译．第一版．北京：人民邮电出版社，2001
[2] 齐治昌，谭庆平，宁洪．软件工程．第一版．北京：高等教育出版社，1997(2000重印)，11—22
[3] 单景辉．面向路径的测试数据自动生成方法研究：[国防科学技术大学博士学位论文]．长沙：国防科学技术大学，2002，1—85
[4] Beizer B. Software Testing Techniques. 2th edition. Van Nostrand Reinhold, 1990
[5] H Zhu, P Hall, J May. Software unit testing coverage and adequacy. ACM Computing Surveys, 1997, 29(4):366—427
[6] Spivey J M. the Z Notation: A Reference Manual. 2th edition. Prentice-Hall, 1992
[7] Simon Burton. Automated Testing From Z Specifications. http://www.cs.york.ac.uk/ftpdir/reports/YCS-2000-329.pdf, 1998-11-02
[8] S Helke, T Neustupny, T Santen. Automating Test Case Generation from Z Specifications with Isabelle. In: ZUM'97 - The Z Formal Specification Notation. Springer, 1997, 52-71
[9] Robert M Hierons. Testing from a Z specification. The Journal of Software Testing, Verification, and Reliability, 1997, 7(1): 19-33
[10] Stocks P A, Carrington D A. Test templates: a specification-based testing framework. In: Proceedings of the 15th International Conference on Software Engineering. Washington, DC: IEEE CS Press, 1993, 405-414
[11] 兰毓华，毛法尧，曹化工．基于Z规格说明的软件测试用例自动生成．计算机学报，1999，22(9)：963-969
[12] 胡芸，缪淮扣，刘玲．从测试规格说明到测试用例的自动生成方法．同济大学学报，2002，30(10)：1226-1231
[13] B Mahony, J S Dong. Blending Object-Z and Timed CSP: An introduction to TCOZ. In: Proceedings of the 20th International Conference on Software Engineering (ICSE'98). Washington, DC: IEEE CS Press, 1998, 95-104
[14] 袁晓东，郑国梁．Z的面向对象的扩充COOZ的设计．软件学报，1997，8(9)：694—700
[15] Christophe Meudec. Automatic Generation of Software Test Cases from Formal Methods. [PhD thesis]. Belfast University. 1997
[16] Richard Atterer. Automatic Test Data Generation from VDM-SL Specification. http://home.in.tum.de/～atterer/uni/sep/vdmpart-1.0.0.pdf. 2002-07-06
[17] 顾玉良，王立福．界面类对象测试建模技术研究．计算机工程，1999，25(7)：21-23
[18] 杜栓柱，谭建荣，陆国栋．基于界面构建关联图的软件功能测试技术．计算机研究与发展，2002，39(2)：148-152
[19] Atif M Memon, Martha E Pollack, Mary Lou Soffa. Automated test oracles for GUIs. In: Proceedings of the 8th ACM SIGSOFT international symposium on Foundations of software engineering. New York: ACM Press, 2000, 30 - 39
[20] Atif Memon, Ishan Banerjee, Nada Hashmi et al. DART: A Framework for Regression Testing "Nightly/daily Builds" of GUIApplications. In: Proceedings of the International Conference on Software Maintenance (ICSM'03). Washington, DC: IEEE CS Press, 2003
[21] Atif M Memon, Mary Lou Soffa, Martha E Pollack. Coverage criteria for GUI testing. In: Proceedings of the 8th European software engineering conference held jointly with 9th ACM SIGSOFT. New York: ACM Press, 2001, 256 - 267
[22] Atif M Memon, Martha E Pollack, Mary Lou Soffa. Hierarchical GUI Test Case Generation Using Automated Planning. IEEE Transactions on Software Engineering, 2001, 27(2):144-155
[23] Atif M Memon, Mary Lou Soffa. Regression testing of GUIs. in:Proceedings of the 9th European software engineering conference held jointly with 10th ACM SIGSOFT, New York: ACM Press, 2003, 118 - 127
[24] Atif M Memon, Ishan Banerjee, Adithya Nagarajan. What Test Oracle Should Ⅰ Use for Effective GUI Testing?. In: Proceedings of the 18th IEEE Conference on Automated Software Engineering (ASE'03). Washington, DC: IEEE CS Press,2003,164-173
[25] Latella D, Majzik I, Massink M. Towards a formal operational semantics of UML Statechart diagrams. In: Proceedings of the 3rd International Conference on Formal Methods for Open Object-Oriented Distributed Systems. Boston: Kluwer Academic Publishers, 1999, 15-18
[26] Latella D, Majzik I, Massink M. A Formal Testing Framework for UML Statechart Diagrams Behaviours: From Theory to Automatic Verification. In: The Sixth IEEE International Symposium on High Assurance Systems
Engineering. Washington, DC: IEEE CS Press, 2001, 11-22
[27] D Latella,M Massink. On testing and conformance relations of UML Statechart Diagrams Behaviours. In: Proceedings of the ACM SIGSOFT 2002 International Symposium on Software Testing and Analysis. New York: ACM Press, 2002, 144-153
[28] David Harel, Eran Gery. Executable object modeling with statecharts. IEEE Computer, 1997, 30(7): 31-42
[29] E Mikk, Y Lakhnech, and M Siegel. Hierarchical automata as model for statecharts. In: 3rd Asian Computing Science Conference (ASIAN'97). Berlin: Springer-Verlag, 1997, 181-196
[30] 李留英，王戟，齐治昌．UML Statechart图的操作语义．软件学报，2001，12(12)：1864-1873
[31] 李留英，王戟，齐治昌．UML Statecharts的测试用例生成方法．计算机研究与发展，2001，38(6)：691-697
[32] Liuying Li, ZhiChang Qi. Test selection from UML Statecharts. in: 31st International Conference on Technology of Object-Oriented Language and Systems. Washington, DC: IEEE CS Press, 1999, 273-279
[33] Jeff Offutt, Shaoying Liu, Aynur Abdurazik et al. Generating Test Data From State-based Specifications. The Journal of Software Testing, Verification and Reliability, 2003.13(1):25-53
[34] Jeff Offutt, Yiwei Xiong, Shaoying Liu. Criteria for Generating Specification-based Tests. in: Fifth IEEE International Conference on Engineering of Complex Computer Systems (ICECCS '99), Washington, DC: IEEE CS Press, 1999, 119-131
[35] Jeff Offutt, Aynur Abdurazik. Generating Tests from UML Specifications. In: Second International Conference on the Unified Modeling Language (UML99). 1999, 416-429
[36] Jeff Offutt, Shaoying Liu. Generating Test Data from SOFL Specifications. The Journal of Systems and Software, 1999, 49(1):49-62
[37] Jeff Offutt, Aynur Abdurazik. Using UML Collaboration Diagrams for Static Checking and Test Generation. In: The Third International Conference on the Unified Modeling Language (UML'00). 2000, 383-395
[38] Aynur Abdurazik, Paul Ammann, Wei Ding et al. Evaluation of Three Specification-based Testing Criteria. In: Sixth IEEE International Conference on Engineering of Complex Computer Systems (ICECCS '00). Washington, DC:
IEEE CS Press, 2000, 179-187
[39] John Anil Saldhana, Sol M Shatz, ZhaoXia Hu. Formalization of object behavior and interactions from UML models. International Journal of Software Engineering Knowledge Engineering, 2001, 11(6): 643-673
[40] M Vieira, M Dias, D Richardson. Object-Oriented Specification-Based Testing Using UML Statechart Diagrams. In: Proceedings of the 22nd International Conference on Software Engineering (ICSE 2000). New York: ACM Press, 2000
[41] C Crichton, A Cavarra, J Davies. Using UML for Automatic Test Generation. http ://www.agedis.de/documents/d133_1/ASE2001.pdf
[42] Kim Y G, Hong H S, Bae D H et al. Test cases generation from UML state diagrams. Software, IEE Proceedings, 1999, 146(4):187-192
[43] OMG unified modeling language specification (Version 1.4). Needham: Object Management Group, Inc., 2001
[44] [美]Brett McLaughlin．JAVA与XML．孙照林，汪东，王鹏 译．北京：中国电力出版社，2001
[45] [美]Tom Myers，Alexander Nakhimovsky．Java XML编程指南．王辉，张晓辉等译．北京：电子工业出版社，2001
[46] OMG XML Metadata Interchange (XMI) Specification (version 1.2). An Adopted Specification of the Object Management Group, Inc.,2002
[47] [美]Meilir Page-Jones．UML面向对象设计基础．包晓露，赵晓玲，叶天军 et al 译．第一版．北京：人民邮电出版社，2001年，94—129
[48] [美]Grady Booch，James Rumbaugh，Ivar Jacobson．UML用户指南．邵维忠， 张文娟，孟祥文 译．第一版．北京：机械工业出版社，2001
[49] [美]Boggs W，Boggs M．UML与Rational Rose 2002从入门到精通．邱仲潘 等译．第一版．北京：电子工业出版社，2002
[50] [美]Robert V Binder．面向对象系统的测试．华庆一，王斌君，陈莉 译．第一版．北京：人民邮电出版社，2001