% abstract.tex
% Author: James Ezick
% Revised: 10 June 2004
A context-sensitive analysis is an analysis in which program elements are
assigned sets of properties that depend upon the context in which they
occur. For analyses on imperative languages, this often refers to
considering the behavior of statements in a called procedure with respect
to the call-stack that generated the procedure invocation. Algorithms for
performing or approximating these types of analyses make up the core of
interprocedural program analysis and are pervasive, having applications in
program comprehension, optimization, and verification. However, for many
of these applications what is of interest is the solution to the dual
problem: given a vertex and a desirable set of properties, what is the set
of potential stack-contexts leading to that vertex that results in the
desirable property set? Many techniques, such as procedure cloning, have
been developed to approximately partition the set of stack-contexts leading
to a vertex according to such a condition. This paper introduces a broad
generalization of this problem referred to as a constraint query on the
analysis. This generalization allows sophisticated constraints to be
placed on both the desirable property set as well as the set of interesting
stack-contexts. From these constraints, a novel technique based on
manipulating regular languages is introduced that efficiently produces a
concise representation of the exact set of stack-contexts solving this dual
problem subject to the constraints. This technique is applied to a pair of
emerging software engineering challenges - resolving program comprehension
queries over aggregate collections of properties and statically modifying
code to enforce a safety policy decidable by the analysis. Practical
examples of both applications are presented along with empirical results.