( ꒪⌓꒪) ゆるよろ日記

(　ﾟ∀ﾟ)o彡°ｵﾊﾟｰｲ!ｵﾊﾟｰｲ! ( ;ﾟ皿ﾟ)ﾉｼΣ ﾌｨﾝｷﾞｨｨｰｰｯ!!!

Nand2Tetris(コンピュータシステムの理論と実装)でCPUからOSまで一気通貫で作るのが最高に楽しかった話

Rust Nand2Tetris

どうも、しいたけです。

去年あたりからローレイヤー周りの知識を充実させようと思い、 低レイヤを知りたい人のためのCコンパイラ作成入門 を読んでCコンパイラを書いてみたりx86_64の勉強をしたりしていました。

今年に入ってから、よりローなレイヤー、具体的にはハードウェアやOSについてもう少し知りたいと思い始め、手頃な書籍を探していました。 CPUなどのハードウェア周りについては概要しか知らなくて手を動かしたことがないので、実際に何か作りながら学べるものとして、 O'Reilly Japan - コンピュータシステムの理論と実装 に挑戦することにしました。

O'Reilly Japan - コンピュータシステムの理論と実装

成果物は以下のリポジトリに置いてあります。

yuroyoro/nand2tetris

結論から言うと、やってみて大変楽しめました！

特にハードウェア周りは今まで挑戦したことのない分野で、回路の設計がとても新鮮で楽しんで取り組めました。 ちょこちょこ間が空いたりしたので、全部完走するまで10ヶ月ちょっとかかりましたが……。

コンパイラやVMの作成は、Cコンパイラ書いてみたりした経験があったのですんなりできましたが、実装言語にRustを採用することでRustの習熟にも役立ちました。 (というかハマったのは主にRustの学習で、使い慣れた言語だったらおそらくすぐに実装できたはずです……)

OSに関してはかなり物足りなかったので、こちらは別な教材で改めて学びたいと思います。

Nand2Tetrisってなに?

「コンピュータシステムの理論と実装」(通称Nand2Tetris: NANDからテトリスへ)は、コンピューターの基本的な構成要素であるCPUやメモリから始めて、そのアーキテクチャ向けの機械語を生成するコンパイラ、アプリケーションとハードウェアの橋渡しをするOSまでを 順を追って作成することで、基本的なコンピューターシステムの動作原理が理解できるような構成になっています。

Courseraにコースがあって、著者のShimon Schocken教授とNoam Nisan教授がインストラクターとしてオンラインで受講することができます。

Build a Modern Computer from First Principles: From Nand to Tetris (Project-Centered Course) | Coursera

僕はヘタレなので受講はせずに独学しましたが、気合入れて取り組むつもりなら受講するのもありではないでしょうか。

Nand2Tetrisでは、Hackという本書独自のアーキテクチャ用のCPUやメモリなどをNand回路から始めて作成し、Jackという本書独自のプログラミング言語のHackアーキテクチャ向けコンパイラを実装し、そのJack言語を用いてOSを書くことで、ハードウェアからOS、アプリケーションまですべてを自前で作っていきます。 とはいえ、Hackアーキテクチャで作成するCPUは16bitでデータレジスタとアドレスレジスタがそれぞれひとつしかない単純なCPU(乗除算すらできません！)ですし、Jack言語はオブジェクト指向言語ですがJavaをかなり単純化した言語仕様です。 また、OSはプロセス管理やファイル管理、ネットワークなどはサポートせず、単純にキーボードやスクリーンなどメモリマップドされたハードウェアを操作するための便利ライブラリのような位置づけです。

それでも、順番に実装していくと(シミュレーター上とはいえ)このようなゲーム(アプリケーション)を動作させることができます!

テトリスちゃうやんけ！！

さて本の構成ですが、おおまかにハードウェア、コンパイラ、OSの3つのパートに分けられており、各パートはいくつかの章で構成されます。 章ごとに演習問題が用意されており、実際にその問題で作ったパーツが次の章で利用される仕掛けになっています。 例えば、回路設計では最初の1章でANDやORゲートを作り、次の2章ではそれらを組み合わせて加算器を作る、といった具合です。

本書はテストするための回路シミュレーターやCPUシミュレーターがすでに用意されており、また章ごとの課題もテストケースが用意されています。 課題の内容にしたがってHDLを書いたりプログラムを作成して、シミュレーター上で用意されているテストをパスすればその章はクリアです。

Home | nand2tetris

このシミュレーターやテストが用意されているのが非常に取り組みやすく、テストをパスすることを目標として実装すればよいので迷わなくてすむのがよかったです。 そうしてテストをパスするように章ごとの課題をこなしていけばいつのまにかコンピューターシステムが完成しているのです。

1章から5章: ハードウェア

まず、最初はNandゲートを組み合わせて論理ゲートを作り、それらのパーツを組み合わせて加算器やメモリやALUなどを実装します。 作ったALUをベースにCPUを設計し実装するところまでが、ハードウェアのパートでやることです。

  • 1章　ブール論理 : Nandゲートを組みわせてAND, ORなどの論理ゲートを作成します。
  • 2章　ブール算術 : AND, ORなどのパーツをもとに加算器やALU(算術論理演算器)を作ります
  • 3章　順序回路 : フリップフロップを用いて1bitレジスタから始めて16KBメモリ, プログラムカウンタを作ります
  • 4章　機械語 : 機械語についてHackアーキテクチャ向けのアセンブラを書いて学びます
  • 5章　コンピュータアーキテクチャ : ここまで作ってきたカウンタやALUを組み合わせて、4章で学んだHackアーキテクチャの機械語を実行できるCPUを作り、メモリや入出力と組み合わせます

回路設計ですが、HDLを書いてシミュレーター上でテストしながら進めていきます。 本書のサポートサイトからダウンロードできるツールチェインにハードウェアシミュレータがあり、実装したHDLをそのシミュレーター上でテストします。 HDLは書いたことがなかったのですが、本書で扱うものは非常に単純なルールなのですぐに覚えることができました。

こんな感じでやっていきます。

回路設計に悩むようすです

CPUの実装でこのページが出てきたときはめっちゃテンションあがりましたね？

シミュレーター上で、自分がHDL書いたCPUがHack機械語を実行できるようになったときの様子です。やりきった感あった。

6章から11章: コンパイラ

6章からはコンパイラの実装です。 本書独自のJack言語のコンパイラを実装して、Jack言語ソースコードからHack機械語を生成できるようになるまでが目標です。

  • 6章　アセンブラ : Hack機械語を生成するアセンブラを実装します
  • 7章　バーチャルマシン#1：スタック操作 : スタックベースのVMを実装します。VMソースコードから6章で作ったアセンブリを生成できるようにします。
  • 8章　バーチャルマシン#2：プログラム制御 : VM実装の続きで主に関数呼び出しを実装します。
  • 9章　高水準言語 : Jack言語の言語仕様についての説明です。実際にこれから作るJack言語を書いてみます。
  • 10章　コンパイラ#1：構文解析 : Jack言語コンパイラのフロントエンド部分の実装です。再起下降パーサーを書いてAST生成まで実装します。
  • 11章　コンパイラ#2：コード生成 : Jack言語コンパイラのバックエンド実装です。ASTからVM向けのコード生成を行います。

コンパイラの章は大きく分けて3部構成で、アセンブラ、バーチャルマシン、Jack言語コンパイラに分けられます。 それぞれのパートで実際にアセンブラやコンパイラを実装するわけですが、言語仕様を満たす実装ができるのであれば使用するプログラミング言語は何を用いても構いません。

「せっかくだから俺はこのRustという言語をを選ぶぜ」

アセンブラやVMの実装では、生成された機械語やアセンブラがCPUシミュレーター上で動作するかを確認します。 ハードウェアではHDL上で回路をテストしましたが、コンパイラは生成したコードをシミュレーターでテストします。 テストケースとして入力となるソースコードとその期待する動作をテストするためのスクリプトが用意されているので、テストがパスするような機械語/アセンブリ/VMコードを生成できるよぅに頑張るだけです。

アセンブラの実装はasmファイルを行ごとに読んでパースして機械語に変換するだけなので悩みはなかったです。この頃は主にRustについて悩んでいた

スタックマシンはCコンパイラ作成入門で一度実装したことがあったので、関数呼び出し時のスタックとかリターンアドレスとかそのあたりは理解していたのですが、Hackはレジスタ2個しかなくて実装しんどかったです。

コンパイラに感謝する様子です

Rustへの理解が深まっていく様子です

VM実装終わったとき

Jack言語コンパイラに関しては再起下降パーサーを書いたことがあるので実装面で悩むことはなかったです

12章: オペレーティングシステム

正直ここからはおまけです。Jack言語でOSを書くのですが、このOSは上で述べたとおりハードウェアとのやりとりをするためのメモリアクセスを便利にしてくれるライブラリみたいなものです。 Jack言語も非力な言語なので書くのはダルかったです。 ただ、自作したコンパイラがちゃんとシンタックスエラーを検出してくれたときはちょっとしたうれしみが湧き上がりましたね?

たとえば、画面に文字を出力するのにDMAされた画面のピクセルに対応するメモリのビットをフォントにしたがって立てる処理とか書くのダルかったです。

あと、画面に●を描画する際の高速なアルゴリズムとか勉強になりましたね多分もう使うことないだろうけど

とはいえ、自分で書いたOS(っぽいライブラリ)でゲームが動いたときは達成感ありましたね。

まとめ

O'Reilly Japan - コンピュータシステムの理論と実装 、楽しいのでみんなやるといいですよ?

とくに、コンピューターサイエンスに苦手意識があるとかローレイヤー怖いとかの人におすすめです。やってみると、とてもシンプルな仕組みの積み重ねでコンピューターが動作していることが実体験として理解できます。 そして、現代のCPUやOSがどれだけ進歩しているかも……

本書で取り扱うそれぞれのトピックは概要レベルですので、例えばコンパイラについてもっと学びたいとかOSを詳しく知りたいというニーズには適してはいませんが、全体を俯瞰する入り口としては最適だと思います。

そして、理解を深めるにはものすごく単純でもいいから自分で作ってみるてっとり早いのですが、本書はそれを手助けしてくれる素晴らしい内容でした。 今後は、自作ブラウザとか自作TCP/IPプロトコル・スタックとか自作RDBMSとか、挑戦してみたいものが山積みです。

で次ですが、Nand2TetrisではOS部分が薄くて物足りないかったので、OSを作ってみることにしました。

12月は忙し目なので、年末年始からまた腰を据えて取り組みたいと思います。

あと、Rust完全にマスターしました(光を放ちながら消滅)

f:id:yuroyoro:20201210001321p:plain
Rust完全に理解した

ラズパイとWebRTCで動物の死活監視ができるようにした話

ラズパイ WebRTC

こんにちわ、しいたけです。

今は夏休みで奥さんと子どもたちが帰省しているので、動物と2人で暮らしています。

で、外出すると動物だけを家に残していくことになります。 ペットモニターとか市販でもあるんですが、せっかくなので、 夏休みの自由研究として、ラズパイ+カメラモジュールとWebRTCを使って、外出先からでも動物の状態を確認できるやつを作ってみました。

f:id:yuroyoro:20190812154310j:plain

↑ 死活監視される動物の様子です

用意したもの

ラズパイ3とケースのセットとカメラモジュールは Raspberry Pi Shop by KSY で購入。期間限定セールでちょっと安かったです。 このセットについてるケースは、ラズパイのマークの穴にカメラモジュールを固定することができて便利。 時雨堂のmomoだと、Raspberry Pi の GPU のH.264 ハードウェアエンコーダー機能を利用できるらしいので、ラズパイzeroでも行けるらしいです。

で、ラズパイを三脚とスマホ用アダプタで固定します。こんな感じになる。

f:id:yuroyoro:20190814165439j:plain

ラズパイの初期設定

まずはラズパイの初期設定でOSインストール。購入したキットのSDカードにすでにOSが用意されているので、電源入れて画面の通りにセットアップすれば終了。

Raspberry Pi 3 Model B+の初回セットアップ（購入から起動まで） - Qiita

あとは、sshとカメラモジュールをconfigから有効にしておく。

Raspberry Piカメラのセットアップ方法

最後に、mDNSとssh周りの設定を行って、GUIをオフにして完了。これで手元のmacbookからsshで接続して作業できるようになった。

手持ちのRaspberryPiをサクッとmDNSに対応させる - Qiita

WebRTC Native Client Momo

時雨堂の WebRTC Native Client Momo を使います。あっさり接続できて最高でした。

Githubのリリースページ から最新のバイナリがtarで配布されているので、ダウンロードして解凍するだけです。

必要なライブラリを入れて、

$ sudo apt-get install libnspr4 libnss3

あとはバイナリを実行するだけで、ラズパイのカメラモジュールを利用したストリーミングが可能になります。

$ ./momo --no-audio ayame wss://ayame-lite.shiguredo.jp/signaling <your-github-id>@<your-room-name> --signaling-key <your-signaling-key>

起動時のオプションは、シグナリングサーバーにAyameとそのURL、そしてルームIDを指定します。また、次で説明するシグナリングキーもわたします。

時雨堂 WebRTC シグナリングサービス Ayame Lite

WebRTCにおいてNAT超えで通信を行うにあたって、シグナリングサーバを介してそれぞれのピアの接続の調整を行う必要がある。 時雨堂がWebRTC の P2P 利用向けに無料で利用できるシグナリングサービスを提供してくれているので、ありがたく使わせていただきます。

WebRTC シグナリングサービス Ayame Lite 開発ログ

P2Pで接続できる場合には、特に登録も必要なく使えます。4G回線の場合などTURNサーバーを経由する必要がある場合は、ベータテスト中のシグナリングキーを利用してTURNサーバーの払い出しをしてもらう必要があります。 Githubアカウントでサインアップすると、シグナリングキーが発行されてTURN サーバの利用が可能になります。

STUN/TURNについてはこのあたり参照

4Gでつながらないとtwitterで囀っていたところ、 @voluntas にベータ版使ってみる? とお誘いを受けたので、ありがたく使わせてもらいました。 ちょうどオープンベータが始まったところでした。

Ayame Lite オープンベータテスト開始しました - shiguredo - Medium

こちらからGithubアカウントでサインアップできます。

Ayame Lite

時雨堂最高では?

クライアント側の実装

あとは、クライアントを準備して接続です。手っ取り早く試してみるのに、 OpenAyame/ayame-react-sample: Ayame React サンプル を利用しました。 上記のリポジトリを git clone したあと、 yarn install して yarn serve すると、localhostで動作確認ができます。

こんな感じで、AyameのURLと、自分で指定したルームID、シグナリングキーを入力して接続を押すと、ストリーミングでラズパイ側のカメラから配信されていることが確認できます。

f:id:yuroyoro:20190814182922p:plain

iOS Safariの場合は再生ボタンを押す必要があるとのことで、video タグに controls を追加して対応しました。

<Videos>
  <RemoteVideo ref={remoteVideoRef} muted autoPlay controls/>
</Videos>

その他調整

まず、クライアントのアセット一式を適当な場所から配信できるようにします。 yarn build してできた成果物をさくらVPSにnginxを立ててﾚｯﾂをｴﾝｸﾘﾌﾟﾄしてhttpsで配信できるようにしました。 httpsで配信できる場所なら、cloudfrontとかNetlifyとかでもいいと思います。

あとは、ラズパイ側のmomoをsystemdのサービスとして設定して起動時に起きるようにすれば終わりです。

Raspberry Pi で systemd を使ってプログラムを自動実行する - Qiita

まとめ

ラズパイでWebRTCするにあたって、当初は NTTコムさんの提供する Skyway とそのsdkを試してみたのですが、どうもデモが上手く動作しませんでした。 時雨堂のmomoとOpenAyameを使ってみたところ、バイナリを落としてきてドキュメントの手順通りに進めるだけであっさり接続できてしまいました。

これで外出時でも動物の様子を死活監視ができて捗る。

時雨堂最高では?

async/awaitとpromise使えばモナド糖衣構文っぽいの書けそうだよねって思って書いてみたけど、async () => {} でwrapしないといけないしまぁそんなにきれいに書けなかったって話

JavaScript

タイトルで全部言い切ってますが

// Optional container like maybe monad 
class Option {
  constructor(value){
    this.value = value
  }

  async promise() {
    return new Promise((resolve, reject) => {
      if (this.value) {
        resolve(this.value);
      } else {
        reject(undefined);
      }
    });
  }
}

こんなMaybe とかOptionalっぽいやつを用意します。 promise() で Promiseを生成して返すようにします。もってる値に応じて resolve (JustやSome)したり reject (Nothing)したりします。

const o1 = new Option("foo");
const o2 = new Option("bar");
const o3 = new Option(null);

(async () => {
  try {
    const v1 = await o1.promise();
    const v2 = await o2.promise();

    console.log(v1, v2);
  } catch {} 
})(); // => foo bar

(async () => {
  try {
    const v1 = await o1.promise();
    const v2 = await o2.promise();
    const v3 = await o3.promise();

    console.log(v1, v2, v3);
  } catch {} 
})(); // do nothing

// introduce doM emulates do-like syntax sugar 
async function doM(f1, f2) {
  try {
    return f1();
  } catch {
    if (f2) {
      return f2();
    }
  }
} // => foo bar

asyncの中で、 promise() を awaitで呼び出すことで、 do記法っぽいあれ……に見えなくもなくないコードになりました。でも失敗系処理しない場合でも catch 書く必要あるのダルいですね？ try..catch を変わりにやってくれるヘルパーを導入しましょう

// introduce doM emulates do-like syntax sugar 
async function doM(f1, f2) {
  try {
    return f1();
  } catch {
    if (f2) {
      return f2();
    }
  }
}

この doM に asyncな無名関数を渡すと、その中でdo記法っぽいあれ……に見えなくもなくないコードを書けます。

doM(async () => {
  const v1 = await o1.promise();
  const v2 = await o2.promise();

  console.log(v1, v2);
}); // => foo bar

doM(async () => {
  const v1 = await o1.promise();
  const v2 = await o2.promise();
  const v3 = await o3.promise();

  console.log(v1, v2, v3);
}); // do nothing

だからどうしたって話ですが、いろいろなモナドを作って合成して扱う場合に便利かもしれないですがそもそもモナドとかJavaScriptで作るな。以上

関数の話

関数型

こんにちは、しいたけです。

某所で関数型プログラミングとはリスト処理のことなのか、と燃えているのを見て、関数型プログラミングとは何か、ということを自分なりの考えを述べたいと思いました。春なので。

この資料は2年ほど前にSupershipの社内勉強会で使ったものですが、この中で関数とオブジェクトを対比している箇所があります。 関数もオブジェクトも、変数や関数の引数戻り値として扱える第1級の値であり、状態を持ち(メンバー変数/クロージャ)、組み合わせが可能(delegate, composition/関数合成)、である、と。

ではオブジェクト指向と関数型プログラミングで何が決定的に異なるかというと、設計・実装のアプローチに何を中心に据えるか、ということだと思います。

オブジェクト指向では、クラス・オブジェクトをモデリングし、各種のオブジェクト指向的デザインパターンを用いてオブジェクト同士を組み合わせながら設計・実装を行います。 関数型プログラミングでは、関数を細かな組み合わせ可能な単位に分解し、関数合成、再帰、クロージャなどを駆使しながら組み合わせることで設計・実装します。

こう書いてみると当たり前のことですが、コードの記述スタイルだけ議論しても意味がなくて、そのような記述はプログラム全体を貫く思想のなかでどのような位置づけにあるのかのコンテキストが重要なのではないでしょうか。 例えば、Goでは無理して無名関数を用いたリスト処理を書くより、forで書くほうがはるかに自然ですよね。 JavaScriptでは……どうでしょうか、色々なスタイルで書けるので議論が紛糾するのかも。

map/reduceを使ったリスト処理が関数型プログラミングの全てかというとそうではなく、あくまで関数を中心に据えた考えた方の一つとして、遅延評価 + 高階関数/クロージャの組み合わせによるストリームライクな実装がある、ということだと思います。 関数を中心に据えると、「何をフィルターするか」「要素をどのように変換するか」という処理の単位が関数として抽出され、その組み合わせ方法として遅延評価リストと高階関数を用いる方法がある、というだけです。 結果、関数を中心にすえたアプローチではmap/reduceを使う記述が自然と導かれます。 とはいえ、 リスト処理の実装としては再帰を使う方法もあるので、あくまで関数型プログラミングによるリスト処理の1アプローチにすぎません。

どちらのスタイルで書くのがよいか、というのに絶対的な正解はないと思いますが、関数を中心としたアプローチを知っていると、手続き型のプログラムを書いていても思わぬ場面で役に立つことがあります。 ちょうど最近役にたった実体験のひとつで、 ある rspecのパフォーマンスチューニングの際に遅延評価が役にたったことがあります。

error_msg = generate_error_message(actual_value, expected_value)
expect(actula_value).to have_content(expected_value),  error_msg

こんな感じのrspecのコードで、 assertのエラー時に表示する error_msg を生成する generate_error_message が非常にコストの掛かる処理でした。 通常はassertに失敗する場合の方が稀なので、必要になるまで(assertに失敗するまで) この処理の呼び出しを遅延させることで性能が改善しそうです。

rspecの expect はエラーメッセージの代わりに Proc を渡すことが可能です。 そこで、エラーメッセージを生成する処理をクロージャとして抽出し、 expect に渡すことで遅延評価させることができます。

error_msg_generator = ->() { generate_error_message(actual_value, expected_value) }
expect(actula_value).to have_content(expected_value),  error_msg_generator

関数型プログラミングの知識があると、 expect の引数が Proc を取る、というシグニチャから、遅延評価による性能改善に利用する発想が導かれます。 このように、関数型プログラミングは通常の手続き型プログラミングでもおおいに役立ちますので、双方それぞれの手法を学んでおくとプログラミングの裾野が広がりま。 これが、ぼくが関数型プログラミングを学ぶことをオススメする理由です。

まとめ

しいたけおいしいです。

作って学ぶ 「Https Man in The Middle Proxy」 in Go

Golang

ᕕ( ᐛ )ᕗ こんにちわ、しいたけです。

webのhttps化が推進される昨今ですね?
https通信は経路上での通信内容が盗聴・改竄されるのを防ぐことができますが、開発用途でhttps通信の内容を確認したい場合が稀にあります。
そのような場合は mitmproxy などを導入すればよいのですが、せっかくなので実際にこのようなProxyをGoで実装してみて、 中間者攻撃(Man-in-The-Middle Attack)がどのような手法でhttps通信を盗聴・改竄するのか確かめてみました。

実際に書いたProxyのコードはこちらです

yuroyoro/mitm_proxy_sample

https proxy と HTTP CONNECT tunneling

まず、通常のhttps Proxyの動作を確認してみましょう。

httpsでは、ProxyはクライアントからのCONNECTメソッドを受信すると、クライアントに代わって対象ホストとのTCPコネクションを確立し、以降はクライアントと対象ホストのTCP通信を転送します。クライアント-ホスト間のTLS接続のhandshakeもproxyを経由して行わます。
この方式により、Proxyを経由しつつクライアント-ホスト間でTLSセッションが確立され、Proxyを経由しつつも経路上では暗号化された通信が可能となります。

図にするとこんな感じです

f:id:yuroyoro:20180216193239p:plain

実装

では具体的な実装を見てましょう。
まずはおなじみ ServeHTTP です。クライアントから CONNECT メソッドが送信されたら、通信を転送する relayHTTPSRequest を呼び出します

https://github.com/yuroyoro/mitm_proxy_sample/blob/master/main.go#L34

func (proxy *MiTMProxy) ServeHTTP(w http.ResponseWriter, r *http.Request) {
  // CONNECT メソッドが来たら
    if r.Method == http.MethodConnect {
        if proxy.mitm {
            proxy.mitmRequest(w, r)  // Man in The Middleする
        } else {
            proxy.relayHTTPSRequest(w, r) // Tunnelingで通信を転送する
        }
        return
    }

    proxy.transportHTTPRequest(w, r)
}

実際に通信を転送しているコードは以下のとおりです。処理の流れはコメントを読んでもらえばわかると思いますが、やっていることは単純です。
CONNECT メソッドで指定されたホストにTCP接続を張って、クライアントからの通信をそのまま流し込むだけです

https://github.com/yuroyoro/mitm_proxy_sample/blob/master/https.go#L12

func (proxy *MiTMProxy) relayHTTPSRequest(w http.ResponseWriter, r *http.Request) {
    proxy.info("relayHTTPSRequest : %s %s", r.Method, r.URL.String())

    // CONNECT先のHostへTCPコネクションを張る
    dest, err := net.Dial("tcp", r.Host)
    if err != nil {
        http.Error(w, err.Error(), http.StatusServiceUnavailable)
        return
    }

    // http.Hicjacker を利用してクライアントとの生のTCPコネクションを取り出す
    conn := hijackConnect(w)
    // クライアントには200 OKを返す。これでクライアントはこのTCP接続にHTTPリクエストを送ってくる
    conn.Write([]byte("HTTP/1.0 200 OK\r\n\r\n"))

    proxy.info("relayHTTPSRequest : start relaying tcp packets %s %s", r.Method, r.URL.String())

    // クライアント-対象Host間のTCP通信をそのまま中継する
    go transfer(dest, conn)
    go transfer(conn, dest)
}

func transfer(dest io.WriteCloser, source io.ReadCloser) {
    defer dest.Close()
    defer source.Close()
    io.Copy(dest, source)
}

Goには http.Hijacker という便利なインターフェースがあり、 http.ResponseWriter から生のクライアントとのTCP接続を取り出すことができます。
これを利用して、TCP通信の転送を行っています

func hijackConnect(w http.ResponseWriter) net.Conn {
    hj, ok := w.(http.Hijacker)
    if !ok {
        panic("httpserver does not support hijacking")
    }

    conn, _, err := hj.Hijack()
    if err != nil {
        panic("Cannot hijack connection " + err.Error())
    }

    return conn
}

実際はtimeoutなどを考慮した実装をすべきなのですが、これだけでも動きます。

Man in The Middel Proxyの仕組み

では、本題の中間者攻撃を行うProxyについてです。

通常のhttps proxyでは、クライアントからの CONNECT メソッドを契機に、対象HostとのTCP通信を中継していました。
Proxyを流れる通信内容はTLSによって暗号化されており、内容を盗聴・改竄することはできません。

しかし、対象Hostとクライアント間のTLS handshakeもProxyを経由するので、この段階でクライアントからのTLS handshakeを、対象ホストになりすましてProxyが行うとどうなるでしょうか？
つまり、Proxyは対象ホストのサーバー証明書をその場で生成して署名し、クライアントに提示します。
もちろん、Proxyが署名したサーバー証明書は信頼できないCAのものとしてブラウザには警告が出ますが、そのままユーザーが続行することでTLS handshakeが成功します。
クライアントは確立したTLS接続を対象ホストとのものだと思いこんで、Proxyがクライアントに送り込んだニセのサーバー証明書の公開鍵で通信を暗号化するので、Proxyはその内容を復号することができます。
あとは、復号したリクエストをそのまま対象のホストに転送すれば、httpsにも関わらずProxyは通信内容を把握しつつ、対象ホストとの通信を取り持つことができてしまいます。
これで中間者攻撃が成立しますʕ　 ﾟ皿ﾟ ʔ 。

図にすると以下の流れとなります

f:id:yuroyoro:20180216193258p:plain

通常、このような攻撃はブラウザが警告を出すために成立しません。
まず、ユーザーが明示的にブラウザにProxyを指定する必要がありますし(port forwardを利用した透過Proxyはその限りではない)、Proxyが署名に使用するルート証明書(または中間証明書)がTrust Chainにないからです。
逆に言えば、信頼できないルート証明書をシステムにインストールしてしまうと、このような攻撃が成立する余地が生まれてしまいます。

実際に、一部のセキュリティアプライアンスやアンチウィルスソフトウェアは、このような手法でhttps通信の内容をチェックしています。
Avastを入れた状態でブラウザで証明書チェーンを確認すると、 「Avast trusted CA」という謎の認証局が出現するのはこのためです( ;ﾟ皿ﾟ)ﾉｼΣ ﾌｨﾝｷﾞｨｨｰｰｯ!!!

以前、LenovoのPCにプリインストールされたアドウェア「Superfish」がルート証明書をシステムにインストールした上に、全PCで共通のCA秘密鍵を使っていたことで大問題になりましたね。
Dellでも似たようなことがあったみたいです( ꒪⌓꒪)

LenovoのPC全機種にプレロードされているアドウェアが実は恐ろしいマルウェアだった！ | TechCrunch Japan DellのPCに不審なルート証明書、LenovoのSuperfishと同じ問題か - ITmedia エンタープライズ

実装

それでは具体的な実装の解説を行います。処理の流れは以下のとおりです。

  1. CONNECTメソッドのリクエストから、http.Hijackerを使って生のTCPコネクションを取り出す
  2. クライアントには200 okを返す
  3. 接続先ホストの証明書を、予め用意してあるroot証明書でサインして生成する
  4. 生成した証明書でクライアントとtls接続を確立する (root証明書が登録されていないとブラウザで警告が出る)
  5. goroutine起こして、クライアントとのtls接続からhttp requestを読み込む
  6. 受けたhttp requestをそのまま接続先hostに送信する
  7. 接続先hostからのhttp responseを、クライアントtls接続に書き込む
  8. EOFが来るまで 5-7繰り返し

https://github.com/yuroyoro/mitm_proxy_sample/blob/master/https.go#L57

func (proxy *MiTMProxy) mitmRequest(w http.ResponseWriter, r *http.Request) {
    // http.Hicjacker を利用してクライアントとの生のTCPコネクションを取り出す
    conn := hijackConnect(w)
    // クライアントに200 OKを返しておく
    conn.Write([]byte("HTTP/1.0 200 OK\r\n\r\n"))

    // 以降の処理はgoroutine上で行う
    go proxy.transportHTTPSRequest(w, r, conn)
}

func (proxy *MiTMProxy) transportHTTPSRequest(w http.ResponseWriter, r *http.Request, conn net.Conn) {
    proxy.info("transportHTTPSRequest : %s %s", r.Method, r.URL.String())

    // 対象ホストのニセのサーバー証明書を生成して署名する
    host := r.Host
    tlsConfig, err := proxy.generateTLSConfig(host)
    if err != nil {
        if _, err := conn.Write([]byte("HTTP/1.0 500 Internal Server Error\r\n\r\n")); err != nil {
            proxy.error("Failed to write response : %v", err)
        }
        conn.Close()
    }

    // クライアントとのTCP接続上で、ニセのサーバー証明書を利用してTLS接続を待ち受ける
    tlsConn := tls.Server(conn, tlsConfig)
    if err := tlsConn.Handshake(); err != nil {
        proxy.error("Cannot handshake client %v %v", r.Host, err)
        return
    }
    defer tlsConn.Close()

    proxy.info("transportHTTPSRequest : established tls connection")

    // ニセの証明書で確立したTLS接続上でクライアントからのリクエストを読み込む
    tlsIn := bufio.NewReader(tlsConn)
    for !isEOF(tlsIn) {
        req, err := http.ReadRequest(tlsIn) // http.Requestオブジェクトとして通信を読み込む
        if err != nil {
            if err == io.EOF {
                proxy.error("EOF detected when read request from client: %v %v", r.Host, err)
            } else {
                proxy.error("Cannot read request from client: %v %v", r.Host, err)
            }
            return
        }

        proxy.info("transportHTTPSRequest : read request : %s %s", req.Method, req.URL.String())

        // 転送用にURLやヘッダーなどを設定
        req.URL.Scheme = "https"
        req.URL.Host = r.Host
        req.RequestURI = req.URL.String()
        req.RemoteAddr = r.RemoteAddr

        dumpRequest(req)
        removeProxyHeaders(req)

        // http.RoundTripper で受信したリクエストを対象ホストに転送し、レスポンスを受け取る
        resp, err := proxy.transport.RoundTrip(req)
        if err != nil {
            proxy.error("error read response %v %v", r.URL.Host, err.Error())
            if resp == nil {
                http.Error(w, err.Error(), 500)
                return
            }
        }

        proxy.info("transportHTTPSRequest : transport request: %s", resp.Status)

        dumpResponse(resp)

        // レスポンスをクライントへのTLS接続に書き込む
        resp.Write(tlsConn)
    }

    proxy.info("transportHTTPSRequest : finished ")
}

ポイントは、 リクエストを受けるとニセのサーバー証明書をその場で生成して、その証明書と http.Hijacker で取り出したクライントのTCPで tls.Server を用いてTLS接続をなりすますことです(生成した証明書はキャッシュします)。
証明書の生成は長くなるのでここには載せませんが、 こちら を見てもらえばと思います。

クライントとのTLS接続を乗っ取れば、あとはその接続上でHttpリクエストを読み込み、対象ホストに転送すればOKです。Goでは、 http.RoundTripper を利用すれば http.Request をそのまま転送できるので便利です。その際に、リクエスト・レスポンスの内容をdumpしています。
悪意があれば、この段階で改竄も可能でしょう。

まとめ

以上が、Man-in-The-Middle Attackを行う簡単なProxyの実装です。この攻撃が成功する条件としては、

  • 経路上にこのようなProxyが存在する (https通信がport forwardされている場合もある)
  • Proxyが署名に使うルート証明書がTrust Chainに存在する

の2点です。特に2点目はTLSの根幹をなす部分で、それゆえにルート証明書の管理は厳格に行う必要があり、GoogleはSymantecの証明書を無効にし、LenoveやDellは責められるべきなのです。Avastもちょっとどうかと思います。

実際に手を動かして実装してみると、Proxyの実装で注意スべき点や、TLSと認証局の仕組みとか色々と学びがあり、よかったとおもいました( ꒪⌓꒪)

go tool traceでgoroutineの実行状況を可視化する

こんにちわ。しいたけです。今日はgoroutineの実行状況をいいかんじに可視化するツールの話です。

goのプロファイリングツールと言えば、 runtime/pprof や net/http/pprof ですよね。これらの使い方はググればすぐに出てくるのですが、 詳細なtraceを取得して可視化できる runtime/trace については、日本語の情報が殆ど無いので書いてみましいたけ。

runtime/trace はgoroutineの実行状況やsystem callのイベント、Heapやnetworkの状況をこんな感じに可視化してくれるので便利です。

f:id:yuroyoro:20171211191843p:plain

これは自作のクローラーを動かしている際のtraceを可視化したもので、横軸がタイムラインになっており、上段に Heapの使用状況やgoroutineとos threadの数が, 下段はnetworkやProccesor(GOMAXPROCSで指定するgoroutineの実行環境)毎にどのコードが実行されているか、が表示されます。

Heapやgoroutines数の増減と処理の関連を時系列で追えるので、大まかなボトルネックの特定に便利です。また、各goroutine毎の開始/終了とsystem callやunblockイベント(goroutineの切り替え)を細かく追えるので、goroutineが刺さっている箇所の特定にも役立ちます

右側のboxの↓アイコンをクリックした上で、グラフ上でドラッグするとzoomin/outできます。また、View Options で Flow Eventsをチェックすると矢印が描画されます

ここに、実際に動かせるサンプルを置いておきます。

f:id:yuroyoro:20171211191957p:plain

これはとある自作Proxyのtraceの一部で、Proc3で実行されている皆さんおなじみの net/http.(*conn).serve がリクエストを受けて、 go 構文で新たなgoroutineを起動してProc2で実行される様子です。このように、どのタイミングでどのgoroutineが動いたのかが一目瞭然です。

f:id:yuroyoro:20171211192018p:plain

これはGCが実行されている様子です。ほとんどのProcでGC関連の処理が動いた後に、上段のHeapのallocatedが減っている様子が見てとれます。

で、このtraceの可視化の方法ですが、 手っ取り早いのは runtime/trace パッケージをimportして、 trace.Start(w io.Writer) と trace.Stop() を呼び出す方法です

https://golang.org/pkg/runtime/trace/

package main

import (
    "log"
    "os"
    "runtime"
    "runtime/trace"
)

func main() {

    f, err := os.Create("trace.out")
    if err != nil {
        log.Fatal(err)
    }
    defer f.Close()

    trace.Start(f)
    defer trace.Stop()

  // do something ...
}

このように、traceを取得したい処理の前後で trace.Start を呼び出すと、結果がファイルに出力されます。 そのファイルを go tool trace コマンドの引数に渡すと、ブラウザで取得したtraceを分析できるようになります。

net/http/pprof パッケージを使っているウェブアプリケーションでも、簡単にtraceを取得することができます。

pprofがlistenしているなら、 /debug/pprof/trace?seconds=5 にリクエストを送ると、5秒間のtraceを取得して結果をダウンロードできます。得られたファイルを go tool trace に渡せば、同様にブラウザ上で分析できます。

詳細なボトルネックの分析は、 pprofやgo-torchでのflamegraphの分析が有向ですが、 go tool trace では時系列に対応しての分析が可能なので、それぞれ状況に合わせて使い分けると良いのではないかと思いましいたけ。

F.Y.I.

ディスク使用量をFlameGraphで可視化する

Golang

こんにちわ。しいたけです。今日はディスク使用量をFlameGraphにするツールの話です。

FlameGraphについては、 Flame Graphs や GolangでFlame Graphを描く | SOTA を読んでもらうのが手っ取り早いのですが、ようはプロファイル結果を可視化する方法です。縦軸が呼び出しの階層に、横軸がサンプル数や実行時間などに対応しており、どの関数が支配的かを直感的に見ることができる優れたグラフですよ。

で、このFlameGraph、別にプロファイル結果だけではなく、ツリー構造で各ノードが量を持つ場合に、枝毎の累積量を可視化するのに利用できます。プロファイル以外に、ツリー構造でノードが量を持つ例として、ディレクトリ階層毎のディスク使用量が考えられます。

というわけで、指定ディレクトリ以下のディスク使用量をFlameGraph化するツールを書きました。

GitHub - yuroyoro/du-flamegraph: visualize disk usage as flamegraph

こんな感じのグラフが出力されます

http://yuroyoro.net/du-flamegraph.svg


goで書かれており、使い方は、 `go get -u yuroyoro/du-flamegraph` でインストールできます。

このツールは、 FlameGraphの描画に `flamegraph.pl` というスクリプトが必要であり、これは GitHub - brendangregg/FlameGraph: Stack trace visualizer にあります。
これを git cloneなどで手元に入れて、 $PATHに追加するか、 `--flamegraph-script` で位置を指定するかしてやれば、FlameGraph がsvgとして出力されます。

NAME:
   du-flamegraph - visualize disk usage as flamegraph

USAGE:
   du-flamegraph [global options] [FILE]

VERSION:
   0.0.0

GLOBAL OPTIONS:
   --width value, -w value    width of image (default 1200) (default: 1200)
   --height value, -h value   height of each frame (default 16) (default: 16)
   --flamegraph-script value  path of flamegraph.pl. if not given, find the script from $PATH
   --out value                distination path of grenerated flamegraph. default is ./du-flamegraph.svg (default: "./du-flamegraph.svg")
   --verbose                  show verbose log
   --version, -v              print the version

FlameGraph、色々と応用がききそうですね。