Checking Compatibility and Substitutability of Software Components

Zuberek, W.M.

in: Models and Methodology of System Dependability; Oficyna Wydawnicza Politechniki Wroclawskiej, ch.14, pp.175-186, 2010 (ISBN 978-83-7493-5260-5).

Abstract:

In component-based systems, two components are compatible if all possible sequences of services requested by one component can be provided by the other component. It has been recently shown that for verification of compatibility, the behavior of interacting components, at their interfaces, can be modeled by labeled Petri nets with labels representing the requested and provided services. Such component models are then composed and the composition operation is designed in such a way that component incompatibilities are manifested as deadlocks in the composed model. Compatibility verification is thus performed through deadlock analysis of the composed models. Component compatibility is also used for the verification of component substitutability; if the new component is compatible with all components that interact with the old component, it can safely replace the old one.

Keywords:

Software components, component-based systems, component compatibility, compatibility verification, component substitutability, Petri nets.

References:

• M. Belguidoum, F. Dagnat, "Formalization of component substitutability"; Electronic Notes in Theoretical Comptuer Science, vol.215, pp.75-92, 2008.
• B. Bordbar, K. Okano, "Testing deadlock-freeness in real-time systems: a formal approach"; Formal Approaches to Software Testing (Lecture Notes in Computer Science 3395) pp.95-109, 2004.
• P. Brada, L. Valenta, "Practical verification of component substitutability using subtype relation"; Proc. Int. Conf. on Software Engineering and Advances Applications (SEAA'06), pp.38-45, 2006.
• I. Cerna, P.Varekova, B. Zimmerova, "Component substitutability via equivalencies of component-interaction automata"; Proc. Int. Workshop on Formal Aspects of Component Software (FACS'06), pp.115-130, 2006.
• S. Chaki, E.M. Clarke, A. Groce, S. Jha, H. Veith, "Modular verification of software components in C"; IEEE Trans. on Software Engineering, vol.30, no.6, pp.388-402, 2004.
• F. Chu, X. Xie, "Deadlock analysis of Petri nets using siphons and mathematical programming"; IEEE Trans. on Robotics and Automation, vol.13, no.6, pp.793-804, 1997.
• J. Costa Seco, L. Caires, "A basic model of typed components"; Proc. 14-th European Conf. on Object-Oriented Programming, London, UK, pp.108-128, 2000.
• D.C. Craig, "Compatibility of software components -- modeling and verification"; Ph.D. Thesis, Department of Computer Science, Memorial University, St.John's, Canada A1B 3X5, 2006.
• D.C. Craig, W.M. Zuberek, "Compatibility of software components - modeling and verification"; Proc. Int. Conf. on Dependability of Computer Systems, Szklarska Poreba, Poland, pp.11-18, 2006.
• D.C. Craig, W.M. Zuberek, "Petri nets in modeling component behavior and verifying component compatibility"; Proc. Int. Workshop on Petri Nets and Software Engineering, Siedlce, Poland, pp.160-174, 2007.
• J. Ezpeleta, J.M. Colombo, J. Martinez, "A Petri net based deadlock prevention policy for flexible manufacturing systems"; IEEE Trans. on Robotics and Automation, vol.11, no.2, pp.173-184, 1995.
• J.E. Hopcroft, R. Motwani, J.D. Ullman, "Introduction to automata theory, languages, and computations" (2 ed.); Addison-Wesley 2001.
• R. Janicki, P.E. Lauer, Specification and analysis of concurrent systems - the COSY approach; Springer-Verlag 1992.
• T. Murata, "Petri nets: properties, analysis, and applications"; Proceedings of the IEEE, vol.77, no.4, pp.541-580, 1989.
• W. Reisig, Petri nets - an introduction (EATCS Monographs on Theoretical Computer Science 4); Springer-Verlag 1985.
• M. Silva, E. Teruel, J. Couvreur, "Linear algebra in and linear programming techniques for the analysis of place/transition net systems"; Lectures on Petri nets -- basic models (Lecture Notes in Computer Science 1491), pp.309-373, Springer-Verlag 1998.
• A.M. Zaremski, J.M. Wang, "Specification matching of software components"; ACM Trans. on Software Engineering and Methodology, vol.6, no.4, pp.333-369, 1997.

Available in pdf.