Mohamed Faouzi Atig ; Ahmed Bouajjani ; Shaz Qadeer - Context-Bounded Analysis For Concurrent Programs With Dynamic Creation of Threads

lmcs:708 - Logical Methods in Computer Science, November 23, 2011, Volume 7, Issue 4 - https://doi.org/10.2168/LMCS-7(4:4)2011
Context-Bounded Analysis For Concurrent Programs With Dynamic Creation of Threads

Authors: Mohamed Faouzi Atig ; Ahmed Bouajjani ; Shaz Qadeer

    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.


    Volume: Volume 7, Issue 4
    Published on: November 23, 2011
    Accepted on: June 25, 2015
    Submitted on: January 31, 2010
    Keywords: Computer Science - Logic in Computer Science,D.2.4, D.3.1, F.4.3, I.2.2

    Linked data

    Source : ScholeXplorer References DOI 10.1145/1250734.1250785
    Source : ScholeXplorer References DOI 10.1145/1273442.1250785
    • 10.1145/1273442.1250785
    • 10.1145/1273442.1250785
    • 10.1145/1250734.1250785
    • 10.1145/1250734.1250785
    Iterative context bounding for systematic testing of multithreaded programs
    Musuvathi, Madanlal ; Qadeer, Shaz ;

    26 Documents citing this article

    Share

    Consultation statistics

    This page has been seen 433 times.
    This article's PDF has been downloaded 228 times.