ASPIRATION: a softwAre teSting aPproach to deadlock detectIon for laRge-scAle mulTIthreaded applicatiONs

Description

Software testing is the de facto approach to find out problems from programs. It consumes 30-50% of software development budgets. With the advent of multicore processor, companies should develop concurrent programs so that their software products can stay competitive. Multithreaded programs are a popular kind of concurrent programs. However, writing multithreaded programs is notoriously difficult, and many existing multithreaded programs such as Apache, Google Chrome, and Firefox have concurrency bugs such as deadlocks. Deadlocks are widely considered as severe bugs that can cause the programs to halt. However, many applications are browser-based. This trend will be intensified as cloud computing becomes increasingly popular. The lack of progress due to deadlock will cause software unable to complete their tasks. Companies that ship products that may suffer from deadlock will put themselves into serious disadvantages.Static analysis or model checking techniques are well known to be unable to scale up enough to handle commercial-scale programs. Our recent work has further shown that existing state-of-the-art dynamic techniques to detect deadlocks cannot consistently scale up to handle real-life software such as Apache, Google Chrome, and Firefox because they need excessive amount of memory or time to complete, if ever. Company products built on such software platforms may require excessive amounts of time and budget to assure their own products. This problem prolongs the development cycle, greatly reducing the competitiveness of the companies. Existing techniques also provide no guidelines on test comprehensiveness for companies to measure to what extent their products can be confidently free from deadlocks.This project aims at developing a novel framework that addresses both the test oracle problem and the test adequacy problem in the dynamic detection of deadlocks from large-scale multithreaded programs. We propose to investigate a lockset-based, iterative and classification-based strategy to address the scalability and adequacy issues. The success of this project will provide a highly efficient and scalable framework to the industry to detect deadlocks and educate research students so that they can contribute to the growth of the software industry after graduation.