ЭКСПЕРИМЕНТАЛЬНОЕ ИССЛЕДОВАНИЕ КОНЕЧНО АВТОМАТНЫХ МЕТОДОВ ТЕСТИРОВАНИЯ В КОНТЕКСТЕ ДЛЯ ТЕЛЕКОММУНИКАЦИОННЫХ ПРОТОКОЛОВ
|
РЕФЕРАТ 3
Введение 5
1 Основные определения и обозначения. Методы синтеза тестов для программного
обеспечения 13
1.1 Основные определения и обозначения 13
1.2 Виды и способы тестирования программного обеспечения 15
1.3 Краткий обзор методов тестирования программного обеспечения 16
1.3.1 Методы синтеза тестов для программного обеспечения для черного ящика 16
1.3.2 Методы синтеза тестов для программного обеспечения для белого ящика 17
1.3.2.1 Методы синтезов тестов на основе формальных моделей 18
1.3.2.2 Особенности тестирования в контексте 19
1.4 Методы синтеза тестов для проверки реализаций телекоммуникационных протоколов на наличие ошибок 19
2 Тестирование реализаций телекоммуникационных протоколов в контексте 22
2.1 Постановка задачи 22
2.2 Обсуждение различных топологий при тестировании в контексте и их технических
реализаций 22
2.3 Эвристика для адаптации известных конечно автоматных методов для тестирования в
контексте телекоммуникационных протоколов 26
3 Описание алгоритмов и программных реализаций 30
3.1 Описание инструмента для автоматического тестирования программ и его алгоритмов 30
3.2 Описание инструмента трансляции представлений формальных моделей 34
4 Тестирование в контексте для протокола TCP 37
4.1 Доопределение автоматной модели TCP 37
4.2 Постановка эксперимента 43
4.3 Эксперименты над реализацией TCP 49
4.3.1 Построение тестовых последовательностей 49
4.3.2 Результаты экспериментов 50
5 Обсуждение результатов для тестирования в контексте протоколов различных уровней и в условиях ограничений на управление контекстом 51
5.1 Обсуждение результатов для тестирования в контексте протоколов различных уровней 51
5.2 Обсуждение результатов для тестирования в контексте в условиях ограничений на
управление контекстом 53
Заключение 55
Список использованной литературы 56
Введение 5
1 Основные определения и обозначения. Методы синтеза тестов для программного
обеспечения 13
1.1 Основные определения и обозначения 13
1.2 Виды и способы тестирования программного обеспечения 15
1.3 Краткий обзор методов тестирования программного обеспечения 16
1.3.1 Методы синтеза тестов для программного обеспечения для черного ящика 16
1.3.2 Методы синтеза тестов для программного обеспечения для белого ящика 17
1.3.2.1 Методы синтезов тестов на основе формальных моделей 18
1.3.2.2 Особенности тестирования в контексте 19
1.4 Методы синтеза тестов для проверки реализаций телекоммуникационных протоколов на наличие ошибок 19
2 Тестирование реализаций телекоммуникационных протоколов в контексте 22
2.1 Постановка задачи 22
2.2 Обсуждение различных топологий при тестировании в контексте и их технических
реализаций 22
2.3 Эвристика для адаптации известных конечно автоматных методов для тестирования в
контексте телекоммуникационных протоколов 26
3 Описание алгоритмов и программных реализаций 30
3.1 Описание инструмента для автоматического тестирования программ и его алгоритмов 30
3.2 Описание инструмента трансляции представлений формальных моделей 34
4 Тестирование в контексте для протокола TCP 37
4.1 Доопределение автоматной модели TCP 37
4.2 Постановка эксперимента 43
4.3 Эксперименты над реализацией TCP 49
4.3.1 Построение тестовых последовательностей 49
4.3.2 Результаты экспериментов 50
5 Обсуждение результатов для тестирования в контексте протоколов различных уровней и в условиях ограничений на управление контекстом 51
5.1 Обсуждение результатов для тестирования в контексте протоколов различных уровней 51
5.2 Обсуждение результатов для тестирования в контексте в условиях ограничений на
управление контекстом 53
Заключение 55
Список использованной литературы 56
Актуальность проблемы. В современном мире программное обеспечение (далее ПО) имеет все большое значение для человека, однако с ростом развития ПО растет и его сложность, а значит и количество ошибок. Существует множество сфер с критическими требованиями к надежности программного обеспечения, такие как медицина, банковское дело или воздушный флот. Наличие ошибки в управляющей части таких систем зачастую недопустимо, соответственно, актуальным является как можно более полное тестирование этих подсистем.
Известны следующие исторические факты фатального влияния ошибки ПО на человеческую жизнь.
а) В 1980-х годах пять пациентов умерли после получения большой дозы рентгеновских лучей в результате ошибки в программировании машины для лучевой терапии Therac-25. Авария, как полагают, была вызвана сбоем, который повлиял на производительность системы [1].
б) Четвертого июня 1996 года Европейское космическое агентство произвело испытательный пуск ракеты Ariane 5. Ошибка в контролирующем программном обеспечении, написанном на языке программирования Ada, вызвала самоликвидацию ракеты через 37 секунд после взлета [2].
в) В 2007 году счета более 3 миллионов клиентов одного из крупнейших банков Великобритании оказались под угрозой взлома из-за ошибки в системе безопасности [3].
г) Расследование NASA в 2007 году установило, что космический зонд Mars Global Surveyor перестал работать из-за ошибки в программном обеспечении, допущенной за пять месяцев до его гибели [4].
д) В 2009 году 206 пациентов клиники Cedars-Sinai Medical Center в Лос-Анджелесе были облучены недопустимо высокой дозой радиации в результате ошибки в программе спирального томографа [5].
е) В 2012 году сбой компьютера чуть не привел инвестиционную компанию Knight Capital к банкротству. Фирма потеряла полмиллиарда долларов через полчаса после того, как ошибка программного обеспечения позволила в автоматическом режиме системе самой покупать и продавать акции без надзора человека. Цена на акции компании упала на 75 процентов в течение двух дней [5].
Следует отметить, что в ходе разработки ПО изначально формируются требования к итоговому продукту, это означает, что задается некоторая спецификация. Спецификация содержит в себе список требований и характеристик, которым должна соответствовать разрабатываемая программная реализация. В спецификации описывается вся необходимая информация о поведении системы и о разнообразии ситуаций, которые могут возникать при ее взаимодействии с другими системами или людьми. Таким образом, наиболее распространенные методы тестирования предназначены именно для проверки, соответствует ли разработанная программа исходной спецификации (тестирование соответствия или conformance testing). При этом известно, что гарантированная полнота тестирования возможна только при условии привлечения формальных моделей и, в частности, конечно автоматных моделей. Тестирование на основе формальных моделей заключается в следующем. По спецификации, которая является неформальным описанием с набором требований к программному обеспечению, строится формальная модель; на основе полученной модели строится множество тестовых последовательностей, которые в дальнейшем подаются на соответствующую данной спецификации проверяемую программную реализацию. На основании наблюдаемых выходных реакций делается заключение о соответствии проверяемой программной реализации ее спецификации.
С другой стороны, время тестирования, как правило, является ограниченным, соответственно, с учетом роста количества ошибок возрастает необходимость в эффективном и быстром тестировании. Однако, по причине встраиваемости тестируемой критической части в более крупную реализацию, подача тестов на нее может быть затруднено . Так, например, множество телекоммуникационных протоколов инкапсулируется в телекоммуникационный протокол, который находится выше уровнем по сетевой модели OSI, и поэтому программные реализации исследуемых телекоммуникационных протоколов часто являются внутренними частями более сложного ПО. Таким образом, необходимо не только синтезировать качественные тесты для реализаций телекоммуникационных протоколов, но и принимать во внимание невозможность прямой подачи данных последовательностей на проверяемую реализацию. Иными словами, требуется также решать задачу трансляции синтезируемых тестовых последовательностей через некоторый контекст. В данной работе экспериментально исследуются методы тестирования в контексте для телекоммуникационных протоколов. Тестирование проводится на основе дискетных моделей, а именно, конечных автоматов.
Целью работы является экспериментальное исследование конечно автоматных методов тестирования в контексте для программных реализаций телекоммуникационных протоколов.
Методы исследования. Для достижения поставленной цели в работе используется аппарат дискретной математики, в частности, для синтеза тестов и их последующей трансляции привлекаются методы классической теории автоматов, комбинаторики и математической логики. Эффективность предлагаемых подходов оценивается посредством компьютерных экспериментов с существующими или разработанными автором программными реализациями телекоммуникационных протоколов.
Научная новизна.
Научная новизна работы заключается в следующем.
а) В работе предложена эвристика для адаптации известных конечно автоматных методов тестирования в контексте для телекоммуникационных протоколов.
б) Компьютерные эксперименты с реализациями телекоммуникационных протоколов (в частности, с реализацией протокола TCP, встроенной в программное обеспечение Psi) подтверждают эффективность предложенной эвристики.
в) Проведенные компьютерные эксперименты позволили выявить несоответствие реализации протокола TCP, встроенной в ПО Psi [6] версии 0.15-2 спецификации протокола TCP, представленной в RFC 793 [7].
Основные положения, выносимые на защиту.
а) Предложена эвристика для адаптации известных конечно автоматных методов для тестирования телекоммуникационных протоколов в контексте, которая основана на синтезе усеченного дерева приемников, представляющего контекст, и позволяет проверять функционирование других встроенных технических систем на основе конечно автоматных моделей.
б) Результаты экспериментального исследования по тестированию
телекоммуникационных протоколов в контексте на основе конечно автоматных моделей, которые, в частности, позволили выявить несоответствие реализации протокола TCP, встроенной в ПО Psi (версия 0.15-2) спецификации протокола TCP, представленной в RFC 793.
Достоверность результатов. Эффективность предложенного подхода подтверждается компьютерными экспериментами с реализациями телекоммуникационных протоколов и, в частности, с реализацией телекоммуникационного протокола TCP, встроенной в ПО Psi версии 0.15-2. При этом дерево преемников контекста Psi было усечено при максимальной длине наблюдаемых последовательностей, равной шести.
Практическая ценность. Результаты работы могут быть использованы при тестировании реальных систем, поведение которых может быть описано посредством конечно автоматных моделей. Разработанные программные реализации инструментов автоматизации подачи тестовых последовательностей и сравнения результатов могут быть использованы при тестировании программного обеспечения различного назначения и на основе различных подходов к синтезу тестов. Разработанные программные реализации инструментов трансляции различных представлений конечного автомата могут быть использованы при синтезе тестов для технических систем на основе конечно автоматных моделей с использованием различных автоматизированных средств, например, FSM test 1.0. Построенная формальная спецификация для протокола TCP в виде конечного детерминированного автомата может быть использована при синтезе тестов для реализации этого протокола, встроенного в иное программное обеспечение (отличное от Psi).
Апробация работы. Основные положения и результаты, представленные в работе, были представлены на двух Российских конференциях с международным участием «Новые информационные технологии в исследовании сложных структур» на Алтае (2014 г.) и Екатеринбурге (2016 г.), а также на международной Летней Школе IT CoSAS в Анапе (2015 г.). По результатам работы опубликована одна статья в журнале, входящем в Перечень ВАК.
Структура и объем работы. Магистерская диссертация включает введение, 5 глав, заключение и список используемой литературы. Диссертация содержит 20 рисунков и 1 таблицу. Объем работы составляет 58 страниц, в том числе: титульный лист - одна страница, оглавление - 2 страницы, основной текст - 52 страницы, список использованных
литературных источников из 43 наименований - 3 страницы.
Во введении обсуждается актуальность и цель работы, формулируются положения, выносимые на защиту, а также отмечается апробация работы.
В первой главе приводятся основные определения и обозначения, используемые в работе; представляется краткий обзор видов и способов тестирования программного обеспечения, в том числе, методов синтеза тестов для моделей черного и белого ящика для тестирования в контексте (на основе формальных моделей).
Работа посвящена исследованию актуальной задачи, а именно, задачи тестирования реализаций телекоммуникационных протоколов. Телекоммуникационный протокол регламентирует процедуру и формат взаимодействия между некоторым количеством независимых компонент, которые могут являться устройствами, компьютерами, программами или процессами [8].
Тестирование программных реализаций телекоммуникационных протоколов является серьезной задачей при текущем большом распространении сетей и распределенных служб. Богатство разнообразия сетей и быстро увеличивающееся число соединений между ними объясняется как растущим числом взаимодействующих компонент, так и созданием множества принципиально новых телекоммуникационных протоколов, для которых требуется взаимодействие с существующими техническими системами. Гарантированная полнота тестирования возможна только с применением формальных моделей, и среди формальных моделей, на основе которых могут синтезироваться тесты, для таких систем и, в частности, для программного обеспечения выделяют модели с конечным числом переходов. В данной работе в качестве такой модели рассматривается конечный автомат. Под конечным автоматом S понимается пятерка S = (S, I, O, Ts, so), где S - множество состояний c выделенным начальным состоянием so, I - входной алфавит, O - выходной алфавит, T - отношение переходов, T о S * I * O * S.
Задачи анализа конечные автоматы являются хорошо изученными, и в настоящий момент известны методы построения проверяющих тестов для конечных автоматов. Тем не менее, проверяющие тесты, построенные для автоматов, которые описывают поведение реальной системы целиком, могут иметь слишком большие размеры для проведения эксперимента за некоторое отведенное время. Поэтому для тестирования часто выбирают только критическую компоненту технической системы, полнота тестирования которой должны быть гарантирована. Однако такая компонента может быть недоступна для прямой подачи тестовой последовательности. Другими словами, тестируемая реализация находится в контексте.
Данная диссертация посвящена исследованию тестирования в контексте для телекоммуникационных протоколов. Соответственно, в первой главе отдельный раздел посвящен методам синтеза тестов на основе формальных моделей (в том числе, в контексте), а также методам синтеза тестов для телекоммуникационных протоколов.
Во второй главе описывается постановка задачи, а именно, обсуждается проблема тестирования в контексте для реализаций телекоммуникационных протоколов. Обсуждаются различные топологии тестирования в контексте при исследовании телекоммуникационных протоколов, рассматриваются особенности технических реализаций предложенных топологий. Предлагается эвристика для адаптации известных конечно автоматных методов тестирования в контексте телекоммуникационных протоколов.
Основная идея тестирования в контексте заключается в том, что тестер не имеет прямого доступа к тестируемой реализации и вынужден взаимодействовать с ней через контекст некоторой иной реализации. Следовательно, тестовая последовательность должна быть транслирована через контекст, что влияет на полноту и сложность метода синтеза тестов.
Упоминая синтез тестов в контексте для автоматных моделей, мы предполагаем композицию двух (или более) автоматных моделей: автоматной модели, описывающей тестируемую реализацию, а также автоматной модели, описывающий окружающую среду (контекст), который определяет условия и правила трансляции тестовой последовательности. Однако на практике возможны более сложные (автоматные) взаимодействия.
Следует отметить, что в данной работе используется параллельная композиция автоматов, которая предполагает, что в один момент времени может передаваться слово только по одному каналу связи.
По причине того, что не всегда существует возможность подать проверяющую последовательность непосредственно на тестируемую реализацию телекоммуникационного протокола, можно выделить ряд топологий в зависимости от ограничений на управляемость и наблюдаемость критической компоненты технической сложной системы, что в свою очередь, может по-разному влиять на процесс тестирования. Различные топологии зачастую присущи определенным телекоммуникационным протоколам за счет особенностей их взаимодействия с протоколами других уровней. Соответственно, иногда для возможности исследования определенной топологии тестирования в контексте необходимо обратиться к техническим средствам, которые описаны в предпоследнем подразделе данной главы. Примерами таких программных средств могут служить tcpdump, netcat, wireshark.
Третья глава посвящена описанию алгоритмов и программных реализаций инструментов, разработанных в рамках данной работы для решения различных подзадач в процессе проведения экспериментального исследования конечно автоматных методов тестирования в контексте для телекоммуникационных протоколов.
Первый раздел посвящен основным алгоритмам и программной реализации инструмента автоматизации процесса множественной подачи тестовых последовательностей на программную реализацию контекста, в которой находится реализация тестируемого телекоммуникационного протокола. Реализация инструмента для автоматического тестирования представляет собой два самостоятельных модуля, предназначенных для узконаправленных задач. Комбинация этих модулей позволяет приспосабливать инструмент под конкретные виды тестирования. Первый модуль wrap облегчает работу испытателя (тестера) и исключает человеческий фактор из процесса подачи и извлечения данных с интерфейса тестируемой программы. Второй модуль comp облегчает работу испытателя (тестера) и исключает человеческий фактор из процесса сравнения данных тестирования. Работа с модулями происходит через добавление аргументов командной строки при исполнении модуля. Порядок аргументов не важен, при использовании недопустимых аргументов или нехватке обязательных выводится соответствующее сообщение об ошибке. В разделе подробно описан алгоритм работы каждого модуля, кроме того, перечислены основные функции, написанные при реализации данного инструмента.
Для промежуточной обработки формальных представлений детерминированного полностью определенного конечного автомата и тестовых последовательностей, синтезированных на его основе (для дальнейшего использования программы FSM Test 1.0 [9]), были написаны следующие программы на языке bash.
а) table_hum2fsm.sh - программа для перевода формата определения конечного автомата из таблиц переходов и выходов в его представление посредством списка переходов;
б) fsm_hum2toolkit.sh - программа перевода формата определения конечного автомата из произвольного списка переходов в список переходов в виде хеш-значений соответствующих входных/выходных символов и состояний, а также заголовочным объявлением мощностей требуемых алфавитов для последующего использования программы FSM Test 1.0;
в) tests_toolkit2hum.sh - программа перевода списка тестовых последовательностей из вида хеш-значений соответствующих входных/выходных символов в вид соответствующих им текстовых значений для конкретного автомата, заданного списком переходов.
В разделе кратко приводятся особенности использования каждой из программ, сопровождаемые иллюстративными примерами.
В четвертой главе приведено экспериментальное исследование конечно автоматных методов тестирования в контексте для телекоммуникационного протокола TCP.
Как известно, тесты будут полными и могут быть полиномиальной длины только для класса детерминированных полностью определенных автоматов. Поскольку задача тестирования, как правило, ставит целью наибольшую полноту, исходную автоматную модель, которая расположена на сайте School of Computer Science University of St Andrews [10] следует доопределить до детерминированного, полностью определенного конечного автомата. Доопределение автоматной модели протокола TCP до полностью определенного детерминированного конечного автомата проводилось по спецификации RFC793 [7].
На первом этапе преобразования автоматной модели из соответствующей спецификации были исключены переходы по временной задержке (таймауту); для этого был увеличен соответствующий уровень абстракции модели посредством принятия во внимание предположения «о мгновенной передаче событий». Полученный детерминированный полностью определенный приведенный конечный автомат, описывающий поведение клиентской реализации TCP представляется в работе таблицей переходов.
В качестве контекста выбирается остальная часть ПО Psi Client (исключая TCP), а также реализация XMPP. Следовательно, для построения тестовых последовательностей, подаваемых через контекст, требуется определение конечных автоматов, описывающих реализации контекста. В разделе приводятся построенные детерминированные, полностью определенные конечные автоматы для компонент контекста. Для данных автоматов построены деревья преемников, усеченные на уже определенных состояниях. Возможные последовательности выходных реакций представлены регулярными выражениями.
Экспериментально исследуется полнота тестов, синтезированных классическими конечно автоматными методами, при их дальнейшей трансляции через соответствующий контекст. Рассматриваются метод Василевского (W метод). Для автомата TCP Client методом Василевского с помощью программы FSM Test 1.0 и прикладных инструментов построены наборы тестовых последовательностей. Вручную выделено подмножество тестовых последовательностей, трансляция которых возможна через контекст. Тестовые последовательности были поданы на тестируемую реализацию TCP Client через контекст. На основе анализа передаваемых по сети пакетов, был сделан вывод о несоответствии реализации TCP в ПО Psi ее спецификации, заданной конечным автоматом. А именно, проверяемая реализация передала по сети пакет с флагами FIN и ACK, находясь в состоянии, в котором спецификация не допускает передачу пакета с данными флагами.
В пятой главе обсуждаются приложения результатов, полученных в работе. В частности, приводится дискуссия о том, каким образом полученные результаты могут быть использованы при тестировании телекоммуникационных протоколов различных уровней. Обсуждается влияние выбора границы между проверяемой реализацией и ее контекстом на полноту транслированного теста на примере тестирования реализации протокола TFTP. Рассмотрены возможные проблемы при тестировании других телекоммуникационных протоколов различных уровней при использовании разных топологий доступности встраиваемой компоненты для управления и наблюдения. С другой стороны, во втором части главы приводится дискуссия, затрагивающая возможности управляемости и наблюдаемости не только проверяемой реализации, но и ее контекста. Обсуждаются ситуации возникновения ограничений на управление контекстом проверяемой компоненты. Показывается, каким образом конечно автоматные модели могут быть использованы при мониторинге проверяемой протокольной реализации с целью проверки ее функциональных и нефункциональных свойств.
В заключении кратко перечисляются полученные в диссертации результаты, и обсуждаются перспективы дальнейших научных исследований.
Известны следующие исторические факты фатального влияния ошибки ПО на человеческую жизнь.
а) В 1980-х годах пять пациентов умерли после получения большой дозы рентгеновских лучей в результате ошибки в программировании машины для лучевой терапии Therac-25. Авария, как полагают, была вызвана сбоем, который повлиял на производительность системы [1].
б) Четвертого июня 1996 года Европейское космическое агентство произвело испытательный пуск ракеты Ariane 5. Ошибка в контролирующем программном обеспечении, написанном на языке программирования Ada, вызвала самоликвидацию ракеты через 37 секунд после взлета [2].
в) В 2007 году счета более 3 миллионов клиентов одного из крупнейших банков Великобритании оказались под угрозой взлома из-за ошибки в системе безопасности [3].
г) Расследование NASA в 2007 году установило, что космический зонд Mars Global Surveyor перестал работать из-за ошибки в программном обеспечении, допущенной за пять месяцев до его гибели [4].
д) В 2009 году 206 пациентов клиники Cedars-Sinai Medical Center в Лос-Анджелесе были облучены недопустимо высокой дозой радиации в результате ошибки в программе спирального томографа [5].
е) В 2012 году сбой компьютера чуть не привел инвестиционную компанию Knight Capital к банкротству. Фирма потеряла полмиллиарда долларов через полчаса после того, как ошибка программного обеспечения позволила в автоматическом режиме системе самой покупать и продавать акции без надзора человека. Цена на акции компании упала на 75 процентов в течение двух дней [5].
Следует отметить, что в ходе разработки ПО изначально формируются требования к итоговому продукту, это означает, что задается некоторая спецификация. Спецификация содержит в себе список требований и характеристик, которым должна соответствовать разрабатываемая программная реализация. В спецификации описывается вся необходимая информация о поведении системы и о разнообразии ситуаций, которые могут возникать при ее взаимодействии с другими системами или людьми. Таким образом, наиболее распространенные методы тестирования предназначены именно для проверки, соответствует ли разработанная программа исходной спецификации (тестирование соответствия или conformance testing). При этом известно, что гарантированная полнота тестирования возможна только при условии привлечения формальных моделей и, в частности, конечно автоматных моделей. Тестирование на основе формальных моделей заключается в следующем. По спецификации, которая является неформальным описанием с набором требований к программному обеспечению, строится формальная модель; на основе полученной модели строится множество тестовых последовательностей, которые в дальнейшем подаются на соответствующую данной спецификации проверяемую программную реализацию. На основании наблюдаемых выходных реакций делается заключение о соответствии проверяемой программной реализации ее спецификации.
С другой стороны, время тестирования, как правило, является ограниченным, соответственно, с учетом роста количества ошибок возрастает необходимость в эффективном и быстром тестировании. Однако, по причине встраиваемости тестируемой критической части в более крупную реализацию, подача тестов на нее может быть затруднено . Так, например, множество телекоммуникационных протоколов инкапсулируется в телекоммуникационный протокол, который находится выше уровнем по сетевой модели OSI, и поэтому программные реализации исследуемых телекоммуникационных протоколов часто являются внутренними частями более сложного ПО. Таким образом, необходимо не только синтезировать качественные тесты для реализаций телекоммуникационных протоколов, но и принимать во внимание невозможность прямой подачи данных последовательностей на проверяемую реализацию. Иными словами, требуется также решать задачу трансляции синтезируемых тестовых последовательностей через некоторый контекст. В данной работе экспериментально исследуются методы тестирования в контексте для телекоммуникационных протоколов. Тестирование проводится на основе дискетных моделей, а именно, конечных автоматов.
Целью работы является экспериментальное исследование конечно автоматных методов тестирования в контексте для программных реализаций телекоммуникационных протоколов.
Методы исследования. Для достижения поставленной цели в работе используется аппарат дискретной математики, в частности, для синтеза тестов и их последующей трансляции привлекаются методы классической теории автоматов, комбинаторики и математической логики. Эффективность предлагаемых подходов оценивается посредством компьютерных экспериментов с существующими или разработанными автором программными реализациями телекоммуникационных протоколов.
Научная новизна.
Научная новизна работы заключается в следующем.
а) В работе предложена эвристика для адаптации известных конечно автоматных методов тестирования в контексте для телекоммуникационных протоколов.
б) Компьютерные эксперименты с реализациями телекоммуникационных протоколов (в частности, с реализацией протокола TCP, встроенной в программное обеспечение Psi) подтверждают эффективность предложенной эвристики.
в) Проведенные компьютерные эксперименты позволили выявить несоответствие реализации протокола TCP, встроенной в ПО Psi [6] версии 0.15-2 спецификации протокола TCP, представленной в RFC 793 [7].
Основные положения, выносимые на защиту.
а) Предложена эвристика для адаптации известных конечно автоматных методов для тестирования телекоммуникационных протоколов в контексте, которая основана на синтезе усеченного дерева приемников, представляющего контекст, и позволяет проверять функционирование других встроенных технических систем на основе конечно автоматных моделей.
б) Результаты экспериментального исследования по тестированию
телекоммуникационных протоколов в контексте на основе конечно автоматных моделей, которые, в частности, позволили выявить несоответствие реализации протокола TCP, встроенной в ПО Psi (версия 0.15-2) спецификации протокола TCP, представленной в RFC 793.
Достоверность результатов. Эффективность предложенного подхода подтверждается компьютерными экспериментами с реализациями телекоммуникационных протоколов и, в частности, с реализацией телекоммуникационного протокола TCP, встроенной в ПО Psi версии 0.15-2. При этом дерево преемников контекста Psi было усечено при максимальной длине наблюдаемых последовательностей, равной шести.
Практическая ценность. Результаты работы могут быть использованы при тестировании реальных систем, поведение которых может быть описано посредством конечно автоматных моделей. Разработанные программные реализации инструментов автоматизации подачи тестовых последовательностей и сравнения результатов могут быть использованы при тестировании программного обеспечения различного назначения и на основе различных подходов к синтезу тестов. Разработанные программные реализации инструментов трансляции различных представлений конечного автомата могут быть использованы при синтезе тестов для технических систем на основе конечно автоматных моделей с использованием различных автоматизированных средств, например, FSM test 1.0. Построенная формальная спецификация для протокола TCP в виде конечного детерминированного автомата может быть использована при синтезе тестов для реализации этого протокола, встроенного в иное программное обеспечение (отличное от Psi).
Апробация работы. Основные положения и результаты, представленные в работе, были представлены на двух Российских конференциях с международным участием «Новые информационные технологии в исследовании сложных структур» на Алтае (2014 г.) и Екатеринбурге (2016 г.), а также на международной Летней Школе IT CoSAS в Анапе (2015 г.). По результатам работы опубликована одна статья в журнале, входящем в Перечень ВАК.
Структура и объем работы. Магистерская диссертация включает введение, 5 глав, заключение и список используемой литературы. Диссертация содержит 20 рисунков и 1 таблицу. Объем работы составляет 58 страниц, в том числе: титульный лист - одна страница, оглавление - 2 страницы, основной текст - 52 страницы, список использованных
литературных источников из 43 наименований - 3 страницы.
Во введении обсуждается актуальность и цель работы, формулируются положения, выносимые на защиту, а также отмечается апробация работы.
В первой главе приводятся основные определения и обозначения, используемые в работе; представляется краткий обзор видов и способов тестирования программного обеспечения, в том числе, методов синтеза тестов для моделей черного и белого ящика для тестирования в контексте (на основе формальных моделей).
Работа посвящена исследованию актуальной задачи, а именно, задачи тестирования реализаций телекоммуникационных протоколов. Телекоммуникационный протокол регламентирует процедуру и формат взаимодействия между некоторым количеством независимых компонент, которые могут являться устройствами, компьютерами, программами или процессами [8].
Тестирование программных реализаций телекоммуникационных протоколов является серьезной задачей при текущем большом распространении сетей и распределенных служб. Богатство разнообразия сетей и быстро увеличивающееся число соединений между ними объясняется как растущим числом взаимодействующих компонент, так и созданием множества принципиально новых телекоммуникационных протоколов, для которых требуется взаимодействие с существующими техническими системами. Гарантированная полнота тестирования возможна только с применением формальных моделей, и среди формальных моделей, на основе которых могут синтезироваться тесты, для таких систем и, в частности, для программного обеспечения выделяют модели с конечным числом переходов. В данной работе в качестве такой модели рассматривается конечный автомат. Под конечным автоматом S понимается пятерка S = (S, I, O, Ts, so), где S - множество состояний c выделенным начальным состоянием so, I - входной алфавит, O - выходной алфавит, T - отношение переходов, T о S * I * O * S.
Задачи анализа конечные автоматы являются хорошо изученными, и в настоящий момент известны методы построения проверяющих тестов для конечных автоматов. Тем не менее, проверяющие тесты, построенные для автоматов, которые описывают поведение реальной системы целиком, могут иметь слишком большие размеры для проведения эксперимента за некоторое отведенное время. Поэтому для тестирования часто выбирают только критическую компоненту технической системы, полнота тестирования которой должны быть гарантирована. Однако такая компонента может быть недоступна для прямой подачи тестовой последовательности. Другими словами, тестируемая реализация находится в контексте.
Данная диссертация посвящена исследованию тестирования в контексте для телекоммуникационных протоколов. Соответственно, в первой главе отдельный раздел посвящен методам синтеза тестов на основе формальных моделей (в том числе, в контексте), а также методам синтеза тестов для телекоммуникационных протоколов.
Во второй главе описывается постановка задачи, а именно, обсуждается проблема тестирования в контексте для реализаций телекоммуникационных протоколов. Обсуждаются различные топологии тестирования в контексте при исследовании телекоммуникационных протоколов, рассматриваются особенности технических реализаций предложенных топологий. Предлагается эвристика для адаптации известных конечно автоматных методов тестирования в контексте телекоммуникационных протоколов.
Основная идея тестирования в контексте заключается в том, что тестер не имеет прямого доступа к тестируемой реализации и вынужден взаимодействовать с ней через контекст некоторой иной реализации. Следовательно, тестовая последовательность должна быть транслирована через контекст, что влияет на полноту и сложность метода синтеза тестов.
Упоминая синтез тестов в контексте для автоматных моделей, мы предполагаем композицию двух (или более) автоматных моделей: автоматной модели, описывающей тестируемую реализацию, а также автоматной модели, описывающий окружающую среду (контекст), который определяет условия и правила трансляции тестовой последовательности. Однако на практике возможны более сложные (автоматные) взаимодействия.
Следует отметить, что в данной работе используется параллельная композиция автоматов, которая предполагает, что в один момент времени может передаваться слово только по одному каналу связи.
По причине того, что не всегда существует возможность подать проверяющую последовательность непосредственно на тестируемую реализацию телекоммуникационного протокола, можно выделить ряд топологий в зависимости от ограничений на управляемость и наблюдаемость критической компоненты технической сложной системы, что в свою очередь, может по-разному влиять на процесс тестирования. Различные топологии зачастую присущи определенным телекоммуникационным протоколам за счет особенностей их взаимодействия с протоколами других уровней. Соответственно, иногда для возможности исследования определенной топологии тестирования в контексте необходимо обратиться к техническим средствам, которые описаны в предпоследнем подразделе данной главы. Примерами таких программных средств могут служить tcpdump, netcat, wireshark.
Третья глава посвящена описанию алгоритмов и программных реализаций инструментов, разработанных в рамках данной работы для решения различных подзадач в процессе проведения экспериментального исследования конечно автоматных методов тестирования в контексте для телекоммуникационных протоколов.
Первый раздел посвящен основным алгоритмам и программной реализации инструмента автоматизации процесса множественной подачи тестовых последовательностей на программную реализацию контекста, в которой находится реализация тестируемого телекоммуникационного протокола. Реализация инструмента для автоматического тестирования представляет собой два самостоятельных модуля, предназначенных для узконаправленных задач. Комбинация этих модулей позволяет приспосабливать инструмент под конкретные виды тестирования. Первый модуль wrap облегчает работу испытателя (тестера) и исключает человеческий фактор из процесса подачи и извлечения данных с интерфейса тестируемой программы. Второй модуль comp облегчает работу испытателя (тестера) и исключает человеческий фактор из процесса сравнения данных тестирования. Работа с модулями происходит через добавление аргументов командной строки при исполнении модуля. Порядок аргументов не важен, при использовании недопустимых аргументов или нехватке обязательных выводится соответствующее сообщение об ошибке. В разделе подробно описан алгоритм работы каждого модуля, кроме того, перечислены основные функции, написанные при реализации данного инструмента.
Для промежуточной обработки формальных представлений детерминированного полностью определенного конечного автомата и тестовых последовательностей, синтезированных на его основе (для дальнейшего использования программы FSM Test 1.0 [9]), были написаны следующие программы на языке bash.
а) table_hum2fsm.sh - программа для перевода формата определения конечного автомата из таблиц переходов и выходов в его представление посредством списка переходов;
б) fsm_hum2toolkit.sh - программа перевода формата определения конечного автомата из произвольного списка переходов в список переходов в виде хеш-значений соответствующих входных/выходных символов и состояний, а также заголовочным объявлением мощностей требуемых алфавитов для последующего использования программы FSM Test 1.0;
в) tests_toolkit2hum.sh - программа перевода списка тестовых последовательностей из вида хеш-значений соответствующих входных/выходных символов в вид соответствующих им текстовых значений для конкретного автомата, заданного списком переходов.
В разделе кратко приводятся особенности использования каждой из программ, сопровождаемые иллюстративными примерами.
В четвертой главе приведено экспериментальное исследование конечно автоматных методов тестирования в контексте для телекоммуникационного протокола TCP.
Как известно, тесты будут полными и могут быть полиномиальной длины только для класса детерминированных полностью определенных автоматов. Поскольку задача тестирования, как правило, ставит целью наибольшую полноту, исходную автоматную модель, которая расположена на сайте School of Computer Science University of St Andrews [10] следует доопределить до детерминированного, полностью определенного конечного автомата. Доопределение автоматной модели протокола TCP до полностью определенного детерминированного конечного автомата проводилось по спецификации RFC793 [7].
На первом этапе преобразования автоматной модели из соответствующей спецификации были исключены переходы по временной задержке (таймауту); для этого был увеличен соответствующий уровень абстракции модели посредством принятия во внимание предположения «о мгновенной передаче событий». Полученный детерминированный полностью определенный приведенный конечный автомат, описывающий поведение клиентской реализации TCP представляется в работе таблицей переходов.
В качестве контекста выбирается остальная часть ПО Psi Client (исключая TCP), а также реализация XMPP. Следовательно, для построения тестовых последовательностей, подаваемых через контекст, требуется определение конечных автоматов, описывающих реализации контекста. В разделе приводятся построенные детерминированные, полностью определенные конечные автоматы для компонент контекста. Для данных автоматов построены деревья преемников, усеченные на уже определенных состояниях. Возможные последовательности выходных реакций представлены регулярными выражениями.
Экспериментально исследуется полнота тестов, синтезированных классическими конечно автоматными методами, при их дальнейшей трансляции через соответствующий контекст. Рассматриваются метод Василевского (W метод). Для автомата TCP Client методом Василевского с помощью программы FSM Test 1.0 и прикладных инструментов построены наборы тестовых последовательностей. Вручную выделено подмножество тестовых последовательностей, трансляция которых возможна через контекст. Тестовые последовательности были поданы на тестируемую реализацию TCP Client через контекст. На основе анализа передаваемых по сети пакетов, был сделан вывод о несоответствии реализации TCP в ПО Psi ее спецификации, заданной конечным автоматом. А именно, проверяемая реализация передала по сети пакет с флагами FIN и ACK, находясь в состоянии, в котором спецификация не допускает передачу пакета с данными флагами.
В пятой главе обсуждаются приложения результатов, полученных в работе. В частности, приводится дискуссия о том, каким образом полученные результаты могут быть использованы при тестировании телекоммуникационных протоколов различных уровней. Обсуждается влияние выбора границы между проверяемой реализацией и ее контекстом на полноту транслированного теста на примере тестирования реализации протокола TFTP. Рассмотрены возможные проблемы при тестировании других телекоммуникационных протоколов различных уровней при использовании разных топологий доступности встраиваемой компоненты для управления и наблюдения. С другой стороны, во втором части главы приводится дискуссия, затрагивающая возможности управляемости и наблюдаемости не только проверяемой реализации, но и ее контекста. Обсуждаются ситуации возникновения ограничений на управление контекстом проверяемой компоненты. Показывается, каким образом конечно автоматные модели могут быть использованы при мониторинге проверяемой протокольной реализации с целью проверки ее функциональных и нефункциональных свойств.
В заключении кратко перечисляются полученные в диссертации результаты, и обсуждаются перспективы дальнейших научных исследований.
В работе рассмотрена актуальная задача синтеза проверяющих тестов для реализаций телекоммуникационных протоколов. В частности, исследован случай тестирования соответствующих реализаций в контексте другого программного обеспечения. Данная задача возникает при отсутствии прямого доступа к проверяемой протокольной реализации, и, соответственно, не каждая тестовая последовательность может быть транслирована через предъявленную внешнюю среду (контекст).
Работа посвящена экспериментальному исследованию конечно автоматных методов синтеза тестов для реализаций телекоммуникационных протоколов. В этом случае и проверяемая реализация, и ее контекст описываются подходящими конечными автоматами (или другими автоматными моделями). Для упрощения задачи трансляции теста в работе предложена эвристика для адаптации известных конечно автоматных методов для тестирования телекоммуникационных протоколов в контексте, которая основана на синтезе усеченного дерева приемников, представляющего контекст. Ее эффективность подтверждается результатами экспериментального исследования по тестированию телекоммуникационных протоколов в контексте на основе конечно автоматных моделей, которые, в частности, позволили выявить несоответствие реализации протокола TCP, встроенной в ПО Psi (версия 0.15-2) спецификации протокола TCP, представленной в RFC 793.
Следует отметить, что данная эвристика может быть использована при тестировании других технических систем в контексте, описанных автоматными моделями.
В работе также приводится дискуссия, каким образом предложенный подход может быть адаптирован на случай мониторинга телекоммуникационной сети с целью проверки корректности функционирования протокольных реализаций. В этом случае предложено использовать последовательности, наблюдение которых позволяет заключить о текущем состоянии реализации.
Ряд вопросов, непосредственно относящихся к задаче тестирования в контексте для протокольных реализаций, остался за рамками работы. В частности, не исследованы методы синтеза и трансляции тестов для неклассических автоматных моделей. Не автоматизирован процесс трансляции тестов для классических конечных автоматов. Компьютерные эксперименты проведены только для реализаций протокола TCP - другие протокола остались за рамками диссертационной работы. Отметим, что эти и другие вопросы открывают перспективы для дальнейших научных
Работа посвящена экспериментальному исследованию конечно автоматных методов синтеза тестов для реализаций телекоммуникационных протоколов. В этом случае и проверяемая реализация, и ее контекст описываются подходящими конечными автоматами (или другими автоматными моделями). Для упрощения задачи трансляции теста в работе предложена эвристика для адаптации известных конечно автоматных методов для тестирования телекоммуникационных протоколов в контексте, которая основана на синтезе усеченного дерева приемников, представляющего контекст. Ее эффективность подтверждается результатами экспериментального исследования по тестированию телекоммуникационных протоколов в контексте на основе конечно автоматных моделей, которые, в частности, позволили выявить несоответствие реализации протокола TCP, встроенной в ПО Psi (версия 0.15-2) спецификации протокола TCP, представленной в RFC 793.
Следует отметить, что данная эвристика может быть использована при тестировании других технических систем в контексте, описанных автоматными моделями.
В работе также приводится дискуссия, каким образом предложенный подход может быть адаптирован на случай мониторинга телекоммуникационной сети с целью проверки корректности функционирования протокольных реализаций. В этом случае предложено использовать последовательности, наблюдение которых позволяет заключить о текущем состоянии реализации.
Ряд вопросов, непосредственно относящихся к задаче тестирования в контексте для протокольных реализаций, остался за рамками работы. В частности, не исследованы методы синтеза и трансляции тестов для неклассических автоматных моделей. Не автоматизирован процесс трансляции тестов для классических конечных автоматов. Компьютерные эксперименты проведены только для реализаций протокола TCP - другие протокола остались за рамками диссертационной работы. Отметим, что эти и другие вопросы открывают перспективы для дальнейших научных
