График звонков

Граф вызовов, созданный для простой компьютерной программы на Python.

Граф вызовов (также известный как мультиграф вызова ^[1]^[2] ) представляет собой график потока управления , ^[3] , который представляет собой отношения между вызовом подпрограммой в компьютерной программе . Каждый узел представляет процедуру, и каждое ребро (f, g) указывает, что процедура f вызывает процедуру g . Таким образом, цикл на графике указывает на рекурсивные вызовы процедур.

Основные понятия

Графики звонков могут быть динамическими или статическими. ^[4] Динамический граф вызовов - это запись выполнения программы, например, вывод профилировщика. Таким образом, динамический граф вызовов может быть точным, но описывает только один запуск программы. Статический граф вызовов - это граф вызовов, предназначенный для представления всех возможных запусков программы. Точный статический граф вызовов - неразрешимая проблема , поэтому алгоритмы статического графа вызовов обычно являются чрезмерными приближениями. То есть каждая возникающая взаимосвязь вызовов представлена на графике и, возможно, также некоторые взаимосвязи вызовов, которые никогда не возникли бы при фактических запусках программы.

Графы вызовов могут быть определены для представления различной степени точности. Более точный график вызовов более точно аппроксимирует поведение реальной программы за счет того, что требуется больше времени для вычислений и большего объема памяти для хранения. Наиболее точный граф вызовов полностью контекстно-зависимый , что означает, что для каждой процедуры граф содержит отдельный узел для каждого стека вызовов , с помощью которого может быть активирована процедура. Полностью контекстно-зависимый граф вызовов называется деревом контекста вызова . Это можно легко вычислить динамически, хотя это может занять большой объем памяти. Деревья контекстов вызова обычно не вычисляются статически, потому что для большой программы это займет слишком много времени. Наименее точный граф вызовов не зависит от контекста, что означает, что для каждой процедуры существует только один узел.

В языках с динамической диспетчеризацией , таких как Java и C ++ , для вычисления статического графа вызовов точно требуются результаты анализа псевдонимов . ^[5] И наоборот, для вычисления точного алиасинга требуется граф вызовов. Многие системы статического анализа решают очевидную бесконечную регрессию, вычисляя и то, и другое одновременно.

Использование

Графики звонков можно использовать по-разному. Одно простое применение графов вызовов - поиск процедур, которые никогда не вызываются. Графы вызовов могут служить документацией для понимания программ людьми . ^[6] Они также могут служить основой для дальнейшего анализа, такого как анализ, отслеживающий поток значений между процедурами или прогнозирование воздействия изменений . ^[7] Графы вызовов также могут использоваться для обнаружения аномалий выполнения программы или атак путем внедрения кода. ^[8]

Программное обеспечение

Генераторы графов вызовов бесплатных программ

График вызовов во время выполнения (большинство перечисленных инструментов являются профилировщиками с функциями графика вызовов)

gprof : включен в BSD или часть двоичных утилит GNU
callgrind: часть Valgrind
KCachegrind : мощный инструмент для создания и анализа графиков вызовов на основе данных, созданных callgrind.
Монитор активности Mac OS X: Монитор процессов с графическим интерфейсом пользователя Apple Activity Monitor имеет встроенный генератор графа вызовов, который может выполнять выборку процессов и возвращать граф вызовов. Эта функция доступна только в Mac OS X Leopard.
OpenPAT: включает control_flowинструмент, который автоматически создает изображение графика вызовов Graphviz на основе измерений времени выполнения.
pprof , инструмент с открытым исходным кодом для визуализации и анализа данных профиля, который будет использоваться вместе с gperftools .
CodeAnalyst от AMD (выпущен под лицензией GPL)
makeppgraph - это генератор графов зависимостей (на уровне модуля) для сборок, выполняемых с помощью makepp .
Intel (R) Single Event API (бесплатно, с открытым исходным кодом)

Статический для получения графиков вызовов без запущенного приложения:

C / C ++

Sourcetrail создает статический граф вызовов, который пользователь может динамически исследовать. Также поддерживает Python и Java
doxygen : использует Graphviz для создания статических диаграмм вызовов / наследования
cflow : GNU cflow может генерировать прямой и инвертированный граф вызовов программы на C
Египет : небольшой Perl- скрипт, использующий gcc и Graphviz для создания статического графа вызовов программы C.
Analizo : вычисляет метрики исходного кода, строит графики зависимостей.
CCTree : собственный плагин Vim, который может отображать статические графики вызовов, читая базу данных cscope . Работает для программ C.
codeviz : генератор статического графа вызовов (программа не запускается). Реализован как патч к gcc ; работает для программ на C и C ++.
calltree.sh : функции оболочки Bash, которые объединяют cscope, graphviz и набор инструментов точечного рендеринга для отображения отношений «вызывающий» и «вызываемый» выше, ниже и / или между указанными вами функциями C.
tceetree : как и calltree.sh, он соединяет Cscope и Graphviz , но это исполняемый файл, а не сценарий bash.

Идти

go-callvis : интерактивный генератор графа вызовов для программ Go, вывод которых можно нарисовать с помощью Graphviz

Многоязычный

callGraph : генератор графов вызовов с открытым исходным кодом для awk, bash, basic, dart, fortran, go, lua, javascript, kotlin, matlab, perl, pascal, php, python, R, raku, ruby, rust, scala, swift, tcl , и машинописный текст.

.Сеть

NDepend : это инструмент статического анализа кода .NET. Этот инструмент поддерживает большое количество метрик кода, позволяет визуализировать зависимости с помощью ориентированных графов и матрицы зависимостей.

PHP, Perl и Python

Devel :: NYTProf : анализатор производительности Perl и генератор диаграмм вызовов
phpCallGraph : генератор графа вызовов для программ PHP, использующий Graphviz . Он написан на PHP и требует как минимум PHP 5.2.
pycallgraph : генератор графа вызовов для программ Python, использующий Graphviz .
pyan : генератор статического графа вызовов для программ Python, использующий Graphviz .
gprof2dot : генератор графа вызовов, написанный на Python, который преобразует данные профилирования для многих языков / сред выполнения в граф вызовов Graphviz .
code2flow : генератор графа вызовов для программ Python и Javascript, использующий Graphviz.
rcviz : модуль Python для рендеринга графиков вызовов, сгенерированных во время выполнения, с помощью Graphviz . Каждый узел представляет собой вызов функции с переданными ей параметрами и возвращаемым значением.

XQuery

Графики вызовов XQuery из XQuery Wikibook : генератор графов вызовов для функционального модуля XQuery, который использует Graphviz

Собственные генераторы графов вызовов

Анализатор проекта: Статический анализатор кода и генератор графа вызовов для кода Visual Basic
Визуальный эксперт: Статический анализатор кода и граф вызовов генератор для Oracle PL / SQL , SQLServer Transact-SQL , C # и PowerBuilder кода
Анализатор производительности Intel VTune: Инструменты профилировщика для отображения графика вызовов и статистики выполнения
Набор инструментов для реинжиниринга программного обеспечения DMS: Настраиваемый инструмент анализа программ со статическим извлечением глобального графа вызовов для всей программы для C, Java и COBOL

Другие, связанные инструменты

Graphviz: Превращает текстовое представление любого графа (включая граф вызовов) в картинку.
цорт: Утилита командной строки, выполняющая топологическую сортировку.

Пример графика

Примерный график звонков, сгенерированный gprof, который анализирует сам себя:

индекс с именем имя | индекс с именем имя 72384/72384 sym_id_parse [54] | 1508/1508 cg_dfn [15]
[3] 72384 совпадений [3] | [13] 1508 предварительных посещений [13]
---------------------- | ---------------------- 4/9052 cg_tally [32] | 1508/1508 cg_assemble [38] 3016/9052 hist_print [49] | [14] 1508 Время_пропускания [14] 6032/9052 spread_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 имеет номер [9]
---------------------- | 1508/1508 is_busy [11] 24/1537 parse_spec [19] | 1508/1508 pre_visit [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 путь_к_источному_просмотру [17]
---------------------- | ---------------------- 1509/1509 cg_dfn [15] | 24/24 sym_id_parse [54]
[9] 1509 is_numbered [9] | [18] 24 parse_id [18]
---------------------- | 24/24 parse_spec [19] 1508/1508 spread_flags [52] | ----------------------
[10] 1508 inherit_flags [10] | 24/24 parse_id [18]
---------------------- | [19] 24 parse_spec [19] 1508/1508 cg_dfn [15] | 24/1537 sym_init [6]
[11] 1508 занят [11] | ----------------------
---------------------- | 24/24 основной [1210] 1508/1508 cg_dfn [15] | [20] 24 sym_id_add [20]
[12] 1508 post_visit [12] |

См. Также

Визуализация программного обеспечения
График зависимости

Ссылки

^ Каллахан, Д .; Carle, A .; Холл, МВт; Кеннеди, К. (апрель 1990 г.). «Построение мультиграфа вызова процедуры». IEEE Transactions по разработке программного обеспечения . 16 (4): 483–487. DOI : 10.1109 / 32.54302 .
^ Удай Khedker; Амитабха Саньял; Багешри Сате (2009). Анализ потока данных: теория и практика . CRC Press. п. 234. ISBN 978-0-8493-3251-7.
^ Панкадж Джалот (1997). Комплексный подход к разработке программного обеспечения . Springer Science & Business Media. п. 372 . ISBN 978-0-387-94899-7.
Перейти ↑ Ryder, BG (май 1979 г.). «Построение графа вызовов программы». IEEE Transactions по разработке программного обеспечения . SE-5 (3): 216–226. DOI : 10.1109 / tse.1979.234183 .
^ Роща, Дэвид; ДеФоу, Грег; Дин, Джеффри; Чемберс, Крейг; Гроув, Дэвид; ДеФоу, Грег; Дин, Джеффри; Чемберс, Крейг (9 октября 1997 г.). «Построение графа вызовов в объектно-ориентированных языках». Уведомления ACM SIGPLAN . ACM. 32 (10): 108, 108-124, 124. DOI : 10,1145 / 263700,264352 .
^ Eisenbarth, T .; Koschke, R .; Саймон, Д. (2001). «Помощь в понимании программ с помощью статического и динамического анализа функций». Труды Международной конференции по сопровождению программного обеспечения IEEE. ICSM 2001 : 602–611. DOI : 10.1109 / icsm.2001.972777 . ISBN 0-7695-1189-9.
^ Муско, Винченцо; Монперрус, Мартин; Preux, Philippe (26 июля 2016 г.). «Крупномасштабное исследование прогнозирования воздействия на основе графа вызовов с использованием мутационного тестирования» . Журнал качества программного обеспечения . 25 (3): 921–950. arXiv : 1812.06286 . DOI : 10.1007 / s11219-016-9332-8 .
^ Гао, Дебин; Рейтер, Майкл К .; Песня, Рассвет (25 октября 2004 г.). «Серый ящик извлечения графиков выполнения для обнаружения аномалий». Материалы 11-й конференции ACM по компьютерной и коммуникационной безопасности - CCS '04 . ACM. С. 318–329. DOI : 10.1145 / 1030083.1030126 . ISBN 1581139616.

[1] Каллахан, Д .; Carle, A .; Холл, МВт; Кеннеди, К. (апрель 1990 г.). «Построение мультиграфа вызова процедуры». IEEE Transactions по разработке программного обеспечения . 16 (4): 483–487. DOI : 10.1109 / 32.54302 .

[KhedkerSanyal2009-2] Удай Khedker; Амитабха Саньял; Багешри Сате (2009). Анализ потока данных: теория и практика . CRC Press. п. 234. ISBN 978-0-8493-3251-7.

[Jalote1997-3] Панкадж Джалот (1997). Комплексный подход к разработке программного обеспечения . Springer Science & Business Media. п. 372 . ISBN 978-0-387-94899-7.

[4] Перейти ↑ Ryder, BG (май 1979 г.). «Построение графа вызовов программы». IEEE Transactions по разработке программного обеспечения . SE-5 (3): 216–226. DOI : 10.1109 / tse.1979.234183 .

[5] Роща, Дэвид; ДеФоу, Грег; Дин, Джеффри; Чемберс, Крейг; Гроув, Дэвид; ДеФоу, Грег; Дин, Джеффри; Чемберс, Крейг (9 октября 1997 г.). «Построение графа вызовов в объектно-ориентированных языках». Уведомления ACM SIGPLAN . ACM. 32 (10): 108, 108-124, 124. DOI : 10,1145 / 263700,264352 .

[6] Eisenbarth, T .; Koschke, R .; Саймон, Д. (2001). «Помощь в понимании программ с помощью статического и динамического анализа функций». Труды Международной конференции по сопровождению программного обеспечения IEEE. ICSM 2001 : 602–611. DOI : 10.1109 / icsm.2001.972777 . ISBN 0-7695-1189-9.

[7] Муско, Винченцо; Монперрус, Мартин; Preux, Philippe (26 июля 2016 г.). «Крупномасштабное исследование прогнозирования воздействия на основе графа вызовов с использованием мутационного тестирования» . Журнал качества программного обеспечения . 25 (3): 921–950. arXiv : 1812.06286 . DOI : 10.1007 / s11219-016-9332-8 .

[8] Гао, Дебин; Рейтер, Майкл К .; Песня, Рассвет (25 октября 2004 г.). «Серый ящик извлечения графиков выполнения для обнаружения аномалий». Материалы 11-й конференции ACM по компьютерной и коммуникационной безопасности - CCS '04 . ACM. С. 318–329. DOI : 10.1145 / 1030083.1030126 . ISBN 1581139616.

[1]