識別子の共起関係に基づく類似コード検索法の提案と 欠陥検出への適用

Presentation on theme: "識別子の共起関係に基づく類似コード検索法の提案と 欠陥検出への適用"— Presentation transcript:

1 識別子の共起関係に基づく類似コード検索法の提案と 欠陥検出への適用
大阪大学 大学院情報科学研究科 服部 剛之，吉田 則裕，早瀬 康裕， 肥後 芳樹，松下 誠，楠本 真二， 井上 克郎 それでは，識別子の共起関係に基づく類似コード検索法の提案と欠陥検出への適用というタイトルで， 大阪大学の服部が発表します．

2 概要 キーワードを自動的に抽出し，類似コードを検索する手法を提案する 提案手法を欠陥検出に適用し，実験を行った
grep等のキーワード検索では，適切なキーワードを決めるために対象ソフトウェアの知識が必要 ソースコードの一部を与えることで，キーワードを自動的に抽出 識別子の共起関係を利用 提案手法を欠陥検出に適用し，実験を行った 始めに，本発表の概要について説明します． 本発表では，識別子の共起関係を用いることで，キーワードを自動的に抽出し， 類似コードを検索する手法を提案します． grepなどの既存のキーワード検索では，適切なキーワードを決めるために 対象ソフトウェアの知識が必要となります． そこで，ソースコードの一部を与えることで，キーワードを自動的に抽出する手法を提案します． そして，提案手法を欠陥検出に適用し，実験を行いました．

3 目次 研究の背景 研究の目的とアプローチ 提案手法の説明 適用実験 まとめと今後の課題 欠陥の修正 類似コード検索 手法の概要
作成したシステムの説明 適用実験 欠陥検出への適用 まとめと今後の課題 次に，発表の流れについて説明します． まず始めに，研究の背景として，欠陥の修正と類似コード検索について説明します． 次に研究の目的とアプローチについて説明し， その後，提案手法の概要と実際に作成したシステムについて説明します． そして，提案手法を欠陥検出に適用した実験について説明した後， 最後にまとめと今後の課題について述べます．

4 欠陥の修正 ソフトウェア保守作業の効率化が重要な課題 ソフトウェアには，コピーアンドペーストによって生成されたソースコードが存在
ソフトウェア保守の際に，複数箇所に同様の修正を加える必要が生じることがある 同様の欠陥が存在する箇所を特定する方法が必要 ソースコードの一部が 類似した箇所が存在 近年，ソフトウェアの大規模化，複雑化により， ソフトウェア保守作業の効率化が重要な課題となっています． ソフトウェアには，コピーアンドペーストによって生成されたソースコードが存在するため， 保守を行う際に，複数箇所に同様の修正を加える必要が生じることがあります． そのため，欠陥が存在する箇所が見つかった場合，同様の欠陥が存在する箇所を特定する方法が必要となります． 同様の欠陥が存在 欠陥が存在

5 類似コード検索(1/2) ソースコードの集合から，一致もしくは類似したコード片(ソースコードの断片)を検索する
クエリ(検索質問)を与えることで検索を行う 検索結果 同様の欠陥が存在する箇所を特定する方法として，類似コード検索が挙げられます． 類似コード検索では，ユーザが検索質問であるクエリを与えることで， ソースコードの集合から，クエリと一致もしくは，類似したコード片の検索を行います． コード片とは，ソースコードの断片を指します． ソースコードの集合 類似コード検索 クエリを指定 ユーザ クエリ 一致もしくは類似したコード片

6 類似コード検索(2/2) ソースコードの集合から，一致もしくは類似したコード片(ソースコードの一部)を検索する
クエリ(検索質問)を与えることで検索を行う キーワードをクエリとして与える方法 例)grep コード片をクエリとして与える方法 例)コードクローン検索ツール Libra[1] 類似コード検索の例としては，grepなどのキーワードをクエリとして与える方法や， 我々の研究グループで提案しているコードクローン検索ツールLibraなどの コード片をクエリとして与える方法があります． 次にgrep，Libraそれぞれを用いた類似コード検索について説明します． [1] 泉田聡介，植田泰士，神谷年洋，楠本真二，井上克郎， “ソフトウェア保守のための類似コード検査ツール”， 電子情報通信学会論文誌，Vol.J-86-D-I(No.12):pp.906–908，2003.

7 grepを用いた類似コード検索 手順 利点 問題点 ユーザがコード片からキーワードを発見する
検出した箇所を基にキーワードを含むコード片を特定する 利点 名前などの識別子の情報が利用可能 問題点 適切なキーワードを発見することが困難 対象のソースコード集合に対する知識が必要 同義語などのキーワードの変化形を検出することが困難 grepを用いた類似コード検索では， 最初にユーザがコード片からキーワードを発見し，grepでキーワードが出現する箇所の検索を行います． そして，キーワードが出現する箇所を基に，キーワードを含むコード片を特定します． この方法の利点は，名前などの識別子の情報が利用できることです． しかし，適切なキーワードを発見するには，対象のソースコード集合に対する知識が必要であり， また，同義語などのキーワードの変化形を検出することが困難であるという問題があります．

8 Libraを用いた類似コード検索 手順 利点 問題点 ユーザがコード片をクエリとして与える
コードクローン検出ツールCCFinder[2]を用いてクエリのコードクローンを検出する 利点 キーワードを考えなくても検索が可能 キーワードの変化形にも対応可能 問題点 クエリとコードクローンの関係にある類似コードしか検出できない コード片の挿入，削除などの差異があると検出できない Libraを用いた類似コード検索では， 最初にユーザがコード片をクエリとして与えます． そして，コードクローン検出ツールCCFinderを用いて， クエリのコードクローン検出を行うことで類似コードを検出します． この方法の利点は，検索を行う際にキーワードを考える必要がないことと， コードクローンを利用するため，キーワードの変化形にも対応可能であることです． しかし，類似したコードがクエリのコードクローンでなければ，検出することができないという問題点があります． 例えば，クエリと類似コードの差異がコード片の挿入，削除という場合には検出することができません． [2] T. Kamiya, S. Kusumoto, and K. Inoue, "CCFinder: A multi-linguistic token-based code clone detection system for large scale source code", IEEE Transactions on Software Engineering, Vol.28(No.7):pp.654–670, 2002.

9 研究の目的とアプローチ 目的 アプローチ キーワードの発見を自動的に行い，類似コードの検索を行う
キーワードの変化形も考慮する アプローチ 識別子の共起関係を利用することで，コード片からキーワード，キーワードの変化形を自動的に抽出する 入力 提案手法 出力 そこで，本研究では， キーワードの発見を自動的に行い，類似コードの検索を行うことを目的として， 識別子の共起関係を利用することで，コード片からキーワードやその変化形を自動的に抽出して 類似コードの検索を行う手法を提案します． 手法の流れとしては，ソースコードの集合とクエリとなるコード片を入力として与え， クエリと類似したコード片の集合を出力します． また，提案手法はキーワードなどの抽出を行う抽出部と，類似コードの検査を行う照合部にわかれています． 次に提案手法の概要について説明します． 抽出部 ソースコードの集合 キーワード等の抽出 照合部 クエリとして与えるコード片 クエリと類似した コード片の集合 類似コードの検索

10 提案手法の概要(1/2) 抽出部 クエリとして与えられたコード片から，コード片を特徴付ける識別子(特徴語)を求める
ソースコード集合から，クエリとして与えられたコード片と特徴語が同じ，もしくは特徴語が類似したコード片を抽出する クエリとして与えられたコード片 手法が抽出したコード片 … host = host_alloc( ... ); log ( ... ); if (!add_host(host)) { // scan_host(host) // is missing! } … node = node_alloc( ... ); if ( ... == 0){ return; } if (!add_node(node)) { // scan_node(node) // is missing! 特徴語 抽出部では， 最初にクエリとして与えられたコード片から，コード片を特徴付ける識別子である特徴語を求めます． 次に，ソースコード集合から，クエリとして与えれれたコード片と特徴語が同じ，もしくは， 特徴語が類似したコード片を抽出します． 図では，赤の太字識別子が特徴語となっています． 特徴語

11 提案手法の概要(2/2) 照合部 クエリとして与えられたコード片と手法が抽出したコード片に対して，特徴語を含む文の集合を比較する
特徴語を含む文の構文情報が一致した場合，クエリとして与えられたコード片と類似したコード片として検出する クエリとして与えられたコード片 手法が抽出したコード片 … host = host_alloc( ... ); log ( ... ); if (!add_host(host)) { // scan_host(host) // is missing! } … node = node_alloc( ... ); if ( ... == 0){ return; } if (!add_node(node)) { // scan_node(node) // is missing! 次に照合部では， クエリとして与えられたコード片と抽出部で抽出したコード片に対して， 特徴語を含む文の集合を比較します． このとき，特徴語を含む文の構文情報が一致した場合， クエリとして与えられたコード片と類似したコード片として判定します． 図では，ハイライトされた箇所が特徴語を含む文の集合となっており， この集合において，文の構文情報がそれぞれ一致しているので， 手法が抽出したコード片は，類似したコード片と判定されます． 構文情報が一致 類似したコード片

12 作成したシステムの概略図 クエリ 識別子情報の抽出 識別子の同義語の導出 抽出部 ソースコードの集合 特徴的な箇所の抽出 構文情報の取得
次に，実際に作成したシステムの概略図について説明します． 青線で囲まれた部分がシステムとなっており， まず，ソースコードの集合を与え，識別子情報などの抽出を行います． その後，ユーザがクエリとなるコード片を与え，構文情報を比較することで， クエリと類似したコード片を持つ，例えば関数，メソッドなどのモジュールのリストを出力します． 次に抽出部から順に，システムのそれぞれの手順について説明します． 構文情報の取得 ユーザ 照合部 ユーザが行単位で コード片を選択 特徴的な箇所の構文の比較 ユーザが与えたコード片と類似した コード片を持つモジュールのリスト

13 識別子情報の抽出 ソースコードの集合からモジュール単位で識別子を抽出する モジュールごとに識別子の出現回数を計算する
予約語，型名を表す識別子は除外 モジュールごとに識別子の出現回数を計算する 識別子情報 識別子名 対象モジュール 出現回数 識別子情報の抽出のところでは， ソースコードの集合からモジュール単位で識別子の抽出を行います． このとき，予約語，型名を表す識別子は除外しています． そしてモジュールごとに識別子の出現回数を計算し，識別子情報として記録します． 識別子情報は，識別子名，対象モジュール，出現回数で構成されています．

14 識別子の同義語の導出 識別子の共起関係に基づいて，識別子のクラスタリングを行う 同じクラスタに属する識別子を同義語と定義する
識別子の共起回数の分布が類似している場合，同じクラスタに含まれる Jensen-Shannon divergence[3]を用いて，類似度を表す 同じクラスタに属する識別子を同義語と定義する 例） 識別子aと識別子bの共起回数の分布 識別子a 識別子b 識別子c 識別子d 識別子e 次に識別子の同義語の導出では， 識別子の共起関係に基づいて，識別子のクラスタリングを行います． クラスタリングを行った結果，識別子の共起回数の分布が類似している識別子が同じクラスタに含まれます． そして，同じクラスタに属する識別子を同義語と定義します． 識別子の共起回数は，識別子情報を用いて求めています． また，類似度については，自然言語処理で用いられているJensen-Shannon divergenceを用いました． 例の場合では，共起回数a2，a3，a4とb2，b3，b4が類似している場合，識別子aと識別子bが同義語と判定されます． - a1 a2 a3 a4 b1 - b2 b3 b4 a2，a3，a4とb2，b3，b4が類似している場合，識別子aと識別子bを同義語とする [3] I. Dagan, L. Lee, and F. C. N. Pereira, "Similarity-based models of word cooccurrence probabilities", Machine Learning, Vol.34(No.1-3):pp.43–69, 1999.

15 特徴的な箇所の抽出 モジュールごとに特徴語を求める モジュール中の特徴語を含む行を特徴的な箇所と設定した モジュール単位で閾値を定める
ソースコード集合固有の基準値をモジュールの規模に応じて正規化する 識別子の出現回数が閾値を上回る場合，そのモジュールにおける特徴語と設定した モジュール中の特徴語を含む行を特徴的な箇所と設定した 照合部で比較を行う対象として用いる 特徴的な箇所の抽出では， 今回は，モジュール単位で閾値を定め，識別子の出現回数が閾値を上回る場合， そのモジュールにおける特徴語と設定しました． また，照合部で比較を行う対象として，モジュール中の特徴語を含む行を特徴的な箇所と設定しました．

16 作成したシステムの概略図 クエリ 識別子情報の抽出 識別子の同義語の導出 抽出部 ソースコードの集合 特徴的な箇所の抽出 構文情報の取得
続いて，照合部の手順について説明します． 構文情報の取得 ユーザ 照合部 ユーザが行単位で コード片を選択 特徴的な箇所の構文の比較 ユーザが与えたコード片と類似した コード片を持つモジュールのリスト

17 構文情報の取得 入力コード片から特徴的な箇所を抽出する それぞれの特徴的な箇所において，構文情報を取得する 構文情報の設定
出現している特徴語の集合 文の種類 変数宣言などの宣言文 条件文，繰り返し文などの条件節 break文，return文などの補助制御文 それ以外の文 まず，入力コード片から抽出部のところで述べた特徴的な箇所の抽出を行います． そして，それぞれの特徴的な箇所において，構文情報を取得します． 今回，構文情報については，出現している特徴語の集合と特徴的な箇所の文の種類の組と設定しました． また，文の種類は宣言文，条件節，補助制御文，そしてそれ以外の文としました．

18 特徴的な箇所の構文の比較(1/2) 入力コード片と各モジュールについて，特徴的な箇所の構文情報を比較する 構文情報の対応付けを行う
特徴語が一致もしくは同義語の関係にある 文の種類が一致する 同義語 {host_alloc, node_alloc} {add_host, add_node} 特徴語が同義語の関係 文の種類が一致 … host = host_alloc( ... ); log ( ... ); if (!add_host(host)) { // scan_host(host) // is missing! } 入力コード片 … node = node_alloc( ... ); if ( ... == 0){ return; } if (!add_node(node)) { // scan_node(node) // is missing! 比較対象 構文情報を取得した後，入力コード片と各モジュールについて， 特徴的な箇所の構文情報を比較します． このとき，特徴語が一致もしくは同義語の関係にあり，かつ文の種類が一致した場合， 構文情報の対応付けができたと判定します． 図では，ハイライトされた箇所が特徴的な箇所となっています． 比較対象の特徴的な箇所と構文情報を比較します． 1つ目は，特徴語が同義語の関係にあり，文の種類が一致するため，構文情報の対応付けが取れます． 2つ目は，特徴語が同義語ではなく，文の種類は一致していないため，構文情報の対応付けは取れません． 特徴語が同義語ではない 文の種類が一致しない

19 特徴的な箇所の構文の比較(2/2) 構文情報の対応付けの状態によって，類似したコード片を含むモジュールを検出する
入力コード片の特徴的な箇所の構文情報すべてが，対応付け可能である場合 … host = host_alloc( ... ); log ( ... ); if (!add_host(host)) { // scan_host(host) // is missing! } 入力コード片 … node = node_alloc( ... ); if ( ... == 0){ return; } if (!add_node(node)) { // scan_node(node) // is missing! 比較対象 そして，入力コード片の特徴的な箇所の構文情報すべてが，対応付け可能である場合， 比較対象が入力コード片と類似したコード片を含むモジュールと判定されます． 対応付け可能 類似したコード片を含むモジュール

20 適用実験目次 実験概要 実験対象 実験の設定 評価基準 実験結果 考察 日本語入力システム かんな
ソフトウェア部品検索システム SPARS-J 実験の設定 クラスタリングの閾値 入力コード片 評価基準 実験結果 考察 次に，提案手法を欠陥検出に適用した実験について，説明します． 実験の概要について説明し， 実験を行った対象，実験の設定，出力の評価基準について説明します． そして，実験結果と考察について述べます．

21 実験概要 実験対象に存在している欠陥の箇所をクエリとする クエリと同じ欠陥を含むコード片がどの程度検出されているか調べる コード片の1つを
クエリとして与える 同じ欠陥を含む コード片の集合 提案手法 クエリ 実験の概要では，実験対象に存在している欠陥の箇所をクエリとして与え， 類似したコード片を持つモジュールを検出します． 検出結果が，クエリと同じ欠陥を持つコード片をどの程度含んでいるか 調べることによって評価を行います． 検出できた数を調べる クエリと類似したコード片を 持つモジュール

22 実験対象 日本語入力システム かんな ソフトウェア部品検索システム SPARS-J モジュールの単位を関数単位とした
Version3.6，Version3.6p1間でバッファのオーバーフローを検出するコードが追加された コードが追加される箇所を欠陥の箇所とした ソフトウェア部品検索システム SPARS-J 複数の関数において型キャストの追加が行われた 2004/5/27で同時に修正が行われている 型キャストの追加が行われる箇所を欠陥の箇所とした モジュールの単位を関数単位とした 実験対象として，日本語入力システム かんなとソフトウェア部品検索システム SPARS-Jを用いました． 共にC言語のソフトウェアとなっています． かんなでは，2つのバージョン間でバッファのオーバーフローを検知するコードが追加されており， 追加されるコードが挿入される箇所を欠陥の箇所としました． SPARS-Jでは，複数の関数において型キャストの追加が行われており， 型キャストの追加が行われる箇所を欠陥の箇所としました． また，モジュールの単位は関数単位に設定しました．

23 実験の設定(クラスタリングの閾値) 同義語を求める際のクラスタリングの閾値を変化させて実験を行った クラスタリングの閾値を求める手順
共起回数の分布の差異をクラスタ間距離とする クラスタリングの閾値を求める手順 初期状態のクラスタ間距離の最大値を求める 1の値のx%を閾値とする Xを0%～100%まで10%刻みに変化させ実験を行った 例)初期状態のクラスタ間距離の分布 同義語を求める際のクラスタリングの閾値について， 値を変化させて実験を行いました． 初期状態のクラスタ間距離の最大値を基準として， 閾値を設定しました． 設定した割合が0%の場合は，共起回数の分布が全く同じ識別子のみをクラスタリングすることになります． また，設定した割合が100%の場合は，すべての識別子が1つのクラスタに属することになります． クラスタb クラスタa クラスタc クラスタd - 1 2 3 6 5 4 割合を50%に設定した場合， 閾値は6×0.5=3となる

24 実験の設定(入力コード片) 後のバージョンで修正が行われる箇所とその前後合わせて3行を入力のコード片とする 入力コード片の総数
かんな：21個 SPARS-J：75個 修正前 修正後 修正箇所 key.data = package; key.size = size + 1; /* Acquire a cursor for the database. */ dbcp = get_cursor(&DBlist[PACKAGEDB]); key.data = package; key.size = (u_int32_t)(size + 1); /* Acquire a cursor for the database. */ dbcp = get_cursor(&DBlist[PACKAGEDB]); 入力コード片については，後のバージョンで修正が行われる箇所と前後の行合わせて3行を入力のコード片としました． 入力コード片は，かんなが21個，SPARS-Jが75個となりました． 図では，修正が行われる箇所の前後1行ずつを追加して3行を入力コード片としています． 修正が行われる箇所の前後1行ずつを 追加して3行を入力コード片とする

25 評価基準 それぞれの入力コード片について，適合率，再現率を求めた 適合率： 再現率： 正解集合は実験対象で述べた欠陥を含むコード片とした
システムが検出した正解集合のコード片を含む関数の数 　　　　　　　　 システムが検出した関数の数 × 100 (%) システムが検出した正解集合のコード片を含む関数の数 　　　　　 正解集合のコード片を含む関数の総数 × 100 (%) システムの検出結果の評価基準として，適合率，再現率を用いました． 適合率とは，システムが検出した関数のうち，システムがどの程度正解を検出しているかを表す値です． この図では，分母が緑と紫の部分，分子が紫の部分となります． 再現率とは，設定された正解集合のうち，システムがどの程度正解を検出しているかを表す値です． この図では，分母が青と紫の部分，分子が紫の部分となります． 正解集合の関数 システムが検出した関数

26 実験結果 かんな ＳＰＡＲＳ－Ｊ 適合率は低いが，20%以降高い再現率が得られた 0% 17.03% 5.51% 10% 89.86%
閾値として 設定した割合 入力コード片の 適合率の平均 再現率の平均 0% 17.03% 5.51% 10% 89.86% 18.55% 20% 39.45% 81.95% 30% 21.09% 100.00% 40% 9.64% 50% 60% 9.55% 70% 80% 90% 100% 閾値として 設定した割合 入力コード片の 適合率の平均 再現率の平均 0% 8.05% 0.36% 10% 22.67% 18.28% 20% 7.01% 87.19% 30% 7.33% 88.31% 40% 50% 60% 7.23% 89.53% 70% 80% 90% 100% これが，かんなとSPARS-Jの実験結果となります． 適合率，再現率については，それぞれの入力コード片における値の平均を表示しています． この表を見ると，適合率は低いが，閾値として設定した割合が20%以降の場合，高い再現率が得られています． 適合率は低いが，20%以降高い再現率が得られた

27 結果と考察 入力コード片の再現率の平均が高い値となっていた 入力コード片の適合率の平均は低い値となっていた
欠陥を漏れなく検出することが要求される条件下では，提案手法は有効 入力コード片の適合率の平均は低い値となっていた 欠陥が含まれていなくても，同じ構文であれば欠陥を含むコード片と判定されてしまう 欠陥と関係がないコード片を除外することが必要 閾値として設定した割合が，10%～20%の間で再現率が大きく変化している 閾値の基準となる値を設定できると期待される 入力コード片の再現率の平均が高い値となっていたことから， 欠陥を漏れなく検出することが要求される条件下では，提案手法は有効であると考えられます． 一方，適合率の平均は低い値となっており，欠陥が含まれていなくても，構文が同じならば システムが検出してしまうことが原因となっていると考えられます． そのため，欠陥と関係がないコード片を除外することが必要であると考えられます． また，閾値として設定した割合が10%～20%の間で，再現率が大きく変化していることから， 閾値の基準となる値を設定できると期待されます．

28 まとめ 識別子の共起関係に基づいて類似コード片を検索する手法を提案 提案手法を欠陥検出に適用し，実験を行った
コード片から自動的にキーワードを発見 同義語を用いて，キーワードの変化形にも対応 提案手法を欠陥検出に適用し，実験を行った 実験対象はC言語のソフトウェア かんな SPARS-J 適合率は低いが，再現率は高い結果 本発表では， 識別子の共起関係に基づいて類似コード片を検索する手法を提案しました． 提案手法では，コード片から自動的にキーワードを発見することで， grepなどのキーワード検索法の問題点を解消した類似コード検索を行います． また，提案手法を欠陥検出に適用し，実験を行いました． C言語のソフトウェアを対象として実験を行った結果，適合率が低いが再現率は高い結果となりました．

29 今後の課題 出力結果を分類して評価を行う必要がある 他のプログラミング言語で開発されたソフトウェアを対象とした実験を行う必要がある
同じ欠陥を含むモジュール 処理内容が同じで欠陥を含まないモジュール 異なる処理内容のモジュール 他のプログラミング言語で開発されたソフトウェアを対象とした実験を行う必要がある 特徴語検出における閾値の妥当性を評価する必要がある 構文情報の対応付けを行った効果について，評価する必要がある 最後に今後の課題について述べます． 入力コード片と同じ処理内容でも欠陥を含まない場合があるため， 出力結果を分類して評価を行う必要があります． 分類としては，入力コード片と同じ欠陥を含むモジュール， 処理内容は入力コード片と同じであるが欠陥を含まないモジュール， 入力コード片と異なる処理内容のモジュールが挙げられます． 今回はC言語のソフトウェアのみを対象とした実験であったため， 他のプログラミング言語で開発されたソフトウェアを対象として実験を行う必要があります． また，特徴語検出における閾値の妥当性評価が行われていないので， 閾値を変更した比較実験などの評価を行う必要があります． また，プログラミング言語やコーディングスタイルによって，絞込みの効果が変わる可能性があるため， 構文情報を利用した絞込みの効果を評価をする必要があります．