Verificación de modelos para software
La verificación de modelos comprueba automáticamente si el modelo de un sistema satisface una especificación de lógica temporal, explorando exhaustivamente sus estados alcanzables.
Definition
La verificación de modelos es una técnica de verificación automática que, dado un modelo de estados finitos de un sistema y una especificación de lógica temporal, comprueba exhaustivamente si la especificación se cumple y produce un rastro de contraejemplo si no es así.
Scope
Este tema abarca la verificación automática de sistemas de estados finitos y concurrentes frente a propiedades de lógica temporal (seguridad y vivacidad), el problema de la explosión de estados y las técnicas para combatirlo (representación simbólica con diagramas de decisión binarios, reducción de orden parcial, abstracción), la verificación de modelos acotada con SAT/SMT, y el refinamiento de abstracción guiado por contraejemplos para software.
Core questions
- ¿Cómo se puede verificar una propiedad explorando todos los estados alcanzables?
- ¿Qué es el problema de la explosión de estados y cómo se mitiga?
- ¿Cómo escalan los métodos simbólicos y acotados la verificación de modelos?
- ¿Cómo se abstraen los sistemas de software de estados infinitos a modelos finitos?
Key theories
- Verificación de modelos de lógica temporal
- Clarke, Emerson y Sistla, e independientemente Queille y Sifakis, introdujeron algoritmos para verificar automáticamente sistemas concurrentes de estados finitos frente a especificaciones de lógica temporal.
- Verificación de modelos simbólica
- Burch y sus colegas representaron conjuntos de estados simbólicamente con diagramas de decisión binarios, lo que permitió la verificación de sistemas con un número astronómico de estados y superó la explosión de estados ingenua.
Clinical relevance
La verificación de modelos se utiliza para verificar diseños de hardware, protocolos de comunicación y software concurrente y de seguridad crítica, donde encuentra errores sutiles que las pruebas no detectan y proporciona contraejemplos que señalan las fallas. Su automatización la distingue de la demostración interactiva de teoremas.
History
Basándose en la introducción de la lógica temporal para programas por Pnueli, Clarke y Emerson y, de forma independiente, Queille y Sifakis idearon la verificación de modelos alrededor de 1981-82, un trabajo que más tarde fue reconocido con un Premio Turing. La verificación de modelos simbólica con diagramas de decisión binarios (década de 1990) y la verificación de modelos acotada basada en SAT extendieron enormemente su alcance, y los métodos de abstracción-refinamiento la llevaron al software.
Debates
- Combatir la explosión de estados
- El desafío central es que el número de estados crece exponencialmente con el tamaño del sistema; los investigadores debaten la mejor combinación de representación simbólica, abstracción, reducción de orden parcial y verificación acotada para mantener la verificabilidad manejable.
Key figures
- Edmund Clarke
- E. Allen Emerson
- Joseph Sifakis
- Kenneth McMillan
- Amir Pnueli
Related topics
Seminal works
- clarke1986
- queille1982
- burch1992
Frequently asked questions
- ¿En qué se diferencia la verificación de modelos de la demostración de teoremas?
- La verificación de modelos es completamente automática y explora el espacio de estados de un sistema de forma exhaustiva para modelos finitos o abstractos, mientras que la demostración de teoremas utiliza la deducción lógica (a menudo de forma interactiva) y puede manejar sistemas de estados infinitos, pero requiere más guía humana.
- ¿Qué es el problema de la explosión de estados?
- Es el crecimiento exponencial en el número de estados alcanzables a medida que un sistema adquiere componentes o variables, lo que limita la verificación de modelos ingenua y motiva las técnicas simbólicas, acotadas y basadas en abstracción.