A Family of Coverage Testing Criteria for Coloured Petri Nets
In this paper, we propose a family of specification-based coverage testing criteria for Coloured Petri Nets (CPNs). CPNs are an extension of Petri Nets with the capability of expressing, defining and handling datatypes and structured values. The main approaches used for testing and validation of CPNs based on specifications are simulation and analysis of properties. However, these approaches do not essentially provide a mechanism for quantifying the testing activity, compromising the testing quality assessment. The coverage criteria family proposed in this paper aims at complementing this scenario by providing mechanisms either to evaluate the adequacy of test sequences (e.g., sequences generated by simulation) or to guide the generation of adequate test sequences with respect to a given criterion. The underlying model to derive the requirements of the testing criteria is the occurrence graph. The concepts and criteria presented in this paper are supported by a prototyping tool. Some examples are provided to illustrate the main ideas.
Chow, T. S. (1978). Testing software design modeled by finite-state machines. IEEE Transactions on Software Engineering, 4(3):178-187.
Chung, A., Sidhu, D., Wang, Y., Lin, W., and Kou, F. (1996). Task decomposition testing and metrics for concurrent programs. In ISSRE'96 - International Symposium on Software Reliability Engineering, pages 122-130.
DeMillo, R. A., Lipton, R. J., and Sayward, F. G. (1978). Hints on test data selection: Help for the practicing programmer. IEEE Computer, 11(4):34-41.
Fabbri, S. C. P. F., Maldonado, J. C., Masiero, P. C., and Delamaro, M. E. (1994). Mutation analysis testing for finite state machines. In Fifth International Symposium on Software Reliability Engineering, pages 220-229, Monterey, California, USA.
Fabbri, S. C. P. F., Maldonado, J. C., Masiero, P. C., Delamaro, M. E., and Wong, E. (1995). Mutation testing applied to validate specifications based on Petri nets. In FORTE'95 8th International IFIP Conference on Formal Description Techniques for Distributed Systems and Communications Protocol, Montreal, Canada.
Fabbri, S. C. P. F., Maldonado, J. C., Sugeta, T., and Masiero, P. C. (1999). Mutation testing applied to validate specifications based on statecharts. In ISSRE - International Symposium on Software Reliability Systems, pages 210-219.
Frankl, P. G. and Weyuker, E. J. (1993). A formal analysis of the fault-detecting ability of testing methods. IEEE Transactions on Software Engineering, 19(3):202-213.
Fujiwara, S., Bochmann, G. V., Khendek, F., Amalou, M., and Ghedamsi, A. (1991). Test selection based on finite state models. IEEE Transactions on Software Engineering, 17(6):591-603.
Gansner, E. R. and North, S. C. (2001). An open graph visualization system and its applications to software engineering. Software - Practice & Experience, 30(11):1203-1233.
Gill, A. (1962). Introduction to the Theory of Finite-State Machines. McGraw-Hill, New York.
Hansen, M. R. and Rischel, H. (1999). Introduction to Programming using SML. Addison-Wesley.
Harel, D. (1987). Statecharts: On the formal semantics of statecharts. In The 2nd IEEE Symposium on Logic in Computer Science, pages 54-64, Ithaca, New York.
Harel, D. (1992). Bitting the silver bullet - toward a brighter future for systems development. IEEE Computer, 25(1):8-20.
Jensen, K. (1986). Coloured Petri nets. In Application and Theory of Petri Nets, volume 254 of Lecture Notes on Computer Science, pages 248-299, Berlin. Springer.
Jensen, K. (1997a). A brief introduction to coloured petri nets. In Brinkma, E., editor, Tools and Algorithms for Construction and Analysis of Systems, volume 1217 of Lecture Notes on Computer Science, pages 203-208. Springer.
Jensen, K. (1997b). Coloured Petri Nets: Analysis Methods. Springer, Berlin, 2 edition.
Jensen, K. (1997c). Coloured Petri Nets: Basic Concepts. Springer, Berlin, 2 edition.
Koppol, P. V. and Tai, K. C. (1996). An incremental approach to structural testing of concurrent software. In International Symposium on Software Testing and Analysis, pages 14-23.
Masiero, P. C., Maldonado, J. C., and Boaventura, I. G. (1994). A reachability tree for statecharts and analysis of some properties. Informations and Software Technology, 36(10):615-624.
Murata, T. (1984). Modeling and analysis of concurrent systems. In Handbook of Software Engineering. Van Nostrand Reinhold Electrical, New York.
Peterson, J. L. (1981). Petri Net Theory and the Modeling of Systems. Prentice-Hall, Englewood Cliffs, New Jersey.
Petrenko, A., v. Bochmann, G., and Yao, M. (1996). On fault coverage of tests for finite state specifications. Computer Networks and ISDN Systems, 29(1):81-106.
Probert, R. L. and Guo, F. (1991). Mutation testing of protocols: Principles and preliminary experimental results. In Proceedings of the IFIP TC6 Third International Workshop on Protocol Test Systems, pages 57-76, North-Holland.
Rapps, S. and Weyuker, E. J. (1985). Selecting software test data using data flow information. IEEE Transactions on Software Engineering, 11(4):367-375.
Simão, A. S. and Maldonado, J. C. (2000). Mutation based test sequence generation for Petri nets. In Proceedings of III Workshop of Formal Methods, pages 68-79, João Pessoa, PB.
Souza, S. R. S., Maldonado, J. C., and Fabbri, S. C. P. F. (2001). FCCE: Uma família de critérios de teste para validação de sistemas especificados em estelle. In Anais do XV Simpósio Brasileiro de Engenharia de Software, pages 256-271, Rio de Janeiro, Brasil.
Souza, S. R. S., Maldonado, J. C., Fabbri, S. C. P. F., and Lopes de Souza, W. (2000a). Mutation testing applied to Estelle specifications. Software Quality Journal, 8(4):285-301.
Souza, S. R. S., Maldonado, J. C., Fabbri, S. C. P. F., and Masiero, P. C. (2000b). Statecharts specifications: A family of coverage testing criteria. In CLEI2000 - Conferncia Latino Americana de Informtica, Cidade do Mexico, Mexico.
Taylor, R. N., Levine, D. L., and Kelly, C. D. (1992). Structural testing of concurrent programs. IEEE Transactions on Software Engineering, 18(3):206-215.
Ural, H. and Yang, B. (1991). A test sequence selection method for protocol testing. IEEE Transactions on Communications, 39(4):514-523.
Yang, C., Souter, A. L., and Pollock, L. L. (1998). All-du-path coverage for parallel programs. In International Symposium on Software Testing and Analysis, pages 153-162.
Yang, R. D. and Chung, C. (1992). Path analysis testing of concurrent programs. Information and Software Technology, 34(1):43-56.
Zhu, H. (1996). A formal analysis of the subsume relation between software test adequacy criteria. IEEE Transactions on Software Engineering, 22(4):248-255.
Zhu, H., Hall, P. A. V., and May, J. H. R. (1997). Software unit test coverage and adequacy. Computer Survey, 29(4):367-427.