Verificación en tiempo de ejecución

La verificación en tiempo de ejecución es un enfoque de análisis y ejecución de sistemas informáticos basado en la extracción de información de un sistema en ejecución y su uso para detectar y posiblemente reaccionar ante comportamientos observados que satisfacen o violan ciertas propiedades. ^[1] Por lo general, se desea que todos los sistemas satisfagan algunas propiedades muy particulares, como la carrera de datos y la libertad de bloqueo , y se pueden implementar mejor mediante algoritmos. Otras propiedades se pueden capturar de manera más conveniente como especificaciones formales . Las especificaciones de verificación en tiempo de ejecución generalmente se expresan en formalismos de predicado de seguimiento, como máquinas de estados finitos , expresiones regulares , patrones libres de contexto , lógicas temporales lineales , etc., o extensiones de estos. Esto permite un enfoque menos ad hoc que las pruebas normales . Sin embargo, cualquier mecanismo para monitorear un sistema en ejecución se considera verificación en tiempo de ejecución, incluida la verificación contra oráculos de prueba e implementaciones de referencia ^{[ cita requerida ]} . Cuando se proporcionan especificaciones de requisitos formales, los monitores se sintetizan a partir de ellas y se infunden dentro del sistema por medio de instrumentación. La verificación en tiempo de ejecución se puede utilizar para muchos propósitos, como monitoreo de políticas de seguridad o protección , depuración, prueba, verificación, validación, creación de perfiles, protección contra fallas, modificación de comportamiento (por ejemplo, recuperación), etc. La verificación en tiempo de ejecución evita la complejidad de las técnicas de verificación formal tradicionales , como la verificación de modelos y la demostración de teoremas, al analizar solo uno o unos pocos rastros de ejecución y al trabajar directamente con el sistema real, escalando así relativamente bien y brindando más confianza en los resultados del análisis (porque evita el paso tedioso y propenso a errores de modelar formalmente el sistema), a expensas de una menor cobertura. Además, a través de sus capacidades reflexivas, la verificación en tiempo de ejecución se puede convertir en una parte integral del sistema de destino, monitoreando y guiando su ejecución durante la implementación.

Historia y contexto

La verificación formal o informal de propiedades especificadas frente a sistemas o programas en ejecución es un tema antiguo (ejemplos notables son la tipificación dinámica en software, o los dispositivos a prueba de fallos o temporizadores de vigilancia en hardware), cuyas raíces precisas son difíciles de identificar. El término verificación en tiempo de ejecución se introdujo formalmente como el nombre de un taller de 2001 ^[2] destinado a abordar problemas en el límite entre la verificación formal y las pruebas. Para bases de código grandes, la escritura manual de casos de prueba resulta ser una tarea que consume mucho tiempo. Además, no todos los errores se pueden detectar durante el desarrollo. Las primeras contribuciones a la verificación automatizada fueron realizadas en el Centro de Investigación Ames de la NASA por Klaus Havelund y Grigore Rosu para lograr altos estándares de seguridad en naves espaciales, vehículos exploradores y tecnología aviónica. ^[3] Propusieron una herramienta para verificar especificaciones en lógica temporal y detectar condiciones de carrera y bloqueos en programas Java mediante el análisis de rutas de ejecución individuales.

En la actualidad, las técnicas de verificación en tiempo de ejecución se presentan a menudo con varios nombres alternativos, como monitoreo en tiempo de ejecución, verificación en tiempo de ejecución, reflexión en tiempo de ejecución, análisis en tiempo de ejecución , análisis dinámico , análisis simbólico dinámico/en tiempo de ejecución, análisis de trazas, análisis de archivos de registro, etc., todos ellos haciendo referencia a instancias del mismo concepto de alto nivel aplicado a diferentes áreas o por académicos de diferentes comunidades. La verificación en tiempo de ejecución está íntimamente relacionada con otras áreas bien establecidas, como las pruebas (en particular, las pruebas basadas en modelos) cuando se utilizan antes de la implementación y los sistemas tolerantes a fallas cuando se utilizan durante la implementación.

Dentro del amplio ámbito de la verificación en tiempo de ejecución, se pueden distinguir varias categorías, tales como:

Monitoreo "sin especificaciones" que apunta a un conjunto fijo de propiedades relacionadas principalmente con la concurrencia, como la atomicidad. El trabajo pionero en esta área es el de Savage et al. con el algoritmo Eraser ^[4].
Monitoreo con respecto a especificaciones lógicas temporales; las primeras contribuciones en esta dirección fueron hechas por Lee, Kannan y sus colaboradores, ^[5]^[6] y Havelund y Rosu,. ^[7]^[8]

Enfoques básicos

El amplio campo de los métodos de verificación en tiempo de ejecución se puede clasificar en tres dimensiones: ^[9]

El sistema puede ser monitoreado durante la ejecución misma (en línea) o después de la ejecución, por ejemplo en forma de análisis de registros (fuera de línea).
El código de verificación se integra en el sistema (como se hace en la Programación Orientada a Aspectos) o se proporciona como una entidad externa.
El monitor puede reportar la violación o validación de la especificación deseada.

Sin embargo, el proceso básico en la verificación en tiempo de ejecución sigue siendo similar: ^[9]

Un monitor se crea a partir de alguna especificación formal. Este proceso normalmente se puede realizar de forma automática si existen autómatas equivalentes para las fórmulas del lenguaje formal en el que se especifica la propiedad. Para transformar una expresión regular , se puede utilizar una máquina de estados finitos ; una propiedad en lógica temporal lineal se puede transformar en un autómata de Büchi (véase también Lógica temporal lineal a autómata de Büchi ).
El sistema está instrumentado para enviar eventos relacionados con su estado de ejecución al monitor.
El sistema se ejecuta y es verificado por el monitor.
El monitor verifica el seguimiento del evento recibido y emite un veredicto sobre si se cumple la especificación. Además, el monitor envía comentarios al sistema para corregir posibles comportamientos incorrectos. Cuando se utiliza la supervisión fuera de línea, el sistema responsable no puede recibir comentarios, ya que la verificación se realiza en un momento posterior.

Ejemplos

Los ejemplos siguientes analizan algunas propiedades simples que han sido consideradas, posiblemente con pequeñas variaciones, por varios grupos de verificación en tiempo de ejecución hasta el momento de escribir este artículo (abril de 2011). Para hacerlos más interesantes, cada propiedad a continuación utiliza un formalismo de especificación diferente y todas son paramétricas. Las propiedades paramétricas son propiedades sobre trazas formadas con eventos paramétricos, que son eventos que vinculan datos a parámetros. Aquí una propiedad paramétrica tiene la forma , donde es una especificación en algún formalismo apropiado que se refiere a eventos paramétricos genéricos (no instanciados). La intuición para tales propiedades paramétricas es que la propiedad expresada por debe cumplirse para todas las instancias de parámetros encontradas (a través de eventos paramétricos) en la traza observada. Ninguno de los siguientes ejemplos es específico de ningún sistema de verificación en tiempo de ejecución en particular, aunque obviamente se necesita soporte para parámetros. En los siguientes ejemplos se asume la sintaxis de Java, por lo tanto "==" es igualdad lógica, mientras que "=" es asignación. Algunos métodos (por ejemplo, en UnsafeEnumExample) son métodos ficticios, que no son parte de la API de Java, que se utilizan para mayor claridad. $\para todos los parámetros:\varphi$ ${\estilo de visualización \varphi}$ ${\estilo de visualización \varphi}$ update()

TieneSiguiente

La interfaz Java Iterator requiere que hasNext()se llame al método y que devuelva true antes de que next()se llame al método. Si esto no ocurre, es muy posible que un usuario itere "hasta el final" de una colección. La figura de la derecha muestra una máquina de estados finitos que define un posible monitor para comprobar y hacer cumplir esta propiedad con verificación en tiempo de ejecución. Desde el estado desconocido , siempre es un error llamar al next()método porque dicha operación podría ser insegura. Si hasNext()se llama a y devuelve true , es seguro llamar a next(), por lo que el monitor ingresa al estado more . Sin embargo, si el hasNext()método devuelve false , no hay más elementos y el monitor ingresa al estado none . En los estados more y nonehasNext() , llamar al método no proporciona información nueva. Es seguro llamar al next()método desde el estado more , pero se vuelve unknown si existen más elementos, por lo que el monitor vuelve a ingresar al estado unknown inicial . Finalmente, llamar al next()método desde el estado none da como resultado ingresar al estado de error . Lo que sigue es una representación de esta propiedad utilizando lógica temporal lineal de tiempo pasado paramétrico .

$\forall ~{\text{Iterador}}~i\quad i.{\text{siguiente}}()~\rightarrow ~\odot (i.{\text{tieneSiguiente}}()==verdadero)$

Esta fórmula dice que cualquier llamada al next()método debe ser precedida inmediatamente por una llamada al hasNext()método que devuelva true. La propiedad aquí es paramétrica en el Iterator i. Conceptualmente, esto significa que habrá una copia del monitor para cada Iterator posible en un programa de prueba, aunque los sistemas de verificación en tiempo de ejecución no necesitan implementar sus monitores paramétricos de esta manera. El monitor para esta propiedad se configuraría para activar un controlador cuando se viole la fórmula (equivalentemente cuando la máquina de estados finitos ingrese al estado de error ), lo que ocurrirá cuando next()se llame a cualquiera sin llamar primero a hasNext(), o cuando hasNext()se llame antes de next(), pero devuelva false .

Enumeración insegura

Código que viola la propiedad UnsafeEnum

La clase Vector en Java tiene dos medios para iterar sobre sus elementos. Se puede utilizar la interfaz Iterator, como se ve en el ejemplo anterior, o se puede utilizar la interfaz Enumeration. Además de la adición de un método remove para la interfaz Iterator, la principal diferencia es que Iterator es "fail fast" mientras que Enumeration no lo es. Esto significa que si se modifica el Vector (excepto mediante el método remove de Iterator) cuando se está iterando sobre el Vector utilizando un Iterator, se lanza una ConcurrentModificationException. Sin embargo, cuando se utiliza una Enumeration este no es el caso, como se mencionó. Esto puede dar como resultado resultados no deterministas de un programa porque el Vector se deja en un estado inconsistente desde la perspectiva de la Enumeration. Para los programas heredados que aún utilizan la interfaz Enumeration, se puede desear hacer cumplir que las Enumerations no se utilicen cuando se modifica su Vector subyacente. Se puede utilizar el siguiente patrón regular paramétrico para hacer cumplir este comportamiento:

∀ Vector v , Enumeración e : ( e = v .elements()) ( e .nextElement()) ^* v .update() e .nextElement()

Este patrón es paramétrico tanto en la Enumeración como en el Vector. Intuitivamente, y como los sistemas de verificación en tiempo de ejecución anteriores no necesitan implementar sus monitores paramétricos de esta manera, se puede pensar en el monitor paramétrico para esta propiedad como la creación y el seguimiento de una instancia de monitor no paramétrico para cada par posible de Vector y Enumeración. Algunos eventos pueden afectar a varios monitores al mismo tiempo, como v.update(), por lo que el sistema de verificación en tiempo de ejecución debe (de nuevo conceptualmente) enviarlos a todos los monitores interesados. Aquí se especifica la propiedad de modo que indique los malos comportamientos del programa. Esta propiedad, entonces, debe ser monitoreada para la coincidencia del patrón. La figura a la derecha muestra el código Java que coincide con este patrón, violando así la propiedad. El Vector, v, se actualiza después de que se crea la Enumeración, e, y luego se utiliza e.

Bloqueo seguro

Los dos ejemplos anteriores muestran propiedades de estado finito, pero las propiedades utilizadas en la verificación en tiempo de ejecución pueden ser mucho más complejas. La propiedad SafeLock aplica la política de que la cantidad de adquisiciones y liberaciones de una clase de bloqueo (reentrante) coincidan dentro de una llamada de método determinada. Esto, por supuesto, no permite la liberación de bloqueos en métodos distintos de los que los adquieren, pero es muy posible que este sea un objetivo deseable para el sistema probado. A continuación se muestra una especificación de esta propiedad utilizando un patrón paramétrico libre de contexto:

∀ Hilo t , Bloqueo l : S →ε | S start( t ) S end( t ) | S l .acquire( t ) S l .release( t )

Un rastro que muestra dos violaciones de la propiedad SafeLock

El patrón especifica secuencias balanceadas de pares anidados de inicio/fin y adquisición/liberación para cada subproceso y bloqueo ( es la secuencia vacía). Aquí, inicio y fin se refieren al inicio y fin de cada método en el programa (excepto las llamadas a adquirir y liberar). Son paramétricos en el subproceso porque es necesario asociar el inicio y fin de los métodos si y solo si pertenecen al mismo subproceso. Los eventos de adquisición y liberación también son paramétricos en el subproceso por la misma razón. Son, además, paramétricos en el bloqueo porque no deseamos asociar las liberaciones de un bloqueo con las adquisiciones de otro. En el extremo, es posible que haya una instancia de la propiedad, es decir, una copia del mecanismo de análisis sintáctico libre de contexto, para cada combinación posible de subproceso con bloqueo; esto sucede, nuevamente, intuitivamente, porque los sistemas de verificación en tiempo de ejecución pueden implementar la misma funcionalidad de manera diferente. Por ejemplo, si un sistema tiene subprocesos , y con bloqueos y , entonces es posible tener que mantener instancias de propiedad para los pares < , >, < , >, < , >, < , >, < , > y < , >. Esta propiedad debe supervisarse para detectar fallos en la coincidencia con el patrón porque el patrón especificó el comportamiento correcto. La figura de la derecha muestra un seguimiento que produce dos violaciones de esta propiedad. Los pasos hacia abajo en la figura representan el comienzo de un método, mientras que los pasos hacia arriba son el final. Las flechas grises en la figura muestran la coincidencia entre adquisiciones y liberaciones dadas del mismo bloqueo. Para simplificar, el seguimiento muestra solo un subproceso y un bloqueo. $\épsilon$ $estilo de visualización t_{1}$ $estilo de visualización t_{2}$ $estilo de visualización t_{3}$ $estilo de visualización l_{1}}$ $estilo de visualización l_{2}}$ $estilo de visualización t_{1}$ $estilo de visualización l_{1}}$ $estilo de visualización t_{1}$ $estilo de visualización l_{2}}$ $estilo de visualización t_{2}$ $estilo de visualización l_{1}}$ $estilo de visualización t_{2}$ $estilo de visualización l_{2}}$ $estilo de visualización t_{3}$ $estilo de visualización l_{1}}$ $estilo de visualización t_{3}$ $estilo de visualización l_{2}}$

Desafíos y aplicaciones de la investigación

La mayor parte de la investigación de verificación en tiempo de ejecución aborda uno o más de los temas enumerados a continuación.

Reducción de la sobrecarga en tiempo de ejecución

La observación de un sistema en ejecución suele generar cierta sobrecarga en tiempo de ejecución (los monitores de hardware pueden ser una excepción). Es importante reducir la sobrecarga de las herramientas de verificación en tiempo de ejecución tanto como sea posible, en particular cuando los monitores generados se implementan con el sistema. Las técnicas para reducir la sobrecarga en tiempo de ejecución incluyen:

Instrumentación mejorada . Extraer eventos del sistema en ejecución y enviarlos a los monitores puede generar una gran sobrecarga en tiempo de ejecución si se hace de manera ingenua. Una buena instrumentación del sistema es fundamental para cualquier herramienta de verificación en tiempo de ejecución, a menos que la herramienta se dirija explícitamente a los registros de ejecución existentes. Existen muchos enfoques de instrumentación en uso actualmente, cada uno con sus ventajas y desventajas, que van desde la instrumentación personalizada o manual hasta bibliotecas especializadas, la compilación en lenguajes orientados a aspectos, la ampliación de la máquina virtual y la creación de soporte de hardware.
Combinación con análisis estático . Una combinación común^{[ cita requerida ]} de análisis estático y dinámico, particularmente encontrada en compiladores, es monitorear todos los requisitos que no se pueden descargar estáticamente. Un enfoque dual y en última instancia equivalente tiende a convertirse en la norma^{[ cita requerida ]} en la verificación en tiempo de ejecución, es decir, usar análisis estático para reducir la cantidad de monitoreo que de otro modo sería exhaustivo. El análisis estático se puede realizar tanto en la propiedad a monitorear como en el sistema a monitorear. El análisis estático de la propiedad a monitorear puede revelar que ciertos eventos son innecesarios para monitorear, que la creación de ciertos monitores puede retrasarse y que ciertos monitores existentes nunca se activarán y, por lo tanto, pueden recolectarse como basura. El análisis estático del sistema a monitorear puede detectar código que nunca puede influir en los monitores. Por ejemplo, al monitorear la propiedad HasNext anterior, no es necesario instrumentar partes de código donde cada llamadai.next()es precedida inmediatamente en cualquier ruta por una llamadai.hasnext()que devuelve verdadero (visible en el gráfico de flujo de control).
Generación y gestión eficiente de monitores . Al monitorear propiedades paramétricas como las de los ejemplos anteriores, el sistema de monitoreo necesita realizar un seguimiento del estado de la propiedad monitoreada con respecto a cada instancia de parámetro. El número de tales instancias es teóricamente ilimitado y tiende a ser enorme en la práctica. Un desafío de investigación importante es cómo enviar de manera eficiente los eventos observados precisamente a aquellas instancias que los necesitan. Un desafío relacionado es cómo mantener pequeño el número de tales instancias (para que el envío sea más rápido), o en otras palabras, cómo evitar la creación de instancias innecesarias durante el mayor tiempo posible y, dualmente, cómo eliminar instancias ya creadas tan pronto como se vuelvan innecesarias. Finalmente, los algoritmos de monitoreo paramétrico generalmente generalizan algoritmos similares para generar monitores no paramétricos. Por lo tanto, la calidad de los monitores no paramétricos generados dicta la calidad de los monitores paramétricos resultantes. Sin embargo, a diferencia de otros enfoques de verificación (por ejemplo, verificación de modelos), el número de estados o el tamaño del monitor generado es menos importante en la verificación en tiempo de ejecución; De hecho, algunos monitores pueden tener una cantidad infinita de estados, como el de la propiedad SafeLock mencionada anteriormente, aunque en un momento dado solo puede haber ocurrido una cantidad finita de estados. Lo importante es la eficiencia con la que el monitor pasa de un estado a su siguiente estado cuando recibe un evento del sistema en ejecución.

Especificación de propiedades

Uno de los principales impedimentos prácticos de todos los enfoques formales es que sus usuarios son reacios a aprender a leer o escribir especificaciones, o no saben o no quieren hacerlo. En algunos casos, las especificaciones son implícitas, como las de bloqueos y carreras de datos, pero en la mayoría de los casos es necesario generarlas. Un inconveniente adicional, en particular en el contexto de la verificación en tiempo de ejecución, es que muchos lenguajes de especificación existentes no son lo suficientemente expresivos para capturar las propiedades deseadas.

Formalismos mejores. Se ha dedicado una cantidad significativa de trabajo en la comunidad de verificación en tiempo de ejecución al diseño de formalismos de especificación que se ajusten a los dominios de aplicación deseados para la verificación en tiempo de ejecución mejor que los formalismos de especificación convencionales. Algunos de estos consisten en cambios sintácticos leves o nulos en los formalismos convencionales, pero solo en cambios en su semántica (por ejemplo, semántica de traza finita versus semántica de traza infinita, etc.) y en su implementación (máquinas de estados finitos optimizadas en lugar de autómatas de Büchi, etc.). Otros extienden los formalismos existentes con características que son adecuadas para la verificación en tiempo de ejecución pero que pueden no serlo fácilmente para otros enfoques de verificación, como agregar parámetros, como se ve en los ejemplos anteriores. Finalmente, hay formalismos de especificación que se han diseñado específicamente para la verificación en tiempo de ejecución, intentando lograr lo mejor para este dominio y preocupándose poco por otros dominios de aplicación. Diseñar formalismos de especificación universalmente mejores o específicamente mejores para el dominio para la verificación en tiempo de ejecución es y seguirá siendo uno de sus principales desafíos de investigación.
Propiedades cuantitativas. En comparación con otros métodos de verificación, la verificación en tiempo de ejecución puede operar sobre valores concretos de variables de estado del sistema, lo que permite recopilar información estadística sobre la ejecución del programa y utilizar esta información para evaluar propiedades cuantitativas complejas. Se necesitan lenguajes de propiedades más expresivos que nos permitan aprovechar al máximo esta capacidad.
Mejores interfaces. Leer y escribir especificaciones de propiedades no es fácil para los no expertos. Incluso los expertos suelen contemplar durante minutos fórmulas lógicas temporales relativamente pequeñas (en particular cuando tienen operadores "hasta" anidados). Un área de investigación importante es el desarrollo de interfaces de usuario potentes para diversos formalismos de especificación que permitan a los usuarios comprender, escribir y tal vez incluso visualizar propiedades con mayor facilidad.
Especificaciones de minería. No importa qué herramienta de soporte esté disponible para ayudar a los usuarios a producir especificaciones, casi siempre estarán más contentos de no tener que escribir ninguna especificación, particularmente cuando son triviales. Afortunadamente, hay muchos programas que supuestamente hacen un uso correcto de las acciones/eventos sobre los que uno quiere tener propiedades. Si ese es el caso, entonces es concebible que uno quiera hacer uso de esos programas correctos aprendiendo automáticamente de ellos las propiedades deseadas. Incluso si se espera que la calidad general de las especificaciones extraídas automáticamente sea menor que la de las especificaciones producidas manualmente, pueden servir como punto de partida para estas últimas o como base para herramientas de verificación automática en tiempo de ejecución destinadas específicamente a encontrar errores (donde una especificación deficiente se convierte en falsos positivos o negativos, a menudo aceptables durante las pruebas).

Modelos de ejecución y análisis predictivo

La capacidad de un verificador de tiempo de ejecución para detectar errores depende estrictamente de su capacidad para analizar los rastros de ejecución. Cuando los monitores se implementan con el sistema, la instrumentación suele ser mínima y los rastros de ejecución son lo más simples posibles para mantener baja la sobrecarga de tiempo de ejecución. Cuando se utiliza la verificación de tiempo de ejecución para realizar pruebas, se pueden permitir instrumentaciones más completas que aumenten los eventos con información importante del sistema que los monitores pueden utilizar para construir y, por lo tanto, analizar modelos más refinados del sistema en ejecución. Por ejemplo, aumentar los eventos con información del reloj vectorial y con información de flujo de datos y control permite a los monitores construir un modelo causal del sistema en ejecución en el que la ejecución observada fue solo una instancia posible. Cualquier otra permutación de eventos que sea coherente con el modelo es una ejecución factible del sistema, que podría ocurrir bajo un entrelazado de subprocesos diferente. La detección de violaciones de propiedades en dichas ejecuciones inferidas (al monitorearlas) hace que el monitor prediga errores que no ocurrieron en la ejecución observada, pero que pueden ocurrir en otra ejecución del mismo sistema. Un desafío de investigación importante es extraer modelos de los rastros de ejecución que comprendan tantos otros rastros de ejecución como sea posible.

Modificación de conducta

A diferencia de las pruebas o la verificación exhaustiva, la verificación en tiempo de ejecución promete permitir que el sistema se recupere de las violaciones detectadas, mediante la reconfiguración, microrreinicios o mecanismos de intervención más precisos, a veces denominados ajuste o dirección. La implementación de estas técnicas dentro del marco riguroso de la verificación en tiempo de ejecución da lugar a desafíos adicionales.

Especificación de acciones. Es necesario especificar la modificación que se realizará de una manera suficientemente abstracta que no requiera que el usuario conozca detalles de implementación irrelevantes. Además, es necesario especificar cuándo se puede realizar dicha modificación para mantener la integridad del sistema.
Razonamiento sobre los efectos de la intervención. Es importante saber que una intervención mejora la situación o al menos no la empeora.
Interfaces de acción. De manera similar a la instrumentación para la monitorización, necesitamos habilitar el sistema para recibir invocaciones de acciones. Los mecanismos de invocación necesariamente dependerán de los detalles de implementación del sistema. Sin embargo, a nivel de especificación, necesitamos proporcionar al usuario una forma declarativa de proporcionar retroalimentación al sistema especificando qué acciones se deben aplicar, cuándo y bajo qué condiciones.

Trabajo relacionado

Programación orientada a aspectos

Los investigadores en verificación en tiempo de ejecución reconocieron el potencial de usar la programación orientada a aspectos como una técnica para definir la instrumentación del programa de una manera modular. La programación orientada a aspectos (AOP) generalmente promueve la modularización de preocupaciones transversales. La verificación en tiempo de ejecución naturalmente es una de esas preocupaciones y, por lo tanto, puede beneficiarse de ciertas propiedades de la AOP. Las definiciones de monitor orientadas a aspectos son en gran medida declarativas y, por lo tanto, tienden a ser más simples de razonar que la instrumentación expresada a través de una transformación de programa escrita en un lenguaje de programación imperativo. Además, los análisis estáticos pueden razonar sobre aspectos de monitoreo más fácilmente que sobre otras formas de instrumentación de programa, ya que toda la instrumentación está contenida dentro de un solo aspecto. Por lo tanto, muchas herramientas de verificación en tiempo de ejecución actuales se construyen en forma de compiladores de especificaciones, que toman una especificación expresiva de alto nivel como entrada y producen como código de salida escrito en algún lenguaje de programación orientado a aspectos (como AspectJ ).

Combinación con verificación formal

La verificación en tiempo de ejecución, si se utiliza en combinación con un código de recuperación demostrablemente correcto, puede proporcionar una infraestructura invaluable para la verificación de programas, lo que puede reducir significativamente la complejidad de este último. Por ejemplo, verificar formalmente el algoritmo de ordenamiento por montículos es muy desafiante. Una técnica menos desafiante para verificarlo es monitorear su salida para que se ordene (un monitor de complejidad lineal) y, si no se ordena, ordenarla utilizando algún procedimiento fácilmente verificable, digamos ordenamiento por inserción. El programa de ordenamiento resultante ahora es más fácil de verificar, lo único que se requiere del ordenamiento por montículos es que no destruya los elementos originales considerados como un multiconjunto, lo que es mucho más fácil de probar. Mirando desde la otra dirección, se puede utilizar la verificación formal para reducir la sobrecarga de la verificación en tiempo de ejecución, como ya se mencionó anteriormente para el análisis estático en lugar de la verificación formal. De hecho, se puede comenzar con un programa completamente verificado en tiempo de ejecución, pero probablemente lento. Luego se puede utilizar la verificación formal (o análisis estático) para descargar los monitores, de la misma manera que un compilador utiliza el análisis estático para descargar las verificaciones en tiempo de ejecución de la corrección de tipos o la seguridad de la memoria .

Aumentar la cobertura

En comparación con los métodos de verificación más tradicionales, una desventaja inmediata de la verificación en tiempo de ejecución es su cobertura reducida. Esto no es problemático cuando los monitores de tiempo de ejecución se implementan con el sistema (junto con el código de recuperación adecuado que se ejecutará cuando se viole la propiedad), pero puede limitar la eficacia de la verificación en tiempo de ejecución cuando se utiliza para encontrar errores en los sistemas. Las técnicas para aumentar la cobertura de la verificación en tiempo de ejecución con fines de detección de errores incluyen:

Generación de entradas. Es bien sabido que generar un buen conjunto de entradas (valores de variables de entrada del programa, valores de llamadas del sistema, programaciones de subprocesos, etc.) puede aumentar enormemente la efectividad de las pruebas. Esto también es válido para la verificación en tiempo de ejecución utilizada para la detección de errores, pero además de utilizar el código del programa para impulsar el proceso de generación de entradas, en la verificación en tiempo de ejecución también se pueden utilizar las especificaciones de propiedades, cuando estén disponibles, y también se pueden utilizar técnicas de monitoreo para inducir los comportamientos deseados. Este uso de la verificación en tiempo de ejecución la relaciona estrechamente con las pruebas basadas en modelos, aunque las especificaciones de verificación en tiempo de ejecución son típicamente de propósito general, no necesariamente diseñadas para fines de prueba. Considere, por ejemplo, que uno desea probar la propiedad UnsafeEnum de propósito general anterior. En lugar de simplemente generar el monitor mencionado anteriormente para observar pasivamente la ejecución del sistema, uno puede generar un monitor más inteligente que congela el subproceso que intenta generar el segundo evento e.nextElement() (justo antes de que lo genere), dejando que los otros subprocesos se ejecuten con la esperanza de que uno de ellos pueda generar un evento v.update() , en cuyo caso se ha encontrado un error.
Ejecución simbólica dinámica. En la ejecución simbólica, los programas se ejecutan y monitorean simbólicamente, es decir, sin entradas concretas. Una ejecución simbólica del sistema puede cubrir un gran conjunto de entradas concretas. Las técnicas de resolución de restricciones o de verificación de satisfacibilidad disponibles comercialmente se utilizan a menudo para impulsar ejecuciones simbólicas o para explorar sistemáticamente su espacio. Cuando los verificadores de satisfacibilidad subyacentes no pueden manejar un punto de elección, se puede generar una entrada concreta para pasar ese punto; esta combinación de ejecución concreta y simbólica también se conoce como ejecución concólica.

Véase también

Referencias

^ Ezio Bartocci y Yliès Falcone (eds), Lectures on Runtime Verification - Introductory and Advanced Topics, parte de la serie de libros Lecture Notes in Computer Science (LNCS, volumen 10457), también parte de la subserie de libros Programming and Software Engineering (LNPSE, volumen 10457), 2018. Lecture Notes in Computer Science. Vol. 10457. 2018. doi :10.1007/978-3-319-75632-5. ISBN 978-3-319-75631-8.S2CID23246713 .
^ "RV'01 - Primer taller sobre verificación en tiempo de ejecución". Conferencias sobre verificación en tiempo de ejecución . 23 de julio de 2001. Consultado el 25 de febrero de 2017 .
^ Klaus Havelund y Grigore Rosu. 2004. Una descripción general de la herramienta de verificación en tiempo de ejecución Java PathExplorer. Métodos formales en diseño de sistemas, 24(2), marzo de 2004.
^ Stefan Savage, Michael Burrows, Greg Nelson, Patrick Sobalvarro y Thomas Anderson. 1997. Eraser: un detector de carreras de datos dinámico para programas multiproceso. ACM Trans. Comput. Syst. 15(4), noviembre de 1997, págs. 391-411.
^ Moonjoo Kim, Mahesh Viswanathan, Insup Lee, Hanêne Ben-Abdellah, Sampath Kannan y Oleg Sokolsky, Monitoreo formalmente especificado de propiedades temporales, Actas de la Conferencia Europea sobre Sistemas en Tiempo Real, junio de 1999.
^ Insup Lee, Sampath Kannan, Moonjoo Kim, Oleg Sokolsky, Mahesh Viswanathan, Garantía de tiempo de ejecución basada en especificaciones formales, Actas de la Conferencia internacional sobre técnicas y aplicaciones de procesamiento paralelo y distribuido, junio de 1999.
^ Klaus Havelund, Uso del análisis en tiempo de ejecución para guiar la verificación de modelos de programas Java, 7º Taller internacional SPIN, agosto de 2000.
^ Klaus Havelund y Grigore Rosu, Monitoreo de programas mediante reescritura, Ingeniería de software automatizada (ASE'01), noviembre de 2001.
^ de Yliès Falcone, Klaus Havelund y Giles, Un tutorial sobre verificación en tiempo de ejecución, 2013