Algorithmic diversity through semantic program comparison (2021)
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.