Saltar al contenido ForoHackers

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

Métodos formales y verificación
#3216 · · Citar · 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

No has iniciado sesión, así que esto se publica como anónimo: no se guarda con ello ninguna cuenta, nombre ni dirección, y no puede llevar enlaces ni imágenes. Inicia sesión o únete para publicar con tu nombre. Los registros de nuestro servidor web guardan la dirección y la hora de cada petición hasta 14 días; para que la tuya no quede en ellos, usa Tor. Para escribir al equipo de forma confidencial, usa el buzón. Firmar como fuente habitual (una clave guardada solo en este navegador)

Enviar tarda unos segundos aquí: tu navegador resuelve antes una prueba de trabajo contra el spam.

Responder