PDF de programación - Depuración Automática para Programas en Lenguaje C usando Algoritmos Genéticos

Centro de Investigación y de Estudios

Avanzados

del Instituto Politécnico Nacional

Unidad Zacatenco

Departamento de Computación

Depuración Automática para Programas en

Lenguaje C usando Algoritmos Genéticos.

Tesis que presenta

Pedro Eduardo Torres Jiménez

para obtener el Grado de

Maestro en Ciencias

en Computación

Director de la Tesis

Dr. Pedro Mejía Álvarez

México, D.F.

Diciembre, 2014

1

Dedicatoria

A mis padres María Luisa y Pedro Francisco por su amor y apoyo
incondicional.

A mis abuelos Cristina Gallardo y Marcelo Jiménez por su gran
amor y por todas las lecciones de vida que aprendí a su lado.

A Nicolás mi hijo por inspirarme a ser cada día una mejor per-
sona.

A todos mis compañeros de clase, por compartir gratas experien-
cias juntos.

Agradecimientos

Al CINVESTAV por brindarme la oportunidad de formar parte
de este gran centro de estudios.

Al Consejo de Ciencia y Tecnología CONACYT por el apoyo
económico brindado y el impulso científico en México.

Al Dr. Pedro Mejía Álvarez, por su conocimiento, entusiasmo
brindado y por aceptarme en su tema de tesis.

A todos los profesores del departamento de computación que
ayudaron en mi formación académica.

Resumen

Actualmente el proceso de desarrollo de software ha adquirido ma-
durez. Una de las características más importantes del software es sin
duda la confiabilidad. La experiencia indica que es fácil introducir
errores por parte de los desarrolladores de manera no intencional. Por
esta razón se han desarrollado distintas estrategias para localizar de-
fectos.

Nuestros servicios como energía, comunicaciones, transporte, etc. de-
penden de sistemas informáticos muy grandes. Por esta razón es im-
portante detectar y eliminar la mayor cantidad posible de errores.

Los trabajos actuales de detección de defectos se basan en análisis
estático, dinámico e inspecciones de software. Estos métodos son muy
útiles, no obstante requieren mucho tiempo y son actividades tediosas.

Cuando el Software manifiesta un defecto, éste se encuentra gene-
ralmente dentro de un conjunto de datos grande. La depuración en
este contexto es difícil y requiere mucho tiempo localizar la causa del
defecto.

Este trabajo aprovecha las ventajas de las pruebas automáticas para
automatizar el proceso de depuración. Se pretende ayudar al progra-
mador a simplificar código fuente y entradas de usuario de manera
automática. Como resultado se entrega un subconjunto útil que pre-
serve las características de un defecto y pueda ser corregido fácimente.

Se presenta una biblioteca de depuración automática de programas
escritos en lenguaje C que permite identificar, simplificar y aislar de-
fectos.

La biblioteca contiene los algoritmos clásicos de la literatura sobre
depuración automática. Específicamente las técnicas de depuración
delta, además se introduce un método de simplificación de casos de
prueba basado en perfilaje y optimización usando un algoritmo genéti-
co, el cual entrega buenos resultados sin repetir pruebas.

Palabras clave: Simplificación de casos de prueba, aislamiento
de defectos, depuración automática, depuración delta, algo-
ritmo genético.

Abstract

Currently the software development process has aquired maturity. One
of the most important features of the software is the reliability. Expe-
rience suggests that it isnt difficult to introduce errors by developers.
For this reason different strategies have been developed to simplify
and isolate failures.

Our services and infrastrucure like energy, communications, transpor-
tation, etc. Dependens of big computer systems. For this reason its
important detect and remove as many bugs as possible.

Recent works are based on static, dynamic analysis and Software ins-
pectios. These methods are useful but are expensive in terms of time
and practice.

Debugging process are very difficult when the failures are in large sets
of data. This is the most common scenario.

This work takes advantage of automated testing to automate the de-
bugging process. This work help the developer to simplify user input
and source code automatically. As a result we gain an useful subset
which preserves the minimum characteristics of a defect and allow
easily prevent failures.

A library of automatic debugging we present for programs written
in C language. Allowing identify, simplify and isolate the defects on
failure inducing inputs.

The library include the literature algorithms on automated debug-
ging such delta debugging algoritmhs and a novel method that uses

profiling technique and genetic algorithm in the input data to avoids
repeated tests.

Keywords: Simplification of test cases, failure isolation, au-
tomated debugging, delta debugging, genetic algorithm.

Índice general

Índice general

Índice de figuras

1.

Introducción

1.1. Antecedentes

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

1.2. Motivación . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1.3. Contribuciones

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

1.4. Organización de la Tesis . . . . . . . . . . . . . . . . . . . . . . .

2. Depuración de Software

VIII

XI

2

3

6

8

9

11

2.1. Proceso de Desarrollo de Software . . . . . . . . . . . . . . . . . .

11

2.2. Pruebas de Software

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

12

2.2.1. Análisis dinámico de Software . . . . . . . . . . . . . . . .

16

2.2.2. Clasificación . . . . . . . . . . . . . . . . . . . . . . . . . .

17

viii

ÍNDICE GENERAL

2.3. El Proceso de depuración . . . . . . . . . . . . . . . . . . . . . . .

23

2.4. Depuración automática . . . . . . . . . . . . . . . . . . . . . . . .

27

2.5. Trabajo relacionado . . . . . . . . . . . . . . . . . . . . . . . . . .

29

2.5.1. Trabajos basados en depuración delta y análisis de cobertura 29

2.5.2. Trabajos basados en depuración delta y model checking . .

29

2.5.3. Trabajos basados en depuración delta y slicing dinámico .

30

2.5.4. Trabajos basados en depuración delta, metaheurísticas y
pruebas de mutación . . . . . . . . . . . . . . . . . . . . .

32

2.5.5. Trabajos basados en depuración delta y análisis de impacto

32

2.6. Sumario . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

33

3. Depuración Delta

35

3.1. Simplificación y aislamiento de casos de prueba . . . . . . . . . .

36

3.2. Depuración delta . . . . . . . . . . . . . . . . . . . . . . . . . . .

37

3.2.1. Simplificación de Casos de Prueba . . . . . . . . . . . . . .

37

3.2.2. Ejemplo de Simplificación de un Caso de Prueba . . . . . .

42

3.2.3. Algoritmo de Simplificación . . . . . . . . . . . . . . . . .

47

3.3. Aislamiento de Entradas . . . . . . . . . . . . . . . . . . . . . . .

53

3.4. Depuración Delta Jerárquica . . . . . . . . . . . . . . . . . . . . .

57

3.4.1. Algoritmo HDD . . . . . . . . . . . . . . . . . . . . . . . .

59

ix

ÍNDICE GENERAL

3.5. Sumario . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

61

4. Depuración automática usando algoritmos genéticos.

64

4.1. Algoritmos genéticos . . . . . . . . . . . . . . . . . . . . . . . . .

64

4.2. Depuración automática usando algoritmos genéticos

. . . . . . .

66

4.3. Simplificación de Casos de Prueba . . . . . . . . . . . . . . . . . .

67

4.4. Aislamiento de defectos de casos de prueba . . . . . . . . . . . . .

70

4.5. Sumario . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

71

5. Experimentos

73

5.1. Diseño de experimentos . . . . . . . . . . . . . . . . . . . . . . . .

73

5.2. Resultados . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

74

5.3. Análisis y comparaciones . . . . . . . . . . . . . . . . . . . . . . .

77

5.4. Discusión . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

88

6. Conclusiones

91

6.1. Trabajo a futuro . . . . . . . . . . . . . . . . . . . . . . . . . . .

92

Referencias

93

x

Índice de figuras

1.1. Etapa de pruebas en el proceso de desarrollo de Software . . . . .

4

2.1. Proceso de desarrollo de Software . . . . . . . . . . . . . . . . . .

12

2.2. Caso de prueba . . . . . . . . . . . . . . . . . . . . . . . . . . . .

14

2.3. Oráculo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

15

2.4. Clasificación de pruebas

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

18

2.5. Pasos de la depuración . . . . . . . . . . . . . . . . . . . . . . . .

24

2.6. Algoritmo de la depuración . . . . . . . . . . . . . . . . . . . . .

26

3.1. ddmin . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

36

3.2. Espacio de estados

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

40

3.3. Particiones ordenadas . . . . . . . . . . . . . . . . . . . . . . . . .

53

3.4. Ast . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

57

4.1. Evaluación . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

68

xi

ÍNDICE DE FIGURAS

4.2. Selección . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

68

4.3. Cruza . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

69

4.4. Mutación . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

69

5.1. ddmin . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

75

5.2. Histograma de la figura 5.4 . . . . . . . . . . . . . . . . . . . . . .

79

5.3. Histograma de la figura 5.6 . . . . . . . . . . . . . . . . . . . . . .

81

5.4. Histograma de la figura 5.8 . . . . . . . . . . . . . . . . . . . . . .

83

5.5. Histograma de la figura 5.10 . . . . . . . . . . . . . . . . . . . . .

85

5.6. Histograma de la figura 5.12 . . . . . . . . . . . . . . . . . . . . .

86

5.7. Histograma de la figura 5.14 . . . . . . . . . . . . . . . . . . . . .

87

xii

Introducción

El Software es complejo, la mayoría de las veces no está libre de defectos y gran
parte del tiempo que se tiene disponible para su creaci