Publication: Diseño automático de funciones hash no criptográficas
Loading...
Identifiers
Publication date
2011
Defense date
2011-11-18
Authors
Advisors
Tutors
Journal Title
Journal ISSN
Volume Title
Publisher
Impact
Export
Abstract
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.
Description
Keywords
Funciones hash no criptográficas, Diseño automático