Deteccion automatica de estructuras de datos basadas en punteros

Abstract

En esta tesis se han desarrollado nuevas tecnicas para el analisis automatico de la forma de las estructuras dinamicas creadas a base de punteros. Hemos propuesto e implementado una mejora sobre el metodo SSG, permitiendo que en los grafos existan mas de un nodo sumario y que contengan mas informacion por nodo. Esto permite que el metodo sea capaz de reconocer estructuras mas complejas como la utilizada por un algoritmo de descomposicion LU de una matriz dispersa. Precisamente se ha analizado con la implementacion del metodo un codigo sintetico que crea y modifica la misma estructura utilizada en dicho algoritmo, obteniendose unos resultados satisfactorios. Aunque la mejora sobre los SSGs a permitido el reconocimieto de estructuras mas complejas, algunas de sus peculiaridades hacen que el metodo falle a la hora de analizar nucleos de algoritmos reales. Para solucionar, esto hemos propuesto un nuevo metodo basado en grafos, denominado conjunto Reducido de Grafos de forma de Referencias (RSRSG). Este metodo utiliza un conjunto de grafos para describir las posibles configuraciones de memoria que pueden aparecer tras la ejecucion de una sentencia. Tambien hemos creado una abstraccion nueva, los multiselectores, dentro de los RSRSGs para el soprote de los arrays de punteros como un elemento nuevo dentro de las porciones de memoria. Con la implementacion del metodo RSRSG, en un pseudocompilador que lee codigo C y devuelve el RSRSG asociado a cada sentencia, se han analizado una serie de codigos reales basados en estructuras de datos dinamicas como son la multiplicacion de una matriz dispersa por un vector,la multiplicacion de dos matrices dispersas, la factorizacion LU de una matriz dispersa y el nucleo de algoritmo de simulacion N-Body Barnes-Hut. Los RSRSGs obtenidos para cada codigo describen con gran precision las estructuras dinamicas utilizadas. Hasta donde nosotros conocemos, ninguno de los metodos propuestos anteriormente para detecta