サーバー技術

GPUを使って無線LANをクラックする話：帰ってきたPyrit

linkucojp

次から次へと生まれ続ける「新技術」。今日もまた、「今後ITエンジニアに必要な技術はこれだ！」「キャッチアップ！」「未来が変わる！」と迫ってきます。たしかに、どれもすごい技術なのには間違いなさそうです。

しかしながら、疲弊してきているのも正直なところ本音ではないでしょうか。

…本当に身に付けたい能力ってなんだろう。

このタンポポの隣を通るたびに、いつもわたしは思うのです。

コンクリートの間のわずかな土で、光合成をしながら、冬の寒さにも負けずに、花を咲かせて生きる。

うん、わたしにもこの能力が欲しい！

こう書いてみると、そこらのラノベの主人公のチートな能力よりチートですね、タンポポ。

帰ってきたPyrit

というわけで、前々回山の上で瞑想して考えた「ぼくの考えた最強のベンチマーク・ルール」にしたがってガンガンPyritを書き換えていきましょう。この影響でPyritのリポジトリの構成が諸々変わっているので、使ってる人がいたら気をつけてください（居ないと思うけど）。

現状の問題を煮詰めると、次の２つでした：

  • 以下の処理が、すべてCPUを取り合っている：
    • ランダムなパスワードを生成する処理
    • パスワードをSHA1とかごにょごにょして変形するsolveの処理（GPUにもオフロードされるたぶん一番重い処理）
    • solveした結果とパケットダンプを突き合わせて、パスワードが正解かチェックするCrackerの処理（CPUのみ）
    • GPUのためにデータを詰めて渡す処理
  • CPUとGPUのsolverが、シングルスレッドで生成される「パスワード」の仕事を奪い合っている

というものでした。最初の問題のせいで、CPUやGPUの真の実力がわからず、２つめの問題のせいでマシン全体の実力がわかりません。GPUが1%ぐらいしか使われていなかった衝撃を思い出しておきましょう。

後者のほうはかなり厄介な問題な気がします。というのも、現在のパスワード生成処理は次の極めて簡素なコードで書かれており、小手先の最適化では立ち向かえそうにないからです：

            while time.time() - t < timeout:
                pws = ["barbarbar%s" % random.random() for i in xrange(bsize)]
                cp.enqueue('foo', pws)
                r = cp.dequeue(block=False)
                if r is not None:
                    perfcounter += len(r)
                self.tell("rRunning benchmark (%.1f PMKs/s)... %s" % 
                        (perfcounter.avg, cycler.next()), end=None)

これ1.5倍速くするのは…まぁ…ギリギリ可能かもしれませんが…100倍は無理じゃん？

これらを踏まえつつ、今日はCPUやGPUだけ単体で走らせて測定してみて、何がどうボトルネックになっているのか探っていきましょう。そうすれば、パスワードを今の何倍の速度で生成してやればいいのかのヒントも得られるはずです。

CPUに本気を出してもらう

ベンチマークで測っているのは、一番重い（であろう）solveの処理です。デフォルトではsolveの処理スレッドはCPUのコア数分立ち上がるのですが、CPUは他の処理もしないといけないので、CPUを占有してsolveに専念することができませんし、同じようにCPUで生成されているパスワードも取り合ってしまうでしょう。そこで、立ち上げるスレッドの数を減らします。

.pyrit/configにあるlimit_ncpusでその設定が出来るので、これを減らしていって何が起こるのか調べます：

~/.pyrit$ cat config 
default_storage = file://
limit_ncpus = 0
rpc_announce = true
rpc_announce_broadcast = false
rpc_knownclients = 
rpc_server = false
use_CUDA = false
use_OpenCL = false
workunit_size = 75000

オリジナルのバージョンはlimit_ncpus = 0を指定したときは「デフォルト」扱いになってCPUのコア数分（このマシンでは48個）立ち上がるようになっていたのですが、後でGPUだけで実行するときのために、0を指定したときは本当に0個スレッドを立ち上げる（つまりCPUを一切使わない）ように変更しました（ちなみに、CUDAもCPUも使わない場合、フリーズします）。

測ってみた結果がこちら(PMKというのがいわゆる「パスワード」です)：

ncputotal PMK/saverage PMK/s
1989.66989.66
22015.591007.795
43811.58952.895
87264.9908.1125
1613800.76862.5475
3217994.36562.32375
4818600.49387.5102083

で、グラフにするとこんな感じ：

16コアくらいまではだいたいスケールする（16倍とはいかないが、13倍くらいにはなる）んですが、32コアで突然頭打ちになって、コアあたりのパフォーマンスががくっと下がり、だいたい1.8万PMK/secぐらいで張り付きます。というわけで、これが現在のパスワード生成処理の限界なのでは？という仮説が立ち上がります。

GPUに本気を出してもらう

PyritはCUDAをデフォルトでは「全部使う」ようになっているので、これも１台ずつだけ使えるようにしてみました。CPUも一切使わず、GPU1台だけでクラックしていただきます。

で、やってみた結果がこちら：

デバイス名PMK/sec
Tesla V100-PCIE-16GB#1236335
Tesla V100-PCIE-16GB#2232217.35
GeForce GTX 1080 Ti#1222854.14
GeForce GTX 1080 Ti#2222457.37
全部一緒に動かす256639.55
CPUも全部同時に動かす136911.19

桁が多くて目が痛いのですが、単体で走らせた時に22〜23万PMK/sec、全部一緒に動かした時には25万PMK/secぐらい出ております。

これはつまり、あのパスワード生成コードは25万PMK/secは生成できているという事ですね。

…あれ？

ついでにいうと、CPUもGPUも同時に動かすと13万PMK/secという事で半分の速度にまで遅くなってしまいます。CPUとGPUで同時に処理して加速するはずだったのに、足を引っ張りあうのか、減速しております。

…あれ？デフォルトではCPUなしで実行できないし、ひょっとして、これ、誰も気づいてないんでは…。

結局、システム全体のポテンシャルはどれぐらいあるのか？

前に使ったProfilerをもっかい動かして、GPUを何割使ってるのか計測します：

Computed 225057.65 PMKs/s total.
CUDA:
#1: 'CUDA-Device #1 'Tesla V100-PCIE-16GB'': 237348.4 PMKs/s (RTT 0.5)
==41597== Profiling application: venv/bin/python pyrit benchmark
==41597== Profiling result:
            Type  Time(%)      Time     Calls       Avg       Min       Max  Name
 GPU activities:   99.08%  26.9879s       116  232.65ms  27.573ms  270.97ms  cuda_pmk_kernel
                    0.53%  143.46ms       116  1.2367ms  2.1760us  2.9881ms  [CUDA memcpy HtoD]
                    0.40%  108.18ms       116  932.60us  2.3360us  2.7747ms  [CUDA memcpy DtoH]
      API calls:   96.48%  27.1509s       116  234.06ms  27.585ms  272.31ms  cuMemcpyDtoH
                    1.88%  530.46ms         1  530.46ms  530.46ms  530.46ms  cuCtxCreate
                    0.54%  153.24ms       116  1.3211ms  27.996us  3.5144ms  cuMemcpyHtoD
                    0.47%  133.17ms         1  133.17ms  133.17ms  133.17ms  cuCtxDestroy
...

ベンチマークの時間は45秒、そのうちの27秒ほどを使っており、なかなかいい感じです。皮算用をしてみると、理想的な状況下ではGPU一枚あたり30万PMK/secぐらい出てもおかしくないと思います。で、4台あるので全体では120万PMK/sec出てほしい。

CPUは全体で理想的には4.8万PMK/sec出そうでしたから、合計すると125万PMK/secぐらいが理論的な限界値ではないかと皮算用できます。

あくまで皮算用ですけど。

原理的にパスワードはどれくらいの速度で生成できるのか？

ボトルネックだと思っていたパスワード生成はどうやらボトルネックではなさそうです。それを確かめるために、Pyritのコードから抜き出して加工した次のソースで測定します：

import time
import random

cnt = 0
t = time.time()
timeout = 30
while time.time() - t < timeout:
  pws = ["barbarbar%s" % random.random() for i in xrange(50000)]
  cnt += len(pws)

total = time.time()-t
print(cnt / total)

結果は268万PMK/secと出ました。うん、ボトルネックじゃないよここ…「推測はよくない」の例がまた一個増えましたね。…orz

とはいえ、皮算用したボトルネックのだいたい倍ぐらいの速度でしかなく、Pythonとその周辺コードはシングルスレッドでしか走らないことを踏まえると、最終的にボトルネックとして立ちはだかる可能性はまだ十分残されているでしょうな。

今月のまとめと来月の予告

  • CPUだけで走らせると、16コアと32コアの間で速度が頭打ちになる
  • GPUだけで走らせると、CPUとGPUを同時に走らせるより速い
  • 理想的なシステム全体のパフォーマンスは125万PMK/sec程度だと思われるが、パスワードの生成速度はそれをはるかに上回っているのでボトルネックではなさそう

以上の観察を踏まえるに、どうやら問題は最初の問題、つまり「CPUを取り合っている」の問題に尽きそうです。

次回はPythonのプロファイラーを使って、どこで詰まっているのかを調べましょう。

よいお年を〜。たんぽぽには、人間の暦なんか、関係ないけどね。