Difference between revisions of "Book/Principles of Abstract Interpretation"

From PKC
Jump to navigation Jump to search
 
(One intermediate revision by the same user not shown)
Line 25: Line 25:
=Table of Contents=
=Table of Contents=
# Introduction
# Introduction
## Abstract Interpretation and Is Main Applications
## Abstract Interpretation and Its Main Applications
## Basic Set Theory
## Basic Set Theory
## Syntax, Semantics, Properties, and Static Analysis of Expressions
## Syntax, Semantics, Properties, and Static Analysis of Expressions
Line 38: Line 38:
## Undecideability and Rice Theorem
## Undecideability and Rice Theorem
## Posets, Lattices, and Complete Lattices
## Posets, Lattices, and Complete Lattices
## Galois Connections and Abstraction
## [[Galois Connections and Abstraction]]
## Relational and Transformer Semantics
## Relational and Transformer Semantics
## Topology
## Topology

Latest revision as of 01:24, 14 January 2023

Cousot, Patrick (Sep 2021). Principles of Abstract Interpretation. local page: ACM Press. 


Summary

Introduction to abstract interpretation, with examples of applications to the semantics, specification, verification, and static analysis of computer programs.

Formal methods are mathematically rigorous techniques for the specification, development, manipulation, and verification of safe, robust, and secure software and hardware systems. Abstract interpretation is a unifying theory of formal methods that proposes a general methodology for proving the correctness of computing systems, based on their semantics. The concepts of abstract interpretation underlie such software tools as compilers, type systems, and security protocol analyzers. This book provides an introduction to the theory and practice of abstract interpretation, offering examples of applications to semantics, specification, verification, and static analysis of programming languages with emphasis on calculational design.

The book covers all necessary computer science and mathematical concepts—including most of the logic, order, linear, fixpoint, and discrete mathematics frequently used in computer science—in separate chapters before they are used in the text. Each chapter offers exercises and selected solutions. Chapter topics include syntax, parsing, trace semantics, properties and their abstraction, fixpoints and their abstractions, reachability semantics, abstract domain and abstract interpreter, specification and verification, effective fixpoint approximation, relational static analysis, and symbolic static analysis. The main applications covered include program semantics, program specification and verification, program dynamic and static analysis of numerical properties and of such symbolic properties as dataflow analysis, software model checking, pointer analysis, dependency, and typing (both for forward and backward analysis), and their combinations. Principles of Abstract Interpretation is suitable for classroom use at the graduate level and as a reference for researchers and practitioners.

The Seminal Paper on Abstract Intepretation

The seminal paper on Abstract Interpretation is here[1].

Table of Contents

  1. Introduction
    1. Abstract Interpretation and Its Main Applications
    2. Basic Set Theory
    3. Syntax, Semantics, Properties, and Static Analysis of Expressions
  2. Syntax
    1. Syntax
    2. Parsing
  3. Trace Semantics
    1. Structural Deductive Stateless Prefix Trace Semantics
    2. Maximal Trace Semantics
  4. Properties and Their Abstractions
    1. Program Properties
    2. Undecideability and Rice Theorem
    3. Posets, Lattices, and Complete Lattices
    4. Galois Connections and Abstraction
    5. Relational and Transformer Semantics
    6. Topology
    7. Safety and Liveness Trace Properties
  5. Fixpoints and Their Abstractions
    1. Fixpoints
    2. Fixpoint, Deductive, Inductive, Structural, Coinductive, and Bi-inductive Definitions
    3. Structural Fixpoint Prefix and Maximal Trace Semantics
    4. Fixpoint Abstraction
  6. Reachability Semantics
    1. Structural Forward Reachability Semantics
    2. Calculational Design of the Forward Reachability Semantics
  7. Abstract Domain and Abstract Interpreter
    1. Abstract Domain and Abstract Structural Semantics
    2. Chaotic Iterations
    3. Abstract Equational Semantics
  8. Specification and Verification
    1. Fixpoint Induction
    2. Abstract Reachability / Invairiance / Safety Verification Semantics
    3. Hoare Logic
  9. Cartesian Static Analysis
    1. Abstraction
    2. Abstract Cartesian Semantics
    3. Reduction
    4. Basic Number Theory
    5. Cartesian Cogruence Analysis
    6. Dynamic Interval Analysis
    7. Static Interval Analysis
  10. Effective Fixpoint Approximation
    1. Fixpoint Approximation by Extrapolation and Interpolation
    2. Fixpoint Checking
    3. Reduced Product
  11. Relational Static Analysis
    1. Basic Linear Algebra
    2. Linear Equality Analysis
    3. Graphs
    4. Zone and Octagon Analysis
  12. Symbolic Static Analysis
    1. Dataflow Analysis
    2. Stateful Prefix Trace Semantics
    3. Transition Semantics
    4. Software Model Checking
    5. Flow-Intensive Static Analysis
    6. Points-To Analysis
    7. Dependency Analysis
    8. The Herbrand Abstract Domain of Symbolic Terms
    9. Typing
  13. Backward Static Analysis
    1. Backward Accessibility Semantics
    2. Reduced Forward-Backward Analysis
  14. Sound Static Analysis Tools
    1. Semantic Soundness, Completeness, and Definedness
    2. Static Analysis Tools
  15. Conclusion
    1. Conclusion
  16. Bibliography
  17. Author Index
  18. Index
  19. Symbol Index
  20. Project Index
  21. List of Figures

References

  1. ↑ Cousot, Patrick; Cousot, Radhia (1977). Abstract interpretation: a unified lattice model for static analysis of programs by construction or approximation of fixpoints (PDF). 4th POPL. local page: ACM Press. p. 238-252. 

Related Pages

Author:Patrick Cousot

Retrieved from "https://pkc.pub/index.php?title=Book/Principles_of_Abstract_Interpretation&oldid=37742"