2015-01-19

最小二乗法のロバスト推定についてまとめた

統計学

　最近，研究とはほとんど関係ないところで統計学にハマっているので自己満でロバスト推定をやってみた．それからRのggplotモジュールで描けるグラフの美しさをみなさんに知ってほしい．

最小二乗法

　最小二乗法とは，測定で得られた数値に組を適当なモデルから想定される関数(ここでは1次関数)を用いて近似するときに，残差の二乗和を最小とするような係数を決定する方法である．残差とは，二変量の観測値（Xi, Yi）に対してその回帰式が y ＝ax + b で与えられるときの Yi - (aXi + b) の値をいう．
　近似直線の式を"y = ax + b"とした時のa, bは以下の行列計算によって求めることができる．

$\begin{pmatrix} \Sigma x_i^2 & \Sigma x_i \\ \Sigma x_i & \Sigma 1 \end{pmatrix} \begin{pmatrix} a \\ b \end{pmatrix} = \begin{pmatrix} \Sigma x_i y_i \\ \Sigma y_i \end{pmatrix}$

$\begin{pmatrix} a \\ b \end{pmatrix} = \begin{pmatrix} \Sigma x_i^2 & \Sigma x_i \\ \Sigma x_i & \Sigma 1 \end{pmatrix}^{-1} \begin{pmatrix} \Sigma x_i y_i \\ \Sigma y_i \end{pmatrix}$

　この辺は前提知識として扱うので，詳しくは「最小二乗法」でググって一番上に出てきたサイトを参照されたい．
最小二乗法について

　例えば，以下の様な分散図に対して最小二乗法で近似した直線が描ける．
f:id:sonickun:20150119215129p:plain

　ところが，計測の際に何らかの拍子でプロットが1つだけ大きく外れた値(外れ値)を取ると，以下の青色のグラフように近似が大きくずれる．
f:id:sonickun:20150119215615p:plain

　グレーの網掛けになっている部分は回帰モデルに対する95%信頼区間を表している(グレーの領域に95%の確率でプロットが存在するという意味)．外れ値がある方は分散が大きく，95%信頼区間も大きく広がってしまう．

　このような外れ値が最小二乗法に大きく影響を与えるという問題点を解決する方法として，ロバスト推定法がある．

ロバスト推定

　ロバスト推定とは，誤差があるデータに対してその誤差の影響を最小にすることを目的とした理論である．ここではロバスト推定法の中の「M推定法」を扱う(他にはL推定やR推定がある)．
　M推定法とは，二乗誤差基準では誤差が大きいほど値が大きくなるが，ある一定以上の誤差で値の上昇を抑えることで，外れ値による影響を小さくする方法である．最小二乗法のロバスト推定における誤差とは，近似した直線と各プロットとの距離のことをいう．また重み付けにはTukeyのBiweight推定法という手法を採用する．

　点(Xi,Yi)と近似直線との誤差をd = Yi - (aXi + b)，Wを誤差の許容範囲としたとき，誤差が大きいほど最小二乗に与える影響力を小さくするように，以下のような式を用いて重みw(d)を計算する．

$\begin{equation} w(d) = \left \{ \begin{array}{l} \Bigl\{1- (\cfrac{d}{W})^2 \Bigr\}^2　　　(　|d| \leq W　)\\ 0　　　　　　　　　　(　|d| > W　) \end{array} \right. \end{equation}$

　この重みの関数w(d)をグラフで表すと，以下のようになる．
f:id:sonickun:20150119225459p:plain
(引用:ロバスト推定法（Ｍ推定法）画像処理ソリューション)

　この重みWiを各近似データ(Xi、Yi)に関して計算し、Wiを付加した最小二乗法を再度行い，ロバスト推定による近似式y = a'x + b'のa', b'を求める．

$\begin{pmatrix} \Sigma w_i x_i^2 & \Sigma w_i x_i \\ \Sigma w_i x_i & \Sigma w_i \end{pmatrix} \begin{pmatrix} a' \\ b' \end{pmatrix} = \begin{pmatrix} \Sigma w_i x_i y_i \\ \Sigma w_i y_i \end{pmatrix}$

$\begin{pmatrix} a' \\ b' \end{pmatrix} = \begin{pmatrix} \Sigma w_i x_i^2 & \Sigma w_i x_i \\ \Sigma w_i x_i & \Sigma w_i \end{pmatrix}^{-1} \begin{pmatrix} \Sigma w_i x_i y_i \\ \Sigma w_i y_i \end{pmatrix}$

　ロバスト推定後のグラフは以下のようになる．
f:id:sonickun:20150119230933p:plain

　青いグラフのように外れ値による影響が抑えられ，測定データに近い直線が描けた．

　最終的に作成したRスクリプトは以下のとおり．

library(ggplot2)
library(MASS)

pdf("robust.pdf", width=8, height=4)

set.seed(123)          # allow reproducible random numbers
orig <- within(data.frame(x=1:10),
               {
                 type <- "orig"
                 y <- rnorm(x, mean=x)
               }
               )
outlier <- orig
outlier$y[2] <- 20
outlier$type <- "outlier"


theme_set(theme_grey(base_size = 16))  # increase default font etc. size

#p <- ggplot(orig,aes(x,y)) + geom_point(colour="#F8766D")
#p <- p + geom_smooth(method="lm", se=FALSE, colour="#F8766D")

p <- ggplot(data = rbind(outlier, orig), aes(x, y, colour=type, linetype=type)) + geom_point() # "base" plot, with points only
p <- p + geom_smooth(method = "rlm")         #  fit & plot *robust* model + envelope

print(p)
dev.off()

参考

2015-01-07

LaTeXでbibファイルのURLに関するエラーが発生する時の対処法

環境構築

　今まで論文を書くときはLatexのテンプレート的なものを使って何も考えずにコンパイルしていたので，今回変なところでつまづいてしまった．自分のための備忘録．

　Latexで参考文献(サイトのURL)を載せたいとき，例えば以下のようにbibファイルを作成する．

@misc{twitter,
  title = {{Twitter}},
  howpublished = {\url{http://twitter.com/}}
}

　コンパイルの際はbibファイルを元に以下の様なbblファイルが生成され読み込まれる．(自分の環境ではTeXworksかmakeコマンドを使っている)

\begin{thebibliography}{}

\bibitem[twi]{twitter}
``{Twitter}'', \url{http://twitter.com/}

\end{thebibliography}

　ところがこのbblファイルのurlの部分でUndefined control sequence.というエラーが発生してしまう．
　
　

解決策

　どうやらbibファイルのurlの書き方には次の2通りあるらしい．

howpublished = {http://twitter.com/}
howpublished = {\url{http://twitter.com/}}

　1の方法ではエラーは発生せず，2の場合にはエラーが発生する．このエラーは「url」というパッケージが入っていないために起こる．
　2の方法を用いるときは，styファイルに以下の一行を追加する．

\usepackage{url}

　これで正常にコンパイルが成功する．

　URLであることを明記するためには2の方法をとるのが望ましいと思われる．

2014-12-19

情報セキュリティスペシャリスト試験に合格した話

セキュリティ,資格セキュリティ,資格

　平成26年度秋期情報処理技術者試験にて，情報セキュリティスペシャリスト(SC)試験に合格しました．
　情報セキュリティスペシャリストは，IPAの情報処理技術者試験のレベル4にあたる高度試験のうち，セキュリティ分野に特化した国家資格です．
　今回の受験者平均年齢は36.2歳，合格率は14.4％(試験会場に到達できなかった人も含めると9.1％)でした．受験者はやはり実務経験のある社会人の方が殆どのようですが，自分の周りにはキャンパーの方など，学生の受験者も多い印象でした．
<a href="https://www.jitec.ipa.go.jp/1_11seido/sc.html">IPA 独立行政法人情報処理推進機構：制度の概要：情報セキュリティスペシャリスト試験</a>
IPA 独立行政法人情報処理推進機構：制度の概要：情報セキュリティスペシャリスト試験

　まずは成績から．平成26年度春期で応用情報技術者試験に合格したので，情報セキュリティスペシャリストの午前Ⅰは免除となりました．

f:id:sonickun:20141219185825p:plain
　
　午後ⅡのWEBの問題が解けなくてかなり心配しましたがギリギリボーダーを超えていました．その他は概ね想定内の成績です．

合格体験記

準備期間

　SCの勉強を始めたのは試験日のおよそ一ヶ月前です．ホントはもっと時間を取りたかったのですが，論文投稿などで忙しくて直前のスタートとなってしまいました．
　試験対策として，以下の2つの参考書を購入しました．

情報処理教科書情報セキュリティスペシャリスト 2014年版 (EXAMPRESS)

作者: 上原孝之
出版社/メーカー: 翔泳社
発売日: 2013/09/13
メディア: 単行本（ソフトカバー）
この商品を含むブログ (1件) を見る

ポケットスタディ情報セキュリティスペシャリスト第2版 (情報処理技術者試験)

作者: 村山直紀
出版社/メーカー: 秀和システム
発売日: 2014/05
メディア: 単行本
この商品を含むブログ (2件) を見る

　また，午前Ⅱの対策として「情報セキュリティスペシャリストドットコム」というサイトのWebアプリ過去問道場で，過去問の演習を行いました．
<a href="http://www.sc-siken.com/">情報セキュリティスペシャリストドットコム</a>
情報セキュリティスペシャリストドットコム

　まずは情報処理教科書を辞書代わりにしてひと通り読んだあと，サイトで過去問演習を行い，あとは時間の許す限りポケスタを繰り返し読み倒していきました．

ポケスタいい感じにボロボロになった http://t.co/usbPmirMLx
— そにっくん/sonickun (@y_hag) 2014, 10月 18

　この村山先生の「ポケスタ」には本当に助けられました．特に午後対策の「速効サプリ」では，出題・解答パターンがまとめられており，効率的に試験対策が出来ました．
　
　
　また，10月4日の江戸前セキュリティ勉強会では，村山先生の試験対策のお話も聞いてきました．（ちゃっかりサインも貰った）
<a href="http://togetter.com/li/728459">江戸前セキュリティ勉強会(2014/10) #edomaesec #edomae_asp</a>
江戸前セキュリティ勉強会(2014/10) #edomaesec #edomae_asp - Togetterまとめ

edomaesec_20141004_murayama from Naoki Murayama

edomaesec_20141004_murayama

そしてちゃっかり貰っていたサイン http://t.co/CV5oFd6rOo
— そにっくん/sonickun (@y_hag) 2014, 10月 18

@y_hag ああ，あなたでしたか！
— 村山直紀 (@MurayamaNaoki) 2014, 10月 18

試験当日

～試験直前～

明日は情報早起きスペシャリスト試験・・・
— そにっくん/sonickun (@y_hag) 2014, 10月 18

ﾌﾊﾊ起きれたぞ…!!
— そにっくん/sonickun (@y_hag) 2014, 10月 18

情報処理技術者試験最高難易度科目「時間までの会場への移動」が行われている
— ろ。＠ 3日目西く 20b (@kamiya344) 2014, 10月 18

ぼくの隣の席の受験者は毎回会場に到達できないの法則
— そにっくん/sonickun (@y_hag) 2014, 10月 19

～試験終了後～

各位お疲れさまでございました
— そにっくん/sonickun (@y_hag) 2014, 10月 19

がっつりバッファオーバーフローの問題出て白目剝いたけどなんとかなった
— そにっくん/sonickun (@y_hag) 2014, 10月 19

午後Ⅱは泣きながら全部埋めた…WEB力が足りなかった…
— そにっくん/sonickun (@y_hag) 2014, 10月 19

　会場への到達に成功したので合格はもらった！とおもいきや，午後ⅡでXSSやHSTSなどのWEB系の問題が解けずに大汗を書きました．WEB分野の対策が完全に不足していた．．．
　
　大事なことは全て徳丸本に書いてあった

体系的に学ぶ安全なWebアプリケーションの作り方　脆弱性が生まれる原理と対策の実践

作者: 徳丸浩
出版社/メーカー: ソフトバンククリエイティブ
発売日: 2011/03/03
メディア: 大型本
購入: 119人クリック: 4,283回
この商品を含むブログ (143件) を見る

　SCを受ける人は必ずこの本を読んでおくことをおすすめします．
　
　

合格発表

SC合格しました！
— そにっくん/sonickun (@y_hag) 2014, 12月 19

どうも，情報セキュリティスペシャリスト(初心者)です．
— そにっくん/sonickun (@y_hag) 2014, 12月 19

半年前にWiresharkの存在を知った人間でもここまでこれることを証明した．
— そにっくん/sonickun (@y_hag) 2014, 12月 19

　村山先生からもお祝いのお言葉を頂きました．

@y_hag おめでとうございます！
— 村山直紀 (@MurayamaNaoki) 2014, 12月 19

まとめ

　情報セキュリティスペシャリスト試験は，私のような実務経験のないぽっと出の大学生でもある程度テクニックを身につけて勉強すれば十分合格できるということを証明できたと思います．
　また午後の文章題は国語の問題といわれることもあり，知識がなくとも文章をじっくり読めば解ける場合があるので，最後まで諦めずに解ききることが大事だと思います．
　
　今後は他のスペシャリスト資格の取得を目指して頑張りたいと思います．
　
　

リンク

<a href="http://sonickun.hatenablog.com/entry/2014/06/25/163722">応用情報技術者試験合格体験記 - sonickun.log</a>
応用情報技術者試験合格体験記 - sonickun.log

2014-12-08

SECCON CTF 2014 Online Qualifications Write-Up

セキュリティ CTF

　SECCON 2014 オンライン予選(英語)にチームm1z0r3(みぞれ)として参加しました．結果は2100点で1067チーム中65位．完敗です．世界の壁は高かった...
　ただ，m1z0r3は国内予選6位で既に全国大会の切符を手に入れているので，本番までにもっと力を蓄えていきたいです．

　今回のSECCONで自分が解答した or 解答に携わった問題のWrite-Upを書きます．実際大した問題はあまり解いていない．鮮やかにHeartBleedの攻撃とかやりたかったです(HearBleedはリーダーが解いてくれた)．
　
<a href="http://ctf.seccon.jp/ranking.html">SECCON CTF 2014 Online Qualifications (32 Hours)</a>
SECCON CTF 2014 Online
　

はじまった！！！ #seccon
— そにっくん/sonickun (@y_hag) December 6, 2014

Reverse it (Binary, 100)

　"Reverseit"というファイルが渡される．fileコマンドを打つと"data"とだけ．さっそくバイナリを上から下まで眺めていると終端が"FF 8D FF"になっている．
　これどこかで見たことある......と思ったら"FF D8 FF"はJPEGの先頭のマジックナンバーであること気づく．先頭のバイナリに戻って見てみると"9D FF"...JPEGの終端のバイナリは"FF D9"...
　どうやらJPEGのバイナリが4bit(16進数1桁)ごと逆順に並んでいるよう．"Reverse it"とはこのことか(笑) Pythonでコードを書いて並び替える．

f = open("Reverseit","rb").read()
g = open("Reverseit.jpg","wb")

f = f.encode('hex')[::-1].decode('hex')

g.write(f)
g.close()

　生成したファイルを開くとこの画像．またもやReverseになっている．
f:id:sonickun:20141207224641j:plain
　ということでこれも逆さにして，フラグはSECCON{6in_tex7}．バイナリからすぐマジックナンバーを思い出せたのは嬉しかった．
　
　
　

REA-JUU WATCH (Web, 200)

　問題文のURLにアクセスすると「リア充ウォッチ」という，なんとも愉快で不愉快なWEBアプリが現れる．
　 f:id:sonickun:20141207225243p:plain
　次の画面でIDとパスワードが生成され，ログインすると次のような問題が始まる．
　 f:id:sonickun:20141207225256p:plain
　6問ほど回答すると，リザルト画面に自分のリア充度スコアが表示される．
　 f:id:sonickun:20141207225302p:plain

　FiddlerでHTTPリクエストを眺めていると，最後の問題を解いた後，別のURL(http://reajuu.pwn.seccon.jp/users/chk/[id])にもアクセスしている．[id]にはユーザーIDに対応した数字が入っているよう．試しにid=1にして，1番目のユーザーのところへつなぎに行くと，以下の文字が出現する．

{"username":"rea-juu","password":"way_t0_f1ag","point":99999}

　このようにユーザーの名前，パスワード，ポイントの情報が表示される．この情報を用いてもう一度ログインして問題に解答し，リザルト画面へ行くとフラグが現れた．
f:id:sonickun:20141207230211p:plain
　ということで晴れて真のリア充になることができた．フラグはSECCON{REA_JUU_Ji8A_NYAN}．

Get the key.txt (Forensics, 100)

　"forensic100"という名前のシステムファイルデータが渡される．FTK-Imagerでマウントして見てみる．すると，中身に"key.txt"とあるファイルを見つける．
f:id:sonickun:20141207231543p:plain
　先頭バイナリ"1F 8B"を見た瞬間にgzipだと気づいたので，このファイルをエクスポートして解凍するとフラグが得られた．
　フラグ→SECCON{@]NL7n+-s75FrET]vU=7Z}
　
　　
　

Get the key (Network, 100)

　nw100.pcapというpcapログが渡される．

だーっと眺めているとHTTP通信をしているよう．(10秒)
とあるURLにアクセスしている(中には"key.html"ヘのリンクが含まれている)．（20秒）
実際にアクセスするとBasic認証が必要みたい．（30秒）
pcapにもどり，BASE64でエンコードされた認証データを抜き出す．(40秒)
BASE64をデコードし，IDとパスワードを取得．（50秒）
Basic認証を突破しkey.htmlにアクセスしてフラグゲット．（1分）

　瞬殺でした．フラグ→SECCON{Basic_NW_Challenge_Done!}

　フレーム番号21番のパケットのHTTPヘッダーが以下のようになっている．

Hypertext Transfer Protocol
    GET /nw100/ HTTP/1.1\r\n
        [Expert Info (Chat/Sequence): GET /nw100/ HTTP/1.1\r\n]
            [GET /nw100/ HTTP/1.1\r\n]
            [Severity level: Chat]
            [Group: Sequence]
        Request Method: GET
        Request URI: /nw100/
        Request Version: HTTP/1.1
    Accept: text/html, application/xhtml+xml, */*\r\n
    Accept-Language: ja-JP,en-US;q=0.5\r\n
    User-Agent: Mozilla/5.0 (Windows NT 6.1; WOW64; Trident/7.0; rv:11.0) like Gecko\r\n
    Accept-Encoding: gzip, deflate\r\n
    Host: 133.242.224.21:6809\r\n
    Authorization: Basic c2VjY29uMjAxNDpZb3VyQmF0dGxlRmllbGQ=\r\n
        Credentials: seccon2014:YourBattleField
    Connection: Keep-Alive\r\n
    DNT: 1\r\n
    \r\n
    [Full request URI: http://133.242.224.21:6809/nw100/]
    [HTTP request 1/1]

　http://133.242.224.21:6809/nw100/へ接続している．
　"Basic c2VjY29uMjAxNDpZb3VyQmF0dGxlRmllbGQ="とあるので，これをBASE64 エンコードすると"seccon2014:YourBattleField"となる．つまりBasic認証のユーザー名が"seccon2014"，パスワードが"YourBattleField"となる．

Get from curious "FTP" server (Network, 300)

　FTPサーバのURLが渡される．ここにアクセスしてフラグとなるファイルをダウンロードしてくる問題らしい．
　さっそくアクセスして，ディレクトリ情報を取得しようとしたが，lsやdirなどの，いわゆるLISTコマンドが使えない．

$ ftp ftpsv.quals.seccon.jp
Connected to ftpsv.quals.seccon.jp.
220 (vsFTPd 2.3.5(SECCON Custom))
Name (ftpsv.quals.seccon.jp:****): anonymous
331 Please specify the password.
Password:
230 Login successful.
Remote system type is UNIX.
Using binary mode to transfer files.
ftp> ls
200 PORT command successful. Consider using PASV.
502 LIST not implemented.
ftp> dir
200 PORT command successful. Consider using PASV.
502 LIST not implemented.
ftp> quote list
502 LIST not implemented.

　"502 LIST not implemented."とは，つまりLISTコマンドが実装されていないという意味．ほかにもNLSTなどのコマンドも使えない．この状態でどうやってディレクトリ情報を取り出すかがこの問題のミソとなっている．また，get ./*のようにワイルドカード(*)を使用することもできないようになっている．

　他の使えそうなコマンドを探してみる．以下のサイトを参考にした．

FTPのコマンド一覧

　このサイトを見てみるとSTATコマンドの説明に「現在のシステムや転送状態の情報を表示する。ファイル／ディレクトリ名が与えられた場合は、その情報を表示する（NLSTなどとほぼ等価）」とある．そこでquote stat /を実行してみるとディレクトリ情報が取得できた．

ftp> quote stat /
213-Status follows:
drwxr-xr-x    2 0        107          4096 Nov 29 04:43 .
drwxr-xr-x    2 0        107          4096 Nov 29 04:43 ..
-rw-r--r--    1 0        0              38 Nov 29 04:43 key_is_in_this_file_afjoirefjort94dv7u.txt
213 End of status
ftp> get key_is_in_this_file_afjoirefjort94dv7u.txt
200 PORT command successful. Consider using PASV.
150 Opening BINARY mode data connection for key_is_in_this_file_afjoirefjort94dv7u.txt (38 bytes).
226 Transfer complete.
38 bytes received in 0.000115 seconds (330434 bytes/s)

　ということで，"key_is_in_this_file_afjoirefjort94dv7u.txt"をgetでダウンロードして開くとフラグが得られた．
　フラグ→SECCON{S0m3+im3_Pr0t0c0l_t411_4_1i3.}

version2 (Network, 200)

　「もうすぐ version 2 が来るけど準備はいいかい？」という問題文で，さらに「srv h2o.pwn.seccon.jp.」とドメインが与えられる．雑魚なのでこの時点で「version 2」が何のことが分かっていない．とりあえず「srv」とは何なのかを調べる．
　SRVとはDNSに含まれるレコードの一つで，動いているサービスやプロトコル，使用しているポート番号などの情報を保持しているらしい．SRVテーブルの情報はnslookupを用いて以下の様なコマンドで取得することができる．

$ nslookup
> set type=srv
> h2o.pwn.seccon.jp
Server:         10.1.2.1
Address:        10.1.2.1#53

Non-authoritative answer:
*** Can't find h2o.pwn.seccon.jp: No answer



Authoritative answers can be found from:
seccon.jp
        origin = ns1.value-domain.com
        mail addr = hostmaster.seccon.jp
        serial = 1417939413
        refresh = 16384
        retry = 2048
        expire = 1048576
        minimum = 2560
> _http._tcp.h2o.pwn.seccon.jp
Server:         10.1.2.1
Address:        10.1.2.1#53

Non-authoritative answer:
_http._tcp.h2o.pwn.seccon.jp    service = 1 1 65080 h2o.pwn.seccon.jp.

Authoritative answers can be found from:
> _https._tcp.h2o.pwn.seccon.jp
Server:         10.1.2.1
Address:        10.1.2.1#53

Non-authoritative answer:
_https._tcp.h2o.pwn.seccon.jp   service = 2 0 65432 h2o.pwn.seccon.jp.

Authoritative answers can be found from:

　SRV，nslookupに関して参考にしたサイト

　以上のことから，h2o.pwn.seccon.jp.では，65080番ポートでHTTP，65432番ポートでHTTPSが動いていることがわかった．実際にこのポートを指定してHTTP接続してみると以下の様なページが表示される．
f:id:sonickun:20141207235607p:plain
　この時点で「version 2」とはHTTP/2のことであると気づく．　
　HTTP/2 - Wikipedia, the free encyclopedia
　要はこのページにHTTP/2で接続すれば良い．Chrome ChromeのSPDYではHTTP/2が実装されている．HTTP/2の設定を有効にして接続すると以下の様なページが表示される．（HTTP/2はSSL必須なのでHTTPSで繋ぎに行く）
　 f:id:sonickun:20141207235940p:plain
　「HPACK」とはデータの圧縮形式の一つで，HTTP/2で通信を行う際はこの形式でデータを圧縮して送信しているらしい．
　Chromeのデベロッパーツールでレスポンスヘッダを見てみたらフラグの書かれているヘッダが含まれていた．
　 f:id:sonickun:20141208000247p:plain
　ということで，フラグはSECCON{spdy4isSoC001}

　HTTP/2，SPDYに関して参考にしたサイト

　余談だが，自分の代わりにHTTP/2でWEBサイトにつなぎに行ってくれるサービスもあったらしい．

HTTP2CAT

f:id:sonickun:20141208000850p:plain

所感

　前回の国内予選から約半年間で，ある程度成長が実感できた．自分の知識や経験則からある程度攻略が楽になった問題もあったし，瞬殺すべき問題はきっちり瞬殺できたのもよかった．ただ，CTFを始めて数ヶ月の雑魚には変わりはないので，今後は自分の得意分野を伸ばして全国大会でも戦える力をつけていきたい．あとCTFはやっぱり楽しい．ちなみに近々チーム内CTFが開催されるのでとても楽しみです．
　

2014-11-12

確率的情報検索 Okapi BM25 についてまとめた

研究

　ひょんなことで情報検索の知識が必要になったので，勉強したことを簡単にまとめておきます．

　情報検索とは，コンピュータを用いて大量のデータ群から目的に合致した物を取り出すことです．
　Okapi BM25は情報検索における文章中の単語の重み付けの手法の一つであり，他にもTF-IDFと言ったアルゴリズムがあります．

　Okapi BM25 - Wikipedia, the free encyclopedia

　一般的にはTF-IDFよりも良い結果が得られると言われ，比較手法としてのベースラインになっています．
　
　

Term Frequency (TF)

　文書中において出現頻度の高い単語は重要であるという考え方です．
　ある単語Tiの文書Dj中における重みを考えると

TF(i,j) = (文書Djにおける単語Tiの出現回数) / (文書Djのの総単語数)

　となります．
　
　

Inverse Document Frequency (IDF)

　多くの文書において出現頻度の高い単語は重要ではないという考え方です．

n = 単語Tiが出現する文書数
N = 文書の総数
としたとき
IDF(i) = log(N) - log(n) = log(N/n)

　となります．
　ちなみに，TFとIDFをかけ合わせるとTF-IDFの式となり，文書とクエリの特徴ベクトルの内積から類似度を評価することができます．BM25はこのTF-IDFをさらに改良したものとなります．
　
　

Document Length (DL)

　これがDM25のミソとなってきます．
　ある単語の出現回数が同じ2つの文書について，総単語数の少ない文書と多い文書では，前者のほうがより価値があると考えます．

DL(j) = 文書Djの総単語数
としたとき
NDL(j) = DL(j) / (すべての文書の平均DL)

　となります．
　
　

Okapi BM25b (Combined Weight)

　これまでの3つの重み付けをインプットとして，BM25のCombined Weight(CW)を作ります．

CW(i,j) = [ TF(i,j) * IDF(i) * (K1 + 1) ] / [ K1 * (1 - b + (b * NDL(j)) + TF(i,j) ]

　となります．定数K1とbについて以下に説明します．これらはどちらもチューニングの役割を果たします．

　K1は単語の出現頻度による影響を調節します．1 < k1 < 2 で，K1 = 2が最も効果的と言われています．
　bは文書の長さによる影響を調節します．0 < b < 1で，b = 0.75が効果的と言われています．

　まとめると，この式でより大きく重み付けされるのは

文書における単語の出現頻度の高いもの
多くの文書における単語の出現頻度が低いもの
より短い文書において出現回数が大きいもの

　となります．

参考

2014-11-05

tkbctf4 みんなのWrite-upまとめ

CTF セキュリティ

　tkbctf4参加者の皆さんのWrite-upをまとめました．新しいWrite-upが公開され次第随時更新していく予定です．
<a href="http://tkbctf.info/">tkbctf</a>
tkbctf

問題一覧

No.	Title	Genre	Score
1	monochrome bar	steganography	100
2	rcrypto	cryptography	200
3	high-low	cryptography	400
4	high-low2	cryptography	400
5	gradius	binary	100
6	Simple Serial Code	binary	200
7	Just Do It ?	binary	200
8	rakuda	binary	300
9	Cheer of CPU	binary	300
10	fourbytes	binary	500
11	rand	javascript	200
12	args	javascript	200
13	amida	misc	400
14	ITF point system	web	300

Write-up

　上の問題一覧の表の番号が対応しています．
　「途中まで解いた」または「あとで書く」とあった問題は△で表記しています。

Write-up	1	2	3	4	5	6	7	9	10	11	12	13	14
電気通信大学MMA	○	○	○	○	○	○		○	△	○	○	○	△
kusano_k’s blog	○	○	○		○	○	○			○	○		○
mt_caret.blog		○
st98's Gists	○				○					○	○	△
わふぅ。		○	○
misodengakuのブログ						○
aki33524の日記	○				○		○		○
math314のブログ		○										○
jujube2333's Gists	○	○			○		○
sonickun.log		○
[:title=]
[:title=]
[:title=]

　
tkbctf4問題のソースコードはこちら
<a href="https://github.com/tkbctf/tkbctf4">tkbctf/tkbctf4</a>
tkbctf/tkbctf4 · GitHub
　
記事の間違い，新しいWrite-upの情報等ありましたらsonickun@y_hagまでお知らせください．
　

その他 Write-up まとめ

<a href="http://sonickun.hatenablog.com/entry/2014/07/20/190238">SECCON 2014 CTF オンライン予選みんなのWrite-upまとめ - sonickun.log</a>
SECCON 2014 CTF オンライン予選みんなのWrite-upまとめ - sonickun.log

2014-11-03

tkbctf4 Write-up rcrypto (cryptography200)

CTF セキュリティ

　tkbctfにチームm1z0r3として参加しました．結果は600点で71チーム中15位．自分が解いたのはrcryptoの1問だけでした．（つらい）
　javascriptの2問が解けそうで解けなかったのが悔しかったです．引き続き解いてみてWrite-upを書こうと思います．

rcrypto (cryptography200)

　encrypto.pyとresul.txtの2つのファイルが渡されます．

encrypto.py

import struct

N = 0xcd892c64f1803742a89e68567aea60283066b368d2c2454ad55f740fb0ff8e98e03f70cd9a2c9168294eee89a9f995d2596f2c0be881bfbfa72cccbb18a77287134e2ffc89e7bce766cca9136074a19f6807c3ff51e5cf53ec79838067cbefac809fccbbe2c1c4d170f3be58b34b9c3dfaeb2914341697d6503a826716073f9808b91c747030e2cdeaf20620b269c701d5ce96623c95c983678fd1175243b9eda7f6a310b4ccfd6c69fa836adb82271c56aa7ca267c1d47e64e69a0c3541f63432b4d75b881c1694a07b546eaee036521213967201cd91ff6a4e1e7c89027eb57096f2e3e5cd274d5cd272be44435b21648538f31760b4f8b50cbcd42f0873d5

def encrypt(M, B):
    return M * (M + B) % N

if __name__ == '__main__':
    s = open('flag', 'r').read()
    tkbctf = struct.unpack('<2I', 'tkbctf4\0')
    flag = int(s.encode('hex'), 16)
    print "1: %d" % encrypt(flag, tkbctf[0])
    print "2: %d" % encrypt(flag, tkbctf[1])

result.txt

1: 2302864379938375384787522457289953058762346515694717964988017701221632252068998721016780659512789645178039929483162432085291148128875938650563974652974607897108753247761759018159346471819526717450317624121005691577913298753406802656066710989103644069541226797561238591832001786871030959032526532824897381416113004865029523158041337929652792421367459253385313006702525506606665513325657107841851439410104118856833250549528309345600994438901026890993789031255524302387252820866177521016309668779564405438776186649089481716393902512049059686799788362854701624870108840227739233423565617147635810535089953364777452765391
2: 869821841437664579273841208702057334636310328092375384661895122870843280009327763942775667106913326453781559554453279690395959752854296081023254897131426262762124201024166059200347755016000992120349762030587256929453375758557293418778029046615012379759165445526510048231152939113590563355048407714266168812177988203610092674509339069396233061882191910214456155546393848777696938097852335164090584476493820466258280954729469300306911409684786367255431603152145902151223834708442564731418184393252984714050882676106734102146980036229108895568198263271905480015122766218776429803994468521463000793677542363327966917714

　encrypt.pyで暗号化された結果がresulet.txtに出力されています．暗号化前の平文がフラグになっているようです．
　暗号アルゴリズムは，平文(フラグ)をM，鍵をB,N，暗号文をRとすると

R = M * (M + B) (mod N)

　となっています．暗号化というよりハッシュっぽいですね．
　この式から単純にMを導くことは不可能ですが，今回はこの暗号化が以下のように2パターンあります．青字が既知の値で，赤字が未知の値です．

R1 = M * (M + B1) (mod N)　・・・①
R2 = M * (M + B2) (mod N)　・・・②

　この2式から未知の値Mを推定します．
　R1>R2かつB1>B2のとき，①式から②式を減算すると

R1 - R2 = M( B1 - B2 ) (mod N)

　が成り立ちます．（証明は省略）
　つまり

M( B1 - B2 ) - ( R1 - R2 ) = kN　　　　(kは自然数)
⇒ M = {kN + ( R1 - R2)} / (B1-B2)

　となりM=の式が出来ます．この式において，Mが整数になるようにkをブルートフォースします．
　作成したスクリプトがこちら．

import struct

tkbctf = struct.unpack('<2I', 'tkbctf4\0')
t=tkbctf[0]-tkbctf[1]

R1=2302864379938375384787522457289953058762346515694717964988017701221632252068998721016780659512789645178039929483162432085291148128875938650563974652974607897108753247761759018159346471819526717450317624121005691577913298753406802656066710989103644069541226797561238591832001786871030959032526532824897381416113004865029523158041337929652792421367459253385313006702525506606665513325657107841851439410104118856833250549528309345600994438901026890993789031255524302387252820866177521016309668779564405438776186649089481716393902512049059686799788362854701624870108840227739233423565617147635810535089953364777452765391
R2=869821841437664579273841208702057334636310328092375384661895122870843280009327763942775667106913326453781559554453279690395959752854296081023254897131426262762124201024166059200347755016000992120349762030587256929453375758557293418778029046615012379759165445526510048231152939113590563355048407714266168812177988203610092674509339069396233061882191910214456155546393848777696938097852335164090584476493820466258280954729469300306911409684786367255431603152145902151223834708442564731418184393252984714050882676106734102146980036229108895568198263271905480015122766218776429803994468521463000793677542363327966917714
x=R1-R2

N=0xcd892c64f1803742a89e68567aea60283066b368d2c2454ad55f740fb0ff8e98e03f70cd9a2c9168294eee89a9f995d2596f2c0be881bfbfa72cccbb18a77287134e2ffc89e7bce766cca9136074a19f6807c3ff51e5cf53ec79838067cbefac809fccbbe2c1c4d170f3be58b34b9c3dfaeb2914341697d6503a826716073f9808b91c747030e2cdeaf20620b269c701d5ce96623c95c983678fd1175243b9eda7f6a310b4ccfd6c69fa836adb82271c56aa7ca267c1d47e64e69a0c3541f63432b4d75b881c1694a07b546eaee036521213967201cd91ff6a4e1e7c89027eb57096f2e3e5cd274d5cd272be44435b21648538f31760b4f8b50cbcd42f0873d5

k=1
while(1):
	if (k*N+x)%t==0:
		print (k*N+x)/t
		break
	else:
		k+=1
	print k

Result

k=569111799
M=8874284088105576854948238238614457044505028639011349374021861498995036023097152049555857239549350287166006347100199983957544356840501980854784901113821946197380611177705292212987004478484951309819182405098846767765333862409425926812573611864910204824928321142829182839508679805462040296761411851272619037561124670207800113160725445151643233355853069817035845548582628939322952705418085312089629008831113802005771457751200233715401850140367028206001736592528758851066145310031045563613680644635600425736132514865977264503188118025685603053077990165729300195014737832785024786331903041102248425142311946913492026078519

　計算に1時間以上かかりました．（途中何度諦めかけたことか・・・）
　きっともっと効率のいい解法があると思います．

　あとは得られたMをASCII文字に変換するだけ．

$ python
>>>a=8874284088105576854948238238614457044505028639011349374021861498995036023097152049555857239549350287166006347100199983957544356840501980854784901113821946197380611177705292212987004478484951309819182405098846767765333862409425926812573611864910204824928321142829182839508679805462040296761411851272619037561124670207800113160725445151643233355853069817035845548582628939322952705418085312089629008831113802005771457751200233715401850140367028206001736592528758851066145310031045563613680644635600425736132514865977264503188118025685603053077990165729300195014737832785024786331903041102248425142311946913492026078519
>>> s = hex(a)[2:]
>>> z=''
>>> for i in range(0, len(s), 2):
...   z += chr(int( (s[i]+s[i+1]), 16))
...
>>> z
'FLAG{R4b1n cryp705y573m 15 v3ry 1n73r3571ng!!!}FLAG{R4b1n cryp705y573m 15 v3ry 1n73r3571ng!!!}FLAG{R4b1n cryp705y573m 15 v3ry 1n73r3571ng!!!}FLAG{R4b1n cryp705y573m 15 v3ry 1n73r3571ng!!!}FLAG{R4b1n cryp705y573m 15 v3ry 1n73r3571ng!!!}FLAG{R4b1n cryp705y57'

　ということで，フラグはR4b1n cryp705y573m 15 v3ry 1n73r3571ng!!!でした．
　
　ほぼ数学の問題でした．