On Concurrent Program Detection Techniques Based On Predictive Analysis

Concurrency can improve the efficiency of program execution significantly. Therefore, concurrent programs are concerned and widely applied in practice. However, it often brings concurrency bugs, such as, data race, atomicity violation, order violation and so on. The detection for concurrency bugs continues to grow.Based on the study of the mainstream technologies and the main technical index on the detection of concurrency bugs, this thesis focuses on the predictive analyze technique, and proposes several methods for detecting the concurrency bugs address to improve four dimensions: scalability, efficiency, effectiveness and understandability of the detection result.Aiming at the problem that there are many redundant and residual events in the analyzed trace, This thesis proposes a biphasic trace filtering technique. In the first phase, this technique scans this analyzed trace, computes the concurrency context of every thread and locates the corresponding statement location to construct a two dimension equivalence computation model. This model is used for collecting the criteria of the fully equivalence event and the equivalent thread for removing the local and global redundancies. In the second phase, this technique uses the redundancies-filtered trace and the message identifiers in the redundant threads to recognize the lock and communication residues automatically. The experiments show that this biphasic filtering technique can reduce the size of the analyzed trace significantly. It can improve the scalability of the predictive analysis technique.Aiming to the problem of order violation, the thesis proposes a interval-bounded bidirectional prediction approach. Through bidirectional scanning one normal trace,this approach first collects the types of expected data relations and computes the constraint to construct an expectation-based bidirectional prediction model. Secondly, it then adopts a safe tactics to recognize the violation interval, and directionally predict whether the expected relations can be flipped within this interval. Thirdly, it generates the corresponding schedules to prune the feasible order violations. The experiments show that this directional prediction approach can detect real order violations efficiently and effectively.Aiming to the null pointer dereference exceptions, this thesis proposes a technique combining constraint-directed prediction with active randomized testing. This technique first scans the analyzed trace to construct a constraint directed prediction model through computing the constraints, recoding the thread consecutive execution interval and collecting the sharing data flows. Secondly, directed by the constraints in the prediction model, it permutes the order of data flows relevant to null pointer dereference, and then generates the critical scenarios that may lead to null pointer dereference.Lastly, according to the generated critical scenarios, it actively controls thread schedules for detecting this bug. The experiments show that this technique can detect the null pointer dereference effectively.Aiming at the problem of frequent context switches in a trace, this thesis proposes a progressive trace simplification technique. This technique first scan the analyzed trace to construct a two-layered trace simplification model: the upper model is used for collecting the dependencies of the trace, the bottom model is used for identifying the context switches. Under the dependencies, it progressively merges the consecutive intervals of one thread in the bottom model. Lastly, according to the bottom model, it reorganizes the trace. The experiments show that this technique can reduce the number of context switches.