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

构建可靠、无bug的软件是一个重要且具有挑战性的问题。系统跟踪的动态分析是多管齐下的策略的几个方面之一，该策略试图通过识别软件中错误的可扩展的自动分析方法来解决这个问题。在这里，我们观察一个部署的系统或一个测试中的组件，以提取相关事件的踪迹，然后自动分析这些踪迹，以确定执行是否是系统中错误的症状。 该项目开发了可靠的、预测性的动态分析技术，用于检测竞争、原子性违反、死锁和其他并发属性，这些并发属性可以扩展到具有大量事件的跟踪。该项目侧重于离线动态分析，其中检查程序的存储跟踪。这些跟踪通常非常大，以确保跟踪能够执行生产规模软件的大部分内容。因此，为了最小化存储需求，这些跟踪被压缩。该项目开发的算法直接分析这种压缩的轨迹，而无需首先解压缩轨迹，然后分析它。这样的算法将被证明是快速的，因为它们将在压缩轨迹的大小上线性运行。该项目开发的教学材料将用于调查人员在推广活动中为当地的女孩谁代码章，并将在全国各地的教师论坛上提供。这个奖项反映了国家科学基金会的法定使命，并已被认为是值得通过使用基金会的智力价值和更广泛的影响审查标准进行评估的支持。

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.