Contrôle douanier pour le code : comment garantir une optimisation sans erreur des programmes pour enfants ✛
Contexte
Regardez un jeu d'enfant écrit dans le système théorie du contrôle Scratch : le personnage apparaît au centre de l'écran, puis saute instantanément dans un coin. Le premier déplacement n'a été vu par personne — il a disparu entre les images. Le supprimer, c'est ne rien casser pour le joueur, mais comment le garantir automatiquement ? Les outils d'optimisation actuels pour ces langages visuels reposent sur l'analyse et les tests, sans offrir de garanties formelles. Pendant ce temps, le dépôt Scratch contient des dizaines de millions de projets écrits par des enfants et des amateurs — un public incapable de remarquer ou de corriger une erreur introduite par un améliorateur automatique. La confiance devient ici primordiale : un optimiseur qui modifie silencieusement le jeu d'un enfant est pire que pas d'optimiseur du tout. L'approche classique du monde des compilateurs vérifiés — prouver la correction des transformations une fois pour toutes — se heurte au multithreading coopératif, au modèle événementiel et au rendu propres à Scratch. Il y a un fossé : les méthodes formelles savent traiter le C séquentiel, mais le code vivant et respirant d'une animation scolaire exige de nouveaux fondements.
Méthodes
Les développeurs de CertiBlock ont divisé le système en deux parties inégales : un optimiseur non vérifiable et un contrôleur de confiance. L'optimiseur scanne le projet, construit un graphe de dépendances et propose une suppression, par exemple, d'une commande morte ou d'un costume inutilisé. À la proposition est joint un « certificat » — un manifeste indiquant le type de modification, la somme de contrôle des programmes source et modifié, et la lentille d'observation. La lentille est une notion paramétrée qui définit ce que le joueur voit : images, sons, valeurs de variables à l'écran, et non les commentaires internes. Le contrôleur, tel un inspecteur des douanes méticuleux, réanalyse les deux versions du programme, vérifie les sommes de contrôle et recalcule chaque condition dont dépend la sécurité de la modification. Il ne croit aucune affirmation de l'optimiseur, même s'il a honnêtement indiqué ses calculs. Le mécanisme central est un théorème de cadre coopératif, mécanisé dans l'assistant de preuve Lean. Il stipule : une écriture dans une ressource qui est réécrite dans le même fil sans passer la main à l'ordonnanceur et sans observation externe peut être supprimée. Le théorème est paramétré par le type de ressource et la frontière d'observation ; une seule preuve couvre à la fois la suppression de variables mortes et la suppression de déplacements invisibles de sprites. Le contrôleur en Python implémente deux algorithmes de décision clés, dont les versions de référence ont été vérifiées en Lean et compilées en code exécutable. Une assurance supplémentaire est un oracle différentiel : après acceptation de la modification, il exécute les deux versions sur la machine virtuelle réelle de Scratch dans des conditions déterministes identiques et compare la trace visible par le joueur.
Résultats
L'expérience sur 300 projets choisis aléatoirement dans le dépôt public a montré que le contrôleur a accepté au moins une modification préservant le comportement dans 94.3% des cas (283 sur 300). Il s'agissait principalement de nettoyage de ressources inutilisées et de commentaires, mais des optimisations sémantiques plus profondes — suppression d'écritures visuellement mortes — ont réussi sur 17 projets. Le temps moyen de vérification d'un projet était de quelques dizaines de millisecondes, et la taille des données économisées atteignait des centaines de kilo-octets. Le résultat clé concerne la sécurité : un audit indépendant du système intégré a révélé huit fausses acceptations non détectées par les tests des familles individuelles. Toutes provenaient de canaux d'observation manqués — par exemple, l'indice de costume était lu par un autre sprite, et la suppression le décalait. Les erreurs ont été corrigées, et chacune est désormais couverte par un test de régression. Une campagne contradictoire inter-familles de 4278 modifications perturbées — avec ajout de changements superflus — n'a produit aucun faux rejet. Une ablation, où les conditions sémantiques étaient écartées, aurait conduit à accepter des dizaines de remplacements non sûrs, mais le contrôleur complet les a tous rejetés. L'oracle différentiel sur la machine virtuelle n'a enregistré aucune divergence de comportement parmi les modifications acceptées.
Implications
Ce résultat signifie que pour un langage parallèle orienté événements, on a pour la première fois construit un système de réécriture où chaque modification porte un certificat vérifiable par un noyau de confiance compact. Cela transfère la discipline des compilateurs vérifiés dans le domaine de l'utilisateur final, où le coût d'une erreur est particulièrement élevé. La métaphore douanière fonctionne en pratique : le contrôleur n'a pas besoin de comprendre comment l'optimiseur a trouvé le candidat à la suppression ; il vérifie simplement la « cargaison » par rapport à la « déclaration », et la cargaison est le programme lui-même. La paramétrisation par lentille d'observation permet de traiter uniformément les modifications sûres pour le joueur mais pas pour l'éditeur. Le théorème de cadre coopératif mécanisé ne repose que sur deux hypothèses de correspondance modèle-machine et ne dépend pas de la famille de modifications spécifique, ce qui le rend à la fois rigoureux et extensible. La base de confiance comprend environ dix mille lignes de Python et environ six mille lignes de Lean — un volume que peut auditer une petite équipe.
Développements futurs
Le cadre se transposera probablement à d'autres langages événementiels avec multithreading coopératif, car le théorème coopératif ne requiert qu'un ordonnanceur qui fixe explicitement les observations. L'objectif proche est de combler le fossé entre la référence vérifiée en Lean et le contrôleur déployé en Python grâce à l'extraction automatique de code, et d'étendre l'approche au multithreading préemptif. L'intégration dans l'éditeur réel de Scratch permettrait de montrer en temps réel à l'auteur des simplifications sûres qui ne perturbent pas l'intention du jeu. À terme, des systèmes hybrides où un grand modèle de langage propose des modifications et le contrôleur les évalue impartialement, comme il évalue actuellement les optimisations automatiques.
Impact
La méthodologie touche au développement d'environnements éducatifs de programmation, d'outils de refactorisation et de compilateurs vérifiés. Elle offre aussi un modèle pour construire des assistants IA de confiance générant du code : un générateur non vérifié produit une variante, et un contrôleur formel compact l'accepte ou la rejette.
Prochaines étapes
Il faut achever le pont de vérification entre le modèle prouvé en Lean et le contrôleur industriel en Python, et étendre la couverture des familles de modifications, par exemple à la fusion de scripts. En parallèle, il faut étudier le comportement du système sur de très grands projets avec des milliers de sprites.
Problèmes ouverts clés
Ce travail est directement lié au problème du traitement automatique fiable de programmes écrits par des non-spécialistes — un défi de longue date à l'intersection des méthodes formelles et de l'interaction homme-machine. Il illustre aussi comment des preuves paramétrées peuvent réduire le coût de vérification pour toute une classe d'optimisations, en faisant appel à des questions fondamentales de théorie de l'information sur la complétude des conditions de correction.
Le regard de la machine du savoir
Cette section s'adresse à l'auteur du travail et à ses collègues. Les travaux voisins ont été trouvés par une recherche sémantique dans notre archive, et non par correspondance de mots. Nous n'évaluons pas : nous montrons le champ autour.
Ce que fait ce travail
L'article présente CertiBlock, un système d'optimisation sûre pour les projets Scratch : un optimiseur non vérifié propose la suppression de code mort, tandis qu'un vérificateur de confiance valide chaque modification en s'appuyant sur un théorème de cadre mécanisé dans Lean. Les expériences menées sur 300 projets aléatoires montrent que le vérificateur a accepté au moins une modification préservant le comportement dans 94,3 % des cas.
Où est sa force
Le point fort réside dans la garantie formelle de préservation du comportement observable lors de l'optimisation, adaptée au multithreading coopératif et au modèle événementiel de Scratch, ce qui comble le fossé entre la vérification classique des compilateurs et les langages visuels réels.
Vers où avancer
- On pourrait envisager d'utiliser des méthodes d'apprentissage adaptatif pour ajuster les paramètres de la lentille d'observation : par exemple, déterminer automatiquement quels aspects du comportement sont importants pour un projet donné, en s'appuyant sur les retours des utilisateurs.appui : La correction d'erreurs quantiques apprend à la volée arXiv:2607.10707
- Il serait intéressant d'étudier comment le bruit et l'incertitude dans le comportement de la machine virtuelle Scratch peuvent être exploités pour renforcer la fiabilité de la vérification : par exemple, en ajoutant des perturbations aléatoires contrôlées lors des tests d'équivalence.appui : Le bruit qui aide à corriger les erreurs arXiv:2608.09583v1
- On pourrait explorer des approches de correction en temps réel, afin que le vérificateur puisse non seulement rejeter les modifications dangereuses, mais aussi proposer des corrections qui préservent l'intention de l'auteur.appui : Un traducteur quantique qui apprend de ses erreurs arXiv:2604.27648
À essayer
- Examiner si l'apprentissage par renforcement peut être utilisé pour générer automatiquement des lentilles qui maximisent la proportion de modifications sûres acceptées.
- Tester l'application de techniques de correction d'erreurs quantiques pour détecter des divergences subtiles dans les traces d'exécution.
- Expérimenter l'ajout de bruit dans la machine virtuelle afin de révéler des dépendances cachées à des facteurs non déterministes.
Travaux voisins dans notre archive
- L'écriture sans alphabet : comment le cerveau dessine des lettres qu'il n'a jamais vuesproximité 0.57
- La correction d'erreurs quantiques apprend à la voléeproximité 0.57
- États magiques : comment la distillation rend l'ordinateur quantique fiableproximité 0.56
- Le bruit qui aide à corriger les erreursproximité 0.56
- Magie quantique : non locale et éternelleproximité 0.56
- Un traducteur quantique qui apprend de ses erreursproximité 0.56
L'archive est vide autour de ce travail : l'analyse la plus proche n'est qu'à 0.57, contre 0,64 d'ordinaire. Il semble qu'on ait peu foré à côté.
Résumé original
tel que rédigé par les auteurs, en anglais arXiv:2607.00563
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.
L'audit du système, mené par un expert indépendant, a révélé huit fausses acceptations que les tests traditionnels sur chaque famille de modifications avaient manquées. Toutes étaient liées au fait qu'un sprite observait un autre par des canaux inattendus — par exemple, en lisant le numéro de costume qui changeait lors de la suppression d'une ressource inutilisée. Après correction, les erreurs ont été définitivement verrouillées par des tests de régression.
Chiffres clés
- proportion de projets avec optimisation réussie: 94.3% (283 sur 300)
- absence de fausses acceptations lors de l'attaque: 0 sur 4278 modifications perturbées
- lignes de code de confiance (Python): 9 921
- lignes de preuve mécanisée (Lean): 5 909
- temps moyen de vérification d'un projet: quelques dizaines de millisecondes