RACE CONDITIONS

(1)

SECURE PROGRAMMING

A.A. 2018/2019

(2)

RACE CONDITIONS

(3)

System, Social and Mobile Security

RACE CONDITIONS

Uncontrolled concurrency can lead to nondeterministic behavior (that is, a program can exhibit different behavior for the same set of inputs).

A race condition occurs in any scenario in which two threads can produce different behavior, depending on which thread completes first.

(4)

RACE CONDITIONS

Race conditions can result from trusted or untrusted control flows.

Trusted control flows include tightly coupled threads of execution that are part of the same program.

An untrusted control flow is a separate application or process, often of unknown origin, that executes

concurrently.

Any system that supports multitasking with shared resources has the potential for race conditions from untrusted control flows.

(5)

PROPERTIES

Three properties are necessary for a race condition to exist:

1. Concurrency property: At least two control flows must be executing concurrently.

2. Shared object property: A shared race object must be accessed by both of the concurrent flows.

3. Change state property: At least one of the control flows must alter the state of the race object.

(6)

OS

Race conditions are a software defect and are a frequent source of vulnerabilities. Race conditions are particularly insidious because they are timing dependent and

manifest sporadically.

üAs a result, they are difficult to detect, reproduce, and

eliminate and can cause errors such as data corruption or crashes.

Race conditions result from runtime environments,

including operating systems that must control access to shared resources, especially through process

scheduling. It is the programmer’s responsibility to ensure that his or her code is properly sequenced regardless of how runtime environments schedule execution

(7)

ELIMINATING THEM

Eliminating race conditions begins with identifying race windows.

A race window is a code segment that accesses the race object in a way that opens a window of opportunity

during which other concurrent flows could “race in” and alter the race object.

Furthermore, a race window is not protected by a lock or any other mechanism.

A race window protected by a lock or by a lock-free mechanism is called a critical section.

(8)

EXAMPLE

(9)

EXAMPLE CORRUPTED VALUES

(10)

RACE CONDITIONS ON FILES

File access sequences where a file is opened, read from or written to, closed, and perhaps reopened by separate functions called over a period of time are fertile regions for race windows.

Open files are shared by peer threads, and file systems can be manipulated by independent processes.

Files and directories commonly act as race objects.

(11)

EXAMPLE

The race window is between lines 4 and 6.

An exploit consists of the following shell command, if executed during this race window:

mv /tmp/a/b/c /tmp/c

(12)

TIME OF CHECK, TIME OF USE

TOCTOU race conditions can occur during file I/O.

üTOCTOU race conditions form a race window by first testing (checking) some race object property and then later

accessing (using) the race object.

rm a_file

ln –s /etc/shadow a_file

race

(13)

TEST AND CREATION TOGETHER

(14)

SOLUTION

One solution using the open() function is to use the O_CREAT and

O_EXCL flags. When used together, these flags instruct the open() function to fail if the file specified by file_name already exists

(15)

SYNCHRONIZATION PRIMITIVES

To prevent data races, any two actions that act on the same object must use synchronization primitives.

C and C++ support several different kinds of

synchronization primitives, including mutex variables, condition variables, and lock variables.

Acquiring a synchronization object before a race window and then releasing it after the window ends makes the race window atomic with respect to other code using the same synchronization mechanism.

All critical sections appear atomic to all appropriately synchronized threads other than the thread performing the critical section.

(16)

REORDERING

Assembly instructions can be rearranged by the

üProcessor during execution üCompiler during optimization

(17)

EXAMPLE

(18)

RACE CONDITION ON THE MUTEX

NO

(19)

MUTEX VARIABLE IN C++

(20)

MUTEX IN C11

C mutex support is semantically identical to C++ mutex support, but with different syntax because C lacks

classes and templates. The C standard library provides the mtx_lock(), mtx_unlock(), mtx_trylock(), and

mtx_timedlock() functions to lock and unlock mutexes. It also provides mtx_init() and mtx_destroy() to create and destroy mutexes.

The signature of the mtx_init() function is int mtx_init(mtx_t *mtx, int type);

p_thread (pthread.h instead of thread.h) are POSIX implementation of threads

(21)

LOCK VARIABLES

A lock guard is a standard object that assumes

responsibility for a mutex (actually, for any lock object).

When a lock guard is constructed over a mutex, it

attempts to lock the mutex; it unlocks the mutex when the lock guard is itself destroyed.

(22)

ATOMIC OBJECTS

An atomic object is any object that guarantees that all actions performed on it are atomic.

By imposing atomicity on all operations over an object, an atomic object cannot be corrupted by simultaneous reads or writes. No data races.

(23)

SEMAPHORES

A semaphore is similar to a mutex, except that a

semaphore also maintains a counter whose value is declared upon initialization.

Consequently, semaphores are decremented and incremented rather than locked and unlocked.

When a semaphore’s counter reaches 0, subsequent

attempts to decrement the semaphore will block until the counter is incremented.

üIt can be used to control the number of threads üIn C, semaphore.h (POSIX)

üNo object oriented version of them in C++, you can use the C version wrapped in an object or use the Boost library

(https://www.boost.org)

(24)

MEMORY FENCING

Both can be set to 0!

Either one of the two can be set to 0

(25)

FILE LOCKS

No memory is shared!

(26)

MITIGATION PITFALLS

Not using the lock when accessing shared data when the lock does exist

Prematurely releasing a lock Deadlock caused by

üImproper use or selection of locking mechanisms

üNot releasing a lock or trying to reacquire a lock that is already held

Lack of fairness Starvation

Livelock

Assuming threads run in a particular order, NOT run

simultaneously, run simultaneously, make progress before one thread ends

(27)

RACE DETECTION TOOLS (STATIC)

A static analysis tool analyzes software for race conditions without actually executing the software.

Race condition detection has been shown to be an NP- complete problem.

üTherefore, static race detection tools provide an approximate identification

üAs a result, all static analysis algorithms are prone to some false negatives and false positives.

Clang thread Safety Analysis (Google)

ühttps://clang.llvm.org/docs/ThreadSafetyAnalysis.html üclang -c -Wthread-safety example.cpp

(28)

RACE DETECTION (DYNAMIC)

Dynamic race detection tools overcome some of the problems with static tools by integrating detection with the actual

program’s execution.

üLess false positives.

But, the disadvantages of dynamic detection are a

üdynamic tool fails to consider execution paths not taken, and üthere is often a runtime overhead associated with dynamic

detection.

Intel Inspector (commercial)

ühttps://software.intel.com/en-us/intel-inspector-xe

Helgrind (part of Valgrind)

ühttp://valgrind.org/docs/manual/hg-manual.html#hg-manual.data- races.example

(29)

EXAMPLE FROM HELGRIND

#include <pthread.h>

int var = 0;

void* child_fn ( void* arg ) {

var++; /* Unprotected relative to parent */ /* this is line 6 */

return NULL;

}

int main ( void ) { pthread_t child;

pthread_create(&child, NULL, child_fn, NULL);

var++; /* Unprotected relative to child */ /* this is line 13 */

pthread_join(child, NULL);

return 0;

}

(30)

EXAMPLE FROM HELGRIND

Thread #1 is the program's root thread Thread #2 was created

at 0x511C08E: clone (in /lib64/libc-2.8.so)

by 0x4E333A4: do_clone (in /lib64/libpthread-2.8.so)

by 0x4E33A30: pthread_create@@GLIBC_2.2.5 (in /lib64/libpthread-2.8.so) by 0x4C299D4: pthread_create@* (hg_intercepts.c:214)

by 0x400605: main (simple_race.c:12)

Possible data race during read of size 4 at 0x601038 by thread #1 Locks held: none

at 0x400606: main (simple_race.c:13)

This conflicts with a previous write of size 4 by thread #2 Locks held: none

at 0x4005DC: child_fn (simple_race.c:6)

by 0x4C29AFF: mythread_wrapper (hg_intercepts.c:194) by 0x4E3403F: start_thread (in /lib64/libpthread-2.8.so) by 0x511C0CC: clone (in /lib64/libc-2.8.so)

Location 0x601038 is 0 bytes inside global var "var"

declared at simple_race.c:3

(31)

EXAMPLE FROM HELGRIND

The last clause is the main error message. It says there is a race as a result of a read of size 4 (bytes), at 0x601038, which is the address of var, happening in function main at line 13 in the program.

Two important parts of the message are:

üHelgrind shows two stack traces for the error, not one. By definition, a race involves two different threads accessing the same location in such a way that the result depends on the relative speeds of the

two threads.

üThe first stack trace follows the text "Possible data race during read of size 4 ..." and the second trace follows the text "This conflicts

with a previous write of size 4 ...". Helgrind is usually able to show both accesses involved in a race. At least one of these will be a write (since two concurrent, unsynchronised reads are harmless), and they will of course be from different threads.

To use this tool, you must specify --tool=helgrind on the Valgrind command line.

(32)

VALGRIND

Valgrind is Open Source / Free Software, and is freely

available under the GNU General Public License, version 2.

It runs on the following platforms: X86/Linux,

AMD64/Linux, ARM/Linux, ARM64/Linux, PPC32/Linux, PPC64/Linux, PPC64LE/Linux, S390X/Linux,

MIPS32/Linux, MIPS64/Linux, X86/Solaris,

AMD64/Solaris, ARM/Android (2.3.x and later), ARM64/Android, X86/Android (4.0 and later),

MIPS32/Android, X86/Darwin and AMD64/Darwin (Mac OS X 10.12)s

(33)

COMPONENTS

The Valgrind distribution currently includes six production-quality tools:

üa memory error detector, ütwo thread error detectors,

üa cache and branch-prediction profiler, üa call-graph generating cache,

üa branch-prediction profiler, and a heap profiler.

It also includes three experimental tools: a stack/global array overrun detector, a second heap profiler that

examines how heap blocks are used, and a SimPoint basic block vector generator.

(34)

TO USE HELGRIND

To use this tool, you must specify --tool=helgrind on the Valgrind command line

Example

üvalgrind –tool=helgrind myprog arg1 arg2

(35)

FUZZ TEST and

SANITIZATION

(36)

WHAT IS IT?

Fuzzing or fuzz testing is an automated

software testing technique that involves providing invalid, unexpected, or random data as inputs to a computer program.

Fuzz testing, or fuzzing, is a method of finding reliability problems, some subset of which may be vulnerabilities, by feeding purposely invalid and ill-formed data as input to program interfaces.

Fuzzing is typically a brute-force method that requires a high volume of testing, using multiple variations and test passes.

As a result, fuzzing generally needs to be automated.

(37)

INPUTS AND GOALS

Any application interface (for example, network, file input, command-line, Web form, and so forth) can be fuzz-tested.

The goals of fuzzing can vary depending on the type of interface being tested.

When testing an application to see if it properly handles a particular protocol, for example, goals include finding mishandling of truncated messages, incorrect length values, and illegal type codes that can lead to unstable operation protocol implementations

(38)

CYCLE

(39)

TOOLS

Dynamic randomized-input functional testing, also known as black-box fuzzing, has been widely used to find

security vulnerabilities in software applications since the early 1990s.

üRandomly modify (“fuzz”) well-formed input.

CERT Basic Fuzzing Framework (BFF) is a software testing tool that finds defects in applications that run on the Linux and Mac OS X platforms.

üVersion 2.8, Windows, Linux, Mac

ühttps://resources.sei.cmu.edu/library/asset- view.cfm?assetID=507974

üBFF automatically collects test cases that cause software to crash in unique ways.

(40)

BLACK BOX

Other black-box

üPeach, Protos, Spike, Autodafe, etc.

Simple but effective

(41)

TOOLS

LibFuzzer

ühttp://llvm.org/docs/LibFuzzer.html

üclang -g -O1 -fsanitize=fuzzer mytarget.c # Builds the fuzz target w/o sanitizers

üclang -g -O1 -fsanitize=fuzzer,address mytarget.c # Builds the fuzz target with ASAN

üclang -g -O1 -fsanitize=fuzzer,signed-integer-overflow mytarget.c # Builds the fuzz target with a part of UBSAN

(42)

CORPUS

Coverage-guided fuzzers like libFuzzer rely on a corpus of sample inputs for the code under test.

This corpus should ideally be seeded with a varied

collection of valid and invalid inputs for the code under test; for example, for a graphics library the initial corpus might hold a variety of different small PNG/JPG/GIF files.

The fuzzer generates random mutations based around the sample inputs in the current corpus. If a mutation triggers execution of a previously-uncovered path in the code under test, then that mutation is saved to the

corpus for future variations.

(43)

RUN

LibFuzzer will work without any initial seeds, but will be less efficient if the library under test accepts complex, structured inputs

mkdir CORPUS_DIR

cp /some/input/samples/* CORPUS_DIR

(44)

OUTPUT ON STDERR

(45)

ADDRESS SANITIZER

AddressSanitizer is a fast memory error detector. It

consists of a compiler instrumentation module and a runtime library. The tool can detect the following types of

bugs:

üOut-of-bounds accesses to heap, stack and globals üUse-after-free

üUse-after-return üUse-after-scope

üDouble-free, invalid free

üMemory leaks (experimental)

(46)

USAGE

http://clang.llvm.org/docs/AddressSanitizer.html

Simply compile and link your program with -

fsanitize=address flag. The AddressSanitizer run-time library should be linked to the final executable

(47)

UNDEF BEHAVIOR SANITIZER

UndefinedBehaviorSanitizer (UBSan) is a fast undefined behavior detector. UBSan modifies the program at

compile-time to catch various kinds of undefined behavior during program execution, for example:

üUsing misaligned or null pointer üSigned integer overflow

üConversion to, from, or between floating-point types which would overflow the destination

(48)

USAGE

http://clang.llvm.org/docs/UndefinedBehaviorSanitizer.ht ml

clang++ -fsanitize=undefined test.cc

(49)

BLACK AND WHITE

Black-box fuzzing Sending of malformed data without actual verification of which code paths were hit and which were not.

White-box fuzzing Sending of malformed data with

verification that all target code paths were hit—modifying software

configuration and the fuzzed data to traverse all data validations in the tested code.

(50)

NO BLACK-BOX APPROACHES

Black-box fuzzing has inferior code path coverage when compared to more sophisticated techniques such as

automated white-box fuzzing (or smart fuzzing).

üDynamic test generation.

Studies show that compare fuzzing methodologies

generally recommend using a mix of methodologies to maximize the efficacy of vulnerability discovery.

(51)

TPM

(52)

TRUST

Trust: A feeling of certainty (sometimes based on

inconclusive evidence) either (a) that the system will not fail or (b) that the system meets its specifications (i.e., that system does what it claims to do and does not

perform unwanted functions).

Trusted system: A system that operates as expected according to design and policy, doing what is required – despite environmental disruption, human user and

operator errors, and attacks by hostile parties – and not doing other things.

Trustworthy system: A system that not only is trusted, but also warrants that trust because the system’s

behavior can be validated in some convincing way, such as through formal analysis or code review.

(53)

TRUST

NSA definition

üTrusted:Systemorcomponentwhosefailurecanbreak the security policy. (TCB = Trusted Computing Base)

üTrustworthy: System or component that will not fail with respect to the security policy.

TCG definition

ü“An entity can be trusted if it always behaves in the expected manner for the intended purpose.”

Some people now regret the name Trusted Computing

üTrustworthy Computing or maybe Trustable Computing could be a better title, but it is too late to change.

(54)

TPM

Trusted Platform Module (TPM, also known as ISO/IEC 11889) is an international standard for a secure

cryptoprocessor, a dedicated microcontroller designed to secure hardware through integrated cryptographic keys

Trusted Platform Module (TPM) was conceived by a

computer industry consortium called Trusted Computing Group (TCG)

(55)

TPM

Chip manufacturers Intel and AMD, hardware

manufacturers such as HP and Dell, and operating system providers such as Microsoft include Trusted Computing in their products if enabled.

The U.S. Army requires that every new PC it purchases comes with a Trusted Platform Module (TPM).

As of July 3, 2007, so does virtually the entire United States Department of Defense.

(56)

COMPONENTS

Design goals:

üSimple, thus cheap (< $1) and hopefully free of bugs üLow performance (no crypto accelerator)

Smartcard like cryptographic coprocessor

üSmall set of cryptographic functions

• Key generation, signing, encryption (RSA), hashing (SHA-1), HMAC

üHardware random number generator (RNG)

Additional features

üAuthenticated boot (integrity measurement) üRemote attestation (integrity reporting)

üSealed storage

Securely bound to the rest of the platform

(57)

ARCHITECTURE

(58)

ARCHITECTURE

(59)

POSITIONING

(60)

TPM HARDWARE ARCHITECTURE

Microcontroller (μC) with RSA coprocessor and RNG ROM: Firmware for microcontroller

üSHA-1 and HMAC typically in software SRAM: Volatile memory

üKey slots: load external keys

üPlatform Configuration Registers (PCR): store integrity measurements (24 x 160 bit)

EEPROM: Non-volatile memory

üEndorsement Key (EK) uniquely identifies TPM

üStorage Root Key (SRK) encrypts other keys maintained by TPM ü Owner’s authorization data (password)

üMonotonic counters (4 x 32 bit)

üNVRAM: small amount of freely programmable memory I/O interface

üPC Client: Low-Pin Count (LPC) bus

üEmbedded: I2C or System Management Bus (SMBus)

(61)

TCG FUNCTIONALITIES

Authenticated boot

üLogging of boot sequence

Remote attestation

üReport boot sequence to third party

User management

üBalance the interest of different parties (user,owner,...)

Key management

üMaintain cryptographic keys and control usage/access üSealed storage: restrict access based on specific boot

sequence

• Other features

o RNG,c lock, monotonic counter,

(62)

AUTHENTICATED BOOT

(63)

FEATURES

Authenticated boot

üTPM is passive and only records the boot process

üPlatform can still load arbitrary software, like with a traditional open platform (e.g., PC)

üEnforcement of “good” configurations has to be done separately

• Remote attestation is used to grant/deny access to network service

• Sealed storage is used to grant/deny access to locally stored secret

Secure boot

Boot process is halted when untrusted software is loaded

o Only execute code that is signed by the device manufacturer or a certified software vendor

o Examples: game consoles, smart phones, TV settop box

•

(64)

REMOTE ATTESTATION

TPM identities

o Endorsement Key (EK): uniquely identifies TPM

o Attestation Identity Key (AIK): pseudonym

(65)

2 KEYS

TPM only stores two permanent cryptographic keys

üEndorsementKey(EK):uniqueRSAen-/decryptionkey

• Private key never leaves TPM

• Public key is privacy sensitive (identifies a TPM)

• Generated during manufacturing process of TPM

üStorageRootKey(SRK):RSAen-/decryptionkey

• Root of key hierarchy maintained by TPM

• Private key never leaves TPM

• Generated by TPM when ownership is taken

• Deleted when TPM owner is deleted

(66)

TWO KEYS

(67)

FURTHER LECTURES

https://link.springer.com/content/pdf/10.1007%2F978-1- 4302-6584-9_12.pdf