Entries:
Comments:
Posts:

Loading User Information from Channel 9

Something went wrong getting user information from Channel 9

Latest Achievement:

Loading User Information from MSDN

Something went wrong getting user information from MSDN

Visual Studio Achievements

Latest Achievement:

Loading Visual Studio Achievements

Something went wrong getting the Visual Studio Achievements

CHESS: An Automated Concurrency Testing Tool

Download

Right click “Save as…”

  • High Quality WMV (PC)
  • MP3 (Audio only)
  • MP4 (iPhone, Android)
  • Mid Quality WMV (Lo-band, Mobile)
  • WMV (WMV Video)
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.

Tags:

Follow the Discussion

  • Testing ability to post.
  • CKurtCKurt while( ( !​succeed=try​() ) ) { }
    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
  • FlatlinerFlatliner With our thoughts we make the world.
    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?
  • 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
  • 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
  • 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.

    1. Testing this comment!
  • 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?

     

  • 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?

  • 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
  • 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
  • Any ETA for that? Smiley

  • 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!

  • 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.

  • 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.

Remove this comment

Remove this thread

close

Comments Closed

Comments have been closed since this content was published more than 30 days ago, but if you'd like to continue the conversation, please create a new thread in our Forums,
or Contact Us and let us know.