PowerPoint プレゼンテーション

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 条件文を抽象化する
戦略: 分岐後の文が同じ形なら,まとめて説明文にする
– Listing 5: 条件節にあるレシーバ型が共通であることを見つけて,
文の生成に利用する
– Listing 6: return を見付ける.その引数が定数なら,条件式内の単
語の略語かどうかをチェックする
– Listing 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