[pl-seminar] PL Seminar Wednesday, 7 July.

[Matt Elder <elder@xxxxxxxxxxx>]

Nicholas Kidd, Purdue University:
Path-Sensitive Analysis using Edge Strings

Wednesday, 7 July 2010
4:00 pm in CS 3310

Abstract:

Path sensitivity improves the quality of static analysis by avoiding
approximative merging of dataflow facts collected along distinct
program paths.  Because full path sensitivity has prohibitive cost, it
is worthwhile to consider hybrid approaches that provide path
sensitivity on selected subsets of paths.  We consider such a
technique based on an edge string, a compact abstraction of a set of
static program paths.  The edge string E=[e_1,e_2,...,e_k], where each
e_i is an edge label found in a program's control-flow graph, is used
to disambiguate dataflow facts that occur only on paths in which E
occurs as a subsequence.  Loosely speaking, edge strings are a
path-sensitive analog to the notion of call-strings exploited by
context-sensitive analyses.  Experimental evaluation indicates that
edge strings provide an efficient technique to identify infeasible
paths for functional programs that leverage complex control and
dataflow structures.