A checking sequence is defined as follows: "Given a specification finite state machine, for which we have its transition diagram, and an implementation, which is a ‘‘black box’’ for which we can only observe its I/O behavior, we want to test whether the implementation conforms to the specification. This is called the conformance testing or fault detection problem and a test sequence that solves this problem is called a checking sequence."
What is the current state-of-the-art algorithm to find the shortest checking sequence, given a specification finite state machine? Are there some open-source implementations?
Actually it can be an application of compiling priciple. You know the output of each state?
I am specifically working on Mealy machines, so my output is tied to the transitions; but I have the complete specification of the original machine, and I can observe all outputs produced by the "black box" implementation.
I'd like to recommend fsmlib-cpp as open-source implementation (see link). You can use the library to create an m-complete Test Suite, with m being the maximum number of assumed additional states in the Implementation Under Test (which is a black box). Though the state of art you are asking for is not implemented yet, the software is constantly being developed and newer algorithms are promised to be implemented soon. Currently the Wp-Method is implemented there.
I think state-of-art is the so called H-Method (see link). It produces less test cases then the Wp-Method.
However I recently read that even this algorithm is superseded by an algorithm of Simao and Petrenko, which I haven't read yet (see link).
https://github.com/agbs-uni-bremen/fsmlib-cpp
https://link.springer.com/chapter/10.1007/11562436_16
http://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=5396326
Some available and relevant articles about the issue, are attached.
Conference Paper A New Approach To Checking Sequence Generation for Finite St...
Article Generating Checking Sequences for Nondeterministic Finite St...
Conference Paper Generating Checking Sequences for Partial Reduced Finite Sta...
Article Efficient checking sequences for testing finite state machines
- Badges
- Science method
- Similar topics
- Mathematics
- Statistics
- Statistical Techniques
- Meta-Analysis