SHF: Small: New Algorithmic Paradigms in Dynamic Analysis of Multithreaded Software

University Of Illinois At Urbana-Champaign, Urbana IL

Investigators

Abstract

Building reliable, bug-free software is an important and challenging problem. Dynamic analysis of system traces is one among several facets of a multi-pronged strategy that tries to address this problem through scalable, automated analysis methods that identify bugs in software. Here one observes a deployed system or a component under test, to extract a trace of relevant events, which is then automatically analyzed to determine if the execution is symptomatic of a bug in the system. This project develops sound, predictive dynamic analysis techniques to detect races, atomicity violations, deadlocks, and other concurrency properties that scale to traces with a large number of events. This project focuses on offline dynamic analysis, wherein a stored trace of a program is examined. These traces are often very large to ensure that the trace exercises large parts of a production-scale software. Therefore, to minimize storage needs, these traces are compressed. This project develops algorithms to analyze such compressed traces directly without first uncompressing the trace and then analyzing it. Such an algorithm will be provably fast since they will run in time that is linear in the size of the compressed trace. The project develops instructional material to be used by the investigators in outreach activities for the local Girls Who Code chapter, and will be available on teacher forums throughout the country. This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.