MeasuringStateMachineComplexity

Introduction

We want to be able to measure state machines complexity in order to:

• categorize: determine reference values and thresholds, ranking them in complexity levels. We consider that ranking activity could be impossible or too much harder, so the feasibility will be under focus throught this process;
• decrease the complexity level: map state machine umple from N states (transitions, guards,...) to (N-k) states (transitions, guards). A state machine that might be read easily might be harder to execute than its simplified model. Having regarded state machines can be designed as nested/hierarchical/ state machines,the reduction of complexity could be worthy;
• catalog: catalog richness and diversity of state machines and their features.

What means complexity?

It's hard define complexity, but we can state that as higher a complexity is harder is achieve the goal expected. So, if we consider OO code or model, for instance, we could consider coupling, cohesion, size, readability, usability, maintainability and so on to define complexity. We focus our investigation on maintainability, which doesn't become our work easier. Maintainability can be describe as a function of size, readability and others as well. Despite of that, we will start the investigation in this direction, "maintainability", keeping in our minds that we can enlarge or reduce our focus "on the fly" in accordance with results gathering.

Elements of State Machines and some Properties

Elements and characteristics:

• state: A State models a situation in the execution of a StateMachine Behavior during which some invariant condition holds. In most cases this condition is not explicitly defined, but is implied, usually through the name associated with the State. For example, the behavior of a telephone unit, the states “Idle” and “Active” represent situations where the telephone is and is not being used, respectively.
• finalstate: A special kind of state signifying that the enclosing composite state is completed. If the enclosing state is the top state, then it means that the entire state machine has completed.
• transition: A transition is a directed relationship between a source state vertex and a target state vertex. It may be part of a compound transition, which takes the state machine from one state configuration to another, representing the complete response of the state machine to a particular event instance.
• event: An event is a specification of a type of observable occurrence. The occurrence that generates an event instance is assumed to take place at an instant in time with no duration.
• guard: A guard is a boolean expression that is attached to a transition as a fine-grained control over its firing. The guard is evaluated when an event instance is dispatched by the state machine. If the guard is true at that time, the transition is enabled, otherwise, it is disabled.
• actions:
  • entry
  • doActivity
  • exit
• compositeState:
• Pseudo-state:
  • initial
  • deepHistory
  • shallowHistory
  • join
  • fork
  • junction
  • choice
• syncState: A synch state is a vertex used for synchronizing the concurrent regions of a state machine. It is different from a state in the sense that it is not mapped to a boolean value (active, not active), but an integer. A synch state is used in conjunction with forks and joins to insure that one region leaves a particular state or states before another region can enter a particular state or states.
• self cycle: A transition from one state to itself.
• cycle: A transition from one state to itself with one or more states in the path from state up to return it again. The concept of cycles don't accept state repetition in the path.
• nested state machines:

Properties:

• CompositeState:
  1. A composite state can have at most one initial vertex

2. A composite state can have at most one deep history vertex
3. A composite state can have at most one shallow history vertex
4. There have to be at least two composite substates in a concurrent composite state.
5. A concurrent state can only have composite states as substates.
6. The substates of a composite state are part of only that composite state.

• FinalState:
  1. A final state cannot have any outgoing transitions.
• Guard:
  1. A guard should not have side effects.
• PseudoState:
  1. An initial vertex can have at most one outgoing transition and no incoming transitions.

2. History vertices can have at most one outgoing transition.
3. A join vertex must have at least two incoming transitions and exactly one outgoing transition.
4. All transitions incoming a join vertex must originate in different regions of a concurrent state.
5. A fork vertex must have at least two outgoing transitions and exactly one incoming transition.
6. All transitions outgoing a fork vertex must target states in different regions of a concurrent state.
7. A junction vertex must have at least one incoming and one outgoing transition.
8. A choice vertex must have at least one incoming and one outgoing transition.

• StateMachine:
  1. A StateMachine is aggregated within either a classifier or a behavioral feature.

2. A top state is always a composite.
3. A top state cannot be directly contained in any other state.
4. The top state cannot be the source of a transition.
5. If a StateMachine describes a behavioral feature, it contains no triggers of type CallEvent, apart from the trigger on the initial transition (see OCL for Transition 8).

• SynchState:
  1. The value of the bound attribute must be a positive integer, or unlimited.

2. All incoming transitions to a SynchState must come from the same region and all outgoing transitions from a SynchState must go to the same region.

• SubmachineState:
  1. Only stub states allowed as substates of a submachine state.

2. Submachine states are never concurrent.

• Transition:
  1. A fork segment should not have guards or triggers.

2. A join segment should not have guards or triggers.
3. A fork segment should always target a state.
4. A join segment should always originate from a state.
5. Transitions outgoing pseudostates may not have a trigger.
6. An initial transition at the topmost level either has no trigger or it has a trigger with the stereotype "create.”

Considerations throught measuring process

• Determine direct measures: at beginning, direct features should be determine. Those features are assigned to elements seen like components of state machine diagram. for instance, we could measure total of states, transitions, guards, events, cycles, selfcycles, deephistories, nested machines and so on. After determining those totals, we could:

a)determine some known operations like media, median, max, min, quartiles, and so on. b)determine correlations between those elements.

• Determine indirect metrics: indirect metrics make sense if we have abstract concepts to measure. It's possible associate abstract concepts like complexity to state machines. For instance, initially, some metrics like McCabe Complexity (cyclomatic complexity) and halstead's metric could be adapted and verified.

Simple counts

• Number of states
• Number of transitions
• Number of events
• Number of guards
• Number of cycle
• Number of selfcycle
• Number of nested state machine

For each state

• Fan in (incoming transitions)
  • Simple (directly connecting to the state)
  • Full (accounting for transitions via superstates)
• Fan out (outgoing transitions)
  • Simple (directly connecting to the state)
  • Full (accounting for transitions via superstates)
• Entering rate (incoming events / total of events)
• Exiting rate (outgoing events / total of events)
• Keeping rate ( events - (incoming and outgoing events)/total of events)
• Number/Complexity of actions/activities (entry, exit and do)
• Complexity of substates (recursively)

For each transition

• Complexity of guard (operators and operands, nesting)
• From states to states (considering nesting)
• Number/Complexity of actions
  • Simple (directly attached)
  • Full: Executed when the transition taken, including entry and exit from super/substates

Nesting

• Deepest level of nesting
• Average level of nesting, considering all the states

Graph theoretic

• Number of possible paths
• Number of possible cycles
• Disconnected units
• Linearity/cyclicity
  • Number of cycles / cyclomatic complexity
  • Number of cycles, not considering directedness of the graph

For each action

• Simple: setting a variable or sending a message or triggering an event only
• Complex: Arbitrary code

Categorizing state machines as Mealy vs. Moore

• Pure Mealy: Actions are simple and are on transitions
• Pure Moore: Actions are simple and are entry actions in states
• Hybrid Mealy/Moore: Actions are simple but could be on transitions and states
• Complex: Some actions are not simple

Interesting outputs from state machines

Transition table, keyed by event, or keyed by state (resolving nesting)

BIBLIOGRAPHY

• OMG Document Number: ptc/2012-10-24. OMG Unified Modeling Language (OMG UML). October 2012.. Version 2.5 Beta 1. Version 2.5 is a minor revision to the UML 2.4.1 specification. http://www.omg.org/spec/UML/2.5/Beta1