Institutionen för informationsteknologi

Potential Master's and Ph.D. Thesis Projects

The Testing and Model Generation group at Uppsala University is developing techniques and tools to automate the generation of models of communication protocol modules, components of reactive systems, etc. One motivation is to automate the labor-intensive construction of models, which are needed in systematic testing and verification (e.g., in model based testing and model checking). One application would be regression testing, where a model of an earlier implementation can be used to create test suites for subsequent versions. Constructing models of legacy software systems can, in combination with other techniques, support future maintenance, testing, and verification of such systems.
Our main approach is to adapt techniques from regular inference (aka automata learning) so that they can deal with realistic implementations of communication protocol modules, and other similar components. We have previously conducted theoretical studies (see previous papers and theses), and conducted preliminary case studies on implemented communication protocols.
One important goal of this project is to develop a tool which, as automatically as possible, can generate models of communication protocol modules by observing how they respond to sequences of input messages (i.e., by performing extensive testing). Up til now, we have used the LearnLib tool developed at the Univ. of Dortmund, for the experiments that we have conducted. However, the current implementation of LearnLib is too inflexible for further development. One of our current priorities is therefore to implement a more adaptible tool.

Interesting subprojects include:

  • Developing support for different datatypes, which occur in protocols, web services, etc. Typical examples could identifiers, sequence numbers, timers, user data, application data (uninterpreted).
  • An optimized engine algorithm, which efficiently can organize the results of queries into an optimal abstract model. This engine must have less rigid requirements about the input data than, e.g., the L* algorithm, but still be reasonably efficient.
  • Generating optimal representations of the model, in order to make it as understandable as possible. This problem has some relationship with optimization of code in compilers, e.g., to make it as compact as possible, or to make it as simple as possible. It is not completely clear what is the best metric for optimization on this problem.
  • Strategies for selection of input test data. This problem is related to the common problem of selecting the best inputs for test suites.
  • Performing additional case studies.

The overal goal of the project will be work will be carried out in the context of the project Connect. We are collaborating with several research groups, including the group of Prof. Steffen at TU Dortmund, who are developing the LearnLib tool, and the group of Prof. Vaandrager at the Univ. of Nijmegen.

Interested in Ph.D. or M.Sc project?

send an email to Bengt Jonsson (bengt [at] with usual information about yourself,

Uppdaterad  2009-11-29 17:19:07 av Bengt Jonsson.