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

Resumen Técnico: Robustez de Conjunto Fijo en Programación por Ejemplo

Planteamiento del Problema
Los sistemas de Programación por Ejemplo (PBE, por sus siglas en inglés) infieren programas a partir de pequeños conjuntos de ejemplos de entrada-salida. Mientras que la investigación actual sobre robustez se centra en el ruido estocástico (por ejemplo, errores tipográficos aleatorios o datos muestreados de un proceso ruidoso), este artículo investiga un modo de fallo distinto: la corrupción de peor caso de conjunto fijo. En este escenario, un adversario con conocimiento de caja blanca del sintetizador ($S$) y del espacio de hipótesis ($H$) selecciona estratégicamente un número pequeño de ejemplos ($k$) para corromperlos. El objetivo es forzar al sintetizador a devolver un programa que sea consistente con los ejemplos corrompidos pero semánticamente incorrecto en futuras entradas.

El artículo argumenta que los modelos estándar de PBE con ruido, que optimizan la pérdida esperada sobre una distribución de ruido, no logran abordar esta amenaza porque no tienen en cuenta las ediciones específicas y dirigidas que explotan los límites de bajo margen dentro del espacio de versiones de PBE.

Metodología
Los autores formalizan el problema e implementan un conjunto de herramientas para evaluar y defenderse contra esta amenaza:

1. Modelo de Amenaza y Formalización:

   • El adversario opera con un presupuesto $k$ (número de filas de ejemplos corrompidas) y busca maximizar el error semántico del programa devuelto $S(\hat{E})$ frente al programa objetivo $p^*$.
   • El ataque apunta al margen entre el programa objetivo y los programas rivales. Un programa $q$ se convierte en el ganador si el adversario cambia suficientes ejemplos en el conjunto de desacuerdo $\Delta_E(p^*, q)$ para que la pérdida de $q$ sea menor o igual a la de $p^*$, considerando los costos de simplicidad y las reglas de desempate.

2. Procedimientos de Ataque:

   • Exact-within-bounded-pool (Exacto dentro de un conjunto limitado): El sistema enumera todos los reemplazos de salida posibles para los ejemplos dentro de un conjunto de candidatos finito (derivado del DSL, constantes y tokens de origen) para encontrar la corrupción óptima.
   • Búsqueda Heurística: Para presupuestos más grandes, el artículo implementa búsqueda codiciosa (greedy) y búsqueda de haz (beam search con anchura 32) para aproximar la corrupción de peor caso.
   • Modos: El prototipo soporta corrupción de salida, corrupción de entrada, eliminación de ejemplos e inyección de ejemplos.

3. Defensa: Agregación de Partición del Espacio de Versiones (VPA):

   • VPA particiona el conjunto de ejemplos en $m$ grupos disjuntos.
   • El sintetizador se ejecuta de forma independiente en cada grupo para producir programas candidatos.
   • Los candidatos se evalúan en un dominio de votación finito $V$ para generar firmas semánticas (vectores de salidas).
   • El sistema agrega los resultados seleccionando el clúster de candidatos con el mayor número de votos (firma semántica).
   • Certificado de Estabilidad: La defensa proporciona un certificado $\rho$ (basado en el margen de votación) que indica cuántas firmas de partición pueden ser alteradas antes de que la salida cambie.

4. Benchmarks de Evaluación:

   • Tareas de DSL Curadas/Generadas: Tareas controladas con "márgenes" específicos (1, 2, 3) para probar umbrales teóricos.
   • SyGuS Público: Una sección de tareas de transformación de cadenas aceptadas (SLIA) de la competencia SyGuS.
   • Playgol: Un corpus externo de tareas de transformación de cadenas.
   • Harness LLM-PBE: Una prueba a pequeña escala utilizando prompts de salida exacta para LLMs para comprobar si el fenómeno se transfiere al prompting de pocos disparos (few-shot).

Resultos Clave
La evaluación respalda tres afirmaciones principales respecto a la naturaleza de la robustez en PBE:

1. Corrupción Estratégica $\neq$ Ruido Aleatorio:

   • En tareas curadas de bajo margen, una única edición estratégica reduce la precisión de held-out de 1.000 a 0.000.
   • En contraste, el error tipográfico aleatorio, el reemplazo aleatorio dentro del mismo conjunto y los controles aleatorios de distancia igualada tienen éxito en solo ~10–16% de los ensayos.
   • Esto confirma que los ataques estratégicos explotan la geometría específica del espacio de versiones que el ruido aleatorio no explota.

2. La Profundidad de Búsqueda Importa:

   • La búsqueda codiciosa (greedy) falla al encontrar ataques en tareas de margen-2 y margen-3 con un presupuesto de 2, perdiendo a menudo el ataque por completo.
   • La búsqueda exacta acotada y la búsqueda de haz (anchura 32) identifican con éxito estos ataques.
   • Esto implica que evaluar la robustez de PBE utilizando únicamente adversarios codiciosos genera falsos positivos sobre la seguridad del sistema.

3. Eficacia Condicional de VPA:

   • Régimen de Éxito: VPA recupera perfectamente (precisión de 1.000) en tareas generadas de margen-1 donde la semántica objetivo mantiene un margen de votación.
   • Régimen de Fallo: En tareas públicas de SyGuS, el margen de votación limpio suele ser cercano a 1 (radio certificado $\rho \approx 0$). En estos casos, un atacante adaptativo que conoce las particiones puede llevar la precisión de VPA a 0.000.
   • VPA es efectivo solo cuando la semántica objetivo retiene un margen de votación de partición suficiente; falla cuando el adversario controla la mayoría de las particiones.

Significación y Reivindicaciones
El artículo enmarca deliberadamente su contribución como una definición de frontera en lugar de una afirmación de prevalencia general:

• Dimensión de Robustez Distinta: La corrupción de peor caso de conjunto fijo es un problema separado del ruido estocástico. Las tareas de PBE de bajo margen poseen una vulnerabilidad adversaria que las evaluaciones de PBE con ruido estándar pasan por alto.
• Limitaciones de las Defensas: La agregación de partición semántica (VPA) no es una solución universal. Proporciona un certificado de estabilidad solo cuando el margen de votación es suficiente. En tareas públicas realistas donde los márgenes son estrechos, VPA no ofrece protección contra un atacante adaptativo.
• Alcance de la Evaluación: Los hallazgos se basan en un DSL de cadenas determinista y benchmarks públicos específicos (SyGuS, Playgol). El artículo señala explícitamente que FlashFill, PROSE y los benchmarks de generación de código siguen siendo objetivos futuros.
• Relevancia para LLM: Un pequeño harness muestra que la "sensibilidad estratégica de los ejemplos" observada en el PBE simbólico también se manifiesta en el prompting de salida exacta de los LLM, lo que sugiere que la vulnerabilidad es estructural a la interfaz de pocos disparos (few-shot) más que específica de los solvers simbólicos.

El artículo concluye que la robustez en PBE requiere atención explícita a los márgenes del espacio de versiones y que las defensas como VPA deben ir acompañadas de certificados que indiquen cuándo es probable que fallen.