SHF: Small: Practical Controlled Concurrency Testing for Managed Code

About This Grant

Software testing is the predominant form of validating correctness for large real-world programs. Testing multi-threaded programs, where independent program tasks can execute concurrently and manipulate shared resources, remains challenging in practice since the sequence and ordering of interactions between multiple threads is hard to capture and replicate. This makes concurrency-related software bugs, called race conditions, very hard to detect and diagnose. If not identified proactively, concurrency bugs can manifest in production unexpectedly in disastrous ways, leading to potential human harm or loss of critical infrastructure. This project aims to develop principled techniques and tools for testing multi-threaded programs written in programming languages that depend on run-time management systems, such as, Java. Successful completion of this project will enable software engineers to perform reliable, efficient, and reproducible testing of large-scale concurrent applications to discover and eliminate race conditions. The project also includes synergistic educational activities, such as developing a debugging tool for novice programming classes and incorporating research findings into upper-division undergraduate computing courses. This project will develop a controlled concurrency testing solution for multi-threaded programs running alongside managed runtimes (e.g., Java Virtual Machine code), which will: (a) ensure a correct and efficient mechanism for deterministically controlling the scheduling of thread interactions; (b) provide support for systematically or randomly exploring thread schedules using state-of-the-art search strategies based on probabilistic or partial-order-based algorithms in order to uncover hard-to-find concurrency bugs; and (c) work for arbitrary programs off-the-shelf in a push-button fashion. A key pillar of this project is to focus on general-purpose applicability as a primary objective for research on concurrency testing platforms, alongside the traditional goals of performance and search-space optimization. The project will also enable the large-scale evaluation of modern search algorithms across a wide variety of real-world software that powers production-scale distributed systems and web applications. The project will develop open-source tooling for use by software engineers as well as for educational purposes. This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.