IEkE TRANSAClIONS ON SOFTWARE ENGINEERING. VOL. 15. NO 3.

MARCH 1989 34s

Structural Approach to the Estimation of the Number

of Residual Software Faults Based on the Hyper-
Geometric Distribution
YOSHIHIRO TOHMA, FELLOW, IEEE, KENSHIN TOKUNAGA, SHINJI NAGASE,
AND YUKIHISA MURATA

Abstract-New models based on the hyper-geometric distribution for served curve. However, the lack of reasoning why such
estimating the number of residual software faults are proposed. The
functions were used would make us skeptical if their
applications of these models to real data are demonstrated.
methods could be applied to other cases in general.
Index Terms-Debugging, growth, hyper-geometric distribution, In view of the test process, we exploit the hyper-geo-
modeling, reliability, software, test. metric distribution as the basis of our model. This prob-
ability distribution was considered earlier in the context
of the capture-recapture sampling technique. (See, for
I . INTRODUCTION example, [SI.) While earlier studies noted the recaptured

T HE more important roles computer systems play in

highly computerized society, the more serious dam-
age we may suffer upon the failure of computer systems.
faults, we deal here with newly detected faults. They did
not consider the debugging process, but we do in this pa-
per. Thus, we claim that our use of the hyper-geometric
Therefore, computer systems must be very reliable. distribution is different from the earlier ones.
Recent reduction of hardware cost has made redun- In the usual process of the development of a software,
dancy techniques feasible so that hardware faults are well programmers first test their products by themselves, using
tolerated by these redundancy techniques. Contrarily, the some debugging tools. Then, their products will be passed
software is still a simplex system in most applications and to test workers with the programmers’ confidence that the
therefore, computer systems are quite vulnerable to faults software is completely fault-free. However, more faults
in the software. Further, since the software used in most will be found by the test workers in most cases. Here we
computer systems today is very huge and complicated, it focus our attention on this test stage only.
is quite likely to suffer from faults. Thus, the reliability Section I1 shows the definitions and assumptions made
of software has recently become one of major issues in in this paper. Section I11 describes the basic model, and
the realization of highly reliable computer systems. its two extensions will be argued in Sections IV and V.
A variety of models to evaluate the software reliability Section VI gives the concluding remarks.
have been proposed. (See, for example, [l].) Many of
11. DEFINITIONS A N D ASSUMPTIONS
them are those to estimate probabilistically the time du-
ration between occurrences of errors in operation with the A . Notations and De$nitions
analogy to hardware faults [2]-[4]. Another approach is The test of a software is a set of test instances. A test
to argue the number of software faults still residual after instance is a couple of an input test data and the observed
debugging process. This paper presents new models by test result. This set is denoted by D = { t ( i ) 1 i = 1, 2 ,
which we can estimate the number of residual faults in the . . . , n } , where t ( i ) is the ith test instance. n is the total
software, observing the growth of the cumulative number number of test instances.
of faults detected by the test. The applications of these In some cases, a test may be a collection of subsets of
models to real data will be demonstrated. test instances. We call these subsets test classes, because
Several papers already argued the number of residual each subset will have a characteristic nature common to
faults [ 5 ] - [ 7 ]However,
. they only viewed the form of the all test instances of the subset, or it is aimed at a specific
growth curve of the cumulative number of detected faults, test item. For a moment, however, we regard all test in-
looking for appropriate functions which could fit the ob- stances to be of a single class. Sections IV and V will
discuss the test made of several test classes.
Manuscript received December 24, 1986; revised September 29, 1987. A set of faults initially resident in the software (which
This work was supported in part by the Ministry of Education of Japan will be simply referred to as inirialfaults) is expressed by
under a Grant o f Scientific Research. B = { b ( j ) ( j= 1, 2 , * * , m } , where b ( j ) is a fault.
The authors are with the Department of Computer Science. Tokyo In-
stitute of Technology, 2-12-1 Ookayama. Meguro-ku. Tokyo 152, Japan. Thus, the total number of initial faults is m , which is to
IEEE Log Number 8825780. be estimated by our model.

0098-5589/89/0300-0345$01.OO O 1989 IEEE

346 IEEE TRANSACTIONS ON SOFTWARE ENGINEERING. VOL. 15. NO. 3. MARCH 19KY

Here we define the response function of a fault. When Let the probability that t ( i ) detects x faults be
an error due to b ( j ) is observed in (the test result o f ) Prob ( x l m , C ( i - I ) , w ( i ) ) . Then,
t ( i ), b ( j ) is said sensed by (the input test data o f ) t ( i ),
and the value of the response function Y ( i ,j ) of t ( i ) and Prob(x(m, C ( i - l ) , w(i))
b ( j ) is defined to be 1 . Otherwise, r ( i ,j ) = 0. S ( i ) is
a set of faults which are sensed by t ( i ). That is, S(i ) =
{ b ( j ) E B I Y ( i ,j ) = 1 } . Note that the response function
is defined for initial faults, before any maintenance action
is taken place. Further, we distinguish here the sensiti-
zation of faults from the detection of faults.
In the subsequent, EO would denote an estimate of any
parameter 8. w h e r e x m u s t b e o Ix Im i n { w ( i ) , m - C ( i - l ) ]
(this minimum value will be denoted hereafter by 17~).
B. Assumptions The probability distribution of ( 3 ) is called __the hyper-geo-
-
In debugging, test instances t ( l ) , t ( 2 ) , * . will be metric distribution. The expected value N ( i ) of N ( i ) is
exercised. At a test instance, some initial faults will be
newly (term newly attached to the detection will be omit- r 1
ted hereafter for simplicity) detected and the maintenance
will be carried out for these faults. The number of faults L _I
detected by a test instance may vary at actual test in-
stances. Further, new faults may be inserted, when the
detected faults are removed. In the subsequent analysis,
however, we assume the following for simplicity:
1 ) Faults detected by a test instance are surely re-
moved, before the next test instance is exercised. where ROUND represents an appropriate round operator
2) No fault is newly inserted during the removal of the to make the expected value an integer [ 121. If we use the
detected faults. Thus, the software reliability grows with following estimate E C ( i - 1 ) in place of actual C ( i -
the exercise of test instances. 1 ),
3) A test instance t ( i ) senses w ( i ) initial faults. w ( i ) .i - 1. - -
may vary with the condition of test instances over i. c
E C ( i - 1 ) = ;=0 N ( j ) , N ( O ) = 0 (5)
4) Of course, initial faults actually sensed by t ( i ) de-
pend on t ( i ) itself. However, they are regarded to be such we obtain step-by-step the estimate of the number of faults
w ( i ) initial faults that are taken randomly out of m initial detected by t ( i ) for i = 1 , 2, * and accordingly the

faults, since the order of the exercise of test instances is estimate of the cumulative number of faults detected by
indefinite or determined rather randomly within a class of test instances from t ( I ) to t ( i ).
tests. On the other hand, by using such estimate EC( j - 1 )
111. BASICMETHODOLOGY f o r j - 1 Ii a s
A. Model-] J-I __

The number of faults detected by the first test instance

E C ( j - 1 ) = C ( i - 1) + C N(k)
k=l
(6)
t ( 1 ) is obviously w ( 1 ) faults of S( 1 ) by the definition.
However, the number of faults detected by t ( 2 ) is not in place of C( j - 1), we have the estimates f o r j - 1 2
necessarily w ( 2 ) , because some faults of S ( 2 ) may be i , taking the actual C( i - 1 ) into account. In the sequel,
removed already by t ( 1 ) . Similarly, faults detected by however, only- the former case will be considered.
t ( 3 ) are those of S( 3 ) that are not yet sensed by t ( 1 ) and Instead of N ( i ) of (4), we may use such MLN ( i ) as
t ( 2 ) . Thus, the number of faults detected by t ( i ), de-
noted by N ( i ), can be written as
is maximum at x. (7)
That is, MLN( i ) takes the maximum likely x .
where I I represents the cardinality of a set. Then, the Let us denote Prob ( x l m , C ( i - l ) , w ( i ) ) simply by
cumulative number of faults detected so far by test in- L ( x ) . Then, L ( x ) takes its maximum value nearly at such
stances from t ( 1 ) to t ( i ) is x that
I

c
C(i) = j = I N ( j ) . (2)
TOHMA cr ol. ESTIMATION O F RESIDUAL SOFTWARE FAULTS
'
347

Solving this equation for x, we obtain the approximation TABLE 1

F i w ) REPORTOF TEST
of MLN( i ) as - -
- - -
- __
~ - -
- - - - __ ~
-
-
No. of NOof
Dale V(l) Ci') ale ?(I) :(I) C(I)
Workers Uorken
MLN(i) - - -
I 5' 5'
~

4.
-
51
- -
2 433
~

4
-
477
5' 10. 4' 52 2 435 4 477

i 1.
5. 15. 4' 478
{m- c(i - 1) + 1 ) ( w ( i )+ 1 )
3
4
5
5.
6.
20'
"5
4'
4'
53
54
55
2
7
2
437
444
446
4
4
4
478
478
= ROUND 6 8 31 5 56 0 446 4' 479
m + 2 7 2 36 5 57 2 448 4' I07 479
8 7 43 5 58 3 451 4 108 479
9 4 47 5 59 2 453 4 109 480
10 2 49 5 60 7 460 4 480
(9) 11
I2
31
4
80
QA
5
5
61
62
3
0
463
463
4
4'
~
481

13 24 108 5 63 I 461 4.
Parameters to be estimated are m and w ( i ). In order to 14
I5
49
14
157
171
5
5
61 0 464 4. * Intcrpohled
65 I 465 4.
get these estimates, EC( i )'s will be evaluated with the 16
17
12
8
183
191
5
5
66 0 465 3.
67 0 465 3-
following measures. 18
19
9
4
?M
?M
5
5
68 1 466 3.
69 1 467 3
n 20 7 211 5 70 0 467 3'
21 6 217 5 71 0 467 3'
6 217
EF1 = (l/n) ( C ( i )- E C ( i ) l 22
23 4 230
5
5
72
73
I
1
468
469
3'
4
I = ) 24 4 251 5 74 0 469 4.
25 2 236 5 75 0 469 4.
I1 26 4 240 5 76 0 469 4.

EF1' = (l/n) c (ilC(i) - EC(i)l)

i= I
27
28
29
30
3
9
2
5
243
252
254
259
5
6
6
6
77
78
79
I
2
0
470
472
412
4'
2
2.
80 l 473 2.
31 4 263 6 81 0 473 2.
EF2 = max I C ( i ) 32
33
1
4
261
268
6
6
82
83
0
0
473
473
2.
2.
34 3 27 I 6 84 0 473 2.

15
35 6 277 6 85 0 473 2.
36 13 290 6 86 0 473 2-
EF3 = (l/n) 37 19
I5
309 8 87 2 475 2.
I=I 38 324 8 88 0 475 21
39 7 331 8 89 0 475 2.
40 I5 346 8 90 0 475 2.
I1 21

c
41 367 8 91 0 475 2-
42 8 375 8 92 0 475 2.
EF4 = (l/n) 43 6 381 8 93 0 475 2.
i= I 44 20 401 8 94 0 475 2.
45 IO 411 8 95 0 475 2'
46 3 414 8 96 1 476 2-
Em and E w ( i ) will be determined so as to give the min- 47 3
8
417 8
4
97 0 476 2.
48 425 98 0 476 2.
imum value of the measure. The possible change of w ( i ) 49 5 430 4 99 0 476 2.

over i makes it difficult to get Em and Ew( i ) analytically. -50 I

- 431
- 4
___ -00 ~
I -477 ~
2'

Therefore, we rely on the exhaustive scan method over

possible m and w ( i ), looking for Em and Ew ( i ). with the implicitly assumed definition. Hence, we do not
argue the detailed meaning of faults in Table I.
B. Observation 2) Test Instance: As shown in Table I, N ( i ) ' s were
Here we show how Model-1 fits real data. Table I is an recorded day by day. How many test instances were ex-
example of the field report of the test of a software for ercised in a day was not known, nor the condition on
monitoring and real-time control. The software consists which test instances were carried out. Therefore, we in-
of about 200 modules, of which size is about 1000 lines terpret the test exercised in a day as a test instance. Again,
each in a high-level language like Fortran. Since these the detail of test instances is of no matter, provided the
data are not intentionally gathered for evaluating our way of the interpretation is kept consistent.
model, the detailed conditions of test instances are unfor- 3) w (i ): We regard accordingly w ( i ) to be the num-
tunately not recorded in the data. Therefore, we must in- ber of initial faults sensed by t ( i ) defined above. How-
terpret the data in accordance with our model. ever, w ( i ) is not given in Table I. Only information
1) Faults: In real circumstances, how to count faults available is the number of workers who were engaged in
is a problem. A single fault sometimes causes multiple a test instance. The more workers are involved, the more
associated errors in operation. It is natural to count, as a initial faults will be likely sensed by a test instance.
fault, a modification of the software to remove the asso- Therefore, we assume that w ( i ) is a function of the num-
ciated errors in these cases. In more complicated cases, ber of workers at t ( i ) in the form as
however, an error may originate from a combination of
faults. Two ways will be possible in these latter cases. w ( i ) = A,,{tester(i)jP (11)
The one is to regard the combination of multiple modifi- where tester ( i ) represents the number of workers in-
cations for removing the associated error to be a single volved in t ( i ), A,, and p being constants.
fault. The alternative is to count the modifications them- The reason why we consider the exponent p is [hat the
selves. test efficiency will not necessarily be doubled exactly,
However, it does not matter which way is used. The even if the number of workers in a test instance is in-
most important is the consistency in the way of counting creased two times.
faults. If this consistency is kept, we can interpret faults As described previously, w ( i ) will be scanned over an
348 IEEE TRANSACTIONS ON SOFTWARE ENGINEERING. VOL. 15. NO. 3. MARCH 1989

TABLE I1
ESTIMATES
OF m , p , A N D maxw [(4)W A S USED]

EmarW

EC(i) /C(i)
500

40C

30C

20c
OBSERVED

EFI
EF2

EF3
_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ EF4
1 oc
. .. .. . . . , . EFl'

( f
20 40 60 80 IO0 I20

Date
Fig. 1 . EC( i ) and C ( i ) [(4) was used].

appropriate range. In the actual calculation, however, A,, TABLE 111

ESTIMATES
OF m , p , A N D maxw [(9) W A S USED]
is substituted by
A,, = maxw /(maxtester)' (12)
where maxtester is the maximum value of tester ( i ) over E m
(Ap) (0.933) (0.933) (0.171) (0.130) (0.453)
all test instances, and we change maxw and p step by step
with appropriate increments.
One may doubt if w( i ) is a deterministic variable. In The estimates obtained by using (9) were not so much
our preliminary investigation, we considered w as a ran- different from those obtained by (4). They are summa-
dom variable of the normal distribution [9]. However, this rized in Table 111. The values of the measure obtained by
treatment did not show much improvement. using (4) and (9), respectively, are compared in Table IV.
Table I1 shows the estimates together with the ranges Since little difference is observed, (9) will not be used in
of scanning parameters and their increments. The entry in the following sections.
the parentheses represents the value of (12), where
Emaxw and Ep are substituted for max w and p , respec-
IV. SEGMENTATION
tively. Equation (4) was used in obtaining E C ( i ) ' s .
EC( i )'s together with C ( i )'s are plotted in Fig. 1. It can A . Model-2
be seen that the fitness of Model-1 is fairly good on the Looking at Fig. 1 in more detail, we see that E C ( i )
whole. does not follow C ( i ) very well over the ranges of the
TOHMA er (I/. : ESTIMATION OF RESIDUAL SOFTWARE FAULTS 349

Eq.(4) 14.69 40.0 0.0278 343.7 349.6

Eq.(9) 14.19 39.0 O.oo00 324.7 351.6

TABLE V
FIFI.DRFPORIOF TEST
-
- - - - __ -
- - - - ~
- -
- -
- - -
- - -
- -.
~

No. of No. of NO. of NO. Of

1ale V(1) 7(1) ale $11) C(1) >ale {('I Cll) Norker lale '(1 1 :(I)
$0rkers
- - - Yodm
~ - - - Norkerr~ - - - - - - - ~

1 0. 0
. NA 51 0. 5- NA 101 0' 27. NA 5521 N 50' NA
2 N 0. NA 52 N 5' NA 102 N 27' NA N 50. NA
3 '
0 0. NA 53 N 5. NA 103 '
0 27. NA 53 0. 50. YA
4 0. 0. NA 54 0. 5' NA 101 N 27' NA 54 I 51 NA
5 0' 0
. NA 55 I 6 NA LOS 1 28 NA 55 0. 51. NA
6 0' 0. NA 56 0. 6% NA lo6 O* 28' NA 56 N 51. NA
7 0' 0' NA 57 3 9 NA I07 N 28. NA 57 0. 51. NA
8 '
0 0' NA 58 N 9. NA IO8 0. 28. NA 58 0' 51' NA
9 0' 0' NA 59 0. 9. NA IW 0. 28. NA 159 0. 51' NA
IO 0. 0. NA 60 I1 NA I10 0' 28. NA 160 1 52 NA
I1 0' 0' NA 61 2 13 NA Ill 0. 28. NA 161 0
. 52- NA
I2 N N NA 62 0' 13' NA I12 1 9 NA 162 I 53 NA
13 0. 0' NA 63 2 IS NA 113 0. 29' NA 163 N 53' SA
14 0. 0' NA 64 1 16 NA I I4 '
0 29' NA 164 0' 53' NA
IS 2 2 NA 65 0' 16. NA 115 I 30 NA 165 0. 53. NA
16 0. 2. NA 66 0. 16' NA I I6 0' 30' NA 166 0. 53. NA
17 1 3 NA 67 0. 16. NA I I7 '
0 30' NA 167 N 53. NA
18 N 3* NA 68 18 NA 118 0' 30* NA 168 N 53- NA
19 N 3. NA 69 20 NA 119 '
0 30' NA 169 0
. 53' NA
20 0- 3' NA 70 N 20' NA I20 0. 30. NA 170 '
0 53' NA
21 0' 3. NA 71 '
0 20' NA 121 0. 30. NA 171 N 53' NA
22 N 3. NA 72 0' 20' NA I22 0. 30' NA I72 0. 53. NA
23 N 3' NA 73 0. 20. NA 123 '
0 30' NA 173 0. 53. NA
24 N 3. NA 74 0. 20' NA I24 '0 30' NA 174 0. 53' NA
25 0
. 3' NA 75 '
0 20. NA I25 2 32 NA 175 0. 53' NA
26 0. 3. NA 76 0. 20. NA I26 2 34 NA 176 N 53. NA
27 0' 3. NA 77 1 21 NA 127 (r 34. NA I77 0. 53' NA
28 0
. 3. NA 78 N 21. NA I28 1 35 NA 178 1 54 NA
29 N 3' NA 79 0. 21. NA I29 1 36 NA I79 01 54' NA
30 0. 3' NA 80 0. 21. NA I30 N 36. NA I80 0. 54. NA
31 0. 3' NA 81 0- 21. NA I31 0' 36- NA 181 0. 54- NA
32 0. 3. NA 82 0. 21. NA I32 0' 36. NA 182 N 54' NA
33 N 3' NA 83 0. 21. NA I33 1 37 NA 183 I 55 NA
34 0' 3. NA 84 0. 21. NA I34 1 38 NA 184 0. 55' NA
35 0. 3' NA 85 0' 21. NA 135 1 39 NA 185 N 55' NA
36 '
0 3' NA 86 1 22 NA 136 0. 39, NA 186 0' 55' NA
37 0. 3' NA 87 2 4 NA 137 N 39- NA 187 0. 55' NA
38 0
. 3. NA 88 0' 24. NA 138 0. 39' NA 188 0' 55. NA
39 N 3. NA 89 0. 24' NA 139 0. 39' NA I89 N 55- NA
40 1 4 NA 90 1 25 NA 140 I 40 NA I90 0. 55' NA
41 0- 4' NA 91 0. 25. NA 141 2 42 NA 191 0. 55. NA
42 0. 4' NA 92 0. 25- NA 142 N 42' NA 192 0' 55. NA
43 0' 4. NA 93 0. 25. NA 143 3 J5 NA 193 0. 55. NA
44 1 5 NA 94 0. 25' NA 144 1 46 NA 194 '
0 55' NA
45 0. 5. NA 9s 0- 25' NA 145 1 47 NA 195 '
0 55' NA
46 0. 5' NA 96 27 NA 146 0. 47- NA 196 0. 55. NA
47 0. 5' NA 97 '
0 27' NA 147 1 ?8 NA I97 0. 55. NA
48 0' 5. NA 98 0
' 27' NA 148 1 49 NA 198 N 55' NA
49 0- 5' NA 99 N 27- NA 149 1 so NA 199
- 0
- 55
- ~
NA
0' 5' NA 00 0. 27 NA I50 0' 50. NA
50 ~ ~ ~ - - - ~ - ~ - -

sharp bends of the growth curve of C( i ). The test data of different T ( j ) ' s . That is, in each T ( j ), j = 1 , 2, . . . ,
Table V is another example, where the software consists the detection of faults is modeled by the hyper-geometric
of about 14.5 kilolines of ASSEMBLER language and is distribution as before, but with different in ( j ) and \ t 3 ( i.
developed for a railway interlocking system. The direct j ). However, if we consider each test class still to test the
application of Model-1 to this data is not successful as software as a whole, m ( j ) should be the same constant
shown in Fig. 2. (Since the number of test workers was for all test intervals.
not available here, w ( i ) was assumed to be independent Further, at the beginning of T ( j ), C( n ( j - 1 ), ,j -
of i.) 1 ) must be taken into account, where t7 ( j - 1 ) is the
The bends of the growth curve of C( i ) possibly relate number of test instances of T ( j - 1 ). We assume that
to the change of the nature of test instances. In fact, we C ( 0 , j ) is not equal to 0, but C ( n ( j - l ) , j - 1 ) . In
see from the more detailed investigation that test instances the actual estimation, however, EC( n ( j - 1 ). j - 1 ) is
of Table V can be classified into test classes as shown in used in place of C ( n ( j - l ) , j - 1 ) .
Table VI. In general, the last interval will be devoted to an overall
Considering the change of the nature of test classes, we test. In such a case, the estimate of m ( j ) obtained there
divide the whole test duration into intervals T ( 1 ), T ( 2 ) , will be Em itself.
. . . , and so on. Then, the ith test instance in T ( j ) is
represented by t (i, j ). Accordingly, the cumulative num- B. Observation
ber of faults detected by test instances from t ( 1, 1 ) to t ( i, The application of the above segmentation technique to
j ) is denoted by C( i, j ). Its estimate will be suffixed sim- the test data of Table 1 revealed that the use of the same
ilarly. constant tn ( j ) over test intervals was not so favorable
We assume the parameters to take different values over [ 101. We speculate that the same constant m ( j ) generally
350 l E t E 'TRANSACTIONS ON SOFTWARE ENGLNEERING. VOL. IS. N O 3 . M A R C H 19x9

EC(i) / C ( i )
60
r

Date

Fig. 2. E C ( i ) and C ( i ) [(4) was used]

TABLE VI TABLE V11

T t s r CLAssr:.s SEGMENTATION
Classes Test Insrances Interval I TestInstance I
Module & Partial
Combination
Combinatorial(1)
Over-All(1) 10.5 - 123
Combinatorial(2) 124 - 139
Over-All(2) 140 - 199

TABLE VI11
makes plots of E C ( i ) rather smooth and accordingly, the Em( j ) A N D E w ( j )
use of the segmentation technique does not fit sharp bends
of the growth curve of C ( i ) well. Therefore, we assumed
in the application of the segmentation technique to the test
data of Table V that m ( j ) would take different values
over j .
Viewing test classes of Table VI and the bends on the
plots of C ( i ) of Fig. 2, we determined the test intervals V . COMPOSITE ESTIMATION
as shown in Table VII. As before, we assumed w( i, j ) to A . Model-3
remain constant in T ( j ). In the above two sections, we did not consider what
The result of the estimation is summarized in Table modules of the software were exercised by test instances.
VIII. EC( i , j )'s and C ( i, j ) ' s are plotted in Fig. 3 . The Here, a test class TC(i), i = 1, 2, * is assumed to -
improvement made by the segmentation technique is re- exercise only a part of the software. This part, denoted
markable. by D ( i ) , will be called simply the domain of TC(i).
TOHMA PI u l . : ESTIMATION OF RESIDUAL SOFTWARE FAULTS 35 1

Date

Fig. 3 . EC( i, j ) and C( i, j ) [(4)was used].

D ( i ) may or may not have a common part with D ( j ), j

# i. Test classes and their domains can be determined
from the structure of the software and the test items.
However, D ( i ) may not necessarily correspond to the
modular structure of the software. Even if the software
consists of modules, some of them may be exercised al-
ways together by a test class. In such a case, these mod-
ules exercised together should be regarded as a whole to
be a domain of the test class.
Suppose that the test consists of three test classes
T C ( a ) , TC( b ) , TC( c ) and their respective domains
D ( a > ,D ( b ) , D ( c ) are as shown in Fig. 4. D ( a ) is di-
vided into four subdomains: A , A fl B , A n C, and A n
B f l C. A is the area proper to T C ( a ) , while A fl B is Fig. 4. Test classes and domains.
the area included commonly in D ( a ) and D ( b ) . This
means that faults in this area are sensed by both test in-
stances of T C ( a ) and T C ( 6 ) . Likewise, A fl B fl C i s of course, influenced by faults detected in the common
the area common to D ( a ) , D ( b ) , and D ( c ) . Let us de- area by test instances of TC( b ) and/or TC( c ) . Just before
note the numbers of initial faults in D ( a ) , D ( b ) , D ( c ) , the ith test instance of T C ( a ) [which will be denoted by
A , B , c, A n B , B n c, c n A , and A n B n c by t (i, a ) ] ,let the cumulative numbers of faults detected in
m ( a > ,m ( b ) , m ( c > ,m ( A ) , m ( B ) , m ( C ) , m ( A n B ) , A n B , A n C , and A fl B C by test instances of
m ( B fl C ) , m ( C f l A ) , and m ( A f l B f l C ) , respec- T C ( b ) and T C ( c )be C,(i - 1, A fl B ) , C,(i - 1, A n
tively. B n c ) ,~ , ( i - 1, A n c ) ,and c,(i - 1, A n B n
The detection of faults by test instances of T C ( a ) is, C ) , respectively, and the cumulative number of faults de-
352 I E E E TRANSACTIONS ON SOFTWARE ENGINEERING. VOL. 15. NO 3. MARCH 1984

tected by test instances of T C ( a ) be C u ( i - 1 ) . Then, Em ( B n C ) and Em ( C n A ) will be estimated similarly.

the faults detected by this t ( i , a ) will be some of the re- E m ( A fl B n C ) will be estimated by
maining
Em(A n B n c )= { E m ( a )K , ( A n B n C)
m ( a ) - C,(i - 1 ) - C/,(i - 1, A f l B)
+ E m ( b ) K / , ( An B n C )
- C/,(i - 1, A r l B nC)
+ E m ( c ) K,.(A n B n c ) } / 3 .
- c<(i- 1 , n~ c ) - C < ( i- 1, A n B n c)
( 16)
faults in D ( a ) . Therefore, the probability that the number
of the detected faults is x can be evaluated by (3) with Then, Em ( A ) is given by
m ( a ) and E m ( A ) = Ern(a) - Em(A n B)
+ C,(i 1, A fl B )
Cil(i - 1 ) -
- E ~ ( A n c )- Em(A n B n c). (17)
+ c,,(i- 1, A n B n c ) The following remark should be in order. The cumu-
+ C((i- 1, A n C ) + c<(i 1, A n B n c ) lative number of faults actually detected in A n B , A n
C , and A n B n C by test instances of TC( 6 ) and TC( c ) ,
-

in place of m and C(i - 1 ), respectively. Except this for example, is used in the calculation of the estimate of
substitution, Em ( a ) will be obtained in the same way as the number of faults detected by a test instance of T C ( a ) .
described in Section 111. Em ( b ) and Em ( c ) will be ob- In Section 111-A, however, EC( i - 1 ) was used in place
tained likewise. of the actual C( i - 1 ). In this context, the way of cal-
Obviously, the estimate of the total number of initial culation here is a little inconsistent with those in the pre-
faults in the software may not be equal to the summation ceding sections.
of E m ( a ) , E r n ( b ) , and E m ( c ) . Note, for example, that Inprinciple,wecanuseEC,,(i- l , A n B ) , E C , ( i -
both Em ( a ) and Em ( 6 ) include faults in A f l B . There- 1, A f l B f l C ) , EC,.(i - 1, A f l C ) , and E C , ( i - 1,
fore, we must obtain E m ( A ) ,E m ( B ) ,E m ( C ) as well as A fl B n C ) . However, it makes extremely large the
E m ( A n B ) , € m ( B n C ) , E m ( C fl A ) , and E m ( A n number of cases of scanning parameters to find their op-
B n c). timum values. Therefore, this approach may not be fea-
Let C , and C ( A n B ) be the numbers of faults actually sible in real applications.
detected in D ( a ) and A fl B , respectively. We define
coefficient K , ( A n B ) to be the ratio of C ( A n B ) to C(,. B. Observation
Other coefficients will be defined similarly. Then, it seems Here we present the result of the composite estimation
reasonable to evaluate Em ( A n B ) by described above. The software used in this estimation was
developed for monitoring and real-time control. It con-
Em(A f l B ) = Em(a)K,,(A n B). (13) sists of about 90 modules. The size of modules is about 1
Similarly, Em ( A n B ) may also be evaluated by kiloline of PL/ 1, Fortran, and Assembler languages in
average.
Em(A nB) nA)
= E m ( b ) K,(B (14) The data was collected on what modules were exercised
by test instances and where faults were found. Since the
where K , ( B n A ) is the ratio of C(B nA ) = (C(A n software was tested on its three functional properties, the
B ) ) to Cl,. test instances were classified into T C ( a ) , T C ( b ) , and
If E m ( a ) and E m ( b ) would be accurately equal to T C ( c ) . Three domains D ( a ) , D ( b ) , and D ( c ) were
m ( n ) and m ( b ) , respectively, and further E m ( A n identified accordingly. These domains have common areas
B ) / E m ( a )and E m ( A f l B ) / E m ( b )would also be & ( A as shown in Table 1X. There was no module which was
f l B ) and &,(A n B ) , respectively, both (13) and (14) tested by T C ( b ) and T C ( c ) (that is, B fl C = null).
would give us exactly the same value. However, it is not The table shows the number of detected faults for each
always the case, because E m ( a ) and E m ( b ) are only the test date and for each subdomain. No faults were detected
estimates and possibly include errors. Further, due to the in A n C by T C ( a ) , in B n C by T C ( b ) , nor in C n A
rather limited number of test instances, the relationship and C n B by T C ( c ) . The total number of workers in a
that E m ( A f l B ) / E m ( a ) = K , ( A f l B ) and E m ( A fl day is divided for each test class in reference to the time
B ) / E m ( b ) = & ( A fl B ) may not hold exactly. Thus, spent for each test class. In some days, a test class (test
the above two equations may give us slightly different Val- classes) was (were) not exercised. These cases are indi-
ues. Therefore, we estimate E m ( A fl B ) by cated by "-" in the table. The number of detected faults,
Em(A n B ) = { Em(a)&(A n B ) the cumulative number of detected faults, and the number
of workers for each day are respectively summarized in
+ € m ( b )&(A fl
B)}/2. (15) the table.
TOHMA 1’1 a l . : ESTIMATION OF RESIDUAL SOFTWARE FAULTS 353

TABLE 1X
O F Ttsr
F I ~ LREPOKI
D
-
- -

T
- ~
~

Date -
7 8 9 10
- 12 13 14 15 _.
16
N ( i ) detected
by TC ( a ) in
(A 1
- - 1 1 2 1 0 1 2
(Am) - 0 0 1 0 0 1 0
( A M nC) - 0 - 0 0 1 0 1 0 0
Subtotal - 1 1 4 1 1 2 2
No. of worken
- 2.5 - 3 4 3.3 I 9.4 14 10
in TC ( a ) - - -
N (i) detected
by TC(b) in
(8 ) 1 2 - 12 4 3 4 0 0
( B a ) 0 1 - 0 0 0 0 0 0
(BnCfIA) 0 0 - 0 2 2 0 0 0
Subtotal 1 3 - 12 6 5 4 0 0
No. of workers -
0.6 1.5 12 8.7 10 5.7 4 IO
in TC(b) - -
N ( i ) detected
by TC(c) in
(C) 7 23 19 8 9 2 3 4 0
(CfMflB) 4 0 3 1 0 0 0 0 0
Subtotal 11 23 22 9 9 2 3 4 0
No.of workers 9.4 9.5 12
25 8 9 11.9 14 8
in T C ( c ) - - _.

NU) 12 26 23 22 19 8 8 6 2
C(i) 75 101 124 46 174 182 190 196 198
Total No. of
10 I1 28 28 30 26 27 32 28
worken - -

From the table, we obtain E ~ ( n

A B n c )= (i/3) x (71 x 0.344 + 99
ca 64,c b = 76, c, = 115, x 0.289 + 148 x 0.191)
C(A n B ) = 13, C ( B n c ) = c(c n A ) = 0, = 27.1. (20)
C ( A n B n c ) = 22. Others are summarized in Table X. Em is defined by
K,(A n B) = 13/64 = 0.203, Em = Em(A) + Em(B) + E m ( C )
K,(A n c ) = 0, +E ~ A B) + E ~ ( n
( n B C)

KJA n B n c ) = 22/64 = 0.344, +E ~ nA) + E ~ ( n

( C A B n c ) .(21)
It is 248. When the detailed structure of the software is
& ( B n C ) = 0,
ignored, its value (given by applying Model-1) is 230.
K , ( B n A ) = 13/76 = 0.171, In order to estimate the growth of the cumulative num-
ber of detected faults, E C ( i , a ) , the estimate of the cu-
Kb(B n c n A ) = 22/76 = 0.289, mulative number of faults detected by test instances from
r ( l , u ) t o f ( i , a ) o f TC(a),aswellasEC(i,b)forTC(b)
K J C n A ) = K J C n B ) = 0,
and EC( i, c ) for TC( c ) were calculated, respectively, by
K J C n B n A ) = 2 2 / m = 0.191. the method described above. Note, however, that they
must be allotted in accordance with their test date, be-
We estimated cause i is only the sequential number of a test instance
and does not necessarily correspond to the date of the test
E m ( a ) = 71, instance. Then, the estimates of the cumulative number
E m ( b ) = 99, of detected faults in T C ( a ) , T C ( b ) ,and T C ( c ) for each
test date were added to each other, and the sum was com-
E m ( c ) = 148. (19) pared to C ( i ) of Table IX. These are plotted in Fig. 5.
Therefore, E m ( A f l B ) , E m ( A fl C ) , E m ( A nB fl C ) VI. CONCLUDING REMARKS
are given by
Based on the hyper-geometric distribution, we have
E ~ ( n
A B) = ( 1 / 2 ) x (71 x 0.203 proposed the basic model (Model-1) for estimating the
+ 99 x 0.171) = 15.7, number of initially resident faults in a software. Examples
of the application of this model indicate that the fitness of
E ~ ( n
A c )= 0, Model-1 to real data is fairly good, when the cumulative
354

ESTIMATED
TABLE X
NUMBFR

Subc;ain

AflB
Bn C
C m
OF FAULTS

1
IEEE TRANSACTIONS ON SOFTWARE ENGINEERING. VOL

I N SUBDOMAIYS

Esthated;of

120.9
Faults
I S . NO 3. MARCH 198’)

AflBflC 27.1
Total 248.1

250

200

150

100
OBSERVED

EF1

EF2

-
___._._ __ EF3

_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ EF4
EFl *
50

C I
2 4 6 8 10 12 14 16
Date
Fig. 5. E C ( i ) and C ( i ).

number of detected faults grows smoothly with the exer- exercised in succession. In such a case, the division of
cise of test instances. the whole test duration into successive test intervals may
We have also shown ways of improving Model-1, i.e., not be justified. Some rearrangement of test instances will
the segmentation technique and the composite estimation. be required.
The application of the segmentation technique (Model-2) Here, we considered only the number of test workers
looks quite effective, particularly when the growth curve in defining w(i)/w(i,j ) . w ( i ) / w ( i ,j ) could be im-
of the cumulative number of detected faults bends sharply. proved, if additional factors such as the number of test
In determining the test intervals, we noted in part that items in a test instance and/or the progress of the skill in
the sharp bend occurred a little later than the time of the exercising test instances were taken into account. We are
change of test classes. We observed similar delays in other currently conducting further studies on this line.
examples. Thus, some mechanisms should be incorpo- The composite estimation looks promising. As we see
rated in the segmentation technique so that we could de- in Table IX, however, the number of test instances for
termine test intervals only by observing the change of test each test class was rather small to make the estimation
classes. properly. Although we hope the composite estimation as
Further, test instances of a test class are not necessarily well as the segmentation technique will be effective in
TOHMA ('I o/ F.SrlMATlON OF RFSIDUAL S O F T W A R E F A U L I S 355

where the plot curve of C ( j ) bends sharply, further Dr. Tohina is an Advisory Board Member of TC on Faull-Tolci-anl
Computing. IEEE Computer Society. and Vicc-Chairman of IFlP WG 10.4.
investigation with more data of test instances will be He served as ProFraln of FTCS.IO and w i l l
needed to evaluate our models definitely. Charman of FTCS-18 to be held i n Tohyo i n 1988 He I \ a mcnihcr ot thc
The composite estimation and the segmentation tech- hformation Processing Society of Japan. the Japan Sociely lor Softwarc
Science and Technology. the Institute o t Electronic\. Intornlation. and
nique should be combined with each other. Communication Engineers (IEICE). and other technical socictics i n Japan.
Among other awards from IEICE. he received the Excellent Booh Auard
ACKNOWLEDGMENT and the Okabe Memorial Award.

We express our thanks to Railway Technical Research

Institute, Japan National Railways, and Toshiba Corpo-
ration for their cooperation and support in providing us
with real data.
REFERENCES Kenshin Tokunaga was born in Yaniaguchi. Ja-
pan. on February 1 1 . 1961. He received the
C. V . Ramainoorthy and F. B. Bastani. "Software reliability-Status B.Eng. and M.Eng. degrees in computer sciencc
and per5pectives." / € € E Trcrris. Sofrltwrc, G i g . , vol. SE-8. no. 4 , pp.
from Tokyo Institute of Technology. Tokyo. Ja-
354-371, Apr. 1982.
pan, in 1983 and 1985. respectively.
2 . Jelinski and P. B. Moranda. "Software reliability research." in
Since 1987. he has been with the Department
S/c/risriccr/ Cortipicter Pei$rrricrric.e E i u I u c i I i o r i . W . Freiberger. Ed.
of Computer Science. T o k j o Institute of Tech-
New York: Academic, 1972. pp. 465-484.
nology. His current research interests include nat-
B. Littlewood and J . L. Verrall, "A Bayesian reliability model with
ural language processing and k n o w ledge rcprc-
a stochastically monotone failure rate." lEEE Trnr7.y. Re/. , vol. R-23,
sentation.
no. 2. pp. 108-1 14. Feb. 1974.
Mr. Tokunaga is a member of the Information
A. A. Abdel-Ghaly. P. Y . Chan. and B. Littlewood. "Evaluation of
Processing Society of Japan and the Japan Society for Softuare Scicncc
competing software reliability predictions," / € € E Truns. Sofr\t~are
and Technology.
Etig., vol. SE-12. no. 9. pp. 950-967, Sept. 1986.
T . Mitauhashi, The Eiwluciriori of Sojhturc. Quciliry. Nikkagiren.
1981. pp. 182-191 (in Japanese).
A. L. Goel and K. Okumoto, "Time-dependent error-detection rate
model for software reliability and other performance measures," / € E E
Truns. R e / . , vol. R-28, no. 3 , pp. 206-21 I. Aug. 1979.
S. Yamada and S. Osaki, "Software reliability growth modeling:
Models and applications," /€EE Trnr7s. Sofruure Eng., vol. SE-I I .
Shinji Nagase was born i n Kuwana. Japan. o n
no. 12. pp. 1431-1437. Dec. 1985.
February 28. 1962. He received the B.Eng. and
G . J . Schick and R. W. Wolverton, "An analysis of competing soft- M.Eng. degrees in computer science from Tokyo
ware reliability models." /€€€ Trcrris. Softweire € r i g . , vol. SE-4, no.
Institute of Technology, Tokyo. Japan. in 1981
2. pp. 104-120. Mar. 1978.
and 1986, respectively.
Y . Tohma and K. Tokunaga, "A model for estimating the number of
Since 1986, he has been associated with Chubu
software faults." Inst. Electron. Conimun. Eng. (IECE) Japan. Tech.
Electric Power Company, Inc. His research inter-
Rep. FTS86-14, Sept. 1986. ests include fault-tolerant computing and software
Y. Tohnia, S . Nagase. and Y. Murata. "Structural approach to soft-
engineering.
ware reliability growth model based on the hyper-geometric distri-
bution." IECE Japan, Tech. Rep. FTS86-23, Nov. 1986.
B . Littlewood, "Software reliability model for modular program
structure." / € E E Trcitis. R e / . . vol. R-28. no. 3 , pp. 241-246. Mar.
1979.
T. C. Fry, Probcihi/ir\ c i n d irs Erfgiric.erin,y Uses. 2nd ed. New York:
Van Nostrand. 1965. p . 205.

Yukihisa Murata ua5 born i n Hqogo. Japan on

Yoshihiro Tohma (M'74-SM'75-F'80) was born October 23. 1954 He received the B Eng degree
i n Kdwdsdki. Japan, on Augu\t 22, 1933 He re- i n intormation engineering trom Kyoto UniLer-
.
ceived the B Eng M Eng , and Dr Eng degrees S l t y . Kyoto. Jdpdn. i n 1977
in electrical engineering from Tokyo Institute of Since 1977. he ha\ been engaged i n de\igning
Technology. Tokyo. Japan, i n 1956, 1958, and and developing operdting \)\tern\ of gener'il pur-
1961, respectively pose computer\ at Mit5ubishi Electric Corpora
In 1961, he joined the \la8 of Tokyo In5trtute tion His m e a r c h interest5 include operating \q\
of Technology. where he is a Profe\sor of Com- tern\. computer architecture. and wttu'irc
puter Science His research interest5 include com- engineering
puter architecture. fdult tolerant computing. and Mr Muraid is a rneinber ot thc Intoriii,itioii
software engineering Processing Society of Japan