Algorithmic diversity through semantic program comparison

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 tant...

Full description

Autores:
Trujillo Achury, Miller Andrés
Tipo de recurso:
Fecha de publicación:
2021
Institución:
Universidad de los Andes
Repositorio:
Séneca: repositorio Uniandes
Idioma:
eng
OAI Identifier:
oai:repositorio.uniandes.edu.co:1992/55118
Acceso en línea:
http://hdl.handle.net/1992/55118
Palabra clave:
Semantic equivalence
Program similitude
Code clones
Algorithmic diversity
Ingeniería
Rights
openAccess
License
http://creativecommons.org/licenses/by-nc-nd/4.0/
Description
Summary: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.