Page History

Mutexes are used to prevent multiple threads from causing a data race by accessing shared resources at the same time. Sometimes, when locking mutexes, multiple threads hold each other's lock, and the program consequently deadlocks. Four conditions are required for deadlock to occur:

• Mutual exclusion
• Hold and wait
• No preemption
• Circular wait

Deadlock needs all four conditions, so preventing deadlock requires preventing any one of the four conditions. One simple solution is to lock the mutexes in a predefined order, which prevents circular wait.

Noncompliant Code Example

The behavior of this noncompliant code example depends on the runtime environment and the platform's scheduler. The program is susceptible to deadlock if thread thr1 attempts to lock ba2's mutex at the same time thread thr2 attempts to lock ba1's mutex in the deposit() function

Introduction

Whenever threads come into play, there are bounded to be shared memory or resources that each thread wants to access. But because of the random nature of execution of each thread, there will be corruption of data when multiple threads try to read and write into the same memory space. One possible way to fix the problem is using locking mechanism like a mutex. POSIX provides a mutex called pthread_mutex_t just for this purpose. See POS00-C Avoid race conditions with multiple threads for more information.

Deadlock can happen when multiple threads each holds a lock the other needs and are waiting for each other to release that resource. One way to fix the problem is to avoid circular wait by locking the mutex in a predefined order.

Noncompliant Code Example

Based on runtime environment and the scheduler on the operating system, the following code will have different behaviors. Let's assume function thread1 and thread2 are called consecutively as in pthread_create is called for thread2 right after pthread_create is called for thread1. If lucky, the code will run without any problems. In other times, the code will deadlock in which thread1 try to lock m1 while thread2 try to lock on m2 and the program will not progress.

#include <stdlib.h>
#include <pthread.h>

void *thread1(void *ptr);
void *thread2(void *ptr);

pthread_mutex_t m1 = PTHREAD_MUTEX_INITIALIZER;
pthread_mutex_t m2 = PTHREAD_MUTEX_INITIALIZER;

void *thread1<threads.h>
 
typedef struct {
  int balance;
  mtx_t balance_mutex;
} bank_account;

typedef struct {
  bank_account *from;
  bank_account *to;
  int amount;
} transaction;

void create_bank_account(bank_account **ba,
                         int initial_amount) {
  bank_account *nba = (bank_account *)malloc(
    sizeof(bank_account)
  );
  if (nba == NULL) {
    /* Handle error */
  }

  nba->balance = initial_amount;
  if (thrd_success
      != mtx_init(&nba->balance_mutex, mtx_plain)) {
    /* Handle error */
  }

  *ba = nba;
}

int deposit(void *ptr) {
  transaction *args = (transaction *)ptr;

  pthread_mutexif (thrd_success != mtx_lock(&m1);args->from->balance_mutex)) {
    /* Handle error */
  }

 do some/* stuffNot thatenough requirebalance lockingto mutex1transfer */
  if (args->from->balance < args->amount) {
    pthread_mutex_lock(&m2);
  /* do some stuff that require locking mutex2 */

  pthread_mutex_unlock(&m2);
  pthread_mutex_unlock(&m1);

  return NULL;
}

void *thread2(void *ptr) {

  pthread_mutex_lock(&m2);
  /* do some stuff that require locking mutex2 */

  pthread_mutex_lock(&m1);
  /* do some stuff that require locking mutex1 */

  pthread_mutex_unlock(&m1);
  pthread_mutex_unlock(&m2);

  return NULL;
}

Compliant Solution

The solution to the deadlock problem is to lock in predefined order. In the following example, each thread will lock m1 first then m2. This way circular wait problem is avoided and when one thread requires a lock will guarantee it will require the next lock.

#include <pthread.h>

void *thread1(void *ptr);
void *thread2(void *ptr);

pthread_mutex_t m1 = PTHREAD_MUTEX_INITIALIZER;
pthread_mutex_t m2 = PTHREAD_MUTEX_INITIALIZER;

void *thread1(void *ptr) {

  pthread_mutex_lock(&m1);
  pthread_mutex_lock(&m2);

  /* do some stuff that require locking mutex1 */
  /* do some stuff that require locking mutex2 */

  pthread_mutex_unlock(&m2);
  pthread_mutex_unlock(&m1);

  return NULL;
}

void *thread2(void *ptr) {

  pthread_mutex_lock(&m1);
  pthread_mutex_lock(&m2);
  /* do some stuff that require locking mutex1 */
  /* do some stuff that require locking mutex2 */

  pthread_mutex_unlock(&m1);
  pthread_mutex_unlock(&m2);

  return NULL;
}

Risk Assessment

Deadlock causes multiple threads to not be able to progress and thus halt the executing program. This is a potential denial-of-service attack when the attacker can force deadlock situations. It's probable that deadlock will occur in multi-thread programs that manage multiple resources. Some automation for detecting deadlock can be implemented in which the detector can try different inputs and wait for a timeout. The fixes can be done automatically using some graph algorithm like Dijkstra, but most like be manual.

if (thrd_success
        != mtx_unlock(&args->from->balance_mutex)) {
      /* Handle error */
    }
    return -1; /* Indicate error */
  }
  if (thrd_success != mtx_lock(&args->to->balance_mutex)) {
    /* Handle error */
  }

  args->from->balance -= args->amount;
  args->to->balance += args->amount;

  if (thrd_success
      != mtx_unlock(&args->from->balance_mutex)) {
    /* Handle error */
  }

  if (thrd_success
      != mtx_unlock(&args->to->balance_mutex)) {
    /* Handle error */
  }

  free(ptr);
  return 0;
}

int main(void) {
  thrd_t thr1, thr2;
  transaction *arg1;
  transaction *arg2;
  bank_account *ba1;
  bank_account *ba2;

  create_bank_account(&ba1, 1000);
  create_bank_account(&ba2, 1000);

  arg1 = (transaction *)malloc(sizeof(transaction));
  if (arg1 == NULL) {
    /* Handle error */
  }
  arg2 = (transaction *)malloc(sizeof(transaction));
  if (arg2 == NULL) {
    /* Handle error */
  }
  arg1->from = ba1;
  arg1->to = ba2;
  arg1->amount = 100;

  arg2->from = ba2;
  arg2->to = ba1;
  arg2->amount = 100;

  /* Perform the deposits */
  if (thrd_success
     != thrd_create(&thr1, deposit, (void *)arg1)) {
    /* Handle error */
  }
  if (thrd_success
      != thrd_create(&thr2, deposit, (void *)arg2)) {
    /* Handle error */
  }
  return 0;
} 

Compliant Solution

This compliant solution eliminates the circular wait condition by establishing a predefined order for locking in the deposit() function. Each thread will lock on the basis of the bank_account ID, which is set when the bank_account struct is initialized.

#include <stdlib.h>
#include <threads.h>
 
typedef struct {
  int balance;
  mtx_t balance_mutex;
 
  /* Should not change after initialization */
  unsigned int id;
} bank_account;

typedef struct {
  bank_account *from;
  bank_account *to;
  int amount;
} transaction;

unsigned int global_id = 1;

void create_bank_account(bank_account **ba,
                         int initial_amount) {
  bank_account *nba = (bank_account *)malloc(
    sizeof(bank_account)
  );
  if (nba == NULL) {
    /* Handle error */
  }

  nba->balance = initial_amount;
  if (thrd_success
      != mtx_init(&nba->balance_mutex, mtx_plain)) {
    /* Handle error */
  }

  nba->id = global_id++;
  *ba = nba;
}

int deposit(void *ptr) {
  transaction *args = (transaction *)ptr;
  int result = -1;
  mtx_t *first;
  mtx_t *second;

  if (args->from->id == args->to->id) {
    return -1; /* Indicate error */
  }

  /* Ensure proper ordering for locking */
  if (args->from->id < args->to->id) {
    first = &args->from->balance_mutex;
    second = &args->to->balance_mutex;
  } else {
    first = &args->to->balance_mutex;
    second = &args->from->balance_mutex;
  }
  if (thrd_success != mtx_lock(first)) {
    /* Handle error */
  }
  if (thrd_success != mtx_lock(second)) {
    /* Handle error */
  }

  /* Not enough balance to transfer */
  if (args->from->balance >= args->amount) {
    args->from->balance -= args->amount;
    args->to->balance += args->amount;
    result = 0;
  }

  if (thrd_success != mtx_unlock(second)) {
    /* Handle error */
  }
  if (thrd_success != mtx_unlock(first)) {
    /* Handle error */
  }
  free(ptr);
  return result;
} 

Risk Assessment

Deadlock prevents multiple threads from progressing, halting program execution. A denial-of-service attack is possible if the attacker can create the conditions for deadlock.

References

pthread_mutex pthread_mutex tutorial
MITRE CWE:764 Multiple Locks of Critical Resources
Bryant 03 Chapter 13, Concurrent Programming

Other Languages

Related Vulnerabilities

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

Automated Detection

Related Guidelines

Key here (explains table format and definitions)

...

...

Image Added Image Added Image Added