ソフトウェアコンポーネントの挙動をモデリングする手法
明けましておめでとうございます。
年末年始にいろいろ論文読んだので簡単にメモしてゆく。
タイトル
Modeling Black-Box Components with Probabilistic Synthesis
GPCE 2020
[2010.04811] Modeling Black-Box Components with Probabilistic Synthesis
https://dl.acm.org/doi/10.1145/3425898.3426952
概要
ソフトウェアコンポーネントのブラックボックスな振る舞いを模倣したプログラムを合成する手法。
手法の入出力
手法の入力
- 実行可能な関数 f（内部の構造は一切不明、つまり black-box とみなす）
- その関数のシグネチャ
出力の出力
- 実行可能な関数
- その振る舞いが入力の関数と（有限な入力において）等しい。
提案手法の手順
- 入出力データの生成
- 入力値は、元の関数の引数の型に応じて、固定された区間のランダム値を生成。
- ポインタ型の引数にはメモリブロックを割り当ててランダム値で埋める。
- 出力値は元の関数を実行して得る。
- 使用されそうな sketch の推定
- まず IID（Independent and Identically Distributed）に基づいて使用する fragments の推定
- 次に、Markov モデルで fragment sequence を推定
- sketch を LLVM IR のプログラムへコンパイル
- この時点ではプログラムは不完全であり実行できない（sketch がプログラムとして欠損しているため）
- プログラムの完全化
- basic block ごとに使用可能な SSA（single static assignment）変数を求める。
- それらを組み合わせて statements を構成する。この探索は enumerative search。
- 詳細は不明。組み合わせ爆発起こしそうだけどどうやって回避している？
疑問点メモ：
- もっともらしい sketch を見つけきてそれを完全化する流れは分かったが、もし sketch が不適切な場合はどういう手順になる？他の sketch にトライするみたいなアルゴリズムの設計になっていることは読み取れない。
確率モデル（Section 5）
2種類の確率モデル（IID, Markov）の部分が提案手法の特徴的な部分なので詳細を見てみる。
IID では、入出力データから使用されそうな fragment の集合を求める。ここで fragment とは合成のための DSL の要素のことである。fragment が組み合わされて1つのプログラムを構成する。詳細は Section 4 を参照。IID の学習には random forest モデルを使用しており、関数のシグネチャを入力として、それぞれの fragment を使用するかどうかを 1/0 で出力する分類器となっている。
Markov では fragment の列を予測する。このモデルの入力が何か読み取れない。関数のシグネチャとか入出力データを使う？ 具体的には、学習データのプログラムを fragment の列とみなし、連続する2つの fragments を収集しカウントする。その割合をもとに fragments の列を生成することで sketch を構築する。ただし、前手順の IID で求めた fragments に含まれないものは除外する。fragments の終わりを示す特殊なトークンが出現するか、長さの上限に達したら sketch の構築を完了する。要するにトークン列の 2-gram の統計を利用してプログラムを生成するという感じ。
疑問点メモ：
- 学習データの詳細が不明。特に、学習データがなぜ fragment の列を持っているのか不明。合成を実現するための学習に、合成結果のプログラムを利用できる状況がよく分からない。あり得るとすれば、同じ DSL を使用する既存の合成エンジンがあるか、もっと素朴なやり方でこの DSL を使うプログラム合成エンジンを実装したか、くらいかな。まさか人手で大量のプログラムを作った？プログラムをランダムに生成する synthetic なやり方も考えたが、実際によく出現する 2-gram の統計を集めたい状況なので今回はこの方法はなさそう。
評価実験
既存研究のプログラム合成手法のために作られたベンチマークと、今回新たに集めた既存ライブラリの関数群を対象に実験を行った。これら合計112個のベンチマークの詳細は Section 7.3 を参照。
提案手法の入力としてプログラムが必要であるため、それぞれの問題にベンチマークに対して正解となるプログラムを C 言語で実装した。それぞれのプログラムから "適切" な数の入出力データを生成し、元のプログラムを復元できるかどうかを調べた。
その結果は以下の図の通り。提案手法 PRESYN が既存手法を outperform している。
提案手法があまりにも強すぎる。今回集めたライブラリだけでなく、先行研究のベンチマークでもすべての先行手法を上回っている。比較手法はどれも近年のトップカンファで発表されている手法なのに、なぜ提案手法の素朴なやり方でここまで outperform できるのか。一番怪しいのは確率モデルの overfitting。次点でベンチマークの作り方。
所感
- アイデアは面白い。black-box なプログラムを white-box なプログラムで近似するというアイデア。
- 提案した合成手法が、既存のあらゆる汎用的なプログラム合成手法を outperform しているのに、論文のタイトルは black-box なプログラムの挙動のモデリング。なぜ素直に、ノーヒントにも関わらず高い性能を持つ program synthesizer をタイトルにしなかったのか。しかも Section 1.1 を見ると program synthesizer の提案が contributions のほとんどを占めていてさらに気持ちが分からない。
- 機械学習モデルの精度は学習データに大きく左右されるが、この手法の IID と Markov モデルの学習の詳細が分からない。具体的に、どんな学習データでどのくらいの数のデータを学習に用いたのか読み取れない。ちなみにFigure 2 に training に関する図があるが、まさかの文中で参照されていないという。論文のフォーマットの規約に違反していそう。
- プログラムの sketch を完成させるための enumerative search の詳細が読み取れない。合成エンジンを提案する研究として、組み合わせ爆発の軽減はかなり肝な部分のはず。なぜ書かないのか。
