Export or edit this event...

Galois Tech Talk: Theorem Proving for Verification

Galois, Inc
421 SW 6th Ave. Suite 300
Portland, OR 97204, US (map)


Title: Theorem Proving for Verification

Speaker: John Harrison

        Principal Engineer

Date: Tuesday, September 16th.


Location: Galois, Inc.

        421 SW 6th Ave. Suite 300
        (3rd floor of the Commonwealth Building)
        Portland, Oregon


The theorem proving approach to verification involves modelling a system in a rich formalism such as higher-order logic or set theory, then performing a human-driven interactive correctness proof using a proof assistant. In a striking contrast, techniques like model checking, by limiting the user to a less expressive formalism (propositional logic, CTL etc.), can offer completely automated decision methods, making them substantially easier to use and often more productive.

With this in mind, why should one be interested in the theorem proving approach? In this tutorial I will explain some of the advantages of theorem proving, showing situations where the generality of theorem proving is beneficial, allowing us to tackle domains that are beyond the scope of automated methods or providing other important advantages. I will talk about the state of the art in theorem proving systems and and give a little demonstration to give an impression of what it's like to work with such a system.

Biographical details:

John Harrison has worked in formal verification and automated theorem proving since 1990, when he joined Mike Gordon's "Hardware Verification Group" (HVG) at the University of Cambridge Computer Laboratory. As well as working on the development of the HOL theorem prover, he developed a particular interest in the formalization of real analysis and its application to formal verification of floating-point hardware. His PhD in this area, "Theorem Proving with the Real Numbers", written under Mike Gordon's supervision, won a UK Distinguished Dissertation award and was published as a book. He also redesigned HOL from scratch, resulting in an alternative version called HOL Light. After completing his PhD research in 1995, John Harrison spent a very enjoyable year at Abo Akademi University and Turku Centre for Computer Science (TUCS) in Turku, Finland, where he was a member of Ralph Back's Programming Methods Research Group. Among other activities, he championed the "declarative" proofs of the Mizar system and showed how these could be integrated into other theorem-provers, work subsequently taken up in DECLARE, Isar and other systems.

John Harrison then returned to Cambridge and worked on a formal model of floating-point arithmetic and its application to the verification of some realistic algorithms for transcendental functions. This work attracted the attention of Intel, and in 1998 John Harrison joined the company as a Senior Software Engineer (now Principal Engineer) specializing in the design and formal verification of mathematical algorithms. He has formally verified and in many cases designed or redesigned numerous algorithms for mathematical functions including division, square root and transcendental functions.

In his limited spare time over the past 10 years, John Harrison has been working on a book giving a comprehensive introduction to automated theorem proving.  (http://www.cambridge.org/9780521899574)

About the Galois Tech Talks.

Galois (http://galois.com) has been holding weekly technical seminars for several years on topics from functional programming, formal methods, compiler and language design, to cryptography, and operating system construction, with talks by many figures from the programming language and formal methods communities.

The talks are open and free. If you're planning to attend, dropping a note to <[email protected]> is appreciated, but not required. If you're interested in giving a talk, we're always looking for new speakers.