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

形式化验证

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

(图片仅供参考)

正式的 确认 形式验证是指运用数学方法来证明或反驳系统设计相对于形式化规范的正确性。与只能针对特定输入检测缺陷的测试不同,形式验证可以证明所有可能的输入下均不存在缺陷。它涉及创建系统的形式化模型,并使用模型检测或定理证明等技术。

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

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

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

UNESCO Nomenclature: 1203
- 计算机科学

类型

软件/算法

中断

基础

用法

小众/专业

前体

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

应用程序

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

专利:

NA

潜在创新理念

由于机器人流量被拦截(目前每天超过 4 万),此内容仅限社区成员查看。
> 登录 > 或者 > 注册 < (100% 免费)即可访问此内容,以及所有其他受限内容和工具。

相关领域:形式化验证、模型检测、定理证明、形式化方法、正确性、软件验证、硬件验证、时序逻辑。

历史背景

形式化验证

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

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

相关发明、创新和技术原理

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

> 登录 <