E ective Testing and Debugging Methods and Its Supporting System with
Program Deltas
Makoto Matsushitayzmatusita@ics.es.osaka-u.ac.jpy

Masayoshi Teraguchi

Katsuro Inoueteraguti@jp.ibm.com

inoue@ics.es.osaka-u.ac.jp

yDept. of Information and Computer ScienceszTokyo Research Laboratory

Faculty of Engineering Science

IBM Japan, Ltd.

Osaka University

1623-14 Shimotsuruma, Yamato

1-3 Machikaneyama, Toyonaka

Kanagawa, 242-8502 Japan

Osaka 560 JAPAN

Information Technology Center

Nara Institute of Science and Technology
8916-5 Takayama, Ikoma
Nara 630-01 JAPAN

Abstract
In the maintenance phase of software development, it
should be checked that all features are performed correctly after some changes are applied to existing software. However, it is not easy to debug the software
when a defect is found to the features which is notchanged during the changes, although using a regression test. Existing approaches employs the program
deltas to specify defects; they have hard limitation ofenacting them, don't support an actual debugging activities. Moreover, its system is hard to introduce anactual environment.
In this paper, we propose a new debugging method
DMET to solve such problems. DMET supports debugging activities when a defect is found by regression
tests through detection, indication, and re ection procedures. We also implement a debugging supporting
system DSUS based on DMET. DSUS executes DMET
procedures automatically, and easy to con gure for existing environment.
Through the experimentation of DMET and DSUS,
we con rm that DMET/DSUS reduce debugging timeof software signi cantly. As a result, DMET/DSUS
help evolving the software for the aspect of software
maintenance.

1

Introduction

In the maintenance phase of software development,
many changes are applied to existing software. How-ever, Hetzel shows that it is 50 to 80 percent of probability of adding some defects when some changes areapplied to the software[4]; testing should be needed to
not only changed features of software but also the unchanged features. Since recent software development
environment tends to be more complicated, software
maintenancability is important issue for maintaining
software e ectively and future evolution of the software.
Regression test[2, 8, 9, 13] is commonly used in orderto check that the features of software is implemented as
speci cation. Actual software development and maintenance activity employ version control system thatrecognizes, organizes, and manages software products(source codes and accompanying documents), in order
to raise the maintainability of software. Under thesedevelopment environments, regression test checks thelatest version of software. If a defect is found during
the regression test, the error that causes a defect will be
speci ed and it will be corrected. However, when thedefect that is not changed by the code changes causes
a defect, it is not easy to specify the error used as thecause.
There is a research on debugging approach that uses
the deltas of code changes between the base version (aversion before the code changes are applied) and a latest version[7, 14]. However, these approaches does notdetect the delta correctly, and require some environmental setup manually to enact a test tool[5] which
requires the inputs of test data and the outputs of test
data which is compared with the outputs of program.
Since these approaches do not support a code modi -2.1 Regression Containment

cation activity that will x the error found by a test
tool, it is diÆcult to apply these approaches to actual
software maintenance activities.
In this paper, we propose a new debugging method
DMET (Debugging METhod) to solve these problems,and a debugging supporting system DSUS (Debugging
SUpport System) based on DMET approach. DMET
supports debugging activities when a defect is found byregression tests, and nds the defects to the featuresthat are not changed during the code changes. DSUS
assumes the existence of a version management system
and a regression test tool, and provides auto con guration/execution of test tools and auto detection a deltaof code that will contain the defects. Since DSUS also
performs as a wrapper of version management system,engineers can concentrate on the error correction work.
We also evaluate our DMET/DSUS with a experimentation. The experimentation shows that total debugging time is reduced by DMET/DSUS when defect detection is succeeded. We also found throughexperiments that DSUS supports a series of software
debugging activities. As a result, DMET/DSUS help
maintaining and evolving existing software.
In section 2, we explain related researches about
software debugging with a delta of code. In section
3, we propose our DMET and show how to detect codedelta that may contain a defect. In section 4, DSUS
debugging supporting system are illustrated. We evaluate DMET/DSUS in section 5, and in section 6 we
present our conclusion and further research topics.

2

Ness and Ngo at Gray Research have proposed themethod called Regression Containment[7]. In Regression Containment, it is mentioned that a software conguration system (version controlling system)[1, 12],tool-chain for testing are used. This method assumes
that the version that carries out normal operation andthe version that contains some errors do not appear
by turns. Under such premise conditions, Regression
Containment identi es the causes of errors by testing
automatically.
In testing phase, base version of source code are extracted from version management system rst, thensome deltas to the codes and compiled to executables. Next, compiled executables are performed withtest data and testing tools compares the results. If
it performs normally, another delta is applied repeatedly. The code modi cation fragments (deltas) can bedetected if there is something wrong is found in the
results of test execution; it enables to specify the causeof this defect without modifying existing source code.
In error collection phase, detected deltas are deleted
from (current version of) source code; it aims at notdelaying software development by this defects.
However, before testing, it is needed to setup someenvironments for running testing tools manually; tools
input (source codes, test data, etc) and correct outputs to compare should be clearly speci ed. Moreover,this method requires applying all deltas to a base version for each test execution, and does not analyze thedi erence of results. This method simply removes thedeltas, which introduces some defects; actually error
correction is not performed.

Debugging with Code Deltas

When some modi cations are applied to software,
the features that were implemented before may be broken. Although the reason is obvious (some errors areincorporated with this modi cation), it is diÆcult to
detect what is an error and x it. In this section, we
consider about a method of debugging using a codedelta, a part for the di erence between the base version and the current version.
Generally, debugging activities is usually composedof testing and error collection. In the debugging
method using code delta, it is assumed that there areno errors in base version and current version has someerrors. In the testing phase, a code delta is detectedwhich contains which causes errors. The code delta isused in the error collection phase.
In this section, we explain previous approaches
about debugging with code deltas about preconditions,
testing procedure, error collection procedure, and its
problems.

2.2 Delta Debugging
In a particular situation, Regression Containment
performs e ectively for debugging. However, when applying two or more deltas cause the defect, or executables cause core dump and no output are collected, it
does not operate well. Zeller has proposed the debugging methods called Delta Debugging[14], which cancorrespond also to these situations that these problems
provide. Although there is no requirement to use software con guration system, it assumes some the existence of test tools[5] that compares the test results.
In order not to take into consideration use of software con guration system, Delta Debugging employs afunction which acts like \di " command in UNIX environment; the code delta between base version and a
version which has some defects are extracted by thisfunction. Obtained delta is examined and classi ed
2

as a set of \code insertion" and \code deletion". Using
these styles of deltas, it can correspond also to the errorthat cannot be nding out by Regression Containment.
Delta Debugging uses the algorithm to nd out thesmallest number of set of code composition that canbe applied in testing phase. In this phase, this method
considers yet another type of error output which corresponds to compilation error or program core dump.
Since an order of code deltas in actual software development is not investigated, a set of program deltas
should be examined by combining each various changes
which is classi ed before which can be applied to baseversion. Therefore, if the number of changes classi ed
nely is n, the number of candidates which will be a
set of program deltas detected by this method is 2n ;combination explosion potentially exists. Since the application order of these changes is not take into consideration, error detection may fail in some cases. Manual
setup of testing tools is also required, and there is noerror correction procedure in this method; it is diÆcult
to apply this method to actual software maintenance
work.

3

Src1

Exe

Src2

V1

V1

V1

V2

V2

V2

V3

V3

V4
V4

V3

V5

Figure 1. Relationship between source codesand objects

changes of not only source code but also program
executables, to reduce the testing time. In caseof registering an executable to version controllingsystem, the relationship between source code andcompiled object are also recorded. Figure 1 shows
an example of this relationship. Src1 and Src2 aresource codes, and Exe is an executable that comesfrom Src1 and Src2. Vi (i = 1,2,..,5) expresses
each version. When registering Exe version V4,
the related information that Exe V4 contains of
V5 of Src1 and V3 of Src2. These relationships
are used later.

DMET

In this section, we propose a new debugging method
named DMET[11] that solves the problem in previous approaches described in section 2. DMET uses
source code deltas to specify defects. In order to support series of debugging procedures, DMET reduces
the premise conditions in previous approaches in testing phase, shows detected deltas with current source
code, and re ects the modi cation which xes the defects to other versions for further debugging.
DMET supports debugging activities, which detecting and xing defects in unchanged features of softwarethat works with base version of software. Limiting thetarget software to some extent, DMET supports autocon guration of testing tools that is normally by manually. Moreover, not only source codes but also compiled objects are managed by existing version management system, total testing time can be reduced. DMET
supports the debugging activities from testing to error
correction; it is applicable approach to actual software
maintenance activities.

 Base version is existed.

In a typical software life cycle, in order to check ordinal operations of the functions required in speci cations, various test cases are taken into consideration. These test cases are used to check in thetesting phase, and if the software correctly passes
to all the test case, the software is released andit will shift to the software maintenance phase.
Therefore it is thought that the base version thatis maybe the rst release of the software exists. It
is guaranteed that there is two versions that thedeltas between versions which contains defects.

 Test results using each version cannot be pre-dicted.
It cannot predict beforehand how the version
which works correctly, and the version which hassome defects. Therefore, it is also considered thata correct version and a defect version appear byturns in the sequence of versions. Moreover, thetest output result of versions which produce defects always are not the same result of the latest
version.

3.1 Premise conditions
There is some premise conditions that are needed forsoftware, software maintenance activity, and software
engineers to apply DMET to debugging activity.

 Version controlling system is used.

We use version controlling system to record the3Under these premise condition, DMET is consistedof three phases, named \detection", \indication", and\re ection".

Regression test: RegT( i , N )VL : version to test

3.2 Detectioni>NI i : input for test

O B, i : correctYes

outputoutputfinishno defects are foundNo

VL : I i =>O L, i

O L, i = O B, iNo

YesRegT( i + 1, N )do the next test

LclT( i , L - 1 , L )do localization test

Figure 2. Regression test(a), there is no errors a ected the latest version's
output between V6 /V9 and V9 /V10.
2. Same correct result of OB;i ( )If the output of Vj is correct, the localization test
is nished and speci es the code deltas between
Vj and Vk has a defect. In Figure 4 (a), deltas
between V5 and V6 has the defects which causes
an error at V10 .

Regression test

The regression test is automatically done whenever certain changes are applied to software. In T (i)(1  i N ), OB;i is used as correct output. If something wrong
with Ti , localization test LctT (i; L 1; L) is performed.
Figure 2 shows an algorithm of RegT (1; N ).
3.2.2

O L, i : wrong

start

In detection phase, auto-detection of source codedeltas is established using auto-execution test tools.
This phase consists of regression test and localization
test. After adding some modi cation to the base version of software, regression test with test data are performed. If something wrong with regression test, localization test are also performed with a test case that ispicked up by regression test. Localization test detects
the versions, which causes error in this regression test.
In this section, we use following notations: Vj shows
the software which version is j , and VB /VL shows thebase version and latest version of software respectively.
Regression test has N test, and each test is shown asTi (1  i  N ). Ii is input data of test Ti , and Oj;i isan output of version j . Each regression test is shown
as RegT (i; N ) where Ti is used in regression test. If
OL;i is a wrong output, each localization test to Vj isshown as LclT (i; j; k) where output Ok;i (j  k) isalso wrong.
3.2.1

T i : test

3. No outputs (4)There is nothing special that the test execution
cannot be done because of the segmentation faultsof the program. Under these circumstances, it isdiÆcult to check the output of test results. Therefore, DMET ignores this version to detect a defect.
However, in the special case, if this is found in the
regression test (Figure 4 (b)), localization test isalso performed with this test data. In this case, detected delta should be between version Vc (whereB < c < L) and VL

Localization test

Localization test checks whether there is a version
which output is the same of OB;i . This checking starts
from VL to VB by linear search, then nds out two versions. DMET assumes there is a base version which
output OB;i is correct, this checking should be stopped
at least all versions are checked. That is, there is atleast one version, which produces correct output between VL and VB . Figure 3 shows an algorithm of
localization test.
Under localization tests LctT (i; j; k), Oj;i are produced and examined, then the results are categorized
as four types.

4. Other outputs (|)
It is assumes that there is yet another defect isfound. However, it is also ignored if the defect is
not what to be detected in this localization test. In
Figure 4, V7 of (a) and V9 of (b) are not considered
in localization test.

1. Same wrong result of Ok;i ()We assume that same wrong output comes fromthe same defects. Therefore, changes between Vj
and Vk does not a ects the defects. In Figure 44

Localization test: LclT( i , j , k )Vj : version to test

T i : test

Vk : defected version I i : input of test

(1) same wrong output(2) correct output

O j, i : output of test
O k, i (= O L, i ) : wrong output(3) no output(4) another wrong output

latest version

base version

V1 V2 V3 V4 V5 V6 V7 V8 V9 V10O B, i : correct output(a) Ti

skip

start

j=B

(2)

Yes

base version

latest version

V1 V2 V3 V4 V5 V6 V7 V8 V9 V10(b) TiVj : I i =>O j, i

O j, i = O k, i

(1)

Defects are found between V5 and V6

finishDefects are between Vb and Vk

No

skip

(3)
(4)
(1)

Yes

skip skip
(4)
(3)
(2)

LclT( i , j-1 , j )Defects are found between V7 and V10

No

O j, i = O B, i

Yes

Defects are between Vj and Vk

Nocore output?

Figure 4. Sample results of localization test
finishYes

LclT( i , j-1 , k )

Src1

Exe

V1

V1

Src2
V1

VC
No

V2

V2

LclT( i , j-1 , k )

V2

VE
V3

Figure 3. Localization test

V3

VL
V4

3.3 Indication

V4

V3

V5

In indication phase, code deltas that are speci edin detection phase are mapped to the latest version ofcodes. At rst, using the relationship between source
codes and executable, source code versions associatedwith executable version are detected. For example in
Figure 5, Exe version VC (decided asin previous
phase) consists of version V2 of Src1 and Src2, andExe version VE (decided as  in previous phase) consists of Src1 version V4 and Src2 version V2. In thisexample, code delta between V2 and V4 of Src1 should
be mapped to V5 (the latest version of Src1).
In general, there are some modi cation between VE
and the latest version VL , the delta cannot be applied
to easily. In the indication phase, modi cations in thedelta are classi ed as \code insertion" and \code deletion", and then some correction is performed to eachmodi cation.
Inserted codes by detected delta may be includedin the latest version, so indication phase analyzes thefurther code modi cation and speci es which line in adelta is the line in the latest version. However, deleted
codes are not shown in the latest version; the phase

Figure 5. Example of indication
checks the deleted point of source code, tracks the further modi cation, and speci es the line in the latest
version if the deleted code existed.

3.4 Re ection
In re ection phase, the modi cation that should x
the detected defects is applied to the every former version until the version that is not a ected with the defect.
This phase should be needed for further cycle of debugging. It is assumed that there are two or more
defects in the target software; if you x one defect in
the latest version, other defects existed from all versions. Further detection phase does work e ectively
when removing the detected defects to all versions.
This phase consists of two procedures, apply a x
5file edit build test window tool

(1) apply a fix(2) compile

file1.c

Src1

Exe

Src2

V1

V1

V1

V2

V2
V3

(1) CL1

V1

exe
1.1
1.2
file1.c
1.1
1.2

Regression Test
Test No[1]correct output
Test No[2]new bug
Localization Test
With Version[1.3]same bug

DSUS

V4
CL2
(1) CL2

CL1

V1

file1.cfile2.c

GUI

V3

V5
(1) CL1

Thu Feb 17 2000

project

V2
V3

V4

file2.c

int main() {scanf("%d", a);if (a == 1) {printf("data is OK\n");} else {printf("data is No\n");}DSUSmain

V1

(2)

(2)

V’2

V’2

V’2

RCS

DejaGnu

V’3
V’4

V’4
storages

V’5
Versioninformation

Figure 6. Example of re ection phase

Figure 7. DSUS structure

and compile again. If either of this procedure fails(does not apply a x, or cannot compile the code),such version is ignored in the further phases.
Figure 6 shows the example of re ection phase. In
this example, there is a defect between V1 and V2 . At
rst, DMET applies a x to V2, V3, and V4 of Src1 andV2 of Src2. Unfortunately, V3 is failed to apply, so thisversion is ignored. Then, compilation is done to all
versions. However, V30 cannot be produced. Therefore,
version V1 , V20 , and V40 are used in next localization test

4

Test data
Test results Executes tools automaticallyRouting work such as doing a regression test istired for engineers. All activities in DMET should
be automatically done by DSUS.

4.2 System overview

DSUS

DSUS system consists of DSUSmain , RCS[12],DejaGnu[10], and graphical interface (Figure 7).
DSUS employs two external systems, RCS and DejaGnu. RCS is a version controlling system based on
check-in/check-out model[3]. DSUS wraps these dangerous operations with GUI; miss-operation of RCS
tools can be eliminated, and periodical check-in canbe performed by DSUS; code delta should be kept tosmall. DejaGnu is a testing framework and DSUS uses
this as regression testing tool. DejaGnu setup is automatically done with con guration templates by DSUS.
DSUSmain is the main engine for DSUS. GUI management, RCS operation, DejaGnu environment setup
and test management are performed by this component. GUI component (Figure 8) is composed of editor
window and status window. User can edit arbitrarily
version of code, and command DSUS to execute theprocedures de ned in DMET.
Most of system is implemented in C, and GTK+[15]is used in GUI component. Con guration templates
are written in Tcl to adapt the DejaGnu requirements.
System scale is about 20000+ LOCs.

In this section, we propose debug supporting prototype system DSUS based on DMET proposed in section
3.

4.1 Features
Before designing DSUS, we specify DSUS features
to support software maintenance activities as follows: Independent from programming language

It is possible that more detailed support can bedone with language dependent system. However,there are many languages used in actual softwaredevelopment environment, so the system should be
language independent to support lots of softwaredevelopment environment.

 Supports both testing and error correction

The debugging system supports not only test execution, but also xing defects. It should be enoughto use DSUS while debugging for engineers.
6Table 1. Software used in the experiments
versions tests detected?
A
28
25
B
91
10
C
72
70

Table 2. Debugging time of G1 (with DMET)
A&B
C
testee17525
testee26260
testee36557
testee47934
testee554
21
average 67.0 39.4

Figure 8. GUI component

5

lected. There are three software (A, B, and C), andsoftware A has 28 versions (including base version),and DMET does 25 times of localization test, and thedetected delta contains the defects. Note that the deltaof software C is large (70 tests executed although there
is 72 versions), and detected delta does not contain thedefects.
Both G1 and G2 members do debugging with thesesoftware, and records the total time of testing and error
correction of each testee. We assume that the elapsed
time of G1 is shorter than G1.

Evaluation

In this section, we evaluate DMET through the experimentation of DSUS. The object of this evaluation
is to con rm DMET is e ective for debugging activities
that x defects in unchanged features.

5.1 Experiments
There are 10 testees (undergraduate and graduate
students in a university, have some skill of C programming), and it divides into two group G1 and G2 .
Group G1 uses whole DSUS features including automated DMET procedures, and group G2 uses restricted
DSUS system which does only regression test, editing code, and check-in/check-out arbitrarily version ofsource code.
In this experiment, we should prepare software
which contains only one defects that comes from theinventory control program of wine shop[6]. To collectthem, we have done a preliminary experimentation. At
rst, we prepare a speci cation and a program whichcomes from the speci cation. Next, we add one feature(checking empty wine container) to the speci cation.
All testees do develop a software based on the one we
provide, with a new speci cation. We have gatheredsoftware, and check if a defect exists in the features
which is in the original speci cation. Note that the program we have prepared with original speci cation has
no defect; after the modi cation by testee, the defectis appeared because testee forget to re ect the changesof the speci cation to the existing part of software.
Table 1 shows the summary of software we have col-5.2 Results and investigations
Table 2 and 3 show the elapsed time results of G1
and G2.
A, B, and C show the software described before, andeach line shows the result of each testee. These tables
summarize the time of A and B; the detected delta
Table 3. Debugging time of
DMET)

testee6testee7testee8testee9testee10
average

7

A&B
237
107
237
69
165
163.0

G2

C
20
5
15
5
8
10.6

(withoutcontains the defect of software.
According to the Welch's test (using 5% di erences),there is a signi cant di erence of the total time of A
and B between both groups. However, the time ofsoftware C and the total time of A, B, and C does
not introduce signi cant di erence between groups.
Therefore, DMET/DSUS provide e ective features fordebugging if the detection is successfully established.
Moreover through this experience, we con rm that
DMET/DSUS support whole procedures of software
debugging.

6[5] IEEE., \Test Methods for Mesureing Conformance to POSIX," ANSI/IEEE Standard 1003.31991, ISO/IEC Standard 13210-1994.
[6] Kudo, H., Sugiyama, Y., Fujii, M. and Torii, K.,\Quantifying a design process based on experiments". In Proceedings of the 21th International
Conference on System Sciences, Hawaii, pages
285{292, 1988.
[7] Ness, B. and Ngo, V., \Regression containment
through source code isolation," In Proceedings ofthe 21st Annual Internatial Computer & Applications Conference (COMPSAC '97), IEEE Computer Society Press, pp.616-621, 1997.

Conclusion

In this paper, we propose DMET debugging method
to detect where is a defect in source code. DMET consists of three phases,including detecting a delta throughversions, indicating the delta to the latest version, andre ecting the changes that x the defect. We also implement prototype system DSUS based on DMET. Using DSUS, we evaluate DMET method. As a result,
we nd out that DMET/DSUS support whole debugging activity, and help maintaining and evolving thesoftware.
As further works, improvements of DMET detection
phase to reduce the number of localization tests and to
detect correct code delta are required. Moreover, weare going to expand DMET method to apply not only
debugging for unchanged features in the maintenancephase, but also for newly created features in the developing phase.

[8] Ostrand, T. and Weyuker, E., \Using Data Flow
Analysis for Regression Testing," 6th Annual
Paci c Northwest Software Quality Conference,
pp.1-4, Portland, Oreg., 1988.
[9] Raither, B. and Osterweil, I., \TRICS : a Testing Tool for C," In Proceedings of the First European Software Engineering Conference, pp.254262, Strasbourg, France, 1987.
[10] Savoye, R., \Test DejaGnu Testing Framework for
DejaGnu Version 1.3," Free Software Foundation.
Inc., January, 1996.
[11] Teraguchi, M., Matsushita, M., and Inoue, K., \A
Proposal of Debugging Method with Changes between Versions," Technical Report of IEICE, SS99-52, pp.17-24, Naha, Japan, 2000.
[12] Tichy, W. F., \RCS - A System for Version Control," Software-Practice and Experience, Vol.15,
No.7, pp.637-654, 1985.

References[1] Babich, W. A., \Software Con guration Management," Addison-Wesley, Reading, Massachusetts,
1986.

[13] Yau, S. and Kishimoto, Z., \A Method for
Revalidating Modi ed Programs in the Maintenance Phase," In Proceedings of the 11th Annual Internatial Computer & Applications Conference (COMPSAC '87), pp.272-277, Tokyo, Japan,
1987.

[2] Dogsa, T. and Rozman, I., \CAMOTE - Computer Aided Module Testing and Design Environment," In Proceedings of the Conference on
Software Maintenance - 88, pp.404-408, Phoenix,
Ariz., 1988.

[14] Zeller, A., \Yesterday, my program worked. Today, it does not. Why?," Proceedings of the
7th European Software Engineering Conference
and 7th ACM SIGSOFT International Symposium on the Foundations of Software Engineering (ESEC/FSE '99), Toulouse, France, September 1999.

[3] Feiler P. H., \Con guration Management Models in Commercial Environments," Technical Report CMU/SEI-91-TR-7, Software Engineering
Institute, Carnegie-Mellon University, Pittsburgh,
Pennsylvania 15213, March 1991.
[4] Hetzel, W., \The Complete Guide to Software
Testing," QED Informaion Sciences, Wellsley,
Mass., 1984.

[15] GTK+ : http://www.gtk.org/

8