iptables のみで Fizz Buzz を解いてみた

# はじめに
Kubernetes の Service の実態は Linux カーネルに実装されている `iptables` です。より厳密には Netfileter と呼ばれるパケットフィルタリングモジュールであるといえるかもしれません。
さて、この `iptables` ですがざっくり説明すると「システムを通過するパケットに**特定の条件**に基づいて許可またはブロックする」といった**ルールを作成**するコマンドラインベースのツールです。 Kubernetes では `statistic` という拡張モジュールを使って確率でパケットの行き先を分岐する（負荷分散）という仕組みになっています。

・・・なんだか FizzBuzz を解けそうな気配を感じますね。やってみましょう。
- - -

# 条件
「`iptables` "のみ"で FizzBuzz を解いた」と言えるように、先に制約条件を決めておきます。
1. 入力は `ping` コマンドを使い、パケットを生成すること
2. 出力（レスポンス）も `iptables` のルールによって表現すること

結局、入力の受取りから判定ロジック、出力の生成までを `iptables` のルールで表現できれば良いよね、という話です。

# FizzBuzz 問題を整理
FizzBuzz の解法はいくつもありますが、基本的には
1. 条件によって処理を分岐できること(IF)
2. 除算の余りを取得できること(%)

の2つの処理を実行できれば解けるはずです。
また、今回特有のポイントとして、
1. `ping` からの入力をどう受け取るか
1. 出力をどう表現するか

の二点が挙げられます。

# `iptables` で解いていく
まずはおもむろに `iptables` のドキュメントを読み漁ります。
https://straypenguin.winfield-net.com/ipttut/output/ipttut_all.html

## 出力を考える
`iptables` は、パケットを通過させるか遮断するかを選択するためだけのツールなので、任意のレスポンスを返すという機能はありません。
ただ唯一、パケットの REJECT をすることで、送信者に対してエラー通知を行うことができます。今回はこのエラー通知を利用して出力を行います。

### ICMP 到達不能メッセージを返す
`ping` などで使われる ICM プロトコルではエコー要求に対して Port Unreachable などのエラーを返すことが可能です。幸い `iptables` でも `REJECT` ターゲットによっていくつかのエラーを直接返すことが可能です。
以下はすべての自機から出る ICMP エコー要求パケットをポート不到達エラーで返すサンプルです。
```
iptables -A OUTPUT -p icmp --icmp-type 8 -j REJECT --reject-with icmp-port-unreachable
```
このルールを適用した状態で `ping` をするとこのように表示されます。
```
❯  ping localhost -4 -c 1
PING  (127.0.0.1) 56(84) bytes of data.
From localhost (127.0.0.1) icmp_seq=1 Destination Port Unreachable
ping: sendmsg: Operation not permitted

---  ping statistics ---
1 packets transmitted, 0 received, +1 errors, 100% packet loss, time 0ms
```

## 入力を考える

### `ping -c` オプションで渡す
`ping` コマンドには `-c` オプションで何回 `ping` を送るかを設定することができます。この `-c` オプションで指定する値を入力値として使用します。
こうすることで一度の `ping` コマンドで `1~N (Nは任意の自然数)` の解を求めることができます。

## 処理１：条件によって処理を分岐する
`iptables` のドキュメントを読んでも 条件分岐を直接表現する機能はありません。しかし、ルールそのものが「一致した場合はターゲットにジャンプする」ということ示しているため、それ自体が条件分岐を表現しているはずです。
したがって残りは「除算の余り」をどう条件としてルールに設定できるかのみを考えればいいです。

## 処理２：除算の余りを取得する
 `iptables` のドキュメントを読み漁って得られた知見はルールに使用できるマッチのほとんどは定数的であるということです。つまり、「とあるヘッダの値がKである」のようなマッチしかなく、「とあるヘッダの値をTで割ったときの結果がこうである」のようなマッチはありません。（自由に使える演算子が無い）

:::note info
用語解説
<dl>
  <dt>ルール</dt>
  <dd>「パケットが特定の条件の場合にどのように処理するか」を指定するものです</dd>
  <dt>マッチ</dt>
  <dd>いわゆるマッチャで、ルールの「条件」を表現する方法です</dd>
</dl>
:::

### `u32` マッチ
数少ない柔軟なマッチのうち、`u32` はとてもいい線にいっています。
> U32 は、パケットから最大 4 バイトの数値を取り出して、指定した値を持つかの検査を行う。 どこを取り出すかの指定は汎用的になっており、TCP ヘッダーやペイロードから指定したオフセットのデータを取り出すことができる。

検査のために演算子もいくつか使用できます。使える演算子は `&, <<, >>, &&` (意味はCと同じ)で、これだけでは `%5` を表現することができませんでした。（少なくとも自分の頭では）

### `recent` マッチ
マッチの一つに `recent` があります。
> recent マッチは、かなり幅広い使い方のある複雑なマッチング機構で、前に行われたマッチを手掛かりにしてパケットを選定することができる。

一見関係なさそうに見えますが、 `--seconds` や `--hitcount` オプションを使うことで「指定秒数以内にN回ヒットしたパケット」をマッチさせることが可能です。
幸い入力は `ping -c N` で行うので、（シーケンス番号だけ異なる）同じパケットが N 個飛びます。 `--hitcount 3` とすれば、最初の Fizz は判定することができそうです。
また、 `recent` にはアドレスリストを操作するためのルールも設定することができます。例えば Fizz がマッチしたときにリストをクリアして、再度1からカウントするようにすれば次の Fizz も判定することができそうです。
・・・言葉で説明するより実際にルールとして起こしてみます。
```
# 使うチェインを作成
iptables -N ICMP_CHAIN
iptables -N FIZZ

# ICMP エコー要求パケットを ICMP_CHAIN に飛ばす
iptables -A OUTPUT -p icmp --icmp-type 8 -j ICMP_CHAIN

# アドレスリストを作成または更新
iptables -A ICMP_CHAIN -m recent --name fizz --set

# ヒット数が3に達したら FIZZ に飛ばす
iptables -A ICMP_CHAIN -m recent --name fizz --rcheck --hitcount 3 -j FIZZ

# アドレスリストをリセットし、リジェクトする
iptables -A FIZZ -m recent --name fizz --remove -j REJECT
```
このルールを適用して `ping` を流してみます。
```
❯  ping localhost -4 -c 6
PING  (127.0.0.1) 56(84) bytes of data.
64 bytes from localhost (127.0.0.1): icmp_seq=1 ttl=64 time=0.040 ms
64 bytes from localhost (127.0.0.1): icmp_seq=2 ttl=64 time=0.128 ms
From localhost (127.0.0.1) icmp_seq=3 Destination Port Unreachable
ping: sendmsg: Operation not permitted
64 bytes from localhost (127.0.0.1): icmp_seq=4 ttl=64 time=0.134 ms
64 bytes from localhost (127.0.0.1): icmp_seq=5 ttl=64 time=0.126 ms
From localhost (127.0.0.1) icmp_seq=6 Destination Port Unreachable
ping: sendmsg: Operation not permitted

---  ping statistics ---
6 packets transmitted, 4 received, +2 errors, 33.3333% packet loss, time 5061ms
rtt min/avg/max/mdev = 0.040/0.107/0.134/0.038 ms
```
`icmp_seq=` が3の倍数の時のみ `Destination Port Unreachable` されるようになっています。
以上で「除算の余りを取得する」処理を `iptables` を使って表現することができました。

:::note info
厳密には「除算の余りを取得」ではない
:::

### `recent` マッチの問題点
`recent` マッチは"アドレスリスト"を残しておくことで、以前のパケットとのマッチを実現しています。
つまり、アドレスリストの数が中途半端な値になってしまった場合、入力と hitcount がズレてしまい結果としてFizzBuzzできなくなってしまいます。これでは FizzBuzz を解いたとは言えません。
`ping` コマンド単位でアドレスリストをリセットするルールを考えてみます。

ICMPのエコー要求パケットでは送信するパケットに**シーケンス番号**を割り振ります。
このシーケンス番号はパケットの27バイト目から2バイトです。
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3523954/f70cb892-94e3-30fa-51f8-0a4ce321a689.png)
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3523954/a1d5ee3c-5b44-d5a1-cae0-7bde06b5e841.png)
*　https://straypenguin.winfield-net.com/ipttut/output/ipttut_all.html#ICMPHEADERS より引用
ここで先に触れた `u32` マッチを応用して使ってみます。
```
iptables -N RESET
iptables -A ICMP_OUTPUT -m u32 --u32 "26>>16=0x01" -j RESET
iptables -A RESET -m recent --name fizz --remove
```
`--u32 "26>>16=0x01"`の部分をざっと解説しておきます。
`26`：パケットの27バイト目から4バイト取出し、
`>>16`：右に16ビット（2バイト）シフトした、
`=0x01`：結果が0x01であれば、
マッチとなり、RESET に飛ばします。 RESET チェインではすべてのアドレスリストを削除します。
以上でシーケンス番号が1のとき、必ず `recent` の hitcount も1になるようにできるはずです。


## 処理を繋げていく
以上で FizzBuzz を解くのに必要な要素はすべて揃いました。あとは実際に動くようにチューニングしながらルールを組み立てていきます。
以下がその完成したルールセットです。
```
#!/bin/bash -x

iptables -F

iptables -N RESET_CHAIN
iptables -N COUNTER_CHAIN
iptables -N LOGIC_CHAIN
iptables -N NOTHING
iptables -N FIZZ
iptables -N BUZZ
iptables -N FIZZBUZZ

iptables -A OUTPUT -p icmp --icmp-type 8 -j RESET_CHAIN
iptables -A OUTPUT -p icmp --icmp-type 8 -j COUNTER_CHAIN
iptables -A OUTPUT -p icmp --icmp-type 8 -j LOGIC_CHAIN

iptables -A RESET_CHAIN -m u32 ! --u32 "26>>16=0x01" -j RETURN
iptables -A RESET_CHAIN -m recent --name fizz      --remove
iptables -A RESET_CHAIN -m recent --name buzz      --remove
iptables -A RESET_CHAIN -m recent --name fizzbuzz  --remove

iptables -A COUNTER_CHAIN -m recent --name fizz     --set
iptables -A COUNTER_CHAIN -m recent --name buzz     --set
iptables -A COUNTER_CHAIN -m recent --name fizzbuzz --set

iptables -A LOGIC_CHAIN -m recent --name fizzbuzz --rcheck --hitcount 15 -j FIZZBUZZ
iptables -A LOGIC_CHAIN -m recent --name buzz     --rcheck --hitcount 5  -j BUZZ
iptables -A LOGIC_CHAIN -m recent --name fizz     --rcheck --hitcount 3  -j FIZZ
iptables -A LOGIC_CHAIN                                                  -j NOTHING

iptables -A NOTHING                                     -j REJECT --reject-with icmp-net-unreachable   # CODE = 0
iptables -A FIZZ     -m recent --name fizz     --remove -j REJECT --reject-with icmp-host-unreachable  # CODE = 1
iptables -A BUZZ     -m recent --name buzz     --remove -j REJECT --reject-with icmp-proto-unreachable # CODE = 2
iptables -A FIZZBUZZ -m recent --name fizzbuzz --remove -j REJECT --reject-with icmp-port-unreachable  # CODE = 3

iptables -I FIZZBUZZ 1 -m recent --name fizz --remove
iptables -I FIZZBUZZ 1 -m recent --name buzz --remove

iptables-save | iptables-restore
```
このシェルスクリプトを `sudo` 権限で実行することで `iptables` で動作する FizzBuzz ソルバーが完成します。

:::note warn
既にルールを設定している場合、破壊することになるので注意してください
:::

# 結果を見る
試しに `ping` を流してみましょう。
```
❯  ping localhost -4 -i 0.02 -c 15
PING  (127.0.0.1) 56(84) bytes of data.
From localhost (127.0.0.1) icmp_seq=1 Destination Net Unreachable
ping: sendmsg: Operation not permitted
From localhost (127.0.0.1) icmp_seq=2 Destination Net Unreachable
ping: sendmsg: Operation not permitted
From localhost (127.0.0.1) icmp_seq=3 Destination Host Unreachable
ping: sendmsg: Operation not permitted
From localhost (127.0.0.1) icmp_seq=4 Destination Net Unreachable
ping: sendmsg: Operation not permitted
From localhost (127.0.0.1) icmp_seq=5 Destination Protocol Unreachable
ping: sendmsg: Operation not permitted
...(略)
From localhost (127.0.0.1) icmp_seq=14 Destination Net Unreachable
ping: sendmsg: Operation not permitted
From localhost (127.0.0.1) icmp_seq=15 Destination Port Unreachable
ping: sendmsg: Operation not permitted

---  ping statistics ---
15 packets transmitted, 0 received, +15 errors, 100% packet loss, time 373ms
```
出力は見にくいですが `icmp_seq=` が特定の値のときだけリジェクト結果が異なっていることがわかります。
`awk` を使って出力結果を整形し、ファイルに入れます。
```
❯  ping localhost -4 -i 0.02 -c 50| awk -v 'OFS=\t' '/^From/ { gsub("Net", "", $6);gsub("Host", "Fizz"); gsub("Protocol", "Buzz"); gsub("Port", "FizzBuzz"); print substr($4, 10), $6 }' > ./result_ip.txt
```
```
❯  cat ./result_ip.txt
1
2
3       Fizz
4
5       Buzz
6       Fizz
7
8
9       Fizz
10      Buzz
11
12      Fizz
13
14
15      FizzBuzz
...(略)
45	FizzBuzz
46	
47	
48	Fizz
49	
50	Buzz
```
とてもそれっぽい結果が得られました。
さっとpythonの結果と比較してみます。
```
import sys

args = sys.argv
max = int(args[1])
for i in range(1, max+1):
    if i % 15 == 0:
        print(i, "\tFizzBuzz", sep="")
    elif i % 3 == 0:
        print(i, "\tFizz", sep="")
    elif i % 5 == 0:
        print(i, "\tBuzz", sep="")
    else:
        print(i, "\t", sep="")
```
```
❯  python fizzbuzz.py 50 > result_py.txt
❯  diff result_ip.txt result_py.txt | wc -l
0
```
差分がないので正しく解けているといえそうです。

# まとめ
Kubernetes のサービスについての理解を深めるつもりが `iptables` の理解がだけが深まってしまいました。どのマッチを使えば何を表現をできるのかを考える時間は非常に楽しく、面白かったです。
他にも色々な実装がありそうなので、ぜひ皆さんも夏の自由研究として iptables fizz-buzz ルールを作ってみてはいかがでしょうか。