Atomでconfig.fishをハイライトさせる

zshからfishに移行している最中にconfig.fishAtomでハイライトされていなかったのでさせました。 単純に拡張子とscope nameを対応させるだけですが、fishを検索ワードにしてると意外と引っかからなかったのでメモ書きとしてまとめておきます。

事前準備(file-typesのインストール)

Atomを開き、cmd + ,でPreferenceを開きます。 Installからfile-typesパッケージを検索し、インストールします。

config.csonの編集

以下のように設定します。 恐らく$HOME/.atom/config.csonにあるかと思います。

"*":
  "file-types":
    fish: "source.shell"

上記編集後、保存すれば設定が反映されます。

Reference

GolangでCuckoo Hashingを実装してみた

2017/5/27 修正
int64型であるkey[]byte型へconvertする際にhasher.Write([]byte(string(key)))ではうまくいかないため以下のように修正しました。

b := make([]byte, 8)
binary.LittleEndian.PutUint64(b, uint64(key))

hasher.Write(b)

背景

BloomFilterを実装した後に、やろうやろうと思っていたCuckoo Hashingを実装してみました。
Cuckoo Hashing自体の説明は @_krzさんの記事がわかりやすいです。絵を交えられているのでイメージもつきやすいです。
メリットとしてはlookupが定数時間(2回比較するだけ)で完了することが挙げられます。
またアルゴリズム自体がわかりやすいです。2つのテーブルを用意しておき、挿入したいkeyハッシュ値を計算し、ハッシュ値をindexとみて、テーブルが空いていれば挿入。すでに埋まっていれば、keyと既に入っていた値を交換して、もう一つのテーブルで同様の操作を繰り返すという流れになっています。カッコーの托卵のようですね。

デメリットは、ハッシュの衝突が起こった場合やループが無限ループに入る恐れがあります。今回の実装でもMAXLOOPを設定することで無限ループを防いでいます。 また、こちらによるとテーブルの半分が埋まった段階で性能が落ちてしまうそうです。

実装

gistaaf77c63f3668efdd44e2f4ae9642f76

今回は0を空とする実装にしましたが、実際には0を挿入したい場合も多いと思うので、その場合はうまくゼロ値を使うなどするのがよいと思います。

References

Golangで有向グラフをかく

背景

言語処理100本ノック 2015をやっている最中に、有向グラフで表示する問題(Q44)に遭遇しました。 gographvizでDOT言語のdotファイルを作成し、graphvizで可視化したのでまとめます。

動作環境

# sw_vers
ProductName:    Mac OS X
ProductVersion: 10.11.6
BuildVersion:   15G31

# go version
go version go1.8 darwin/amd64

# dot -V
dot - graphviz version 2.40.1 (20161225.0304)

インストール

graphvizのインストール

# brew install graphviz

gographviz packageのインストール

# go get github.com/awalterschulze/gographviz

有向グラフの作成

設定値などはGraphvizとdot言語でグラフを描く方法のまとめを参考にさせて頂きました。

gist4c915c1e14aae064a92cc30fbcb5eac7

dotファイル上で、Attributionにダブルクオーテーションが必要な場合は、エスケープしないとsyntaxエラーになるので注意してください。
また、今回のように事前のテストができる場合は問題ないですが、Attrを動的に設定するような場合は、以下のようにエラーチェックをしたほうがよいでしょう。

// 例) colorschemeを設定する場合
if _, err := gographviz.NewAttr("colorscheme"); err != nil {
    panic(err)
}
nodeAttrs["colorscheme"] = "rdylgn11" // 問題ないことを確認してからmapに格納する

出力のdotファイルは以下のようになります。

gistc0bdfb47ec6948b6bed5cd51ad92f05c

有向グラフの出力

噂のGraphvizを使ってみるにもありますが、上記で出力したdotファイルをもとに、pngファイルとして結果を出力させるには以下のようにします。

# dot -T png diGraph.dot -o diGraph.png

結果です。いい感じですね。

f:id:cipepser:20170422201356p:plain

Reference

Golangで言語処理100本ノック2015 第4章: 形態素解析

言語処理100本ノック 2015の第4章: 形態素解析の10問です。

前処理

mecabの処理は先に済ませておきます。

# mecab neko.txt -o neko.txt.mecab

30. 形態素解析結果の読み込み

形態素解析結果(neko.txt.mecab)を読み込むプログラムを実装せよ.ただし,各形態素は表層形(surface),基本形(base),品詞(pos),品詞細分類1(pos1)をキーとするマッピング型に格納し,1文を形態素マッピング型)のリストとして表現せよ.第4章の残りの問題では,ここで作ったプログラムを活用せよ.

gistc6be3f30935d9f1032cb8dd29b3a6f8e

# go run q30.go
[map[base:  pos:記号 pos1:空白 surface: ] map[pos:名詞 pos1:代名詞 surface:吾輩 base:吾輩] map[pos1:係助詞 surface:は base:は pos:助詞] map[base:猫 pos:名詞 pos1:一般 surface:猫] map[pos:助動詞 pos1:* surface:で base:だ] map[pos1:* surface:ある base:ある pos:助動詞] map[surface:。 base:。 pos:記号 pos1:句点]]

mecabの結果は形態素ごとに一行で出力されるのでReadLine()で読み取っています。 例として「 吾輩は猫である。」を表示させています。

31. 動詞

動詞の表層形をすべて抽出せよ.

gist0230b9eddcac1d6541935856342866ba

# go run q31.go
[生れ つか し] [死な 得 られ]

Q30をそのまま利用すれば余裕です。結果が長くなるので最初と最後の3つだけ標準出力させました。

32. 動詞の原形

動詞の原形をすべて抽出せよ.

gist015db5a66878a77df992821b075ab8b5

# go run q32.go
[生れる つく する] [死ぬ 得る られる]

Q31とほぼ同じです。

33. サ変名詞

サ変接続の名詞をすべて抽出せよ.

gistc2c9fe26605d803583db6ee4b26f6f00

# go run q33.go
[見当 記憶 話] [抵抗 見当 判然]

こちらもQ31とほぼ同じです。

34. 「AのB」

2つの名詞が「の」で連結されている名詞句を抽出せよ.

gist120cb467e3a271b9bfbd55af9ca1b868

$ go run q34.go
[彼の掌 掌の上 書生の顔] [水の中 座敷の上 不可思議の太平]

「の」が出てきた前後が名詞になるものを抜き出しています。 気をつけるのはindex out of rangeのruntime errorを出さないことでしょうか。

35. 名詞の連接

名詞の連接(連続して出現する名詞)を最長一致で抽出せよ.

gistf15b4cadbae765b94f4abf99b771ae39

# go run q35.go
[吾輩 猫 名前] [太平 太平 南無阿弥陀仏南無阿弥陀仏]

名詞が続く間はループ回しています。 標準出力させながらコード書いてましたが、意外なもの(非自立や接尾の名詞)が出力され、間違っているのでは?と微妙にハマりました。そもそも国語力というか日本語の弱さが問題です。。。

36. 単語の出現頻度

文章中に出現する単語とその出現頻度を求め,出現頻度の高い順に並べよ.

gistc5f254f78da7fd7774c6513726607a71

# go run q36.go
の 9194
。 7486
て 6848
、 6772
は 6420
に 6243
を 6071
だ 5975
と 5508
が 5337

mapは順序を保存してくれないので、擬似的なTreeMapとしてsortedMap型を用意しました。ほぼこちらを参考にしました。
上位10個を抜き出してみましたが、固有名詞がないですね。。。

37. 頻度上位10語

出現頻度が高い10語とその出現頻度をグラフ(例えば棒グラフなど)で表示せよ.

gist5f74bc0a182cfa616d5f270037ac4d17

実行結果

f:id:cipepser:20170325103521p:plain

gonum/plotが日本語サポートしていないのでX軸にどの単語だが、表示されないのが微妙ですね。。。出力しているのはQ36と同じですが。 棒グラフの書き方は以前記事にまとめました。

38. ヒストグラム

単語の出現頻度のヒストグラム(横軸に出現頻度,縦軸に出現頻度をとる単語の種類数を棒グラフで表したもの)を描け.

gistc2bdc1b97162a49e390991bd454d45c5

実行結果

f:id:cipepser:20170325125720p:plain

英語だとちゃんと軸名が表示されます笑 題意の単語が何を指しているのか戸惑って、問題文理解するのに時間掛かりました。。。

39. Zipfの法則

単語の出現頻度順位を横軸,その出現頻度を縦軸として,両対数グラフをプロットせよ.

gista037ce443bd2066f6061ce91a8167630

実行結果

f:id:cipepser:20170325172053p:plain

Q38を流用するとすぐですね。

感想

言語処理をやったことがなかったので、そもそもの用語を知らなくて戸惑うことが多かったです。このまま5章の係り受け解析も頑張ります。

いつも通りコードはGithubにも置いてあります。

Reference

Golangのmath/bigでIntを直接入力したい

背景

Golangの基本型であるint64では 64 \times log_{10} 2 \approx 64 \times 0.3 = 19.2のため20桁程度(※)でoverflowを起こします。そのため、math/bigパッケージのNewIntを使おうとするとoverflowのコンパイルエラーになります。

※正確には、符号付き64bit整数の最大値9223372036854775807(ギリギリ19桁)を超えるとoverflowします。

例えば、20桁の数16329805957987392833で試してみると、以下のようにconstant 16329805957987392833 overflows int64コンパイルエラーとなります。

package main

import (
    "fmt"
    "math/big"
)

func main()  {
    n := big.NewInt(16329805957987392833) // constant 16329805957987392833 overflows int64
    fmt.Println(n)
}

int64の最大値を超えるような大きな数をbig.Int型として扱いたいときは以下のようにすれば直接入力可能です。

package main

import (
    "fmt"
    "math/big"
)

const (
    DECIMAL int = 10
)

func main()  {
    
    n, _ := new(big.Int).SetString("16329805957987392833", DECIMAL)
    fmt.Println(n)
    
}

使った素数について

素数生成機をお借りして10桁の素数を2つ(7508269669,2174909357)生成し、積を計算したのが16329805957987392833です。

Reference

DH鍵交換でもWiresharkでSSL/TLSを復号化したい

WiresharkでSSL通信の中身を覗いてみる を拝見し、実際に自分の手を動かしてみたのですが、記事内でも触れられているようにDiffie-Hellman(DH) key exchange (および楕円曲線を用いたECDH) では、実際に鍵を送り合うわけではなく、鍵を生成するためのパラメータだけがやり取りされるので、サーバの秘密鍵を持っていても復号できません。
今回はDH鍵交換(以下、DHE)でもWiresharkSSL/TLSを復号すべく試行錯誤したので、まとめます。

事前の設定内容

VirtualBoxで以下のゲストOSやApacheを立ち上げておきます。

$ cat /etc/redhat-release
CentOS Linux release 7.2.1511 (Core)

$ httpd -v
Server version: Apache/2.4.6 (CentOS)
Server built:   Nov 14 2016 18:04:44

$ rpm -aq | grep mod_ssl
mod_ssl-2.4.6-45.el7.centos.x86_64

$ openssl version
OpenSSL 1.0.1e-fips 11 Feb 2013

ホストOSとゲストOSのIPは、それぞれ以下のようにアサインしました。

ホストOS ゲストOS
192.168.10.100 192.168.10.104

オレオレ証明書CentOS に Apache HTTPD を導入して SSL を有効にする を参考に作成し、証明書と秘密鍵は以下の名前でssl.confに記載しています。

# サーバ証明書
SSLCertificateFile /etc/httpd/conf/server.crt
# サーバ秘密鍵
SSLCertificateKeyFile /etc/httpd/conf/server.key

(参考)DHEを無効にする

参考までにサーバ側とクライアント側でDHEを無効にすることでSSL/TLS通信を復号する方法も記載します。 この方法ではサーバの秘密鍵があれば、SSL/TLS通信を復号することができます。サーバの秘密鍵を外へ出したくないということであれば(むしろ出すべきでないと思いますが)、session keyのみをexportすることでも復号できます。 セッションキーをエクスポートし、秘密鍵を共有することなくWireshark でSSL/TLS 通信を複合 に両方のやり方がありますので、興味がある方はぜひ。

サーバ側でDHEを無効にする

WiresharkでSSL通信の中身を覗いてみる にも記載がありますが、ssl.confで以下のように設定すればOKです。

SSLCipherSuite kRSA

設定後はservice httpd restartApacheを再起動しておきます。 この状態でhttpsの通信を発生させ、Server Helloに含まれるcipher suiteを見ると Cipher Suite: TLS_RSA_WITH_AES_128_CBC_SHA (0x002f)となっており、DHEもECDHEも使われていないことがわかります。

f:id:cipepser:20170326204102p:plain

ssl.confの設定を戻すことをお忘れなく

クライアント側でDHEを無効にする(Firefox)

Firefoxを立ち上げ、アドレスバーにabout:configと打ち込みます。 dheで検索し、DHEおよびECDHEを含むcipher suitesを無効化(false)にします。 以下の太字の箇所が変更箇所です(一番上以外)。

f:id:cipepser:20170326202640p:plain

この状態でhttpsの通信を発生させ、Server Helloに含まれるcipher suiteを見ると Cipher Suite: TLS_RSA_WITH_AES_128_CBC_SHA (0x002f)となっており、サーバ側でDHEとECDHEを無効化したときと同じですね。

f:id:cipepser:20170326202929p:plain

Firefoxの設定を戻すことをお忘れなく

本題

さて、DHEを無効化せずにWiresharkで復号化したいですね。 復号化するにはサーバの秘密鍵ではなく、session keyを入手する必要があります。 まずはホストOSでsession keyをexport先を指定してFirefoxを起動します。 ここではpremaster.txtにexportさせます。
Firefoxは閉じた状態で実行しないと怒られます。

$ SLKEYLOGFILE=/YOURPATH/TO/premaster.txt "/Applications/Firefox.app/Contents/MacOS/firefox-bin"

上記を実行すると、いつも通りFirefoxが起動するので、httpsの通信を発生させます。 するとpremaster.txtには以下のようにsession keyが書き込まれているはずです。

$ cat premaster.txt
# SSL/TLS secrets log file, generated by NSS
CLIENT_RANDOM  xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx

※実際にはxが16進数で表示されるはずです。

この時点では以下のように復号化できていないです。

f:id:cipepser:20170326212249p:plain

復号するためには、Wiresharkpremaster.txtからsession keyを読むように指定してあげます。 指定方法は、WiresharkPreferenceからProtocolsSSL(Pre)-Master-Secret log filenamepremaster.txtを指定します。
※特にサーバの秘密鍵などは指定する必要ありません。

f:id:cipepser:20170326213212p:plain

OKを押下すると以下のようにhttpのパケットが復号できます。

f:id:cipepser:20170326214605p:plain

このときのServer Helloに含まれるcipher suiteを見ると Cipher Suite: TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256 (0xc02f)となっており、ECDHEでも復号化できていることがわかります。

f:id:cipepser:20170326214620p:plain

References

2016年度に読んだ本まとめ

年度も変わったので2016年度の一年間で読んだ本をまとめました。
例によって小説とか漫画は数が多くなりすぎるので割愛です。

技術書

いい加減、GitHub触っておかないとな、と思ったので読みました。 今でもたまにコマンド忘れて、Referenceとして本棚から引っ張り出しています。
手元にあると、困ったとき便利。

CTFとは何か、というところからバイナリ解析の種々の分野について例題を追っていくような感じです。ここからさらに常設CTFなどを自分で解いていくのがよさげです。

2015年末くらいからGo言語やり始めていた折に本屋でちら見して、実際のコードが記載された上で議論していたのでよさそうと思い、購入。実際、自分で書いたコードを思い浮かべながら読むと、意識してなかったこと、すべきことが多数紹介されていて、とても勉強になりました。
しかも思いの外手軽に読めるのがよいです。kindle版が、技術書にありがちな固定レイアウトではなく、しっかりkindleフォーマットなのがポイント高いです。iPhoneでも文字が小さくない!
ただし、A Tour of Goくらいは一読している前提で話が進むのでGo言語初見だと厳しいような印象です。少し触ったあとがオススメです。

良くも悪くも広く浅くという印象でした。各種用語を掴んだ上で自分の手を動かすなり、別の書籍で調べていくのがよさそうです。ちなみに情報処理資格(基本情報、応用情報)よりは深いです。

マネジメントとか

ソフトウェアのプロジェクトを技術的なものではなく、社会学的なものとして捉えて、どういうマネジメントが失敗していくかというお話です。身に覚えのある筋の悪いルールなどもあって、職場で紹介してあげたくなります笑

Googleがどうやって成功してきたか、ひたすら書かれています。 以下の考え方、あんまり思ったことがなかったのでよかったです。

燃え尽き症候群の原因は働きすぎではなく、自分にとって本当に大切なことを諦めなければならなくなったときに起こる

データ分析は銀の弾丸ではないという話をデータサイズや分析結果など様々な観点から話されています。分析の心構え的な話でした。

さくっと読めるセキュリティインシデント事例集。詳細までは追わないもののざっくりとどんなことが起きていて、知っておくべきキーワード、考え方は抑えられそうです。高度情報処理のセキュリティ受ける人とか読んでおくと午後問題回答しやすいかもですね。

資格系

※リンクは最新版にしました。

両方やっておけば合格余裕と思います。自分個人としては計算問題をしっかり理解できたので、計算が安定感ある得点源になりました。

先にある程度問題を解いていたのもあると思いますが、本気でやれば数時間で終わります。無理なくやれば1週間程度でしょうか。問題こなしてから本書を読むと知識が整理されるので教科書としてとても助かりました。

その他

上のGitHub実践入門読んで、GitHubの草も残しておこうと思ったので残します。 Go言語触り始めたあたりから草多めになりました。

f:id:cipepser:20170401001153p:plain