C-AGENDA: A Constraint-sensitive Approach to GENeration of Deadlock Test Schedules for Multithreaded Applications

Description

Program testing is the most widely-practiced approach to exposing real failures from software applications and assuring their quality during software development. With the advent of the mulitcore architecture, multithreaded software applications are increasingly integrated to our living environments. Nonetheless, critical concurrent bugs such as deadlocks are from time to time reported by end users of many large-scale multithreaded software applications, indicating that the testing methods applied to them are still far from being adequate to cope with the challenges in real-world software development. Deadlocks stop programs from making progress. When users are performing critical activities that rely on multithreaded programs, deadlocks will be a nightmare.Static analysis or model checking techniques are well known to be imprecise. These techniques could not firmly and consistently expose real failures from multithreaded programs. Dynamic approach to testing is essential and demonstrates the ability to expose real failures instead of simply reporting that such a program has the potential to form deadlocks in some program runs. Nonetheless, our recent work has shown that existing state-of-the-art dynamic techniques are not consistently effective in exposing deadlocks that they target to detect. We have further found that sometimes they may systematically fail to expose certain deadlock bugs. If this is the case, then testers should manually confirm whether the scenarios are really the threats of the programs that they are developing and clear the threats if needed. Such manual inspection and judgment could be tedious and error-prone. New, precise and automated techniques that effectively expose deadlock failures should be developed to facilitate companies to implement high quality multithreaded software applications with pleasant user experience.This project aims at developing a novel C-AGENDA framework to support a Constraint-sensitive Approach to GENeration of Deadlock test schedules for multithreaded Applications that addresses all the above challenges. We propose to investigate the essential constraints and swappable constraints in a deadlock-free concurrent execution of a multithreaded program. We then use these constraints to model how a potential deadlock scenario could become a real nightmare (deadlock) in some other executions and divert the testing effort to confirm whether such a scenario is really a nightmare. The success of this project provides a highly effective framework to the industry to expose real deadlocks. We will also use this project to educate research students.