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 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, Thermo Fisher and Axini). We refer to the 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) Internships at Thermo Fisher

Thermo Fisher develops high-end microscopes. To build control software for electron microscopes, Thermo Fisher is continuously looking for ways to optimize the software engineering process. Two internships are currently available for which we are looking for students. A first internship concerns the application of model learning to learn a model of a legacy software component for an electron microscope (contact Frits Vaandrager). Another technique that could improve the quality and time-to-market is making use of model-based testing. The goal of the second internship is to get sufficient knowledge to decide whether Thermo Fisher 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 Thermo Fisher (contact Jozef Hooman).

b) 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? Why do Galois connections show up all the time in model learning? (contact Frits Vaandrager).

c) Tools

Do you like programming? Within our group we are working on software tools for learning, e.g. Tomte, LearnLib and RAlib. There are several possibilities for tool oriented projects, especially to link our learning tools to other tools, such as testing tools (in order to establish the correctness of a learned hypothesis model), model checking tools (to analyse compositions of learned component models), and other learning tools (in particular passive learning tools to construct models from logs). Recently, we have set up a repository with benchmarks for automata learning and model based testing. There is still much work to do in extending this repository with new benchmarks and software, and experimentally evaluating existing learning and testing algorithms. (contact Frits Vaandrager).

For model-based testing, we are working on the TorXakis tool. Also here there are several possibilities for tool oriented projects. Examples are the connection of TorXakis to other tools, such as constraint solvers for test-data generation, to model-checkers for validation of test models, and to industrial and popular testing frameworks (SoapUI, Robot Framework, Behave, ...) for combining model-based testing with existing testing practices. Other possibilities include improving the performance of TorXakis, extension of the TorXakis modelling language, visualization of TorXakis models and test results, and the implementation of new test generation algorithms. (contact Jan Tretmans).

d) 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. 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 ideas on how symbolic execution and taint analysis can be used to speed up model learning. (contact Frits Vaandrager)

e) Learning Models of Network Protocols

Did you like the Computer Networks 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 or Erik Poll).

f) 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. Recently, we have published papers on combining Tretmans' theory with the theory of Finite State Machines, see here and here, but this theory requires some next steps to make it applicable and to implement in the model-based testing tool TorXakis. The goal of this project would be to extend, adapt, and apply this theory. (contact Frits Vaandrager or Jan Tretmans).

g) 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).

h) 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).

i) 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).

j) Using Usage Profiles in Model-Based Testing

Current systems are huge. Scaling model-based testing to such large systems is a challenge, in particular the selection of appropriate test cases for testing. One approach is to use usage (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).

k) Internships at Oce (Canon)

There are several opportunities for internships at Oce, for instance on applying model-based testing. The latter opportunities may involve technical and tool aspects (e.g., connecting TorXakis to the OcÚ test environment), process aspects (e.g., how to embed model-based testing in the OcÚ testing process), as well as human aspects (e.g., how to support test engineers in using model-based testing). (contact Jan Tretmans).

l) 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.

m) Internships at other companies

In the context of our research on model based testing and automata learning, we are collaborating with several other companies that are interested in the potential of these new techniques, for instance, ASML, Philips Healthcare, Tom Tom, Vanderlande, InTraffic, and SpronQ. Please contact Jozef Hooman, Jan Tretmans or Frits Vaandrager.