Análisis Estático de Programas

El análisis estático de programas examina el código fuente o intermedio, sin ejecutarlo, para inferir propiedades como los valores que una variable puede contener o si puede ocurrir un error.

Definition

El análisis estático de programas es el cálculo de información aproximada pero sólida sobre los posibles comportamientos de un programa directamente a partir de su código, sin ejecutarlo, típicamente resolviendo ecuaciones de flujo de datos sobre un retículo de estados abstractos.

Scope

Este tema abarca el análisis de flujo de datos sobre grafos de flujo de control, el cálculo de punto fijo basado en retículos, el análisis interprocedural, el análisis de punteros y alias, y el análisis de grafos de llamadas y flujo de control. Aborda las dimensiones de precisión (sensibilidad al flujo, al contexto y a la ruta), la solidez de los análisis y su uso en la optimización y la detección de errores.

Core questions

• ¿Cómo se calculan las propiedades del programa propagando hechos sobre un grafo de flujo de control?
• ¿Cómo afectan la sensibilidad al flujo, al contexto y a la ruta la precisión y el costo?
• ¿Cómo se realiza un análisis sólido a través de las llamadas a procedimientos?
• ¿Cómo maneja el análisis de punteros el aliasing y la indirección?

Key theories

Análisis de flujo de datos como punto fijo sobre un retículo

Kildall unificó las optimizaciones globales de programas como el cálculo de un punto fijo de ecuaciones de flujo de datos sobre un retículo, proporcionando el marco general para los análisis estáticos.

Análisis interprocedural mediante alcanzabilidad de grafos

Reps, Horwitz y Sagiv redujeron una gran clase de problemas precisos de flujo de datos interprocedural a la alcanzabilidad de grafos, lo que permitió un análisis eficiente sensible al contexto a través de los límites de los procedimientos.

Principios y dimensiones del análisis

Nielson, Nielson y Hankin sistematizan los análisis basados en flujo de datos, en restricciones y en tipos, así como las compensaciones entre precisión y costo que rigen su diseño.

Clinical relevance

El análisis estático impulsa las optimizaciones del compilador, las herramientas de detección de errores y vulnerabilidades, los linters y las características del IDE. Los análisis sólidos pueden certificar la ausencia de ciertos errores, mientras que los análisis heurísticos escalables se implementan ampliamente para detectar defectos tempranamente en el desarrollo.

History

El análisis de flujo de datos surgió de los compiladores optimizadores, con el marco de retículos de Kildall de 1973 y los análisis de Allen-Cocke proporcionando la base teórica. Los análisis interprocedurales y de punteros avanzaron a lo largo de las décadas de 1980 y 1990, incluyendo la formulación de alcanzabilidad de Reps-Horwitz-Sagiv, y el análisis estático posteriormente escaló a la detección de errores industriales en bases de código muy grandes.

Debates

Precisión versus escalabilidad

Los diseñadores de análisis continuamente intercambian dimensiones de precisión como la sensibilidad al contexto y a la ruta, que reducen los falsos positivos, por el costo computacional que limita el tamaño de un programa que puede ser analizado.

Key figures

• Gary Kildall
• Thomas Reps
• Susan Horwitz
• Flemming Nielson
• Hanne Riis Nielson

Seminal works

• kildall1973
• reps1995
• nielson1999

Frequently asked questions

¿Qué significa que un análisis estático sea sólido?

Un análisis sólido nunca omite una ocurrencia real de la propiedad que verifica: si no reporta ningún error de un tipo dado, ese tipo de error genuinamente no puede ocurrir, aunque también puede generar falsas alarmas.

¿Por qué es difícil el análisis de punteros?

Los punteros y las referencias introducen el aliasing, donde múltiples nombres se refieren a la misma memoria, por lo que el análisis debe aproximar qué ubicaciones puede apuntar cada puntero, un problema que intercambia precisión por escalabilidad.