derivación de contraejemplos para model checking cuantitativo miguel e. andrés famaf – córdoba...
TRANSCRIPT
Derivación de Contraejemplos para Derivación de Contraejemplos para Model Checking CuantitativoModel Checking Cuantitativo
Miguel E. Andrés
FaMAF – Córdoba
Director: Pedro D’Argenio
2
ResumenResumen
Motivación El Problema Solución: Caso Determinista
Carriles Solución
Reducción del Modelo Derivación del Contraejemplo
Optimizaciones Solución: Caso No Determinista Implementación Conclusión Trabajos Futuros
3
ResumenResumen
Motivación El Problema Solución: Caso Determinista
Carriles Solución
Reducción del Modelo Derivación del Contraejemplo
Optimizaciones Solución: Caso No Determinista Implementación Conclusión Trabajos Futuros
4
Model Checking Clásico (Cualitativo)Model Checking Clásico (Cualitativo)
MotivaciónMotivación
EjemploEjemploModel Checking es una técnica de
verificación tal que, una vez dado el modelo del sistema bajo estudio y una
propiedad para verificar, permite decidir automáticamente si la propiedad se satisface o no
DefiniciónDefinición
La justificación de la violación de una propiedad no satisfecha es un
feedback muy importante que nos permite corregir el diseño o la
implementación del sistema modelado.
ContraejemploContraejemplo
5
Nuestro Problema: Nuestro Problema: Model Checking CuantitativoModel Checking Cuantitativo (mas complejo)(mas complejo)
Dado el NO DETERMINISMO, sólo podemos hablar de PROBABILIDADES
MINIMAS y MAXIMAS
MotivaciónMotivación
Propiedad CuantitativaPropiedad Cuantitativa
2/3
2/3
1/3
1/3 1/3
1/3
1/21/21/2 1/2
1/2
1/2
1/3
Modelo No Determinista y ProbabilistaModelo No Determinista y Probabilista
6
Problema No ExploradoProblema No Explorado Trabajos Relacionados Trabajos Relacionados
Counterexamples for Timed Probabilistic Reachability (Aljazzar,Hermanns,Leue)
Sin EmbargoSin Embargo Los contraejemplos se limitan a una única ejecución Es necesario especificar una cota para la longitud de la
ejecución contraejemplo No contempla comportamientos No Deterministas en el
sistema
MotivaciónMotivación
7
ResumenResumen
Motivación El Problema Solución: Caso Determinista
Carriles Solución
Reducción del Modelo Derivación del Contraejemplo
Optimizaciones Solución: Caso No Determinista Implementación Conclusión Trabajos Futuros
8
El ProblemaEl Problema
Propiedad de Alcanzabilidad (acotada superiormente):La probabilidad de alcanzar una condición finales menor o igual que un valor probabilista dado.
“Dado un modelo Probabilista y No Determinista,
y una propiedad de alcanzabilidad no válida
en dicho modelo, encontrar un contraejemplo”
Testigo de ContraejemploTestigo de Contraejemplo
9
ResumenResumen
Motivación El Problema Solución: Caso Determinista
Carriles Solución
Reducción del Modelo Derivación del Contraejemplo
Optimizaciones Solución: Caso No Determinista Implementación Conclusión Trabajos Futuros
10
El ModeloEl Modelo: Cadenas de Markov de Tiempo Discreto (CMTD): Cadenas de Markov de Tiempo Discreto (CMTD)
Solución: Caso Determinista Solución: Caso Determinista [Definiciones][Definiciones]
11
DefinicionesDefiniciones
Caminos:
Probabilidad de Caminos:
Probabilidad de Alcanzabilidad:
Cálculo de Probabilidad
de Alcanzabilidad:
Solución: Caso Determinista Solución: Caso Determinista [Definiciones][Definiciones]
12
Solución: Caso Determinista Solución: Caso Determinista [Carriles][Carriles]
ProblemasProblemas Resultados Menos
precisos. Resultados aportan la
misma información. Resultados muy distantes
de un Contraejemplo. Infinitos resultados.
SoluciónSolución
ContraejemploContraejemplo
13
Un Carril es un camino sin ciclos. El conjunto de caminos que “fluyen” a
través del carril se denomina Torrente asociado a .
La probabilidad asociada a un Carril es la probabilidad de que ocurra alguno de los caminos de su torrente asociado.
Solución: Caso Determinista Solución: Caso Determinista [Carriles][Carriles]
CarrilesCarriles y sus y sus TorrentesTorrentes asociados asociados
14
CarrilesCarriles y sus y sus TorrentesTorrentes asociados asociados
Solución: Caso Determinista Solución: Caso Determinista [Carriles][Carriles]
15
ResumenResumen
Motivación El Problema Solución: Caso Determinista
Carriles Solución
Reducción del Modelo Derivación del Contraejemplo
Optimizaciones Solución: Caso No Determinista Implementación Conclusión Trabajos Futuros
16
Solución: Caso DeterministaSolución: Caso Determinista
SoluciónSolución1. Pre Procesamiento
Agregar información a cada estado que nos permita identificar los Carriles y Componentes Fuertemente Conexas Maximales. [DFS-E]
Obtener una Cadena de Markov reducida.
2. Búsqueda Búsqueda guiada del Carril con mayor
probabilidad en la cadena reducida. [Z*]
17
Solución: Caso Determinista Solución: Caso Determinista [Pre Procesamiento][Pre Procesamiento]
18
alcanzadoprocesado
no-alcanzado
Solución: Caso Determinista Solución: Caso Determinista [Pre Procesamiento][Pre Procesamiento]
19
[s3]
suc_cfcm
carril_id dist pred suc
S2[(1,1,s1, s4), (2,1,s0, s4)]
Flag: • 0 Ninguno• 1 Carril• 2 Ciclo• 3 Carril y Ciclo
Solución: Caso Determinista Solución: Caso Determinista [Pre Procesamiento][Pre Procesamiento]
20
Solución: Caso Determinista Solución: Caso Determinista [Pre Procesamiento][Pre Procesamiento]
Componente FuertementeConexa Maximal
Reducción de la CadenaReducción de la Cadena Sacar estados no necesarios (flag=0) Reducir CFCM`s
21
Solución: Caso Determinista Solución: Caso Determinista [Pre Procesamiento][Pre Procesamiento]
El Conjunto de todos los Carriles El conjunto de todas las CFCM La Cadena Reducida
Información obtenida en Pre Procesamiento:Información obtenida en Pre Procesamiento:
22
ResumenResumen
Motivación El Problema Solución: Caso Determinista
Carriles Solución
Reducción del Modelo Derivación del Contraejemplo
Optimizaciones Solución: Caso No Determinista Implementación Conclusión Trabajos Futuros
23
Búsqueda del Carril MáximoBúsqueda del Carril Máximo (Z*) (Z*)
Solución: Caso Determinista Solución: Caso Determinista [Búsqueda][Búsqueda]
Donde: y
24
Ejemplo (Z*)
Solución: Caso Determinista Solución: Caso Determinista [Resultados][Resultados]
Resultado del Programa
Propiedad Informac.Comienzo TerminarZ*Error
Encontra-do?
No
SiCarril
Modelo de Debugueo
Otro Carril
PrePro.Modelo Cadena R.
25
ResumenResumen
Motivación El Problema Solución: Caso Determinista
Carriles Solución
Reducción del Modelo Derivación del Contraejemplo
Optimizaciones Solución: Caso No Determinista Implementación Conclusión Trabajos Futuros
26
La función hh es una función que asocia a cada estado s una sobre
estimación de la máxima probabilidad entre los caminos desde s hasta
algún estado que satisfaga determinada condición (Goal), es decir:
Solución: Caso Determinista Solución: Caso Determinista [Optimización][Optimización]
h-Optimizaciónh-Optimización
Obtención de hObtención de h
27
Reducción por Demanda (2da Optimización)Reducción por Demanda (2da Optimización)
Solución: Caso Determinista Solución: Caso Determinista [Optimización][Optimización]
Para la obtención del carril máximo nono es necesario reducir todasreducir todas las CFCM CFCM de la cadena!!!
La reducciónreducción se hace “por demandapor demanda” extendiendo Z*Z*
28
Solución: Caso Determinista Solución: Caso Determinista [Optimización][Optimización]
29
ResumenResumen
Motivación El Problema Solución: Caso Determinista
Carriles Solución
Reducción del Modelo Derivación del Contraejemplo
Optimizaciones Solución: Caso No Determinista Implementación Conclusión Trabajos Futuros
30
Solución: Caso No Determinista Solución: Caso No Determinista [Definiciones][Definiciones]
Modelo (Procesos de Decisión de Markov)Modelo (Procesos de Decisión de Markov)
Los Schedulers inducen Cadenas de Markov!
EjemploEjemplo
2/3
2/3
1/3
1/3 1/3
1/3
1/21/21/2 1/2
1/2
1/2
1/3
No Determinismo!No Determinismo!
Schedulers:
31
Solución: Caso No Determinista Solución: Caso No Determinista [Definiciones][Definiciones]
Probabilidades Máximas y MínimasProbabilidades Máximas y Mínimas
El valor máximo entre todas las probabilidades obtenidas en las Cadenas de Markov inducidas por los distintos schedulers.
El valor mínimo entre todas las probabilidades obtenidas en las Cadenas de Markov inducidas por los distintos schedulers.
32
p
q
s0
s1
s2
s3
s4
s5
s6
s7
Solución: Caso No Determinista Solución: Caso No Determinista [Ejemplo][Ejemplo]
33
ResumenResumen
Motivación El Problema Solución: Caso Determinista
Carriles Solución
Reducción del Modelo Derivación del Contraejemplo
Optimizaciones Solución: Caso No Determinista Implementación Conclusión Trabajos Futuros
34
Se implementó un prototipo en C.
Sólo para modelos deterministas.[DFS-E,Z*-E]
No se optimizaron las estructuras de Datos.
ImplementaciónImplementación
35
Se introdujo el concepto de Carriles.
Se definió una técnica para localizar el Carril Máximo en modelos No Deterministas y Probabilistas.
Se definió una técnica para derivar CMTD`s con Contraejemplos a partir de PDM`s.
ConclusiónConclusión
Lo aportadoLo aportado:
36
Implementar una herramienta para la visualización de Carriles
Estudiar el aporte de Carriles para propiedades de alcanzabilidad acotadas inferiormente.
Extender la herramienta prototípica a una de uso real.
Estudiar el uso de algoritmos alternativos a Z* para la obtención del Carril Máximo
Trabajos FuturosTrabajos Futuros
37
Preguntas Preguntas (Fáciles (Fáciles ))