STM-UNIT -I

 Software testing is a process, or a series of process, designed to ensure that the

computer code does what it is designed for and does not do something that is
not intended.
 Testing involves at least half of the time and efforts spent to build working
software. And the efforts put into testing are considered waste if the tests
conducted on the code do not reveal all the errors.
 Testing ensures presence of errors, not the absence of errors. Even after a code
has been tested thoroughly, it can report errors. So, even the best written code
can have errors. The only way to minimize it is to devise best possible test
design and carry out testing which covers maximum possible functionality.

1. THE PURPOSE OF TESTING

1.1. What We Do
 Testing consumes at least half of the labor expended to produce a working
program.
 The effort put into testing seems wasted if the tests don’t reveal bugs.
 It’s done to catch bugs.
 if we were really good at programming, there would be no bugs to catch.
If only we could really concentrate, if everyone used structured
programming, top-down design, decision tables, if programs were written.
 The statistics show that programming, done well, will still have one to
three bugs per hundred statements

1.2. Productivity and Quality in Software

 In production of consumer goods and other products, every manufacturing

stage is subjected to quality control and testing from component to final
stage.
 If flaws are discovered at any stage, the product is either discarded or
cycled back for rework and correction.

1
  Productivity is measured by the sum of the costs of the material, the
rework, and the discarded componenets, and the cost of quality assurance
and testing.
 There is a trade off between quality assurance costs and manufacturing
costs: If sufficient time is not spent in quality assurance, the reject rate will
be high and so will be the net cost. If inspection is good and all errors are
caught as they occur, inspection costs will dominate, and again the net cost
will suffer.
 Testing and Quality assurance costs for 'manufactured' items can be as low
as 2% in consumer products or as high as 80% in products such as space-
ships, nuclear reactors, and aircrafts, where failures threaten life. Where as
the manufacturing cost of a software is trivial.
 The biggest part of software cost is the cost of bugs: the cost of detecting
them, the cost of correcting them, the cost of designing tests that discover
them, and the cost of running those tests.
 For software, quality and productivity are indistinguishable because the
cost of a software copy is trivial.

1.3. Goals for Testing

 Testing and test design, as parts of quality assurance, should also focus on
bug prevention. To the extent that testing and test design do not prevent
bugs, they should be able to discover symptoms caused by bugs.
 Finally, tests should provide clear diagnoses so that bugs can be easily
corrected. Bug prevention is testing’s first goal.
 A prevented bug is better than a detected and corrected bug because if the
bug is prevented, there’s no code to correct.

1.4. Phases in a Tester’s Mental Life

PHASE 0—There’s no difference between testing and debugging. Other than in

support of debugging, testing has no purpose.
PHASE 1—The purpose of testing is to show that the software works.
PHASE 2—The purpose of testing is to show that the software doesn’t work.
PHASE 3—The purpose of testing is not to prove anything, but to reduce the
perceived risk of not working to an acceptable value.
2
PHASE 4—Testing is not an act. It is a mental discipline that results in low-risk
software without much testing effort.

1. Phase 0: (Until 1956: Debugging Oriented) There is no difference between

testing and debugging. Phase 0 thinking was the norm in early days of software
development till testing emerged as a discipline.
2. Phase 1: (1957-1978: Demonstration Oriented) the purpose of testing here is to
show that software works. Highlighted during the late 1970s. This failed because the
probability of showing that software works 'decreases' as testing increases. I.e. the
more you test, the more likely you will find a bug.
3. Phase 2: (1979-1982: Destruction Oriented) the purpose of testing is to show that
software doesn’t work. This also failed because the software will never get released as
you will find one bug or the other. Also, a bug corrected may also lead to another bug.
4. Phase 3: (1983-1987: Evaluation Oriented) the purpose of testing is not to prove
anything but to reduce the perceived risk of not working to an acceptable value
(Statistical Quality Control). Notion is that testing does improve the product to the
extent that testing catches bugs and to the extent that those bugs are fixed. The
product is released when the confidence on that product is high enough. (Note: This is
applied to large software products with millions of code and years of use.)
5. Phase 4: (1988-2000: Prevention Oriented) Testability is the factor considered
here. One reason is to reduce the labor of testing. Other reason is to check the testable
and non testable code. Testable code has fewer bugs than the code that's hard to test.
Identifying the testing techniques to test the code is the main key here.

Phase 0 Thinking
Phase 1 Thinking—The Software Works
Phase 2 Thinking—The Software Doesn’t Work
Phase 3 Thinking—Test for Risk Reduction
Phase 4 Thinking—A State of Mind

1.5. Test Design

We know that the software code must be designed and tested, but many appear to
be unaware that tests themselves must be designed and tested. Tests should be
properly designed and tested before applying it to the actual code.

3
 1.6. Testing Isn’t Everything
There are approaches other than testing to create better software. Methods other
than testing include:
1. Inspection Methods: Methods like walkthroughs, desk checking, formal
inspections and code reading appear to be as effective as testing but the bugs
caught don’t completely overlap.
2. Design Style: While designing the software itself, adopting stylistic objectives
such as testability, openness and clarity can do much to prevent bugs.
3. Static Analysis Methods: Includes formal analysis of source code during
compilation. In earlier days, it is a routine job of the programmer to do that. Now,
the compilers have taken over that job.
4. Languages: The source language can help reduce certain kinds of bugs.
Programmers find new bugs while using new languages.
5. Development Methodologies and Development Environment: The
development process and the environment in which that methodology is
embedded can prevent many kinds of bugs.

1.7. The Pesticide Paradox and the Complexity Barrier

First Law: The Pesticide Paradox—Every method you use to prevent or find bugs
leaves a residue of subtler bugs against which those methods are ineffectual.
That’s not too bad, you say, because at least the software gets better and better. Not
quite!
Second Law: The Complexity Barrier—Software complexity (and therefore that of
bugs) grows to the limits of our ability to manage that complexity.

2. SOME DICHOTOMIES
2.1. Testing Versus Debugging
 The purpose of testing is to show that a program has bugs.
 The purpose of debugging is find the error or misconception that led to the
program’s failure and to design and implement the program changes that correct the
error.

4
  Debugging usually follows testing, but they differ as to goals, methods, and most
important, psychology:
1. Testing starts with known conditions, uses predefined procedures, and has predictable
outcomes; only whether or not the program passes the test is unpredictable. Debugging starts
from possibly unknown initial conditions, and the end cannot be predicted, except
statistically.
2. Testing can and should be planned, designed, and scheduled. The procedures for, and
duration of, debugging cannot be so constrained.
3. Testing is a demonstration of error or apparent correctness. Debugging is a deductive
process.
4. Testing proves a programmer’s failure. Debugging is the programmer’s vindication.
5. Testing, as executed, should strive to be predictable, dull, constrained, rigid, and inhuman.
Debugging demands intuitive leaps, conjectures, experimentation, and freedom.
6. Much of testing can be done without design knowledge. Debugging is impossible without
detailed design knowledge.
7. Testing can often be done by an outsider. Debugging must be done by an insider.
8. Although there is a robust theory of testing that establishes theoretical limits to what
testing can and can’t do, debugging has only recently been attacked by theorists—and so far
there are only rudimentary results.
9. Much of test execution and design can be automated. Automated debugging is still a
dream.
2.2. Function Versus Structure
Tests can be designed from a functional or a structural point of view.
In functional testing
 the program or system is treated as a black box. It is subjected to inputs, and its
outputs are verified for conformance to specified behavior.
 The software’s user should be concerned only with functionality and features, and the
program’s implementation details should not matter.
 Functional testing takes the user’s point of view bother about functionality and
features and not the program's implementation.
Structural testing
 does look at the implementation details.
 Such things as programming style, control method, source language, database design,
and coding details dominate structural testing;

5
  the boundary between function and structure is fuzzy.
 Good systems are built in layers—from the outside to the inside. The user sees only
the outermost layer, the layer of pure function. Each layer inward is less related to the
system’s functions and more constrained by its structure: so structure to one layer is
function to the next
 Both Structural and functional tests are useful, both have limitations, and both target
different kinds of bugs. Functional tests can detect all bugs but would take infinite
time to do so. Structural tests are inherently finite but cannot detect all errors even if
completely executed.

2.3. The Designer Versus the Tester

 Test designer is the person who designs the tests where as the tester is the one actually
tests the code. During functional testing, the designer and tester are probably different
persons. During unit testing, the tester and the programmer merge into one person.
 Tests designed and executed by the software designers are by nature biased towards
structural consideration and therefore suffer the limitations of structural testing

2.4. Modularity Versus. Efficiency

 Both tests and systems can be modular.
 A module is a discrete, well-defined, small component of a system. The smaller the
component, the easier it is to understand; but every component has interfaces with
other components, and all interfaces are sources of confusion. The smaller the
component, the likelier are interface bugs.
 Large components reduce external interfaces but have complicated internal logic that
may be difficult or impossible to understand. Part of the artistry of software design is
setting component size and boundaries at points that balance internal complexity
against interface complexity to achieve an overall complexity minimization.
 Testing can and should likewise be organized into modular components. Small,
independent test cases can be designed to test independent modules.
2.5. Small Versus Large
 Programming in the large means constructing programs that consist of many
components written by many different programmers

6
  Programming in the small is what we do for ourselves in the privacy of our own
offices .
Qualitative changes occur with size and so must testing methods and quality criteria.
.
2.6. The Builder Versus the Buyer
 Most software is written and used by the same organization. Unfortunately, this
situation is dishonest because it clouds accountability.
 Many organizations today recognize the virtue of independent software development
and operation because it leads to better software, better security, and better testing.
 The different roles / users in a system include
1. The builder, Who designs the system and is accountable to the buyer.
2. The buyer, who pays for the system in the hope of profits from providing services to
3. The user, the ultimate beneficiary or victim of the system. The user’s interests are guarded
by
4. The tester, who is dedicated to the builder’s destruction and
5. The operator, who has to live with the builder’s mistakes, the buyer’s murky
specifications, the tester’s oversights, and the user’s complaints.

3. A MODEL FOR TESTING

3.1. The Project

A real-world context characterized by the following model project:

a. Application—The specifics of the application are unimportant. It is a real-time

system that must provide timely responses to user requests for services. It is an
online system connected to remote terminals.
b. Staff—The programming staff consists of twenty to thirty programmers—big
enough to warrant formality, but not too big to manage—big enough to use
specialists for some parts of the system’s design.
c. Schedule—The project will take 24 months from the start of design to formal
acceptance by the customer. Acceptance will be followed by a 6-month cutover
period. Computer resources for development and testing will be almost
adequate.

7
d. Specification—The specification is good. It is functionally detailed without
constraining the design, but there are undocumented “understandings”
concerning the requirements.
e. Acceptance Test—The system will be accepted only after a formal acceptance
test. The application is not new, so part of the formal test already exists. At first
the customer will intend to design the acceptance test, but later it will become
the software design team’s responsibility.
f. Personnel—The staff is professional and experienced in programming and in
the application. Half the staff has programmed that computer before and most
know the source language. One-third, mostly junior programmers, have no
experience with the application. The typical programmer has been employed by
the programming department for 3 years. The climate is open and frank.
Management’s attitude is positive and knowledgeable about the realities of such
projects.
g. Standards—Programming and test standards exist and are usually followed.
They understand the role of interfaces and the need for interface standards.
Documentation is good. There is an internal, semiformal, quality-assurance
function. The database is centrally developed and administered.
h. Objectives—The system is the first of many similar systems that will be
implemented in the future. No two will be identical, but they will have 75% of
the code in common. Once installed, the system is expected to operate profitably
for more than 10 years.
i. Source—One-third of the code is new, one-third extracted from a previous,
reliable, but poorly documented system, and one-third is being rehosted (from
another language, computer, operating system—take your pick).
j. History—One programmer will quit before his components are tested. Another
programmer will be fired before testing begins: excellent work, but poorly
documented. One component will have to be redone after unit testing: a superb
piece of work that defies integration. The customer will insist on five big
changes and twenty small ones. There will be at least one nasty problem that
nobody—not the customer, not the programmer, not the managers, nor the
hardware vendor—suspected. A facility and/or hardware delivery problem will
delay testing for several weeks and force second- and third-shift work. Several
important milestones will slip but the delivery date will be met.

8
3.2. Overview

 All the systems ranging from a subroutine to a millions of statements require

testing. The typical system is that which allows exploration of all testing aspects
without any complications. It’s medium-scale programming.
 Figure 1.1 is a model of the testing process. The process starts with a program
embedded in an environment, such as a computer, an operating system, or a
calling program.
 Based on our understanding of the human nature and its susceptibility to error,
we can create three models: model of the environment, model of the program
and a model of the expected bugs.
 From these models we create a set of tests, which are then executed.
 The result of each test is either expected or unexpected. If unexpected, it may
lead us to revise the test, our model or concept of how the program behaves, our
concept of what bugs are possible, or the program itself. Only rarely would we
attempt to modify the environment.

3.3. The Environment

o A program’s environment is the hardware and software required to make it
run.

9
 o The environment also includes all programs that interact with—and are used to
create—the program under test, such as operating system, loader, linkage
editor, compiler, utility routines.
o A testing environment comprises of a test plan which details the tests that will
be carried out and the test cases which describe how we will test each of the
components.
o Creation of a test environment reduces the risk of errors occurring when the
software is put to actual use and thereby reducing the downtime of the
software.

3.4. The Program

 Most programs are too complicated to understand in detail.
 We must simplify our concept of the program in order to test it.
 We might ignore the called subroutines and concentrate on the program unless
we suspect the former. Similarly, we can ignore the process details so that we
can focus on the control structure of the program or vice versa.
 If the simple model of an environment does not explain the unexpected
behavior we might have to include more facts and details.

3.5. Bugs
 Bugs are more insidious than ever we expect them to be.
 Yet it is convenient to categorize them: initialization, call sequence, wrong
variable, and so on. Our notion of what is or isn’t a bug varies.
 A bad specification may lead us to mistake good behavior for bugs, and vice
versa.
 An unexpected test result may lead us to change our notion of what a bug is—
that is to say, our model of bugs.

Benign bug hypothesis: The belief that bugs are nice, tame and logical. Only
week bugs are logical and are open to exposure based on logical means. Subtle
bugs have no definable patterns.
Bug locality hypothesis: A bug occurring in a particular module affects only that
module locally and not the other modules. However, this is not the case with the
subtle bugs. Their consequences are far removed from the cause in time and space
from the component in which they exist.
10
 Control bug dominance: The belief that errors in the control structure are more
dominant. While bugs related to control-flow, data-flow and data structures flow
can be traced easily, subtle bugs that violate the data structures boundaries and
data/code separation can’t be found by merely looking at the control structures.
Code/Data separation: The belief that bugs respect the separation of data and
code. The distinction between data and code is hard to make in a real system and
this permits the existence of such bugs.
Correction abide: The belief that a corrected bug remains corrected. We might
have changed one of the interacting components in the event of a bug believing it
as the cause, however, the bug might re-occur as it was caused by some other
component which we did not change.
Silver bullets: The mistaken belief that A (language, design, representation,
environment, etc.) makes the program immune of bugs. It might reduce the
severity of bugs but not the complete occurrence of bugs.
Sadism effect: The belief that intuition and cunningness are sufficient to detect
bugs. This is true for easy bugs but the tough bugs need proper methodology and
techniques for detection.
Angelic Testers—The ludicrous belief that testers are better at test design than
programmers are at code design.*

3.6. Tests
 Tests are formal procedures. Inputs must be prepared, outcomes predicted,
tests documented, commands executed, and results observed; all these steps
are subject to error.
 An unexpected test result could have been caused due to either test bug or real
bug.
 Bugs can creep in documentation, inputs and the commands and over-shadow
our observation of results. Thus, it might be required to change the mentality
of the tester rather than the tests themselves.

3.7. Testing and Levels

 We do three distinct kinds of testing on a typical software system:
a. unit/ component testing.
b. integration testing
c. system testing.
11
Unit Testing:
 A unit is the smallest testable piece of software.
 It is the work of a programmer and contains fewer lines of code.
 Unit testing is the testing done to show that the unit does not satisfy its
functional specification and/or its implemented structure does not match
the intended design structure. The faults resulting from such testing are
called unit bugs.
Component Testing:
 A component is an integration of one or more units.
 A unit is also a component and a component with subroutines it calls is a
component, etc. By this recursive definition, a component can be
anything ranging from a unit to a complete system.
 Component testing is the testing done to show that the component does
not satisfy its functional specification and/or its implemented structure
does not match the intended design structure. The faults resulting from
such testing are called component bugs.
Integration Testing:
 Integration is a process by which components are aggregated to create
larger components.
 Integration testing is testing done to show that even though the
components were individually satisfactory, as demonstrated by successful
passage of component tests, the combination of components are incorrect
or inconsistent. For example, components A and B have both passed their
component tests. Integration testing is aimed as showing inconsistencies
between A and B. Examples of such inconsistencies are improper call or
return sequences, inconsistent data validation criteria, and inconsistent
handling of data objects.
 Integration testing is specifically aimed at exposing the problems that
arise from the combination of components.
System Testing:
 A system is a big component.
 System testing is done to reveal the bugs that cannot be attributed to the
components, their inconsistencies or their interactions.
 System testing concerns issues and behavior that can be revealed only by
testing the entire integrated system or a major chunk of it. It includes
12
 performance testing, security testing, accountability testing,
configuration sensitivity testing, start-up and recovery testing.

3.8. The Role of Models

 Testing is a process in which we create mental models of the environment, the

program, human nature, and the tests themselves.
 Each model is used either until we accept the behaviour as correct or until the
model is no longer sufficient for the purpose.
 Unexpected test results always force a revision of some mental model, and in
turn may lead to a revision of whatever is being modeled.
 The revised model may be more detailed, which is to say more complicated, or
more abstract, which is to say simpler.
 The art of testing consists of creating, selecting, exploring, and revising
models.
 Our ability to go through this process depends on the number of different
models we have at hand and their ability to express a program’s behavior.

4. The Consequences of Bugs

 A bug can be important in the terms of correction cost, frequency, installation
cost, and consequences.
 The bugs can affect us in many ways depending upon their severity.
 The severity must be measured in humanistic terms rather than machine terms.
 The importance of a bug can be calculated with the help of its frequency of
occurrence, correction cost, installation and consequential cost.
 A bug might be creep in any part of the software development life cycle.
 It could be related to requirements specification, requirements validation,
requirement reviews, structural bugs, etc.
a. The Importance of Bugs
The importance of a bug depends on frequency, correction cost, installation
cost, and consequences.
I. Frequency—It is important to know so as to how regularly a bug occurs
and what are the bugs which occur most regularly.

13
 II. Correction Cost—It is important to have an idea about the cost to correct
the bug after it is found. That cost is the sum of two factors: (1) the cost of
discovery and (2) the cost of correction. These costs go up dramatically the
later in the development cycle the bug is discovered. Correction cost also
depends on system size. The larger the system the more it costs to correct
the same bug.
III. Installation Cost—Installation cost depends on the number of installations:
small for a single-user program, but how about a PC operating system bug?
Installation cost can dominate all other costs—fixing one simple bug and
distributing the fix could exceed the entire system’s development cost.
IV. Consequences—The consequences of the occurrence of bugs can be
measured by the means of mean size of the awards given to the victim of the
bugs.

A reasonable metric for bug importance is:

Importance= ($) = Frequency * (Correction cost + Installation cost + Consequential cost)
Frequency does not tend to depend upon application or environment
but the other three do. As designers, testers, and QA workers, one must
be interested in bug importance and not only the frequency. Thus, it is
required to come up with your own importance model.

b. How Bugs Affect Us – Consequences

The consequences of a bug can be measure in terms of human rather than

machine. Some consequences of a bug on a scale of one to ten are:
1 Mild: The symptoms of the bug offend us aesthetically (gently); a
misspelled output or a misaligned printout.
2 Moderate: Outputs are misleading or redundant. The bug impacts the
system's performance.
3 Annoying: The system's behavior because of the bug is dehumanizing. E.g.
Names are truncated or arbitrarily modified.
4 Disturbing: It refuses to handle legitimate (authorized / legal) transactions.
The ATM won’t give you money. My credit card is declared invalid.
5 Serious: It loses track of its transactions. Not just the transaction itself but
the fact that the transaction occurred. Accountability is lost.
14
 6 Very Serious: The bug causes the system to do the wrong transactions.
Instead of losing your paycheck, the system credits it to another account or
converts deposits to withdrawals.
7 Extreme: The problems aren't limited to a few users or to few transaction
types. They are frequent and arbitrary instead of sporadic infrequent) or for
unusual cases.
8 Intolerable: Long term unrecoverable corruption of the database occurs and
the corruption is not easily discovered. Serious consideration is given to
shutting the system down.
9 Catastrophic: The decision to shut down is taken out of our hands because
the system fails.
10 Infectious: What can be worse than a failed system? One that corrupt other
systems even though it does not fall in itself ; that erodes the social physical
environment; that melts nuclear reactors and starts war

c. Flexible Severity rather than Absolute

 Quality can be measured as a combination of factors, of which number of bugs
and their severity is only one component.
 Many organizations have designed and used satisfactory, quantitative, quality
metrics.
 Because bugs and their symptoms play a significant role in such metrics, as
testing progresses, you see the quality rise to a reasonable value which is
deemed to be safe to ship the product.
 The factors involved in bug severity are:
1. Correction Cost: Not so important because catastrophic bugs may be
corrected easier and small bugs may take major time to debug.
2. Context and Application Dependency: Severity depends on the context
and the application in which it isused.
3. Creating Culture Dependency: What’s important depends on the creators
of software and their cultural aspirations. Test tool vendors are more sensitive
about bugs in their software then games software vendors.
4. User Culture Dependency: Severity also depends on user culture. Naive
users of PC software go crazy over bugs where as pros (experts) may just
ignore.

15
 5. The software development phase: Severity depends on development
phase. Any bugs gets more severe as it gets closer to field use and more severe
the longer it has been around

5. Taxonomy for Bugs

 There is no universally correct way categorize bugs. The taxonomy is not
rigid.
 A given bug can be put into one or another category depending on its history
and the programmer's state of mind.
 The major categories are:
a. Requirements, Features and Functionality Bugs
Various categories in Requirements, Features and Functionality bugs include:
i. Requirements and Specifications Bugs:
 Requirements and specifications developed from them can be
incomplete ambiguous, or self-contradictory. They can be
misunderstood or impossible to understand.
 The specifications that don't have flaws in them may change while the
design is in progress. The features are added, modified and deleted.
 Requirements, especially, as expressed in specifications are a major
source of expensive bugs.
 The range is from a few percentages to more than 50%, depending on
the application and environment.
 What hurts most about the bugs is that they are the earliest to invade
the system and the last to leave.
ii. Feature Bugs:
 Specification problems usually create corresponding feature
problems.
 A feature can be wrong, missing, or superfluous (serving no useful
purpose). A missing feature or case is easier to detect and correct. A
wrong feature could have deep design implications.
 Removing the features might complicate the software, consume more
resources, and foster more bugs.
iii. Feature Interaction Bugs:
 Providing correct, clear, implementable and testable feature
specifications is not enough.
16
  Features usually come in groups or related features. The features of
each group and the interaction of features within the group are usually
well tested.
 The problem is unpredictable interactions between feature groups or
even between individual features. For example, your telephone is
provided with call holding and call forwarding. The interactions
between these two features may have bugs.
 Every application has its peculiar set of features and a much bigger
set of unspecified feature interaction potentials and therefore result in
feature interaction bugs.
iv. Specification and Feature Bug Remedies:
 Most feature bugs are rooted in human to human communication
problems. One solution is to use high-level, formal specification
languages or systems.
 Such languages and systems provide short term support but in the
long run, does not solve the problem.
 Short term Support: Specification languages facilitate formalization
of requirements and inconsistency and ambiguity analysis.
 Long term Support: Assume that we have a great specification
language and that can be used to create unambiguous, complete
specifications with unambiguous complete tests and consistent test
criteria.
 The specification problem has been shifted to a higher level but not
eliminated.
b. Structural Bugs : Various categories in Structural bugs include:
i. Control and Sequence Bugs
 Control and sequence bugs include paths left out, unreachable
code, improper nesting of loops, loop-back or loop termination
criteria incorrect, missing process steps, duplicated processing,
unnecessary processing, rampaging, GOTO's, ill-conceived (not
properly planned) switches, spaghetti code, and worst of all,
pachinko code.
 One reason for control flow bugs is that this area is amenable
(supportive) to theoretical treatment.

17
 Most of the control flow bugs are easily tested and caught in unit
testing
 Another reason for control flow bugs is that use of old code
especially ALP & COBOL code are dominated by control flow
bugs.
 Control and sequence bugs at all levels are caught by testing,
especially structural testing, more specifically path testing
combined with a bottom line functional test based on a
specification
ii. Logic Bugs
 Bugs in logic, especially those related to misunderstanding how
case statements and logic operators behave singly and
combinations
 Also includes evaluation of boolean expressions in deeply
nested IF-THEN-ELSE constructs.
 If the bugs are parts of logical (i.e. boolean) processing not
related to control flow, they are characterized as processing
bugs.
 If the bugs are parts of a logical expression (i.e. control-flow
statement) which is used to direct the control flow, then they are
categorized as control-flow bugs
iii. Processing Bugs
 Processing bugs include arithmetic bugs, algebraic,
mathematical function evaluation, algorithm selection and
general processing.
 Examples of Processing bugs include: Incorrect conversion
from one data representation to other, ignoring overflow,
improper use of greater-than-or-equal etc
 Although these bugs are frequent (12%), they tend to be caught
in good unit testing.
iv. Initialization Bugs
 Initialization bugs are common. Initialization bugs can be
improper and superfluous.
 Superfluous bugs are generally less harmful but can affect
performance.
18
  Typical initialization bugs include: Forgetting to initialize the
variables before first use, assuming that they are initialized
elsewhere, initializing to the wrong format, representation or
type etc
 Explicit declaration of all variables, as in Pascal, can reduce
some initialization problems
v. Data-Flow Bugs and Anomalies
 Most initialization bugs are special case of data flow anomalies.
 A data flow anomaly occurs where there is a path along which
we expect to do something unreasonable with data, such as
using an uninitialized variable, attempting to use a variable
before it exists, modifying and then not storing or using the
result, or initializing twice without an intermediate use.
c. Data Bugs
 Data bugs include all bugs that arise from the specification of data
objects, their formats, the number of such objects, and their initial
values.
 Data Bugs are at least as common as bugs in code, but they are often
treated as if they did not exist at all.
 Code migrates data: Software is evolving towards programs in which
more and more of the control and processing functions are stored in
tables.
 Because of this, there is an increasing awareness that bugs in code are
only half the battle and the data problems should be given equal
attention
i. Dynamic Versus Static
 Dynamic data are transitory. Whatever their purpose their
lifetime is relatively short, typically the processing time of
one transaction. A storage object may be used to hold
dynamic data of different types, with different formats,
attributes and residues.
 Dynamic data bugs are due to leftover garbage in a shared
resource. This can be handled in one of the three ways:
(1) Clean up after the use by the user
(2) Common Cleanup by the resource manager
19
 (3) No Clean up
 Static Data are fixed in form and content. They appear in
the source code or database directly or indirectly, for
example a number, a string of characters, or a bit pattern.
 Compile time processing will solve the bugs caused by
static data
ii. Information, Parameter, and Control
Static or dynamic data can serve in one of three roles, or in
combination of roles: as a parameter, for control, or for
information.
iii. Contents, Structure, and Attributes
 Content can be an actual bit pattern, character string, or
number put into a data structure. Content is a pure bit
pattern and has no meaning unless it is interpreted by a
hardware or software processor. All data bugs result in the
corruption or misinterpretation of content.
 Structure relates to the size, shape and numbers that
describe the data object, which is memory location used to
store the content. (E.g. A two dimensional array).
 Attributes relates to the specification meaning that is the
semantics associated with the contents of a data object.
(E.g. an integer, an alphanumeric string, a subroutine). The
severity and subtlety of bugs increases as we go from
content to attributes because the things get less formal in
that direction.
d. Coding Bugs
 Coding errors of all kinds can create any of the other kind of bugs.
 Syntax errors are generally not important in the scheme of things if the
source language translator has adequate syntax checking.
 If a program has many syntax errors, then we should expect many logic
and coding bugs.
 The documentation bugs are also considered as coding bugs which may
mislead the maintenance programmers
e. Interface, Integration and System Bugs
Various categories of bugs in Interface, Integration, and System Bugs are
20
 i. External Interfaces
 The external interfaces are the means used to communicate with the
world.
 These include devices, actuators, sensors, input terminals, printers, and
communication lines.
 The primary design criterion for an interface with outside world should
berobustness.
 All external interfaces, human or machine should employ a protocol. The
protocol may be wrong or incorrectly implemented.
 Other external interface bugs are: invalid timing or sequence assumptions
related to external signals
 Misunderstanding external input or output formats.
 Insufficient tolerance to bad input data
ii. Internal Interfaces
 Internal interfaces are in principle not different from external interfaces
but they are more controlled.
 A best example for internal interfaces is communicating routines.
 The external environment is fixed and the system must adapt to it but the
internal environment, which consists of interfaces with other components,
can be negotiated.
 Internal interfaces have the same problem as external interfaces
iii. Hardware Architecture
 Bugs related to hardware architecture originate mostly from
misunderstanding how the hardware works.
 Examples of hardware architecture bugs: address generation error, i/o
device operation / instruction error, waiting too long for a response,
incorrect interrupt handling etc.
 The remedy for hardware architecture and interface problems is
twofold: (1) Good Programming and Testing (2) Centralization of
hardware interface software in programs written by hardware interface
specialists.
iv. Operating System
 Program bugs related to the operating system are a combination of
hardware architecture and interface bugs mostly caused by a
misunderstanding of what it is the operating system does.
21
  Use operating system interface specialists, and use explicit interface
modules or macros for all operating system calls.
 This approach may not eliminate the bugs but at least will localize them
and make testing easier.
v. Software Architecture
 Software architecture bugs are the kind that called - interactive.
 Routines can pass unit and integration testing without revealing such bugs.
 Many of them depend on load, and their symptoms emerge only when the
system is stressed.
 Sample for such bugs: Assumption that there will be no interrupts, Failure to
block or un block interrupts, Assumption that memory and registers were
initialized or not initialized etc
 Careful integration of modules and subjecting the final system toa stress test
are effective methods for these bugs.
vi. Control and Sequence Bugs
 These bugs include: Ignored timing, Assuming that events occur in a
specified sequence, Working on data before all the data have arrived from
disc, Waiting for an impossible combination of prerequisites, Missing,
wrong, redundant or superfluous process steps.
 The remedy for these bugs is highly structured sequence control.
Specialize, internal, sequence control mechanisms are helpful.
vii. Resource Management Problems
 Memory is subdivided into dynamically allocated resources such as
buffer blocks, queue blocks, task control blocks, and overlay buffers.
 External mass storage units such as discs, are subdivided into memory
resource pools.
 Some resource management and usage bugs: Required resource not
obtained, Wrong resource used, Resource is already in use, Resource
dead lock etc
 Resource Management Remedies: A design remedy that prevents bugs is
always preferable to a test method that discovers them.
 The design remedy in resource management is to keep the resource
structure simple: the fewest different kinds of resources, the fewest
pools, and no private resource management

22
 viii. Integration Bugs
 Integration bugs are bugs having to do with the integration of, and with
the interfaces between, working and tested components.
 These bugs results from inconsistencies or incompatibilities between
components.
 he communication methods include data structures, call sequences,
registers, semaphores, and communication links and protocols results in
integration bugs.
 The integration bugs do not constitute a big bug category (9%) they are
expensive category because they are usually caught late in the game and
because they force changes in several components and/or data structures.
ix. System Bugs
 System bugs covering all kinds of bugs that cannot be ascribed to a component
or to their simple interactions, but result from the totality of interactions
between many components such as programs, data, hardware, and the
operating systems.
 There can be no meaningful system testing until there has been thorough
component and integration testing.
 System bugs are infrequent (1.7%) but very important because they are often
found only after the system has been fielded

f. Test and Test Design Bugs

i. Testing
 Testers have no immunity to bugs. Tests require complicated
scenarios and databases.
 They require code or the equivalent to execute and consequently
they can have bugs.
ii. Test Criteria
 if the specification is correct, it is correctly interpreted and
implemented, and a proper test has been designed; but the criterion by
which the software's behavior is judged may be incorrect or
impossible. So, a proper test criteria has to be designed. The more
complicated the criteria, the likelier they are to have bugs.

23
 iii. Remedies
The remedies for test bugs are: test debugging, test quality
assurance, test execution automation, and test design automation
1. Test Debugging: The first remedy for test bugs is testing and debugging the
tests. Test debugging, when compared to program debugging, is easier because
tests, when properly designed are simpler than programs and do not have to make
concessions to efficiency.
2. Test Quality Assurance: Programmers have the right to ask how quality in
independent testing is monitored.
3. Test Execution Automation: The history of software bug removal and
prevention is indistinguishable from the history of programming automation aids.
Assemblers, loaders, compilers are developed to reduce the incidence of
programming and operation errors. Test execution bugs are virtually eliminated by
various test execution automation tools.
4. Test Design Automation: Just as much of software development has been
automated, much test design can be and has been automated. For a given
productivity rate, automation reduces the bug count - be it for software or be it for
tests.

g. Testing and Design Styles

 Bad designs lead to bugs and are difficult to test; therefore, the bugs
remain.
 Good designs inhibit bugs before they occur and are easy to test. The two
factors are multiplicative, which explains the productivity difference. The
best test techniques are useless when applied to abominable code; it is
sometimes easier to redesign a bad routine than to attempt to create tests
for it.
 The labor required producing new code and design for the new code is
much lesser than the labor required to design thorough tests for an
undisciplined, unstructured monstrosity.
 Good testing works best on good code and good designs.
h. Memory related Bugs
 Memory related bugs are caused due to improper handling of the memory
objects.

24
  These bugs can be used to cause security breaches in software. These bugs are
the biggest contributors to all vulnerabilities of software.
 They can be further classified as under:
Buffer overflow bugs: They are caused when we try to access the allocated
memory beyond the buffer boundary.
Stack smashing: These bugs are caused when we illegally overwrite the
function return address.
Memory leak: These bugs are caused when we are not able to access a
dynamically allocated memory to free it.
Uninitialized read: These bugs occur when we try to read a memory data
before it is initialized. Double free: These bugs occur when we try to free an
already freed memory location.

i. Concurrent Bugs
 Concurrent bugs are those that can occur only in multi-threading or multi-
process environment.
 They are caused because of the bad synchronization of the operations of
multiple threads.
 These bugs are un-deterministic in nature which makes them difficult to
reproduce. Such temporary sensitivity makes the bug detection more
difficult.
 They can be classified as below:
Datarace bugs: They occur because of the conflicting access from
concurrent threads when they try to use the same shared memory in
different orders.
Atomicity related bugs: These are caused when a bunch of operations
from a single thread are unexpectedly interrupted by a conflicting
operation from some other threads.
Deadlock: In resource sharing, one or more processes wait indefinitely for
some resource to get free and cannot proceed further, thus, leading to a
deadlock.

25
Software Testing Methodologies Unit II

UNIT –II
TRANSACTION FLOW TESTING
(1) Transaction Flows:
(i) Definitions:
 A transaction is defined as a set of statements or a unit of work handled by a system user.
 A transaction consists of a sequence of operations, some of which are performed by a
system, persons, or devices that are outside of the system.
 Each transaction is usually associated with an entry point and an exit point.
 The execution of a transaction begins at the entry point and ends at an exit point there by
producing some results.
 After getting executed, the transaction no longer exists in the system.
 All the results are finally stored in the form of records inside the system.
A transaction for an online information retrieval system might consist of the following steps:
1. Accept input (tentative birth).
2. Validate input (birth).
3. Transmit acknowledgment to requester.
4. Do input processing.
5. Search file.
6. Request directions from user.
7. Accept input.
8. Validate input.
9. Process request.
10. Update file.
11. Transmit output.
12. Record transaction in log and cleanup (death).
 The user processes these steps as a single transaction.
 From the system’s point of view, the transaction consists of twelve steps and ten different
kinds of subsidiary tasks.
 Most online systems process many kinds of transactions.
 For example, an automatic bank teller machine can be used for withdrawals, deposits, bill
payments, and money transfers.
 Furthermore, these operations can be done for a checking account, savings account,
vacation account, Christmas club, and so on.
 Although the sequence of operations may differ from transaction to transaction, most
transactions have common operations.
 For example, the automatic teller machine begins every transaction by validating the user’s
card and password number.
 Tasks in a transaction flowgraph correspond to processing steps in a control flowgraph.
 As with control flows, there can be conditional and unconditional branches, and junctions.
(ii) Example:
 The following figure shows part of a transaction flow.
 A transaction flow is processed in Forms. Each form consists of several pages with records
and fields in it.
 A system is taken as the terminal controller to process these form. Only those forms which
are located on a central computer are requested for processing.

1
Software Testing Methodologies Unit II

User Request
D1 A
BEGIN Order form
Type ?
From CPU

Accept Process
Wait Order form form B
From CPU

Transmit Accept
B C Any
page to Wait field more
terminal input fields

Transmit
answers to D
CPU

Wait for Accept

D Valid
CPU CPU
confirm confirm ?
C

User Transmit
More want EXIT diagnostic C
Pages review terminal

Set up
review

2
Software Testing Methodologies Unit II
 Long forms are compressed and transmitted by the central computer to minimize the
number of records in it.
 The output of each page is transmitted by the terminal controller to the central computer.
 If the output is invalid, the central computer transmits a code to the terminal controller.
 The terminal controller in tern transmits the code to the user to check the input. At the end
the user reviews the filled out form.
 The above figure shows the processing of a transaction using forms.
 When the transaction is to be initiated, the process p1 requests forms from CPU.
 The central computer accepts the form in the process p3. p4 process the form.
 The characteristics of the transactions are shown by using a decision box D1 to
determine whether to cancel or process further.
 These decisions are handled by the terminal controller.
 P5 transmits the page to the terminal.
 D2 and D4 are the decision boxes to know whether the form needs more pages or not.
 D3 is a decision for the structure of the form, to validate the input.
 If necessary, the user reviews whole system in process p12
 The central computer then transmits a diagnostic code back to the terminal controller
in p11. After reviewing, the transaction flow is closed and exit operation is performed. 
(iii) Usage:
 Transaction flows are indispensable for specifying requirements of complicated systems,
especially online systems.
 A big system such as an air traffic control or airline reservation system has not hundreds,
but thousands of different transaction flows.
 The flows are represented by relatively simple flowgraphs, many of which have a single
straight-through path.
 An ATM system, for example, allows the user to try, say three times, and will take the card
away the fourth time.
(iv) Implementation:
 Transaction flow has an implicit representation of system control structure.
 That is, there is no direct relation between the process and decisions.
 A transaction flow is represented by a path taken by a transaction through a succession of
processing modules. These transactions are placed in a transaction-control block.
 The transactions present in that block are processed according to their flow.
 Each transaction is represented by a token and the transaction flowgraph shows a pictorial
representation of these tokens.
 The transaction flowgraph is not the control structure of the program.
 The below figure a shows transaction flow and corresponding implementation of a
program that creates that flow.
 This transaction goes through input processing, and then passes through process A,
followed by B.
 The result of process B may force the transaction to pass back to process A.
 The transaction then goes to process C, then to either D or E, and finally to output
processing.
 Figure b is a diagrammatic representation of system control structure.
 This system control structure is controlled either by an executive or scheduler or
dispatcher operating system.
 The links in the structure either represents a process queue or a dispatcher queue.
 The transaction is created by placing a token on an input queue.

3
Software Testing Methodologies Unit II
 The scheduler then examines the transaction and places it on the work queue for
process A, but process A will not necessarily be activated immediately.
 When a process has finished working on the transaction, it places the transaction-
control block back on a scheduler queue.
 The scheduler then examines the transaction control block and routes it to the next
process based on information stored in the block.
 The scheduler contains tables or code that routes the transaction to its next process.
In systems that handle hundreds of transaction types, this information is usually stored
in tables rather than as explicit code.
 Alternatively, the dispatcher may contain no transaction control data or code; the
information could be implemented as code in each transaction processing module.
D

Input S S B S C S S Output
A

(a) Transaction Flow

E

DISC TAPES
HANDLER

EXECUTIVE-
FRONT OUTPUT
END SCHEDULER- AND/OR OPERATING SYSTEM MODULE
DISPATCHER

DISPATCHER
QUEUES
A Processor B Processor C Processor D Processor E Processor
PROCESS
QUEUES
Application Processes

(b) System Control Structure

DO ALL DISC DO TAPE DO NEW DISC

1 Bs READS Cs WRITES Bs WRITES
3

DO DISC DO TAPE DO NEW DISC

3 Ds READS As READS Es WRITES
1

(c) Executive/Dispatcher Flowchart

4
Software Testing Methodologies Unit II
 Figure c shows a simplified representation of transaction flow.
 Let’s say that while there could be many different transaction flows in the system, they
all used only processes A, B, C, D, E, and disc and tape reads and writes, in various
combinations.
 Just because the transaction flow order is A,B,C,D,E is no reason to invoke the
processes in that order.
 For other transactions, not shown, the processing order might be B,C,A,E,D. A fixed
processing order based on one transaction flow might not be optimum for another.
 Furthermore, different transactions have different priorities that may require some to
wait for higher-priority transactions to be processed.
 Similarly, one would not delay processing for all transactions while waiting for a
specific transaction to complete a necessary disc read operation.
(v) Perspective:
 There were no restrictions on how a transaction’s identity is maintained: implicit, explicit, in
transaction control blocks, or in task tables.
 Transaction-flow testing is the ultimate black-box technique because all we ask is that there
be something identifiable as a transaction and that the system will do predictable things to
transactions.
 Transaction flowgraphs are a kind of data flowgraph.
 Data flowgraphs and control flowgraphs the most important difference is in control
flowgraphs we defined a link or block as a set of instructions such that if any one of them
was executed, all (barring bugs) would be executed.
 For data flowgraphs in general, and transaction flowgraphs in particular, we change the
definition to identify all processes of interest.
 Another difference to which we must be sensitive is that the decision nodes of a transaction
flowgraph can be complicated processes in their own rights.

(vi) Complications:
(a) General
 Transaction flows don’t have a good structured design for code.
 The problems of transaction flows result in problems like error conditions, malfunctions,
recovery actions etc.
 These errors are unstructured. As features are added into the transaction flows the
complexity of the transaction flow increases.
 Transactions are interactions between modules. A good system design indicates that
there is no implementation of new transaction or changing of an existing transaction.
 Hence transaction flow model results in consequences such as poor response times,
security problems, inefficient processing, dangerous processing etc.
 The decision nodes of a transaction flowgraph can be complicated.
 These nodes have exists that go to central recovery processes.
 The effect of interrupts in a transaction flow model converts every process box into
many, with exit links.
 Therefore the test design is no longer fit for transaction flow model.
 Examples for the transaction flow to be imperfect.
(b) Births
 A transaction can give birth to others and can also merge with others in many of the
systems. From the time they are created to the time they are completed, transaction
flows have a unique identity.

5
Software Testing Methodologies Unit II
 The following figure shows three different possible interpretations of the decision nodes
with two or more outlinks.
Alternate 1 Parent Daughter

Parent Parent

Alternate 2 Daughter Daughter

(a) Decision (b) Biosis (c) Mitosis

 In figure a, a transaction (Birth) has been created. The incoming transaction at decision
node gives birth of two new transactions.
 The two transactions alternate 1 and alternate 2 has a different or same identity.
 The figure b shows a different situation compared to figure a.
 The parent transaction gives birth to two new transactions.
 One transaction has the same identity as Parent the other transaction results in a
different identity Daughter. This situation is called Biosis.
 The figure c is similar to figure b, except that the parent transaction is destroyed and
two new transactions (daughters) are created. This situation is called mitosis.
(c) Mergers
 Merging is as troublesome as transaction flow splitting. The two transactions are
merged at decision node giving a new transaction with the same or different identity.

Path 1 Predator Parent

Continue Predator Daughter

Path 2 Prey Parent

(a) Junction (b) Absorption (c) Conjunction

 In figure a path 1 and path 2 merge at a junction resulting in a single one Continue.
 The figure b is a predator transaction absorbs a prey. The prey is gone but the predator
retains its identity.
 The figure c shows a slightly different situation in which two parent transactions merge
to form a new daughter.
(d) Theoretical Status and Pragmatic Solutions (Solutions for the above examples)
 Transaction flow model doesn’t meet the requirements of multiprocessor system.
Therefore a generic model called Petri is taken.
 Petri nets use operations that include explicit representation of tokens in the stages of
process.
 Petri net have been used to test the problems in protocol testing, network testing and so
on. The application to software testing is still in its beginning stage to determine whether
it is a productive model or not.

6
Software Testing Methodologies Unit II
 As long as test results are good, the imperfect model doesn’t not matter because the
complexities that can invalidate the model have been ignored.
 The following are some of the possible cases:
1. Biosis
 The parent flow is followed from beginning of a transaction flow to the end of a
transaction flow.
 A new birth is treated as a new flow, either to end or to absorb that birth.
2. Mitosis
 It begins from the parent’s flow to the mitosis point. From mitosis point, an
additional flow starts and get destroyed at their respective ends.
3. Absorption
 In this situation, the parent’s flow is treated as the primary flow. The parent flow
is modeled from its absorption point to the point at which it gets destroyed.
4. Conjugation
 This situation is the opposite of mitosis situation. Each parent flow is modeled
from its birth to the conjugation point.
 And from the conjugation point, the resulting child flow starts and get destroyed.
 Births, Mitosis, Absorptions, and conjugations are as problematic for the software
designers.
 Illegal births, wrongful deaths and lost children are some of the common problems.
 Although the transaction flow is modeled by simple flowgraphs, they recognize bugs
where transactions are created, absorbed and conjugated.
(vii) Transaction flow structure:
 A sequential flow of operations is represented by a structure called a transaction flow
structure.
 Even transaction flows are analogous to control flowgraphs, it is not necessary that
good structure provided for code should also exist for transaction flows. 
 Transactions flows are often considered as ill-structured due to the following reasons.
1. It’s a model of a process, not just code. While processing the transaction, humans
can’t be forced to follow the rules of a specific software structure, as they may
incorporate decisions, loops, etc
2. Behavior of other uncontrolled systems may be incorporated by some parts of the
transactional flow.
3. Permanent ill-structured nature of the transaction flow leads to loop jumps
uncontrollable GOTO statements etc. Not even a small part of the transaction flow
has the ability to handle error detection, failures, malfunctioning, recovery actions etc
4. If any new features are added and enhancements are made in transactional flows,
then the complexity of each and every transaction inherently increases. For instance
one can’t expect a good transaction flow from lawyers, politicians, salesman etc
5. Basically systems are designed from specific modules and the transaction flows are
designed or produced through the module of interaction..
6. Modeling of interrupts, multitasking, synchronization, polling, queue disciplines are
not related to structuring..
(2) Transaction Flow Testing Techniques:
(i) Get the Transaction Flows:
 Complicated systems that process a lot of different complicated transactions should have
explicit representations of the transaction flows, or the equivalent documented.

7
Software Testing Methodologies Unit II
 The transaction flows can be mapped into programs such that the flow of transaction will be
created easily.
 The processing of the transactions is done in the design phase.
 The overview section in design phase contains the details of the transaction flows.
 Detailed transaction flows are necessary to design the system’s functional test.
 Transaction flows are similar to control flow graphs where the act of getting information can
be more effective.
 Therefore the bugs can be determined. The flow of transaction in design phase is done
step by step such that the problems would not arise and a bad design can be avoided.
(ii) Transaction Flow testing:
 Transaction flow testing is a technique used in computerized applications.
 The transaction flow testing technique is used to control the documents that require the
auditor to specify the following.
 The business cycle in the flow.
 The various types of transaction that flow through individual cycle.
 The operations that are carried out within the cycle.
 The objectives of internal control
 The internal control methods used to attain each objective.
 The tester in the transaction flow testing is used to develop a flowchart. The tester tracks
the transaction flow and performs various functions in the same order as that of the
transaction.
 The internal control methods are recognized at each point of the transaction flow.
(iii) Inspections, Reviews, Walkthroughs:
 Transaction flows are a natural agenda for system reviews or inspections.
 Start transaction-flow walkthroughs at the preliminary design review and continue them in
ever greater detail as the project progresses.
1. In conducting the walkthroughs, you should:
a. Discuss enough transaction types (i.e., paths through the transaction flows) to
account for 98%–99% of the transactions 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 to the specification and to show how that
transaction, directly or indirectly, follows from the requirements.
2. Make transaction-flow testing the cornerstone of system functional testing just as path
testing is the cornerstone of unit testing. For this you need enough tests to achieve C 1
and C2 coverage of the complete set of transaction flowgraphs.
3. Select additional transaction-flow paths (beyond C1 + C2) for loops, extreme values,
and domain boundaries.
4. Select additional paths for weird cases and very long, potentially troublesome
transactions with high risks and potential consequential damage.
5. Design more test cases to validate all births and deaths and to search for lost
daughters, illegitimate births, and wrongful deaths.
6. 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.
7. Have the buyer concur that the selected set of test paths through the transaction flows
constitute an adequate system functional test.
8. Tell the designers which paths will be used for testing but not (yet) the details of the
test cases that force those paths.

8
Software Testing Methodologies Unit II
(iii) Path Selection:
 Path selection for system testing based on transaction flows should have a distinctly
different flavor from that of path selection done for unit tests based on control flowgraphs.
 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 weird paths.
 This procedure is best done early in the game, while the system design is still in progress,
before processing modules have been coded. The covering set of paths belongs in the
system feature tests.
 It gives everybody more confidence in the system and its test.
(iv) Sensitization:
 The Good news is most of the normal paths are very easy to sensitize—80%–95%
transaction flow coverage (C1 + C2) is usually easy to achieve.
 The bad news is that 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.
 Sensitization is the act of defining the transaction. If there are sensitization problems on the
easy paths, then bet on either a bug in transaction flows or a design bug.
 The reason these paths are often difficult to sensitize is that they correspond to error
conditions, synchronization problems, overload responses, and other anomalous situations.
1. Use Patches
 The dirty system tester’s best, but dangerous, friend.
 It’s a lot easier to fake an error return from another system by a judicious patch
than it is to negotiate a joint test session.
2. Mistune
 Test in a system sized with grossly inadequate resources.
 By “grossly” I mean about 5%–10% of what one might expect to need.
 This helps to force most of the resource-related exception conditions.
3. Break the Rules
 Transactions almost always require associated, correctly specified, data structures
to support them.
 Often a system database generator is used to create such objects and to assure
that all required objects have been correctly specified.
 Bypass the database generator and/or use patches to break any and all rules
embodied in the database and system configuration that will help you to go down
the desired path.
4. Use Breakpoints
 Put breakpoints at the branch points where the hard-to-sensitize path segment
begins and then patch the transaction control block to force that path.
 You can use one or all of the above methods, and to sensitize the strange paths.
 These techniques are especially suitable for those long tortuous paths that avoid the exit.
(v) Instrumentation:
 Instrumentation plays a bigger role in transaction-flow testing than in unit path testing.

9
Software Testing Methodologies Unit II
 Counters are not useful because the same module could appear in many different flows
and the system could be simultaneously processing different transactions.
 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.
(vi) Test databases:
 About 30%–40% of the effort of transaction-flow test design is the design and maintenance
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 designs his own, unique database, which is
incompatible with all other programmers’ and testers’ needs.
 The consequence is that every tester (independent or programmer) needs exclusive use of
the entire system. Furthermore, many of the tests are configuration-sensitive, so there’s no
way to port one set of tests over from another suite.
(vii) 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 achieve C1 + C2 transaction-flow
coverage, don’t bother with transaction-flow testing if you don’t have the time and
resources to almost completely automate all test execution.
 You’ll be running and rerunning those transactions not once, but hundreds of times over the
project’s life.
 Transaction-flow testing with the intention of achieving C1 + C2 usually leads to a big
increase in the number of test cases.
 Without execution automation you can’t expect to do it right.
DATA FLOW TESTING
(3) Basics of Data-Flow Testing:
(i) Motivation and assumptions:
(a) What is it?
 Data-flow testing is the name given to a family of test strategies based on selecting
paths through the program’s control flow in order to explore sequences of events related
to the status of data objects.
 For example, pick enough paths to assure that every data object has been initialized
prior to use or that all defined objects have been used for something.
(b) Motivation
 It is our belief that, just as one would not feet confident about a program without
executing every statement in it as part of some test, one should not feel confident about
a program without having seen the effect of using the value produced by each and
every computation.
 To the extent that we achieve the widely sought goal of reusable code, we can expect
the balance of source code statements to shift ever more toward data statement
domination.

10
Software Testing Methodologies Unit II
 In all known hardware technologies, memory components have been, are, and are
expected to be cheaper than processing components.
(c) New Paradigms-Data-Flow Machines
 Data flow machines are programmable computers that use packet switching
communication.
 The hardware in data flow machines is optimized for data-driven execution and for fine
grain parallelism.
 Data flow machines support recursion. Recursion is a mechanism used to map virtual
space to a physical space of realistic size. It is the fastest mechanism.
 The prototype in data flow machines is taken as a processing or working element.
 The overhead in data flow machines can be made acceptable by sophisticated
hardware.
 There is a sufficient parallelism in many computer programs.
 The problem in data flow machine is in distribution of computation and storage of data
structures.
 Another problem in data flow machines is to cease (stop) parallelism when resources
tend to get overloaded.
 Some of the data flow machines are Von Neumann machines and MIMD (multi
instruction, multi data) machines.
Von Neumann machines
 The Von Neumann architecture executes one instruction at a time in the following,
typical, microinstruction sequence.
1. Fetch instruction from memory.
2. Interpret instruction.
3. Fetch operand(s).
4. Process (execute).
5. Store result (perhaps in registers).
6. Increment program counter (pointer to next instruction).
7. GOTO 1.
 The pure Von Neumann machine has only one set of control circuitry to interpret the
instruction, only one set of registers in which to process the data, and only one
execution unit (e.g., arithmetic/logic unit).
 This design leads to a sequential, instruction-by-instruction execution, which in turn
leads to control-flow dominance in our thinking.
 The Von Neumann machine forces sequence onto problems that may not inherently be
sequential.
MIMD (multi-instruction, multi data) machines
 MIMD machines are massively parallel machines.
 They fetch several instructions in parallel.
 Therefore they have several mechanisms for executing the above steps 1-7.
 MIMD machines can also perform arithmetic or logical operation simultaneously.
 These operations are done on different data objects.
 In these machines parallel computation is left to the compiler for processing instructions.
 For a MIMD machine, the instructions are produced in parallel flow while for a
conventional machine the instructions are produced in sequential flow.
 The Parallel machine is MIMD machine with multiple processors and sequential
machine is Von Neumann machine with only one processor.

11
Software Testing Methodologies Unit II
(d) The Bug Assumptions
 The bug assumption for data-flow testing strategies is that control flow is generally
correct and that something has gone wrong with the software so that data objects are
not available when they should be, or silly things are being done to data objects.
 Also, if there is a control-flow problem, we expect it to have symptoms that can be
detected by data-flow analysis.
(ii) Data Flowgraphs:
(a) General:
 The data flowgraph is a graph consisting of nodes and directed links (i.e., links with
arrows on them). The data flow is between the data objects in the data flowgraph.
 The data flowgraph not only shows the flow of data but also shows the deviation
between the data objects to be implemented.
(b) Data Object State and Usage:
 Data objects can be three states i.e. created, killed and used states.
 They can be used in two distinct ways: in a calculation part and in the control flowgraph
part. The following symbols denote these possibilities.
d—defined, created, initialized, etc.
k—killed, undefined, released.
u—used for something.
c—used in a calculation part.
p—used in a predicate for operation purpose.
 Every symbol in data flowgraph has a meaning. Each symbol is described below.
1. Defined:
 An object is defined explicitly when it appears in a data declaration or implicitly
when it appears on the left-hand side of an assignment statement.
 “Defined” can also be used to mean that a file has been opened, a dynamically
allocated object has been allocated, something is pushed onto the stack, and so
on.
2. Killed or Undefined
 When an object is released and is no longer in use, then it is known as a killed
object. Killed object is similar to an undefined object.
 An object that is not available in the statement is known as Undefined object.
 For example, a loop in FORTRAN language gets terminated when an undefined
variable exists.
 Another example for a killed variable is that, if an object A has been assigned a
value such as A:=8 and another assignment is done for the same object A, such as
A:=11 then the previous value of A (i.e. 8) is killed and redefined (i.e.11). Therefore
the value of A is 11.
 Define and kill are complementary operations. That is, they generally come in pairs
and one does the opposite of the other.
3. Usage
 A used variable is for computation (c) use and is on the right side of an assignment
statement.
 It is also used in a predicate (P) such as if z > 0, to evaluate the flow of control.
 Hence usage variables are used both in predicate and computational purposes.
(c) Data-Flow Anomalies:
 An anomaly is a situation or condition where an object is defined but not used. For
example
IF A>0 THEN X:=1 ELSE X:= -1
12
Software Testing Methodologies Unit II
A:= 0
A:= 0
A:= 0
A:= B + C
 From the above example, we notice that object A is defined trice to zero. Hence an
anomaly occurs.
 There are nine possible two-letter combinations for d, k and u. Some are bugs state,
some are suspicious (dangerous) state, and some are normal state.
dd—It results in a suspicious state where an object is defined twice.
dk—results in a bug state.
du—the normal case. The object is defined, then used.
kd—normal situation. An object is killed, then redefined.
kk—harmless but probably buggy.
ku—A bug state.
ud—suspicious state.
uk—normal situation.
uu—normal situation
 The three variables (d,k,u) show the representation of anomalous state.
 In addition to the above two-letter situations there are six single-letter situations
-k: possibly anomalous.
–d: okay. This is just the first definition along this path.
–u: possibly anomalous. Not anomalous if the variable is global and has been
previously defined.
k–: not anomalous. The last thing done on this path was to kill the variable.
d–: possibly anomalous.
u–: not anomalous.
 The single-letter situations do not lead to clear data-flow anomalies but only the
possibility thereof.
(d) Data-Flow Anomaly State Graph :
 The data flow anomaly defines an object to be in one of the following four different
states. The states are
K—undefined, previously killed, does not exist.
D—defined but not in use.
U—has been used for computation or in predicate.
A—anomalous

U D A

13
Software Testing Methodologies Unit II
 Don’t confuse these capital letters (K,D,U,A), which denote the state of the variable,
with the program action, denoted by lowercase letters (k,d,u).
 The data flow anomaly starts in K state.
 An attempt is made to use an undefined variable. Hence it goes in an anomalous (A)
state. The killed (K) state defines a variable d in defined (D) state.
 If a variable is killed from a defined (D) state then it becomes anomalous.
 The variable u is used in U state and is redefined d in D state.
 Variable k get killed in K state.
(e) Static versus Dynamic Anomaly Detection:
 Static analysis is an analysis done at compile time.
 The source code is checked and the quality is improved by removing the bugs in the
program.
 Syntax errors are detected in static analysis.
 To improve the quality of a document, the document is analyzed and checked by a tool.
 If a problem, such as a data-flow anomaly, can be detected by static analysis methods,
then it does not belong in testing—it belongs in the language processor.
 Static analysis tools are typically used by tools.
 Static analysis is done in design phases so that the whole model can be analyzed and
the inconsistencies can be detected.
 Static analysis can be used in the detection of security problem.
 Dynamic analysis is done at run time. Dynamic analysis detects anomalous situations at
run time with some of the data structures like Arrays, Pointers, Records etc.. 
1. Dead Variables
 Although it is often possible to prove that a variable is dead or alive at a given
point in the program, the general problem is unsolvable.
2. Arrays
 Arrays are problematic in that the array is defined or killed as a single object, but
reference is to specific locations within the array.
 Array pointers are usually dynamically calculated, to know whether the values
are within the boundary range or out of boundary range.
3. Records and Pointers
 The array problem and the difficulty with pointers is a special case of multipart
data structures.
 We have the same problem with records and the pointers to them.
 In the case of records, files are created and the names of such files are
dynamically known.
 Without execution there is no way to determine the state of such objects.
4. Dynamic Subroutine or Function Names in a Call
 A subroutine or function name is a dynamic variable in a call. What is passed, or
a combination of subroutine names and data objects, is constructed on a specific
path.
 There’s no way, without executing the path, to determine whether the call is
correct or not.
5. False Anomalies
 Anomalies don’t occur when the path of objects is not completed.
 Such anomalies are false anomalies. The problem of identifying whether a path
is completed or not is not solved.

14
Software Testing Methodologies Unit II
6. Recoverable Anomalies and Alternate State Graphs
 What constitutes an anomaly depends on context, application, and semantics.
 Huang provided two anomaly state graphs
7. Concurrency, Interrupts, System Issues
 Anomalies become more sophisticated while moving from single processor
surroundings to multi processors environment.
 The main purpose or task of interrupt is to develop correct anomalous which is
even performed in true concurrency or pseudo concurrency.
 The objective of system integration testing is to detect data flow anomalies at run
time that was not possible using context level testing.
 Although static analysis methods have limits, they are worth using and a continuing
trend in language processor design has been better static analysis methods, especially
for data flow anomaly detection.
 That’s good because it means there’s less for us to do as testers and we have far too
much to do as it is.
(f) Anomaly detection & types of data flow anomalies:
 An anomaly is a term that leads to inconsistency in the data flow analysis.
 The data flow is referred to as reading variables and data flow anomaly is referred to as
reading variables without having an idea that the value of the variable is in use or not. 
 During data flow analysis, every variable is referred to and inspected.
 There are different variables in data flow analysis.
 They are classified as
[Link] Variables Definition
1 Defined (d) Value assigned to a variable
2 Referenced (r) Value read or used by a variable
3 Undefined (u) Variable that has no defined value
 Depending on these variables, three different data flow anomalies are distinguished.
They are
1. ur-anomaly
2. du-anomaly
3. dd-anomaly
1. ur-anomaly:
 During data flow analysis if the undefined value of a variable (u) is read
(r) then it is known as a ur-anomaly.
2. du-anomaly:
 A defined (d) variable becomes invalid or undefined (u) variable when a
variable is not used within a particular time.
3. dd-anomaly:
 This anomaly occurs when the variable accepts a value at the second
assignment (d) and the first assignment value had not been used.
 This situation occurs in dd-anomaly. For example if A:=7,A:=11 then it
accepts A:=11.
 Depending on the usage of variables the anomalies can be detected.
 For example consider c++example The example shows an exchange of values of the
variables A and B with the help of another variable get if the value of the variable A is
greater than the value of the variable B.
void exchange(int &A,int &B)
{
15
Software Testing Methodologies Unit II
int get;
if(A>B)
{
B=get;
B=A;
get=A;
}
}
 The detection of anomalies are
1. ur-anomaly:
 In the above example, the variable get is used on the right side of an
assignment.
 The variable get has an undefined value because it is not initialized
where it is declared.
 This undefined variable is being read or referred to and hence it results in
ur-anomaly.
2. dd-anomaly:
 The variable B is used twice on the left side of an assignment.
 The first assignment value becomes invalid or unused and the second
assignment value is taken or used.
 Therefore the unused variable B of the first assignment results in dd-
anomaly
3. du-anomaly:
 The variable get has a defined value in the last assignment. The defined
variable cannot be used anywhere in the function because only those
variables are valid which are inside the function.
 Therefore the unused variable results in du-anomaly.
(iii) The Data-Flow Model:
(a) General:
 Our data-flow model is based on the program’s control flowgraph—don’t confuse that
with the program’s data flowgraph.
 So Data-flow model is considered as the heart of programs control flowgraph.
 It consists of links which are denoted by symbols d,k,u,c,p or a sequence of the symbols
like dd, du, ddd etc.
 This sequence specifies the sequential flow of data operations on the link with respect
to the given variable.
 These symbols are called link weights as each link is assigned with weights (d,k,u,c,p).
 For all variables and array elements, different set of link weights exist.
The symbols are defined as
d= Defined object , k=Killed object, u=Used object
c=Object for calculation purpose, p=predicate
(b) Components of the model:
 Here are the modeling rules.
1. To every statement there is a node, whose name (number) is unique.
Every node has at least one outlink and at least one inlink except exit nodes, which do
not have outlinks, and entry nodes, which do not have inlinks.

16
Software Testing Methodologies Unit II
2. Exit nodes are dummy nodes placed at the outgoing arrowheads of exit statements
(e.g., END, RETURN), to complete the graph. Similarly, entry nodes are dummy nodes
placed at entry statements (e.g., BEGIN) for the same reason.
3. Another components is simple statements. These are the statements with only one
outlink. The weight of simple statement is determined by sequential actions of data-flow
with respect to the given statement.
For example, consider a simple statement A:= A + B in most languages is weighted
by cd or possibly ckd for variable A.
4. Predicate nodes (e.g., IF-THEN-ELSE, DO WHILE, CASE) are weighted with the p-
use(s) on every outlink, appropriate to that outlink.
5. Every sequence of simple statements (e.g., a sequence of nodes with one infink and
one outlink) can be replaced by a pair of nodes that has, as weights on the link between
them, the concatenation of link weights.
6. If there are several data-flow actions on a given link for a given variable, then the
weight of the link is denoted by the sequence of actions on that link for that variable.
7. If multiple data-flow actions are available on a link for a variable, then its
corresponding weight is determined by the sequence of actions. Inversely a sequence
of equivalent links are used to replace the link with more data flow actions.
(c) Putting it together:
 The following figure a shows the control flowgraph. The figure b shows this control
flowgraph annotated for variables X and Y data flows.
 The figure c shows the same control flowgraph annotated for variable Z. Z is first
defined by an assignment statement on the first link.
 Z is used in a predicate (Z >= 0?) at node 3, and therefore both outlinks of that node—
(3,4) and (3,5)—are marked with a p. The data-flow annotation for variable V is shown
in figure d.
(4) Strategies in Data-Flow Testing:
(i) General:
 Data-flow testing strategies are structural strategies.
 Data-flow testing strategies are based on the program’s control flowgraph.
 Data-flow testing strategies are based on selecting test path segments (also called
subpaths) that satisfy some characteristic of data flows for all data objects. For example, all
subpaths that contain a d (or u, k, du, dk).
 These strategies differ in determining whether the paths of a given type are required or only
one path of that type is required.
 The test set includes the predicate uses and computational uses of variables.
 This usage also differs in the test set that is either computational use or predicate use of
variables.
(ii) Terminology:
 We’ll assume for the moment that all paths are achievable. Some terminology.
 A definition-clear path segment
 A path segment is a sequence of connected links between nodes. This first link of
the path is defined and the subsequent link of that path is killed.
 A definition-clear path segment is a connected sequence of links such that X is
(possibly) defined on the first link and not redined or killed on any subsequent link of
that segment.
 All paths in figure b are definition clear because variables X and Y are defined only
on the first link (1,3) and thereafter. Similarly for variable V in figure d.

17
Software Testing Methodologies Unit II
 In Figure c we have a more complicated situation. The following path segments are
definition-clear: (1,3,4), (1,3,5), (5,6,7,4), (7,8,9,6,7), (7,8,9,10), (7,8,10), (7,8,10,11).
 Subpath (1,3,4,5) is not definition-clear because the variable is defined on (1,3) and
again on (4,5).
 For practice, try finding all the definition-clear subpaths for this routine (i.e., for all
variables).

1 3 4 5 6 7

2 13 12 11 10 9 8

(a) Unannotated Control Flowgraph

1 3 4 5 6 7

2 13 12 11 10 9 8

(b) Control Flowgraph Annotated for X and Y Data Flows.

1 3 4 5 6 7

2 13 12 11 10 9 8

(c) Control Flowgraph Annotated for Z Data Flow

18
Software Testing Methodologies Unit II

1 3 4 5 6 7

2 12 11 11 9 8

(d) Control Flowgraph Annotated for V Data Flow

 The fact that there is a definition-clear subpath between two nodes does not imply
that all subpaths between those nodes are definition-clear; in general, there are
many subpaths between nodes, and some could have definitions on them and some
not.
 A definition clear sub path does not include loops. For example a loop consists of
(i,j) and (j,i) links.
 These links have a definition on (i,j) and a computational use on (j,i). If we include
loops in a path by definition-clear path segment then there is no need to go around
such path.
 Because of this the testing strategies will have a finite number of test paths.
 The strategies must be weaker than the paths because a bug can be created
whenever a loop has been traversed and iterated.
2. A loop-free path segment
 A loop-free path segment is a path segment for which every node is visited at most
once.
 Path (4,5,6,7,8,10) in figure c is loop free, but path (10,11,4,5,6,7,8,10,11,12) is not
because nodes 10 and 11 are each visited twice.
3.A simple path segment
 A simple path segment is a path segment in which at most one node is visited twice.
 For example in figure c (7,4,5,6,7) is a simple path segment.
 A simple path segment is either loop-free or if there is a loop, only one node is
involved.
4.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 path.
 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.
(iii) The Strategies:
(a) Overview:
 The structural test strategies are based on the program’s control flowgraph.
 These strategies differ in determining whether the paths of a given type are required or
only one path of that type is required.
 The test set includes the predicate uses and computational uses of variables.

19
Software Testing Methodologies Unit II
 This usage also differs in the test set that is either computational use or predicate use of
variables.
 The different data flow testing strategies are given below.
(b) All-du Paths (ADUP) strategy:
 The all-du-paths (ADUP) strategy is the strongest data-flow testing strategy discussed
here. It requires that every du path from every definition of every variable to every use
of that definition be exercised under some test.
 In the above figure b variables X and Y are used only on link (1,3), any test that starts at
the entry satisfies this criterion (for variables X and Y, but not for all variables as
required by the strategy).
 The situation for variable Z in figure c is more complicated because the variable is
redefined in many places. For the definition on link (1,3) we must exercise paths that
include subpaths (1,3,4) and (1,3,5). The definition on link (4,5) is covered by any path
that includes (5,6), such as subpath (1,3,4,5,6, ...).
 The (5,6) definition requires paths that include subpaths (5,6,7,4) and (5,6,7,8).
 Variable V in figure d is defined only once on link (1,3).
 Because V has a predicate use at node 12 and the subsequent path to the end must be
forced for both directions at node 12, the all-du-paths strategy for this variable requires
that we exercise all loop-free entry/exit paths and at least one path that includes the
loop caused by (11,4).
 Note that we must test paths that include both subpaths (3,4,5) and (3,5) even though
neither of these has V definitions.
 They must be included because they provide alternate du paths to the V use on link
(5,6). Although (7,4) is not used in the test set for variable V, it will be included in the
test set that covers the predicate uses of array variable V() and U.
 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.
(c) All-uses Strategy:
 Just as we reduced our ambitions by stepping down from all paths (P ∞) to branch
coverage (P2), say, 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 the all-uses (AU) 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.
 In figure d, ADUP requires that we include subpaths (3,4,5) and (3,5) in some test
because subsequent uses of V, such as on link (5,6), can be reached by either
alternative. In AU either (3,4,5) or (3,5) can be used to start paths, but we don’t have to
use both.
 Similarly, we can skip the (8,10) link if we’ve included the (8,9,10) subpath.
(d) All-p-Uses/Some-c-Uses and All-c-Uses/Some-p-Uses Strategies:
 Weaker criteria require fewer test cases to satisfy. We would like a criterion that is
stronger than P2 but weaker than AU.
 Therefore, select cases as for All (Section 3.3.3) except that if we have a predicate use,
then (presumably) there’s no need to select an additional computational use (if any).
More formally, the all-p-uses/some-c-uses (APU+C) strategy is defined as follows: for
every variable and every definition of that variable, include at least one definition-free
path from the definition to every predicate use; if there are definitions of the variable that

20
Software Testing Methodologies Unit II
are not covered by the above prescription, then add computational-use test cases as
required to cover every definition.
 The all-c-uses/some-p-uses (ACU+P) strategy reverses the bias: first ensure coverage
by computational-use cases and if any definition is not covered by the previously
selected paths, add such predicate-use cases as are needed to assure that every
definition is included in some test.
 In figure b for variables X and Y, any test case satisfies both criteria because definition
and uses occur on link (1,3). In figure c, for APU+C we can select paths that all take the
upper link (12,13) and therefore we do not cover the c-use of Z: but that’s okay
according to the strategy’s definition because every definition is covered.
 Links (1,3), (4,5), (5,6), and (7,8) must be included because they contain definitions for
variable Z. Links (3,4), (3,5), (8,9), (8,10), (9,6), and (9,10) must be included because
they contain predicate uses of Z.
 Find a covering set of test cases under APU+C for all variables in this example—it only
takes two tests. In figure d, APU+C is achieved for V by
(1,3,5,6,7,8,10,11,4,5,6,7,8,10,11,12[upper], 13,2) and (1,3,5,6,7,8,10,11,12[lower],
13,2). Note that the c-use at (9,10) need not be included under the APU+C criterion.
 The figure d shows a single definition for variable V. C-use coverage is achieved by
(1,3,4,5,6,7,8,9,10,11,12,13,2). In figure c, ACU+P coverage is achieved for Z by path
(1,3,4,5,6,7,8,10, 11,12,13[lower], 2), but the predicate uses of several definitions are
not covered. Specifically, the (1,3) definition is not covered for the (3,5) p-use, the (7,8)
definition is not covered for the (8,9), (9,6) and (9, 10) p-uses.
 The above examples imply that APU+C is stronger than branch coverage but ACU+P
may be weaker than, or incomparable to, branch coverage.
(e) All definitions Strategy:
 The all-definitions (AD) strategy asks only that every definition of every variable be
covered by at least one use of that variable, be that use a computational use or a
predicate use.
 Path (1,3,4,5,6,7,8, . . .) satisfies this criterion for variable Z, whereas any entry/exit path
satisfies it for variable V. From the definition of this strategy we would expect it to be
weaker than both ACU+P and APU+C.
(f) All-Predicate Uses, All-Computational Uses Strategies:
 The all-predicate-uses (APU) strategy is derived from the 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.
 Similarly, the all-computational-uses (ACU) strategy is derived from ACU+P by dropping
the requirement that we include a p-use if there are no c-use instances following a
definition.
 It is intuitively obvious that ACU should be weaker than ACU+P and that APU should be
weaker than APU+C.
(g) Ordering the Strategies:
 The below figure compares path-flow and data-flow testing strategies. The arrows
denote that the strategy at the arrow’s tail is stronger than the strategy at the arrow’s
head.
 The right-hand side of this graph, along the path from “all paths” to “all statements” is
the more interesting hierarchy for practical applications.
 Variations of data-flow strategies exist, including different ways of characterizing the
paths to be included and whether or not the selected paths are achievable.

21
Software Testing Methodologies Unit II
 The strength relation graph of the above figure can be substantially expanded to fit
almost all such strategies into it. Indeed, one objective of testing research has been to
place newly proposed strategies into the hierarchy.

ALL PATHS

ALL du PATHS

ALL USES

ALL-c/SOME-p ALL-p/SOME-c

ALL-c USES ALL DEFS ALL-p USES

BRANCH

STATEMENT

(iv) Slicing, Dicing, Data Flow and Debugging:

(a) General:
 Slicing is a program originally developed for conventional languages.
 It helps in understanding data flow and debugging techniques. The Slicing is done
based on variable sharing.
 Dicing and debugging are the concepts related to removal of unwanted bugs.
(b) Slices and Dices:
 There are two types of slicing technique. i.e. Static slicing & dynamic slicing.
 Static slicing is a part of a program defined with respect to a given variable X and a
statement i:
 It consists of all statements that could affect the value of X at statement i.
 The result of a false statement effect in an improper computational use or predicate use
of some other variable.
 If the variable X is correct then the bug is detected in the program itself.
 A program dice is a part of a slice in which the statements which are correct has been
removed.
 The idea behind slicing and dicing is based on Weiser’s observation that these
constructs are at the heart of the procedure followed by good debuggers.
 Dynamic slicing is a refinement of static slicing. Dynamic slicing compares the data flow
relationship with respect to static data flows.
 Dicing is defined as the process of refining slice by removing all the unwanted bug
statements in a program.
 Basically a dice is generated from a slice which posses the information about testing or
debugging the function of a dice is to improve or refine a slice by removing the
unwanted statements from a program.
 The process of dicing is often employed by debuggers. The current methods of dicing
encompass assumptions related to bugs and programs.
 Due to the existence of bugs the usage of real program is declined.

22
Software Testing Methodologies Unit II
(c) Data-flow:
 Data flow is defined as the process of reading variables. The central concept of data-
flow is to bridge the gap between debugging and testing.
 The idea of slices was extended to arrays and data vectors and the data-flow relations
(such as dc and dp) in dynamic slices are analogous compared to the data-flow
relations in static slices (dc and dp).
 Where dc and dp are the data objects. Here
d=Object definition,
c=Computation
p=Symbol used in a predicate for operation purpose.
(d) Debugging:
 Debugging is defined as an iterative method in which refinement of slices is carried out
through dices so as to obtain the dicing information.
 Basically debugging is carried out after a test case is successfully executed.
 The process of debugging terminates when all the bugs that exists in the program
statements are corrected.
 Methods of slicing leads to commercial testing or development of different debugging
tools.
 The test cases involved in integration and testing are modeled for efficient error
detection, where as the cases involved in debugging are modeled for efficient error
isolation.
(5) Application of Data-Flow Testing:
 Data flow testing is used to detect the different abnormalities that may arise due to data
flow anomalies.
 Data flow testing shows the relationship between the data objects that represents data.
 Data flow testing strategies help in determining the usage of variables that are included in
the test set.
 Data flow testing is cost effective.
 Data flow testing solves the problems that are encountered while performing.
 Data flow testing uses practical applications rather than mathematical applications.
 Data flow testing is used in developing web applications with Java technology.

23
Software Testing Methodologies Unit II

DOMAIN TESTING

(1) Domains and paths:

(i) The Model:
 Domain testing can be based on specifications and/or equivalent implementation
information.
 If domain testing is based on specifications, it is a functional test technique; if based on
implementations, it is a structural technique.
 Domain testing is applied to one input variable or to simple combinations of two variables,
based on specifications.
 The schematic representation of Domain testing is given below.

DO CASE 2

DO CASE 3

DO CASE n

 First the different input variables are provided to a program.

 The classifier receives all input variables and divides them into different cases.
 Every case there should be at least one path to process that specified case.
 Finally output is received from this do cases..
(ii) A domain is a set:
 An input domain is a set. If the source language supports set definitions less testing is
needed because the compiler (compile-time and run-time) do much of it for us.
(iii) Domains, paths and predicates:
 In domain testing, predicates are assumed to be interpreted in terms of input vector
variables.
 If domain testing is applied to structure (implementation), then predicate interpretation must
be based on control flowgraph.
 If domain testing is applied to specifications, then predicate interpretation is based on data
flowgraph.
 For every domain there is at least one path through the routine.
 There may be more than one path if the domain consists of disconnected parts.
 Unless stated otherwise, we’ll assume that domains consist of a single, connected part.
 We’ll also assume that the routine has no loops.
 Domains are defined by their boundaries. For every boundary there is at least one
predicate.
 For example in the statement, IF X > 0 THEN ALPHA ELSE BETA we know that number
greater than zero, belong to ALPHA, number smaller to zero, belong to BETA.
24
Software Testing Methodologies Unit II
Review:
1. A domain is a loop free program.
2. For every domain there is at least one path through the routine.
3. The set of interpreted predicates defines the domain boundaries.
(iv) Domain Closure:
 To understand the domain closure, consider the following figure.

MIN MAX
D1 D2 D3

(a) Both side closed

MIN MAX
D1 D2 D3

(b) One side open

MIN MAX
D1 D2 D3

(c) Both side open

 If the domain boundary point belongs to the same domain then the boundary is said to
close. If the domain boundary point belongs to some other domain then the boundary is
said to open.
 In the above figure there are three domains D1, D2, D3.
 In figure a D2’s boundaries are closed both at the minimum and maximum values. If D2 is
closed, then the adjacent domains D1 and D3 must be open.
 In figure b D2 is closed on the minimum side and open on the maximum side, meaning
that D1 is open and D3 is closed. In figure c D2 is open on both sides, which mean that the
adjacent domains D1 and D3 must be closed.
(v) Domain Dimensionality:
 Depending on the input variables, the domains can be classified as number line domains,
planer domains or solid domains.
 That is for one input variable the value of the domain is on the number line, for two
variables the resultant is planer and for three variables the domain is solid.
 One important thing here is to note that we need not worry about the domains
dimensionality with the number of predicates. Because there might be one or more
boundary predicates.
(vi) The Bug Assumptions:
 The bug assumption for domain testing is that processing is okay but the domain definition
is wrong.
 An incorrectly implemented domain means that boundaries are wrong, which mean that
control-flow predicates are wrong.
 The following are some of the bugs that give to domain errors.
(a) Double-Zero Representation:
 Boundary errors for negative zero occur frequently in computers or programming
languages where positive and negative zeros are treated differently.
25
Software Testing Methodologies Unit II
(b) Floating-Point Zero Check:
 A floating-point number can equal to zero only if the previous definition of that number is
set it to zero or if it is subtracted from itself, multiplied by zero.
 Floating-point zero checks should always be done about a small interval.
(c) Contradictory Domains:
 Here at least two assumed distinct domains overlap.
(d) Ambiguous Domains:
 These are missing domain, incomplete domain.
(e) Over specified Domains:
 The domain can be overloaded with so many conditions.
(f) Boundary Errors:
 This error occurs when the boundary is shifted or when the boundary is tilted or missed.
(g) Closure Reversal
 This bug occurs when we have selected the wrong predicate such as x>=0 is written as
x<=0.
(h) Faulty Logic:
 This bug occurs when there are incorrect manipulations, calculations or simplifications
in a domain.
(vii) Restrictions:
(a) General
 Domain testing has restrictions. i.e. we cannot use domain testing if they are violated.
 In testing there is no invalid test, only unproductive test.
(b) Coincidental Correctness
 Coincidental correctness is assumed not to occur.
 Domain testing is not good for which outcome is correct for the wrong reason.
 One important point to be noted here is that, domain testing does not support Boolean
outcomes (TRUE/FALSE).
 If suppose the outputs are some discrete values, then there are some chances of
coincidental correctness.
(c) Representative Outcome
 Domain testing is an example of partition testing.
 Partition testing divide the program’s input space into domains.
 If the selected input is shown to be correct by a test, then processing is correct, and
inputs within that domain are expected to be correct.
 Most test techniques, functional or structural fall under partition testing and therefore
make this representative outcome assumption.
(d) Simple Domain Boundaries and Compound Predicates
 Each boundary is defined by a simple predicate rather than by a compound predicate.
 Compound predicates in which each part of the predicate specifies a different boundary
are not a problem: for example, x >= 0 .AND. x < 17, just specifies two domain
boundaries by one compound predicate.
(e) Functional Homogeneity of Bugs
 Whatever the bug is, it will not change the functional form of the boundary predicate.
(f) Linear Vector Space
 A linear predicate is defined by a linear inequality using only the simple relational
operators >, >=, =, <=, <>, and <.
 Example x2 + y2 > a2.
(g) Loop-free Software
 Loops (indefinite loops) are problematic for domain testing.
26
Software Testing Methodologies Unit II
 If a loop is an overall control loop on transactions, say, there’s no problem.
 If the loop is definite, then domain testing may be useful for the processing within the
loop, and loop testing can be applied to the looping values.
(2) Nice Domains:
(i) Where Do Domains Come From?
 Domains are often created by salesmen or politicians.
 The first step in applying domain testing is to get consistent and complete domain
specifications.
(ii) Specified versus Implemented Domains:
 Implemented domains can’t be incomplete or inconsistent but specified domains can be
incomplete or inconsistent.
 Incomplete means that there are input vectors for which no path is specified and
inconsistent means that there are at least two contradictory specifications.
(iii) Nice Domains:
(1) General
 The representation of Nice two-dimensional domains is as follows. .

 The U and V represent boundary sets and D represents domains.

 The boundaries have several important properties. They are linear, complete,
systematic, orthogonal, consistently closed, simply connected and convex.
 If domains have these properties, domain testing is very easy otherwise domain testing
is tough.
(2) Linear and Nonlinear Boundaries
 Nice domain boundaries are defined by linear inequalities or equations.
 The effect on testing comes from only two points then it represents a straight line.
 If it considers three points then it represents a plane and in general it considers n + 1
points then it represents an n-dimensional hyperplane.
 Linear boundaries are more frequently used than the non-linear boundaries.
 We can linearize the non-linear boundaries by using simple transformations.
(3) Complete Boundaries
 Complete boundaries are those boundaries which do not have any gap between them.
 Nice domain boundaries are complete boundaries because they cover from plus infinity
to minus infinity in all dimensions.
 Incomplete boundaries are those boundaries which consist of some gaps between them
and are not covered in all dimensions.
 The following figure represents some incomplete boundaries.
27
Software Testing Methodologies Unit II

E
 The Boundaries A and E have gaps so they are incomplete & the boundaries B, C, D
are complete.
 The main advantage of a complete boundary is that it requires only one set of tests to
verify the boundary
(4) Systematic Boundaries
 Systematic boundaries refer to boundary inequalities with simple mathematical
functions such as a constant.
 Consider the following relations,
f1(X) >= k1 or f1(X) >= g(1,c)
f2(X) >= k2 f2(X) >= g(2,c)
................ ................
fi(X) >= ki fi(X) >= g(i,c)
 Where fi is an arbitrary linear function, X is the input vector, ki and c are constants,
and g(i,c) is a decent function that yields a constant, such as k + ic.
(5) Orthogonal Boundaries
 The U and V boundary sets in Nice two-dimensional domains figure are orthogonal; that
is, the every boundary V is perpendicular to every other boundary U.
 If two boundary sets are orthogonal, then they can be tested independently.
 If we want to tilt the above orthogonal boundary we can do it by testing its intersection
points but this can change the linear growth, O(n) into the quadratic growth O(n2).
 If we tilt the boundaries to get the following figure then we must test the intersections.

(6) Closure Consistency

 Consistent closures are the most simple and fundamental closure.
 It gives consistent and systematic results.
 The following figure shows the boundary closures are consistent.
28
Software Testing Methodologies Unit II
y = k 1 + bx

y = k 2 + bx

y = k 3 + bx

x =A1 x =A 2 x = A3 x = A4 x = A5
 In the above figure, the shading lines show one boundary and thick lines show other
boundary.
 It shows Non orthogonal domain boundaries, which mean that every inequality in
domain x is not perpendicular to every inequality in domain y.
(7) Convex
 A figure is said to be convex when for any two boundaries, with two points placed on
them are combined by using a single line then all the points on that line are within the
range of the same figure.
 Nice domains support convex property, where as dirty domains don’t.
(8) Simply Connected
 Nice domains are usually simply connected because they are available at one place as
a whole but not dispersed in other domains..
 Simple connectivity is a weaker requirement than convexity; if a domain is convex it is
simply connected, but not vice versa.
(iv) Ugly Domains:
(a) General
 Some domains are born ugly. Some domains are bad specifications.
 So every simplification of ugly domains by programmers can be either good or bad.
 If the ugliness results from bad specifications and the programmer’s simplification is
harmless, then the programmer has made ugly good.
 But if the domain’s complexity is essential such simplifications gives bugs.
(b) Nonlinear Boundaries
 Non linear boundaries are rare in ordinary programming, because there is no
information on how programmers correct such boundaries.
 So if a domain boundary is non linear, then programmers make it linear.
(c) Ambiguities and Contradictions:.

(a) Ambiguities

(c) Overlapped Domains

Hole B

(d) Contradiction:
Dual Closure (b) Ambiguity:
Missing Boundary

29
Software Testing Methodologies Unit II
 Domain ambiguity is missing or incomplete domain boundary.
 In the above figure Domain ambiguities are holes in the A domain and missing
boundary in the B domain.
 An ambiguity for one variable can be see easy.
 An ambiguity for two variables can be difficult to spot.
 An ambiguity for three or more variables impossible to spot. Hence tools are required.
 Overlapping domains and overlapping domain closure is called contradiction.
 There are two types of contradictions are possible here.
(1) Overlapped domain specifications
(2) Overlapped closure specifications.
 In the above figure there is overlapped domain and there is dual closure contradiction.
This is actually a special kind of overlap.
(d) Simplifying the Topology
 Connecting disconnected boundary segments and extending boundaries is called
simplifying the topology
 There are three generic cases of simplifying the topology.

(a) Making it convex

(b) Filling in the Holes

(c) Joining the Pieces

 Programmers introduce bugs and testers misdesign test cases by, smoothing out
concavities, filling in holes, joining disconnected pieces.
(e) Rectifying Boundary Closures
 Different boundaries in different directions can obtain in consistent direction is called
rectifying boundary closures.
 That is domain boundaries which are different directions can obtain in one direction.

(a) Consistent Direction

30
Software Testing Methodologies Unit II

(b) Inclusion/Exclusion Consistency

 In the above figure the hyper plane boundary is outside that can obtain inside. This is
called inclusion / exclusion consistency.
(3) Domain Testing:
(i) Overview:
 Domains are defined by their boundaries. So domain testing concentrates test points on
boundaries or near boundaries.
 Find what wrong with boundaries, and then define a test strategy.
 Because every boundary uses at least two different domains, test points used to check one
domain can also be used to check adjacent domains.
 Run the tests, and determine if any boundaries are faulty.
 Run enough tests to verify every boundary of every domain.
(ii) Domain Bugs and How to Test for Them:
(a) General:
EXTREME POINT

BOUNDARY POINT

INTERIOR POINT

EPSILON NEIGHBORHOOD
 An interior point is a point in a domain. It can be defined as a point which specifies
certain distance covered by some other points in the same domain.
 This distance is known as epsilon neighborhood.
 A boundary point is on the boundary that is a point with in a specific epsilon
neighborhood.
 An extreme point is a point that does not lie between any other two points.

 An on point is a point on the boundary. An off point is outside the boundary.

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

31
Software Testing Methodologies Unit II
 If the domain boundary is open, an off point is a point near the boundary but in the
same domain.
 Here we have to remember CLOSED OFF OUTSIDE, OPEN OFF INSIDE
 i.e. COOOOI
 The following figure shows a generic domain ways.

EXTRA BOUNDARY
SHIFTED BOUNDARIES

TILTED BOUNDARIES MISSING BOUNDARY

CORRECT
INCORRECT
OPEN / CLOSE ERROR

(b) Testing One-Dimensional Domains:

 The following figure shows one dimensional domain bugs for open boundaries.
B A

a) An Open Domain (A)

X
B A

b) Closure bug

X
B A

c) Boundary shifted left

X
B A

c) Boundary shifted right

X
B

e) Missing Boundary

X X
B A C

f) Extra Boundary

32
Software Testing Methodologies Unit II
 In the above figure a) we assume that the boundary was to open for A.
 In figure b) one test point (marked X) on the boundary detects the bug.
 In figure c) a boundary shifts to left.
 In figure d) a boundary shifts to right.
 In figure e) there is a missing boundary. In figure f) there is an extra boundary.
 The following figure shows one dimensional domain bugs for closed boundaries.

a) A closed Domain (A)

X

b) Closure bug

c) Boundary shifted left

c) Boundary shifted right

e) Missing Boundary

f) Extra Boundary

 In the above figure a) we assume that the boundary was to close for A.
 In figure b) one test point (marked X) on the boundary detects the bug.
 In figure c) a boundary shifts to left. In figure d) a boundary shifts to right.
 In figure e) there is a missing boundary. In figure f) there is an extra boundary.
 Only one difference from this diagram to previous diagram is here we have closed
boundaries.
(c) Testing Two-Dimensional Domains:
 The following figure shows domain boundary bugs for two dimensional domains.
 A and B are adjacent domains, and the boundary is closed with respect to A and the
boundary is opened with respect to B.
(i) Closure Bug:
 The figure (a) shows a wrong closure, that is caused by using a wrong operator for
example, x>=k was used when x > k was intended.
 The two on points detect this bug.
(ii) Shifted Boundary:
 In figure (b) the bug is shifted up, which converts part of domain B into A’.
 This is caused by incorrect constant in a predicate for example x + y >= 17 was used
when x + y > = 7 was intended. Similarly figure (c) shows a shift down.
33
Software Testing Methodologies Unit II

X A X
(a) Closure Bug

X A X
(b) Shifted Up

(c) Shifted Down

A'
X

X A X
B'

(d) Tilted Boundary

A'
X

X A X

B'
(e) Extra Boundary

(f) Missing Boundary

34
Software Testing Methodologies Unit II
(iii) Tilted boundary:
 A tilted boundary occurs, when coefficients in the boundary inequality are wrong.
 For example we used 3x + 7y > 17 when 7x + 3y > 17 is needed.
 Figure (d) shows a tilted boundary which creates domain segments A’ and B’.
(iv) Extra Boundary:
 An extra boundary is created by an extra predicate.
 Figure (e) shows an extra boundary. The extra boundary is caught by two on points.
(v) Missing Boundary:
 A missing boundary is created by leaving out the predicate.
 A missing boundary shown in figure (f) is caught by two on points.
 The following figure summarizes domain testing for two dimensional domains.

 There are two on points (closed circles) for each segment and one off point (open circle)
 Note that the selected test points are shared with adjacent domains.
 The on points for two adjacent boundary segments can also be shared.
 The shared on points is given below.

(d) Equality and Inequality Predicates:

 Equality predicates are defined by equality equation such as x + y =12.
 Equality predicates supports only few domain boundaries

 Inequality predicates are defined by inequality equation such as x + y > 12 or x + y <12

 Inequality predicates supports most of the domain boundaries.
 In domain testing, equality predicate of one dimension is a line.
 Similarly equality of two dimensions is a two dimensional domain and equality of three
dimensions is a planer domain.
35
Software Testing Methodologies Unit II
 Inequality predicates test points are obtained by taking adjacent domains into
consideration.
 In the above figure the three domains A, B, C are planer. The domain C is a line.
 Here domain testing is done by two on points & two off points.
 That is test point b for B, and test point a for A and test points c and c’ for C.
(e) Random Testing:
 Random testing is a form of functional testing that is useful when the time needed to
write and run directed tests are too long.
 One of the big issues of random testing is to know when a test fails.
 When doing random testing we must ensure that they cover the specification.
 The random testing is less efficient than direct testing. But we need random test
generators.
(f) Testing n-Dimensional Domains:
 If domains defined over n-dimensional input space with p-boundary segments then the
domain testing gives testing n-dimensional domains.
(iii) Procedure:
 Generally domain testing can be done by hand for two dimensions.
 Without tools the strategy is practically impossible for more than two variables.
1. Identify the input variables.
2. Identify variables which appear in domain predicates.
3. Interpret all domain predicates in terms of input variables.
4. For p binary predicates there are 2p domains.
5. Solve the inequalities to find all the extreme points of each domain.
6. Use the extreme points to solve for near by on points.
(iv) Variations, Tools, Effectiveness:
 Variations can vary the number of on and off points or the extreme points.
 The basic domain testing strategy discussed here is called the N X 1 strategy, because it
uses N on points and one off point.
 In cost effectiveness of domain testing they use partition analysis, which includes domain
testing, computation verification and both structural and functional information.
 Some specification tools are used in domain testing.
(4) Domains and Interface Testing:
(i) General:
 The domain testing plays a very important role in integration testing. In integration testing
we can find the interfaces of different components.
 We can determine whether the components are accurate or not.
(ii) Domains and Range:
 Domains are the input values used. Range is just opposite of domains.
 i.e. Range is output obtained.
 In most testing techniques, more forces on the input values.
 This is because with the help of input values it will be easy to identify the output.
 But interface testing gives more forces on the output values.
 An interface test consists of exploring the correctness of the following mappings.

Caller domain Caller range

Caller range Called domain
Called domain Called range
36
Software Testing Methodologies Unit II
(iii) Closure Compatibility:
 Assume that the caller’s range and the called domain spans the same numbers say 0 to 17
 The closure compatibility shows the four cases in which the caller’s range closure and the
called’s domain closure can agree.
 The four cases consists of domains that are closed on top (17) & bottom (0), open top &
closed bottom, closed top & open bottom and open top & bottom.
 Here the thick line represents closed and thin line represents open.
caller called open tops open bottoms both bottom
17

0
both closed
 The following figure shows the twelve different ways the caller and the called can disagree
about closure. Not all of them are necessarily bugs.
17

 Here the four cases in which a caller boundary is open and the called is closed are not
buggy.
(iv) Span Compatibility:
 The following figure shows three possibly harmless of span incompatibilities.
 In this figure Caller span is smaller than Called.
9 9 9 9
7 7

3 3
1 1 1 1
 The range of a caller is a sub set of the called domain. That is not necessarily a bug.
 The following figure shows Called is Smaller than Caller.
37
Software Testing Methodologies Unit II
9 9 9 9
7 7

3 3
1 1 1 1
(v) Interface Range/ Domain Compatibility Testing:
 The application of domain testing is also very important for interface testing because it tests
the range and domain compatibilities among caller and called routines.
 It is the responsibility of the caller to provide the valid inputs to the called routine.
 After getting the valid input, the test will be done on every input variable.
(vi) Finding the values:
 Start with the called routine’s domains and generate test points.
 A good component test should have included all the interesting domain-testing cases.
 Those test cases are the values for which we must find the input values of the caller.
(5) Domains and Testability:
(i) General:
 Domain testing gives orthogonal domain boundaries, consistent closure, independent
boundaries, linear boundaries, and other characteristics. We know that which makes
domain testing difficult. That is it consists of applying algebra to the problem.
(ii) Linearizing Transformations:
 This is used to transfer non linear boundaries to equivalent linear boundaries.
 The different methods used here are
(i) Polynomials:
 A boundary is specified by a polynomial or multinomial in several variables.
 For a polynomial each term can be replaced by a new variable.
 i.e. x, x2, x3, …can be replaced by y1 = x, y2 = x2, y3 = x3 , …
 For multinomials you add more new variables for terms such as xy, x2y, xy2, …
 So polynomial plays an important role in linear transformations.
(ii) Logarithmic Transforms:
 Products such as xyz can be linearized by substituting u = log (x), v = log (y), log (z).
 The original predicate xyz > 17 now becomes u + v + w > 2.83.
(iii) More general forms:
 Apart from logarithmic transform & polynomials there are general linearizable forms
such as x / (a + b) and axb. We can also linearize by using Taylor series.
(iii) Coordinate Transformations:
 The main purpose of coordinate transformation technique is to convert Parallel boundary
inequalities into non parallel boundary inequalities and Non-parallel boundary inequalities
into orthogonal boundary inequalities.
(iv) A Canonical Program Form:
 Testing is clearly divided into testing the predicate and coordinate transformations.
 i.e. testing the individual case selections, testing the control flow and then testing the case
processing..
(v) Great Insights:
 Sometimes programmers have great insights into programming problems that result in
much simpler programs than one might have expected.

38
 Unit III

PATHS, PATH PRODUCTS AND REGULAR EXPRESSIONS

(1) Path products & path expression:
(1) Explain Paths, Path products, Path expressions, path sums and loops?
(a) Paths:
 A sequence of statements which starts at an entry and ends at an exit and passes all the
decisions, junctions & processes is known as path.
 A path represents different links and we can give a simplest weight to a link is a name.
 Using link names, we can convert the graphical flowgraph into an equivalent algebraic
expression.
 The link name will be denoted by lower case italic letters.
 In traversing a path, we traverse link names that give the name of the path.
 If you traverse links a, b, c, d then the name for that path is abcd.
 This path name is also called a path product. The following are some examples of paths.
a c

b d
The different paths are: eacf, eadf, ebcf, ebdf

a b c d e
The different paths are: abcde, abgjfbcde, abcdimfbcde

The different paths are: ac, abc, abbc, abbbc, abbbbc

The different paths are: abd, abcbd, abcbcbd, abcbcbcbd

(b) Path Products:
 The concatenation of names of two consecutive path segments is called a path product.
 For example if X and Y are defined as X = abcde and Y = fghij then
XY = abcdefghij YX = fghijabcde
aX = aabcde Xa = abcdea XaX = abcdeaabcde .
 Another example is if X = abc + def + ghi and Y = uvw + z then
XY = abcuvw + defuvw + ghiuvw + abcz + defz + ghiz
If X = abcde then X1 = abcde
X2 = (abcde)2 = abcdeabcde
…
 The path product is not commutative that is XY does not necessarily equal to YX.
1
 Unit III
 The path product is associative that is (XY)Z = X(YZ).
(c) Path expression:
 Path expression is defined as an expression which represents set of all possible paths
between an entry and exit nodes. For example:
u

 The path expression to the above figure is: f (x + y + d) g (u + v + w + h + i + j) k

(d) Path sums:
 The path sum is the sum of all the parallel links between two nodes or sum of all parallel
paths between two nodes. Path sum is denoted by ‘+’.
 Ex (i)
a c

b d
 In the above figure, links a & b are parallel, so these parallel paths are denoted by a + b.
 Similarly c and d are parallel & these parallel paths are denoted by c + d.
 The set of parallel paths between 1 and 2 nodes are eacf + eadf + ebcf + ebdf.
 Ex (ii)
u

 The first set of parallel path is denoted by X + Y + d and second 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
 Path sum is commutative and associative. Commutative is X + Y = Y + X
Associative is (X+Y)+Z=X+(Y+Z)
(e) Loops:
 If a single link or path expression is traversed indefinite no of times leading to infinite no of
parallel paths then it is called a loop. For example the loop consists of a single link b, then
the set of all paths through that loop is b0 + b1 + b2 + ….bn
b0

 This infinite sum is denoted by b*. So b*= b0 + b1 + b2 + ….bn.

 If the loop is taken at least once then it is denoted by b+.

2
 Unit III
 Ex (i)

The path expression is: ab*c = a(b0)c + a(b1)c + a(b2)c + a(b3)c+…….

= ac + abc + a bbc + a bbbc + ……
Ex (ii)

The path expression is: a(bc)*bd = a(bc)bd + a(bc)bd + a(bc)bd + …….

=abd + abcbd + abcbcbd + …
(2) Discuss all the rules in path representation of graphs?
Rule 1:
A(BC)=(AB)C=ABC
Rule 2:
X+Y=Y+X
Rule 3:
(X + Y) + Z = X + (Y + Z) = X + Y + Z
A(BC)=(AB)C=ABC
Rule 4:
 Distributive laws are A(B+C) = AB + AC
(B + C) D = BD + CD.
 For example:

e(a+b)(c+d)f = e(ac+ad+bc+bd)f = eacf + eadf + ebcf + ebdf

Rule 5:
 The absorption rule is, if X and Y denote the same set paths, then the union of these sets is
not changed. Ex: X + X = X.
 Another example is: if X = a + aa + abc + abcd + def then
X + a = X + aa = X + abc = X + abcd = X + def = X
Rule 6:
Xn + Xm = Xn if n is bigger than m
= Xm if m is bigger than n
Rule 7:
XnXm = Xn+m
Rule 8:
XnX* = X*Xn = X*
Rule 9:
XnX+ = X+Xn = X+
Rule 10:
X*X+ = X+X* = X+
Identity elements:(Rule 11 to Rule 17)
 a0, X0 denote the path whose length is zero. The rules are
Rule 11:
1+1=1

3
 Unit III
Rule 12:
1X = X1 = X
Rule 13:
1n = 1n = 1* = 1+ = 1
Rule 14:
1+ + 1 = 1* = 1
Rule 15:
X+0=0+X=X
Rule 16:
X0 = 0X = 0
Rule 17:
0* = 1 + 01 + 02 + . . . = 1
(2) A Reduction Procedure:
(1) Write the steps involved in Node Reduction Procedure. Illustrate all the steps with
the help of neat labeled diagrams?
Node Reduction Procedure:
 The main aim of Node Reduction Procedure is to remove all the intermediate nodes
between entry and exit nodes. This procedure is helpful in debugging process. i.e. Instead
of gathering information about path expression of all the intermediate nodes for debugging;
it is easy to debug only the path expression between entry and exit nodes.
Procedure:
1. Combine all serial links by multiplying their path expressions.
2. Combine all parallel links by adding their path expressions.
3. Remove all self loops by replacing them with a link of the form x*, where x is the path
expression of the link in that loop.
4. Choose the node which is to be removed other than initial and final node. The path
expression of the inlink and outlink of this node is multiplied and a direct link is applied with
the product of path expression. This step-4 is called Cross-Term Step.
5. Combine any remaining serial links by multiplying their path expressions.
6. Combine all parallel links by adding their path expressions. This Step-6 is called Parallel
Term Step.
7. Remove all self-loops as in step 3. This Step-7 is called Loop Term Step.
8. If the graph consists of a single link between the entry and the exit node, then the path
expression for that link is a required path expression. Otherwise return to step 4.
Example:
 Consider the following graph.

 First remove node 8 by applying step 4 (cross-term step) and combine by step 5.

4
 Unit III
 Remove node 7 by applying step 4 (cross-term step) and combine by step 5.

 Remove node 6 by applying step 4 (cross-term step) and combine by step 5.

 Add parallel links between node 5 and node 2 by applying parallel term step.

 Remove node 5 by applying step 4 (cross-term step) and combine by step 5.

 Remove self loop at node 4 by applying loop term step.

 Remove node 4by applying step 4 (cross-term step) and combine by step 5.
b[cgjf]*cgjie

a b[cgjf]*c(d + gh)
1 3 2
 Remove self loop at node 3 by applying loop term step.
a [b[cgjf]*cgjie]*b[cgjf]*c(d + gh)
1 3 2
 Remove node 3 by applying step 4.
a([b[cgjf]*cgjie]*b[cgjf]*c(d + gh))

(3) Applications:
(1) How many paths in a Flowgraph:
Q. Explain maximum path count arithmetic of a flowgraph with an example?
Maximum Path Count Arithmetic:
 Here each link is represented by a link weight. There are three arithmetic cases that are
considered here.
 They are

5
 Unit III
 (i) Parallel rule:
 Each term of the path expression A is added with each term of the path expression B if
there are two path expressions A and B. So it is A+B. If there are W A paths in A and W B
paths in B then there are W A + W B paths in its combination.
(ii) Series rule:
 Each term of the path expression A is multiplied with each term of the path expression B
if there are two path expressions A and B. So it is AB. If there are W A paths in A and W B
paths in B then there are W A W B paths in its combination.
(iii) Loop rule:
 Loop rule is evaluated by considering number of times that the path is iterated.

CASE PATH WEIGHT

EXPRESSION EXPRESSION
PARALLEL A+B W A + WB
SERIES AB WAWB
LOOP An n
∑ WA i
i=0
Example:
 Determine the path expression to the following figure.

 The path expression is given by

a(b +c) d [e(fi)*fgj(m + l)k]*e(fi)*fgh
 Let each link represents a single link and is given by a link weight 1.
 Assume that the outer loop will be taken exactly four times and the inner loop can be taken
zero to three times.
 The reduction is as follows.
1

 Now apply parallel rule.

1+1=2

 Now apply series rule.

6
 Unit III
1x2x1=2

 Now create inner self loop & Apply loop rule for removing inner self loop.
2 2
{4-4} {4-4}
1(1)=1
{0-3}
2 1 1x1=1 1 2 1 10+11+12+13=4 1 1

 Now apply series rule.

2

 Now create outer self loop.

2(4)=8

 Apply loop rule to remove the self loop.

2 84 4

 Apply series rule.

2 x 84 x 4 32768

 Alternatively we can calculate the maximum number of paths as follows.

 The path expression is given by
a(b +c) d [e(fi)*fgj(m + l)k]*e(fi)*fgh
 In the above expression each link is substituted by 1.
1(1+1)1[1(1x1)3 1x1x1 (1+1)1]4 1(1x1)3 1x1x1
=1(2)[13 x 2]4 1x13
=2[4x2]4 x 4 [since 13 = 10 +11 + 12 + 13 =4]
=2 x [8]4 x 4 = 32,768..
(2) Approximate Minimum number of paths:
Q. Define structured code. Explain about lower path count arithmetic?
Structured code:
 A structured flowgraph is one that can be reduced to a single link by successive application
of transformations.
 Based on the path expression obtained by node-by-node reduction procedure we can
determine whether the given flow graph is a structured or unstructured.
 That is if the resultant expression is large and ugly then the graph is unstructured one
otherwise the graph is structured one.
Lower path count arithmetic:
 The lowest number of paths in a structured flowgraph can be approximately known; it may
or may not be accurate because there is every possibility of a path being unachievable
which further lowers the number count.
 Here each link is represented by a link weight. Loops are always problematic.

7
 Unit III
 So it must be traversed only one time or zero times to achieve the coverage. There are
three arithmetic cases here. They are.
 (i) Parallel rule:
 Each term of the path expression A is added with each term of the path expression B if
there are two path expressions A and B. So it is A+B. If there are W A paths in A and W B
paths in B then there are W A + W B paths in its combination.
(ii) Series rule:
 Each term of the path expression A is multiplied with each term of the path expression B
if there are two path expressions A and B. So it is AB.
 If there are W A paths in A and W B paths in B then there are MAX (W A, W B) paths in its
combination.
(iii) Loop rule:
 Loop rule is taken either by considering only one time that the path is iterated or zero
times the path is iterated. So it gives the value 1 or its link weight.
CASE PATH WEIGHT
EXPRESSION EXPRESSION
PARALLEL A+B W A + WB
SERIES AB MAX(W A,W B)
LOOP An 1,W 1
Example:
 Determine the path expression to the following figure.
m

 The path expression is given by a(b +c) d [e(fi)*fgj(m + l)k]*e(fi)*fgh

 Let each link represents by a link weight 1. Assume that the outer loop will be taken exactly
four times and the inner loop can be taken zero to three times. The reduction is as follows.

 Now apply parallel rule.

 Now apply series rule.

8
 Unit III

 Now create inner self loop & apply loop rule for removing inner self loop.

 Now apply series rule.

 Now create outer self loop.

2(1)=2

 Apply loop rule to remove self loop.

2 2 1

 Apply series rule.

2
 Alternatively we can calculate the minimum number of paths as follows.
 The path expression is given bya(b +c) d [e(fi)*fgj(m + l)k]*e(fi)*fgh
 In the above expression each link is substituted by 1.
1(1+1)1[1(1x1)0 1x1x1 (1+1)1]0 1(1x1)0 1x1x1
=1(2)[10 x 2]0 1x10 =2x1 = 2
(3) The probability of getting there:
Q. What is the probability of path expressions? Write arithmetic rules. Explain with an
example.
Probability of path expressions:
 Specify each out link of a node equal to the probability of that link. The sum of the out link
probabilities is equal to 1. For a simple loop, if the loop is taken N times then the looping
probability is N/(N+1) and non looping probability is 1/(N+1).
 There are three arithmetic cases here. They are
Parallel rule:
 Each term of the path expression A is added with each term of the path expression B if
there are two path expressions A and B. So it is A+B.
 If there is a path expression A with Probability PA and path expression B with Probability
PB then the resultant probability is PA + PB.
Series rule:
 Each term of the path expression A is multiplied with each term of the path expression B
if there are two path expressions A and B. So it is AB. If there is a path expression A
with Probability PA and path expression B with Probability PB then the resultant
probability is PA PB
Loop rule:
 If the probability of looping node is PL and the probability of link leaving the loop node is
PA then PA + PL=1. So PA = 1- PL

9
 Unit III

CASE PATH WEIGHT

EXPRESSION EXPRESSION
PARALLEL A+B PA + PB
SERIES AB PAPB
LOOP An PA/(1-PL)
Example (i)

PA
PA = 1 - PL
New Probability PNEW = PA / (1-PL) = (1-PL) / (1-PL) = 1

Example (ii)
PA
PL 1-PL
PB
PA
1-PL
PB
PC PC
1-PL
Here PL + PA + PB + PC =1
1 - PL = PA + PB + PC
PA / (1 - PL) + PB / (1 - PL) + PC / (1 - PL) = (PA + PB + PC) / (1 - PL)
= (PA + PB + PC) / (PA + PB + PC) = 1
Example:
 Consider the following flowgraph.

 Calculate the probabilities of cases A, B, C.

10
 Unit III

First consider case A:

.8
.2
A
.01 .99
.1 .2
.3
.05
 In the above flowgraph if the link weight is not specified then it is specified by 1 and also
represents its nodes as follows.

 The above flowgraph is also taken by

 Remove self loop by applying loop rule

 Remove node 9 by applying series rule

 Remove node 8 by applying series rule

.8

1 .1 1 1 1 .2
1 3 4 5 6 7 2 A
.01
.015
 Remove node 5 by applying series rule

11
 Unit III

 Add parallel links between node 3 and node 6 by applying parallel rule

 Remove node 7 by applying series rule

.8
1 .1 1 .2
1 3 4 6 2 A
.025
 Remove node 4 by applying series rule
.8
1 .1 .2
1 3 6 2 A
.025
 Add parallel links between node 3 and node 6 by applying parallel rule

A
 Remove self loop at node 6 by applying loop rule
A
 Remove node 3 and node 6 by applying loop rule
A
Consider case B:
.05 .5 .2
B
.6
.85 .4
.9
 In the above flowgraph if the link weight is not specified then it is specified by 1 and also
represents its nodes as follows.
B

 Remove node 9 by applying series rule.

1 .05 .5 1 1 .2
1 3 4 5 6 7 2 B

.85 .54 .36

8
 Remove node 8 by applying series rule.
12
 Unit III
1 .05 .5 1 1 .2
1 3 4 5 6 7 2 B

.459 .306

 Remove node 4 and node 7 by applying series rule.

1 .025 1 .2
1 3 5 6 2 B

.459 .306

 Add parallel links between node 3 and node 5 by applying parallel rule
B

 Remove node 5 by applying series rule.

B

 Add parallel links between node 3 and node 5 by applying parallel rule
1 .79 .2
1 3 6 2 B
 Remove node 5 by applying series rule.
.158
1 2 B
Consider case C.
.05 .5
.6
.85 .4
.9 .8

.1
C
 In the above flowgraph if the link weight is not specified then it is specified by 1 and also
represents its nodes as follows.

C
 Remove node 9 by applying series rule.

C
 Remove node 10 by applying series rule.

13
 Unit III

C
 Remove node 8 by applying series rule.
C

 Remove node 7 & node 4 by applying series rule.

C

 Add parallel links between node 3 and node 5 by applying parallel rule
C

 Remove node 5 by applying series rule

1 .484 .8
1 3 6 2 C

.306
.085

 Add parallel links between node 3 and node 6 by applying parallel rule
1 .79 .8
1 3 6 2 C

.085
 Remove node 6 by applying series rule
1 .632
1 3 2 C

.085
 Add parallel links between node 3 and node 2 by applying parallel rule
1 .717
1 3 2 C
 Remove node 3 by applying series rule
C
Cross check:
 Sum of case A + case B + case C = .125 + .158 + .717 =1.
(4) The mean processing time of a routine
Q. What is the mean processing time of a routine? Write arithmetic rules. Explain with
an example.
Mean processing time of a routine:
 Here every link has two weights.

14
 Unit III
 One is the processing time for that link denoted by T, & other one is the probability of that
link denoted by P.
 There are three arithmetic cases here.
 They are
Parallel rule:
 It is the arithmetic mean of all processing time over all parallel links.
Series rule:
 It is the sum of two processing times.
Loop rule:
 It is evaluated by considering number of times the path is iterated
CASE PATH WEIGHT EXPRESSION
EXPRESSION
PARALLEL A+B TA+B = (PATA+PBTB)/(PA+PB)
PA+B = PA + PB
SERIES AB TAB =TA + TB
PAB = PA PB
TA = (TL PL)/(1-PL) + TA
LOOP A* PA = PA/(1-PL)
Example:
 The following figure is represented by, loop probabilities, and processing time for each link.
The probabilities are given in parentheses.
20 (.95)

300
14 (.05) 15
(.3) 25 12 (.3)
(.6)
10 16 10 8 5 7
(.4) (.7)
(.7) 40
 Apply parallel rule.
34
14 15
12
(.6) (.3)
10 35.5 16 10 8 5 7
(.4) (.7)
 .Apply series rule.
63

12 (.6) (.3)
61.5 10 8 5 7
(.4) (.7)
 Now create inner self loop.
63

20
(.6) (.3)
61.5 10 13 7
(.4) (.7)
 Remove the inner self loop by applying loop rule.

15
 Unit III
63
(.3)
61.5 10 30 13 7
(.7)
 Apply series rule.
63

(.3)
61.5 53 7
(.7)
 Create the outer self loop.
116
(.3)
61.5 60
(.7)
 Remove the outer self loop by applying loop rule.
61.5 49.714 60
 Apply series rule
171.214
 .
(5) Push/Pop, Get/Return
Q. What is Push/Pop, Get/Return? Write arithmetic rules. Explain with an example.
Push/Pop:
 Here PUSH operation is used to insert elements into the stack. POP operation is used to
remove elements from the stack.
 Apart from PUSH/POP other operations are GET/RETURN, OPEN/CLOSE and
START/STOP.
 There are three arithmetic cases here.
 They are
Parallel rule:
 Each term of the path expression A is added with each term of the path expression B if
there are two path expressions A and B. So it is A+B. If there are W A paths in A and W B
paths in B then there are W A + W B paths in its combination.
Series rule:
 Each term of the path expression A is multiplied with each term of the path expression B
if there are two path expressions A and B. So it is AB. If there are W A paths in A and W B
paths in B then there are W A W B paths in its combination.
Loop rule:
 It is evaluated by considering number of times the path is iterated.
CASE PATH WEIGHT
EXPRESSION EXPRESSION
PARALLEL A+B W A + WB
SERIES AB W A WB
LOOP A* W*A
 PUSH/POP operations satisfy commutative, associative, and distributive law of addition
and multiplication.
 The arithmetic tables for PUSH/POP are given by

16
 Unit III
PUSH/POP MULTIPLICATION TABLE PUSH/POP ADDITION TABLE

X H P 1 + H P 1

2
H H 1 H H H P+H H+1

P 1 P2 P P P+H P P+1

1 H P 1 1 H+1 P+1 1

 These tables are used to determine the weight of addition and multiplication operation.
 Here H represents the PUSH operation, P represents the POP operation and 1 represents
NO operation.
Example:
 Consider the following flowgraph.
P

 Path expression for the above flowgraph is.

P(P+1)1[P(HH)n1 HP1(P+H)1]n2 P(HH)n1HPH
 Simplifying by using the arithmetic tables
PUSH/POP = (P2 + P)[P(HH)n1(P+H)]n2(HH)n1
= (P2+P)[H2n1(P2+1)]n2H2n1
 Let us consider M1,M2 represents the two looping terms. i.e. M1 represents the number of
times the inner loop is considered, M2 represents the number of times the outer loop is
considered.
CASE (i)
Consider M1=0, M2 =0 (i.e. n1=0, n2=0)
PUSH/POP= (P+P2)[H0(P2+1)]0H0 = P + P2
CASE (ii)
Consider M1=0, M2 =1 (i.e. n1=0, n2=1)
PUSH/POP= (P+P2)[H0(P2+1)]1H0
= (P + P2)[1+P2] = P + P2 + P3 + P4
 For different combination of M1, M2 values the following table is obtained.

M1 0 0 0 0 1 1 1 1 2 2 2 2
M2 0 1 2 3 0 1 2 3 0 1 2 3
PUSH P + P2 P + P2 + 6 8 3 5 7 7 11 16
/POP P3 + P4 ∑ Pi ∑ Pi 1+H ∑ Hi ∑ Hi ∑ Hi H2+H3 ∑ Hi ∑ Hi ∑ Hi
1 1 0 0 0 4 6 8
Get/Return:
 The arithmetic tables for GET/RETURN are.
17
 Unit III
GET/RETURN MULTIPLICATION TABLE GET/RETURN ADDITION TABLE

X G R 1 + G R 1

G G2 1 G G G G+R G+1

R 1 R2 R R G+R R R+1

1 G R 1 1 G+1 R+1 1

 The arithmetic table for GET/RETURN is same as that of PUSH/POP.

Example:
 Consider the following flowgraph.

 Path expression for the above flowgraph is. G(G+R) G(GR)* GGR* R
 Simplifying by using the arithmetic tables
GET/RETURN = G(G+R)G3 R*R
= (G+R) G3 R* = (G4 + G3R) R* = (G4 + G2GR)R* = (G4 + G2)R*
(6) Limitations and Solutions
Q. What are the limitations and solutions of the applications?
 The main limitation to these applications is the problem of unachievable paths.
 The node-by-node reduction procedure and most graph-theory based algorithms work well
when all paths are achievable, but may provide misleading results when some paths are
unachievable.
 The solution to handling unachievable paths is to partition the graph into subgraphs so that
all paths in each of the subgraphs are achievable. But the resulting sub graphs may
overlap, because one path may be common to several different subgraphs.
 Each predicate’s truth value splits the graph into two subgraphs.
 For n predicates there may be 2n sub graphs. Here there is an algorithm for one predicate.
1. Set the value of the predicate to TRUE and strike out all FALSE links for that predicate.
2. Discard any node, other than an entry or exit node, that has no incoming links. Discard
all links that leave such nodes. If there is no exit node, the routine has a bug because there
is a predicate value that forces an endless loop or the equivalent.
3. Repeat step 2 until there are no more links or nodes to discard. The resulting graph is
the subgraph corresponding to a TRUE predicate value.
4. Change “TRUE” to “FALSE” in the above steps and repeat. The resulting graph is the
subgraph that corresponds to a FALSE predicate value.
 Only correlated predicates should be included in this analysis not all predicates that may
control the program flow.
(4) Regular expressions and flow anomaly detection:
Q. Explain about Regular expression and Flow-Anomaly detection?
(i) The Problem:
 The generic flow-anomaly detection problem is used to search for a specific sequence of
operations considering all possible paths through a routine.
 Let’s say the operations are SET and RESET, denoted by s and r respectively, and we
want to know if there is a SET followed immediately by a SET or a RESET followed
immediately by a RESET (i.e, an ss or an rr sequence).

18
 Unit III
 Flow anomaly detection is used to know if particular sequence occurred, but not to know
the total impact of the procedure.
 It is used to detect the bug sequence in the following situations.
1. A file can be opened (o), closed (c), read (r), or written (w). If the file is read or written to
after it is closed, then it is anomalous. i.e. cr and cw are anomalous. Similarly, if the file is
read before it’s been written, just after opening, we may have a bug. Therefore, or is also
anomalous.
2. The operations performed by tape transport device are read(r), write(w), rewind (d),
forward (f), skip (k) and stop (p). In a tape-transport device rewind and forward operations
cannot be performed one after the other without performing stop operation. So the following
sequences are anomalous: df, dr, dw, fd, and fr.
3. With the help of generic flow anomaly detection, it is possible to detect the data flow
bugs sequence such as dd, dk, kk, and ku.
4. A bug that occur only if two operations a and b occurred in the order aba or bab.
(ii) Huang Theorem:
 Annotate each link in the graph with the appropriate operator or the null operator 1.
 Simplify things using a + a = a and 12 = 1.
 The regular expression obtained should be simplified carefully, as null operations cannot be
combined with other operations.
 For example, 1a may not be the same thing as a alone. Huang theorem is used to simplify
the regular expression and to examine the specific operation sequence.
 Let A, B, C, be nonempty sets of character sequences whose smallest string is at least
one character long. Let T be a two-character string of characters.
 Then if T is a substring of ABnC, then T will appear in AB2C.
 As an example, let A = pp B = srr C = rp T = ss
 The theorem states that if ss is a substring of pp(srr)nrp then ss will appear in pp(srr)2rp.
 Similarly let A = p + pp + ps B = psr + ps(r + ps) C = rp T = P4
 If p4 is a substring of ABnC then p4 will appear in AB2C (p + pp + ps)[psr + ps(r + ps)]2rp
 Huang theorem is also useful in test design.
 Further Huang shows that if you substitute 1 + X2 for every expression of the form X*, the
paths that result from this substitution are sufficient to determine whether a given two-
character sequence exists or not.
 Two character string sequences are used to represent data flow anomaly. Then using
Huang’s theorem these anomalous can be detected if these loop is iterated twice.
Data Flow Testing Example:
 By assigning appropriate operators on each link the following flowgraph can be used to
detect different anomalies bugs.
r dr d

 Huang’s theorem states that the following expression is sufficient to detect any two
character sequence. d(r + 1)r[1 + (udr)2]ur(1 + d2)ru
 This makes the dd bug obvious. A kk bug cannot occur and also a dk bug cannot occur.
(drr + dr)(1 + udrudr)(urru + urd2ru)
 A better way to the above is subscript the operator with the link name.

 The regular expression is da(rb + 1c)rd(uedfrf)*uergdh*riui

19
 Unit III
 Applying Huang’s theorem:
da(rb + 1c)rd(1 + (uedfrf)2)uerg(1 + d2h)riui
(darbrd + dacrd)(uerg + uedfrfuedfrfuerg)(riuid2 hr u)
i i
(iii) Generalizations, Limitations and comments:
 Huang’s theorem can be easily generalized to cover sequences of greater length than two
characters. If A, B, and C are nonempty sets of strings of one or more characters, and if T
is a string of k characters, and if T is a substring of ABnC, where n is greater than or equal
to k, then T is a substring of ABkC.
 A sufficient test for strings of length k can be obtained by substituting Pk for every
appearance of P*
Pk = 1 + P + P2 + P3 + . . . + Pk
 In order to find the starting and ending sequence of strings in a path expression, the
mathematical approaches such as application of derivations to algebraic expression makes
it easier and time consuming than the path tracing process on a flowgraph.
 Static flow analysis methods can’t determine whether a path is achievable or is not
achievable.
 If unachievable paths exist, then the exactness and applicability of all flow analysis
methods reduces gradually. Hence achievable paths are preferred in order to overcome the
problems of unachievable paths.

20
 LOGIC BASED TESTING
(1) Motivational Overview:
(i) Programmers and Logic:
 Logic is used in programming.
 Logic in its simple form is Boolean algebra.
(ii) Hardware logic testing:
 Hardware logic test design is automated.
 Many test methods developed for hardware logic can also be adapted to software logic
testing.
(iii) Specification Systems and Languages:
 We need Specifications and requirements in test development and programming
development.
 As programming and test techniques have improved the bugs shifted to requirements and
their specifications.
 These bug range from 8% to 30% of the total.
 The trouble with specification is that they are very hard to express. So Boolean algebra is
used for all logic systems.
 Higher order logic systems are needed and used for formal specifications.
(iv) Knowledge based systems or Expert System:
 A system which is based on knowledge is known as knowledge based systems.
 The knowledge based systems is also needed in a programming construct.
 The knowledge based systems is also come from a domain such as medicine, law or civil
engineering.
 One implementation of knowledge based system 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 then processed through the rule.
 The processing is done by a program called the inference engine.
(v) Overview:
 We start with decision tables because they are extensively used in business data processing.
 Next Boolean algebra is used.
(2) Decision Tables:
(i) Definition and Notation
 A decision table is a tabular form that consists of a set of conditions and their respective
actions. The decision tables provide a useful basis for program and test design.
 It consists of four parts they are
1. Condition Stub
2. Action Stub
3. Condition entry
4. Action entry.
 The condition stub is a list of names of conditions. The action stub consists of a list of names
of actions
 Each column of the table consists of a rule.
 A rule specifies whether a condition should or should not be met.
 YES means the condition must met. NO means the condition does not be met and I means
that the condition plays no part in the rule or it is immaterial to that rule.
21
 If the condition is met and if the action entry is YES then the action will taken place, if NO the
action will not taken place.
Condition entry
RULE 1 RULE 2 RULE 3 RULE 4
CONDITION 1 YES YES NO NO
Condition
CONDITION 2 YES I NO I
Stub
CONDITION 3 NO YES NO I
CONDITION 4 NO YES NO YES
ACTION 1 YES YES NO NO
Action
Stub ACTION 2 NO NO YES NO
ACTION 3 NO NO NO YES
Action entry
 From the above table, Action 1 will take place if conditions 1 and 2 are met and if conditions
3 and 4 are not met (rule 1) or if conditions 1,3 and 4 are met (rule 2).
 Condition is another word for predicate. So replace condition with predicate.
 If a condition is met then the predicate is true. Similarly for not met is false.
 Now we can say that Action 1 will be taken if predicates 1 and 2 are true and if predicates 3
and 4 are false (rule 1) or if predicates 1,3 and 4 are true (rule 2).
 Action 2 will be taken if all the predicates are false (rule 3).
 Action 3 will be taken place if predicate 1 is false and predicate 4 is true (rule 4).
 Here we need a default rule that specifies the default action to be taken when all other rules
fail. The default rules for the above table are show below.
RULE 5 RULE 6 RULE 7 RULE 8
CONDITION 1 I NO YES YES
CONDITION 2 I YES I NO
CONDITION 3 YES I NO NO
CONDITION 4 NO NO YES I
DEFAULT YES YES YES YES
ACTION

 If the set of rules covers all the combinations of TRUE / FALSE (YES/ NO) for the predicates,
a default specification is not needed.
(ii) Decision-Table Processors
 Decision tables can be automatically translated into code and decision table represent higher
level language. The decision table’s translator checks the source decision table for
consistency and completeness and fills in any default rules.
 First it observes rule1. If the rule is satisfied, the corresponding action is executed.
 Otherwise rule 2 is tried. This process is repeated until a rule is satisfied or no rule is
satisfied.
 If the rule is satisfied then the corresponding action will take place. If the rule is not satisfied
then the default action taken place.
22
 The advantages of using decision tables are: it provides clarity, it provides relation to
specification, and it provides maintainability. The main drawback is object code inefficiency.
(iii) Decision-Tables as a basis for Test case Design:
 If a specification is implemented as a decision table, then decision tables are used for test
case design.
 Similarly, if a program’s logic is implemented as decision tables, then decision tables also
used for test case design.
 If this is so, then the consistency and completeness of the decision table is checked by the
decision table processor.
 It is not desirable to implement program as decision table because restrictions in decision
table language.
 The following are restrictions.
1. The specifications are specified.
2. The order in which the predicates are evaluated does not effect the resulting action.
3. The order in which the rules are evaluated does not effect the resulting action.
4. Once a rule is satisfied and an action is executed, no other rule need to be examined.
5. If several actions can result from satisfying a rule, the order in which the actions are
executed does not matter.
 It is clear from the above restrictions that action selected is based on the combination of
predicate truth values. Let us consider an automatic teller machine.
 The first condition is that the card should be valid.
 The second condition is the correct password should be entered.
 The third condition is that the sufficient money should be present in the account.
 Depending on the conditions, respective actions are executed.
(iv) Expansion of Immaterial Cases:
 In decision table immaterial entries are denoted by ‘I ’.
 If there are n predicates in the decision table then 2n combination of truth values should be
considered.
 The expansion is done by converting each I entry into two entries one with YES and other
with NO. Each I entry in a rule double the number of cases.
Rule 2 Rule 4
RULE RULE RULE RULE RULE RULE
2.1 2.2 4.1 4.2 4.3 4.4
CONDITION 1 YES YES NO NO NO NO
CONDITION 2 YES NO YES YES NO NO
CONDITION 3 YES YES NO YES YES NO
CONDITION 4 YES YES YES YES YES YES

 In the previous table rule 2 contains one I entry and therefore it expands into two equivalent
sub rules.
 Rule 4 contains two I entries and therefore it expands into four equivalent sub rules.
 The expansion of rules 2 and 4 are shown in the above table.
 The following table is an example of an inconsistent specification in which the expansion of
two rules gives a contradiction.
 Here rules 1 and 2 are contradictory, because two column entries 1.2 & 2.3 are same.
 Therefore action 1 or action 2 is taken depending on which rule is evaluated first

23
 RULE RULE RULE RULE RULE RULE
1 2 1.1 1.2 2.3 2.4
CONDITION 1 YES YES CONDITION 1 YES YES YES YES
CONDITION 2 I NO CONDITION 2 YES NO NO NO
CONDITION 3 YES I CONDITION 3 YES YES YES NO
CONDITION 4 NO NO CONDITION 4 NO NO NO NO
ACTION 1 YES NO ACTION 1 YES YES NO NO
ACTION 2 NO YES ACTION 2 NO NO YES YES

(v) Test case Design:

 Test case design by decision tables starts with examining the specification’s consistency and
completeness.
 This is done by expanding all immaterial cases and checking the expanded tables.
 Once the specification is verified next to show the correct action.
 The following rules are followed while designing test cases.
1. If there are k rules over n-binary predicates, there are atleast k cases and at most 2n cases
2. The order in which the conditions are evaluated cannot be altered. But if the order is to be
altered then the test cases are increased.
3. The order in which the rules are evaluated cannot be altered. But if the order is to be altered
then the rules are interchanged pair wise and tested.
4. Identify the places where the rules are invoked.
5. Identify the places where the actions are initiated.
(vi) Design Tables and Structure:
 The main purpose of a decision table is to check the structure of a program.
 It can be represented in the form of a decision tree.
 The following figure shows a program segment that consists of a decision tree.

24
 The decision table corresponding to the above figure is.
RULE 1 RULE 2 RULE 3 RULE 4 RULE 5 RULE 6
CONDITION A YES YES YES NO NO NO
CONDITION B YES NO YES I I I
CONDITION C I I I YES NO NO
CONDITION D YES I NO I YES NO
ACTION 1 YES YES NO NO NO NO
ACTION 2 NO NO YES YES YES NO
ACTION 3 NO NO NO NO NO YES

 If the decision appears on a path put YES or NO.

 If the decision does not appear on the path, put I.
 Rule 1 does not contain decision C, therefore its entries are YES, YES, I, YES.
 Expanding the immaterial cases for the above table is shown in the following table.
RULE 1 RULE 2 RULE 3 RULE 4 RULE 5 RULE 6
CONDITION A YY YYYY YY NNNN NN NN
CONDITION B YY NNNN YY YYNN YN NY
CONDITION C YN NNYY NY YYYY NN NN
CONDITION D YY YNNY NN NYYN YY NN

 Sixteen cases are represented in the previous table and no cases appear twice.
 Therefore the flowgraph appears to be complete and consistent.
 Count the number of Y’s and N’s in each row. They should be equal.
 Consider the following flowgraph.

25
 1. If condition A is met, do process A1. If condition B is met, do process A2
2. If condition C is met, do process A3
3. If none of the condition is met, do process A1, A2, and A3.
4. When more than one process is done, process A1 must be done first, then A2 and then A3.
 The following table shows the conversion of this flowgraph into a decision table.

A B C ABC ABC ABC ABC ABC ABC ABC

CONDITION A NO NO NO NO YES YES YES YES
CONDITION B NO NO YES YES YES YES NO NO
CONDITION C NO YES YES NO NO YES YES NO
ACTION 1 YES NO NO NO YES YES YES YES
ACTION 2 YES NO YES YES YES YES NO NO
ACTION 3 YES YES YES NO NO YES YES NO
(3) Path Expressions:
(1) General:
(i) Model:
 Logic based testing is a structural testing when it is applied to structure and it is functional
testing when it is applied to a specification.
 In logic based testing we focus on the truth values of control flow predicates.
(ii) Predicates and Relational Operators:
 Predicate is defined as a process which gives truth value as its output.
 Predicates are based on relational operators such as >, >=, =, < , <=
 The other relational operators are is a member of, is a subset of, is a substring of, is a sub
graph of etc.
(iii) Case statements and Multivalued Logics :
 Predicates are not restricted to binary truth values (TRUE/ FALSE).
 There are multiway predicates, or multivalued logic.
 Multiway predicates include FORTRAN’s 3-way, if case statements.
 Multivalued logic includes post algebra which is responsible for evaluating the structure of
predicates. These post algebra logics are very difficult to implement.
(iv) What goes wrong with predicates :
 There are many situations where something can go wrong with predicates.
1. The wrong relational operator is used. Eg. > instead of <=
2. The predicate expression of a compound predicate is incorrect. Eg. A + B instead of AB
3. The wrong operands are used. Eg A>X instead of A > Z
4. If there is a process that leads to faulty predicate.
 The first two errors can be found using logic based testing, where as last two errors can be
detected using data flow testing.
(v) Overview :
 We start by generating path expressions by path tracing. This time we convert the path
expressions into Boolean algebra, using the predicates truth values as weights.
(2) Boolean Algebra:
(i) Notation:
 There are only two numbers in Boolean algebra i.e. Zero (0) and One (1).
 One means always true and zero means always false.
26
 Label each decision with an upper case letter that represents the truth value of the predicate.
 The YES or TRUE branch is labeled with a letter and the NO or FALSE branch with the same
letter overscored.
 For example consider the following figure.

 In the above figure the straight through path which gives via nodes 3,6,7,8,10,11,12,2 has a
truth value of ABC.
 The path via nodes 3,6,7,9,2 has a value of ABC
 If two or more paths merge at a node then it is expressed by use of a plus sign (+) which
means OR.
 Using the above we can write
N6 = A + A B C
N8 = (N6) B + A B
N11 = (N8) C + (N6) B C
N12 = N11 + A B C
N2 = N12 + (N8) C + (N6) B C
(ii) The rules of Boolean Algebra:
 Boolean algebra has three operators.
 x means AND. Also called multiplication. A statement such as AB means A and B both true.
 + means OR. Also called addition. A statement such as A + B mean either A is true or B is
true or both.
 A means NOT. Also called negation or complementation.
 Ex A is true only when statement A is false.
 The Laws of Boolean algebra is shown below.
1. :A+A=A 10 A A=0

A+A=A 11. A = A
2. : A + 1 = 1 12. 0 = 1

27
3. : A + 0 = A 13. 1 = 0
4. : A + B = B + A 14. De Morgan’s Law: A + B = A B
5. : A + A = 1 15. A B = A + B
6. : A A = A 16. Distributive Law: A (B + C)= AB + AC
A A=A 17.(AB) C = A(BC)
7. : A x 1= A 18.(A + B) + C = A + ( B + C)
8. : A x 0 = 0 19. A + A B = A + B
9. : AB = BA 20. A + AB = A
 Individual letters in a Boolean algebra expression are called literals.
 The product of several literals is called a product form (eg: ABC, DE ).
(iii) Examples:
 The path expressions are simplified by applying the rules.
N6 = A + A B C
=A+BC [ since let D=B C, A + A B C = A + A D = A + D =A + B C]
N8 = (N6) B + A B = ( A + B C) B + A B
= A B + B C B + A B = ( A B + B B C) + A B
= AB + 0 C + AB = AB + A B
=( A + A ) B =1xB
=B
N11 = (N8) C +(N6) BC = BC + ( A + B C) B C
= B C + A B C +0 = C ( B + A B)
= C ( B + BA) =C(B+A)
=CB+CA = AC + BC
N12= N11 + A B C
= AC + BC + A B C = BC + A B C + AC
= C ( B + A B) + AC = C ( A + B) + AC
= CA + AC + BC = C(A + A) + BC
= C (1) + BC = C + BC
= C (1 + B) = C(1)
=C
N2= N12 + (N8) C +(N6) B C
=C+BC+(A+BC)BC
=C+BC+ABC+BCBC=C+BC+ABC+BC
= C + BC + BC(1+A) = C + BC + BC
28
 = C + C (B + B)
= C + C(1)
=C+C
=1
(iv) Paths and domains:
 Consider a loop free entry / exit path and assume all predicates are simple.
 Each predicate on the path is denoted by a capital letter either overscored or not.
 The result is a term that consists of the product of several literals. For ex: A B C.
 If a literal appears twice in a product term then one appearance can be removed and the
decision is redundant. For ex: consider C C, B B here we have to take only one C & one B
 If a literal appears both barred and un barred in a product term then the term is equal to zero
and the path is un achievable.
 A product term on an entry / exit path specifies a Domain.
 For compound predicates there is a provision of separate path for each product term.
 For example, we can implement ABC + DEF +GH as one path using a compound predicate
or as three separate paths i.e. ABC, DEF, GH and specify three separate domains.
 Let us say we have a specification such that there is one and only one product term for each
domain then represent these domains as D 1, D2, D3, ……Dm.
 Consider any of these product terms Di, Dj.
 For every i not equal to j, Di, Dj equal to zero. If not equal to zero, then there is an overlap of
the domains which is a contradictory domain specification.
 The sum of all the Di must equal to 1 else there is an ambiguity.
(v) Test case design:
 Let us consider a hierarchy of test cases for a loop that has a compound predicate.
 The routine has a single entry and single exit and has no dead end code.
 Because the predicates may be compound, the Boolean algebra expression of a domain will
be a sum of products after simplification.
 We can build a hierarchy of test strategies by considering how we test for each domain.
 Here consider
1. Simplest: Use any prime implicant in the expression. Suppose ABC + AB + DEF reduces
by AB + DEF, then AB, DEF are called prime implicant.
2. Prime implicant cover: Pick input values so that there is at least one path for each prime
implicant at the node.
3. All Terms: Test all expanded terms for that node. For example in previous figure the node
6 has five terms.
N6 = A + A B C
= AB(C + C ) + AB (C + C) + A B C
=ABC+ABC+ABC+ABC+ABC
Here there are totally five terms. Similarly for node 8 has 4 terms & node 12
has 4 terms. There is at least one path for each term.
4. Path dependence: Because in general the truth value of a predicate is obtained by
interpreting the predicate, its value may depend on the path taken there.
(3) Boolean equations:
 Loops complicate things because we may have to solve a Boolean equation to determine
what predicate value combinations lead to where. Consider the following flowgraph

29
 B

B B A A
1 4 6 2
3 5
F2
F1 A F4
B
B
7
8

B A
F3
C C C A
9 10
A

 Here the link name F1, F2, F3, F4 represents the Boolean expression corresponding to that
link.
N4 = B + F1 N7 = (N4) A + F3
= B + (N7) B C = A B + (N7) B C A
= B (1 + (N7) C) =AB
=B N2 = N6 + F4
N6 = (N4) A + B = A + B + (N7) A B C
=BA+B = A + B (1 + (N7) A B C)
=A+B =A+B
Example:
(1) Demonstrate by means of truth tables the validity of the following theorems of Boolean
Algebra.
(i) Associative laws
(ii) De Morgan’s theorems for three variables
(iii) Distributive law of + over.
(Ans) (i) Associative laws
(a) Associative law of addition
(A + B) +C = A + (B + C)
Let TRUE= T & FALSE = F then (A + B) +C & A + (B +C) is given by

A B C (A+B) (A+B)+C (B+C) A+(B+C)

T T T T T T T
T T F T T T T
T F T T T T T
T F F T T F T
F T T T T T T
F T F T T T T
F F T F T T T
F F F F F F F
30
 From the above table it shows that
(A + B) + C = A + (B + C)
(b) Associative law of multiplication
(A x B) xC = A x (B x C)
Let TRUE= T & FALSE = F then (A x B) xC & A x (B xC) is given by

A B C (AxB) (AxB)xC (BxC) Ax(BxC)

T T T T T T T
T T F T F F F
T F T F F F F
T F F F F F F
F T T F F T F
F T F F F F F
F F T F F F F
F F F F F F F
From the above table it shows that
(A x B) x C = A x (B x C)
(ii) De Morgan’s law
(a) (A + B) +C = (A B) C
Let TRUE= T & FALSE = F then (A + B) + C & A (B C) is given by

A B C (A+B) (A+B)+C (A + B) + C
T T T T T F
T T F T T F
T F T T T F
T F F T T F
F T T T T F
F T F T T F
F F T F T F
F F F F F T

A B C A B C (AxB) ( Ax B ) x C
T T T F F F F F
T T F F F T F F
T F T F T F F F
T F F F T T F F
F T T T F F F F
F T F T F T F F
F F T T T F T F
F F F T T T T T

From the above two tables it is clear that

(A + B) + C = A x (B x C)

31
 (b) (A x B) x C = (A + B) + C
Let TRUE= T & FALSE = F then (A x B) x C & A + (B + C) is given by

A B C (AxB) (AxB)xC (A x B) x C
T T T T T F
T T F T F T
T F T F F T
T F F F F T
F T T F F T
F T F F F T
F F T F F T
F F F F F T

A B C A B C (A+B) ( A+ B ) + C
T T T F F F F F
T T F F F T F T
T F T F T F T T
T F F F T T T T
F T T T F F T T
F T F T F T T T
F F T T T F T T
F F F T T T T T

From the above two tables it is clear that

(A x B) x C = A + (B + C)
(iii) Distributive law of + over
Distributive law of + over
A + (B x C) = (A + B) x (A + C)
Let TRUE= T & FALSE = F then A + (B x C) & (A + B) x (A + C) is given by

A B C (BxC) A+(BxC) (A+B) (A+C) (A+B) x (A+C)

T T T T T T T T
T T F F T T T T
T F T F T T T T
T F F F T T T T
F T T T T T T T
F T F F F T F F
F F T F F F T F
F F F F F F F F

From the above table it shows that

A + (B x C) = (A + B) x (A + C)

32
(2) Demonstrate by means of truth tables the validity of the following theorems of Boolean
Algebra.
(i) Commutative laws
(ii) Absorption law
(iii) Idempotency laws
(i) Commutative laws
(a) Commutative law of addition
A+B =B+A
Let TRUE= T & FALSE = F then A + B & B +A is given by
A B A+B B A B+A
T T T T T T
T F T F T T
F T T T F T
F F F F F F
From the above table it shows that A + B = B + A
(b) Commutative law of multiplication
AxB =BxA
Let TRUE= T & FALSE = F then A x B & B x A is given by
A B AxB B A BxA
T T T T T T
T F F F T F
F T F T F F
F F F F F F
From the above table it shows that A x B = B x A
(ii) Absorption law
Absorption law
A+AB =A+B
Let TRUE= T & FALSE = F then A + A B & A +B is given by

A A B AxB A+ AxB A+B

T F T F T T
T F F F T T
F T T T T T
F T F F F F
From the above table it shows that A + A B = A + B
(iii) Idempotency laws
Idempotency law of addition A + A = A ; A + A = A
Idempotency law of multiplication A x A = A ; A x A = A
Let TRUE= T & FALSE = F

A A A+A A A A+ A Ax A Ax A
T T T F F F T F
F F F T T T F T
T T T F F F T F
F F F T T T F T
From the above table it shows that A + A= A ; A + A = A
AxA=A; AxA=A
33
(4) KV Charts:
(i) The Problem:
 The Karnaugh-Veitch chart is known by combination of Karnaugh and Veitch with any one of
map, chart, and diagram. This chart reduces Boolean algebraic manipulations to graphical
trivia.
 Beyond six variables these diagrams get cumbersome and other techniques such as the
Quine-McCluskey method should be used.
(ii) Simple Forms:
 The following figure shows all the Boolean functions of a single variable A and their
equivalent representation as a KV chart.
A
0 1

0 The function is never true

A
0 1

A The function is true when A is true

A
0 1

A The function is true when A is false

A
0 1

1 The function is always true

 The following figure shows sixteen possible functions of two variables.

A A A A
B 0 1 B 0 1 B 0 1 B 0 1

0 1 0 1 0 0

1 1 1 1 1 1

A B AB AB AB

A B A B
34
 A
B 0 1

0 1 1

1 1

A+B A +B A+B B +A
A A A
B 0 1 B 0 1 B 0 1

0 1 0 1 0

1
1 1 1 1

A B + AB A B +A B Universal False Universal True

(iii) Three Variables:
 KV charts for three variables are shown below. A few examples are shown.
AB AB AB
C 00 01 1 1 1 0 C 00 0 1 1 1 1 0 C 00 01 1 1 1 0
0 1 0 0 1

1 1 1 1 1

ABC ABC AB
AB 1 1 1 0 AB
00 AB 00
C 01 1 1 1 0 C 01 C 00 0 1 1 1 1 0
0 0 1 1 1 0 1 1

1 1 1 1 1 1

BC BC+AB BC
AB AB AB
C 00 0 1 1 1 1 0 C 00 01 1 1 1 0 C 00 01 1 1 1 0
0 1 1 0 1 0 1 1
1
1 1 1 1 1 1 1 1 1
1

BC+AB+BC ABC + ABC + ABC + ABC B

AB AB AB
C 00 01 1 1 1 0 C 00 0 1 1 1 1 0 C 00 0 1 1 1 1 0
0 1 1 0 0 1 1 1 1

1 1 1 1 1 1 1 1 1

A C C
AB AB AB
C 00 0 1 1 1 1 0 C 00 0 1 1 1 1 0 C 00 0 1 1 1 1 0
0 1 1 0 1 1 0 1 1
1
1 1 1 1 1 1 1 1 1 1
1 1

B B+C A + BC + BC

35
(iv) Four Variables:
 The same principles hold for four or more variables
AB AB AB
CD 00 01 11 10 CD 00 01 11 10 CD 00 01 11 10

00 1 1 00 1 1 00 1 1

01 1 1 01 01 1 1

1 1 1 1
11 11 11

10 1 1 10 1 1 10 1 1

AC+AC BD BD+BD

AB AB AB
CD 00 01 11 10 CD 00 01 11 10 CD 00 01 11 10

00 1 00 1 1 00

01 1 01 1 1 01 1 1

1 1 1 1 1 1 1 1 1
11 11 11

10 1 1 10 1 1 10

ABCD+ABD+AC ABD+BD+BC BD
Examples:
(i) Using a Karnaugh map minimize
F= A B C D + A B C D + A B C D + A B C D + A B D + B C D + A B C D
Ans: The Standard SOP form is:
F(A,B,C,D)=A B C D + A B C D + A B C D + A B C D + A B D (C + C) + (A + A) B C D + A B C D
=ABCD+ABCD+ABCD+ABCD+ABCD+ABCD+ABCD
+ABCD+ABCD
A B
00 01 11 10
CD
0 4 12 8
00 1
1 5 13 9
01 1 1 1
3 7 15 10
11 1 1
2 6 14 11
10 1 1 1

The minimized function is: A B D + B D + A C D + A C D

36
(ii) Minimize the function using Karnaugh map method
F(A,B,C,D)= ∑(1,2,3,8,9,10,11,14) + ∑d (7,15)
Ans:
A B
00 01 11 10
CD 8
0 4 12
00 1
1 5 13 9
01 1 1 1
3 7 15 10
11 1 d d 1
2 6 14 11
10 1 1 1

The minimized function is: A B + A C + A B D + A B C

(iii) Reduce the following function using Karnaugh Map method
F(A,B,C,D)= π(4,5,6,7,8,12,13) + d( 1,15)
Ans:
A B
00 01 11 10
CD 8
0 4 12
00 0 0 0
1 5 13 9
01 d 0 0
3 7 15 10
11 0 d
2 6 14 11
10 0

The minimized function is: (B + D) (A + B) (A + C +D)

(5) Specifications:
(i) General:
 Using KV charts specification is validated. The procedure is given below.
1. Rewrite the specification with consistent language.
2. Identify the predicates. Name with suitable letters such as A, B, C,..
3. After predicate identification, rewrite the specification into logical or Boolean connectives
such as AND, OR, NOT.
4. This rewritten specification is then transformed into set of Boolean expressions.
5. Identify the default action if any.

37
 6. Enter the Boolean expressions in a KV chart and check for consistency. If the
specifications are consistent, there will be no overlaps.
7. Enter the default cases and check for consistency.
8. If all boxes are covered, the specification is complete.
9. If the specification is incomplete or inconsistent, translate the corresponding boxes back
and get a clarification, explanation or revision.
10. If the default cases were not specified explicitly, translate the default cases back and get
a confirmation.
(ii) Finding and translating the logic:
 The formation of specifications into sentences is given below.
 Specifications are formed into sentences by using the following IF-THEN format.
 IF represents predicate, THEN represents action.
 Hence predicates are used by applying certain Boolean connectives like AND, OR, and NOT
and represented by A1, A2, A3.
 The different phrases which can be used for the words are
IF: if, if and when, only if, only when, based on, because, but etc.
THEN: then, assign, shall, should, will, would, do etc.
AND: all, and, as well as, both, but, in conjunction with, coincidental with etc.
OR: or, either-or, and, and if..then, and/or, in addition to, otherwise etc.
NOT: but, but Not, excluding, less, neither, never, besides etc.
EXCLUSIVE OR: but, by contrast, conversely, nor etc.
IMMATERIAL: irrelevant, independent of, irregardless, irrespective, whether or not etc.
 Other than these, some other dangerous phrases also exist such as respectively, similarly
etc.
 Now we have a specification of the form
IF A AND B AND C, THEN A1
IF C AND D AND F, THEN A3
IF A AND B AND D, THEN A2
(iii) Ambiguities and Contradictions:
 The problem of ambiguity occurs, when more than one action is activated by many boxes of
KV chart or any box is empty in KV chart.
 Let us consider an ambiguous specification that is
A1 = B C D + A B C D
= (A + A) B C D + A B C D
=ABCD+ABCD+ABCD
A2= A C D + A C D + A B C + A B C
= A(B + B) C D + A( B + B) C D + A B C (D + D) + A B C(D + D)
=ABCD+ABCD+ABCD+ABCD+ABCD+ABCD
+ABCD+ABCD
= A B C D +A B C D + A B C D + A B C D
A3= B D + B C D
= (A + A) B (C + C) D + (A + A) B C D
=A B C D + A B C D + A B C D + A B C D + A B C D + A B C D

38
 ELSE = B C + A B C D
=(A + A) B C (D +D) + A B C D
=ABCD+ABCD+ABCD+ABCD+ABCD
 Here 1,2,3 represents the actions and the 4th specifies the default case.
 Now represent these specifications as follows.

A B
00 01 11 10
CD
00 4 1 1,2 2

01 3 2,3 1,2

11 4 3 3 4

10 4 3 3 4

 In this case the ambiguity occurs in the case of A B C D, this gives many inconsistent or
contradictory solutions.
 There are several boxes that call for more than one action.
 In A B C D both action 1 and action 2 shall be taken.
 For unspecified default action do the following
 Insert explicit entries in the KV chart.
 Apply negation.
 Provide an equivalent expression as a default statement.
(iv) Don’t care and Impossible terms:
 Don’t care terms (Ø) are the terms or conditions using which logic is simplified through KV
chart.
 The value of Ø can be either 0 or 1.
 Consider the following three impossible things.
1. Creation of a universal program verifier
2. Knowing both the exact position and the exact momentum of a fundamental particle.
3. Knowing what happened before that started the universe.
 Basically impossible conditions are used to simplify the logic.
 The two types of impossible conditions are
1. The condition cannot be created or improbable
2. The condition results from forcing a complex continuous one into a binary logical one.
Logic Simplification:
 The steps involved in simplifying the logic are as follows.
1. Identify all impossible and illogical cases.
2. Next avail these cases effectively
3. For this purpose KV chart is used
4. Use the symbol Ø which is to be interpreted as 0 or 1.

39
 A B
00 01 11 10
CD
00 Ø 1

01 1 Ø Ø

11 Ø 1 1 1

10 1 1 1 1

The minimized function is: C D + A B C D + C B + C A + A B D (1)

By taking impossible conditions we get C + A. (2)
The corresponding control flowgraphs for equations (1) and (2) are defined as follows.
Control flowgraph for equation (1)

A
B
C A B D
C A B D ACTION

D
ELSE
C

A B D
A B D

A D
B
ELSE ELSE
D
D

D
ELSE
Control flowgraph for equation (2)

40
 UNIT –IV
STATES, STATE GRAPHS, AND TRANSITION TESTING
(1) State Graphs:
(i) States(public question)
 State is a condition or situation during which an object undergoes throughout its life time.
 States are represented by nodes.
 States are numbered or identified by characters or words or whatever else is convenient.
 A state graph consists of a set of states in order to represent the behavior of the system.
 To understand the concept of states let us consider the following examples.
Example 1: A program that detects the character sequence ZCZC can be in the following states.
1. Neither ZCZC nor any part of it has been detected.
2. Z has been detected.
3. ZC has been detected.
4. ZCZ has been detected.
5. ZCZC has been detected.
Example 2: A moving automobile whose engine is running can have the following states with
respect to transmission.
1. Reverse gear.
2. Neutral gear.
3. First gear.
4. Second gear.
5. Third gear.
6. Four gear.
Example 3: A person’s checkbook can have the following states with respect to bank balance.
1. Equal.
2. Less than.
3. Greater than.
Example 4: A word processing program menu can be in the following states with respect to file
transmission.
1. Create document. 6. Saving document
2. Copy document. 7. Copy disc.
3. Delete document. 8. Format disc
4. Rename document. 9. Backup disc
5. Compress document. 10. Recover from backup
(ii) Inputs and Transitions:(public question)
 Some thing is modeled and given is called input. Input may be values or variables.
 A state graph takes input provided to states.
 As a result of these inputs the state changes is known as transition.
 That is changing from one state to other state is called transition.
 Transitions are denoted by links that join the states.
 The input that causes the transition is represented on the link. So the inputs are link weights.
 A finite state machine is represented by a state graph having a finite number of states and a
finite number of transitions between states.
 The ZCZC detection example can have the following types of inputs.
1. Z
2. C
3. Any character other than Z or C which will be denoted by A.
Page 1
 A

C,A Z,C,A
A
A,C
Z C Z C
NONE Z ZC ZCZ ZCZC

Z
Z
The above state graph is interpreted as follows.
1. If a system is in the NONE state, and it receives A or C then it is in NONE state only.
2. In NONE state if Z is received, the system enters into Z state. In Z state if it receives Z it will
remain in the same state. If C is received it will go to the ZC state or if any other character
say A is received then it will go back to the NONE state.
3. In ZC state if it receives Z it will enter into ZCZ state. If C or A is received it enter into NONE
state.
4. In ZCZ state if it receives Z it enter into the Z state. If A is received it enters into the NONE
state.
5. In ZCZ state if it receives C it enter into the ZCZC state. In ZCZC state if it receives Z or C or
A then it will remain in the same state only.
(iii) Outputs:
 Outputs are based on the input values.
 When an input is applied to a state it is processed in order to produce an output.
 Each input and output of the state graph is separated by a slash ‘/’ symbol.
 Outputs are also link weights. If more than one input having the same output than it can be
represented by input1, input 2, input 3…/output.
Example: Let us consider a tape control recovery system. This system contains two inputs OK &
Error. OK means “No write errors”. Error means “There may be write errors”. The outputs are
Rewrite, Erase, None, Out of service. Here None means no special action is taken.
OK/NONE
OK/NONE
EROR/
EROR/ OUT OF SERVICE
OK/NONE ERASE
1 5 6 7
OK/NONE

EROR/
REWRITE OK/NONE 3 EROR/
ERASE

OK/NONE
EROR/
REWRITE
2 4
EROR/
REWRITE
 At state 1 if no write errors are detected (input = OK) no special action is taken
(output=NONE). If error is detected (input=ERROR) backspace the tape one block and
rewrite the block (output =REWRITE) i.e. enter into state 2.

Page 2
  At state 2 if the rewrite is successful (input= OK) no action is taken (output=NONE) and
return to state 1.
 If the rewrite is not successful try another back space and rewrite (output=REWRITE) i.e.
enter into state 4.
 If there are two successive rewrites and a third error occurs then backspace ten centimeters
and erase (output=ERASE) i.e. from state 4 to state 5.
 If there are two successive rewrites and a third no error occurs then it enter into state 3 &
then state 1. At state 3 if any error is detected then it enter into state 2 and rewrite.
 At state 5 if the erasure works (input=OK) no action is taken and return to initial state.
 If it does not work, backspace another ten centimeters and erase. i.e. enter into state 6.
 At state 6 if the erasure works (input=OK) no action is taken and return to initial state
 If the second erasure does not work put the tape control out of service i.e enter into state 7
(iv) State Table:
 If state graph has a large number of states and transitions, then it is difficult to follow them.
 Therefore a state table is used, as an easiest way to represent all the states, inputs,
transitions and outputs of the state graph.
 A state table is defined as a tabular representation of a state graph.
 It consists of
1. Each row represents a state.
2. Each column represents an input condition.
3. The box at the intersection of row and column represents the next state and the output.
 The state table for the tape control system is shown below.
STATE OK ERROR
1 1/NONE 2/REWRITE
2 1/NONE 4/REWRITE
3 1/NONE 2/REWRITE
4 3/NONE 5/ERASE
5 1/NONE 6/ERASE
6 1/NONE 7/OUT
7
. (v) Time Versus Sequence:
 State graphs don’t represent time-they represent sequence.
 A transition might take microseconds or centuries.
 A system may be in one state for milliseconds or years.
 The finite state machine model can be elaborated to include notions of time in addition to
sequence, such as Petri nets.
(vi) Software Implementation( public question)
1. Implementation and Operation:
 Here four tables are involved.
1. First table encode the input value. i.e. INPUT_TABLE_CODE.
2. A table that specifies the next state i.e. TRANSITION_TABLE
3. A table that specifies the output. i.e. OUTPUT_TABLE
4. A table that stores the present state of every device. i.e. DEVICE_TABLE.
This routine operates as follows.
BEGIN
PRESENT_STATE:=DEVICE_TABLE
ACCEPT INPUT_VALUE
INPUT_CODE:=INPUT_CODE_TABLE

Page 3
 POINTER:=INPUT_CODE#PRESENT_STATE
NEW_STATE:=TRANSITION_TABLE
OUTPUT_CODE:=OUTPUT_TABLE
CALL OUTPUT_HANDLER
DEVICE_TABLE:=NEW_STATE
END
Steps:
1. The present state is fetched from memory.
2. The present input value is fetched. If it is numerical it can be used directly. If it is not
numerical encode into a numerical value.
3. The present state and input code are combined.
4. The output table contains a pointer to the routine to be executed.
5. The same pointer is used to fetch the new state value, which is then stored.
2. Input encoding and Input Alphabet:
 Only the simplest finite state machines can use the inputs directly.
 In ZCZC detector there are 256 possible ASCII characters. But we are taken Z, C and
OTHER.
 The input encoding here is for OTHER=0, for Z=1, for C=2.
 The different encoded input values are called the input alphabet.
3. Output encoding and Output Alphabet:
 A single character output for a link is rare.
 So we want to output a string of characters.
 These can be encode into a convenient output alphabet.
4. State codes and State-Symbol products:
 The term state-symbol product is used to convert the combined state and input code into a
pointer to compact table.
5. Application Comments for Designers:
 An explicit state table implementation is advantageous when either the control function is
likely to change in the future or when the system has many similar, but slightly different
control functions.
6. Application Comments for Testers(Public Question)
 Independent testers are not usually taken with either implementation details or the
economics of this approach.
 If the programmers have implemented an explicit finite state machine then much of our work
has been done for us.
 Sometimes showing the programmers the kinds of tests developed from a state graph
description can lead them to consider it as an implementation technique.
(2) Good State Graphs and Bad State Graphs: (public question)
(i) General:
 In testing we deal with a good state graph and also with a bad one.
 The following figure shows examples of improper or bad state graphs.
1 1,2

In state B the initial state can never be entered again

Page 4
 1 1,2 1

State C cannot be entered

1,2 1,2

State A,B are not reachable

1 1

No transition is specified for an input of 2 when in state B

1 2

Two transitions are specified for an input of 1 in state A

1
(2) State Bugs(public question)
 The bugs in states are called state bugs. The state bugs arise due to the following reasons.
1. Number of States:
 A State graph consists of the number of states. It represents behavior of the system.
 In practice the state is directly or indirectly recorded.
 State table is used to record the number of states of the state graph.
 In state table the state bugs are occurred because of missing states.
 That is in state table if the number of states are not recorded or missed then the result
might be the bugs.
 To find the missing states, first find the number of states
 The number of states is founded by as follows.
1. Identify all the component factors of the state.
2. Identify all the allowable values for each factor.
3. Now the number of states is the product of the factors and allowable values.
 Functional specifications are used to find the factors of the state. They may also
helpful to find the number of possible values for each factor.
2. Impossible States:
 A state that is not possible is called impossible states.
 For example a broken engine cannot run, so running a broken engine state is
impossible state.
 There are some combination of factors that are impossible, they are
GEAR: R, N, 1, 2, 3, 4 = 6 factors
DIRECTION: forward, reverse, stopped = 3 factors
ENGINE: running, stopped = 2 factors
TRANMISSION: ok, broken = 2 factors
ENGINE: ok, broken = 2 factors

Page 5
 TOTAL = 6 x 3 x 2 x 2 x2 =144 states.
 A broken engine cannot run so the combination of engine is 3 states. Therefore the
total number of states is 108. A car with a broken transmission does not move for
long, there by further decreasing the number of states.
3. Equivalent States:
 Two states A, B are equivalent if every sequence of inputs starting from one state (s)
produces exactly the same sequence of outputs.
 Let us take an example of two equivalent states.
 In the below figure, let us assume the system is in state S.
 An input of ‘a’ begins a transition to state A and an input of ‘b’ begins a transition to
state B from S.
 If all the sequence of inputs from the state A generates exactly the same sequence of
outputs as the other state B, then we say that these two states are equivalent.

 Because these two states are treated equally, the state graph can be minimized by
combining these two equivalent states as shown in the following figure.

 Equivalent states can be recognized by the following procedure.

1. The two states are differentiated only by the different input values. For example
Consider the following figure.
d/y

d/y
Here except a, b inputs, the system behavior in two states A, B are identical for every
input sequence.
Page 6
 2. There are two set of rows which except for the state name, have identical state graphs
with respect to transitions and outputs. The two sets can be merged. Let consider the
following equivalent states.
a/y

a/u
a/y
The Decision table to the above figure is shown below:
STATE OK ERROR
1 A1/u B1/u
A1 A1/y A2/x
B1 B1/y B2/x
A2 B2/w A3/u
B2 A2/w B3/u
A3 A3/u B2/y
B3 B3/u A2/y
The merged equivalent states are represented by as follows
a/y a/w a/u

b/y
The Unmergeable states are represented by as follows
a/y a/w

a/y a/w a/u

(3) Transition Bugs( public question)

 The connectivity between two or more states is known as transition.
 The bug in transition is called Transition Bug.
1. Unspecified and Contradictory Transitions:
 A transition is specified between states. If a transition may occur between states and
not specified (i.e. unspecified transition) then the transition bug occurs.
 If a transition is not possible in the state then there must be a method that prevents
the occurrence of input in that state.
Page 7
  If there is no such method available then the occurrence of input becomes inefficient.
 So to avoid transition bug one transition must be specified for every input state
combination.
 A program does not contain contradictions, if one input must be processed at a time to
produce desired output. If a transition does not possible between states and the
transition is specified then a contradictory transition may occur.
 That is if a programmer does not take all the measures of a program then
contradictory transitions may occur because of transitions may not be possible
between some of the states. For example if a single bit of a state is misplaced by the
programmer then it doubles the number of states in the state graph and performs the
contradictory transitions. This contradiction gives a transition bug.
2. Example(public question)
 The following example shows how to convert a specification into a state graph and
how contradictions can come out.(public question)
OK

Rule 1:
 The program will maintain an error counter which will be incremented whenever there is
an error. Here there are only two input values OK, ERROR.
 These values make it easier to detect ambiguities and contradictions in a state table.
INPUT
STATE OK ERROR
0 0/NONE 1/
1 2/
2 3/
3 4/
4 5/
5 6/
6 7/
7 8/
Rule 2:If there is an error rewrite the block.
INPUT
STATE OK ERROR
0 0/NONE 1/REWRITE
1 2/REWRITE
2 3/REWRITE
3 4/REWRITE
4 5/REWRITE
5 6/REWRITE
6 7/REWRITE
7 8/REWRITE
Rule 3: If there are three errors, erase 10 centimeters of tape and rewrite the block.
INPUT
STATE OK ERROR
0 0/NONE 1/REWRITE
1 2/REWRITE
2 3/REWRITE,ERASE,REWRITE
Page 8
 3 4/REWRITE,ERASE,REWRITE
4 5/REWRITE,ERASE,REWRITE
5 6/REWRITE,ERASE,REWRITE
6 7/REWRITE,ERASE,REWRITE
7 8/REWRITE,ERASE,REWRITE
Rule 4: If there are three erasures and another error occur, then put out of service.
INPUT
STATE OK ERROR
0 0/NONE 1/REWRITE
1 2/REWRITE
2 3/ERASE,REWRITE
3 4/ERASE,REWRITE
4 5/ERASE,REWRITE
5 6/OUT
6
7
Rule 5:
 If the erasure was successful return to the normal state and clear the error counter.
INPUT
STATE OK ERROR
0 0/NONE 1/REWRITE
1 2/REWRITE
2 3/ERASE,REWRITE
3 0/NONE 4/ERASE,REWRITE
4 0/NONE 5/ERASE,REWRITE
5 0/NONE 6/OUT
6
Rule 6:
 If the rewrite was unsuccessful increment the error counter, and try another rewrite.
Rule 7:
 If the rewrite was successful decrement the error counter and return to the previous state.
INPUT
STATE OK ERROR
0 0/NONE 1/REWRITE
1 0/NONE 2/REWRITE
2 1/NONE 3/ERASE,REWRITE
3 0/NONE 4/ERASE,REWRITE
2/NONE
4 0/NONE 5/ERASE,REWRITE
3/NONE
5 0/NONE 6/OUT
4/NONE
6
Rule 7 A:
 If there have been no erasures and the rewrite is successful return to the previous state.

Page 9
 3. Unreachable States:
 An un reachable state is like unreachable code If a transition is not specified between
two states then that states are unreachable. That is if any incorrect transition occurs
then the state becomes unreachable.
 There may be a transition from unreachable states to other states.
4. Dead States:
 A dead state is a state that once entered cannot be left.
 In programming, a set of states may be dead because a program has two stages.
 In the first stage an initialization process takes place that consists of number of states
to be initialized.
 In the second stage strongly connected set of functional states takes place in which
operations of the states cannot be completed. So the functional states become dead
states. The only solution to this problem is system restart.
(4) Output Errors:
 The errors in output are called output errors.
 The states, the transitions, and the inputs may be correct & there may be no dead or
unreachable states, but the output for the transition may be incorrect.
 Output actions must be verified independently for states and transitions.
(5) Encoding Bugs:(public question)
 Encoding is a process of converting or coding the inputs, transitions, and outputs of the state.
 Encoding process is applied in both explicit and implicit finite state machines.
 The encoding bugs are more common at the time of input coding, output coding and state
coding in an explicit state machine.
 The encoding bugs may also exist in an implicit finite state machine, because of different
views made by programmer and tester.
 The behavior of a finite state machine is invariant under all encodings.
 That is say that the states are numbered 1 to n.
 If you renumber the states by an arbitrary permutation, the finite state machine is unchanged.
Similarly for input and output code is unchanged.
 Therefore if you present your version of the finite state machine with a different encoding and
if the programmer objects to renaming then there is encoding bugs.
 You may have to look at the implementation for these, especially the data dictionary.
 The implementation of the fields as bunch of bits tells you the potential size of the code.
 If the number of code value is less than this potential, there is an encoding process.
 In strongly typed languages with user defined semantic types the encoding process is
probably a type conversion a set membership to integer.
 Again you may have to look at the program to spot potential bugs of this kind.
(3) State Testing:
(i) Impact of Bugs:
 Let us say that a routine is specified as a state graph that has been verified as correct in all
details.
 From the following the bugs may occur.
1. Wrong number of states
2. Wrong transition
3. Wrong output for a given transition
4. Pair of states are wrongly made equivalent
5. Set of states are split to create in equivalent duplicates.
6. Set of states become dead.
Page 10
 7. Set of states become unreachable.
(ii) Principles:( public question)
 State testing is defined as a functional testing technique to test the functional bugs in the
entire system.
 The principles for state testing are very similar to the principles of path testing.
 For path testing it is not possible to test every possible path in a flowgraph.
 Similarly for state testing it is not possible to test every possible path in a state graph.
 In a state graph a path is a sequence of transitions caused by a sequence of inputs.
 In state testing the primary interest is given to the states and transitions rather than outputs.
 In state testing define a set of covering input sequences and for each step in each input
sequence define the expected next state, the expected transition and the expected output
code.
 A set of tests consists of three sets of sequences
1. Input sequences.
2. Corresponding transitions
3. Output sequences.
(iii) Limitations and extensions:
The limitation is: State transition coverage in a state graph does not guarantee complete testing.
The extension:
 Chow defines a hierarchy of paths and methods for combining paths.
 The simplest is called a 0 switch which corresponds to test each transition independently.
 The next level consists of testing transition sequences consisting of two transitions called 1
switch. The maximum length switch is an n-1 switch where n is the number of states.
The different advantages are
 State testing is useful when the error corrections are less expensive.
 State testing is also useful when the testers want to detect a specified input.
 A state testing is specifically designed for catching the deep bugs.
 A state testing provides easiness during the design of tests.
The different disadvantages are
 State testing does not provide through testing because when a test is completed there might
be some bugs remains in the system. Testers require large number of input sequences to
catch transition errors, missing states etc..
(iv) What to model:
 Combination of hardware & software can be modeled sufficiently complicated state graph.
 The state graph is behavioral model that is it is functional rather than structural.
(v) Getting the data:
 Here labor intensive data gathering is needed and needs more meetings to resolves issues.
(vi) Tools:
 Tools for hardware logic designs are needed.
(4) Testability tips:
(i) A balm for programmers:
 The key to testability design is easy that is we can easily build explicit finite state machines.
(ii) How big How small:
 For two finite state machines there are only eight good and bad ones.
 For three finite state machines there are eighty possible good and bad one.
 Similarly for Four state machines 2700 most of which are bad and for five state machines
275000 most of which are bad. For six state machines 100 millions most of which are bad.
(iii) Switches, Flags and unachievable paths :
 The functionality of switches and flags are almost similar in the state testing.
Page 11
 Switches or flags are used as essential tool for state testing to test the finite state machine in
every possible state.
 A flag or switch value is set at the initial process of finite state machine, and then this value is
evaluated and tested.
 Depending on its value the specific path is selected to find an easiest way for testing the
finite state machine.
 Mostly the switch or flag works on true or false condition.
 In figure a flag is set to p in the program. This p variable is assigned to some value which can
be evaluated.
 Depending on its value a path is separated into branches in order to proceed testing in either
way that is u or x
 This also can be done by removing a flag and separating v path into two different paths w,y
as shown in the above figure.
 Unachievable paths those paths which don’t interact with each other.
 Here there are four paths u,w,x,y in that two are not achievable and two are achievable.
 That is u is not achievable to path y and path x is not achievable to path w & u is achievable
to path w and path x is achievable to path y.
 Finally both the paths uw and xy are needed to cover the branches.
 In the above figure there are three flag variables p,q,r in the program.
 These variables are assigned some values that can be evaluated and based on which the
paths are separated into branches.
 The main benefit of using this implementation is to remove the unnecessary combination
from the decision tree as shown in the figure c.
(iv) Essential and inessential finite state behavior:
 To understand an essential and inessential finite state behavior, we need to know the
concept of finite state machines and combinational machines.
 There is a difference between finite state machines and combinational machines in terms of
quality.
 In combinational machines a path is chosen depending on the truth values of predicates.
 The predicate truth values are the values which once determined will never change and
always remains constant.
 In these machines a path is equivalent to a Boolean algebraic expression over the predicates
 Further more it does not matter in which order the decisions are made.
(v) Design guide lines:
 Fine state machine is represented by a state graph having a finite number of states and a
finite number of transitions between states
 Finite state machine (FSM) is a functional testing tool and programming testing tool.
 That is it is an essential tool for state testing in order to identify or model the behavior of
software.
 The different guide lines are given below.
1. Initially learn the procedure of finite state machine that are used in both hardware and
software.
2. Design an abstract machine in such a way that it works properly and satisfies the user
requirements.
3. Design an explicit finite state machine.
4. Prototype test must be conducted thoroughly to determine the processing time and space
of explicit finite state machine design.
5. If time or space is more effecting the overall system, then use shortcuts to complete the
design process.
Page 12
 6. If there are more than a few numbers of states then use hierarchical design to represent
them.
7. If there is large number of states then software tools and programming languages must
be developed.
8. The capability to initialize to an arbitrary state must be inbuilt together with the transition
verification instrumentation.

UNIT -V -GRAPH MATRICES AND APPLICATIONS

(1) Motivational Overview:
(1) What are the problems with pictorial graphs?
Problems with pictorial graphs:
1. Tracing a path in a pictorial graph is difficult task.
2. There is every possibility of having an error while tracing i.e. we can miss a link or cover
some links twice.
3. Even yellow marking pen also not be reliable because once the concentration is lost during
marking; we will lose the position to be marked.
4. It is very difficult to generate test cases for a pictorial graph
5. The time is also wasted if pictorial graphs are used.
(2) What are the graph matrices and their applications?
(i) Graph Matrices:
 The matrix in which every node of a graph is represented by one row and one column is
called a graph matrix. or The matrix that represents the structure of a graph is known as
graph matrix.
 In a graph matrix each row and each column intersection represents, the relationship
between the respective row nodes and column nodes.
 A graph is an abstract representation of a software structure.
 A graph can be traced thoroughly to perform a check for covering paths, sensitizing paths,
predicate expressions etc.
 Here we use either pictorial graphs or graph matrices.
 Tracing a path in a pictorial graph is difficult task.
 There is every possibility of having an error while tracing i.e. we can miss a link or cover
some links twice. Even yellow marking pen also not be reliable because once the
concentration is lost during marking; we will lose the position to be marked.
 Graph matrices are introduced to overcome these problems.
 A graph matrix is purely based on matrix methods.
(ii) Applications:
(i) Tool Building:
 Using matrix representation and its methods we construct test tools.
 It is more difficult to generate test cases for a pictorial graph than the graph matrix.
(ii) Doing and understanding testing theory:
 Theoretically speaking, graphs are the simple structures but when used in theorem proving
we use graph matrices because pictorial graphs will omit some important algorithms.
(iii) The Basic Algorithms:
 The basic algorithms represent a basic tool kit. The basic tool kit consists of
1. Matrix multiplication is used to derive the path expression from every node to every other
node.
2. A partitioning algorithm is used for eliminating loops from graphs.
3. A collapsing process is used to get the path expression.
Page 13
 (3) Write relative merits and demerits of different Graph Matrix representations?
(i) Merits:
1. Using matrix representation and its methods we construct test tools.
2. Matrix representation gives the best results.
3. Graph matrices are used for developing algorithms and proving theorems of graphs.
4. Linked list representation is used to represent graph matrices.
(ii) Demerits:
1. Graph matrix representation for two dimensional arrays is useful only for small graphs
with simple link weights, however with large graphs; this matrix representation gives
inconvenience.
2. Matrix representation requires a large storage space.
3. An additional weight matrix is also needed.
4. Since many entries of the graph matrices are null, the time taken to process such entries
is a waste of time.
(2) The Matrix of a graph:
(1) Explain about the matrix of a graph?
(i) Basic Principles:
 A graph matrix is array representation of nodes. In a graph matrix each row and each
column intersection represents, the relationship between the respective row nodes and
column nodes.
 Some examples of graphs and their associated matrices are given by.
a a
a
[0] [a]
Figure (a) Figure (b) Figure (c) Figure (d)
3 1 2 3 4
a e c
1 2 3 a b 1 a
b a
1 2 1 d 2
1 2
2 b+c 3 b
d c
3 c c d 4 d
3 4
Figure (e) Figure (f)
1 2 3 4 5
1 a
2
3 d b
4 c f
5 g e h

Figure (f)

Page 14
 1 2 3 4 5 6 7 8
1 a i
2
3 b h
h
3 c g 4 j
a b 5 m
m d e f
1 5 6 7 8 2 6 c l d
i l 7 e
j
4 k 8 f k g

Figure (h)
 Now observe the following
1. The size of the matrix is equal to the number of nodes.
2. There is a place to put every link weight between any node and any other node. i.e. The
entry at a row and column intersection is the link weight of the link.
3. A connection from node i to node j does not same that a connection from node j to node
i. For example in figure (h) the (5,6) entry is m but the (6,5) entry is c..
(ii) A simple weight:
 Let ‘1’ means that there is a connection and ‘0’ means that there is no connection.
 The different arithmetic rules are
1+1=1 1+0=1 0+0=0
1x1=1 1x0=0 0x0=0
 A matrix with link weights defined with 1 or 0 is called a connection matrix.
 Consider the following flowgraph and its matrix representation.
1 2 3 4 5 6 7 8
1 1 1 2-1=1
2
3 1 1 2-1=1
1
3 1 1 4 1 1-1=0
1 1 5 1 1-1=0
1 1 e 1
1 5 6 7 8 2 6 1 1 1 3-1=2
1 1 7 1 1-1=0
1
4 1 8 1 1 1 3-1=2

6+1=7
 Each row of a matrix denotes the outlinks corresponding to that node and each column
denotes the inlinks corresponding to that node.
 A branch node is a node with more than one non zero entry in its row. For example rows
1,3,6, and 8 of the above figure have more than one entry, so these nodes are branch
nodes.
 A junction node is a node with more than one non zero entry in its column. For example
columns 5,6 and 7 of the above figure have more than one entry, so these nodes are
junction nodes
 By subtracting 1 from the total number of entries in each row and ignoring rows with no
entries we obtain the number of decisions for each row. Adding these decision values and
then adding 1 to the sum gives the graph’s cyclomatic complexity.
 In the above figure the graph’s cyclomatic complexity is 7.
(iii) Further notation:
 The link weight between node i and node j, is denoted by aij.

Page 15
  A self loop at node i is denoted by aii The link weight for the link between nodes j and i is
denoted by aji.
 Consider the following figure.
h
3 c g
a b
m d e f
1 5 6 7 8 2
i j l
4 k
 From the above figure
abmd=a13 a35 a56 a67
degef=a67 a78 a87 a78 a82
ahekmlld=a13 a37 a78 a85 a56 a66 a66 a67
 The expression aij ajj ajm denotes that a path from node i to j, with a self loop at j and then a
link from node j to m. 
 The transpose of a matrix is the matrix with rows and columns interchanged.
 It is denoted by AT.
 If C=AT then cij=aji
 The intersection of two matrices is denoted by A#B. If C=A # B then cij=aij # bij.
(3) Node Reduction Algorithm:
Write the steps involved in Node Reduction Algorithm. Illustrate with an example?
Node Reduction Algorithm:
Steps:
1. The reduction is done one node at a time by combining the elements in the last column with
the elements in the last row and putting the result into the entry at the corresponding
intersection. This step is called cross-term reduction. After cross term reduction the matrix
size is reduced by one.
2. If there is one entry in one position and we want to enter another entry in that same position
then add that two entries. This step is called parallel reduction.
3. If there is entry in principle diagonal then it represents a self loop. To remove that self loop,
multiply every term in that row by the loop term. This step is called loop reduction.
4. By using the above three steps a 2x2 size matrix is obtained with the path expression. This
path expression is the required path expression from node 1 to node 2.
Example:
 Consider the following flow graph.

 Specify the above flowgraph in the matrix format.

1 2 3 4 5
1 . a
2 .
3 d . b
4 c . f
5 g e h

Page 16
  Remove the self loop at node 5 by applying the loop reduction step.
1 2 3 4 5
1 . a
2 .
3 d . b
4 c . f
5 h*g h*e .
 Combine the elements in the last column with the elements in the last row by applying
cross-term reduction and parallel reduction steps.
1 2 3 4
1 . a
2 .
3 d . b
4 c+fh*g fh*e .
 Combine the elements in the last column with the elements in the last row by applying
cross-term reduction and parallel reduction steps.
1 2 3
1 . a
2 .
3 d+b(c+fh*g) bfh*e

 Again a self loop occurred at node 3. So Remove the self loop by applying loop reduction
step.
1 2 3
1 . a
2 .
3 (bfh*e)*(d+b(c+fh*g))
 Combine the elements in the last column with the elements in the last row by applying
cross-term reduction.
1 2
.
1 a(bfh*e)*(d+b(c+fh*g))

2 .
Note: Refer other four examples from class notes
(4) Applications:
(1) Illustrate the applications of Node Reduction Algorithm:
(i) Maximum Path Count Arithmetic:
 For theory refer unit-5 material.
 For example refer unit-8 notes.
(ii) Probability of path expressions:
 For theory refer unit-5 material.
 For example refer unit-8 notes.

Page 17
(5) Relations:
(1) What is a Relation? What are the different properties of Relations?
Relation:
 The property by which two nodes are interconnected is called a relation.
 A relation can be represented by a link with connecting nodes.
 A link represented with link weight.
 This link weight can be numerical, logical, illogical, or whatever.
 The graph matrix which consists of unweighted simple links is called a connection matrix
 The graph matrix which consists of weighted simple links is called a relation matrix.
Different properties of relations:
 The different properties of relations are.
(i) Transitive Relations:
 A Relation R is transitive if aRb and bRc then aRc.
 Examples of transitive relations are: is connected to, is greater than or equal to, is less than
or equal to, is a relative of, etc.
 Examples of intransitive relations are: is a friend of, is a neighbor of, etc.

(ii) Reflexive Relations:

 A relation R is reflexive if for every a, aRa. This relation represents a self-loop at every
node.
 Examples of reflexive relations are: equals, is a relative of, etc.
 Examples of irreflexive relations include: not equals, is a friend of, etc.
(iii) Symmetric Relations:
 A relation R is symmetric if aRb then bRa. This relation represents if a link from a to b then
there is also a link from b to a.
 A graph whose relations are symmetric is called an undirected graph and a graph whose
relations are not symmetric is called a directed graph
 Examples of symmetric relations are: a relative of, is brother of, etc.
 Examples of asymmetric relations are: is the boss of, is greater than, etc.
(iv) Antisymmetric Relations:
 A relation R is antisymmetric, if aRb and bRa, then a = b.
 Examples of antisymmetric relations are: is greater than or equal to, is a subset of, etc.
 Examples of nonantisymmetric relations are: is connected to, is a relative of, etc.
(2) What are Equivalence Relations and Partial Ordering Relations?
(i) Equivalence Relations:
 A relation is said to be an equivalence relation if it satisfies transitive, reflexive, and
symmetric properties. If a set of objects satisfy an equivalence relation, then it forms an
equivalence class.
 The idea behind a partition-testing is that we can partition the input space into equivalence
classes.
(ii) Partial Ordering Relations:
 A partial ordering relation satisfies the reflexive, transitive, and antisymmetric properties.
 A graph which shows partial ordering relation between its nodes is said to be partial
ordered graph. Partial ordered graphs have different properties. They are
i. loop free,
ii. There is at least one maximum element.
iii. There is at least one minimum element.

Page 18
 iv. If you reverse all the arrows the resultant graph is also partial ordered.
 The maximum element ‘a’ represents the relation xRa. Similarly, the minimum element ‘a’,
represents a relation aRx. Examples are Trees and loop-free graphs.
(6) The Powers of a Matrix:
(i) Explain about Matrix Powers and Products?
Matrix Powers and Products:
 A graph matrix is array representation of nodes. In a graph matrix each row and each
column intersection represents, the relationship between the respective row nodes and
column nodes.
 The square of the matrix represents all path segments with two links long. Similarly the
third power represents all path segments with three links long and so on.
 Let A be a matrix whose entries are aij. The set of all paths between any node i and any
node j is given by
n n n n n n
aij + aik akj + aik akmamj + aikakmaml alj
M

M
M

M
M
M
k=1 k=1 m=1 k=1 m=1 l=1

n n
n n
+... ... aikakmaml . . . aqp apj

M
M
M
M
k=1 m=1 l=1 p=1
 Given a matrix whose entities are aij the square of that matrix is given by
n
M

aij = aik akj

k=1
 When given two matrices A,B with entries aik and bkj respectively. The product of AB is a
new matrix C whose entries are cij.
n
M

cij = aik bkj

k=1

a11 a12 a13 a14 b11 b12 b13 b14 c11 c12 c13 c14
a21 a22 a23 a24 x b21 b22 b23 b24 = c21 c22 c23 c24
a31 a32 a33 a34 b31 b32 b33 b34 c31 c32 c33 c34
a41 a42 a43 a44 b41 b42 b43 b44 c41 c42 c43 c44
c11 = a11b11+ a12 b21 + a13 b31 + a14 b41
c12 =a11b12 + a12 b22 + a13 b32 +a14b42
c13 =a11b13+a12 b23 + a13 b33 + a14b43
c32 = a41b12+ a42 b22+a43 b32 + a44 b42
c44 = a41b14 +a42 b24 +a43b34+a44 b44
 The c32 entry is obtained by combining, the entries in the third row of the A matrix, with the
corresponding elements in the second column of the B matrix. 
Example:
 Consider the following flowgraph and its graph matrix.
1 2 3 4 5
1 a
2
Let A = 3 d b
4 c f
5 g e h .

Page 19
 A2 = A * A
1 2 3 4 5 1 2 3 4 5 1 2 3 4 5
1 a 1 a 1 ad ab
2 2 2
A2 =
3 d b x 3 d b = 3 bc bf
4 c f 4 c f 4 fg fe fh
5 g e h 5 g e h 5 ed+hg he eb h2

A3 = A2 * A
1 2 3 4 5 1 2 3 4 5 1 2 3 4 5
1 ad ab 1 a 1 abc abf
2 2 2
A3 = 3 bc bf x 3 d b = 3 bfg bfe bfh
4 fg fe fh 4 c f 4 fed+fhg fhe feb fh2
5 ed+hg he eb h2 5 g e h 5 hed+ebc+h2g h2e heb ebf+h3

(ii) Explain about the set of all paths and the algorithm for finding set of all paths?
(a) The set of all paths:
 The set of all paths is given by the following infinite series of matrix powers.
∞
∑ Ai = A1+A2+A3+…+A∞
i=1
 Let I be an n x n diagonal matrix where n is the number of nodes, then the above
expression becomes
∞
∑ Ai = A(I+A1+A2+A3+…+A∞)
i=1
 We know that (A+A) = A
So (A+I)2 = A2 + 2AI + I2 = A2 + 2A + I2 = A2 + A+A + I2= A2+A+I. (Since A + A = A)

 Similarly
(A+I)n = I+A1+A2+A3+…An
 Now the original expression becomes
∞
∑ Ai = A(I+A1+A2+A3+…+A∞) = A(A+I)∞
i=1
 If the paths of length n-1, where n is the number of nodes, the set of all such paths is

n-1
∑ Ai = A(A+I)n-2
i=1
(b) The algorithm for finding set of all paths:
 The algorithm for finding set of all paths
1. Express n-2 as a binary number.
2. Calculate the successive squares of (A+I) matrix, that is (A+I)2, (A+I)4, (A+I)8, (A+I)16
and so on.
3. Select only the binary powers of (A+I) matrix that correspond to a value 1 in the binary
representation of (n-2).
4. The set of all paths of length less than or equal to (n-1) is obtained from the original
matrix as a result of step 3.
Page 20
 For example the set of all paths for 16 nodes is given by
15
∑ Ai = A(A+I)8(A+I)4(A+I)2
i=1
 A matrix for which A2=A is said to be idempotent matrix. A matrix whose successive power
gives an idempotent matrix is called idempotent generator. The nth power of a matrix A + I
over a transitive relation is called the transitive closure of the matrix.
(iii) What are the loops? How to convert graphs with loops into loop-free graphs:
 Loops are infinite sum of matrix powers.
 The way to handle loops is similar like handling loops in regular expressions.
 Loop terms are displayed on the principle diagonal of the graph matrix. A loop can be
removed from a graph by using loop reduction step of Node Reduction Algorithm.
Example:
 Consider the following flowgraph and its graph matrix
d
1 2 3 4 5 1 2 3 4 5
a b c
1 3 4 2 1 a 1 1 a
f 2 2 1
e g Let A = 3 d b A+I= 3 d 1 b
5 4 c f 4 c 1 f
h 5 g e h 5 g e h+1

 In (A+I) matrix there is a self loop at node 5. Now we can obtain (A+I)* after removing the
self loop at node 5 by applying loop reduction step.
 i.e. To remove self loop at node 5 multiply loop term h* with all row elements of row 5.
1 2 3 4 5
1 1 a
2 1
(A+I)* = 3 d 1 b
4 c 1 f
5 h*g h*e 1

(A+I)2* = (A+I)* (A+I)*

1 2 3 4 5 1 2 3 4 5 1 2 3 4 5
1 1 a 1 1 a 11 ad a ab
2 1 2 1 2 1
= 3 d 1 b x 3 d 1 b = 3 d+bc 1 b bf
4 c 1 f 4 c 1 f 4 c+fh*g fh*e 1 f
5 h*g h*e 1 5 h*g h*e 1 5 h*g+h*ed h*e h*eb 1

(A+I)3* = (A+I)2* (A+I)* 1 2 3 4 5

1 2 3 4 5 1 2 3 4 5 1 1 ad+abc a ab abf
1 1 ad a ab 11 a 2 1
2 1 2 1 3 d+bc+ 1+ b bf
= 3 d+bc 1 b bf x 3 d 1 b = bfh*g bfh*e
4 c+fh*g fh*e 1 f 4 c 1 f c+fh*g+ 1+
5 h*g+h*ed h*e h*eb 1 h*g h*e
4
fh*ed fh*e fh*eb f
5 1
5 h*g+h*ed 1+
+h*e(d+bc) h*e h*eb h*ebf
 No new loops were found for the second power matrix
Page 21
 But the third power matrix has a loop term bfh*e at node 3. So all other entries in that row
are multiplied by (bfh*e)*. Similarly there is a loop term (fh*eb) at node 4.
 So all other entries in that row are multiplied by (fh*eb)*. Also a loop term (h*ebf)* at
node 5.
 So all other entries in the fifth row is multiplied by (h*ebf)*
(iv) Explain about Partitioning Algorithm in detail?
Partitioning Algorithm:
 It is an algorithm which is used to transform the graphs with loops into loop free graphs.
 There are certain points to remember here. They are
1. A graph is loop free at the top level.
2. Many graphs with loops are easy to analyze, if you know where to break the loops.
3. This algorithm is used to develop a tool which can identify the loops.
 The partition algorithm represents.
(A+I)n # (A+I)nT
Example:
 Consider the following flowgraph and its graph matrix (A + I).
1 2 3 4 5 6 7 8
1 1 1
2 1 1 1
3 1 1
3 4 1 1 1
A+I =
5 5 1 1
4 6 1
7 1 1 1
6 8 1 1

 The transitive closure matrix (A+I)n can be obtained by using the following steps.
Step:1: Mark all diagonal entries by 1
Step:2: The flow from node 1 to node 6 is 1-2-7-2-3-4-5-3-4-6
So mark nodes 1,2,3,4,5,6,7 by 1 in the first row
Step:3: The flow from node 2 to node 6 is 2-7-2-3-4-5-3-4-6
So mark nodes 2,3,4,5,6 by 1 in the second row.
Step:4: The flow from node 3 to node 6 is 3-4-5-3-4-6.
So mark nodes 3,4,5,6 by 1 in the third row
Step:5: The flow from node 4 to node 6 is 4-5-3-4-6.
So mark nodes 3,4,5,6 by 1 in the fourth row
. Step:6: The flow from node 5 to node 6 is 5-3-4-6.
So mark nodes 3,4,5,6 by 1 in the fifth row.
Step:7: The flow from node 6 is only 6. So mark node 6 by 1 in the sixth row.
Step:8: The flow from node 7 to node 6 is 7-2-3-4-5-3-4-6
So mark nodes 2,3,4,5,6,7 by 1 in the seventh row
. Step:9: The flow from node 8 to node 6 is 8-3-4-5-3-4-6
So mark nodes 3,4,5,6,8 by 1 in the eighth row

Page 22
 Therefore the transitive closure matrix is.
1 2 3 4 5 6 7 8
1 1 1 1 1 1 1 1
2 1 1 1 1 1 1
3 1 1 1 1
4 1 1 1 1
(A+I)n =
5 1 1 1 1
6 1
7 1 1 1 1 1 1
8 1 1 1 1 1

 The transpose of (A+I) is. n

1 2 3 4 5 6 7 8
1 1
2 1 1 1
3 1 1 1 1 1 1 1
nT
(A+I) = 4 1 1 1 1 1 1 1
5 1 1 1 1 1 1 1
6 1 1 1 1 1 1 1 1
7 1 1 1
8 1

 The intersection of transitive closure matrix (A+I)n and transpose matrix (A+I)nT is given by,
identifying similar rows and column entries from (A+I) n and (A+I)nT
1 2 3 4 5 6 7 8
1 1
2 1 1
3 1 1 1
4 1 1 1
(A+I)n#(A+I)nT= 5 1 1 1
6 1
7 1 1
8 1
 From the above matrix, by comparing a row/column with other rows/columns, the
equivalent nodes to be grouped.
 After grouping
Let A=[1] B=[2,7] C=[3,4,5] D=[6] E=[8]
 The graph and graph matrix representation to the above values is given by
FlowGraph .

Graph Matrix

A B C D E
A 1 1
B 1 1
C 1 1
D 1
E 1 1

Page 23
(v) Explain about Breaking Loops And Applications:
 Consider the matrix format of a flowgraph.
 If there are any entries on the principal diagonal, then break the loop for that link.
 Here we use successive powers of the matrix.
 Another way to break the loop is applying the node reduction algorithm.
 Here we break the loop or we remove the self loop at any node is, by multiplying loop term
with all other entries in that corresponding row.
(vi) Explain about Some matrix properties?
 To interchange the node names in the flowgraph, we must interchange both the
corresponding rows and the corresponding columns of the node names in the graph matrix.
 Consider the following flowgraph and its Graph matrix.
1 2 3 4 5
1 a
2
3 d b
4 c f
5 g e h

 Interchange rows 3 and 4 to the above graph matrix.

1 2 3 4 5
1 a
2
3 c f
4 d b
5 g e h
 Interchange columns 3 and 4 to the above graph matrix.
1 2 3 4 5
1 a
2
3 c f
4 d b
5 g e h
 The flowgraph to the above graph matrix is given by.

 By comparing the above flowgraph with the given flowgraph, it is proved that nodes 3,4 are
interchanged

Page 24
(7) Building Tools:
Explain about building tools of graph matrices?
i. Matrix Representation in software:
 A graph is an abstract representation of the software structure.
 Theoretically speaking, graphs are the simple structures but when used in theorem proving
we have to apply graph matrices.
 It consists of
a) Overview:
 We prove theorems and develop graph algorithms by using graph matrices. When we
want to process graphs in a computer we represent them as linked lists.
b) Node degree and graph density:
 Each intermediate node may have any number of inner links and outer links.
 The inner links of a node represents the in degree of the node.
 Similarly the outer links of a node represents the out degree of a node.
 The sum of in degree and out degree of a particular node is the degree of that node.
 The average degree of a node for a graph is between 3 and 4.
 The degree of a simple branch and simple junction is 3.
 The degree of a loop in a graph is 4.
 Any graph with average degree of 5 or 6 is said to be a very busy flowgraph.
c) What is wrong with arrays:
 We can represent the matrix as a two-dimensional array for small graphs with simple
weights, but this is not convenient for larger graphs because
(i) Space:
 Matrix representation requires a large storage space.
 Hence a linked list representation is used which requires less storage space.
(ii) Weights:
 An additional weight matrix is required for complicated link weights.
(iii) Variable-Length Weights:
 The link weights in a flow graphs are represented in a two dimensional string array
(matrix format), in which most of entries are null.
(iv) Processing time:
 Since many entries of the graph matrices are null, the time taken to process such
entries are more.
d) Linked-list Representation:
 Consider following the flowgraph.

 The linked list for the above flowgraph is

Page 25
 1,3;a
2,exit
3,2;d
3,4;b
4,2;c
4,5;f
5,2;g
5,3;e
5,5;h
 List entries are usually placed in lexicographic (dictionary) order.
 The link weight expressions are stored in a string array to which link names act as
pointers.
 If the link weights are values then, they are stored in an array of fixed length.
List Entry Content
1 node 1,3;a
2 node 2,exit
3 node 3,2;d
,4;b
4 node 4,2;c
,5;f
5 node 5,2;g
,3;e
,5;h
 The node names appear only once, at the first link entry. A node name i.e starting node
is used for the list entry.
 And there are back pointers for the inlinks. So we get
List Entry Content List Entry Content
1 node 1,3;a 4 node 4,2;c
2 node 2,exit ,5;f
3, 3,
4, 5 node 5,2;g
5, ,3;e
3 node 3,2;d ,5;h
,4;b 4,
1, 5,
5,
 It is important to keep the lists sorted in lexicographic order with the following priorities:
node names or pointer outlink names, inlink names.
2. Matrix Operations:
a) Parallel Reduction:
 Parallel links after sorting are adjacent entries with the same pair of node names. Ex:
y
node 17,21;x
,44;y
,44;z
,44;w
 We have three parallel links from node 17 to 44. So

Page 26
 Node 17,21;x
,44;y(where y=y+z+w)
b) Loop Reduction:
 The loop reduction step is used to remove the loop. Here self link represents the loop.
 For removing a loop, the loop term is multiplied with all the outer links of the node at
which the loop presents. Consider the following example.

List Entry Content Before Content After

5 node 5,2;g node 5,2;h*g
,3;e ,3;h*e
,5;h
4, 4,
5,
c) Cross term reduction:
 Select a node for reduction.
 The cross term reduction represents that we combine every inlink to the node with every
outlink from that node after removing that node.
 The links created by node removal are stored in a separate list which is then sorted and
thereafter merged into the master list.
d) Addition, Multiplication and other operations:
 Here addition of two matrices is simple. Multiplication is more complicated.
 Transposition is done by reversing the pointer directions, resulting in a list that is not
correctly sorted. Sorting that list provides the transpose. All other matrix operations can
be easily implemented by sorting, merging, and combining parallels.
List Entry Content Before Content After
d
2 node 2,exit node 2,exit
1 a 3 b 4 c 2
3, 3,
f 4, 4,
e g 5, 5,
5 3 node 3,2;d node 3,2;d
h ,4;b ,2;bc
,5;bf
1, 1,
5, 5,
4 node 4,2;c
,5;f
3,
5 node 5,2;h*g node 5,2;h*g
,3;h*e ,3;h*e
4,
3. Node Reduction Optimization:
 The optimum order for node reduction is to do lowest-degree nodes first. The idea is to get
the lists as short as possible as quickly as possible. Nodes of degree 3 reduce the total link
count by one link when removed. A degree-4 node keeps the link count the same, and all
higher-degree nodes increase the link count.
 For large graphs with 500 or more nodes and an average degree of 6 or 7, the difference
between not optimizing the node-reduction order and optimizing it was about 50: 1 in
processing time.
Page 27
 SOFTWARE TESTING TOOLS
(1) Introduction to Testing-Automated Testing:
 Automated Testing means using an automation tool executing the test case suite. Manual
Testing is performed by a human sitting in front of a computer carefully executing the test steps.
 The automation software can also enter test data into the System. Now compare expected and
actual results and generate detailed test reports. Test Automation demands considerable
investments of money and resources.
 Successive development cycles will require execution of same test suite repeatedly. Using a test
automation tool, it's possible to record this test suite and re-play it as required. Once the test suite
is automated, no human test is required.
 This improve ROI (Return On Investment) of Test Automation. The goal of Automation is to
reduce the number of test cases to be run manually and not to eliminate Manual Testing.
(2) Concepts of Test Automation:
(i) Test Automation
 Automated Software Testing or Test Automation is the process of automating the manual test
cases. This also involves comparing the run time data with the test data provided, and producing
useful Test Results.
(ii) Test Automation tool – What we can expect
 To test a software, a manual testing engineer needs to do the following basic actions:
1. Click a button, link, image
2. Select radio button
3. Check / Uncheck a checkbox
4. Type into an Edit box or controls which resemble edit box
 But also he needs to get the run time data from the application and compare with the test data
provided (i.e. checkpoints). For this actually, we will be extracting the values from an edit box,
button, link, image, table, drop down list, etc.
 All of these basic features are provided by Test Automation tools such as QTP(Quick Test
Professional). There are many test automation tools which allow users to record user actions
and replay them any number of iterations and compare the actual results with the test data and
generate results.
(iii) Why Test Automation?
 Since the very large quantity of software development tools available in the market the
productivity of the developer is dramatically increased over the past years.
 To manage the quality of the product developed it is essential to thoroughly test all the features of
the application.
 If the application is a large software product having lot of features, then it is very much difficult to
test by manually executing the test cases.
 There will be a lot of pressure on testing team to test more and more functionalities in less
time. Hence, the Automation Testing has become an integral part of software development.
(iv) Benefits of Test Automation:
(a) Execution is Less Time Consuming:
 Automated tools execute the test cases (test script) faster than manual test case execution.
 Hence, in less time, more end-to-end test cases can be covered during test execution.
(b) Un-attended mode execution:

Page 28
 There is no need of human involvement for the execution of entire Test Automation Suite for
regression testing. But, to achieve the unattended mode execution, the automation framework
has to be properly designed.
(c) Repeatable:
 The test suite can be executed multiple times on the application under test.
 For example, if there is a need to test the application on different browsers and environments, we
need to just change the configurations of the test automation suite and execute.
 In case of manual execution, we would need one more resource to execute the same set of test
cases on different environment / browser.
(d) Reusability:
 The test suite can be built in such a way that the functions or methods written are highly reusable
across the framework. Also, the entire test suite built with a proper framework can also be utilized
for different versions of the application under test.
(e) Consistency of Test Execution:
 There is a chance of manual tester making errors during execution of test cases. But, the test
suite being automated we can expect no or zero errors during execution.
 For example, if there is a need to enter a value in an edit box such as 7693178.87651, a manual
tester might make mistakes (as this is a big number with five decimal values) but the automation
tool will not make any mistakes. It will enter the same value even if the test is run for many times.
(f) Better Coverage:
 As the time required executing automated test suite will be less compared to manual test case
execution, more number of test scenarios can be covered during the execution.
 Hence, we can expect better coverage.
(g) Cost Effective:
 Once the test suite is completely ready for regression testing, the resources required will be less
compared to manual test execution. This reduces the cost of testing.
(v) Key factors to be considered in Test Automation:
(a) Test automation is expensive
 It involves testing tools as well as skilled professionals.
(b) Size of the Regression Test Suite:
 Generally, a recommendation is made for test automation if there is a long regression cycle.
(c) Tool compatibility:
 Test Automation tool has to be compatible with the application under test.
 A comprehensive tool evaluation has to be conducted and a best suited tool should be
recommended for automation testing.
(d) No. of Regression Cycles:
 If there is a need to execute the automated test suite against many builds / releases then the test
automation becomes cost effective and beneficial.
(3) Introduction to list of tools like Win runner, Load Runner & JMeter:
(i) Win Runner:
 Win Runner is the most used Automated Software Testing Tool.
 Main Features of Win Runner are
•Developed by Mercury Interactive
•Functionality testing tool
•Supports o/s and web technologies
•To Support .net, xml, SAP, Multimedia etc we can use QTP.
• Winrunner run on Windows only.
•Xrunner run only UNIX and linux.
•Tool developed in C on VC++ environment.

Page 29
 •To automate our manual test win runner used TSL (Test Script language like c)
The main Testing Process in Win Runner is
1) Learning
 Recognization of objects and windows in our application by winrunner is called learning.
2) Recording
 Winrunner records over manual business operation in TSL
3) Edit Script
 Depends on corresponding manual test, test engineer inserts check points in to that record script.
4) Run Script:
 During test script execution, winrunner compare tester given expected values and application
actual values and returns results.
5) Analyze Results
 Tester analyzes the tool given results to concentrate on defect tracking if required.
(ii) Load Runner:
 LoadRunner is a software testing tool from Micro Focus.
 It is used to test applications, measuring system behaviour and performance under load.
 LoadRunner can simulate thousands of users concurrently using application software, recording
and later analyzing the performance of key components of the application.
 The components of LoadRunner are The Virtual User Generator, Controller, and the Agent
process, LoadRunner Analysis and Monitoring, LoadRunner Books Online.
 The Component of LoadRunner would you use to record a Script is the Virtual User Generator
(VuGen) component .
 LoadRunner copy hundreds or thousands of human users with Virtual Users (Vusers) to apply
measurable & repeatable production workloads and stresses an Application end-to-end.
 Vusers copy the actions of human users by performing typical Business Processes.
 For each user action, the tool submits an input request to server and receives the response.
 Increase number of Vusers, to increase the load on the Server.
(iii) Jmeter:
 The Apache JMeter is pure Java open source software, which was first developed by Stefano
Mazzocchi of the Apache Software Foundation, designed to load test functional behavior and
measure performance. You can use JMeter to analyze and measure the performance of web
application or a variety of services.
 Apache JMeter is a testing tool used for analyzing and measuring the performance of different
software services and products. It is a pure Java open source software used for testing Web
Application or FTP application. It is used to execute performance testing, load testing and
functional testing of web applications.
 First JMeter can be integrated into selenium using the plugins, So Selenium you can use as
an automation tool for your testing needs. The Apache JMeter is pure Java open source
software, designed to load test functional behavior and measure performance.
 JMeter is an open source desktop Java application that is designed to load test and measure
performance. It can be used to simulate loads of various scenarios and output performance data
in several ways, including CSV and XML files, and graphs.
 Apache JMeter is one of the most popular open source systems for testing applications, and also
a 100% Java scripted desktop application.
(4) About Win Runner:
 WinRunner is a test automation tool, designed to help customers save testing time and effort by
automating the manual testing process. Automated testing with WinRunner addresses the
problems by manual testing, speeding up the testing process

Page 30
 WinRunner uses the GUI Map file to recognize objects on the application. When WinRunner runs
a test, it uses the GUI map to locate objects. It reads an object's description in the GUI map and
then looks for an object with the same properties in the application being tested
(5) Using Win runner:
 After installing the WinRunner on your computer, invoke the WinRunner application:
Start -> Programs ->WinRunner ->WinRunner
 The opening screen of the WinRunner application is displayed, prompting you to select one of the
three options:
New Test: To create a new test script
Open Test: To open an existing test script
Quick Preview: To view the quick preview of WinRunner

(6) Recording Test Cases

 To test any application, first you can run the application and understand its operation. Then, you
can invoke WinRunner, again run the application and record the GUI operations.
 During the recording mode, WinRunner will capture all your actions, which button you pressed,
where you clicked the mouse etc. You need to work with the application as usual and perform all
the actions to be tested.
 Once the recording is completed, WinRunner generates a script in TSL (Test Script Language).
You can run this test script generated by WinRunner to view the results. The test results will
show whether the test has passed or failed.
 There are two modes of recording:
(i)Context Sensitive mode:
 This mode of recording is used when the location of the GUI controls (i.e. X and Y coordinates)
or the mouse positions are not necessary.

Page 31
(ii)Analog mode:
 This mode of recording is used when the mouse positions, the location of the controls in the
application, also play an important role in testing the application. This mode of recording has to
be used to validate bitmaps, testing the signature etc.
 The procedure for recording a test case is as follows:
Step 1: Open a new document: File -> New (or) Select "New Test"
from the WinRunner's Welcome screen.
Step 2: Open (run) the application to be tested.
Step 3: Start recording a test case.
Create ->Record - Context Sensitive (or) click on the toolbar's "Record" button once, to record in
Context Sensitive mode.
Step 4: Select the application to be tested by clicking on the application's title bar.
Step 5: Perform all the actions to be recorded.
Step 6: Once all required actions are recorded, stop the recording.
Create -> Stop (or) Click on the toolbar's "Stop" button to stop the recording WinRunner
generates the script for the recoded actions.
Mapping the GUI,
 When WinRunner runs a test, it uses the GUI map to locate objects. It reads an object's
description in the GUI map and then looks for an object with the same properties in the
application being tested. Each of these objects in the GUI Map file will be having a logical name
and a physical description.
 There are two views in the GUI Map Editor, which enable you to display the contents of either:
(i) the entire GUI map
(ii) an individual GUI map file
(i)the entire GUI map
 When viewing the contents of specific GUI map files, you can expand the GUI Map Editor to view
two GUI map files simultaneously. This enables you to easily copy or move descriptions between
files.
 To view the contents of individual GUI map files, choose View GUI Files.
(ii)an individual GUI map file
 In the GUI Map Editor, objects are displayed in a tree under the icon of the window in which they
appear. When you double-click a window name or icon in the tree, you can view all the objects it
contains. To concurrently view all the objects in the tree, choose View Expand Objects Tree. To
viewwindows only, choose ViewCollapse Objects Tree.
 When you view the entire GUI map, you can select the Show Physical Description check box to
display the physical description of any object you select in the Windows/Objects list.
 When you view the contents of a single GUI map file, the GUI Map Editor automatically displays
the physical description.
 Suppose the WordPad window is in your GUI map file. If you select Show Physical
Description and click the WordPad window name or icon in the window list, the following
physical description is displayed in the middle pane of the GUI Map Editor:
(7) Working with Test:
 WinRunner facilitates easy test creation by recording how you work on your application. As you
point and click GUI (Graphical User Interface) objects in your application, WinRunner generates
a test script in the C-like Test Script Language (TSL).
 You can further enhance your test scripts with manual programming.
 User can create tests using recording or programming or by both. While recording, each
operation performed by the user generates a statement in the Test Script Language (TSL).

Page 32
 These statements are displayed as a test script in a test window. User can then enhance the
recorded test script, either by typing in additional TSL functions and programming elements or by
using WinRunner’s visual programming tool, the Function Generator, or using the Function
Viewer.
(8) Checkpoints:
 Checkpoints allow user to compare the current behavior of the application being tested to its
behavior in an earlier version. If any mismatches are found, WinRunner captures them as actual
results.
 User can add four types of checkpoints to test scripts they are
(i)GUI Checkpoints
(ii)Bitmap Checkpoints
(iii)Text checkpoints
(iv)Database checkpoints
(i) GUI checkpoints
 It verifies information about GUI objects. For example, user can check that a button is enabled or
see which item is selected in a list. There are three types of GUI Check points they are
(a)For Single Property
(b)For Object/Window
(c)For Multiple Objects
(a) GUI checkpoint for single property:-
 User can check a single property of a GUI object. For example, user can check whether a button
is enabled or disabled or whether an item in a list is selected.
(b) GUI checkpoint for object/window:-
 User can create a GUI checkpoint to check a single object in the application being tested.
 User can either check the object with its default properties or user can specify multiple properties
to check.
(c) GUI checkpoint for multiple objects:-
 User can create a GUI checkpoint to check multiple objects in the application being tested. User
can either check the object with its default properties or user can specify multiple properties of
multiple objects to check.
(ii) Bitmap Checkpoint :
 It checks an object, a window, or an area of a screen in the application as a bitmap. While
creating a test, user can indicate what user want to check. WinRunner captures the specified
bitmap, stores it in the expected results folder (exp) of the test, and inserts a checkpoint in the
test script. While running the test, WinRunner compares the bitmap currently displayed in the
application being tested with the expected bitmap stored earlier.
 In the event of a mismatch, WinRunner captures the current actual bitmap and generates a
difference bitmap. By comparing the three bitmaps (expected, actual, and difference), user can
identify the nature of the discrepancy there are two types of bitmap check points they are
(a) Bitmap Checkpoint for Object/Window: -
 User can capture a bitmap of any window or object in the application by pointing to it.
(b) Bitmap Checkpointfor Screen Area:-
 User defines any rectangular area of the screen and captures it as a bitmap for comparison.
(iii) Text checkpoints
 It reads and check text in GUI objects and in areas of the screen. While creating a test user has
to point to an object or a window containing text. WinRunner reads the text and writes a TSL
statement to the test script.
 Later user can add simple programming elements to test scripts to verify the contents of the text.
User should use a text checkpoint on a GUI object only when a GUI checkpoint cannot be used 
Page 33
 to check the text property. There are two types of Text checkpoints they are
From Object/Window
From Screen Area
(iv) Database checkpoints
 It checks the contents and the number of rows and columns of a result set, which is based on a
query user, create on database. There are three types of database check points they are
(a) Default Check:-
 Used to check the entire contents of a result set, Default Check are useful when the expected
results can be established before the test run.
(b) Custom Check:-
 Used to check the partial contents, the number of rows, and the number of columns of a result
set.
(c) Runtime Record Check:-
 User can create runtime database record checkpoints in order to compare the values displayed in
the application during the test run with the corresponding values in the database.
(9) Test Script Language & Enhancing Test
 TSL stands for “Test Scripting Language”. The test scripts are written in Test Scripting Language
in winrunner. TSL is an enhanced, C-like programming language designed for testing.
 The advantages of TSL are:
It is easy to use.
It is similar to other programming languages. ...
It is a high level language.
 When you record a test, a test script is generated in Mercury Interactive’s Test Script Language
(TSL). Each line WinRunner generates in the test script is a statement.
 A statement is any expression that is followed by a semicolon. Each TSL statement in the test
script represents keyboard and/or mouse input to the application being tested. A single statement
may be longer than one line in the test script.
 TSL is a C-like programming language designed for creating test scripts. It combines functions
developed specifically for testing with general purpose programming language features such as
variables, control-flow statements, arrays, and user-defined functions. You enhance a recorded
test script simply by typing programming elements into the test window, If you program a test
script by typing directly into the test window, remember to include a semicolon at the end of each
statement.
 TSL is easy to use because you do not have to compile. You simply record or type in the test
script and immediately execute the test.
 TSL includes four types of functions:
 Context Sensitive functions perform specific tasks on GUI objects, such as clicking a button
or selecting an item from a list. Function names, such as button_press andlist_select_item,
reflect the function’s purpose.
 Analog functions depict mouse clicks, keyboard input, and the exact coordinates traveled by
the mouse.
 Standard functions perform general purpose programming tasks, such as sending messages
to a report or performing calculations.
 Customization functions allow you to adapt WinRunner to your testing environment.
 WinRunner includes a visual programming tool which helps you to quickly and easily add TSL
functions to your tests. For more information, see “Generating Functions.”
 This chapter introduces some basic programming concepts and shows you how to use a few
simple programming techniques in order to create more powerful tests. For more information,
refer to the following documentation:

Page 34
(10) Running and Debugging Tests
(i) Create Tests
 Next, you create test scripts by recording, programming, or a combination of both. While
recording tests, insert checkpoints where you want to check the response of the application being
tested. You can insert checkpoints that check GUI objects, bitmaps, and databases.
 During this process, WinRunner captures data and saves it as expected results—the expected
response of the application being tested.
(ii) Debug Tests
 You run tests in Debug mode to make sure they run smoothly. You can set breakpoints, monitor
variables, and control how tests are run to identify and isolate defects.
 Test results are saved in the debug folder, which you can discard once you’ve finished debugging
the test.
 When WinRunner runs a test, it checks each script line for basic syntax errors, like incorrect
syntax or missing elements in If, While, Switch, and For statements.
 You can use the Syntax Check options (Tools Syntax Check) to check for these types of syntax
errors before running your test.
(iii) Run Tests
 You run tests in Verify mode to test your application. Each time WinRunner encounters a
checkpoint in the test script, it compares the current data of the application being tested to the
expected data captured earlier.
 If any mismatches are found, WinRunner captures them as actual results.
(11) Analyzing Results:
 After you run a test, you can view the results in the Test Results window. The appearance of this
window depends on the Report View option you select in the Runcategory of the General
Options dialog box.
 There are two types of Test Results Views:
(i)WinRunner report view
 Displays the test results in a Windows-style viewer.
 If you run a test that includes a call to a QuickTest test, the WinRunner report view displays only
basic information about the results of the QuickTest test.
 When running tests that call QuickTest tests, it is recommended to use the Unified report view.
(ii)Unified report view
 Displays the results in an HTML-style viewer.
 The unified TestFusion report viewer is identical to the style used for QuickTest Professional test
results.
 If you run a test that includes a call to a QuickTest test (version 6.5 or later), the unified report
view enables you to view detailed results of each step in the called QuickTest test.
 Regardless of the selected report view, the test results window always contains a description of
the major events that occurred during the test run, such as GUI, bitmap, or database
checkpoints, file comparisons, and error messages. It also includes tables and pictures to help
you analyze the results.
(12) Batch Tests,
 A batch test is a test script that calls other tests.
 You program a batch test by typing call statements directly into the test window and selecting the
Run in batch mode option in the Run category of the General Options dialog box before you
execute the test.

Page 35
 A batch test is a test script that calls other tests. You program a batch test by typing call
statements directly into the test window and selecting the Run in batch mode option in
the Run category of the General Options dialog box before you execute the test.
 A batch test may include programming elements such as loops and decision making statements.
Loops enable a batch test to run called tests a specified number of times.
 Decision-making statements such as if/else and switch condition test execution on the results of
a test called previously by the same batch script.
 See “Enhancing Your Test Scripts with Programming,” for more information.
 You execute a batch test in the same way that you execute a regular test.
 Choose a mode (Verify, Update, or Debug) from the list on the toolbar and choose Test > Run
from Top. See “Understanding Test Runs,” for more information.
 When you run a batch test, WinRunner opens and executes each called test. All messages are
suppressed so that the tests are run without interruption.
 If you run the batch test in Verify mode, the current test results are compared to the expected
test results saved earlier.
 If you are running the batch test in order to update expected results, new expected results are
created in the expected results folder for each test.
 See “Storing Batch Test Results” below for more information. When the batch test run is
completed, you can view the test results in the Test Results window.
 Note that if your tests contain TSL texit statements, WinRunner interprets these statements
differently for a batch test run than for a regular test run. During a regular test
run, texit terminates test execution.
 During a batch test run, texit halts execution of the current test only and control is returned to the
batch test.
(13) Rapid Test Script Wizard
 The Rapid test script wizard is the fastest way of performing the test process. It systematically
opens up all the windows in the application, stores the learnt information in the GUI Map file and
generates the test cases based on the information learnt from the application.
 It is possible to apply these tests only on those applications, which open windows upon
performing some task (like clicking a button, selecting the menu item etc). Let us apply this
wizard on the Calculator application whose GUI is shown in Figure.

Page 36