Rewriting modulo SMT and open system analysis

Abstract

This paper proposes rewriting modulo SMT, a new technique that combines the power of SMT solving, rewriting modulo theories, and model checking. Rewriting modulo SMT is ideally suited to model and analyze reachability properties of infinite-state open systems, i.e., systems that interact with a nondeterministic environment. Such systems exhibit both internal nondeterminism, which is proper to the system, and external nondeterminism, which is due to the environment. In a reflective formalism, such as rewriting logic, rewriting modulo SMT can be reduced to standard rewriting. Hence, rewriting modulo SMT naturally extends rewriting-based reachability analysis techniques, which are available for closed systems, to open systems. Furthermore, a single state expression with symbolic constraints can now denote an infinite set of concrete states. The proposed technique is illustrated with the formal analysis of: (i) a real-time system that is beyond the scope of timed-automata methods and (ii) automatic detection of reachability violations in a synchronous language developed to support autonomous spacecraft operations.

Este artículo propone la reescritura de módulo SMT, una nueva técnica que combina el poder de la resolución SMT, la reescritura de teorías de módulo y la verificación de modelos. La reescritura del módulo SMT es ideal para modelar y analizar las propiedades de accesibilidad de los sistemas abiertos de estado infinito, es decir, los sistemas que interactúan con un entorno no determinista. Dichos sistemas exhiben tanto un no determinismo interno, que es propio del sistema, como un no determinismo externo, que se debe al entorno. En un formalismo reflexivo, como la lógica de reescritura, la reescritura del módulo SMT se puede reducir a la reescritura estándar. Por lo tanto, la reescritura del módulo SMT extiende naturalmente las técnicas de análisis de accesibilidad basadas en la reescritura, que están disponibles para sistemas cerrados, a sistemas abiertos. Además, una sola expresión de estado con restricciones simbólicas ahora puede denotar un conjunto infinito de estados concretos. La técnica propuesta se ilustra con el análisis formal de: (i) un sistema en tiempo real que está más allá del alcance de los métodos de autómatas cronometrados y (ii) detección automática de violaciones de accesibilidad en un lenguaje sincrónico desarrollado para soportar operaciones de naves espaciales autónomas.