Search papers, labs, and topics across Lattice.
This paper introduces a certificate-carrying approach to optimizing event-driven block programs, specifically targeting the behavior preservation of programs written in languages like Scratch. By employing a trusted checker that verifies rewrites proposed by an untrusted optimizer, the authors ensure soundness through a cooperative-frame refinement theorem, mechanized in Lean. The evaluation demonstrates that the checker successfully accepts behavior-preserving rewrites for 94.3% of 300 real Scratch projects, with certification costs remaining under one tenth of a second per project and no false accepts in adversarial testing.
A novel certificate-carrying method guarantees behavior preservation in Scratch programs, achieving a 94.3% acceptance rate with zero false positives in adversarial scenarios.
Block-based end-user languages such as Scratch run tens of millions of programs. Existing tools establish behavior preservation through program analysis and testing without a checked guarantee. We turn optimization into certificate-carrying source-to-source rewriting. An untrusted optimizer proposes a rewrite; a trusted, fail-closed checker accepts it only after recomputing every side condition that the rewrite's behavior preservation depends on under an explicit observation lens. The checker is the sole authority: given a correct checker and a small, explicitly stated set of model-to-VM assumptions, an optimizer bug cannot mint an unsound acceptance. The observation lens is a parameter, and the central soundness argument is a cooperative-frame refinement theorem: a write overwritten before any thread observes it, within a window in which no thread yields, can be removed. We mechanize this theorem in Lean and show that one parametric statement covers two concrete rewrite families instantiated to variable state and renderer state. We build a checker for six rewrite families and evaluate it on 300 real Scratch projects. The checker accepts a behavior-preserving rewrite on 94.3% of projects (283 of 300); certification costs under one tenth of a second per project; and a cross-family adversarial campaign of 4,278 perturbed rewrites produces zero false accepts. An audit found eight false accepts the per-family test suites missed; each is now rejected. An ablation that strips the semantic side conditions, leaving analysis and testing alone, ships rewrites the virtual machine confirms change behavior; the full checker rejects every one. The result shows how to provide behavior-preservation guarantees for a concurrent, event-driven, end-user language. The checker recomputes every required condition instead of trusting optimizer claims, keeping the trusted base small.
