A Verifying Core for a Cryptographic Language Compiler

• ABSTRACT:
  
  A verifying compiler is one that emits both object code and a proof of correspondence between object and source code. We report the use of ACL2 in building a verifying compiler for μCryptol, a stream-based language for encryption algorithm specification that targets Rockwell Collins' AAMP7 microprocessor (and is designed to compile efficiently to hardware, too). This paper reports on our success in verifying the ``core'' transformations of the compiler -- those transformations over the sub-language of μCryptol that begin after ``higher-order'' aspects of the language are compiled away, and finish just before hardware or software specific transformations are exercised. The core transformations are responsible for aggressive optimizations. We have written an ACL2 macro that automatically generates both the correspondence theorems and their proofs. The compiler also supplies measure functions that ACL2 uses to automatically prove termination of μCryptol programs, including programs with mutually-recursive cliques of streams. Our verifying compiler has proved the correctness of its core transformations for multiple algorithms, including TEA, RC6, and AES. Finally, we describe an ACL2 book of primitive operations for the general specification and verification of encryption algorithms.

• BIBTEX:
  

  @inproceedings{pike_acl2:06,
    author    = {Lee Pike and Mark Shields and John Matthews},
    title     = {A verifying core for a cryptographic language compiler},
    booktitle = {Proceedings of the Sixth International Workshop on the ACL2 Theorem Prover and its Applications},
    year      = {2006},
    pages     = {1--10},
    publisher = {ACM Press},
    note      = {Available at \url{http://www.cs.indiana.edu/~lepike/pub_pages/acl2.html}}}
  

• PAPER DOWNLOAD: pdf 

• SLIDES DOWNLOAD: pdf

• FILES DOWNLOAD: core_verifier.tgz
  • To extract the files, issue

    tar -xzvf core_verifier.tgz

  • Includes ACL2 files and sample compiler output and proofs for factorial, Fibonacci, TEA, AES, and RC6. Note: the ACL2 proofs require Rockwell Collins' super-ihs machine arithmetic ACL2 book, slated for release shortly.

• NOTE: A preliminary version of this paper appeared in the participants' proceedings of the High Confidence Systems and Software Conference, 2006.