オブジェクト指向メトリクスを用いた 開発支援法に関する研究 神谷 年洋 2001/02/14

背景(1) ソフトウェアの応用分野の拡大 ソフトウェアの大規模化・複雑化 開発期間の短縮・品質の向上 オブジェクト指向開発技術 開発／保守プロセス メトリクス 研究の背景ですが， 近年，ソフトウェアの応用分野の拡大に伴い， ソフトウェアが大規模化・複雑化しています． また，開発期間の短縮や，ソフトウェアの品質の向上が要求されています． そのような要求に応えるため， オブジェクト指向開発技術や， 開発・保守プロセスの改善といった手法が用いられます． また，メトリクスによるプロダクトの品質計測・フォールト予測と いった手段が提案されています． 2000/12/21

背景(2) オブジェクト指向ソフトウェア開発 分析／設計／実装を通してオブジェクトを用いる オブジェクト指向プログラミング言語 JavaやC++など 開発ツール 大規模な再利用 フレームワーク オブジェクト指向メトリクス CKメトリクス では次に，オブジェクト指向開発の特徴を説明いたします． オブジェクト指向ソフトウェア開発の特徴は， 開発プロセス中，分析・設計・実装を通じてオブジェクトという概念が 一貫して用いられることです． オブジェクト指向ソフトウェア開発やその支援技術として， JavaやC++を始めとする多くのオブジェクト指向プログラミング言語が開発されています． また，言語処理系や設計ツールなど，多くの開発ツールが用いられています． 大規模な再利用を可能にするライブラリであるフレームワークが提供され， オブジェクト指向プログラムから，複雑度や機能量を計測するための オブジェクト指向メトリクスが提案されています． 2000/12/21

背景(3) オブジェクト指向ソフトウェアの品質評価／フォールト予測のために，オブジェクト指向メトリクスが用いられている ↓ オブジェクト指向複雑度メトリクスの適用において，オブジェクト指向開発技術や開発プロセスの特性が考慮されていない オブジェクト指向メトリクスは， オブジェクト指向プログラムの特徴である オブジェクトや，クラス，メッセージパッシングなどを 測を行うために提案されています． しかし，提案されてからまだ日が浅いため， さまざまなオブジェクト指向開発技術や オブジェクト指向ソフトウェア向けに提案されている開発プロセスの特性を 考慮した適用法は研究されていませんでした． 2000/12/21

目的 オブジェクト指向メトリクスを用いた開発支援法に関して研究を行った 再利用技術 設計 開発プロセス 重複コード 2000/12/21 本研究では オブジェクト指向メトリクスを用いた開発支援に関して研究を行いました． 具体的には， オブジェクト指向メトリクスの計測や評価に影響を与える， オブジェクト指向ソフトウェアで用いられる再利用技術， 再利用技術を用いた設計， オブジェクト指向開発プロセスについてしらべ， また，オブジェクト指向プログラム中の重複コードといったトピックについて 研究を行いました． 2000/12/21

論文の構成 1. 緒論 2. 諸準備 3. 再利用を考慮した構造メトリクス計測法[1-2] →再利用部品と新規開発部品を区別することでフォールト予測精度を改善 4. フレームワークを用いたクラス分類に基づくフォールト予測手法[1-4] →フレームワークを利用したクラス分類によってフォールト予測精度を改善 5. CKメトリクスを開発プロセスの初期に計測する手法[1-6] →OMT法に基づく開発プロセスにチェックポイントを設け，各チェックポイントにおいて予測を行う 6. オブジェクト指向プログラミング言語向けのコードクローン検出手法[1-5] →オブジェクト指向プログラミング言語の文法知識を用いた，効果的な重複コード検出技術 7. むすび 博士論文は以下の7つの章から構成されております． この発表では，時間の都合上，4章と6章を中心に説明いたします． 2000/12/21

フレームワークを用いたクラス分類法 [論文の4章] 複雑度メトリクスによるフォールト予測 CKメトリクス 問題点 フレームワークを利用したクラス分類法 クラス分類を用いたフォールト予測 実験 結論と課題 それでは，まず， 論文の4章の内容である， 「フレームワークを用いたクラス分類法」について説明いたします． 2000/12/21

複雑度メトリクスによるフォールト予測 (1)メトリクスを用いてプロダクトの複雑度を計測し (2)プロダクトに作りこまれるフォールトを予測する 「複雑なプロダクトほどフォールトが作りこまれやすい」 フォールトの予測はレビューやテストを効果的に配分するために用いられる 背景として， 複雑度メトリクスを用いてフォールトを予測する一般的な手順について説明いたします． まず，複雑度メトリクスを用いてプロダクトの複雑度を計測し， 「複雑なプロダクトほど，フォールトが作りこまれやすい」という仮定に基づいて， プロダクトに作りこまれるフォールトの数や修正時間などを予測します． フォールトの予測はプロダクトのレビューやテストの工数を効果的に配分するために用いられます． 2000/12/21

CKメトリクスおよびその他のメトリクス CKメトリクス[Chidamber] DIT：クラス階層木内での深さ NOC：直接導出されている子子クラスの数 RFC：呼び出すメソッドの種類数（RFCR, RFCN) CBO：結合するクラスの種類数（CBOR, CBON） WMC：クラスのメソッド数 LCOM：メソッドの凝集度の欠如の度合い その他のメトリクス NIV：インスタンス変数の数 SLOC：ソースコードの行数 継承 結合 クラスの 内部複雑度 オブジェクト指向プログラムから複雑度を計測するメトリクスとして代表的な， CKメトリクスについて説明いたします． CKメトリクスはChidamberとKemererによって94年に提案され， クラスの複雑度を計測する6つのメトリクスからなります． 6つのうち2つは，クラスの継承や導出に関する複雑度， 2つは，クラス間の結合に関する複雑度， 残りの2つは，クラスの内部的な複雑度を計測します． 本研究では，CKの6種のメトリクスに加えて， インスタンス変数の数やソースコードの行数といったメトリクスも用いました． [Chidamber] S.R. Chidamber and C.F. Kemerer: “A Metrics Suite for Object Oriented Design”, IEEE Trans. on Software Eng., vol., 20, No. 6, Jun 1994. 2000/12/21

問題点 クラスの機能によりメトリクス値の分布が異なる[Basili] 一般的なソースコードにおいて，クラスの機能分類を自動的に行うことは難しい オブジェクト指向プログラムでは，クラスはその機能によって，異なったメトリクスの分布を持つことが知られています． 右の図は後述する実験で開発されたクラスのメトリクス値の分布を調べたものです． それぞれの点はクラスで，横軸はCBOの計測値，縦軸はRFCの計測値を示します． 点の色と形はクラスの分類を表しています． たとえば，紫の丸で示されるクラスと，青の四角で示されるクラスでは，分布がほぼ分かれています． このような分布の偏りは，メトリクスによるフォールト予測に影響すると考えられます． Basiliが行った研究においても，クラスの機能により，メトリクス計測値の分布が異なることが示されています． しかしながら，どんなソースコードにでも適用できるような，一般的なクラスの機能分類といったものは困難です． [Basili] V. R. Basili, L. C. Briand, W. L. Mélo: “A validation of object-oriented design metrics as quality indicators,” IEEE Trans. on Software Eng., Vol. 20, No. 22, pp. 751-761 (1996). 2000/12/21

フレームワークを利用したクラス分類法 フレームワークのクラスから，「導出が期待される」クラスを選出する →代表クラス どの代表クラスから導出されているかによって，新規開発クラスを分類する そこで，フレームワークが再利用されているような開発に限定して，機能分類を行う手法を考えました． この方法では，フレームワークを用いた開発においては， 多くの新規開発クラスが，フレームワークのクラスから導出することで開発されることを利用します． 右の図で，四角はクラスを表しており，矢印は導出を表します． 白い四角はフレームワークのクラス， 灰色の四角は新規開発のクラスです． フレームワークのクラスの中から，クラス分類に用いるクラスを選出します． ここでは，A, B, Cの3つのクラス，図では太線の四角で囲まれている 3つのクラスを分類クラスとして選出したとします． このとき，新規開発クラスpはAから導出されているので，ｐの分類はAです． 同様に，qとuはBから導出されているので，Bと分類します． Sのように，分類クラスから導出されていないクラスはその他分類とします． フレームワーク （ 代表クラス ） 新規開発クラス 2000/12/21

クラス分類を用いたフォールト予測 (1)代表クラスを選出する (2)基準となるデータを収集する メトリクスを計測するためのプロダクト(たとえばソースコード)から，クラスごとに，分類，メトリクス値，フォールト修正時間を記録する (3)予測式の作成 重回帰分析によって，クラス分類ごとに，メトリクスを入力とし，フォールト修正時間を出力とする予測式を作成する (4)フォールト修正時間を予測する フォールト修正時間の予測を行いたいクラスから計測したメトリクスを，分類に応じた予測式に当てはめる クラス分類を用いてフォールト予測を行うには，次の4つのステップを順に行います． まず最初に，先に説明した方法によって，分類クラスを選出します． 次に，予測の基準となるデータを収集します． これには，メトリクスを計測するためのプロダクト，ソースコードや設計書から， クラスごとに，分類，メトリクス値，フォールト修正時間を記録します． 次に，重回帰分析によって，メトリクスを入力とし，フォールト修正時間を出力とする予測式を作成します． あとは，予測を行いたいクラスに対して，計測したメトリクスを，分類に応じた予測式に当てはめることで， 予測を行います． 下線を引いた部分を削除すると，クラス分類を行わずにフォールト予測を行う手順になります． 2000/12/21

実験概要 ある企業の新人研修におけるプログラム開発演習 GUIを備えた電子メールの配送システム 4から5人のチームによる開発であり，各開発者はサブシステムを開発する インストラクタによって受け入れテストが実施される Visual C++，フレームワークとしてMFC(Microsoft Foundation Class)を用いる 開発規模はチームあたり3千行程度(再利用分を含まない) 最終的には，17人分，124個のクラスのデータが利用できた 手法を評価するための実験について説明します． この実験では，ある企業の新人研修におけるプログラム開発演習からデータを収集しました． 2000/12/21

クラス分類 (1)CDocument：アプリケーションのデータを格納 (2)CView：ユーザーに対してデータを表示 (3)CDialog： ユーザーからデータを受け取る エラーメッセージ出力する (4)CWinApp：アプリケーションの設定に関する処理 (5)CFrameWnd：アプリケーションのウィンドウの管理 (6)CSocket：通信を行う「ソケット」を実装 (7)その他：上記のいずれにも属さないクラス この開発では，MFCがフレームワークとして再利用されているため，MFCから分類クラスを選びました． 選んだクラスはCDocument, CView, CDialog, CWinApp, CFrameWnd, CSocketの6種類です． たとえば，Cdocument分類のクラスは，アプリケーションのデータを格納する機能を持ち， Cview分類のクラスは，ユーザーに対してデータを表示する機能を持ちます． 2000/12/21

収集されたメトリクス値の分布(1/2) CDocument CDialog CView CWinApp CFrameWnd CSocket クラス分類ごとに，メトリクスの計測値をレーダーチャートにしたものを示します． メトリクスの値はすべてのクラスについての平均を1としています． レーダーチャートの細い線は，ここのクラスのメトリクス値を表し， レーダーチャートの黒い太い線は，その分類ごのと平均値を示しています． たとえば，CdocumentとCviewを比べると， CdocumentはNIVが大きい，すなわち，インスタンス変数が多くなっていて， CviewはLCOMが大きい，すなわち，凝集度が低いことが分かります． CWinApp CFrameWnd CSocket 2000/12/21

収集されたメトリクス値の分布(2/2) メトリクス値の傾向は，CDocument, CView, CWinApp, CFrameWndで大きく異なる それぞれの分類内では似た傾向にある →クラス分類が適切であったことがわかる その他 特に，CDocument, CView, CWinApp, CFrameWndは大きく異なった傾向を持つことがわかります． また，それぞれの分類内では似たような傾向をもっています． これにより，クラス分類が適切であったことがわかります． 2000/12/21

フォールト予測精度の比較 クラス分類を用いない場合 クラス分類を用いた場合 相関係数で比較すると0.53(分類を用いない)， 次に，クラス分類を用いた場合と用いない場合とで，予測式による予測精度を比較します． 左のグラフはクラス分類を用いない場合， 右のグラフはクラス分類を用いた場合です． グラフの横軸は予測修正時間， 縦軸は実測修正時間で， それぞれの点がクラスを表します． 分類を用いない場合は相関係数が0.53， 分類を用いた場合は相関係数が0.74となり， 分類を用いたほうが予測精度が向上することが分かりました． クラス分類を用いない場合 クラス分類を用いた場合 相関係数で比較すると0.53(分類を用いない)， 0.74(分類を用いる)となる 2000/12/21

考察 クラス分類を行うことによってフォールト予測精度が向上する 統計的には，「クラス分類」というあらたな名義尺度のメトリクスを，ダミー変数として用いることを意味する クラス分類を行う・・・「クラス分類」メトリクスを予測式に取り入れる クラス分類を行わない・・・「クラス分類」以外のメトリクスだけで予測式を立てる 従って，クラス分類間でメトリクス分布に差があれば，分類によって予測精度が向上する 2000/12/21

結論と課題 結論 フレームワークを用いたクラス分類法を提案 評価実験では，CKメトリクスによるフォールト予測精度が向上した 課題 クラス分類の精密化 代表クラス選出の自動化 適用事例の追加 2000/12/21

オブジェクト指向プログラミング言語向けのコードクローン検出手法 [論文の6章] コードクローン 既存のクローン検出手法 問題点 提案するクローン検出手法 適用実験 結論と課題 次に，論文の6章の内容である， 「オブジェクト指向プログラミング言語向けのコードクローン検出手法」について説明いたします． 2000/12/21

コードクローンとは ソースコード中に類似したコード片があるとき，それらをコードクローンという 2000/12/21

コードクローンが起こす問題 コードクローンはソフトウェア保守を困難にする クローンにフォールトが含まれる場合，すべてのクローンについて修正を行わなければならない 機能追加も同様 設計書には表れないソースコードの潜在的欠陥 大規模なソースコードからクローンを人手で発見するのは非現実的である クローンが引き起こす問題としては， クローンが存在するとソフトウェアの保守が困難になるという問題があります． クローンにフォールトが含まれる場合， すべてのクローンについて修正を行わなければなりません． 機能を追加する際にも同じことが言えます． そのため，クローンは「設計品質の劣化」であるといわれています． クローンに対処するためには，まずクローンの存在を知らなければなりません． そのため，特に，大規模なソースコードから，クローンを検出するための手法が提案されています． 2000/12/21

既存のクローン検出手法(ツール) Dup[Baker] 行単位でソースコードを比較してクローンを検出する →基本的に入力ソースファイルの記述言語を問わない Baxterらのツール[Baxter] C言語のソースファイルを入力，構文解析して，解析木(の部分木)を比較する [Baker] B. S. Baker: “On finding Duplication and Near-Duplication in Large Software System,” Proc. of The Second IEEE Working Conf. on Reverse Eng., pp. 86-95, Tronto, Canada (Jul., 1995). [Baxter] I. D. Baxter, A. Yahin, L. Moura, M. Sant’Anna, and L. Bier: “Clone Detection Using Abstract Syntax Trees,” Proc. of ICSM ’98, pp. 368-377, Bethesda, Maryland (Nov., 1998). そのような手法として，代表的なものに BakerのDupというツールと， Baxterらのツールがあります． Bakerのツールは，ソースコードを行単位で比較して，クローンを検出するツールです． 行単位の処理を行うため，基本的にどのようなプログラミング言語で記述されたソースコードからでも， クローンを検出することが出来ます． これに対して， Baxterらのツールは，C言語のソースファイルを入力し，構文解析し，構文木を作り， その部分木を比較します． 2000/12/21

問題点 オブジェクト指向プログラミング言語への対応 オブジェクト指向プログラミング言語では，クラスのスコープルール，名前空間，汎用型などにより，構造をもった名前が用いられる std::map<int, std::string> クローンを選択する手法 テーブルの初期化など，検出しても意味がないクローンがある 従来のコードクローン検出ツールの問題点として， オブジェクト指向プログラミング言語への対応が不十分であることがあげられます． オブジェクト指向プログラミング言語では， クラスのスコープや，名前空間，汎用型などにより， 構造をもった複雑な名前が用いられます． また，クローンを検出したあとで，ソースコードの書き換えを行うことを考えた場合， どのように書き換えるべきクローンを選出するかという問題があります． クローンの中には，テーブルの初期化部分の数字の並びなど， 検出できたとしてもあまり書き換えに適さないものがあります． 2000/12/21

提案するクローン検出手法 ソースコードを字句解析してトークンの列に直してから処理する 文法知識に基づいたコード変形 クラススコープや名前空間による複雑な名前の正規化を行う 初期化テーブルを取り除く モジュールの区切りを認識する 言語依存部分を取り替えることで，さまざまなプログラミング言語に対応 2000/12/21

クローン検出手順 (1)ソースコードを入力し，トークンの列にする (2)変形ルールにより，トークン列を変形する (3)パラメータ置換を行う (4)マッチングアルゴリズムによりクローンを検出する (5)クローンの位置(ファイル，行)を出力する 2000/12/21

ステップ(1)：ソースコードを入力し，トークンの列にする 1. static void foo() throws RESyntaxException { 2. String a[] = new String [] { "123,400", "abc", "orange 100" }; 3. org.apache.regexp.RE pat = new org.apache.regexp.RE("[0-9,]+"); 4. int sum = 0; 5. for (int i = 0; i < a.length; ++i) 6. if (pat.match(a[i])) 7. sum += Sample.parseNumber(pat.getParen(0)); 8. System.out.println("sum = " + sum); 9. } 10. static void goo(String [] a) throws RESyntaxException { 11. RE exp = new RE("[0-9,]+"); 12. int sum = 0; 13. for (int i = 0; i < a.length; ++i) 14. if (exp.match(a[i])) 15. sum += parseNumber(exp.getParen(0)); 16. System.out.println("sum = " + sum); 17. } 2000/12/21

ステップ(2)：変形ルールにより，トークン列を変形する 2000/12/21

(変数，関数，型の識別子を，単一の「パラメータ」トークンに置き換える) ステップ(3)：パラメータ置換を行う (変数，関数，型の識別子を，単一の「パラメータ」トークンに置き換える) 2000/12/21

マッチングアルゴリズムにより，クローンを検出 ステップ(4)： マッチングアルゴリズムにより，クローンを検出 2000/12/21

ステップ(5)：クローンの位置を出力する 1. static void foo() throws RESyntaxException { 2. String a[] = new String [] { "123,400", "abc", "orange 100" }; 3. org.apache.regexp.RE pat = new org.apache.regexp.RE("[0-9,]+"); 4. int sum = 0; 5. for (int i = 0; i < a.length; ++i) 6. if (pat.match(a[i])) 7. sum += Sample.parseNumber(pat.getParen(0)); 8. System.out.println("sum = " + sum); 9. } 10. static void goo(String [] a) throws RESyntaxException { 11. RE exp = new RE("[0-9,]+"); 12. int sum = 0; 13. for (int i = 0; i < a.length; ++i) 14. if (exp.match(a[i])) 15. sum += parseNumber(exp.getParen(0)); 16. System.out.println("sum = " + sum); 17. } 2000/12/21

変形ルールを用いない場合 4-6行目と 13-15行目， 8-10行目と 17-19行目 1. static void foo() throws RESyntaxException { 2. String a[] = new String [] { "123,400", "abc", "orange 100" }; 3. org.apache.regexp.RE pat = new org.apache.regexp.RE("[0-9,]+"); 4. int sum = 0; 5. for (int i = 0; i < a.length; ++i) { 6. if (pat.match(a[i])) 7. sum += Sample.parseNumber(pat.getParen(0)); 8. } 9. System.out.println("sum = " + sum); 10. } 11. static void goo(String [] a) throws RESyntaxException { 12. RE exp = new RE("[0-9,]+"); 13. int sum = 0; 14. for (int i = 0; i < a.length; ++i) { 15. if (exp.match(a[i])) 16. sum += parseNumber(exp.getParen(0)); 17. } 18. System.out.println("sum = " + sum); 19. } 4-6行目と 13-15行目， 8-10行目と 17-19行目 変形ルールを用いなかった場合には，行3と行12，行7と行16が異なった行であると判定されるため，検出されるクローンはいずれも3行以下のクローンになります． 2000/12/21

Java向けの変形ルール RJ1：パッケージ名除去 ( PackageName ‘.’ )+ ClassName → ClassName RJ2:Callee挿入 NDotOrNew NClassName ‘(‘ → NDotOrNew CalleeIdentifier ‘.’ NClassName ‘(‘ RJ3:テーブル初期化除去 '=' '{' InitalizationList, '}' → '=' '{' UniqueIdentifier '}‘ ']' '{' InitalizationList, '}' → ']' '{' UniqueIdentifier '}' RJ4:モジュールの分離 トップレベルの定義や宣言の終わりにUniqueIdentifier を挿入する 2000/12/21

最適化 Suffix-treeによるO(n log n)のマッチングアルゴリズム (入力ソースファイルの大きさをｎとして) メモリ使用量を削減 「文の最初のトークンだけがクローンの開始位置となることができる」制約によりメモリ使用量を削減 大規模なソースファイルには分割して処理を行う 2000/12/21

JDKのライブラリへの適用 JDK（Java Development Kit） 1.2.2（サンプルとデモプログラムを除く） 入力ファイルは164８個，約50万行 ツールの実行には，Pentium III 650MHzおよび1GBのRAMを持つPCで約3分を要した 2000/12/21

クローンの散布図 両軸はソースファイルを辞書順に並べたもの 20行以上のクローンを図示 多くのクローンが密集している（A) 最長のクローン（B） B A 2000/12/21

クローンが密集している部分（A） src/javax/swing/plaf/multi/*.javaの29のファイル コード生成ツールによって生成された いくつかはクラス名を除いてまったく同じクラスの定義を含んでいた 31| */ 32| public class MultiButtonUI extends ButtonUI { 33|   160| public static ComponentUI createUI(JComponent a) { 161| ComponentUI mui = new MultiButtonUI(); 162| return MultiLookAndFeel.createUIs(mui, 163| ((MultiButtonUI) mui).uis, 164| a); 165| } 2000/12/21

最長のクローン（B） 最長のクローン（349行） src/java/util/Arrays.javaの18の“sort”メソッド シグネチャ（引数の型と数）が異なる アルゴリズムは同一 2000/12/21

変形ルールの評価 変形／置換なしでは発見されるクローンは半減する 2000/12/21 次に，変形ルールの効果を定量的に評価するため， 変形ルールを用いた場合と，用いない場合で，検出されるクローンを比較しました． 下のグラフは，JDKのライブラリから検出したクローンの長さのヒストグラムです． 水色の棒は変形ルールを適用した場合， 赤色の棒は変形ルールを適用しない場合です． 適用しない場合には，検出されるクローンが半減することが分かります． また，変形ルールを適用した場合には80前後の長さであると判定されるクローンが 適用しない場合にはより短くなってしまうことも分かります． 2000/12/21

その他の適用実験 オープンソース Qt(C++，2４万行) C++向けの変形ルールの効果を確認した LinuxとFreeBSDのカーネルとドライバ(C，160万行＋130万行) ドライバ部分にクローン「ファイル」が多数存在する システム間で名前が異なるファイル 商用 NTTデータ (出入国管理システム) COBOL，120万行 NASDA(ロケットの制御・管制) C，50万行 2000/12/21

結論と課題 結論 ソースコードの変形を用いるコードクローン検出手法を提案した 実験では，提案する手法がJDKのライブラリから効果的にコードクローンを検出することが確認された 課題 構文によるクローン選別 クローン除去 クローン検出の保守プロセスでの利用 「横並びリスト」を補完する手段 2000/12/21

むすび 複雑度メトリクスによるフォールト予測 再利用を考慮した構造メトリクス計測法 CKメトリクスを開発プロセスの初期に計測する手法 フレームワークを用いた開発においてクラス分類を行い予測精度を高める手法 →フレームワークによってクラス分類を行う手法を提案し，実験によってフォールト修正時間予測精度を評価 コードクローン検出 オブジェクト指向プログラミング言語向けのコードクローン検出手法 →検出手法を提案し，JDKのソースファイルに適用した 以上，論文の4章と6章について説明しました． 論文全体の結びとして， 2000/12/21

2000/12/21

Suffix-tree 以下の条件を満たす木 (1)木の葉は部分文字列の開始位置 (2)根から葉までラベルをたどると部分文字列になる (3)ひとつの節点から出る辺のラベルはすべて異なる文字で始まる →共通のパス＝クローン （Suffix-treeをO(n)で構築するアルゴリズムが知られている） 2000/12/21