Structured Testing: Analysis and Extensions (Thesis)

Abstract:

Structured testing, also known as basis path testing, is a methodology
for software module testing based on the cyclomatic complexity measure
of McCabe. In this dissertation, we analyze the theoretical properties
of structured testing, describe the implementation of a system to support
structured testing, empirically evaluate the error detection performance
of structured testing, and extend the structured testing approach to cover
integration testing.
We exhibit a class of programs with unbounded complexity for which the
structured testing approach is both necessary and sufficient to ensure
correctness, and place structured testing in a hierarchy with other
structural testing criteria. We also discuss Weyuker's axioms for testing
criteria, and show that a variant of structured testing in which only
executable paths are considered satisfies those axioms.
We describe an automated system to support structured testing for the
C language. We present a technique for assessing and improving a test
suite with respect to basis path coverage, based on source code
instrumentation and execution trace analysis.
We present an empirical study comparing the error detection effectiveness
of structured testing, all-uses data flow coverage, and branch coverage.
Structured testing outperformed branch coverage, was comparable to all-uses,
and was more robust with respect to test set minimization than either
branch coverage or all-uses.
We extend structured testing to support software integration testing.
We present a mathematical model for integration testing, and derive
an integration test sufficiency criterion from that model. We motivate
the criterion from a practical perspective, and demonstrate its relationship
to structured module testing. We extend our automated system to assess
test suites with respect to our integration test criterion, and suggest
extensions of the core method to support incremental integration and
object-oriented programming.