High Performance Dynamic Threading Analysis for Hybrid Applications

Mößbauer, Felix (10. Januar 2019): High Performance Dynamic Threading Analysis for Hybrid Applications. Masterarbeit, Fakultät für Mathematik, Informatik und Statistik, Ludwig-Maximilians-Universität München.

Abstract

Verifying the correctness of multithreaded programs is a challenging task due to errors that occur sporadically. Testing, the most important verification method for decades, has proven to be ineffective in this context. On the other hand, data race detectors are very successful in finding concurrency bugs that occur due to missing synchronization. However, those tools introduce a huge runtime overhead and therefore are not applicable to the analysis of real-time applications. Additionally, hybrid binaries consisting of Dotnet and native components are beyond the scope of many data race detectors. In this thesis, we present a novel approach for a dynamic low-overhead data race detector. We contribute a set of fine-grained tuning techniques based on sampling and scoping. These are evaluated on real-world applications, demonstrating that the runtime overhead is reduced while still maintaining a good detection accuracy. Further, we present a proof of concept for hybrid applications and show that data races in managed Dotnet code are detectable by analyzing the application on the binary layer. The approaches presented in this thesis are implemented in the open-source tool DRace.

• Dokumententyp: LMU München: Studienabschlussarbeit
• Keywords: Concurrency Bugs; Race Condition; Program Analysis; Binary Instrumentation; Sampling; Managed Applications
• Fakultät: Mathematik, Informatik und Statistik > Informatik > Ausgewählte Abschlussarbeiten
• Institut oder Departement: Institut für Informatik
• Themengebiete: 000 Informatik, Informationswissenschaft, allgemeine Werke > 004 Informatik
• Sprache: Englisch

Literaturliste

[App11] Andrew W. Appel. “Verified software toolchain”. In: European Symposium on Programming. 2011, pp. 1–17.

[Atz+16] Simone Atzeni et al. “ARCHER: effectively spotting data races in large OpenMP applications”. In: 2016 IEEE International Parallel and Distributed Processing Symposium (IPDPS). 2016, pp. 53–62.

[Bey+07] Dirk Beyer et al. “The software model checker b last”. In: International Journal on Software Tools for Technology Transfer 9.5-6 (2007), pp. 505–525.

[Blä18] Luc Bläser. “Practical detection of concurrency issues at coding time”. In: Proceedings of the 27th ACM SIGSOFT International Symposium on Software Testing and Analysis. 2018, pp. 221–231.

[Bru04] Derek L. Bruening. “Efficient, Transparent, and Comprehensive Runtime Code Manipulation”. PhD thesis. MASSACHUSETTS INSTITUTE OF TECHNOLOGY, 2004.

[Bru18] Derek Bruening. The DynamoRIO API. 2018.

[DNS05] David Detlefs, Greg Nelson, and James B. Saxe. “Simplify: a theorem prover for program checking”. In: Journal of the ACM (JACM) 52.3 (2005), pp. 365–473.

[DS91] Anne Dinning and Edith Schonberg. “Detecting access anomalies in programs with critical sections”. In: ACM SIGPLAN Notices. Vol. 26. 1991, pp. 85–96.

[FF09] Cormac Flanagan and Stephen N. Freund. “FastTrack: Efficient and Precise Dynamic Race Detection”. In: (2009).

[FF10] Cormac Flanagan and Stephen N. Freund. “The RoadRunner dynamic analysis framework for concurrent programs”. In: Proceedings of the 9th ACM SIGPLAN SIGSOFT workshop on Program analysis for software tools and engineering. 2010, pp. 1–8.

[FF17] Cormac Flanagan and Stephen N. Freund. The FASTTRACK2 Race Detector. 2017.

[Hil+13] Tobias Hilbrich et al. “MPI runtime error detection with MUST: advances in deadlock detection”. In: Scientific Programming 21.3-4 (2013), pp. 109–121. issn: 1058-9244.

[Hol97] Gerard J. Holzmann. “The model checker SPIN”. In: IEEE Transactions on software engineering 23.5 (1997), pp. 279–295.

[HP00] Klaus Havelund and Thomas Pressburger. “Model checking java programs using java pathfinder”. In: International Journal on Software Tools for Technology Transfer 2.4 (2000), pp. 366–381.

[Huf54] David A. Huffman. “The synthesis of sequential switching circuits”. In: (1954).

[JT08] Ali Jannesari and Walter F. Tichy. “On-the-fly race detection in multi-threaded programs”. In: Proceedings of the 6th workshop on Parallel and distributed systems: testing, analysis, and debugging. 2008, p. 6.

[KW10] Vineet Kahlon and Chao Wang. “Universal causality graphs: A precise happens-before model for detecting bugs in concurrent programs”. In: International Conference on Computer Aided Verification. 2010, pp. 434–449.

[KZC12] Baris Kasikci, Cristian Zamfir, and George Candea. “Data races vs. data race bugs: telling the difference with portend”. In: ACM SIGPLAN Notices 47.4 (2012), pp. 185–198.

[Lam78] Leslie Lamport. “Time, clocks, and the ordering of events in a distributed system”. In: Communications of the ACM 21.7 (1978), pp. 558–565.

[Lan07a] Rich Lander. Data Access Component (DAC) Notes. 2007.

[Lan07b] Rich Lander. Profiling. 2007.

[Luk+05] Chi-Keung Luk et al. “Pin: building customized program analysis tools with dynamic instrumentation”. In: Acm sigplan notices. Vol. 40. 2005, pp. 190–200.

[Mag+02] Peter S. Magnusson et al. “Simics: A full system simulation platform”. In: Computer 35.2 (2002), pp. 50–58.

[Mic17] Microsoft. Anatomy of a DbgEng Extension DLL. Ed. by Microsoft Hardware Dev Center. 2017.

[Mic18a] Microsoft. PE Format. Ed. by Microsoft Windows Dev Center. 2018.

[Mic18b] Microsoft. Synchronization Functions. Ed. by Microsoft Windows Dev Center. 2018.

[MMN09] Daniel Marino, Madanlal Musuvathi, and Satish Narayanasamy. “LiteRace: Effective Sampling for Lightweight Data-Race Detection”. In: (2009).

[Muc+99] Philip J. Mucci et al. “PAPI: A portable interface to hardware performance counters”. In: Proceedings of the department of defense HPCMP users group conference. Vol. 710. 1999.

[MW07] Arndt Müehlenfeld and Franz Wotawa. “Fault detection in multi-threaded C++ server applications”. In: Proceedings of the 12th ACM SIGPLAN symposium on Principles and practice of parallel programming. 2007, pp. 142–143.

[Nas17] Phil Nash. Catch2. 2017.

[NS07] Nicholas Nethercote and Julian Seward. “Valgrind: a framework for heavy-weight dynamic binary instrumentation”. In: ACM Sigplan notices. Vol. 42. 2007, pp. 89–100.

[OC03] Robert O’Callahan and Jong-Deok Choi. “Hybrid Dynamic Data Race Detection”. In: (2003).

[Ots+18] Yuto Otsuki et al. “Building stack traces from memory dump of Windows x64”. In: Digital Investigation 24 (2018), S101–S110. doi: 10.1016/j.diin.2018.01.013.

[Pat+11] Avadh Patel et al. “MARSS: a full system simulator for multicore x86 CPUs”. In: Design Automation Conference (DAC), 2011 48th ACM/EDAC/IEEE. 2011,pp. 1050–1055.

[Pau94] Lawrence C. Paulson. Isabelle: A generic theorem prover. Vol. 828. Springer Science & Business Media, 1994.

[PS03] Eli Pozniansky and Assaf Schuster. “Efficient On-the-Fly Data Race Detection in Multithreaded C++ Programs”. In: (2003).

[Sav97] Stefan Savage. “Eraser: A Dynamic Data Race Detector for Multithreaded Programs”. In: (1997).

[She+11] Tianwei Sheng et al. “RACEZ: a lightweight and non-invasive race detectio tool for production applications”. In: Proceedings of the 33rd International Conference on Software Engineering. 2011, pp. 401–410.

[SI09] Konstantin Serebryany and Timur Iskhodzhanov. “ThreadSanitizer – data race detection in practice”. In: (2009).

[SL14] Young Wn Song and Yann-Hang Lee. “Efficient data race detection for C/C++ programs using dynamic granularity”. In: Parallel and Distributed Processing Symposium, 2014 IEEE 28th International. 2014, pp. 679–688.

[Sut05] Herb Sutter. “The free lunch is over: A fundamental turn toward concurrency in software”. In: Dr. Dobb’s journal 30.3 (2005), pp. 202–210.

[TA13] Andrew S. Tanenbaum and Todd Austin. Structured computer organization. 6. ed. Boston: Pearson, 2013. isbn: 0132916525.

[THW10] Jan Treibig, Georg Hager, and Gerhard Wellein. “Likwid: A lightweight performance-oriented tool suite for x86 multicore environments”. In: Parallel Processing Workshops (ICPPW), 2010 39th International Conference on. 2010, pp. 207–216.

[Tv07] Andrew S. Tanenbaum and Maarten van Steen. Distributed systems: principles and paradigms. Prentice-Hall, 2007.

[Wen17] Maira Wenzel. Profiling Overview. Ed. by Microsoft. 2017.

[Xam08] Xamarin. Cecil Mono: Bytecode inspector. 2008.