From Rule-Based to Automata-Based Testing

Rule based languages have been used extensively to provide a declarative description of causal relationships between events and conditions in a wide variety of systems. On the other hand, automata (finite state machine) based models provide a detailed operational specification of how the system state evolves over time. While rules are a convenient declarative mechanism, a finite automaton is more flexible and far more easily analyzed than a collection of rules with potentially complicated semantics.In this paper, we address this dichotomy in the context of large scale testing. We describe a (probabilistic) rule based system, which has been developed and used over many years as the testing model of a large telephone switch. One important drawback of the rule-based system is that it is inflexible in terms of the test generation mechanisms it supports, essentially only allowing the generation of random tests.We have designed and implemented a translation from the rule-based language to a probabilistic finite automaton model, and applied it to the switch model. Our translation makes use of several automata-theoretic algorithms to keep the size of the resulting automata manageable.The automaton model allows much more flexible and targeted test generation. We have designed and implemented an assortment of targeted test generation algorithms which are applied to the probabilistic automaton.