ENGLISH

Introduction to Static Analysis

By Xavier Rival , Kwangkeun Yi

Book information

Publisher
The MIT Press
Year
2020
ISBN
9780262043410
Language
english
Format
PDF
Filesize
7 MB (7306490 bytes)
Pages
320\400
Time added
2023-02-18 07:05:54

Description

Copyright Preface 1 Program Analysis 1.1 Understanding Software Behavior 1.2 Program Analysis Applications and Challenges 1.3 Concepts in Program Analysis 1.3.1 What to Analyze 1.3.2 Static versus Dynamic 1.3.3 A Hard Limit: Uncomputability 1.3.4 Automation and Scalability 1.3.5 Approximation: Soundness and Completeness 1.4 Families of Program Analysis Techniques 1.4.1 Testing: Checking a Set of Finite Executions 1.4.2 Assisted Proof: Relying on User-Supplied Invariants 1.4.3 Model Checking: Exhaustive Exploration of Finite Systems 1.4.4 Conservative Static Analysis: Automatic, Sound, and Incomplete Approach 1.4.5 Bug Finding: Error Search, Automatic, Unsound, Incomplete, Based on Heuristics 1.4.6 Summary 1.5 Roadmap 2 A Gentle Introduction to Static Analysis 2.1 Semantics and Analysis Goal: A Reachability Problem 2.2 Abstraction 2.3 A Computable Abstract Semantics: Compositional Style 2.3.1 Abstraction of Initialization 2.3.2 Abstraction of Post-Conditions 2.3.3 Abstraction of Non-Deterministic Choice 2.3.4 Abstraction of Non-Deterministic Iteration 2.3.5 Verification of the Property of Interest 2.4 A Computable Abstract Semantics: Transitional Style 2.4.1 Semantics as State Transitions 2.4.2 Abstraction of States 2.4.3 Abstraction of State Transitions 2.4.4 Analysis by Global Iterations 2.5 Core Principles of a Static Analysis 3 A General Static Analysis Framework Based on a Compositional Semantics 3.1 Semantics 3.1.1 A Simple Programming Language 3.1.2 Concrete Semantics 3.2 Abstractions 3.2.1 The Concept of Abstraction 3.2.2 Non-Relational Abstraction 3.2.3 Relational Abstraction 3.3 Computable Abstract Semantics 3.3.1 Abstract Interpretation of Assignment 3.3.2 Abstract Interpretation of Conditional Branching 3.3.3 Abstract Interpretation of Loops 3.3.4 Putting Everything Together 3.4 The Design of an Abstract Interpreter 4 A General Static Analysis Framework Based on a Transitional Semantics 4.1 Semantics as State Transitions 4.1.1 Concrete Semantics 4.1.2 Recipe for Defining a Concrete Transitional Semantics 4.2 Abstract Semantics as Abstract State Transitions 4.2.1 Abstraction of the Semantic Domain 4.2.2 Abstraction of Semantic Functions 4.2.3 Recipe for Defining an Abstract Transition Semantics 4.3 Analysis Algorithms Based on Global Iterations 4.3.1 Basic Algorithms 4.3.2 Worklist Algorithm 4.4 Use Example of the Framework 4.4.1 Simple Imperative Language 4.4.2 Concrete State Transition Semantics 4.4.3 Abstract State 4.4.4 Abstract State Transition Semantics 5 Advanced Static Analysis Techniques 5.1 Construction of Abstract Domains 5.1.1 Abstraction of Boolean-Numerical Properties 5.1.2 Describing Conjunctive Properties 5.1.3 Describing Properties Involving Case Splits 5.1.4 Construction of an Abstract Domain 5.2 Advanced Iteration Techniques 5.2.1 Loop Unrolling 5.2.2 Fixpoint Approximation with More Precise Widening Iteration 5.2.3 Refinement of an Abstract Approximation of a Least Fixpoint 5.3 Sparse Analysis 5.3.1 Exploiting Spatial Sparsity 5.3.2 Exploiting Temporal Sparsity 5.3.3 Precision-Preserving Def-Use Chain by Pre-Analysis 5.4 Modular Analysis 5.4.1 Parameterization, Summary, and Scalability 5.4.2 Case Study 5.5 Backward Analysis 5.5.1 Forward Semantics and Backward Semantics 5.5.2 Backward Analysis and Applications 5.5.3 Precision Refinement by Combined Forward and Backward Analysis 6 Practical Use of Static Analysis Tools 6.1 Analysis Assumptions and Goals 6.2 Setting Up the Static Analysis of a Program 6.2.1 Definition of the Source Code and Proof Goals 6.2.2 Parameters to Guide the Analysis 6.3 Inspecting Analysis Results 6.4 Deployment of a Static Analysis Tool 7 Static Analysis Tool Implementation 7.1 Concrete Semantics and Concrete Interpreter 7.2 Abstract Domain Implementation 7.3 Static Analysis of Expressions and Conditions 7.4 Static Analysis Based on a Compositional Semantics 7.5 Static Analysis Based on a Transitional Semantics 8 Static Analysis for Advanced Programming Features 8.1 For a Language with Pointers and Dynamic Memory Allocations 8.1.1 Language and Concrete Semantics 8.1.2 An Abstract Semantics 8.2 For a Language with Functions and Recursive Calls 8.2.1 Language and Concrete Semantics 8.2.2 An Abstract Semantics 8.3 Abstractions for Data Structures 8.3.1 Arrays 8.3.2 Buffers and Strings 8.3.3 Pointers 8.3.4 Dynamic Heap Allocation 8.4 Abstraction for Control Flow Structures 8.4.1 Functions and Procedures 8.4.2 Parallelism 9 Classes of Semantic Properties and Verification by Static Analysis 9.1 Trace Properties 9.1.1 Safety 9.1.2 Liveness 9.1.3 General Trace Properties 9.2 Beyond Trace Properties: Information Flows and Other Properties 10 Specialized Static Analysis Frameworks 10.1 Static Analysis by Equations 10.1.1 Data-Flow Analysis 10.2 Static Analysis by Monotonic Closure 10.2.1 Pointer Analysis 10.2.2 Higher-Order Control-Flow Analysis 10.3 Static Analysis by Proof Construction 10.3.1 Type Inference 11 Summary and Perspectives A Reference for Mathematical Notions and Notations A.1 Sets A.2 Logical Connectives A.3 Definitions and Proofs by Induction A.4 Functions A.5 Order Relations and Ordered Sets A.6 Operators over Ordered Structures and Fixpoints B Proofs of Soundness B.1 Properties of Galois Connections B.2 Proofs of Soundness for Chapter B.2.1 Soundness of the Abstract Interpretation of Expressions B.2.2 Soundness of the Abstract Interpretation of Conditions B.2.3 Soundness of the Abstract Join Operator B.2.4 Abstract Iterates with Widening B.2.5 Soundness of the Abstract Interpretation of Commands B.3 Proofs of Soundness for Chapter B.3.1 Transitional-Style Static Analysis over Finite-Height Domains B.3.2 Transitional-Style Static Analysis with Widening B.3.3 Use Example of the Transitional-Style Static Analysis Bibliography Index

Similar books

Session C11: Ancient Cultural Landscapes in South Europe – their Ecological Setting and Evolution, Session C22: Gardeners from South America, Session S04: Agro-Pastoralism and Early Metallurgy Sessions, Session WS29: The Idea of Enclosure in Recent Iberian Prehistory, Session C88: Rhytmes et causalites des dynamiques de l'anthropisation en Europe entre 6500 ET 500 BC: Hypotheses socio-culturelles et/ou climatiques: Proceedings of the XV UISPP World Congress (Lisbon 4-9 September 2006) / Actes du XV Congrès Mondial (Lisbonne 4-9 Septembre 2006) Vol.36

Session C11: Ancient Cultural Landscapes in South Europe – their Ecological Setting and Evolution, Session C22: Gardeners from South America, Session S04: Agro-Pastoralism and Early Metallurgy Sessions, Session WS29: The Idea of Enclosure in Recent Iberian Prehistory, Session C88: Rhytmes et causalites des dynamiques de l'anthropisation en Europe entre 6500 ET 500 BC: Hypotheses socio-culturelles et/ou climatiques: Proceedings of the XV UISPP World Congress (Lisbon 4-9 September 2006) / Actes du XV Congrès Mondial (Lisbonne 4-9 Septembre 2006) Vol.36

2010 · PDF

THE BRITISH ARMY IN INDIA: ITS PRESERVATION BY AN APPROPRIATE CLOTHING, HOUSING, LOCATING, RECREATIVE EMPLOYMENT, AND HOPEFUL ENCOURAGEMENT OF THE TROOPS. with AN APPENDIX ON INDIA : THE CLIMATE OP ITS HILLS ; THE DEVELOPMENT OF ITS RESODRCBS, INDUSTRY, AND ARTS ; THE ADMINISTRATION OF JUSTICE ; THE BLACK ACT ; THE PROGRESS OF CHRISTIANITY ; THE TRAFFIC IN OPIUM ; THE VALUE OF INDIA ; PERMANENT CAUSES OF DISAFFECTION, AND OF THE RECENT REBELLION ; THE TRADITIONARY POLICY; MISGOVERNMENT BY NATIVE RULERS ; ANNEXATIONS OF THEIR TERRITORY, ETC.

THE BRITISH ARMY IN INDIA: ITS PRESERVATION BY AN APPROPRIATE CLOTHING, HOUSING, LOCATING, RECREATIVE EMPLOYMENT, AND HOPEFUL ENCOURAGEMENT OF THE TROOPS. with AN APPENDIX ON INDIA : THE CLIMATE OP ITS HILLS ; THE DEVELOPMENT OF ITS RESODRCBS, INDUSTRY, AND ARTS ; THE ADMINISTRATION OF JUSTICE ; THE BLACK ACT ; THE PROGRESS OF CHRISTIANITY ; THE TRAFFIC IN OPIUM ; THE VALUE OF INDIA ; PERMANENT CAUSES OF DISAFFECTION, AND OF THE RECENT REBELLION ; THE TRADITIONARY POLICY; MISGOVERNMENT BY NATIVE RULERS ; ANNEXATIONS OF THEIR TERRITORY, ETC.

1858 · PDF

Idries Shah 27 Books Collection : A Perfumed Scorpion, A Veiled Gazelle, Caravan of Dreams, Darkest England, Destination Mecca, Evenings with Idries Shah, Knowing How to Know, Learning How to Learn, Letters and Lectures of Idries Shah, Neglected aspects of Sufi study, Observations, Oriental Magic, Reflections, Seeker after Truth, Special Illumination, Special Problems in the study of Sufi ideas, Sufi thought and action, Tales of the Dervishes, The Dermis Probe, The Elephant in the Dark, The Englishman Handbook, Idries Shah Antology, The Magic Monastery, The natives are restless, wisdom of the Idiots PDF.

Idries Shah 27 Books Collection : A Perfumed Scorpion, A Veiled Gazelle, Caravan of Dreams, Darkest England, Destination Mecca, Evenings with Idries Shah, Knowing How to Know, Learning How to Learn, Letters and Lectures of Idries Shah, Neglected aspects of Sufi study, Observations, Oriental Magic, Reflections, Seeker after Truth, Special Illumination, Special Problems in the study of Sufi ideas, Sufi thought and action, Tales of the Dervishes, The Dermis Probe, The Elephant in the Dark, The Englishman Handbook, Idries Shah Antology, The Magic Monastery, The natives are restless, wisdom of the Idiots PDF.

2022 · PDF

The travels of Capts. Lewis and Clarke from St. Louis, by way of the Missouri and Columbia rivers, to the Pacific ocean; performed in the years 1804, 1805 & 1806, by order of the government of the United States. Containing delineations of the manners, customs, religion, &c. of the Indians, comp. from various authentic sources, and original documents, and a summary of the Statistical view of the Indian nations, from the official communication of Meriwether Lewis. Illustrated with a map of the country, inhabited by the western tribes of Indians

The travels of Capts. Lewis and Clarke from St. Louis, by way of the Missouri and Columbia rivers, to the Pacific ocean; performed in the years 1804, 1805 & 1806, by order of the government of the United States. Containing delineations of the manners, customs, religion, &c. of the Indians, comp. from various authentic sources, and original documents, and a summary of the Statistical view of the Indian nations, from the official communication of Meriwether Lewis. Illustrated with a map of the country, inhabited by the western tribes of Indians

1809 · PDF

Professional Linux kernel architecture ''Wrox programmer to programmer''--Cover. - ''What you are reading right now is the result of an evolution over more than seven years: After two years of writing, the first edition was published in German by Carl Hanser Verlag in 2003. It then described kernel 2.6.0. The test was used as a basis for the low-level design documentation for the EAL4+ security evaluation of Red Hat Enterprise Linux 5, requiring to update it to kernel 2.6.18 (if the EAL acronym does not mean anything to you, then Wikipedia is once more your friend). Hewlett-Packard sponsored the translation into English and has, thankfully, granted the rights to publish the result. Updates to kernel 2.6.24 were then performed specifically for this book''--P. ix

Professional Linux kernel architecture ''Wrox programmer to programmer''--Cover. - ''What you are reading right now is the result of an evolution over more than seven years: After two years of writing, the first edition was published in German by Carl Hanser Verlag in 2003. It then described kernel 2.6.0. The test was used as a basis for the low-level design documentation for the EAL4+ security evaluation of Red Hat Enterprise Linux 5, requiring to update it to kernel 2.6.18 (if the EAL acronym does not mean anything to you, then Wikipedia is once more your friend). Hewlett-Packard sponsored the translation into English and has, thankfully, granted the rights to publish the result. Updates to kernel 2.6.24 were then performed specifically for this book''--P. ix

2008 · PDF