Hostname: page-component-586b7cd67f-t8hqh Total loading time: 0 Render date: 2024-11-28T00:01:52.809Z Has data issue: false hasContentIssue false
  • English
  • Français

A light-weight integration of automated and interactive theorem proving

Published online by Cambridge University Press:  12 November 2014

KARIM KANSO  and
ANTON SETZER
KARIM KANSO
Affiliation:
Department of Computer Science, Swansea University, Swansea, SA2 8PP, United Kindgom Email: [email protected], [email protected]
ANTON SETZER
Affiliation:
Department of Computer Science, Swansea University, Swansea, SA2 8PP, United Kindgom Email: [email protected], [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

In this paper, aimed at dependently typed programmers, we present a novel connection between automated and interactive theorem proving paradigms. The novelty is that the connection offers a better trade-off between usability, efficiency and soundness when compared to existing techniques. This technique allows for a powerful interactive proof framework that facilitates efficient verification of finite domain theorems and guided construction of the proof of infinite domain theorems. Such situations typically occur with industrial verification. As a case study, an embedding of SAT and CTL model checking is presented, both of which have been implemented for the dependently typed proof assistant Agda.

Finally, an example of a real world railway control system is presented, and shown using our proof framework to be safe with respect to an abstract model of trains not colliding or derailing. We demonstrate how to formulate safety directly and show using interactive theorem proving that signalling principles imply safety. Therefore, a proof by an automated theorem prover that the signalling principles hold for a concrete system implies the overall safety. Therefore, instead of the need for domain experts to validate that the signalling principles imply safety they only need to make sure that the safety is formulated correctly. Therefore, some of the validation is replaced by verification using interactive theorem proving.

Type
Paper
Information
Mathematical Structures in Computer Science , Volume 26 , Special Issue 1: Special Issue: Dependently Typed Programming , January 2016 , pp. 129 - 153
Copyright
Copyright © Cambridge University Press 2014 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Abrial, J. R., Butler, M., Hallerstede, S. and Voisin, L. (2006) An open extensible tool environment for event-B. In: Liu, Z. and He, J. (eds.) Formal Methods and Software Engineering. Springer Lecture Notes in Computer Science 4260 588–605.Google Scholar
Armand, M., Grégoire, B., Spiwack, A. and Théry, L. (2010) Extending Coq with imperative features and its application to SAT verification. In: Kaufmann, M. and Paulson, L. (eds.) Interactive Theorem Proving. Springer Lecture Notes in Computer Science 6172 83–98.CrossRefGoogle Scholar
Bar-Hillel, Y., Perles, M. and Shamir, E. (1964) On formal properties of simple phrase structure grammars. In: Language and Information: Selected Essays on their Theory and Application 116–150.Google Scholar
Barrett, C., Sebastiani, R., Seshia, S. A. and Tinelli, C. (2009) Satisfiability modulo theories. In: Biere, A., Heule, M., van Maaren, H. and Walsh, T. (eds.) Handbook of Satisfiability, volume 185, IOS Press 737–797.Google Scholar
Bierman, G. M., Gordon, A. D., Hriţcu, C. and Langworthy, D. (2010) Semantic subtyping with an SMT solver. In: Proceedings of the 15th ACM SIGPLAN International Conference on Functional Programming, ACM 105–116.CrossRefGoogle Scholar
Böhme, S. and Nipkow, T. (2010) Sledgehammer: Judgement day. In: Giesl, J. and Hähnle, R. (eds.) Automated Reasoning. Lecture Notes in Computer Science 6173 107–121.CrossRefGoogle Scholar
Boutin, S. (1997) Using reflection to build efficient and certified decision procedures. In: Theoretical Aspects of Computer Software. Springer Lecture Notes in Computer Science 1281 515–529.Google Scholar
Bove, A., Dybjer, P. and Norell, U. (2009) A brief overview of Agda – a functional language with dependent types. In: Berghofer, S., Nipkow, T., Urban, C. and Wenzel, M. (eds.) Theorem Proving in Higher Order Logics. Springer Lecture Notes in Computer Science 5674 73–78.Google Scholar
Curry, H. B. (1934) Functionality in combinatory logic. In: Proceedings of the National Academy of Sciences of the United States of America 20 (11) 584.Google Scholar
Curry, H. B., Feys, R., Craig, W. and Craig, W. (1958) Combinatory Logic, volume 1, North-Holland.Google Scholar
Davis, M., Putnam, H. and Robinson, J. (1961) The decision problem for exponential diophantine equations. The Annals of Mathematics 74 (3) 425–436.Google Scholar
de Bruijn, N. (1970) The mathematical language AUTOMATH, its usage, and some of its extensions. In: Laudet, M., Lacombe, D., Nolin, L. and Schtzenberger, M. (eds.) Symposium on Automatic Demonstration. Springer Lecture Notes in Computer Science 125 29–61.Google Scholar
De Moura, L. and Bjørner, N. (2009) Satisfiability modulo theories: An appetizer. In: Formal Methods: Foundations and Applications 23–36.Google Scholar
Dedekind, R. (1863) Vorlesungen über Zahlentheorie, F. Vieweg und Sohn.Google Scholar
Diller, J. and Troelstra, A. S. (1984) Realizability and intuitionistic logic. Synthese 60 253–282.Google Scholar
Dong, Y., Ramakrishnan, C. R. and Smolka, S. A. (2003) Model checking and evidence exploration. In: Proceedings of 10th IEEE International Conference and Workshop on the Engineering of Computer-Based Systems 214–223.Google Scholar
Fontaine, P., Marion, J. Y., Merz, S., Nieto, L. and Tiu, A. (2006) Expressiveness+ automation+ soundness: Towards combining SMT solvers and interactive proof assistants. In: Tools and Algorithms for the Construction and Analysis of Systems 167–181.Google Scholar
Foster, S. and Struth, G. (2011) Integrating an automated theorem prover into Agda. In: Bobaru, M., Havelund, K., Holzmann, G. and Joshi, R. (eds.) NASA Formal Methods. Springer Lecture Notes in Computer Science 6617 116–130.Google Scholar
Harrison, J. (2008) Automated and interactive theorem proving. In: Grumberg, O., Nipkow, T. and Pfaller, C. (eds.) Formal Logical Methods for System Security and Correctness. NATO Science for Peace and Security Series 14 111–147.Google Scholar
Hendriks, D. (2002) Proof reflection in coq Journal of Automated Reasoning 29 (3) 277–307.Google Scholar
Howard, W. A. (1980) The formulae-as-types notion of construction. To HB Curry: Essays on Combinatory Logic, Lambda Calculus and Formalism 44 479–490.Google Scholar
Huth, M. and Ryan, M. (2004) Logic in Computer Science, Cambridge University Press Cambridge.Google Scholar
Jones, C. B., Grov, G. and Bundy, A. (2010) Ideas for a high-level proof strategy language, Technical Report CS-TR-1210, Newcastle University.Google Scholar
Kanso, K. (2008) Formal Verification of Ladder Logic, Master's thesis, Department of Computer Science, Swansea University.Google Scholar
Kanso, K., Moller, F. and Setzer, A. (2009) Automated verification of signalling principles in railway interlocking systems. Electronic Notes in Theoretical Computer Science 250 (2) 19–31.Google Scholar
Kerr, D. and Rowbotham, T. (2001) Introduction to Railway Signalling, Institution of Railway Signal Engineers.Google Scholar
Leach, M. (2003) RAILWAY Control Systems, 2nd edition, Institution of Railway Signal Engineers.Google Scholar
Lescuyer, S. and Conchon, S. (2008) A reflexive formalization of a SAT solver in coq. In: TPHOLs 2008: Emerging Trends of the 21st International Conference on Theorem Proving in Higher Order Logics.Google Scholar
Müller, O. and Nipkow, T. (1995) Combining model checking and deduction for i/o- automata. In: Brinksma, E., Cleaveland, W., Larsen, K., Margaria, T. and Steffen, B. (eds.) Tools and Algorithms for the Construction and Analysis of Systems. Springer Lecture Notes in Computer Science 1019 1–16.Google Scholar
Nock, O. S. (2002) Railway Signalling, 2nd edition, Institution of Railway Signal Engineers.Google Scholar
Nordström, B., Petersson, K. and Smith, J. M. (1990) Programming in Martin-Löf's Type Theory, International Series of Monographs on Computer Science, volume 7, Oxford University Press.Google Scholar
Owre, S., Rushby, J. and Shankar, N. (1992) PVS: A prototype verification system. In: Kapur, D. (ed.) Automated Deduction CADE-11. Springer Lecture Notes in Computer Science 607 748–752.Google Scholar
Paulson, L. and Susanto, K. (2007) Source-level proof reconstruction for interactive theorem proving In: Schneider, K. and Brandt, J. (eds.) Theorem Proving in Higher Order Logics. Lecture Notes in Computer Science 4732 232–245.Google Scholar
Stump, A. (2009) Proof checking technology for satisfiability modulo theories. Electronic Notes in Theoretical Computer Science 228 121–133.Google Scholar
Sutcliffe, G. (2009) The TPTP problem library and associated infrastructure: The FOF and CNF parts, v3.5.0. Journal of Automated Reasoning 43 (4) 337–362.CrossRefGoogle Scholar
Verma, K. N. (2000) Reflecting Symbolic Model Checking in coq , Master's thesis, Mémoire de DEA, DEA Programmation, Paris.Google Scholar
Weber, T. (2006) Integrating a SAT solver with an LCF-style theorem prover. In: Proceedings of the 3rd Workshop on Pragmatics of Decision Procedures in Automated Reasoning (PDPAR 2005). Electronic Notes in Theoretical Computer Science 144 (2) 67–78.Google Scholar
Woodbridge, P. (2011) Locking frame testing. Available at http://www.signalbox.org/branches/pw/index.htm Google Scholar
Woodcock, J., Larsen, P. G., Bicarregui, J. and Fitzgerald, J. (2009) Formal methods: Practice and experience. ACM Computing Surveys (CSUR) 41 (4) 1–36.Google Scholar