SMT-based Formal Verification of Synchronous Reactive Model for Zone Controller
Author:
Affiliation:

  • Article
  • | |
  • Metrics
  • |
  • Reference [25]
  • |
  • Related
  • | | |
  • Comments
    Abstract:

    Formal verification is a proven technique for improving product quality during software development of safety critical systems. However, the verification must be complete, both theoretically and in the interest of practicality. Data-flow verification is a pervading manifestation of verification of the software model in implementation level. Environmental input, generic function, high-order iterative operation, and intermediate variables are therefore crucial for analyzing usability of verification approaches. To verify a synchronous reactive model, engineers readily verify the control-flow model (i.e., safe state machine). Existing work shows that these approaches fall short of complete verification of synchronous reactive model of industrial software, which results in the loss of reaching the industrial requirements. It presents a significant pain point for adopting formal verification of industrial software. Thus, it is drawn on the insight that the synchronous reactive model of safety-critical systems should be verified completely, and the data-flow models should be considered. An approach is presented for automated, generic verification that tailor to verify the integration of safe state machines and data-flow models. Furthermore, a synthesis-based approach is adopted where the SCADE models describe functional requirements, safety requirements and environmental inputs that can be verified for an SMT-based model checker through program synthesis to Lustre model. The proposed technique promotes program synthesis as a general primitive for improving the integrity of formal verification. The proposed approach is evaluated on an industrial application (nearly two million lines of Lustre code) in rail transit. It is show that the proposed approach is effective in sidestepping long-standing and complex verification issues in large scale synchronous reactive model.

    Reference
    [1] Shi J, Shi JQ, Huang YH, et al.Scade2Nu:A tool for verifying safety requirements of SCADE models with temporal specifications.In:Joint Proc.of the 25th Int'l Conf.on Requirements Engineering:Foundation for Software Quality (REFSQ 2019).2019.1-6.
    [2] Heim S, Xavier D, Bonnafous E, et al.Model checking of SCADE designed systems.In:Proc.of the 8th European Congress on Embedded Real Time Software and Systems (ERTS 2016).2016.1-8.
    [3] Yuan ZH, Chen XH, Liu J, et al.Simplifying the formal verification of safety requirements in zone controllers through problem frames and constraint-based projection.IEEE Trans.on Intelligent Transportation Systems, 2018, 19(11):3517-3528.
    [4] Caspi P, Pilaud D, Halbwachs N, et al.LUSTRE:A declarative language for real-time programming.In:Proc.of the ACM SIGACT-SIGPLAN Symp.on Principles of Programming Languages.ACM, 1987.178-188.
    [5] Nicolas H, Paul C, Pascal R, et al.The synchronous data flow programming language LUSTRE.Proc.of the IEEE, 1991, 70(9):1305-1320.
    [6] Ran D, Chen Z, Sun Y, et al.SCADE model checking based on program transformation.Computer Science, 2021, 48(12):125-130.
    [7] Vassil T, Safouan T, Frederic B, et al.Improved invariant generation for industrial software model checking of time properties.In:Proc.of the IEEE 19th Int'l Conf.on Software Quality, Reliability and Security (QRS).IEEE, 2019.334-341.
    [8] Aniculaesei A, Vorwald A, Rausch A.Using the SCADE toolchain to generate requirements-based test cases for an adaptive cruise control system.In:Proc.of the 22nd ACM/IEEE Int'l Conf.on Model Driven Engineering Languages and Systems Companion (MODELS-C).2019.503-513.[doi:10.1109/MODELS-C.2019.00079]
    [9] Henning B, Henning G, Michaela H, et al.An open alternative for SMT-based verification of SCADE models.In:Proc.of the 19th Int'l Conf.on Formal Methods for Industrial Critical Systems (FMICS).Florence:Springer, 2014.124-139.
    [10] Zhou JM.Formal modeling and verification of SCADE model based on PVS for rail transit control system[MS.Thesis].Shanghai:East China Normal University, 2011(in Chinese with English abstract).
    [11] Bennour IE.Formal verification of timed synchronous dataflow graphs using Lustre.Journal of Logical and Algebraic Methods in Programming, 2021, 121(100678):1-24.
    [12] Henning G, Stefan M, Oliver M.On the formal verification of systems of synchronous software components.In:Proc.of the 31st Int'l Conf.on Computer Safety, Reliability, and Security (SAFECOMP 2012).Magdeburg:Springer, 2012.291-304.
    [13] Milton S, Siddhartha B, Matthew AC, et al.Formal compositional reasoning of autonomous aerial systems with complex algorithms.In:Proc.of the IEEE Int'l Systems Conf.(SysCon).IEEE, 2020.1-7.
    [14] Ferrari A, Mazzanti F, Basile D, et al.Systematic evaluation and usability analysis of formal methods tools for railway signaling system design.IEEE Trans.on Software Engineering, 2022, 48(11):4675-4691.
    [15] Liu XS, Yuan ZH, Chen XH, et al.Safety requirements modeling and automatic verification for zone controllers.Ruan Jian Xue Bao/Journal of Software, 2020, 31(5):1374-1391(in Chinese with English abstract).http://www.jos.org.cn/1000-9825/5952.htm[doi:10.13328/j.cnki.jos.005952]
    [16] Blanc B, Bandmann O, Fredholm D.2018.https://www.prover.com/https://www.prover.com/webinar/building-a-safety-case-for-rail-control-software-with-formal-verification/
    [17] Li TF, Chen XH, Sun HY, et al.Modeling and verification of spatiotemporal intelligent transportation systems.In:Proc.of the 19th IEEE Int'l Conf.on Trust, Security and Privacy in Computing and Communications (TrustCom).IEEE, 2020.568-575.
    [18] Dumitru PB, Stephen AE, Gerard B.Compiling Esterel.Springer, 2007.
    [19] Andrew G, John B, Mike W, et al.The JKind model checker.In:Proc.of the 30th Int'l Conf.on Computer Aided Verification (CAV).Springer, 2018.20-27.
    [20] EN 50126 Railway Applications.The specification and demonstration of reliability, availability, maintainability and safety (RAMS).In:Proc.of the Systems Approach to Safety.2017. 11-25.
    [21] Erwan J, Pascal R, Nicolas H.The Lustre V6 Reference Manual.Verimag Lab, 2017.https://www-verimag.imag.fr/Lustre-V6.html
    [22] Amar B, Bernard D.Formal verification for model-based development.Journal of Passenger Cars:Electronic and Electrical Systems, 2005, 114:171-181.
    [23] Martin L, Schatalov M, Hagner M, et al.A methodology for model-based development and automated verification of software for aerospace systems.In:Proc.of the IEEE Aerospace Conf.IEEE, 2013.1-19.附中文参考文献:
    [10] 周佳铭.基于PVS对SCADE开发轨交控制系统的形式化建模与验证[硕士学位论文].上海:华东师范大学, 2011.
    [15] 刘筱珊, 袁正恒, 陈小红, 等.区域控制器的安全需求建模与自动验证.软件学报, 2020, 31(5):1374-1391.http://www.jos.org.cn/1000-9825/5952.htm[doi:10.13328/j.cnki.jos.005952]
    Related
    Cited by
    Comments
    Comments
    分享到微博
    Submit
Get Citation

李腾飞,孙军峰,吕新军,陈祥,刘静,孙海英,何积丰.基于SMT的区域控制器同步反应式模型的形式化验证.软件学报,2023,34(7):3080-3098

Copy
Share
Article Metrics
  • Abstract:1166
  • PDF: 3508
  • HTML: 2165
  • Cited by: 0
History
  • Received:September 04,2022
  • Revised:October 08,2022
  • Online: December 30,2022
  • Published: July 06,2023
You are the first2036718Visitors
Copyright: Institute of Software, Chinese Academy of Sciences Beijing ICP No. 05046678-4
Address:4# South Fourth Street, Zhong Guan Cun, Beijing 100190,Postal Code:100190
Phone:010-62562563 Fax:010-62562533 Email:jos@iscas.ac.cn
Technical Support:Beijing Qinyun Technology Development Co., Ltd.

Beijing Public Network Security No. 11040202500063