プログラミング・バイ・エグザンプルにおける固定セットロバストネス：事例破損とセマンティック分割復元
本論文は、プログラミング・バイ・エグザンプルシステムの敵対的ロバストネスを研究し、新たな攻撃モードとして、敵対者がシンセサイザを観察し、返されるプログラムに最も損害を与える事例を選択するものを導入する。著者らは、有限バージョン空間における最悪ケースの事例破損を形式化し、探索アルゴリズムを実装し、防御としてバージョン空間分割集約（VPA）を提案する。実験により、低マージンタスクにはランダムノイズ評価では見逃される敵対的ロバストネスの次元が存在し、VPAはクリーンセマンティクスが分割投票マージンを維持する場合にのみ有効であり、現実的なタスクではしばしば失敗することが示された。
プログラミング・バイ・エグザンプル（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目標ベースラインである。
具体的な実験結果は以下を示す：1つのキュレーションされた編集が8つのスパイクタスクすべてを反転させたのに対し、200回試行のタイプミス、DSLプール、距離マッチングランダム対照はそれぞれ10.3%、11.0%、16.7%の成功率であった；生成されたマージン1行は予算1で反転したが、VPAはそれらを回復した；公開SyGuSでは投票マージンが1に近く、適応的攻撃者がVPAの精度をゼロに低下させた；受理された公開SyGuSスライスは精密有界プール予算境界を越えて移動した；Playgolでは141の受理行において、タイプミスおよび同プールランダム対照と比較して正のペア付きブートストラップギャップを示した。さらに、20の制御されたマージン1タスクにおける小型の精密出力プロンプト実験は、同じクリーンから攻撃へのパターンを示した。
この研究は、PBEシステムが標的事例破損に対して脆弱であることを明らかにし、将来のよりロバストなPBEシステムの設計に重要な洞察を提供する。