1 CAEPIA 2005 Santiago de Compostela, 15 de noviembre de 2005 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)

2 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

3 Programación con Restricciones – Aplicaciones Diagnosis Diagnosis basada en modelos Diagnosis de Software Diagnosis distribuida Seguridad informática Tolerancia a fallos Planificación para la recuperación de fallos Índice n Paradigma Programación con Restricciones – Aplicaciones  Diagnosis  Diagnosis basada en modelos  Diagnosis distribuida  Diagnosis de Software  Seguridad informática como problema de diagnosis  Tolerancia a fallos  Planificación para la recuperación de fallos

4 Programación con Restricciones – Aplicaciones 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 M1M1 M2M2 M3M3 A1A1 A2A2 f g x y z a b c d e Diagnosis basada en modelos Diagnosis

5 Programación con Restricciones – Aplicaciones Diagnosis Diagnosis basada en modelos Diagnosis de Software Diagnosis distribuida Seguridad informática Tolerancia a fallos Planificación para la recuperación de fallos Especificación de Problema de Diagnosis PD(MPS,MO) MPS(P,V obs,V nobs ) Restricciones Polinómicas Variables Observables Variables no observables M1: x=a*c M2: y=b*d M3: z=c*e A1: f=x+y A2: g=y+z abcdefgabcdefg xyzxyz MO  {a obs =2,b obs,=2,c obs =3,d obs =3,e obs, =2, f obs =10,g obs =12} Diagnosis basada en modelos Diagnosis

6 Programación con Restricciones – Aplicaciones Diagnosis Diagnosis basada en modelos Diagnosis de Software Diagnosis distribuida Seguridad informática Tolerancia a fallos Planificación para la recuperación de fallos Red de contextos Diagnosis basada en modelos Diagnosis

7 Programación con Restricciones – Aplicaciones Diagnosis Diagnosis basada en modelos Diagnosis de Software Diagnosis distribuida Seguridad informática Tolerancia a fallos Planificación para la recuperación de fallos Red de contextos Context Analytical Redundancy Constraint (CARC) 1a*c+b*d-f=0 2b*d+c*e-g=0 3a*c-c*e-f+g=0 M 1 M 2 M 3 A 1 M 1 M 2 M 3 A 2 M 1 M 2 A 1 A 2 M 1 M 3 A 1 A 2 M 2 M 3 A 1 A 2 {1} {2} {1} {3} {2} M 1 M 2 A 1 M 2 M 3 A 2 {1} {2} M 1 M 2 M 3 A 1 A 2 {2,3} Diagnosis basada en modelos Diagnosis

8 Programación con Restricciones – Aplicaciones 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 de Software n Necesitamos: Código fuente, precondición y postcondición n Las sentencias serán transformadas a restricciones polinómicas n Uso de técnicas de Testing n Subconjunto del lenguaje Java n Ejemplo:Cambiamos S5 con g=y-z n Caso de Test n 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 Diagnosis de Software Diagnosis

9 Programación con Restricciones – Aplicaciones Diagnosis Diagnosis basada en modelos Diagnosis de Software Diagnosis distribuida Seguridad informática Tolerancia a fallos Planificación para la recuperación de fallos Sistema de intercambiadores Resultant system: 34 equations and 54 variables (28 observable) Diagnosis

10 Programación con Restricciones – Aplicaciones Diagnosis Diagnosis basada en modelos Diagnosis de Software Diagnosis distribuida Seguridad informática Tolerancia a fallos Planificación para la recuperación de fallos Sistema de intercambiadores Minimal Context Network Rules for the diagnosis (off-line):  If (9) is violated, there is a simple fault in N 12, E 1 or E 2  …  (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) Diagnosis

11 Programación con Restricciones – Aplicaciones Diagnosis Diagnosis basada en modelos Diagnosis de Software Diagnosis distribuida Seguridad informática Tolerancia a fallos Planificación para la recuperación de fallos Sistema de intercambiadores Resultant system: 34 equations and 54 variables (28 observable) Diagnosis distribuida Diagnosis

12 Programación con Restricciones – Aplicaciones 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 distribuida n Resolución de Problemas CSP distribuidos n Agentes móviles con restricciones Envia/recibe Diagnosis distribuida Diagnosis

13 Programación con Restricciones – Aplicaciones Diagnosis Diagnosis basada en modelos Diagnosis de Software Diagnosis distribuida Seguridad informática Tolerancia a fallos Planificación para la recuperación de fallos Bases de Datos con Restricciones Diagnosis

14 Programación con Restricciones – Aplicaciones 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 n Políticas de Seguridad  Modelado basado en CSP  Coherencia de políticas centralizadas  Coherencia de políticas distribuidas n Mecanismos de Seguridad  Modelado de sus propiedades basado en CSP  Detección y Diagnosis de incumplimiento de políticas por los mecanismos Seguridad informática Diagnosis

15 Programación con Restricciones – Aplicaciones Diagnosis Diagnosis basada en modelos Diagnosis de Software Diagnosis distribuida Seguridad informática Tolerancia a fallos Planificación para la recuperación de fallos Tolerancia a fallos CSP Model Re-assembly the product Substituting/repairing the faulty part Extracting the faulty part Diagnosis There is a simple fault Planificación para la recuperación de fallos Tolerancia a fallos Planificación para la recuperación de fallos

16 Programación con Restricciones – Aplicaciones Diagnosis Diagnosis basada en modelos Diagnosis de Software Diagnosis distribuida Seguridad informática Tolerancia a fallos Planificación para la recuperación de fallos Tolerancia a fallos n Seguridad Informática  Sistemas Altamente Fiables (dependable systems) Distribuidos  Planificación para recuperación de fallos en Sistemas Altamente Fiables Distribuidos. Tolerancia a fallos Planificación para la recuperación de fallos

17 Programación con Restricciones – Aplicaciones Diagnosis Diagnosis basada en modelos Diagnosis de Software Diagnosis distribuida Seguridad informática Tolerancia a fallos Planificación para la recuperación de fallos Reparación de productos       Tolerancia a fallos Planificación para la recuperación de fallos

18 Programación con Restricciones – Aplicaciones Diagnosis Diagnosis basada en modelos Diagnosis de Software Diagnosis distribuida 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 Modelo de planificación n Nodos Or - Submontajes  Raíz - Montaje completo  Hojas - Piezas individuales n Nodos And – Tareas de montaje / desmontaje Grafo And/Or para el producto ABCDE A B C D E A B C D A C D A BA CA DC DB E ABCDE A B C D E A B C D A C D A BA CA DC DB E ABCDE A B C D E A B C D A C D A BA CA DC DB E ABCDE

19 Programación con Restricciones – Aplicaciones Diagnosis Diagnosis basada en modelos Diagnosis de Software Diagnosis distribuida 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 Modelo de planificación dur=15 dur=18 dur=20 dur=10 C2C2 C3C3 C1C1 C4C4 M1M1 M2M2 M1M1 M2M2  Transportation of intermediate sub-assemblies  Changing configuration  Configuration (tools)  Durations of tasks  Execution in multirobot systems (optimizing total assembly time): n Sequencing assembly plans A B C D E A C D A CB E ABCDE T2T2 T5T5 T8T8 T 11 M1M1 M2M2 M1M1 M2M2 C2C2 C3C3 C1C1 C4C4 dur=15 dur=18 dur=20 dur=10  Machines R1R1 R2R2 time T2T2 T5T5 T 11 T8T8

20 Programación con Restricciones – Aplicaciones Diagnosis Diagnosis basada en modelos Diagnosis de Software Diagnosis distribuida Seguridad informática Tolerancia a fallos Planificación para la recuperación de fallos Modelo de planificación The Planning Problem: Tasks:  assemble(sub1,sub2,result): assembles sub-assemblies sub1 and sub2 and obtains sub- assembly result  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  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 Tolerancia a fallos Planificación para la recuperación de fallos

21 Programación con Restricciones – Aplicaciones Diagnosis Diagnosis basada en modelos Diagnosis de Software Diagnosis distribuida Seguridad informática Tolerancia a fallos Planificación para la recuperación de fallos Modelo de planificación The Planning Problem: Some definitions:  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 Tolerancia a fallos Planificación para la recuperación de fallos

22 Programación con Restricciones – Aplicaciones Diagnosis Diagnosis basada en modelos Diagnosis de Software Diagnosis distribuida 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 Modelo de planificación (1) (2) (3) (4)... Variables: m – machine c – configuration dur – duration st – start time ft – finish time s - selected t OR – assembled time t' OR – disassembled “ m – assemb. mach. m' – disassemb. mach. s - selected T SA (T') A B C D E A B C D A C D A BA CA DC DB E ABCDE T1T1 T2T2 T3T3 T4T4 T5T5 T6T6 T9T9 T 10 M2C3M2C3 M2C4M2C4 M2C4M2C4 M1C1M1C1 M2C3M2C3 M1C2M1C2 M1C2M1C2 M2C4M2C4 M2C3M2C3 M2C3M2C3 M2C4M2C4 M1C1M1C1 M2C3M2C3 M1C2M1C2 M1C1M1C1 M2C4M2C4

23 Programación con Restricciones – Aplicaciones Diagnosis Diagnosis basada en modelos Diagnosis de Software Diagnosis distribuida 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 Modelo de planificación (1) (2) (3) (4)... Variables: m – machine c – configuration dur – duration st – start time ft – finish time s - selected t OR – assembled time t' OR – disassembled “ m – assemb. mach. m' – disassemb. mach. s - selected T SA (T') A B C D E A B C D A C D A BA CA DC DB E ABCDE T1T1 T2T2 T3T3 T4T4 T5T5 T6T6 T9T9 T 10 M2C3M2C3 M2C4M2C4 M2C4M2C4 M1C1M1C1 M2C3M2C3 M1C2M1C2 M1C2M1C2 M2C4M2C4 M2C3M2C3 M2C3M2C3 M2C4M2C4 M1C1M1C1 M2C3M2C3 M1C2M1C2 M1C1M1C1 M2C4M2C4