Study On Concurrency Bug Detection

In the era of real concurrency with multi-core architecture,concurrent programs have been widely used in software development because of their resource utilization and computing speed.However,due to the non-deterministic nature of thread scheduling,concurrent programs are prone to various types of concurrency bugs.Therefore,advanced concurrency bug detection techniques have become the current demands for finding various concurrency bugs defects rapidly and ensuring concurrent software reliability.In recent years,concurrency bug detection has drawn much attention of researchers in software engineering.Many kinds of concurrency bug detection techniques have been proposed.However,the current studies still face some limitations,such as the imprecise of thread sharing analysis,the inefficiency of concurrent test generation as well as concurrency bug detection,and the frenquent context switches in concurrent program execution trace.This paper focuses on solving these key problems in concurrency bug detection to further improve the detection ability and the efficiency.The contents are described as follows:1.To improve the precision of thread sharing analysis without impacting performance,we present a fine-grained and dynamic thread sharing analysis approach.First,we use stationary analysis to filter stationary fields,reducing false positives in the process ofidentifying shared fields.Then,we subtly leverage program locations as a bridge to distinguish between diffierent array elements.Finally,we mark shared access points and filter those points not accessed during program execution.We conduct the experiments on 20 Java multi-threaded programs,including three large systems.The results show that our approach performs better than the state-of-the-arts in terms of accuracy while maintaining good performance and can scale well to large programs with hundreds of threads.2.To explore the impact of thread sharing analysis with different granularities on the performance of data race detection,we conduct an empirical study.First,three granularities are considered,including object,field and “field + array element”.Then,an empirical study is conducted to evaluate the performance of data race detection based on three dynamic TSA approaches.The results show that data race detection based on the TSA with “field + array element” granularity outperforms those with object and field granularities.3.To improve the efficiency of concurrency bug detection,we present an automatic and efficient approach which combines the advantages of both bug-driven and coverage-guided techniques to generate test cases for thread-safe classes.First,method pairs that cannot be executed concurrently are removed by static analysis.Then,a strategy of bug-driven grouping of method pairs is designed to divide the remaining method pairs into two groups.One group contains the method pairs with a high priority and another group contains the method pairs with a low priority.Finally,iterative generation of concurrent test cases,which consists of coverage-guided generation of concurrent tests and concurrency bug detection,is conducted to find concurrency bugs.Our evaluation is on 20 thread-safe classes.Compared with four state-of-the-art approaches,the results show that our approach can obtain a significant improvement on efficiency without impairing bug finding capacities.4.To reduce the frequent context switches in concurrent program execution traces,we present a bidirectional trace simplification approach based on context switch linked list.First,we calculate the maximal sound dependence relations,including local dependences,synchronization dependences and remote read/write dependences.Second,we construct the context switch linked list according to the original buggy trace.Then,we backward refactor the context switch linked list in sequence to extend thread execution intervals.Finally,we forward check the context switch linked list in sequence to ensure that no nodes can be further merged.We conduct the experiments on eight Java multi-threaded programs to evaluate our approach.The results show that our approach performs better than or is comparable to the compared static approaches in effectiveness and efficiency.To sum up,this paper aims to solve some key problems in concurrency bug detection.It enriches the theory of concurrent program testing.Furthermore,it provides a new research guide for increasing the accuracy of thread sharing analysis and for improving the efficiency of concurrency bug detection as well as concurrency bug diagnose.