Collaborative Research: FMitF: Track I: Formally Verified Numerical Methods
Collaborative Research: FMitF: Track I: Formally Verified Numerical Methods
批准号:
2219757
负责人:
Andrew Appel
金额:
$55.95万
依托单位:
依托单位国家:
美国
项目类别:
Standard Grant
财政年份:
2022
资助国家:
美国
项目状态:
未结题
起止时间:
2022-10-01 至 2025-09-30
中文摘要
当计算机算法计算物理系统——行星、自动驾驶汽车、火箭、wi-fi天线、药物——的行为时,有些数学方程无法精确求解。因此,算法可以根据需要精确地逼近答案。数值分析是计算这些算法的精确度的科学。在某种类型的计算中,需要的精度越高,计算答案所需的时间就越长。当一个人绝对需要事先知道答案的精确程度时,传统的数值方法很难结合成一个完整可信的解决方案。这个项目的新颖之处在于:(1)将所有关于数值软件的推理集成到一个单一的系统中,(2)将所有层次的推理连接起来,从数学到软件代码,产生端到端的正确性和准确性保证,(3)以数学定理的形式产生这种保证,其证明可以完全自动检查。该项目更广泛的意义和重要性是科学的和经济的:开发的新方法和工具可以(1)防止用传统方法诊断极其昂贵的软件缺陷;(2)允许使用更快的算法(当人们现在可以证明它们是准确的);(3)确保控制软件在飞机和车辆控制等安全关键应用中的安全性。该项目采用分层方法对数值软件的正确性和准确性进行基础验证——也就是说,对程序(不仅仅是算法)进行正式的机器检查证明,除了指令集架构的规范外,没有任何假设。研究人员在每一层建立、改进和使用适当的工具:用实数证明离散算法;证明浮点算法如何逼近实数算法;浮点算法的C程序实现推理;并在Coq校对助手中将所有校对端到端连接起来。该奖项反映了美国国家科学基金会的法定使命,并通过使用基金会的知识价值和更广泛的影响审查标准进行评估,被认为值得支持。
英文摘要
When computer algorithms calculate the behavior of physical systems -- planets, self-driving cars, rockets, wi-fi antennas, medicines – some of the mathematical equations can't be solved exactly. Thus, the algorithms approximate the answers as precisely as needed. Numerical analysis is the science of calculating how accurate these algorithms are. The more precision is needed in a certain type of computation, the more time it takes to compute the answer. When one absolutely needs to know in advance how accurate the answers will be, traditional numerical methods are hard to combine into a complete and trustworthy solution. This project's novelties are (1) to integrate all the reasoning about numerical software into a single system, (2) to connect all the levels of reasoning, from mathematics down to software code, producing an end-to-end guarantee of correctness and accuracy, and (3) to produce that guarantee in the form of a mathematical theorem whose proof can be checked fully automatically. The project's broader significance and importance are both scientific and economic: the novel methods and tools developed can (1) prevent software bugs that can be extremely expensive to diagnose by conventional means; (2) allow faster algorithms to be used (when one can now prove that they are accurate); and (3) assure the safety of control software in safety-critical applications such as aircraft and vehicle control.The project takes a layered approach to foundational verification of correctness and accuracy of numerical software---that is, formal machine-checked proofs about programs (not just algorithms), with no assumptions except specifications of instruction-set architectures. The researchers build, improve, and use appropriate tools at each layer: proving in the real numbers about discrete algorithms; proving how floating-point algorithms approximate real-number algorithms; reasoning about C program implementation of floating-point algorithms; and connecting all proofs end-to-end in the Coq proof assistant.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.
期刊论文(1)
专著(0)
科研奖励(0)
会议论文
VSTlib: Library Components for Verified C Programs
VSTlib:经过验证的 C 程序的库组件
DOI:
--
发表时间:
2023
期刊:
Coq Workshop
影响因子:
--
作者:
[Andrew W. Appel]
通讯作者:
Andrew W. Appel
SHF: Small: VeriFFI -- Formally Verified Functional+C programs
-
批准号:2005545
-
项目类别:Standard Grant
-
资助金额:$50.0万
-
财政年份:2020
-
负责人:Andrew Appel
-
依托单位:
Collaborative Research: Expeditions in Computing: The Science of Deep Specification
-
批准号:1521602
-
项目类别:Continuing Grant
-
资助金额:$345.34万
-
财政年份:2015
-
负责人:Andrew Appel
-
依托单位:
SHF: Medium: Collaborative Research: Principled Optimizing Compilation of Dependently Typed Languages
-
批准号:1407794
-
项目类别:Standard Grant
-
资助金额:$60.0万
-
财政年份:2014
-
负责人:Andrew Appel
-
依托单位:
TC: Large:Collaborative Research: Combining Foundational and Lightweight Formal Methods to Build Certifiably Dependable Software
-
批准号:0910448
-
项目类别:Standard Grant
-
资助金额:$50.0万
-
财政年份:2009
-
负责人:Andrew Appel
-
依托单位:
End-to-end source-to-object verification of interface safety
-
批准号:0540914
-
项目类别:Standard Grant
-
资助金额:$32.5万
-
财政年份:2006
-
负责人:Andrew Appel
-
依托单位:
Collaborative Research: High-Assurance Common Language Runtime
-
批准号:0208601
-
项目类别:Continuing Grant
-
资助金额:$40.0万
-
财政年份:2002
-
负责人:Andrew Appel
-
依托单位:
Applying Compiler Techniques to Proof-Carrying Code
-
批准号:9974553
-
项目类别:Standard Grant
-
资助金额:$22.0万
-
财政年份:1999
-
负责人:Andrew Appel
-
依托单位:
Framework, Algorithms, and Applications for Cross-Module Inlining
-
批准号:9625413
-
项目类别:Standard Grant
-
资助金额:$18.03万
-
财政年份:1996
-
负责人:Andrew Appel
-
依托单位:
Optimization of Space Usage
-
批准号:9200790
-
项目类别:Continuing Grant
-
资助金额:$34.81万
-
财政年份:1992
-
负责人:Andrew Appel
-
依托单位:
Standard ML of New Jersey Software Capitalization
-
批准号:8914570
-
项目类别:Standard Grant
-
资助金额:$11.95万
-
财政年份:1990
-
负责人:Andrew Appel
-
依托单位:
Using Immutable Types for Debugging and Parallelism
-
批准号:9002786
-
项目类别:Standard Grant
-
资助金额:$17.46万
-
财政年份:1990
-
负责人:Andrew Appel
-
依托单位:
Unifying Compile-Time and Run-Time Evaluation
-
批准号:8806121
-
项目类别:Continuing Grant
-
资助金额:$12.35万
-
财政年份:1988
-
负责人:Andrew Appel
-
依托单位:
Implementation of an Efficient Reducer for Lambda Expressions
-
批准号:8603453
-
项目类别:Standard Grant
-
资助金额:$11.58万
-
财政年份:1986
-
负责人:Andrew Appel
-
依托单位:
国内基金
海外基金
登录
查看更多内容
Research on Quantum Field Theory without a Lagrangian Description
-
批准号:24ZR1403900
-
项目类别:省市级项目
-
资助金额:--
-
批准年份:2024
-
负责人:SATOSHI NAWATA
-
依托单位:
Cell Research
-
批准号:31224802
-
项目类别:专项基金项目
-
资助金额:24.0万元
-
批准年份:2012
-
负责人:程磊
-
依托单位:
Cell Research
-
批准号:31024804
-
项目类别:专项基金项目
-
资助金额:24.0万元
-
批准年份:2010
-
负责人:程磊
-
依托单位:
Cell Research (细胞研究)
-
批准号:30824808
-
项目类别:专项基金项目
-
资助金额:24.0万元
-
批准年份:2008
-
负责人:张爱兰
-
依托单位:
Research on the Rapid Growth Mechanism of KDP Crystal
-
批准号:10774081
-
项目类别:面上项目
-
资助金额:45.0万元
-
批准年份:2007
-
负责人:滕冰
-
依托单位: