Ariè Avnur

A Finite State Machine Model for Requirements Engineering

How can the standard UML FSM be improved to better serve the requirements engineer?

Requirement models ‎are used to clarify and improve requirements consistency, unambiguity, correctness and completeness. The finite state machine (FSM) model is very popular with requirement engineers and developers, but all use the same basic model for requirements and implementation. This article presents a layered FSM model—a layer for each development phase, and presents the requirements layer in detail as the requirements engineer’s tool for creating more correct and complete requirements. It also shows how this requirements model can guide design, implementation and testing, creating a requirements-derived development process.

Introduction

Requirement models ‎^[6] are used to clarify and improve requirements consistency, unambiguity, correctness and completeness. Model types used in requirements engineering have visual representation and mathematical rigor; it is up to the requirements engineer to decide which of those two aspects to emphesize more. Some model types define data: entity-relationship diagrams that represent application entities and their relationships; class diagrams represent entities as classes, their data (members), operations (methods), and their inheritance and aggregation relationships (for additional model definitions—see ‎^[6]). Process models include data flow diagrams that define processes (despite the name), their input and output data, how it flows between them and their hierarchical decomposition. Activity diagrams show processes and their temporal—sequential and concurrent relationships, and state transition diagrams or their more mathematical manifestation—finite state machines (FSM, state machine in ‎^[6]), that represent the dynamic behavior of entities in response to events. Here we will focus on that FSM model, examining its power to improve requirements' correctness and drive large parts of the following development steps.

Distinguishing requirements from design is a pervasive subject debated by scholars and development experts (‎^[5] p.195). Typically, where developers perform both requirements analysis ‎^[6] and implementation, there will be less emphasis on the separation of those two system aspects. Where requirement engineers are a distinct group, more effort will be invested in separating requirements from design and implementation. Clear distinction between those two phases is required by regulations in some markets and carries general benefits, giving developers the freedom to design and optimize to clear requirements and requirements engineers to focus on real requirements rather than preconceived design assumptions. UML offers models as tools for requirements and/or design using the same notations for both. We will explore a version of FSM designated specifically as a requirements tool and then see how it affects the other development steps.

Many of the concepts presented here are part of Key FSM—a new conceptual reference FSM model extending UML’s Statechart ‎^[11] ‎^[5], showing that more improvements and concepts can still be added to the FSM and yield more benefits ‎^[1].

The Requirements FSM

FSM’s state definition is often quite general. All too often the state’s name is the only definition used, and we trust it to convey all that the state entails. Sometimes a natural language description is added as part of the documentation. UML’s notation includes state actions: entry, do and exit, but those can be viewed as design elements of the state, since they outline a structure or mechanism.

FSM Layers

In addition to requirements modeling, an FSM is often used for implementation, and since the blueprint of implementation is the design, it should be part of it too. We will indicate later how the FSM model can be used for testing (this subject is out of scope, for more details see ‎^[1]). All those models’ information and code can be structured as a layered FSM and its state as Figure 1 depicts.

At the top – the General Layer, includes:

1. State transitions – diagram or table, defining model’s dynamics.
2. Control structure – the set of all entities or properties that are affected or controlled by the FSM and its states (more details below).
3. States’ general definition – their name and description and attributes.

Next is the states’ requirements layer, detailing the requirements for each state; it is the subject of this work and will be discussed in detail in the following sections. Combined, the general and requirements layers form the requirements FSM (RFSM).

The design layer specifies how the requirements will be implemented; the implementation layer is the FSM's code, and the test layer supports the verification development step. Those layers and how they relate to the requirements layer will be discussed later.

Control Structure

Before focusing on the requirements FSM, it is worth discussing the control structure concept, defined by Key FSM ‎^[1] and referenced by the requirements FSM.

An FSM model is constructed to specify some type of control function: process, behavior or dynamics of data that is sometimes called “FSM output.” We commonly see an output definition of each state virtually as a separate entity—there is nothing in the model itself that binds states’ output and “keeps it all together.” Key FSM adds this element—the control structure. It specifies system elements controlled or affected by the FSM, reducing error risk by requiring ALL states to define control structure values, improving the accuracy and correctness of requirements and the FSM as a whole.

Two types of control structure are defined:

1. Entities – A list of actors and records and their properties that are controlled by the FSM. Often only one such entity is controlled by a specific FSM, but more are possible. Each of the states must explicitly define some condition over each of the controlled entities, even if it is only “no change” or “no effect” — documenting the rationale for those decisions makes them conscientious and the whole model more accurate.
2. Control variables – a set of variables or properties (record fields) controlled by the FSM or said to be the FSM’s output. Each of the FSM states must define a value for those variables, and the reasons for those values documented. The advantages of using this type of control structure will be explored later.

The control structure defines the scope over which the FSM has control; at the design and implementation layers, it is translated into actual objects, records and fields that are manipulated or set by the FSM.

The requirements layer

This layer contains the states’ requirements specifications over the control structure and it may take one of the following three forms:

Requirement statements. Use a notation standardized for the project, product or organization to specify state requirements. These could be user stories, EARS notation ‎^[7], the standard “X shall do Y” or any other. These statements express system requirements for each state, but note that they should referece the FSM’s control structure. If at one state we need to specify a requirement relating to entities beyond the control structure, those have to be added to the control structure, and the rest of the states have to reference it as well.

Control variable values. If the FSM’s control structure comprises only simple variables, we need to specify their value at each state and nothing more. We also document the reasoning for the specified value. Examples will be: (a) session FSM—sets the session’s “authenticated” variable to true or false depending if logged in or out; and set the time of entering the logged-in state (for session expiration), (b) a cruise control system’s FSM, as in the example described later on, controls a few variables: boolean controlOn, real setPoint, boolean accelerating, and a few other optional boolean variables to control indications on the instruments panel.

State invariant. This form of state requirements uses a logic expression over the control structure that must evaluate “true” in the state. E.g. for a session FSM:

authenticConfidenceLevel(actualUser, user(loginName)) > C1; where the authenticConfidenceLevel and user(LoginName) functions, as well as the threshold C1 are defined. Note that this will require performing an authentication function on the session’s user—one, two or three factors depending on C1, on password complexity, etc. – that will all be part of the design, aimed at satisfying the state invariant.

Whichever requirement's notation we choose, we end up with an FSM that specifies pure requirements and their dynamics (how they change in response to events).

Requirements FSM in the Requirements Process

Figure 2 depicts the process steps involved in creating and modeling requirements with RFSM using a DFD-like diagram (dataflow diagram, ‎^[6], ‎^[10]). Elicitation meetings (i) produce SME (subject matter expert) statements that are “raw requirements.” Those are analyzed (ii) to produce draft requirements and optionally, when needed, a requirements model. An FSM is most often the choice to model dynamic behavior, process and status of application entities. And since we are dealing with requirements, RFSM can be used. (When we model requirements with an FSM and strictly limit states to represent system requirements and not design—we get RFSM de-facto.) The requirements engineer should analyze the RFSM (iii) using rules, techniques and tools designed specifically to evaluate FSM’s integrity. This analysis usually produces a list of flaws; some can be resolved by correcting draft requirements and others require going back (3) to elicitation to complete missing information or resolve conflicts. After all model analysis errors are resolved, the process moves (4) to the final review (iv). SME’s may provide additional corrections that may require going back and analyzing the model (iii) to keep its integrity. When a review passes, the requirements lose their draft status and become official. The final model (b) in its tabular form (states and state transition tables) and/or its graphical representation (state transitions diagram) is usually included in the requirements (a), specifying dynamic process or behavior that in many cases would otherwise be too complex to specify and comprehend. An additional benefit of the model is the analysis step (iii) that helps uncover hidden flaws, improving requirements quality.

FSM Analysis

An FSM model can be validated by structural and semantic rules (‎^[1] sections IV–F and IV-G). Static and structural rules check states to be reachable, have transitions out of the state (except for terminal states), timeout, and more, and can be applied to the model directly. Semantic rules require symbolic processing, or can be tested at run-time. One rule in particular (4 - Complete transition definitions) requires a whole process to be evaluated – the event-state analysis (ESA).

Event-state analysis verifies the complete definition of the state transitions mapping function (states X events → state) that is part of the formal finite automaton and FSM definition (∂ in ‎^[3]). A concise state transitions table form—rows representing states, columns and cells contain the next state guide the analyst in defining this function, is depicted by Table 1:

In many practical cases however, the number of states and events is too high for this form, and other forms are used (see ‎^[1]). The process checks all events against all states systematically and domain knowledge is used to add transitions and confirm where transitions are not needed, and documenting rationale for future maintenance that may require those decisions to be revisited. This simple process yields many additional transitions and sometimes new states. Combined with states’ timeout, it practically guarantees that “forgotten” transitions will be added. Performed rigorously, it achieves model completeness and thus contributes to its correctness.

FSM and exceptions

Exceptions that are visible and the handling of which makes a difference to actors and stakeholders (and those constitute most of the exceptions) have to be specified at the requirements level. Most exceptions require deviation from the interaction path and can be viewed as events that trigger transitions to different states, diverting the process from the nominal path. No behavior or process model is complete, and therefore correct, without modeling such visible exceptions. Most FSM models however ignore exceptions, leaving the issue to the implementation level, where the risk of changing the design and handling them in an undesired way is high. It is therefore required to include exceptions in the requirements model. Key FSM adds exceptions as state specific events. How those exceptions are identified is beyond the scope of this paper (for more details see ‎^[1] section IV-A-10). Identifying exceptions is part of the first step of the event-state analysis—identify all relevant events.

Cruise Control System Example

Next, let’s examine the benefit of using RFSM using an excerpt from a detailed example published with Key FSM ‎^[4]. Note that this was not meant to be a real cruise control design; that will be somewhat more complex, it is intended only to demonstrate the use of requirements FSM.

User stories from first elicitation, and predicate statements (summarized facts studies by requirements engineers, and considered “ground truth”) are:

And the FSM that can be constructed from these requirements:

This FSM is then analyzed according to the Key FSM integrity rules and the event-state analysis - ESA, producing the revised state-transition table (too long to be included), and state-transition diagram:

Some comments on this result (see the full example for a complete discussion):

1. ESA could have also been used to construct the FSM from scratch, here we started with draft or baseline FSM version as is the often the case.
2. A couple of the added transitions have safety implications; e.g. stopping speed control when brakes are applied. In general, ESA produces a complete FSM and that is critical in safety-related applications.
3. The rationale for all event responses is documented (see the full example); this is useful in case changes are required.

Beyond requirements

Requirements are the means for correct and successful product development, and as such they are the input for “downstream” development phases. In closing, we will explore how the requirement FSM affects the development phases that follow it.

Requirements to Design

Two types of system elements are commonly modeled by an FSM: a process that switches between well-defined steps or states, and a variable that represents a state.

A common and simple design choice for a process modeled by an FSM is a dedicated module that will run an implementation of the requirements FSM—FSM1 in Figure 5. To justify this design, consider that the requirements FSM specifies a set of states and what the system is required to do at each state. Running an equivalent FSM and having its states create the conditions specified by the requirements layer is a straight-forward design that meets the requirements. This solution is the most common design choice. Figure 5-(a) illustrates this mapping of the FSM model from requirements to design.

A basic assumption here is that the events’ set specified by the requirements FSM is also the set of events that applies to the implementation. This is often the case because otherwise the requirements represented by the RFSM are not accurate. Events that are considered minute details, not important at the requirements level, are omitted from the requirements model and included only at the design and implementation levels. Both experience and logic show that those added events just add new states, or even whole sub-FSM’s, but the original sets of states and transitions still apply to the implementation and therefore the design. The requirements FSM can then still be applied to the design, but some events and states may need to be added. For additional discussion of this assumption see ‎^[1].

The other case of using an FSM model is a class’s member variable (or actually any variable) defined as derived from an FSM state; e.g. an enumerated type that represents the state. See Figure 5-(b) “member 2” variable. This is the case of most “status” variables. E.g. an account status, can be defined as the state of an FSM that defines how the status reacts and changes with various events. In this case a straight-forward design solution is to implement the FSM, and define the status variable (like member 2) as a control variable of that FSM (FSM2 in Figure 5 (b)).

The cruise control example used above can demonstrate this requirements-to-design mapping concept as illustrated in

The design layer

Using the requirements layer as a reference, the design layer specifies how the requirements as specified by the requirements layer will be implemented, using a design specifications text and diagrams. A more structured way is to use the entry, do and exit actions structure, and to specify those actions for each state, so they implement the requirements layer for the state. Table 2 describes the general functionality of those actions for the various types of state requirements.

As we can see, the case of specifying states’ requirements by control variable values is special—only simple entry and do actions are needed to set the required control variable values. Key FSM ^[1], the model that implements the layers described here, takes this case even further and its “FSM Engine” (see implementation below) identifies this case and sets the values from the FSM definition, eliminating the need for any states’ action. This could actually be considered a design pattern and Figure 7 depicts such a design for our cruise control example, while Table 2 outlines how the state actions for that example change the control variables.

Implementation

An FSM can be implemented by writing transitions code: two level nested switch statements, calls to the entry and exit actions and control of the task that performs the do action periodically. However, for complex notation like the hierarchical, multi-zone, features rich Statechart, this is an impractical approach. A more common implementation is that of a code generator; a kind of compiler that generates code from the FSM definition, like the FSM compiler ‎^[8]. State actions are the main application code written by developers. A third implementation type is that of the FSM engine—a module or class that instantiates an FSM object derived from the FSM’s definition that can be written as an XML file ‎^[1].

The choice of FSM Engine implementation and control variables is interesting in particular: it leaves very little application code. E.g. the Control and Accelerating tasks of the Cruise Control example that are pure application code.

Test

Coming up with an exhaustive set of test cases is often a challenge. With an FSM model, we can generate productions that are strings of events and the sequences of states they create. These can be translated into test scenarios: the events string is an input sequence and the corresponding states strings specify the required output as defined by the requirements layer’s specifications.

Summary and Conclusions

We saw how FSM states can contain multiple layers and how the requirement layer can specify what is to happen in the state, forming a requirements FSM. We showed how it can be used in the requirements engineering process, detecting missing and conflicting requirements, leading to better and more correct requirements. We then showed how design and implementation can be derived from such a model, automatically in some cases, and pointed out how test scenarios can be generated from the model. This process creates a requirements-derived system implementation from start to end.

References

• [1] A. Avnur, Key FSM, http://www.aa-sw-dev.com/KeyFSM/KeyFSM.htm (or: http://www.aa-sw-dev.com/KeyFSM/KeyFSM.pdf)
• [2] A. Avnur Finite State machine for real-time software engineering, IEE Computing & Control Engineering Journal, Nov. 1990, pp 273.
• [3] Stanford University, Basics of Automata Theory, http://cs.stanford.edu/people/eroberts/courses/soco/projects/2004-05/automata-theory/basics.html
• [4] Cruise control FSM requirements modeling, http://www.aa-sw-dev.com/KeyFSM/Cruise%20control%20requirements%20FSM.htm
• [5] D. Harel, Statecharts: A Visual Formalism for Complex Systems, Science of Computer Programming, 8 (1987), 234-274.
• [6] IREB Glossary, http://www.ireb.org/fileadmin/IREB/Download/Homepage%20Downloads/IREB_CPRE_Glossary_16.pdf
• [7] Mavin, A. at al, Easy Approach to Requirements Syntax (EARS), Requirements Engineering Conference, 2009. RE '09. 17th IEEE International.
• [8] SMC – The States Machine Compiler, http://smc.sourceforge.net
• [9] University of Toronto, Dept. of Computer Science, Requirements Modeling Lecture, slide 5, http://www.cs.toronto.edu/~sme/CSC340F/slides/09-modelling.pdf
• [10] Karl E. Wiegers, Software Requirements, Microsoft Press, 2nd Edition.
• [11] Wikipedia, UML State machine