Incorporating Data into EFSM Inference

By Michael Foster, Achim D. Brucker, Ramsay G. Taylor, Siobhán North, and John Derrick.

Models are an important way of understanding software systems. If they do not already exist, then we need to infer them from system behaviour. Most current approaches infer classical FSM models that do not consider data, thus limiting applicability. EFSMs provide a way to concisely model systems with an internal state but existing inference techniques either do not infer models which allow outputs to be computed from inputs, or rely heavily on comprehensive white-box traces that reveal the internal program state, which are often unavailable.

In this paper, we present an approach for inferring EFSM models, including functions that modify the internal state. Our technique uses black-box traces which only contain information visible to an external observer of the system. We implemented our approach as a prototype.

Keywords:
EFSM Inference, Model Inference, Reverse Engineering

Please cite this work as follows:
M. Foster, A. D. Brucker, R. G. Taylor, S. North, and J. Derrick, “Incorporating data into EFSM inference,” in Software engineering and formal methods (SEFM), P. C. Ölveczky and G. Salaün, Eds. Heidelberg: Springer-Verlag, 2019, pp. 257–272. doi: 10.1007/978-3-030-30446-1_14. Author copy: http://logicalhacking.com/publications/foster.ea-incorporating-2019/

BibTeX
@InCollection{ foster.ea:incorporating:2019,
  abstract  = {Models are an important way of understanding software
               systems. If they do not already exist, then we need to infer
               them from system behaviour. Most current approaches infer
               classical FSM models that do not consider data, thus limiting
               applicability. EFSMs provide a way to concisely model systems
               with an internal state but existing inference techniques
               either do not infer models which allow outputs to be computed
               from inputs, or rely heavily on comprehensive white-box traces
               that reveal the internal program state, which are often
               unavailable.
               
               In this paper, we present an approach for inferring EFSM
               models, including functions that modify the internal state.
               Our technique uses black-box traces which only contain
               information visible to an external observer of the system. We
               implemented our approach as a prototype.},
  keywords  = {EFSM Inference, Model Inference, Reverse Engineering},
  location  = {Oslo},
  author    = {Michael Foster and Achim D. Brucker and Ramsay G. Taylor and
               Siobh{\'a}n North and John Derrick},
  booktitle = {Software Engineering and Formal Methods (SEFM)},
  language  = {USenglish},
  pages     = {257--272},
  publisher = {Springer-Verlag },
  address   = {Heidelberg },
  series    = {Lecture Notes in Computer Science },
  number    = {11724},
  isbn      = {3-540-25109-X},
  doi       = {10.1007/978-3-030-30446-1_14},
  editor    = {Peter C. {\"O}lveczky and Gwen Sala{\"u}n},
  title     = {Incorporating Data into EFSM Inference},
  areas     = {formal methods, software},
  year      = {2019},
  note      = {Author copy: \url{http://logicalhacking.com/publications/foster.ea-incorporating-2019/}},
}