Regular Inference for State Machines with Parameters
2006 (English)In: Fundamental approaches to software engineering: ( 9th international conference, FASE 2006, held as part of the Joint European Conferences on Theory and Practice of Software, ETAPS 2006, Vienna, Austria, March 27-28, 2006 ), Berlin: Springer , 2006, 107-121 p.Chapter in book (Other academic)
Techniques for inferring a regular language, in the form of a finite automaton, from a sufficiently large sample of accepted and nonaccepted input words, have been employed to construct models of software and hardware systems, for use, e.g., in test case generation. We intend to adapt these techniques to construct state machine models of entities of communication protocols. The alphabet of such state machines can be very large, since a symbol typically consists of a protocol data unit type with a number of parameters, each of which can assume many values. In typical algorithms for regular inference, the number of needed input words grows with the size of the alphabet and the size of the minimal DFA accepting the language. We therefore modify such an algorithm (Angluin's algorithm) so that its complexity grows not with the size of the alphabet, but only with the size of a certain symbolic representation of the DFA. The main new idea is to infer, for each state, a partitioning of input symbols into equivalence classes, under the hypothesis that all input symbols in an equivalence class have the same effect on the state machine. Whenever such a hypothesis is disproved, equivalence classes are refined. We show that our modification retains the good properties of Angluin's original algorithm, but that its complexity grows with the size of our symbolic DFA representation rather than with the size of the alphabet. We have implemented the algorithm; experiments on synthesized examples are consistent with these complexity results.
Place, publisher, year, edition, pages
Berlin: Springer , 2006. 107-121 p.
, Lecture notes in computer science, ISSN 0302-9743
Test generation, Algorithm complexity, Modeling, Equivalence classes, Deterministic automaton, Data type, Transmission protocol, Finite automaton, Regular language, Inference, Software development
Computer and Information Science
IdentifiersURN: urn:nbn:se:uu:diva-98084ISBN: 3-540-33093-3OAI: oai:DiVA.org:uu-98084DiVA: diva2:173260