SimTrace: An Efficient Static Trace Simplification Technique for Debugging Concurrent Programs

One of the major difficulties in debugging concurrent programs is that the programmer usually experiences frequent thread context switches, which perplexes the reasoning process. This problem can be alleviated by trace simplification techniques, which produce the same computation process but with much fewer number of context switches. The state of the art trace simplification technique takes a dynamic approach and does not scale well to large traces, hampering its practicality. We present a static trace simplification approach, SimTrace, that dramatically improves the efficiency of trace simplification through reasoning about the computation equivalence of traces offline. By constructing a dependence graph model of events, our trace simplification algorithm scales linearly to the trace size and quadratic to the number of nodes in the dependence graph. Underpinned by a trace equivalence theorem, we guarantee that the results generated by SimTrace are sound and no dynamic program re-execution is required to validate the trace equivalence. Our experiments show that SimTrace scales well to traces with more than 1M events, making it attractive to practical use.

Contents:

• People
• Download
• Example
• Experiments

People

• Jeff Huang
• Charles Zhang

Download

• The instrumentor: simtrace-instrumentor.jar
• The trace colletor: simtrace-monitor.jar
• The simtrace engine: simtrace-engine.jar
• The replayer: simtrace-replayer.jar


• All in one package: all.zip

Example

This section shows how to use SimTrace.

package example;
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());
    	}
}

package example;
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();
    		System.exit(1);
    	}
    }                                                                      
}

package example;
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;
    }
}

1. Compile the source
   Suppose the source is under the path ./app

   javac ./app/example/*.java

2. Instrumentation
   Generate two versions of the program into the path ./tmp/, one for trace collection and the other for re-execution.

   java -cp ./app/:simtrace-instrumentor.jar edu.hkust.clap.Main example.Example

   Delete redundant classes:

   rm -rf ./tmp/*/edu

3. Trace collection
   Collect a buggy execution trace of this program into the path ./tmp and also generate a replay driver in the path ./src for re-executing the program:

   java -cp ./tmp/runtime/:simtrace-monitor.jar edu.hkust.clap.Main example.Example

4. Trace analysis
   SimTrace simplifies the trace according to the algorithm in our technical report and generates another equivalent trace for exposing the same data race bug. The generated trace are in the path ./tmp.

   java -cp simtrace-engine.jar edu.hkust.clap.engine.SimTraceMain

   The following report will be generated after the trace analysis:

   Number of Threads: 3 Number of Shared Variables: 1 Number of Lock Nodes: 0 Number of Message Nodes: 8 Number of Non-Method Entry/Exit Nodes: 33 Number of Read/Write Nodes: 25 Number of Total Nodes: 61 Number of Original Context Switches: 12 Number of Simplified Context Switches: 5 Number of Nodes In the Original Graph: 6 Number of Edges In the Original Graph: 10 Total Data Load Time: 30 ms Total Graph Construction Time: 3 ms Total Graph Merging Time: 0 ms Total Graph Topological Sort Time: 0 ms Total Schedule Generation Time: 3 ms Total Processing Time: 37 ms

5. Compile the replay driver
   

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

6. Deterministic re-execution
   Re-execute the program according to the simplified schedule to determinisitically expose the data race bug that crashed the program.

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

Experiments

We have evaluated SimTrace using several popular multi-threaded subjects as well as a number of large multi-threaded Java applications. SimTrace is able to efficiently and significantly simplify the trace.