La verificación formal no es verificable: por qué desconfiar de lo 'formalmente verificado'
Formal Verification Is Not Verifiable
La IA ha disparado la verificación formal, pero el autor advierte que llamar a un sistema 'formalmente verificado' es engañoso: las pruebas dependen de componentes no revisados (definiciones, modelos, compiladores) y las afirmaciones son universales, por lo que un solo error puede invalidarlas. Aboga por abolir esa etiqueta y exigir una lista precisa de qué se demuestra y qué se asume. Aun así, se muestra optimista sobre probar propiedades acotadas, especialmente en programas monohilo.
Es mi opinión que debemos abolir cuanto antes la noción de 'software formalmente verificado'; tiene que surgir el matiz.
- johnbender
> Esto nos permite (1) eludir el modelado de la semántica del lenguaje de programación de alto nivel, pudiendo en su lugar modelar la semántica de la máquina --presumiblemente una semántica más simple
Las ISAs son bastante complicadas y razonar sobre programas en ese contexto es difícil, que es por lo que tenemos lenguajes de alto nivel.
> Esta distinción en la terminología solía ser una noción aceptada coloquialmente; cuando oíamos "CompCert es un compilador formalmente verificado" o "seL4 es un microkernel formalmente verificado", asumíamos que los autores no verificaban propiedades vacuas o triviales, porque el trabajo de la verificación en sí se sostenía a un estándar alto que afectaba enormemente la reputación del investigador.
CompCert también ha tenido una extensa evaluación empírica para validar los teoremas. Famosamente, el artículo de CSmith (https://users.utah.edu/~regehr/papers/pldi11-preprint.pdf) tiene esta cita bastante selecta:
> A principios de 2011, la versión en desarrollo de CompCert es el único compilador que hemos probado para el cual Csmith no puede encontrar errores de código incorrecto. Esto no es por falta de intentos: hemos dedicado unos seis años de CPU a la tarea. La aparente inquebrantabilidad de CompCert respalda un argumento sólido de que desarrollar optimizaciones de compilador dentro de un marco de prueba, donde las comprobaciones de seguridad son explícitas y verificadas por máquina, tiene beneficios tangibles para los usuarios de compiladores.
En mi trabajo hemos extendido esto a milenios de CPU. Me apresuro a añadir que esto, por supuesto, no descarta la posibilidad de suposiciones mal formadas en la semántica, etc. (es empírico despu […]
- mjb
> Para cualquier propiedad de un programa universalmente cuantificada de primer orden que podamos escribir como una prueba basada en propiedades, creo que seremos capaces de generar pruebas a nivel binario, contra modelos de arquitectura que a su vez han sido validados por millones de horas de pruebas. El desafío de extender esto a programas multihilo, sistemas distribuidos, [..] serán años más de trabajo que debemos realizar entre miles de ingenieros de verificación e investigadores.
Espero que la versión distribuida y concurrente de esto llegue más rápido. De hecho, estaría dispuesto a apostar que para finales de 2030 se alcanzará el listón mencionado aquí del software de un solo hilo para sistemas multihilo y distribuidos bajo modos de fallo no adversarios. Esto es significativamente más agresivo que lo que opina la mayoría en el campo (y yo soy, como mucho, adyacente al campo), pero dado el ritmo de progreso creo que en realidad es una apuesta bastante conservadora (la apuesta realmente agresiva sería "julio de 2027").
> Cuanto más "bouba" es una pieza de software o una capa dada, más difícil es hablar de qué la hace correcta. Siempre podemos hablar de algunos atributos correctos, pero hablar de una noción uniforme de corrección no es posible en mi opinión.
Estoy en gran medida de acuerdo con esto, aunque sí creo que vamos a ver más progreso del esperado en cuantificar (y por lo tanto verificar) la usabilidad y los aspectos de "aspecto y sensación" del software. El riesgo es que esto ocurra de una manera "estrecha" que fuerce a todo el software 'correcto' a verse y sentirse igual, porqu […]
- nanolith
Las pruebas son útiles en la medida en que la especificación formal sea sólida. El problema es que construir una especificación formal sólida es la parte difícil, y no es algo en lo que los LLMs vayan a ser particularmente buenos. Sí, pueden escribir una especificación formal. Pero, ¿es sólida esta especificación formal? ¿Es usable? ¿Es aplicable? ¿Es completa? Todo esto requiere razonamiento a nivel humano y quizás más allá para verificarlo.
Una vez que tienes una especificación formal sólida, construir pruebas de que el software sigue esta especificación es en realidad bastante sencillo. Los LLMs no están haciendo ninguna magia aquí.
- skybrian
Cuando existe una especificación de lenguaje y todo el mundo acepta usarla, significa que "¿debería compilar este código?" tiene un significado claro, y también lo tiene "error del compilador".
Quizás tener paquetes comunes que contengan especificaciones compartidas para otras propiedades deseables sea el camino a seguir. Desde el punto de vista del usuario, la herramienta debería comportarse como un linter.
¿De dónde vendrá la confianza? Para un proyecto de software popular, viene de tener un equipo de confianza que lo mantenga y mucha gente (y bots) vigilándolos. El resultado sería que alguien pueda usar el linter sin necesidad de verificar mucho por sí mismo.
Y claro, también deberías poder escribir y probar tus propias propiedades personalizadas, pero con suerte se apoyará en definiciones compartidas.
- Taikonerd
> Un gran ejemplo de esto es el reciente enfoque de "verificación binaria", donde en lugar de probar hechos sobre los programas mismos, probamos hechos sobre los binarios compilados de esos programas.
Este es un argumento interesante; puedo ver pros y contras aquí.
No soy un tipo de métodos formales, pero imaginaría que la razón por la que podrías querer probar hechos sobre los programas mismos es que codifican información de más alto nivel "gratis" -- como, por ejemplo, que esta función devuelve un Person.
Si mal no recuerdo, hubo investigación sobre compiladores especiales que producirían TAL: Typed Assembly Language. La idea era que TAL pudiera llevar anotaciones que serían útiles para los probadores.