Grupo QUIVIR
http://www.lsi.us.es/~quivir
Dpto. de LENGUAJES Y SISTEMAS INFORMÁTICOS
Escuela Técnica Superior de Ingeniería Informática
Universidad de Sevilla (España)
CAEPIA 2005
Santiago de Compostela, 15 de noviembre de 2005
Grupo QUIVIR
Faculty Members
Miguel Toro, PhD
Rafael M. Gasca, PhD
Carmelo del Valle, PhD
Fernando de la Rosa
Rafael Ceballos
Mayte Gómez
Sergio Pozo
Pablo Neira
Collaborators
Pedro Abad
José M. Bravo, PhD
Luis González, PhD
Antonio Márquez
Antonio J. Suárez
Francisco Velasco, PhD
Student Members
Irene Barba
Diana Borrego
Víctor Cejudo
Programación con Restricciones – Aplicaciones
Índice
Diagnosis
Diagnosis
basada en
modelos
Diagnosis de
Software

Paradigma Programación con Restricciones –
Aplicaciones
 Diagnosis
Diagnosis
distribuida
Diagnosis basada en modelos
 Diagnosis distribuida
 Diagnosis de Software
 Seguridad informática como problema de
diagnosis

Seguridad
informática
Tolerancia a
fallos
Planificación
para la
recuperación
de fallos

Tolerancia a fallos

Planificación para la recuperación de fallos
Programación con Restricciones – Aplicaciones
Diagnosis
Diagnosis
Diagnosis
basada en
modelos
Diagnosis de
Software
Diagnosis
distribuida
Seguridad
informática
Tolerancia a
fallos
Planificación
para la
recuperación
de fallos
a
M1
x
b
c
d
e
M2
M3
A1
f
A2
g
y
z
Programación con Restricciones – Aplicaciones
Especificación de Problema de
Diagnosis
PD(MPS,MO)
Diagnosis
Diagnosis
basada en
modelos
Diagnosis de
Software
Diagnosis
distribuida
Seguridad
informática
Tolerancia a
fallos
Planificación
para la
recuperación
de fallos
MPS(P,Vobs,Vnobs)
Restricciones
Polinómicas
M1: x=a*c
M2: y=b*d
M3: z=c*e
A1: f=x+y
A2: g=y+z
Variables
Observables
Variables no
observables
a
b
c
d
e
f
g
x
y
z
MO{aobs=2,bobs,=2,cobs=3,dobs=3,eobs,=2, fobs=10,gobs =12}
Programación con Restricciones – Aplicaciones
Red de contextos
Diagnosis
M 1M 2M 3A 1A 2
Diagnosis
basada en
modelos
{b *d + c*e -g = 0 , a *c -c*e -f+ g = 0 }
Diagnosis de
Software
Diagnosis
distribuida
Seguridad
informática
Tolerancia a
fallos
Planificación
para la
recuperación
de fallos
M 1M 2M 3A 1
M 1M 2M 3A 2
{a *c-b *d -f= 0 } {b *d + c*e -g = 0 }
M 1M 2M 3
M 1M 2A 1
M 1M 3A 2
M 1M 2A 2
{ } {a *c-b *d -f= 0 } { }
M 1M 2
M 1M 3
{}
{}
{}
{}
M 1M 3A 1A 2
M 2M 3A 1A 2
{a *c-b *d -f= 0 } {a *c-c*e -f+ g = 0 }{b *d + c*e -g = 0 }
M 1M 3A 1 M 2M 3A 1
{}
M 2M 3 M 1A 1
{}
M 1M 2A 1A 2
M 2M 3A 2
M 1A 1A 2 M 2A 1A 2
{ } {b *d + c*e -g = 0 } { }
M 1A 2 M 2A 1
{}
{}
{}
M 2A 2
M 3A 1
M 3A 2
A 1A 2
{}
{}
{}
{}
M1
M2
M3
A1
A2
{}
{}
{}
{}
{}
M 3A 1A 2
{}
Programación con Restricciones – Aplicaciones
Red de contextos
Context Analytical Redundancy
Constraint (CARC)
Diagnosis
Diagnosis
basada en
modelos
1
a*c+b*d-f=0
Diagnosis de
Software
2
b*d+c*e-g=0
Diagnosis
distribuida
3
a*c-c*e-f+g=0
Seguridad
informática
M1M2M3A1A2
{2,3}
Tolerancia a
fallos
Planificación
para la
recuperación
de fallos
M1M2M3A1
{1}
M1M2A1
{1}
M1M2M3A2
{2}
M1M2A1A2
{1}
M1M3A1A2
{3}
M2M3A1A2
{2}
M2M3A2
{2}
Programación con Restricciones – Aplicaciones
Diagnosis de Software
Diagnosis
Diagnosis
basada en
modelos
Diagnosis
Diagnosis de
de
Software
Software
Diagnosis
distribuida
Seguridad
informática
Tolerancia a
fallos
Planificación
para la
recuperación
de fallos







Necesitamos: Código fuente, precondición y postcondición
Las sentencias serán transformadas a restricciones
polinómicas
Uso de técnicas de Testing
Subconjunto del lenguaje Java
Ejemplo:Cambiamos S5 con g=y-z
Caso de Test
Metodología:
 Normalización
 Obtención de las restricciones del contexto y simplificación de la
red de contextos
 Determinación de la diagnosis mínima
Programación con Restricciones – Aplicaciones
Sistema de intercambiadores
Diagnosis
31
Diagnosis
basada en
modelos
26
Diagnosis de
Software
Seguridad
informática
Planificación
para la
recuperación
de fallos
N 23
N 22
12
11
29
28
25
24
Diagnosis
distribuida
Tolerancia a
fallos
27
E3
14
E1
32
18
110
E5
N 12 1 6 E 4 1 7 N 13
N 11
E2
13
22
N 14
E6
19
15
112
111
2 1 0 N 24 2 1 1
N 21 2 3
33
21
212
Resultant system:
34 equations and 54 variables (28 observable)
Programación con Restricciones – Aplicaciones
Sistema de intercambiadores
Diagnosis
Diagnosis
basada en
modelos
Minimal Context Network
N 12N 21N 22E 1E 2
{9 ,1 1 ,1 3 }
E3 E4
{5 ,6 ,7 ,8 }
N 14N 23N 24E 5E 6
{1 0 ,1 2 ,1 4 }
Diagnosis de
Software
Diagnosis
distribuida
N 21N 22E 1E 2
{1 1 }
Seguridad
informática
Tolerancia a
fallos
Planificación
para la
recuperación
de fallos
N 12E 1E 2
{9 }
N 11
{1 ,2 }
E3
{5 }
E4
{6 }
N 13
{3 ,4 }
N 23N 24E 5E 6
{1 2 }
N 14E 5E 6
{1 0 }
Rules for the diagnosis (off-line):
If (9) is violated, there is a simple fault in N12, E1 or E2
…
(9 and 11) → E1 or E2 or (N12 and N21) or (N12 and N22)
(10 and 12) → E5 or E6 or (N14 and N23) or (N14 and N24)
Programación con Restricciones – Aplicaciones
Sistema de intercambiadores
Diagnosis
31
Diagnosis
basada en
modelos
26
Diagnosis de
Software
Seguridad
informática
Planificación
para la
recuperación
de fallos
N 23
N 22
12
11
29
28
25
24
Diagnosis
distribuida
Tolerancia a
fallos
27
E3
14
E1
32
18
110
E5
N 12 1 6 E 4 1 7 N 13
N 11
E2
13
22
N 14
E6
19
15
112
111
2 1 0 N 24 2 1 1
N 21 2 3
33
21
212
Resultant system:
34 equations and 54 variables (28 observable)
Programación con Restricciones – Aplicaciones
Diagnosis distribuida
Diagnosis
Diagnosis
basada en
modelos
Diagnosis de
Software


Resolución de Problemas CSP distribuidos
Agentes móviles con restricciones
Diagnosis
distribuida
Seguridad
informática
Tolerancia a
fallos
Envia/recibe
Envia/recibe
Planificación
para la
recuperación
de fallos
Envia/recibe
Programación con Restricciones – Aplicaciones
Bases de Datos con Restricciones
Diagnosis
Diagnosis
basada en
modelos
Diagnosis de
Software
Diagnosis
distribuida
Seguridad
informática
Tolerancia a
fallos
Planificación
para la
recuperación
de fallos
Programación con Restricciones – Aplicaciones
Seguridad informática
Diagnosis
Diagnosis
basada en
modelos

Diagnosis de
Software
Diagnosis
distribuida
Seguridad
Seguridad
informática
informática
Tolerancia a
fallos
Planificación
para la
recuperación
de fallos

Políticas de Seguridad
 Modelado basado en CSP
 Coherencia de políticas centralizadas
 Coherencia de políticas distribuidas
Mecanismos de Seguridad
 Modelado de sus propiedades basado en
CSP
 Detección y Diagnosis de incumplimiento de
políticas por los mecanismos
Programación con Restricciones – Aplicaciones
Tolerancia a fallos
Diagnosis
Diagnosis
basada en
modelos
Diagnosis de
Software
Diagnosis
distribuida
Seguridad
informática
Tolerancia a
fallos
Planificación
para la
recuperación
de fallos
Diagnosis
There is a simple fault
CSP Model
Extracting
the faulty part
Substituting/repairing
the faulty part
Re-assembly
the product
Planificación para
la recuperación de
fallos
Programación con Restricciones – Aplicaciones
Tolerancia a fallos
Diagnosis
Diagnosis
basada en
modelos
Diagnosis de
Software
Diagnosis
distribuida
Seguridad
informática
Tolerancia a
fallos
Planificación
para la
recuperación
de fallos

Seguridad Informática
 Sistemas Altamente Fiables (dependable
systems) Distribuidos
 Planificación para recuperación de fallos en
Sistemas Altamente Fiables Distribuidos.
Programación con Restricciones – Aplicaciones
Reparación de productos
Diagnosis
Diagnosis
basada en
modelos
Diagnosis de
Software
Diagnosis
distribuida
Seguridad
informática
1
2
3
Tolerancia a
fallos
Planificación
para la
recuperación
de fallos
4
5
6
Programación con Restricciones – Aplicaciones
Modelo de planificación
Diagnosis
ABCDE

Diagnosis
basada en
modelos
Diagnosis de
Software
ABCD

Diagnosis
distribuida
Seguridad
informática
Nodos Or - Submontajes
 Raíz - Montaje completo
 Hojas - Piezas individuales
Nodos And – Tareas de
montaje / desmontaje
ACD
Tolerancia a
fallos
Planificación A B
para la
recuperación
de fallos
A
AC
B
AD
C
CD
D
BE
E
Grafo And/Or para el producto ABCDE
Programación con Restricciones – Aplicaciones
Modelo de planificación
Diagnosis
Diagnosis
basada en
modelos

Sequencing assembly plans
Execution in multirobot systems
(optimizing total assembly time):
ABCDE
Diagnosis de
Software
M1 C2 T dur=15
2
Diagnosis
distribuida
Seguridad
informática
Tolerancia a
fallos
ACD
M2 C3
Planificación M1 C1
para la
recuperación
de fallos A
R1
R2
T5
dur=18
M2 C4
AC
T8
dur=20
B
T11 dur=10
C
T2
m ov
T5
BE
D
E
m ov
T8
cht
T11
time




Machines
Configuration (tools)
Durations of tasks
Changing configuration
 cht ( M , C , C  )
 Transportation of
intermediate sub-assemblies
 m ov ( SA , M , M  )
Programación con Restricciones – Aplicaciones
Modelo de planificación
Diagnosis
Diagnosis
basada en
modelos
The Planning Problem:
Tasks:

assembles sub-assemblies sub1 and sub2 and obtains subassembly result
Diagnosis de
Software
Diagnosis
distribuida
Seguridad
informática

disassemble(result,sub1,sub2):
disassembles result in 2 sub-assemblies, sub1 and sub2

move-subassembly(sub,mach1,mach2):
moves the sub-assembly sub from machine mach1 to machine
mach2
Tolerancia a
fallos
Planificación
para la
recuperación
de fallos
assemble(sub1,sub2,result):

change-configuration(mach,conf1,conf2):
changes the configuration of the machine mach from conf1 to
conf2

repair-part(p):
repairs or substitutes the part p
Programación con Restricciones – Aplicaciones
Modelo de planificación
Diagnosis
Diagnosis
basada en
modelos
Diagnosis de
Software
The Planning Problem:
Some definitions:

Diagnosis
distribuida
Seguridad
informática
Tolerancia a
fallos

Planificación
para la
recuperación
de fallos

A reparation graph is an And/Or graph which
only contains assembly and disassembly tasks
that handle subassemblies that contain the faulty
part
An assembly (disassembly) task T is reversible if
its corresponding disassembly (assembly) task T'
exists, i.e., if both tasks handle the same
subassemblies, but in an opposite way
A reversible plan is a tree of the reparation
graph that only contains reversible tasks
Programación con Restricciones – Aplicaciones
Modelo de planificación
ABCDE
...
(1)
Variables:
Diagnosis
M2
T1
C4
Diagnosis
basada en
modelos
M2
C3
M2
T2
C3
M2
C3
(2)
(3)
ABCD
Diagnosis de
Software
M2
Diagnosis
T3 M2
C4
C4
distribuida
(4)
M1
M1
C1 T4 C1
Seguridad
informática
ACD
Tolerancia a
fallos
Planificación
para la
recuperación
de fallos
AB
A
M2
T M2
C3 5 C3
B
SA tOR – assembled time
M1
M1
T
C2 6 C2
AC
C
m – machine
(T') c – configuration
dur – duration
st – start time
ft – finish time
s - selected
T
AD
CD
M1
M1
C2 T9 C1
M2
M2
T
C4 10 C4
D
BE
E
t'OR – disassembled “
m – assemb. mach.
m' – disassemb. mach.
s - selected
Programación con Restricciones – Aplicaciones
Modelo de planificación
ABCDE
...
(1)
Variables:
Diagnosis
M2
T1
C4
Diagnosis
basada en
modelos
M2
C3
M2
T2
C3
M2
C3
ABCD
Diagnosis de
Software
M2
Diagnosis
T3 M2
C4
C4
distribuida
M1
M1
C1 T4 C1
Seguridad
informática
m – machine
(3)
(T') c – configuration
(4)
dur – duration
st – start time
ft – finish time
  s (T 3 )   s (T 4 )  s - selected
(2)
T
s ( A B C D )   s (T3 ) X O RA Cs (DT 4 )    s ( A B C D ) 
sTolerancia
(T3 )   m
a ( A B C D )  M 2  t O R ( A B C D )  ft (T 3 )  st (T 3)  t O R ( A B C D )   m ov  A B C D , m  ( A B C D ), M 2  
fallos
s (T 4 )   m ( A B C D
M M
t O1 RT( AMB
C D )  ft (T 4 )  st (T 4)  t O R ( A B C D SA
)  tm ov  –
A Bassembled
C D , m ( A B C D ),
M 1 
M2)  M
1
time
T5 2 1
OR
6 C
C
C
C
2
2
3
3
Planificación
para la
recuperación
de fallos
AB
A
AC
B
C
AD
CD
M1
M1
C2 T9 C1
M2
M2
T
C4 10 C4
D
BE
E
t'OR – disassembled “
m – assemb. mach.
m' – disassemb. mach.
s - selected
Descargar

Concurso a Plaza