Transcript SWE 637: Here! Test this!

CS 217
Software Verification and
Validation
Week 3, Summer 2014
Instructor: Dong Si
http://www.cs.odu.edu/~dsi
REVIEW OF LAST CLASS
LOGIC IN COMPUTER
SCIENCE
Week 2, topic 1
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.
4
Motivation

Since the latter half of the 20th century, logic has been
used in computer science for various purposes ranging
from software validation and verification to theoremproving.
5
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)
6
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.)
7

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

8
Fundamental of Logic

We are interested in precise declarative statements about
computer systems and programs. (Verification)

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)
9
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
10
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.”
11
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
12
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!
13
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!
14
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
15
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!
16
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
17
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
18
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
19
Answers to Quiz 2
Q1. Let
H = "John is healthy"
W = "John is wealthy"
S = "John is smart"

(1). “John is healthy and wealthy but not smart”:
Answer:
H Λ W Λ ¬S
(2). “John is not wealthy but he is healthy and smart”:
Answer:
¬W Λ H Λ S
(3). “John is neither healthy nor wealthy nor smart”:
Answer:
¬H Λ ¬W Λ ¬S
20
Q2. Let
P = “You stay at the hotel”
Q = “You watch TV”
R = “You go to the museum”
S = “You spend some time in the museum”

"You can either (stay at the hotel and watch TV ) or (you
can go to the museum and spend some time there)”
Answer:
(P Λ Q) V (R Λ S)
21
Q3. Let P, Q, and R be the following propositions:
P = “You get an A on the final exam”
Q = “You do every exercise in the book”
R = “You get an A in this class”

(1). “You get an A in this class, but you do not do every
exercise in the book.”
Answer:
R ∧ ¬Q
22
(2). “To get an A in this class, it is necessary for you to get
an A on the final.”
Answer:
R⇒P
“If you want an A in this class, you must have an A on the
final.”
“If you got an A in this class, that means you have gotten an
A on the final.”
(3). “Getting an A on the final and doing every exercise in
the book is sufficient for getting an A in this class.”
Answer:
P∧Q⇒R
23

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)

25
CODE COVERAGE TESTING
Week 2, topic 2
Definition

Code coverage is a measure used to describe the
degree to which the source code of a program is tested by
a particular test suite.

A program with high code coverage has been more
thoroughly tested and has a lower chance of
containing software bugs than a program with low code
coverage.
27
Coverage criterias

Function coverage - Has each function (or subroutine)
in the program been called?
√

Statement coverage - Has each statement in the
program been executed?
√
√
28
Coverage criterias

Branch coverage - Has each branch of each control
structure (such as in if and case statements) been
executed?
For example, given an if statement, have both the T and F
branches been executed?
 Another way of saying this is, has every edge in the
program been executed?

29
Coverage criterias

Condition coverage - Has each Boolean sub-expression
evaluated both to true (T) and false (F) ?
In “A and B”,
 if sub-expression A is evaluated both to T and F
 if sub-expression B is evaluated both to T and F

30
Example

consider the following C++ function:

If during this execution function 'foo' was called at least
once, then function coverage for this function is satisfied.
31
Example

consider the following C++ function:

Statement coverage for this function will be satisfied if it
was called e.g. as foo(1,1), as in this case, every line in the
function is executed including ’z = x;’.
32
Example

consider the following C++ function:

Tests calling foo(1,1) and foo(0,1) will satisfy branch
coverage because, in the first case, the 2 if conditions are
met and z = x; is executed, while in the second case, the
first condition (x>0) is not satisfied, which prevents
executing z = x;.
33
Example

consider the following C++ function:
(x>0) && (y>0)
T,F
T,F

Condition coverage can be satisfied with tests that
call foo(1,1), foo(1,0) and foo(0,0). These are necessary
because in the first two cases, (x>0) evaluates to true,
while in the third, it evaluates false. At the same time, the
first case makes (y>0) true, while the second and third
make it false.
34
Condition / branch coverage?

Condition coverage does not necessarily imply branch
coverage. For example:

Condition coverage can be satisfied by two tests:

However, this set of tests does not satisfy branch
coverage since neither case will meet the if condition.
35
Condition / branch coverage?
IF (
X>0
AND
Y>0
)
T,F?
T,F?
T
F
THEN
…
ELSE
…
36
Answers to Quiz 2

Q5. Consider the following pseudo code of a program
‘Fun’. It takes x and y as input variables, and outputs the
value of z:
fun (x, y)
{
z = 1;
IF ((x>z) AND (y>z))
THEN z = 0;
Output z;
}
1.
2.
3.
4.
5.
Fun (0, 0)
Fun (2, 0)
Fun (0, 2)
Fun (2, 2)
Fun (8, 9)
37
Consider the following five test cases:
1. Fun (0, 0)
2. Fun (2, 0) 3. Fun (0, 2)
5. Fun (8, 9)

4. Fun (2, 2)
Function coverage: all
Statement coverage: 4 and 5
Branch coverage: all
(4&5 make the branch ’IF’ to T, 1&2&3 make it to F)
Condition coverage: all
(2&4&5 make the sub-expression ‘x>z’ to T, 1&3 make it F)
38
Bonus Question

What happened if switch AND with OR logic in the
program:
fun (x, y)
{
z = 1;
IF ((x>z) OR (y>z))
THEN z = 0;
Output z;
}
1.
2.
3.
4.
5.
Fun (0, 0)
Fun (2, 0)
Fun (0, 2)
Fun (2, 2)
Fun (8, 9)
Function coverage:
Statement coverage:
Branch coverage:
Condition coverage:
39
Input Space Partitioning
Week 3
Black-box testing

Program is treated as a black box.

Different inputs will be used as tests.

Testing based solely on analysis of requirements
(specification, user documentation, etc.).

Black-box techniques apply to all levels of testing (e.g.,
unit, integration and system).
41
Test Data and Test Cases

Test data: Inputs which have been devised to test the
system.

Test cases: Inputs to test the system and the predicted
outputs from these inputs if the system operates
according to its specification.
42
Input Domains

The input domain to a program contains all the possible
inputs to that program

For even small programs, the input domain is so large that
it might as well be infinite

Testing is fundamentally about choosing finite sets of
values from the input domain
43
Input Domains

Input parameters define the scope of the input domain
– Parameters to a program/function
y = Absolute(x)
– Data read from a file

Domain for each input parameter is partitioned into
regions
-3 -2 -1 0 1 2 3……

x<0, negative
x=0, zero
x>0, positive
At least one value is chosen from each region
x = -3,
x = 0,
x = +2
44
Data Testing

If you think of a program as a function, the input of the
program has its own domain.

Examples of program data are:
– words typed into MS Word
– numbers entered into Excel
– picture displayed in Photoshop
–…
45
Input space partitioning

Also known as equivalence partitioning.

Reducing the huge (or infinite) set of possible test cases
into a small but equally effective set of test cases.
Invalid inputs
Valid inputs
System
Outputs

Dividing input values into valid and invalid partitions and
selecting representative values from each partition as test
data.
46
Equivalence partitions

Sometimes boundary values need more tests
3
4
Less than 4
7
11
10
Between 4 and 10
More than 10
Number of input values
9999
10000
Less than 10000
50000
100000
99999
Between 10000 and 99999
More than 99999
Input values
47
Partitioning Domains




Domain D
Partition scheme q of D
The partition q defines a set of blocks, Bq = b1 , b2 , … bQ
The partition must satisfy two properties :
1. blocks must be pairwise disjoint (no overlap)
2. together the blocks cover the domain D (complete)
b1
b2
b3
48
Using Partitions – Assumptions
Choose a value from each partition
 Each value is assumed to be equally useful for testing
 Application to testing

– Find characteristics in the inputs : parameters, semantic
descriptions, …
– Partition each characteristic
– Choose tests by combining values from characteristics

Example Characteristics
– Input X is a number (null, negative, zero, positive…)
– Input X is a picture (binary, gray scale, …)
– Input X is a multimedia disk to a device (DVD, CD, VCD, …)
49
Example 1: compare two numbers

Function ‘compare (x, y)’
Inputs: Two numbers – x and y
 Outputs: A larger number between x and y

(x, y)
z
z = Compare (x, y)
50
• 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” }
51
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
52
Example 2: Loan application
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…
53
Customer name
Number of characters:
invalid
Valid characters:
Conditions
Customer
name
1
2
valid
A-Z
-’ a-z
space
Valid
Invalid
Partitions
Partitions
2 to 64 chars < 2 chars
valid chars
> 64 chars
invalid chars
64 65
invalid
Any
other
Valid
Invalid
Boundaries
Boundaries
2 chars
1 chars
64 chars
65 chars
0 chars
54
Loan amount
499
invalid
Conditions
Loan
amount
Valid
Partitions
500 - 9000
500
9000
valid
Invalid
Partitions
< 500
>9000
0
non-numeric
null
9001
invalid
Valid
Invalid
Boundaries
Boundaries
500
499
9000
9001
55
Design test cases
Test
Case
Description
Expected Outcome
New Tags
Covered
1
Name:
Acc no:
Loan:
Term:
John Smith
123456
2500
3 years
Term:
Repayment:
Interest rate:
Total paid:
3 years
79.86
10%
2874.96
V1, V2,
V3, V4,
V5 .....
2
Name:
Acc no:
Loan:
Term:
AB
100000
500
1 year
Term:
Repayment:
Interest rate:
Total paid:
1 year
44.80
7.5%
537.60
B1, B3,
B5, .....
Next class

Talk about Black-Box testing
(Input Space Partitioning & Boundary value analysis)

Given a lab assignment on BB testing

Finish the lab report in the class
57