Закрыть

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

Автор: Васин Алексей
Опубликовано 26.08.2009 в 11:13
Раздел: Теория вероятности
Теги:

Иногда очень остро встает вопрос о случайности используемых данных. Во многих программах вы используете датчики случайных (точнее псевдослучайных) чисел. Зачастую это линейный конгруэнтный датчик случайных чисел. А на сколько хорош датчик случайных чисел используемый в вашей программе?

В этой заметке я хочу рассказать одном из статистических тестов входящих в пакет исследования NIST для датчиков случайных чисел. Это спектральный тест на основе дискретного преобразования Фурье. Заметка представляет собой «вольный» перевод оригинальной документации с некоторыми исправлениями. К материалу прилагается практическая реализация этого теста.

Известно, что проблема генерации случайной последовательности с произвольным законом распределения вероятностей сводится к проблеме генерации так называемой равномерно распределенной случайной последовательности (РРСП), или, как ее часто называют в криптографических приложениях, «чисто случайной» последовательности.

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

Тест исследует последовательность бит с целью выявления периодических составляющих в псевдослучайной последовательности (ПСП).

Параметрами теста выступают:

$n$ - длина ПСП (бит), должна быть кратна $2^k$,

$x_i$ - биты ПСП, $i = 1 ,…, n$

Итак, давайте рассмотрим алгоритм выполнения теста.

1. ПСП преобразуется к виду: $x_i = 2x_i – 1$, для $i = 1,2,…,n$;

2. Определяются параметры:

$T = \sqrt{2.995732274 n}$ – верхняя граница значений спектральных компонент c’; Следует заметить, что в оригинальной документации NIST вместо числа 2.995… дано число 3, но оно было уточнено.

$N_0 = 0.95 n/2$ – ожидаемое число значений спектральных компонент c’ в интервале $[0; T);$

3. Вычисляется быстрое дискретное преобразование Фурье: c = БДПФ(x);

4. вычисляется модуль спектра: $c_i' = |c_i| = \sqrt{Re(ci)^2+Im(ci)^2}, i = 1,2, ..., n/2$.

5. определяется число N_1 значений спектральных компонент c’, принадлежащих диапазону: $c_i' \in [0; T)$

6. определяется значение вероятности $Pv: Pv = 2 (1-Ф(|N_1 - N_0|/\sqrt{0.25 * 0.95 * 0.05 * n} ))

Заметим, что до проведения теста выбирается критическое значение $a$ и считается, что последовательность «хорошая», если вероятность значимости $Pv$ попала в интервал от $a$ до $1-a$. Как правило выбирают a довольно меленьким, например, 0.005.Математическая основа теста довольно проста. Т.к. последовательность спектральных компонент обладает свойством симметрии, то можно ограничится анализом первой половины спектра: ci, i = 1,2, ...,n/2 . В предположении о том, что последовательность случайна, ограничиваем амплитуды спектра ci уровнем $T = \sqrt{2.995732274 n}$. Для случайной последовательности более 95% компонент спектра должны быть ниже уровня T. Уровень Т здесь определен для биномиального распределения элементов последовательности.

Покажем наглядно, работу теста.

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

ПСП1 – сгенерирована «хорошим» генератором ПСП.

ПСП2 – сгенерирована генератором ПСП с дефектом, порождающим периодические подпоследовательности внутри ПСП.

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

Рисунок 1 – Спектр ПСП1 (не обнаружено периодических составляющих), результат тестирования – удовлетворительный, $Pv = 0.8077$.

Рисунок 2 – Спектр ПСП2 (периодические составляющие ярко выражены), результат тестирования – неудовлетворительный, $Pv = 0.0001$

На практике при исследовании ПСП статистический тест выполняют многократно.

При этом получают целый набор статистик $d = |N_1 - N_0|/\sqrt{0.25 * 0.95 * 0.05 * n}$ и вероятностей значимости Pv. Эти две последовательности дополнительно исследуются на соответствие распределению теста и на равномерность в [0,1] соответственно при помощи статистических критериев.

В завершение статьи привожу код на Delphi для вычисления числа $N_1$. Конечно, есть оригинальная реализация от NIST, но в моей проведены некоторые оптимизации, позволяющие немного сократить время счета. Модуль содержит 2 функции: fft – Выполняет быстрое преобразование Фурье, и DFT_Test – собственно сам тест Фурье. На вход последней функции подается массив из байт, каждый равен 0 или 1, и длинна этого массива.Теоретически данным модулем можно обрабатывать последовательности до $2^32$. Однако на практике я больше чем $2^20$ не использовал из-за увеличения времени вычислений.

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

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

Комментарии (6)

  • KvanTTT Koch 2010-10-21  [ ответить ]

    А что за формула Ф в опеределении Pv?

  • Васин Алексей 2010-10-21  [ ответить ]

    Ф - стандартное обозначение для функции нормального распределения c математическим ожиданием 0 и  дисперсией 1 - тот самый колокольчик N(0,1)

  • KvanTTT Koch 2010-10-22  [ ответить ]

    Ну скорее не колокольчик, а знак типа интеграла)) Но дело в том, что тогда может принимать значения [0;2], хотя должна по идее [0;1]. И еще получается, что d получается слишком большое и поэтому Ф = 0. Это из-за неправильно рассчитанного N1? N1 - это фактическое количество всех ci' в интервале [0; T) ?

  • KvanTTT Koch 2010-10-22  [ ответить ]

    Ошибся: Ф = не нулю, а Ф = 1

  • Васин Алексей 2010-10-24  [ ответить ]

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

    Если вы внимательно посмотрите на выражение $d=∣N1-N0∣/sqrt{0.25*0.95*0.05*n}$, то оно принимает только неотрицательные значения.

    Таким образом, $Ф(d)$ в интервале [0.5,1], $1-Ф(d)$ в интервале [0,0.5], ну и Pv как и положено от нуля до 1.

    Пункт 5 исправил. Про $N_1$ все верно.

  • Васин Алексей 2010-10-24  [ ответить ]

    Кстати. Я на официальном сайте Ниста не смотре, но вроде этот тест они исключили из пакета статистических тестов. Даже по собственному опыту скажу. Тест давал приемлемые результаты, если выборок было до 10000. Если же тестируется скажем около $10^6$ или больше последовательностей, то тест всегда дает плохие результаты. Я думаю это связано с тем, что распределение в тесте приближенное.

    И во всех документах NIST у них обем тестирования не превышал 10000.

    Поэтому, мое мнение, что тест можно использовать только при небольшом объеме выборок до 10000.

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

Комментировать могут только зарегистрированные пользователи

Подразделы
Новые статьи
  • 2017-07-09 14:11:58 Robertfoere » трейдинг

    Я получил бесплатно $100 для обу...

  • 2017-07-09 13:54:28 Robertfoere » forex

    Я получил бесплатно $100 для ...

  • 2017-07-09 07:21:33 Robertfoere » trader

    Я получил бесплатно $100 для обу...

  • 2017-07-09 07:03:20 Robertfoere » broker

    Я получил бесплатно $100 для обу...

  • 2017-07-06 14:45:03 Robertfoere » stock exchange

    Я получил бесплатно $100 для обу...

Aрхив статей