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

Description

Program testing is a method to execute a multithreaded program over a test case anddetermine whether the program execution reveals any error or the output of the programis incorrect. It is the most widely practiced method in the industry to ensure programcorrectness. With the advent of multicore processors, more and more programs aremultithreaded. Bug reports of useful multithreaded programs such as MySQL or Eclipseare 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 programsare increasingly mature, indicating that some basic kinds of concurrency bugs like dataraces should now be able to detect and fix. The continual reporting of severe symptomson the use of such useful multithreaded programs indicate that research efforts shouldbe placed to address the next level of fundamental concurrency bugs.Atomicity violation is a fundamental kind of concurrency bugs. Even an executionwithout any data race or deadlocks may incur atomicity violations. A code blockexecution in a trace usually contains a sequence of accesses to one or more memorylocations as well as synchronization operations. Atomicity violation occurs when anexecution fails to protect some of its code blocks. Such a code block is marked to beatomic. However, in actual execution, it is not the case. Such a failure of protectionindicates that the intermediate results being processed by a particular code block maymistakenly be read or corrupted by some concurrently executing code blocks.Static analysis and model checking techniques in analyzing large-scale multithreadedprograms are either imprecise or impractical. Dynamic approach to testing is essential todemonstrate the presence of atomicity violations instead of merely reporting thepotentials of the code to produce them. Nonetheless, the state of the art techniques canonly reveal such concurrency bugs by using excessive memory overheads and can beineffective. They may exhaust all the memory even on analyzing medium-scaleprograms, not to mention the industry-scale ones.This project aims at developing a novel FAVOR framework to support the detection ofatomicity violations in large-scale multithreaded programs. FAVOR addresses the keychallenge in tracking cross-thread dependency and interleaving-sensitive issue ingenerating thread schedules with and without atomicity violations. This project will alsoeducate students so that they can effectively contribute to the growth of the softwareindustry after graduation.?