## Presentation on theme: "A Theory of"— Presentation transcript

Slide1

A Theory ofFault Based Testing

Larry J.

Morell

Presented by: Joonghoon LeeSlide2

A Reliable Test?

A test whose success implies

Program Correctness

Unattainable in generalSlide3

Quality Measures

Desirable to have gradations of ‘goodness’

‘Reliable Test’ being the ultimate

Structural Coverage Measures

do not imply correctness

Maximize the number of faults

eliminated

Hopefully, eliminating all faultsSlide4

Fault-Based Testing

Determine the

absence

of pre-specified faults

Based on the number of faults eliminatedSlide5

A Different Perspective

Traditional point of view

A test that does not find an error is useless

Fault-Based Testing

Every correct program execution contains information that proves the program could not have contained particular faultsSlide6

Program Verification Continuum

Formal Verification

Absolute Correctness can be achieved

Fault-Based Testing

Assume that an alternate sufficient arena is available

Certain faults are shown to be eliminated

Structural CoverageSlide7

Basic Framework

<P, S, D>: Arena

P: Program

S: Specification

D: Domain, source of test dataSlide8

Framework

[P]: Program function (input, output)

[

P](x

)↓: P halts on input

x

[

P](x

)↑: doesn’t

dom([P

]): All points for which P haltsSlide9

Successful Test Case

For an arena G = <P, S, D>,

x∈D

is successful

iff

[

P](x

)↓ and (

x

, [

P](x

)) ∈[S]

Slide10

Failure Sets

The set of all failure points for G is the

Failure set

of G.

A Program P is correct with respect to S

iff

P’s failure set is empty.

Failures sets are not always recursively enumerable

Must restrict failure setSlide11

Fault-Based Arena

<

P, S, D

, L, A>

P: Program

S: Specification

D: Domain, source of test data

L: Locations in P

A: alternative set associated with locations Slide12

Test DataIn Fault-Based Testing,

test data

distinguishes

the

original program from its alternate programs.

x

distinguishes

P from R

iff

For a Program P and

x

∈

dom([P

])

<P>(

x

) ≠ <R>(

x

)Slide13

Alternate Sufficient

A fault based arena which contains a correct program is alternate sufficient

It is undecidable whether or not an arbitrary fault based arena is alternate sufficient.Slide14

Symbolic Testing

A fault based testing strategy

Symbolic execution

Use symbolic input

model infinitely many executions with single symbolic execution

2+3 , 3+3, 5+3, 7+3… => X + 3Slide15

read(x,y

)

x

: =

x

＊

y

+

3

➔ let’s try to ensure that no mistake was made in

write (

x

＊

2) in selecting the constant 3.

read(x,y

)

x

: =

x

＊

y

+

F

➔ use F to denote infinitely many alternate programs

write (

x

＊

2)

read(5,6)

➔ pick

x

: 5,

y

: 6

x

: = 5 * 6 +

F

write ( 30 +

F

) * 2 ➔ F was propagated through the program,

ultimately appearing in the output

Say original program computes 66.

➔ (30 +

F)*2 = 66

Therefore, for F, no other constant than 3 will go undetectedSlide16

Thus,

{ (5,6) } distinguishes P from

P

E

(

P

E

contains all alternate programs produced by substituting any constant for 3 in P )Slide17

Another Example 1

Program

ComputeArea(input,output

);

var

a,b,incr,area,v:real

;

begin

1 read (

a,b,incr

); {

incr

>0}

2

v

:=a*a+1

3 area := 0 => area := F

4 while

a+incr

<=

b

do begin

5 area := area +

v

*

incr

;

6 a :=

a+incr

;

7

v

:= a*a+1; end8 incr := b – a;9 if incr >= 0 then begin10 area := area + v*incr;11 write(‘area by rectangular method:’,area) end else12 write( ‘illegal values for a=’,a, ‘and b=’, b) end.

Symbolic input

a:A,b:B,incr:I

Assuming B>=A and A+I>B

(skipping loop)

Result is,

(A*A+1)*(B-A)

Introduce an assignment fault in 3:

area := F

Provides,

F+(A*A+1)*(B-A)

form a general propagation equation,

F+(A*A+1)(B-A)=(A*A+1)(B-A)

Thus,

F = 0Slide18

Another Example 2

Symbolic input

a:A,b:B,

incr:N

Assuming A

+N<

=B and A+

2N>

B

(1 iteration)

Result is,

(A

2

+1

)N+

[(A

+N)

2

+1](B-A

-N)

Introduce an assignment fault in 5:

area := F

Provides

F + [(A

+N)

2

+1](B-A

-N)

form a general propagation equation,

(A

2

+1

)N+

[(A+N)2+1](B-A-N) = F + [(A+N)2+1](B-A-N)Thus, F = (A2+1)NA2+1>0, N > 0No clear constant substitution possible

Fault Equation.

Program

ComputeArea(input,output

);

var

a,b,incr,area,v:real

;

begin

1 read (

a,b,incr

); {

incr

>0}

2

v

:=a*a+1

3 area :

= 0

4 while

a+incr

<=

b

do begin

5 area := area +

v

*

incr

;

=> area := F

6 a :=

a+incr

;

7

v

:= a*a+1;

end

8

incr

:=

b

– a;

9 if

incr

>= 0 then begin

10 area := area +

v

*

incr

;

11

write(‘area

by rectangular

method:’,area

)

end else

12 write( ‘illegal values for a=’,a, ‘and

b

=’,

b

)

end

.Slide19

Domain Dependent Transformations

Domain Independent

If

x

= 1 then

y

:=1 else

y

:=

x

*

x

Domain Dependent

If

x

=

F

then

y

:=1 else

y

:=

x

*

x

Makes testing difficult!Slide20

“

Looking for errors”

misleading in two ways:

What errors should we find?

Unattainable

Fault-Based Testing

<P, S, D, L, A>

Symbolic Testing

Use symbolic input to represent all inputs which follow a given path