Software error detection models : validation tests and program complexity measures

LIBRAPY
TECi-
NAVAI
MONTEREY. CA.

NPS52SS76111

//

NAVAL POSTGRADUATE SCHOOL

Monterey, California

SOFTWARE ERROR DETECTION

MODELS , VALIDATION TESTS

AND PROGRAM COMPLEXITY MEASURES

by

N.

F. Schneidewind G. T. Howard

M. Kirchgaessner

November 197 6

Approved for public release; distribution unlimited

FEDDOCS

D 208.14/2:NPS-52SS76111

epared for:

val Air Development Center

rminster, Pennsylvania

NAVAL POSTGRADUATE SCHOOL
Monterey, California

Rear Admiral Isham Linder Jack R. Brosting

Superintendent Provost

The work reported herein was supported by the Naval Air Development
Center, Warminster, Pennsylvania.

Reproduction of all or part of this report is authorized.

This report was prepared by:

UNCLASSIFIED

SECURITY CLASSIFICATION OF THIS PAGE (Whan Data Entered)

REPORT DOCUMENTATION PAGE

READ INSTRUCTIONS
BEFORE COMPLETING FORM

I. REPORT NUMBER

NPS-52SS76111

2. GOVT ACCESSION NO

3. RECIPIENT'S CATALOG NUMBER

4. TITLE (and Subtitle)

Software Error Detection Models, Validation Tests
and Program Complexity Measures

5. TYPE OF REPORT 4 PERIOD COVERED

Technical Report

6. PERFORMING ORG. REPORT NUMBER

7. AUTHORCsJ

N. F. Schneidewind and G. T. Howard

8. CONTRACT OR GRANT NUMBER*-*;

9. PERFORMING ORGANIZATION NAME AND ADDRESS

Naval Postgraduate School
Monterey, California 93940

10. PROGRAM ELEMENT, PROJECT, TASK
AREA 4 WORK UNIT NUMBERS

N66269/76/RQ/02030

II. CONTROLLING OFFICE NAME AND ADDRESS

Naval Air Development Center
Warminster, Pennsylvania 18974

12. REPORT DATE

November 1976

13. NUMBER OF PAGES

154

14. MONITORING AGENCY NAME 4 AODRESSf// different from Controtlini Office)

15. SECURITY CLASS, (of thia report)

Unclassified

15«. DECLASSIFI CATION/ DOWN GRADING
SCHEDULE

16. DISTRIBUTION STATEMENT (of thia Report)

Approved for putlic release;
distribution unlimited

17. DISTRIBUTION STATEMENT (ot the abatract entered In Block 20. If different from Report)

18. SUPPLEMENTARY NOTES

19. KEY WORDS (Continue on reverae aide if neceeaary and identify by block number)

Software measurement
Program Structure
Software error

20. ABSTRACT Continue on reverae aide II neceeaary and identify by block number)

This report describes a continuing research effort in software reliability
which was first reported in "System Test Methodology," Naval Postgraduate
School, Vol I NPS55SS75072A, Vol. II NPS 55SS75072B(1975) . The work just
completed involved: improvement of the software error simulation model;
validation of the software error simulation model; and analysis of program
complexity with simulation and analytical models, using 44 Naval Tactical
Data System procedures. The results which were achieved are the following:

DD , :°NRM73 1473

EDITION OF 1 NOV 65 IS OBSOLETE
S/N 0102-014-6601

UNCLASSIFIED

SECURITY CLASSIFICATION OF THIS PAGE (Whan Data Sntarad)

Unclassified

.L.CUR1TY CLASSIFICATION OF THIS P XGECWhon Data Entered)

(1) all validation tests were passed; however simulation results were
generally higher than analytical results and (2) the general direction
of the relationship between complexity measures and error detection was
as expected; however, considerable variability was exhibited when single
independent variables were used. It appeared that a multivariable model
involving error detection and several program complexity measures would
be more appropriate.

UNCLASSIFIED

SECURITY CLASSIFICATION OF THIS PAGEfWh«n Data

TABLE OF CONTENTS

s
INTRODUCTION 1-1

DESCRIPTION OF ERROR SIMULATION PROGRAM II-l

VALIDATION TESTS III-l

ANALYSIS OF COMPLEXITY MEASURES IV-1

SUMMARY V-l

REFERENCES R-l

APPENDIX A: FLOW CHART OF ERROR A-l

SIMULATION PROGRAM (MAIN) , AND
SUBROUTINE (SEED)

APPENDIX B: DIRECTED GRAPHS, B-l

SIMULATION AND ANALYTICAL RESULTS

I. INTRODUCTION

This report describes and documents the research conducted at the
Naval Postgraduate School (NPS) during FY 76-77 on the System Test Methodology
project sponsored by the Naval Air Development Center (NADC) . The project
began in FY 75-76. Previous reports were "System Test Methodology," Vol. I,
NPS55Ss75072A and Vol. II, NPS55Ss75072B, July 1975, published by the Naval
Postgraduate School [1] . Several publications in the open literature have
resulted from this research [2, 3, 4]. This work covered three areas:

a. Software error simulation and analytic models.

b. System test simulation model.

c. Partitioned tests for software error analysis.

Computer programs were developed and provided to NADC for the simulation and
analytic models of a. Of the three areas, it was felt a. had the greatest
potential for improving software reliability. Consequently, the following
efforts were undertaken in FY 76-77:

Improvement of the software error simulation model.

Validation of the software error simulation model.

Analysis of program complexity measures.
These topics are covered in Sections II, III, and IV, respectively. A brief
overview of each topic, in the order listed above, will be given here.

° Sections of the simulation program which involved execution and

repair times were removed because: (1) current research interests
are structural characteristics and error detection properties of
programs, rather than timing aspects and (2) CPU time required by
these parts of the program were too high in relation to the need for
this information. The new error insertion feature (simulates the

1-1

possibility of new error insertion as a result of error correction)
was removed because this process is not well understood. Therefore,
it was difficult to prescribe the appropriate probability distribu-
tions and conditions which should govern error insertion in a
simulation. User instructions are provided in Section II. A program
listing of the simulation model is included with this report.
Validation tests of the simulation model were performed with respect
to: (1) mean number of errors seeded, (2) probability of arc traversa
and (3) number of arc and path traversals. Validation tests were
conducted with respect to the analytical model. We did not conduct
validation tests of either the analytical or simulation model with
respect to the error detection process in real programs, although
Naval Tactical Data System program structures and error parameters
were used in some of our studies. Thus, validation tests were limited
to a test of the correctness of our concept of error detection. The
analytical model was used as the standard for comparing simulation
results. Independent appraisals by NADC and NPS personnel have con-
cluded that the analytical model's equations accurately represent the
error detection process as originally conceived. Validation with
respect to actual program error detection processes will be attempted
in future research.

The third area involved using the models to study the relationship
between program structure and error detection properties . Naval
Tactical Data System programs were used for this investigation.

1-2

II. DESCRIPTION OF ERROR SIMULATION PROGRAM
Summary

This program is designed to simulate the error detection process
in a portion of computer software, represented here as a directed
graph. The graph consists of nodes representing merging or branching
points in the software and arcs representing the sequences of instructions
between the nodes. There are no real limitations on the topology of
the graphs which can be handled by the program except that multiple arcs
between the same two nodes are not permitted. If such arcs are desired,
they can be artifically handled by introducing additional dummy nodes
on each of the multiple arcs. The program is currently dimensioned
for thirty nodes. This could easily be changed although some formats
would also have to be modified.

In the specification of the graph, the user can input the length

(number of instructions) of each arc or allow them all to be set

internally to the same length of 10.

The locations of the errors in the graph can also be specified by
the user, or the program can place the errors by a random process.

When this is done random numbers representing the distance between

errors are drawn from the exponential distribution. The errors are

then placed in the arcs corresponding to these randomly selected

instructions .

The MAIN program simulates the process of running an input through

the directed graph. Each input finds all errors on its path in a

single pass. The single input is terminated when it reaches a node

from which no arcs emanate.

II-l

The selection of which arc to follow from a given node is made
randomly (uniform) using IZ as the random number seed. The seed is
used to generate a new random number which serves as the next seed.
The seed IZ is not reset to its initial value when the graph is re-
seeded with errors. Thus the random process IZ continues to run
sequentially until the run ends.

For the graph which is input, the data specifies (among other items)

a) the number of inputs per replication

b) the number of replications per seeding

c) the number of seedings

The main elements of the model are discussed in more detail in the
following sections.

1. error seeding

2. branching

3. error finding

4. data input

5. computations performed

II-2

1. Error Seeding

The user has the option of planting errors in the arcs of the directed
graph or he can allow the program to seed the errors randomly. If the user
chooses to let the program place the errors, he must specify the parameter
MEANER as part of the input data. This parameter is used by the program as
the mean of the distribution which determines the distance between success-
ive errors. It is conveniently interpreted as the mean number of instructions
between errors.

Since the arc lengths and distances between errors are treated
internally as floating point numbers, it is not necessary that arc
lengths be integer, although that is the proper interpretation when the
length is measured by the number of instructions. It may be desirable
to measure length in some other way related to the complexity of the
instructions and the program permits this.

Unless the user specifies the individual arc lengths X(K,J), they
will all be set internally to 10 (line 95) . The random selection of
arc lengths is not a feature of this program but a simple modification
would permit this, if desired. If so, a random number seed (say IY)
would have to be specified above line 95. To avoid correlation with the
other random processes in the program the symbols IX, IW, and IZ should
not be used as the seed.

The random seeding of errors is done in the subroutine SEED.
The arcs of the graph is assumed to be arranged in "natural order"
so that arc ( i, j ) precedes (k,l) if i < k, and arc (i,j) precedes
(i,l) if j < 1. Each arc (i,j) has a specified length X(I,J) and

II-3

it is convenient to think of these lengths as being laid out sequentially
on the real line beginning at the origin.

Using the seed IX, a random number ERl is drawn from the exponential
distribution with mean 1 and rescaled by multiplying it (in floating
point) by the parameter MEANER to yield XER1 . Thus the quantity XER1
is a sample from the exponential distribution whose mean is MEANER.
The quantity XERl is used as the distance from the last seeded error
to the next. A comparison is made to ascertain in which arc the error
should be placed and the process is repeated with a new value of
XERl until the location of the "next" error falls beyond the total
length of all arcs combined. At this point the seeding process is
complete and the SEED subroutine returns control to the main program.

The variables set in SEED and placed in common with the MAIN

program include
/
ISEED(I,J) = The number of errors seeded in the arc ij for

every arc

SVSEED(I,J) = A saved copy of ISEED(I,J)

NINST = total number of instructions

NSEED = total number of errors seeded.
When errors are planted by the user, the subroutine SEED is not called,
and the variables NINST and NSEED are not computed.

II-4

2. Branching

This section discusses the branching mechanism which governs the
path taken by an individual input traversing the directed graph.

Node one is assumed to be the input node to the directed graph and
any node having no arcs leaving it is a terminal node. To preclude
endless cycling, it is necessary that the graph have at least one
terminal node which can be reached from node 1 . Except for node 1
no special ordering of nodes is required. An arc can go from any
node to any node. There is no special significance to an arc which
begins and ends on the same node. Such self-loops may be used to model
repetitive processes which are repeated a variable number of times.
The number of repetitions is not controlled by the user but is
determined by the branching process which randomly selects the next
node in the sequence of nodes encountered by a particular input.

The branching process from a particular node is begun by
counting the number of arcs NUMSUC which emanate from the. current
node designated as NODE. Then using the seed IZ, a random number U
is selected from the uniform distribution on the interval 0 to 1 .
The quantity K = 1 + NUMSUC*U is computed. Note that K can assume
any integer value from 1 to NUMSUC and that these are all equally
likely.

It is convenient to think of the arcs emanating from NODE as being
arranged in natural order as the first, second, third, ..., NUMSUC.
Then the K — arc emanating from NODE is selected as the node to which
the input advances.

II-5

3. Error Finding

The number of errors placed in an arc ij is ISEED(I,J). When the
traversal of a particular arc is simulated by the program, it is
assumed that all errors in that arc are detected by that input and
corrected before subsequent inputs are run. Thus after traversal
of arc ij the variable ISEED(I,J) xs set to 0. The variable SVSEED(I,J)
is available for replacing the original errors when desired.
The total number of errors detected by any input is cumulated and
recorded as NFIND (line 166) .

Other error finding mechanisms are possible and may prove realistic
if sufficient data becomes available to reveal more about the error
finding process. For example, it may be more realistic to assume
that when an arc is traversed its errors are exposed to detection but
may or may not actually be found depending on some random process.
An assumption of this type could be accommodated in this model if
some modifications are made.

II-6

4. Data Input

The required data is described below. Each card or group of cards
is described in a separate section.

(a) MINPUT, NUMOUT, NREPET, MEANER, N. The format is
(515)

MINPUT is the number of different inputs desired within each

replication (dimensioned 50)

NUMOUT is the number of replications within each repetition

NREPET is the number of repetitions or re-seedings. With each

reseeding NUMOUT replications are performed and in each of those

there are MINPUT inputs.

MEANER is the mean distance between seeded errors

N is the number of nodes in the graph (currently dimensioned for

30)

(b) The graph structure is read in as described below. The number
of cards is variable but can not exceed N + 1.

Each card has format of (1615) although typically many fields will
not be used.

The first field identifies a node from which arcs emanate.

The second field gives the number of arcs (< 14) .

The remaining 14 fields (if required) identify the nodes to which
these arcs go.

The above information is repeated for each node from which arcs
emanate .

This section of data is terminated by a card with 99 punched in
columns 4 and 5.

II-7

(c) The following cards are optional. If used, they specify the
arc lengths.

The format is 215, 7(15, F5.0).
The first field identifies the from node.
The second field specifies the number of arcs.
The next fields are used in pairs and have the following
meanings.

first field, identifies a to node,
second field, specifies the arc length.
This section is terminated with a 99 in cols 4 and 5. This card
is not optional .

(d) If the user wishes to plant the errors in arcs of his choice
instead of letting the program seed the errors randomly, the following
cards are used.

The format is (1615) .
Field one specifies a from node

Field two specifies the number of arcs emanating from the node
in which errors are to be planted.

The next fields are used in pairs.

- first in pair, identifies the to node

- second in pair, specifies the number of errors in the arc
just defined

This section is terminated with 99 in cols 4 and 5. (not optional)

(e) The last card is used to specify an output option. The
variable name is MOOT.

The format is (15)

II-8

If a 0 is punched, only summary output is given.

If a 1 is punched, detailed information about the seeding, the
paths, etc is given. This should be used only for small values of the
product NUMOUT * NREPET.

If this product exceeds 25, the program sets MOUT=0 as protection
against extensive output.

II-9

5. Computations Performed by the Program

a. As discussed in section A-l the program simulates MINPUT inputs
for each of NUMOUT replications and the entire process is repeated for
NREPET seedings. This section describes the computation performed in
producing the summary output.
Let i = 1 , . . . , MINPUT
j = 1 , . . . , NUMOUT
k = 1, . . . , NREPET.
x. . = number of errors found on input i, replication j of seeding k.

IJK

For each seeding k a summary is produced giving the average number
of errors found for each input and the standard deviation of the number
of errors found on each input. These are defined as follows:

INPUT NUMBER i

AVE NUMBER ERRORS FOUND

NUMOUT

x . , = ) x . . , /
L«k .*■_ ink NUMOUT

STD DEV

-.1/2

Gi.k

NUMOUT

y (x - x ) /

ijk ' i-k ' (NUMOUT-1)
L 3*1

After all NREPET seedings have been analyzed a summary output is
produced giving the average number of errors found for each input and
the standard deviation of the number of errors found. These quantities
are defined as:

SUMMARY FOR INPUT i

AVERAGE ERRORS FOUND

x

- V

I X-J-4i/ tvnn

i" -I ? ijk (NUMOUT) • (NREPET)
3 k

11-10

STANDARD DEVIATION

l'

-,1/2

y y (x - x ) /

h T ijk i«« ( (NUMOUT) • (NREPET) -1)

] k

b. To assist in relating these computations to the the program, the

following section is included.

for each input i

IFOUND( ) = 7 x. ., for k given
. 13k

v 2
SFOUND( ) = l(x. ) for k given

ijk

CUMSQR( ) = I £(x..,) # the cumulative number of (squared)

kin K

errors found for all replications
and seedings .

SVAVE( ) = I h

k j

ijk/ NUMOUT

TAVE

k {;Xijk/ (NUMOUT). (NREPET)
D k

The quantity a. , the standard deviation is computed using the

following relationships:

— 7

y V (X. ., - x. ) /([NUMOUT) • (NREPET) -1
, i]k i* •

U k

1/2

7 7x.., - (NUMOUT) • (NREPET) x. ]/ (NUMOUT) • (NREPET)
L , ink i"

L ] k

-1 1/2

1)

-, 1/2

[CUMSQR( ) - (NUMOUT) (NREPETK TAVE) "]/ ( (NUMOUTXNREPET)-l!

11-11

III. VALIDATION TESTS

This section describes validation tests of the simulation model; the ana-
lytical model [1] was used as the standard. The test results are preceded
by a brief description of the analytical model. Hypothesis tests were con-
ducted of: (1) mean number of errors seeded, (2) probability of arc traversal
and (3) numbers of arc and path traversals. Tests of mean number of detected
errors were not performed because an efficient method of computing the variance
from the analytical model was not available. The standard deviation of detected
errors was needed to calculate confidence limits. Although the simulation model
computes an estimate of the variance, this calculation could not be used because,

without the analytical model variance, it could not be validated. However, a

t

notable achievement has been the development of an algorithm for computing the
variance of number of errors detected from the analytical model [5] . Work is
proceeding on obtaining a solution in closed form. When a computer program is
available for the closed form solution, validation tests will be conducted of
simulation model mean number of detected errors and the variance.

Analytical Model

The analytical model [1] computes the exptected number of detected

errors for each input. Designating the original expected number of errors

in arc ij as u. ., for the arc between nodes i and j and p. . as the
ID i]

probability of traversing arc ij one or more times, the expected number

of detected errors in arc ij for the first input is U..P. .. The expected

ID 3-D
number of errors remaining in arc ij after the first input is u. . (1-p. .) .

The expected number of errors detected on the second input is y . . (1-p. .)p, ..

th ID ID ID

The expected number of errors detected on the k — input is

e(k) = u. , (1-p. ,)k"V . (1)

iD ID ID

When the expected number of detected errors is added over all arcs, we have

E(k) = J y. . (1-p. .)k_1p. (2)

][j ID ID ID

for the total expected number of detected errors on the k — input. The

initial y . . can be interpreted as the mean number of errors per arc which

XD _

is originally present, in which case the u. . = y. . are equal for all arcs,

ID ID
or as a specified number of errors in each arc. In the latter case, the y. .

_ XD
will be different. When comparing simulation and analytical results, y. .

is used in (1) if the simulation is repeated for a number of seedings and

y. . is used in (1) if only one seeding is used.
ID

III-l

When an actual program is available for analysis, the number of source

statements in an arc s . . and the mean number of source statements between

ID

errors M (obtained from historical module error records) can be used to

obtain the li, . in (2) by the computation v. . = s. ./M. Then (2) becomes
ID ID ID

E(k) - ( I s. . (1-p. .)k_1p. .)/M. (3)

r. ID ID ID

If it is desired to calculate (3) as the fraction of original errors detected,
then (3) is divided by U, the expected number of original errors in a program,
We obtain U <= S/M, where S is the total number of statements in the program.
If the program is a procedure of a larger module, S is the number of state-
ments in the procedure and M is the mean number of errors between statements
of the module. Thus when calculated on a fractional basis, (3) becomes

E(k)/U = ( T s. . (1-p. .)k-1p. .)/S. (4)

A ID ID ID

It is important to use (4) when comparing detected errors from different size
programs, since we would expect to find more errors in larger programs.

The probability of traversing arc ij is computed by multiplying the
probability of reaching node i by the branch probability for arc ij , 1/n,
where n is the number of arcs emanating from node i. The probability of
reaching node i is the sum of the traversal probabilities of arcs which enter
node i.

Navy Tactical Data System (NTDS) program listings were converted to
directed graphs. After constructing the graphs, the numbers of nodes, arcs,
paths and source statements were recorded. Simulation and analytical results
were obtained for 44 procedures in two modules. The data were obtained in
order to compare simulation and analytical results and to analyze complexity

III-2

measures (see Section IV) . Although any values of M could have been used for
these purposes, the values were computed from S/U where S and U were
actual numbers of module source statements and total reported errors, respectively
In the model, the distance between errors refers to statements executed and not
statements on the program listing. M is equal to the model mean distance when
module testing starts (all U errors are present) and all statements are
executed once (S statements) .

Appendix B contains the directed graphs and tables pertaining to the
simulation and analytical solutions for 31 procedures of one module and 13
procedures of a second module of the NTDS . The graphs and tables show numbers
of nodes, arcs, paths and source statements. Simulation and analytical results
are shown for mean number and mean fraction of errors detected and probability
of arc traversal for every arc of every directed graph for a single input.
Simulation results were obtained for 100 repetitions and 100 replications
where a repetition is an error seeding and a replication is a path. One hundred
replications were used for each of 100 repetitions.

Validation Tests

a. Mean Number of Errors Seeded.

Errors are seeded in the simulation model with exponentially distributed
distances (number of source statement) between errors. This is equivalent
to a Poisson distribution of number of errors seeded per arc, with the mean
number seeded being proportional to arc length. The total number of errors

seeded in the directed graph is also Poisson distributed with mean S/M and

1/2
standard deviation (S/M) . Since the sample was N = 100 seedings, the

normal approximation of the Poisson was used. Since the variance is known,

the test statistic:

III-3

1/9

Z = ( X - (S/M))/ (S/MN) , where X is the mean number of errors seeded
over N seedings with M = 21 statements between errors • A two sided test was
used with a = .05. Eight Module 1 NTDS procedures were tested for error
seeding separately and independently of the results shown in Appendix B for
error detection.

H : \i = S/M

H : y j& S/M

Reject H if Izl > 1.96

The results of the hypothesis tests are shown in Table III-l.

TABLE

III-l

Mean Error

Se<

=ding Tests

Procedure

S
10

S/M
.476

X
.550

(5/«,1/2

.690

|z|

8

1.072

14

9

.429

.430

.655

.015

25

3

.381

.400

.617

.308

34

15

.714

.780

.345

.781

39

17

.810

.840

.900

.333

47

12

.571

.680

.756

1.442

48

13

.619

.700

.787

1.0292

53

11

.524

.630

.724

1.464

Although H would be accepted in each of the above tests , the simulation
error seeding was consistently high.

Another test involved a graph with a single input and a single exit node.
The arc joining these nodes had a length of 10 and the parameter MEANER was set
to 1 so that the expected number of seeded errors was 10. The subroutine SEED
was called 1000 times to seed errors in this arc, and the mean number of errors
seeded was 9.995. This test was conducted by running a 1000 inputs through the
graph and since each input traverses the single arc the number of errors found
is the same as the number seeded ( Z = (10 - 9 .9995) / (10 • 1000) / = .00005).

III-4

b. Probability of Arc Traversal

Traversals on a given arc or path are independent and the probability of
traversal is constant on successive trials. The number of traversals in an

arc ij is binomially distributed. The probability of arc traversal is P. .

i

and the relative frequency of traversal obtained from simulation is P . . , so

• i

that E(P. . ) = P. . and V(P. . ) = P. . (1-P. . )/N, where N is the number of
ij id ID id xd

independent trails (100 replications x 100 repetitions = 10,000 trials). Since
a normal approximation can be used when N is this large and the variance is
known, the test statistic

2 - (/■■ ~ P.J/fP. • (1-P. .)NJ1/2
I id iy \. id id

was employed for a two sided test with a = .05. Eight procedures listed in
Appendix B (different procedures than used in seeding tests) were randomly
selected. A branch node of each of the eight procedures and its outgoing arcs
were also randomly selected.

Hn : U = P . .

0 ID

H : y ? P. .

1 ID

Reject H if jzl > 1.96

0 ' '

The results of the hypothesis tests are shown in Table III-2. The hypothesis

H would be accepted in each case. Simulation and analytical results are close,

as can be seen by examining Appendix B.

III-5

TABLE III-2

Probability of Arc Traversal Tests

Module/

Procedure

Arc

1/28

4,5

1/28

4,6

1/29

2 / 3

1/29

2,6

1/44

5,6

1/44

5,k

1/49

4,5

1/49

4,8

1/60

6,7

1/60

6,17

2/23

2,3

2/23

2,4

2/48

5,6

2/48

5,7

2/86

5,12

2/86

5,20

P. .

J-3

P. .

.1256

.1250

.1235

.1250

.5014

.5000

.4986

.5000

.2458

.2500

.2419

.2500

.1260

.1250

.1232

.1250

.1225

.1250

.1213

.1250

.4947

.5000

.5053

.5000

.1369

.1875

.1850

.1875

.2524

.2500

.2472

.2500

((P. .) (1-P. .))

.331
.331
.500
.500
.433
.433
.331
.331
.331
.331
.500
.500
.390
.390
.433
.433

1/2

.181

.453

.280

.280

.970

1

.871

.302

.544

.755

1

.118

1

.060

1

.060

.154

.641

.554

.647

III-6

c. Numbers of Arc and Path Traversals

The branching mechanism was tested by including in the program a traversal
counter which records the number of times each arc is traversed during a program
run. The correct functioning of the counter was confirmed by obtaining detailed
output (MOUT = 1) for several different graphs and manually confirming that
the count corresponded to the detailed output.

Several runs were made to test the actual traversal count against the expected
number. Two specific tests are reported below:

1. The graph with a single input node connected to each of 4 terminal nodes
was used in a run with 1 input, 4000 replications, and 1 seeding. The expected
number of traversals on each arc is 1000, and the traversal counter showed 994,
1004, 1006, 996 as the observed frequencies. These values easily pass a chi square
test at the 99% confidence level (x2 -=.104, x2 = 11.34).

2. A second test used a graph with node 1 connected to nodes 2 and 3, node 3

connected to nodes 4 and 5, and node 5 connected to nodes 6 and 7. In addition

10 inputs were used to test if the branching mechanism works for multiple inputs.

The test used 100 replications and 2 seedings. The graph has a total of four

paths from input to termination. The expected number of traversals for the path

terminating at each node is shown below along with the actual number of traversals

produced in this test. These values also pass the chi square test at the 99%

confidence level (x2 = .419, x2 = 11-34).

3, .99

path ending at 2 4 6

expected traversals 1000 500 250 250
actual traversals 1011 491 253 245

III-7

IV. ANALYSIS OF COMPLEXITY

One objective of the research was to identify complexity measures which
could be used to estimate the difficulty of detecting errors in a program.
If these measures could be identified, they would prove useful in program
design and testing. Complexity measures would be used during program design
to avoid structures which are difficult to test and during testing to allocate
resources to testing on the basis of estimated difficulty of error detection.

Four complexity measures were evaluated: numbers of nodes (Nn) , arcs, (Ma),
paths (Np) and source statements (S) . A brief explanation will be given of
the significance of these measures as indices of difficulty of error detection.
These measures were developed for 31 procedures of one MTDS module and 13 pro-
cedures of another NTDS module. A procedure is a subset of a module.

Nodes'

Nodes can be categorized as follows :

a. Start. Signifies program beginning. No entry and one or more exits.

b. Terminal . Signifies program end. One or more entries and no exit.

c. Branch. Single entry and multiple exits.

d. Merge. Multiple entries and single exit.

e. Merge and Branch. Multiple entries and exits.

f. Transfer. Single entry and exit. Commonly used to signify a call

to a sub-procedure and to indicate the return point in the calling procedure.

g. Dummy. A special case of f. An artificial node in the simulation
for handling parallel arcs.

h. Transient. Nodes which delineate the beginning and ending of
sub-procedures .

IV-1

As compared to a structure with a start node, terminal node and one arc
connecting the two, the addition of nodes in categories c, d, and e will add
to the number of paths and decrease the probability of reaching certain arcs.
Thus, error detection is affected. Transfer nodes do not affect the structure
of a program, but do add to its complexity because these nodes correspond to
a point of transfer of control to a sub-procedure and a return to the calling
procedure. Transient nodes were not counted in Nn because transient nodes
are part of a sub-procedure; however, the transient nodes were necessary in
order to complete certain paths in the directed graph. Dummy nodes were not
counted as part of Nn because they were used only to specify a directed
graph in the model and did not contribute to program complexity. All other
nodes were counted. It would be useful in future work to develop an additional
measure consisting only of nodes involving branching, since the presence of
these nodes may cause the probabilities of arc traversal in the outgoing arcs
to be less than the probabilities in incoming arcs, thus increasing the
difficulty of error detection in paths which contain the outgoing arcs.

Arcs

Transient arcs are arcs contained in sub-procedures. These arcs were not
counted in Na. However, these arcs were needed to complete certain paths in
the directed graphs. An entire sub-procedure was represented by two nodes
(start and end nodes) and one arc. This was done because it was infeasible
to represent in the model an entire module of approximately 2000 source
statements and many interconnected procedures. Secondly, the point of view
was adopted that sub-procedures called by procedures have been checked out
and any errors detected reside in the main procedure. Thus the sub-procedure

IV- 2

was treated as a zero source statement (no errors were seeded) arc. This
treatment corresponds to viewing the test of a procedure as a unit test
in which it is assumed that interacting units (sub-procedures) are working;
the focus is on finding errors in the main procedure. An important facet
of testing is the integration test in which the focus is on the inter-
actions between units. The model could be employed in this vein by conceiving
of each procedure as an arc and the nodes as branch points to entire
procedures. It was not necessary to depict transient nodes and arcs, since
these components do not affect the error finding mechanism in the
model. However, it was considered important to document the actual program
structure rather than the structure required by the model.

Dummy arcs were not counted in Na because they were used only to
represent parallel arcs in the model and did not contribute to program
complexity.

An increase in the number of arcs increases the number of paths and,
hence, makes error finding more difficult.

Paths

We define a path as a series of connected nodes and arcs which begins
with a start node and ends with a terminal node. A definitional problem
arises in the case of paths which contain cycles. A graph containing
cycles has an infinite number of paths. However, for our purposes,
traversals in cycles were counted the minimum number of times. A cycle
contained in a path was traversed one time. This treatment of paths is
consistent with the model assumption that all errors in an arc are detected
on the first traversal. Cycles in the model do not represent DO loops
in a program, where the program is forced to iterate in a loop a

IV- 3

specified number of times. Rather, a cycle contains nodes and arcs which
may be revisited.

As the number of paths in a program increases, error finding becomes
more difficult because the number of areas in the program which must be
searched increases. It should be noted that number of paths is not
independent of number of nodes and arcs; number of paths is a function
of number of nodes and arcs.

Source Statements

The number of source statements S will affect error detection in
the model because an assumption of the model is that the number of original
errors in a program is proportional to the number of source statements.
Based on this assumption, error detection would increase as program size
increases, all other factors (number of paths) being equal. In order to
not mask the effect of other factors, the number of errors detected on
the first input E(l) , as a fraction of the original number of errors U,
is used instead of E(l). The relationship between error detection and S
is complex because error detection depends on both U (a function of S)
and structural properties (paths) .

Structural properties are not independent of number of source statements
Since few programs are written as one line of code or a single arc, the
number of nodes, arcs and paths will, in general, increase with number of
source statements.

Analysis of Complexity Measures

Values of Nn, Na, Np, S and E(l)/U (analytical solution) are
tabulated in Table IV- 1. Plots of E(l)/U versus Nn, Na, Np and S

IV-4

are shown in Figures IV- 1 to IV-4, respectively. Points are plotted for
both Module 1 and Module 2. Since the data were shown to be highly non-
linear when plotted on a linear scale, the data were plotted first on
semi-log and then on log- log scales (Figures IV- 1 to IV-4) to see whether
a straight line would emerge indicative of a non-linear relationship.
As seen in the figures, the data are still scattered on a log-log scale.
In many cases there are multiple values of errors detected for a given
value of complexity. This result suggests that error detection is a
function of multiple complexity measures. However, lack of independence
among variables makes the identification of a multi-variate relationship
difficult. Other measures, such as path length, connectivity and
reachability, may prove more illuminating as indices of error detection.

In order to more clearly indicate the relationship between error
detection and a single complexity measure, multiple values of E(l)/U
were averaged (for three or more values) and plotted in Figures IV- 5
and IV-6 for paths and nodes, respectively. These curves provide a
better indication of the inverse relationship between error detection
and complexity. However, the reduced sample which results from averaging
is inadequate for fitting an equation to the data.

IV-5

TABLE

IV-1

COMPLEXITY

MEASURES

Module/

Procedure

Nn

Na

Np

S

E(l)/U

1/2

12

21

26

37

.1700

1/8

8

11

3

10

.6000

1/11

6

7

3

8

.5938

1/14

4

5

4

9

.7222

1/19

17

25

7

22

.3295

1/22

18

26

11

30

.3458

1/25

8

10

2

8

.6875

1/28

12

16

4

24

.6145

1/29

20

28

13

47

.6463

1/30

7

10

5

10

.3563

1/34

11

15

3

15

.9167

1/35

12

16

3

11

.8636

1/36

17

24

3

31

.4032

1/39

15

24

10

17

.3526

1/44

15

24

7

21

.4256

1/47

12

16

4

12

.7500

1/48

14

21

7

13

.6538

1/49

13

19

7

19

.2829

1/53

11

18

9

11

.4531

1/57

22

31

12

26

.2726

1/60

22

34

16

24

.3317

1/7 5

17

24

8

20

.6800

1/76

13

18

5

19

.4803

1/77

10

16

9

10

.6000

1/79

19

28

3

23

.3804

1/81

6

8

3

7

.5000

1/87

14

20

6

25

.4700

1/91

18

28

9

14

.2514

1/92

4

5

3

9

.4444

1/93

23

33

12

34

.2289

1/95

16

26

10

19

.2325

IV- 6

TABLE IV- 1 (cont'd)
COMPLEXITY MEASURES

Module/

Procedure

Nn

Na

Np

S

E(l)/U

2/15

9

12

5

10

.47 50

2/23

8

10

3

12

.6667

2/41

9

13

12

13

.5192

2/46

23

32

18

32

.3212

2/47

22

34

36

33

.2060

2/48

12

18

14

17

.4651

2/79

9

12

5

11

.5455

2/86

20

29

6

33

.3775

2/90

11

17

8

23

.2446

2/99

19

27

10

23

.4620

2/122

12

18

6

20

.4313

2/137

10

15

11

23

.3505

2/149

16

24

9

35

.3964

Legend

Nn: number of nodes, with dummy nodes (nodes associated with dummy

parallel arcs) and transient nodes (nodes associated with called
procedures) eliminated.

Na: number of arcs, with dummy arcs and transient arcs (arcs
associated with called procedures) eliminated.

Np: number of paths, with paths involving cycles counted minimum
number of times.

S: number of source language statements.

E(l)/U: expected fraction errors detected on first imput obtained with
analytical model.

IV- 7

IV-8

en «

N =
IN H

Jo u

< N 3

J N

2C

Mil 1 1 1 1 | ; ,

• . ;

::[;:;: i±fct

• : . :

; , ■ ■ — tr

^ rnr

: •: :

-

^— '- '■ '• • ■ ~

« IT

■ ,

1 -_

— —

1

1 ■ i

, , ■ i

^ir m~t

^n: , ; , l:ZZ

:::: .::

:: m:. :::~:

-Hrr

i

1 1 1 1 ff

^^i

^—~

Vn~

^~

, . i 1

1 , ! — ' —

MM

1

.:: jtt

^H

1

—\ — 1 —

'

~-~~^

t|

, i . ,

. ,

Mil

1 | !
— i— — —

' ' — ^ -~

~~~~ TT

— \

tt~

— t—

-f-

-hhtt

JliL

i i 1

i 1 ! i

'

i

H

~ t

.If--— U-

1 1 1 1

3=^

i — i —

. .- u

, LjJJ

-^P

. . .

(__ —

....

MM

i . . ■

,

— —

•

"IBriti:

"±ZZZ±E

1 1
1 1

■tf

—\ — r— r ■

II

j |||.|

1 ' ' '

T+_

llj |

iii.

i j 1 ;

' |H

in "

1 1

:

li

1 ! 1

1

1

III

,i,

_

:

HI 1 1 1

.

i

Ili M i!!

lln I

i ! • ! ;
1 I'll

ii '

i

1 1 ■ ;

lj; *

|

in:: ■ fflf

III' ;

1

i

1 1

1 M

:

ii

'

t^-Xl

! 1 i

i

j |

;

1 ■

ML ._ I .

ESI

i ■

i

| |

i

ill

. :

.:' |l!:

J-Lj-J — I— l—L-i— .

.,..-.—

i

——

Jiii

m

3

4-J-i — H+

^^^~

— r

^¥ Yi

XJ — i 1 2

Ijl i

1 '■ , *" ' ; i i

1 1 1 1

ftti ' '

— —

■

- . :i

mm

— —

& -. zz =

- -.;-

3

=;

—;

r^

|Sr li!

rr— -, 3

i— o <b 1 ,

Z^Z^l

_

M

:::

4— jj-j-L

I

' .j,— ll J, 1 1

'ill

||j.|

; ' ,

^__i

'.D, , vJJ i •J

tl —

— J —

— M

— 1 — . .

OJ1 & III

' ■ " ■

■fi

1 —

1

; cm ■ :

J 1 — 1

XJ 7

» 1 1 1

li Mi

',

- ..CJL

UJ —

-H-l — i ' ■

M

u

i:;. |||!

1 |

^

>": 1 '

cm . c,

Q i

IN™

,;! i!|

'l*'

M | B

* A

"

Oi '

Mi

I M U-J

-\

Hi d

3

<

^

|d *■

1 Hi

U r

I JrJ I -

^ 1
.» i

,

*Jd

i

jf Jill

tt

,

Pi i b

3 1

1 "

!

1

! il,

<

■ ; *

■ , j

:ui v-

(TJI

;

■

— : *rH

— ^

^F==4

• :'

(D ' h

FT" 3 """

— j- —

~1

- — J

— . — i — __^

i li

«

r

+"'! V_l

U. 4f U

nil rn •s1

jBt=F

ipi

U

■■ill

11

■

_

j 1 — Lp.

i

; .',:■,'

...... ... ,

— +—

1— I!

■ nr ■

31 !

I

| 1 1 :'i

0"!

I n;l

■-+

,

!— j

jffiffi

i ili

ll I! ' 111

MM

! l!

ill; | lj

,;,. li

ii

1 i
I I

1 ■■

j ; ; 1

i
j | !

Nil

--—L-i

ii i

!

;

■

j

1

Tt

| |

™:n^

^^—

EttF

T^™

'■ill, '

— S

fffn1

■j — *^

tttt

•--

::::

1 ' | '

I ; ' ;

]

n/(i)a

O. 00 N O to

,_' o oo iv <o m

co

IV- 9

:::

[ —

pa

till

5H£

Ej

* '

w

-:.

=

.....

_| ,

-

_L_.

n

—

-444"

^— ■

— < — ! — i — 1 —

~ H — : — ' — 1

^_

-r—

—

■[jit-

...

n

m

. {J

- — 1

II

tt-i-

-j— | — i — | —
| 1

: | i

Ilk

— i

P)

__

U|i

—-

_~_ —

— j — | — | — | — '

tti

~— ^

4-_r

" ' '

1 , —

1

L

1 ' I ,

i

'II

1

III

l '

1 I >

i! r'

III

CN

1 ll

M

i |

l!i

I'l

1 r ,

.. _,

— A

,

1 ■ | [

i 1 tO

i

M

LLL

!

T<

|l

1

! ^

! j

fQ

i ■

CO

!

1

z

1 ' j 1

p

y

w

II

Ml

o

1

jf "It

o>

-

ME

"i

....

1 ! ~~

'li'11 i

O 0'

-4—1 — j — 1 —

flE

#£

; ' ' 1 i

-tfU-U

ftfj"

1 1 i

+H+

-j-j-p

r^—

, : .. ,

<=0

— —

. ■

— \~

i — ,_ — | —

rr| j U

- —

—

-«

1

i

| —

— ffl — o-

U^—

- . I

i 1 1

i ■ ■ ■

i-J-H —

— .

:.:

=;r

^=

-^

—

Lj —

.■;_::;'

i 1 '

-LL XX : —

:

-

i

=r^rj '5

«0

:-::

rrr*

"=r

-

1 —
— x— 1

~~1

=J

B^=E

a a

=^

■■■

m

7^

.

-

j ' ' j

IO

■

-

—

=53

— 3— ■

— s 1

4-4-1-

1-

~rrq

-U_

■ ■ 1

l

O

T

. .

— — i i —

-40-

lj

. „. ■

. <

,

— -j-j-

— hr

— +—

— i4_

. : M ' i —

r^"

rp>«-

T—

1

o

— — 1

—

- —

1

CO

r*

iiij.

■ i

, Y

v,

tN

n V

*

•H —

l| 1

f!

LJ 1 M

r~i

w

c*

1) "*■"

- ,

~W~

W '-*

U -P

R"

" '

fa P

rH

a

.

r

1

'

13 C

cu

'

Q) H

r-j

1

^.

■

;

0 ■ 1 '

3

73 i

"•fi;.

vi

a) w

0

M

j ! i !

,

a,, h
-* — -±

s

-*— -

i •

O

j __i

i_

__

E^E

__,

^S

_

SsS

—

o>

: v:

~~

___

,',,

"-. : ::_:

--. : 1

, '

||| ;

J h4h

, , 1 j j

I'. |

—

■-

■1.

r^J

II 1

l*i ' !

II

iv

!

H-1,

— --

-■..

:.■■

:

1.:--

' h~

— —

r- ^

J2— —

-" :

-

-0

Y-l

-

, , ,

—

P

— :

--:-

X

;■ ■ ■ —

T- 7"

^^

~-

T

1 1 1 1

i | . i

, .

l+rl

' . ' ' '

|

— -.-

' i 1

" -•-- -

- — -

trffti-

'

i

-> '

! '

O

i

' 1

rs

....j.,.

!M

1 1

i

• ■ ;

I1!

...

1

I

li1!

]

ml

' '

T -

1 |

=

~

— —

-

Ml

Si

::::

—

5e

a

m

- : ^

J-L. -L . — —

. . r

fffl '

I . . |

CO

JILL

iliJ

-i—

_,...

LXLJ

1 ' ', '

■"■

ai=

■

l—

1 ' ' 1

rv

o a n 4 m

CN

n/ ( I ) 3 a

,j o oo r*. -o >o V

en <
co .>

CJ =

N E

u u)

S3

_ u

< rj

o*

[iiLi.|[||||iiin:

1 |||||||||]i||||| ll1!1'11!

c

IV-

10

1 — IKVIIIIII

l!P:^:

#4ff¥%N

1 I' 1 ' 1

— 1 — 1 — 1 — I — 444-1- 44-M- -

....

^—^44

it 1 1 1 1

1 1 — —

1

1 i i ' i I

1 i '| 1 i ' 1 1

jiii iii' . i

— "*7T — r'" "' — *"**"

!l|IJM|j ; i |=

1 1 1 i

TTTTTtTm

■-"

"*"T7*

1111

■ '

;::: :.^rtrz::

1 ! ■ ■

_J — LJ — 1 — lllilllL

^^+U^:-L

-

1 n

— 1 ' ' 1

1 [T

. |~l-i~l

!

— ' 1-

Cr_r :.::

— „_|.„._ — _„^

trrr 1-1 1 1 III

1 i 1 1

; 1 ' |^^~-

I11 III 11

.. . .

-■-

fnf4i

-{-*-■■ 1 i

1 1 ' 1

I'll

T-t-v- i i ■ ! 1 M !

■ ! 1 1 —

_4 , j ]

1 ' ; ; \m ■

Jffl !'

i#

1 ! I ;

-J— I — 1 — j —

iii ! \ ) '<

III: ' !

1 1

1 ! '

1 1 j

H ' 1 ^ '

1 j j ||; '"1

I i , 1 1

! ! ! 1,

i 1 ; 1

1

■ 1

I 1

1, ' 1 1 !'■

l! 1 !

1: '

|l !

nr.jr: .ttr

I

:if:|tt;nj::n:trr

i; ! ,

1

,

I

1 [

,

i1 1

'

1 1

t-— — 4

"j

T

1114IU4.

I

Mil-

I....-..I

lil!

1 ■

jt

\ ;

fll

1 i ,

||i!f

illjjlj

2;

l||il

=^Hr^

*~

fflffiBS:

-r-r.- ~r7Tl"~"r. ~ - ~r~ t~— :

rr '• ' ■ Pffl:

— ^=^p

□

O" 1 " " ~

;" i 1 ;

4tf

= b1JsEE|eJSSEEESE;

1

— jl 1 — ■ ■ H1JE

z^^. ,; !.; j, z£a

■

Ii

He^

^^

r~~ ^ , . ~

^se=^==2=;

— 3 , -*r Bj± — :

H» " " ; '

Ijl j 1 | | Iii

i— ii

i , , 1 1

III

. ■ , '

\ '•

1— . — tj — ffl— — . — 1 — , __^_i_i--

! 1 ' I 1

Bl )"

„^+^._^+^-^.^w^- 1 j ; , -

j ; — 1 — '—4

ffff frfr fftfi

i,i [ | j | | j | i j { j j 1 1 j 1 |||]

j : I i j

— — Hi — , — — ■ — <=i , TTTT'tl — ~"

}| j

S — ii ■ | — 0 ■;'

r,i »+) ifl ' 1

m i | li|

> 0 ! in

n -f s 'i1 '

III !| ||l

n" 1 1

u ■ 1

"'^ "T rS

1 1 I

: ffl

1 ! ; i 1 1 nil

+j cfi ■ Ml 'I

Ml 1 ;|

III 1

LIE.

i nil

Ii ' :

0 Y

1 m

|l

Iji;

Et

< ! nil ]• 1 hi ||

fa

1 ' ,'■

•

II

_..

1-4 -UJ

t

I1 l! ' :!; jl

^ 1 i; 1 i 1 I Nil

■ :

Ml'

^nn^-.

<rt ■ F< QJ j j [Ii

V :

! Ijjl

m :

QJ ; tf i rH

III j 1

1 ,

lip

^r^mp"7 HE =====!

=±== ■ 1

Hi,3 1 1 ll

g 1 f 1 'pi

_^^

— n

] J*i.

» ,

= 31^= =

— ={

,„,'..;,

^__ __

(V*J

1

lillliiii=

|I=^|=3==|=E

EJp

^TfJTw

t~Tr

. ™:

— ; j | ' ~

==F

=^===

— r — = - — -:

^=~"^=^^=

, ' -H

1 1 , ' ■ i '

1 H I— i — ' —

1 f.

— ^ — L^^ — n —

<-f—

hH 1

| | | j |

1 ! 1 L* 1 Ili

1 !■ ' ! 1

1 1

! 1 ',

|| lil1

■

U :, i:: ffl ' ' i

1 1 : ! ; II

i : ; i ; ':

III

1

III

: ' ' I

|fl • ' ttfl 1

III | 1 : 1 !

r

11 11 |

!'|i

■

IE-it

;

_j 1! Ill

i| MM

I

1 !

,

ili ii ' 'ij :

i

■

li

; ;!

J 1

m t^4^

III '

i j

M.jl

1
-Li— L 4-

i

IT S

, , , 1

^r=prpr;::- 7, a=n:

Q N

1 1

ffi

1 ;

I I I I I

1 n/,(i)a

oo k^ *n in

h+— — 1 I 1 I

^4—

■■"r —

1 ' ' | ' i

i i > ■

1

;

.:::

i '

1 '

• • • -1

—>•-••■

1 ■ i ■ | ' ' ■ ■

ill

. 1 . 1 i

~H — ' — ; — ! —

T~~

i ; 1 '

r*-

—*-

1 1 | |

r—

; 1 —

' '

I llli'j!

lllllfj \

■ ' i ■

4ftT

rt

CO

-j-f-j-j- -H-H-

__

4i — 1~~

4+44-

. , ;

— i — i — | — : —

— | — ! — ! — 1 —

t*"^

!"1

! ! I ;

•

■-'

4-r-

| ■ ' '

....

|

I

—

1

1

1 1 1 1

! ! 1 :

Nil

! : 1 '

i i

|||l 1 1 1 1

I ! !

1

1 ' 1

; ! ' '

|l

1 ! 1

1 1

!■

1 | <u

, !

■

i

.

O

i

d

'

3

: j

i

li!

ii

o

i

~S

1 :

. ..

■ '

T

: ,

i4

1 !

i! \\\

,

tjtt

1 |

: 1
m

- —

' '

^=5r^

SH^

i=

EEli

o

"" " ;"===

■

_ _ ; _ _

~~~=Z

^=r

==

: : ' ■

g

~

:..:

ftp:

==

O

: ...

■■

~—

- — — — — —

■ '^ i,

1

in—

III

E TT

i ]

i

I]

, , — UJ

.

i

j

4]j}-m-j-

— r-

— M-l

— !

t— -

iM — ,

; : ■•

—

i ' , j

;

- — -o— Q

as

— ^— —

===

:';

•o

r3

p~

==:

, .

(N

: :

r —

=

- -■-- ■' J- ■ ' ■ '

« 1

-

J

J) i

t— !

— —

„..,!.. .

' Ll ,n

1-

m rr

1' i

■* i.

«l II*

]

i

U > i—l i

>

,1 ! 1 1 A

—

i i i

m

J

iH/t- +i rr-1

"VT "O

a H 0

ci >1

+i >

nJ

1

2-1- x

1 •'

^^

■H

r*

4J uj

U'-P

i ! :

td .

| . ■

-j.

Vl J-j .

Em 7) ffi ■— i

CL-P " "

■ ' - ■-■ ■— ■

1

|||

:T)iq C QJ

...

jjjj

Zj

1 <u i-f d) H ;

j 1

■

1 +> ' E T3!
U ■+) CD r^

AJ '

t

=^^^

==

..■

:::"

~rr~

' <U u|i -w o

* : :

*.

z.

: ' ; ' ; : ' .

=£=

1 ■ =

^rrt:

1 '

r»r—

'

1

=^E

1

co

1

:

1

•s

ill

— — H : —

j » - ..,

1 T • ! T ■

—4- . ).- - ........

1 ■ ■ ■ j ■ ■ --

■J j

1

1 ,

> |

•0

^=ESE

HHf

_

Hi

^

_^ —

!

r_ .:

p

• l ■

■ '. i i

^ -iki—l ■

5=

£E5

- ■ ■

^

T

-~T—

1 ' i

! —

— — —

! 1

— <

— i —

JJ L J h— |

Xi

— | !—

1 1 1 ^ 1 1 ' <—

'■*-- ■■' ■ 1

+i — -

—

1

' ' '

n

u ,

'

r*

1 1 : ■

j': ' !•

i1

....

L ,__l

i|.

1 1 ■

i

1 \\[

■

"

It- ! '

||l

~T"

1 |

: '

=====

____

>

;=

::r:

__"P —

-

7™r

■

oa

i

(rrdrrr

■ffW-

— — ! ■ 1 1 ■

1 :

: ,1

1

— i

n/(T)a

_ » oo s 4 m

CN

wm

....

■

r-^-4- ; I : !

IV-

— 1 1

12

rlrri

liiiJ

:■::

_

:::r

:::ii: , : ' i : :

^ III 1 1 [~

-

■ ■ i

... ...........

........ ..___.

........

i — r

4-1 -H

t -

— I — i — i

44-

1 i

1 1 Tt

| 1 *.

— — t — Tl
1 1 H

ftTT^
11 1 ' ! '

Jul

1 ' 1

±T-r-

1

fir

...

::::

i : ' '

Of| II i1

4- | i ! i : !

iii

— L

.... :.._. mi

. ..

-H

4-+-T-

| I ! — —

,

l !

. : , .

LLJii

<U-+-

....

• c:.

,

-~-p— — — &

*~

11(^1111

Pi=#

1 ' 1

| | — — '

—

-

— —

j _. .

w

J ■ '

"rt'

—

^_^J-4M

rf 1 1 i 1 ' ' ' '

Til T—

,,,,

-£

J —

uu

nt; i

T-'ll 1 ' '

4—1—1 — 1 — |

i — 1 —

_..,

+ 4-H — '

1 III, If

n i. . i

....

U~^4^ — f—

•^Ml| I'l

. i

1XJ

T

: M

i

i

;•

Ml -

J

M ■ '

i Ul

:. ;:" '

! Mil III

' !

III1'

i

S"-,

r*r-

! ! i

i i

L

i!i '1 M 'O

UJ

|| c

MC-^^

1 i MM

^

■j, . ,

u

111

in

' B

1 1

1 i

1

V

j_:::::

■ TTT -* t I ;t3

....

'' ! ' ! '

1 !

. ..

'

J

Til

IL

^_zi:::

— t- : ^'

■■ m ; :<1)

M

1

, .

Ji ;

5l.

ft

ii. i

^0

W

Ilk

i

;

J

rt

:

J

(1)

1

:

1 ! i

1

Oi M

H

tf

■TTT " '" W
(1)

O

m

a-

3^

I 1 !i 1

i

0

-,..

<1

P
— «-

^~=

= — z==:

ill H

:._!i-L

||3|||| fbfffi

r'ji1.. i tJ|:
|'fi|l J rt' ' '

-r I ' I ■ . ! '

: : I

1 1 1 1 [ +T

1 . i |

' <-c

r — r

u-r-r.

■i: . :

Li*

■fMeKB

— "1 — g

— - — N —

_

\=

■H-::3

---JtUi

:r : -rrr~r. Til.: : : . :r^=

,; ; , ; "H

f- -

p&9

:.. j — nji —

T:. 1 , : : ', _| .:
r — |rTr~ E rH i ,
- -if} ["-

— — ==

i

7— -^— — U — ^
- fff+44-Hf

ffijl

;■£}■■;. -J~ CIp =

__ _

1

ii— i— '

itffli

J---.

Mh — f

r .| ^

UJ i

r4r

i U i -V "5'1

' — ' ' ! ' Tl

'i ,

-t' : '[

till

i

IIIIIKIi : ^'11

— - — | • ^~—

— — i — ■ —

l| . , , ; i . PQ

Ph

H: J 2.

tP;

rr : ~ —

ir e

1U

i

i

......... <^J

i

1 H I

'III' ' l|

. 1

"Drl" He

j ,

ii

III

Hi

— -H ' ■ f ]

— W-

fi — r~*~li

l — . — . , ■ 1J

j1 ' '.

rffl

^g)^^ '

—vt

^

■

LO

QJ

* "■*

: i

,

■ri '

BH

- r

r^-

«--; K"

| , . ' ,

i ' 1 i! ; ' I ' i n;

■Uii

ha 1 31 1

i | i i |

j

; ' i tr

-+—

<. .

r

i1

ai . , . i .

4 '

\

ft

' Ira

— <

' 3" s

■ - ■[

q. . f

n

li

fC^u

' i '

i

'

1 !

II II 1 1

lii

! j

i ! ' ' i : I

Mil

1

i i;

|

1 IIH i I

.

UJ

M

.^i^n

ii

i

V

rri

1 |P| : : M

i ii

TTTT 1 1 f '—

0

I !

— ■ — — - —

::.:

— •—

s —

1 =

, . i

— 1-=-~ — —

1 —

— :

-*—

| —

— —

• i II

1 IF

H

— *r : —

_ =

E

li :

_u

- . .

__

r=r ;^r -— - — — _:

::-;;

__

gp|!H

H-f4

___J — __

— — rCTT*

....

-

In

m , , , |

II . 1

1. .

1 ' ' ' ' ,

I

, ■, ■ i i ; \

1 '

II

||

||] ill]

nil

i

i MM I'll

,

'

;'' m r

: 1

1

I'll I |

1 :! ■ ' 1 :

MMIu

1 , !

i H

MM

! i

_

tt:::::i:i

l

1 |

-tl

'

I 1

11

:

i '

II II

Li —

!

^T^rr^r^r

ttt- ;■ ' ; ■

n/(i)a

r*. m t^ ^n is\

_ ^ oo n o m

C4

V. SUMMARY

This report covered the following areas:

. Description of the modified error simulation model
. Validation tests of the simulation model
. Analysis of program complexity measures

A description of the revised simulation model was presented in Section

II. The data input format was described in Section II-4. A flowchart
appears in Appendix A.

Validation tests on the simulation model were described in Section

III. Some of the tests used data shown in Appendix B. These data show:
directed graphs, properties of the directed graphs, simulation solutions
and analytical solutions for 44 NTDS procedures. Validation tests were
conducted for error seeding and arc/path traversal. All hypothesis
(validation) tests were passed. However, simulation results were
consistently higher than analytical results.

Program complexity measures were analyzed in Section IV. Four
complexity measures — numbers of nodes, arcs, paths and source statements --
were plotted against fraction expected detected errors obtained from the
analytical solution. The data were obtained from the NTDS procedures of
Appendix B. Although the direction of the plots (error detection inversely
related to complexity measures) was as expected, considerable variability in
the data were exhibited. The variability indicated error detection was a
function of several complexity measures instead of one. There were multiple
values of error detection for many values of complexity measure. When these
values were averaged the effect of a single complexity measure became

V-l

clearer. However, the reduced sample size made quantitative analysis
infeasible. Although the four factors are potentially useful as measures
of complexity, no single factor stood out as being a major determinant of
error detection.

V-2

REFERENCES

[1] G. H. Bradley, G. T. Howard, N. F. Schneidewind, T. F. Green, and

G. W. Montgomery, "System Test Methodology," Vol. 1, Naval Postgraduate
School, NPS55Ss75072A and Vol. II, NPS55Ss75072B, July 1975.

[2] G. H. Bradley, T. F. Green, G. T. Howard and N. F. Schneidewind,
"Structure and Error Detection in Computer Software," Proceedings
AIIE Conference, pp. 54-59, 1975.

[3] N. F. Schneidewind and T. F. Green, "Simulation of Error Detection in
Computer Programs , " Proceedings of the Symposium on the Simulation of
Computer Systems, National Bureau of Standards, pp. 101-105, 1975.

[4] T. F. Green, N. F. Schneidewind, G. T. Howard, and T. Pariseau, "Program
Structures, Complexity and Error Characteristics," Proceedings of the
Computer Engineering Conference, Microwave Research Institute, Polytechnic
Institute of New York, 1976.

[5] S. Litwin and R. J. Pariseau, "Variance of the Number of Errors Detected
During a Set of Random Passes Through an Error Laden Graph," Naval Air
Development Center Technical Memorandum, 52TM 76-STS-001, 6 April 1976.

R-l

APPENDIX A

FLOW CHART FOR ERROR

SIMULATION PROGRAM (MAIN) ,
AND SUBROUTINE (SEED)

A-l

JL

Read input: MINPUT, NUMOUT, NREPET, MEANER, N

1L

Initialize: NUMPTS(I)=I for 1=1,..., N

X(I,J)=0.

for

I,J=1,.

,. ,N

NTRAV(I,J)=0

for

I,J=1,.

.. ,N

NODES (I, J)=0

for

I,J=1,.

• ,N

ISEED(I,J)=0

for

I,J=1,.

• ,N

SVSEED(I ,J)=0

for

I,J-1,.

. ,N

i.

If next data card is 99, continue;

otherwise read graph description from data cards

let ISW1=0
1

If next data card is 99, continue;

otherwise read arc lengths from data cards and

set ISW1=1

I Set ISW2=0

If next data card is 99, continue;
otherwise read the number of errors in each
arc from the data cards and set ISW2=1

V

Read input: MOUT

L-2

0

NIX=NUMOUT*NREPET

If NIX > 2, set MOUT=0

CALL OVFLOW

(required for random number generator)

/

If ISW1=1, the arc lengths were

input by the user. Continue.

Otherwise set X(I,J)=10. for all I,J=1,.

• ,N

and write output:

"ALL ARC LENGTHS SET BY PROGRAM TO 10"

J.

II

Select initial values for
random number generators

IX=
IW=
IZ=

(any integer between 1 and 2147483647)

A- 3

IREPET=0

(counter for number of seedings

'

CUMSQR(I)=0 1=1, . . . ,MINPUT

cumulative squared errors found by input I

(begin seeding
loop)

IREPET=IREPET+1

If ISW2=1 so that the errors were read in,

and NREPETyi so that the number of seedings called

for is not 1, then set NREPET=1 and write

"PROGRAM SETS NREPET TO 1 WHEN ERRORS ARE PLANTED".

Otherwise, continue.

If ISW2=1 the errors were read in, continue,
Otherwise, CALL SEED.

A-4

0

k

IREP=0

replication counter

78 ) begin a replication

IREP=IREP+1

J_

IRUN = 1
input counter

785 ) do next input

f

NFIND=0
N0DE=1

L

If MOUNT=0, continue.

Otherwise, write

"SEEDING NUMBER"

"REPLICATION^'

"INPUT="

A- 5

79

Count the arcs leaving NODE.
Call the number NUMSUC

If NUMSUC=0, GO TO 96
Otherwise, continue

I

96

/

If NUMSUC=1, that node is next.

If NUMSUC > 1, select randomly the next

node. (L is the index of the next node)

J

If MOUT=0 continue.
Otherwise, write the index L

±

801

NTRAV (NODE , L) =NTRAV (NODE , L) +1
(count the number of traversals'

J

If ISEED(NODE,L)=0,

Otherwise, continue,
detected

GO TO
An

95.
error

has

been

J-

If MOUT=0 continue.

Otherwise, write "ERROR ROUND IN PREVIOUS ARC"

£.

802

nfind=nfind+iseed(node,l;
iseed(node,l)=0

95

.J-

NODE=L

A-6

yes

IFIND(IRUN)=NFIND
SFIND(IRUN)=NFIND*NFIND

1

>

IRUN=IRUN+1

\f

(^)

If IRUN <_ MINPUT, GO TO 785
and do next input.

Otherwise, continue.

^)

.

'

Is IREP=1 ?

(is this the first replication for this seeding?

for each input 1,..., MINPUT

IFOUND( )=IFIND( )

SFOUND( )=SFIND( )

CUMSQR( )=CUMSQR( )+SFIND( )

->-( 112

for each input 1,

no

, MINPUT

IFOUND( )=IFOUND( )+IFIND( )
SFOUND( )=SFOUND( ) +SFIND ( )
CUMSQR( )=CUMSQR( )+SFIND( )

no

/

I REP > NUMOUT \_

113

ISEED(I ,J) =SVSEED(I ,J)
for all I, J

yes

0

A-7

©

i

Do 666, this page, for
each input 1,...,MINPUT

AVE

IFOUND( )
IREP( )

(float pt)

I

no

s irep=i ? \ yes

\. first replication for this seeding^-

J-

VAR=SFOUND( ) -I REP* AVE* AVE
IREP-1

If MOUT=0, continue.

Otherwise, write

"STD DEV NOT COMPUTED'

^L

±.

123

VAR=11108889
(dummy value)

SD=VAR**.5

If MOUT=0, continue.

Otherwise, write

"INPUT NUMBER=H

"AVE NUMBER ERRORS FOUND="

"STD DEV="

yes

IREPET=1 ?

Is this the first seeding?

no

X

116

SVAVE ( ) =AVE
S WAR ( ) =VAR
SVSQR( )=AVE*AVE

SVAVE ( ) =SVAVE ( ) +AVE
SWAR( )=SWAR( ) +VAR
SVSQR( )=SVSQR( ) +AVE*AVE

A-{

77

yes

IREPET < NREPET ?

are there more reseedings
to do?

no

If MOUT=0, continue.

Otherwise, write

"THE PATH SEED IZ IS NOW"

Do 120, for each input
1, . . . ,MINPUT

TAVE=SVAVE (

NREPET

TVAROK=-

CUMSQR ( ) -NUMOUT*NREPET*TAVE*TAVE
NUMGUT*NREPET-1

TS DOK= TVARCK * * . 5

(all in floating point)

t-

Write "SUMMARY FOR INPUT

"AVE ERRORS FOUND= ' "
"STANDARD DEVIATION= "

JL

If NREPET=1 (# seedings)

or NUMOUT;=l (# replications)

(or both) , GO TO 7766
Otherwise, continue.

VAR1=SVSQR( )-NREPET*TAVE*TAVE

NREPET- 1
SD1 = VAR1**. 5

Write "STD DEV OVER SEEDING WITH ONE REPLIC="

A-9

0

L

Write "I J NBR OF TRAVERSALS"

(for each arc)

A-10

SUBROUTINE SEED

initialize :

NSEED=0

XNUMER=0.

JUMP=0

INTERU=0

XINST=0

XMEAN=MEANER

ISEED(all arcs)=0

consider next arc
XINST=XINST+X ( I , J )

(cumulative number of instructions)

No

CALL EXPON
to get ERl

XERl = XiMEAN*ERl

INTERV=INTERV+1
XNUMBE R= XNUME R+XE Rl

JUMP=1

Yes

v

JUMP=0

I3EED(this arc)=I3EED(
NSEED=NSEED+1

>+l

no

XINST < XNUMER ?

-v yes

Write

"TOTAL NUMBER OF INSTRUCTIONS IS"
"SEED ERRORS AT INSTRUCTION INTERVALS"
"TOTAL NUMBER OF ERRORS SEEDED IS"
"THE ERROR MATRIX"
THE ERROR SEED IX IS NOW"

last arc

yes

__

SVSEED( )=ISEED( )
for all arcs

jL

MOUT=0 ?

X

yes

■*- RETURN

A-ll

APPENDIX B
DIRECTED GRAPHS, SIMULATION AND ANALYTICAL RESULTS

Notation used in Appendix B

i : node i

j : node j

P. .: relative frequency of traversing arc ij one or more times

(simulation model)
P. .: probability of traversing arc ij one or more times (analytical

model) .

S. .: number of source statements in arc ij .
ID

E(l) = I P . _, S . ./M: expected number of errors detected on first input,
ij 1: 1]

obtained from analytical model, where M is the mean number of
source statements between errors (M = 21 for Module 1 and M = 51

for Module 2) .

/
U = S/M: expected number of errors in a program, where S is the number

of source statements in a program.

E' (1)/U = ; P. .S../S: expected fraction of number of errors detected on
r. i] id7

first input.

E'(l): mean number of errors detected on first input obtained from

simulation model.

E'(l)/U = (E'(1)/S)M: mean fraction of number of errors detected on

first input (given as a percentage at the bottom of directed

graphs) .

*: indicates that P . has no meaning because ratio of number of traversals

in arc ij to total number of input traversals is greater than one,

because arc ij is part of a cycle.

B-l

2. Notes.

° The number of source statements (x) and number of machine instructions (]
in an arc are indicated by (x/y) alongside the arc. No number or zero
means there are zero statements/instructions in an arc. (These are trans:
of control arcs) . In some cases the number of machine instructions was
not available.

0 Since the simulation model does not accomodate parallel arcs, a dummy
node was inserted in each parallel arc.

° Nodes associated with sub-procedures (entry and exit nodes) are designate
by letters. The entire sub-procedure is indicated by a dotted line
and is counted as one arc.

B-2

Module: 1

Procedure No

Hunter of nodes:

Nuccec cf arcs:

Hunter of paths:

Nun her ci source stmts.:

Average e r r c r found:

Eercentace encrs found:

14

23

26

37

0 . 3 1 4 '4

17.34

B-3

100 Re

Modul e

1

Procedure 2

plications

100 Repetitions

i

i

p'i:

pn

s . .

1

2

1.0000

1.0000

4

2

3

.4948

.5000

l

2

14

.5052

.5000

0

3

4

.2480

.2500

2

3

8

.2468

.2500

0

4

5

.1250

.1250

3

4

14

.1230

.1250

0

5

6

.0645

.0625

4

5

8

.0605

.0625

0

6

7

.0315

.0313

0

6

8

.0330

.0313

4

7

8

.0315

.0313

0

8

9

.1860

.1875

1

8

14

.1858

.1875

0

9

10

.0949

.0938

1

9

14

.0911

.0938

0

10

11

.0475

.0469

1

10

14

.0474

.0469

0

11

12

.0233

.0234

2

11

14

.0242

.0234

0

12

13

.0101

.0117

0

12

14

.0132

.0117

14

13

14

.0101

.0117

0

= €

>.2890

37

• • ID ID

ID

E(l) = .2995
E(l)/U = .1700

B-4

H c d u 1 e : 1

Procedure Ito

Hunter cf nccss: 13

tiunher of arcs: 14

Nucher of paths: 3

Nunber cf source stats.: 10

Average errcr found: 0.2523

::=rcencdqe errors round: 5 2.93

B-5

100 Re.

Modul

e 1

Procedure

8

plications

100 Repetitions

i

i

p'ij

!ii

s . .

13

1

2

1.0000

1.0000

3

2

3

.4947

.5000

3

2

9

.5053

.5000

0

3

A

.4947

.5000

0

4

5

.4947

.5000

1

5

C

.4947

.5000

0

6

7

.4947

.5000

1

7

8

.2497

.2500

0

7

9

.2450

.2500

2

8

9

.2497

.2500

0

A

B

.4947

.5000

0

B

4

.4947

.5000

0

C

D

.4947

.5000

0

D

6

.4947

.5000

_0
10

y p. .s . . = 6.0000
•• ij i]

E(l) = .2857
E(l)/U ■ .6000

B-6

ttcdule: 1

Procedure No. : 11

Nu n ter o f nodes: 6

iiuiil:er cf arcs: 7

Nuicer of paths: 3

Number cf sctrce stats.: 3

Average srrci found: 0.197^

Z-srcentacs errcrs found: 5 1.82

B-7

100 Re

Module

1

Procedure 11

iplications

100 Repetitions

i

i

p'ij

p. . s. .
H i]

1

2

1.0000

1.0000 2

2

3

.4947

.5000 1

2

4

.5053

.5000 0

3

4

.2497

.2500 1

3

6

.2450

.2500 0

4

5

.7550

.7500 2

6

5

.2450

.2500 2_
8

T p. .s. . = 4.75
• ID ID

E(l) = .2262
E(l)/U = .5938

B-8

Module: 1

Procedure No.; 14

4/11

2/7

3/6

Kuater of nodes: 6

Suiter cf arcs: 7

Nucter of paths: 4

iiuiiher cf scirce stats.: 9

Average errcr found: 0.2586

Esrcentace errors found: 60.34

B-9

Module 1

Procedure 14

100 Replications

100 Repetitions

i

i

P

i

ij

pij

s .

l

1

2

i

.0000

1.0000

4

2

3

.4983

.5000

0

2

4

.5017

.5000

2

3

4

.4983

.5000

0

4

5

.4994

.5000

0

4

6

.5006

.5000

3

5

6

.4994

.5000

0

9

J p. .s. . = 6.5000

• ID ij

13

E(l) = .3095
E(l)/U = .7222

B-10

rtcdule: 1

Procedure No. : 19

Number of nodes:

N u □ b e r cf afcs:

Nutrber of paths:

Number cf source stats.:

Average errgf fcund:
Perce ntace errors found:

19

26

7

22

0.2 33 5

27.54

B-ll

Module 1 Procedure 19

100

Replications 100

Repetitions

i_

i

P* ■ •

pm

s .

1

2

1.0000

1.0000

3

2

3

.4948

.5000

1

2

19

.5052

.5000

0

3

4

*

.2500

0

3

5

.4948

.5000

4

4

3

*

.2500

0

5

A

.4948

.5000

0

6

7

*

.1667

1

7

8

*

.0909

3

7

14

*

.1000

1

3

A

*

.0909

0

9

10

*

.1538

2

10

A

*

.1538

0

11

12

*

.1538

2

12

A

*

.1538

0

13

19

.2206

.2222

1

14

15

*

.0500

3

14

19

.0560

.0556

0

15

A

*

.0500

0

16

19

.2182

.2222

1

A

B

*

.5000

0

B

6

*

.1667

0

B-12

B

9

*

.1538

0

B

11

*

.1538

0

B

13

.2206

.2222

0

B

16

.2182

.2222

0
22

Z p. . s. .= 7.2 490
1J ID

E(l) - .3452
E(l)/u = .3295

B-13

Module: 1

Procedure No.: 22

Hunter of nodes: 25

Hunter cf arcs: 30

Hunter of paths: 11

Nuater cf sccrce stmts.: 30

Average errcr found: 0.410.

Perce ntace srrcrs found: 28.7-

B-14

Module

1

Procedure 22

100 Replications

100 Repetitions

i

i

p'ij

pu

s . .

1

2

1.0000

1.0000

4

2

3

.4950

.5000

4

2

19

.5050

.5000

0

3

4

.2490

.2500

0

3

5

.2460

.2500

3

4

5

.2490

.2500

0

5

6

.1280

.1250

1

5

7

.1179

.1250

1

5

8

.1234

.1250

1

5

9

.1257

.1250

1

6

16

.1280

.1250

2

7

15

.1179

.1250

:

3

10

.1885

.1875

3

9

14

.1257

.1250

1

10

A

.1885

.1875

0

11

12

.1885

.1875

2

12

C

.1885

.1875

0

13

18

.1885

.1875

0

14

8

.0651

.0625

0

14

15

.0606

.0625

1

15

16

.1785

.1875

1

16

17

.3065

.3125

1

17

E

.3065

.3125

0

18

19

.4950

.5000

:

A

B

.1885

.1875

0

B

11

.1885

.1875

0

C

D

.1885

.1875

0

D

13

.1885

.1875

0

E

F

.3065

.3125

0

F

13

.3065

.3125

0
30

J p. .s. . = 10.375
..ID i]

E(l) = .4940
E(l)/U =

3458

B-15

H c c u 1 e : 1

Procedure No.: 25

1/1

Hunter of nodes:
Nunter cf arcs:
Nunher of paths:
Su liter cf scarce stats
Average eircr found:

12

12

2

3

0.2324

6 1.01

B-16

Modul e

1

Procedure 25

100 Replications

100 Repetitions

i

i

P

■

ij

p. . s.
ID ID

1

2

1

.0000

1.0000 1

2

3

*

1.0000 2

3

4

*

. 5000 2

3

8

*

. 5000 0

4

A

*

.5000 0

5

6

*

.5000 2

6

C

*

. 5000 0

7

2

•

.5000 1

A

B

*

.5000 0

B

5

•

.5000 0

C

D

*

.5000 0

D

7

*

.5000 0
8

* p. .s. . = 5.5

E(l) = .2619

.6875

E(l)/u -

B-17

Module: 1

Procedure No.: 28

4/14

II u ii her of nodes:
NuEber c i arcs:
Nunher of paths:
Number of scace stats.:
Average error found:
Eercentace errors found:

17
19

24
0.6U0 0

56. 00

3-18

10(

Module

1

Procedure 28

) Replications

100 Repetitions

i

i

p'ij

pij

s . .

13

1

2

1.0000

1.0000

5

2

3

.4975

.5000

2

2

11

.5025

.5000

0

3

4

.2491

.2500

6

3

12

.2484

.2500

0

4

5

.1256

.1250

0

4

6

.1235

.1250

0

5

6

.1256

.1250

0

6

7

.7516

.7500

5

7

A

.7516

.7500

0

8

9

.7516

.7500

1

9

C

.7516

.7500

0

10

13

.7516

.7500

1

11

6

.5025

.5000

4

12

13

.2484

.2500

0

A

3

.7516

.7500

0

B

3

.7516

.7500

'3

C

D

.7516

.7500

0

D

10

.7516

.7500

0
24

I P. .s. .

i:

= 14

.75

E(l) = .7024
E(l)/U = .6145

B-19

Module : 1

Procedure No.: 29

Number of nodes:

Number of arc s :

Number of paths:

Number of source stmts: 47

Average error found: 1.3946

Percentage errors found:62.31

B-20

Modu

le 1

100 Repli

cations

i

i

p'i:

1

2

1.0000

2

3

. 5014

2

6

.4986

3

4

. 2499

3

20

. 2515

4

A

. 2499

5

7

. 2499

6

7

. 4986

7

8

. 7485

3

C

. 7485

9

10

. 7485

10

11

. 3682

10

13

. 3793

11

S

. 3692

12

13

. 3692

13

14

. 7485

14

15

*

14

16

.7485

15

14

*

16

G

. 7485

17

18

. 7445

18

G

.7445

19

20

. 7485

A

B

. 2499

B

5

. 2499

C

D

.7485

D

9

. 7485

E

F

. 3692

F

12

. 3692

G

H

*

H

17

. 7445

H

19

. 7485

Procedure No. 29
100 Repetitions
P.

i]

iD

1.0000 4
. 5000

.5000 0

.2500 3

.2500 1

. 2500 0

.2500 3

.5000 1

.7500 15

. 7500 0

.7500 5

. 3750 2

. 3750 0

.3750 0

. 3750 3

.7500 2

. 3750 0

.7500 4

.3750 0

.7500 0

.7500 2

. 7500 0

.7500 1

. 2500 0

.2500 0

.7500 0

.7500 0

.3750 0

.3750 0

.7500 0

.7500 0

.7500 0
47

B-21

Module 1

Procedure No . 29

(cont inued )

A p..S. = 30.375
ID ID ID

E(l) = 1.4464
E(l)/U = .6463

B-22

Hcdule: 1

Procedure Ho.:

30

Hunter of nodes: 7

Kui'cer cf arcs: 10

Hunter of paths: 5

Nuister cf sccice stmts.: 10

Average errcr found: 0.1649

ir^rcentace errors found: 34.63

B-23

Modul e

1

Procedure 30

100 Replications

100 Repetitions

i

i

P

i

ij

pi:

s . .

1

2

1

.0000

1.0000

2

2

3

.4943

.5000

1

2

7

.5057

.5000

0

3

4

.2500

.2500

1

3

7

.2443

.2500

0

4

5

.1276

.1250

1

4

6

.1224

.1250

0

5

6

.0638

.0625

0

5

7

.0638

.0625

2

6

7

.1862

.1875

_3_
10

J p. .s. . = 3.5625

E(l) = .1696
E(l)/U = .3563

B-24

Module

Procedure No. :

34

Jiunher of nodes:
Hunter of arcs:
Nucher of paths:
Nucter of source stnts.
Average eirci found:
Esrcentace errors round

16

18

3

15

0. 5 45 5

76.51

B-25

Module 1 Procedure No. 34

100 Replications 100 Repetitions

1
2

3

4
4
5
5
6
7
8
9
10
11
C
D
D
A
B

2

A
4

5
7

6
7
7
8
C
10

c

12
D
9

11
B
3

p ij

1

. 0000

1.

. 0000

1,

. 0000

. 4994

. 5006

2475

2519

2475

1.

. 0000

1

.0000

1 . 0000
*
*

1 . 0000
1.0000
1.0000

pij

s . .

1J

1. 0000

2

1. 0000

0

1 . 0000

1

. 5000

1

. 5000

0

. 2500

0

.2500

1

. 2500

0

1 . 0000

5

1 .0000

0

1. 0000

2

1. 0000

0

1.0000

3

1.0000

0

1 .0000

0

1 . 0000

0

1 . 0000

0

1 . 0000

0

15

A p. . s . . = 13.75
ID ID ID

E (1) = .6548
E (1) /U = . 9167

B-26

Module: 1

Procedure No

35

II u n c s r of nodes:
Number of arcs:
N u ir fc s r of paths:
Jiucber of source stats.:
Average error found:
Fsrcentacs errors found:

14
17
3

1 1

0.3576
63.27

B-27

Module 1

100 Replications

Procedure No. 35
100 Repetitions

1
2

3
4
4
5
5
6
7
8
9
10
11
A
B
B
B

2

A
4
5
6
6
9
7
A
9

10
A

12
B
3
8

11

1. 0000
1. 0000
*

. 5075
. 5055
.2563
. 2512
. 7618

.7618
*

*

*

1. 0000
*

*

*

1.0000

L2

1]

1 . 0000

4

1. 0000

0

1 .0000

1

. 5000

1

. 5000

0

. 2500

0

. 2500

0

. 7500

4

. 7500

0

1 . 0000

0

1 . 0000

0

1 . 0000

0

1.0000

1

1 .0000

0

1. 0000

0

1 . 0000

0

1. 0000

0

11

r. p . . s . .

E(l) =
E (1)/U =

9 . 5

.4524
.8636

B-28

ttcdule: 1

Procedure No. : 36

L/l

Nuafcer cf n c c € s :
Nuccer cf arcs :
Hunter of paths:
Nuaber cf scurce strats.:

Average errcr found:
Percentage liters found

B-29

Module 1 Procedure 36

100

Replications

100 Repetitions

P' • •

p4

s . .

1

2

1.0000

1.0000

2

2

3

.4964

.5000

12

2

17

.5036

.5000

0

3

4

.2449

.2500

3

3

6

.2515

.2500

0

4

A

,2 449

.2500

0

5

6

*

.2500

0

6

7

*

.2500

4

7

A

*

.2500

0

8

9

*

.2500

/

2

9

A

*

.2500

0

10

11

*

.2500

2

11

A

*

.2500

0

12

13

*

.2500

1

13

C

•

.2500

0

14

15

*

.2500

4

15

A

*

.2500

0

16

17

.4964

.5000

1

A

B

*

.5000

0

B

5

*

.2500

0

B

8

•

.2500

0

B

10

*

.2500

0

B

12

*

.2500

0

B

16

.4964

.5000

0

B-30

CD * .2500 0

D 14 * .2500 0

31

Z P. . S. . - 12.5000
JO JO

ECD = .5952
E(l)/u = .4032

B-31

Module: 1

Procedure No. : 39

Hunter of dccss: 17

Duster of arcs: 25

Jlantsr of paths: 10

tiuoter cf source s t m -t s .- : 17

Average eircr found: 0.2637

rcicsntaci errors found: 32.57

B-32

Module

1

Procedure 39

100 Replications

100 Repetitions

i

i

p'i;

pi:

s . .

1

2

1.0000

1.0000

4

2

3

.4954

.5000

1

2

14

.5046

.5000

0

3

4

.2490

.2500

1

3

14

.2464

.2500

0

4

5

.1258

.1250

1

4

14

.1232

.1250

0

5

6

.0631

.0625

1

5

14

.0627

.0625

0

6

7

.0299

.0313

1

6

14

.0332

.0313

0

7

3

.0162

.0156

1

7

14

.0137

.0156

0

8

9

.0090

.0078

1

8

13

.0072

.0078

1

9

10

.0040

.0039

1

9

11

.0050

.0039

0

10

11

.0040

.0039

1

11

A

.0123

.0117

0

12

15

.0123

.0117

1

14

15

.9877

.9883

1

13

11

.0033

.0039

1

13

14

.0039

.0039

0

A

B

.0123

.0117

0

B

12

.0123

.0117

_0

17

y p. .s. = 6.0117

• • ID ID

ID

E(l) = .2863
E(l)/U = . 3536

B-33

Module: 1

Procedure Ho.: MU

Nunterofnocles: 2 7

Number cf arcs: 30

Nun ter c i pa tfcs: 7

Nucter cf source stats.: 21

Average error fcunc: 0.3554

Bsrcsntacc errors found: 35.54

B-34

Module 1 Procedure 44

100

Replications 100

Repetitions

i

i

P". -
l3.

!ii

s .
r;

1

2

1.0000

1.0000

2

2

A

1.0000

1.0000

0

3

4

1.0000

1.0000

1

4

5

.4877

.5000

1

4

6

.5123

.5000

0

5

6

.2458

.2500

1

5

K

.2419

.2500

0

6

7

.3846

.3750

7

6

C

.3735

.3750

0

7

E

.3946

.3750

0

8

9

.3846

.3750

' 1

9

10

.1952

.1875

4

9

14

.1894

.1875

0

10

G

.1952

.1875

0

11

12

.1952

.1875

2

12

I

.4371

.4375

0

13

14

.4371

.4375

I

14

27

.6265

.6250

1

G

H

.1952

.1875

0

H

11

.1952

.1875

0

A

3

1.0000

1.0000

0

B

3

1.0000

1.0000

0

C

D

.3735

.3750

0

D

27

.3735

.3750

0

B-35

E

F

.3735

.3750

0

F

8

.3846

.3750

0

I

J

.4371

.4375

0

J

13

.4371

.4375

0

K

L

.2419

.2500

0

L

12

.2419

.2500

0

Z p. , S. . - 8.9375

E(l) = .4256
E(l)/u = .4256

21

B-36

Module.

Procedure No.

m

Huibsr of nodes: 19

:iunfcer of arcs: 20

Number of paths: 4

Nuaber of source stats.: 12

Average error found: 0.4 231

Percentage errors found: 74.04

B-37

Module 1 Procedure 47

100 Replications 100

Repetitions

i

J

P'. •

!ii

s . .

1

2

1.0000

1.0000

3

2

A

1.0000

1.0000

0

3

4

1.0000

1.0000

1

4

5

.4913

.5000

0

4

6

.5017

.5000

1

5

6

.4983

.5000

3

6

7

1.0000

1.0000

0

7

C

1.0000

1.0000

1

8

9

1.0000

1.0000

1

9

10

.4994

.5000

0

9

12

.5006

.5000

0

10

E

.4994

.5000

0

11

12

.4994

.5000

2

12

19

1.0000

1.0000

0

A

B

1.0000

1.0000

0

B

3

1.0000

1.0000

0

C

D

1.0000

1.0000

0

D

8

1.0000

1.0000

0

E

F

.4994

.5000

0

F

11

.4994

.5000

0
12

Z p. .
13

s. . = 9.
13

.0000

E(l) = .4286
E(l)/u = .7500

B-38

Module: 1

Procedure No. : U8

Nunter of nodes: 23

Nun ber cf a res : 26

Hunter of paths: 7

Nucbei cf source stats.: 13

Average errcr found: 0.3287

Ecccsniacc errors found: 53. 1C

B-39

Module 1 Procedure 48

100

Replications 100

Repetitions

i

i

P' • •
3-3

!ii

s.

i;

1

2

1.0000

1.0000

2

2

3

.4943

.5000

1

2

8

.5057

.5000

0

3

4

.2520

.2500

1

3

G

.2423

.2500

0

4

5

.1288

.1250

0

4

6

.1232

.1250

1

5

6

.1288

.1250

0

6

A

.2520

.2500

0

7

8

.2520

.2500

0

8

9

.7577

.7500

7 4

9

C

.7577

.7500

0

10

11

.7577

.7500

1

11

12

.3766

.3750

1

11

14

.3811

.3750

0

12

E

.3766

.3750

0

13

14

.3766

.3750

0

14

15

.7577

.7500

2

A

B

.2520

.2500

0

B

7

.2520

.2500

0

C

D

.7577

.7500

0

D

10

.7577

.7500

0

E

F

.3766

.3750

0

B-40

F

13

.3766

.3750

0

G

H

.2423

.2500

0

H

15

.2423

.2500

0

13

Z p. . s. . = 8.5000
E (1) = .4048
E(l)/u = .6538

B-41

Module: 1

Procedure No

49

Number cf nodes: 15

Number of arcs: 20

Number of paths: 7

Number of sconce stmts.: 19

Average error found: 0.2217

Percentage errors found: 2 4.50

B-42

Module 1 Procedure 49

100

Replications

100 Reoetitions

i

1

P' • •

!ii

s .

1

2

1.0000

1.0000

_

2

3

.4959

.5000

I

2

8

.5041

.5000

0

3

4

.2492

.2500

2

3

8

.2467

.2500

0

4

5

.1260

.1250

1

4

8

.1232

.1250

0

5

6

.0632

.0625

1

5

8

.0628

.0625

0

6

7

.0302

.0313

1

6

10

.0330

.0313

0

7

11

.0164

.0156

0

7

12

.0138

.0156

2

8

A

.9368

.9375

I

9

13

.9368

.9375

:

10

12

.0330

.0313

3

11

12

.0164

.0156

:

12

13

.0632

.0625

2

A

3

.9368

.9375

0

3

9

.9368

.9375

0
L9

Z p. , s. . = 5.3751
13 JO

E(l) ■ .2560
E(l)/u = .2829

B-43

ttcdule: 1

Procedure No. : 53

Nunterofncdes: 11

Nucbsrcfarcs: 18

tluitsr oi paths: 9

Nucher cf scuice stmts.: 11

Average errcr found: 0.1376

Eeicentace encrs found: 35.81

B-44

Mo

dule

1

100

Repl

icat ions

i_

i

*u

1

2

1. 0000

2

3

. 4946

2

10

.5054

3

4

.2486

3

10

.2460

4

5

. 1258

4

10

. 1228

5

6

.0632

5

10

.0626

6

7

.0299

6

10

.0333

7

3

.0161

7

10

.0138

8

9

.0092

8

10

.0069

9

10

.0040

9

11

.0052

0

11

. 9948

Procedure No. 53
100 Repetitions

pij

s . .

3-3

1. 0000

2

. 5000

1

.5000

0

.2500

1

.2500

0

.1250

1

. 1250

0

.0625

1

.0625

0

.0313

1

.0313

0

.0156

1

.0156

0

. 0078

1

.0078

0

. 0039

0

.0039

0

.9961

2

11

". . p . . s .

13 13 13

E(l) =
E(l)/U =

= 4.9844

. 2374
.4531

B-45

Kcdule: 1

Procedure No. : 57

Nuoiber of nodes: 30

Number of arcs: 35

tiuaber of paths: 12

Number of scqrce stmts.: 26

Average error found: 0.2910

Percentage errors found: 23.50

B-46

Module 1 Procedure 57

100

Replications

100 Repetitions

jl

2

P' • •
13

!ii

s .
1

1

2

1.0000

1.0000

2

2

3

.4972

.5000

1

2

19

.5028

.5000

1

3

A

.4972

.5000

0

4

5

.4972

.5000

1

5

6

.2511

.2500

1

5

9

.2461

.2500

0

6

7

.1228

.1250

1

6

19

.1283

.1250

0

7

8

.0621

.0625

1

7

21

.0607

.0625

1

8

9

.0309

.0313

0

8

19

.0312

.0313

0

9

10

.2770

.2813

2

10

11

.1407

.1407

0

10

12

.1363

.1407

I

12

13

.1644

.1720

5

13

C

.1644

.17 20

0

14

15

.1644

.1720

1

15

16

.0842

.0860

3

15

18

.0802

.0860

0

16

E

.0842

.0860

0

17

18

.0842

.0860

0

B-47

18

22

,1644

.1720

2

19

G

.6949

.6875

0

20

22

.6949

.6875

1

21

12

.0281

.0313

2

21

19

.0326

.0313

0

E

F

.0842

.0860

0

F

17

.0842

.0860

0

A

B

.4972

.5000

0

B

4

.4972

.5000

0

G

H

.6949

.6875

0

H

20

.6949

.6875

0

C

D

.1644

.1720

0

D

14

.1644

.1720

0
26

s. . = 7.0874

1J 13
E(l) = .3375

E(l)/u = .2726

B-4!

Module: 1

Procedure No.: 60

Nuuter of nodes: 28

Number of arcs : 37

Hunter of paths: 16

Nuatsr cf sctice stats.: 24

Average errcr found: 0.3336

Eercentace errors found; 29.19

B-49

Module 1 Procedure 60

100

Replications

100 Repetitions

i

i

P'. •
*3

!ii

s . .
ij

1

2

1.0000

1.0000

3

2

3

.4987

.5000

1

2

12

.5013

.5000

0

3

4

.2438

.2500

1

3

17

.2549

.2500

0

4

A

.2438

.2500

0

5

6

.2438

.2500

1

6

7

.1225

.1250

1

6

17

.1213

.1250

0

7

8

.0626

.0625

1

7

19

.0599

.0625

1'

8

9

.0303

.0313

1

8

12

.0323

.0313

0

9

10

.0172

.0156

1

9

12

.0131

.0156

0

10

11

.0090

.0078

0

10

12

.0082

.0078

2

11

12

.0090

.0078

0

12

E

*

.6095

0

13

14

*

.6095

1

14

15

*

.3047

4

14

18

*

.4063

0

15

C

*

.3047

0

B-50

16

18

*

.2188

I

17

18

.3762

.3750

1

18

22

1.0000

1.0000

1

19

12

.0295

.0313

0

19

20

.0304

.0313

:

20

C

.0304

.0313

0

21

12

*

.1641

l

C

D

*

.3282

0

D

16

*

.2188

0

D

21

*

.1461

0

A

B

.2438

.2500

Q

B

5

.2438

.2500

0

E

F

*

.6095

0

F

13

*

.6095

0
24

- Pij Sij = 7.9613

E(l) = .3791
ECl)/u = .3317

B-51

Med ule.

Procedure lio.

75

1/'

number of nodes:
Number ci arcs:
8 u n b e r of paths:
liucber of source stats.
Average error found:
"Percentage e rr c r s found

b I . ijD

B-52

Module 1 Procedure 75

100

Replications 100

Repetitions

i

1

p'. .

!ii

s .

1

2

1.0000

1.0000

4

2

3

.5020

.5000

4

2

5

.4980

.5000

0

3

A

.5020

.5000

0

4

5

*

.3750

1

5

6

*

.3750

1

5

12

.5066

.5000

0

6

C

*

.3750

0

7

3

*

.3750

2

8

A

*

.3750

0

9

10

*

.3000

2

10

A

*

.3000

'3

11

12

.4934

.5000

0

12

13

1.0000

1.0000

2

13

E

1.0000

1.0000

0

14

15

1.0000

1.0000

i

15

16

.4937

.5000

0

15

17

.5063

.5000

:

16

17

.4937

.5000

0

17

24

1.0000

1.0000

2

A

B

*

.7500

0

B

4

*

.3750

0

B

9

*

.3000

0

B-53

B

11

.4934

.5000

0

E

F

1.0000

1.0000

0

F

14

1.0000

1.0000

0

C

D

*

.3750

0

D

7

*

.3750

0
20

Z p. . s. . = 13.6000
3-D ID

E(l) = .6476
E(l)/u = .6800

B-54

Module: 1

Procedure No. : 76

Nun fcer o f nodes: 15

Hunter c£ arcs: 19

Kuufcer of paths: 5

Nucter of sctrce stats.: 19
Average error found: 0.3893

Eercsntace errors found: 43.03

B-55

Module 1 Procedure 76

100

Replications 100

Repetitions

i

i

P'. •

!ii

s .

1

1

2

1.0000

1.0000

2

2

3

.4941

.5000

2

2

10

.5059

.5000

0

3

4

.2431

.2500

4

3

13

.2510

.2500

0

4

A

.2431

.2500

0

5

6

*

.1250

3

6

A

*

.1250

0

7

8

*

.1250

2

8

A

*

.1250

0

9

10

.2431

.2500

0

10

11

.7490

.7500

6

11

12

*

.3750

0

11

13

.7490

.7500

0

12

11

*

.3750

0

A

B

.7493

.2500

0

B

5

*

.1250

0

B

7

*

.1250

0

B

9

.2431

.2500

0
19

E p. . s. . = 9.1250
E(l) = .4345
E(l)/u = .4803

B-56

ttcdule: 1

Procedure No. : 77

Hunter of ncces: 17

Hunter cf arcs: 20

Sucter of paths: 9

Number cf scirce stmts.: 10

Avscags srrci found: 0.2425

Feces n race encrs found: 50.93

B-57

Module 1 Procedure 77

100 Repli

cations 100

Repetitions

i_

i

!±i

s

1

2

1.0000

1.0000

2

2

3

.49 72

.5000

2

2

5

.5028

.5000

0

3

4

.2506

.2500

0

3

5

.2466

.2500

2

4

5

.2506

.2500

0

5

A

1.0000

1-0000

0

6

7

1.0000

1.0000

1

7

8

.4979

.5000

1

7

9

.5021

.5000

0

8

9

.2513

.2500

1

8

E

.2 466

.2500

0

9

C

.7534

.7500

0

LO

11

.7534

.7500

1

C

D

.7534

.7500

0

D

10

.7534

.7500

0

A

B

1.0000

1.0000

0

B

6

1.0000

1.0000

0

E

F

.2466

.2500

0

F

11

.2466

.2500

0
10

Z p. . s. . = 6.0000
13 ID

E(l) = .2857
E(l)/u = .6000

B-5.

acdule: 1

Hunter of ncd^s:

Number ci arcs:

Nun her of paths:

Nun be r of source stats.:

Average error found:

E^rcentace errors found:

Procedure No

79

B-59

Module 1 Procedure 79

100 Replications 100

Repetitions

i_

i

p'i:

!ii

s .

l

1

2

1.0000

1.0000

2

2

3

.4965

.5000

3

2

E

.5035

.5000

0

3

4

.2458

.2500

2

3

6

.2507

.2500

0

4

A

.2458

.2500

0

5

6

*

.2500

0

6

7

*

.3750

2

7

A

*

.3750

0

8

9

*

.2500

2

9

A

*

.2500

0

10

11

*

.2500

2

11

C

*

.2500

0

12

13

*

.2500

3

13

A

*

.2500

0

14

15

*

.2500

2

15

A

*

.2500

0

16

17

*

.2500

3

17

A

*

.2500

0

18

25

.4965

.5000

2

A

B

*

.5000

0

B

5

*

.2500

0

B-60

B

8

*

.2500

0

B

10

*

.2500

0

B

14

*

.2500

0

B

16

*

.2500

0

B

18

.4965

.5000

0

E

F

.5035

.5000

0

F

25

.5035.

.5000

0

C

D

*

.2500

0

D

12

*

.2500

0
23

X p. . s. . = 8.7500
ID ID

E(l) = .4167
E(l)/u - ,3804

B-61

ttcdule: 1

Procedure No. : 81

Hunter of ncces: 8

lluibsr cf arcs: 9

Nuntsr of paths: 3

Nuucer cf sctrce stmts.: 7

Average sircr found: 0.1449

-ercenbacs errors found: 43.47

B-62

Module 1

Procedure No. 81

2
3

6
4
6
A
3
5
6

Pi

(1)

!ii

s . .

1. 0000

2

. 5000

1

.5000

0

. 2500

3

.2500

0

.2500

0

.2500

0

. 2500

0

. 2500

1

p . . s .

. . 1] 1]

13

3 .50

E(l)

1667

E(l)/U =

. 5000

(1)

p! . data was not available for this procedure

B-63

Module: 1

Procedure No. : 87

2/11

Nunber of nodes:
Nunber of arcs:
Nuaber of paths:
Number cf scarce stats.:
Average error found:
Percentage errors found;

21

24

6

25

0.5 02 9

4 2.24

B-64

Module 1 Procedure 87

100

Replications 100

Repetitions

i_

i

p'ij

!ii

s .

i;

1

2

1.0000

1.0000

2

2

A

1.0000

1.0000

0

3

4

1.0000

1.0000

4

4

5

.4915

.5000

1

4

10

.5085

.5000

0

5

6

.2438

.2500

2

5

12

.2477

.2500

0

6

7

.2572

.2500

0

6

8

.2444

.2500

3

7

8

.2572

.2500

0

8

C

.5016

.5000

0

9

21

.5016

.5000

I

10

11

.5085

.5000

2

11

6

.2578

.2510

4

11

21

.2507

.2500

0

12

13

.2477

.2500

4

13

E

.2477

.2500

0

14

21

.2477

.2500

2

E

F

.2477

.2500

0

F

14

.2477

.2500

0

A

B

1.0000

1.0000

0

B

3

1.0000

1.0000

0

B-65

c

D

.5016

.5000

0

D

9

.5016

.5000

0
25

Z p. . s. . = 11.7500
E(l) - .5595
E(l)/u = .4700

B-66

Module: 1

Procedure No.: 91

Number of nodes:
Nuaber of arcs:
Number of paths:
Nunber of source stmts.
Average errai found:
Percentage errors found

B-67

Module 1 Procedure 91

1
2
2
3

3

4

4

5

5

6

6

7

8

9

9

10

10

11

12

13

13

14

15

100

Replications 100

Repetitions

i

p'm

!ii

s .

2

1.0000

1.0000

2

3

.4957

.5000

1

22

.5043

.5000

0

4

' .2494

.2500

1

22

.2463

.2500

0

5

.1254

.1250

1

17

.12 40

.1250

0

6

.0628

.0625

1

14

.0626

.0625

0

7

.0301

.0313

1

22

.0327

.0313

0

A

.0301

.0313

0

9

*

.0157

1

10

*

.0078

1

14

.0085

.0078

0

11

*

.0039

1

22

.0054

.0039

0

20

*

.0039

0

13

.0162

.0153

1

14

.0082

.0078

0

22

.0080

.0078

0

15

.0793

.0860

1

18

.0793

.0860

0

B-(

16

17

.0793

.0860

0

17

22

.2033

.2110

2

C

D

.0793

.0860

0

D

15

.0793

.0860

0

A

3

.0348

.0313

0

B

8

.0186

.0157

0

B

12

.0162

.0157

0
14

Z p. . s. . = 3.5195
ID ID

E(l) = .1676
E(l)/u = .2514

B-69

Module: 1

Procedure No

S2

liuiter cf ecccs: 5

Number of arcs: 6

Nun t er o £ pa ths: 3

Hunter cf set" ice stats.: 9

Average errcr found: 0.1837

rsreer. tacs errors found; 4 2.66

B-70

Module

1

Proce

dure Ni

500

Rep

1 ica t

ions

500 Repet

it ions

i_

i

ID

pij

s . .
*1

1

2

1. 0000

1. 0000

2

2

3

.4995

.5000

1

2

5

.5005

.5000

0

3

4

.2499

.2500

0

3

5

. 2497

. 2500

6

4

5

. 2499

. 2500

0

y. p . . s . .

ID ID ID

E (1) =
E(l)/U =

= 4.0

1905
4444

B-71

Hcdule: 1

Procedure No. : 93

Nuttter of nodes: 25

tiuiter cf arcs: 34

Nuiter of path: 12

Nuiter cf source stats.: 34

Average errcr found: 0.3972

Eercentacs errcrs found: 24.53

B-72

Module 1 Procedure 93

100

Replications 100

Repetitions

i

i

P'. •

pij

s.
1

1

2

1.0000

1.0000

2

2

3

.4996

.5000

I

2

19

.5004

.5000

0

3

4

.2537

.2500

1

3

• 20

.2459

.2500

0

4

5

.1301

.1250

2

4

20

.1236

.1250

0

5

6

.0659

.0625

8

5

23

.0642

.0625

0

6

7

.0339

.0313

2

6

9

.0320

.0313

0

7

8

*

.0157

0

7

12

.0339

.0313

1

8

7

*

.0157

0

9

10

.0320

.0313

2

10

11

*

,0157

0

10

12

.0320

.0313

0

11

10

*

.0157

0

12

13

.0659

.0625

5

13

A

.0659

.0625

0

14

15

*

.3125

2

15

16

*

.1563

0

B-73

15

17

*

.3125

2

16

15

*

.1563

0

17

A

*

.3125

0

18

23

.4629

.4688

1

19

21

.5004

.5000

1

20

21

.3695

.3750

3

21

A

.8699

.8750

0

22

23

.4729

.4688

1

A

B

*

.9375

0

B

14

*

.3125

0

B

18

.4629

.4688

0

B

22

.4729

.4688

0
34

Z p. . s. . = 7.7814
E(l) = .3705
E(l)/u = .2289

B-74

Module: 1

Procedure No. : 95

Nuarer of ncces: 1 8

liuifcer cf arcs: 27

Nun her of paths: 10

Nuorer cf source stmts.: 19

Average errcr found: 0-1822

fercsntace sircrs found: 20.14

B-75

Module 1 Procedure 95

100

Replications 100

Repetitions

i

i

P*. •

fii

s .

1

2

1.0000

1.0000

2

2

3

.4964

.5000

2

2

16

.5036

.5000

0

3

4

.2470

.2500

1

3

12

.2494

.2500

1

4

5

.1229

.1250

1

4

16

.1241

.1250

0

5

6

.0633

.0625

1

5

13

.0596

.0625

0

6

7

.0315

.0313

1

6

16

.0318

.0313

0

7

8

.0166

.0156

1

7

16

.0149

.0156

0

8

9

.0087

.0078

1

8

16

.00 79

.0078

0

9

10

.0042

.0039

3

9

13

.0045

.0039

0

10

A

.0042

.0039

0

11

16

.0978

.0977

1

12

13

.1255

.1250

0

12

16

.1239

.1250

3

13

14

.1896

.1914

0

B-76

14

A

.1296

.1914

1

15

16

.0960

.0977

0

A

B

.1938

.1953

0

B

11

.0978

.0977

0

B

15

.0960

.0977

0
19

7 p. . s. . = 4.4180
E(l) = .2104
E(l)/u = .2325

B-77

Module : -^

Procedure No. 15

Nuafcercfnocjes: 11

liuEhsr cf arcs: 13

Nufltsr ci faths: 5

Nuaher cf source stats.: 10

Average errcr found: 0.0836

Percent ace errors found: 42.64

B-78

MODULE 2 Procedure 15

100

Replications

100 Repetitions

i

2

P'. •

pij

s . .

3-D

1

2

1.0000

1.0000

0

2

3

.4944

.5000

3

2

9

.5056

.5000

0

3

4

.4992

.2500

0

3

5

.4994

.5000

2

4

3

.4992

.2500

0

5

6

*

.5000

3

6

A

*

.5000

0

7

/

8

*

.5000

1

8

5

*

.2500

1

a

9

.4944

.5000

0

A

B

*

.5000

0

B

7

*

.5000

0

y p. .s. . = 4.7500
E(l) = .0931
E(l)/u = .4750

10

B-79

Module:

Procedure No. : 23

Nun ter of ncces: 1 0

Nunber cf arcs : 1 1

Hunter of paths: 3

Number cf s c r r c e stats.: 12

Average srrci found: 0.1592

Percent a e€ errors found: 6 7.65

B-80

MODULE 2 Procedure 23

100

Replications

100 Repetitions

_i

i

P' ■ •

pij

s .

l

1

2

1.000

1.000

3

2

3

.4947

.5000

1

2

4

.5053

.5000

0

3

4

.2497

.2500

1

3

6

.2450

.2500

1

4

5

.7550

.7500

3

5

8

.7550

.7500

2

6

A

.2450

.2500

0

7

8

.2450

.2500

1

A

B

.2450

.2500

0

B

7

.2450

.2500

0
12

y p. .s. . = 8.0000

E(l) = .1569
E(l)/u = .6667

B-81

Bed ule:

Procedure No. :

41

Nun her of ncces:
Nuuter cf arcs:
Hunter of caths:
Hunter cf scircs stats
Average errcr found:

10
14
12
13
0. 1554

r <= i_ k_

enta

encib roan-

o u

f C;

B-82

Module 2

Procedure 41

100

Repl

i cations

100

Repetitions

_i

i

P' ■ •
1P

pi:

s . .

1

2

1.0000

1.0000

3

2

3

.4955

.5000

0

2

6

.5045

.5000

0

3

4

*

.5000

2

4

5

*

.2500

3

4

6

.3303

.3333

0

5

3

*

.1250

0

5

6

.1652

.1667

0

6

7

.4993

.5000

1

6

10

.5007

.5000

0

7

3

.4993

.5000

2

S

9

.2474

.2500

0

8

10

.2519

.2500

2

9

10

.2474

.2500

0

I p. .s. , = 6.75

E(l) = .1324

E(l)/u = .5192

13

B-83

Module: 2

Procedure No. 46

Numb er of nodes :
Number of ar cs :
Number o f paths :
Number of source stmts.:
Average error found:
Percentage errors found:

B-84

Module 2 Procedure 46

100

Replications 100

Repetitions

i^

i

P'. •
l3.

pij

s . .
l3

1

2

1.0000

1.0000

3

2

6

1.0000

1.0000

0

5

23

.3908

.3906

2

6

7

1.0000

1.0000

2

7

8

.4955

.5000

2

7

23

.5045

.5000

0

8

9

.4955

.5000

2

9

10

.2485

.2500

I

9

14

.2470

.2500

1

10

5

.1220

.1250

0

10

11

.1265

.1250

2

11

5

.0642

.0625

0

11

12

.0623

.0625

4

12

5

.0333

.0313

0

12

13

.0290

.0313

2

13

5

.0290

.0313

0

14

15

.1228

.1250

1

14

21

.1242

.1250

1

15

16

.0607

.0625

1

15

21

.0621

.0625

0

16

5

.0330

.0313

0

16

17

.0277

.0313

1

17

24

.0277

.0313

0

18

19

.1051

B-85

.1094

0

19

20

.2140

.2188

3

20

5

.1093

.1094

0

20

23

.1047

.1094

3

21

24

.1863

.1875

22

19

.1089

.1094

1

24

25

.2140

.2188

0

25

18

.1051

.1094

0

25

22

.1089

.1094

0
32

7 p. .s. . = 10.2815

E(l)
E(l)/u

.2016
.3213

B-86

Module: 2

Procedure No

U7

SunbeiC of nodes:

iiuraber ci arcs:

Number of paths: 36

Nunber cf scarce stmts.: 33

Average error found: 0.1163

Percentage errors found: 17.97

B-87

Module 2 Procedure 47

100

Replications

100 Repetitions

i

i

P'. •

pij

s

1

2

1.0000

1.0000

3

2

3

.4915

.5000

2

2

22

.5085

.5000

0

3

4

.2443

.2500

2

3

5

.2472

.2500

0

4

5

.1231

.1250

2

4

22

.1212

.1250

0

5

6

.1874

.1875

2

5

7

.1829

.1875

0

6

7

.0928

.0938

1

6

22

.0946

.0938

0

7

8

.1403

.1406

1

7

21

.1354

.1406

0

8

9

.0719

.0703

1

8

21

.0684

.0703

0

9

10

.0352

.0352

1

9

21

.0367

.0352

0

10

11

.0184

.0176

1

10

18

.0168

.0176

0

11

12

.0089

.0088

0

11

22

.0095

.0088

1

12

13

.0089

.0088

3

13

A

.0089

.0088

0

B-88

14

15

.0127

.0132

1

15

16

.0257

.0268

2

16

17

*

.0132

0

16

22

.0257

.0264

1

17

16

*

.0132

0

18

19

.0168

.0176

3

19

A

.0168

.0176

0

20

15

.0130

.0132

2

21

22

.2405

.2461

4

A

B

.0257

.0264

0

B

14

.0127

.0132

0

B

20

.0130

.0132

0

I p. .s. . = 6.7983
E(l) = .1333
E(l)/u = .2060

33

B-89

Ucdule: 2

Procedure No.: 48

Hunter of ncces: 16

Hunter of arcs: 21

Huafcex of paths: 14

Hunter cf sctrce stm-ts.: 17

Average errcr found: 0.1530

Esrcentacs errors found: 4 7.40

B-90

Module 2 Procedure 48

100

Replications

100 Repetitions

i^

2

P*. •

p^

s . .

1

2

1.0000

1.0000

3

2

3

.4934

.5000

2

2

14

.5066

.5000

0

3

4

.2444

.2500

2

3

5

.2490

.2500

0

4

5

.1229

.1250

2

4

14

.1215

.1250

0

5

6

.1869

.1875

C

5

7

.1850

.1875

1

6

7

.1869

.1875

0

7

3

.3719

.3750

2

8

A

.3719

.3750

0

9

10

.3719

.3750

1

10

11

.1863

.1875

1

10

13

.1856

.1875

0

11

12

.0979

.0938

0

11

13

.0884

.0938

1

12

13

.0979

.0938

0

13

14

.3719

.3750

2

A

B

.3719

.3750

0

B

9

.3719

.3750

0

17

I Pi.s±. = 7.9063

E(l) = .1550

E(l)/U = .4651

B-91

Module: 2

Procedure No.: 79

N u & fc e r of d c d e s :
Hunter c f arcs:
N u n t s r of paths:

Uutther ci scace stats.
Average errci fcuad:
Perce ntacs e r r c c 5 found

13

14

D

1 1

0.

1379

53

. 34

B-92

1_

1

1

2

2

3

3

4

3

9

4

2

4

5

5

A

6

7

7

C

8

2

A

B

B

6

C

D

D

8

Y p. .s. . = 6.0000

E(l) = .1176
E(l)/u = .5455

Module 2 Procedure 79

100 Replications 100 Repetitions

P*

1.0000

1.0000

!ii

s . .
l3

1.0000

l

1.0000

2

.5000

2

1.0000

0

.3333

i

.3333

0

.3333

4

.3333

0

.3333

I

.3333

0

.3333

0

.3333

0

.3333

0

.3333

0

11

B-93

Mcdule:

Procedure No. :

86

tiuiter of ncces:

Hunter ci arcs:

Nuaber of paths:

Number cf scuce stats.:

Average srrci found:

Percentage

X. L. C jl c= j-JuU

30

34

6

33

0.20^2

31.55

B-94

Module 2

Procedure 86

_i

2

P'. •

p^

s . .

1

2

1.0000

1.0000

2

2

3

.4962

.5000

2

2

6

.5038

.5000

1

3

A

.4962

.5000

0

4

5

.4996

.5000

1

5

12

.2524

.2500

0

5

20

.2472

.2500

1

6

C

.5038

.5000

0

7

8

.5038

.5000

3

8

E

.5038

.5000

0

9

10

.5038

.5000

7

10

A

.5038

.5000

0

11

20

.5004

.5000

2

12

13

.2524

.2500

4

13

G

.2524

.2500

0

14

15

.2524

.2500

0

15

16

*

.2500

2

16

17

*

.1250

1

16

20

.2524

.2500

0

17

15

*

.0833

0

17

18

*

.0833

5

18

I

*

.0833

0

19

15

*

.0833

2

A

B

1.0000

1.0000

0

B

4

.4996

.5000

0

B-95

B

11

.5004

.5000

0

C

D

.5038

.5000

0

D

7

.5038

.5000

0

E

F

.5038

.5000

0

F

9

.5038

.5000

0

G

H

.2524

.2500

0

H

14

.2524

.2500

0

I

J

*

.0833

0

J

19

*

.0833

0
33

5" p. .s. . = 12.4582

E(l) = .2443
E(l)/u = .3775

B-96

Kcdule: 2

Procedure No. : 90

1/1

Nunher of ncces: 13

Nucher cf arcs : 1 8

Nuiter of paths: 8

II u a b e r cf source stats.: 23

Average errcr found: 0.0958

fsrcsntace errors found: 21.24

B-97

Module 2 Procedure 90

100

Replications

100 Repetitions

i

2

P*. •

l3.

!ii

s . .

1

2

1.0000

1.0000

2

2

3

.4925

.5000

1

2

11

.5075

.5000

0

3

4

.2427

.2500

1

3

5

.2498

.2500

0

4

5

.1249

.1250

1

4

11

.1178

.1250

2

5

A

.3747

.3750

0

6

7

*

.2500

3

7

8

*

.1875

3

7

11

.3747

.3750

0

8

7

*

.0938

8

8

9

*

.1875

1

9

A

*

.1875

0

.0

7

*

.2500

1

A

B

*

.3750

0

B

6

*

.2500

0

B

10

*

.2500

0

y p. .s . = 5.625
L ID iD

E(l) = .11029
E(l)/u = .2446

23

B-98

Module: 2

Procedure No . : 99

Number of nodes:
Number of ar cs :
Number of paths :
Number of source stmts. :
Average error found:
Percentage errors found:

25
30

10
23
0.1513

33.55
B-99

MODULE 2 Procedure 99

100

Replications

100 Repetitions

i

i

P'. ■
1J

!ii

s . .
ID

1

2

1.0000

1.0000

2

2

3

.4981

.5000

1

2

11

.5019

.5000

0

3

4

.2506

.2500

1

3

18

.2475

.2500

0

4

5

.1307

.1250

2

4

6

.1199

.1250

0

5

6

.0643

.0625

2

5

18

.0664

.0625

0

6

7

.6861

.6875

0

7

8

*

.6875

3

a

A

*

.6875

0

9

10

*

.6875

1

10

7

*

.3438

0

10

18

.6861

.6875

0

11

12

.5019

.5000

2

12

13

.2483

.2500

3

12

17

.2536

.2500

0

13

E

.2483

.2500

0

14

15

.2483

.2500

2

15

G

.2483

.2500

0

16

17

.2483

.2500

0

17

6

.5019

.5000

3

18

19

1.0000

B-

1.0000

-100

1

A

B

*

.6875

0

B

9

*

.6875

0

E

F

.2483

.2500

0

F

14

.2483

.2500

0

G

H

.2483

.2500

0

H

16

.2483

.2500

0
23

T p. .s. . = 10.625

E(l) = .20833

E(l)/U = .4620

B-101

tied ule:

Procedure No.

122

N u a 1 6 r cf nodes;
Nucher cf arcs:
Nuater oi paths:
Nucher cf scarce stats.
Average errct found:
P^rcentacs errors found

13
21
6

20

0. 1635

U2.99

B-102

Module 2 Procedure 122

100

Replications

100 Repetitions

i_

i

P'. •

!ii

s . .

1

2

1.0000

1.0000

3

2

3

.4945

.5000

1

2

12

.5055

.5000

1

3

4

.2480

.2500

1

3

5

.2465

.2500

1

4

5

.1232

.1250

2

4

12

.1248

.1250

1

5

6

*

.1875

0

5

8

.3697

.3750

4

6

A

*

.1875

0

7

5

*

.1875

0

8

C

.3697

.3750

0

9

10

.3697

.3750

5

10

E

.3697

.3750

0

11

12

.3697

.3750

I

A

3

*

.1875

0

B

7

*

.1875

0

C

D

.3697

.3750

0

D

9

.3697

.3750

0

E

F

.3697

.3750

0

F

11

.3697

.3750

0

20

7 p. .s. . = 8.625

E(l)

1691

E(l)/u - .4313

B-103

tlccule: 2

Procedure No. : 137

Nurrter of ncces:
Number cf arcs:
•iunter of paths:
liunter cf scurce stmts.:
Average errcr found:

rercentace

rou

13
17
11
23

0. 1 17
25. 12

B-104

MODULE 2 Procedure 137

100

Replications

100 Repetitions

i

i

P'. •

!ii

s . .

1

2

1.0000

1.0000

2

2

3

.4994

.5000

1

2

9

.5006

.5000

1

3

4

.2482

.2500

0

3

5

.2512

.2500

1

4

5

.2482

.2500

0

5

6

.4994

.5000

2

6

7

.2503

.2500

2

6

8

.2491

.2500

0

7

8

.1269

.1250

1

7

9

.1234

.1250

0

8

9

.1863

.1875

0

8

11

.1897

.1875

12

9

12

.8103

.8125

0

10

11

.8103

.8125

1

12

13

.8103

.8125

0

13

10

.8103

.8125

0

23

V p. .s. . = 8.0625

E(l)
E(l)/u

15809
3505

B-105

Module: 2

Procedure So.: 149

Hunter of nodes: 18

Hue t er of arcs : 25

Husher of paths: 9

Hunter of sciice stmts.: 35

Average error found: 0.2357

rsrcentac^ errors round: 3 4. 3 '4

B-106

Module 2 Procedure 149

100

Replications

100 Repetitions

i

i

P'. •
. x3

P. .

13

s . .

1

2

1,0000

1.0000

2

2

3

.4895

.5000

1

2

8

.5105

.5000

0

3

4

.2410

.2500

2

3

16

.2485

.2500

0

4

5

.1213

.1250

4

4

16

.1197

.1250

0

5

6

.0604

.0625

0

5

16

.0609

.0625

0

6

7

*

.0625

4

7

6

*

.03125

0

7

16

.0604

.0625

2

8

9

.5105

.5000

5

9

10

.5105

.5000

J

10

A

.5105

.5000

0

11

12

.5105

.5000

1

12

13

*

.5000

2

13

12

*

.3750

0

13

14

*

.5000

6

14

12

*

.3333

0

14

15

*

.5000

1

15

12

*

.2 500

0

B-107

15 16 .5105 .5000 3

A B .5105 .5000 0

B 11 .5105 .5000 J^

35

J p. .s. . = 13.8750

E(l) = .2721

E(l)/u = .3964

B-108

INITIAL DISTRIBUTION LIST

Copies

Mr. Richard Pariseau 4

Naval Air Development Center
Warminster, Pennsylvania

Defense Documentation Center 2

Cameron Station
Arlington, Virginia 22314

Naval Postgraduate School
Dean of Research

Knox Library 2

W. R. Church Computer Center Library 1

Prof. G. Bradley 1

CDR C. Gibfried 1

Prof. G. Howard 1

Prof. C. Jones 1

Prof. N. Schneidewind 12

U176713

DUDLEY KNOX LIBRARY -RESEARCH R EHOH a

5 6853 01060618 9

A//>

(J/7L ?