SecurityCamp2019参加体験記
まえがき
2019/8/13~17に行われた、セキュリティ・キャンプ全国大会2019のデータベースゼミに参加しました。ここでは、セキュリティ・キャンプではどのようなことをして、何を学んだかを書きます。
セキュリティ・キャンプ全国大会とは
セキュリティ・キャンプは4泊5日かけて一流の先生方がセキュリティに関する様々な知識を教えてくださるイベントです。選択コース、集中開発コース、ジュニア開発ゼミ、ネクストキャンプの4つがあります。どれも専門的な内容で、非常に貴重な講義ばかりです。しかも、交通費・宿泊費ともに無料で、フリーWifiもあります(記憶では、個室のWifiでも80Mbpsは超えていたような気がします)。
選択コース
数時間～1日単位で様々な講義を受けることができます。今回は、4つのコース(トラック)があり、それぞれテーマがあります。そのテーマに沿った講義があり、どれも非常に専門的な内容を扱います。
集中開発コース
僕が受講したコースは、集中開発コースの中のデータベースゼミです。集中開発コースは、手を動かして一つのものを作り上げるというコースです。例えば、データベースの他にも暗号化通信や自作言語などがありました。
ジュニア開発ゼミ
ジュニア開発ゼミは、集中開発コースの一つのゼミです。小中学生用のコースで、こちらもやることを自分で決め、プログラミングをします。今回はプロキシ関係の授業を最初にしたようで、プロキシを活用した面白いものを実装していました。ちなみに、ジュニア開発ゼミに参加しても次の年以降もジュニア開発ゼミ以外ならセキュリティ・キャンプに参加可能だそうです。
ネクストキャンプ
セキュリティ・キャンプは22才以下でないと参加できなく、セキュリティ・キャンプに二回参加することもできません。ですが、このネクストキャンプはセキュリティ・キャンプを受講した方が次のステップとして様々なことを学べる場として今年から作られたそうです。そのため、セキュリティ・キャンプに参加したことがある人も、ネクストキャンプに参加できます。さらに、年齢制限も25才までになっているそうです。
スケジュール
https://www.ipa.go.jp/jinzai/camp/2019/zenkoku2019programtimetable.html
このサイトに2019年度のプログラムがあるので、それを見ながら読むと良いと思います。
Day1
全体講義を受講しました。内容は、サイバー空間に関する法律の講義、パスワードシステムの現状と問題点の講義、コミュニティに関する講義の3つがありました。どれもわかりやすく説明されていました。
また、夕食を食べた後には、生徒も発表できるLT大会がありました。こちらでは、4つか5つのプロジェクターがあり、同時並行でLTをして、興味のあるところを見に行くことができました。
その後、グループワークがあり、「セキュリティ・キャンプ終了後に、参加者同士でチームを組んで活動するための仲間探し」が今回の目的でした。例えば、「CTFのチームを組んで活動する」とか「VRに関するコミュニティを作る」とかがありました。
Day2
ここから、選択コースと集中開発コースに分かれて作業をします。集中開発コースを受講した僕は、講師の星野先生と顔合わせをして、すぐに実装に移りました。集中開発コースでは、事前課題があり、必要な情報は基本的に事前課題を通して学びます。また、実装もセキュリティ・キャンプが始まる前に半分くらいは終わっているケースが多いです。
おやつの時間があり、通称「飲める税金」のペットボトルとアクエリアスを飲み、お菓子類を食べて雑談をしていました。複数のゼミが一つの部屋で作業していたので、ゼミを超えてゼミでやっていることや自分のしていることなどの雑談をしていました。
Day3
基本的には、Day2と同じですが、夕食後に会員企業のお仕事紹介がありました。これは、複数の企業の中から自分の興味のある企業のお話を聞くことができるというものです。
Day4
この日は、夕方に集中開発コース（ジュニア開発ゼミ含む）内での発表がありました。そのため、午前中にスライドを作って、余った午後の時間で更に実装をしていました。発表では、それぞれのゼミでどのようなことをしたのかを知り、その内容が非常に高度で驚きました。
また、プレゼント会がありました。プレゼント会では様々な技術書やBlackHatのグッズなどがあり、それらを参加者がもらうことができるという素晴らしい企画です。前は年齢順やじゃんけんで決めていたらしいのですが、今回はグループワークでのチーム名のハッシュ値の順番でした。実はこれには伏線があり、グループワークでチーム名を決めるように言われていたのですが、そのときに「チーム名は重要です」とおっしゃっていました。さらに、チーム名を登録するところの下の方にWhirlpoolと書かれていて、Whirlpoolはハッシュ関数の一つらしいです。ちなみに、それに気づいた人は誰もいなかったです。運良く僕はBlackHatのリュックサックと詳解ディープラーニングの本をGetすることができました。これを読んでセキュリティ・キャンプに参加するみなさん、どんな小さなことにも気を配る事が大事です！。
Day5
全員が集まり、選択コース・集中開発コース（ジュニア開発ゼミ含む）・ネクストキャンプそれぞれの発表を3時間程度かけて行いました。閉会式が終わった後、皆さん帰らずに1Fで話していて、スタッフの方に「電車の時間は大丈夫でしょうか？」と、遠回しに「早く帰りましょう」と言われていて少し面白かったです。
トランザクション処理について
ここから、データベースゼミでやったことについて説明します。
今回、トランザクション処理を実装した。トランザクション処理では、ACIDが重要になる。以下に、ACIDの説明を示した。
略称
|
正式名称
|
日本語訳
|
意味
|
A
|
Atomicity
|
原子性
|
操作がすべて実行されるか、すべて実行されないかのどちらかであること
|
C
|
Consistency
|
一貫性
|
トランザクション操作の前後で、制約を満たしていること
|
I
|
Isolation
|
独立性
|
操作の途中状態が、外から見えないこと
|
D
|
Durability
|
永続性
|
トランザクションが成立した場合、その結果は失われないこと
|
ただし、独立性とデータベースの速度はトレードオフの関係にあるため、独立性を完全に保証しているデータベースは少ないそうです。
今回作成したデータベース
• 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);
// 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;
}
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 ®istered_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;
}
}
}
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 ®istered_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;
}
}
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;
}
}
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;
}
{
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
の2箇所で公開しています。
の2箇所で公開しています。
コメント
コメントを投稿