Research On Race Detection And Debugging Mechanisms In Multi-threaded Programs

With the development of multi-core technology,the computer processing power has been greatly improved.To take advantage of the power of multi-core processors,multithreaded programming has been widely adopted.However,writing correct and reliable multithreaded programs is more complicated than that of single-threaded programs.Developers require to consider both the implementation of algorithms and the synchronization between different threads.If the threads are not well synchronized,multi-threaded programs are prone to data races.However,data races are different from the errors in single-threaded programs.Data races are not only related to input,but also related to the run-time environment,making it difficult for developers to locate their locations and causes.Data races are harmful to the reliability and security of multi-threaded programs.They can lead to program errors and system crashes,greatly affect the normal operation of enterprise IT system and cause serious economic losses.At present,there are many problems that need to be studied and solved in the research of data races in multi-threaded programs.First,there exist many false negatives for the present data race detection techniques.In general,typical studies build a relational model of events based on synchronization operations in a multi-threaded program,and then analyze the corresponding relations to detect data races.However,some data races are hidden by special lock synchronization order,which cannot be found by existing detection techniques.Therefore,online analysis,prediction and detection of these hidden data races is a problem to be solved.Second,the present studies of testing and debugging for data races in multi-threaded programs are seriously inadequate.For the testing of multi-threaded programs,the present studies focus on thread scheduling,and only adopt few inputs to test multi-threaded programs,which causes path coverage to be very limited.The root cause is that the performance of active scheduling for multi-threaded programs is very low,and if a large number of inputs are applied,the testing time will be huge,and the test becomes very impractical.Therefore,how to test multi-threaded programs and consider both input and active scheduling is an important and urgent problem.Developers still apply traditional debugging methods to debug multi-threaded programs,but the traditional methods are very inefficient because of the randomness of data races.There is only a few of debugging techniques,which also require to use some complicated techniques,such as symbolic execution,to debug and find the causes of the errors.They are inefficient for the real-world debugging of the multi-threaded program.Therefore,it is critical to propose a more practical and efficient concurrent debugging method.In view of the above problems,from three aspects,including race detection,testing and debugging,to improve the reliability of multithreaded programs:Aiming at the data race detection,a new causal relation,called Afterward-Confirm(AC)relation for lock synchronization analysis is proposed.Compared with the existing HappensBefore(HB)and Causally-Precedes(CP)relations,the AC relation can more accurately represent the causality between events.Based on the AC relation,an efficient dynamic data race detection method is proposed.This method can predict the sequence of events after the lock synchronization sequence changed,and thus can predict hidden data races.Experiments show that,compared with the existing methods,the AC-based method can find additional 21.1% of data races,and use less time and space overheads.For the testing of multi-threaded programs,a concurrency testing method combining thread scheduling and fuzzing-input generation is proposed.This method applies the coverage-driven fuzzing testing to improve the coverage of the concurrency test.Both fuzzing and thread scheduling are very time-consuming,and the time will increase exponentially if we simply combine them.To address the performace challenge,a series of performance optimization techniques are proposed,including input filtering and static instrumentation.Experimental evaluation shows that the performance of concurrency testing and path coverage have been greatly improved.Compared with the other mthods,it can test and locate more data races.Aiming at the debugging of multi-threaded programs,a lightweight concurrency debugging technique is proposed.It exploits a layered scheduling technique based on two characteristics of multi-threaded programs: lock contention and race access.The global scheduling is separated into multiple sub-scheduling in the lock contention layer and race access layer.First,a new causal relation,Directly-Follows,is proposed to locate all the lock contentions.Then,it performs layered scheduling,first scheduling the order of lock contentions and then triggering race accesses.Last,it analyzes and finds the root causes of errors.As the scheduling happens within a much smaller scope,computational overhead can be largely reduced.The experimental results show that the proposed concurrency debugging method can effectively find the causes of errors.In summary,focusing on the data races in multi-threaded programs,this work is carried out from three aspects: data race detection,concurrency testing and concurrency debugging.These three aspects locate and eliminate data races in multi-threaded programs from different angles.