EAGER:Theories and Tools for Safe Concurrent Data Structures
EAGER:Theories and Tools for Safe Concurrent Data Structures
批准号:
1153558
负责人:
Warren Hunt, Jr.
金额:
$20.0万
依托单位国家:
美国
项目类别:
Standard Grant
财政年份:
2011
资助国家:
美国
项目状态:
已结题
起止时间:
2011-09-01 至 2015-08-31
中文摘要
现有的对运行在多处理器计算机上的软件的行为和正确性进行推理的技术假设,共享内存中的每个位置总是有一个处理器观察到的唯一值。但是,在现代计算机系统中,这种假设是错误的——在不同处理器上执行的程序可能同时在内存中的某些位置观察到不同的值。因此,当应用于某些重要的程序类时,现有的推理技术可能错误地断言不正确的程序实际上是正确的,从而可能导致运行时错误甚至安全漏洞。这个研究项目的目标是发展基础理论和自动的、实用的程序推理工具,这些工具是正确的,适用于这种现代多处理器计算机系统。该理论由hoare风格的程序逻辑组成,它深入地结合了x86内存模型的特点,并且可以用来对类c多线程程序的部分正确性属性给出严格的、高级的证明。该逻辑受到分离逻辑的启发,并体现了特定于x86的局部推理原则,该原则允许将规范和证明限制在运行时使用的那些资源,而不是全局系统状态。该项目还包括基于此逻辑的程序检查器,用于自动构造部分指定程序的证明。使用这些工具,该项目打算特别针对并发数据结构:传统顺序数据结构的并发且通常容易出现竞争的实现,这些实现小心地忽略了锁和其他同步指令,以最大限度地提高并发吞吐量。
英文摘要
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.
期刊论文(0)
专著(0)
科研奖励(0)
会议论文
Student Travel Support for the FMCAD Student Forum 2017;Vienna, Austria; October, 2017
-
批准号:1743689
-
项目类别:Standard Grant
-
资助金额:$1.0万
-
财政年份:2017
-
负责人:Warren Hunt, Jr.
-
依托单位:
TWC: Small: Memory Analysis and Machine-Code Verification Techniques for Multiprocessor Systems
-
批准号:1525472
-
项目类别:Standard Grant
-
资助金额:$50.0万
-
财政年份:2015
-
负责人:Warren Hunt, Jr.
-
依托单位:
TC: Large: A Formal Platform for Analyzing Internet Routing
-
批准号:0910913
-
项目类别:Standard Grant
-
资助金额:$79.99万
-
财政年份:2009
-
负责人:Warren Hunt, Jr.
-
依托单位:
TC: Small: Collaborative Research: Trustworthy Hardware from Certified Behavioral Synthesis
-
批准号:0916772
-
项目类别:Continuing Grant
-
资助金额:$25.0万
-
财政年份:2009
-
负责人:Warren Hunt, Jr.
-
依托单位:
Trusted Certification Tools
-
批准号:0429591
-
项目类别:Standard Grant
-
资助金额:$0.0万
-
财政年份:2005
-
负责人:Warren Hunt, Jr.
-
依托单位:
海外基金