ブルートフォース

候補をすべて順に試して答えを探す方法

ブルートフォース(Brute Force)は、答えになりうる候補を1つずつ順に取り出し、条件を満たすかどうかを確かめていく問題の解き方です。英語の brute force は力任せという意味で、日本語では総当たりや全探索とも呼ばれます。この語は特定の手順の名前というより、コンピュータサイエンスで解き方の方針を表す一般的な呼び名として使われます。

ブルートフォースに必要なものは2つです。1つは、調べる候補の範囲です。もう1つは、ある候補が答えかどうかを判定する方法です。ブルートフォースは候補を順に並べて判定を当てていき、条件を満たした候補を答えとして返します。どの候補が有望かを見積もる工夫は使いません。

4桁の暗証番号で数える試行回数

数字4桁の南京錠の番号を忘れた場面を考えます。各桁は0から9の10通りなので、候補は10×10×10×10で10000通りです。0000から9999まで順に試せば、どこかで必ず開きます。最も運が悪ければ10000回目、平均するとおよそ5000回目で当たります。

桁が1つ増えて5桁になると候補は100000通り、6桁なら1000000通りです。桁が1つ増えるたびに、試す回数は10倍になります。候補の数は、1桁あたりの選択肢の数を桁数の回数だけ掛け合わせた値になるためです。

確実さと引き換えになる試行回数の増え方

ブルートフォースの長所は、候補の範囲の中に答えがあれば必ず見つかることです。全部試して1つも条件を満たさなければ、その範囲に答えが無いことも確かめられます。手順が単純なので、誤りの少ないプログラムを書きやすいという利点もあります。そのため、候補が少ない問題を解くときや、より速い方法が出した結果が正しいかを確かめる比較の基準として使われます。

短所は、試す回数が候補の数に比例することです。上の例のように、候補の数は問題の大きさに対して指数的に増えることが多く、問題が少し大きくなるだけで現実の時間では試しきれなくなります。この現象は組み合わせ爆発と呼ばれます。計算機を2倍速くしても、桁が1つ増えて候補が10倍になれば追いつけません。

探索木を手がかりなしで広げる探索との関係

AIの探索の分野では、問題の初期状態から取れるアクションごとに枝分かれさせた探索木を作り、目標の状態を探します。スチュアート・ラッセル(Stuart J. Russell)とピーター・ノーヴィグ(Peter Norvig)の教科書『Artificial Intelligence: A Modern Approach』第2版の第3章では、浅いノードから順に木を広げる幅優先探索や、深いノードから順に広げる深さ優先探索が説明されています。これらは、問題の定義以外に、どちらへ進めば目標に近いかという手がかりを使いません。こうした手法は情報なし探索(uninformed search)とまとめて呼ばれます。

ブルートフォースという語は、この教科書の章の見出しには出てきません。ただ、手がかりを使わずに可能性を順に調べていくという情報なし探索の性質は、ブルートフォースの一般的な意味と重なります。整理すると、ブルートフォースは総当たりで調べるという方針を表す語であり、木をどの順に広げるかまでは決めていません。幅優先探索や深さ優先探索は、その方針を探索木の上で行うときの具体的な手順と捉えられます。

探索木では、1つのノードから分かれる枝の数を分岐数と呼びます。深さが1段増えるごとにノードの数はおよそ分岐数の倍に増えるので、手がかりなしに木を端から調べると、暗証番号の桁が増えたときと同じ組み合わせ爆発が起きます。

機械学習とセキュリティでの使われ方

機械学習では、学習の前に人が決める設定値であるハイパーパラメータを選ぶときに、ブルートフォースの考え方が使われます。代表例はグリッドサーチで、候補値を格子状に並べ、すべての組み合わせでモデルを学習させて評価します。たとえば学習率の候補を3つ、層の数の候補を4つ用意すると、3×4で12回の学習が必要です。候補を5つ持つハイパーパラメータがもう1つ加われば、12×5で60回になります。1回の学習に時間がかかるモデルでは、この回数が大きな負担になります。そこで、候補から無作為に選んだ組み合わせだけを試すランダムサーチのような方法も使われます。

情報セキュリティでいうブルートフォース攻撃や総当たり攻撃は、パスワードや暗号の鍵として考えられる文字列を機械的にすべて試す攻撃です。暗証番号の例と同じく、使える文字の種類と桁数が増えるほど候補は急に増えるので、長く複雑なパスワードほど総当たりで破られにくくなります。ログインの失敗が続いたときに試行を止める仕組みも、試せる回数を減らして総当たりを難しくします。

手がかりで候補を減らす方法との違い

ブルートフォースと比べられるのは、何らかの手がかりで調べる候補を減らす方法です。パスワードの辞書攻撃は、すべての文字列ではなく、よく使われる単語の一覧から試します。試す回数は大きく減りますが、一覧に無いパスワードには当たらないので、必ず見つかるというブルートフォースの確実さは失われます。

ゲームの先読みで使われるαβ 法は、結果に影響しないと分かった枝の探索を打ち切ります。省くのは答えを変えない部分だけなので、すべての手を調べた場合と同じ結論が、より少ない計算で得られます。候補を減らす方法には、確実さを手放して速さを得るものと、確実さを保ったまま無駄だけを省くものがあります。ブルートフォースは、そのどちらとも比べる出発点になります。