Concurrency Testing

One of the biggest challenges in concurrency testing is the large number of interleaving that is possible among processes or threads and even a single execution schedule (or thread interleaving) can cause a deadlock. To validate a code to be deadlock proof requires testing all possible execution schedules which is clearly not feasible. For example, a program with 2 threads and 100 lines has 2100 interleaving, which is practically infinite. Hence several heuristics have been designed to intelligently prune these execution schedules to a manageable size. One such attempt is the Microsoft Chess (Chess stands for concurrency stress test) tool, which intelligently selects a small subset of interleaving to test. We will present a framework that allows testers to either manually create an interleaving to test or to auto generate test cases. This forms the dynamic approach where the deadlocks are detected at runtime. In the static approach, the application is never executed but rather the source code forms as an input to another program.  One of the drawbacks of this this approach is that several false positives are reported. We will present an implementation of a static deadlock detection algorithm and show its performance on Java and C# libraries. Following is the list of projects in this page, 

1. A Concurrency Testing Tool for Dynamic Thread Interleaving - ACT3D Interleaver

2. Deadlock Detection in Java / C# Libraries Using Static Analysis

A Concurrency Testing Tool for Dynamic Thread Interleaving - ACT3D Interleaver

This project was done at IIIT-B in Fall 2010 as part of the software testing class under the guidance of Prof. R Chandrashekhar. Thanks to my friend Reehan for his constant support and contribution to this project.

Project Abstract:

There has been a rapid growth in the field of parallel programming over the past few years, primarily due to the advent of multi-core processors. The biggest challenge in concurrency is the uncontrollable non-determinism that it possesses due to the large number of interleaving that is possible among the processes or threads. Hence the traditional techniques employed for testing sequential programs cannot be used for testing concurrent software. In addition, there are other issues like race conditions and deadlocks.

     The goal of this project is to develop a concurrency testing tool that allows users to test specific interleaving of the threads in a program. A sequence of thread interleaves is called an execution schedule. The tool provides a graphical interface to create and test these execution schedules, provides an automatic interleave generator based on bread first search. The tool also allows the execution schedules to be stored and retrieved from a file. This helps in reproducing the defects caused by specific interleaving of the threads.

Downloads: Source Code   Project Report   Project Proposal 

Figure: High level block diagram

Following are some of the screen shots of the tool in action,

Figure: Initial Screen

Figure: User Interface for manual interleaving

Figure: Results of Test Case Execution

Figure: Auto Generate test cases (thread interleaving)

Deadlock Detection in Java / C# Libraries Using Static Analysis

This project was done at IIIT-B during Fall 2010 under the guidance of Prof. K. V. Dinesha and Mr. Vivek Shanbhag. 

Project Abstract:

The project aims to implement the algorithm presented in "Deadlock-Detection in Java-Library Using Static-Analysis". We extend the algorithm for detecting deadlocks in C# libraries (both Mono and .Net) and compare the results obtained with Java Libraries. In addition, we also report deadlocks that involve more than two locks / two threads. Most applications written in Java/C# depend heavily on the built-in libraries. When these libraries are used in a multi-threaded environment, a specific order of method invocations could cause the virtual machine (JVM / .Net) to deadlock. We observe that the library’s incorrect usage of locks on its shared objects / code blocks is the primary cause for the occurrence of such deadlocks.

        In Java, a ‘synchronized’ keyword annotated to a method ensures that only one thread can invoke it for the same object or class (if method is static). In other words, the synchronized keyword causes a thread to either acquire a lock on the object or block until all other threads that already invoked the method finish. The libraries are first disassembled using the appropriate tools (as shown in Fig. below). A parser then constructs a method invocation graph with each method as a node and each invocation within the method forms an edge. Each node is then short circuited if it does not represent a synchronized method. Next, two or more nodes that belong to the same object or class are combined and their corresponding edges retained which form parallel edges. The resulting graph is called a Lock Acquisition Graph (LAG) and any cycles in this graph could form a potential deadlock. 

Downloads: Source Code  Readme  Printable Source  XML Output with Open JDK 6 Libraries

Figure: Block diagram  and work flow of the implementation

Results: Open JDK 6  .Net 3.5   Mono 2.4.x

The cycles (potential deadlocks) in the Lock Acquisition Graph are reported in an xml format as shown in the figure below. Click here to download the complete output for Open JDK 6 libraries.

The tag <Cycle-#> lists the class names, where # represents the number of threads involved in the deadlock. The invocation sequence for each thread is listed using the <Thread-X> tag.

Our implementation found 65 cycles (potential deadlocks) in the Open JDK 6 libraries. But, no cycles were found in either the .Net or Mono libraries. In addition, the LAG (Lock Acquisition Graph) obtained from .Net libraries had only 10 edges whereas the Mono libraries had none. This is because .NET guidelines do not advice the use of synchronized methods, instead it is recommended to declare a 'private' object instance and use it to create a lock which can used anywhere within the Class. Click Here to access the related query that I posted on Mono development list. Hence we observed that enforcing certain coding guidelines / standards can help prevent bugs in the software.

Since the size of these libraries are in several megabytes, it becomes important to efficiently implement the algorithm, both in terms of the running time and memory consumption. Following figures show an analysis of the run-time complexity of our implementation.