Stack-based static WebAssembly binary slicing and mutation for generating valid sub-binaries

Abstract

Abstract WebAssembly is a low-level binary format originally designed to enable high-performance applications to run in web browsers. As WebAssembly is increasingly being ported to various environments, the security verification of WebAssembly execution environments is becoming more critical. While a wide variety of WebAssembly binaries is required to verify these environments, collecting binaries from the wild poses clear limitations. To meet this demand, techniques for automatically generating WebAssembly binaries are necessary. However, automatic generation of WebAssembly binaries must consider not only syntactic validity but also the potential lack of diversity in the generated binaries. To overcome these challenges, this paper proposes a series of algorithms for generating valid and semantically rich sub-binaries from a given base WebAssembly binary. First, closure slices are extracted from the base WebAssembly binary using static program slicing. Then, a stack balance correction algorithm is applied to the closure slices to construct syntactically complete functions. Finally, the generated functions are assembled into a complete WebAssembly binary, and instruction-level mutation is applied to introduce diversity. Several experiments were designed to demonstrate the effectiveness and efficiency of these algorithms, and the evaluation results showed that the proposed algorithms are highly promising in generating sub-binaries.