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

SHF：Small：多线程软件动态分析中的新算法范式

• 批准号: 2007428
• 负责人: Mahesh Viswanathan
• 金额: $ 25万
• 依托单位: University of Illinois at Urbana-Champaign
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2020
• 资助国家: 美国
• 起止时间: 2020-07-01 至 2024-06-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2007428&HistoricalAwards=false
• 关键词: SHF; Small; New; Algorithmic; Paradigms

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.

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

项目成果

On Linear Time Decidability of Differential Privacy for Programs with Unbounded Inputs

• DOI: 10.1109/lics52264.2021.9470708
• 发表时间: 2021-04
• 期刊: 2021 36th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS)
• 作者: Rohit Chadha;A. Sistla;Mahesh Viswanathan

A tree clock data structure for causal orderings in concurrent executions

• DOI: 10.1145/3503222.3507734
• 发表时间: 2022-01
• 期刊: Proceedings of the 27th ACM International Conference on Architectural Support for Programming Languages and Operating Systems
• 作者: Umang Mathur;Andreas Pavlogiannis;Hunkar Can Tuncc;Mahesh Viswanathan

Checking LTL[F,G,X] on compressed traces in polynomial time

在多项式时间内检查压缩迹线上的 LTL[F,G,X]

• DOI: 10.1145/3468264.3468557
• 发表时间: 2021
• 期刊: ACM Joint European Software Engineering Conference and Symposium on the Foundations of Software Engineering
• 作者: Zhang, Minjian;Mathur, Umang;Viswanathan, Mahesh
• 通讯作者: Viswanathan, Mahesh

Optimal prediction of synchronization-preserving races

同步保持竞争的最佳预测

• DOI: 10.1145/3434317
• 发表时间: 2021
• 期刊: Proceedings of the ACM on Programming Languages
• 作者: Mathur, Umang;Pavlogiannis, Andreas;Viswanathan, Mahesh
• 通讯作者: Viswanathan, Mahesh

Sound Dynamic Deadlock Prediction in Linear Time

• DOI: 10.1145/3591291
• 发表时间: 2023-04
• 期刊: Proceedings of the ACM on Programming Languages
• 作者: Umang Mathur;Andreas Pavlogiannis;Hunkar Can Tuncc;Mahesh Viswanathan