Transcript Software Engineering Program

Functional Verification I
Software Testing and Verification
Lecture Notes 21
Prepared by
Stephen M. Thebaut, Ph.D.
University of Florida
Overview of Functional Verification Topics
Lecture Notes #21 - Functional Verification I
• Introduction
• Verifying correctness in program reading, writing, and
validation
• Complete and sufficient correctness
• Compound programs and the Axiom of Replacement
Lecture Notes #22 - Functional Verification II
•
Correctness conditions and working correctness
questions: sequencing and decision statements
Overview of Functional Verification Topics
Lecture Notes #23 - Functional Verification III
•
Iteration Recursion Lemma (IRL) (Very Cool!)
•
Termination predicate
•
Correctness conditions for while_do statement
•
Sufficient correctness conditions
•
Correctness conditions for repeat_until statement
•
Subgoal Induction
Lecture Notes #24 – Functional Verification IV
• Invariant Status Theorem (EXTREMELY Cool!)
• While Loop Initialization
Today’s Topics:
• Introduction
• Verifying correctness in program
reading, writing, and validation
• Complete and sufficient correctness
• Compound programs and the Axiom of
Replacement
Introduction
• What is functional verification?
A methodology originally developed by Mills
for verifying program correctness with
respect to an intended function specification.
It represents a viable alternative to the
axiomatic verification method developed by
Hoare and Floyd.
Introduction (cont’d)
• References:
Linger, Mills, & Witt, Structured Programming:
Theory and Practice, Addison-Wesley, 1979.
Dunlop & Basili, “A Comparative Analysis of
Functional Correctness,” Computing Surveys,
Vol. 14, No. 2, June 1982.†
Linger, “Cleanroom Software Engineering for ZeroDefect Software,” Proceedings, 15th Int. Conf. on
Soft. Eng. (1993), IEEE Computer Society Press.†
† Required readings.
Tasks in Program Reading, Writing, and
Verification
• Program Reading:
– Abstract a given program construct
(e.g., an if_then_ else statement)
into a hypothesized function f.
– To confirm that your understanding of
the program is correct, show:
f = [if p then G else H]
Tasks in Program Reading, Writing, and
Verification (cont’d)
• Program Writing:
– Expand a given function f into a
hypothesized program construct (e.g.,
an if_then_else statement).
– To confirm that your expansion of f
into a program is correct, show:
f = [if p then G else H]
Tasks in Program Reading, Writing, and
Verification (cont’d)
• Program Verification:
– You are given both function f and its
hypothesized program expansion (e.g.,
an if_then_ else statement).
– To confirm the correctness of the
hypothesized program expansion with
respect to f, show:
f = [if p then G else H]
Tasks in Program Reading, Writing, and
Verification (cont’d)
• In all three cases, the final task is to
confirm the equivalence (or subset
relationship) of two expressions, each
representing the function of a program.
Complete and Sufficient
Correctness
• Given a function f and a program P
(claimed to implement f ), correctness is
concerned with one of two questions:
1. Is f = [P] ? (“Is f equivalent to the
function computed by P ?”) – A
question of complete correctness.
2. Is f  [P] ? (“Is f a subset of the
function computed by P ?”) – A
question of sufficient correctness.
Complete and Sufficient
Correctness (cont’d)
• In the case of complete correctness, P
computes the correct values of f for
arguments in D(f) only; [P] is undefined
(P does not terminate) for arguments
outside D(f).
• In the case of sufficient correctness, P
may compute values from arguments
not in D(f).
• Note that, by definition,
f = [P] implies f  [P]
Correctness Relationships
(X,Y)f  (X,Y)[P]
(X,Y)f  (X,Y)[P]
[P]
f
f
[P]
(X,Y)f  (X,Y)[P]
[P], f
(X,Y)f  (X,Y)[P]
[P]
f
Example
• For integers x,y consider the function:
f = (y≥0  x,y := x+y,0)
and the programs:
P1 = while y>0 do x,y := x+1,y-1
P2 = while y<>0 do x,y := x+1,y-1
Use heuristics to hypothesize functions
for P1 and P2 and compare these to f.
Example (cont’d)
• Consider
P1 = while y>0 do x,y := x+1,y-1
y>0 
y=0 
y<0 
f = (y≥0  x,y := x+y,0)
Example (cont’d)
• Consider
P2 = while y<>0 do x,y := x+1,y-1
y>0 
y=0 
y<0 
f = (y≥0  x,y := x+y,0)
Example (cont’d)
• Both programs satisfy sufficient correctness.
(Both correctly compute f(x,y) for y≥0.)
• Only P2 satisfies complete correctness. (P1
terminates for negative y.)
Defensive Programming: Handling
Invalid Inputs
• f and P can be redefined to handle invalid
inputs:
f’ = (y≥0  x,y,z := x+y,0,z |
true  x,y,z := x,y,‘error’)
P’ = if y<0 then z := ‘error’
else
while y>0 do
x,y := x+1,y-1
end_while
end_if_then_else
• Does f’ = [P’] ?
Exercise
“Identify” function:
x,y := x,y
• Given
P = if x>=y then x,y := y,x
f1 = (x>y  x,y := y,x | true  I)
f2 = (x>y  x,y := y,x | x<y  I)
f3 = (x≠y  x,y := y,x)
• Fill in the following “correctness table”:
P
f1
f2
f3
C=Complete (and Sufficient)
S=Sufficient (only)
N=Neither
Compound Programs and the
Axiom of Replacement
• The algebraic structure of compound
program P permits decomposition into
a hierarchy of abstractions.
• The proof of correctness of P is
thereby decomposed into a proof of
correctness of each such abstraction.
Compound Programs and the
Axiom of Replacement (cont’d)
• For example, to show that compound
program F implements function f, where
F = if p then G else H
and G, H are themselves programs:
– hypothesize functions g, h and
attempt to prove
g = [G] and h = [H]
Compound Programs and the
Axiom of Replacement (cont’d)
– If successful, use the Axiom of
Replacement to reduce the problem to
proving
f = if p then g else h
– If successful again, you will have
proved
f = [F]
Compound Programs and the
Axiom of Replacement (cont’d)
• Thus, the Axiom of Replacement allows
one to prove the correctness of complex
programs in a bottom-up, incremental
fashion.
• In the next lecture, we consider
correctness conditions for sequencing
and decision statements.
Functional Verification I
Software Testing and Verification
Lecture Notes 21
Prepared by
Stephen M. Thebaut, Ph.D.
University of Florida