Product Design, Manufacturing & Innovation Resources
家 » 形式化验证

形式化验证

1980
  • Edmund M. Clarke
  • E. Allen Emerson
  • Joseph Sifakis
计算机科学工程师在办公室审查形式验证模型。

(图片仅供参考)

Formal verification is the use of mathematical methods to prove or disprove the correctness of a system’s design with respect to a formal specification. Unlike testing, which can only show the presence of bugs for specific inputs, formal verification can prove their absence for all possible inputs. It involves creating a formal model of the system and using techniques like model checking or theorem proving.

形式化验证为系统正确性提供了最高级别的保证。该过程首先使用数学语言(例如时序逻辑或进程代数)创建系统的形式化模型。一组源自系统需求的属性也用形式化语言表达出来。然后,验证过程使用自动化工具系统地探索模型的所有可能状态,以确定指定的属性是否成立。

主要采用两种技术:模型检测和定理证明。模型检测是一种自动化技术,它会遍历有限状态模型的整个状态空间。如果某个属性被违反,模型检测器会生成一个反例——一个展示该缺陷的具体执行轨迹。这种方法非常有效,但对于非常复杂的系统,可能会遇到“状态空间爆炸”的问题。定理证明则涉及将系统及其属性表示为逻辑公式(定理),并使用自动化或交互式证明器来构建形式化的正确性证明。这种方法可以处理无限状态系统,但通常需要专家投入大量人工。

虽然形式化验证计算成本高昂且需要专业知识,但对于安全关键型或安保关键型系统而言,由于故障代价极高,形式化验证必不可少。它已成功应用于验证CPU浮点单元、通信协议和控制系统的正确性,而这些系统难以进行详尽的测试。

UNESCO Nomenclature: 1203
- 计算机科学

类型

软件/算法

中断

基础

用法

小众/专业

前体

  • 命题逻辑和谓词逻辑
  • 自动机 理论
  • λ演算
  • 程序语义(例如,霍尔逻辑)
  • 计算复杂性理论

应用程序

  • 微处理器设计(例如,英特尔奔腾处理器 fdiv 错误修复)
  • 航空电子软件(例如,电传操纵系统)
  • 密码协议分析
  • 铁路信号系统
  • 关键操作系统软件驱动程序

专利:

NA

潜在创新理念

  • formal verification of 神经网络 properties (e.g., robustness)
  • automated formal verification of smart contracts on blockchains
  • hybrid approaches combining static analysis, testing, and formal verification
  • user-friendly formal verification tools integrated into development environments
  • formal verification of quantum computing algorithms
  • cloud-based formal verification services for scalable analysis
  • verifying fairness and ethical constraints in ai decision-making systems
  • runtime verification to check formal properties in live systems
相关领域:形式化验证、模型检测、定理证明、形式化方法、正确性、软件验证、硬件验证、时序逻辑。

历史背景

形式化验证

1970
1973
1980
1980
1980
1980
1986-01-01
1970
1970-01-01
1975-06-01
1980
1980
1980
1982-07-01
1988-06-01

(如果日期未知或不相关,例如“流体力学”,则提供其显著出现的近似估计)

第十年 周年纪念日

只有注册会员才能免费获得 100% 的全尺寸图片和下载。.

> 登录 <