Introduction to Static Analysis
An Abstract Interpretation Perspective
by Rival, Yi
ISBN: 9780262043410 | Copyright 2020
Instructor Requests
A self-contained introduction to abstract interpretation–based static analysis, an essential resource for students, developers, and users.
Static program analysis, or static analysis, aims to discover semantic properties of programs without running them. It plays an important role in all phases of development, including verification of specifications and programs, the synthesis of optimized code, and the refactoring and maintenance of software applications. This book offers a self-contained introduction to static analysis, covering the basics of both theoretical foundations and practical considerations in the use of static analysis tools. By offering a quick and comprehensive introduction for nonspecialists, the book fills a notable gap in the literature, which until now has consisted largely of scientific articles on advanced topics.
The text covers the mathematical foundations of static analysis, including semantics, semantic abstraction, and computation of program invariants; more advanced notions and techniques, including techniques for enhancing the cost-accuracy balance of analysis and abstractions for advanced programming features and answering a wide range of semantic questions; and techniques for implementing and using static analysis tools. It begins with background information and an intuitive and informal introduction to the main static analysis principles and techniques. It then formalizes the scientific foundations of program analysis techniques, considers practical aspects of implementation, and presents more advanced applications. The book can be used as a textbook in advanced undergraduate and graduate courses in static analysis and program verification, and as a reference for users, developers, and experts.
| Expand/Collapse All | |
|---|---|
| Contents (pg. vii) | |
| Preface (pg. xi) | |
| 1. Program Analysis (pg. 1) | |
| 1.1 Understanding Software Behavior (pg. 1) | |
| 1.2 Program Analysis Applications and Challenges (pg. 2) | |
| 1.3 Concepts in Program Analysis (pg. 4) | |
| 1.3.1 What to Analyze (pg. 4) | |
| 1.3.2 Static versus Dynamic (pg. 6) | |
| 1.3.3 A Hard Limit: Uncomputability (pg. 7) | |
| 1.3.4 Automation and Scalability (pg. 8) | |
| 1.3.5 Approximation: Soundness and Completeness (pg. 9) | |
| 1.4 Families of Program Analysis Techniques (pg. 12) | |
| 1.4.1 Testing: Checking a Set of Finite Executions (pg. 12) | |
| 1.4.2 Assisted Proof: Relying on User-Supplied Invariants (pg. 13) | |
| 1.4.3 Model Checking: Exhaustive Exploration of Finite Systems (pg. 14) | |
| 1.4.4 Conservative Static Analysis: Automatic, Sound, and Incomplete Approach (pg. 15) | |
| 1.4.5 Bug Finding: Error Search, Automatic, Unsound, Incomplete, Based on Heuristics (pg. 16) | |
| 1.4.6 Summary (pg. 17) | |
| 1.5 Roadmap (pg. 17) | |
| 2. A Gentle Introduction to Static Analysis (pg. 19) | |
| 2.1 Semantics and Analysis Goal: A Reachability Problem (pg. 19) | |
| 2.2 Abstraction (pg. 24) | |
| 2.3 A Computable Abstract Semantics: Compositional Style (pg. 31) | |
| 2.3.1 Abstraction of Initialization (pg. 32) | |
| 2.3.2 Abstraction of Post-Conditions (pg. 32) | |
| 2.3.3 Abstraction of Non-Deterministic Choice (pg. 36) | |
| 2.3.4 Abstraction of Non-Deterministic Iteration (pg. 37) | |
| 2.3.5 Verification of the Property of Interest (pg. 43) | |
| 2.4 A Computable Abstract Semantics: Transitional Style (pg. 44) | |
| 2.4.1 Semantics as State Transitions (pg. 45) | |
| 2.4.2 Abstraction of States (pg. 48) | |
| 2.4.3 Abstraction of State Transitions (pg. 48) | |
| 2.4.4 Analysis by Global Iterations (pg. 51) | |
| 2.5 Core Principles of a Static Analysis (pg. 56) | |
| 3. A General Static Analysis Framework Based on a Compositional Semantics (pg. 59) | |
| 3.1 Semantics (pg. 60) | |
| 3.1.1 A Simple Programming Language (pg. 60) | |
| 3.1.2 Concrete Semantics (pg. 60) | |
| 3.2 Abstractions (pg. 65) | |
| 3.2.1 The Concept of Abstraction (pg. 65) | |
| 3.2.2 Non-Relational Abstraction (pg. 69) | |
| 3.2.3 Relational Abstraction (pg. 72) | |
| 3.3 Computable Abstract Semantics (pg. 74) | |
| 3.3.1 Abstract Interpretation of Assignment (pg. 76) | |
| 3.3.2 Abstract Interpretation of Conditional Branching (pg. 79) | |
| 3.3.3 Abstract Interpretation of Loops (pg. 82) | |
| 3.3.4 Putting Everything Together (pg. 90) | |
| 3.4 The Design of an Abstract Interpreter (pg. 92) | |
| 4. A General Static Analysis Framework Based on a Transitional Semantics (pg. 95) | |
| 4.1 Semantics as State Transitions (pg. 96) | |
| 4.1.1 Concrete Semantics (pg. 96) | |
| 4.1.2 Recipe for Defining a Concrete Transitional Semantics (pg. 100) | |
| 4.2 Abstract Semantics as Abstract State Transitions (pg. 101) | |
| 4.2.1 Abstraction of the Semantic Domain (pg. 102) | |
| 4.2.2 Abstraction of Semantic Functions (pg. 105) | |
| 4.2.3 Recipe for Defining an Abstract Transition Semantics (pg. 107) | |
| 4.3 Analysis Algorithms Based on Global Iterations (pg. 109) | |
| 4.3.1 Basic Algorithms (pg. 109) | |
| 4.3.2 Worklist Algorithm (pg. 110) | |
| 4.4 Use Example of the Framework (pg. 112) | |
| 4.4.1 Simple Imperative Language (pg. 112) | |
| 4.4.2 Concrete State Transition Semantics (pg. 114) | |
| 4.4.3 Abstract State (pg. 115) | |
| 4.4.4 Abstract State Transition Semantics (pg. 116) | |
| 5. Advanced Static Analysis Techniques (pg. 119) | |
| 5.1 Construction of Abstract Domains (pg. 120) | |
| 5.1.1 Abstraction of Boolean-Numerical Properties (pg. 120) | |
| 5.1.2 Describing Conjunctive Properties (pg. 122) | |
| 5.1.3 Describing Properties Involving Case Splits (pg. 126) | |
| 5.1.4 Construction of an Abstract Domain (pg. 130) | |
| 5.2 Advanced Iteration Techniques (pg. 131) | |
| 5.2.1 Loop Unrolling (pg. 131) | |
| 5.2.2 Fixpoint Approximation with More Precise Widening Iteration (pg. 133) | |
| 5.2.3 Refinement of an Abstract Approximation of a Least Fixpoint (pg. 135) | |
| 5.3 Sparse Analysis (pg. 137) | |
| 5.3.1 Exploiting Spatial Sparsity (pg. 139) | |
| 5.3.2 Exploiting Temporal Sparsity (pg. 140) | |
| 5.3.3 Precision-Preserving Def-Use Chain by Pre-Analysis (pg. 142) | |
| 5.4 Modular Analysis (pg. 143) | |
| 5.4.1 Parameterization, Summary, and Scalability (pg. 144) | |
| 5.4.2 Case Study (pg. 145) | |
| 5.5 Backward Analysis (pg. 147) | |
| 5.5.1 Forward Semantics and Backward Semantics (pg. 147) | |
| 5.5.2 Backward Analysis and Applications (pg. 148) | |
| 5.5.3 Precision Refinement by Combined Forward and Backward Analysis (pg. 150) | |
| 6. Practical Use of Static Analysis Tools (pg. 153) | |
| 6.1 Analysis Assumptions and Goals (pg. 153) | |
| 6.2 Setting Up the Static Analysis of a Program (pg. 159) | |
| 6.2.1 Definition of the Source Code and Proof Goals (pg. 159) | |
| 6.2.2 Parameters to Guide the Analysis (pg. 162) | |
| 6.3 Inspecting Analysis Results (pg. 166) | |
| 6.4 Deployment of a Static Analysis Tool (pg. 170) | |
| 7. Static Analysis Tool Implementation (pg. 173) | |
| 7.1 Concrete Semantics and Concrete Interpreter (pg. 174) | |
| 7.2 Abstract Domain Implementation (pg. 180) | |
| 7.3 Static Analysis of Expressions and Conditions (pg. 183) | |
| 7.4 Static Analysis Based on a Compositional Semantics (pg. 186) | |
| 7.5 Static Analysis Based on a Transitional Semantics (pg. 190) | |
| 8. Static Analysis for Advanced Programming Features (pg. 195) | |
| 8.1 For a Language with Pointers and Dynamic Memory Allocations (pg. 196) | |
| 8.1.1 Language and Concrete Semantics (pg. 196) | |
| 8.1.2 An Abstract Semantics (pg. 199) | |
| 8.2 For a Language with Functions and Recursive Calls (pg. 203) | |
| 8.2.1 Language and Concrete Semantics (pg. 203) | |
| 8.2.2 An Abstract Semantics (pg. 206) | |
| 8.3 Abstractions for Data Structures (pg. 212) | |
| 8.3.1 Arrays (pg. 212) | |
| 8.3.2 Buffers and Strings (pg. 217) | |
| 8.3.3 Pointers (pg. 219) | |
| 8.3.4 Dynamic Heap Allocation (pg. 223) | |
| 8.4 Abstraction for Control Flow Structures (pg. 229) | |
| 8.4.1 Functions and Procedures (pg. 230) | |
| 8.4.2 Parallelism (pg. 237) | |
| 9. Classes of Semantic Properties and Verification by Static Analysis (pg. 243) | |
| 9.1 Trace Properties (pg. 243) | |
| 9.1.1 Safety (pg. 244) | |
| 9.1.2 Liveness (pg. 247) | |
| 9.1.3 General Trace Properties (pg. 250) | |
| 9.2 Beyond Trace Properties: Information Flows and Other Properties (pg. 251) | |
| 10. Specialized Static Analysis Frameworks (pg. 257) | |
| 10.1 Static Analysis by Equations (pg. 258) | |
| 10.1.1 Data-Flow Analysis (pg. 258) | |
| 10.2 Static Analysis by Monotonic Closure (pg. 262) | |
| 10.2.1 Pointer Analysis (pg. 263) | |
| 10.2.2 Higher-Order Control-Flow Analysis (pg. 265) | |
| 10.3 Static Analysis by Proof Construction (pg. 268) | |
| 10.3.1 Type Inference (pg. 268) | |
| 11. Summary and Perspectives (pg. 275) | |
| A. Reference for Mathematical Notions and Notations (pg. 277) | |
| A.1 Sets (pg. 277) | |
| A.2 Logical Connectives (pg. 277) | |
| A.3 Definitions and Proofs by Induction (pg. 278) | |
| A.4 Functions (pg. 278) | |
| A.5 Order Relations and Ordered Sets (pg. 278) | |
| A.6 Operators over Ordered Structures and Fixpoints (pg. 279) | |
| B. Proofs of Soundness (pg. 281) | |
| B.1 Properties of Galois Connections (pg. 281) | |
| B.2 Proofs of Soundness for Chapter 3 (pg. 282) | |
| B.2.1 Soundness of the Abstract Interpretation of Expressions (pg. 282) | |
| B.2.2 Soundness of the Abstract Interpretation of Conditions (pg. 283) | |
| B.2.3 Soundness of the Abstract Join Operator (pg. 283) | |
| B.2.4 Abstract Iterates with Widening (pg. 283) | |
| B.2.5 Soundness of the Abstract Interpretation of Commands (pg. 285) | |
| B.3 Proofs of Soundness for Chapter 4 (pg. 286) | |
| B.3.1 TransitionalStyle Static Analysis over Finite-Height Domains (pg. 286) | |
| B.3.2 Transitional-Style Static Analysis with Widening (pg. 287) | |
| B.3.3 Use Example of the Transitional-Style Static Analysis (pg. 288) | |
| Bibliography (pg. 291) | |
| Index (pg. 297) | |
Xavier Rival
Xavier Rival is Research Director at INRIA Paris and head of the research group on static analysis at Ecole Normale Supérieure/CNRS/INRIA/PSL
Kwangkeun Yi
Kwangkeun Yi is Professor in the Department of Computer Science & Engineering at Seoul National University and head of its Programming Research Laboratory.
| Instructors Only | |
|---|---|
|
You must have an instructor account and submit a request to access instructor materials for this book.
|
|
eTextbook
Go paperless today! Available online anytime, nothing to download or install.
Features
|
