Paper: Parameterization as Abstraction: A Tractable Approach to the Dataflow Analysis of Concurrent Programs (at LICS 2008)

Authors: Vineet Kahlon

Abstract

Dataflow analysis for concurrent programs is a problem of critical importance but, unfortunately, also an undecidable one. A key obstacle is to determine precisely how dataflow facts at a location in a given thread could be affected by operations of other threads.This problem, in turn, boils down to pairwise reachability, i.e., given program locations $c_1$ and $c_2$ in two threads $T_1$ and $T_2$, respectively, determining whether $c_1$ and $c_2$ are simultaneously reachable in the presence of constraints imposed by synchronization primitives. Unfortunately, pairwise reachability is undecidablefor most synchronization primitives. However, we leverage the surprising result that the closely related problem of parameterized pairwise reachability of $c_1$ and $c_2$, i.e., whether for some $n_1$ and $n_2$, $c_1$ and $c_2$ are simultaneously reachable in the program $T_1^{n_1}\|T_2^{n_2}$ comprised of $n_1$ copies of $T_1$ and $n_2$ copies of $T_2$,is not only decidable for many primitives, but efficiently so. Although parameterization makes pairwise reachability tractable it may over-approximate the set of pairwise reachable locations and can, therefore, be looked upon as an abstraction technique.Where as abstract interpretation is used for control and data abstractions, we propose the use of parameterization as an abstraction for concurrency. Leveraging abstract interpretation in conjunction with parameterization allows us to lift two desirable properties of sequential dataflow analysis to the concurrent domain, i.e., precision and scalability.

BibTeX

  @InProceedings{Kahlon-ParameterizationasA,
    author = 	 {Vineet Kahlon},
    title = 	 {Parameterization as Abstraction: A Tractable Approach to the Dataflow Analysis of Concurrent Programs},
    booktitle =  {Proceedings of the Twenty-Third Annual IEEE Symposium on Logic in Computer Science (LICS 2008)},
    year =	 {2008},
    month =	 {June}, 
    pages =      {181--192},
    location =   {Pittsburgh, PA, USA}, 
    publisher =	 {IEEE Computer Society Press}
  }