基于不可满足核的近似逼近可达性分析
作者:
作者单位:

作者简介:

于忠祺(1997-),男,硕士生,主要研究领域为形式化验证,模型检测;李建文(1987-),男,博士,研究员,博士生导师,CCF专业会员,主要研究领域为形式化方法,软硬件安全;张小禹(1997-),男,博士生,CCF学生会员,主要研究领域为形式化方法,模型检测算法.

通讯作者:

李建文,E-mail:jwli@sei.ecnu.edu.cn

中图分类号:

基金项目:

国家自然科学基金(62002118,U21B2015);上海市浦江人才计划(19511103602);上海市可信工业互联网软件协同创新中心(2021-2025)


UC-based Approximate Incremental Reachability
Author:
Affiliation:

Fund Project:

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

    近年来,形式化验证技术受到了越来越多的关注,它在保障安全关键领域系统的安全性和正确性方面发挥着重要的作用.模型检测作为形式化验证中自动化程度较高的分支,具有十分广阔的发展前景.研究并提出了一种新的模型检测技术,可以有效地对迁移系统进行模型检测,包括不安全性检测和证明安全性.与现有的模型检测算法不同,提出的基于不可满足核(unsatisfied core,UC)的近似逼近可达性分析(UC-based approximate incremental reachability,UAIR),主要利用不可满足核来求解一系列的候选安全不变式,直至生成最终的不变式,以此来实现安全性证明和不安全性检测(漏洞查找).在基于SAT求解器的符号模型检测中,使用由可满足性求解器得到的UC构造候选安全不变式,如果迁移系统本身是安全的,得到的初始不变式只是安全不变式的一个近似.然后,在检查安全性的同时,逐步改进候选安全不变式,直到找到一个真正的不变式,证明系统是安全的;如果系统是不安全的,该方法最终可以找到一个反例证明系统是不安全的.作为一种全新的方法,利用不可满足核进行安全性模型检测,取得了相当好的效果.众所周知,模型检测领域没有绝对最好的方法,尽管该方法在基准的可解数量上无法超越当前的成熟方法,例如IC3,CAR等,但是该方法可以解出3个其他方法都无法解出的案例,相信本方法可以作为模型检测工具集很有价值的补充.

    Abstract:

    In recent years, formal verification technology has received more and more attention, and it plays an important role in ensuring the safety and correctness of systems in critical areas of safety. As a branch of formal verification with a high degree of automation, model checking has a very broad development prospect. This work studies and proposes a new model checking technique, which can effectively check transition systems, including bug-finding and safety proof. Different from existing model checking algorithms, the proposed method, unsatisfied core (UC)-based approximate incremental reachability (UAIR), mainly utilizes the unsatisfied core to solve a series of candidate safety invariants until the final invariant is generated, so as to realize safety proof and bug-finding. In symbolic model checking based on the SAT solver, the UC obtained by the satisfiability solver is used to construct candidate safety invariant, and if the transition system itself is safe, the initial invariant obtained is only an approximation of the safety invariant. Then, while checking the safety, the candidate safety invariant is gradually improved until a real invariant is found that proves the system is safe; if the system is unsafe, the proposed method can finally find a counterexample to prove the system is unsafe. As a brand new method, UCs are exploited for safety model checking and sound results are achieved. As it is all known, there is no absolute best method in the field of model checking, although the proposed method cannot surpass the current mature methods such as IC3, CAR, etc., the method in this paper can solve 3 cases that other mature methods are unable to solve, it is believed that this method can be a valuable addition to the model checking toolset.

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

于忠祺,张小禹,李建文.基于不可满足核的近似逼近可达性分析.软件学报,2023,34(8):3467-3484

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

京公网安备 11040202500063号