C/C++の静的解析ツール・事例まとめ

C/C++の静的解析は、どう考えても大変なんだけどどう考えても需要が高いので、やはり色々なソフトウェアや事例があるようだ。まとまった情報が欲しいけど見つからなかったので自分の調べた範囲でまとめることにした。

他にも耳寄りな情報があったら教えてほしい。

静的解析を行うことができるソフトウェア

調べてみると結構たくさんある。それぞれの特徴とかあまりよくわからない。

(個人的には、とりわけ網羅的な形式的検証ができるツールの性能に興味があるので、それを中心に集めていたが、やはり網羅的とは限らないで探すともっとたくさん見つかるようだ。もちろん網羅性にはトレードオフがある)

• Frama-C …… C言語に形式手法を適用するための汎用のフレームワークで、静的検証のためのプラグインも多数(WPとかValueとか)存在する。網羅的な検証から発見的な手法、動的な手法まで様々ある。研究で使うのに便利そう
• Astrée Runtime Error Analyzer …… 飛行機などミッションクリティカル環境を主に想定した網羅的な静的分析器のようだ。昔のページ→The Astrée Static Analyzerを見ると、再帰と動的メモリ確保のないプログラムを対象としていたようだが、現在は再帰のないプログラムなら動的メモリ確保があっても検査できるようだ。フランスのINRIAとかその辺が関わっていそうな雰囲気がある
• VCC …… 名前に "concurrent" が含まれていたり、並行性が何かとプッシュされているように見える。codeplexに置いてあるしMSRかな
• SLAyer …… 最近MSが出したらしい。これも分離論理でメモリ安全性を調べるパターン(なので網羅性あるのかな)。
• VeriFast …… これもCのプログラムが検証できるらしい。
• Escher C/C++ Verifier …… 説明を見る限り、網羅的な検査をすると言っているように読める。C++も検証できると主張しているので強そう。会社概要を見る限り、これが主力商品のようだ
• Infer …… Facebookが買収したことで有名。分離論理使うくらいだから何らかの意味で網羅的なんだろうか。一般的なC/C++プログラムを検証できそうな雰囲気
• CBMC …… 有界モデル検査をするツールのようだ
• CodeSonar …… Z3使うらしい(ということはwhite-box testingとかかな)。網羅的とは書いていないように見えるので発見的な手法かな
• Coverity …… これも静的解析ツールとしては強いらしい。網羅性はパッと見では確認できなかった ← grafiさんが紹介してくれた記事にunsoundと書いてあった
• QAC …… これも網羅性は確認できなかった

余裕があれば上記のソフトウェアを以下のような観点から整理したい。

• 標準準拠 …… 言語仕様である ISO C, ISO C++. POSIXの仕様であるSUSやThe Open Group Specification. コーディング標準であるCWE, CERT C, MISRA-C. 安全性の規格であるDO-178B level A, ISO 26262, IEC 61508. ……などがあるらしいので、それぞれへの対応度を調べる。
• 網羅性 …… 一部の静的解析ツールは、ある種の問題(例えば実行時エラー)がないことを保証できる場合がある。例えばAstréeのページにはsound(健全)という言葉があるが、これはこの網羅性をあらわしている。
• 精度と再現率 …… 実際の問題に適用したときには、見つけられなかったバグの数や誤検出された問題の数が重要になると考えられる。
• 適用可能なプログラムの範囲 …… Astréeは再帰のないプログラムに限定して検証すると書かれている。このように、適用対象を絞ることで高性能な静的解析を提供している場合があるようだ。
• 適用可能なアサーションの表現力 …… プログラムにコメントでアサーションを入れるタイプの静的解析ツールでは、そのアサーションの表現力に違いがあるかもしれないので、その辺りを調べる。また、そうでない静的解析ツールでは、発見できるバグの種類がこれに相当すると考えられる。

検証済みコンパイラ

コンパイラ自体が(主に最適化まわりで)バグってることはたまにあるので、ミッションクリティカルな用途ではコンパイラ自体の正しさも気になるという事情があるようだ。

• CompCert …… Astréeと同じあたりが作ってるやつ。

プログラミング言語の形式仕様

C言語のプログラムやコンパイラに関して正確に論証したいとなるとそもそも仕様が必要になるが、ここで紹介しているのがまさにそれだ。

• Verifiable C …… Coqで書かれたC言語の仕様。便利そう。CompCertの正しさはこの仕様と照らしあわせて検証されている。

動的検査するやつ

静的解析ではないような気がするけど。

• Frama-C (上述) のE-ACSLプラグイン。
• Fail-Safe C

事例

• Frama-Cでmbedtls(PolarSSL)のメモリ破損脆弱性を見つけた事例

更新履歴

• 2016/05/07 Coverityについての記事をコメントで教えてもらったので追加。SLAyerについてTwitterで教えてもらったので追加。
• 2016/05/07 Code Sonar, Coverity, QACの3つの静的解析ツールを教えてもらったので追加。全体としては静的解析ツールのまとめなのでタイトルとか少し変更した。静的解析ツールについて分類したい旨を追加した。
• 2016/05/06 CBMCという有界モデル検査器を教えてもらったので追加
• 2016/05/06 公開

latexmk設定メモ

LaTeX文書のコンパイルをよしなにやってくれるlatexmkについて。

全体設定である ~/.latexmkrcには以下のように記入してある。

#!/usr/bin/env perl

$pdf_mode = 3;
$latex = 'uplatex -kanji=utf8 -synctex=1 -file-line-error -halt-on-error -interaction=nonstopmode %O %S';
$bibtex = 'upbibtex %O %B';
$dvipdf = 'dvipdfmx %O -o %D %S';

$biber = 'biber --bblencoding=utf8 -u -U %O %S';
$makeindex = 'mendex %O -o %D %S';

$pvc_view_file_via_temporary = 0;
$pdf_previewer = 'SumatraPDF -reuse-instance'

この設定は、ディレクトリごとの.latexmkrcで上書きできる。

運用

ディレクトリごとに.latexmkrcを置いて作業している。上の設定ファイルのうちビューワー設定以外の部分を、各状況にあわせて変更して使っている。

• latexmk pdfを作りたいだけのとき
• latexmk -pvc 継続ビルド。pdfを見ながら編集したいとき
• latexmk -pvc document.tex 上に同じ、ただしカレントディレクトリに*.texが複数あるときはこのように指定する

ビューワー設定

$pvc_view_file_via_temporary = 0;
$pdf_previewer = 'SumatraPDF -reuse-instance'

• $pvc_view_file_via_temporary ... latexmk -pvc でPDFを作成するとき、既定では一時ファイルに出力してから目的のファイルに移動する仕様になっているが、この設定ではこれを0にしている。
• $pdf_previewer ... Adobeなどファイルをロックするビューワーは使わないほうがよいだろう。この環境ではSumatraPDFにパスを通しているが、普通はフルパスを指定する

各種latexに共通のオプション

$latex = 'uplatex -kanji=utf8 -synctex=1 -file-line-error -halt-on-error -interaction=nonstopmode %O %S';

• -synctex=1 ... *.synctex.gzを生成する。
• -file-line-error ... エラー出力がわかりやすくなるらしい。
• -interaction=nonstopmode ... 文法エラーなどのときにユーザーに尋ねなくなる。
• -halt-on-error ... ファイルが存在しないなどのときにユーザーに尋ねなくなる。

特に最後の2つは、継続ビルドして作業するのには必須だろう

なお、%O %Sはそれぞれオプションとソースファイルを表す。コマンド指定系の変数では、%が全くない場合は自動的に適切なものが付与される。位置を変えたら何故か-interaction=nonstopmodeが効かなくなったので上のような順番がよいだろう。

latexごとの設定

生成経路に応じて数パターンあるが、ここではtex→dvi→pdfの場合と、tex→pdfの場合を書く。$pdf_modeが生成経路を指定している。

tex→dvi→pdf

uplatexを使う例。

$pdf_mode = 3;
$latex = 'uplatex -kanji=utf8 -synctex=1 -file-line-error -halt-on-error -interaction=nonstopmode %O %S';
$bibtex = 'upbibtex %O %B';
$dvipdf = 'dvipdfmx %O -o %D %S';

dvipdfとdvipdfm(x)ではオプションの順序が違うらしいので注意

tex→pdf

lualatexを使う例。(upbibtexにしない理由があるらしいが、こちらでは肯定的にも否定的にも未確認)

$pdf_mode = 1;
$pdflatex = 'lualatex -synctex=1 -file-line-error -halt-on-error -interaction=nonstopmode %O %S';
$bibtex = 'pbibtex %O %B';

auxdirについて

-auxdir / $aux_dir というオプションがあり、これを使うと各種の中間生成物の場所を別のディレクトリにできるような気がしてくるが、これは半分正しくない。現在はこのオプションが有効なのはMikTeX版のlatex系コマンドだけらしいので、残念ながら避けるのが無難だろう。

volatileとatomicの違い

volatileとatomicの違いを調べるために、以下のC++プログラムをコンパイルしてみる。

#include <atomic>

void func1(int *p) {
  ++*p; ++*p;
}

void func2(volatile int *p) {
  ++*p; ++*p;
}

void func3(std::atomic_int *p) {
  ++*p; ++*p;
}

$ g++ -std=c++11 -pthread -O2 -Wall -Wextra -g -c func.cpp -o func.o

環境による可能性はあるが、出力された機械語は端的に言うと次のようなものになる。(なおアーキテクチャはLinux x86-64)

func1:
	addl	$2, (%rdi)
	ret
func2:
	movl	(%rdi), %eax
	addl	$1, %eax
	movl	%eax, (%rdi)
	movl	(%rdi), %eax
	addl	$1, %eax
	movl	%eax, (%rdi)
	ret
func3:
	lock addl	$1, (%rdi)
	lock addl	$1, (%rdi)
	ret

• func1 は、「2を足す」という動作をしている。
• func2 は、「メモリから読み込んで1を足して書き込む」という動作を2回している。
• func3 は、「lockしながら1を足す」という動作を2回している。

これは以下の違いによる:

• volatile は、メモリの読み込みや書き込みを、副作用を伴う動作と見なす。*1 そのため、読み込みや書き込み動作を減らす最適化を行わない。ただし、回数や順番さえ合っていればよいので、他のスレッドに干渉されるかどうかは考えない。
• atomic は、他のスレッドが同時に読み書きしようとしても、あるひとまとまりの動作の間は独占的に動作するような振舞いになる。x86の場合はlockプレフィックスで実現できる。

動作確認

この動作は以下のプログラムで確認できる。

#include <cstdio>
#include <atomic>
#include <thread>

void func1(int *p);
void func2(volatile int *p);
void func3(std::atomic_int *p);

void count1(int *p) {
  for(int i = 0; i < 1000000; ++i) {
    func1(p);
  }
}

void count2(volatile int *p) {
  for(int i = 0; i < 1000000; ++i) {
    func2(p);
  }
}

void count3(std::atomic_int *p) {
  for(int i = 0; i < 1000000; ++i) {
    func3(p);
  }
}

int main(int argc, char *argv[]) {
  int num = -1;
  if(argc > 1) {
    std::sscanf(argv[1], "%d", &num);
  }
  if(num == 1) {
    int x = 0;
    std::thread th0(&count1, &x);
    std::thread th1(&count1, &x);
    th0.join();
    th1.join();
    std::printf("%d\n", x);
  } else if(num == 2) {
    volatile int x = 0;
    std::thread th0(&count2, &x);
    std::thread th1(&count2, &x);
    th0.join();
    th1.join();
    std::printf("%d\n", x);
  } else if(num == 3) {
    std::atomic_int x = ATOMIC_VAR_INIT(0);
    std::thread th0(&count3, &x);
    std::thread th1(&count3, &x);
    th0.join();
    th1.join();
    std::printf("%d\n", (int)x);
  }
  return 0;
}

$ g++ -std=c++11 -pthread -O2 -Wall -Wextra -g -c main.cpp -o main.o
$ g++ -std=c++11 -pthread -O2 -Wall -Wextra -g func.o main.o -o main

$ ./main 1
2497250
$ ./main 1
2432386
$ ./main 1
3136510
$ ./main 1
2411326
$ ./main 1
3466956
$ ./main 1
2367656
$ ./main 1
2297168

$ ./main 2
2324260
$ ./main 2
3137164
$ ./main 2
2374254
$ ./main 2
2627152
$ ./main 2
2593840
$ ./main 2
2871581
$ ./main 2
2218822
$ ./main 2
2617198

$ ./main 3
4000000
$ ./main 3
4000000
$ ./main 3
4000000
$ ./main 3
4000000
$ ./main 3
4000000
$ ./main 3
4000000
$ ./main 3
4000000

これはマルチコアの動作結果に関わるので環境によって異なる動作をするかもしれない。手元の環境はVirtualBoxで仮想化されたLinux x86-64であった。

atomicでは不十分な場合もある

atomicで一まとまりの動作と見なされる範囲はごく小さい。例えば*pが偶数であったとすると、以下の関数を繰り返し実行しても*pの値が変わらないことが意図される(シングルスレッドではそうなる)が、マルチスレッドではそうはならない。

#include <atomic>

void func(std:atomic_int *p) {
  *p += 1;
  *p ^= 1;
}

このような場合は単に*pをatomicにするだけでは不十分だが、mutexなどを使えばうまくいく。

*1:これはマルチスレッドのための仕組みというよりも、Memory-Mapped I/Oなどでメモリの読み書きが動作を伴う場合が想定されていると思われる。

文脈自由文法(CFG)と解析表現文法(PEG)をHaskellのモナドで説明する話

文脈自由文法(Context Free Grammar) と 解析表現文法(Parsing Expression Grammar) は記法が似ているものの、その性質は大きく異なっている。しかし、以下のようにHaskellのモナドを用いて、左再帰的でない文脈自由文法をそのままパーサーコンビネーターとして変換すると、PEGはList monadをMaybe monadとして置き換えたものとして説明できる。

-- CFGとPEGの関係を List vs. Maybe として説明するサンプル

import Control.Monad
import Control.Monad.State

-- 型の説明 : StateT String m a
-- StateT String ... 構文解析の残りの文字列を記憶している。
-- m ... 正否をあらわす。ListにするとCFG, MaybeにするとPEGになる
-- a ... 今回は構文解析の正否のみに興味があるので () にする。

-- 演算子の説明
-- A >> B ... 構文要素の連接を表す。
-- A `mplus` B ... 構文要素の選択を表す。

-- CFG/PEG共通 : 指定した1文字を読む。
readChar :: MonadPlus m => Char -> StateT String m ()
readChar ch = do
  (ch0:str) <- get
  guard $ ch0 == ch
  put str

-- CFG/PEG共通 : 文字列の終端か検査する。
eof :: MonadPlus m => StateT String m ()
eof = do
  [] <- get
  return ()

-- 文法その1
-- S -> A $
-- A -> "a" A "a" | "a"
a :: MonadPlus m => StateT String m ()
a = (readChar 'a' >> a >> readChar 'a')
    `mplus` readChar 'a'

grammar1 :: MonadPlus m => StateT String m ()
grammar1 = a >> eof


-- 文法その2
-- S -> B $
-- B -> "a" B "a" | "b" B "b" | ""
b :: MonadPlus m => StateT String m ()
b = (readChar 'a' >> b >> readChar 'a')
    `mplus` (readChar 'b' >> b >> readChar 'b')
    `mplus` return ()

grammar2 :: MonadPlus m => StateT String m ()
grammar2 = b >> eof


-- 文法を(左再帰的でない)CFGとして検査する
checkCFG :: StateT String [] () -> String -> Bool
checkCFG grammar str = runStateT grammar str /= []

-- 文法をPEGとして検査する
checkPEG :: StateT String Maybe () -> String -> Bool
checkPEG grammar str = runStateT grammar str /= Nothing


main :: IO ()
main = do
  forM_ [
      "",
      "a",
      "aa",
      "aaa",
      "aaaa",
      "aaaaa",
      "aaaaaa",
      "aaaaaaa"
    ] (\str -> do
      putStrLn $ "checkCFG grammar1 " ++ show str ++ " = " ++ show (checkCFG grammar1 str)
      putStrLn $ "checkPEG grammar1 " ++ show str ++ " = " ++ show (checkPEG grammar1 str)
    )
  forM_ [
      "aa",
      "abba",
      "bbbbbb",
      "baaaab"
    ] (\str -> do
      putStrLn $ "checkCFG grammar2 " ++ show str ++ " = " ++ show (checkCFG grammar2 str)
      putStrLn $ "checkPEG grammar2 " ++ show str ++ " = " ++ show (checkPEG grammar2 str)
    )

実行結果

checkCFG grammar1 "" = False
checkPEG grammar1 "" = False
checkCFG grammar1 "a" = True
checkPEG grammar1 "a" = True
checkCFG grammar1 "aa" = False
checkPEG grammar1 "aa" = False
checkCFG grammar1 "aaa" = True
checkPEG grammar1 "aaa" = True
checkCFG grammar1 "aaaa" = False
checkPEG grammar1 "aaaa" = False
checkCFG grammar1 "aaaaa" = True
checkPEG grammar1 "aaaaa" = False
checkCFG grammar1 "aaaaaa" = False
checkPEG grammar1 "aaaaaa" = False
checkCFG grammar1 "aaaaaaa" = True
checkPEG grammar1 "aaaaaaa" = True
checkCFG grammar2 "aa" = True
checkPEG grammar2 "aa" = True
checkCFG grammar2 "abba" = True
checkPEG grammar2 "abba" = True
checkCFG grammar2 "bbbbbb" = True
checkPEG grammar2 "bbbbbb" = True
checkCFG grammar2 "baaaab" = True
checkPEG grammar2 "baaaab" = False

文法の例として挙げたもの

S -> A
A -> "a" A "a"
A -> "a"

このCFGは奇数個のaからなる文字列を受理する。

S <- A
A <- "a" A "a"
   / "a"

このPEGは(2の冪-1)個のaからなる文字列を受理する。

S -> B
B -> "a" B "a"
B -> "b" B "b"
B -> ε

このCFGはaとbからなる偶数文字の回文を受理する。

S <- B
B <- "a" B "a"
   / "b" B "b"
   / ε

このPEGはよくわからないが回文でも受理しない場合がある。(上の実行結果を見よ。)

GCC拡張の無効化 (と、それにまつわる細かい話)

端的に言えば-pedantic-errorsを使えばよい。(できれば-std=...も併用したほうがいいだろう)

以下解説

GCCのC/C++コンパイラは、独自の拡張機能を導入している。これを無効化するオプションには2種類あり、意味が異なる。

1. C標準と矛盾する拡張機能を無効化する。
2. (C標準と矛盾しないかもしれない)拡張機能を無効化する/または警告を出す。

実は、C言語の規格は、それぞれのコンパイラの拡張機能を全面的に禁止しているわけではない。「正しいプログラム(strictly conforming program)を正しく動かす」ことさえ満たせばいいので、いくつかの拡張機能が有効化されたままでも、標準に準拠していると言える場合があるのだ。

C標準と矛盾する拡張機能を無効化する

C標準と矛盾する拡張機能を無効化するには、 -std オプションでISO C/C++を指定すればいい。 C Dialect Options - Using the GNU Compiler Collection (GCC) このオプションは、「C/C++のバージョン」「ISO準拠またはGNU独自」の2つの内容を指定する。

このオプションのデフォルトは、-std=gnu11や-std=gnu++03のように、gnuが含まれている設定である。これには、C標準と矛盾する拡張機能が含まれている。これを-std=c11や-std=c++14のように、cが含まれている設定に変えれば、C標準に準拠した挙動になる。

C標準と矛盾する拡張機能の例

• 1行コメント : C89と矛盾する。一見矛盾しないように見えるが、1行コメントの有無により挙動が変わるコードが存在する。
• Trigraphの無効化 : "??/"のようなコードの解釈が変わる。
• typeof : C++11以降のdecltypeに相当する機能。このような予約語をC標準の範囲内で追加することはできない(変数名と衝突する可能性があるからである)。同じ機能をもつ__typeof__は問題ない。

多くのGCC拡張機能は、既存のCコードの意味を変えないように配慮されている。したがって、この方法で拡張機能を無効化することによる影響はそれほど大きくはない。

拡張機能を無効化する/または警告を出す

• 拡張機能に警告を出すには、 -Wpedantic オプション*1を使う。 C Dialect Options - Using the GNU Compiler Collection (GCC)
• 拡張機能をエラーにするには、-pedantic-errors オプションを使う。

これは、C/C++コード中で拡張機能が利用されていた時に、警告またはエラーにする機能である。

このオプションの挙動も明快に説明できるわけではなく、色々な注釈が必要である。

• long longなど、「以前のバージョンではGCC拡張であったが、新しいバージョンでは標準」という機能は多数存在する。これらは、-std=c...で指定されたバージョンに応じて判定する。
• -std=gnu...が指定されていた場合は、対応するISO C/C++標準に基づいて判定する。しかし、-pedantic-errorsを指定していても、例えば-std=c90と-std=gnu90では意味が違う。上記の1行コメントの例は、前者ではコンパイルが通るが、後者ではコンパイルエラーになる。
• -Werror=pedanticとすると、-Wpedanticで出る警告すべてをエラーにすることができる。これは-pedantic-errorsとは微妙に意味が異なる。*2
• 明示的に「拡張機能」とされているものを判定することはできるが、これによってプログラムが本当の意味でISO C/C++準拠であるかを確認できるとは限らない。
  • コンパイル時にわかる範囲の例では、int _Foo = 1;のようなコードを規格違反として検出できない。*3
  • 処理系定義・未規定・未定義な挙動により、「たまたま動いているけど動く保証がないコード」が生まれることはよくある。これを全てコンパイル時に検出するのは不可能である。実行時にある程度検出することはできる (デバッグオプションで説明されている-fsanitize=undefinedオプションなど) が、完全ではないし、実行効率が落ちると予想される。

*1:Wがない -pedantic も同じ意味

*2:とドキュメントには書いてあるが、詳細は未調査

*3:その部分が標準ライブラリ由来であるか、ユーザーの提供したプログラム由来であるかを判定するには、コンパイラの構造をそれなりに変えないといけないので、将来のコンパイラでもこれを判定することはないだろう。

64bit windows上でのalloy* (hola)

Alloy (hola) のバックエンドはSATソルバであり、いくつかのバックエンドから選べる。しかし、64bit windows上の64bit JREでは、SAT4J以外は動作しない。

以下の手順で自分でjarを作成すれば、minisat等が動くバイナリが作れる。

kodkodのネイティブライブラリをダウンロードして展開

/some/path$ wget http://alloy.mit.edu/kodkod/release/win_x86_64.zip
/some/path$ unzip win_x86_64.zip

Alloyをダウンロードして展開

/some/path$ wget http://alloy.mit.edu/alloy/hola/downloads/hola-0.2.jar
/some/path$ mkdir hola-0.2
/some/path$ cd hola-0.2
/some/path/hola-0.2$ jar xvf ../hola-0.2.jar

kodkodのネイティブライブラリをコピー

/some/path/hola-0.2$ cp -r ../win_x86_64 amd64-windows

jarを作成

/some/path/hola-0.2$ jar cvfm ../hola-0.2.jar META-INF/MANIFEST.MF .

以上により、64bit windows用のネイティブライブラリが含まれたhola-0.2.jarが作成された。

C++11 random 覚え書き

C++11以降では<random>ヘッダで良質な擬似乱数を得ることができる。

#include <random>

外部からの乱数

外部から乱数を得るにはrandom_deviceを使う。

#include <random>
#include <iostream>

int main() {
  std::random_device rand_dev;
  std::cout << rand_dev() << std::endl;
  std::cout << rand_dev() << std::endl;
  return 0;
}

上のように、外部からの乱数源は関数として呼び出すことで乱数を生成する。

このプログラムは実行するごとに異なる値を出力する。

擬似乱数

擬似乱数は、シード値を放り込むと乱数っぽい数列を吐き出すプログラム。

生成方法が何種類かあるが、mt19937だけ把握していればよい。

#include <random>
#include <iostream>

int main() {
  std::mt19937 rand_src(12345);
  std::cout << rand_src() << std::endl;
  std::cout << rand_src() << std::endl;
  return 0;
}

上のように、擬似乱数生成器は関数として呼び出すことで擬似乱数を生成する。

このプログラムは異なる整数を2つ出力するが、プログラムの実行ごとに同じ整数を出力する。

ソース中の12345がシード値である。この数値を変更すると、異なる整数を出力するようになる。

乱数の加工

上で生成した乱数は32bit一様乱数等なので、必要な分布が出るように加工する。

#include <random>
#include <iostream>

int main() {
  std::mt19937 rand_src(12345);
  std::uniform_int_distribution<int> rand_dist(0, 99);
  std::cout << rand_dist(rand_src) << std::endl;
  std::cout << rand_dist(rand_src) << std::endl;
  return 0;
}

上のように、分布を関数として使うときは、引数に乱数源への参照を渡す。内部で乱数源が(必要に応じて複数回)呼ばれている。

上のソースコードでは、MTで生成される擬似乱数列をもとに、一様分布に従う0以上99以下の整数を2つ生成している。

よく使う分布:

• 離散一様分布 uniform_int_distribution
  • テンプレート引数 : 戻り値の型(int等)
  • コンストラクタの引数 : a以上b以下の乱数を生成
• 連続一様分布 uniform_real_distribution
  • テンプレート引数 : 戻り値の型(double等)
  • コンストラクタの引数 : a以上b未満の乱数を生成
• 正規分布 normal_distribution
  • テンプレート引数 : 戻り値の型(double等)
  • コンストラクタの引数 : 平均meanで標準偏差stddev (省略すると標準正規分布)

暗号論的擬似乱数

たぶんこのライブラリには無い。

分布と擬似乱数生成器を合体させる

分布に毎回擬似乱数生成器をつけるのは面倒であるから、<functional>ヘッダにあるbindとrefを使って以下のようにする。

#include <random>
#include <iostream>
#include <functional>

int main() {
  std::mt19937 rand_src(12345);
  std::uniform_int_distribution<int> rand_dist(0, 9);
  auto rand_dist_bound = std::bind(rand_dist, std::ref(rand_src));
  std::cout << rand_dist_bound() << std::endl;
  std::cout << rand_dist_bound() << std::endl;
  return 0;
}

refを使わずに、

  auto rand_dist_bound = std::bind(rand_dist, rand_src);

としても一応動作するが、これは擬似乱数生成器のコピーを作成してしまうので意味が変わる。同じ擬似乱数生成器を複数の分布で使う場合は注意が必要(通常、refをつけるほうが好ましい)

これは以下のようにしても同じことである:

#include <random>
#include <iostream>
#include <functional>

int main() {
  std::mt19937 rand_src(12345);
  auto rand_dist_bound = std::bind(
    std::uniform_int_distribution<int>(0, 9),
    std::ref(rand_src));
  std::cout << rand_dist_bound() << std::endl;
  std::cout << rand_dist_bound() << std::endl;
  return 0;
}

さらに、この擬似乱数生成器はこの分布でしか使わないというのであれば、以下のようにもできる(この場合はrefは使わない):

#include <random>
#include <iostream>
#include <functional>

int main() {
  auto rand_dist_bound = std::bind(
    std::uniform_int_distribution<int>(0, 9),
    std::mt19937(12345));
  std::cout << rand_dist_bound() << std::endl;
  std::cout << rand_dist_bound() << std::endl;
  return 0;
}

シードの決め方

シードの決め方は場合による。大雑把に言うと次の2種類:

• 外部からの乱数に基づいて決める
• 決め打ち

ただし、以下のことに注意が必要だ:

• 外部からの乱数が必要な状況はあまり多くない : 乱数に基づくアルゴリズムは、シード決め打ちの擬似乱数で問題なく動作する。
• むしろ、再現性を考えると、シードを決め打ちにしたほうが良い。
• 「実行ごとに動作を変えたい」という需要は、コマンドライン引数などでシードを指定できるようにするだけで満足されることがある。

外部からの乱数に基づいてシードを決める

外部からの乱数に基づいてシードを決めるには、単に以下のようにすればよい:

#include <random>
#include <iostream>

int main() {
  std::random_device rand_dev;
  std::mt19937 rand_src(rand_dev());
  std::cout << rand_src() << std::endl;
  std::cout << rand_src() << std::endl;
  return 0;
}

このようにすると、毎回シードが変わるので、実行するごとに異なる整数が表示される。

外部からの乱数源を1回しか使っていないので、以下のようにもできる:

#include <random>
#include <iostream>

int main() {
  std::mt19937 rand_src(std::random_device{}());
  std::cout << rand_src() << std::endl;
  std::cout << rand_src() << std::endl;
  return 0;
}

コマンドライン引数に基づいてシードを決める

例えば、コマンドライン引数の1番目がある場合はそれをシードとして使うようにするには:

#include <random>
#include <iostream>
#include <string>

int main(int argc, char *argv[]) {
  int seed = 12345;
  if(argc > 1) {
    seed = std::stoi(argv[1]);
  }
  std::mt19937 rand_src(seed);
  std::cout << rand_src() << std::endl;
  std::cout << rand_src() << std::endl;
  return 0;
}

また、コマンドライン引数を与えない場合のデフォルトは、外部からの乱数でもよいかもしれない:

#include <random>
#include <iostream>
#include <string>

int main(int argc, char *argv[]) {
  int seed;
  if(argc > 1) {
    seed = std::stoi(argv[1]);
  } else {
    seed = std::random_device{}();
  }
  std::mt19937 rand_src(seed);
  std::cout << rand_src() << std::endl;
  std::cout << rand_src() << std::endl;
  return 0;
}

サンプルコード

POSIX usleep(3)を使って、1秒間あたり平均5個のランダムな(ポアソン過程に基づく)イベントを発生させる (十分たくさんの粒子があるときの放射線の発生とかがこれ)

#include <random>
#include <iostream>
#include <string>
#include <functional>
#include <unistd.h>

int main(int argc, char *argv[]) {
  int seed;
  if(argc > 1) {
    seed = std::stoi(argv[1]);
  } else {
    seed = std::random_device{}();
  }
  std::mt19937 rand_src(seed);
  auto rand = std::bind(
      std::exponential_distribution<double>(5.0 / 1000000.0),
      std::ref(rand_src));
  while(true) {
    std::cout << "a" << std::flush;
    usleep(rand());
  }
  std::cout << rand_src() << std::endl;
  std::cout << rand_src() << std::endl;
  return 0;
}