CON12-J. Avoid deadlock by requesting and releasing locks in the same order

To avoid data corruption in multithreaded Java programs, shared data must be protected from concurrent modifications and accesses. This can be performed at the object level by using synchronized methods or blocks, or by using dynamic lock objects. However, excessive use of locking may result in deadlocks (See CON08-J. Do not call alien methods that synchronize on the same objects as any callers in the execution chain).

"The Java programming language neither prevents nor requires detection of deadlock conditions." [[JLS 05]]. Deadlocks can arise when two or more threads request and release locks in different orders.

Noncompliant Code Example

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

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 synchronized void depositAllAmount(BankAccount ba) {
    ba.balanceAmount += this.balanceAmount;
    this.balanceAmount = 0; // withdraw all amount from this instance
    ba.displayAllAmount();  // Display the new balanceAmount in ba (may cause deadlock)
  }
  
  private synchronized void displayAllAmount() {
    System.out.println(balanceAmount);
  }

  public static void main(String[] args) throws Exception {
    final BankAccount a = new BankAccount(5000);
    final BankAccount b = new BankAccount(6000);
		
    // These two threads correspond to two malicious requests triggered by the attacker
    Thread t1 = new Thread(new Runnable() {
      public void run() {
        a.depositAllAmount(b);
      }
    });
 
    Thread t2 = new Thread(new Runnable() {
      public void run() {
        b.depositAllAmount(a);
      }
    });
    t1.start();
    t2.start();
  }
}

Objects of 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 instance a to b and b to a. 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, or T2 before T1, there are no issues because in these cases, locks are acquired and released in the same order. Sequences where the threads alternate, such as, T1, T2, T1, T2 may deadlock.

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.

private volatile int balanceAmount;  

//...

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

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.

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 an 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 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. This fine-grained locking strategy is more flexible than using a single global lock object which has the effect of blocking all the array elements from being accessed from other threads while the computation is in progress.

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 illustration
      locks[i] = new Object(); // Create lock objects
    }
  }

  double getAverageSpeed(int[] time) {
    times = time.clone();
    return averageSpeedCalculator(0, 0, 0);
  }

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

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

    synchronized(locks[i]) {
      distance += distances[i];
      time += times[i];    
      return averageSpeedCalculator(++i, distance, time);
    }	  
  }

  int averageTimeCalculator(int i, int distance, int speed) { // Acquires locks in nonincreasing order
    if(i <= -1) {		 
      return distance/speed;
    } 

    synchronized(locks[i]) {
      distance += distances[i];
      speed += speeds[i];  
      return averageTimeCalculator(--i, distance, speed);
    }	  
  }
}

The averageSpeedCalculator() and averageTimeCalculator() methods recursively calculate the sum of the speeds and times, respectively, for each distance value in the array. This 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, averageSpeedCalculator() requests locks from index 0 to MAX - 1 (19) whereas averageTimeCalculator() 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 averageSpeedCalculator() while the other calls averageTimeCalculator() before either method has finished executing.

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

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

Compliant Solution

This compliant solution moves the recursive calls from the averageSpeedCalculator() and averageTimeCalculator() methods to outside the synchronized block.

public class RecursiveTravel {
  // ...

   double getAverageSpeed(int[] time) {
    times = time.clone();
    return averageSpeedCalculator(0, 0, 0);
  }

  double getAverageTime(int[] speed) {
    speeds = speed.clone();
    return averageTimeCalculator(0, 0, 0);
  }

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

    synchronized(locks[i]) {
      distance += distances[i];
      time += times[i];    
    }	  
    return averageSpeedCalculator(++i, distance, time); // Moved outside the synchronized region
  }

  int averageTimeCalculator(int i, int distance, int speed) { // Acquires locks in nondecreasing order
    if(i <= -1) {		 
      return distance/speed;
    } 

    synchronized(locks[i]) {
      distance += distances[i];
      speed += speeds[i];  
    }	  
    return averageTimeCalculator(--i, distance, speed); // Moved outside the synchronized region
  }
}

Consequently, locks are released as soon as they are no longer needed. Also, the locks are acquired in the same order (nondecreasing) from both these methods. This eliminates potential deadlock conditions.

Risk Assessment

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

Automated Detection

TODO

Related Vulnerabilities

Search for vulnerabilities resulting from the violation of this rule on the CERT website.

References

[[JLS 05]] Chapter 17, Threads and Locks
[[Halloway 00]]
[[MITRE 09]] CWE ID 412 "Unrestricted Lock on Critical Resource"

[!The CERT Sun Microsystems Secure Coding Standard for Java^button_arrow_left.png!]      [!The CERT Sun Microsystems Secure Coding Standard for Java^button_arrow_up.png!]      [!The CERT Sun Microsystems Secure Coding Standard for Java^button_arrow_right.png!]