Survey of Constraint-based Program Analysis
Nathan Brunelle · 2011
When writing a program, the programmers may wish to verify certain properties of this program. For example, will my variable X always be an integer? To answer these questions we use program analysis. Constraint-based program analysis is a form of static program analysis. This means that all of these questions about the program’s run-time behavior are answered at compile time. This paper seeks to provide a survey of constraint-based program analysis including: a description of the approach, research done on the topic, applications of the topic, and future directions. 1. Introduction The idea for constraint-based program analysis was first introduce by John C. Reynolds in 1969 in his paper Automatic Computation of Data Set Definitions [12]. At the time, systems which provide fast and flexible data representations require the programmer to give the range of variables, parameters, and functions by detailed data structure definitions. Reynolds’s insight was that this information is redundant, as much of it can be inferred. His paper discusses a method for giving data set description of the output and input of a function given the program of the function, this was done specifically in the LISP programming language. This idea has been expanded into the modern program analysis approach of constraint-based program analysis. The rest of the paper will primarily focus on the most common form, set constraint-based program analysis, but others will be mentioned.