Gráfico de llamadas

Estructura en la informática

Un gráfico de llamadas (también conocido como multigráfico de llamadas ^[1]^[2] ) es un gráfico de flujo de control [ ^3] que representa relaciones de llamadas entre subrutinas en un programa informático . Cada nodo representa un procedimiento y cada arista (f, g) indica que el procedimiento f llama al procedimiento g . Por lo tanto, un ciclo en el gráfico indica llamadas a procedimientos recursivos.

Conceptos básicos

Los gráficos de llamadas pueden ser dinámicos o estáticos. ^[4] Un gráfico de llamadas dinámico es un registro de una ejecución del programa, por ejemplo, como salida de un generador de perfiles. Por lo tanto, un gráfico de llamadas dinámico puede ser exacto, pero solo describe una ejecución del programa. Un gráfico de llamadas estático es un gráfico de llamadas destinado a representar cada ejecución posible del programa. El gráfico de llamadas estático exacto es un problema indecidible , por lo que los algoritmos de gráficos de llamadas estáticos son generalmente sobreaproximaciones. Es decir, cada relación de llamadas que ocurre se representa en el gráfico, y posiblemente también algunas relaciones de llamadas que nunca ocurrirían en ejecuciones reales del programa.

Los gráficos de llamadas se pueden definir para representar distintos grados de precisión. Un gráfico de llamadas más preciso se aproxima con mayor precisión al comportamiento del programa real, a costa de tardar más en calcularse y de necesitar más memoria para almacenarse. El gráfico de llamadas más preciso es totalmente sensible al contexto , lo que significa que, para cada procedimiento, el gráfico contiene un nodo independiente para cada pila de llamadas con la que se puede activar el procedimiento. Un gráfico de llamadas totalmente sensible al contexto se denomina árbol de contexto de llamada. Esto se puede calcular de forma dinámica con facilidad, aunque puede ocupar una gran cantidad de memoria. Los árboles de contexto de llamada normalmente no se calculan de forma estática, porque llevaría demasiado tiempo para un programa grande. El gráfico de llamadas menos preciso es insensible al contexto , lo que significa que solo hay un nodo para cada procedimiento.

En el caso de lenguajes que cuentan con distribución dinámica (por ejemplo, Java o C++ ), ^[5] funciones de primera clase (por ejemplo, Python o Racket ) o punteros de función (por ejemplo, C ), el cálculo preciso de un gráfico de llamadas estático requiere resultados de análisis de alias . Por el contrario, el cálculo preciso de alias requiere un gráfico de llamadas. Muchos sistemas de análisis estático resuelven la regresión infinita aparente calculando ambos simultáneamente.

Usos

Los gráficos de llamadas se pueden utilizar de diferentes maneras. Una aplicación sencilla de los gráficos de llamadas es encontrar procedimientos que nunca se llaman. Los gráficos de llamadas pueden actuar como documentación para que los humanos comprendan los programas . ^[6] Los gráficos de llamadas también se pueden utilizar para detectar anomalías en la ejecución de programas o ataques de inyección de código. ^[7]

Software

Software libregeneradores de gráficos de llamadas

Gráfico de llamadas en tiempo de ejecución (la mayoría de las herramientas enumeradas son perfiladores con funcionalidad de gráfico de llamadas)

gprof : incluido en BSD o parte de las utilidades binarias de GNU
callgrind: parte de Valgrind
KCachegrind: poderosa herramienta para generar y analizar gráficos de llamadas basados en datos generados por callgrind
Monitor de actividad de Mac OS X: monitor de procesos de la interfaz gráfica de usuario de Apple El Monitor de actividad tiene un generador de gráficos de llamadas integrado que puede muestrear procesos y devolver un gráfico de llamadas. Esta función solo está disponible en Mac OS X Leopard
OpenPAT: incluye la control_flowherramienta que crea automáticamente una imagen del gráfico de llamadas Graphviz a partir de las mediciones en tiempo de ejecución.
pprof, herramienta de código abierto para visualización y análisis de datos de perfil, para ser utilizada junto con gperftools.
CodeAnalyst de AMD (publicado bajo GPL)
makeppgraph es un generador de gráficos de dependencia (a nivel de módulo) para compilaciones realizadas con makepp .
API de evento único Intel(R) (gratuita, de código abierto)

Estático para obtener gráficos de llamadas sin ejecutar la aplicación

C/C++

Sourcetrail crea un gráfico de llamadas estático que el usuario puede explorar de forma dinámica. También es compatible con Python y Java.
doxygen : utiliza Graphviz para generar diagramas de herencia/llamada estáticos
Cally: una herramienta que utiliza archivos de lenguaje de transferencia de registros (RTL) de GCC para crear gráficos de llamadas de llamador o de destinatario para proyectos C.
cflow : GNU cflow puede generar el gráfico de llamadas directas e invertidas de un programa C
Egipto: un pequeño script de Perl que utiliza gcc y Graphviz para generar el gráfico de llamadas estáticas de un programa C.
Analizo: calcula métricas del código fuente, genera gráficos de dependencia.
CCTree: complemento nativo de Vim que puede mostrar gráficos de llamadas estáticas mediante la lectura de una base de datos cscope . Funciona con programas C.
codeviz: generador de gráficos de llamadas estáticas (el programa no se ejecuta). Implementado como parche para gcc ; funciona para programas C y C++.
calltree.sh: funciones de shell Bash que unen cscope, graphviz y una muestra de herramientas de representación de puntos para mostrar las relaciones entre "llamador" y "llamado" arriba, abajo y/o entre las funciones C que usted especifique.
tceetree: al igual que calltree.sh, conecta Cscope y Graphviz , pero es un ejecutable en lugar de un script bash.

Ir

go-callvis: un generador de gráficos de llamadas interactivo para programas Go cuya salida se puede dibujar con Graphviz

Multi-idioma

callGraph: generador de gráficos de llamadas de código abierto para awk, bash, basic, dart, fortran, go, lua, javascript, julia, kotlin, matlab, perl, pascal, php, python, R, raku, ruby, rust, scala, swift, tcl y typescript.

.NETO

NDepend : es una herramienta de análisis estático para código .NET. Esta herramienta admite una gran cantidad de métricas de código y permite la visualización de dependencias mediante gráficos dirigidos y matrices de dependencia.

PHP, Perl y Python

Devel::NYTProf: un analizador de rendimiento de Perl y generador de gráficos de llamadas
phpCallGraph: un generador de gráficos de llamadas para programas PHP que utiliza Graphviz . Está escrito en PHP y requiere al menos PHP 5.2.
pycallgraph Archivado el 25 de mayo de 2007 en Wayback Machine : un generador de gráficos de llamadas para programas Python que utiliza Graphviz .
pyan: un generador de gráficos de llamadas estáticos para programas Python que utiliza Graphviz .
gprof2dot: un generador de gráficos de llamadas escrito en Python que convierte datos de creación de perfiles para muchos lenguajes/tiempos de ejecución en un gráfico de llamadas de Graphviz .
code2flow: un generador de gráficos de llamadas para programas Python y Javascript que utiliza Graphviz
rcviz: módulo de Python para representar gráficos de llamadas generados en tiempo de ejecución con Graphviz . Cada nodo representa una invocación de una función con los parámetros que se le pasan y el valor de retorno.

Consulta X

Gráficos de llamadas XQuery del Wikilibro XQuery: un generador de gráficos de llamadas para un módulo de función XQuery que utiliza Graphviz

Generadores de gráficos de llamadas propietarios

Banco de pruebas LDRA: Motores de análisis estático y dinámico tanto para software host como integrado, con una gran variedad de informes que incluyen gráficos de llamadas.
Analizador de proyectos: Analizador de código estático y generador de gráficos de llamadas para código de Visual Basic
Experto visual: Analizador de código estático y generador de gráficos de llamadas para código Oracle PL/SQL , SQLServer Transact-SQL , C# y PowerBuilder
Analizador de rendimiento Intel VTune: Instrumentación del generador de perfiles para mostrar gráficos de llamadas y estadísticas de ejecución
Kit de herramientas de reingeniería de software DMS: Herramienta de análisis de programas personalizable con extracción de gráficos de llamadas globales de todo el programa estático para C, Java y COBOL

Otras herramientas relacionadas

Visualización gráfica: Convierte una representación de texto de cualquier gráfico (incluido un gráfico de llamadas) en una imagen.
clasificación: Utilidad de línea de comandos que realiza una ordenación topológica.

Gráfico de muestra

Un gráfico de llamadas de muestra generado a partir del análisis de gprof a sí mismo:

índice llamado nombre |índice llamado nombre 72384/72384 análisis de id_de_sim [54] | 1508/1508 cg_dfn [15][3] 72384 coincidencias [3] |[13] 1508 visitas previas [13]---------------------- |---------------------- 4/9052 cg_tally [32] | 1508/1508 cg_assemble [38] 3016/9052 hist_print [49] |[14] 1508 tiempo_de_propagación [14] 6032/9052 propagar_banderas [52] |----------------------[4] 9052 búsqueda_de_símbolo [4] | 2 cg_dfn [15]---------------------- | 1507/1507 cg_assemble[38] 5766/5766 función de creación de núcleo_syms [41]|[15] 1507+2 cg_dfn [15][5] 5766 core_sym_class [5] | 1509/1509 está numerado [9]---------------------- | 1508/1508 está_ocupado[11] 24/1537 parse_spec [19] | 1508/1508 pre_visita [13] 1513/1537 función de creación de núcleos_syms [41]| 1508/1508 visita posterior [12][6] 1537 sym_init [6] | 2 cg_dfn [15]---------------------- |---------------------- 1511/1511 función_de_creación_core_syms [41]| 1505/1505 hist_print [49][7] 1511 obtener_información_de_origen [7] |[16] 1505 imprimir_línea [16]---------------------- | 2/9 imprimir_solo_nombre [25] 2/1510 arco_add[31] |---------------------- 1508/1510 cg_assemble [38] | 1430/1430 función de creación de núcleo_syms [41][8] 1510 arc_lookup [8] |[17] 1430 ruta_de_búsqueda_del_archivo_de_origen [17]---------------------- |---------------------- 1509/1509 cg_dfn [15] | 24/24 análisis de id_de_símbolo [54][9] 1509 está numerado [9] |[18] 24 parse_id [18]---------------------- | especificación de análisis 24/24 [19] 1508/1508 propagar_banderas [52] |----------------------[10] 1508 indicadores heredados [10] | 24/24 id de análisis [18]---------------------- |[19] 24 especificación_de_análisis [19] 1508/1508 cg_dfn [15] | 24/1537 sym_init [6][11] 1508 está ocupado [11] |-------------------------------------------- | 24/24 principal [1210] 1508/1508 cg_dfn [15] |[20] 24 id_de_symbolso [20][12] 1508 post_visita [12] |

Véase también

Referencias

^ Callahan, D.; Carle, A.; Hall, MW ; Kennedy, K. (abril de 1990). "Construcción del multigrafo de llamadas a procedimientos". IEEE Transactions on Software Engineering . 16 (4): 483–487. doi :10.1109/32.54302.
^ Uday Khedker; Amitabha Sanyal; Bageshri Sathe (2009). Análisis del flujo de datos: teoría y práctica . CRC Press. pág. 234. ISBN 978-0-8493-3251-7.
^ Pankaj Jalote (1997). Un enfoque integrado de la ingeniería de software . Springer Science & Business Media. pág. 372. ISBN 978-0-387-94899-7.
^ Ryder, BG (mayo de 1979). "Construcción del gráfico de llamadas de un programa". IEEE Transactions on Software Engineering . SE-5 (3): 216–226. doi :10.1109/tse.1979.234183. S2CID 16527042.
^ Grove, David; DeFouw, Greg; Dean, Jeffrey; Chambers, Craig; Grove, David; DeFouw, Greg; Dean, Jeffrey; Chambers, Craig (9 de octubre de 1997). "Construcción de grafos de llamadas en lenguajes orientados a objetos". Avisos SIGPLAN de la ACM . 32 (10). ACM: 108, 108–124, 124. doi : 10.1145/263700.264352 .
^ Eisenbarth, T.; Koschke, R.; Simon, D. (2001). "Ayuda a la comprensión de programas mediante análisis de características estáticas y dinámicas". Actas de la Conferencia Internacional IEEE sobre Mantenimiento de Software. ICSM 2001. págs. 602–611. doi :10.1109/icsm.2001.972777. ISBN 0-7695-1189-9. Número de identificación del sujeto 5934718.
^ Gao, Debin; Reiter, Michael K.; Song, Dawn (25 de octubre de 2004). "Extracción de caja gris de gráficos de ejecución para la detección de anomalías". Actas de la 11.ª conferencia de la ACM sobre seguridad informática y de las comunicaciones - CCS '04. ACM. págs. 318–329. doi :10.1145/1030083.1030126. ISBN 1581139616.S2CID1189805 .

[1] Callahan, D.; Carle, A.; Hall, MW ; Kennedy, K. (abril de 1990). "Construcción del multigrafo de llamadas a procedimientos". IEEE Transactions on Software Engineering . 16 (4): 483–487. doi :10.1109/32.54302.

[KhedkerSanyal2009-2] Uday Khedker; Amitabha Sanyal; Bageshri Sathe (2009). Análisis del flujo de datos: teoría y práctica . CRC Press. pág. 234. ISBN 978-0-8493-3251-7.

[Jalote1997-3] Pankaj Jalote (1997). Un enfoque integrado de la ingeniería de software . Springer Science & Business Media. pág. 372. ISBN 978-0-387-94899-7.

[4] Ryder, BG (mayo de 1979). "Construcción del gráfico de llamadas de un programa". IEEE Transactions on Software Engineering . SE-5 (3): 216–226. doi :10.1109/tse.1979.234183. S2CID 16527042.

[:0-5] Grove, David; DeFouw, Greg; Dean, Jeffrey; Chambers, Craig; Grove, David; DeFouw, Greg; Dean, Jeffrey; Chambers, Craig (9 de octubre de 1997). "Construcción de grafos de llamadas en lenguajes orientados a objetos". Avisos SIGPLAN de la ACM . 32 (10). ACM: 108, 108–124, 124. doi : 10.1145/263700.264352 .

[6] Eisenbarth, T.; Koschke, R.; Simon, D. (2001). "Ayuda a la comprensión de programas mediante análisis de características estáticas y dinámicas". Actas de la Conferencia Internacional IEEE sobre Mantenimiento de Software. ICSM 2001. págs. 602–611. doi :10.1109/icsm.2001.972777. ISBN 0-7695-1189-9. Número de identificación del sujeto 5934718.

[7] Gao, Debin; Reiter, Michael K.; Song, Dawn (25 de octubre de 2004). "Extracción de caja gris de gráficos de ejecución para la detección de anomalías". Actas de la 11.ª conferencia de la ACM sobre seguridad informática y de las comunicaciones - CCS '04. ACM. págs. 318–329. doi :10.1145/1030083.1030126. ISBN 1581139616.S2CID1189805 .