Malicious Race Conditions and Data Races

Contents[Show]

This post is about malicious race conditions and data races. Malicious race conditions are race conditions that cause the breaking of invariants, blocking issues of threads, or lifetime issues of variables.

 At first, let me remind you, what a race condition is. 

  • Race condition: A race condition is a situation, in which the result of an operation depends on the interleaving of certain individual operations.

That's fine as starting point. A race condition can break the invariant of a program.

Breaking of invariants

In the last post Race Conditions and Data Races, I use the transfer of money between two accounts to show a data race. There was a benign race condition involved. To be honest, there was also a malicious race condition.

The malicious race condition breaks an invariant of the program. The invariant is, that the sum of all balances should always have the same amount. Which is in our case is 200 because each account starts with 100 (1). For simplicity reason, the unit should be euro. Neither I want to create money by transferring it nor I want to destroy it.

// breakingInvariant.cpp

#include <atomic>
#include <functional>
#include <iostream>
#include <thread>

struct Account{
  std::atomic<int> balance{100};                               // 1
};
                                                              
void transferMoney(int amount, Account& from, Account& to){
  using namespace std::chrono_literals;
  if (from.balance >= amount){
    from.balance -= amount;  
    std::this_thread::sleep_for(1ns);                           // 2
    to.balance += amount;
  }
}

 void printSum(Account& a1, Account& a2){
  std::cout << (a1.balance + a2.balance) << std::endl;         // 3
}

int main(){
  
  std::cout << std::endl;

  Account acc1;
  Account acc2;
  
  std::cout << "Initial sum: ";                          
  printSum(acc1, acc2);                                        // 4
  
  std::thread thr1(transferMoney, 5, std::ref(acc1), std::ref(acc2));
  std::thread thr2(transferMoney, 13, std::ref(acc2), std::ref(acc1));
  std::cout << "Intermediate sum: ";                
  std::thread thr3(printSum, std::ref(acc1), std::ref(acc2));  // 5
  
  thr1.join();
  thr2.join();
  thr3.join();
                                                               // 6
  std::cout << "     acc1.balance: " << acc1.balance << std::endl;
  std::cout << "     acc2.balance: " << acc2.balance << std::endl;
  
  std::cout << "Final sum: ";
  printSum(acc1, acc2);                                        // 8
  
  std::cout << std::endl;

}

 

At the begin, the sum of the accounts is 200 euro. (4) display the sum by using the function printSum (3). Line (5) makes the invariant visible. Because there is a short sleep of 1ns in line (2), the intermediate sum is 182 euro. At the end, all is fine. Each account has the right balance (6) and the sum is 200 euro (8).

Here is the output of the program.

breakingInvariant

The malicious story goes on. Let's create a deadlock by using conditions variables without a predicate.

Blocking issues with race conditions

Only to make my point clear. You have to use a condition variable in combination with a predicate. For the details read my post Condition Variables. If not, your program may become the victim of a spurious wakeup or lost wakeup.

If you use a condition variable without a predicate, it may happen that the notifying thread sends it notification before the waiting thread is in the waiting state. Therefore, the waiting thread waits forever. That phenomenon is called a lost wakeup.

Here is the program.

// conditionVariableBlock.cpp

#include <iostream>
#include <condition_variable>
#include <mutex>
#include <thread>

std::mutex mutex_;
std::condition_variable condVar;

bool dataReady;


void waitingForWork(){

    std::cout << "Worker: Waiting for work." << std::endl;

    std::unique_lock<std::mutex> lck(mutex_);
    condVar.wait(lck);                           // 3
    // do the work
    std::cout << "Work done." << std::endl;

}

void setDataReady(){

    std::cout << "Sender: Data is ready."  << std::endl;
    condVar.notify_one();                        // 1

}

int main(){

  std::cout << std::endl;

  std::thread t1(setDataReady);
  std::thread t2(waitingForWork);                // 2

  t1.join();
  t2.join();

  std::cout << std::endl;
  
}

 

The first invocations of the program work fine. The second invocation locks because the notify call (1) happens before the thread t2 (2) is in the waiting state (3).

 

conditionVariableBlock

Of course, deadlocks and livelocks are other effects of race conditions. A deadlock depends in general on the interleaving of the threads and my sometimes happen or not. A livelock is similar to a deadlock. While a deadlock blocks, I livelock seems to make progress. The emphasis lies on seems. Think about a transaction in a transactional memory use case. Each time the transaction should be committed, a conflict happens. Therefore a rollback takes place. Here is my post about Transactional Memory.

Showing lifetime issues of variables is not so challenging.

Lifetime issues of variables

The recipe of a lifetime issue is quite simple. Let the created thread run in the background and you are half done. That means the creator thread will not wait until its child is done. In this case, you have to be extremely careful that the child is not using something belonging to the creator.

 

// lifetimeIssues.cpp

#include <iostream>
#include <string>
#include <thread>

int main(){
    
  std::cout << "Begin:" << std::endl;            // 2    

  std::string mess{"Child thread"};

  std::thread t([&mess]{ std::cout << mess << std::endl;});
  t.detach();                                    // 1
  
  std::cout << "End:" << std::endl;              // 3

}

 

This is too simple. The thread t is using std::cout and the variable mess. Both belong to the main thread. The effect is that we don't see the output of the child thread in the second run. Only "Begin:" (2) and "End:" (3) are displayed. 

lifetimeIssues2

I want to emphasise it very explicitly. All the programs in this post are up to this point without a data race. You know is was my idea to write about race conditions and data races. They are a related, but different concept.

I can even create a data race without a race condition.

A data race without a race condition

But first, let me remind you, what a data race is.

  • Data race: A data race is a situation, in which at least two threads access a shared variable at the same time. At least on thread tries to modify the variable.

 

// addMoney.cpp

#include <functional>
#include <iostream>
#include <thread>
#include <vector>

struct Account{
  int balance{100};                              // 1
};

void addMoney(Account& to, int amount){
  to.balance += amount;                          // 2
}

int main(){
  
  std::cout << std::endl;

  Account account;
  
  std::vector<std::thread> vecThreads(100);
  
                                                 // 3
  for (auto& thr: vecThreads) thr = std::thread( addMoney, std::ref(account), 50);
  
  for (auto& thr: vecThreads) thr.join();
  
                                                 // 4
  std::cout << "account.balance: " << account.balance << std::endl;
  
  std::cout << std::endl;

}

 

100 threads are adding 50 euro (3) to the same account (1). They use the function addMoney. The key observation is, that the writing to the account is done without synchronisation. Therefore we have a data race and no valid result. That is undefined behaviour and the final balance (4) differs between 5000 and 5100 euro.

 

addMoney

What's next?

I often hear at concurrency conference discussions about the terms non-blocking, lock-free, and wait-free. So let me write about these terms in my next post.

Add comment


My Newest E-Books

Latest comments

Subscribe to the newsletter (+ pdf bundle)

Blog archive

Source Code

Visitors

Today 1576

All 539297

Currently are 192 guests and no members online