ICSE 勉強会 Comprehending the Drift I 筑波大学北川研早瀬康裕 Mining Message Sequence Graphs Sandeep Kumar, Siau-Cheng Khoo, Abhik Roychoudhury, David Lo 背景 • Dynamic specification mining：実行トレースからプログラムの振舞いを抽出する研究 – オートマトンに基づく記述 [11,23,28] – temporal ruleに基づく記述 [43,25] – どれも，逐次プログラムが対象 • 並列/分散プログラムからの抽出は難しい – 特に，イベントの半順序を発見する所 • 分散システムの記述には Message Sequence Charts (MSCs, ITU勧告) がよく用いられる – シーケンス図にそっくりだが，縦線はプロセスを表す MSGMiner • 入力: プログラムトレース • 出力: MSG (MSC を頂点とする有向グラフ) – 頂点 (basic MSC) のイベントが全て終了すると，次の頂点に移動する • 手順 (1) イベント間の半順序関係の抽出 – イベント列 (全順序) から，不要な関係を捨てる – 残す順序関係 • メッセージの送信 <s!r, m> は，対応する受信 <r?s, m> に先立つ • 同一のプロセス内の時系列順序 (2) basic MSC の抽出 • 頻出する部分グラフを抽出する (3) automata の学習 • sk-strings (既存手法) を使用する (4) 拡張 • • broadcast の送受信に対応不要な順序関係を捨てる • oracle (特別な入力列)を与えて，不要な順序を認識させる Automatically Detecting and Describing High Level Actions within Methods Giriprasad Sridhara, Lori Pollock, K. Vijay-Shanker Motivating example • コード片に対して，アルゴリズムレベルでの説明文を生成する手法を提案背景技術 3.1 プログラムの自然言語的構文解析著者らの作った Software Word Usage Model (SWUM) で，プログラム中に出現する単語の関係を取得する．動詞節，名詞節などが取り出せる．以下の組み合わせ • 連続する文から生成 • 制御構造から生成 9 for ( int x = 0 ; x < vAttacks . size() ; x++) { 10 WeaponAttackAction waa=vAttacks . elementAt (x); 11 float fDanger = getExpectedDamage(g, waa) ; 12 if (fDanger> fHighest) { 13 fHighest = fDanger; 14 waaHighest = waa; 15 } 16 } 17 return waaHighest ; Get weapon attack action object (in vectorAttacks) with highest expected damage 説明文の生成例 (Listing 1) 説明文生成の基本 • 3.2 連続する文をまとめる戦略: よく似た文の連続を，ひとつの処理として説明文を作る • まとめたい例 Listing 3 と，まとめたくない例 Listing 4 アルゴリズム – 上から順に連続する文をチェックし，連結可能な限りつなぐ – 連結可能の基準 • 動詞節が同じ • 名詞節の最後の語 (Head Word) が同じ • (前置詞節もチェックするが省略) – 連結可能な文から，名詞節の共通部分を括り出して複数形にする制御構造からの説明文生成 • 3.3 条件文を抽象化する戦略: 分岐後の文が同じ形なら，まとめて説明文にする – Ｌｉｓｔｉｎｇ 5: 条件節にあるレシーバ型が共通であることを見つけて，文の生成に利用する – Ｌｉｓｔｉｎｇ 6: return を見付ける．その引数が定数なら，条件式内の単語の略語かどうかをチェックする – Ｌｉｓｔｉｎｇ 7: 同じ変数への代入を見付ける • 3.4 ループ中のパターンを見付ける戦略: 特徴的なループのパターンを見付けて，説明文にする – max-min: 最大値 (最小値) を見付ける処理 – count: 集合型の中の要素数を数える – contains: 条件を満たす要素が含まれているかどうかを検査する – find: 条件を満たす要素を返す – copy: 集合型の(条件を満たす)要素を，別の集合型にコピーする 5 何に使える? • • • • リファクタリング関数・メソッド内部用のコメント生成より良いメソッド名の提案メソッドのドキュメントコメント(summary comment)生成 (の改善) Portfolio: Finding Relevant Functions and Their Usages Collin McMillan, Mark Grechanik, Denys Poshyvanyk, Qing Xie, Chen Fu mip map dithering texture image graphics Search 意図: mip map 画像を dithering していて，テクスチャに使っている例を探したい (?) • 全ての単語を含む関数はない • 個々の単語を含む関数が，別々に列挙されるだけでは，理解や再利用には不足開発者に必要なもの • 関連する関数全て • 適切な組み合わせ関連する関数も含めたコールグラフを見せようモデル • 検索対象のデータモデルは，関数間の静的なコールグラフ． – 辺は呼出しの有無のみで引かれる (多重辺，ラベルはなし) • PageRank と，キーワードマッチ(WOS)，Spreading Activation Network (SAN) を組み合わせて評価値を出す – 「SAN」と呼んでいるものの実態 • キーワードマッチの評価値を，コールグラフ上で隣接する頂点に伝播させる • これにより，直接キーワードにマッチしなかった頂点も検索結果として表示される • 検索結果は部分グラフ (+ 含まれる頂点のリスト) 検索結果の Web UI • 上位にランクされた関数は，コールグラフ上で大きく表示される • リストにマウスカーソルを合わせると，対応するコールグラフの頂点がハイライトされる評価実験 • Google Code Search, Koders, Portfolio を被験者実験で評価 – 49人中， Accenture コンサルティング部門の社員が44人(!) • 15種類のタスクのコンセプトを，それぞれ1つのクエリで表現 • 検索結果の上位10件を，4段階で評価 • 結果: Portfolio > Koders > Google