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

Golangで棒グラフを描く

背景

言語処理100本ノック 2015をやっている最中に、棒グラフで表示する問題(Q37)に遭遇しました。簡単に検索したところ、意外と日本語記事が少なかったので、Gonum Plotを色々触ってみたメモを残しておきます。

packageのインストール

Gonum Plotにもありますが、go getしておきます。

# go get github.com/gonum/plot/...

何もエラーが出ず、プロンプトが表示されれば問題ありません。 ここでhgが足りないエラーがでる場合は、mercurialをインストールしましょう。

# brew install mercurial

棒グラフの作成

各設定事項はコメントで記載しました。 その他にももろもろ設定できますので、Gonum Plotをご覧ください。

gist9515002d792508b91e54766930751e37

棒グラフの出力

上記を実行すると、グラフがディレクトリに.pngで出力されます。 f:id:cipepser:20170324010640p:plain

Reference

Golangで言語処理100本ノック2015 第3章: 正規表現

言語処理100本ノック 2015の第3章: 正規表現の10問です。

20. JSONデータの読み込み

Wikipedia記事のJSONファイルを読み込み，「イギリス」に関する記事本文を表示せよ．問題21-29では，ここで抽出した記事本文に対して実行せよ．

gist1c2eef5c84cb1bb2f2ffc568d5d60d31

Goでjsonを触ったことがなかったので勉強がてら。 結果の表示は長すぎるので割愛します。

21. カテゴリ名を含む行を抽出

記事中でカテゴリ名を宣言している行を抽出せよ．

gistd85ddaaaeedb8accc0431d2ea8458fb5

Q20で抜き出した結果をtxtに格納しています。 本問題は実質、L45-48のみです。

# go run q21.go
[[Category:イギリス|*]]
[[Category:英連邦王国|*]]
[[Category:G8加盟国]]
[[Category:欧州連合加盟国]]
[[Category:海洋国家]]
[[Category:君主国]]
[[Category:島国|くれいとふりてん]]
[[Category:1801年に設立された州・地域]]

22. カテゴリ名の抽出

記事のカテゴリ名を（行単位ではなく名前で）抽出せよ．

gistd36f7ebc49991afa58cb42101c9265b5

# go run q22.go
イギリス|*
英連邦王国|*
G8加盟国
欧州連合加盟国
海洋国家
君主国
島国|くれいとふりてん
1801年に設立された州・地域

正規表現のところをCategory:.*]としました。 あとは表示する箇所を*のところだけにしています。

23. セクション構造

記事中に含まれるセクション名とそのレベル（例えば"== セクション名 ==“なら1）を表示せよ．

gist4db740893310296693544caa501a9727

# go run q23.go
国名 1
歴史 1
地理 1
気候 2
政治 1
外交と軍事 1
地方行政区分 1
主要都市 2
科学技術 1
経済 1
鉱業 2
農業 2
貿易 2
通貨 2
企業 2
交通 1
道路 2
鉄道 2
海運 2
航空 2
通信 1
国民 1
言語 2
宗教 2
 婚姻  2
教育 2
文化 1
食文化 2
文学 2
 哲学  2
音楽 2
イギリスのポピュラー音楽 3
映画 2
コメディ 2
国花 2
世界遺産 2
祝祭日 2
スポーツ 1
サッカー 2
競馬 2
モータースポーツ 2
脚注 1
関連項目 1
外部リンク 1

(?m)がないと^が否定として認識されるところでハマりました。。。

24. ファイル参照の抽出

記事から参照されているメディアファイルをすべて抜き出せ．

gist6feafca211c2f0c574b60770553f1a71

# go run q24.go
Royal Coat of Arms of the United Kingdom.svg
Battle of Waterloo 1815.PNG
The British Empire.png
Uk topo en.jpg
BenNevis2005.jpg
Elizabeth II greets NASA GSFC employees, May 8, 2007 edit.jpg
Palace of Westminster, London - Feb 2007.jpg
David Cameron and Barack Obama at the G20 Summit in Toronto.jpg
Soldiers Trooping the Colour, 16th June 2007.jpg
Scotland Parliament Holyrood.jpg
London.bankofengland.arp.jpg
City of London skyline from London City Hall - Oct 2008.jpg
Oil platform in the North SeaPros.jpg
Eurostar at St Pancras Jan 2008.jpg
Heathrow T5.jpg
Anglospeak.svg
CHANDOS3.jpg
The Fabs.JPG
PalaceOfWestminsterAtNight.jpg
Westminster Abbey - West Door.jpg
Edinburgh Cockburn St dsc06789.jpg
Canterbury Cathedral - Portal Nave Cross-spire.jpeg
Kew Gardens Palm House, London - July 2009.jpg
2005-06-27 - United Kingdom - England - London - Greenwich.jpg
Stonehenge2007 07 30.jpg
Yard2.jpg
Durham Kathedrale Nahaufnahme.jpg
Roman Baths in Bath Spa, England - July 2006.jpg
Fountains Abbey view02 2005-08-27.jpg
Blenheim Palace IMG 3673.JPG
Liverpool Pier Head by night.jpg
Hadrian's Wall view near Greenhead.jpg
London Tower (1).JPG
Wembley Stadium, illuminated.jpg

.*でマッチさせようとすると最後の|まで引っかかってしまうので.*?としています。
Fileとファイルでわかれてるがめんどくさかったですね。。。

25. テンプレートの抽出

記事中に含まれる「基礎情報」テンプレートのフィールド名と値を抽出し，辞書オブジェクトとして格納せよ．

gistb73da44413a4ccb5c9e32bd95a7ae4a4

# go run q25.go
イギリス
------------------
{{lang|en|United Kingdom of Great Britain and Northern Ireland}}<ref>英語以外での正式国名:<br/>
*{{lang|gd|An Rìoghachd Aonaichte na Breatainn Mhòr agus Eirinn mu Thuath}}（[[スコットランド・ゲール語]]）<br/>
*{{lang|cy|Teyrnas Gyfunol Prydain Fawr a Gogledd Iwerddon}}（[[ウェールズ語]]）<br/>
*{{lang|ga|Ríocht Aontaithe na Breataine Móire agus Tuaisceart na hÉireann}}（[[アイルランド語]]）<br/>
*{{lang|kw|An Rywvaneth Unys a Vreten Veur hag Iwerdhon Glédh}}（[[コーンウォール語]]）<br/>
*{{lang|sco|Unitit Kinrick o Great Breetain an Northren Ireland}}（[[スコットランド語]]）<br/>
**{{lang|sco|Claught Kängrick o Docht Brätain an Norlin Airlann}}、{{lang|sco|Unitet Kängdom o Great Brittain an Norlin Airlann}}（アルスター・スコットランド語）</ref>
------------------
現在の国号「'''グレートブリテン及び北アイルランド連合王国'''」に変更

最初に基本情報を抜き出し、そこから|で区切られるテンプレートを抽出しました。 公式国名があるせいで、改行区切りではないので、\s\Sを用いて改行を含む抽出をしつつ、|を区切りとしています。 ただし単純に\n|を終端として持ってくると偶数回目が抜き出せなくなるので、\n|をダブらせるように前処理を入れています。 同様に最後の注記も抜き出せなくなるので終端処理を入れています。

課題では辞書オブジェクト(Map)に格納するところまでですが、テストとして略名と、ハマりどころの公式国名、偶数番目、最後のテンプレートもちゃんと取れているかの確認用に確立形態4、注記を表示させてみました。

26. 強調マークアップの除去

25の処理時に，テンプレートの値からMediaWikiの強調マークアップ（弱い強調，強調，強い強調のすべて）を除去してテキストに変換せよ（参考: マークアップ早見表）．

gist8fb6214399e84001eecfcd72acddd3c1

# go run q26.go
現在の国号「グレートブリテン及び北アイルランド連合王国」に変更

Q25を元に、ReplaceAllStringで'{2,5}をマッチさせています。 確認用には確立形態4を表示。

27. 内部リンクの除去

26の処理に加えて，テンプレートの値からMediaWikiの内部リンクマークアップを除去し，テキストに変換せよ（参考: マークアップ早見表）．

gist0531301d5d7252c813b3f8bc12bd074d

# go run q27.go
1801年
244,820
1兆5478億<ref name="imf-statistics-gdp">[http://www.imf.org/external/pubs/ft/weo/2012/02/weodata/weorept.aspx?pr.x=70&pr.y=13&sy=2010&ey=2012&scsm=1&ssd=1&sort=country&ds=.&br=1&c=112&s=NGDP%2CNGDPD%2CPPPGDP%2CPPPPC&grp=0&a= IMF>Data and Statistics>World Economic Outlook Databases>By Countrise>United Kingdom]</ref>
2兆3162億<ref name="imf-statistics-gdp" />
イングランド王国／スコットランド王国<br />（両国とも連合法 (1707年)まで）
グレートブリテン及びアイルランド連合王国建国<br />（連合法 (1800年)）
女王陛下万歳
ロンドン
246
1.3%
2兆4337億<ref name="imf-statistics-gdp" />
±0
.uk / .gb<ref>使用は.ukに比べ圧倒的少数。</ref>
44
（イギリスの国章）
{{lang|fr|Dieu et mon droit}}<br/>（フランス語:神と私の権利）
6
建国
1927年
{{lang|en|United Kingdom of Great Britain and Northern Ireland}}<ref>英語以外での正式国名:<br/>
*{{lang|gd|An Rìoghachd Aonaichte na Breatainn Mhòr agus Eirinn mu Thuath}}（スコットランド・ゲール語）<br/>
*{{lang|cy|Teyrnas Gyfunol Prydain Fawr a Gogledd Iwerddon}}（ウェールズ語）<br/>
*{{lang|ga|Ríocht Aontaithe na Breataine Móire agus Tuaisceart na hÉireann}}（アイルランド語）<br/>
*{{lang|kw|An Rywvaneth Unys a Vreten Veur hag Iwerdhon Glédh}}（コーンウォール語）<br/>
*{{lang|sco|Unitit Kinrick o Great Breetain an Northren Ireland}}（スコットランド語）<br/>
**{{lang|sco|Claught Kängrick o Docht Brätain an Norlin Airlann}}、{{lang|sco|Unitet Kängdom o Great Brittain an Norlin Airlann}}（アルスター・スコットランド語）</ref>
ロンドン
デーヴィッド・キャメロン
927年／843年
GB / GBR
1707年
Flag of the United Kingdom.svg
22
63,181,775<ref>[http://esa.un.org/unpd/wpp/Excel-Data/population.htm United Nations Department of Economic and Social Affairs>Population Division>Data>Population>Total Population]</ref>
2012
グレートブリテン王国建国<br />（連合法 (1707年)）
2011
1 E7
36,727<ref name="imf-statistics-gdp" />
ファイル:Royal Coat of Arms of the United Kingdom.svg|85px
Location_UK_EU_Europe_001.svg
イギリスの君主
76
1 E11
+1
<references />
2012
5
2012
イギリス
グレートブリテン及び北アイルランド連合王国
英語（事実上）
エリザベス2世
イギリスの首相
現在の国号「グレートブリテン及び北アイルランド連合王国」に変更
スターリング・ポンド (&pound;)
GBP

ルールは単純なのですが、意外と時間かかりました。 グループ文字列の概念をここで知ったのでFindAllStringSubmatch()も使ってみました。

28. MediaWikiマークアップの除去

27の処理に加えて，テンプレートの値からMediaWikiマークアップを可能な限り除去し，国の基本情報を整形せよ．

gistb0ae0915872317ffa62cedb2c505d854

# go run q28.go
1 E7
1兆5478億<ref name="imf-statistics-gdp">
スターリング・ポンド (&pound;)
GBP
1.3%
244,820
2兆3162億<ref name="imf-statistics-gdp" />
36,727<ref name="imf-statistics-gdp" />
ロンドン
2011
63,181,775<ref>
グレートブリテン及びアイルランド連合王国建国<br />（連合法 (1800年)）
1927年
<references />
イギリスの君主
Flag of the United Kingdom.svg
（イギリスの国章）
エリザベス2世
{{lang|en|United Kingdom of Great Britain and Northern Ireland}}<ref>英語以外での正式国名:<br/>
*{{lang|gd|An Rìoghachd Aonaichte na Breatainn Mhòr agus Eirinn mu Thuath}}（スコットランド・ゲール語）<br/>
*{{lang|cy|Teyrnas Gyfunol Prydain Fawr a Gogledd Iwerddon}}（ウェールズ語）<br/>
*{{lang|ga|Ríocht Aontaithe na Breataine Móire agus Tuaisceart na hÉireann}}（アイルランド語）<br/>
*{{lang|kw|An Rywvaneth Unys a Vreten Veur hag Iwerdhon Glédh}}（コーンウォール語）<br/>
*{{lang|sco|Unitit Kinrick o Great Breetain an Northren Ireland}}（スコットランド語）<br/>
**{{lang|sco|Claught Kängrick o Docht Brätain an Norlin Airlann}}、{{lang|sco|Unitet Kängdom o Great Brittain an Norlin Airlann}}（アルスター・スコットランド語）</ref>
1801年
+1
246
Location_UK_EU_Europe_001.svg
英語（事実上）
ロンドン
5
2012
1707年
現在の国号「グレートブリテン及び北アイルランド連合王国」に変更
グレートブリテン及び北アイルランド連合王国
GB / GBR
±0
イギリスの首相
76
1 E11
2012
2兆4337億<ref name="imf-statistics-gdp" />
建国
イングランド王国／スコットランド王国<br />（両国とも連合法 (1707年)まで）
{{lang|fr|Dieu et mon droit}}<br/>（フランス語:神と私の権利）
グレートブリテン王国建国<br />（連合法 (1707年)）
.uk / .gb<ref>使用は.ukに比べ圧倒的少数。</ref>
44
927年／843年
ファイル:Royal Coat of Arms of the United Kingdom.svg|85px
女王陛下万歳
デーヴィッド・キャメロン
22
2012
6
イギリス

外部リンクとコメントアウトを消しました。

29. 国旗画像のURLを取得する

テンプレートの内容を利用し，国旗画像のURLを取得せよ．（ヒント: MediaWiki APIのimageinfoを呼び出して，ファイル参照をURLに変換すればよい）

gist84f53bc3fb6df3029aff323f42cb6c5d

# go run q29.go
https://upload.wikimedia.org/wikipedia/en/a/ae/Flag_of_the_United_Kingdom.svg

API client書いたことがなかったので書いてみましたが、もっとちゃんと書けそうな気がしています。どういうことに気をつけて書くべきなのかも経験不足なので、今後の課題ですね。

感想

序盤はさくさく進んだので余裕かと思いましたが、後半でかなり手こずりしました。正規表現むずい。
今回もコードはGithubにも置いてあります。

Reference

tracerouteで * (アスタリスク)になる理由

背景

「ネットワークがつながらない！」といったトラブルシューティングをしていると、 tracerouteの結果が、以下のように経路の途中で*になる事象によく遭遇します。
今回はIPヘッダやパケットを見比べながら、なぜ*になるのかを見ていきます。

$ traceroute 8.8.8.8
traceroute to 8.8.8.8 (8.8.8.8), 64 hops max, 52 byte packets
 1  192.168.43.1 (192.168.43.1)  823.037 ms *  3.936 ms
 2  * * *
 3  osk004bb01.iij.net (202.32.116.5)  476.654 ms  132.676 ms  120.725 ms
 4  osk004ix50.iij.net (58.138.107.218)  119.609 ms
    osk004ix50.iij.net (58.138.107.166)  133.204 ms
    osk004ix51.iij.net (58.138.107.222)  117.566 ms
 5  72.14.210.182 (72.14.210.182)  126.614 ms
    210.130.133.86 (210.130.133.86)  115.229 ms  118.843 ms
 6  108.170.243.36 (108.170.243.36)  119.670 ms
    108.170.243.68 (108.170.243.68)  134.219 ms
    108.170.243.132 (108.170.243.132)  135.462 ms
 7  209.85.255.163 (209.85.255.163)  141.621 ms
    216.239.41.199 (216.239.41.199)  132.251 ms  138.545 ms
 8  66.249.95.77 (66.249.95.77)  165.501 ms
    108.170.235.231 (108.170.235.231)  155.299 ms
    66.249.95.77 (66.249.95.77)  172.740 ms
 9  216.239.43.101 (216.239.43.101)  153.654 ms
    72.14.235.77 (72.14.235.77)  175.888 ms
    64.233.175.209 (64.233.175.209)  156.037 ms
10  * * *
11  * * *
12  * * *
13  * * *
14  * * *
15  * * *
16  * * *
17  * * *
18  google-public-dns-a.google.com (8.8.8.8)  159.839 ms  156.416 ms  166.939 ms

※プロバイダによっては*にならない場合もあるようです。 今回はDMMのSIMカードからテザリングしています。
ちなみに8.8.8.8はGoogleのパブリックDNSのIPアドレスです。覚えやすいですね。

前提知識

IPヘッダのProtocolナンバー

RFC791でIPヘッダのフォーマットは以下のように定められています。

0                   1                   2                   3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|Version|  IHL  |Type of Service|          Total Length         |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|         Identification        |Flags|      Fragment Offset    |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|  Time to Live |    Protocol   |         Header Checksum       |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|                       Source Address                          |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|                    Destination Address                        |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|                    Options                    |    Padding    |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

上記のProtocolフィールドが1となるものがICMPとなります。
※ProtocolナンバーはRFC790 で規定されています。 TCP、UDP(User Datagram)もそれぞれ6、17がアサインされています。

ping実行時のパケットをWiresharkで見てみると以下のようにICMP(1)となっていることがわかります。

f:id:cipepser:20170305172120p:plain

tracerouteの仕組み

tracerouteは、冒頭のコマンド結果のように、宛先までのホップ情報を教えてくれる便利なコマンドです。
tracerouteは上記のIPヘッダにあるTime to Live(TTL)を利用して実装されています。
TTLはパケットの寿命みたいなものです。誤ったルーティングが設定されたネットワークでは、度々ループが発生します。この時、ネットワークに入ってきたパケットがいつまでもループし続けると、ネットワークの帯域を逼迫させ、通信ができなくなります。それを避けるための方法として、ルータはパケットをフォワードする際にTTLを1ずつデクリメントします。TTLが0になったパケットを受信したルータは、そのパケットをフォワードせず、破棄します。これによってネットワークが輻輳まみれになることを防ぎます。
そしてTTLが0になったときtracerouteの発行元に対して、TTLが0になったことを通知(Time Exceeded Message)します。

※これらはRFC792で以下のように規定されています。

If the gateway processing a datagram finds the time to live field is zero it must discard the datagram. The gateway may also notify the source host via the time exceeded message.

この通知には破棄したルータのIPアドレスが含まれています。 tracerouteではTTLを1つずつインクリメントし、応答があったTime Exceeded Messageに含まれるIPアドレスを表示することで実装されています。

本題

前置きが長くなりましたが、いよいよ本題に入っていきます。
tracerouteは、WindowsではICMPを用いていますが、LinuxではUDPでポート番号33434 〜33534が使われます。tracerouteをFWで通す要件がある場合は、実装する際に注意が必要です。
今回はICMPのTTLをマニュアルで設定することで、tracerouteの仕組みを擬似的に再現し、*の正体を探ります。 そのためtracerouteに-Iオプションを付けてICMPでのtraceroute結果を得ておきます。

$ traceroute -I 8.8.8.8
traceroute to 8.8.8.8 (8.8.8.8), 64 hops max, 72 byte packets
 1  * * *
 2  * * *
 3  osk009nasgw111.iij.net (202.32.116.105)  132.515 ms  122.689 ms  119.731 ms
 4  osk004bb01.iij.net (202.32.116.5)  117.981 ms  114.951 ms  121.114 ms
 5  osk004ix51.iij.net (58.138.107.222)  123.171 ms  118.085 ms  122.172 ms
 6  72.14.210.182 (72.14.210.182)  117.047 ms  122.246 ms  123.139 ms
 7  108.170.243.66 (108.170.243.66)  117.916 ms  498.344 ms  149.948 ms
 8  209.85.255.163 (209.85.255.163)  116.059 ms  132.291 ms  121.649 ms
 9  72.14.233.211 (72.14.233.211)  159.789 ms  163.511 ms  173.399 ms
10  72.14.235.77 (72.14.235.77)  154.462 ms  153.933 ms  170.539 ms
11  * * *
12  * * *
13  * * *
14  * * *
15  * * *
16  * * *
17  * * *
18  * * *
19  google-public-dns-a.google.com (8.8.8.8)  168.872 ms  150.776 ms  161.775 ms

この時の通信の様子をWiresharkで見てみると以下のようになります。 TTLを1から順に増やしつつ、それぞれ3回送っていることがわかります。

f:id:cipepser:20170305211345p:plain f:id:cipepser:20170305211351p:plain f:id:cipepser:20170305211358p:plain

勘の良い方はすでにお気づきかと思いますが、 tracerouteの結果が*ではないものはTime Exceeded Messageを返しています。 逆に言えば、*になっている箇所は応答がありません。

さらに詳しく見るためにTTLを設定したpingを打ってみましょう。 -mオプションでpingのTTLを設定できます。 長いですが、以下結果です。
192.168.43.11は自ホストのアドレスです。

$ ping -m 1 -c 1 8.8.8.8
PING 8.8.8.8 (8.8.8.8): 56 data bytes

--- 8.8.8.8 ping statistics ---
1 packets transmitted, 0 packets received, 100.0% packet loss

$ ping -m 2 -c 1 8.8.8.8
PING 8.8.8.8 (8.8.8.8): 56 data bytes

--- 8.8.8.8 ping statistics ---
1 packets transmitted, 0 packets received, 100.0% packet loss

$ ping -m 3 -c 1 8.8.8.8
PING 8.8.8.8 (8.8.8.8): 56 data bytes
36 bytes from osk009nasgw111.iij.net (202.32.116.105): Time to live exceeded
Vr HL TOS  Len   ID Flg  off TTL Pro  cks      Src      Dst
 4  5  00 5400 248e   0 0000  01  01 9958 192.168.43.11  8.8.8.8

--- 8.8.8.8 ping statistics ---
1 packets transmitted, 0 packets received, 100.0% packet loss

$ ping -m 4 -c 1 8.8.8.8
PING 8.8.8.8 (8.8.8.8): 56 data bytes
76 bytes from osk004bb01.iij.net (202.32.116.5): Time to live exceeded
Vr HL TOS  Len   ID Flg  off TTL Pro  cks      Src      Dst
 4  5  00 5400 80d2   0 0000  01  01 3d14 192.168.43.11  8.8.8.8

--- 8.8.8.8 ping statistics ---
1 packets transmitted, 0 packets received, 100.0% packet loss

$ ping -m 5 -c 1 8.8.8.8
PING 8.8.8.8 (8.8.8.8): 56 data bytes
36 bytes from osk004ix51.iij.net (58.138.107.222): Time to live exceeded
Vr HL TOS  Len   ID Flg  off TTL Pro  cks      Src      Dst
 4  5  00 5400 1fb3   0 0000  01  01 9e33 192.168.43.11  8.8.8.8

--- 8.8.8.8 ping statistics ---
1 packets transmitted, 0 packets received, 100.0% packet loss

$ ping -m 6 -c 1 8.8.8.8
PING 8.8.8.8 (8.8.8.8): 56 data bytes
36 bytes from 72.14.210.182: Time to live exceeded
Vr HL TOS  Len   ID Flg  off TTL Pro  cks      Src      Dst
 4  5  00 5400 3fb3   0 0000  01  01 7e33 192.168.43.11  8.8.8.8

--- 8.8.8.8 ping statistics ---
1 packets transmitted, 0 packets received, 100.0% packet loss

$ ping -m 7 -c 1 8.8.8.8
PING 8.8.8.8 (8.8.8.8): 56 data bytes
36 bytes from 108.170.243.66: Time to live exceeded
Vr HL TOS  Len   ID Flg  off TTL Pro  cks      Src      Dst
 4  5  80 5400 acc6   0 0000  01  01 10a0 192.168.43.11  8.8.8.8

--- 8.8.8.8 ping statistics ---
1 packets transmitted, 0 packets received, 100.0% packet loss

$ ping -m 8 -c 1 8.8.8.8
PING 8.8.8.8 (8.8.8.8): 56 data bytes
148 bytes from 209.85.255.163: Time to live exceeded
Vr HL TOS  Len   ID Flg  off TTL Pro  cks      Src      Dst
 4  5  80 5400 5d6e   0 0000  01  01 5ff8 192.168.43.11  8.8.8.8

--- 8.8.8.8 ping statistics ---
1 packets transmitted, 0 packets received, 100.0% packet loss

$ ping -m 9 -c 1 8.8.8.8
PING 8.8.8.8 (8.8.8.8): 56 data bytes
148 bytes from 72.14.233.211: Time to live exceeded
Vr HL TOS  Len   ID Flg  off TTL Pro  cks      Src      Dst
 4  5  80 5400 13e9   0 0000  02  01 a87d 192.168.43.11  8.8.8.8

--- 8.8.8.8 ping statistics ---
1 packets transmitted, 0 packets received, 100.0% packet loss

$ ping -m 10 -c 1 8.8.8.8
PING 8.8.8.8 (8.8.8.8): 56 data bytes
36 bytes from 72.14.235.77: Time to live exceeded
Vr HL TOS  Len   ID Flg  off TTL Pro  cks      Src      Dst
 4  5  80 5400 6b01   0 0000  01  01 5265 192.168.43.11  8.8.8.8

--- 8.8.8.8 ping statistics ---
1 packets transmitted, 0 packets received, 100.0% packet loss

$ ping -m 11 -c 1 8.8.8.8
PING 8.8.8.8 (8.8.8.8): 56 data bytes

--- 8.8.8.8 ping statistics ---
1 packets transmitted, 0 packets received, 100.0% packet loss

$ ping -m 12 -c 1 8.8.8.8
PING 8.8.8.8 (8.8.8.8): 56 data bytes

--- 8.8.8.8 ping statistics ---
1 packets transmitted, 0 packets received, 100.0% packet loss

$ ping -m 13 -c 1 8.8.8.8
PING 8.8.8.8 (8.8.8.8): 56 data bytes

--- 8.8.8.8 ping statistics ---
1 packets transmitted, 0 packets received, 100.0% packet loss

$ ping -m 14 -c 1 8.8.8.8
PING 8.8.8.8 (8.8.8.8): 56 data bytes

--- 8.8.8.8 ping statistics ---
1 packets transmitted, 0 packets received, 100.0% packet loss

$ ping -m 15 -c 1 8.8.8.8
PING 8.8.8.8 (8.8.8.8): 56 data bytes

--- 8.8.8.8 ping statistics ---
1 packets transmitted, 0 packets received, 100.0% packet loss

$ ping -m 16 -c 1 8.8.8.8
PING 8.8.8.8 (8.8.8.8): 56 data bytes

--- 8.8.8.8 ping statistics ---
1 packets transmitted, 0 packets received, 100.0% packet loss

$ ping -m 17 -c 1 8.8.8.8
PING 8.8.8.8 (8.8.8.8): 56 data bytes

--- 8.8.8.8 ping statistics ---
1 packets transmitted, 0 packets received, 100.0% packet loss

$ ping -m 18 -c 1 8.8.8.8
PING 8.8.8.8 (8.8.8.8): 56 data bytes

--- 8.8.8.8 ping statistics ---
1 packets transmitted, 0 packets received, 100.0% packet loss

$ ping -m 19 -c 1 8.8.8.8
PING 8.8.8.8 (8.8.8.8): 56 data bytes
64 bytes from 8.8.8.8: icmp_seq=0 ttl=46 time=166.696 ms

--- 8.8.8.8 ping statistics ---
1 packets transmitted, 1 packets received, 0.0% packet loss
round-trip min/avg/max/stddev = 166.696/166.696/166.696/0.000 ms

確かにtracerouteの結果が*ではないものはTime Exceeded Messageを返していることがわかります。 しかもその応答をTTL=0となったホップが返しているので、送信元アドレス(=tracerouteで表示するアドレス)もわかりました。
逆に*になっている箇所はpacket lossで応答なしのため、表示することができず、代替手段として*を表示するしかないようですね。
またTTL=19の最終の宛先では、通常のping応答と同様のメッセージが返ってきているので、これを自分でtracerouteを実装するとしたら、「応答があったこと」を条件にループ止めるなどで実装できそうですね。

結論

tracerouteの結果、経路の途中で*になるのは、そのホップが応答を返さないとき（フォワードのみする）。

Reference

dockerで<none>になったimageを一発で削除するシェル芸

タイトルのままですが、docker imagesを見たときにTAGが<none>となってしまったdocker imageをまとめて削除するためのシェル芸です。
シェルも書けるようになりたいなという思いから、練習がてら。

docker images | grep none | sed -E 's/ +/ /g' | cut -f 3 -d ' ' | xargs docker rmi -f

Reference

Golangでcounting BloomFilterを実装してみた

先日実装したBloomFilter に要素の削除ができるようにcounting BloomFilterを実装しました。

概要

単純なBloomFilter では要素を削除することはできません。
BloomFilterへのマッピングが、削除したい特定の要素によるものか、はたまた別の要素によるものか区別することができないためです。

counting BloomFilterでは、BloomFilterにDelete()ができるようにマッピングをbooleanからcountingができるようmulti-bit化しています。
当然、その分空間効率性が犠牲になります。Fanらのpaper のイントロによると、一般的には3-4[bit]で実装するそうなので、3-4倍空間効率が悪くなります。
今回はGolangのprimitive型であるuint8を使用したため、アイデア自体は変わらないですが、一般的なcounting BloomFilterよりも空間効率が劣ります。

実装と結果

gistb38c96069b177b4f64ede336c658b976

要素"2"の削除前後で結果がtrue→falseと変わっていることがわかります。

参考

Golangの関数リテラルについてメモ書き

A Tour of GoのFunction valuesを読んでいて、色々勘違いしていてわからなくなってしまったので、手を動かしてわかるようになるまでのメモ書きです。

要旨

勘違いしていたのはA Tour of Goの以下の記載についてです。

関数も変数です。他の変数のように関数を渡すことができます。

どうしても関数を変数に渡した際に「戻り値を渡している」と考えていまい、例題が理解できませんでした。

理解に至った考え方は 「関数そのものを変数に渡している」 です。

例: A Tour of GoのFunction values

ここでは関数computeが定義されています。

func compute(fn func(float64, float64) float64) float64 {
    return fn(3, 4)
}

これは

引数: (float64, float64)を引数に、float64を返す関数
戻り値: float64

となる関数です。 つまり関数そのものを引数として、変数のように渡すことができます。
A Tour of Goでは「(float64, float64)を引数に、float64を返す関数」であるhypotを定義するとともに、同じ関数型の関数math.Powを引数としてcomputeに渡してあげる例となっています。

fmt.Println(compute(hypot))
fmt.Println(compute(math.Pow))

Reference