Testing hierarchical systems

ABSTRACT

We investigate the testing of hierarchical (modular) systems, in which individual modules are modeled by finite state machines. Given a hierarchical system, we are interested in finding a small set of tests that exercises all the transitions of the system. We present tight approximation algorithms and hardness results for the problem. Our techniques extend to other criteria and metrics.

REFERENCES

• 1: Ravindra K. Ahuja , Thomas L. Magnanti , James B. Orlin, Network flows: theory, algorithms, and applications, Prentice-Hall, Inc., Upper Saddle River, NJ, 1993
• 2: Rajeev Alur , Sampath Kannan , Mihalis Yannakakis, Communicating Hierarchical State Machines, Proceedings of the 26th International Colloquium on Automata, Languages and Programming, p.169-178, July 11-15, 1999
• 3: Rajeev Alur , Mihalis Yannakakis, Model Checking of Message Sequence Charts, Proceedings of the 10th International Conference on Concurrency Theory, p.114-129, August 24-27, 1999
• 4: Rajeev Alur , Mihalis Yannakakis, Model checking of hierarchical state machines, ACM Transactions on Programming Languages and Systems (TOPLAS), v.23 n.3, p.273-303, May 2001 [doi>10.1145/503502.503503]
• 5: L. Apfelbaum. Automated functional test generation. In Proc. IEEE Autotestcon Conference, 1995.
• 6: Grady Booch , James Rumbaugh , Ivar Jacobson, The Unified Modeling Language user guide, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1999
• 7: Irit Dinur , Venkatesan Guruswami , Subhash Khot , Oded Regev, A new multilayered PCP and the hardness of hypergraph vertex cover, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA [doi>10.1145/780542.780629]
• 8: J. Edmonds and E. L. Johnson. Matching, Euler tours and the Chinese postman. Mathematical Programming, 5:88--124, 1973.
• 9: David Harel, Statecharts: A visual formalism for complex systems, Science of Computer Programming, v.8 n.3, p.231-274, June 1, 1987 [doi>10.1016/0167-6423(87)90035-9]
• 10: G. Holzmann, D. A. Peled, and M. H. Redberg. Design tools for requirements engineering. Bell Labs Technical Journal, 2:86--95, 1997.
• 11: D. Lee , M. Yannakakis, Optimization problems from feature testing of communication protocols, Proceedings of the 1996 International Conference on Network Protocols (ICNP '96), p.66, October 29-November 01, 1996
• 12: D. Lee and M. Yannakakis. Principles and methods of testing finite state machines - a survey. Proceedings of the IEEE, 84:1090--1126, 1996.
• 13: Ekkart Rudolph , Peter Graubmann , Jens Grabowski, Tutorial on message sequence charts, Computer Networks and ISDN Systems, v.28 n.12, p.1629-1641, June 1996 [doi>10.1016/0169-7552(95)00122-0]
• 14: James Rumbaugh , Michael Blaha , William Premerlani , Frederick Eddy , William Lorensen, Object-oriented modeling and design, Prentice-Hall, Inc., Upper Saddle River, NJ, 1991
• 15: Bran Selic , Garth Gullekson , Paul T. Ward, Real-time object-oriented modeling, John Wiley & Sons, Inc., New York, NY, 1994
• 16: uBET. http://cm.bell-labs.com/cm/cs/what/ubet.