Using first-order theorem provers in the jahob data structure verification system

Charles Bouillaguet, Viktor Kuncak, Thomas Wies, Karen Zee, Martin Rinard

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

This paper presents our integration of efficient resolution-based theorem provers into the Jahob data structure verification system. Our experimental results show that this approach enables Jahob to automatically verify the correctness of a range of complex dynamically instantiable data structures, such as hash tables and search trees, without the need for interactive theorem proving or techniques tailored to individual data structures. Our primary technical results include: (1) a translation from higher-order logic to first-order logic that enables the application of resolutionbased theorem provers and (2) a proof that eliminating type (sort) information in formulas is both sound and complete, even in the presence of a generic equality operator. Our experimental results show that the elimination of type information often dramatically decreases the time required to prove the resulting formulas. These techniques enabled us to verify complex correctness properties of Java programs such as a mutable set implemented as an imperative linked list, a finite map implemented as a functional ordered tree, a hash table with a mutable array, and a simple library system example that uses these container data structures. Our system verifies (in a matter of minutes) that data structure operations correctly update the finite map, that they preserve data structure invariants (such as ordering of elements, membership in appropriate hash table buckets, or relationships between sets and relations), and that there are no run-time errors such as null dereferences or array out of bounds accesses.

Original languageEnglish (US)
Title of host publicationVerification, Model Checking, and Abstract Interpretation, - 8th International Conference, VMCAI 2007, Proceedings
PublisherSpringer Verlag
Pages74-88
Number of pages15
ISBN (Print)3540697357, 9783540697350
DOIs
StatePublished - 2007
Event8th International Conference on Verification, Model Checking, and Abstract Interpretation, VMCAI 2007 - Nice, France
Duration: Jan 14 2007Jan 16 2007

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume4349 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other8th International Conference on Verification, Model Checking, and Abstract Interpretation, VMCAI 2007
CountryFrance
CityNice
Period1/14/071/16/07

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'Using first-order theorem provers in the jahob data structure verification system'. Together they form a unique fingerprint.

Cite this