Context-Bounded Analysis For Concurrent Programs With Dynamic Creation of Threads
Authors:
- Mohamed Faouzi AtigMAMohamed Faouzi Atig
- Ahmed BouajjaniABAhmed Bouajjani
- Shaz QadeerSQShaz Qadeer
Open Access
- 23 November 2011
- journal article
- Published by Centre pour la Communication Scientifique Directe (CCSD) in Logical Methods in Computer Science
- Vol. ume 7, Iss
Abstract
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.Keywords
All Related Versions
This publication has 22 references indexed in Scilit:
- Reducing Context-Bounded Concurrent Reachability to Sequential Reachability2009
- Reducing Concurrent Analysis Under a Context Bound to Sequential AnalysisLecture Notes in Computer Science, 2008
- Verification of Boolean programs with unbounded thread creationTheoretical Computer Science, 2007
- Expand, Enlarge and Check: New algorithms for the coverability problem of WSTSJournal of Computer and System Sciences, 2006
- Regular Symbolic Analysis of Dynamic Networks of Pushdown SystemsLecture Notes in Computer Science, 2005
- Reachability Analysis of Multithreaded Software with Asynchronous Communication2005
- On Computing Reachability Sets of Process Rewrite SystemsLecture Notes in Computer Science, 2005
- A Complete Abstract Interpretation Framework for Coverability Properties of WSTS2005
- Reachability Analysis of Process Rewrite SystemsLecture Notes in Computer Science, 2003
- Efficient algorithms for pre* and post* on interprocedural parallel flow graphs2000