Что такое рандомное тестирование

random testing

Смотреть что такое «random testing» в других словарях:

random testing — atrankinis bandymas statusas T sritis fizika atitikmenys: angl. lot by lot testing; random testing vok. Stichprobenprüfung, f rus. выборочное испытание, n pranc. essai au hasard, m; essai sur prélèvement, m … Fizikos terminų žodynas

Random number table — Random number tables have been used in statistics for tasks such as selected random samples. This was much more effective than manually selecting the random samples (with dice, cards, etc.). Nowadays, tables of random numbers have been replaced… … Wikipedia

random — ran‧dom [ˈrændəm] adjective 1. random sample/​ check/​test etc a sample, check etc in which things or people are chosen without any particular reason or pattern so that they will include a typical mixture of the larger group they represent: • The … Financial and business terms

Random assignment — or random placement is an experimental technique for assigning subjects to different treatments (or no treatment). The thinking behind random assignment is that by randomizing treatment assignment, then the group attributes for the different… … Wikipedia

Random access machine — In computer science, random access machine (RAM) is an abstract machine in the general class of register machines. The RAM is very similar to the counter machine but with the added capability of indirect addressing of its registers. Like the… … Wikipedia

Random number generation — A random number generator (often abbreviated as RNG) is a computational or physical device designed to generate a sequence of numbers or symbols that lack any pattern, i.e. appear random. Computer based systems for random number generation are… … Wikipedia

Random walk hypothesis — The random walk hypothesis is a financial theory stating that stock market prices evolve according to a random walk and thus the prices of the stock market cannot be predicted. It has been described as jibing with the efficient market hypothesis … Wikipedia

Random password generator — A random password generator is software program or hardware device that takes input from a random or pseudo random number generator and automatically generates a password. Random passwords can be generated manually, using simple sources of… … Wikipedia

random — 01. Student pairs are chosen at [random] for the speaking test at the end of each session of the English Language Program. 02. Olympic athletes are subject to [random] drug testing. 03. Several people put their names forward to work on the… … Grammatical examples in English

random — [[t]ræ̱ndəm[/t]] 1) ADJ: usu ADJ n A random sample or method is one in which all the people or things involved have an equal chance of being chosen. The survey used a random sample of two thousand people across England and Wales. The… … English dictionary

Источник

СОДЕРЖАНИЕ

История случайного тестирования

Случайное тестирование оборудования было впервые исследовано Мелвином Брейером в 1971 году, а первоначальная попытка оценить его эффективность была предпринята Пратима и Вишвани Агравал в 1975 году.

Что касается программного обеспечения, Duran и Ntafos исследовали случайное тестирование в 1984 году.

Обзор

Рассмотрим следующую функцию C ++:

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

О случайности

Согласно основополагающей статье Д. Гамлета о случайном тестировании

[..] Техническое, математическое значение термина «случайное тестирование» относится к явному отсутствию «системы» в выборе тестовых данных, так что между различными тестами нет корреляции.

Сильные и слабые стороны

Случайное тестирование хвалят за следующие сильные стороны:

Были описаны следующие недостатки:

Типы случайного тестирования

Что касается ввода

Управляемый против неуправляемого

Реализации

Некоторые инструменты, реализующие случайное тестирование:

Критика

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

Источник

Способы тестирования игр. 6 типов

За последние годы индустрия видеоигр еще больше выросла, поэтому если в 2018 году рынок видеоигр стоил более 130 млрд долларов, то в 2020 году, по оценкам Global Data, он будет стоить более 300 млрд долларов. Этот рост также приводит к росту конкуренции в индустрии видеоигр, поэтому компании по разработке игр должны быть конкурентоспособными в играх, которые они запускают. В настоящее время ассортимент игр, из которых игроки могут выбирать, очень велик, поэтому требования игроков к качеству возросли. Видеоигры должны быть развлекательными и без багов.

Почему необходимо тестирование игр?

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

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

2. Комбинаторное тестирование

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

3. Интуитивное тестирование (ad-hoc)

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

4. Тестирование совместимости

5. Методология “чистой комнаты” (Cleanroom Testing)

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

6. Регрессионное тестирование

В преддверии старта курса Game QA Engineer приглашаем всех желающих на бесплатный демоурок в рамках которого вы узнаете как создаются игры, в чем особенности их тестирования. Почему в играх особенные сроки? Подробно рассмотрим как тестировать баланс и почему автоматизация не спасает? А также будем практиковаться и протестируем анимацию «Лепрекон».

Источник

Что такое ad-hoc тестирование?

В этой статье мы разберем, что такое ad-hoc тестирование и какие оно имеет преимущества и недостатки. Также рассмотрим best practices в этом виде тестирования.

Что из себя представляет ad-hoc тестирование?

«Ad hoc» переводится с английского как «случайный, непродуманный, спонтанный». Такое тестирование также называют «случайным тестированием» или «monkey testing» («обезьяньим тестированием»).

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

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

Самый интересный аспект ad-hoc тестирования — отсутствие каких-либо методик продумывания тестов. Благодаря этому можно найти баги, которые обычно проскакивают незамеченными. Но, вместе с тем, воспроизвести это тестирование сложно, поскольку нет ни написанных тест-кейсов, ни документации.

Успех ad-hoc тестирования полностью зависит от креативности и настойчивости тестировщика, а порой и от чистой удачи.

Виды ad-hoc тестирования

1. Buddy Testing

Суть Buddy Testing в том, что как минимум два «компаньона» (в переводе с английского buddy — приятель, компаньон) одновременно пытаются выявить баги в одном и том же модуле.

Buddy Testing можно считать комбинацией системного и модульного тестирования. Оно проводится после юнит-тестирования модуля.

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

2. Monkey Testing

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

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

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

3. Парное тестирование

Парное тестирование похоже на Buddy Testing, но здесь над модулем работают два тестировщика, а не тестировщик и разработчик. Кроме того, Buddy Testing — комбинация модульного и системного тестирования, а парное тестирование — чисто модульное.

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

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

Когда стоит проводить ad-hoc тестирование

Ad-hoc testing бывает полезным, когда у вас нет времени на длительный и всеобъемлющий процесс тестирования, требующий подготовки требований и тест-кейсов.

Идеальное время для ad-hoc тестирования — после проведения всех формальных тестов. Но его также можно проводить и в процессе разработки, и после его завершения.

Стоит отметить и пару сценариев, при которых ad-hoc тестирование не рекомендуется:

Преимущества ad-hoc тестирования

Основное преимущество ad-hoc тестирования — возможность выявить баги, которые остались бы незамеченными при других проверках. А поскольку для такого тестирования не нужно ничего планировать и структурировать, оно экономит много времени.

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

Такое тестирование могут проводить и сами разработчики ПО.

Недостатки ad-hoc тестирования

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

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

Также ad-hoc тестирование не гарантирует, что все ошибки будут найдены. Успех этого тестирования вообще очень зависит от знаний и навыков тестировщика.

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

Best Practices в ad-hoc тестировании

Если тесты проводятся неправильно, время тратится впустую. Поэтому для успешного проведения ad-hoc тестирования важно знать, как оптимизировать процесс.

Следующие best practices гарантируют, что время на тестирование будет потрачено с умом, а шансы на успех будут максимальными.

Ознакомьтесь со спецификацией

QA-специалист, проводящий ad-hoc тестирование, должен хорошо знать тестируемое приложение и его основные функции. Только благодаря этому он сможет «угадывать», где скрываются ошибки и баги.

Определите наиболее «подозрительные» части приложения

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

Функции, к которым имеет доступ конечный пользователь, должны быть в приоритете

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

Сформулируйте план тестирования в свободной форме

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

Используйте подходящие инструменты

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

Итоги

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

Источник

Статистическая проверка случайности двоичных последовательностей методами NIST

Любой, кто, так или иначе, сталкивался с криптографией, знает, что без генераторов случайных чисел в этом деле не обойтись. Одно из возможных применений таких генераторов, например, – генерация ключей. Но не каждый при этом задумывается, а насколько «хорош» тот или иной генератор. А если и задумывался, то сталкивался с тем фактом, что в мире не существует какого-либо единственного «официального» набора критериев, который бы оценивал, насколько данные случайные числа применимы именно для данной области криптографии. Если последовательность случайных чисел предсказуема, то даже самый стойкий алгоритм шифрования, в котором данная последовательность будет использоваться, оказывается, уязвим — например, резко уменьшается пространство возможных ключей, которые необходимо «перебрать» злоумышленнику для получения некоторой информации, с помощью которой он сможет «взломать» всю систему. К счастью, разные организации все же пытаются навести здесь порядок, в частности, американский институт по стандартам NIST разработал набор тестов для оценки случайности последовательности чисел. О них и пойдет речь в данной статье. Но сначала — немного теории (постараюсь изложить не нудно).

Случайные двоичные последовательности

Во­-первых, под генерацией случайных чисел подразумевается получение последовательности из двоичных знаков 0 и 1, а не байтами, как бы ни хотелось программистам. Идеальным подобным генератором является подбрасывание «идеальной» монеты (ровная монета, у которой вероятности выпадения каждой из сторон одинаковы), которую бы подбрасывали столько раз, сколько нужно, но проблема в том, ничего идеального не сущ ествует, а производительность такого генератора оставляла бы желать лучшего (один подрос монеты = одному биту). Тем не менее, все тесты, описываемые ниже, оценивают, насколько исследуемый генератор случайных чисел «похож» или «не похож» на воображаемую идеальную монету (не по скорости получения «случайных» знаков, а их «качества»).

Во­-вторых, все генераторы случайных чисел делятся на 2 типа —истинно случайные — физические генераторы/датчики случайных чисел (ДСЧ/ФДСЧ) и псевдо­случайные – программные датчики/генераторы случайных чисел (ПДСЧ). Первые принимают на вход некий случайный бесконечный процесс, а на выходе дают бесконечную (зависит от времени наблюдения) последовательность 0 и 1. Вторые представляют собой заданную разработчиком детерминированную функцию, которая инициализируется т. н. зерном, после чего также на выходе выдает последовательность 0 и 1. Зная это зерно, можно предсказать всю последовательность. Хороший ПДСЧ — этот тот, для которого невозможно предсказать последующие значения, имея всю историю предыдущих значений, не имея зерна. Это свойство называется прямой непредсказуемостью. Есть еще обратная непредсказуемость — невозможность вычислить зерно, зная любое количество генерируемых значений.

Казалось бы, проще всего взять истинно случайные/физические ДСЧ и не думать ни о какой предсказуемости. Однако тут есть проблемы:

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

Нулевая и альтернативная гипотезы

В основе тестов лежит понятие нулевой гипотезы. Попробую объяснить, что это. Допустим, мы набрали некую статистическую информацию. Например, пусть это будет количество людей, заболевших раком легких в группе из 1000 человек. И пусть известно, что некоторые люди из этой группы являются курильщиками, а другие нет, причем известно, какие конкретно. Стоит следующая задача: понять, есть ли взаимосвязь между курением и заболеванием. Нулевая гипотеза — это предположение, что между двумя фактами отсутствует какая-либо взаимосвязь. В нашем примере это предположение, что курение не вызывает рак легких. Существует также альтернативная гипотеза, которая опровергает нулевую гипотезу: т.е. между явлениями взаимосвязь существует (курение вызывает рак легких). Если переходить к терминам случайных чисел, то за нулевую гипотезу принимается предположение, что последовательность является истинно случайной (знаки которой появляются равновероятно и независимо друг от друга). Следовательно, если нулевая гипотеза верна, то наш генератор производит достаточно «хорошие» случайные числа.

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

Вероятность ошибки первого рода называют уровнем статистической значимости и обозначают как α. Т.е. α — это вероятность отбраковать «хорошую» случайную последовательность. Это значение определяется областью применения. В криптографии принято α брать от 0.001 до 0.01.

В каждом тесте вычисляется т.н. P-значение: это вероятность того, что подопытный генератор произведет последовательность не хуже, чем гипотетический истинный. Если P­значение = 1, то наша последовательность идеально случайна, а если оно = 0, то последовательность полностью предсказуема. В дальнейшем P-значение сравнивается с α, и если она больше α, то нулевая гипотеза принимается и последовательность признается случайной. В противном случае — отбраковывается.

Частотный блочный тест

Этот тест делается на основе предыдущего, только теперь значения пропорции «1»/«0» для каждого блока анализируются методом Хи-квадрат. Ясно, что это соотношение должно быть приблизительно равным 1.

Например, пусть дана последовательность 0110011010. Разобъем ее на блоки по 3 бита («бесхозный» 0 на конце отброшен):
011 001 101

Посчитаем пропорции π_i для каждого блока: π₁ = 2/3, π₂ = 1/3, π₃ = 1/3. Далее вычисляем статистику по методу Хи-квадрат c N степенями свободы (здесь N — количество блоков):

Вычислим P-значение через специальную функцию Q:

Q — это т.н. неполная верхняя гамма-функция, определяемая как:

При этом функция Г — стандартная гамма-функция:

Последовательность считается случайной, если P-значение > 0.01. Рекомендуется анализировать последовательности длиной не менее 100 бит, а также должны выполняться соотношения M >= 20, M > 0.01n и N 0.1, а значит идем дальше.

Вычисляем суммарное число знакоперемен V:

где если , или в противном случае.

Вычисляем P-значение через функцию ошибок:

Если результат >= 0.01 (как в нашем примере), то последовательность признается случайной.

Тест на самую длинную последовательность из единиц в блоке

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

Какую взять длину блока? NIST рекомендует несколько опорных значений, как разбивать на блоки:

Пусть дана последовательность:
11001100 00010101 01101100 01001100 11100000 00000010
01001101 01010001 00010011 11010110 10000000 11010111
11001100 11100110 11011000 10110010

Разобьем ее на блоки по 8 бит (M=8), после чего посчитаем максимальную последовательность из единиц для каждого блока:

Далее считаем статистику по разным длинам на основе следующей таблицы:

Как пользоваться этой таблицей: у нас M = 8, поэтому смотрим только один соответствующий столбец. Считаем v_i:
v₀ = <кол-во блоков с макс. длиной ≤ 1 > = 4
v₁ = <кол-во блоков с макс. длиной = 2 > = 9
v₂ = <кол-во блоков с макс. длиной = 3 > = 3
v₃ = <кол-во блоков с макс. длиной ≥ 4 > = 0

Вычисляем Хи-квадрат:

Где значения K и R берутся исходя из такой таблицы:

Теоретические вероятности π_i задаются константами. Например, для K=3 и M=8 рекомендуется взять π₀ = 0.2148, π₁ = 0.3672, π₂ = 0.2305, π₃ = 0.1875. (Значения для других K и M приведены в [2]).

Далее вычисляем P-значение:

Если оно > 0.01, как в нашем примере, то последовательность считается достаточно случайной.

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

Тест анализирует матрицы, которые составлены из исходной последовательности, а именно — рассчитывает ранги непересекающихся подматриц, построенных из исходной двоичной последовательности. В основе тест лежат исследования Коваленко [6], где ученый исследовал случайные матрицы, состоящие из 0 и 1. Он показал, что можно спрогнозировать вероятности того, что матрица M x Q будем иметь ранг R, где R = 0,1,2. min(M,Q). Эти вероятности равны:

NIST рекомендует брать M = Q = 32, а также, чтобы длина последовательности n = M^2 * N. Но мы для примера возьмем M = Q = 3. Далее нужны вероятности P_M, P_M-1 и P_M-2. С небольшой долей погрешности формулу можно упростить, и тогда эти вероятности равны:

Итак, пусть дана последовательность 01011001001010101101. «Раскладываем» ее по матрицам — хватило на 2 матрицы:

Вычисляем P-значение:

Если результат > 0.01, то последовательность признается случайной. NIST рекомендует, чтобы общая длина последовательности была >= 38MQ.

Спектральный тест

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

Как нетрудно догадаться, для представления последовательности в виде суммы периодических составляющих будем использовать дискретное преобразование Фурье. Оно выглядит так:

Вы спросите, а где же здесь периодичности? Ответ — экспоненту можно выразить через тригонометрические функции:

Для нашего теста интересны не фазы, а абсолютные значения амплитуд. И если мы вычислим эти абсолютные значения, то окажется, что они симметричны (это общеизвестный факт при переходе от комплексных значений к вещественным), поэтому для дальнейшего рассмотрения мы возьмём только половину этих значений (от 0 до n/2) — остальные не несут дополнительной информации.

Вот как разложение Фурье можно сделать, например, в программе GNU Octave:
Видим, что наблюдается симметрия. Поэтому нам хватит и пять значений: 0, 2, 4.4721, 2, 4.4721.

Далее вычисляем граничное значение по формуле

Оно означает, что если последовательность истинно случайная, то 95% пиков не должны превышать эту границу.

Вычислим предельное число пиков, которых должно быть меньше, чем T:

Далее смотрим на результат разложения и видим, что все наши 4 пика меньше граничного значения. Далее оцениваем эту разницу:

Вычисляем P-значение:

Оно получилось >0.01, поэтому гипотеза о случайности принимается. И да, для теста рекомендуется брать не менее 1000 бит.

Тест на встречающиеся непересекающиеся шаблоны

Подопытная последовательность разбивается на блоки одинаковой длины. Например:
1010010010 1110010110

В каждом блоке будем искать какой-нибудь шаблон, например «001». Слово непересекающиеся означает, что в случае нахождения шаблона внутри последовательности, следующее сравнение не будет захватывать ни одного бита найденного шаблона. В результате поиска для каждого i-го блока будет найдено число W_i, равное кол-ву найденных случаев.

Итак, для наших блоков W₁ = 2 и W₂ = 1:
101 001 001 0
111 001 0110

Вычислим математические ожидание и дисперсию, как если бы наша последовательность была подлинно случайна. Ниже приведены формулы. Здесь N = 2 (кол-во блоков), M = 10 (длина блока), m = 3 (длина образца).

Вычислим итоговое P-значение через неполную гамма-функцию:

Видим, что P-значение > 0.1, а значит, последовательность достаточно случайна.

Мы оценили только один шаблон. На самом деле нужно проверить все комбинации шаблонов, да и ещё к тому же для разной длины этих шаблонов. Сколько того и другого нужно, определяется исходя из конкретных требований, но обычно m берут 9 или 10. Чтобы получить осмысленные результаты, следует брать N 0.01 * n.

Тест на встречающиеся пересекающиеся шаблоны

Этот тест отличается от предыдущего тем, что при нахождении шаблона «окно» поиска сдвигается не на длину шаблона, а только на 1 бит. Чтобы не загромождать статью, мы не станем приводить пример расчета по этому методу. Он полностью аналогичен.

Универсальный тест Мауэра

Тест оценивает, насколько «далеко» друг от друга отстоят шаблоны внутри последовательности. Смысл теста в том, чтобы понять, насколько последовательность сжимаема (конечно, имеется в виду сжатие без потерь). Чем более сжимаема последовательность, тем она менее случайна. Алгоритм этого теста весьма громоздкий для Хабра-формата, поэтому опустим его.

Тест на линейную сложность

В основе теста лежит предположение, что подопытная последовательность была получена через регистр сдвига с линейной обратной связью (или LFSR, Linear feedback shift register). Это общеизвестный метод получения бесконечной последовательности: тут каждый следующий бит получается как некая функция бит, «сидящих» в регистре. Минус LFSR в том, что он всегда имеет конечный период, т.е. последовательность обязательно будет рано или поздно повторяться. Чем больше длина LFSR, тем лучше случайная последовательность.

Исходная последовательность разбивается на равные блоки длиной M. Далее для каждого блока с помощью алгоритма Берлекэмпа — Мэсси [10] находится его линейная сложность (L_i), т.е. длина LFSR. Затем для всех найденных L_i оценивается распределение Хи-квадрат со 6 степенями свободы. Покажем на примере.

Пусть дан блок 1101011110001 (M=13), для которого алгоритм Берлекэмпа — Мэсси выдал L = 4. Убедимся, что это так. Действительно, нетрудно догадаться, что для этого блока каждый следующий бит получается как сумма (по модулю 2) 1-го и 2-го бита (нумерация с 1):
x₅ = x₁ + x₂ = 1 + 1 = 0
x₆ = x₂ + x₃ = 1 + 0 = 1
x₇ = x₃ + x₄ = 1 + 0 = 1
и.т.д.

Вычисляем математическое ожидание по формуле

Для каждого блока вычисляем значение T_i:

Имеем 7 возможных исходов, а значит вычисляем Хи-квадрат с числом степеней свободы 7 — 1 = 6:

Вероятности π_i в тесте жестко заданы и равны соответственно: 0.010417, 0.03125, 0.125, 0.5, 0.25, 0.0625, 0.020833. (π_i для большего числа степеней свободы можно вычислить по формулам, данным в [2]).

Вычислить P-значение:

Если результат получился > 0.01, то последовательность признается случайной. Для реальных тестов рекомендуется брать n >= 10^6 и М в пределах от 500 до 5000.

Тест на подпоследовательности

В основе теста лежат работы [8] и [11]. Там описываются 2 показателя (∇ψ 2 _m и ∇ 2 ψ 2 _m), которые характеризуют, насколько частоты появления образцов соответствуют этим же частотам для истинно случайной последовательности. Покажем алгоритм на примере.

Пусть дана последовательность 0011011101 длиной n = 10, а также m = 3.

Подставляем:

Итоговые значения:

Итак, оба P-значения > 0.01, а значит последовательность признается случайной.

Приблизительная энтропия

Метод приблизительной энтропии (Approximate Entropy) изначально проявил себя в медицине, особенно в кардиологии. Вообще, согласно классическому определению, энтропия является мерой хаоса: чем она выше, тем более непредсказуемые явления. Хорошо это или плохо, зависит от контекста. Для случайных последовательностей, используемых в криптографии, важно иметь высокую энтропию — это значит, что будет сложно предсказать последующие случайные биты на основе того, что уже имеем. А вот, например, если за случайную величину взять сердечный ритм, измеряемый с заданным периодом, то ситуация иная: есть множество исследований (например, [12]), доказывающих, что чем ниже вариабельность сердечных ритмов, тем реже вероятность инфарктов и прочих неприятных явлений. Очевидно, что сердце человека не может биться с постоянной частотой. Однако одни умирают от инфарктов, а другие нет. Поэтому метод приблизительной энтропии позволяет оценить, насколько с виду случайные явления действительно случайны.

Конкретно, тест вычисляет частоты появления всевозможных образцов заданной длины (m), а затем аналогичные частоты, но уже для образцов длиной m+1. Затем распределение частот сравнивается с эталонным распределением Хи-квадрат. Как и в предыдущем тесте, образцы могут перекрываться.

Покажем на примере. Пусть дана последовательность 0100110101 (длина n = 10), и возьмём m = 3.

Для начала дополним последовательность первыми m-1 битами. Получится 0100110101 01.

Посчитаем встречаемость каждого из 8 всевозможных блоков. Получится:
k₀₀₀ = 0, k₀₀₁ = 1, k₀₁₀ = 3, k₀₁₁ = 1, k₁₀₀ = 1, k₁₀₁ = 3, k₁₁₀ = 1, k₁₁₁ = 0.

Посчитаем соответствующие частоты по формуле C_i m = k_i / n:
C₀₀₀ 3 = 0, C₀₀₁ 3 = 0.1, C₀₁₀ 3 = 0.3, C₀₁₁ 3 = 0.1, C₁₀₀ 3 = 0.1, C₁₀₁ 3 = 0.3, C₁₁₀ 3 = 0.1, C₁₁₁ 3 = 0.

Аналогичным образом считаем частоты появления подблоков длиной m+1=4. Их уже 2 4 =16:
С₀₀₁₁ 4 = С₀₁₀₀ 4 = С₀₁₁₀ 4 = С₁₀₀₁ 4 = С₁₁₀₁ 4 = 0.1, С₀₁₀₁ 4 = 0.2, С₁₀₁₀ 4 = 0.3. Остальные частоты = 0.

Вычисляем φ 3 и φ 4 (заметьте, что здесь натуральный логарифм):

Вычисляем Хи-квадрат:

P-значение:

Получившееся значение > 0.01, а значит последовательность признается случайной.

Тест кумулятивных сумм

Далее находится число z = максимум среди этих сумм.

Наконец, считается P-значение по следующей формуле (её вывод см. в [9]):

Где:

Здесь Φ — функция распределения стандартной нормальной случайной величины. Напоминаем, что стандартное нормальное распределение — это всем известное гауссово распределение (в форме колокола), у которого математическое ожидание 0 и дисперсия 1. Выглядит так:

Если получившееся P-значение > 0.01, то последовательность признается случайной.

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

Тест на произвольные отклонения

Где v_k(x) — значения в таблице для данного состояния, J — количество циклов (у нас 3), π_k(x) — вероятности того, что состояние «x» возникнет k раз в подлинно случайном распределении (они известны).

Например, для x=1 получается:

Значения π для остальных x смотрите в [2].

Вычисляем P-значение:

Если оно > 0.01, то делается вывод о случайности. В итоге необходимо вычислить 8 P-значений. Какие-то могут оказаться больше 0.01, какие-то — меньше. В таком случае финальное решение о последовательности делается на основе других тестов.

Разновидность теста на произвольные отклонения

Ниже привожу список источников, которые можно посмотреть, если хочется углубиться в тему:

Источник