PDF de programación - Técnicas automáticas para la diagnosis de errores en software diseñado por contrato

Técnicas automáticas para la diagnosis de
errores en software diseñado por contrato

Rafael Ceballos Guerrero,

[email protected]

Supervised by Prof. Dr. Rafael Martínez Gasca y Carmelo del Valle Sevillano

Research Report submitted to the Department of Computer Languages

and Systems of the University of Sevilla in partial fulfilment

of the requirements for the degree of Ph.D. in Computer Engineering.

(“Research Period”)

If debugging is the process of removing
bugs, then programming must be the
process of putting them in...
Edsger Dijkstra.

Índice general

1. Introducción
1.1. Objetivos
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.2. Presentación . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.3. Estructura del documento . . . . . . . . . . . . . . . . . . . . . . . . .
1.4. Publicaciones originales . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.5. Proyectos de investigación . . . . . . . . . . . . . . . . . . . . . . . . .

2. Estado del arte

2.1. Diagnosis de componentes . . . . . . . . . . . . . . . . . . . . . . . . .
2.1.1. Ejemplo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.1.2. Metodología DX . . . . . . . . . . . . . . . . . . . . . . . . . .
2.1.3. Metodología FDI
. . . . . . . . . . . . . . . . . . . . . . . . . .
2.2. Problema de satisfacción de restricciones . . . . . . . . . . . . . . . . .
2.2.1. Conceptos básicos del modelado CSP . . . . . . . . . . . . . . .
2.2.2. Consistencia . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.2.3. Algoritmos de búsqueda . . . . . . . . . . . . . . . . . . . . . .
2.2.4. Problemas de optimización con restricciones . . . . . . . . . . .
2.3. Generación de pruebas . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . . . . . . .
2.4. Diseño por contrato . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . . . . . . . .
2.5. Trabajos previos de depuración y verificación de código . . . . . . . . .

2.3.1. Conceptos básicos de generación de pruebas
2.3.2. Técnicas de generación de pruebas

2.4.1. Elementos básicos en el diseño de contratos
2.4.2. Diagnosticabilidad en el software

3. Diagnosis basada en modelos CSP

3.1. Ejemplo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.2. Modelado a través de un CSP . . . . . . . . . . . . . . . . . . . . . . .
3.3. Diagnosis con variables de dominios intervalares . . . . . . . . . . . . .
3.4. Conclusiones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.5. Publicaciones relacionadas . . . . . . . . . . . . . . . . . . . . . . . . .

i

1
1
1
3
4
8

9
9
11
11
13
16
17
18
18
19
20
20
21
22
23
25
25

27
28
28
31
34
34

ÍNDICE GENERAL

4. Diagnosis basada en técnicas de precompilación

4.1.
Introducción . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.2. Ejemplos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.3. Pretratamiento estructural . . . . . . . . . . . . . . . . . . . . . . . . .
4.3.1.
Identificación de los clusters . . . . . . . . . . . . . . . . . . . .
4.3.2. Obtención de relaciones sin variables no observables . . . . . . .
4.3.3. Obtención de los nodos de cada cluster . . . . . . . . . . . . . .
4.4. Determinación de la red de contextos . . . . . . . . . . . . . . . . . . .
4.5. Determinación de la diagnosis mínima
. . . . . . . . . . . . . . . . . .
4.6. Conclusiones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.7. Publicaciones relacionadas . . . . . . . . . . . . . . . . . . . . . . . . .

5. Diagnosis del Software

5.1.
Introducción . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.2. Definiciones y fases de la metodología . . . . . . . . . . . . . . . . . . .
5.3. Generación del modelo abstracto
. . . . . . . . . . . . . . . . . . . . .
5.3.1. Determinación de los bloques básicos . . . . . . . . . . . . . . .
5.3.2. Forma SSA . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.3.3. Transformación del programa . . . . . . . . . . . . . . . . . . .
5.3.4. Casos de test
. . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . .
5.5.1. Diagnosis de los asertos sin usar casos de test
. . . . . . . . . .
5.5.2. Diagnosis de los asertos usando casos de test . . . . . . . . . . .
5.5.3. Diagnosis del código fuente . . . . . . . . . . . . . . . . . . . . .
5.5.4. Diagnosis del código fuente usando varios casos de test
. . . . .
5.6. Conclusiones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.7. Publicaciones relacionadas . . . . . . . . . . . . . . . . . . . . . . . . .

5.4. Problema de diagnosis
5.5. Diagnosis de programas

6. Conclusiones y trabajos futuros

. Bibliografía

37
37
39
40
40
42
43
46
48
51
52

55
55
56
58
58
60
61
67
68
69
70
71
71
73
74
74

77

79

ii

Índice de figuras

1.1. Sistema físico y programa equivalente . . . . . . . . . . . . . . . . . . .

2.1. Sistema polybox básico (Toy Problem) . . . . . . . . . . . . . . . . . .
2.2. Modelo CSP para el coloreado de un mapa . . . . . . . . . . . . . . . .

3.1. Sistema de los intercambiadores de calor

. . . . . . . . . . . . . . . . .

4.1. Sistema polybox extendido . . . . . . . . . . . . . . . . . . . . . . . . .
4.2. ALU 74181 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.3. Algoritmo para obtener los clusters de un sistema . . . . . . . . . . . .
4.4. Diagnosis posibles para los cinco clusters del sistema de intercambiadores
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.5. Algoritmo para la detección de los nodos de un cluster
. . . . . . . . .
4.6. Descomposición en nodos del sistema polybox extendido . . . . . . . .
4.7. Red de contextos del sistema polybox extendido . . . . . . . . . . . . .

de calor

5.1. Fases de la diagnosis del software . . . . . . . . . . . . . . . . . . . . .
5.2. Transformación de bucle a sentencias selectivas . . . . . . . . . . . . . .
5.3. Código fuente de la interfaz Account y clase AccountImp . . . . . . . .

2

10
17

28

38
39
40

42
44
45
48

57
65
70

iii

Índice de Tablas

2.1. Modelo DX para el ejemplo de la figura 2.1 . . . . . . . . . . . . . . . .
2.2. Modelo FDI para el ejemplo de la figura 2.1 . . . . . . . . . . . . . . .
2.3. Matriz de firmas del sistema polybox para fallos simples
. . . . . . . .
. . . . . . .
2.4. Matriz de firmas del sistema polybox para fallos múltiples

12
14
15
16

3.1. Ecuaciones del modelo del sistema de intercambiadores de calor
29
3.2. Modelos para el sistema polybox usando las técnicas DX, CSP y Max-CSP 30
32
3.3. CSDP para el sistema polybox . . . . . . . . . . . . . . . . . . . . . . .
3.4. CSDP para los componentes N12, N21, N22, E1 y E2
. . . . . . . . . . .
33

. . . .

4.1. Clusters del sistema de intercambiadores de calor
. . . . . . . . . . . .
4.2. Nodos para el sistema polybox extendido . . . . . . . . . . . . . . . . .
4.3. Mejoras obtenidas realizando el pretratamiento estructural
. . . . . . .
4.4. CARCs obtenidas del sistema polybox extendido . . . . . . . . . . . . .
4.5. Matriz de firmas del sistema polybox extendido . . . . . . . . . . . . .
4.6. Resumen de las reglas generadas para el sistema polybox extendido . .

5.1. Modelo abstracto del Toy Program . . . . . . . . . . . . . . . . . . . .
5.2. Ejemplo de código con sentencias condicionales
. . . . . . . . . . . . .
5.3. Modelo abstracto del ejemplo de la tabla 5.2 . . . . . . . . . . . . . . .
5.4. Modelo del Toy Program modificado . . . . . . . . . . . . . . . . . . .
5.5. Diagnosis del método Withdraw usando un caso de test . . . . . . . . .
5.6. Comprobación de la clase AccountImp usando casos de test . . . . . . .

41
46
47
47
49
51

63
64
66
69
71
73

iv

A mi familia, por confiar siempre en mí, y estar conmigo cuando más lo he necesitado.

1

.

ÍNDICE DE TABLAS

2

Capítulo 1

Introducción

1.1. Objetivos

En las últimas décadas, parte de la comunidad científica ha dedicado sus esfuerzos
al desarrollo de una metodología para la diagnosis de sistemas. Dicha metodología se
denomina diagnosis basada en modelos, y cubre un amplio espectro de sistemas. Se
parte de un modelo explícito del sistema a diagnosticar, y a partir de él se identifican
los subsistemas que provocan los fallos. Para ello se utilizan los valores monitorizados
de las entradas y salidas del sistema. En cualquier proceso de producción o desarrollo
es importante tener un control sobre los fallos en componentes o procesos. La diagnosis
permite controlar estas irregularidades, lo que conlleva a los sistemas que la incorporan
una mayor seguridad y reducción de costos.

El objetivo de este trabajo es generar una metodología que permita realizar la diag-
nosis de una aplicación software. Durante los últimos años la investigación en técnicas
para probar y depurar software de forma automática ha aumentado sustancialmente.
Las pruebas y depuración del software, representan ya el 30 % de los recursos de un
desarrollo de aplicaciones. Por tanto, es uno de los procesos más caros en el desarrollo
y mantenimiento del software. Un estudio reciente del NIST [64], estima que el coste de
fallos del software es de 59.5 billones de dólares sólo en EEUU. Las técnicas para probar
software (testing) permiten detectar si existe o no un error en una aplicación, pero no
garantizan si un programa es correcto al cien por cien, ni permiten encontrar qué parte
del código es el origen de los errores encontrados. La diagnosis del software va más alla,
y permite además identificar y localizar el origen de los errores de una aplicación.

1.2. Presentación

Pero, ¿qué tipos de errores se diagnostican?. La metodología propuesta en este
trabajo detecta errores debidos a la no concordancia entre los resulta