It is also well known that the later a bug was found in the development process the more expensive it is to fix it. Several publications exists which displays hockey stick like curves with the development phase on the x-axis and cost per defect on the y-axis.

Here we will not explain statecharts again but focuses on how statechart models can be used to increase software quality in the different development phases.

Why every embedded developer should know statecharts

a) Statecharts allow designing the dynamic behaviour of a device: Parts of an embedded device can be often modelled as state machine due to the reactive nature of embedded devices. Devices react to some kind of external or internal stimuli which leads to an action and, eventually, to a change of state.

b) Statecharts provide a good level of abstraction: Many people with different technical background understand statechart diagrams. This is important because for the development of an embedded system often different engineering disciplines come together. Therefore statecharts are a very good basis to discuss the modelled behaviour or requirements in design reviews with colleagues or customers. Compare the following simple statechart below with the C implementation of it (simplified). The state chart is much easier to understand.

01.07.2009

  switch(instanceVar->stateVar){

  case Running:

      if((msg==(TEST_EVENT_T)stop)){

          stopEngine();

          testChangeToState(instanceVar,Stopped);

    }

    break;

    case Stopped:

        if((msg==(TEST_EVENT_T)start) && (enoughFuel())){

         startEngine();

         testChangeToState(instanceVar,Running);

    }

    break;

}

„The graphical representation of a state machine is a good basis for requirements or design discussions. Also people with no software background do understand them“.

Even for this simple diagram the C-source code is more difficult to understand.

Statecharts are Useful in all Development Phases

Statecharts allow finding defects already in the design phase. To decrease cost of poor quality it is important to find defects as early as possible in the development process. During the design usually defects related to unclear, incomplete or missing requirements are found. Such defects can lead to very costly redesigns or even to the reconstruction of the system if they are found not before the system test. Statecharts open a number of possibilities to find defects early in the process.

a) Statecharts allow simulation of the modelled behaviour: It is easily possible to execute a statechart in a simulator and allow the user to send events to the machine and observe how the statechart reacts to the sent stimuli. This way the user can interactively test the model and improve it where necessary.

1. 
   

b) Robustness of statecharts can be automatically checked on model level: In the hardware design or PCB layout automatic design rule checks are very common. For software designs this is not yet common. Software design rules needs to be defined, hand made checks are time-consuming and the result is very dependent on the reviewer. In practise a tool is needed to ensure that checks are really performed. For UML statecharts the OMG has specified a set of well-formedness rules within the UML specification [4]. These rules as well as a number of additional rules [5] can be automatically performed by the model checker of the sinelabore codgen.

The following list shows some rules:

State related:

1. •State names must be unique and shall conform to a defined naming schema
   (e.g. start with a capital S, must not contain spaces to be a valid C-name)
   

2. •States must be connected by a sequence of transitions outgoing from an initial
   state (connectivity).
   

3. •States should have not only incoming or even no transitions at all (isolated states).
   

4. •Composite states should have more than one child state. If only one child state is
   defined the composition is superfluous and just creates unnecessary complexity.
   

5. •Initial states must be defined on every state hierarchy and must have exactly one
   outgoing transition.
   

6. •Final states must only have incoming transitions.
   

Choice related:

1. •A choice must have only one incoming transition
   

2. •A choice should have at least two outgoing transitions otherwise it is useless
   and should be replaced with a normal transition.
   

3. •Every outgoing transition from a choice must have a guard defined
   

4. •One default transition must be specified for a choice state - i.e. the guard
   is defined as 'else' (default from choice).
   

Some rules seem to be trivial but are nevertheless very useful to check. Other rules are very difficult to check on source code level (if possible at all) but can be easily checked on model level.

The following figure shows a statechart with several defects. Do you find them all? A model checker can find them automatically!

Defects:

1. •The state name of the composite state is missing.
   

2. •There is no default state on the top-level.
   

3. •S2 is not reachable as transitions triggered by the same event (here ev1) but located deeper in the state hierarchy have priority.
   

4. •The two transitions triggered by ev11 leaving S11 are ambiguous as one has no guard defined and the other one has.
   

5. •No default transition leaving the choice state is defined.

c) Automatic code-generation reduces coding errors: Once the statechart was checked the implementation can start. It is highly recommended not to code the statemachine by hand but let a tool generate the code for you. Automatic code generation has many benefits especially if a model checker is integrated in the generator and can perform a large number of checks automatically. Especially composite state charts can be tricky to code by hand. And latest when transitions or states have to be added because of an additional requirement one wishes to have a generator at hand taking over all the error-prone placement of entry, exit and action code associated with states or transitions.

It is important of course that the code generator was developed for the embedded domain. I.e. it produces efficient but readable code which can be understood from the developer. A number of requirements for such a generator were listed in [3].

Automatic code generation does not make source code analysis (SCA) needless. SCA technology has been evolved for more than two decades, and well known tools such as PCLint are used by embedded software developers in virtually every industry. Both model checking and SCA complement each other quite well. It is important to mention that a code generator shall generate code that is not in conflict with used SCA tools.

d) Automatically deriving test-cases from the model: There are several articles about testing state machines, but the one written by Martin Gomez [6] nicely summarizes the usually used approach:

„The beauty of coding even simple algorithms as state machines is that the test plan almost writes itself. All you have to do is to go through every state transition. I usually do it with a highlighter in hand, crossing off the arrows on the state transition diagram as they successfully pass their tests ... This requires a fair amount of patience and coffee, because even a mid-size state machine can have 100 different transitions. However, the number of transitions is an excellent measure of the system's complexity.“

Based on a statechart model the sinelabore codegen can take over this time consuming manual task of defining routes through the statechart ensuring 100% transition coverage. Implementing the test cases is a task that you still have to do. But a good code generator can also support you there by automatically generate trace code if you need it for test purposes or post mortem analysis.

For the trivial example of figure 1 a path with 100% coverage is the following:

Transition Coverage:

0:       From Stopped taking event start[enoughFuel()] ending in Running

1:          From Running taking event stop ending in Stopped

Summary

As you have seen there are many good reasons to create statechart models in your next project and use them throughout the development process. Several good general purpose UML tools exist to efficiently model state machines. It is not recommended to just draw them with a drawing tool. The model can then be used for design reviews, advanced model checking, code- and testcase generation as described above. I strongly vote for automatic source code generation based on the graphical UML model and not creating code directly by hand. This ensures consistency between design and code.

References:

[1] D. Harel, "Statecharts: A Visual Formalism for Complex Systems," www.wisdom.weizmann.ac.il/~harel/SCANNED.PAPERS/Statecharts.pdf

[2] Douglass, Bruce Powel. "Introduction to UML statecharts," Embedded Systems Programming, www.embedded.com/columns/beginerscorner/13900141

[3] Peter Mueller: "Generate efficient statecharts in C using general-purpose UML tools" http://www.embedded.com/design/211200148

[4] Object Management Group,

Unified Modelling Language (UML) 1.3 specification, 2000

[5] Analyzing Robustness of UML State Machines, infoscience.epfl.ch/record/97176/files/ProchnowSBvH06.pdf

[6] Martin Gomez, "Embedded State Machine Implementation" http://www.embedded.com/2000/0012/0012feat1.htm

Statecharts are a well known design method to develop embedded systems. Several articles have been written explaining state machines, their visual representation in UML and how to implement them in different programming languages. For an introduction into statecharts see e.g. [1] and [2].