Модернизация PCG64 с помощью PCG64DXSM

Затронет ли это меня?

Если

1. вы используете только один экземпляр Generator,
2. вы используете только RandomState или функции в numpy.random,
3. вы используете только метод PCG64.jumped для генерации параллельных потоков,
4. вы явно используете BitGenerator , отличную от PCG64,

то эта уязвимость вас совершенно не коснется. Продолжайте работу.

Если вы используете умеренное количество параллельных потоков, созданных с помощью default_rng или SeedSequence.spawn, в тысячах, то вероятность обнаружения этой уязвимости незначительно мала. Вы можете продолжать комфортно использовать PCG64.

Если вы используете очень большое количество параллельных потоков, в миллионах, и извлекаете большое количество чисел из каждого, то вероятность обнаружения этой уязвимости может стать существенной, хотя и остается небольшой. Примером такого использования может служить очень большая распределенная задача обучения с подкреплением с миллионами длинных игр Монте-Карло, каждая из которых генерирует миллиарды случайных чисел. В таких случаях следует рассмотреть явное использование PCG64DXSM или другого современного BitGenerator, такого как SFC64 или Philox, но маловероятно, что какие-либо старые результаты, которые вы могли рассчитать, неверны. В любом случае, уязвимость представляет собой вид парадокса дней рождения. То есть, пара параллельных потоков из миллионов, рассматриваемых вместе, может не пройти строгий набор статистических тестов на случайность. Остальные миллионы потоков будут в полном порядке, и влияние плохой пары в целом вычислении, очень вероятно, будет затенено остальными потоками в большинстве приложений.

Технические детали

Как и многие алгоритмы генерации псевдослучайных чисел (PRNG), PCG64 построен из функции перехода, которая продвигает состояние 128 бит, и функции вывода, которая смешивает состояние 128 бит в 64-битовое целое число для вывода. Одним из руководящих принципов проектирования семейства PRNG PCG является баланс между вычислительной сложностью (и силой псевдослучайности) функции перехода и функции вывода. Функция перехода является 128-битным линейным конгруэнтным генератором (LCG), который состоит из умножения 128-битного состояния на фиксированную константу умножения, а затем добавления выбранного пользователем приращения в 128-битном модульном арифметике. LCG — это хорошо изученные PRNG с известными слабыми местами, хотя 128-битные LCG достаточно велики, чтобы пройти строгие статистические тесты самостоятельно, только с тривиальной функцией вывода. Функция вывода PCG64 предназначена для устранения некоторых из этих известных недостатков, выполняя «достаточно» перемешивания бит для улучшения статистических свойств без добавления чрезмерной вычислительной сложности.

Один из этих известных недостатков заключается в том, что продвижение состояния LCG на шаги, являющиеся степенью двойки (bg.advance(2**N)), оставит нижние N биты идентичными состоянию, которое только что было оставлено. Для единственного потока, полученного последовательно, это имеет мало последствий. Остальные \(128-N\) биты обеспечивают достаточную псевдослучайность, которая будет смешана для любой практической N , которая может быть наблюдаема в одном потоке, поэтому об этом не нужно беспокоиться, если вы используете только один поток в своем приложении. Аналогично, метод PCG64.jumped использует тщательно выбранное количество шагов, чтобы избежать создания таких коллизий. Однако, как только вы начинаете создавать «случайно инициализированные» параллельные потоки, либо используя энтропию ОС путем многократного вызова default_rng, или используя SeedSequence.spawn, то мы должны рассмотреть, сколько младших битов нужно «совпасть», чтобы создать плохую пару потоков, и затем оценить вероятность создания такой коллизии. Эмпирически было установлено, что если один разделяет младшие 58 битов состояния и разделяет приращение, то пара потоков при интерполяции будет не удовлетворять тесты PractRand за разумное время после получения нескольких гигабайт данных. Следуя стандартным расчетам парадокса дня рождения для коллизии 58 бит, мы можем видеть, что мы можем создать \(2^{29}\), или около полумиллиарда, потоков, когда вероятность такой коллизии становится высокой. Полумиллиард потоков довольно много, и количество данных, которые каждый поток должен получить, прежде чем статистические корреляции станут заметными даже для строгих PractRand тестов, составляет гигабайты. Но это актуально для очень больших приложений, таких как распределённое обучение с подкреплением. Есть основания полагать, что даже в этих приложениях коллизия, вероятно, не окажет практического влияния на итоговый результат, поскольку статистическая проблема ограничивается только парой, которая столкнулась.

Теперь давайте рассмотрим случай, когда приращение не ограничено одинаковым значением. Наша реализация PCG64 инициализирует как состояние, так и приращение; то есть два вызова default_rng (почти наверняка) имеют разные состояния и приращения. При первом выпуске мы полагали, что имеющееся засеянное приращение обеспечит определённую дополнительную защиту, и что для наблюдения корреляций (PractRand сбои) в паре потоков необходимо быть «близким» как в пространстве состояний, так и в пространстве приращений. Если бы это было правдой, то «узким местом» для коллизий был бы объём пула энтропии 128 бит внутри SeedSequence (и коллизии 128 бит находятся в категории «абсолютно невероятных»). К сожалению, это не так.

Одно из известных свойств LCG состоит в том, что разные приращения создают *разные* потоки, но с известной взаимосвязью. Каждый LCG имеет орбиту, которая проходит через все \(2^{128}\) различных 128-битных состояний. Два LCG с разными приращениями связаны тем, что один может «вращать» орбиту первого LCG (продвинуть его на определённое количество шагов, которое мы можем вычислить из двух приращений) таким образом, что оба LCG будут иметь одинаковое состояние до аддитивной константы и, возможно, инверсии битов. Если затем вы итерируете оба потока синхронно, то состояния всегда останутся связанными той же самой аддитивной константой (и инверсией, если она присутствует). Напомним, что PCG64 построен как из функции перехода (LCG), так и из функции вывода. Ожидалось, что эффект перемешивания функции вывода будет достаточно сильным, чтобы сделать различные потоки практически независимыми (т.е. «пройти PractRand тесты»), если только два приращения не будут патологически связаны (например, 1 и 3). Функция вывода XSL-RR, тогда стандартного алгоритма PCG, реализованного в PCG64, оказывается слишком слабой, чтобы скрыть коллизию 58 бит в лежащем в основе LCG, описанной выше. Для любой данной пары приращений размер «коллизионного» пространства состояний одинаков, поэтому дополнительная различимость, обеспечиваемая приращениями, не переходит в дополнительную защиту от статистических корреляций, которые PractRand может обнаружить.

К счастью, усиление функции вывода способно исправить этот недостаток и *действительно* превращает дополнительную различимость, предоставляемую различными приращениями, в дополнительную защиту от этих коллизий младших бит. К чести автора PCG, она разработала более сильную функцию вывода в ответ на связанные обсуждения во время долгого рождения новой системы BitGenerator. Мы, разработчики NumPy, решили быть «осторожными» и использовать вариант XSL-RR, который в то время прошёл более длительный период тестирования. Функция вывода DXSM использует конструкцию «xorshift-умножение», используемую в сильных хеш-функциях для целых чисел, которая имеет намного лучшие свойства разброса, чем функция вывода XSL-RR. Хотя существуют «патологические» пары приращений, которые вызывают «плохие» аддитивные константы, связывающие два потока, подавляющее большинство пар вызывают «хорошие» аддитивные константы, превращающие просто различные потоки состояний LCG в практически независимые потоки вывода. В самом деле, теперь утверждение, которое мы когда-то сделали о PCG64, действительно верно для PCG64DXSM: коллизии возможны, но оба потока должны одновременно быть как «близкими» в пространстве состояний 128 бит, *так* и «близкими» в пространстве приращений 127 бит, поэтому это менее вероятно, чем ничтожная вероятность столкновения в 128-битном внутреннем пуле SeedSequence. Функция вывода DXSM более вычислительно затратна, чем XSL-RR, но некоторые оптимизации в LCG более чем компенсируют потери производительности на большинстве машин, поэтому PCG64DXSM — хорошее, надёжное обновление. Конечно, существует бесконечное множество более сильных функций вывода, которые можно рассмотреть, но большинство из них будут иметь большую вычислительную сложность, а функция вывода DXSM в настоящее время прошла множество циклов тестирования на процессоре с помощью PractRand.