Principles of Abstract Interpretation

by Patrick Cousot

Overview

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.

Product Details

ISBN-13:	9780262361521
Publisher:	MIT Press
Publication date:	09/21/2021
Sold by:	Penguin Random House Publisher Services
Format:	eBook
Pages:	832
File size:	88 MB
Note:	This product may take a few minutes to download.

About the Author

Patrick Cousot is Julius Silver, Roslyn S. Silver, and Enid Silver Winslow Professor in the Computer Science Department at New York University.

Table of Contents

I Introduction
II Syntax
III Trace Semantics
IV Properties and their Abstractions
V Fixpoints and their Abstractions
VI Reachability Semantics
VII Abstract Domain and Abstract Interpreter
VIII Specification and Verification
IX Cartesian Static Analysis 
X Effective Fixpoint Approximation
XI Relational Static Analysis
XII Symbolic Static Analysis
XIII Backward Static Analysis
XIV Sound Static Analysis Tools
XV Conclusion
Bibliography 
Author Index
Index
Symbol Index
Project Index

What People are Saying About This

From the Publisher

“This is a marvelous book that covers both the breadth and the depth of abstract interpretation. Along with definitions, theorems, and proofs, the book is packed with examples, illustrations, and exercises, including solutions to some of the exercises. I plan to use the book for a course on abstract interpretation.”
—Jens Palsberg, Professor of Computer Science, University of California, Los Angeles

“This monumental work by Patrick Cousot is a long-awaited book for the community of programming languages, program analysis, and verification. It is a must-read reference for all researchers and students who want to have an in-depth account of the beautiful theory of abstract interpretation”
—Roberto Giacobazzi, Professor of Computer Science, University of Verona