Formal derivation of finite state machines for class testing

Previous work on generating state machines for the purpose of class testing has not been formally based. There has also been work on deriving state machines from formal specifications for testing non-object-oriented software. We build on this work by presenting a method for deriving a state machine for testing purposes from a formal specification of the class under test. We also show how the resulting state machine can be used as the basis for a test suite developed and executed using an existing framework for class testing. To derive the state machine, we identify the states and possible interactions of the operations of the class under test. The Test Template Framework is used to formally derive the states from the Object-Z specification of the class under test. The transitions of the finite state machine are calculated from the derived states and the class's operations. The formally derived finite state machine is transformed to a ClassBench testgraph, which is used as input to the ClassBench framework to test a C++ implementation of the class. The method is illustrated using a simple bounded queue example.

Checking Completeness of Tests for Finite State Machines

In testing from a Finite State Machine (FSM), the generation of test suites which guarantee full fault detection, known as complete test suites, has been a long-standing research topic. In this paper, we present conditions that are sufficient for a test suite to be complete. We demonstrate that the existing conditions are special cases of the proposed ones. An algorithm that checks whether a given test suite is complete is given. The experimental results show that the algorithm can be used for relatively large FSMs and test suites.

A finite state model for on-line analytical processing in triadic contexts

About ten years ago, triadic contexts were presented by Lehmann and Wille as an extension of Formal Concept Analysis. However, they have rarely been used up to now, which may be due to the rather complex structure of the resulting diagrams. In this paper, we go one step back and discuss how traditional line diagrams of standard (dyadic) concept lattices can be used for exploring and navigating triadic data. Our approach is inspired by the slice & dice paradigm of On-Line-Analytical Processing (OLAP). We recall the basic ideas of OLAP, and show how they may be transferred to triadic contexts. For modeling the navigation patterns a user might follow, we use the formalisms of finite state machines. In order to present the benefits of our model, we show how it can be used for navigating the IT Baseline Protection Manual of the German Federal Office for Information Security.

Comparing finite state machine test coverage criteria

To plan testing activities, testers face the challenge of determining a strategy, including a test coverage criterion that offers an acceptable compromise between the available resources and test goals. Known theoretical properties of coverage criteria do not always help and, thus, empirical data are needed. The results of an experimental evaluation of several coverage criteria for finite state machines (FSMs) are presented, namely, state and transition coverage; initialisation fault and transition fault coverage. The first two criteria focus on FSM structure, whereas the other two on potential faults in FSM implementations. The authors elaborate a comparison approach that includes random generation of FSM, construction of an adequate test suite and test minimisation for each criterion to ensure that tests are obtained in a uniform way. The last step uses an improved greedy algorithm.

Landscape state machines: Tools for evolutionary algorithm performance analyses and landscape/algorithm mapping

Many evolutionary algorithm applications involve either fitness functions with high time complexity or large dimensionality (hence very many fitness evaluations will typically be needed) or both. In such circumstances, there is a dire need to tune various features of the algorithm well so that performance and time savings are optimized. However, these are precisely the circumstances in which prior tuning is very costly in time and resources. There is hence a need for methods which enable fast prior tuning in such cases. We describe a candidate technique for this purpose, in which we model a landscape as a finite state machine, inferred from preliminary sampling runs. In prior algorithm-tuning trials, we can replace the 'real' landscape with the model, enabling extremely fast tuning, saving far more time than was required to infer the model. Preliminary results indicate much promise, though much work needs to be done to establish various aspects of the conditions under which it can be most beneficially used. A main limitation of the method as described here is a restriction to mutation-only algorithms, but there are various ways to address this and other limitations.

Subsystem Testing of Message Guided State Machines Using a Simulator Framework

Simulaattorit ovat yksinkertaistettuja malleja tietyistä järjestelmän osioista. Niitä käytetään mallintamaan testattavan osion ympärillä olevien muiden osioiden ulkoista toimintaa, jotta testattavalle osiolle saadaan oikeanlainen toimintaympäristö aikaiseksi. Tilakoneita käytetään mallintamaan ohjelmistojen tai niiden osien toimintaa. Sanomaohjatuissa tilakoneissa tilojen vaihdot perustuvat saapuviin sanomiin. Tässä työssä esitellään erään ohjelmiston alijärjestelmän testaamisessa käytettävä arkkitehtuuri, joka perustuu suurelta osin simulaattoreiden käyttöön muiden alijärjestelmien mallintamisessa. Testattava ohjelmisto koostuu enimmäkseen tilakoneista, jotka vaihtavat keskenään sanomia ja ohjaavat näin toistensa tilasiirtymiä. Työn testausympäristö on suunniteltu juuri tämänkaltaisen ohjelmiston testaamiseen. Työssä esiteltävää testausympäristöä myöskin käytettiin useamman kuukauden ajan ja se todettiin toimivaksi. Joitakin testausympäristön käyttöohjeita, käyttökokemuksia sekä siihen liittyviä parannusehdotuksia käydään läpi työn loppuosassa. Erityisesti havaittiin miten tärkeää on testata implementaatiota jo luokka tasolla ennen alijärjestelmä tason testaukseen siirtymistä sekä päädyttiin siihen, että suunnitteluvaiheen pitäisi olla lähemmin liitoksissa alijärjestelmätestaukseen.

Time Reversibility of Stationary Regular Finite State Markov Chains

We propose an alternate parameterization of stationary regular finite-state Markov chains, and a decomposition of the parameter into time reversible and time irreversible parts. We demonstrate some useful properties of the decomposition, and propose an index for a certain type of time irreversibility. Two empirical examples illustrate the use of the proposed parameter, decomposition and index. One involves observed states; the other, latent states.

Modeling of state machines in VHDL for encapsulation of DNP3 Protocol in P2P ZigBee Network

Several countries have invested in technologies for Smart Grids. Among such protocols designed cover this area, highlights the DNP3 (Distributed Network Protocol version 3). Although the DNP3 be developed for operation over the serial interface, there is a trend in the literature to the use of other interfaces. The Zigbee wireless interface has become more popular in the industrial applications. In order to study the challenges of integrating of these two protocols, this article is presented the analysis of DNP3 protocol stack through state machines The encapsulation of DNP3 messages in P2P (point-to-point) ZigBee Network, may assist in the discovery and solution of failures of availability and security of this integration. The ultimate goal is to merge the features of DNP3 and Zigbee stacks, and display a solution that provides the benefits of wireless environment, without impairment of security required for Smart Grid applications.