Skip to the content ForoHackers
Log inJoin

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

Formal methods and verification
#3216 · · Quote · Report

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

You are not logged in, so this goes up anonymously: no account, no name and no address is stored with it, and it may carry no link and no image. Log in or join to post under your name. Our web server's logs keep the address and time of every request for up to 14 days; to keep yours out of them, use Tor. To reach the staff in confidence, use the drop. Sign as a returning source (a key kept only in this browser)

Sending takes a few seconds here: your browser first works out a proof of work against spam.

Reply