識別子の共起関係を用いた類似コード検索手法の提案と実現井上研究室博士前期課程2年服部剛之 Department of Computer Science, Graduate School of Information Science & Technology, Osaka University 1 概要  ソフトウェア保守を困難にする要因である類似コードを検索する手法を提案する  検索キーワードを自動的に抽出  対象ソフトウェアに対する知識がなくても検索が可能  適用実験として，欠陥を含むコードの類似コードを検索した  欠陥検出に対する有効性の評価 Department of Computer Science, Graduate School of Information Science & Technology, Osaka University 2 類似コードが引き起こす問題点  類似コードはソフトウェア保守作業を困難にする要因例）同様の内容を含む欠陥の修正  複数箇所に同様の修正を加える必要が生じることがある  欠陥の類似コードを検索する方法が必要ソースコードの一部が類似した箇所が存在同様の内容を含む欠陥が存在欠陥が存在 Department of Computer Science, Graduate School of Information Science & Technology, Osaka University 3 類似コード検索  ソースコードの集合から，一致もしくは類似したコード片（ソースコードの断片）を検索する  クエリ（検索質問）を与えることで検索を行うキーワードをクエリとして与える方法例）文字列照合コマンドgrep ソースコードの集合クエリ（検索質問）検索 request 開発者・・・・ request ・・・・・・・・ request・・・・・・・・・・・・ Department of Computer Science, Graduate School of Information Science & Technology, Osaka University 4 grepを用いた類似コード検索  手順 1. ユーザがコード片からキーワードを抽出 2. grepによって，キーワードが出現する箇所を検索 3. 検索結果を基にキーワードを含むコード片を特定  問題点  適切なキーワードを抽出することが困難  対象のソースコード集合に対する知識が必要  同義語などのキーワードの変化形に対応することが困難 Department of Computer Science, Graduate School of Information Science & Technology, Osaka University 5 研究の目的とアプローチ  目的  自動的にキーワード抽出を行う類似コード検索  アプローチ  キーワード，キーワードの変化形を自動的に抽出ソースコードの集合提案手法抽出部キーワードの抽出クエリ開発者クエリと類似したコード片の集合照合部コード間の類似性の判定コード片を与える Department of Computer Science, Graduate School of Information Science & Technology, Osaka University 6 単語の共起関係に基づく関連語の検出法  ある単語と関連した単語を特定する手法  自然言語処理の分野で用いられている  単語間の共起関係を用いている  単語間の共起関係  関連語とは，文中で共起する単語が類似する単語対 This word is related to another example. For example, it is related to another term. It finds a similar word. It found a similar term. 共に出現している単語が類似共に出現している単語が類似 Department of Computer Science, Graduate School of Information Science & Technology, Osaka University 7 共起回数の分布  他の単語と文中で共起した回数を表した分布  関連語は，分布が類似している This word is related to another example. For example, it is related to another term term. It finds a similar word word. 共起回数の分布が類似 It found a similar term term. term word word another term term term word word  0  0  1 1  example 1 1  found  1 0     Department of Computer Science, Graduate School of Information Science & Technology, Osaka University 8 提案手法の概要（抽出部） 1. モジュール中で共起する識別子が類似する識別子の対を関連語とする  2. 3. 単語の共起回数の分布に基づいて関連語を求める手法[1]を利用モジュール単位で頻出する識別子を特徴語とする特徴語を含むコードの構文を求めるモジュールB 代入文代入文 ... ... モジュールA node node = node_alloc(...); host = host host_alloc(...); if (...) { log(...); hostとnodeは関連語条件節 return; 条件節 } if (!add_host(host)) host host { if(!add_node(node)) node node { // scan_host(host) // scan_node(node) // is missing! // is missing! } hostが特徴語 nodeが特徴語 } ... ... Department of Computer Science, School of Information Science & Technology, Osaka University1999 [1] I. Dagan, et al. "Similarity-Based Models ofGraduate Word Cooccurrence Probabilities", Machine Learning, 9 提案手法の概要（照合部） 1. 2. クエリのコード片から特徴語を含むコードを求める特徴語を含むコードの対応付けを行う   特徴語が一致，もしくは関連語の関係にある構文が一致関連語はhostとnode クエリの類似コード比較対象クエリのコード片 ... ... node = node_alloc(...); host = host_alloc(...); if (...) { log(...); 特徴語が関連語の関係にある return; 構文が代入文 } if (!add_host(host)) { if(!add_node(node)) { // scan_host(host) // scan_node(node) // is missing! 特徴語が関連語の関係にある // is missing! } 構文が条件節 hostが特徴語 nodeが特徴語 } ... ... Department of Computer Science, Graduate School of Information Science & Technology, Osaka University 10 実験概要実験対象に存在している欠陥の箇所をクエリとする  クエリと同じ欠陥を含むコード片がどの程度検索結果に含まれているか調べる  実験対象クエリと類似したモジュールの集合提案手法抽出部キーワード等の抽出クエリ照合部コード間の類似性の判定ユーザ欠陥を含むコード片クエリと同じ欠陥を含むコード片が含まれているか調べる Department of Computer Science, Graduate School of Information Science & Technology, Osaka University 11 実験対象  日本語入力システムかんな  後のバージョンでバッファのオーバーフローを検知するコードが追加  ソフトウェア部品検索システム SPARS-J  複数の関数において型キャストが追加モジュールの単位を関数単位としたかんなの修正事例 ir_debug( Dmsg(10, "ProcWideReq2 start!!\n") ); if (Request.type2.datalen != SIZEOFSHORT) return( -1 ); バッファオーバーフローを検知 buf += HEADER_SIZE; Request.type2.context = S2TOS(buf); ir_debug( Dmsg(10, "req->context =%d\n", Request.type2.context) ); ・・・ Department of Computer Science, Graduate School of Information Science & Technology, Osaka University 12 実験の設定  関連語を設定する閾値 1. 識別子間の距離を算出  2.  共起回数の分布の差異を利用識別子間の距離が閾値以下の識別子を関連語と設定閾値を変化させて実験を行った  対象ソフトウェアでの識別子間の距離の最大値を求め，最大値の0%～100%まで10%刻みで変化させた  0%   共に出現する識別子の種類が等しい識別子が関連語 100%  全ての識別子が関連語 Department of Computer Science, Graduate School of Information Science & Technology, Osaka University 13 評価基準それぞれのクエリについて，適合率，再現率を求めた  適合率：検索された欠陥を含む関数の数 × 100 (%) 検索された関数の数   検索結果のノイズの少なさを表す  再現率：検索された欠陥を含む関数の数欠陥を含む関数の総数 × 100 (%)  検索結果の漏れの少なさを表す欠陥を含む関数検索された関数 Department of Computer Science, Graduate School of Information Science & Technology, Osaka University 14 実験結果実験結果：かんな実験結果：かんな 100% 80% 60% 適合率の平均再現率の平均 40% 20% 0% 0% 10% 20% 30% 40% 50% 60% 70% クラスタリングの閾値として設定した割合 80% 90% 100% 実験結果：SPARS-J 実験結果：SPARS-J 100% 80% 60% 適合率の平均再現率の平均 40% 20% 0% 0% 10% 20% 30% 40% 50% 60% 70% クラスタリングの閾値として設定した割合 80% 90% 100% Department of Computer Science, Graduate School of Information Science & Technology, Osaka University 15 考察欠陥を漏れなく検出することが要求される条件下では，提案手法は有効である  クラスタリングの閾値に対して，基準となる値が設定できると期待される   今回の実験では，10%～30%が基準に利用可能  入力コード片の選び方で，検出結果が変わる可能性がある  入力コード片のサイズで，特徴語が変化 Department of Computer Science, Graduate School of Information Science & Technology, Osaka University 16 まとめと今後の課題  識別子の共起関係に基づいて類似コード片を検索する手法を提案  コード片から自動的にキーワードを抽出  提案手法を欠陥検出に適用し，実験を行った  適合率は低いが，再現率は高い結果  今後の課題  他のソフトウェアを対象とした実験  入力コード片のサイズが与える影響の調査 Department of Computer Science, Graduate School of Information Science & Technology, Osaka University 17