反例引导的C代码空间流模型检测方法
作者:
作者简介:

于银菠(1991-),男,博士,副教授,CCF专业会员,主要研究领域为软件与系统安全,物联网安全,深度学习安全;慕德俊(1963-),男,博士,教授,博士生导师,主要研究领域为硬件安全,机器学习,数据挖掘;刘家佳(1984-),男,博士,教授,博士生导师,主要研究领域为网络安全,智能通信

通讯作者:

刘家佳,E-mail:liujiajia@nwpu.edu.cn

中图分类号:

TP311

基金项目:

广东省基础与应用基础研究基金(2021A1515110279);太仓市基础研究计划(TC2020JC03);中央高校基本科研业务费专项资金(D5000210588)


Counterexample-guided Spatial Flow Model Checking Methods for C Codes
Author:
  • 摘要
  • | |
  • 访问统计
  • |
  • 参考文献 [36]
  • |
  • 相似文献 [20]
  • | | |
  • 文章评论
    摘要:

    软件验证一直是确保软件正确性和安全性的热点研究问题.然而,由于程序语言复杂的语法语义特性,应用形式化方法验证程序的正确性存在准确度低和效率差的问题.其中,由指针操作带来的地址空间的状态变化使得现有模型检测方法的检测准确度难以得到保证.为此,通过结合模型检测与稀疏值流分析方法,设计了一种空间流模型,实现了对C程序在符号变量层面和地址空间层面的状态行为的有效描述,并提出了一种反例引导的抽象细化和稀疏值流强更新算法(CEGAS),实现了C程序指向信息敏感的形式化验证.建立了包含多种指针操作的C代码基准库,并基于该基准库进行了对比实验.实验结果表明:所提出的模型检测算法CEGAS在分析含有多种C代码特性的任务中,与现有模型检测工具相比均能取得突出的结果,其检测准确度为92.9%,每行代码的平均检测时间为2.58 ms,优于现有检测工具.

    Abstract:

    Software verification has always been a hot research topic to ensure the correctness and security of software. However, due to the complex semantics and syntax of programming language, applying formal methods to verify the correctness of programs has the problems of low accuracy and low efficiency. Among them, the state change of address space caused by pointer operations makes the verification accuracy of existing model checking methods difficult to be guaranteed. By combining model checking and sparse value-flow analysis, this study designs a spatial flow model to effectively describe the state behavior of C codes at the symbolic variable level and address space level, and proposes a model checking algorithm of counterexample-guided abstraction refinement and sparse value flow strong update (CEGAS), which enables points-to-sensitive formal verification for C codes. This study establishes a C code benchmark containing a variety of pointer operationsand conducts comparative experiments based on this benchmark. These experiments indicate that in the task of analyzing multi-class C code features, the model checking algorithm CEGAS proposed in this study can achieve outstanding results compared with the existing model detection tools. The verification accuracy of CEGAS is 92.9%, and the average verification time of each line of code is 2.58 ms, which are both better than existing testing tools.

    参考文献
    [1] D'silva V, Kroening D, Weissenbacher G. A survey of automated techniques for formal software verification. IEEE Trans. on Computer-aided Design of Integrated Circuits and Systems, 2008, 27(7):1165-1178.[doi:10.1109/TCAD.2008.923410]
    [2] Clarke E, Grumberg O, Jha S, Lu Y, Veith H. Counterexample-guided abstraction refinement for symbolic model checking. Journal of the ACM (JACM), 2003, 50(5):752-794.[doi:10.1145/876638.876643]
    [3] Baldoni R, Coppa E, D'elia DC, Demetrescu C, Finocchi I. A survey of symbolic execution techniques. ACM Computing Surveys (CSUR), 2018, 51(3):1-39.[doi:10.1145/3182657]
    [4] Clarke EM, Henzinger TA, Veith H, Bloem R. Handbook of Model Checking. Cham:Springer, 2018.
    [5] Kalra S, Goel S, Dhawan M, Sharma S. Zeus:Analyzing safety of smart contracts. In:Proc. of the Symp. on Network and Distributed Systems Security (NDSS). 2018. 1-12.[doi:10.14722/ndss.2018.23082]
    [6] Yu Y, Li Y, Hou K, Chen Y, Zhou H, Yang J. CellScope:Automatically specifying and verifying cellular network protocols. In:Proc. of the ACM SIGCOMM 2019 Conf. on Posters and Demos. 2019. 21-23.[doi:10.1145/3342280.3342294]
    [7] Chaki S, Datta A. ASPIER:An automated framework for verifying security protocol implementations. In:Proc. of the 22nd IEEE Computer Security Foundations Symp. IEEE, 2009. 172-185.[doi:10.1109/CSF.2009.20]
    [8] Zhang XL, Zhu YF, Gu CX, Chen X. C2P:Formal abstraction method and tool for C protocol code based on Pi caculus. Ruan Jian Xue Bao/Journal of Software, 2021, 32(6):1581-1596(in Chinese with English abstract). http://www.jos.org.cn/1000-9825/6238. htm[doi:10.13328/j.cnki.jos.006238]
    [9] Beyer D, Keremoglu ME. CPAchecker:A tool for configurable software verification. In:Proc. of the Int'l Conf. on Computer Aided Verification (CAV). Berlin, Heidelberg:Springer, 2011. 184-190.[doi:10.1007/978-3-642-22110-1_16]
    [10] Holzmann GJ. Software model checking with SPIN. Advances in Computers, 2005, 65:77-108.[doi:10.1016/S0065-2458(05)65002-4]
    [11] Ádám Z, Sallai G, HajduÁ. Gazer-Theta:LLVM-based verifier portfolio with BMC/CEGAR. In:Proc. of the Int'l Conf. on Tools and Algorithms for the Construction and Analysis of Systems (TACAS). 2021. 433-437.
    [12] Henzinger TA, Jhala R, Majumdar R, Sutre G. Lazy abstraction. In:Proc. of the 29th ACM SIGPLAN-SIGACT Symp. on Principles of Programming Languages (POPL). 2022. 58-70.[doi:10.1145/565816.503279]
    [13] Henzinger TA, Jhala R, Majumdar R, McMillan KL. Abstractions from proofs. In:Proc. of the 31st ACM SIGPLAN-SIGACT Symp. on Principles of Programming Languages (POPL). 2004. 232-244.[doi:10.1145/982962.964021]
    [14] Andersen LO. Program analysis and specialization for the C programming language[Ph.D. Thesis]. DIKU:University of Copenhagen, 1994.
    [15] Beyer D, Dangl M, Wendler P. A unifying view on SMT-based software verification. Journal of Automed Reasoning, 2018, 60(3):299-335.[doi:10.1007/s10817-017-9432-6]
    [16] Musuvathi M, Park DYW, Chou A, Engler DR, Dill DL. CMC:A pragmatic approach to model checking real code. In:Proc. of the Operating Systems Design and Implementation (OSDI). 2002. 75-88.[doi:10.1145/844128.844136]
    [17] Havelund VK, Brat G, Park S, Lerda F. Model checking programs. Automted Software Engineering (ASE), 2003, 10(2):203-232.[doi:10.1023/A:1022920129859]
    [18] Rakamarić Z, Emmi M. SMACK:Decoupling source language details from verifier implementations. In:Proc. of the Int'l Conf. on Computer Aided Verification (CAV). Cham:Springer, 2014. 106-113.[doi:10.1007/978-3-319-08867-9_7]
    [19] Clarke EM, Kroening D, Lerda F. A tool for checking ANSI-C programs. In:Proc. of the Int'l Conf. on Tools and Algorithms for the Construction and Analysis of Systems. LNCS 2988, Springer, 2004. 168-176.[doi:10.1007/978-3-540-24730-2_15]
    [20] Gadelha MR, Monteiro F, Cordeiro L, et al. ESBMC v6.0:Verifying C programs using k-induction and invariant inference. In:Proc. of the Int'l Conf. on Tools and Algorithms for the Construction and Analysis of Systems. Cham:Springer, 2019. 209-213.
    [21] Ball T, Levin V, Rajamani SK. A decade of software model checking with SLAM. Communication of ACM, 2011, 54(7):68-76.
    [22] Tóth T, HajduÁ, Vörös A, et al. Theta:A framework for abstraction refinement-based model checking. In:Proc. of the 2017 Formal Methods in Computer Aided Design (FMCAD). IEEE, 2017. 176-179.[doi:10.23919/FMCAD.2017.8102257]
    [23] Steensgaard B. Points-to analysis in almost linear time. In:Proc. of the Annual ACM SIGPLAN-SIGACT Symp. on Principles of Programming Languages (POPL). 1996. 32-41.[doi:10.1145/237721.237727]
    [24] Oh H, Heo K, Lee W, Lee W, Yi K. Design and implementation of sparse global analyses for C-like languages. In:Proc. of the 33th ACM SIGPLAN Conf. on Programming Language Design and Implementation (PLDI). 2012. 229-238.[doi:10.1145/1273442. 1250789]
    [25] Sui Y, Xue J. Value-flow-based demand-driven pointer analysis for C and C++. IEEE Trans. on Software Engineering, 2018, 46(8):812-835.[doi:10.1109/TSE.2018.2869336]
    [26] Cherem S, Princehouse L, Rugina R. Practical memory leak detection using guarded value-flow analysis. In:Proc. of the 28th ACM SIGPLAN Conf. on Programming Language Design and Implementation (PLDI). ACM, 2007. 480-491.
    [27] Shi Q, Xiao X, Wu R, et al. Pinpoint:Fast and precise sparse value flow analysis for million lines of code. In:Proc. of the 39th ACM SIGPLAN Conf. on Programming Language Design and Implementation (PLDI). 2018. 693-706.[doi:10.1145/3192366. 3192418]
    [28] Shi Q, Yao P, Wu R, et al. Path-sensitive sparse analysis without path conditions. In:Proc. of the 42nd ACM SIGPLAN Int'l Conf. on Programming Language Design and Implementation (PLDI). 2021. 930-943.[doi:10.1145/3453483.3454086]
    [29] Beyer D, Löwe S. Explicit-state software model checking based on CEGAR and interpolation. In:Proc. of the Int'l Conf. on Fundamental Approaches to Software Engineering (FASE). Berlin, Heidelberg:Springer, 2013. 146-162.[doi:10.1007/978-3-642-37057-1_11]
    [30] Sui Y, Xue J. SVF:Interprocedural static value-flow analysis in LLVM. In:Proc. of the 25th ACM Int'l Conf. on Compiler Construction (CC). 2016. 265-266.[doi:10.1145/2892208.2892235]
    [31] Lattner C, Adve V. LLVM:A compilation framework Forlifelong program analysis& transformation. In:Proc. of the Int'l Symp. on Code Generation and Optimization (CGO). 2004. 75-86.[doi:10.1109/CGO.2004.1281665]
    [32] de Moura LM, Bjørner N. Z3:An efficient SMT solver. In:Proc. of the Int'l Conf. on Tools and Algorithms for the Construction and Analysis of Systems (TACAS). 2008. 337-340.[doi:10.1007/978-3-540-78800-3_24]
    [33] Int'l competition on software verification (SV-COMP). http://sv-comp.sosy-lab.org
    [34] Lattner C, Lenharth A, Adve V. Making context-sensitive points-to analysis with heap cloning practical for the real world. In:Proc. of the ACM SIGPLAN Conf. on Programming Language Design and Implementation (PLDI). 2007, 42(6):278-289.[doi:10.1145/1273442.1250766]
    [35] De Line R, Leino KRM. BoogiePL:A typed procedural language for check-ing object-oriented programs. Technical Report, MSR-TR-2005-70, Microsoft Research, 2005.
    附中文参考文献:
    [8] 张协力,祝跃飞,顾纯祥,陈熹. C2P:基于Pi演算的协议C代码形式化抽象方法和工具.软件学报, 2021, 32(6):1581-1596. http://www.jos.org.cn/1000-9825/6238.htm[doi:10.13328/j.cnki.jos.006238]
    引证文献
    网友评论
    网友评论
    分享到微博
    发 布
引用本文

于银菠,刘家佳,慕德俊.反例引导的C代码空间流模型检测方法.软件学报,2022,33(6):1961-1977

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

京公网安备 11040202500063号