Случайность восстановлена в Chrome 49


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

Случайные числа часто используются в программах, начиная от игр и заканчивая серьезными симуляторами реального мира. Многие языки, включая JavaScript, предоставляют встроенную функцию, например Math.Random (), для генерации случайных чисел. Это имеет преимущество перед использованием дополнительных библиотек функций в том, что реализация может быть оптимизирована – в общем, вам нужно много случайных чисел за очень короткое время, поэтому важна скорость. Большая проблема с включением функции в язык заключается в том, что вам просто нужно принять то, что вам дано.

Конечно, генераторы случайных чисел обычно не являются случайными; они псевдослучайны. То есть числа генерируются алгоритмом так, чтобы они покрывали диапазон равномерно, и по n выборкам трудно предсказать будущие значения. Обратите внимание, что в принципе всегда очень легко предсказать будущее значение генератора случайных чисел – просто запустите его еще раз.

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

До Chrome 49 движок V8 JavaScript использовал MWC1616 (умножение с переносом, объединение двух 16-битных частей) PRNG, который, как известно, имел некоторые серьезные проблемы – проще говоря, он не прошел многие стандартные тесты.

Один из графических способов оценки качества ГПСЧ состоит в том, чтобы сгенерировать пары случайных значений x, y и построить их. В идеальном ГПСЧ точки были бы распределены равномерно и не демонстрировали бы слипания или тенденции к образованию полос.

Вы можете увидеть именно такой график для MWC1616 слева на двух диаграммах ниже:

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

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

Команда V8 теперь сообщает, что она «исправила» свой ГПСЧ, заменив MWC1616 на xorshift128 +, альтернативный алгоритм, который проходит все стандартные тесты и имеет период повторения 2128-1. Итак, начиная с версии V8 4.9.41.0, то есть Chrome 49, вы можете иметь случайные числа хорошего качества, как показано на правом графике, помеченном «После» выше. Вы можете видеть, что это выглядит более случайным.

Однако «выглядит» случайным образом недостаточно для многих приложений, и, как отмечает команда, новый ГПСЧ не обладает криптографическим качеством. Крипто-ГПСЧ или CPRNG должен пройти ряд дополнительных тестов. Если вы хотите сгенерировать случайное число для использования в безопасном хешировании, генераторе подписей или шифровании, вам понадобится CPRNG. Решением в этом случае является использование API веб-криптографии и метода getRandomValues, который обещает криптографически хорошие случайные числа, но только за дополнительную плату во времени.

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

Это поднимает интересный вопрос об опыте. Когда язык включает в себя такие специализированные функции, как случайный выбор, это, безусловно, расширяет навыки разработчика языка. JavaScript определяет случайную функцию, но не предоставляет никаких спецификаций того, как генерируются случайные числа – это кажется немного несправедливым.

Может быть, было бы лучше, если бы все реализации JavaScript использовали один и тот же ГПСЧ?

До тех пор не принимайте случайность JavaScript как должное.


Добавить комментарий