ABSTRACT
Concurrency bugs are notoriously difficult to detect because there can be vast combinations of interleavings among concurrent threads, yet only a small fraction can reveal them. Atomic-set serializability characterizes a wide range of concurrency bugs, including data races and atomicity violations. In this paper, we propose a two-phase testing technique that can effectively detect atomic-set serializability violations. In Phase I, our technique infers potential violations that do not appear in a concrete execution and prunes those interleavings that are violation-free. In Phase II, our technique actively controls a thread scheduler to enumerate these potential scenarios identified in Phase I to look for real violations. We have implemented our technique as a prototype system AssetFuzzer and applied it to a number of subject programs for evaluating concurrency defect analysis techniques. The experimental results show that AssetFuzzer can identify more concurrency bugs than two recent testing tools RaceFuzzer and AtomFuzzer.
- Artho, C., Havelund, K., and Biere, A. 2003. High-level data races. Softw. Test. Verif. Reliab. 13, 4 (Nov. 2003), 207--227.Google ScholarCross Ref
- Ben-Asher, Y., Eytani, Y., Farchi, E., and Ur, S. 2006. Noise makers need to know where to be silent - producing schedules that find bugs. In Proc. ISOLA '06, 458--465. Google ScholarDigital Library
- Boonstoppel, P., Cadar, C., and Engler, D. 2008. RWset: Attacking path explosion in constraint-based test generation. In Proc. TACAS '08, 351--366. Google ScholarDigital Library
- Edelstein, O., Farchi, E., Nir, Y., Ratsaby, G., Ur, S. 2002. Multithreaded Java program test generation. IBM Syst J. 41, 1, 111--125. Google ScholarDigital Library
- Farzan, A. and Madhusudan, P. 2006. Causal atomicity. In Proc. CAV '06, 315--328. Google ScholarDigital Library
- Flanagan, C. and Freund, S. N. 2004. Atomizer: A dynamic atomicity checker for multithreaded programs. In Proc. POPL '04, 256--267. Google ScholarDigital Library
- Frankl, P. G. and Weiss, S. N. 1993. An experimental comparison of the effectiveness of branch testing and data flow testing. IEEE Trans. Softw. Eng. 19, 8 (Aug. 1993), 774--787. Google ScholarDigital Library
- Godefroid, P. and Nagappan, N. 2008. Concurrency at Microsoft: An exploratory survey. Technical Report MSR-TR-2008-75, May 2008.Google Scholar
- Hammer, C., Dolby, J., Vaziri, M., and Tip, F. 2008. Dynamic detection of atomic-set-serializability violations. In Proc. ICSE '08, 231--240. Google ScholarDigital Library
- Joshi, P., Naik, M., Park, C., and Sen, K. 2009. CalFuzzer: An extensible active testing framework for concurrent programs. In Proc. CAV '09, 675--681. Google ScholarDigital Library
- Joshi, P., Park, C., Sen, K., and Naik, M. 2009. A randomized dynamic program analysis technique for detecting real deadlocks. In Proc. PLDI '09, 110--120. Google ScholarDigital Library
- Kidd, N., Reps, T., Dolby, J., and Vaziri, M. 2007. Static detection of atomic-set-serializability violations. Technical Report #1623, University of Wisconsin-Madison, Oct. 2007.Google Scholar
- Kidd, N., Reps, T., Dolby, J., and Vaziri, M. 2009. Finding concurrency-related bugs using random isolation. In Proc. VMCAI '09, 198--213. Google ScholarDigital Library
- Lai, Z., Cheung, S. C., and Chan, W. K. 2009. Detecting atomic-set serializability violations in multithreaded programs through active randomized testing. Technical Report HKUST-CS09-07, September 2009.Google Scholar
- Lamport, L. 1978. Time, clocks, and the ordering of events in a distributed system. Commun. ACM 21, 7 (Jul. 1978), 558--565. Google ScholarDigital Library
- Lu, S., Park, S., Hu, C., Ma, X., Jiang, W., Li, Z., Popa, R. A., and Zhou, Y. 2007. MUVI: Automatically inferring multivariable access correlations and detecting related semantic and concurrency bugs. In Proc. SOSP '07, 103--116. Google ScholarDigital Library
- Lu, S., Park, S., Seo, E., and Zhou, Y. 2008. Learning from mistakes: A comprehensive study on real world concurrency bug characteristics. In Proc. ASPLOS '08, 329--339. Google ScholarDigital Library
- Lu, S., Tucek, J., Qin, F., and Zhou, Y. 2006. AVIO: Detecting atomicity violations via access interleaving invariants. In Proc. ASPLOS '06, 37--48. Google ScholarDigital Library
- Mazurkiewicz, A. 1987. Trace theory. In Advances in Petri Nets, 279--324. Google ScholarDigital Library
- Musuvathi, M., Qadeer, S., Ball, T., Basler, G., Nainar, P., and Neamtiu, I. 2008. Finding and reproducing Heisenbugs in concurrent programs. In Proc. OSDI '08, 267--280. Google ScholarDigital Library
- O'Callahan, R. and Choi, J. 2003. Hybrid dynamic data race detection. In Proc. PPoPP '03, 167--178. Google ScholarDigital Library
- Park, C. and Sen, K. 2008. Randomized active atomicity violation detection in concurrent programs. In Proc. SIGSOFT '08/FSE-16, 135--145. Google ScholarDigital Library
- Park, S., Lu, S., and Zhou. Y. CTrigger: Exposing atomicity violation bugs from their hiding places. In Proc. ASPLOS '09, 25--36. Google ScholarDigital Library
- Perkovic, D. and Keleher, P. J. 1996. Online data-race detection via coherency guarantees. In Proc. OSDI '96, 47--57. Google ScholarDigital Library
- Ratanaworabhan, P., Burtscher, M., Kirovski, D., Zorn, B., Nagpal, R., and Pattabiraman, K. 2009. Detecting and tolerating asymmetric races. In Proc. PPoPP '09, 173--184. Google ScholarDigital Library
- Savage, S., Burrows, M., Nelson, G., Sobalvarro, P., and Anderson, T. 1997. Eraser: A dynamic data race detector for multithreaded programs. ACM Trans. Comput. Syst. 15, 4 (Nov. 1997), 391--411. Google ScholarDigital Library
- Sen, K. 2008. Race directed random testing of concurrent programs. In Proc. PLDI '08, 11--21. Google ScholarDigital Library
- Stoller, S. D. 2002. Testing concurrent Java programs using randomized scheduling. In Proc. RV '02, 142--157.Google ScholarCross Ref
- Tian, C., Nagarajan, V., Gupta, R., and Tallam, S. 2008. Dynamic recognition of synchronization operations for improved data race detection. In Proc. ISSTA '08, 143--154. Google ScholarDigital Library
- Wang, C., Chaudhuri, S., Gupta, A., and Yang, Y. 2009. Symbolic pruning of concurrent program executions. In Proc. ESEC/FSE '09, 23--32. Google ScholarDigital Library
- Wang, L. and Stoller, S. D. 2006. Runtime analysis of atomicity for multithreaded programs. IEEE Trans. Softw. Eng. 32, 2 (Feb. 2006), 93--110. Google ScholarDigital Library
- Vaziri, M., Tip, F., and Dolby, J. 2006. Associating synchronization constraints with data in an object-oriented language. In Proc. POPL '06, 334--345. Google ScholarDigital Library
Recommendations
Randomized active atomicity violation detection in concurrent programs
SIGSOFT '08/FSE-16: Proceedings of the 16th ACM SIGSOFT International Symposium on Foundations of software engineeringAtomicity is an important specification that enables programmers to understand atomic blocks of code in a multi-threaded program as if they are sequential. This significantly simplifies the programmer's job to reason about correctness. Several modern ...
Learning from mistakes: a comprehensive study on real world concurrency bug characteristics
ASPLOS XIII: Proceedings of the 13th international conference on Architectural support for programming languages and operating systemsThe reality of multi-core hardware has made concurrent programs pervasive. Unfortunately, writing correct concurrent programs is difficult. Addressing this challenge requires advances in multiple directions, including concurrency bug detection, ...
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