ソフトウェア保守・再利用の支援を目的としたプログラム解析手法に関する研究

プログラム解析技術の

理解支援への応用に関する研究

大学院基礎工学研究科

情報数理系専攻ソフトウェア科学分

野

井上研究室

横森 励士

背景

ソフトウェアの大規模化複雑化に伴い，ソフ

トウェアの構築や保守にかかるコストが増

大し， 多くの労力が必要となっている

ソフトウェア開発や保守作業の支援を目的と

して，プログラム解析が注目されている

プログラム解析

プログラム解析とは

プログラム内の関係や性質を

グラフ化

数値化（記号化）

することにより抽象化し，抽象化した情報を利用し

て目的に応じた解析を行うこと

開発者にとって必要な「プログラムの特

徴」のみの抽出が容易となり，作業支援に役立

つ

プログラムのグラフ化

プログラム解析におけるグラフ化とは

解析対象内の個々の要素間の関係を抽出し，抽象

化して表現すること

グラフ化の例

–

_{手続き，メソッドなどの呼び出し関係のグラフ化}

–

_{クラス階層構造のグラフ化}

–

_{プログラム依存グラフの構築}

利用目的に応じて解析技術が提案されている

自動生成

対象の限定

検証

A

B

Class A{

………}

Class B extends A{

………}

Class C extend B{

………}

Class D extend B{

………}

_C

_D

必要な関係だけを抽出

プログラムの数値化（記号化）

プログラム解析における数値化（記号化）とは

解析対象における個々の要素を抽象化し，性質を取り出

す

解析対象における個々の要素を列挙し，全体の性質を表

現する

数値化（記号化）の例

–

_{クラス数，メソッド数， LOC などのメトリクスの抽出}

–

_{トークンの記号化}

グラフ化した情報を利用することもある

利用目的に応じて解析技術が提案されている

プログラムの品質・再利用性評価

コピー（クローン）の把握

クラスタリング（分類）

A

B

Class A{

………}

Class B extends A{

………}

Class C extend B{

………}

Class D extend B{

………}

C

D

総クラス数：４

クラス階層の深さ：３

子の数の和：５

：

：

：

性質を取り出す

研究の対象とその目的

研究の対象

プログラム内の関係のグラフ化を利用した解析

情報漏洩解析

影響波及解析

プログラムの性質の数値化

ソフトウェア部品の再利用性評価手法

研究の目的

プログラム理解支援への利用を考慮した手法の

提案

構築したシステムの評価

論文の構成

第 1 章 . まえがき

第 2 章 . プログラムスライシングを利用した情

報漏洩解析手法の提案と実現 [1-a-1]

第 3 章 . オブジェクト指向プログラムの変更作

業を支援する影響波及解析システム [1-a-2]

第 4 章 . 利用実績に基づくソフトウェア部品重

要度評価システム [1-a-3]

第 5 章 . 動的情報を利用したソフトウェア部品

評価手法の提案と評価 [1-a-4]

第 6 章 . あとがき

プログラムスライシングを利用

した情報漏洩解析手法の提案と実

情報漏洩解析

プログラムに入力される機密度の高い情報が，プログ

ラムの実行を通してどのように処理・出力されるかを

解析

与えられたセキュリティポリシーを満たさない文を検出する

[1]

プログラムの検証が目的

各出力文で出力されうるデータの機密度を情報フローを用い

て解析 [2]

検証だけではなく，「機密性の高い情報が，どの部分に出力されるの

かを把握したい」などの場合に，プログラム理解支援にも利用できる

[1]J.Bantre, C.Bryce and D.Le Metayer: ``Compile-Time Detection of Information Flow in Sequential Pr

ograms'', Proc.3rd ESORICS, LNCS 875, pp. 55--73, 1994.

[2]

_{國信茂太 , 高田喜朗 , 関 浩之 , 井上克郎 : " 束構造をもつセキュリティクラスに基づく再帰的プロ}

グラムに対する情報フロー解析法 ", 電子情報通信学会論文誌 D-I, Vol.J85-D-I, No.10, pp.961-973, 200

2

セキュリティクラス（ＳＣ）

データの持つ機密度や利用者のアクセス権限をセ

キュリティクラスとよぶ

各 SC を元とする束を用いて表される

一意な最大元、最小元が存在

任意の 2 元の最小上界，最大下界が

定義されている

3

high(

最大元 )

low(

_{最小元 )}

1

2

0

SC

を用いて表されるモデル

利用者は，自分の持つアクセス権限以下の

セキュリティクラスを持つデータを参照可能

全てのデータに対してセキュリティクラスを設定

全ての利用者にアクセス権限を設定

ＳＣを利用したアクセス制御

高

低

情報フローとは

プログラム中の変数間に存在するデータ授受関係

explicit flow

:

_{変数の定義～参照間に存在}

implicit flow

:

分岐 ( 繰り返し ) 命令の条件節と内部の文の間に存在

1: b := 5;

2: c := 5;

3: if ( c > 0 ) then begin

4: a = b

5: end;

情報フローを用いた解析の例

a (SC:1)

_{のデータと b (SC:2) のデータが}

３行目の c の値の決定に利用される

代入後の c のデータを参照できるの

は、 a 、 b 両方のデータを参照できる利用

者であるべき

代入後の c の SC は a と b の SC の最小

上界として求められる ( この場合 SC 3)

3

1

2

0

セキュリティモデル

1: readln(a);

2: readln(b);

3: c = a + b;

explicit flow

情報漏洩解析の問題点

情報フローを用いた情報漏洩解析に関して

は，手法の提案および健全性の証明のみで，

実現がなされていない

情報漏洩解析の実現

プログラム依存グラフ (PDG) を利用した情

報漏洩解析手法

PDG

_{の辺と情報フローの類似性に着目}

2

種類の実現手法

ＰＤＧ構築ルーチンを流用して解析を行う手法

[1-a-1]

–

_{データフロー方程式に基いた，繰り返し計算による解析}

ＰＤＧを利用して解析を行う手法

–

_{プログラムスライスにおけるＰＤＧ探索ルールに基づいた解}

析

» PDG

の利用による汎用性の向上

プログラム依存グラフ

（ Program Dependence Graph, PDG ）

プログラムの各文を頂点、

文間に存在する依存関係を

有向辺としたグラフ

プログラムの文間の依存関

係

データ依存関係

変数の定義～参照

制御依存関係

条件節～述部

データ依存辺

制御依存辺

PDG

1: a=5;

2: b=3;

3: if (b>0) {

4: c=a;

5: }else{

6: d=b;

7: }

データ依存関係

制御依存関係

1

₂

3

4

6

情報フローと PDG が示す依

存関係には等価性がある

explicit flow

_{とデータ依存関}

係，

implicit flow

_{と制御依存関係}

を対応させる

ＰＤＧを利用した解析手法の利点

スライシング手法およびＰＤＧを構築する手法は様々な言

語において提案されている

言語の違いを考慮して，ＰＤＧが構築されているため，スライスの

計算時には，グラフ上の辺をたどり到達可能な節点を求めるだけで

よい

情報漏洩解析の実現においては

プログラムスライスにおけるＰＤＧをそのまま利用

辺をたどる際にプログラムスライスにおける探索手法を利用

情報漏洩解析手法の他言語への移植が容易に

PDG

を利用した情報漏洩解析の実現

PDG

PDG

を構築

SC

の初期化

セキュリティモデルの読み込

み

各入力文に対応する頂点に対

し SC の初期値を与える

各入力文を起点として PDG

を探索し、各頂点の SC を

求める

すでに高い SC が与えられて

いる頂点への辺はたどらない

探索が合流する頂点では SC

の最小上界をとる

結果を出力

セキュリティモデル

データ依存辺

入力文

その他の文

制御依存辺

起点

起点

起点

SC

制約機能の追加

関数の戻り値データに対する SC 制約機能を付加

情報漏洩解析の問題点

情報を隠蔽可能な暗号化通信路の存在や、情報の復元や類推が不

可能な状況は考慮されていない

現実的には問題がないデータの SC が過度に高くなってしまう場

合がある

ユーザが「重要な情報の復元・類推が不可能である」と

判断できる関数の戻り値データに対し、その SC をユー

ザが指定できる

関数の戻り値は，ユーザが把握しやすい

現実的な情報漏洩解析を可能に

情報漏洩解析システムの実現

(1/2)

既存のスライス抽出システム（ Osaka

Slicing System

）に機能追加の形で実現

評価 : 成績管理システムへの適用 (1/

４ )

事例 : 学生の成績管理システム ( 約 400 行 )

_認証関数

認証番号

入力

_・

_{入力によりユーザを識別}

・

ユーザの種類を

戻り値として返す

main

_関数

return

利用者が可能な処理を実行

教養事務の処理関数

学生の処理関数

専門事務の処理関数

・全学生の教養科目の

成績の更新

・自身の両科目の

成績の参照

・全学生の専門科目の

成績の更新

教養事務

学生

専門事務

認証関数の戻り値を条件式として分岐

評価 : 成績管理システムへの適用 ( ２

/

４ )

成績管理システム上でのセキュリティモデ

ル

4

セキュリティモデル

0

1

2

3

5

6

主なデータ

データの SC

教養科目の成績

₁

専門科目の成績

₂

教養科目の事務の認証番号

₃

学生の認証番号

₄

専門科目の事務の認証番号

₅

ユーザおよびそのアクセス権限

学生 ： 4 教養事務 : 3

専門事務 : 5 システム管理者： 6

評価 : 成績管理システムへの適用 (3/

４ )

SC

_{が高い出力文が非常に多い}

一つの認証関数で， 3 種類あるユ

ーザの種類を一度に判定する

認証関数の戻り値の SC が

教養科目の事務の認証番号

学生の認証番号

専門科目の事務の認証番号

の最小上界をとる

認証関数の戻り値を隠蔽した場

合を想定し，戻り値の SC を low

として設定

4

セキュリティモデル

0

1

2

3

5

6

1

1

26

5

0

₀

0

各 SC の右下の数字 :

結果その SC となった出力文の数

2

1

27

2

1

0

0

評価 : 成績管理システムへの適用 ( ４

/

４ )

戻り値の SC を low として設定した

ところ，ほとんどの文の SC が０と

なった

各ユーザに対応した処理内で，データ

を出力する部分のみが高くなった

認証の結果を隠蔽すれば，情報漏洩の

危険性は微々たるものに

SC

_{を制約する機能を組み込む事で}

，現実的な情報漏洩解析が可能とな

る

隠蔽すべきデータを判断する基準を与

える

4

セキュリティモデル

0

1

2

3

5

6

各 SC の右下の数字 :

結果その SC となった出力文の数

まとめ

PDG

を利用した情報漏洩解析手法を提案し

，実現した

情報漏洩解析の効率化と、汎用性の向上

適用事例を紹介し，手法の有効性を確認

SC

制約機能による現実的な利用度の向上

利用実績に基づくソフトウェ

ア 部品重要度評価システム

背景

ソフトウェア開発効率を向上するための手法と

して、再利用が注目されている

再利用とは既存のソフトウェア部品を同一システム

内、他のシステム内で用いること

開発者が再利用を行う単位をソフトウェア部品と呼ぶ

部品の例 : ソースコード，ドキュメント， ソフトウェア…

部品が再利用に適しているか判断するために、

再利用性を定量的に示すことが必要

過去に開発した大量のソフトウェア部品から再利用

しやすい部品を見つけるのに役立つ

ソフトウェア部品に対する理解支援

従来の再利用性評価手法

従来の再利用性評価手法は、部品単体の特性から評

価している

コードメトリクスを足し合わせて再利用性を評価 [1]

インターフェース部分の情報から再利用性を評価 [2]

[1] L. Etzkorn et al.: ``Automated reusability quality analysis of OO legacy software,'' Information a

nd Software Technology, Vol. 43, Issue 5, pp. 295-308 (2001).

[2]

山本 他 : `` 再利用特性に基づくコンポーネントメトリクスの提案と検証 ," FOSE2001,

(2001).

利用実績に基づいた定量的な評価手法が必要

部品単体の特性からは再利用性が低いと評価され

ていても、実際には頻繁に再利用されている部品

も存在する

研究の目的

利用実績に基づくソフトウェア部品評価手法

（ Component Rank 法）の提案

部品間の利用関係から利用実績を定量的に評価

提案手法による部品評価システムを実装

Java

_{ソースコードに対して適用実験を行う}

提案手法が利用実績を反映しているか

Component Rank

法

利用関係から部品の利用実績

（ Component Rank ）を評価する手法

開発者による部品の参照行為をモデル化

よく利用されている部品や重要な部品から利用さ

れている部品の評価が高くなる

利用実績の定量的な評価が期待できる

計算手順

1.

部品間の利用関係をグラフとして表現

2.

利用関係に重みをつけ，各部品の利用実績を繰り

返し計算により求める

部品グラフの生成

部品間の利用関係を部品グラフ化して表現

頂点：ソフトウェア部品

有向辺：利用関係

利用する側からされる側に有向辺を引く

c

₄

c

₁

c

₁

'

c

₂

c

₂

'

c

₅

c

₃

(a)

部品間の関係

c

₄

c

₁

c

₁

'

c

₂

c

₂

'

c

₅

c

₃

部品群グラフの生成 (1)

実際に部品を抽出した場合、コピーした部品や

コピーして一部変更した部品が多く存在する

コピーされたと判断できる部品は一緒の部品群とみ

なす

c

₄

c

₁

c

₁

'

c

₂

c

₂

'

c

₅

c

₃

(a)

_{部品間の関係}

C

₁

C

₂

C

₃

C

₄

C

₅

部品群グラフの生成 (2)

所属する部品同士に利用関係があれば、部品

群間にも利用関係がある

部品グラフから部品群グラフを生成

c

₄

c

₁

c

₁

'

c

₂

c

₂

'

c

₅

c

₃

C

₁

C

₂

C

₃

C

₄

C

₅

利用関係から部品の Component Rank を求める

部品群グラフの利用

計算手順

1.

各頂点に適当な重みを与える

頂点の重みの総和は 1

2.

各有向辺の重みを求める

頂点の重みを，その頂点から出ていく辺で分配する

3.

各頂点の重みを再計算

頂点に入ってくる辺の重みの総和を，その頂点の重みとして再定義する

4.

頂点の重みが収束するまで， 2.3. を繰り返し計算する

5.

収束した頂点の重みを，その頂点に対応する部品群の評価値として求

める

–

_{部品の評価値は属する部品群の評価値とする}

–

_{評価値に基づいて順位付けした部品の順位を}

_{Component Rank}

_とする

C

₁

0.334

C

₂

0.333

C

₃

0.333

C

₁

0.334

C

₂

0.333

C

₃

0.333

v

₁

×50%

v

₁

×50%

v

₂

×100%

v

₃

×100%

C

₁

C

₂

C

₃

0.167

0.167

0.333

0.333

C

₁

0.333

C

₂

0.167

C

₃

0.500

C

₁

C

₂

C

₃

0.1665

0.1665

0.167

0.500

C

₁

0.500

C

₂

0.1665

C

₃

0.3335

C

₁

0.400

C

₂

0.200

C

₃

0.400

0.200

0.200

0.200

0.400

利用実績の計算

Ｊａｖａ部品評価システムの実現

Java

_{ソースコード (N 個 )}

ファイル間の関係

抽出部

SMMT

クラスタリングによる

部品群化部

部品群間の関係

抽出部

繰り返し計算部

ファイル順位決定部

N

_{個のファイルの順位}

類似度判定部

（ SMMT ）

ソースコードファイルを

部品として入力

部品間の利用関係：

インターフェイスの実装

メソッド呼出，継承

ソースコード間

で

一致する行の割

合

適用実験

実現したシステムをもとに， Java ソースコ

ードに対して適用実験を行う

提案手法が利用実績を反映しているか

適用対象

ＪＤＫ 1.3.0

研究室内で開発したソースコード

JDK

への適用

JDK (Java Development Kit) 1.3.0

のソースコー

ドへ適用 (1877 files, 18.4MB)

言語仕様上、直接的、間接的に利用しなければ

ならないクラスが上位を占めている

順位

クラス名

評価値

1 java.lang.Object

0.161269

2 java.lang.Class

0.087124

3 java.lang.Throwable

0.055101

4 java.lang.Exception

0.031032

5 java.io.IOException

0.013438

6 java.lang.StringBuffer

0.012144

7 java.lang.SecurityManager

0.011700

8 java.io.InputStream

0.010277

9 java.lang.reflect.Field

0.009483

研究室内ソースコードへの適用

研究室内で作成したツールと、使用したパッケージのソ

ースコードへ適用 (582 files, 6.1MB)

同一部品群にある部品は同一評価値を持っている ( ２，８位）

作成ツールより使用パッケージの方が評価が高い

使用パッケージ内のクラスが１～ 8 位（上位９クラス）を占める

作成ツール内のクラスは１０位が最上位

ソフトウェア部品検索への応用

ＣＲ法による順位付けをソフトウェア部品検索へ応用

インターネットを通じてソフトウェア部品を収集

あらかじめ，ＣＲ法で部品を順位付け

検索エンジンを通じて検索

検索結果を CR 法による順位をもとに表示

インターネット

部品リポジトリ

部品の収集

Ｃ R-System

部品検索

エンジン

検索キー

_検索結果

順位付け

開発者は利用実績の高い部品を

手軽に取得できる

まとめ

部品間の利用関係から利用実績を評価する手

法（ CR 法）を提案した

提案する手法に基づいて利用実績の評価を行

うシステムを開発し、 Java ソースコードを

対象に適用した

適用結果から、提案する評価手法が利用実績を反

映していることが示された

むすび

プログラム理解支援を目的とした，プログラ

ム解析技術の応用化手法を提案した

プログラムスライシングを利用した情報漏洩解

析手法

利用実績に基づくソフトウェア部品重要度評価

手法の提案

提案手法それぞれにおいて適用事例を示す事

で，有効性を確認した

プログラムの保守工程や，テストにおいて利用

することで，ソフトウェア開発における生産性

の向上が期待できる

今後の研究方針

大規模なプログラムへの適用

　情報漏洩解析

他言語への実装

大規模プログラムを想定した視覚化手法の利用

　 CR 法

大量の部品に対する CR 法の適用

保守工程やテスト工程における利用を想定した手法

の評価

CR

法の評価

CR

_{法と既存の再利用性評価手法との比較}

部品検索システム SPARS における， CR 法による順位

付けの評価

評価値の計算例

相対的再利用性評価値を求める計算は行列の

固有ベクトルを求める計算に帰着される

C

₁

v

₁

C

₂

v

₂

C

₃

v

₃

50%

50%

100%

100%























3

2

1

v

v

v

V























0

1

5

.

0

0

0

5

.

0

1

0

0

D

V = D

・ V

λ=1

（絶対値最大）の固有ベクトル

C

₁

0.400

C

₂

0.200

C

₃

0.400

0.200

0.200

0.200

0.400

































































4

.

0

2

.

0

4

.

0

0

1

5

.

0

0

0

5

.

0

1

0

0

4

.

0

2

.

0

4

.

0

評価値計算の補正

利用関係を投票とみなして，票の重みの偏りを分析

することで相対的再利用性を評価している

利用してない部品に対しても非常に低い重みの票を投票した

とみなす

票が全体に循環せず正しく評価できない場合がある

この部品の評価値が０となり，

部品の利用関係を反映出来ない

この部品からの利用関係を

評価値に反映

ソフトウェア部品検索への利用

利用実績に基づくソフトウェア部品検索シス

テム SPARS （ Software Product Archiving,

analyzing and Retrieving System

）

現在， Java を対象として， SPARS-J を構築中

公開されている Java ソースファイルを収集し，解析

を行い，解析情報を元に検索システムを構築

Component Rank

を検索結果の表示順位に利用

検索への適用例

XML

を利用しているアプリケーション群

（ 7171 ファイル）に対する検索

getNodetype

というクエリーで検索

DOM

ツリーにおいてノードの種類を得るためのメ

ソッド

Grep

を用いて検出できたクラス中で，コメントのみに

getNodetype

という単語が現れるクラスを削除

検索の結果 128 クラスを検出

Component Rank

でソート

検索の結果

getNodetype

の定義に関するクラスが上位に （ 1 位， 2 位）

定義クラスはこの二つのみ

一般的な利用例が上位に

ノードの操作（ 3 ～ 5 位， 10 位）

スタイルシートなどの XML 文書の解析（ 6 ～ 9 位）

表示順位の決定に CR 法を用いることで

•

_{大量の部品の中からでも部品定義に関}

する情報を取得しやすくなる

•

_{利用方法を知りたい場合にも，一般的}

な利用方法から参照できるようになる

0 1 2 3 4 5

0 0 1 2 3 4 5

1 1 1 3 3 5 5

2 2 3 2 3 4 5

3 3 3 3 3 5 5

4 4 5 4 5 4 5

5 5 5 5 5 5 5

一般的なセキュリティモデルへの対

応

束上の任意の 2 元の最小上界を二次元行列で記述

二次元行列を参照することで、最小上界が求められる

一般的なセキュリティモデルへの対応

3

1

2

0

4

5

セキュリティモデル