Verified LISP implementations on ARM, x86 and PowerPC / A HOL Formalisation of Smallfoot

Add to your list(s) Download to your calendar using vCal

• Magnus Myreen & Thomas Tuerk
• Wednesday 12 August 2009, 13:00-14:00
• Computer Laboratory, William Gates Building, Room SS03.

If you have a question about this talk, please contact Thomas Tuerk.

Magnus Myreen and Thomas Tuerk are going to practice their TPHOLS talks. So, there will be two 20 minute talks.

Magnus Myreen: Verified LISP implementations on ARM , x86 and PowerPC

This paper reports on a case study, which we believe is the first to produce a formally verified end-to-end implementation of a functional programming language running on commercial processors. Interpreters for the core of McCarthy’s LISP 1 .5 were implemented in ARM , x86 and PowerPC machine code, and proved to correctly parse, evaluate and print LISP s-expressions. The proof of evaluation required working on top of verified implementations of memory allocation and garbage collection. All proofs are mechanised in the HOL4 theorem prover.

Thomas Tuerk A Formalisation of Smallfoot in HOL

I’m building a framework based on Abstract Separation Logic in HOL . Furthermore, I use this framework to build a tool called Holfoot that is similar to Smallfoot. In this talk I will give a high level presentation of the framework and especially Holfoot.

Smallfoot is one of the oldest and best documented separation logic tools. It is able to automatically prove specifications about programs written in a simple, low-level imperative language. This programming language is designed to be similar to C. It contains pointers, local and global variables, dynamic memory allocation/deallocation, conditional execution, while-loops and recursive procedures with call-by-value and call-by-reference arguments. Moreover, there is support for parallism.

Holfoot is able to parse Smallfoot-specifications and verify them automatically inside HOL . While Smallfoot-specifications only talk about the shape of data-structures in memory, my tool is able to reason about their data-content as well. However, proofs of fully-functional specification usually need user interaction.

This talk is part of the Computer Laboratory Automated Reasoning Group Lunches series.

This talk is included in these lists:

• All Talks (aka the CURE list)
• Cambridge talks
• Computer Laboratory Automated Reasoning Group Lunches
• Computer Laboratory, William Gates Building, Room SS03
• Department of Computer Science and Technology talks and seminars
• Interested Talks
• School of Technology
• Trust & Technology Initiative - interesting events
• bld31
• yk373's list

Note that ex-directory lists are not shown.