, см. упражнение 2.3.4.2-23 в [10], показывает, что такие циклы существуют при всех m, k ? 1. Слово де Бройна получается из цикла разрезанием его в некотором месте и копированием (k-1) символа из начала в конец получившегося слова в обратном порядке, для того, чтобы сохранить подслова длины k.

Обзор [11] дает наиболее полный экскурс в теорию слов де Бройна и историю их использования для решения различных задач. Там они названы циклами нелинейных сдвиговых регистров полной длины (full length nonlinear shift register cycles). Среди задач, связанных с комбинаторикой слов, в которых возникают слова де Бройна можно отметить построение псевдослучайных последовательностей [12], построение кодов [13, 14], кодирование образов [15, 16], построение машин на основе сдвиговых регистров [11, 17, 18], организацию CDMA-сетей. В связи с тестированием программного обеспечения они упоминаются в [19].

Слова де Бройна связаны с графами специального вида, называемыми также графами де Бройна. Граф де Бройна с параметрами m?1 и k?1 B(m, k) — это ориентированный граф с mk-1 вершинами V(m, k) = [0..(m-1)]k-1, являющимися всеми возможными m-словами длины (k-1), и ребрами E(m, k) = [0..(m-1)]k, являющимися всеми возможными m-словами длины k.
При этом ребро x1x2…xk-1xk начинается в вершине x1x2…xk-1 и заканчивается в вершине x2…xk-1xk. Примеры графов де Бройна изображены на рис. 1. Достаточно легко убедиться в выполнении следующего утверждения. Утверждение 1. 1) Граф B(m, 1) имеет ровно одну вершину — пустое слово — и m ребер-петель. 2) Граф B(m, 2) изоморфен полному ориентированному графу с петлями на m вершинах. 3) Количества входящих и выходящих ребер для любой вершины B(m, k) равны m. "v Î V(m, k) in-deg(v) = out-deg(v) = m

Рисунок  1. Графы B(3, 1), B(3, 2), B(2, 3), B(2, 4). Последний пункт непосредственно влечет следующее. Утверждение 2. 1) Для всех m, k ? 1 граф B(m, k) эйлеров, т.е. в нем существует цикл, включающий все ребра 2) Любой эйлеров путь в B(m, k) однозначно соответствует слову де Бройна, а значит такие слова существуют для всех m, k ? 1.
Для построения слова, соответствующего пути в B(m, k), выпишем слово, соответствующее первому ребру пути, затем для каждого следующего ребра пути будем приписывать в конец полученного слова последний символ этого ребра. Определим для ориентированного графа G дуальный граф L(G) как граф, имеющий в качестве вершин множество ребер G, а в качестве ребер — множество пар смежных ребер G, т.е. таких, что конец первой является началом второй. При этом ребро L(G) начинается в вершине, соответствующей первому элементу пары, а кончается в вершине, соответствующей второму. Утверждение 3. 1) Для всех m, k ? 1 дуальный граф к B(m, k) изоморфен B(m, k+1).
Это легко проверить, заметив, что паре смежных ребер B(m, k) соответсвует слово длины (k+1), построенное по правилу из второго пункта предыдущего замечания.
Кроме того, все m-слова длины (k+1) могут быть получены таким способом. 2) Эйлеров путь или цикл на графе G соответствует гамильтонову (проходящему через каждую вершину ровно один раз) пути или циклу на графе L(G) 3) Для всех m, k ? 1 граф B(m, k) имеет гамильтонов цикл Сделанные замечания позволяют определить достаточно эффективный алгоритм построения слов де Бройна — для этого достаточно построить граф B(m, k), что требует объема памяти и времени O(mk), и найти в нем эйлеров цикл, что можно сделать за время, пропорциональное количеству ребер графа, т.е.


опять за O(mk), и используя такой же объем памяти. Длина слова де Бройна равна mk+k-1, т.е. тоже O(mk), следовательно, такой алгоритм оптимален по порядку. Можно улучшить «внутренние» показатели эффективности такого алгоритма, т.е. уменьшить объем памяти, занимаемый внутренними структурами данных и время их обработки, не учитывая внешнюю память и время, используемые для вывода результата. Различные алгоритмы для порождения слов де Бройна довольно часто упоминаются в литературе, в том числе и алгоритмы с лучшими показателями «внутренней» эффективности. Часть из них основана на неожиданной связи между словами де Бройна и словами Линдона (Lyndon words). Слово Линдона длины k в алфавите мощности m — это лексикографически минимальный представитель m-цикла, т.е. класса эквивалентности m-слов по циклическим перестановкам их символов. Оказывается, что верно следующее утверждение. Утверждение 4. [11] Конкатенация лексикографически упорядоченной последовательности всех слов Линдона длин, делящих k, в некотором алфавите дает лексикографически минимальный цикл де Бройна шага k в том же алфавите (для получения из него слова де Бройна достаточно добавить первые k-1 символов из начала в конец). Эффективный (требующий ограниченного константой «внутреннего» времени на построение одного слова Линдона) алгоритм построения слов Линдона и слов де Бройна на их основе представлен в [20]. Другие алгоритмы можно найти в [21–28]. В работе [29] эмпирически сравнивается эффективность по времени алгоритмов из [20], [25] и [27], и последний демонстрирует наиболее высокое быстродействие.

Универсальные покрывающие последовательности

Теперь рассмотрим другой способ интерпретации «как можно более разнообразного» поведения m-слова. Можно считать, что тестируемая система является некоторым небольшим конечным автоматом и строить искомое слово как покрывающее все возможные конечные автоматы с числом состояний, меньшим некоторого k (нужно рассматривать только сильно связные автоматы, в которых все входные стимулы допустимы во всех состояниях, иначе их нельзя покрыть с помощью одного слова, кроме того, остановимся пока на детерминированных автоматах). Нужное k можно выбрать как максимальное, допускающее покрывающее все автоматы слово длины, не большей N.

Таким образом, мы ищем m-слова, покрывающие все детерминированные сильно связные конечные автоматы с не более чем k состояниями и m входными символами, определенными во всех состояниях (автоматы, в которых во всех состояниях допустимы одни и те же m символов называют m-регулярными). Однако «покрывать» можно разные элементы автомата. Достаточно естественно такими элементами считать все состояния, все переходы, пары смежных переходов и пр., и рассматривать разные слова для этих случаев.

Универсальной покрывающей m-последовательностью или универсальным покрывающим m-словом шага k ? 1  и глубины l ? 0 (universal covering word) назовем m-слово, которое, будучи подано на вход любому детерминированному сильно связному m-регулярному автомату с k состояниями, определит в нем маршрут, содержащий все возможные маршруты длины l данного автомата. При l= 0 считаем маршрутами длины 0 все его состояния. Обозначим множество универсальных покрывающих m-слов шага k и глубины l через UC(m, k, l).

Можно усомниться в том, что наша гипотеза о тестируемой системе как автомате с не более чем k состояниями, хорошо согласуется с реальностью — ведь число состояний в большинстве реальных систем таково, что требующиеся последовательности будут иметь колоссальную длину. Однако такая гипотеза приобретает более глубокий смысл, если считать, что состояния системы разбиваются на не более чем k групп так, что переход по любому стимулу осуществляется из одной группы в другую или в ту же (т.е.
отсутствуют такие стимулы, что из некоторой группы состояний переходы по этому стимулу ведут в состояния нескольких разных групп). При этом иногда можно считать, что различия между состояниями в рамках одной группы гораздо меньше, чем между состояниями различных групп, и поэтому прежде всего важно протестировать поведение системы относительно разных групп ее состояний. В имеющейся литературе универсальные покрывающие слова практически не упоминаются, в отличии от слов де Бройна. Некоторое количество работ посвящено аналогу универсальных покрывающих слов глубины 0 (т.е. покрывающих все состояния) для неориентированных графов под именем универсальных обходящих последовательностей (universal traversal sequences, введены Куком, S. A. Cook, в конце 70-х годов прошлого века). Фокусом внимания этих работ является не собственно построение таких последовательностей, а одна из проблем теории сложности алгоритмов — как соотносятся классы сложности P-log-SPACE детерминированных алгоритмов, требующих полиномиально-логарифмической памяти, и NP-log-SPACE недетерминированных алгоритмов с такими же требованиями к памяти. Дело в том, что задача построения пути между двумя произольными вершинами графа является примером NP-log-SPACE задачи, а универсальная обходящая последовательность дает детерминированный алгоритм решения для нее. Тем самым верхние и нижние границы длины универсальных обходящих последовательностей задают правила преобразования сложности NP-log-SPACE алгоритма для решения некоторой задачи в сложность P-log-SPACE алгоритма для нее же. В первой известной автору статье [33], в которой появилось понятие универсальной обходящей последовательности, было показано, что для любых m, k ? 1 существует универсальная обходящая последовательность для m-регулярных неориентированных графов с k вершинами длины O(m2k3log k), а при m = 2 даже O(k3). Для ориентированного случая, который нас интересует, все обстоит несколько сложнее — длина универсальных покрывающих слов как минимум экспоненциальна в зависимости от k.


Для доказательства этого достаточно заметить, что такие слова, как минимум, не короче слов де Бройна (см. Утвержедние 7). Доказать, что универсальные покрывающие слова существуют для всех m, k ? 1 и l ? 0, достаточно просто. Для этого заметим, что m-регулярных автоматов с k состояниями конечное множество — число способов направить m переходов из одного состояния равно km, число возможных способов их компоновки в автомат kkm, а если учесть возможность произвольной перенумерации состояний, отличных от начального, остается kkm/(k-1)! неизоморфных автоматов. «Почти все» из них сильно связны (т.е. доля не являющихся сильно связными автоматов уменьшается с ростом k и m. Если строить универсальное покрывающее слово достаточно прямолинейно — покрывать один за другим пути длины l в одном автомате, затем в другом и т.д., при этом на проход в первую вершину очередного непокрытого пути тратится не более (k-1) шагов — то через максимум (kml)(l + k - 1)(kkm/(k-1)!) шагов все такие пути во всех автоматах будут покрыты — (l + k - 1) шаг делается для того, чтобы покрыть один путь, в каждом состоянии начинается ml путей, в одном автомате k состояний. Обозначим через US(m, k) множество m-слов, содержащих все возможные m-слова длины k в качестве подслов. Слова де Бройна являются наиболее короткими словами в US(m, k). Утверждение 7. 1) Для всех m ? 1 пустое слово лежит в UC(m, 1, 0).
Для всех m ? 1 слово 012...(m-1) лежит в UC(m, 2, 0).
Для всех m, l ? 1 UC(m, 1, l) = US(m, l-1), т.е. в качестве универсального покрывающего слова шага 1 и глубины l можно взять слово де Бройна шага (l-1). 2) Для всех m ? 1, k ? 2 UC(m, k, 0) Í US(m, k-1).
Т.е. слово может быть универсальным покрывающим шага k и глубины 0, только если оно содержит в качестве подслов все возможные слова длины (k-1). Таким образом, длина такого слова не меньше mk-1+k-2. 3) Для всех m, k, l ? 1 UC(m, k+l, 0) Í UC(m, k, l).
Зная универсальные покрывающие слова глубины 0 мы будем знать универсальные покрывающие слова для всех глубин, хотя, быть может, и не самые короткие. 4) Для всех m, k ? 1 UC(m, k+1, 0) = UC(m, k, 1).


Т.е. универсальные покрывающие слова глубины 0 в точности совпадают с универсальными покрывающими словами глубины 1 для на единицу меньшего шага.
Следствие: UC(m, k, 1) Í US(m, k). Для доказательства п. 2 рассмотрим семейство графов с k состояниями, изображенное на Рисунке 2.

Рисунок 2. Семейство "плохих" графов. В каждом графе этого семейства некоторая выделенная последовательность (k-1) символов приводит из начального состояния в (k-1)-е, а все остальные символы во всех состояниях ведут в начальное. Всякая последовательность символов длины (k-1) встречается в качестве выделенной одном из графов семейства. Если в слове из UC(m, k, 0) нет какой-то последовательности длины (k-1) в качестве подслова, то состояние (k-1) соответствующего графа не будет покрыто. Для доказательства п. 3 предположим, что слово из UC(m, k+l, 0), будучи применено к некоторому автомату с k состояниями, не покрывает некоторый путь в нем длины l. Добавим в этот автомат новые l состояний так, чтобы этот путь начинался в том же состоянии, что и раньше, а дальше шел по новым состояниям. Переходы по всем символам из [0..(m-1)], не ведущим вдоль выделенного пути, из новых состояний направим в то состояние, которое было вторым на этом пути в исходном автомате. При этом получится m-регулярный автомат с (k+l) состояниями, по-пержнему сильно связный. Поскольку в исходном автомате наше слово не могло покрыть выделенный путь, а только по этому пути можно попасть в l-е состояние из добавленных, то в результирующем автомате наше слово не может покрывать это состояние, что противоречит его принадлежности UC(m, k+l, 0). Для доказательства утверждения п. 4 (осталось доказать включение UC(m, k, 1) Í  UC(m, k+1, 0)) предположим, что слово из UC(m, k, 1) не покрывает некоторое состояние в некотором автомате с (k+1)-м состоянием. Поскольку автомат сильно связен, в это состояние ведет некоторое множество ребер и из него выводит хотя бы одно ребро. Перенаправим все ребра, ведущие в это состояние, в состояние, в которое входит это самое выводящее ребро.


При этом сильная связность не нарушится, а в автомате останется k состояний. Значит, наше слово покрывает все ребра из числа перенаправленных. Рассмотрим то ребро из этого множества, которое покрывается первым. Поскольку оно первое из перенаправленных, путь, покрываемый до него словом в исходном и результирующем автоматах останется неизменным. Значит, в исходном автомате он должен далее пройти по этому ребру и попасть в непокрытое состояние. Полученная при доказательстве существования универсальных покрывающих слов верхняя оценка их длины слишком велика — на практике наиболее короткие покрывающие слова оказываются не намного длиннее соответствующих слов де Бройна. К сожалению, кроме приведенного выше замечания, автору не много известно о свойствах универсальных покрывающих слов и об алгоритмах их построения. То, что каждое универсальное покрывающее слово глубины 0 содержит все последовательности определенной длины в качестве подслов позволяет предположить, что можно строить такие слова на основе слов де Бройна. Сами по себе слова де Бройна не являются универсальными покрывающими в большинстве случаев (при k ? 3 в п. 2 Замечания 7). Например, минимальная длина элемента UC(2, 3, 0) = UC(2, 2, 1) равна 6 (001011 и 110100), а соответсвующие слова де Бройна имеют длину 5 (и универсальные покрывающие слова в данном случае — даже не продолжения слов де Бройна 00110, 01100, 10011, 11001). Неизвестно, выполнен ли аналог утверждения п. 4 Замечания 7 для глубин, больших 2 при k ? 2 (при k = 1 он точно не выполнен, поскольку UC(m, 1, l) совпадает с US(m, l), а, как только что было сказано, UC(m, 2, 1) уже отличается от US(m, 2)). Если это так, то можно было бы иметь дело либо только с универсальными покрывающими словами глубины 0 для разных шагов, либо только с универсальными покрывающими словами шага 2 для разных глубин (т.е. искать все универсальные покрывающие слова только на автоматах с двумя состояниями). Последнее свойство выглядит очень сильным, и поэтому есть сомнения в том, что оно выполнено. Все (с точностью до перестановок символов) известные автору универсальные покрывающие слова минимальных длин сведены в Таблице 2 (могут существовать универсальные покрывающие слова меньшей длины с заданными параметрами — те слова, про которые точно известно, что они имеют минимальную возможную длину, помечены звездочкой, в конце остальных слов стоит точка, кроме того, знаками вопроса помечены слова предположительно минимальной возможной длины). Таблица 2. Минимальные известные универсальные покрывающие слова.

При тестировании систем, поведение которых

При тестировании систем, поведение которых определяется не только последним обращением к ним, а и предшествующей историей работы, т.е. зависит от внутреннего состояния системы, необходимо строить тесты в виде последовательностей обращений, чтобы покрыть возникающие разнообразные ситуации. Если о системе известно немного, например, только список обращений, которые можно делать, построить ее тест в полном смысле этого слова нельзя, поскольку частью теста всегда является проверка правильности работы системы в ответ на тестовые обращения. Однако можно попробовать построить входные данные теста — определить какие операции с какими параметрами и когда вызывать, предположив, что проверка правильности работы системы производится отдельно. Ее может выполнять специальный модуль автоматической проверки, или же это может делать человек, понимающий, когда очередная реакция системы правильна, а когда — нет. При этом возникает две задачи: построение значений параметров вызовов и построение последовательности вызовов. Непосредственное решение этих задач путем построения всех возможных комбинаций значений параметров и всех возможных последовательностей обращений сразу приводит к комбинаторному взрыву, поэтому требуются методы построения небольшого числа тестов, которые, тем не менее, были бы достаточно качественны, то есть покрывали бы максимально возможное число различных ситуаций, связанных с поведением тестируемой системы. Первая задача при отсутствии дополнительной информации о тестируемой системе обычно решается на основе разбиений возможных значений параметров на конечное число групп и использования различных комбинаций значений из разных групп. Для построения этих комбинаций можно использовать покрывающие массивы (covering arrays) [1–3] дающие минимально возможные множества комбинаций, перебирающие все возможные сочетания пар, троек или другого числа значений отдельных параметров. Другие методы основываются на эвристических алгоритмах, вычисляющих приближения к минимальным покрывающим массивам, — это оправдано, поскольку построение такого массива с нужными параметрами является NP-полной задачей. Обзоры имеющихся результатов по построению покрывающих массивов см. в [1, 2]. Эта статья целиком посвящена возможным подходам к решению второй задачи — построения тестовых последовательностей, поскольку она в имеющейся литературе практически не затрагивается. В статье не излагается ее полное решение с каких бы то ни было позиций, а, скорее, рассматриваются несколько подходов к такому решению, основанных на похожих идеях, и освещаются известные автору результаты, полученные в рамках этих подходов.

Данная статья представляет два возможных

Данная статья представляет два возможных подхода к построению тестовых последовательностей при отсутствии какой-либо информации, кроме числа возможных воздействий на тестируемую систему и длины последовательности, которую хотелось бы получить. Оба подхода приводят к построению слов в конечном алфавите, обладающих специфическими комбинаторными свойствами. Первый подход основывается на предположении, что поведение тестируемой системы определяется фиксированным числом последних оказанных воздействий. Последовательности, построенные на его основе, соответствуют словам де Бройна — самым коротким словам, содержащим в качестве подслов все последовательности определенной длины. Поскольку слова де Бройна имеют помимо тестирования массу других приложений, имеется достаточно много посвященных им работ и различных эффективных алгоритмов их построения. Второй подход предлагает использовать универсальные покрывающие слова, обеспечивающие покрытие путей некоторой длины во всех регулярных сильно связных детерминированных конечных автоматах с фиксированным числом состояний. Несмотря на наглядность предлагаемой идеи, она, по-видимому, до сих пор не рассматривалась, и найти работы, в которых использовалось бы понятие, эквивалентное определенным выше универсальным покрывающим словам, автору не удалось. Такие слова устроены сложнее, чем слова де Бройна, и пока не найдено ни хорошего описания их свойств, ни удобного аппарата для работы с ними, подобного графам де Бройна, ни достаточно эффективных алгоритмов их построения. Все это — задачи для продолжения исследований. Другое возможное направление развития — использование знаний пользователя о системе, которые в реальности чаще всего не нулевые, для построения более эффективных и более коротких тестовых последовательностей. Для начала можно использовать знания о том, что некоторые операции не изменяют состояния системы, некоторые другие, такие, как конструкторы объектов, не зависят от него, впоследствии можно добавить чаще всего известные предусловия операций, и т.д.

Близкие работы

Формальные методы применяются для построения компиляторов и теоретического доказательства корректности их поведения. Проект Verifix[] содержит теоретические разработки схем построения надежных компиляторов, основанных на применении серии промежуточных языков. Кроме того, имеются различные попытки реализации надежных компиляторов с использованием логических исчислений [,,]. Это также чисто теоретические работы. Обычно здесь предлагается простой модельный компилятор, для него строится логическое исчисление и демонстрируется метод доказательства корректности предложенного компилятора.

В работе [], предложены идеи построения спецификации оптимизирующих трансформаций с помощью системы перерисовки графа (Graph Rewrite Systems). Автор утверждает, что данная технология спецификации применима ко многим алгоритмам оптимизации и анализа программ. Такой подход к специфицированию трансформаций, несомненно, является очень интересным и может быть использован для построения оракулов. Однако практическое использование систем перерисовки графов требует большой технической поддержки, создание которой является отдельной сложной задачей.

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

Работа [] описывает основанную на идеях моделирования методологию автоматического построения тестов для парсеров формальных языков. В качестве описания модели в работе используется BNF-грамматика входного языка. В работе [] содержится методика ручного создания тестов для семантического анализатора программ по описанию модели языка.

В работе [] описан подход к автоматизации тестирования семантического анализа и кодогенерации. Спецификации для векторных и многопроцессорных выражений языка mpC были разработаны на языке XASM. Спецификации использовались для фильтрации программ, генерируемых относительно несложным итератором, и для получения эталонных результатов. Кроме того на их основе генерировались критерии тестового покрытия и инструменты его оценки.

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

Литература

А. Ахо, Р. Сети, Д. Ульман. Компиляторы: принципы, технологии, инструменты // Москва-Санкт-Петербург-Киев, 2001

S. Muchnick. Advanced Compiler Design and Implementation. Morgan Kaufmann Publishers, 1997

R. Allen, K. Kennedy. Optimizing Compilers for Modern Architectures. Morgan Kaufmann Publishers, 2002

I.B. Bourdonov, A.S. Kossatchev, V.V. Kuliamin, A.K. Petrenko. UniTesK Test Suite Architecture. Proc. FME'2002 conference, LNCS, 2391. Copenhagen, Denmark (2002) 77-88

A.K. Petrenko, A.I. Vorobiev. Industrial Experience in Using Formal Methods for Software Development in Nortel Networks. Proc. Testing Computer Software (2000) 103-112

Г.В. Ключников, А.К. Косачев, Н.В. Пакулин, А.К. Петренко, В.З. Шнитман. Применение формальных методов для тестирования реализации IPv6 // Труды Института Системного Программирования РАН, 2003 (в печати)

A.K. Petrenko. Specification Based Testing: Towards Practice. LNCS, 2244. (2001) 287-300

С.В. Зеленов, С.А. Зеленова, А.С. Косачев, А.К. Петренко. Генерация тестов для компиляторов и других текстовых процессоров // Программирование, Москва, 2003, том. 29, #2, 59-69

Verifix.

J. Hannan, F. Pfenning. Compiler Verification in LF. Proc. 7th Annual IEEE Symposium on Logic in Computer Science (1992) 407-418

M. Wand, Zh. Wang. Conditional Lambda-Theories and the Verification of Static Properties of Programs. Proc. 5th IEEE Symposium on Logic in Computer Science (1990) 321-332

M. Wand. Compiler Correctness for Parallel Languages. Conference on Functional Programming Languages and Computer Architecture (FPCA) (1995) 120-134

U. Assmann. Graph Rewrite Systems For Program Optimization. ACM Trans. on Programming Languages and Systems (TOPLAS), 22, No. 4 (2000) 583-637

C. Jaramillo, R. Gupta, M.L. Soffa. Comparison Checking: An Approach to Avoid Debugging of Optimized Code. ACM SIGSOFT 7th Symposium on Foundations of Software Engineering and European Software Engineering Conference, LNCS, 1687 (1999) 268-284

G. Necula.
Translation Validation for an Optimizing Compiler. Proc. ACM SIGPLAN Conference on Programming Language Design and Implementation (2000) 83-95 T.S. McNerney. Verifying the Correctness of Compiler Transformations on Basic Blocks using Abstract Interpretation. In Symposium on Partial Evaluation and Semantics-Based Program Manipulation (1991) 106-115 А.В. Демаков, С.А. Зеленова, С.В. Зеленов. Тестирование парсеров текстов на формальных языках // ``Программные системы и инструменты: Тематический сборник факультета ВМиК МГУ'', Москва, 2001, вып. 2, 150-156 А.К. Петренко и др. Тестирование компиляторов на основе формальной модели языка // Препринт института прикладной математики им. М.В Келдыша, #45, 1992 A. Kalinov, A. Kossatchev, M. Posypkin, V. Shishkov. Using ASM Specification for automatic test suite generation for mpC parallel programming language compiler. Proc. Fourth International Workshop on Action Semantic, AS'2002, BRICS note series NS-02-8 (2002) 99-109 A.S. Kossatchev, A.K. Petrenko, S.V. Zelenov, S.A. Zelenova. Application of Model-Based Approach for Automated Testing of Optimizing Compilers. In Proceedings of the International Workshop on Program Understanding (Novosibirsk - Altai Mauntains, Russia), July 14-16, 2003, 81-88
http://www.iis.nsk.su/psi03/workshop/

Области применимости подхода

Предложенный подход применялся для тестирования компиляторов императивных языков программирования. В составе таких компиляторов тестировались модули, касающиеся внутрипроцедурных оптимизаций и/или анализа.

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

Подход к решению задачи проверки сохранения семантики программы во время работы оптимизатора

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

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

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

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

Пример: Инструкции для трассировки в тесте для анализатора Weak-Zero SIV Subscripts. Ниже приведен пример тестового воздействия для анализатора Weak-Zero SIV Subscripts на языке программирования C: 01: void f( int i, int* a, int* b, int* c ) 02: { 03: for( i = -10; i

Строки 03-06 содержат код, построенный по модельной структуре. Строки 07-09 содержат инструкции для трассировки.

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

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

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

Далее в статье мы подробно рассмотрим процессы генерации и запуска тестов.

Построение абстрактной модели

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

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

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

Пример: Weak-Zero SIV Subscripts analyzer. Рассмотрим анализатор, собирающий информацию о некотором виде зависимости данных для последующего использования этой информации в различных оптимизаторах. А именно, рассмотрим Weak-Zero SIV Subscripts analyzer (см., например, []).

Термин subscript используется для обозначения пары выражений, использующихся в паре обращений в теле цикла к одному (возможно, многомерному) массиву и стоящих на одной и той же позиции в ндексах. Subscript называется SIV (single index variable), если на соответствующей индексируемой позиции используется ровно одна индексная переменная. SIV subscript, зависящий от индукционной переменной i, называется слабо-нулевым (weak-zero), если он имеет вид <ai+c1, c2>, где a, c1, c2 - константы и a≠0.

Зависимость между двумя обращениями к массиву существует тогда и только тогда, когда обращение к общему элементу попадает в границы цикла.
Это случается только тогда, когда значение

является целым и L ≤ i0 ≤ U, где L и U соответственно нижняя и верхняя граница цикла. Этот алгоритм использует следующие термины: SIV subscript, определяемый тремя коэффициентами a, c1 и c2; цикл, определяемый своей нижней границей L и верхней границей U. Алгоритм осуществляет поиск следующего шаблона: Таким образом, модель состоит из следующих видов строительных блоков: SIV subscript, содержащий три атрибута, которые соответствуют значениям a, c1 и c2; Цикл, содержащий два атрибута, которые соответствуют значениям L и U, а также множество SIV subscript. Для частного случая оптимизаций, работающих с таким абстрактным представлением, которое близко синтаксической структуре программы, можно использовать способ построения модели, основанный на идее редукции грамматик (см. []). Пример: Control Flow Graph optimizer. Рассмотрим оптимизатор, который осуществляет трансформации для упрощения графа потока управления процедуры. Термин линейный участок (basic block) обозначает последовательность инструкций, которая начинается с метки, может заканчиваться условным или безусловным переходом, и может содержать последовательность не-переходных инструкций. Линейный участок называется пустым, если в нем не содержится не-переходных инструкций. Оптимизатор осуществляет следующие трансформации: если некоторый переход J1 ведет на метку L1 некоторого пустого линейного участка, который завершается безусловным переходом J2 на метку L2, то J1 трансформируется в прямую ссылку на метку L2; если обе ветви условного перехода J ведут на одну и ту же метку L, то J трансформируется в безусловный переход на метку L; если метка L некоторого линейного участка B не используется ни в каком переходе, то B удалается. Алгоритм этой оптимизации использует такие термины: линейный участок, условный переход, безусловный переход. Алгоритм осуществляет поиск следующих шаблонов: переход J1 ведет на метку L1 некоторого пустого линейного участка, который завершается безусловным переходом J2 на метку L2; обе ветви условного перехода J ведут на одну и ту же метку L; метка L не используется ни в каком переходе; Этот алгоритм использует граф потока управления в качестве абстрактного представления обрабатываемой программы.


Такое представление тесно связано с синтаксической структурой программы. Редукция грамматики языка позволяет получить модель, которая состоит из следующих видов строительных блоков: Процедура, содержащая последовательность линейных участков; Линейный участок, содержащий метку, переход, а также атрибут ``пустой''; Метка, содержащая атрибут ``не используется''; Безусловный переход, содержащий ссылку на метку; Условный переход, содержащий ссылки на метки. Будем называть модельной структурой граф, вершины которого - строительные блоки, а ребра - связи между строительными блоками. Проекция предложений исходного языка в модельные структуры индуцирует разбиение множества предложений исходного языка на классы эквивалентности. Один класс эквивалентности состоит из предложений, которые имеют одинаковое модельное представление, т.е. которые неразличимы для алгоритма оптимизации. Это свойство позволяет нам выдвинуть гипотезу, согласно которой на эквивалентных предложениях оптимизатор работает одинаково. Следовательно, в желаемом тестовом наборе достаточно иметь не более одного представителя из каждого класса эквивалентности. Поскольку множество модельных структур, т.е. множество классов эквивалентности, в общем случае бесконечно, то для создания тестового набора мы должны выбрать некоторое его конечное подмножество. Основанием для этого выбора должны служить те шаблоны, которые были выделены при анализе алгоритма оптимизации. Таким образом, критерий тестового покрытия формулируется в терминах абстрактной модели. Пример: Критерий тестового покрытия для анализатора Weak-Zero SIV Subscripts. Напомним, что анализатор Weak-Zero SIV Subscripts осуществляет поиск следующего шаблона: L ≤ i0 ≤ U и i0 целое, где i0 определяется из соотношения

(1)

Сформулируем соответствующий критерий тестового покрытия в терминах модели, т.е. в терминах L, U, a, c1 и c2. Фиксируем L, U и c1 - целые числа. Пусть a принимает значения 1 и 2. Мы хотим, чтобы i0 принимало целые значения из некоторого множества, а также какие-нибудь нецелые значения.Пусть в упомянутое множество входят целые числа, удовлетворяющие одному из следующих требований: i0<L, например, i0=L-1; i0=L; i0 расположено близко к L внутри интервала, задаваемого границами цикла, например, i0=L+1; i0 расположено в середине интервала, задаваемого границами цикла, например, i0=; i0 расположено близко к U внутри интервала, задаваемого границами цикла, например, i0=U-1; i0=U; i0>U, например, i0=U+1. Для нахождения значения c2 достаточно решить уравнение (1) относительно значений a и i0.

Практическое применение подхода

С помощью предложенного подхода были построены тесты и протестированы ряд оптимизаторов в нескольких компиляторах для современных архитектур: GCC, Open64, Intel C/Fortran compiler.

Были разработаны генераторы для следующих оптимизаторов: Control Flow Graph optimization; Common Subexpression Elimination; Induction Variable optimization; Loop Fusion optimization; Loop Data Dependence analysis.

Соответствующие множества тестов генерировались для языков программирования C и Fortran.

Применение модельного подхода для автоматического тестирования оптимизирующих компиляторов

, , ,

В статье предлагается концепция автоматизированного построения тестовых наборов и тестовых оракулов для тестирования оптимизаторов. Используется подход, основанный на генерации тестов из моделей. Основные идеи модельного подхода заключаются в следующем: 1) модельный язык неявно разбивает множество программ целевого языка на классы эквивалентности; 2) критерий тестового покрытия формулируется в терминах модельного языка; 3) в соответствии с выбранным критерием генерируется набор тестов. В работе описывается схема построения тестового оракула, который проверяет сохранение семантики программы после ее оптимизации.

Создание генератора тестов

Будем называть тестовым воздействием единичные входные данные для тестируемого оптимизатора, т.е. программу на целевом языке. Термин ко-тестовое воздействие обозначает единичные входные данные для результата компиляции тестового воздействия, т.е. значения параметров для запуска соответствующей откомпилированной программы. Итератор ко-тестовых воздействий - это компонент, обеспечивающий перебор необходимых ко-тестовых воздействий и запуск откомпилированного тестового воздействия. Таким образом, один тест включает в себя тестовое воздействие и итератор ко-тестовых воздействий.

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

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

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

Итератор должен создавать множество модельных структур в соответствии с выбранным критерием тестового покрытия.

Для данной модельной структуры S меппер должен строить соответствующий тест со следующими свойствами: тестовое воздействие, построенное по модельной структуре S, имеет модельное представление, совпадающее с S; построенный тест (т.е. тестовое воздействие и итератор ко-тестовых воздействий) является синтаксически и семантически корректным с точки зрения целевого языка; тестовое воздействие содержит вычисления в тех местах, которые должны подвергаться оптимизации; тестовое воздействие содержит инструкции для трассирования окончательных результатов вычислений; итератор ко-тестовых воздействий содержит инструкции для формирования всех необходимых параметров, а также инструкции для активации откомпилированного тестового воздействия (т.е. вызов соответствующей процедуры или нескольких процедур).

Если модель предполагает начилие некоторых вычислений, то для формирования трассы меппер вставляет в текст тестового воздействия печать окончательных значений всех переменных, вовлеченных в вычисления. В противном случае меппер дополнительно вставляет в текст тестового воздействия некоторые вычисления, а для формирования трассы вставляет печать окончательных результатов этих вычислений.

По окончании разработки итератора и меппера они собираются в генератор. После этого происходит генерация искомого множества тестов.

это основной инструмент при создании

Компиляторы[,,] - это основной инструмент при создании программного обеспечения, поэтому их надежность особенно важна. Наряду с другими методами верификации и валидации для компиляторов, тестирование попрежнему остается важным элементом в семье этих методов. Необходимость автоматизации тестирования компиляторов также представляется очевидной, поскольку реальные объемы добротных наборов тестов и сложность анализа результатов весьма велики. Подход UniTesK [] является методологий построения надежного и качественного ПО на основе использования моделей этого ПО. UniTesK использует модельный подход в следующих целях: для построения критериев правильности реализации ПО, для построения критериев полноты и эффективности проверки качества ПО, для построения входных тестовых данных и процедур анализа результатов целевого ПО. В узком смысле UniTesK предлагает рассматривать модели как инструмент для построения тестов целевого ПО. При этом процесс разработки теста и собственно тестирования распадается на следующие фазы: Построение абстрактной модели или спецификации поведения целевой системы. Извлечение тестового оракула (т.е. процедуры анализа результата целевой системы) из спецификации. Разбиение пространства входных данных целевой системы на домены, Проектирование критерия тестового покрытия в терминах абстрактной модели. Интеграция сгенерированных и вручную написанных компонентов тестовой системы. Пропуск тестов, включающий анализ результатов целевой системы при помощи оракулов; измерение тестового покрытия в терминах модели/спецификации или в терминах реализации. Основные достоинства этого подхода состоят в следующем: Спецификации и модели обычно строятся на основе функциональных требований к системе, и часто структура спецификаций следует структуре требований, что позволяет явным образом связать требования к системе с результатами тестирования и метриками тестового покрытия. Спецификации и модели, а значит и тесты, могут разрабатываться до завершения реализации целевой системы, что сокращает общее время разработки ПО. Спецификации и модели обычно компактнее и проще реализации, что упрощает ре-юз и сопровождение как самих моделей, так и тестов, которые строятся на их основе. Достижение исчерпывающего покрытия в соответствии с критериями, определенными на спецификациях и моделях, как правило, обеспечивает уровень покрытия реализации, сравнимый с уровнем, достигаемым при традиционном тестировании, но за счет существенно меньших трудозатрат. Подход UniTesK прошел апробацию в проектах, свзяаннных с тестированием как действующего, так и вновь создаваемого ПО [,,].
Целевое ПО в этих проектах принадлежало к различным классам систем, предоставляющих процедурный интерфейс: ядра операционных систем, телекоммуникационные протоколы, серверы, run-time поддержка компиляторов и отладчиков. Следуя общей схеме процесса UniTesK, описанной выше, удалось полностью автоматизировать работы фаз 2, 3, 5, 6. Фаза 1 выполняется вручную, фаза 4 - полуавтоматически. Перенос опыта и инструментов UniTesK на тестирование компиляторов вскрыл ряд проблем. В этой статье мы опишем применение этого подхода к тестированию оптимизирующих модулей в компиляторах. Главная проблема здесь заключается в том, что нет эффективного способа создавать для оптимизатора такие спецификации, из которых можно было бы извлекать эффективные оракулы. Поэтому в предлагаемом подходе мы используем лишь следующие фазы процесса UniTesK: Построение абстрактной модели входных данных целевой системы. Проектирование критерия тестового покрытия в терминах абстрактной модели. Интеграция сгенерированных и вручную написанных компонентов тестовой системы. Пропуск тестов, включающий анализ результатов целевой системы при помощи оракулов; измерение тестового покрытия в терминах модели/спецификации или в терминах реализации. В рамках предлагаемого подхода оракул проверяет только сохранение семантики программы во время оптимизации. Для этого в качестве тестовых воздействий на оптимизатор берутся такие программы, семантика которых полностью представляется их трассой. Такое свойство тестов позволяет свести задачу проверки сохранения семантики к сравнению трассы с некоторой эталонной трассой. Итак, суть подхода такова: Построить для тестируемого оптимизатора представительное множество тестовых воздействий следующим образом: построить абстрактную модель входных данных оптимизатора; в терминах абстрактной модели сформулировать критерий покрытия этих входных данных; перебрать соответствующие тестовые воздействия; Протестировать оптимизатор следующим образом: пропустить тесты через компилятор при активированном тестируемом оптимизаторе; вынести вердикт относительно сохранения семантики тестов после оптимизации. В следующих разделах статьи описываются детали процесса тестирования оптимизаторов в соответствии с предлагаемым подходом.В конце приводятся экспериментальные данные по применению методологии, обсуждаются область применимости и ограничения этого подхода и приводится обзор близких работ. Предварительный вариант настоящей статьи был доложен на международном семинаре ``Понимание программ''[].

Для автоматического получения представительных множеств

Для автоматического получения представительных множеств тестов строились генераторы на основе абстрактного описания алгоритма оптимизации. При построении генераторов использовались инструменты и библиотеки, которые существенно облегчали процесс разработки моделей и компонентов генератора. Некоторые этапы создания генератора при этом были полностью автоматизированы. Преимущества использования модельного подхода состоят в следующем: гораздо меньшая трудоемкость по сравнению с написанием тестов вручную; систематичность тестирования; легкая сопровождаемость получаемых множеств тестов; возможность переиспользования отдельных компонентов генератора. Перечисленные преимущества подтверждаются результатами ряда проектов по тестированию коммерческих компиляторов.

Запуск тестов

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

Итак, процесс запуска тестов и анализа результатов состоит из следующих шагов: Тестирование оптимизатора: компиляция тестов с включенной целевой оптимизацией. Ко-тестирование: запуск результатов компиляции на выполнение; сохранение получившейся трассы (тестовая трасса). Получеие эталона: компиляция теста с отключенной целевой оптимизацией; запуск результатов компиляции; сохранение получившейся трассы (эталонная трасса). Запуск оракула: cравнение тестовой трассы с эталоном; вынесение вердикта о сохранении семантики теста во время оптимизации.

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

Аннотация

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

Целенаправленный поиск

Учитывая структуру критерия , из задачи 1 можно выделить следующую подзадачу:

Задача 2. Для заданной тестовой системы S и заданного элемента тестового покрытия q, построить тест

, удовлетворяющий условию .

Для решения исходной задачи 1, достаточно решить задачу 2 для

попарно различных элементов тестового покрытия , то есть построить тесты такие, что

Решением задачи 1 будет множество

.

Рассмотрим генетический алгоритм решения задачи 2. В качестве множества кандидатов возьмём множество тестов T. Условие останова: в текущей популяции присутствует тест q такой, что

. Оценочная функция каждому тесту t ставит в соответствие числовую меру того, насколько тест t близок к тому, чтобы покрыть элемент тестового покрытия q. При этом оценочная функция достигает своего максимального значения на тех и только на тех тестах, которые удовлетворяют условию . Иными словами:

(5)

В частности, в качестве оценочной функции можно использовать следующую функцию, удовлетворяющую условию (5):

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

Генетические алгоритмы

Генетические алгоритмы - это метод решения задач оптимизации. В методе используются идеи, почерпнутые из эволюционной биологии: наследование признаков, мутация, естественный отбор и кроссовер []. Определяется множество кандидатов, среди которых ищется решение задачи. Кандидаты представляются в виде списков, деревьев или иных структур данных.

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

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

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

Генетический алгоритм генерации тестов

Рассмотрим следующую задачу генерации тестов:

Задача 1. Для заданной тестовой системы S построить тестовый набор

, удовлетворяющий критерию .

Для построения генетического алгоритма решения этой задачи необходимо определить: множество кандидатов; структуру представления кандидатов; оценочную функцию; оператор кроссовера; оператор мутации; условие останова.

Критерии полноты тестового покрытия

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

Пусть P - множество программных систем, T - множество тестов, а Σ - множество тестовых наборов, то есть множество всех конечных подмножеств множества T . Тогда задача генерации тестов может быть сформулирована следующим образом: для заданной тестируемой системы S

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

Многие критерии полноты тестового покрытия, имеющие практическое применение, строятся по следующей схеме: для тестируемой системы S критерий F определяет множество элементов тестового покрытия

. Элементом тестового покрытия можно считать некоторый класс событий, которые могут произойти в ходе работы тестируемой программной системы. По появлению в процессе исполнения программы элементов тестового покрытия и различных их комбинаций можно судить о полноте или качестве проверки, которую выполняет данный тестовый набор. Например, элементами тестового покрытия могут быть исполняемые строки исходного кода (соответствующие событиям их исполнения); рёбра графа потока управления; пути в графе потока управления; логические выражения, встречающиеся в исходном коде и т.п. Кроме того, критерий F определяет логическую функцию , которая принимает значение , если элемент тестового покрытия q покрывается тестом t. Тестовый набор для системы S удовлетворяет критерию полноты тестового покрытия F, если каждый элемент тестового покрытия из множества покрывается хотя бы одним тестом из тестового набора . Иными словами:

(1)

Приведём несколько примеров часто упоминаемых критериев полноты тестового покрытия: каждый оператор в исходном коде выполняется хотя бы один раз; каждая ветвь графа потока управления выполняется хотя бы один раз; каждый путь графа потока управления исполнение выполняется хотя бы один раз; каждое логическое выражение хотя бы один раз вычисляется со значением «истина» и хотя бы один раз - со значением «ложь»; тестовый набор убивает всех мутантов из заданного набора.

Заметим, что все критерии, приведённые в качестве примеров, соответствуют ранее изложенной схеме.

Литература

[1]	Г. Мейерс. Искусство тестирования. М.: Финансы и статистика, 1982.
[2]	André Baresel, Harmen Sthamer, and Michael Schmidt. Fitness function design to improve evolutionary structural testing. In GECCO, pages 1329-1336, 2002.
[3]	Chandrasekhar Boyapati, Sarfraz Khurshid, and Darko Marinov. Korat: Automated testing based on Java predicates. In Proceedings of the International Symposium on Software Testing and Analysis (ISSTA 2002) , Rome, Italy, 22-24 July 2002. IEEE.
[4]	Ugo A. Buy, Alessandro Orso, and Mauro Pezzè. Automated testing of classes. In ISSTA, pages 39-48, 2000.
[5]	Yoonsik Cheon and Myoung Kim. A fitness function for modular evolutionary testing of object-oriented programs. Technical Report 05-35, Department of Computer Science, University of Texas El Paso, Nov 2005.
[6]	Yoonsik Cheon, Myoung Kim, and Ashaveena Perumendla. A complete automation of unit testing for Java programs. In Hamid R. Arabnia and Hassan Reza, editors, Proceedings of the 2005 International Conference on Software Engineering Research and Practice (SERP '05), Volume I, Las Vegas, Nevada, June 27-29, 2005, pages 290-295. CSREA Press, 2005.
[7]	John H. Holland. Adaptation in natural and artificial systems. MIT Press, Cambridge, MA, USA, 1992.
[8]	Paolo Tonella. Evolutionary testing of classes. In ISSTA '04: Proceedings of the 2004 ACM SIGSOFT international symposium on Software testing and analysis, pages 119-128, New York, NY, USA, 2004. ACM Press.
[9]	Hong Zhu, Patrick A. V. Hall, and John H. R. May. Software unit test coverage and adequacy. ACM Comput. Surv. , 29(4):366-427, 1997.

1(к тексту)

Работа поддержана грантом РФФИ (05-01-999).

Метрики тестового покрытия

Со многими критериями полноты тестового покрытия можно связать соответствующую метрику тестового покрытия. Метрика тестового покрытия - это функция вида

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

В частности, для критерия полноты тестового покрытия F, представимого в виде , можно ввести следующую метрику:

(2)

Сам критерий при этом примет вид:

(3)

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

(4)

Параметр

указывает, какая доля элементов тестового покрытия должна быть покрыта тестовым набором. Приведём несколько примеров часто упоминаемых метрик тестового покрытия: количество покрытых (выполненных хотя бы один раз) операторов в исходном коде; количество покрытых ветвей графа потока управления; количество покрытых путей графа потока управления; количество распознанных мутантов (версий тестируемой системы с искусственно привнесёнными ошибками).

Все эти метрики могут быть представлены в виде . Подробное описание этих и других, используемых на практике, метрик полноты тестового покрытия можно найти в [].

Оценочные функции

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

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

Тестовый набор удовлетворяет критерию покрытия операторов исходного кода, если при выполнении этого тестового набора каждый оператор исходного текста программы выполняется хотя бы один раз. Элементами тестового покрытия в данном случае являются операторы исходного текста. Для заданного оператора q значение оценочной функции

тем больше, чем ближе тест t к тесту, покрывающему оператор q. Для построения оценочной функции рассмотрим граф потока управления тестируемой системы S. Вершинами графа являются операторы исходного кода, то есть множество . В графе существует ребро, идущее из вершины q1 в вершину q2 тогда и только тогда, когда оператор q2 может быть выполнен непосредственно после оператора q1. Пусть - это множество всех элементов q' из , для которых выполняются следующие условия: существует путь в графе потока управления ведущий из q' в q или q' = q; .

Обозначим через dist(q', q) длину кратчайшего пути в графе потока управления, ведущего из q' в q (dist(q, q)≡0). Тогда оценочную функцию можно определить следующим образом:

(6)

Выражение, стоящее справа, определяет, за какое минимальное количество переходов можно добраться до элемента покрытия q от уже покрытых элементов из множества

. Функция принимает значение 0 на тех и только тех тестах, которые покрывают элемент q. Заметим, что

Покрытие путей потока управления

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

, где имеет вид , при 1 ≤ i ≤ n . Упорядоченным подмножеством пути назовём последовательность такую, что . Заметим, что в упорядоченном подмножестве пути конечный оператор перехода может не совпадать с начальным оператором следующего за ним перехода.

Пусть есть два пути

и , и пусть

причём

и . Тогда пути и имеют общее упорядоченное подмножество размера m.

Обозначим через length(R) длину пути R, а через

- максимальный размер общего упорядоченного подмножества путей и . Определим оценочную функцию для критерия покрытия путей потока управления следующим образом:

Здесь path(t) - это путь, по которому приходит управление при выполнении теста t. Значение в правой части равно количеству переходов в путях R и path(t), не входящих в максимальное общее упорядоченное подмножество этих путей. Оно равно 0 тогда и только тогда, когда пути R и path(t) совпадают.

Покрытие ветвей потока управления

Тестовый набор удовлетворяет критерию покрытия ветвей потока управления, если при выполнении этого тестового набора управление хотя бы один раз проходит по каждому ребру графа потока управления. Заметим, что любой тестовый набор, удовлетворяющий этому критерию, удовлетворяет также и критерию покрытия операторов исходного кода. Обратное утверждение, однако, неверно []. Элементами тестового покрытия являются переходы в графе потока управления. С каждым переходом в графе потока управления можно связать условие, при котором этот переход может быть выполнен. Переход от оператора q к оператору r, с которым связано условие p, обозначим как

. Для выполнения перехода необходимо и достаточно, чтобы был выполнен оператор q, и чтобы после этого условие p обратилось в истину. Соответственно, для тестов, не покрывающих оператор q, в качестве оценочной подходит функция , определённая уравнением , так как истинность условия p для оценки таких тестов роли не играет. Для тестов, покрывающих оператор q, функция обращается в 0. Для таких тестов оценочная функция должна определять, насколько близок тест к тесту, для которого после выполнения оператора q будет истинным условие p. Таким образом, в общем виде оценочную функцию для критерия покрытия ветвей потока управления можно определить следующим образом:

(7)

Значение функции

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

Функцию

можно определять по-разному в зависимости от характера условия p. Если условие имеет форму простого (не)равенства , где « » обозначает одно из отношений « < », « > », « = », « ≤ » или « ≥ », то для определения функции можно использовать значение , например, следующим образом:

Если условие представляет собой конъюнкцию

, то в качестве значения функции можно взять количество членов этой конъюнкции, принимающих значение «истина». В общем случае эффективно определить функцию затруднительно.

Простейший алгоритм

Рассмотрим простейший генетический алгоритм для решения задачи 1. В качестве множества кандидатов возьмём множество Σ; в качестве оценочной функции возьмём метрику тестового покрытия

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

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

Заметим также, что каждое последующее поколение тестов формируется путём применения операторов кроссовера и мутации к тестам из предыдущего поколения. Если в предыдущем поколении не было ни одного теста, покрывающего некоторый элемент тестового покрытия q, то в последующем поколении такой тест может появиться только как результат кроссовера или мутации тестов, не покрывающих q. Как бы мы не определяли операторы кроссовера и мутации, нет никаких оснований полагать, что получить таким способом тест, покрывающий q, проще, чем при полностью случайной генерации.

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

и сопровождении программного обеспечения, значительная

При разработке и сопровождении программного обеспечения, значительная часть усилий тратится на поиск и устранение ошибок. Самым распространённым методом поиска ошибок является тестирование, то есть процесс выполнения программ с целью обнаружения ошибок []. Здесь слово «программа» понимается в широком смысле, как любая запись алгоритма. В частности, программами являются отдельные процедуры, функции, классы и т.д. Процесс тестирования включает выполнение некоторого набора тестов и анализ полученных результатов. Тест - это последовательность обращений к тестируемой программе. Результатом выполнения теста является решение (вердикт) о том, отработала ли программа корректно или некорректно. Основной характеристикой тестового набора, определяющей качество тестирования, является класс возможных ошибок в программе, которые данный тестовый набор способен обнаружить. Для количественной оценки качества тестирования используются различные метрики тестового покрытия []. Для качественного тестирования необходимо построить полный тестовый набор, то есть набор, удовлетворяющий некоторому критерию полноты. Зачастую критерий полноты для тестового набора определяют через пороговое значение метрики тестового покрытия. Построение полного тестового набора для больших систем вручную может быть крайне трудоёмкой задачей. Автоматизация этого процесса позволяет существенно снизить затраты на тестирование. Существуют различные подходы к решению задачи автоматической генерации тестов: [,,]. Один из них основан на применении генетических алгоритмов []. Этот подход во многих случаях даёт хорошие результаты. К сожалению, его эффективность существенно зависит от используемого критерия полноты. Цель данной статьи - проанализировать некоторые широко распространённые критерии полноты тестового набора на их применимость при использовании генетических алгоритмов для генерации тестов.

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

Применение генетических алгоритмов для генерации тестов предъявляет дополнительные требования к используемым критериям полноты тестового покрытия. Это вызвано тем, что критерий полноты используется не только для оценки качества сгенерированных тестов, но и непосредственно в процессе генерации для оценки близости полученных тестов к нужным результатам. Таким образом, нужно иметь оценочную функцию, позволяющую измерить эту близость, определить, насколько перспективными являются уже построенные тесты с точки зрения их использования в качестве основы для построения новых тестов. Кроме того, нужно иметь в виду, что тривиальные решения - функции вида «покрыто - 0, не покрыто - 1» - работают очень плохо. Для критериев, связанных с покрытием тех или иных путей в коде программы, удается построить достаточно удобные оценочные функции, основанные на количестве непокрытых дуг в пути, который нужно покрыть. В статье построены такие функции для некоторых широко распространённых критериев полноты тестового покрытия.

 Конфигурационные параметры

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

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

Такие параметры могут определять глубину проводимого тестирования, набор выполняемых тестов (например, используя некоторый помечающий их квалификатор), объем проводимых проверок — некоторые проверки в тестах можно помечать как опциональные и выполнять, только если выставлено соответствующее значение некоторого параметра.

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

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

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

 Квалификаторы

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

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

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

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

Литература

V. Maraia. The Build Master: Microsoft's Software Configuration Management Best Practices. Addison-Wesley Professional, 2005. Ю. Гуревич, Microsoft Research. Устное сообщение. 2004. I. Schieferdecker; Z. R. Dai, J. Grabowski. The UML 2.0 Testing Profile and its Relation to TTCN-3. IFIP 15-th Int. Conf. on Testing Communicating Systems — TestCom 2003, Cannes, France, May 2003. Z. R. Dai. UML 2.0 Testing Profile. In M. Broy et al.,eds. Model-Based testing of Reactive Systems. Advanced Lectures. LNCS 3472:497-521, Springer, 2005. UML Testing Profile, 2005. http://www.omg.org/docs/formal/05-07-07.pdf. A. Hartman, K. Nagin. Model Driven Testing — AGEDIS Architecture Interfaces and Tools. Proceedings of the 1-st European Conference on Model Driven Software Engineering, Nuremburg, Germany, December 2003. I. Bourdonov, A. Kossatchev, V. Kuliamin, A. Petrenko. UniTesK Test Suite Architecture. Proceedings of FME’2002, Kopenhagen, Denmark, LNCS 2391:77-88, Springer, 2002. V. V. Kuliamin, A. K. Petrenko, N. V. Pakoulin, A. S. Kossatchev, I. B. Bourdonov. Integration of Functional and Timed Testing of Real-time and Concurrent Systems. Proceedings of PSI’2003, Novosibirsk, Russia, LNCS 2890:450-461, Springer, 2003. В. В. Кулямин, А. К. Петренко, А. С. Косачев, И. Б. Бурдонов. Подход UniTesK к разработке тестов. Программирование, 29(6):25-43, 2003. К. Бек. Экстремальное программирование: разработка через тестирование. СПб.: Питер, 2003. G. Meszaros. xUnit Test Patterns: Refactoring Test Code. Addison-Wesley, 2007. D. Peters, D. Parnas. Using Test Oracles Generated from Program Documentation. IEEE Transactions on Software Engineering, 24(3):161-173, 1998. А. В. Хорошилов. Спецификация и тестирование систем с асинхронным интерфейсом. Препринт 12 ИСП РАН, 2006.

 Модульность

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

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

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

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

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

Тестовые адаптеры — один из наиболее широко используемых видов компонентов теста.
Адаптеры используются и в UniTESK под именем медиаторов , и при разработке тестов на TTCN для их привязки к конкретным тестируемым системам. В UML Testing Profile адаптеры не упоминаются, поскольку он определяет структуру абстрактного тестового набора, не зависящего от синтаксиса обращений к тестируемой системе. Тестовые заглушки (test stubs). Заглушки используются при тестировании отдельных компонентов, модулей или групп модулей, для работы которых необходимы другие компоненты, если эти другие компоненты недоступны (еще не разработаны) или просто не используются, чтобы не усложнять тестирование и анализ его результатов. Заглушка реализует интерфейс одного из отсутствующих компонентов, заменяя его в ходе теста. В качестве результатов заглушки обычно возвращают произвольные значения — постоянные или сгенерированные случайным образом. Однако иногда используются "умные заглушки" (smart stubs), реализующие какую-то часть функций заменяемого модуля или специфические сценарии его работы. Поскольку заглушки часто возникают при модульном тестировании, в книге  различным видам заглушек посвящена отдельная глава. В сообществе, связанном с разработкой на основе тестирования (TDD), заглушки предпочитают называть «фиктивными объектами» (mock objects, mocks) или «тестовыми дубликатами» (test doubles). Более точно, в терминологии  тестовые дубликаты могут относиться к различным видам. Фальшивый объект (fake object). Это простой тестовый дубликат, способный принимать обращения из тестируемой системы и выдавать какие-то результаты в ответ на них, все равно какие, лишь бы происходило корректное взаимодействие. Собственно, заглушка (test stub). В рамках данного сообщества считается, что такие дубликаты должны уметь выдавать значения возвращаемых тестовой системе результатов в соответствии с целями теста, в котором они используются. Эти значения используются как неявные тестовые данные, с помощью которых тест приводит проверяемую систему в нужное состояние или оказывает на нее нужный набор воздействий. Тестовый шпион (test spy). Это разновидность дубликата, которая умеет протоколировать сделанные к ней обращения из тестируемой системы, чтобы проверить их правильность в конце теста. Фиктивный объект (mock object). Отличается от шпиона только тем, что выполняет проверки корректности производимых к нему обращений прямо в ходе работы теста, а не в его конце. Генераторы тестовых данных. Роль их, как видно из названия, состоит в построении некоторого набора данных, обычно одного типа.


Выгода от их использования появляется при необходимости создавать разнообразные объекты одного типа данных в разных тестах. Генераторы тестовых данных сложной структуры обычно делаются составными. Например, генератор значений комплексных чисел можно построить из двух генераторов действительных чисел — для вещественной и для мнимой частей. Генератор сложных документов удобно строить в виде системы из взаимодействующих генераторов отдельных частей таких документов — заголовков, отдельных полей и разделов, отдельных фраз и слов. В технологи UniTESK такого рода компоненты названы итераторами . В профиле UML для разработки тестов  они названы селекторами данных (data selector). Селекторы могут использовать контейнеры данных (data pool), хранящие определенный набор данных, выбор из которых может производиться селектором по дополнительным правилам. Тестовые оракулы (test oracles) или просто оракулы. Тестовый оракул  — компонент, ответственный за вынесение вердикта о соответствии или несоответствии поведения системы требованиям. Работа оракула часто в большой степени зависит от конкретной тестовой ситуации, от сценария данного теста. Однако оракул для сложного сценария часто получается некоторой композицией проверок корректности его отдельных действий. Проверки корректности работы отдельных операций гораздо проще использовать многократно в разных тестах и удобнее применять для отслеживания более точной информации об ошибке, например, точного нарушенного требования или конкретной операции, выполненной с ошибкой. Поэтому удобно определить оракул типа событий или оракул операции, которые привязываются к событиям соответствующего типа или к вызовам определенной операции и выносят вердикт о том, насколько поведение системы при возникновении событий такого типа или при различных обращениях к этой операции соответствует требованиям. Другая возможная разновидность таких оракулов — ограничения целостности данных. Они относятся к некоторому типу данных и должны проверяться каждый раз, когда данные такого типа передаются в тестируемую систему или принимаются от нее.


Поскольку данные сами по себе не активны, а лишь используются в вызываемых операциях и возникающих событиях, обычно ограничения целостности данных используются всеми оракулами операций и событий, в которых затрагивается соответствующий тип данных. Выделение таких модульных оракулов оправдано двумя факторами. Требования формулируются, в основном, именно в отношении различных типов данных, типов событий или операций. Поэтому при переносе их в тесты достаточно удобно и с точки зрения возможных будущих модификаций, и для обеспечения прослеживаемости требований объединять требования к одному типу событий, типу данных или операции в один компонент. Одна и та же операция, данные или события одного и того же типа могут в сложном тестовом наборе использоваться во многих тестах. Это одно из основных отличий «сложных» тестовых наборов от «простых» — во втором случае тестов, затрагивающих одну и ту же операцию, не так много, и проблема многократного использования кода не стоит так остро. Кроме описанных выше оракулов, могут использоваться более сложные, композиционные оракулы. Они возникают в тех случаях, когда для вынесения вердикта о корректности поведения системы в некоторой ситуации требуется нетривиальный анализ многих разных его аспектов, который неудобно проводить в рамках одного компонента. Например, при оценке корректности данных достаточно сложной структуры, таких как XML-документы или программы на языках программирования, или даже документы, в которых может быть смешано несколько языков, проводить такую проверку в рамках одного компонента крайне неудобно — он становится крайне сложным, неудобным для модификаций и сопровождения. В таком случае ограничения целостности данных разбиваются на группы ограничений, относящихся только к определенным конструкциям, и правила корректного связывания конструкций, и для каждой такой группы можно иметь отдельный компонент, проверяющий ее ограничения. Общий оракул для документа в целом получается как некоторая композиция этих компонентов. Композиционные оракулы применяются и при тестировании распределенных систем.


При этом обычно используют набор тестовых агентов, каждый из которых отслеживает поведение только одного компонента системы или небольшой их группы. Он сам может выносить вердикт о корректности событий, касающихся отслеживаемых компонентов, в том числе, используя оракулы отдельных событий. Однако к поведению системы в целом могут при этом предъявляться требования, которые ни один из таких агентов не в состоянии проверить самостоятельно. Тогда их проверка организуется в отдельном компоненте, который получает необходимую ему информацию от всех тестовых агентов. Примером такого составного оракула является сериализатор в технологии UniTESK , который проверяет правильность набора событий в соответствии с семантикой чередования, убеждаясь, что наблюдаемое поведение системы соответствует возникновению этих событий в некотором порядке (все равно в каком). Для этого он вызывает оракулы отдельных событий в разных последовательностях, пока не будет найдена корректная или не будет показано, что подходящей последовательности нет, что означает ошибку. Другим примером является арбитр, один из компонентов, определяемых в профиле UML для разработки тестов . Однако он играет только роль посредника, позволяя тестовым агентам, выносящим свои вердикты на основе доступной им информации, обмениваться данными об этих вердиктах друг с другом. Других компонентов тестов, которые выделялись бы в рамках различных методов построения тестов и различными авторами, пока не удается найти. Все остальные виды компонентов специфичны для определенных методов тестирования и чаще всего не имеют аналогов в других подходах. При определении модульной структуры тестов стоит учитывать, что вместе с появлением возможности многократно использовать одни и те же компоненты, повышается и их сложность для людей, не знающих об используемой архитектуре. Поэтому архитектура таких тестов, с указанием всех видов используемых компонентов и задач, решаемых ими, должна быть описана в документации на тестовый набор. Крайне желательно постепенно стандартизовать достаточно широкий набор видов модулей теста, чтобы сделать возможным их использование в различных инструментах. Другое препятствие к широкому использованию модульности тестов связано с усложнением анализа ошибок.Тест уже не представляет собой единый, изолированный сценарий работы, для понимания которого не нужно заглядывать в много различных документов или в код различных компонентов. Поток управления в рамках одного тестового варианта или более сложного теста становится иногда очень причудливым и сложным, разобраться в нем становится тем труднее, чем больше разных видов компонентов используется. Поэтому при использовании модульных тестов необходимы дополнительные усилия по упрощению анализа ошибок. Одним из вариантов решения этой проблемы может быть автоматическое создание более простых, классических тестовых вариантов, повторяющих ситуацию, в которой обнаружена ошибка.

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

При тестировании всегда используется конечный набор тестов, даже в определении тестирования в SWEBOK  сказано, что оно проводится в конечном наборе ситуаций. Однако не менее важен другой аспект тестирования, также зафиксированный в этом определении, — необходимость сделать выводы о качестве проверяемой системы и потребность в том, чтобы такие выводы были достоверными. Чтобы обеспечить достоверности выводов по результатам тестирования, оно должно проводиться так, чтобы все существенные аспекты поведения тестируемой системы и все факторы, способные повлиять на его корректность, были хоть как-то затронуты. Для сложного программного обеспечения таких аспектов и факторов очень много, что и приводит и к большому количеству необходимых тестов, и к сложности их самих.

Чаще всего тестовые наборы организуются в виде комплектов тестовых вариантов. Один тестовый вариант представляет собой последовательность действий, состоящую из следующих частей. Сначала выполняются некоторые действия, нацеленные на создание определенной ситуации, приведение тестируемой системы в определенное состояние. Это преамбула тестового варианта. Затем выполняется основной набор действий, правильность которых в заданной ситуации нужно проверить. Часто этот набор содержит ровно одно действие. Обычно ситуация и действия, которые в ней нужно выполнить, задаются целью тестирования (test purpose), для достижения которой и создается данный тестовый вариант.

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

Представление тестовой системы как набора тестовых вариантов сложилось достаточно давно, еще 30-40 лет назад.
Оно довольно удобно для разработки тестов человеком — можно поставить определенную задачу (в данном случае представленную целью тестирования), а затем оформить ее решение в виде отдельной процедуры, которую можно использовать независимо от разработчика. Кроме того, такая организация тестов имеет следующие достоинства. Каждый тестовый вариант сам по себе достаточно компактен и легко отделяется от остального набора тестов. Поэтому, если необходимо построить тестовый набор, нацеленный на проверку только определенных функций или определенной части интерфейса тестируемой системы, соответствующие тестовые варианты можно выделить и использовать отдельно от остальных. По той же причине достаточно просто выбросить часть тестовых вариантов из набора, если потребуется уменьшить его размер или ускорить выполнение тестов. Тестовые варианты облегчают разработчикам анализ возникающих ошибок. Хотя основной целью тестирования является только обнаружение ошибок, а не их локализация, результаты тестирования только в виде вердиктов «ошибок нет» или «ошибки есть» никому не нужны на практике. В случае обнаружения ошибки разработчики системы надеются получить достаточно информации, чтобы легко восстановить и проанализировать возникшую ситуацию. Для этого тестовый вариант хорошо подходит — он представляет собой единый сценарий событий, достаточно компактен и формирует ровно одну основную ситуацию, так что для выполняющего отладку разработчика область анализа ограничена. Но у организации тестовой системы как набора тестовых вариантов есть и недостатки, связанные с многократно возросшей сложностью тестируемых систем и необходимостью постоянного обновления и развития наборов тестов. В современных тестовых наборах тестовых вариантов часто очень много, иногда десятки и сотни тысяч. Таким количеством тестов уже нельзя эффективно управлять, если не вводить дополнительных уровней иерархии или каких-то классификаторов. Очень часто в больших наборах тестов одни и те же их элементы используются многократно.


Например, проверка реакции системы на одни и те же действия обычно одинакова, генерация тестовых данных для разных операций может выполняться одними и теми же процедурами. Все это приводит к потребности обеспечения многократного использования одних и тех же решений, которые стоит оформлять в виде отдельных компонентов. Таким образом выделяются тестовые оракулы — компоненты, чья задача состоит в проверке корректности поведения тестируемой системы в ответ на воздействия определенного типа, возникающие в различных тестах. Генераторы тестовых данных тоже часто становятся отдельными компонентами, которые можно использовать в разных тестах. Возможные виды компонентов тестовых систем обсуждаются в профиле универсального языка моделирования UML для разработки тестов (UML 2.0 Testing Profile [6-10]), в предложениях общей архитектуры инструментов тестирования, сформулированных в проекте AGEDIS [11-13], а также в работах, посвященных технологии UniTESK [14-16]. Техники выделения модулей в модульных тестах (unit tests), как общего характера, так и связанные с подходом к разработке на основе тестирования (test driven development, TDD), обсуждаются в книгах . Развитие тестируемой системы или потребность в независимом развитии тестового набора (например, для повышения полноты тестирования, добавления проверки ранее игнорируемых свойств и т.п.) вынуждают вносить изменения в тесты. С точки зрения удобства внесения изменений неструктурированный набор тестовых вариантов представляет собой одно из самых худших решений. Без аккуратного анализа всех входящих в него тестов невозможно понять, какие требования к тестируемой системе и какие ее модули проверяются, а какие нет, какие для этого используются техники и пр. Крайне тяжело вносить изменения, при которых иногда требуется согласованно модифицировать десятки и сотни отдельных тестовых вариантов в связи с изменением лишь одного-двух требований к проверяемой системе. Простые, неструктурированные наборы тестовых вариантов не всегда удобны при автоматической генерации тестов из каких-либо моделей.


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


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

Тестирование софта - статьи

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

 Техники организации тестовых наборов

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

 Введение

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

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

Однако, с ростом сложности систем, сложность разработки и поддержки в рабочем состоянии тестовых наборов для них растет гораздо быстрее. Современные методы разработки ПО позволяют с разумными трудозатратами создавать системы объемом до десятков миллионов строк кода , хотя еще двадцать лет назад эта планка была на уровне десятков тысяч строк. В то же время используемые на практике техники создания тестов за это время увеличили свою масштабируемость лишь примерно на порядок, хотя тестовый набор для сложной программной системы сам по себе также является сложной системой. Возникающее расхождение между масштабами систем, которые мы можем создать, и систем, которые мы в состоянии аккуратно проверить, грозит увеличением количества сбоев в ПО и ущерба от них. О масштабах возникающих проблем говорят хотя бы следующие цифры, относящиеся к различным программным продуктам компании Microsoft.
Тестовый набор для текстового редактора Microsoft Word XP содержал около 35 тысяч тестов , а для Windows XP — более 2-х миллионов. Если в разработке Windows NT 4.0 участвовало около 800 служащих компании, а в ее тестировании — около 700, то у Windows 2000 было около 1400 разработчиков и 1700 тестировщиков, т.е. соотношение программистов и тестировщиков поменялось на обратное . Еще более важным фактором увеличения сложности тестовых наборов является необходимость их развития, следующего за развитием тестируемой системы. Любое практически значимое ПО проходит достаточно долгую эволюцию, постепенно расширяя и изменяя свои функции и пользовательский интерфейс. Соответственно, для снижения затрат на сопровождение и обеспечение большей предсказуемости этого развития аналогичный путь должен проходить и тестовый набор. Но в него вносить изменения сложнее, чем в проверяемую систему, — помимо связей между отдельными его частями, необходимо учитывать и связи с подсистемами м и модулями тестируемого ПО, их отдельными функциями и проверяемыми свойствами. Наиболее значимый вклад в масштабируемость технологий создания и эксплуатации тестов вносит используемая организация тестовых наборов. Количество тестов в тестовых наборах для современного ПО довольно велико и продолжает увеличиваться. Кроме того, часто тесты связаны друг с другом разнообразными зависимостями, которые не всегда выделены явно, но должны учитываться при сопровождении тестов и внесении в них изменений. Проблемам организации сложных тестовых наборов и подходам к их решению и посвящена данная статья.

 Заключение

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

Наиболее легко с широко применяемыми сейчас подходами к разработке тестов сочетается использование набора квалификаторов для классификации тестов и указания связей между тестами и требованиями или элементами тестируемой системы. Однако большинство инструментов управления тестами поддерживает использование только предопределенного набора квалификаторов, которые не могут быть расширены. Пока только HP/Mercury TestDirector  имеет возможность добавления пользовательских квалификаторов, которые можно затем использовать для построения специфических отчетов — группировки или отбрасыванию результатов тестов по значениям квалификатора.

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

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

Генерация тестовых данных сложной структуры с учетом контекстных ограничений

А.В. Демаков, С.В. Зеленов, С.А. Зеленова,
Труды Института системного программирования РАН

Идея метода

Множество вершин типа t изоморфно декартову произведению множеств объектов, которые могут быть её полями. Поясним это на примере. Пусть вершина типа t содержит: Список list детей типа p Ребёнка child типа s Необязательного ребёнка opt_child типа r Атрибут attr типа W

Пусть Ml - множество списков вершин типа p, Ms - множество вершин типа s, Mr - множество вершин типа r, Mw - множество объектов типа W. Тогда множество вершин типа t изоморфно декартову произведению множеств Ml, Ms, Mw, Mr U ε (здесь ε - символ отсутствия ребёнка). Действительно, любой кортеж из этого декартова произведения - набор возможных значений полей вершины типа t.

Это наблюдение обеспечивает общий метод генерации вершин типа t. Итак, для построения (конечного) множества вершин типа t необходимо построить конечные множества значений полей такой вершины и выбрать подмножество из декартова произведения этих множеств.

До сих пор мы говорили о ситуации, когда нет никаких связей между атрибутами, а также нет никаких ограничений на значения полей вершины. Если такие связи или ограничения есть, то множества значений полей зависят друг от друга. То есть для того, чтобы определить множество допустимых значений для одного поля, нужно знать значения каких-то других полей. Если в строящемся дереве два атрибута разных вершин зависят друг от друга, то эта зависимость может быть описана через зависимость полей некоторого узла (см. рис. 5).

Процесс генерации теперь будет выглядеть несколько по-другому. Сначала нужно определить зависимости между значениями полей. Граф зависимостей должен быть ациклическим, иначе будет невозможно установить порядок построения полей вершины. Когда порядок построения полей определен, строим множество значений для независимого поля, выбираем из него какое-то значение и устанавливаем его в качестве соответствующего поля вершины. Затем строим множества значений для полей, зависящих от уже установленного поля, выбираем из них значения, устанавливаем выбранные значения в качестве соответствующих полей вершины и т.д.
Таким образом, множества значений полей строятся в соответствии с уже построенным контекстом, поэтому результирующая вершина будет удовлетворять всем наложенным ограничениям. Для построения детей вершины можно использовать такой же метод генерации вершин соответствующего типа (см. рис 6; стрелками указано направление движения данных от одного генератора к другому).

Откуда могут возникать ограничения и связи между элементами дерева? Есть четыре основных источника. Первый источник - это семантические требования на данные, такие как требование существования определения используемой переменной в языках программирования или требование уникальности значений какого-то атрибута в XML-документе. Второй источник - это удовлетворение требований определённого критерия покрытия. В большинстве практических случаев множество всевозможных деревьев с вершинами определённых типов - это бесконечное множество, и мы, конечно же, не можем построить его целиком. Но это и не нужно, так как обычно такое множество можно разбить на конечное число классов таким образом, что в одном классе будут находиться элементы, "эквивалентные" с точки зрения целевой задачи. Такое разбиение называется критерием покрытия множества деревьев. Для одного и того же множества деревьев можно формулировать разные критерии покрытия; они будут зависеть от целевой задачи. Третий источник - это ограниченность ресурсов. Часто даже в пределах одной задачи сформулировать для неё точный критерий покрытия невозможно или же слишком трудоёмко. Поэтому приходится брать более сильный критерий покрытия, разбивающий множество деревьев на более мелкие классы. При этом число классов может весьма сильно возрасти. О том, как можно бороться с этой проблемой, будет сказано немного позже. Наконец, четвертый источник - это наличие рекурсии во множестве типов вершин T. Наличие рекурсии влечет необходимость её ограничения, то есть запрещения перебора деревьев с глубиной рекурсии, большей некоторого числа. При отсутствии ограничений на рекурсию множество допустимых деревьев бесконечно, а это значит, что генератор может войти в бесконечный цикл. Итак, в самом общем виде идея состоит в том, чтобы создать систему генераторов вершин.Генераторы образуют иерархическую структуру, соответствующую структуре типов вершин. При этом работа генератора поля вершины может зависеть от результата работы генераторов других полей этой же вершины в соответствии с требованиями, накладываемыми на строящееся дерево, то есть работа генераторов зависит от контекста строящейся вершины.

Использование абстрактных моделей

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

Для начала введём понятие абстрактной модели. Абстрактная модель объекта - это фактор-объект, получаемый с помощью абстрагирования от некоторых деталей. В качестве примера можно привести граф наследования классов в языках Java или C++. Граф наследования не содержит никакой информации о методах или полях классов, он является абстрактной моделью системы классов, для которой эта информация несущественна.

Абстрактная модель может иметь разные представления, так, например, граф наследования можно представить в виде списка рёбер, или в виде последовательности чисел, или графически в виде дерева. То есть модель эквивалентна некоторой части объекта, но может не совпадать с ней (рис. 10).

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

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

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

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

Итераторы

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

В самом общем виде итератор - это объект, имеющий несколько последовательных состояний. Итератор может перевести себя в начальное состояние; находясь в каком-то состоянии, он может перевести себя в следующее состояние, а также ответить на вопрос, имеется ли у него следующее состояние. Итератором значений называется итератор, связанный с некоторым упорядоченным множеством. Итератор значений можно рассматривать как "указатель" на элемент множества. Для него имеются три операции: встать в начало множества, передвинуться на следующий элемент множества и выдать текущий элемент множества (вместо "выдачи" текущего элемента итератор значений может проделать с ним любую другую операцию).

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

Пример. Пусть имеются итераторы значений i1, i2, связанные с множествами {a,b,c},{d,e} соответственно. И пусть мы хотим построить итератор значений декартова произведения этих множеств.

Используем для этого такой комбинатор (рис.8): его состояния - это тройка состояний итераторов i1, i2. Начальное состояние - тройка начальных состояний итераторов i1, i2. Таким образом, чтобы перейти к начальному состоянию, наш комбинатор переводит итераторы i1, i2 в начальное состояние. Чтобы перейти к следующему состоянию, комбинатор смотрит, в каком положении находится итератор i2. Если у этого итератора есть следующее состояние, то итератор в него переводится - получается новая пара состояний итераторов i1, i2, то есть новое состояние для комбинатора. Если у итератора i2 нет следующего состояния, то комбинатор смотрит, есть ли следующее состояние у итератора i1; если есть, то итератор i1 переводится в следующее состояние, а итератор i2 - в начальное, снова получается новая пара состояний итераторов i1, i2, а значит и новое состояние комбинатора.
Если же следующего состояния нет ни у итератора i1, ни у итератора i2, то это означает, что и комбинатор не имеет следующего состояния. Другой важный пример - это комбинатор системы зависимых итераторов. Пусть нам нужно проитерировать пары букв и цифр, при этом для каждой буквы есть своё множество цифр, с которыми она может быть в паре. Пусть для буквы a - это множество {0, 1}, для буквы b - множество {2, 3, 5}, для буквы c - множество {4}. Заведём итераторы для множеств цифр и букв: итератор i1 для множества {a, b, c}, итераторы i2, i3, i4 - для множеств {0, 1}, {2, 3, 5}, {4} соответственно. Состоянием комбинатора теперь будет пара состояний двух других итераторов: итератора i1 и итератора, соответствующего состоянию итератора i1. Работа комбинатора проиллюстрирована рис. 9. При переходе итератора букв в следующее состояние в зависимости от этого состояния выбирается итератор цифр. При переходе к другой букве итератор цифр будет другим.

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

Представление тестовых данных

Многие языки формального описания данных сложной структуры, по сути, описывают некоторое атрибутированное дерево. Среди таких языков - BNF грамматики формальных языков, XMLSchema для описания структуры XML-документов, ASN.1 для описания формата данных телекоммуникационных протоколов и многие другие.

Действительно, сама структура записи информации в компьютере предполагает такую форму: всякий объект записывается в памяти как некая последовательность бит, в которой можно выделить подпоследовательности, в них - другие подпоследовательности и т.д. При этом выделенные подпоследовательности могут быть связаны между собой, например, равны друг другу.

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

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

Предварительные сведения и понятия

В начале введём понятие атрибутированного дерева.

Как известно, дерево - это граф, в котором нет циклов. Мы будем рассматривать ориентированные деревья, то есть деревья, у которых имеется выделенная вершина - корень, и все ребра ориентированы от более близких к корню вершин к более дальним.

Пусть A - некоторая вершина ориентированного дерева. Если она не является корнем, то существует единственная вершина B, из которой в A идет ребро. Вершину B мы будем называть родителем вершины A, а вершину A, соответственно, ребёнком вершины B. В отличие от родителя, детей у вершины может быть много.

Деревья, которые мы рассматриваем, являются атрибутированными, то есть с каждой вершиной могут быть связаны её атрибуты - объекты произвольного типа.

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

Пример. Рассмотрим следующее определение типа вершины: вершины типа A должны содержать одного ребёнка типа B с именем child, необязательный атрибут name типа "строка", список list детей типа С. Примеры вершин типа A приведены на .

Заметим, что на рис. нет атрибута name - это возможно, так как в определении типа этот атрибут заявлен необязательным, в то же время список list присутствует всегда, хотя может и не содержать элементов.

Итак, в определении типа вершины должны быть описаны: Атрибуты вершины: их имена и типы, а также то, являются ли они обязательными. Списки атрибутов: их имена и типы элементов этих списков. Дети вершины: их имена и типы, а также то, являются ли они обязательными. Списки детей: их имена и типы элементов этих списков.

Детей, атрибуты и списки вершины мы будем называть полями этой вершины.

Пусть имеется конечное множество T типов вершин, замкнутое относительно использования типов (то есть все типы вершин, на которые есть ссылки в определениях типов из этого множества, определены). Далее мы будем рассматривать множество D деревьев, типы вершин которых принадлежат множеству T.

Схема генерации

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

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

Итак, опишем генератор вершин типа t. Контекст для строящейся вершины типа t - это внешний параметр генератора. Генератор создаёт вершину-заготовку, в которой поля не установлены. По контексту вершины генератор вычисляет граф зависимостей между полями вершины. Для этого он использует информацию из элементарных ограничений. Из графа зависимостей вычисляется порядок построения полей: f1 → f2 → … → fn. Далее строится комбинатор зависимых генераторов значений полей, у которого первая ось зависимости - генератор независимого поля f1, вторая ось зависимости - генератор поля f2, зависимого от поля f1, и т.д. При этом генераторы полей при переходе в новое состояние проставляют значение соответствующего поля вершины. Генератор значений конкретного поля fi создаётся так: Если поле - ребёнок c типа s, то генератор строит для него контекст, основываясь на контексте вершины-родителя и значений полей, от которых зависит поле fi. Для полученного контекста строится генератор вершин типа s, который используется в качестве генератора значений поля. Если поле - атрибут, то генератор значений для него строится так: Для всех элементарных ограничений, наложенных на данный атрибут, вычисляются множества допустимых значений M1, M2, …, Mk. Как было сказано ранее, они задаются итераторами. Строится итератор, перебирающий значения из объединения множеств M1, M2, …, Mk, которые удовлетворяют всем элементарным ограничениям, наложенным на данный атрибут. Этот итератор и будет генератором значений данного атрибута. Если поле - список, то для него строится комбинатор зависимых итераторов, у которого первая ось зависимости - итератор длины списка, вторая - итератор первого элемента списка, третья - итератор второго элемента списка, и т.д. Этот комбинатор используется в качестве генератора значений списка. Генераторы значений элементов списка строятся так же, как и генераторы значений полей.

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

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

[1]
[2]
[3]
[4]
[5]
[6]
[7]	Paul Purdom. A sentence generator for testing parsers. // Behavior and Information Technology. 12(3):366-375, 1972.
[8]	B.A. Wichmann, B.Jones. Testing ALGOL 60 compilers. // Software Practice and experience. 6 (1976) 261-270.
[9]	A. Celentano, S. Crespi Reghezzi, P. Della Vigna, C. Ghezzi, G. Granata, and F. Savoretti. Compiler Testing using a Sentence Generator. // Software - Practice and Experience. 10:897-918, 1980.
[10]	A.G. Duncan, J.S. Hutchison. Using Attributed Grammars to Test Designs and Implementation. // In Proceedings of the 5th international conference on Software engineering. 170-178, 1981.
[11]	А.К. Петренко и др. Тестирование компиляторов на основе формальной модели языка // Препринт института прикладной математики им. М.В Келдыша, № 45, 1992.
[12]	A. Kalinov, A. Kossatchev, A. Petrenko, M. Posypkin, V. Shishkov. Using ASM Specifications for Compiler Testing // Proceedings of Abstract State Machines - Advances in Theory and Applications 10th International Workshop, ASM 2003.
[13]	С.В. Зеленов, С.А. Зеленова, А.С. Косачев, А.К. Петренко. Генерация тестов для компиляторов и других текстовых процессоров // Программирование, Москва. - 2003. - 29. - № 2. - с. 59-69.
[14]	С.В. Зеленов, С.А. Зеленова. Генерация позитивных и негативных тестов парсеров // Программирование, том. 31, №6, 2005, 25-40.
[15]	С.В. Зеленов, С.А. Зеленова, А.С. Косачев, А.К. Петренко.
[16]	М.В. Архипова. Генерация тестов для модулей проверки статической семантики в компиляторах. // Труды ИСП РАН, т. 8, 2004, с. 59-76.
[17]	A.K. Petrenko. Specification Based Testing: Towards Practice // LNCS. - 2001. - 2244. - p. 287-300.
[18]	В.В. Кулямин, А.К. Петренко, А.С. Косачев, И. Б. Бурдонов. Подход UniTesK к разработке тестов. // Программирование, 29(6):25-43, 2003.
[19]	V. Kuliamin, A. Petrenko, A. Kossatchev, I. Bourdonov. UniTesK: Model Based Testing in Industrial Practice. // Proceedings of the 1-st European Conference on Model-Driven Software Engineering, Nurnberg, December 2003.

Способ описания ограничений

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

В каждый момент построения дерева мы имеем какую-то конфигурацию вершин и атрибутов. Для конкретной вершины в этом недостроенном дереве мы можем определить её состояние - это то, что окружает вершину в данный момент. Фактически, это вся построенная часть дерева, но с точки зрения данной вершины. Рассмотрим понятие состояния на примере. На рис. 7 показано дерево с тремя вершинами типа Def (определение переменной). Чем отличается состояние, например, второй вершины от состояния первой? Состояния этих вершин различны, так как положения их в дереве различны. Из состояния (положения) первого определения видно, что в нём не могут быть использованы ссылки на переменные, так как до этой инструкции нет определённых переменных, а во втором определении можно использовать ссылку на переменную, поскольку к этому моменту уже есть определённая переменная v1.

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

Итак, множество значений поля вершины может зависеть от: значений других полей этой вершины; некоторых аспектов состояния вершины.

Введём понятие элементарного ограничения. Это ограничение накладывается на поле вершины. Чтобы его определить, нужно задать: тип вершины t; поле f вершины типа t, на которое накладывается ограничение; поля вершины f1, f2, …, fk, от которых зависит множество допустимых значений поля f; аспекты состояния вершины S1, S2, … , Sn, от которых зависит множество допустимых значений поля f; способ вычисления множества допустимых значений поля f; функцию проверки значения поля f на соответствие определяемому ограничению; функцию ограничения количества используемых значений поля f.

Итак, в каждой вершине строящегося дерева определены: аспекты состояния этой вершины, существенные для её построения; ограничения на поля вершины.

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

Тестирование программных систем является важным

Тестирование программных систем является важным компонентом всех проектов, связанных с разработкой программного обеспечения. По мере роста масштабов и сложности программных систем растет трудоемкость тестирования. Решить задачу повышения качества и сокращения расходов на тестирование можно за счет привлечения эффективных средств автоматизации разработки тестов. Одной из наиболее распространенных задач, возникающей при тестировании сложных программных систем, является генерация тестовых данных сложной структуры. Такие задачи характерны для тестирования систем, использующих интернет-протоколы, XML-технологии, SQL-интерфейсы баз данных; интерпретаторов и трансляторов языков программирования, спецификаций, командных языков, а также многих других видов программных систем. Существенным недостатком имеющихся в настоящее время инструментов для генерации тестовых данных сложной структуры для тестирования, например, приложений над базами данных [-], XML-приложений [-], компиляторов и других обработчиков формальных языков [-] является то, что в них очень узок предоставляемый спектр возможностей по управлению процессом генерации тестовых данных. Поэтому для достижения приемлемого качества тестирования приходится генерировать очень большие множества тестовых данных, что сопряжено с большими накладными расходами по использованию ресурсов, как на этапе генерации тестовых данных, так и на этапе анализа результатов прогонов тестов. В настоящей статье представлена технология автоматической генерации тестовых данных сложной структуры, которая предполагает возможность тонкой настройки процесса генерации тестовых данных и оптимизации этого процесса под особенности функциональности конкретного тестируемого приложения. В основу предлагаемой технологии положен опыт работ ИСП РАН по разработке тестовых данных и созданию автоматических генераторов тестовых данных на основе языковых моделей [-]. Предложенный в ИСП РАН подход к работе с данными сложной структуры является частью разработанной в ИСП РАН технологии UniTesK тестирования программного обеспечения на основе формальных спецификаций и моделей [-]. Этот подход основан на использовании формального описания данных сложной структуры.

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

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

---

---