Desafíos en el análisis estático de software

En esta nota, se exploran las oportunidades de realizar el análisis estático y automático de código en un set de máquinas distribuidas en la nube, con la posibilidad de utilizar algoritmos elásticos en memoria.

Actualmente una actividad muy relevante dentro de la ingeniería de software es el análisis automático de programas. Estos tipos de análisis permiten que el software que se usa diariamente tenga menos errores y, a su vez, poder ayudar a los desarrolladores de software  a tener una mejor comprensión del código de cada programa. A diferencia del análisis dinámico de software que involucra la ejecución real del programa, el análisis estático es una suerte de “inspección de código” que permite simular que el programa se ejecuta con todos los datos posibles.

Este es uno de los problemas en que se enfoca Diego Garbervetsky, integrante del Grupo de Fundamentos de la Ingeniería de Software e investigador del ICC. “Nuestra investigación apunta a hacer programas que entiendan diferentes propiedades de un programa. Puede ser desde un Bug (error de software), un acceso sin permiso a un recurso, o un acceso a una porción de memoria incorrecta. Incluso aparecen propiedades más sutiles: el programa corre más lento de lo esperado, consume más memoria o aparecen relaciones directas entre los datos de entrada y de salida”, puntualiza Garbervetsky.

En la práctica el investigador se ocupa del análisis estático que se sitúa sobre el código fuente original y busca entenderlo pero sin necesidad de ejecutar realmente el programa. Se trata de una simulación abstracta de lo que luego se ejecutará en la realidad en la computadora, la “nube” o el teléfono móvil.

Una de las bases teóricas de los análisis estáticos es la idea de Interpretación Abstracta. Esta da un marco para la ejecución “virtual” del código donde se simula su ejecución con datos aproximados (en realidad cada dato representa muchos datos), reduciendo la cantidad de operaciones totales  que el programa necesita para completar. Como estos análisis logran la exhaustividad para todas las entradas o datos posibles mediante la aproximación del cómputo, es frecuente que en ese proceso aparezcan “falsos positivos”: errores del programa que en realidad no lo son. Ante la pregunta sobre cómo lidiar con este aspecto del análisis, el investigador del ICC aclara, “una posibilidad es ejecutar realmente el programa y ver qué sucede, otra es refinar el análisis en el lugar preciso donde aparece el supuesto error, lo cual es un poco más costoso pero puede eliminar ese dato falso”.

Otro de los usos que presenta este tipo de técnicas es que ayudan al entendimiento del programa, como brindar a los desarrolladores de software herramientas para que puedan navegar el código u obtener visualizaciones de diferentes aspectos de su semántica, optimizando tiempos y recursos.

En general para poder analizar el programa es necesario diseñar un mapa (o grafo) que permita seguir el camino que transita durante la ejecución, ya que habitualmente en un programa se salta de una función a otra y se lee no secuencialmente (como si fuera una red de caminos que no sigue un recorrido predefinido). “Calcular ese mapa es complejo y depende del tamaño del programa, la cantidad de llamadas que tiene y un último factor, que aparece generalmente en la programación orientada a objetos, es la cantidad de destinos posibles en función del objeto receptor de un mensaje. Por ejemplo, si en el programa Corel Draw está la función ‘figura.dibujar’, esa figura puede ser un cuadrado, círculo, triángulo, etc. Puede haber miles de figuras asociadas a una misma función, y hay que adivinar en tiempo de análisis a qué figura real se estaría refiriendo cuando el programa realmente se ejecute. Un análisis aproximado elegirá siempre el tipo de figura correcto pero si es aproximado puede elegir algunas adicionales (falsos positivos)”, precisa el investigador y doctor en ciencias de la computación.

La complejidad de esta tarea converge en el análisis de referencias o análisis de punteros, que es uno de los análisis estáticos clásicos y sirve de base para muchos otros análisis, ya que ayuda a construir el mapa de la aplicación. Es por ello que frecuentemente se investiga cómo realizar versiones de estas técnicas para que permitan escalar a programas grandes (millones de líneas de código) y mantener una precisión razonable. Mantener este equilibrio es difícil, porque un análisis preciso suele ser muy costoso, en términos de tiempo y sobre todo consumo de memoria. Entonces uno tiene que decidir de acuerdo a los recursos que disponibles.

Ahora bien, ¿cómo ayuda al análisis automático estar en un entorno Cloud donde se pueda realizar en diferentes computadoras distribuidas en lugar de en una sola computadora? Para encarar esta cuestión en profundidad, Garbervetsky viene desarrollando una colaboración con Microsoft Research junto a Edgardo Zoppi (Investigador en formación del ICC), Tom Ball (Investigador principal de Microsoft Research) y Benjamin Livshits (Profesor Asociado del Imperial College de Londrés). Con el propósito de difundir el trabajo ya han publicado el artículo científico “Toward Full Elasticity in Distributed Static Analysis: The case of Callgraph Analysis”.

El investigador del ICC explica que el proyecto surgió de un contexto muy favorable. “A diferencia de hace algunos años donde todos los análisis se hacían en una sola máquina y localmente, hoy vemos que muchos de las herramienta para edición de  de código son online, permitiendo que la visualización se haga en la máquina del programador pero la compilación suceda en otras máquinas. Además la mayoría de los repositorios de código open source brindan la posibilidad de compilar proyectos. Encontramos una enorme oportunidad de poder generar un algoritmo distribuido para el análisis en la nube, con muchas máquinas conectadas al mismo tiempo y aprovechando recursos libres de cómputo a un menor costo”, comenta con entusiasmo Garbervetsky.

Poder diseñar el análisis para que sea distribuible en la nube fue una ventaja sustancial para los investigadores en cuanto a poder de cómputo y memoria disponible. Si bien muchos de los algoritmos actuales están pensados para correr en una sola máquina, este algoritmo distribuido debía ser completamente elástico para dividir el análisis en diferentes máquinas. No obstante, a partir de estos avances aparecieron diferentes problemas 1) Aunque se pudo diseñar un algoritmo que sea elástico en el uso de memoria porque cada vez que se necesitaba más memoria se agregaba una computadora más, a medida que aumenta la necesidad de comunicación entre máquinas llega un punto en que la comunicación de los procesos genera demasiado overhead; 2) Con esa instancia en que no se produce una mejora en velocidad de procesamiento (aunque sí en memoria), es necesario mover una porción del grafo de proceso a una máquina que esté más cercana para mejorar la performance  3) Un último desafío del trabajo es poder escalar el proceso utilizando un “algoritmo incremental”: si el programa tiene 100 millones de líneas de código, se hace un análisis que tenga en cuenta sólo la modificación en cada punto que se propaga del código (por ej. cambiar la variable figura para que en lugar de apuntar a un círculo apunte a un cuadrado). “De ese modo no hace falta repetir el análisis de esos millones de líneas sino sólo de la parte afectada, lo cual ayuda a escalar el proyecto logrando un análisis más rápido y eficiente”, concluye Garbervetsky.