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

Sintesi Tecnica: Robustezza di Set Fissi nella Programmazione per Esempio

Definizione del Problema
I sistemi di Programmazione per Esempio (PBE) inferiscono programmi da piccoli set di esempi di input-output. Mentre la ricerca esistente sulla robustezza si concentra sul rumore stocastico (ad esempio, errori di battitura casuali o dati campionati da un processo rumoroso), questo articolo investiga una modalità di fallimento distinta: la corruzione peggiore del caso per set fissi. In questo scenario, un avversario con conoscenza white-box del sintetizzatore ($S$) e dello spazio delle ipotesi ($H$) seleziona strategicamente un piccolo numero di esempi ($k$) da corrompere. L'obiettivo è costringere il sintetizzatore a restituire un programma che sia coerente con gli esempi corrotti ma semanticamente errato sugli input futuri.

L'articolo sostiene che i modelli standard di noisy-PBE, che ottimizzano la perdita attesa su una distribuzione di rumore, non riescono ad affrontare questa minaccia perché non tengono conto delle modifiche specifiche e mirate che sfruttano i margini bassi all'interno dello spazio delle versioni (version space) del PBE.

Metodologia
Gli autori formalizzano il problema e implementano una suite di strumenti per valutare e difendere contro questa minaccia:

1. Modello di Minaccia e Formalizzazione:

   • L'avversario opera con un budget $k$ (numero di righe di esempi corrotte) e mira a massimizzare l'errore semantico del programma restituito $S(\hat{E})$ rispetto al programma target $p^*$.
   • L'attacco mira al margine tra il programma target e i programmi rivali. Un programma $q$ diventa il vincitore se l'avversario modifica abbastanza esempi nell'insieme di disaccordo $\Delta_E(p^*, q)$ da rendere la perdita di $q$ inferiore o uguale a quella di $p^*$, considerando i costi di semplicità e le regole di risoluzione dei pareggi.

2. Procedure di Attacco:

   • Exact-within-bounded-pool: Il sistema enumera tutte le possibili sostituzioni di output per gli esempi all'interno di un insieme candidato finito (derivato dal DSL, dalle costanti e dai token sorgente) per trovare la corruzione ottimale.
   • Ricerca Euristica: Per budget più ampi, l'articolo implementa una ricerca greedy e una beam search (larghezza 32) per approssimare la corruzione peggiore del caso.
   • Modalità: Il prototipo supporta la corruzione dell'output, la corruzione dell'input, la cancellazione di esempi e l'iniezione di esempi.

3. Difesa: Aggregazione delle Partizioni dello Spazio delle Versioni (VPA):

   • VPA partiziona l'insieme degli esempi in $m$ gruppi disgiunti.
   • Il sintetizzatore viene eseguito indipendentemente su ciascun gruppo per produrre programmi candidati.
   • I candidati vengono valutati su un dominio di voto $V$ per generare firme semantiche (vettori di output).
   • Il sistema aggrega i risultati selezionando il cluster di candidati con il maggior numero di voti (firma semantica).
   • Certificato di Stabilità: La difesa fornisce un certificato $\rho$ (basato sul margine di voto) che indica quanti segni delle partizioni possono essere alterati prima che l'output cambi.

4. Benchmark di Valutazione:

   • Compiti DSL Curati/Generati: Compiti controllati con margini specifici (1, 2, 3) per testare le soglie teoriche.
   • SyGuS Pubblico: Una porzione di compiti di trasformazione di stringhe SLIA accettati nella competizione SyGuS.
   • Playgol: Un corpus esterno di compiti di trasformazione di stringhe.
   • LLM-PBE Harness: Un piccolo test utilizzando prompt a output esatto per verificare se il fenomeno si trasferisce al prompting few-shot degli LLM.

Risultati Chiave
La valutazione supporta tre rivendicazioni primarie riguardanti la natura della robustezza del PBE:

1. Corruzione Strategica $\neq$ Rumore Casuale:

   • Su compiti curati a basso margine, una singola modifica strategica porta l'accuratezza sui dati non visti da 1.000 a 0.000.
   • Al contrario, il controllo di errori di battitura casuali, sostituzione casuale nello stesso pool e controllo basato sulla distanza hanno successo solo in circa il 10–16% delle prove.
   • Ciò conferma che gli attacchi strategici sfruttano la geometria specifica dello spazio delle versioni che il rumore casuale non coglie.

2. La Profondità di Ricerca Conta:

   • La ricerca greedy fallisce nel trovare attacchi su compiti con margine-2 e margine-3 con un budget di 2, mancando spesso l'attacco completamente.
   • La ricerca esatta limitata (bounded exact search) e la beam search (larghezza 32) identificano con successo questi attacchi.
   • Ciò implica che valutare la robustezza del PBE con soli avversari greedy produce falsi positivi riguardo alla sicurezza del sistema.

3. Efficacia Condizionata di VPA:

   • Regime di Successo: VPA recupera perfettamente (accuratezza 1.000) su compiti generati con margine-1 dove la semantica target mantiene un margine di voto.
   • Regime di Fallimento: Sui compiti SyGuS pubblici, il margine di voto pulito è spesso vicino a 1 (raggio certificato $\rho \approx 0$). In questi casi, un attaccante adattivo che conosce le partizioni può portare l'accuratezza di VPA a 0.000.
   • VPA è efficace solo quando la semantica target mantiene un margine di voto di partizione sufficiente; fallisce quando l'avversario controlla una maggioranza di partizioni.

Significatività e Rivendicazioni
L'articolo inquadra deliberatamente il proprio contributo come una definizione di confine piuttosto che una rivendicazione di prevalenza generale:

• Dimensione di Robustezza Distinta: La corruzione peggiore del caso per set fissi è un problema distinto dal rumore stocastico. I compiti PBE a basso margine possiedono una vulnerabilità avversaria che le valutazioni standard del noisy-PBE non colgono.
• Limitazioni delle Difese: L'aggregazione semantica delle partizioni (VPA) non è una soluzione universale. Fornisce un certificato di stabilità solo quando il margine di voto è sufficiente. Sui compiti pubblici realistici dove i margini sono sottili, VPA non offre protezione contro un attaccante adattivo.
• Ambito di Valutazione: Le scoperte sono basate su un DSL di stringhe deterministico e su specifici benchmark pubblici (SyGuS, Playgol). L'articolo nota esplicitamente che FlashFill, PROSE e i benchmark di generazione di codice rimangono obiettivi futuri.
• Rilevanza per gli LLM: Un piccolo harness mostra che la "sensibilità strategica agli esempi" osservata nel PBE simbolico si manifesta anche nel prompting a output esatto degli LLM, suggerendo che la vulnerabilità è strutturale all'interfaccia few-shot piuttosto che specifica per i solver simbolici.

L'articolo conclude che la robustezza nel PBE richiede un'attenzione esplicita ai margini dello spazio delle versioni e che le difese come VPA devono essere accompagnate da certificati che indichino quando è probabile che falliscano.