skip to main content
research-article

Validation of requirements for hybrid systems: A formal approach

Published: 07 February 2013 Publication History

Abstract

Flaws in requirements may have unacceptable consequences in the development of safety-critical applications. Formal approaches may help with a deep analysis that takes care of the precise semantics of the requirements. However, the proposed solutions often disregard the problem of integrating the formalization with the analysis, and the underlying logical framework lacks either expressive power, or automation.
We propose a new, comprehensive approach for the validation of functional requirements of hybrid systems, where discrete components and continuous components are tightly intertwined. The proposed solution allows to tackle problems of conversion from informal to formal, traceability, automation, user acceptance, and scalability.
We build on a new language, othello which is expressive enough to represent various domains of interest, yet allowing efficient procedures for checking the satisfiability. Around this, we propose a structured methodology where: informal requirements are fragmented and categorized according to their role; each fragment is formalized based on its category; specialized formal analysis techniques, optimized for requirements analysis, are finally applied.
The approach was the basis of an industrial project aiming at the validation of the European Train Control System (ETCS) requirements specification. During the project a realistic subset of the ETCS specification was formalized and analyzed. The approach was positively assessed by domain experts.

References

[1]
Abrial, J.-R. 1996. The B-Book: Assigning Programs to Meanings. Cambridge University Press.
[2]
Aho, A. V., Sethi, R., and Ullman, J. D. 1986. Compilers: Principles, Techniques and Tools. Addison-Wesley, Reading, MA.
[3]
Alur, R. and Henzinger, T. A. 1991. Logics and models of real time: A survey. In Proceedings of the REX Workshop. J. W. de Bakker, C. Huizing, W. P. de Roever, and G. Rozenberg, Eds., Lecture Notes in Computer Science, vol. 600, Springer, 74--106.
[4]
Alur, R. and Henzinger, T. A. 1993. Real-time logics: Complexity and expressiveness. Inf. Comput. 104, 1, 35--77.
[5]
Ambriola, V. and Gervasi, V. 2006. On the systematic analysis of natural language requirements with CIRCE. Autom. Softw. Eng. 13, 1, 107--167.
[6]
Barney, D., Haley, D., and Nikandros, G. 2001. Calculating train braking distance. In Proceedings of the 6th Australian Workshop on Safety Critical Systems And Software. Vol. 3, Australian Computer Society, Inc., Darlinghurst, Australia, 23--29.
[7]
Biere, A., Cimatti, A., Clarke, E. M., and Zhu, Y. 1999. Symbolic model checking without bdds. In Proceedings of the Workshop on Tools and Algorithms for the Construction and Analysis of Systems. R. Cleaveland, Ed., Lecture Notes in Computer Science, vol. 1579, Springer, 193--207.
[8]
Bois, P. D., Dubois, E., and Zeippen, J.-M. 1997. On the use of a formal r. e. language - the generalized railroad crossing problem. In Proceedings of the IEEE International Symposium on Requirements Engineering. IEEE, 128.
[9]
Bresciani, P., Giorgini, P., Giunchiglia, F., Mylopoulos, J., and Perini, A. 2004. Tropos: An agent-oriented software development methodology. Auton. Agents Multi-Agent Syst. 8, 3, 203--236.
[10]
Bruttomesso, R., Cimatti, A., Franzén, A., Griggio, A., and Sebastiani, R. 2008. The mathsat 4smt solver. In Proceedings of the International Conference on Computer Aided Verification. A. Gupta and S. Malik, Eds., Lecture Notes in Computer Science, vol. 5123, Springer, 299--303.
[11]
Bucchiarone, A., Gnesi, S., Trentanni, G., and Fantechi, A. 2008. Evaluation of natural language requirements in the MODCONTROL project. ERCIM News 75, 52--53.
[12]
Cavada, R., Cimatti, A., Franzén, A., Kalyanasundaram, K., Roveri, M., and Shyamasundar, R. K. 2007. Computing predicate abstractions by integrating bdds and smt solvers. In Proceedings of the International Conference on Formal Methods in Computer-Aided Design. IEEE, 69--76.
[13]
Cavada, R., Cimatti, A., Mariotti, A., Mattarei, C., Micheli, A., Mover, S., Pensallorto, M., Roveri, M., Susi, A., and Tonetta, S. 2009. Supporting requirements validation: The EuRailCheck tool. In Proceedings of the IEEE/ACM International Conference on Automated Software Engineering. IEEE, 665--667.
[14]
Chaochen, Z., Hoare, C. A. R., and Ravn, A. P. 1991. A calculus of durations. Inf. Process. Lett. 40, 5, 269--276.
[15]
Chaochen, Z., Ravn, A. P., and Hansen, M. R. 1992. An extended duration calculus for hybrid real-time systems. In Hybrid Systems, Grossman, R. L., Nerode, A., Ravn, A. P., and Rischel, H., Eds., Lecture Notes in Computer Science, vol. 736, Springer, 36--59.
[16]
Chiappini, A., Cimatti, A., Macchi, L., Rebollo, O., Roveri, M., Susi, A., Tonetta, S., and Vittorini, B. 2010. Formalization and validation of a subset of the European train control system. In Proceedings of the International Conference on Software Engineering. Vol. 2, J. Kramer, J. Bishop, P. T. Devanbu, and S. Uchitel, Eds., ACM, 109--118.
[17]
Cimatti, A., Clarke, E. M., Giunchiglia, F., and Roveri, M. 2000. NuSMV: A new symbolic model checker. Int. J. Softw. Tools .Techn. Transfer 2, 4, 410--425.
[18]
Cimatti, A., Giunchiglia, F., Mongardi, G., Romano, D., Torielli, F., and Traverso, P. 1998. Formal verification of a railway interlocking system using model checking. Formal Asp. Comput. 10, 4, 361--380.
[19]
Cimatti, A., Roveri, M., Schuppan, V., and Tonetta, S. 2007. Boolean abstraction for temporal logic satisfiability. In Proceedings of the International Conference on Computer Aided Verification. W. Damm and H. Hermanns, Eds., Lecture Notes in Computer Science, vol. 4590, Springer, 532--546.
[20]
Cimatti, A., Roveri, M., Susi, V., and Tonetta, S. 2011. Formalizing requirements with object models and temporal constraints. J. Softw. Syst. Model. 10, 2, 147.
[21]
Cimatti, A., Roveri, M., and Tonetta, S. 2008. PSL symbolic compilation. IEEE Trans. CAD Integr. Circ. Syst. 27, 10, 1737--1750.
[22]
Cimatti, A., Roveri, M., and Tonetta, S. 2009. Requirements validation for hybrid systems. In Proceedings of the International Conference on Computer Aided Verification. A. Bouajjani and O. Maler, Eds., Lecture Notes in Computer Science, vol. 5643, Springer, 188--203.
[23]
Clarke, E. M., Grumberg, O., Jha, S., Lu, Y., and Veith, H. 2000. Counterexample-guided abstraction refinement. In Proceedings of the International Conference on Computer Aided Verification. E. A. Emerson and A. P. Sistla, Eds., Lecture Notes in Computer Science, vol. 1855, Springer, 154--169.
[24]
Clarke, E. M., Grumberg, O., and Peled, D. A. 1999. Model Checking. MIT Press, Cambridge, MA.
[25]
Damas, C., Lambeau, B., Roucoux, F., and Van Lamsweerde, A. 2009. Analyzing critical process models through behavior model synthesis. In Proceedings of the International Conference on Software Engineering. IEEE, 441--451.
[26]
Darimont, R., Delor, E., Massonet, P., and Van Lamsweerde, A. 1997. GRAIL/KAOS: An environment for goal-driven requirements engineering. In Proceedings of the International Conference on Software Engineering. ACM, 612--613.
[27]
de Alfaro, L. and Manna, Z. 1995. Verification in continuous time by discrete reasoning. In Proceedings of the Workshop on Algebraic Methodology and Software Technology. V. S. Alagar and M. Nivat, Eds., Lecture Notes in Computer Science, vol. 936, Springer, 292--306.
[28]
Duan, Z., Koutny, M., and Holt, C. 1994. Projection in temporal logic programming. In Proceedings of the International Conference on Logic Programming, Artificial Intelligence and Reasoning. F. Pfenning, Ed., Lecture Notes in Computer Science, vol. 822, Springer, 333--344.
[29]
Eisner, C. 2002. Using symbolic CTL model checking to verify the railway stations of Hoorn-Kersenboogerd and Heerhugowaard. Int. J. Softw. Tools .Techn. Transfer 4, 1, 107--124.
[30]
Eisner, C. and Fisman, D. 2006. A Practical Introduction to PSL. Springer.
[31]
ETCS 2006. ERTMS/ETCS---Baseline 3: System Requirements Specifications. SUBSET-026. http://www.era. europa.eu/Document-Register/Pages/UNISIGSUBSET-026.aspx.
[32]
EuRailCheck-cft 2007. Feasibility study for the formal specification of ETCS functions. Call for tender. http://www.era.europa.eu/The-Agency/Procurement/Pages/ERA-2007-ERTMS-OP-01.aspx.
[33]
Faber, J. and Meyer, R. 2006. Model checking data-dependent real-time properties of the european train control system. In Proceedings of the International Conference on Formal Methods in Computer-Aided Design. IEEE, 76--77.
[34]
Fantechi, A., Gnesi, S., Ristori, G., Carenini, M., Vanocchi, M., and Moreschini, P. 1994. Assisting requirement formalization by means of natural language translation. Formal Methods Syst. Des. 4, 3, 243--263.
[35]
Feilkas, M., Fleischmann, A., Hölzl, F., Pfaller, C., Scheidemann, K., Spichkova, M., and Trachtenherz, D. 2009. A top-down methodology for the development of automotive software. Tech. rep., Technische Universität München.
[36]
Furia, C. A., Mandrioli, D., Morzenti, A., and Rossi, M. 2010. Modeling time in computing: A taxonomy and a comparative survey. ACM Comput. Surv. 42, 2.
[37]
Fuxman, A., Liu, L., Mylopoulos, J., Pistore, M., Roveri, M., and Traverso, P. 2004. Specifying and analyzing early requirements in Tropos. Requirements Engin. 9, 2, 132--150.
[38]
Gervasi, V. and Zowghi, D. 2005. Reasoning about inconsistencies in natural language requirements. ACM Trans. Softw. Eng. Methodol. 14, 3, 277--330.
[39]
Ghezzi, C., Mandrioli, D., and Morzenti, A. 1990. TRIO: A logic language for executable specifications of real-time systems. J. Syst. Softw. 12, 2, 107--123.
[40]
Gurevich, Y. 1995. Evolving Algebras 1993: Lipari Guide. In Specification and Validation Methods. Oxford.
[41]
Heitmeyer, C. 2007. Formal methods for specifying, validating, and verifying requirements. J. Univ. Comput. Sci. 13, 5, 607--618.
[42]
Henzinger, T. A. 1996. The theory of hybrid automata. In Proceedings of the Annual IEEE Symposium on Logic in Computer Science. 278--292.
[43]
Henzinger, T. A., Manna, Z., and Pnueli, A. 1992. Towards refining temporal specifications into hybrid systems. In Hybrid Systems, R. L. Grossman, A. Nerode, A. P. Ravn, and H. Rischel, Eds., Lecture Notes in Computer Science, vol. 736, Springer, 60--76.
[44]
Jackson, D. 2002. Alloy: a lightweight object modeling notation. ACM Trans. Softw. Eng. Methodol. 11, 2, 256--290.
[45]
Kapur, A. 1998. Interval and point-based approaches to hybrid system verification. Ph.D. thesis, Stanford University, Stanford, CA.
[46]
Kof, L. 2005. Natural language processing: Mature enough for requirements documents analysis? In Proceedings of the International Conference on Applications of Natural Language to Information Systems. A. Montoyo, R. Muñoz, and E. Métais, Eds., Lecture Notes in Computer Science, vol. 3513, Springer, 91--102.
[47]
Kof, L. 2009. Requirements analysis: Concept extraction and translation of textual specifications to executable models. InProceedings of the International Conference on Applications of Natural Language to Information Systems. H. Horacek, E. Métais, R. Muñoz, and M. Wolska, Eds., Lecture Notes in Computer Science, vol. 5723, Springer, 79--90.
[48]
Kühne, U., Grosse, D., and Drechsler, R. 2009. Property analysis and design understanding. In Proceedings of the Conference and Exhibition on Design, Automation and Test in Europe. IEEE, 1246--1249.
[49]
Liu, Z., Ravn, A. P., and Li, X. 2004. Unifying proof methodologies of duration calculus and timed linear temporal logic. Formal Asp. Comput. 16, 2, 140--154.
[50]
Lutz, R. 1993. Analyzing Software Requirements Errors in Safety-Critical, Embedded Systems. In Proceedings of the IEEE International Symposium on Requirements Engineering. 126--133.
[51]
Maler, O., Nickovic, D., and Pnueli, A. 2008. Checking temporal properties of discrete, timed and continuous behaviors. In Pillars of Computer Science, A. Avron, N. Dershowitz, and A. Rabinovich, Eds., Lecture Notes in Computer Science, vol. 4800, Springer, 475--505.
[52]
Manna, Z. and Pnueli, A. 1992. The temporal Logic of Reactive and Concurrent Systems. Springer.
[53]
Meyer, R., Faber, J., Hoenicke, J., and Rybalchenko, A. 2008. Model checking duration calculus: A practical approach. Formal Asp. Comput. 20, 4-5, 481--505.
[54]
Nelken, R. and Francez, N. 1996. Automatic translation of natural language system specifications. In Proceedings of the International Conference on Computer Aided Verification. R. Alur and T. A. Henzinger, Eds., Lecture Notes in Computer Science, vol. 1102, Springer, 360--371.
[55]
OMG 2006. OMG 2006. Object constraint language. OMG available specification Version 2.0.
[56]
Ortmeier, F., Reif, W., and Schellhorn, G. 2005. Formal safety analysis of a radio-based railroad crossing using deductive cause-consequence analysis (dcca). In Proceedings of the 5th European Dependable Computing Conference. M. D. Cin, M. Kaâniche, and A. Pataricza, Eds., Lecture Notes in Computer Science, vol. 3463, Springer, 210--224.
[57]
Peleska, J., Grosse, D., Haxthausen, A. E., and Drechsler, R. 2004. Automated Verification for Train Control Systems. In Proceedings of Formal Methods for Automation and Safety in Railway and Automotive Systems (FORMS/FORMAT '04).
[58]
Pill, I., Semprini, S., Cavada, R., Roveri, M., Bloem, R., and Cimatti, A. 2006. Formal analysis of hardware requirements. In Proceedings of the IEEE/ACM Design Automation Conference. E. Sentovich, Ed., ACM, New York, NY, 821--826.
[59]
Platzer, A. 2007. Differential dynamic logic for verifying parametric hybrid systems. In Proceedings of the 16th International Conference on Automated Reasoning with Analytic Tableaux and Related Methods. N. Olivetti, Ed., Lecture Notes in Computer Science, vol. 4548, Springer, 216--232.
[60]
Platzer, A. and Quesel, J.-D. 2009. European train control system: A case study in formal verification. In Proceedings of the 11th International Conference on Formal Engineering Methods: Formal Methods and Software Engineering. K. Breitman and A. Cavalcanti, Eds., Lecture Notes in Computer Science, vol. 5885, Springer, 246--265.
[61]
Pnueli, A. 1977. The temporal logic of programs. In Proceedings of the Annual Symposium on Foundations of Computer Science. IEEE, 46--57.
[62]
PROSYD 2007. PROSYD 2007. The PROSYD project on property-based system design. http://www. prosyd.org.
[63]
Rumbaugh, J., Jacobson, I., and Booch, G. 2010. Unified Modeling Language Reference Manual. Addison-Wesley.
[64]
Sebastiani, R. 2007. Lazy Satisfiability Modulo Theories. J. Satisfiability, Boolean Model. Comput. 3, 3--4, 141--224.
[65]
Sinha, A., Paradkar, A. M., Kumanan, P., and Boguraev, B. 2009. A linguistic analysis engine for natural language use case description and its application to dependability analysis in industrial use cases. In Proceedings of the International Conference on Dependable Systems and Networks. IEEE, 327--336.
[66]
Sommerville, I. 2004. Software Engineering. Addison Wesley.
[67]
Spivey, J. M. 1992. The Z Notation: A Reference Manual 2nd Ed. Prentice Hall, Inc., Upper Saddle River, NJ.
[68]
Susi, A., Perini, A., Giorgini, P., and Mylopoulos, J. 2005. The tropos metamodel and its use. Informatica 29, 4, 401--408.
[69]
Van Lamsweerde, A. 2009. Requirements Engineering. Wiley.

Cited By

View all

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Transactions on Software Engineering and Methodology
ACM Transactions on Software Engineering and Methodology  Volume 21, Issue 4
November 2012
197 pages
ISSN:1049-331X
EISSN:1557-7392
DOI:10.1145/2377656
Issue’s Table of Contents
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 07 February 2013
Accepted: 01 April 2011
Revised: 01 December 2010
Received: 01 April 2010
Published in TOSEM Volume 21, Issue 4

Permissions

Request permissions for this article.

Check for updates

Author Tags

  1. European train control system
  2. Requirements validation
  3. formal languages
  4. methodology
  5. safety-critical applications

Qualifiers

  • Research-article
  • Research
  • Refereed

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)45
  • Downloads (Last 6 weeks)7
Reflects downloads up to 03 Jan 2025

Other Metrics

Citations

Cited By

View all

View Options

Login options

Full Access

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Media

Figures

Other

Tables

Share

Share

Share this Publication link

Share on social media