Context-Bounded Analysis for Concurrent Programs with Dynamic Creation of Threads

Context-bounded analysis has been shown to be both efficient and

effective at finding bugs in concurrent programs. According to its original definition,

context-bounded analysis explores all behaviors of a concurrent program

up to some fixed number of context switches between threads. This definition is

inadequate for programs that create threads dynamically because bounding the

number of context switches in a computation also bounds the number of threads

involved in the computation. In this paper, we propose a more general definition

of context-bounded analysis useful for programs with dynamic thread creation.

The idea is to bound the number of context switches for each thread instead of

bounding the number of switches of all threads. We consider several variants

based on this new definition, and we establish decidability and complexity results

for the analysis induced by them.

AtBQ09.pdf
PDF file

In  Conference on Tools and Algorithms for the Construction and Analysis of Systems

Publisher  Springer Verlag
All copyrights reserved by Springer 2007.

Details

TypeInproceedings
> Publications > Context-Bounded Analysis for Concurrent Programs with Dynamic Creation of Threads