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). For instance, to avoid deadlocks, the paint(), dispose(), stop(), destroy() methods in an applet should not be synchronized because they are always called and used from dedicated threads.
"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 void depositAllAmount(BankAccount ba) {
synchronized (this) {
synchronized(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 initiateTransfer(final BankAccount first, final BankAccount second) {
Thread t = new Thread(new Runnable() {
public void run() {
first.depositAllAmount(second);
}
});
t.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.
Objects of this class are deadlock-prone. An attacker may cause the program to construct two threads that initiate balance transfers from two different BankAccount object instances, a and b. Consider the following code that does this:
BankAccount a = new BankAccount(5000); BankAccount b = new BankAccount(6000); initiateTransfer(a, b); // starts thread 1 initiateTransfer(b, a); // starts thread 2
The two transfers are performed in their own threads, 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. When executing depositAllAmount(), the first thread might acquire a lock on object a while the second thread may acquire a lock on object b. Subsequently, the first thread requests a lock on b which is already held by the second thread and the second thread requests a lock on a which is already held by the first thread. This constitutes a deadlock condition, as neither thread can proceed.
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 (single private lock)
The deadlock can be avoided by using a single lock to acquire before doing any account transfers.
class BankAccount {
private int balanceAmount; // Total amount in bank account
private static final Object lock;
private BankAccount(int balance) {
this.balanceAmount = balance;
this.lock = new Object();
}
// Deposits the amount from this object instance to BankAccount instance argument ba
private void depositAllAmount(BankAccount ba) {
synchronized (lock) {
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 void displayAllAmount() {
synchronized (lock) {
System.out.println(balanceAmount);
}
}
public static void initiateTransfer(final BankAccount first, final BankAccount second) {
Thread t = new Thread(new Runnable() {
public void run() {
first.depositAllAmount(second);
}
});
t.start();
}
}
In this scenario, if two threads with two different BankAccount objects try to tranfer to each others' accounts simultaneously, deadlock cannot occur. One thread will acquire the private lock, complete its transfer, and release the lock, before the other thread may proceed.
This solution comes with a performance penalty, as a private static lock restricts the system to only performing one transfer at a time. Two transfers involving four distinct accounts (and distinct target accounts) may not happen concurrently. The impact of this penalty increases considerably as the number of BankAccount objects increase. Consequently this solution does not scale very well.
Compliant Solution (ordered locks)
This compliant solution ensures that multiple locks are acquired and released in the same order. It requires that an ordering over BankAccount objects is available. The ordering is enforced by having the class BankAccount extend the java.lang.Comparable interface and overriding the compareTo() method.
class BankAccount implements Comparable {
private int balanceAmount; // Total amount in bank account
private final Object lock;
private BankAccount(int balance) {
this.balanceAmount = balance;
this.lock = new Object();
}
// Deposits the amount from this object instance to BankAccount instance argument ba
private void depositAllAmount(BankAccount ba) {
BankAccount former, latter;
if (compareTo(ba) < 0) {
former = this;
latter = ba;
} else {
former = ba;
latter = this;
}
synchronized (former) {
synchronized (latter) {
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 initiateTransfer(final BankAccount first, final BankAccount second) {
Thread t = new Thread(new Runnable() {
public void run() {
first.depositAllAmount(second);
}
});
t.start();
}
public int compareTo(BankAccount ba) {
if(this.balanceAmount < ba.balanceAmount) {
return -1;
} else if(this.balanceAmount > ba.balanceAmount) {
return 1;
} else {
return 0;
}
}
}
In this compliant solution, whenever a transfer occurs, the two BankAccount objects are ordered, with the first object's lock being acquired before the second object's lock. Consequently if two threads attempt transfers between the same two accounts, they will both try to acquire the first account's lock first, with the result that one thread will acquire both locks, complete the transfer, and release both locks before the other may proceed.
Unlike the previous compliant solution, this solution incurs no performance penalty, as multiple transfers can occur concurrently as long as the transfers involve distinct target accounts.
Compliant Solution (ReentrantLock)
In this compliant solution, each BankAccount has a java.util.concurrent.locks.ReentrantLock associated with it. This permits the depositAllAmount() method to try acquiring both accounts' locks, but releasing its locks if it fails, and trying again later.
class BankAccount {
private int balanceAmount; // Total amount in bank account
private final Lock lock = new ReentrantLock();
private static final int TIME = 1000; // 1 second
private BankAccount(int balance) {
this.balanceAmount = balance;
}
// Deposits the amount from this object instance to BankAccount instance argument ba
private void depositAllAmount(BankAccount ba) throws InterruptedException {
while (true) {
if (this.lock.tryLock()) {
try {
if (ba.lock.tryLock()) {
try {
ba.balanceAmount += this.balanceAmount;
this.balanceAmount = 0; // withdraw all amount from this instance
ba.displayAllAmount(); // Display the new balanceAmount in ba
break;
} finally {
ba.lock.unlock();
}
}
} finally {
this.lock.unlock();
}
}
Thread.sleep(TIME);
}
}
private void displayAllAmount() throws InterruptedException {
while (true) {
if (lock.tryLock()) {
try {
System.out.println(balanceAmount);
break;
} finally {
lock.unlock();
}
}
Thread.sleep(TIME);
}
}
public static void initiateTransfer(final BankAccount first, final BankAccount second) {
Thread t = new Thread(new Runnable() {
public void run() {
try {
first.depositAllAmount(second);
} catch (InterruptedException e) {
// Forward to handler
}
}
});
t.start();
}
}
Deadlock is impossible in this code, because no method grabs a lock and holds it indefinitely. If a lock is acquired, but the system cannot proceed immediately, it releases the lock and sleeps before requesting the lock again.
Code that uses this lock behaves similar to synchronized code that uses the traditional monitor lock. ReentrantLock provides several other capabilities, for instance, the tryLock() method does not block waiting if another thread is already holding the lock. The class java.util.concurrent.locks.ReentrantReadWriteLock can be used when some thread requires a lock to write information while other threads require the lock to concurrently read the information.
Noncompliant Code Example
This noncompliant code example consists of an application to monitor a sports race. Each racer is asociated with a dedicated object instance of class Racer.
class Racer implements Cloneable {
private double currentSpeed;
private double distance;
public double getCurrentSpeed() {
return currentSpeed;
}
public void setCurrentSpeed(double currentSpeed) {
this.currentSpeed = currentSpeed;
}
public double getDistance() {
return distance;
}
public void setDistance(double distance) {
this.distance = distance;
}
public Racer clone() {
try {
return (Racer) super.clone();
} catch (CloneNotSupportedException x) {
/* handle error */
}
return null;
}
}
Each racer has two statistics that can be reported about them: their current speed, and the current distance traveled. The class Racer provides methods getCurrentSpeed() and getDistance() for this purpose.
The monitoring application is built upon class Race which maintains a list of racers. To be thread-safe, it accepts a list of racers, and defensively clones them. Henceforth, any thread can change a Racer's distance or current speed, or get the average distance or average current speed of all racers. Changing a racer's statistics involves locking using the racer's intrinsic lock, while getting the average statistics for all racers involves locking all the racers' intrinsic locks until the average is calculated.
public class Race {
private final Racer[] racers;
public Race(Racer[] racers) {
this.racers = cloneRacers( 0, racers);
}
// Defensively clone the racers array, but only after all racers are locked
private Racer[] cloneRacers(int i, Racer[] racers) {
if (i > racers.length - 1) {
Racer[] result = new Racer[i];
for (int j = 0; j < this.racers.length; j++) {
result[j] = racers[j].clone();
}
return result;
}
synchronized(racers[i]) {
return cloneRacers( ++i, racers);
}
}
public void setCurrentSpeed(int index, double currentSpeed) {
synchronized( racers[index]) {
racers[index].setCurrentSpeed( currentSpeed);
}
}
public void setDistance(int index, double distance) {
synchronized( racers[index]) {
racers[index].setDistance( distance);
}
}
double getAverageCurrentSpeed() {
return averageCurrentSpeedCalculator(0, 0.0);
}
double averageCurrentSpeedCalculator(int i, double currentSpeed) {
// Acquires locks in increasing order
if (i > racers.length - 1) {
return currentSpeed / racers.length;
}
synchronized(racers[i]) {
currentSpeed += racers[i].getCurrentSpeed();
return averageCurrentSpeedCalculator(++i, currentSpeed);
}
}
double getAverageDistance() {
return averageDistanceCalculator(racers.length - 1, 0.0);
}
double averageDistanceCalculator(int i, double distance) {
// Acquires locks in decreasing order
if (i <= -1) {
return distance / racers.length;
}
synchronized(racers[i]) {
distance += racers[i].getDistance();
return averageDistanceCalculator(--i, distance);
}
}
}
Consequently, the statistics reported by the methods are accurate at the time the methods actually return their results.
This implementation is prone to deadlock because the recursive calls occur within the synchronized regions of these methods and acquire locks in opposite numerical orders. That is, averageCurrentSpeedCalculator() requests locks from index 0 to MAX - 1 (19) whereas averageDistanceCalculator() 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.
For example, if one thread calls getCurrentSpeed(), it acquires the intrinsic lock for Racer 0, the first in the array. Meanwhile if a second thread calls getCurrentDistance(), it acquires the intrinsic lock for Racer 19, the last in the array. Consequently, deadlock results, as neither thread can acquire all of the locks and proceed with the calculation.
Compliant Solution
In this compliant solution, the two calculation methods acquire and release locks in the same order.
public class Race {
double averageCurrentSpeedCalculator(int i, double currentSpeed) {
// Acquires locks in increasing order
if (i > racers.length - 1) {
return currentSpeed / racers.length;
}
synchronized(racers[i]) {
currentSpeed += racers[i].getCurrentSpeed();
return averageCurrentSpeedCalculator(++i, currentSpeed);
}
}
double averageDistanceCalculator(int i, double distance) {
// Acquires locks in increasing order
if (i > racers.length - 1) {
return distance / racers.length;
}
synchronized(racers[i]) {
distance += racers[i].getDistance();
return averageDistanceCalculator(++i, distance);
}
}
}
Consequently, while one thread is calculating the average speed or distance, another thread cannot interfere or induce a deadlock. This is because the other thread would first have to synchronize on racers0, which is impossible until the first calculation is complete.
Noncompliant Code Example
// Immutable Racer
public final class Racer {
private final double currentSpeed;
private final double distanceTraveled;
public Racer(double speed, double distance) {
currentSpeed = speed;
distanceTraveled = distance;
}
public double getCurrentSpeed() {
return currentSpeed;
}
public double getDistance() {
return distanceTraveled;
}
}
public final class Race {
private final Vector<Racer> racers;
private final Object lock = new Object();
public Race(Vector<Racer> racer) {
racers = (Vector<Racer>) racer.clone();
}
public boolean addRacer(Racer racer){
synchronized(racers.elementAt(racers.size() - 1)) {
return racers.add(racer);
}
}
public boolean removeRacer(Racer racer) {
synchronized(racers.elementAt(racers.indexOf(racer))) {
return racers.remove(racer);
}
}
private double getAverageCurrentSpeed(int i, double currentSpeed) {
if (i > racers.size()) {
return currentSpeed / racers.size();
}
synchronized(racers.elementAt(i)) {
currentSpeed += racers.get(i).getCurrentSpeed();
return getAverageCurrentSpeed(++i, currentSpeed);
}
}
private double getAverageCurrentDistance(int i, double distance) {
if (i <= -1) {
return distance / racers.size();
}
synchronized(racers.elementAt(i)) {
distance += racers.get(i).getDistance();
return getAverageCurrentDistance(--i, distance);
}
}
public void getStatisticsAtSomePointInRace() {
synchronized(lock) {
getAverageCurrentSpeed(0, 0.0);
getAverageCurrentDistance(racers.size()-1, 0.0);
}
}
}
Compliant Solution
public final class Race {
private final Vector<Racer> racers;
private final Object lock = new Object();
public Race(Vector<Racer> racer) {
racers = (Vector<Racer>) racer.clone();
}
public boolean addRacer(Racer racer){
return racers.add(racer);
}
public boolean removeRacer(Racer racer) {
synchronized(racers.elementAt(racers.indexOf(racer))) {
return racers.remove(racer);
}
}
private double getAverageCurrentSpeed(int i, double currentSpeed) {
if (i > racers.size()) {
return currentSpeed / racers.size();
}
synchronized(racers.elementAt(i)) {
currentSpeed += racers.get(i).getCurrentSpeed();
return getAverageCurrentSpeed(++i, currentSpeed);
}
}
private double getAverageCurrentDistance(int i, double distance) {
if (i > racers.size()) {
return distance / racers.size();
}
synchronized(racers.elementAt(i)) {
distance += racers.get(i).getDistance();
return getAverageCurrentDistance(++i, distance);
}
}
public void getStatisticsAtSomePointInRace() {
synchronized(lock) {
getAverageCurrentSpeed(0, 0.0);
getAverageCurrentDistance(0, 0.0);
}
}
}
Noncompliant Code Example
public class Book {
private String title;
private double width;
private double weight;
public String getTitle() {
return title;
}
public double getWidth() {
return width;
}
public double getWeight() {
return weight;
}
public Book(String title, double width, double weight) {
this.title = title;
this.width = width;
this.weight = weight;
}
}
public class Bookshelf {
private final Vector<Book> books = new Vector<Book>();
public boolean addBook(Book book) {
// lock on last element to prevent race cond with calculation methods
synchronized(books.lastElement()) {
return books.add(new Book( book.getTitle(), book.getWidth(), book.getWeight()));
}
}
// only one remove can happen at a time
public final synchronized boolean removeBook(String title) {
for (int i = 0; i < books.size(); i++) {
if (books.getTitle().equals( title)) {
// lock on book to prevent race cond with calculation routines
synchronized (books.elementAt(i)) {
return books.remove( i);
}
}
}
return false; // book not on bookshelf
}
private double getTotalWidth(int i, double width) {
if (i > books.size()) {
return width;
}
synchronized (books.elementAt(i)) {
numberOfPages += books.get(i).getWidth();
return getTotalWidth(++i, width);
}
}
private double getTotalWeight(int i, double weight) {
if (i <= -1) {
return weight;
}
synchronized (books.elementAt(i)) {
weight += books.get(i).getWeight();
return getTotalWeight(--i, weight);
}
}
}
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 |
P3 |
L3 |
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"
CON11-J. Do not assume that declaring an object volatile guarantees visibility of its members 11. Concurrency (CON) CON13-J. Do not try to force thread shutdown