• Nu S-Au Găsit Rezultate

Software Quality Engineering:

N/A
N/A
Protected

Academic year: 2022

Share "Software Quality Engineering:"

Copied!
31
0
0

Text complet

(1)

Software Quality Engineering:

Testing, Quality Assurance, and Quantifiable Improvement

Jeff Tian, [email protected]

www.engr.smu.edu/∼tian/SQEbook

Chapter 10. Coverage and Usage Testing Based on FSMs and Markov Chains

• Finite-State Machines (FSMs)

• FSM-Based Testing

• Markov Chains as Enhanced FSMs

• Unified Markov Models for Testing

(2)

Alternative Testing Models

• Motivation: Why FSMs?

. Complicated operations involve many steps/stages in the end-to-end chain . Not modeled in checklists/partitions.

. Ability to use existing models and structural information

. Ability to use localized knowledge . Local information easy to gather

• FSM: Basic ideas

. State: operations/functions.

. Transition: link in a chain.

. Input/output associated with transition.

. Complete operation: chain.

(3)

FSMs as Graphs

• FSMs often represented by graphs.

• State/node and properties:

. Represents status/processing/component . Identification and labeling

. Other properties: node weights

• Links and link properties:

. Represent state transitions.

. Labeling: Often by the nodes they link.

. Other properties: link weights – associated input and output.

. Directed (e.g., A-B link 6= B-A link).

(4)

Types of FSMs

• Types of FSMs:

. Classification by input/output.

. Classification by state.

. Other classifications possible.

• FSM types by input/output representation:

. Mealy model: both input and output associated with transitions

. Moore model: output represented as separate states.

. Mealy model used in this book.

(5)

Types of FSMs

• Classification by state representation.

. Type I. state = status, with most of the processing and I/O at transition.

. Type II. transition = I/O free link, with most of the processing and I/O at state.

. We use both, and mixed type too.

• Type I & II as Mealy models:

. Type I: classical Mealy model.

. Type II: modified Mealy model,

I/O not explicitly represented in FSMs.

. Mixed type: used for convenience if not leading to confusion.

(6)

Types of FSMs

• Type I example (classical Mealy model):

. “initial” state: when program starts, . transfer to another state accompanied

by some processing and associated I/O – performing user-oriented function

– execution some statements

– I/O associated with above (or empty) . above state transitions may be repeated

for different states and transitions

. “final” state: where program terminates.

. See also web testing discussion in Section 10.3.

• Type II example: control flow graph (CFG) or flow chart in Chapter 11.

(7)

Types of FSMs

• Mixed type example: Fig 10.1 (p.151)

. state C = status,

no associated processing.

. states with processing: A, B, D, E.

. transitions with I/O:

C-D, C-B, D-C, D-E.

(only input marked, output implicit) . transitions without I/O:

A-B, B-C, E-B.

• Mixed type for convenience:

. Hard to restrict to one type

⇒ use mixed type.

. Ensure no confusion.

. Key: significant difference among states so that state transitions are meaningful.

(8)

FSM/Graph Representation

• Types of graphs:

. Directed graph: FSM etc.

. Undirected graph: neighbor-relation, etc.

. Connectivity vs. disconnected graphs.

• Graph representation:

. Graphical: good for human processing (mostly in the book)

. Tables/matrices: machine processing – example: Table 10.1 (p.152).

. Lists: compact sets of items like {C, B,

“unable to receive paging channel”, -} . Conversion: easy, but need to know.

(9)

Basic FSM Testing

• Typical problems:

. Missing, extra, or incorrect states.

. Missing, extra, or incorrect transitions.

. Input problems: treat as related state or transition problems.

. Output problems: as oracle problems.

• Basic coverage: Node and link coverage.

• Basic approach:

. Missing/extra states/transitions dealt with at FSM construction stage.

. State traversal based on graph theory and algorithms for constructed FSMs.

. Correct functioning of individual state ensured by lower level testing.

(10)

Basic FSM Testing

• Checking for missing/extra states/links during model construction.

• Model construction steps:

. Identify info. sources and collect data.

. Construct initial FSM.

. Model refinement and validation.

• Identify information sources and collect data.

. external functional behavior (black-box):

– specification, usage scenarios, etc.

. internal program execution (white-box):

– design, code, execution trace, etc.

. also existing test cases, documents, etc.

. key: linking individual pieces together.

(11)

Basic FSM Testing

• Construct initial FSM.

. state identification and enumeration (too many states

⇒ nested/hierarchical FSMs) . transition/link identification

. identify I/O relations (as test oracles) . key sub-step: link identification

• Link identification and problem detection:

. identify all possible input for each state, . input values may be partitioned (Ch. 9) . each partitioned subset/subdomain

associated with a state transition . undefined transition for some input

⇒ missing state or extra link identified.

. extra state or missing link identified by the collective states and transitions

(or by connectivity algorithm later)

(12)

Basic FSM Testing

• Model refinement and validation.

. Refinement with additional states/links.

. State explosion concerns

– at most “dozens” of states in FSMs . Proper granularity needed

⇒ use of nested/hierarchical FSMs

• Applicability:

. Suitable for menu driven software.

. Systems with clearly identified states/stages.

. Interactive mode (many I/O pairs).

. Control systems, OOS, etc.

• Key limitation: state explosion!

⇒ nested FSMs, or Markov chains (later)

(13)

Basic FSM Testing

• Node/link coverage via state traversal

. Based on graph theory/algorithms.

. States directly covered.

. Link coverage: starting from state in combination with input domain testing ideas (Ch.8&9).

• Implementation issues:

. Sensitization: easy, with specific input.

. State cover: series of links with input.

. Capability to “save” state information:

– help with link coverage from the state, – state traversal w/o much repeating.

. Oracle: output with link

(14)

Case Study: FSMs for Web Testing

• Web applications vs. menu-driven systems:

. Many similarity but significant differences.

. Computation vs. information/document.

. Separate vs. merged navigations.

. Entry/exit/control difference.

. Differences in population size/diversity.

. Layers (Fig. 10.2, p.158) or not?

• Web problems: What to test:

. Reliability: failure-free content delivery.

. Failure sources identified accordingly:

– host or network failures – browser failures

– source or content failures – user problems

. Focus on source/content failures

(15)

FSMs for Web Testing

• Web source/content components:

. HTML and other documents

. Programs (Java/JavaScript/ActiveX/etc.) . Data forms and backend databases

. Multi-media components

• Testing of individual components:

≈ traditional testing (mostly coverage).

• Testing of overall operation:

. FSMs for navigation/usage . States = pages

. Transitions = embedded links

(direct URLs not by content providers) . I/O: clicks & info. loading/displaying.

. Difficulty: size! ⇒ other models later.

(16)

Markov Usage Model: Overview

• Extend FSMs to support selective testing.

• Markov-chain OP models

. State transitions and probability . Markov property

. Attractive in interactive systems, GUI, and many state-transition types

. Structural and conceptual integrity

• Comparison with Musa OP:

. Similar to FSM vs list/partitions.

. Musa OP as collapsed Markov chains.

. Coverage: harder to achieve.

(17)

Markov Usage Model

• Applications:

. Similar to flat OP (Musa),

but captures more detailed information . Models functional structure and usage . Test case generation more complex

. Result: both analytical and observational

• Background and Linkage:

. Augmented FSMs.

. Cleanroom background:

testing technique and tools

. (Whittaker and Thomason, 1994) – TSE 20(10):812-824 (10/94) . UMM and web testing at SMU

(18)

Markov OP and UMMs

• Markov chains: Formal definitions:

. FSMs with probabilistic state transitions.

. Memoryless or Markovian property:

P{Xn+1 = j|Xn = i, Xn1 = sn1, . . . , X0 = s0}

= P{Xn+1 = j|Xn = i}

= pij.

. pij: probability from state i to state j 0 ≤ pij ≤ 1, and Pj pij = 1.

. Example: Fig 10.3 (p.162)

• UMM: Unified Markov Models

. Hierarchical modeling idea.

. Markov chains at different-levels.

. More flexibility for statistical testing.

. Example: Fig 10.4 (p.163) as expanded

(19)

Markov/UMM Construction: Steps

• Structure of Markov chain:

. State machines:

e.g., IS-95 call processing ⇒ Fig 10.3 . Flow diagram/function description.

. At proper granularity

. Same as FSM construction earlier

• Transition probabilities:

. Various way to obtain

– measurement/survey/expert-opinion – Musa procedures (Ch.8) usable?

. May use structural/domain knowledge

• UMM hierarchy determination/adjustment along the way.

(20)

Markov/UMM Construction

• Other sources of information:

. Sources for FSMs, with emphasis on external/black-box information

. Existing flow charts/testing model . Performance models

(especially for real time systems) . Analytical (e.g. queuing) models . Market/requirement analyses

. Similar/earlier products . Industry/external surveys

• Use of the above information sources . for FSMs and transition probabilities . existing hierarchies ⇒ UMM hierarchies?

(21)

Markov/UMM Analysis

• Analysis of the chain/model:

. Static/stationary properties . Transient properties

. Analysis difficulties if size↑ or non-stationary process.

. Alternative: simulation & measurement.

• Result analysis:

. Testing using Markov OP . Collect failure data

. Fit to reliability models

⇒ direct reliability assessment.

(22)

Markov/UMM: Testcase Generation

• Basic approaches:

. Markov chain ⇒ test cases . Static: off-line, traditional

– need more analysis support

. Dynamic: on-line, dynamic decisions – need more run-time support

• Whittaker/Thomason:

. Basic testing chain from Markov chain . Incorporating failure data

. Results and result analysis:

– testing vs. usage comparison – mean-steps-between-failures

(23)

Markov/UMM: Testcase Generation

• Avritzer/Weyuker (TSE 21, 9/95):

. Both coverage &usage,

. Off-line test case generation . Path probability and coverage:

– overall testing, similar to Musa OP.

. Node probability and coverage:

– critical component testing

. Call-pair probability and coverage:

– transition/interface testing

• Hierarchical testing with UMMs

. High level coverage

. Low level selective/statistical testing . Dynamic expansion

(24)

UMM in Web Testing

• Web testing factors:

. Existing: coverage-based testing . Web size, complexity, user focus . Dynamic nature

. Focus on source failures . Statistical web testing

– modeling, testing, result analysis

• Measurement and analysis support:

. Model construction: access-log e.g. Fig 10.5 (p.168)

. Analysis: error-log

. Some existing analyzers

(25)

Statistical Web Testing

• High level testing: UMMs

. Overall structure and linkage

. Usage and criticality information . Guide/drive low level testing

. Performance and reliability analyses

• Low level testing:

. HTML checkers

. Other existing tools

. Future: formal spec. checker

(26)

UMMs: Web Usage Modeling

• Access log analysis:

. Access frequency from different users . Timing analysis of accesses

. Network traffic and performance

• For usage-based web testing?

. Usage patterns and frequencies . Usage model: UMMs

. Information extraction . Use of existing tools

• Existing tool: FastStats

. Summary statistics & hyperlink tree view used to generate UMMs

(27)

UMMs: Web Usage Modeling

• Top level model: Fig 10.6 (p.170)

. Node and link information:

#s not probabilities due to omission.

. Selection of top-hit pages.

. Grouping of low-hit pages.

. Lower level models connected to this.

• Problems and issues:

. Entry pages: Table 10.2 (p.170)

– skewed distribution ⇒ single top model . Exit pages: implicit.

. Missing information: need extra effort and ways to collect additional data.

. Integration with existing testing and Musa OP: Chapter 12.

(28)

UMMs vs. Musa

• Flat (Musa) vs. Markovian OPs

. Granularity and sequencing differences . Use in test case generation

– Musa: direct test cases

– Markov: tool to generate test cases . Use in reliability analysis

– overall (both) vs. localized (Markov)

• Common issues:

. Musa’s 5 steps applicable to both . Focus on customer and reliability . Information collection

(29)

Choice: Musa vs Markov/UMM

• External (primary) factors to consider:

. Product size

. Product/usage structure

. Link/sequence of operations . Granularity of info. available

• Internal (secondary) factors to consider:

. Ability to handle complexity . Desired level of detail

. Tool support

• Key: What does the user see?

(unit of operation or in a lump?)

(30)

Conversion: Musa ⇔ Markov

• Is conversion meaningful?

• Musa to Markovian:

. enough info?

. additional information gathering . additional analysis/construction

• Markovian to Musa:

. prob(path) from prob(links) . loops ⇒ prob. threshold

. mostly related to test case generation

(31)

Summary and Comparison

• Comparison between FSMs and list/partitions similar to between Markov and Musa OPs.

• FSMs and Markov-OPs/UMMs:

. More complex operations/interactions . More complex models too!

. Need algorithm and tool support for analysis and testing.

. Difficulties with FSMs: state explosion

⇒ UBST with Markov-OPs/UMMs

• FSM testing focus on traversal of individual states and links ⇒ extend FSMs to test problems involving more states/links:

. specialized FSM to test execution paths . test related data dependencies?

. CFT and DFT techniques (Ch.11)

Referințe

DOCUMENTE SIMILARE

Key word s: state diagrams, finite state automatic machine, state, initial state and final state, transition, event, message, condition, effect: action/activity, durable

Given a library of program plan templates, generating a partial understanding of a piece of software source code can be shown to correspond to the construction of mappings

In 5 of the answers, the subject occupies the initial position of the main clause (Victor s-a apucat să cânte/de cântat la trombon), but 2 of the answers contain only

In the situation where failures are experienced, the genetic algorithm approach yields information about similar, but different, test cases that reveal faults in the software

• General Types of Defect Analyses.. • ODC: Orthogonal

Gilb Inspection (Expanded Fagan).. • Key: A “process

• Hazard sources identification ⇒ elimination (Some specific faults prevented or removed.).. • Traditional QA (but with

 Software maintenance in software engineering is the modification of a software product after delivery to correct faults, to improve performance or other7. attributes