Applying synchronization contracts approach for dynamic detection of data races in industrial applications
https://doi.org/10.15514/ISPRAS-2018-30(3)-4
Abstract
Data race occurs in multithreaded program when several threads simultaneously access same shared data and at least of them writes. Two main approaches to automatic race detection - static and dynamic - have their pros and cons. Dynamic analysis can provide best precision on certain program execution but introduce enormous runtime overheads. Earlier we introduced high-performance approach that improves performance of dynamic race detection. The key idea is to define and exclude external trusted parts of code (e.g. libraries) from analysis and replace them with specifications of their behavior in multithreaded environment. Possible behavior was classified and corresponding language for describing contracts developed. Evaluation on lightweight applications confirmed performance boost but further industrial usage of detector revealed some problems. This article covers that problems, introduces method and architecture of contract processing module and some technical features that help to apply proposed approach on high load production systems.
References
1. Java Language Specification, Third Edition. Threads and Locks. Happens-before Order. http://docs.oracle.com/javase/specs/jls/se7/html/jls-17.html#jls-17.4.5
2. Netzer R., Miller B. What Are Race Conditions? Some Issues and Formalizations. ACM Letters on Programming Languages and Systems, 1(1), 1992, pp. 74–88.
3. Blackout Final Report, August 14, 2003, http://www.ferc.gov/industries/electric/indus-act/reliability/blackout/ch5.pdf
4. Leveson N., Turner C. S. An Investigation of the Therac-25 Accidents. In IEEE Computer, vol. 26, N 7, 1993, pp. 18–41.
5. Engler D., Ashcraft K. RacerX: Effective, Static Detection of Race Conditions and Deadlocks. Proceedings of the Nineteenth ACM Symposium on Operating Systems Principles, 2003, pp. 237–252.
6. Voung J., Jhala R., Lerner S. RELAY: Static Race Detection on Millions of Lines of Code. In ESEC/FSE, 2007, pp. 205–214.
7. Herlihy M., Shavit N. The Art of Multiprocessor Programming. Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 2008, 528 p.
8. Kahlon V., Sinha N., Kruus E., Zhang Y.: Static data race detection for concurrent programs with asynchronous calls. In Proceedings of the 7th Joint Meeting of the European Software Engineering Conference and the Foundations of Software Engineering, 2009, pp. 13–22.
9. Naik M., Aiken A., Whaley J. Effective Static Race Detection for Java. In Proceedings of the 2006 ACM SIGPLAN Conference on Programming Language Design and Implementation, 2006, pp. 308–319.
10. Radoi C., Dig D. Practical static race detection for java parallel loops. In Proc. of the 13th International Symposium on Software Testing and Analysis, ISSTA ’13, 2013. P.178–190.
11. Xie X., Xue J., Zhang J. Acculock: Accurate and Efficient Detection of Data Races. Softw. Practice Experience, vol. 43, no. 5, May 2013, pp. 543–576.
12. Burckhardt S., Musuvathi M. Effective program verification for relaxed memory models. In Proceedings of the 20th international conference on Computer Aided Verification, Berlin, Heidelberg, 2008. pp. 107–120.
13. Huynh T., Roychoudhury A. Memory model sensitive bytecode verification. Form. Methods Syst. Des., 31(3), 2007, pp. 281–305.
14. Boyapati C., Lee R., Rinard M. Ownership types for safe programming: preventing data races and deadlocks. In Proceedings of the 17th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, 2002, pp. 211–230.
15. Flanagan C., Freund S. Type inference against races. Sci. Comput. Program., Vol 64, January 2007, pp. 140–165.
16. Rose J., Swamy N., Hicks M. Dynamic inference of polymorphic lock types. Science of Computer Programming, 58(3), 2005, pp. 366–383.
17. Biswas S., Zhang M., Bond M., Lucia B. Valor: Efficient, Software-Only Region Conflict Exceptions. In OOPSLA, 2015, pp. 241–259.
18. Flanagan C., Freund S. FastTrack: Efficient and Precise Dynamic Race Detection. In ACM Conference on Programming Language Design and Implementation, 2009, pp. 121–133.
19. Kini D., Mathur U., Viswanathan M. Dynamic race prediction in linear time. SIGPLAN Not. 52(6), 2017, pp. 157–170.
20. Qi Y., Das R., Luo Z., Trotter M. MulticoreSDK: a practical and efficient data race detector for real-world applications. Proceedings Software Testing, Verification and Validation (ICST), IEEE, 21-25 March 2011, pp. 309–318.
21. Serebryany S., Iskhodzhanov T. ThreadSanitizer: Data race detection in practice. In Proceedings of the Workshop on Binary Instrumentation and Applications, 2009, pp. 62–71.
22. Serebryany K., Potapenko A., Iskhodzhanov T., Vyukov D. Dynamic race detection with LLVM compiler - compile-time instrumentation for ThreadSanitizer. In RV, 2011, Lecture Notes in Computer Science, vol 7186, pp. 110–114.
23. Yu M., Bae D., SimpleLock+: Fast and Accurate Hybrid Data Race Detection. Comput. J., vol. 59, no. 6, 2016, pp. 793–809.
24. Zhang T., Jung C., Lee D. ProRace: Practical Data Race Detection for Production Use. In Proceedings of the International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS), 2017, pp. 149–162.
25. Bond M., Coons K., McKinley K. Pacer: Proportional Detection of Data Races. Proceedings of 2010 ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI 2010), Toronto, June 2010, pp. 255–268.
26. Marino D., Musuvathi M., Narayanasamy S. LiteRace: Effective Sampling for Lightweight Data Race Detection. PLDI '09 Proceedings of the 2009 ACM SIGPLAN conference on Programming language design and implementation, Vol. 44, Issue 6, 2009, pp. 134–143.
27. Trifanov V.Yu. Detecting data races in Java programs with synchronization contracts. Komp'juternye instrumenty v obrazovanii [Computer Tools in Education]. №4, 2012, pp. 16-29. (in Russian)
28. Trifanov V.Yu., Tsitelov D.I. Dynamic detection of data races in Java programs with synchronization contracts. Materialy konferencii "Instrumenty i metody analiza programm (TMPA-2013)" [Proc of Tools and Methods of Program Analysis conference TMPA-2013], Kostroma, 2013, pp. 273–285. (in Russian)
29. Trifanov V.Yu., Tsitelov D.I. Language for synchronization contracts creation to detect races in multithreaded applications. Programmnaja inzhenerija [Software Engineering], vol. 8, N 6, 2017, pp. 250–257. (in Russian)
30. Elmas T., Qadeer S., Tasiran S. Goldilocks: A Race and Transaction-Aware Java Runtime. Proceedings of the 2007 ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI'07), 2007, pp. 245–255.
31. Lamport L. Time, Clocks and the Ordering of Events in a Distributed System. Communications of the ACM, Vol. 21, Issue 7, 1978, pp. 558–565.
32. Intel Thread Checker, http://software.intel.com/en-us/intel-thread-checker/
33. Trifanov V.Yu. Dynamic data race detection in multithreaded Java-programs. PhD thesis, SPbSU, 2013. (in Russian)
34. Liskov B., Wing J. A behavioral notion of subtyping. ACM Trans. Program. Lang. Syst. 16 (6). November 1994, pp.1811–1841.
35. Click C. A lock-free wait-free hash table. https://web.stanford.edu/class/ee380/Abstracts/070221_LockFreeHash.pdf
36. Gavrilova T.A., Leshheva I.A., Kudrjavcev D.V. Using models of knowledge engineering for growing specialists in information technologies area. Sistemnoe programmirovanie [System programming], vol. 7, № 1, 2012, pp.. 90–105. (in Russian)
37. Koznov D.V. Basis of visual modeling. Internet-Universitet Informacionnyh Tehnologij (INTUIT) [Internet-University of Information Technologies], Moscow, 2008 (in Russian)
38. Ol'hovich L.B., Koznov D.V. OCL-Based Automated Validation Method for UML Specifications. Programming and Computer Software, vol. 29, № 6, 2003, pp. 44–50. DOI: 10.1023/B:PACS.0000004132.42846.11
39. Ivanov A., Koznov D., Murasheva T. Behavioral model RTST++, Zapiski seminara Kafedry sistemnogo programmirovanija "Case-sredstva RTST++" [Notes of seminar “Case-tools RTST++” of system engeneering department], 1998, № 1, pp. 37–52. (in Russian)
40. Luciv D.V., Koznov D.V., Basit H.A., Terehov A.N. On fuzzy repetitions detection in documentation reuse. Programming and Computer Software, vol. 42, № 4, 2016, pp. 39–49. DOI: 10.1134/S0361768816040046
41. Koznov D.V., Romanovskij K.Ju. Automated documentation refactoring for lines of program products. Sistemnoe programmirovanie [System programming], vol. 4, 2009, pp. 128–150. (in Russian)
Review
For citations:
Trifanov V.Yu. Applying synchronization contracts approach for dynamic detection of data races in industrial applications. Proceedings of the Institute for System Programming of the RAS (Proceedings of ISP RAS). 2018;30(3):47-62. (In Russ.) https://doi.org/10.15514/ISPRAS-2018-30(3)-4
Email this article 