arXiv:2607.01280cs.LGcs.PL2026-07

研究编程示例系统在恶意示例污染下的脆弱性,提出防御方法并揭示现有评估的盲区。

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

  • 设计对抗性污染测试,模拟攻击者精心选择破坏性示例
  • 提出语义分组聚合防御,在清洁语义有投票余量时有效
  • 实验证明常规评估忽略对抗鲁棒性,真实任务中防御常失效

编程示例(PBE)系统通过少量输入输出示例推断程序。传统鲁棒性研究将错误示例视为随机噪声,最小化期望或经验损失。本文研究另一种失效模式:攻击者观察合成器后,选择最损害生成程序的示例进行污染。针对有限版本空间的固定集最坏情况污染,我们实现了基于边界池的精确搜索与启发式污染搜索,并提出版本空间分组聚合(VPA)防御机制,对不相交示例组分别合成并按语义签名投票。核心结论是部分负面但明确:低置信度的PBE任务存在随机打字错误和噪声评估无法捕捉的对抗鲁棒性维度;而VPA仅在清洁语义保持投票余量时有效,这在真实任务中常不成立。在精心构造/生成的DSL任务、公开的SyGuS PBE_SLIA片段、SYNTRA Playgol v2及噪声评估基线上的证据支持此结论:一个手动编辑可使全部8个尖峰任务失败,而200次打字错误、DSL池和距离匹配的随机控制在10.3%、11.0%、16.7%下成功;生成的边际为1的行在预算内被攻破,但VPA可恢复;在公开SyGuS中投票余量接近1,自适应攻击使VPA准确率降至零;接受的SyGuS片段跨越精确池内预算边界;Playgol显示在141个接受行上,配对自助法相对于打字错误和同池随机控制有正差距。一个小规模精确输出提示在超过20个受控边际1任务上表现出一致的从清洁到攻击的模式,而该模式被视为范围检查,非广泛大模型基准。

原文摘要 · Abstract (English)

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.

编程示例对抗鲁棒性语义分组

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。