Product Design, Manufacturing & Innovation Resources
Hogar » Verificación formal

Verificación formal

1980
  • Edmund M. Clarke
  • E. Allen Emerson
  • Joseph Sifakis
Ingeniero informático revisando un modelo de verificación formal en la oficina.

(Imagen generada únicamente con fines ilustrativos)

Formal verificación La verificación formal utiliza métodos matemáticos para probar o refutar la corrección del diseño de un sistema con respecto a una especificación formal. A diferencia de las pruebas, que solo pueden mostrar la presencia de errores para entradas específicas, la verificación formal puede demostrar su ausencia para todas las entradas posibles. Implica la creación de un modelo formal del sistema y el uso de técnicas como la verificación de modelos o la demostración de teoremas.

La verificación formal proporciona el máximo nivel de garantía sobre la corrección del sistema. El proceso comienza con la creación de un modelo formal del sistema mediante un lenguaje matemático, como la lógica temporal o el álgebra de procesos. Un conjunto de propiedades, derivadas de los requisitos del sistema, también se expresa en un lenguaje formal. A continuación, el proceso de verificación utiliza herramientas automatizadas para explorar sistemáticamente todos los estados posibles del modelo y determinar si las propiedades especificadas son verdaderas.

Se utilizan dos técnicas principales: la comprobación de modelos y la demostración de teoremas. La comprobación de modelos es una técnica automatizada que explora todo el espacio de estados de un modelo de estado finito. Si se incumple una propiedad, el verificador de modelos produce un contraejemplo, una traza de ejecución específica que demuestra el fallo. Este método es muy eficaz, pero puede sufrir el problema de la "explosión del espacio de estados" en sistemas muy complejos. La comprobación de teoremas consiste en representar el sistema y sus propiedades como fórmulas lógicas (teoremas) y utilizar comprobadores automatizados o interactivos para construir una prueba formal de corrección. Este método puede aplicarse a sistemas de estado infinito, pero a menudo requiere un esfuerzo manual considerable por parte de los expertos.

Si bien la verificación formal es computacionalmente costosa y requiere conocimientos especializados, resulta indispensable para sistemas críticos para la seguridad, donde el costo de un fallo es extremadamente alto. Se ha aplicado con éxito para verificar la corrección de las unidades de coma flotante de la CPU, los protocolos de comunicación y los sistemas de control, donde las pruebas exhaustivas son inviables.

UNESCO Nomenclature: 1203
- Informática

Tipo

Software/Algoritmo

Ruptura

Fundacional

Uso

Nicho/Especialización

Precursores

  • lógica proposicional y de predicados
  • automata theory
  • cálculo lambda
  • semántica de programas (por ejemplo, lógica de Hoare)
  • teoría de la complejidad computacional

Aplicaciones

  • diseño de microprocesadores (por ejemplo, intel pentium fdiv bug fix)
  • software de aviónica (por ejemplo, sistemas fly-by-wire)
  • análisis de protocolos criptográficos
  • sistemas de señalización ferroviaria
  • controladores de software para sistemas operativos críticos

Patentes:

NA

Ideas para posibles innovaciones

Debido al bloqueo del tráfico generado por bots, que actualmente supera los 40.000 al día, este contenido está reservado para los miembros de la comunidad.
> Iniciar sesión < o > Registrarse < (100% gratis) para acceder a esto, al igual que a todo el demás contenido y herramientas restringidos.

Relacionado con: verificación formal, comprobación de modelos, demostración de teoremas, métodos formales, corrección, verificación de software, verificación de hardware, lógica temporal.

Contexto histórico

Verificación formal

1970
1973
1980
1980
1980
1982-07-01
1988-06-01
1970
1970-01-01
1975-06-01
1980
1980
1980
1986-01-01
1990

(Si la fecha es desconocida o no es relevante, por ejemplo "mecánica de fluidos", se proporciona una estimación redondeada de su aparición notable)

Invención, innovación y principios técnicos relacionados.

Las imágenes a tamaño completo y las descargas sólo están disponibles, 100% gratis, para los miembros registrados.

> Acceso <