Dongdong Deng
Shan Lu
Skip Abstract Section
Abstract
In the multi-core era, it is critical to efficiently test multi-threaded software and expose concurrency bugs before software release. Previous work has made significant progress in detecting and validating concurrency bugs under a given input. Unfortunately, software testing always faces large sets of test inputs, and existing techniques are still too expensive to be applied to every test input in practice.
In this paper, we use open-source software to study how existing concurrency-bug detection tools work for a set of inputs. The study shows that an interleaving pattern, such as a data race or an atomicity violation, can often be exposed by many inputs. Consequently, existing bug detectors would inevitably waste their bug detection effort to generate duplicate bug reports, when applied to a set of inputs.
Guided by the above study, we propose a coverage metric, Concurrent Function Pairs (CFP), to efficiently approximate how interleavings overlap across inputs. Using CFP, we have designed a new approach to detecting data races and atomicity-violation bugs for a set of inputs.
Our evaluation on open-source C/C++ applications shows that our CFP-guided approach can effectively accelerate concurrency-bug detection for a set of inputs by reducing redundant detection effort across inputs.
- S. Agarwal, R. Barik, V. Sarkar, and R. K. Shyamasundar. May-happen-in-parallel analysis of x10 programs. In PPoPP, 2007. Google Scholar
Digital Library
- M. D. Bond, K. E. Coons, and K. S. McKinley. Pacer: Proportional detection of data races. In PLDI, 2010. Google ScholarDigital Library
- S. Burckhardt, P. Kothari, M. Musuvathi, and S. Nagarakatte. A randomized scheduler with probabilistic guarantees of finding bugs. In ASPLOS, 2010. Google ScholarDigital Library
- J. Burnim and K. Sen. Asserting and checking determinism for multithreaded programs. In FSE, 2009. Google ScholarDigital Library
- C. Cadar, D. Dunbar, and D. R. Engler. KLEE: Unassisted and automatic generation of high-coverage tests for complex systems programs. In OSDI, 2008. Google ScholarDigital Library
- F. Chen, T. F. Serbanuta, and G. Rosu. jPredictor: a predictive runtime analysis tool for Java. In ICSE, 2008. Google ScholarDigital Library
- J.-D. Choi et al. Efficient and precise datarace detection for multithreaded object-oriented programs. In PLDI, 2002. Google ScholarDigital Library
- Click. The Click Modular Router Project. http://read.cs.ucla.edu/click/click.Google Scholar
- D. Deng, W. Zhang, B. Wang, P. Zhao, and S. Lu. Understanding the interleaving-space overlap across inputs and software versions. In 4th USENIX Workshop on Hot Topics in Parallelism, 2012. Google ScholarDigital Library
- O. Edelstein, E. Farchi, Y. Nir, G. Ratsaby, and S. Ur. Multithreaded Java program test generation. IBM Systems Journal, 2002. Google ScholarDigital Library
- M. Emmi, S. Qadeer, and Z. Rakamarić. Delay-bounded scheduling. In POPL, 2011. Google ScholarDigital Library
- D. Engler and K. Ashcraft. RacerX: Effective, static detection of race conditions and deadlocks. In SOSP, 2003. Google ScholarDigital Library
- J. Erickson, M. Musuvathi, S. Burckhardt, and K. Olynyk. Effective data-race detection for the kernel. In OSDI, 2010. Google ScholarDigital Library
- C. Flanagan and S. N. Freund. Atomizer: a dynamic atomicity checker for multithreaded programs. In POPL, 2004. Google ScholarDigital Library
- C. Flanagan and S. N. Freund. Fasttrack: efficient and precise dynamic race detection. In PLDI, 2009. Google ScholarDigital Library
- J. Gilchrist. Parallel BZIP2, Data Compression Software. http://compression.ca/pbzip2/.Google Scholar
- GNU. gcov. http://www.linuxcommand.org/manpages/gcov1.html.Google Scholar
- P. Godefroid. Partial-Order Methods for the Verification of Concurrent Systems: An Approach to the State-Explosion Problem. Springer-Verlag New York, Inc., 1996. Google ScholarCross Ref
- P. Godefroid, N. Klarlund, and K. Sen. Dart: directed automated random testing. In PLDI, 2005. Google ScholarDigital Library
- P. Godefroid and N. Nagappan. Concurrency at Microsoft an exploratory survey. Technical report, Microsoft Research, MSR-TR-2008-75, May 2008.Google Scholar
- J. L. Greathouse, Z. Ma, M. I. Frank, R. Peri, and T. M. Austin. Demand-driven software race detection using hardware performance counters. In ISCA, 2011. Google ScholarDigital Library
- M. J. Harrold and B. A. Malloy. Data flow testing of parallelized code. In Proceedings of the International Conference on Software Maintenance, 1992.Google ScholarCross Ref
- G. J. Holzmann. The SPIN Model Checker: Primer and Reference Manual. Addison-Wesley Professional, 2003. Google ScholarDigital Library
- G. Jin, A. Thakur, B. Liblit, and S. Lu. Instrumentation and sampling strategies for Cooperative Concurrency Bug Isolation. In OOPSLA, 2010. Google ScholarDigital Library
- P. Joshi, C.-S. Park, K. Sen, and M. Naik. A randomized dynamic program analysis technique for detecting real deadlocks. In PLDI, 2009. Google ScholarDigital Library
- P. V. Koppol and K.-C. Tai. An incremental approach to structural testing of concurrent software. In ISSTA, 1996. Google ScholarDigital Library
- C. Lattner and V. Adve. LLVM: A compilation framework for lifelong program analysis & transformation. In CGO, 2004. Google ScholarDigital Library
- N. Leveson and C. S. Turner. An investigation of the Therac-25 accidents. In IEEE Computer, 1993. Google ScholarDigital Library
- D. Li, W. Srisa-an, and M. B. Dwyer. SOS: saving time in dynamic race detection with stationary analysis. In OOPSLA, 2011. Google ScholarDigital Library
- S. Lu, W. Jiang, and Y. Zhou. A study of interleaving coverage criteria. In FSE, 2007. Google ScholarDigital Library
- S. Lu, S. Park, C. Hu, X. Ma, W. Jiang, Z. Li, R. A. Popa, and Y. Zhou. MUVI: Automatically inferring multi-variable access correlations and detecting related semantic and concurrency bugs. In SOSP, 2007. Google ScholarDigital Library
- S. Lu, J. Tucek, F. Qin, and Y. Zhou. AVIO: detecting atomicity violations via access interleaving invariants. In ASPLOS, 2006. Google ScholarDigital Library
- B. Lucia and L. Ceze. Finding concurrency bugs with context-aware communication graphs. In MICRO, 2009. Google ScholarDigital Library
- C.-K. Luk, R. Cohn, R. Muth, H. Patil, A. Klauser, G. Lowney, S. Wallace, V. J. Reddi, and K. Hazelwood. Pin: building customized program analysis tools with dynamic instrumentation. In PLDI, 2005. Google ScholarDigital Library
- D. Marino, M. Musuvathi, and S. Narayanasamy. Effective sampling for lightweight data-race detection. In PLDI, 2009. Google ScholarDigital Library
- Mozilla. SpiderMonkey, Mozilla's JavaScript engine. https://developer.mozilla.org/en/SpiderMonkey.Google Scholar
- M. Musuvathi, S. Qadeer, T. Ball, G. Basler, P. A. Nainar, and I. Neamtiu. Finding and reproducing heisenbugs in concurrent programs. In OSDI, 2008. Google ScholarDigital Library
- S. Nagarakatte, S. Burckhardt, M. M. K. Martin, and M. Musuvathi. Multicore acceleration of priority-based schedulers for concurrency bug detection. In PLDI, 2012. Google ScholarDigital Library
- M. Naik, A. Aiken, and J. Whaley. Effective static race detection for Java. In PLDI, 2006. Google ScholarDigital Library
- S. Narayanasamy, Z. Wang, J. Tigani, A. Edwards, and B. Calder. Automatically classifying benign and harmful data races all using replay analysis. In PLDI, 2007. Google ScholarDigital Library
- N. Nethercote and J. Seward. Valgrind: a framework for heavyweight dynamic binary instrumentation. In PLDI, 2007. Google ScholarDigital Library
- R. H. B. Netzer and B. P. Miller. Improving the accuracy of data race detection. In PPoPP, 1991. Google ScholarDigital Library
- C.-S. Park and K. Sen. Randomized active atomicity violation detection in concurrent programs. In FSE, 2008. Google ScholarDigital Library
- S. Park, S. Lu, and Y. Zhou. CTrigger: Exposing atomicity violation bugs from their finding places. In ASPLOS, 2009. Google ScholarDigital Library
- PCWorld. Nasdaq's Facebook Glitch Came From Race Conditions. http://www.pcworld.com/businesscenter/article/255911/nasdaqs_facebook_glitch_came_from_race_conditions.html.Google Scholar
- M. Prvulovic. Cord:cost-effective (and nearly overhead-free) order-reordering and data race detection. In HPCA, 2006.Google Scholar
- M. Prvulovic and J. Torrellas. ReEnact: Using thread-level speculation mechanisms to debug data races in multithreaded codes. In ISCA, 2003. Google ScholarDigital Library
- S. Qadeer and D. Wu. Kiss: keep it simple and sequential. In PLDI, 2004. Google ScholarDigital Library
- R. Raman, J. Zhao, V. Sarkar, M. T. Vechev, and E. Yahav. Efficient data race detection for async-finish parallelism. In RV, 2010. Google ScholarDigital Library
- S. Savage, M. Burrows, G. Nelson, P. Sobalvarro, and T. Anderson. Eraser: A dynamic data race detector for multithreaded programs. ACM TOCS, 1997. Google ScholarDigital Library
- SDTimes. Testers spend too much time testing. http://www.sdtimes.com/SearchResult/31134.Google Scholar
- SecurityFocus. Software bug contributed to blackout. http://www.securityfocus.com/news/8016.Google Scholar
- K. Sen. Race directed random testing of concurrent programs. In PLDI, 2008. Google ScholarDigital Library
- K. Sen and G. Agha. Automated systematic testing of open distributed programs. In FSE, 2006.Google ScholarDigital Library
- K. Sen, D. Marinov, and G. Agha. CUTE: a concolic unit testing engine for c. In ESEC/SIGSOFT FSE, 2005. Google ScholarDigital Library
- K. Serebryany and T. Iskhodzhanov. Threadsanitizer, a valgrind-based detector of data races. http://code.google.com/p/data-race-test/wiki/ThreadSanitizer.Google Scholar
- T. Sheng, N. Vachharajani, S. Eranian, R. Hundt, W. Chen, and W. Zheng. Racez: a lightweight and non-invasive race detection tool for production applications. In ICSE, 2011. Google ScholarDigital Library
- E. Sherman, M. B. Dwyer, and S. Elbaum. Saturation-based testing of concurrent programs. In FSE, 2009. Google ScholarDigital Library
- Y. Shi, S. Park, Z. Yin, S. Lu, Y. Zhou,W. Chen, and W. Zheng. DefUse: Definition-use invariants for detecting concurrency and sequential bugs. In OOPSLA, 2010. Google ScholarDigital Library
- R. N. Taylor, D. L. Levine, and C. D. Kelly. Structural testing of concurrent programs. IEEE Trans. Softw. Eng., 1992. Google ScholarDigital Library
- M. Vaziri, F. Tip, and J. Dolby. Associating synchronization constraints with data in an object-oriented language. In POPL, 2006. Google ScholarDigital Library
- W. Visser, K. Havelund, G. Brat, S. Park, and F. Lerda. Model checking programs. Automated Soft. Eng. Journal, 2003. Google ScholarDigital Library
- E. Vlachos, M. L. Goodstein, M. A. Kozuch, S. Chen, B. Falsafi, P. B. Gibbons, and T. C. Mowry. Paralog: enabling and accelerating online parallel monitoring of multithreaded applications. In ASPLOS, 2010. Google ScholarDigital Library
- S. C. Woo, M. Ohara, E. Torrie, J. P. Singh, and A. Gupta. The SPLASH-2 programs: Characterization and methodological considerations. In ISCA, 1995. Google ScholarDigital Library
- M. Xu, R. Bodík, and M. D. Hill. A serializability violation detector for shared-memory server programs. In PLDI, 2005. Google ScholarDigital Library
- C.-S. D. Yang, A. L. Souter, and L. L. Pollock. All-du-path coverage for parallel programs. In ISSTA, 1998. Google ScholarDigital Library
- J. Yu and S. Narayanasamy. A case for an interleaving constrained shared-memory multi-processor. In ISCA, 2009. Google ScholarDigital Library
- J. Yu, S. Narayanasamy, C. Pereira, and G. Pokam. Maple: a coverage-driven testing tool for multithreaded programs. In OOPSLA, 2012. Google ScholarDigital Library
- Y. Yu, T. Rodeheffer, and W. Chen. Racetrack: Efficient detection of data race conditions via adaptive tracking. In SOSP, 2005. Google ScholarDigital Library
- W. Zhang, J. Lim, R. Olichandran, J. Scherpelz, G. Jin, S. Lu, and T. Reps. ConSeq: Detecting concurrency bugs through sequential errors. In ASPLOS, 2011. Google ScholarDigital Library
- P. Zhou, R. Teodorescu, and Y. Zhou. HARD: Hardware-assisted lockset-based race detection. In HPCA, 2007. Google ScholarDigital Library
Index Terms
- Efficient concurrency-bug detection across inputs
Recommendations
ConMem: detecting severe concurrency bugs through an effect-oriented approach
ASPLOS '10Multicore technology is making concurrent programs increasingly pervasive. Unfortunately, it is difficult to deliver reliable concurrent programs, because of the huge and non-deterministic interleaving space. In reality, without the resources to ...
Efficient concurrency-bug detection across inputs
OOPSLA '13: Proceedings of the 2013 ACM SIGPLAN international conference on Object oriented programming systems languages & applicationsIn the multi-core era, it is critical to efficiently test multi-threaded software and expose concurrency bugs before software release. Previous work has made significant progress in detecting and validating concurrency bugs under a given input. ...
ConMem: detecting severe concurrency bugs through an effect-oriented approach
ASPLOS XV: Proceedings of the fifteenth International Conference on Architectural support for programming languages and operating systemsMulticore technology is making concurrent programs increasingly pervasive. Unfortunately, it is difficult to deliver reliable concurrent programs, because of the huge and non-deterministic interleaving space. In reality, without the resources to ...
Comments