Propiedad de tiempo lineal

En la verificación de modelos , una rama de la informática , las propiedades de tiempo lineal se utilizan para describir los requisitos de un modelo de un sistema informático . Las propiedades de ejemplo incluyen "la máquina expendedora no dispensa una bebida hasta que se haya ingresado dinero" (una propiedad de seguridad ) o "el programa de computadora finalmente termina" (una propiedad de vida ). Las propiedades de equidad se pueden utilizar para descartar caminos poco realistas de un modelo. Por ejemplo, en un modelo de dos semáforos, la propiedad de vivacidad "ambos semáforos están en verde infinitas veces" sólo puede ser cierta bajo la restricción de equidad incondicional "cada semáforo cambia de color infinitamente veces" (para excluir el caso en el que un semáforo es "infinitamente más rápido" que el otro). ^[1]

Formalmente, una propiedad del tiempo lineal es un lenguaje ω sobre el conjunto de potencias de "proposiciones atómicas". Es decir, la propiedad contiene secuencias de conjuntos de proposiciones, cada secuencia conocida como "palabra". Cada propiedad se puede reescribir como " P y Q ocurren" para alguna propiedad de seguridad P y propiedad de vida Q. Una invariante de un sistema es algo que es verdadero o falso para un estado particular. Las propiedades invariantes describen un invariante que cada estado alcanzable de un modelo debe satisfacer, mientras que las propiedades de persistencia tienen la forma "eventualmente, para siempre, algún invariante se mantiene".

Las lógicas temporales , como la lógica temporal lineal, describen tipos de propiedades de tiempo lineal mediante fórmulas.

Este artículo trata sobre propiedades proposicionales de tiempo lineal y no puede manejar predicados sobre estados de programas, por lo que no puede definir una propiedad como: el valor actual de y determina la cantidad de veces que x alterna entre 0 y 1 antes de la terminación. El formalismo más general utilizado en propiedades de seguridad y vitalidad puede manejar esto.

Definición

Sea AP un conjunto de proposiciones atómicas. Una palabra sobre (el conjunto potencia de AP ) es una secuencia infinita de conjuntos de proposiciones, como (para las proposiciones atómicas ). Una propiedad de tiempo lineal (LT) sobre AP es un subconjunto de, es decir, un conjunto de palabras. ^[2] Un ejemplo de una propiedad LT sobre el conjunto es "el conjunto de palabras que contienen una frecuencia infinita". La palabra w está en este conjunto, porque a está contenida en , lo que ocurre infinitamente a menudo. Una palabra que no está en este conjunto es , ya que solo aparece una vez (en el primer conjunto). ${\displaystyle 2^{AP}}$ ${\displaystyle w:=\{a\}\{a,b\}\emptyset \{a,b\}^{\omega }}$ ${\displaystyle AP=\{a,b\}}$ ${\displaystyle (2^{AP})^{\omega }}$ ${\displaystyle \{a,b\}}$ ${\displaystyle \{a,b\}}$ ${\displaystyle x:=\{a\}(\{b\}\emptyset )^{\omega }}$

Una propiedad LT es un lenguaje ω sobre el alfabeto (y viceversa). ${\displaystyle \Sigma =2^{AP}}$

Denotamos por pref ( w ) los prefijos finitos de w (es decir, en el caso anterior). El cierre de una propiedad LT P es: ${\displaystyle \{\{a\},\{a\}\{a,b\},\{a\}\{a,b\}\emptyset ,...\}}$

${\displaystyle {\mathit {closure}}(P):=\{\sigma \in (2^{AP})^{\omega }\mid {\mathit {pref}}(\sigma )\subseteq {\mathit {pref}}(P)\}}$

Aplicaciones

Una estructura de Kripke encima . No satisface la propiedad LT "infinitamente q ", debido a la ruta . Satisface la propiedad "infinitamente p ", porque todos los caminos posibles entran o infinitamente. ${\displaystyle \{p,q\}}$ ${\displaystyle s_{1}s_{2}s_{3}^{\omega }}$ ${\displaystyle s_{1}}$ ${\displaystyle s_{3}}$

Utilizando la teoría de las máquinas de estados finitos , se puede modelar un programa o sistema informático mediante una estructura de Kripke . Las propiedades LT luego describen restricciones sobre las trazas (salidas) de una estructura Kripke. Por ejemplo, si dos semáforos en una intersección están representados por una estructura de Kripke, entonces las proposiciones atómicas pueden ser los colores posibles de cada luz y puede ser deseable que las trazas satisfagan la propiedad LT "los semáforos no pueden ser ambos verdes en el mismo lugar". mismo tiempo" (para evitar colisiones de coches). ^[3]

Si cada rastro de la estructura de Kripke TS es un rastro de TS ', entonces cada propiedad de LT que satisface TS ' es satisfecha por TS . Esto es útil en la verificación de modelos para permitir la abstracción: si un modelo simplificado del sistema satisface una propiedad LT, entonces el modelo real del sistema también la satisfará. ^[4]

Clasificación de propiedades de tiempo lineal.

Propiedades de seguridad

Una propiedad de seguridad tiene informalmente la forma "no sucede nada malo". ^[5] Por ejemplo, si un sistema modela un cajero automático (ATM), entonces dicha propiedad es "no se debe dispensar dinero a menos que se haya ingresado un PIN". ^[6] Formalmente, una propiedad de seguridad es una propiedad LT tal que cualquier palabra que viole la propiedad tiene un "prefijo incorrecto", por lo que ninguna palabra con ese prefijo satisface la propiedad. Es decir, ^[7]

${\displaystyle \forall \sigma \in (2^{AP})^{\omega }\setminus P\ \exists {\text{ a finite prefix}}\ {\hat {\sigma }}:P\cap \{\sigma '\mid {\hat {\sigma }}\ {\text{is a prefix of}}\ \sigma '\}=\emptyset }$

En el ejemplo del cajero automático, un prefijo incorrecto mínimo es un conjunto finito de pasos realizados en los que se dispensa dinero en el último paso y no se ingresa un PIN en ningún paso. Para verificar una propiedad de seguridad, es suficiente considerar solo las trazas finitas de una estructura Kripke y verificar si alguna de dichas trazas es un prefijo incorrecto. ^[8]

Una propiedad LT P es una propiedad de seguridad si y sólo si . ^[9] ${\displaystyle {\mathit {closure}}(P)=P}$

Propiedades invariantes

Una propiedad invariante es un tipo de propiedad de seguridad en la que la condición sólo se refiere al estado actual. ^[10] Por ejemplo, el ejemplo del cajero automático no es una invariante porque no podemos decir si se viola la propiedad al ver que el estado actual es "dispensar dinero", solo al ver que el estado actual es "dispensar dinero" y ningún estado anterior. era "leer PIN". Un ejemplo de invariante es la condición del semáforo "los dos semáforos no pueden estar en verde al mismo tiempo" anterior. Otra es "la variable x nunca es negativa", en un modelo de programa informático.

Formalmente, una invariante tiene la forma:

${\displaystyle P=\{A_{0}A_{1}....\in (2^{AP})^{\omega }\mid \forall j\in \mathbb {N} :A_{j}\ {\text{satisfies}}\ \Phi \}}$

para alguna fórmula lógica proposicional . ^[10] ${\displaystyle \Phi }$

Una estructura de Kripke satisface un invariante si y sólo si cada estado alcanzable satisface el invariante, lo que puede comprobarse mediante una búsqueda en amplitud o en profundidad . ^[11] Las propiedades de seguridad se pueden verificar de forma inductiva utilizando invariantes. ^[12]

Propiedades de vivacidad

Una propiedad de vida tiene informalmente la forma "algo bueno eventualmente sucede". ^[5] Formalmente, P es una propiedad de vida si, es decir, cualquier cadena finita puede continuar hasta una traza válida. ^{[13] [7]} Un ejemplo de propiedad de vida es la propiedad LT anterior "el conjunto de palabras que contienen una frecuencia infinita". Ningún prefijo finito de una palabra puede probar que la palabra no satisface esta propiedad, ya que la palabra podría seguir teniendo infinitos a s. ${\displaystyle {\mathit {pref}}(P)=(2^{AP})^{*}}$

En términos de programas de computadora, las propiedades de vida útiles incluyen "el programa eventualmente termina" y, en la computación concurrente , "cada proceso debe eventualmente ser atendido". ^[14]

Propiedades de persistencia

Una propiedad de persistencia es una propiedad de vida de la forma "eventualmente para siempre ". Es decir, una propiedad de la forma: ^[15] ${\displaystyle \Phi }$

${\displaystyle P=\{A_{0}A_{1}...\in (2^{AP})^{\omega }\mid \exists N\in \mathbb {N} :\forall n\geq N:A_{n}\ {\text{satisfies}}\ \Phi \}}$

Relación entre propiedades de seguridad y vivacidad.

Ninguna propiedad LT distinta de (el conjunto de todas las palabras sobre ) es a la vez una propiedad de seguridad y de vida. ^[16] Aunque no todas las propiedades son una propiedad de seguridad o una propiedad de vida (considere " a ocurre exactamente una vez"), cada propiedad es la intersección de una propiedad de seguridad y una propiedad de vida. ^[5] ${\displaystyle (2^{AP})^{\omega }}$ ${\displaystyle 2^{AP}}$

En topología , el conjunto de todas las palabras puede equiparse con la métrica : ${\displaystyle (2^{AP})^{\omega }}$

${\displaystyle d(w,x):=\inf\{2^{-|s|}\mid s\in {\mathit {pref}}(w)\cap {\mathit {pref}}(x)\}}$

Entonces una propiedad de seguridad es un conjunto cerrado y una propiedad de vida es un conjunto denso . ^[17]

Propiedades de equidad

Las propiedades de equidad son condiciones previas impuestas a un sistema para descartar rastros poco realistas. ^{[18] [19]} La justicia incondicional es de la forma "cada proceso tiene su turno infinitamente a menudo". La justicia fuerte tiene la forma "cada proceso tiene su turno infinitamente a menudo si se habilita infinitamente a menudo". La equidad débil tiene la forma "cada proceso tiene su turno infinitamente seguido si se habilita continuamente desde un punto particular". ^[20]

En algunos sistemas, una restricción de equidad está definida por un conjunto de estados, y un "camino justo" es aquel que pasa por algún estado en la restricción de equidad con infinitas veces. Si hay múltiples restricciones de equidad, entonces un camino justo debe pasar infinitas veces a través de un estado por restricción. ^[21] Un programa "satisface bastante" una propiedad LT P con respecto a un conjunto de condiciones de equidad si para cada camino, el camino no cumple una condición de equidad o satisface P. Es decir, la propiedad P se satisface para todos los caminos justos. ^[22]

Una propiedad de equidad es realizable para una estructura Kripke si cada estado alcanzable tiene un camino justo a partir de ese estado. Mientras un conjunto de condiciones de equidad sean realizables, son irrelevantes para las propiedades de seguridad. ^[23]

Lógica temporal

Se pueden utilizar lógicas temporales como la lógica del árbol de cálculo (CTL) para especificar algunas propiedades de LT. ^[24] Todas las fórmulas de lógica temporal lineal (LTL) son propiedades LT. Mediante un argumento de conteo, vemos que cualquier lógica en la que cada fórmula sea una cadena finita no puede representar todas las propiedades de LT, ya que debe haber muchas fórmulas contables pero hay una cantidad incontable de propiedades de LT.

Notas

1. Baier y Katoen (2008), pág. 126.
2. Baier y Katoen (2008), págs. 97–98.
3. Baier y Katoen (2008), págs. 97–99.
4. Baier y Katoen (2008), pág. 102.
5. Alpern y Schneider (1987).
6. Baier y Katoen (2008), pág. 109.
7. Finkbeiner y Torfah (2017), pág. 4.
8. Baier y Katoen (2008), pág. 112.
9. Baier y Katoen (2008), pág. 113.
10. Baier y Katoen (2008), pág. 105.
11. Baier y Katoen (2008), págs. 105-106.
12. Kern y Greenstreet (1999), pág. 135.
13. Baier y Katoen (2008), pág. 119.
14. D'Silva, Kroening y Weissenbacher (2008), pág. 5.
15. Baier y Katoen (2008), pág. 197.
16. Baier y Katoen (2008), pág. 121.
17. Baier y Katoen (2008), págs. 123-124.
18. Baier y Katoen (2008), pág. 124.
19. Kern y Greenstreet (1999), págs. 131-132.
20. Baier y Katoen (2008), págs. 126-127.
21. Clarke, Grumberg y Kroening (2018), págs.
22. Baier y Katoen (2008), pág. 132.
23. Baier y Katoen (2008), págs. 137-139.
24. Kern y Greenstreet (1999), pág. 127.

Referencias

• Alpern, B.; Schneider, FB (1987). "Reconociendo la seguridad y la vivacidad". Computación distribuída . 2 (3): 117. CiteSeerX  10.1.1.20.5470 . doi :10.1007/BF01782772. S2CID  9717112.
• Baier, Christel ; Katoen, Joost-Pieter (2008). Principios de verificación de modelos . Prensa del MIT. ISBN 9780262026499.
• Clarke, Edmund M .; Grumberg, Orna ; Kroening, Daniel (2018). Comprobación de modelos . Prensa del MIT. ISBN 9780262038836.
• D'Silva, Vijay; Kroening, Daniel ; Weissenbacher, Georg (2008). "Un estudio sobre técnicas automatizadas para la verificación formal de software". Transacciones IEEE sobre diseño asistido por computadora de circuitos y sistemas integrados . 27 (7): 1165-1178. doi :10.1109/TCAD.2008.923410. S2CID  8921624.
• Finkbeiner, Bernd; Torfah, Hazem (2017). "La densidad de las propiedades del tiempo lineal". Apuntes de conferencias sobre informática . Tecnología Automatizada de Verificación y Análisis. vol. 10482. Saltador.
• Kern, Christoph; Greenstreet, Mark R. (1999). "Verificación formal en diseño de hardware: una encuesta". Transacciones ACM sobre automatización del diseño de sistemas electrónicos . 4 (2). Asociación para Maquinaria de Computación. doi :10.1145/307988.307989. ISSN  1084-4309. S2CID  13994730.

Otras lecturas

• Emerson, E.Allen (1990). "Lógica temporal y modal". Manual de informática teórica . B .
• Pnueli, Amir (1986). Aplicaciones de la lógica temporal a la especificación y verificación de sistemas reactivos: un estudio de las tendencias actuales . Apuntes de conferencias sobre informática. vol. 224, págs. 510–584. doi :10.1007/BFb0027047. ISBN 978-3-540-16488-3. {{cite book}}: |journal=ignorado ( ayuda )