Los métodos formales usan las matemáticas para especificar lo que un sistema debe hacer y para demostrar, o comprobar exhaustivamente, que lo hace. Las pruebas muestrean el comportamiento; la verificación lo cubre todo dentro de un modelo. El costo es esfuerzo y formación, así que se usan donde fallar sale caro: protocolos, núcleos, compiladores, hardware, sistemas de seguridad.
Conceptos clave
- Especificación: un enunciado preciso de las propiedades requeridas, escrito en lógica o en un lenguaje de modelado.
- Verificación de modelos: explorar automáticamente cada estado alcanzable de un modelo finito frente a una propiedad.
- Demostración de teoremas: construir pruebas verificadas por máquina, a mano o con automatización, en un asistente de pruebas.
- Seguridad y vivacidad: nunca ocurre nada malo, y tarde o temprano ocurre algo bueno.
- Abstracción y refinamiento: razonar sobre un modelo simple y mostrar después que el diseño real lo respeta.
Vocabulario
- Invariante: propiedad que se cumple en todo estado alcanzable, o en cada iteración de un bucle.
- Precondición y poscondición: lo que debe cumplirse antes de que una función se ejecute, y lo que garantiza después.
- Solucionadores SAT y SMT: herramientas que deciden fórmulas lógicas, usadas dentro de muchos verificadores.
- Explosión de estados: el número de estados crece demasiado rápido para enumerarlos.
Qué estudiar, en orden
- Lógica proposicional y de primer orden, y demostración por inducción.
- Escribe una especificación pequeña y compruébala con un verificador de modelos como TLA+ o Alloy.
- Anota un programa pequeño con contratos y verifícalo con una herramienta automática.
- Demuestra una propiedad simple de una estructura de datos en un asistente de pruebas.
- Estudia cómo se especifica un componente verificado, como un compilador o un núcleo, y qué queda sin demostrar.