OpenSSLでオレオレ認証局を作ろう

フリーなSSLの実装であるOpenSSLがこの世に登場してから15年以上の月日が経過しています。したがって、OpenSSLを使用したオレオレ認証局の構築手順を紹介しているサイトは多数あります。しかし、各操作の意味まで説明しているサイトは、残念ながらほとんど見当たりません。本稿では、オレオレ認証局の構築手順について、各操作の意味の説明を交えながら紹介しています。

(お断り)
本稿の内容は筆者がOpenSSLの公式文書、ソースコード、RFC (Request for Comments)、インターネット上の情報サイト、実機検証の結果などに基づいています。そのため、誤った内容を記載している場合がありますので、あらかじめご了承ください。

オレオレ認証局の構築

まず、オレオレ認証局を構築します。

準備

一般ユーザで構築するため、openssldirをホームディレクトリ直下にコピーします。Red Hat Enterprise Linuxの場合、openssldirは/etc/pki/tlsです。

$ cp -a /etc/pki/tls .

続いて、openssl.cnfを開き、CA_defaultセクションのdirを「./」に設定します。元々は、「./demoCA」や「../../CA」などになっていると思います。

キーペアの生成

まず、下記のコマンドを実行し、キーペアを生成します。

$ openssl genrsa -rand /dev/random 2048

証明書に使用するキーの長さは、本稿執筆の時点では2048ビット以上にするのがよいと言われています。なので、ここでは「2048」を指定しています。使用するランダムデバイスは/dev/urandomではなく、「/dev/random」を指定し、よりランダムな乱数が生成されることを期待しています。

/dev/randomを使用するにはエントロピーをたくさん貯める必要があります。エントロピーを速く貯めるには、コンソールでキーボードやマウスを動かしまくるといったことが行われますが、別の端末を立ち上げて下記のコマンドを実行するのが手っ取り早いです。

$ find / -type foobar >/dev/null 2>&1; ls -R / >/dev/null 2>&1; sync

この方法であれば手が疲れることもないし、リモート接続であっても速くエントロピーを貯めることができます。

ちなみに、エントロピーの貯まり具合は下記で確認できます。どんなコマンドを実行すると速く貯まるか調べてみるとよいでしょう。

$ cat /proc/sys/kernel/random/entropy_avail

証明書署名要求の作成

キーペアを生成したら、次は証明書署名要求 (Certificate Signed Request, CSR) を作成します。

$ openssl req -new -key private/cakey.pem -config openssl.cnf -out careq.pem

下記のように-x509 オプションを指定すれば、いきなりオレオレ認証局の証明書を作成することができますが、この方法だと細かい設定ができないので、今回はやりません。

$ openssl req -new -x509 -key private/cakey.pem -config openssl.cnf -out cacert.pem

証明書署名要求に自己署名

証明書署名要求に自己署名する前に、発行した証明書の履歴を格納する index.txt ファイルと、次に発行する証明書のシリアル番号を格納する serial ファイルを作成しておきます。これらのファイルを正しく作成しておかないと、証明書に署名しようとした時にエラーが発生します。

$ touch index.txt
$ echo 00 > serial

次に、X509v3拡張属性を設定するためのファイルを作成します。下記の3つを指定すればよいでしょう。

$ cat <<EOF > v3_ca
basicConstraints = critical, CA:true
keyUsage = critical, cRLSign, keyCertSign
subjectKeyIdentifier=hash
EOF

basicConstraintsの「CA:true」は認証局の証明書であることを設定しています。「CA:true」を指定する場合はcritialフラグを設定する必要があります。keyUsageはキーペアの用途を制限します。認証局の証明書なので、「cRLSign」と「keyCertSign」を設定しています。それぞれ、CRLへの署名と証明書への署名です。最後にsubjectKeyIdentifierを設定しています。「hash」は公開鍵のハッシュ値を埋め込むことを意味します。このハッシュ値と同じ値をこの認証局が発行した証明書のauthorityKeyIdentifierに埋め込むことで、その証明書がこの認証局から発行されたものであることを素早く確認できます。

続いて、証明書署名要求に自己署名します。期間は2015-03-01から2025-03-31までの10年間を指定しています。最後の「Z」を忘れると不正な証明書とみなされる場合があるので注意してください。

$ openssl ca -in careq.pem -selfsign -notext -config openssl.cnf -outdir . \
  -extfile v3_ca -out cacert.pem -startdate 150301000000Z -enddate 250331235959Z

内容を確認し、間違いがなければ「Y+Enter」を2回押してください。これで、オレオレ認証局が完成します。

サーバ証明書の発行

続いて、構築したオレオレ認証局を用いて、サーバ証明書を発行してみましょう。

キーペアの生成

これはオレオレ認証局を構築した時と同じです。キーの長さは2048ビット、ランダムデバイスは「/dev/random」を指定しています。

$ openssl genrsa -rand /dev/random 2048

証明書署名要求の作成

キーペアを生成したら、次は証明書署名要求 (Certificate Signed Request, CSR) を作成します。これもオレオレ認証局を構築した時と同じです。

$ openssl req -new -key private/server.csr -config openssl.cnf -out server.csr

証明書署名要求に署名

次に、X509v3 拡張属性を設定するためのファイルを作成します。下記の4つを指定すればよいでしょう。

$ cat <<EOF > v3_server
basicConstraints = CA:false
keyUsage = critical, digitalSignature, keyEncipherment
extendedKeyUsage = serverAuth
authorityKeyIdentifier=keyid,issuer
EOF

basicConstraintsの「CA:false」は認証局の証明書ではないことを設定しています。この証明書を使用して証明書を発行できないようにしています。keyUsageはキーペアの用途を制限します。サーバ証明書なので、「digitalSignature」と「 keyEncipherment」を指定しています。それぞれ、デジタル署名とキーの暗号化を指定しています。extendedKeyUsageは拡張キー使用法と呼ばれるもので、「サーバ認証」を指定しています。もし、クライアント用の証明書の場合は「クライアント認証」を指定します。authorityKeyIdentifierはkeyidとissuerを指定しています。これは、認証局の証明書にsubjectKeyIdentifierが含まれている場合はその値(認証局の公開鍵のハッシュ)を、含まれていない場合は認証局の証明書のDistinguishedNameを設定することを意味します。ここでは、認証局を構築するときにsubjectKeyIdentifierを指定しているので、その値が設定されます。

続いて、証明書署名要求に署名します。期間は2015-03-01から2017-03-31までの2年間を指定しています。最後の「Z」を忘れると不正な証明書とみなされる場合があるので注意してください。

$ openssl ca -in server.csr -notext -config openssl.cnf -outdir . \
  -extfile v3_server -out server.crt -startdate 150301000000Z -enddate 170331235959Z

これで、オレオレ認証局に署名されたサーバ証明書を発行できたと思います。

GHOST (CVE-2015-0235) について

1/27にglibcのgethostbynameでバッファオーバーフローのを脆弱性 (CVE-2015-0235) が発表されました。この脆弱性は、通称 GHOST と呼ばれています。

http://www.openwall.com/lists/oss-security/2015/01/27/9

CVE-2015-0235の原因

脆弱性が見つかったのは、nss/digits_dots.cの__nss_hostname_digits_dots()という内部関数。影響を受けるのは、内部で__nss_hostname_digits_dots()をコールしているgethostbyname()、gethostbyname_r()、gethostbyname2()、gethostbyname2_r()、gethostbyname3_r()の5つの関数です。

CVE-2015-0235は、内部で使用するバッファのサイズの見積ロジックに不備があり、その結果サイズが小さいバッファを割り当ててしまいバッファオーバーフローを引き起こしてしまう不具合によって引き起こされる脆弱性です。

それでは、問題箇所のソースコードを見てみましょう。下記は、nss/digits_dots.cにある__nss_hostname_digits_dots()関数の一部です。

      typedef unsigned char host_addr_t[16];
      host_addr_t *host_addr;
      typedef char *host_addr_list_t[2];
      host_addr_list_t *h_addr_ptrs;
      char **h_alias_ptr;
      size_t size_needed;
      ........
      size_needed = (sizeof (*host_addr)
                     + sizeof (*h_addr_ptrs) + strlen (name) + 1);★１
      ........
      host_addr = (host_addr_t *) *buffer;★２
      h_addr_ptrs = (host_addr_list_t *)
        ((char *) host_addr + sizeof (*host_addr));
      h_alias_ptr = (char **) ((char *) h_addr_ptrs + sizeof (*h_addr_ptrs));
      hostname = (char *) h_alias_ptr + sizeof (*h_alias_ptr);

★２の部分以下のコードより、bufferには、ホストアドレス、ホストアドレスのリスト、エイリアス (ホスト名に対する別名) のリスト、ホスト名 (入力文字列) を格納しようとしていることがわかります。従って、bufferに必要なサイズは、順に、16バイト (unsigned char x 16個)、ポインタのサイズ x 2バイト、ポインタのサイズ、ホスト名 (入力文字列) の長さです。

そして、その前の★１でバッファの必要サイズsize_neededを計算しています。ここには載せていませんが、もし不足している場合はrealloc()で再割当てするか、異常終了するようになっています。

しかし、★１を見ると、エイリアス (ホスト名に対する別名) のリストを乗せるサイズ分が漏れてしまっています。その結果、サイズが小さいバッファを割り当ててしまいます。

CVE-2015-0235の修正

       size_needed = (sizeof (*host_addr)
-                    + sizeof (*h_addr_ptrs) + strlen (name) + 1);
+                    + sizeof (*h_addr_ptrs)
+                    + sizeof (*h_alias_ptr) + strlen (name) + 1);

「CVE-2015-0235の内容」で述べたとおり、エイリアス (ホスト名に対する別名) のリストを乗せるサイズ分が漏れてしまっていることが原因ですので、これを入れてあげることで正しいコードになり脆弱性はなくなります。

CVE-2015-0235への該当有無の判定

続いて、上記のURLで公開されている脆弱性の有無を判定するプログラムのソースコードを見てみましょう。

#include <netdb.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <errno.h>

#define CANARY "in_the_coal_mine"

struct {
  char buffer[1024];★３
  char canary[sizeof(CANARY)];
} temp = { "buffer", CANARY };★４

int main(void) {
  struct hostent resbuf;
  struct hostent *result;
  int herrno;
  int retval;

  /*** strlen (name) = size_needed - sizeof (*host_addr) - sizeof (*h_addr_ptrs) - 1; ***/
  size_t len = sizeof(temp.buffer) - 16*sizeof(unsigned char) - 2*sizeof(char *) - 1;★５
  char name[sizeof(temp.buffer)];
  memset(name, '0', len);
  name[len] = '\0';

  retval = gethostbyname_r(name, &resbuf, temp.buffer, sizeof(temp.buffer), &result, &herrno);

  if (strcmp(temp.canary, CANARY) != 0) {  ★６
    puts("vulnerable");
    exit(EXIT_SUCCESS);
  }
  if (retval == ERANGE) {
    puts("not vulnerable");
    exit(EXIT_SUCCESS);
  }
  puts("should not happen");
  exit(EXIT_FAILURE);
}

最初に着目すべき箇所は★５です。sizeof (temp.buffer) はバッファのサイズです。ここから逆算して、バッファのサイズが必要サイズぎりぎりになる (size_needed == suzeof (temp.buffer)) ようにホスト名 (入力文字列) のサイズを計算しています。もちろん、故意にバッファオーバーフローを発生させるためです。

★４では1024バイトのバッファの後ろにカナリア (バッファオーバーフローが発生するとこの部分が上書きされるため、バッファーオーバーフローを検知できる。"in_the_coal_mine"の内容に特別な意味はない) を置いています。gethostbyname_r ()を実行し、★６でカナリアの部分が書き換えられたかどうかチェックしています。書き換えられたのであれば、バッファオーバーフローが発生した、すなわち脆弱性ありということになります。

CVE-2015-0235の危険度

GHOSTは以前に発見されたOpenSSLの「HeartBleed」やBashの「ShellShock」とは違い、簡単に攻撃に利用できるものではないので、これらほど危険度は高くありません。だからと言って放置しても構わないわけではありませんが、落ち着いて対処すれば問題ないレベルです。

それにも関わらず、これだけ注目を集めているのは、非常に多くのプログラムが使用する関数で見つかった脆弱性であるゆえ、影響範囲が広大なことにあると言えるでしょう。

grepの-lオプションと-Lオプション

grepの-lオプションと-Lオプション。マニュアルを見ると、それぞれ以下のように説明されている。

-l, --files-with-matches
通常の出力はしません。その代わりに、grepを普通に実行した際に、何らかの検索結果を表示する
ような入力ファイルの名前を列挙します (訳注: すなわち、-lオプションを指定すると、-vオプシ
ョンを同時に指定しない場合は、パターンにマッチする文字列を含む行が存在するファイルの名前
を列挙するということです)。 個々のファイルに対する走査は、最初のマッチで終了します。 (-l
オプションは POSIX で規定されています)

-L, --files-without-match
通常の出力はしません。その代わりに、grepを普通に実行した際に、何の検索結果も表示しないよ
うな入力ファイルの名前を列挙します (訳注: すなわち、-Lオプションを指定すると、-vオプショ
ンを同時に指定しない場合は、パターンにマッチする文字列を含む行がまったく存在しないファイ
ルの名前を列挙するということです) 。個々のファイルに対する走査は、最初のマッチで終了しま
す。

-lと-Lは反対の意味を持つようだ。それでは、-Lと-lv、-lと-Lvは同じ意味なのか、という質問をときどき受けることがある。先に答えを言うと、4つは全て異なる意味を持つ。それぞれの動作を確認しよう。

grep -l pattern file1 file2 file3...

パターンにマッチする行が1行以上あるファイルの名前を表示する。

grep -lv pattern file1 file2 file3...

パターンにマッチしない行が1行以上あるファイルの名前を表示する。

grep -L pattern file1 file2 file3...

パターンにマッチする行が1行もないファイルの名前を表示する。言い換えると、全ての行がパターンにマッチしないファイルの名前を表示する。

grep -Lv pattern file1 file2 file3...

パターンにマッチしない行が1行もないファイルの名前を表示する。言い換えると、全ての行がパターンにマッチするファイルの名前を表示する。

$ cat file1
a
b
c
$ cat file2
a
a
a
$ cat file3
b
b
b
$ grep -l  a file1 file2 file3
file1
file2
$ grep -lv a file1 file2 file3
file1
file3
$ grep -L  a file1 file2 file3
file3
$ grep -Lv a file1 file2 file3
file2

ここまで読んでくださった方は、-l、-lv、-L、-Lvの違いをおわかりになられたでしょうか。

grabやagは本当にgrepよりも速い？

grepよりも高速なgrepの実装「grab」、grabよりも高速な「ag」。すなわち、grep < grab < ag。それを信じてgrepからgrabやagに移行する人がいるらしい。

ag (The Silver Searcher) の作者は、自らベンチマークを行いagがgrabよりも30倍高速であることを示したそうです。

そこで、agやgrabがどれくらい高速なのか試してみました。

grabのビルド

画面の右側にある「Download ZIP」よりソースコードをダウンロードし、コンパイルしました。

$ wget https://github.com/stealth/grab/archive/master.zip
$ unzip -q master.zip
$ cd grab-master
$ make

agのビルド

画面の右側にある「Download ZIP」よりソースコードをダウンロードし、コンパイルしました。

$ wget https://github.com/ggreer/the_silver_searcher/archive/master.zip
$ unzip -q master.zip
$ cd the_silver_searcher-master
$ ./build.sh

パフォーマンス比較

/etcディレクトリ配下を再帰的に検索してみました。公平に測定するため、Cロケールで比較しています。grepは Red Hat Enterprise Linux 6にバンドルされているgrep-2.6.3、grabとagは本稿執筆時点でのgitバージョンです。

$ export LANG=C
$ time -p /bin/grep -r http /etc >/dev/null
real 2.21
user 1.89
sys 0.31
$ time -p ./grab -r http /etc/ >/dev/null
real 0.08
user 0.05
sys 0.02
$ time -p ./ag http /etc/ >/dev/null
real 0.48
user 0.09
sys 0.67

言われているように、grabやagはgrep-2.6.3よりもかなり速いという結果になりました。

しかし、その後の調査で、grep-2.6.3だけはシンボリック・リンクを追跡することが判明しました。grep-2.11までは、-rと-Rは同じで、どちらもシンボリック・リンクを追跡する動作となっています。grep-2.12からは、grabやagと同様に-rはシンボリック・リンクを追跡しないように動作変更されています。

これでは不公平なので、grep-2.21で再検証してみました。

$ export LANG=C
$ time -p grep -r http /etc/ >/dev/null
real 0.04
user 0.01
sys 0.02

結果はgrepの勝利でした。続いて別のディレクトリ/usr/share/doc配下を検索してみましたが、やはりgrepが勝利しました。

$ time -p grep -r http /usr/share/doc/ >/dev/null
real 0.31
user 0.19
sys 0.11
$ time -p ./ag http /usr/share/doc/ >/dev/null
real 4.92
user 1.26
sys 7.33
$ time -p ../grab-master/grab -r http /usr/share/doc/ >/dev/null
real 0.74
user 0.52
sys 0.22

ということで、予想に反してgrep > grab > agとなりました。

基本正規表現 (BRE) と拡張正規表現 (ERE)

POSIX正規表現には、grepコマンドやsedコマンドで使用できる基本正規表現(BRE)と、egrepコマンドやawkコマンドで使用できる拡張正規表現(ERE)があります。一般的にはどういうわけかより多くの特殊文字を持つ正規表現が好まれているようで、BREよりもERE、EREよりもPerlの正規表現の方が人気があるように思います。しかし、BREとEREの違いをきっちりと理解されている人はそれほど多くないのではないかと思います。

BREとEREの違い

下記はBREとEREで使用できる正規表現の一覧です。

名前	BRE	ERE
Collation-related bracket symbols	[==] [::] [..]	[==] [::] [..]
Escaped characters	\	\
Bracket expression	[]	[]
Grouping	\(\) \n	() \n
Single-character duplication	* \{m,n\}	* + ? {m,n}
Concatenation
Anchoring	^ $	^ $
Alternation	(not supported)

見ていただければわかるように、EREで使えてBREで使えないのは、「+」、「?」、「|」の3つです。「+」は「{1,}」、「?」は「{0,1}」に置き換えることができるので、実際にEREで使えてBREで使えないのは、「|」のみです。

しかも、GNU grepやGNU sedでは、BREであっても「\|」を用いることができるので、ほとんど差はありません。

次に通常の文字として認識させたい場合にエスケープが必要となる特殊文字を示します。

BRE	.	[	\			*					^	$
ERE	.	[	\	(	)	*	+	?	{	|	^	$

BREよりもEREの方がかなり少ないですね。これがBREがEREよりも表現力に乏しいと思われている理由ではないでしょうか。

BREとEREの使い分け

ここまで読んでいただいて、BREもEREも機能面で大差はないことを理解していただけたかと思います。それでは、BREとEREをどのように使い分けるのがよいでしょうか。

コマンドラインで使用する場合

コマンドラインで使用する場合は、どちらかと言うとEREをおすすめします。以下にその理由を説明します。

例として、「abcまたはdef」をBREとEREで書くと、それぞれ下記のようになります。

BRE: abc\|def
ERE: abc|def

続いての例として、abcの3個から5個をBREとEREで書くと、それぞれ下記のようになります。

BRE: abc\{3,5\}
ERE: abc{3,5}

どちらの例においても、BREよりもEREの方がよりも短くなっています。そして、読みやすいと思います。それは、間違えにくいことでもあります。なので、コマンドラインで使用する場合は、どちらかと言うとBREよりもEREをおすすめします。

スクリプト内で使用する場合

スクリプト内で使用する場合は、BREをおすすめします。パターン内にシェル変数を使う場合、一般的には特殊文字をエスケープする必要がありますが、BREの場合はエスケープが必要なのは「.[\*^$」の6文字ですが、EREの場合は「.[\()*+?{|^$」の12文字もあります。エスケープ用のシェル関数を定義すればよいだけのことですが、文字数が少ない方がシンプルかつ高速です。

下記の例は、指定されたファイル「$FILE」 のパスが「$DIR/」 で始まる場合は、「$DIR/」 を取り除いて「$FILE」に書き出しています。sed_pattern_string()を通さなかったら、DIR 特殊文字や「/」 が入ってきた場合にうまく動作しません。

sed_pattern_string()
{
  echo "${1-}" | sed -e " \
    "'s/\\/\\\\/g; s/\./\\\./g; s/\*/\\\*/g; s/\^/\\\^/g;'" \
    "'s/\$/\\\$/g; s/\[/\\\[/g; s/\]/\\\]/g; s/\//\\\//g'
}

DIR=$1
shift

DIR_SED=`sed_pattern_string "$DIR/"`

for FILE
do
  test -f "$SRCFILE" || continue
  echo "$FILE" | sed -e "s/^$DIR_SED//" >>"$FILE"
done

まもなく GNU grep 2.21 リリース

GNU grep 2.21のリリースが秒読み段階に入りました。

GNU grep 2.21 では、特筆すべきものはないものの、いくつかの点で機能やパフォーマンスが改善されています。それでは、主な改善点を見ていくことにしましょう。

スパースファイルに対する改善

スパースファイルとは

プログラムがクラッシュした際に生成されるcoreファイルはメモリイメージを書き出したものですが、プロセスがマップされていない部分は書き出されません。また、仮想マシンでは巨大な仮想ディスクを作成しても全ての領域が直ぐに使用されるわけではないでしょう。これらのような使用されていない領域にまで前もってディスク上の領域を割り当てるのは無駄といえます。

このようなニーズに答えるため、XFSやReiserFSではスパースファイルをサポートしています。スパースファイルとはホールを含むファイルです。ホールとはファイルの中でディスク上の領域が割り当てらていない領域であり、read() すると 0 が埋められているように見えます。ファイルの中で直ぐに使用しない部分をホールにすることで、write () されるまでディスク上の領域の割り当てを遅延させることができ、ディスクを有効活用できます。

スパースファイルに対する改善

GNU grep 2.21 では、ファイルの中のホールを読み飛ばすことで、スパースファイルに対するパフォーマンスが改善しています。

$ dd if=/dev/zero bs=32M seek=32 count=0 of=m
$ time -p grep -z ^a$ ~/m
  grep-2.20: real 4.13    user 0.95     sys 0.87
  grep-2.21: real 0.12    user 0.00     sys 0.04

GNU grep 2.21 では、1GB ものファイルに対して、一瞬で結果が返されています。

パターンの最初の部分にさえマッチしないデータに対する改善

DFA*1を使った検索では、状態毎の遷移テーブル*2をあらかじめ作成しておき*3、入力データから 1 文字受け取って状態が遷移するたびに遷移テーブルを新しい状態のものに差し替えます。

ところで、パターンの最初の部分にさえマッチしない間は、入力データから何文字受け取ろうとも初期状態 0 です。従来のリリースでは、そのような場合でも遷移テーブルを差し替えていました。入力データから 1 文字受け取るたびに状態 0 の遷移テーブルを状態 0 の遷移テーブルに差し替えていました。GNU grep 2.21 では、パターンの最初の部分にさえマッチしない間は、状態 0 の遷移テーブルを差し替えることなく使用し続けるように改善されています。

$ yes jjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjj | head -10000000 >k
$ env LC_ALL=C grep '\(a\|b\)' k
  grep-2.20: real 0.96    user 0.85     sys 0.10
  grep-2.21: real 0.46    user 0.35     sys 0.10

$ yes j | head -100000000 >l
$ env LC_ALL=C grep '\(a\|b\)' l
  grep-2.20: real 0.64    user 0.60     sys 0.03
  grep-2.21: real 0.54    user 0.49     sys 0.04

-P オプションに対する改善

GNU grep では、-P オプションを使用することで PCRE (Perl Compatible Regular Expression) ライブラリを使用した検索が可能になっています。ところが、UTF-8 ロケールで -P オプションを使用すると、PCRE ライブラリによって事前に入力データが正しい UTF-8 シーケンスかどうかチェックする処理が実行され、不正な UTF-8 シーケンスが見つかるとそこでアボートしていました。

そこで、GNU grep 2.16 では、PCRE ライブラリの関数をコールする際に PCRE_NO_UTF8_CHECK オプション*4を指定するように変更されました。ところが、このオプションが指定された状態で不正な UTF-8 シーケンスを含む入力データを指定するとクラッシュする可能性があることが判明しました。そのため、GNU grep 2.19 では PCRE_NO_UTF8_CHECK オプションを指定しないように戻された上で、入力データに不正な UTF-8 シーケンスが含まれていた場合にはアボートするのではなくエラーを返すように変更されました。

GNU grep 2.21 では、入力データの中に不正な UTF-8 シーケンスが含まれていてもそれを検出しスキップして処理を継続できるように改善されました。この改善により、UTF-8 ロケールで -P オプションを指定した場合でもバイナリファイルを検索対象に含めることができるようになりました。

$ env LC_ALL=ja_JP.utf8 src/grep -P a src/grep
  grep-2.15: Aborted (core dumped)
  grep-2.20: src/grep: invalid UTF-8 byte sequence in input
  grep-2.21: Binary file src/grep matches

その他の主な改善

非常に長いパターンに対する改善

GNU grep では、最初にパターンから固定文字列を取り出し、それを使ってマッチする可能性がある行を絞り込みます。従来のリリースでは、パターンから固定文字列を取り出す処理のロジックに問題があり、パターンが非常に長い場合には多くのメモリを消費していました。

以下にテストケースを示しますが、結果は省略します。

$ echo '' | src/grep -f /usr/share/dict/linux.words

非UTF-8マルチバイトロケールで「^」と「\|」を含むパターンに対する結果不正の修正

EUC-JPで「\244\263」は「こ」であり、「\263\244」は「海」です。「\263\244\263\244」は「\244\263」が含まれているものの「海海」と解釈されるべきです。従って、下記はマッチするべきではありませんが、従来のリリースではマルチバイト文字の境界を正しく認識できずマッチしていました。

$ pattern=$(printf '^x\|\244\263')
$ printf '\263\244\263\244\n' | env LC_ALL=ja_JP.eucJP src/grep "$pattern"

*1:DFA は、Boyer-Moore 法では処理できないやや複雑なパターンを処理します。

*2:次の状態に遷移するためのテーブルです。例えば、次に a を受け取ったら状態 1 に、b を受け取ったら状態 2 に、それ以外の文字を受け取ったら初期状態 0 に遷移といった内容が記録されています。

*3:ある状態の遷移テーブルは、初めてその状態の遷移テーブルが必要になった時点で作成されます。

*4:PCRE_NO_UTF8_CHECK オプションを指定すると、入力データに不正な UTF-8 シーケンスが含まれていないかを事前にチェックする処理がスキップされます。

GNU sedのパフォーマンス

GNU grepとGNU awk (Gawk) のパフォーマンス向上についてお話したので、今度はGNU sedを見てみましょう。

GNU sed 4.2.1

Red Hat Enterprise Linux 6にバンドルされているGNU sed 4.2.1でテストしてみました。

$ yes jjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjj | head -10000000 >../k

$ time -p env LC_ALL=C sed -ne '/a\|b/p' ../k
real 2.22
user 2.17
sys 0.05

$ time -p env LC_ALL=ja_JP.eucJP sed -ne '/a\|b/p' ../k
real 11.91
user 11.82
sys 0.08

$ time -p env LC_ALL=C gawk '/a|b/ { print }' ../k
real 2.65
user 2.58
sys 0.07

$ time -p env LC_ALL=ja_JP.eucJP gawk '/a|b/ { print }' ../k
real 13.96
user 13.86
sys 0.09

同じくRed Hat Enterprise Linux 6にバンドルされているGawk 3.1.7よりも高速であることがわかります。

GNU sed 4.2.2

執筆時点の最新版GNU sed 4.2.2 (2012-12-12) リリースでテストしてみました。

$ time -p env LC_ALL=C gawk '/a|b/ { print }' ../k
real 2.20
user 2.13
sys 0.07

$ time -p env LC_ALL=ja_JP.eucJP gawk '/a|b/ { print }' ../k
real 11.89
user 11.81
sys 0.07

$ time -p env LC_ALL=C ./gawk '/a|b/ { print }' ../k
real 2.29
user 2.22
sys 0.07

$ time -p env LC_ALL=ja_JP.eucJP ./gawk '/a|b/ { print }' ../k
real 5.37
user 5.28
sys 0.08

ということで、Red Hat Enterprise Linux 6にバンドルされているGNU sed 4.2.1とほとんど変わりませんでした。なので、最新版対決ではパフォーマンスが向上したGNU awkに軍配です。

GNU sed開発中版 (Git)

GNU sed 4.2.2以降の状況ですが、GNU sed 4.2.2のリリースと同時にGNU sedの作者の1人であるPaolo Bonzini氏がGNUの方針に賛同できないことを理由にメンテナーを辞任してしまいました。そのことが影響しているのか、最近はほとんど更新されておらず、メーリングリストにおける議論も活発ではありません。

まとめと解説

GNU sed < GNU awk < GNU grepでした。内部的な話をすると、GNU sedは「regex」のみ使用、GNU awkは「regex」およびそれよりも対応しているパターンが少ないものの高速な「dfa」を使用、GNU grepは「regex」および「dfa」に加えて固定文字列を超高速で検索する「KWset」を使用しています。なので、パフォーマンスにおいてGNU sed < GNU awk < GNU grepとなるのは当然といえます。

ちなみに、私見ですがGNU sed、GNU awk、GNU grepの中では、GNU sedのソースコードがいちばんきれいで読みやすいと思います。