2008 23rd Annual IEEE Symposium on Logic in Computer Science Parameterization as Abstraction: A Tractable Approach to the Dataflow Analysis of Concurrent Programs June 24-June 27 ISBN: 978-0-7695-3183-0
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/LICS.2008.37
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.
Index Terms:
Dataflow Analysis, Concurrent Programs, Parameterized Systems, Pushdown Systems, Model Checking
Citation:
Vineet Kahlon, "Parameterization as Abstraction: A Tractable Approach to the Dataflow Analysis of Concurrent Programs," lics, pp.181-192, 2008 23rd Annual IEEE Symposium on Logic in Computer Science, 2008 Usage of this product signifies your acceptance of the Terms of Use. | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||