Principles of Program Analysis | springerprofessional.de

Springer Professional

nach oben

1999 | Buch

Kapitel lesen Erstes Kapitel lesen

Principles of Program Analysis

verfasst von: Flemming Nielson, Hanne Riis Nielson, Chris Hankin

Verlag: Springer Berlin Heidelberg

Enthalten in: Professional Book Archive

Einloggen, um Zugang zu erhalten

Über dieses Buch

Program analysis concerns static techniques for computing reliable approximate information about the dynamic behaviour of programs. Applications include compilers (for code improvement), software validation (for detecting errors in algorithms or breaches of security) and transformations between data representation (for solving problems such as the Y2K problem). This book is unique in giving an overview of the four major approaches to program analysis: data flow analysis, constraint based analysis, abstract interpretation, and type and effect systems. The presentation demonstrates the extensive similarities between the approaches; this will aid the reader in choosing the right approach and in enhancing it with insights from the other approaches. The book covers basic semantic properties as well as more advanced algorithmic techniques. The book is aimed at M.Sc. and Ph.D. students but will be valuable also for experienced researchers and professionals.

Anzeige

Inhaltsverzeichnis

Frontmatter

Chapter 1. Introduction

Abstract

In this book we shall introduce four of the main approaches to program analysis: Data Flow Analysis, Constraint Based Analysis, Abstract Interpretation, and Type and Effect Systems. Each of Chapters 2 to 5 deals with one of these approaches at some length and generally treats the more advanced material in later sections. Throughout the book we aim at stressing the many similarities between what may at a first glance appear to be very unrelated approaches. To help to get this idea across, and to serve as a gentle introduction, this chapter treats all of the approaches at the level of examples. The technical details are worked out but it may be difficult to apply the techniques to related examples until some of the material of later chapters has been studied.

Flemming Nielson, Hanne Riis Nielson, Chris Hankin

Chapter 2. Data Flow Analysis

Abstract

In this chapter we introduce techniques for Data Flow Analysis. Data Flow Analysis is the traditional form of program analysis which is described in many textbooks on compiler writing. We will present analyses for the simple imperative language While that was introduced in Chapter 1. This includes a number of classical Data Flow Analyses: Available Expressions, Reaching Definitions, Very Busy Expressions and Live Variables. We introduce an operational semantics for While and demonstrate the correctness of the Live Variables Analysis. We then present the notion of Monotone Frameworks and show how the examples may be recast as such frameworks. We continue by presenting a worklist algorithm for solving flow equations and we study its termination and correctness properties. The chapter concludes with a presentation of some advanced topics, including Interprocedural Data Flow Analysis and Shape Analysis.

Flemming Nielson, Hanne Riis Nielson, Chris Hankin

Chapter 3. Constraint Based Analysis

Abstract

In this chapter we present the technique of Constraint Based Analysis using a simple functional language, FUN. We begin by presenting an abstract specification of a Control Flow Analysis and then study its theoretical properties: it is correct with respect to a Structural Operational Semantics and it can be used to analyse all programs. This specification of the analysis does not immediately lend itself to an efficient algorithm for computing a solution so we proceed by developing first a syntax directed specification and then a constraint based formulation and finally we show how the constraints can be solved. We conclude by illustrating how the precision of the analysis can be improved by combining it with Data Flow Analysis and by incorporating context information thereby linking up with the development of the previous chapter.

Flemming Nielson, Hanne Riis Nielson, Chris Hankin

Chapter 4. Abstract Interpretation

Abstract

The purpose of this chapter is to convey some of the essential ideas of Abstract Interpretation. We shall mainly do so in a programming language independent way and thus focus on the design of the property spaces, the functions and computations upon them, and the relationships between them.

Flemming Nielson, Hanne Riis Nielson, Chris Hankin

Chapter 5. Type and Effect Systems

Abstract

So far our techniques have applied equally well to typed and untyped programming languages. This flexibility does not apply to the development to be performed in this chapter: here we demand that our programming language is typed because we will use the syntax for types in order to express the program analysis properties of interest (as was already illustrated in Section 1.6).

Flemming Nielson, Hanne Riis Nielson, Chris Hankin

Chapter 6. Algorithms

Abstract

In previous chapters we have studied several algorithms for obtaining solutions of program analyses. In this chapter we shall explore further the similarities between the different approaches to program analysis by studying general algorithms for solving equation or inequation systems.

Flemming Nielson, Hanne Riis Nielson, Chris Hankin

Backmatter

Titel: Principles of Program Analysis
verfasst von: Flemming Nielson
Hanne Riis Nielson
Chris Hankin
Copyright-Jahr: 1999
Verlag: Springer Berlin Heidelberg
Electronic ISBN: 978-3-662-03811-6
Print ISBN: 978-3-642-08474-4
DOI: https://doi.org/10.1007/978-3-662-03811-6