leap

leap

LEAP: Lightweight deterministic multiprocessor replay for concurrent Java programs

LEAP is a new local order based efficient deterministic record and replay technique for multi-threaded Java programs running on general multi-processor environments. It is more than 10x faster than conventional global order based approaches and 2x to 10x faster than other local order based approaches. It's recording overhead on Tomcat and Derby is less than 10%. It is able to deterministically reproduce 7 out of 8 real bugs in Tomcat and Derby, 13 out of 16 benchmark bugs in IBM ConTest benchmark suite, and 100% of the randomly injected concurrency bugs.

people
document
download
example
experiment

People

LEAP is now maintained by Jeff Huang. If you have any questions, please contact Jeff.

Document

Here is our FSE paper describing LEAP.

Download

Example

This page shows a simple example program that contains a heisenbug and how to use LEAP to deterministically reproduce the bug once the bug manifests itself in a certain execution.

Example program: The following simple program starts two threads to parse a shared URL. Due to a data race bug, the program crashes when one thread use the dirty data modified by another thread to reference the url in the method getval. The example program can be downloaded here.

public class Example {                                             
    public static void main (String [] args) {                  
        String url="key1=Alice&key2=Bob"; 
        URLParse urlparse = new URLParse (url);          
        Thread t1 = new ExampleThread(urlparse ,"key1");    
        Thread t2 = new ExampleThread(urlparse ,"key2");
        System.out.println("before parsing: "+urlparse.getURL()); 
        t2.start ();
t1.start();
try {
    t1.join();
    t2.join();
} catch (InterruptedException e) {
    e.printStackTrace();
}
System.out.println("after parsing: "+urlparse.getURL()); 
    }
}

public class ExampleThread extends Thread                                  
{                                                                            
    URLParse urlparse;                                             
    String key;                                                         
    ExampleThread(URLParse url,String key){                                                                        
        this.urlparse = url;                                  
        this.key = key;                                               
    }                                                                       
    public void run()                                               
    {       
     try{
     urlparse.parse(key);     
     }catch(Exception e)
     {
     e.printStackTrace();
     "leap_Crashed_with".equals(e);
     }
    }                                                                      
}

public class URLParse {
    private String url;                                                    
    
    URLParse (String url)
    {                                            
this.url=url;                                                    
    }                                                                           
    //should be synchronized                                       
    public void parse(String key)                                            
    {                                                                           
     String val = getVal(key);
     if(val.equals("Alice"))
     replaceVal(key,"A");
     if(val.equals("Bob"))
     replaceVal(key,"B");
    }
    private void replaceVal(String key, String newVal)
    {
        int keyPos=url.indexOf(key);                             
        int valPos=url.indexOf("=", keyPos)+1;               
        int ampPos=url.indexOf("&", keyPos);                
        if(ampPos<0) ampPos = url.length();               
        url=url.substring(0, valPos)                               
                +newVal+url.substring(ampPos);       
    }                                                                          
    private String getVal(String key)
    {                       
        int keyPos=url.indexOf(key);                       
        int valPos=url.indexOf("=", keyPos)+1;       
        int ampPos=url.indexOf("&", keyPos);               
        if(ampPos<0) ampPos=url.length(); 
        return url.substring(valPos,ampPos);                  
    }
    public String getURL()
    {
     return url;
    }
}

LEAP HowTo:

Step 1: transformer

javac ./example/Example.java

java -cp .:transformer.jar edu.hkust.leap.Main example.Example
rm -rf tmp/*/edu
Two new directories "tmp/runtime" and "tmp/replay" will be created, which contain the transformed runtime version and replay version of example.Example.class, respectively.

Step 2: recorder

java -cp ./tmp/runtime:recorder.jar edu.hkust.leap.Main 1 example.Example
Here, the input parameter "1" is the number of SPEs reported in Step 1.

If it crashes, a replay driver will be generated by LEAP to reproduce the failure.

Step 3: replayer

javac -cp ./tmp/replay/:replayer.jar ./src/replaydriver/ReplayDriver.java

java -cp ./src/:./tmp/replay/:replayer.jar replaydriver.ReplayDriver

Experiment

We have conducted thorough experiments to demonstrate the performance of LEAP. We use real complex Java server programs and third-party benchmarks to assess the recording overhead of LEAP, compared to the related approaches. We have also designed a micro-benchmark to conduct controlled experiments for quantifying various runtime characteristics of the evaluated techniques. We use bug reproducibility as a way to verify if our technique can faithfully and deterministically reproduce problematic concurrent runs.

PART 1. Table 1 shows some of the relevant static attributes of the benchmarked programs as well as the associated runtime overhead of the evaluated record and replay techniques. LEAP is the fastest on all the evaluated applications. It is even more than 150x faster than global clock on MolDyn. For Derby and Tomcat, LEAP is 5x to 10x faster than all the related approaches. The runtime overhead of LEAP on Derby and Tomcat is less than 10% (9.9% and 7.3% respectively). LEAP's overhead is large on Avrora (626%), the reason is that there are several SPEs in Avrora that are frequently accessed in hot loops.

Table 1: The runtime performance of LEAP and the state of the art techniques. Log and LogCmp in KB/s.

Application	LOC	Total	SPE	SPESize	Log	LogCmp	LEAP	Lamport	Instant	Global
Avrora	93K	16003	1725(11%)	113	30623	796	626%	1697%	1821%	1036%
Lusearch	69K	11497	1140(9.9%)	75	7485	632	74%	308%	379%	227%
Derby	1.51M	48356	1433(3.0%)	264	18545	113	9.9%	68%	113%	52%
Tomcat	535K	23046	654(2.6%)	163	15351	51.0	7.3%	39%	44%	34%
MolDyn	864	821	634(77%)	66	110761	37760	64%	2776%	3567%	9960%
MonteCarlo	3128	427	104(24%)	18	70384	1994	7.5%	7.9%	8.6%	9.1%
RayTracer	1431	442	223(50%)	19	124239	35878	18%	39%	43%	94%

PART 2. Figure 1 and 2 show the runtime characteristics of LEAP and the related techniques on our micro-benchmark. By fixing the number of threads to 10, as the number of SPE increases from 10 to 500, LEAP is more than 10x faster than global clock, more than 5x faster than InstantReplay, and at least 2x faster than Lamport clock. Global clock is the slowest among the four techniques. Figure 2 shows a similar performance trend as the number of threads increases from 10 to 80 and the number of SPE is fixed to 1000. The micro-benchmark can be downloaded here .

PART 3: Table 2 and 3 show the description of the real concurrency bugs and the benchmark bugs used in our experiments. All the 8 real bugs in Table 2 are extracted from the Derby andTomcat bug repositories9 that were reported by users. The 16 benchmark bugs in Table 3 are from the IBM ConTest benchmark suite, which cover the major types of concurrency bugs, including data races, atomicity violation, order violation, and deadlocks. We also run both JaRec and LEAP on these buggy programs to compare the bug reproducibility between them. For the 8 real world concurrency bugs, LEAP is able to deterministically reproduce 7 of them (88%) except tomcat4036, and JaRec is able to reproduce none of them. For the 16 benchmark bugs, LEAP can reproduce 13 of them (81%) excepts BufferWriter, Loader, and DeadlockException, while JaRec can only reproduce one of them (Deadlock).

Table 2: Summary of the evaluated real bugs

Bug Id	Version	LOC	Exception Type
Derby230	Derby-10.1	1.34M	DuplicateDescriptor
Derby1573	Derby-10.2	1.52M	NullPointerException
Derby3260	Derby-10.2	1.52M	SQLException
Derby2861	Derby-10.3	1.51M	NullPointerException
Tomcat37458	Tomcat-5.5	535K	NullPointerException
Tomcat728	Tomcat-3.2	150K	NullPointerException
Tomcat4036	Tomcat-3.3	184K	NumberFormatException
Tomcat27315	Tomcat-4.1	361K	ConcurrentModification

Table 3: Summary of the evaluated benchmark bugs

Bug Name	LOC	Bug Description
BubbleSort	362	Not atomic, Orphaned-Thread
AllocationVector	286	Weak-reality, two stage access
AirlineTickets	95	Not-atomic interleaving
PingPong	272	Not-atomic
BufferWriter	255	Wrong or no-Lock
RandomNumbers	359	Blocking-Critical-Section
Loader	130	Initialization-Sleep Pattern
Account	155	Wrong or no-Lock
LinkedList	416	Not-atomic
BoundedBuffer	536	Notify instead of notifyAll
MergeSort	375	Not-atomic
Critical	73	Not-atomic
Deadlock	135	Deadlock
DeadlockException	255	Deadlock
FileWriter	311	Not-atomic
Manager	236	Not-atomic