VALIDATION, VERIFICATION,

AND TESTING FOR

THE INDIVIDUAL PROGRAMMER

NBS Special Publication 500-56

U.S. DEPARTMENT OF COMMERCE

National Bureau of Standards
NATIONAL BUREAU OF STANDARDS

The National Bureau of Standards' was established by an act of Congress on March 3, 1901. The Bureau's overall goal is to strengthen and advance the Nation's science and technology

and facilitate their effective application for public benefit. To this end, the Bureau conducts

research and provides: (1) a basis for the Nation's physical measurement system, (2) scientific and technological services for industry and government, (3) a technical basis for equity in trade, and (4) technical services to promote public safety. The Bureau's technical work is per- formed by the National Measurement Laboratory, the National Engineering Laboratory, and

the Institute for Computer Sciences and Technology.

THE NATIONAL MEASUREMENT LABORATORY provides the national system of

physical and chemical and materials measurement; coordinates the system with measurement

systems of other nations and furnishes essential services leading to accurate and uniform

physical and chemical measurement throughout the Nation's scientific community, industry,

and commerce; conducts materials research leading to impioved methods of measurement,

standards, and data on the properties of materials needed by industry, commerce, educational

institutions, and Government; provides advisory and research services to other Government

agencies; develops, produces, and distributes Standard Reference Materials; and provides

calibration services. The Laboratory consists of the following centers:

Absolute Physical Quantities' — Radiation Research — Thermodynamics and

Molecular Science — Analytical Chemistry — Materials Science. THE NATIONAL ENGINEERING LABORATORY provides technology and technical ser- vices to the public and private sectors to address national needs and to solve national problems; conducts research in engineering and applied science in support of these efforts; builds and maintains competence in the necessary disciplines required to carry out this research and technical service; develops engineering data and measurement capabilities;

provides engineering measurement traceability services; develops test methods and proposes

engineering standards and code changes; develops and proposes new engineering practices;

and develops and improves mechanisms to transfer results of its research to the ultimate user. The Laboratory consists of the following centers:

Applied Mathematics — Electronics and Electrical Engineering- — Mechanical

Engineering and Process Technology^ — Building Technology — Fire Research —

Consumer Product Technology — Field Methods.

THE INSTITUTE FOR COMPUTER SCIENCES AND TECHNOLOGY conducts

research and provides scientific and technical services to aid Federal agencies in the selection, acquisition, application, and use of computer technology to improve effectiveness and

economy in Government operations in accordance with Public Law 89-306 (40 U.S.C. 759), relevant Executive Orders, and other directives; carries out this mission by managing the Federal Information Processing Standards Program, developing Federal ADP standards

guidelines, and managing Federal participation in ADP voluntary standardization activities; provides scientific and technological advisory services and assistance to Federal agencies; and

provides the technical foundation for computer-related policies of the Federal Government.

The Institute consists of the following centers:

Programming Science and Technology — Computer Systems Engineering.

'Headquarters and Laboratories at Gaithersburg, MD, unless otherwise noted; mailing address Washington, DC 20234. ^Some divisions within the center are located at Boulder, CO 80303.
MATIONAL BL/Iv or OTANDAJQL LIBRART COMPUTER SCIENCE & TECHNOLOGY: JUN 1 7 i; VALIDATION, VERIFICATION, AND TESTING

FOR THE INDIVIDUAL PROGRAMMER

ft -

Martha A. Branstad

John C. Cherniavsky

W. Richards Adrion

Center for Programming Science and Technology

Institute for Computer Sciences and Technology

National Bureau of Standards

Washington, DC 20234

U.S. DEPARTMENT OF COMMERCE, Philip M. Klutznick, Secretary

Luther H. Hodges, Jr., Deputy Secretary

Jordan J. Baruch. Assistant Secretary for Science and Technology

NATIONAL BUREAU OF STANDARDS, Ernest Ambler, Director

Issued February 1980
Reports on Computer Science and Technology

The National Bureau of Standards has a special responsibility within the Federal

Government for computer science and technology activities. The programs of the

NBS Institute for Computer Sciences and Technology are designed to provide ADP

standards, guidelines, and technical advisory services to improve the effectiveness of

computer utilization in the Federal sector, and to perform appropriate research and

development efforts as foundation for such activities and programs. This publication

series will report these NBS efforts to the Federal computer community as well as to interested specialists in the academic and private sectors. Those wishing to receive

notices of publications in this series should complete and return the form at the end

of this publicaton.

National Bureau of Standards Special Publication 500-56

Nat. Bur. Stand. (U.S.), Spec. Publ. 500-56, 26 pages (Feb. 1980) CODEN. XNBSAV

Library of Congress Catalog Card Number: 80-600005

U. S. GOVERNMENT PRINTING OFFICE

WASHINGTON: 1980

For sale by the Superintendent of Documents, U.S. Government Printing Office, Washington, D.C. 20402

Stock No. 003-003-02159-8 Price $1.75

(Add 25 percent for other than U.S. mailing).
TABLE OF CONTENTS

Page

1. Introduction 1

2. Verification Through the Life Cycle 3

3 . Testing . 6

4. Requirements 9

5. Design 11

6. Construction 13

7. Operation 18

8. Summary and General Rules 18

References 21

Bibliography 22

-ill-

VALIDATION, VERIFICATION, AND TESTING

FOR THE INDIVIDUAL PROGRAMMER

Martha A. Branstad

John C. Cherniavsky

W. Richards Adrion

Guidelines are given for program testing and

verification to insure quality software for the

programmer working alone in a computing environment with limited resources. The emphasis is on

verification as an integral part of the software

development. Guidance includes developing and

planning testing as well as the application of

other verification techniques at each lifecycle

stage. Relying upon neither automated tools nor

formal quality assurance support, the guidelines

should be appropriate for applications programmers

doing small development projects.

Key words: Testing; Program Verification; Software

Deve 1 o pment

.

1. Introduction

Testing, validation and verification of software is a difficult and arduous task even for a manager with automated

tools and sufficient people to devote to the task. This report is intended as a guideline to those who are developing

programs and software with limited resources. It is aimed

at the production of quality software through the use of

sound verification methods, techniques, and planning. The

most common resource limited environment is that of the single programmer working alone on a development project.

The domain of the solitary programmer is unique and

warrants a specialized guide to verification and testing.

Neither the problems nor the solutions that exist for the

development of medium or large computer systems apply.

Problems of coordinating several programmers do not exist in

this domain nor do massive integration efforts. All management is done by the programmer. No independent internal or external quality assurance groups exist. In addition, the

problem is usually of a size which is intellectually manageable.

-1-
The verification and validation approaches used for

medium and large systems are not always applicable to the

environment of the single programmer. For instance, tool

development is stressed for large and medium systems. For

very small program development, time and cost restrictions

do not allow for specialized tool development. Although

this report assumes limited resources, tools which exist locally should not be ignored. A skilled craftsman uses the

best tools available.

This report concentrates on inexpensive verification

and testing techniques to assure the quality of work. For a more comprehensive treatment of verification techniques and

tools the reader is referred to a forthcoming NBS Special

Publication [ADRI80].

Since we believe verification should be performed at

every development stage, this report is organized around the

life cycle stages given in Figure 1.

RE QUIREMENTS DESIGN CONSTRUCTION OPERATION & MAINTENANCE

Figure 1. Life Cycle Stages for Software Development

Section 2 introduces verification techniques and planning

which should be employed throughout the life cycle. Section

3 discusses testing in general and why it is difficult.

Section 4,5,6, and 7 discuss verification and testing during

the requirements, design, construction, and operation

stages, respectively. Section 8 summarizes and presents a collection of general rules.

The following definitions of common terms are used in

this document. It should be noted that some of these terms

may appear with slightly different meanings elsewhere in the

1 it erat ure

.

1. VALIDATION: determination

final program or software

ment project with respect t quirements. Validation is

verifying each stage of the

f e c yc 1 e .

of the correctness of the

produced from a developo the user needs and reusually accomplished by

software development li2. CERTIFICATION: acceptance of software by an authorized agent usually after the software has been validated by the agent, or after its validity has been

demonstrated to the agent.

-2-
3. VERIFICATION: in general the demonstration of consistency, completeness, and correctness of the

software at each stage and between each stage of the

development llfecycle. Requirements are verified;

successive iterations of the design specifications

are verified internally, both against the requirements and the earlier iterations; modules are unit

tested and verified against the design specifications; and the system undergoes intensive verification during integration at the construction stage.

For small programs, verification is the process of

determining the correspondence between a program and

its specification. Static analysis, dynamic

analysis, and program testing are used during verification .

4. TESTING: examination of the behavior of a program by

executing the program on sample data sets.

5. PROOF OF CORRECTNESS: use of techniques of logic to

infer that an assertion assumed true at program entry implies that an assertion holds at program exit.

6. PROGRAM DEBUGGING: the process of correcting syntactic and logical errors detected during coding. Debugging occurs before the program or module is fully

executable and continues until the programmer feels

the program or module is sound and executable. Testing is then used to exercise the code over a sufficient range of test data to verify its adherence to

the design and requirements specifications.

2. Verification Through the Life Cycle

Problem solving is a creative process that follows a general paradigm. The first step is to carefully define the

problem to be solved. Next a solution is hypothesized. The

trial solution is then scrutinized and exercised to determine if it works. Based upon the results of the third step,

modifications are made to the problem statement or to the

trial solution. The revised solution is again exercised and

scrutinized. Many iterations may occur before the problem

solver is satisfied with the solution. When this state occurs, the solution is prepared in final form and final testing is performed.

If the original problem Is so difficult that no trial

solution comes immediately to mind, it should be transformed

into a new problem as follows:

-3-
a. Identify the problem as a particular case of a problem whose solution is known.

b. Solve a specific inst

that it will lead to

Solution of this new problem

ance of the problem in the hope

the general solution,

proceeds as above.

Computer programming is a form of problem solving. Its

solution paradigm is called the development life cycle and

is organized into stages. There are many life cycle charts

in the 1 it erat ure , [ NB S 7 6 ] [DOD77] but no one current chart

is appropriate for all views of the development process. The

one given in Figure 1 is representative. During the requirements stage, the problem to be solved is carefully defined. The design stage is when general solutions are hypothesized and data and process structures are organized.

During construction the program modules are coded and debugged. The modules are integrated and the interfaces debugged. Testing begins as the program is exercised over the

test data selected during this and earlier stages. The program is used and maintained during the final stages.

Some significant differences are apparent between the

problem solution paradigm described in the first paragraphs

and the development life cycle described above. The life

cycle activity is expressed as a straight line solution

whereas the previous paradigm emphasized iteration toward a solution. Anyone who has ever programmed knows that iteration is essential. Iteration is the result of the verification process and error assessment. Unless the correct problem Is stated and the correct solution achieved at the first

try, modification and iteration occur.

Verification should accompany each stage of the

development life cycle. If the verification process is isolated in a single stage then problem statement errors or design errors discovered at that stage may exact an exorbitant price. Not only must the original error be corrected

but the structure built upon it must be changed also.

Viewing each development stage as a sub-problem leads

to a more productive paradigm for program development. The

amended life cycle chart in Table 1 presents the verification activities that accompany each development stage.

-4-
Table 1. Life Cycle Verification Activities

Life Cycle Stage Verification Activities

Re qui r ement s Determine Correctness

Generate Functional Test Data

De sign Determine Correctness and Consistency

Generate Structural and Functional

: Test Data

Construe tion : Determine Correctness and Consistency

Generate Structural and Functional

Test Data

Apply Test Data

Ope rat i on

& Maintenance

: Retest

At each stage the verification activities should include:

1. Determine the correctness and consistency of

the structures produced at the stage, and

2. Generate test data based upon structures introduced at that stage.

For the design and construction stages it is also necessary

to :

3. Determine that the structures are consistent

with those at the previous stage, and

4. Refine and redefine test sets generated earlier.

-5-
Performing the above activities at each development

stage should help to locate errors when they are introduced

and will also partition the test set construction.

3. Testing

Great strides have been made toward the development of

formal verification techniques. These techniques, based on

ideas of formal semantics and proof techniques, while being

promising research avenues are not easily applied without

supporting tools (verifiers). Currently automated verifiers

are expensive, not widely available, and limited in application. For the single programmer, testing is the most easily

applied verification technique. Testing is, as we will discuss, limited in its ability to demonstrate correctness.

Testing shows the presence of errors, and generally (excluding exhaustive testing) cannot demonstrate the absence

of errors.

One view of a program is as a representation of a function taking elements from one set (called the domain) and

transforming them into elements of another set (called the

range). The testing process is then used to ensure that the

implementation (the program) faithfully realizes the function. Since programs are frequently given Inputs that are

not in the domain, they should also act reasonably on such

elements. Thus a program which realizes the function 1/x

should not fail catastrophicall y when x=0 , but Instead

should generate an error message. We call elements within

the functional domain val id Inputs and those outside the

domain 1 nval i d inputs.

The goal of testing is to reveal errors not removed

during debugging. The testing process consists of obtaining

a valid value from within the functional domain or an invalid value from outside the functional domain, determining

the expected (correct) value, running the program on the

given value, observing the program's behavior, and finally

comparing that behavior with the expected (correct)

behavior. If the comparison is successful, the result of

the testing process has revealed no errors. If the comparison is unsuccessful, then through the testing process the

errors are revealed.

The key words in the paragraph above are expec ted

( corr ec t ) behavior , observation , and compar 1 son . An important phase of testing lies in planning how to apply test

data, how to observe the results, and how to compare the

results with desired behavior. Applying and observing tests

are not always straightforward activities. Often extensive

-6-
analysis Is required to determine tests which adequately

test design components, and often code must be instrumented

to provide observation. Determining the desired (correct)

behavior for comparison with observed results is very difficult. To test a program, we must have an "oracle" to provide the correct responses and, to represent the desired

behavior. This is a major role of a requirements specification. By providing a complete description of how the system

is to respond to its environment , a good requirements

specification may form a basis for constructing such an oracle. In the future, executable requirements languages may

provide this capability directly, but currently they are

still basic research topics, consequently we must be content

with more ad hoc techniques. Some typical ones include:

1 . Int ui t i on .

2. Hand calculation.

3. Simulation, both manual and automated.

4. An alternate solution to the same problem.

Although we have been discussing testing through examples at the coding level, our intent is to be general enough

so that the discussion of the validation methods applies to

any stage in the program's life cycle. Testing in its narrowest definition is performed during the construction

stage, and then later during operation and maintenance as revisions are made. Derivation of test data and test planning, however, are activities which should cover the entire

life cycle.

If a broader meaning of testing is used, subsuming more

of the verification process, then testing is an important

activity in each life cycle stage. Simplified walkthroughs,

code reading, and most forms of requirements and design

analysis can be thought of as testing procedures. Each of

these will be discussed in later sections.

The main problem with testing is that it reveals only

the presence of errors. A complete validation of a program

can be obtained only by testing for every element of the

domain. Since this process is exhaustive, finding the presence of no errors guarantees the validity of the program.

This technique is the only dynamic analysis technique with

this guarantee. Unfortunately, it is not practical. Frequently program domains are infinite or so large as to make

the testing of each element of the domain infeasible. There

is also the problem of deriving, for an exhaustive input

set, the expected (correct) responses. Such a task is at

-7-
least as difficult as ( and possibly equivalent to) writing

the program itself. The goal of a testing methodology is to

reduce the potentially infinite exhaustive testing process

to a finite testing process. This is done by choosing

representative elements to exercise features of the problem

under solution or of the program written to solve the prob1 em .

A subset of the domain used in a testing process is

called a test data set. Thus the crux of the testing problem

is finding an adequate test data set, one that covers the

domain and yet is small enough to use. This activity must

be planned and carried out in each life cycle stage. Sample

criteria for the selection of test data for test sets Incl ud e :

1. The test data should reflect special properties of the domain such as extremal or ordering properties or singularities.

2. The test data should reflect special properties of the function that the program is supposed to

implement such as domain values leading to extremal

function values.

3. The test data should "exercise" the program

in a specific manner, e.g., causing all branches to

be executed or all statements to be executed.

The properties that the test data sets are to reflect

are classified according to whether they depend upon the

program 's Internal structure or the function the program is

to perform. In the first two cases above, the test data reflect functional properties and in the latter case structural properties. Structural testing helps to compensate for

the inability to do exhaustive functional testing.

While criteria for a test set to be adequate In a structural sense are often simple to state (such as branch

coverage), the satisfaction of those criteria can usually

only be determined by measurement. Due to the lack of

analytical methods for deriving test data to satisfy structural criteria, most structural test sets are obtained using

he ur 1 s 1 1 c s .

For functional analysis techniques, the major current

difficulties are in the specification of such vague terms as extremal or exceptional value. Further, for some functional

analysis techniques, it may not be possible to obtain a functional description from a requirement or specification

statement. Thus once again a substantial amount of effort in

-8-
test set construction for functional considerations is of a heuristic nature.

The general concepts of testing will be discussed below

as they apply to each life cycle stage. Keep in mind

throughout the discussions that planning is the key to successful testing .

4. Requirements

INVEST IN ANALYSIS AT THE

BEGINNING OF THE PROJECT

Why bother with formal requirements for a small program

written by a single programmer? The answer is that an investment in careful analysis at the very beginning of the

project can reap benefits even for the programmer working

alone. Having a clear, concise statement of the problem to

be solved will facilitate construction, communication, error

analysis, and test data generation.

should be included in the requirements or problem

The following list suggests the information that

recorded and the decisions that should be made at

in the development.

1. Functionally, what the program is to do.

2. What the input will be like such as the

f orm , r o rmat , d at a types, and units for the input.

3. The form, format, data types, and units for

the out put .

4. How exceptions, errors, and deviations are

tobehandled.

5. For scientific computations, the numerical

method or at least the required accuracy of the

so 1 ut i on .

6. The computer environment required or assumed, e.g. the machine, operating system, and implementation language.

What

St at ement ? should be

this stage

-9-
Making and recording decisions on the issues listed

above are only part of what should be done during the requirements stage of development. In addition, the core of

the test data set should be established and error analysis

should be performed.

START DEVELOPING THE TEST

SET AT THE REQUIREMENTS STAGE

The requirements state what the program is to do. Data

should be generated which will determine if the requirements

have been met. To do this the input domain should be partitioned into classes of values that the program will treat in

a similar fashion. For each class a representative element

should be included in the test data. Boundary values, elements at the edge of the input class, frequently require

special treatment by the program and are thus a likely

source of error. Therefore, boundary values for each class

should be included in the test data set. In addition, any

non-extremal input values that will require special handling

by the program should be included in the test data set. Output classes should also be covered by input which causes

output at each class boundary and within each class. Invalid input values require the same analysis provided for

valid val ue s

.

For all elements in the test data set expected values

should be determined. That is, how the program should treat

each of the elements should be decided and recorded. The

test data set and accompanying expected values form the core

of the test set that will be refined to use with the implementation code. The test set generated during the requirements stage will address the functional aspects of the program. Data to test the structural aspects will be generated

during the design and implementation stages.

Generating test data at this stage also serves another

useful purpose, that of insuring that the requirements are

testable. Requirements for which it is impossible to define

test data or to determine the expected value for the test

data are ineffective requirements and should be reformulated .

-10-
ARE YOU SOLVING THE CORRECT

PROBLEM?

Generating the test set is only part of the verification activity that should accompany the requirements stage.

Analysis for the correctness, consistency , and completeness

of the requirements should also be done. Whether the correct

problem is being solved should be considered. Perhaps a more

general solution or a more specific solution would be more

advantageous. The requirements should be carefully checked

for conflicts and inconsistencies. The possibility of missing cases should be considered. Have functions been omitted

that should have been included? Too frequently the results

of such analysis aren't obtained until the program is executed with test data. At the implementation stage the cost

of requirements modification is high and the rework is

painful. Therefore, error analysis early in the development

cycle is advocated.

5 . De s i gn

WRITE AN EXPLICIT DESIGN

STATEMENT

Even for small projects, the programmer should spend

the time and energy to produce an explicit statement of the

design, for such a document will aid construction, communication, error analysis, and test data generation. The requirements and design documents together should describe the

problem to be solved and organization of the solution. They

should convey enough information so that the reader can

determine what the program is to do and how it is to do it

without having to resort to code reading.

Several different design techniques and methodologies

have received wide coverage recently [EDP79]. Whether you

use one of those or your own technique, the following information should be included in the design.

1. Principle data structures should be specified since the way key data are organized frequently

shapes the structure of the entire program.

-11-
2. Functions, algorithms, heuristics, or special techniques used for processing should be

record ed .

3. The basic program organization should be

stated. How the program is to be sub-divided or modularized and the internal aAd external interfaces

should be specified.

4. Additional information may be needed for

particular projects.

Verification activity is very important in the design

stage. If faults are not found until after the program is

coded, fixes are often more costly and less satisfactory,

yerlflcation at the design stage follows the steps listed

in section 2

A. The design should be analyzed to determine

if it is complete and consistent. The individual algorithms, heuristics, and special techniques should

be checked to see if they really work for the given

problem and data. This could involve hand calculations for representative test cases. The total process should be analyzed to determine that no steps

or special cases have been overlooked. The module

interfaces should be examined to assure that calling

routines provide the information and environment required by the called routines and in the form, format, and units assumed. The data structure should

be examined for inconsistencies or awkwardness.

Input/output handling should be carefully analyzed

for it is a frequent source of error.

B. The design should be analyzed to determine

if it satisfies the requirements. Determine if all

constraints specified by the requirements have been

met. Determine if the design assumes the same form,

format and units for input and output that are stated in the requirements. Check that all functions

listed in the requirements have been included in the

design. Selected test data generated during the requirements should be hand simulated to determine if

the design would produce the expected values.

C. Test data based upon the design should be

g ene ra t ed . Dur i ng the design stage data structures,

functions, algorithms, heuristics, and the general

program structure have all been established; data to

test these structures and function^ should also be

generated. Standard, extremal, and special values

-12-
for the data structures should be Included in the

test data set. Boundary value analysis should be applied to both the structure and the values of the

data structures. For example, if array size can

vary, then a single element array, a maximum size

array, and special valued arrays should be candidates for the test data set. Test data for externally visible functions has been generated at the requirements stage. For the internal functions introduced during design, test data should also be generated. The input and output analysis suggested in

Section 4 should be used to generate the test data

for these functions. If not already accomplished by

the existing test data, new tests should be generated to exercise the modular structure of the design.

For all the data in the test data set, expected

values should be calculated. The test data generated during the design stage should test both the

structure and the internal functions of the design.

D. The test set generated during the requirements stage should be re-examined in view of the

design. Since additional decisions have been made

during design, it is possible that data and expected

values generated during requirements can be refined

and made more exact.

Many programmers and managers want to rush directly to

the coding stage when they begin a new project. However, the

time spent in careful analysis during the first two life cycle stages can increase the quality of the total project.

Following the above four steps will greatly facilitate program verification. Steps one and two should also be carried

out by a colleague; specific techniques will be discussed in

Section 6. It is so difficult to find your own errors that

an independent analysis is strongly advocated.

6. Construction

The construction or coding stage is what most people

think of when they think of programming. However, if the requirements and design have been carefully done, the coding

should be straightforward, almost mechanical. Since so much

has been written about software engineering, structured programming, and various coding techniques, little will be said

here except that we assume the programmer is using good programming techniques [ZELK79].

-13-
CHECK FOR CONSISTENCY

WITH DESIGN

The first step in verification during the construction

stage is to determine if the code is consistent with the

design. Both code and design should exhibit the same modular

structure and have the same module interfaces. Both should

utilize the same data structures and implement the same

functions using the same algorithms. Input/output handling

in the code should be consistent with the decisions made

during the design stage.

KEEP YOUR TESTS

Testing should be performed in an organized and systematic manner. Test runs should be dated, annotated, and

saved. Not infrequently testing is slow and ineffective because it is performed in a random manner. The programmer

manufactures test data on the spot and runs tests as the

spirit moves him using his memory as the only record of what

has been previously tested. Such random testing will produce

random results. The systematic development of the test set

through the requirements, design, and construction stages

helps to produce an adequate test set; however, the actual

execution of the program using the test data must also be

performed in an orderly manner. A plan or schedule of which

code pieces or modules are to be tested and in what order

can be used as a check list to help the programmer organize

his efforts. All test data and runs should be saved after

being dated and suitably annotated. If errors are found and

changes made to the program, retesting must be performed.

Not only must the given test be rerun, but also any tests

previously run and passed that involve the erroneous segment

must be rerun since the program modifications may have invalidated the previous tests.

ASK A COLLEAGUE

FOR ASSISTANCE

During the construction stage, code exists and testing

can begin. However, additional manual analysis of the code

should precede the first test runs. Desk checking, in which

a programmer sits at a desk reading his code, looking for

errors, is not a particularly effective verification

-14-
technique. Usually programmers are poor at finding their own

errors. Fundamental logic errors and missing cases elude

the creat or / pr og rammer for if it seemed right when it was

designed, it still seems right. As for syntactic errors, the

programmer tends to see what was meant rather than what was

c od ed .Inspection, an exercise in disciplined error hunting,

and wal k-through ,a form of manual simulation, are formalized

manual techniques based upon desk checking. In both techniques a team of programmers examine the code (or design or requirements) and look for errors in a very organized

manne r .

For small programs, a technique partway between desk

checking and inspections or wal k- throughs seems appropriate.

An independent party, usually a colleague, should be asked

to analyze the development product at each stage, the requirements, the design, and the code. The programmer should

explain the product to his colleague, while the colleague

plays devil's advocate, questioning the logic and searching

for errors. A check list of likely errors should be used to

guide the search. The second party aspect of this technique

is essential to its success for a new perspective is needed

to locate the errors the programmer cannot perceive.

USE AVAILABLE TOOLS

At last the code is ready to be run. The programmer

should be familiar with the various compilers and interpreters available on his system for the language he is using. If more than one exists, they undoubtedly differ in

their error analysis and code generation capabilities. Some

processors do syntax checking only with no code generation;

others perform extensive error checking such as array bound

checking and provide aids such as cross reference tables.

If debugging compilers exist on your system, it is very

helpful to use them.

APPLY STRESS TO THE PROGRAM

Testing should exercise and stress the program structure, the data structures, the internal functions, and the

externally visible functions or functionality. Both valid

and invalid data should be in the test set. The test set,

which consists of test data and expected values generated

during the requirements and design stages, forms the core of

-15-
the test set to be used during construction. Additional

data may be required to test structural and functional details visible only in the code. The test set generated during the first two life cycle stages may require refinement

or redefinition in order to be applied to the code. The test

data should be organized to conform with the general test

organization to be used during construction. Intermediate

values may be required in order to test Incomplete pieces of

code or individual modules. Testing requires as much

creativity as does design.

TEST ONE AT A TIME

As with many tasks, divide and conquer is the rule for

testing. Pieces of code, individual modules, and small collections of modules are exercised separately before they are

integrated Into the total program. Only after the pieces

have been found error-free are they joined together, one at

a time, and tested as a unit. It is easier to Isolate errors

when the number of potential Interactions is kept small.

In order to test the smaller units of code, some additional code may be required. If the testing is done bottomup, then drivers will need to be written. For small programs

this may only entail producing code to call a procedure so the Interface and control transfer can be tested. If construction is proceeding top-down, then stubs will be needed.

In this case incomplete or dummy called routines must be

constructed so the flow of control and argument passage can

be tested before the entire program has been constructed.

Often there is a reluctance with small programs to want to

generate any "unnecessary" code solely for testing. However,

it is wise to organize the testing so that small pieces of

code are exercised and deemed error-free before aggregating

them into ever larger units.

Instrumentation, the insertion of code into the program

solely to measure various program characteristics, can be

useful for program verification. For medium and large scale

projects tools are often acquired or developed which will do

automatic instrumentation. For small projects the programmer

can do his own instrumentation. Array bound checks, checking

of loop control variables, determining if key data values

are within permissible ranges, tracing the execution, and

counting the number of times a group of statements is executed are examples of the types of analysis that can be performed using instrumentation.

-1 6-
ARE YOU EVER THROUGH?

How do you know when you have tested enough? That's a fundamental question that unfortunately has no clear cut

answer. If you are still finding errors everytime you execute your program, then testing should continue. As a matter

of fact, errors tend to cluster, so those modules that appear particularly error prone should receive special scrutiny. If you have run your complete test set against the

program and have found no more errors, it does not mean that

your program is error free. Perhaps your test set is incomplete. The metrics that tend to be used to measure testing

thoroughness include: statement testing, branch testing, and

path testing. Statement testing determines if each statement

in the program has been executed at least once. Branch testing determines if each exit from each branch in the program

has been executed at least once. Path testing determines if

all logical paths through the program, which may involve repeated execution of various segments, have been executed at

least once. Each succeeding metric subsumes the others.

Since the number of paths grows exponentially with the

number of decision points, path testing tends to be too

costly in time and money to utilize and often impossible to

do. Statement testing , although known to be theoretically

insufficient, is the coverage metric most frequently used

because it is relatively simple to Implement.

If no dynamic analysis tool that measures test coverag-e

is available on your system, it is a straight forward exercise to instrument your own program to calculate statement

coverage. Identify each program point into which control can

be transferred and establish an array with as many slots as there are transfer points. At each transfer point insert a statement which will increment the appropriate slot in the

array. The final values in the array can be printed at program exit. This technique will not only provide an indication of test coverage but will also show the portions of

your program with the heaviest usage. Statement testing will

not guarantee your program is correct; however, it is a testing minimum that is frequently used for if code has never been exercised, it is difficult to know if it is error

f r ee .

It should be emphasized that the amount of testing will

depend upon the cost of an error. Critical programs or code

segments will require more thorough testing' than more insignificant functions do.

-17-
7 . Operati on

Why talk about testing during operation? For many production programs 50 to 85% of the total life cycle costs are

accrued during the maintenance stage that is coincident with

operation. These costs do not imply error studded programs

that take forever to fix but evolving programs that are constantly undergoing modification. Even for small programs

corrections, modifications, and extensions are bound to occur. Any time there is modification or change, testing is

required. Testing during maintenance is termed regression

testing. The systematic approach recommended in the rest of

the report facilitates regression testing since much of the

work should already have been done. The test set, test plan,

and test results for the original program should exist.

Modification to accommodate the program changes must be done

and then all portions of the program affected by the modifications must be retested. After regression testing is complete, the program and test documentation must be updated to

reflect the changes. To ignore the need to maintain consistent and current documentation on both programs and completed tests is to insure increasing instability of the programs at each successive modification.

8. Summary and General Rules

We have proposed a general approach to developing

software in an environment with limited resources. This approach stresses that verification must take place throughout

the development process. Even for relatively small, noncritical projects lifecycle planning for software quality is

very important. A programmer's task of demonstrating that he

has produced reliable and consistent code can be much simplified by beginning early to develop and plan verification

activities.

The approach we recommend relies heavily on testing as the main verification technique with code reading and inspection techniques employed as supporting activities. Testing cannot be performed as an after-the-fact activity. Test

data sets are derived throughout the development process beginning at the requirements stage. It is a*- the first stage

that test data can be derived from functional analysis of

the system requirements. Inconsistency in the requirements

is often detected during this analysis. During the design

stage, test data which stress the program control and data

structures are generated. When the final code generation

and construction stage begins, the test data set should be

nearly complete. The remaining test data should be chosen to

-18-
exercise those "special functions" used by the programmer in

the actual implementation. Care should be taken to insure

that the data and control structures represented by the final programs are covered as extensively as possible by the

test data.

The actual testing should proceed in an organized

manner with small pieces being tested individually, then aggregated and retested. Test coverage metrics are very useful

for determining a "confidence level" for the test data. Such

metrics can be implemented by instrumenting your own code.

Since testing is a process aimed at discovering errors, it

must be noted that for each design or code modification

resulting from such a discovery, retesting is necessary. The

process becomes an iterative one towards a goal of achieving

a high level of confidence in the finished product through

intelligent testing.

Inspection, close reading and analysis of the code, and

manual simulation are important verification techniques

which should also be used throughout development. Thorough

analysis and hand simulation are employed during both requirements and design in order to discover errors early in

the development. Each stage must be analyzed for consistency with prior stages and for internal consistency. You

should seek independent review of your work by having a colleague Inspect your design and code for errors. We believe

that quality can be improved through planning, a staged

development, and the use of sound verification techniques at

eachstage.

The following list summarizes the approach presented in

this report.

1. Generate test data at all stages and in particular the early stages.

2. Develop a means for calculating the expected

values for test data to compare with test results.

3. Inspect requirements, design, and code for

errors and for consistency.

4. Be systematic in your approach to testing.

5. Test pieces and then aggregate.

6. Save, organize, and annotate test runs.

-19-
7. Concentrate testing on modules that exhibit

the most errors and on their interfaces.

8. Re test when modifications are made.

9. Discover and use available tools on your

sys t em

.

-20-
References

[ADRI 80]

[DOD77 ]

'EDP79

]

[NBS76 ]

[ZELK79]

ADRION, W. R. ; BRANSTAD, M. A.; and CHERNIAVSKY,

J. C, forthcoming National Bureau of Standards,

Institute for Computer Science and Technology

Special Publication, Veri f i cat ion and Val idat ion , 1980 . Department of Defense, Automat ed Data Sy st ems

Documentation Standards , Standard 7935 . 1-S, September 1 977 . "Program Design Techniques," EDP ANALYZER, Vol.

17 No. 3, Canning Publ icat ions , Inc . , March 1979 . National Bureau of Standards, Guid el i ne s for

Documentation of Com put e r Programs and Aut omat ed

Data S y s t em

, Federal Information Processing

Standards Pub 1 ic at i on 3 8 , February 1 976 . ZELKOWITZ, M. V., "Perspectives on Software Engineering," ACM Comput i ng Surveys , Vol. 10 No. 2 (June 1978), 197-216.

-21-
Bl bl i ography

This collection is meant to provide the reader with an entry

into the field of verification, validation, and testing.

Each document lists further references and an annotated bibliograghy on validation appears in [YEH77].

[GOOD75] GOODENOUGH, J. B.; and GERHART, S., "Toward a Theory of Test Data Selection," IEEE Transacti ons

on Software Eng i nee r i ng 1,2 (June 1 975 ) , 156-173

.

[HETZ73] HETZEL, W. C. (Ed.), Program Test Methods , Prentice-Hall, Engelwood Cliffs, N.J., 1973.

[KERN78] KERNIGHAN, B. W.; and PLAUGER, P. J., The

E 1 em ent s of Pr ogrammi ng St yl

e

, McGraw-Hill, New

York, 1978.

[MILL78] MILLER, E.; and HOWDEN, W. E., Tutorial : S o f t wa r e Testing and Validation Techniques , IEEE Computer

Society, Long Beach, CA , 1978.

[MYER79] MYERS, G. J., The Art of Software Testing , John

Wiley & Sons, New York, 1979.

[YEH77] YEH, R. T. (Ed.), Current Trends in Programming

Methodology Vol. 2, Pr ent i c e-Ha 1 1 , Eng el wood

Cliffs, N.J., 1977.

-22-
NBS-114A IREV. 9-78)

U.S. DEPT. OF COMM. 1. PUBLICATION OR REPORT NO. :2.Gov*t, Abcesaion No. 3. R^cifiient's Acc«ssi(ori Ho. M,

4

Mini l/\/*DADLII^ r\ AT K BIBLIOGRArnH- UA I A SHEET

SP 500-56

4. TITLE AND SUBTITLE

"computer science and technology

Validation, Verification, and Testing for the

Individual Progrannner

5. Publication Date February 1980

(. Ferfeimins Organization Co<]«

7. AUTHOR{S)

Martha A, Brans tad, John C, Cherniavsky, & W, Richards Adrion

8. Performing Organ. Report No.

9. PERFORMING ORGANIZATION NAME AND ADDRESS

NATIONAL BUREAU OF STANDARDS

DEPARTMENT OF COMMERCE

WASHINGTON, DC 20234

10. Project/Task/Work Unit No.

11. Contract/Grant No.

ZZ. SPONSOKmb UKbANI^A 1 lUN INAIVit AIMU L/UIVIrLt 1 t AUUntoS (Street, City, State, ZIP)

Same as item 9

13. Type of Report & Period Covered Final

^ ^.l^-j^My^h^^ ^^>., .

*

15. SUPPLEMENTARY NOTES

Library of Congress Catalog Card Number: 80-600005

I I Document describes a computer program; SF-185, PIPS Software Summary, is attached.

16. ABSTRACT (A 200-word or less factual summary of most significant information. If document includes a significant bibliography or

literature survey, mention it here.)

Guidelines are given for program testing and verification to insure quality

software for the programmer working alone in a computing environment with limited

resources. The emphasis is on verification as an integral part of the software

development. Guidance includes developing and planning testing as well as the

application of other verification techniques at each lifecycle stage. Relying

upon neither automated tools nor formal quality assurance support, the guidelines

should be appropriate for applications programmers doing small development projects.

17. KEY WORDS (six to twelve entries; alphabetical order; capitalize only the first letter of the first key word unless a proper name;

separated by semicolons)

Program verification; software development; testing.

18. AVAILABILITY [x] Unlimited

1 1 For Official Distribution. Do Not Release to NTIS H Order From Sup. of Doc, U.S. Government Printing Office, Washington, DC

20402, SD Stock No. SN003-003' -00^-07 1 5Q-8

Order From National Technical Information Service (NTIS), Springfield, VA. 22161

19. SECURITY CLASS

(THIS REPORT)

UNCLASSIFIED

21. NO. OF

PRINTED PAGES

26

20. SECURITY CLASS

(THIS PAGE)

UNCLASSIFIED

22. Price

Price $1.75

USCOMM-DC
ANNOUNCEMENT OF NEW PUBLICATIONS ON

COMPUTER SCIENCE & TECHNOLOGY

Superintendent of Documents,

Government Printing Office,

Washington, D. C. 20402

Dear Sir:

Please add my name to the announcement list of new publications to be issued in the series: National Bureau of Standards Special Publication 500-.

Name

COmpanv

Address ,

City State Zip Code

(Notification key N-503)

ft u s, GOVERNMENT PRINTING OFFICE; 1980 - 311-04 6 /7



I

}!iI
NBS TECHNICAL PUBLICATIONS

PERIODICALS

JOURNAL OF RESEARCH—The Journal of Research of the National Bureau of Standards reports NBS research and develop- ment in those disciplines of the physical and engineering sciences in which the Bureau is active. These include physics, chemistry,

engineering, mathematics, and computer sciences. Papers cover a broad range of subjects, with major emphasis on measurement

methodology and the basic technology underlying standardization. Also included from time to time are survey articles on topics

closely related to the Bureau's technical and scientific programs. As a special service to subscribers each issue contains complete

citations to all recent Bureau publications in both NBS and non- NBS media. Issued six times a year. Annual subscription: domestic

$17; foreign $21.25. Single copy, $3 domestic; $3.75 foreign. NOTE; The Journal was formerly published in two sections; Section A "Physics and Chemistry" and Section B "Mathematical

Sciences." DIMENSIONS/NBS—This monthly magazine is published to in- form scientists, engineers, business and industry leaders, teachers,

students, and consumers of the latest advances in science and

technology, with primary emphasis on work at NBS. The magazine

highlights and reviews such issues as energy research, fire protection, building technology, metric conversion, pollution abatement,

health and safety, and consumer product performance. In addition, it reports the results of Bureau programs in measurement

standards and techniques, properties of matter and materials, engineering standards and services, instrumentation, and

automatic data processing. Annual subscription: domestic $11;

foreign $13.75. NONPERIODICALS

Monographs—Major contributions to the technical literature on

various subjects related to the Bureau's scientific and technical activities. Handbooks—Recommended codes of engineering and industrial practice (including safety codes) developed in cooperation with in- terested industries, professional organizations, and regulatory

bodies. Special Publications—Include proceedings of conferences sponsored by NBS, NBS annual reports, and other special publications

appropriate to this grouping such as wall charts, pocket cards, and

bibliographies. Applied Mathematics Series—Mathematical tables, manuals, and

studies of special interest to physicists, engineers, chemists,

biologists, mathematicians, computer programmers, and others engaged in scientific and technical work.

National Standard Reference Data Series—Provides quantitative data on the physical and chemical properties of materials, compiled from the world's literature and critically evaluated. Developed under a worldwide program coordinated by NBS under

the authority of the National Standard Data Act (Public Law

90-396).

NOTE: The principal publication outlet for the foregoing data is the Journal of Physical and Chemical Reference Data (JPCRD)

published quarterly for NBS by the American Chemical Society

(ACS) and the American Institute of Physics (AIP), Subscriptions,

reprints, and supplements available from ACS, 1 155 Sixteenth St., NW, Washington, DC 20056.

Building Science Series—Disseminates technical information developed at the Bureau on building materials, components,

systems, and whole structures. The series presents research results,

test methods, and performance criteria related to the structural and

environmental functions and the durability and safety characteristics of building elements and systems.

Technical Notes—Studies or reports which are complete in themselves but restrictive in their treatment of a subject. Analogous to monographs but not so comprehensive in scope or definitive in treatment of the subject area. Often serve as a vehicle for final reports of work performed at NBS under the sponsorship of other government agencies.

Voluntary Product Standards—Developed under procedures

published by the Department of Commerce in Part 10, Title 15, of

the Code of Federal Regulations. The standards establish nationally recognized requirements for products, and provide all concerned interests with a basis for common understanding of the

characteristics of the products. NBS administers this program as a supplement to the activities of the private sector standardizing

organizations. Consumer Information Series—Practical information, based on NBS research and experience, covering areas of interest to the con- sumer. Easily understandable language and illustrations provide

useful background knowledge for shopping in today's tech- nological marketplace. Order the above NBS publications from: Superintendent of Documents. Government Printing Office. Washington, DC 20402. Order the following NBS publications—FIPS and NBSlR's—from

the National Technical Information Services. Springfield. VA 22161.

Federal Information Processing Standards Publications (FIPS

PUB)—Publications in this series collectively constitute the Federal Information Processing Standards Register. The Register

serves as the official source of information in the Federal Govern- ment regarding standards issued by NBS pursuant to the Federal Property and Administrative Services Act of 1949 as amended.

Public Law 89-306 (79 Stat. 1127), and as implemented by Executive Order 11717(38 FR 12315, dated May II, 1973) and Part 6 of Title 15 CFR (Code of Federal Regulations).

NBS Interagency Reports (NBSIR)—A special series of interim or

final reports on work performed by NBS for outside sponsors

(both government and non-government). In general, initial dis- tribution is handled by the sponsor; public distribution is by the National Technical Information Services, Springfield, VA 22161,

in paper copy or microfiche form.

BIBLIOGRAPHIC SUBSCRIPTION SERVICES

The following current-awareness and literature-survey bibliographies

are issued periodically by the Bureau:

Cryogenic Data Center Current Awareness Service. A literature sur- vey issued biweekly. Annual subscription: domestic $25; foreign

$30. Liquefied Natural Gas. A literature survey issued quarterly. Annual

subscription; $20.

Superconducting Devices and Materials. A literature survey issued

quarterly. Annual subscription: $30. Please send subscription or- ders and remittances for the preceding bibliographic services to the National Bureau of Standards, Cryogenic Data Center (736) Boulder, CO 80303.
U.S. DEPARTMEMT OF COMMERCE

National Bureau of Standards

Washington. D.C. 20234

OFFICIAL BUSINESS

Penalty for Private Use. $300

POSTAGE AND FEES PAID

U.S. DEPARTMENT OF COMMERCE

COM-2 1 5

SPECIAL FOURTH-CLASS RATE

BOOK