Termination proofs for systems code
Authors:
Open Access
- 11 June 2006
- journal article
- Published by Association for Computing Machinery (ACM) in ACM SIGPLAN Notices
- Vol. 41 (6) , 415-426
Abstract
Program termination is central to the process of ensuring that systems code can always react. We describe a new program termination prover that performs a path-sensitive and context-sensitive program analysis and provides capacity for large program fragments (i.e. more than 20,000 lines of code) together with support for programming language features such as arbitrarily nested loops, pointers, function-pointers, side-effects, etc.We also present experimental results on device driver dispatch routines from theWindows operating system. The most distinguishing aspect of our tool is how it shifts the balance between the two tasks of constructing and respectively checking the termination argument. Checking becomes the hard step. In this paper we show how we solve the corresponding challenge of checking with binary reachability analysis.Keywords
This publication has 19 references indexed in Scilit:
- Cogent: Accurate Theorem Proving for Program VerificationLecture Notes in Computer Science, 2005
- Termination of Polynomial ProgramsLecture Notes in Computer Science, 2005
- Shape Analysis by Predicate Abstraction2005
- Proving Program Invariance and Termination by Parametric Abstraction, Lagrangian Relaxation and Semidefinite Programming2005
- Abstraction Refinement for Termination2005
- A Complete Method for the Synthesis of Linear Ranking Functions2004
- Automated Termination Proofs with AProVELecture Notes in Computer Science, 2004
- A semantic basis for the termination analysis of logic programsThe Journal of Logic Programming, 1999
- TermiLog: A system for checking termination of queries to logic programsLecture Notes in Computer Science, 1997
- Assigning meanings to programs1967