示例编程中的固定集鲁棒性：示例破坏与语义分区恢复
本文研究编程示例系统的对抗性鲁棒性，提出一种新攻击模式：对手观察合成器并选择最有害的示例进行破坏。作者形式化了有限版本空间下的最坏情况破坏，实现了精确搜索和启发式搜索，并引入版本空间分区聚合（VPA）防御。实验表明，低裕度任务存在随机噪声评估忽略的对抗鲁棒性维度，而VPA仅在清洁语义保持分区投票裕度时有效，这在现实任务中常失败。
编程示例（Programming by Example, PBE）系统通过少量输入输出示例推断程序，在自动化编程中具有重要应用。然而，现有鲁棒PBE工作通常将错误示例建模为随机噪声，并最小化期望或经验损失。一篇新研究论文《Fixed-Set Robustness in Programming by Example: Example Corruption and Semantic Partition Recovery》探讨了不同的失败模式：一个对手观察合成器并故意选择最能破坏返回程序的示例进行破坏。
作者将有限PBE版本空间下的最坏情况示例破坏形式化为固定集对抗鲁棒性问题，并针对字符串转换领域特定语言实现了精确（有界池内）和启发式破坏搜索。为了防御这种攻击，他们引入了版本空间分区聚合（Version-Space Partition Aggregation, VPA），该方法将示例分成不相交的组，分别合成程序，然后通过语义签名投票产生最终结果。
论文的核心主张是有意限定且部分消极的：低裕度PBE任务具有对抗鲁棒性维度，而随机打字错误和噪声PBE评估无法捕捉；同时，语义分区聚合仅在清洁示例保持分区投票裕度时才有帮助，而这在现实任务中常常失败。研究团队在多个数据集上验证了这一点，包括人工策划和生成的DSL任务、已接受的公共SyGuS PBE_SLIA切片、SYNTRA Playgol v2以及噪声PBE目标基线。
具体实验结果显示：一个精心策划的编辑翻转了所有8个尖峰任务，而200次试验的打字错误、DSL池和距离匹配随机对照分别成功率为10.3%、11.0%和16.7%；生成的裕度1行在预算1下被翻转，但VPA恢复了它们；在公共SyGuS上，投票裕度接近1，因此自适应攻击者将VPA准确率降至零；已接受的公共SyGuS切片在精确有界池预算边界上移动；Playgol显示在141个已接受行上，与打字错误和同池随机对照相比，有正的配对自助差距。此外，在20个受控裕度1任务上的小型精确输出提示实验显示了相同的清洁到攻击模式。
这项工作揭示了PBE系统在面对针对性示例破坏时的脆弱性，并为未来设计更鲁棒的PBE系统提供了重要见解。