Cet ouvrage fait partie de la bibliothèque YouScribe
Obtenez un accès à la bibliothèque pour le lire en ligne
En savoir plus

Diseño automático de funciones hash no criptográficas

De
308 pages

Las funciones hash no criptográficas son una de las herramientas más ampliamente utilizadas en las ciencias de la computación. Sus innumerables campos de aplicación van desde analizadores léxicos y compiladores, hasta bases de datos, cachés, redes de comunicaciones, bloom filters, algoritmos de reconocimiento de patrones, juegos de ordenador, servidores DNS, sistemas de archivos, y prácticamente cualquier trozo de código en el que sea necesario consultar o indexar información a gran velocidad. Su tremenda utilidad se debe a que pueden llevar a cabo búsquedas en tiempo constante, independientemente del tamaño del conjunto en el que se busca. Sin embargo, el diseño de estas expresiones matemáticas sigue siendo, a día de hoy, una tarea poco conocida por los ingenieros de software, escasamente documentada, y tradicionalmente llevada a cabo por expertos en procesos prácticamente artesanales. La principal razón es que una buena función hash debe generar salidas pseudoaleatorias, aparentemente impredecibles, y por tanto su diseño involucra estructuras altamente no lineales y sistemas caóticos. Este tipo de diseño, por definición, es muy poco intuitivo y plantea dificultades importantes, incluso para expertos en hashing. Pero por otro lado, estas mismas características que resultan tan exigentes para los humanos, parecen muy apropiadas para que técnicas de inteligencia artificial como la Programaci on Gen etica (PG) automaticen el trabajo, sustituyendo a los expertos en la producción de buenas funciones hash. En esta tesis se presenta GP-hash, un sistema basado en PG capaz de generar de forma automática funciones hash no criptográficas de alta calidad. En este documento se demostrará empíricamente que GP-hash puede generar funciones hash de propósito general con un rendimiento igual o superior al de las má utilizadas por la industria, todas ellas creadas por algunos de los mayores expertos en hasing del mundo, y que forman el estado del arte actual. Este resultado por si sólo ya es importante, puesto que permite sostener que la PG es capaz de igualar (y en ocasiones superar) a los humanos en una tarea que claramente requiere cierto nivel de inteligencia. Adem as, GP-hash también puede utilizarse para generar funciones hash a medida, específicamente diseñadas para ofrecer un rendimiento óptimo en un problema en concreto. Se justificará que, si se entrena al sistema GP-hash bajo ciertas condiciones, un porcentaje muy alto de las funciones generadas superan fácilmente en el problema en cuestión a las funciones de propósito general más utilizadas. Esto permitiría a los ingenieros de software -con o sin conocimientos específicos sobre hashing- evitar una de las decisiones más comprometidas y que más problemas de rendimiento generan en este tipo de sistemas: la elección de una función hash adecuada a su caso particular. En lugar de eso, podránn utilizar GP-hash para obtener una función específicamente diseñada para su problema, que muy probablemente desarrollará un rendimiento excelente en el mismo. Las aplicaciones prácticas de un sistema así son enormes e inmediatas, y podrán llegar a tener un importante impacto en la industria del software. Por último, durante el desarrollo de esta investigaíón se observó que no existía un método estandarizado y universalmente aceptado para comparar funciones hash no criptogáficas entre sí, lo cual suponía un problema de base para los objetivos de esta tesis: no se puede afirmar que una función hash es competitiva si no hay una manera objetiva de compararla con otras funciones. La última aportación de este trabajo es la de llenar este vacío estructural: se recopilarán y analizarán las métricas de hashing más utilizadas en la literatura, y se propondrá a la comunidad científica un marco de referencia sistemático y estructurado para estandarizar la evaluación de funciones hash no criptográficas.
Voir plus Voir moins

Universidad Carlos III de Madrid
~ Diseno automatico de
funciones hash no
criptograficas
Tesis Doctoral
Autor: Cesar Estebanez Tascon
~Directores: Dr. D. Pedro Isasi Vinuela
Dr. D. Yago Saez Achaerandio
2011Resumen
Las funciones hash no criptogr a cas son una de las herramientas m as
ampliamente utilizadas en las ciencias de la computaci on. Sus innumerables
campos de aplicaci on van desde analizadores lexicos y compiladores, hasta
bases de datos, caches, redes de comunicaciones, bloom lters, algoritmos de
reconocimiento de patrones, juegos de ordenador, servidores DNS, sistemas
de archivos, y pr acticamente cualquier trozo de odigoc en el que sea necesario
consultar o indexar informaci on a gran velocidad. Su tremenda utilidad se
debe a que pueden llevar a cabo busquedas en tiempo constante, indepen-
dientemente del tamano~ del conjunto en el que se busca.
Sin embargo, el diseno~ de estas expresiones matem aticas sigue siendo, a
d a de hoy, una tarea poco conocida por los ingenieros de software, esca-
samente documentada, y tradicionalmente llevada a cabo por expertos en
procesos pr acticamente artesanales. La principal raz on es que una buena
funci on hash debe generar salidas pseudoaleatorias, aparentemente impre-
decibles, y por tanto su diseno~ involucra estructuras altamente no lineales y
sistemas ca oticos. Este tipo de diseno,~ por de nici on, es muy poco intuitivo y
plantea di cultades importantes, incluso para expertos en hashing. Pero por
otro lado, estas mismas caracter sticas que resultan tan exigentes para los
humanos, parecen muy apropiadas para que tecnicas de inteligencia arti cial
como la Programaci on Genetica (PG) automaticen el trabajo, sustituyendo
a los expertos en la producci on de buenas funciones hash.
En esta tesis se presenta GP-hash, un sistema basado en PG capaz de
generar de forma autom atica funciones hash no criptogr a cas de alta calidad.
En este documento se demostrar a emp ricamente que GP-hash puede generar
funciones hash de prop osito general con un rendimiento igual o superior al
de las m as utilizadas por la industria, todas ellas creadas por algunos de los
mayores expertos en hasing del mundo, y que forman el estado del arte actual.
Este resultado por si solo ya es importante, puesto que permite sostener que
la PG es capaz de igualar (y en ocasiones superar) a los humanos en una
tarea que claramente requiere cierto nivel de inteligencia.
Adem as, GP-hash tambien puede utilizarse para generar funciones hash
a medida, espec camente disen~adas para ofrecer un rendimiento optimo en
un problema en concreto. Se justi car a que, si se entrena al sistema GP-hash
bajo ciertas condiciones, un porcentaje muy alto de las funciones generadas
superan acilmenf te en el problema en cuesti on a las funciones de prop osito
general m as utilizadas. Esto permitir a a los ingenieros de software |con o
sin conocimientos espec cos sobre hashing| evitar una de las decisiones m as
Icomprometidas y que m as problemas de rendimiento generan en este tipo de
sistemas: la elecci on de una funci on hash adecuada a su caso particular. En
lugar de eso, podr an utilizar GP-hash para obtener una funci on espec ca-
mente disenada~ para su problema, que muy probablemente desarrollar a un
rendimiento excelente en el mismo. Las aplicaciones pr acticas de un sistema
as son enormes e inmediatas, y podr an llegar a tener un importante impacto
en la industria del software.
Por ultim o, durante el desarrollo de esta investigaci on se observ o que no
exist a un metodo estandarizado y universalmente aceptado para comparar
funciones hash no criptogr a cas entre si, lo cual supon a un problema de
base para los objetivos de esta tesis: no se puede a rmar que una funci on
hash es competitiva si no hay una manera objetiva de compararla con otras
funciones. La ultima aportaci on de este trabajo es la de llenar este vac o
estructural: se recopilar an y analizar an las metricas de hashing m as utili-
zadas en la literatura, y se propondr a a la comunidad cient ca un marco
de referencia sistem atico y estructurado para estandarizar la evaluaci on de
funciones hash no criptogr a cas.
IIIndice general
1. Introducci on 1
1.1. Motivaci on . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2. Objetivos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.2.1. Generaci on de funciones hash de prop osito general . . . 6
1.2.2.on de hash a medida . . . . . . . . . 7
1.2.3. El problema de la evaluaci on . . . . . . . . . . . . . . . 8
1.3. Contribuciones . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.4. Organizaci on de la tesis . . . . . . . . . . . . . . . . . . . . . 11
1.5. Material experimental adicional . . . . . . . . . . . . . . . . . 14
2. Programaci on Genetica (PG) 15
2.1. Representaconi de genotipos . . . . . . . . . . . . . . . . . . . 16
2.2. Proceso de evoluci on de individuos . . . . . . . . . . . . . . . 17
2.3. Especi caciones propias del dominio . . . . . . . . . . . . . . . 21
2.3.1. Conjunto de Funciones y Terminales . . . . . . . . . . 21
2.3.2. Funci on de evaluaci on o funci on de tness . . . . . . . 23
2.4. Par ametros . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
2.5. Bases Toricase de la PG . . . . . . . . . . . . . . . . . . . . . 24
2.5.1. Modelos matem aticos . . . . . . . . . . . . . . . . . . . 25
2.5.2. Teor as de bloat . . . . . . . . . . . . . . . . . . . . . . 25
2.5.3. Fitness Landscapes . . . . . . . . . . . . . . . . . . . . 26
2.6. Aplicaciones pr acticas de la PG . . . . . . . . . . . . . . . . . 32
2.7. Resumen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
3. Funciones Hash No Criptogra cas (FHNC) 35
3.1. Introducci on y de niciones . . . . . . . . . . . . . . . . . . . . 36
3.2. Estructura interna de las funciones hash . . . . . . . . . . . . 38
3.3. La funci on de mezcla . . . . . . . . . . . . . . . . . . . . . . . 41
3.4. Esquemas de compresi on . . . . . . . . . . . . . . . . . . . . . 43
3.5. Propiedades y medidas de calidad . . . . . . . . . . . . . . . . 45
3.6. Tablas hash . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
III3.6.1. De nici on . . . . . . . . . . . . . . . . . . . . . . . . . 48
3.6.2. Tamano~ de la tabla y factor de carga . . . . . . . . . . 49
3.6.3. Suposici on de hashing uniforme simple . . . . . . . . . 51
3.6.4. Estrategias de resoluci on de colisiones . . . . . . . . . . 51
3.7. Otras aplicaciones de las funciones hash no criptogr a cas . . . 62
3.8. Universal Hashing . . . . . . . . . . . . . . . . . . . . . . . . . 66
3.9. FHNC m as utilizadas . . . . . . . . . . . . . . . . . . . . . . . 67
3.10. Resumen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73
4. Evaluaci on de FHNC 75
4.1. Un marco para la comparaci on de FHNC . . . . . . . . . . . . 77
4.1.1. Trabajos previos . . . . . . . . . . . . . . . . . . . . . 78
4.1.2. Revisi on de la literatura . . . . . . . . . . . . . . . . . 79
4.1.3. Velocidad . . . . . . . . . . . . . . . . . . . . . . . . . 81
4.1.4. Colisiones . . . . . . . . . . . . . . . . . . . . . . . . . 84
4.1.5. Distribuci on de las salidas . . . . . . . . . . . . . . . . 88
4.1.6. Efecto avalancha . . . . . . . . . . . . . . . . . . . . . 90
4.1.7. Funneling . . . . . . . . . . . . . . . . . . . . . . . . . 94
4.1.8. Bit Independence Criterion . . . . . . . . . . . . . . . 95
4.2. HashBench: un banco de pruebas libre para FHNC . . . . . . 96
4.2.1. Estructura de HashBench . . . . . . . . . . . . . . . . 97
4.2.2. Esquemas de compresi on . . . . . . . . . . . . . . . . . 98
4.2.3. Tests proporcionados por HashBench . . . . . . . . . . 99
4.2.4. FHNC proporcionadas porh . . . . . . . . . 101
4.2.5. Bases de datos proporcionadas por HashBench . . . . . 104
4.2.6. SMHasher . . . . . . . . . . . . . . . . . . . . . . . . . 109
4.3. Comparaci on experimental de las FHNC mas importantes usan-
do HashBench . . . . . . . . . . . . . . . . . . . . . . . . . . . 111
4.3.1. Efecto avalancha . . . . . . . . . . . . . . . . . . . . . 111
4.3.2. El mito del m odulo primo . . . . . . . . . . . . . . . . 115
4.3.3. Distribuci on de las salidas . . . . . . . . . . . . . . . . 120
4.3.4. Velocidad . . . . . . . . . . . . . . . . . . . . . . . . . 122
4.3.5. Conclusiones . . . . . . . . . . . . . . . . . . . . . . . 124
4.4. Resumen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 127
5. Generaci on de FHNC con PG: El sistema GP-hash 129
5.1. Antecedentes (Estado de la cuesti on) . . . . . . . . . . . . . . 129
5.1.1. Origen de esta tesis . . . . . . . . . . . . . . . . . . . . 130
5.1.2. Diseno~ autom atico de generadores de numeros pseudo-
aleatorios . . . . . . . . . . . . . . . . . . . . . . . . . 131
5.1.3. Generaci on autom atica de funciones hash criptogr a cas 133
IV5.1.4. Generaci on autom atica de FHNC . . . . . . . . . . . . 133
5.1.5. Conclusiones . . . . . . . . . . . . . . . . . . . . . . . 136
5.2. Diseno~ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 137
5.2.1. ProGen . . . . . . . . . . . . . . . . . . . . . . . . . 137
5.2.2. HashBench . . . . . . . . . . . . . . . . . . . . . . . . 138
5.2.3. GP-hash Core . . . . . . . . . . . . . . . . . . . . . . . 139
5.3. Implementaci on . . . . . . . . . . . . . . . . . . . . . . . . . . 139
5.3.1. Funci on de Fitness . . . . . . . . . . . . . . . . . . . . 140
5.3.2. Conjunto de funciones y terminales . . . . . . . . . . . 148
5.3.3. Ajuste de par ametros . . . . . . . . . . . . . . . . . . . 160
5.4. Resumen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 174
6. GP-hash: Generaci on de FHNC de prop osito general 177
6.1. Objetivo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 177
6.2. Metodolog a . . . . . . . . . . . . . . . . . . . . . . . . . . . . 178
6.2.1. Fase 1: GP-hash . . . . . . . . . . . . . . . . . . . . . . 178
6.2.2. Fase 2: HashBench . . . . . . . . . . . . . . . . . . . . 179
6.3. Resultados I: Con guraci on b asica . . . . . . . . . . . . . . . . 181
6.3.1. Fase 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . 181
6.3.2. Fase 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . 182
6.4. Resultados II: Ajuste del tamano~ de muestreo en el tness de
avalancha . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 195
6.4.1. Fase 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . 196
6.4.2. Fase 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . 198
6.5. Resultados III: Rotaci on binaria . . . . . . . . . . . . . . . . . 203
6.5.1. Fase 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . 204
6.5.2. Fase 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . 204
6.6. Conclusiones . . . . . . . . . . . . . . . . . . . . . . . . . . . . 211
7. GP-hash: Generaci on de FHNC a medida. 215
7.1. Objetivo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 217
7.2. Metodolog a . . . . . . . . . . . . . . . . . . . . . . . . . . . . 217
7.3. Funci on de tness de entrop a . . . . . . . . . . . . . . . . . . 220
7.3.1. Conjunto real.Lcc . . . . . . . . . . . . . . . . . . . . . 220
7.3.2.to real.Nombres . . . . . . . . . . . . . . . . . . 223
7.3.3. Conjunto real.Passwords . . . . . . . . . . . . . . . . . 225
7.3.4.to real.Megatab . . . . . . . . . . . . . . . . . . 226
7.3.5. Conjunto synth.Random . . . . . . . . . . . . . . . . . 228
7.3.6.to synth.Repeat . . . . . . . . . . . . . . . . . . 229
7.3.7. Conjunto synth.Sparse . . . . . . . . . . . . . . . . . . 231
7.3.8.to synth.Variable . . . . . . . . . . . . . . . . . 232
V7.3.9. Resumen y An alisis . . . . . . . . . . . . . . . . . . . . 233
7.4. Otras funciones de tness . . . . . . . . . . . . . . . . . . . . 235
7.4.1. Fitness basada en distancia de Bhattacharyya . . . . . 235
27.4.2. en tests . . . . . . . . . . . . . . . . 236
7.4.3. Fitness basada en tasas de colisiones . . . . . . . . . . 237
7.5. Discusi on sobre las distintas funciones de tness . . . . . . . . 239
7.6. Conclusiones . . . . . . . . . . . . . . . . . . . . . . . . . . . . 240
8. Conclusiones y L neas Futuras de Investigaci on 245
8.1. Introducci on y conocimientos b asicos . . . . . . . . . . . . . . 246
8.2. El problema de la evaluaci on de FHNC . . . . . . . . . . . . . 247
8.3. Diseno~ e implementacion de GP-hash . . . . . . . . . . . . . . 250
8.3.1. Estado de la cuesti on . . . . . . . . . . . . . . . . . . . 251
8.3.2. Diseno~ de GP-hash . . . . . . . . . . . . . . . . . . . . 252
8.3.3. Implementaci on de GP-hash . . . . . . . . . . . . . . . 252
8.4. Generaci on de FHNC de prop osito general . . . . . . . . . . . 254
8.5.on de a medida . . . . . . . . . . . . . . . . . 256
8.6. Trabajos futuros y posibles aplicaciones . . . . . . . . . . . . . 260
8.7. Conclusiones nales . . . . . . . . . . . . . . . . . . . . . . . . 267
VIIndice de guras
2.1. Representaconi del programa ( log(X 7) (3 +Y )) en forma
de arb ol sinacticot (arriba) y en forma de s-expression o en
notaci on polaca (abajo). . . . . . . . . . . . . . . . . . . . . . 16
2.2. Ejemplo de cruce est andar utilizado para generar un nuevo
individuo (izquierda) o dos (derecha). . . . . . . . . . . . . . . 20
2.3. Ejemplo de aplicaci on del cruce de un punto. . . . . . . . . . . 20
2.4. del tness landscape de un problema relativamente
sencillo para la Programaci on Genetica. . . . . . . . . . . . . . 28
2.5. Ejemplo del tness landscape de un problema dif cil para la
Programaci on Genetica. . . . . . . . . . . . . . . . . . . . . . 29
3.1. Ejemplo de una funci on hash t pica: Los valores de entrada
pueden tener cualquier longitud; Las salidas son valores de
32 bits; Las dos ultimas entradas se diferencian olos en una
palabra, pero sus salidas son completamente distintas. . . . . . 37
3.2. Merkle{Damgard construction. . . . . . . . . . . . . . . . . . 39
3.3. Esquema del bloque de compresi on de una funci on hash. . . . 44
3.4. Resoluci on de colisiones mediante encadenamiento: los elemen-
tos que colisionan en la posici on i se colocan en una lista en-
lazada. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
3.5. Ejemplo de funcionamiento de un bloom lter de 30 bits con 3
funciones hash (N = 30;k = 3). Los objetosx yx se insertan1 2
poniendo a 1 los tres bits correspondientes a los valores hash
producidos para cada uno. Al consultar six est a en el conjun-3
to se produce un falso positivo debido a que h (x ) =h (x ),1 3 1 2
h (x ) =h (x ) y h (x ) =h (x ). . . . . . . . . . . . . . . . . 642 3 3 1 3 3 2 1
4.1. En estos dos casos, las metricas de tasa del colisiones dan el
mismo resultado, pese a que la con guraci on de la izquierda
es bastante mala, y la de la derecha es la ideal. . . . . . . . . . 87
4.2. Una funci on hash ( h) con un buen efecto avalancha. . . . . . . 92
VII4.3. Matrices de avalancha para las FHNC implementadas en Hash-
Bench. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113
4.4. Medida de error RMSE de la matriz de avalancha de cada
funci on respecto a la matriz ideal. . . . . . . . . . . . . . . . . 115
4.5. Resultados de los tests de entrop a. Las barras indican la pun-
tuaci on de entrop a lograda por cada funci on. . . . . . . . . . 121
4.6. Resultados de los tests de velocidad. . . . . . . . . . . . . . . 123
5.1. Ejemplos de representaci on gr a ca de varias matrices de ava-
lancha. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 149
5.2. Operadores de desplazamiento y rotaci on de bits. . . . . . . . 153
5.3. Mejora del tness medio en relaci on al numero de individuos
de la poblaci on. Los puntos representan las mediciones para
100, 200, 300, 400, 500 y 1000 individuos por poblaci on. . . . . 165
5.4. Mejora del tness medio en relaci on al tamano~ de los torneos.
Los puntos representan las mediciones para tamano~ 2, 4 (la
referencia), 6, 8 y 10. . . . . . . . . . . . . . . . . . . . . . . . 166
5.5. Impacto de los distintos porcentajes de elitismo en el tness
medio. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 167
5.6. Fitness del mejor individuo de cada una de las 50 ejecuciones
(c rculos grises) y su media (l nea roja) para cada generaci on. 169
5.7. Ampliaci on de la Figura 5.6 sobre las cien primeras generaciones.170
6.1. Diagramas de caja de los valores del tness, numero de nodos
y profundidad de las FHNC generadas en las 50 ejecuciones. . 182
6.2. Fitness del mejor individuo de cada una de las 50 ejecuciones
para cada generaci on (c rculos grises), y la media de todos
ellos tambien para cada generaci on (l nea roja). . . . . . . . . 183
6.3. Matrices de avalancha de las funciones gp-hash601, gp-hash602,
gp-hash603, gp-hash604 y gp-hash605. . . . . . . . . . . . . . 185
6.4. Medida de error RMSE de la matriz de avalancha de cada
funci on respecto a la matriz ideal. . . . . . . . . . . . . . . . . 186
6.5. Resultados de los tests de entrop a prime-sparse para las
funciones gp-hash601, gp-hash602, gp-hash603, gp-hash604 y
gp-hash605. N otese que la escala es distinta para cada gr a ca. 187
6.6. Diagramas de ocupaci on de las tablas hash correspondientes
a la funci on lookup3 (a) y gp-hash601 (b). . . . . . . . . . . . 190
6.7. Diagrama de ocupaci on de la tabla hash correspondiente a la
funci on gp-hash605. . . . . . . . . . . . . . . . . . . . . . . . . 191
6.8. Diagramas de caja de los valores del tness, numero de nodos
y profundidad de las FHNC generadas en las 50 ejecuciones. . 198
VIII

Un pour Un
Permettre à tous d'accéder à la lecture
Pour chaque accès à la bibliothèque, YouScribe donne un accès à une personne dans le besoin