L-SCALE: Locality-Sensitive Coverage for Automata LEarning

Approaches like AFLNet have successfully managed to improve upon stateless fuzzers by incorporating state information in the form of response codes or enum values in the source code. Most approaches use the state information directly instead of attempting to infer a state machine. However, having an explicit state model of the System under Test (SUT) is beneficial for designing more sophisticated fuzzing techniques, demonstrated by approaches that infer a state machine by using the responses the SUT sends. In this work, we propose L-SCALE, an approach based on the 𝐿∗-Algorithm utilizing the coverage of individual messages as a measure of the behavior of the SUT. In contrast to other approaches that utilize only the responses of the SUT, this allows us insights into the internal state of the SUT, which is often not reflected in the responses it sends. Since coverage is a very fine-grained measure, we utilize TLSH, a Locality Sensitive Hash (LSH), in combination with a threshold value for the similarity of the hashes to categorize slightly different coverage measurements as the same observation. We also contribute mogi, an emulator framework that provides deterministic execution and incremental snapshotting capabilities. ... mehrmogi facilitates efficient exploration of deep states since we can reset to any point along the exploration path. This avoids having to replay all the messages along that path each time. We use mogi as a runtime environment for L-SCALE. We evaluate L-SCALE on two real-world open-source targets: Redis, a widely used key-value store, representing the IT-domain, and open62541, an implementation of the OPC UA architecture, representing the Operational Technology (OT)-domain. Our results show that by using coverage as an observation measure, we can successfully identify detailed state representations of SUT, and that by utilizing LSH, one can control the coarseness of the learned state representation while still maintaining an accurate, albeit simplified, representation of the underlying state space. This enables testers to choose between fine-grained but complex, and coarse but simple state representations, depending on the use case. Our experiments also show that choosing a good threshold highly depends on the SUT. Overall, L-SCALE provides a means to automatically infer This work is licensed under a Creative Commons Attribution 4.0 International License.
AST ’26, Rio de Janeiro, Brazil