stringtranslate.com

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

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

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

Базовые концепты

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

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

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

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

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

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

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

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

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

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

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

Испытательный стенд ЛДРА
Механизмы статического и динамического анализа как для хостового, так и для встроенного программного обеспечения с множеством отчетов, включая графики вызовов.
Анализатор проекта
Статический анализатор кода и генератор графов вызовов для кода Visual Basic
Визуальный эксперт
Статический анализатор кода и генератор графов вызовов для кода Oracle PL/SQL , SQLServer Transact-SQL , C# и PowerBuilder.
Анализатор производительности Intel VTune
Инструментарий профилировщика для отображения графика вызовов и статистики выполнения.
Набор инструментов для реинжиниринга программного обеспечения 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] |

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

Рекомендации

  1. ^ Каллахан, Д.; Карл, А.; Холл, Мичиган ; Кеннеди, К. (апрель 1990 г.). «Построение мультиграфа вызова процедуры». Транзакции IEEE по разработке программного обеспечения . 16 (4): 483–487. дои : 10.1109/32.54302.
  2. ^ Удай Хедкер; Амитабха Саньял; Багешри Сатэ (2009). Анализ потоков данных: теория и практика . ЦРК Пресс. п. 234. ИСБН 978-0-8493-3251-7.
  3. ^ Панкадж Джалоте (1997). Интегрированный подход к разработке программного обеспечения . Springer Science & Business Media. п. 372. ИСБН 978-0-387-94899-7.
  4. ^ Райдер, Б.Г. (май 1979 г.). «Построение графа вызовов программы». Транзакции IEEE по разработке программного обеспечения . СЭ-5 (3): 216–226. дои :10.1109/tse.1979.234183. S2CID  16527042.
  5. ^ Гроув, Дэвид; ДеФау, Грег; Дин, Джеффри; Чемберс, Крейг; Гроув, Дэвид; ДеФау, Грег; Дин, Джеффри; Чемберс, Крейг (9 октября 1997 г.). «Построение графа вызовов в объектно-ориентированных языках». Уведомления ACM SIGPLAN . АКМ. 32 (10): 108, 108–124, 124. дои : 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.