State Machine DNA

About this Page

On this page we describe our current work on state machine DNA. This work is part of a GOA project, with title Embedded Systems for Multimedia Applications Toward an Efficient Design Methodology.

Additional funding and support from the Prof. Dr. Wuytack Fund and the Department of Pure Mathematics and Computer Algebra.

Benjamin De Leeuw

prof. dr. Albert Hoogewijs

Gent University

Belgium

Motivation

The Unified Modeling Language (OMG-UML) is a visual formalism to classify and display all kinds of information in the form of a diagrammatic model. Buisness models, action models, database models, software models, metamodels and real-time specifications are but some of the sheer endless possibilities of the Unified Modeling Language. The basic diagrams of the UML have been widely accepted in industry and the engineering community as valuable and exchangeable representations of diagrammatic information.

One of the UML diagrams is the Statechart. Invented and formalized by David Harel, it was soon integrated in the UML concept. Statecharts are used in behavior specifications. Allthough useful in the specification of complex interaction patterns, its take-up in industry is not like the other basic UML diagrams. Statecharts offer ways to define system behavior for distributed components, synchronized by event-based communication and shared memory usage. Using Statecharts to specify single component systems or even sequentially consistent distributed computations is a useless effort. Only distributed computations with very complex or non-deterministic interaction patterns are valid candidates to be modeled as UML Statecharts. Convincing examples of such complex interaction systems can be found in biological sciences. Other examples include, but are not limited to, airtraffic control systems, security intensive systems, space vehicle models, embedded systems and so on.

One of the main efforts in the computer science community is the verification of complex distributed and non-deterministic applications. With modelchecking techniques as introduced by E. Clarke, Vardi and many others, Statechart specifications can be verified to possess certain properties. Our colleague dr. Sara Van Langenhove has made an implementation which checks Statechart models for user defined properties. Look up her website here for more information on the matter.

Our research on State Machine DNA tries to maken an in-depth analysis of state machine (or Statechart) primitive structures using a generative grammar (rewrite system). The language that is generated by this rewrite system is called State Machine DNA. State Machine DNA provides a workable compaction and serialization of state machines, allowing two practical applications, namely

complexity metric and
version comparison for state machines.

With the complexity metric we are able to measure the complexity of state machines by tracking the complexity determining constructs in a way similar to the McCabe or cyclomatic complexity metric for procedural and object oriented programs. State machine version comparison allows us to compose version histories of state machines that can be compared and merged visually, laying out the foundation for (automatic) merge tools for state machine diagrams, similar to the ones available for object oriented source code.

Background Information

UML

In an effort to develop a language that fitted in with all contemporary good programming and design practices for object-oriented models, the three amigos Rumbaugh, Jacobson and Booch invented the Unified Modeling Language (UML). Now, the UML is integrated in the Object Management Group's (OMG) Model Driven Design project. UML can be seen as a formalization or stratification of paper-and-pencil scetches of software systems, made by programmers to evaluate their ideas before implementing them. UML offers highly evolved schemata to draw organizations of information in. For more information on the UML, check out the references below.

G. Booch, J. Rumbaugh, and I. Jacobson. The Unified Modeling Language User Guide (2nd edition). Addison-Wesley Professional, 2005.
OMG. Unified Modeling Language: Superstructure, v2.0 (formal/05-07-04), August 2005.
OMG. MOF 2.0/XMI Mapping Specification, v2.1 (formal/05-09-01), September 2005.
J. Rumbaugh, M. R. Blaha, W. Lorensen, F. Eddy, and W. Premerlani. Object-oriented Modeling and Design. Prentice Hall, 1990.
OMG: MDA Guide Version 1.0.1 (omg/2003-06-01) (2003)

Statecharts

Statecharts are labeled transition systems, extended with constructs for hierarchical organisation and for the denotation of concurrent processes. Transitions are labeled with a trigger, a guard and an actionlist, specified in some context-free action language. For more information on Statecharts, take a look at the references below.

D. Harel. Statecharts: A Visual Formalism for Complex Systems. Science of Computer Programming, 8(3):231–274, June 1987.

Program Instrumentation

Instrumenting programs amounts to measuring certain things of a program, before or during its execution. Some example measures for programs are: number of cache missers, number of memory operations, number of instructions, number of loops, loopnesting, unreachable code, number of external calls and so on. For a more in depth discussion about the general outline and possible instrumentations of programs, check out the references below. We also included a reference on the McCabe or cyclomatic complexity metric. Another important metric is the Halstead metric a reference of which is also included below for illustratory purposes.

L. Briand, K. E. Emam, and S. Morasca. Theoretical and Empirical Validation of Software Product Measures. Technical Report ISERN-95-03, 1995.
Tom McCabe. A Complexity Measure. IEEE Transactions on Software Engineering, 2(4):308-320, December 1976.
M. H. Halstead. Elements of Software Science. Elsevier North-Holland, 1977.

Object Model Instrumentation

The need for object model metrics was already suggested in the earliest work on object oriented specification. Convincing work has already been done in the area of measuring static or structural object oriented data. Not too much work has been done in the area of Statechart instrumentation, or more generally, in the area of dynamic or behavioral specification instrumentation. Our work on this page should contribute to this area. Some references are below.

V. Garousi, L. Briand, and Y. Labiche. Control Flow Analysis of UML 2.0 Sequence Diagrams. Technical report, September 2005. Software Quality Engineering Laboratory (SQUALL).
M. Genero, D. Miranda, and M. Piattini. Defining and Validating Metrics for UML Statechart Diagrams. In QAOOSE ’02: Online proceedings of the 6th ECOOP Workshop on Quantitative Approaches in Object-Oriented Software Engineering, June 2002.
G. Poels and G. Dedene. Measures for Assessing Dynamic Complexity Aspects of Object-Oriented Conceptual Schemes. In ER, pages 499–512, 2000.

Versioning Programs And Models

Versioning programs or source code is an industrial practice to keep track of the different versions of software artifacts. With different versions of a software product available to customers, developers can easily loose track of which version of software artifacts belong together. This is why tools are made available that can keep track of changes within software artifacts like source code. Example versioining systems are the commercial Microsoft Team Foundation Server, mainly built for .NET source code and the more Java-oriented and freeware Subversion system. Keeping track of versions of software artifacts cannot be realized without proper tools to compare and merge different versions of the same artifact. This is why it is important to be able to inspect and compare the artifacts based on their syntax and semantics in order to allow tools to automatically store only the difference (or delta) between versions of an artifact in the versioning system. Comparing artifacts based on their syntax and semantics is also important to visualize changes between versions consistently to allow developers to manually merge their artifact versions. Below are some references to versioning systems and also to the current state of affairs in the area of model comparison, which is notoriously more difficult than source code comparison.