バイナリエンコーダー/デコーダージェネレーター
開発駆動コース 仲山ゼミ 藤岡航介

brgen

仕様だけでわからないから
OSSのソースコードとか見ても結構
エンコード/デコード部分が分散していたりしてわかりにくい…

手書きの解析/生成コード
分かりづらいDRY原則にも

違反だし…

手書きで
エンコード
デコード
解析/生成処理
書くの構造体定義/
エンコード/
DRY原則
デコード etc…で同じ定義についてを何回も何回も…
自作TCP/IPプロトコルとかはよくあるが、プロトコルで使われるフォーマットが増えていくとどんどん敷居が高くなっていく…
SecHack365での紆余曲折

めんどくさいhttps://www.rfc-editor.org/rfc/rfc791
https://github.com/msgpack/msgpack/blob/master/spec.md
https://www.rfc-editor.org/rfc/rfc8446
https://www.rfc-editor.org/rfc/rfc9000.html
https://www.rfc-editor.org/rfc/rfc9221.html

量が多くてつらい!

いろんな形式があって混乱する!
昔の人(プログラマー)

コードジェネレーター
少量のソースコードから多量の定型的なソースコードを生成するツール
例: Web - HTML、CSS
gRPC – Protocol Buffers
RDB - SQL
ある特定の分野に特化した プログラミング言語 GitHub Actions Workflow File

DSL(ドメイン固有言語)

定義言語のサンプル

format HeaderChunk:magic :“MThd“ ← マジックナンバー型
length : ub32(6)format_type : ub16
track_count : ub16
time_division_flag : ub1
match time_division_flag:
0 => time_division : ub15
1 => time_division : SMPTE

enum TLSVersion::u16
invalid = 0
tls12 = 0x0303
format TLSRecord:
type :ContentType
legacy_version :TLSVersion
length :u16
fragment :[length]u8

format SMPTE:
frames_per_second : ub7
ticks_per_frame : ub8

format TLSInnerPlaintext:
content :[..]u8
type :ContentTypezeros_length_of_padding :u32

↑Standard MIDI File(一部)format TLSCipherText:
opaque_type :ContentType(ContentType.application_data)
legacy_record_version :TLSVersion(TLSVersion.tls12)
length :u16
encrypted_record :[length]u8↑TLS(一部)→ELF(一部)←サンプル一覧からコードを生成する

コードジェネレーター

バイナリフォーマット定義言語
書きやすい– 簡単に書けて読みやすい

十分な表現力–プロトコル/ファイルフォーマットを十分表現できる

magic :"¥177ELF"
class :CPUClass
class == CPUClass._32 ||class == CPUClass._64
endian :Endian
endian == Endian.LittleEndian ||endian == Endian.BigEndian
input.endian =endian == Endian.LittleEndian ?
config.endian.little :config.endian.big
version :u8
version == 1
osabi :u8
osabi == 0
abiversion :u8
abiversion == 0
padding :[7]u8
objtype :u16
machine :u16
version2 :u32
if class == CPUClass._32:
entry :u32
program_header_offset :u32
section_header_offset :u32
else:
entry :u64
program_header_offset :u64
section_header_offset :u64
flags :u32
header_size :u16
program_header_entry_size :u16
program_header_entry_count :u16
section_header_entry_size :u16
section_header_entry_count :u16
section_header_name_index :u16

enum ContentType::u8
invalid = 0change_cipher_spec = 20
alert = 21
handshake = 22
application_data = 23

任意のバイナリフォーマットの Before SecHack365: QUICクライアントを実装する～6月: QUICサーバーを作ろうとするがプレッシャーを感じて病みだす
バイナリエンコーダー/デコーダージェネレーターにテーマをエンコード/デコードルールを 7月～8月:変更。プロトタイプを作る。競合事例を調べ始めてまた病みだす。
8月～: いろいろなバイナリフォーマットのパーサを書いてみたりする。
表せるDSL
サンプルを書き始める。
を作ればいいんだ!

バイナリフォーマット定義言語の書きやすさと十分な表現力を持っていることを示すため、既存のバイナリフォーマットを表現するサンプルたちを作成しました。
ネットワーク・プロトコルのフォーマットやファイルフォーマットなどのサンプ
ルがあります。これらのサンプルは定義言語の仕様を決めたり、定義ファイル
パーサーのバグを検出したりするのに大いに役立ちました。また、WebPlaygroundformat ELFFileHeader:ではこれらのサンプルを読み込むことができます。
format StandardMidiFile:header: HeaderChunk
tracks: [..]TrackChunk

Don’t Repeat Yourselfの略。
同じ定義のことを繰り返し書くなというプログラミングをする上での格言/設計思想

operation == Operation.Request || operation == Operation.Reply
source_hardware_address :[hardware_len]u8
source_protocol_address :[protocol_len]u8
target_hardware_address :[hardware_len]u8
target_protocol_address :[protocol_len]u8

WebPlaygroundbrgenの定義言語を書くのを支援するLSPサーバーを書きました。
これは当初はバイナリエンコーダー/デコーダージェネレーターの開発に行き詰まり、その気分転換として開発を始めました。シンタックスハイ
ライトやホバーの表示などによってより定義言語の意味がわかりやすくなりました。LSPサーバーが定義言語パーサーを頻繁に呼び出し、また中途半端な入力がたくさん入力されるため定義言語パーサーのデバッグが進むという思わぬ効果もありました。また、このLSPサーバー用につくったAST解析ツールはWebPlaygroundでも生かされています。

DSL
バイナリフォーマット
コードジェネレーター

サイズ(可変長時はdynamic表記)

Microsoftが提唱した言語サーバー(シンタックスハイライ
トや定義検索などの機能を提供)とエディタ間の通信規約。
これに従うことで同じ言語サーバーを異なるエディタで使用することができる。

定義言語パーサー/型解析

仕様書などのバイナリフォーマット表現はそれぞれのプロトコルなどの表現に特化しているといbrgenの開発で最も開発に時間をかけた部分にして最も地味な部分です。
う面もありいろいろ種類がありますが、その表記はバラバラです。またフィールド間の関係につC++で記述されています。定義言語パーサーは定義言語の構文解析と意味解析(型解
いてもフォーマット図ではなく文章で仕様が書かれていたりと親切とは言い難いものがあります。 析など)を行いその結果得られたASTをJSON形式で出力します。
さらに図のような形だとプログラムで読み込むのが難しかったり気軽に変更したりできません。
現状、定義言語パーサーの実装=フォーマット定義言語の仕様となっており、またこ
そこで私は以上のような目標を設定してDSLを開発しました。
れによって解析をしてASTに落とし込まないことにはエンコーダー/デコーダージェ
ネレーターの方にも反映できないため、かなりの時間をこれに費やしました。
enum Operation::u16
私はこれのことをずっとパーサーと呼んでいましたが最近になってパーサーと言う
Python風インデント構文
Request = 1には高級すぎると思い始めたためなんと呼べばいいのか迷い中です。
プログラミング言語に近い
Reply = 2
形式
AST(Abstract Syntax Tree/抽象構文木) ↓出力されるJSONの中身
format ArpPacket:
長さ指定により、
プログラミング言語などのソースコードを本質だけ取り出した木構造にしhardware_type :u16たもの。本質だけというのは例えばスペースや改行と言った重要ではない
どのフィールドがprotocol_type :u16
情報は省略されていたりするということです。
どのフィールドの長さだと(コメントやかっこも省略したりするがbrgenのASTでは省略されていない)
hardware_len :u8
protocol_len :u8
いうのが直感的にわかる。
↓JSONとASTの変換の仕組み
operation :Operation
制約式も付けられる

LSPサーバー/VSCode拡張

LSP(Language Server Protocol)

9月～: 現在の定義言語パーサーを書き始める。
ジェネレータードライバーを作り始める。LSPサーバーを作り始める。
json2cppを作り始める。json2goを作り始める。
10月～: ASTコードジェネレーターを作り始める。
WebPlaygroundを作り始める。
11月～: json2cpp2を作り始める
12月: QUICについての同人誌を書く/C103で販売する。
1月～: brgenのドキュメントを書き始める。

ビットアラインメント
依存構造体/enum

Webブラウザ上でbrgenを試せるWebPlaygroundを開発しました。
定義言語パーサーとバイナリエンコーダー/デコーダージェネレーターを
WebAssemblyに変換して動かすことで、GETする以外すべてローカルで完結して動きます。またGitHub Pagesを使ってホスティングしており、サーバー管理の必要などはなく(下手にサーバー建てるよりは)安全です。エディタにはMonaco Editorを使用しています。
また、LSPサーバーと共通のロジックを使っており、LSPサーバーで表示されるのと同じようなシンタックスハイライトやエラー表示、ホバーなどが使えます。
GitHub Actionsを使ってmainブランチの最新版をデプロイしているので新機能が実装されたらすぐ使えます。
https://on-keyday.github.io/brgenジェネレータードライバー
CLIの定義言語パーサーとバイナリエンコーダー/デコーダージェネレーターの橋渡しをするツールです。Go言語で書かれています。構成ファイルを読み込んで入力に従って定義ファイルパーサーを呼び出しその出力結果をバイナリエン
コーダー/デコーダージェネレーターに渡しさらにその出力結果をファイルに保存します。またgoroutineを使い並列/並行にファイルを処理します。
ちなみにこのジェネレータドライバーの名前はbrgenとなっています。
例えるならgcc(コンパイラドライバ)とcc1(コンパイラ),ld(リンカー)の関係です。
brgen.json(構成ファイル)
src2json(定義ファイルパーサー)

サンプルをロードする↑

バイナリエンコーダー/
デコーダージェネレーター(複雑さはgccが明らかに上だけどね){“src2json”: “./tool/src2json”, ← 定義ファイルパーサーのPATH“input_dir”: [“./example/”, “./example/gen_step/”], ← 入力ディレクトリ
“suffix”: “.bgn”, ← 入力ファイルのサフィックス"warnings": {"disable_untyped": true,"disable_unused": true},
"test_info_output": "./ignore/example/test_info.json","output": [{“generator”: “./tool/json2cpp2”, ← バイナリエンコーダー/デコーダージェネレーター“output_dir”: “./ignore/example/cpp2/”, ← 出力先ディレクトリ
"args": ["--add-line-map", "--use-error", "--use-overflow-check"]
},
………

brgen

json2cpp(バイナリエンコーダー/デコーダージェネレーターfor C++)

brgenの２つ目のコアとなるバイナリエンコーダーデコーダージェネレーター。現時点ではC++/Go言語向けの2種類を提供しています。C++向けはC++で、Go言語向けはGo言語で書かれています。実のところ一番本質(タイトルにもなっていますね)にも関わらずかけた時間が一番少ないところだったりします。ジェネレーターは当初brgenのASTからさらに中間表現に落とし込んで生成しようとしたのですが、複数言語対応しようとしたときにいくつもの言語で中間表現を考えるのが大変だったので現在の成果物ではASTから直接落とし込んでいくような形になっています。
(このポスターを書いているときにその言語非依存中間表現自体も開発すればよかったなと思ったのは秘密です)
基本的なバイナリフォーマット(基本整数型のみ)などであればどれもきちんと生成できます。条件分岐やビルトイン関数な
どの対応はまちまちだったりします。バイトアラインされていないフォーマットやbit prefixで分岐するみたいなのはまだ対応できていません。正直に言って私はまだ出来に満足してはいません。まだまだ改善の余地が残っています。

出力ファイル

ASTコードジェネレーター

LSPサーバーやGo言語用コードジェネレーター制作のためにASTを各言語(TypeScriptやGo言語)に人力で移植しようとしましたがノードの種類が大量で困難であり、またメンテナンス性も考えると人力移植はバグの原因になります。
同じ定義のものを移植するって面倒…はっ、これもコードジェネレーターで作ればいいんだ!と思い至り
ASTノードの定義から各言語のソースコードを生成するツールも作りました。
これのおかげでC++のノード定義をいじるだけで他言語には自動で反映することができるようになり、定義言語の仕様をASTの移植のことを気にせずかなり柔軟に変更することができるようになりました。
struct Ident : Expr {define_node_type(NodeType::ident);
std::string ident;
scope_ptr scope;
std::weak_ptr<Node> base;
IdentUsage usage = IdentUsage::unknown;

export interface Ident extends Expr {ident: string;usage: IdentUsage;
base: Node|null;
scope: Scope|null;}},{"node_type": "ident","base_node_type": ["expr","node"],"loc": "loc","body": {"expr_type": "shared_ptr<type>","constant_level": "constant_level","ident": "string","usage": "ident_usage","base": "weak_ptr<node>","scope": "shared_ptr<scope>"}

Ident(lexer::Loc l, std::string&& i): Expr(l, NodeType::ident), ident(std::move(i)) {}Ident(lexer::Loc l, const std::string& i): Expr(l, NodeType::ident), ident(i) {}// for decode
Ident(): Expr({}, NodeType::ident) {}void dump(auto&& field_) {Expr::dump(field_);
sdebugf(ident);
sdebugf(usage);
sdebugf(base);sdebugf(scope);
}

},
{

};

将来的にはC++もJSONから生成にしたい….

対象ユーザー
自作プロトコルしたい人

コードジェネレーターは作りかけ…

export function isIdent(obj: any): obj is Ident {return obj && typeof obj === 'object' &&typeof obj?.node_type === 'string' &&obj.node_type === "ident"}
func (n *Ident) GetNodeType() NodeType {return NodeTypeIdent}
type Ident struct {Loc
Loc
ExprType
Type
ConstantLevel ConstantLevel
Ident
string
Usage
IdentUsage
Base
Node
Scope
*Scope}生成コード→
C++(json2cpp2)

現時点で一番機能を実装しているジェネレーター。
しかし、依存ライブラリが今のところ私しか使っていない独自ライブラリのため、PoC的な意味合
いが強い言語によって継承があったりなかったり、
ポインタ値の扱いが違ったりしたのでそれぞれどう
実装するかに苦心しました。

使い方

セキュリティ

CLI

バッファオーバーフロー対策

例えば自作WebRTCとか自作QUICとか自作TLSとか https://github.com/onしてみたいけどフォーマット多すぎてやる気にな keyday/brgen/releases/tag/v0.0.5
らんと言う方、そういうつまんないところはぜひ からビルド済みバイナリをダウンロード
brgenを使って省略して、プロトコルの上位レイ できます。詳しくは
ヤー(アルゴリズム等)の実装に集中しましょう!
https://on-keyday.github.io/brgen/doc/docs/setup/
え?ツールだよりじゃいやだ?そんなあなたはぜひ LSPサーバー
ジェネレーター自体も自作してみましょう!
上記と同じ箇所からダウンロードできます
C++,Go,Rust,Python,TypeScriptでASTを扱うための
WebPlayground
ライブラリが提供されています!
https://on-keyday.github.io/brgen で公開しています。上のWebPlaygroundの説明の箇所に
2024/3/6
もQRコードがあります

たくさんコードを書いていると範囲チェックのコードを書いたりするのがめんどくさかったり忘れがちだったりしますがそれだとバッ
ファオーバフローなどの脆弱性に繋がってしまいます。brgenのコードジェネレーターは自動で範囲チェックを挿入するので安全です

算術オーバーフロー対策

struct FrameHeader{
std::uint32_t len = 0; // 24 bit int
std::uint8_t type = 0;::futils::binary::flags_t<std::uint8_t, 4, 1, 1, 1, 1> flags_0_;
bits_flag_alias_method(flags_0_,0,reserved_flag);
bits_flag_alias_method(flags_0_,1,padding);
bits_flag_alias_method(flags_0_,2,end_headers);
bits_flag_alias_method(flags_0_,3,unused);
bits_flag_alias_method(flags_0_,4,end_stream_or_ack);::futils::binary::flags_t<std::uint32_t, 1, 31> flags_1_;
bits_flag_alias_method(flags_1_,0,reserved);
bits_flag_alias_method(flags_1_,1,stream_id);
FrameHeader() {}::futils::error::Error<> encode(::futils::binary::writer& w) const ;::futils::error::Error<> decode(::futils::binary::reader& r);};
inline ::futils::error::Error<> FrameHeader::encode(::futils::binary::writer& w) const {if (!::futils::binary::write_uint24(w,this->len)) {return ::futils::error::Error<>("encode: FrameHeader::len: write 24 bit int failed",::futils::error::Category::lib);}if (!::futils::binary::write_num(w,static_cast<std::uint8_t>(this->type) ,true)) {return ::futils::error::Error<>("encode: FrameHeader::type: write std::uint8_t failed",::futils::error::Category::lib);}if (!::futils::binary::write_num(w,flags_0_.as_value() ,true)) {return ::futils::error::Error<>("encode: FrameHeader::end_stream_or_ack: write bit field
failed",::futils::error::Category::lib);}if (!::futils::binary::write_num(w,flags_1_.as_value() ,true)) {return ::futils::error::Error<>("encode: FrameHeader::stream_id: write bit field failed",::futils::error::Category::lib);}
return ::futils::error::Error<>{};}
inline ::futils::error::Error<> FrameHeader::decode(::futils::binary::reader& r) {if (!::futils::binary::read_uint24(r,this->len)) {return ::futils::error::Error<>("decode: FrameHeader::len: read 24 bit int failed",::futils::error::Category::lib);}if (!::futils::binary::read_num(r,this->type ,true)) {return ::futils::error::Error<>("decode: FrameHeader::type: read int failed",::futils::error::Category::lib);}if (!::futils::binary::read_num(r,flags_0_.as_value() ,true)) {return ::futils::error::Error<>("decode: FrameHeader::end_stream_or_ack: read bit field
failed",::futils::error::Category::lib);}if (!::futils::binary::read_num(r,flags_1_.as_value() ,true)) {return ::futils::error::Error<>("decode: FrameHeader::stream_id: read bit field failed",::futils::error::Category::lib);}
return ::futils::error::Error<>{};}

Go(json2go)

json2c – C言語向け
絶賛制作中!
json2rust – Rust向け
json2kaitai – Kaitai Struct(https://kaitai.io/)向け
その他雑ツール
ctobgnC言語の構造体や列挙体の定義をbrgenの定義ファイル
形式に変換するツール。
(完璧ではないです…)
json2cpp – json2cpp2のプロトタイプ版

Go言語向けジェネレーター。こちらは標準ライブラリのみ使用なので生成されたコードは比較的使いやすいです。ただjson2cppに比べると機能が少ないです

展望
課題
ジェネレーターの限界
現段階のジェネレーターは定義言語で表現できる範囲に比べてその能力はかなり制限されています。また、言語ごとに出来ることにも差があります。また対応言語もまだまだ少ないです。他にも生成結果もまだまだ最適とは言い難い面があります。

定義言語の限界
定義言語自体もまだまだ定義を表現するのに最適とは言い難いと思っています。より多くのサンプルを集め改善していきます。

C++のみですが算術オーバフローチェックをす
ドキュメントる関数に置き換えるオプションを提供していドキュメントは書きつつありますがまだまだ十分とは言えます。
ません。内容がわかりづらい部分もあるので改善していき
他にも自動生成なので人力で書いたときの整Jsonアイコン出典: https://icons8.com/icons/set/json
合性が合わないみたいなバグがなくなります。 たいです。
ソースコードアイコン出典: https://icons8.jp/icon/11260/%E3%82%BD%E3%83%BC%E3%82%B9%E3%82%B3%E3%83%BC%E3%83%89(そしてずるずると言語処理系に沼りましょう)

type EthernetFrame struct {DstMac[6]uint8
SrcMac[6]uint8
EtherType uint16
union_2_ struct {VlenTaguint16
EtherType2 uint16}
union_3_ struct {ServiceVlenTag uint16
DummyEtherType uint16
VlenTaguint16
EtherType2
uint16}
union_4_ struct {Data []uint8}
union_5_ struct {Data []uint8}}
func (t *EthernetFrame) Encode() ([]byte, error) {長いので省略}
func (t *EthernetFrame) Read(r io.Reader) (errerror) {長いので省略}

開発リポジトリ:https://github.com/on-keyday/brgenドキュメント:https://on-keyday.github.io/brgen/doc

対応言語の拡充
現在対応している言語は2つだけですが、より多くの言語にも対応していきたいです。現段階ではTypeScriptなどへの対応構想があります。また、インタープリターのようにして定義言語と実バイナリデータの整合性チェックを行うツールも作り途中です。

使えるサンプルの拡充
現在あるサンプルの中にはジェネレーターの限界もあってジェネレータで生成できないものが多いです。それらを対応していき生成できるものを増やしたいです。またサンプル自体も増やしていきたいです。

AST操作ライブラリの整備
現在定義言語パーサーに力を入れすぎた結果複雑になって若干
1
使いづらい部分もあります。もう少し使いやすくなるよう、また使い方がわかりやすくなるようASTを改良したり、周辺ツールをつくったり、ドキュメントを整備したりしていきたいです。