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

       

Максимизация числа различных подслов


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

В слове длины N имеется всего

N + (N-1) + (N-2) + … + 2 + 1 = N(N+1)/2                                 (*)

подслов (слагаемые соответствуют подсловам длины 1, 2 и т.д.). Можно попытаться максимизировать количество разных подслов, сделав все подслова какой-то длины k различными. При этом все подслова большей длины тоже автоматически будут различны, т.е. мы получим как минимум (N-k+1)(N-k+2)/2 разных подслов длины k и больше. Значение k при этом можно выбрать так, чтобы максимизировать полученное выражение при фиксированном N, т.е. как можно меньше.

При этом имеется всего mk разных m-слов длины k, а если они все реализуются как подслова одного слова, длина этого слова должна быть не меньше mk+k-1. Предположим, что существуют такие «наиболее плотные» слова, что все их подслова длины k различны и в то же время включают в себя все возможные m-слова длины k, и они нам известны. Тогда для заданного N можно найти минимальное k, такое, что N ? mk+k-1, т.е. m(k-1)+(k-1)-1 < N ? mk+k-1, и в качестве искомого слова взять начало длины N соответствующего «наиболее плотного» слова. Это гарантирует различие всех подслов длины k в нем.

Для того, чтобы еще увеличить количество разных подслов в нашем слове, можно попытаться найти «наиболее плотное» слово для (k-1), которое продолжается в «наиболее плотное» слово для k. Взяв начало этого последнего мы получим наилучший результат — в полученном слове длины N все подслова минимально возможной длины k различны, и в то же время в нем в качестве подслов содержатся все возможные слова длины (k-1) и, соответственно, меньшие — все слагаемые в формуле (*) имеют максимальные возможные значения.

Осталось выяснить два момента.

  • Существуют ли «наиболее плотные» слова для всех m и k, и если это так, можно ли их продолжать до «наиболее плотных» слов для m и (k+1)? Есть ли достаточно эффективные алгоритмы для построения таких слов?
  • Какой тестовой гипотезе, т.е.
    какому допущению относительно свойств тестируемой системы, соответствует выбранное понимание «наиболее разнообразного» поведения слова? Для какого рода систем этот подход дает действительно оптимальное покрытие различных возможных ситуаций?
Ответу на первый вопрос посвящен весь следующий раздел. В рамках данного раздела проще ответить на второй. Такой подход к построению тестов базируется на предположении о том, что поведение тестируемой системы целиком определяется последними k обращениями. При этом выбирая тестовую последовательность, содержащую как можно больше различных подпоследовательностей длины k, мы покрываем наибольшее количество различных «поведений» системы. В качестве реального примера такой системы можно привести кодовый замок, реагирующий на последние набранные k (обычно 4 или 5) цифр (автор сам пользовался такими замками, см. также статью [4], посвященную стратегии эффективного вскрытия замка в отеле Baltimore Hilton). Дополнительное условие, обеспечивающее содержание в тестовой последовательности всех возможных слов длины (k-1), по отношению к этой гипотезе является некоторой необязательной «оптимизацией».

Содержание раздела