BIFER： a biphasic trace filter approach to scalable prediction of concurrency errors  

作　　者：XiCHANG Zhuo ZHANG Peng ZHANG Jianxin XUE Jianjun ZHAO 

机构地区：[1]Department of Computer Science and Engineering, Shanghai Jiao Tong University, Shanghai 200240, China [2]Department of Software Engineering, National University of Defense Technology, Changsha 410073, China [3]Department of Software Engineering, Shanghai Second Polytechnic University, Shanghai 201209, China

出　　处：《Frontiers of Computer Science》2015年第6期944-955,共12页中国计算机科学前沿（英文版）

摘　　要：Predictive trace analysis （PTA）, a static trace analysis technique for concurrent programs, can offer power- ful capability support for finding concurrency errors unseen in a previous program execution. Existing PTA techniques always face considerable challenges in scaling to large traces which contain numerous critical events. One main reason is that an analyzed trace includes not only redundant memory accessing events and threads that cannot contribute to dis- covering any additional errors different from the found can- didate ones, but also many residual synchronization events which still affect PTA to check whether these candidate ones are feasible or not even after removing the redundant events. Removing them from the trace can significantly improve the scalability of PTA without affecting the quality of the PTA results. In this paper, we propose a biphasic trace filter ap- proach, BIFER in short, to filter these redundant events and residual events for improving the scalability of PTA to expose general concurrency errors. In addition, we design a model which indicates the lock history and the happens-before his- tory of each thread with two kinds of ways to achieve the efficient filtering. We implement a prototypical tool BIFER for Java programs on the basis of a predictive trace analysis framework. Experiments show that BIFER can improve the scalability of PTA during the process of analyzing all of the traces.Predictive trace analysis （PTA）, a static trace analysis technique for concurrent programs, can offer power- ful capability support for finding concurrency errors unseen in a previous program execution. Existing PTA techniques always face considerable challenges in scaling to large traces which contain numerous critical events. One main reason is that an analyzed trace includes not only redundant memory accessing events and threads that cannot contribute to dis- covering any additional errors different from the found can- didate ones, but also many residual synchronization events which still affect PTA to check whether these candidate ones are feasible or not even after removing the redundant events. Removing them from the trace can significantly improve the scalability of PTA without affecting the quality of the PTA results. In this paper, we propose a biphasic trace filter ap- proach, BIFER in short, to filter these redundant events and residual events for improving the scalability of PTA to expose general concurrency errors. In addition, we design a model which indicates the lock history and the happens-before his- tory of each thread with two kinds of ways to achieve the efficient filtering. We implement a prototypical tool BIFER for Java programs on the basis of a predictive trace analysis framework. Experiments show that BIFER can improve the scalability of PTA during the process of analyzing all of the traces.

关 键 词：predictive trace analysis concurrency errors SCALABILITY 

分 类 号：TP393[自动化与计算机技术—计算机应用技术] TN713[自动化与计算机技术—计算机科学与技术]