Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Bücher
Zeitschriften
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
ATZ-Fachkongress

Chassis.tech plus 2024


4 Kongresse in einer Veranstaltung

Treffen Sie in München die Fachleute von Chassis, Lenkung, Bremsen sowie Reifen/Räder.
Erweiterte Suche
Anmelden
nach oben
Erschienen in:
A Trusted Mechanised Specification of JavaScript: One Year On Kapitel lesen Erstes Kapitel lesen

2015 | OriginalPaper | Buchkapitel

On Automation of CTL* Verification for Infinite-State Systems

verfasst von : Byron Cook, Heidy Khlaaf, Nir Piterman

Erschienen in: Computer Aided Verification

Verlag: Springer International Publishing

Einloggen

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

search-config
loading …

Abstract

In this paper we introduce the first known fully automated tool for symbolically proving CTL \(^*\) properties of (infinite-state) integer programs. The method uses an internal encoding which facilitates reasoning about the subtle interplay between the nesting of path and state temporal operators that occurs within CTL \(^*\) proofs. A precondition synthesis strategy is then used over a program transformation which trades nondeterminism in the transition relation for nondeterminism explicit in variables predicting future outcomes when necessary. We show the viability of our approach in practice using examples drawn from device drivers and various industrial examples.

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!

Jetzt informieren

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!

Jetzt informieren

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!

Jetzt informieren
Vorheriges Kapitel A Trusted Mechanised Specification of JavaScript: One Year On
Nächstes Kapitel Algorithms for Model Checking HyperLTL and HyperCTL
Fußnoten
1
A CTL is the universal subset of CTL where one can only address all possible paths with the universal quantifier A (e.g. A G or A F), but not the existence of some paths with E (e.g. E G or E F).
 
2
The source-code of our implementation and our benchmarks are available under the MIT open-source license at https://​github.​com/​hkhlaaf/​T2/​tree/​T2Star.
 
Literatur
1.
2.
Beyene, T., Chaudhuri, S., Popeea, C., Rybalchenko, A.: A constraint-based approach to solving games on infinite graphs. In: POPL 2014, pp. 221–233. ACM (2014)
3.
Beyene, T.A., Popeea, C., Rybalchenko, A.: Solving existentially quantified horn clauses. In: Sharygina, N., Veith, H. (eds.) CAV 2013. LNCS, vol. 8044, pp. 869–882. Springer, Heidelberg (2013) CrossRef
4.
Bjørner, N.S., Browne, A., Colón, M.A., Finkbeiner, B., Manna, Z., Sipma, H.B., Uribe, T.E.: Verifying temporal properties of reactive systems: a STeP tutorial. Form. Methods Syst. Des. 16(3), 227–270 (2000)CrossRef
5.
Bodden, E.: A lightweight LTL runtime verification tool for Java. In: OOPSLA 2004, pp. 306–307. ACM (2004)
6.
Cook, B., Khlaaf, H., Piterman, N.: Fairness for infinite-state systems. In: Baier, C., Tinelli, C. (eds.) TACAS 2015. LNCS, vol. 9035, pp. 384–398. Springer, Heidelberg (2015)
7.
8.
Cook, B., Koskinen, E.: Reasoning about nondeterminism in programs. In: PLDI 2013, pp. 219–230. ACM (2013)
9.
Cook, B., See, A., Zuleger, F.: Ramsey vs. lexicographic termination proving. In: Piterman, N., Smolka, S.A. (eds.) TACAS 2013 (ETAPS 2013). LNCS, vol. 7795, pp. 47–61. Springer, Heidelberg (2013) CrossRef
10.
Cook, B., Gotsman, A., Podelski, A., Rybalchenko, A., Vardi, M.Y.: Proving that programs eventually do something good. In: POPL 2007, pp. 265–276. ACM (2007)
11.
Cook, B., Khlaaf, H., Piterman, N.: Faster temporal reasoning for infinite-state programs. In: FMCAD 2014, pp. 16:75–16:82. FMCAD Inc. (2014)
12.
Cook, B., Koskinen, E.: Making prophecies with decision predicates. In: POPL 2011, pp. 399–410. ACM (2011)
13.
Cormen, T.H., Stein, C., Rivest, R.L., Leiserson, C.E.: Introduction to Algorithms, 2nd edn. McGraw-Hill Higher Education, Boston (2001)MATH
14.
Emerson, E.A., Halpern, J.Y.: “Sometimes" and “Not Never"; revisited: on branching versus linear time temporal logic. J. ACM 33(1), 151–178 (1986)MathSciNetCrossRefMATH
15.
16.
Emerson, E.A., Lei, C.-L.: Modalities for model checking: branching time logic strikes back. Sci. Comput. Program. 8(3), 275–306 (1987)MathSciNetCrossRefMATH
17.
Emerson, E.A., Sistla, A.P.: Deciding branching time logic. In: STOC 1984, pp. 14–24. ACM (1984)
18.
Griffault, A., Vincent, A.: The Mec 5 model-checker. In: Alur, R., Peled, D.A. (eds.) CAV 2004. LNCS, vol. 3114, pp. 488–491. Springer, Heidelberg (2004) CrossRef
19.
Gupta, A., Henzinger, T.A., Majumdar, R., Rybalchenko, A., Xu, R.-G.: Proving non-termination. SIGPLAN Not. 43, 147–158 (2008)CrossRef
20.
21.
Lamport, L.: “Sometime” is sometimes “Not Never”: on the temporal logic of programs. In: POPL 1980, pp. 174–185. ACM (1980)
22.
Magill, S., Berdine, J., Clarke, E., Cook, B.: Arithmetic strengthening for shape analysis. In: Riis Nielson, H., Filé, G. (eds.) SAS 2007. LNCS, vol. 4634, pp. 419–436. Springer, Heidelberg (2007) CrossRef
23.
Manna, Z., Pnueli, A.: Temporal Verification of Reactive Systems: Safety, vol. 2. Springer, Heidelberg (1995)CrossRef
24.
McMillan, K.L.: Lazy abstraction with interpolants. In: Ball, T., Jones, R.B. (eds.) CAV 2006. LNCS, vol. 4144, pp. 123–136. Springer, Heidelberg (2006) CrossRef
25.
Podelski, A., Rybalchenko, A.: Transition invariants. In: LICS, pp. 32–41. IEEE, Turku, Finland (2004)
26.
27.
Song, F., Touili, T.: Pushdown model checking for malware detection. In: Flanagan, C., König, B. (eds.) TACAS 2012. LNCS, vol. 7214, pp. 110–125. Springer, Heidelberg (2012) CrossRef
Metadaten
Titel
On Automation of CTL* Verification for Infinite-State Systems
verfasst von
Byron Cook
Heidy Khlaaf
Nir Piterman
Copyright-Jahr
2015
Buch
Computer Aided Verification

Print ISBN: 978-3-319-21689-8

Electronic ISBN: 978-3-319-21690-4

Copyright-Jahr: 2015

DOI
https://doi.org/10.1007/978-3-319-21690-4_2

Premium Partner

    Bildnachweise