¿Qué es exactamente la verificación simbólica del modelo?

8

Sé que la Comprobación de modelo simbólico es un recorrido de espacio de estado basado en representaciones de conjuntos de estados y relaciones de transición como fórmulas como en CTL usando modelos como Kripke Model. Conozco la teoría Pero me resulta difícil entender la aplicación real. ¿Dónde se usa exactamente? ¿Qué hace exactamente y cómo funciona?

¿Alguien puede explicar con un ejemplo real y relacionar la teoría con la práctica?

Xpleria
fuente
1
Esto me parece amplio. El "¿qué hace?" parte puede tener un alcance razonable (o no), pero "¿dónde se usa?" es a) otra pregunta completamente yb) probablemente demasiado amplia.
Raphael
Pero se puede tomar y explicar un ejemplo basado en eso. Eso no es demasiado amplio.
Xpleria
2
¿Por qué no está satisfecho con la descripción de la verificación simbólica del modelo en el libro de texto estándar, por ejemplo, "Principios de la verificación del modelo" por Christel Baier y Joost-Pieter Katoen? ¿De qué partes estás confundido?
hengxin
Hablan sobre "cómo se supone que debe hacerse" pero no "cómo exactamente se hace". Estoy tratando de relacionar la teoría y la implementación práctica. Todavía soy nuevo en esto y necesito un ejemplo.
Xpleria
1
Puede que estés en el sitio equivocado entonces. Ordenador ciencia es acerca de los conceptos ( "la forma en que se debe hacer"), usted tiene que pedir los profesionales acerca de la parte "cómo se hace".
Raphael

Respuestas:

4

La verificación simbólica de modelos es la verificación de modelos que funciona en estados simbólicos. Es decir, codifican los estados en representaciones simbólicas, típicamente diagramas de decisión binaria ordenados (OBDD).

La pregunta es qué hacen y cómo funcionan.

Primero tiene su código fuente para alguna aplicación. Luego transforma su código fuente en un gráfico de transición de estado como una Estructura de Kripke. Los estados están llenos de proposiciones atómicas que describen lo que es cierto en ese estado en particular. En la verificación simbólica del modelo, las proposiciones atómicas se codifican como OBDD para ahorrar espacio y mejorar el rendimiento.

Luego, el Comprobador de modelos comienza en algún estado inicial y explora los estados, buscando errores en el gráfico de transición de estado. Si encuentra un error, a menudo generará un caso de prueba que demuestre el error. Utiliza los OBDD simbólicos para navegar de manera óptima por el espacio de estado. Ojalá pudiera explicar más allí pero aún aprendiendo.

Pero eso es básicamente todo. Tiene un programa convertido en un modelo formal (gráfico de transición de estado), y luego utiliza optimizaciones simbólicas para navegar por el espacio de estado para buscar errores (comparándolo con una especificación LTL / CTL). Y si se encuentra un error, el Verificador de modelos le brinda algunas cosas para ayudar a documentarlo y resolverlo.

Lance Pollard
fuente
5

La verificación simbólica del modelo puede ser muy útil para verificar la exactitud de las comunicaciones y los protocolos de seguridad. Por ejemplo:

  • Un modelo simbólico de una implementación de OAUTH2 podría ayudar a verificar las consecuencias no deseadas cuando un adversario obtiene tokens de autenticación secretos o datos circunstanciales relacionados que podrían ayudarlos a contravenir el proceso.
  • Un modelo simbólico de un protocolo criptográfico, como un apretón de manos TLS, podría ayudar a verificar que el diseño criptográfico no tenga consecuencias no deseadas.

Esto funciona escribiendo una descripción simbólica de todas las funciones primitivas y algoritmos de protocolo, y luego tener un verificador de modelo simbólico, como ProVerif , atraviesa el espacio de estado e intenta detectar combinaciones de estados que producen resultados desfavorables. En el caso de ProVerif, los modelos simbólicos se describen utilizando el cálculo Pi aplicado como lenguaje de modelado. Esto permite la descripción de protocolos en una sintaxis funcional similar a ML.

kaepora
fuente