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.

构建可靠，无漏洞的软件是一个重要且具有挑战性的问题。系统痕迹的动态分析是多管齐下策略的几个方面之一，该策略试图通过可扩展的自动化分析方法来解决此问题，以识别软件中的错误。在这里，人们观察到已部署的系统或正在测试的组件，以提取相关事件的痕迹，然后自动分析，以确定执行是否是系统中错误的症状。 该项目开发了声音，预测的动态分析技术，以检测种族，原子性违规，僵局和其他并发性能，以扩展到具有大量事件的痕迹。此项目着重于离线动态分析，其中检查了程序的存储痕迹。这些痕迹通常非常大，以确保痕量练习生产规模软件的大部分。因此，为了最大程度地减少存储需求，这些迹线被压缩。该项目开发了直接分析此类压缩迹线的算法，而无需首先取消压缩迹线然后进行分析。这样的算法将被证明很快，因为它们会在压缩痕迹大小的及时运行。该项目开发了调查人员在代码分会的当地女孩的外展活动中使用的教学材料，并将在全国范围内的教师论坛上提供。该奖项反映了NSF的法定任务，并被认为是值得通过基金会的知识分子优点和更广泛影响的审查标准通过评估来获得支持的。

项目成果

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