FAVOR: A Testing Framework for Detecting Atomicity ViOlations in ConcuRrent Traces

Project: ResearchGRF

View graph of relations


Program testing is a method to execute a multithreaded program over a test case and determine whether the program execution reveals any error or the output of the program is incorrect. It is the most widely practiced method in the industry to ensure program correctness. With the advent of multicore processors, more and more programs are multithreaded. Bug reports of useful multithreaded programs such as MySQL or Eclipse are still filed by users every now and then, reporting symptoms like halts and crashes, which are critical. On the other hands, program developments of this class of programs are increasingly mature, indicating that some basic kinds of concurrency bugs like data races should now be able to detect and fix. The continual reporting of severe symptoms on the use of such useful multithreaded programs indicate that research efforts should be placed to address the next level of fundamental concurrency bugs. Atomicity violation is a fundamental kind of concurrency bugs. Even an execution without any data race or deadlocks may incur atomicity violations. A code block execution in a trace usually contains a sequence of accesses to one or more memory locations as well as synchronization operations. Atomicity violation occurs when an execution fails to protect some of its code blocks. Such a code block is marked to be atomic. However, in actual execution, it is not the case. Such a failure of protection indicates that the intermediate results being processed by a particular code block may mistakenly be read or corrupted by some concurrently executing code blocks. Static analysis and model checking techniques in analyzing large-scale multithreaded programs are either imprecise or impractical. Dynamic approach to testing is essential to demonstrate the presence of atomicity violations instead of merely reporting the potentials of the code to produce them. Nonetheless, the state of the art techniques can only reveal such concurrency bugs by using excessive memory overheads and can be ineffective. They may exhaust all the memory even on analyzing medium-scale programs, not to mention the industry-scale ones. This project aims at developing a novel FAVOR framework to support the detection of atomicity violations in large-scale multithreaded programs. FAVOR addresses the key challenge in tracking cross-thread dependency and interleaving-sensitive issue in generating thread schedules with and without atomicity violations. This project will also educate students so that they can effectively contribute to the growth of the software industry after graduation. ?


Effective start/end date1/01/17 → …

    Research areas

  • program testing , multithreaded programs , adaptive testing , thread scheduling ,