CHESS: An Automated Concurrency Testing Tool

Sign in to queue

Description

CHESS is an automated tool from Microsoft Research for finding errors in multithreaded software by systematic exploration of thread schedules. It finds errors, such as data-races, deadlocks, hangs, and data-corruption induced access violations, that are extremely hard to find with current testing tools. Once CHESS locates an error, it provides a fully repeatable execution of the program leading to the error, thus greatly aiding the debugging process. In addition, CHESS provides a valuable and novel notion of test coverage suitable for multithreaded programs. CHESS can use existing concurrent test cases and is therefore easy to deploy. Both developers and testers should find CHESS useful. The CHESS architecture is described in this technical report.

Here, we meet some of the researchers behind CHESS, Madan Musuvathi and Shaz Qadeer. Joining in the conversation are two software test engineers extraordinare, Chris Dern and Rahul Patil. Chris and Rahul use CHESS as part of their daily routine of finding bugs in the various technologies that power Microsoft's Parallel Computing Platform. Tune in and learn about this great technology from the folks who know it best.

Embed

Download

Download this episode

The Discussion

  • User profile image
    kohnie
    Testing ability to post.
  • User profile image
    CKurt
    It's funny how he assumed in his demo that the number of steps per thread would be equal for every thread. Probably to keep the formula simple, but it isn"t the case most of the time, is it ?

    How do you detect when a slot between steps (instuctions) is a valueble place where bugs can happen of another thread changes a value? And what is de difference between een step and a thread ?

    I would love a folowup video!! Thanks Charles
  • User profile image
    Flatliner
    Yeah, something that I was wondering was how do you identify a "pre-emption". i.e. Is it exposing/accessing variables and/or return values from outside critical sections?
  • User profile image
    Madan Musuvathi
    Hi Duke
     We used the formula just to provide intuition for how big the exploration space is with and without preemption bounding. Also, you can think of k as the maximum number of steps in any thread and you would get an upper-bound.
     CHESS uses a lot of algorithms/heuristics to figure out which instruction is a valuable place for preemptions. For instance, we can show it is not necessary to preempt at instructions that do not access shared memory. In fact, you can extend this argument to show that it is only necessary to preempt before synchronization points (lock ops, semaphore ops, CreateThread, ...) and at instructions that participate in a data race.

    madan
  • User profile image
    Madan Musuvathi
    Hi Flatliner
     CHESS adds preemptions during the program execution. CHESS attaches to your program and schedules one thread at a time (like what would happen if your program ran on a uni processor). CHESS then inserts context switches when it stops executing one thread to start executing another thread. There are two kinds of context switches. One that is "forced" on CHESS, when the current thread blocks (on a lock, say) or it dies. The second kind of context switch, called a preemption, is soemthing that CHESS forces on the program. The current thread can continue to execute, but CHESS preempts its execution to switch to another thread. We have found that such unexpected preemptions are the sources of bugs in concurrent programs.

    madan
  • User profile image
    shaz.qadeer

    Response to DukeNukem:

    1.  You are right.  Usually, the number of steps would vary from one thread to another. We can do a similar analysis in terms of the total number of steps in the entire program (summed over all threads).  If s is the total number of steps, n is the number of threads, and c is the preemption-bound, then the total number of executions could be as large as n^s and the number of executions with at most c preemptions is bounded by (s^c)*(n+c)!. 

    2.  There are many options for choosing the control locations for introducing a preemption.  By default, CHESS introduces preemptions at calls to threading and synchronization APIs.  But, a user could instruct the .NET version of CHESS to introduce preemptions at accesses to volatile variables.  Also, you could instrument your code with a callback to CHESS to indicate that CHESS should put a preemption point there.  We are planning to provide more options in the future, including the ability to automatically put a preemption at a variable access in a thread when that access is found to race with a conflicting access in another thread.

    3.  I am not sure I understand your final question.  A thread usually makes a number of steps.  A step in a thread is the execution of code from one context-switch point to the next one.  As explained above, there is flexibility in choosing the locations where CHESS introduces context switches.

  • User profile image
    Luiz Gadetto
    1. Testing this comment!
  • User profile image
    Chris J

    Thanks for producing this video, it solidified a lot of unknowns for me about CHESS. There is one thing I'm still curious about, though -- in what contexts can CHESS be run? Based on the video, it sounds as if CHESS can only be used with defined unit tests -- is this correct? I would like to be able to use CHESS on a running program, but I'm guessing this is not possible since it would not allow CHESS to "re-run" the program with different pre-emption scenarios. Is this true?

     

  • User profile image
    vasilep

    App Verifier lets you attach it to any EXE even a Windows service (daemon). From what I see, CHESS is not there yet. Right?
    If so, are there plans to take it in that direction?

  • User profile image
    Madan Musuvathi
    Hi Chris,
     CHESS is specifically designed for a the unit-testing scenario. Thus, you cannot apply it "out-of-the-box" on existing long-running programs. In return, CHESS can give you guaranteed coverage of interleavings.
     A lot of folks have given similar feedback saying that they would rather give up coverage guarantees if they dont have to refactor their existing tests. we are working on a tool called Cuzz that would serve that purpose. Cuzz would work very much like AppVerifier and you can attach it to any EXE or a windows service.

    madan
  • User profile image
    Madan Musuvathi
    Yup, CHESS is not there yet. We are working on a modified version of CHESS that works like App Verifier - you can attach it to any EXE or a daemon
  • User profile image
    vasilep
    Any ETA for that? Smiley
  • User profile image
    MadHatter


    In the video, there is mention that CHESS works with both managed and unmanaged code.   I downloaded and install CHESS and only see unmanaged code samples.   How does CHESS work with managed code?   Will the team be providing C# samples sometime soon?  The whiteboard explaination really help me better understand the functionality provided by CHESS.   It would be great to see this implemented in a way which does not require any instrumentation of code and could instead by attached to a running process which could be used by a QA team.  Keep up the good work!

  • User profile image
    Tom ball
    Yes. But for the moment, please try out our recent release of CHESS (just live today):


    CHESS is available for download at http://msdn.microsoft.com/en-us/devlabs/cc950526.aspx. CHESS is a tool from Microsoft Research for finding and reproducing concurrency errors. Please download the bits and let us know what you think in our forum. Also, subscribe to our blog for more details and tidbits.

  • User profile image
    Alexander Korol

    Is CHESS able to track context swtiches in new coming Parallel Framework (aka PFX). It seems that due to parallel framework operates with own pool of threads and own scheduling - CHESS it is not applicable in the case of Parallel Framework scheduled Tasks. Thanks.

Add Your 2 Cents