Transcription of Software Testing and Analysis: Process, Principles, and ...
1 Software Testing and Analysis: process , principles , andTechniquesSoftware Testing and Analysis: process , principles , andTechniquesMauro Pezz`eUniversit`a di Milano BicoccaMichal YoungUniversity of OregonPUBLISHERD aniel SayreSENIOR PRODUCTION EDITORLisa WojcikEDITORIAL ASSISTANTL indsay MurdockCOVER DESIGNERM adelyn LesureCOVER PHOTORick Fischer/MasterfileWILEY200TH ANNIVERSARY LOGO DESIGNR ichard J. PacificoThis book was typeset by the authors using pdfLATEXand printed and boundby Malloy Lithographing. The cover was printed by Phoenix Color book is printed on acid free paper. Copyrightc 2008 John Wiley & Sons, Inc. All rights reserved. No part of thispublication may be reproduced, stored in a retrieval system or transmitted in any form orby any means, electronic, mechanical, photocopying, recording, scanning or otherwise,except as permitted under Sections 107 or 108 of the 1976 United States Copyright Act,without either the prior written permission of the Publisher, or authorization throughpayment of the appropriate per-copy fee to the Copyright Clearance Center, Inc.
2 222 Rosewood Drive, Danvers, MA 01923, website Requests to thePublisher for permission should be addressed to the Permissions Department, John Wiley& Sons, Inc., 111 River Street, Hoboken, NJ 07030-5774, (201) 748-6011, fax(201) 748-6008, website order books or for customer service please, call 1-800-CALL WILEY (225-5945).ISBN-13 978-0-471-45593-6 Printed in the United States of America10 9 8 7 5 6 4 3 2 1 ContentsList of FiguresxiList of TablesxvI Fundamentals of Test and Analysis11 Software Test and analysis in a Engineering Processes and Verification .. Basic Questions .. When Do Verification and Validation Start and End? .. What Techniques Should Be Applied? .. How Can We Assess the Readiness of a Product? .. How Can We Ensure the Quality of Successive Releases? .. How Can the Development process Be Improved?
3 112 A Framework for Test and Validation and Verification .. Degrees of Freedom .. Varieties of Software ..233 Basic Sensitivity .. Redundancy .. Restriction .. Partition .. Visibility .. Feedback ..364 Test and analysis Activities Within a Software The Quality process .. Planning and Monitoring .. Quality Goals .. Dependability Properties .. analysis .. Testing .. Improving the process .. Organizational Factors ..50II Basic Techniques535 Finite Overview .. Finite Abstractions of Behavior .. Control Flow Graphs .. Call Graphs .. Finite State Machines ..656 Dependence and Data Flow Definition-Use Pairs .. Data Flow analysis .. Classic Analyses: Live and Avail .. From Execution to Conservative Flow analysis .. Data Flow analysis with Arrays and Pointers.
4 Interprocedural analysis ..967 Symbolic Execution and Proof of Symbolic State and Interpretation .. Summary Information .. Loops and Assertions .. Compositional Reasoning .. Reasoning about Data Structures and Classes ..1098 Finite State Overview .. State Space Exploration .. The State Space Explosion Problem .. The Model Correspondence Problem .. Granularity of Modeling .. Intensional Models .. Model Refinement .. Data Model Verification with Relational Algebra ..140 III Problems and Methods1499 Test Case Selection and Overview .. Test Specifications and Cases .. Adequacy Criteria .. Comparing Criteria ..157 CONTENTSvii10 Functional Overview .. Random versus Partition Testing Strategies .. A Systematic Approach .. Choosing a Suitable Approach ..17411 Combinatorial Overview.
5 Category-Partition Testing .. Pairwise Combination Testing .. Catalog-Based Testing ..19412 Structural Overview .. Statement Testing .. Branch Testing .. Condition Testing .. Path Testing .. Procedure Call Testing .. Comparing Structural Testing Criteria .. The Infeasibility Problem ..23013 Data Flow Overview .. Definition-Use Associations .. Data Flow Testing Criteria .. Data Flow Coverage with Complex Structures .. The Infeasibility Problem ..24314 Model-Based Overview .. Deriving Test Cases from Finite State Machines .. Testing Decision Structures .. Deriving Test Cases from Control and Data Flow Graphs .. Deriving Test Cases from Grammars ..25715 Testing Object-Oriented Overview .. Issues in Testing Object-Oriented Software .. An Orthogonal Approach to Test .. Intraclass Testing .
6 Testing with State Machine Models .. Interclass Testing .. Structural Testing of Classes .. Oracles for Classes .. Polymorphism and Dynamic Binding .. Inheritance .. Genericity .. Exceptions ..30816 Fault-Based Overview .. Assumptions in Fault-Based Testing .. Mutation analysis .. Fault-Based Adequacy Criteria .. Variations on Mutation analysis ..32117 Test Overview .. From Test Case Specifications to Test Cases .. Scaffolding .. Generic versus Specific Scaffolding .. Test Oracles .. Self-Checks as Oracles .. Capture and Replay ..33718 Overview .. The Inspection Team .. The Inspection process .. Checklists .. Pair Programming ..35119 Program Overview .. Symbolic Execution in Program analysis .. Symbolic Testing .. Summarizing Execution Paths .. Memory analysis .
7 Lockset analysis .. Extracting Behavior Models from Execution ..365IV Process37320 Planning and Monitoring the Overview .. Quality and process .. Test and analysis Strategies .. Test and analysis Plans .. Risk Planning .. Monitoring the process .. Improving the process .. The Quality Team ..39921 Integration and Component-based Software Overview .. Integration Testing Strategies .. Testing Components and Assemblies ..41322 System, Acceptance, and Regression Overview .. System Testing .. Acceptance Testing .. Usability .. Regression Testing .. Regression Test Selection Techniques .. Test Case Prioritization and Selective Execution ..43423 Automating analysis and Overview .. Automation and Planning .. process Management .. Static Metrics .. Test Case Generation and Execution.
8 Static analysis and Proof .. Cognitive Aids .. Version Control .. Debugging .. Choosing and Integrating Tools ..45124 Documenting analysis and Overview .. Organizing Documents .. Test Strategy Document .. analysis and Test Plan .. Test Design Specification Documents .. Test and analysis Reports ..462 Bibliography467 Index479xCONTENTSList of Figures1 Selective reading .. analysis and Testing activities .. Validation and verification .. Verification trade-off dimensions .. Unpredictable failure and predictable failure .. Initialize before use problem .. Dependability properties .. Abstraction coalesces execution states .. Constructing control flow graphs .. Java method to collapse adjacent newline characters .. Statements broken across basic blocks .. Linear-code sequence and jump (LCSAJ).
9 Over-approximation in a call graph .. Context sensitivity .. Exponential explosion of calling contexts in a call graph .. Finite state machine specification of line-end conversion procedure . Correctness relations for a finite state machine model .. Procedure to convert among Dos, Unix, and Macintosh line ends .. Completed FSM specification of line-end conversion procedure .. GCD calculation in Java .. Control flow graph of GCD method .. Data dependence graph of GCD method .. Calculating control dependence .. Control dependence tree of GCD method .. Reaching definitions algorithm .. Available expressions algorithm .. Java method with potentially uninitialized variable .. Control flow with definitions and uses .. Annotated CFG for detecting uses of uninitialized variables ..89xixiiLIST OF CGI program in Python with misspelled variable.
10 Powerset lattice .. Spurious execution paths in interprocedural analysis .. Binary search procedure .. Concrete and symbolic tracing .. Finite state verification .. Misapplication of the double-check initialization pattern .. FSM models from Figure .. Promela finite state model .. Excerpts of Spin verification tool transcript .. Spin guided simulation trace describing race condition .. A graphical interpretation of Spin guided simulation trace .. Dining philosophers in Promela .. A simple data race in Java .. Coarse and fine-grain models of interleaving .. Lost update problem .. OBDD encoding of a propositional formula .. OBDD representation of transition relation .. Data model of a simple Web site .. Alloy model of a Web site.. Alloy model of a Web site (continued) .. A Web site that violates the browsability property.
