CHESS: An Automated Concurrency Testing Tool | Going Deep

kohnie

Testing ability to post.

CKurt
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

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

Madan Musuvathi

In reply to CKurt

#Dec 11th, 2008 @ 3:06 PM

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

Madan Musuvathi

In reply to Flatliner

#Dec 12th, 2008 @ 3:29 AM

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

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.

Luiz Gadetto

Testing this comment!

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?

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?