Take a look at the new version of this page: [ beta version ]. Tell us what you think.

ABSTRACT

Multicore hardware is making concurrent programs pervasive. Unfortunately, concurrent programs are prone to bugs. Among different types of concurrency bugs, atomicity violation bugs are common and important. Existing techniques to detect atomicity violation bugs suffer from one limitation: requiring bugs to manifest during monitored runs, which is an open problem in concurrent program testing.

This paper makes two contributions. First, it studies the interleaving characteristics of the common practice in concurrent program testing (i.e., running a program over and over) to understand why atomicity violation bugs are hard to expose. Second, it proposes CTrigger to effectively and efficiently expose atomicity violation bugs in large programs. CTrigger focuses on a special type of interleavings (i.e., unserializable interleavings) that are inherently correlated to atomicity violation bugs, and uses trace analysis to systematically identify (likely) feasible unserializable interleavings with low occurrence-probability. CTrigger then uses minimum execution perturbation to exercise low-probability interleavings and expose difficult-to-catch atomicity violation.

We evaluate CTrigger with real-world atomicity violation bugs from four sever/desktop applications (Apache, MySQL, Mozilla, and PBZIP2) and three SPLASH2 applications on 8-core machines. CTrigger efficiently exposes the tested bugs within 1--235 seconds, two to four orders of magnitude faster than stress testing. Without CTrigger, some of these bugs do not manifest even after 7 full days of stress testing. In addition, without deterministic replay support, once a bug is exposed, CTrigger can help programmers reliably reproduce it for diagnosis. Our tested bugs are reproduced by CTrigger mostly within 5 seconds, 300 to over 60000 times faster than stress testing.

REFERENCES

• 1: Paul Barford , Mark Crovella, Generating representative Web workloads for network and server performance evaluation, Proceedings of the 1998 ACM SIGMETRICS joint international conference on Measurement and modeling of computer systems, p.151-160, June 22-26, 1998, Madison, Wisconsin, United States [doi>10.1145/277851.277897]
• 2: Boris Beizer, Software testing techniques (2nd ed.), Van Nostrand Reinhold Co., New York, NY, 1990
• 3: Arkady Bron , Eitan Farchi , Yonit Magid , Yarden Nir , Shmuel Ur, Applications of synchronization coverage, Proceedings of the tenth ACM SIGPLAN symposium on Principles and practice of parallel programming, June 15-17, 2005, Chicago, IL, USA [doi>10.1145/1065944.1065972]
• 4: O. Edelstein, E. Farchi, Y. Nir, G. Ratsaby, and S. Ur.Multi-threaded Java program test generation. In IBM Systems Journal, 2002.
• 5: Cormac Flanagan , Stephen N Freund, Atomizer: a dynamic atomicity checker for multithreaded programs, Proceedings of the 31st ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.256-267, January 14-16, 2004, Venice, Italy [doi>10.1145/964001.964023]
• 6: Cormac Flanagan , Shaz Qadeer, A type and effect system for atomicity, Proceedings of the ACM SIGPLAN 2003 conference on Programming language design and implementation, June 09-11, 2003, San Diego, California, USA [doi>10.1145/781131.781169]
• 7: Christian Hammer , Julian Dolby , Mandana Vaziri , Frank Tip, Dynamic detection of atomic-set-serializability violations, Proceedings of the 30th international conference on Software engineering, May 10-18, 2008, Leipzig, Germany [doi>10.1145/1368088.1368120]
• 8: M. J. Harrold, and B. A. Malloy. Data flow testing of parallelized code. In ICSM, 1992.
• 9: Pramod V. Koppol , Kuo-Chung Tai, An incremental approach to structural testing of concurrent software, Proceedings of the 1996 ACM SIGSOFT international symposium on Software testing and analysis, p.14-23, January 08-10, 1996, San Diego, California, United States [doi>10.1145/229000.226298]
• 10: J. R. Larus, and R. Rajwar. Transactional memory. Morgan & Claypool, 2006.
• 11: Shan Lu , Weihang Jiang , Yuanyuan Zhou, A study of interleaving coverage criteria, Proceedings of the the 6th joint meeting of the European software engineering conference and the ACM SIGSOFT symposium on The foundations of software engineering, September 03-07, 2007, Dubrovnik, Croatia [doi>10.1145/1287624.1287703]
• 12: Shan Lu , Soyeon Park , Eunsoo Seo , Yuanyuan Zhou, Learning from mistakes: a comprehensive study on real world concurrency bug characteristics, Proceedings of the 13th international conference on Architectural support for programming languages and operating systems, March 01-05, 2008, Seattle, WA, USA [doi>10.1145/1346281.1346323]
• 13: Shan Lu , Joseph Tucek , Feng Qin , Yuanyuan Zhou, AVIO: detecting atomicity violations via access interleaving invariants, Proceedings of the 12th international conference on Architectural support for programming languages and operating systems, October 21-25, 2006, San Jose, California, USA [doi>10.1145/1168857.1168864]
• 14: Brandon Lucia , Joseph Devietti , Karin Strauss , Luis Ceze, Atom-Aid: Detecting and Surviving Atomicity Violations, Proceedings of the 35th International Symposium on Computer Architecture, p.277-288, June 21-25, 2008 [doi>10.1109/ISCA.2008.4]
• 15: Chi-Keung Luk , Robert Cohn , Robert Muth , Harish Patil , Artur Klauser , Geoff Lowney , Steven Wallace , Vijay Janapa Reddi , Kim Hazelwood, Pin: building customized program analysis tools with dynamic instrumentation, Proceedings of the 2005 ACM SIGPLAN conference on Programming language design and implementation, June 12-15, 2005, Chicago, IL, USA [doi>10.1145/1065010.1065034]
• 16: Madanlal Musuvathi , Shaz Qadeer, Iterative context bounding for systematic testing of multithreaded programs, Proceedings of the 2007 ACM SIGPLAN conference on Programming language design and implementation, June 10-13, 2007, San Diego, California, USA [doi>10.1145/1250734.1250785]
• 17: M. Musuvathi, S. Qadeer, T. Ball, and G. Basler. Finding and reproducing heisenbugs in concurrent programs. In OSDI, 2008.
• 18: Nicholas Nethercote , Julian Seward, Valgrind: a framework for heavyweight dynamic binary instrumentation, Proceedings of the 2007 ACM SIGPLAN conference on Programming language design and implementation, June 10-13, 2007, San Diego, California, USA [doi>10.1145/1250734.1250746]
• 19: Robert H. B. Netzer , Barton P. Miller, Improving the accuracy of data race detection, Proceedings of the third ACM SIGPLAN symposium on Principles and practice of parallel programming, p.133-144, April 21-24, 1991, Williamsburg, Virginia, United States [doi>10.1145/109625.109640]
• 20: Stefan Savage , Michael Burrows , Greg Nelson , Patrick Sobalvarro , Thomas Anderson, Eraser: a dynamic data race detector for multithreaded programs, ACM Transactions on Computer Systems (TOCS), v.15 n.4, p.391-411, Nov. 1997 [doi>10.1145/265924.265927]
• 21: Software Bug Contributed to Blackout. SecurityFocus. http://www.securityfocus.com/news/8016
• 22: Koushik Sen, Race directed random testing of concurrent programs, Proceedings of the 2008 ACM SIGPLAN conference on Programming language design and implementation, June 07-13, 2008, Tucson, AZ, USA [doi>10.1145/1375581.1375584]
• 23: K. Sen, and G. Agha. Automated systematic testing of open distributed programs. In FSE, 2006.
• 24: Richard N. Taylor , David L. Levine , Cheryl D. Kelly, Structural Testing of Concurrent Programs, IEEE Transactions on Software Engineering, v.18 n.3, p.206-215, March 1992 [doi>10.1109/32.126769]
• 25: Mandana Vaziri , Frank Tip , Julian Dolby, Associating synchronization constraints with data in an object-oriented language, Conference record of the 33rd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.334-345, January 11-13, 2006, Charleston, South Carolina, USA [doi>10.1145/1111037.1111067]
• 26: Steven Cameron Woo , Moriyoshi Ohara , Evan Torrie , Jaswinder Pal Singh , Anoop Gupta, The SPLASH-2 programs: characterization and methodological considerations, Proceedings of the 22nd annual international symposium on Computer architecture, p.24-36, June 22-24, 1995, S. Margherita Ligure, Italy [doi>10.1145/223982.223990]
• 27: Min Xu , Rastislav Bodík , Mark D. Hill, A serializability violation detector for shared-memory server programs, Proceedings of the 2005 ACM SIGPLAN conference on Programming language design and implementation, June 12-15, 2005, Chicago, IL, USA [doi>10.1145/1065010.1065013]
• 28: Cheer-Sun D. Yang , Amie L. Souter , Lori L. Pollock, All-du-path coverage for parallel programs, Proceedings of the 1998 ACM SIGSOFT international symposium on Software testing and analysis, p.153-162, March 02-04, 1998, Clearwater Beach, Florida, United States [doi>10.1145/271771.271804]
• 29: Yuan Yu , Tom Rodeheffer , Wei Chen, RaceTrack: efficient detection of data race conditions via adaptive tracking, Proceedings of the twentieth ACM symposium on Operating systems principles, October 23-26, 2005, Brighton, United Kingdom [doi>10.1145/1095810.1095832]

INDEX TERMS

Primary Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.5 Testing and Debugging
          Subjects: Testing tools (e.g., data generators, coverage testing)

General Terms:
Languages, Reliability

Keywords:
concurrency bug, software testing