2012年3月31日土曜日

同窓会サービスのセキュリティ問題

前職の会社から同窓会ネットワークへの招待メールが届いた。退職はしたものの本当に素晴らしい会社・同僚・文化だと思っているので、同窓会に招待してもらったは大変うれしい。うれしいのだが・・・。

これが招待メール。社名と私の個人情報に関わる箇所は赤でマスクした。

"Alumni Network website" リンクをクリックすると、secure.imodules.com というサイトが開き、名前と旧従業員番号の入力を求められる。

問題は、このメールにもそのサイトにも、前職の会社(以下 G)との関係を証明するものが何もないということだ。メールやサイトのデザインは、見る人が見れば G 社のものだとすぐに分かるが、こういうものはほぼコスト0で完全にコピーできる。
サイト自体にはサイト証明書がついていて、Imodules Software Inc. という会社が運営していることがわかる。この会社が同窓会サービスを請け負ってるんだと思うが、そんな話は在職時には聞いたことがないので、Imodules Software に個人情報を渡していいのかどうか判断できない。

「あなたの従業員ナンバーを入力する必要があります」と書いてある。私の ID 確認も結構だが、そっちの(サービスの) ID も確認させてくれと言いたい。

私が退職したことや私の前職を知ってる人はそれなりにいるので、このタイミングでこういう phishing を仕掛けてるのはありそうな話だ。

まぁそうはいっても、私はこのサイトに登録することになるだろうと思う。前職の人とのネットワークは重要だし、(証拠は何も無いが)これが phishing であることはない「気がする」。G 社に電話して「これ本物ですか?」と聞くのもめんどうだ。

しかし、これこそが悪意の無い insecure なサービスによる最大の害であって、こういう経験を積むことで「セキュリティ、セキュリティって言ってるけど、そんなうるさいこと言わなくても全然問題ないよね」と感覚が麻痺して、いつの日か本当の詐欺にあうことになる。そういうユーザーを増やすことに加担している。

そもそもこれをセキュアにするのは難しい話ではない。G 社のサイト証明書つきのウェブサーバに「G 社は同窓会サービスを Imodules Software Inc. に委託しています。下のリンクをクリックすると Imodules Software Inc. のサイトにジャンプします」というページを用意し、招待メールからこのページにリンクすれば良い。
そうすれば、(G 社のサイトが不正に改竄されていない限り)Imodules の同窓会サービスの正当性を確認できる。

なんてことをここに書かずに、G 社に言うべきなんだろうけど。同窓会サービスに関するコンタクトを見つけたからメールするべきなのか? それもなぁ・・・。

zshとscreenを少し便利にした。主にgit向け。

メインの開発環境が git になり、かつ複数の作業を平行してやってるため、「あ、しまった。この変更はこのブランチじゃなかった」と今週だけで 3 回は叫び、git stash -> git checkout XXX -> git stash pop を繰り返してしまった。

会社の他の人のターミナルを盗み見ると、プロンプトの一部にブランチ名を表示している人が多かったので、やり方を調べてブログにまとめよう・・・と思ったが、すでに A Zsh prompt for Git users という素晴らしい記事があり、このとおりに設定できてしまったので、書くことがない。

現在のターミナルはこんな感じ。zsh であることを見せびらかすように、ブランチ名は右プロンプトに、目立つように赤で表示させた。ついでに時刻も表示させた。「この処理何分かかったっけ」と考えることがたまにあったので。普段は幅 180 カラムで使ってるので、これでも全然狭くない。
ついでに GNU screen のステータスバーの表示も少し見直した。直前のコマンドが "cd" なら異動先のディレクトリ名を表示、そうじゃなければコマンド名と第一引数を表示するようにした。ただし第一引数がハイフン '-' で始まる場合は引数は表示しない。(今考えるとこの特別扱い不要だな)

まず、GNU screen のステータスバーを表示するように .screenrc を設定する。
hardstatus alwayslastline "[%02c] %-w%{=b bw}%n %t%{-}%+w"

次に、preexec_update_screen_status というファイルを作り、
emulate -L zsh
local -a cmd; cmd=(${(z)2})
case $cmd[1] in
  cd)
      if [[ $#cmd -eq 2 ]]; then
        echo -n "^[k$cmd[2]^[\\"
      else
        echo -n "^[k$HOME^[\\"
      fi
      ;;
  *)
      if [[ $#cmd -eq 2 && ! ("$cmd[2]" =~ "-.*") ]]; then
        echo -n "^[k$cmd[1] $cmd[2]^[\\"
      else
        echo -n "^[k$cmd[1]^[\\"
      fi
      ;;
esac
と書いておく。"^[" はエスケープシークエンスなので注意。Emacs だと Ctrl+Q ESC で入力する。(このファイル自体もどこかからコピーした気がするが忘れてしまった)

ほとんど分かってないが、"^[k" と "^[\" で囲まれた文字列は、(普通に出力されるのではなく)ウィンドウのタイトルに設定されるようだ。で、hardstatus で設定した "%t" が、「ウィンドウのタイトルをステータスラインに表示する」という意味らしい。(余談だけど、エスケープシークエンス・コントロールシークエンスは複雑すぎて覚える気にならない)

最後に、この preexec_udpate_screen_status 関数を、コマンド実行直前に評価するように、以下の内容を .zshrc に追加する。
typeset -ga preexec_functions
case "$TERM" in
screen)
  preexec_functions+='preexec_update_screen_status'
  ;;
esac
$TERM で場合分けしないと、screen 使ってないときに表示が乱れる。

というようにツールを整備したので、来週は効率10倍で働いてコミット10倍します。あ、まだエイプリルフールじゃなかったか。来週は効率1.05倍で働いてコミット1.05倍します。[追記: 日本ではすでに 4/1 だった。]

zsh とか screen とかもっと便利に使える気がするが、あとどれだけ時間をかければ何が得られるのか分からないので時間のかけようがないのがつらいところだ。

2012年3月19日月曜日

Splay Tree への insert の amortized cost が O(log N) の証明

Purely Functional Data Structures の 5.4 で、Splay Tree に要素を insert すると、一回あたりの最悪計算量は O(N) ですが、amortized cost は O(log N) になる、という話の証明です。

まず insert の定義を確認します。

insert x t = let (a, b) = partition x t
             in T (a, x, b)

(partition は長いので省略します。テキスト (Purely Functional Data Structures) の P.50 or P.198 を見てください。)
partition のポイントは二段ごとに再帰していくこと。あるノードについて partition が呼ばれると、その中で、孫ノードに対して再帰的に partition が呼ばれます。なので、insert の計算量は O(N) となりますが、amortized cost が O(log N) となることを証明します。

始めにいくつか関数を定義します。
  • #t := t (tree) に含まれるノードの数 + 1
  • φ(t) := log(#t)
  • Φ(t) := sum $ map φ $ nodes t (t に含まれる全てのノードに対して φ を適用した結果の和)
次に partition の actual cost を T(t)、amortized cost を A(t) とすると、ポテンシャル関数 Φ(t) を使って次のような関係が成立します。
A(t) = T(t) + Φ(a) + Φ(b) - Φ(t)
ここで、a, b は、t について呼び出した partition の結果である sub-tree です。

補題として、A(t) <= 1 + 2φ(t) = 1 + 2log(#t) を示します (Theorem 5.2)。これが成り立つとすると、挿入後の tree を t' として、
[amortized cost of insert] = A(t) + 1 + Φ(t') - (Φ(a) + Φ(b))     (*1)
                                        = A(t) + 1 + φ(t')
                                        <= 1 + 2log(#t) + 1 + log(#t + 1)
                                         2 + 3log(#t)
(*1) insert の amortized cost は、partition の amortized cost と、データコンストラクタの適用と、ポテンシャルの変化の和
となり、insert の amortized cost が O(log N) であることがわかります。

さて、partition の再起呼び出しには zig-zig ケースと zig-zag パターンの 2 つがあります。(冗長に書くと、左の子を辿るのを zig, 右の子を辿るのを zag として、zig-zig, zig-zag, zag-zig, zag-zag の 4 パターンありますが、zig-zig と zag-zag, zig-zag と zag-zig は対称な操作なのでまとめて、zig-zig と zig-zag だけを考えます)

zig-zig ケースを考えます。下の図のようなツリーを考え、partition pivot s の結果 sub-tree u が二つに分かれて、a, b になったとします。

partition の amortized cost A(s) を展開していきます。
A(s) = T(s) + Φ(a) + Φ(s') - Φ(s)                                            (*2)
        = 1 + T(u) + Φ(a) + Φ(s') - Φ(s)                                     (*3)
        = 1 + A(u) - Φ(a) - Φ(b) + Φ(u) + Φ(a) + Φ(s') - Φ(s)   (*4)
        = 1 + A(u) - Φ(b) + Φ(u) + Φ(s') - Φ(s)                          (*5)
(*2) A の定義より
(*3) T(s) は、u に対して partition を呼んだコスト + 1
(*4) A の定義を T について整理したものを使って、T(u) を A(u), Φ, φ に置換
(*5) Φ(a) はキャンセル
ここで、Φ(s) と Φ(s') を φ を使ってできる限り展開すると、
Φ(s) = φ(s) + φ(t) + Φ(u) + Φ(c) + Φ(d)
Φ(s') = φ(s') + φ(t') + Φ(b) + Φ(c) + Φ(d)
となります。(b, c, d, u は内部構造が分からないので、φ で展開できないことに注意)

これを元の式に代入して整理すると、
A(s) = 1 + A(u) + φ(s') + φ(t') - φ(s) - φ(t)
となります。

u は s より小さい木なので、帰納法の過程より A(u)  <= 1 + 2φ(u) を代入すると、
A(s) <= 2 + 2φ(u) + φ(s') + φ(t') - φ(s) - φ(t)
u は t より小さく、s' は s より小さいので、φ(t) を φ(u) に置き換え、φ(s) を φ(s') に置き換えても式の大小関係は崩れない(φ(t), φ(s) の符号は負であることに注意)ので、
A(s) <= 2 + 2φ(u) + φ(s') + φ(t') - φ(s') - φ(u)
        < 2 + φ(u) + φ(t')
#u + #t' < #s なので、Lemma 5.1 (ここでは省略。テキスト参照のこと) より、
A(s) < 1 + 2φ(s) 
となり、証明終了となります。

zig-zag ケースの場合も、下図を参考にして式を展開をしていくと同じ結果が得られます。


数式を blog で書くのつらいなぁ・・・。