Parametric and Termination-Sensitive Control Dependence

From FSL
Jump to: navigation, search

This work has been published both as a conference paper (SAS'06) and as a technical report; the technical report contains all the proofs that have been omitted from the conference paper. The termination-sensitive control dependence was originally inspired by our work on predictive runtime analysis. The interested reader can also find the implemented algorithm in the termination-sensitive control dependence webpage.

SAS'06

Parametric and Termination-Sensitive Control Dependence - Extended Abstract
Feng Chen and Grigore Rosu
SAS'06, LNCS 4134, pp 387-404. 2006.
Abstract. A parametric approach to control dependence is presented, where the parameter is any prefix-invariant property on paths in the control-flow graph (CFG). Existing control dependencies, both direct and indirect, can be obtained as instances of the parametric framework for particular properties on paths. A novel control dependence relation, called termination-sensitive control dependence, is obtained also as an instance of the parametric framework. This control dependence is sensitive to the termination information of loops, which can be given via annotations. If all loops are annotated as terminating then it becomes the classic control dependence, while if all loops are annotated as non-terminating then it becomes the weak control dependence; since in practice some loops are terminating and others are not, termination-sensitive control dependence is expected to improve the precision of analysis tools using it. The unifying formal framework for direct and indirect control dependence suggests also, in a natural way, a unifying terminology for the various notions of control dependence, which is also proposed in this paper. Finally, a worst-case O(n^2) algorithm to compute the indirect termination-sensitive control dependence for languages that allow only “structured” jumps (i.e., ones that do not jump into the middle of a different block), such as Java and C#, is given, avoiding the O(n^3) complexity of the trivial algorithm calculating the transitive closure of the direct dependence.
PDF, LNCS, SAS'06, BIB


Technical Report

Parametric and Termination-Sensitive Control Dependence
Feng Chen and Grigore Rosu
Technical report UIUCDCS-R-2006-2712, April 2006
Abstract. A parametric approach to control dependence is presented, where the parameter is any prefix-invariant property on paths in the control-flow graph. Existing control dependencies, both direct and indirect, can be obtained as instances of the parametric framework for particular properties on paths. A novel control dependence relation, called termination-sensitive control dependence, is obtained also as an instance of the parametric framework. This control dependence is sensitive to the termination information of loops, which can be given as annotations on loops. If all loops are annotated as terminating then it becomes the classic control dependence, while if all loops are annotated as non-terminating then it becomes the weak control dependence; since in practice some loops are terminating and others are not, termination-sensitive control dependence is expected to improve the precision of analysis tools using it. The unifying formal framework for direct and indirect control dependencies suggests also, in a natural way, a unifying terminology for the various notions of control dependency, which is also proposed in this paper. Finally, a worst-case O(n^2) algorithm to compute the indirect termination-sensitive control dependence for languages like Java and C# is given, avoiding the O(n^3) complexity of the trivial algorithm calculating the transitive closure of the direct dependence.
PDF, TR@UIUC, BIB

Personal tools
Namespaces

Variants
Actions
Navigation