July 9, 2013

329 Views

Modeling Techniques

Building a Strong Foundation for Model-Based Testing

A model is an abstract and pictorial presentation of the functional behavior of an SUT (system under test). The ideal model notation would be easy for testers to understand, describe a large problem as easily as a small system, and still be parsed by a test-generation tool. Reconciling all these goals is difficult, and thus there is no one modeling language for all purposes, which implies that several notations may be required. Ideally, the data model can be generated from some representation of the requirements.

There are a number of software model notations used in current software model-based test tools automation. Identifying the right model notation to depict the system behavior and using it to right details is a very important part of model-based testing.

This section summarizes some of the popular modeling techniques. They are: finite state machines, state charts, UML (Unified Modeling Language), and Markov chains. Some other models are grammar models, decision tables, decision trees and abstract machine notation.

Finite State Machines

The finite state machine model is a well-known dynamic model for software design and testing. It can be very effective to present the state-based behaviors of a software system and related processes. A finite state machine consists of a set of all possible states of the system, the transitions that transform a system from one state to another and a set of final states in which the system can end up. The entire lifecycle of the system is represented in terms of states and transitions. The state that a system is in at any point in time is known as current state.

The easiest way and norm to draw an FSM (finite state machine) is to draw a circle for every state, and arrows to show the transitions between two states. For example, the finite state machine in the diagram below has three states. If the machine is in state 1 then transition/event “A” moves it to state 2 or transition/event “B” moves it to state 3. The machine will come back to state 1 on occurrence of transition/event “C” over state 2.


A three-state finite state machine

The major restriction in using the FSM model is that the number of states must be finite, and so must the number of transitions. Generally, this model is easy to design and maintain as long as the system in question is low in terms of complexity. As system complexity grows, the model becomes exceptionally hard to design and maintain. In addition, because finite state machine does not allow for concurrency, this model cannot be used for concurrency modeling.

State Charts

A state chart is also referred to as “Harel statechart,” based on name Harel, who created this variation of finite state machine. It is basically a finite state machine developed specifically for testing of complex and real-time software systems, where concurrency and behavioral sequences need to be depicted. Its most notable feature is the ability to represent a state hierarchically, wherein a particular state can be decomposed into one or more lower level finite state machines. This feature is especially helpful in generalizing the states by grouping the common/shared states, and thus eliminating the diagram explosion problem that a typical finite state machine faces. This notation also provides a history mechanism to remember information of the state when it was last visited.

Statechart diagrams are now a part of the standard UML specification. Although improved over the true finite state machine, state charts are still hard to design and maintain for complex software systems. Also it requires very diligent skills in deploying the model. Compared with the conventional finite state machines, state charts provide special advantages in presenting both sequential and concurrent software behaviors in a hierarchical way.


State Chart Model

For example, a conventional state machine with states – Active, Standby, Suspect and Defective – and many different input messages is shown here. In a simple finite state machine model, this will lead to a message handler code explosion due to numerous combinations of states and messages. The state chart machine shown above captures the commonality by organizing the states as a hierarchy. The child states at the lower level inherit the functionalities from the upper level, and thus eliminate the state-transition explosion problem.

Markov Chains

A Markov chain, named after Andrey Markov, is a finite state machine with probabilistic state transitions. The current state along with the probability of possible transitions to occur at any point in time is the only factor to determine next state and the history of past states does not influence any transition.

The changes of state are called transitions, and the probabilities associated with various state changes are termed transition probabilities.

Markov chains are often modeled using a directed graph, where the transitions are labeled by the probabilities of going from one state to other states. Markov chains are structurally similar to finite state machines, and can be thought of as probabilistic FSM. Its main advantages over conventional FSM are in gathering data and analyzing the reliability to provide failure rate distributions and test coverage.
An example of a network connection is represented by the Markov chain show below. The basic task in building this model is to identify the states of the system and the possible transitions among those states with the probability of occurrence.


Example of Markov Chain

UML

UML (Unified Modeling Language) is one of the most widely used modeling languages to depict the big picture, business processes, static components and dynamic behavior of the system. Built on the basic principle of object oriented concepts, it provides a foundation to model-driven engineering. It uses XML at the root to capture model information, which makes it easy to use and import across tools. It has a plethora of notations which gives flexibility to model any system as needed, irrespective of platform or technology. So, for practical model-based testing, it is necessary to select a subset of UML which best represents the system under test. The data part of the model is generally defined using class and instance diagrams and the dynamic behavioral aspect of the model is represented using use case, activity or state chart diagrams.

The UML models used for test generation must have a precise and unambiguous meaning so the behavior of those models can be understood and manipulated by the test generator. This precise meaning also makes it possible to use the model as an oracle, either by predicting the expected output of the SUT, or checking the actual output of the SUT against the model.

Other Models

Many other model notations are being used for creating models, but are not as popular. Some of those include:

Abstract Machine Notation (AMN) – The abstract machine notation is a specification language and an abstract programming language for specifying abstract machines in the B method, based on the mathematical theory of generalized substitutions.

UML OCL (Object Constraint Language) – OCL is a language that allows the user to add additional information to UML models. It is used to define constraints, attributes and variables to the model elements. Attaching OCL constraints to UML models makes those models communicate unambiguously.

Decision Table Model – It is modeled in a table format with four quadrants listing conditions/inputs, actions/outputs, alternatives and action entries. It is very effective in representing combinational systems.

Applicability

  • Finite-state machines are most appropriate for state rich systems such as telephony
  • State charts models are effective for systems with few states or hierarchical structures, transitions caused by user input and external conditions
  • Markov chains are used where statistical analysis, failure data, or reliability assessments are desired.Read more about HCL's global IT solutions, here.

References

https://en.wikipedia.org/wiki/Finite-state_machine
http://en.wikipedia.org/wiki/State_diagram
http://www.benmeadowcroft.com/reports/statecharts/
http://en.wikipedia.org/wiki/Unified_Modeling_Language
http://en.wikipedia.org/wiki/Markov_chain
http://en.wikipedia.org/wiki/Object_Constraint_Language
http://en.wikipedia.org/wiki/Decision_table

You can follow us on Twitter @hclers for more updates about HCL ERS

Visit us for more Engineering Blogs!