Генератор случайных чисел на базе неопределённого поведения состояния гонки09.02.2023 09:47

Введение

Генерация случайных чисел окружает нас везде. Любой шаг, дыхание, дуновение ветра, шум кулера, частота мяуканья кошки и т.п. уже может рассматриваться как некая генерация случайности. Так например, на сколько вы контролируете вашу ходьбу? Можете ли вы с точностью до нанометра определить точку опоры? Если не можете, то сама погрешность в неопределённости расстояния начинает становиться для вас генератором случайности.

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

1. Скорость генерации. Наверное является самым явным ограничением в применении. Чем быстрее генерируются случайные числа — тем лучше. И действительно, если само событие генерации будет происходить раз в год, то такой генератор будет являться неприменимым на практике. Например, попытаемся взять первое число июля в следующем году (в определённом регионе) и если на это время выпадут осадки — то сгенерируется бит = 1, иначе бит = 0.

2. Стоимость генерации. Некоторые генераторы могут производить случайную последовательность более быстро, чем другие и иногда за это приходится переплачивать. Так например, мяуканье кошки стоит символические пять рублей (за приобретение) с последующим кормлением (уже зависит от привередливости самой кошки). За счёт этого, вы получаете пушистый генератор случайных чисел, который раз в определённый промежуток времени может мяукать, мурчать, кусать, кушать и т.д. Если записывать каждое действие и ставить в голове некие ставки, что будет происходить дальше, то будут генерироваться случайные числа. Тем не менее, существуют генераторы случайных чисел ещё дороже (и значительно дороже), например, АЭС (атомная электростанция), которая благодаря распаду атомов урана может генерировать очень эффективно случайные числа. Но для этого понадобится ± 22 миллиарда долларов без учёта последующего обслуживания.

3. Уровень случайности. Является самым сложным ограничением в плане своего описания. Существует множество видов генераторов случайных чисел — ГСЧ (генератор случайных чисел), ГПСЧ (генератора псевдо-случайных чисел), КСГПСЧ (криптографически стойкий генератор псевдо-случайных чисел). Последние два являются генераторами псевдослучайных чисел, иными словами генерируемая ими последовательность лишь выглядит как случайная, но на деле является следствием алгоритма. За счёт алгоритмизации, у псевдослучайных генераторов существует три качества: 1) ГПСЧ и КСГПСЧ имеют периоды генерации при достижении которых вся ранее генерируемая последовательность начнёт повторяться; 2) При необходимости можно повторить всю ранее сгенерированную последовательность, если имеется seed/ключ — начальное значение из которого происходит вся последующая генерация; 3) ГПСЧ и КСГПСЧ работают в разы эффективнее большинства представителей ГСЧ, требуя при этом меньше ресурсов. Тем не менее, если говорить о качестве генераторов, то таковое можно изобразить в неравенстве ГСЧ > КСГПСЧ > ГПСЧ.

Разобрав основные ограничения, настало время разобрать тонкости различия ГСЧ и ГПСЧ.

ГСЧ и ГПСЧ

Как было определено ранее, основным отличием ГСЧ от ГПСЧ (в том числе и от КСГПСЧ) является фактор алгоритмизации. Если существует алгоритм, который способен повторить всю генерируемую последовательность, то это значит, что никакой на деле случайности не существует, существует лишь псевдослучайность. Но так ли всё однозначно на первый взгляд?

Вернёмся к примеру с кошкой. Если вы живёте с кошкой достаточно длительное количество времени, то рано или поздно вы начнёте предугадывать большинство её действий/событий, что-то будет являться фактором/причиной её последующих действий/следствий. Ровно такие же условия будут действовать с ураном и распадом атомов, если нам будут известны все возможные неизвестные переменные — местоположение атомов, частиц, их скорости, столкновения и т.д. Чисто теоретически, если это всё станет возможным, то ГСЧ регрессирует до ГПСЧ, где вместо входных бит, на вход будут подаваться факторы/причины всех последующих действий.

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

Рассмотрев возможный регресс ГСЧ до ГПСЧ, становится логичным последующий вопрос, а возможен ли прогресс ГПСЧ до ГСЧ? Чтобы ответить на данный вопрос, необходимо решить противоречивую задачу, при которой сам алгоритм должен стать неоднозначным. При этом алгоритм не должен задействовать сторонние способы генерации случайных и псевдо-случайных чисел, иначе таковой алгоритм станет нечистым и приведёт лишь к композиции. Иными словами, если рассматривать алгоритм как A, то само A должно стать ГСЧ => A=ГСЧ, а не быть выражением A+ГСЧ.

Неопределённые поведения и состояние гонки

Компьютер представляет собой выражение алгоритма. Действие компьютера — есть действие алгоритма. Со стороны математической модели не может существовать такого алгоритма, который бы стал выражением самой случайности. Тем не менее, компьютер != математическая модель, хоть с одной стороны он действительно детерминирован, но с другой стороны, противоречиво он становится также выражением хаотичности собственных процессов.

Неопределённые поведения (UB — undefined behaviour) алгоритмов — это задачи, на базе которых алгоритм может становиться случайным. Тем не менее, одно неопределённое поведение неравно другому, ровно также одно неопределённое поведение может быть бесполезным для ГСЧ, в то время как другое может становиться его основой.

Так например, существуют неопределённые поведения некоторых языков программирования со стороны стандартов, в которых не указывается единственно верное действие, например язык С и выражение i = i++ + ++i;. Решением такого неопределённого поведения становится порядок вычисления со стороны самих компиляторов. Данное UB крайне проблематично применять в ГСЧ, т.к. единожды установив компилятор, все дальнейшие действия уже будут определены.

Но существуют также UB, которые очень сложно или невозможно определить каким-либо стандартом или спецификацией из-за собственной своей особенности. К таким неопределённым поведения относится состояние гонки. Состояние гонки — ситуация, при которой несколько параллельных процессов обращаются одновременно к одной области памяти. Так например, если запущено два параллельных процесса, один из которых будет писать в область памяти число = 0, а другой число = 1, то какое число запишется в эту область памяти? С уверенностью на данный вопрос ответить крайне проблематично, потому что в данном контексте не существует никаких документаций, стандартов, реализаций. Если процессы действительно параллельны и обращаются единовременно к участку памяти, то события равновероятны. На основе данной концепции становится возможным построение ГСЧ. Параллельность можно организовывать разными способами. В моём случае, я буду реализовывать генерацию случайных чисел на двух языках — CUDA C (под GPU) и Golang (под CPU). Разные механизмы языков программирования также могут дать понимание, насколько непредсказуемым остаётся состояние гонки.

Тестирование ГСЧ

При тестировании случайных чисел (случайной последовательности — гаммы) будет использоваться программа rngtest. Но стоит помнить, что таковые тесты способны давать хороший результат только в определении неслучайной последовательности. Тем не менее, доказать, что последовательность случайная — они не могут. Поэтому даже если давать таким тестам псевдослучайную последовательность, то она с большей долей вероятности пройдёт тест, потому как внешние характеристики будут указывать на хорошее распределение.

#include 
#include 
#include 

int main() {
    srand(5);

    const int n = 4096;
    uint8_t gamma[n];

    for (int i = 0; i < n; ++i) {
        gamma[i] = rand()%256;
    }

    fwrite(gamma, sizeof(uint8_t), n, stdout);
}

Результат программы rngtest.

rngtest < gamma.txt                                                                                                                    ✔ 
rngtest 6.16
Copyright (c) 2004 by Henrique de Moraes Holschuh
This is free software; see the source for copying conditions.  There is NO warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

rngtest: starting FIPS tests...
rngtest: entropy source drained
rngtest: bits received from input: 32768
rngtest: FIPS 140-2 successes: 1
rngtest: FIPS 140-2 failures: 0
rngtest: FIPS 140-2(2001-10-10) Monobit: 0
rngtest: FIPS 140-2(2001-10-10) Poker: 0
rngtest: FIPS 140-2(2001-10-10) Runs: 0
rngtest: FIPS 140-2(2001-10-10) Long run: 0
rngtest: FIPS 140-2(2001-10-10) Continuous run: 0
rngtest: input channel speed: (min=6.209; avg=6.209; max=6.209)Gibits/s
rngtest: FIPS tests speed: (min=196.634; avg=196.634; max=196.634)Mibits/s
rngtest: Program run time: 9965 microseconds

Тогда встаёт логичный вопрос — для чего тогда вообще нужен этот инструмент, если он говорит о том, что псевдослучайная последовательность проходит тест на случайность? Это нужно для того, чтобы быть уверенным в правильном распределении бит, чтобы разрабатываемый ГСЧ не оказался слишком слабым. У некоторых ГСЧ существуют недостатки подобия малого диапазона генерации, частых повторений одних и тех же блоков и т.д. На это может rngtest поругаться, а нам это и будет нужно.

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

#include 
#include 

void print_bin(uint8_t num);

int main(int argc, char *argv[]) {
    if (argc != 2) {
        return 1;
    }
	FILE *input = fopen(argv[1], "rb");
    if (input == NULL) {
        return 2;
    }
    int ch;
    while((ch=fgetc(input))!= EOF) {
        print_bin(ch);
    }
    fclose(input);
    printf("\n");
    return 0;
}

void print_bin(uint8_t num) {
	for (int bit = 0x80; bit > 0; bit /= 2) {
		printf("%d",(num&bit)?1:0);
	} 
}

GTX 1650 и CUDA C

Первое что делаем — готовим шаблон самой генерации. Здесь всё крайне легко, мы подаём в качестве аргумента указатель на переменную, куда будет записываться случайное число. В качестве случайного числа мы берём ID блока, который смог перезаписать число и «выиграть» в гонке. Константа MODULE_N равна 2. Будем генерировать бинарные числа. Константу можно изменить на другое число, алгоритм также продолжит функционировать. Тем не менее, MODULE_N должен быть степенью двойки, то-есть равен 2 или 4 или 8 или 16 и т.д. Это необходимо для более равномерного распределения итоговых чисел по битовому пространству.

__global__ void rand_uintN(uint8_t *r) { 
    *r = blockIdx.x % MODULE_N; 
}

Функция вызова rand_uintNs будет выглядить следующим образом. Визуально её можно поделить на две части: 1) генерация сырой гаммы, 2) сжатие сырой гаммы посредством суммирования. Второй пункт приводит к лучшему выравниванию частот встречаемости. Так например, без второго пункта количество нулей часто привышало количество единиц (при MODULE_N=2). Второй пункт приводит к хорошему выравниванию частот встречаемости, в том числе и для разных MODULE_N.

Константа CUDA_BLOCK_N = 4096. В ходе экспериментов, данная константа привела к положительным результатам в тестировании. Связано это с тем, что чем больше будет задействовано параллельности, тем больше будет конечная неопределённость. Тем не менее, тут всё также упирается во время (чем больше CUDA_BLOCK_N, тем дольше ждать). Под каждый блок выделяется только один поток. При экспериментах, потоки ведут себя более конкурентным образом, чем параллельным.

void rand_uintNs(uint8_t *gamma, int n) {
  int num_count = n * MODULE_N;

  uint8_t raw_rand[num_count];
  uint8_t *dev_r;

  memset(raw_rand, 0, sizeof(raw_rand));
  cudaMalloc(&dev_r, sizeof(uint8_t));
  for (int i = 0; i < num_count; i++) {
    rand_uint1<<>>(dev_r);
    cudaMemcpy(raw_rand + i, dev_r, sizeof(uint8_t), cudaMemcpyDeviceToHost);
  }
  cudaFree(dev_r);

  for (int i = 0; i < num_count; i += MODULE_N) {
    int sum = 0;
    for (int j = 0; j < MODULE_2; ++j) {
      sum += raw_rand[i + j];
    }
    gamma[i / MODULE_N] = sum % MODULE_N;
  }
}

Вызов всего этого кода происходит так.

int main(int argc, char *argv[]) {
  const int n = 1024;
  uint1_t gamma[n];
  
  rand_uintNs(gamma, n);

  print_uintNs(gamma, n);
  print_uintNs_count(gamma, n);
  
  return 0;
}

Остальные функции

void print_uintNs(uint1_t *gamma, int n) {
  for (int i = 0; i < n; ++i) {
    printf("%d", gamma[i]);
  }
  printf("\n");
}

void print_uintNs_count(uint1_t *gamma, int n) {
  int count[MODULE_N];
  memset(count, 0, sizeof(count));

  for (int i = 0; i < n; ++i) {
    count[gamma[i]]++;
  }

  for (int i = 0; i < MODULE_N; ++i) {
    printf("[%d] = %d\n", i, count[i]);
  }
}

Результаты

1110110011110010100101000110001110110010100111001110101111000111011001101011110001000101100010001110001111001001111011010000001100001111000011110111101111100010100111011110110111101100001101101000011001111100000000111111010000011100111101100000110000101111010111101001111100111011101000111100110001111100011111001010010110101011011000011010110110000111111000010010111000010100101011101000001110010000011001111000101100011010100001000110010011001011010111011010111111001001110101101000010101101101111100100101001111101100101010011011101011001101111111111011110100000001110111000101010100101100111111110011101001011101110010001100111101110001011010000010011001111110111011100110100101110010011100110011100101000010010011100101000010101001100001101101100001101100011001111100110001010001100101011001101010111011101000110100011001101100100001011000000011000011001010101001000101001000110001011011011101111011010000101100101101100100011011000010011011001000101001001001101101100100111011101000000100111000000010111100010110010110
[0] = 498
[1] = 526

0100100010111010100110100001011101101001010111010101011001011110101011110001000001000110000111001000100010000011111001010010011001100101101010101000111011001010100000000100010100101001010110111101010110111011011001110101010110101011110010100010010110101111000010010001000010000010111100000101011100101010010111010010100011111000101100111011100100011100001011101110000110010011000111010000001100101011001000101010011110011101101001110010110010001011101101111000010100011001111010000010111010100111010101110001101111011010010110111001101110101000001101010101110111100111101011111001011101100110110010000110111011100100011110111101110001110110010111100000100100001100000110111111000101110111001111010100101101011101100010010111110111011010001010001010111110111010111000011110111011111110110111001011011010110001101011111011110100100110101001011100010100100010001110110000001001111100010001110000010101000011101011000001110101000010011010001001110011110100010001111000110001000101001100100101111011000011001000111010111001111001
[0] = 503
[1] = 521

1000001110010010100011110010100001100001011010011101111111011101010000100100100111000000011001111011001110000010000101001011001001110010001100000011110101011000100110111000110111111001010100010000010001010010010000110011101111101000110011001001000001011111111110000100011101011010110111001010110010010110000100101110111011100100010101110001110110101101111100011010001000101111011010000001111111101000100111100101111000111010101100000110110000110000011110010110101100001100111011110110111011110111000101000101100100101001111100011100101101110011111000000111010110110100111001101000111001000110000110111001011001110111111001001010111001001001000100011001010110001000100101011000111001001101100011011101011010011010000110100011100001111111010001101010011101000010010100011000100011010010101100110110011011000010101000000010111111011111110101001111010001100111101100100101000100100010000111100001001011111010101010111001000011101011110010100011010011111111000010100101011001100100010010000010110111000001110010000001010010011101
[0] = 519
[1] = 505

0100011110011010110000000100101110001100110110110101001011110000100011011101111101001001000011101000101011001011010000110110110001111111111011000010110010010110011010010110111001001101100001010100010001110110111000101010011110100010111000100001110011001011011110010110010101111100000000011101100011111100011101001111100010111110001110001000000110101111110101101001110000101101000100101011011101001100100000110000011101100111111000010011111010111000101100000111001100101010001101111111100100111011101001111001000000101100011001001100010111001110101010010001101001111100011111010010111100110000101010010011100100100110000000010001001111000110001110011010000101011010011101000110100000111111101011001000111011110101100000100010001100110100101101110011011100110101001111110110111111000010111010110111001100110010010111100000110111010111100010000110101010110101101100010010011011110110100110011100111110110110111101111011100000011010111000111000010010000001010111101000100100001001010001000010101110010011001000011100101111111110
[0] = 504
[1] = 520

0011001010100110111110000000100011101101010010101001000110010100101011101110000100000100000011110100110111101110111011010000000000001010000000011111101011101101001110001110101101111110000111001110101011000011101101011001100101101101001010100100001001100010100010101100001111100000100000111111100000110110110011010110101010001011011111110111000011100001010110101101010010110101011001001000001000101011011110011010100111000010110001000100110000100111010110001010100111111001111010010111100011010111101101101110001001011001101101100000000010010011101101110011111001110100000000000111010111100101110011010100001011010010110011100110000110101100100010001111001001011010100010111010001111101001111000101010010011110001110001001000100011011011101111101101000111010001001101001100011100110100010011010001100011111111011001000001101001101000000100011111011000000101111110001110000110000010110100111100000110110011000111110010100011111000010011000010100001011100110100101010101101010100100010000101011101110011010100001101010000010110
[0] = 528
[1] = 496

Тесты

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

Таким образом, меняем константу MODULE_N с 2 на 256, чтобы генерировались конкретно байты. Далее, нужно поменять константу n в функции main с 1024 на 4096, т.к. 1024 будет недостаточно для rngtest. После этого, надо написать функцию, которая сохраняет байты, а не числа в виде строки.

void write_uintNs(uint8_t *gamma, int n) {
  fwrite(gamma, sizeof(uint8_t), n, stdout);
}

Запускаем ГСЧ.

$ ./main > gamma.txt

Гамма генерировалась 3 минуты, 10 секунд для CUDA_BLOCK_N=65535 (максимальное количество) и 26 секунд для CUDA_BLOCK_N=4096 (оба значения прошли тест, но если имеется возможность, то лучше использовать конечно консервативный вариант). Относительно неплохое время для ГСЧ, генерирующего в одного 4096 байт. Тем не менее, видеокарта нехило так работала (при 65535), значения в 100%, а ноутбук (на котором все эти вычисления я производил) нагрелся быстро. Ощущение словно биткоин майнил…

И запускаем теперь rngtest, получаем результаты.

$ rngtest < gamma.txt                                                                                                          ✔  3m 10s  
rngtest 6.16
Copyright (c) 2004 by Henrique de Moraes Holschuh
This is free software; see the source for copying conditions.  There is NO warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

rngtest: starting FIPS tests...
rngtest: entropy source drained
rngtest: bits received from input: 32768
rngtest: FIPS 140-2 successes: 1
rngtest: FIPS 140-2 failures: 0
rngtest: FIPS 140-2(2001-10-10) Monobit: 0
rngtest: FIPS 140-2(2001-10-10) Poker: 0
rngtest: FIPS 140-2(2001-10-10) Runs: 0
rngtest: FIPS 140-2(2001-10-10) Long run: 0
rngtest: FIPS 140-2(2001-10-10) Continuous run: 0
rngtest: input channel speed: (min=18.626; avg=18.626; max=18.626)Gibits/s
rngtest: FIPS tests speed: (min=110.892; avg=110.892; max=110.892)Mibits/s
rngtest: Program run time: 232 microseconds

Intel CORE I7 и Golang

Теперь настало время потестировать CPU. В данном примере, у нас будет Intel CORE I7 с 12 ядрами. На Golang’e я постарался запрограммировать примерно такой же код с такими же функциями.

Функции генерации случайного числа на основе состояния гонки. Функция randUintN — эквивалент rand_uintN в CUDA C, функция runRandUintN подобие параллельному запуску функции с видеокарты в несколько блоков.

Константа moduleN = 256, blockN = 256. Последнее значение проходит тесты. Такое число было взято по причине полного покрытия диапазона модуля.

func randUintN(r *uint8, i int) {
	*r = uint8(i % moduleN)
}

func runRandUintN() uint8 {
	x := uint8(0)
	for i := 0; i < blockN; i++ {
		go randUintN(&x, i)
	}
	return x
}

Функция randUintNs — эквивалент функции rand_uintNs в CUDA C примере.

func randUintNs(n int) []uint8 {
	numCount := n * moduleN
	gamma := make([]uint8, n)

	slice := make([]uint8, numCount)
	for i := 0; i < numCount; i++ {
		slice[i] = runRandUintN()
	}

	for i := 0; i < numCount; i += moduleN {
		sum := 0
		for j := 0; j < moduleN; j++ {
			sum += int(slice[i+j])
		}
		gamma[i/moduleN] = uint8(sum % moduleN)
	}

	return gamma
}

Основная функция. В ней я устанавливаю максимальное количество процессоров.

func main() {
	runtime.GOMAXPROCS(runtime.NumCPU())

	const n = 4096
	gamma := randUintNs(n)

	os.Stdout.Write(gamma)
}

Тесты

Запускаем ГСЧ. Генерация гаммы заняло 1 минуту, 6 секунд.

go run ./main.go > gamma.txt

И запускаем теперь rngtest, получаем результаты.

rngtest < gamma.txt                                                                                                          ✔  1m 8s  
rngtest 6.16
Copyright (c) 2004 by Henrique de Moraes Holschuh
This is free software; see the source for copying conditions.  There is NO warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

rngtest: starting FIPS tests...
rngtest: entropy source drained
rngtest: bits received from input: 32768
rngtest: FIPS 140-2 successes: 1
rngtest: FIPS 140-2 failures: 0
rngtest: FIPS 140-2(2001-10-10) Monobit: 0
rngtest: FIPS 140-2(2001-10-10) Poker: 0
rngtest: FIPS 140-2(2001-10-10) Runs: 0
rngtest: FIPS 140-2(2001-10-10) Long run: 0
rngtest: FIPS 140-2(2001-10-10) Continuous run: 0
rngtest: input channel speed: (min=0.000; avg=inf; max=0.000)bits/s
rngtest: FIPS tests speed: (min=123.854; avg=123.854; max=123.854)Mibits/s
rngtest: Program run time: 209 microseconds

В Go потребовалось всего blockN=256 (тесты проходили и с меньшим числом), в то время как в CUDA C потребовалось CUDA_BLOCK_N=4096 для прохождения тестов. Связано всё это с тем, что чем меньше загружены ядра/блоки, тем менее эффективно будет исполняться состояние гонки. Поэтому CUDA C требует большее количество блоков, чтобы происходило неопределённое поведение.

Заключение

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

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

Помимо прочего, использование только одного инструмента тестирования на случайность также может быть недостаточным. В идеальном случае лучше всё это тестировать при помощи нескольких инструментов. Но тут уже можете привести в комментариях какие тесты проходят, какие не проходят. Если некоторые тесты не проходят, то могу посоветовать покрутить параметры CUDA_BLOCK_N © или blockN (Golang), не забывая также выставить MODULE_N и moduleN = 256 (если того требует инструмент тестирования).

Все исходные коды можно посмотреть тут.

Литература

1. GPUs and chaos: a new true random number generator https://www.researchgate.net/profile/Je-Sen-Teh/publication/282478044_GPUs_and_chaos_a_new_true_random_number_generator/links/5c05de93a6fdcc315f9ae0f1/GPUs-and-chaos-a-new-true-random-number-generator.pdf

2. GPUs as high-performance random sources https://ietresearch.onlinelibrary.wiley.com/doi/10.1049/el.2013.4047

© Habrahabr.ru