With the rise of multi-core processors, concurrency has become increasingly common. The broader use of concurrency, however, has been accompanied by new challenges for programmers, who struggle to avoid race conditions and other concurrent memory access hazards when writing multi-threaded programs. The problem with concurrency is that many programmers have been trained to think sequentially, so when multiple threads execute concurrently, they struggle to visualize those threads executing in parallel. When two threads attempt to access the same unprotected region of memory concurrently (one reading, one writing) logical inconsistencies can arise in the program, which can yield security concerns that are hard to detect.

The ongoing struggle with concurrent threads of execution has introduced a whole class of concurrency-related issues, from race conditions to deadlock. Developers need help writing concurrent code correctly. This post, the second in a series on concurrency analysis introduces Clang Thread Safety Analysis, a tool that was developed as part of a collaboration between Google and the Secure Coding Initiative in the SEI's CERT Division. Clang Thread Safety Analysis uses annotations to declare and enforce thread safety policies in C and C++ programs.

Foundations of Our Work

Many programmers today typically take a lock-based approach to dealing with concurrency issues. Typically, the canonical lock-based approach involves locking a piece of memory to ensure only one thread at a time can access a given region of memory. Then, when that piece of memory no longer requires protection, it is unlocked. Attempts to access that memory by threads not holding the lock result in those threads blocking until the lock is released. There are certain classes of problems, however, where a lock-based approach does not make sense, including real-time systems and interactions between the graphical user interface (GUI) and synchronous resources, such as a database or the network.

Real-time systems typically avoid locks because with locked resources, the potential exists for threads to block while waiting for a lock to be released. If a critical thread is blocked (like the thrusters for a jet), the resulting behavior of the system could be disastrous. Likewise, is it often desirable to avoid using locks from the GUI thread. If the GUI thread is blocked, the user interface cannot be updated and no new user input can be accepted until the GUI thread is released from its blocking operation.

As detailed in our introductory blog post on this work, which was spearheaded by Dean Sutherland, our approach is predicated on thread usage policy (the subject of Sutherland's doctoral thesis) to address the locking problem described above. That blog post defined thread usage policy as a group of often unspecified preconditions used to manage access to a shared state by regulating which specific threads are permitted to execute particular code segments or to particular data fields. Put another way, instead of locking regions of memory, a programmer specifies that threads have roles to fulfill. Roles are associated with methods. Specifically, a programmer declares that a particular method should only be called from a thread context that is explicitly holding or not holding a specific role. For example, the main thread in a program is typically used to run the GUI for the program, so a programmer could assign the main thread a "GUI" role. A worker thread could be spawned off to handle database access, and that thread could be assigned a "Database" role. Finally, the programmer can use an annotation that specifies "may only be called when the 'Database' role is held." If the programmer wrote code that would attempt to access the database by calling the "Database" annotated function from a GUI function, a diagnostic would be generated alerting the programmer of this constraint violation.

The concept of thread usage policy is not language specific; similar concepts exist in many programming languages including Java, C, C#, C++, Objective-C, and Ada. The initial post on this work described its application to Java. This post will describe my effort with Dean Sutherland, along with collaborator DeLesley Hutchins of Google, to take the thread usage policy initially applied in Java and transfer it to C and C++ using the Clang open source compiler.

Collaborating with Google

As our team of researchers began implementing our approach, we learned that a thread safety analysis based on locks had already been developed by Google, and deployed on a large scale within their internal code base. The Google code base makes heavy use of locks, and they have developed both static analysis tools, and dynamic analysis tools such as Thread Sanitizer, to help find and prevent race conditions.

Working with DeLesley Hutchins, we came to the conclusion that although locks and roles are orthogonal ways of ensuring thread safety, they can both be handled using the same underlying static analysis machinery. The primary difference between the two approaches lies in the terminology that programmers use to annotate their programs. When we began this collaboration, Google had already mandated that all programmers use lock-based analysis on every line of C++ code that is run within Google.

An Overview of Our Analysis Technique

Compilers with static analysis functionality, such as Clang, have helped developers by allowing threading policies to be formally specified and mechanically checked. Clang is a production quality, open source compiler for the C family of programming languages that builds on the LLVM optimizer and code generator. Clang also provides a sophisticated infrastructure for implementing warnings and static analysis. We selected Clang because it initially parses a C++ input file to an abstract syntax tree (AST), which is an accurate representation of the original source code, down to the location parentheses. The AST makes it easier to emit quality diagnostics, but complicates analysis in other respects.

As described in our paper, the Clang analysis infrastructure constructs a control flow graph (CFG) for each function in the AST. This transformation is not a lowering step; each statement in the CFG points back to the AST node that created it. We are then able to walk the CFG, building a contextual set of roles currently held or not held, and compare them against assumptions annotated in the source code to diagnose incorrect assumptions. Due to working within a higher-level abstraction layer, the diagnostics we report to the user closely map to their actual source code, but we are still capable of producing diagnostics for compiler-generated code, such as implicitly-defined constructors in C++.

You can annotate your source with thread roles for analysis with Clang by using the capability attributes provided by the compiler (the full list can be found in the Clang documentation). You start by defining role types using the capability or shared_capability attributes and pass "role" as the argument. This attribute appertains to a struct or typedef, which can then be used to declare unique roles for use within your source code. For example, if a programmer wanted to declare two thread roles, FlightControl and Logging, for a C program, they would be introduced as:

typedef int __attribute__((capability("role"))) ThreadRole;
ThreadRole FlightControl, Logging;

These two distinct thread roles can then be used to identify those capabilities for use in the other capability attributes. Since thread roles do not define semantic functionality at runtime, the acquisition and forfeiture of a thread role capability is typically defined as a noop which does not require additional thread safety analysis checking, and is optimized away by the compiler, requiring no runtime overhead:

void acquire(ThreadRole R) __attribute__((acquire_capability(R))) __attribute__((no_thread_safety_analysis)) {}
void release(ThreadRole R) __attribute__((release_capability(R))) __attribute__((no_thread_safety_analysis)) {}

These functions can then be used to acquire or release the given thread role. Once the acquire() function is called, the capability passed in to the function will then be held for the capability context of all subsequent function calls, until the release() function is called with that capability. For instance, the logging thread's entry point may look like:

void *logging_entrypoint(void *arg) {
void *ret;
acquire(Logging);
ret = logging_entrypoint_impl(arg);
release(Logging);
return ret;
}

The thread entry point acquires the Logging role, calls the actual implementation of the logging thread with the Logging capability held, and then releases the Logging role before the thread completes execution. The FlightControl thread entry point would look similar, except it would acquire and release the FlightControl capability instead of the Logging capability.

At this point, it is now possible to usefully annotate functions as requiring either the Logging or the FlightControl capability. If these functions are called from a context where the capability set satisfies the requirements written on the function, no diagnostic is produced because the source code is logically consistent with the annotations. For instance, the following definition of the logging_entrypoint_impl() function demonstrates requiring the Logging capability in a well-formed manner:

extern void dispatch_log(const char *msg) __attribute__((requires_capability(Logger)));
extern const char *deque_log_msg(void) __attribute__((requires_capability(Logger)));
void *logging_entrypoint_impl(void *) __attribute__((requires_capability(Logger))) {
const char *msg;

while ((msg = deque_log_msg())) {
dispatch_log(msg);
}
return 0;
}

However, if a function is called from a context where the capability set does not satisfy its requirements, a diagnostic is produced at compile time. Consider this definition of the flight_control_entrypoint_impl() function:

void *flight_control_entrypoint_impl(void *) __attribute__((requires_capability(FlightControl))) {
dispatch_log("Flight Control Started"); /* Should diagnose an error */
/* ... */
return 0;
}

In this example, flight_control_entrypoint_impl() requires that the FlightControl capability be held, which is successful due to the implied implementation of the thread entrypoint acquiring the FlightControl role. However, the call to dispatch_log() requires the Logging capability be held, which it is not from within this call graph, and so a diagnostic is issued.

A Calculus of Capabilities

As described in our recently published paper on this work, C/C++ Thread Safety Analysis, Clang's thread safety analysis is based on a calculus of capabilities. To read or write to a particular location in memory, a thread must have the capability, or permission, to do so. A capability can be thought of as an unforgeable key or token, which the thread must present to perform the read or write. Capabilities can take one of two forms:

• A unique capability cannot be copied, so only one thread can hold the capability at any one time.
• A shared capability may have multiple copies that are shared among multiple threads. Uniqueness is enforced by a linear type system.

The analysis enforces a single-writer/multiple-reader discipline. Writing to a guarded location requires a unique capability. Likewise, reading from a guarded location requires either a unique or shared capability. In other words, many threads can read from a location at the same time because they can share the capability, but only one thread can write to it. Moreover, a thread cannot write to a memory location at the same time that another thread is reading from it because a capability cannot be both shared and unique at the same time.

This discipline ensures that programs are free of data races, which are a situation that occurs when multiple threads attempt to access the same location in memory at the same time, and at least one of the accesses is a write. Since write operations require a unique capability, no other thread can access the memory location at that time.

Wrapping Up

The destructive nature of race conditions means that many organizations use both static analysis and dynamic analysis in multi-threaded programs, similar to Google. While these tools complement each other, dynamic analysis operates without annotations and thus can be applied more widely. Dynamic analysis, however, can only detect race conditions in the subset of program executions that occur in test code. Static analysis has proved to be less flexible, but covers all possible program executions. Static analysis also reports errors earlier, i.e., at compile time.

We encourage readers to use these annotations by downloading the latest version of Clang (3.5) and trying them out. Please send us feedback on your experiences as well as feedback on the research described above in the comments section below.

Additional Resources

To download the paper, C/C++ Thread Safety Analysis, please visit
http://static.googleusercontent.com/media/research.google.com/en/us/ pubs/archive/42958.pdf.

To read the paper, Composable Thread Coloring (which was an earlier name for the technique we now call thread role analysis) by Dean Sutherland and Bill Scherlis, please go to
https://www.researchgate.net/publication/221643730_Composable_Thread_Coloring.