Project Summary

Research Summary

Humans often manage to learn the behavior of a device or computer program by just pressing buttons and observing the resulting behavior. Especially children are very good in doing this and know exactly how to use a game computer, iPod or microwave oven without ever consulting a manual. In such situations we construct a mental model of a state diagram: we determine in which global states a device can be and which state transitions and outputs occur in response to which input. This research proposal deals with the design of algorithms that will allow computers to learn complex state diagrams by providing inputs and observing outputs. The state diagrams that can be learned by current techniques have at most 30.000 states. In contrast, the state diagrams that govern the behavior of computing based systems (defined using dozens of state variables) typically have more than 10¹⁰⁰⁰ states. This year we obtained a breakthrough in learning large state diagrams in collaboration with prof. Jonsson from the University of Uppsala: based on some global information about how an application handles data, our algorithm learned models of some realistic communication protocols (TCP, SIP and the new biometric passport). The research objective of the ITALIA project is to further develop this technique and to construct a tool set that will allow us to learn | routinely and fully automatically | state diagrams with up to 40 state variables. Our project is unique in bringing together research on automata learning with research on machine learning, model based testing, and computer-aided verification.

Utilisation Summary

Once they have high-level models of the behavior of software components, software engineers can construct better software in less time: behavioral models can be used to simulate a system and reason about it, they allow all stakeholders to participate in the development process and to communicate with each other, they can be used to generate and test implementations, and they facilitate reuse. A key problem in practice, however, is the construction of models for existing software components, for which no or only limited documentation is available. The solution that the ITALIA project will provide is technology that will allow engineers to infer state diagrams models fully automatically through observations and test, that is, through black box reverse engineering. We expect that our technology will be particularly effective for control oriented applications such as embedded controllers and network protocols. The ITALIA project will focus on the utilisation of model inference technology within the area of testing: once we have learned a model of a software component, we will use model checking technology to analyze this model (e.g. to detect security vulnerabilities) and the technology of model based testing to automatically infer test suites. Using these test suites we can then check, for instance :

• whether no new faults have been introduced in a modified version of the component (regression testing),
•  whether an alternative implementation by some other vendor agrees with a reference implementation, 
• or whether some new implementation of legacy software is correct. 

The development of our inference/learning technology will be driven by challenging case studies from a number of areas:

• embedded systems (Axini), 
• secure transaction systems (Collis),
• internet protocols (NLnet Labs), 
• printers (Océ-Technologies)
• and wireless sensor networks (Chess).

 We will fully integrate our technology with the Axini TestManager, a commercial model based testing tool, and evaluate the effectiveness of our technology by a comparison with the commercial testing platforms of Axini and Collis. Our goal is to reach the point where it becomes interesting for commercial parties, including Axini and Collis, to integrate our technology within their testing tools.