微信服务号

微信订阅号

2025年5月10日 23:11 星期六
首页 > 过刊浏览>2020年第31卷第5期 >1353-1373. DOI:10.13328/j.cnki.jos.005957
PDF HTML阅读 XML下载 导出引用 引用提醒
嵌入式实时操作系统内核混合代码的自动化验证框架
作者:
作者简介:

郭建(1969-),女,陕西西安人,博士,副教授,CCF专业会员,主要研究领域为嵌入式实时操作系统,形式化建模与验证,模型检验;丁继政(1991-),男,硕士,主要研究领域为嵌入式系统建模与验证;朱晓冉(1991-),女,博士,主要研究领域为形式化验证.

通讯作者:

郭建,E-mail:jguo@sei.ecnu.edu.cn

基金项目:

国家自然科学基金（61532019）；上海市重点项目（19511103602）


Automated Verification Framework for Mixed Code in Embedded Real Time Operating System Kernel
Author:
Fund Project:

National Natural Science Foundation of China (61532019); Major Project of Science and Technology Commitment of Shanghai (19511103602)

  • 摘要
    • | |
  • 访问统计
    • |
  • 参考文献 [39]
    • |
  • 相似文献 [20]
    • |
  • 引证文献
    • | |
  • 文章评论
    摘要:

    “如何构造高可信的软件系统”已成为学术界和工业界的研究热点.操作系统内核作为软件系统的基础组件，其安全可靠是构造高可信软件系统的重要环节.为了确保操作系统内核的安全可靠，将形式化方法引入到操作系统内核验证中，提出了一个自动化验证操作系统内核的框架.该验证框架包括：（1）分别对C语言程序和混合语言程序（C语言和汇编语言）进行验证；（2）在混合语言程序验证中，为汇编程序建立抽象模型，并将C语言程序和抽象模型粘合形成基于C语言验证工具可接收的验证模型；（3）从规范中提取性质，基于该自动验证工具，对性质完成自动验证；（4）该框架不限于特定的硬件架构.成功地运用该验证框架对两种不同硬件平台的嵌入式实时操作系统内核μC/OS-II进行了验证.结果显示，利用该框架在对两个不同的硬件平台上内核验证时，框架的可重复利用率很高，高达83.8%，虽然其抽象模型需要根据不同的硬件平台进行重构.在对基于这两种平台的操作系统内核验证中，分别发现了10处~12处缺陷.其中，在ARM平台上两处与硬件相关的问题被发现.实验结果表明，该方法对不同硬件平台的同一个操作系统分析验证具有一定的通用性.

    Abstract:

    “How to construct a trustworthy software system” has become an important research area in academia and industry. As a basic component of the software system, the operating system kernel is an important component of constructing a trustworthy software system. In order to ensure the safety and reliability of an operating system kernel, this study introduces formal method into OS kernel verification, and proposes an automatically verifying framework. The verification framework includes following factors. (1) Separate C language programs and mixed language programs (for example, mixed language programs written by C and assembly language) for verification. (2) In the mixed language program verification, establish an abstract model for the assemble program, and then glue the C language program and the abstract model to form a verification model received by a C language verification tool. (3) Extract properties from the OS specification, and automatically verify properties based on a verification tool. (4) Do not limit to a specific hardware architecture. This study successfully applies the verification framework to verify a commercial real-time operating system kernel μC/OS-II of two different hardware platforms. The results show that when kernels on two different hardware platforms are verified, the reusability of the verification framework is very high, up to 83.8%. Of course, the abstract model needs to be reconstructed according to different hardware. During verification of operating system kernels based on two kinds of hardware, 10~12 defaults are found respectively. Among them, two hardware-related defaults on the ARM platform are discovered. This method has certain versatility for analysis and verification of the same operating system on different hardware architectures.

    参考文献
    [1] Ehrenfeld JM. Wannacry, cybersecurity and health information technology: A time to act. Journal of Medical Systems, 2017,41(7): Article No.104.
    [2] Mohurle S, Patil M. A brief study of wannacry threat: Ransomware attack 2017. Int’l Journal of Advanced Research in Computer Science, 2017,8(5):1938-1940.
    [3] Lipp M, Schwarz M, Gruss D, et al. Meltdown. arXiv preprint arXiv:1801.01207, 2018.
    [4] Kocher P, Genkin D, Gruss D, et al. Spectre attacks: Exploiting speculative execution. arXiv preprint arXiv:1801.01203, 2018.
    [5] Simakov NA, Innus MD, Jones MD, et al. Effect of meltdown and spectre patches on the performance of HPC applications. arXiv preprint arXiv:1801.04329, 2018.
    [6] Klein G, Elphinstone K, Heiser G, et al. seL4: Formal verification of an OS kernel. In: Proc. of the Symp. on Operating Systems Principles. ACM, 2009. 207-220.
    [7] Klein G, Andronick J, Elphinstone K, et al. Comprehensive formal verification of an OS microkernel. ACM Trans. on Computer Systems (TOCS), 2014,32(1):1-70.
    [8] Paulson LC. Isabelle: A Generic Theorem Prover. Springer Science & Business Media, 1994.
    [9] der Rieden TI, Tsyban A. CVM—A verified framework for microkernel programmers. Electronic Notes in Theoretical Computer Science, 2008,217:151-168.
    [10] Baumann C, Beckert B, Blasum H, et al. Formal verification of a microkernel used in dependable software systems. In: Proc. of the Int’l Conf. on Computer Safety, Reliability, and Security. Berlin, Heidelberg: Springer-Verlag, 2009. 187-200.
    [11] Daum M, Schirmer NW, Schmidt M. Implementation correctness of a real-time operating system. In: Proc. of the 7th IEEE Int’l Conf. on Software Engineering and Formal Methods. IEEE, 2009. 23-32.
    [12] Baumann C, Beckert B, Blasum H, et al. Lessons learned from microkernel verification—Specification is the new bottleneck. arXiv preprint arXiv:1211.6186, 2012.
    [13] Baumann C, Beckert B, Blasum H, et al. Better avionics software reliability by code verification. In: Proc. of the Embedded World Conf. Nuremberg, 2009.
    [14] Cohen E, Dahlweid M, Hillebrand M, et al. VCC: A practical system for verifying concurrent C. In: Proc. of the TPHOLs. 2009. 23-42.
    [15] Kaiser R, Wagner S. Evolution of the PikeOS microkernel. In: Proc. of the 1st Int’l Workshop on Microkernels for Embedded Systems. 2007. 50-57.
    [16] Chlipala A. Certified Programming with Dependent Types: A Pragmatic Introduction to the Coq Proof Assistant. MIT Press, 2013.
    [17] Gu R, Koenig J, Ramananandro T, et al. Deep specifications and certified abstraction layers. ACM SIGPLAN Notices, 2015,50(1): 595-608.
    [18] Costanzo D, Shao Z, Gu R. End-to-end verification of information-flow security for C and assembly programs. ACM SIGPLAN Notices, 2016,51(6):648-664.
    [19] Gu R, Shao Z, Chen H, et al. CertiKOS: An extensible architecture for building certified concurrent OS kernels. In: Proc. of the 10th USENIX Symp. on Operating Systems Design and Implementation (OSDI 2016). 2016. 653-669.
    [20] Chen H, Wu XN, Shao Z, et al. Toward compositional verification of interruptible OS kernels and device drivers. ACM SIGPLAN Notices, 2016,51(6):431-447.
    [21] Nelson L, Sigurbjarnarson H, Zhang K, et al. Hyperkernel: Push-button verification of an OS kernel. In: Proc. of the 26th Symp. on Operating Systems Principles. ACM, 2017. 252-269.
    [22] Xu F, Fu M, Feng X, et al. A practical verification framework for preemptive OS kernels. In: Proc. of the Int’l Conf. on Computer Aided Verification. Cham: Springer-Verlag, 2016. 59-79.
    [23] Xu FW. Design and implementation of a verification framework for preemptive OS kernels [Ph.D. Thesis]. Hefei: University of Science and Technology of China, 2016(in Chinese with English abstract).
    [24] Ma JB, Fu M, Feng XY. Formal verification of the message queue communication mechanism in μC/OS-II. Journal of Chinese Computer Systems, 2016,37(6):1179-1184(in Chinese with English abstract).
    [25] Labrosse JJ. C/OS-II The Real-Time Kernel User’s Manual. Rev.2.92.17, 2019. https://doc.micrium.com/pages/viewpage.action?pageId=10753158&preview=/10753158/20644170/100-uC-OS-II-003.pdf
    [26] Zhao Y, Sanan D, Zhang F, et al. Refinement-based specification and security analysis of separation kernels. IEEE Trans. on Dependable and Secure Computing, 2017,16(1):127-141.
    [27] Zou L, Lv JD, Wang SL, et al. Verifying Chinese train control system under a combined scenario by theorem proving. In: Proc. of the Working Conf. on Verified Software: Theories, Tools, and Experiments. Berlin, Heidelberg: Springer-Verlag, 2013. 262-280.
    [28] Ding JZ. Formal verification and analysis of RTOS kernel [MS. Thesis]. Shanghai: East China Normal University, 2019(in Chinese with English abstract).
    [29] Freescale Semiconductor. Mcf5441x Reference Manual. Rev.4, 2012.
    [30] Freescale Semiconductor. Coldfire Family Programmer’s Reference Manual. Rev.303, 2005.
    [31] Yiu J. The Definitive Guide to ARM® Cortex®-M3 and Cortex®-M4 Processors. Newnes, 2013.
    [32] Moskal M, Schulte W, Cohen E, Hillebrand MA, et al. Verifying C programs: A VCC tutorial. 2012. https://archive.codeplex.com/?p=vcc
    [33] DeLine R, Leino KRM. BoogiePL: A typed procedural language for checking object-oriented programs. Technical Report, 2005. https://www.microsoft.com/en-us/research/wp-content/uploads/2016/02/tr-2005-70.pdf
    [34] Barnett M, Chang BYE, DeLine R, et al. Boogie: A modular reusable verifier for object-oriented programs. In: Proc. of the Int’l Symp. on Formal Methods for Components and Objects. Berlin, Heidelberg: Springer-Verlag, 2005. 364-387.
    [35] ARM® Cortex®-M3 Processor Technical Reference Manual. Rev.r2p1, 2015. https://static.docs.arm.com/100165/0201/arm_ cortexm3_processor_trm_100165_0201_01_en.pdf?_ga=2.256657411.904144181.1588151964-699243147.1588151964
    附中文参考文献:
    [23] 许峰唯.抢占式操作系统内核验证框架的设计和实现[博士学位论文].合肥:中国科学技术大学,2016.
    [24] 马杰波,付明,冯新宇.μC/OS-II中消息队列通信机制的形式化验证.小型微型计算机系统,2016,37(6):1179-1184.
    [28] 丁继政.实时操作系统内核的形式化验证与分析[硕士学位论文].上海:华东师范大学,2019.
    引证文献
引用本文

郭建,丁继政,朱晓冉.嵌入式实时操作系统内核混合代码的自动化验证框架.软件学报,2020,31(5):1353-1373

复制
相关视频

分享
文章指标
  • 点击次数:
  • 下载次数:
  • HTML阅读次数:
  • 引用次数:
历史
  • 收稿日期:2019-09-05
  • 最后修改日期:2019-12-24
  • 在线发布日期: 2020-04-09
  • 出版日期: 2020-05-06
文章二维码
友情链接:中国科学院软件研究所中国计算机学会中国科学院国家自然科学基金委员会CCF数字图书馆Int'l J of Softw Info计算机系统应用
您是第19921079位访问者
版权所有：中国科学院软件研究所 京ICP备05046678号-3
地址：北京市海淀区中关村南四街4号,邮政编码：100190
电话：010-62562563 传真：010-62562533 Email：jos@iscas.ac.cn
技术支持：北京勤云科技发展有限公司

京公网安备 11040202500063号