Continuity and robustness of programs
Authors:
Open Access
- 1 August 2012
- journal article
- research article
- Published by Association for Computing Machinery (ACM) in Communications of the ACM
- Vol. 55 (8) , 107-115
Abstract
Computer scientists have long believed that software is different from physical systems in one fundamental way: while the latter have continuous dynamics, the former do not. In this paper, we argue that notions of continuity from mathematical analysis are relevant and interesting even for software. First, we demonstrate that many everyday programs are continuous (i.e., arbitrarily small changes to their inputs only cause arbitrarily small changes to their outputs) or Lipschitz continuous (i.e., when their inputs change, their outputs change at most proportionally). Second, we give an mostly-automatic framework for verifying that a program is continuous or Lipschitz, showing that traditional, discrete approaches to proving programs correct can be extended to reason about these properties. An immediate application of our analysis is in reasoning about the robustness of programs that execute on uncertain inputs. In the longer run, it raises hopes for a toolkit for reasoning about programs that freely combines logical and analytical mathematics.Keywords
This publication has 15 references indexed in Scilit:
- Testing and Reconstruction of Lipschitz Functions with Applications to Data Privacy2011
- Proving programs robust2011
- Approximate Bisimulation: A Bridge Between Computer Science and Control TheoryEuropean Journal of Control, 2011
- The reachability-bound problem2010
- Smooth interpretation2010
- Continuity analysis of programs2010
- Symbolic Robustness Analysis2009
- Interval Polyhedra: An Abstract Domain to Infer Interval Linear Relationships2009
- The ASTREÉ Analyzer2005
- Continuity in software systems2002