Интерактивный метод автоматизированного создания тестового набора для формальных моделей программных систем
Предложен интерактивный метод для упрощения отладки и повышения производительности построения тестовых сценариев для обеспечения покрытия требований высокого уровня. Метод реализует полуавтома-тическую генерацию тестов, используя задаваемую пользователем дополнительную информацию об искомых поведени...
Saved in:
| Published in: | Штучний інтелект |
|---|---|
| Date: | 2018 |
| Main Authors: | , |
| Format: | Article |
| Language: | Russian |
| Published: |
Інститут проблем штучного інтелекту МОН України та НАН України
2018
|
| Subjects: | |
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/162373 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Cite this: | Интерактивный метод автоматизированного создания тестового набора для формальных моделей программных систем / А.В. Колчин, С.В. Потиенко // Штучний інтелект. — 2018. — № 2 (80). — С. 51-58. — Бібліогр.: 26 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1859907585000341504 |
|---|---|
| author | Колчин, А.В. Потиенко, С.В. |
| author_facet | Колчин, А.В. Потиенко, С.В. |
| citation_txt | Интерактивный метод автоматизированного создания тестового набора для формальных моделей программных систем / А.В. Колчин, С.В. Потиенко // Штучний інтелект. — 2018. — № 2 (80). — С. 51-58. — Бібліогр.: 26 назв. — рос. |
| collection | DSpace DC |
| container_title | Штучний інтелект |
| description | Предложен интерактивный метод для упрощения отладки и повышения производительности построения тестовых сценариев для обеспечения покрытия требований высокого уровня. Метод реализует полуавтома-тическую генерацию тестов, используя задаваемую пользователем дополнительную информацию об искомых поведениях проектируемой системы. В основу положен эффективный алгоритм сокращения обхода поведения модели, способный оперативно оценивать перспективы достижения непокрытых элементов и приостанавливать рассмотрение ветвей поведения, которые гарантированно не приведут к увеличению покрытия.
Interactive method for simplification and efficiency improvement of test scenario development to satisfy high-level requirements coverage is proposed. The method implements semiautomatic generation of tests on a basis of points-of-interest of desired behavior of a system under development. It is based on efficient algorithm for state space reducing, which makes on-the-fly assessment of the prospects of achieving elements yet uncovered. The algorithm will suspend consideration of the behavior branches that will provably not be able contribute to coverage.
|
| first_indexed | 2025-12-07T16:00:37Z |
| format | Article |
| fulltext |
ISSN 1561-5359. Штучний інтелект, 2018, № 2
© А.В. Колчин, С.В. Потиенко 51
УДК 004.415.53+004.416.2
А.В. Колчин, С.В. Потиенко
Институт кибернетики имени В.М. Глушкова НАН Украины, Украина
пр. Академика Глушкова, 40, г. Киев, 03680
ИНТЕРАКТИВНЫЙ МЕТОД АВТОМАТИЗИРОВАННОГО
СОЗДАНИЯ ТЕСТОВОГО НАБОРА ДЛЯ ФОРМАЛЬНЫХ
МОДЕЛЕЙ ПРОГРАММНЫХ СИСТЕМ
А. Kolchin, S. Potiyenko
V.M. Hlushkov Institute of cybernetics NAS of Ukraine, Ukraine
40, Academician Hlushkov av., Kyiv, Ukraine, 03680 MSP
INTERACTIVE METHOD FOR AUTOMATED TEST SUIT
DEVELOPMENT FOR FORMAL MODELS OF SOFTWARE SYSTEMS
Предложен интерактивный метод для упрощения отладки и повышения производительности построения
тестовых сценариев для обеспечения покрытия требований высокого уровня. Метод реализует полуавтома-
тическую генерацию тестов, используя задаваемую пользователем дополнительную информацию об искомых
поведениях проектируемой системы. В основу положен эффективный алгоритм сокращения обхода поведения
модели, способный оперативно оценивать перспективы достижения непокрытых элементов и приостанавливать
рассмотрение ветвей поведения, которые гарантированно не приведут к увеличению покрытия.
Ключевые слова: тестирование, покрытие, редукция пространства поиска
Interactive method for simplification and efficiency improvement of test scenario development to satisfy high-
level requirements coverage is proposed. The method implements semiautomatic generation of tests on a basis of
points-of-interest of desired behavior of a system under development. It is based on efficient algorithm for state space
reducing, which makes on-the-fly assessment of the prospects of achieving elements yet uncovered. The algorithm will
suspend consideration of the behavior branches that will provably not be able contribute to coverage.
Key words: testing, coverage, state-space search reduction
Введение
Рассмотрим тестирование програм-
мных систем как способ проверки конк-
ретной реализации на соответствие требо-
ваниям. Так как при тестировании невоз-
можно проверить поведение программы во
всех ситуациях, то во время создания
тестов прибегают к определению крите-
риев покрытия и ограничиваются требо-
ванием проверки классов тестовых сцена-
риев, удовлетворяющих таким критериям.
Часто полнота тестового покрытия оцени-
вается по числу выполненных операторов
кода, а также ветвей, путей, достижению
граничных значений функций, выполне-
нию условий в выражениях, и т.п. [1, 2].
Подобные критерии удобно использовать
для автоматической генерации тестов,
которые могут обеспечить структурное
покрытие кода разрабатываемого продук-
та, но не требований к нему. Например, из
того, что тестовый набор покрывает все
условия и операторы кода не следует, что
будет проверена правильность реакции на
входящие сигналы. Трудоемкость создания
тестов по функциональным специфика-
циям вручную (или с применением симу-
ляторов) слишком велика для систем со
сложной моделью поведения, а качество
таких тестов не приемлемо для систем, в
которых надежность критична. Обостря-
ется необходимость автоматизации созда-
ния тестовых сценариев на основе фор-
мальных моделей.
Обычно исходные требования, фор-
мулируемые заказчиком, и их детальные
спецификации, создаваемые разработ-
чиками, заданы на разных уровнях детали-
зации. Для того чтобы автоматизировать
проверку соответствия спецификаций раз-
работчиков требованиям заказчика, необ-
ходимо построить формальные модели
ISSN 1561-5359. Штучний інтелект, 2018, № 2
52 © А.В. Колчин, С.В. Потиенко
спецификаций, согласованные с требова-
ниями заказчика и их интерпретацией раз-
работчиком. Как правило, последние пред-
ставляют собой сценарии типичных режи-
мов поведения (use-cases) разрабатывае-
мой системы. Такие сценарии можно пере-
формулировать в виде последователь-
ностей событий модели, успешное выпол-
нение которых при определенных усло-
виях будет означать покрытие соответст-
вующего требования [3, 4]. Подобные
цепочки событий, соотнесенные с требова-
нием, называют целью теста (test purpose).
Проблемы автоматизации построе-
ния тестовых сценариев
Разработка тестового набора, обеспе-
чивающего покрытие требований к про-
дукту, достаточно сложна и вполне сопос-
тавима с трудоемкостью создания кода.
Для снижения трудоемкости создания тес-
тов активно применяются методы и систе-
мы автоматической генерации тестовых
сценариев на основе формальных моделей
разрабатываемых систем (model based
testing) [2–5]. Большинство из них приме-
няют некоторый структурный критерий
покрытия для поиска соответствующего
поведения модели. Хотя получаемые в
результате тесты обычно слабо связаны со
специфическими особенностями кода тес-
тируемой системы, тем не менее, они
содержат представительный набор сцена-
риев ее поведения, что позволяет значи-
тельно сократить трудозатраты тестиро-
вания сложных систем. Обзоры таких
работ можно найти в [1–5].
Однако можно встретить отчеты
(например, [6, 7]), свидетельствующие о том,
что обеспечение структурного покрытия как
цель для автоматической генерации тестов
может быть ошибочной стратегией: такие
метрики должны использоваться для измере-
ния тщательности покрытия построенными
тестами, и не обязательно приводят к хоро-
шим результатам, когда используются в роли
спецификации для их генерации. Например, в
работе [8], авторы добились покрытия
MC/DC (Modified Condition/Decision, вклю-
чен в сертификацию DO-178B,C безопас-
ности оборудования авиационных систем, а
также является частью требований в стан-
дарте автомобильной безопасности ISO
26262 Road Vehicles Functional Safety) для
модели системы управления полетами и
проверили полученные тесты на реализациях,
в которых были допущены ошибки. Авторы
отмечают, что автоматически сгенерирован-
ные тесты обнаруживали относительно мало
ошибок, и, в общем, продемонстрировали
эффективность ниже, чем у тестов, произве-
денных случайным образом.
Еще один недостаток автоматического
подхода заключается в том, что генери-
руемый тестовый сценарий не обязательно
является хорошим испытанием проверяемого
свойства: сгенерированная тестовая последо-
вательность является артефактом стратегии
поиска, поэтому она может заканчиваться в
середине некоторого интересного поведения,
может включать в себя много избыточности.
Причинно-следственные связи часто запутан-
ны и сложны, и, более того, путь может даже
не содержать состояние, в котором предпо-
сылка требуемого свойства становится ис-
тинной. Автоматические тесты нуждаются в
ручном сопровождении для определения
условий успешного прохождения, а также
для последующего обновления в связи с
изменениями в коде продукта [9]. В работах
[10, 11] подчеркивается, что плохо состав-
ленные тесты имеют негативный эффект на
их сопровождение.
Проблемы соответствия требова-
ниям и отладки
При проектировании тестовых сцена-
риев актуальна задача обеспечения семан-
тического соответствия между тестами и
критериями покрытия исходных функцио-
нальных требований к программному про-
дукту. Системы, основанные на методе
model checking, предполагают, что иско-
мый сценарий можно задать в виде неко-
торой формулы темпоральной логики:
если заданная формула станет ложной на
некотором пути, то такой путь будет выдан
верификационной системой в качестве
контр-примера и может рассматриваться
как один из сценариев покрытия исходного
ISSN 1561-5359. Штучний інтелект, 2018, № 2
© А.В. Колчин, С.В. Потиенко 53
требования. Однако на практике часто
оказывается, что однозначного соответст-
вия между формулой над атрибутами
модели и желаемой цепочкой событий
(обусловленной исходными требованиями)
нет; более того, формулы становятся
громоздкими и сложными для построения.
Существуют подходы, которые помимо
формальной модели на вход принимают
сценарий тестирования, заданный пользо-
вателем в виде последовательности сооб-
щений, которыми обмениваются компо-
ненты модели, например, в виде MSC [4].
Также актуальны проблемы отладки
как самого тестового сценария, так и
анализа результатов выполнения тестов на
реализации системы: для устранения де-
фекта необходимо иметь эффективные
средства его локализации.
Проблемы производительности
Автоматизация тестирования – попу-
лярная тема современных исследований.
Активно разрабатываются различные
эволюционные, стохастические и эвристи-
ческие методы для ускорения достижения
покрытия, а также методы, основанные на
символьных вычислениях [2], так, разви-
тие SMT алгоритмов позволило сущест-
венно повысить производительность так
называемого Bounded Model Checking
подхода [12]. Однако проблема комбина-
торного взрыва остается основным пре-
пятствием на пути интеграции формаль-
ных методов в разработку промышленных
программных систем. Существующие ал-
горитмы часто углубляются в перебор
вариантов, не приводящих к обнаружению
новых элементов искомого покрытия.
Актуальна задача разработки алгоритмов
для эффективного анализа пространства
поведения модели, в частности, проблемой
становятся циклы, приводящие к беско-
нечным путям.
Описание метода
Основные цели предлогаемого метода:
˗ повысить уровень семантического
соответствия между генерируемыми
тестами и требованиями к разрабаты-
ваемой системе;
˗ упростить и усовершенствовать руч-
ное управление, средства отладки,
снабдить информацией о недостаю-
щем покрытии и о путях его
достижения;
˗ повысить производительность алго-
ритмов поиска поведений модели,
удовлетворяющих заданным ограниче-
ниям.
В практике проектирования качест-
венных программных продуктов разработ-
чикам необходимо согласовать с заказ-
чиком семантику требований и формали-
зовать процедуру их тестового покрытия.
Опыт показывает, что наиболее удобной и
понятной для обеих сторон запись такого
согласования выражается в терминах
событий исходной модели. Так, для каж-
дого требования формулировались специ-
альные конструктивные критерии [13],
которые, с одной стороны, подтверждали
семантическое соответствие требованию, с
другой – служили дополнительным входом
для автоматической генерации тестов.
Описываемый метод развивает рабо-
ты [14, 15], в которых был предложен
метод направленного поиска. Требования к
искомому поведению ассоциировались с
некоторым регулярным выражением над
алфавитом, семантически соответствую-
щим событиям модели. К недостаткам
можно отнести высокую сложность созда-
ния таких выражений, ведь они должны
учитывать «дистанцию» между описывае-
мыми событиями (таким образом наклады-
валось ограничение на поиск, ввиду
проблемы комбинаторного взрыва). Также
был затруднен анализ результатов для слу-
чая, когда искомое поведение оказывалось
недостижимым ввиду чрезмерно строгих
ограничений, накладывемых на поиск.
В предлагаемом методе цель теста
(запрос или условия для выбора) также
задается пользователем и определяет
свойство искомого пути в виде множества
точек потока управления, опционально
упорядоченное и ограниченное количест-
вом их посещений, а также расширенное
условиями над переменными модели.
ISSN 1561-5359. Штучний інтелект, 2018, № 2
54 © А.В. Колчин, С.В. Потиенко
Например, условие x>0 на выбранной
точке будет означать «рассматривать
только пути, в которых значения
переменной x в данной точке больше 0»;
чтобы исключить из рассмотрения пути,
проходящие через некоторую точку,
достаточно установить количество ее
прохождений в 0.
Идея упрощения поиска путей состоит
в том, чтобы оперативно предоставить
разработчику тестового набора информацию
о множестве всех допустимых поведений
модели. Наивное решение генерация всех
путей это, очевидно, неосуществимая зада-
ча, и даже если множество конечно, оно
может быть необозримым из-за огромных
размеров. Описанный метод предлагает
компромисс: он исходит из предположения,
что основные интересующие события
представлены различными конструктивными
элементами дизайна модели (т.е. они
находятся в разных точках потока
управления), и поэтому проекция искомого
пути на структуру потока управления (или
блок-схему) будет информативной для
разработчика. Так, в начале работы (до
внесения каких-либо ограничений на поиск)
отображается информация обо всех
достижимых траекториях путем визуа-
лизации их проекции на поток управления.
Далее, пользователь шаг за шагом инте-
рактивно задает дополнительные ограниче-
ния, при этом реакцией служит обновление
информации о допустимых поведениях. В
итоге получается, что пользователь задал
некоторую последовательность событий,
ассоциированную с требованием к реализу-
емой системе, и получил в ответ проекцию
всего множества трасс (последовательности
переходов) модели, каждая из которых,
выходя из начального состояния, пройдет
через все точки в (опционально) указанной
последовательности в соответствии с задан-
ными ограничениями. Это дает пользователю
возможность визуального контроля всех воз-
можных альтернатив поведения одновремен-
но (путем выделения соответствующих эле-
ментов графического потока на панели
визуализации). Таким образом, метод позво-
ляет разработчику найти нужный путь, итера-
тивно шаг за шагом задавая его ключевые
точки, тогда как все возможные альтерна-
тивы промежутков между ними будут
генерироваться автоматически, а проекция
полных допустимых путей обновляться «на
лету». После визуального контроля можно
записать на диск множество трасс, каждая из
которых удовлетворяет требованию и кото-
рые в совокупности обеспечивают покрытие
всех выделенных ветвей потока управления.
Для отладочных целей при записи
трассы сохраняется информация обо всех
причинно-следственных связях в ней, т.е.
места определения значений переменных
для каждого использования в условиях или
правых частях присваиваний. Эти данные
упощают отладку модели и, в последствии,
локализацию дефектов, обнаруженных по
результатам выполенния тестов.
Также накапливается информация о
достигнутом покрытии для подсказки
пользователю и приоритезации поиска
направлений, содержащих больше непо-
крытых элементов.
Описание алгоритма обхода пове-
дения модели
В основу метода положены алгорит-
мы обхода пространства поведения модели
[16, 17], эффективно генерирующие проек-
цию всех выполнимых путей. Путь
(последовательность переходов модели)
удовлетворяет запросу, если он включает
все заданные контрольные точки в соот-
ветствии с условиями.
В качестве примера существующих
подходов рассмотрим алгоритм генерации
тестовых наборов применительно для авто-
матных моделей с семантикой конечных
транзиционных систем. На рис.1 представлен
алгоритм [18], учитывающий частичное
покрытие рассматриваемой трассой элемен-
тов, требуемых заданным критерием
ISSN 1561-5359. Штучний інтелект, 2018, № 2
© А.В. Колчин, С.В. Потиенко 55
Рис. 1. Алгоритм покрытия с учетом частичных элементов [18]
Алгоритм заканчивает работу, когда
множество нерассмотренных состояний
WAIT становится пустым. К этому момен-
ту все достижимые состояния из начально-
го состояния s0 рассмотрены, множество
Cov содержит все достижимые элементы
покрытия и SUITE содержит множество
пар вида (wi, Ci), где wi – трасса, закан-
чивающаяся покрытием элемента Ci, и
i
Ci = Cov. Алгоритм обеспечивает пол-
ное покрытие достижимых элементов, т.к.
для каждого частичного элемента ai расши-
ренное состояние (s, A, C, w) такое, что
aiA, будет рассмотрено.
Хорошо известной проблемой подоб-
ных алгоритмов является время, затрачен-
ное на обход пространства поведения и па-
мять для хранения пройденных состояний.
Для поставленной задачи пространство
поиска, порожденное алгоритмом [18], бу-
дет иметь размер, определяемый произве-
дением количества состояний модели |S|,
количества возможных подмножеств мно-
жества точек покрытия 2|R| и количества
точек потока управления |C|. Очевидная
оптимизация – рассматривать включение
A’Ai вместо равенства A’=Ai [18]. Однако
производительность остается неприемле-
мой, и, как следствие, алгоритм не приго-
ден для предлагаемого подхода.
Ключевая идея усовершенствования поис-
ка в прогнозировании перспектив рассмат-
риваемого состояния заключается в следу-
ющем: текущее состояние поиска будет
рассматриваться как неперспективное (и,
как следствие, текущий путь будет оста-
новлен), если никакое его продолжение не
сможет достичь непокрытый эле-мент. С
другой стороны, если состояние, покры-
вающее искомый элемент достижимо, оно
будет рассмотрено алгоритмом, таким об-
разом сохраняя свойство полноты резуль-
татов поиска. Необходимо отметить, что
такая остановка развертывания состояний
в результате дает большой прирост
эффективности поиска, так как количество
путей, выходящих из состояния, может
экспоненциально возрастать с увеличени-
ем встречающихся условий. Детальное
описание алгоритма поиска приведено в
работе [16].
Рассмотрим пример, демонстрирую-
щий экспоненциальное сокращение анали-
зируемого пространства поведения моде-
ли. Пусть для некоторой абстрактной прог-
раммы (см. рис. 2) множество точек, требу-
емых для посещения трассой,
R={w,a1,…,an}. Асимптотическая оценка
количества различных состояний
O(|S| |C| 2|R|)=O(n2 2n), однако алгоритм
[16] закончит работу за O(n2) шагов:
действительно, пути {init,a1,…,an-2,bn-1,cn-
1}, {init,a1,…,an-3,bn-2,cn-2}, …, {init,b1,c1} не
будут продолжены, так как станет
известно, что элемент ‘w’ не будет
достигнут на их продолжении.
ISSN 1561-5359. Штучний інтелект, 2018, № 2
56 © А.В. Колчин, С.В. Потиенко
statement init;
if(cond0){
statement W;
}else{
if(cond1)
statement a1;
else
statement b1;
statement c1;
…
if(condn)
statement an;
else
statement bn;
statement cn;
}
Рис.2. Пример программы
Аналогичный подход к редукции
пространства поиска предложен в работе
[19] применительно для символьного
выполнения. Его авторы отмечают, что сос-
тояния, отличающиеся только значениями
переменных, которые в последствие (на
развертываниях всех выходящих путей) не
читаются, будут иметь одинаковые после-
дующие выполнения, следовательно, вто-
рое выполнение будет избыточным. Стоит
отметить, однако, что алгоритм [19] не спо-
собен корректно выявлять все читаемые
переменные для случая программ с беско-
нечными циклами, как следствие, авторы
указывают на необходимость их ограни-
ченного развертывания. Для устранения
последнего недостатка в алгоритме [16]
предусмотрена процедура уточнения состо-
яния и его последующего повторного
анализа.
Заключение
Обычно автоматически сгенериро-
ванные тесты позволяют проверить только
неявные требования, например, отсутствие
зависаний, аварийных завершений или
неожиданных исключительных ситуаций
во время выполнения теста [20, 21], но не
обнаружение несоответствия между реали-
зацией системы и ее спецификациями. Для
установления факта успешного прохожде-
ния теста, необходимо описать соответ-
ствующие проверки или формальную мо-
дель [3–5] (так называемая «проблема
оракула» [9]).
Данная работа объединяет оба под-
хода: разработан интерактивный конструк-
тор трасс, который, с одной стороны,
упрощает поиск поведения соответствую-
щего требованию путем задания контроль-
ных точек, с другой – автоматически иссле-
дует альтернативы промежуточных участков
и генерирует результирующий тестовый
набор, удовлетворяющий структурному
покрытию.
Разработан прототип для автоматизи-
рованного построения тестовых сценариев.
Помимо соответствия требованиям высо-
кого уровня, генерируемые тесты удовлет-
воряют критерию покрытия ветвей, а для
участков поведения, требующих более
тщательного тестирования, применен эф-
фективный алгоритм [22] для покрытия
потока данных [23]. Для повышения спо-
собности обнаруживать ошибки применен
метод [24] конкретизации символьных
трасс, осуществляющий вычисление и
подстановку конкретных значений, лежа-
щих на границах допустимого диапазона.
Метод успешно применен [25] к анализу
legacy-кода и генерации тестов [26] для
Java программ.
Литература
1. Myers G.J. (2004). The Art Of Software Testing.
New York. John Wiley & Sons, Inc. – 254 P.
2. Волков В., Колчин А., Летичевский А.,
Потиенко С. (2017). Обзор систематических
методов генерации тестовых данных по
исходному коду программных систем //
Искусственный интеллект, 2, 71–84.
3. Fraser G., Wotawa F., Ammann P. (2009). Testing
with model checkers: a survey // Software Testing,
Verification and Reliability, 19, 215–261.
4. Utting M., Legeard B. (2007). Practical Model-
Based Testing: A Tools Approach. Morgan-
Kaufmann. – 456 P.
5. Petrenko A., Silva S., Maldonado J. (2012). Model-
based testing of software and systems: recent
advances and challenges // Software tools for
technology transfer, 14(4), 383–386.
6. Rushby J. (2008). Automated test generation and
verified software // Verified Software: Theories,
Tools, Experiments, 161–172.
7. Gay G., Staats M., Whalen M., Heimdahl M.
(2015). The risks of coverage-directed test case
generation // IEEE Transactions on Software
Engineering, 41, 803–819.
8. Heimdahl M., Whalen M., Rajan A., Staats M.
(2008). On MC/DC and implementation structure:
ISSN 1561-5359. Штучний інтелект, 2018, № 2
© А.В. Колчин, С.В. Потиенко 57
An empirical study // In Proc. of Digital Avionics
Systems Conf.
9. Barr E., Harman M., McMinn P., Shahbaz M.,
Yoo S. (2015). The oracle problem in software
testing: a survey // IEEE Transactions on Software
Engineering, 41, 507–525.
10. Athanasiou D., Nugroho A., Visser J. and Zaidman
A. (2014). Test code quality and its relation to issue
handling performance // IEEE Transactions on
Softw. Eng, 40(11), 1100–1125.
11. Palomba F., Panichella A., and oth. (2016).
Automatic Test Case Generation: What if Test
Code Quality Matters? // In Proc. of Int. Symp. on
Softw. Testing and Analysis, 130–141.
12. Beyer D., Dangl M. (2016). SMT-based Software
Model Checking: An Experimental Comparison of
Four Algorithms // Verified Software. Theories,
Tools, and Experiments, 181–198.
13. Baranov S., Kotlyarov V., Weigert T. (2012).
Varifiable Coverage Criteria For Automated
Testing. SDL2011: Integrating System and
Software Modeling // LNCS, 7083, 79–89.
14. Колчин А.В., Котляров В.П., Дробинцев П.Д.
(2012). Метод генерации тестовых сценариев в
среде инсерционного моделирования //
Управляющие системы и машины, 6, 43–48.
15. Колчин А.В. (2009). Разработка
инструментальных средств для проверки
формальных моделей асинхронных систем: Дис.
... канд. физ.-мат. наук. – Киев. –140 С.
16. Kolchin A.V. (2018). Interactive method for
cumulative analysis of software formal models
behavior // Proc. of the 11th Int. conf. of programming
UkrPROG'2018, CEUR-WS, 2139, 115–123.
17. Колчин А.В. (2013). Метод редукции
анализируемого пространства поведения при
верификации формальных моделей
распределенных программных систем //
Искусственный интеллект, 4, 113–126.
18. Hessel A., Petterson P. (2007). A global algorithm
for model-based test suite generation // Electr.
Notes Theor. Comput. Sci, 190(2), 47–59.
19. Boonstoppel P., Cadar C. (2008). RWset: Attacking
path explosion in constraint-based test generation.
LNCS, 4963, 351–366.
20. Cseppento L., Micskei Z. (2015). Evaluating
symbolic execution-based test tools // In IEEE Int.
Conf. on Software Testing, Verification and
Validation, 1–10.
21. Fraser G., Arcuri A. (2015). 1600 faults in 100
projects: automatically finding faults while
achieving high coverage with Evosuite // Emperical
software engineering, 20(3), 611–639.
22. Kolchin A. (2018). A novel algorithm for attacking
path explosion in model-based test generation for
data flow coverage // IEEE Int. Conf. on System
Analysis & Intelligent Computing.
23. Su T., Wu K., Miao W., Pu G., and oth. (2017).
A Survey on Data-Flow Testing // ACM Comput.
Survey, 50(1), 35p.
24. Voinov N., Drobintsev P. and oth. (2015). Method
of Symbolic Test Scenarios Automated
Concretization // Proceedings of the Institute for
system programming of the RAS, 27, 115–124.
25. Губа А., Колчин А., Потиенко С. (2016). Метод
извлечения логики поведения из промышленного
программного кода на языке Кобол // Проблемы
программирования, 1–2, 17–25.
26. Колчин А.В., Потиенко С.В. (2016). Метод
генерации тестовых данных по исходному коду
Java программ // Искусственный интеллект, 3,
50–58.
References
1. Myers G.J. (2004). The Art Of Software Testing.
New York. John Wiley & Sons, Inc. –254p.
2. Volkov V., Kolchin A., Letychevskiy A., Potiyenko S.
Obzor sistematicheskih metodov generacii testovyh
dannyh po ishodnomu kodu programmnyh sistem //
Iskusstvennyj intellekt. –2017. –N2. –P. 71–84.
3. Fraser G., Wotawa F., Ammann P. (2009). Testing
with model checkers: a survey // Software Testing,
Verification and Reliability, 19, 215–261.
4. Utting M., Legeard B. (2007). Practical Model-
Based Testing: A Tools Approach. Morgan-
Kaufmann. – 456p.
5. Petrenko A., Silva S., Maldonado J. (2012). Model-
based testing of software and systems: recent
advances and challenges // Software tools for
technology transfer, 14(4), 383–386.
6. Rushby J. (2008). Automated test generation and
verified software // Verified Software: Theories,
Tools, Experiments, 161–172.
7. Gay G., Staats M., Whalen M., Heimdahl M.
(2015). The risks of coverage-directed test case
generation // IEEE Transactions on Software
Engineering, 41, 803–819.
8. Heimdahl M., Whalen M., Rajan A., Staats M.
(2008). On MC/DC and implementation structure:
An empirical study // In Proc. of Digital Avionics
Systems Conf.
9. Barr E., Harman M., McMinn P., Shahbaz M.,
Yoo S. (2015). The oracle problem in software
testing: a survey // IEEE Transactions on Software
Engineering, 41, 507–525.
10. Athanasiou D., Nugroho A., Visser J. and Zaidman
A. (2014). Test code quality and its relation to issue
handling performance // IEEE Transactions on
Softw. Eng, 40(11), 1100–1125.
11. Palomba F., Panichella A., and oth. (2016).
Automatic Test Case Generation: What if Test
Code Quality Matters? // In Proc. of Int. Symp. on
Softw. Testing and Analysis, 130–141.
12. Beyer D., Dangl M. (2016). SMT-based Software
Model Checking: An Experimental Comparison of
Four Algorithms // Verified Software. Theories,
Tools, and Experiments, 181–198.
13. Baranov S., Kotlyarov V., Weigert T. (2012).
Varifiable Coverage Criteria For Automated
Testing. SDL2011: Integrating System and
Software Modeling // LNCS, 7083, 79–89.
14. Kolchin A.V., Kotlyarov V.P., Drobintsev P.D.
(2012). Metod generacii testovyh scenariev v srede
ISSN 1561-5359. Штучний інтелект, 2018, № 2
58 © А.В. Колчин, С.В. Потиенко
insercionnogo modelirovanija // Upravljajushhie
sistemy i mashiny, 6, 43–48.
15. Kolchin A.V. (2009). Razrabotka instrumentalnykh
sredstv dlya proverki formalnykh modeley
asinkhronnykh sistem, Dis. … kand. fiz.-mat. nauk,
Kiev. –140p.
16. Kolchin A.V. (2018). Interactive method for
cumulative analysis of software formal models
behavior // Proc. of the 11th Int. conf. of programming
UkrPROG'2018, CEUR-WS, 2139, 115–123.
17. Kolchin A. (2013). Metod reduktsii analiziruemogo
prostranstva povedeniya pri verifikatsii formalnyih
modeley raspredelennyih programmnyih sistem //
Iskusstvennyiy intellect, 4, 113–126.
18. Hessel A., Petterson P. (2007). A global algorithm
for model-based test suite generation // Electr.
Notes Theor. Comput. Sci, 190(2), 47–59.
19. Boonstoppel P., Cadar C. (2008). RWset: Attacking
path explosion in constraint-based test generation.
LNCS, 4963, 351–366.
20. Cseppento L., Micskei Z. (2015). Evaluating
symbolic execution-based test tools // In IEEE Int.
Conf. on Software Testing, Verification and
Validation, 1–10.
21. Fraser G., Arcuri A. (2015). 1600 faults in 100
projects: automatically finding faults while
achieving high coverage with Evosuite // Emperical
software engineering, 20(3), 611–639.
22. Kolchin A. (2018). A novel algorithm for attacking
path explosion in model-based test generation for
data flow coverage // IEEE Int. Conf. on System
Analysis & Intelligent Computing.
23. Su T., Wu K., Miao W., Pu G., and oth. (2017).
A Survey on Data-Flow Testing // ACM Comput.
Survey, 50(1), 35p.
24. Voinov N., Drobintsev P. and oth. (2015). Method
of Symbolic Test Scenarios Automated
Concretization // Proceedings of the Institute for
system programming of the RAS, 27, 115–124.
25. Guba A., Kolchin A., Potiyenko S. (2016). Metod
izvlechenija logiki povedenija iz promyshlennogo
programmnogo koda na jazyke Cobol // Problemy
programmirovanija, 1–2, 17–25.
26. Kolchin A.V., Potiyenko S.V. (2016). Metod
generacii testovyh dannyh po ishodnomu kodu Java
programm // Iskusstvennyj intellect, 3, 50–58.
RESUME
A. Kolchin, S. Potiyenko
Interactive method for automated test
suit development for formal models of
software systems
Software industry moves toward model-
based development, and automated test
generation from the model is often considered
as a form of requirements-based testing. The
majority of test generation approaches use
some structural coverage criterion based on a
behavioral model of the SUT to guide the
selection of test cases. However, using the
coverage provision as a target for automated
test generation in many cases is a flawed
strategy: coverage metrics are intended to
measure the thoroughness of human-
generated tests, and do not necessarily lead to
good test sets when used in an inverted role as
a specification for the tests required.
This paper proposes a novel interactive
method for simplification and efficiency
improvement of test scenario development to
satisfy high-level requirements coverage. The
method implements semiautomatic generation
of tests on a basis of points-of-interest of
desired behavior of a system under
development. Unlike existing methods of
models behavior analysis, which produce as a
result only one witness or counter-example
path per specified property, the proposed
method provides analysis of behavior in a
cumulative way: it generates aggregate
information about all satisfiable paths. This
distinctive feature plays a role of interactive
path constructor, which prompts all satisfiable
behavior alternatives, so user can find a desired
path by iteratively specifying points-of-interest
and observe updates of the prompting on-the-
fly. The method is based on the original
algorithm that, on the one hand, guarantees
completeness of the search, and on the other it
avoids exhaustive state-space exploration by
applying a specialized decision procedure for
early termination of path unfolding, which
allows exploration of a state only if it might
increase the requested coverage.
Надійшла до редакції 28.09.2018
|
| id | nasplib_isofts_kiev_ua-123456789-162373 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 1561-5359 |
| language | Russian |
| last_indexed | 2025-12-07T16:00:37Z |
| publishDate | 2018 |
| publisher | Інститут проблем штучного інтелекту МОН України та НАН України |
| record_format | dspace |
| spelling | Колчин, А.В. Потиенко, С.В. 2020-01-07T18:28:16Z 2020-01-07T18:28:16Z 2018 Интерактивный метод автоматизированного создания тестового набора для формальных моделей программных систем / А.В. Колчин, С.В. Потиенко // Штучний інтелект. — 2018. — № 2 (80). — С. 51-58. — Бібліогр.: 26 назв. — рос. 1561-5359 https://nasplib.isofts.kiev.ua/handle/123456789/162373 004.415.53+004.416.2 Предложен интерактивный метод для упрощения отладки и повышения производительности построения тестовых сценариев для обеспечения покрытия требований высокого уровня. Метод реализует полуавтома-тическую генерацию тестов, используя задаваемую пользователем дополнительную информацию об искомых поведениях проектируемой системы. В основу положен эффективный алгоритм сокращения обхода поведения модели, способный оперативно оценивать перспективы достижения непокрытых элементов и приостанавливать рассмотрение ветвей поведения, которые гарантированно не приведут к увеличению покрытия. Interactive method for simplification and efficiency improvement of test scenario development to satisfy high-level requirements coverage is proposed. The method implements semiautomatic generation of tests on a basis of points-of-interest of desired behavior of a system under development. It is based on efficient algorithm for state space reducing, which makes on-the-fly assessment of the prospects of achieving elements yet uncovered. The algorithm will suspend consideration of the behavior branches that will provably not be able contribute to coverage. ru Інститут проблем штучного інтелекту МОН України та НАН України Штучний інтелект Програмно-технічні засоби інтелектуальних систем Интерактивный метод автоматизированного создания тестового набора для формальных моделей программных систем Interactive method for automated test suit development for formal models of software systems Article published earlier |
| spellingShingle | Интерактивный метод автоматизированного создания тестового набора для формальных моделей программных систем Колчин, А.В. Потиенко, С.В. Програмно-технічні засоби інтелектуальних систем |
| title | Интерактивный метод автоматизированного создания тестового набора для формальных моделей программных систем |
| title_alt | Interactive method for automated test suit development for formal models of software systems |
| title_full | Интерактивный метод автоматизированного создания тестового набора для формальных моделей программных систем |
| title_fullStr | Интерактивный метод автоматизированного создания тестового набора для формальных моделей программных систем |
| title_full_unstemmed | Интерактивный метод автоматизированного создания тестового набора для формальных моделей программных систем |
| title_short | Интерактивный метод автоматизированного создания тестового набора для формальных моделей программных систем |
| title_sort | интерактивный метод автоматизированного создания тестового набора для формальных моделей программных систем |
| topic | Програмно-технічні засоби інтелектуальних систем |
| topic_facet | Програмно-технічні засоби інтелектуальних систем |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/162373 |
| work_keys_str_mv | AT kolčinav interaktivnyimetodavtomatizirovannogosozdaniâtestovogonaboradlâformalʹnyhmodeleiprogrammnyhsistem AT potienkosv interaktivnyimetodavtomatizirovannogosozdaniâtestovogonaboradlâformalʹnyhmodeleiprogrammnyhsistem AT kolčinav interactivemethodforautomatedtestsuitdevelopmentforformalmodelsofsoftwaresystems AT potienkosv interactivemethodforautomatedtestsuitdevelopmentforformalmodelsofsoftwaresystems |