EPSRC logo - link to webpage University Crest - link to university homepage SourceForge.net Logo

StateChum

Introduction

Statechum is a framework that implements a number of regular grammar inference algorithms. Regular grammars can be represented as finite state machines. Once the grammar / state machine has been generated, StateChum can visualise it, and provides a selection of state-machine analysis and testing algorithms.

The original purpose of the framework was to investigate the application of grammar inference to the problem of reverse-engineering state machines from execution traces. It also contains code to generate test sets using the W method and methods for random trace generation.

It is possible to introduce domain-specific constraints using LTL or by directly encoding them in automata. This makes inference significantly more effective because the learner does not need to make "guesses" in many cases.

Random FSM generator implemented in this tool was built to generate finite-state machines with structural properties similar to machines published in Software Engineering literature. It has been used to generate samples for the Stamina grammar inference competition.

Graph comparison effectively computes a "diff" between arbitrary directed graphs by using language measure to match states. Finite-state machines can also be compared using precision/recall or BCR scores. Graphs can be visualised using the R tool and dynamically updated in the course of analysis.

Recent work involves integration with Erlang in order to perform automated inference of Erlang software. This is made possible by the Typer engine which generates types of Erlang functions hence making it possible to automate trace generation for the inference process.

The framework has been primarily used as a proof-of-concept for a number of ideas, and was not originally intended for widespread use. One of the main challenges now is to make it available to the wider community, and to provide interfaces that make it more usable. It is currently an alpha release; we are currently considering making it available as an Eclipse plugin.

To download the software, go to the SourceForge project page, which also provides a forum for questions / suggestions.

References

These are available from two places,
For further references refer to the AutoAbstract Project page (link also mentioned on the right-hand column).

Links

SourceForge Project page.
AutoAbstract Project page at the University of Sheffield.
Introduction to Grammar Induction (H. Curien laboratory at Universite Jean Monnet).
Flash demo of active induction

Related Software

Note: Statechum depends on the following software.
ProjectWhere used in Statechum
JUNGGraph manipulation and visualisation.
Automatically Tuned Linear Algebra Software and UMFPACK: LU factorisation of sparse matricesStructural state comparison.
JRI - Java/R Interface and JavaGD - Java Graphics DeviceUsed to display R graphs in Swing windows.
Eclipse TPTPExtraction of dynamic information.
SOOTStatic analysis.
LTL2BAConversion of user-specified properties to Buchi automata for checking properties using Spin (below).
SPINChecking that automata being constructed satisfies user-specified properties.
Parts of Erlang such as modified typer Automatic inference of Erlang software using type information from Typer.