! "
I see a
deadlock potential
in that execution
log file
lock(T1,L1)
lock(T1,L2)
release(T1,L2)
release(T1,L1)
lock(T2,L2)
lock(T2,L1)
Page 1
RV
Implemented
system
under test
Page 2
dispatch
input
Implemented
system
event stream
under test
Specs
reports
Algorithms
instrumentation
runtime monitoring
runtime checking
runtime validation
runtime analysis
dynamic analysis
Page 3
#
$
# &
# )
#
"
'
'
%
!
$ (
!
%
$
$
"
#
"
# * (" %
# " %
#
%
"
!
!
%
+&
,
Page 4
!
"
always
newCommand
s1
validate
success
s3
s2
execute
fail
execute
s6
s8
customValidate
s4
rejectCommand
execute
s7
customValidate
s5
Page 5
#
#
$
!
(
0
#
.
1
# )
%/
(
/
!
(
1
%
(
&
'
/
Page 6
$
!
! (
(
(
1
,
%
+
!
/
Page 7
( )
*+
synchronized statements
A basic scenario
$
' 2
3
*2
*3
T1:
T2:
synchronized(L1){
...
synchronized(L2){
...
synchronized(L2){
...
synchronized(L1){
...
}
...
}
}
...
}
Page 8
(
)
*+
synchronized methods
Dynamic locks
class Value{
int x = 1;
synchronized void add(Value v){x = x + v.get();}
synchronized int get(){return x;}
}
v1 = new Value();
v2 = new Value();
Thread T1
Thread T2
v1
v1.add(v2)
v2.add(v1)
v2
Page 9
(
)
*+
A challenge for static analysis
dynamic locking
N = number of philosophers
class Main{
Fork[] forks = new Fork[N];
..
for(int i=0;i<N;i++){
new Phisosopher(forks[i],forks[(i+1)%N];
};
}
$
'
while(count<10){
synchronized(salt_chaker)
synchronized(left){
synchronized(right){count++}
}
}
arithmetic
Page 10
(
#
"
# )
%&
(
!
4 %
# 0
,
1
%
4 %
#
%
'
– 0 526 +7 3
– 0 538 +3/6 2
– 0 532 + !
#
,
!
– 0 57 +7
– 0 59 +3:
,
/,
%
, .!
'
%
!
# ) ,- !
#
$
!
'
,
!
!
;$
/,
(
4
Page 11
Error report
Error X in line Y
…
analyze
model
build
model
extract
trace
l(T1,G)
l(T1,L1)
l(T1,L2)
u(T1,L2)
u(T1,L1)
l(T2,G)
l(T2,L2)
l(T2,L1)
u(T2,L1)
u(T2,L2)
u(T2,G)
l(T3,L1)
l(T3,L2)
u(T3,L2)
u(T3,L1)
l(T1,L2)
l(T1,L1)
u(T1,L1)
u(T1,L2)
Extracted events kinds:
l(T,L) -- T locks L
u(T,L) -- T unlocks L
Page 12
"
/
%
Hmm … looks
pretty good
to me.
good run
bad run
Page 13
(
0,
1 (
%
Shoot … some
foot prints
of a bug!
good run
turn a hard to test
property into a
stronger easy
to test property.
bad run
Page 14
,
<
< =
(
2
+
,
!
!$$
"
%
"
%
" =
$
$
%
%
!
Page 15
#
# >!
-
(
%
$
/
# >!
/
Page 16
$
Error report
Error X in line Y
…
2%
/
detect
cycles
compute
graph
extract
trace
Page 17
(
3
# 45556
T1:
T2:
synchronized(L1){
...
synchronized(L2){
...
synchronized(L2){
...
synchronized(L1){
...
}
...
}
}
...
}
=
%
/7
/4
Page 18
(
Input: an execution trace
GL : (Lock *
,
CL : [Thread
Lock
+ 5 2//@ @,
A?
+ ,
GL '5 GL
CL := CL
!+ ,
CL := CL
+B
?
{ (o’,o) | o’
[
CL(t)
[
;
CL(t) };
{o} ];
CL(t) \ {o} ];
+
$
$
$
*,
' C < ,D
Page 19
(
-
,
3-
%
$
8
%
6
9
T1:
T2:
T3:
sync(G){
sync(L1){
sync(L2){}
}
};
T3 = new T3();
j3.start();
J3.join();
sync(L2){
sync(L1){}
}
sync(G){
sync(L2){
sync(L1){}
}
}
sync(L1){
sync(L2){}
}
%
%
Page 20
*+
*+
T1:
T2:
T3:
sync(G){
sync(L1){
sync(L2){}
}
};
T3 = new T3();
j3.start();
J3.join();
sync(L2){
sync(L1){}
}
sync(G){
sync(L2){
sync(L1){}
}
}
sync(L1){
sync(L2){}
}
*
!
:
l(T1,G)
l(T1,L1)
l(T1,L2)
u(T1,L2)
u(T1,L1)
s(T1,T3)
l(T2,G)
l(T2,L2)
l(T2,L1)
u(T2,L1)
u(T2,L2)
u(T2,G)
l(T3,L1)
l(T3,L2)
u(T3,L2)
u(T3,L1)
j(T1,T3)
l(T1,L2)
l(T1,L1)
u(T1,L1)
u(T1,L2)
Page 21
(
' !
E
$
F
$ /
E (
F/
(
%
$
%
9
T1:
T2:
T3:
sync(G){
sync(L1){
sync(L2){}
}
};
T3 = new T3();
j3.start();
J3.join();
sync(L2){
sync(L1){}
}
sync(G){
sync(L2){
sync(L1){}
}
}
sync(L1){
sync(L2){}
}
%
T3: L1 -> L2
%
T2: L2 -> L1
4 cycles =
4 deadlock potentials reported (Visual Threads).
1 real deadlock! (3 false positives)
Page 22
/
(
45556
3
T1
T2
T3
L2
G
G
L1
L1
L1
L2
L2
L2
L1
Page 23
/
(
45556
3
T1
T2
T3
L2
G
G
L1
L1
L1
L2
L2
L2
L1
Page 24
(
(
' ;
$ (
!
'
/
(
$
%
9
T1:
T2:
T3:
sync(G){
sync(L1){
sync(L2){}
}
};
T3 = new T3();
j3.start();
J3.join();
sync(L2){
sync(L1){}
}
sync(G){
sync(L2){
sync(L1){}
}
}
sync(L1){
sync(L2){}
}
2%
Potential 1 & 2
%
!
!
2 cycles =
2 deadlock potentials reported.
Page 25
(
Input: an execution trace
% *
5
*
*
,
GL : (Lock *
CL : [Thread
Lock
?
+ 5 2//@ @,
A?
+ ,
GL '5 GL
CL := CL
!+ ,
CL := CL
%
$
+B
$
;
{ (o’,(t,g),o) |
o’ CL(t)
g = { o’’ | o’’ CL(t) }};
[
CL(t) {o} ];
[
CL(t) \ {o} ];
"
$
+
thread : Label
thread(t,g) = t
Thread
guards : Label
guards(t,g) = g
Lock-set
valid-cycle( c ) =
e1,e2 c
thread(e1) thread(e2)
guards(e1) guards(e2) = { }
*,
' C < ,D
Page 26
$
1
2
4
2
T1:
T2:
T3:
sync(G){
sync(L1){
sync(L2){}
}
};
T3 = new T3();
j3.start();
J3.join();
sync(L2){
sync(L1){}
}
sync(G){
sync(L2){
sync(L1){}
}
}
sync(L1){
sync(L2){}
}
%
3
x executes before y
x
y
Page 27
*
36
:
36
; <
n : next free segment
T1
t2.start()
x
T2
T1
T2
n
n+1
t2.join()
x
n
Let S* be the transitive
closure of segmentation
graph S.
The happens-before
relation is defined as:
x
y = (x,y)
S*
The in-parallel
relation is defined as:
y
x || y = (x
y)
(y
x)
Page 28
(
(
' ;
$ (
'
/
-
(
$
2%
9
T1:
T2:
sync(G){
sync(L1){
sync(L2){}
}
};
T3 = new T3();
j3.start();
J3.join();
sync(L2){
sync(L1){}
}
sync(L1){
sync(G){
sync(L2){
sync(L2){}
}
sync(L1){}
}
One potential left, the real deadlock!
}
!
!
&'
%
M:
new T1().start();
new T2().start();
(
"##$
T3:
M
3
1
0
" $$$$
T1
" $
"%%$
2
5
T2
T3
7
4
6
Page 29
Input: an execution trace
% *
5
*
"
GL : (Lock *
*
,
GS : (nat
,
CL : [Thread
(Lock
,
?
CS : [Thread
?
'
5 2D
; %
+ 5 2//@ @,
A?
+ ,
GL '5 GL
CL := CL
!+ ,
CL := CL
+ 2 3,
GS '5 GS
CS := CS
n := n + 2;
G+ 2 3,
GS '5 GS
CS := CS
n := n + 1;
%
$
+B
$
$
/
/
{ (o’,(s1,t,g,s2),o) |
(o’, s1) CL(t)
g = { o’’ | (o’’, *) CL(t) }
s2 = CS(t)};
[
CL(t) {(o,CS(t))} ];
[
CL(t) \ {(o,*)} ];
{ (CS(t1),n), (CS(t1),n+1)}
[ 2
n, 3
n+1];
{ (CS(t1),n), (CS(t2),n)};
[ 2
n];
"
$
+
*,
' C < ,D
-
;
;
(
/
thread : Label
Thread
thread(s1,t,g,s2) = t
guards : Label
Lock-set
guards(s1,t,g,s2) = g
source : Label
nat
source(s1,t,g,s2) = s1
target : Label
nat
target(s1,t,g,s2) = s2
valid-cycle( c ) =
e1,e2 c
thread(e1) thread(e2)
guards(e1) guards(e2) = { }
target(e2)
target(e1)
Page 30
"
Error report
Error X in line Y
…
2
model
check
project on
threads
extract
trace
Page 31
"
# &;
"
$
2
!
;
"
!
%
C ;
B
$
"
$ *" )$ "
$
"
$
!
$
" )$
'
"
$
"
$
"
T1:
T2:
long x;
synchronized(R1){
synchronized(R2){};
x = big1*big2;
}
synchronized(R2){
System.out.println(x);
synchronized(R1){};
}
$
Page 32
"
"
$
"
$
2
"
$ *" )$ "
$
"
$
" )$
"
$
"
$
"
$
project on threads
"
"
$
"
$ " )$
$
"
"
$ *" )$ "
$
"
$ "
$
$
Page 33
$
;
%
!
5
$
@@
8
8
!
2
H!
3
2
3
"2
I
+2 2 I 2 JK,
8
!
3 65
'
$
$ *( $ / 2
'
%
L
+ ,
%
3== 6 5
. 365
/
+
2
3 I
@@
JK,
/
+ ,
+@@ ,
Page 34
*+
"
#
2
better
#
$
$
$
#
#
#
. >? %
. >@ !
'
0 59 M
$
+
7N
+2/6 >
!
6
28
!
,'
,
N=3: faster
N=4: out of mem.
Page 35
2
*
*
*
;
!
/
reflects : Cycle
reflects(c, ) =
(l1,(_,t,_,_),l2) c
t holds l1 in
t next wants l2 in
$ /
*
@@
/
soundness wrt. execution trace !
c
valid-cycles(GL)
||Si
Deadlocking( )
Bool
reflects(c, )
completeness wrt. execution trace !
||Si
Deadlocking( )
c
valid-cycles(GL)
reflects(c, )
execution trace
cycles
||Si
Page 36
"
8
%
A
T1:
T2:
T3:
sync(G){
sync(L1){
sync(L2){}
}
};
T3 = new T3();
j3.start();
J3.join();
sync(L2){
sync(L1){}
}
if(p)
X := G
else
X := H;
sync(X){
sync(L2){
sync(L1){}
}
}
sync(L1){
sync(L2){}
}
If p evaluates to true
Cycle becomes guarded
and error is missed.
Page 37
,
#
$
# O
-
%
1
.
!
$
;
! /
(
(
!
(
$
%
# - ( %
/
(
! $
+
(
(
!
,/
Page 38
,
!
.
,
3 B 6!
synchronized(L1){
if(random(1,n)==1)
synchronized(L2){}
}
Probability for deadlock to occur:
PD(k,n) = P(,
3 B 6 deadlocks in a run)
= 1/n * P(deadlock | random == 1)
= 1/n * (1 * (k-1)/k * (k-2)/k * … * 1/k)
synchronized(L2){
if(random(1,n)==1)
synchronized(L3){}
}
= 1/n * k!/k^k
…
Example:
synchronized(Lk){
if(random(1,n)==1)
synchronized(L1){}
}
PD(k=4,n=3) = 0.03
Page 39
*+
*
,
3 B 6!
synchronized(L1){
if(random(1,n)==1)
synchronized(L2){}
}
75
Probability for deadlock to occur:
PC(k,n) = P(,
3 B 6 generates cycle in a run)
= 1/n * P(cycle | random == 1)
= 1/n * 1
synchronized(L2){
if(random(1,n)==1)
synchronized(L3){}
}
= 1/n
…
Example:
synchronized(Lk){
if(random(1,n)==1)
synchronized(L1){}
}
PC(k=4,n=3) = 0.33
= 10 * PD(k=4,n=3)
<1
Page 40
$
,
trace model checking
%
–0 59 M +6
model checking
%
,
!
,
/,
%
–0 57 +7
–0 59 + !
!
!
,
%
'
–0 526 +7 3
–0 538 +3/6 2
–0 532 + !
'
'
,
/,
'
–0 57 +7 N
–0 59 + !
,
/,
runtime analysis
%
'
–0 5288 +N
–0 57 88 +33
–I
,
,
%
–0 59 +M
–0 5288 +7 8
–0 57 88 +3
–I
'
,
,
!
,
Page 41
2
. ( (<
C
7 6 888
! 2
.( ( C )
N 888
! 3$
.( (
<<
!
.( (
0
!
<<
! /
!
4 % %
4 % +
<< %
(
! /
$ *(
,
B
$
C/
!
3
/
!
!
+ ! 4 % %
&
!
,/
Page 42
$
(
%
. ( ( ; $ *( < ,
With Chuck Fry,
QSS, NASA Ames
agent relay (communication system)
external
events
Error message:
TokenNetworkMutex
traceLock
main
PlanRunner::trace_lock
by thread:
DeliberativePlanner
at positions:
planner
- trySetVariableDomain()
- PlanRunner::traceLock()
TokenNetworkMutex
TokenNetworkMutexby thread:
Mission_Agent_Main
at positions:
- PlanRunner::traceLock()
- getPredicateType()
token network (plan)
Page 43
#
$%
#
#
#
#
(
P Q %
!
$
$
!
- ( %
#
$
38
/
$
+
!
! !
/
;/ <<
%
,/
! /
(
!
;$
%
#
#
!
%
- ( %
!
#
#
%
$(
%
/
/
!
+
(
/
!
$
B
!
/
$
/
! ,/
C/
/
,
!
#
!
#
$
$
$
'
synchronized(A,B){…}
$$
(
$
/
Page 44
&
Page 45