Discovering Techniques for Detecting Deadlock Bugs in Concurrent Programs

 
Deadlock Bug Detection Techniques
 
Prof. Moonzoo Kim
CS KAIST
 
CS492B Analysis of Concurrent Programs
 
1
Bug Detection Techniques for
Concurrent Programs
1,000,000 LOC <
100~1,000 LOC
Precision
rstest
rstest
ConTest
ConTest
MetaL
MetaL
RacerX
RacerX
Java PathFinder
Java PathFinder
jCute
jCute
CHESS
CHESS
SPIN
SPIN
CalFuzzer
CalFuzzer
Atomizer
Atomizer
 Eraser
 Eraser
Fusion
Fusion
KISS
KISS
Scalability
Verification
False alarm
Model checking techniques
+  High precision
+  Comprehensive error detection
-  Scalability
   (state explosion problem)
-  Verification expertise is required
Testing techniques
+  High precision
+  Friendly to developers
-  Difficult to generate
   test cases and thread schedules
Bug detection techniques
+ Fast and convenient
   (no need to generate many
    executions)
-
  False alarms
2
CS492B Analysis of Concurrent Programs, Prof. Moonzoo Kim
 
Deadlock Bugs Frequently Occur in Real World
 
•
In a survey on 105 real-world concurrency bugs in open-
source applications, 
31 out of 105 bugs are deadlock bugs
[Lu 
et al
., ASPLOS 08]
 
3
 
CS492B Analysis of Concurrent Programs, Prof. Moonzoo Kim
 
Deadlock Bugs Frequently Occur in Real World
 
•
According to Apache
bug tracking systems,
there have been  
200
deadlock related issues
since 2014
 
4
 
CS492B Analysis of Concurrent Programs, Prof. Moonzoo Kim
Deadlock
•
A deadlock occurs when each of a set of threads
is blocked, waiting for another thread in the set
to satisfy certain condition
 
 
5
CS492B Analysis of Concurrent Programs, Prof. Moonzoo Kim
 
release shared resource
 
raise event
Resource Deadlock
•
Ex. Dining philosopher problem
1.
Think
2.
If left fork is available,
pick it up
3.
If right fork is available,
pick it up
4.
Eat
5.
Put the right folk down
6.
Put the left folk down
 
 
Folk#1
Folk#2
6
CS492B Analysis of Concurrent Programs, Prof. Moonzoo Kim
Resource
 Deadlock in Concurrent Programs
•
ABBA deadlock
 
      
t1: Thread 1
1
:lock(X)
2:x = …
 
3
:lock(Y)
 
t2: Thread 2
 
11:
lock(Y)
12:y=...
 
13
:lock(X)
 
  Thread1() {
1: 
lock(
X
)
2: x = … ;
3: 
lock(
Y
)
4: y = … ;
5: 
unlock(
Y
)
6: 
unlock(
X
)
  }
  Thread2() {
11: 
lock(
Y
)
12: y = … ;
13: 
lock(
X
)
14: x = … ;
15: 
unlock(
X
)
16: 
unlock(
Y
)
  }
7
CS492B Analysis of Concurrent Programs, Prof. Moonzoo Kim
 
Non-blocking Algorithm
 
•
An algorithm is called 
non-blocking
 if failure or suspension of any thread
cannot
 cause failure or suspension of another thread
–
a non-blocking algorithm is lock-free if there is guaranteed system-wide
progress, and wait-free if there is also guaranteed per-thread progress.
•
Blocking a thread is undesirable for many reasons while non-blocking
algorithms do not suffer from these downsides
–
while the thread is blocked, it cannot accomplish anything
–
certain interactions between locks can lead to error conditions such as
deadlock, livelock, and priority inversion.
–
using locks involves a trade-off between coarse-grained locking, which can
significantly reduce opportunities for parallelism, and fine-grained locking,
which requires more careful design, increases locking overhead and is more
prone to bugs.
 
CS492B Analysis of Concurrent Programs, Prof. Moonzoo Kim
 
8
 
Excerpt from the wikipedia
Communication
 Deadlock
 
t
1
: Thread 1
3:
wait
(m)//i==0
  …
 
 
 
 
 
 
 
 
 
 
 
3:
wait
(m)//i==9
 
t
2
: Thread 2
 
 
13:
notify
(m)//j==0
   …
 
13:
notify
(m)//j==9
   (terminate)
 
  Thread1() {
1: ...
2: 
for
(i=0;i<10;i++){
3:  
wait
(m) ;}
  }
   Thread2() {
11: ...
12: 
for
(j=0;j<10;j++){
13:
  notify
(m)
;
}
   }
9
CS492B Analysis of Concurrent Programs, Prof. Moonzoo Kim
•
Lost notify
 
public final void wait()
 
CS492B Analysis of Concurrent Programs, Prof. Moonzoo Kim
 
10
 
Excerpt from the Java reference manual
•
Causes the current thread to wait until another thread invokes the notify()
method or the notifyAll() method for this object.
•
The current thread must 
own this object's monitor
.
–
The thread releases ownership of this monitor and waits until another thread notifies
threads waiting on this object's monitor to wake up either through a call to the notify
method or the notifyAll method. The thread then waits until it can re-obtain ownership
of the monitor and resumes execution.
•
Interrupts and spurious wakeups 
are possible, and this method should
always be used in a loop:
     synchronized (obj) {
         while (<condition does not hold>)
             obj.wait();
         ... // Perform action appropriate to condition
     }
See the following stackoverflow discussion:
http://stackoverflow.com/questions/105059
2/do-spurious-wakeups-actually-happen
 
public final void notify()
 
CS492B Analysis of Concurrent Programs, Prof. Moonzoo Kim
 
11
 
Excerpt from the Java reference manual
•
Wakes up a single thread that is waiting on this object's 
monitor
.
–
If any threads are waiting on this object, one of them is chosen to be awakened. The
choice is 
arbitrary
 and occurs at the discretion of the implementation.
•
The awakened thread will not be able to proceed until the current
thread relinquishes the lock on this object.
–
The awakened thread will 
compete
 in the usual manner with any other threads that
might be actively competing to synchronize on this object; for example, the
awakened thread enjoys no reliable privilege or disadvantage in being the next
thread to lock this object.
•
This method should only be called by a thread that is the 
owner of
this object's monitor.
 A thread becomes the owner of the object's
monitor in one of three ways:
–
By executing a synchronized instance method of that object.
–
By executing the body of a synchronized statement that synchronizes on the object.
–
For objects of type Class, by executing a synchronized static method of that class.
 
Finding Deadlock Bugs is Difficult
 
•
A deadlock bug induces deadlock situations
only under certain thread schedules
•
Systems software creates a 
massive number
of locks 
for fine-grained concurrency controls
•
Function caller-callee relation
 complicates
the reasoning about possible nested lockings
 
12
 
CS492B Analysis of Concurrent Programs, Prof. Moonzoo Kim
 
Bug 
Detection
 Approach
 
Resource deadlock
•
Basic potential deadlock detection algorithm
•
GoodLock algorithm
 
Communication deadlock
•
CHECKMATE: a trace program model-checking
technique for deadlock detection
 
13
 
CS492B Analysis of Concurrent Programs, Prof. Moonzoo Kim
 
Basic Potential Deadlock Detection
 
•
Extend the cyclic deadlock monitoring algorithm
 
•
Cyclic deadlock monitoring algorithm 
(e.g. 
LockDep
)
–
Monitor lock acquires and releases in runtime
–
Lock graph (
N
, 
E
N
)
•
Create a node 
n
X
 when a thread acquires lock 
X
•
Create an edge (
n
X
, 
n
Y
) when a thread acquires lock 
Y
while holding lock 
X
•
Remove 
n
X
 , 
(
n
X
,*
)
 
and
 
(
*, n
X
)
 
when a thread releases 
X
 
 
Report deadlock when the graph has any cycle
 
14
 
CS492B Analysis of Concurrent Programs, Prof. Moonzoo Kim
Cyclic Deadlock Detection Example (1/2)
 
t1: Thread 1
1
:lock(X)
2:a = …
 
3
:lock(Y)
 
t2: Thread 2
 
11:
lock(Y)
12:b=...
 
13
:lock(X)
 
  Thread1() {
1: 
lock(
X
)
2: a = … ;
3: 
lock(
Y
)
4: b = … ;
5: 
unlock(
Y
)
6: 
unlock(
X
)
  }
  Thread2() {
11: 
lock(
Y
)
12: b = … ;
13: 
lock(
X
)
14: a = … ;
15: 
unlock(
X
)
16: 
unlock(
Y
)
  }
X
Y
 
3
 
13
 
Deadlock detected!
15
CS492B Analysis of Concurrent Programs, Prof. Moonzoo Kim
Cyclic Deadlock Detection Example (2/2)
 
t1: Thread 1
1
:lock(X)
2:a = …
3
:lock(Y)
4:b = …
5:
unlock(Y)
 
6:
unlock(X)
 
t2: Thread 2
 
 
 
 
11:
lock(Y)
 
12:b =...
13
:lock(X)
14:a =...
15:
unlock(X)
16:
unlock(Y)
 
  Thread1() {
1: 
lock(
X
);
2: a = …
3: 
lock(
Y
);
4: b = …
5: 
unlock(
Y
);
6: 
unlock(
X
);
  }
  Thread2() {
11: 
lock(
Y
);
12: b = …
13: 
lock(
X
);
14: a = …
15: 
unlock(
X
);
16: 
unlock(
Y
);
  }
X
Y
 
3
 
No problem
16
CS492B Analysis of Concurrent Programs, Prof. Moonzoo Kim
 
Basic Deadlock 
Prediction
 Technique
 
•
Potential cyclic deadlock detection algorithm [Harrow, SPIN 00]
–
Lock graph (
N
, 
E
N
)
•
Create a node 
n
X
 when a thread acquires lock 
X
•
Create an edge (
n
X
, 
n
Y
) when a thread acquires lock 
Y
while holding lock 
X
•
Remove 
n
X
 , (n
X
,*) and (*, n
X
) 
when a thread releases 
X
 
Report potential deadlocks if the resulted graph at the
      end of an execution has a cycle
 
17
 
CS492B Analysis of Concurrent Programs, Prof. Moonzoo Kim
 
[Harrow, SPIN 00] J. J. Harrow, Jr.: Runtime checking of multithreaded applications
with Visual Threads, SPIN Workshop 2000
Potential Cyclic Deadlock Detection Example
 
      
t1:Thread 1
1
:lock(X)
2:a = …
3
:lock(Y)
4:b = …
5:
unlock(Y)
 
6:
unlock(X)
 
t2:Thread 2
 
 
 
 
11
:lock(Y)
 
12:b=...
13
:lock(X)
   ...
 
  Thread1() {
1: 
lock(
X
)
2: a = … ;
3: 
lock(
Y
)
4: b = … ;
5: 
unlock(
Y
)
6: 
unlock(
X
)
  }
  Thread2() {
11: 
lock(
Y
)
12: b = … ;
13: 
lock(
X
)
14: a = … ;
15: 
unlock(
X
)
16: 
unlock(
Y
)
  }
X
Y
 
3
 
13
 
Cycle 
 
Potential deadlock
18
CS492B Analysis of Concurrent Programs, Prof. Moonzoo Kim
Basic Deadlock Prediction Technique
•
The algorithm is commercialized as a SW tool
VisualThreads (
HP
)
•
Empirical results show that the algorithm is
very effective to discover hidden deadlock bugs
•
Challenge:
19
CS492B Analysis of Concurrent Programs, Prof. Moonzoo Kim
 
generate 
many false positive
False Positive Example#1 – Single Thread Cycle
  Thread1() {
1:
 lock(
X
);
2:
  lock(
Y
);
3:
  unlock(
Y
);
4:
 unlock(
X
);
5:
 lock(
Y
);
6:
  lock(
X
);
7:
  unlock(
X
);
8:
 unlock(
Y
);
}
   Thread2() {
11:
 lock(
X
);
12:
 unlock(
X
);
13:
 lock(
Y
);
14:
 unlock(
Y
);
}
X
Y
 
2
 
5
 
The lock graph has a
cycle, but no deadlock
 
A cycle 
that consists of edges
created by one thread is a
false positive
20
CS492B Analysis of Concurrent Programs, Prof. Moonzoo Kim
False Positive Example#2: Gate Lock
  Thread1() {
1:
 lock(
X
);
2:
  lock(
Y
);
3
:   lock(
Z
) ;
4
:   unlock(
Z
);
5:
  unlock(
Y
);
6:
 unlock(
X
);
 
}
   Thread2() {
11:
 lock(
X
);
12:  
lock(
Z
) 
;
13:   
lock(
Y
)
 ;
14: 
  unlock(
Y
)
;
15:  
unlock(
Z
)
;
16:
 unlock(
X
);
X
Y
Z
 
3
 
13
 
3, 12
 
2, 13
 
Cycle, but no deadlock
Gate lock
(guard lock)
21
CS492B Analysis of Concurrent Programs, Prof. Moonzoo Kim
False Positive Example#3: Thread Creation
  f1(){
1:
 lock(
X
);
2:
  lock(
Y
);
3:
  unlock(
Y
);
4:
 unlock(
X
);
 
5: 
start
(f2);
  }
 
Cycle, but no deadlock
   f2(){
11: 
lock(
Y
)
 ;
12:
  lock(
X
);
13: 
 unlock(
X
);
14:
 unlock(
Y
)
;
   }
X
Y
 
2
 
12
Thread
segment#1
Thread
segment#2
22
CS492B Analysis of Concurrent Programs, Prof. Moonzoo Kim
 main(){
0:  
start
(f1);
 }
 
GoodLock Algorithm
[Agarwal, IBM 10]
 
•
Extend the lock graph in the basic potential deadlock detection
algorithm to consider 
thread, gate lock, 
and
 thread segment
•
Thread segment graph (
S
, 
E
S
)
–
When
 
the main thread 
t
0
 starts:
•
Create a thread segment node 
s
0
 ;
•
map 
t
0
 to 
s
0  
(
M
(
t
0
) = 
s
0
);
•
n
 = 1.
–
When
 
a thread 
t
i
 starts a new thread 
t
j
•
Create two thread segment nodes 
s
n
 
and
 s
n+1 
;
•
Create two edges
 
(
M
(
t
i
)
, s
n
)
 and 
(
M
(
t
i
)
, s
n+1
)
 ;
•
M
(
t
i
)
 = s
n
 ; M
(
t
j
)
 = s
n+1 
;
•
n 
=
 n 
+
 2 ;
 
 
[Agarwal, IBM 10] R. Agarwal et al., Detection of deadlock potential in
multithreaded programs,  IBM Journal of Research and Development, 54(5), 2010
 
23
 
CS492B Analysis of Concurrent Programs, Prof. Moonzoo Kim
Thread Segment Graph Example
 
  f1(){
1:
 lock(
X
);
2:
 lock(
Y
);
3: 
start
(f2);
4:
 unlock(
Y
);
5:
 unlock(
X
);
}
 
 
 
 
 
 
  f2(){
11: 
lock(
Y
)
 ;
12:
 lock(
X
);
13: 
unlock(
X
);
14:
 unlock(
Y
)
;
 
main(){
0:
 …
1:
 start
(f1);
2: …
}
 
s
0
 
s
1
 
s
3
 
s
2
 
s
4
t0
 
: main()
t1: f1()
t2: f2()
s
0
s
1
s
2
s
4
s
3
24
CS492B Analysis of Concurrent Programs, Prof. Moonzoo Kim
 
Extended Lock Graph
 
25
 
CS492B Analysis of Concurrent Programs, Prof. Moonzoo Kim
 
Potential Deadlock Detection
 
26
 
CS492B Analysis of Concurrent Programs, Prof. Moonzoo Kim
 
Thread Creation Example Revisit
 
  f1(){
1:
 lock(
X
);
2:
 lock(
Y
);
3: 
start
(f2);
4:
 unlock(
Y
);
5:
 unlock(
X
);
}
 
 
 
 
 
 
  f2(){
11: 
lock(
Y
)
 ;
12:
 lock(
X
);
13: 
unlock(
X
);
14:
 unlock(
Y
)
;
 
main(){
0:
 …
1:
 start
(f1);
2: …
}
 
s
0
 
s
1
 
s
3
 
s
2
 
s
4
 
t0
 
: main()
 
t1: f1()
 
t2: f2()
 
27
 
CS492B Analysis of Concurrent Programs, Prof. Moonzoo Kim
X
Y
 
e
2
: (
n
Y
, (
s
4
, 
t
2
, {Y}, 
s
4
), 
n
X
)
 
e
1
: (
n
X
, (
s
2
, 
t
1
, {X}, 
s
2
), 
n
Y
)
s
0
s
1
s
2
s
4
s
3
Revising Singe Thread Cycle Example
main() {
1: 
start
(Thread1);
2: 
start
(Thread2);
}
Thread2() {
21:
 lock(
X
);
22:
 unlock(
X
);
23:
 lock(
Y
);
24:
 unlock(
Y
);
}
X
Y
 
e
1
: (
n
X
, (
s
2
, 
t
1
,{X}, 
s
2
), 
n
Y
)
 
e
2
: (
n
Y
, (
s
2
, 
t
1
, {Y}, 
s
2
), 
n
X
)
s
0
s
1
s
2
s
3
s
4
Thread1() {
11:
 lock(
X
);
12:
  lock(
Y
);
13:
  unlock(
Y
);
14:
 unlock(
X
);
15:
 lock(
Y
);
16:
  lock(
X
);
17:
  unlock(
X
);
18:
 unlock(
Y
);
}
28
CS492B Analysis of Concurrent Programs, Prof. Moonzoo Kim
Revising Gate Lock Example
  Thread1() {
1:
 lock(
X
);
2:
  lock(
Y
);
3
:   lock(
Z
) ;
4
:   unlock(
Z
);
5:
  unlock(
Y
);
6:
 unlock(
X
);
 
}
   Thread2() {
11:
 lock(
X
);
12:  
lock(
Z
) 
;
13:   
lock(
Y
)
 ;
14: 
  unlock(
Y
)
;
15:  
unlock(
Z
)
;
16:
 unlock(
X
);
X
Y
Z
 
e
1
: (
n
Y
, (
s
2
, 
t
1
, 
{X, Y}
, 
s
2
), 
n
Z
)
 
e
2
: (
n
Z
, (
s
4
, 
t
2
, 
{X, Z}
, 
s
4
), 
n
Z
)
main() {
 start(
Thread1
);
 start(
Thread2
);
}
s
0
s
1
s
2
s
3
s
4
29
CS492B Analysis of Concurrent Programs, Prof. Moonzoo Kim
 
Detecting Potential Deadlock
with Wait/Notify, Semaphore, etc*
 
*P. Joshi et al., An Effective Dynamic Analysis for Detecting Generalized Deadlocks, FSE 2010
 
30
 
CS492B Analysis of Concurrent Programs, Prof. Moonzoo Kim
 
class
 BlockedBuffer {
 List buf = 
new
 ArrayList();
 
int
 cursize = 0;
 
int
 maxsize;
 
 BlockedBuffer(
int
 max){
   maxsize = max;
 }
 
 sync
 boolean isFull(){
   
return
(cursize>=maxsize);
 }
 
 sync
 
boolean
 isEmpty(){
   
return
(cursize == 0) ;
 }
 
 sync
 
void
 resize(
int
 m){
   maxsize = m;
 }
 
Object get(){
  Object e;
  
sync
(
this
){
    
while
(isEmpty())
      wait
() ;
    e = buf.remove(0);
    
if
(isFull()){
      cursize--;
      notify
(); }
    
else
      cursize--; }
  
return
 e; }
 
sync
 
void
 put(Object e){
  
while
(isFull())
    wait
() ;
  buf.add(e);
  cursize++ ;
  
notify
(); }
 
Correct Execution Scenario
 
main() {
 BoundedBuffer bf =
   
new
 BoundedBuffer(1);
 (
new
 Thread1(bf)).start();
 (
new
 Thread2(bf)).start();
 (
new
 Thread3(bf)).start();}
 
Thread1(BoundedBuffer bf){
  bf.put(0);
  bf.put(1);}
 
Thread2(BoundedBuffer bf){
  bf.resize(10);}
 
Thread3(BoundedBuffer bf){
  bf.get();}
 
Thread1
 
Thread2
 
Thread3
bf.put(0)
bf.resize(10)
bf.put(1)
bf.get()
 
31
 
CS492B Analysis of Concurrent Programs, Prof. Moonzoo Kim
Another Correct Execution Scenario
main() {
 BoundedBuffer bf =
   
new
 BoundedBuffer(1);
 (
new
 Thread1(bf)).start();
 (
new
 Thread2(bf)).start();
 (
new
 Thread3(bf)).start();}
Thread1(BoundedBuffer bf){
  bf.put(0);
  bf.put(1);}
Thread2(BoundedBuffer bf){
  bf.resize(10);}
Thread3(BoundedBuffer bf){
  bf.get();}
Thread1
Thread2
Thread3
bf.put(0)
bf.resize(10)
bf.put(1)
bf.get()
32
CS492B Analysis of Concurrent Programs, Prof. Moonzoo Kim
bf.put(1)
while(isFull())
    wait();
if(isFull()) {…
  notify() ; }
Deadlock Execution Scenario
main() {
 BoundedBuffer bf =
   
new
 BoundedBuffer(1);
 (
new
 Thread1(bf)).start();
 (
new
 Thread2(bf)).start();
 (
new
 Thread3(bf)).start();}
Thread1(BoundedBuffer bf){
  bf.put(0);
  bf.put(1);}
Thread2(BoundedBuffer bf){
  bf.resize(10);}
Thread3(BoundedBuffer bf){
  bf.get();}
Thread1
Thread2
Thread3
bf.put(0)
bf.resize(10)
bf.put(1)
bf.get()
33
CS492B Analysis of Concurrent Programs, Prof. Moonzoo Kim
while(isFull())
    wait();
if(isFull()) {…
  
notify() ;
 }
cursize=1
 
CHECKMATE: Trace Program Model Checking
 
•
Observe a multi-threaded program execution
•
Retain only the synchronization operations observed
during execution
–
Throw away all other operations like memory update and
method calls
•
Create a program from the retained operations (trace
program)
•
Model checking trace program
–
Check partial behaviors
 
34
 
CS492B Analysis of Concurrent Programs, Prof. Moonzoo Kim
Trace Program Example
 
main() {
 bf = Lock();
 isFull=false;
 
start
(t1);
 
start
(t2);
 
start
(t3);}
 
t1() {
  
lock
(bf) ;
  
if
(isFull)
    
wait
(bf) ;
  isFull=
true
;
  
notify
(bf) ;
  
unlock
(bf);
 
 
  
lock
(bf);
   
if
(isFull)
    
wait
(bf) ;
  
notify
(bf);
  
unlock
(bf);}
 
t2() {
 
lock
(bf);
 isFull=
false
;
 
unlock
(bf);
}
t3() {
 
lock
(bf) ;
 
if
(isFull)
  
notify
(bf);
 
unlock
(bf);
}
Thread1
Thread2
Thread3
bf.put(0)
bf.resize(10)
bf.put(1)
bf.get()
 
bf.put(0)
 
bf.put(1)
 
bf.get()
 
bf.resize()
35
CS492B Analysis of Concurrent Programs, Prof. Moonzoo Kim

								

								
								

										

												
Slide Note

												

										

								


								
						

							
						


							

								

									
										
Embed
									
									
										
Share
									

									
									
									

								

								
							


							

							 
 							 
 							 
						  


							
							

								
This analysis delves into various bug detection techniques for concurrent programs, focusing on deadlock bugs. It explores model checking and testing techniques, discussing their precision, error detection capabilities, and scalability challenges. The prevalence of deadlock bugs in real-world applications is highlighted, underlining the importance of effective bug detection methods. Additionally, examples such as the dining philosopher problem illustrate resource deadlock scenarios in concurrent programs.


								
    
																		
  •   Concurrency Bugs
    • 
																	
  •    Deadlock Detection
    • 
																	
  •    Bug Detection Techniques
    • 
																	
  •    Concurrent Programs
    • 
																

								

								

									

										brrr392
										

											 brrr392 Follow
											

										

									

									
Uploaded on Sep 18, 2024 | 0 Views

								

								


								

									
Download Presentation

									
								

								
Please find below an Image/Link to download the presentation.

								
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
									Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.


									
									

									


										 
										 
										 
										 

									

									

									

									

										
 E N D 

									


								
Presentation Transcript

								

								
  1. CS492B Analysis of Concurrent Programs Deadlock Bug Detection Techniques Prof. Moonzoo Kim CS KAIST 1
    2. 
            
            
            
  2. Bug Detection Techniques for  Concurrent Programs Model checking techniques +  High precision +  Comprehensive error detection - Scalability  (state explosion problem) - Verification expertise is required test cases and thread schedules executions) - False alarms  Testing techniques +  High precision  +  Friendly to developers - Difficult to generate  (no need to generate many  Verification Bug detection techniques + Fast and convenient SPIN  jCute Fusion Java PathFinder CHESS Precision KISS  CalFuzzer ConTest rstest Atomizer  Eraser  RacerX MetaL False alarm 100~1,000 LOC 1,000,000 LOC < Scalability 2 CS492B Analysis of Concurrent Programs, Prof. Moonzoo Kim
    3. 
            
            
            
  3. Deadlock Bugs Frequently Occur in Real World     In a survey on 105 real-world concurrency bugs in open- source applications, 31 out of 105 bugs are deadlock bugs  [Lu et al., ASPLOS 08] 3 CS492B Analysis of Concurrent Programs, Prof. Moonzoo Kim
    4. 
            
            
            
  4. Deadlock Bugs Frequently Occur in Real World     According to Apache  bug tracking systems,  there have been  200  deadlock related issues  since 2014 4 CS492B Analysis of Concurrent Programs, Prof. Moonzoo Kim
    5. 
            
            
            
  5. Deadlock     A deadlock occurs when each of a set of threads  is blocked, waiting for another thread in the set  to satisfy certain condition release shared resource raise event 5 CS492B Analysis of Concurrent Programs, Prof. Moonzoo Kim
    6. 
            
            
            
  6. Resource Deadlock     Ex. Dining philosopher problem 1. Think 2. If left fork is available,  pick it up 3. If right fork is available,  pick it up 4. Eat 5. Put the right folk down 6. Put the left folk down [Milner] [Dijkstra] [Milner] [Dijkstra] Folk#1 Pick up Folk#1 Pick up Folk#1 Pick up Folk#2 Pick up Folk#2 Wait for  Folk#2 Folk#2 Pick up Folk#2 Wait for  Folk#1 Pick up Folk#1 6 CS492B Analysis of Concurrent Programs, Prof. Moonzoo Kim
    7. 
            
            
            
  7. Resource Deadlock in Concurrent Programs     ABBA deadlock Thread1() { 1: lock(X) 2: x =     ; 3: lock(Y) 4: y =     ; 5: unlock(Y) 6: unlock(X) } Thread2() { 11: lock(Y) 12: y =     ; 13: lock(X) 14: x =     ; 15: unlock(X) 16: unlock(Y) } t1: Thread 1 t2: Thread 2 1:lock(X) 2:x =     11:lock(Y) 12:y=... 3:lock(Y) 13:lock(X) 7 CS492B Analysis of Concurrent Programs, Prof. Moonzoo Kim
    8. 
            
            
            
  8. Excerpt from the wikipedia Non-blocking Algorithm     An algorithm is called non-blocking if failure or suspension of any thread  cannot cause failure or suspension of another thread     a non-blocking algorithm is lock-free if there is guaranteed system-wide  progress, and wait-free if there is also guaranteed per-thread progress. Blocking a thread is undesirable for many reasons while non-blocking  algorithms do not suffer from these downsides     while the thread is blocked, it cannot accomplish anything      certain interactions between locks can lead to error conditions such as  deadlock, livelock, and priority inversion.      using locks involves a trade-off between coarse-grained locking, which can  significantly reduce opportunities for parallelism, and fine-grained locking,  which requires more careful design, increases locking overhead and is more  prone to bugs.     8 CS492B Analysis of Concurrent Programs, Prof. Moonzoo Kim
    9. 
            
            
            
  9. Communication Deadlock     Lost notify Thread1() { 1: ... 2: for(i=0;i<10;i++){ 3:  wait(m) ;} } Thread2() { 11: ... 12: for(j=0;j<10;j++){ 13: notify(m);} } t2: Thread 2 t1: Thread 1 3:wait(m)//i==0     13:notify(m)//j==0     13:notify(m)//j==9 (terminate) 3:wait(m)//i==9 9 CS492B Analysis of Concurrent Programs, Prof. Moonzoo Kim
    10. 
            
            
            
  10. Excerpt from the Java reference manual public final void wait()     Causes the current thread to wait until another thread invokes the notify()  method or the notifyAll() method for this object.      The current thread must own this object's monitor.      The thread releases ownership of this monitor and waits until another thread notifies  threads waiting on this object's monitor to wake up either through a call to the notify  method or the notifyAll method. The thread then waits until it can re-obtain ownership  of the monitor and resumes execution.     Interrupts and spurious wakeups are possible, and this method should  always be used in a loop: synchronized (obj) { while (<condition does not hold>) obj.wait(); ... // Perform action appropriate to condition } See the following stackoverflow discussion: http://stackoverflow.com/questions/105059 2/do-spurious-wakeups-actually-happen 10 CS492B Analysis of Concurrent Programs, Prof. Moonzoo Kim
    11. 
            
            
            
  11. Excerpt from the Java reference manual public final void notify()     Wakes up a single thread that is waiting on this object's monitor.      If any threads are waiting on this object, one of them is chosen to be awakened. The  choice is arbitrary and occurs at the discretion of the implementation.       The awakened thread will not be able to proceed until the current  thread relinquishes the lock on this object.      The awakened thread will compete in the usual manner with any other threads that  might be actively competing to synchronize on this object; for example, the  awakened thread enjoys no reliable privilege or disadvantage in being the next  thread to lock this object.     This method should only be called by a thread that is the owner of  this object's monitor. A thread becomes the owner of the object's  monitor in one of three ways:     By executing a synchronized instance method of that object.     By executing the body of a synchronized statement that synchronizes on the object.     For objects of type Class, by executing a synchronized static method of that class. 11 CS492B Analysis of Concurrent Programs, Prof. Moonzoo Kim
    12. 
            
            
            
  12. Finding Deadlock Bugs is Difficult     A deadlock bug induces deadlock situations  only under certain thread schedules     Systems software creates a massive number  of locks for fine-grained concurrency controls     Function caller-callee relation complicates  the reasoning about possible nested lockings 12 CS492B Analysis of Concurrent Programs, Prof. Moonzoo Kim
    13. 
            
            
            
  13. Bug Detection Approach Resource deadlock     Basic potential deadlock detection algorithm     GoodLock algorithm Communication deadlock     CHECKMATE: a trace program model-checking  technique for deadlock detection 13 CS492B Analysis of Concurrent Programs, Prof. Moonzoo Kim
    14. 
            
            
            
  14. Basic Potential Deadlock Detection     Extend the cyclic deadlock monitoring algorithm     Cyclic deadlock monitoring algorithm (e.g. LockDep)     Monitor lock acquires and releases in runtime     Lock graph (N, EN)     Create a node nXwhen a thread acquires lock X     Create an edge (nX, nY) when a thread acquires lock Y while holding lock X     Remove nX, (nX,*) and (*, nX) when a thread releases X     Report deadlock when the graph has any cycle 14 CS492B Analysis of Concurrent Programs, Prof. Moonzoo Kim
    15. 
            
            
            
  15. Cyclic Deadlock Detection Example (1/2) Thread1() { 1: lock(X) 2: a =     ; 3: lock(Y) 4: b =     ; 5: unlock(Y) 6: unlock(X) } Thread2() { 11: lock(Y) 12: b =     ; 13: lock(X) 14: a =     ; 15: unlock(X) 16: unlock(Y) } t1: Thread 1 t2: Thread 2 1:lock(X) 2:a =     11:lock(Y) 12:b=... 3:lock(Y) 13:lock(X) 3 X Y Deadlock detected! 13 15 CS492B Analysis of Concurrent Programs, Prof. Moonzoo Kim
    16. 
            
            
            
  16. Cyclic Deadlock Detection Example (2/2) t1: Thread 1 1:lock(X) 2:a =     3:lock(Y) 4:b =     5:unlock(Y) t2: Thread 2 Thread1() { 1: lock(X); 2: a =      3: lock(Y); 4: b =      5: unlock(Y); 6: unlock(X); } Thread2() { 11: lock(Y); 12: b =      13: lock(X); 14: a =      15: unlock(X); 16: unlock(Y); } 11:lock(Y) 6:unlock(X) 12:b =... 13:lock(X) 14:a =... 15:unlock(X) 16:unlock(Y) 3 XX X YYY No problem X Y 13 16 CS492B Analysis of Concurrent Programs, Prof. Moonzoo Kim
    17. 
            
            
            
  17. Basic Deadlock Prediction Technique     Potential cyclic deadlock detection algorithm [Harrow, SPIN 00]     Lock graph (N, EN)     Create a node nXwhen a thread acquires lock X     Create an edge (nX, nY) when a thread acquires lock Y while holding lock X     Remove nX, (nX,*) and (*, nX) when a thread releases X     Report potential deadlocks if the resulted graph at the  end of an execution has a cycle [Harrow, SPIN 00] J. J. Harrow, Jr.: Runtime checking of multithreaded applications  with Visual Threads, SPIN Workshop 2000 17 CS492B Analysis of Concurrent Programs, Prof. Moonzoo Kim
    18. 
            
            
            
  18. Potential Cyclic Deadlock Detection Example t1:Thread 1 1:lock(X) 2:a =     3:lock(Y) 4:b =     5:unlock(Y) t2:Thread 2 Thread1() { 1: lock(X) 2: a =     ; 3: lock(Y) 4: b =     ; 5: unlock(Y) 6: unlock(X) } Thread2() { 11: lock(Y) 12: b =     ; 13: lock(X) 14: a =     ; 15: unlock(X) 16: unlock(Y) } 11:lock(Y) 6:unlock(X) 12:b=... 13:lock(X) ... 3 X Y Cycle         Potential deadlock 13 18 CS492B Analysis of Concurrent Programs, Prof. Moonzoo Kim
    19. 
            
            
            
  19. Basic Deadlock Prediction Technique     The algorithm is commercialized as a SW tool  VisualThreads (HP)     Empirical results show that the algorithm is  very effective to discover hidden deadlock bugs     Challenge: generate many false positive 19 CS492B Analysis of Concurrent Programs, Prof. Moonzoo Kim
    20. 
            
            
            
  20. False Positive Example#1  Single Thread Cycle 2 Thread1() { 1: lock(X); 2: lock(Y); 3: unlock(Y); 4: unlock(X); Thread2() { 11: lock(X); 12: unlock(X); X Y 13: lock(Y); 14: unlock(Y);} 5 The lock graph has a  cycle, but no deadlock 5: lock(Y); 6: lock(X); 7: unlock(X); 8: unlock(Y);} A cycle that consists of edges  created by one thread is a  false positive 20 CS492B Analysis of Concurrent Programs, Prof. Moonzoo Kim
    21. 
            
            
            
  21. False Positive Example#2: Gate Lock Thread1() { 1: lock(X); 2: lock(Y); 3:   lock(Z) ; 4:   unlock(Z); 5: unlock(Y); 6: unlock(X); } Thread2() { 11: lock(X); 12:  lock(Z) ; 13:   lock(Y) ; 14:  unlock(Y); 15:  unlock(Z); 16: unlock(X); Gate lock (guard lock) Cycle, but no deadlock 3 Y 2, 13 13 X Z 3, 12 21 CS492B Analysis of Concurrent Programs, Prof. Moonzoo Kim
    22. 
            
            
            
  22. False Positive Example#3: Thread Creation Thread  segment#1 Thread  segment#2 main(){ 0:  start(f1); } f1(){ 1: lock(X); 2: lock(Y); 3: unlock(Y); 4: unlock(X); 5: start(f2);  } 2 f2(){ 11: lock(Y) ; 12: lock(X); 13: unlock(X); 14: unlock(Y); } Cycle, but no deadlock X Y 12 22 CS492B Analysis of Concurrent Programs, Prof. Moonzoo Kim
    23. 
            
            
            
  23. GoodLock Algorithm[Agarwal, IBM 10]     Extend the lock graph in the basic potential deadlock detection algorithm to consider thread, gate lock, and thread segment     Thread segment graph (S, ES)     When the main thread t0starts:     Create a thread segment node s0;     map t0to s0  (M(t0) = s0);      n = 1.     When a thread tistarts a new thread tj     Create two thread segment nodes snand sn+1 ;     Create two edges (M(ti), sn) and (M(ti), sn+1) ;     M(ti) = sn; M(tj) = sn+1 ;      n = n + 2 ; [Agarwal, IBM 10] R. Agarwal et al., Detection of deadlock potential in  multithreaded programs,  IBM Journal of Research and Development, 54(5), 2010 CS492B Analysis of Concurrent Programs, Prof. Moonzoo Kim 23
    24. 
            
            
            
  24. Thread Segment Graph Example t0: main() t1: f1() t2: f2() main(){ 0:     1: start(f1); 2:     } s0 s1 s2 f1(){ 1: lock(X); 2: lock(Y); 3: start(f2); 4: unlock(Y); 5: unlock(X);} s4 s3 f2(){ 11: lock(Y) ; 12: lock(X); 13: unlock(X); 14: unlock(Y); s4 s0 s2 s1 s3 24 CS492B Analysis of Concurrent Programs, Prof. Moonzoo Kim
    25. 
            
            
            
  25. Extended Lock Graph     Lock graph (N, EN)     Create a node nXwhen a thread acquires lock X     Create an edge (nX, L, nY) when a thread acquires lock Y while  holding lock X, where  L = (s1, t, G, s2)     s1: the thread segment (s1    S) where lock X was acquired     t: the thread that acquires lock Y     G: the set of locks that t holds when it acquires Y     s2: the thread segment where lock Y was acquired 25 CS492B Analysis of Concurrent Programs, Prof. Moonzoo Kim
    26. 
            
            
            
  26. Potential Deadlock Detection     A cycle is valid (i.e., true positive) when every pair of edges  (m11, (s11, t1, G1, s12), m12), and (m21, (s21, t2, G2, s22), m22) in the  cycle satisfies:     ?1    ?2, and     ?1    ?2=     , and       (?12    ?21)    The happens-before relation     is the transitive  closure of the relation R such that ?1,?2     ? if there exists the edge from ?1 to ?2 in the thread  segment graph 26 CS492B Analysis of Concurrent Programs, Prof. Moonzoo Kim
    27. 
            
            
            
  27. Thread Creation Example Revisit t0: main() t1: f1() t2: f2() main(){ 0:     1: start(f1); 2:     } s0 s1 s2 f1(){ 1: lock(X); 2: lock(Y); 3: start(f2); 4: unlock(Y); 5: unlock(X);} s4 s3 f2(){ 11: lock(Y) ; 12: lock(X); 13: unlock(X); 14: unlock(Y); e1: (nX, (s2, t1, {X}, s2), nY) X Y s4 s0 s2 e2: (nY, (s4, t2, {Y}, s4), nX) s1 s3 27 CS492B Analysis of Concurrent Programs, Prof. Moonzoo Kim
    28. 
            
            
            
  28. Revising Singe Thread Cycle Example Thread1() { 11: lock(X); 12: lock(Y); 13: unlock(Y); 14: unlock(X); Thread2() { 21: lock(X); 22: unlock(X); main() { 1: start(Thread1); 2: start(Thread2); } 23: lock(Y); 24: unlock(Y);} 15: lock(Y); 16: lock(X); 17: unlock(X); 18: unlock(Y);} e1: (nX, (s2, t1,{X}, s2), nY) s0 s2 X Y s1 s4 s3 e2: (nY, (s2, t1, {Y}, s2), nX) 28 CS492B Analysis of Concurrent Programs, Prof. Moonzoo Kim
    29. 
            
            
            
  29. Revising Gate Lock Example main() { start(Thread1); start(Thread2); } Thread1() { 1: lock(X); 2: lock(Y); 3:   lock(Z) ; 4:   unlock(Z); 5: unlock(Y); 6: unlock(X); } Thread2() { 11: lock(X); 12:  lock(Z) ; 13:   lock(Y) ; 14:  unlock(Y); 15:  unlock(Z); 16: unlock(X); Y e1: (nY, (s2, t1, {X, Y}, s2), nZ) s0 s2 e2: (nZ, (s4, t2, {X, Z}, s4), nZ) s1 s4 X Z s3 29 CS492B Analysis of Concurrent Programs, Prof. Moonzoo Kim
    30. 
            
            
            
  30. Detecting Potential Deadlock  with Wait/Notify, Semaphore, etc* class BlockedBuffer { List buf = new ArrayList(); int cursize = 0;  int maxsize; sync void put(Object e){ while(isFull())   wait() ; buf.add(e);  cursize++ ; notify(); } BlockedBuffer(int max){ maxsize = max; } Object get(){ Object e; sync(this){ while(isEmpty())  wait() ; e = buf.remove(0); if(isFull()){ cursize--;  notify(); } else cursize--; } return e; } sync boolean isFull(){ return(cursize>=maxsize); } sync boolean isEmpty(){ return(cursize == 0) ; } sync void resize(int m){ maxsize = m; } *P. Joshi et al., An Effective Dynamic Analysis for Detecting Generalized Deadlocks, FSE 2010 30 CS492B Analysis of Concurrent Programs, Prof. Moonzoo Kim
    31. 
            
            
            
  31. Correct Execution Scenario main() { BoundedBuffer bf = new BoundedBuffer(1); (new Thread1(bf)).start(); (new Thread2(bf)).start(); (new Thread3(bf)).start();} Thread1 Thread2 Thread3 bf.put(0) bf.resize(10) Thread1(BoundedBuffer bf){ bf.put(0); bf.put(1);} bf.put(1) bf.get() Thread2(BoundedBuffer bf){ bf.resize(10);} Thread3(BoundedBuffer bf){ bf.get();} 31 CS492B Analysis of Concurrent Programs, Prof. Moonzoo Kim
    32. 
            
            
            
  32. Another Correct Execution Scenario main() { BoundedBuffer bf = new BoundedBuffer(1); (new Thread1(bf)).start(); (new Thread2(bf)).start(); (new Thread3(bf)).start();} Thread1 Thread2 Thread3 while(isFull())  wait(); bf.put(0) bf.put(1) if(isFull()) {    notify() ; } Thread1(BoundedBuffer bf){ bf.put(0); bf.put(1);} bf.get() bf.put(1) Thread2(BoundedBuffer bf){ bf.resize(10);} bf.resize(10) Thread3(BoundedBuffer bf){ bf.get();} 32 CS492B Analysis of Concurrent Programs, Prof. Moonzoo Kim
    33. 
            
            
            
  33. Deadlock Execution Scenario main() { BoundedBuffer bf = new BoundedBuffer(1); (new Thread1(bf)).start(); (new Thread2(bf)).start(); (new Thread3(bf)).start();} Thread1 Thread2 Thread3 while(isFull())  wait(); bf.put(0) bf.put(1) Thread1(BoundedBuffer bf){ bf.put(0); bf.put(1);} cursize=1 bf.resize(10) if(isFull()) {    notify() ; } Thread2(BoundedBuffer bf){ bf.resize(10);} bf.get() Thread3(BoundedBuffer bf){ bf.get();} 33 CS492B Analysis of Concurrent Programs, Prof. Moonzoo Kim
    34. 
            
            
            
  34. CHECKMATE: Trace Program Model Checking     Observe a multi-threaded program execution     Retain only the synchronization operations observed  during execution     Throw away all other operations like memory update and  method calls     Create a program from the retained operations (trace  program)     Model checking trace program     Check partial behaviors 34 CS492B Analysis of Concurrent Programs, Prof. Moonzoo Kim
    35. 
            
            
            
  35. Trace Program Example main() { bf = Lock(); isFull=false; start(t1); start(t2); start(t3);} bf.resize() t2() { lock(bf); isFull=false; unlock(bf); } Thread1 Thread2 Thread3 bf.put(0) bf.put(0) t1() { lock(bf) ; if(isFull) wait(bf) ; isFull=true; notify(bf) ; unlock(bf); bf.put(1) bf.get() t3() { lock(bf) ; if(isFull) notify(bf); unlock(bf); } bf.put(1) bf.get() bf.resize(10) lock(bf); if(isFull) wait(bf) ; notify(bf); unlock(bf);} 35 CS492B Analysis of Concurrent Programs, Prof. Moonzoo Kim
    36. 
            
            
            
							

							

					

					
					
					

						
Related

						

						


							
							
							
							

						

							

									

      

        
          

            

              Fighting Bed Bugs NYC Bed Bug Treatments and Exterminators
            

            

              
Fighting Bed Bugs NYC Bed Bug Treatments and Exterminators

              
VJ

            

          

        
      


     

      

        
          

            

              Arkansas Concurrent Challenge Scholarship Program Details
            

            

              
Arkansas Concurrent Challenge Scholarship Program Details

              
vela

            

          

        
      


     

      

        
          

            

              Deadlocks in Operating Systems
            

            

              
Deadlocks in Operating Systems

              
zahava

            

          

        
      


     

      

        
          

            

              Database Deadlocks and Detection
            

            

              
Database Deadlocks and Detection

              
pear

            

          

        
      


     

      

        
          

            

              Deadlock: Conditions, Detection, and Avoidance
            

            

              
Deadlock: Conditions, Detection, and Avoidance

              
arjan

            

          

        
      


     

      

        
          

            

              Deadlock Avoidance in Operating System Concepts
            

            

              
Deadlock Avoidance in Operating System Concepts

              
lior

            

          

        
      


     

      

        
          

            

              Deadlock in Shareholders Disputes
            

            

              
Deadlock in Shareholders Disputes

              
anatoly

            

          

        
      


     

      

        
          

            

              Understanding and Detecting Real-World Performance Bugs
            

            

              
Understanding and Detecting Real-World Performance Bugs

              
bri_gar

            

          

        
      


     

      

        
          

            

              Real-World Concurrency Bugs and Detection Strategies
            

            

              
Real-World Concurrency Bugs and Detection Strategies

              
markwell_b

            

          

        
      


     

      

        
          

            

              Bed Bug Awareness and Prevention Tips for Travelers
            

            

              
Bed Bug Awareness and Prevention Tips for Travelers

              
brin_182

            

          

        
      


     

      

        
          

            

              Real-World Concurrency Bugs in Go Programming Language
            

            

              
Real-World Concurrency Bugs in Go Programming Language

              
esters_j

            

          

        
      


     

      

        
          

            

              Software Bugs and Formal Verification in Critical Systems
            

            

              
Software Bugs and Formal Verification in Critical Systems

              
jama_ico

            

          

        
      


     

      

        
          

            

              Rely-Guarantee-Based Simulation for Concurrent Program Transformations
            

            

              
Rely-Guarantee-Based Simulation for Concurrent Program Transformations

              
raer503

            

          

        
      


     

      

        
          

            

              Techniques for Detecting and Analyzing Deadlock Bugs in Concurrent Programs
            

            

              
Techniques for Detecting and Analyzing Deadlock Bugs in Concurrent Programs

              
manfredi_z

            

          

        
      


     

      

        
          

            

              Enhancing Android Development Lifecycle with VALERA Record-and-Replay Approach
            

            

              
Enhancing Android Development Lifecycle with VALERA Record-and-Replay Approach

              
alejand

            

          

        
      


     

      

        
          

            

              The Impact of Bugs on User Satisfaction in Software Programs
            

            

              
The Impact of Bugs on User Satisfaction in Software Programs

              
schipper_m

            

          

        
      


     

      

        
          

            

              Deadlock in Operating Systems
            

            

              
Deadlock in Operating Systems

              
griesemer_k

            

          

        
      


     

      

        
          

            

              Succinct Representation of Concurrent Trace Sets in Program Synthesis
            

            

              
Succinct Representation of Concurrent Trace Sets in Program Synthesis

              
gen_ea

            

          

        
      


     

      

        
          

            

              Systematic Testing of Reactive Software - A Case Study on LG Electric Oven
            

            

              
Systematic Testing of Reactive Software - A Case Study on LG Electric Oven

              
giro_sha

            

          

        
      


     

      

        
          

            

              Data Race Detection Techniques in Concurrent Programs
            

            

              
Data Race Detection Techniques in Concurrent Programs

              
jalyri

            

          

        
      


     

      

        
          

            

              Idempotence Bugs in Intermittent Systems
            

            

              
Idempotence Bugs in Intermittent Systems

              
don_323

            

          

        
      


     

      

        
          

            

              CalFuzzer Tutorial: Analysis of Concurrent Programs
            

            

              
CalFuzzer Tutorial: Analysis of Concurrent Programs

              
juanpabl

            

          

        
      


     							

						

					

					

				


				

			

		
		

			

				
				

					
More Related Content

					

						

														

					

				

				
			

		












 





  
  
  



giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#