微内核操作系统互斥量模块功能正确性的形式化验证
作者:
作者简介:

张林雁(1998-), 女, 硕士生, CCF学生会员, 主要研究领域为形式化方法, 软件验证. ;李希萌(1987-), 男, 博士, 副教授, CCF专业会员, 主要研究领域为形式化方法, 软件验证. ;施智平(1974-), 男, 博士, 教授, 博士生导师, CCF高级会员, 主要研究领域为形式化方法, 人工智能. ;关永(1966-), 男, 博士, 教授, 博士生导师, CCF专业会员, 主要研究领域为形式化验证, 高可靠嵌入式系统, 机器人. ;曹钦翔(1990-), 男, 博士, 副教授, 博士生导师, CCF专业会员, 主要研究领域为交互式定理证明, 分离逻辑, 程序验证. ;张倩颖(1986-), 女, 博士, 副教授, CCF专业会员, 主要研究领域为形式化验证, 系统安全, 操作系统.

通讯作者:

李希萌, E-mail: lixm@cnu.edu.cn

基金项目:

国家自然科学基金(62002246, 62272322, 62272323, 62372311, 62372312, 61902240)


Formal Verification of Functional Correctness for Mutexes in Microkernel
Author:
  • 摘要
  • | |
  • 访问统计
  • |
  • 参考文献 [27]
  • |
  • 相似文献 [20]
  • | | |
  • 文章评论
    摘要:

    操作系统在许多安全攸关领域为软件系统提供关键性底层支撑, 操作系统中一个微小的错误或漏洞都可能引起整个软件系统的重大故障, 造成巨大经济损失或危及人身安全. 为了减少此类安全事故的发生, 对操作系统正确性进行验证十分必要. 传统测试手段无法穷尽系统中的所有潜在错误, 因而操作系统验证有必要使用具有严格数学理论基础的形式化方法. 在操作系统中, 互斥量可协调多任务对资源的访问, 是一种常用的任务同步方式, 其功能正确性对于保障多任务应用的正确性十分关键. 基于定理证明方法, 在交互式定理证明器Coq中对某抢占式微内核操作系统的互斥量模块进行代码级形式化建模, 给出其接口函数的形式化规范, 并实现这些接口函数的功能正确性验证.

    Abstract:

    Operating systems are the key foundational components of the software stacks employed in many safety-critical scenarios. A tiny error or loophole in the operating system may cause major failures of the overall software system, resulting in huge economic losses or endangering human lives. Thus, the correctness of the operating system should be verified to reduce the number of such accidents. Traditional testing methods cannot guarantee the exhaustive detection of potential errors in the target system. Therefore, it is necessary to adopt formal methods based on strict mathematical theories for verifying operating systems. In an operating system, mutexes are utilized to coordinate the access of shared resources by tasks and they are a typical means of task synchronization. The functional correctness of mutexes is the key to the correct functioning of multi-task applications. Based on the theorem proof method, this study conducts formal verification on the code of the mutex module of a preemptive microkernel in an interactive theorem prover Coq, gives the formal specifications of the interface functions of this module, and formally proves the functional correctness of these interface functions.

    参考文献
    [1] 王戟, 詹乃军, 冯新宇, 刘志明. 形式化方法概貌. 软件学报, 2019, 30(1): 33–61. http://www.jos.org.cn/1000-9825/5652.htm
    Wang J, Zhan NJ, Feng XY, Liu ZM. Overview of formal methods. Ruan Jian Xue Bao/Journal of Software, 2019, 30(1): 33–61 (in Chinese with English abstract). http://www.jos.org.cn/1000-9825/5652.htm
    [2] Xu FW, Fu M, Feng XY, Zhang XR, Zhang H, Li ZH. A practical verification framework for preemptive OS kernels. In: Chaudhuri S, Farzan A, eds. Proc. of the 28th Int’l Conf. on Computer Aided Verification. Toronto: Springer Int’l Publishing, 2016. 59–79.
    [3] Cohen E, Dahlweid M, Hillebrand M, Leinenbach D, Moskal M, Santen T, Schulte W, Tobies S. VCC: A practical system for verifying concurrent C. In: Berghofer S, Nipkow T, Urban C, Wenzel M, eds. Proc. of the 22nd Int’l Conf. on Theorem Proving in Higher Order Logics. Munich: Springer, 2009. 23–42. [doi: 10.1007/978-3-642-03359-9_2]
    [4] Baumann C, Beckert B, Blasum H, Bormer T. Formal verification of a microkernel used in dependable software systems. In: Buth B, Rabe G, Seyfarth T, eds. Proc. of the 28th Int’l Conf. on Computer Safety, Reliability, and Security. Hamburg: Springer, 2009. 187–200. [doi: 10.1007/978-3-642-04468-7_16]
    [5] Leinenbach D, Santen T. Verifying the Microsoft Hyper-V hypervisor with VCC. In: Cavalcanti A, Dams DR, eds. Proc. of the 2nd World Congress on Formal Methods. Eindhoven: Springer, 2009. 806–809. [doi: 10.1007/978-3-642-05089-3_51]
    [6] Klein G, Huuck R, Schlich B. Operating system verification. Journal of Automated Reasoning, 2009, 42(2–4): 123–124.
    [7] Klein G, Andronick J, Elphinstone K, Murray T, Sewell T, Kolanski R, Heiser G. Comprehensive formal verification of an OS microkernel. ACM Trans. on Computer Systems, 2014, 32(1): 2.
    [8] Klein G, Elphinstone K, Heiser G, Andronick J, Cock D, Derrin P, Elkaduwe D, Engelhardt K, Kolanski R, Norrish M, Sewell T, Tuch H, Winwood S. seL4: Formal verification of an OS Kernel. In: Proc. of the 22nd ACM SIGOPS Symp. on Operating Systems Principles. Big Sky: ACM, 2009. 207–220. [doi: 10.1145/1629575.1629596]
    [9] Gu RH, Koenig J, Ramananandro T, Shao Z, Wu XN, Wang SC, Zhang HZ, Guo Y. Deep specifications and certified abstraction layers. In: Proc. of the 42nd Annual ACM SIGPLAN-SIGACT Symp. on Principles of Programming Languages. Mumbai: Association for Computing Machinery, 2015. 595–608. [doi: 10.1145/2676726.2676975]
    [10] Feng XY, Shao Z. Modular verification of concurrent assembly code with dynamic thread creation and termination. In: Proc. of the 10th ACM SIGPLAN Int’l Conf. on Functional Programming. Tallinn: Association for Computing Machinery, 2005. 254–267.
    [11] Feng XY, Shao Z, Vaynberg A, Xiang S, Ni ZZ. Modular verification of assembly code with stack-based control abstractions. In: Proc. of the 27th ACM SIGPLAN Conf. on Programming Language Design and Implementation. Ottawa: Association for Computing Machinery, 2006. 401–414. [doi: 10.1145/1133981.1134028]
    [12] Gu RH, Shao Z, Chen H, Wu XN, Kim J, Sjoberg V, Costanzo D. CertiKOS: An extensible architecture for building certified concurrent OS kernels. In: Proc. of the 12th USENIX Conf. on Operating Systems Design and Implementation. Savannah: USENIX Association, 2016. 653–669.
    [13] Chen H, Wu XN, Shao Z, Lockerman J, Gu RH. Toward compositional verification of interruptible OS kernels and device drivers. Journal of Automated Reasoning, 2018, 61(1–4): 141–189.
    [14] Liu MQ, Rieg L, Shao Z, Gu RH, Costanzo D, Kim J, Yoon M. Virtual timeline: A formal abstraction for verifying preemptive schedulers with temporal isolation. Proc. of the ACM on Programming Languages, 2020, 4: 20.
    [15] Andronick J, Lewis C, Morgan C. Controlled owicki-gries concurrency: Reasoning about the preemptible eChronos embedded operating system. arXiv:1511.04170, 2015.
    [16] 顾海博. 操作系统全局性质的形式化描述和验证 [硕士学位论文]. 合肥: 中国科学技术大学, 2018.
    Gu HB. Formalization and verification of operating system’s global properties [MS. Thesis]. Hefei: University of Science and Technology of China, 2018 (in Chinese with English abstract).
    [17] 张啸然. 无上界优先级反转问题的避免及其证明 [硕士学位论文]. 合肥: 中国科学技术大学, 2021.
    Zhang XR. Freedom of unbounded priority inversion and its verification [MS. Thesis]. Hefei: University of Science and Technology of China, 2021 (in Chinese with English abstract).
    [18] Zhao YW, Sanán D, Zhang FY, Liu Y. Reasoning about information flow security of separation kernels with channel-based communication. In: Chechik M, Raskin JF, eds. Proc. of the 22nd Int’l Conf. on Tools and Algorithms for the Construction and Analysis of Systems. Eindhoven: Springer, 2016. 791–810. [doi: 10.1007/978-3-662-49674-9_50]
    [19] Sun JW, Long X, Zhao YW. A verified capability-based model for information flow security with dynamic policies. IEEE Access, 2018, 6: 16395–16407.
    [20] Zhao YW, Sanán D, Zhang FY, Liu Y. Refinement-based specification and security analysis of separation kernels. IEEE Trans. on Dependable and Secure Computing, 2019, 16(1): 127–141.
    [21] Ma YW, Zhang QY, Zhao SJ, Wang GH, Li XM, Shi ZP. Formal verification of memory isolation for the TrustZone-based TEE. In: Proc. of the 27th Asia-Pacific Software Engineering Conf. (APSEC). Singapore: IEEE, 2020. 149–158.
    [22] Bertot Y, Castéran P. Interactive Theorem Proving and Program Development: Coq’Art: The Calculus of Inductive Constructions. Berlin: Springer, 2004. 1–472. [doi: 10.1007/978-3-662-07964-5]
    [23] Gonthier G. Formal proof—The four-color theorem. Notices of the American Mathematical Society, 2008, 55(11): 1382–1393.
    [24] Leroy X. Formal verification of a realistic compiler. Communications of the ACM, 2009, 52(7): 107–115.
    引证文献
    网友评论
    网友评论
    分享到微博
    发 布
引用本文

张林雁,李希萌,施智平,关永,曹钦翔,张倩颖.微内核操作系统互斥量模块功能正确性的形式化验证.软件学报,2024,35(9):4179-4192

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

京公网安备 11040202500063号