Model based testing
(c) 2007 Mauro Pezzè & Michal Young Ch 14, slide 1
Learning Objectives
• Understand the role of models in devising test
cases
• Principles underlying functional and structural test adequacy criteria, as well as model-based testing
• Understand some examples of model-based testing techniques
• A few of the most common model-based techniques, representative of many others
• Be able to understand, devise and refine other model-based testing techniques
• Grasp the basic approach and rationale well enough to apply it in other contexts
(c) 2007 Mauro Pezzè & Michal Young Ch 14, slide 2
Functional Specifications
Independently Testable Feature
Finite State Machine Grammar
Algebraic Specification Logic Specification Control/Data Flow Graph
Model
Test Selection Criteria
Brute
Force Testing
Representative Values
Semantic Constraints Combinatorial Selection Exaustive Enumeration Random Selection
Test Case Specifications
Manual Mapping Symbolic Execution A-posteriori Satisfaction
Test Cases
Scaffolding
(c) 2007 Mauro Pezzè & Michal Young
Ch 14, slide 3
De ri ve a Model
Identify
R epre senta tive Values
Generate Test-Case Specifications
GenerateTest-Case Specifications
Instantiate Tests
Generate T est Cases
Identify Independently Testable Features
Why model-based testing?
• Models used in specification or design have structure
• Useful information for selecting representative classes of behavior; behaviors that are treated differently with respect to the model should be tried by a thorough test suite
• In combinatorial testing, it is difficult to capture that structure clearly and correctly in constraints
• We can devise test cases to check actual
behavior against behavior specified by the
model
• “Coverage” similar to structural testing, but applied to specification and design models
(c) 2007 Mauro Pezzè & Michal Young Ch 14, slide 4
Deriving test cases from finite state machines
A common kind of model for describing behavior that depends on sequences of events or stimuli
Example: UML state diagrams
(c) 2007 Mauro Pezzè & Michal Young
Ch 14, slide 5
Finite State Machines (FSM)
• A mathematical model of computation
– used to design computer programs and sequential logic circuits
• Defined by the set of states and the set of triggers/conditions that lead to a change from one state to another (a transition).
• Can be in only one state at a time.
• Has no external memory (usually).
• Finite Automata are FSM with accepting states and no external memory.
(c) 2007 Mauro Pezzè & Michal Young Ch 14, slide 6
Example of FSM – UML state charts
(c) 2007 Mauro Pezzè & Michal Young Ch 14, slide 7
From an informal specification…
Maintenance: The Maintenance function records the history of items undergoing maintenance.
If the product is covered by warranty or maintenance contract, maintenance can be requested either by calling the maintenance toll free number, or through the web site, or by bringing the item to a designated maintenance station.
If the maintenance is requested by phone or web site and the customer is a US or EU resident, the item is picked up at the customer site, otherwise, the customer shall ship the item with an express courier.
If the maintenance contract number provided by the customer is not valid, the item follows the procedure for items not covered by warranty.
If the product is not covered by warranty or maintenance contract, maintenance can be requested only by bringing the item to a maintenance station. The maintenance station informs the customer of the estimated costs for repair. Maintenance starts only when the customer accepts the estimate.
If the customer does not accept the estimate, the product is returned to the customer.
Small problems can be repaired directly at the maintenance station. If the maintenance station cannot solve the problem, the product is sent to the maintenance regional headquarters (if in US or EU) or to the maintenance main headquarters (otherwise).
If the maintenance regional headquarters cannot solve the problem, the product is sent to the maintenance main headquarters.
Maintenance is suspended if some components are not available. Once repaired, the product is returned to the customer.
(c) 2007 Mauro Pezzè & Michal Young Ch 14, slide 8
From an informal specification…
Maintenance: The Maintenance function records the history of items undergoing maintenance.
If the product is covered by warranty or maintenance contract, maintenance can be
requested either by calling the maintenance toll free number, or through the web site, or
by bringing the item to a designated maintenance station.
…
If the maintenance is requested by phone or web site and the customer is a US or EU resident, the item is picked up at the customer site, otherwise, the customer shall ship the item with an express courier.
If the maintenance contract number provided by the customer is not valid, the item follows
the procedure for items not covered by warranty.
If the product is not covered by warranty or maintenance contract, maintenance can be requested only by bringing the item to a maintenance station. The maintenance station informs the customer of the estimated costs for repair. Maintenance starts only when the customer accepts the estimate.
Multiple choices in the first step
… determine the possibilities for the next step …
If the customer does not accept the estimate, the product is returned to the customer.
Small problems can be repaired directly at the maintenance station. If the maintenance station cannot solve the problem, the product is sent to the maintenance regional headquarters (if in US or EU) or to the maintenance main headquarters (otherwise).
If the maintenance regional headquarters cannot solve the problem, the product is sent to the maintenance main headquarters.
Maintenance is suspended if some components are not available. Once repaired, the product is returned to the customer.
… and so on …
(c) 2007 Mauro Pezzè & Michal Young Ch 14, slide 9
0
NO Maintenance
1
Wait for returning
2 Maintenance (no warranty )
3
return
Wait for pick up
…to a finite state machine…
Repaired
4
5
component arrives (a)
lackcomponent (b)
component arrives (b)
Wait for acceptance
Repair estimate (maintenance
station)
6
accept
repair completed
there are infinite paths
7
8
Wait for component
Repair (regional headquarters )
unable to repair
(not US or EU resident )
component arrives (c)
9 Repair (main
(c) 2007 Mauro Pezzè & Michal Young
headquarters )
Ch 14, slide 10
pickup
pickup
est ima te c o s ts
requestat maintenance station or by express courier (contract number)
request a t maintenance station (n o warranty)
request
by phone or web [US or EU resident] (contract number)
reject estimate
inv alid c o nt r a ct number
unable to repair (US or EUresident)
successful repair
lackcomponent(a)
successful repair
unable to repair
lackcomponent (c)
…to a test suite
Meaning: From state 0 to state 2 to state 4 to state 1 to state 0
0
TC1 TC2 TC3 TC4
0 0 0 0
2 5 3 3
4 2 5 5
1 4 9 7
0 5 6 5
6 0 8
78960
Is this a thorough test suite? How can we judge?
(c) 2007 Mauro Pezzè & Michal Young
Ch 14, slide 11
TC1 TC2 TC3 TC4
0 0 0 0
2 5 3 3
4 2 5 5
1 4 9 7
0 5 6 5
6 0 8
0 7
8
9
6
0
(c) 2007 Mauro Pezzè & Michal Young Ch 14, slide 12
TC1 TC2 TC3 TC4
0 0 0 0
2 5 3 3
4 2 5 5
1 4 9 7
0 5 6 5
6 0 8
0 7
8
9
6
0
(c) 2007 Mauro Pezzè & Michal Young Ch 14, slide 13
TC1 TC2 TC3 TC4
0 0 0 0
2 5 3 3
4 2 5 5
1 4 9 7
0 5 6 5
6 0 8
0 7
8
9
6
0
(c) 2007 Mauro Pezzè & Michal Young Ch 14, slide 14
TC1 TC2 TC3 TC4
0 0 0 0
2 5 3 3
4 2 5 5
1 4 9 7
0 5 6 5
6 0 8
0 7
8
9
6
0
(c) 2007 Mauro Pezzè & Michal Young Ch 14, slide 15
“Covering” finite state machines
• State coverage:
– Every state in the model should be visited by at least one test case
• Transition coverage
– Every transition between states should be traversed by at least one test case.
– This is the most commonly used criterion
• A transition can be thought of as a (precondition,
postcondition) pair
• transition coverage subsumes state coverage (though it does not mean that it subsumes the bugs)
(c) 2007 Mauro Pezzè & Michal Young Ch 14, slide 16
Path sensitive criteria?
• Basic assumption: States fully summarize history
• No distinction based on how we reached a state; this should be true of well-designed state machine models
• If the assumption is violated, we may distinguish paths and devise criteria to cover them
– Single state path coverage:
• traverse each subpath that reaches each state at most once
– Single transition path coverage:
• traverse each transition at most once
– Boundary interior loop coverage:
• each distinct loop of the state machine must be exercised the minimum, an intermediate, and the maximum or a large number of times
• Of the path sensitive criteria, only boundary-interior is common
(c) 2007 Mauro Pezzè & Michal Young Ch 14, slide 17
Flowgraph based testing
If the specification or model has both decisions and sequential logic, we can cover it like program source code.
(c) 2007 Mauro Pezzè & Michal Young Ch 14, slide 18
from an informal spec(1)
• Process shipping order: The Process shipping order function checks the validity of orders and prepares the receipt
A valid order contains the following data:
– cost of goods: If the cost of goods is less than the minimum processable order (MinOrder) then the order is invalid.
– shipping address: The address includes name, address, city, postal code, and country.
– preferred shipping method: If the address is domestic, the shipping method must be either land freight, expedited land freight, or overnight air; If the address is international, the shipping method must be either air freight, or expedited air freight.
(c) 2007 Mauro Pezzè & Michal Young Ch 14, slide 19
from an informal spec(2)
– a shipping cost is computed based on
• address and shipping method.
• type of customer which can be individual, business, educational
– preferred method of payment. Individual customers can use only credit cards, business and educational customers can choose between credit card and invoice
– card information: if the method of payment is credit card, fields credit card number, name on card, expiration date, and billing address, if different than shipping address, must be provided. If credit card information is not valid the user can either provide new data or abort the order
(c) 2007 Mauro Pezzè & Michal Young Ch 14, slide 20
from an informal spec(3)
• The outputs of Process shipping order are
• validity: Validity is a boolean output which indicates whether the order can be processed.
• total charge: The total charge is the sum of the value of goods and the computed shipping costs (only if validity = true).
• payment status: if all data are processed correctly and the credit card information is valid or the payment is invoice, payment status is set to valid, the order is entered and a receipt is prepared; otherwise validity = false.
(c) 2007 Mauro Pezzè & Michal Young Ch 14, slide 21
…to a flowgraph
Process shipping order
no
CostOfGoods < MinOrder
international
preferred shipping method = air freight OR expedited air freight
domestic
shipping address
preferred shipping method = land freight, OR expedited land freight OR overnight air
calculate international shipping charge
total charge = goods + shipping
calculate domestic shipping charge
no nono
yes
individual customer
method of payement
yes
credit card
obtain credit card data: number, name on card, expiration date
billing address = shipping address no
yes
invoice
no
yes
valid credit card information
no
obtain billing address
payement status = valid
enter order prepare receipt
abort order?
yes
(c) 2007 Mauro Pezzè & Michal Young
invalid order
Ch 14, slide 22
...from the flow graph to test cases
Branch testing: cover all branches
TC-1 No Int Air Bus CC No Yes
Too Ship Ship Cust Pay Same
Case Small Where Method Type Method Address CC valid
TC-2 No TC-3 Yes TC-4 No TC-5 No TC-6 No TC-7 No TC-8 No
TC-9 No
Dom Land - - - - ----- - Dom Air - - - - Int Land - - - -
- - Edu Inv - - - CC - - - CC
- - - CC
- - Yes -
- No(abort)
No (no - abort)
(c) 2007 Mauro Pezzè & Michal Young
Ch 14, slide 23
Summary: Black-box
and grey-box testing
• Black-box testing techniques: – functional testing
– random testing
– combinatorial testing
– stress testing
– model-based testing
• Grey-box testing techniques (require access to the source code, but not understanding of specifics of implementation):
– fault-based testing (error seeding, fault injection, mutation) – next lecture
(c) 2007 Mauro Pezzè & Michal Young Ch 14, slide 24
Home reading
• Chapter 14 of the book Software Testing and Analysis, by Mauro Pezze and Michal Young
– Model-based testing
(c) 2007 Mauro Pezzè & Michal Young Ch 1, slide 25