Файл: Тестирования производительности программ: подходы в зависимости от категорий приложений.pdf

Потенциальным решением (одним тестовым набором) в данном случае является набор значений входных переменных. Например, если все входные переменные являются действительными, то это вектор действительных чисел. В общем случае переменные могут иметь различные типы (например, действительные и булевы), и тестовый набор может представлять более сложную структуру. Но при реализации ГА для представления значений каждой переменной можно использовать бинарное кодирование. Для одной переменной длина входного сигнала определяется доменом и необходимой точностью. Любой домен представляется D, = |д, Ь;], где каждая переменная в программе принимает значения из диапазона [а^, bi]. Каждая область (домен) D, должна быть разбита на (b₁-a₁)-10^d₁ диапазонов равных размеров, если необходима точность до d, десятичных разрядов. Если т, - целое число, обозначающее длину хромосомы или строки, такое, что (Ь - a ) -10^ < 2^m -1, то двоичная строка длины т, обеспечивает требование по точности. Далее для отображения из двоичной строки i в действительное число из диапазона [а^ bi] выполняется стандартной стандартное преобразование [5]. В том случае, когда все входные переменные являются действительными числами, каждая хромо- k

сома (в качестве тестового набора) представляется двоичной строкой длины т_{ = т_{ . При этом i=1

первые mi бит представляют значение из диапазона [ai, bi] переменной х_ь следующая группа т₂ битов отображает значение из диапазона [а₂, Ь₂] переменной х₂ и т. д. Последняя группа m_k бит отображает значение из диапазона [a_k, b_k] переменной х_к. При формировании начальной популяции случайным образом генерируются m-битные строки размера pop_size. Соответствующее значение pop_size определяется экспериментально. Каждая хромосома преобразуется в к десятичных чисел, представ-ляющие значения к входных переменных х_к.. ,,х_к (то есть тестовый набор).

Центральной компонентой ГА является фитнесс-функция, которая позволяет оценивать каждый тестовый набор путем выполнения программы со значениями входных переменных, представляющий этот набор, и записи путей def-use в программе, покрываемых этим набором. Считается, что тестовый набор покрывает путь def-use, если он заставляет программу проходить путь, имеющий подпуть, который начинается в def-узле и заканчивается в узле c-use / p-use (def-use path). Значение фитнесс-функции eval (v;) для каждой хромосомы v; (i = 1,..., pop_size) рассчитывается следующим образом:

---

Тест V! эффективен, если для него значение фитнесс-функции eval (vi) > 0. Таким образом, каждый тест (хромосома) оценивается, выполняется программа для формирования def-use путей, которые покрываются тестами (используемыми в качестве их входных данных). Все тестовые наборы отбираются с эффективными eval (vi) или хорошими значениями фитнесс-функции. Отбор родительских особей производится пропорциональным методом (рулетки) [5] или случайного выбора. Эффективные тестовые наборы (значений входных переменных программы) формируют родительские особи новой популяции. Если ни один тестовый набор не эффективен (не покрывает минимального числа путей), то все особи текущей популяции рассматриваются в качестве родителей. В процессе отбора родителей ГА использует один из двух методов: рулетка или случайный выбор по выбору пользователя.

При построении новых тестовых наборов используются стандартные генетические операторы кроссинговера и мутации. Во время кроссинговера двое родителей (хромосом) случайным образом обмениваются информацией подстрок (генетическим материалом) со случайной позиции, чтобы произвести две новые строки (потомство). Целью является построение лучшей популяции в процессе искусственной эволюции путем объединения генетического материала из пар текущей популяции. Кроссинговер выполняется с некоторой вероятностью р_с . Мутация выполняется по битам путем инвертирования каждого бита с заранее определенной вероятностью мутации р_т, что дает нам ожидаемое количество мутированных битов р_т • т -pop_size. При традиционном подходе ГА популяция развивается, пока одна особь из популяции, которая представляет решение, будет найдена. В нашем случае это соответствует одной группе элементов данных, которая достигает максимального покрытия программы (то есть прохождения всех путей def-use программы). Хотя это возможно для некоторых программы, большинство программ не могут быть охвачены только одной группой данных элементов (то есть одним тестовым набором). Поэтому может потребоваться много групп и несколько запусков программы, чтобы достичь желаемого уровня тестирования. Итак, мы позволяем популяции развиваться до тех пор, пока объединенная подгруппа популяции достигает желаемого уровня покрытия. В результате эволюции для каждого включаемого тестового набора определяем множество путей, покрываемых этим набором, и путем объединения этих множеств для всех построенных тестовых наборов находим множество путей программы, покрываемых тестовой последовательностью. Этот процесс продолжается до тех пор, пока мы не построим последователь наборов, покрывающих все необходимые пути. Решением является эта последовательность тестовых наборов.

---

Предложенный генетический алгоритм принимает в качестве входных данных инструментальную версию программы для тестирования, список путей к def-use, количество входных данных переменных, а также область и точность каждой входной переменной. Кроме того, он принимает параметры ГА: численность популяции, максимальное количество поколений и значения вероятностей кроссинговера и мутации. Алгоритм выдает набор тестовых наборов, набор def-use путей, покрываемых каждым тестовым набором, и список непокрытых путей def-use, если таковые имеются. Алгоритм использует целочисленный вектор, называемый вектором покрытия def-use, для записи покрытых путей. В этом векторе каждый элемент (изначально ноль) соответствует пути def-use. Всякий раз, когда путь def-use покрыт, номер тестового набора, который покрывает этот путь, сохраняется в соответствующем элементе покрытия def-use вектора. Алгоритм отслеживает все сгенерированные тестовые наборы, покрывающие новые пути def-use. Эти тесты хранятся для последующего использования. Методика ГА, представленная в этом разделе, основана на зависимости в потоке данных программы для поиска тестовых данных соответственно критерия универсального использования. Такой подход может быть использован при генерации тестовых данных для программы без циклов и процедур. Проведены эксперименты по оценке эффективности предложенного ГА по сравнению с методом случайного тестирования для сравнения предложенного случайного метода выбора метода рулетки. Результаты этих экспериментов показали, что методика ГА превзошла метод случайного тестирования в 12 из 15 программ, использованных в эксперименте. В 10 из этих программ методики ГА требуется меньшее количество поколений, чем метод случайного тестирования для достижения того же процента покрытия по умолчанию. В двух программах ГА достиг более высокого процента покрытия в меньшем количестве поколений, чем метод случайного тестирования.

Для методов тестирования типа «белого ящика» одним из наиболее мощных критериев тестового покрытия является покрытие решений (decision coverage). Согласно этому критерию набор тестов должен обеспечить хотя бы однократное выполнение каждой ветви программы и каждого логического условия внутри нее. Для этого требуется выделение в графе потоков управления программы множества путей, содержащих все ее ветви, и формирование тестового набора, обеспечивающего максимально возможное (а в идеале - исчерпывающее) прохождение этих путей при заданных ограничениях на ресурсы тестирования. Известно, что в общем случае все пути протестировать невозможно по нескольким причинам. Во-первых, программа может содержать бесконечное количество путей, например, в случае наличия в ней циклов. Во-вторых, число путей в программе экспоненциально увеличивается с ростом количества ветвей в ней, и многие из этих путей могут быть невыполнимыми. В-третьих, количество возможных тестовых наборов слишком велико, так как каждый путь может быть охвачен несколькими тестовыми наборами. Поэтому проблема путевого тестирования реальных достаточно сложных программ является NP сложной проблемой, для которой покрытие всех возможных путей либо невозможно в принципе, либо же требует слишком больших вычислительных ресурсов. Поскольку охватить все пути в программном обеспечении невозможно, проблема путевого тестирования обычно сводится к эффективному выбору приоритетного подмножества путей для выполнения и тестовых данных, покрывающих эти пути. Отметим, что особую актуальность проблема путевого тестирования приобретает в связи с быстрым распространением практики разработки, управляемой тестами - test driven development. При этом вначале создаются модульные тесты, описывающие требования к ПО, а потом - код модулей, для которых эти тесты должны выполняться. Поэтому игнорирование критических ветвей при тестировании создает предпосылки для появления ошибок при их реализации в соответствующем коде.

---

В отличие от предыдущего, в рассматриваемом методе используется взвешенный граф потока управления, для которого существует некоторая функция (правило) f.E R (функция на множестве дуг со значениями на множестве вещественных чисел). Сама функцияf называется весовой, а ее значение на той или иной дуге называется весом этой дуги. Любой подграф данного графа и любой путь в данном графе имеют свой вес: это сумма весов дуг, входящих в этот подграф или в этот путь. В рассматриваемом методе [8, 9] при взвешивании графа предлагается использовать правило равенства сумм весов всех дуг, входящих в произвольную вершину, и всех дуг, исходящих из нее. При этом предполагается, что каждая вершина графа (исключением является вершина start) имеет свой входящий вес (сумма весов всех входящих в нее дуг). Поскольку вершина start не имеет явных входящих дуг, то ей присваивается фиктивный входящий вес w, который будем называть опорным весом графа потока управления. Он является регулируемым параметром. Обычно чем сложнее граф потока управления, тем больше следует брать его опорный вес. Входящий вес каждой вершины распределяется среди всех исходящих из нее дуг. Исключением является вершина end, не имеющая явных исходящих дуг. Заметим, что единого правила распределения входящего веса произвольной вершины у по ее исходящим дугам нет. Однако в подавляющем большинстве случаев большие веса целесообразно назначать так называемым критическим дугам, то есть дугам в составе путей, более подверженных ошибкам, ведущим к тяжелым последствиям. Предложено придерживаться следующего правила: fl процентов входящего веса вершины выделяется для дуг в последовательном пути (эти проценты затем делятся поровну между дугами, составляющими этот путь), а остальные 0 = 100 - fl процентов входящего веса резервируются для циклов и ветвей. Следует подчеркнуть, что fl < 50 % (часто полагают fl = 20 % ). В случае если некоторая вершина имеет только одну исходящую дугу, то весь ее входящий вес присваивается этой дуге. Тройка (G, w, fl), где G - граф потока управления, является одним из возможных представлений взвешенного графа потока управления. В этом случае пара (w, fl) задает правило взвешивания графа.

Путь, выполняемый тестируемой программой, однозначно определяется значениями входных данных. Этот набор и является хромосомой - потенциальным решением. Как и в предыдущем случае, каждая хромосома может быть закодирована в двоичном алфавите {0,1}. Например, закодированная хромосома (15,4) представляет собой битовую строку вида: 11110100. Качество каждой хромосомы оценивается фитнесс-функцией вида: где w, - вес, назначенный i-u дуге соответствующего ;=1 хромосоме пути; l - количество дуг, образующих путь.

---

Начальная популяция Х0 представляет собой множество из N случайно сгенерированных двоичных последовательностей, каждая из которых является закодированной хромосомой. Отбор лучших родителей популяции для участия в последующем воспроизводстве осуществляется с помощью пропорциональной селекции (рулетки). Тогда вероятность р. выбора хромосомы j находится по формуле:

где N - начальный размер популяции. Кумулятивная вероятность k-й хромосомы Е F

C_k вычисляется следующим образом: С_к = р. . При генерации потомков - новых тестовых наборов j=i

используется стандартный 1 -точечный кроссинговер р_с = 0,9, производящий две новые хромосомы путем обмена правыми от точки разрыва частями. После получения всех хромосом потомков каждая из них подвергается также стандартной побитовой мутации с вероятностью р_т = 0,3. На завершающем этапе каждого прогона алгоритма из хромосом текущей популяции, то есть родителей, и их потомков одним из известных методов сокращения популяции [5] формируется новая популяция. Если критерий завершения алгоритма не выполняется, то начинается следующий прогон алгоритма уже с новой популяцией. В целом применение данного подхода способствовует сокращению затрат на проведение тестирования и его стоимости. Но поскольку эксперименты были проведены для относительно небольших программ, дальнейшее усовершенствование предложенного подхода требует его апробации.

При функциональном тестировании по методу «черного ящика» программа рассматривается как функция, которая отображает значения из ее входной области значений в выходном диапазоне значений. Один из способов тестирования программ предполагает ее проверку на соответствие их формальным спецификациям при выполнении программы. К сожалению, на практике сложно убедить разработчиков написать формальные спецификации. Более реальным подходом является использование «искусственных спецификаций», генерируемых компьютером. Другой вариант использования - применение автоматического тестирования. Инструменты, такие как QuickCheck, Evosuite и ТЗ [10-12], способны генерировать тестовые входные данные, но если спецификация не указана, можно проверить только общие условия корректности, такие как отсутствие сбоев.

Использование искусственных спецификаций расширяет диапазон этого подхода. Хотя мы не можем ожидать, что компьютер сможет самостоятельно определять намерение (цель) программы, он может попытаться его угадать. Один из способов сделать это - наблюдение за некоторыми тренировочными запусками, чтобы предсказать общие свойства программы, например, в виде «инвариантов» (свойств состояния) [13], конечного автомата [14], или алгебраические свойства [15]. Эти подходы, однако, не могут охватить полную функциональность программы, к примеру, [13] может выводить только предопределенные семейства предикатов, многие из которых являются простыми предикатами, такими как o! = null and x + у > 0. Нейронные сети предлагают интересную альтернативу этому подходу, так как они могут быть обученными имитировать функцию [16]. Теоретически нейронную сеть можно обучить путем показа образцов выполнения программ, чтобы она действовала как искусственная спецификация для программы. На практике такое обучение осуществить очень тяжело. Программы часто оперируют с дискретными областями, для которых сложно различить шаблоны.

---