Методы тестирования инвариантами для верификации систем анализа данных тема диссертации и автореферата по ВАК РФ 00.00.00, кандидат наук Якушева Софья Федоровна

• Якушева Софья Федоровна
• кандидат наук
• 2024

Оглавление диссертации кандидат наук Якушева Софья Федоровна

Введение

Глава 1. Общие сведения о методе тестирования инвариантами

1.1 Проблема формулирования тестового оракула и методы её решения

1.2 Тестирование инвариантами

1.3 Выводы главы

Глава 2. Методы построения тестовых инвариантов

2.1 Цели и методы исследования

2.2 Общие приёмы составления

2.2.1 Предлагаемая классификация инвариантов

2.2.2 Базовые подходы

2.3 Методы составления инвариантов в популярных областях

анализа данных

2.3.1 Поисковые алгоритмы

2.3.2 Машинное обучение

2.3.3 Глубокое обучение и нейронные сети

2.3.4 Обработка естественного языка

2.3.5 Графовые модели. Геоинформатика

2.3.6 Биоинформатика (тексты)

2.3.7 Компиляторы

2.4 Анализ применения методик построения инвариантов по областям

2.5 Обобщение методов построения

2.6 Выводы главы

Глава 3. Применение композиций и логических функций в

тестировании инвариантами многокомпонентных систем

3.1 Метод составных инвариантов

3.1.1 Определение составного инварианта

3.1.2 Метод построения составных тестовых инвариантов

Стр.

3.2 Иллюстративные примеры применения алгоритма построения составных тестовых инвариантов

3.3 Вычислительный эксперимент по проверке применимости метода

3.3.1 Система сравнительного генетического анализа тканей

как пример сложной системы

3.3.2 Тестируемая система

3.3.3 Применение алгоритма получения составных инвариантов

3.3.4 Конфигурация эксперимента

3.3.5 Результаты эксперимента

3.4 Выводы главы

Глава 4. Применение статистических методов для

тестирования инвариантами стохастических систем

4.1 Стохастические тестовые инварианты

4.1.1 Метод тестирования СТИ

4.2 Построение инвариантов для задачи многорукого бандита

4.2.1 Задача многорукого бандита. Свойства бандитов

4.2.2 Описание инвариантов

4.3 Вычислительный эксперимент по проверке применимости метода 60 4.3.1 Результаты эксперимента

4.4 Анализ результатов эксперимента

4.5 Выводы главы

Глава 5. Разработка и применение библиотеки тестирования

инвариантами алгоритмов машинного обучения

5.1 Решаемая задача

5.2 Архитектура программного комплекса для тестирования инвариантами

5.2.1 Генератор тестовых данных

5.2.2 Проверка инварианта

5.2.3 Фильтр

5.2.4 Конвейер для проведения эксперимента

5.2.5 Задачи, при решении которых применялся программный комплекс

Стр.

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

системы генерации персонализированных стикеров

5.3 Выводы главы

Глава 6. Метод выявления причин нарушения тестовых

инвариантов в системах

6.1 Причинно-следственные модели

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

6.3 Применение метода для системы генерации стикеров

6.3.1 Шаг 1. Тестируемая система и проверяемые инварианты

6.3.2 Шаг 2. Выявление влияющих факторов

6.3.3 Шаг 3. Моделирование системы. Построение и анализ причинно-следственного графа

6.3.4 Шаг 4. Получение байесовской сети

6.3.5 Шаг 5. Постановка вычислительного эксперимента

6.3.6 Шаг 6. Результаты эксперимента

6.4 Выводы главы

Заключение

Список сокращений и условных обозначений

Словарь терминов

Список литературы

Список рисунков

Список таблиц

Приложение А. Примеры использования Программного

комплекса

А.1 Пример конфигурационного файла

Введение диссертации (часть автореферата) на тему «Методы тестирования инвариантами для верификации систем анализа данных»

Введение

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

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

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

lTsong Yueh Chen, Fei-Ching Kuo, Huai Liu et al. Metamorphic testing: A review of challenges and opportunities // ACM Computing Surveys (CSUR). — 2018. — Vol. 51, no. 1. — Pp. 1-27.

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

Основной проблемой метода является сложность составления тестовых инвариантов. На данный момент отсутствуют формализованные методики получения инвариантов, для большинства задач инварианты составляются экспертами вручную с нуля. Возможность обобщения методик осложняется тем, что исследователи, как правило, формулируют только инварианты и не описывают процесс их поиска. Многие простые тестовые инварианты оказываются непригодны для обнаружения не критических ошибок. В связи с этим разрабатываются методы автоматического получения инвариантов, составления композиций инвариантов, а также гибридные методы на базе тестирования инвариантами. В разное время разработкой и применением метода занимались T. Y. Chen, S. Segura, Z. Q. Zhou, C.-a. Sun, U. Kanewala, P. L. Poon и другие исследователи. Среди российских учёных метод пока мало известен.

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

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

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

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

Целью данной работы является разработка методов тестирования инвариантами для верификации систем анализа данных.

Для достижения поставленной цели были поставлены следующие задачи:

1. Исследовать существующие методы составления тестовых инвариантов, выявить, сформулировать и обобщить распространённые методики их составления.

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

3. Разработать метод применения тестирования инвариантами для верификации стохастических систем.

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

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

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

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

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

3. Показана применимость предлагаемого метода тестирования стохастическими инвариантами для решения задачи верификации стохастических систем.

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

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

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

автоматического тестирования инвариантами рекомендательных систем многоруких бандитов (свидетельство № 2023665316). Комплекс включен в открытую библиотеку МЬЭеу и может использоваться компаниями и исследователями для повышения качества верификации программных продуктов. Стоит отметить, что комплекс может применяться не только для тестирования систем многоруких бандитов, но и для любых стохастических систем машинного обучения.

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

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

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

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

3. Разработан метод тестирования стохастическими инвариантами стохастических систем анализа данных.

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

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

Соответствие паспорту специальности. Содержание диссертации соответствует паспорту специальности 2.3.1. Системный анализ, управление и обработка информации, статистика, в частности, пункту 1 «Теоретические основы и методы системного анализа, оптимизации, управления, принятия решений, и обработки информации и искусственного интеллекта» и пункту 11 «Методы и алгоритмы прогнозирования и оценки эффективности, качества, надежности функционирования сложных систем управления и их элементов».

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

Апробация работы. Была проведена апробация предлагаемых методов для 3 систем из разных научных областей. Основные результаты работы докладывались на международных конференциях 8th International Conference on Computer Technology Applications (ICCTA-2022) [1], 11th International Conference on Analysis of Images, Social Networks and Texts (AIST-2023) [2], Program Semantics, Specification and Verification: Theory and Applications (PSSV-2023) [3], конференции Intelligent Data Processing: Theory and Application (2022) [4], конференции «Математические методы распознавания образов (ММРО-2023)» [5], на Международных молодежных научных форумах «Л0М0Н0С0В-2021» [6] и «Л0М0Н0С0В-2023» [7], 63-й [8], 64-й [9], 65-й [10] и 66-й конференциях МФТИ [11], а также на научно-исследовательском семинаре кафедры АТП МФТИ и научных семинарах НИУ ВШЭ.

Разработанный программный комплекс использовалась для тестирования рекомендательных алгоритмов, реализованных в рамках проекта №5ГУКодИИC12-D7/72689 программы Код-ИИ при поддержке Фонда содействия инновациям. Результаты работы также были внедрены в учебный процесс по специальности 09.04.01 Информатика и вычислительная техника на кафедре алгоритмов и технологий программирования в ФГАОУ ВО «Московский физико-технический институт (национальный исследовательский университет)»

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

Публикации. Основные результаты по теме диссертации изложены в 13 печатных изданиях - 5 статьях и 8 тезисах докладов. Из них 2 статьи опубликованы в изданиях, индексируемых системой Scopus, 2 опубликованы в журналах, рекомендованных ВАК, 1 статья опубликована в журнале, индексируемом базой научного цитирования РИНЦ. При этом 2 издания, в которых были опубликованы результаты, имеют категорию К1, 1 - категорию К2 и 1 - категорию К3.

Объем и структура работы. Диссертация состоит из введения, шести глав, заключения и одного приложения. Полный объём диссертации составляет 118 страниц, включая 14 рисунков и 15 таблиц. Список литературы содержит 114 наименований.

Глава 1. Общие сведения о методе тестирования инвариантами

1.1 Проблема формулирования тестового оракула и методы её

решения

Процесс тестирования заключается в выполнении отдельных тестовых случаев и оценке правильности поведения программы в каждом из них. Правильность прохождения теста проверяется с помощью тестового оракула (test oracle [12]). В качестве оракула могут выступать человек или другая программа. Для определения правильности могут потребоваться правильный ответ (эталон), критерий правильности, экспертное мнение. Например, в области искусственного интеллекта сбор и разметка данных требуют больших временных и финансовых затрат. В области разработки диалоговых систем требуется экспертная оценка правильности поведения системы. Во многих задачах вычислительной комбинаторики и целочисленного программирования поиск точного ответа может быть произведён только методом полного перебора, что занимает длительное время, иногда превышающее допустимое. При работе со стохастическими и распределенными системами сложно заранее предсказать конечное состояние системы после выполнения тестового сценария. Таким образом, получение тестовых оракулов, особенно автоматических, сопряжено с рядом трудностей. Эта проблема называется проблемой формулирования тестового оракула (test oracle problem [13]).

Для решения проблемы формулирования тестового оракула было предложены методы получения специфицированных (specified), производных (derived) и неявных (implicit) оракулов, а также методы снижения стоимости использования человека в качестве оракула (human oracle) [13]. Эти методы позволяют так или иначе верифицировать программу без проверки правильности каждого ответа.

Специфицированные оракулы предназначены для проверки того, что поведение программы в процессе выполнения тестового сценария удовлетворяет формальной спецификации (например, [14] и [15]). Спецификации могут быть разработаны на основе формального представления системы, а также

получены из документации [16]. Помимо этого, используются тестирование утверждениями (assertion testing [17]) и контракты (например, [18]).

Неявные оракулы [19] используются для проверки общей правильности поведения программы: отсутствия ошибок работы с памятью, гонки или взаимного блокирования потоков и т.д. Метод универсален, один и тот же неявный оракул может быть применён для тестирования многих программ. Недостатком метода является невозможность проверки индивидуальных свойств программы.

Производные оракулы используют для определения правильности прохождения теста производную информацию, которую можно получить из различных артефактов тестирования, свойств системы или других её версий. Например, при сравнительном тестировании (n-version programming [20]) сравниваются ответы нескольких версий программы или нескольких независимых реализаций, несовпадение ответов свидетельствует о наличии ошибок в какой-либо из программ. Эта идея может использоваться и при регрессионном тестировании [21], в процессе которого сравниваются поведение и результаты работы старой и новой версий тестируемой программы. Псевдо-оракул (pseudo-oracle [22]) - это альтернативная реализация тестируемой программы, разработанная независимо, и предназначенная для вычисления правильных ответов с целью последующего сравнения. К данной категории методов также относится тестирование инвариантами [23].

1.2 Тестирование инвариантами

Метод тестирования инвариантами (metamorphic testing) был предложен в 1998 году [24]. Ключевым понятием метода является тестовый инвариант(metamorphic relation).

Пусть в тестовом случае происходит п ^ 2 независимых запусков программы, Xi - исходные данные для ¿-го запуска, а f(х{) - г-й ответ программной системы f (в самом простом случае - отдельной программы). Тестовый инвариант для программы - это функция вида

R(xi,x2,...,xn,f (xi),f (х2 ),..., f (хп)) —> {0,1} (1.1)

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

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

В качестве примера рассмотрим несколько инвариантов для проверки алгоритма поиска подстроки £ в строке й.

— Повторный поиск £ в й даст тот же самый результат.

— Если произвести поиск в строке й ив строке вв, то во второй строке найдётся как минимум вдвое больше подстрок

— При добавлении к строке й любой другой строки г количество вхождений подстроки £ не должно уменьшиться.

— При обрезании строки й количество вхождений £ не должно увеличиться.

Стоит отметить, что в некоторых инвариантах для получения исходных данных для следующего тестового запуска используются результаты предыдущего. Эта идея была предложена ещё в 2005 году [25]. В недавней работе [26] также успешно используется составление данных для следующего тестового запуска по результатам предыдущего. В работе рассматривается линейная предсказательная модель, и точки выборки переносятся параллельно или перпендикулярно относительно задаваемой ей прямой.

Преимущество метода заключается в возможностях автоматизации процесса генерации тестовых случаев, и, как следствие, удешевления каждого последующего набора. Метод не имеет ограничений на минимальный размер набора тестовых случаев, и это позволяет избежать проблемы гигантского количества тестов, свойственной некоторым другим методам. Кроме того, метод позволяет получать тестовые случаи из любых подходящих исходных данных, поэтому он успешно применяется во многих предметных областях [23; 27]. В последнее время метод набирает популярность в области машинного обучения [28-31] и глубоких нейронных сетей [32-36], поскольку решает позволяет использовать для тестирования данные без разметки. Кроме того, метод применяется для проверки поисковых алгоритмов [37; 38], алгоритмов биоинформатики [39; 40] и алгоритмов построения маршрутов по картам [41; 42], анализа графовых моделей [39; 41; 43], моделей естественного языка [44-47] и эпидемиологических моделей [48; 49], компиляторов [50], алгоритмов хеширования [51] и в других областях.

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

Одним из основных направлений развития метода является разработка методов поиска инвариантов. Было разработано несколько методов поиска и комбинирования инвариантов, а также совмещения тестирования инвариантами с другими методами, например, фаззингом [52], адаптивным случайным тестированием [53]. Кроме этого, тестирование инвариантами применяется в обнаружении ошибок на основе спектров [54] и в сочетании с генетическими алгоритмами [55].

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

на основании категорий входных и выходных данных [59]. Была сделана попытка использования алгоритма БУМ для предсказания инвраиантов по вычислительным графам [60]. Ещё одним методом является анализ текстовых описаний программы на естественном языке и выделение из них свойств, определяющих инварианты [61].

Для проверки инвариантов в некоторых ситуациях уже применялись статистические методы: ЛКОУЛ [62], ранговая корреляция Спирмена [63] и другие критерии [64; 65], позволяющие оценивать случайные выборки. В ранней работе [66] исследовалась применимость статистических методов для верификации характерных свойств статистического распределения. Эти работы положили начало исследованиям применимости статистических и вероятностных методов для составления и проверки тестовых инвариантов. Пока не разработано общих приёмов использования этих методов для широких классов программ.

Ещё одно направление развития метода - разработка способов получения эффективных композиций тестовых инвариантов. Ранние исследования показали, что композиции обладают большей эффективностью по сравнению с единичными инвариантами [67]. Работа [68] посвящена теоретическому анализу построения сложных функций (композиций). В практическом исследовании по тестированию географических систем [69] в качестве инвариантов используются композиции из 2-4 инвариантов, отражающих в себе разноплановые свойства проверяемой системы. Стоит отметить, что все эти работы рассматривают системы целиком и используют инварианты только для полных систем, без анализа компонент.

На данном этапе развития метода уже производились попытки применения к сложным многокомпонентным системам. В работе [70] тестирование инвариантами применено к биоинформатической облачной системе, однако система рассматривается как чёрный ящик. Тот же подход наблюдается в работе [71] по проверке устойчивости рекомендательных систем. В работе [72] тестирование инвариантами применяется как интеграционное. В исследовании по тестированию микросервисов [37] уже применяются более сложные проверки инвариантами как отдельных микросервисов, так и системы. Вышеперечисленные исследования охватывают лишь малую часть классов сложных многокомпонентных систем. Обобщение методик пока не проводилось.

1.3 Выводы главы

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

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

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

Глава 2. Методы построения тестовых инвариантов

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

Необходимым условием применения метода тестирования инвариантами является умение составлять тестовые инварианты. Уже предложенных тестовых инвариантов для конкретных задач может не хватить для полноценного тестирования новых программ. Поэтому необходима разработка общих методов получения инвариантов «с нуля».

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

2.1 Цели и методы исследования

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

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

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

Список литературы диссертационного исследования кандидат наук Якушева Софья Федоровна, 2024 год

Список литературы

1. Iakusheva Sofia, Khritankov Anton. Composite metamorphic relations for integration testing // ACM International Conference Proceeding Series. — 2022. — Pp. 98-105.

2. Iakusheva Sofia, Khritankov Anton. Metamorphic Testing for Recommender Systems // Lecture Notes in Computer Science. — 2024. — Pp. 281-293.

3. Якушева С.Ф., Хританков А.С., Горбачёнок Д.И. Тестирование инвариантами в применении к генеративным системам искусственного интеллекта // Системная информатика. — 2023. — Vol. 22. — Pp. 37-44.

4. Iakusheva Sofia, Khritankov Anton. Testing by invariants as applied to the problem of testing recommender systems // Intelligent Data Processing: Theory and Applications: Book of abstract of the 14th International Conference. — Moscow: Russian Academy of Sciences, 2022. — Pp. 68-73.

5. Якушева С. Ф, Хританков А. С. Применение причинно-следственных графов при тестировании инвариантами // Математические методы распознавания образов: Тезисы докладов 21-й Всероссийской конференции с международным участием. — 2023. — С. 78-80.

6. Якушева С. Ф. Тестирование инвариантами в применении к сложным системам в биоинформатике // Материалы Международного молодежного научного форума «Л0М0Н0С0В-2021». — 2021.

7. Якушева С. Ф, Хританков А. С. Тестирование инвариантами в применении к задаче о многоруком бандите // Материалы Международного молодежного научного форума «ЛОМОНОСОВ-2023». — 2023.

8. Якушева С. Ф, Хританков А. С. Тестирование инвариантами в применении к инструментам биоинформатики // Труды 63-й Всероссийской научной конференции МФТИ. Прикладная математика и информатика. — 2020. — С. 246-248.

9. Якушева С. Ф, Хританков А. С. Проблема тестирования инвариантами сложных систем с допустимыми ошибками // Труды 64-й Всероссийской научной конференции МФТИ. Прикладная математика и информатика. — 2022. — С. 194-195.

10. Якушева С. Ф, Хританков А. С. Автоматическое тестирование инвариантами в применении к рекомендательным системам // Труды 65-й Всероссийской научной конференции МФТИ. Прикладная математика и информатика. — 2023. — С. 156-157.

11. Якушева С. Ф., Хританков А. С. Применение причинно-следственных графов для анализа тестовых инвариантов // Труды 66-й Всероссийской научной конференции МФТИ. Прикладная математика и информатика. — 2024.

12. Howden W.E. Theoretical and Empirical Studies of Program Testing // IEEE Transactions on Software Engineering. — 1978. — Vol. 4 (4). — P. 293-298.

13. The Oracle Problem in Software Testing: A Survey / Earl T. Barr, Mark Harman, Phil McMinn et al. // IEEE Transactions on Software Engineering. — 2015. — Vol. 41, no. 5. — Pp. 507-525.

14. Borger Egon. High level system design and analysis using abstract state machines // International Workshop on Current Trends in Applied Formal Methods / Springer. — 1998. — Pp. 1-43.

15. Utting Mark, Pretschner Alexander, Legeard Bruno. A taxonomy of model-based testing approaches // Software testing, verification and reliability.

— 2012. — Vol. 22, no. 5. — Pp. 297-312.

16. Jin Ying, Parnas David Lorge. Defining the meaning of tabular mathematical expressions // Science of Computer Programming. — 2010. — Vol. 75, no. 11.

— Pp. 980-1000.

17. Dunn Robert H. Software Defect Removal. — McGraw-Hill Book Company, New York, 1984.

18. Araujo Wladimir, Briand Lionel C, Labiche Yvan. On the effectiveness of contracts as test oracles in the detection and diagnosis of race conditions

and deadlocks in concurrent object-oriented software // 2011 International Symposium on Empirical Software Engineering and Measurement / IEEE. — 2011. — Pp. 10-19.

19. Blikle Andrzej. Proving programs by sets of computations // Mathematical Foundations of Computer Science: 3rd Symposium at Jadwisin near Warsaw, June 17-22, 1974 3 / Springer. — 1975. — Pp. 333-358.

20. Chen L, Avizienis A. N-Version Programming: A fault-tolerance approach to reliability of software operation // Proc. 8th IEEE Int.Symp. on Fault-Tolerant Computing (FTCS-8), Toulouse. — 1978. — Pp. 3—-9.

21. Yoo Shin, Harman Mark. Regression testing minimization, selection and prioritization: a survey // Software testing, verification and reliability. — 2012.

— Vol. 22, no. 2. — Pp. 67-120.

22. Davis Martin D, Weyuker Elaine J. Pseudo-oracles for non-testable programs // Proceedings of the ACM'81 Conference. — 1981. — Pp. 254-257.

23. Metamorphic testing: A review of challenges and opportunities / Tsong Yueh Chen, Fei-Ching Kuo, Huai Liu et al. // ACM Computing Surveys (CSUR). — 2018. — Vol. 51, no. 1. — Pp. 1-27.

24. Chen Tsong Y, Cheung Shing C, Yiu Shiu Ming. Metamorphic testing: a new approach for generating next test cases // arXiv preprint arXiv:2002.12543.

— 2020.

25. Wu Peng. Iterative metamorphic testing // 29th Annual International Computer Software and Applications Conference (C0MPSAC'05) / IEEE. — Vol. 1. — 2005. — Pp. 19-24.

26. Towards effective metamorphic testing by algorithm stability for linear classification programs / Yingzhuo Yang, Zenan Li, Huiyan Wang et al. // Journal of Systems and Software. — 2021. — Vol. 180. — P. 111012.

27. Chen Tsong Yueh, Tse TH. New visions on metamorphic testing after a quarter of a century of inception // Proceedings of the 29th ACM Joint Meeting on European Software Engineering Conference and Symposium on the Foundations of Software Engineering. — 2021. — Pp. 1487-1490.

28. METTLE: a METamorphic testing approach to assessing and validating unsupervised machine LEarning systems / Xiaoyuan Xie, Zhiyi Zhang, Tsong Yueh Chen et al. // IEEE Transactions on Reliability. — 2020. — Vol. 69, no. 4. — Pp. 1293-1322.

29. Testing machine learning classifiers based on compositional metamorphic relations / Minghua Jia, Xiaodong Wang, Yue Xu et al. // International Journal of Performability Engineering. — 2020. — Vol. 16, no. 1. — P. 67.

30. Saha Prashanta, Kanewala Upulee. Fault detection effectiveness of metamorphic relations developed for testing supervised classifiers // 2019 IEEE International conference on artificial intelligence testing (AITest) / IEEE. — 2019. — Pp. 157-164.

31. Metamorphic testing for quality assurance of protein function prediction tools / Morteza Pourreza Shahri, Madhusudan Srinivasan, Gillian Reynolds et al. // 2019 IEEE International Conference On Artificial Intelligence Testing (AITest) / IEEE. — 2019. — Pp. 140-148.

32. Deeptest: Automated testing of deep-neural-network-driven autonomous cars / Yuchi Tian, Kexin Pei, Suman Jana, Baishakhi Ray // Proceedings of the 40th international conference on software engineering. — 2018. — Pp. 303-314.

33. Ellis Joshua D, Iqbal Razib, Yoshimatsu Keiichi. Verification of the neural network training process for spectrum-based chemical substructure prediction using metamorphic testing // Journal of Computational Science. — 2021. — Vol. 55. — P. 101456.

34. Identifying implementation bugs in machine learning based image classifiers using metamorphic testing / Anurag Dwarakanath, Manish Ahuja, Samarth Sikand et al. // Proceedings of the 27th ACM SIGSOFT international symposium on software testing and analysis. — 2018. — Pp. 118-128.

35. DeepRoad: GAN-based metamorphic testing and input validation framework for autonomous driving systems / Mengshi Zhang, Yuqun Zhang, Lingming Zhang et al. // 2018 33rd IEEE/ACM International Conference on Automated Software Engineering (ASE) / IEEE. — 2018. — Pp. 132-142.

36. Metamorphic Testing for Edge Real-Time Face Recognition and Intrusion Detection Solution / Mourad Raif, Abdessamad El Rharras, Abdellah Chehri et al. // 2022 IEEE 96th Vehicular Technology Conference (VTC2022-Fall) / IEEE. — 2022. — Pp. 1-5.

37. Verification of microservices using metamorphic testing / Gang Luo, Xi Zheng, Huai Liu et al. // Algorithms and Architectures for Parallel Processing: 19th International Conference, ICA3PP 2019, Melbourne, VIC, Australia, December 9-11, 2019, Proceedings, Part I 19 / Springer. — 2020. — Pp. 138-152.

38. Metamorphic testing of RESTful web APIs / Sergio Segura, Jose A Parejo, Javier Troya, Antonio Ruiz-Cortes // Proceedings of the 40th International Conference on Software Engineering. — 2018. — Pp. 882-882.

39. An innovative approach for testing bioinformatics programs using metamorphic testing / Tsong Yueh Chen, Joshua WK Ho, Huai Liu, Xiaoyuan Xie // BMC bioinformatics. — 2009. — Vol. 10, no. 1. — Pp. 1-12.

40. Verification and validation of bioinformatics software without a gold standard: a case study of BWA and Bowtie / Eleni Giannoulatou, Shin-Ho Park, David T. Humphreys, Joshua WK Ho // BMC Bioinformatics. — 2014. — 12. — Vol. 15. — URL: https://doi.org/10.1186/1471-2105-15-S16-S15.

41. Testing graph searching based path planning algorithms by metamorphic testing / Jiantao Zhang, Zheng Zheng, Beibei Yin et al. // 2019 IEEE 24th Pacific Rim International Symposium on Dependable Computing (PRDC) / IEEE. — 2019. — Pp. 158-15809.

42. Iqbal Muhammad. Metamorphic Testing of Advanced Driver-Assistance Systems: Implementing Euro NCAP Standards on OpenStreetMap // 2023 IEEE/ACM 8th International Workshop on Metamorphic Testing (MET) / IEEE. — 2023. — Pp. 1-8.

43. Raunak Mohammad S, Olsen Megan M. Metamorphic testing on the continuum of verification and validation of simulation models // 2021 IEEE/ACM 6th International Workshop on Metamorphic Testing (MET) / IEEE. — 2021. — Pp. 47-52.

44. Bozic Josip, Wotawa Franz. Testing chatbots using metamorphic relations // Testing Software and Systems: 31st IFIP WG 6.1 International Conference, ICTSS 2019, Paris, France, October 15-17, 2019, Proceedings 31 / Springer.

— 2019. — Pp. 41-55.

45. Mttm: Metamorphic testing for textual content moderation software / Wenxuan Wang, Jen-tse Huang, Weibin Wu et al. // 2023 IEEE/ACM 45th International Conference on Software Engineering (ICSE) / IEEE. — 2023. — Pp. 2387-2399.

46. Chen Songqiang, Jin Shuo, Xie Xiaoyuan. Validation on machine reading comprehension software without annotated labels: A property-based method // Proceedings of the 29th ACM Joint Meeting on European Software Engineering Conference and Symposium on the Foundations of Software Engineering. — 2021. — Pp. 590-602.

47. Systematicity, Compositionality and Transitivity of Deep NLP Models: a Metamorphic Testing Perspective / Edoardo Manino, Julia Rozanova, Danilo Carvalho et al. // arXiv preprint arXiv:2204-12316. — 2022.

48. Pullum Laura L, Ozmen Ozgur. Early results from metamorphic testing of epidemiological models // 2012 ASE/IEEE International Conference on BioMedical Computing (BioMedCom) / IEEE. — 2012. — Pp. 62-67.

49. Ramanathan Arvind, Steed Chad A, Pullum Laura L. Verification of compartmental epidemiological models using metamorphic testing, model checking and visual analytics // 2012 ASE/IEEE International Conference on BioMedical Computing (BioMedCom) / IEEE. — 2012. — Pp. 68-73.

50. Metamorphic testing of deep learning compilers / Dongwei Xiao, Zhibo Liu, Yuanyuan Yuan et al. // Proceedings of the ACM on Measurement and Analysis of Computing Systems. — 2022. — Vol. 6, no. 1. — Pp. 1-28.

51. Sun Chang-ai, Wang Zuoyi, Wang Guan. A property-based testing framework for encryption programs // Frontiers of Computer Science. — 2014. — Vol. 8.

— Pp. 478-489.

52. Zhou Zhi Quan, Sun Liqun. Metamorphic testing of driverless cars // Communications of the ACM. — 2019. — Vol. 62, no. 3. — Pp. 61-67.

53. MT-ART: A test case generation method based on adaptive random testing and metamorphic relation / Zhan-wei Hui, Xiaojuan Wang, Song Huang, Sen Yang // IEEE Transactions on Reliability. — 2021. — Vol. 70, no. 4.

— Pp. 1397-1421.

54. Metamorphic slice: An application in spectrum-based fault localization / Xiaoyuan Xie, W Eric Wong, Tsong Yueh Chen, Baowen Xu // Information and Software Technology. — 2013. — Vol. 55, no. 5. — Pp. 866-879.

55. MTGP: Combining Metamorphic Testing and Genetic Programming / Dominik Sobania, Martin Briesch, Philipp Rochner, Franz Rothlauf // European Conference on Genetic Programming (Part of EvoStar) / Springer.

— 2023. — Pp. 324-338.

56. Tambon Florian, Antoniol Giulio, Khomh Foutse. HOMRS: High Order Metamorphic Relations Selector for Deep Neural Networks // arXiv preprint arXiv:2107.04863. — 2021.

57. RBF-MLMR: A multi-label metamorphic relation prediction approach using RBF neural network / Pengcheng Zhang, Xuewu Zhou, Patrizio Pelliccione, Hareton Leung // IEEE access. — 2017. — Vol. 5. — Pp. 21791-21805.

58. Search-based inference of polynomial metamorphic relations / Jie Zhang, Junjie Chen, Dan Hao et al. // Proceedings of the 29th ACM/IEEE international conference on Automated software engineering. — 2014. — Pp. 701-712.

59. METRIC++: A Metamorphic Relation Identification Technique Based on Input Plus Output Domains / Chang-Ai Sun, An Fu, Pak-Lok Poon et al. // IEEE Transactions on Software Engineering. — 2019. — Vol. 47, no. 9. — Pp. 1764-1785.

60. Kanewala Upulee, Bieman James M, Ben-Hur Asa. Predicting metamorphic relations for testing scientific software: a machine learning approach using graph kernels // Software testing, verification and reliability. — 2016. — Vol. 26, no. 3. — Pp. 245-269.

61. MeMo: Automatically identifying metamorphic relations in Javadoc comments for test automation / Arianna Blasi, Alessandra Gorla, Michael D Ernst et al. // Journal of systems and software. — 2021. — Vol. 181. — P. 111041.

62. A Monte Carlo method for metamorphic testing of machine translation services / Daniel Pesu, Zhi Quan Zhou, Jingfeng Zhen, Dave Towey // Proceedings of the 3rd International Workshop on Metamorphic Testing. — 2018. — Pp. 38-45.

63. Zhou Zhi Quan, Tse TH, Witheridge Matt. Metamorphic robustness testing: Exposing hidden defects in citation statistics and journal impact factors // IEEE Transactions on Software Engineering. — 2019. — Vol. 47, no. 6. — Pp. 1164-1183.

64. Testing web enabled simulation at scale using metamorphic testing / John Ahlgren, Maria Berezin, Kinga Bojarczuk et al. // 2021 IEEE/ACM 43rd International Conference on Software Engineering: Software Engineering in Practice (ICSE-SEIP) / IEEE. — 2021. — Pp. 140-149.

65. ur Rehman Faqeer, Izurieta Clemente. Statistical Metamorphic Testing of Neural Network Based Intrusion Detection Systems // 2021 IEEE International Conference on Cyber Security and Resilience (CSR) / IEEE. — 2021. — Pp. 20-26.

66. Guderlei Ralph, Mayer Johannes. Statistical metamorphic testing testing programs with random output by means of statistical hypothesis tests and metamorphic testing // Seventh International Conference on Quality Software (QSIC 2007) / IEEE. — 2007. — Pp. 404-409.

67. Liu Huai, Liu Xuan, Chen Tsong Yueh. A new method for constructing metamorphic relations // 2012 12th international conference on quality software / IEEE. — 2012. — Pp. 59-68.

68. Theoretical and empirical analyses of the effectiveness of metamorphic relation composition / Kun Qiu, Zheng Zheng, Tsong Yueh Chen, Pak-Lok Poon // IEEE Transactions on software engineering. — 2020. — Vol. 48, no. 3. — Pp. 1001-1017.

69. Semiautomated metamorphic testing approach for geographic information systems: An empirical study / Zhan-Wei Hui, Song Huang, Caslon Chua, Tsong Yueh Chen // IEEE Transactions on Reliability. — 2019. — Vol. 69, no. 2. — Pp. 657-673.

70. A Cloud-Based Framework for Applying Metamorphic Testing to a Bioinformatics Pipeline / Michael Troup, Andrian Yang, Amir Hossein Kamali et al. // Proceedings of the 1st International Workshop on Metamorphic Testing. — MET '16. — New York, NY, USA: Association for Computing Machinery, 2016. — P. 33-36. — URL: https://doi.org/10.1145/2896971. 2896975.

71. Mao Chengying, Yi Xiaorong, Chen Tsong Yueh. Metamorphic Robustness Testing for Recommender Systems: A Case Study // 2020 7th International Conference on Dependable Systems and Their Applications (DSA) / IEEE. — 2020. — Pp. 331-336.

72. A metamorphic approach to integration testing of context-sensitive middleware-based applications / W.K. Chan, T.Y. Chen, Heng Lu et al. // Fifth International Conference on Quality Software (QSIC'05). — 2005. — Pp. 241-249.

73. Kitchenham Barbara. Procedures for performing systematic reviews // Keele, UK, Keele University. — 2004. — Vol. 33, no. 2004. — Pp. 1-26.

74. Фальковский Р.Р. Метаморфное тестирование программ улучшения изображений // XIX Международная телекоммуникационная конференция молодых ученых и студентов «МОЛОДЕЖЬ И НАУКА». Тезисы докладов. Ч. 3. М.: НИЯУ МИФИ, 2015.-268 с. — 2015. — С. 176.

75. Миронов Андрей Михайлович. Верификация программ методом инвариантов // Интеллектуальные системы. Теория и приложения. — 2017. — Т. 21, № 4. — С. 31-49.

76. Wu Chaohua, Sun Liqun, Zhou Zhi Quan. The impact of a dot: Case studies of a noise metamorphic relation pattern // 2019 IEEE/ACM 4th International Workshop on Metamorphic Testing (MET) / IEEE. — 2019. — Pp. 17-23.

77. Nakajima Shin, Chen Tsong Yueh. Generating biased dataset for metamorphic testing of machine learning programs // Testing Software and Systems: 31st IFIP WG 6.1 International Conference, ICTSS 2019, Paris, France, October 15-17, 2019, Proceedings 31 / Springer. — 2019. — Pp. 56-64.

78. TEA-Cloud: A formal framework for testing cloud computing systems / Alberto Núñez, Pablo C Cañizares, Manuel Núñez, Robert M Hierons // IEEE Transactions on Reliability. — 2020. — Vol. 70, no. 1. — Pp. 261-284.

79. Yoo Shin. Metamorphic testing of stochastic optimisation // 2010 Third International Conference on Software Testing, Verification, and Validation Workshops / IEEE. — 2010. — Pp. 192-201.

80. An Interleaving Guided Metamorphic Testing Approach for Concurrent Programs / Chang-ai Sun, Hepeng Dai, Ning Geng et al. // ACM Transactions on Software Engineering and Methodology. — 2023.

81. Quality assurance of bioinformatics software: a case study of testing a biomedical text processing tool using metamorphic testing / Madhusudan Srinivasan, Morteza Pourreza Shahri, Indika Kahanda, Upulee Kanewala // Proceedings of the 3rd International Workshop on Metamorphic Testing. — 2018. — Pp. 26-33.

82. A cloud-based framework for applying metamorphic testing to a bioinformatics pipeline / Michael Troup, Andrian Yang, Amir Hossein Kamali et al. // Proceedings of the 1st International Workshop on Metamorphic Testing. — 2016. — Pp. 33-36.

83. Metamorphic testing of chess engines / Manuel Mendez, Miguel Benito-Parejo, Alfredo Ibias, Manuel Núñez // Information and Software Technology. — 2023. — P. 107263.

84. Metamorphic relations for enhancing system understanding and use / Zhi Quan Zhou, Liqun Sun, Tsong Yueh Chen, Dave Towey // IEEE Transactions on Software Engineering. — 2018. — Vol. 46, no. 10. — Pp. 1120-1154.

85. Finding Bugs in Cryptographic Hash Function Implementations / Nicky Mouha, Mohammad S. Raunak, D. Richard Kuhn, Raghu Kacker // IEEE Transactions on Reliability. — 2018. — Vol. 67, no. 3. — Pp. 870-884.

86. Brown Joshua, Zhou Zhi Quan, Chow Yang-Wai. Metamorphic testing of navigation software: A pilot study with Google Maps. — 2018.

87. Robustness Evaluation of Stacked Generative Adversarial Networks using Metamorphic Testing / Hyejin Park, Taaha Waseem, Wen Qi Teo et al. // 2021 IEEE/ACM 6th International Workshop on Metamorphic Testing (MET) / IEEE. — 2021. — Pp. 1-8.

88. Enhancing supervised classifications with metamorphic relations / Liming Xu, Dave Towey, Andrew P French et al. // Proceedings of the 3rd International Workshop on Metamorphic Testing. — 2018. — Pp. 46-53.

89. Stability evaluation for text localization systems via metamorphic testing / Rongjie Yan, Siqi Wang, Yixuan Yan et al. // Journal of Systems and Software. — 2021. — Vol. 181. — P. 111040.

90. Deepbackground: Metamorphic testing for deep-learning-driven image recognition systems accompanied by background-relevance / Zhiyi Zhang, Pu Wang, Hongjing Guo et al. // Information and Software Technology. — 2021. — Vol. 140. — P. 106701.

91. Datamorphic testing: A methodology for testing AI applications / Hong Zhu, Dongmei Liu, Ian Bayley et al. // arXiv preprint arXiv:1912.04900. — 2019.

92. Ma Pingchuan, Wang Shuai, Liu Jin. Metamorphic Testing and Certified Mitigation of Fairness Violations in NLP Models. // IJCAI. — 2020. — Pp. 458-465.

93. Metamorphic Testing of Relation Extraction Models / Yuhe Sun, Zuohua Ding, Hongyun Huang et al. // Algorithms. — 2023. — Vol. 16, no. 2. — P. 102.

94. Sun Liqun, Zhou Zhi Quan. Metamorphic testing for machine translations: MT4MT // 2018 25th Australasian Software Engineering Conference (ASWEC) / IEEE. — 2018. — Pp. 96-100.

95. Gao Wentao, He Jiayuan, Pham Van-Thuan. Metamorphic Testing of Machine Translation Models using Back Translation // 2023 IEEE/ACM International Workshop on Deep Learning for Testing and Testing for Deep Learning (DeepTest) / IEEE. — 2023. — Pp. 1-8.

96. Donaldson Alastair F, Lascu Andrei. Metamorphic testing for (graphics) compilers // Proceedings of the 1st international workshop on metamorphic testing. — 2016. — Pp. 44-47.

97. Le Vu, Afshari Mehrdad, Su Zhendong. Compiler validation via equivalence modulo inputs // ACM Sigplan Notices. — 2014. — Vol. 49, no. 6. — Pp. 216-226.

98. Li Heng. Aligning sequence reads, clone sequences and assembly contigs with BWA-MEM. — 2013.

99. Strelka2: fast and accurate calling of germline and somatic variants. / Sangtae Kim, Konrad Scheffler, Aaron L Halpern et al. // Nat Methods. — 2018. — Vol. 15 (8).

100. Sequenza: allele-specific copy number and mutation profiles from tumor sequencing data. / F Favero, T Joshi, A M Marquard et al. // Annals of oncology : official journal of the European Society for Medical Oncology. — 2015. — Vol. 26 (1). — Pp. 64-79.

101. Riley Alex B, Kim Dohyup, Hansen Allison K. Genome Sequence of Candidatus Carsonella ruddii Strain BC, a Nutritional Endosymbiont of Bactericera cockerelli. // Genome announcements. — 2017. — April. — Vol. 5 (17).

102. Slivkins Aleksandrs. Introduction to Multi-Armed Bandits // Foundations and Trends in Machine Learning. — 2019. — Vol. 12, no. 1-2. — Pp. 1-286. — URL: http://dx.doi.org/10.1561/2200000068.

103. Recommender Systems Handbook / Francesco Ricci, Lior Rokach, Bracha Shapira, Paul B. Kantor. — Berlin, Heidelberg: Springer-Verlag, 2010.

104. The nonstochastic multiarmed bandit problem / Peter Auer, Nicolo Cesa-Bianchi, Yoav Freund, Robert E Schapire // SIAM journal on computing. — 2002. — Vol. 32, no. 1. — Pp. 48-77.

105. Russo D.J., Roy B.V., Kazerouni A. et al. A Tutorial on Thompson Sampling. Foundations and Trends R in Machine Learning 11 (1), 1-96. — 2018.

106. Non stationary multi-armed bandit: Empirical evaluation of a new concept drift-aware algorithm / Emanuele Cavenaghi, Gabriele Sottocornola, Fabio Stella, Markus Zanker // Entropy. — 2021. — Vol. 23, no. 3. — P. 380.

107. MLDev: Data Science Experiment Automation and Reproducibility Software / Anton Khritankov, Nikita Pershin, Nikita Ukhov, Artem Ukhov // Data Analytics and Management in Data Intensive Domains. — Cham: Springer International Publishing, 2022. — Pp. 3-18.

108. Wang Jianqiang C, Meyer Mary C. Testing the monotonicity or convexity of a function using regression splines // Canadian Journal of Statistics. — 2011.

— Vol. 39, no. 1. — Pp. 89-107.

109. Якушева Софья Федоровна, Хританков Антон Сергеевич. Систематический обзор методов составления тестовых инвариантов // Программные системы: теория и приложения. — 2024. — Т. 15, № 2. — С. 37-86.

110. Wright S. Correlation and causation // Journal of Agricultural Research. — 1921. — Vol. 20. — Pp. 557-585.

111. Pearl J. et al. Causality. Models, reasoning and inference. — Cambridge, UK: Cambridge University Press, 2000.

112. Marcot B.G., Penman T.D. Advances in Bayesian network modelling: Integration of modelling technologies // Environmental modelling & software.

— 2019. — Vol. 111. — Pp. 386-393.

113. Горбачёнок Д.И. Исследование методов машинного обучения для создания персонализированных стикеров // ВКР бакалавра. НИУ ВШЭ. — 2023.

114. Strumbelj E., Kononenko I. An efficient explanation of individual classifications using game theory // Journal of Machine Learning Research. — 2010. — Vol. 11. — P. 1.

Список рисунков

3.1 Система для иллюстративного примера................... 41

3.2 Тестируемая система............................... 45

3.3 Схема вычислительного эксперимента. Генератором создаются исходные тестовые данные, затем имитируется процесс секвенирования с помощью 1п8Шсо8ец. Затем с помощью инструментов ВША, Б1ге1ка2 и Зедиеша-иШз производится анализ данных....................................... 47

3.4 Визуализация результатов эксперимента.................. 51

4.1 Распределение величины "ф! - ф(ф2) из СТИ-5 для трёх тестовых случаев. Красные линии показывают приближение........... 64

4.2 Пример результатов проверки СТИ-5. Несмотря на то, что СТИ-5 верно для всех алгоритмов, средняя получаемая награда алгоритма Р-ОБШ-ТЗ не увеличивается в то же число раз, в которое увеличивается награда остальных алгоритмов............... 65

4.3 Нарушение СТИ-4 в ходе предварительного тестирования. Оно помогло обнаружить ошибку в коде эксперимента: распределения наград ручек изменялись только для первого тестируемого алгоритма..................................... 65

4.4 Нарушение СТИ-5 в ходе предварительного тестирования. Оно помогло обнаружить ошибку в коде эксперимента: не применялось линейное преобразование параметров, поэтому графики почти идентичны..................................... 65

5.1 Концептуальная схема МЮеу [107]..........................................68

5.2 Диаграмма классов библиотеки................................................71

5.3 Диаграмма классов, иллюстрирующая связи между классами разработанной библиотеки и классами МЬЭеу..............................72

5.4 Оригинальное изображение и тематический стикер по теме «программирование»............................................................78

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

и сегментацию изображений.......................... 87

6.2 Полный причинно-следственный граф для системы генерации персонализированных стикеров........................ 88

Список таблиц

1 Классификация инвариантов по изменениям исходных данных и параметров.................................... 21

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

3 Параметры эксперимента........................... 47

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

5 Значения метрики (3.5) для разных конфигураций эксперимента. . . 50

6 СТИ для моделей многоруких бандитов.................. 55

7 СТИ для алгоритмов многоруких бандитов................ 56

8 Доля тестовых случаев с верными СТИ в рассматриваемом пространстве значений для алгоритмов многоруких бандитов. Полученные результаты согласуются со свойствами случайного и оптимального алгоритмов: эти алгоритмы не обучаются (СТИ-1, СТИ-2), не реагируют на перестановки ручек (СТИ-4)......... 62

9 Таблица режимов генерации параметров, реализованных в теге Generator..................................... 72

10 Таблица режимов генерации временных рядов, реализованных в

теге Generator .................................. 73

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

Validator ..................................... 75

12 Результаты тестирования СГС......................... 80

13 d-разделяющие множества вершин для вершин причинно-следственного графа........................ 90

14 Оценки влияния компонент тестируемой системы на нарушение тестовых инвариантов R\ и R\,n)....................... 92

15 Оценки влияния компонент тестируемой системы на нарушение

тестового инварианта Я2............................ 93

Приложение А Примеры использования Программного комплекса

А.1 Пример конфигурационного файла

Листинг А.1 — Пример конфигурационного файла эксперимента с

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

pipeline: !MetamorphicPipeline

target_folder: "${env.TARGETFOLDER}" generator: !Generator

name: test - tag-generator 5 relation: shuffle

parameter_name: "probabilities" data_type: "set"

values_range: [ 10, 20, 30, 40 ] parameter_size: 5 10 runs :

- !Bas i cSt age name: basic-run

outputs: ${root.pipeline.target_folder} env :

15 PYTHONPATH: '${env.PYTHONPATH}'

TARGETFOLDER: "${root.pipeline.current_run_target_folder

}"

script:

- !line |

python3 generate_data.py ${root.pipeline . parameters_file} 20 ${root.pipeline.rel ation_data_file} probs

validator:

- !Validator name: validatorl relation: "equivalence"

output: "${root.pipeline.target_folder}/met1.txt" input s: ${root.pipeline.relation_input_paths} data_type: "nominal" dependent: False