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

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

Киселев Алексей Викторович

МОДЕЛИ И АЛГОРИТМЫ СТРУКТУРНОГО ТЕСТИРОВАНИЯ ВЗАИМОДЕЙСТВИЯ КЛАССОВ В ОБЪЕКТНО-ОРИЕНТИРОВАННОМ ПРОГРАММНОМ ОБЕСПЕЧЕНИИ

Специальность 05.13.01. - «Системный анализ, управление и обработка информации (в науке и промышленности) по техническим наукам»

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата технических наук

21 НОЯ 2013

005539068

Нижний Новгород - 2013 г.

005539068

Работа выполнена на кафедре «Вычислительные системы и технологии» федерального государственного бюджетного образовательного учреждения высшего профессионального образования «Нижегородский государственный технический университет им. Р.Е.Алексеева».

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

Ломакина Любовь Сергеевна Официальные оппоненты: Крылов Владимир Владимирович,

доктор технических наук, профессор, Нижегородский государственный технический университет им. Р.Е.Алексеева, руководитель лаборатории технологий больших данных. Волков Владимир Георгиевич, кандидат технических наук, общество с ограниченной ответственностью «МЕРА НН», руководитель проекта. Ведущая организация: Научно-исследовательский центр контроля и

диагностики технических систем, г. Нижний Новгород («НИЦ КД»).

Защита диссертации состоится «19» декабря 2013 года в Д часов в аудитории 1258 на заседании диссертационного совета Д212.165.05 при Нижегородскомгосударственном техническом университете им. P.E. Алексеева по адресу: 603950, г. Нижний Новгород, ул. Минина, 24.

С диссертацией можно ознакомиться в библиотеке Нижегородского государственного технического университета им. P.E. Алексеева.

Автореферат разослан «19» ноября 2013 года.

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

Суркова Анна Сергеевна

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

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

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

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

Существующие техники тестирования классов привязывают генерацию тестовых сценариев к существующей спецификации класса. Среди исследователей в этой области можно выделить В.В. Липаева, П.П. Пархоменко, В.И. Сагунова, А.А. Шалыто, Б. МасОге§ог, Б. Кш^, Р. ТопеНа и другие. Данные методики применимы к тестированию класса изолированно, не учитывают взаимодействие объектов классов в программе и требуют дополнительной модификации исходного кода программы для получения информации о текущем состоянии объекта класса.

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

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

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

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

Достижение поставленной цели предполагает решение следующих задач:

- анализ существующих моделей, методов и алгоритмов тестирования ОО ПО;

- обоснование целесообразности применения граф-модели для моделирования ОО ПО;

- разработка метода анализа, потока данных на основе граф-модели;

- разработка алгоритма генерации тестовых сценариев для ОО ПО, обеспечивающих наиболее полное тестовое покрытие кода программы;

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

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

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

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

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

Практическая ценность работы

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

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

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

На защиту выносятся:

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

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

3. Метод автоматической генерации тестовых сценариев на основе исходного кода программы.

Реализация результатов работы

Практические результаты, полученные в ходе выполнения диссертационной работы, используются в производственном процессе одного из проектов компании «МЕРА НН», что подтверждается актом о внедрении. Они также используются в учебном процессе подготовки магистрантов направления «Информатика и вычислительная техника» по программе «Диагностические и информационно-поисковые системы» в Нижегородском государственном техническом университете им. P.E. Алексеева. Разработанный программный комплекс зарегистрирован в Реестре программ для ЭВМ Федеральной службы по интеллектуальной собственности, патентам и товарным знакам РФ.

Результаты работы использованы в госбюджетной НИР (Отчет по НИР «Диагностика технических и программных систем с использованием современных информационных технологий». № государственной регистрации 01.2009.00405 от28.01.09 -Н. Новгород:НГТУ), выполненнойв рамках НИОКР «Диагностические и информационно - поисковые системы» (№ регистрации 01201252337, интернет-номер И111112195013, руководитель работы Ломакина JI.C.).

Апробация работы

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

— Международных научно-технических конференциях «Информационные системы и технологии (ИСТ-2009, ИСТ-2010, ИСТ-2011)» (Нижний Новгород);

— XV Международной открытой научной конференции «Современные проблемы информатизации» (Воронеж, 2010);

— XI Международной молодежной научно-технической конференции «Будущее технической науки» (Нижний Новгород, 2012);

— XVI Международной научно-практической конференции «Системный анализ в проектировании и управлении» (Санкт-Петербург, 2012).

Публикации

По теме диссертации опубликовано 10 работ, в том числе 3 статьи в рецензируемых изданиях из перечня ВАК РФ, свидетельство о государственной регистрации программы для ЭВМ № 2010611279 от 15 февраля 2010 г.

Структура и объем работы

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

СОДЕРЖАНИЕ ДИССЕРТАЦИИ

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

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

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

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

7

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

Орграф С = (X, II) называется управляющим графом (р-графом, графом переходов), если выполнены следующие условия:

■ X - это непустое множество вершин или узлов;

■ и - это множество упорядоченных пар различных вершин, называемых дугами или ориентированными рёбрами;

■ граф б не содержит параллельных дуг;

■ в множестве вершин графа выделена одна вершина 5 — вход графа;

■ в множестве вершин графа выделена одна вершина / - выход графа;

■ каждая вершина достижима из входа s;

■ каждая вершина достигает выхода /.

1 class NatBrokerlf { 23 class Connection {

2 Connection conn; 24 int opc;

Э bool is_active; 25 int dpc;

4 public: 26 bool opened;

5 NatBrokerlf(): is_actlve(false) {;} 27 public:

6 NatBrokerlf () 23 Connection():

7 { 29 opc(&), dpc(0), cpened(false) {;

3 // conn.~Cormection(); 38 Connection(int op, int dp):

9 > 31 opc(op5j dpc(rip), opened(false)

10 void setActive(bool act) 32 "■Connect! on( )

11 i 33 {

12 is_active • actj 34 closeQ;

13 if (lis active) conruclose(); 35 }

14 > 36 bool islnited() const

15 void perfor<RCorinect(int opc, int dpc) 37 {

16 £ 33 return opc && dpc;

17 if (is_active) { 39 }

13 conn.init(opc, dpc); 48 yoid init(int op, Int dp)

19 conn.create(); 41 {

28 } 42 opc »op;

21 > 43 dpc = dps

22 44 }

45 void create(}

45 {

47 if (IsXnitedO) {

43 оpenPorts(opcj dpc);

49 sendHeartbeat(opc, dpc);

50 opened » truej

51 >

52 }

53 void close()

54 {

55 if (opened) closePort5(opc, dpc]

56 Opc ■ 0J

57 dpc = 0;

53 >

59 //a..

68 )

Рис. 2.1 — Код классов NatBrokerlf и Connection 8

Вершины управляющего графа соответствуют элементарным операторам, а дуги - возможным передачам управления между операторами.

Поскольку в 00 программировании внутри класса каждый метод имеет императивный (повелительный) характер исполнения, предписывающий определенную последовательность выполнения команд, то каждый метод в классе может быть представлен в виде УГ программы. Это позволяет построить управляющий граф класса ОО ПО, состоящий из подграфов для каждого метода класса, связанных через дополнительную вершину класса. Например, на рисунке 2.1 представлены классы NatBrokerlf и Connection. Управляющий граф класса Connection показан на рисунке 2.2.

Рис. 2.2 - Управляющий граф класса Connection Между классами программы существует взаимодействие. В данной работе рассматриваются типы взаимодействия «агрегация» и «использование». При

наличии взаимодействий между классами управляющие графы для классов объединяются в единый граф потока управления между классами (рис. 2.3).

Рис. 2.3 - Граф потока управления между классами NatBrokerlf и Connection

Например, класс NatBrokerlf содержит параметр conn, являющийся представителем класса Connection. Когда вызывается метод performConnectO

10

класса NatBrokerlf, при выполнении условия «//(isActive)» выполняются методы in it 0 и createQ класса Connection.

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

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

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

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

отдельности. С этой целью сначала анализируются простые классы, которые

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

Определяется последовательность классов, основанная на связях («агрегация» и

«использование») между ними. В этой последовательности классы

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

11

классов 5 определяет направленный граф, вершины которого — классы, ветви между вершинами представляют связи («агрегацию» или «использование») (рис. 3.1). Последовательность начинается с классов, которые соответствуют листьям в графе, чьи состояния не зависят от других классов. Задача сортировки классов решается на основе графа связей между классами с помощью алгоритма топологической сортировки.

Ранжирование классов позволяет анализировать простые классы до зависящих от них сложных классов.

Анализ потока данных между классами. Ассоциация «определение-использование» или йе/-иэе ассоциация - это тройка (<1, и, у), в которой ¡Л и и являются операторами, V - переменная. с1 определяет V, и использует V, и существует путь от б/к г/, в котором нет другого определения V. Для вычисления def-u.se ассоциаций внутри одного класса применяется метод Харолда-Розермела. Данная техника применима для межпроцедурного классического анализа потока данных. При рассмотрении взаимодействий между объектами классов в ОО ПО, необходимо адаптировать технику, представленную Харолдом и Розермелом1, с целью выполнения анализа потока данных.

1 M. J. Harrold and G. Rothermel. Performing data flow testing on classes. In 2nd ACM-SIGSOFT Symposium on the foundations of software engineering, pages 154-163,New Orleans, LA (USA), December 1994.

Перед анализом класса С необходимо обобщить информацию для множества классов S, от которых зависит прямо или косвенно состояние класса С. Рассмотрим пример на рис. 2.1. Трудно оценить эффект оператора 18 conn.initO. Он может содержать определение объекта conn класса Connection, использование этого объекта или и то и другое, в зависимости от семантики метода Connection::initQ. Анализ оператора 18 требует в первую очередь анализа класса Connection.

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

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

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

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

13

Для каждого метода meth символьное выполнение применяется в следующем порядке:

1. Выделяется начало метода meth в управляющем графе класса.

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

3. Определяется множество всех путей Paths на управляющем графе, не проходящих через замыкающие дуги (данное множество конечно).

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

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

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

< predcondition >=> (< attrib >'=< symbExpr >)

def = {< setOJDefAttr >} '

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

Дедуктивый процесс построения тестового сценария. Тестовый

сценарий, соответствующий def-use ассоциации, - это последовательность

14

вызовов методов, начиная с конструктора, которая включает вызов обоих методов, определяющих с\ef-use ассоциацию.

Последний шаг алгоритма заключается в генерации последовательностей вызовов методов, которые выполняют каждую <1е£и8е ассоциацию и удовлетворяют следующим условиям (рис. 3.2):

• начинаются с вызова конструктора класса С;

• содержат вызов метода тл выполняющего оператор с1\

• содержат вызов метода ти, выполняющего оператор и;

• последовательность методов между т1/ и ти не может содержать выполнение какого-либо другого оператора, прямо или косвенно определяющего переменную V.

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

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

constructor,.. .,т|,...,т0,. ..,mj,„.,mu>

Метод, содержащий определение V (definition)

Метод, содержащий использование v (using)

Рис. 3.2 - Тестовый сценарий, последовательность вызовов методов

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

Алгоритм построения дерева выглядит следующим образом:

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

2. Вставить вершину, соответствующую методу та, отвечающему за определение переменной, при первой же возможности как уникальный последующий элемент.

3. Исследовать поддерево с корнем в вершине т11, вставить конструктор при первой же возможности.

Продемонстрируем технику построения дерева на примере класса АТшВгокег1/ (рис. 2.1). Рассмотрим процесс построения последовательности вызовов методов для с1е£-и$е ассоциации, представленной в таблице 1.

Переменная, v сопп.орс

Определение, d NatBrokerlf, строка 5

Использование, и NatBrokerlf::setActive -> Connection::close, строка 55

PCU opened = true, act = false

Таблица 1 — Def-use ассоциация для переменной сопп.орс

Процесс генерации дерева (рис. 3.3) начинается с метода setActivefbool act), который использует значение переменной сопп.орс. Соответствующее ему предусловие PCU: opened = true, act = false. Исходя из постусловий вызовов всех методов класеа NatBrokerlf, добавляется метод performConnect(int орс, int dpc). Это единственный метод, который выставит значение переменной conn.opened в true за счет вызова метода conn.createß• Построение дерева продолжается, пока не будет добавлен конструктор класса NatBrokerlf. Результирующая последовательность вызовов методов для данной ассоциации:

NarBrokerlfi)->setActive(true)->perform Connect(opc, dpc)->setActive(false).

setActíve(act)^>

opened® true' act« fake

/V ¡ -— k. '^S

ísActive = true

\ /

Рис. 3.3 — Пример построения последовательности вызовов методов

В результате работы предложенного метода получается конечный набор тестов. При структурном тестировании ПО необходимо, чтобы тестовый набор удовлетворял структурному критерию полноты тестирования. Для разработанного метода тестирования О О ПО метрика покрытия def-use ассоциаций используется в качестве метрики тестового покрытия — это доля покрытых def-use ассоциаций для всех переменных-атрибутов классов программы по отношению к достижимым def-use ассоциациям (недостижимой называется def-use ассоциация, которая не может быть покрыта ни при каком выполнении программы): N

(~~< _ _ т СОУ

DU ~ N ;

ly du

где CDU - коэффициент покрытых достижимых def-use ассоциаций, Nmy - число покрытых defuse ассоциаций, NJu - число всех достижимых def-use ассоциаций. Данный коэффициент будет равен 1, когда будут покрыты все достижимые defuse ассоциации.

Метрика покрытия def-use ассоциаций является одной из самых сильных метрик покрытия, используемых на практике. Количество тестов в полном

наборе по такой метрике может быть огромным, но в большинстве случаев это не так — один тест покрывает сразу несколько def-use ассоциаций.

В четвертой главе (Вычислительный эксперимент. Практическая реализация) приведен пример практического применения предложенной техники тестирования ООПО. Проводится вычислительный эксперимент над классом Stream, реализующим буфер ввода/вывода, и над программным комплексом NATGateway, который выполняет адаптацию между системами OSS (Operations Support System) и NAT-SCP (Number Address Translation - Service Control Point), использующими разные сетевые протоколы передачи данных.

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

С* *

ЯШ

Синтаксический аппликатор классов

Г Управ

I ;гр;а-фь1

Анализатор мошка данных

lief u-л .iLcmiiMUtfH члиюиис ipa<J»,i классов

Инструмент символьного выполнении

¡шф.

ds!" »so ассоциации щкц пост условия

ll'licpillop последовательности методов

Тестовые сценарии - последовательности /вызовов Wroiö» /■

Рис. 4.1 - Основные блоки системы генерации тестовых сценариев

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

тестовыми последовательностями вызовов методов, и суммарное время выполнения.

Класс Количество defuse ассоциаций Количество покрытых def-use ассоциаций Время выполнения, сек

NatBroker 360 292 1456

NatBrokerlf 18 18 < 1

Connection 25 25 2

MessageListener 32 32 2

NatConfig 720 512 4609

NatAddress 41 40 3

GlobalTitle 4 4 < 1

NatUser 9 9 < 1

NatClient 24 24 2

Всего 1233 956 6075

Таблица 2 - Статистика тестирования TENATGW Application

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

На рис. 4.2 представлено сравнение количества тестов и покрытых ими def-use ассоциаций для двух тестовых наборов: 1) тесты, написанные на основе существующих спецификаций для программного модуля TENATGW Application, и 2) тесты, сгенерированные на основе разработанного метода. Из рисунка видно, что, несмотря на большее число функциональных тестов, основанных на существующих спецификациях, они не покрывают все возможные последовательности вызовов методов классов программы.

Коэффициент покрытых def-use ассоциаций при использовании разработанного подхода CDU =1, что удовлетворяет структурному критерию полноты тестирования.

■ на основе

спецификаций □ на основе нового метода

количество количество покрытых тестов clef-use ассоциаций

Рис. 4.2 - Сравнение двух тестовых наборов

Для анализа эффективности предложенной методики в Тестируемый код специально были вставлены 100 ошибок пяти видов:

• неправильное определение переменной-атрибута класса;

• переменная- атрибут класса не определяется прямым или косвенным (через вызов метода) путем;

• переменная-атрибут класса определяется некорректно;

• переменная-атрибут класса не проверяется (условие if);

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

В результате прогона тестов обнаружено ошибок:

1) тестами на основе спецификаций - 84;

2) тестами на основе нового метода - 100.

После первого запуска автоматизированной системы генерации тестовых сценариев и их выполнения были выявлены 73 ошибки из 100. В первую очередь были выявлены ошибки в классах Connection, GlobalTittle, NatBrokerlf. Ошибки в классах NatConfig и NatBroker не были выявлены из-за наличия ошибок в классах, объекты которых являются атрибутами первых, поэтому некоторые пути потока данных не были пройдены.

После исправления первых 73 ошибок система была перезапущена. При втором запуске были сгенерированы тестовые сценарии, которые раскрыли оставшиеся 27 ошибок.

ТЖГ

-956-

6701

I

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

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

Приложение содержит:

• акт о внедрении разработанной автоматизированной системы генерации тестовых сценариев для объектно-ориентированного программного обеспечения в производственный процесс компании «МЕРА НН»;

• акт о внедрении результатов диссертационной работы в учебный процесс подготовки магистрантов направления «Информатика и вычислительная техника» по программе «Диагностические и информационно-поисковые системы» в Нижегородском государственном техническом университете им. P.E. Алексеева;

• свидетельство о государственной регистрации программы для ЭВМ №2010611279 от 15 февраля 2010 г.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

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

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

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

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

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

6. Результаты диссертационной работы внедрены в производственный процесс компании «МЕРА НН» и учебный процесс подготовки магистрантов направления «Информатика и вычислительная техника» по программе «Диагностические и информационно-поисковые системы» в Нижегородском государственном техническом университете им. Р.Е. Алексеева.

СПИСОК ОПУБЛИКОВАННЫХ РАБОТ ПО ТЕМЕ ДИССЕРТАЦИИ Публикации в рекомендованных ВАК рецензируемых изданиях

[1] Киселев, А.В. Метод тестирования классов объектно-ориентированного программного обеспечения [Текст] / А.В. Киселев // Журнал «Вестник Нижегородского государственного университета». — Нижний Новгород, 2012. -№2.- С. 210-215.

[2] Киселев, А.В. Метод интеграционного тестирования объектно-ориентированной программы [Текст] / А.В. Киселев // Журнал «Научно-технический вестник Поволжья», КГУ, Казань, № 5, 2013. - С. 195-198.

[3] Киселев, А.В., Ломакина, Л.С. Модели и методы структурного тестирования взаимодействия классов в объектно-ориентированном программном обеспечении [Текст] / Л.С. Ломакина, АВ. Киселев // Журнал «Системы управления и информационные технологии» / ИПУ РАН, ВГТУ, № 3.1 (53), М.-Воронеж, 2013. - С. 155-159.

Публикации в других изданиях

[4] Киселев, А.В. Методика диагностики объектно-ориентированного программного обеспечения на основе граф-моделей [Текст] / АВ. Киселев // Материалы Международной научно-технической конференции

«Информационные системы и технологии (ИСТ-2009)», 17 апреля 2009 г. - Н. Новгород: НГТУ, 2009. - С.266.

[5] Киселев, A.B. Тестирование объектно-ориентированного программного обеспечения [Текст] / A.B. Киселев // Материалы 15-й Международной открытой научной конференции «Современные проблемы информатизации». -Воронеж: ВГТУ, 2010. - С. 426-429.

[6] Киселев, A.B. Метод тестирования классов в объектно-ориентированном программном обеспечении [Текст] / A.B. Киселев // Материалы Международной научно-технической конференции «Информационные системы и технологии (ИСТ-2010)», 23 апреля 2010 г. - Н.Новгород: НГТУ, 2010. - С.ЗОО.

[7] Киселев, A.B. Метод тестирования взаимодействия классов в объектно-ориентированном программном обеспечении [Текст] / A.B. Киселев // Материалы Международной научно-технической конференции «Информационные системы и технологии (ИСТ-2011)», 22 апреля 2011 г. -Н.Новгород: НГТУ, 2011. - С.316.

[8] Киселев, A.B. Тестирование как объект инженерии объектно-ориентированного программного обеспечения [Текст] / A.B. Киселев, JI.C. Ломакина // Материалы XI Международной научно-технической конференции «Будущее технической науки», 18 мая 2012 г. - Н. Новгород: НГТУ, 2012. -С.27-28.

[9] Киселев, A.B. Системный подход при тестировании объектно-ориентированного программного обеспечения [Текст] / Л.С. Ломакина, A.B. Киселев // Труды XVI Международной научно-практической конференции «Системный анализ в проектировании и управлении», 27-29 июня 2012 г. -Санкт-Петербург: СПб. ГПУ, 2012. - С. 128-129.

[10] Киселев, A.B. Визуализация тестирования объектно-ориентированного программного обеспечения / Л.С. Ломакина, A.B. Киселев, С.Н. Малинин // Свидетельство об официальной регистрации программ для ЭВМ № 2010611279. Зарегистрировано в реестре программ для ЭВМ Федеральной службы по интеллектуальной собственности, патентам и товарным знакам РФ от 15 февраля 2010 г.

Подписано в печать 08.11.2013. Формат 60 х 84 1/16. Бумага офсетная. _Печать офсетная. Уч.-изд. л. 1,0. Тираж 100 экз. Заказ 802._

Нижегородский государственный технический университет им. P.E. Алексеева. Типография НГТУ. 603950, ГСП-41, г. Нижний Новгород, ул. Минина, 24.

Нижегородский государственный технический университет

им. Р.Е. Алексеева

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

Киселев Алексей Викторович

МОДЕЛИ И АЛГОРИТМЫ СТРУКТУРНОГО ТЕСТИРОВАНИЯ ВЗАИМОДЕЙСТВИЯ КЛАССОВ В ОБЪЕКТНО-ОРИЕНТИРОВАННОМ

ПРОГРАММНОМ ОБЕСПЕЧЕНИИ

Специальность 05.13.01 -«Системный анализ, управление и обработка информации (в науке и промышленности)» (технические науки)

Диссертация на соискание ученой степени кандидата технических наук

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

Нижний Новгород - 2013 г.

СОДЕРЖАНИЕ

ВВЕДЕНИЕ...................................................................................................................4

ГЛАВА 1. ОБЗОР СУЩЕСТВУЮЩИХ МЕТОДОВ ТЕСТИРОВАНИЯ ПРОГРАММНОГО ОБЕСПЕЧЕНИЯ И ПОСТАНОВКА ЗАДАЧИ ИССЛЕДОВАНИЯ .....................................................................................................................................10

1.1 Тестирование программного обеспечения. Основные задачи и проблемы тестирования....................................................................10

1.2 Методы тестирования................................................................................14

1.3 Методы построения тестов.......................................................................17

1.4 Метрики тестирования..............................................................................19

1.5 Автоматизация тестирования..................................................................22

1.6 Техника тестирования объектно-ориентированного программного обеспечения...........................................................................................................25

1.7 Постановка задачи......................................................................................33

ГЛАВА 2. БАЗОВАЯ МОДЕЛЬ ОБЪЕКТНО-ОРИЕНТИРОВАННОГО ПРОГРАММНОГО ОБЕСПЕЧЕНИЯ..........................................................................35

2.1 Особенности объектно-ориентированного программирования......35

2.2 Графовая модель объектно-ориентированного программного обеспечения...........................................................................................................40

2.3 Построение графа потока управления между классами.....................44

2.3.1 Синтаксический анализ программы.................................................45

2.3.2 Семантический анализ программы..................................................47

2.3.3 Алгоритм построения управляющего графа класса......................52

2.3.4 Инструмент построения модели 00 ПО...........................................53

2.4 Выводы..........................................................................................................54

ГЛАВА 3. ДИАГНОСТИЧЕСКАЯ МОДЕЛЬ. МЕТОДЫ И АЛГОРИТМЫ ТЕСТИРОВАНИЯ ОБЪЕКТНО-ОРИЕНТИРОВАННОГО ПРОГРАММНОГО ОБЕСПЕЧЕНИЯ..........................................................................................................56

3.1 Основная идея разработанного алгоритма тестирования.................56

3.2 Ранжирование классов...............................................................................58

3.3 Анализ потока данных между классами.................................................59

3.4 Межклассовое символьное выполнение................................................63

3.5 Дедуктивный процесс построения тестовых сценариев....................73

3.6 Критерий полноты тестирования...........................................................78

3.7 Применимость разработанной техники тестирования......................80

3.8 Выводы..........................................................................................................83

ГЛАВА 4. ВЫЧИСЛИТЕЛЬНЫЙ ЭКСПЕРИМЕНТ. ПРАКТИЧЕСКАЯ РЕАЛИЗАЦИЯ............................................................................................................85

4.1 Автоматизированная система генерации тестовых сценариев........85

4.2 Вычислительный эксперимент №1: класс Stream...............................87

4.3 Вычислительный эксперимент №2: NATGateway................................95

4.3.1 Описание программного комплекса NATGateway..........................95

4.3.2 Экспериментальная проверка разработанного алгоритма тестирования.....................................................................................................97

4.4 Анализ результатов..................................................................................103

Заключение.............................................................................................................104

Библиографический список................................................................................105

ПРИЛОЖЕНИЯ.......................................................................................................117

ВВЕДЕНИЕ

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

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

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

Существующие техники тестирования классов привязывают генерацию тестовых сценариев к существующей спецификации класса. Среди исследователей в этой области можно выделить В.В. Липаева, П.П. Пархоменко, В.И. Сагунова, А.А. Шалыто, О. Масвге§ог, О. Кш^, Р. Топе11а и другие. Данные техники применимы к тестированию класса изолированно, не учитывают взаимодействие объектов классов в программе и требуют дополнительной модификации исходного кода программы для получения информации о текущем состоянии объекта класса.

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

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

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

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

Достижение поставленной цели предполагает решение следующих задач:

- анализ существующих моделей, методов и алгоритмов тестирования 00 ПО;

- обоснование целесообразности применения граф-модели для моделирования ОО ПО;

- разработка метода анализа потока данных на основе граф-модели;

- разработка алгоритма генерации тестовых сценариев для 00 ПО, обеспечивающих наиболее полное тестовое покрытие кода программы;

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

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

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

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

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

Практическая ценность работы

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

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

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

На защиту выносятся:

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

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

3. Метод автоматической генерации тестовых сценариев на основе исходного кода программы.

Реализация результатов работы

Практические результаты, полученные в ходе выполнения диссертационной работы, используются в производственном процессе одного из проектов компании «МЕРА НН», что подтверждается актом о внедрении. Они также используются в учебном процессе подготовки магистрантов направления «Информатика и вычислительная техника» по программе «Диагностические и информационно-поисковые системы» в Нижегородском государственном техническом университете им. Р.Е. Алексеева. Разработанный программный комплекс зарегистрирован в Реестре программ для ЭВМ Федеральной службы по интеллектуальной собственности, патентам и товарным знакам РФ.

Результаты работы использованы в госбюджетной НИР (Отчет по НИР «Диагностика технических и программных систем с использованием современных информационных технологий». № государственной регистрации 01.2009.00405 от 28.01.09 - Н.Новгород: НГТУ), выполненной в рамках НИОКР «Диагностические и информационно - поисковые системы» (№ регистрации 01201252337, интернет-номер И111112195013, руководитель работы Ломакина Л.С.).

Апробация работы

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

- Международных научно-технических конференциях «Информационные системы и технологии (ИСТ-2009, ИСТ-2010, ИСТ-2011)» (Нижний Новгород);

- XV Международной открытой научной конференции «Современные проблемы информатизации» (Воронеж, 2010);

- XI Международной молодежной научно-технической конференции «Будущее технической науки» (Нижний Новгород, 2012);

- XVI Международной научно-практической конференции «Системный анализ в проектировании и управлении» (Санкт-Петербург, 2012).

Публикации

По теме диссертации опубликовано 10 работ, в том числе 3 статьи в рецензируемых изданиях из перечня ВАК РФ, свидетельство о государственной регистрации программы для ЭВМ № 2010611279 от 15 февраля 2010 г.

Структура и объем работы

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

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

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

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

В третьей главе (Диагностическая модель. Методы и алгоритмы тестирования объектно-ориентированного программного обеспечения) представлены методы и алгоритмы тестирования ОО ПО, разработанные на основе описанной в предыдущей главе базовой граф-модели. Описаны

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

В четвертой главе (Вычислительный эксперимент. Практическая реализация) приведен пример практического применения предложенного метода тестирования ОО ПО. Проводится вычислительный эксперимент над классом Stream, реализующим буфер ввода/вывода, и над программным комплексом NATGateway, который выполняет адаптацию между системами OSS {Operations Support System) и NAT-SCP {Number Address Translation - Service Control Point), использующими разные сетевые протоколы передачи данных.

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

Приложение содержит:

• акт о внедрении разработанной автоматизированной системы генерации тестовых сценариев в производственный процесс компании «МЕРА НН»;

• акт о внедрении результатов диссертационной работы в учебный процесс подготовки магистрантов направления «Информатика и вычислительная техника» по программе «Диагностические и информационно-поисковые системы» в Нижегородском государственном техническом университете им. P.E. Алексеева;

• свидетельство о государственной регистрации программы для ЭВМ №2010611279 от 15 февраля 2010 г.

ГЛАВА 1. ОБЗОР СУЩЕСТВУЮЩИХ МЕТОДОВ ТЕСТИРОВАНИЯ ПРОГРАММНОГО ОБЕСПЕЧЕНИЯ И ПОСТАНОВКА ЗАДАЧИ

ИССЛЕДОВАНИЯ

1.1 Тестирование программного обеспечения. Основные задачи и проблемы тестирования

Тестирование программного обеспечения - процесс исследования, испытания программного обеспечения (ПО) с целью получения информации о качестве продукта.

Сегодня тестирование является основным способом проверки правильности программного обеспечения. Как один из основных этапов процесса разработки ПО, тестирование характеризуется достаточно большим вкладом в суммарную трудоемкость разработки продукта. На тестирование, как правило, приходится от 30% до 50% от стоимости разработки программного обеспечения [1]. Тем не менее, программные сбои происходят довольно часто и их стоимость для мировой экономики измеряется в нескольких миллиардах долларов [2].

Вследствие этого исследование способов повышения надежности ПО является актуальной задачей. Надежность программного обеспечения определяется как возможность программы работать без сбоев определенный период времени в определенных условиях. В настоящее время ведется интенсивное исследование этой области: разрабатываются методы доказательства корректности программ, методы их тестового диагностирования, а также методы структурного программирования и различных организационных техник, которые могли бы повысить надежность ПО. Также были предложены методы создания программ, устойчивых к ошибкам [3-8].

Важными составляющими вычислительного (управляющего) процесса являются надежность аппаратуры ЭВМ и надежность их ПО [9]. Однако надежность ПО существенно отличается от надежности аппаратуры ЭВМ.

Программы не изнашиваются, поломка программы не возможна. Надежность ПО - следствие исключительно ошибок проектирования, т.е. ошибок, внесенных в процессе разработки. Следует отметить, что если теория надежности аппаратуры ЭВМ уже достаточно хорошо развита [10], то теория надежности вычислительных процессов и теория надежности ПО еще не разработаны в достаточной степени [11].

Исследования последних десятилетий в области разработки ПО [12,13] сформировали набор методов, моделей, процессов и технологий, использование которых позволяет достичь заданных характеристик надежности и качества ПО. Постепенно из отдельных исследований сформировалась единая дисциплина, которая и легла в основу инженерии программного обеспечения [14, 15].

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