-The Technology Behind Static Code Analysis for Identifying Concurrency Defects
Most developers would agree that consumers of software today continually demand more from their applications. Because of its pace of evolution to date, the world now anticipates a seemingly endless expansion of capabilities from their software, regardless of where that software is applied. For the last 40 years of computing, Moore’s Law has held true, with the number of transistors available in an integrated circuit doubling approximately every two years.
This constant pace of innovation provided software developers with critical hardware resources, enabling them to expand the features and functionalities of their applications without concern for performance. However, while Moore’s Law still is holding steady, single-core processing has reached its performance ceiling. In response, hardware manufacturers have developed new multi-core (or multi-processor) devices to accomplish the speed gains to which the world had grown accustomed.
Today, the world of software development is presented with a new challenge. To fully leverage this new class of multi-core hardware, software developers must change the way they create applications. By turning their focus to multi-threaded applications, developers will be able to take full advantage of multi-core devices and deliver software that meets the demands of the world. But this paradigm of multi-threaded software development adds a new wrinkle of complexity for those who care the utmost about software quality. Concurrency defects such as race conditions and deadlocks are software defect types that are unique to multi-threaded applications. Complex and hard-to-find, these defects can quickly derail a software project. To avoid catastrophic failures in multi- threaded applications, software development organizations must understand how to identify and eliminate these deadly problems early in the application development lifecycle.
Testing software code is notoriously difficult, even for single-threaded applications. One reason this is a challenge, is that properly testing an application requires the simulation of all possible inputs to the program. Many organizations are satisfied when they achieve 95% line coverage in their programs (meaning 95% of all lines of code in their program are executed at least once in their test suite). However, this metric of coverage does not even come close to the total number of possible execution paths through a code base. Each decision point in a program means at least a factor of two in the number of paths though that program.
Multi-threaded applications add a new level of complexity to the program that results in an exponential increase in the number of possible run time scenarios. See Figure 1 below for an example as to how turning a simple single-threaded application into a multi-threaded application increases the complexity tremendously.
To completely test the program in Figure 1 the software developer would simply need to make sure that they fed the program a value that was less than 100 as well as a value that was greater than or equal to 100. Then the two paths through the program would be explored and the program would be tested entirely. (NOTE: This assumes that nothing interesting happens in the input_from_user function—admittedly a bad assumption in software development!). Now imagine that the end-user wanted this program to input two values instead of one with the same logic after the input. This change would increase the complexity of the single-threaded application in such a way that the software developer would need to explore four different paths to fully test the program.
Now imagine that a requirement comes in from the field to make this application multi-threaded to take advantage of a dual-core processor. This change would require that the code in Figure 1 would be executed simultaneously by two different threads to take in the two inputs. Assuming that each statement is made up of three instructions (likely an underestimate), the number of possible interleavings of the instructions in the two threads leads to a mind boggling 194,480 different execution possibilities.
By moving to multi-threaded code in this simplified example, complexity explodes by five orders of magnitude, creating a tremendous challenge for any tester of software. If this type of defect does happen to slip into the field, developers are then faced with a dramatic increase in the number of avenues that require exploration before they can determine the root cause of the problem. Worse, for the first time, developers may not be able to reproduce problems that occur in multi-threaded applications because they are not in control of how their application will be executed when it runs. The operating system and thread scheduler together decide when each thread will be executed as multiple threads execute. Fortunately, by leveraging breakthroughs in technology, static analysis solutions can analyze code prior to run-time enabling developers to identify and eliminate onerous multi-threaded defects including race conditions, thread blocks and deadlocks.
Deadlocks (situations where a multi-threaded program cannot make any progress) are a particularly difficult concurrency issue to debug. They arise when the order of lock acquisition used by the program is inconsistent. A simple example is lock inversion, which happens when one thread attempts to acquire a lock (a), then holds on to the lock while attempting to acquire lock (b) . If another thread tries to acquire the locks in the opposite order (acquiring b before a), neither thread can make progress, and the program is deadlocked. A sample of this type of software defect can be found in Figure 2. (Note: While the remaining code examples in this paper are in Java, all the defects discussed herein can occur in any programming language.
If two distinct threads call methods lock1 and lock2, an unlucky scheduling might have the first thread acquire lock (a), while the second thread acquires lock (b). In this state, it is impossible for either thread to acquire the lock it needs to continue execution or release the lock it holds. More complicated deadlocks exist that involve the acquisition of multiple locks across multiple threads.
One way that advanced static analysis technology detects deadlocks is to ensure that all locks in the program are acquired and released in a consistent order. More concretely, the static analysis can construct an acyclic lock graph for a program. Nodes in a lock graph represent lock names, and an edge between nodes (a) and (b) denotes that at some point, lock (a) was held while lock (b) was acquired.
If a lock graph contains a cycle, the program may have a lock ordering or lock inversion deadlock. Innovative static analysis is now capable of finding these lock ordering defects inter-procedurally (through method calls), as these are likely to be missed by conventional code review or other defect detection techniques.
In Figure 2 above, a static analysis solution would create the following lock graph for method lock1:
The edge from Lock.a to Lock.b indicates that Lock.a should always be acquired before Lock.b. Analysis of method lock2, however, causes the analysis to add an edge from Lock.b to Lock.a:
This violates the requirement that the lock graph be acyclic. Therefore, a defect would be reported in lock2.
One of the biggest difficulties in leveraging static analysis to detect deadlocks is the issue of naming locks. In Figure 2, it is clear that “synchronized(a)” locks the static field “a” declared in the “Lock” class. But naming is not always so obvious. Consider the following refactoring of lock2.
Race conditions are another potentially disastrous type of concurrency defect that is endemic to multi-threaded applications. A race condition occurs when multiple threads access the same piece of data concurrently, at least one thread accessing the data is writing to the data (as opposed to simply reading the data), and the execution depends critically on the relative timing of events.
This is as concrete a definition as can be achieved in languages like C and C++ that do not have a formally defined memory model. In Java, a more precise (but not necessarily equivalent) definition can be formulated based on the Java memory model. A data race occurs when a variable is read by one or more threads and written by at least one thread, where the read and write events are not ordered by the ‘happens-before’ relationship. The happens-before relationship precisely defines when events are made visible to other threads (check the Java Language Specification for a complete definition of happens-before). See Figure 4 below for an example of this.
Suppose that an instance of class Race is used to keep a counter of active events across multiple threads. One problem with Race is that the ++ operator is not atomic. If increment is called 10 times from two different threads, the final value of count could be less than 10, because some of the writes to count can be clobbered by writes from the second thread. One possible fix is to synchronize the increment method as shown in Figure 5 below.
With count accessed in a synchronized block, interleaved calls to increment on the same instance object are eliminated. Static analysis helps programmers avoid race conditions by inferring and enforcing ‘guarded-by’ relationships on shared fields in the program. A field (f) is guarded-by lock (l) if accesses to (f) must be protected by holding lock (l). In Figure 5, the count variable is guarded-by the lock field of the Race class. The set of guarded-by relationships essentially define the locking discipline for each class in the program. When a preponderance of accesses to a field occur with the same lock held, a guarded-by relationship is inferred between the accessed field and the held lock. This may sound simple, but a number of sophisticated techniques are necessary to make this approach tenable.
Most importantly, the same lock-naming algorithm used in the context of deadlock detection is applied to associate fields with the specific lock used to protect access. This serves two purposes. First, it yields stronger correlations, since fields accessed incidentally with different locks held are not used to infer guarded-by relationships. Second, it allows static analysis tools to suggest a possible way to correct the discovered defect, such as enclosing the access in a synchronized scope with the suggested lock.
Another important technique in discovering race conditions with static analysis is to infer information about the program’s thread execution model. This includes information such as where threads are created, which functions can be called by multiple threads simultaneously, and which pieces of data are shared among threads.
Multi-core hardware is clearly increasing software complexity by driving the need for multi-threaded applications. Based on the rising rate of multi-core hardware adoption in both enterprise and consumer devices, the challenge of creating multi-threaded applications is here to stay for software developers. In the coming years, multi-threaded application development will most likely become the dominant paradigm in software.
As this shift continues, many development organizations will transition to multi-threaded application development on the fly. This creates new liabilities for development teams in terms of application quality and security, because their code is now vulnerable to a host of concurrency defects—a class of defect that can easily slip past manual code review and traditional testing techniques.
Developers moving to multi-threaded applications need advanced new testing capabilities to help them control this new cause of software complexity. Because they are nearly impossible to replicate in dynamic testing environments, static analysis is uniquely suited to play an important role in eliminating concurrency defects early in the software development lifecycle. However, due to their underlying complexity, some concurrency defect types (such as race conditions) have historically escaped detection by conventional static analysis tools. Today, sophisticated new technology is advancing the science of static analysis to help developers meet the challenge of creating multi-threaded applications. By arming developers with static analysis capabilities that detect complex concurrency defects early in the development lifecycle, organizations will accelerate their ability to produce and release multi-threaded applications with greater confidence.
Rutul Dave, Senior Development Manager, Coverity
Rutul received his Masters in Computer Science with a focus on networking and communications systems from University of Southern California. Within nine months into graduate school while learning about creating high-performance networking and distributed systems, he found his passion creating real bleeding-edge technology systems at various Bay Area-Silicon Valley startups like Procket Networks, Topspin Communications and then moving to Cisco Systems. He has years of software development experience in embedded and real-time systems.
His focus these days is on creating tools and technology to enhance the Software Development process and to equip Developers with the best resources, techniques and practices to maximize the integrity of software. When not evangelizing about the benefits of Software Integrity, he scratches the coding itch by developing mobile apps and understanding the Linux kernel.