Requirement patterns in deductive verification of poST programs

I. M. Chernenko ; I. S. Anureev ; N. O. Garanina

Modelirovanie i analiz informacionnyh sistem, Tome 31 (2024) no. 1, pp. 6-31.

Résumé

Process-oriented programming is one of the approaches to developing control software. A process-oriented program is defined as a sequence of processes. Each process is represented by a set of named states containing program code that define the logic of the process's behavior. Program execution is sequential execution of each of these processes in their current states at every iteration of the control cycle. Processes can interact through changing each other's states and shared variables. The paper expands a method for classifying temporal requirements for process-oriented programs in order to simplify and automate the deductive verification of such programs. The method consists of the following steps. At the first step, the requirements are formalized in a specialized language DV-TRL, a variant of typed first-order predicate logic with a set of interpreted types and predicate and functional symbols, that reflect specific concepts of control systems in a process-oriented paradigm. At the second step, the formalized requirements are divided into classes, each of which is defined by a pattern — a parametric formula of the DV-TRL language. The correctness conditions generated for process-oriented programs regarding requirements satisfying the same pattern have the same proof scheme. At the third step, appropriate proof schemes are developed. In our paper, we first give a brief introduction to the poST language, a process-oriented extension to the ST language of the IEC 61131-3 standard. Next, the DV-TRL language is defined. We also provide a collection of natural language requirements for several control systems. Then we define patterns that fully cover all the requirements of this collection. For each of these patterns we give an example of a formalized requirement from the collection and describe a scheme for proving the correctness conditions for this pattern. Statistics on the distribution of requirements from the collection across patterns reveals the most popular patterns. We also analyzed related works.

Détail

Keywords: deductive verification, temporal requirements, requirement patterns, control software, process-oriented programming.

Bibliographie

[1] V. E. Zyubin, “Hyper-automaton: a Model of Control Algorithms”, 2007 Siberian Conference on Control and Communications, 2007, 51–57 | DOI

[2] I. Anureev, N. Garanina, T. Liakh, A. Rozov, V. Zyubin, and S. Gorlatch, “Two-step deductive verification of control software using Reflex”, International Andrei Ershov Memorial Conference on Perspectives of System Informatics, 2019, 50–63 | DOI

[3] V. E. Zyubin, T. V. Liakh, and A. S. Rozov, “Reflex language: a practical notation for cyber-physical systems”, System Informatics, 2018, no. 12, 85–104

[4] C. Paulin-Mohring, “Introduction to the Coq proof-assistant for practical software verification”, LASER Summer School on Software Engineering, Springer, 2011, 45–95

[5] I. Chernenko, I. S. Anureev, N. O. Garanina, and S. M. Staroletov, “A Temporal Requirements Language for Deductive Verification of Process-Oriented Programs”, IEEE 23rd International Conference of Young Professionals in Electron Devices and Materials (EDM), 2022, 657–662 | DOI

[6] I. M. Chernenko and I. S. Anureev, “Development of Verification Condition Generator for Process-Oriented Programs in poST Language”, IEEE 24th International Conference of Young Professionals in Electron Devices and Materials (EDM), 2023, 1760–1765 | DOI

[7] V. E. Zyubin, A. S. Rozov, I. S. Anureev, N. O. Garanina, and V. Vyatkin, “poST: A Process-Oriented Extension of the IEC 61131-3 Structured Text Language”, IEEE Access, 10 (2022) | DOI

[8] IEC 61131-3: 2013 rogrammable controllers-Part 3: programming languages, IEC, 2013 https://webstore.iec.ch/publication/4552

[9] L. C. Paulson, T. Nipkow, and M. Wenzel, “From LCF to Isabelle/HOL”, Formal Aspects of Computing, 31 (2019), 675–698 | DOI | MR | Zbl

[10] I. M. Chernenko, “Requirements patterns in deductive verification of process-oriented programs and examples of their use”, System Informatics, 2023, no. 22 | DOI

[11] J.-C. Filliâtre, “Deductive software verification”, International Journal on Software Tools for Technology Transfer, 13 (2011), 397–403 | DOI

[12] D. Gurov, P. Herber, and I. Schaefer, “Automated Verification of Embedded Control Software”, International Symposium on Leveraging Applications of Formal Methods, 2020, 235–239 | DOI

[13] D. Gurov, C. Lidström, M. Nyberg, and J. Westman, “Deductive Functional Verification of Safety-Critical Embedded C-Code: An Experience Report”, Critical Systems: Formal Methods and Automated Verification, 2017, 3–18 | DOI | MR

[14] C. B. Lourenço, D. Cousineau, F. Faissole, C. Marché, D. Mentré, and H. Inoue, “Automated Verification of Temporal Properties of Ladder Programs”, Formal Methods for Industrial Critical Systems, 2021, 21–38 | DOI

[15] Z. Manna et al., “An Update on STeP: Deductive-Algorithmic Verification of Reactive Systems”, Tool Support for System Specification, Development and Verification, 1999, 174–188 | DOI

[16] S. Yamane, “Deductive verification method of real-time safety properties for embedded assembly programs”, Electronics, 8:10 (1163), 1163 | DOI

[17] E. M. Clarke, T. A. Henzinger, H. Veith, R. Bloem, and others, Handbook of model checking, Springer, 2018 | MR | Zbl

[18] N. O. Garanina et al., “A Temporal Logic for Programmable Logic Controllers”, Automatic Control and Computer Sciences, 55:7 (2021), 763–775 | DOI

[19] Z. Manna and A. Pnueli, The temporal logic of reactive and concurrent systems: Specification, Springer, New York, NY, 1992 | MR

[20] M. B. Dwyer, G. S. Avrunin, and J. C. Corbett, “Patterns in Property Specifications for Finite-State Verification”, Proceedings of the 21st International Conference on Software Engineering, 1999, 411–420 | DOI

[21] L. Grunske, “Specification patterns for probabilistic quality properties”, Proceedings of the 30th international conference on Software engineering, 2008, 31–40 | DOI

[22] S. Konrad and B. H. C. Cheng, “Real-Time Specification Patterns”, Proceedings of the 27th International Conference on Software Engineering, 2005, 372–381 | DOI

[23] A. Mekki, M. Ghazel, and A. Toguyéni, “Assisting Temporal Requirement Specification”, Computer Technology and Application, 3:1 (2012), 47–55

[24] O. Mondragon, A. Q. Gates, and S. Roach, “Prospec: Support for elicitation and formal specification of software properties”, Electronic Notes in Theoretical Computer Science, 89:2 (2003), 67–88 | DOI

[25] S. Salamah, A. Gates, and V. Kreinovich, “Validated Templates for Specification of Complex LTL Formulas”, Journal of Systems and Software, 85:8 (2012), 1915–1929 | DOI

[26] D. Bianculli, C. Ghezzi, C. Pautasso, and P. Senti, “Specification patterns from research to industry: A case study in service-based applications”, 34th International Conference on Software Engineering (ICSE), 2012, 968–976 | DOI

[27] S. Halle, R. Villemaire, and O. Cherkaoui, “Specifying and Validating Data-Aware Temporal Web Service Properties”, IEEE Transactions on Software Engineering, 35:5 (2009), 669–683 | DOI

[28] A. Post, I. Menzel, and A. Podelski, “Applying Restricted English Grammar on Automotive Requirements-Does it Work? A Case Study”, Requirements Engineering: Foundation for Software Quality, 2011, 166–180 | DOI

[29] M. Autili, L. Grunske, M. Lumpe, P. Pelliccione, and A. Tang, “Aligning Qualitative, Real-Time, and Probabilistic Property Specification Patterns Using a Structured English Grammar”, IEEE Transactions on Software Engineering, 41:7 (2015), 620–638 | DOI

[30] A. N. Getmanova, N. O. Garanina, S. M. Staroletov, V. E. Zyubin, and I. S. Anureev, “Semantic Classification of Event Driven Temporal Logic Requirements”, IEEE 23rd International Conference of Young Professionals in Electron Devices and Materials (EDM), 2022, 663–668 | DOI

[31] V. Zyubin, I. Anureev, N. Garanina, S. Staroletov, A. Rozov, and T. Liakh, “Event-Driven Temporal Logic Pattern for Control Software Requirements Specification”, International Conference on Fundamentals of Software Engineering, 2021, 92–107 | Zbl