Approximate Active Learning of Nondeterministic Input Output Transition Systems

Authors

  • Michele Volpato Radboud University
  • Jan Tretmans Radboud University TNO - ESI

DOI:

https://doi.org/10.14279/tuj.eceasst.72.1008

Abstract

Constructing a model of a system for model-based testing, simulation, or model checking can be cumbersome for existing, third party, or legacy components. Active automata learning, a form of black-box reverse engineering, and in particular Angluin’s L* algorithm, support the automatic inference of a model from a System Under Learning (SUL), through observations and tests. Most of the algorithms based on L* , however, deal with complete learning of deterministic models, thus being unable to cope with nondeterministic SULs, and always learning a complete and correct model as they are based on equivalence between the SUL and the model. We present an adaptation of Angluin’s algorithm for active learning of nondeterministic, input-enabled, input-output transition systems. It enables dealing with nondeterministic SULs, and it allows to construct partial, or approximate models, by expressing the relation between the SUL and the learned model as a refinement relation, not necessarily an equivalence. Thus, we can reason about learned models being more, or less precise than others. Approximate learning has benefits in model-based regression testing: we need not to wait until a complete model has been learned; with an approximate model ioco-based regression testing can start.

Downloads

Published

2015-11-25

How to Cite

[1]
M. Volpato and J. Tretmans, “Approximate Active Learning of Nondeterministic Input Output Transition Systems”, eceasst, vol. 72, Nov. 2015.