A HOL Formalisation of Smallfoot

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

• Thomas Tuerk (University of Cambridge)
• Tuesday 27 January 2009, 13:00-14:00
• Computer Laboratory, William Gates Building, Room SS03.

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

In my last ARG Lunch talk I presented a formalisation of Abstract Separation Logic in HOL . Based on this formalisation, I build a formalisation of a tool similar to Smallfoot. This talk will present this tool and its formalisation.

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.

My tool 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.

The talk will consist of 3 parts. First, I will shortly present the theoretical background and give an overview over the Smallfoot formalisation. Then I will give a demonstration on how a fully-functional-specification of mergesort can be proved using the tool. After this, there will be time for questions and people that are not interested in HOL implementation details will be able to leave. Finally, I plan to give an overview over some general HOL infrastructure that I developed for this tool. This part of the talk will require some knowledge of HOL and might only be of interest to HOL -users. In particular, I will present consequence conversions (/src/bool/ConseqConv) and the quantifier instantiation-heuristics library (/src/quantHeuristics).

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.