Combining Static Code Analysis and Large Language Models Improves Correctness and Performance of Algorithm Recognition

Resumen Técnico: Combinación de Análisis Estático y Modelos de Lenguaje Grande para el Reconocimiento de Algoritmos

1. Problema y Contexto

Los desarrolladores dedican más de la mitad de su tiempo a la comprensión del código fuente. El reconocimiento automático de algoritmos dentro de bases de código es una capacidad valiosa para apoyar la comprensión de programas, facilitar el mantenimiento y mejorar la calidad del software. Sin embargo, las técnicas existentes suelen basarse en patrones de búsqueda heurísticos o clasificadores de aprendizaje automático tradicionales, que carecen de flexibilidad o requieren un reentrenamiento costoso para nuevos algoritmos.

Recientemente, los Modelos de Lenguaje Grande (LLMs) han demostrado un rendimiento excepcional en tareas relacionadas con el código. No obstante, su aplicación directa para la detección de algoritmos presenta dos desafíos principales:

1. Costo y Tiempo de Ejecución: Las llamadas a LLMs son computacionalmente costosas y lentas, especialmente en grandes bases de código.
2. Dependencia de Nombres: Existe el riesgo de que los modelos dependan excesivamente de nombres de identificadores (variables, funciones) en lugar de la semántica real del código, lo que podría llevar a falsos positivos si los nombres son engañosos.

El objetivo de este estudio es evaluar empíricamente cómo la combinación de LLMs con análisis estático de código puede mejorar la precisión y el rendimiento del reconocimiento de algoritmos, comparándolo con el uso de LLMs de forma aislada.

2. Metodología

Los autores realizaron un estudio empírico riguroso siguiendo las guías de ingeniería de software, utilizando el conjunto de datos BigCloneEval (BCEval), que contiene implementaciones de algoritmos verificadas manualmente en código Java real.

• Modelos Evaluados: Se probaron tres LLMs de vanguardia: GPT-4o mini, Llama 3.1 70B y Mixtral 8x22B.
• Algoritmos Objetivo: Se centraron en 7 algoritmos específicos (Factores Primos, MCD, Fibonacci, Palíndromo, Ordenamiento Burbuja, Búsqueda Binaria y Transposición de Matriz).
• Preguntas de Investigación (RQ):
  • RQ1 (Estrategias de Prompting): ¿Qué estrategias (Zero-shot, In-Context Learning, Chain of Thought) funcionan mejor?
  • RQ2 (Análisis Estático): ¿Se pueden usar patrones de filtrado estático para reducir los requisitos de tiempo de ejecución sin sacrificar la precisión?
  • RQ3 (Información de Nombres): ¿Qué tan dependientes son los LLMs de la información de los nombres de los identificadores?

Diseño Experimental:

1. Prompting: Se compararon prompts binarios (Sí/No) con prompts de puntuación (0-4) y se evaluó el In-Context Learning (ICL) con diferentes combinaciones de ejemplos positivos y negativos.
2. Filtrado Híbrido: Se implementaron patrones de filtrado estático (basados en palabras clave y características estructurales del AST - Árbol de Sintaxis Abstracta) para descartar métodos que no implementan el algoritmo antes de enviar el código al LLM.
3. Obfuscación: Se realizó un estudio de ablación donde se reemplazaron los identificadores de código por nombres aleatorios para medir la dependencia semántica del modelo.

3. Contribuciones Clave

1. Evaluación de Estrategias de Prompting: Determinación de que el In-Context Learning con dos ejemplos positivos es el punto óptimo ("sweet-spot") entre rendimiento y tiempo de inferencia.
2. Arquitectura Híbrida: Propuesta y validación de un enfoque que combina análisis estático ligero con LLMs, logrando reducir drásticamente las llamadas a los modelos.
3. Análisis de Robustez: Cuantificación de la dependencia de los LLMs respecto a los nombres de las variables, demostrando que los modelos pueden inferir algoritmos basándose en la lógica estructural incluso sin nombres descriptivos.

4. Resultados Principales

• RQ1: Estrategias de Prompting

  • El In-Context Learning (ICL) mejoró los puntajes F1 en un 4-8% en comparación con la línea base.
  • Proporcionar dos ejemplos positivos (2P+0N) ofreció la mejor relación costo-beneficio. Añadir más ejemplos aumentó el tiempo de inferencia linealmente con ganancias marginales.
  • La técnica Chain of Thought (CoT) no superó al ICL y aumentó el tiempo de ejecución en un factor de ~15x a ~65x, haciéndola inviable para grandes conjuntos de datos.

• RQ2: Combinación con Análisis Estático

  • Los patrones de filtrado estático (basados en palabras clave y características estructurales) lograron reducir las llamadas a LLMs entre un 72.39% y un 97.50%.
  • Mejora de Precisión: Al eliminar falsos negativos potenciales antes de la clasificación, la combinación híbrida mejoró los puntajes F1 en hasta 12 puntos porcentuales en comparación con el uso exclusivo de LLMs.
  • Eficiencia: El tiempo de procesamiento total para el conjunto de datos completo se redujo de ~19 horas a solo 33 minutos utilizando el patrón "Prominent Feature" con Mixtral.
  • La combinación superó consistentemente a ambos enfoques (solo LLM o solo análisis estático) en precisión y F1.

• RQ3: Dependencia de Nombres

  • Al obfuscar los identificadores, la recuperación (Recall) disminuyó ligeramente (4-5%), pero la precisión aumentó significativamente (hasta 17 puntos porcentuales para Mixtral).
  • Sorprendentemente, el puntaje F1 global aumentó entre 3 y 10 puntos. Esto indica que los nombres genéricos o engañosos a menudo causaban falsos positivos en la línea base, y que los LLMs son capaces de reconocer la lógica del algoritmo basándose en la semántica del código, no solo en los nombres.

5. Significado y Conclusión

El estudio concluye que la combinación de análisis estático y LLMs es un enfoque superior para el reconocimiento de algoritmos.

• Eficiencia: Permite escalar la detección a grandes bases de código reduciendo drásticamente los costos computacionales.
• Precisión: Mejora la calidad de la detección al filtrar casos obvios que no requieren la capacidad de razonamiento profundo del LLM.
• Robustez: Los LLMs no dependen exclusivamente de nombres de variables; pueden inferir algoritmos basándose en la estructura y el flujo de control, lo que los hace herramientas viables para el análisis de código ofuscado o mal documentado.

Los autores proponen el desarrollo de pipelines automatizados e integraciones en IDEs que utilicen estos patrones de filtrado para asistir a los desarrolladores en la comprensión y optimización del código en tiempo real.