Passer à la navigation principale Passer à la recherche Passer au contenu principal

C-SHORe: A collapsible approach to verifying higher-order programs

  • Christopher Broadbent
  • , Arnaud Carayol
  • , Matthew Hague
  • , Olivier Serre
  • Université Paris 7
  • CNRS
  • University of Tokyo
  • Technical University of Munich
  • Université Paris-Est
  • Royal Holloway University of London

Résultats de recherche: Le chapitre dans un livre, un rapport, une anthologie ou une collection › Contribution à une conférence › Revue par des pairs

14 Citations (Scopus)

Résumé

Higher-order recursion schemes (HORS) have recently received much attention as a useful abstraction of higher-order functional programs with a number of new verification techniques employing HORS model-checking as their centrepiece. This paper contributes to the ongoing quest for a truly scalable model-checker for HORS by offering a different, automata theoretic perspective. We introduce the first practical model-checking algorithm that acts on a generalisation of pushdown automata equi-expressive with HORS called collapsible pushdown systems (CPDS). At its core is a substantial modification of a recently studied saturation algorithm for CPDS. In particular it is able to use information gathered from an approximate forward reachability analysis to guide its backward search. Moreover, we introduce an algorithm that prunes the CPDS prior to model-checking and a method for extracting counter-examples in negative instances. We compare our tool with the state-of-the-art verification tools for HORS and obtain encouraging results. In contrast to some of the main competition tackling the same problem, our algorithm is fixed-parameter tractable, and we also offer significantly improved performance over the only previously published tool of which we are aware that also enjoys this property. The tool and additional material are available from http://cshore.cs.rhul.ac.uk.

langue originaleAnglais
titreICFP 2013 - Proceedings of the 2013 ACM SIGPLAN International Conference on Functional Programming
EditeurAssociation for Computing Machinery
Pages13-24
Nombre de pages12
ISBN (imprimé)9781450323260
Les DOIs
étatPublié - 25 sept. 2013
Evénement2013 18th ACM SIGPLAN International Conference on Functional Programming, ICFP 2013 - Boston, MA, États-Unis
Durée: 25 sept. 2013 → 27 sept. 2013

Série de publications

NomProceedings of the ACM SIGPLAN International Conference on Functional Programming, ICFP

Une conférence

Une conférence2013 18th ACM SIGPLAN International Conference on Functional Programming, ICFP 2013
Pays/TerritoireÉtats-Unis
La villeBoston, MA
période25/09/13 → 27/09/13

Empreinte digitale

Examiner les sujets de recherche de « C-SHORe: A collapsible approach to verifying higher-order programs ». Ensemble, ils forment une empreinte digitale unique.

Contient cette citation