Phyllis G Frankl.

Data flow testing in the presence of unexecutable paths online

. (page 2 of 2)
Online LibraryPhyllis G FranklData flow testing in the presence of unexecutable paths → online text (page 2 of 2)
Font size
QR-code for this ebook

both executable. This would be the case, for example, in an environment in which uninitialized
variables receive arbitrary values. Since node 3 is unexecutable, the only executable definition-use
associations are (1,2, input), and (2, (2,4), x). Let T be a test which executes P = {(1,2,4,5,7,8)}.
Then T satisfies (all-p-uses)*. (all-p-uses/some-c-uses)*, and (all-uses)', but does not satisfy (all-
edges)* or (all-nodes)*.

Notice that the subprogram in Figure 8 has a data flow anomaly [OST76]. We shall see below
that this is not a mere coincidence, but that rather, it is this particular kind of anomaly which
prevents the inclusions from holding.


.© -nIcU to

Fl^^^t ?a.



respect to


























Figure 7b


rtc^ (y)-

VtUi^) (5


r»teU CVoo )

WriTtU L loar )

Flui^RE ?

- 11 -

The rest of the non-inclusions follow from the incomparability and strictness proofs in
[RAP85]. ■

It seems discouraging that (all-p-uses)* fails to include (all-edges)'. Data flow testing was
developed in order to "bridge the gap" between branch testing and path testing. Since many "real-
life" subprograms cannot be adequately tested using the unstarred versions of the data flow criteria,
one would hope that the FDF criteria would "bridge the gap" between (all-edges)' and (all-paths)*.
We have seen that this is not the case. We next show that for a certain class of "well-behaved"
subprograms, any test which satisfies (all-p-uses)' satisfies (all-edges)*.

DEFINITION: We will say that a subprogram P satisfies the No-Feasible-Undefined-P-uses property
(NFUP) if and only if for every executable edge (i,j) in P having a p-use of a variable x there is
some executable path from the start node to edge (i,j) which contains a global definition of x.

We note that it is quite reasonable to expect subprograms to have property NFUP. If (i,j) is an
edge which causes NFUP to fail, then any input which causes (i,j) to be executed will involve
referencing an uninitialized variable.
THEOREM 2: For the class of subprograms which satisfy NFUP, (all-p-uses)* => (all-edges)*.

PROOF: Let P be a subprogram satisfying NFUP, let T be a test which satisfies (all-p-uses)* for P,
let P be the set of paths executed by T, and let (i,j) be an executable edge in P. Suppose (i,j) has a
p-use of a variable x. By hypothesis there is an executable path -n from the start node to (i,j) which
includes a global definition of x. Let n be the last node in -n having a global definition of x. Then
(n, (i,j), x) is an executable definition-p-use association so it is covered by p. Hence (i,j) is covered
by P.

If (i,j) has no p-uses. then the result follows by a straight-forward modification of the
corresponding part of the proof of (allp-uses) => (all-edges) [RAP85]. ■

In [RAP85] the class of subprograms to which data-flow testing applies is restricted to those
subprograms satisfying the No-Syntactic-Undefined-P-use Property (NSUP):

For every p-use of a variable x on an edge (i,j) in P, there is some path from the start node to
edge (i,j) which contains a global definition of x.

- 12 -

This restriction was necessary in order to insure that all-p-uses => all-edges. NFUP is a strengthening
of NSUP which takes into account the fact that in subprograms satisfying NSUP, the only paths tt
from the entry node to some p-use of x such that x has a global definition in some node in it might
be unexecutable.

It is tempting to restrict the class of programs to which the FDF criteria apply to those satisfying
NFUP. It is our feeling however that while one can live with the undecidability of the adequate test
recognition problem and perhaps (albeit very uncomfortably) with the undecidability of the adequate
test existence problem, one should at least be able to decide algorithmically whether a given testing
strategy applies co a given subprogram Since it is undecidabie whether a given subprogram satisfies
NFUP, we refrain from requiring this property of subprograms to be tested.

Another possible way to lorce (all-p-uses)' to include (all-edges)* would be to require
subprograms to satisfy the No-Anomalies Property (NA):

Every path from the start node to a use of a variable x must contain a definition of x.

Osterweil and Fosdick [OST76] consider any subprogram not satisfying this property to have data-
flow anomaly indicative of possible subprogram error Since NA is a purely syntactic property and
NA implies NFUP we could restrict FDF testing to subprograms satisfying this property. We feel
that this is overly restrictive, since many perfectly good subprograms fail to satisfy NA.

One way to force .NA to be satisfied is to give the entry node a definition of each variable.
Another approach is to perform FDF testing in conjunction with a check for data-flow anomalies.
For any subprogram which satisfies NA and any test T which satisfies (all-p-uses)* the user will be
assured that T satisfies (all-edges)* . In case NA does not hold, the user should explicitly check
whether (all-edges)* is satisfied and if necessary add more test data or inspect the subprogram for
references of uninitialized variables.

4. A Modification of the All-du-paths Criterion

We have seen above that (all-du-paths)* fails to include (all-uses)*. This is because in some
programs the only executable def-clear paths with respect to a variable x from some definition of x to

- 13 -

some use of x are paths with non-simple cycles. In this section we define a modification of the all-
du-paths criterion which includes all-uses and whose starred version includes (all-uses)*.

DEFINITION: Let -ir^ = (n|,n, nj be a du-path with respect to x. Then cycle-extension(iT,x)

= {def-clear paths with respect to x of the form (X,,X, X^) where each X, is a path of length

greater than or equal to one, beginning and ending with n,.}

Informally, cycle-extension(iT,x) is the set of def-clear paths with respect to x formed by
following IT, taking "side-trips" which traverse cycles zero or more times. For any du-path i: with
respect to x, ir € cycle-extension(iT,x).

Our modified version of all-du-paths requires that one element of the cycle-extension of each
du-path be selected. We now define this criterion formally and investigate some of its properties.
DEFINITION: A test T which executes the set P of paths satisfies the cycle-extended-du-paths
criterion for a program P if and only if for each variable x and each du-path tt with respect to x, P
covers some path it' € cycle-extension(ir,x).

LEMMA: Let it be a def-clear path with respect to x from a node i containing a definition of x to a
node j or edge (j,k) containing a use of x. Then there is a (not necessarily unique) du-path it' such
that TT € cycle-extension('7r',x).

PROOF: Let -rr = («,,«,, ... ,n.) be a definition-clear path with respect to x. The following

algorithm decomposes -n into the form (X|,X, X,,) where for 1 s j < h all-uses since the program in Figure 9 has no unexecutable paths. ■

5. Conclusions

We have introduced a new family of path selection criteria derived from the data flow testing
criteria and explored the relationships among them. These criteria, the feasible data flow testing
criteria, are obtained from the corresponding data flow testing criteria by eliminating unexecutable
associations from consideration.

For a large class of "well-behaved" programs, the FDF criteria (all-p-uses)*, (all-p-uses/some-
c-uses)*, and (all-uses)* "bridge the gap" between (all-branches)* and (all-paths)* in the same way

- 16 -

that the corresponding DF criteria do. For certain programs with anomalies however, there are tests
which satisfy (all-p-uses)' without satisfying (all-edges)*.

Although (all-paths) => (all-du-paths) => (all-uses), (all-du-paths)' does not even include (all-
nodes)*. We have defined a new criterion, (cycle-extended-du-paths) such that (all-paths) => (cycle-
extended-du-paths) => (all-uses) and (all-paths)' => (cycle-extended-du-paths)* => (all-uses)*.

The advantage of the FDF criteria over the DF criteria is that they satisfy the applicability
property: for every subprogram P and every FDF criterion C there is some set of paths which is C-
adequate for P. The DF criteria do not satisfy this property. The disadvantage of the FDF criteria is
that it is undecidable whether a particular set of paths is C-adequatc for P. Thus, in deciding
whether to use the DF criteria or the FDF criteria, one is faced wiih a trade-off between applicability
and automatability.

Although it is in general undecidable whether a given association is executable, it is often easy
for a person looking at a subprogram to determine whether or not a particular association is
executable. Sometimes this requires very little semantic information. For example, any program
with a for loop in which the upper bound is always greater than or equal to the lower bound has an
unexecutable definition-p-use association. In other cases, determining whether a given association is
executable seems to require "high-level" understanding of how the subprogram and other
subprograms which it calls operate.

We plan to enhance ASSET, our data flow testing tool, by adding heuristics which attempt to
determine which of the required associations are unexecutable. When the heuristics cannot decide
whether or not a particular association is executable, the person using the tool will have to intervene.
We hope that this approach will prove to be a practical way to preserve the applicability property
enjoyed by the FDF criteria while sacrificing automatability to as small extent as possible.

- 17-

6. References

[CLA85] L.A. Clarke, A. Podgurski, D.J. Richardson and S.J. Zeil, "A Comparison of Data Flow
Path Selection Criteria", 8th IEEE International Conference on Software Engineering,
August, 1985, London, pp. 244-251.

[FRA85a] P.G. Frankl, S.N. Weiss and E.J. Weyuker, "ASSET: A System to Select and Evaluate
Tests", Proceedings of the IEEE Conference on Software Tools, New York, April 1985.

[FRA85b] P.G. Frankl and E.J. Weyuker, "A Data Flow Testing Tool," Proceedings of IEEE Softfair
II, San Francisco, Dec. 1985.

[GIR85] M.R. Girgis and M.R. Woodward, "An Integrated System for Program Testing Using
Weak Mutation and Data Flow Analysis," 8th IEEE International Conference on Software
Engineering, August, 1985, London, pp. 313-319.

[G0075] J.B. Goodenough and S.L Gerhart, "Toward a Theory of Test Data Selection," IEEE
Transactions on Software Engineering, SE-1,2, June 1975.

[HEC77] M. S. Hecht, Flow Analysis of Computer Programs, North Holland, 1977.

[HOW76] W.E. Howden, "Reliability of the Path Analysis Testing Strategy ', IEEE Transactions on
Software Engineering, Vol. SE-2,3, 1976, pp. 208-215.

[HOW78] W.E. Howden, "A Survey of Dynamic Analysis Methods" in Tutorial Software Testing and
Validation Techniques, eds. E. Miller and W.E. Howden, IEEE Computer Society, 1978.

[HL)A75J J.C. Huang, " An Approach to Program Testing," ACM Computing Surveys, 7(3), Sept.

1975, pp. 113-128.

[KOR85] B. Korel and J. Laski, "A tool for Data Flow Oriented Program Testing", Proceedings of
IEEE Softfair II, San Francisco, Dec. 1985.

[LAS831 J. W. Laski and B. Korel, "A Data Flow Oriented Program Testing Strategy," IEEE Trans.
Software Eng., Vol. SE-9, No. 3, May 1983, pp. 347-354.

[MIL74] E. F. Miller, Jr. M. R. Paige, J. P. Benson, and W. R. Wisehart, "Structural Techniques
of Program Validation," Dig. Compcon, Spring 1974, pp. 161-164.

[NTA84] S. Ntafos, "On Required Element Testing," IEEE Trans. Software Eng., Vol. SE-10, No. 6,
Nov. 1984, pp. 795-803.

[OST76] L.J. Osterweil and L. D Fosdick, "DAVE - A Validation Error Detection and
Documentation System for Fortran Programs," Software Practice and Experience, Oct-Dec

1976, pp. 473-486.

[RAP82] S. Rapps and E. J. Weyuker, "Data Flow Analysis Techniques for Program Test Data
Selection," Proceedings Sixth Int'l Conference on Software Eng., Tokyo, Japan, Sept. 1982,
pp. 272-278.

[RAP85J S. Rapps and E.J. Weyuker, "Selecting Software Test Data Using Data Flow
Information", IEEE Trans. Sofrvxare Eng., Vol. SE-11, No. 4, April 1985, pp. 367-375.

[SCH73] M. Schaeffer, A Mathematical Theory of Global Program Optimization, Prentice-Hall,
Englewood Cliffs, N. J., 1973.

[WEY85] E.J. Weyuker, "Axiomatizing Software Test Data Adequacy," Computer Science
Department Technical Report #99, Courant Institute of Mathematical Sciences, New
York, NY, Jan. 1984, revised Aug. 1985.

[WOO80] M. R. Woodward, D. Hedley, and M. A. Hennell, "Experience with Path Analysis and
Testing of Programs," IEEE Trans. Software Eng., Vol. SE-6, May 1980, pp. 278-286.

This book may be kept ^PR 1 1 1986


A fine will be chciged for each day the hook is kept oveitime.




Frankl, Phyllis G

Data flow testing in the
presence of unexecutable
paths. C.2

Frankl, Phyllis G
Data flow testing in the
P^f^^"ce of unexecutable


N.Y.U. Courant Institute of

Mathematical Sciences

251 Mercer St.
New York, N. Y. 10012


Online LibraryPhyllis G FranklData flow testing in the presence of unexecutable paths → online text (page 2 of 2)