To Örebro University

Fuzzing frameworks allow the detection of code bugs or errors by feeding the code with unconventional inputs. Recently, Ma et al. proposed LOKI (NDSS, 2023), the first fuzzing framework tailored to blockchain consensus protocols [1]. LOKI uses high-frequency messages to model the dynamics of consensus algorithms. However, low-frequency messages are fundamental to the consensus's state evolution. Thus, neglecting them hinders the in-depth exploration of vulnerabilities, leading to missed bugs or critical issues generated by low-frequency messages.

In this paper, we propose messAge-aWare hybrid markOved StatE model (AWOSE), a fuzzing frameworkmodeling highandlow-frequency messages to uncover vulnerabilities and bugs in consensus algorithms. AWOSEleverages Markov Chains (MCs) tomodel the general states of the consensus messages while leveraging Hidden Markov Models (HMMs) to model latent or hidden state transitions based on code mutations (as in LOKI) or external factors (e.g., malicious inputs). Such probabilistic state models are beneficial for capturing the uncertain nature of system behaviors, enabling a more realistic and flexible representation of consensus dynamics. AWOSE is the first model to introduce the message context-based state model generation for fuzzing purposes. Via a thorough evaluation, we compare AWOSE with LOKI. Results show that our proposed AWOSE provides 48.3% more accurate states and 83.2% better path coverage. Thanks to AWOSE we were able to uncover new bugs that LOKI did not detect. Our experiments lead to the identification of previously unknown vulnerabilities, currently being evaluated as CVEs.