Falcon: fault localization in concurrent programs

ABSTRACT

Concurrency fault are difficult to find because they usually occur under specific thread interleavings. Fault-detection tools in this area find data-access patterns among thread interleavings, but they report benign patterns as well as actual faulty patterns. Traditional fault-localization techniques have been successful in identifying faults in sequential, deterministic programs, but they cannot detect faulty data-access patterns among threads. This paper presents a new dynamic fault-localization technique that can pinpoint faulty data-access patterns in multi-threaded concurrent programs. The technique monitors memory-access sequences among threads, detects data-access patterns associated with a program's pass/fail results, and reports dataaccess patterns with suspiciousness scores. The paper also presents the description of a prototype implementation of the technique in Java, and the results of an empirical study we performed with the prototype on several Java benchmarks. The empirical study shows that the technique can effectively and efficiently localize the faults for our subjects.

References

1. R. Abreu, P. Zoeteweij, and A. J. C. van Gemund. On the accuracy of spectrum-based fault localization. In TAIC PART, pages 89--98, 2007.
2. K. Asanovic, R. Bodik, B. C. Catanzaro, J. J. Gebis, P. Husbands, K. Keutzer, D. A. Patterson, W. L. Plishker, J. Shalf, S. W. Williams, and K. A. Yelick. The landscape of parallel computing research: A view from Berkeley. Technical Report UCB/EECS-2006-183, UC Berkeley, 2006.
3. Q. Chen, L. Wang, Z. Yang, and S. D. Stoller. HAVE: detecting atomicity violations via integrated dynamic and static analysis. In ETAPS, pages 425--439, 2009.
4. J. DeSouza, B. Kuhn, B. R. de Supinski, V. Samofalov, S. Zheltov, and S. Bratanov. Automated, scalable debugging of MPI programs with the Intel® Message Checker. In Proc. Int'l. Wkshp. Software Eng. for HPC System Applications, IEEE Int'l. Conf. Software Eng. (ICSE), pages 78--82, 2005.
5. O. Edelstein, E. Farchi, Y. Nir, G. Ratsaby, and S. Ur. Multithreaded java program test generation. In Java Grande, page 181, 2001.
6. Y. Eytani, K. Havelund, S. D. Stoller, and S. Ur. Towards a framework and a benchmark for testing tools for multi-threaded programs. Concurr. Comput.: Pract. Exper., 19(3):267--279, 2007.
7. C. Flanagan and S. N. Freund. Type-based race detection for java. In PLDI, pages 219--232, June 2000.
8. C. Flanagan and S. N. Freund. Atomizer: a dynamic atomicity checker for multithreaded programs. In POPL, pages 256--267, 2003.
9. C. Flanagan, S. N. Freund, and J. Yi. Velodrome: a sound and complete dynamic atomicity checker for multithreaded programs. In PLDI, pages 293--303, 2008.
10. C. Flanagan and S. Qadeer. A type and effect system for atomicity. In PLDI, pages 338--349, 2003.
11. P. Godefroid and N. Nagappan. Concurrency at Microsoft: An exploratory survey. In Workshop on Exploiting Concurrency Efficiently and Correctly, 2008.
12. R. L. Halpert. Static lock allocation. Master's thesis, McGill University, 2008.
13. C. Hammer, J. Dolby, M. Vaziri, and F. Tip. Dynamic detection of atomic-set-serializability violations. In ICSE, pages 231--240, 2008.
14. J. A. Jones and M. J. Harrold. Empirical evaluation of the tarantula automatic fault-localization technique. In ASE, pages 273--282, 2005.
15. B. Liblit, M. Naik, A. X. Zheng, A. Aiken, and M. I. Jordan. Scalable statistical bug isolation. In PLDI, pages 15--26, 2005.
16. S. Lu, S. Park, E. Seo, and Y. Zhou. Learning from mistakes: A comprehensive study on real world concurrency bug characteristics. In ASPLOS, pages 329--339, March 2008.
17. S. Lu, J. Tucek, F. Qin, and Y. Zhou. AVIO: detecting atomicity violations via access interleaving invariants. In ASPLOS, pages 37--48, 2006.
18. B. Lucia and L. Ceze. Finding concurrency bugs with context-aware communication graphs. In MICRO, pages 553--563, 2009.
19. C. E. McDowell and D. P. Helmbold. Debugging concurrent programs. ACM Computing Surveys (CSUR), 21(4):593--622, 1989.
20. M. Musuvathi and S. Qadeer. Iterative context bounding for systematic testing of multithreaded programs. In PLDI, pages 446--455, June 2007.
21. M. Musuvathi, S. Qadeer, T. Ball, G. Basler, P. Nainar, and I. Neamtiu. Finding and reproducing heisenbugs in concurrent programs. In OSDI, pages 267--280, 2008.
22. M. Naik and A. Aiken. Conditional must not aliasing for static race detection. In POPL, pages 327--338, 2007.
23. S. Narayanasamy, Z. Wang, J. Tigani, A. Edwards, and B. Calder. Automatically classifying benign and harmful data racesallusing replay analysis. In PLDI, pages 22--31, 2007.
24. R. O'Callahan and J. Choi. Hybrid dynamic data race detection. In PPoPP, pages 167--178, 2003.
25. C. Park and K. Sen. Randomized active atomicity violation detection in concurrent programs. In FSE, pages 135--145, 2008.
26. S. Park, S. Lu, and Y. Zhou. CTrigger: exposing atomicity violation bugs from their hiding places. In ASPLOS, pages 25--36, 2009.
27. K. Poulsen. Tracking the blackout bug. SecurityFocus, February 2004. http://www.securityfocus.com/news/8412.
28. M. Ronsse and K. D. Bosschere. RecPlay: a fully integrated practical record/replay system. Trans. Comput. Syst., 17(2):133--152, 1999.
29. S. Savage, M. Burrows, G. Nelson, P. Sobalvarro, and T. Anderson. Eraser: a dynamic data race detector for multithreaded programs. Trans. Comput. Syst., 15(4):391--411, 1997.
30. K. Sen. Race directed random testing of concurrent programs. In PLDI, pages 11--21, 2008.
31. M. Süß and C. Leopold. Common mistakes in OpenMP and how to avoid them. In OpenMP Shared Memory Parallel Programming, volume LNCS 4315, pages 312--323, 2008.
32. A. Thakur, R. Sen, B. Liblit, and S. Lu. Cooperative crug isolation. In WODA, pages 35--41, 2009.
33. C. von Praun and T. R. Gross. Object race detection. In OOPSLA, pages 70--82, 2001.
34. R. Vuduc, M. Schulz, D. Quinlan, B. de Supinski, and A. Sæbjørnsen. Improving distributed memory applications testing by message perturbation. In PADTAD, pages 27--36, 2006.
35. L. Wang and S. D. Stoller. Accurate and efficient runtime detection of atomicity errors in concurrent programs. In PPoPP, pages 137--146, 2006.
36. J. Yi, C. Sadowski, and C. Flanagan. Sidetrack: Generalizing dynamic atomicity analysis. In PADTAD, 2009.