Граф вызовов (также известный как мультиграф вызовов [1] [2] ) — это граф потока управления [3] , который представляет отношения вызовов между подпрограммами в компьютерной программе . Каждый узел представляет процедуру, а каждое ребро (f, g) указывает, что процедура f вызывает процедуру g . Таким образом, цикл в графе указывает на рекурсивные вызовы процедур.
Базовые концепты
Графы вызовов могут быть динамическими или статическими. [4] Граф динамических вызовов — это запись выполнения программы, например, результат профилировщика. Таким образом, динамический граф вызовов может быть точным, но описывает только один запуск программы. Статический граф вызовов — это граф вызовов, предназначенный для представления всех возможных запусков программы. Точный статический граф вызовов является неразрешимой проблемой , поэтому алгоритмы статического графа вызовов обычно являются завышенными аппроксимациями. То есть на графике представлены все возникающие отношения вызовов, а также, возможно, некоторые отношения вызовов, которые никогда не возникнут при реальных запусках программы.
Графы вызовов могут быть определены для представления различной степени точности. Более точный граф вызовов более точно аппроксимирует поведение реальной программы за счет увеличения времени вычислений и увеличения объема памяти для хранения. Самый точный граф вызовов полностью контекстно-зависим , что означает, что для каждой процедуры граф содержит отдельный узел для каждого стека вызовов , с помощью которого процедура может быть активирована. Полностью контекстно-зависимый граф вызовов называется деревом контекста вызовов. Это можно легко вычислить динамически, хотя это может занять большой объем памяти. Деревья контекстов вызовов обычно не вычисляются статически, поскольку для большой программы это заняло бы слишком много времени. Наименее точный граф вызовов является контекстно-независимым , что означает, что для каждой процедуры существует только один узел.
В языках, поддерживающих динамическую диспетчеризацию (например, Java или C++ ), [5] первоклассных функциях (например, Python или Racket ) или указателях функций (например, C ), вычисление статического графа вызовов точно требует результатов анализа псевдонимов . И наоборот, для вычисления точного псевдонима требуется граф вызовов. Многие системы статического анализа решают кажущуюся бесконечную регрессию, вычисляя оба показателя одновременно.
Использование
Графы вызовов можно использовать по-разному. Одним из простых применений графов вызовов является поиск процедур, которые никогда не вызываются. Графы вызовов могут служить документацией для понимания людьми программ . [6] Графы вызовов также можно использовать для обнаружения аномалий выполнения программы или атак с внедрением кода. [7]
Программное обеспечение
Бесплатные генераторы графов вызовов программного обеспечения
График вызовов во время выполнения (большинство перечисленных инструментов являются профилировщиками с функциональностью графа вызовов)
KCachegrind: мощный инструмент для создания и анализа графиков вызовов на основе данных, сгенерированных callgrind.
Монитор активности Mac OS X: Монитор процессов Apple GUI. Монитор активности имеет встроенный генератор графа вызовов, который может выполнять выборку процессов и возвращать граф вызовов. Эта функция доступна только в Mac OS X Leopard .
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.
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
^ Каллахан, Д.; Карл, А.; Холл, Мичиган ; Кеннеди, К. (апрель 1990 г.). «Построение мультиграфа вызова процедуры». Транзакции IEEE по разработке программного обеспечения . 16 (4): 483–487. дои : 10.1109/32.54302.
^ Удай Хедкер; Амитабха Саньял; Багешри Сатэ (2009). Анализ потоков данных: теория и практика . ЦРК Пресс. п. 234. ИСБН978-0-8493-3251-7.
^ Панкадж Джалоте (1997). Интегрированный подход к разработке программного обеспечения . Springer Science & Business Media. п. 372. ИСБН978-0-387-94899-7.
^ Райдер, Б.Г. (май 1979 г.). «Построение графа вызовов программы». Транзакции IEEE по разработке программного обеспечения . СЭ-5 (3): 216–226. дои :10.1109/tse.1979.234183. S2CID 16527042.
^ Эйзенбарт, Т.; Кошке, Р.; Саймон, Д. (2001). «Помощь в понимании программы посредством статического и динамического анализа функций». Материалы Международной конференции IEEE по сопровождению программного обеспечения. МЦСМ 2001 . стр. 602–611. дои : 10.1109/icsm.2001.972777. ISBN0-7695-1189-9. S2CID 5934718.
^ Гао, Дебин; Райтер, Майкл К.; Песня, Рассвет (25 октября 2004 г.). «Извлечение графов выполнения из серого ящика для обнаружения аномалий». Материалы 11-й конференции ACM по компьютерной и коммуникационной безопасности - CCS '04. АКМ. стр. 318–329. дои : 10.1145/1030083.1030126. ISBN1581139616. S2CID 1189805.