PECAN: Persuasive Prediction of Concurrency Access Anomalies

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.



Please contact Jeff if you have any question about PECAN.


Please read our ISSTA paper describing the details of PECAN.



This section shows how to use PECAN.

  • Sample Program, :
    package stringbuffer;
    * @(#)	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, 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);
        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)
            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)
                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());
            switch (choice) {
                case 0:
                case 1:
                    al1.delete(0, al1.length());
        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();
  • This simple program above contains an atomicity violation bug (colored yellow) in the StringBuffer class. When this bug is triggered, the program will crash and throws an StringIndexOutOfBoundsException. However, this concurrency bug is very hard to manifest. You may need to run the program thousands of times before it manifests itself.
    Let's run it and see what will happen:
    started Thread[Thread-0,5,main]
    started Thread[Thread-1,5,main]

  • We next show how PECAN exposes this bug deterministically:
    1. Compile the source
      Suppose the source is under the path ./app
      javac ./app/stringbuffer/
    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/:pecan-instrumentor.jar edu.hkust.clap.Main stringbuffer.StringBufferTest
      Delete redundant classes:
         rm -rf ./tmp/*/edu
    3. Trace collection
      Collect a trace of the program execution into the path ./tmp and also generate a replay driver in the path ./src for re-executing the program:
          java -cp ./tmp/runtime/:pecan-monitor edu.hkust.clap.Main stringbuffer.StringBufferTest
    4. Trace analysis
      PECAN searches the violation patterns on the trace and generates a corresponding schedule for exposing each violation. The generated schedules are in the path ./tmp/schedule_tid and ./schedule_line.
          java -cp pecan-engine.jar edu.hkust.clap.engine.Engine
      The following report will be generated after the trace analysis:
      *** 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
    5. Compile the replay driver
      javac -cp ./tmp/replay/:pecan-replayer.jar ./src/replaydriver/
    6. Exposing the bug
      Re-execute the program according to the generated schedule to determinisitically expose the atomicity violation bug that crashes the program.
        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(
      at stringbuffer.StringBuffer.append(
    The above steps illustrate the usage of each component of PECAN. For more convenient use, we provide an ant script runall.xml to run them all together.
    ant -f runall.xml
    Buildfile: runall.xml
        [input] Please enter your app main class name:
    pattern-search and schedule-generation:
         [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(
         [java]     at stringbuffer.StringBuffer.append(
         [java]     at


    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  

    To expose these violation bugs deterministically, simply download the all-in-one package and use the following command:
    ant -f runall.xml
    Then you are asked to input the name of the program to be analyzed:
        [input] Please enter your app main class name:
    Just input the class name of the source, for instance, account.Bank. You will see "bug hatching clips" such as:
         [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(
         [java]     at account.Bank.go(
         [java]     at account.Bank.main(
         [java]     at replaydriver.ReplayDriver$