Trabajo de grado - Maestría
Algorithmic diversity through semantic program comparison
Fecha
2021Registro en:
instname:Universidad de los Andes
reponame:Repositorio Institucional Séneca
Autor
Trujillo Achury, Miller Andrés
Institución
Resumen
La diversidad es una propiedad bien estudiada en el diseño de software, especialmente en áreas como la seguridad o los sistemas distribuidos. Sin embargo, a la hora de diseñar un sistema, no existen formas adecuadas de medir la diversidad real entre las distintas implementaciones del mismo. Por tanto, proponemos una nueva métrica de diversidad basada en técnicas de análisis de similitud de programas que utiliza la representación de grafos de flujo de control para determinar el grado de similitud de dos programas dados. Dividimos nuestro trabajo en dos partes principales: El análisis de la similitud de los programas y el análisis del impacto de la diversidad en el software. Para validar nuestro enfoque de análisis de la similitud de los programas, utilizamos programas simples de los dominios de los algoritmos de ordenamiento, búsqueda y agregación, midiendo la similitud entre las diferentes implementaciones. Además, utilizamos un nuevo corpus creado a partir de problemas de concursos virtuales de programación competitiva para descubrir la similitud entre las soluciones presentadas por los concursantes. Para evaluar el impacto de la diversidad, utilizamos una configuración de balanceadores de carga que implementan diferentes algoritmos, y medimos el rendimiento del sistema utilizando la latencia y la tasa de errores. Nuestros resultados muestran que, de hecho, nuestro enfoque para analizar la similitud de los programas detecta correctamente la similitud entre diferentes implementaciones de programas, y marca como diferentes aquellas implementaciones a problemas no relacionados, con un rendimiento comparable a los enfoques existentes. Por último, también observamos que al añadir diversidad a la configuración de balanceadores de carga se reducía la latencia de todo el sistema, sin impactar las tasas de error. Diversity is a well-studied property of software design, specially in areas like security or distributed systems. However, when designing a system, there are no proper ways for measuring actual diversity between different implementations within it. We proposed a novel diversity metric based on an improved program similitude technique that uses the control flow graph representation of programs to determine how similar are two given programs. We divided our work into two main parts: Analyzing program similitude, and analyzing the impact of diversity in software. To validate our approach for analyzing program similitude, we used simple programs from the domains of sorting, search and aggregation algorithms, measuring the similitude between the different implementations. Additionally, we use a new corpus created from competitive programming virtual judges problems to discover similitude between solutions submitted by contestants. To evaluate the impact of diversity, we used a setup of load balancers which implements different algorithms, and measured system performance using latency and error rate. Our results show that in fact, our approach for analyzing program similitude correctly detects similitude between different program implementations, and marks as different those implementations to unrelated programs problems, with a performance comparable to existing approaches. Finally, we also observed that adding diversity to the setup of load balancers reduced the latency of the whole systems, however we did not find any improvement on the error rates. Additionally, we noted a logarithmic proportionality between the number of algorithms and the diversity value calculated with our approach. This exhibits that increasing the number of algorithms will increase diversity, but after a certain limit we do not expect the diversity to change significantly, and neither systems' performance.