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

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

Основные понятия [ править ]

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

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

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

Использование [ править ]

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

Программное обеспечение [ править ]

Бесплатные генераторы графов вызовов программного обеспечения [ править ]

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

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

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

С/С++

Sourcetrail создает статический граф вызовов, который пользователь может динамически исследовать. Также поддерживает Python и Java
doxygen : использует Graphviz для создания статических диаграмм вызовов/наследования.
Cally : инструмент, который использует файлы языка передачи регистров (RTL) GCC для построения графиков вызовов вызывающего или вызываемого объекта для проектов C.
cflow : GNU cflow способен генерировать прямой и инвертированный граф вызовов программы на языке C.
egypt : небольшой 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, julia, 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. Архивировано 25 мая 2007 г. на Wayback Machine : генератор графов вызовов для программ Python, использующих Graphviz .
pyan : статический генератор графов вызовов для программ Python, использующий Graphviz .
gprof2dot : генератор графа вызовов, написанный на Python, который преобразует данные профилирования для многих языков/сред выполнения в граф вызовов Graphviz .
code2flow : генератор графов вызовов для программ Python и Javascript, использующий Graphviz.
rcviz : модуль Python для рендеринга графов вызовов, созданных во время выполнения, с помощью Graphviz . Каждый узел представляет собой вызов функции с переданными ей параметрами и возвращаемым значением.

XQuery

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

Собственные генераторы графов вызовов [ править ]

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

Другие сопутствующие инструменты [ править ]

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

Пример графика [ править ]

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

индексное имя |индексное имя
       72384/72384 sym_id_parse [54] |  1508/1508 cg_dfn [15]
 [3] 72384 совпадение [3] |[13] 1508 pre_visit [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 имеет номер [9]
 ---------------------- |  1508/1508 занят [11]
          24/1537 parse_spec [19] |  1508/1508 предварительное посещение [13]
        1513/1537 core_create_function_syms [41]|  1508/1508 пост_посещение [12]
 [6] 1537 sym_init [6] |  2 cg_dfn [15]
 ---------------------- |----------------------
        1511/1511 core_create_function_syms [41]|  1505/1505 история_принта [49]
 [7] 1511 get_src_info [7] |[16] 1505 print_line [16]
 ---------------------- |  9/2 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 propagate_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 is_busy [11] |----------------------
 ---------------------- |  24/24 основной [1210]
        1508/1508 cg_dfn [15] |[20] 24 sym_id_add [20]
 [12] 1508 post_visit [12] |

См. также [ править ]

Ссылки [ править ]

^ Каллахан, Д.; Карл, А.; Холл, Мичиган ; Кеннеди, К. (апрель 1990 г.). «Построение мультиграфа вызова процедуры». Транзакции IEEE по разработке программного обеспечения . 16 (4): 483–487. дои : 10.1109/32.54302 .
^ Удай Хедкер; Амитабха Саньял; Багешри Сатэ (2009). Анализ потоков данных: теория и практика . ЦРК Пресс. п. 234. ИСБН 978-0-8493-3251-7 .
^ Панкадж Джалоте (1997). Интегрированный подход к разработке программного обеспечения . Springer Science & Business Media. п. 372 . ISBN 978-0-387-94899-7 .
^ Райдер, Б.Г. (май 1979 г.). «Построение графа вызовов программы». Транзакции IEEE по разработке программного обеспечения . СЭ-5 (3): 216–226. дои : 10.1109/tse.1979.234183 . S2CID 16527042 .
^ Гроув, Дэвид; ДеФау, Грег; Дин, Джеффри; Чемберс, Крейг; Гроув, Дэвид; ДеФау, Грег; Дин, Джеффри; Чемберс, Крейг (9 октября 1997 г.). «Построение графа вызовов в объектно-ориентированных языках» . Уведомления ACM SIGPLAN . 32 (10). ACM: 108, 108–124, 124. doi : 10.1145/263700.264352 .
^ Эйзенбарт, Т.; Кошке, Р.; Саймон, Д. (2001). «Помощь в понимании программы посредством статического и динамического анализа функций». Материалы Международной конференции IEEE по сопровождению программного обеспечения. МЦСМ 2001 . стр. 602–611. дои : 10.1109/icsm.2001.972777 . ISBN 0-7695-1189-9 . S2CID 5934718 .
^ Гао, Дебин; Райтер, Майкл К.; Песня, Рассвет (25 октября 2004 г.). «Извлечение графов выполнения из серого ящика для обнаружения аномалий». Материалы 11-й конференции ACM «Компьютерная и коммуникационная безопасность — CCS '04» . АКМ. стр. 318–329. дои : 10.1145/1030083.1030126 . ISBN 1581139616 . S2CID 1189805 .

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

[KhedkerSanyal2009-2] Удай Хедкер; Амитабха Саньял; Багешри Сатэ (2009). Анализ потоков данных: теория и практика . ЦРК Пресс. п. 234. ИСБН 978-0-8493-3251-7 .

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

[4] Райдер, Б.Г. (май 1979 г.). «Построение графа вызовов программы». Транзакции IEEE по разработке программного обеспечения . СЭ-5 (3): 216–226. дои : 10.1109/tse.1979.234183 . S2CID 16527042 .

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

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

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

[1]

[2]

[3]

[4]

[5]

[6]

[7]