Session Riding - A Widespread Vulnerability in Today's Web Applications を読んでみる。
gcc で predefined macro を出す方法。
% touch t.c % gcc -E -dM t.c
昔どこかで読んだ覚えがあるのだが、今日はどうにも思い出せなくて調べ直した。
/dev/urandom について調べてみる。
以前 Mandrake Linux で util-linux mcookie utility generates predictable cookies という話があったらしい。
(Mandrake Linux のローカルパッチで /dev/random から /dev/urandom に変えていて) /dev/urandom を使っていたから生成した cookie が predictable だったというのだが、 具体的にはどうやって直したのだろう?
また、最近の mcookie は、/dev/random を O_NONBLOCK で読んで、 読めなかったら /dev/urandom も使うようになっているようだが、 これって意味があるのだろうか?
エントロピーが足りてるときには /dev/random でも /dev/urandom でも問題ないだろうし、 エントロピーが足りないときには /dev/random からは読みだせなくて /dev/urandom を使うことになってしまうので、 単に /dev/urandom を使うよりも良い点はあるのだろうか?
Hacker's Delight を眺めて、一番上のビットを見つける方法を調べる。
何種類か書いてあったが、
x = x | x >> 1; x = x | x >> 2; x = x | x >> 4; x = x | x >> 8; x = x | x >> 16; x -= x >> 1;
というのがぐっときた。
Mersenne Twister の FAQ に、 「サイコロみたいに、[0..N-1]の一様乱数を生成したい」という項目がある。
それに対する答として、 「どうしても丸め誤差が問題になる場合は、整数乱数を生成し、N<=2^nとなる最小のnをとって、二進で上位n桁を見て、N以上の乱数は捨てればO.K.」 という方法が述べられている。
この方法で生成するのに必要な乱数生成回数の期待値は何になるか?
最初に生成した n桁の乱数が N-1以下なら 1回で済むが、 N以上なら 2回目に挑戦しないといけない。
2回目に生成した n桁の乱数が N-1以下なら 2回で済むが、 N以上なら 3回目に挑戦しないといけない。
3回目に生成した n桁の乱数が N-1以下なら 3回で済むが、 N以上なら 4回目に挑戦しないといけない。
... 以下同様に続く。
というわけで、期待値 E は 1*(N/2^n) + 2*(1-N/2^n)^1*(N/2^n) + 3*(1-N/2^n)^2*(N/2^n) + ... = 2^n/N になる。
n には 2^(n-1) < N <= 2^n という条件があり、 N=2^(n-1)+1 のときに期待値は最大のほぼ 2 となり、 N=2^n のときに最小の 1 となる。
さて、これは乱数生成 1回で n桁の乱数が得られるときの話である。 genrand_int32 を使うとすれば、これは 32bit 生成するので、n <= 32 のときに適用できる。
ここで、32 < n の場合にも genrand_int32 を使うなら複数回呼ばなければならない。 例えば 64bit のときに genrand_int32 を毎回 2回づつ呼んだとすれば、genrand_int32 の呼び出し回数の期待値は 2倍になる。
しかし、乱数の上位桁から生成していき、その乱数と N の大小比較をするとすれば、 最後の桁まで求めなくても大小比較の結果が決定できることがある。
そのようにして乱数生成を抑えた場合、期待値はどう変わるか?
なぜ -O3 なのか?
Al2 O3 だから?
Nicholas presents the Directors
Rails の次期 URL mapping
パターンマッチでやるらしい。 URL の生成も出来る模様。
Note PC がデイパックから落ちて、構造的欠陥を思い知る。
幸いにして壊れなかった。
新しいのを買う。
mput さんのところの autobuild が cvs co で失敗している。
最近の cvs では (password が不要なら) cvs login が不要になっているはずだが、 いつからだっけか。
FreeBSD 4.x の thread はすべての fd を nonblocking にするという話を知る。 まぁ、ユーザレベルスレッドであればある程度しかたがないともいえるが、傍迷惑ではある。
FreeBSD 4.10 で試してみる。 thread なプログラムが見当たらなかったので とりあえず ruby を --enable-pthread で作ってみる。
freebsd410% ldd ./ruby
./ruby:
libcrypt.so.2 => /usr/lib/libcrypt.so.2 (0x2810f000)
libm.so.2 => /usr/lib/libm.so.2 (0x28128000)
libc_r.so.4 => /usr/lib/libc_r.so.4 (0x28143000)
freebsd410% sh -c './ruby -e "sleep 1" & ./ruby -rio/nonblock -e "sleep 0.5; p STDOUT.nonblock?"'
true
たしかにそうなっているようである。
そういう傍迷惑なプログラムから身を守るためには、nonblocking flag に依存して挙動を変えるという仕様はよろしくない。
FreeBSD 4 で nonblocking になるといっても、 FreeBSD 5 ではカーネルレベルスレッドになるので、 それは時間が解決することだともいえる。
他のはどうか?
NetBSD 2.0 はカーネルレベルスレッドなのでそういう問題はない。
OpenBSD 3.6 は FreeBSD 4.10 と同様な状況のようである。 OpenBSD はいつまでユーザレベルスレッドでありつづけてくれるだろうか?
このへんを調べたときにはいつも思うことだが、 nonblock の仕様は出来が悪い。
誰がデザインしたのだろう?
nonblocking I/O の目的は、 blocking I/O だったらブロックして止まっている時間に、 その I/O 以外の作業を行う機会を得ることだと思う。
だから、もしスレッドが前提であり、 I/O を行った当のスレッド以外のスレッドで作業を行えるのであれば、 I/O オペレーションはブロックしてかまわないはずだと思う。
もちろん、プロセス全体がブロックするのは他のスレッドで作業ができないので論外だし、 場合によってはスレッドのオーバーヘッドが許容できない場合はあるかも知れない。 でも、原理的にはスレッドと blocking I/O でもいいはずだと思う。
では、スレッドがない状況でその目的を達成するためには、 どういう API を用意するのが適切だろうか?
やはりイベントドリブンだろうか?
Twisted は nonblocking I/O をどう扱うのだろう?
Twisted from Scratch, or The Evolution of Finger をざっと眺めてみる。
ひとつのスタイルというわけではない感じだが、 lambda を使っているところは CPS を思い起こさせる。
CPS でぜんぶ書くというのはひとつの案かも知れない。 まぁ、CPS は継続を関数として表現する方法で、 継続はスレッドみたいに使うことも出来るものなんだから、 CPS でどうにかできるのは当り前か。
並行処理をどう書くかというところまで問題を一般化してしまうと、 新しい方法は考えつきそうにない。
とすると、可能性があるとすれば nonblocking I/O という用途に特化した方法を 考えられるかというところだが、nonblocking I/O で行う作業は 一般的な並行処理に対して偏りがあるだろうか?
w3m であるサイトを見ると、w3m 起動後、自動的に他のページにいってしまうという奇怪な現象にみまわれた。
調べてみると、 なんかのひょうしに kterm の Auto Linefeed というのが enable されてしまっており、 改行が余計に w3m に送られ、 その改行によって w3m が画面左上隅のリンクをたどっていたらしい。
nonblocking I/O がユーザレベルスレッドの実装に使われるとき、 nonblocking I/O によって得られる作業の機会は、 他のスレッドの実行にあてられる。 この場合、他のスレッドが行うどんな作業も行われる可能性がある。
DJB は nonblocking I/O を、signal の到着から signal handler を実行できる safe point まで、 一気に (ブロックせずに) 駆け抜けることに使っている (と思う)。 この場合、nonblocking I/O によって得られる作業の機会は、 signal handler の実行に使われている。
select で確認してから I/O を行うと、race condition ができてしまう。 複数の process で file descriptor を共有している場合、 select で確認してから I/O を行うまでに他のプロセスが I/O を行って確認した状況が変化してしまうかも知れない。 そういう場合に I/O でブロックするのを防ぐのに nonblocking I/O を使うことがある。 この場合、nonblocking I/O は、select の結果をなかったことにするのに使われる。
他にはどういう使われかたがあるか?
nonblocking I/O の用途には、 nonblocking I/O を使わなくても select で (race condition を許容すれば) 済むものと、 済まないものに分類できるように思う。
read は前者で、select で読み込めることを確認してから read すれば、 (そして select と read の間で状況が変わる race condition を考慮しないとすれば) ブロックを防げる。
connect は後者で、nonblocking I/O を使わない限りブロックの可能性を避けられない。
accept は前者で、 (race condition を考慮しないとすれば) select で accept がブロックしなくなるのを確認できる。
write は、一度に 1byte (pipe/fifo なら PIPE_BUF) よりもたくさん書き込む場合は select で確認したとしてもブロックする可能性がある。 そして 1byte づつ書き込むのは効率が悪すぎるため、現実的には後者にあたる。
signal は、それ自身はブロックするものではないが、 受け取った場所と safe point の間にある I/O が問題になる。 そして、signal は race condition の問題の度合が I/O よりも大きい。 I/O での race condition は fd を share していなければ問題ない。 しかし、signal が write 直前に到着したにもかかわらず write がブロックしてしまうという race condition はプログラムが write を使っている限り可能性を排除できない。 そして、write を行わないプログラムは稀である。
テストで次のようなエラーとなった。
.../home/akr/autobuild/tmp/autobuild/ruby-trunk/20050127-171641/lib/ruby/1.9/timeout.rb:43:in `rbuf_fill': execution expired (Timeout::Error)
from /home/akr/autobuild/tmp/autobuild/ruby-trunk/20050127-171641/lib/ruby/1.9/net/protocol.rb:132:in `timeout'
from /home/akr/autobuild/tmp/autobuild/ruby-trunk/20050127-171641/lib/ruby/1.9/timeout.rb:56:in `timeout'
from /home/akr/autobuild/tmp/autobuild/ruby-trunk/20050127-171641/lib/ruby/1.9/net/protocol.rb:132:in `rbuf_fill'
from /home/akr/autobuild/tmp/autobuild/ruby-trunk/20050127-171641/lib/ruby/1.9/net/protocol.rb:116:in `readuntil'
from /home/akr/autobuild/tmp/autobuild/ruby-trunk/20050127-171641/lib/ruby/1.9/net/protocol.rb:126:in `readline'
from /home/akr/autobuild/tmp/autobuild/ruby-trunk/20050127-171641/lib/ruby/1.9/net/http.rb:1850:in `read_status_line'
from /home/akr/autobuild/tmp/autobuild/ruby-trunk/20050127-171641/lib/ruby/1.9/net/http.rb:1839:in `read_new'
from /home/akr/autobuild/tmp/autobuild/ruby-trunk/20050127-171641/lib/ruby/1.9/net/http.rb:934:in `request'
... 30 levels...
from /home/akr/autobuild/tmp/autobuild/ruby-trunk/20050127-171641/lib/ruby/1.9/test/unit/ui/testrunnerutilities.rb:29:in `run'
from /home/akr/autobuild/tmp/autobuild/ruby-trunk/20050127-171641/lib/ruby/1.9/test/unit/autorunner.rb:194:in `run'
from /home/akr/autobuild/tmp/autobuild/ruby-trunk/20050127-171641/lib/ruby/1.9/test/unit/autorunner.rb:14:in `run'
from test/runner.rb:9
さて、何が悪いのか?
珍しくメールで反応があり、 accept について、 accept 前に RST で connection (の前段階?) がなくなってしまったときの race condition について指摘を受けた。
その状況自身は忘れていたのの、 それも race condition ではあるので折込済みなのだが、 それに関連して「I/O での race condition は fd を share していなければ問題ない」 という記述には問題があることに後から気づいた。
fd を share して複数のプロセスが accept するときの race condition は share しないことで防げるが、 RST による race condition は防げない。
nonblocking I/O でないと防げないという意味で、 これは signal の race condition に似ている。
Ruby の accept は nonblocking I/O での EAGAIN をそのままユーザに見せる。 ([ruby-talk:113807] 以降)
この挙動は nonblocking flag 依存なので気に入らなかったのだが、 説得力のある実害が見当たらなかったのでいままで放置していた。
しかし、 nonblocking I/O にしないと外部からプロセスをブロックさせてしまえるのであれば、 これは DoS アタックに使えるわけで、 nonblocking I/O での記述を面倒臭くする (retry を自前で書かなければならない) そういう挙動は実害があることを説得できるのではなかろうか。
というわけで試してみる。
まずサーバを起動する。 このサーバは I/O を行い続けてたまに sleep するスレッドと、 繰り返し accept するスレッドからなる。 前者の優先順位を高くしてあるため、select と accept の間にそっちの処理が行われ、sleep したときにやっと accept する。
% ruby -d -rsocket -e '
r, w = IO.pipe
fork {
loop { w << "a" * 10000 }
}
Thread.new {
Thread.current.priority = 1
loop {
10000.times { r.sysread(1) }
p :s
sleep 1
}
}
TCPServer.open("127.0.0.1", 9877) {|s|
loop { p s.accept }
}
'
で、RST を送るクライアントを動かす。
% ruby -rsocket -e '
TCPSocket.open("127.0.0.1", 9877) {|s|
linger = [1, 0].pack("ii")
s.setsockopt(Socket::SOL_SOCKET, Socket::SO_LINGER, linger)
}
'
race condition なので一発でうまくいく (ブロックする) というわけではない。 繰り返し試す。
どうも Linux ではうまくいかないので、NetBSD 2.0 に移る。
何回か動かすと、次のエラーが出て来た。
Exception `Errno::ECONNABORTED' at -e:15 - Software caused connection abort -e:15:in `accept': Software caused connection abort (Errno::ECONNABORTED)
え? ブロックするんじゃなかったのか?
SUSv3 を調べると、この ECONNABORTED はちゃんと載っている。 ただ、説明は「A connection has been aborted.」としか書いてなくて定数名以上の情報はない。
検索すると、RRRWiki - ToDo037 というのが見つかる。 このページに載っているものだと、FreeBSD 2.2.8-RELEASE のがブロックする挙動だろうか?
だが、ECONNABORTED あたりになるのであれば、RST ではブロックされないわけで、 この race condition はブロックに結び付かず、nonblocking I/O は不要である。
なお、情報提供してくれたメールもこのページも Unix Network Programming 2nd Edition Vol.1 を参照している。 ただ、メールでは 15.6 が参照されていたのだが、 このページでは 5.11 が参照されている。 これはもう一度確認してみることにしよう。
しかし、このページを見る限りはブロックする挙動はすたれかけている感じである。 ということは、nonblocking I/O にしなくてもセキュリティ的な問題は大きくなさそうであり、実害としてはあまり説得力がない。
まぁ、EAGAIN はともかく ECONNABORTED と ECONNRESET で retry するというのは提案すれば簡単に通る気はする。
[latest]