Skip to main content
Top

14-03-2024 | Special Section Paper

A lightweight approach to nontermination inference using Constrained Horn Clauses

Authors: Bishoksan Kafle, Graeme Gange, Peter Schachte, Harald Søndergaard, Peter J. Stuckey

Published in: Software and Systems Modeling

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

Nontermination is an unwanted program property for some software systems, and a safety property for other systems. In either case, automated discovery of preconditions for nontermination is of interest. We introduce NtHorn, a fast lightweight nontermination analyser, which is able to deduce non-trivial sufficient conditions for nontermination. Using Constrained Horn Clauses (CHCs) as a vehicle, we show how established techniques for CHC program transformation and abstract interpretation can be exploited for the purpose of nontermination analysis. NtHorn is comparable in effectiveness to the state-of-the-art nontermination analysis tools, as measured on standard competition benchmark suites (consisting of integer manipulating programs), while typically solving problems faster by one order of magnitude.

Dont have a licence yet? Then find out more about our products and how to get one now:

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 "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!

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!

Footnotes
1
A comma to the right of the arrow in a CHC denotes conjunction, and conjunction binds tighter than the arrow.
 
2
We use \(\forall (\varphi )\) for the universal closure of formula \(\varphi \), that is, \(\forall V (\varphi )\), where V is the set of free variables in \(\varphi \).
 
3
Readers familiar with predicative programming a la Hehner [38], may prefer to rename \(\texttt{d}\) in \(c_1\) to \(\texttt{a}'\) (and similarly rewrite other clauses), to support the reading “value of \(\texttt{a}\) after the assignment”.
 
Literature
2.
go back to reference Chen, H.Y., Cook, B., Fuhs, C., Nimkar, K., O’Hearn, P.W.: Proving nontermination via safety. In: Ábrahám, E., Havelund, K. (eds.) Tools and Algorithms for the Construction and Analysis of Systems. LNCS, vol. 8413, pp. 156–171. Springer, Berlin Heidelberg (2014). https://doi.org/10.1007/978-3-642-54862-8_11 Chen, H.Y., Cook, B., Fuhs, C., Nimkar, K., O’Hearn, P.W.: Proving nontermination via safety. In: Ábrahám, E., Havelund, K. (eds.) Tools and Algorithms for the Construction and Analysis of Systems. LNCS, vol. 8413, pp. 156–171. Springer, Berlin Heidelberg (2014). https://​doi.​org/​10.​1007/​978-3-642-54862-8_​11
4.
go back to reference Cousot, P.: Principles of abstract interpretation. MIT Press, Cambridge MA (2021) Cousot, P.: Principles of abstract interpretation. MIT Press, Cambridge MA (2021)
5.
go back to reference Borralleras, C., Brockschmidt, M., Larraz, D., Oliveras, A., Rodríguez-Carbonell, E., Rubio, A.: Proving termination through conditional termination. In: Legay, A., Margaria, T. (eds.) Tools and Algorithms for the Construction and Analysis of Systems. LNCS, vol. 10205, pp. 99–117. Springer, Berlin Heidelberg (2017). https://doi.org/10.1007/978-3-662-54577-5_6 Borralleras, C., Brockschmidt, M., Larraz, D., Oliveras, A., Rodríguez-Carbonell, E., Rubio, A.: Proving termination through conditional termination. In: Legay, A., Margaria, T. (eds.) Tools and Algorithms for the Construction and Analysis of Systems. LNCS, vol. 10205, pp. 99–117. Springer, Berlin Heidelberg (2017). https://​doi.​org/​10.​1007/​978-3-662-54577-5_​6
12.
go back to reference Bakhirkin, A., Berdine, J., Piterman, N.: Backward analysis via over-approximate abstraction and under-approximate subtraction of Horn clauses. In: Müller-Olm, M., Seidl, H. (eds.) Static Analysis. LNCS, vol. 8723, pp. 34–50. Springer, Berlin Heidelberg (2014). https://doi.org/10.1007/978-3-319-10936-7_3 Bakhirkin, A., Berdine, J., Piterman, N.: Backward analysis via over-approximate abstraction and under-approximate subtraction of Horn clauses. In: Müller-Olm, M., Seidl, H. (eds.) Static Analysis. LNCS, vol. 8723, pp. 34–50. Springer, Berlin Heidelberg (2014). https://​doi.​org/​10.​1007/​978-3-319-10936-7_​3
14.
go back to reference Le, T.C., Qin, S., Chin, W.-N.: Termination and non-termination specification inference. In: Grove, D., Blackburn, S.M. (eds.) Proc. 36th ACM SIGPLAN Conf. Programming Language Design and Implementation, pp. 489–498. ACM, New York (2015). https://doi.org/10.1145/2737924.2737993 Le, T.C., Qin, S., Chin, W.-N.: Termination and non-termination specification inference. In: Grove, D., Blackburn, S.M. (eds.) Proc. 36th ACM SIGPLAN Conf. Programming Language Design and Implementation, pp. 489–498. ACM, New York (2015). https://​doi.​org/​10.​1145/​2737924.​2737993
15.
go back to reference Kafle, B., Gange, G., Schachte, P., Søndergaard, H., Stuckey, P.J.: Lightweight nontermination inference with CHCs. In: Calinescu, R., Păsăreanu, C.S. (eds.) Software Engineering and Formal Methods. LNCS, vol. 13085, pp. 383–402. Springer, Switzerland (2021). https://doi.org/10.1007/978-3-030-92124-8_22 Kafle, B., Gange, G., Schachte, P., Søndergaard, H., Stuckey, P.J.: Lightweight nontermination inference with CHCs. In: Calinescu, R., Păsăreanu, C.S. (eds.) Software Engineering and Formal Methods. LNCS, vol. 13085, pp. 383–402. Springer, Switzerland (2021). https://​doi.​org/​10.​1007/​978-3-030-92124-8_​22
16.
go back to reference Chatterjee, K., Goharshady, E.K., Novotný, P., Žikelić, D.: Proving non-termination by program reversal. In: Freund, S.N., Yahav, E. (eds.) Proc. 42nd ACM SIGPLAN Conf. Programming Language Design and Implementation, pp. 1033–1048. ACM, New York (2021). https://doi.org/10.1145/3453483.3454093 Chatterjee, K., Goharshady, E.K., Novotný, P., Žikelić, D.: Proving non-termination by program reversal. In: Freund, S.N., Yahav, E. (eds.) Proc. 42nd ACM SIGPLAN Conf. Programming Language Design and Implementation, pp. 1033–1048. ACM, New York (2021). https://​doi.​org/​10.​1145/​3453483.​3454093
17.
go back to reference Cousot, P., Cousot, R., Fähndrich, M., Logozzo, F.: Automatic inference of necessary preconditions. In: Giacobazzi, R., Berdine, J., Mastroeni, I. (eds.) Verification, Model Checking and Abstract Interpretation. LNCS, vol. 7737, pp. 128–148. Springer, Berlin Heidelberg (2013). https://doi.org/10.1007/978-3-642-35873-9_10 Cousot, P., Cousot, R., Fähndrich, M., Logozzo, F.: Automatic inference of necessary preconditions. In: Giacobazzi, R., Berdine, J., Mastroeni, I. (eds.) Verification, Model Checking and Abstract Interpretation. LNCS, vol. 7737, pp. 128–148. Springer, Berlin Heidelberg (2013). https://​doi.​org/​10.​1007/​978-3-642-35873-9_​10
18.
go back to reference Bakhirkin, A.: Recurrent sets for non-termination and safety of programs. PhD thesis, University of Leicester (2016) Bakhirkin, A.: Recurrent sets for non-termination and safety of programs. PhD thesis, University of Leicester (2016)
23.
go back to reference Gallagher, J.P.: Polyvariant program specialisation with property-based abstraction. In: Lisitsa, A., Nemytykh, A.P. (eds.) Proc. Seventh Int. Workshop on Verification and Program Transformation. EPTCS, vol. 299, pp. 34–48 (2019). https://doi.org/10.4204/EPTCS.299.6 Gallagher, J.P.: Polyvariant program specialisation with property-based abstraction. In: Lisitsa, A., Nemytykh, A.P. (eds.) Proc. Seventh Int. Workshop on Verification and Program Transformation. EPTCS, vol. 299, pp. 34–48 (2019). https://​doi.​org/​10.​4204/​EPTCS.​299.​6
26.
27.
go back to reference Méndez-Lojo, M., Navas, J.A., Hermenegildo, M.V.: A flexible, (C)LP-based approach to the analysis of object-oriented programs. In: King, A. (ed.) Logic-Based Program Synthesis and Transformation. LNCS, vol. 4915, pp. 154–168. Springer, Berlin Heidelberg (2007). https://doi.org/10.1007/978-3-540-78769-3_11 Méndez-Lojo, M., Navas, J.A., Hermenegildo, M.V.: A flexible, (C)LP-based approach to the analysis of object-oriented programs. In: King, A. (ed.) Logic-Based Program Synthesis and Transformation. LNCS, vol. 4915, pp. 154–168. Springer, Berlin Heidelberg (2007). https://​doi.​org/​10.​1007/​978-3-540-78769-3_​11
29.
go back to reference Grebenshchikov, S., Lopes, N.P., Popeea, C., Rybalchenko, A.: Synthesizing software verifiers from proof rules. In: Vitek, J., Lin, H., Tip, F. (eds.) Proc. 33rd ACM SIGPLAN Conf. Programming Language Design and Implementation, pp. 405–416. ACM, New York (2012). https://doi.org/10.1145/2254064.2254112 Grebenshchikov, S., Lopes, N.P., Popeea, C., Rybalchenko, A.: Synthesizing software verifiers from proof rules. In: Vitek, J., Lin, H., Tip, F. (eds.) Proc. 33rd ACM SIGPLAN Conf. Programming Language Design and Implementation, pp. 405–416. ACM, New York (2012). https://​doi.​org/​10.​1145/​2254064.​2254112
32.
go back to reference Perez-Carrasco, V., Klemen, M., López-García, P., Morales, J.F., Hermenegildo, M.V.: Cost analysis of smart contracts via parametric resource analysis. In: Pichardie, D., Sighireanu, M. (eds.) Static Analysis. LNCS, vol. 12389, pp. 7–31. Springer, Switzerland (2020). https://doi.org/10.1007/978-3-030-65474-0_2 Perez-Carrasco, V., Klemen, M., López-García, P., Morales, J.F., Hermenegildo, M.V.: Cost analysis of smart contracts via parametric resource analysis. In: Pichardie, D., Sighireanu, M. (eds.) Static Analysis. LNCS, vol. 12389, pp. 7–31. Springer, Switzerland (2020). https://​doi.​org/​10.​1007/​978-3-030-65474-0_​2
35.
go back to reference Marriott, K., Stuckey, P.J.: Programming with Constraints: An Introduction. MIT Press, Cambridge MA (1998) Marriott, K., Stuckey, P.J.: Programming with Constraints: An Introduction. MIT Press, Cambridge MA (1998)
38.
go back to reference Hehner, E.: A Practical Theory of Programming. Springer, New York NY (1993) Hehner, E.: A Practical Theory of Programming. Springer, New York NY (1993)
39.
go back to reference Cousot, P., Cousot, R.: Abstract interpretation: a unified lattice model for static analysis of programs by construction or approximation of fixpoints. In: Proc. Fourth ACM Symp. Principles of Programming Languages, pp. 238–252. ACM, New York (1977). https://doi.org/10.1145/512950.512973 Cousot, P., Cousot, R.: Abstract interpretation: a unified lattice model for static analysis of programs by construction or approximation of fixpoints. In: Proc. Fourth ACM Symp. Principles of Programming Languages, pp. 238–252. ACM, New York (1977). https://​doi.​org/​10.​1145/​512950.​512973
40.
go back to reference Cousot, P., Cousot, R.: Comparing the Galois connection and widening/narrowing approaches to abstract interpretation. In: Bruynooghe, M., Wirsing, M. (eds.) Programming Language Implementation and Logic Programming. LNCS, vol. 631, pp. 269–295. Springer, Berlin Heidelberg (1992). https://doi.org/10.1007/3-540-55844-6_142 Cousot, P., Cousot, R.: Comparing the Galois connection and widening/narrowing approaches to abstract interpretation. In: Bruynooghe, M., Wirsing, M. (eds.) Programming Language Implementation and Logic Programming. LNCS, vol. 631, pp. 269–295. Springer, Berlin Heidelberg (1992). https://​doi.​org/​10.​1007/​3-540-55844-6_​142
41.
go back to reference Cousot, P., Halbwachs, N.: Automatic discovery of linear restraints among variables of a program. In: Aho, A.V., Zilles, S.N., Szymanski, T.G. (eds.) Proc. Fifth ACM Symp. Principles of Programming Languages, pp. 84–96. ACM, New York (1978). https://doi.org/10.1145/512760.512770 Cousot, P., Halbwachs, N.: Automatic discovery of linear restraints among variables of a program. In: Aho, A.V., Zilles, S.N., Szymanski, T.G. (eds.) Proc. Fifth ACM Symp. Principles of Programming Languages, pp. 84–96. ACM, New York (1978). https://​doi.​org/​10.​1145/​512760.​512770
42.
go back to reference Bancilhon, F., Maier, D., Sagiv, Y., Ullman, J.D.: Magic sets and other strange ways to implement logic programs. In: Silberschatz, A. (ed.) Proc. Fifth ACM SIGMOD-SIGACT Symp. Principles of Database Systems, pp. 1–15. ACM, New York (1986). https://doi.org/10.1145/6012.15399 Bancilhon, F., Maier, D., Sagiv, Y., Ullman, J.D.: Magic sets and other strange ways to implement logic programs. In: Silberschatz, A. (ed.) Proc. Fifth ACM SIGMOD-SIGACT Symp. Principles of Database Systems, pp. 1–15. ACM, New York (1986). https://​doi.​org/​10.​1145/​6012.​15399
44.
45.
go back to reference Podelski, A., Rybalchenko, A.: A complete method for the synthesis of linear ranking functions. In: Steffen, B., Levi, G. (eds.) Verification, Model Checking and Abstract Interpretation. LNCS, vol. 2937, pp. 239–251. Springer, Berlin Heidelberg (2004). https://doi.org/10.1007/978-3-540-24622-0_20 Podelski, A., Rybalchenko, A.: A complete method for the synthesis of linear ranking functions. In: Steffen, B., Levi, G. (eds.) Verification, Model Checking and Abstract Interpretation. LNCS, vol. 2937, pp. 239–251. Springer, Berlin Heidelberg (2004). https://​doi.​org/​10.​1007/​978-3-540-24622-0_​20
46.
go back to reference Sohn, K., Van Gelder, A.: Termination detection in logic programs using argument sizes. In: Rosenkrantz, D.J. (ed.) Proc. Tenth ACM SIGACT-SIGMOD-SIGART Symp. Principles of Database Systems, pp. 216–226. ACM, New York (1991). https://doi.org/10.1145/113413.113433 Sohn, K., Van Gelder, A.: Termination detection in logic programs using argument sizes. In: Rosenkrantz, D.J. (ed.) Proc. Tenth ACM SIGACT-SIGMOD-SIGART Symp. Principles of Database Systems, pp. 216–226. ACM, New York (1991). https://​doi.​org/​10.​1145/​113413.​113433
51.
go back to reference Kafle, B., Gallagher, J.P., Morales, J.F.: RAHFT: A tool for verifying Horn clauses using abstract interpretation and finite tree automata. In: Chaudhuri, S., Farzan, A. (eds.) Computer-Aided Verification. LNCS, vol. 9779, pp. 261–268. Springer, Berlin Heidelberg (2016). https://doi.org/10.1007/978-3-319-41528-4_14 Kafle, B., Gallagher, J.P., Morales, J.F.: RAHFT: A tool for verifying Horn clauses using abstract interpretation and finite tree automata. In: Chaudhuri, S., Farzan, A. (eds.) Computer-Aided Verification. LNCS, vol. 9779, pp. 261–268. Springer, Berlin Heidelberg (2016). https://​doi.​org/​10.​1007/​978-3-319-41528-4_​14
52.
54.
go back to reference Brockschmidt, M., Ströder, T., Otto, C., Giesl, J.: Automated detection of non-termination and NullPointerExceptions for Java bytecode. In: Beckert, B., Damiani, F., Gurov, D. (eds.) Formal Verification of Object-Oriented Software. LNCS, vol. 7421, pp. 123–141. Springer, Berlin Heidelberg (2012). https://doi.org/10.1007/978-3-642-31762-0_9 Brockschmidt, M., Ströder, T., Otto, C., Giesl, J.: Automated detection of non-termination and NullPointerExceptions for Java bytecode. In: Beckert, B., Damiani, F., Gurov, D. (eds.) Formal Verification of Object-Oriented Software. LNCS, vol. 7421, pp. 123–141. Springer, Berlin Heidelberg (2012). https://​doi.​org/​10.​1007/​978-3-642-31762-0_​9
58.
go back to reference Leuschel, M., Lehmann, H.: Solving coverability problems of Petri nets by partial deduction. In: Gabbrielli, M., Pfenning, F. (eds.) Proc. Second Int. ACM SIGPLAN Conf. Principles and Practice of Declarative Programming, pp. 268–279. ACM, New York (2000). https://doi.org/10.1145/351268.351298 Leuschel, M., Lehmann, H.: Solving coverability problems of Petri nets by partial deduction. In: Gabbrielli, M., Pfenning, F. (eds.) Proc. Second Int. ACM SIGPLAN Conf. Principles and Practice of Declarative Programming, pp. 268–279. ACM, New York (2000). https://​doi.​org/​10.​1145/​351268.​351298
64.
go back to reference Komuravelli, A., Gurfinkel, A., Chaki, S., Clarke, E.M.: Automatic abstraction in SMT-based unbounded software model checking. In: Sharygina, N., Veith, H. (eds.) Computer-Aided Verification. LNCS, vol. 8044, pp. 846–862. Springer, Berlin Heidelberg (2013). https://doi.org/10.1007/978-3-642-39799-8_59 Komuravelli, A., Gurfinkel, A., Chaki, S., Clarke, E.M.: Automatic abstraction in SMT-based unbounded software model checking. In: Sharygina, N., Veith, H. (eds.) Computer-Aided Verification. LNCS, vol. 8044, pp. 846–862. Springer, Berlin Heidelberg (2013). https://​doi.​org/​10.​1007/​978-3-642-39799-8_​59
66.
go back to reference De Angelis, E., Fioravanti, F., Pettorossi, A., Proietti, M.: VeriMAP: A tool for verifying programs through transformations. In: Ábrahám, E., Havelund, K. (eds.) Tools and Algorithms for the Construction and Analysis of Systems. LNCS, vol. 8413, pp. 568–574. Springer, Berlin Heidelberg (2014). https://doi.org/10.1007/978-3-642-54862-8_47 De Angelis, E., Fioravanti, F., Pettorossi, A., Proietti, M.: VeriMAP: A tool for verifying programs through transformations. In: Ábrahám, E., Havelund, K. (eds.) Tools and Algorithms for the Construction and Analysis of Systems. LNCS, vol. 8413, pp. 568–574. Springer, Berlin Heidelberg (2014). https://​doi.​org/​10.​1007/​978-3-642-54862-8_​47
69.
go back to reference Le, T.C., Antonopoulos, T., Fathololumi, P., Koskinen, E., Nguyen, T.: DynamiTe: Dynamic termination and non-termination proofs. In: Proc. ACM Program. Lang. 4, OOPSLA, pp. 1–30. ACM, New York (2020). https://doi.org/10.1145/3428257 Le, T.C., Antonopoulos, T., Fathololumi, P., Koskinen, E., Nguyen, T.: DynamiTe: Dynamic termination and non-termination proofs. In: Proc. ACM Program. Lang. 4, OOPSLA, pp. 1–30. ACM, New York (2020). https://​doi.​org/​10.​1145/​3428257
70.
Metadata
Title
A lightweight approach to nontermination inference using Constrained Horn Clauses
Authors
Bishoksan Kafle
Graeme Gange
Peter Schachte
Harald Søndergaard
Peter J. Stuckey
Publication date
14-03-2024
Publisher
Springer Berlin Heidelberg
Published in
Software and Systems Modeling
Print ISSN: 1619-1366
Electronic ISSN: 1619-1374
DOI
https://doi.org/10.1007/s10270-024-01161-5

Premium Partner