Friday, December 26, 2014

[Ann] Initial release of H2O, and why HTTPD performance will matter in 2015

Happy Holidays!

Today I am delighted to announce the first release of H2O, version 0.9.0; this is a christmas gift from me.


H2O is an optimized HTTP server with support for HTTP/1.x and the upcoming HTTP/2; it can be used either as a standalone server or a library.

Built around PicoHTTPParser (a very efficient HTTP/1 parser), H2O outperforms Nginx by a considerable margin. It also excels in HTTP/2 performance.



Why do we need a new HTTP server? The answer is because its performance does matter in the coming years.

It is expected that the number of files being served by the HTTP server will dramatically increase as we transit from HTTP/1 to HTTP/2.

This is because current techniques used to decrease the number of asset files (e.g. CSS sprites and CSS concatenation) becomes a drag in page rendering speed in HTTP/2. Such techniques were beneficial in HTTP/1 since the protocol had difficulty in utilizing all the available bandwidth. But in HTTP/2 the issue is fixed, and the overhead of transmitting all the images / CSS styles used by the website at once while only some of them is needed to render a specific page, becomes a bad idea. Instead, switching back to sending small asset files for every required element consisting the webpage being request becomes an ideal approach.

Having an efficient HTTP/1 server is also a good thing, as we large-scale adopt the idea of Microservices; it increases the number of HTTP requests transmitted within the datacenter.

As shown in the benchmark charts, H2O is designed with these facts in mind, making it (as we believe) an ideal choice of HTTP server of the future.

With this first release, H2O is concentrates on serving static files / working as a reverse proxy at high performance.

Together with the contributors I will continue to optimize / add more features to the server, and hopefully reach a stable release (version 1.0.0) when HTTP/2 becomes standardized in the coming months.

Stay tuned.

PS. It is also great that the tools developed by H2O is causing other effects; not only have we raised the bar on HTTP/2 server performance (nghttp2 (a de-facto reference implementation of HTTP/2) has become much faster in recent months), the performance race of HTTP/1 parser has once again become (Performance improvement and benchmark by indutny · Pull Request #200 · joyent/http-parser, Improving PicoHTTPParser further with AVX2), @imasahiro is working on merging qrintf (a preprocessor that speeds up the sprinf(3) family by a magnitude developed as a subproduct of H2O) to Clang. Using H2O as a footstep, I am looking forward to bringing in new approaches for running / maintaining websites next year.

Monday, December 22, 2014

URL パーサにおける IPv6 対応

プログラマにとって IPv6 対応といえば、C言語のような低レベルな言語の話であって、ホスト名を文字列で扱うスクリプト言語には関係ないと考えがちです。ですが、実際には、文字列の取り扱いにおいても対応が必要になるところがあります。

その代表例が URL のパーサです。多くのエンジニアがイメージする URL の書式は「protocol://host:port/path#fragment」です。この書式を見れば、「:」と「/」を用いてトークンを分割するのが自然であり、RFC を参照せずに記述された URL パーサは、host の中に「:」が含まれないことを前提としていることがあります。あるいは、/[0-9A-Za-z_-\.]+/ のような正規表現を使って、ホスト名または IPv4 アドレスをチェックしている場合も多いのではないでしょうか。

ところが、IPv6 アドレスの文字列表現には「:」が含まれるため、IPv6 のアドレスを含む URL については、

http://[::FFFF:129.144.52.38]:80/index.html

のように、「[]」で囲むこと、と規定されています注1。つまり、「http://」のあとの最初の「:」をポート番号の始まりだと解釈する URL パーサは、IPv6 アドレスを正しく取り扱えないのです。

今後、IPv6 を利用する機会が増えるにともない、このような IPv6 アドレスを含んだ URL を取り扱えないパーサによるバグに直面する可能性も出てくるでしょう。

年末の大掃除がてら、自分が使っているURLパーサの挙動を確認・修正するのも良いかもしれませんね注2

注1: 参照 RFC 3986
注2: なにを言いたかったというと、H2Oの URL パーサで IPv6 対応するのを忘れていたってことですね!!!!! というわけでこの記事は H2O Advent Calendar 2014 の一部です。てへぺろ

Friday, December 19, 2014

Memory Management in H2O

This blogpost (as part of the H2O Advent Calendar 2014) provides a high-level overview of the memory management functions in H2O that can be categorized into four groups.

h2o_mem_alloc, h2o_mem_realloc

They are wrappers of malloc(3) / realloc(3), that calls abort(3) if memory allocation fails. The returned chunks should be freed by calling free(3).

h2o_mem_init_pool, h2o_mem_clear_pool, h2o_mem_alloc_pool

The functions create, clear, and allocate from a memory pool. The term memory pool has several meanings, but in case of H2O the term has been borrowed from Apache; it refers to a memory allocator that frees all associated chunks at once when the destructor (h2o_mem_clear_pool) is being called.

The primary use-case of the functions is to allocate memory that relates to a HTTP request. The request object h2o_req_t has a memory pool associated to it; small chunks of memory that need to be allocated while handling a request should be obtained by calling h2o_mem_alloc_pool instead of h2o_mem_alloc, since the former is generally faster than the latter.

h2o_mem_alloc_shared, h2o_mem_link_shared, h2o_mem_addref_shared, h2o_mem_release_shared

They are the functions to handle ref-counted chunks of memory. Eeach shared chunk has its own dispose callback that gets called when the reference counter reaches zero. A chunk can be optionally associated to a memory pool, so that the reference counter gets decremented when the pool gets flushed.

The functions are used for handling things like headers transferred via HTTP/2, or to for associating a resource that needs a custom dispose callback to a HTTP request through the use of the memory pool.

h2o_buffer_init, h2o_buffer_dispose, h2o_buffer_reserve, h2o_buffer_consume, h2o_buffer_link_to_pool

The functions provide access to buffer, that can hold any length of octets. They internally use malloc(3) / realloc(3) for handling short buffers, and switch to using temporary-file-backed mmap(2) when the length of the buffer reaches a predefined threshold (default: 32MB). A buffer can also be associated to memory pool by calling the h2o_buffer_link_to_pool function.

The primary use-case of the buffer is to store incoming HTTP requests and POST contents (as it can be used to hold huge chunks on 64-bit systems since it switches to temporary-file-backed memory as described).

h2o_vector_reserve

The function reserves given number of slots for H2O_VECTOR which is a variable length array of an arbitrary type of data. Either h2o_mem_realloc or the memory pool can be used as the underlying memory allocator (in the former case, the allocated memory should be manually freed by the caller). The structure is initialized by zero-filling it.

The vector is used everywhere, from storing a list of HTTP headers to a list of configuration directives.

For details, please refer to their doc-comment and the definitions in include/h2o/memory.h and lib/memory.c.

Tuesday, December 16, 2014

GitHub で submodule ではなく subtree を使うべき理由

GitHub には、タグを打つとソースパッケージを自動的にリリースするという機能があります。スクリプト言語においては、それぞれの言語について一般的なパッケージ管理システム注1があるため、この機能を使うことが少ないかと思いますが、デファクトのパッケージ管理システムが存在しないC等の言語で書かれたプログラムや、単独で動作する管理用のスクリプトを GitHub で開発・配布する際には、本機能はとても便利なものです。

しかし、この機能は git-archive コマンドのラッパーとして実装されているため、サブモジュールのファイルが含まれないという問題を抱えています。この点は GitHub の人たちも認識しているものの、今のところ GitHub で独自に対応するということは考えていないようです注2

私がこの問題を 知ることになったのは、picojson の issue で指摘を受けたからです。picojson については問題が「テストが動かない」という程度なので後回しにしても良かったのですが、H2O についても同様の問題が発生することが目に見えていました。

そこでどうするか、irc で相談、実験した結果、サブモジュールのかわりに サブツリーを使えば、参照先のファイルについても git-archive の結果に含めることが可能であることがわかり、picojson についてはサブツリーへの移行を完了しました。

ツールの仕様に引っ張られてやり方を変えるという、ある意味しょうもない話なのですが、H2O についても今後リリースまでにサブツリーへの切り替えを行おうと考えています。

※本記事 H2O Advent Calendar 2014 の一部です。

注1: たとえば Perl については CPAN、JavaScript については NPM が存在する
注2: 参照: » Github zip doesn’t include Submodules Academic Technology Group Developers Blog のコメント

Monday, December 15, 2014

PicoHTTPParser now has a chunked-encoding decoder

Today I have added phr_decode_chunked - a function for decoding chunked-encoded input - to picohttpparser.

As suggested in the doc-comment of the function (shown below), the function is designed to decode the data in-place. In other words, it is not copy-less.
/* the function rewrites the buffer given as (buf, bufsz) removing the chunked-
 * encoding headers. When the function returns without an error, bufsz is
 * updated to the length of the decoded data available. Applications should
 * repeatedly call the function while it returns -2 (incomplete) every time
 * supplying newly arrived data. If the end of the chunked-encoded data is
 * found, the function returns a non-negative number indicating the number of
 * octets left undecoded at the tail of the supplied buffer. Returns -1 on
 * error.
 */
ssize_t phr_decode_chunked(struct phr_chunked_decoder *decoder, char *buf,
                           size_t *bufsz);
It is intentionally designed as such.

Consider a input like the following. The example is more than 2MB long even though it contains only 2 bytes of data. The input is conformant to the HTTP/1.1 specification since it does not define the maximum length of the chunked extensions, requires every conforming implementation to ignore unknown extensions.
1 very-very-veery long extension that lasts ...(snip) 1MB
a
1 very-very-veery long extension that lasts ...(snip) 1MB
a
To handle such input without getting the memory exhausted, a decoder should either a) only preserve the decoded data (requires a copy), or b) limit the size of the chunked-encoded data.

B might have been easier to implement, but such a feature might be difficult to administer. So I decided to take the route a, and for simplicity implemented the decoder to always adjust the position of the data in-place.

Always calling memmove for adjusting the position might induce some overhead, but I assume it to be negligible for two reasons: both the source and destination would exist in the CPU cache / the overhead of unaligned memory access is small on recent Intel CPU.

For ease-of-use, I have added examples to the README.

Saturday, December 13, 2014

C言語で可変長引数をとる関数を、型安全に書く方法

C言語の可変長引数は、型安全でない(まちがった型の引数を渡してもコンパイルエラーにならない)とされています。これは言語仕様の理解としては正しいのですが、特定の型の引数を任意の個数とる関数に限っては、マクロを使うことで型安全性を確保することができます

任意の個数のdoubleを引数にとり、その和を返す関数「sumf」を例にあげて説明します。

C言語の可変長引数機構を使ってsumfを定義すると、以下のようになります。
#include <math.h>
#include <stdarg.h>
#include <stdio.h>

static double sumf(double nfirst, ...)
{
  double r = 0, n;
  va_list args;

  va_start(args, nfirst);
  for (n = nfirst; ! isnan(n); n = va_arg(args, double))
    r += n;
  va_end(args);

  return r;
}

int main(int argc, char **argv)
{
  printf("%f\n", sumf(NAN)); /* => 0 */
  printf("%f\n", sumf(1., NAN)); /* => 1 */
  printf("%f\n", sumf(1., 2.5, 3., NAN)); /* => 6.5 */
  return 0;
}
が、この定義には「NANを終端に使っているがために、NANを引数として渡すことができない(=終端を表す値が必要になる)」「型安全でない」という2点の問題があります。後者については、たとえば、sumf(1, 1, NAN)のように、うっかりdouble型以外の引数を渡してしまってもコンパイルエラーにならず、ただ結果がおかしくなったりコアダンプしたりすることになります注1

では、どのようにsumfを定義すれば良いのでしょう。答えを書いてしまうと、こんな感じです。
#include <stdio.h>

#define sumf(...)                                       \
  _sumf(                                                \
    (double[]){ __VA_ARGS__ },                          \
    sizeof((double[]){ __VA_ARGS__ }) / sizeof(double)  \
  )

static double _sumf(double *list, size_t count)
{
  double r = 0;
  size_t i;

  for (i = 0; i != count; ++i)
    r += list[i];

  return r;
}

int main(int argc, char **argv)
{
  printf("%f\n", sumf()); /* => 0 */注2
  printf("%f\n", sumf(1.)); /* => 1 */
  printf("%f\n", sumf(1., 2.5, 3)); /* => 6.5 */
  return 0;
}
この定義では、可変長の引数群をマクロを用いてインラインで配列として初期化し、かつ、その要素数をsizeof演算子を用いて計算しています。そのため、C言語標準の可変長引数機構を使った場合の問題はいずれも発生しません。要素数が_sumf関数に引数countとして渡されるため、終端を表す特殊な値は必要になりませんし、また、実引数はdouble型の配列として呼出側で構築されるため、誤った型の引数を渡してしまうとコンパイルエラーになります。あるいは、たとえばint型の値を渡してしまった場合は、コンパイラによってdouble型に昇格することになるからです。

私たちが開発しているHTTPサーバ「H2O」では、この手法を用いて、型安全な文字列結合関数h2o_concatを定義、使用しています。

以上、H2Oで使っているC言語の小ネタ紹介でした。

※この記事はH2O Advent Calendar 2014の一部です。

注1: 手元の環境だと、sumf(1, 1, NAN)の結果は1となります
注2: 可変長マクロに対して0個の引数を渡すのはC99の規格には違反しますが、GCCやClangは問題なく処理します

Monday, December 8, 2014

64bit時代のバッファ処理

プログラミングの「常識」は時代とともに変化します。そのひとつが、サーバプログラムにおけるバッファ処理です。

1990年代後半から2010年頃までは、メモリ空間の大きさ(32bitすなわち4GB注1)を超える大きさのファイルを扱う時代でした。このため、httpdなどのサーバプログラムにおいても、入出力データをいったんテンポラリファイルとしてバッファリングする必要がありました。ですが、ファイルI/Oはメモリアクセスと比べると低速です。このため、小さなサイズのデータについてはメモリアクセスする一方で、大きなサイズのデータについてはファイルI/Oを用いる、という煩雑なコードを書く必要がありました。

しかし、2014年も暮れとなる今 、サーバサイドにおいては64bit環境のみを考えれば良い時代に入りつつあります。

もちろん、64bit環境といったところで、64bit空間の全てをユーザプロセスが使えるわけではありません。現行のx86-64 CPUがサポートする論理アドレス空間は48bit(256TB相当)であり、多くのOSではその上位アドレス半分がカーネル空間に割り当てられ、残った128TBがユーザプロセスで使用可能な空間となっています注2

128TBものメモリ空間があれば、全てのテンポラリデータを「メモリ空間にマッピングして」使用することができます。

実際に、H2Oのバッファ処理では、64MBを超えるものについてはテンポラリファイルをftruncate/mmapすることで領域を確保注3し、これに対してメモリアクセスを行うようになっています。詳しくはh2o_buffer_reserve関数の定義をご覧ください。

バッファを利用する側のコードにおいては、サイズの大小に関係なく単なるメモリブロックとしてアクセスできるため、コードが単純かつ高速になるのです。

※本記事はH2O Advent Calendar 2014の一部です。

注1: 多くのOSにおいては、カーネルとメモリ空間を分け合う必要があるため、実際にユーザプロセスで使用できるメモリ空間は1GB〜3GB程度でした
注2: 参照: x86-64 - Wikipedia, the free encyclopedia - Operating system compatibility and characteristics
注3: malloc(3)で確保可能なメモリの総量である物理メモリ+スワップ領域の和は必ずしも十分に大きくないため、テンポラリファイルを生成してftruncateすることでディスク上に必要な領域を確保しています

Q. 条件分岐や算術演算を使わずに、max(a,b) を計算するプログラムを書けますか?

if文(条件分岐)を使わず、max(a, b) を計算 別解 | 津田の開発な日記」に関連した話です。リンク先のブログ記事では、条件分岐を使わずにmax(a,b)を実装する方法が議論されています。

では、更に条件を厳しくして、「条件分岐も算術演算も使わずに」max(a,b)を実装することはできるでしょうか?























なぜ、「もちろん」なのか。CPUは、ANDやOR、NOTのようなデジタルな論理回路から構成されています。であれば、当然、ビット演算(ビットシフトと&, |, ^)を使って、max(a, b)を実装することも可能なわけです。こんな感じ。

#include <stdio.h>

#define BIT(n, pos) (((n) >> (pos)) & 1)

static int mymax(int a, int b)
{
  int islt = BIT(a, 31) & (BIT(b, 31) ^ 1);
  int iseq = BIT(a, 31) ^ BIT(b, 31) ^ 1;

#define CHECK_BIT(pos) do { \
  islt |= iseq & (BIT(a, pos) ^ 1) & BIT(b, pos); \
  iseq &= BIT(a, pos) ^ BIT(b, pos) ^ 1; \
} while (0)

  CHECK_BIT(30); CHECK_BIT(29); CHECK_BIT(28);
  CHECK_BIT(27); CHECK_BIT(26); CHECK_BIT(25); CHECK_BIT(24);
  CHECK_BIT(23); CHECK_BIT(22); CHECK_BIT(21); CHECK_BIT(20);
  CHECK_BIT(19); CHECK_BIT(18); CHECK_BIT(17); CHECK_BIT(16);
  CHECK_BIT(15); CHECK_BIT(14); CHECK_BIT(13); CHECK_BIT(12);
  CHECK_BIT(11); CHECK_BIT(10); CHECK_BIT(9); CHECK_BIT(8);
  CHECK_BIT(7); CHECK_BIT(6); CHECK_BIT(5); CHECK_BIT(4);
  CHECK_BIT(3); CHECK_BIT(2); CHECK_BIT(1); CHECK_BIT(0);

#undef CHECK_BIT

  /* extend flag to 32-bit mask */
  islt <<= 31;
  islt >>= 31;

  return (a & (islt ^ 0xffffffff)) | (b & islt);
}

int main(int argc, char **argv)
{
  int a, b;

  if (argc != 3) {
    fprintf(stderr, "Usage: %s a b\n", argv[0]);
    return 1;
  }
  if (sscanf(argv[1], "%d", &a) != 1) {
    fprintf(stderr, "%s is not a number\n", argv[1]);
    return 1;
  }
  if (sscanf(argv[2], "%d", &b) != 1) {
    fprintf(stderr, "%s is not a number\n", argv[2]);
    return 0;
  }

  printf("max(%d,%d) is %d\n", a, b, mymax(a, b));

  return 0;
}


なぜHTTPSはHTTPより速いのか

先週、httpvshttps.com というウェブサイトが公開されました。このウェブサイトでは、HTTP と HTTPS を用いてアクセスした場合のウェブページのダウンロード完了までにかかる時間の比較ができるのですが、多くの環境で HTTPS の方が HTTP よりも高速なことに驚きの声が上がっていました。

HTTP が TCP 上で平文を送受信するのに対し、HTTPS は TCP 上で TLS (SSL) という暗号化技術を用いて通信を行います。ならば、TLS のオーバーヘッドのぶん HTTPS のほうが遅いはずだ、という予測に反する結果になったのですから、驚くのも無理はありません。

実は、この結果にはからくりがありました。

Google Chrome、Mozilla Firefox、最近のSafari注1は、Google が開発した通信プロトコル「SPDY」に対応しており、HTTPS の通信においてはHTTP/1.1 ではなく SPDY を TLS 上の通信プロトコルとして利用します。

HTTP/1.1 は20年近く前に標準化された技術であり、今日では様々な限界が指摘されるようになってきています。そのうち最大の問題が、ウェブブラウザ上において、現在ダウンロード中のファイルのダウンロードが完了するまで次のファイルのダウンロード要求を送信できないという問題です。クライアントとサーバ間を通信が往復するには、数十ミリ秒から数百ミリ秒という時間がかかります(この時間は、ラウンドトリップタイム (RTT) と呼ばれます)。

ウェブブラウザが、第一のファイルのダウンロードを完了した直後に第二のファイルのダウンロード要求をサーバに送信したとしても、その中身が届き始めるのは、このラウンドトリップタイムが経過した後になります。その間、サーバからクライアント方向の通信回路は無駄に遊んでいることになります。

httpvshttps.com のような、小さな画像ファイルを多数ダウンロードするウェブページでは(これは多くのウェブサイトに見られる一般的な特徴です)、この無駄が占める割合が大きくなるのです(ウェブブラウザの動作としては、リクエストを送信後、RTTが経過するまでじっと待ち、その後一瞬でファイル受信が完了、直後に次のリクエストを送信し、RTT が経過するまでじっと待つ…を繰り返す形になります)。

一方、SPDY はこれら HTTP/1.1 が抱える問題を改善しようとする Google の試みとして開発が進んできたプロトコルであり、多数のファイルを並行してダウンロードすることが可能となっています。HTTP/1.1 のように、ファイルの到着を待つだけの時間は発生しません。

この違いが、暗号化のオーバーヘッドがあるにも関わらず、HTTPS のウェブページの方が HTTP より速くダウンロードが完了することの原因なのです。


■この傾向は今後も続くのか

SPDY は Google が開発した実証実験的な性格の強いプロトコルでした。そこから得られた成果をもとに、現在、HTTP/2 という次世代の HTTP プロトコルの標準化が進められており、はやければあと数週間で標準化される見込みとなっています。

HTTP/2 プロトコルの標準化案自体は HTTP でのアクセスにおいても HTTPS でのアクセスにおいても利用可能なものとなっています。ですが、多くのウェブブラウザはHTTPS でのアクセスにおいてのみ、HTTP/2 を有効化する公算が高くなっています注2

このため、HTTPS の方が HTTP よりも高速である、という状況は今後とも続くと考えられます。

■HTTPS のサーバ負荷はどうなのか

HTTPS に対する事業者の不安としては、ダウンロード速度に加えてもう一点、サーバ負荷の問題をあげることができます。暗号化を導入することで、サーバの負荷が増大するのではないか。

筆者らが開発している、高速なHTTPサーバであるH2Oでは…(続く)

本記事は HTTP2 Advent Calendar 2014 および H2O Advent Calendar 2014 の一部です。筆者体調不良により遅延&書きかけの状態ですみませんすみません。

注1: YosemiteまたはiOS 8上で動作するものに限る
注2: 参照: (HTTP/2標準化ワークグループ座長のブログ記事, https://wiki.mozilla.org/Networking/http2

Monday, December 1, 2014

Improving Parser Performance using SSE Instructions (in case of PicoHTTPParser)

PicoHTTPParser is a tiny but very fast HTTP parser library known for its use by many Perl applications. In the slides I used last month, I suggested it could be even faster if SIMD instructions were used. Now the feature is available thanks to @herumi.

The library now uses the PCMPESTRI instruction which is part of SSE 4.2, running 68% to 90% faster.

Benchmarkclang -O3clang -O3 -msse4.2Improvement
bench.c2,181,0254,140,787+90%
fukamachi.c3,213,4405,400,064+68%

PCMPxSTRx is a SIMD instruction that can be used for parsing text. In _SIDD_CMP_RANGES mode, it checks at most 16 bytes at once, if each byte is within given set of ranges. Herumi and I have created a wrapper function for the instruction named findchar_fast that iterates though every 16 bytes of a given buffer to find the first occurrence of a byte within a set of given ranges.

And the function is merged neatly into the parser; the code below at first uses the SIMD function to look for a control character (the match condition is defined as ranges1), then falls back to the non-SIMD code to handling up to 15 remaining characters (that cannot be processed by the SIMD function due to out-of-bounds access).
#ifdef __SSE4_2__
  static const char ranges1[] =
    "\0\010"
    /* allow HT */
    "\012\037"
    /* allow SP and up to but not including DEL */
    "\177\177"
    /* allow chars w. MSB set */
    ;
  int found;
  buf = findchar_fast(buf, buf_end,
                      ranges1, sizeof(ranges1) - 1,
                      &found);
  if (found)
    goto FOUND_CTL;
#endif
  /* code that handles the input byte-by-byte */
To summarize, PCMPxSTRx is an excellent instruction for performance that can be cleanly integrated into existing parsers (tokenizers). Hopefully we will see performance improvements in various parsers in the future through the use of the instruction.

This blog post has been written as part of the H2O Advent Calendar.

Wednesday, November 5, 2014

[memo] Installing nghttp2 onto OSX

Following the steps below should install nghttp2 with all of its useful apps for testing into /usr/local/http2-15 of your OS X machine.

-- openssl
% wget --no-check-certificate https://www.openssl.org/source/openssl-1.0.2-beta3.tar.gz
% tar xzf openssl-1.0.2-beta3.tar.gz
% cd openssl-1.0.2-beta3
% KERNEL_BITS=64 ./config shared enable-ec_nistp_64_gcc_128 --prefix=/usr/local/http2-15
% make
% make install

-- libevent
% wget https://github.com/downloads/libevent/libevent/libevent-2.0.21-stable.tar.gz
% CFLAGS=-I/usr/local/http2-15/include CXXFLAGS=-I/usr/local/http2-15/include LDFLAGS=-L/usr/local/http2-15/lib ./configure --prefix=/usr/local/http2-15
% make
% make install

-- zlib-1.2.8
% wget http://zlib.net/zlib-1.2.8.tar.gz
% tar xzf zlib-1.2.8.tar.gz
% cd zlib-1.2.8
% ./configure --prefix=/usr/local/http2-15
% make
% make install

--  spdylay
% git clone https://github.com/tatsuhiro-t/spdylay.git
% cd spdylay
% (cd m4 && wget http://keithr.org/eric/src/whoisserver-nightly/m4/am_path_xml2.m4)
% autoreconf -i
% PKG_CONFIG_PATH=/usr/local/http2-15/lib/pkgconfig ./configure --prefix=/usr/local/http-15
% make
% make install

-- nghttp2
% git clone https://github.com/tatsuhiro-t/nghttp2.git
% cd nghttp2
% (cd m4 && wget http://keithr.org/eric/src/whoisserver-nightly/m4/am_path_xml2.m4)
% autoreconf -i
% PKG_CONFIG_PATH=/usr/local/http2-15/lib/pkgconfig ./configure --prefix=/usr/local/http2-15 --enable-app --disable-threads
% make
% make install

note: I have gathered this from my command history. Please forgive me if any of them are wrong.
EDIT: added libevent as pointed out by @tatsuhiro-t.

Tuesday, November 4, 2014

The internals H2O (or how to write a fast server)

Yesterday, I had the opportunity to speak at the HTTP2Conference held in Tokyo.

Until now, I have rather been silent about H2O since I think it is still premature for wild use. But you do not need to worry about such thing in a technology conference, so I happily talked about the motives behind H2O, and its implementation.

IMO the talk should be interesting not only to people working with HTTP server implementations but also to those interested in programming in general, since it covers the common performance pitfalls (or misconceptions as I see) in many server implementations.

Below are the slides and the recorded video of my presentation.

Enjoy!

PS. Please forgive me for the provocative attitude in the questions raised in the last part of the slides. They were intentionally written as such in order to spark discussion at the hall.



my talk starts a 3h15m (in Japanese)

Related links:

Friday, October 10, 2014

[メモ] root権限でrsyncする方法

サーバの移転作業時など、rootしかアクセスできない設定ファイルやアクセス権を保ったままrsyncしたいことってありませんか?

そういった際には、sudo の -A オプションと rsync の --rsync-path オプションを使うと良いようです。

まず、リモートサーバに、パスワードを標準出力に出力するスクリプトファイルを配置します(ファイルのパーミッションを厳しくするのを忘れずに)。
% cat > bin/askpass
#! /bin/sh
echo "{{my_password}}"
% chmod 700 bin/askpass
% 
そして、rsync を実行する際には --rsync-path オプションを使い、リモートサーバの rsync を sudo -A 経由で起動するようにすれば良いのです。
% sudo rsync -avz -e ssh \
    --rsync-path='SUDO_ASKPASS=/home/remote-user/bin/askpass sudo -A rsync' \
    remote-user@remote-host:remote-dir local-dir

これは簡単!

sudo -Aオプションはパスワードを記述したファイルを設置する必要があるという点でNOPASSWD同様セキュリティの懸念はありますが、使いどころを誤らなければ便利だなと思いました。

Tuesday, October 7, 2014

Making the HTTP server run 20% faster by using qrintf-gcc; a sprintf-optimizing preprocessor / compiler

tl;dr

This is an initial release announcement of qrintf, a preprocessor (and qrintf-gcc is the compiler frontend) that optimizes calls to sprintf and snprintf. C programs calling the functions may run faster by using the preprocessor / compiler in place of the standard compiler toolchain.

github.com/kazuho/qrintf

Background

sprintf (snprintf) is a great function for converting data to strings. The downside is that it is slow. Recently the functions have been one of the bottlenecks of H2O, which is a high performance HTTP server / library with support for HTTP/1.x and HTTP/2.

The function is slow not because stringification in general is a slow operation. It is slow mainly due to its design.

The function takes a format string (e.g. "my name is %s") and parse it at runtime, every time the function gets called. The design must have been a good choice when the C programming language was designed. Until the 1990s, every byte of memory was a precious resource. Using a memory-conscious approach (e.g. a state-machine for formatting strings) was a logical choice. But nowadays, the cost of memory is hundreds-of-thousand times cheaper than it used to be. On the other hand, the relative cost of running a state machine for building formatted strings has become large since it causes lots of branch mis-predictions that stall the CPU pipeline.

How it works

The understanding has led me to write qrintf, which works as a wrapper against the C preprocessor. It precompiles invocations of sprintf (and snprintf) with a constant format string (which is mostly the case) into optimized forms.

The example below illustrates the conversion performed by the qrintf preprocessor. As can be seen, the call to sprintf is precomplied into a series of function calls specialized for each portion of the format (and the C compiler may inline-expand the specialized calls). In the case of the example, the optimized code runs more than 10 times faster than the original form.
// source code
snprintf(
    buf,
    sizeof(buf),
    "%u.%u.%u.%u",
    sizeof(buf),
    (addr >> 24) & 0xff,
    (addr >> 16) & 0xff,
    (addr >> 8) & 0xff,
    addr & 0xff);

// after preprocessed by qrintf
_qrintf_chk_finalize(
    _qrintf_chk_u(
        _qrintf_chk_c(
            _qrintf_chk_u(
                _qrintf_chk_c(
                    _qrintf_chk_u(
                        _qrintf_chk_c(
                            _qrintf_chk_u(
                                _qrintf_chk_init(buf, sizeof(buf)),
                                (addr >> 24) & 0xff),
                            '.'),
                        (addr >> 16) & 0xff),
                    '.'),
                (addr >> 8) & 0xff),
            '.'),
        addr & 0xff));
$ gcc -Wall -O2 examples/ipv4addr.c && time ./a.out 1234567890
result: 73.150.2.210

real 0m2.475s
user 0m2.470s
sys 0m0.002s
$ qrintf-gcc -Wall -O2 examples/ipv4addr.c && time ./a.out 1234567890
result: 73.150.2.210

real 0m0.215s
user 0m0.211s
sys 0m0.002s

Performance impact on H2O

H2O uses sprintf in three parts: building the HTTP status line, building ETag, and building the access log.

By using qrintf-gcc in place of gcc, the performance of H2O jumps up by 20% in a benchmark that sends tiny files and with access logging enabled (from 82,900 reqs/sec. to 99,200 reqs/sec.).

The fact not only makes my happy (as the developer of qrintf and H2O) but also shows that optimizing sprintf at compile-time do have benefit for real world programs.

So if you are interested in using qrintf or H2O, please give it a try. Thank you for reading.

Thursday, October 2, 2014

sprintf を最大10倍以上高速化するプリプロセッサ「qrintf」を作った

最近H2OというHTTPサーバを書いているのですが、プロファイルを取ってみるとsprintfが結構な時間を食っていて不満に感じていました。実際、sprintfは数値や文字列をフォーマットするのに十徳ナイフ的に便利なので、HTTPサーバに限らず良く使われる(そしてCPU時間を消費しがちな)関数です。

では、sprintfを最適化すれば、様々なプログラムが より高速に動作するようになるのではないでしょうか。ということで作ったのが、qrintfです。

qrintfは、Cプリプロセッサのラッパーとしてソースコードに含まれるsprintfの呼出フォーマットを解析し、フォーマットにあわせたコードに書き換えることで、sprintfを高速化します。

たとえば、以下のようなIPv4アドレスを文字列化するコード片を
sprintf(
    buf,
    "%d.%d.%d.%d",
    (addr >> 24) & 0xff,
    (addr >> 16) & 0xff,
    (addr >> 8) & 0xff,
    addr & 0xff);
以下のようにコンパイル時に自動的に書き換え、実行時にフォーマット文字列の解析する負荷を省くことで大幅な高速化を実現しています。
((int)(_qrintf_d(
    _qrintf_c(
        _qrintf_d(
            _qrintf_c(
                _qrintf_d(
                    _qrintf_c(
                        _qrintf_d(
                            _qrintf_init(buf),
                            (addr >> 24) & 0xff),
                        '.'),
                    (addr >> 16) & 0xff),
                '.'),
            (addr >> 8) & 0xff),
        '.'),
    addr & 0xff)
).off);

たとえば上記のコードの場合、以下のように、qrintfを用いることで10倍以上文字列化処理が高速化することを確認しています。
$ gcc -O2 examples/ipv4addr.c
$ time ./a.out 1234567890
result: 73.150.2.210

real    0m2.602s
user    0m2.598s
sys 0m0.003s
$ ./qrintf-gcc -O2 examples/ipv4addr.c
$ time ./a.out 1234567890
result: 73.150.2.210

real    0m0.196s
user    0m0.192s
sys 0m0.003s

sprintfを呼んでいるコードを書き換えずに高速化できて、ハッピーですね!

Monday, September 8, 2014

The reasons I stopped using libuv for H2O

Libuv is a great cross-platform library that abstracts various types of I/O by using callbacks.

So when I started writing H2O - a high-performance HTTP server / library implementation with support for HTTP1, HTTP2 and websocket, using libuv seemed like a good idea. But recently, I have stopped using it for sereval reasons. This blog post explains them.

■No Support for TLS

Although libuv provides an unified interface for various types of streams, it does not provide access to a TLS stream though the interface, nor does provide a way for application developers to implement their own types of streams.

The fact has been a disappointment to me. Initially I had created a tiny library called uvwslay that binds libuv streams to wslay - a websocket protocol implementation. But since libuv does not provide support for TLS, it was impossible to support SSL within the tiny library.

To support wss protocol (i.e. websocket over TLS) I needed to reimplement the websocket binding, to stop using libuv as its stream abstraction layer and switch to an abstraction layer defined atop of libuv that abstracts the differences between libuv streams and the I/O API provided by the SSL library being used (in my case it is OpenSSL).

It would be great if libuv could provide direct support for TLS in future (or provide a way to implement their own type of libuv streams), so that code directly calling the libuv API can support various types of streams.

■Memory Usage is not Optimal

Libuv provides a callback-based API for writes and I love the idea. It simplifies the complicatedness of implementing non-blocking I/O operations. However the problem of libuv is that it does not call the completion callback right after write succeeds. Instead, it is only until all I/Os are performed that the callbacks are called. This means that if you have 1,000 connections sending 64KB of data, your code first allocates 64KB of memory 1000 times (64MB in total) and then call free for all of those memory chunks, even when the network operation does not block. IMO, libuv should better call the completion callback immediately after the application returns the control back to the library after calling uv_write, so that the memory allocation pattern could be a repetition of malloc-and-then-free for 1000 times.

■No Support for Delayed Tasks

Libuv does not provide an interface to schedule actions to be run just before the I/O polling method is being called.

Such interface is necessary if you need to aggregate I/O operations and send the results to a single client. In case of HTTP2, a certain number of HTTP requests need to be multiplexed over a single TCP (or TLS) connection.

With lack of support for delayed tasks, you would need to use uv_timer with 0 second timeout to implement delayed tasks.

This works fine if the intention of the application developer is to aggregate read operations, but does not if the intension was to aggregate the result of write operations, since in libuv the write completion callbacks are called after the timers are called.

■Synchronous File I/O is Slow

Synchronous file I/O seems to be slow when compared to directly calling the POSIX API directly.

■Network I/O has Some Overhead

After I found out the issues mentioned above, I started to wonder how much overhead libuv imposes for network I/O.

So I stripped the parts that depended on libuv off from the stream abstraction layer of H2O (that hides the difference between TCP and TLS as described above) and replaced it with direct calls to POSIX APIs and various polling methods (i.e. select, epoll, queue).

The chart below shows the benchmark results taken on my development environment running Ubuntu 14.04 on VMware. H2O become 14% to 29% faster by not depending on libuv.


■The Decision

Considering these facts altogether, I have decided to stop using libuv in H2O, and use the direct binding that I have written and used for the benchmark, at least until the performance penalty vanishes and the TLS support gets integrated.

OTOH I will continue to use libuv for other projects I have as well as recommending it to others, since I still think that it does an excellent job in hiding the messy details of platform-specific asynchronous APIs with adequate performance.

PS. Please do not blame me for not trying to feedback the issues as pull requests to libuv. I might do so in the future, but such task is too heavy for me right now. I am writing this post in the hope that it would help people (including myself) understand more about libuv, and as an answer to @saghul.

Tuesday, July 15, 2014

自社サーバと交信するスマホアプリにおけるサーバ証明書の発行手法について(SSL Pinningと独自CA再考)

■背景




■他社CAは信頼できるのか



■独自CAに問題はあるのか




■自社CAと他社CAのリスク評価




■SSL Pinningの是非




■2種類のSSL Pinning



■では、どうすれば良いか





■補足:優良なCAから証明書を買うだけではダメな理由

Tuesday, July 1, 2014

The JSON SQL Injection Vulnerability

tl;dr

Many SQL query builders written in Perl do not provide mitigation against JSON SQL injection vulnerability.

Developers should not forget to either type-check the input values taken from JSON (or any other hierarchical data structure) before passing them to the query builders, or should better consider migrating to query builders that provide API immune to such vulnerability.

Note: 問題の発見者による日本語での説明はこちらです.

Background

Traditionally, web applications have been designed to take HTML FORMs as their input. But today, more and more web applications are starting to receive their input using JSON or other kind of hierarchically-structured data containers thanks to the popularization of XMLHttpRequest and smartphone apps.

Designed in the old days, a number of Perl modules including SQL::Maker have been using unblessed references to define SQL expressions. The following example illustrate how the operators are being specified within the users' code. The first query being generated consists of an equality match. The second query is generated through the use of a hashref to specify the operator used for comparison.

use SQL::Maker;
my $maker = SQL::Maker->new(…);

# generates: SELECT * FROM `user` WHERE `name`=?
$maker->select('user', ['*'], {name => $query->param('name')}); 

# generates: SELECT * FROM `fruit` WHERE `price`<=?
$maker->select('fruit', ['*'], {price => {'<=', $query->param('max_price')}});

This approach did not receive any security concern at the time it was invented, when the only source of input were HTML FORMs, since it is represented as a set of key-value pairs where all values are scalars. In other words, it is impossible to inject SQL expressions via HTML FORMs due to the fact that there is a guarantee by the query parser that the right hand expression of foo (i.e. $query->param('foo')) is not a hashref.


JSON SQL Injection

But the story has changed with JSON. JSON objects are represented as hashrefs in Perl, and thus a similar code receiving JSON is vulnerable against SQL operator injection.

Consider the code below.

use SQL::Maker;
my $maker = SQL::Maker->new(…);

# find an user with given name
$maker->select('user', ['*'], {name => $json->{'name'}}); 

The intention of the developer is to execute an SQL query that fetches the user information by using an equality match. If the input is {"name": "John Doe"} the condition of the generated query would be name='John Doe', and a row related to the specified person would be returned.

But what happens if the name field of the JSON was an object? If the supplied input is {"name": {"!=", ""}}, then the query condition becomes name!='' and the database will return all rows with non-empty names. Technically speaking, SQL::Maker accepts any string supplied at the key part as the operator to be used (i.e. there is no whitelisting); so the attack is not limited to changing the operator. (EDIT: Jun 3 2014)

Similar problem exists with the handling of JSON arrays; if the name field of the JSON is an array, then the IN operator would be used instead of the intended = operator.

It should be said that within the code snippet exists an operator injection vulnerability, which is referred hereafter as JSON SQL injection. The possibility of an attacker changing the operator may not seem like an issue of high risk, but there are scenarios in which an unexpected result-set of queries lead to unintended information disclosures or other hazardous behaviors of the application.

To prevent such attack, application developers should either assert that the type of the values are not references (representing arrays/hashes in JSON), or forcibly convert the values to scalars as shown in the snippet below.

use SQL::Maker;
my $maker = SQL::Maker->new(…);

# find an user with given argument that is forcibly converted to string
$maker->select('user', ['*'], {name => $json->{'name'} . ''}); 


Programmers Deserve a Better API

As explained, the programming interface provided by the SQL builders including SQL::Maker is per spec. as such, and thus it is the responsibility of the users to assert correctness of the types of the data being supplied.

But it should also be said that the programming interface is now inadequate in the sense that it is prone to the vulnerability. It would be better if we could use a better, safer way to build SQL queries.

To serve such purpose, we have done two things:


SQL::QueryMaker and the Strict Mode of SQL::Maker

SQL::QueryMaker is a module that we have developed and released just recently. It is not a fully-featured query builder but a module that concentrates in building query conditions. Instead of using unblessed references, the module uses blessed references (i.e. objects) for representing SQL expressions / exports global functions for creating such objects. And such objects are accepted by the most recent versions of SQL::Maker as query conditions.

Besides that, we have also introduced strict mode to SQL::Maker. When operating under strict mode, SQL::Maker will not accept unblessed references as its arguments, so that it would be impossible for attackers to inject SQL operators even if the application developers forgot to type-check the supplied JSON values.

The two together provides a interface immune to JSON SQL injection. The code snippet shown below is an example using the features. Please consult the documentation of the modules for more detail.

use SQL::Maker;
use SQL::QueryMaker;

my $maker = SQL::Maker->new(
   …,
   strict => 1,
);

# generates: SELECT * FROM `user` WHERE `name`=?
$maker->select('user', ['*'], {name => $json->{‘name'}}); 

# generates: SELECT * FROM `fruit` WHERE `price`<=?
$maker->select('fruit', ['*'], {price => sql_le($json->{‘max_price’})}); 


Similar Problem may Exist in Other Languages / Libraries

I would not be surprised if the same proneness exist in other modules of Perl or similar libraries available for other programming languages, since it would seem natural from the programmers' standpoint to change the behaviour of the match condition based on the type of the supplied value.

Generally speaking application developers should not except that a value within JSON is of a certain type. You should always check the type before using them. OTOH we believe that library developers should provide a programming interface immune to vulnerabilities, as we have done in the case of SQL::Maker and SQL::QueryMaker.


Note: the issue was originally reported by Mr. Toshiharu Sugiyama, my colleague working at DeNA Co., Ltd.

Determining whether if a function (or variable, or constant) is declared in C++11

As @mattn_jp pointed out on his blog entry, C/C++ allow use of redundant parenthesis in variable declaration. For example, both of the following statements conform to the language specification.

int i = 3; // declares variable i, initialized to 3
int (j) = 4; // declares variable j, initialized to 4

By using this feature, it is possible to create a macro that tests the existence of whatever variable or constant.

The macro: is_defined in the following example is one such implementation.

Compiling and running the code would likely emit is NAN defined? yes. But if you remove #include <cmath> the output will likely change to false, since NAN is a constant defined in cmath.

#include <iostream>
#include <cmath>

struct is_defined_t {
  static bool defined_;
  is_defined_t() { defined_ = false; }
  template <typename T> explicit is_defined_t(const T&) { defined_ = true; }
};

bool is_defined_t::defined_;

#define is_defined(arg) (([]() { is_defined_t(arg); return is_defined_t::defined_; })())

int main(int argc, char **argv)
{
  std::cout << "is NAN defined? " << (is_defined(NAN) ? "yes" : "no") << std::endl;
  return 0;
}

Shortcoming of the example is that the result can be only obtained at runtime. It would be useful if we could get the result at compile time, since once we have such thing, we can get rid of autoconf, CMake, etc.

Friday, June 27, 2014

LINE「独自暗号化」のメリットと安全性について

LINEが使用している「独自の」暗号化手法について、情報が一部開示(参照:LINEの暗号化について « LINE Engineers' Blog)され、Twitterでもやりとりをしたので、まとめてみる。

■なぜTLSを使わないか

TLSではなく、1パスのメッセージ暗号化を使っている理由については、Adopting SPDY in LINE – Part 2: The Details « LINE Engineers' Blogに以下のような記載があり、TLSを使うことによるレイテンシの増加を懸念しているためと考えられる。
3G mobiles networks normally operate at slow speeds. (中略)If the connection changes modes when the user sends a message, we are forced to wait until we receive the server response before we can do anything else.

■どのような暗号化手法なのか

RSA暗号に加え、ブロックサイズが128bitの共通鍵暗号を用いており、共通鍵暗号の鍵をサーバのRSA公開鍵で暗号化し、共通鍵暗号で暗号化されたメッセージとともに送信していると考えられる(参考:ツイート 1, 2, 3, 4)。

おそらく、リクエストを送信する度に、大筋で以下のようなことを行っているのではないか。
# AES鍵を生成
AESKEY=`openssl rand -hex 16`注6

# 初期化ベクタを生成
IV=`openssl rand -hex 16`

# AES鍵をサーバの公開鍵で暗号化注1し、HTTPリクエストヘッダとして送信
echo -n "$AESKEY" | openssl rsautl -encrypt -pubin -inkey server-public.pem -in /dev/stdin | openssl base64

# POSTリクエストのボディをAESを利用して暗号化し、送信
echo -n "$content" | openssl enc -aes-128-cbc -in /dev/stdin -K "$AESKEY" -iv "$IV" | openssl base64

■この手法は安全か

RSAやAESといった暗号アルゴリズムは正しく使わないと脆弱になるし、どのように使っているかは今回開示されていない。とは言え、このように良く知られた部品(PKCS #1 v1.5とAES-CBC)を単純な形で組み合わせているのであれば、問題がある可能性は低い注2。実際のところ、上記推測例は、秘話化という観点からは僕には特に問題がないように思える。問題があるなら誰か教えてほしい注3

手法の推測が正しいならば、「通信全体について、他国からアクセスすることは不可能」注4ということだし、「システムに直接侵入するのではなく、通信回線とサーバーの間でワイヤタッピング」注5することにより情報が漏洩している可能性は極めて小さいのではないか。

■同様の暗号化を行いたい場合はどうすればいいか

ウェブアプリケーションなどで使用が容易なメッセージ暗号化手法については、現在、JSON Web EncryptionがIETFで標準化の最終段階にあります。完全性保護も含まれているし、標準化団体での安全性検証が行われているこちらを使いましょう。対応しているライブラリについてはJSON Web Token (JWT) - OAuth.jpが参考になるかもしれません。


注1: この例ではPKCS #1 v1.5を使用しているが、RSA-KEMが、より望ましいかもしれない
注2: CBCモードの使用法については、NISTが出しているガイドライン(NIST SP 800-38A)と、CRYPTRECによる安全性評価を参照
注3: リプレイ攻撃への対策や完全性保護については、この例には含めていない
注4: 参照:LINE、改めて傍受を否定 「暗号化後データは独自形式、解読は不能」 - ITmedia ニュース
注5: 参照:韓国国情院がLINE傍受:FACTA online
注6: 生成している鍵とIVの長さが64bitになっていたのを修正 (11:21am)

Thursday, June 5, 2014

Unix系OSの権限分離の変遷について(もしくはなぜ、アプリ単位の権限分離が求められるようになったか)

[ブコメした件について。大筋でおかしなことは書いてないと思いますが、出典は確認していません]

Unix系OSにおける権限分離は、伝統的に、利用者ごとに異なるuser idを割り振り、これを用いてアクセス制御を行うという方式で実現されてきた。また、デーモンプロセスについては、不要な権限付与を避け、デーモンプロセス間の相互作用を抑制するために、デーモンごとに専用の「user id」を発番するのが一般的な慣習とされるようになったという経緯がある。

しかし、2000年代に入ると、インターネットの普及とあいまって、クライアントサイドではこのような「利用者ごと」の権限分離では不十分という考え方がされるようになってきた。具体的には、

  • (オンラインバンクのパスワードに代表されるような)攻撃価値が高い情報をOS内に保存・利用するのが一般的になった
  • (限定された流通経路で入手するソフトウェアのみならず)インターネットからダウンロードしたプログラムを実行するという慣習が一般的になった
のようにユーザー行動が変化した結果、高いセキュリティが要求される処理と、セキュリティよりも利便性を重視したい処理が、同一のアクセス権限のもとに併存するようになったのである。だが、そのような状況は危険である(ネットからダウンロードしたマルウェアによって重要な情報が流出する可能性がある)。よって、同一ユーザー権限のもとで動作するプログラム間においても、アクセス権限の分離の必要性が認められるようになってきたのだ。

このため、iOSやAndroidのようなスマホOSにおいては、利用者ごとではなくプログラムごとに異なる「user id」を割り振り、互いのデータにアクセスできないような仕組みになっている。

一方でOS Xのような、より以前からあるUnix系OSにおいては、このような仕組みに移行することは現実的でないため、Keychainのように、秘匿性の高い情報についてのみプログラム単位でのアクセス制御機能を提供することで、問題の緩和が計られている。

以上のような経緯があるので、クライアント上で一般ユーザー権限で動作するプログラムにおいて、(psコマンド等を通じて情報が流出する問題がある)環境変数に認証情報を格納するのは避けるべきと言えるだろう。

Friday, May 23, 2014

[メモ] Perlのクロージャ生成速度は遅くない件

いくつかのスクリプト言語の処理系では、オブジェクトを生成して利用する場合と比較して、クロージャを生成する場合のオーバーヘッドが大きいという問題が知られています。最近、Perlでクロージャを使いたい場面に遭遇したので、ベンチマークをとってみることにしました。

結果、以下のように両者を使うアプローチで大きな速度差はないということがわかったのでメモ。

$ perl closure-vs-method.pl
         Rate  method closure
method  535/s      --    -12%
closure 609/s     14%      --
$ cat closure-vs-method.pl
use strict;
use warnings;
use Benchmark qw(cmpthese);

my $COUNT = 1000;

sub doit_closed {
    my $cb = shift;
    $cb->();
}

sub doit_method {
    my $cb = shift;
    $cb->meth();
}

cmpthese(-1, {
    'closure' => sub {
        for my $i (1..$COUNT) {
            doit_closed(sub {
                $i;
            });
        }
    },
    'method' => sub {
        for my $i (1..$COUNT) {
            doit_method(Holder->new($i));
        }
    }
});

package Holder;

sub new {
    my ($class, $value) = @_;
    return bless {
        value => $value
    }, $class;
}

sub meth {
    my $self = shift;
    return $self->{value};
}

Tuesday, May 20, 2014

[メモ] Apache+mod_sslでSIGBUSが発生した件

@hirose31さんと、Apache HTTPDからHTTPSでファイルダウンロード中にサーバプロセスがSIGBUSで死ぬって件にぶちあたり、

「OpenSSLの中でmemcpyがSIGBUSしてます」「な、なんだってー!」

って調べたのですが、理由は以下のとおりだった。

  • HTTPSの場合、デフォルト設定だとファイル読込にmmap(2)が使われる
    • mmapされたファイルのサイズが変更されてもApacheはそれを検知しようがない
    • そして、ファイル末尾以降のデータを読もうとするとセグメンテーションエラー(SIGBUS)が発生し、Apacheのサーバプロセスは異常終了する
  • HTTPの場合は、ローカルファイルシステムの場合sendfile(2)が使われるので、ファイルサイズが変更になってもApacheは異常終了しない
    • ただし、mod_deflateのような出力フィルタを使っている場合は、HTTPS同様に異常終了する可能性がある注1

この動作はApacheの「仕様」のようです注1日本語版だとNFS特有の現象のように読めるけど、英語版は以下のように書かれています。
Deleting or truncating a file while httpd has it memory-mapped can cause httpd to crash with a segmentation fault.
EnableMMAP Directive - core - Apache HTTP Server
言われてみれば当然だけど、mmapやsendfile等を自動的に使い分けているサーバの場合、これが原因だとは気づきにくいですよね。

というわけで、Apacheを使う場合はEnableMMAP Offにしておきましょう注1、さもないとアラートが上がってきたりしてウザいですよという話でした。本当は配信ファイルを全てアトミックに更新できばいいのですが、運用的にできないこともありますからね。

Apache以外のサーバでも同様の問題があるかどうかは知りません。

注1: HTTPSに限らない問題なので加筆修正 (17:06)。参照: Bug 46688 – Child segfault when mmaped file truncated

Friday, May 9, 2014

良いソフトウェアに求められる3点セットとJSXの開発手法の改善とgit-pushdirについて


テスト駆動開発(TDD)の一般化とGitHubの登場によって、機能追加の際にコードとテストを同時に実装する(そして、両者を一括してmasterにmergeする)という開発手法が一般化してきました。

しかし、「良いプログラム」の要素を構成するのは、コードとテストのみではありません。動作するコードと、その品質を担保するためのテストがあったとしても、適切なドキュメントがなければ、ユーザーはそのプログラムをどうやって使ったら良いかわかりません。

つまり、ユーザーに使いやすいプログラムを継続的に開発/提供しようと思うと、

  • コード
  • テスト
  • ドキュメント

の3点セットを提供する必要があるのです注1

今日のJSXが抱えている最大の課題は、ドキュメントが不足しているという点にあります。その原因は、「機能追加」の際にコードとテストのみを実装してmasterにmergeすることを繰り返す一方で、ドキュメントはプロジェクトページレポジトリとして別個に更新作業を行ってきた注2点にあり、その結果、コードとテストは存在するが対応するドキュメントがない機能がいろいろ実装されてきてしまった、と認識しています。

以上の認識に基づき、JSXのプロジェクトページにあった文書を全てJSX本体のレポジトリへ移動しました。今後は、

  • プルリクエストはコード/テスト/ドキュメントの3点セットで構成すること注4
  • そのために、すべてのドキュメントをレポジトリ本体の一部として管理すること

という形で運用していきたいと考えています。

また、この目標を実現するために、git-pushdirというスクリプトを書きました。このスクリプトは、あるディレクトリの中にあるファイルを丸ごと、指定したGitレポジトリにpushすることができます。JSXではこのスクリプトをMakefileから以下のように呼び出すことで、リリースの際に自動的にプロジェクトページのドキュメントを更新するようにしました。

publish: publish-test
        npm publish
        $(MAKE) doc-publish

doc-publish: doc
        (cd doc/jsx.github.com && ../../tool/git-pushdir -m "`git log --format='doc at commit %h' | head -1`" git@github.com:jsx/jsx.github.com.git)


似たようなことはgit subtreeを使っても可能注3ですが、subtreeの定義やpullした場合のconflictに絡む問題がない点がgit-pushdirの優位性になるかと思います。

つーことでよろしくお願いします>関係者諸氏。

注1: テストを書くコストが見合わない、あるいはドキュメントなど不要というケースもあるとは思います
注2: jsxdoc(javadocライクなツール)が出力するAPIリファレンスではなく、言語仕様に関わる文書のようなものについて述べています
注3: 参照: git subtreeで自動生成ドキュメントをGitHub Pagesに連携してみた - Life goes on
注4: コードとテストのレビュー完了 → ドキュメント加筆更新 → merge というフローでいいと思います

Tuesday, April 22, 2014

[perl][memo] File::Tempのバッドノウハウ

■まとめ
  • tempfile(...)が作成したテンポラリファイルは、環境によってはflockされていることがある
  • tempfile(CLEANUP => 1)は、テンポラリファイルへの参照をretainする
  • つまり、CLEANUPを指定している場合、参照カウントに頼った自動closeは機能しないので、明示的にcloseする必要がある
  • また、明示的にcloseしないとflock可能にならない場合がある

■ログ
16:23:30 <kazuho_> あれ perl って file handle への refcnt がゼロになったら自動的に close してくれますよね
16:23:43 <tokuhirom> してくれますね
16:23:48 <tokuhirom> しなきゃおかしいw
16:32:33 <kazuho_> https://gist.github.com/kazuho/11168660
16:32:37 <kazuho_> こういうことだった
16:32:53 <tokuhirom> あー。それな。
16:33:01 <tokuhirom> なんか File::Temp さんごちゃごちゃやってんすよね
16:42:37 <kazuho_> linux で perl -MFile::Temp=tempfile -e '(undef, my $fn) = tempfile(UNLINK => 1); sleep 100'
16:42:47 <kazuho_> ってやっても、テンポラリファイルが開きっぱになるなー
16:49:41 <kazuho_> _deferred_unlink って関数が $fh にぎにぎしちゃうのかー > File::Temp
16:50:50 <tokuhirom> UNLINK => 1 するとなかなか UNLINK されなくなるの、だいぶアレゲですねw
16:51:16 <kazuho_> というより、
16:51:22 <kazuho_> > # close the filehandle without checking its state
16:51:23 <kazuho_> > # in order to make real sure that this is closed
16:51:30 <kazuho_> という理由で $fh をにぎりっぱにしてるから
16:51:38 <kazuho_> refcnt 減らしても自動でcloseされない
16:52:13 <tokuhirom> なんか UNLINK => 0 してやり過ごすってのを昔見た気がした
16:52:27 <kazuho_> そしたら自動削除してくれないじゃんw
16:52:33 <kazuho_> 明示的にcloseするわ…
16:53:03 <kazuho_> Starlet で select を、テンポラリファイルの flock で囲おうとしてるんだけど
16:53:15 <kazuho_> osx だと tempfile が EXLOCK 指定する
16:53:23 <kazuho_> → UNLINK してるとファイル開いたままになる
16:53:28 <kazuho_> → ロックできない!!!
16:53:34 <kazuho_> という問題なので
16:54:01 <tokuhirom> 明示的にクローズが正解かー
16:54:07 <kazuho_> ですね
16:54:09 <kazuho_> まあ、UNLINK => 1 してるとファイル開きっぱになるの、バグだと思うけどなー
16:54:15 <kazuho_> file descriptorたりなくなるじゃん!!
16:54:52 <kazuho_> まあそういう場合は tempdir してその中に手動でファイル作ろうね、なんだろうな
16:54:53 <tokuhirom> なんかでもそこ今更変えられなさそうw
16:54:57 <kazuho_> 変えようがないでしょうね
16:54:58 <tokuhirom> a-
16:55:40 <kazuho_> あざますあざます

Friday, April 11, 2014

[メモ] Starlet 0.22のリリースに伴いThundering Herd問題を再訪した件

@takezawaさんから、PerlベースのWebアプリケーションサーバであるStarletで複数ポートをlistenできるようにするPRをいただいたのでマージしました。やったね!

で、それに伴いprefork型TCPサーバのThundering Herd問題を再訪したので、その備忘録。なお、Thundering Herd問題については、prefork サーバーと thundering herd 問題 - naoyaのはてなダイアリーや、Starman と Starlet のベンチマークと Accept Serialization - Hateburo: kazeburo hatenablogあたりを参照のこと。

まず、こんなテストスクリプトを書いた: thundering-herd.pl

こいつを書いてあるコメントのとおり実行してみることで、2種類のケースでThundering Herd問題が存在するか調べることができる。

で、こいつを使った結果、以下の結論に達した。
  • accept(2)の呼出によるThundering Herd問題だが、多くの環境で過去の問題になったと考えてよい
  • select(2)で接続を待ち受け、次にaccept(2)を呼ぶようなケースでは、依然としてThundering Herd問題が存在する(当然と言えば当然だが)
とか言ってみたけど、、linux 2.6.32とOS X 10.8.5でしかテストしてないので、補足あれば教えてください m(__)m

あと、複数のポートにbind(2)するTCPサーバを書く際に注意すべき点として、prefork型サーバでselect(2)accept(2)の呼出順序で接続を確立する際は、ソケットをnonblockingモードにしておかないと、ワーカプロセスが余っているのに接続できないといった事態が発生する可能性がある。

この点は、上記のテストスクリプトを書くまでレビューするのを忘れていたんだけど、確認したらtakezawaさんのコードではちゃんと記述されていて、ちょっと感動した。いい仕事ありがとうございました。

Heartbleed脆弱性と、その背後にあるWebアプリケーションアーキテクチャの一般的欠陥について

■Heartbleedのリスクと善後策

Heartbleedは、攻撃者が一定の条件を満たすOpenSSLが動作しているサーバの、任意位置のメモリを外部から読み出すことができてしまうという脆弱性です。具体的には、以下のようなリスクが想定されています。

  • 秘密鍵の漏洩による、偽サイトの出現(あるいは中間者攻撃)
  • 秘密鍵の漏洩により、(過去のものを含む)パケットキャプチャの解読
  • サーバの同一プロセスが行った処理に関連する(他のユーザーのパスワードやセッションキーを含む)データの漏洩

漏洩した秘密鍵を用いた攻撃には、ユーザーを偽サイトへ誘導できたり、パケットの経由点を管理しているなどの、経路上の要件が必要になります。他のユーザーのデータの漏洩については、経路上の要件は不要な一方、攻撃の実施に近いタイミングでサーバにアクセスしたユーザーのデータしか漏れない、という違いがあります。

どこまで対策を施すべきかは、攻撃を受けた可能性をどの程度と評価するか、個々の組織の判断によるところがあると思うのでコメントしませんが、以下のような対策が必要になる可能性があります。

  • 偽サイトの出現や中間者攻撃、これからのパケット解読を防ぐには、新しい秘密鍵/公開鍵ペアを使うサーバ証明書への更新と、現行のサーバ証明書のrevocation
  • 秘密鍵の漏洩によって過去のパケット解読が容易になることのないよう、Forward Secrecyを満たすようなサーバ設定
  • 他のユーザーのものを含むデータの漏洩については、セッション情報のリセットとパスワードの再設定のお願い

■Heartbleedの背景

Heartbleedのような問題は、そもそもなぜ発生するのでしょう。それは言うまでもなく、安全性の根拠をプログラムが正しく記述されることに求めているからです(つまり、プログラムにバグがあると脆弱性として発現する可能性があるから)。最小権限の原則が守られていない、と言い換えてもよいと思います。

Heartbleedにおいて他のユーザーのデータが漏洩するのは、一つのプロセスが複数のユーザーの通信を処理しているからです。ユーザーごとに(あるいは接続毎に)別個のプロセスを割り当てていれば、他のユーザーの通信内容が漏洩することは起こりえません。

秘密鍵の漏洩にしても、秘密鍵を必要とする処理(TLSのハンドシェイク中の一部処理に限られます)と、TLS Heartbeatの処理(ハンドシェイク中以外に限られます)を別個の権限の元で動作させていれば、発生しなかったと言えます(17:19修正)。

多くのOSのプロセス分離やファイルアクセス権の制御に見られるように、最小権限の原則に基づいたセキュリティは有効に機能することが知られています。

にもかかわらず、ウェブ関連のソフトウェアにおいては同原則を用いずに、安全性の根拠をプログラムにバグがない点に求めるという悪しき慣習が続いています。特に、機能別の権限分離はまだしも、アクセスユーザー別の権限分離については系統だった実施例が非常に少ないという印象をもっています。

たとえば、SQL Injectionに代表されるSQL関連の情報漏洩も、アクセス制御にRDBMSのアクセス制御機構を用いず、アプリケーションプログラム内のSQL(とそのエスケープ)が正しく記述されている点に、安全性の根拠を求めているが故に発生しているわけです注1

ウェブの黎明期においては、(小数のユーザが使用することが一般的だった)RDBMSの認証システムの要件と多数が使用するウェブの要件は異なるのでRDBMSの認証システムはウェブ向けには使用できない、というのは説得力のある言い訳でした。ですが、今やRDBMSの用途の多くがウェブアプリケーションのデータストアになっているはずです。にもかかわらず、RDBMS(あるいはその他のデータストア)のアクセス制御機構をウェブアプリケーションからのアクセス制御に使う、というのは一般的な手法になっていません。

同様の問題はウェブアプリケーションサーバにもあり、複数のユーザーのリクエストを単一のプロセスで処理する結果、情報漏洩が発生するケースが見受けられます注2

リバースプロキシ、アプリケーションサーバ、データストア、そういったウェブアプリケーションの各要素について、最小権限の原則に基づいた、アプリケーションにバグがあっても脆弱にならないようなアーキテクチャの構成技法と技術開発が求められているのではないでしょうか。


注1: 強制アクセス制御がうまく機能しないようなアクセスパターンも、もちろん存在します
注2: 卑近な例としては、ログインユーザーとして別のユーザの名前が表示されるとか

Wednesday, April 2, 2014

Announcing Unco - undo changes to files made by any command

Being sick of myself occasionally wiping off the changes made to files by running wrong commands, I have started writing a program called "Unco" (pronunciation: an-ko) - a command that records the changes to the file system, and let the users undo the changes afterwards if necessary.

Unlike existing command-level solutions like aliasing rm to trash-cli, Unco is designed to be capable of undoing changes made by any program; it hooks the library calls that affect the file system and records the changes for later undoing.

The following scenario illustrates how it can be used, in case of git.
  1. instruct the shell to record all git commands
    % alias git="unco record -- git"
    
  2. edit file under the git repository
    % vi program.c
    
  3. Oops! I have accidentally reset the changes
    % git reset --hard HEAD
    
  4. don't worry, just undo the last action
    % undo history
    index    command (*=undone)
         1   git reset --hard HEAD
    % unco undo 1
    
As described, you can apply unco for rm or make install or whatever command.

The development is still in early stages, and I would not advise anybody not capable of debugging the code by oneself to use it. But for those interested, the repo is at github.com/kazuho/unco.

For the time being, the program runs on OS X and linux (edited Apr. 3 2014)only on OS X. Hopefully the command may be polished up so that it can be turned on by default; i.e. record all commands run on the shell by default.

Monday, March 17, 2014

「技術的負債」をコントロールする定量評価手法への期待

「「技術的負債」を問いなおす」というタイトルでJAWS DAYS 2014で話してきた #jawsdays - delirious thoughtsにて、追記でコメントいただけたので、外野として好き放題言わせてください。すばらしいスライドありがとうございます&いつもすみません。

僕が興味がもつとすると、それは「技術的負債」の定量評価手法についてです。

なぜ、そういう前提を置くかと言うと、それは、たとえばKrutchenによる「技術的負債」の定性評価は、とてもわかりやすいものの、技術を取捨選択するツールとしては使えないからです。

スライドでは、技術評価における将来の不確定性を象徴する問題としてSSDの普及前夜にシャーディングをがんばって実装してしまう例をご紹介いただきましたが、実際、そのような不確実性を織り込んだ正しい決定を我々が日々のエンジニアリングで下すことができているのか疑問に感じることが多いです。思いつくがままに挙げると、例えば以下のようなことを疑問に感じたことがあります。

  • ライブラリやフレームワークを採用するにあたり、その将来性を何年程度のスパンで評価すればいいのか
  • ウェブサービスを開発するにあたり、最初からシャーディングの機能を作り込むことは正しいのか
    • それとも、サービスが当たってからシャーディング機能を実装するほうが利益は大きいのか
  • プロトタイピングにおいて、きれいな実装を行うべきなのか、それとも汚くても早期に実装できたほうがいいのか
    • プロトタイプのコードをサービスインする確率によって答えは変わるはずだが、その確率の閾値はいくらなのか

これらの例からもわかるように、ライブラリ等の部品を選定する際の評価や、規模拡大や拡張を前提とした作り込みの程度を決定するには、「技術的負債」についての定性評価ではなく定量評価が必要です。そして、kentaroさんによる「割引率」という概念の導入は、それを可能にするという点で、僕には興味深く感じられます。

感覚的に言うと、

  • 割引率は、ある期間の後にそのソフトウェアをメンテすることになる可能性
  • 期間毎の割引率に「技術的負債」の解消に必要なコストを掛けて積分したものが、予測されるTCO
  • 予測されるTCOを最小に抑えるのが、正しい技術的選択

のような形として、定量的に評価し、現時点において正しい選択を取るためのツールとして「技術的負債」を使うことが可能になるのではないか。

「これからはnode.jsでしょ」とか「サービスがヒットしたら必要になるから、シャーディング機能は作り込むべき」といった感覚論ではなく、技術的判断をサポートする定量評価手法として「技術的負債」を使えればいいなと思う次第です。


23:37追記: ↓とのことです。ありがとうございます。

Monday, March 10, 2014

拡張可能なWeb APIの設計原則と、バージョン番号を使う理由について

APIのバージョニングは限局分岐でやるのが良い - Hidden in Plain Sightにはブコメしたのですが、Rebuild: 35: You Don't Need API Version 2 (Kenn Ejima)でも本件に言及があったようなので、少し一般論を書いておきたいと思います。


■Web APIの設計原則について

そもそも、良いAPIとはどのような特性をもつものでしょうか? 一般的に、以下の2点が挙げられると思います。
  • 拡張が容易である
  • 拡張時に後方互換性を破壊しない

ウェブの場合は、これに加え、
  • スケーラブルである
  • HTTPに起因する問題に上手に対処できる
ことが求められます。

前2者はウェブに限らない要件です。これを満たす設計手法としては、
  • リクエストおよびレスポンスのパラメータを拡張可能に
  • 互換性を壊す拡張が必要な場合は、関数名を変える
    • 古い関数は従来と同じ機能を提供する
  • ステートフルAPIは、抽象データ型の使用
といった手法が一般的です。

たとえばMicrosoft WindowsのAPIを見ると、多くのリクエストとレスポンス型が拡張可能であり(cbSizeというフィールドで拡張領域を指定する)、非互換な拡張がされたAPIは「〜Ex」という名前をもっており、ステートの表現にはHANDLEという抽象データ型が使われていることが分かります。

これに対し、後2者はウェブ固有の色合いが強い要件です。そして、そのための設計手法として、
  • (出来る限り)ステートレスなAPI
  • 冪等性に対する配慮
が求められる、ということが知られています(したがって、「ステートフルなAPIにおける抽象型の利用」という一般的な設計手法は検討対象外となる)。

以上の2者をまとめると、Web APIを設計する基本原則として、以下の4点を採用するのが良い、ということになります。
  • 拡張可能なパラメータ
    • JSONのような拡張可能なシリアライズフォーマットを用い、拡張可能な形で入出力パラメータを設計する
  • 互換性を壊す必要がある場合は関数名を変更する
  • できるだけステートレス
  • 冪等性に対する配慮
    • よく分からなければ、とりあえずRESTを使う

このような設計をとっていれば、APIを拡張しても後方互換性を確保することができますし、バージョン番号による分岐も必要になりません。


■バージョン番号をURLに含めるべき理由

述べたように、拡張可能なWeb APIの設計において、バージョン番号による分岐という概念は必ずしも必要なものではありません。ですが実際は、それでもバージョン番号をURLに含めるべきだと考えられることがあります。

APIが拡張(ないし変更)されていくということは、すなわち、サーバサイドの提供するAPIの「バージョン」とクライアントアプリケーションが期待するバージョンの齟齬による互換性問題が発生しうるということを意味します。そして、そのような互換性問題は、実行中の良くわからないエラーではなく(データ保存しようとしたらエラーとか最悪ですね!)、明確にトラブルシュートできる、つまり、起動時のバージョンチェックで検出され、ユーザーや管理者に明確に通知されることが望ましいということになります。

実際には、以下のような要件のもとで、確実に機能するバージョンチェック機構が望ましいということになります。
  • クライアントが「廃止された」APIに依存しているかどうかは、サーバサイドでないとチェックできない
  • クライアントアプリケーションの開発者は、しばしば「バージョンチェックを怠る」

もうお分かりでしょうか。この要件を最も単純に実現する手法が、APIのURLにバージョン番号を含めるという手法なのです。APIに対する全てのリクエストにバージョン番号が含まれるため、「クライアント側でバージョンチェックを怠った」がゆえのエラーは発生しようがありません。また、サーバサイドのログにもバージョン番号が残るため、管理者の側で問題の切り分けを要求された場合にも、対処することが容易です。

これが、バージョン番号をAPIのURLに含めるべきと考えられる理由です。必ずしも全ての条件において必要ではないかもしれませんが、一考に値するのではないでしょうか。

なお蛇足ですが、APIのバージョニングについては、サービスとしてしか提供しないソフトウェアの場合は、後方互換性を崩す度にバージョン番号の変更が必要です。また、サーバをソフトウェア製品として提供する場合には、機能拡張を行う度にバージョン番号の変更が必要になります注1(2014/3/11加筆)。ですので、特に後者のバージョン番号発番については、semantic versioningを参考に、MAJOR.MINORのような記法を採用するのが望ましいと言えるでしょう。


参考文献: Webを支える技術 -HTTP、URI、HTML、そしてREST (WEB+DB PRESS plus)

注1: クライアントの機能が特定のマイナーバージョン以降に依存することもあり、かつ、サーバサイドのバージョンがクライアントサイドのそれより古いことがあり得るため

Tuesday, February 25, 2014

ウェブアプリの「合理的な」セキュリティ対策に関する一考察

※※※ミドルウェアを中心に、ウェブ関連の研究開発に携わっている者による雑文です※※※

ウェブの脆弱性は、ウェブアプリケーションのバグに起因するものと、ウェブブラウザのバグに起因するものの2者に大別することができる。

ウェブアプリケーションを開発/提供する仕事に従事している者には、この前者、すなわち、ウェブアプリケーションのバグに起因する脆弱性を最小限に抑え込むことを求められる注1

かといって、脆弱性がないことを保障するのは難しい。「ウェブアプリケーションにバグがあっても脆弱性とはならない(あるいは被害が限定される)ような設計」を採用するのが現実的だと考えられる。

OSにおける、プロセス間のメモリ分離やuserIDに基づいたファイルへのアクセス制御を考えてみると、OSがセキュリティを「強制」するため、アプリケーション側で不正なコードが実行されても脆弱性とならない、もしくは、影響を小さく抑え込むことができるようになっていることがわかる。

ウェブ技術における同様の例は数多いが、たとえばXSS脆弱性対策を見ると、


といったものを挙げることができる。また、SQL Injection対策を見ると、


等の手法が知られている。

これらの対策をひとつ選択し、あるいは組み合わせて使うことで、コーディングミスがあったとしても脆弱性が発現しない(もしくは発現する可能性が低い)アプリケーションを実現することができる

ただ、この種の技術には多かれ少なかれ、アプリケーション側のコードに不自由を強いるという側面がある。

たとえば、Content Security Policyには、インラインの<SCRIPT>タグを実行しづらいという制限がある(1.1で修正見込)し、例として挙げたSQL Injection対策のいずれもが現実的でないウェブアプリケーションも多いだろう。また、SQLにおける条件節の漏れによる情報漏洩のように、本質的に対策が難しい注3問題も存在する。

以上のように、共通モジュール(あるいは下位レイヤ)でアクセス方法を「強制」する仕組みを用いることで、脆弱性への耐性を高めるという情報工学における一般的なアプローチは、ウェブ技術においても有効であり、積極的に使用すべきである注4。一方で、述べたように、今後の発展が期待される分野も存在する注5



注1: 後者については、一義的にはウェブブラウザベンダーが対応すべき問題である。もちろん、ウェブアプリケーション側で緩和策が実装できるならすれば良いケースもある

注2: 最新のテンプレートエンジン事情を良く知らないので列挙はしません。また、DOM APIベースのアプローチについても本稿では割愛します。

注3: ウェブアプリケーションにおいては、アクセス制限とアクセスを単一のクエリで記述することを求められることが多いため。この点は、ケーパビリティの概念を導入したORMのようなアプローチで解決可能なのかもしれないが…

注4: 「IPA 独立行政法人 情報処理推進機構:安全なウェブサイトの作り方」では、脆弱性を9種類に類型化して説明しているが、そのほとんどは「アプリケーションプログラマがミスをしても問題ない」ような共通コード(ウェブアプリケーションフレームワークやライブラリ等)の使用により回避することが可能であるし、そのような実装が称揚されるべきである

注5: なので、研究課題として面白いと思います

Friday, February 7, 2014

Why asm.js sometimes runs faster than hand-written JavaScript (and the changes in JSX 0.9.77)

I have released an update (version 0.9.77) of JSX - a statically-typed altJS programming language with an optimizing compiler to JavaScript, with the following changes:

  • the definition of int has been changed to strict 32-bit signed integer
  • introduce Promise class in conformance to the ECMAScript 6 draft

The second change should be obvious. Let me explain the reasoning behind the first one.

Background:

Until now, definition of int in JSX has been: a number that is at least possible to represent integers between -231 to 231-1, or may or may not become NaN or +-Infinity.

This was based on our understanding that enforcing integer arithmetic in JavaScript (i.e. using | 0) would lead to slower execution speed. We wanted the int type of JSX to represent some kind of integral numbers without sacrificing execution speed. And the type had been defined as such.

But the advent of asm.js has changed the game. Such enforced integer arithmetic is one of the most common patterns found in JavaScript generated by Emscripten (since it compiles C/C++ code), and it would be natural to expect that existing JavaScript runtimes would optimize against such patterns.

The Benchmark:

So I decided to take time to run a tiny benchmark that compares the execution speed of ordinary arithmetic vs. enforced integer arithmetic on fib-using-int - jsPerf, and the results are interesting.

The benchmark compares three functions calculating Fibonacci numbers using loops.

// original
function fib(n) {
  var value = 1, prev = 1;
  for (var i = 1; i < n; ++i) {
    var t = prev;
    prev = value;
    value += t;
  }
  return value;
}

// core operation is enforced integer arith.
function fib(n) {
  var value = 1, prev = 1;
  for (var i = 1; i < n; ++i) {
    var t = prev;
    prev = value;
    value = (value + t) | 0;                <--- HERE
  }
  return value;
}

// core operation and loop are integer arith.
function fib(n) {
  n = n | 0;                                <--- HERE
  var value = 1, prev = 1;
  for (var i = 1; i < n; i = (i + 1) | 0) { <--- HERE
    var t = prev;
    prev = value;
    value = (value + t) | 0;                <--- HERE
  }
  return value;
}

Looking at the results below (please refer to the benchmark page for the latest numbers) the fact is that code runs about 10% faster on Chrome and Firefox when explicitly specifying an extra operation (i.e. | 0).


This is not a surprise for people with the understanding of how the JIT (just-in-time-compile) engines of the runtimes work. The engines compile arithmetic operations in the original function of the benchmark into integer arithmetics with guards, so that the calculation can be changed to use floating-point operations once the numbers goes out of the 32-bit integer range. But if | 0 is added to the statement it becomes clear that the result of the arithmetic should be a module of 232 and thus that the guards become no longer necessary.

The Problem and the Solution:

The problem being left is how to write code that takes benefit from such optimizations. It is hard to add | 0 all over the source code, and there would be a negative performance impact unless you succeed in marking all of them correctly. It is once again clear that some kind of automated code generator is desirable for JavaScript, and this is the reason why we are happily applying the described change to JSX :-)

To summarize, JSX as of version 0.9.77 supports strict 32-bit integer arithmetic; and it is easy for the users to benefit from the described optimizations within the JavaScript runtimes. It's just a matter of marking some variables as : int. And the results of assignment to the variable as well as additions, subtractions, and multiplication between such variables would be int.


PS. I have also written the Fibonacci calculator in asm.js, but have excluded the numbers from the benchmark since it was too slow. It seems that there exists a non-marginal overhead when calling asm.js code from JavaScript.

Thursday, January 30, 2014

Q4M 0.9.12 has been released

Today I have released version 0.9.12 of Q4M - a message queue storage engine for MySQL.

As of the release, Q4M finally includes CMakeFiles.txt, file necessary for building Q4M together with MySQL 5.5 and above. The installation procedure is described in q4m.github.io/install.html.

Changelog is also available at the homepage. Have fun!

Tuesday, January 28, 2014

SSL/TLSライブラリの正しい使い方(もしくは、コモンネームの検証について)

スマホアプリの市場拡大に伴い、直接SSL/TLSライブラリを使用するプログラムを書く機会も増えてきている今日この頃かと思います。

SSL/TLSライブラリを使う際には、接続確立時にサーバの認証を正しく行う必要があります。具体的には、クライアントプログラムで以下の2種類の検証を行うことになります

  • SSL/TLSライブラリがサーバの証明書の検証に成功したこと
  • サーバの証明書に含まれるコモンネーム注1が接続しようとしたサーバと同一であること

前者については、OpenSSLの場合はSSL_CTX_set_verifyの引数にSSL_VERIFY_PEERを指定するなどして、ライブラリ側で処理を行わせることが可能です(証明書の検証に失敗した場合はSSL_connectがエラーを返します)。

一方、後者についてはSSL/TLSライブラリによって差があり、検証機能を有効にするために特別な呼出が必要だったり、あるいは検証機能を提供していないライブラリもあるため注意が必要です(これは、SSL/TLSが任意のストリームで安全な通信手段を確立するためのものであるのに対し、コモンネームの検証はTCP/IP+DNS上でSSL/TLSを使用する場合に必要となる作業である、という要件のズレによるものです)。

たとえば、OpenSSLはコモンネームの検証機能を提供していないので、アプリケーションプログラマが独自に同機能を実装する必要があります。具体的な方法はいくつかあるのですが、最も単純な形で以下のようになるかと思います注2

// returns non-zero value if the verification succeeds
static int verify_common_name_of_ssl(SSL* ssl, const char* hostname)
{
    X509* peer;
    X509_NAME* subject_name;
    char peer_name[256];

    peer = X509_get_peer_certificate(ssl);
    if (peer == NULL)
        return 0; // fail
    subject_name = X509_get_subject_name(X509_get_peer_certificate(ssl);
    if (subject_name == NULL)
        return 0; // fail
    if (X509_NAME_get_text_by_NID(subject_name, NID_commonName, peer_name, sizeof(peer_name)) == -1)
        return 0; // fail
    return strcasecmp(peer_name, hostname) == 0;
}

Android SDKを使っている場合は、公式ドキュメントに注意喚起と対応方法の説明があるので、そちらを参考にすれば良いかと思います(参照: Warnings About Using SSLSocket Directly - Security with HTTPS and SSL | Android Developers)。

iOSでSecure Transportを使っている場合は、SSLSetPeerDomainNameを呼び出して、ライブラリに検証を依頼することが推奨されています(参照: Secure Transport Reference)。

詳しくは、お使いのSSL/TLSライブラリのドキュメントを参照することをお勧めします注3

また、SSL/TLSを使用するアプリケーションのコードレビューや検証にあたっては、コモンネームの確認を行っているかを検証項目に含めることが望ましいと言えるでしょう。

注1: コモンネームとは、証明書に含まれる「www.google.com」等のホスト名のことです(参照: コモンネームとは何ですか - knowledge.verisign.co.jp
注2: ワイルドカード証明書への対応など、任意の証明書に対応する実装をするとなると泥沼が待っているかと思います(参照: WildcardCertificates - CAcert Wiki
注3: より高レベルな、ホスト名解決とTCP上でのSSL/TLS接続機能を一体として提供している類のライブラリにおいては、コモンネームの確認機能が組み込まれている場合が多いかと思います

Monday, January 27, 2014

JSX - experimental support for NPM

Based on @shibukawa-sans work, I have added experimental support for NPM-based packages in JSX 0.9.75. It is now possible to publish libraries for JSX using NPM (or use such packages from JSX).

A tiny example would be the following:

package.json:
{
  "dependencies": {
    "nodejs.jsx": "~ 0.1.1"
  }
}

hello-npm.jsx:
import "nodejs.jsx/*.jsx";

class _Main {
  static function main(args : string[]) : void {
    fs.appendFileSync("/dev/fd/1", "hello npm!\n");
  }
}

Running npm install would install nodejs.jsx (JSX binding for node.js) which is specified as a dependency in package.json. And when the compiler is executed (e.g. jsx hello-npm.jsx) it would automatically search for the imported files and use them in the node_modules directory.

For the time being, file specified in the main section of package.json is used if the name of a module is an argument to the import statement (e.g. import "npm-module-name"). Or the directory designated by the dependencies/lib section is searched if a file within an npm module is specified (e.g. import "npm-module-name/filename").

If you have any comments / suggestions please file a issue at the GitHub issues page.

Tuesday, January 21, 2014

Deflate (gzip) のアルゴリズムを視覚化してみた

DeflateとそのバリエーションであるZIPやgzipは、HTTPにおけるデータ転送やファイル圧縮など、様々な場面で使われる圧縮アルゴリズムです。

そのアルゴリズムの解説としてはslideshare.net/7shi/deflateを始め優れたものがいろいろあるかと思いますが、実際のデータをエンコードして視覚化できるものがないのが不満でした

というわけで、作った注1

ソースコードは、github.com/kazuho/visiflateにあります。

こいつをダウンロードして動かすと、記事の末尾の出力結果のようにダラダラと、どのようにエンコードされているかが表示されます。

この出力を見ることで、例えば、不思議の国のアリスのテキストをgzipすると

テキスト圧縮長
(ビット)
複製位置
"Alice was beginning to get very tired of sitt"224なし
"ing "1329バイト前
"by her"32なし
" si"1115バイト前
"st"9なし
"er "117バイト前
"on the bank, an"72なし
"d of "1342バイト前

のような感じにエンコードされることが分かります。

自分の好きなデータで試すことができて便利!という話でした。


PS. 以下は実行結果です。

% make
% gzip < alice.txt > alice.txt.gz
% ./puff -10 alice.txt.gz
puff() succeeded uncompressing 1328 bytes
8 compressed bytes unused
inpos=406,inbits=224,outpos=0,outbytes=45
    41 6c 69 63 65 20 77 61 73 20 62 65 67 69 6e 6e 69 6e 67 20 74 6f 20 67 65 74 20 76 65 72 79 20 74 69 72 65 64 20 6f 66 20 73 69 74 74
    A  l  i  c  e     w  a  s     b  e  g  i  n  n  i  n  g     t  o     g  e  t     v  e  r  y     t  i  r  e  d     o  f     s  i  t  t 

inpos=630,inbits=13,outpos=45,outbytes=4,distance=-29
    69 6e 67 20
    i  n  g    

inpos=643,inbits=32,outpos=49,outbytes=6
    62 79 20 68 65 72
    b  y     h  e  r 

inpos=675,inbits=11,outpos=55,outbytes=3,distance=-15
    20 73 69
       s  i 

inpos=686,inbits=9,outpos=58,outbytes=2
    73 74
    s  t 

inpos=695,inbits=11,outpos=60,outbytes=3,distance=-7
    65 72 20
    e  r    

inpos=706,inbits=72,outpos=63,outbytes=15
    6f 6e 20 74 68 65 20 62 61 6e 6b 2c 20 61 6e
    o  n     t  h  e     b  a  n  k  ,     a  n 

inpos=778,inbits=13,outpos=78,outbytes=5,distance=-42
    64 20 6f 66 20
    d     o  f    

注1: 元にしたのは、zlibに付属する参照実装であるPuff