ABSTRACT
Concurrent programs are prone to various classes of difficult-to-detect faults, of which data races are particularly prevalent. Prior work has attempted to increase the cost-effectiveness of approaches for testing for data races by employing race detection techniques, but to date, no work has considered cost-effective approaches for re-testing for races as programs evolve. In this paper we present SimRT, an automated regression testing framework for use in detecting races introduced by code modifications. SimRT employs a regression test selection technique, focused on sets of program elements related to race detection, to reduce the number of test cases that must be run on a changed program to detect races that occur due to code modifications, and it employs a test case prioritization technique to improve the rate at which such races are detected. Our empirical study of SimRT reveals that it is more efficient and effective for revealing races than other approaches, and that its constituent test selection and prioritization components each contribute to its performance.
- R. Agarwal and S. D. Stoller. Run-time detection of potential deadlocks for programs with locks, semaphores, and condition variables. In Proceedings of the 2006 Workshop on Parallel and Distributed systems: Testing and Debugging, 2006. Google ScholarDigital Library
- M. D. Bond, K. E. Coons, and K. S. McKinley. PACER: Proportional Detection of Data Races. In Proceedings of the 2010 ACM SIGPLAN Conference on Programming Language Design and Implementation, 2010. Google ScholarDigital Library
- K. E. Coons, S. Burckhardt, and M. Musuvathi. Gambit: Effective unit testing for concurrency libraries. In Proceedings of the 15th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, 2010. Google ScholarDigital Library
- D. Deng, W. Zhang, and S. Lu. Efficient concurrency-bug detection across inputs. In International Conference on Object-Oriented Programming, Systems, Languages and Applications, 2013. Google ScholarDigital Library
- H. Do, S. G. Elbaum, and G. Rothermel. Supporting controlled experimentation with testing techniques: An infrastructure and its potential impact. Empirical Software Engineering, 10(4):405–435, 2005. Google ScholarDigital Library
- H. Do and G. Rothermel. On the use of mutation faults in empirical assessments of test case prioritization techniques. IEEE Transactions on Software Engineering, 32(9), Sept. 2006. Google ScholarDigital Library
- H. Do and G. Rothermel. On the use of mutation faults in empirical assessments of test case prioritization techniques. IEEE Transactions on Software Engineering, 32(9), Sept. 2006. Google ScholarDigital Library
- S. Elbaum, A. G. Malishevsky, and G. Rothermel. Test case prioritization: A family of empirical studies. IEEE Transactions on Software Engineering, 28(2), Feb. 2002. Google ScholarDigital Library
- D. Engler, B. Chelf, A. Chou, and S. Hallem. Checking system rules using system-specific, programmer-written compiler extensions. In Proceedings of the 4th International Conference on Symposium on Operating System Design and Implementation, 2000. Google ScholarDigital Library
- J. Erickson, M. Musuvathi, S. Burckhardt, and K. Olynyk. Effective data-race detection for the kernel. In Proceedings of the 9th USENIX Conference on Operating systems Design and Implementation, 2010. Google ScholarDigital Library
- C. Flanagan and S. N. Freund. FastTrack: Efficient and Precise Dynamic Race Detection. In Proceedings of the 2009 ACM SIGPLAN Conference on Programming Language Design and Implementation, 2009. Google ScholarDigital Library
- S. Fouché, M. B. Cohen, and A. Porter. Towards incremental adaptive covering arrays. In The 6th Joint Meeting on European Software Engineering Conference and the ACM SIGSOFT Symposium on the Foundations of Software Engineering: Companion Papers, 2007. Google ScholarDigital Library
- M. Gligoric, V. Jagannath, and D. Marinov. Mutmut: Efficient exploration for mutation testing of multithreaded code. In Proceedings of the Third International Conference on Software Testing, Verification and Validation, 2010. Google ScholarDigital Library
- Guarded Blocks. http://docs.oracle.com/javase/tutorial /essential/concurrency/guardmeth.html.Google Scholar
- R. L. Halpert, C. J. F. Pickett, and C. Verbrugge. Component-based lock allocation. In Proceedings of the 16th International Conference on Parallel Architecture and Compilation Techniques, 2007. Google ScholarDigital Library
- J. Huang, P. Liu, and C. Zhang. Leap: Lightweight deterministic multi-processor replay of concurrent java programs. In Proceedings of the 18th ACM SIGSOFT International Symposium on Foundations of Software Engineering, 2010. Google ScholarDigital Library
- V. Jagannath, Q. Luo, and D. Marinov. Change-aware preemption prioritization. In Proceedings of the 2011 International Symposium on Software Testing and Analysis, 2011. Google ScholarDigital Library
- P. Joshi, C.-S. Park, K. Sen, and M. Naik. A randomized dynamic program analysis technique for detecting real deadlocks. In Proceedings of the 2009 ACM SIGPLAN Conference on Programming Language Design and Implementation, 2009. Google ScholarDigital Library
- V. Kahlon, Y. Yang, S. Sankaranarayanan, and A. Gupta. Fast and accurate static data-race detection for concurrent programs. In Proceedings of the 19th International Conference on Computer Aided Verification, 2007. Google ScholarDigital Library
- B. Korel, G. Koutsogiannakis, and L. Tahat. Application of system models in regression test suite prioritization. In IEEE International Conference on Software Maintenance, 2008.Google ScholarCross Ref
- O. Laadan, N. Viennot, C.-C. Tsai, C. Blinn, J. Yang, and J. Nieh. Pervasive detection of process races in deployed systems. In Proceedings of the 23th ACM Symposium on Operating Systems Principles, 2011. Google ScholarDigital Library
- H. K. N. Leung and L. White. Insights into testing and regression testing global variables. Journal of Software Maintenance: Research and Practice, 2(4), 1990. Google ScholarDigital Library
- Z. Li, M. Harman, and R. M. Hierons. Search algorithms for regression test case prioritization. IEEE Transactions on Software Engineering, 33(4), Apr. 2007. Google ScholarDigital Library
- M. Musuvathi and S. Qadeer. Iterative context bounding for systematic testing of multithreaded programs. In Proceedings of the 2007 ACM SIGPLAN Conference on Programming Language Design and Implementation, 2007. Google ScholarDigital Library
- G. J. Myers and C. Sandler. The Art of Software Testing. John Wiley & Sons, 2004. Google ScholarDigital Library
- M. Naik, A. Aiken, and J. Whaley. Effective static race detection for java. In Proceedings of the 2006 ACM SIGPLAN Conference on Programming Language Design and Implementation, 2006. Google ScholarDigital Library
- R. O’Callahan and J.-D. Choi. Hybrid dynamic data race detection. In Proceedings of the 8th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, 2003. Google ScholarDigital Library
- A. Orso, N. Shi, and M. J. Harrold. Scaling regression testing to large software systems. In Proceedings of the 12th ACM SIGSOFT International Symposium on Foundations of Software Engineering, 2004. Google ScholarDigital Library
- C. Pacheco and M. D. Ernst. Randoop: Feedback-directed random testing for java. In Companion to the 22nd ACM SIGPLAN Conference on Object-oriented Programming Systems and Applications Companion, 2007. Google ScholarDigital Library
- C.-S. Park and K. Sen. Randomized active atomicity violation detection in concurrent programs. In Proceedings of the 16th ACM SIGSOFT International Symposium on Foundations of Software Engineering, 2008. Google ScholarDigital Library
- S. Park, S. Lu, and Y. Zhou. Ctrigger: Exposing atomicity violation bugs from their hiding places. In Proceedings of the 14th International Conference on Architectural Support for Programming Languages and Operating Systems, 2009. Google ScholarDigital Library
- R. Raman, J. Zhao, V. Sarkar, M. Vechev, and E. Yahav. Scalable and precise dynamic datarace detection for structured parallelism. In Proceedings of the 33rd ACM SIGPLAN Conference on Programming Language Design and Implementation, 2012. Google ScholarDigital Library
- G. Rothermel and M. J. Harrold. Analyzing regression test selection techniques. IEEE Transactions on Software Engineering, 22(8), Aug. 1996. Google ScholarDigital Library
- G. Rothermel and M. J. Harrold. A safe, efficient regression test selection technique. ACM Transactions on Software Engineering and Methodology, 6(2), Apr. 1997. Google ScholarDigital Library
- G. Rothermel, R. J. Untch, and C. Chu. Prioritizing test cases for regression testing. IEEE Transactions on Software Engineering, 27(10), Oct. 2001. Google ScholarDigital Library
- A. Salcianu and M. Rinard. Pointer and escape analysis for multithreaded programs. In Proceedings of the Eighth ACM SIGPLAN Symposium on Principles and Practices of Parallel Programming, 2001. Google ScholarDigital Library
- R. Santelices, P. K. Chittimalli, T. Apiwattanapong, A. Orso, and M. J. Harrold. Test-suite augmentation for evolving software. In Proceedings of the 23rd IEEE/ACM International Conference on Automated Software Engineering, 2008. Google ScholarDigital Library
- S. Savage, M. Burrows, G. Nelson, P. Sobalvarro, and T. Anderson. Eraser: A Dynamic Data Race Detector for Multithreaded Programs. ACM Transactions on Computer Systems, 15(4), 1997. Google ScholarDigital Library
- K. Sen. Race directed random testing of concurrent programs. In Proceedings of the 2008 ACM SIGPLAN Conference on Programming Language Design and Implementation, 2008. Google ScholarDigital Library
- K. Serebryany and T. Iskhodzhanov. ThreadSanitizer: Data race Detection in Practice. In Proceedings of the Workshop on Binary Instrumentation and Applications, 2009. Google ScholarDigital Library
- 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 Proceedings of the 33rd International Conference on Software Engineering, 2011. Google ScholarDigital Library
- Soot: a Java Optimization Framework. http://www.sable.mcgill.ca/soot/.Google Scholar
- F. Sorrentino, A. Farzan, and P. Madhusudan. Penelope: Weaving threads to expose atomicity violations. In Proceedings of the 18th ACM SIGSOFT International Symposium on Foundations of Software Engineering, 2010. Google ScholarDigital Library
- A. Srivastava and J. Thiagarajan. Effectively prioritizing tests in development environment. In Proceedings of the 2002 ACM SIGSOFT International Symposium on Software Testing and Analysis, 2002. Google ScholarDigital Library
- M. Staats, P. Loyola, and G. Rothermel. Oracle-centric test case prioritization. In Proceedings of the 23rd IEEE International Symposium on Software Reliability Engineering, 2012.Google ScholarDigital Library
- J. W. Voung, R. Jhala, and S. Lerner. Relay: Static race detection on millions of lines of code. In Proceedings of the 15th ACM SIGSOFT International Symposium on Foundations of Software Engineering, 2007. Google ScholarDigital Library
- L. White and B. Robinson. Industrial real-time regression testing and analysis using firewalls. In Proceedings of the 20th IEEE International Conference on Software Maintenance, 2004. Google ScholarDigital Library
- W. E. Wong, J. R. Horgan, S. London, and H. A. Bellcore. A study of effective regression testing in practice. In Proceedings of the Eighth International Symposium on Software Reliability Engineering, 1997. Google ScholarDigital Library
- S. Yoo and M. Harman. Regression testing minimisation, selection and prioritisation: A survey. Software Testing, Verification and Reliability, 22(2), 2012. Google ScholarDigital Library
- S. Yoo, M. Harman, P. Tonella, and A. Susi. Clustering test cases to achieve effective and scalable prioritisation incorporating expert knowledge. In Proceedings of the Eighteenth International Symposium on Software Testing and Analysis, 2009. Google ScholarDigital Library
- J. Yu, S. Narayanasamy, C. Pereira, and G. Pokam. Maple: A coverage-driven testing tool for multithreaded programs. In Proceedings of the ACM International Conference on Object Oriented Programming Systems Languages and Applications, 2012. Google ScholarDigital Library
- T. Yu, X. Qu, M. Acharya, and G. Rothermel. Oracle-based regression test selection. In Proceedings of the Sixth IEEE International Conference on Software Testing, Verification and Validation, 2013. Google ScholarDigital Library
- T. Yu, W. Srisa-an, and G. Rothermel. Simtester: A controllable and observable testing framework for embedded systems. In Proceedings of the 8th ACM SIGPLAN/SIGOPS Conference on Virtual Execution Environments, 2012. Google ScholarDigital Library
- T. Yu, W. Srisa-an, and G. Rothermel. An empirical comparison of the fault-detection capabilities of internal oracles. In IEEE 24rd International Symposium on Software Reliability Engineering, 2013.Google ScholarCross Ref
- T. Yu, W. Srisa-an, and G. Rothermel. Simracer: An automated framework to support testing for process-level races. In Proceedings of the 2013 International Symposium on Software Testing and Analysis, 2013. Google ScholarDigital Library
- W. Zhang, C. Sun, and S. Lu. Conmem: Detecting severe concurrency bugs through an effect-oriented approach. In Proceedings of the 15th International Conference on Architectural Support for Programming Languages and Operating Systems, 2010. Google ScholarDigital Library
- P. Zhou, R. Teodorescu, and Y. Zhou. Hard: Hardware-assisted lockset-based race detection. In Proceedings of the 2007 IEEE 13th International Symposium on High Performance Computer Architecture, 2007. Google ScholarDigital Library
Index Terms
- SimRT: an automated framework to support regression testing for data races
Recommendations
SimRacer: an automated framework to support testing for process-level races
ISSTA 2013: Proceedings of the 2013 International Symposium on Software Testing and AnalysisFaults introduced by races are difficult to detect because they usually occur only under specific execution interleavings. Numerous program analysis and testing techniques have been proposed to detect races between threads. Little work, however, has ...
Data races vs. data race bugs: telling the difference with portend
ASPLOS '12Even though most data races are harmless, the harmful ones are at the heart of some of the worst concurrency bugs. Alas, spotting just the harmful data races in programs is like finding a needle in a haystack: 76%-90% of the true data races reported by ...
Data races vs. data race bugs: telling the difference with portend
ASPLOS '12Even though most data races are harmless, the harmful ones are at the heart of some of the worst concurrency bugs. Alas, spotting just the harmful data races in programs is like finding a needle in a haystack: 76%-90% of the true data races reported by ...
Comments