An Experimental Evaluation of Conformance Testing Techniques in Active Automata Learning
Bharat Garhewal, Carlos Diego Nascimento Damasceno · 2023
Active automata learning is a technique for dynamically learning finite state machine models of black-box systems. Conformance testing is a well-known bottleneck during learning. While multiple conformance testing techniques (CTTs) for Finite State Machines have been proposed, there is a lack of empirical studies that assess the effects of these CTTs during learning. In this work, we compare the performance of eight different CTTs (W, Wp, HSI, H-ADS, H, SPY, SPY-H, I-ADS) while learning 46 models from different communication protocols. Moreover, we propose APFDLas a metric for characterizing the efficiency of automata learning experiments in terms of fault detection capacity. This metric allows identifying CTTs with a lower total cost regarding the number of symbols and resets and a higher rate of state discovery during learning. Our results indicate that while the total cost entailed by CTTs in learning tends to be negligible, we found a significant difference in fault detection rate in learning. Nevertheless, the differences in fault detection rates become negligible when CTTs are applied in randomized mode. These findings reveal the positive role that randomness can have in improving learning efficiency, despite compromising test completeness.