ICTSC Tech Blog

ICTSC2025 本戦 問題解説: [6824] エコロケーション

ICTSC2025 問題解説 ネットワーク関連

問題文

概要

ネットワーク初心者のイルカは、ネットワークプロトコルの実装というものをやりたくなった。

ターゲットは NAPT だ。流行りにのって Rust でやろう。AI にも頼りながら書いていくぞ！

～数時間後～

あの、ping すら通らないんですけど……

ところで、ICMP ってポート番号はないけど、NAPT ではどう扱っているんだろう？ んー AI にでも訊くか……

制約

  • この問題は Network Namespace を使用した、仮想的なネットワーク空間で実現される
    • Namespace は ns_lan, ns_wan の2つ
  • NS ns_lan のエンドポイントは 192.168.200.2 192.168.200.3 192.168.200.4 の3つであり、それぞれから NS ns_wan の 10.200.0.2 との ping の橋渡しを実現する NAPT の実装を行う
  • /home/user/napt/ に Rust製の NAPT プロジェクトがあり、これを編集、コンパイルしてプログラムを修正する
  • 以下のバイナリをrootで実行すると、VM内のNAPTが起動する
    • /home/user/napt/target/debug/napt
  • /home/user/napt ディレクトリ配下で以下のコマンドを実行すると NAPT のバイナリが更新される
    • cargo build
  • ip や Namespace の追加や変更、削除など、ネットワーク情報を変更してはならない
  • 解答にソースコードを含める必要はないが、変更点の概要は含めること

初期状態

  • NAPT起動時、以下のコマンドで ping が返らない
sudo ip netns exec ns_lan ping -I 192.168.200.2 -c 3 10.200.0.2
sudo ip netns exec ns_lan ping -I 192.168.200.3 -c 3 10.200.0.2
sudo ip netns exec ns_lan ping -I 192.168.200.4 -c 3 10.200.0.2

終了状態

  • NAPT起動時、以下のコマンド全てで ping が返る
sudo ip netns exec ns_lan ping -I 192.168.200.2 -c 3 10.200.0.2
sudo ip netns exec ns_lan ping -I 192.168.200.3 -c 3 10.200.0.2
sudo ip netns exec ns_lan ping -I 192.168.200.4 -c 3 10.200.0.2

接続情報

ホスト名 IPアドレス ユーザ パスワード
6824-h1 192.168.24.1 user ictsc2025

解説

ICMP の checksum の再計算が抜けていましたので、それを追加する必要がありました。

#[cfg(target_os = "linux")]
use nix::sched::{CloneFlags, setns};
use pnet::packet::MutablePacket;
use pnet::packet::icmp::echo_reply::{EchoReplyPacket, MutableEchoReplyPacket};
use pnet::packet::icmp::echo_request::{EchoRequestPacket, MutableEchoRequestPacket};
use pnet::packet::icmp::{IcmpPacket, IcmpTypes, MutableIcmpPacket, checksum as icmp_checksum};
use pnet::packet::ip::IpNextHeaderProtocols;
use pnet::packet::ipv4::{MutableIpv4Packet, checksum as ipv4_checksum};
#[cfg(target_os = "linux")]
use std::fs::File;
use std::{collections::HashMap, net::Ipv4Addr};
use tokio::io::{AsyncReadExt, AsyncWriteExt};
use tun::AbstractDevice;

const WAN_IP: Ipv4Addr = Ipv4Addr::new(10, 200, 0, 1);

#[cfg(target_os = "linux")]
fn open_tun_in_netns(
    netns_name: &str,
    tun_name: &str,
) -> Result<tun::AsyncDevice, Box<dyn std::error::Error>> {
    let original_netns = File::open("/proc/self/ns/net")?;
    let target_netns = File::open(format!("/var/run/netns/{netns_name}"))?;

    setns(&target_netns, CloneFlags::CLONE_NEWNET)?;

    let create_result = (|| -> Result<tun::AsyncDevice, Box<dyn std::error::Error>> {
        let mut cfg = tun::Configuration::default();
        cfg.tun_name(tun_name).up();
        cfg.platform_config(|platform| {
            platform.ensure_root_privileges(false);
        });
        Ok(tun::create_as_async(&cfg)?)
    })();

    let restore_result = setns(&original_netns, CloneFlags::CLONE_NEWNET);
    if let Err(err) = restore_result {
        return Err(format!("failed to restore netns: {err}").into());
    }

    create_result
}

#[derive(Default)]
struct NatTable {
    forward: HashMap<(Ipv4Addr, u16), u16>,
    backward: HashMap<u16, (Ipv4Addr, u16)>,
    next_id: u16,
}

impl NatTable {
    fn allocate_external_id(&mut self, internal: (Ipv4Addr, u16)) -> u16 {
        if let Some(existing) = self.forward.get(&internal) {
            return *existing;
        }

        // テーブルが埋まるとハングしてしまうが、今回は見逃す
        loop {
            self.next_id = self.next_id.wrapping_add(1);
            if self.backward.contains_key(&self.next_id) {
                continue;
            }
            self.forward.insert(internal, self.next_id);
            self.backward.insert(self.next_id, internal);
            return self.next_id;
        }
    }

    fn lookup_internal(&self, external_id: u16) -> Option<(Ipv4Addr, u16)> {
        self.backward.get(&external_id).copied()
    }
}

fn rewrite_outbound_icmp(packet: &mut [u8], table: &mut NatTable) -> Option<usize> {
    let packet_len = packet.len();
    let mut ip = MutableIpv4Packet::new(packet)?;
    let total_len = ip.get_total_length() as usize;
    if total_len < 20 || total_len > packet_len {
        return None;
    }
    if ip.get_next_level_protocol() != IpNextHeaderProtocols::Icmp {
        return None;
    }

    let src = ip.get_source();
    let payload = ip.payload_mut();
    let icmp = IcmpPacket::new(payload)?;
    if icmp.get_icmp_type() != IcmpTypes::EchoRequest {
        return None;
    }

    let request = EchoRequestPacket::new(payload)?;
    let internal_id = request.get_identifier();
    let external_id = table.allocate_external_id((src, internal_id));

    let mut req_mut = MutableEchoRequestPacket::new(payload)?;
    req_mut.set_identifier(external_id);

    // 追加
    let mut icmp_mut = MutableIcmpPacket::new(payload)?;
    icmp_mut.set_checksum(0);
    let csum = icmp_checksum(&icmp_mut.to_immutable());
    icmp_mut.set_checksum(csum);

    ip.set_source(WAN_IP);
    ip.set_checksum(0);
    let ip_csum = ipv4_checksum(&ip.to_immutable());
    ip.set_checksum(ip_csum);

    Some(total_len)
}

fn rewrite_inbound_icmp(packet: &mut [u8], table: &NatTable) -> Option<usize> {
    let packet_len = packet.len();
    let mut ip = MutableIpv4Packet::new(packet)?;
    let total_len = ip.get_total_length() as usize;
    if total_len < 20 || total_len > packet_len {
        return None;
    }
    if ip.get_next_level_protocol() != IpNextHeaderProtocols::Icmp {
        return None;
    }

    let payload = ip.payload_mut();
    let icmp = IcmpPacket::new(payload)?;
    if icmp.get_icmp_type() != IcmpTypes::EchoReply {
        return None;
    }

    let reply = EchoReplyPacket::new(payload)?;
    let external_id = reply.get_identifier();
    let (internal_ip, internal_id) = table.lookup_internal(external_id)?;

    let mut rep_mut = MutableEchoReplyPacket::new(payload)?;
    rep_mut.set_identifier(internal_id);

    // 追加
    let mut icmp_mut = MutableIcmpPacket::new(payload)?;
    icmp_mut.set_checksum(0);
    let csum = icmp_checksum(&icmp_mut.to_immutable());
    icmp_mut.set_checksum(csum);

    ip.set_destination(internal_ip);
    ip.set_checksum(0);
    let ip_csum = ipv4_checksum(&ip.to_immutable());
    ip.set_checksum(ip_csum);

    Some(total_len)
}

#[tokio::main(flavor = "current_thread")]
async fn main() -> Result<(), Box<dyn std::error::Error>> {
    #[cfg(target_os = "linux")]
    let mut lan = open_tun_in_netns("ns_lan", "tun_lan")?;
    #[cfg(target_os = "linux")]
    let mut wan = open_tun_in_netns("ns_wan", "tun_wan")?;

    #[cfg(not(target_os = "linux"))]
    compile_error!("This program currently supports Linux network namespaces only.");

    eprintln!(
        "opened lan={} wan={}",
        lan.tun_name().unwrap_or_else(|_| "unknown".to_string()),
        wan.tun_name().unwrap_or_else(|_| "unknown".to_string())
    );

    let mut lan_buf = [0_u8; 2048];
    let mut wan_buf = [0_u8; 2048];
    let mut table = NatTable::default();

    loop {
        tokio::select! {
            n = lan.read(&mut lan_buf) => {
                let n = n?;
                if let Some(out_len) = rewrite_outbound_icmp(&mut lan_buf[..n], &mut table) {
                    wan.write_all(&lan_buf[..out_len]).await?;
                    println!("LAN->WAN icmp napt {} bytes", out_len);
                }
            }
            n = wan.read(&mut wan_buf) => {
                let n = n?;
                if let Some(out_len) = rewrite_inbound_icmp(&mut wan_buf[..n], &table) {
                    lan.write_all(&wan_buf[..out_len]).await?;
                    println!("WAN->LAN icmp restore {} bytes", out_len);
                }
            }
        }
    }
}

余談

IP の方もチェックサムを再計算しているのですが、実はこれは環境によっては不要です。

採点基準

ping が napt を通じて通ったら 100点

講評

全チーム100点を獲得していました。素晴らしい！

……と言いましたが、実際のところ AI に与えれば一発で解ける問題だったと思います。
別に、AI を使って解いても使わず解いても、どちらも等しく素晴らしいです。

この問題は、作問者の「NAPT は IP アドレスとポート番号で識別しているけど、ポート番号を持たない ICMP はどうやって識別しているのか？」という疑問から作成されました。
参考書などで「このプロトコルはこのような動作原理で動いています！」とか言われても「この場合はマズくね？」って思うとき、ありますよね。
たとえば、「BGP は AS 間の経路を広告する」に対して、「誰でも任意のプレフィックスを広告できるなら、嘘の経路を流せない？」などです。（BGP ハイジャック問題）
この、捻くれた隅々まで逃さない思考方法を頭の片隅に置くことは大切だと思います。
AI 時代、見た目はちゃんと動いていそうな生成物も、頭を捻らせて、コーナーケースを探し出す癖を持てば、AIに裏切られた！みたいなことは起きずに済むのではないでしょうか？

雑記

登場人物（人物？）は最初はコウモリだったが、同じエコロケーションができる種として、イルカに差し替えられた。
普段は訊かれる側であろうイルカを AI に訊く側に立たせたかったため。