セキュリティ・キャンプ2019に参加した話 #C++

この記事はNから始まる別称を持つパソコン部の部誌としても掲載します。盗作ではありません

追記(2020/11/05)

2019年度セキュリティ・キャンプMVPに選ばれました!

まえがき

　2019/8/13~17に行われた、セキュリティ・キャンプ全国大会2019のデータベースゼミに参加しました。ここでは、セキュリティ・キャンプではどのようなことをして、何を学んだかを書きます。
　また、一番最後には応募申請書に書いた内容を(一部を除き)貼り付けています。ぜひ参考にしてください。

セキュリティ・キャンプ全国大会とは

セキュリティ・キャンプは4泊5日かけて一流の先生方がセキュリティに関する様々な知識を教えてくださるイベントです。選択コース、集中開発コース、ジュニア開発ゼミ、ネクストキャンプの4つがあります。どれも専門的な内容で、非常に貴重な講義ばかりです。しかも、交通費・宿泊費ともに無料で、Wi-Fiもあります(記憶では、個室のWi-Fiでも80Mbpsは超えていたような気がします)。

選択コース

数時間～1日単位の様々な講義を受けることができます。今回は、4つのコース(トラック)があり、それぞれテーマがあります。そのテーマに沿った講義があり、どれも非常に専門的な内容を扱います。

集中開発コース

僕が受講したコースは、集中開発コースの中のデータベースゼミです。集中開発コースは、手を動かして一つのものを作り上げるというコースです。例えば、僕の受講したデータベースの他にも暗号化通信や自作言語などがありました。

ジュニア開発ゼミ

ジュニア開発ゼミは、集中開発コースの一つのゼミです。小中学生用のコースで、こちらもやることを自分で決め、プログラミングをします。今回はプロキシ関係の授業を最初にしたようで、プロキシを活用した面白いものを実装していました。ちなみに、ジュニア開発ゼミに参加しても次の年以降もジュニア開発ゼミ以外ならセキュリティ・キャンプに参加可能だそうです。

ネクストキャンプ

セキュリティ・キャンプは22才以下でないと参加できなく、セキュリティ・キャンプに二回参加することもできません。ですが、このネクストキャンプはセキュリティ・キャンプを受講した方が次のステップとして様々なことを学べる場として今年から作られたそうです。そのため、セキュリティ・キャンプに参加したことがある人も、ネクストキャンプに参加できます。さらに、年齢制限も25才までになっているそうです。

スケジュール

このサイトに2019年度のプログラムがあるので、それを見ながら読むと良いと思います。

Day1

　全体講義を受講しました。内容は、サイバー空間に関する法律の講義、パスワードシステムの現状と問題点の講義、コミュニティに関する講義の3つがありました。どれもわかりやすく説明されていました。

　また、夕食を食べた後には、生徒も発表できるLT大会がありました。こちらでは、4つか5つのプロジェクターがあり、同時並行でLTをして、興味のあるところを見に行くことができました。

　その後、グループワークがあり、「セキュリティ・キャンプ終了後に、参加者同士でチームを組んで活動するための仲間探し」が今回の目的でした。例えば、「CTFのチームを組んで活動する」とか「VRに関するコミュニティを作る」とかがありました。

Day2

　ここから、選択コースと集中開発コースに分かれて作業をします。集中開発コースを受講した僕は、講師の星野先生と顔合わせをして、すぐに実装に移りました。集中開発コースでは、事前課題があり、必要な情報は基本的に事前課題を通して学びます。また、実装もセキュリティ・キャンプが始まる前に半分くらいは終わっているケースが多いです。

　おやつの時間があり、通称「飲める税金」のペットボトルとアクエリアスを飲み、お菓子類を食べて雑談をしていました。複数のゼミが一つの部屋で作業していたので、ゼミを超えてゼミでやっていることや自分のしていることなどの雑談をしていました。

Day3

　基本的には、Day2と同じですが、夕食後に会員企業のお仕事紹介がありました。これは、複数の企業の中から自分の興味のある企業のお話を聞くことができるというものです。

Day4

　この日は、夕方に集中開発コース（ジュニア開発ゼミ含む）内での発表がありました。そのため、午前中にスライドを作って、余った午後の時間で更に実装をしていました。発表では、それぞれのゼミでどのようなことをしたのかを知り、その内容が非常に高度で驚きました。

　また、プレゼント会がありました。プレゼント会では様々な技術書やBlack Hatのグッズなどがあり、それらを参加者がもらうことができるという素晴らしい企画です。前は年齢順やじゃんけんで決めていたらしいのですが、今回はグループワークでのチーム名のハッシュ値の順番でした。実はこれには伏線がありました。1つ目の伏線は、「チーム名は重要です」とグループワークでチーム名を決めるように言われていたことです。2つ目の伏線は、チーム名を登録するところの下の方にWhirlpoolと書かれていたことです。Whirlpoolはハッシュ関数の一つらしいです。ちなみに、それに気づいた人は誰もいなかったです。運良く僕はBlack Hatのリュックサックと詳解ディープラーニングの本をGetすることができました。これを読んでセキュリティ・キャンプに参加するみなさん、どんな小さなことにも気を配る事が大事です！。

Day5

　全員が集まり、選択コース・集中開発コース（ジュニア開発ゼミ含む）・ネクストキャンプそれぞれの発表を3時間程度かけて行いました。閉会式が終わった後、皆さん帰らずに1Fで話していて、スタッフの方に「電車の時間は大丈夫でしょうか？」と、遠回しに「早く帰りましょう」と言われていて少し面白かったです。

トランザクション処理について

ここから、データベースゼミでやったことについて説明します。

今回、トランザクション処理を実装した。トランザクション処理では、ACIDが重要になる。以下に、ACIDの説明を示した。

略称	正式名称	日本語訳	意味
A	Atomicity	原子性	操作がすべて実行されるか、すべて実行されないかのどちらかであること
C	Consistency	一貫性	トランザクション操作の前後で、制約を満たしていること
I	Isolation	独立性	操作の途中状態が、外から見えないこと
D	Durability	永続性	トランザクションが成立した場合、その結果は失われないこと

ただし、独立性とデータベースの速度はトレードオフの関係にあるため、独立性を完全に保証しているデータベースは少ないそうです。

参考記事(qiita)

参考記事(wiki)

今回作成したデータベース

C++で実装
- STLなども使用
Read, Insert, Update, Delete, Crash Recovery, Commit, Abort処理が実行可能
Key-Value store
シングルスレッド

実装の内容

データ構造

DBファイルと、Logファイルは永続化されたデータである。DB on memoryは、DBファイルをメモリ上にコピーしたものである。Write Setは、Insert, Update, Delete処理を一時的に格納する。

DB on memory

DB on memoryは、以下のように実装した。

using Id = std::uint64_t;
// key-value store
using Columns = std::map<std::string, std::string>;
Record {
    Id id;
    Columns columns;
    enum Option {
        NO_OPTION,
        INSERT,
        UPDATE,
        DELETE
    };
    Option option; // write set用
};
std::map primary_index<Id, Record);

idは、すべてのRecordで重複することはないunsigned int型の変数である。また、Columnsには、(“name”, “yamada”)のようにデータを格納する。汎用性を重視したこの形にした。primary_indexは、idからRecordを検索するmap型の変数で、これがDB本体である。

また、本来なら、インデックス構造から自作するべきだが、時間の都合上省略した。

Write Set

Write Setは以下のように実装した。

std::map write_set<Id, Record);

Insert, Update, Deleteの操作の内容を直接DB on memoryに反映させるのではなく、write_setに一時的に格納する。これは、ログ先行書き込みによるAtomicityの担保と、Isolationを実現するために必要不可欠なものである。

DBファイル

Csv形式で保存している。(ただし、書き込みのコードは未実装)。

実際のデータの一部を以下に示す。

ID	Name	Age
1	Sato	82
2	Suzuki	23
3	Takahashi	91
4	Tanaka	29
5	Ito	58
6	Watanabe	23
7	Yamamoto	60
8	Nakamura	70
9	Kobayashi	31
10	Kato	36

Logファイル

Logファイルには、write_setの内容を保存する。

データの内容を以下に示す。

データの文字数0x1fデータのハッシュ値0x1fID0x1fkey0x1fvalue0x1fkey0x1fvalue ... 0x1fvalue0x1f^x1e

0x1fと0x1eはASCIIコードでユニット分離文字とレコード分離文字という名前がついていて、区切り文字として使用することができる。

上のデータを正確でないが、見やすい形に変換すると以下の通りだ。

データの文字数　データのハッシュ値　ID　Key　Value　Key　Value　...　Value

ここで、データの文字数とデータのハッシュ値のデータは、ID Key Value ... value 0x1f 0x1eの部分だ。

このデータの文字数とデータのハッシュ値は、Logファイルのデータの内容が壊れていないかをチェックしている。また、これら２つは固定長である。

Insert, Update, Delete, Read処理

Write Setに、Insert, Update, Delete処理を書き込む。Read関数は、Write Setに対象のデータがあるかチェックした後、DB on memoryのデータを検索する。

簡略化したサンプルコードを示す。そのため、一部の関数の仕様は実際の仕様と違う。

Insert

bool insertRecord(Record &record) {
    record.option = Record::INSERT;
    setId2Record(record);
    if(checkRecord(record) == false) { // record制約チェック
        std::cerr << "record check error" << std::endl;
        return false;
    }

    // write_setにrecordを代入する
    write_set[record.id] = record; 
    return true;
}

update

bool updateRecord(const Record update_record) {
    update_record.option = Record::UPDATE;
    if(checkRecord(update_record) == false) { // record制約チェック
        std::cerr << "record check error" << std::endl;
        return false;
    }

    auto write_set_itr = write_set.find(update_record.id);
    if(write_set_itr == write_set.end()) {
        // write_set内に対象のRecordは存在しない
        auto primary_index_itr = primary_index.find(update_record.id);
        if(primary_index_itr == primary_index.end()) {
            // primary_index内にも存在しない
            std::cerr << "there is no record" << std::endl;
            return false;
        }
        else {
            write_set[update_record.id] = update_record;
        }
    }
    else {
        Record &registered_record = write_set_itr->second;
        if(registered_record.option == Record::DELETE) {
            // すでにdeleteされている場合
            std::cerr << "the record deleted" << std::endl;
            return false;
        }
        else {
            write_set_itr->second = record;
        }
    }
}

delete

bool deleteRecord(const Record record) {
    record.option = Record::DELETE;

    auto itr = primary_index.find(reocrd.id);
    if(itr == primary_index.end()) {
        // primary_index内に存在しない
        std::cerr << "there is no record" << std::endl;
        return false;
    }
    else {
        write_set[record.id] = record;
    }
}

read

Record readRecord(Id id) {
    auto write_setitr = write_set.find(id);
    if(write_set_itr == write_set.end()) {
        // write_set内に存在しない場合
        auto primary_index_itr = primary_index.find(id);
        if(primary_index_itr == primary_index.end()) {
            // primary_index内に存在しない場合
            std::cerr << "there is no record" << std::endl;
        }
        else {
            return primary_index_itr->second;
        }
    }
    else {
        return write_set_itr->second;
    }
}

Commit処理

Write Setの内容を、Logファイルに書き込み、その後DB on memoryに反映していく。

簡略化したサンプルコードを以下に示す。

uint64_t getHash(std::string &str) // ハッシュ値を求める
{
    static std::hash<std::string> hash_fn;
    return hash_fn(str);
}

uint32_t getHashDigit() // 固定長の長さを求める
{
    const static uint32_t digit = std::to_string(UINT64_MAX).size();
    return digit;
}

bool saveWriteSet2LogFile() {
    std::ofstream file("redo.log");

    // start
    file << "CS" << endl;
    for(const auto &[id, record] : write_set) {
        std::string message;
        if(record.option == Record::INSERT) {
            message += "I\x1f";
            message += to_string(id) + '\x1f';
            for(const auto &[name, value] : record.columns) {
                message += name + '\x1f' + value + '\x1f';
            }
            message += '\x1e';
        }
        else if(record.option == Record::UPDATE) {
            message += "U\x1f";
            message += to_string(id) + '\x1f';
            for(const auto &[name, value] : record.columns) {
                message += name + '\x1f' + value + '\x1f';
            }
            message += '\x1e';
        }
        else if(record.option == Record::Delete) {
            message += 'D\x1f' + to_string(record.id) + "\x1f\x1e";
        }
        else {
            std::cerr << "undefined option " << record.option << std::endl;
            return false;
        }
        uint64_t hash = getHash(message);
        uint64_t message_size = message.size();

        file << << std::setfill('0') << std::setw(getHashDigit()) << to_string(message_size) << '\x1f' << std::setfill('0') << std::setw(getHashDigit()) << hash << '\x1f' << message;
    }
    // finish
    file << "CF" << endl;
    return true;
}

bool saveWriteSet2DbOnMemory() {
    for(const auto &[id, record] : write_set) {
        if(record.option == Record::INSERT) {
            primary_index[id] = record;
        }
        else if(record.option == Record::UPDATE) {
            primary_index[id] = record;
        }
        else if(record.option == Record::Delete) {
            primary_index.erase(id);
        }
        else {
            std::cerr << "undefined option " << record.option << std::endl;
            return false;
        }
    }
}

bool commit() {
    if(saveWriteSet2LogFile() == false) {
        return false;
    }
    if(saveWriteSet2DbOnMemory() == false) {
        return false;
    }
    ofstream file("redo.log", std::ios::out); // ファイル消去
    return true;
}

Crash Recovery処理

Crash Recoveryはcommit中に何らかの原因で電源が落ちてしまったときなどに実行する。Logファイルに保存された内容をWrite Setに反映し、もう一度DB on memoryに反映し、最後にDBファイルに書き込むことで永続化する。

ソースコードなど

GitHub : https://github.com/2lu3/SecurityCamp2019

スライド：https://docs.google.com/presentation/d/1pp14xrh3YfOMCrqWNIQlKCoC2H6WVyxI9LwYBbHOMl4/edit?usp=sharing

星野先生万歳！

その他

まだ書ききれていないこともあるので、また書き足します
この記事は、

Qiita : https://qiita.com/hi2lu3/items/7ddeb6d27474db6fbe7e

blogger: https://2lu3.blogspot.com/2019/08/securitycamp2019.html

名称がNから始まる部活の2020年度の部誌

の3箇所で公開しています。

応募申請書

あなたの好きなプログラミング言語について、どんなところが好きなのか教えてください

　僕が普段使っている言語は、C、C++、Java、Pythonです。このうち、文法やライブラリを最もよく知っているのはC言語で、他の3つはネットで検索しながら使っています。

　一番好きな言語は、Pythonです。理由は、様々なモノを短時間に作成可能だからです。もちろん、実行スピードは非常に遅いですが、プロトタイプを作るときには重宝しますし、非本質的な補助ソフトの開発に時間を取られたくないときに有用です。例えば、パソコン部での文化祭で展示した顔認識ソフトの開発時間はわずか15分です。

　また、C++も好きです。僕がC++を使うときは、たいてい実行速度が必要なときが多く、そのための最適なアルゴリズム・データ構造を調べて選び、自分のソフト用にカスタマイズする必要があります。この、カスタマイズをするときに、実行速度を速くするための様々な工夫を考えることが楽しいです。この楽しさは、Pythonや他の言語でも得ることは可能ですが、極限まで実行速度を追求する楽しさはC++でないと味わえません。

トランザクション処理やそれに関する技術のどんなところに興味を持ったのか教えてください．

　一言で言うと、僕はデータベースを作り、そのデータベースを活用する必要があり、データベースゼミは専門家の講義を受け質問をすることができるという点で、データベースを学ぶ絶好で唯一の機会です。もちろん、ネット上でも勉強は可能ですし、多くはネットから学べます。しかし、その分野の暗黙の了解や便利なツールというのは、その存在を知っていないと検索することすら難しいです(例えば、プログラミング初心者がメモ帳でプログラミングしているようなもの)。

　また、データベースの中でもトランザクション処理を勉強することで、より効率的なデータベースを作ることができるのではないかと思いました。

次の (3a)〜(3f) の中から 2 つ選んで説明してください．

たくさん時間をかける必要はありません(目安はひとつにつき 5?20 分くらい)．
調べる過程で分かったことだけでなく，分からなかったことや疑問に思ったことも書いてください．
参考にした書籍や Web ページの情報があれば全て書いてください．
(3a) ACID (atomicity, consistency, isolation, durability) について．
(3b) データ構造としての Hash table と Tree の違いについて．
(3c) Write-ahead Logging (WAL) について．
(3d) Serializability について．
(3e) キャッシュメモリについて．
(3f) 永続(不揮発)ストレージについて．

キャッシュメモリについて

　キャッシュメモリは、メモリアクセスを高速化するためのメモリで、メインメモリとCPUの間にあります(最近のパソコンの場合、キャッシュメモリはCPUチップ内部に取り込まれている)。

　キャッシュメモリはメインメモリよりも記憶容量ははるかに小さいですが、高速にメモリの値を読み書きすることが可能です。この理由は、それぞれのメモリのCPUからの距離にあります。光の速さを30万キロメートル毎秒として、コアのクロック周波数を5GHz(*1)とすると、1 clockで光の進む距離は6cmになります。つまり、CPUとメモリの距離によって、何clock後に目的の値が帰ってくるかが決まります(もちろん、メモリの中での目的のアドレスにアクセスするための時間もかかります)。そのため、CPUの中にあるキャッシュメモリはメインメモリに比べて、非常に高速にアクセスが可能です。

　キャッシュメモリには、メインメモリでアクセスされたアドレスの近くのデータを保存します。また、CPUは変数などを、まずキャッシュメモリに、もしなかったらメインメモリから探します。これにより、もし目的の変数などがキャッシュメモリにある場合は、非常に高速にメモリアクセスをすることが可能です。

　キャッシュメモリを有効活用するには、メモリアクセスの場所を、前回のメモリアクセスの場所に近づけたほうが良いです。つまり、２次元以上の配列などを扱う場合、メモリに保存されている順番に気をつける必要があります。具体的には、下のプログラムのようにしないといけません。

int array[10][20];

for(int i = 0; i < 10; i++) {

for(int j = 0; j < 20; j++) {

    array[i][j]+=1;

}

}

　キャッシュメモリ・メインメモリに保存された値は、パソコンの電源を切ると基本的に保存されません。つまり、キャッシュメモリ・メインメモリは揮発性メモリです。

　また、レジスタというCPUに非常に近い場所に配置されたメモリもあり、こちらは演算を高速化させるためのものです。

参考文献

永続(不揮発)ストレージについて．

　不揮発性メモリというのは、電源を供給しなくても値が保存されたままになるメモリのことです。

　不揮発性メモリには、アドレスを電気的に指定するものと、機械的に指定するものがあります。このうち、電気的に指定するものにはSSDなどがあり、機械的に指定するものには、HDD、磁気テープなどがあります。SSDはHDDと比べてデータの読み書きの速度が速いです。しかし、SSDはHDDよりもビット単価は高くなります。

　不揮発性メモリには、電源を切っても消失してほしくないデータを保存します。そのため、パソコンのサーバーのデータベースなどに利用されています。

参考文献

何かアピールしたいことがあれば自由に書いてください．この欄は空欄でも構いません．

　（省略：僕が何を学び、何をしたいかを書きました）

　また、僕はアルゴリズムやデータ構造も必要最低限は知っているので、データベースゼミを受講することで非常に有意義な学びを得ることができる自負があります。（省略：アルゴリズム系の大会の実績を書きました）

　同時に、数時間～数日単位の開発である（省略：上に挙げた大会）だけではなく、年単位でのプログラムの開発も行っているので、エラーに対する根気強さや長時間・長期間のプログラミングに慣れています。（省略：なぜ慣れているのかの根拠・実績を書きました）

　僕は、このデータベースゼミに誰よりも真剣に臨み、非常に多くの学びを得ようと思っています。どうか、どうか、よろしくおねがいします。