Un gráfico de llamadas (también conocido como multigraph de llamadas [1] [2] ) es un gráfico de flujo de control , [3] que representa las 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 de procedimiento recursivas.
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 posible ejecución 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 se produce se representa en el gráfico y posiblemente también algunas relaciones de llamada que nunca ocurrirían en las 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 calcular y más memoria en 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 el que se puede activar el 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 tomaría demasiado tiempo para un programa grande. El gráfico de llamadas menos preciso no es sensible al contexto , lo que significa que solo hay un nodo para cada procedimiento.
Con lenguajes que cuentan con despacho dinámico , como Java y C ++ , calcular un gráfico de llamadas estáticas requiere precisamente resultados de análisis de alias . [5] Por el contrario, el cálculo de un alias preciso requiere un gráfico de llamadas. Muchos sistemas de análisis estático resuelven la aparente regresión infinita calculando ambos simultáneamente.
Usos
Los gráficos de llamadas se pueden utilizar de diferentes formas. Una aplicación simple 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] También pueden servir como base para análisis adicionales, como un análisis que rastrea el flujo de valores entre los procedimientos o la predicción del impacto del cambio . [7] Los gráficos de llamadas también se pueden utilizar para detectar anomalías en la ejecución del programa o ataques de inyección de código. [8]
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 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 proceso de la GUI de Apple Monitor de actividad tiene un generador de gráfico de llamadas incorporado 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_flow
herramienta que crea automáticamente una imagen de gráfico de llamadas Graphviz a partir de mediciones en tiempo de ejecución. - pprof , herramienta de código abierto para la visualización y análisis de datos de perfil, que se utilizará 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 dinámicamente. También es compatible con Python y Java.
- doxygen : utiliza Graphviz para generar diagramas de herencia / llamada estática
- cflow : GNU cflow puede generar el gráfico de llamadas directo e invertido de un programa en C
- egypt : un pequeño script en Perl que usa gcc y Graphviz para generar el gráfico de llamadas estáticas de un programa en C.
- Analizo : calcula métricas de 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áfico de llamadas estático (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 "llamador" y "destinatario" arriba, abajo y / o entre las funciones de C que especifique.
- tceetree : como calltree.sh, conecta Cscope y Graphviz , pero es un ejecutable en lugar de un script bash.
- Ir
- go-callvis : un generador interactivo de gráficos de llamadas 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, 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 utilizando gráficos dirigidos y 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 usa Graphviz . Está escrito en PHP y requiere al menos PHP 5.2.
- pycallgraph : 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 los datos de creación 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
- Gráficos de llamadas de XQuery del Wikibook de XQuery : un generador de gráficos de llamadas para un módulo de funciones de XQuery que usa Graphviz
Generadores de gráficos de llamadas patentados
- Analizador de proyectos
- Analizador de código estático y generador de gráfico de llamadas para código Visual Basic
- Experto visual
- Analizador de código estático y gráfico de llamadas generador para Oracle PL / SQL , SQL Server Transact-SQL , C # y PowerBuilder código
- Analizador de rendimiento Intel VTune
- Instrumentación del generador de perfiles para mostrar el gráfico de llamadas y las 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 estáticas de todo el programa para C, Java y COBOL
- Graphviz
- Convierte una representación de texto de cualquier gráfico (incluido un gráfico de llamadas) en una imagen.
- tsort
- 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 de gprof que se analiza a sí mismo:
índice llamado nombre | índice llamado nombre 72384/72384 sym_id_parse [54] | 1508/1508 cg_dfn [15][3] 72384 coincide con [3] | [13] 1508 antes de la visita [13]---------------------- | ---------------------- 4/9052 cg_tally [32] | 1508/1508 cg_assemble [38] 3016/9052 hist_print [49] | [14] 1508 propagate_time [14] 6032/9052 propagate_flags [52] | ----------------------[4] 9052 sym_lookup [4] | 2 cg_dfn [15]---------------------- | 1507/1507 cg_assemble [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 is_busy [11] 24/1537 parse_spec [19] | 1508/1508 previa_visita [13] 1513/1537 core_create_function_syms [41] | 1508/1508 post_visit [12][6] 1537 sym_init [6] | 2 cg_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 print_name_only [25] 2/1510 arc_add [31] | ---------------------- 1508/1510 cg_assemble [38] | 1430/1430 core_create_function_syms [41][8] 1510 arc_lookup [8] | [17] 1430 source_file_lookup_path [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 propagate_flags [52] | ----------------------[10] 1508 heredados_banderas [10] | 24/24 parse_id [18]---------------------- | [19] 24 parse_spec [19] 1508/1508 cg_dfn [15] | 24/1537 sym_init [6][11] 1508 is_busy [11] | -------------------------------------------- | 24/24 principal [1210] 1508/1508 cg_dfn [15] | [20] 24 sym_id_add [20][12] 1508 post_visit [12] |
Ver también
- Visualización de software
- Gráfico de dependencia
Referencias
- ^ Callahan, D .; Carle, A .; Hall, MW; Kennedy, K. (abril de 1990). "Construyendo el procedimiento llamado multigraph". 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 . Springer Science & Business Media. 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 .
- ^ Grove, David; DeFouw, Greg; Dean, Jeffrey; Chambers, Craig; Grove, David; DeFouw, Greg; Dean, 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 .; Simon, D. (2001). "Ayudar a la comprensión del programa mediante el análisis de características estáticas y dinámicas". Actas IEEE International Conference on Software Maintenance. ICSM 2001 : 602–611. doi : 10.1109 / icsm.2001.972777 . ISBN 0-7695-1189-9.
- ^ Musco, Vincenzo; Monperrus, Martin; Preux, Philippe (26 de julio de 2016). "Un estudio a gran escala de predicción de impacto basado en gráficos de llamadas utilizando pruebas de mutación" . Revista de calidad de software . 25 (3): 921–950. arXiv : 1812.06286 . doi : 10.1007 / s11219-016-9332-8 .
- ^ Gao, Debin; Reiter, Michael K .; Song, Dawn (25 de octubre de 2004). "Extracción de caja gris de gráficos de ejecución para 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.