An approach for software white box testing with genetic algorithm
A genetic algorithm is proposed to software testing efficiency improve through the most critical paths detecting in software program’s control flaw diagram. The results of algorithm’s probation are done. As exhaustive testing is often impossible even for medium-sized programs, usually only some sepa...
Gespeichert in:
| Datum: | 2018 |
|---|---|
| Hauptverfasser: | , |
| Format: | Artikel |
| Sprache: | Russian |
| Veröffentlicht: |
PROBLEMS IN PROGRAMMING
2018
|
| Schlagworte: | |
| Online Zugang: | https://pp.isofts.kiev.ua/index.php/ojs1/article/view/41 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | Problems in programming |
| Завантажити файл: |  |
Institution
Problems in programming| id |
pp_isofts_kiev_ua-article-41 |
|---|---|
| record_format |
ojs |
| resource_txt_mv |
ppisoftskievua/43/18bd387ad08aa6900b03fff89462ee43.pdf |
| spelling |
pp_isofts_kiev_ua-article-412018-07-25T14:00:23Z An approach for software white box testing with genetic algorithm Подход к структурному тестированию программ с использованием генетического алгоритма Підхід до структурного тестування програм з використанням генетичного алгоритму Slabospickaya, O.A. Moroz, O.G. testing; genetic algorithm генетический алгоритм; тестирование генетичний алгоритм; тестування A genetic algorithm is proposed to software testing efficiency improve through the most critical paths detecting in software program’s control flaw diagram. The results of algorithm’s probation are done. As exhaustive testing is often impossible even for medium-sized programs, usually only some separate paths of the program are checked that aren’t obligatory the most fault-prone. That’s why the more flexible approach for test data generating is developed allowing the most critical paths to be checked first detection. An approach usage may can be instrumental in the rise of efficiency of testing Предложен генетический алгоритм для повышения эффективности тестирования программного обеспечения за счет выявления наиболее критических фрагментов путей в графе потока управления программы. Приведены результаты его апробации. Поскольку исчерпывающее тестирование зачастую невыполнимо уже для программ среднего размера, обычно проверяются только части программы – не обязательно наиболее подверженные ошибкам. Поэтому развит более избирательный подход к генерации тестовых данных, позволяющий выделять наиболее критические пути для их первоочередной проверки. Применение подхода может способствовать повышению эффективности тестирования. Запропонований генетичний алгоритм для підвищення ефективності тестування програмного забезпечення за рахунок виявлення найбільш критичних фрагментів шляхів у графі потоку управління програми. Приведені результати його апробації. Оскільки вичерпне тестування часто нездійсненно вже для програм середнього розміру, зазвичай перевіряються тільки частини програми які не обов'язково найбільш схильні до помилок. Тому розвинений більш вибірковий підхід до генерації тестових даних, що дозволяє виділяти найбільш критичні шляхи для їх першочергової перевірки. Застосування підходу може сприяти підвищенню ефективності тестування. PROBLEMS IN PROGRAMMING ПРОБЛЕМЫ ПРОГРАММИРОВАНИЯ ПРОБЛЕМИ ПРОГРАМУВАННЯ 2018-07-23 Article Article application/pdf https://pp.isofts.kiev.ua/index.php/ojs1/article/view/41 PROBLEMS IN PROGRAMMING; No 1 (2012) ПРОБЛЕМЫ ПРОГРАММИРОВАНИЯ; No 1 (2012) ПРОБЛЕМИ ПРОГРАМУВАННЯ; No 1 (2012) 1727-4907 ru https://pp.isofts.kiev.ua/index.php/ojs1/article/view/41/42 Copyright (c) 2015 ПРОБЛЕМИ ПРОГРАМУВАННЯ |
| institution |
Problems in programming |
| baseUrl_str |
https://pp.isofts.kiev.ua/index.php/ojs1/oai |
| datestamp_date |
2018-07-25T14:00:23Z |
| collection |
OJS |
| language |
Russian |
| topic |
testing genetic algorithm |
| spellingShingle |
testing genetic algorithm Slabospickaya, O.A. Moroz, O.G. An approach for software white box testing with genetic algorithm |
| topic_facet |
testing genetic algorithm генетический алгоритм тестирование генетичний алгоритм тестування |
| format |
Article |
| author |
Slabospickaya, O.A. Moroz, O.G. |
| author_facet |
Slabospickaya, O.A. Moroz, O.G. |
| author_sort |
Slabospickaya, O.A. |
| title |
An approach for software white box testing with genetic algorithm |
| title_short |
An approach for software white box testing with genetic algorithm |
| title_full |
An approach for software white box testing with genetic algorithm |
| title_fullStr |
An approach for software white box testing with genetic algorithm |
| title_full_unstemmed |
An approach for software white box testing with genetic algorithm |
| title_sort |
approach for software white box testing with genetic algorithm |
| title_alt |
Подход к структурному тестированию программ с использованием генетического алгоритма Підхід до структурного тестування програм з використанням генетичного алгоритму |
| description |
A genetic algorithm is proposed to software testing efficiency improve through the most critical paths detecting in software program’s control flaw diagram. The results of algorithm’s probation are done. As exhaustive testing is often impossible even for medium-sized programs, usually only some separate paths of the program are checked that aren’t obligatory the most fault-prone. That’s why the more flexible approach for test data generating is developed allowing the most critical paths to be checked first detection. An approach usage may can be instrumental in the rise of efficiency of testing |
| publisher |
PROBLEMS IN PROGRAMMING |
| publishDate |
2018 |
| url |
https://pp.isofts.kiev.ua/index.php/ojs1/article/view/41 |
| work_keys_str_mv |
AT slabospickayaoa anapproachforsoftwarewhiteboxtestingwithgeneticalgorithm AT morozog anapproachforsoftwarewhiteboxtestingwithgeneticalgorithm AT slabospickayaoa podhodkstrukturnomutestirovaniûprogrammsispolʹzovaniemgenetičeskogoalgoritma AT morozog podhodkstrukturnomutestirovaniûprogrammsispolʹzovaniemgenetičeskogoalgoritma AT slabospickayaoa pídhíddostrukturnogotestuvannâprogramzvikoristannâmgenetičnogoalgoritmu AT morozog pídhíddostrukturnogotestuvannâprogramzvikoristannâmgenetičnogoalgoritmu AT slabospickayaoa approachforsoftwarewhiteboxtestingwithgeneticalgorithm AT morozog approachforsoftwarewhiteboxtestingwithgeneticalgorithm |
| first_indexed |
2025-12-02T16:04:14Z |
| last_indexed |
2025-12-02T16:04:14Z |
| _version_ |
1850413106136612864 |
| fulltext |
Тестування, надійність та якість програм
УДК 681.3.06
О.А. Слабоспицкая, О.Г. Мороз
ПОДХОД К СТРУКТУРНОМУ ТЕСТИРОВАНИЮ ПРОГРАММ
С ИСПОЛЬЗОВАНИЕМ ГЕНЕТИЧЕСКОГО АЛГОРИТМА
Предложен генетический алгоритм для повышения эффективности тестирования программного обес-
печения за счет выявления наиболее критических фрагментов путей в графе потока управления про-
граммы. Приведены результаты его апробации. Поскольку исчерпывающее тестирование зачастую не-
выполнимо уже для программ среднего размера, обычно проверяются только части программы – не
обязательно наиболее подверженные ошибкам. Поэтому развит более избирательный подход к генера-
ции тестовых данных, позволяющий выделять наиболее критические пути для их первоочередной про-
верки. Применение подхода может способствовать повышению эффективности тестирования.
Введение
Сегодня проблема качества являет-
ся главной для мировой индустрии про-
граммного обеспечения (ПО). Существует
даже отдельная дисциплина (программная
инженерия), которая занимается всеми ас-
пектами повышения качества программ-
ных продуктов, начиная с подготовитель-
ных работ и заканчивая их изъятием из об-
ращения. Тестирование – неотъемлемая
составляющая программной инженерии,
один из методов непрерывного улучшения
качества разработанного ПО посредством
выявления его дефектов, не обнаруженных
ранее другими видами проверок [1–4].
Следует подчеркнуть, что тестиро-
вание любой программной системы явля-
ется сложным, длительным и дорогостоя-
щим видом деятельности, требующим око-
ло трети времени и почти половины общей
стоимости разработки ПО [3–5]. Согласно
исследованиям Национального института
стандартов и технологии США [6], «на-
циональные ежегодные затраты из-за не-
адекватной инфраструктуры тестирования
ПО оцениваются в диапазоне от $22.2 до
$59.5 млрд.» – приблизительно 0.6 процен-
та американского валового национального
продукта. Эта сумма не включает расходы
из-за отказов программ в критических сис-
темах, что, к примеру, привелок нецелево-
му запуску ракет «Пэтриот» в системе
обороны США в 1991 г. или к неудачной
посадке спускаемого модуля на Марс в
1999 г., что обошлось потерей $165 млн.
Из вышесказанного следует, что
существенно поднять качество ПО, значи-
тельно сократив сроки и стоимость разра-
ботки, можно, в частности, за счет повы-
шения эффективности его тестирования.
В результате почти полувековых
исследований для решения этой сложной
проблемы предложены и частично автома-
тизированы различные способы генерации
тестовых данных, как-то методы случай-
ной, символической, динамической и т. п.
генерации, объединяемые сегодня в груп-
пы подходов структурного и функцио-
нального тестирования [2–11]. Однако су-
щественного прогресса в этом направле-
нии пока что достичь не удалось, и генера-
ция тестовых данных остается, в значи-
тельной степени, ручной деятельностью.
В последние годы интенсивно ис-
следуются методы искусственного интел-
лекта, и прежде всего алгоритмы поиска
(муравьиные алгоритмы, имитации отжи-
га, генетические алгоритмы и т. п.), – в ка-
честве лучшей альтернативы для разработ-
ки генераторов тестовых данных [7, 8, 12].
В частности, получены обнадеживающие
результаты по использованию для этих ге-
нераторов эволюционных вычислений и
генетических алгоритмов [10–15].
В работе представлены результаты
исследований авторов по применению ге-
нетического алгоритма для повышения
эффективности структурного тестирования
ПО за счет выявления наиболее критиче-
ских фрагментов путей в графе потоков
управления программы.
Статья имеет следующую структу-
ру: в разделе 1 рассмотрена проблема пу-
тевого тестирования в жизненном цикле
ПО; раздел 2 посвящен описанию графа
73
© О.А. Слабопицкая, О.Г. Мороз, 2012
ISSN 1727-4907. Проблеми програмування. 2012. № 1
Тестування, надійність та якість програм
потоков управления; в разделе 3 описыва-
ются основные структуры генетического
алгоритма; в разделе 4 предлагается новый
алгоритм генерирования тестовых данных
и в разделе 5 дается заключение.
1. Проблема путевого тестирова-
ния ПО
С появлением в 1995 году стандарта
ISO/IEC 12207 [5], где все действия по
созданию ПС систематизированы в виде
отдельных процессов жизненного цикла,
тестирование отнесено к основным про-
цессам. Кроме того, отдельные задачи тес-
тирования решаются в других процессах
разработки. В частности, задачи планиро-
вания тестирования распределены по про-
цессам: «Проектирование архитектуры
системы», «Анализ требований к ПО»,
«Проектирование ПО». Автономное и ин-
теграционное тестирование ПО выполня-
ются в процессах «Построение ПО» и
«Интеграция ПО», поскольку неразрывно с
ними связаны. Таким образом, сегодня
тестирование интегрировано с процессами
разработки и рассматривается как непре-
рывная многоуровневая деятельность на
протяжении всего жизненного цикла ПО
независимо от его критичности . Для каж-
дого уровня установлены цели (тестируе-
мые характеристики), типы объектов (вся
система, программные компоненты, моду-
ли) и методы тестирования [1–4].
Цели и объекты тестирования вме-
сте определяют критерии формирования
множества тестов: его полноты – «какой
объем тестов достаточен для достижения
установленной цели?» и состава – «какие
тесты следует выбирать?». Первый вопрос
касается определения критерия покрытия,
а второй – критерия выбора типов тестов.
Методы динамического тестирова-
ния отвечают на оба вопроса с позиций
обеспечения наиболее показательного по-
ведения программы при ее выполнении на
конечном множестве тестовых данных,
Они различаются подходами к проектиро-
ванию тестов – способами специального
выбора тестовых данных из (вообще гово-
ря) бесконечного входного пространства.
Традиционно выделяют две катего-
рии этих методов [1–3]:
– функциональное тестирование,
при котором программа рассматривается
как "черный ящик" и используется только
информация о ее функциях без доступа к
исходному коду;
– структурное тестирование, при
котором используются только структура и
код программы "белого ящика".
Для методов «белого ящика» одним
из наиболее мощных критериев тестового
покрытия является покрытие решений (de-
cision coverage) [2–4]. В соответствии с
ним, набор тестов должен обеспечить хотя
бы однократное выполнение каждой ветви
программы и каждого логического условия
внутри нее.
Выполнение данного критерия тре-
бует постановки и решения проблемы пу-
тевого тестирования – выделения в графе
потоков управления программы множества
путей, содержащих все ее ветви, и форми-
рования тестового набора, обеспечиваю-
щего максимально возможное (а в идеале –
исчерпывающее) прохождение этих путей
при заданных ограничениях на ресурсы
тестирования.
Однако, в общем случае, все пути
протестировать невозможно по несколь-
ким причинам. Во-первых, программа мо-
жет содержать бесконечное количество
путей, например, если в ней есть циклы.
Во-вторых, число путей в программе экс-
поненциально возрастает с ростом количе-
ства ветвей в ней, и многие из этих путей
могут быть невыполнимыми. В-третьих,
количество тестовых ситуаций слишком
велико, так как каждый путь может быть
охвачен несколькими тестовыми ситуа-
циями. Поэтому проблема путевого тести-
рования сложных программ, разрабаты-
ваемых для решения практических задач
автоматизации деловых процессов в раз-
личных предметных областях, может стать
NP-сложной проблемой, для которой по-
крытие всех возможных путей либо невоз-
можно в принципе, либо же требует нереа-
листичных вычислительных ресурсов.
Так как охватить все пути в про-
граммном обеспечении невозможно, про-
блема путевого тестирования сводится к
эффективному выбору приоритетного
74
Тестування, надійність та якість програм
подмножества путей для выполнения и;
тестовых данных, покрывающих эти пути.
Игнорирование проблемы путевого
тестирования либо ее некорректное реше-
ние приводит к фатальным последствиям
при традиционной организации разработки
ПО согласно водопадной модели [1, 6], ко-
гда ошибки в ветвях низкоуровневых мо-
дулей, «пропущенных» при их автономном
тестировании, вызывают трудно диагно-
стируемые отказы ПО во время его прие-
мочных испытаний. Достаточно серьезны-
ми эти последствия могут быть и при ите-
ративных моделях разработки – от спи-
ральной до RAD [1], – если модуль с «про-
пущенной» ветвью реализует базовую
функциональность. Однако особую акту-
альность проблема путевого тестирования
приобретает в связи с быстрым распро-
странением, особенно в современных гиб-
ких методологиях, практики разработки,
управляемой тестами – test driven develop-
ment [1, 6]. Согласно этой практике, внача-
ле создаются модульные тесты, описы-
вающие требования к ПО, а потом – код
модулей, для которых эти тесты должны
выполняться. Таким образом, игнорирова-
ние критических ветвей в тестах создает
предпосылки для появления ошибок при
их реализации в соответствующем коде.
2. Взвешенный граф потока
управления
Граф потока управления – ориенти-
рованный граф, в котором выделены две
вершины, например start и end, и который
удовлетворяет следующим условиям:
– в вершину start не входит ни одна
дуга;
– из вершины end не выходит ни
одна дуга;
– любая вершина достижима из
вершины start;
– из любой вершины достижима
вершина end.
В графе потока управления каждая
вершина соответствует базовому блоку –
прямолинейному участку кода, не содер-
жащему ни операций передачи управле-
ния, ни точек, на которые управление пе-
редается из других частей программы.
Имеется только два исключения: точка, на
которую выполняется переход, является
первой инструкцией в базовом блоке, и
базовый блок завершается инструкцией
перехода. Направленные дуги используют-
ся для представления инструкций перехода
от блока к блоку. Также, в большинстве
реализаций добавлены два специализиро-
ванных блока: входной, через который
управление передается графу (вершина
start) и выходной, завершающий все пути в
данном графе (вершина end) [16].
Пусть N – конечное множеством
вершин, а E – конечное множеством дуг.
Предполагаем, что множество N содержит
вершины start и end. Тогда граф потока
управления является конечным множест-
вом из вершин и дуг, которое обозначим
как G = (N, E). Дуга (i, j) в E соединяет две
вершины ni и nj в N. Блоки и вершины мар-
кированы так, чтобы блок bi соответство-
вал вершине ni. Дуги (i, j), соединяющиеся
базовые блоки bi и bj, подразумевают, что
управление может передаваться от блока bi
к блоку bj.
Путем длины k через граф потока
управления называется последователь-
ность k дуг (e1, e2, …, ek), удовлетворяю-
щая условию: пусть np, nq, nr, и ns являются
вершинами, принадлежащими N, и 0 <i <k.
Тогда если ei = (np, nq) и ei+1 = (nr, ns), то
nq = nr.
Граф потока управления называется
взвешенным, если существует некоторая
функция (правило) f: E → R (функция на
множестве дуг со значениями на множест-
ве вещественных чисел). Сама функция f
называется весовой, а ее значение на той
или иной дуге называется весом этой дуги.
Любой подграф данного графа и любой
путь в данном графе имеют свой вес: это
сумма весов дуг, входящих в этот подграф
или в этот путь.
Очевидно, что в зависимости от
решаемой задачи и преследуемых целей
весовая функция может иметь различный
вид. В данной работе при взвешивании
графа предлагается использовать правило
равенства сумм весов всех дуг, входящих в
произвольную вершину, и всех дуг, исхо-
дящих из нее. Суть этого правила состоит
в следующем: предполагается, что каждая
вершина графа (исключением является
75
Тестування, надійність та якість програм
вершина start) имеет свой входящий вес
(сумма весов всех входящих в нее дуг).
Поскольку вершина start не имеет явных
входящих дуг, то ей присваивается фик-
тивный входящий вес w, который будем
называть опорным весом графа потока
управления. Опорный вес – регулируемый
параметр. Обычно чем больше граф потока
управления имеет вершин и дуг, тем
большим следует брать его опорный вес.
Входящий вес каждой вершины
распределяется среди всех исходящих из
нее дуг. Исключением является вершина
end, не имеющая явных исходящих дуг.
Заметим, что единого правила распределе-
ния входящего веса произвольной верши-
ны j по ее исходящим дугам нет. Однако в
подавляющем большинстве случаев боль-
шие веса целесообразно назначать, так
сказать, критическим дугам, т. е. дугам в
составе путей, более подверженных ошиб-
кам, ведущим к тяжелым последствиям.
Мы будем придерживаться сле-
дующего правила: β процентов входящего
веса вершины выделяется для дуг в после-
довательном пути (эти проценты затем де-
лятся поровну между дугами, составляю-
щими этот путь), а остальные θ = 100 – β
процентов входящего веса резервируются
для циклов и ветвей. Важно подчеркнуть,
что β< 50%. При этом, если некоторая
вершина имеет только одну исходящюю
дугу, то весь ее входящий вес присваива-
ется этой дуге.
Тройка (G, w, β), где G – граф пото-
ка управления, является одним из возмож-
ных представлений взвешенного графа по-
тока управления. При этом пара (w, β) за-
дает правило взвешивания графа.
3. Генетический алгоритм
Генетические алгоритмы (ГА) –
адаптивные алгоритмы общего назначе-
ния, которые используют принципы гене-
тики и эволюционной теории Дарвина для
решения оптимизационных проблем. Осо-
бенно ГА эффективны в случае больших,
сложных и слабо структурированных про-
странствах поиска, где классические мето-
ды и алгоритмы не подходят, неэффектив-
ны, трудоёмки или слишком ресурсозат-
ратны [17]. Поскольку ГА используют
биологические метафоры, то и применяю-
щаяся терминология напоминает биологи-
ческую.
ГА начинает свою работу с созда-
ния, случайным образом, исходного мно-
жества “хромосом”, каждая из которых
представляет собой одно из возможных
решений конкретной проблемы. Хромосо-
мы кодируются как последовательности
конечной длины в некотором конечном
алфавите, удобном для выполнения эво-
люционных операций. Зачастую результа-
том кодирования являются обычные бито-
вые строки. Каждая буква, которая состав-
ляет хромосому, называется геном, а сово-
купность таких хромосом образует “попу-
ляцию”.
Качество хромосом популяции оце-
нивается с помощью целевой функции. По
результатам этой оценки определяется, ка-
кие хромосомы будут участвовать в после-
дующем эволюционном процессе. Затем
создается новое поколение хромосом. При
этом используются генетические опера-
торы, в результате выполнения которых
новые хромосомы получаются путем ком-
бинации свойств родителей.
Базовая структура ГA включает ша-
ги, представленные на рис. 1.
Репродукция – это процесс копиро-
вания хромосом в соответствии с целевой
функцией решаемой задачи. При этом
хромосомы с «лучшим» значением целе-
вой функции имеют большую вероятность
включения в следующую генерацию. Опе-
ратор репродукции является искусствен-
ной версией натуральной селекции “выжи-
вания сильнейшего”. Репродукция опреде-
ляет, как хромосомы будут отобраны,
сколько и каких потомков каждая из них
создаст. С ее помощью из текущей попу-
ляции создается новая, так называемая
брачная популяция, из хромосом которой
будут в последующем образованы брачные
пары для скрещивания.
Оператор кроссинговера – метод
обмена информацией между двумя хромо-
сомами: он определяет процедуру для по-
лучения: потомства от двух родителей.
Кроссинговер моделирует передачу
наследственности хромосомами и сущест-
венно зависит от типа задачи, так как он
76
Тестування, надійність та якість програм
должен создать только допустимых потом-
ков. После его применения будем иметь
две старые хромосомы и всегда получаем
две новые хромосомы.
Рис. 1. Базовая структура генетиче-
ского алгоритма
Сегодня предложено большое число
различных операторов кроссинговера [11,
14, 17]. Наиболее распространенным, не-
смотря на свою простоту, является одно-
точечный кроссинговер. В соответствии с
ним, две хромосомы, выбранные в качест-
ве потенциальных родителей с помощью
процесса репродукции и представленные в
виде строк из “0” и “1”, обмениваются ин-
формацией путем обмена подстроками,
находящимися справа от случайным обра-
зом выбранной точки разрыва.
Важно отметить, что каждая хромо-
сома может образовать брачную пару с не-
которой вероятностью pc, которая называ-
ется вероятностью кроссинговера и явля-
ется регулируемым параметром. Это про-
исходит следующим образом: для каждого
родителя генерируется случайное вещест-
венное число r в диапазоне [0, 1], и если
r < pc, то родитель отбирается для кроссин-
говера.
Оператор мутации изменяет значе-
ния одного или нескольких генов в хромо-
соме с целью повышения структурной из-
менчивости. Этот оператор является ос-
новным инструментом ГА для “выбива-
ния” популяции из локального экстремума
и ее защиты от преждевременной локали-
зации в какой-либо конкретной области из
всего поискового пространства [17]. В от-
личие от кроссинговера, мутация работает
только с одной хромосомой за один раз. В
большинстве случаев, мутация происходит
сразу после кроссинговера, таким образом
она фактически воздействует на потомков,
напоминая естественный процесс.
Осуществляется мутация на поби-
товой основе. Каждый бит в любой хромо-
соме потомства имеет равные шансы му-
тации (изменения ''0'' на ''1'' или ''1'' на ''0''),
которая происходит в соответствии с веро-
ятностью мутации pm. Эта вероятность
также является регулируемым параметром.
Чтобы выполнить мутацию, для каждой
хромосомы в потомстве и для каждого би-
та в хромосоме генерируют случайное ве-
щественное число r в диапазоне [0,1], и
если r < pm, то значение бита меняется на
противоположное.
Если кроссинговер пытается соз-
дать лучшие хромосомы из наиболее при-
годных, то мутация вносит разнообразие в
популяцию, чтобы избежать возможности
“застрять” в локальных оптимумах.
Действие и поведение ГА опреде-
ляют различные параметры, среди которых
наиболее важными являются:
– размер популяции N – этот пара-
метр определяет количество хромосом в
популяции. Если N слишком мал, то ГA
может быстро сходиться, а если он слиш-
ком велик, то ГA может потратить впус-
тую вычислительные ресурсы;
– длина хромосомы L – определя-
ет количество генов в каждой хромосоме.
Это число зависит от выбранного пред-
ставления;
– количество поколений Ng – оп-
ределяет число поколений, для которых
ГА будет работать. Этот параметр часто
используется в критериях завершения ГА;
– вероятность кроссинговера рс –
вероятность обмена информацией между
двумя родителями. Если значение рc слиш-
ком мало, то обмен информацией между
77
Тестування, надійність та якість програм
хромосомами с большим значением целе-
вой функции может не состояться, следо-
вательно уменьшается их способность
произвести лучших потомков. С другой
стороны, кроссинговер может также дать
потомство с более низким значением целе-
вой функции, и поэтому если значение рc
слишком большое, то увеличивается веро-
ятность попасть в локальный оптимум;
– вероятность выполнения мута-
ции рm – вероятность мутации в данной
хромосоме. Обычно рm < рс.
Мутация помогает уберечь популя-
цию от попадания в локальный оптимум,
но с увеличением значения рm замедляется
сходимость алгоритма.
4. Предлагаемый подход
Предлагаемый подход лучше всего
продемонстрировать на конкретном при-
мере. В качестве такого примера рассмот-
рим алгоритм Эвклида нахождения наи-
большего общего делителя двух натураль-
ных чисел, который часто используется
при решении самых разнообразных задач.
Его код и взвешенный граф потока управ-
ления показаны на рис. 2. Значения весов
указаны возле каждой дуги.
Номера вершин соответствуют
строкам кода. Поскольку строка 1 кода –
условный оператор IF, то вершина 1 явля-
ется узлом предиката и две исходящих из
него дуги соответствуют двум возможным
исходам этого оператора. Строка 6 являет-
ся оператором WHILE и, соответственно,
вершина 6 также имеет две исходящие ду-
ги в построенном графе. К тому же, можно
увидеть дугу от вершины 9 к вершине 6,
отображающую петлю (цикл). На этом ри-
сунке показано назначение веса дугам
графа в соответствии с правилом (10, 20),
описанным в разд. 2. Поскольку фрагмент
кода небольшой, то опорный вес w был
взят равным 10 и затем распределен по
различным дугам в зависимости от их
важности. При этом для каждой вершины
20 % ее входящего веса отдается исходя-
щим дугам в последовательном пути. При-
оритетность пути при генерации тестовых
данных основана на факте, что предикат,
петля и вершины ветвления имеют пред-
почтение перед последовательными вер-
шинами во время тестирования программ-
ного обеспечения.
Чтобы применить генетический ал-
горитм для конкретной проблемы, к при-
меру, для генерации тестовых случаев, мы
должны определить следующие его эле-
менты [17]:
– генетическое представление для
потенциальных решений проблемы;
– целевую функцию;
– метод создания начальной попу-
ляции потенциальных решений;
– генетические операторы, которые
изменяют состав потомков;
– значения различных параметров,
используемых генетическим алгоритмом
(размер популяции, вероятности примене-
ния генетических операторов и т. д.).
Наш алгоритм работает с графом
потока управления. Путь, который будет
выполнен программой, однозначно опре-
деляется значениями входных данных, т. е.
парой натуральных чисел (a, b). Эта пара, с
точки зрения ГА, и является хромосомой.
Каждую хромосому кодируем в двоичном
алфавите {0,1}. Так, к примеру, закодиро-
ванная хромосома (15,4) представляет со-
бой битовую строку вида: 11110100.
Качество каждой хромосомы оце-
нивается целевой функцией вида:
,
1
∑
=
=
l
i
iwF
где wi – вес, назначенный i-й дуге соответ-
ствующего хромосоме пути, l – количество
дуг, образующих путь. Например, хромо-
соме (15,4) соответствует путь 0-1-2-3-4-5-
6-7-8-9-6-7-8-9-6-10-11-12 и поэтому зна-
чение целевой функции этой хромосомы
равно 108.
Начальная (Х0) и последующие по-
пуляции (Хi) представляют собой множе-
ства из N случайно сгенерированных дво-
ичных последовательностей, каждая из ко-
торых является закодированной хромосо-
мой. Однако, для удобства изложения ос-
новных идей работы, мы обычно будем
обозначать хромосому в явном виде, т. е.
как множество пар тестовых данных, сге-
нерированных с помощью датчика случай-
ных чисел, т. е.
Xi = {(ai1,bi1), (ai2,bi2),…,(aiN,biN)},
78
Тестування, надійність та якість програм
0
1
2
3
4
5
6
7
8
9
10
11
12
gсd (int a, int b)
{
int r;
if (b>a) {
r = a;
a = b;
b=r;
}
r = a%b;
while(r!=0)
{
a = b;
b=r;
r = a%b;
}
return b;
}
Рис. 2. Код пограммы и еевзвешенный граф потока управления
где N – размер популяции, i = 0,1,… – ее
номер, aik и bik – натуральные числа.
Отбор лучших родителей популя-
ции для участия в последующем воспроиз-
водстве осуществляется с помощью про-
порциональной селекции.
При этом вероятность pj выбора
хромосомы j находится по формуле:
∑
=
=
N
i
ijj FFp
1
/ ,
где N – начальный размер популяции.
Кумулятивная вероятность k-й хро-
мосомы Сk рассчитывается следующим
образом: . ∑
=
=
k
j
jk pC
1
В результате применения одното-
чечного кроссинговера с точкой разрыва
между четвертым и пятым битами входной
битовой строки каждая пара отобранных
из брачной популяции хромосом с вероят-
ностью рс = 0,9 производит две новые хро-
мосомы путем обмена правыми от точки
разрыва частями.
После получения всех хромосом-
потомков, каждая из них подвергается му-
тации. При этом для каждого бита хромо-
сомы генерируется случайное число, и ес-
ли оно меньше рm = 0.3, то значение соот-
ветствующего бита меняется на противо-
положное.
На завершающем этапе каждого
прогона алгоритма из хромосом текущей
популяции, т. е. родителей, и их потомков
одним из известных методов, например
методом вытеснения, формируем новую
популяцию. Если условие завершения ал-
горитма не выполняется, то начинаем сле-
дующий прогон алгоритма уже с новой
популяцией.
Результаты решения задачи пред-
ставлены в табл. 1–7. Обозначения, ис-
пользующиеся в этих таблицах, следую-
шие:
Xi – i-я популяция хромосом;
Fik = F(γik) – значение целевой
функции k-й хромосомы i-й популяции,
где γik обозначает k-ю хромосому i-й попу-
ляции, т. е. тестовые данные (aik, bik);
Рik – вероятность случайного выбо-
ра k-й хромосомы i-й популяции т. е.
,
)(
)(
1
∑
=
= n
k
ik
ik
ik
F
FP
γ
γ
Cik – кумулятивная вероятность k-й
хромосомы i-й популяции;
Rik – сгенерированное случайное
число, необходимое для реализации опера-
79
Тестування, надійність та якість програм
тора репродукции в i-й популяции,
k = 1,…,N;
Nik – номер хромосомы i-й популя-
ции, кумулятивная вероятность которой
превышает Rik;
БП – брачная популяция. В этом
столбце указано, сколько раз каждая хро-
мосома появляется в столбце Nik.
Начальная популяция:
X0 = {(12, 8), (2, 3), (6, 2), (15, 4)}
В табл. 1 – 7 приведены результаты
итераций выполнения алгоритма. Значения
целевой функции текущей популяции при-
ведены в столбце 3. В столбце 5 даны зна-
чения кумулятивной вероятности. Случай-
ные числа, необходимы для реализации
оператора репродукции, приведены в
столбце 6. В столбце 8 показано, какое ко-
личество хромосом разного вида текущей
популяции содержится в брачной популя-
ции.
Результаты итераций описываются
таблицами следующим образом:
Итерация 1: табл. 1 и 2 .
Итерация 2: табл. 3 и 4 .
Итерация 3: табл. 5 и 6 .
Конечный результат: табл. 7.
Результатом применения рассмот-
ренного алгоритма является набор тесто-
вых данных, состоящий из пар (4, 3) и (7,
12). Как видно из табл. 7, он обеспечивает
полное покрытие путей программы.
Таблица 1
N
п/п X0 F0k P0k C0k R0k N0 БП
1 2 3 4 5 6 7 8
1 (12,8) 76 0.228 0.228 0.934 4 0
2 (2,3) 106 0.317 0.545 0.474 2 2
3 (6,.2) 44 0.132 0.677 0.374 2 1
4 (15,4) 108 0.323 1.000 0.618 3 1
Таблица 2
N
п/п N0 БП Кроссин-
говер Мутация
1 4 (15,4)
11110100
(15,4)
11110100
(15,5)
11110101
2 2 (2,3)
00100011
(2,3)
00100011
(3,3)
00110011
3 2 (2,3)
00100011
(2,2)
00100010
(2,2)
00100010
4 3 (6,2)
01100010
(6,3)
01100011
(10,3)
10100011
Таблица 3
N
п/п X1 F1k P1k С1k R1k N1 БП
1 (15,5) 44 0.212 0.212 0.217 2 0
2 (3,3) 44 0.212 0.424 0.999 4 1
3 (2,2) 44 0.212 0.636 0.979 4 1
4 (10,3) 76 0.364 1.000 0.533 3 2
Таблица 4
N
п/п Ns БП Кроссин-
говер Мутация
1 2 (3,3)
00110011
(3,2)
00110010
(5,10)
01011010
2 4 (10,3)
10100011
(10,3)
10100011
(9,10)
10001010
3 4 (10,3)
10100011
(10,3)
10100011
(11,6)
10110110
4 3 (2,2)
00100010
(2,3)
00100011
(2,2)
00100010
Таблица 5
N
п/п X2 F2k P2k C2k R2k N2 БП
1. (5,10) 74 0.223 0.223 0.934 4 0
2. (9,10) 106 0.319 0.542 0.474 2 2
3. (11,6) 108 0.325 0.867 0.374 2 1
4. (2,2) 44 0.133 1.000 0.618 3 1
Таблица 6
N
п/п Ns БП Кроссин-
говер Мутация
1 4 (2,2)
00100010
(2,2)
00100010
(4,3)
01000011
2 2 (9,10)
10011010
(9,10)
10011010
(7,12)
01111100
3 2 (9,10)
10011010
(9,10)
10011010
(13,10)
11011010
4 3 (11,6)
10110110
(11,6)
10110110
(2,6)
00100110
Таблица 7
N
п/п X3 F3k P3k C3k R3k N3 БП
1 (4,3) 76 0.178 0.178 0.098 1 1
2 (7,12) 170 0.399 0.577 0.275 2 3
3 (13,10) 106 0.249 0.826 0.325 2 0
4 (2,6) 74 0.174 1.000 0.487 2 0
Заключение
Генетические алгоритмы часто ис-
пользуются для решения проблем оптими-
зации, в которых развитие популяции яв-
ляется механизмом поиска удовлетвори-
тельного решения при ряде ограничений.
80
Тестування, надійність та якість програм
Зачастую они превосходят по эффективно-
сти исчерпывающий поиск и методы ло-
кального поиска.
В работе предложен генетический
алгоритм для повышения эффективности
путевого тестирования, основанный на вы-
явлении и анализе наиболее критических
путей графа потока управления.
Представлены результаты экспери-
мента, сравнивающего случайную генера-
цию тестовых данных с новым подходом,
использующим генетический поиск.
Применение подхода может способ-
ствовать сокращению трудозатрат на про-
ведение тестирования и его стоимости.
Поскольку эксперименты были проведены
для относительно небольших программ, то
дальнейшее усовершенствование предло-
женного подхода требует его апробации
для программных продуктов различного
размера и назначения.
1. Андон Ф.И., Коваль Г.И., Коротун Т.М.,
Лаврищева Е.М., Суслов В.Ю. Основы ин-
женерии качества программных систем. 2-
e издание. – Киев.: Акадкмпериодика,
2007. – 672 с.
2. Липаев В.В. Тестирование программ. – М.:
Радио и связь, 1986. – 296 с.
3. Beizer B. Software Testing Techniques. 2nd.
Ed. Van Nostrand Reinhold, 1990. – 549 с.
4. Mathur A.P. Foundations of Software Test-
ing: Fundamental Algorithms and Techniques,
1st edition Pearson Education.– 2008. –
С. 689.
5. ISO/IEC 12207: 1995. Information technologies.
Software life cycle processes. – 61 p.
6. Pfleeger S.L. Software Engineering: Theory
and Practice. 2nd Edition, Prentice-Hall,
2001. – 659 p.
7. Mansour N., Salame M. Data Generation for
Path Testing , Software Quality J. – 2004.–
12.– P. 121–136.
8. Wegener J., Baresel A., Sthamer H. Suitabil-
ity of Evolutionary Algorithms for Evolution-
ary Testing // In Proceedings of the 26th
Annual International Computer Software and
Applications Conference, Oxford, England,
August 26– 29, 2002.
9. Berndt D.J., Watkins A. Investigating the Per-
formance of Genetic Algorithm-Based
Software Test Case Generation // In Pro-
ceedings of the Eighth IEEE International
Symposium on High Assurance Systems
Engineering (HASE'04), University of South
Florida, March 25–26, 2004.– p. 261–262.
10. Korel B. Automated software test data
generation. IEEE Transactions on Software
Engineering, 16(8), August 1990.
11. Jones B.F., Sthamer H.H., Eyres D.E. Auto-
matic structural testing using genetic algo-
rithms. Software Engineering J., September,
1996. – p. 299–306.
12. Harman M., Jones B. Search-based Software
engineering // Information and software
technology. – 2001, 43(14). – р. 833–839.
13. Last M., Eyal S., Kandel A. Effective Black-
Box Testing with Genetic Algorithms //
Lecture notes in computer science. – 2006. –
P. 134–148.
14. Alander J., Mantere T., Turunen P. Genetic
Algorithm Based Software Testing. –
http://cite-seer.ist.psu.edu/40769.html.
15. Berndt D.J., Fisher J., Johnson L., Pinglikar
J., Watkins A. Breeding Software Test Cases
with Genetic Algorithms // In Proceedings of
the Thirty-Sixth Hawaii International Confer-
ence on System Sciences (HICSS-36), Ha-
waii, January 2003.
16. Allen F.E. Control flow analysis/ACM SIG-
PLAN Notices – Proceedings of a symposium
on Compiler optimization. –1970. – Vol.5, Is-
sue 7. – p. 1–19.
17. Гладков Л.А., Курейчик В.В., Курейчик В.М.
Генетические алгоритмы. – М.: ФИЗМАТ-
ЛИТ, 2006. – 320 с.
Получено 26.07.2011
Об авторах:
Слабоспицкая Ольга Александровна,
кандидат физико-математических наук,
старший научный сотрудник,
Мороз Ольга Григорьевна,
инженер-программист.
Место работы авторов:
Институт программных систем
НАН Украины,
03187, Киев-187,
проспект Академика Глушкова, 40.
Тел.: (044) 526 4579
e-mail: ols07@mail/ru
81
http://cite-seer.ist.psu.edu/40769.html
|