Saltar al contenido ForoHackers

Métodos formales y verificación: por dónde empezar

Métodos formales y verificación
#710 · Ophuscado · · Denunciar

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

  1. Lógica proposicional y de primer orden, y demostración por inducción.
  2. Escribe una especificación pequeña y compruébala con un verificador de modelos como TLA+ o Alloy.
  3. Anota un programa pequeño con contratos y verifícalo con una herramienta automática.
  4. Demuestra una propiedad simple de una estructura de datos en un asistente de pruebas.
  5. Estudia cómo se especifica un componente verificado, como un compilador o un núcleo, y qué queda sin demostrar.

Etiquetas relacionadas

#logic #type-theory #static-analysis #hardware-verification

Inicia sesión o únete para responder.