Abstract | ||
---|---|---|
The paper focuses on the problems of passive and active FSM inference as well as checking sequence generation. We consider the setting where an FSM cannot be reset so that its inference is constrained to a single trace either given a priori in a passive inference scenario or to be constructed in an active inference scenario or aiming at obtaining checking sequence for a given FSM. In each of the last two cases, the expected result is a trace representing a checking sequence for an inferred machine, if it was not given. We demonstrate that this can be achieved by a repetitive use of a procedure that infers an FSM from a given trace (identifying a minimal machine consistent with a trace) avoiding equivalent conjectures. We thus show that FSM inference and checking sequence construction are two sides of the same coin. Following an existing approach of constructing conjectures by SAT solving, we elaborate first such a procedure and then based on it the methods for obtaining checking sequence for a given FSM and inferring a machine from a black box. The novelty of our approach is that it does not use any state identification facilities. We demonstrate that the proposed approach can also be constrained to find a solution in a subset of FSMs represented by a nondeterministic mutation machine. Experiments with a prototype implementation of the developed approach using an existing SAT solver indicate that it scales for FSMs with up to a dozen of states and requires relatively short sequences to identify a black box machine. |
Year | DOI | Venue |
---|---|---|
2019 | 10.1007/s11219-018-9429-3 | Software Quality Journal |
Keywords | Field | DocType |
FSM testing, Machine inference, Machine identification, Active learning, Checking experiments, Checking sequences, Conformance testing | Black box (phreaking),Active learning,Nondeterministic algorithm,Computer science,Inference,A priori and a posteriori,Boolean satisfiability problem,Theoretical computer science,Conformance testing,Novelty,Reliability engineering | Journal |
Volume | Issue | ISSN |
27.0 | SP2 | 1573-1367 |
Citations | PageRank | References |
0 | 0.34 | 20 |
Authors | ||
4 |
Name | Order | Citations | PageRank |
---|---|---|---|
Alexandre Petrenko | 1 | 176 | 15.90 |
Florent Avellaneda | 2 | 11 | 4.62 |
Roland Groz | 3 | 496 | 50.60 |
Catherine Oriat | 4 | 55 | 9.54 |