автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.18, диссертация на тему:Разработка алгоритмов и моделирование динамической типизации в программах для технических систем

На правах рукописи

Старцев Евгений Владимирович

РАЗРАБОТКА АЛГОРИТМОВ И МОДЕЛИРОВАНИЕ ДИНАМИЧЕСКОИ ТИПИЗАЦИИ В ПРОГРАММАХ ДЛЯ ТЕХНИЧЕСКИХ СИСТЕМ

Специальность 05.13.18 — Математическое моделирование, численные методы и комплексы программ

АВТОРЕФЕРАТ

на соискание ученой степени кандидата физико-математических наук

005560800

1 8 МАР 2015

Челябинск - 2015

005560800

Работа выполнена на кафедре компьютерной безопасности и прикладной алгебры ФГБОУ ВПО «Челябинский государственный университет»

Научный руководитель: Пустыгин Алексей Николаевич,

кандидат технических наук, доцент

Официальные оппоненты: доктор физико-математических наук, профессор

Крымский Валерий Вадимович, ФГБОУ ВПО «Южно-Уральский государственный университет» (национальный исследовательский университет), профессор кафедры электротехники,

кандидат физико-математических наук, доцент Лядова Людмила Николаевна, Пермский филиал ФГАОУ ВПО «Национальный исследовательский университет «Высшая школа экономики», доцент кафедры информационных технологий в бизнесе

Ведущая организация: ФГБУН Институт математики и механики

им. H.H. Красовского Уральского отделения РАН

Защита диссертации состоится «16» апреля 2015 года в 14 часов на заседании диссертационного совета Д 212.296.02 при ФГБОУ ВПО «Челябинский государственный университет» по адресу: 454001, г. Челябинск, ул. Братьев Кашириных, 129, конференц-зал.

С диссертацией можно ознакомиться в научной библиотеке ФГБОУ ВПО «Челябинский государственный университет».

Автореферат разослан « » марта 2015 г.

Ученый секретарь диссертационного совета, доктор физ.-мат. наук

В.Е. Федоров

Общая характеристика работы

Актуальность темы исследования

Значение программного обеспечения в наши дни достаточно велико. Объем существующего программного кода во всем мире превышает миллиарды строк. Это не только коммерческие разработки, исходный код которых - это закрытая собственность корпораций, но и программное обеспечение с открытым программным кодом(Ореп Source). Доступ к исходному коду таких программ может получить любой желающий. Сложно оценить объем кода в закрытых коммерческих разработках, но объем исходного кода ядра Linux - одного из наиболее известных open-source продуктов превышал 12 миллионов строк уже в 2009 г, что говорит о гигантском объеме разработок. Исходный код крупных коммерческих разработок, таких как операционная система Windows от Microsoft последних версий может содержать еще больший объем исходного кода.

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

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

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

модель исходного кода, жестко привязанную к входному языку, что ограничивает их применение, потому что реализованный метод анализа неприменим к программам, написанным на других языках программирования. Например можно отметить инструменты cppcheck или FindBugs, предназначенные для анализа программ на С++ и Java, соответственно. В таких условиях, методы анализа не могут быть использованы повторно, что затрудняет их развитие. По этой причине имеется множество инструментов статического анализа, решающих похожие задачи для разных языков программирования. В частности, существует немало инструментов поиска ошибок для разных языков программирования. Набор типовых ошибок, которые может находить каждый конкретный инструментарий, зачастую уникален. Многие типы ошибок характерны для конкретного, языка, но также существует множество типовых ошибок, характерных для различных языков программирования, работу с которыми каждый инструмент реализует по своему (работа с не инициализированными данными, выход за границы массива и пр.). Как правило в роли анализируемой модели исходного кода выступает абстрактное синтаксическое дерево. Данное представление жестко привязано к грамматике языка, для которого оно строится, что и затрудняет применение алгоритмов анализа этого представления для других языков. Решением позволяющим преодолеть узкую ориентированность современных средств статического анализа может выступить использование универсальных представлений, т. е. представлений, поддерживающих более одного входного языка. Благодаря этому можно будет перенести акцент на реализацию более совершенных алгоритмов анализа, каждый из которых будет доступен сразу для группы входных языков, которые поддерживает универсальное промежуточное представление. Это одна из главных особенностей разработанных в рамках диссертационного исследования инструментов статического анализа, что определяет актуальность разрабатываемого комплекса программ.

Кроме того за время своего развития для таких популярных и имеющих длительную историю языков как С или С++ появилось немало инструментов статического анализа. Но с 90-х годов стали получать распространение динамические языки программирования, такие как Python или Ruby. Их основным отличием является то, что разработчику не требуется указывать типы данных переменных в исходном коде программ. Многие разработчики переходят на использование таких языков и количество программ написанных на этих языках стремительно растет из-за простоты их использования. Динамическим языкам свойственно то, что гипы объектов в программе не могут быть в явном виде извлечены из исходного текста программ, как в языках C/C++ или Java, они могут быть известны только на момент

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

Степень разработанности темы исследования

Область статического анализа берет свое начало с 70-х годов XX века, благодаря исследованиям Кусо на тему абстрактной интерпретации в статическом анализе и систем верификации программ а также Аллена - на тему анализа потока управления и данных в компиляции и статическом анализе. Одним из первых инструментов статического анализа является утилита lint для статического анализа программ на языке С.

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

На основе статического анализа может быть выполнена верификация - доказательство корректности программы с той или иной точки зрения. Можно отметить работы Остервейла, Маджумдара, Чернова, Ицыксона. В работе Бейера затронут вопрос верификации исходного кода драйверов для операционной системы Linux, также с этой темой связаны работы Мутилина, Новикова, Хорошилова.

Вопросы реверс-инжинеринга и реинжинеринга затронуты в работах Кошке, Ицыксона.

Среди исследований, посвященных построению инструментов анализа для нескольких языков можно выделить работы Кошке и Церански - исследователей из проекта Bauhaus.

Область статического анализа программ на динамических языках программирования тесно связана с областью вывода типов в языках программирования, в которой можно отметить работы Хиндли, Милнера, Дамаса, Пальцсберга и Шварцбаха, Агесена и Бронштейна.

Цели и задачи

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

Для достижения этой цели нужно решить следующие задачи:

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

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

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

4. Разработать промежуточное представление на основе предложенных требований и разработанной математической модели.

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

6. Разработать численные методы для проверки адекватности предложенной математической модели типов для языка программирования Python.

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

Научная новизна

1. Разработана математическая модель универсального классового промежуточного представления (UCR), позволяющая анализировать классы и связи между ними в объектно-ориентированных языках программирования.

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

3. Предложен численный метод проверки адекватности математической модели типов на основе данных натурного эксперимента.

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

Теоретическая и практическая значимость работы

1. Практическая реализация генерации универсального классового представления(иСЯ) и универсального представления потока управления(иСРК) из исходного кода на языке программирования Python.

2. Программная реализация алгоритма и численного метода вывода типов на основе предложенной математической модели.

3. Реализованы инструменты визуального анализа архитектуры наследования на основе универсального классового представления.

4. Программная реализация методики срезов представлений для универсального классового представлсш1я(иСЯ) и универсального представления потока ynpaBneniM(UCFR). Реализованы срезы UCR И UCFR (в том числе при совместном использовании представлений); срез представления UCR на основе отношений наследования; срез представления UCFR на основе связей вызовов между функциональными блоками; срез представления UCFR на основе критериев представления UCR (срез классов UCFR); срез представления UCR на основе критериев представления UCFR (срез создаваемых объектов UCR).

5. Реализован численный алгоритм проверки адекватности математической модели типов в динамических языках программирования на основе динамического анализа программ на языке программирования Python.

Методология и методы исследований

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

Положения, выносимые на защиту:

I) Разработана математическая модель - для описания программ, написанных на объектно-ориентированных языках программирования, и универсальное

промежуточное представление на ее основе.

2) Разработана математическая модель типов, являющихся классами исследуемого проекта для языков с динамической типизацией. На основе данной модели реализована методика вывода типов для языка программирования Python.

3) Предложен численный алгоритм для вывода типов на основе предложенной модели с использованием нечетких множеств.

4) Предложен численный метод проверки адекватности модели типов на основе данных натурного эксперимента. Выполнена реализация такой проверки на основе вычислительного эксперимента с использованием динамического анализа для языка программирования Python.

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

Степень достоверности и апробация результатов

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

Результаты диссертационной работы докладывались и обсуждались на седьмой международной конференции «Свободное программное обеспечение в высшей школе» (Переславль-Залесский, 2012 г.); на семинаре научно-Практического Центра СКВ и ОПО ФГОУ ВПО «ЧелГУ» (Челябинск, 2012 г.); на второй международной научно-практической конференции «FOSS Lviv-2012» (Украина, Львов, 2012 г.); на восьмой международной конференции «Linux Vacation / Eastern Europe» (Беларусь, Гродно, 2012 г.); на восьмой конференции «Свободное программное обеспечение в высшей школе» (Переславль-Залесский, 2013 г.); на научно-практической конференции «Тверские интернет технологии» (Тверь, 2013 г.); на девятой конференции «Свободное программное обеспечение в высшей школе» (Переславль-Залесский, 2014 г.); на семинаре сектора визуализации ОСО ИММ УрО РАН (Екатеринбург, июнь и октябрь 2014 г.); на семинаре кафедры системного программирования ЮУрГУ (Челябинск, ноябрь, 2014); на семинаре кафедры компьютерной

безопасности и прикладной алгебры ЧелГУ (Челябинск, декабрь, 2014); на научном семинаре по теории операторов и дифференциальным уравнениям под руководством профессора В.Е. Фёдорова на кафедре математического анализа ЧелГУ.

Все результаты диссертации получены лично автором, В совместных работах с А.Н. Пустыгиным научному руководителю принадлежат постановка задачи и общее руководство. Из совместных статей с М.В.Зубовым использовались только результаты, полученные лично автором диссертации.

Основное содержание диссертационной работы

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

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

1. Представление предназначено для анализа объектно-ориентированных языков программирования. Представление должно обеспечивать возможность анализа таких сущностей как классы и связи между ними без выполнения дополнительных преобразований представления.

2. Возможность использовать представление для описания программ на нескольких входных языках (универсальное представление).

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

4. Формат пригодный для восприятия человеком. Формат должен обеспечивать возможность ручной обработки - исследования представления, без привлечения машинной обработки.

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

6. Уникальная идентификация элементов представления. Это необходимо для избежания коллизий любого рода при анализе.

Приведена характеристика промежуточных представлений, используемых в

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

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

Множество всех идентификаторов классов анализируемого проекта представляется множеством UCR_ID . Основную информацию о классах в проекте представляет отношение S .

S={{с, п, file, line, col)\ , где c6UCR_ID , п - имя класса, file - имя файла, line - номер строки, со/ - позиция в строке.

Обозначим за F множество всех возможных имен полей классов, множество модификаторов видимости - MF .Определим отношение D£UCRJDXFXMF , в которое входят все пары идентификаторов классов, полей , принадлежащих этим классам, и их модификаторов видимости(1).

D={(c,f,mf)},cSVCR_lD,fsF,mfeMF (1)

Определим отношение £SUCR_IDxMxMF , в которое входят все пары классов, методов, принадлежащих этим классам, и их модификаторов видимости(2).

E=\(c,m,mf)\],meM,ceVCRJD,mfeMF (2)

Наибольший интерес представляют связи агрегации между классами проекта. Отношением ассоциации между двумя классами называют структурное отношение, показывающее, что объекты одного типа неким образом связаны с объектами другого типа. Отношение (связь) агрегирования между двумя классами - это особый вид ассоциации, демонстрирующий отношение «часть-целое». Он показывает, что внутри одного класса содержатся поля, в которых хранится объект, тип которого является другим классом.

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

Связи агрегации определяются в виде отношения:

и

I=((c,f.t)} , где ceUCR_ID - агрегирующий класс,

fsF - агрегирующее поле, teUCR_ID - агрегируемый класс.

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

На данный момент можно отметить следующие алгоритмы вывода типов:

1. Алгоритм Хиндли-Милнера

2. Алгоритм Декартова произведения

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

Основные шаги существующих алгоритма вывода типов могут быть представлены в виде следующего списка:

1. Извлечение ограничений на типы выражений из исходного кода, в виде того, что какая-либо составная часть выражения соответствует определенному типу (абстрактному или конкретному).

2. Построение в том или ином виде множества этих ограничений и вывода типов заключающегося в разрешении этого множества ограничений на основе правил вывода типов (например ограничения представляются в виде ориентированного графа). Алгоритм состоит из двух фаз - извлечения ограничений типов и решения системы полученных уравнений.

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

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

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

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

Введем множество всех возможных сигнатур классов S (3): S=[(Fs,Ms)\VFsZF,VMsQM} , (3)

где S - множество всех возможных сигнатур классов.

Определим множество характеристических сигнатур интересующих полей(4).

X=j(c,/,i).je5},V(c,/)eD , (4)

где X - множество характеристических сигнатур интересующих полей.

Формула 4 определяет для класса с и принадлежащего ему поля / сигнатуру s . Эта сигнатура характеризует некоторый класс, объект которого потенциально может храниться в этом поле. В данную сигнатуру входят те поля и методы, к которым происходило обращение в области видимости данного поля, т. е. в методах класса, которому принадлежит

данное поле.

В ходе работы алгоритма для каждого интересующего поля выполняется поиск кандидатов. Определим отношение подобранных алгоритмом типов //ЕСХ/^ХС . Он представляет собой множество всех троек из класса проекта, его поля и класса, подобранного алгоритмом в качестве, кандидата для данного поля. Опишем, как формируется это множество алгоритмом вывода типов на основе отношений X, Б и Е. Для некоторого класса с, обозначим за Рс - множество полей этого класса, а за Мс - множество его методов. Выполняется условие (5).

/1е^|и,бМс=>(с„/()бЛ, (с,, тс) е Е (5)

Запишем условие, при котором данный класс, будет выбран алгоритмом как возможный тип (6).

^^=!(c,/,c,)|э(c,/,(Fd,мrf))ex,^=■0EFc,л/Dcrл/c)V(c,/)s5 (б)

Формула 6 определяет алгоритм подбора классов-кандидатов. В качестве кандидатов подбираются те классы, которые содержат все поля и методы из хотя бы одной характеристической сигнатуры данного поля. В результате работы алгоритма получается множество Я , которое является некоторым приближением к искомому множеству / . Отношение Я представляет базовую модель типов.

Была предложена модель типов на основе нечетких множеств для получения более точных результатов. Для этого было предложено представлять кандидатов для класса поля в виде нечеткого отношения Н , определяемого как показано ниже (7).

НЕСрХРрХСр=(с3,/',сс,цй(с3,/',сс)|с5,ссеСр,/'еРр) (7)

Будет использоваться функция принадлежности >сс) , которая позволяет

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

Вводятся отношения ^г/eCxFxF (8) и У.ЕСх^хЛ/ (9), определяющие все поля и методы, соответственно, интересующих полей к которым происходило обращение в методах класса, которому принадлежит интересующее поле

Y f={{c, f, f ^обращение к палю f ¿утиного поля f классас,[с, f)s.D D, f d&F\ (g)

У m=[{c,f, т)\обращение к методу m утиного поля f классас, (с ,f)eDB,mEM} ^9)

Было предложено 2 функции принадлежности для нечеткого отношения типов полей классов. Первая функция принадлежности была названа «capacity». Сигнатура класса ct.eC - sc-{Fc,Mc),Fc£F, Мсе.И , сигнатура интересующего поля /eF класса cseC - sb=(Fd.Md),FdsF,MdzM . Для определения класса ссеС как кандидата для интересующего поля fsF класса cseC в нечетком отношении Я вводится функция принадлежности /, сс) , которая рассчитывается как показано ниже (10):

|FcnFjt|McnMD! (Ю)

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

Для применения второй функции принадлежности, названной «frequency», вводятся функции т/(с,/в,/),(с,/в)бО и T„(c,/0,m),(c,/D)e.D , которые для каждого используемого интересующего поля fа класса с возвращает количество случаев обращения к полю / и методу т , соответственно.

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

Hc.f)= £ Т/(с././,)+ £ т.(с,/,м(),(с,/)бС которая для каждого класса

(e././Jel", (c./.mjs)-, , V fv V4

возвращает общее количество случаев обращения к полям/методам его интересующих полей.

Тогда для каждого поля /, и метода интересующего поля / класса с

\ х(с,/,/|) , , x(c,f,m,)

можно определить оценочные функции bf(c,f, /()= у) и J-mi)~ ^

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

£ Мс,/,у> £ 6„(c,/,m,)=l,V(c,/)e5 (i././Je',

Определим функцию принадлежности V-/\cs,f,cc) (11) в нечетком отношении Я для определения класса ссе<^ как кандидата для интересующего поля feF класса cssC . Сигнатура класса ссеС - sc=(Fc,Mc). FcsF,Mc^M .

И/(с„/,сс)= Е 8/(cs,/,/,)+ Е 6,„(Cj,/,m() (Н)

f,eFc.{c, .I.Ifer, и J.mjer.

Функция суммирует значения функции ^(с,/,/,) и для тех

интересующих полей и методов, соответственно, класса cseC , которые также имеются у

класса ссеС . Основное отличие функции принадлежности «frequency» связано с тем, что

поля из сигнатуры интересующего поля имеют различный вес в зависимости от частоты

обращений к полю при оценке класса-кандидата.

UCR Logilab

Ba2aarO»jectTracer

i Lo0ifabObje<;iT''acet

Ру .пЮо,ос"'г.аоег

CSUDbg

Ixml

bdb

inspect

Рисунок 1 - Архитектура разработанных инструментов проверки адекватности математической модели типов

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

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

Для оценки базовой модели используется величина /i8=

|г„пн|

Для оценки на основе

аналогичного подхода .модели с использованием нечетких множеств было использовано обычное отношение, получаемое из нечеткого отношения, использующего функцию принадлежности «capacity», как указано ниже (12):

Аналогично для нечеткого отношения, использующего функцию принадлежности «frequency» формировалось множество (13):

Представлены результаты реализации такой проверки для языка программирования

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

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

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

(13)

Python, которые демонстрируют, что предложенная модель типов в динамических языках

Утилиты анализа

Исходное представление

Исследуемое I представление

i ■ СР®3 представления

Средства визуализации

Рисунок 2 - Выполнение срезов представлений

Описаны разработанные инструменты выполнения срезов представлений:

1. Выполнение среза наследования представления 1)СЯ

2. Выполнение среза вызовов представления иСН^

3. Выполнение среза классов представления иСБЯ

4. Выполнение среза создаваемых объектов представления иСЯ

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

Заключение

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

Список работ автора по теме диссертации в журналах, входящих в Перечень ведущих периодических изданий

1. Зубов, М.В. Математическое моделирование универсальных многоуровневых промежуточных представлений для статического анализа исходного кода / М.В. Зубов, Е.В. Старцев, А.Н. Пустыпш // Доклады ТУСУР. - 2014. - №3 (33). - С. 94-99.

2. Зубов, М.В. Численное моделирование анализа исходного- кода с использованием промежуточных представлений / М.В. Зубов, А.Н. Пустыгин, Е.В. Старцев // Вестн. Астрахан. гос. ун-та. Сер.: Управление, вычислительная техника и информатика. -2014,- № 1.-С. 66-74.

3. Зубов, М.В. Применение универсальных промежуточных представлений для статического анализа исходного программного кода / М.В. Зубов, А.Н. Пустыгин, Е.В. Старцев // Доклады ТУСУР, - 2013. - № 1 (27). - С. 64-68.

4. Зубов, М.В. Получение типов данных в языках с динамической типизацией для статического анализа исходного кода с помощью универсального классового представления / М.В. Зубов, А.Н. Пустыгин, Е.В Старцев // Вестн. Астрахан. гос. унта. Сер.: Управление, вычислительная техника и информатика. - 2013. - № 2. -С. 66-74.

Сведения о регистрации программы

Генератор классового представления(иСК) для языка Python. Свид-во о гос. per.

программы для ЭВМ № 2014663482 от 24.12.2014 / Пустыгин А.Н., Старцев Е.В.;

заявитель и правообладатель ФГБОУ ВПО «Челябинский государственный университет».

Другие публикации автора

5. Зубов, М.В. Получение типов данных в динамических языках при статическом анализе / М.В. Зубов, А.Н. Пустыгин, Е.В. Старцев // Тверские интернет-технологии: сб. трудов науч.-пр. конф. - Тверь, 2013. - С. 53-57.

6. Зубов, М.В. Статический анализ ПО с помощью его промежуточных представлений и технологий с открытым исходным кодом / М.В. Зубов, А.Н. Пустыгин, Е.В. Старцев //

Материалы Второй научно-практической конференции FOSS LVIV. - Львов, 2012. -С. 165-168.

7. Зубов, М.В. Подходы к статическому анализу открытого исходного кода / М.В. Зубов, А.Н. Пустыгин, Е.В. Старцев // Сб. материалов Восьмой междунар. конф. разработчиков и пользователей свободного программного обеспечения Linux Vacation / Eastern Europe. - Брест, 2012. — С. 36-40.

8. Зубов, М.В. Построение универсального представления графа потока управления для статического анализа исходного кода / М.В. Зубов, А.Н. Пустыгин, Е.В. Старцев // СПО в высшей шкале: тез. докл. Девятой конф. - Переславль, 2014. - С. 46-51.

9. Зубов, М.В. Выделение типов в универсальном классовом представлении для статического анализа исходного кода / М.В. Зубов, А.Н. Пустыгин, Е.В. Старцев // СПО в высшей школе: тез. докл. Восьмой конф. - Переславль, 2013. - С. 53-58.

Ю.Зубов, М.В. Прототипы построителей промежуточных представлений исходных текстов программ, основанные на компиляторах с открытым исходным кодом / М.В. Зубов, А.Н. Пустыгин, Е.В. Старцев // СПО в высшей школе: тез. докл. Седьмой конф. - Переславль, 2012. - С. 82-86.

11. Зубов, М.В. Краткий анализ и исследование промежуточных представлений исходного текста программ / М.В. Зубов, А.Н. Пустыгин, Е.В. Старцев // Суперкомпьютерные технологии и открытое программное обеспечение. - 2013. - С. 45-53.

12. Зубов, М.В. Сравнительный анализ существующих инструментов исследования программ по исходному коду / М.В. Зубов, А.Н. Пустыгин, Е.В. Старцев // Суперкомпьютерные технологии и открытое программное обеспечение. - 2013. -С. 37-44.

Подписано в печать 13.02.2015. Формат 60x84 1/16. Бумага для множительных аппаратов. Печать на ризографе. Усл. печ. л. 1,16. Тираж 100 экз. Заказ 997.

Отпечатано с готового оригинал-макета в ООО «Абрис-принт» 454008 г. Челябинск, Комсомольский пр., 2, оф, 203