Сравнивайте с английским: нажмите на абзац — оригинал откроется в окне. Кнопка EN под абзацем показывает его прямо в тексте.
Содержание
Введение
Структура в вычислительной технике
Structure in computing
Граф вызовов (также известный как мультиграф вызовов) — это граф потока управления, представляющий отношения вызовов между подпрограммами в компьютерной программе. Каждый узел соответствует процедуре, а каждое ребро (f, g) указывает, что процедура f вызывает процедуру g. Следовательно, цикл в графе свидетельствует о рекурсивных вызовах процедур.
A call graph (also known as a call multigraph) is a control flow graph, which represents calling relationships between subroutines in a computer program. Each node represents a procedure and each edge (f, g) indicates that procedure f calls procedure g. Thus, a cycle in the graph indicates recursive procedure calls.
Основные понятия
Графики вызовов могут быть динамическими или статическими. Динамический график вызовов представляет собой запись выполнения программы, например, полученную с помощью профилировщика. Таким образом, динамический график вызовов может быть точным, но описывает только один конкретный запуск программы. Статический график вызовов предназначен для представления всех возможных запусков программы. Вычисление точного статического графика вызовов является неразрешимой задачей, поэтому алгоритмы построения статических графиков вызовов обычно представляют собой переоценки. Это означает, что в графике отображаются все фактические отношения вызовов, а также, возможно, некоторые отношения вызовов, которые никогда не произойдут при реальном выполнении программы. Графики вызовов могут быть определены с разной степенью точности. Более точный график вызовов точнее аппроксимирует поведение реальной программы, но требует больше времени на вычисление и больше памяти для хранения. Наиболее точный график вызовов является полностью контекстно-зависимым, что означает, что для каждой процедуры в графе содержится отдельный узел для каждого стека вызовов, с которым эта процедура может быть активирована. Полностью контекстно-зависимый график вызовов называется деревом контекста вызовов. Его можно легко вычислить динамически, хотя это может потребовать значительного объема памяти. Деревья контекста вызовов обычно не вычисляются статически, поскольку для больших программ это заняло бы слишком много времени. Наименее точный график вызовов является контекстно-независимым, что означает, что для каждой процедуры существует только один узел. Для языков с динамической диспетчеризацией (например, Java или C++), функциями первого класса (например, Python или Racket) или указателями на функции (например, C), точное вычисление статического графика вызовов требует результатов анализа псевдонимов. И наоборот, для вычисления точного анализа псевдонимов требуется график вызовов. Многие системы статического анализа разрешают эту кажущуюся бесконечную регрессию, вычисляя оба компонента одновременно.
Call graphs can be dynamic or static. A dynamic call graph is a record of an execution of the program, for example as output by a profiler. Thus, a dynamic call graph can be exact, but only describes one run of the program. A static call graph is a call graph intended to represent every possible run of the program. The exact static call graph is an undecidable problem, so static call graph algorithms are generally overapproximations. That is, every call relationship that occurs is represented in the graph, and possibly also some call relationships that would never occur in actual runs of the program. Call graphs can be defined to represent varying degrees of precision. A more precise call graph more precisely approximates the behavior of the real program, at the cost of taking longer to compute and more memory to store. The most precise call graph is fully context sensitive, which means that for each procedure, the graph contains a separate node for each call stack that procedure can be activated with. A fully context sensitive call graph is called a calling context tree. This can be computed dynamically easily, although it may take up a large amount of memory. Calling context trees are usually not computed statically, because it would take too long for a large program. The least precise call graph is context insensitive, which means that there is only one node for each procedure. With languages that feature dynamic dispatch (i. e. Java or C++), first class functions (i. e. Python or Racket), or function pointers (i. e. C), computing a static call graph precisely requires alias analysis results. Conversely, computing precise aliasing requires a call graph. Many static analysis systems solve the apparent infinite regress by computing both simultaneously.
Использование
Графики вызовов могут использоваться разными способами. Одно из простых применений графиков вызовов — поиск процедур, которые никогда не вызываются. Графики вызовов могут служить документацией, помогающей людям понимать программы. Графики вызовов также могут использоваться для выявления аномалий в работе программы или атак с внедрением кода.
Call graphs can be used in different ways. One simple application of call graphs is finding procedures that are never called. Call graphs can act as documentation for humans to understand programs. Call graphs can also be used to detect anomalies of program execution or code injection attacks.
Другие, связанные с ними инструменты
Graphviz Преобразует текстовое представление любого графа (включая граф вызовов) в изображение. tsort Утилита командной строки для выполнения топологической сортировки.
Graphviz Turns a text representation of any graph (including a call graph) into a picture. tsort Command line utility that performs a topological sort.