Análisis de punteros y de memoria

Todo lo anterior se apoya en una suposición que en un binario nunca se cumple: que sabemos qué escribe cada instrucción. Este capítulo levanta esa suposición. El análisis de punteros es, con diferencia, el análisis que más determina la calidad de un decompilador, porque de él dependen el análisis de memoria del capítulo «16», la recuperación de variables y la de tipos.

18.1 El problema

Supóngase que queremos hacer análisis de signos o propagación de constantes sobre este código:

...
*x = 42;
*y = -87;
z = *x;

El valor de z depende de si x e y son alias, es decir, de si apuntan a la misma celda. Sin información de aliasing, resulta rápidamente imposible producir resultados útiles de flujo de datos o de flujo de control.

18.2 Abstracción por sitio de asignación

La información fundamental que hay que obtener es el conjunto de celdas de memoria a las que pueden apuntar los punteros. Durante la ejecución hay arbitrariamente muchas celdas, así que hace falta una abstracción finita.

La elección habitual se llama abstracción por sitio de asignación (allocation-site abstraction): se introduce una celda abstracta X por cada variable del programa llamada X, y una celda abstracta alloc-i por cada ocurrencia de una operación alloc en el programa. Cada celda abstracta representa el conjunto de celdas que en tiempo de ejecución se asignan en esa posición del código —de ahí el nombre—. Escribiremos Cell para el conjunto de celdas abstractas.

Los primeros análisis que veremos son insensibles al flujo. Su resultado es una función

que para cada variable puntero X devuelve el conjunto pt(X) de celdas abstractas a las que puede apuntar. A esta clase de análisis se la llama análisis de apuntamiento (points-to analysis), y se busca que sea conservador: conjuntos que pueden ser demasiado grandes, nunca demasiado pequeños.

Con esa información se aproximan muchos otros hechos. Para saber si x e y pueden ser alias, una respuesta segura se obtiene comprobando si pt(x) ∩ pt(y) es no vacío.

El análisis casi trivial, llamado address taken, consiste en devolver todas las celdas abstractas posibles, incluyendo una variable X sólo si la expresión &X aparece en el programa. Basta para aplicaciones muy simples. Si nos restringimos a programas tipables, cualquier análisis de apuntamiento puede mejorarse eliminando las celdas cuyo tipo no case con el del puntero.

18.3 El algoritmo de Andersen

El algoritmo de Andersen, o análisis de apuntamiento basado en inclusión, es muy parecido al análisis de flujo de control del capítulo «17». Para cada celda abstracta c se introduce una variable de restricción ⟦c⟧ cuyo valor es un conjunto de celdas abstractas.

Se supone el programa normalizado de modo que toda operación con punteros sea de una de estas seis formas:

X = alloc P;      donde P es null o una constante entera
X1 = &X2;
X1 = X2;
X1 = *X2;
*X1 = X2;
X = null;

y para cada una se generan las restricciones:

Las dos restricciones condicionales se generan para cada celda abstracta, aunque es seguro saltarse las celdas de variables X donde &X no aparece en el programa. La asignación a null se ignora, porque corresponde a la restricción trivial ∅ ⊆ ⟦X⟧.

Estas restricciones encajan exactamente en el formato del algoritmo cúbico del capítulo «17». El resultado es simplemente pt(p) = ⟦p⟧.

Un ejemplo:

p = alloc null;
x = y;
x = z;
*p = z;
p = q;
q = &y;
x = *p;
p = &z;

Las restricciones generadas, con Cell = {p, q, x, y, z, alloc-1}:

alloc-1 in [[p]]
[[y]] subset [[x]]
[[z]] subset [[x]]
c in [[p]]  =>  [[z]] subset [[c]]      para cada c en Cell
[[q]] subset [[p]]
y in [[q]]
c in [[p]]  =>  [[c]] subset [[x]]      para cada c en Cell
z in [[p]]

y la menor solución es bastante precisa:

pt(p) = {alloc-1, y, z}
pt(q) = {y}
pt(x) = pt(y) = pt(z) = {}

Aunque el análisis es insensible al flujo, la direccionalidad de las restricciones de inclusión hace que el flujo de datos se modele con cierta precisión: ⟦y⟧ ⊆ ⟦x⟧ no es lo mismo que ⟦x⟧ = ⟦y⟧.

18.4 Sensibilidad a los campos

Para programas con registros —o estructuras— hay tres niveles:

• Insensible a campos (field insensitive): se tratan todos los campos de un registro como equivalentes. Trivial de implementar y muy impreciso.
• Basado en campos (field based): se trata cada nombre de campo como una variable global única, sin distinguir entre las distintas celdas que lo contienen. Sorprendentemente útil en lenguajes con tipado fuerte.
• Sensible a campos (field sensitive): se distingue cada pareja (celda, campo).

Para la versión sensible a campos se amplían las variables de restricción a ⟦·⟧ : Cell ∪ (Cell × Field) → ℘(Cell), escribiendo ⟦c.f⟧, y se añaden reglas para las operaciones sobre registros. Las más importantes:

X = {X1:X'1, ..., Xk:X'k}      [[X'1]] subset [[X.X1]] and ... and [[X'k]] subset [[X.Xk]]
X = alloc {X1:X'1, ...}        alloc-i in [[X]]  and  [[X'j]] subset [[alloc-i.Xj]]
X1 = X2.X3                     [[X2.X3]] subset [[X1]]
X1 = X2                        [[X2]] subset [[X1]]  and
                               [[X2.f]] subset [[X1.f]]  para cada f en Field
X1 = *X2                       c in [[X2]] => ([[c]] subset [[X1]] and
                                               [[c.f]] subset [[X1.f]])
                               para cada c en Cell y f en Field

Un ejemplo, ya normalizado:

i = null;
x = alloc {f: i};   // alloc-1
y = alloc {h: x};   // alloc-2
t = *y;
z = t.h;

produce pt(x) = pt(z) = {alloc-1}, pt(y) = {alloc-2}, pt(i) = pt(t) = ∅. Obsérvese que la sensibilidad a campos es lo que permite concluir que z apunta a alloc-1: un análisis insensible a campos habría mezclado f y h.

18.5 El algoritmo de Steensgaard

Una alternativa interesante es el algoritmo de Steensgaard, que hace un análisis más grueso tratando esencialmente las asignaciones como bidireccionales. Se expresa elegantemente mediante unificación de términos, y por eso se llama análisis de apuntamiento basado en unificación.

Se usa una variable de término ⟦c⟧ por cada celda abstracta —nótese el cambio de significado respecto de la «sección 18.3 · El algoritmo de Andersen»: aquí ⟦c⟧ es una variable de término, no un conjunto— y un constructor de términos ↑t que representa «puntero a t».

Se construyen como mucho dos restricciones de unificación por operación, frente a una por celda abstracta en Andersen. Y los constructores satisfacen el axioma general de igualdad de términos:

El resultado es pt(p) = { t ∈ Cell : ⟦p⟧ = ↑⟦t⟧ }, y se calcula con el algoritmo de unificación por union-find del capítulo «19».

Sobre el mismo programa de la «sección 18.3 · El algoritmo de Andersen», Steensgaard produce:

Menos preciso que Andersen —q ha ganado dos celdas que no le corresponden—, pero obtenido con un algoritmo mucho más rápido. Nótese que la unificación nunca falla aquí, porque sólo hay un constructor de términos, a diferencia del análisis de tipos del capítulo «19».

18.6 El huevo y la gallina interprocedural

En lenguajes con funciones como valores y punteros, las funciones pueden guardarse en el montón, lo que hace difícil hacer análisis de flujo de control antes que el de punteros. Pero también es difícil hacer análisis de punteros interprocedural sin el resultado del de flujo de control. Por ejemplo:

(*x)(x);

usa un valor función accedido por desreferencia y pasa un puntero como argumento.

La solución a este problema del huevo y la gallina es hacer los dos análisis simultáneamente. El algoritmo de Andersen ya es parecido al análisis de flujo de control, así que basta añadirle las restricciones adecuadas. Suponiendo normalizadas todas las llamadas a la forma X = X₀(X₁,…,Xₙ); y todos los retornos a return X;:

• una referencia a una función constante f genera f ∈ ⟦f⟧;
• una llamada calculada genera, para cada definición f(X'₁,…,X'ₙ) { … return X'; }:

Con esto se mantiene la precisión del análisis de flujo de control. Es exactamente la misma restricción del capítulo «17», ahora resuelta a la vez que las de punteros en el mismo sistema.

18.7 Análisis de punteros nulos

Con pt disponible ya se puede definir un análisis que detecte desreferencias nulas: garantizar que *X sólo se ejecuta cuando X no es nulo. Y aquí, a diferencia de los anteriores, el análisis sí es sensible al flujo.

El retículo básico, Null, tiene dos elementos: NN (not null, definitivamente no nulo) abajo y ⊤ (puede ser nulo) arriba. Los estados abstractos son State = Cell → Null.

Para los nodos que no involucran punteros, ⟦v⟧ = JOIN(v). Para una carga:

es decir, el valor de X₁ es el supremo de los valores de todas las celdas a las que X₂ puede apuntar. Ahí es donde se consume el resultado del análisis de apuntamiento. Y para las demás:

X = alloc P:   [[v]] = JOIN(v)[X -> NN, alloc-i -> T]
X1 = &X2:      [[v]] = JOIN(v)[X1 -> NN]
X1 = X2:       [[v]] = JOIN(v)[X1 -> JOIN(v)(X2)]
X = null:      [[v]] = JOIN(v)[X -> T]

La regla del almacenamiento es la interesante, porque hay que modelar el cambio de lo que sea que X₁ apunte, que pueden ser varias celdas abstractas:

Nótese el ⊔: no se sustituye el valor anterior, se une con él. Ésa es la distinción que da nombre a la sección siguiente.

18.8 Actualización fuerte y actualización débil

La razón de que la regla del almacenamiento use ⊔ es doble. Primero, pt(X₁) puede contener varias celdas, y sólo una de ellas se escribe realmente. Segundo, y más sutil: cada celda abstracta alloc-i puede representar muchas celdas concretas, porque el sitio de asignación puede ejecutarse muchas veces.

• Una actualización fuerte (strong update) sustituye el valor antiguo: σ[α ↦ nuevo]. Sólo es correcta si se sabe que se está escribiendo exactamente una celda concreta.
• Una actualización débil (weak update) une el valor nuevo con el antiguo: σ[α ↦ σ(α) ⊔ nuevo]. Siempre es correcta, pero pierde precisión: la celda nunca «olvida» sus valores anteriores.

Se puede hacer actualización fuerte cuando pt(X₁) es un conjunto unitario {α} y α representa una sola celda concreta —típicamente, una variable local en un análisis intraprocedural, o una celda de montón que el análisis haya demostrado única—. En todos los demás casos hay que hacer actualización débil.

18.9 Sensibilidad al flujo y análisis de escape

El análisis de apuntamiento sensible al flujo lleva la idea más lejos: en lugar de una función pt global, calcula una función Cell → ℘(Cell) por cada punto del programa. Es notablemente más preciso y notablemente más caro, y es lo que permite las actualizaciones fuertes de la sección anterior en el caso general.

El análisis de escape (escape analysis) responde a una pregunta distinta: ¿puede un puntero a una celda de la pila sobrevivir a la función que la creó? En TIP basta comprobar si la expresión de retorno puede apuntar a una celda que represente una variable local. Sus dos aplicaciones son opuestas y ambas importantes: en un compilador, permite asignar en la pila objetos que no escapan, evitando el montón; en análisis de seguridad, detecta punteros colgantes, es decir, exactamente lo contrario.

18.10 En binarios

18.11 Lecturas

La conexión con el algoritmo cúbico y con el análisis de flujo de control es la del capítulo «17».

Las referencias originales son Andersen (1994), Steensgaard (1996), Chase, Wegman y Zadeck (1990) para la abstracción por sitio de asignación, y Horwitz (1997) y Chakaravarthy (2003) para los resultados de no optimalidad. La «sección 18.10 · En binarios» se relaciona con Balakrishnan y Reps (2004), ya citados en el capítulo «8».