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

1 ^—

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

КНЯЗЕВ Евгений Геннадьевич

Автоматизированная классификация изменений исходного кода на основе кластеризации метрик в процессе разработки программного обеспечения

Специальность 05.13.11. Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

Санкт-Петербург 2009

1 О ДЕК 2009

003487925

Работа выполнена в Санкт-Петербургском государственном университете информационных технологий, механики и оптики (СПбГУ ИТМО)

Научный руководитель: доктор технических наук, профессор

Шалыто Анатолий Абрамович

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

Воробьев Владимир Иванович

кандидат физ.-мат. наук, доцент Новиков Федор Александрович

Ведущая организация: Санкт-Петербургский

государственный университет аэрокосмического приборостроения

Защита диссертации состоится 24 декабря 2009 года в 15 часов 30 минут на заседании диссертационного совета Д212.227.06 в Санкт-Петербургском государственном университете информационных технологий, механики и оптики, 197101, Санкт-Петербург, Кронверкский проспект, д. 49.

С диссертацией можно ознакомиться в библиотеке СПбГУ ИТМО.

Автореферат разослан 23 ноября 2009 г.

Ученый секретарь диссертационного совета

доктор технических наук, доцент -г^С^у, л с Лишцьша

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

Актуальность проблемы

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

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

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

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

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

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

распределения изменений по кластерам существенно сокращает время экспертизы изменений кода.

Задача автоматизации классификации изменений исходного кода решалась многими исследователями: А. Hassan, R. Holt, S. Demeyer, S. Ducasse, S. Raghavan, R. Rohana, J. Maletic, M. Collard, R. Robbes, S. Kim, J. Whitehead и другими. Ими были разработаны методы классификации изменений на базе эвристического, синтаксического, метрического и Data Mininig подходов к анализу изменений.

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

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

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

Основные задачи исследования:

1. Обоснование возможности частичной автоматизации классификации изменений исходного кода методом кластеризации метрик.

2. Разработка метода автоматизированной классификации изменений исходного кода на основе кластеризации метрик изменений.

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

Научная новизна. На защиту выносятся результаты, обладающие научной новизной.

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

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

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

Перечисленные результаты получены в ходе выполнения работ в СПбГУ ИТМО и ЗАО «Транзас Технологии» (Санкт-Петербург).

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

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

Практическое значение работы состоит в том, что все полученные результаты используются в настоящее время и будут использоваться в дальнейшем для повышения качества программного обеспечения в ходе разработки сложных программных комплексов. Предложенный подход применялся для классификации изменений исходного кода в продуктах, разрабатываемых ЗАО «Транзас Технологии» (система мониторинга мобильных объектов Navi-Manager, набор компонент глобальной системы LR1T {Long-Rangé Identification and Tracking) для отслеживания положения судов в мировом океане, система контроля действий студентов на тренажерах e-Tutor 5000), а также в двух программных системах с открытым кодом.

Внедрение результатов. Результаты, полученные в диссертации, внедрены в указанных системах Navi-Manager, LRIT, e-Tutor 5000, а также в учебном процессе на кафедре «Компьютерные технологии» СПбГУ ИТМО по курсу лекций «Современные технологии разработки программного обеспечения».

Апробация результатов. Основные положения диссертационной работы докладывались на научно-методической конференции «Телематика-2007» (СПб., 2007), X международной конференции по мягким вычислениям и измерениям (СПб., 2007), на конференции «Software Egineering Conference (Russia) 2007» (M., 2007), XXXVI научной и учебно-методической конференции профессорско-преподавательского и научного состава СПбГУ ИТМО (СПб., 2007), на семинаре Российского Северо-Западного регионального отделения IEEE по компьютерным технологиям и инженерному менеджменту (IEEE Region 8 Russia North-West Computer Society/Engineering Management Society Joint Chapter) (СПб., 2007), IV и V Межвузовской конференции молодых ученых (СПбГУ ИТМО, 2007, 2008), XV Международной научно-методической конференции «Высокие интеллектуальные технологии и инновации в образовании и науке» (СПб., 2008).

Публикации. По теме диссертации опубликовано 11 печатных работ, в том числе две статьи в журналах из списка ВАК. Результаты, приводимые в диссертации, опубликованные без соавторов, получены лично автором. В работах под номерами 1 и 7 в списке публикаций автором предложены способы использования автоматизированной классификации изменений. В работе 6 автором предложен способ расчета метрики покрытия изменения кода модульными тестами. В работах 2, 3 и 8 автором предложен метод автоматизированной классификации изменений на основе предложенного автором способа расчета метрик изменений и их кластеризации. Остальные результаты в статьях под номерами 1,2,3,7 и 8 принадлежат соавтору.

Структура диссертации. Диссертация изложена на 135 страницах и состоит из введения, трех глав и заключения. Список литературы содержит 95 наименований. Работа иллюстрирована 27 рисунками и содержит 25 таблиц.

Содержание работы

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

1. В первой главе приведен обзор состояния проблемы классификации изменений исходного кода. Известны следующие методы автоматизации классификации изменений исходного кода: 1. Эвристический метод поиска характерных слов в комментариях к изменениям (A. Hassan, R. Holt). 2. Эвристический метод поиска и классификации рефакторингов на основе значений определенных метрик (S. Demeyer, S. Ducasse и другие). 3. Метод сравнения синтаксических деревьев версий кода (S. Raghavan, R. Rohana и другие). 4. Метод анализа синтаксической разницы версий кода с помощью встраиваемых в код тегов (J. Malefic, М. Collard). 5. Метод, основанный на реализации системы контроля версий, которая хранит абстрактные синтаксические деревья кода, полученные на основе данных из среды разработки (R. Robbes). 6. Метод классификации изменений по признаку возможного наличия в них ошибки (S. Kim, J. Whitehead и другие).

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

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

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

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

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

2.1. Исследование возможности автоматизации классификации изменений исходного кода методом кластеризации метрик. Рассмотрим некую программную систему Р в процессе ее развития во времени. Состояние этой системы в каждый момент времени / задается ее текущим кодом Для удобства обозначим множества неизменных состояний 51,, в течение последовательных интервалов времени I е (/г_/,...,/г), через 5Г, где г - целое число, 1 < г < И, N -общее число различных состояний кода. Изменением исходного кода назовем отображение ¿V, переводящее код из предшествующего состояния 8Г.} в модифицированное состояние Б/.

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

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

В общем виде способ классификации множества изменений с трудом поддается формализации. Поэтому задача отнесения изменения к тому или иному

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

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

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

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

Гипотеза 1. Автоматизированная классификация изменений кода некоторой програлтной системы возможна методом кластеризации метрик.

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

Обоснование справедливости данной гипотезы будет приведено в последней главе диссертации на основе экспериментальной ее проверки.

2.2. Метод автоматизированной классификации изменений исходного кода. Автоматизацию классификации изменений исходного кода в данной работе предлагается строить на основе кластеризации метрик изменений.

Схема метода приведена на рис. 1. В качестве входных данных метода используются множество изменений для классификации А = {8Г}, множество экспертных классов С = {с¡} (7 < / < п), набор метрик изменений /а число кластеров к, которое первоначально задается равным числу экспертных классов п.

Выходные данные метода - множество классифицированных изменений. Опишем этапы метода, соответствующие блокам схемы, приведенной на рис. 1.

2.2.1. Экспертная настройка. В процессе настройки экспертом выбирается набор метрик изменений, который позволяет обеспечить заданные уровни Рстт, Естах критериев качества классификации. Описание этих критериев приводится в пунктах 2.2.4, 2.2.7.

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

Рис. 1. Схема метода классификации Рис. 2. Схема алгоритма

изменений исходного кода на основе кластеризации ¿-средних

кластеризации метрик изменений

2.2.2. Вычисление векторов метрик изменений. Для каждого изменения формируется вектор из значений метрик, выбранных на этапе настройки метода. Формулы для расчета значений метрик изменений приведены ниже. На выходе этапа формируется множество векторов метрик изменений {ц8г}.

Назовем метрикой изменения 8Г исходного кода числовую величину ц8г, которая характеризует данное изменение. Эту метрику для кода Я предлагается вычислять по формуле:

где

М5 - метрика изменения. Метрика М3 вычисляется на основе кода, предшествующего изменению $г_!, и измененного кода 5Г. На практике более удобно производить расчет метрик в терминах добавленных, измененных и удаленных строк кода. Обобщим понятие строки кода I как последовательности лексем sis2-.se, где .$г - лексема конца строки.

Каждое изменение §г можно представить в виде совокупности добавленных Ь+, удаленных Ь. и измененных Ь строк кода:

где L' - множество пар <11, Г+>, где /1 - строка до внесения изменения и 1+-измененная строка. В настоящей работе такое представление изменений производится методом поиска редакционного предписания. Редакционное предписание - это последовательность действий по вставке, удалению и замене символов, необходимая для получения простейшим образом из одной строки другой.

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

Зададим функцию СС(1), позволяющую вычислить упрощенную цикломатическую сложность строки кода I как число конструкций языка, управляющих потоком исполнения программы, которые встречаются в строке /:

CC(0 = Z„el [Si&SCF],l<i<n, Здесь {si} - совокупность лексем исходной строки /, и, - число лексем в строке /, Scf - множество лексем, представляющих конструкции управления потоком исполнения программы. Выражение [5] в настоящей работе принимает значение единица, когда значение предиката В истинно, и ноль, когда значение В ложно.

Приведем в качестве примера формулы для расчета метрик цикломатической сложности добавленного СС+, удаленного СС, и измененного кода СС*:

cc+=Xl+eL+cco+), Z<ili;>ei.(cca;)-cc(/-)).

Метрики СС+, СС. рассчитываются по цикломатическим числам добавленной и удаленной строк соответственно. Цикломатическая сложность СС* рассчитывается как разность цикломатических чисел строки до внесения изменения и измененной строки.

Метрики, используемые в диссертации при анализе исходного кода, приведены в табл. 1.

Для каждого изменения 5Г рассчитывается /^мерный вектор метрик, где р -число используемых метрик:

ц5г = <ц,8г, Нр8г>.

Векторы метрик изменений используются для распределения изменений по кластерам.

2.2.3. Кластеризация векторов метрик изменений. На данном этапе формируется множество кластеров изменений Q. Кластеры qjeQ - это непересекающиеся подмножества изменений, объединенные по заданным критериям сходства в процессе кластеризации.

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

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

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

Таблица 1. Метрики изменений кода, используемые в диссертации

Обозначение метрики Описание метрики Обозначение метрики Описание метрики

1. ЮС+ Число добавленных строк кода 7.Г Число измененных файлов исходного кода

2. ЮС. Число удаленных строк кода 8.1+ Число добавленных интерфейсов

3. ЮС' Число измененных строк кода 9.1. Число удаленных интерфейсов

4. СС+ Цикломатическая сложность добавленного кода 10. С5+ Число добавленных классов и структур

5. СС. Цикломатическая сложность удаленного кода 11. С£ Число удаленных классов и структур

6. СС' Цикломатическая сложность измененного кода

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

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

РО1,1>2) = собО],^), со5(171( г2) = ||1?^2||, где V,, векторы метрик изменений, у/— транспонированный вектор Данная мера широко применяется при решении других задач, и оправдала себя, например, для кластеризации текстовых документов. Объекты считаются тем более близкими, чем ближе значение соответствующей меры р к единице.

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

В алгоритме кластеризации векторов метрик изменений используются следующие входные данные: число кластеров к и векторы метрик изменений //¿¡, Выходные данные алгоритма: множество кластеров изменений Схема алгоритма приведена на рис. 2.

Ниже приведено описание работы этого алгоритма.

2.2.3.1. Производится начальное разбиение (¿0> = {q¡0>, q20>,■■■, Як°'} множества объектов {8$ таким образом, чтобы к наиболее далеко расположенных друг от друга изменений были первыми включены в различные кластеры:

Я,(0>=т. я/> = (3, | р(р8„ сд,(0>) = ттир(р8„ сд,<0))}, 2 <] <к, 1<1<К 1< /</,

где И- общее число изменений.

2.2.3.2. Номер итерации / принимается равным единице.

2.2.3.3. Центры кластеров cqj') = {сд}1'} определяются по формуле:

2.2.3.4. Множества распределения объектов по кластерам обновляются по формуле ()п> = {ц}1*}, где:

е т = {8,1 р(р8„ сд/>) = тах,р(р8и сд/')}, 1< / <ДГ, 1 <] < к.

2.2.3.5. Проверяется условие: — = 0. Здесь под знаком "-" понимается операция взятия симметрической разности множеств: А-В = (АиВ)\(АпВ). Если условие выполнено, то процесс завершается и осуществляется переход к шагу 3 и номер итерации I увеличивается на единицу.

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

Этот алгоритм реализован в открытом программном средстве CLUTO (Karypis Lab, University of Minnesota, США). Средство CLUTO используется в настоящей работе для кластеризации метрик изменений. Ниже приводится способ расчета функционала качества кластеризации.

2.2.4. Оценка критерия качества кластеризации. Для оценки качества разбиения изменений на кластеры был выбран функционал 1, как наиболее простая мера «плотности» группировки изменений по кластерам. Этот функционал рассчитывается по следующей формуле:

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

На данном этапе метода проверяется условие превышения значения функционала I над заданным экспертом минимальным уровнем 1тт. Если условие не выполняется, то проводится подбор нового числа кластеров к.

2.2.5. Экспертное сопоставление кластеров изменений классам. На данном этапе каждому кластеру сопоставляется некоторый экспертный класс. При

таком сопоставлении устанавливается соответствие между кластерами д/, <72. •••, <7* и классами изменений с/, с2, ..., с„. В настоящей работе предлагается проводить сопоставление кластеров классам на основании выборочной экспертной классификации изменений из каждого кластера.

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

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

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

2.2.7. Оценка критериев качества метода. Оценка качества метода автоматизированной классификации проводится на проверочном множестве изменений Ле.

Для каждого кластера ^ рассчитываются следующие критерии: чистота Р(д) и энтропия Е(д). Чистота Р(ц1) кластера д) - отношение числа его изменений, принадлежащих экспертному классу с„ соответствующему данному кластеру (<7у —> с,), к числу изменений множества Д, в кластере др Усредненные по всем кластерам значения чистоты Рв и энтропии Ев используются как оценки качества распределения изменений экспертных классов по соответствующим кластерам на всем множестве изменений Л. Критерии чистоты Рд и энтропии Ед используются для проверки гипотезы 1.

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

Формулы для расчета значений чистоты Рд(Ас) и энтропии Ед(А,) разбиения множества изменений Д, по кластерам 2 следующие:

Р0(ле) = ^4еР{Ч)), Р(„) = |

яв(4.) = *Ы =

где Ne - общее число изменений множества Д., п - число классов изменений, к -число кластеров, иеу - число попавших в кластер <7, изменений множества ЛЕ, п) -число попавших в кластер изменений множества Ле, принадлежащих классу с„

rfj - число попавших в кластер qj изменений множества Ла принадлежащих

экспертному классу c"j которому сопоставлен кластер qj. В случае, если п) равно «i

i ni

нулю, то значение члена log также полагается равным нулю.

Чистота P(qj) кластера qj - отношение числа присутствующих в нем изменений экспертного класса, соответствующего этому кластеру, к общему числу классифицированных изменений кластера. Чистота характеризует степень соответствия кластера экспертному классу. Чем большее значение чистоты - тем лучше выполнена кластеризация. Энтропия E(qj) кластера qj характеризует неопределенность соответствия кластера экспертному классу. Чем меньше энтропия, тем лучше полученное решение. Чистота решения, в котором каждый кластер полностью представлен одним классом, равна единице, а энтропия -нулю.

Используем критерии Pq, Eq для проверки гипотезы 1. Для этого переформулируем ее в следующем виде:

Для проверочного множества изменений Ле автоматизированный метод классификации изменений производит такое разбиение изменений по кластерам с последующем сопоставлением их классам, что для заданных уровней РQmin> E*Qmax справедливо следующее неравенство:

РоШ > РQmin' ^Qmax >

где Рд,тт Egmax - допустимые уровни чистоты и энтропии распределения экспертных изменений по кластерам.

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

Разделим заданное множество изменений на М равных частей. Затем исключим первую часть и используем М-1 оставшихся частей как отдельную выборку. Вернем исключенную на предыдущем шаге часть, исключим вторую и используем оставшиеся части с номерами 7 Д..., А/как следующую выборку и так далее. На основе сгенерированных таким образом выборок произведем оценивание статистических параметров.

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

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

3.2. Во втором разделе третьей главы описано внедрение в компании ЗАО «Транзас Технологии» автоматизированной классификации изменений исходного

кода на основе кластеризации метрик. Внедрение выполнено (о чем свидетельствуют акты внедрения) при создании: 1. системы мониторинга мобильных объектов Navi-Manager; 2. компонент системы глобального мониторинга флота LRIT; 3. системы e-Tutor 5000 контроля действий студентов в процессе обучения на судовом, крановом и других тренажерах.

Предлагаемый метод использовался при анализе программных систем с открытым кодом: системы контроля версий Subversion (subversion.tigris.org, CollabNET, США) и объектной обертки над реляционными базами данных NHibernate (./Boss, США).

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

Таблица 2. Входные данные эксперимента по использованию метода классификации изменений в системе М1ПЬегпа1е

Общая информация

Экспертные классы С Удаление кода, реализация новой функциональности, исправление логики, рефакторинг, форматирование кода с изменением комментариев

Метод кластеризации метрик изменений к- средних

Мера близости векторов метрик р Косинус угла между векторами метрик

Набор метрик для кластеризации ц Приведен в табл. 1

Входные данные метода

Общее число классифицируемых изменений 2069

Число классифицированных экспертом изменений 73

Данные настройки метода

Выбранное число кластеров к | 12

Опишем, как выполняется автоматизированная классификация изменений.

3.2.1. В процессе экспертной настройки выбраны метрики, приведенные в табл. 1. Проверочное множество Авя из 68 изменений выбрано следующим образом. Из каждого выделяемого автоматизированным методом класса случайным образом выбрано по 16 изменений. Из 80 полученных отобрано 68 изменений, для которых совпали результаты экспертной классификации двух независимых экспертов.

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

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

3.2.4. Осуществлена оценка критерия качества кластеризации для различного числа кластеров к от 5 до 15. Значение функционала качества кластеризации I увеличивается с ростом значений к. При значении к = 12 достигается наименьший размер самого «плохого» кластера - 547 изменений.

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

3.2.6. Автоматическая классификация изменений на основе сопоставления их кластеров классам проводится на основе предыдущего шага.

3.2.7. Значения критериев качества метода чистоты Р^Аба) и энтропии Ев(л,68) разбиения проверочного множества Д ® по кластерам приведены в табл. 3.

Таблица 3. Распределение изменений проверочного множества по кластерам. Обозначения экспертных классов: «И» - исправление логики, «Ф» - форматирование кода с изменением комментариев, «У» - удаление кода, «Н»- реализация новой функциональности, «Реф.» -

№ кластера / Результат экспертного сопоставления q¡ —> с, Экспертные классы с1 п, Р9 Ер

И Ф Н У Реф.

0 И 9 0 0 1 1 11 0,82 0,37

1 Ф 1 4 0 0 0 5 0,8 0,31

2 Ф 0 1 0 0 0 1 1 0

3 Ф 0 0 0 0 0 0 1 0

4 Ф 1 7 0 0 0 8 0,88 0,23

5 Н 0 0 8 0 0 8 1 0

6 н 0 0 4 0 0 4 1 0

7 н 1 1 1 0 0 3 0,33 0,68

8 У 1 0 0 13 1 15 0,87 0,3

9 Реф. 2 1 0 0 3 6 0,5 0,63

10 Реф. 0 0 0 0 1 1 1 0

11 Реф. 2 2 0 0 2 6 0,33 0,68

Итого 17 16 13 14 8 68 0,78 0,32

В табл. 4 приведены результаты оценки критериев Рс и Ес. Значения в таблице получены, во-первых, объединением строк для кластеров, представляющих один и тот же экспертный класс, расчета Рс(Аби Ес(Аби> для них, и, во-вторых, усреднением полученных значений по пяти экспериментам, проведенным с помощью метода размножения выборок. Уровень значимости при построении доверительных интервалов для значений Рс и Ес принят равным 0,05.

Таблица 4. Усредненные значения критериев качества автоматизированной классификации изменений программной системы ИШЬетШе_

Число классифицированных изменений

340

Качество классификации

Рс = 0,75 ± 0,05 Ес = 0,37 ± 0,06

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

Применение автоматизированной классификации изменений позволило распределить 2069 изменений по пяти классам на основе кластеризации по двенадцати кластерам.

Для сравнения предлагаемого подхода с «чисто экспертной оценкой» приведем следующие цифры. Только 73 изменения были классифицированы для сопоставления кластеров классам в ходе экспертной классификации. Автоматизированный классификатор распределил 53 изменения проверочного множества из 68 по тем же классам, что и эксперты. Следовательно, в результате применения метода удалось существенно сократить затраты времени экспертов на классификацию изменений.

Для изменений проанализированной программной системы подтверждается гипотеза 1 для следующих значений и Евтах автоматизированной

классификации с уровнем значимости 0,05:

PQmi„ = 0,71, EQmax = 0,34, что свидетельствуют о приемлемом качестве автоматизированной классификации для практического применения метода.

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

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

3.3. В третьем разделе третьей главы описано разработанное автором программное средство, реализующее предложенный в диссертации метод. Оно состоит из следующих частей: модуль расчета метрик изменений, указанных в табл. 1 (модуль разработан автором, особенности расчета метрик изложены в п. 2.2.2); модуль поиска редакционных предписаний (рассмотрены в п. 2.2.2) изменений кода (основан на открытой системе контроля версий файлов Subversion); модуль кластеризации с оптимизацией функционала качества разбиения (основан на инструментальном средстве CLUTO, описание которого приведено в следующем разделе).

3.4. Особенности реализации алгоритма кластеризации в программном средстве СШТО описаны в четвертом разделе третьей главы. СШТО -специализированное программное средство, разработанное для кластеризации данных. Его особенностью является возможность задания параметра «число повторений» («Шпак»), который указывает вычислить заданное число кластерных решений различными способами и выбрать лучшее из них на основе максимизации значения функционала качества кластеризации. Это позволяет улучшить качество кластеризации за счет снижения вероятности попадания значения функционала в локальный минимум. Кроме того, инструмент позволяет задавать различные алгоритмы для кластеризации, а также выбирать меру близости объектов кластеризации.

Заключение

В диссертации получены следующие результаты.

1. Обоснована возможность частичной автоматизации классификации изменений исходного кода методом кластеризации метрик.

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

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

4. Разработано программное средство автоматизированной классификации изменений предложенным методом.

Перечисленные результаты получены в ходе выполнения совместных работ СПбГУ ИТМО и ЗАО «Транзас Технологии» и используются как при разработке программного обеспечения сложных систем, так и в учебном процессе.

В работе приводятся результаты сравнения классификаций изменений в программной системе с открытым исходным кодом, выполненные с использованием предложенного автоматизированного метода и вручную. Для этого привлекались эксперты, имеющие опыт разработки сложных программных систем не менее пяти лет. Всего в работе было проанализировано пять программных систем. Исследования показали, что метод позволяет сократить время классификации изменений по сравнению с «чисто ручной» экспертизой (при анализе системы ЫШЬегпШе необходимо классифицировать вручную лишь 73 изменения из 2069) при следующих значениях характеристик качества классификации: чистота Рс= 0,75 ± 0,05 и энтропия Ес = 0,37 ± 0,06.

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

Список публикаций

1. Князев Е. Г., Шопырин Д. Г. Использование автоматизированной классификации изменений программного кода в управлении процессом разработки программного обеспечения // Информационно-управляющие системы. 2008. № 5, с. 15-21. (Журнал из списка ВАК)

2. Князев Е. Г., Шопырин Д. Г. Автоматизированная классификация изменений программного кода методами многомерного статистического анализа // Информационные технологии. 2008. № 5, с. 48-53. (Журнал из списка ВАК)

3. Князев Е. Г., Шопырин Д. Г. Анализ изменений программного кода методом кластеризации метрик // Научно-технический вестник СПбГУ ИТМО. Исследования в области информационных технологий. 2007. Вып. 39, с. 197-208.

4. Knyazev Е. Automated Source Code Changes Classification for Effective Code Review and Analysis / Proceedings of SYRCoSE 2008 (SYRCoSE) Spring Young Researchers Colloquium on Software Engineering. Volume 2, pp. 55-59.

5. Князев E. Г. Методы обнаружения закономерностей эволюции программного кода / Труды XIV Всероссийской научно-методической конференции «Телематика-2007». СПбГУ ИТМО. 2007. Т.2, с. 435-436.

6. Князев Е. Г., Лобанов П. Г. Оценка опасности изменений программного кода путем анализа покрытия кода модульными тестами / Сборник докладов X международной конференции по мягким вычислениям и измерениям. СПбГЭТУ «ЛЭТИ». 2007. Т.2, с. 273-275.

7. Князев Е. Г. Шопырин Д. Г. Использование автоматической классификации изменений программного кода в управлении процессом разработки программного обеспечения / Тезисы докладов Software Engineering Conference (Russia) (SECR-2007). M.: Tekama. 2007. Цифровой носитель.

8. Князев E. Г., Шопырин Д. Г. Анализ изменений программного кода методом кластеризации метрик / Сборник тезисов IV межвузовской конференции молодых ученых. СПбГУ ИТМО. 2007, с. 68.

9. Князев Е. Г. Применение автоматической классификации изменений программного кода для отслеживания реализации несанкционированной функциональности / V Санкт-Петербургская межрегиональная конференция «Информационная безопасность регионов России». СПб.: СПОИСУ. 2007, с. 84.

Ю.Князев. Е. Г. Применение алгоритма нечеткой кластеризации метрик для классификации изменений программного кода / Сборник тезисов V Всероссийской межвузовской конференции молодых ученых. СПбГУ ИТМО. 2008, с. 282, 283.

П.Князев Е. Г. Применение алгоритма потоковой кластеризации для задачи классификации модификаций исходного кода / Тезисы докладов XV Международной научно-методической конференции «Высокие интеллектуальные технологии и инновации в образовании и науке». СПб ГПУ. 2008, с. 289,290.

Тиражирование и брошюровка выполнены в копировальном центре «Средний-28»

199004, Санкт-Петербург, Средний просп. В.О., 28/29. Тел. (812)323-40-44 Тираж 100 экз. Усл. печ. л. 1,0.

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

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

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

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

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

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

Задача автоматизации классификации изменений исходного кода решалась многими исследователями: A. Hassan, R. Holt, S. Demeyer, S. Ducasse, S. Raghavan, R. Rohana, J. Maletic, M. Collard, R. Robbes, S. Kim, J. Whitehead и другими. Ими были разработаны методы классификации изменений на базе эвристического, синтаксического, метрического и Data Mininig подходов к анализу изменений.

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

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

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

Цель диссертационной работы - разработка метода автоматизированной классификации изменений кода в процессе создания программного обеспечения на основе кластеризации метрик. Основные задачи исследования:

• обоснование возможности частичной автоматизации классификации изменений исходного кода методом кластеризации метрик;

• разработка метода автоматизированной классификации изменений исходного кода на основе кластеризации метрик изменений;

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

Научная новизна. На защиту выносятся результаты, обладающие научной новизной.

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

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

3. Метод автоматизированной классификации изменений исходного кода на основе кластеризации метрик изменений, позволяющий сократить число изменений для классификации, выполняемой вручную. Перечисленные результаты получены в ходе выполнения работ в СПбГУ ИТМО и ЗАО «Транзас Технологии» (Санкт-Петербург).

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

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

Практическое значение работы состоит в том, что все полученные результаты используются в настоящее время и будут использоваться в дальнейшем для повышения качества программного обеспечения в ходе разработки сложных программных комплексов. Предложенный подход применялся для классификации изменений исходного кода в продуктах, разрабатываемых ЗАО «Транзас Технологии» (система мониторинга мобильных объектов Navi-Manager, набор компонент глобальной системы LR1T (.Long-Range Identification and Tracking) для отслеживания положения судов в мировом океане, система контроля действий студентов на тренажерах e-Tutor 5000), а также в двух программных системах с открытым кодом.

Внедрение результатов. Результаты, полученные в диссертации, внедрены в указанных системах Navi-Manager, LR1T, e-Tutor 5000, а также в учебном процессе на кафедре «Компьютерные технологии» СПбГУ ИТМО по курсу лекций «Современные технологии разработки программного обеспечения».

Апробация результатов. Основные положения диссертационной работы докладывались на научно-методической конференции «Телематика-2007» (СПб., 2007), X международной конференции по мягким вычислениям и измерениям (СПб., 2007), на конференции «Software Egineering Conference

Russia) 2007» (M., 2007), XXXVI научной и учебно-методической конференции профессорско-преподавательского и научного состава СПбГУ ИТМО (СПб., 2007), на семинаре Российского Северо-Западного регионального отделения IEEE по компьютерным технологиям и инженерному менеджменту (IEEE Region 8 Russia North-West Computer Society/Engineering Management Society Joint Chapter) (СПб., 2007), IV и V Межвузовской конференции молодых ученых (СПбГУ ИТМО, 2007, 2008), XV Международной научно-методической конференции «Высокие интеллектуальные технологии и инновации в образовании и науке» (СПб., 2008).

Публикации. По теме диссертации опубликовано 11 печатных работ, в том числе две статьи в журналах из списка ВАК. Результаты, приводимые в диссертации, опубликованные без соавторов, получены лично автором. В работах под номерами 1 и 7 в списке публикаций автором предложены способы использования автоматизированной классификации изменений. В работе 6 автором предложен способ расчета метрики покрытия изменения кода модульными тестами. В работах 2, 3 и 8 автором предложен метод автоматизированной классификации изменений на основе предложенного автором способа расчета метрик изменений и их кластеризации. Остальные результаты в статьях под номерами 1, 2, 3, 7 и 8 принадлежат соавтору.

Структура диссертации. Диссертация изложена на 126 страницах и состоит из введения, трех глав и заключения. Список литературы содержит 95 наименований. Работа иллюстрирована 21 рисунком и содержит 34 таблицы.

Выводы по главе 3

1. Применение предложенного метода позволяет существенно повысить степень автоматизации задачи классификации изменений. Для пяти программных систем участие эксперта требовалось в среднем для классификации одного из одиннадцати изменений, а остальные изменения классифицировались автоматически при сохранении средних значений критериев качества классификации Рс = 0,74 ± 0,05 (вероятность ошибки классификации произвольного изменения) Ес= 0,40 ± 0,06 (степень неопределенности распределения изменений по классам). Также подтверждена гипотеза о возможности автоматизированной классификации методом кластеризации метрик изменений для значений критериев качества распределения изменений по кластерам Pq не ниже 0,69 и Eq не выше 0,47.

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

3. Эффект от использования автоматизированной классификации следующий:

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

• Задача экспертизы изменений кода для изучения истории развития системы также выполняется существенно более эффективно.

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

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

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

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

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

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

• необходимость участия эксперта в процессе сопоставления кластеров классам;

• отсутствие возможности классификации изменений, содержащих разнородные модификации.

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

Заключение

В диссертации получены следующие результаты.

1. Обоснована возможность частичной автоматизации классификации изменений исходного кода методом кластеризации метрик.

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

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

4. Разработано программное средство автоматизированной классификации изменений предложенным методом.

Перечисленные результаты получены в ходе выполнения совместных работ СПбГУ ИТМО и ЗАО «Транзас Технологии» и используются как при* разработке программного обеспечения сложных систем, так и в учебном процессе.

В работе приводятся результаты сравнения классификаций изменений в программной системе с открытым исходным кодом, выполненные с использованием предложенного автоматизированного метода и вручную. Для этого привлекались эксперты, имеющие опыт разработки сложных программных систем не менее пяти лет. Всего в работе было проанализировано пять программных систем. Исследования показали, что метод позволяет сократить время классификации изменений по сравнению с «чисто ручной» экспертизой (для пяти программных систем участие эксперта требовалось в среднем для классификации одного из одиннадцати изменений, а остальные изменения классифицировались автоматически) при следующих средних значениях характеристик качества классификации: чистота Рс = 0,74 ± 0,05 и энтропия 0,40 ±0,06. Также подтверждена гипотеза о возможности автоматизированной классификации методом кластеризации метрик изменений для значений Рд не ниже 0,69 и Eg не выше 0,47.

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

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

Темы перспективных исследований

Перспективными являются следующие направления исследований:

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

2. Разработка потокового метода классификации изменений на основе кластеризации метрик изменений;

3. Разработка модификации предложенного в диссертации метода на основе кластеризации метрик, основанной на нечеткой логике;

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

В указанных направлениях в настоящее время получены следующие результаты:

1. Сформулировано предположение, что метрики структуры кода (глубина дерева наследования, число наследуемых интерфейсов и другие), метрики связности классов (число классов, к которым- происходит обращение из некоторого класса), а также метрики дублирования кода [2, 23, 24] позволят более четко выделять класс рефакторинг, что позволит повысить качество работы метода.

2. Разработан потоковый метод классификации изменений на основе кластеризации метрик изменений ' с использованием обучающего множества изменений. В настоящее время еще не исследован вопрос устойчивости алгоритма кластеризации метрик с использованием обучающего множества изменений. Также подробно не изучены особенности построения обучающего множества изменений для решаемой задачи [12].

3. Предложена модификация метода автоматизированной классификации изменений на основе нечеткой логики. Построена нечеткая классификация множества изменений программной системы Navi-Manager. Проведен сравнительный анализ результата нечеткой классификации предложенным методом и экспертной классификации изменений [11].

4. Предложен теоретический способ автоматизированного контроля качества разработки на основе расчета метрики покрытия кода изменения тестами, с применением метода автоматизированной классификации изменений на два класса: изменение покрытого тестами кода и изменение непокрытого тестами кода [14].

1. Ауэр К, Миллер Р. Экстремальное программирование: постановка процесса. С первых шагов и до победного конца. СПб.: Питер, 2004, 368 с.

2. Афанасьев С.В., Воробьев В.И. Метрики для объектно-ориентированного проектирования сложных систем // Вестник гражданских инженеров, 2005, №4, с. 118-123.

3. Ахо А., Сети Р., Ульман Д. Д. Компиляторы: принципы, технологии и инструменты. М.: Вильяме, 2001, 768 с.

4. Барсегян А. А., Куприянов М. С., Степаненко В. В., Холод И. И. Методы и модели анализа данных: OLAP и Data Mining. СПб: БХВ-Петербург, 2004, 336 с.

5. Барсегян А. А., Куприянов М. С., Степаненко В. В., Холод И. И. Технологии анализа данных: Data Mining, Visual Mining, Text Mining, OLAP. СПб: БХВ-Петербург, 2007. 375 с.

6. Брукс П. Метрики для управления ИТ-услугами. М.: Альпина Бизнес Букс, 2008, 288 с.

7. Викиучебник. Алгоритмы поиска редакционного предписания. http://m.wikibooks.org/wiki/PeflaKUHQHHoe предписание

8. Диаконис П., Эфрон Б. Статистические методы с интенсивным использованием ЭВМ // В мире науки, 1993, №3, с. 60-72.

9. Князев Е. Г. Методы обнаружения закономерностей эволюции программного кода / Труды XIV Всероссийской научно-методической конференции «Телематика-2007». СПбГУ ИТМО. 2007. Т.2, с. 435-436.

10. Князев Е. Г. Применение алгоритма нечеткой кластеризации метрик для классификации изменений программного кода / Сборник тезисов V Всероссийской межвузовской конференции молодых ученых. СПбГУ ИТМО. 2008, с. 282, 283.

11. Князев E. Г., Лобанов П. Г. Оценка опасности изменений программного кода путем анализа покрытия кода модульными тестами / Сборник докладов X международной конференции по мягким вычислениям и измерениям. СПбГЭТУ «ЛЭТИ». 2007. Т.2, с. 273-275.

12. Князев Е. Г., Шопырин Д. Г. Автоматизированная классификация изменений программного кода методами многомерного статистического анализа // Информационные технологии. 2008. № 5, с. 48-53.

13. Князев Е. Г., Шопырин Д. Г. Анализ изменений программного кода методом кластеризации метрик // Научно-технический вестник СПбГУ ИТМО. Исследования в области информационных технологий. 2007. Вып. 39, с. 197-208.

14. Князев Е. Г., Шопырин Д. Г. Анализ изменений программного кода методом кластеризации метрик / Сборник тезисов IV межвузовской конференции молодых ученых. СПбГУ ИТМО. 2007, с. 68.

15. Князев Е. Г., Шопырин Д. Г. Использование автоматизированной классификации изменений программного кода в управлении процессомразработки программного обеспечения // Информационно-управляющие системы. 2008. № 5, с. 15-21.

16. Кобзарь А. Прикладная математическая статистика. Для инженеров и научных работников. М.: Физматилит, 2006. 816 с.

17. Количественные методы в исторических исследованиях / Под ред. Ковальченко И. Д. М.: Высшая школа, 1984. 384с.

18. Левенштейн В. И. Двоичные коды с исправлением выпадений, вставок и замещений символов. Докл. АН СССР, 163, 4, 1965, с. 845-848.

19. Липаев В. В. Методы обеспечения качества крупномасштабных программных средств. М.: Синтег, 2003, 520 с.

20. Липаев В.В. Выбор и оценивание характеристик качества программных средств: Методы и стандарты. М.: Синтег, 2001. 224 с.

21. Макконелл С. Совершенный код. СПб: Питер, 2007, 896 с.

22. Манделъ ИД. Кластерный анализ. М.: Финансы и статистика, 1988. 176 с.

23. Мартин Р. Быстрая разработка программ: принципы, примеры, практика. М.: Вильяме, 2003, 752 с.

24. Новиков Ф. А. Дискретная математика для программистов. СПб.: Питер, 2003, 460 с.

25. Орлов А. И. О реальных возможностях бутстрепа как статистического метода // Заводская лаборатория, 1987, Т.53, № 10, с. 82-85.

26. Орлов С. А. Технологии разработки программного обеспечения: Учебник для вузов. СПб: Питер, 2004. 528 с.

27. Подборка статей по бутстрепу // Заводская лаборатория, 1987, Т.53, № 10, с. 76-99.

28. Чубукова И.A. Data Mining. М.: Лаборатория Базовых Знаний, 2008. 382 с.

29. Фаулер М. Рефакторинг: улучшение существующего кода. СПб: Символ-Плюс, 2003.432 с.

30. Ханк Д. Э., Уичерн Д. У., Райте А. Д. Бизнес-прогнозирование. 7-е издание, М.: Вильяме, 2003, 656 с.

31. Эфрон Б. Нетрадиционные методы многомерного статистического анализа. М.: Финансы и статистика, 1988, 263 с.

32. A Guide to the Project Management Body of Knowledge (PMBOK® Guide) -Fourth Edition. Project Management Institute, USA, 2008, 459 p.

33. Beck K. Extreme Programming Explained: Embrace Change (2nd Edition). Addison-Wesley Professional, USA, 2004, 224 p.

34. Beck K. Test driven development by example. Addison-Wesley Professional, USA, 2002, 240 p.

35. Bevan J., Wlutehead E. J., Kim S., Godfrey M. Facilitating Software Evolution with Kenyon / European Software Engineering Conference and 2005 Foundations of Software Engineering (ESEC/FSE 2005), Lisbon, Portugal, 2005, pp. 177-186.

36. Canfora G., Cerulo L., Penta D. M. Identifying Changed Source Code Lines from Version Repositories / MSR: International Workshop on Mining Software Repositories. Minneapolis, USA. 2007, pp. 34-45.

37. Chidamber S. R., Kemerer C. F. A Metrics Suite for Object Oriented Design // IEEE Transactions on Software Engineering, Vol. 20(6), June 1994, pp. 62-69.

38. Cohen J. A Coefficient of Agreement for Nominal Scales // Educational and Psychological Measurement. 1960, № 2, pp. 37-46.

39. Cohen J. Best Kept Secrets of Peer Code Review (Modern Approach: Practical Advice), http://smartbearsoftware.com. USA, 2006, 233 p.

40. Collard M. L. Meta-Differencing: An Infrastructure for Source Code Difference Analysis. Kent State University, Kent, Ohio USA. Ph.D. Dissertation Thesis, 2004. 136 p.

41. Collins-Sussman В., Fitzpatrick B.W., Pilato M. Version Control with Subversion. O'Relly, 2004. http://svnbook.red-bean.com/

42. Concurrent Versions System (CVS), http://www.nongiiu.org/cvs/

43. Crane Simulator. Transas. http://transas.com/products/default.asp

44. Demeyer S. Ducasse S., Nierstrasz 0. Finding refactorings via change metrics / Proceedings of the ACM Conference on Object-Oriented Programming, Systems, Languages, and Applications (OOPSLA '00), pp. 166-178, 2000.

45. Efron B. Bootstrap methods: Another look at the jackknife / Ann. Statist., № 1, 1979, pp. 1-26.

46. Emam E. K. Benchmarking Kappa for Software Process Assessment Reliability Studies. Technical Report ISERN-98-02, International Software Engineering Research Network, 1998.http://citeseer.ist.psu.edu/elemam98benchm arkhi^itml

47. Engine Room Simulator (ERS) 4000. Transas. http://www.transas.com/products/simulators/sim products/ers/

48. E-Tutor 5000. Transas. http://transas.com/products/default.asp

49. Fagan, M. E. Design and Code Inspections to Reduce Errors in Program Development // IBM Systems Journal, № 3, 1976, pp. 182-211.

50. Free Software Foundation. GNU Compiler Collection, http://www.gnu.org

51. Hassan A. E., Holt. R. C. Source Control Change Messages: How Are They Used And What Do They Mean? 2004. http://www.ece.uvic.ca/~ahmed/home/pubs/CVSSurvey.pdf

52. HyppoDraw. http://www.slac.stanford■edu/gф/ek/hippodraw/index.html

53. IBM Object-Oriented Technology Center. Developing Object-Oriented Software: An Experience-Based Approach. Prentice Hall, IBM, 1997, 636 p.

54. Joachims T. Text Categorization with Support Vector Machines: Learning with Many Relevant Features / ECML 98, 10th European Conference on Machine Learning, Chemnitz, Germany, 1998, pp. 137-142.

55. Kaner С. Exploratory Testing, Florida Institute of Technology / Quality Assurance Institute Worldwide Annual Software Testing Conference, Orlando, USA, 2006, pp. 36-39.

56. Karypis G. CLUTO. A Clustering Toolkit. Technical Report: #02-017, University of Minnesota, Department of Computer Science Minneapolis, USA, 2003, 71 p.

57. KDE. К Desktop Environment, http://www.kde.org/

58. Kim M., Notkin D. Program element matching for multi-version program analyses / MSR '06: Proceedings of the 2006 International Workshop on Mining Software Repositories. 2006, pp. 58-64.

59. Kim S., Whitehead E. J., Zhang Y. Classifying Software Changes: Clean or Buggy? http://www.cs.ucsc.edu/~ejw/papers/cc.pdf

60. Knyazev E. Automated Source Code Changes Classification for Effective Code Review and Analysis / Proceedings of SYRCoSE 2008 (SYRCoSE) Spring Young Researchers Colloquium on Software Engineering. Volume 2, pp. 5559.

61. Kruskal J. В., Wish M. Multidimensional scaling. // Paper Series on Quantitative Applications in the Social Sciences, (№№ 07-011), 1978.

62. Lamping J., Rao R., Pirolli P. A focus+context technique based on hyperbolic geometry for visualizing large hierarchies // Proc. ACM Conf. Human Factors in Computing Systems, CHI, ACM, 1995, pp. 401-408.

63. Larman C., Basili V. R. Iterative and Incremental Development: A Brief History // Computer, № 6,2003, pp. 47-56

64. Liquid Cargo Handling Simidator (LCHS). Transas. http://www.transas.com/products/simulators/sim products/ers/

65. Long range identification and tracking (LRIT). International Maritime Organization, http://www.imo.org/safety/mainframe.asp'?topicid=905

66. Lorenz M., Kidd J., Object-Oriented Software Metrics: A Practical Approach, PrenticeHall, 1994, 154 p.

67. Maitra R. Clustering Massive Datasets With Application in Software Metrics and Tomography // Technometrics. № 3, 2001, pp. 336-346.

68. Malefic J. I., Collard M. L. Supporting Source Code Difference Analysis / Proceedings of IEEE International Conference on Software Maintenance (ICSM'04). Chicago, Illinois. September 11-17, 2004, pp. 210-219.

69. McCabe T. J. A Complexity Measure // IEEE Trans SE-2 № 4, December 1976.

70. Mockus A., Votta L. G. Identifying reasons for software change using historic databases / Proceedings of the International Conference on Software Maintenance (ICSM). San Jose, California, 2000, pp. 120-130.

71. MSqared Resource Standard Metrics Documentation. http://msquaredtechnolooies.com/m2rsm/docs/rsm metrics narration.htm

72. MSqared Resource Standard Metrics. Code Analysis for Code Reviews and Acceptance, http://msquaredtechnologies.com/m2rsm/index.htm

73. Navi-Manager Vessel Monitoring System. Transas. http://www.transas.com/products/shorebased/manager/ http://www.transas.ru/products/shorebased/fleet/navi-manager/

74. Navi-Trainer Professional (NTPro) 5000. Transas. http://www.transas.com/products/simulators/sim products/navigational/

75. NHibernate. Object-relation mapping for Microsoft .NET. https://www.hibernate.org/343.html

76. Pan K., Kim S., Whitehead J. E. Bug Classification Using Program Slicing Metrics / Sixth IEEE International Workshop on Source Code Analysis and Manipulation (SCAM 2006), Philadelphia, PA, 2006, pp. 77-86.

77. Radice R. Software Inspections. Software Technology Transition, www.stt.com // Methods and Tools, № 3, Martinig & Associates, USA, 2009, pp. 7-20.

78. Rasmussen M. gcluto: A graphical interface for clustering algorithms and visualizations. Technical Report TR# 04-020, Department of Computer Science & Engineering, University of Minnesota, Minneapolis, USA, 2004, 10 p.

79. Robbes R. Mining a Change-Based Software Repository / MSR: International Workshop on Mining Software Repositories. Minneapolis, USA, 2007, pp. 120-124.

80. Scott S., Matwin S. Feature Engineering for Text Classification / Sixteenth International Conference on Machine Learning, Bled, Slovenia, 1999, pp. 379-388.

81. Sebastiani F. Machine Learning in Automated Text Categorization // ACM Computing Surveys, № 1, 2002, pp. 1—47.

82. SHwerski J., Zimmermann Т., Zeller A. When Do Changes Induce Fixes? / Workshop on Mining Software Repositories (MSR 2005), Saint Louis, Missouri, USA, 2005, pp. 24-28.

83. Smart Bear Sofware. http://smartbear.com/

84. Software release lifecycle. http://en.wtkipedia.org/wiki/Softvvarereleaselife cycle

85. Subversion (SVN). http://subversion.tigris.org

86. The Apache Software Foundation. Apache HTTP Server. http://httpd.apache.org.

87. TortoiseSVN. Windows Shell Extension for Subversion. http://tortoisesvn.tigris.org/

88. Zimmermann T. Knowledge Collaboration by Mining Software Repositories / Proceedings of the 2nd International Workshop on Supporting Knowledge Collaboration in Software Development (KCSD 2006). Tokyo, Japan, 2006, pp. 64, 65.

89. Zimmermann Т., Wei.gerber P., Diehl S., Zeller A. Mining Version Histories to Guide Software Changes / Proceedings of 26th International Conference on Software Engineering (ICSE'04). Edinburgh, Scotland, United Kingdom, May 23-28, 2004, pp. 563-572.