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|AA. Java References#JLS 05]\]. Deadlocks can arise when two or more threads request and release locks in different orders.
h2. 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()}}.
{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 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);
}
}
{code}
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.
This object can easily yield to deadlock. Consider if the following function were invoked:
{code:bgColor=#FFcccc}
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();
}
{code}
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}}. As a result, the first thread might acquire a lock on the {{a}} object, while trying to acquire a lock on the {{b}} object. Meanwhile the second thread acquires a lock on the {{b}} object, while trying to acquire a lock on the {{a}} object. This constitutes a deadlock condition, as neither thread may 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.
h2. Compliant Solution (single private lock)
The deadlock can be avoided by using a single lock to acquire before doing any account transfers.
{code:bgColor=#ccccff}
class BankAccount {
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) {
public static void initiateTransfer(final BankAccount first, final BankAccount second) {
Thread t = new Thread(new Runnable() {
public void run() {
first.depositAllAmount(second);
}
});
t.start();
}
}
{code}
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:
{code}
BankAccount a = new BankAccount(5000);
BankAccount b = new BankAccount(6000);
initiateTransfer(a, b); // starts thread 1
initiateTransfer(b, a); // starts thread 2
{code}
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.
h2. Compliant Solution (single private lock)
The deadlock can be avoided by using a single lock to acquire before doing any account transfers.
{code:bgColor=#ccccff}
class BankAccount {
private static 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) {
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) {
ba.balanceAmount += this.balanceAmountSystem.out.println(balanceAmount);
}
this.balanceAmount = 0; // withdraw all amount from this instance}
public static void initiateTransfer(final BankAccount first, final BankAccount second) {
Thread ba.displayAllAmountt = new Thread(new Runnable(); {
// Display the new balanceAmount inpublic bavoid run(may cause deadlock)
} {
}
private void displayAllAmountfirst.depositAllAmount(second) {;
synchronized (lock) {}
System.out.println(balanceAmount});
}t.start();
}
}
{code}
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 iscomes accompanied 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 may not happen simultaneously. The impact of this penalty increases considerably as the number of {{BankAccount}} objects increase. Consequently this solution may be infeasible for performance reasons.
h2. Compliant Solution (ordered locks)
A second way of avoiding deadlock is to ensure that multiple locks are acquired and released in the same order. This solution requires that an ordering over {{BankAccount}} objects is available. The ordering is implied by having the {{bankAccount}} extend the {{Comparable}} interface.
{code:bgColor=#ccccff}
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 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.
h2. 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.
{code:bgColor=#ccccff}
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 ba.balanceAmount += this.balanceAmount;void run() {
this.balanceAmount = 0; // withdraw all amount from this instancefirst.depositAllAmount(second);
}
});
bat.displayAllAmountstart();
// Display}
the newpublic balanceAmountint incompareTo(BankAccount ba (may cause deadlock)) {
if(this.balanceAmount < } ba.balanceAmount) {
}
return }-1;
private synchronized void displayAllAmount(} else if(this.balanceAmount > ba.balanceAmount) {
System.out.println(balanceAmount)return 1;
} else {
public int compareTo(Object o)return {0;
// ...}
}
}
{code}
In this scenariocompliant solution, whenever a transfer must occuroccurs, 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 consequenceresult that one thread will acquire both locks, complete the transfer, and release both locks before the other may proceed.
Unlike the previous Compliantcompliant Solutionsolution, this solution suffersincurs no performance penalty, as multiple transfers can occur simultaneously providedconcurrently as long as the transfers involve fourdistinct distincttarget accounts.
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 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.
{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 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);
}
}
}
{code}
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:
{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 {{averageSpeedCalculator()}} and {{averageTimeCalculator()}} methods to outside the {{synchronized}} block.
{code:bgColor=#ccccff}
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
}
}
{code}
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.
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]
\[[Halloway 00|AA. Java References#Halloway 00]\]
\[[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] [!The CERT Sun Microsystems Secure Coding Standard for Java^button_arrow_up.png!|11. Concurrency (CON)] [!The CERT Sun Microsystems Secure Coding Standard for Java^button_arrow_right.png!|CON13-J. Do not try to force thread shutdown]
|
