ueno’s diary

正確には、本インターンで実装するプロトコルスタックはmasterではなくkec5ブランチの実装で、インターン用にいくつか機能が削られています。masterにはSocket APIやTUN/TAPだけではなくPF_PACKETを用いたEthernetドライバ実装などがあります。↩
ユーザランドではパケットが到着した際のハードウェア割込みを捕まえられないので、ハードウェア割込みをシグナルの送受信で模倣します。↩
ICMPはIPと同じインターネット層のプロトコルですが、実際はIPに包まれて送られます。↩
Linux側でIPフォワードとアドレス変換の設定をすることでLinuxホストはゲートウェイとなり、[自作プロトコルスタック]<---- (Linuxホスト) ---->[インターネット上のホスト]で通信できるようにします。↩

はじめに

2023年度のセキュリティ・ネクストキャンプに参加しました。応募課題を書く際に公開されているものが参考となったため、私も応募課題を公開します。

2023年度セキュリティ・ネクストキャンプ応募課題

以下について，フリーフォーマットで自由に記述し回答してください．

■ あなたに関する問い

あなたは今までどのようなことをやってきましたか．どのようなことができて，どのようなことが得意で，どのようなことに自信がありますか．どのようなものを作りましたか．どのような情報を発信してきましたか．どのようにしてそうしたことをやってきましたか．なぜ，そのようなことをやってきましたか．やってきてどう思いましたか．参加できた場合，セキュリティ・ネクストキャンプにどのようなことを期待し，どのようなことをやってみたいですか．

私は大学生になるまで自由に触れる汎用計算機がおおよそスマートフォンしかない生活を送っていたため、学部生からの取り組みについて書く。なお、現在修士1年である。

2019-2020年度(学部1、2年生)の頃は、███████████████████████████████████に所属し、キャチロボというお題で指定されたお菓子を、指定された場所にロボットで運ぶロボコンに参加していた。ロボコンよろしく、制作の大部分は学生同士で協議しながら機体・回路・制御の開発を行った。そのなかでも、私は機体班や回路班が制作したロボットを動かすためのプログラムを書く制御班となり、当時学部2年の先輩と2人でプログラムを作成した。当時の団体にはROS(Robot Operation System)のようなミドルウェアを使う習慣がなく、制御用のSTM32マイコン用のプログラムをMbed環境上でスクラッチで開発であった。私は主にロボットのアームをPID制御で制御するプログラムを書き、ここで、マイコンの基本的なペリフェラル（GPIO、UART、PWMなど）、ペリフェラルが扱う信号の仕様、ロボットに目的の動作をしてもらうための制御方法(PID制御)を学んだ。また、プロジェクトを分担して進めるにあたって、プログラムの品質を保ちながら時間内に開発を終わらせるためには自身が担当するドメインの周辺の知識が必要であると強く思った。というのも、機体や回路の知識がないとプログラムのデバッグが困難になり、機体の動作限界や回路の定格を把握しておかないとそもそもロボットが動作しないといったことを経験したためである。多難ではあったもののなんとか完成にこぎつけ、2019年9月の大会に出場し、初戦敗退だった。次年度以降は、COVID-19の影響でキャチロボ含めすべてのロボコンが中止になり、また団体での活動もできなくなった。加えて、大学でオートマトンやOSなどの授業が始まったことにより、ロボットから徐々に計算機科学(特に低レイヤー)・ソフトウェアの方へ興味が移った。

2021年度には、███████████████████████████████████████████のインターンに参加に参加し、そこでアルバイトとして雇っていただきReact、Redux、Jestを用いてe-Learningシステムのフロントエンド開発を行なっていた。詳細に書くとよくなさそうなのでので簡単に述べるが、██████████████████████████████████████████████████。また、同時期に、大学で受けたOSでOSの仮想化技術(コンテナ、ハイパバイザなどではなく、プロセス管理やメモリ空間の仮想化の方)に興味を惹かれたため、OSの自主ゼミをいくらかの友人に呼びかけ主催した。呼びかけに応えてくれた2人とゼミ用の本を選び、有名なOSの教科書であるOperating System Three Easy Piecesを採用した。ジョブスケジューリングやメモリの仮想化について学び、これらの機能を小さなCのコードで実際に確認しながら読み進めた(当時のログ)。他にも、低レイヤを知りたい人のためのCコンパイラ作成入門を読みながらCコンパイラのサブセットを書き始めたが、関数の実装のところででやめてしまった(当時のリポジトリ)。しかし、LL文法（特にLL(1)）をパースするためのアルゴリズム（再帰下降構文解析）をそこで知り、BNFをそのままコードに書き起こすだけでLL(1)文法がパースできることに感動した記憶がある。このとき、ELFの仕様やコンパイラやリンカの仕組みについて調べたので、ELFのパーサも書いたりした。 2019-2021年度の経験から、小さな組み込み機器を作ることや、OSを気遣ったコードが書ける。後者については、例えば、キャッシュやレジスタ意識した高速なコードを書けるという意味である。

2022年度は院試と研究が大部分を占めていた。私は外部の大学院に進学したため、院試の勉強が必要であり、その際にはパタヘネやM. Sipserの計算機理論の基礎などの計算機科学の著名な教科書を読み直した。院試の勉強中もそれをもとにしたプログラムはいくつか書いていて、例えば、Sipserの本には（拡張されていない真の意味での）正規表現で表せる言語と決定性有限オートマトンが受理する言語が等価であることの証明が載っているため、正規表現をそのままオートマトンにマッピングすることにより正規表現エンジンを作った。結果、簡単な正規表現を見ると脳内でオートマトンに展開できるようになった。研究では、よくソフトウェアのインストールに使われるcurl|shで悪性のシェルスクリプトがダウンロードされたとき、不正な動作、特に情報漏洩を防ぐことを目的とした研究を行った。手法にはデータフロー解析の1種である動的テイント解析を用い、漏洩させてはならないデータの流れを監視するためのツールを作成し、評価した。実装は動的テイント解析ライブラリであるlibdft64を用い、結果、設定した評価項目の50%は作成したツールで情報漏洩を阻止できることを確認した。データフローの監視はシステムコールをフックすることで実現したので、本研究を通して動的テイント解析への理解だけではなく、シェルのコマンド実行・プロセス間通信の仕組みやデータ送信のためのソケットの仕組みなどへの理解が深まった。

2023年度には、修士から所属する研究室がHPC(High Performance Computing)の研究室であり、学部の頃から分野が変わったので論文を読んでいた。 ████████████████████████████████████████████████████████████████████████████████。

私が参加できた場合に期待することは、特定の技術よりも講師の方や同じ参加者の方と議論や雑談ができる環境および機会を用意していただくことである。これは、技術的な側面を含めて、人の行動や思考が周囲の人々を含む環境に大きく影響を受けると私が信じているからである（外部の大学院に進学した理由の一つ）。ただし、暗黙的にスキルアップも望んでいることは全く否定できない。

やってみたいことに関しては、3番目の質問への回答へ譲る。

■ 課題への姿勢に関する問い

自身で何らかの技術的な疑問を設定し，その疑問を解決しようと取り組み，その過程を示すことで，自身の技術力や課題に取り組むやりかたを説明してください． (疑問の例：実行ファイルはどのような構造になっているのだろう？ lsコマンドは何をしているのだろう？ pingコマンドを実行すると何が起きるんだろう？といったようなことです) 設定する疑問は何でも構いませんし，解決しなくても構いません．解決できたかどうかではなく，いかに課題に取り組むかという点を評価します．

設定する課題

xv6は起動時何をするか？ xv6はMITの授業で使用されているRISC-V向けの教育用OSである。 Linuxは普段使用しているOSで、資料も豊富であるが、調査が終わりそうもないのでxv6を選択した。

課題に対する調査

動作確認

課題は起動時の調査のみであるが、まずはxv6の全体の動作を確認するためビルドし、QEMU上で実行してみる。 xv6には、QEMUで実行するためのレシピがMakefileに書いてあるので、make qemuを実行するだけでQEMUが立ち上がる。すると、xv6がブートされ、シェルが起動されたので、デフォルトで実装されているlsコマンドを実行すると、確かにファイル一覧が表示された。これではシェルの動作確認に過ぎないような気がするが、裏でOSがリソースを管理してくれていると信じて動作確認は終了とする。

エミュレータ起動時の処理

ここからxv6の起動時の処理について調査する。調査に向け、xv6とRISC-Vのドキュメントを用意しておく。 xv6の場合、ドキュメントというより参考資料だが、xv6の作者らが書いたxv6: a simple, Unix-like teaching operating systemが参考になる。 RISC-Vについては仕様書、特にISA、を参照する。 QEMUを起動するコマンドは qemu-system-riscv64 -machine virt -bios none -kernel kernel/kernel -m 128M -smp 3 -nographic -global virtio-mmio.force-legacy=false -drive file=fs.img,if=none,format=raw,id=x0 -device virtio-blk-device,drive=x0,bus=virtio-mmio-bus.0 であったので、-kernelオプションを見ると、kernel/kernelがカーネルのようである。このファイルを調べたところELFファイルであったため、ELFヘッダを見るとEntry point addressは0x80000000である。

$ readelf -h kernel/kernel
ELF Header:
  Magic:   7f 45 4c 46 02 01 01 00 00 00 00 00 00 00 00 00
  Class:                             ELF64
  Data:                              2's complement, little endian
  Version:                           1 (current)
  OS/ABI:                            UNIX - System V
  ABI Version:                       0
  Type:                              EXEC (Executable file)
  Machine:                           RISC-V
  Version:                           0x1
  Entry point address:               0x80000000
  Start of program headers:          64 (bytes into file)
  Start of section headers:          262776 (bytes into file)
  Flags:                             0x5, RVC, double-float ABI
  Size of this header:               64 (bytes)
  Size of program headers:           56 (bytes)
  Number of program headers:         3
  Size of section headers:           64 (bytes)
  Number of section headers:         20
  Section header string table index: 19

GDBで0x80000000にブレイクポイントを設定し実行すると、スタックポインタ(sp)を更新するカーネルの前処理らしき関数_entryを確認できる。カーネルはCで書かれており、かつ、普通のCコンパイラはローカルな変数や一部の関数のプロローグでスタックを使うだろうから、カーネルを動かすためのスタックの準備は納得がいく。 auipc sp,0x9とcsrr a1,mhartid以外は算術命令やロード命令に見えるので、auipcとcsrrについて調べる。 auipcはプログラムカウンタ(pc)の値を使用した加算命令、csrrは特殊なレジスタ群(CSRs)のRead命令である。 csrrのオペランドのmhartidはHardware Thread(hart) IDを持つレジスタ(CSR)であり、各Hardware Threadごとに別々のspを設定していると思われる。結局、ここではspの更新が主な処理であり、spをなぜこのように計算するかは不明であるが時間がないので次に進む。しかし、最後startにジャンプする前のspの値を確認したところ0x8000aa30 <stack+8192>であるため、先に(0x80000000-)カーネルのコードがあり、その後(0x8000aa30-8192)にカーネルスタックがあるというメモリマップの雰囲気はわかる。最後はstartへジャンプし、カーネルのメインの処理へ移る。

Dump of assembler code for function _entry:
=> 0x0000000080000000 <+0>:     auipc   sp,0x9
   0x0000000080000004 <+4>:     ld      sp,-1904(sp) # 0x80008890
   0x0000000080000008 <+8>:     lui     a0,0x1
   0x000000008000000a <+10>:    csrr    a1,mhartid
   0x000000008000000e <+14>:    addi    a1,a1,1
   0x0000000080000010 <+16>:    mul     a0,a0,a1
   0x0000000080000014 <+20>:    add     sp,sp,a0
   0x0000000080000016 <+22>:    jal     ra,0x8000008c <start>
End of assembler dump.

上記の調査の過程で"xv6 0x80000000"などと検索しているうちに、xv6の参考資料の2.6節に"Code: starting xv6, the first process and system call"なる節があることに気がついた。この節には、xv6を起動してからシェルが起動するまでの過程が書いてあるので参考にする。また、カーネルをロードするアドレスは0x80000000である、といった決まりはQEMU-RISCVの実装に由来するようなので、QEMU-RISCVのブートに関するNOTEも参考にする。以上のxv6の資料とQEMU-RISCVの資料の情報を加えた上で、ここまでの処理をまとめる。 QEMUはCPUをリセットした後、メモリにbootROMを領域を設定し、pcがbootROMを指す(0x10000)ように設定する(kernel/memlayout.h)。 bootROMはカーネルがロードされているアドレス0x80000000(entry)にジャンプし、spの初期化を行う。スタックを設定することでCをコンパイルしたコードが動くようになる。 entryはstartを呼び出し、カーネルのメインの処理へ移る。ここまでをまとめると以上である。

ここで疑問に残るのは、GDBを起動し命令を追うと、bootROMから直接カーネルへジャンプしており、いつブートローダがカーネルを0x80000000にロードしたか不明である。仮説としては、QEMUがbootROMやカーネルをロードする場所を決めているのなら、QEMUがロードするのが自然である。 memmap[VIRT_DRAM].base = 0x80000000を参照しているQEMU-RISCVのコードを眺めると、関数void virt_machine_doneが見つかる。見てみると、関数riscv_load_kernelでstart_addr = 0x80000000にカーネルをロードしていることがわかり、QEMUがカーネルをロードしていることが分かった。

// https://github.com/qemu/qemu/blob/aa222a/hw/riscv/virt.c#L1238
static void virt_machine_done(Notifier *notifier, void *data)
{
    ...

    target_ulong start_addr = memmap[VIRT_DRAM].base;

    ...

    } else if (machine->kernel_filename) {
        kernel_start_addr = riscv_calc_kernel_start_addr(&s->soc[0],
                                                         firmware_end_addr);

        kernel_entry = riscv_load_kernel(machine, &s->soc[0],
                                         kernel_start_addr, true, NULL);
    ...
}

マシンモードにおける処理

次に、_entryが呼び出すstartを調べる。 startはkernel/start.cにある。ここでやたら出てくるM、m prefixはマシンモードのMである。 RISC-Vには特権レベルが（いまのところ）3段階あり、マシンモードが最も強い権限を持つモードである。 0. User/Application 1. Supervisor 2. (Reserved) 3. Machine

ここまでの命令はすべてマシンモードで実行されており、startはkernel/main.cで定義されているmain関数をスーパバイザモードで実行するための準備をする。例えば、mret命令はマシンモードからスーパバイザモードにリターンする命令であるため、w_mepc((uint64)main);でリターン先のアドレスを指定する。他にも、割り込みの有効化、割り込みが起きたときに呼び出されるトラップハンドラの登録をtimerinit関数で行う。準備ができたら、mretでリターンし、main関数に処理が移る。

// kernel/start.c
// entry.S jumps here in machine mode on stack0.
void
start()
{
  // set M Previous Privilege mode to Supervisor, for mret.
  unsigned long x = r_mstatus();
  x &= ~MSTATUS_MPP_MASK;
  x |= MSTATUS_MPP_S;
  w_mstatus(x);

  // set M Exception Program Counter to main, for mret.
  // requires gcc -mcmodel=medany
  w_mepc((uint64)main);

  // disable paging for now.
  w_satp(0);

  // delegate all interrupts and exceptions to supervisor mode.
  w_medeleg(0xffff);
  w_mideleg(0xffff);
  w_sie(r_sie() | SIE_SEIE | SIE_STIE | SIE_SSIE);

  // configure Physical Memory Protection to give supervisor mode
  // access to all of physical memory.
  w_pmpaddr0(0x3fffffffffffffull);
  w_pmpcfg0(0xf);

  // ask for clock interrupts.
  timerinit();

  // keep each CPU's hartid in its tp register, for cpuid().
  int id = r_mhartid();
  w_tp(id);

  // switch to supervisor mode and jump to main().
  asm volatile("mret");
}

OSのメイン処理

startはmretによりリターンし、main関数に処理が移る。 mainはkernel/main.cにある。 cpuid(=mhartid)が0のCPUのみ様々な初期化を行い、それ以外のCPUはページングの設定と割り込みの設定のみ行う。余談だが、レジスタmhartidはマシンモードでしか読み取れない。だからこそ、マシンモードであるstartの時点で他のレジスタ(tpレジスタ)に保存しておく必要があった。すべての初期化を見る時間もキャパシティもないので、シェルなどのユーザプログラムの実行について見ていく。

// kernel/main.c
void
main()
{
  if(cpuid() == 0){
    consoleinit();
    printfinit();
    printf("\n");
    printf("xv6 kernel is booting\n");
    printf("\n");
    kinit();         // physical page allocator
    kvminit();       // create kernel page table
    kvminithart();   // turn on paging
    procinit();      // process table
    trapinit();      // trap vectors
    trapinithart();  // install kernel trap vector
    plicinit();      // set up interrupt controller
    plicinithart();  // ask PLIC for device interrupts
    binit();         // buffer cache
    iinit();         // inode table
    fileinit();      // file table
    virtio_disk_init(); // emulated hard disk
    userinit();      // first user process
    __sync_synchronize();
    started = 1;
  } else {
    while(started == 0)
      ;
    __sync_synchronize();
    printf("hart %d starting\n", cpuid());
    kvminithart();    // turn on paging
    trapinithart();   // install kernel trap vector
    plicinithart();   // ask PLIC for device interrupts
  }

  scheduler();        
}

初期化を終えたあと、userinit関数を呼び出すことで最初のプロセスを作成する。 userinitでアロケートしたプロセスはuser/initcode.Sをユーザモードのプログラムとして実行する。なお、user/initcode.Sを直接使うわけではなく、initcode.Sの命令がバイナリでハードコードされているのが面白い。ハードコードするにはinitcode.Sのサイズは小さいことが求められる。そのため、initcode.Sは単にexec(2)を呼び出し、user/init.cに置き換える仕事のみする。 initはコンソール用のデバイスファイルを作成し、ファイルディスクリプタ開くことで入出力を整え、シェル(user/sh.c)を起動する。結果、kernel/userinit --(allocproc)--> user/initcode --(exec)--> user/init --(exec)--> user/shと順に呼ばれ、シェルはユーザから入力を受け付けることができるようになった。

ここでは、main.cはスーパバイザモードで実行されていたはずだが、いつユーザモードに切り替わったのか？どの命令で切り替わったのか？という疑問が残った。マシンモードからスーパバイザモードへ切り替えるmret命令があるのだから、スーパバイザモードからユーザモードに戻るsret命令はありそうだと思い、仕様書を見るとsret命令は存在した。おそらくsret命令を使ってユーザモードへ切り替えているが、コードを追うことはできなかった。

まとめ

xv6はQEMUで起動することが想定されており、カーネルがロードされると順に初期化が行われ、最後はシェルが起動する。この一連のソフトウェアにおける初期化は、bootROM -> _entry -> start -> main -> userinit -> user/initcode -> user/init -> user/shと徐々に権限レベルを絞る形で行われる。序盤はスタックの準備をしてCのコードが動くようにし、次にマシンモードでしかできない設定を整え、スーパバイザモードでOSの機能の初期化を行い、最後はexec(2)を用いることでユーザモードでシェルが起動した。

■ 興味ある分野に関する問い

セキュリティ・ネクストキャンプの講義の一覧を見て，その中から興味のある講義を選び，その講義で扱うテーマに対して自分が考えること，興味，疑問，課題，自分なりの考察などを説明してください．その分野について知識があるかどうかではなく，いかに興味や疑問を持ち，課題を考え，自分なりに調べて考察するかといった点を評価します．

『SimHでPDP-7ベアメタルプログラミング』に興味を持った。特に以下の記述である。

画面入出力(TTY)やシミュレーションされた当時のディスプレイ(ベクタースキャンディスプレイ)への描画等を行う予定です。

私がアセンブリを学んだとき、単なるレジスタ/メモリ計算や特殊レジスタの扱いなどに終始しがちだったので、描画について知れるのはありがたい。

取り組んでみたいこととしては、PDP-7のアセンブリを吐く電卓的な処理系を作り、それをPDP-7 on SimHで動かしてみたい。処理系が扱う対象は、四則演算、変数による値の束縛、関数適用ができる程度のものを想定している。これは、@rui314さんのによる簡単なプログラミング言語を作るライブコーディングにインスパイアされている。スタック操作を簡単にできるようなアーキテクチャ・ISAであれば、スタックマシンを実装できるので比較的楽に実装できそうだが、このあたりは要調査である。 x86_64のアセンブリしか書いたことがないため、当時の計算機が持つ機能の感覚はわからない。しかし、古い計算機の常識を知ると、当時のリソースが限られた中での工夫などを見れて面白そうである。

他のモチベーションとしては、これを機会にPDP-7のアセンブリを読めるようになれば、オリジナルのUNIXを読めるようになる（はず）ということである。 SimH上のPDP-7でUNIXを動かすプロジェクトも存在し、カーネルのコードもコメント付きで存在するのでおあつらえ向きである。

応募課題は以上です。

ueno’s diary

KLab Expert Camp（第6回：TCP/IPプロトコルスタック自作開発 #4）参加記

何ができた？

日程

1日目

2日目

3日目

4日目

5日目

まとめと感想

セキュリティ・ネクストキャンプ2023 応募課題晒し

はじめに

2023年度セキュリティ・ネクストキャンプ応募課題

■ あなたに関する問い

■ 課題への姿勢に関する問い

設定する課題

課題に対する調査

動作確認

エミュレータ起動時の処理

マシンモードにおける処理

OSのメイン処理

まとめ

■ 興味ある分野に関する問い

何ができた？

日程

1日目

2日目

3日目

4日目

5日目

まとめと感想

はじめに

2023年度 セキュリティ・ネクストキャンプ 応募課題

■ あなたに関する問い

■ 課題への姿勢に関する問い

設定する課題

課題に対する調査

動作確認

エミュレータ起動時の処理

マシンモードにおける処理

OSのメイン処理

まとめ

■ 興味ある分野に関する問い

2023年度セキュリティ・ネクストキャンプ応募課題