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

Resumo Técnico: Robustez de Conjunto Fixo em Programação por Exemplo

Definição do Problema
Sistemas de Programação por Exemplo (PBE) inferem programas a partir de pequenos conjuntos de exemplos de entrada-saída. Enquanto a pesquisa de robustez existente foca em ruído estocástico (ex: erros de digitação aleatórios ou dados amostrados de um processo ruidoso), este artigo investiga um modo de falha distinto: a corrupção de pior caso de conjunto fixo. Neste cenário, um adversário com conhecimento white-box do sintetizador ($S$) e do espaço de hipóteses ($H$) seleciona estrategicamente um pequeno número de exemplos ($k$) para corromper. O objetivo é forçar o sintetizador a retornar um programa que seja consistente com os exemplos corrompidos, mas semanticamente incorreto em entradas futuras.

O artigo argumenta que modelos de PBE ruidosos padrão, que otimizam a perda esperada sobre uma distribuição de ruído, falham em abordar esta ameaça porque não consideram as edições específicas e direcionadas que exploram as fronteiras de baixa margem dentro do espaço de versão do PBE.

Metodologia
Os autores formalizam o problema e implementam um conjunto de ferramentas para avaliar e defender contra esta ameaça:

1. Modelo de Ameaça e Formalização:

   • O adversário opera com um orçamento $k$ (número de linhas de exemplos corrompidas) e visa maximizar o erro semântico do programa retornado $S(\hat{E})$ contra o programa pretendido $p^*$.
   • O ataque visa a margem entre o programa alvo e programas rivais. Um programa $q$ torna-se o vencedor se o adversário alterar exemplos suficientes no conjunto de discordância $\Delta_E(p^*, q)$ para tornar a perda de $q$ menor ou igual à de $p^*$, considerando custos de simplicidade e regras de desempate.

2. Procedimentos de Ataque:

   • Exato dentro de pool limitado (Exact-within-bounded-pool): O sistema enumera todas as substituições de saída possíveis para exemplos dentro de um conjunto candidato finito (derivado da DSL, constantes e tokens de origem) para encontrar a corrupção ótima.
   • Busca Heurística: Para orçamentos maiores, o artigo implementa busca gananciosa (greedy) e busca por feixe (beam search, largura 32) para aproximar a corrupção de pior caso.
   • Modos: O protótipo suporta corrupção de saída, corrupção de entrada, deleção de exemplos e injeção de exemplos.

3. Defesa: Agregação de Partição do Espaço de Versão (VPA):

   • VPA particiona o conjunto de exemplos em $m$ grupos disjuntos.
   • O sintetizador executa independentemente em cada grupo para produzir programas candidatos.
   • Os candidatos são avaliados em um domínio de votação finito $V$ para gerar assinaturas semânticas (vetores de saídas).
   • O sistema agrega os resultados selecionando o cluster de candidatos com o maior número de votos (assinatura semântica).
   • Certificado de Estabilidade: A defesa fornece um certificado $\rho$ (baseado na margem de voto) indicando quantos assinaturas de partição podem ser alteradas antes que a saída mude.

4. Benchmarks de Avaliação:

   • Tarefas de DSL Curadas/Geradas: Tarefas controladas com "margens" específicas (1, 2, 3) para testar limiares teóricos.
   • SyGuS Público: Uma fatia de tarefas de transformação de strings aceitas (SLIA) da competição SyGuS.
   • Playgol: Um corpus externo de tarefas de transformação de strings.
   • Harness LLM-PBE: Um teste em pequena escala usando prompts de saída exata para LLMs para verificar se o fenômeno se transfere para o few-shot prompting.

Resultos Principais
A avaliação apoia três afirmações primárias sobre a natureza da robustez em PBE:

1. Corrupção Estratégica $\neq$ Ruído Aleatório:

   • Em tarefas curadas de baixa margem, uma única edição estratégica leva a precisão em dados não vistos de 1.000 para 0.000.
   • Em contraste, controles de erro de digitação aleatório, substituição aleatória no mesmo pool e controle de distância correspondente têm sucesso em apenas ~10–16% dos ensaios.
   • Isso confirma que ataques estratégicos exploram a geometria específica do espaço de versão que o ruído aleatório não explora.

2. A Profundidade de Busca Importa:

   • A busca gananciosa falha em encontrar ataques em tarefas de margem-2 e margem-3 com orçamento 2, muitas vezes perdendo o ataque completamente.
   • Busca exata limitada e busca por feixe (largura 32) identificam com sucesso esses ataques.
   • Isso implica que avaliar a robustez do PBE apenas com adversários gananciosos gera falsos positivos sobre a segurança do sistema.

3. Eficácia Condicional do VPA:

   • Regime de Sucesso: VPA recupera perfeitamente (precisão 1.000) em tarefas de margem-1 geradas onde a semântica alvo mantém uma margem de voto.
   • Regime de Falha: Em tarefas públicas do SyGuS, a margem de voto limpa é frequentemente próxima de 1 (raio certificado $\rho \approx 0$). Nesses casos, um atacante adaptativo que conhece as partições pode levar a precisão do VPA a 0.000.
   • VPA é eficaz apenas quando a semântica alvo retém uma margem de voto de partição suficiente; ele falha quando o adversário controla a maioria das partições.

Significância e Alegações
O artigo enquadra deliberadamente sua contribuição como uma definição de fronteira em vez de uma afirmação de prevalência ampla:

• Dimensão de Robustez Distinta: A corrupção de pior caso de conjunto fixo é um problema separado do ruído estocástico. Tarefas de PBE de baixa margem possuem uma vulnerabilidade adversarial que as avaliações de PBE ruidoso padrão não detectam.
• Limitações de Defesas: A agregação de partição semântica (VPA) não é uma correção universal. Ela fornece um certificado de estabilidade apenas quando a margem de voto é suficiente. Em tarefas públicas realistas onde as margens são finas, o VPA não oferece proteção contra um atacante adaptativo.
• Escopo da Avaliação: Os achados são fundamentados em uma DSL de string determinística e benchmarks públicos específicos (SyGuS, Playgol). O artigo nota explicitamente que FlashFill, PROSE e benchmarks de geração de código permanecem como alvos futuros.
• Relevância para LLM: Um harness em pequena escala mostra que a "sensibilidade estratégica a exemplos" observada no PBE simbólico também se manifesta no prompting de saída exata de LLMs, sugerindo que a vulnerabilidade é estrutural à interface de few-shot e não específica de solvers simbólicos.

O artigo conclui que a robustez em PBE requer atenção explícita às margens do espaço de versão e que defesas como o VPA devem ser acompanhadas de certificados indicando quando é provável que falhem.