Search papers, labs, and topics across Lattice.
This paper introduces GenWasym, a concolic execution compiler for WebAssembly that combines the simplicity of interpreter-based systems with the efficiency of instrumentation-based systems. By employing a staged approach and continuation-passing style, the authors enable the capture of execution snapshots at branch points, allowing for efficient exploration of alternative paths without redundant re-execution. The results demonstrate a remarkable average speedup of 44.9 times over traditional interpreter-based methods across 184 benchmarks, significantly enhancing the performance of concolic execution.
Achieving up to 44.9x speedup in concolic execution for WebAssembly could revolutionize how we analyze and test complex software systems.
Concolic execution is a variant of symbolic execution that runs a program simultaneously with concrete and symbolic inputs. It records the symbolic constraints encountered along a concrete execution path, then solves those constraints to generate inputs that explore new paths. Existing concolic engines generally follow one of two implementation strategies: Interpreter-based systems are comparatively simple to build but incur substantial interpretation overhead, while instrumentation-based systems avoid this overhead but typically re-execute the program from the beginning for each new input. In this paper, we develop a new approach that achieves the best of both worlds. Starting from the concrete semantics of the target language, we first develop a definitional concolic interpreter and stage it to compile away interpretation overhead while retaining the simplicity of an interpretation-based implementation. By expressing the staged interpreter in continuation-passing style, we can capture execution snapshots at branch points and resume from them when exploring alternative paths, avoiding repeated execution from the program entry. Because snapshot-reuse can itself incur overhead, we further develop a heuristic that favors snapshot-reuse only when it is expected to be beneficial. We instantiate this approach for WebAssembly and implement it in a new concolic-execution compiler GenWasym. Across 184 benchmarks, GenWasym with staging alone achieves a $29.4\times$ average speedup over the interpreter-based WASP; heuristic snapshot-reuse further increases the speedup to $44.9\times$.
