StaMInA: A Novel Competition to Drive the Comparative Evaluation of State Machine Inference Approaches

Lead Research Organisation: University of Sheffield
Department Name: Computer Science


Software systems pervade modern life; they control everything from fly-by-wire aircraft and financial transfer systems to ABS breaking systems in cars and cooking modes in microwaves. The ability to understand these complex systems, and to make sure that they behave as expected, is crucial. State machines are a formal, diagrammatic notation that can be used to visualise behaviour of these systems in an accessible way. They can also be used as a basis for several rigorous and automated testing and verification techniques.Currently, state machines have to be designed and maintained by hand. This is an expensive and error-prone task, particularly when the system in question is constantly subject to change. Faced with this challenge, a substantial amount of research has been devoted to solving this problem with automated techniques; to automatically infer state machines of software systems, usually from samples of their behaviour. This has resulted in a multitude of proposed solutions from groups around the world.Although these advances are welcome, they have given rise to an important problem: There is no accepted process by which these techniques can be evaluated and compared against each other. There is no evidence to indicate which technique is better than the others, and why certain techniques excel. This in turn hampers further research in the area.With this project, we will address the above problems by organising an international competition to thoroughly compare and evaluate a diverse range of state machine inference techniques. The competition is especially novel because it will employ a range of techniques to compare the results of different techniques against each other. This will identify (a) which techniques are the most effective ones and (b) shed light on the possible reasons for their effectiveness. It is envisaged that this competition will become a regular event, driving research in the area.
Description Software is a foundation of many existing systems, such as cars, telephones and aircraft.
In this project, a competition was run between different techniques to infer models of software, based on finite-state machines. The aim was to get different inference approaches to compete on learning FSMs like those found in Software Engineering literature. The winning algorithm was able to learn well from half as much data as the best previously-known algorithm.
Exploitation Route The novel technique that emerged from the competition funded by this grant may be useful to both software developers and software development tool builders. Results of the work have appeared in an open-access article STAMINA: A Competition to Encourage the Development and Assessment of Software Model Inference Techniques, in Empirical Software Engineering journal. This is expected to be read by practicing software engineers.
Sectors Aerospace

Defence and Marine

Digital/Communication/Information Technologies (including Software)


Description The winning algorithm formed the basis for several initiatives by its inventor in the Netherlands in a cyber-security context on two prestigious CWI-funded research projects in conjunction with the Dutch national cyber-security centre. The competition site continues to be a valuable resource long after the end of the competition: in three years to October 2014 the site has attracted 1368 sessions from 990 different IP addresses, from 70 different countries.
First Year Of Impact 2013
Sector Digital/Communication/Information Technologies (including Software)
Impact Types Economic

Description Pierre DuPont 
Organisation Catholic University of Louvain
Country Belgium 
Sector Academic/University 
PI Contribution The Grammar inference competition funded by this grant was a joint work between Sheffield and Université catholique de Louvain, Belgium.
Collaborator Contribution The Grammar inference competition funded by this grant was a joint work between Sheffield and Université catholique de Louvain, Belgium.
Impact Research outputs are described in the Publications section and impact on society in the Narrative Impact
Start Year 2008
Title Statechum 
Description This tool implements the inference method developed as part of AutoAbstract and REGI research grants. 
Type Of Technology Software 
Year Produced 2007 
Open Source License? Yes  
Impact Was reimplemented by Quviq (Swedish SME) and contributed to their significant growth.