breakingInvariant

Malicious Race Conditions and Data Races

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.

 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 a starting point. A race condition can break the invariance of a program.

Breaking of invariants

In the last post Race Conditions and Data Races, I use money transfer between two accounts to show a data race. There was a benign race condition involved. 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 in our case is 200 because each account starts with 100 (1). For simplicity reasons, the unit should be euro. Neither I want to create money by transferring it, nor do 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;

}

 

 

Rainer D 6 P2 500x500Modernes C++ Mentoring

Be part of my mentoring programs:

  • "Fundamentals for C++ Professionals" (open)
  • "Design Patterns and Architectural Patterns with C++" (open)
  • "C++20: Get the Details" (open)
  • "Concurrency with Modern C++" (starts March 2024)
  • Do you want to stay informed: Subscribe.

     

    In the beginning, the sum of the accounts is 200 euros. (4) display the sum using printSum (3). Line (5) makes the invariant visible. Because there is a short sleep of 1ns in line (2), the intermediate sum is 182 euros. In the end, all is fine. Each account has the right balance (6), and the sum is 200 euros (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 its notification before the waiting thread is in the waiting state. Therefore, the waiting thread waits forever. That phenomenon is called a lost wake-up.

    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 generally depends on the interleaving of the threads, and may 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 emphasize it very explicitly. All the programs in this post are up to this point without a data race. You know it was my idea to write about race conditions and data races. They are related but different concepts.

    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 simultaneously. At least one 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 add 50 euros (3) to the same account (1). They use the function addMoney. The critical observation is that the writing to the account is done without synchronization. Therefore we have a data race and no valid result. That is undefined behavior and the final balance (4) differs between 5000 and 5100 euros.

     

    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.

     

     

    Thanks a lot to my Patreon Supporters: Matt Braun, Roman Postanciuc, Tobias Zindl, G Prvulovic, Reinhold Dröge, Abernitzke, Frank Grimm, Sakib, Broeserl, António Pina, Sergey Agafyin, Андрей Бурмистров, Jake, GS, Lawton Shoemake, Jozo Leko, John Breland, Venkat Nandam, Jose Francisco, Douglas Tinkham, Kuchlong Kuchlong, Robert Blanch, Truels Wissneth, Kris Kafka, Mario Luoni, Friedrich Huber, lennonli, Pramod Tikare Muralidhara, Peter Ware, Daniel Hufschläger, Alessandro Pezzato, Bob Perry, Satish Vangipuram, Andi Ireland, Richard Ohnemus, Michael Dunsky, Leo Goodstadt, John Wiederhirn, Yacob Cohen-Arazi, Florian Tischler, Robin Furness, Michael Young, Holger Detering, Bernd Mühlhaus, Stephen Kelley, Kyle Dean, Tusar Palauri, Dmitry Farberov, Juan Dent, George Liao, Daniel Ceperley, Jon T Hess, Stephen Totten, Wolfgang Fütterer, Matthias Grün, Phillip Diekmann, Ben Atakora, Ann Shatoff, Rob North, Bhavith C Achar, Marco Parri Empoli, moon, Philipp Lenk, Hobsbawm, and Charles-Jianye Chen.

    Thanks, in particular, to Jon Hess, Lakshman, Christian Wittenhorst, Sherhy Pyton, Dendi Suhubdy, Sudhakar Belagurusamy, Richard Sargeant, Rusty Fleming, John Nebel, Mipko, Alicja Kaminska, Slavko Radman, and David Poole.

    My special thanks to Embarcadero
    My special thanks to PVS-Studio
    My special thanks to Tipi.build 
    My special thanks to Take Up Code
    My special thanks to SHAVEDYAKS

    Seminars

    I’m happy to give online seminars or face-to-face seminars worldwide. Please call me if you have any questions.

    Standard Seminars (English/German)

    Here is a compilation of my standard seminars. These seminars are only meant to give you a first orientation.

    • C++ – The Core Language
    • C++ – The Standard Library
    • C++ – Compact
    • C++11 and C++14
    • Concurrency with Modern C++
    • Design Pattern and Architectural Pattern with C++
    • Embedded Programming with Modern C++
    • Generic Programming (Templates) with C++
    • Clean Code with Modern C++
    • C++20

    Online Seminars (German)

    Contact Me

    Modernes C++ Mentoring,

     

     

    0 replies

    Leave a Reply

    Want to join the discussion?
    Feel free to contribute!

    Leave a Reply

    Your email address will not be published. Required fields are marked *