print · source · login   

Theme: Model Learning and Model-Based Testing

Within our group we work on the design of algorithms that allow computers to learn complex state diagrams by providing inputs and observing outputs. This is an exciting new area in which we collaborate with the Digital Security group to learn models of security protocols and also with several companies (e.g. ASML, Philips Healtcare, Oce, FEI and Axini). We refer to the recent review article by Frits Vaandrager in Communications of the ACM for a general introduction. In model-based testing, a model is the starting point for testing. This model expresses precisely and completely what a system under test should do, and should not do, and, consequently, it is a good basis for systematically generating test cases. Model learning and model-based testing are complementary techniques. In particular, model-based testing can be used to find counterexamples for candidate models produced by model learning techniques. There are several opportunities for theoretical, tool/programming oriented, and application oriented projects related to model learning and model-based testing:

a) Theory

Did you like the Languages and Automata course and are you interested in theory (e.g. have you selected the MFoCS specialization)? Well, we can define dozens of projects on automata learning that build further on the classical theory of languages and automata. How can we make automata learning algorithms more efficient (for instance by integrating learning and testing of hypotheses)? How can we extend Angluin's original L* algorithm for learning finite automata to richer classes of automata that can model data or time? What is the link between nominal automata and register automata? How can we learn complex dynamic behavior incrementally? (contact Frits Vaandrager).

b) Learning Tools

Do you like programming? Within our group we are working on the Tomte learning tool. There are several possibilities for tool oriented projects, especially to link Tomte to other tools, such as model based test tool (in order to establish the correctness of the hypothesis models learned by Tomte), invariant detector tools such as Daikon (to learn models with data), model checking tools (to analyse compositions of learned component models), and other learning tools (in particular passive learning tools to construct models from logs) (contact Frits Vaandrager).

c) Combining Black Box and White Box Learning

Thus far, in Nijmegen, we have concentrated mostly on black box automata learning techniques. Application of such techniques makes sense if we have either no access to the code of the system under learning, or when this code is too complicated to analyze/understand. Recently, interesting progress has been made in the area of white-box learning, e.g. by Botinčan & Babić. Here the goal is to derive abstract models of external behavior directly from the code. The goal of this project would be to investigate, based on a well-chosen case study, scenarios in which black box and white box learning are combined. We have some very nice ideas on how static analysis and techniques from compiler construction can be used to speed up model learning! (contact Frits Vaandrager)

d) Learning Models of Network Protocols

Did you like the Computer Networks (GDN) course and do you find it interesting to understand the details of network protocols? There are many possibilities for projects in which the goal is to learn models of protocol components. We are particularly interested in learning models of security related protocols (like TCP, SSH, TLS, EMV, etc). Here model learning may help us to find specific sequences of input events that exhibit security vulnerabilities. (contact Frits Vaandrager, Erik Poll or Joeri de Ruiter).

e) Generalizing Algorithms for FSM Conformance Testing to an Ioco Setting

Theorists have developed a powerful set of algorithms for conformance testing of deterministic Finite State Machine models, see e.g. Lee & Yannakakis. Now a problem is that in practice systems often are nondeterministic and do not exhibit the strict alternation of inputs and outputs from the FSM model: sometimes an input is not followed by any output at all, sometimes an input is followed by a series of outputs. Jan Tretmans has developed a popular theory of testing for this general class of systems, but there are still very few algoritms for efficient conformance testing in this general setting. The goal of this project would be to adapt existing algorithms for FSM testing to the Ioco setting of Tretmans. (contact Frits Vaandrager or Jan Tretmans)

f) Model-based Concolic Testing

Concolic testing is a combination of symbolic and concrete testing applied for white-box testing, which, among others, is successfully used by Microsoft. Model-based testing (MBT) is a promising approach for black-box testing. The goal is to combine these two approaches by applying the concepts of concolic tesing to (ioco-based) MBT, in order to improve test selection for MBT (contact Jan Tretmans).

g) Learning Algorithms for Non-deterministic Systems

Current tools for automata learning are based on deterministic Finite State Machines (FSM; Mealy Machines). Recently, we have published methods for learning non-deterministic labelled transitions systems, combining the FSM learning theory and the IOCO model-based testing theory. The next step is to turn these learning methods into efficient algorithms, to implement them, and to apply them to case studies with non-deterministic behaviour (contact Jan Tretmans).

h) Minimal Counterexamples in Model-based Testing

We defined Domain Specific Languages to express logic properties of pure functions and the allowed behaviour of state-based systems. Based on these specifications the automatic test system generates test cases, executes the associated tests, and gives a verdict about the system under test. Current research focuses on finding smaller test cases showing non-conformance, and challenging applications of model-based testing (contact Pieter Koopman).

i) Internships at ASML

There are several opportunities for MSc thesis projects at ASML.

ASML systems are huge. Scaling model-based testing such large systems is a challenge, in particular the selection of appropriate test cases for testing. One approach is to use operational profiles as the basis for testing, i.e., using users' scenarios as the basis for test selection. The goal is to combine user profile-based testing with ioco model-based testing (contact Jan Tretmans).

Many companies like to write models in languages that are specific for their domain, i.e., domain specific languages (DSL). Such models shall then also be used for model-based testing of products developed from these models. Goal is to investigate how DSLs can be used for model-based testing, what requirements shall be imposed on DSLs to facilitate MBT, and to apply these ideas to a DSL from ASML and ioco-based MBT (contact Jan Tretmans).

There are also opportunities for projects in which model learning is used for refactoring legacy software: Towards a Risk-Assessment Based Approach for Refactoring of Legacy Components (contact Frits Vaandrager)

j) Internships at Oce

There are several opportunities for internships at Oce, for instance on Model learning for performance model calibration and on Validation of inter process communication.

Some time ago we succeeded to apply automata learning to learn a Finite State Machine model of a control that is being used in printers/copiers from Oce. An interesting project would be to further scale this technique so that it becomes practically useful, for instance to create new implementations of legacy software. The main new idea is to use logs of an existing implementation as a starting point for active learning algorithms. (contact Frits Vaandrager or Jan Tretmans).

k) Internships at Axini

Axini is a spin-off of the University of Twente, based on research by Jan Tretmans and his students on model-based testing. The company specializes in test automation and aims at the application of formal methods in practice. There are several MSc thesis projects available at Axini, see here for more details. In particular subprojects 1, 2 and 7 are interesting (contact Jan Tretmans).

l) Internship at FEI Company

FEI Company develops high-end microscopes. To build control software for electron microscopes, FEI Company is continuously looking for ways to optimize the software engineering process. One of the techniques that could improve the quality and time-to-market is making use of model-based testing. The goal of this internship is to get sufficient knowledge to decide whether FEI should introduce model-based testing in the software engineering process. This includes an overview of available techniques, the selection of a promising candidate, and the application to a case study of FEI (contact Jozef Hooman).

m) Internships at other companies

In the context of our research on automata learning we are collaborating with several companies that are interested in the potential of this new technique, for instance Philips Healthcare. Please contact Jozef Hooman, Jan Tretmans or Frits Vaandrager