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