stringtranslate.com

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

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

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

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

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

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

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

Обычаи

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

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

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

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

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

С/С++
Идти
Многоязычный
.СЕТЬ
PHP, Perl и Python
XQuery

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

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

Другие, сопутствующие инструменты

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

Образец графика

Пример графика вызовов, сгенерированного 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 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 is_numbered [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 получить_источник_информации [7] |[16] 1505 вывести_строку [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 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 занят [11] |-------------------------------------------- | 24/24 основной [1210] 1508/1508 cg_dfn [15] |[20] 24 sym_id_add [20][12] 1508 пост_визит [12] |

Смотрите также

Ссылки

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