CHESS: An Automated Concurrency Testing Tool

The Discussion

• 

  Testing ability to post.

• 

  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
  

• 

  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?

• 

  
  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.