To avoid data corruption in multithreaded Java programs, shared data must be protected from concurrent modifications and accesses. This can be done at the object level by using synchronized blocks (coarse-grained locking), as a result locking out other threads from interfering. If synchronization is used judiciously, deadlocks do not usually crop up (See CON08-J. Do not call alien methods or constructors that synchronize on the same object as the calling class).
When a fine-grained locking approach is employed by using member locks, deadlocks can still arise unless it is ensured that each thread always requests locks in the same numeric order.
Noncompliant Code Example
This noncompliant code example shows a subtle deadlock issue that manifests itself when synchronization is implemented incorrectly. Assume that an attacker has two bank accounts and is capable of requesting two amount deposit operations in succession. This corresponds to two threads as shown in main(). Objects a and b are constructed such that the amount will be transferred from a to b by first depositing the amount from a to b and then zeroing out a (and vice-versa during the call to b.deposit()).
class BadLocks {
private int balance; // Total amount
private BadLocks(int balance) {
this.balance = balance;
}
private synchronized void withdraw() {
System.out.println("Withdrawing amount...");
this.balance = 0;
}
private synchronized void deposit(BadLocks bl) {
System.out.println("Depositing amount...");
bl.balance += this.balance;
bl.withdraw();
}
public static void main(String[] args) throws Exception {
final BadLocks a = new BadLocks(5000);
final BadLocks b = new BadLocks(6000);
// These two threads correspond to two malicious requests triggered by the attacker
Thread t1 = new Thread(new Runnable() {
public void run() {
a.deposit(b);
}
});
Thread t2 = new Thread(new Runnable() {
public void run() {
b.deposit(a);
}
});
t1.start();
t2.start();
}
}
Both the threads invoke the synchronized deposit method on objects a and b respectively and there is no interleaving of locks. However, the deposit method is designed to request a lock on object a for the first thread and object b for the second. If both threads acquire separate locks in different orders, for instance, if the call to withdraw() in one thread requests an already held lock in the other thread, a deadlock situation arises. If Thread 1 finishes executing before Thread 2, there would not be any issues. Sequences where the threads alternate, such as, T1, T2, T1, T2 can result in a deadlock (In Tx, 'x' denotes Thread number).
Compliant Solution (1) (acquire locks in proper order)
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. This can be achieved by invoking the withdraw() method without qualifying it with the bl parameter. This allows the withdraw() method of the current thread to be called.
private synchronized void deposit(BadLocks bl) {
System.out.println("Depositing amount...");
bl.balance += this.balance;
withdraw(); // Call same instance's withdraw() method
}
Compliant Solution (2) (avoid synchronization)
The deadlock can also be avoided by declaring the balance field as volatile and removing the synchronized keyword from the withdraw() method.
private volatile int balance; // Total amount
//...
private void withdraw(BadLocks bl) {
System.out.println("Withdrawing amount...");
this.balance = 0;
}
The withdraw() method does not require additional synchronization because it atomically makes the balance zero.
Noncompliant Code Example
In this noncompliant code example, a deadlock occurs if the transfer() method acquires the locks in decreasing numeric order, while the sumHelper() method uses an increasing numeric order to acquire its locks.
class Stocks implements FundConstants {
static int[] balances = new int[noOfStocks];
static Object[] locks = new Object[noOfStocks];
static {
for (int n = 0; n < noOfStocks; n++) {
balances[n] = 10000;
locks[n] = new Object();
}
}
static void transfer(Transfer t) {
int lo, hi;
if (t.fundFrom > t.fundTo) { // Acquires the locks in decreasing numeric order
lo = t.fundFrom;
hi = t.fundTo;
} else {
lo = t.fundTo;
hi = t.fundFrom;
}
synchronized (locks[lo]) {
synchronized (locks[hi]) {
balances[t.fundFrom] -= t.amount;
balances[t.fundTo] += t.amount;
}
}
}
static int sumHelper(int next) {
synchronized (locks[next]) { // Acquires the locks in increasing numeric order
if (next == (noOfStocks - 1)) {
return balances[next];
} else {
return balances[next] + sumHelper(next + 1); // Increasing numeric order
}
}
}
static void checkSystem() {
int actual = 0;
actual = sumHelper(0);
System.out.println("The actual balance is " + actual);
}
}
Compliant Solution
To implement a fine-grained locking strategy, request a separate lock for each position in the balances array. As it is not possible to lock on primitive types, a direct lock on the items in the balances array cannot be obtained. Instead, an array of raw Objects (locks) can be used.
This compliant solution avoids deadlocks because every thread requests the locks in the same order and as a result, the locks are acquired (and released) correctly.
class Stocks implements FundConstants {
static int[] balances = new int[noOfStocks];
static Object[] locks = new Object[noOfStocks];
static {
for (int n = 0; n < noOfStocks; n++) {
balances[n] = 10000;
locks[n] = new Object();
}
}
static void transfer(Transfer t) {
int lo, hi;
if (t.fundFrom < t.fundTo) { // Acquires the locks in increasing numeric order
lo = t.fundFrom;
hi = t.fundTo;
} else {
lo = t.fundTo;
hi = t.fundFrom;
}
synchronized (locks[lo]) {
synchronized (locks[hi]) {
balances[t.fundFrom] -= t.amount;
balances[t.fundTo] += t.amount;
}
}
}
static int sumHelper (int next) {
synchronized (locks[next]) { // Acquires the locks in increasing numeric order
if (next == (noOfStocks - 1)) {
return balances[next];
} else {
return balances[next] + sumHelper(next + 1); // Increasing numeric order
}
}
}
static void checkSystem() {
int actual = 0;
actual = sumHelper(0);
System.out.println("The actual balance is " + actual);
}
}
Risk Assessment
Fine-grained locking may result in deadlocks if some thread does not always request locks in the same order as others.
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
[[SDN 08]] Sun Developer Network Tech tips
[[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