Размещено на http://www.allbest.ru/

Оглавление

Введение

Глава 1. Статический анализ языка программирования Python

1.1 Инструменты статического анализа кода

1.2 Дефекты в коде программ на языке Python

1.3 Реализации статического анализа программ на языке Python

Глава 2. Внутрипроцедурный и межпроцедурный анализ для поиска дефектов

2.1 Абстракция потока данных

2.2 Аннотации (резюме)

2.3 Граф вызовов

Глава 3. Реализация решения

3.1 Инструменты разработки

3.2 Анализ потока данных

3.3 Модули реализации

Глава 4. Полученные результаты

4.1 Примеры найденных предупреждений

Заключение

Список использованных источников

Приложения



Введение

В работе рассмотрены подходы, использующиеся в статическом анализе для поиска ошибок в программах на языке Python.

В настоящее время тестирование является важной стадией при разработке программного обеспечения. Тестирование ПО позволяет проверить программы на соответствия требованиям, выявить присутствие ошибок, улучшить качество кода или инспектировать код на соответствие спецификациям. Своевременное тестирование ПО позволяет сократить затраты на исправление решений, обеспечивает надежность и сопровождаемость кода.

Одним из видов тестирования могут являться инструменты статического анализа кода. Статический анализ кода -- анализ исходного кода программы до этапа её компиляции. Также статический анализ кода может быть рассмотрен как автоматизированный процесс инспектирования кода, однако в отличие от процесса инспектирования статический анализ может обладать следующими преимуществами: минимизация человеческого фактора на стадии анализа, снижение стоимости проверки за счет человеко-часов, упрощение просмотра больших участков кода.

Существует несколько программных инструментов для статического анализа исходного кода, такие как Svace, Coverity Prevent, Klocwork Insight, PVS-Studio, PyCharm, Pylint и т.д. Представленные решения различаются по поддержке соответствующих языков программирования и спецификации поддерживаемых типов ошибок. Большая часть решений специализируется на поддержке языков со статической типизацией. Следует отметить, что такие возможности как интегрированные среды разработки с навигацией по коду, автодополнением широко распространены для языков со статической типизацией, такие как C#, C++, Java, но недоступны для языков с динамической типизацией, таких как Python, PHP, Perl, JavaScript. Это обусловлено некоторыми особенностями статического анализа языков с динамической типизацией. Отличительной чертой динамической типизации является отсутствие связывания переменной с типом до момента присваивания значения. По этой причине невозможна прямая проверка соответствия типов на стадии статического анализа, одним из альтернативных решений для анализа является использование механизмов вывода типов, однако такие механизмы не совсем точны. Данные подходы используются в среде разработки для Python PyCharm компании JetBrains, также такое решение было использовано в инструменте TIRPAN - разработке Института системного программирования Российской академии наук, дополнением к которому является данная работа. Описанный подход позволяет выявить некоторые типы ошибок, но имеет недостатки. Недостатками при полном выводе типов является ресурсоемкость по памяти, а также быстродействие. Поэтому было предположено ограничить необходимость вывода типов, попытавшись сузить общую задачу поиска несоответствия типов до более частных задач, а также исследовать, в какой мере использование приближенных подходов при работе с типами влияет на результаты анализа. Для этой цели в данной работе рассматривается возможность адаптации техник статического анализа, использующихся для программ, написанных на языках со статической типизацией для анализа программ на языках с динамической типизацией.

В представленной работе рассмотрен анализ программ написанных на языке Python. Python является высокоуровневым языком программирования и имеет динамическую типизацию. Последнее время, наблюдается рост популярности использования языка Python, согласно индексу TIOBE по состоянию на апрель 2016 Python входит в десятку самых популярных языков программирования, поднявшись за последний год с восьмой на пятую позицию [15]. Многие широко известные программные решения написаны на Python, такие как Django, Youtube, Dropbox, BitTorrent и т.д. Помимо прочего часть этих решений является достаточно объемными программами (включающие более ста тысяч строк), что обуславливает необходимость средств автоматизированного анализа качества данного кода.

Работа является продолжением работы курсовой работы “Checker for Static Detection of Erroneous Member Access to None-values in Python Programs”, в которой было заложено начало внутрипроцедурного анализа, однако результаты работы показали необходимость последующей разработки модуля внутрипроцедурного анализа и применения межпроцедурного анализа. В рамках данной выпускной квалификационной работы была поставлена цель -- исследовать применение классических подходов статического анализа к поиску ошибок в программах на языке Python связанных с ошибками обращения к элементам None-значений. Для реализации поставленной цели были выделены следующие задачи:

1. Изучение техник статического анализа;

2. Изучение особенностей языка Python;

3. Изучение специфики использования None - значений в программах на языке Python

4. Разработка прототипа поиска соответствующих типов дефектов (Checker);

5. Анализ полученных результатов Checker-а на проектах, с открытым кодом реализованных на языке Python.

Работа структурирована следующим образом: в первой главе рассмотрены инструменты статического анализа кода, виды дефектов, а также существующие решения статического анализа программ на языке Python. Во второй главе описаны примененные алгоритмы анализа, в третьей главе вынесены результаты по реализации решения, в четвертой приведен анализ полученных результатов. В Приложениях приведены схемы и таблицы: диаграмма классов модулей инструмента.



Глава 1. Статический анализ языка программирования Python

В данной главе приводится описание существующих техник статического анализа кода, рассматриваются виды дефектов и приводятся описания существующих решений статического анализа для языка Python.

1.1 Инструменты статического анализа кода

Статический анализ кода - анализ программного кода, производимый без выполнения исследуемой программы. Статический анализ, как правило, выполняется не непосредственно на исходном коде программы, а на некотором промежуточном представлении кода. Традиционные фазы разбора исходного кода: анализу кода предшествует синтаксический разбор, используемый после лексического разбора, группирующего лексемы и строящий токены, передаваемые синтаксическому анализатору (Рисунок 1)[1]. После семантического анализатора исходный код представлен в виде синтаксического дерева, в котором каждый внутренний узел представляет операцию, а дочерние узлы - аргументы этой операции. В Python существует стандартный модуль для генерации AST (абстрактного синтаксического дерева) по исходному коду на языке Python. Далее для некоторых узлов вычисляются семантические характеристики или строится дополнительное промежуточное представление. В настоящей работе реализованный модуль выполняет анализ по MIR (Medium Level Intermediate Representation). Уже на уровне синтаксического дерева, возможно, выявление некоторых классов ошибок[19,21], чаще всего связанное с особенностями использования определенных конструкций кода. Но для более сложных видов дефектов необходимо выявить дополнительную информацию в ходе исполнения кода, для этого моделируется поток данных и формируется граф потока управления.



Граф потока управления (control flow graph- CFG) применяется для формирования путей выполнения программы, определяет последовательность анализа, для выполнения потока управления используется классический подход обхода графа в глубину и принцип доминаторов, или подходы, основывающиеся на концепции сводимости, предоставляющие иерархическое представление (Рисунок 4)[14]. Также к классическому подходу анализа графа потока управления относится направление обхода графа, различаются прямой и обратный порядок обхода графа. Разные порядки обхода графа позволяют получить разную информацию о данных. (Рисунок 5)

Прямой и обратный анализ функции func [22]

Многие дефекты определяются благодаря анализу потоков данных. Анализ потоков данных (data flow graph- DFG [20]) означает методы, собирающие информацию о потоках данных вдоль путей выполнений программы. Например, большинство машинно-независимых оптимизаций основано на анализе потока данных, такие как анализ достигающих переменных, предоставляющий информацию о том, где в программе может быть определена каждая переменная, анализ активных переменных, предоставляющий информацию о том где в программе может использоваться каждая переменная или анализ доступных выражений, основное применение, которого -- поиск глобальных общих подвыражений.

Помимо перечисленных классификаций видов анализа, возможно, выделить следующие типы анализа: внутрипроцедурный и межпроцедурный. Оба этих анализа включают в себя стадии анализа потока управления и анализа потока данных, однако внутрипроцедурный анализ распространяется на область внутри тела функции, в то время как межпроцедурный анализ рассматривает программу в целом, основываясь на информации, передаваемой от вызывающей процедуры вызываемой и обратно.

При переходе от внутрирпоцедурного анализа к межпроцедурному возникает несколько новых задач, усложняющих межпроцедурный анализ. Одной из таких задач является чувствительность к контексту (context-sensitive analysis)[7], так как поведение каждой процедуры зависит от окружающего контекста её вызова. Для упрощения реализации алгоритма существует контекстно-нечувствительный анализ (context-insensitive analysis).

“…Принцип такого анализа заключается в рассмотрении каждой инструкции вызова и возврата как операции безусловного перехода. Мы создаем граф потока управления, в котором помимо обычных ребер внутрипроцедурных потоков управления, имеются дополнительные ребра соединяющие

1.каждую точку вызова с началом вызываемой в ней процедуры

2.инструкции возврата с точками вызова ”[1]

1.2 Дефекты в коде программ на языке Python

В настоящее время существует много решений статического анализа для языков со статической типизацией, самые популярные типы ошибок в этих языках выявлены и находятся в свободном доступе в виде документаций к этим решениям. [2,5]. Однако для языков с динамической типизаций в настоящий момент не так широко распространены общие шаблоны дефектов. В этой ситуации, возможно, рассмотреть сопоставление видов ошибок для языков со статической типизацией в контексте языков с динамической типизацией или попробовать выявить самостоятельные дефекты. Такой обзор произведен в работе [16] В статье рассматриваются, как корреляция между видами ошибок языков статической и динамической типизации, так и анализ ошибок выявленных при анализе Python проектов. В работе было предположено не следовать идее теоретического распространения встречающихся в Си/Си++ дефектов на язык Python из-за несоответствия специфик этих ошибок. Ошибки, выявленные при анализе Python проектов, были разделены на следующие категории простые и сложные.

“Простые” дефекты являлись следствием некорректного использования конструкций языка, такой вид дефектов может быть поддержан на уровне синтаксического дерева, но не так часто встречается в программах, поэтому большему интересу для анализа подвергается тип “сложных” дефектов, “сложные” дефекты были определены как “…дефекты, для обнаружения которых требуется наличие вывода типов”. Такие дефекты чаще встречались на проектах и представляют сферу для исследований в контексте статического анализа.

1.3 Реализации статического анализа программ на языке Python

Как было упомянуто ранее Python язык с динамической типизацией, такой вид типизации усложняет процесс статического анализа кода. Но существует ряд решений, предоставляющий поддержку стадий анализа. Под поддержкой не обязательно подразумевается выявление дефектов, в некоторых реализациях инструменты статического анализа помогают со стилевыми конструкциями, отступами и т.д. Как и во многих языках программирования у языка Python есть свой стандарт оформления кода, некоторый `Style Guide for Python Code', этот стандарт был создан в 2001 году и размещен на официальной странице предложений по улучшению языка Python (Python Enhancement Proposals index 8 - PEP8)[11].

В настоящее время наиболее известными являются следующие инструменты статического анализа Python: Pylint, Pychecker, PyFlakes, PyCharm и т.д.

Pylint является инструментом командной строки и не имеет графического интерфейса, однако может быть интегрирован в среды разработок такие как Eclipse, Emacs, Komodo и PyCharm.

Pychecker похож на Pylint за исключением того, что Pychecker не поддерживает проверки оформления стиля кода, к тому же Pychecker содержит малую часть поддержки PEP8, включающие в себя ограничения на длину строки, пробелы, отступы и т.д

PyCharm является наиболее интересным и полным инструментом, поддерживает проверку стиля, анализ потока данных, построение графа вызовов и т.д. Инструмент реализован на Java, во многом выбор языка реализации связан с поддержкой общих форматов данных решений JetBrains, также это связано с тем, что построение AST средствами Python зависит от версии интерпретатора. Анализ исходного кода происходит по AST представлению, в реализации предусмотрена некоторая поддержка типов, которая осуществляется формированием условных `структурных типов' для тела методов. PyCharm Community имеет открытый исходный код и размещен на github [9]

TIRPAN - Type InfeRence-based Python Analyzer- инструмент статического анализа кода на языке Python, разработка Института системного программирования Российской академии наук. В основе анализа по выводу типов которого был модифицированный алгоритм декартового произведения.[17]

“ При анализе вызовов функций алгоритм декартового произведения АДП работает с мономорфными, а не с полиморфными типами аргументов вызова. Под мономорфным типом понимается конкретный тип, с которым связано выражение по ходу выполнения программы. Примеры мономорфных типов: NoneType, int, класс A. Полиморфный тип для переменной или выражения определяется как совокупность всевозможных мономорфных типов для неё (него)”.[18]

АДП для вызова max(x,y)[7]

В первой главе приведены основные инструменты статического анализа кода, рассмотрены особенности статической и динамической типизации, подходы к анализу и поиску ошибок на языке Python, а также рассмотрены существующие реализации статических анализатор программ на Python.



Глава 2. Внутрипроцедурный и межпроцедурный анализ для поиска дефектов

В главе представлены подходы и алгоритмы, используемые в программной реализации. Описаны необходимые теоретические основы, а также дополнительная информация об алгоритмической части реализации.

2.1 Абстракция потока данных

В текущей работе промежуточное представление кода в основном представлено MIR структурой [Приложение 1]. Для реализации потоков управления по такому представлению необходим алгоритм обхода графа, учитывающий последовательность исполнения конструкций языка. Для решения этой задачи был выбран алгоритм обхода в глубину depth-first search(DFS)[20]. Принцип алгоритма основан на обходе потомков узла в графе перед посещением любого из соседних узлов, не являющимися его потомками.

Направленный граф и его DFG представление[5, 178]

Цифры, выделенные на представлении DFS на графе (Рисунок 8) обозначают номер при последовательности обхода графа и называются глубиной узла. Алгоритм обхода в глубину не обязательно предоставляет единственный путь обхода графа, но это не влияет на исполнение анализа, важно, что анализ происходит последовательно от узлов к предкам вглубь. На практике в работе реализован несколько измененный DFS, отличием является необходимость аккумулирования информации анализа в объединяющих узлах после if ветвлений кода. Поэтому в алгоритм внесены изменения, такие, что последующий анализ от узла объединяющего ветвления кода происходит только после обхода всех узлов вариативных путей.

Для запуска анализа необходимо реализовать вычисление потока данных по графу потока управления. В общем, выполнение программы может быть представлено, как последовательность состояний, состояния подразумевают срез значений всех переменных программы под воздействием определенных инструкций. Состояния под воздействием инструкций можно разделить на состояния перед исполнением инструкции и после выполнения инструкции. Алгоритм организации потока управления обеспечивает обход всех возможных путей исполнения. Затем при обходе путей рассматриваются все возможные состояния узлов, и извлекается необходимая для анализа информация. Линейные конструкции кода содержат общую информацию об изменениях переменных, поэтому могут быть объединены. Объединение линейных участков представляется как базовый блок. Точка программы после исполнений инструкций базового блока совпадает с точкой программы перед следующей инструкцией.

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

Для распространения информации об изменяемых переменных внутри базового блока и для координации информации между блоками вводится понятие передаточных функций [4]. Например, если во входных значениях базового блока переменная имеет значение x и если внутри блока эта переменная присваивается переменной y, то можно утверждать, что значение переменной y после базового блока будет равно x. Такое соотношение между потоками данных и называется передаточной функцией. (Схема 1)

Введем обозначения состояний потока данных:

IN [Bi] - состояние потока данных на входе в блок S, где i-номер блока

OUT [Bi] - состояние потока данных на выходе блока S, где i-номер блока Во введенных терминах при линейном выполнении:

OUT [Bi] = IN [Bi+1]

В случае более сложной организации потока данных (например, if ветвление):

? ?? (OUT[B])= IN[Bi+1]

где входные значения блока - это объединение множеств выходных значений предыдущих блоков, а f- функция ограничений на OUT[B], критериями которой служит информация if-условия. Композиция значений предшествующих блоков выбрана, как объединение, так как задача заключается в анализе информации о возможных присвоениях значениях.

Такой подход определен как “Консерватизм анализа потоков данных”“…Поскольку все схемы вычисляют всего лишь приближения (определяемые всеми возможными путями выполнения программы), следует гарантировать, что любые ошибки будут допущены только в “безопасном направлении”. Стратегия принятия решений безопасна, если она не позволяет изменить результаты вычисления программы…”[8,c.727]



2.2 Аннотации (резюме)

Важной информацией при межпроцедурном анализе является контекст вызова процедуры. Контекст представляет собой информацию о состоянии программы (данных программы) в момент вызова функций. Анализ контекста сильно усложняет межпроцедурный анализ, альтернативой может служить контекстно-нечувствительный анализ, описанный ранее. Для реализации же контекстно-чувствительного анализа используются подходы клонирования или аннотаций.

Клонирование основано на алгоритме, когда для каждого вызова встраивается вызываемый блок кода, то есть копируется представление тела вызова. Анализ продолжается на встраиваемой конструкции.

Аннотации (резюме) - краткое описание, инкапсуляция поведения процедуры. Аннотации могут формироваться в зависимости от нужд конкретного анализа. Использование аннотаций позволяет приблизить принцип межпроцедруного анализа к анализу блоков, областей, так как резюме включает информацию о поведении функции, теоретически эта информация может быть представлена как входное/выходное значение базового блока, тогда возможно применить принцип передаточных функций. Также использование аннотаций функций позволяет исключить анализ поведения функции при каждом её вызове в графе вызовов. Дополнительно формирование аннотаций функций позволяет решить вопрос рекурсии, то есть решить задачу циклических узлов в графе вызовов. Так как аннотации хранят обобщенную информацию о состоянии переменных, то в случае замыкания пути, собственных дуг, возможно итеративно посчитать окончательное значение функции [12].

Алгоритм межпроцедурного анализа с использованием аннотаций (резюме):

“…Анализ состоит из двух частей:

1. Восходящая фаза, вычисляющая передаточную функцию для резюмирования действий процедуры;

2. Нисходящая фаза, которая передает информацию вызывающей функции для вычисления результатов выполнения вызываемых процедур” [13, p.1072]

Отдельное внимание стоит уделить формированию аннотаций. Для автоматического формирования аннотаций необходим внутрипроцедурный анализ, также необходимы некоторые шаблоны, паттерны для формирования предупреждения дефектов. Паттерны должны базироваться на специфике анализа и содержать описание конструкций кода, хранящихся в промежуточном представлении кода (в данной работе это MIR представление), эти конструкции должны порождать возможное формирование дефекта. Таким образом, формирование аннотации (резюме) происходит в следствии процесса DFG обхода тела функции с проверкой конструкций кода на соответствие шаблонам ошибок.

2.3 Граф вызовов

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

Граф вызовов (call graph) - некоторый каркас представления программы, граф программы в котором каждой процедуре и точке вызова соответствует один узел, а каждому возможной точке вызова процедуры x, соответствует ребро от узла процедуры к узлу вызова x.

В большинстве случаев для языков со статической типизацией в представлении графа вызовов каждая точка вызова имеет единственное ребро к процедуре, однако в случае использования процедурных параметров, указателей на функции или в случае с языками с динамической типизацией, до момента выполнения программы целевой код не известен. В этом случае в графе могут присутствовать несколько ребер между точкой вызова и процедурой.

Граф вызовов [1]

В главе были представлены основная теоретическая часть работы, были разобраны алгоритмы организации графа потока управления и потока данных на внутрипроцедурном уровне, а также организаций графа потока управления на межпроцедурном уровне. Были приведены принципы построения основных алгоритмов.



Глава 3. Реализация решения

3.1 Инструменты разработки

В работе использован язык программирования Python, версии 2.7. Выбор языка для реализации основан на программной реализации проекта TIRPAN. Инструмент TIRPAN предоставляет внутреннее представление кода, на котором должен быть произведен запуск модуля по статическому анализу, реализация представления абстрактного синтаксического дерева выполнена на Python 2. В настоящее время существует две версии интерпретатора Python 2 и 3. Последней версией является Python3, однако Python2 широко используется и большое количество проектов, а особенно крупных проектов (Django, Twisted и т.д) реализовано на Python2. Так как реализация внутреннего представления выполнена средствами модуля ast стандартной библиотеки языка Python второй версии [8], то программой поддерживаются только конструкции Python2, и конструкции Python 3 не будут поддержаны.

Дополнительные библиотеки для решения не использованы, для запуска программы достаточно терминала и интерпретатора языка программирования Python.

3.2 Анализ потока данных

До стадии анализа происходит стадия формирования внутренней структуры исходного кода анализируемой программы. Внутренняя структура кода представлена MIR (Приложение 1). Анализ потока данных производится по MIR (внутреннему представлению программы среднего уровня). Анализ осуществляется путем обхода узлов данного графа. В настоящий момент модуль TIRPAN, отвечающий за построение внутреннего представления находится в процессе разработки и хотя он поддерживает генерацию конструкций внутреннего представления ( MIR) для многих конструкций языка Python, но не для всех. В том числе отсутствуют следующие конструкции, оказавшиеся важными для анализа потока данных. Для учета такого рода конструкций, а именно конструкций Module, Import, Import From, Return используются обходчики по представлению AST.

Задачу анализа потока данных рассматривается как задача вычисления некоторого множества fact для каждой вершины графа потока управления. Множество fact можно воспринимать как описание некоторых свойств, которыми обладают данные программы при её выполнении. Для нашей задачи анализа множество fact - это множество в которое помещаются ключевые для анализа значения и переменных.Так при поиске None значений, во множество fact помещаются переменные, возможно, содержащие None значения. Fact множества вычисляются для каждого линейного блока, причем сохраняются состояния fact для входных значений в блок и для выходных значений блока, эти состояния обозначаются как input-output. Такие состояния выделены для обработки нелинейных конструкций, так для оператора if ветвления необходимо объединить fact в вершине объединения ветвлений путей исполнения. Для поддержки цикличных конструкций fact множество позволяет итеративно посчитать множества до достижения неподвижной точки.

В работе выделяются следующие случаи добавления переменной в множество fact: прямое присваивание, следование по соответствующей ветке после проверки переменной на None значение.

Также условием внесения переменной во множество fact служит присваивание переменной значения переменной, находящейся во множестве. Условием исключения из множества соответственно служат присваивания переменной нового значения или же следование потока выполнения по новому пути после проверки переменной на None значение.

Условием формирования предупреждений о наличии ошибок является соответствие некоторому шаблону, конструкции и вхождение советующих переменных во множество “вероятно имеющих None значение” переменных, таким образом, в работе выделены следующие случаи сообщения об ошибках: обращение к полю объекта, имеющего None значение и произведение операций с объектом, имеющим None значение.

Таким образом, существуют правила вычисления фактов в вершинах множества fact и правила проверки на соответствие шаблону предупреждения об ошибке, для запуска внутрипроцедурного анализа остается определить порядок обхода внутреннего представления кода и правила передачи множеств. Согласно представлению об абстракции потока данных, описанных ранее, поток данных разделен на линейные участки. Внутри линейного участка формируется индивидуальное fact множество для блока, в случае нескольких путей исполнения, например if оператор ветвления, требуется определить функцию сложения множеств fact. В работе выбрана функция объединения, чтобы рассмотреть все допустимые присваивания. статический код программный дефект

3.3 Модули реализации

Обход структуры начинается с первого линейного блока к последующим, при этом проверяется, чтобы не происходило обращение к линейным блокам, до посещения всех его предшественников. Для обхода с начального использован шаблон проектирования `посетитель', так как необходимо выполнять операции над разными объектами, а также чтобы не запрашивать тип каждого узла для выполнения просмотра узла. Основным обходчиком, при проходе которого формируются fact множества, является class Visitor модуля None-visitor.(Приложение 2). При обходе, формирующем fact, из соответствующих узлов, которые могу являться началом шаблонов, конструкций, вызывается проверка на соответствие конструкциям и произведение соответствующих операций по формированию предупреждений. Данные классы по проверке соответствия конструкциям, шаблонам размещены в модуле None-Check.

Линейные блоки исполнения

Для проведения внутрипроцедурного анализа достаточно модулей None-Check и None-Visitor. Происходит обход от начального узла, формируется fact для блока, объединяется с предыдущим блоком, рассматривается следующий блок. Внутри блока происходит обход всех вершин, для узлов ClassMisNode и FuncMirNode создаются новые обертки - блоки, запускается анализ блоков внутри тела класса или функции, причем эти блоки, сформированные в теле классов или функций, являются автономными относительно внешних блоков. Получается, что внутри линейного блока не могут быть обработаны узлы CallMirNode, которые обозначают вызов другого участка кода. Для решения этих вопросов реализованы аннотации к функциям и граф вызовов.

В рамках нужд нашего анализа выделяются следующие знания для хранения в аннотациях. Первое, может ли процедура возвращать None значение или нет и второе это внутреннее поведение процедуры. Внутренне поведение процедуры формируется в зависимости от входных параметров функции, а именно фиксируются случаи обращения к полю или проведения операций с переменной имеющей None значение при соответвующих параметрах.

Вычисление аннотаций к функциям происходит отдельным классом AnnotationVisitor модуля None-Visitor, который также по принципу паттерна “посетитель” посещает узлы графа, формируя представление поведения функции. При формировании аннотации к функции учитывается поведение функции, для разных вариантов поступления None значения в какой-либо аргумент функции. Для этого происходит обход тела функции с соответствующим содержанием fact множества, и фиксируются переменные и их расположение в функции, относительно которых будут вызваны предупреждения об ошибках.

Помимо информации о зависимости потока данных от входных параметров аннотации содержат сведения о возвращаемых значениях функций. Return конструкции не поддержаны в MIR представлении, поэтому для их формирования производится обход AST представления кода функции, так как для AST представления нет анализа потока данных, то при обходе фиксируются имена всех возможных return, а после сверяются с fact множеством в конечной точке линейного блока и формируется общая для всей функции Boolean переменная, обозначающая возможность возвращения None значения. общая для всей функции Boolean переменная, обозначающая возможность возвращения None значения.

После завершения обхода AnnotationVisitor формируется общая таблица всех аннотаций к функциям, чтобы не возникло коллизий, а также, чтобы в дальнейшем было возможно связать вершину графа вызова с необходимой аннотацией функций, то производится определение пространства имен расположения функции, которое используется для записи в общую таблицу.

Язык программирования Python не имеет строгой типизации, поэтому в рамках построения графа вызовов возникает некоторые особенности относительно классического подхода построения графа вызова. Например, вызов метода может соответствовать любому одноименному методу в пространстве имен. В такой ситуации было выбрано решение о сопоставлении всех одноименных методов и функций с соответствующим количеством входных аргументов. Это значит, что в графе вызовов вершина может иметь несколько дуг.

Построение графа вызовов осуществляется в модуле CallGraph. Класс CGVisitor отвечает за формирование графа вызовов, содержит общую таблицу вершин и таблицы зависимостей (определения и использования) вершин. Класс CGNode, представляет собой вершину графа вызовов, уникальность вершины определяется ее пространством определения namespace и именем name.Такое представление соответствует принципам языка Python, так как в Python исключен полиморфизм функций, при наличии функций с одинаковым именем вне зависимости от параметров в рамках одного пространства имен `поздняя' функция перезапишет объявление одноименной функции находящейся выше по коду. В общую таблицу всех вершин класса СGVisitor - nodes, содержатся все объявления вершин. Таблица определений - defines - содержит зависимости между объявленными вершинами. Например, когда в модуле содержится класс, то формируется вершина-объявление для названия модуля, и вершина-объвление для названия класса, обе эти вершины соединяет ребро объявления. Отношения объявления могут присутствовать только у объектов типа ClassMirNode, FuncMirNode. Также в классе CGVisitor содержится таблицы - uses, где располагается информация о возможных использованиях вершин одна другой, такие зависимости могут присутствовать для Import, ImportFrom, CallMirNode объектов.

Граф вызовов формируется по всем модулям, включенным в анализируемый проект. Изначально производится формирование всех основных узлов, только после этого расставляются возможные ребра соответствия вызываемой функции, до этого пространство вызова является неизвестным.



Представление графа вызова до этапа связывания (серыми линиями обозначены `определяющие' ребра, черными `использующие' ребра)

При инициализации ребер между вершинами помимо имени учитывалось количество входных параметров. Для каждого модуля были разработаны наборы юнит-тестов для проверки корректности реализации.

В главе приведены основные инструменты реализации. Описаны принципы действия и особенности реализации (паттерны проектирования, диаграммы классов). Приведен обзор модели построения аннотация, анализа потока данных и построения графа вызовов.



Глава 4. Полученные результаты

Для апробации инструмента были выбраны следующие Python проекты: Django, Tactic, Twisted. При выборе проектов учитывалась версия языка программирования Python на котором написаны проекты, объём проектов и условие открытого исходного кода[6].

4.1 Примеры найденных предупреждений

Предупреждения внутрипроцедурного характера:

Таблица 2. Статистика выявленных предупреждений при применении внутрипроцедурного анализа

	Raise	Call	Return	For (iterator)	Try/Except
Django	1	11	6		2
TACTIC	3	15	1	1
Twisted	1	4	1

В Таблице2. приведены цифры, полученные при запуске внутрипроцедурного анализа на проектах. Для большинства проектов число предупреждений превысило количество шестидесяти, в этом случае были рассмотрены двадцать произвольных предупреждений. Все предупреждения были проанализированы и разделены на отдельные категории, соответствующие контексту их вызова.

Raise конструкция. Пример, когда поток данных может прерываться, еще до точки выхода из процедуры, как показывает статистика, такие решения часто используются для проверки на None значения, а значит, возможно, должны быть учтены в конструкции внутреннего представления. Также прерывать поток данных могут Return, Try/Except конструкции, следовательно, их учет улучшит качество анализа.

Call конструкции, под этой категорией подразумевается вызов метода или функции, возвращаемое значение которых может присваивается переменным находящихся в fact множестве. Как показывает статистика, такие ситуации чаще всего встречаются в предупреждениях об ошибках, однако они не могут быть поддержаны на внутрипроцедурном уровне, а значит необходимо применение межпроцедурного анализа.

Также интересной с точки зрения анализа является ситуация, когда может происходить экранирование переменной. Одну из ситуаций экранирования выявило в случае итерации по списку.

Предупреждения межпроцедурного характера.

Таблица 3. Статистика выявленных предупреждений при применении внутрипроцедурного анализа

	Constructor call inside procedure	Import	Input	Self
Django	1	7	8	17
TACTIC	3	30
Twisted		5	20	8

В Таблице 3. приведены цифры, полученные при запуске межпроцедурного анализа на проектах. Для большинства проектов число предупреждений превысило количество двухсот. Для анализа было выбрано сто произвольных предупреждений по всем проектам. Все предупреждения были проанализированы и разделены на отдельные категории, соответствующие контексту их вызова.

Self конструкция. Python имеет полноценную поддержку объектно-ориентированного программирования [10]. Классы создаются зарезервированной конструкцией class, существует метод __init__, который приближенно можно назвать конструктором. Чтобы создать методы необходимо первым аргументом указывать параметр self, но он не указывается при вызове объекта. При вызове метода self указывает на экземпляр класса, для которого вызывается метод. Таким образом, внутри тела метода зарезервированы методы, которые могут быть вызваны от конструкции self, эти методы будут находиться в текущем классе или классах предках. Поэтому в рамках анализа, выделенная конструкция является интересной информацией (наличие self может сократить uses ребра в графе вызовов) для дальнейшего рассмотрения и поддержания в инструменте.

Input/Import категория. Такая ситуация очень часто встречается в выделенных предупреждениях, однако является трудной для поддержки. В данной категории рассматриваются входные параметры процедуры и непосредственное обращение к полям переданного параметра без какой-либо проверки на наличие поля. В данном случае невозможно оценить наличие поля у объекта без определенной поддержки типов.

Constructor call inside procedure. В этой категории рассматривается ситуация, когда внутри процедуры создается объект, а потом вызывается метод этого объекта и/ или присваивается какое-либо значение. В этой ситуации не возможно точно определить, какая процедура вызывается, однако возможно попробовать сократить ребра путем привязки к классам на основании стиля PEP8.

Статистика.

В Таблицах представлены данные, собранные при анализе проектов.

Таблица 4. Статистика использования None значений и общие данные

	procedures	if-node with None identity	if-node with None equality	None returns
Django	3370	654	0	76
TACTIC	12808	339	820	279
Twisted	764	125	0	18

Таблица 4. содержит количественные показатели проектов, относящиеся к использованию None значений, `Procedures' обозначает общее количество всех процедур, содержащихся в проекте. `if-node with None identity' обозначает конструкцию проверки на None значение (is None), `if-node with None equality' - проверка на None значение (==None, такая конструкция является плохим стилем для Python, однако как показывает статистика используется разработчиками), `None returns' - количество процедур напрямую возвращающие None значение.

Таблица5. Статистика использования функций и методов

	methods	functions	%functions
Django	2676	694	0,21
TACTIC	593	12215	0,95
Twisted	505	259	0,34

Таблица отображает общее количество все функций и методов в проектах, выделено процентное соотношение использования функций (процедур не связанных с объектом) и методов. В общем случае, чаще всего используются именно методы.

Таблица 6. Статистика использования уникальных имен процедур

	unique procedures names	repeated procedures names	%procedures name repeats
Django	2409	961	0,29
TACTIC	10080	2728	0,21
Twisted	630	134	0,18

В главе приведены основные результаты применения алгоритма на проектах с открытым исходным кодом, приведены статистические данные по объему проектов, процентному соотношения использования методов и функций, а также использования уникальных имен процедур. Приведен анализ полученных предупреждений на проектах, произведена классификация предупреждений на основе их происхождения.



Заключение

Статический анализ кода языков с динамической типизацией является достаточно сложной задачей, для решения который в настоящее время не существует классических подходов. Однако возрастающая популярность использования языков с динамической типизацией индицирует актуальность таких исследований.

В рамках выполнения выпускной квалификационной работы была разработан инструмент статического анализа программ на языке Python, позволяющий оценить использование None-значений в программе до этапа её выполнения. Для реализации программы был разработан механизм построение графа вызовов программы, позволяющий оценить взаимодействие между функциями, разработан инструмент по оценке поведения процедур, в контексте нужд анализа, формирующий аннотации. Был разработан модуль по анализу потока данных, также были разработаны тесты для контроля качества каждого из модулей.

Помимо разработки инструмента были рассмотрены классификации статического анализа кода, изучены методы и подходы статического анализа кода.Таким образом, в процесс выполнения выпускной квалификационной работы были решены следующие задачи:

1. Изучены техники статического анализа;

2. Рассмотрены особенности динамической типизации языка Python;

3. Собрана статистика и изучены данные по использованию None - значений в программах на языке Python;

4. Разработан прототип поиска ошибок доступа к None-значениям;

5. Проведена апробация разработанного инструмента на проектах с открытом кода и произведен анализ полученных результатов.

Направления дальнейшей работы включают в себя реализацию конструкций MIR представления, необходимость которых была выявлена в ходе произведенного анализа, а также модификация модуля анализа потока данных в соответствии с внедрением новых конструкций.



Список использованных источников

1. V. Aho, M. Lam, R. Sethi, D. Ullman, Compilers: Principles, Techniques, and Tools, Harlow, England: Addison-Wesley, 1986. - 1175с.

2. Cristian Cadar, Koushik Sen Symbolic execution for software testing: three decades later // Communications of the ACM CACM Homepage archive Volume 56 Issue 2. New York, NY, USA: ACM, February 2013 - с. 82-90.

3. Cristian Cadar, Patrice Godefroid, Sarfraz Khurshid, Corina S. Pгsгreanu, Koushik Sen, Nikolai Tillmann Symbolic execution for software testing in practice: preliminary assessment // ICSE '11 Proceedings of the 33rd International Conference on Software Engineering: New York, NY, USA, 2011. С. 1066-1071.

4. Manuvir Das, Sorin Lerner, Mark Seigle ESP: path-sensitive program verification in polynomial time // PLDI '02 Proceedings of the ACM SIGPLAN conference on Programming language design and implementation. ACM New York, NY, USA : 2002. С. 57-68.

5. Reps, T.: Program analysis via graph reachability. Information and Software technology 40 (11-12), 1998, 701-726c.

6. S. Muchnick, Advanced Compiler Design and Implementation, Morgan Kaufmann, San Francisco, Calif., 1997. - 857с.

7. Sorin Lerner, David Grove, Craig Chambers Composing dataflow analyses and transformations // POPL '02 Proceedings of the 29th ACM SIGPLAN-SIGACT symposium on Principles of programming languages. Jan. 2002. с. 270-282.

8. И.Е.Бронштейн, Исследование дефектов в коде программ на языке Python: в том.24 Труды Института системного программирования, 2013 - c.25-32.

9. И.Е.Бронштейн, Вывод типов для языка Python: в том.24 Труды Института системного программирования, 2013. - c. 161-190.

10. И.Е.Бронштейн, Подход к обнаружению ошибок несоответсвия типов в коде на динамических языках программирования : в том.25 Труды Института системного программирования, 2013. - c. 67-84.

11. В.П. Иванников, А.А. Белеванцев, А.Е. Бородин, В.Н. Игнатьев, Д.М. Журихин, А.И. Аветисян, М.И. Леонов, Статический анализатор Svace для поиска дефектов в исходном коде программ.: в том 26. Труды Института системного программирования, 2014. - c.231-250.

12. Кормен, Томас Х. Алгоритмы: построение анализ, 3-е изд.: Пер. с англ.-М. :ООО “И.Д.Вильмс”, 2013. - 1328 с.

13. С.В. Сыромятников, Декларативный интерфейс поиска дефектов по синтаксическим деревьям: язык KAST: том 20 Труды Института системного программирования, 2011. - c.51-68.

14. С.В. Сыромятников, Применение языка KAST для преобразования исходного кода и автоматического исправления дефектов: том 25 Труды Института системного программирования, 2013. - c.51-66.



Приложения

Приложение 1

Приложение 2

Диаграмма классов. Модуль None-Visitor.



Приложение 3

Диаграмма классов. Модуль None-Check.

Размещено на Allbest.ru

...