En informática , el análisis de punteros , o análisis de puntos a , es una técnica de análisis de código estático que establece qué punteros , o referencias de pila, pueden apuntar a qué variables o ubicaciones de almacenamiento. A menudo es 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 hace que el análisis de punteros sea el nombre colectivo tanto para el análisis de puntos a , definido como antes, como para el análisis de alias . Los análisis de puntos a y de alias están estrechamente relacionados pero no siempre equivalen problemas.)
Ejemplo
Para el siguiente programa de ejemplo, un análisis de puntos a calcularía que el conjunto de puntos a p
es { x
, y
}.
int x ; int y ; int * p = desconocido () ? & x : & y ;
Introducción
Como forma de análisis estático, se puede demostrar que el análisis de puntero totalmente preciso es indecidible . [1] La mayoría de los enfoques son sólidos , pero varían ampliamente en rendimiento y precisión. Para programas grandes, pueden ser necesarias algunas compensaciones para que el análisis finalice en un tiempo y espacio razonables. Dos ejemplos de estas compensaciones son: [2]
- Tratar todas las referencias de un objeto estructurado como si fueran del objeto como un todo. Esto se conoce como insensibilidad de campo o insensibilidad de estructura .
- Ignorar el flujo de control al analizar qué objetos se asignan a los punteros. Esto se conoce como análisis de puntero insensible al contexto (cuando se ignora el contexto en el que se realizan las llamadas a la función) o análisis de puntero insensible al flujo (cuando se ignora el flujo de control dentro de un procedimiento).
La desventaja de estas simplificaciones es que el conjunto calculado de objetos apuntados puede volverse menos preciso.
Algoritmos insensibles al contexto, insensibles 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 señalar a otro) en un gráfico útil de lo que cada puntero puede señalar. [3]
El algoritmo de Steensgaard y el algoritmo de Andersen son comunes contexto-insensibles, algoritmos de flujo insensible para el análisis de puntero. A menudo se utilizan en compiladores y tienen implementaciones en la base de código LLVM .
Enfoques insensibles al flujo
Muchos enfoques de análisis de punteros insensibles al flujo pueden entenderse como formas de interpretación abstracta , en las que las asignaciones de montones son abstraídas por su sitio de asignación (es decir, una ubicación de programa). [4]
Muchos algoritmos insensibles al flujo se especifican en Datalog , incluidos los del marco de análisis de hollín para Java. [5]
Los algoritmos sensibles al contexto e insensibles al flujo logran una mayor precisión, generalmente a costa de cierto rendimiento, al analizar cada procedimiento varias veces, una por contexto . [6] 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). [7] Para asegurar la terminación (y más generalmente, la escalabilidad), tales análisis generalmente usan 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. [8] Tres variantes comunes de análisis sensible al contexto e insensible al flujo son: [9]
- Sensibilidad del sitio de llamada
- Sensibilidad al objeto
- Sensibilidad de tipo
Sensibilidad del sitio de llamada
En la sensibilidad del sitio de llamada, el conjunto de puntos a de cada variable (el conjunto de asignaciones de montón abstracto al que podría apuntar cada variable) se califica aún má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 llamadas puede lograr una mayor precisión que un análisis insensible al contexto y al flujo.
int * id ( int * x ) { retorno x ; } int main () { int y ; int z ; int * y2 = id ( & y ); // sitio de llamada 1 int * z2 = id ( & z ); // sitio de llamada 2 return 0 ; }
Para este programa, un análisis insensible al contexto concluiría (de manera sólida pero imprecisa) que x puede apuntar a la asignación que contiene y o la de z , por lo que y2 y z2 pueden alias, y ambos podrían apuntar a cualquiera de las asignaciones. Un análisis sensible al sitio de llamadas analizaría la identificación dos veces, una para el sitio de llamadas 1 y una vez para el sitio de llamadas 2, y los hechos de referencia para x serían calificados por el sitio de llamadas, lo que permitiría al análisis deducir que cuando la principal regresa , y2 solo puede apuntar a la asignación que contiene y y z2 solo puede apuntar a la asignación que contiene z .
Sensibilidad al objeto
En un análisis sensible a objetos, el conjunto de puntos a de cada variable se califica mediante la asignación de montón abstracta del objeto receptor de la llamada al método. A diferencia de la sensibilidad del sitio de llamada, la sensibilidad a los objetos no es sintáctica ni local : las entradas de contexto se derivan durante el análisis de los puntos a. [10]
Sensibilidad de tipo
La sensibilidad de tipo es una variante de la sensibilidad del objeto en la que 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. [11] 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
- ↑ Representantes, Thomas (1 de enero de 2000). "Indecidibilidad del análisis de dependencia de datos sensibles al contexto" . Transacciones ACM sobre lenguajes y sistemas de programación . 22 (1): 162–186. doi : 10.1145 / 345099.345137 . ISSN 0164-0925 . S2CID 2956433 .
- ^ Barbara G. Ryder (2003). "Dimensiones de precisión en el análisis de referencia de lenguajes de programación orientados a objetos". Compiler Construction, 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 al 11 de abril de 2003 Actas . págs. 126-137. doi : 10.1007 / 3-540-36579-6_10 .
- ^ 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.
- ^ Smaragdakis, Yannis; Bravenboer, Martin; Lhoták, Ondrej (26 de enero de 2011). "Elija bien sus contextos: comprensión de la sensibilidad a los objetos" . Actas del 38º Simposio anual ACM SIGPLAN-SIGACT sobre principios de lenguajes de programación . POPL '11. Austin, Texas, Estados Unidos: Asociación de Maquinaria de Computación: 17–30. doi : 10.1145 / 1926385.1926390 . ISBN 978-1-4503-0490-0. S2CID 6451826 .
- ^ Antoniadis, Tony; Triantafyllou, Konstantinos; Smaragdakis, Yannis (18 de junio de 2017). "Porting doop a Soufflé: una historia de portabilidad entre motores para análisis basados en registros de datos" . Actas del VI Taller Internacional ACM SIGPLAN sobre el estado del arte en el análisis de programas . SOAP 2017. Barcelona, España: Asociación de Maquinaria Informática: 25–30. doi : 10.1145 / 3088515.3088522 . ISBN 978-1-4503-5072-3. S2CID 3074689 .
- ↑ ( Smaragdakis y Balatsouras , p. 29)
- ^ 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 .
- ^ ( Li et al. , Págs. 1: 4)
- ^ ( Smaragdakis y Balatsouras )
- ↑ ( Smaragdakis y Balatsouras , p. 37)
- ↑ ( Smaragdakis y Balatsouras , p. 39)
Bibliografía
- 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.
- Smaragdakis, Yannis; Balatsouras, George (2015). "Análisis de puntero" (PDF) . Fundamentos y tendencias en lenguajes de programación . 2 (1): 1–69. doi : 10.1561 / 2500000014 . Consultado el 30 de mayo de 2019 .
- Li, Yue; Tan /, Tian; Møller, Anders; Smaragdakis, Yannis (18 de mayo de 2020). "Un enfoque basado en principios para la sensibilidad selectiva al contexto para el análisis de punteros" . Transacciones ACM sobre lenguajes y sistemas de programación . 42 (2): 10: 1–10: 40. doi : 10.1145 / 3381915 . ISSN 0164-0925 . S2CID 214812357 .
- Michael Hind (2001). "Análisis de punteros: ¿no hemos resuelto todavía este problema?" (PDF) . PASTE '01: Actas del taller ACM SIGPLAN-SIGSOFT 2001 sobre Análisis de programas para herramientas e ingeniería de software . ACM. págs. 54–61. ISBN 1-58113-413-4.
- Steensgaard, Bjarne (1996). "Análisis por puntos en tiempo casi lineal" (PDF) . POPL '96: Actas del 23º simposio ACM SIGPLAN-SIGACT sobre Principios de lenguajes de programación . Nueva York, NY, EE.UU .: ACM. págs. 32–41. doi : 10.1145 / 237721.237727 . ISBN 0-89791-769-3.
- Andersen, Lars Ole (1994). Análisis y especialización del programa para el lenguaje de programación C (PDF) (tesis doctoral).