Exploiting Domain and Program Structure to Synthesize Efficient and Precise Data Flow Analyses (T)

A key challenge in implementing an efficient and precise ¹ data flow analysis is determining how to abstract the domain of values that a program variable can take on and how to update abstracted values to reflect program semantics. Such updates are performed by a transfer function and recent work by Thakur, Elder and Reps [26] defined the bilateral algorithm for computing the most precise transfer function for a given abstract domain.

In this paper, we identify and exploit the special case where abstract domains are comprised of disjoint subsets. For such domains, transfer functions computed using a customized algorithm can improve performance and in combination with symbolic modeling of block-level transfer functions improve precision as well. We implemented these algorithms in Soot and used them to perform data flow analysis on more than 100 non-trivial Java methods drawn from open source projects. Our experimental data are promising as they demonstrate that a 25-fold reduction in analysis time can be achieved and precision can be increased relative to existing methods.