s'authentifier
version française rss feed

inria-00258275, version 3

Certifying a Tree Automata Completion Checker

Benoît Boyer () a1, Thomas Genet () b1, Thomas Jensen () c1

N° RR-6462 (2008)

Résumé : Tree automata completion is a technique for the verification of infinite state systems. It has already been used for the verification of cryptographic protocols and the prototyping of Java static analysers. However, as for many other verification techniques, the correctness of the associated tool becomes more and more difficult to guarantee. It is due to the size of the implementation that constantly grows and due to low level optimizations which are necessary to scale up the efficiency of the tool to verify real-size systems. In this paper, we define and develop a checker for tree automata produced by completion. The checker is defined using Coq and its implementation is automatically extracted from its formal specification. Using extraction gives a checker that can be run independently of the Coq environment. A specific algorithm for tree automata inclusion checking have been defined so as to avoid the exponential blow up. The obtained checker is certified in Coq, independant of the implementation of completion, usable with any approximation performed during completion, small and fast. Some benchmarks are given to illustrate the efficiency of the tool.

  • a –  INRIA
  • b –  Université Rennes I
  • c –  CNRS
  • 1 :  LANDE (INRIA - IRISA)
  • CNRS : UMR6074 – INRIA – INSA Rennes – Université de Rennes 1
  • Domaine : Informatique/Logique en informatique
    Informatique/Génie logiciel
  • Mots-clés : Term Rewriting Systems – Tree Automata – Tree Automata Completion – Certification – Coq – Reachability
  • Référence interne : RR-6462
  • Versions disponibles :  v1 (04-03-2008) v2 (04-03-2008) v3 (07-04-2008)
 
  • inria-00258275, version 3
  • oai:hal.inria.fr:inria-00258275
  • Contributeur : 
  • Soumis le : Lundi 7 Avril 2008, 10:05:06
  • Dernière modification le : Lundi 5 Octobre 2009, 14:37:17
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...