EAGER:Theories and Tools for Safe Concurrent Data Structures
EAGER:安全并发数据结构的理论和工具
基本信息
- 批准号:1153558
- 负责人:
- 金额:$ 20万
- 依托单位:
- 依托单位国家:美国
- 项目类别:Standard Grant
- 财政年份:2011
- 资助国家:美国
- 起止时间:2011-09-01 至 2015-08-31
- 项目状态:已结题
- 来源:
- 关键词:
项目摘要
Existing techniques for reasoning about the behavior and correctness of software running on multi-processor computers assume that each location in the shared memory always has a single, unique value as observed by the processors. But, on modern computer systems, this assumption is false---programs executing on different processors may simultaneously observe different values for some locations in memory. As a consequence, when applied to some important classes of programs, existing reasoning techniques may falsely assert that an incorrect program is in fact correct, thus potentially leading to runtime errors or even security breaches. The goal of this research project is to develop foundational theories and automatic, practical tools for program reasoning that are correct for such modern multi-processor computer systems.The theory consists of a Hoare-style program logic, which deeply incorporates the specifics of the x86 memory model, and which can be used to give rigorous, high-level proofs of partial correctness properties of C-like, multi-threaded programs. The logic is inspired by separation logic, and embodies a x86-specific principle of local reasoning, which allows specifications and proofs to be restricted to just those resources used at runtime, instead of the global system state. The project additionally includes program checkers based on this logic, for automatically constructing proofs of partially-specified programs. Using these tools, the project intends to target, in particular, concurrent data structures: concurrent, and typically race-prone implementations of traditional sequential data structures, which carefully omit locks and other synchronization instructions to maximize concurrent throughput.
用于推理在多处理器计算机上运行的软件的行为和正确性的现有技术假定共享存储器中的每个位置总是具有如由处理器观察到的单个唯一值。但是,在现代计算机系统中,这种假设是错误的-在不同处理器上执行的程序可能同时观察到内存中某些位置的不同值。因此,当应用于一些重要的程序类别时,现有的推理技术可能错误地断言不正确的程序实际上是正确的,从而潜在地导致运行时错误甚至安全漏洞。本研究课题的目标是开发适用于现代多处理器计算机系统的程序推理的基础理论和自动实用工具。该理论由Hoare风格的程序逻辑组成,该逻辑深入融合了x86内存模型的细节,可用于对类似C的多线程程序的部分正确性进行严格的高级证明。该逻辑受到分离逻辑的启发,并体现了x86特定的局部推理原则,该原则允许规范和证明仅限于运行时使用的资源,而不是全局系统状态。该项目还包括基于此逻辑的程序检查器,用于自动构建部分指定程序的证明。使用这些工具,该项目旨在特别针对并发数据结构:传统顺序数据结构的并发且通常易于竞争的实现,这些实现小心地省略锁和其他同步指令以最大化并发吞吐量。
项目成果
期刊论文数量(0)
专著数量(0)
科研奖励数量(0)
会议论文数量(0)
专利数量(0)
数据更新时间:{{ journalArticles.updateTime }}
{{
item.title }}
{{ item.translation_title }}
- DOI:
{{ item.doi }} - 发表时间:
{{ item.publish_year }} - 期刊:
- 影响因子:{{ item.factor }}
- 作者:
{{ item.authors }} - 通讯作者:
{{ item.author }}
数据更新时间:{{ journalArticles.updateTime }}
{{ item.title }}
- 作者:
{{ item.author }}
数据更新时间:{{ monograph.updateTime }}
{{ item.title }}
- 作者:
{{ item.author }}
数据更新时间:{{ sciAawards.updateTime }}
{{ item.title }}
- 作者:
{{ item.author }}
数据更新时间:{{ conferencePapers.updateTime }}
{{ item.title }}
- 作者:
{{ item.author }}
数据更新时间:{{ patent.updateTime }}
Warren Hunt, Jr.其他文献
Warren Hunt, Jr.的其他文献
{{
item.title }}
{{ item.translation_title }}
- DOI:
{{ item.doi }} - 发表时间:
{{ item.publish_year }} - 期刊:
- 影响因子:{{ item.factor }}
- 作者:
{{ item.authors }} - 通讯作者:
{{ item.author }}
{{ truncateString('Warren Hunt, Jr.', 18)}}的其他基金
Student Travel Support for the FMCAD Student Forum 2017;Vienna, Austria; October, 2017
2017 年 FMCAD 学生论坛的学生旅行支持;奥地利维也纳;
- 批准号:
1743689 - 财政年份:2017
- 资助金额:
$ 20万 - 项目类别:
Standard Grant
TWC: Small: Memory Analysis and Machine-Code Verification Techniques for Multiprocessor Systems
TWC:小型:多处理器系统的内存分析和机器代码验证技术
- 批准号:
1525472 - 财政年份:2015
- 资助金额:
$ 20万 - 项目类别:
Standard Grant
TC: Large: A Formal Platform for Analyzing Internet Routing
TC:大型:分析互联网路由的正式平台
- 批准号:
0910913 - 财政年份:2009
- 资助金额:
$ 20万 - 项目类别:
Standard Grant
TC: Small: Collaborative Research: Trustworthy Hardware from Certified Behavioral Synthesis
TC:小型:协作研究:来自经过认证的行为综合的值得信赖的硬件
- 批准号:
0916772 - 财政年份:2009
- 资助金额:
$ 20万 - 项目类别:
Continuing Grant
相似海外基金
Modelling ecological dynamics in changing environments: novel theories, policy suggestions and operational tools for mitigating the impact of anthropogenic disturbances.
模拟不断变化的环境中的生态动态:减轻人为干扰影响的新颖理论、政策建议和操作工具。
- 批准号:
DGECR-2022-00454 - 财政年份:2022
- 资助金额:
$ 20万 - 项目类别:
Discovery Launch Supplement
Modelling ecological dynamics in changing environments: novel theories, policy suggestions and operational tools for mitigating the impact of anthropogenic disturbances.
模拟不断变化的环境中的生态动态:减轻人为干扰影响的新颖理论、政策建议和操作工具。
- 批准号:
RGPIN-2022-04559 - 财政年份:2022
- 资助金额:
$ 20万 - 项目类别:
Discovery Grants Program - Individual
Theories and Tools for Sustainable Programming
可持续规划的理论和工具
- 批准号:
RGPIN-2017-06692 - 财政年份:2021
- 资助金额:
$ 20万 - 项目类别:
Discovery Grants Program - Individual
Theories and tools for the verification of complex distributed systems
复杂分布式系统验证的理论和工具
- 批准号:
2891068 - 财政年份:2020
- 资助金额:
$ 20万 - 项目类别:
Studentship
Theories and Tools for Sustainable Programming
可持续规划的理论和工具
- 批准号:
RGPIN-2017-06692 - 财政年份:2020
- 资助金额:
$ 20万 - 项目类别:
Discovery Grants Program - Individual
Opening the system to the environment: new theories and tools in classical and quantum settings
向环境开放系统:经典和量子环境中的新理论和工具
- 批准号:
2241267 - 财政年份:2019
- 资助金额:
$ 20万 - 项目类别:
Studentship
Theories and Tools for Sustainable Programming
可持续规划的理论和工具
- 批准号:
RGPIN-2017-06692 - 财政年份:2019
- 资助金额:
$ 20万 - 项目类别:
Discovery Grants Program - Individual
Theories and Tools for Sustainable Programming
可持续规划的理论和工具
- 批准号:
RGPIN-2017-06692 - 财政年份:2018
- 资助金额:
$ 20万 - 项目类别:
Discovery Grants Program - Individual
Theories and Tools for Sustainable Programming
可持续规划的理论和工具
- 批准号:
RGPIN-2017-06692 - 财政年份:2017
- 资助金额:
$ 20万 - 项目类别:
Discovery Grants Program - Individual
Theories, techniques and tools for engineering
工程理论、技术和工具
- 批准号:
2513782 - 财政年份:2016
- 资助金额:
$ 20万 - 项目类别:
Studentship