Page History

final class BankAccount {
  private double balanceAmount;  // Total amount in bank account

  BankAccount(double}} methods or blocks. However, excessive use of synchronization may result in deadlocks (See [CON08-J. Do not call alien methods or constructors that synchronize on the same object as the calling class]).

According to the Java Language Specification \[[JLS 05|AA. Java References#JLS 05]\], "The Java programming language neither prevents nor requires detection of deadlock conditions." Deadlocks can arise unless each thread requests and releases locks in the same order. 

h2. Noncompliant Code Example

This noncompliant code example can deadlock because synchronization is implemented incorrectly. Assume that an attacker has two bank accounts and is capable of requesting two {{depositAllAmount()}} operations in succession, from the two threads started in {{main()}}. 

{code:bgColor=#FFcccc}
class BankAccount {
  private int balanceAmount;  // Total amount in bank account
	 
  private BankAccount(int balance) {
    this.balanceAmount = balance;
  }

  // Deposits the amount from this object instance
  // to BankAccount instance argument ba 
  private synchronizedvoid void depositAllAmountdepositAmount(BankAccount ba, double amount) {
    System.out.println("Depositing all amount...");
synchronized (this) {
      synchronized (ba.balanceAmount += this.balanceAmount;) {
    this.balanceAmount = 0; // withdraw allif (amount from> thisbalanceAmount) instance{
    ba.displayAllAmount();  // Display the new balanceAmount in ba (may cause deadlock)
  }
  
  private synchronized void displayAllAmount() {
    System.out.println(balanceAmount      throw new IllegalArgumentException(
               "Transfer cannot be completed"
          );
  }

  public static void main(String[] args) throws Exception {
 }
       final BankAccount a = new BankAccount(5000)ba.balanceAmount += amount;
    final   BankAccount bthis.balanceAmount -= new BankAccount(6000)amount;
		
    // These two}
 threads correspond to two}
 malicious requests}

 triggered bypublic thestatic attacker
void initiateTransfer(final BankAccount first,
 Thread t1 = newfinal Thread(new Runnable() {
      public void run() {
        a.depositAllAmount(b);
      }
    });
 BankAccount second, final double amount) {

    Thread t2transfer = new Thread(new Runnable() {
        public void run() {
        b  first.depositAllAmount(adepositAmount(second, amount);
        }
    });
    t1.start();
    t2transfer.start();
  }
}
{code}

BankAccount a = new BankAccount(5000);
BankAccount b = new BankAccount(6000);
BankAccount.initiateTransfer(a, b, 1000); // starts thread 1
BankAccount.initiateTransfer(b, a, 1000); // starts thread 2

final class BankAccount {
  private double balanceAmount;  // Total amount in bank account
  private static final Object lock = new Object();

  BankAccount(double balance) {
    this.balanceAmount = balance;
  }

  // Deposits the amount from this object instance
  // to BankAccount instance argument ba
  private void depositAmount(BankAccount ba, double amount) {
    synchronized (lock) {
      if (amount > balanceAmount) {
        throw new IllegalArgumentException(
            "Transfer cannot be completed");
      }
      ba.balanceAmount += amount;
      this.balanceAmount -= amount;
    }
  }

  public static void initiateTransfer(final BankAccount first,
    final BankAccount second, final double amount) {

    Thread transfer = new Thread(new Runnable() {
        @Override public void run() {
          first.depositAmount(second, amount);
        }
    });
    transfer.start();
  }
}

final class BankAccount implements Comparable<BankAccount> {
  private double balanceAmount;  // Total amount in bank account
  private final Object lock;

  private final long id; // Unique for each BankAccount
  private static final AtomicLong nextID = new AtomicLong(0); // Next unused ID

  BankAccount(double balance) {
    this.balanceAmount = balance;
    this.lock = new Object();
    this.id = nextID.getAndIncrement();
  }

  @Override public int compareTo(BankAccount ba) {
     return (this.id > ba.id) ? 1 : (this.id < ba.id) ? -1 : 0;
  }

  // Deposits the amount from this object instance
  // to BankAccount instance argument ba
  public void depositAmount(BankAccount ba, double amount) {
    BankAccount former, latter;
    if (compareTo(ba) < 0) {
      former = this;
      latter = ba;
    } else {
      former = ba;
      latter = this;
    }
    synchronized (former class {{BankAccount}} represent bank accounts. The {{balanceAmount}} field represents the total balance amount available for a particular object (bank account). A user is allowed to initiate an operation _deposit all amount_ that transfers the balance amount from one account to another. This is equivalent to closing a bank account and transferring the balance to a different (existing or new) account. 

An attacker may cause the program to construct two threads that initiate balance transfers from two different {{BankAccount}} object instances, {{a}} and {{b}}. The two transfers are performed from the first object to the second object and from the second object to the first. The first thread atomically transfers the amount from {{a}} to {{b}} by depositing the balance from {{a}} to {{b}} and withdrawing the entire balance from {{a}}. The second thread performs the reverse operation, that is, it transfers the balance from {{b}} to {{a}} and withdraws the balance  from {{b}}. These operations are safe up to this point. However, the {{depositAllAmount()}} method (first thread) invokes the {{synchronized}} {{displayAllAmount()}} method on the instance of object {{b}}. The {{displayAllAmount()}} may request the monitor that is already secured by the second thread that is performing the reverse transfer. The second thread may itself be blocked waiting to enter the monitor secured by the {{displayAllAmount()}} method of the first thread that is attempting to display the balance amount of instance {{a}}. This constitutes a deadlock condition.

The threads in this program request monitors in varying order depending on the interleaving of method calls. If {{Thread T1}} finishes executing before {{Thread T2}}, there are no issues because in this case, locks are acquired ad released in the proper order. Sequences where the threads alternate, such as, {{T1}}, {{T2}}, {{T1}}, {{T2}} can result in a deadlock.    

h2. Compliant Solution (avoid excessive synchronization)

The deadlock can be avoided by declaring the {{balanceAmount}} field as {{volatile}} and removing the {{synchronized}} keyword from the {{displayAllAmount()}} method.

{code:bgColor=#ccccff}
private volatile int balanceAmount;  

//...

private void displayAllAmount() {
  System.out.println(balanceAmount);
}
{code}

The {{displayAllAmount()}} method does not require additional synchronization because it atomically displays the latest value for the balance amount.

To be compliant, do not request a lock when it is already held by another object where that object is waiting for the requesting object to release its own lock. When this is not possible, avoid synchronizing unnecessary accesses.

h2. Noncompliant Code Example

This noncompliant code example consists of three integer arrays: {{distances}}, {{speeds}} and {{times}}. The distances are fixed and cannot be changed by the client. The client can pass a {{time}} array as argument to method {{getAverageSpeed()}} to find the average speed. It can also pass a {{speed}} array as argument to method {{getAverageTime()}} to find the average time taken. This allows the client to calculate the third parameter from two given parameters. For example, speed is calculated as distance/time.

The example also uses an array of internal lock objects instead of intrinsic synchronization (or method synchronization) so that multiple threads do not interfere with the array elements when the arrays are being traversed. Because it is not possible to lock on primitive types, a direct lock on the array elements cannot be obtained. Instead, an array of raw {{Objects}} ({{locks}}) is used.

{code:bgColor=#FFcccc}
public class RecursiveTravel {
  final static int MAX = 20;
  static int[] distances = new int[MAX];
  static int[] times = new int[MAX];
  static int[] speeds = new int[MAX];
  static Object[] locks = new Object[MAX];
  
  static {
    for (int i = 0; i < MAX; i++) {
      distances[i] = 10;  // Assuming all distances are 10 for illustrationsynchronized (latter) {
        if (amount > balanceAmount) {
      locks[i] = new Object(); // Createthrow locknew objectsIllegalArgumentException(
    }
  }

  double getAverageSpeed(int[] time) {
   "Transfer timescannot = time.clone(be completed");
    return getSpeed(0, 0) / MAX;}
  }

  double getAverageTime(int[] speed) {    ba.balanceAmount += amount;
    speeds = speed.clone()    this.balanceAmount -= amount;
    return getTime(MAX -}
 1, 0) / MAX;}
  }

  int getSpeed(int i, int speed) { // Acquire locks in nondecreasing orderpublic static void initiateTransfer(final BankAccount first,
    final BankAccount second, final double amount) {

    if(i > MAX - 1Thread transfer = new Thread(new Runnable() {
        @Override public void return speed;run() {
    }

      synchronized(locks[i]) {first.depositAmount(second, amount);
      speed += distances[i]/times[i];
 }
    });
   return getSpeed(++i, speedtransfer.start();
    }	  
  }

  int getTime(int i, int time) { // Acquire locks in nonincreasing order
    if(i <= -1) {		 
      return time;
    } 

    synchronized(locks[i]) {
      time += distances[i]/speeds[i];
      return getTime(--i, time);
    }	  
  }
}
{code}

The {{getSpeed()}} and {{getTime()}} methods recursively calculate the sum of the speeds and times, respectively, for each distance value in the array. The implementation is deadlock prone because the recursive calls occur within the synchronized regions of these methods and acquire locks in opposite numerical orders. That is, {{getSpeed()}} requests locks from index 0 to {{MAX}} - 1 (19) whereas {{getTime()}} requests them from index {{MAX}} - 1 (19) to 0. Because of recursion, no previously acquired locks are released by either method. A deadlock occurs when two threads call these methods out of order in that, one thread calls {{getSpeed()}} while the other calls {{getTime()}} before either method has finished executing.

One such execution order that causes a deadlock is shown below:

{code}
Thread T1 (in getTime()) acquires lock:
i = 19
...
i = 0

Thread T1 (in getSpeed()) acquires lock:
i = 0
...
i = 18

Thread T2 (in getTime()) acquires lock:
i = 19

Thread T1 next wants, i = 19 which T2 holds
Thread T2 next wants, i = 18 which T1 holds
{code}


{mc}
// Class to make the above code run in a multi-threaded environment
public class RecursiveControl implements Runnable {
  static RecursiveTravel t = new RecursiveTravel();
  static int[] speed = new int[MAX];
  static int[] time = new int[MAX];
  static {
    for (int i = 0; i < MAX; i++) {
      speed[i] = 2;
      time[i] = 2;
    }
  }

  public void run() {
    t.getTime(speed); 	
    t.getSpeed(time);
  }

  public static void main(String[] args) throws InterruptedException {
    Runnable r1 = new RecursiveControl();
    Runnable r2 = new RecursiveControl();
    Thread c1 = new Thread(r1);
    Thread c2 = new Thread(r2);
    c1.start();
    c2.start();	
  }
}
{mc}

h2. Compliant Solution 

This compliant solution moves the recursive calls from the {{getSpeed()}} and {{getTime()}} methods to outside the {{synchronized}} block. Consequently, locks are released as soon as they are no longer needed. Also, the locks are acquired in the same order (nondecreasing) form both these methods. This eliminates potential deadlock conditions.  

{code:bgColor=#ccccff}
public class RecursiveTravel {
  // ...

  double getAverageSpeed(int[] time) {
    times = time.clone();
    return getSpeed(MAX - 1, 0) / MAX;
  }

  double getAverageTime(int[] speed) {
    speeds = speed.clone();
    return getTime(MAX - 1, 0) / MAX;
  }

  int getSpeed(int i, int speed) { // Acquire locks in nondecreasing order
    if(i > MAX - 1) {
      return speed;
    }

    synchronized(locks[i]) {
      speed += distances[i]/times[i];
    }	  
    return getSpeed(++i, speed); // Moved outside of synchronized region
  }

  int getTime(int i, int time) { // Acquire locks in nondecreasing order
    if(i > MAX - 1) {  		 
      return time;
    } 

    synchronized(locks[i]) {
      time += distances[i]/speeds[i];
    }	  
    return getTime(++i, time); // Moved outside of synchronized region
  }
}
{code}

h2. Risk Assessment

Acquiring and releasing locks in the wrong order may result in deadlocks.

|| Rule || Severity || Likelihood || Remediation Cost || Priority || Level ||
| CON12- J | low | likely | high | {color:green}{*}P3{*}{color} | {color:green}{*}L3{*}{color} |

h3. Automated Detection

TODO

h3. Related Vulnerabilities

Search for vulnerabilities resulting from the violation of this rule on the [CERT website|https://www.kb.cert.org/vulnotes/bymetric?searchview&query=FIELD+KEYWORDS+contains+CON34-J].

h2. References

\[[JLS 05|AA. Java References#JLS 05]\] [Chapter 17, Threads and Locks|http://java.sun.com/docs/books/jls/third_edition/html/memory.html]
\[[SDN 08|AA. Java References#SDN 08]\] [Sun Developer Network Tech tips|http://java.sun.com/developer/TechTips/2000/tt0328.html]&nbsp;
\[[MITRE 09|AA. Java References#MITRE 09]\] [CWE ID 412|http://cwe.mitre.org/data/definitions/412.html] "Unrestricted Lock on Critical Resource"

----
[!The CERT Sun Microsystems Secure Coding Standard for Java^button_arrow_left.png!|CON11-J. Do not assume that declaring an object volatile guarantees visibility of its members]&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;[!The CERT Sun Microsystems Secure Coding Standard for Java^button_arrow_up.png!|11. Concurrency (CON)]&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;[!The CERT Sun Microsystems Secure Coding Standard for Java^button_arrow_right.png!|CON13-J. Do not try to force thread shutdown]

}

final class BankAccount {
  private double balanceAmount;  // Total amount in bank account
  private final Lock lock = new ReentrantLock();
  private final Random number = new Random(123L);

  BankAccount(double balance) {
    this.balanceAmount = balance;
  }

  // Deposits amount from this object instance
  // to BankAccount instance argument ba
  private void depositAmount(BankAccount ba, double amount)
                             throws InterruptedException {
    while (true) {
      if (this.lock.tryLock()) {
        try {
          if (ba.lock.tryLock()) {
            try {
              if (amount > balanceAmount) {
                throw new IllegalArgumentException(
                    "Transfer cannot be completed");
              }
              ba.balanceAmount += amount;
              this.balanceAmount -= amount;
              break;
            } finally {
              ba.lock.unlock();
            }
          }
        } finally {
          this.lock.unlock();
        }
      }
      int n = number.nextInt(1000);
      int TIME = 1000 + n; // 1 second + random delay to prevent livelock
      Thread.sleep(TIME);
    }
  }

  public static void initiateTransfer(final BankAccount first,
    final BankAccount second, final double amount) {

    Thread transfer = new Thread(new Runnable() {
        public void run() {
          try {
            first.depositAmount(second, amount);
          } catch (InterruptedException e) {
            Thread.currentThread().interrupt(); // Reset interrupted status
          }
        }
    });
    transfer.start();
  }
}

// Immutable WebRequest
public final class WebRequest {
  private final long bandwidth;
  private final long responseTime;

  public WebRequest(long bandwidth, long responseTime) {
    this.bandwidth = bandwidth;
    this.responseTime = responseTime;
  }

  public long getBandwidth() {
    return bandwidth;
  }

  public long getResponseTime() {
    return responseTime;
  }
}

public final class WebRequestAnalyzer {
  private final Vector<WebRequest> requests = new Vector<WebRequest>();

  public boolean addWebRequest(WebRequest request) {
    return requests.add(new WebRequest(request.getBandwidth(),
                        request.getResponseTime()));
  }

  public double getAverageBandwidth() {
    if (requests.size() == 0) {
      throw new IllegalStateException("The vector is empty!");
    }
    return calculateAverageBandwidth(0, 0);
  }

  public double getAverageResponseTime() {
    if (requests.size() == 0) {
      throw new IllegalStateException("The vector is empty!");
    }
    return calculateAverageResponseTime(requests.size() - 1, 0);
  }

  private double calculateAverageBandwidth(int i, long bandwidth) {
    if (i == requests.size()) {
      return bandwidth / requests.size();
    }
    synchronized (requests.elementAt(i)) {
      bandwidth += requests.get(i).getBandwidth();
      // Acquires locks in increasing order
      return calculateAverageBandwidth(++i, bandwidth);
    }
  }

  private double calculateAverageResponseTime(int i, long responseTime) {
    if (i <= -1) {
      return responseTime / requests.size();
    }
    synchronized (requests.elementAt(i)) {
      responseTime += requests.get(i).getResponseTime();
      // Acquires locks in decreasing order
      return calculateAverageResponseTime(--i, responseTime);
    }
  }
}

public final class WebRequestAnalyzer {
  private final Vector<WebRequest> requests = new Vector<WebRequest>();

  public boolean addWebRequest(WebRequest request) {
    return requests.add(new WebRequest(request.getBandwidth(),
                        request.getResponseTime()));
  }

  public double getAverageBandwidth() {
    if (requests.size() == 0) {
      throw new IllegalStateException("The vector is empty!");
    }
    return calculateAverageBandwidth(0, 0);
  }

  public double getAverageResponseTime() {
    if (requests.size() == 0) {
      throw new IllegalStateException("The vector is empty!");
    }
    return calculateAverageResponseTime(0, 0);
  }

  private double calculateAverageBandwidth(int i, long bandwidth) {
    if (i == requests.size()) {
      return bandwidth / requests.size();
    }
    synchronized (requests.elementAt(i)) {
      // Acquires locks in increasing order
      bandwidth += requests.get(i).getBandwidth();
      return calculateAverageBandwidth(++i, bandwidth);
    }
  }

  private double calculateAverageResponseTime(int i, long responseTime) {
    if (i == requests.size()) {
      return responseTime / requests.size();
    }
    synchronized (requests.elementAt(i)) {
      // Acquires locks in increasing order
      responseTime += requests.get(i).getResponseTime();
      return calculateAverageResponseTime(++i, responseTime);
    }
  }
}