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

Использование генератора PCG64 BitGenerator в массивном параллельном контексте продемонстрировало статистические уязвимости, которые не были очевидны при первом выпуске в numpy 1.17. Большинство пользователей никогда не столкнутся с этой уязвимостью и могут продолжать безопасно использовать PCG64. Мы представили новый генератор PCG64DXSM BitGenerator, который в будущих версиях станет новым стандартным генератором BitGenerator, используемым в default_rng. PCG64DXSM устраняет статистические недостатки, сохраняя производительность и функции PCG64.

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

Если вы

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

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

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

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

Технические подробности

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

Одна из этих известных уязвимостей заключается в том, что перемещение состояния ЛКГ на шаги, являющиеся степенью двойки (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 использует конструкцию «исключающее ИЛИ – умножение», используемую в сильных целочисленных хешах, которая обладает значительно лучшими свойствами «всплеска» по сравнению с функцией вывода XSL-RR. Хотя существуют «патологические» пары приращений, которые вызывают «плохие» добавочные константы, связывающие два потока, подавляющее большинство пар вызывает «хорошие» добавочные константы, превращая просто различные потоки состояний LCG в практически независимые потоки вывода. Действительно, теперь утверждение, которое мы когда-то сделали о PCG64, на самом деле верно для PCG64DXSM: столкновения возможны, но оба потока должны одновременно быть как «близки» в 128-битном пространстве состояний, так и «близки» в 127-битном пространстве приращений, поэтому это менее вероятно, чем ничтожная вероятность столкновения в 128-битном внутреннем SeedSequence пуле. Функция вывода DXSM более трудоёмка в вычислениях, чем XSL-RR, но некоторые оптимизации в LCG более чем компенсируют потери производительности на большинстве машин, поэтому PCG64DXSM является хорошим и безопасным обновлением. Конечно, существует бесконечное множество более сильных функций вывода, которые можно рассмотреть, но большинство из них будут иметь большую вычислительную стоимость, а функция вывода DXSM к этому моменту прошла много циклов тестирования на процессорах посредством PractRand.