gráfico de llamadas

Un gráfico de llamadas (también conocido como multigrafo de llamadas ^[1]^[2] ) es un gráfico de flujo de control , ^[3] que representa relaciones de llamadas entre subrutinas en un programa de computadora . Cada nodo representa un procedimiento y cada borde (f, g) indica que el procedimiento f llama al procedimiento g . Por 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ámicas es un registro de una ejecución del programa, por ejemplo, como resultado de un generador de perfiles. Por lo tanto, un gráfico de llamadas dinámicas 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áticas exacto es un problema indecidible , por lo que los algoritmos de gráficos de llamadas estáticas son generalmente sobreaproximaciones. Es decir, cada relación de llamada que ocurre está representada en el gráfico, y posiblemente también algunas relaciones de llamada 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 tomar más tiempo para calcular y más memoria para almacenar. 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 separado para cada pila de llamadas con la que se puede activar ese procedimiento. Un gráfico de llamadas totalmente sensible al contexto se denomina árbol de contexto de llamadas. Esto se puede calcular dinámicamente fácilmente, aunque puede ocupar una gran cantidad de memoria. Los árboles de contexto de llamada generalmente no se calculan estáticamente, porque llevaría demasiado tiempo para un programa grande. El gráfico de llamadas menos preciso no tiene en cuenta el contexto , lo que significa que solo hay un nodo para cada procedimiento.

Con lenguajes que cuentan con despacho dinámico (es decir, Java o C++ ), ^[5] funciones de primera clase (es decir, Python o Racket ) o punteros de función (es decir, C ), calcular un gráfico de llamadas estáticas requiere precisamente resultados de análisis de alias . Por el contrario, calcular el alias preciso requiere un gráfico de llamadas. Muchos sistemas de análisis estático resuelven la aparente regresión infinita calculando ambas 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

Generadores de gráficos de llamadas de software gratuito

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

gprof : incluido en BSD o parte de GNU Binary Utilities
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 GUI de Apple Activity Monitor tiene un generador de gráficos de llamadas incorporado que puede muestrear procesos y devolver un gráfico de llamadas. Esta función sólo está disponible en Mac OS X Leopard
OpenPAT: incluye la control_flowherramienta que crea automáticamente una imagen de gráfico de llamadas Graphviz a partir de mediciones de 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 Intel(R) de evento único (gratis, 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 dinámicamente. También es compatible con Python y Java
doxygen : utiliza Graphviz para generar diagramas estáticos de llamada/herencia
Cally: una herramienta que utiliza archivos de lenguaje de transferencia de registros (RTL) de GCC para crear gráficos de llamadas de personas que llaman o llamadas para proyectos en C.
cflow : GNU cflow es capaz de generar el gráfico de llamadas directa e invertida de un programa en C.
Egipto: un pequeño script en Perl que utiliza gcc y Graphviz para generar el gráfico de llamadas estáticas de un programa en 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 leyendo una base de datos cscope . Funciona para programas C.
codeviz: un generador de gráficos de llamadas estáticas (el programa no se ejecuta). Implementado como un 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 de "llamador" y "llamado" arriba, abajo y/o entre las funciones C que 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 lenguaje

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 mecanografiado.

.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, permite la visualización de dependencias mediante gráficos dirigidos y una matriz de dependencia.

PHP, Perl y Python

Devel::NYTProf: un analizador de rendimiento de Perl y un 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 usa Graphviz .
pyan: un generador de gráficos de llamadas estáticas para programas Python que usa Graphviz .
gprof2dot: un generador de gráficos de llamadas escrito en Python que convierte datos de perfiles para muchos lenguajes/tiempos de ejecución en un gráfico de llamadas Graphviz .
code2flow: un generador de gráficos de llamadas para programas Python y Javascript que usa 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.

XQuery

XQuery Call Graphs del XQuery Wikibook: un generador de gráficos de llamadas para un módulo de funciones XQuery que usa Graphviz

Generadores de gráficos de llamadas propietarios

Banco de pruebas LDRA: Motores de análisis estáticos y dinámicos para software host e 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 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: Generador de perfiles de instrumentación 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 estática de gráficos de llamadas globales de todo el programa para C, Java y COBOL

Otras herramientas relacionadas

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

Gráfico de muestra

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

índice llamado nombre | índice llamado nombre 72384/72384 sym_id_parse [54] | 1508/1508 cg_dfn[15][3] 72384 coincidencia [3] |[13] 1508 visita previa [13]---------------------- |---------------------- 4/9052 cg_tally [32] | 1508/1508 cg_ensamblar [38] 3016/9052 hist_print [49] |[14] 1508 propagate_time [14] 6032/9052 propagar_flags [52] |----------------------[4] 9052 búsqueda_sim [4] | 2cg_dfn [15]---------------------- | 1507/1507 cg_ensamblar [38] 5766/5766 core_create_function_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 visita previa [13] 1513/1537 core_create_function_syms [41]| 1508/1508 post_visita [12][6] 1537 sym_init [6] | 2cg_dfn [15]---------------------- |---------------------- 1511/1511 core_create_function_syms [41]| 1505/1505 hist_print [49][7] 1511 get_src_info [7] |[16] 1505 print_line [16]---------------------- | 2/9 imprimir_nombre_solo [25] 2/1510 arc_add [31] |---------------------- 1508/1510 cg_ensamblaje [38] | 1430/1430 core_create_function_syms [41][8] 1510 búsqueda_arco [8] |[17] 1430 ruta_búsqueda_archivo_fuente [17]---------------------- |---------------------- 1509/1509 cg_dfn [15] | 24/24 sym_id_parse [54][9] 1509 está_numerado [9] |[18] 24 parse_id [18]---------------------- | 24/24 parse_spec [19] 1508/1508 propagar_flags [52] |----------------------[10] 1508 banderas_heredadas [10] | 24/24 parse_id [18]---------------------- |[19] 24 parse_spec [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 sym_id_add [20][12] 1508 post_visita [12] |

Ver también

Referencias

^ Callahan, D.; Carlé, A.; Hall, MW ; Kennedy, K. (abril de 1990). "Construcción del multigrafo de llamada a procedimiento". Transacciones IEEE sobre ingeniería de software . 16 (4): 483–487. doi : 10.1109/32.54302.
^ Uday Khedker; Amitabha Sanyal; Bageshri Sathe (2009). Análisis de flujo de datos: teoría y práctica . Prensa CRC. pag. 234.ISBN _ 978-0-8493-3251-7.
^ Pankaj Jalote (1997). Un enfoque integrado de la ingeniería de software . Medios de ciencia y negocios de Springer. pag. 372.ISBN _ 978-0-387-94899-7.
^ Ryder, BG (mayo de 1979). "Construcción del gráfico de llamadas de un programa". Transacciones IEEE sobre ingeniería de software . SE-5 (3): 216–226. doi :10.1109/tse.1979.234183. S2CID 16527042.
^ Arboleda, David; DeFouw, Greg; Decano, Jeffrey; Cámaras, Craig; Arboleda, David; DeFouw, Greg; Decano, Jeffrey; Chambers, Craig (9 de octubre de 1997). "Construcción de gráficos de llamadas en lenguajes orientados a objetos". Avisos ACM SIGPLAN . ACM. 32 (10): 108, 108–124, 124. doi : 10.1145/263700.264352 .
^ Eisenbarth, T.; Koschke, R.; Simón, D. (2001). "Ayudar a la comprensión del programa mediante análisis de características estáticas y dinámicas". Actas de la Conferencia internacional IEEE sobre mantenimiento de software. CISM 2001 . págs. 602–611. doi : 10.1109/icsm.2001.972777. ISBN 0-7695-1189-9. S2CID 5934718.
^ Gao, Debin; Reiter, Michael K.; Canción, amanecer (25 de octubre de 2004). "Extracción de cuadro gris de gráficos de ejecución para detección de anomalías". Actas de la undécima conferencia ACM sobre seguridad informática y de las comunicaciones - CCS '04. ACM. págs. 318–329. doi :10.1145/1030083.1030126. ISBN 1581139616. S2CID 1189805.