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.