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

arXiv: https://arxiv.org/abs/2607.01280 · HTML: https://mlsanity.com/paper/2607.01280/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 37 of its 67 references that are in the map.
- First posted on arXiv 1 Jul 2026.

## Builds on (most cited first, 30 of 37)

- [Explaining and Harnessing Adversarial Examples](https://mlsanity.com/paper/1412.6572/) (2014)
- [Towards Deep Learning Models Resistant to Adversarial Attacks](https://mlsanity.com/paper/1706.06083/) (2017)
- [Intriguing properties of neural networks](https://mlsanity.com/paper/1312.6199/) (2013)
- [Not what you've signed up for: Compromising Real-World LLM-Integrated Applications with Indirect Prompt Injection](https://mlsanity.com/paper/2302.12173/) (2023)
- [Certified Adversarial Robustness via Randomized Smoothing](https://mlsanity.com/paper/1902.02918/) (2019)
- [Poison Frogs! Targeted Clean-Label Poisoning Attacks on Neural Networks](https://mlsanity.com/paper/1804.00792/) (2018)
- [Spectral Signatures in Backdoor Attacks](https://mlsanity.com/paper/1811.00636/) (2018)
- [Weight Poisoning Attacks on Pre-trained Models](https://mlsanity.com/paper/2004.06660/) (2020)
- [Certified Defenses for Data Poisoning Attacks](https://mlsanity.com/paper/1706.03691/) (2017)
- [Poisoning Web-Scale Training Datasets is Practical](https://mlsanity.com/paper/2302.10149/) (2023)
- [PoisonedRAG: Knowledge Corruption Attacks to Retrieval-Augmented Generation of Large Language Models](https://mlsanity.com/paper/2402.07867/) (2024)
- [Robust Estimators in High Dimensions without the Computational Intractability](https://mlsanity.com/paper/1604.06443/) (2016)
- [DeepCoder: Learning to Write Programs](https://mlsanity.com/paper/1611.01989/) (2016)
- [You Autocomplete Me: Poisoning Vulnerabilities in Neural Code Completion](https://mlsanity.com/paper/2007.02220/) (2020)
- [RobustFill: Neural Program Learning under Noisy I/O](https://mlsanity.com/paper/1703.07469/) (2017)
- [Deep Partition Aggregation: Provable Defense against General Poisoning Attacks](https://mlsanity.com/paper/2006.14768/) (2020)
- [Certified Robustness to Label-Flipping Attacks via Randomized Smoothing](https://mlsanity.com/paper/2002.03018/) (2020)
- [Leveraging Grammar and Reinforcement Learning for Neural Program Synthesis](https://mlsanity.com/paper/1805.04276/) (2018)
- [TrojanPuzzle: Covertly Poisoning Code-Suggestion Models](https://mlsanity.com/paper/2301.02344/) (2023)
- [Improved Certified Defenses against Data Poisoning with (Deterministic) Finite Aggregation](https://mlsanity.com/paper/2202.02628/) (2022)
- [Practical Poisoning Attacks against Retrieval-Augmented Generation](https://mlsanity.com/paper/2504.03957/) (2025)
- [Is Programming by Example solved by LLMs?](https://mlsanity.com/paper/2406.08316/) (2024)
- [Data Poisoning for In-context Learning](https://mlsanity.com/paper/2402.02160/) (2024)
- [Program Synthesis from Polymorphic Refinement Types](https://mlsanity.com/paper/1510.08419/) (2015)
- [Representing Partial Programs with Blended Abstract Semantics](https://mlsanity.com/paper/2012.12964/) (2020)
- [Exploring the Security Threats of Knowledge Base Poisoning in Retrieval-Augmented Code Generation](https://mlsanity.com/paper/2502.03233/) (2025)
- [Inductive Program Synthesis Over Noisy Data](https://mlsanity.com/paper/2009.10272/) (2020)
- [Automated Feedback Generation for Competition-Level Code](https://mlsanity.com/paper/2206.01848/) (2022)
- [A Systematic Study of Time Limit Exceeded Errors in Online Programming Assignments](https://mlsanity.com/paper/2510.14339/) (2025)
- [ViScratch: Using Large Language Models and Gameplay Videos for Automated Feedback in Scratch](https://mlsanity.com/paper/2509.11065/) (2025)

## Abstract (arXiv)

Programming-by-example systems infer programs from a small set of input-output examples. Robust PBE work usually models wrong examples as samples from a stochastic noise process and then minimizes an expected or empirical loss. This paper studies a different failure mode: an adversary who sees the synthesizer and chooses the examples whose corruption most damages the returned program. We formalize fixed-set worst-case corruption for finite PBE version spaces, implement exact-within-bounded-pool and heuristic corruption searches for a string-transformation DSL, and introduce version-space partition aggregation (VPA), a defense that synthesizes on disjoint example groups and votes by semantic signatures. The central claim is deliberately bounded and partly negative: low-margin PBE tasks have an adversarial robustness dimension that random-typo and noisy-PBE evaluations miss, while semantic partition aggregation helps only when the clean semantics keep a partition vote margin, which often fails on realistic tasks. Evidence from curated/generated DSL tasks, accepted public SyGuS PBE_SLIA slices, SYNTRA Playgol v2, and noisy-PBE objective baselines supports that boundary. One curated edit flips all 8 spike tasks while 200-trial typo, DSL-pool, and distance-matched random controls succeed on 10.3%, 11.0%, and 16.7%; generated margin-1 rows flip under budget 1 yet VPA recovers them; on public SyGuS the vote margin is near one, so an adaptive attacker drives VPA accuracy to zero; accepted public SyGuS slices move across exact-within-pool budget boundaries; and Playgol shows positive paired-bootstrap gaps against typo and same-pool random controls on the 141 accepted rows. A small exact-output prompt harness over 20 controlled margin-1 tasks shows the same qualitative clean-to-attacked pattern across local and API models, while it is treated as a scope check, not a broad LLM benchmark.