CS Paper Radar

Compiling WebAssembly Concolic Execution with Staging, Continuations, and Snapshots (Extended Version)

Dinghong Zhong, Alexander Bai, Mikail Khan, Guannan Wei

cs.PL ·submitted 2026-08-18 21:24 UTC · v2
published

Abstract

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$.

Comment
29 pages; preprint of paper accepted at OOPSLA 2026

Closest papers

Nearest neighbours by meaning across the whole index.

ATLAS: A Multi-Agent Framework for Lifting Binary to Canonical Compiler IR

cs.SE ·2026-10-22 ·Xiaoao Zhu, Ni Zhang, Jie Ren, Zhiqiang Li, Jie Zheng +2 more
similarity 0.71
Abstract

Lifting stripped, heavily optimized binaries to a canonical, pre-optimization LLVM intermediate representation (IR) is essential for downstream security analysis and legacy software migration when source code is unavailable. However, aggressive compiler optimizations rewrite control and data flow, remove structural metadata, and introduce type-erased low-level idioms, causing current lifters to produce malformed or semantically divergent IR. We present ATLAS, a multi-agent framework designed to reconstruct formally valid and canonical LLVM IR from optimized disassembly.ATLAS combines (i) Structure-aware, region-level retrieval, which utilizes pseudo-probe attribution to align optimized instructions with canonical IR exemplars, and (ii) a collaborative refinement loop that closes the gap between probabilistic generation and deterministic compiler constraints. Concretely, a Lift agent generates an initial IR draft conditioned on retrieved exemplars, an Advisor agent interprets LLVM verifier/compilation diagnostics and static checks to propose localized repair actions, and a Validation agent applies the edits, re-runs toolchain verification and (when available) runtime checks, and feeds the resulting diagnostics back to the Advisor. The agents iterate until the IR is verifier-clean and behaviorally consistent, or a budget limit is reached. On HumanEval-Decompile and MBPP, ATLAS outperforms seven baselines on lifting LLVM IR, achieving 91.8% re-executability and 89.4% CFG similarity across ARM, x86-64, and RISC-V binaries. Moreover, our evaluation demonstrates that ATLAS also outperforms the Binary to C to IR pipelines in pointer-flow precision and downstream analyzability. By recovering a well-formed, machine-centric representation, ATLAS enables practical cross-ISA recompilation and verifiable binary-only migration workflows.

0.22

WasmLens: Automatic Glass-Box Instrumentation for Composed WebAssembly Applications

cs.SE ·2026-11-09 ·Michiel Van Kenhove, Ewout Verlinde, José Santos, Filip De Turck, Bruno Volckaert +1 more
published similarity 0.70
Abstract · Accepted article in WebAssembly, Cloud and Edge: Shaping the Future of Computing (WACE '26)

The WebAssembly Component Model enables language-independent composition of independently developed components, but complicates observability. Existing tracing support flattens execution hierarchy by attributing every span created inside a composition to a single host-level parent context, so execution across component boundaries cannot be reconstructed. The problem is amplified because components are typically deployed as black boxes whose internals cannot be modified or inspected by the system integrator. To address these limitations, we propose a revised wasi:otel/tracing design in which the runtime maintains a per-component span stack, restoring parent-child relationships across component boundaries without changing component interfaces or source code. This change has since been adopted upstream. Building on this design, we present WasmLens, an automatic instrumentation tool that derives instrumentation points from a composition graph and injects tracing middleware into already composed binaries, yielding end-to-end traces for black-box compositions with no developer configuration. This automatic instrumentation raises mean request latency from $238$ $μ$s to $454$ $μ$s across six component boundaries. Raising the expected number of boundary crossings from 6 to 11 further increases latency to $514$ $μ$s, an incremental cost of $12$ $μ$s per crossing, of which $10.4$ $μ$s is attributable to instrumentation. These results show that instrumentation overhead is additive in composition depth rather than proportional to baseline execution time.

0.38

Path2Spec: Path-Aware Specification Generation via Large Language Models

cs.SE ·2026-09-27 ·Dan Huang, Zhensu Sun, Huihui Huang, Jinfeng Jiang, Xiaofei Xie +2 more
similarity 0.69
Abstract

Formal specifications are critical for program verification, comprehension, and maintenance. However, manually writing them is costly and difficult to scale. Recent studies have shown that Large Language Models (LLMs) are promising for automated specification generation, but existing methods suffer from quality issues. We analyze a state-of-the-art approach and find that at least 34.6% of successfully verified specifications actually fail to meaningfully capture the program's distinct behavior, which is a quality issue not captured by metrics that only measure verification success. We further found that a major factor contributing to such hidden quality issues stems from the design of existing methods: these methods treat a program as a single unit, resulting in overly general, coarse-grained constraints. To this end, we introduce Path2Spec, a divide-and-conquer framework that addresses these limitations through systematic path-based reasoning. Path2Spec leverages LLMs to extract all execution paths from an input program, generates path-specific specifications for each, and merges them into a comprehensive overall specification. For complex programs where path-based generation struggles, Path2Spec employs a decompose-then-retry strategy that recursively breaks a program into smaller subprograms based on logical branches, generates specifications for each, and merges them back. We evaluate Path2Spec on two public benchmarks: SG-Bench (120 programs) and SV-COMP (265 programs). Results show that Path2Spec can outperform the state-of-the-art baseline SpecGen: 87.5% versus 66.7% on SG-Bench, and 83.0% versus 44.2% on SV-COMP. Human evaluation further validates that Path2Spec generates higher-quality specifications with precise semantic alignment to the code.

0.16

ElevatorII: High-Performance Fully-Static Cross-ISA Binary Translation

cs.CR cs.PL ·2026-11-14 ·Hongyu Chen, James McGowan, Michael Franz
similarity 0.68
Abstract

The established method for running software compiled for one instruction-set architecture (ISA) on a different ISA is by emulation in conjunction with just-in-time (JIT) compilation. This requires run-time support on the target that needs to be trusted and whose compilation decisions are hard to predict or reconstruct. We present ElevatorII, a fully static, ahead-of-time cross-ISA binary-to-binary compiler from x86 to AArch64 that challenges the established consensus. Our approach eliminates the need for run-time support on the target, removes the hard to reproduce effects of dynamic compilation, and provides the capability to exhaustively test the actual binary that is eventually executed. Our approach combines superset disassembly with observation-guided path selection. Superset disassembly overcomes the code vs. data differentiation problem by creating a separate control flow path for every possible interpretation of every byte in the input binary. It guarantees that there is pre-translated code for every possible jump destination in the original text segment, even for computed jumps that are not statically decidable. Static and observation-guided path selection then creates additional optimized "confirmed code paths" that overlay the regular grid. On the 11 SPEC CPU 2026 Integer benchmarks that do not use C++ exceptions, ElevatorII runs at 2.5x native AArch64 time, on par with Box64, the fastest dynamic translator, and 5x faster than QEMU. It also translates binaries obfuscated with virtualization and branch functions, which no static disassembler can follow. Our approach trades execution performance for space: our output code is 51x the size of code compiled from source. We alleviate this by separating cold code to a .text.unlikely ELF section: only 2-3% hot code winds up in the main ELF section, while the rest will likely never be loaded into memory.

0.26

ContextPipe: Database-Inspired Context Assembly for Long-Horizon Agents

cs.AI cs.DB ·2026-09-01 ·Peng Xu, Zuyu Zhang, Yuze Sun, Feng Tian, Long Wang +1 more
position similarity 0.67
Abstract

Long-horizon large language model (LLM) agents require context assembly: the runtime must decide what to include in each prompt, in what order, and when to compact history under a hard context-window budget and a byte-sensitive prompt cache. In production agentic systems, this logic is scattered across prompt builders, ad hoc compaction routines, cache-break workarounds, and per-provider shims. We argue that context assembly is structurally isomorphic to query execution in a relational database: both execute under a hard budget, exploit a tiered cache, and leverage statistics. We adopt this discipline in ContextPipe: a five-phase pipeline (Plan Bind Optimize Execute Feedback) backed by a structured data-source catalog, a deterministic cache-aware optimizer, and an EXPLAIN ANALYZE trace. We show that context in ContextPipe is auditable, replayable, and failure-isolated. A preliminary evaluation using the SWE-bench Pro Qutebrowser subset shows that, compared with the append-only context construction policy, ContextPipe reduces total token volume by 31%, LLM calls by 23%, and response time by 9%, at the cost of a lower KV cache-hit ratio.

0.21

Statically Typed Purely Functional Definitional Interpreters for {\it Essentials of Programming Languages}

cs.PL ·2026-11-17 ·Kwanghoon Choi
similarity 0.66
Abstract · The 24th Asian Symposium on Programming Languages and Systems (APLAS 2026)

Definitional interpreters provide an executable and pedagogically effective way to explain programming language semantics. However, when implemented in a dynamically typed and effectful metalanguage, semantic components such as stores, continuations, handlers, substitutions, and scheduling states may remain implicit in the host-language implementation, making it harder to see how language extensions affect interpreter structure. This paper reconstructs the family of interpreters from \textit{Essentials of Programming Languages} (EOPL) in Haskell, a statically typed and purely functional metalanguage, for pedagogical use. We preserve the object languages, examples, and tests of EOPL while making their semantic components explicit through algebraic data types, evaluator signatures, and explicit semantic domains. Across 15 interpreters and 6 type checkers, language extensions are exposed as systematic type-directed changes. The reconstruction is currently used in undergraduate and graduate programming language courses, where students learn interpreter construction through incremental and test-driven development. We further illustrate its pedagogical use through three case studies that progressively extend students' experience: composing mutable state and exception handling, deriving an actor-based interpreter from the typed structure of the EOPL thread interpreter, and translating the CHECKED interpreter and type checker into Rocq to mechanize type safety. Together, the classroom experience and case studies suggest that the reconstruction provides a concrete bridge from learning programming language concepts through executable interpreters to language design and mechanized reasoning.

0.26

Template-Free Dynamic Invariant Detection

cs.SE ·2026-10-28 ·Erfan Arvan, Michael D. Ernst, Martin Kellogg
code/data similarity 0.66
Abstract · 20 pages

A dynamic invariant detector proposes invariants, such as method pre- and postconditions, and rules out those that do not hold at run time. Traditional detectors propose invariants from a fixed library of templates, which limits their expressiveness. A large language model (LLM) can propose invariants instead of, or in addition to, template-derived ones. With the right prompt and context choices, we found that this idea can both improve the invariants' expressiveness and reduce the cost of inferring the invariants. Greater expressiveness brings complications: an LLM-proposed invariant can execute arbitrary code during invariant evaluation, causing side effects or infinite loops. Our novel instrumentation strategies mitigate these problems. We wrap each candidate and evaluate only one invariant per thread at a time, so nested invariant evaluations cannot trigger one another indefinitely. To recover from non-nested hangs, we monitor each run for stalls and retry it under a growing time budget. Because we cannot prove a candidate side-effect-free in advance, we use delta debugging over the invariants evaluated during a failing test to isolate and disable a side-effecting candidate without discarding the rest of the run. We compared our implementation, Oca, to the popular template-based Daikon invariant detector on real open-source Java projects. Oca produces more expressive invariants: on average, 28% of its held invariants call a project-specific method, which Daikon's templates cannot express. Its invariants are more often valid, with a false-positive rate of 18% in a manual inspection, vs. 76% for Daikon, and more useful: as properties for property-based testing, they exposed 9 of 25 real bugs, compared with 4 for Daikon. Oca also costs less, using 566 minutes and 27 GB of disk, compared with 2,817 minutes and 827 GB for Daikon.

0.40

SpeC2Rust: Specification-Driven Repository-Level C-to-Rust Translation

cs.SE ·2026-10-25 ·Junjie Yao, Xiongzheng Guan, Jia Feng, Yujia Chen, Hongliang Tian +1 more
similarity 0.66
Abstract

Legacy C codebases remain central to system software and performance-critical infrastructure, but their weak memory safety imposes security and maintenance risks. Recent C-to-Rust translation systems, including LLM-based translators, make automated migration increasingly feasible, yet they still struggle to recover repository-level intent, avoid raw pointers and unsafe constructs, maintain cross-file interfaces, and repair compilation and validation failures efficiently. We propose SpeC2Rust, a specification-driven pipeline for repository-level C-to-Rust translation. It has three stages: (1) Project-Intent Structuring, which decomposes a C repository into semantically coherent modules and generates persistent repository- and module-level specifications; (2) Spec-Guided Generation, which translates each Rust module against these specifications with a live symbol registry to preserve cross-file consistency; and (3) Layered-Feedback Repair, which batches repairs and injects only failure-relevant diagnostics, specification context, and source evidence for efficient compilation and test-driven correction. We evaluate SpeC2Rust on eight repository-level C projects. It generates Rust projects that compile and pass the original end-to-end tests, with no raw-pointer declarations, raw-pointer dereferences, or unsafe lines. On projects shared with an LLM-based baseline, SpeC2Rust reduces cost by 66.1% and input-token usage by 84.7%.

0.22