Содержание к диссертации
Введение
1 Применение промежуточных представлений в статическом анализе программ 16
1.1 Статический анализ 16
1.2 Промежуточные представления 16
1.3 Требования к промежуточному представлению 18
1.4 Используемые представления в существующих инструментах статического анализа и компиляции
1.4.1 Абстрактное синтаксическое дерево 20
1.4.2 GIMPLE 21
1.4.3 LLVMIR 22
1.4.4 SSA 22
1.4.5 Представления Вauhaus 23
1.4.6 Представление Malpas
1.5 Характеристика существующих промежуточных представлений в соответствии с требованиями 24
1.6 Разрабатываемое представление 25
1.7 Объектно-ориентированные языки программирования 26
1.8 Математическая модель классового представления
1.8.1 Связи наследования 29
1.8.2 Связи агрегации 29
1.9 Универсальное классовое представление 31
2 Особенности статического анализа динамических языков 34
2.1 Динамические языки программирования 34
2.2 Проблема извлечения классового представления в динамических языках
2.3 Существующие решения 35
2.3.1 Алгоритм Хиндли-Милнера 36
2.3.2 Алгоритм Декартова произведения 38
2.3.3 Заключение по существующим алгоритмам вывода типов 40
2.3.4 Существующие инструменты вывода типов для Python 41
2.3.5 Pylint 42
2.3.6 Pysonar 2.4 Предлагаемая методика вывода типов 46
2.5 Описание базовой модели типов 47
2.5.1 Характеристическая сигнатура 47
2.5.2 Предлагаемая модель типов в динамических языках программирования 48
2.6 Численная оценка результатов извлечения типов 51
2.7 Применение нечетких множеств
2.7.1 Ограничения базовой модели 53
2.7.2 Математическая модель типов в динамических языках программирования на основе нечетких множеств 54
2.7.3 Функция принадлежности «capacity» 56
2.7.4 Функция принадлежности «frequency» 57
2.7.5 Пример применения функций принадлежности алгоритмом вывода типов 59
2.8 Применение динамического анализа для проверки адекватности математической модели 61
2.8.1 Результаты для программы logilab 66
2.8.2 Результаты для программы pylint 67
2.8.3 Результаты для программы bazaar 67
2.8.4 Выводы 68
2.9 Результаты для различных значений порога 68
3 Разработанный комплекс программ для статического анализа 72
3.1 Обзор разработанных инструментов анализа 72
3.2 Обработка XML 73
3.3 Извлечение представлений UCR и UCFR для Python 73
3.4 Реализация методики вывода типов при генерации промежуточных представлений для языка Python 76
3.5 Связывание представлений 77
3.6 Инструменты визуального анализа 77
3.6.1 Визуальное представление диаграммы классов 79
3.7 Анализ иерархии наследования на предмет корректного выделения методов в суперклассах 82
3.8 Технология выполнения срезов представлений
3.8.1 Срез на основе одного представления 86
3.8.2 Срез на основе нескольких представлений 87
3.8.3 Реализованные срезы 87
3.8.4 Срез наследования представления UCR 89
3.8.5 Срез вызовов представления UCFR 91
3.8.6 Срез классов представления UCFR 93
3.8.7 Срез создаваемых объектов представления UCR 93
Заключение 96
Список сокращений и условных обозначений 97
Список литературы 98
Список иллюстративного материала 111
Приложения 112
Исходный код программного модуля для извлечения универсального классового представления из исходного кода на языке программирования Python
- Используемые представления в существующих инструментах статического анализа и компиляции
- Проблема извлечения классового представления в динамических языках
- Реализация методики вывода типов при генерации промежуточных представлений для языка Python
- Срез создаваемых объектов представления UCR
Используемые представления в существующих инструментах статического анализа и компиляции
Абстрактное синтаксическое дерево или AST (от англ. Abstract syntax tree) - это конечное, помеченное, ориентированное дерево, в котором внутренние вершины сопоставлены с (помечены) операторами языка программирования, а листья — с соответствующими операндами. Таким образом листья являются пустыми операторами и представляют только переменные и константы. Большое количество инструментов статического анализа работает с абстрактными синтаксическими деревьями. В [73] представлен инструмент для анализа изменений в программе на языке С, на основе изменений абстрактных синтаксических деревьев. Также можно отметить работу [91], посвященную исследованию потока управления и потока данных в программах на основе анализа их абстрактных синтаксических деревьев.
Данное представление основывается на грамматике входного языка и, соответственно, привязано к конкретному языку программирования, для которого построено, AST одного и того же формата не может быть использовано для представления программ, написанных на разных языках программирования.
Данное представление используется в наборе компиляторов GCC. После получения абстрактных синтаксических деревьев для каждого из входных языков формируется промежуточное представление, которое представляет из себя независимое от входного языка представление функций в виде деревьев. На его основе формируется трехадресное представление, разбиения всех выражений на составляющие выражения не более чем с 3 операндами. Там где необходимо при разбиении вводятся временные переменные для вычисления сложных выражений. Структуры потока управления (такие как условные операторы, циклы) приводятся к форме с использованием оператора безусловного перехода goto. Представление используется в инструментах анализа на базе GCC. Одно из интересных исследований в области статического анализа с использованием GIMPLE[55] затрагивает создание инструмента проверки моделей[58].
Данное представление ] используется в компиляторах основанных на виртуальной машине LLVM[63] (англ. Low Level Virtual Machine). В виртуальной машине LLVM, на которой основано целое семейство компиляторов, в том числе, набирающий популярность компилятор языков C/C++ - clang, процесс компиляции построен вокруг промежуточного представления, которое так и называется - Intermediate representation[93]. С помощью фронт-эндов из исходного кода получается это промежуточное представление, над ним могут выполняться преобразования во время компиляции, связанные с оптимизацией и т.д. После этого генераторы кода преобразуют представление в нативный код.
Представление основано на низкоуровневом наборе инструкций RISC-подобной виртуальной машины, которая поддерживает простые инструкции такие как сложение, вычитание, сравнение и переход. Инструкции имеют трехадресную форму, виртуальная машина поддерживает бесконечное количество виртуальных регистров, используемых для хранения переменных и результатов вычисления выражений.
В конструировании компиляторов 88А-представление[45] (англ. Static single assignment form) это промежуточное представление, в котором каждой переменной значение присваивается лишь единожды. Переменные исходной программы разбиваются на версии, обычно с помощью добавления суффикса, таким образом, что каждое присваивание осуществляется новой версии переменной и данная версия более не изменяется. В SSА-представлении цепочки определение-использование (англ. def-use) заданы явно и содержат единственный элемент. Данное представление используется при оптимизации [29] результирующего кода в компиляции. В наборе компиляторов GCC SSA используется для представления переменных в GIMPLE. Представление используется также и в компиляторах основанных на LLVM.
Набор инструментов статического анализа Bauhaus Project[85] использует 2 различных представления при анализе - IML[60] и RFG[44].
Первое представление является низкоуровневым и описывает программу на достаточно низком уровне. Оно формируется на основе обобщенного синтаксического дерева (GAST) и GSA[77] - формата основанного на SSA.
Второе представление определяет высокоуровневые сущности в программе такие как конструкции языков программирования (функции, типы, переменные и пр.) и абстрактные концепции (абстрактные типы данных, компоненты, подсистемы и т.д.) и связи между ними. Примеры таких связей могут быть различными - от информации, которая может быть напрямую извлечена из исходного кода(например вызовы функций) до более абстрактных (например взаимодействие между клиентом и сервером).
Проблема извлечения классового представления в динамических языках
Разработаны Оле Агесеном[31] и являются развитием исследований Пальцберга и Шварцбаха[78]. Результаты работы алгоритма вывода представляются в виде множества возможных типов объектов. Ограничения типов представляются в виде графа, связывающего выражения, их типы и переменные, для которых выполнялось присваивание. Алгоритм типизации состоит из трех шагов:
1. Размещение переменных типов. На первом шаге с каждым выражением и переменной в программе связывается переменная типа, возможными значениями переменной являются типы, которые может иметь выражение. В начальный момент все переменные типов имеют значение пустого множества типов, в ходе работы алгоритма вывода типов для каждой переменной будут добавляться новые значение возможных типов.
2. 3aceHBafflie»(seeding) переменных типов. Объекты типов добавляются к переменным типов. Целью является получить начальное состояние программы, инициализируя переменные типов в тех местах где объекты типов могут быть получены. Например если можно определить тип выражения (например «3» - целочисленный тип), то выражению присваивается этот тип.
3. Установление ограничений и распространение. На последнем шаге переменные типов связываются в сеть с помощью добавления направленных ребер между ними. По завершении этого этапа переменные типов будут представлены в виде ориентированного графа. Ребра графа будут представлять ограничения. Ограничение является эквивалентом потока данных. Например, если переменной присваивается значение, то появляется ребро между переменной типа присваиваемого выражения и переменной типа переменной. Когда добавляется ограничение, оно распространяется дальше для тех выражений и переменных от которых зависит выражение, для которого появилось ограничение типа. Ограничения генерируются для всех возможных потоков данных в целевой программе. Различные языки программирования имеют различные языковые конструкции, которые могут приводить к появлению потока данных, можно представить общие примеры: Присваивание создает поток данных от выражения присваиваемого значения к переменной, для которой выполняется присваивание. Доступ к переменной создает поток данных от переменной к которой выполняется доступ к выражению в котором она участвует. Вызов функции вызывает поток данных между фактическим значением параметра и формальным, также возвращаемое значение связывается с целью.
Большинство языков имеет также и другие языковые конструкции потока данных. Когда добавляется новое ограничение, появляются новые возможности его распространения. Шаг 3 повторяется до тех пор, пока новых ограничений не может быть получено и распространено. В момент завершения работы алгоритма сеть ограничений представляется в виде ориентированного графа большого размера. Тип выражения может быть получен с помощью анализа соответствующего узла графа.
Также Оле Агесеном был разработан алгоритм Декартова произведения (Cartesian product algorithm) [31], который является развитием оригинального алгоритма и позволяет получать более качественные результаты вывода типов возвращаемых функциями значений на основе обработки различных типов входных параметров.
Алгоритм Декартова произведения также был реализован для вывода типов в языке Python в инструменте Tirpan[6][7] - утилите которая позволяет определять ошибки несоответствия типов. Также можно отметить другой инструмент использующий данный алгоритм при выводе типов -Starkiller[89], утилиту которая позволяет выполнять компиляцию программ на языке Python в код на С.
Существующие алгоритмы вывода типов базируются на анализе выражений присваивания. Тип переменной определяется на основе выражений присваивания для нее. Основные шаги существующих алгоритма вывода типов могут быть представлены в виде следующего списка: 1. Извлечение ограничений на типы выражений из исходного кода, в виде того, что какая-либо составная часть выражения соответствует определенному типу (абстрактному или конкретному). 2. Построение в том или ином виде множества этих ограничений и вывода типов заключающегося в разрешении этого множества ограничений на основе правил вывода типов (например ограничения представляются в виде ориентированного графа). Алгоритм состоит из двух фаз - извлечения ограничений типов и решения системы полученных уравнений.
При определении конкретного типа-класса проекта информация может быть получена при анализе выражений создания экземпляров классов в результате вызовов функций/методов. Если вызывается метод, который является конструктором, то ситуация простая - результат вызова это экземпляр определенного класса - ограничение извлечено и алгоритм может продолжить работу с другими выражениями. Если вызывается обычный метод или функция, то ситуация сложнее, при отсутствии аннотаций типов для возвращаемых значений функций и методов, что имеет место в Python и других динамических языках, для анализа выражений являющихся вызовами функций необходимо выполнять дополнительный анализ таких функций, чтобы определить тип возвращаемого ими значения, если он в свою очередь зависит от вызовов других функций то потребуется дополнительный анализ и т.д. Недостатком является отсутствие возможности вывести тип при отсутствии аннотаций типов для функций, в результате вывода типов получаются только стандартные типы языка, которые получаются на основе анализа констант в выражениях - целочисленные, булевы и т.д.
Можно отметить 2 основные реализации вывода типов для Python, которые доступны для использования, первая из них входит в состав пакета Pylint[82]. Pylint - пакет для статического анализа для Python на основе библиотеки logilab-astng, вывод типов реализован в одном из модулей этой библиотеки. Второй реализацией вывода типов является инструмент Pysonar[84], это утилита предназначенная специально для вывода типов и индексации Python-проектов.
Средства вывода типов logilab-astng используются утилитами пакета pylint. Для тестирования работы была использована утилита pyreverse[83] -средство построения диаграмм классов для Python. Поля классов в ней снабжаются аннотациями типов, полученными в результате их вывода, когда это получилось сделать. На основе этой утилиты мы разработали инструмент генерирующий UCR-подобное представление (не удовлетворяющее в полной мере спецификации UCR), типы полей классов извлечены с помощью утилиты pyreverse. В результирующем представлении Pyreverse типы представляются в текстовой форме в виде постфикса к записи поля, если для поля выведено несколько типов, они перечисляются через запятую. При формировании UCR-подобного представления, все записи для полей разбирались на наличие постфиксов, описывающих типы, почле чего составлялся список имен типов для данного поля.
Реализация методики вывода типов при генерации промежуточных представлений для языка Python
Класс выбирался в качестве кандидата, если множество методов его сигнатуры являлось подмножеством множества методов сигнатуры интересующего поля, а множество полей его сигнатуры являлось подмножеством множества полей сигнатуры интересующего поля. Данная методика базировалась на том предположении, что взаимодействия с полями и методами интересующего поля внутри методов класса, которому он принадлежит, происходит посредством интерфейса некоторого суперкласса (т. е. класса являющегося классом родителем для других классов), т.е. каждое обращение к полям и методам интересующего класса - это обращение к полям и методам, характерным для данного суперкласса.
В реальности это довольно жесткое ограничение, т.к. поле класса при разных сценариях исполнения программы может хранить объекты различных классов, интерфейс работы с которыми не ограничивается сигнатурой некоторого суперкласса. Эти классы вполне могут вообще не быть наследниками некоторого общего суперкласса, либо помимо полей и методов суперкласса будут также использоваться поля характерные только для наследников. В таком случае в проекте может не быть класса, в сигнатуре которого есть все поля и методы из сигнатуры интересующего поля, т.к. в нее входят поля и методы различных классов. 2.7.2 Математическая модель типов в динамических языках программирования на основе нечетких множеств
Предлагается доработать метод подбора классов-кандидатов для возможности подбирать классы-кандидаты для полей, хранящих объекты классов, не характеризующихся интерфейсом общего суперкласса. Для этого предлагается представлять кандидатов для класса поля в виде нечеткого отношения я , определяемого как показано ниже. HQCpXFpXCp={cs,f,cc,\is(cs,f,cc)\cs,cc Cp,f Fp} (13) Будет использоваться функция принадлежности \i (cs,f,cc) , которая позволяет оценить класс в качестве кандидата для определенного интересующего поля. Функция формирует количественную оценку класса в качестве типа интересующего поля в соответствии с определенным подходом. 1 значение функции для класса определяет максимальную оценку, а 0 — минимальную. Основываясь на значении этой функции для того или иного класса можно выполнять подбор кандидатов для типа интересующего поля. На основе данного нечеткого множества можно подбирать класс в качестве кандидата, если значение функции принадлежности для этого класса больше определенного порогового значения.
Согласно оригинальной терминологии отношение D содержит пары классов и их интересующих полей. Отметим, что интересующими полями в предлагаемой методике являются те поля классов, которые как-либо использовались в методах класса, которому они принадлежат. Под использованием в данном случае понимаем обращение к полям или методам этого поля.
Также введем отношения Yf CxFxF и Ym CxFxM 5 определяющие все поля и методы, соответственно, интересующих полей к которым происходило обращение У , = {(с , f, f а)\обращение к полю fd утиного поля /класса с ,{с, f)&DD, f d&F] f 14) Y m={(c, f, т)\обращение к методу[m утиного поля / класса с, (с ,/)eZ)D, тєМ] (\5) Например, рассмотрим класс приведенный в листинге 4: Листинг 4 - Пример класса для применения методики типизации class DocumentHandler(object): doc = None handler = None def init ( self, factory,doc factory) : self, handler = factory.get handler () self, doc = doc factory.get current doc () def change head ( self, new head) self. doc.head = new head self. doc.update links () self, handler. update head(self. doc) def get contents by head (self, head) : if (self, doc .head==head) : self, handler . protect contents ( self . doc) return self. doc.contents def find ( self, name) : for n in self. doc.index: if(n.name==name): return self, handler.get strings(n. ids ) def find and replace ( self, name,changed name) : for n in self. doc.index: if(n.name==name): for s in self, handler.get strings(n. ids ) : s. replace(name,changed name)
Для класса DocumentHandler из примера интересующими полями, используемыми в методах класса, являются поля doc и handler, для первого из этих полей происходило обращение к методу_update_links и полям head, contents и index, а для второго обращение к методам updatehead, protectcontents, getstrings. В данном случае: Y,={(DocumentHandler, doc, head), {DocumentHandler, _doc, contents), (DocumentHandler, _doc, index) 1 Ym={{DocumentHandler, doc, update_links), {DocumentHandler, handler, update_head), {DocumentHandler, handler, protect_contents), {DocumentHandler, _handler, get_strings))
Возможные варианты функции принадлежности нечеткого отношения.
1. Учитывать только процент полей из полной сигнатуры интересующего поля, которые имеются у данного класса. Класс будет подобран в качестве кандидата, если он у него имеется определенная доля полей и методов из сигнатуры интересующего поля. Будем использовать для обозначения данной функции название «capacity».
2. Учитывать частоту использования полей в методах класса, наибольшую долю в итоговой оценке отдавать тем полям которые использовались наиболее часто у класса. Частота использования - достаточно важный параметр для принятия решения о потенциальном классе кандидате, ведь поле которое использовалось трижды несет гораздо больше информации о потенциальном классе кандидате, чем поле к которому обращались лишь 1 раз. Будем использовать для обозначения данной функции название «frequency».
В первом случае в качестве функции принадлежности будет использоваться отношение общего количества полей и методов из сигнатуры интересующего поля, которые имеются у рассматриваемого класса к общему количеству полей и методов из сигнатуры интересующего ПОЛЯ.
Сигнатура класса ссеС - SC={FC,MC),FC F,МС М ; сигнатура интересующего поля f F класса cseC - SD={FD,MD),FD F,MD M ДЛЯ определения класса ссеС как кандидата для интересующего поля feF класса cseC в нечетком отношении Я вводится функция принадлежности Vc{cs,f,cc) , которая рассчитывается как показано ниже:
При использовании такой функции высокую оценку будут получать те классы, которые содержат больше различных полей и методов характерных для сигнатуры интересующего поля. Максимальная оценка будет у тех классов, которые содержат все поля и методы из сигнатуры интересующего поля. Классы, которые подбирались как кандидаты для типа поля в соответствии с оригинальной методикой соответствуют 1 значению этой функции, т.к. в оригинальной методике все поля и методы из сигнатуры интересующего поля должны были входить в сигнатуру класса, который выбирался в качестве класса-кандидата.
Срез создаваемых объектов представления UCR
Оба промежуточных представления используемые в разработанном комплексе программ основаны на формате XML. Для обработки XML на языке Python существует несколько библиотек. Была выбрана библиотека lxml[66], наиболее популярное решение в своей области по ряду причин, во-первых, это первая XML-библиотека для Python, которая имеет высокую производительность, кроме того она содержит встроенную поддержку XPath[49] 1.0, XSLT 1.0, пользовательские элементарные классы и даже типичный для Python интерфейс привязки данных. Библиотека lxml построена на базе двух библиотек языка С: Hbxml2 и libxslt. Они обеспечивают большую часть возможностей для основных задач анализа, сериализации и преобразования.
При реализации обработки данных представлений в XML был использован язык запросов к элементам XML-документа Xpath[106].
Извлечение представлений UCR и UCFR для Python Для решения этой задачи была использована библиотека logilab 74 astng[65] библиотека предназначена для обработки AST для программ на Python. Были реализованы классы CSUStAn.ucr.builder.UCRBuilder и CSUStAn.ucfr.builder.UCFRBuilder для извлечения представлений UCR и UCFR, соответственно. Исходными данными для получения представлений выступало AST, полученное с помощью данной библиотеки. Обработка узлов AST реализована с использованием паттерна Visitor на основе базового класса logilab.astng.utils.LocalsVisitor были реализованы Visitor-классы для извлечения каждого из представлений. Классы содержат функции посещения интересующих узлов AST Python. Основная обработка при работе UCRBuilder выполняется при посещении узлов типа Function и Class (соответствующих представленным в исходном коде функциям и классам) UCFRBuilder - при посещении узлов типа Function. Исходный код на Python
Результирующие представления UCR и UCFR сохраняются в формате XML, для сохранения представлений в данный формат используется Python-библиотека lxml[66]. Эта же библиотека используется в дальнейшем для извлечения представлений из XML-файла. Таким образом в качестве исходных данных анализаторов выступают представления в виде XML и напрямую с исходным кодом они не работают. Архитектура разработанной программы представлена на рисунке 7. 3.4 Реализация методики вывода типов при генерации промежуточных представлений для языка Python Универсальное классовое представление и универсальное представление потока управления генерируются из абстрактного синтаксического дерева, получаемого из исходного текста программ на Python с использованием библиотеки logilab-astng[65]. Обработка узлов абстрактного синтаксического дерева выполняется с использованием паттерна Visitor, базовым классом для такой обработки в библиотеке logilab-astng является logilab.astng.utils.LocalsVisitor. От него пронаследован класс СSUStAn.astng.inspector.DuckLinker, выполняющий сбор информации об обращении к полям и методам в области видимости при обработке узлов типа Getattr, класс является базовым для классов С SUSt An. astng. inspector .ClassIRLinker и CSUStAn.astng.controlflow.UCFRLinker, выполняющих обработку узлов абстрактного ситаксического дерева при генерации представления UCR и UCFR, соответственно.
Основная обработка в классе DuckLinker связана с обработкой узлов типа Getattr, описывающих конструкции обращения к полям выражений (например а.с, self.update() и т. д.) в исходном коде программ на Python. Обработку можно разделить на 2 этапа.
Первым этапом служит обработка обращений к полям локальных переменных, например, обращение к полю name переменной employee -employee.name. Такие обращения несут информацию о сигнатуре локальных переменных, которая в дальнейшем позволит выводить тип для данной переменной и определить цель вызова для вызовов методов объекта, хранимого этой переменной. Помимо этого необходимо также обработать обращения к полям и методам объектов, хранимых в полях текущего экземпляра класса для методов классов. Для обращения к текущему экземпляру класса в методах используется специальный аргумент - self, таким образом, обращение к методу update поля doc текущего экземпляра класса в исходном коде будет иметь вид self.doc.update(). Такие обращения несут информацию о сигнатурах полей класса, которая в дальнейшем используется для вывода типов этих полей в соответствии с описанным алгоритмом типизации.
Для выполнения совместного анализа представлений UCR и UCFR одного и того же проекта необходимо выполнить связывание представлений -добавить в представление UCFR информацию о соответствии элементов представления UCFR элементам представления UCR для возможности удобной навигации между представлениями. Для выполнения этой задачи был реализован класс CSUStAn.cross.handling.DataflowLinker, принимающий в качестве входных параметров представления UCR и UCFR. На первом этапе для элементов описывающих методы классов в представлении UCFR добавляется информации о связанных с ними классов представления UCR. Обработка выполняется на основе запросов Xpath. После этого выполняется связывание элементов, описывающих вызовы - добавляется информация о классе для вызовов конструкторов и методов классов.
Результаты статического анализа предназначены в первую очередь для анализа человеком. Наиболее удобной представления для человека является визуальная форма, в связи с этим был разработан ряд инструментов визуального анализа. Основными направлениями анализа служили анализ объектно-ориентированной архитектуры и анализ потока управления программ. Эти направления разрабатывались как по отдельности так и совместно, когда одновременно с анализом архитектуры классов программы выполнялся анализ потока управления и визуализируются результаты такого анализа. Такой совместный анализ предоставляет большой интерес, т. к. одновременно выполняется анализ двух промежуточных представлений исходного кода, совместно несущих больше информации об исходном коде чем каждое из представлений в отдельности. В качестве основного инструмента визуализации был разработана утилита для визуального представления диаграммы классов.
Для реализации инструментов визуального анализа так или иначе требовалось выполнять визуализацию графов разного формата. Для решения данной задачи был задействован пакет Graphviz[54].
Graphviz (сокращение от англ. Graph Visualization Software) — это пакет утилит по автоматической визуализации графов, заданных в виде описания на языке DOT. Пакет Graphviz разработан специалистами лаборатории AT&T и распространяется с открытыми исходными файлами по лицензии EPL (Eclipse Public License) и работает на многих операционных системах, включая Linux[94], Mac OS[34], Microsoft Windows[105]. В пакет утилит входит программа «dot», автоматический визуализатор ориентированных графов, который принимает на вход текстовый файл на языке DOT с представлением графа в виде смежных списков, а на выходе формирует граф в виде графического, векторного или текстового файла.
Входной файл для программы «dot» является обычным текстовым файлом на специальном языке описания. Программа «dot» сама распознаёт все связи графа и упорядочивает его таким образом, чтобы было наименьшее количество пересечений в полученном графическом представлении графа. Данный формат широко распространен в инструментах визуализации для программного обеспечения. Одной из интересных разработок[86], использующих пакет Graphviz, является инструмент визуализации системных вызовов операционной Unix, используемый в обучении.
Для его использования из Python-программ была использована библиотека pydot[81]. Результирующие изображения были представлены в векторном формате svg, для удобства масштабирования при визуальном анализе человеком. Генерация данного графического формата из dot поддерживается пакетом Graphviz.
