CS 217
Software Verification and
Validation
Week 9, Summer 2014
Instructor: Dong Si
http://www.cs.odu.edu/~dsi
REVIEW OF THE CLASS
What is (software) testing?
Softeware Testing – definition

The process consisting of all life cycle activities,
concerned with planning, preparation and evaluation
of software products and related work products to
determine:
– that they satisfy specified requirements,
– to demonstrate that they are fit for purpose and
– to detect defects
4
Validation & Verification
Validation : Have we built the right software?
 i.e., do the requirements satisfy the customer?
 (This is dynamic process for checking and testing the real
product. Software validation always involves with executing the
code)

Verification : Have we built the software right?
 i.e., does it implement the requirements?
 This is static method for verifying design, code. Software
verification is human based checking of documents and files

Introduction to Software Testing, Edition 2 (Ch 1)
© Ammann & Offutt
5
Software Faults, Errors & Failures

Software Fault : A static defect in the software

Software Failure : External, incorrect behavior with
respect to the requirements or other description of the
expected behavior

Software Error : An incorrect internal state that is the
manifestation/expression of some fault
Faults in software are equivalent to design mistakes in
hardware.
Software does not degrade.
Introduction to Software Testing, Edition 2 (Ch 1)
© Ammann & Offutt
6
Fault and Failure Example

The doctor tries to diagnose the root cause, the disease
– Fault

A patient gives a doctor a list of symptoms
– Failures

The doctor may look for anomalous internal conditions
(high blood pressure, irregular heartbeat, bacteria in the
blood stream)
– Errors
Most medical problems result from external attacks
(bacteria, viruses) or physical degradation as we age.
They were there at the beginning and do not “appear”
when a part wears out.
Introduction to Software Testing, Edition 2 (Ch 1)
© Ammann & Offutt
7
Sources of Problems

Requirements Definition: Erroneous, incomplete, inconsistent
requirements.

Design: Fundamental design flaws in the software.

Implementation: Mistakes in chip fabrication, wiring,
programming faults, malicious code.

Support Systems: Poor programming languages, faulty compilers
and debuggers, misleading development tools.
Sources of Problems (Cont’d)

Inadequate Testing of Software: Incomplete testing,
poor verification, mistakes in debugging.

Evolution: Sloppy redevelopment or maintenance,
introduction of new flaws in attempts to fix old flaws,
incremental escalation to inordinate complexity.
Summary: Why Do We Test
Software ?
A tester’s goal is to eliminate faults
as early as possible
• Improve quality
• Reduce cost
• Preserve customer satisfaction
Introduction to Software Testing, Edition 2 (Ch 1)
© Ammann & Offutt
10
Testing main principles
Testing Principles (1)

Testing can demonstrate only the presence of defects and
not their absence
– Testing can show that defects are present, but cannot prove that there
are no defects. Testing reduces the probability of undiscovered defects
remaining in the software but, even if no defects are found, it is not a
proof of correctness.

Exhaustive testing is impossible
– Exhaustive testing (all combinations of inputs and preconditions) is not
feasible except for trivial cases. Instead of exhaustive testing, risk
analysis and priorities should be used to focus testing efforts.
Testing Principles (2)

Early testing is important
– Testing activities should start as early as possible in the software
or system development life cycle and should be focused on
defined objectives.

Defects are clustering
– A small number of modules contain most of the defects
discovered during pre-release testing, or are responsible for the
most operational failures.
Testing Principles (3)

Testing is context dependent
– Testing is done differently in different contexts. For example, military
software is tested differently from an business site.
Software Testing Process
V&V Targets
Code & Implementation
Unit test
Software Design
Integration
test
System
test
System engineering
15
Software Development Lifecycles
Code and Fix
 Waterfall
 Cycle

BASIC OF LOGICS
Motivation

LOGIC enabled mathematicians to point out WHY a
proof is wrong, or WHERE in the proof, the reasoning has
been faulty.

Faults (bugs) have been detected in proofs (programs)

Is such a tool that by symbolizing arguments rather than
writing them out in some natural language (which is
fraught with ambiguity), checking the correctness of a
proof becomes a much more viable task.
18
Introduction to Logic

CS areas where we use LOGIC
Architecture (logic gates)
Software Engineering (Validation & Verification)
Programming Languages (Semantics & Logic Programming)
AI (Automatic theorem proving)
Algorithms (Complexity)
Databases (SQL)
19
Fundamental of Logic

Declarative statements

Examples of declarative statements
– “A is older than B”
– “There is ice in the glass”
– In CIS, describing the data (variables, functions, etc.)
20

Propositions
- a statement that is either true or false.
For every proposition p, either p is T or p is F
 For every proposition p, it is not the case that p is both T
and F

21
Fundamental of Logic

We not only want to specify such statements, but also
want to check whether a given program or system fulfills
specifications that user needs. (Validation)

We are interested in precise declarative statements about
computer systems and programs. (Verification)
22
Propositional Logic: Basics

Propositional logic describes ways to combine some true
statements to produce other true statements.
If it is proposed that `Jack is taller than John' and
`John can run faster than Jack' are both T
=`Jack is taller than John and John can run faster than Jack'.


Propositional logic allows us to formalize such statements.

In concise form: A ^ B
23
Propositional Logic

Composition of atomic sentences
p: I won the lottery yesterday
q: I will purchase a lottery ticket today
r: I played a football game yesterday

~ p: Negation. “I did not win the lottery last week”

p v r: Disjunction. The statement is true if at least one of
them is true. “I won the lottery or played a football game
yesterday.”
24
Propositional Logic

p ^ r: Conjunction. “Yesterday I won the lottery and
played a football game.”

p q: Implication. “If I won the lottery last week, then I
will purchase a lottery ticket today.” p is called the
assumption and q is called conclusion.
– p implies q
– If p then q
25
Natural Deduction

Proof

Set of rules which allow us to draw a conclusion by given a
set of preconditions

Constructing a proof is much like a programming!

It is not obvious which rules to apply and in what order to
obtain the desired conclusion, be careful to choose proof
rules!
26
Rules of Natural Deduction

Fundamental rule 1 (rule of detachment)
p
p
q
...q

The rule is a valid inference because
[p ^ (p
q)]
q is a tautology!
27
Rules of Natural Deduction
 Example:
if it is 11:00 o’ clock in Norfolk
if it is 11:00 o’ clock in Norfolk, then it is 11:00 o’ clock in DC
then by rule of detachment, we must conclude:
it is 11:00 o’ clock in DC
28
Rules of Natural Deduction

Fundamental rule 2 (transitive rule)
p
q
...p
q
r
r
This is a valid rule of inference because the implication
(p q) ^ (q r)
(p
r) is a tautology!
29
Rules of Natural Deduction

FR 3 (De Morgan’s law)
~(p v q) = (~p) ^ (~q)
~(p ^ q) = (~p) v (~q)

FR 4 (Law of contrapositive)
p
q = (~q
~p)

FR 5 (Double Negation)
~(~p) = p
30
Examples of Arguments



If a baby is hungry, then the baby cries. If the baby is not
mad, then he does not cry. If a baby is mad, then he has a
red face. Therefore, if a baby is hungry, then he has a red
face.
Model this problem!!
h: a baby is hungry
c: a baby cries
m: a baby is mad
r: a baby has a red face
h
~m
m
c
~c
r
...h
h
c
m
r
c
m
r
...h
r
31
Logic is the Skeleton

What remains when arguments are symbolized is the bare
logical skeleton

It is this form that enables us to analyze the program /
code / software.

Software V&V = Logical proof & Logic error detection
32

Q4. Problem:
“Tom is a math major but not computer science major”
M: Tom is a math major
C: Tom is a computer science major

Tasks:
Use De Morgan's Law to write the negation of the above
statement as logic expression

Answer:
Original:
 M Λ ¬ C (Tom is a math major but not computer science
major)

Negation:
 ¬ (M Λ ¬ C) = ¬ M V ¬ (¬ C) (De Morgan's Laws)
= ¬ M V C (Double negation rule)

34
BLACK-BOX TESTING
&
WHITE-BOX TESTING
Differences Between BB and WB
36
Black-Box Testing
37
White-Box testing
38
REVIEW OF BB-testing
Black-box Testing
1.
Input Space Partitioning
2.
Boundary Value Analysis
40
Example 1: compare two numbers
– p50 of week3

Function ‘Compare (x, y)’
Inputs: Two numbers – x and y
 Outputs: A larger number between x and y

(x, y)
z
Compare (x, y) = z
41
– p51 of week3
• Equivalence Classes:
{ (x, y) | x < y }
{ (x, y) | x > y }
Valid inputs
{ (x, y) | x = y }
{ input other than a pair of numbers,
Invalid inputs
“as&%dfget^$(&w” }
42
– p52 of week3
Valid (x, y) Input Space
Three test cases:
(1, 2) --- 2
x<y
(8, 8) --- 8
(100, 30) --- 100
x>y
Plus one test cases:
(^&%*) --- ERROR
43
Example 2: Loan application
- p53 of week3
Customer Name
Account number
Loan amount requested
Term of loan
Monthly repayment
2-64 chars.
6 digits, 1st
non-zero
$500 to $9000
1 to 30 years
Term:
Repayment:
Minimum $10
Interest rate:
Total paid back:
Choosing (or defining) partitions seems easy, but is easy to get wrong…
44
Customer name
Number of characters:
invalid
Valid characters:
C o nd itio ns
C us to m e r
na m e
V a lid
P a rtitio ns
2 to 6 4 c ha rs
va lid c ha rs
1
2
A-Z
-’ a-z
space
Inva lid
P a rtitio ns
< 2 c ha rs
> 6 4 c ha rs
inva lid c ha rs
valid
64 65
invalid
Any
other
V a lid
B o und a rie s
2 c ha rs
6 4 c ha rs
Inva lid
B o und a rie s
1 c ha rs
6 5 c ha rs
0 c ha rs
45
Loan amount
499
invalid
C o nd itio ns
Loan
a m o unt
V a lid
P a rtitio ns
500 - 9000
500
9000
valid
Inva lid
P a rtitio ns
< 500
>9 0 0 0
0
no n-num e ric
null
9001
invalid
V a lid
B o und a rie s
500
9000
Inva lid
B o und a rie s
499
9001
46
WB Testing Techniques
Logic coverage: (learned in previous classes)
 Statement coverage
 Branch coverage
 Condition coverage
…


Dataflow based testing / Path coverage: all program paths
have been traversed at least once
47
Pseudo code & Control/Dataflow Graphs
“nodes”
“edges”
Input
x
Absolute (x)
{
IF (x>=0)
THEN y = x;
IF (x>=0)
ELSE IF (x<0)
y = -x;
y = x;
ELSE IF (x<0)
THEN y = -x;
y
Output y;
}
output
48
Descargar

SWE 637: Here! Test this!