Heuristics for Finding Concurrent Bugs

ieeexplore.ieee.org/iel5/8608/27277/01213514.pdf

 

이 논문은 기존의 white noise방안과 제시하는 new heuristic방안을 비교한다.

- white noise: 모든 혹은 임의 concurrent event의 before/after time에 noise를 invoke하는 방식

- new heuristic: 

1. race condition상태의 shared variable을 찾아서 가장 access rate가 많은 변수를 뽑아 해당 변수에 대한 접근시에 noise를 invoke하는 방식

2. shared variable의 sub variable(영향을 받는 변수들)을 조사하여 이들에 대한 concurrent event가 발생할 때 일명 thread barrier를 설치하여 context switching을 제어하는 방식

3. 각 thread의 scheduling순서를 기억하고 있다가 이에 대한 coverage information을 기반으로 context switching을 제어하는 방식

 

주요 내용 인용

Biased decision policies
The heuristic decision procedure is to focus on the variable that ranks highest and

execute seeded primitives at critical events related to that variable.

 

Scheduing heuristics
Scheduling heuristics use the seeding primitives to cause context switches in

probability at concurrent events related to the chosen global shared variable V.

Instead of choosing one variable, we could have dhosen a subset of variables and

applied scheduling heuristeics to concurrent vents related to that subset. An extreme

case is when all of the program shared variables are chosen. This is called white

noise.

 

- The yield() scheduling heuristic

 

//before or after a concurrent event
while((random*100) < loop-probability)
{
 if((random*100)<yield-probability) Thread.yield;
}

 

- The barrier scheduling heuristic
We try to create interesting interleavings related to a given shared variable by

installing thread barriers before and after accessing the variable. The barrier is

implemented by using a counting semaphore.

The semaphore causes threads to wait just before the shared variable is accessed. When

more than one thread is waiting, then notifyAll() is used to simultaneously advance the

waiting threads.

 

- Comparing the purely coverage based approach and the randomization approach
A specific program access to a variable instance is determined by the program location, the current thread, the variable instance, etc. Thread names and variable instances are scoped to the current run. To identify program instances and thread names, cross-run replay of concurrent programs should be used. RaceFinder currently approximates the program access to avariable instance by its prgram location and variable name.

 

For example, if the race is a write and a read to the same memory location, the scheduling heuristic coverage task would be to obtain both the write before the read and the read before the write. A naive coverage-based sheduling heuristic could miss a concurrent bug whild obtaining the required coverage.

 

Analysis
Once the correct variable is focused on, both the yield() and barrier scheduling heuristics manifest the bug more often than white noise. Thus, in cases where the total measure pinpoints the raced shared variable, the biased heuristics are better than white noise.