KOMIYA Atsushi

KOMIYA Atsushi

Software engineer in Tokyo.

Java における乱数生成器とのつき合い方 / #JJUG CCC 2019 fall に登壇してきました

一般公募の枠で CfP 出してあえなくリジェクトされたテーマを、スポンサー枠で勝手に敗者復活させてお話してきました。

はじめに

Java 標準のクラスライブラリには、いくつかの乱数生成器の実装 (クラス) が存在しています。長年 Java でアプリケーションを書いている方であれば状況に応じてそれらの実装を使い分けることも難しい話ではありませんが、Java を扱い初めて間もない方にとってはそう簡単な話ではありません。

たとえば java 乱数 のようなクエリでググるとその状況がうかがい知れるのですが、巷にはプログラミングスクール各社の SEO を目的としたコンテンツが溢れていて、それらはいずれも「java.util.Random とか Math.random() とかなんでそんなレガシーなクラス/メソッドしか紹介しないの？ この記事を書いたライターというかエンジニアの人たちは J2SE 1.4 の時代で時が止まっているの？？？」といったお気持ちを抱く程度に 実用的でない内容満載でクオリティの低い (と個人的に感じられる) コンテンツであるにも関わらず検索結果 1 ページ目の上位を占拠しがちで、ゆえに Java 初学者にとっては実用的な乱数生成器の利用方法を知る機会が得られにくくなっています。

そういう状況をちょっとでも改善できればいいなあと思い、今回の JJUG CCC 2019 fall では Java (Java 11) における乱数生成器の利用方法についてお話をしました。具体的には、Java が標準的に提供する乱数生成器の実装にはどのようなものがあって、それらをもしくは外部ライブラリの乱数生成器実装をどのように使い分ければよいのかを、その前提となる知識 (乱数生成器の種類や、その評価方法など) とあわせてお話しました。

発表資料は こちら (SpeakerDeck) です。

お話の概要

今回の話の内容を箇条書きで要約すると、以下になります。

  • 乱数生成器には種類がある
    • 真の乱数生成器
    • 擬似乱数生成器
    • 暗号論的擬似乱数生成器
  • 乱数生成器の性能を評価する
    • 乱数の生成速度
      • アプリケーションのパフォーマンスに関わる
    • 乱数生成器の内部で保持する 内部状態 のメモリフットプリント
      • 非常にたくさんの乱数生成器を併用する場合には、メモリフットプリントが小さい方が好ましい
    • 周期の長さ
      • 利用目的次第では、周期の長さがとても重要になる
    • 統計的品質
      • 生成される乱数がランダムなのかを測る
      • テストスイート TestU01 の Big Crush がデファクト的に用いられる
  • Java の乱数生成器実装
    • java.util.Random
      • 擬似乱数生成器の実装
      • レガシーな実装であり欠陥も多く、好んで使っていいものではない
        • 統計的品質に問題がある、乱数の生成速度が遅いなど
    • SecureRandom
      • 暗号論的 擬似乱数生成器の実装
      • アルゴリズムの実装は (プラットフォーム/OS にもよるが) 複数存在する
      • シード再設定による乱数生成の再現性を担保しているかどうかは、アルゴリズムによる
      • NativePRNG 系のアルゴリズムは、アルゴリズムとプラットフォームの組み合わせ次第でブロッキングが生じうることに注意が必要
        • NativePRNGBlocking は Linux 環境だとブロックしうる
      • JEP 273 によって DRBG ベースのアルゴリズムが実装され、Java 9 から使えるようになった
        • 一部アルゴリズム は NSA によってバックドアが仕込まれた結果、DRBG から排除されたそうだが、他のアルゴリズムは大丈夫なのだろうか…
      • SHA1PRNG はレガシーであり、なるべくなら使わない方がよい
        • Windows でも DRBG が利用できるなら、そちらを使うのがよさそう
    • ThreadLocalRandom
      • 乱数生成速度的にも統計的品質にも優れている SplitMix アルゴリズム を採用した乱数生成器
      • シード再設定が許されていないため、再現性ある乱数列を生成することができない 弱点がある
      • 同じアルゴリズムを採用している SplittableRandom とは異なり、どのスレッドにおいても同じ乱数列を生成しうる
        • 複数スレッドで長期間乱数を生成し続けていると、あるスレッドが生成した乱数列とまったく同じ乱数列を生成し始めるスレッドが出現してしまう
    • SplittableRandom
      • ThreadLoc alRandom と同じく SplitMix アルゴリズムを採用している
      • SplittableRandom#split() によって、完全に異なる乱数列を生成する乱数生成器を作る ことができる
      • 標準の Java クラスライブラリの中では唯一の java.util.Random を継承していない乱数生成器の実装 である
  • 乱数生成器の使い分け
    1. 何を目的として乱数を生成しようとしているのかに合わせて適切な乱数生成器の 種類 を選び、求められる性能を考える
      • セキュリティに関わる場面で使うならば、原則として暗号論的擬似乱数生成器を使うべき
      • シミュレーション目的で使うならば、高速かつ周期の長い擬似乱数生成器が望ましい
      • Web アプリケーションで使うならば、高速でメモリフットプリントの小さい擬似乱数生成器が望ましい
    2. 求められる性能にあった乱数生成器のアルゴリズム・実装を選ぶ
      • 暗号論的擬似乱数生成器が必要ならば SecureRandom で、セキュリティ要件にあったアルゴリズムを選ぶ
      • シミュレーション目的なら Apache Commons RNG で実装されているメルセンヌツイスタや、周期の長さを気にしないなら SplittableRandom でもよさそう
      • Web アプリケーションなら ThreadLocalRandom、もしくは SplittableRandom を ThreadLocal で保持して利用するなど

会場での Q&A

会場からいただいた質問を自分なりに解釈した上での Q&A を載せておきます。

  • Q. シード再設定による乱数の再現性が必要なときって、どのようなケースがあるのか？
    • A. シミュレーションで乱数を用いる場合がそれにあたる。(そのシミュレーション内容にもよるが) シミュレーションを実行するたびに結果が変わると不都合であるなら、乱数の再現性が必要になる
  • Q. レガシーなアプリケーションで使われている乱数生成に関わるコードはどうすべき？
    • A. 再現性が求められるか否かで、書き換えて良いかダメかが決まる。また再現性が不要であっても、例えば乱数生成が速度パフォーマンスを左右しているとかそういう状況でなければ書き換えなくてもいいのでは？

時間の都合上割愛したネタ

今回は (同僚と折半して) 20 分の枠でお話ししたこともあり、いくつか触れなかった小ネタがあります。

ベンチマーク

Java クラスライブラリの実装に限定し、乱数の生成速度をベンチマークで測定してみました。macOS 上での測定であったため、NativePRNG 系のパフォーマンスがほとんど変わらずといった結果になっていますが、それぞれどれくらいの性能差があるのかの目安にはなるかと思います。

乱数生成器の実装 クラス (アルゴリズム) RNGs/ms
java.util.Random 97,861.489
SecureRandom (SHA1PRNG) 12,277.860
SecureRandom (DRBG) 1,080.910
SecureRandom (NativePRNG) 4,365.586
SecureRandom (NativePRNGBlocking) 4,257.936
SecureRandom (NativePRNGNonBlocking) 4,272.576
ThreadLocalRandom 285,754.982
SplittableRandom 296,092.275

暗号論的 ではない 擬似乱数生成器でランダムな文字列を作る際の注意

セキュリティ的な場面で使うわけではないが、ある程度の長さをもつランダムな文字列が欲しい、という状況を想定します。具体的に、英語アルファベットの大文字・小文字と 0~9 の数字、合計 52 種の文字からなる長さ 20 文字のランダムな文字列を生成する例を考えてみます。

このとき、期待されるランダム文字列の種類数は $52^{20} \approx 2^{114}$ 個になるのですが、仮に周期が $2^{64}$ しかない擬似乱数生成器を使ってランダム文字列を生成してしまうと、実際に得られるランダム文字列の種類数はその周期に等しい $2^{64}$ 個に制限されてしまいます。これはランダム文字列の利用用途次第ではあるのですが、仮に何かを識別する ID 的な目的で利用するとなると、誕生日パラドックス的にも想定より ID 重複が起こりやすい状況が発生してしまう、ということに注意が必要です。

なおこれはランダム文字列の生成だけの話ではなく、例えば Collections.shuffle() で比較的長いリストをシャッフルしようとした場合にも同様の状況が起こり得ます。

この手の問題を回避ないしは緩和するには、メルセンヌツイスタのようになるべく長い周期をもつ乱数生成器を利用することに尽きます。

さいごに

SecureRandom や DRBG の利用についてはあまり詳しくなかったこともあり、資料作成の際に以下のサイトを参考にさせていただきました。

CfP でリジェクトされたネタを話してはたしていいのだろうか… という疑問を抱きつつの発表でしたが、Twitter での反応を見ていると多少なりとも人のお役に立てる発表にはなったようで幸いです。お話をお聞きいただいた聴講者の方々、ならびに JJUG 運営の方々には感謝を申し上げます。ありがとうございました。

You may also enjoy