Una imagen general de la verificación formal en software.

Question

Estoy tratando de juntar una imagen general del estado de la verificación formal del software, y estoy teniendo un buen problema. Para el contexto, vengo de principalmente un fondo de matemáticas. Estoy bastante familiarizado con el estado de los profesionales del teorema automatizado y los asistentes de prueba con respecto a su uso para probar declaraciones matemáticas bien formadas (por ejemplo, en CoQ, Isabelle, Lean, etc.). Lo que tengo problemas para entender es lo que está pasando con "Métodos formales" en las aplicaciones prácticas CS.

He encontrado que las empresas como Microsoft y AWS han usado TLA + como un "método formal" en su desarrollo de software un poco sustancialmente. Pero cuando comencé a leer el libro de TLA + TLA + , encontré que consideraba que un programa se verifica formalmente si solo verificamos decir un algoritmo de clasificación en las listas de longitud $ con las entradas entre 1 y $ n $ para algunos $ n $ , es decir, solo estamos revisando finamente muchos casos y diciendo que, por lo tanto, el algoritmo debería funcionar en general. Esto no parece particularmente interesante; Solo un ejemplo de pruebas unitarias particularmente rigurosas. En particular, no es una prueba formal de corrección.

Por otro lado, he visto murmullos sobre Isabelle y Coq, pudiendo probar cosas sobre el software al igual que pueden probar los teoremas matemáticos. Aunque cuando miro a los libros que parecen prometer esto, por ejemplo. La programación certificada de Chlipala con los tipos dependientes , veo muchas cosas abstractas que parecen relacionarse vagamente con los programas de verificación formal, pero no hay ejemplos de tomar un programa real escrito en un idioma que tenga un uso generalizado (por ejemplo, C ++ , Python, Java, etc.) o incluso solo pseudocódigo y "verificándolo", lo que sea que eso signifique.

¿Puede alguien tratar de aclarar mi confusión?

Answer 1

Un programa comprobado formalmente es un programa comprobado formalmente, independientemente de qué idioma está en. Solo porque un programa está escrito en CoQ y quizás extraído a Ocaml o Haskell, en lugar de escrito en un lenguaje más" de la empresa ", como C ++ o Java, no lo hace menos un programa.

Probación de programas escritos en lenguajes de programación de propósito general, incluso "domesticados" como Haskell, es difícil porque estos idiomas suelen incluir muchas características de conveniencia, esquinas oscuras para el rendimiento y para interactuar con el sistema operativo, y rico y complejo. Bibliotecas. Para probar una propiedad de un programa, primero debe indicar esta propiedad, y la declaración incorpora a la semántica del lenguaje en el que se escribe el programa. Cuando intenta formalizar idiomas que se diseñaron inicialmente sin una semántica formal (que es casi todos ellos), golpeas muy rápidamente las esquinas oscuras que la descripción inglesa deja sin especificar, o donde es ambigua, o donde es completamente contradictorio, o donde la implementación de referencia no hace lo que dice la descripción y que se considera un error en El inglés en lugar de en la implementación. El estado de la técnica de demostrar propiedades de los programas escritos en un lenguaje preexistente es restringir los programas a un subconjunto del idioma.

Lo que va en ese subconjunto es altamente variable. El azúcar sintáctico no es demasiado difícil: la semántica solo necesita traducirla en construcciones más simples. Las propiedades de reflexión no son particularmente difíciles de modelar, pero pueden hacer que el modelo sea mucho más difícil de razonar (por ejemplo, invalida las propiedades, como "Este fragmento de código no tiene ninguna manera de hacer referencia a esta variable, por lo tanto, no puede Cambia su valor "), tantos marcos descartaron esto. Las interacciones con el sistema operativo (normalmente a través de bibliotecas) son problemáticas porque requieren modelar el sistema operativo, que se vuelven extremadamente complejos. Las operaciones de puntos flotantes son difíciles porque hacer un seguimiento de las aproximaciones en operaciones sucesivas causa una gran explosión.

para C, uno de los principales subconjuntos grandes con un modelo formal es compercero C, el idioma de compercert . Compcert es un compilador verificado formalmente (escrito en CoQ), por lo que si demuestra una propiedad del programa C, además puede obtener una prueba del código de la máquina generado. CompcerT C es un subconjunto muy grande de C99, pero la formalización excluye la mayor parte del estándar Biblioteca y algunos peculiares del idioma.

Para demostrar un programa que está escrito en un idioma de programación del (Subconjunto adecuado de A), el programa debe estructurarse de manera tal que haga que la prueba sea transitable. En la práctica, esto significa haber escrito y demostrado el programa primero en un lenguaje de nivel superior (que no tiene implementación en el hardware real), y utilizando este lenguaje de nivel superior como una especificación del programa final. A menudo hay varios niveles de refinamientos sucesivos entre el programa ejecutable y la especificación.

Es bastante común que el programa final no está escrito manualmente, sino que se extrae mecánicamente de un lenguaje de nivel superior. Por ejemplo, escribiendo CoQ que se extrae a OCAML, o escribiendo f * que se extrae a C. pero la También es posible un enfoque opuesto, por ejemplo, la escritura ("Dame") c, anotándola con propiedades de funciones y otras subdivisiones de código, y usando FRAMA-C para demostrar esas propiedades (y la propiedad implícita que el programa C no tiene un comportamiento indefinido).

Cuando tiene una semántica formal de un lenguaje de programación y una forma de expresar propiedades de los programas, demostrar estas propiedades es un teorema matemático. Por lo general, estos teoremas no implican ninguna matemática compleja, como el cálculo (a menos que se traiga el dominio de la aplicación, como rastrear el movimiento de un objeto físico), pero son difíciles de probar porque involucran fórmulas muy grandes, y contienen declaraciones aritméticas. ( $ x ^ n + y ^ n= z ^ n ^ ^ ^ span> no es una ecuación compleja, ¡pero resolverlo no es elemental!). Es teóricamente imposible escribir un programa que pueda probar una propiedad semántica no trivial de todos los programas , y prácticamente imposible escribir un programa que pueda probar muchas propiedades interesantes de los programas típicos. La verificación formal implica una combinación de romper el problema en pasos suficientemente pequeños (escribir pequeñas funciones y declarar suficientes propiedades precisas de esas funciones), tener una herramienta para probar automáticamente algunas de esas propiedades (tal

como una Sábil Sábil para la lógica proposicional), y que los humanos escriban pruebas donde la computadora puede 'T Hágalo (pero la computadora revisará la prueba del humano). Asistentes de prueba como CoQ e Isabelle entran para este último paso.

Probar formalmente un programa del mundo real es un gran esfuerzo, que requiere una cantidad de tiempo y experiencia mucho mayor que el proyecto de software típico. Rara vez se realiza fuera de los entornos de alta garantía, principalmente entornos con alta requrementos de seguridad, como transporte (planos, trenes, no tanto automóviles), a veces entornos con altos costos, como el espacio o (muy raramente) con requisitos de alta seguridad, como SMART. tarjetas.

Si simplemente verificamos decir un algoritmo de clasificación en las listas de longitud

Eso no sería una prueba formal a menos que el programa tenga un límite de n artículos para su entrada. No sé este libro, pero sospecho que tampoco le escribes mal algo. Verificar formalmente un programa de clasificación implicaría demostrar su corrección para todos los n.