世界を動かす技術を、日本語で。

D言語でASN.1コンパイラを作るのに1年を費やしました

概要

  • ASN.1 の複雑さと実装体験に関する技術的な雑記
  • D言語 でのASN.1コンパイラ(dasn1)の開発経緯
  • ASN.1規格(x.680~x.683)の要点と課題
  • ASN.1の制約・バージョン管理・エンコーディング方式の特徴
  • 実装時のD言語特有の工夫や苦労話

ASN.1とD言語によるコンパイラ開発雑記

  • Juptune というD言語製の非同期I/Oフレームワーク開発の一環
    • TLS実装 のためにx.509証明書対応が必要
    • x.509証明書の基盤である ASN.1 DERエンコーディング 対応が目的
  • ASN.1 は1980年代から使われている複雑なデータ記述言語
    • protobufの超強化版 とも呼べる仕様
    • ノーテーション(x.680~x.683)と複数のエンコーディング(BER, CER, DER, PER, XER, JER等)で構成
  • ASN.1ノーテーション例 (RFC 5280より抜粋)
    • 強力なバージョニング
    • ビットフラグ、構造体、制約付き型、OBJECT IDENTIFIERの定義方法
  • 代表的なエンコーディング
    • BER :無限長データ対応の基本バイナリ形式
    • CER :BERのサブセット、限定的な用途
    • DER :暗号用途で広く使われる一意なバイナリエンコーディング
    • PER/OER :制約を活用した効率的なバイナリエンコーディング
    • XER/JER :XML/JSONベースの表現
  • ASN.1仕様の複雑さ
    • 基本ノーテーション(x.680)に加え、拡張仕様(x.681~x.683)が存在
    • x.680 :実装は比較的容易だが、細かい変換規則や拡張との兼ね合いが難点
    • x.681 :情報クラスオブジェクト。独自イニシャライザ構文など高度な機能
    • x.682 :テーブル制約。仕様が難解で未実装
    • x.683 :テンプレート型(パラメタライズド型)の定義が可能
  • ASN.1の魅力
    • 強力な 制約システム (型・フィールドへの範囲やサイズ指定)
    • バージョン管理 や拡張性の高さ
    • 多様なエンコーディングの選択肢
  • D言語による実装の工夫
    • 静的import・完全修飾名 による柔軟な名前解決
    • mixinテンプレート によるASTノード生成
    • alias thisunittestバージョン によるテスト容易化
    • メタプログラミング 活用でシンプルなコンパイラ設計
  • 実装上の課題・痛点
    • 仕様書の情報探しの難しさ
    • 制約実装の多重化
    • ANY DEFINED BY など歴史的な構文のサポート
    • IRノードの不変性 維持の難しさ
    • コンパイラ開発の地道な作業量

ASN.1とは何か

  • ASN.1 は1980年代後半から標準化されたデータ記述言語
    • x.680 :基本ノーテーション
    • x.681~x.683 :拡張機能(情報クラス、テーブル制約、テンプレート型など)
  • ノーテーション でデータ構造を定義し、各種エンコーディングでバイナリ化
  • 用途例 :TLS証明書(x.509)、各種通信プロトコル

ASN.1エンコーディング方式

  • BER :タグ・長さ・値(TLV)形式、柔軟な長さ対応
  • CER/DER :BERのサブセット、暗号用途でDERが主流
  • PER/OER :制約情報を活用した高効率エンコーディング
  • XER/JER :XML/JSONでの表現

ASN.1の仕様と拡張

  • x.680 :基本構文、制約、OBJECT IDENTIFIER管理
  • x.681 :情報クラスとカスタムイニシャライザ
  • x.682 :テーブル制約(複雑で未実装)
  • x.683 :型・値のテンプレート化

ASN.1の制約システム

  • 型・フィールドに範囲やサイズ等の制約指定が可能
    • 例:INTEGER (0..255)UTF8String (SIZE (8..32))
  • 複数制約の組合わせ(UNION・INTERSECTION)対応
  • 他言語では珍しい高度な制約機能

ASN.1のバージョン管理

  • OBJECT IDENTIFIER による一意なモジュール識別・バージョニング
  • 拡張性後方互換性 の両立

D言語によるASN.1実装の特徴

  • 静的import完全修飾名 で柔軟なモジュール設計
  • mixinテンプレート でASTノードを効率的に生成
  • メタプログラミング でエラー検出やAPI自然化
  • alias thisunittestwith() によるテスト容易化
  • コンパイラのシンプル化 を目指した設計

実装時の課題・苦労

  • 仕様書の情報が見つけにくい
  • 制約の多重実装 (パーサ・型システム・エンコーダでそれぞれ必要)
  • 歴史的な構文(ANY DEFINED BY等) の扱い
  • IRノードの不変性 を保つ設計の難しさ
  • コンパイラ実装の地道さ と精神的負担

結論

  • ASN.1 は複雑だが、学ぶ価値と面白さがある技術
  • D言語 の特性を活かした実装は多くの気付きと成長の機会
  • コンパイラ開発 は困難だが、現代の基盤技術を理解する上で貴重な経験

Hackerたちの意見

要するに、ASN.1について少し、Dについて少し、コンパイラについても少し話したいと思ったんだけど、まとまった形が思いつかなかったんだ。だから、半ば関連のあることを適当にまとめて、これをブログ記事って呼んじゃおうと思った。あらかじめごめんね、あんまり質が良くないのは認めるよ。でも、こんなにたくさんのことを短く話すのは本当に難しいんだ(特に、もっと深く話したかったことをたくさん忘れちゃったし :()。

Asn.1データ(そう、証明書ね)を扱ったことがある者として、あなたが経験した苦労には完全に共感します。あの6ヶ月間のAnsible HRのコメントには思わず笑っちゃいましたよ :D

心配しないで、自分のブログなんだから、自分のやり方でいいよ。続けてね、それが自分を満たしてくれるなら。

Dについて話してると、もしかしたらウォルター・ブライトを召喚してるかもね。俺のお気に入りの言語の一つで、もっと多くの企業が使ってほしいんだけど。残念ながら、業界ではGoやRustの方がずっと人気なんだよね。

あなたの投稿、すごく楽しんだよ。書いてくれてありがとう。Dが大好きだけど、残念ながら数年触ってないんだ。パーサーを書いたり、プロトコルを実装した経験もあるよ。

小さな指摘だけど、あなたの交差点の例は、意図した通りにはなってないと思う。もしかしたら「PER-visibility」とかの微妙な違いがあるかもしれないけど、少なくとも集合論的には、LegacyFlags2 ::= INTEGER (0 | 2 ^ 4..8) -- 記事にある通りは、LegacyFlags2 ::= INTEGER (0) -- ただ一つの値が許可されるっていうのと全く同じだよ。標準的な数学的表記を使って優先順位を明示すると、{0} ∪ ({2} ∩ {4,5,6,7,8}) = {0} ∪ ∅ = {0} になるから。

少し前にSwiftでASN.1コンパイラを作ったんだ(swift-asn1じゃなくて、俺のはCodableを使ったやつ)。HeimdalのJSONコンパイラを使ったおかげで、ASN.1をもっと解析しやすいJSONのASTに変換できて、時間を節約できたよ。 [1] https://github.com/PADL/ASN1Codable [2] https://github.com/heimdal/heimdal/tree/master/lib/asn1

その2つのプロジェクトについては聞いたことがなかったけど、libasn1のREADMEにちょっとしたASN.1への軽蔑が見え隠れしてるのが好きだな。

「ASN.1をもっとパースしやすいJSON ASTに変換できる」 傷ついた人のサインだね、他の人にも同じ痛みを感じてほしくないっていう :D

Dが大好きなんだ、私のお気に入りのプログラミング言語の一つだよ。今、Raylibだけを依存関係にして、ゼロからVim風のテキストエディタを作り始めたんだけど、思ったよりも進んで、テストカバレッジもかなり良かったことに驚いてる。 私がDの好きな機能はこれだね:

  • ユニットテストをどこにでも書けるから、メソッドや関数のすぐ後にユニットテストを書くことが多い。
  • version(unittest) {}のようなブロックがあるおかげで、テスト用にコンパイルすべきものを簡単に除外/含められる。
  • 列挙型、共用体、アサート、契約プログラミングも全部素晴らしい。

Dを学ぶのに苦労したことはあまりないかな。やりたいことはドキュメントで見つけられるし、ChatGPTに聞けば、いつも素敵な方法が見つかるんだ。

Dは私にとってちょっと複雑な話題なんだ。哲学的な観点や言語設計の面から見ると、いろんな要素が揃ってる。もしいくつかのことが違っていたら、すごく人気が出る可能性もあったと思う。言語のツールやライブラリのエコシステムが、今のRustやGoみたいに充実していたら、本当に強力な言語になっていたはずだよ。

OMG ASN.1。これを見逃した人のために、インターネットの成長過程で面白いことがあったんだ。あの頃、人々はIETFを通じてプロトコルを進化させていた。今頼りにしているもののほとんどは、その時に生まれたものなんだよ。ある日、メールがあって、FTPがあって、TCPがあって、バン・ジェイコブソンのTCPの改良もあった。あの時、企業の人たちはインターネットに全然注目していなかった。学者たちやIETFが、私が見た限りでは主な開発者だったね。

でも、ある日企業の世界が「これでお金が稼げるかも」と気づいたんだ。でも、プロトコルの開発プロセスは企業文化とはまったく理解できない(そして互換性もない)ものだった。TCPは明らかに混乱していて、DNSのようなプロトコルもめちゃくちゃだった。企業の視点から見るとね。そこでプロトコル戦争が始まったんだよ。https://en.wikipedia.org/wiki/Protocol_Wars

ASN.1がその戦争の産物なのか、単に企業のメンタリティの産物なのかは分からないけど、企業の世界と学問の世界の違いを示す強力な例になっている。戦争の残骸はあちこちに散らばっているよ。もしX.somethingプロトコルを見かけたら、それはその遺物の一つかもしれない。いくつかのX.系は採用されて役に立ったけど、夢に出てくるようなものもあった。これは古代の歴史で、今はほぼ企業の視点から語られているけど、企業の思考プロセスがIETFや学問の代替手段ほど効果的ではないことを示唆しているんだ。

一つはレシピ文化のようなもので、レシピを書いてみんながそれに従って、みんな幸せになる。もう一つは機能文化のようなもので、パンを作って食べられれば幸せになる。パンの味が良くない時は、直すんだ。今アメリカで一般的に手に入るパンの種類を考えると、レシピ思考やレシピ文化、企業文化についていくつかの結論を引き出せるかもしれない。これをAIのような新しいものにも当てはめることができるかもしれないし、できないかもしれないね。

この前、パートナーと「花嫁の父」を再視聴してたんだけど(ダイアン・キートン、安らかに)、最初の親の会議で、婚約者が自分のことを通信コンサルタントだって言って、X.25ネットワークの設置をやってるって説明してたんだ。映画を一時停止して、パートナーにインターネットがどれだけ危うくなってたかを説明しなきゃいけなかったよ。「CN=wikipedia, OU=org, C=US」みたいなアドレスのサイトに行く羽目になってたかもしれないし、他にもひどいプロトコルがあったんだろうね。彼女は、俺がどれだけ怒ってて、動揺してたかに驚いてたみたい!それはひどいことになってたよ!かわいそうに!

「OMG ASN.1」っていうのが次のバンド名になる予定。

プロトコル戦争は、インターネットの初期の「クソ化」の物語でもあるんだ。すでに知られている問題に対する解決策を進めようとしたけど、ベンダー側の投資が必要になるから、無料で提供されているソフトウェアを使い続けることになった。DoDがPDP-10の代替を急いで求めてたからね。(ちょっと誇張してるけど)多くの問題は、ISOの基準が既知の問題を解決せずに立ち往生してしまったり、偶発的な一時的解決策が長期的なものになってしまったことからも来てる。一方でIETFのプロトコルは「後で直すから」と進んでいったけど、結局は基盤が硬直化してしまった。教訓の一つは、新しいプロトコルにはランダム性を加えることで、単純な実装が初日から失敗するようにすることだね。それから、1990年にC用の主要なASN.1実装がひどかったっていう偶発的なこともあった(OpenSSLがさらに悪化させた伝統だと思うし、X.509に触ってるほとんどの人にはそう思われてる)。ASN.1のエンコーディングがCPUにバレルシフターがないせいで遅いっていう不満もあったし(PERに何か関係してるんじゃないかな)。

ちょっと混乱してる。君の話の多くは正しいけど、主要なプレイヤー(ITUとISO)を「企業」に置き換えてるよね。ITUが電話文化を代表しているのは確かだけど、企業主義全体を代表しているわけじゃない。別の「プロトコル戦争」もあったけど、それは確かに冷戦だった。90年代後半からのインターネット企業は、標準化の努力にもう関心を持たなくなったんだ。既存のプロトコルを使って、その意図を歪めることができた。一般の人が使いやすい製品を作るために、普遍的な到達可能性の目標を放棄して「機能」を追加することもできた。要するに、何でも受け入れられるものを探してた。これに関しての象徴的な例がIPv6やマルチキャストプロトコルの開発だった。IETFは、過去20年間のように解決策を見つけてネットワークに展開されるだろうと考えていたんだけど、ルールが変わってしまった。インターネットはもう政府や学術機関が運営しているわけじゃなくて、新しいチームは気にしなくなってしまった。2つの戦争があった。IETFは最初の戦争を粗い合意と動くコードで勝ったけど、ほぼ同じ理由で2つ目は負けた。

普通、何かの標準を実装する時は、計画した時間の20%で機能の80%が得られるって言えるけど、ASN.1の場合、残りの20%が人生の残りを占めることもあるからね。

俺もいろんな文脈でこれを扱ったことがあるよ… パーサーがない深く埋め込まれたシステムとか、ちゃんとしたものが合わないところでね。だから、基本的なパーシングと生成を手書きしたことも何回かある。あ、非準拠の実装もあるよ。例えば、一部のパスポート(そう、チップ付きのパスポートはASN.1をたくさん使ってる)では、大きな整数の取り扱いが間違ってることもあるんだ(最小の2の補数であるべきなのに、固定の非補数フォーマットが0x02 INTEGER型に引きずり込まれてることもあった... 一部のライブラリにはそれに対処するための特別な非準拠パーシングモードがある)。

ASN.1のウィキペディアの項目によると、ASN.1をサポートするツールのほとんどは以下のことをするらしいよ:1) ASN.1ファイルをパースする、2) プログラミング言語(CやC++など)で同等の宣言を生成する、3) 前の宣言に基づいてエンコーディングとデコーディング関数を生成する。これらの作業は、データエンジニアリングプロセスやライフサイクルの一部らしいね。21世紀初頭の頃、Pythonはただの解釈型の汎用プログラミング言語の一つで、ウェブ用(PHP)でもなければ、コマンドツール用(TCL)でも、システム用(C/C++)でも、データ処理用(Perl)でも、数値計算用(Matlab/Fortran)でも、統計用(R)でもなかった。DもおそらくPythonと同じような軌道を辿るだろうけど、本当に特別なキラーアプリケーションが必要だね。それがDを前面に押し出す瞬間になると思う。リアルタイムデータのストリーミング、処理、エンジニアリングがDのキラーユーティリティになって、Dはデータのためのものだってことを定義できると思ってるよ。

DはおそらくPythonのような軌道を辿るだろう。 その「お前」みたいなやつになってしまうけど、Dの軌道は今やほぼ固定されてるように見える。一方でPythonは機械学習で再生された。

すごく面白い記事だね。俺もASN.1コンパイラに何時間もハッキングして、X.681、X.682、X.683の機能を追加して、1回のコーデック呼び出しで全体の証明書を再帰的にデコードできるようにしたことがある。だから、似たような作業についての投稿を見るのはすごく嬉しい!ASN.1は本当に素晴らしい。たくさんの批判を受けてるけど、それは全然正当じゃない。ASN.1は単なる構文やエンコーディングルールのセットじゃなくて、強力な型システムなんだ。

トルコのことわざに「人間はこれを使う、人間だ!」っていうのがあって、これはその物が異常すぎて人間のために作られているように見えないことを示すんだ。動詞は文脈によって変わるよ。例えば、食べ物を作りすぎたら、動詞は「食べる」になる。これってデザインにとって素晴らしいモットーだと思う。ゲーム・オブ・スローンズのセリフ「判決を下す者が剣を振るうべきだ」って覚えてる?これも仕様に適用されるべきだと思う。仕様を考えた人は、その仕様のパーサーを開発する最初の責任者であるべきだ。動作するパーサーコードとユニットテストがなければ、仕様は承認されない。こういう要求があれば、仕様が実際に改善されるかもしれない。

わお、俺はたった一つの小さなASN.1を一つの値(署名一つ)でパースする必要があったんだけど、ASN.1には仕様があって、それを元にパーサーを生成できるって知らなかった。だから、その特定の256ビットのために自分で解決する羽目になった。でも、セキュリティ関連のものには過剰に仕様を定義する方がいいと思う。JSONやXMLはあまりにも曖昧で、パーサーが予測できないからね。