Call-Mark Slicing: An EÆcient and Economical Way of
Reducing Slice
Akira NishimatsuyMinoru JihirazGraduate School of Engineering Science,
Osaka University
1-3 Machikaneyama, Toyonaka,
Osaka 560-8531, Japan+81 6 6850 6571
fa-nisimt, kusumoto, inoueg@ics.es.osaka-u.ac.jpyABSTRACT

When we debug and maintain large software, it is very
important to localize the scope of our concern to small
program portions. Program slicing is one of promisingtechniques for identifying portions of interest. There aremany research results on the program slicing method. A
static slice, which is a collection of program statements
possibly a ecting a particular variable's value, limits thescope, but the resulting collections are often still large.
A dynamic slice, which is a collection of executed program statements a ecting a particular variable's value,
generally reduces the scope considerably, but its computation is expensive since the execution trace of the
program must be recorded.
In this paper, we propose a new slicing technique named
call-mark slicing that combines static analysis of aprogram's structure with lightweight dynamic analysis.
The data dependences and control dependences among
the program statements are statically analyzed beforehand, and procedure/function invocations (calls) arerecorded (marked) during execution. From this information, the dynamic dependences of the variables are
explored.
This call-mark slicing mechanism has been implemented, and the e ectiveness of the method has been
investigated.

Keywords

Static Slicing, Dynamic Slice, Dependence Analysis, Execution Overhead

1 INTRODUCTION

Debugging and maintaining large software is one of a

Shinji KusumotoyKatsuro Inouey

Graduate School of Information Science,
Nara Institute of Science and Technology
8916-5, Takayama, Ikoma,
Nara 630-0101, Japan+81 743 72 5236
minoru-j@itc.aist-nara.ac.jp

zcentral theme of software engineering research and practice.
Various ways of analyzing large programs and extracting
abstracted information of the target software have beenstudied[5, 11].
One approach to ease the diÆculty of handling large
software is to localize a developer's attention to speci cparts of the program that are directly and indirectly
related to the developer's concerns.
Program slicing is one promising technique to realize
this program localization[8, 17].
We have investigated the e ectiveness of program slicing
for program debugging and maintenance processes using
a controlled method[13]. The bug- nding time was measured and compared between two independent groups ofprogrammers, where one group of subjects used an ordinary debugging tool and the other used the debugging
tool with static slicing features. Each subject was given
a fault-injected program and an associated test data set
that e ectively detected the faults. The average bugnding times were 165 minutes without the slicing, and
122 minutes with the slicing. The e ectiveness of theslicing was con rmed statistically.
There are many research results on the program slicing method[7, 8]. Static slicing was rst proposed by
Weiser[17]. A static slice is a collection of program
statements possibly a ecting a variable's value at a particular program point. The variable of interest and theprogram point of interest are called the slicing criterion. Static slicing extracts portions from an original
program; however, the resulting portions are still large
in many cases. In extreme cases, there is no reduction
after taking a static slice. This is due to its analysis nature such that it must consider all possible input data
and all possible control ows.
Dynamic slicing was proposed by Agrawal et. al.[1, 2,
9, 10]. A dynamic slice is a collection of executed pro-gram statements actually a ecting a variable's value ata particular program point. Since the dynamic slicing isbased on an execution instance for the source programwith a speci c input data, non-executed parts of thesource program are automatically excluded, resulting ina slice that is generally smaller than a static one. However, computing a dynamic slice is costly, requiring signi cant memory and time resources because of dynamic
variable dependences that must be tracked during execution.
We have explored various slicing methods under the following policy.

 The static analysis information and lightweight dynamic information are combined.

 The reduction rate of slicing is greater than thestatic slice, and is hopefully close to the dynamic
slice.

 The execution overhead is minimized as much as

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

possible.

In this paper, we propose a new slicing technique named
call-mark slicing. Data dependences and control dependences among the program statements are statically analyzed beforehand, and procedure/function invocations(calls) are recorded (marked) during the program's execution. From this information, the dynamic dependenceof the variables are explored.
This call-mark slice mechanism has been implemented
as part of our Osaka Slicing System. Using this system,
we have executed various sample programs for the evaluation. The result shows that the call-mark slice limits
the scope better than the static slice. Also, there is little
burden of run-time information collection.
In Section 2, we will overview the static and dynamic
slicing methods. We propose the call-mark slicing
method in Section 3. Section 4 describes the implementation of the call-mark slicing method as part of ourslicing system, and also shows the results of using our
method on sample programs. In Section 5, we discuss
our approach compared to other method. We conclude
with some remarks in Section 6.

2 STATIC AND DYNAMIC SLICING
Static Slicing

Consider statements s1 and s2 in a source program p.
When all of the following conditions are satis ed, a control dependence, CD , from statement s1 to statement s2
exists: s1 is a conditional predicate, and the result of s1 determines whether s2 is executedor not.

program Square_Cube(input,output);var a,b,c,d : integer;function Square(x : integer):integer;
begin
Square := x*xend;function Cube(x : integer):integer;
begin
Cube := x*x*x
end;
begin
writeln("Squared Value ?");
readln(a);writeln("Cubed Value ?");
readln(b);writeln("Select Feature! Square:0 Cube: 1");
readln(c);if(c = 0) thend := Square(a)else
d := Cube(b);if (d < 0) thend := -1 * d;writeln(d)end.

Figure 1: Pascal Source ProgramThis relation is written by s1-s .
2

When the following conditions are all satis ed, a data
dependence, DD , from statement s1 to statement s2 by
a variable v exists:

 s1 de nes v, and s2 refers v, and at least one execution path from s1 to s2 without
re-de ning v exists.

-

This relation is denoted by s1 v s2 .
Program Dependence Graph (PDG) is a directed
graph whose edges denote dependences between statements, and whose nodes denote statements in a program
such as conditional predicates, assignment statements,and so on. For a Pascal source program shown in Figure
1 (which computes an absolute value of the squared or
cubed value selected by an input), we have a PDG presented in Figure 2. To handle function/procedure calls,
we employed additional nodes as discussed in Section 5.

Awith respect to a variable v on a statement s (this pair (v , s) is called the slice criterion) in a
program is a collection of statements corresponding to
the nodes which possibly reach v on s through the edges
in the PDG, using CD relations and DD relations in the
program. The static slice of variable d at line 24 as the
slice criterion for the program shown in Figure 1 is allstatements except for the message output statements(lines 12, 14, 16) as shown in Figure 3.
A Static SliceSquareMainwriteln("Sq ...

readln(a)x-paraax

writeln("Cu ...

readln(b)Square:=x*x
writeln("Sel...

readln(c)SquareSquare-exit

Squarecab

if c = 0

Cube
d:=Square(a)x-paraxdb
Cube:=x*x*x

d:=Cube(b)dCube
if d < 0

Cube

Cube-exit

d:= -1 * ddwriteln(d)DataDependenceControl
Dependence

Figure 2: Program Dependence Graph (PDG)

Dynamic Slicing

Consider an execution trace e of a source program p for
an input data d. si is a program statement appearing
in e and indicates a point during an execution of p withd.
A dynamic slice p with respect to si , d, and a variable
v is a syntactic correct subset of p, which computes
the same value of v for d at execution point si that
corresponds to si . A triple (d, si , v ) is also called aslice criterion of a dynamic slice.
00

A dynamic slice is computed rst by analyzing and storing the actual data/control dependences of variables inassociation with the program execution. Using this dependence chain, all statements in e, which a ect thevalue of v at si , are extracted. Then p , which generates the same execution trace as this extracted trace, isreconstructed.
0

Figure 4 shows a dynamic slice of the program shownin Figure 1. The slice criterion is input data (a = 2; b =3; c = 0), line 24 (of the last instance), and variable d.

Some Issues on Static and Dynamic Slicing

In static slicing, the analysis is performed without executing the program. The control dependences are fairly
easily obtained by parsing the source program. The
data dependences are computed by solving the dataow equations[3]. We devised an optimized algorithm
which analyzes dependences among the equations asmentioned in Section 4. The time complexity of this algorithm is generally square to the source program size,
where one of the factors grows very slowly to the program size[15]. Actually, we have constructed a slicing
system that performs the static slicing in a very short

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

program Square_Cube(input,output);var a,b,c,d : integer;function Square(x : integer):integer;
begin
Square := x*xend;function Cube(x : integer):integer;
begin
Cube := x*x*x
end;
begin
readln(a);readln(b);readln(c);if(c = 0) thend := Square(a)else
d := Cube(b);if (d < 0) thend := -1 * d;writeln(d)end.

Figure 3: Static Slicing Result by d at Line 24

amount of time[14] (this system has been extended to
our Osaka Slicing System discussed in Section 4).
The result of static slicing is a subset of the original
program. By supplying appropriate declarations, theobtained result is an executable program and it computes the value of the slice criterion correctly as theoriginal program does.
From the perspective of reducing the scope of concern
for the programmer, the static slicing method may not
be a helpful approach. This is because the slice result isoften a fairly large part of the original source programin many cases. This is generally due to large control
and data dependences in a PDG, which cover all possible program execution paths (and infeasible paths also).
This is a limitation of static analysis.
On the other hand, the dynamic slice is generally
smaller than the static one, since the dynamic slice iscomputed based on an execution trace for a speci c input data. Unrelated statements for that execution aredeleted from the slice result.
Also, computing a dynamic slice seems to be a wellsuited process for debugging, since the source of many
faults could be more easily found by executing programswith suitable test data and examining the faulty program outputs. These executions may be directly usedas the traces for dynamic slicing where the names ofthe variables with faulty output are used as the slice
criteria.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

program Square_Cube(input,output);var a,b,c,d : integer;function Square(x : integer):integer;
begin
Square := x*x
end;

begin
readln(a);readln(c);if(c = 0) thend := Square(a)program lengths. The data dependences and control
dependences in the execution trace may easily become
long chains. These long chains tend to contain repeateddependence structures that are caused by iterations in
the program. Thus, the traversal of dependences froma slice criteria can take a fairly long time1 . To resolve
this, we use static dependences, instead of the dynamic
ones, for computing a slice; this has the advantage thatthe static dependences are typically less numerous thanthe dynamics dependences.

Execution Dependence and CEDHere, we introduce execution dependence of two statements s1 and s2 .
Consider a case where s1 cannot be executed if s2 is not
executed. We say that s1 is executionally dependent ons2 .

Figure 4: Dynamic Slicing Result by d at Line 24 with
input (a = 2; b = 3; c = 0)

Finding all of the execution dependences in a program
would require dynamic information of the program behavior which is known to be very expensive to compute.
Thus, we choose a practical and safe approximation;
namely, we use a subset obtained by static analysis of
the program(with assumption of program termination).

For computing dynamic slice, pre-execution analysis is
not needed. However, during the execution, we have tokeep the dependences of data and control in the memory space or other area. This is a very large overhead
in memory space and computation time. Also, since thestored dependences are typically numerous, the collection and reconstruction of the slice after the execution
typically takes a long time.

If both s1 and s2 are contained in the same basic blockof the control ow graph[3], i.e., there is no outgoingor incoming path on the control ow between the twostatements, s1 is executionally dependent on s2 and viceversa. Also, if s2 is contained in a dominant basic blockof s1 's block, s1 is executionally dependent on s2 . The
control ow associated with the basic block structure
and the domination relation of the basic blocks are easily obtained by static analysis[3].

writeln(d)end.

3 CALL-MARK SLICING

The weakness of the static and dynamic slices discussed
above is resolved by combining static and dynamic information. We propose here a new method named callmark slicing.
The overhead of the dynamic slice is due to the following
two reasons.

 Recording the execution trace and constructing the
dynamic dependences of the statements

 Traversing the dynamic dependences and collecting
the slice result

For the rst issue, we abandon collecting a precise execution trace, instead gathering partial execution information. In call-mark slicing, we only record whether or
not each function/procedure call statement in the program is executed.
The second issue is based on the fact that the lengths of
execution traces are generally far longer than the source

Now we de ne a set of caller statements with execution
dependence, CED(s), as follow.

CED(s)

 ft j t is a function/procedure callstatement and s is executionallydependent on tg

The execution of s is dominated by the call statementsin CED(s). If we know that any call statement in
CED(s) is not performed during an execution, we canconclude that s is never executed.
Consider a small portion of a program such that,...
s1: callA ;s2: if a=1 then begins3:
b:= c ;
s4:
callB ;...
1 However, the result of the dynamic slice would be smaller
than the static one in general, since the repeated structures are
mapped to single statements in the result.

In this program, s1 is executionally dependent on s2,
and vice versa, and also s3 and s4 are executionallydependent on each other. In addition, s3 and s4 are
executionally dependent on s1 and also on s2. Thus
CED(s2) = fs1g and CED(s3) = fs1; s4g.

Computation of Call-Mark Sliceis de ned as a subset of a static sliceof the original program with respect to an execution eof the program and a slice criterion (sc , v ) where sc is astatement and v is a variable. Each statement s in thecall-mark slice is such that all of the call statements in
CED(s) are executed at least once in the execution e.
This means that statements appearing in the static slice
but not in the call-mark slice are not executed in e. The
execution of each statement is determined by the recordof activation of each call statement in the program.
A call-mark slice

In the following, a process of computing the call-markslice is described.

Step 1 Pre-execution Analysis
Similar to the computing a static slice, we construct
the PDG (Program Dependence Graph) by analyzing the data dependences and control dependencesamong the statements. Also, the execution dependences and CED(s) for each statement s are computed at the same time.

Step 2 Execution-time Marking
The target program is executed with an input
data set. Each time a call statement of a function/procedure is executed, that statement name(i.e., a pointer to the node in PDG) is marked as\executed". We refer to the set of marked callstatements as CM .

Step 3 Post-execution Collection
By performing the algorithm shown in Figure 5, thecall-mark slice is collected.
For the program shown in Figure 1, we have a static slice
for the slicing criterion of (line 24, d) as shown in Figure
3. Consider an execution of this program with input
data (a = 2; b = 3; c = 0). In this case, CM = f19g.
For line 19 of this program, CED(19) = f19g; thus
CED(19)  CM and line 19 is not deleted. For line
21, CED(21) = f21g; therefore CED(21) 6 CM andline 21 (and associated line 20) is deleted. Since line
21 is deleted, the statement de ning b at line 15 is alsodeleted. The resulting call-mark slice for that execution
and the same criterion, (line 24, d) is as shown in Figure
6.

Inputs
PDG: Program Dependence Graph
CM : Set of nodes which are executed callstatements(sc , v ): Slice criterion where sc is a node (astatement) and v is a variable nameTemporary

M; N : Sets of nodes
m; n: nodes
OutputM : Set of nodes of call-mark slice
Algorithm Body
1. M scsc g
2. N fn j n v sc g [fm j m
3. While N 6=  then execute the following
steps(a) choose a node n 2 N(b) N N n(c) if CED(n) 6 CM then goto (a)(d) M M [ n(e) N N [fm j m 62 M ^ (m w n _ m n)g
where w is any variable name.

-

-

-

-

Figure 5: Algorithm of Post-Execution Collection for
Call-Mark Slicing

4 IMPLEMENTATION OFSLICING
Overview of Slice System

CALL-MARK

In order to validate the call-mark slicing approach, wehave implemented the algorithm within our Osaka Slicing System[14].
The target language is a subset of Pascal, which isused in an undergraduate course of our department. It
contains essential control structures and recursive function/procedure invocations, allowing most introductory
programming.
Figure 7 shows the architecture. It contains static anddynamic slicers, as well as an executor and debugger.
The source program in Pascal is parsed into an abstracted source program that is stored in the system.
The user can view and modify the source program interactively using a visual editor.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

program Square_Cube(input,output);var a,b,c,d : integer;function Square(x : integer):integer;
begin
Square := x*x
end;

begin
readln(a);readln(c);if(c = 0) thend := Square(a)tion/procedure, the pointer to the return context is collected as CM . By doing so, we do not need to ndout all function/procedure calls in the program, but we
simply modify the entry part of each function/procedureslightly.
To handle inter-procedural dependences including recursive functions/procedures, we have introduced auxiliary types of nodes in a PDG. Table 1 shows thesenodes, which do not directly correspond to source program statements as other nodes. Using these nodes,
the data dependences are examined inter-procedurally.
In the case of self/mutual recursive structures of function/procedure calls, the dependences become cyclic.
This cyclic dependence is eÆciently solved by analyzing the structure of the dependences, and a suitable
solution is found[15].

if (d < 0) thend := -1 * d;writeln(d)end.

Dynamic
Dependence
Graph/
Trace Info.

Figure 6: Call-Mark Slicing Result by d at Line 24 with
input (a = 2; b = 3; c = 0)

Executor/
Debugger

Figure 8 shows the user interface of the system. The
left window displays the target source program. The
statement of the slice criteria is shaded darkly, and thestatements in the slice result are shaded lightly. We
can also edit the source program on this window. The
right upper window gives system status such as loaded
le name, program size, slice size and so on. The rightlower window works for the standard input and output
during the execution of the target program.
The source program is analyzed and transformed into a
PDG by a user request. A static slice may be computedfrom the PDG by specifying a slice criterion.
Both the whole source program and a computed static
slice can be executed by the executor. The debugger associated with the executor contains features of ordinary
runtime debuggers such as tracing, setting breakpoints,
viewing and modifying variable values, and so on. The
dynamic variable dependences are recorded during execution; a dynamic slice can be computed using thisinformation.
The total size of the system is about 19,000 lines of C
code including the call-mark slicing part.
The implementation of the call-mark slicing is basedon the method presented in previous section. For Step2, we need only one bit of information for each function/procedure call statement in the program. Thisbit is not necessarily marked at the caller context, butrather at the callee context. At the entry of each func-

Call Mark
Flags

Dynamic
Slicer

Programmer

Abstracted
SourceProgramInteractive
Viewer/Editor

Call-Mark
SlicerStaticSlicerStaticDependence
Analyzer
Program
Dependence
Graph/
CED

Figure 7: Architecture of Osaka Slicing System

Execution of Sample Programs

Using this experimental system, we have executed various programs and obtained several metrics values. Table 2 shows the statistics of three sample programs.
These values can vary with di erent slice criteria andinput data. In these cases, we have chosen the criteria and inputs for a typical debugging situation. (Thecriteria are mostly program output variables, and theoutput statements are placed at the end part of program execution.)
Program P 1 is a calender calculation program and thesize is 88 lines. P 2 is an inventory management programfor a whole seller, and it is 387 lines long. P 3 is also an
extended version of the inventory management programFigure 8: Snapshot of Osaka Slicing System
of P 2, and is 941 lines long. These programs include no
pointer variables.

We discuss these tables in detail in the next section.

Table 3 shows the time needed for the analysis before
the execution. In the case of static slicing, the value isthe time to construct a PDG. The time for computing
both the PDG and the CED is counted for in the callmark slicing. In the case of dynamic slicing, the analysis
is not necessary.

Table 2: Size of Various Slicing Results (lines of code)

In Table 4, the execution time is shown. In the case ofstatic slicing, the original program is executed; thus thisvalue means the execution time of the original program.
The execution for the dynamic slicing is performed in association with the construction of dynamic dependencesof variables. Therefore, the execution time contains thetime for this construction. In the case of call-mark slicing, the execution time to mark callers is included.
Table 5 shows the time needed for collecting statements
to be included in the resulting slices. In the case ofstatic slicing, this would be done before execution. For
dynamic slicing, the time for traversing the dynamic
dependences is counted. For call-mark slicing, this is
the time for Step 3.

program
P 1 (88 lines)
P 2 (387 lines)
P 3 (941 lines)

static27
175324

dynamic
14
139
50

call-mark
22
156
166

5 DISCUSSIONInterpretation of Program Execution Data Slice Size

As shown in Table 2, the result of the call-markslice is between the static and dynamic slices. It isalways smaller and better than the static slice andbigger and worse than the dynamic slice.

 Pre-Execution Analysis:

As shown in Table 3, call-mark slicing needs a little
extra time compared to the static slicing. This isnatural since we have to construct a PDG as inTable 1: Auxiliary nodes
Auxiliary Nodes
node to propagate the in uence through the return value of a function, every
procedure has its own exit node.
node to propagate the in uence of global variables from the outside of a procedure to the inside of it, every procedure has in-nodes of each global variables.
node to propagate the in uence of global variables from the inside of a procedure to the outside of it, every procedure has out-nodes of each global variables.
node to propagate the in uence through the parameters of a procedure, every
procedure has its own parameter-nodes corresponding to its parameters.

exit-node
in-nodeout-nodeparameter-node

Table 3: Pre-Execution Analysis Time (ms by PentiumII 300MHz with 256MB Memory)
program
P1
P2
P3

static
22
1,275
5,652

dynamic
N/A
N/A
N/A

call-mark
23
1,362
8,670

Table 4: 4 Execution Time (ms by Pentium-II 300MHz
with 256MB Memory)
program
P1
P2
P3

static38
48
4,046

dynamic
87
903
31,635call-mark
47
53
4,104

Notationf {exitfg {infg {out
fp {parfacility. On the other hand, the call-mark slicing
can be executed with very little overhead increase
compared to the execution of the static slicing (i.e.,
the execution of the original source program). It
shows that the marking of the caller names during execution is a lightweight task, requiring little
execution time.

 Slice Collection TimeAs shown in Table 5, dynamic slicing requires along time to collect the slice result. The time forcollecting a call-mark slice is almost the same as
the time to collect a static slice. Furthermore, inP 3, it is better than the static one. This is because
call-mark slicing removes parts of the PDG so thatthe searching space within the PDG is smaller thanthat for static slicing.

Relation to Other Methods
static slicing, and additionally we have to analyze
the execution dependences.

 Execution TimeThe execution time shown in Table 4 indicates thatthe overhead of the dynamic slicing is very big. For
P 3, it is almost 32 seconds where about 200,000
lines of code are executed with maximum 90 M
bytes memory use. If the program execution becomes longer by say, repeated execution of loops,
this overhead would cause serious decline of performance so that the programmer can hardly use thisTable 5: Slice Collection Time (ms by Pentium-II
300MHz with 256MB Memory)
program
P1
P2
P3

static1
5
93

dynamic
199
2,863
1,182

call-mark1
880

As discussed above, the call-mark slicing is a very
promising approach to provide eÆcient and practical
tools to localize a programmer's attention.
The pre-execution analysis, execution, and slice collection times are almost the same as those for static slicing, and the e ect of the slicing is much better than thestatic one. It seems that this approach provides a goodcompromise between e ectiveness and overhead.
Others have worked on combining static and dynamic
information for slicing[4, 6].
Hybrid slicing[6] targets a very similar goal as ours. It
reduces the static slice by using two types of dynamic
information: breakpoint information and call history
information. The former is supplied by the programmer and that information is used to infer the executed
control ow. The latter is used to compute portionsof dynamic slices for the periods between every function/procedure call and return. The result is closer tothe dynamic slice than our approach since it gathers
more dynamic information. The weakness of the hybrid
slicing would be that we have to specify appropriate

breakpoints to get a better slice. On the other hand,
our approach performs everything automatically except
for giving the input data and slice criterion. Also, thehybrid slicing requires a fairly large amount of memory space for recording the call history. The space required is roughly proportional to the program execution
length. Our approach, however, needs only the memory for the call marks, which is of a pre-determined
size and is roughly proportional to the program text
size. The di erence is signi cant if the program execution becomes long. In [6], the idea of the hybrid slicing
was proposed, although no implementation nor execution data was presented.
In [4], a method to extract various slice algorithms fromsemantic speci cations is presented. They propose aconstrained slice, which is a generalization of static anddynamic slices, and which takes a subset of the inputsof the program as symbolic program execution. Using
this input constraint, the program is rewritten and dependences are computed. Their approach contains very
important notions of generalization of static and dynamic slicing, and also it covers the partial evaluationand program simpli cation methods. However, it is notknown whether such a generalized approach may be implemented eÆciently and whether it is useful practically.
In terms of building analysis systems, several interesting
approaches have been proposed[12, 16]. A generalized
environment for developing analysis algorithm is proposed in [16]. It uses denotational frameworks to specify analysis algorithms; however, practicability of thegenerated algorithms for analysis tools is not known.
In [12], a more practical environment for understanding Cobol programs is presented, where various slicing
and program localization features are uni ed. Our aim
is to construct an eÆcient and e ective environment
for structured languages with functions and procedures
calls.

Application Domain and Limitation of CallMark Slice

Our main target of this slicing method is a debugging
environment as discussed in previous sections. Dynamic
information is considered to be essential for eÆcient
fault detection. A call-mark slice can be directly associated with a speci c test data which exposes faults
in the source program, although static slice would generally include various portions which do not relate to
the execution with the test data.
Programs which consist of independent function/procedure components may also be eÆciently debugged
with our approach. In such cases, there would bemany function/procedure invocation statements, andalso many function/procedure de nitions. Activationof selected functions/procedures using a speci c input

data will clearly reduce the slice size.
On the other hand, if the target programs contain asmall number of function/procedure invocation statements or the function/procedures are tightly interleaved, the e ect of our approach is limited.

Relation to Program Pro le Information

Our approach, call-mark slicing, uses information ofwhether or not each function/procedure call statementin the program is executed.
The precision of our slices can be improved if we takesuch information of all statements in the program. Thisapproach can be implemented using a similar method tocomputing pro ling and program coverage information.
For each statement, we employ one bit ag of whether
it is executed or not. The mechanism would be simple;
however, it requires more run-time overhead and signi cant modi cation of the executable program. The
call-mark slicing information can be obtained by minor
modi cation of the function/procedure entry routine tocollect caller statements.
We could also take a simpler approach than the callmark slice. We could only gather information about
whether or not each function/procedure is activatedwithout recording which call statement actually activated it. This approach reduces run-time overhead forcollecting caller statements; however it would increase
the result slice size.

6 CONCLUSIONS

Localizing a programmer's attention to a small portionof software is very important for improving the eÆciency
of program debugging and maintenance. Traditional
program slicing methods do not provide adequate tradeo s of e ectiveness and eÆciency.
We have proposed an eÆcient and e ective slicing
method, call-mark slicing. This method uses lightweight
run-time execution, and has a similar overhead with respect to static analysis as static slicing. The resulting
slices are smaller than corresponding static ones, butlarger than corresponding dynamic ones.
We have implemented this slice algorithm. Also wehave executed sample programs, and con rmed our approach.
We are planning to extend our approach to reduce static
analysis overhead, using call-mark information. The
pre-execution analysis for the call-mark slicing may bedone after the execution and before the slice collection.
Using the call-mark information, unnecessary dependence analysis would be deleted, and total analysis time
could be improved.
Also, empirical evaluation of the call-mark slicing will
be made. We have performed an experiment to evalu-

ated the e ectiveness of static slicing. We plan to similarly explore the e ectiveness of call-mark slicing using
controlled experiments.

[10] Korel, B., and Laski, J. : \Dynamic Slicing ofComputer Programs", Journal of Systems Software, Vol.13, pp. 187{195 (1990).

ACKNOWLEDGEMENTS[11] Murphy, G. C., and Notkin, D.: \Lightweight Lexical Source Model Extraction", ACM Transactions
on Software Engineering and Methodology, Vol. 5,
No. 3, pp. 262{292, July (1996).

The authors are very grateful to the reviewers for many
helpful comments.
This work is partly supported by Ministry of Education, Science, Sports, and Culture, grant-in-aid for priority areas \Principles for Constructing Evolutionary
Software", #10139223.

REFERENCES[12] Ning, J. Q., Engberts, A., Kozaczynski, W. V. :\Automated Support for Legacy Code Understanding", Communications of the ACM, Vol. 37, No. 5,
pp.50{57, May (1994).

[1] Agrawal, H., and Horgan, J.: \Dynamic Program
Slicing", SIGPLAN Notices, Vol.25, No.6, pp. 246{
256 (1990).

[13] Nishimatsu, A., Kusumoto, S., Inoue, K. : \An Experimental Evaluation of Program Slicing on Fault
Localization Process", Technical Report of IEICE
Japan, SS98{3, pp. 17{24, (1998)(in Japanese).

[2] Agrawal, H., Demillo, R. A., and Spa ord, E. H. :\Debugging with Dynamic Slicing and Backtracking", Software Practice and Experience, Vol. 23,
No. 6, pp. 589{616 (1993).

[14] Sato, S., Iida, H., and Inoue, K. : \Software Debug
Supporting Tool Based on Program Dependence
Analysis", Transaction on IPSJ, Vol. 37, No. 4, pp.
536{545 (1996) (in Japanese).

[3] Aho, A. V., Sethi, R., and Ullman, J. D.: \Compilers: Principles, Techniques, and Tools", Addison
Wesley, Massachusetts, 1986.

[15] Ueda, R., Inoue, K., and Iida, H. : \A PracticalSlice Algorithm for Recursive Programs", Proceed-[4] Field, J., and Ramalingam, G.: \Parametric Program Slicing", Proc. of 22nd ACM Symposium on
Principles of Programming Languages, pp. 379{
392, San Francisco, USA, January (1995).
[5] Atkinson, D. C. and Griswold, W. G. : \The
Design of Whole-Program Analysis Tools", Proceedings of the 18th International Conference on
Software Engineering

March (1996).

, pp. 16{27, Berlin, Germany,[6] Guputa,R., and So a, M. L. : \Hybrid Slicing: An
Approach for Re ning Static Slices Using Dynamic
Information", Proceedings of the 3rd International
Symposium on the Foundation of Software Engi-, pp. 29{40, October (1995).

neering[7] Harrold, M. J., and Ci, N. : \Reuse-Driven Interprocedural Slicing", Proceedings of the 20th International Conference on Software Engineering , pp.
74{83, Kyoto, Japan, April (1998).
[8] Horwitz, S. and Reps, T.:\The Use of Program Dependence Graphs in Software Engineering", Proceedings of the 14th International Conference on
Software Engineering, pp. 392{411(1992).
[9] Korel, B., and Laski, J. : \Dynamic Program
Slicing", Information Processing Letters, Vol.29,
No,10, pp. 155{163 (1988).

ings of the International Symposium on Software, pp. 96{106,Engineering for the Next Generation

Nagoya, Japan, February (1996).

[16] Vengatesh, G. A., and Fischer, C. N. : \SPARE:
A Development Environment for Program Analysis
Algorithms", IEEE Trans. on Software Engineering, Vol. 18, No. 4, pp.304{315, April (1992).
[17] Weiser, M.: \Program Slicing", Proceedings of theFifth International Conference on Software Engineering, pp. 439{449 (1981).