基于SMT求解器的路径敏感程序验证
作者:
作者单位:

作者简介:

通讯作者:

中图分类号:

基金项目:

国家自然科学基金(90818018, 91018009)


Path Sensitive Program Verification Based on SMT Solvers
Author:
Affiliation:

Fund Project:

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

    随着软件规模的不断扩大以及复杂度的不断增长,人们越来越关注软件的可信性问题.验证程序是否满足断言所描述的性质,是保证软件可信性的一种常见方法.路径敏感的程序验证由于不可能遍历所有的路径,需要合并路径信息,因此造成精度上的损失.提出一种基于 SMT 求解器的路径敏感程序验证方法,在保证精确度的前提下,有效减少路径搜索空间.其基本思想是,利用最大强连通分量压缩循环路径,然后根据目标断言对控制流图进行切片.使用一种布尔表达式方法对路径空间进行抽象,结合抽象解释和符号执行技术对路径进行验证.结合 F-Soft 平台和 Z3 工具对该方法进行了实验验证,结果表明,该方法在验证的精确度和效率上都有较好的效果.

    Abstract:

    With the rapid increase in size and complexity of software, more and more attention is paid to thesoftware’s trust. Verifying whether programs satisfy the properties described by assertions is a common method toguarantee trust of the software. Since path sensitive program verification cannot traverse all paths, it needs mergethe path information, which causes a loss of precision. The study proposes a program verification method usingSMT solvers, which can reduce the path search space and improve the precision at the same time. The method’smain sprit is impacting the cycle path by using maximal strongly connected component and slicing the CFGaccording to the aim assertion. The study abstracts the path space using Boolean formulas and verifies the path bycombining abstract interpretation and symbolic execution. The study has conducted experiments based on the F-Softprogram verification platform and SMT solver Z3, and results show that this method performs well based onprecision and effect.

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

何炎祥,吴伟,陈勇,徐超.基于SMT求解器的路径敏感程序验证.软件学报,2012,23(10):2655-2664

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

京公网安备 11040202500063号