自作プロトコルスタック（全体像の理解〜ARPリプライ）

最近自作プロトコルスタックを始めました。とりあえずpingからのARPリクエストにARPリプライするまでを実装できたので、備忘録として残しておきます。（コードはneddyというリポジトリで公開しています） ARP周りの実装を中心に解説するため、

TCP/IPなどのデータリンク層以上の内容
そもそもARPって何って話
ip, tcpdumpなどのコマンド
TAP/TUNデバイスの詳しい扱い方

については要所で簡単に触れるのみ、または全く触れないものとします。マスタリングTCP/IPなどを読んで、一通り全体像を理解した人がARPの実装をざっくりと理解できるような内容になっています。

github.com

全体像

いきなりARPの実装に入っても意味がわからないと思うので、まずは自作プロトコルスタックがどのような構成で動いているのか確認したいと思います。以下の画像を見てください。

f:id:oshibori0121:20210219190632p:plain

まず、プロトコルスタックを自作する前に仮想デバイスを用意する必要があります。Linuxでは仮想Ethernetデバイスとして振る舞うTAPデバイスをユーザーが自由に作成できるので、これを使います。（図では分かりやすさのためにノードの中にプロトコルスタックがあるように見えますが、実際にそのような対応関係はありません）このような構成でプロトコルスタックを自作する利点として、

本来ring0で動作するプロトコルスタックを普通のユーザープログラムとして動かせる
上記の理由からgdbなどによるデバッグが簡単
デバドラ実装をサボってTAPデバイスのread/writeでパケットの読み書きが可能

などが考えられると思います。以下のようなコマンドを打って、TAPデバイスをreadすればすぐに届いたパケットが見れるので、実装を始めるハードルはとても低いです。（Ethernet デバイスドライバ = TAPデバイスに対する read/ writeみたいなイメージです）

$ sudo ip tuntap add mode tap user $USER name tap0
$ sudo ip addr add 10.0.0.1/24 dev tap0
$ sudo ip link set tap0 up

今回やること

pingからのARPリクエストにARPリプライして、pingがICMPエコーリクエストを送信してくるのを確認するところまでを実装します。事前に行うTAPデバイスの初期化処理などは省略し、主にARPに関連する部分を実装していきます。 pingによる疎通確認までの動作を以下のような4ステップに分解し、今回は3までを確認します。（ping側の視点で書いています）

ARPリクエストの送信
ARPリプライの受信
ICMPエコーリクエストの送信
ICMPエコーリプライの受信

今回の実装に特に関係するのは1,2のみです。1ではEthernetヘッダ、ARPヘッダのパースを行い必要な情報（送信元MACアドレスや送信元IPなど）を取り出します。2ではARPリプライパケットを作成します。（といっても、送信されてきたパケットを一部改変したパケットを返すだけなので、1の処理が今回のメインになります）3に関してはARPリプライが正常に送信されたことをチェックするために、tcpdumpで一応確認する程度に留めます。

実装

ここから具体的な実装を説明していきます。

※ TAPデバイスの初期化についてはneddyの tap.c に書いてあります。

ARPパケットの構造

APRパケットはEthernetヘッダ + ARPヘッダという構造になっています。 Ethernetヘッダ→ARPヘッダの順番で見ていきたいと思います。

f:id:oshibori0121:20210220204812p:plain — ARPパケットの構造

ざっくりと把握するだけならWikipedia を見ると良いです。

Ethernetヘッダの構造を理解する

Ethernetヘッダは14バイトで構成されており、

宛先アドレス（6バイト）
送信元アドレス（6バイト）
タイプ（2バイト）

という内訳になっています。構造体にすると、以下のようになります。

#define ETHER_ADDR_LENGTH 0x06
#define IPV4_ADDR_LENGTH 0x04

struct ether_hdr {
    uint8_t dst_addr[ETHER_ADDR_LENGTH];
    uint8_t src_addr[ETHER_ADDR_LENGTH;
    uint16_t type;
} __attribute__((__packed__));

プロトコルスタックは受信したパケットの宛先アドレスを確認し、自分宛でなければその時点でパケットを破棄します。ARPパケットの場合はブロードキャストで送信されるため、宛先アドレスが f:fff:ff:ff:ff:ff になります。ブロードキャストの場合は何かしら対応が必要なので、タイプを確認した上でどうハンドリングするかを決定します。タイプには決められた複数の値が指定可能であり、値の一覧はIEEE 802 numbersで参照できます。ARPの場合は 0x0806 です。ARPパケットであればARPのハンドラにパケットを流す必要があります。neddyでは以下のような実装になっています。

if (conv_endian16(ethdr->type) == 0x0806) {
       struct arp_packet *arp = (struct arp_packet*)buff;
       dump_arp(arp);  
       handle_arp(arp);
 }

conv_endian16 というのは、neddyで簡易的にビッグエンディアンをリトルエンディアンに変換する関数です。 TCP/IPではパケットのヘッダ部に関して、ビッグエンディアンを採用しています。一方で、普通のホストではリトルエンディアンでバイト列を取り出します。そのため、変換用の関数が必要になります。（@drumato さんに教えていただきました。ありがとうございます。）

こんにちは．
私はKLab Expert Campで同じくプロトコルスタックを実装しているものです．

ネットワークバイトオーダの考慮をしていない，という可能性はないですか?
バイトオーダがホストのものと異なる場合があり，micropsではネットワークバイトオーダからホストへの変換が実装されているかと．
— Drumato (@drumato) 2021年2月11日

ARPパケットの構造体を定義する

ここまででEthernetヘッダを見て、パケットがARPパケットであることを確認しました。次に、ARPパケットの中からARPヘッダを取り出し、ARPリプライパケットを作成する必要があります。 RFC826 を確認すればARPヘッダの具体的な構造は分かるので、ここでは仕様を構造体レベルに落とし込んで説明します。

struct arp_packet {
    struct ether_hdr ethdr;
    uint16_t hard;
    uint16_t pro;
    uint8_t hard_len;
    uint8_t pro_len;
    uint16_t opcode;
    uint8_t sha[ETHER_ADDR_LENGTH];
    uint8_t spa[IPV4_ADDR_LENGTH];
    uint8_t tha[ETHER_ADDR_LENGTH];
    uint8_t tpa[IPV4_ADDR_LENGTH];
} __attribute__((__packed__));

ARPヘッダは以下の9つのフィールドで構成されます。

ハードウェアタイプ（2バイト）
プロトコルタイプ（2バイト）
ハードウェア長（1バイト）
プロトコル長（1バイト）
オペコード（2バイト）
送信元ハードウェアアドレス（6バイト）
送信元プロトコルアドレス（4バイト）
宛先ハードウェアアドレス（6バイト）
宛先プロトコルアドレス（4バイト）

ハードウェアタイプはRFCによると、現時点でハードウェアタイプはEthernetを示す 0x001 だけのようです。

Currently the only defined value is for the 10Mbit Ethernet (ares_hrd$Ethernet = 1).

プロトコルタイプはIPv4の場合は 0x0800 になります。ハードウェアタイプがEthernet, プロトコルタイプがIPv4の場合はハードウェア長、プロトコル長がそれぞれ 0x06, 0x04 になります。 opcodeは、ARPリクエストの場合は 0x001 になり、ARPリプライの場合は 0x002 になります。ARPリクエストはブロードキャストで送信されるため、ARPリクエストパケットの宛先ハードウェアアドレスは無視します。

パケットを受信する

構造体が定義できたので、あとはパケットを受信する処理を書けば実際にpingから送信されたパケットを確認できるはずです。上述の通り、TAPデバイスに送られてきたパケットは通常のファイルのread / write の要領でアクセス可能です。ざっくりとですが、以下のようなコードを書けばパケットが受信できます。やっていることはtapデバイスのファイルをreadしてtypeがARPであればそれをダンプしているだけです。 (MAX_PACKET_SIZEは今のところ適当な値を設定しています)

int rsize = 0;

for (;;) {
        rsize = read_packet(buff, MAX_PACKET_SIZE);

        struct ether_hdr *ethdr = (struct ether_hdr*)buff;

        dump_ether(ethdr);

        if (conv_endian16(ethdr->type) == 0x0806) {
            struct arp_packet *arp = (struct arp_packet*)buff;
            dump_arp(arp);  
            handle_arp(arp);
        }

実際にpingから受信したARPパケットをダンプすると以下のような出力が得られました。

[Ethernet header]
dst addr=ff:ff:ff:ff:ff:ff
src addr=b2:6d:da:9:59:53
type=0x806(=ARP)
[ARP header]
hard_type=0x001, length 6
pro_type=0x800, length 4
opcode=0x001(=Request)
sha=b2:6d:da:9:59:53
spa=10.0.0.1
tha=0:0:0:0:0:0
tpa=10.0.0.2

spaが 10.0.0.1 になっているのは、pingから送信されたパケットが仮想EthernetデバイスであるTAPデバイス(10.0.0.1)からノード（10.0.0.2）へ転送されているためです。僕はここら辺を理解するのに結構悩んだのですが、Twitterで @pandax381 さんに色々教えていただきました。ありがとうございます。

やっと理解できました・・！！本当にありがとうございます🙇🙇

pingで10.0.0.2に届くARPパケットの送信元が10.0.0.1なのは、仮想Ethernetデバイスとして振る舞うtapデバイスから10.0.0.2のノードへパケットが転送されているからという認識で合っているのでしょうか？(何度もすみません)
— メールちゃんと確認する (おしぼり) (@oshibori_vmm) 2021年2月15日

はい、その通りです👌 tapデバイスをオープンしているプロセスがARPリプライを返せばOSのプロトコルスタック側からtapの先にノードが存在するように見え、なにも返さなければ存在しないように見えます。

なお、ARPのリプライやEthernetヘッダのMACアドレスは任意の値でも動作します。
— YAMAMOTO Masaya (@pandax381) 2021年2月15日

ARPリプライパケットの作成と送信

ARPパケットを受信して中身を確認することができたので、次はARPリプライを送信する必要があります。 pingの送信元に対してARPリプライを送信すると、pingはICMPエコーリクエストを返してくれるはずです。 ARPリプライの作成についてRFCでは以下のように書かれています。

Swap hardware and protocol fields, putting the local hardware and protocol addresses in the sender fields. Set the ar$op field to ares_op$REPLY Send the packet to the (new) target hardware address on the same hardware on which the request was received.

書かれている内容を具体的な実装に落とし込むと、以下の通りの変更を加えれば良さそうです。

宛先ハードウェアアドレスをARPリクエストパケットのshaにする
宛先プロトコルアドレスをリクエストのspaにする
送信元ハードウェアアドレスノードのハードウェアアドレスにする
送信元プロトコルアドレスをノードのIPアドレスにする
opcodeを 0x02 (= Reply) にする

ARPリプライパケットを作成し送信するコードは以下の通りです。 (現時点での実装はヒジョーーーーに雑なので、リトルエンディアンからビッグエンディアンへの変換関数の実装をサボってビッグエンディアンでベタ書きしています・・・)

int arp_reply(struct arp_packet *request) {
    struct arp_packet arp;
    int wsize;
    
    arp.hard = 0x100;
    arp.pro = 0x008;
    arp.hard_len = ETHER_ADDR_LENGTH;
    arp.pro_len = IPV4_ADDR_LENGTH;
    arp.opcode = 0x0200;
    memcpy(arp.sha, get_tap_hwaddr(), 6);
    memcpy(arp.spa, get_tap_ipaddr(), 4);

    // setup ethernet header
    memcpy(&arp.ethdr.dst_addr, request->sha, ETHER_ADDR_LENGTH);
    memcpy(&arp.ethdr.src_addr, arp.sha, ETHER_ADDR_LENGTH);
    arp.ethdr.type = 0x0608;

    memcpy(&arp.tha, request->sha, ETHER_ADDR_LENGTH);
    memcpy(&arp.tpa, request->spa, IPV4_ADDR_LENGTH);
    
    dump_ether(&(arp.ethdr));
    dump_arp(&arp);

    if ((wsize = write_packet(&arp, sizeof(arp))) < 0) {
        return -1;
    }

    printf("write %d bytes\n", wsize);

    return 1;
}

この時、送信元ハードウェアアドレスをどうするかちょっと悩みました。これについても @pandax381 さんに教えていただき、00:00:5e:00:53:01 というアドレスを使用することにしました。ドキュメント用アドレスについてはここが参考になりました。

自作プロトコルスタックの使うHWアドレスについては、動作するかという視点であれば任意の値でで大丈夫です。勝手に他者のOUIを使うのはお行儀が良くないので、テストの範囲であればドキュメント用のOUIを使うのがいいと思います（僕はそうしています）。
— YAMAMOTO Masaya (@pandax381) 2021年2月19日

変更後のARPパケットをダンプすると以下のような出力が得られます。

[Ethernet header]
dst addr=b2:6d:da:9:59:53
src addr=00:00:5e:00:53:01
type=0x806(=ARP)
[ARP header]
hard_type=0x001, length 6
pro_type=0x800,  length 4
opcode=0x002(=Reply)
sha=00:00:5e:00:53:01
spa=10.0.0.2
tha=b2:6d:da:9:59:53
tpa=10.0.0.1

ICMPエコーリクエストの確認

ARPリプライが正常に送信されていれば、10.0.0.2宛にpingからICMPエコーリクエストが届くはずです。今回はtcpdumpを利用して、1特定のTAPデバイスに絞ってパケットを見ることにしました。

tcpdump -i <tap_name>

<tap_name> は作成したTAPデバイスによります。例えば、tap0という名前でTAPデバイスを作成したのならtap0になります。

上記のコマンドを入力した上で、自作プロトコルスタックとpingを動かすと以下のような出力が得られます。 ARPリプライが送信され、pingからICMPエコーリクエストが送信されていることが確認できます。

20:23:32.295711 ARP, Request who-has 10.0.0.2 tell <----my_usrename---->, length 28
20:23:32.295870 ARP, Reply 10.0.0.2 is-at 00:00:5e:00:53:01 (oui IANA), length 28
20:23:32.295886 IP <----my_usrename----> > 10.0.0.2: ICMP echo request, id 5196, seq 1, length 64
20:23:33.325972 IP <----my_usrename----> > 10.0.0.2: ICMP echo request, id 5196, seq 2, length 64
20:23:34.350099 IP <----my_usrename----> > 10.0.0.2: ICMP echo request, id 5196, seq 3, length 64

未対応の仕様について

ここまでで、ARPリプライが正しく送信されていることが確認できました。最後にneddyで未対応の実装について軽く触れて終わりにしたいと思います。現在のneddyではアドレス変換テーブルの更新やエントリの追加に関して、RFCの仕様に準拠していません。RFCによると、ARPリクエストの受信側ではopcodeの確認より前にパケットのプロトコルタイプとプロトコルアドレスのペアをチェックします。もしそのペアに該当するエントリがアドレス変換テーブルに存在すればハードウェアアドレスを更新します。この動作について、 RFC826では以下のように書かれています。

If the pair is already in my translation table, update the sender hardware address field of the entry with the new information in the packet and set Merge_flag to true.

もしそのペアが存在しない場合はアドレス変換テーブルに新しいエントリとして登録します。

If Merge_flag is false, add the triplet to the translation table.

現状のneddyではまだアドレス変換テーブル自体が存在しないのでこれについては未対応です。

まとめ

早くTCP/IPレイヤの実装に取り掛かれるように頑張ります。この記事を読んでいればわかると思いますが、Twitter上で本当にたくさんの人にアドバイスを頂きました。本当にいつもありがとうございます！！この記事に書かれている内容に関して、間違いや問題点などがあればドシドシ指摘してもらえると嬉しいです。

おしぼりの日常

低レイヤが好きです.