基于交互式定理证明的并发程序验证工作综述
作者:
作者单位:

作者简介:

王中烨(1998-), 男, 硕士, 主要研究领域为程序语言, 程序逻辑, 并发程序验证. ;吴姝姝(1999-), 女, 博士, CCF学生会员, 主要研究领域为程序语言, 形式化验证, 关系霍尔逻辑. ;曹钦翔(1990-), 男, 博士, 副教授, 博士生导师, CCF专业会员, 主要研究领域为交互式定理证明, 分离逻辑, 程序验证.

通讯作者:

王中烨, E-mail: wangzhongye1110@sjtu.edu.cn

中图分类号:

基金项目:


Survey on Interactive Theorem Proving Based Concurrent Program Verification
Author:
Affiliation:

Fund Project:

  • 摘要
  • |
  • 图/表
  • |
  • 访问统计
  • |
  • 参考文献
  • |
  • 相似文献
  • |
  • 引证文献
  • |
  • 资源附件
  • |
  • 文章评论
    摘要:

    并发程序与并发系统可以拥有非常高的执行效率和相对串行系统较快的响应速度, 在现实中有着非常广泛的应用. 但是并发程序与并发系统往往难以保证其实现的正确性, 实际应用程序运行中的错误会带来严重的后果. 同时, 并发程序执行时的不确定性会给其正确性验证带来巨大的困难. 在形式化验证方法中, 人们可以通过交互式定理证明器严格地对并发程序进行验证. 对在交互式定理证明中可用于描述并发程序正确性的验证目标进行总结, 它们包括霍尔三元组、可线性化、上下文精化和逻辑原子性. 交互式定理证明方法中常用程序逻辑对程序进行验证, 分析基于并发分离逻辑、依赖保证逻辑、关系霍尔逻辑等理论研究的系列成果与相应形式化方案, 并对使用这些方法的程序验证工具和程序验证成果进行总结.

    Abstract:

    Concurrent programs and systems are usually highly efficient and respond faster than serial systems, making them widely used in practice. However, concurrent programs and systems are often prone to error, which could bring fatal consequences in real world applications. Moreover, the non-determinism brought by concurrency is a major difficulty in the verification of concurrent programs. With formal verification, people could use interactive theorem provers to rigorously prove the correctness of a concurrent program. This study presents several correctness criteria for concurrent programs, which can be verified by interactive theorem proof techniques. The criteria include Hoare triple, linearizability, contextual refinement, and logical atomicity. Researchers usually use program logic to verify programs in an interactive theorem prover. This study summarizes the usage of concurrent separation logic, rely-guarantee-based logic, and relational Hoare logic in concurrent program verifications. It also surveys existing foundational verification tools and verification results by these techniques.

    参考文献
    相似文献
    引证文献
引用本文

王中烨,吴姝姝,曹钦翔.基于交互式定理证明的并发程序验证工作综述.软件学报,2024,35(9):4069-4099

复制
分享
文章指标
  • 点击次数:
  • 下载次数:
  • HTML阅读次数:
  • 引用次数:
历史
  • 收稿日期:2023-09-11
  • 最后修改日期:2023-10-30
  • 录用日期:
  • 在线发布日期: 2024-01-05
  • 出版日期:
文章二维码
您是第位访问者
版权所有:中国科学院软件研究所 京ICP备05046678号-3
地址:北京市海淀区中关村南四街4号,邮政编码:100190
电话:010-62562563 传真:010-62562533 Email:jos@iscas.ac.cn
技术支持:北京勤云科技发展有限公司

京公网安备 11040202500063号