1.

PATH TESTING

7.1 Path, Nodes, and Links

A path through a program is a sequence of instructions or statements that starts at an
entry, junction, or decision and ends at another, or possibly the same, junction, decision,
or exit. Paths consist of segments. The smallest segment is a link.

A path segment is a succession of consecutive links that belongs to some path. The
length of a path is measured by the number of links in it and not by the number of
instructions or statements executed along the path.

Links are named by the pair of nodes they join, the name of a path is the name of the
nodes along the path. A path has a loop in it if any node (link) name is repeated.

The term entry/exit path and complete path are also used in the literature to denote
a path that starts at an entry and goes to an exit.

7.2 Multi-Entry / Multi-Exit Routines

We might want to jump out of a routine when an illogical condition has been detected for
which it is clear that any further processing along the path could damage the system’s
operation or data.

Under such circumstances, the normal return path must be bypassed. In such cases,
though, there is only one place to go – to the system’s recovery-processing software.

If the routine performs several variations on the same processing and it is effective to
bypass part of the processing, the correct way to design the routine is to provide an entry
parameter that within the routine, directs the control flow to the proper point.

2
 Similarly, if a routine can have several different kinds of outcomes, then an exit pa- rameter
should be used. Another alternative is to encapsulate the common parts into subroutines.

Instead of using direct linkage between multiple exits and entrances, we handle the control
flow by examining the values of the exit parameter that can serve as an entry parameter for
the next routine or a return parameter for the calling routine.

The trouble with multi-entry and multi-exit routines is that it can be very difficult
to determine what the inter-process control flow is, and consequently it is easy to miss
important test cases. The use of multi-entry and multi-exit routines increases the number of
entries and exits and therefore the number of interfaces.

7.3 Fundamental Path Selection Criteria

There are many paths between the entry and exit of a typical routine. Every decision
doubles the number of potential paths, and every loop multiplies the number of potential
paths by the number of different iteration values possible for the loop.

A lavish test approach might consist of testing all paths, but that would not be a complete
test, because a bug could create unwanted paths are right doesn’t mean that the routine
is doing the required processing along those paths.

1. Exercise every path from entry to exit.

2. Exercise every statement or instruction at least once.

3. Exercise every branch and case statement, in each direction, at least once.

If prescription 1 is followed, then prescriptions 2 and 3 are automatically followed; but

prescription 1 is impractical for most routines. It can be done only for routines that have
no loops, in which case it includes all the cases included in prescriptions 2 and 3. Prescriptions
2 and 3 might appear to be equivalent, but they are not.

A Static analysis cannot determine whether a piece of code is or is not reachable. Only
a Dynamic analysis can determine whether code is reachable or not and therefore
distinguish between the ideal structure we think we have and the actual, buggy structure.

3.
7.4 Path-Testing Criteria
Any testing strategy based on paths must at least both exercise every instruction and
take branches in all directions. A set of tests that does this is not complete in an absolute
sense, but it is complete in the sense that anything less must leave something untested.

1. Path Testing (P-∞): Execute all possible control flow paths through the pro- gram:
typically, this is restricted to all possible entry / exit paths through the program. If
we achieve this prescription, we are said to have achieved 100% path coverage.
This is the strongest criterion in the path-testing strategy family: it is generally
impossible to achieve.

2. Statement Testing (P1) (C1): Execute all statements in the program at least
once under some test. If we do enough tests to achieve this, we are said to have
achieved 100% statement coverage. An alternate, equivalent characterization is
to say that we have achieved 100% node coverage. This is the weakest criterion
in the family.

3. Branch Testing (P2) (C2): Execute enough tests to assure that every branch
alternative has been exercised at least once under some test. If we do enough tests to
achive this prescription, then we have achieved 100% branch coverage. An
alternative characterization is to say that we have achieved 100% link cover-
age. For structured software, branch testing and therefore branch coverage strictly
includes statement coverage.

7.5 Common Sense and Strategies

Not testing a piece of code leaves a residue of bugs in the program in proportion to the size
of the untested code and the probability of bugs.

The high-probability paths are always thoroughly tested if only to demonstrate that
the system worked properly.

Logic errors and fuzzy thinking are inversely proportional to the probability of the
path’s execution. The subjective probability of executing a path as seen by the routine’s
designer and its objective execution probability are far apart.

The subjective evaluation of the importance of a code segment as judged by its pro-
grammer is biased by aesthetic sense, ego, and familiarity.

4.
7.6 Which Paths
We must pick enough paths to achieve C1 + C2. Start at the beginning and take the
most obvious path to the exit – it typically corresponds to the normal path.

Figure 7.1: An Example of Path Selection

Does every decision have a YES and a NO in its column? (C2). Has every case of all case
statements been marked? (C2). Is every three-way branch covered? (C2). Is every link
(process) covered at least once? (C1).

Select successive paths as small variations of previous paths:

1. Small changes from path to path means small, easily documented, and gradual changes
in the test setup. Setting up long, complicated paths that share nothing with other
test cases is also a lot of extra work.

2. Testing is experimenting. Good experiments rely on changing only one thing at a time.
The more you change from test to test, the likelier you are to get confused.

3. The costs of extra paths are a few more microseconds of computer time, the time
to run another case, and the cost of additional documentation. Many more and
different kinds of tests are required beyond path testing. A few extra paths represent
only a small increment in the total test labor.

The path selection rules can be revised as follows:

1. Pick the simplest, functionally sensible entry/exit path.

5.
 2. Pick additional paths as small variations from previous paths. Pick paths that do
not have loops rather than paths that do. Favor short paths over long paths, simple
paths over complicated paths, and paths that make sense over paths that don’t.

3. Pick additional pats that have no obvious functional meaning only if it’s necessary
to provide coverage.

4. Be comfortable with your chosen paths. Play your hunches and give your intuition free
reigns as long as you achieve C1+C2.

PATH INSTRUMENTATION

8.1 The Problem

The outcome of a test is what we expect to happen as a result of the test. The expected
outcome includes any expected changes or the lack of change.

We run the test, observe the actual out-

come, and compare that outcome to the
expected outcome. We can say only say
that some of the necessary conditions for
passing are satisfied, but the conditions are
not sufficient because the desired outcome
Figure 8.1: Coincidental Correctness could have been achieved for the wrong
reason. This situation is called Coinci-
dental Correctness.

6
 Path Instrumentation is what we have to do to confirm that the outcome was achieved
by the intended path.

8.2 General Strategy

An Interpretive Trace Program is one that executes every statement in order and
record the intermediate values of all calculations, the statement labels traversed, etc.

If we run the tested routine under a trace, then we have all the information we need to
confirm the outcome and furthermore, to confirm that it was achieved by the intended path.

8.3 Link Markers

Figure 8.2: Single Link Marker Instrumentation

A simple and effective form of instrumentation is called a traversal market or link

marker, figure 8.2. Name every link by a lowercase letter. Instrument the links so that
the links name recorded when the link is executed.

The succession of letters produced in going from the routine’s entry to its exit should,
if there are no bugs, exactly correspond to the path name.

Unfortunately, a single link marker may not do the trick because links can be chewed
open by bugs. The situation is illustrated in figure8.3a.

We intended to traverse the jkm path, but because of a rampaging GOTO in the middle
of the m link, we go to process B. If coincidental correctness is against us, the outcomes
will be the same and we won’t know about the bug.
7.
 The solution is to implement two markers pre link: one at the beginning of each link
and one at the end; (figure 8.3b). The two link markers now specific the path name and
confirm both the beginning and end of the link.

8.4 Link Counter

A less disruptive instrumentation method is based counters. Instead of a unique link
name to be pushed into a string when the link is traversed, we simply increment a link
counter. We now confirm that the path length is as expected.

8.
 (a) Why Single Link Markers Aren’t Enough (b) Double Link Markers

Figure 8.3: Overcoming Coincidental Correctness of Single Link Marker using Double
Link Markers

The same problem that led us to double link markers also leads us to double link counters
with these in place, we expect an even count that is exactly double the expected path length.
The same reasoning as before leads us to double link counters – one at the start of the link
and one at the end.

The checkout procedure then consist of answering the following questions:

1. Do the begin-link counter values equal the end-link counter values for all links?

2. Do the input-link count of every decision equal the sum of the link counts of the
output links from the decision?

3. Do the sum of the input-link counts for a junction equal the output link count for
that junction?

4. Do the counts match the values you predicted when you designed the test?

9.
10.
TRANSACTION FLOW TESTING

9.1 Get the Transaction-Flows

Complicated systems that process many different complicated transactions should have
explicit representations of the transaction flows, or the equivalent, documented.

Transaction flows can be mapped into programs; they can be described in a PDL
(Program Description Language).

It is correct and effective to have sub flows analogous to subroutines in control flow-
graphs.

The first step in using transaction flows as a basis for system testing is to get the
transaction flows.

9.2 Inspection, Review, Walkthrough

Transaction-flows are a natural agenda for system reviews or inspections.

1. In conducting the walkthrough, you should:

(a) Discuss enough transaction types to account for 98%-99% of the transaction
the system is expected to process.
(b) Discuss paths through flows in functional rather than technical terms.
(c) Ask the designers to relate every flow of the specification and to show how
that transaction, directly or indirectly, follows from the requirements.

2. Make transaction-flow testing the cornerstone of system testing. For this you need
enough test to achive C1 and C2 coverage of the complete set of transaction flow-
graphs.

11
 3. Select additional transaction–flow paths (beyond C1 + C2) for loops, extreme value
and domain boundaries.

4. Select additional paths for weired cases and very long, potentially troublesome
transactions with high risks and potential consequential damage.

5. Publish and distribute the selected test paths through the transaction-flows as early as
possible so that they will exert the maximum beneficial effect on the project.

6. Have the buyer agree that the selected set of test paths through the transaction
flows constitute an adequate system function test. Negotiate a subset of these paths
to be used as the basis for a formal acceptance test.

7. Tell the designers which paths will be used for testing but not the details of the
test cases that forces those paths.

9.3 Path Selection

Start with a covering set of tests (C1 + C2) using the analogous criteria you used for
structural path testing, but don’t expect to find too many bugs on such paths.

Select a covering set of paths based on functionally sensible transactions as you would for
control flowgraphs. Confirm these with the designers.

Try to find the most tortuous, longest, strangest path from the entry to the exit of the
transaction flow.

Create a catalog of these weired paths. Go over them not just with the high-level designer
who laid out the transaction flows, but with the next-level designers who are implementing
the modules that will process the transaction.

The act of discussing the weired paths will expose missing interlocks, duplicated in- terlocks,
interface problems, programs working at cross-purpose, duplicated processing a lot of stuff
that would otherwise have shown up only during the final acceptance test, or worse, after the
system was operating.

This procedure is best done early in the game, while the system design is still in
progress, before processing module have been coded.

12.
9.4 Sensitization
Most of the normal paths are very easy to sensitize 80% - 95% transaction flow coverage
(C1 - C2) is usually easy to achieve. The remaining small percentage is often very difficult,
if not impossible, to achieve by fair means.

While the simple paths are easy to sensitize there are many of them, so that there’s a
lot of tedium in test design. Usually, just identifying the normal path is enough to
sensitizing. It fact, many test designers who do mainly transaction-flow testing are not
even conscious of a sensitization issue.

9.5 Instrumentation
The information of the path taken for a given transaction must be kept with that
transaction. It can be recorded either by a central transaction dispatcher (if there is one)
or by the individual processing modules.

You need a trace of all the processing steps for the transaction, the queues on which it
resided, and the entries and exits to and from the dispatcher.

In some systems, such traces are provided by the operating system. In other systems, such
as communications systems or most secure systems, a running log that contains exactly this
information is maintained as part of normal processing.

Another, better alternative is to make the instrumentation part of the system design.
Augment the design as needed to provide complete transaction-flow tracing for all trans-
actions. They payoff in system debugging and performance testing alone is worth the
effort for most systems.

9.6 Test Databases

About 30%-40% of the effort of transaction-flow test design is the design and mainte- nance
of the test database(s).

The first error is to be unaware that there’s a test database to be designed. The
result is that every programmer and tester design his own, unique database, which is
incompatible with all other programmer’s and tester’s needs. The consequence is that every
tester (independent or programmer) needs exclusive use of the entire system.

13.
 Furthermore, many of the tests are configuration-sensitive, so there’s no way to port
one set of tests over from another suite. The independent testers need more elaborate
test setups than do the programmers, the responsibility is given to the test group.

That’s when the second error occurs. In order to avoid a repetition of the previous chaos,
it is decided that there will be one comprehensive database that will satisfy all testing needs.

The design of these databases is no less important than the design of the system data
structures. It requires talented, mature, diplomatic, experienced designers-experienced both
in the system design and in test design.

9.7 Execution
If you’re going to do transaction-flow testing for a system of any size, be committed to test
execution automation from the start.

If more than a few hundred test cases are required to achive C1 + C2 transaction-flow
testing if you don’t have the time and resources to almost completely automate all test
execution.

Transaction-flow testing with the intention of achieving C1 + C2 usually leads to a big

(four‒to‒five fold)increase in the number of test cases. Without execution automation
you can’t expect to do it right.

14.
DATA FLOW TESTING

10.1 GENERAL
Data flow testing strategies are structural strategies. This is only one family of an
infinite number of families of possible test strategies. Ntafos (NTAF84B) generalizes the
idea by defining required element testing as a way of generating gamily of test strategies
based on a structural characterization of the way test cases are to be defined and a
functional characterization that test cases must satisfy.

In path-testing strategies, the only structural characteristic used was the raw program-
control Flowgraph without consideration of what happened on those links. In contrast to the
path-testing strategies, data-flow strategies take into account what happens to data objects
on the links in addition to the raw connectivity of graph.

In other words, data flow strategies require data -flow link weights (d,k,u,c,p). Data-
flow testing strategies are based on selecting test path segments (also call ed subpaths)
that satisfy some characteristic of data flow for all data objects.

A strategy X is stronger than another strategy Y if all test cases produced under Y
are included in those produced under X – conversely for weaker. All structural strategies are
weaker than total path testing. Data-flow testing strategies provide one set of families that
fill the gap.

10.2 TERMINOLOGY
A Definition-Clear Path Segment: A Definition –clear path segment is a connected
sequence of links such that X is defined on the first link and not redefined or killed on
any subsequent link of that path segment.

15
A Loop-Free Path Segment: A loop-free path segment is a path segment for which
every node is visited at most once.

A Simple Path Segment: A simple path segment is a path segment in which at most
one node is visited twice.

A du Path: A du path from node i to k is a path segment, such that if the last link has
a computational use of X, then the path is simple and definition-clear; if the penultimate
node is j – that is, the path is (i,p,q, . . . ,r,s,t,j,k) and link (j,k) has a predicate use –
then the path from I to j is both loop-free and definition-clear.

10.3 THE STRATEGIES

The strategies differ as to whether or not all paths of a given type are required or
only one path of that type – that is, all predicate uses versus at least one predicate use;
all computational uses versus at least one computational use; both computational and
predicate uses versus either one or the other.

All-du Paths (ADUP): The all-du-paths strategy is the strongest data-flow testing
strategy. It requires that every du path from every definition of every variable to every
use of that definition be exercised under some test.

The all-du-paths strategy is a strong criterion, but it does not take as many tests as it might
seem at first because any one test simultaneously satisfies the criterion for several definitions
and uses of several different variables.

All-Uses Strategy (AU): We can reduce the number of test cases by asking that the
test set include at least one path segment from every definition to every use that can be
reached by that definition – this is called all-uses strategy.

The strategy is that at least one definition-clear path from every definition of every variable
to every use of that definition be exercised under some test.

All-p-Uses / Some-c-Uses (APU+C) and All-c-Uses / Some-p-Uses (ACU+P)

Strategies: The APU+C strategy is defined as, for eery variable and every definition
of that variable, include at least one definition-free path from the definition to every
predicate use; if there are definition of the variable that are not covered by the above
prescription, then add computational-use test cases as required to cover every definition.

16.
 The ACU+P strategy reverse the bias: first ensure coverage by computational-use
cases and if any definition is not covered by the previously selected paths, and such
predicate-use cases as are needed to assure that every definition is included in some test.

The APU+C is stronger than branch coverage but ACU+P may be weaker than, or
incomparable to, branch coverage.

All-Definition Strategy (AD): The AD strategy asks only that every definition of every
variable be covered by at least one use of the variable, be that uase a computational use or
a predicate use.

All-Predicate-Uses (APU), All-Computational Uses (ACU) Strategies: The APU

strategy is derived from APU+C strategy by dropping the requirement that we include
a c-use for the variable if there are no p-uses for the variable following each
definition. It is intuitively obvious that APU is weaker than APU+C.

The ACU strategy is derived from ACU+P strategy by dropping the requirement that
we include a p-use for the variable if there are no c-uses instances following a definition.
It is intuitively obvious that ACU is weaker than ACU+P.

Ordering the Strategies:

Figure 10.1: Relative Strength of Structural Test Strategies

17.
10.4 SLICING, DICING, DATA FLOW and DEBUG-
GING:
Testing in a maintenance context is not the same as testing new code – for which most
testing theory and testing strategies have been developed. It is interesting to note that
the three concerns come together in the context of data-flow testing techniques(KORE85,
LASK83, LYLE88, OSTR88B).

A (static) program slice (WEIS82) is a part of a program defined with respect to a given
variable X (where X is a simple variable or a data vector) and a statement i: it is the set of
all statements that could affect the value of X at statement i – where the influence of a
faulty statement could result from an improper computational use or predicate use of
some other variables at prior statements. If X is incorrect statement i, it follows that the
bug must be in the program slice for X with respect to i.

A program dice(LYLE87) is a part of a slice in which all statements which are known to
be correct have been removed.

Debugging can be modeled as an iterative procedure in which slices are further refined by
dicing, where the dicing information is obtained from ad hoc tests aimed primarily at
eliminating possibilities. Debugging ends when the dice has been reduced to the one faulty
statement.

Dynamic Slicing (KORE88C) is refinement of static slicing in which only statements

on achievable paths to the statement in question are included.

18.
DOMAIN TESTING

11.1 Overview
Domains are defined by their boundaries; therefore, domain testing concentrates test
points on or near boundaries. Classify what can go wrong with boundaries, then define a test
strategy for each case. Pick enough points to test for all recognized kinds of boundary errors.

Because every boundary serves at least two different domains, test points used to check
one domain can also be used to check adjacent domains. Remove redundant test points. Run
the test and by posttest analysis determine if any boundaries are fault and if so, how.
Run enough tests to verify every boundary of every domain.

11.2 Domain Bugs and how to test for them

General
An interior point is a point in the domain such that all points within an arbitrary small
distance (called an epsilon neighborhood ) are also in the domain.

A boundary point is one such that within an epsilon neighborhood there are points
both in the domain and not in the domain.

An extreme point is a point that does not lie between any two other arbitrary but
distinct points of a domain.

An on point is a point on the boundary, If the domain boundary is closed, an off point
is a point near the boundary but in the adjacent domain. If the boundary is open,

19
an off point is a point near the boundary but in the domain being tested. (COOOOI –
Closed Off Outside, Open Off Inside).

Testing One-Dimensional Domains

The figure 11.1a shows possible domain bugs for a one-dimensional open domain bound-
ary. The closure can be wrong or the boundary can be shifted one way or the other, we
can be missing a boundary, or we can have an extra boundary.

For closed domains look at the figure 11.1b. As for the open boundary, a test point on
the boundary detects the closure bug. The rest of the cases are similar to the open
boundary, expect now the strategy requires off points just outside the dom ain.

(a) Open Boundaries (b) Closed Boundaries

Figure 11.1: One-Dimensional Domain Bugs

Testing Two-Dimensional Domains

The figure 11.2 shows domain boundary bugs for two-dimensional domains. A and B are
adjacent domains and the boundary is closed with respect to A, which means that it is
open with respect to B.

Closure Bug: The figure 11.2 shows a fault closure, such as might be caused by using
a wrong operator. The two on points detect this bug because those values will get B
rather than A processing.

Shifted Boundary: In the figure 11.2 the bug is a shift up, which converts part of
domain B into A processing, denoted by A. This result is caused by an incorrect constant
in a predicate, such as x + y ≥ 17 when x + y ≥ 7 was intended. The off point catches
this bug.

20.
Tilted Boundary: A tilted boundary occurs when coefficient in the boundary inequal-
ity are wrong. For example, 3x + 7y >17 when 7x + 3y >17.

Figure 11.2: Two-Dimensional Domain Bugs

Extra Boundary: An extra boundary is created by an extra predicate. An extra boundary

will slice through many different domains and will therefore cause many test failures for
the same bug.

Missing Boundary: A missing boundary is created by leaving a boundary predicate out.

A missing boundary will merge different domains and as the extra boundary can, will
cause many test failures although there is only one bug.

Equality and Inequality Predicates

Equality predicates such as x + y = 17 define lower-dimensional domains. If there
are two input variables, a two-dimensional space, an equality predicate defines a line – a
one-dimensional domain. Similarly, an equality predicate in three dimensions defines a
planar domain.

There is a pathological situation in which the bug causes the boundary to go through
the two selected off points: it can be detected by another on point at the intersection
between the correct domain line and the two off points: it can be detected by another on
point at the intersection between the correct domain line and the two off point.

Because such bugs require careful design and because our failure to catch them depends
on an unfortunate choice of the two off points, they can be ignored.

21.
Testing n-Dimensional Domains
For domains defined over an n-dimensional input space with p boundary segments, the
domain testing strategy generalizes to require at most (n+1)p test points per domain,
consisting of n on points and one off point.

22.
INTERFACE TESTING

12.1 General
Components A and B have been demonstrated to satisfy their component tests, and as part
of the act of integrating them we want to investigte possible inconsistencies across their
interface.

Although the interface between two components can be a subroutine call shared data
objects, values left in registers or global variables, or some combination thereof.

It’s convenient to talk about the interface as if it is a subroutine call.

We’re looking for bugs in the “call” when we do interface testing.

Let’s assume that the call sequence is correct and that are no type incompatibilities.

What left is a possible disagrement about domains - the variable’s domain as seen by
tge caller and called routine.

For a single variable, the domain span is the set of numbers between ( and including )
the smallest value and the largest value.

For every input variable we want ( at least ) compatibility domain span and compatible
closure.

Domains need not be equal to be compatible.

23
12.2 Domains and Range
The set of output values produced by a function is called the range of the function,
in contrast with the domain, which is the set of input values over which the function is defined.

For most testing, our aim has been to specify input values and to predict and / or
confirm output values that result from those inputs.

Interface testing requires that we select the output values of the calling routine.

A more precise statement of the kind of compatibility needed between caller and called
is to say that the caller’s range must be compatible with the called routine’s domain.

An interface test consist of exploring the correctness of the following mappings:

CALLER DOMAIN −→ CALLER RANGE ( CALLER UNIT TEST)

CALLER RANGE −→ CALLED DOMAIN (INTEGRATION TEST)

CALLED DOMAIN −→ CALLED RANGE ( CALLED UNIT TEST)

12.3 Closure Compatibility

Assume that the caller’s range and the called domain spans the same numbers say, 0
to 17.

Figure 12.1: Range/Domain Closure Compatibility

The above figure shows the four ways in which the caller’s range closure and the called’s
domain closure can agree.

The thick line means closed and the thin line means open.

24.
 Figure 12.2: Equal-Span Range/Domain Compatibility Bugs

The above figure shows the twelve different ways the caller and the called can disagree
about closure.

Not all of them are necessarily bugs.

The four cases in which a caller boundary is open and th e called is close are probably
not buggy.

It means that the caller will not supply such values but the called can accept them.

Note that inconsistencies even if harmless in one domain may be erroneous in adjacent
domain.

If there are only two domains ( valid, not valid ) and we’re looking at the valid domain,
then the inconsistency is harmless; otherwise it’s a bug.

12.4 Span Compatibility

Figure 12.3: Harmless Range/Domain Span Incompatibility Bugs

The above figure shows three possibly harmless span incompatibilities.

In all cases, the caller’s range is a subset of the called’s domain.

25.
 That’s not necessarily a bug.

Figure 12.4: Buggy Range/Domain Mismatches

The (a) in the above figure shows the opposite situation, in which the called routine’s
domain has a smaller span than the caller expected. All of these example’s are buggy.

The (b) in the above figure shows the range and domains don’t line up; hence good values
are rejected, bad values are accepted and if called routine isn’t robust enough, we have
crashes.

The (c) in the above figure combines those notations to show various ways we can have
holes in the domain: these are all probably bugs.

26.
LINGUSTIC METRIC

Linguistic metrics based on measuring properties of program or specification text with- out
interpreting what that text means or the ordering of components of the text.

For example: lines of code, number of statements, number of unique operators, number
of unique operands, total number of operators, total number of operands, total number
of keyword appearances, total number of tokens.

A metric is (mainly) linguistic if its value doesn’t change when you rearrange the text.
Linguistic metrics, to date, have been applied mostly to program text.

13.1 Lines of Code, Statement Count, and Related

Metrics

What is it?
Count the number of lines of code in a program and use that number as a measure
of complexity. If then, bugs appear to occur at 1% per line, a 1000-line program should
have 10 bugs and a 10,000 line program should have 100.

Going further, if we find that it takes an average of twenty tests to find a bug, we might
infer (empirically) the expected number of tests needed per line of code.

In today’s electronic programming world, you could just count the number of k of
storage used to store the program text. There’s a high correlation between the weight
of the listing or its thickness and the number of statements in it. On a big project, it probably
correlates to better than 95%.

27
What to Count and Not Count
Early users of lines of code did not include data declarations, comments, or any other lines
that did not result in object code. Later users decided to include declarations and other
unexecutable statements but still excluded comments and blank lines.

There is a rationale for including comments. The quality of comments materially affects
maintenance costs because the maintenance programmer will depend on the comments
more than anything else to do her job.

Conversely, too many blank lines and wordy but information-poor comments will in- crease
maintenance effort. The problem with including comments is that we must be able to
distinguish between useful and useless comments, and there’s no rigorous way to do that.

The lines-of-code metric has obvious difficulties. The count depends on the printing format.
Programming standards and individual style change lines of code, especially for data
declarations.

For languages that permit multiple statements on each line: putting an entire loop on
a line reduces apparent complexity, but overcrowding a line by arbitrarily packing statements
makes the program text more obscure.

Lines of code makes more sense for source languages in which there’s a high correlation
between statement count and lines of code.

Statement Counts
Some of the difficulties with lines of code can be overcome by using statements instead.
Just as subjectivity is involved in applying lines of code, there’s subjectivity in deciding
what is and what is not to be called a statement (for some languages).

How Good (Bad) Are They?

Small programs had an error rate of 1.3% to 1.8%, with big programs increasing from 2.7%
to 3.2%.

The bottom line is that lines of code is reasonably linear for small programs (under 100
lines) but increases nonlinearly with program size. It seems to correlate with maintenance
costs. Statement count shows the same correlation.

28.
13.2 Halstead’s Metrics
What Are They?

Halstead’s metrics are based on a combination of arguments derived from common

sense, information theory, and psychology.

The set of metrics are based on two, easily measured, parameters of programs:

n 1 = the number of distinct operators in the program (e.g., keywords)

n 2 = the number of distinct operands in the program (e.g., data objects)

From these he defines program length, which is not to be confused with the number
of statements in a program, by the following relation:

H = n 1 log2 n 1 + n 2 log2 n2 (13.1)

In calculating the Halstead length, paired operators such as “BEGIN...END,” “DO...UNTIL,”

“FOR...NEXT,” “(...)” are usually treated as a single operator, which is what they ac-
tually are.

For any given program it’s possible to count the actual operator and operand appear-
ances.

N1 = program operator count

N2 = program operand count

The actual Halstead length is evidently

N = N1 + N2 (13.2)

The actual length is effectively a static count of the number of tokens in the program.

Halstead also defines a program’s vocabulary as the sum of the number of distinct
operators and operands.

29.
 n = vocabulary = n 1 + n2 (13.3)

If a program is written using 20 keywords out of a total of 200 in the language, and it
references 30 data objects, its Halstead length should be 20 log2 20 + 30 log2 30 = 233.6.

How well does H (the predicted Halstead length) compare with N, (the actual Halstead
length measured on the program)? The answer is: closely. Further-more, the relation
appears to hold when a program is subdivided into modules.

The bug prediction formula is based on the four values: n1, n2, N1, and N2:

(N1 + N2) log2(n 1 + n2)

B= (13.4)
3000

A program then that accesses 75 data objects a total of 1300 times and uses 150
operators a total of 1200 times, should be expected to have (1300+1200)log2(75+150) = 6.5
3000

bugs.

The Hidden Assumptions and Weaknesses

1. Modularity: Modularity is not ignored because each call, together with the pa-
rameters of the call sequence, will contribute to the values of n1, n2, N1, and N2,
and therefore to the predicted bug count.

2. Database Impact and Declarations: Halstead isn’t to be faulted on this one.

It’s just that most evaluators and confirmers have continued the erroneous practice
of ignoring unexecutable statements such as declarations and data statements.

3. Opera/Operand Ambiguity: Trying to expand the bug prediction or program length

equations to dynamically varying calls would make it impossible to do a static
calculation of the metrics. Only a dynamic count would do. The data whose actual
function is control. Control and instructions in the guise of data are operators and
not operands.

4. Data-Type Distinctions: In strongly typed languages that force the explicit

declaration of all types and prohibit mixed-type operations unless a type conversion
statement has been inserted. The problem arises in the more common languages
that permit mixed operations (e.g., integer floating-point addition) and that have
no user-defined types. In principle, each use of an operator must be linked with

30.
type of data over which it operates.

31.
 5. Call Depth: A routine that calls ten different subr outines as a sequence of
successive calls would actually be considered more complex than a routine that had
ten nested calls. If the totality of the routines and all that it calls were considered,
the bug prediction would be the same for both because the t otal operator and
operand counts would be the same.

6. Operator Types: An IF-THEN-ELSE statement is given the same weight as a FOR-

UNTIL, even though it’s known that loops are more troublesome. This is an example
of a broader criticism—that operators and operands are treated equally, with no
correlation to the bug incidence associated with specific operators or with operand
types.

7. General Structure Issues: Of these, the fact that nesting is ignored (nested
loops, nested IF-THEN-ELSE, and so on) is probably the most serious critique.

13.3 Token Count

A token in a programming language is the basic syntactic unit from which programs
are constructed. Tokens include keywords, labels, constants, strings, and variable names.

Token counting is easy because the first stage of compilation is to translate the source code
into equivalent numerical tokens. The number of tokens is easily obtained as a by-
product of compilation. Token count gets around the subjectivity problems we have with
statement counts and lines of code.

There are two possible ambiguities: paired delimiters and dynamically bound
objects.

Paired delimiters are usually converted by the compiler into two tokens and then elim-
inated by the (typical) subsequent translation to parenthesis-free form (i.e., polish prefix
or suffix form).

Although syntactically, paired delimiters function as a single object, there is a strong

case for treating them as two objects, in that a paired delimiter is more complex than a single
operator, and bugs can occur with mismatched paired delimiters if both a begin and end
delimiter are dropped or added.

With respect to dynamically bound objects such as a variable number of objects in a

call or a variable subroutine name in a call is that you cannot define a static metric over

32.
such objects–the size is dynamic and only a metric defined over the program at run-time
will do.

The use of dynamically bound objects is much more complex than statically bound objects.
A static count can still be used, but the metric should be augmented with a count of the
instances of dynamically bound objects as determined at compile time, which could result in
additional tokens when bound.

That is, the metric consists of two parts: the static token count and unbound token count.
This approach gets around the problems of how to count dynamic subroutine names in
calls, pointer variables, variable number of objects in a call, etc. We would expect the
unbound variable count to have a much higher coefficient in a bug prediction formula.

33.
STRUCTURAL METRIC

Structural metrics take the opposite viewpoint of linguistic metrics. Linguistic com- plexity
is ignored while attention is focused on control-flow or data-flow complexity– metrics based
on the properties of flowgraph models of programs.

14.1 Cyclomatic Complexity (McCabe’s Metric)

Definition

McCabe’s cyclornatic complexity metric (MCCA76) is defined as:

M = L − N + 2P

where
L =the number of links in the graph
N =the number of nodes in the graph
P =the number of disconnected parts of the graph (eg., a calling program and a subrou-
tine)

This metric can also be calculated by adding one to the number of binary decisions in
a structured flowgraph with only one entry and one exit. If all decisions are not binary,
count a three-way decision as two binary decisions and N-way case statements as N – 1
binary decisions.

Similarly, the iteration test in a DO or other looping statement is counted as a binary

decision.

34
 Figure 14.1: Examples of Graphs and Calculation of McCabe’s Complexity Metric

Applications to Test Plan Completeness and Inspections

Evaluate the cyclomatic complexity of the program’s design (e.g., from the design
control flowgraph). Any significant difference should be explained, because it’s more likely
that the difference is due to a missing path, an extra path, or an unplanned deviation
from the design than to something else.

Having verified the code’s cyclomatic complexity, compare the number of planned test
cases to the code’s complexity.

If the number of covering test cases is less than the cyclomatic complexity, there is
reason for caution, because one of the following may be true:

1. You haven’t calculated the complexity correctly. Did you miss a decision?

2. Coverage is not really complete; there’s a link that hasn’t been covered.

3. Coverage is complete, but it can be done with a few more but simpler paths.

4. It might be possible to simplify the routine.

35.
When to Subroutine
McCabe’s metric can be used to help decide whether it pays to make a piece of code
which is common to two or more links into a subroutine.

The program has a common part that consists of Nc nodes and L c links. This is the part
being considered for conversion to a subroutine. This common part recurs k times in the
body of the main program.

The main program has Nm nodes and Lm links over and above the common part.

The total number of links and nodes for the main program, therefore, is Lm + kLc and
Nm + kNc. When the common parts are removed, an additional link must be added to the
main program to replace the code by a subroutine call.

The subroutine’s code must be augmented with an additional entry node and exit node.
The break-even point occurs when the total complexities are equal.

SUBROUTINE FOR COMMON

EMBEDDED COMMON PART
PART

Main Nodes Nm + kNc Nm

Main Links L m + kLc Lm + k
Sub-Nodes 0 Nc + 2
Sub-Links 0 Lc

Main Complex-
(Lm + kLc) − (Nm + kNc) + 2(1) (Lm + k) − Nm + 2(1)
ity

Sub Complexity 0 Lc − (Nc + 2) + 2(1)

Total Complex-
Lm + kLc − Nm − kNc + 2(1) (Lc+Lm+k)−(Nc+2+Nm)+2(2)
ity

36.
37.
PATH SUM, PRODUCT and
EXPRESSION

15.1 Overview
The flow-graph denoted only control-flow connectivity; that is, links had no property
other than the fact that they connected nodes.

On data-flow testing, to add link weight; that is, every link was annotated with a letter
or sequence of letters that denoted the sequence of data-flow actions on the link.

The simplest weight we can give to a link is a name. Using link names as weights, we
then convert the graphical flow-graph into an equivalent algebraic-like expression which
denotes the set of all possible paths from entry to exit for the flow-graph.

The same basic algorithm is then used in subsequent sections with different kinds of
weights to do data-flow anomaly detection, timing analyses, and to solve various debug- ging
and testing problems.

15.2 Basic Concepts

Every link of a graph can be given a name; the link name will be denoted by lowercase italic
letters. In tracing a path or path segment through a flow-graph, we traverse a succession of
link names. The name of the path or path segment that corresponds to those links is
expressed naturally by concatenating those link names.

Consider a pair of nodes in a graph and the set of paths between those nodes. Denote
that set of paths by uppercase letters such as X or Y.

38
The members of that set can be listed as follows:

ac, abc, abbc, abbbc, ...

Alternatively, that same set of paths can be donoted by:

ac + abc + abbc + abbbc + ...

The “+” sign is understood to mean “or”.

That is, between the two nodes of interest,
paths ac, or abc, or abbc, and so on can be
taken.

Any expression that consist of path

names and “ORs” and which denotes a set
of paths between two nodes is called a path
expression.

15.3 Path Products

If we traverse link a, b, c, and d along
some path, the name for that path segment
is abcd. This path name is also called a
Figure 15.1: Example of Paths path product.

The name of a path that consist of two

successive path segments is conveniently
expressed by the concatenation or path
product of the segment names.

X = abcde

Y = fghij

then the path corresponding to X followed by Y is denoted by

XY = abcdefghij

39.
 Similarly,
Y X = fghijabcde

aX = aabcde

Xa = abcdea

XaX = abcdeaabcde

If X and Y represent sets of paths or path expressions, their product represents the set
of paths that can be obtained by following every element of X by any element of Y in all
possible ways.

The path product is not commutative, but expressions derived from it may be com -
mutative. The path product is associative, but expressions derived from it may not be;
that is
A(BC) = (AB)C = ABC

15.4 Path Sums

The “+” sign was used to denote the fact that path names were part of the same set
of paths. The path sum denotes paths in parallel between two nodes.

The first set of parallel paths is denoted by X + Y + d and the second set by U + V +
W + h + i + j. The set of all paths in this flowgraph is

f (X + Y + d)g(U + V + W + h + i + j)k

The path sum is a set union operation, it is clearly commutative and associative; that
is,
(X + Y ) + Z = X + (Y + Z) = X + Y + Z

40.
41.
SYNTAX TESTING

16.1 Generators, Recognizers, and Approach

The tester attempts to generate strings and is said to be a string generator. The
routine is said to be a string recognizer.

• Incorrect Actions

– The recognizer does not recognize a good string.

– It accepts a bad string.

– It may accept or reject a good string or a bad string, but in so doing, it fails.

• String Errors

– High-Level Syntax Errors.

– Intermediate-Level Syntax Errors.

– Field-Syntax Error.

– Delimiter Errors.

– Syntax-Value Errors.

– State-Dependency Errors.

16.2 Test Case Design

Strategy
If there are of the order of N single-error cases, there will be of the order of N 2 double-
error and N 3 triple-error cases.

42
Top, Intermediate, and Field-Level Syntax Errors
The topmost syntax level is defined as

item ::= atype/btype/ctype/dtypeetype

Here are some obvious test cases

• Do it wrongly.

• Use a wrong combination.

• Don’t do nothing

• Do too much.

Delimiter Errors
Delimiters are characters or strings placed between two fields to denote where one ends
and the other begins.

• Missing Delimiters.

• Wrong Delimiters.

• Not a Delimiters.

• Too many Delimiters.

• Paired Delimiters.

Field-Value Errors
Field-Value errors are clearly a domain-testing issue. We want to look for boundary values
and near boundary values, excluded values, binary values for integers, and values vulnerable
to semantic type changes and representation changes.

Context-Dependent Syntax Errors

Components of the syntax may be interrelated and may be related by field values of other
fields. The first field could be a code that specifies the syntax of subsequent fields.

command ::= pilotf ieldsyntaxoption

pilotf ield ::= 1/2/3/4/5/6/7/8/9

43.
 syntaxo ption ::= option1/option2/option3/. . .

command ::= 1option1/2option2/. . .

State-Dependency Errors
The string or field value that may be acceptable at one instance may not be acceptable
at the next because validity depends on the transactions or the systems state.

44.
45.
LOGIC BASED TESTING

17.1 Programming and Logic

Boolean algebra is to logic as arithmetic is to mathematics. Without it, the tester or
programmer is cut off from many test and design techniques and tools that incorporate those
techniques.

17.2 Hardware Logic Testing

Logic has been, for several decades, the primary tools of hardware logic designers.

Many test methods developed for hardware logic can be adapted to software logic testing.
Because hardware testing automation is 10 to 15 years ahead of software testing automation,
hardware testing methods and its associated theory is a fertile ground for software testing
methods.

Hardware testing methods will eventually filter into the software tester’s toolkits, but
there’s another ongoing trend that provides an even stronger motivation. The distinction
between hardware and software is blurring.

Hardware designers talk about silicon compilers–compilers that start with a specifi-
cation in a high-order language and automatically produce integrated circuit layouts.

The hardware designers look more like programmers each day and we can expect them to
meet at a middle ground.

46
17.3 Specification Systems and Languages
As programming and test techniques have improved, the bugs have shifted closer to
the process front end, to requirements and their specifications.

These bugs range from 8% to 30% of the total and because they’re first-in and last-out,
they’re the costliest of all.

The trouble with specifications is that they’re hard to express. Boolean algebra is the most
basic of all logic systems. Higher-order logic systems are needed and used for formal
specifications.

That does not necessarily mean that future programmers will have to live with upside-
down, because much of logical analysis can be and is embedded in tools. But these tools
incorporate methods to simplify, transform and check specifications, and the methods are to
a large extent based on Boolean algebra.

So even if you have a relatively painless specification system, to understand why your
specification was rejected or how it was transformed, you’ll have to understand Boolean
algebra.

17.4 Knowledge-Based Systems

The knowledge-based system (also expert systems or “artificial intelligence”) has
become the programming construct of choice for many applications that were once
considered very difficult.

Knowledge-based systems incorporate knowledge from a knowledge domain such as

medicine, law, or civil engineering into a database.

The data can then be queried and interacted with to provide solutions to problems in
the domain. One implementation of knowledge-based systems is to incorporate the expert’s
knowledge into a set of rules.

The user can then provide data and ask questions based on that data. The user’s data
is processed through the rule base to yield conclusions and requests for more data. The
processing is done by a program called the inference engine.

From the point of view of testing, there’s nothing special about the inference engine–it’s
just another piece of software to be tested.

47.
 When we talk about testingn knowledge-based systems, it’s not the inference engine
that concerns us, but testing the validity of the expert’s knowledge and the correctness
of the transcription (i.e., coding)of the knowledge into a rule base.

48.
49.
TRANSITION TESTING

18.1 Unspecified and Contradictory Transitions

Every input-state combination must have a specified transition. If the transition is
impossible, then there nust be a mechanism that prevents that input from occuring in
that state.

Exactly one transition must be specified for every combination of input and state. However
you model it or test it, the system will do something for every combination of input and state.

It’s better that it does what you want it to do, which you assure by specifying a
transition rather than what some bugs want it to do.

A program can’t have contradictions or ambiguities. Ambiguities are impossible be-

cause the program will do something ( right or wrong ) for every input. Even if the state
does not change, by definition this is a transition to the same test.

A seeming contradiction could come about in a model if you don’t accoun t for all the
factors that constitute the state and all the inputs.

A single bit may have escaped your notice; if that bit is part of the definition of the
state it can double the number of states, but if you’re not monitoring that factor of the
state, it would appear that the program had performed contradictory transitions or had
different outputs for what appeared to be the same input from the same state.

If you, as a designer, say while debugging “sometimes it works and sometimes it doesn’t”,
you’ve admitted to a state factor of which you’re not aware – a factor probably caused by
abug.

50
 Exploring the real state graph and recording the transitions and outputs for each
combination of input and state may lead you to discover the bug.

18.2 Unreachable States

An unreachable state is like unreachable code – a state that no input sequence can
reach. There may be transitions from the unreachable state to other states.

Unreachable states can come about from previously “impossible” states.

An isolated, unreachable state here and there, which clearly relates to impossible com-
binations of real-world state-determining conditions, is acceptable, but if you find groups
of connected states that are isolated from others, there’s cause for concern.

There are two possibilities:

1. There is a bug; that is, some transitions are missing.

2. The transitions are there, but you don’t know about it.

18.3 Dead States

A dead state, ( or set of dead states ) is a state that once entered cannot be left. This
is not necessarily a bug, but it is suspicious.

A set of states may appear to be dead because the program has two modes of operation.

In the first mode it goes through an initialization process that consists of several states.
Once initialized, it goes to a strongly connected set of working states, which, within the
context of the routine, cannot be exited.

The initialization states are unreachable to the working states, and the working states
are dead to the initialization states. The only way to get back might be after a system
crash and restart.

Legitimate dead states are rare. They occur mainly with system-level issues and device
handler. In normal software, if it’s not possible to get from any state to any other, there’s
reason for concern.

51.
STATE TESTING

19.1 Impact of Bugs

A bug can manifest itself as one or more of the following symptoms:

1. Wrong number of states.

2. Wrong transition for a given state-input combination.

3. Wrong output for a given transition.

4. Pairs of states or sets of states that are inadvertently made equivalent (factor lost).

5. States or sets of states that are split to create ineqivalent duplicates.

6. States or set of states that have became dead.

7. States or set of states that have become unreachable.

19.2 Principles
Its impractical to fo through every path in a state graph.

A path in a state graph, of course, is a succession of transitions caused by a sequence

of inputs.

The starting point of the state testing is:

1. Define a set of covering input sequence that get back to the initial state when
starting from the initial state.

2. For each step in each input sequence, define the expected next state, the expected
transition, and the expected output code.

52
 A set of tests, consist of three sets of sequences:

1. Input Sequence.

2. Corresponding transitions or next-state names.

3. Output Sequence.

19.3 Limitation and Extensions:

State-transition coverage in a state-graph model does not guarantee complete testing.

The simplest is called a “0 switch”, which corresponds to testing each transition indi -
vidually.

The next level consist of testing transition sequence consisting of two transitions, called
“1 switches”.

The maximum-length switch is an n-1 switch, where n is the number of states.

A “0 switch” cover can catch output errors but may not catch some transition errors.

In general, one must use longer and longer covering sequence to catch transition errors,
missing states and extra states.

53.
VERIFICATION vs VALIDATION

VERIFICATION vs VALIDATION
It includes checking documents, It includes testing and validating
design, codes and programs. the actual product.
Verification is the static testing. Validation is the dynamic testing.
It does not include the execution It includes the execution of the
of the code. code.
Methods used in validation are
Methods used in verification are
Black Box Testing, White Box
reviews, walkthroughs and in-
Testing and nonfunctional test-
spections.
ing.
It checks whether the software
It checks whether the software
meets the requirements and ex-
conforms to specifications or not.
pectations of a customer or not.
Validation is executed on soft-
Quality assurance team does ver-
ware code with the help of testing
ification.
team.
It comes before validation. It comes after verification.
It consists of checking of docu- It consists of execution of pro-
ments/files and is performed by gram and is performed by com-
human. puter.

54