Predictive analysis is a powerful technique that exposes concurrency bugs in un-exercised program executions. However, current predictive analysis approaches lack the persuasiveness property as they offer little assistance in helping programmers fully understand the execution history that triggers the predicted bugs. We present a persuasive bug prediction technique as well as a prototype tool, PECAN, for detecting general access anomalies (AAs) in concurrent programs. The main characteristic of PECAN is that, in addition to predict AAs in a more general way, it generates ``bug hatching clips" that deterministically instruct the input program to exercise the predicted AAs. The key ingredient of PECAN is an efficient offline schedule generation algorithm, with proof of the soundness, that guarantees to generate a feasible schedule for every real AA in programs that use locks in a nested way. We evaluate PECAN using twenty-two multi-threaded subjects including six large concurrent systems and our experiments demonstrate that PECAN is able to effectively predict and deterministically expose real AAs. Several serious and previously unknown bugs in large open source concurrent systems were also revealed in our experiments.
Contents:
This section shows how to use PECAN.
package stringbuffer;
/*
* @(#)StringBuffer.java 1.78 03/05/16
*
* Copyright 2003 Sun Microsystems, Inc. All rights reserved.
* SUN PROPRIETARY/CONFIDENTIAL. Use is subject to license terms.
*/
public final class StringBuffer implements java.io.Serializable, CharSequence
{
private char value[];
private int count;
...
public StringBuffer(int length) {
value = new char[length];
shared = false;
}
public StringBuffer(String str) {
this(str.length() + 16);
append(str);
}
public synchronized int length() {
return count;
}
private void expandCapacity(int minimumCapacity) {
int newCapacity = (value.length + 1) * 2;
if (newCapacity < 0) {
newCapacity = Integer.MAX_VALUE;
} else if (minimumCapacity > newCapacity) {
newCapacity = minimumCapacity;
}
char newValue[] = new char[newCapacity];
System.arraycopy(value, 0, newValue, 0, count);
value = newValue;
shared = false;
}
public synchronized void getChars(int srcBegin, int srcEnd, char dst[], int dstBegin) {
if (srcBegin < 0) {
throw new StringIndexOutOfBoundsException(srcBegin);
}
if ((srcEnd < 0) || (srcEnd > count)) {
throw new StringIndexOutOfBoundsException(srcEnd);
}
if (srcBegin > srcEnd) {
throw new StringIndexOutOfBoundsException("srcBegin > srcEnd");
}
System.arraycopy(value, srcBegin, dst, dstBegin, srcEnd - srcBegin);
}
public synchronized StringBuffer append(StringBuffer sb) {
if (sb == null) {
sb = NULL;
}
int len = sb.length();
int newcount = count + len;
if (newcount > value.length)
expandCapacity(newcount);
sb.getChars(0, len, value, count );
count = newcount;
return this;
}
public synchronized StringBuffer delete(int start, int end) {
if (start < 0)
throw new StringIndexOutOfBoundsException(start);
if (end > count)
end = count;
if (start > end)
throw new StringIndexOutOfBoundsException();
int len = end - start;
if (len > 0) {
if (shared)
copy();
System.arraycopy(value, start+len, value, start, count-end);
count -= len;
}
return this;
}
}
|
package stringbuffer;
public class StringBufferTest extends Thread {
StringBuffer al1, al2;
int choice;
public StringBufferTest(StringBuffer al1, StringBuffer al2, int choice) {
this.al1 = al1;
this.al2 = al2;
this.choice = choice;
}
public void run() {
System.out.println("started " + Thread.currentThread());
System.out.flush();
switch (choice) {
case 0:
al1.append(al2);
break;
case 1:
al1.delete(0, al1.length());
break;
}
}
public static void main(String args[]) {
StringBuffer al1 = new stringbuffer.StringBuffer("Hello");
StringBuffer al2 = new stringbuffer.StringBuffer("World");
(new StringBufferTest(al1, al2, 0)).start();
(new StringBufferTest(al2, al1, 1)).start();
}
}
|
started Thread[Thread-0,5,main] started Thread[Thread-1,5,main] |
javac ./app/stringbuffer/StringBufferTest.java |
java -cp ./app/:pecan-instrumentor.jar edu.hkust.clap.Main stringbuffer.StringBufferTest
|
rm -rf ./tmp/*/edu |
java -cp ./tmp/runtime/:pecan-monitor edu.hkust.clap.Main stringbuffer.StringBufferTest
|
java -cp pecan-engine.jar edu.hkust.clap.engine.Engine
|
*** Violation Patterns [ID - Memory Location - Line Number - Thread - Access Type] *** -------------------------------------- *** AV-I --- 33 "stringbuffer.StringBuffer.count" 144 9 READ * 57 "stringbuffer.StringBuffer.count" 667 10 WRITE * 40 "stringbuffer.StringBuffer.count" 327 9 READ *** ------------------------------------- Number of Threads: 3 Number of Shared Variables: 5 Number of Lock Nodes: 16 Number of Message Nodes: 7 Number of Non-Method Entry/Exit Nodes: 60 Number of Read/Write Nodes: 37 Number of Total Nodes: 92 Number of Races: 0 Number of Atomicity Violations: 1 Number of ASVs: 0 Total Pattern Search Time: 2 ms Total Schedule Generation Time: 5 ms Total Processing Time: 40 ms |
javac -cp ./tmp/replay/:pecan-replayer.jar ./src/replaydriver/ReplayDriver.java |
java -cp ./src/:./tmp/replay/:pecan-replayer.jar replaydriver.ReplayDriver 1 |
started Thread[Thread-0,5,main] started Thread[Thread-1,5,main] Violation Successfully Created! Exception in thread "Thread-0" java.lang.StringIndexOutOfBoundsException: String index out of range: 5 at stringbuffer.StringBuffer.getChars(StringBuffer.java:328) at stringbuffer.StringBuffer.append(StringBuffer.java:447) at stringbuffer.StringBufferTest.run(StringBufferTest.java:25) |
ant -f runall.xml |
Buildfile: runall.xml
compile-source:
[input] Please enter your app main class name:
stringbuffer.StringBufferTest
transform:
...
collect-trace:
...
pattern-search and schedule-generation:
...
re-execute:
[java] 1
[java] started Thread[Thread-0,5,main]
[java] started Thread[Thread-1,5,main]
[java] Violation Successfully Created!
[java] Exception in thread "Thread-0" java.lang.StringIndexOutOfBoundsException: String index out of range: 5
[java] at stringbuffer.StringBuffer.getChars(StringBuffer.java:328)
[java] at stringbuffer.StringBuffer.append(StringBuffer.java:447)
[java] at stringbuffer.StringBufferTest.run(StringBufferTest.java:25)
|
We have evaluated PECAN on a set of popular subjects used in benchmarking the concurrency defect analysis techniques and also a number of large multi-threaded Java applications. PECAN detected real violations in almost all the evaluated subjects:
| Account | BuggyProgram | Critical | Loader | Manager | MergeSort | Shop |
| StringBuffer | ArrayList | LinkedList | HashSet | TreeSet | Moldyn | RayTracer | MonteCarlo |
| Cache4j | SpecJBB | Hedc | Weblech | OpenJMS | Jigsaw | Derby |
ant -f runall.xml |
[input] Please enter your app main class name:
|
[java] 3
[java] Bank system started
[java] loop: 2
[java] sum: 256
[java] loop: 2
[java] sum: -174
[java] sum: -33
[java] .
[java] End of the week.
[java] sum: 76
[java] Violation Successfully Created!
[java] Bank records = 332, accounts balance = 49.
[java] java.lang.RuntimeException: ERROR: records don't match !!!
[java] at account.Bank.checkResult(Bank.java:81)
[java] at account.Bank.go(Bank.java:70)
[java] at account.Bank.main(Bank.java:30)
[java] at replaydriver.ReplayDriver$1.run(ReplayDriver.java:25)
|