A Type System for Extracting Functional Specifications from Memory-Safe Imperative ProgramsVirtual
Fri 22 Oct 2021 22:05 - 22:20 at Zurich D - Types & Verification -- mirror Chair(s): Atsushi Igarashi
Verifying imperative programs is hard. A key difficulty is that the specification of what an imperative program does is often intertwined with details about pointers and imperative state. Although there are a number of powerful separation logics that allow the details of imperative state to be captured and managed, these details are complicated and reasoning about them requires significant time and expertise. In this paper, we take a different approach: a memory-safe type system that, as part of type-checking, extracts functional specifications from imperative programs. This disentangles imperative state, which is handled by the type system, from functional specifications, which can be verified without reference to pointers. A key difficulty is that sometimes memory safety depends crucially on the functional specification of a program; e.g., an array index is only memory-safe if the index is in bounds. To handle this case, our specification extraction inserts dynamic checks into the specification. Verification then requires the additional proof that none of these checks fail. However, these checks are in a purely functional language, and so this proof also requires no reasoning about pointers.
Fri 22 OctDisplayed time zone: Central Time (US & Canada) change
13:50 - 15:10 | Types & VerificationOOPSLA at Zurich D +8h Chair(s): Leonidas Lampropoulos University of Maryland, College Park | ||
13:50 15mTalk | Scalability and Precision by Combining Expressive Type Systems and Deductive VerificationVirtual OOPSLA Florian Lanzinger KIT, Alexander Weigl KIT, Mattias Ulbrich KIT, Werner Dietl University of Waterloo DOI | ||
14:05 15mTalk | A Type System for Extracting Functional Specifications from Memory-Safe Imperative ProgramsVirtual OOPSLA Paul He University of Pennsylvania, Edwin Westbrook Galois, Brent Carmer Galois, Chris Phifer Galois, Valentin Robert Galois, Karl Smeltzer Galois, Andrei Ştefănescu Galois, Aaron Tomb Galois, Adam Wick Galois, Matthew Yacavone Galois, Steve Zdancewic University of Pennsylvania DOI | ||
14:20 15mTalk | Transitioning from Structural to Nominal Code with Efficient Gradual TypingIn-Person OOPSLA DOI | ||
14:35 35mLive Q&A | Discussion, Questions and Answers OOPSLA |
21:50 - 23:10 | |||
21:50 15mTalk | Scalability and Precision by Combining Expressive Type Systems and Deductive VerificationVirtual OOPSLA Florian Lanzinger KIT, Alexander Weigl KIT, Mattias Ulbrich KIT, Werner Dietl University of Waterloo DOI | ||
22:05 15mTalk | A Type System for Extracting Functional Specifications from Memory-Safe Imperative ProgramsVirtual OOPSLA Paul He University of Pennsylvania, Edwin Westbrook Galois, Brent Carmer Galois, Chris Phifer Galois, Valentin Robert Galois, Karl Smeltzer Galois, Andrei Ştefănescu Galois, Aaron Tomb Galois, Adam Wick Galois, Matthew Yacavone Galois, Steve Zdancewic University of Pennsylvania DOI | ||
22:20 15mTalk | Transitioning from Structural to Nominal Code with Efficient Gradual TypingIn-Person OOPSLA DOI | ||
22:35 35mLive Q&A | Discussion, Questions and Answers OOPSLA |