IEICE TRANS. INF. & SYST., VOL.Exx–??, NO.xx XXXX 200x

1

PAPER

Variable Data-Flow Graph for Lightweight Program Slicing and
Visualization
Yu KASHIMA†a) , Nonmember, Takashi ISHIO†b) , Member, Shogo ETSUDA† , Nonmember,and Katsuro INOUE†c) , Fellow

SUMMARY
To understand the behavior of a program, developers often need to read source code fragments in various modules. Systemdependence-graph-based (SDG) program slicing is a good candidate forsupporting the investigation of data-flow paths among modules, as SDG
is capable of showing the data-dependence of focused program elements.
However, this technique has two problems. First, constructing SDG requires heavyweight analysis, so SDG is not suitable for daily uses. Second, the results of SDG-based program slicing are difficult to visualize, as
they contain many vertices. In this research, we proposed variable dataflow graphs (VDFG) for use in program slicing techniques. In contrast to
SDG, VDFG is created by lightweight analysis because several approximations are used. Furthermore, we propose using the fractal value to visualize
VDFG-based program slice in order to reduce the graph complexity for visualization purposes. We performed three experiments that demonstrate theaccuracy of VDFG program slicing with fractal value, the size of a visualized program slice, and effectiveness of our tool for source code reading.
key words: Static Analysis, Program Slicing, Variable Data-Flow Graph,
Visualization

1.

Introduction

Many software developers spend much of their time investigating source code [1]. Program understanding can be difficult in part because a single functionality is typically implemented by a complex interaction of modules, e.g. methods
and classes in Java. To investigate an interaction of modules, developers often search code fragments related to theircurrent task, using explicit dependencies including controlflow and data-flow among modules [2].
System-dependence-graph (SDG)-based program slicing technique [3] helps developers investigate data-flow
paths. Program slicing on SDG extracts data and controldependences related to a particular program point. This is
typically sufficient information for developers to understandthe program. However, there are two problems with using SDG-based program slicing on a regular basis. First,
making SDGs requires heavyweight analyses, e.g. pointsto analysis and side effect analysis. Although a developer’s
typical working session time is between 30 minutes and twohours, making SDGs often consumes more than single session[4]. Second, existing research [5] shows that a straight
Manuscript received January 1, 2011.
Manuscript revised January 1, 2011.
†
Graduate School of Information Science and Technology, Osaka University, Yamadaoka, Suita-shi, Osaka, 565-0871, Japana) E-mail: y-kasima@ist.osaka-u.ac.jpb) E-mail: ishio@ist.osaka-u.ac.jpc) E-mail: inoue@ist.osaka-u.ac.jp
DOI: 10.1587/transinf.E0.D.1

graph visualization of program slices on an SDG for a typical program is too large and too complicated for a human tounderstand. Therefore, the authors in [5] proposed a visualization method based on text highlighting in a source code
editor. However, this visualization lost the direction, or edge
information, of the control and data dependencies.
In this paper, we propose variable data-flow graph(VDFG)-based program slicing technique as well as robust
methods for its visualization. VDFG represents approximated control and data-dependencies among formal parameters, actual arguments of method invocation, local variables, predicate and field accesses.
In order to create VDFGs using lightweight analysis,
VDFG is designed to flow-, object-, and context-insensitive.
Flow-insensitivity is caused by the fact that VDFG simply
connects data-dependence edges from all assignment statements of a variable to all reference statements of the same
variable. Object-insensitivity is caused by the fact that afield is represented by a vertex that is distinguished by thefield’s fully qualified name, but is not distinguished by areceiver object. Finally, context-insensitivity arises due tothe backward/forward traversal method of program slicing.
Owing to these insensitivities, constructing VDFG requires
abstract syntax trees or byte code, and class hierarchy information at minimum, but not intensive analyses such as
points-to analysis and side effect analysis.
We visualize a program slice on a VDFG in the formof graph. In order to reduce the complexity of the visualized
slice, we used the fractal value [6]. Fractal value, which corresponds to the weight of a vertex, is reduced in accordancewith the number of the siblings of the vertex. By filtering
vertices using fractal value, we can automatically prevent
visualization at vertices that have a large number of edges.
As a result, a human operator will be capable of reading
and comprehending the visualized graph. Naturally, edges
excluded from visualization may include important one forprogram comprehension. However, in our experience, thoseedges often include many infeasible paths because of insensitivities employed by VDFG. We designed that the edges
are visualized only when a human operator wants to investigate them.
The implementation of our visualizer for VDFG is aninteractive graph viewer integrated into Eclipse. When amouse button is clicked on a method name or a field namein a text editor, a program slice of the selected entity are
visualized in the graph viewer.

Copyright c 200x The Institute of Electronics, Information and Communication Engineers

IEICE TRANS. INF. & SYST., VOL.Exx–??, NO.xx XXXX 200x2

We performed three experiments to evaluate our proposed program slicing and graph-viewing techniques. The
first experiment compared our technique to Improved slicer[7], which is the state-of-the-art program slicing technique.
Although program slices from VDFGs without fractal values will include many imprecise results, many of the program slices with fractal value are precise. These results indicate that our lightweight technique is sufficiently precise forvisualization. The second experiment measured the size of aslice with fractal value. The results show that dozens of vertices are included in a slice from any applications, and thata slice includes the dependencies spanning several methods,
on average. The third experiment evaluated the effectivenessof our visualization tool for program understanding as wellas the performance of the tool. In this experiment, we assigned two program understanding tasks to 16 participants
using JEdit, a Java text editor. The results demonstrate thatparticipants using Eclipse enhanced with our visualization
tool were able to better investigate data-flow paths than theparticipants using Eclipse without our visualization tool.
This paper is an extended version of [8], and has beencombined two additional contributions:• Compare the precision of our proposed technique andstate of the art program slicing technique. The precision of the program slice using with VDFG and fractal
value was surplysingly high.
• Measure the size of the visualized program slice usingwith VDFG and filtering by fractal values. The numberof vertices in a slice is surpressed to dozens, besides
a slice may include a distant vertex from criterion ofprogram slice.
These contributions correspond to the first and the second
experiments, respectively.
The remainder of the paper is structured as follows. In
Section 2, we present related work. In Section 3, we describe the concept of VDFG, the VDFG-based program slicing techniques, and its visualization. The results of the threeexperiments are shown in Section 4, and we present conclusions and future research in Section 5.
2.

Related Work

2.1

Program Slicing

Program slicing [9] is a well-known technique used to extract program slices, or a set of program statements related
to slicing criteria selected by a developer. A program slice
is computed by backward traversal of an SDG, based on aparticular set of slicing criteria [3].
SDGs are directed graphs whose vertices represent thestatements of a program. Its directed edges represent dataand control dependencies. A data dependency is a relation
between an assignment and a reference of a variable. A data
dependency from statement s1 to statement s2 exists if allof the following conditions are satisfied:
1. s1 assigns a value to v

2. s2 refers to v
3. At least one execution path from s1 to s2 without redefining v exists.
The third condition depends on a control-flow graph of amethod containing s1 and s2.
A control dependency is a relation between a conditional statement and a control statement. A control dependency from statement s1 to statement s2 exists if:
1. s1 is a conditional predicate
2. s1 determines whether s2 is executed or not.
The definition of control dependency relations also depends
on a control-flow graph.
Program slicing can be effectively used to investigate
the detailed behavior of a program for debugging [10].
SDGs are also employed to support source code reading,e.g., to locate features in source code [11] and to search similar code fragments [12].
Although SDGs include sufficient data-flow information for developers, there are two remaining challenges toapplying program slicing to program understanding tasks.
First, making SDGs requires several heavyweight preliminary analyses such as a points-to analysis and side effectanalysis. In the present study, we use a flow, context andobject-insensitive analysis to make VDFGs that do not require heavyweight preliminary analyses.
Secondly, visualizing an SDG or a program slice for atypical program is difficult because of the large number ofvertices [5]. In the study of [5], Krinke has used the following two techniques:• Visualize control/data dependences in a program sliceby text highlighting in the source code editor, without
using graph representation. This drops edge directional
information, but enable to visualize a program slice
hiding a too large SDG.
• Employ distance-limited slicing technique for visualizing locality since user probably interests near instructions from the criteria than far away instructions. The
distance of instructions from the criteria is shown byhighlighting color. However, if a vertex near criterion may connects to a lot of vertices, the size of the
distance-limited slice may not be reduced significantly.
On the contrary, we have used a graph representation in order to visualize the directional information of edges in an
SDG. The issue of the explosion of the number of vertices
and edges has been addressed by fractal value. Fractal value[6] is a weight of a vertex decided as the fractal value of theparent vertex per the number of sibling vertices. Our approach filter out vertices which fractal values are smaller
than a threshold. As a result, even if a vertex near criterion
connects to many vertices, the size of the visualized slice
will be suppressed as much as readable size.
2.2

Lightweight Analysis

Our approach is an approximation of data dependence anal-

KASHIMA et al.: VARIABLE DATA-FLOW GRAPH FOR LIGHTWEIGHT PROGRAM SLICING AND VISUALIZATION

3

ysis. Previously, Jász [13] proposed an alternative approximation — Static Execute After/Before dependencies.
That approach is a control-flow-based approximation without data-flow analysis, while our approach performs approximated data and control flow analysis. The weak point ofJász’ approach is a handling loop that connects control paths
among all functions, e.g., a message loop in the GUI. Our
analysis can extract data dependencies in such applications.
Nguyen [14] has proposed a flow-insensitive data-flow
analysis for mining source code patterns. The analysis constructs a directed acyclic graph named groum whose nodes
represent method calls and field accesses in a Java method.
A data dependency edge between two nodes is generated if
the two nodes share at least one common variable. Notethat groum is an intra-procedural representation to extract acoding pattern in a method. On the contrary, our approachaims to visualize inter-procedural information, e.g. datadependencies among methods.
2.3

Software visualization for Program Comprehension

Our approach along with several tools is able to visualize
software for program comprehension, starting with the implementation detail. The relationships among source codefragments should be visualized so that developers can selectan appropriate source code location to investigate.
Code Bubbles [15] is a unified viewer for source codeand its related documents. The tool focuses on the user interface based on the bubble metaphor. The tool displays anumber of source code fragments and their method call relationships so that developers can track the progress of their
particular investigation. On the other hand, the tool does
not analyze the implementation details of each code fragment. To investigate data-flow paths, developers must therefore open and read source code fragments. Our researchvisualizes summarized dependencies in source code so thatdevelopers can efficiently choose source code fragments to
be investigated and ignore irrelevant source code fragments.
A visualization tool should reflect the structure ofsource code fragments. DA4Java [16] shows an overview
of Java source code as a nested graph. Vertices in the graphrepresent source code entities that correspond to packages,
classes, methods, and fields. Edges in the graph represent
class inheritance/subtyping, method calls and field accesses.
DA4Java represents a class as a node that contains vertices
representing methods as well as fields belonging to thatclass. We make use of nested visualization as a techniquefor graph visualization.
Whyline [17] is a debug support tool. This tool answers developer’s questions of debugging which are “why?”or “why not?” about program bug. For example, if a developer questions “Why this method was executed in the situations?”, Whyline displays the causality of the method invocation, such as conditions, data flows, and control flows.
Whyline uses both static analysis and dynamic analysis,
while our approach uses static analysis.

3.

VDFG-based Slicing Technique

3.1

VDFG

We have defined VDFG as a directed graph that represents
data dependencies and control dependencies in a Java program. VDFG is built from either source code or Java byte
code, and includes both variables and instructions as vertices. Variables are included because they are important toinvestigate data-flow paths. We have defined an approximated data dependence as follows.
• If a statement s1 assigns a value to v and another statement s2 refers to v, then s2 depends on s1 via v.
Compared with the definition of data dependence for program slicing described in Section 2.1, we have removed
the third condition. Similarly, in the case of making a
VDFG from source code, control dependence is approximated based on the syntax tree instead of control-flow
graphs as follows:• A statement is controlled by its enclosing control statement such as if and while.
In the case of making a VDFG from byte code, we
performed traditional control-dependence analysis because
syntax trees are lost in byte code. Although these approximations may generate infeasible dependencies, they will not
miss any traditional dependencies.
VDFG comprises three kinds of vertices and two kindsof edges, as follows.
A variable vertex corresponds to a variable or a literal.
Variables include local variables, formal parameters, actualarguments, instance field variables, class variables, and literals.
An operator vertex corresponds to an operator of an
expression. An operator vertex has one or more incoming
data-flow edges from vertices corresponding to operands. If
the resulting value of an operator is assigned to a variable
or used by another operator, the operator vertex has an outgoing data-flow edge. We treat method calls, field accessand array access as special operators whose operands, e.g. a
receiver object and parameters, are represented by variablevertices.
A control vertex corresponds to a control statement
such as if and while. A control vertex has an incoming dataflow edge representing the conditional expression and outgoing control edges to call-site vertices and operator vertices
controlled by the condition.
Data-dependence and control-dependence edges represent approximated data dependencies and control dependencies, as mentioned above.
A VDFG is constructed by the following steps:
1. Create a variable vertex for each variable declaration.
2. Translate each statement into vertices and edges.
The first step processes fields, local variables, and literals. All instance fields and class fields in the target program

IEICE TRANS. INF. & SYST., VOL.Exx–??, NO.xx XXXX 200x

4

are translated into variable vertices.
The second step is an intra-procedural process of making vertices and edges that represent each statement. First,
statements are parsed into vertices. Expressions are parsed
into variable vertices and operator vertices. if, for, andwhile statements are parsed into control vertices and vertices that represent predicates. Method call statements areparsed into variable vertices that represent actual arguments
and returned values. Field access instructions and array access instructions are treated as method calls. Each instruction has an actual-in vertex representing the receiver object.
Moreover, a field or array write instruction has an actualin vertex representing the assigned value. A field or array
read instruction has an actual-out vertex representing theread field or array element value. Each array instruction has
an additional actual-in vertex representing the index value.
After making vertices, data-dependence edges andcontrol-dependence edges are drawn according to the above
definitions. Additionally, a vertex of a field read/write instruction representing the field value is connected to the field
vertex by a data-dependence edge. A vertex representing anarray element is connected to other vertices representing array elements that have the same declaration type.
An inter-procedural data-dependence edge is drawn
to represent a parameter data-flow related to method
calls. Actual-in vertices to formal-in vertices and formalout vertices to actual-out vertices are connected by datadependence edges according to method calls. For virtual
method call resolution, we use Class Hierarchy Analysis(CHA) [18]. VDFG ignores unanalyzable library classes
for which source code is not available. A method call toa library class is not connected to the called method.
Our analysis does not support several aspects of Java
language as follows:• The statements in a catch block are simply translated
into a VDFG without a special rule. We ignored dataflow paths for an exception object from a method callor a throw statement to a catch block, although we
could represent such a data-flow in VDFG. Developers
who investigate exceptional control-flow can use another visualization tool such as Flow View specialized
for exception handling [19].
• We did not take multi-threaded execution into accountas regular control-flow paths. VDFG includes data dependencies between threads if the threads communicate by variables. A synchronized block is represented
as a control vertex that takes as input an expression andcontrols statements in the block.
Figure 1 shows an example of source code and its
VDFG. The code fragment in Figure 1a is a class C that hasa field f and methods max, setF, and foo. The method max
takes two parameters x and y and returns the larger of thetwo. The method setF takes one parameter i and assigns i
to field f. The method foo executes setF with argument 1,
max with argument f and 5, and then returns z, which is thevalue returned from a call to the max method.

1class C {2

int f;

3

static int max(int x, int y) {4

int result = y;5if (x > y)6result = x;7

return result; }8void setF(int i) { this.f = i; }9

int foo() {10

setF(1);

11

int z = max(this.f, 5);

12

return z; }13}(a) Source Code Example

x

max

foo

y

C.f

this.f $obj $val

x>y

setF

if

max
result=yresult=x5

this$A-in-0 $A-in-1zresultreturn result

this.f $obj $val

$A-out

setF

1

this

i

$A-in-0 $A-in-1$F-outreturn z$F-outData-dependence Edge

Variable Vertex

Control-dependence Edge

Operator Vertex

Control Vertex(b) Variable Data-Flow Graph

Fig. 1: Example of Source Code and Variable Data-Flow
Fraph

Figure 1b shows the VDFG for the example sourcecode. The area enclosed by the dashed line includes the
subgraph of the corresponding method.
In the VDFG, vertices x and y in max correspond to the
local variables “int x” and “int y”, respectively. The vertex “x > y” represents a comparison operator in line 5. The
vertex takes as inputs two edges from x and y, and provides
the resultant value to the following if statement. Assignment“result = x;” in line 6 is controlled by the enclosing ifstatement. Therefore, the “if” vertex has a control edge tooperator vertex “result = x”.
The method call instruction in line 11 is translated
to four vertices whose labels are “max”, “$A-in-0”,“$A-in-1”, and “$A-out” (the vertices are represented by amethod call including four areas). The vertex labeled max is
a pseudo-vertex representing the method call. $A-in-0 and$A-in-1 vertices represent the actual-in vertices. $A-out
represents the actual-out vertex. The actual vertices connect to their corresponding formal vertices, i.e., the vertices

KASHIMA et al.: VARIABLE DATA-FLOW GRAPH FOR LIGHTWEIGHT PROGRAM SLICING AND VISUALIZATION

5$A-in-0, $A-in-1 and $A-out are connected to vertices
x, y, and $F-out, respectively. These are formal-in andformal-out parameters of method max invoked by the call.
The field access instruction in line 8 is translated tothree vertices labeled “this.f”, “$obj” and “$val” in
setF. The vertex this.f is a pseudo-vertex representing the field access. The vertices $obj and $val represent
the receiver object and field value, respectively. The vertex$obj is connected to the vertex labeled “this”, which represents the variable this. The vertex $val is connected to thevertices labeled “i” and “C.f”. The vertex i represents the
local variable i. The vertex C.f represents the value of field
f of class C. The instruction in line 8 sets the value of f, sothat $val vertex connects to C.f. The C.f is connected to$val in foo because the field access instruction in line 11
uses the field value f.
3.2

Program Slicing and Visualization

Program slicing using a VDFG is performed by simple
backward/forward traversal from criterion designated by thedeveloper. To reduce the complexity of the visualized graphcorresponding to the program slice, we use fractal values.
A fractal value w(v) is a weight for a node v. The fractal
value for the root node vroot is defined as w(vroot ) = 1.0. In
our technique, vroot nodes correspond to criterion of a program slice. The fractal values of the other nodes are decided by the fractal value of a parent node and the numberof children of the parent node. A child of a vertex meansa vertex directly connected to the node by a traversal directional edge. If a vertex has multiple parent vertices, thefractal value of the vertex is decided to the maximum value.
The concrete definition in the case of backward traversal asfollows:
w(v) = max{ f (v p ) | {v → v p }}w(v p )f (v p ) =|{v | v → v p }|In the case of forward traversal, the directions of the arrows
are reversed.
Figure 2 shows the example of fractal value using with
the VDFG shown in Figure 1b. This figure shows the VDFG
of method max. The vroot is $F-out. The direction of a program slicing is backward. The fractal value of each vertex
is shown as digit in parentheses. The fractal values of thevertices of return result and result are 1.0, because
the path from vroot has no branch. In contrast, the values ofresult=x and result=y is 0.5, because both are childrenof result. Similarly, values of x and if are 0.25 sincethese are children of result=x. Note that fractal values ofx and y are 0.25 and 0.5 respectively, despite these vertices
are children of x > y. The reason why is that our fractal
value applies the maximum value if a vertex has multiple
parents.
For the purposes of program slicing, the fractal value
is used as a threshold, i.e., traversal in program slicing continues until visiting a vertex whose fractal value is less thanmax

x(0.25)

y(0.5)
x>y(0.25)
if(0.25)
result=y(0.5)

result=x(0.5)

result(1.0)
return result
(1.0)

vroot

$F-out(1.0)

Fig. 2: An example of fractal value for backward traversal
from vroot

a threshold value. As a result, the slices with fractal values
only include vertices whose fractal values are greater than
this threshold. Theoretically, if the threshold fractal value isdecreased, the size of the slices will increase.
An important feature of fractal value is that the fractal value of a node is the same as its parent if there are no
sibling nodes. A graph traversal continues through a variable if the value of the variable is determined by anothersingle variable, e.g., a parameter that is incoming from asingle caller. On the other hand, backward traversal stops
at methods called by a large number of other methods, e.g.,
setter/getter methods. Similarly, forward traversal stops atreturn values and fields used by a large number of methods.
In contrast to the distance limit [5], which limits a slice size
according to the distance from the criteria, fractal value suppresses the complexity even if a complicated portion exists
near the criteria.
The results of program slicing are visualized on thescreen using a graph viewer. In order to focus on the interprocedural dependences, visualized vertices include only
those that represent method calls, parameters, fields, local
variables, and predicates. Edges are visualized if dependence existed between the visualized vertices.
At points where the backward/forward traversal is
stopped because fractal value falls a certain threshold, a
pseudo-node labeled “more ...” is added to the visualizedgraph, so as to indicate that the program slice has been terminated at the node. Developers can start another graphtraversal from the method by selecting another method.
Our VDFG viewer is implemented as an Eclipse plugin. To help developers investigate source code, the VDFG
view interacts with a text editor; a mouse click on a methodname or a field name triggers program slicing according to
the following criterion:
Criterion for Method Declarations A mouse click on a

IEICE TRANS. INF. & SYST., VOL.Exx–??, NO.xx XXXX 200x6

method declaration provides backward program slicing criterion that include all parameters of the methods and referenced fields in the method. Moreover, themouse click also provides forward program slicing criterion that include the return value of the method andassigned fields in the method.
Criterion for Method Calls A mouse click on a method
call site provides forward program slicing criterion, including the actual parameters. Moreover, the click also
provides backward slicing criteria that include the returned value of the method call.
Criterion for Fields A mouse click on a field declaration
or a field reference provides forward/backward program slicing criteria that include a corresponding field
vertex.
Our visualization approach involves a hierarchicalview, similar to DA4Java [16]. A class is represented by arectangle that contains its methods and fields. Each method
involved in the subgraph is also represented as a rectangle including vertices representing the instructions of themethod. We have excluded the other methods and fields thatare not involved in the subgraph from the graph view because such methods and fields are irrelevant to the visualized
subgraph. We have used Graphviz [20] for graph layout.
The graph view provides hyperlinks to Java sourcecode so that developers can quickly confirm the implementation details of methods that have been omitted in the graphview. Developers can move to a method declaration, amethod call site, or a field declaration in a Java editor by
selecting a vertex in the graph view.
4.

Experimentthat we designed to answer these questions.
4.1

Experiment 1: Comparison with State-of-the-Art Program Slicing Techniques

In this experiment, we compared VDFG-based program
slicing for visualization and state-of-the-art program slicing. For the target comparison, we selected the Improved
Slicer (IMP), which is a context-sensitive, flow-sensitive,
and object-sensitive SDG-based program slicing technique[7]. Since VDFG-based program slicing uses conservative
approximations, a slice using VDFG may not be accurate
but includes any portion in a slice by IMP. Therefore, weestimated the accuracy of vertices and edges in a slice usinga criterion c as follows:
Accuracy(c) =|S V DFG (c) ∩ S I MP (c)||S V DFG (c)|where S V DFG (c), S I MP (c) refer to slice with VDFG to c, anda slice with IMP to c, respectively As IMP requires pointsto information, we used Spark [21] with Soot Framework[22]. In addition, we used the byte code analysis version of
our VDFG-based slicing tool in order to be consistent with
Spark and IMP both of which use byte code analysis.
As an SDG of IMP does not have corresponding vertices of a field vertex and a local variable vertex, we havedefined corresponding vertices as follows:• A vertex representing an instruction that accesses a
field corresponds to a field vertex that represents thesame field.
• A vertex representing an instruction that accesses a local variable corresponds to a local variable vertex that
represents the same local variable.

For evaluating our technique, we have defined the following
three research questions:

In addition, we defined the correctness of a vertex and edge
as follows:

RQ1: How accurate is VDFG-based program slicing using fractal values as compared to state-of-the-art
program slicing? The VDFG-based program slicing
technique has several insensitivities. Therefore, forgeneral use, it is important to know the accuracy of thevisualized program slices that result from our methods.
RQ2: Is a slice extracted with fractal values an effective
size for supporting investigation of control and data
dependencies? A program slice should not be so smallthat it cannot provide effective information to developers. Additionally, the slice should not be too large sothat it can actually provide understandable information
to developers. Furthermore, it is desirable that the slice
includes a portion that is distant from the developer’s
focused point i.e. criterion.
RQ3: Is our tool effective for development tasks? Our
proposed tool aims to support development tasks;
therefore, it is important to evaluate the effectivenessin practical usage.

• A vertex of a slice from VDFG is correct if a corresponding vertex exists in a slice from IMP.
• An edge v1 → v2 of a slice from VDFG is correct if
corresponding vertices for v1 and v2 exist in a slice from
IMP, and v2 is reachable from v1 in the slice from IMP.

The following subsections describe the three experiments

To evaluate the accuracy of a visualized slice, we compared VDFG-based slice visualization of target vertices andedges, as described in Section 3.2. Furthermore, to determine the accuracy of a VDFG-based program slice withvarious fractal values, we tested nine configurations. Eightof the configurations use different minimum fractal values,
ranging from 0.005 to 0.32. The ninth configuration does
not use fractal value.
The experimental target applications are taken from
Qualitas Corpus [23]. Table 1 shows the target applications and their sizes. The columns CHA and Points-to show
the number of reachable methods and instructions from amain method by CHA and Spark’s Points-to analysis, respectively. As performing program slicing requires criteria,
we used three different types of criterion, as described inKASHIMA et al.: VARIABLE DATA-FLOW GRAPH FOR LIGHTWEIGHT PROGRAM SLICING AND VISUALIZATION

7

Table 2: Accuracy of Vertices and Edges by VDFG with Fractal Value
TargetCobertura No limit
Cobertura 0.005
Cobertura 0.01
Cobertura 0.02
Cobertura 0.04
Cobertura 0.08
Cobertura 0.16
Cobertura 0.32
Emma No limit
Emma 0.005
Emma 0.01
Emma 0.02
Emma 0.04
Emma 0.08
Emma 0.16
Emma 0.32
Freecs No limit
Freecs 0.005
Freecs 0.01
Freecs 0.02
Freecs 0.04
Freecs 0.08
Freecs 0.16
Freecs 0.32

Accuracy (Vertices / Edges)
1st Qu.
Median3rd Qu.
0.819 / 0.668
0.994 / 0.902
1.000 / 1.000
1.000 / 0.924
1.000 / 1.000
1.000 / 1.000
1.000 / 0.958
1.000 / 1.000
1.000 / 1.000
1.000 / 1.000
1.000 / 1.000
1.000 / 1.000
1.000 / 1.000
1.000 / 1.000
1.000 / 1.000
1.000 / 1.000
1.000 / 1.000
1.000 / 1.000
1.000 / 1.000
1.000 / 1.000
1.000 / 1.000
1.000 / 1.000
1.000 / 1.000
1.000 / 1.000
0.154 / 0.098
0.406 / 0.311
1.000 / 1.000
0.686 / 0.625
1.000 / 0.933
1.000 / 1.000
0.742 / 0.680
1.000 / 0.950
1.000 / 1.000
0.808 / 0.741
1.000 / 1.000
1.000 / 1.000
0.867 / 0.814
1.000 / 1.000
1.000 / 1.000
1.000 / 0.904
1.000 / 1.000
1.000 / 1.000
1.000 / 1.000
1.000 / 1.000
1.000 / 1.000
1.000 / 1.000
1.000 / 1.000
1.000 / 1.000
0.089 / 0.059
0.688 / 0.475
0.991 / 0.960
0.450 / 0.400
0.971 / 0.936
1.000 / 1.000
0.500 / 0.451
0.980 / 0.963
1.000 / 1.000
0.529 / 0.500
1.000 / 1.000
1.000 / 1.000
0.571 / 0.532
1.000 / 1.000
1.000 / 1.000
0.611 / 0.583
1.000 / 1.000
1.000 / 1.000
0.667 / 0.667
1.000 / 1.000
1.000 / 1.000
0.750 / 0.714
1.000 / 1.000
1.000 / 1.000

Table 1: The Sizes of Target Applications
Cobertura
Emma
FreecsInforma
Jasml
SableCC

CHA#Method #Instructions
337
14,0681,234
39,227
1,327
57,324
485
16,368233
18,4191,949
54,373

Points-To#Method #Instructions
327
14,027
1,236
39,102
1,147
51,671458
15,586233
18,4191,898
54,143

Section 3.2. As some of the criteria for VDFG do not exactly correspond to IMPfs vertices, the criterion for IMP aredefined as follows:
Criterion for Method Declaration Backward slicing criterion include all parameters of the methods and fieldreference instructions in the method. Forward slicing
criterion include the return value of the method andfield assignment instructions in the method.
Criterion for Method Call Same as for VDFG (see Section 3.2).
Criterion for Field Given a field, backward/forward slicing criterion include all field access instructions accessed to the field.
Table 2 shows the distributions of the accuracies obtained with the various configurations. In particular, the table shows the first, second, and third quartile values. The
target columns show the target application as well as theconfiguration. Each cell contains the accuracies for vertices
and edges. Note that “No limit” in the target column corresponds to the configuration that does not use fractal value.
The results show that VDFG-based program slicing

TargetInforma No limit
Informa 0.005
Informa 0.01
Informa 0.02
Informa 0.04
Informa 0.08
Informa 0.16
Informa 0.32
Jasml No limit
Jasml 0.005
Jasml 0.01
Jasml 0.02
Jasml 0.04
Jasml 0.08
Jasml 0.16
Jasml 0.32
SableCC No limit
SableCC 0.005
SableCC 0.01
SableCC 0.02
SableCC 0.04
SableCC 0.08
SableCC 0.16
SableCC 0.32

Accuracy (Vertices / Edges)
1st Qu.
Median3rd Qu.
0.091 / 0.069
0.302 / 0.217
1.000 / 1.000
0.714 / 0.667
1.000 / 0.980
1.000 / 1.000
0.784 / 0.714
1.000 / 1.000
1.000 / 1.000
0.846 / 0.792
1.000 / 1.000
1.000 / 1.000
0.875 / 0.836
1.000 / 1.000
1.000 / 1.000
0.928 / 0.870
1.000 / 1.000
1.000 / 1.000
1.000 / 1.000
1.000 / 1.000
1.000 / 1.000
1.000 / 1.000
1.000 / 1.000
1.000 / 1.000
0.016 / 0.013
0.790 / 0.734
1.000 / 1.000
0.179 / 0.170
0.979 / 0.933
1.000 / 1.000
0.265 / 0.245
1.000 / 0.949
1.000 / 1.000
0.385 / 0.375
1.000 / 0.984
1.000 / 1.000
0.500 / 0.452
1.000 / 1.000
1.000 / 1.000
0.533 / 0.500
1.000 / 1.000
1.000 / 1.000
0.667 / 0.643
1.000 / 1.000
1.000 / 1.000
0.692 / 0.640
1.000 / 1.000
1.000 / 1.000
0.111 / 0.047
0.419 / 0.171
1.000 / 1.000
0.650 / 0.588
1.000 / 0.976
1.000 / 1.000
0.714 / 0.632
1.000 / 1.000
1.000 / 1.000
0.800 / 0.750
1.000 / 1.000
1.000 / 1.000
0.857 / 0.800
1.000 / 1.000
1.000 / 1.000
1.000 / 0.913
1.000 / 1.000
1.000 / 1.000
1.000 / 1.000
1.000 / 1.000
1.000 / 1.000
1.000 / 1.000
1.000 / 1.000
1.000 / 1.000

without fractal value leads to many inaccurate vertices andedges. For example, the median of vertex accuracy rates for“SableCC No limit” is 0.419; the median accuracy for edges
is only 0.170. With the exception of the results of Coberturaand Jasml, the median for edge accuracy was less than 0.50.
Unfortunately, this result indicates that using VDFG program slicing without fractal value yields highly inaccurate
results.
On the other hand, the accuracy of VDFG-based program slicing with fractal values is surprisingly high. For example, the median for vertex/edge accuracies of “SableCC
0.005” is 1.0, despite the fact that “SableCC Nolimit” resulted in a quite low accuracy. All of the vertex/edge accuracies with a minimum fractal value threshold of 0.005
were more than 0.9. The result shows two things: First, if
a vertex has many children, edges between the vertex andthe children really include infeasible paths because of insensitivities. Secondly, fractal value succeeds to stop visualization of imprecise vertices which are connected by suchinfeasible paths.
The results shown in Table 2 also indicate that if theminimum fractal value is configured to larger value, thenthe quartiles of accuracies are also higher values. Increasing the minimum fractal value means that the slice excludes
portions that are far from the criteria. Therefore, this result indicates that the portion of the program slice near thecriteria is accurate even if a graph including several known
insensitivities is used. If the minimum fractal value is 0.04
or more, all of the vertex/edge accuracy medians are 1.0.
These results show that VDFG’s program slicing with fractal values is accurate and the insensitivities of VDFG are

IEICE TRANS. INF. & SYST., VOL.Exx–??, NO.xx XXXX 200x8

Table 3: The Distribution of the number of Vertices and Max Distance in the Slice with Fractal Value
Cobertura 0.005
Cobertura 0.01
Cobertura 0.02
Cobertura 0.04
Cobertura 0.08
Cobertura 0.16
Cobertura 0.32
Emma 0.005
Emma 0.01
Emma 0.02
Emma 0.04
Emma 0.08
Emma 0.16
Emma 0.32
Freecs 0.005
Freecs 0.01
Freecs 0.02
Freecs 0.08
Freecs 0.16
Freecs 0.32

1st Qu.
3/1
3/1
3/1
3/1
3/1
3/1
3/1
4/3
4/3
4/2
4/2
4/1
4/1
3/1
4/1
4/1
4/1
4/1
4/1
4/1

#Vertices / Max DistanceMedian3rd Qu.
Max
11 / 633 / 12417 / 36
10 / 526 / 11256 / 30
9/5
21 / 10203 / 29
8/4
17 / 8172 / 25
7/4
14 / 7122 / 22
6/3
10 / 681 / 19
5/3
8/4
50 / 19
22 / 1047 / 15809 / 36
19 / 938 / 13497 / 31
16 / 830 / 11371 / 29
13 / 722 / 10280 / 27
11 / 6 16.25 / 8
196 / 23
8/4
12 / 6140 / 216/3
9/4
76 / 21
21 / 940 / 12 2,130 / 38
18 / 831 / 11 1,431 / 29
15 / 725 / 9950 / 29
10 / 514 / 7524 / 27
8/4
11 / 5424 / 276/3
8/4
277 / 24

therefore tolerable.
4.2

Experiment 2: Investigation of Slice Size

Experiment 1 showed that VDFG-based program slicing
with fractal values extracts accurate slices. However, if theslice is too small, it may not be helpful for program understanding because the slice will only visualize a narrow area.
To address RQ2, we measured slice size as well as whether
the distant portions are included in slices. To measure theformer, we simply counted the number of vertices in eachslice. To measure the latter, we measured the maximum distance of vertices from the criterion in a slice. The configurations and targets were the same as for Experiment 1.
Table 3 shows the distribution of the number of vertices as well as the max distances. Similar to Table 2, thetarget column displays both the target and the fractal value
configuration.
The results shown in Table 3 demonstrate that the number of vertices may be as high as hundreds or thousands;
however, in most cases, the number is several dozen. If theminimum fractal value is 0.005, the maximum median is24, which corresponds to the case of Informa. The results
show that fractal value prevents an explosion in the numberof vertices and leaves a number of vertices that is humanmanageable.
Regarding the distance from the criterion, the data in
Table 3 also indicate that the max distances typically range
from three to ten. If the minimum fractal value is set to0.005, the minimum median distance is six (in the caseof Cobertura). As the slice is focused on revealing interprocedural dependencies, the results suggest that a slice
shows dependencies among several methods, on average.
On the other hand, a slice may include several dozens of
distant vertices in some cases, e.g., the max value is 40 inInforma 0.005
Informa 0.01
Informa 0.02
Informa 0.04
Informa 0.08
Informa 0.16
Informa 0.32
Jasml 0.005
Jasml 0.01
Jasml 0.02
Jasml 0.04
Jasml 0.08
Jasml 0.16
Jasml 0.32
SableCC 0.005
SableCC 0.01
SableCC 0.02
SableCC 0.08
SableCC 0.16
SableCC 0.32

1st Qu.
4/2
4/2
4/2
4/2
4/2
4/1
3/1
4/1
4/1
4/1
4/1
4/1
4/1
4/1
4/1
4/1
4/1
4/1
4/1
3/1

#Vertices / Max DistanceMedian3rd Qu.
Max
24 / 956 / 13644 / 40
21 / 842 / 12380 / 40
17 / 733 / 10216 / 33
14 / 624 / 9148 / 27
10 / 517 / 790 / 26
8/4
12 / 669 / 26
6/3
9/4
56 / 23
16 / 836 / 11734 / 22
14 / 725 / 10576 / 19
13 / 719 / 9468 / 18
11 / 615 / 7329 / 18
8/4
13 / 6234 / 18
6/3
9/4
135 / 15
5/2
7/4
90 / 1414 / 734 / 12
1,058 / 25
12 / 626 / 10496 / 25
11 / 620 / 9364 / 25
8/4
13 / 7146 / 22
7/4
11 / 5131 / 19
5/3
8/4
88 / 16

the case of Informa 0.005. This indicates that the slice actually includes distant locations that are connected by simply
straight-dependence edges. Since these straight edges areeasy to understand for users, the slice supports the investigation of long-range dependence paths.
From an alternative point of view, Table 3 shows thestability of the slice size against the target program. If thefractal value is the same, the medians of the results do notvary greatly. We think that this property is suitable for visualization because a user does not confuse the variation of
the size of the visualized slices.
4.3

Experiment 3: Case Study of Source Code Reading

To evaluate the effectiveness of our visualization technique, we had 16 participants work on program understanding tasks. Out of these, 12 participants were graduate students studying software engineering. They were familiar
with Java, as they implemented tools for their research inJava. Four participants were software developers working
in a software company. They developed package softwareor enterprise applications written in Java.
We selected JEdit, an open source text editor, as thetarget program as no participants had knowledge of or experience with its source code. JEdit has a functionality thatgenerates a beep sound when JEdit cannot execute an action
specified by a user. Such a code fragment frequently appears
in JEdit. We asked the participants to identify conditions
in which the beep sound was generated and to explain how
the if statements are affected by the external environment,such as actions conducted by a user, the status of GUI components, and the status of a file system. The reason why wechose if statements is that understanding precise if conditions is important for debugging tasks [24].
Figure 3 shows two randomly selected source code lo-KASHIMA et al.: VARIABLE DATA-FLOW GRAPH FOR LIGHTWEIGHT PROGRAM SLICING AND VISUALIZATION

9

VFS
boolean load(View,Buffer,String)calledtrue

void

setReadOnly(

boolean)

Bufferint checkFileStatus(View)
calledJEditBuffer
4 node more ...

newReadOnly

void

setFileReadOnly(

boolean)void setReadOnly(boolean)

void finishSaving(View,String,String,String,boolean,boolean)

readOnly=

readOnlyOverride||

calledcalledfalse

void

setFileReadOnly(

boolean||=)void setPath(String)

readOnly

void setFileReadOnly(boolean)boolean isEditable()readOnlycalledboolean isReadOnly()
returncalledcalledcalledvoid

true

setFileReadOnly(

booleanbooleanisReadOnly

(

)

)

boolean checkFileForLoad(View,VFS,String)called2 node more ...

void

setFileReadOnly(

boolean)Fig. 4: A screen shot of a VDFG-based program slice for JEdit
public void actionPerformed (...) {...
if ( editor . getAbbrev () == null ||editor . getAbbrev (). length () == 0) {getToolkit ().beep (); // 153
return ;}...
}(a) TaskA: EditAbbrevDialog.java, Line 153
public void undo( TextArea textArea ){...
if (! isEditable ()){
textArea . getToolkit ().beep (); // 2038
return ;}...
}(b) TaskB: JEditBuffer.java, Line 2038

Fig. 3: Program Comprehension Task Targets

cations in JEdit 4.3pre11. In Task A, a beep sound is generated if a text input widget has no text that must be specified
by a user to execute the command. In Task B, a beep soundis generated if file editing is not permitted by the file system. To explain the conditions for Task A and Task B, 8 and
13 methods in JEdit must be investigated, respectively. We
asked the participants to write down their answers manuallyon paper.
We assigned two tasks to each participant; one task was
performed using Eclipse enhanced with the VDFG plug-in
and another task using the standard Eclipse 3.4, without ourplug-in. We compared the data-flow paths investigated byparticipants in a limited time slot. Note that the minimum
fractal value is set to 0.04 in this experiment. Additionally,
the VDFG tool is used in the source code analysis version
because the API of Eclipse supports accessing abstract syntax tree of the source code.
Figure 4 shows a visualized slice of JEdit, corresponding to a point at which a developer clicked on amethod call instruction isReadOnly() involved in theisEditable method. The highlighted (yellow) call site
in Figure 4 has an incoming data-flow edge from theisReadOnly method. The return value depends on the
readOnlyOverride and readOnly fields. The fields
are assigned by the setReadOnly and setFileReadOnly
methods. The setReadOnly method is called by the load
method of a file system class and the setFileReadOnly
method is called by 4 methods in a buffer class. Using thegraph, we can infer how the return value of the isReadOnly
method is determined without reading the actual sourcecode.
The time for each task was limited to 30 minutes. The
time does not include VDFG construction, as we aimed only
to determine the effectiveness of using the tool and not its
efficiency. We observed the activities of each participant using a video camera. The tasks were sequentially assigned.
For each participant, we had a 30-minute session in which
we explained the concept of VDFGs and gave a trial task sothat participants could learn our tool. After the introduction,
we assigned an experimental task. 30 minutes later, we in-

IEICE TRANS. INF. & SYST., VOL.Exx–??, NO.xx XXXX 200x10load
weight=0.25

saveweight=0.25

An argument of
setPerformingIO(boolean)(true)

A return value ofisPerformingIO()(true)

checkFileStatus()
weight=0.5

An argument of
setFileReadOnly(boolean)(true)

A return value ofisFileReadOnly()(true)

A return value of isEditable()(false)Fig. 5: An example of score computation. The graph is a
simplified version of the answer of Task B.
terrupted the investigation activity and assigned the secondtask.
To evaluate the correctness of an answer, we determined a correct answer for each task prior to the experiment.
The correct answers are defined as data-flow paths. For example, Figure 5 is a simplified version of the correct answer
for Task B. The graph has three data-flow paths from different methods: load, save, and checkFileStatus. We
have computed a Score for each answer using the following
function:X|path(v, m) ∩ A|
w(v)Score(A) =|path(v, m)|v∈VIn this function, A is a set of data-flow edges includedin the answer of a participant, V is a set of source vertices of data-flow paths in the correct answer, m is the target method where beep sound is generated, and w(v) is aweight value for each vertex determined by fractal values[6], as described in Section 3.2. If an answer included agray part of Figure 5, the answer included three of threeedges for load, two of three edges for save and one ofthree edges for checkFileStatus. The resulting score was
0.25 ∗ 33 + 0.25 ∗ 23 + 0.5 ∗ 31 = 0.583.
Table 4 shows the assigned tasks and resulting scoresfor each participant. The average score of participants working with VDFG was 0.79, while the average score of participants working with the standard Eclipse environment was
0.71. A Wilcoxon signed-rank test demonstrated that thedifference between the two groups was statistically significant (p=0.03). The visualization of the VDFG enabled participants to more completely discover and interpret the dataflow paths implicated in the task.
We observed that a visualized VDFG is frequently usedby participants. After the participants selected a method ora variable to obtain a VDFG, they repeatedly selected a return value vertex or a method parameter vertex in the graphto read source code. Without VDFG, participants had to
identify data-flow paths using a call graph view and several
search functionalities provided by Eclipse.
We additionally observed that participants used VDFG
to recognize where they investigated. When the value of avariable depended on two or more methods, participants had

Table 4: The resultant scores. “/VDFG” indicates that a
participant used VDFG for the task.
Participant

1st Task

2nd Task

P1 (Student)
P2 (Student)
P3 (Student)
P4 (Industry)
P5 (Student)
P6 (Student)
P7 (Student)
P8 (Industry)
P9 (Student)
P10 (Student)
P11 (Student)
P12 (Industry)
P13 (Student)
P14 (Student)
P15 (Student)
P16 (Industry)

A/VDFG
A/VDFG
A/VDFG
A/VDFG
A
A
A
A
B/VDFG
B/VDFG
B/VDFG
B/VDFG
B
B
B
B

B
B
B
B
B/VDFG
B/VDFG
B/VDFG
B/VDFGA
A
A
A
A/VDFG
A/VDFG
A/VDFG
A/VDFG

MeanMedianScorewith VDFG
w/o VDFG
0.857
1.000
1.000
0.857
0.875
0.708
0.621
0.760
0.733
0.858
0.817
0.590
0.714
0.857
1.000
0.429

0.781
0.723
0.621
0.652
0.857
0.429
0.571
1.000
0.714
1.000
0.714
0.429
0.590
0.723
0.908
0.671

0.792
0.836

0.711
0.714

to investigate one of data-flow paths and come back to thevariable. On the other hand, participants working without
VDFG had trouble identifying their previous source code
locations. Several participants lost their previous locations
and had to restart their investigation from the starting pointsof the tasks.
Although 13 of 16 participants performed better using VDFG, three participants (P8, P10, and P16) performed
better using Eclipse. P16 has the worst score for VDFG
because he did not write down several data-flow paths in
his answer, even though he appears to have actually investigated those paths. On the other hand, P8 and P10 answered
the correct data-flow using regular Eclipse. They were familiar with Eclipse; thus, they often clicked on a variablename to highlight the variable and quickly scrolled the editor using the mouse wheel to identify the data-flow paths
related to the variable. P8 and P10 also frequently used keyboard shortcuts to obtain method call and field access relationships. Although our VDFG visualized the same information they obtained, the behavior of these two participants
was much faster using the regular Eclipse without our plugin.
Participants appeared to not be disturbed by the precision of our data-flow analysis. As described in Section
3.1, VDFG may include infeasible edges because of the approximations of control and data dependencies. Indeed, an
infeasible path results from the following code fragment for
Task A:
dialog = new EditAbbrevDialog (... , abbrev , ...);
abbrev = dialog . getAbbrev ();Variable abbrev in the first line does not depend on
the second line. Our VDFG visualized a summary data-flowedge from the return value of getAbbrev to a parameterof the constructor call EditAbbrevDialog. However, participants read the source code in a few seconds and simply

KASHIMA et al.: VARIABLE DATA-FLOW GRAPH FOR LIGHTWEIGHT PROGRAM SLICING AND VISUALIZATION

11

ignored the infeasible edge.
Our data-flow analysis ignores library classes. For
example, a method call JTextField.setText has nodata-flow path to the return value of a method call
JTextField.getText. However, the participants nevercomplained about the lack of such data-flow paths. Instead,they have investigated data-flow paths of the JTextField
variable to find the caller methods of setText and
getText.
4.4

Threats to Validity

In the first experiment, we approximated the correspondence
relationships of a local variable vertex and a field vertex between VDFG and IMP. We believe that the approximation
is appropriate, but that the approximation may increase theaccuracy of vertices and edges.
In the second experiment, we measured the number ofvertices and distance from the instructions, and then evaluated the effectiveness of a slice for visualization. Unfortunately, the appropriate number of vertices and distance for
effective visualization is unknown. However, we showedthat the number of vertices is suppressed to only dozens
and a slice may include distant points. In addition, the casestudy showed that our visualized slices were effective for developers to achieve program understanding. Therefore, we
believe that our fractal value technique provides a humanmanageable but informative slice.
The targets of the first and second experiments included only six applications. However, these applications
were practically used and were not toy programs. Additionally, there was not a large difference in the results of eachapplication. Therefore, we believe that the results can begeneralized.
In the case study, the analysis target consisted of justone application and two tasks. The results of the case study
may be application-specific, i.e., VDFG is precise only inthe case of the tested application. However, in the otherexperiments, we used six applications for evaluation. The
results of the other experiments show that visualized subgraphs from VDFG are precise when compared to the stateof-the-art program slicing technique.
Another possible criticism of our case study was
whether it was appropriate or not. If the tasks were slightly
different from practical work, the result does not truly
demonstrate the effectiveness of VDFG in practice. However, the study of Latoza et al. [1] showed that developers
often face the question, “In what situations is this method
called?”, which is essentially equivalent to our tasks. Therefore, VDFG should be useful in practical work.
The other possible criticism was that we did not compare our technique and the visualization technique proposedby Krinke [5]. However, as mentioned in Section 2, thetraditional program slicing technique is too heavyweight tosupport daily tasks, which is the main goal of our proposed
technique. Therefore, we think that this does not matter tothe validity.

5.

Conclusion and Future Work

We proposed a VDFG-based program slicing technique andits visualization using fractal value. We performed three experiments. The first experiment demonstrated the accuracyof our slicing technique compared to a state-of-the-art program slicing technique. The second experiment showed thata slice obtained using our technique included a dozen vertices and a portion spanning from the criteria. The third experiment indicated that our proposed technique was indeed
helpful for source code understanding tasks. In addition, developers did not consider the inherent systems’ limitations
as a problem, as the developers knew that various featuresof Eclipse are also flow-insensitive, context-insensitive, andobject-insensitive.
Future work includes the comprehensive comparisonof our technique and other visualization tools, such as Whyline [17] and a tool proposed by Krinke [5]. In the comparison, we need to investigate the effectiveness of the tools
for not only data flow investigation task, but also the otherpractical program comprehension tasks, such as reachability
questions [1]. Another direction of the future work includes
applying our flow-insensitive data-flow analysis to approximate slice-based software metrics [25].
Acknowledgments
We thank Mr.Takeshi Murayama and developers of Hitachi Government & Public Corporation System Engineering, Ltd. for supporting our experiment. This work was
supported by JSPS KAKENHI Grant Number 26280021.
References[1] T.D. LaToza and B.A. Myers, “Developers ask reachability questions,” Proc. ICSE, pp.185–194, 2010.
[2] A.J. Ko, B.A. Myers, M.J. Coblenz, and H.H. Aung, “An exploratory
study of how developers seek, relate, and collect relevant information during software maintenance tasks,” IEEE Trans. Softw. Eng.,
vol.32, no.12, pp.971–987, Dec. 2006.
[3] S. Horwitz, T. Reps, and D. Binkley, “Interprocedural slicing using
dependence graphs,” Proc. PLDI, pp.35–46, 1988.
[4] Y. Kashima, T. Ishio, and K. Inoue, “Comparison of backward slicing techniques for java,” IEICE, vol.98, no.1, pp.–, Jan. 2015.
[5] J. Krinke, “Visualization of program dependence and slices,” Proc.
ICSM, pp.168–177, 2004.
[6] H. Koike, “Fractal views: A fractal-based method for controllinginformation display,” ACM Trans. Inf. Syst., vol.13, no.3, pp.305–
323, July 1995.
[7] C. Hammer and G. Snelting, “An improved slicer for java,” Proc.
PASTE, pp.17–22, 2004.
[8] T. Ishio, S. Etsuda, and K. Inoue, “A lightweight visualization of interprocedural data-flow paths for source code reading,” Proc. ICPC,
pp.37–46, June 2012.
[9] M. Weiser, “Program slicing,” Proc. ICSE, pp.439–449, 1981.
[10] S. Kusumoto, A. Nishimatsu, K. Nishie, and K. Inoue, “Experimental evaluation of program slicing for fault localization,” Empirical
Softw. Eng., vol.7, no.1, pp.49–76, March 2002.
[11] K. Chen and V. Rajlich, “Case study of feature location using dependence graph,” Proc. IWPC, pp.241–, 2000.

IEICE TRANS. INF. & SYST., VOL.Exx–??, NO.xx XXXX 200x12[12] X. Wang, D. Lo, J. Cheng, L. Zhang, H. Mei, and J.X. Yu, “Matchingdependence-related queries in the system dependence graph,” Proc.
ASE, pp.457–466, 2010.
[13] J. Jasz, A. Beszedes, T. Gyimothy, and V. Rajlich, “Static executeafter/before as a replacement of traditional software dependencies,”
Proc. ICSM, pp.137–146, Sept 2008.
[14] T.T. Nguyen, H.A. Nguyen, N.H. Pham, J.M. Al-Kofahi, and T.N.
Nguyen, “Graph-based mining of multiple object usage patterns,”
Proc. FSE, pp.383–392, 2009.
[15] A. Bragdon, S.P. Reiss, R. Zeleznik, S. Karumuri, W. Cheung, J. Kaplan, C. Coleman, F. Adeputra, and J.J. LaViola, Jr., “Code bubbles:
Rethinking the user interface paradigm of integrated development
environments,” Proc. ICSE, pp.455–464, 2010.
[16] M. Pinzger, K. Graefenhain, P. Knab, and H.C. Gall, “A tool for
visual understanding of source code dependencies,” Proc. ICPC,
pp.254–259, 2008.
[17] A.J. Ko and B.A. Myers, “Designing the whyline: A debugging interface for asking questions about program behavior,” Proc. CHI,
pp.151–158, 2004.
[18] J. Dean, D. Grove, and C. Chambers, “Optimization of objectoriented programs using static class hierarchy analysis,” Proc.
ECOOP, pp.77–101, 1995.
[19] H. Shah, C. Görg, and M.J. Harrold, “Visualization of exception
handling constructs to support program understanding,” Proc. SoftVis, pp.19–28, 2008.
[20] “Graphviz project.” http://www.graphviz.org/.
[21] O. Lhoták and L. Hendren, “Scaling java points-to analysis using
spark,” Proc. CC, pp.153–169, 2003.
[22] R. Vallée-Rai, P. Co, E. Gagnon, L. Hendren, P. Lam, and V. Sundaresan, “Soot - a java bytecode optimization framework,” Proc.
CASCON, pp.13–, IBM Press, 1999.
[23] E. Tempero, C. Anslow, J. Dietrich, T. Han, J. Li, M. Lumpe,
H. Melton, and J. Noble, “Qualitas corpus: A curated collection ofjava code for empirical studies,” Proc. APSEC, pp.336–345, Dec.
2010.
[24] K. Pan, S. Kim, and E.J. Whitehead, Jr., “Toward an understandingof bug fix patterns,” Empirical Softw. Eng., vol.14, no.3, pp.286–
315, June 2009.
[25] T.M. Meyers and D. Binkley, “An empirical study of slice-based cohesion and coupling metrics,” ACM Trans. Softw. Eng. Methodol.,vol.17, no.1, pp.2:1–2:27, Dec. 2007.