Veselin Raychev
Martin Vechev
Manu Sridharan
Abstract
Like shared-memory multi-threaded programs, event-driven programs such as client-side web applications are susceptible to data races that are hard to reproduce and debug. Race detection for such programs is hampered by their pervasive use of ad hoc synchronization, which can lead to a prohibitive number of false positives. Race detection also faces a scalability challenge, as a large number of short-running event handlers can quickly overwhelm standard vector-clock-based techniques.
This paper presents several novel contributions that address both of these challenges. First, we introduce race coverage, a systematic method for exposing ad hoc synchronization and other (potentially harmful) races to the user, significantly reducing false positives. Second, we present an efficient connectivity algorithm for computing race coverage. The algorithm is based on chain decomposition and leverages the structure of event-driven programs to dramatically decrease the overhead of vector clocks.
We implemented our techniques in a tool called EventRacer and evaluated it on a number of public web sites. The results indicate substantial performance and precision improvements of our approach over the state-of-the-art. Using EventRacer, we found many harmful races, most of which are beyond the reach of current techniques.
- AGARWAL, A., AND GARG, V. K. Efficient dependency tracking for relevant events in shared-memory systems. In PODC (2005). Google Scholar
Digital Library
- ARTZI, S., DOLBY, J., JENSEN, S. H., MØLLER, A., AND TIP, F. A Framework for Automated Testing of JavaScript Web Applications. In ICSE (May 2011). Google ScholarDigital Library
- CHRISTIAENS, M., AND BOSSCHERE, K. D. Accordion clocks: Logical clocks for data race detection. In Euro-Par (2001). Google ScholarDigital Library
- FLANAGAN, C., AND FREUND, S. N. FastTrack: efficient and precise dynamic race detection. In PLDI (2009). Google ScholarDigital Library
- HTML5 specification. http://www.w3.org/TR/html5/.Google Scholar
- IDE, J., BODIK, R., AND KIMELMAN, D. Concurrency concerns in rich Internet applications. In EC2 (2009).Google Scholar
- JAGADISH, H. V. A compression technique to materialize transitive closure. ACM Trans. Database Syst. 15, 4 (Dec. 1990), 558--598. Google ScholarDigital Library
- KASIKCI, B., ZAMFIR, C., AND CANDEA, G. Data races vs. data race bugs: telling the difference with Portend. In ASPLOS (2012). Google ScholarDigital Library
- LAMPORT, L. Time, clocks, and the ordering of events in a distributed system. In ACM Operating Systems (1978).Google ScholarDigital Library
- MATTERN, F. Virtual time and global states of distributed systems. In Proc. Workshop on Parallel and Distributed Algorithms (1989), C. M. et al., Ed.Google Scholar
- Bug 538892 - Replying to or forwarding emails on Hotmail no longer works properly: message content is often lost. https://bugzilla.mozilla.org/show_bug.cgi?id=538892.Google Scholar
- NARAYANASAMY, S., WANG, Z., TIGANI, J., EDWARDS, A., AND CALDER, B. Automatically classifying benign and harmful data races using replay analysis. In PLDI (2007). Google ScholarDigital Library
- NETZER, R. H. B., AND MILLER, B. P. Improving the accuracy of data race detection. In PPOPP (1991). Google ScholarDigital Library
- NETZER, R. N., AND MILLER, B. P. Detecting data races in parallel program executions. In LCPC (1989).Google Scholar
- PETROV, B., VECHEV, M., SRIDHARAN, M., AND DOLBY, J. Race detection for web applications. In PLDI (2012). Google ScholarDigital Library
- POZNIANSKY, E., AND SCHUSTER, A. Efficient on-the-fly data race detection in multithreaded c++ programs. In PPoPP (2003). Google ScholarDigital Library
- RICHARDS, G., LEBRESNE, S., BURG, B., AND VITEK, J. An analysis of the dynamic behavior of JavaScript programs. In PLDI (2010). Google ScholarDigital Library
- SEN, K. Race directed random testing of concurrent programs. In PLDI (2008), pp. 11--21. Google ScholarDigital Library
- SHI, Y., PARK, S., YIN, Z., LU, S., ZHOU, Y., CHEN, W., AND ZHENG, W. Do i use the wrong definition?: Defuse: definition-use invariants for detecting concurrency and sequential bugs. In OOPSLA (2010). Google ScholarDigital Library
- WebKit. http://www.webkit.org/.Google Scholar
- ZHENG, Y., BAO, T., AND ZHANG, X. Statically locating web application bugs caused by asynchronous calls. In WWW'2011 (2011). Google ScholarDigital Library
Index Terms
- Effective race detection for event-driven programs
Recommendations
Effective race detection for event-driven programs
OOPSLA '13: Proceedings of the 2013 ACM SIGPLAN international conference on Object oriented programming systems languages & applicationsLike shared-memory multi-threaded programs, event-driven programs such as client-side web applications are susceptible to data races that are hard to reproduce and debug. Race detection for such programs is hampered by their pervasive use of ad hoc ...
Race directed random testing of concurrent programs
PLDI '08Bugs in multi-threaded programs often arise due to data races. Numerous static and dynamic program analysis techniques have been proposed to detect data races. We propose a novel randomized dynamic analysis technique that utilizes potential data race ...
Race directed random testing of concurrent programs
PLDI '08: Proceedings of the 29th ACM SIGPLAN Conference on Programming Language Design and ImplementationBugs in multi-threaded programs often arise due to data races. Numerous static and dynamic program analysis techniques have been proposed to detect data races. We propose a novel randomized dynamic analysis technique that utilizes potential data race ...
Comments