Lecture05 (Лекции в ПДФ), страница 2

Минимальный тестовый набор для тестирования печати Web-страницы.Эти примеры обобщаются до понятия покрывающего набора глубины t. Нам не важныконкретные значения факторов или параметров, важно только, что они образуют конечноемножество. Поэтому можно считать, что если некоторый фактор имеет n возможныхзначений, ими являются числа от 0 до (n-1). Если заданы конечные наборы значений {vij} дляk параметров, i-й параметр может принимать ni различных значений, то покрывающимнабором глубины t <= k является любой набор из списков значений всех параметров {vif(j)},такой что любая комбинация возможных значений любых t параметров встречается в этомнаборе хотя бы один раз.Пары значений параметров покрываются наборами глубины 2, тройки — наборамиглубины 3, и т.д.000000011111112222222222200001110001111000000111110014234134012401223301234001210332030312302031211102002121212220020100122204014213432231010304232401Таблица 3. Покрывающий набор, соответствующий показанному выше тестовому набору.Множество всех покрывающих наборов глубины t с k параметрами, принимающими n1,…, nk значений обозначается CA(t, n1, …, nk).

Минимальное возможное количество рядов впокрывающем наборе обозначается CAN(t, n1, …, nk). Таблица 3 представляет пример набораиз CA(2, 3,⋅2,⋅5,⋅4,⋅3,⋅5) и показывает, что CAN(2, 3,⋅2,⋅5,⋅4,⋅3,⋅5) = 25.Если все параметры могут принимать одно и то же число значений, т.е. n1 = n2 = …= nk =n, соответствующий покрывающий набор называется однородным. Множество однородныхнаборов CA(t, n, …, n) также обозначается CA(t; k, n), соответствующее минимальное числорядов в таком наборе — CAN(t; k, n).Выгода от использования покрывающих наборов определяется тем фактом, что чащевсего существуют покрывающие наборы небольшой мощности, в которых количество рядовзначительно меньше, чем число всех возможных комбинаций значений параметров.Покрывающие наборы могут эффективно использоваться в ситуациях, в которыхвыполнены следующие условия.•Есть некоторый вид воздействий на тестируемую систему, имеющий довольно многопараметров или факторов, влияющих на его работу.•Значения каждого из параметров можно разбить на (небольшое) конечное числоклассов, таких, что все существенные изменения в поведении системы происходяттолько из-за изменения класса одного из параметров.

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

Приколичестве значений всех параметров равном 2 есть даже простой алгоритм построенияминимального покрывающего набора глубины 2 (см. ниже).Для однородных наборов глубины 2, в которых число значений параметров равно степенипростого числа n = pk есть метод построения, основанный на арифметике конечных полей.Известно, что для каждой степени простого числа pk есть конечное поле с таким количествомэлементов, называемое полем Галуа GF(pk). Для k = 1, т.е. когда число элементов самоявляется простым, GF(p) изоморфно полю вычетов по модулю p — ]p.Рассмотрим таблицу из элементов поля GF(pk), построенную следующим способом.Первый столбец состоит из n2 значений, сгруппированных по n одинаковых значений.Каждую такую группу значений, равных i, будем называть i-м блоком. Первому столбцуприсваивается номер ∞.Второй столбец состоит из n2 значений, выстроенных так, что в каждом блокевстречаются все возможные n значений.

Значение, стоящее во втором столбце обозначимчерез j. Второму столбцу присвоим номер 0.Все остальные столбцы, с третьего по (n+1)-й, с номерами m = 1...(n-1) построим так,чтобы в блоке i в j-м ряду стояло значение, получаемое как m*i+j в арифметике GF(pk).Построенная так таблица будет покрывающим набором из множества CA(2; n+1, n), еслирассматривать каждую ее строку как набор значений n+1 параметров, соответствующихстолбцам.Пример для n = 5.Поскольку поле GF(5) изоморфно полю вычетов по модулю 5, складывать и умножатьчисла в обычной целочисленной арифметике, а в конце брать вместо результата его вычет помодулю 5. Получаемый таким способом покрывающий набор представлен ниже.NN∞00000100123401012341201234230123434012344111122222333334444412340123401234012342340234013401240123340140123123403401240121234040123234010123340122340112340Пример для n = 4.В GF(4) сложение и умножение устроены иначе, чем по модулю 4.

Поэтому сначалаприведем таблицы сложения и умножения в поле с 4-мя элементами.+012300123110322230133210*012300000101232023130312Получаемый для n = 4 по описанной конструкции покрывающий набор представлен ниже.NN∞000011112222333300123012301230123101231032230132102012323013210103230123321010322301Таким образом можно строить однородные наборы глубины 2 для (n+1) параметра с nзначениями при n = pk. Этим показывается, что CAN(2; pk+1, pk) = p2k.Похожая конструкция существует для покрывающих наборов глубины t > 2 и n = pk > t.Для этого надо взять таблицу из n+1-го столбца и nt строк. Каждую строку ее можносопоставить набору a0, a1, …, at-1 элементов из поля GF(pk). Столбцы так же обозначаются∞, 0, 1, ..., n-1.

Элемент в определенной строке и определенном столбце вычисляется последующим правилам.∞0xa0a1...at-1 a0 at-1 ΣaixiЗдесь снова используются сложение и умножение из поля GF(pk).Для глубины 3 и n = 2k > t можно расширить эту таблицу на еще один столбец — двапервых столбца обозначим ∞1 и ∞2, остальные, как раньше, — 0, 1, ..., n-1.∞0∞10xa0a1a2 a0 a1 a2 ΣaixiТаким образом, оказывается, что CAN(t; pk+1, pk) = ptk при t < pk, а также CAN(3; 2k+2, 2k)= 23k при k > 1.Пример для n = 3, t = 3.NN000001002010011012020021022100101102110111112120121122200201202210211212220221222∞000000000111111111222222222001201201201201201201201201210121202011202010122010121202012201120120012201201120012Представленные выше конструкции позволяют строить однородные покрывающиенаборы для небольшого числа параметров (<= n+1), принимающих n значений для nявляющегося степенью простого числа.Посмотрим теперь, как можно строить покрывающие наборы для числа значений, неявляющегося степенью простого числа.

Оказывается, есть общая конструкцияпокрывающего набора для числа значений, являющегося произведением чисел значений вуже построенных покрывающих наборов: покрывающие наборы с k параметрами глубины tдля n1 и n2 значений дают покрывающий набор с k параметрами для глубины t для n1·n2.Для его построения обозначим элементы двух исходных наборов через aij и blj — у этихнаборов одинаковое число столбцов, и, возможно, разное число строк. В первом набореучаствуют элементы от 0 до (n1–1), во втором — от 0 до (n2–1). Любое число от 0 до (n1·n2–1)можно однозначно представить в виде n2·q + r, где q лежит от 0 до (n1–1), r — от 0 до (n2–1).Кроме того, обозначим строки новой таблицы парами индексов строк двух исходных таблиц.Тогда ее элементы могут быть построены по формуле x(i,m)j = n2·aij + bmj.

Подученная тактаблица представляет покрывающий набор с k параметрами для глубины t для n1·n2.Как следствие CAN(t; k, n1·n2) <= CAN(t; k, n1)·CAN(t; k, n2).Пример для n = 6 = 2·3.01230011001011011001234567800011122200120120121012120201201220112000010203040506070810111213141516171820212223242526272830313233343536373800011122200011122233344455533344455500120120123453453450120120123453453421012120201345453534345453534012120204Описанные выше техники позволяют строить покрывающие наборы любой глубины слюбыми значениями для небольшого количества параметров.

Чтобы увеличить количествопараметров, нужно использовать другие подходы.Во-первых, для глубины 2 и произвольного числа параметров k, принимающих только 2значения, есть алгоритм, позволяющий достаточно быстро находить минимальныйвозможный покрывающий набор.Выберем наименьшее N такое, что выполнено k ≤ C N⎡ N−1/ 2 ⎤ .

Здесь ⎡x⎤ — наименьшее целоечисло, большее или равное x, C rq — биномиальный коэффициент. Получаемые значения Nдля разных k сведены в следующую таблицу.k2-345-1011-1516-3536-5657-126127-210211-462N456789101112k1717-30033004-64356436-1144011441-2431024311-4375843759-9237892377-167960167961-352716352717-646646N151617181920212223k2496145-52003005200301-96577009657701-2005830020058301-3744216037442161-7755876077558761-145422675145422676-300540195300540196-565722720565722721-1166803110N262728293031323334463-792793-17161314646647-13520781352079-249614424251166803111-22039614302203961431-45375676503536Это число N равно числу строк в покрывающем наборе глубины 2 с двумя значениямидля k параметров. Из таблицы видно, что небольшое число тестов может покрыть всекомбинации пар значений для огромного количества параметров — 10 тестов достаточно для126 параметров, а 20 тестов — для более чем 92000.Первую строка набора сделаем состоящей целиком из 0.

Остается N–1 строк, элементыкоторых строятся по столбцам. В качестве этих столбцов берутся все возможныепоследовательности из ⎡N/2⎤ единиц и ⎣N/2⎦-1 нулей.Примеры.CAN(2; 4, 2) = 500001110100101010011CAN(2; 10, 2) = 600000 0000011111 1000011100 0111010011 0110101010 1101100101 10111CAN(2; 15, 2) = 700000 00000 0000011111 11111 0000011111 10000 1111011100 01110 1110110011 01101 1101101010 11011 1011100101 10111 01111CAN(2; 35, 2) = 800000 00000 00000 00000 00000 00000 0000011111 11111 11111 11111 00000 00000 0000011111 11111 00000 00000 11111 11111 0000011110 00000 11111 10000 11111 10000 1111010001 11000 11100 01110 11100 01110 1110101001 00110 10011 01101 10011 01101 1101100100 10101 01010 11011 01010 11011 1011100010 01011 00101 10111 00101 10111 01111CAN(2; 56, 2) = 900000 00000 00000 00000 00000 00000 00000 00000 00000 00000 00000 011111 11111 11111 11111 11111 11111 11111 00000 00000 00000 00000 011111 11111 11111 11111 00000 00000 00000 11111 11111 11111 00000 011111 11111 00000 00000 11111 11111 00000 11111 11111 00000 11111 011110 00000 11111 10000 11111 10000 11110 11111 10000 11110 11110 110001 11000 11100 01110 11100 01110 11101 11100 01110 11101 11101 101001 00110 10011 01101 10011 01101 11011 10011 01101 11011 11011 100100 10101 01010 11011 01010 11011 10111 01010 11011 10111 10111 100010 01011 00101 10111 00101 10111 01111 00101 10111 01111 01111 1Доказать, что получаемый так набор действительно покрывающий достаточно просто, авот для доказательства того, что он минимальный нужны нетривиальные комбинаторныефакты, а именно — теорема Ердеша-Ко-Радо.Для всех остальных значений параметров хороших алгоритмов построения минимальныхпокрывающих наборов неизвестно, более того, показано, что построение минимальныхпокрывающих наборов CA(2, k, n), CA(t, k, 2) — NP-полные задачи.Для построения однородных покрывающих наборов для числа значений, не равного 2, идля большого количества параметров проще всего использовать рекурсивные конструкции, спомощью которых набор для большого количества параметров строится из наборов дляменьшего количества.