Hatena::ブログ(Diary)

あどけない話

2015-01-28

Haskell の Monad とは言語内DSLのフレームワークである

この記事は、Haskellを勉強してある程度分かったけど、Monadで挫折した人のための記事です。10分間で、Monadに対する納得感を得ることを目的としています。他の言語でいう「モナド」にも通用する内容ですが、Haskell の文法や用語を用いますので、他の言語の利用者に分かるかは不明です。

Haskellを勉強したのですから、

  • 代数データ型
  • 型クラス

は分かっていることにします。Monad は、単なる型クラスの一つで、それ以上でもそれ以下でもありませんから、この二つが分かってないと話になりません。

また、言語内DSL(以下、DSLと略記)という考え方を知っていることも仮定します。Monad とは、DSLフレームワークという直感を与えるのが、この記事の主眼ですからね。

さらに、構造化定理をいう単語を聞いてもビビらない人を想定しています。逐次、反復、分岐があれば、計算しうる計算はすべて記述できるという定理です。Monad の説明にありがちな圏論を持ち出されるより、よっぽどいいでしょう?

Monad とは何か?

繰り返しになりますが、Monad とは単に型クラスの一つです。そして、Monad とは、DSLのためのフレームワークです。つまり、ある代数型を Moand 型クラスのインスタンスにすれば、何らかの DSL になるということです!

DSLの例を挙げてみましょう。

代数データ型

驚くべきことに、Haskell で m a という形の代数データ型を定義すると、それはDSLになる可能性を秘めています。一番簡単な以下のような代数データ型でさえ、(何もしないとういう)DSLになります。

data Identity a = Identity a

一般的に関数は a -> b という型の形を持っています。一方、a -> m b という形の関数は、m のところに「計算以外の仕事」という意味が含まれるようになります。(「計算以外の仕事」のことを命令型では「副作用」、関数型ではエフェクトと呼んだりします。) Monadインスタンスとは、この計算以外の仕事をする DSL なのです。

Functor 型クラス

代数データ型を定義すれば、DSLになることが分かりましたが。次は、このDSLの中で、(a -> b の形をした)「既存の関数」が使いたくなるでしょう。この既存の関数DSL を結びつけるのが Functor 型クラスです。

class Functor m where
  (<$>) :: (a -> b) -> m a -> m b -- 実際は fmap

こんな風に使えます。

> (+1) <$> Identity 1
Identity 2

Applicative 型クラス

DSLというからには、構造化定理でいう逐次、反復、分岐ができるべきでしょう。この内の二つ、つまり逐次と反復を実現するのが、Applicative 型クラスです。

class Functor m => Applicative m where
  return :: a -> m a  -- 実際は pure
  (<*>)  :: m (a -> b) -> m a -> m b

逐次と反復がないと実現できない sqnc という関数をこれらの関数を使って定義してみましょう。

sqnc :: Applicative m => [m a] -> m [a]
sqnc []     = return [] -- 実際は pure にしてね
sqnc (x:xs) = (:) <$> x <*> sqnc xs

以下のように逐次実行できます。

sqnc [putStrLn "Hello", putStrLn "World"]
Hello
World
[(),()]

また、sqnc の中では再帰が使えていますから、反復できているのも明らかです。

Monad 型クラス

残るは分岐です。これを実現するのが、Monad です。

class Applicative m => Monad m where
  (>>=) :: m a -> (a -> m b) -> m b

分岐の例を一つ示しましょう。ファイルがあったら削除するというコードは、以下のようになります。


doesFileExist :: FilePath -> IO Bool
removeFile :: FilePath -> IO ()

removeFileIfExist :: FilePath -> IO ()
removeFileIfExist file = doesFileExist file >>= \exist ->
  if exist then
    removeFile file
  else
    return ()

まとめ

m a という形の型を Functor、Applicative、Monad と出世させていけば、利用できる機能が多くなり、最後にりっぱな DSL となったことが分かったでしょう。Monad を利用するだけなら、これ以上 Monad のことを深追いする必要はありません。あとは、たくさんコードを書いて慣れるのみです。

もう少し詳しく勉強したい人のために、参考文献/記事を挙げておきます。

2014-12-25

Haskell Relational Record をリリースしました

Haskell Relational Record (HRR)尻叩き担当の山本です。この記事では、HRR のリリースについて説明します。

なお、これは Haskell Advent Calendar 2014 の25日目の記事です。

HRR とは何か?

HRRは、日比野さんが中心となって開発が進められている関係代数ライブラリです。Haskellで式を書くと、それがSQL文に変換され、データベースに問い合わせた結果が Haskellレコードになります。以下のような特長があります。

HRRはASAHIネットの内部システムで1年以上稼働しており、その品質は安定しています。

リリース合宿

本当なら、1年前、日比野さんが Haskell Advent Calendar 2013 の記事を書いたころに、HRR をリリースすべきだったのですが、多忙に負けてできませんでした。最近では、ヨーロッパ方面からもリリースの要望が出るようになっていました。そこで、12月11日から12日の間、山本が住んでいるマンションのゲストルームを借りて、日比野さん、多大な貢献をしている村山さん、そして山本の三人で合宿を張まりました。

合宿までの宿題

合宿までに HRR を Hackage に登録するように日比野さんにお願いしました。バラバラになっている貢献されたコードをかき集め、形を整えて Hackage に登録する作業は、とても大変だったそうです。

リリースするということは、マニュアルを書かないといけません。昔からチュートリアルも書こうという話をしていました。チュートリアルでは、直接SQLで書くような難しいことも書けることを示すために、実践的な例題を載せたいと思っていました。その例題は、実際のデータベースに対して動くべきです。

そこで、「初めてのSQL」に載っているSQLをHRRで書いちゃえ作戦が一年前から始まっていました。当時のHRRは、オープンソースSQL データベースサーバとして PostgreSQL しかサポートしていませんでした。一方で「初めてのSQL」は、MySQL を前提としています。サポートページで提供されているテーブルを生成するスクリプトは、当然のように PostgreSQL では動きません。そこで昨年、山本が PostgreSQL 用に書き直し、例題のテーブルを作成するようにしました。また、そのテーブルに対して動くSQLをいくつか選定しました。それを村山さんが HRR に変換してくれていました。

今回チュートリアルの作業を再開するにあたり、山本がPostgreSQLの動かし方をすっかり忘れていたこと、そして HRR が SQLite をサポート済みだったことから、MySQL 用のスクリプトを今度は SQLite 用に書き直しました。SQLite を使ってチュートリアルを書く方が、断然敷居が下がるからです。

村山さんは、古くなっていたHRRの例題をSQLiteで動くようにする作業をしました。SQLite には、例えば日付リテラルがありません。あればちゃんと型が付くのですが、ないので文字列操作で誤魔化す必要があるのです。

合宿1日目

HRRのプロジェクトページの作成には、github Page を使うことにしました。そしてコンテンツとしては、クイックスタート、チュートリアル、例題集、およびマニュアルを置くことにしました。

1日目の成果として、HRRのプロジェクトページクイックスタートができました。クイックスタートでは、式が合成できることを見せたかったので、式 hello と world を使って helloWorld を構築できることを示しました。

合宿2日目

チュートリアルができました。1年遅れたのは悪いことですが、そのおかげで SQLiteを使って説明できました。あれこれ説明する必要はまったくなくなりました。たとえば、例題を動かした後にテーブルを消したくなったら、単にファイルを消せばよいのです。

また、例題もいくつか公開ました。そして、日比野さんが合宿中に育てたマニュアルにリンクを貼りました。

リリース

そして、ついに日比野さんがhaskell-cafe に対してリリースのアナウンスをしました。

例題の更新

例題を更新しようとしています。挿入、更新、削除、および相関サブクエリなどを増やす予定です。

さらなる展開

HRRのリリースしたおかげで、筑波大学亀山研究室の目に止まり、本日筑波大学へ出かけて議論してきました。

今後の僕の仕事は、論文を書くよう日比野さんのお尻を叩くことになりそうです。

2014-12-19

HTTP/2から見えるTLS事情

これは HTTP/2 アドベントカレンダー19日目の記事です。

この記事はたくさんの資料を読んだ上で書きましたが、間違いとか勘違いとかがあるかもしれません。もしあれば、指摘していただけると幸いです。

実質的に必須となったTLS

HTTP/2は、HTTP/1.1と同じく、暗号化なし/ありのポートとして、80と443を使います。そのため、通信開始時にHTTP/1.1とHTTP/2をネゴシエーションするための仕組みが、HTTP/2で定められています。

このように仕様としては暗号化なしのHTTP/2が定義されていますが、FirefoxChromeTLS を要求するために、実質的は暗号化ありが必須となっています。これは、米国の監視プログラムPRISMに代表される広域監視(pervasive surveillance)に対抗するために、IETFがさまざまな通信にプライバシの強化を要求する方向に舵を切ったことが影響していると思われます。

この記事では、HTTP/2 を動機付けとして、TLSの最新事情について説明します。

HTTP/2が要求するTLS

ネットスケープコミュニケーションズ社が1994年に世に送り出した SSL 2.0 は、SSL 3.0(RFC6101) を経て IETF標準化され TLS となりました。TLS は、1.0(RFC2246)、1.1(RFC4346) と改定されていき、最新のバージョンは 1.2(RFC5246) です。そして、現在 TLS 1.3 が標準化されようとしています

端的に言えば、HTTP/2が要求するTLSは、来るTLS 1.3時代を見据えて、以下のように TLS 1.2の機能を限定して使っています。

ネゴシエーションの利用禁止

2009年に再ネゴシエーションに関する脆弱性が発見されました。詳しくは「SSL/TLSのrenegotiation(再ネゴシエーション)における脆弱性」を参照してください。TLS 1.2 以前のすべての SSL/TLS にこの脆弱性があります。対策は、RFC5746で定められている拡張を実装することです。

この拡張を実装すれば、再ネゴシエーションは(今のところ)安全です。では、なぜ HTTP/2 で禁止するのでしょうか?

実は、再ネゴシエーションには2つの用途があります:

ネゴシエーションというと「共有鍵の更新のため」というイメージがあるかもしれませんが、実際にはクライアント認証のために使われていることの方が多いでしょう。

クライアント認証のための再ネゴシエーションは、以下のようなストーリーが一般的です:まず、あるブラウザTLSクライアント認証を要求しないコンテンツにアクセスします。そのページにあるリンクを辿ろうとすると、そのコンテンツはクライアント証明書を要求するよう設定されていました。この場合、サーバは再ネゴシエーションを開始し、ブラウザクライアント証明書を要求します。

HTTP/1.1とTLSという異なる層が協調して動作できるのは、HTTP/1.1が同期的なプロトコルだからです。一方、HTTP/2は、通信路を複数のストリームが非同期に行き交っていますので、再ネゴシエーションを開始する安全なタイミングを決めるのは、簡単ではないと思われます。

このHTTP/2の要請から、TLS 1.3 では再ネゴシエーション自体が削られる予定です。そして、二つの機能を分け、それぞれの役割を果たす方式が定義される見込みです。

圧縮機能の利用禁止

圧縮機能を使うと、CRIME攻撃にさらされます。たとえば、攻撃者がいる公衆無線LANに被害者が接続してしまったとしましょう。攻撃者の目的は、この被害者からあるサイトのクッキーを盗むことです。攻撃者は、なんとかして被害者を特定のサイトに誘導し、被害者のブラウザに悪意のスクリプトダウンロードさせます。ここで攻撃者ができることは、次の二つです。

このスクリプトは、HTTPヘッダを少しづつ変えなから、目標のサイトにHTTPリクエストを送り続けます。追加するヘッダによっては、その一部とクッキーの一部が一致する場合があるでしょう。圧縮が使われていれば、この重複が圧縮され、パケットのサイズが変わります。つまり、パケットの中身を見なくても、クッキーが予想できるのです。

以下に TLS 1.1 のデータ構造を示します。まず、平文(TLSPlaintext)は、こうなっています。

      struct {
          ContentType type;
          ProtocolVersion version;
          uint16 length;
          opaque fragment[TLSPlaintext.length];
      } TLSPlaintext;

TLSPlaintext を圧縮すると、TLSCompressed になります。

      struct {
          ContentType type;       /* same as TLSPlaintext.type */
          ProtocolVersion version;/* same as TLSPlaintext.version */
          uint16 length;
          opaque fragment[TLSCompressed.length];
      } TLSCompressed;

最後に TLSCompressed が暗号文 TLSCiphertext に格納されます。

      struct {
          ContentType type;
          ProtocolVersion version;
          uint16 length;
          select (SecurityParameters.cipher_type) {
              case stream: GenericStreamCipher;
              case block:  GenericBlockCipher;
          } fragment;
      } TLSCiphertext;

       stream-ciphered struct {
           opaque content[TLSCompressed.length];
           opaque MAC[CipherSpec.hash_size];
       } GenericStreamCipher;

       block-ciphered struct {
           opaque IV[CipherSpec.block_length];
           opaque content[TLSCompressed.length];
           opaque MAC[CipherSpec.hash_size];
           uint8 padding[GenericBlockCipher.padding_length];
           uint8 padding_length;
       } GenericBlockCipher;

圧縮を使わないとき(圧縮方式が null のとき)は、TLSPlaintext を変更なしにコピーして、TLSCompressed を作成します。

必須の暗号スイート

TLS1.2の必須暗号スイートは、TLS_RSA_WITH_3DES_EDE_CBC_SHA です。これは以下のように解釈します。

HTTP/2で必須のTLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256は、TLS 1.2 以降で使え、以下のように解釈します。

  • 鍵交換は短命楕円 Diffie Hellman (ECDHE: Elliptic Curve Diffie Hellman, Ephemeral)
  • サーバ認証は RSA
  • 通信の暗号化は AES 128 の GCM (Galois/Counter Model) モード
  • MACを生成する関数がSHA256

ECDHE と DHE

HTTP/2 では、TLSの鍵交換は短命楕円 Diffie Hellman に加えて、短命 Diffie Hellman (DHE)でもよいとされています。RSAに変わって、これらが要求されるのはなぜでしょうか? これにも広域監視が影響しています。

広域監視が、あるサーバTLSの通信を長年に渡って保存していたとしましょう。そのサーバは鍵交換にRSAを使っていました。あるとき、サーバ機器の入れ替えがあり、そのサーバが破棄されたのですが、ディスクを破壊することを忘れました。このディスクを広域監視をしている人達が入手したとすると、RSA秘密鍵を取り出せます。そして、記録した TLS の通信を復号化し、過去すべての通信内容を見ることができるようになります。

これに対抗するには、前方秘匿性(forward secrecy)を備えた鍵交換を利用する必要が有ります。短命楕円 Diffie Hellman や短命 Diffie Hellman の「短命」とは、この前方秘匿性を有していること表しています。これらの鍵交換では、一時的な秘密鍵(と公開鍵)を作り使い捨てます。そのため、ある時点での秘密鍵が漏洩しても、過去すべての通信が復号化されるという危険性はありません。

今年話題になった Heartbleed では、秘密鍵が漏洩される危険性が指摘され、実際に Heartbleed challenge で、秘密鍵が漏洩されることが実証されました。そもそも、個人的にはネゴシエーション以降利用しない秘密鍵をメモリ中に保存している実装がおかしいとは思いますが、世間的には秘密鍵の漏洩も実際に起こりうることをこの事件は印象付けたようです。

AES GCM と AEAD

上記のように TLS では、CBCモードのブロック暗号(GenericBlockCipher)とストリーム暗号(GenericStreamCipher)が定義されています。

TLS 1.0 以前のCBCモードに対する有名な攻撃としては、BEASTがあります。また、これまでの「MAC暗号化」方式は脆弱であり、「暗号化後MAC」を使えというRFC7366も発行されています。さらに、これは SSL 3.0 に限定的な話ですが、POODLE という攻撃方法も発見されてしまいました。

一方、ストリーム暗号の実質上唯一の選択である RC4 にはたくさんの脆弱性が見つかっています。また、RC4の利用を禁止しようというドラフトもあります。

TLSを策定している人たちの間には、再ネゴシエーションや圧縮に加えて、ストリーム暗号CBCモードのブロック暗号もダメなのではないかという空気があるようです。残された希望は、第三の暗号化 AEAD(Authenticated Encryption with Associated Data) です。

AEADとは、暗号化と同時に認証もする暗号方式の総称です。そのような AES のモードとしては、GCM (Galois/Counter Mode) や CCM (CBC MAC Mode) があります。TLS 1.2 では、AEAD 用の書式として GenericAEADCipher が定められています。


      struct {
          ContentType type;
          ProtocolVersion version;
          uint16 length;
          select (SecurityParameters.cipher_type) {
              case stream: GenericStreamCipher;
              case block:  GenericBlockCipher;
              case aead:   GenericAEADCipher;
          } fragment;
      } TLSCiphertext;

      struct {
         opaque nonce_explicit[SecurityParameters.record_iv_length];
         aead-ciphered struct {
             opaque content[TLSCompressed.length];
         };
      } GenericAEADCipher;

暗号文自体に認証データが埋め込まれているため、GenericStreamCipher や GenericBlockCipher には存在する MAC が、GenericAEADCipher にはないことに注意しましょう。

暗号強度

最も弱い環の原則を知っていますか? "A chain is no stronger than its weakest link" という英語の諺があります。全体の強度は、一番弱い部品によって決まるという意味です。全体の強度を上げるには、一番弱い部品の強度を上げなければならない。これが、最も弱い環の原則です。

暗号システムを構築する際も、弱い部品があれば、全体の強度がそれに押し下げられてしまいます。そこで、すべての部品の強度を合わせないといけません。この指標が暗号強度であり、共有鍵暗号のビット数を使って表されます。

以下、「デファクトスタンダード暗号技術の大移行(5)」より暗号強度の表を抜粋します。

暗号強度80112128192256
共有鍵暗号80112128192256
RSA102420483072768015360
Diffie Hellman102420483072768015360
楕円曲線暗号160224256384512
ハッシュ160224256384512

もう一度、HTTP/2が要求する暗号スイート「TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256 (楕円曲線は P256)」を眺めて下さい。128ビットの暗号強度を要求していることがわかります。

この表から、Diffie Hellman よりも楕円曲線暗号を使った Diffie Hellman の方が、短いビット数で済むことが分かるでしょう。これが、短命 Diffie Hellman ではなく、短命楕円 Diffie Hellman が必須となっている理由です。

なお、楕円曲線のよいパラメータには(P256のような)名前が付いており、TLSネゴシエーションのときに名前を指定するだけよいようになっています。一方、Diffie Hellman では、よいパラメータが定義されているものの、それが周知されていなかったり、TLSで使うような名前は定められていません。この現状を打開するためのドラフトも存在します。

TLS 1.3

TLS 1.3 では、再ネゴシエーション、圧縮、ストリーム暗号、そして CBCモードのブロック暗号が削られる予定です。このすっきりしたデータ構造を見て、うっとりしましょう。

      struct {
          ContentType type;
          ProtocolVersion version;
          uint16 length;
          opaque fragment[TLSPlaintext.length];
      } TLSPlaintext;

      struct {
          ContentType type;
          ProtocolVersion version;
          uint16 length;
          opaque nonce_explicit[SecurityParameters.record_iv_length];
          aead-ciphered struct {
             opaque content[TLSPlaintext.length];
          } fragment;
      } TLSCiphertext;

おまけ

SSL 2.0 の利用は推奨されていません。その理由は RFC6176を読んで下さい。また、SSL 3.0 の利用を推奨しなくするためのドラフトも存在します。

2014-12-04

HTTP/2 Frame test case の使い方

これは HTTP2 Advent Calendar 2014の4日目の記事です。

日本のHTTP/2 コミュニティでは、相互接続性を検証するためにHPACK test caseを作成し、好評を得ました。現在は、Frame test caseの作成に取り組んでいます。この記事では、Frame test caseの使い方について説明します。

正常系

現時点では、JSONフォーマットが確定していません。テストケースは、山本がとりあえず作ったものを個人のリポジトリに置いています。この記事がきっかけとなって、フォーマットの議論や他のテストケースの作成が進むと嬉しいです。

たとえば、正常なデータフレームは、こんな感じです。

{
    "error": null,
    "wire": "0000140008000000020648656C6C6F2C20776F726C6421486F77647921",
    "frame": {
        "length": 20,
        "frame_payload": {
            "data": "Hello, world!",
            "padding_length": 6,
            "padding": "Howdy!"
        },
        "flags": 8,
        "stream_identifier": 2,
        "type": 0
    },
    "draft": 14,
    "description": "normal data frame"
}

"error" が null なので、正常だと分かります。"wire"がネットワーク上に流れるフレームであり、16進数表記になっています。まず、"wire"データをパースして、"frame"と一致するか確かめましょう。もちろん、"frame" というJSONオブジェクトをあなたのコードで使われているデータ表現に変える必要がありますよ。

これは、正常なデータですので、逆も確かめます。すなわち、"frame"からフレームをビルドして、"wire" と一致しているか確かめます。

異常系

たとえば、異常なフレームはこんな感じです。

{
    "error": [
        6
    ],
    "wire": "0080000008000000020648656C6C6F2C20776F726C6421686F77647921",
    "frame": null,
    "draft": 14,
    "description": "data frame with frame size error"
}

これは "error" が null でないので、異常なフレームだと分かります。"error" には、可能性のあるエラーコードが(もれていなければ)すべて含まれています。"wire" 部分をパースし、返って来たエラーコードが "error" の中にあるか確かめましょう。

今後の課題

  • みんなで使ってみて JSON フォーマットを確定させましょう
  • みんなでテストケースを増やしましょう
  • それらをhpack-test-caseにマージしましょう

おまけ

なお、余談ですが、現在の仕様では "HTTP2.0" ではなく "HTTP/2" もしくは "HTTP2" が正しい名称です。

2014-06-25

Emacs 24.3/24.4 on Mac のフォント設定

Emacs で一番難しいのはフォントの設定です。特に Mac では地獄のように難しいです。とうわけで、Emacs 24.3 と来る Emacs 24.4 でうまくフォントを使うための設定を公開しておきます。

なお、Mac では素の Emacs を使ってはいけません。Emacs Mac port を使いましょう。パッチを当てるのは面倒なので、早く github なんかで公開されるといいですね。

ちなみに、素の Emacs を Dock から起動すると PATH を引き継がないので、はまります。Emacs Mac port なら PATH を引き継いでくれます。

フォントの設定

以下をお好みに合わせて変えて .emacs などに入れて下さい。

;; 以下はフレームの設定
(defvar my-frame-parameters
  '((height . 40)
    (width . 80)
    (top . 0)
    (left . 0)
    (foreground-color . "white")
    (background-color . "black")
    (cursor-color . "white")
    (mouse-color . "white")
    (tool-bar-lines . nil)))

(when (memq window-system '(x mac ns))
  (setq frame-title-format '(multiple-frames "%b" ("" invocation-name)))
  (setq default-frame-alist my-frame-parameters))

;; 以下が Mac 用のフォント設定
(when (memq window-system '(mac ns))
  (global-set-key [s-mouse-1] 'browse-url-at-mouse)
  (let* ((size 14)
	 (jpfont "Hiragino Maru Gothic ProN")
	 (asciifont "Monaco")
	 (h (* size 10)))
    (set-face-attribute 'default nil :family asciifont :height h)
    (set-fontset-font t 'katakana-jisx0201 jpfont)
    (set-fontset-font t 'japanese-jisx0208 jpfont)
    (set-fontset-font t 'japanese-jisx0212 jpfont)
    (set-fontset-font t 'japanese-jisx0213-1 jpfont)
    (set-fontset-font t 'japanese-jisx0213-2 jpfont)
    (set-fontset-font t '(#x0080 . #x024F) asciifont))
  (setq face-font-rescale-alist
	'(("^-apple-hiragino.*" . 1.2)
	  (".*-Hiragino Maru Gothic ProN-.*" . 1.2)
	  (".*osaka-bold.*" . 1.2)
	  (".*osaka-medium.*" . 1.2)
	  (".*courier-bold-.*-mac-roman" . 1.0)
	  (".*monaco cy-bold-.*-mac-cyrillic" . 0.9)
	  (".*monaco-bold-.*-mac-roman" . 0.9)
	  ("-cdac$" . 1.3)))
  ;; C-x 5 2 で新しいフレームを作ったときに同じフォントを使う
  (setq frame-inherited-parameters '(font tool-bar-lines)))

;; 以下の設定はお好みで
(setq resize-mini-windows nil)
(setq mouse-drag-copy-region t)

あわせて読みたい