Fixed-Set Robustness in Programming by Example: Example Corruption and Semantic Partition Recovery

Résumé Technique : Robustesse des ensembles fixes dans la Programmation par l'Exemple

Énoncé du Problème
Les systèmes de Programmation par l'Exemple (PBE - Programming by Example) infèrent des programmes à partir de petits ensembles d'exemples d'entrée-sortie. Alors que la recherche actuelle sur la robustesse se concentre sur le bruit stochastique (par exemple, des fautes de frappe aléatoires ou des données échantillonnées à partir d'un processus bruité), cet article étudie un mode de défaillance distinct : la corruption par pire cas d'un ensemble fixe. Dans ce scénario, un adversaire possédant une connaissance "boîte blanche" du synthétiseur ($S$) et de l'espace d'hypothèses ($H$) sélectionne stratégiquement un petit nombre d'exemples ($k$) à corrompre. Le but est de forcer le synthétiseur à retourner un programme qui est cohérent avec les exemples corrompus mais sémantiquement incorrect sur de futures entrées.

L'article soutient que les modèles PBE standards, qui optimisent la perte attendue sur une distribution de bruit, ne parviennent pas à traiter cette menace car ils ne tiennent pas compte des éditions ciblées spécifiques qui exploitent les frontières à faible marge au sein de l'espace de versions (version space) du PBE.

Méthodologie
Les auteurs formalisent le problème et implémentent une suite d'outils pour évaluer et défendre contre cette menace :

1. Modèle de Menace et Formalisation :

   • L'adversaire opère avec un budget $k$ (nombre de lignes d'exemples corrompues) et vise à maximiser l'erreur sémantique du programme retourné $S(\hat{E})$ par rapport au programme cible $p^*$.
   • L'attaque cible la marge entre le programme cible et les programmes rivaux. Un programme $q$ devient le vainqueur si l'adversaire modifie suffisamment d'exemples dans l'ensemble de désaccord $\Delta_E(p^*, q)$ pour que la perte de $q$ soit inférieure ou égale à celle de $p^*$, en tenant compte des coûts de simplicité et des règles de départage.

2. Procédures d'Attaque :

   • Exact-within-bounded-pool (Exact à l'intérieur d'un pool borné) : Le système énumère tous les remplacements de sortie possibles pour les exemples au sein d'un ensemble de candidats fini (dérivé du DSL, des constantes et des jetons sources) pour trouver la corruption optimale.
   • Recherche Heuristique : Pour des budgets plus importants, l'article implémente une recherche gloutonne (greedy) et une recherche en faisceau (beam search, largeur 32) pour approximer la corruption dans le pire des cas.
   • Modes : Le prototype prend en charge la corruption de sortie, la corruption d'entrée, la suppression d'exemple et l'injection d'exemple.

3. Défense : Agrégation de Partition de l'Espace de Versions (VPA - Version-Space Partition Aggregation) :

   • VPA partitionne l'ensemble d'exemples en $m$ groupes disjoints.
   • Le synthétiseur s'exécute indépendamment sur chaque groupe pour produire des programmes candidats.
   • Les candidats sont évalués sur un domaine de vote fini $V$ pour générer des signatures sémantiques (vecteurs de sorties).
   • Le système agrège les résultats en sélectionnant le cluster de candidats possédant le plus grand nombre de votes (signature sémantique).
   • Certificat de Stabilité : La défense fournit un certificat $\rho$ (basé sur la marge de vote) indiquant combien de signatures de partition peuvent être altérées avant que la sortie ne change.

4. Benchmarks d'Évaluation :

   • Tâches DSL Curatées/Générées : Tâches contrôlées avec des "marges" spécifiques (1, 2, 3) pour tester les seuils théoriques.
   • SyGuS Public : Une tranche de tâches de transformation de chaînes de caractères acceptées (SLIA) de la compétition SyGuS.
   • Playgol : Un corpus externe de tâches de transformation de chaînes.
   • Harnais LLM-PBE : Un test à petite échelle utilisant des prompts de sortie exacte pour les LLM afin de vérifier si le phénomène se transfère au few-shot prompting.

Résultats Clés
L'évaluation soutient trois affirmations principales concernant la nature de la robustesse du PBE :

1. Corruption Stratégique $\neq$ Bruit Aléatoire :

   • Sur des tâches curatées à faible marge, une seule édition stratégique fait chuter la précision sur les données non vues de 1.000 à 0.000.
   • En revanche, les contrôles de type faute de frappe aléatoire, remplacement aléatoire dans le même pool et contrôle aléatoire de distance correspondante ne réussissent que dans environ 10 à 16 % des essais.
   • Ceci confirme que les attaques stratégiques exploitent une géométrie spécifique de l'espace de versions que le bruit aléatoire n'exploite pas.

2. La Profondeur de Recherche Compte :

   • La recherche gloutonne échoue à trouver des attaques sur les tâches de marge 2 et 3 avec un budget de 2, manquant souvent l'attaque.
   • La recherche exacte bornée et la recherche en faisceau (largeur 32) identifient avec succès ces attaques.
   • Cela implique qu'évaluer la robustesse du PBE avec uniquement des adversaires gloutons produit des faux positifs concernant la sécurité du système.

3. Efficacité Conditionnelle de VPA :

   • Régime de Succès : VPA récupère parfaitement (précision 1.000) sur les tâches de marge 1 générées, là où la sémantique cible maintient une marge de vote.
   • Régime d'Échec : Sur les tâches publiques SyGuS, la marge de vote propre est souvent proche de 1 (rayon certifié $\rho \approx 0$). Dans ces cas, un attaquant adaptatif qui connaît les partitions peut faire tomber la précision de VPA à 0.000.
   • VPA est efficace uniquement lorsque la sémantique cible conserve une marge de vote de partition suffisante ; elle échoue lorsque l'adversaire contrôle une majorité de partitions.

Signification et Revendications
L'article cadre délibérément sa contribution comme une définition de frontière plutôt que comme une affirmation de prévalence large :

• Dimension de Robustesse Distincte : La corruption par pire cas d'un ensemble fixe est un problème distinct du bruit stochastique. Les tâches PBE à faible marge possèdent une vulnérabilité adversaire que les évaluations de PBE bruyantes standards ne détectent pas.
• Limites des Défenses : L'agrégation de partition sémantique (VPA) n'est pas une solution universelle. Elle fournit un certificat de stabilité uniquement lorsque la marge de vote est suffisante. Sur des tâches publiques réalistes où les marges sont fines, VPA n'offre aucune protection contre un attaquant adaptatif.
• Portée de l'Évaluation : Les conclusions sont ancrées dans un DSL de chaînes déterministe et des benchmarks spécifiques (SyGuS, Playgol). L'article note explicitement que FlashFill, PROSE et les benchmarks de génération de code restent des cibles futures.
• Pertinence LLM : Un harnais à petite échelle montre que la "sensibilité stratégique aux exemples" observée dans le PBE symbolique se manifeste également dans le prompting de sortie exacte des LLM, suggérant que la vulnérabilité est structurelle à l'interface few-shot plutôt qu'spécifique aux solveurs symboliques.

L'article conclut que la robustesse dans le PBE nécessite une attention explicite aux marges de l'espace de versions et que les défenses comme VPA doivent être accompagnées de certificats indiquant quand elles sont susceptibles d'échouer.