Research On Detecting Bugs In Concurrent Programs

As multi-core processors become popular,multithreaded programs are becoming pervasive.For programmers,writing correct multithreaded programs are increasingly important.When the multithreaded program is running,the thread schedule is non-deterministic.The programmers cannot clearly consider all the probable thread schedules.The triggering of one concurrency bug is related to specific thread schedule that is deeply hidden in huge thread schedule space.Therefore,the concurrency bugs are hard to be detected during software testing phase.Moreover,the concurrency bugs widely exist in multithreaded programs,affecting the software reliability severely.The previous techniques try to test all the thread schedules to detect concurrency bugs.However,the efficiency of these techniques are low if the concurrent programs are large.The number of thread schedules are increasing exponentially with the size of concurrent program.Therefore,these techniques are always used for small concurrent programs.Some techniques record the runtime information during program execution,and then predict the potential concurrency bugs based on the defined pattern,and finally dynamically verify every potential concurrency bug,detecting the real concurrency bugs.These techniques need to instrument the program to record runtime information and dynamic verify potential concurrency bugs,which brings runtime overhead.Therefore,the efficiency is one of the challenges of concurrency bug detection.In this paper,we design multiple concurrency bug detection techniques and propose many strategies to improve the efficiency of concurrency bug detection.1)Detecting concurrency bugs based on program slicing technique.In order to detect concurrency bugs,we combine static analysis and dynamic analysis to analyze the multithreaded program.We also use the program slicing technique to improve the efficiency of dynamic analysis.Through analyzing program statically,we can obtain all the potential concurrency bugs,including a large number of false positives.Therefore,we need to dynamically verify the results of static analysis.Before dynamic verification,we use the program slicing technique to remove the codes that are not related to concurrency bugs.During dynamically verifying potential concurrency bugs,we can detect concurrency bugs through analyzing smaller programs.In this paper,the static analysis can effectively guide the dynamic verification,making dynamic verification focus on the results of static analysis.The program slicing technique can help dynamic verification to detect real concurrency bugs more efficiently.The dynamic verification can effectively optimize the results of static analysis.We implemented a prototype called Col Finder to verify our approach.Col Finder can effectively detect concurrency bugs in multithreaded programs.The time of verifying potential concurrency bugs is reduced by program slicing technique,with an average of 33%.2)Detecting data races through parallelizing race verification.Data race is one of the most common types of concurrency bugs in multithreaded programs.We propose an approach to detect this type of concurrency bug.We use traditional static race detection technique to analyze the multithreaded program,identifying all the potential data races.To detect the harmful data races,we need to dynamically verify all the potential data races reported by static analysis.However,the number of potential data races may be large.To improve the efficiency,we dispatch all the potential data races to multiple machines,and dynamically verify the potential data races on multiple machines in parallel.On each machine,we instrument the program to control thread schedule,creating race conditions dynamically and checking whether a program failure is caused.We implemented a prototype called PRFinder to verify our approach.PRFinder can effectively detect the harmful data races in multithreaded programs.The time of race verification is reduced linearly with the number of machines.3)Detecting harmful data races by grouping technique.To verify the data races dynamically,previous approaches check whether a data race is harmful during one program execution.If there are a large number of data races,they need to execute the program many times to verify all the data races.According to the four memory accesses of two data races,we propose a grouping technique to group the data races that do not interfere into the same set,making the data races in the same set be dynamically verified during one program execution.Since we need to verify multiple data races during one dynamic execution,we design new strategies to dynamically verify the data races and detect harmful data races.Therefore,the number of program executions of our approach is less than previous approaches.The harmful data races can still be detected by our approach.We implemented a prototype called Race Checker to verify our approach.Race Checker can detect the harmful data races in multithreaded programs successfully.Comparing with previous approaches,Race Fuzzer and Race Mob,the detection time of Race Checker is reduced,with an average of 81% and 45%,respectively.4)General concurrency bug detection based on analysis of redundant thread interleaving.The general concurrency bug detection techniques that are based on interleaving pattern can detect multiple types of concurrency bugs in multithreaded programs.However,the defined interleaving patterns overlap,which makes some interleavings are analyzed repeatedly.To improve the efficiency,we design some strategies to determine whether a thread interleaving is redundant.We also propose an algorithm to analyze all the interleavings and prune the redundant ones.Based on the algorithm,we can design a new general concurrency bug detection technique that without analyzing redundant interleavings.To evaluate our approach,we apply our approach to two existing well-known techniques,PECAN and Maple.The experimental results show that our approach would not affect the results of concurrency bug detection.The bug detection time of the improved PECAN is less than the PECAN,with an average of 40.0%.The improved Maple also reduces bug detection time,with an average of 44.4%.