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

Technical Summary: Fixed-Set Robustness in Programming by Example

Problem Statement
Programming by Example (PBE) systems infer programs from small sets of input-output examples. While existing robustness research focuses on stochastic noise (e.g., random typos or data sampled from a noisy process), this paper investigates a distinct failure mode: fixed-set worst-case corruption. In this scenario, an adversary with white-box knowledge of the synthesizer ($S$) and hypothesis space ($H$) strategically selects a small number of examples ($k$) to corrupt. The goal is to force the synthesizer to return a program that is consistent with the corrupted examples but semantically incorrect on future inputs.

The paper argues that standard noisy-PBE models, which optimize for expected loss over a noise distribution, fail to address this threat because they do not account for the specific, targeted edits that exploit low-margin boundaries within the PBE version space.

Methodology
The authors formalize the problem and implement a suite of tools to evaluate and defend against this threat:

1. Threat Model & Formalization:

   • The adversary operates with a budget $k$ (number of corrupted example rows) and aims to maximize the semantic error of the returned program $S(\hat{E})$ against the intended program $p^*$.
   • The attack targets the margin between the target program and rival programs. A program $q$ becomes the winner if the adversary changes enough examples in the disagreement set $\Delta_E(p^*, q)$ to make $q$'s loss lower than or equal to $p^*$'s, considering simplicity costs and tie-breaking rules.

2. Attack Procedures:

   • Exact-within-bounded-pool: The system enumerates all possible output replacements for examples within a finite candidate set (derived from the DSL, constants, and source tokens) to find the optimal corruption.
   • Heuristic Search: For larger budgets, the paper implements greedy and beam search (width 32) to approximate the worst-case corruption.
   • Modes: The prototype supports output corruption, input corruption, example deletion, and example injection.

3. Defense: Version-Space Partition Aggregation (VPA):

   • VPA partitions the example set into $m$ disjoint groups.
   • The synthesizer runs independently on each group to produce candidate programs.
   • Candidates are evaluated on a finite vote domain $V$ to generate semantic signatures (vectors of outputs).
   • The system aggregates the results by selecting the candidate cluster with the largest number of votes (semantic signature).
   • Stability Certificate: The defense provides a certificate $\rho$ (based on the vote margin) indicating how many partition signatures can be altered before the output changes.

4. Evaluation Benchmarks:

   • Curated/Generated DSL Tasks: Controlled tasks with specific "margins" (1, 2, 3) to test theoretical thresholds.
   • Public SyGuS: A slice of accepted PBE string transformation tasks (SLIA) from the SyGuS competition.
   • Playgol: An external corpus of string transformation tasks.
   • LLM-PBE Harness: A small-scale test using exact-output prompts for LLMs to check if the phenomenon transfers to few-shot prompting.

Key Results
The evaluation supports three primary claims regarding the nature of PBE robustness:

1. Strategic Corruption $\neq$ Random Noise:

   • On curated low-margin tasks, a single strategic edit drives held-out accuracy from 1.000 to 0.000.
   • In contrast, random typo, same-pool random replacement, and distance-matched random controls succeed on only ~10–16% of trials.
   • This confirms that strategic attacks exploit specific version-space geometry that random noise does not.

2. Search Depth Matters:

   • Greedy search fails to find attacks on margin-2 and margin-3 tasks at budget 2, often missing the attack entirely.
   • Bounded exact search and beam search (width 32) successfully identify these attacks.
   • This implies that evaluating PBE robustness with only greedy adversaries yields false positives regarding system safety.

3. Conditional Efficacy of VPA:

   • Success Regime: VPA perfectly recovers (1.000 accuracy) on generated margin-1 tasks where the target semantics maintain a vote margin.
   • Failure Regime: On public SyGuS tasks, the clean vote margin is often near 1 (certified radius $\rho \approx 0$). In these cases, an adaptive attacker who knows the partitions can drive VPA accuracy to 0.000.
   • VPA is effective only when the target semantics retain a sufficient partition vote margin; it fails when the adversary controls a partition majority.

Significance and Claims
The paper deliberately frames its contribution as a boundary definition rather than a broad prevalence claim:

• Distinct Robustness Dimension: Fixed-set worst-case corruption is a separate problem from stochastic noise. Low-margin PBE tasks possess an adversarial vulnerability that standard noisy-PBE evaluations miss.
• Limitations of Defenses: Semantic partition aggregation (VPA) is not a universal fix. It provides a certificate of stability only when the vote margin is sufficient. On realistic public tasks where margins are thin, VPA offers no protection against an adaptive attacker.
• Scope of Evaluation: The findings are grounded in a deterministic string DSL and specific public benchmarks (SyGuS, Playgol). The paper explicitly notes that FlashFill, PROSE, and code-generation benchmarks remain future targets.
• LLM Relevance: A small-scale harness shows that the "strategic example sensitivity" observed in symbolic PBE also manifests in exact-output LLM prompting, suggesting the vulnerability is structural to the few-shot interface rather than specific to symbolic solvers.

The paper concludes that robustness in PBE requires explicit attention to version-space margins and that defenses like VPA must be accompanied by certificates indicating when they are likely to fail.