stringtranslate.com

Análisis de punteros

En informática , el análisis de punteros o análisis de puntos a los que apuntar es una técnica de análisis de código estático que establece qué punteros o referencias de montón pueden apuntar a qué variables o ubicaciones de almacenamiento . Suele ser un componente de análisis más complejos, como el análisis de escape . Una técnica estrechamente relacionada es el análisis de formas .

Este es el uso coloquial más común del término. Un uso secundario es el análisis de punteros , que es el nombre colectivo tanto para el análisis de puntos a , definido como se describió anteriormente, como para el análisis de alias . El análisis de puntos a y el análisis de alias son problemas estrechamente relacionados, pero no siempre equivalentes.

Ejemplo

Considere el siguiente programa en C:

int * id ( int * p ) { devolver p ; } void main ( void ) { int x ; int y ; int * u = id ( & x ); int * v = id ( & y ); }

Un análisis de punteros calcula una asignación de expresiones de punteros a un conjunto de sitios de asignación de objetos a los que pueden apuntar. Para el programa anterior, un análisis idealizado y totalmente preciso calcularía los siguientes resultados:

(Donde X::Yrepresenta la asignación de pila que contiene la variable local Yen la función X).

Sin embargo, un análisis insensible al contexto como el algoritmo de Andersen o Steensgaard perdería precisión al analizar las llamadas a idy calcularía el siguiente resultado:

Introducción

Como forma de análisis estático, se puede demostrar que el análisis de punteros totalmente preciso es indecidible . [1] La mayoría de los enfoques son sólidos , pero varían ampliamente en rendimiento y precisión. Muchas decisiones de diseño afectan tanto la precisión como el rendimiento de un análisis; a menudo (pero no siempre) una precisión menor produce un rendimiento mayor. Estas opciones incluyen: [2] [3]

Algoritmos insensibles al contexto y al flujo

Los algoritmos de análisis de punteros se utilizan para convertir los usos de punteros sin procesar recopilados (asignaciones de un puntero a otro o asignación de un puntero para apuntar a otro) en un gráfico útil de lo que cada puntero puede apuntar. [4]

El algoritmo de Steensgaard y el algoritmo de Andersen son algoritmos comunes que no son sensibles al contexto ni al flujo para el análisis de punteros. Se utilizan a menudo en compiladores y tienen implementaciones en SVF [5] y LLVM .

Enfoques insensibles al flujo

Muchos enfoques para el análisis de punteros insensibles al flujo pueden entenderse como formas de interpretación abstracta , donde las asignaciones de montón se abstraen por su sitio de asignación (es decir, una ubicación de programa). [6]

Un diagrama que muestra cómo el análisis de punteros abstrae la memoria en tiempo de ejecución
Los análisis de punteros que no tienen en cuenta el flujo suelen abstraer las posibles asignaciones en tiempo de ejecución por su sitio de asignación. En tiempo de ejecución, este programa crea tres asignaciones de montón independientes. Un análisis de punteros que no tiene en cuenta el flujo las trataría como una única ubicación de memoria abstracta, lo que provocaría una pérdida de precisión.

En Datalog se especifican muchos algoritmos insensibles al flujo , incluidos aquellos en el marco de análisis Soot para Java. [7]

Los algoritmos sensibles al contexto y al flujo logran una mayor precisión, generalmente a costa de cierto rendimiento, al analizar cada procedimiento varias veces, una vez por contexto . [8] La mayoría de los análisis utilizan un enfoque de "cadena de contexto", donde los contextos consisten en una lista de entradas (las opciones comunes de entrada de contexto incluyen sitios de llamada, sitios de asignación y tipos). [9] Para garantizar la terminación (y, de manera más general, la escalabilidad), dichos análisis generalmente utilizan un enfoque de limitación k , donde el contexto tiene un tamaño máximo fijo y los elementos agregados menos recientemente se eliminan según sea necesario. [10] Tres variantes comunes de análisis sensibles al contexto e insensibles al flujo son: [11]

Sensibilidad del sitio de llamada

En la sensibilidad del sitio de llamada, el conjunto de puntos de cada variable (el conjunto de asignaciones de montón abstractas a las que cada variable podría apuntar) se califica además mediante un contexto que consiste en una lista de sitios de llamada en el programa. Estos contextos abstraen el flujo de control del programa.

El siguiente programa demuestra cómo la sensibilidad del sitio de llamada puede lograr una mayor precisión que un análisis insensible al flujo y al contexto.

int * id ( int * p ) { devolver p ; } void main ( void ) { int x ; int y ; int * u = id ( & x ); // principal.3 int * v = id ( & y ); // principal.4 }

Para este programa, un análisis insensible al contexto concluiría (de manera sólida pero imprecisa) que p puede apuntar a la asignación que contiene x o a la de y , por lo que u y v pueden tener alias, y ambos podrían apuntar a cualquiera de las asignaciones:

Un análisis sensible al sitio de llamada analizaría id dos veces, una para main.3y otra para main.4, y los hechos que apuntan a p serían calificados por el sitio de llamada, lo que permite que el análisis deduzca que cuando main retorna, u solo puede apuntar a la asignación que contiene x y v solo puede apuntar a la asignación que contiene y :

Sensibilidad del objeto

En un análisis sensible a objetos, el conjunto de puntos a los que apunta cada variable se califica mediante la asignación de montón abstracto del objeto receptor de la llamada al método. A diferencia de la sensibilidad al sitio de la llamada, la sensibilidad a objetos no es sintáctica ni local : las entradas de contexto se derivan durante el análisis de puntos a los que apunta. [12]

Sensibilidad de tipo

La sensibilidad de tipo es una variante de la sensibilidad de objeto donde el sitio de asignación del objeto receptor se reemplaza por la clase/tipo que contiene el método que contiene el sitio de asignación del objeto receptor. [13] Esto da como resultado estrictamente menos contextos de los que se usarían en un análisis sensible a objetos, lo que generalmente significa un mejor rendimiento.

Referencias

  1. ^ Reps, Thomas (1 de enero de 2000). "Indecidibilidad del análisis de dependencia de datos sensible al contexto". ACM Transactions on Programming Languages ​​and Systems . 22 (1): 162–186. doi : 10.1145/345099.345137 . ISSN  0164-0925. S2CID  2956433.
  2. ^ Barbara G. Ryder (2003). "Dimensiones de precisión en el análisis de referencia de lenguajes de programación orientados a objetos". Construcción de compiladores, 12.ª conferencia internacional, CC 2003 celebrada como parte de las conferencias europeas conjuntas sobre teoría y práctica del software, ETAPS 2003 Varsovia, Polonia, 7-11 de abril de 2003 Actas . págs. 126-137. doi : 10.1007/3-540-36579-6_10 .
  3. ^ (posterior)
  4. ^ Zyrianov, Vlas; Newman, Christian D.; Guarnera, Drew T.; Collard, Michael L.; Maletic, Jonathan I. (2019). "srcPtr: Un marco para implementar enfoques de análisis de puntero estático" (PDF) . ICPC '19: Actas de la 27.ª Conferencia Internacional IEEE sobre Comprensión de Programas . Montreal, Canadá: IEEE.
  5. ^ Sui, Yulei; Xue, Jingling (2016). "SVF: análisis de flujo de valor estático interprocedimental en LLVM" (PDF) . CC'16: Actas de la 25.ª conferencia internacional sobre construcción de compiladores . ACM.
  6. ^ Smaragdakis, Yannis; Bravenboer, Martin; Lhoták, Ondrej (26 de enero de 2011). "Seleccione bien sus contextos". Actas del 38.º simposio anual ACM SIGPLAN-SIGACT sobre principios de lenguajes de programación . POPL '11. Austin, Texas, EE. UU.: Association for Computing Machinery. págs. 17–30. doi :10.1145/1926385.1926390. ISBN 978-1-4503-0490-0.S2CID6451826  .​
  7. ^ Antoniadis, Tony; Triantafyllou, Konstantinos; Smaragdakis, Yannis (18 de junio de 2017). "Transferencia de doop a Soufflé". Actas del 6.º Taller internacional ACM SIGPLAN sobre el estado del arte en análisis de programas . SOAP 2017. Barcelona, ​​España: Association for Computing Machinery. págs. 25–30. doi :10.1145/3088515.3088522. ISBN . 978-1-4503-5072-3. Número de identificación del sujeto  3074689.
  8. ^ (Smaragdakis y Balatsouras, pág.29)
  9. ^ Thiessen, Rei; Lhoták, Ondřej (14 de junio de 2017). "Transformaciones de contexto para análisis de punteros". Avisos ACM SIGPLAN . 52 (6): 263–277. doi :10.1145/3140587.3062359. ISSN  0362-1340.
  10. ^ (Li y otros, págs. 1:4)
  11. ^ (Smaragdakis y Balatsouras)
  12. ^ (Smaragdakis y Balatsouras, pág.37)
  13. ^ (Smaragdakis y Balatsouras, pág.39)

Bibliografía