4,278 Adversarial Rewrites, Zero False Accepts: A Certificate Checker for Scratch

Zero false accepts in 4,278 adversarial rewrites — that's the claim from a new certificate-carrying transformation system for Scratch. The authors turned optimization into source-to-source rewriting backed by a trusted checker that recomputes every side condition under an explicit observation lens, rather than trusting the optimizer's word.

Proof-Carrying Rewriting for Block Languages

Block-based languages like Scratch run tens of millions of programs. Existing tools for behavior preservation rely on program analysis and testing — they can miss bugs. This work introduces a fail-closed checker that is the sole authority for accepting a rewrite. An untrusted optimizer proposes a transformation; the checker only accepts after re-verifying every side condition the rewrite depends on. The central soundness argument is a cooperative-frame refinement theorem: a write overwritten before any thread observes it, within a window where no thread yields, can be removed. The authors mechanized this theorem in Lean, showing one parametric statement covers rewrites for variable state and renderer state.

What the Checker Checks

The checker implements six rewrite families. The observation lens is a parameter, so different program viewpoints can be verified. Certification costs under one tenth of a second per project — fast enough for interactive use. An ablation experiment stripped the semantic side conditions, leaving only analysis and testing; that version shipped rewrites that the virtual machine confirmed changed behavior. The full checker rejected every one of those rewrites.

Real-World Results and the Audit

Tested on 300 real Scratch projects, the checker accepted a behavior-preserving rewrite on 94.3% (283 of 300). The 5.7% rejection rate reveals either projects where the rewrite would not be safe or where the checker's side conditions are too conservative. An adversarial campaign of 4,278 perturbed rewrites across all six families produced zero false accepts. An audit then found eight false accepts that the per-family test suites had missed — each is now rejected by the checker. The authors note that keeping the trusted base small (checker mechanized in Lean, a small set of model-to-VM assumptions) means an optimizer bug cannot mint an unsound acceptance.

This approach shows how to deliver behavior-preservation guarantees for concurrent, event-driven, end-user languages — and the same certificate-carrying pattern could be applied to any language where untrusted optimizers need to prove they didn't break anything.

Source: Certificate-Carrying Transformation of Event-Driven Block Programs
Domain: arxiv.org