情報処理学会論文誌

Vol.55 No.2 971–980 (Feb. 2014)

Thin Slice のサイズに関する統計的評価
秦野 智臣1,a)

鹿島 悠1,b)

石尾 隆1,c)

井上 克郎1,d)

受付日 2013年5月16日, 採録日 2013年11月1日

概要：プログラム理解の時間を減らすための技術として，プログラムスライシングが提案されている．プ
ログラムスライシングは，プログラム内のある文を基準として，その文に影響を与える可能性のあるすべての文をプログラムスライスとして抽出する技術である．しかし，大規模プログラムの場合は，プログラ
ムスライス自体が非常に大きくなってしまい，プログラム理解への利用は難しい．Thin Slicing は，開発者の選んだ文が使用するデータを生成した文のみを抽出することで，プログラムスライスのサイズを減らす技術である．しかし，一般に Thin Slicing が，どの程度の大きさのプログラムスライスを抽出するのかは示されていない．本研究では，7 個の Java プログラムのすべてのデータフローを対象に Thin Slice を計算し，そのサイズに関する統計的評価を行った．その結果，Thin Slice のサイズは平均でプログラムの2.1%であり，60 から 80%のスライスでは 0.1%以下と十分小さくなることを確認した．
キーワード：プログラムスライシング，データフロー解析，静的解析，Java

A Statistical Evaluation of Thin Slice Size
Tomomi Hatano1,a)Yu Kashima1,b)

Takashi Ishio1,c)Katsuro Inoue1,d)Received: May 16, 2013, Accepted: November 1, 2013

Abstract: Program slicing is a technique which supports program comprehension. Program slicing extracts
all statements — called a program slice — that may aﬀect a certain statement. However, program slicing is
not useful if an analysis target program is too large since program slices of such a program are also often toolarge. Thin slicing is a technique reducing the size of program slice by extracting only statements producing
data which is used by a selected statement. However, the size of Thin Slice in general has not been revealed.
In this paper, we computed Thin Slices for every data-ﬂow path in 7 Java programs, and then performed
statistical evaluation. As a result, the average size of Thin Slice is 2.1% of a program. Furthermore, 60 to
80% of Thin Slices are 0.1% or less.
Keywords: program slicing, data-ﬂow analysis, static analysis, Java

1. まえがき

スコードの位置を知ることである．機能の実装位置を知っている開発者は，そうでない開発者よりも効率的にソース

開発者はプログラムの保守作業に多くの時間を費やして

コードの変更作業を行うことができる [3]．開発者がプログおり，保守作業の中でも，多くの時間をプログラム理解に費

ラムの機能とソースコードとを対応づけるための手がかりやしているといわれている [1], [2]．プログラム理解においの 1 つが，変数の代入と参照の関係を表すデータ依存関係て重要となるのが，変更したい機能が実装されているソーである．引数やフィールドを介して同一のデータを使用する複数のメソッドを特定することが，機能の実装位置を正

1

a)
b)
c)
d)

大阪大学大学院情報科学研究科
Graduate School of Information Science and Technology,
Osaka University, Suita, Osaka 565–0871, Japant-hatano@ist.osaka-u.ac.jp
y-kasima@ist.osaka-u.ac.jp
ishio@ist.osaka-u.ac.jp
inoue@ist.osaka-u.ac.jp

c 2014 Information Processing Society of Japan

しく認識するために有効であると報告されている [4]．一方で，静的な依存関係を探索するために開発者が多くの時間を必要とすることも報告されている [5]．
プログラム理解の作業時間を減らすための技術として，プログラムスライシングがある [6]．プログラムスライシ

971

情報処理学会論文誌

Vol.55 No.2 971–980 (Feb. 2014)

ングは，プログラム内のある文を基準として，その文に影響を与える可能性のあるすべての文をプログラムスライス（以降，単にスライスという）として抽出する技術である．

2. 関連研究2.1 プログラムスライシングプログラムスライシングによって，開発者がプログラム理プログラムスライシングは，プログラム内のある文に影解のために読むコードが少なくなり，理解にかかる時間を響を与える可能性のあるすべての文を抽出する技術であ減らすことができる．しかし，スライスのサイズの平均値

る [6]．スライスの計算には，プログラム依存グラフ（Pro-は，プログラム全体の約 30%であり [7]，大規模プログラ

gram Dependence Graph，以下 PDG）を拡張したシステム

ムの保守作業におけるプログラム理解の際に，プログラム

依存グラフ [10]（System Dependence Graph，以下 SDG）

スライシングを利用することは困難である．

を用いる．PDG は，プログラム内の 1 つの手続きの各文

スライスのサイズを減らす手法として，Thin Slicing がを頂点とし，それらの頂点間の依存関係を有向辺で表した

提案されている [8]．Thin Slicing は，基準となる文が使用グラフである．SDG は，手続きごとの PDG を呼び出し関するデータを生成した文のみを抽出するスライシング手法

係によって接続したグラフである．

である．本稿では，Thin Slicing により抽出された文のこ

スライスは，スライスを計算するための基点となる文ととを Thin Slice と呼ぶが，Thin Slice は通常のプログラム

変数を定め（これをスライシング基準という），その基点スライスに比べサイズが非常に小さくなる．また，同一のに相当する SDG 上の頂点から有向辺に沿った探索を行い，データが使用される場所を特定する場合は，データフロー

基点となった頂点自身を含む到達範囲の頂点集合として計だけに着目する Thin Slicing のほうがプログラムスライシ

算される．スライスの計算方法は，後ろ向きスライシング

ングより適しており，プログラムの機能の実装位置を認識と前向きスライシングに分けられる．

する作業に有用であると考えられる．文献 [8] では，Thin

後ろ向きスライシングは，スライシング基準の実行にSlicing によりプログラム理解の時間が減少した例が 22 個

影響を与える可能性のあるすべての文の集合を計算する．

紹介されている．

図 1 の 10 行目の文 c = add(a, b) と変数 c をスライシン

Thin Slicing は有望な手法であるが，一般的な状況におグ基準として後ろ向きスライシングを実行すると，10 行目

いてつねに有効であるかどうかは明らかではない．従来のの文が使用する変数 a と変数 b の値を定義している 6 行目

スライシング手法については，Binkley らによってスライと 7 行目の文，さらに手続き呼び出し先の add で 2 つの値

スサイズの平均値が計算されている [7]．また，Jász ら [9]の和を計算している 19 行目が抽出され，スライスは {6，は，メソッド呼び出しと制御依存関係のみを用いたスライ

7，10，19} 行目となる．前向きスライシングは，スライシスの高速な近似計算を提案しており，その計算結果の平均

ング基準の実行に影響を受ける可能性のあるすべての文の値はスライスサイズの平均値より 4.27%大きくなることを集合を計算する．図 1 の 8 行目の文 x = new A() と変数 x示している．Binkley らや Jász らの研究のように，Thinをスライシング基準として前向きスライシングを実行する

Slicing においても Thin Slice のサイズの平均値を計算し，と，変数 x の値を使用する文とその値によって実行を制御

その有効性を評価する必要がある．

される文が抽出され，スライスは {8，9，11，12，13，14，

本研究では，Java 言語で記述されたプログラムを対象と15} 行目となる．

した Thin Slicing を実装し，Thin Slice のサイズに関する統計的評価を行う．文献 [8] では，22 個の例で有効である
ことが確認されているだけなのに対し，本研究では Thin

2.2 プログラムスライシングの利用方法
プログラムスライシングは，プログラム理解やデバッグ

Slice のサイズの平均値を計算し，多くの場合で有効であるかどうかを確認する．スライスサイズが十分に小さけれ
ば，開発者が閲覧しなければならない文が少なくなる．また，データの生成元や使用先を Thin Slicing によって特定できれば，開発者がデータ依存関係を調査する作業の時間が削減できる．しかし，メソッド呼び出しをたどらなくてもデータを生成している文が容易に見つかる場合は，Thin

Slicing の効果は低いと考えられる．そのため本研究の実験
では，プログラム中の全データフローから Thin Slicing の効果が期待できるデータフローの割合を調査するために，スライスサイズに加え，スライスがまたがるメソッド数や，使用しているデータの生成元となっている文の数といった

図 1

指標を計測した．

Fig. 1 Example program.

c 2014 Information Processing Society of Japan

サンプルプログラム

972

情報処理学会論文誌

Vol.55 No.2 971–980 (Feb. 2014)に利用されている．プログラム理解においては，開発者が2.4 Thin Slicing

注目しているソースコード断片の内容を理解するにあたっThin Slicing [8] は，スライシング基準で使用しているて，そこに登場する変数の値がどのように計算されているデータを生成している文のみを抽出することでスライスかを調べる必要があるためである [11]．デバッグにおいてサイズを減らし，プログラム理解やデバッグ作業におけるも，プログラムの誤った出力がどのように計算されたか

開発者の負担を軽減するスライシング手法である．Thin

を知るために，プログラムスライシングが用いられていSlicing には，Context-Insensitive Thin Slicing と Context-

る [12]．Kusumoto らの研究 [13] では，開発者にスライス

Sensitive Thin Slicing の 2 種類の計算方法があるが，本研を提供することでデバッグが効率的になることが示されて究では Context-Insensitive Thin Slicing のみを扱う．これいるほか，コードインスペクション環境におけるスライシ

は，文献 [8] において，Context-Sensitive Thin Slicing のングの利用が報告されている [14]．

計算時間が膨大であり，実用的なプログラムで用いることが現実的ではないことが示されているためである．

2.3 スライスサイズを削減する技術

スライシング基準 s に対する Thin Slice とは，s がデー

2.2 節で示した用途では，プログラムスライシングの結タ依存する文の集合である．Thin Slicing においてデータ

果から得られるプログラムの一部を開発者が直接閲覧す

依存関係は，手続き内，手続き間，ヒープ領域の 3 種類をるため，スライスサイズが小さいほど開発者の作業時間を用いる．

短縮する効果がある．そのため，スライスサイズを減らす

手続き内のデータ依存関係は次のように定義する．文 s2

様々な手法が提案されており，一般的な場合で利用できるが s1 にデータ依存するとは，以下の条件がすべて成り立

手法と，ある特定の条件で利用できる手法に分けられる．

つことをいう．

一般的な場合で利用できる手法として，Chopping と呼ば( 1 ) s1 が変数 x の値を定義する．

れる手法 [15] は，データを生成している頂点と使用してい( 2 ) s2 が変数 x の値を使用する．

る頂点について，前向きスライシングと後ろ向きスライシ( 3 ) s1 から s2 に，x の値を書き換えない実行経路が少なングを計算し，その積集合を計算する．Reps ら [16] は，1

くとも 1 つ存在する．

つの手続き内で制限されていた Chopping を手続き間で用

ただし，ポインタ変数を介してヒープ領域にアクセスしいることができるように拡張している．Distance-Limitedている文については，ヒープ領域についてのみ依存関係をSlicing [17] は，PDG における頂点間の距離を定義し，その考える．たとえば，p.f というフィールドを参照する文は，距離内の範囲で到達できる頂点のみを探索する手法である．
ある特定の条件で利用できる手法として，Chen ら [18]f に関するデータ依存関係のみを考え，p に関するデータ依
存関係は無視する．

は，プログラムのある機能について，その機能の実装方法

手続き間のデータ依存関係は次のように定義する．

とプログラム中の位置を開発者が理解することを目的とし• 手続きの実パラメータに対応する頂点に，呼び出し先たグラフの探索方法を提案している．この方法では，開発の仮パラメータに対応する頂点がデータ依存する．

者が指定したスライシング基準とその頂点から有向辺が• 呼び出し先の返り値に対応する頂点に，呼び出し元の引かれている頂点のみを最初に表示し，開発者は探索した

返り値を受け取る頂点がデータ依存する．

い頂点を選択する．同様に，選択された頂点から有向辺がヒープ領域のデータ依存関係は，同一のフィールドまた引かれている頂点をさらに表示し，開発者は探索したい頂は配列の内容を代入し参照する可能性のある文の組につい点を選択する．このように，開発者の要求に応じてスライて，所属する手続きに関係なく，参照する文が代入する文

スを表示することで，開発者が閲覧するスライスサイズをにデータ依存していると定義する．

減らしている．Callstack-Sensitive Slicing [19] は，デバッ

Thin Slice は，上記の定義に対応するデータ依存辺を有グにおいて，バグ発生時のスタックトレースを利用するこ向辺とするグラフで探索を行い計算する．図 2 は図 1 のプとでスライスサイズを減らし，バグの発生位置と原因を特

ログラムに対するグラフであり，手続き内の代入文と手続定する手法である．Ceccato ら [20] は，Barrier Slicing [21]き呼び出し文を丸角矩形の頂点で表し，手続き名と制御文と呼ばれる手法を用いて，ある特定の処理を実装しているをひし形の頂点で表している．実パラメータと仮パラメー

部分を探している．Barrier Slicing は，グラフ探索を打ちタに対応する頂点は p(x) = a，x = p(x) のようにパラメー切る頂点を事前に指定してから探索を行い，スライスサイ

タ名 v に対して p(v) と表記し，返り値を受け取る頂点はズを減らす手法である．Wang ら [22] は，ある関数を変更

ret = x + y，c = ret のように ret という仮想の変数を用した際の影響を調査したい場合に，ソースコード中の文字

いて表記し，いずれも長方形の頂点で表している．これらや依存関係を SDG に対して入力すると，その入力条件にの頂点が所属する手続きを点線の枠で表し，頂点間のデー合った SDG の部分グラフを抽出する手法を提案している．

タ依存関係を矢印で表している．たとえば，図 1 の 15 行
目の文と変数 v をスライシング基準とした後ろ向き Thinc 2014 Information Processing Society of Japan


973

情報処理学会論文誌

Vol.55 No.2 971–980 (Feb. 2014)

献 [8] では，Thin Slicing は，13 個のデバッグの例，22 個のプログラム理解の例で有効であることが示されている．
一方で，調べたいデータに関する依存関係が 1 つのメ
ソッド内で完結している場合は，そのメソッドの内容が複雑でない限り，Thin Slicing の効果は低い．たとえば，図 3において，11 行目で出力している変数 a の値について調べたい場合は，その周辺のコードを読めば Thin Slicing を利用しなくても，4 行目で生成された値を使用していることが特定できる．

2.5 スライスサイズに関する調査プログラムスライシングの各手法が，一般にどの程度有効であるかという点については，既存研究で，平均的なス
図 2 図 1 のプログラムに対する Thin Slicing 計算用のグラフ

ライスサイズを求める形で評価が行われている．BinkleyFig. 2 A graph to compute Thin Slicing for the program inら [7] は，スライスサイズは平均でプログラム全体の約Fig. 1.

30%になることを示している．スライスの高速な近似計算を提案した Jász ら [9] は，その計算結果がスライスサイズ
より平均で 4.27%大きくなることを示している．Horwitz
ら [19] は，デバッグ作業において，調査したいスタックト
レースを限定した場合のスライスサイズが通常の約 3 分の1 になることを示している．本研究は Thin Slicing に対して，このような実験によるスライスサイズの評価を行ったものである．

3. 調査目的
本研究では，Thin Slicing が多くの状況で有効に働くかどうかを評価するために，Thin Slice のサイズに関する統図 3

Thin Slicing の例

Fig. 3 Examples of Thin Slicing.

計的評価を行う．具体的なリサーチクエスチョンは，以下の 2 つである．

RQ1 Thin Slice のサイズは，平均的に十分小さいものでSlice は，{6，7，10，12，14，15，19} 行目となる．一方，従来のスライスは実行可能なすべての文となる．
このように Thin Slicing は従来のスライシングよりスラ
イスサイズが小さくなり，使用している変数の値を生成した文がより明確になる．プログラム理解において開発者がデータ依存関係を調査する際に，この特徴を利用することによって調査にかかる時間を減らすことが期待できる．

あるか．

RQ2 データ依存関係の調査において有効であると考えられる Thin Slice はどの程度存在するか．

4. Thin Slicing の実装
本研究では，実験を行うために Java プログラムのバイトコードを対象とした Thin Slicing を実装した．バイトコー

特に，ソースコード中のある文で使用しているデータに

ドはソースコードに比べ解析が容易であるため，本研究のついて開発者が調べたい際に，そのデータが様々なメソッ

実装ではバイトコードを用いる．バイトコードは表 1 のよドを経由して到達している場合や多くの文をたどって到達うな命令からなる．本実装では，バイトコードの 1 命令をしている場合は Thin Slicing の効果が高い．図 3 の例で頂点とし，各命令間のデータ依存関係を辺としたグラフをは，Thin Slicing で計算するデータフローを矢印で示して作成する．本研究で扱うバイトコードの例を図 4 に示す．

いる．たとえば，32 行目で出力している変数 id の値につ

このバイトコードは，図 1 の main メソッドおよび add メ

いて調べたい場合は，クラス X の addData メソッドの呼ソッドに対応しており，そのメソッド内でのインデクスとび出し元をたどっていかないと変数 id の値を生成した文

命令を表している．ただし，FRAME-OP や括弧付きで表は分からないが，Thin Slicing を利用すると Thin Slice と現されている（L1591151994）と（line=6）などの行は，バ

して {7，9，10，17，25，32} 行目が抽出され，7 行目と 9

イトコードの属性情報であり，命令ではない．以降では，行目で生成された値を使用していることが特定できる．文

バイトコード上のデータ依存関係について説明する．

c 2014 Information Processing Society of Japan

974

Vol.55 No.2 971–980 (Feb. 2014)

情報処理学会論文誌

表 1 バイトコード命令の一覧と分類

Table 1 Bytecode instructions.
命令の種類
ローカル変数の読み込み
ローカル変数の書き込み
フィールド変数の読み込み
フィールド変数の書き込み
配列変数の読み込み
配列変数の書き込み
オペランド・スタック管理
オブジェクトの生成分類
transfertransfertransfertransfertransfertransferなし
sourcesourceかつ sink

値を生成する演算

source
定数の生成

sink
比較演算

メソッドの呼び出し
メソッドからの戻り

特殊transfer([Ljava/lang/String;)V
1: (line=6)
2: ICONST_1
3: ISTORE 4 (a)4: (L2025190714)
5: (line=7)

FLOAD
FSTOREGETSTATIC
PUTSTATICFALOAD
FASTOREDUP

31: ILOAD 6 (c)32: PUTFIELD slice/A#f:int

7: ISTORE 5 (b)8: (L1912008895)
9: (line=8)
10: NEW
11: DUP
12: INVOKESPECIAL
slice/A#<init>()V
13: ASTORE 1 (x)14: (L188204557)
15: (line=9)
16: ALOAD 1 (x)17: ASTORE 2 (z)18: (L2058061115)
19: (line=10)
20: ILOAD 4 (a)21: ILOAD 5 (b)22: INVOKESTATIC
slice/Main#add(II)I
23: ISTORE 6 (c)24: (L314057576)
25: (line=11)
26: ALOAD 1 (x)27: ASTORE 3 (w)
28: (L1998359153)
29: (line=12)

DALOADAALOADDASTOREAASTORE
DUP2
DUP X1ANEWARRAY
DADD
ISUB
IDIV
LDIV
LNEG
FNEG
IAND
LAND
I2D
L2I
D2F
I2B

BALOADCALOAD
BASTORECASTORE
DUP2 X1
DUP X2
MULTIANEWARRAY
LSUB
FSUB
FDIV
DDIV
DNEG
ISHL
IOR
LOR
L2F
L2D
I2C
I2S

ICONST 1
ICONST 5
FCONST 1
ACONST NULL
IFGT
IFLE
IF ICMPGE
IF ACMPNEINVOKESPECIAL
ARETURN
RETURNSALOAD
SASTORE
DUP2 X2

SWAP

DSUB
IREM
LSHL
IXOR
F2I
LCMP

IMUL
LREM
ISHR
LXOR
F2L
FCMPL

ICONST 2
LCONST 0
FCONST 2

LDC
BIPUSH
SIPUSHIFNULLIF ICMPEQ
IF ICMPGTIFNONNULLINVOKESTATIC

そのため，ローカル変数とオペランド・スタック間で値を移動させる命令が存在し，オペランド・スタック上の演算

33: (L1925529038)

におけるデータ依存関係だけでなく，ローカル変数とオペ

34: (line=13)

ランド・スタック間のデータ依存関係が存在する．

35: ALOAD 3 (w)
36: ALOAD 2 (z)37: IF_ACMPNE L1935465023
38: (L1425840452)

6: ICONST_2

該当する命令DLOAD
ALOAD
DSTOREASTORE

FADD
DMUL
INEG
LUSHR
I2F
D2L
DCMPG
ICONST 0
ICONST 4
FCONST 0
DCONST 1
IFLT
IFGE
IF ICMPLTIF ACMPEQLOOKUPSWITCHINVOKEINTERFACEFRETURN
DRETURN

30: ALOAD 3 (w)slice/Main#main#
0: (L1591151994)

ILOAD
LLOAD
ISTORE
LSOTREGETFIELDPUTFIELDIALOADLALOAD
IASTORELASTORE
POP
POP2
NEW
NEWARRAY
IADD
LADD
LMUL
FMUL
FREM
DREM
LSHR
IUSHR
IINC
I2L
F2D
D2I
FCMPG
DCMPL
ICONST M1
ICONST 3
LCONST 1
DCONST 0
IFEQ
IFNE
IF ICMPNE
IF ICMPLE
TABLESWITCHINVOKEVIRTUALIRETURNLRETURN

39: (line=14)
40: ALOAD 2 (z)4.2 フィールド変数と配列変数のデータ依存関係
フィールド変数の依存関係は次の 2 つの方法で決定する．1 つ目は，フィールド変数に値を書き込む命令である

41: GETFIELD slice/A#f:int

PUTSTATIC とフィールド変数の値を読み込む命令である

42: ISTORE 7 (v)GETSTATIC が，同じクラスの同じフィールド名に対し43: (L330459891)て行われている場合に PUTSTATIC から GETSTATIC に

44: (line=15)
45: GETSTATIC

依存辺を引く．2 つ目は，PUTFIELD と GETFIELD が，

java/lang/System#out:

エイリアスされている可能性のある変数の同じフィールド

java/io/PrintStream名に対して行われている場合に，PUTFIELD から GET-

46: ILOAD 7 (v)
47: INVOKEVIRTUAL

FIELD に依存辺を引く．エイリアス解析には，Andersen

java/io/PrintStream#のポインタ解析 [23] に基づいた Object-sensitive Pointerprintln(I)V

Analysis [24] を用いた．配列変数はフィールド変数と同様

48: (L1935465023)
49: (line=17)
50: FRAME-OP(0)に，エイリアスされている可能性のある配列に値を書き込む命令から読み込む命令に依存辺を引く．

51: RETURN
52: (L646676895)
slice/Main#add#(II)I
0: (L283836798)

4.3 メソッド間のデータ依存関係あるメソッド呼び出し文から，その呼び出し文で呼び出

1: (line=18)

される可能性のあるすべてのメソッドに対して，実パラ

2: ILOAD 0 (x)メータから仮パラメータへの依存辺と返り値から呼び出

3: ILOAD 1 (y)4: IADDし元への依存辺を引く．メソッドの動的束縛の解決には，

5: IRETURN

Variable-Type Analysis [25] を用いた．

6: (L883883999)

図 4

図 1 に対応するバイトコード

Fig. 4 A list of Java bytecode for the program in Fig. 1.

4.4 オペランド・スタック管理命令
オペランド・スタックを直接操作するための命令については，本研究の実装では，命令の影響をデータ依存関係の4.1 ローカル変数とオペランド・スタック間のデータ依存関係計算に直接反映する．たとえばメソッド呼び出し命令の戻り値が使用されない場合，バイトコード上ではその値を破Java 仮想マシンは，オペランド・スタックと呼ばれるス

棄する POP 命令が使用されるが，メソッド呼び出し命令

タックに，演算で使用する値やその結果を保持している．

から POP 命令へとデータ依存辺を引く代わりに，メソッc 2014 Information Processing Society of Japan


975

情報処理学会論文誌

Vol.55 No.2 971–980 (Feb. 2014)

ライスに相当する．transfer 命令はいずれもデータの受け渡しのみに対応しており，それらを基点にしてスライスを計算しても，それぞれデータフローで接続された sink やsource からのスライスと同一の結果を返すことになるた
め，計測対象からは除外した．
本研究で用いる Thin Slice に関する表記を以下に定義する．また，以下の各集合 S の要素数を |S| と表記する．

Backward(v) ある sink v をスライシング基準とした
後ろ向き Thin Slice に含まれる頂点の集合．

Source(v) Backward(v) に含まれる source 頂点の集合．
F orward(w) ある source w をスライシング基準とした
前向き Thin Slice に含まれる頂点の集合．

Sink(w) F orward(w) に含まれる sink 頂点の集合．
図 5

図 1 のバイトコードのグラフ

Fig. 5 A graph of bytecode for the program in Fig. 1.

M ethod(Sts ) Thin Slice Sts の頂点が所属するメソッドの集合．

Class(Sts ) Thin Slice Sts の頂点が所属するクラスのド呼び出し命令から戻り値に関するデータ依存辺が存在しないものとして扱う．そのため，オペランド・スタック管
理命令から依存辺が引かれたり，これらの命令に依存辺が引かれたりすることはない．

集合．

LOC(Sts ) Thin Slice Sts のソースコード上での行番号の集合．

LOC(Sts ) は，クラスファイルの行番号情報を利用して計算する．仮パラメータ頂点はメソッドの宣言部（図 1 の4.5 バイトコードのグラフ

3，18 行目）に対応し，ソースコード 1 行分として計算す

図 5 は，図 1 のプログラムに対応するバイトコードのる．返り値頂点はメソッドの終了部（図 1 の 17，20 行目）

グラフである．楕円内の数字は図 4 のバイトコードのインに対応し，ソースコード 1 行分として計算する．実パラ

デクスに対応している．

メータ頂点と返り値を受け取る頂点は対応するバイトコー

5. 評価実験

ドの命令の行番号と同じであるとする．
例として図 5 において，main メソッドのインデクス 47

本実験では，Java プログラムのクラスファイルを解析の頂点をスライシング基準とした後ろ向き Thin Slice は

し，すべてのデータを基点とした Thin Slice を計測する．

Backward(47main ) = {(2，3，6，7，20，21，23，31，32，

Binkley らの実験と同様に，後ろ向き Thin Slice と前向き

41，42，46，47，a x，a y，res)main ，(2，3，4，5，f x，Thin Slice を計算し，各 RQ に対応した指標を計測する．

f y，ret)add } で，|Backward(47main )| = 23 となる．また，
Source(47main ) は Backward(47main ) に含まれる source

5.1 計測方法

で あ る 命 令 の 集 合 な の で ，Source(47main ) = {2main ，

本研究では，バイトコードの命令を，計算に使われるデー

6main ，4add } で，source 命令の数は |Source(47main )| =タを提供する source，データを使用する sink，データを伝3 と な る ．ス ラ イ ス に 含 ま れ る メ ソ ッ ド の 集 合 は

播する transfer に分類する．2 項演算である IADD のよう

M ethod(Backward(47main )) = {main，add} で，メソッな演算は，演算に使用する 2 つの数値に関するデータフ

ド数は |M ethod(Backward(47main ))| = 2 となる．スライ

ローの sink であり，計算結果を次の命令に提供する source

スに含まれるクラスの集合は Class(Backward(47main ))でもある．また，メソッド呼び出しは，実パラメータがそ= {M ain} で，|Class(Backward(47main ))| = 1 となる．

れぞれ sink であり，戻り値が次の計算のための source とな

LOC(Backward(47main )) = {6，7，10，12，14，15，18，

る．ローカル変数の代入，参照のように，データ自体を変

19，20} で，|LOC(Backward(47main ))| = 9 となる．

更しない命令は transfer に分類した．具体的な分類は表 1に示している．

RQ1 に つ い て 調 査 す る た め に ，す べ て の sink v について |Backward(v)| を，すべての source w について

本研究では，sink に対して後ろ向き Thin Slice を，source|F orward(w)| を計測し，これらの平均値を評価する．まに対して前向き Thin Slice を計算していく．これは様々

た，|LOC(Backward(v))| の平均値を計算し，バイトコーな演算やメソッド呼び出し文，条件式に登場する変数やドとソースコードのサイズを比較する．

フィールドの値を調査する後ろ向きスライスと，演算の結
果や変数の値がどこで使われているかを調査する前向きス

c 2014 Information Processing Society of Japan

RQ2 について調査するために，すべての sink v について次の指標を計測する．

976

情報処理学会論文誌

Vol.55 No.2 971–980 (Feb. 2014)

表 3

各指標の統計量

Table 3 Summary of metrics.
プログラム名tomcatluindexsunflow

avrora

pmd

xalan

batik

グラフの頂点数

54,468123,191

190,526

211,343448,722815,861

968,470-

36,06043,974

68,936

-

-

-

922

12,82034,51230,45840,78462,957

93,810

ソースコードの行数
最大値|Backward(v)||F orward(w)||LOC(Backward(v))|

最大値の割合（%）

1.7

10.5

15.3

14.4

9.1

7.7

9.7

平均値

55.2

3012.87739.26919.37108.612482.7

26159.3

平均値の割合（%）

0.10

2.5

4.2

3.3

1.6

1.5

2.7

最大値

3,673

14,326

22,737

27,592

52,339105,749

140,965

最大値の割合（%）

6.7

11.7

12.4

13.1

11.7

13.0

14.7

平均値

57.2

1434.07834.82386.06226.318481.928719.3

平均値の割合（%）

0.11

2.1

3.3

1.1

1.4

2.3

3.0
-

最大値

-

4678

7144

10602

-

-

最大値の割合（%）

-

13.0

16.2

15.4

-

-

-

平均値

-

1102.6

1933.22425.6---

平均値の割合（%）

-

3.1

4.4

3.5

-

-

-

最大値

193

1,342

1727

3,780

4,277

6,849

7,326

平均値

8.0

155.6

155.7

128.7

126.5

385.5

576.9

最大値

368

1,482

870

3,702

3,132

7,175

8,011

平均値

6.4

116.1

213.4

331.0

369.6

1267.11632.0|M ethod(Backward(v))||M ethod(F orward(w))||Class(Backward(v))||Class(F orward(w))||Source(v)||Sink(w)|

最大値

41

288

300

1,284

685

1,352

1,792

平均値

2.9

68.6

83.6

278.0

111.3

264.9

489.7

最大値

68

329

170

1,147

507

1,306

1,750

平均値

2.3

63.9

43.1

98.9

67.0

243.4

361.6

最大値

382

5,494

15,451

14,96418,90027,441

40,687平均値

25.3

1375.83575.93470.63076.65215.611183.8

最大値

1,610

444,1

8,108

11,68919,42541,42352,334

平均値

25.4

819.8

2202.11021.42264.27238.510662.3• |M ethod(Backward(v))|

表 2• |Class(Backward(v))|

Table 2 Subject programs.

• |Source(v)|

クラス数

メソッド数

グラフの頂点数

tomcat261

2,389

54,468-luindex

560

4,180

123,191

36,060sunflow

650

4,507

183,185

43,974

avrora

1,838

9,304

211,343

68,936• |Sink(w)|

pmd

2,369

16,439448,722-|Source(v)| の値が小さい場合は Thin Slicing を利用す

xalan

2,805

22,377815,861

-

batik

4,417

28,818968,470-

また，すべての source w について次の指標を計測する．

• |M ethod(F orward(w))|• |Class(F orward(w))|

プログラム名

実験対象のプログラム

行数

ることで，使用しているデータの生成元を少数に特定できる．同様に，|Sink(w)| の値が小さい場合は生成したデー

Windows 7（64 bit）上で JDK 1.6.0 45 を用いてビルドしタの使用先を少数に特定できる．

たものである．DaCapo benchmark には，Java 言語で書|M ethod(Backward(v))|，|Class(Backward(v))|，|M ethod(F orward(w))|，|Class(F orward(w))| についてかれた多数のアプリケーションが含まれている．本実験で対象としたプログラムの規模は表 2 のとおりである．ただは，これらの値が大きい場合，様々なメソッドやクラスにし，tomcat，pmd，xalan，batik については，一部のライ

またがった Thin Slice であることを意味するため，Thin

ブラリのソースコードが取得できなかったため，行数に関Slice によってメソッド呼び出しをたどってデータの生成元する調査は行っていない．これらについては，ダウンローや使用先を特定する作業の時間を減らすことが期待できる．

ドした jar ファイルを実験対象としている．また，表中の5.2 実験対象
実験対象のプログラムは DaCapo benchmark（9.12）*1 を*1

http://dacapobench.org/

c 2014 Information Processing Society of Japan

行数はコメント行，空行を除いたものである．

5.3 実験結果と考察
本実験で計測した各指標の最大値と平均値を表 3 に示

977

情報処理学会論文誌

Vol.55 No.2 971–980 (Feb. 2014)

す．後ろ向き Thin Slice と前向き Thin Slice の平均値は，小さいものと大きいものの 2 つに分かれており，すべての7 つのプログラムで平均して約 2.1%である．Binkley らのスライスのサイズが小さいわけではない．また，RQ2 につ

実験 [7] では，従来のスライスの平均値が約 30%であった

いて，表 4 に示したような約 10%のスライスが表すデータことから，Thin Slice の平均値は十分小さいことが分かる．

フローは，データ依存関係の調査において特に有効である

luindex，sunﬂow，avrora について，|LOC(Backward(v))|と考えられる．

は |Backward(v)| より平均して約 0.3 ポイント大きくなっている．また，これら 2 つの値の相関係数は 0.9996 となっ

6. まとめと今後の課題ており，ソースコードにおける Thin Slice のサイズも同様

本研究では，Thin Slice のサイズに関する統計的評価とに十分小さいことが予想される．図 6 は，横軸に sink v のして，Thin Slice のサイズ，データの生成元の数，Thin|Backward(v)| がプログラム全体に占める割合，縦軸に横Slice がまたがるメソッド数といった指標を計測した．そ

軸の各値以下であるスライスの割合を示した累積度数分布の結果，Thin Slice のサイズの平均値は十分小さいことを図である．この図から，全スライス中の約 60 から 80%の確認した．Ishio らは，単純なデータフローを可視化するだ

スライスは，そのサイズがプログラム全体の 0.1%以下であけでも開発者のプログラム理解が速くなることを示しておる一方で，残りの約 20 から 40%のスライスは各プログラ

り [26]，Thin Slicing の結果を開発者に提示することも有ムのスライスの最大値付近に分布している．Thin Slicing

効であると期待できる．

が特に有効である場合として，後ろ向き Thin Slice が複数

今後の課題として，Thin Slice の内容について詳細な調のメソッドにまたがり，かつデータの生成元が少ないスラ査を行うことが考えられる．本実験で約 20 から 40%のス

イスの数を表 4 に示す．これらの 10%程度のスライスに

ライスについて，そのサイズが大きくなってしまうことがついては，データフローを複数のメソッドにわたって追跡分かった．しかし，そのようなスライスがどのようなデーしていく作業を Thin Slicing によって置き換えられるた

タフローであるかは分かっていないため，スライスサイズ

め，特に Thin Slicing の効果が高いと考えられる．

が大きくなる原因を調査することが必要である．また，文以上の結果から RQ1 について，Thin Slice のサイズは

献 [8] において Thin Slicing の定性的な有効性は調査され平均的に十分小さいといえる．ただし，スライスは非常にているが，定量的な評価も必要である．さらに，鹿島らのツール [27] と組み合わせることで，メソッドの引数に与えられるデータの生成元を可視化し，データ依存関係の調査を支援することが考えられる．
謝辞 本研究は，日本学術振興会科学研究費補助金基盤
研究（S）（課題番号：25220003），若手研究（A）（課題番
号：23680001）の助成を得た．
参考文献
[1]

[2]
図 6

|Backward(v)| の累積度数分布

Fig. 6 Cumulative frequency distribution for |Backward(v)|.

[3]
表 4 |M ethod(Backward(v))| ≥ 2 であり，|Source(v)| が 3 以下であるスライスの割合（%）

Table 4 Ratio of slices whose |M ethod(Backward(v))| ≥ 2
and |Source(v)| ≤ 3.
|Source(v)|

1

2

3

合計

tomcat

2.9

3.6

3.9

10.3

luindex

3.0

4.5

3.6

11.0

sunflow

1.8

2.5

2.4

6.7

avrora

3.5

3.7

2.5

9.7

pmd

2.8

3.5

4.1

10.5

xalan

2.7

3.4

3.3

9.4

batik

2.5

3.5

2.7

8.7

c 2014 Information Processing Society of Japan


[4]

[5]

Corbi, T.A.: Program Understanding: Challenge for the
1990’s, IBM Systems Journal, Vol.28, No.2, pp.294–306(1989).
LaToza, T.D., Venolia, G. and DeLine, R.: Maintaining Mental Models: A Study of Developer Work Habits,
Proc. 28th ACM/IEEE International Conference on
Software Engineering, pp.492–501 (2006).
Mäder, P. and Egyed, A.: Assessing the Eﬀect of Requirements Traceability for Software Maintenance, Proc.
28th IEEE International Conference on Software Maintenance, pp.171–180 (2012).
Kuang, H., Mader, P., Hu, H., Ghabi, A., Huang, L.,
Jian, L. and Egyed, A.: Do Data Dependencies in Source
Code Complement Call Dependencies for Understanding Requirements Traceability?, Proc. 28th IEEE International Conference on Software Maintenance, pp.181–
190 (2012).
Wang, J., Peng, X., Xing, Z. and Zhao, W.: An Exploratory Study of Feature Location Process: Distinct
Phases, Recurring Patterns, and Elementary Actions,
Proc. 27th IEEE International Conference on Software
Maintenance, pp.213–222 (2011).

978情報処理学会論文誌

[6]

[7]

[8]

[9]

[10]

[11]

[12]
[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

Vol.55 No.2 971–980 (Feb. 2014)

Weiser, M.: Program Slicing, Proc. 5th International Conference on Software Engineering, pp.439–449(1981).
Binkley, D., Gold, N. and Harman, M.: An Empirical
Study of Static Program Slice Size, ACM Trans. Software Engineering and Methodology, Vol.16, No.2, pp.1–
32 (2007).
Sridharan, M., Fink, S.J. and Bodik, R.: Thin Slicing,
Proc. 2007 ACM SIGPLAN Conference on Programming Language Design and Implementation, pp.112–
122 (2007).
Jász, J., Árpád Beszédes, Gyimóthy, T. and Rajlich, V.:
Static Execute After/Before as a Replacement of Traditional Software Dependencies, Proc. 24th IEEE International Conference on Software Maintenance, pp.137–
146 (2008).
Horwitz, S., Reps, T. and Binkley, D.: Interprocedural Slicing Using Dependence Graphs, Proc. ACM
SIGPLAN 1988 Conference on Programming Language
Design and Implementation, pp.35–46 (1988).
LaToza, T.D. and Myers, B.A.: Developers Ask Reachability Questions, Proc. 32nd IEEE/ACM International Conference on Software Engineering - Volume
1, pp.185–194 (2010).
Zeller, A.: Why Programs Fail: A Guide to Systematic
Debugging, Morgan Kaufmann Publishers Inc. (2005).
Kusumoto, S., Nishimatsu, A., Nishie, K. and Inoue, K.:
Experimental Evaluation of Program Slicing for Fault
Localization, Empirical Software Engineering, Vol.7,
No.1, pp.49–76 (2002).
Anderson, P., Reps, T. and Teitelbaum, T.: Design and
Implementation of a Fine-Grained Software Inspection
Tool, IEEE Trans. Softw. Eng., Vol.29, No.8, pp.721–
733 (2003).
Jackson, D. and Rollins, E.J.: A New Model of Program
Dependences for Reverse Engineering, Proc. 2nd ACM
SIGSOFT Symposium on Foundations of Software Engineering, pp.2–10 (1994).
Reps, T. and Rosay, G.: Precise Interprocedural Chopping, Proc. 3rd ACM SIGSOFT Symposium on Foundations of Software Engineering, pp.41–52 (1995).
Krinke, J.: Visualization of Program Dependence andSlices, Proc. 20th IEEE International Conference on
Software Maintenance, pp.168–177 (2004).
Chen, K. and Rajlich, V.: Case Study of Feature Location Using Dependence Graph, Proc. 8th IEEE International Workshop on Program Comprehension, pp.241–
247 (2000).
Horwitz, S., Liblit, B. and Polishchuk, M.: Better Debugging via Output Tracing and Callstack-Sensitive Slicing, IEEE Trans. Softw. Eng., Vol.36, No.1, pp.7–19(2010).
Ceccato, M., Preda, M.D., Nagra, J., Collberg, C. andTonella, P.: Barrier Slicing for Remote Software Trusting, Proc. 7th IEEE International Working Conference
on Source Code Analysis and Manipulation, pp.27–36(2007).
Krinke, J.: Slicing, Chopping, and Path Conditions
with Barriers, Software Quality Journal, Vol.12, No.4,
pp.339–360 (2004).
Wang, X., Lo, D., Cheng, J., Zhang, L., Mei, H. and
Yu, J.X.: Matching Dependence-related Queries in the
System Dependence Graph, Proc. 25th IEEE/ACM International Conference on Automated Software Engineering, pp.457–466 (2010).

c 2014 Information Processing Society of Japan


[23]

[24]

[25]

[26]

[27]

Andersen, L.O.: Program Analysis and Specialization for
the C Programming Language, Ph.D. Thesis, Universityof Copenhagen (1994).
Milanova, A., Rountev, A. and Ryder, B.G.: Parameterized Object Sensitivity for Points-to Analysis for Java,ACM Trans. Software Engineering and Methodology,
Vol.14, No.1, pp.1–41 (2005).
Sundaresan, V., Hendren, L., Razaﬁmahefa, C., ValléeRai, R., Lam, P., Gagnon, E. and Godin, C.: Practical Virtual Method Call Resolution for Java, Proc.
15th ACM SIGPLAN Conference on Object-Oriented
Programming, Systems, Languages, and Applications,pp.264–280 (2000).
Ishio, T., Etsuda, S. and Inoue, K.: A Lightweight Visualization of Interprocedural Data-ﬂow Paths for Source
Code Reading, Proc. 20th IEEE International Conference on Program Comprehension, pp.37–46 (2012).
鹿島 悠，石尾 隆，井上克郎：エイリアス解析を用いたメソッドの入力データの利用法可視化ツール，ソフトウェ
アエンジニアリングシンポジウム 2012 論文集，pp.1–8(2012).

秦野 智臣
平成 25 年大阪大学基礎工学部情報科学科卒業．現在，同大学大学院情報科
学研究科博士前期課程 1 年．プログラ
ム解析に関する研究に従事．

鹿島 悠
平成 22 年大阪大学基礎工学部情報科学科卒業．平成 24 年同大学大学院情報科学研究科博士前期課程修了．同年
同大学院博士後期課程入学．プログラ
ム解析に関する研究に従事．

石尾 隆 （正会員）
平成 15 年大阪大学大学院基礎工学研
究科博士前期課程修了．平成 18 年同
大学院情報科学研究科博士後期課程修了．同年日本学術振興会特別研究員（PD）．同年ブリティッシュコロンビ
ア大学ポストドクトラルフェロー．平成 19 年大阪大学大学院情報科学研究科コンピュータサイ
エンス専攻助教．博士（情報科学）．データフロー解析，ア
スペクト指向プログラミングに関する研究に従事．日本ソフトウェア科学会，ACM，IEEE 各会員．

979

情報処理学会論文誌

Vol.55 No.2 971–980 (Feb. 2014)

井上 克郎 （フェロー）
昭和 54 年大阪大学基礎工学部情報工学科卒業．昭和 59 年同大学大学院博士課程修了．同年同大学基礎工学部情報工学科助手．昭和 59〜61 年ハワイ大学マノア校情報工学科助教授．平成元年大阪大学基礎工学部情報工学科講師．平成 3 年同学科助教授．平成 7 年同学科教授．平成14 年大阪大学情報科学研究科コンピュータサイエンス専攻
教授．平成 20 年国立情報学研究所客員教授．同年情報処理学会フェロー．同年電子情報通信学会フェロー．工学博
士．ソフトウェア工学の研究に従事．日本ソフトウェア科
学会，電子情報通信学会，IEEE，ACM 各会員．

c 2014 Information Processing Society of Japan

980