Skip to main content

2016 | OriginalPaper | Buchkapitel

On Implementing Real-Time Specification Patterns Using Observers

verfasst von : John D. Backes, Michael W. Whalen, Andrew Gacek, John Komp

Erschienen in: NASA Formal Methods

Verlag: Springer International Publishing

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

English language requirements are often used to specify the behavior of complex cyber-physical systems. The process of transforming these requirements to a formal specification language is often challenging, especially if the specification language does not contain constructs analogous to those used in the original requirements. For example, requirements often contain real-time constraints, but many specification languages for model checkers have discrete time semantics. Work in specification patterns helps to bridge these gaps, allowing straightforward expression of common requirements patterns in formal languages. In this work we demonstrate how we support real-time specification patterns in the Assume Guarantee Reasoning Environment (AGREE) using observers. We demonstrate that there are subtle challenges, not mentioned in previous literature, to express real-time patterns accurately using observers. We then demonstrate that these patterns are sufficient to model real-time requirements for a real-world avionics system.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Fußnoten
1
Although our formalisms are expressed as Lustre specifications, the concepts and proofs presented in this paper are applicable to many other popular model checking specification languages.
 
2
AGREE is available at: http://​loonwerks.​com.
 
3
In practice, we allow a timeout to be a negative number to represent infinity. This maintains the correct semantics for the constraint for t in Formula 1.
 
4
The single pattern that cannot be implemented requires an independent event to occur for each of an unbounded number of causes. There are 12 functional and timing RSL patterns in total.
 
Literatur
1.
Zurück zum Zitat Dwyer, M.B., Avrunin, G.S., Corbett, J.C.: Patterns in property specifications for finite-state verification. In: ICSE, pp. 411–420. IEEE (1999) Dwyer, M.B., Avrunin, G.S., Corbett, J.C.: Patterns in property specifications for finite-state verification. In: ICSE, pp. 411–420. IEEE (1999)
2.
Zurück zum Zitat Konrad, S., Cheng, B.H.: Real-time specification patterns. In: Proceedings of the 27th International Conference on Software Engineering, pp. 372–381. ACM (2005) Konrad, S., Cheng, B.H.: Real-time specification patterns. In: Proceedings of the 27th International Conference on Software Engineering, pp. 372–381. ACM (2005)
3.
Zurück zum Zitat Gruhn, V., Laue, R.: Patterns for timed property specifications. Electron. Notes Theoret. Comput. Sci. 153, 117–133 (2006)CrossRef Gruhn, V., Laue, R.: Patterns for timed property specifications. Electron. Notes Theoret. Comput. Sci. 153, 117–133 (2006)CrossRef
4.
Zurück zum Zitat Bellini, P., Nesi, P., Rogai, D.: Expressing and organizing real-time specification patterns via temporal logics. J. Syst. Softw. 82, 183–196 (2009)CrossRef Bellini, P., Nesi, P., Rogai, D.: Expressing and organizing real-time specification patterns via temporal logics. J. Syst. Softw. 82, 183–196 (2009)CrossRef
5.
Zurück zum Zitat Reinkemeier, P., Stierand, I., Rehkop, P., Henkler, S.: A pattern-based requirement specification language: mapping automotive specific timing requirements. In: Fachtagung des GI-Fachbereichs Softwaretechnik, pp. 99–108 (2011) Reinkemeier, P., Stierand, I., Rehkop, P., Henkler, S.: A pattern-based requirement specification language: mapping automotive specific timing requirements. In: Fachtagung des GI-Fachbereichs Softwaretechnik, pp. 99–108 (2011)
6.
Zurück zum Zitat Etzien, C., Gezgin, T., Froschle, S., Henkler, S., Rettberg, A.: Contracts for evolving systems. In: ISORC, pp. 1–8 (2013) Etzien, C., Gezgin, T., Froschle, S., Henkler, S., Rettberg, A.: Contracts for evolving systems. In: ISORC, pp. 1–8 (2013)
7.
Zurück zum Zitat Alur, R.: Techniques for automatic verification of real-time systems. Ph.D. thesis, stanford university (1991) Alur, R.: Techniques for automatic verification of real-time systems. Ph.D. thesis, stanford university (1991)
8.
Zurück zum Zitat Koymans, R.: Specifying real-time properties with metric temporal logic. Real-time Syst. 2, 255–299 (1990)CrossRef Koymans, R.: Specifying real-time properties with metric temporal logic. Real-time Syst. 2, 255–299 (1990)CrossRef
9.
Zurück zum Zitat Moser, L.E., Ramakrishna, Y., Kutty, G., Melliar-Smith, P.M., Dillon, L.K.: A graphical environment for the design of concurrent real-time systems. ACM Trans. Softw. Eng. Methodol. (TOSEM) 6, 31–79 (1997)CrossRef Moser, L.E., Ramakrishna, Y., Kutty, G., Melliar-Smith, P.M., Dillon, L.K.: A graphical environment for the design of concurrent real-time systems. ACM Trans. Softw. Eng. Methodol. (TOSEM) 6, 31–79 (1997)CrossRef
10.
Zurück zum Zitat Abid, N., Dal Zilio, S., Le Botlan, D.: Real-time specification patterns and tools. In: Stoelinga, M., Pinger, R. (eds.) FMICS 2012. LNCS, vol. 7437, pp. 1–15. Springer, Heidelberg (2012)CrossRef Abid, N., Dal Zilio, S., Le Botlan, D.: Real-time specification patterns and tools. In: Stoelinga, M., Pinger, R. (eds.) FMICS 2012. LNCS, vol. 7437, pp. 1–15. Springer, Heidelberg (2012)CrossRef
11.
Zurück zum Zitat Halbwachs, N., Caspi, P., Raymond, P., Pilaud, D.: The synchronous dataflow programming language LUSTRE. Proc. IEEE 79, 1305–1320 (1991)CrossRef Halbwachs, N., Caspi, P., Raymond, P., Pilaud, D.: The synchronous dataflow programming language LUSTRE. Proc. IEEE 79, 1305–1320 (1991)CrossRef
12.
Zurück zum Zitat Backes, J., Cofer, D., Miller, S., Whalen, M.W.: Requirements analysis of a quad-redundant flight control system. In: Havelund, K., Holzmann, G., Joshi, R. (eds.) NFM 2015. LNCS, vol. 9058, pp. 82–96. Springer, Heidelberg (2015) Backes, J., Cofer, D., Miller, S., Whalen, M.W.: Requirements analysis of a quad-redundant flight control system. In: Havelund, K., Holzmann, G., Joshi, R. (eds.) NFM 2015. LNCS, vol. 9058, pp. 82–96. Springer, Heidelberg (2015)
13.
Zurück zum Zitat Murugesan, A., Heimdahl, M.P., Whalen, M.W., Rayadurgam, S., Komp, J., Duan, L., Kim, B.G., Sokolsky, O., Lee, I.: From requirements to code: model based development of a medical cyber physical system. SEHC (2014) Murugesan, A., Heimdahl, M.P., Whalen, M.W., Rayadurgam, S., Komp, J., Duan, L., Kim, B.G., Sokolsky, O., Lee, I.: From requirements to code: model based development of a medical cyber physical system. SEHC (2014)
14.
Zurück zum Zitat Cofer, D., Gacek, A., Miller, S., Whalen, M.W., LaValley, B., Sha, L.: Compositional verification of architectural models. In: Goodloe, A.E., Person, S. (eds.) NFM 2012. LNCS, vol. 7226, pp. 126–140. Springer, Heidelberg (2012)CrossRef Cofer, D., Gacek, A., Miller, S., Whalen, M.W., LaValley, B., Sha, L.: Compositional verification of architectural models. In: Goodloe, A.E., Person, S. (eds.) NFM 2012. LNCS, vol. 7226, pp. 126–140. Springer, Heidelberg (2012)CrossRef
15.
Zurück zum Zitat Feiler, P.H., Gluch, D.P.: Model-Based Engineering with AADL: An Introduction to the SAE Architecture Analysis & Design Language, 1st edn. Addison-Wesley Professional, Reading (2012) Feiler, P.H., Gluch, D.P.: Model-Based Engineering with AADL: An Introduction to the SAE Architecture Analysis & Design Language, 1st edn. Addison-Wesley Professional, Reading (2012)
17.
Zurück zum Zitat Dutertre, B., Sorea, M.: Timed systems in SAL. Technical report, SRI International (2004) Dutertre, B., Sorea, M.: Timed systems in SAL. Technical report, SRI International (2004)
18.
Zurück zum Zitat Pike, L.: Real-time system verification by \(k\)-induction. Technical report, NASA (2005) Pike, L.: Real-time system verification by \(k\)-induction. Technical report, NASA (2005)
19.
Zurück zum Zitat Gao, J., Whalen, M., Van Wyk, E.: Extending lustre with timeout automata. In: SLA++P (2007) Gao, J., Whalen, M., Van Wyk, E.: Extending lustre with timeout automata. In: SLA++P (2007)
21.
Zurück zum Zitat Gómez, R., Bowman, H.: Efficient detection of zeno runs in timed automata. In: Raskin, J.-F., Thiagarajan, P.S. (eds.) FORMATS 2007. LNCS, vol. 4763, pp. 195–210. Springer, Heidelberg (2007)CrossRef Gómez, R., Bowman, H.: Efficient detection of zeno runs in timed automata. In: Raskin, J.-F., Thiagarajan, P.S. (eds.) FORMATS 2007. LNCS, vol. 4763, pp. 195–210. Springer, Heidelberg (2007)CrossRef
22.
Zurück zum Zitat Gafni, V., Benveniste, A., Caillaud, B., Graf, S., Josko, B.: Contract specification language (CSL). Technical report, SPEEDS Deliverable D.2.5.4 (2008) Gafni, V., Benveniste, A., Caillaud, B., Graf, S., Josko, B.: Contract specification language (CSL). Technical report, SPEEDS Deliverable D.2.5.4 (2008)
23.
Zurück zum Zitat Pike, L.: Modeling time-triggered protocols and verifying their real-time schedules. In: Formal Methods in Computer-Aided Design, pp. 231–238 (2007) Pike, L.: Modeling time-triggered protocols and verifying their real-time schedules. In: Formal Methods in Computer-Aided Design, pp. 231–238 (2007)
24.
Zurück zum Zitat Sorea, M., Dutertre, B., Steiner, W.: Modeling and verification of time-triggered communication protocols. In: 2008 11th IEEE International Symposium on Object Oriented Real-Time Distributed Computing (ISORC), pp. 422–428. IEEE (2008) Sorea, M., Dutertre, B., Steiner, W.: Modeling and verification of time-triggered communication protocols. In: 2008 11th IEEE International Symposium on Object Oriented Real-Time Distributed Computing (ISORC), pp. 422–428. IEEE (2008)
25.
Zurück zum Zitat Li, W., Grard, L., Shankar, N.: Design and verification of multi-rate distributed systems. In: 2015 ACM/IEEE International Conference on Formal Methods and Models for Codesign (MEMOCODE), pp. 20–29 (2015) Li, W., Grard, L., Shankar, N.: Design and verification of multi-rate distributed systems. In: 2015 ACM/IEEE International Conference on Formal Methods and Models for Codesign (MEMOCODE), pp. 20–29 (2015)
Metadaten
Titel
On Implementing Real-Time Specification Patterns Using Observers
verfasst von
John D. Backes
Michael W. Whalen
Andrew Gacek
John Komp
Copyright-Jahr
2016
DOI
https://doi.org/10.1007/978-3-319-40648-0_2