Transcript Deadlock Hunter Poster

Deadlock Hunter
Project
Software Engineering Lab.
Winter 07/08
Supervised by:
Yonatan Kaspi
- 2008Nov
Introduced by:
Jamil Shehadeh
Husam Khshaiboun
1
Deadlock Hunter Project
Our goal is to build a tool that will force the operating system
scheduler to make the execution path be truly random.
We will do this by examining the byte code of a Java
program and adding small code sections in places that effect
the execution path.
Our job is to locate the deadlock, not to fix it.
- 2008Nov
2
Strategy
The idea is to enter other wait functions randomly anywhere before
a synchronize keyword appears.
Dealing with threads in any language can be done using specific
commands.
Using java enables us to be Platform independent.
The specific commands will be searched for in java byte code using
a parser.
Code sections will be added automatically in these places forcing
randomization in the execution path
A Java Code with a hidden deadlock will be used as a client.
The deadlock hunter will build a new instrumented byte code.
- 2008Nov
3
Gaston & Alphonso
A Client Example
Gaston & Alphonso are two gentle and friendly fellows.
They must bow one to the other anytime they meet.
Each one of them bows and continue bowing until the other
bows back.
What if both of them bow at the same time?
- 2008Nov
4
Gaston & Alphonso
How to find the deadlock
The idea is to enter other wait functions randomly anywhere before a
synchronize keyword appears.
Then, we can shake the stability of the regular execution path.
We always enter the same byte code of an invariant function that
includes a call of other modifiable function.
To do that. “Some” BCEL is needed.
BCEL stands for Byte Code Engineering Library
Intended to give users a convenient possibility to analyze, create,
and manipulate (binary) Java class files.
Classes are represented by objects which contain all the symbolic
information of the given class: methods, fields and byte code
instructions, in particular.
- 2008Nov
5
The Deadlock Hunter
Main code flow
Get the Client
class file
Loop over its
methods
Create new Instruction list for
each method
Insert the “enter” function call
where needed
Deal with branch instructions
Update exception table handler
Dump new
class file
- 2008Nov
6
Statistics
Before code instrumentation, 0 deadlocks occurred in 100 runs.
After adding all waits randomly (probability 70%) in one function
only, 65 deadlocks occurred in 100 runs.
After adding all waits randomly (probability 20%) in one function
only, 35 deadlocks occurred in 100 runs.
Adding waits randomly in all functions resulted in 100 deadlocks in
100 runs !
- 2008Nov
7