Download Asset User Manual

'/',?' ii'"-*f''3f5H.^"fFJ(
Science
Computer
TECHNICAL
Sif"Vitll^ lItI5-J*W
";
Department
REPORT
ASSET
User
Manual
PhyllisFrankI
Technical
Report
October
NEW
YORK
Department
Courant
251
,,
318
1987
UNIVERSITY
of
Computer
Science
Institute of Mathematical
MERCER
STREET,
NEW
J
YORK,
Sciences
N.Y.
10012
Manual
User
ASSET
Phyllis
Technical
FrankI
318
Report
October
1987
ASSET
USER
MANUAL
1, 1987
October
Phyllis Frank!
of
Depamneni
Courani
New
York
251
New
1.
University
Street
Mercer
New
York,
Sciences
10012
York
INTRODUCTION
ASSET
tool
The
the
that
and
the
the
which
which
it
user
flow
testing,see
the
session.
software
the
on
the
testing
of
set
a
program,
program
data
test
criterion
given
an
that
4
by
describes
a
Section
the
test
and
but
not
or
select
can
individual
the
the
as
reader
in section
ASSET.
the
gives
refer
some
familiaritywith
To
Section
of
references
the
acquire
2 of
ASSET
program.
to
the
relevant
the
the
flow
main
of
analysis
theory
gives
papers.
the
imponant
Section
6
or
program
defines
most
commands.
Section
quately
ade-
of
data
familiaritywith
some
this manual
3 describes
has
been
continue.
data
subject procedure.
has
7.
The
test
and
criterion
function,
to
of the
Section
rest
will
the
and
(procedure,
We
data
test
it has
that
criterion
another
"subject program".
analysis
and
correctly
user
all of the
on
additional
certifying
subprogram
"subject procedure".
separately compiled
7
behaved
behaved
the
output,
correctly
selects
user
has
program
wrong
behaved
program,
operating system.
references
on
has
program
is part
UNTX
has
the
the
computed
program
release
criterion,
the
whether
satisfied, the
been
not
testing
call
the
Section
ASSET
Pascal
a
the
runs
interactive
an
required by
program
If the
If the
accepted
ASSET
the
intra-procedural
with
programs
commands.
It
determine
to
output
If
bug.
the
assumes
and
criteria.
is
input
as
associations
either
to
for
is
manual
use
has
subject procedure
testing
to
a
can
we'll
performs
This
how
criterion
is used
flow
on
has
according
which
the
the
specification.
the
tested
ASSET
examines
testingprocess.
satisfied
program)
testing
definition-use
program
if the
continues
flow
data
Tests)
It takes
data.
then
its
to
Evaluate
and
testing [1,2,3,4].
those
test
user
according
cases,
the
Select
to
flow
list of
a
by
been
of
one
produces
reports
data
on
and
covered
System
(A
based
data,
how
Science
Computer
of Mathematical
Institute
5
tions
restric-
ASSET
describes
example
an
Appendix
data
of
an
I describes
install ASSET.
to
Acknowledgements:
The
earlier
graphics facility was
version
by Ernie
of
ASSET.
Campbell.
The
written
by Stewart
user-interface
was
Weiss,
who
translated
also
from
helped
csh
to
C
implement
and
enhanced
an
Disclaimer:
ASSET
in
is still a "work
progress". We
as
the tool could
how
to
send e-mail
LANGUAGE
2. THE
improved
be
frankl(5)csd2. nyu.edu and
to
ACCEPTED
to
[email protected].
ASSET
ASSET
correct
accepts syntactically
programs
which
do not include
Pascal consistingof programs
and
1. goto statements
2. functions with
var
vouch
not
find any
would
we
BY
for its reliability
nor
are
we
bugs, or have other suggestions
appreciatehearing from you. Please
do
if you
responsiblefor maintaining it. However,
written in the subset of (level0) ISO
of the following constructs:
any
labels.
parameters.
3. variant records
4. with
statements
5. procedural or functional parameters
6. forward
declarations
7. conformant
identifiers
following
The
therefore should
not
are
arrays
used in the modified
in the
be used
version
of the subject program
ASSET
and
and
subjectprogram:
FW
traversed
The
following identifiers
used
file names
as
are
in the
used
as
file
by
names
therefore should
not
be
subjectprogram:
IncFiles, StringTabFile,SymTabPile, anomalies, a.out, comp.msgs,
copy,
copy2, copy2.p, defuse, display, globdecs, graph,
copy. exec,
copy.p,
mainfile, mainfile2, pairs,paths, picfile,
record, results,
listing,
junkfile,
results.old,subject,traversed
It is recommended
order
to
insure
that the
that it is
user
compile the
correct.
syntactically
In addition, ASSET
standard
accepts certain Berkeley Pascal
submitting it to
which
constructs
are
ASSET
in
part of
not
Pascal, including separate compilation(see section 5).
ASSET
For
before
program
places certain arbitraryrestrictions on the size of the program.
Specifically,
300
of variables visible to subjectprocedure "=
number
of procedures and functions visible to subjectprocedure "= 3(X)
number
number
of types visible to subjectprocedure "= 3(X)
of constants
visible to subjectprocedure "=
300
number
number
of identifiersvisible to subjectprocedure "= 500
length of each identifier "= 80
total number
of characters in all identifiers visible to subjectprocedure"= 3000
number
of basic blocks in subject
procedure "= 100
instructions
on
how
to
increase these limits,see
Appendix
I.
BUGS:
I.
ASSET
For
requires that
example, the
case
the last statement
in
a
b of
true:
writeln('hello');
false: writeln('goodbye')
end
will be
rejectedby ASSET,
case
b of
case
correct) program
(syntactically
but
statement
be
fragment
followed
by
a
colon.
semi-
-3-
writeln('hello');
true:
false:
\\Titeln('goodbye');
end
will be
The
accepted.
check
should
user
that all
beforesubmittingthe
program
translates for
2. ASSET
in the
statements
case
subjectprocedure are
of this form
ASSET.
to
If a
loopsincorrectly:
"fori :=el
statement
of the form
toe2doS"
appears in the subjectprocedure,in writingthe modified
translate this to a code fragment functionally
equivalentto
subjectprocedure ASSET
will
i:=el;
if i " e2 then goto "label2"
"labell":
S;
i
succ(i);
:=
goto "label 1 ";
"label2":
next
It should
translate it to
statement;
a
fragment functionally
equivalentto
i:=el;
tmp
:=e2;
"labell":
if i
tmp then gof^ "label2"
"
S;
i
succ(i);
:=
goto "labell";
"label2":
next
statement;
Thus, if any variable
occurringin expressionis modified within the statement
the modified
legal,though poor programming practice),
subjectprogram
the
equivalentto
subjectprogram.
These
bugs
3. THE
will be corrected
MOST
IMPORTANT
In this section
in
order in which
an
in the next
between
relationship
we
they can
be
COMMANDS
the basic ASSET
The
be executed.
the commands.
not
version of ASSET.
ASSET
describe
S (which is
will
Additional
commands.
section ends
commands
The
with
are
commands
some
comments
described in the
listed
are
on
next
the
tion.
sec-
Invoking ASSET
We
will refer to the
directory".Before
contains
The
the
source
directoryfrom
of the program
type "asset" in
Welcome
ASSET
is invoked
as
the "current working
you should set up a "subjectdirectory"which
ject
to be tested. It is usuallyconvenient
to have the sub-
of
directorybe a subdirectoryshould not be
subjectdirectory
ASSET
which
invokingASSET
but this is not necessary.
working directory,
as the current
working directory.To enter
will respond with
prompt. ASSET
response to the UNIX
For help type "help."
to ASSET.
current
the
same
Enter relative pathname of initialdefault directory.":
At this
current
pointyou
should
enter
working directory.ASSET
the
pathname of the subjectdirectory,relative to the
"command
level prompt".
printthe ASSET
will then
-4-
that it is ready to accept
", signifying
""":
We
describe
now
of the ASSET
each
types the command
for additional information.
ASSET
when
user
command.
a
commands.
These
commands
of these commands
level prompt. Some
ASSET
will prompt
When
this occurs,
". Sometimes
"":
prompt",
should
The
will ask the
will query the
the user
with its
has a yes
a question which
for
and
"N"
"n"
for no.
or
or
user
no
answer.
"y"
respond
or
yes
If
default
is
"Y"
in
brackets.
the
will
the
there
then
default (if
is one)
ASSET
indicate
"inner
ASSET
be invoked
can
with
user
"Y"
to be "Y".
response which does not begin with "N" or "n" will be considered
which
does
not begin with "Y"
Similarly,if the default is "N" then any non-null response
If
hits
the user just
or "y" will be considered to be "N".
carriagereturn, the inner prompt
any
non-null
will continue
ASSET
is given. The logicaldependence of
apf"ear until a non-null response
be typed in lower case
is given in Figure 1. The commands
must
to
commands
letters. Any command
be abbreviated
can
by
its firstthree letters.
begin
The "begin" command
analyzes the subjectprocedure,breaking it into basic blocks,
constructingits flow graph, and determining the blocks in which each variable has
each variable has p-uses. An adjacency
and the edges on which
definitions and c-uses
list for the graph is written to the file"graph",and a representation
of the data-flow information
is written
the file "defuse". The
to
the identifiersappearing in the
In addition, ASSET
probes
have
been
constructs
inserted.
"StringTable"
That
a
in which
modified version
of the
resultingprogram
as
version of the modified
pretty-printed
ASSET
also creates
program)
program) which
When
and
return
no
are
also inserted. We
subjectprogram". ASSET
to the file"copy.p".
writes
a
files"copy", "copy2" (preliminaryversions of the modified subject
type
will
ASSET
"begin",
name
of
file of this name
to
subject
program
i, the statement
file"traversed",the constant
of the Symbol table for the subject
"SymTabFile" (a representation
be used by subsequentcommands,
but may be useful for debugging-
Enter
and
the "modified
in which
block
will not
you
If there is
has recorded
subjectprogram
is, at the beginningof basic
"writeln(traversed,i
:FW);" is inserted. Declarations of the text
"FW", and any labels which appear in the modified program
will refer to the
ASSET
is written to the file"StringTabFile".
subjectprogram
the command
respond with
subjectprocedure file. ":
in the subjectdirectoryASSET
level.
ASSET
Otherwise
will
will copy
printan error message
the file to the file "subject",
then say
SeparateCompilation?(Y/N)[N] ":
We
will
is separatelycompiled, "n" otherwise.
"y" if the subject program
is NOT
assume
throughout the rest of this section that the subjectprogram
separately
on
separatelycompiled procompiled. See section 5 for insthictions on using ASSET
grams.
Answer
of the procedure to be instrumented for ing.
will ask you for the name
testof the procedure,or direct ASSET
to prompt
supply the name
you
of the procedures in the program.
Next, ASSET
You
with the
may
names
either
select
The
one
"select" command
of the data flow
causes
testingcriteria.
ASSET
to
printa
menu
and
query
the
user
to
select
find-associations
command
This
ASSET
causes
appropriatetype) in
the
writes
find-associations
produce
to
worst
(of
subject procedure. If the selected criterion is All-du-paths,
list of all of the du-paths in the subject procedure to the file
the
a
writes
"paths". Otherwise, find-associations
associations
and definition-p-use
that in the
list of all definition-use associations
a
findingall
case,
list of all of the definition-c-use
a
in the
of
subjectprocedure
take
du-paths may
the
tions
associa-
the file
to
"pairs". Note
exponential in the
time
of basic blocks.
number
compile
code
executable
The
generated by
messages
invokes
command
"compile"
The
program.
the
the Pascal
is written
compiler to compile the modified
"copy.exec". Warning and
the file "comp.msgs".
ject
subError
the file
to
written
compiler
are
executes
the modified
to
run
The
adds
the program
with
respond
may
command
"run"
and
cases
trace
already exists. Type
File 'traversed'
otherwise.
Type
"Y"
if you
one, "N
current
on
want
or
one
test
more
type "run", ASSET
you
if you
'Y'
If you
append
to
generated by previous
traces
answer
ASSET
no,
(i.e.the program
of
traces
previous
takes
whether
will ask
test
test
whether
will ask you
the program
you
if the subject program
reads
ASSET
Next,
the program
add
otherwise.
the old file "traversed"
save
When
to
it,'N'
":
to
want
'
subject program,
the file "traversed".
to
to
the
want
to
cases
you
cases).
line
command
input from
the
yes
if
like
redirect
the
standard
mechanism
would
to
or
input or
Berkeley
argv
you
will prompt
If you answer
redirection mechanism.
yes, ASSET
output using the UNIX
For example supplying
line arguments.
you for the command
Answer
arguments.
command
via
line arguments
Pascal
"infile "outfile
as
will cause
the modified
line argument
dard
to read its stansubject program
standard
the
the file "infile" and write its
file"outfile".
output to
the command
inputfrom
ASSET
will then
say
modified
Executing
run
the program
line
to
answer
the
no,
Note
each
which
traces
ASSET
that
test
and
arguments
is
trace
of
the
data.
execute
to
you
yes, ASSET
The
written
to
new
like to
will again ask you for
will be
trace
program
the file "traversed".
If you
for
not
one
subject program,
contain
a
trace
single program
may
subjectprocedure. If the subjectprocedure
of the
run
Thus
subject procedure.
the entry to the exit of the
these paths will be "nested" within
is recursive
line arguments
whether
you would
level.
for each
paths from
you've
the command
If you answer
the program.
the command
produced
...
will ask
previously been
have
will return
one
invocation
several
additional
on
command
added
terminates, ASSET
execution
When
supplied.
subjectprogram
with
subjectprogram
the modified
will execute
then
one
another.
check
The
data
"check"
whose
list of those
command
program
def-use
traces
checks
are
whether
the selected criterion is satisfied by the test
in the file "traversed".
associations
which
are
ASSET
required by
writes
to
the criterion
the file "results"
but
have
not
been
a
-6-
by the
covered
"results"
doing this,ASSET
data. (Before
test
the file "results.old".This
to
allows
the
user
additions
the most
recent
eliminated by
If the file "traversed"
"diffresults results.old").
were
to
the old version
moves
to
which
easily
see
the test set
does
not
of the file
def-use
by using the
exist,ASSET
mand
com-
initializes it
"results" will contain
In this case,
traces.
represent an empty set of program
criterion.
the
allof the def-use associations required
by
to
tions
associa-
UNIX
a
list of
save
"save" command
The
the files"subject",
"copy.p","copy .exec","traversed",
moves
from
"defuse", etc.
"results","pairs",
"paths",
working directoryto
the current
the subject
directory.
exit
importantfiles to
Moves
Note
the rest, then exits.
removes
the commands
relationshipbetween
the
on
subjectdirectoryand
the
a set of test data satisfiesany of the criteria All-defs,AllBefore checking
All-uses
it is
or
All-c-uses, AU-c-uses/some-p-uses, AU-p-uses/some-c-uses
p-uses,
in
associations
file
the
Ust
for ASSET
of definition-use
to create
a
"pairs".
necessary
whether
^
Before checking whether
for ASSET
to create
before
once
once
Suppose
another
to
the
sary
neces-
most
the file "pairs".
mand
com-
of program
close T comes
traces
to
(to select the
the program
ASSET
with the criterion
on
C
satisfying
new
test set
du-paths.
then decides to switch to
the program has justbeen run
in the file "traversed" corresponds to test set T).
Let T be the set of test data
set
how
to run
4. OTHER
creates
criterion C
attemptingto satisfy
has been
user
criterion" command
necessary
the "find-associations" command
the fb-sttime
before the firsttime that "check" is invoked
that
see
the
listof du-paths in the file "paths".When
it is necessary
the "find-associations" command
to use
that "check" is invoked with one of the criteria involving
C.
criterion,
(i.e.assume
Then
itis
data satisfiesthe criterion All-du-paths
the file "paths".Thus
creates
"pairs"and
a
All-uses
or
test
recendy selected criterion is All-du-pathsthe "find-associations"
the most
When
of
set
recently
All-pAll-defs, All-p-uses,All-c-uses, All-c-uses/some-p-uses,
selected criterion is
uses/some-c-uses
a
on
the
criterion,C)
T
which
user
and
need
only
the "check"
the "select-
invoke
It is not
command.
again.
COMMANDS
csh
Spawns
exit from
a
new
shell from which
this shell and return
to
you
the ASSET
can
invoke your favorite UNIX
command
commands.
To
level type control-D.
directory
Displaysthe
name
of the
suDJectdirectoryand prompts the
user
for
a
new
subject
directory.
graphics
writes a PIC program describinga graphical
command
representation
"graphics"
is written to the file
of the subject procedure'sflow graph. The PIC program
To obtain a picture
of the flow graph,run the troff preprocessor "pic"(from a
"picfile".
The
-7-
from ASSET)
shell,not directly
UNIX
with
as inputthen pipe it through troff.
picfile
[At NYU, pipe the pic output through itroff (foroutput on a Canon Laser Printer),psroff
(foroutput on an Apple Laser Writer),or preroff(foroutput on the console if you are in
the Suntools environment.) For example, typing
I psroff
pic picfile
-Pap3
the UNIX
prompt) will send printedoutput
%
is
(where "%"
to
the LaserWriter
in
room
505.]
help
On
line
help facility.
purge
Removes
(i.e.
destroys)all of the files "subject",
"copy.p","copy.exec","traversed",
"results","pairs","paths","defuse", etc. from the current
working directory.Handle
with
care.
sepcomp
and links
Compiles
compiled subject
separately
program.
See section 5.
restore
Copies the files "subject","copy.p","copy.exec","traversed","results","pairs",
thus
"paths","defuse", etc. from the subjectdirectoryto the current working directory,
session. If the files in the subjectdirectorywere
created by
restoringa previous ASSET
additional action is
on
a separatelycompiled subjectprogram
running ASSET
some
taken
(see section 5.)
view
The
screen,
"view"
command
screenful
a
directs ASSET
time.
at a
Otherwise, ASSET
wUl
invoking the UNIX
command
Most
next
see
the UNTX
5. USING
prompt
"more", hence
mechanism.
page
ON
section
section
To
and
manual
ASSET
This
This
of text
to
SEPARATELY
displaythe
same
of
a
will
(text)file on
the
displaythat file.
command
inputsas
works
does
by
"more".
line of text, space to displaythe
command
level. For other options,
next
COMPILED
PROGRAMS
how
some
(See the relevent
instrument
contents
responds to the
to the ASSET
q to return
for "more".
describes
assumes
displaythe
type "view "filename"" ASSET
The view
you for the file name.
importantly,
type carriagereturn
screenful
to
If you
ASSET
to use
to test separatelycompiled programs.
with Berkeley Pascal's separate compilation
familiarity
sections of the Berkeley Pascal manual.)
ASSET
modified versions of the
must
create
procedure for testing,
for the main
for that procedure,the filecontainingthe source
and a file containingglobalvariable declarations. To create an executable code
program,
for the modified subjectprogram,
ASSET
must
recompile and relink the modified files
a
filecontainingthe
source
and any other filesdependenton
In order
to
describingthe
do
them.
this,ASSET
dependency
assumes
information
"make"), that
there is
such
objectfilesfor the main
that the
a
filecalled
that
contains
subjectdirectory
(see documentation
which
"globals.h"
program
and
has
for the UNTX
a
Makefile
command
globalvariable declarations,and
procedure to be instrumented
for the
-8-
are
dependenton globals.h.
If the
ASSET
"begin"command,
the main
these
of the file containing
prompts the user for the names
file
the
the
containing
subjectprocedure.We'll refer to
and
program
question"Separatecompilation?"
during execution
the
"yes" to
answers
user
of ASSET'S
ASSET
"main_file" and "subject_proc_file",
respectively.
as
"main_file",
moves
and
and "globals.h"
to "main_file".bak,
"subject_proc_file".bak,
"subject_proc_file",
writes the modified
versions
of the files to
ASSET
bak", respectively.
"globals.h.
and "globals.h".
when
"make"
Thus
the UNIX
"main_file", "subject_proc_file",
mand
comis invoked, the modified
To
rather
the
use
subject program
"compile" command.
Sepcomp
the ASSET
and
to
directory"/a.out")
in
"fname".mod
same
and
contents
whether
to
they
"fname".mod
"restore
ASSET
"sepcomp",
the UNIX
make
assumed
looks
be
to
"fname".
to
the ASSET
for files with
file, ASSET
such
each
For
Thus
session, and
for files with
looks
should
restored.
be
(Y/N)?"
"fname".mod
moves
before
"restore" command
The
as
is invoked,
"fname".bak
moves
they had
as
is
(which
ASSET
invokes
in
mand,
com-
""subject-
the ".bak" extension
"fname"
moves
to
originalfiles have
the
the modified
versions
have
the
the
".mod".
extension
user
command
subject directory.
the
code
linked.
command
copy.exec.
the "save"
When
executable
the
moves
and
compiled
the modified
compile
than
will be
subjectprogram
ASSET
then
to "fname".
the ".mod"
If the
Thus
to
restore
queries the
question
the
yes
"fname".bak
"fname"to
session
a
to
answers
user
moves
and
extension
in which
and
the instrumented
the main program
in file "main.p",answer
was
procedurewas in file "Proc3.p",
yes to the
"restore
"restore
Proc3.p.mod?",
main.p.mod?",and "restore globals.h.mod?"
questions
Restrictions
The
separately compiled
on
1. AH
relevant
2. There
is
files are
in the
file called
a
:
programs
separate compilation optionmakes
the following assumptions:
subjectdirectory.
containingglobaldefinitions
"globals.h"
subjectdirectory.
in the
is mentioned
in #include directives in the subject
"globals.h"
procedurefileand in the main program file.
4. There is a Makefile containing
the dependency information, etc.
3.
needed
to
re-link and
contained
load the program
in the
subject
directory.
Makefile
5. The
directs the executable
procedure being instrumented
nesting.
6. The
of
7. The
last included
end.
NB
--
It is currentlyNOT
6. EXAMPLE
file"a.out".
have
any extra
level
garbage at
the
a
OF
between
the
POSSIBLE
to
instrument the main
program
separately
compiled module.
In this section
by
to
(This is a bug).
of
entered
.h file cannot
code
is at the outer
text
user
AN
ASSET
we
present
written
by
in boldface
SESSION
an
annotated
example of
the system and
type. Comments
an
that written
are
ASSET
by
session.
the user,
written in itaUcs.
we
To
guish
distin-
displaytext
-9-
Example
1:
session in which a brute-force string-matching
example shows an ASSET
procedure
The
reads
and a pattern. It is supposed to printthe
a string
analyzed.
program
in the stringat which
the pattern first appears, and print0 if the pattern never
p"osition
in
the
The
current
string.
working directoryhas a subdirectorycalled "StrMtch".
appears
contains the followingprogram:
The file "StrMtch/subject.p"
(input,output);
TestStringMatch
program
This
is
const
MAX
80;
=
LENGTH
type Source
10;
=
of char;
MAX]
array[l..
LENGTH]
String array [1..
String;
=
of char;
=
var
Pat
:
Txt
: Source;
ijesult,TxtLen
:
integer;
function
%
SorText: Source;
StringMatch(Pattem:String;
: integer):
integer,
Returns 0 for no match)
{Brute force pattern-matcher.
PatPos, SorPos : integer;
var
begin
PatLen, SorLen
PatPos
:=1;
SorPos
1;
:=
repeat
if Pattem[PatPos]
=
SorText[SorPos] then
begin
SorPos
:=
PatPos
end
:=
SorPos
1;
+
PatPos
-i- 1
{then)
else
begin
SorPos
:=
PatPos
:=
(SorPos
-
PatPos)
-i-
2;
1
end; {else}
until (PatPos
if PatPos
"
"
PatLen)
or
(SorPos
then
StringMatch := SorPos
StringMatch := 0
end; {StringMatch)
-
else
begin {main program)
{Read Input)
THE
TEXT');
writelnCENTER
i:=l;
while (not(eoln)and (i"= MAX))
begin
read(Txt[i]);
i
:=
i
+
1
end;
TxtLen
readln;
:=
i
-
1;
"
PatLen
^
do
PatLen
SorLen);
-
10-
THE
PATTERN');
writelnCENTER
i:=l;
while (not(eoln)and (i"= LENGTH))
do
begin
read(Pat[i]);
i
i+
:=
1
end;
readln;
result
:=
StringMatch(Pat,Txt,i1, TxtLen);
-
writeln('The pattern firstappears
in the text.');
at
',result:3,
position
'
end.
Scriptstarted on
csd27"
May 31 13:09:59 1987
asset
Welcome
ASSET.
to
Enter relative
":
Sun
For
help type "help."
pathname of
initialdefault
directory.
StrMtch
begin
"":
subjectprocedurefile.
subject.p
SeparateCompilation?(Y/N) [N]
Enter
of
name
":
":
n
Enter the
of the
name
procedureto
be instrumented.
If you would
like to be prompted with the names
of
the procedures in the subjectprogram,
justhit carriagereturn.
":
Should
Tests tringMatch
be instrumented for testing?(Y/N)
="
":
=="
n
Should
StringMatch
for testing?
(Y/N)
be instrumented
":
"":
y
select
SELECT
A.
AU-defs
B.
All-c-uses
A
CRITERION
C. All-p-uses
D.
All-c-uses/some-p-uses
E.
All-p-uses/some-c-uses
F. All-uses
-11
G.
-
All-du-paths
the selected criterion
Enter letter representing
":
a
Criterion is All-defs.
find
"":
We
next
check
but
whether
the criterion
by doing this, we
necessary,
in the program.
check
"":
get
has
a
been
with
satisfied
no
ALL-DEFS:
Stillmust
exercise
with respect
Pattern
at
least
of the
one
from
to
Pattern
followingdef-clear paths:
to
1
( 3, 5)
1
( 3, 4)
AND
Still inust
exercise
at
least
one
with respect to
from
SorText
1
SorText
1
of the
followingdef-clear paths:
to
( 3, 5)
( 3, 4)
AND
Stillmust
exercise
with respect
PatLen
at
least
one
of the
from
to
followingdef-clear paths:
to
PatLen
PatLen
PatLen
PatLen
AND
StiU
must
exercise
with respect
SorLen
at
least
one
of the
from
to
SorLen
followingdef-clear paths:
to
1
( 6, 3)
1
( 6, 7)
AND
Stillmust
exercise
at
least
one
of the followingdef-clear paths:
exercise
at
least
one
of the
AND
StiU
must
test
listof all of the def-c-useand
followingdef-clear paths:
data. This is
not
tions
def-p-useassocia-
12-
from
with respect to
SorPos
2
4
SorPos
2
5
SorPos
2
SorPos
2
to
( 3, 5)
( 3, 4)
AND
Stillmust
exercise
at
least
one
of the followingdef-clear paths:
from
with respect to
PatPos
to
PatPos
PatPos
PatPos
PatPos
PatPos
PatPos
PatPos
AND
Still must
exercise
at
least
one
of the
from
with respect to
followingdef-clear paths:
to
SorPos
SorPos
SorPos
SorPos
SorPos
SorPos
SorPos
AND
StiU
must
exercise
with respect
at
least
one
of the
from
to
followingdef-clear paths:
to
PatPos
PatPos
PatPos
PatPos
PatPos
PatPos
PatPos
PatPos
AND
Stillmust
exercise
with respect
SorPos
SorPos
SorPos
SorPos
SorPos
SorPos
to
at
least
one
from
of the
followingdef-clear paths:
to
-
The
test
14-
the all-defscriterion.
satisfies
set
We
next
check
whether
the
same
test
set
criterion,all-uses.
a stronger
satisfies
select
"":
A.
AU-defs
B.
All-c-uses
CRITERION
A
SELECT
C. AU-p-uses
D.
All-c-uses/some-p-uses
All-p-uses/some-c-uses
E.
F. All-uses
G. All-du-paths
Enter letter representingthe selected criterion
":f
Criterion is All-uses.
check
"":
ALL-USES
Stillneed
to
exercise
all of the
To
look at these
To
aid in the selection
user
draw
can
node
again use
followingof def-clear paths:
the command
'view
results'.
the remaining def-use associations, the
of test data which cover
flow graph (see Figure 2) and use "copy.p" to aid in labelingeach
ment
corresponding code. Notice that for each i, block i begins with the statethe
with the
"write(traversed,i:F\V);"
view copy.p
"":
program
input,output);
TestStringMatch(traversed,
var
traversed: text;
const
MAX
80;
=
LENGTH
=
type
Source
=
String
=
var
10;
array [1..MAX]
array
of char;
LENGTH]
[1..
of char,
-15-
Pat:
String;
Txt: Source;
i,result,TxtLen:
integer;
Source; PatLen, SorLen:
function StringMatch(Paitem:String;SorText:
label
10;
const
FW'
4;
=
var
PalPos, SorPos:
integer,
begin
write (traversed,1: FW);
write(traversed, 2: FV\');
*
PatPos
:=
SorPos
1;
:=1;
10:
write(traversed,3: FW);
if Pattem[PatPos]
SorTexl[SorPos] then begin
4:
write(traversed, FW);
=
begin
SorPos
:=
SorPos
PatPos
:=
PatPos
1;
+
+
1
end
end
else
begin
write (traversed,5: FW);
begin
SorPos
:=
SorPos
PatPos
:=
1
-
PatPos
+
2;
end
end;
write(traversed,6: FW);
if not ((PatPos " PatLen)
goto 10;
7: FW);
write(traversed,
if PatPos
"
PatLen
then
or
(SorPos
"
SorLen)) then
begin
write(traversed,8: FW);
StringMatch := SorPos
end else begin
-
PatLen
write(traversed,9: FW);
StringMatch:= 0
end;
write(traversed,10: FW);
write(traversed,1 1 : FW)
end; { StringMatch}
begin
^
integer;
integer):
-16-
write (traversed);
THE
writelnCENTER
re
TEXT');
i:=l;
while
eoln and
not
MAX)
(i "=
do
begin
read(Txt[i]);
i
:=
i
1
+
end;
TxtLen
i
:=
-
1;
readln;
WritelnCENTER
i:=l;
while
PATTERN');
THE
eoln and (i"=
not
do
LENGTH)
begin
read(Pat[i]);
i
:=
i
+
1
end;
readln;
result
StringMatch(Pai,Txt,
:=
i
writelnf'The pattern firstappears
-
1, TxtLen);
at
position',result: 3,
'
in the
text.')
{ TestStringMatch }
end.
Examining the annotated flow graph, we see tliatin order to execute
clear with respect to PatPos, a test case
in which
which is definition
character
the
needed.
We
the stringmatches
the first
of
pattern is
the
such a test case, adding its trace to those produced by
test cases
"":
run
File 'traversed'
Do
you
want
":y
Command
":
to
line
alreadyexists.
append to it? (Y/N) [Y]
arguments?(Y/N) [Y]
n
Executingmodified subjectprogram
THE
ENTER
The
quick
ENTER
THE
...
TEXT
brown
fox
PATTERN
The
The
Do
pattern firstappears
you
on
some
":
n
"":
want
to run
additional
check
the
test
at position 1 in
subjectprogram
data? (Y/N) [N]
the text.
a
the
run
run
path from 2 to 4
firstcharacter of
the program
previously.
on
17-
-
Still need
with
all of the
exercise
to
from
to
respect
to
8
SorPos
5
PatPos
4
( 7, 9)
PatPos
5
( 7, 8)
look
To
at
these
again
the
annotated
Examining
which
produced
"":
want
you
":
to
previously.
exists.
append
to
it? (Y/N)
(Y/N)
arguments?
line
THE
quick
The
test
a
case
test
execute
a
in which
adding
case,
5
path from
the
pattern
its
to
trace
to
8
is the
those
[Y]
[Y]
The
first appears
the
bug
this
all-uses
you
on
some
":
n
is
at
output,
position
in
2 in the text.
position
program's
guaranteed
2
be
to
of
that
see
we
the
detected
by
any
bug,
a
test
we
is
The
error!
an
which
set
reported
has
program
string. This
the
discovered
Having
criterion.
the
report
...
fox
string firstappears
that
program
PATTERN
pattern
Examining
subject
TEXT
brown
THE
ENTER
is
adequate
the ASSET
save
that
reader
session
the
should
null
note
according
and
to
prepare
error.
to
want
run
additional
the
test
subject program
data?
(Y/N)
[N]
save
Note
to
run
a
such
on
to
n
ENTER
"":
the program
already
Executing modified
Do
SorPos,
to
respect
run
in order
that
see
y
Command
to
cases
we
run
":
the
with
We
the test
by
'traversed'
File
Do
flow graph,
definition clear
is
string is needed.
null
results'.
'view
the command
use
paths:
of def-clear
following
include
characters
that
a
of
to
test
the
cover
case
text,
the
in
for
one
which
some
association,
remaining
the
first k
k s.t. 0
"
k
characters
"
the
(4,(7,9)J'atPos),
of
length of
the
pattern
the pattern.
we
matched
would
have
the last k
-
select
test
-
select
additional
data
different
criterion
-
-
report
release
O
errror
software
A
user
Figure
Schematic
P
is
program.
diagram
C
1
of
is criterion.
ASSET
T
is Test
Set.
-19-
7.
1.
REFERENCES
S.
and
Rapps
E.J.
Information",
Weyuker,
IEEE
"Selecting
Softv.'are
Trans.
Software
Eng.,
Test
Data
SE-11,
Vol.
Data
Using
No.
4,
April
Flow
1985,
pp.
367-375.
2.
P.G.
3.
York,
April
P.G.
Frankl
and
P.G.
cutable
Banff,
Weiss
Tests",
New
IEEE
4.
S.N.
Frankl,
Evaluate
Softfair
Frankl
and
Canada,
"ASSET:
Weyuker,
E.J.
of
the
System
A
Conference
IEEE
on
to
Select
Software
and
Tools,
1985.
E.J.
II,
Paths",
and
Proceedings
San
E.J.
Weyuker,
Weyuker,
Proceedings
July
"A
Francisco,
1986.
Data
Dec.
"Data
of
the
Flow
Testing
Tool,"
Proceedings
1985.
Flow
IEEE
Testing
Workshop
in
the
on
Presence
Software
of
Unexe-
Testing,
of
-20-
APPENDIX
INSTALLING
I:
This
describes
apjjendix
carefully
directions
ASSET
how
before
you
install
to
We
asset.
recommend
that
read
you
these
installation.
the
begin
Installation
tarfile
The
"assetlib",
the
has
code
source
five
is
written
"tar"
using
the
of
macros
contains
make
source
executable
the
Makefile
made.
in
and
all
the
tape,
the
be
make
the
where
directory
"asset.src/interface"
it is
full
If
the
will
2.
Change
will
code
take
executable
3.
Include
directions
in
a
in
of
long
time
to
Pascal.
Berkeley
be
to
modified
this
the
be
this
modified
"asset";
if
is
be
you
the
where
some-
(full) pathname
tory
direc-
the
to
go
is
"asset"
placed
be
be
must
called
to
to
then
used
in
change
file made
file
is
"assetlib"
ASSETLIB
macro
that
executable
may
Makefile
directory
the
in
which
install
location.
correct
the
in
code
command
the
"assetdir"
to
each
executable
install
to
execute
the
note
Makefile
want
When
of
pathname;
the
have
may
Thus,
the
in
The
then
"MakeASSET".
execute
subdirectories
of
then
creates
execute),
asset.src
links
to
This
be
fi^om
compiled
assetlib
command
fore
there-
(and
and
bin
to
the
code.
the
who
installed
directories
the
causes
be
that
pathname
want
you
written
compiled.
interface,
and
modules.
interface.
user
full
make
"asset"
"asset.src"
"asset/asset.src/interface"
directory
the
this
you
and
the
before
of
macro
ASSET,
by
src",
contains
src"
steps:
pathnames
in
the
are
following
the
some
directory.
DEST
used
ASSET'S
modules
ASSET
the
of
one
other
"asset",
file
you
the
are
assigned
"interface"
the
of
found
for
files
other
for
source
there
source
when
else,
various
"asset.
"asset.
"moduler',"module2","module3","module4",
perform
file
must
the
of
C,
code
into
Also,
the
Makefile
the
coded
has
ASSET,
the
the
hard
left
read
installing
When
to
in
to
contains
subdirectories,
three
"MakeAsset".
csh-command-script,
a
"interface",
which
with
"asset"
directory
a
and
"assetlib"
of
each
"interface"
L
and
has
tape
your
subdirectories,
"modules",
After
on
"asset.man"
and
directory
plans
in
step
to
use
containing
ASSET.
1 above)
this
the
If
will
file
executable
you
be
have
the
not
directory
asset
moved
asset.
in
the
this
src
search-path
file
(according
I interface.
of
to
one
anythe
^M^-