Search papers, labs, and topics across Lattice.
This paper introduces a categorical framework for formally defining and achieving robustness in program analysis. It models programs and their properties as objects in a category, where robustness is characterized as structure-preserving functors under various program transformations. The paper provides a recipe for lifting robust analyses from restricted computational models to general programs, and demonstrates that algebraic program analyses built from robust operators are robust under refactoring.
Robustness, a critical but often overlooked property of program analyses, can be formally defined and achieved using a categorical framework.
Users of program analyses expect that results change predictably in response to changes in their programs, but many analyses fail to provide such robustness. This paper introduces a theoretical framework that provides a unified language to articulate robustness properties. By modeling programs and their properties as objects in a category, diverse notions of robustness-from variable renaming to semantic refinement and structural transformation-can be characterized as structure-preserving functors. Beyond formulating the meaning of robustness, this paper provides methods for achieving it. The first is a general recipe for designing robust analyses, by lifting a sound and robust analysis from a restricted (sub-Turing) model of computation to a sound and robust analysis for general programs. This recipe demystifies the design of several existing loop summarization and termination analyses by showing they are instantiations of this general recipe, and furthermore elucidates their robustness properties. The second is a characterization of a sense in which an algebraic program analysis is robust, provided that it is comprised of robust operators. In particular, we show that such analyses behave predictably under common refactoring patterns, such as variable renaming and loop unrolling.
