pico CTFでweb問題を解いてみる #3
picoCTF、web問題の続き。
今回は300point~
Irish-Name-Repo 1
https://play.picoctf.org/practice/challenge/80?category=1&page=1
irishって聞いて、アヤメかなぁ〜と思って指定ページを開いたら外人さんの写真がずらっと出てきた。そういえばアヤメはirisだった。
...と、そんなことはどうでもよくて、今回はアイルランド人(irish)の画像の掲示板みたいなサイトに飛ばされた。サイトの構成としては、
①画像表示ページ
②サポートページ(ユーザからきた質問とadminからの回答が書いてある)
③管理者用ログインページ
の3つで出来ている。問題文に「ログインしてみてくれ」と書いてあったのでとりあえず③に飛んでみた。するとログインフォームが表示されユーザー名とパスワードを求められる。空白にしたり適当な文字列を入力してログインを試みるも、login failedと書かれたところに飛ばされてしまう。
300点問題だしどうせ無駄かなぁと思いつつ、ダメもとで「admin' --」と入力してみるとログインできた。これなら200点問題の「web gauntlet」の方が難しかったぞ...と思った。
picoCTF{s0m3_SQL_c218b685}
Irish-Name-Repo 2
https://play.picoctf.org/practice/challenge/59?category=1&page=1
前問の亜種。50点上がって350点問題。
サイトの構造が全く同じなので、きっとエスケープ処理とかが施されてるんだろうなぁ〜なんて思いつつ、とりあえず今回も「admin' --」を入力してみる。
通ってしまった。なんやねん...
picoCTF{m0R3_SQL_plz_fa983901}
Java Script Kiddie
https://play.picoctf.org/practice/challenge/29?category=1&page=1
問題文には「画像リンクが壊れている」とだけ書かれている。指定されたページに飛ぶと小さい入力フォームだけがあった。
とりあえず適当に文字を入力するとフォームの下に画像が表示された。といっても正しく読み込めていないようで、画像ということを示すアイコンだけが表示されている状態。肝心の画像はわからない。試しに右クリックして画像リンクを取得してみると
data:image/png;base64,V4JOvABUGp2P7/lS+NTvUsNQAc8NBgEAd/NJwU4khWxVAAAOALpEAADeAPMAGK6jfgCF/ImxeQoAAADtST8AZGAUA+A7qxByAAAARQBERJOJs25wSnnuQQEAnACbAF94AOniKE7C+CxUANANKUiKO6RiRwDRAGOwYXjKAIfANmVA/FFHzQrzhR4Wfe0DXVoqSd0ZcvMAdBYEAztLvHep3aG4sgJJSectDmNmmaayzjZ/VPC/3AqjUUDOgIRmxUh/7/1OXQgW78+Sb4/vG/McAK2fxDD3HFRiPzSr1tYa6f5Bam87Sf+Ub2dbFM7eRvzHoXz1vGZRn3euM77zN/Oc+Xx9Ao+/G3eLflgS96vjSEI2+wBQq5JxrQRP09jWendz4S0YNixMK/0F62j4YAjlyEtA6dkXVyj+u2u1yLXptVHnq6VS/sTvMytyqkn5MnLJikALy5vA+eIjvJzfKNlDS2QtXWapDSLFUK/SgInJpy2MUqs41BF+cYvlf9+1DwB03brb5jjpHw/5SneYLCniPCP9rGEgiemlI7VoUNk4us3UD0BR5uaZPvv7L5eNbCAZQQv9d8mT8wsf9+k2ftmIjb/iidWD72SRl5Z3fJ/Lvj8SqtKvet/fcnw7XfWxZA85P++lkA2VIMYnNDVxYVu6TFtKz4XQAPXx9Ul6wd+fUq/xn+fNGFxLC/dNN6oHX3+PYM/yjpni8l2jbrkavASyZp9hNTq6rO8GTtdBnFqWcM1JTJWjn/ItkxDSMf5SfsgePr7mAlartcW5hKqZUr+a65M3OVz8MM92v6r9NX9ej3rm/pqXujeghH45t9mBtV//I98yRk1rZMsRPaMR45O2uE9+7xxzn/5vWvoOzrmJu43n0/H5J2ODX9Iyk/Fff2fvcaXfpPUj54Sm3PHPQ7KUHZxewkrebgDza56t1tL5VEJrKADLiqQA8Qltk89VHcw=
となっていた。
フォームに正しい文字を入力する復号できるといった感じかもしれない。
問題タイトルがJava script kiddyとなっているし、ここで一旦ソースを見てみる。
<script> var bytes = []; $.get("bytes", function(resp) { bytes = Array.from(resp.split(" "), x => Number(x)); }); function assemble_png(u_in){ var LEN = 16; var key = "0000000000000000"; var shifter; if(u_in.length == LEN){ key = u_in; } var result = []; for(var i = 0; i < LEN; i++){ shifter = key.charCodeAt(i) - 48; for(var j = 0; j < (bytes.length / LEN); j ++){ result[(j * LEN) + i] = bytes[(((j + shifter) * LEN) % bytes.length) + i] } } while(result[result.length-1] == 0){ result = result.slice(0,result.length-1); } document.getElementById("Area").src = "data:image/png;base64," + btoa(String.fromCharCode.apply(null, new Uint8Array(result))); return false; } </script>
早速読んでみる。
最初の数行で行っているのは、https://jupiter.challenges.picoctf.org/problem/17205/bytes というページから文字列を取得して、空白で区切ってから配列に格納するという処理。
お次はassemble_png()関数。ここでは入力キーをもとに複合してるっぽい。if文の中とかを見るとキーは16桁ということもわかる。
さてfor文。まずshifterという変数が登場するが、ここには入力キーのi桁目を文字から数値に変換したものが入る(48という数は'0'の文字コード)。 そして続くfor文の中では、bytes中の要素をshifterをもとにズラしてresultへ格納している。
※ "ズラし方"について説明文を書こうと30分くらい画面と格闘したのですが...文字で書くには複雑すぎてうまくまとめられませんでした。後ほどwriteupを探してみたら、アニメーションでわかりやすく解説されているページがありましたので、よければpicoCTF 2019 - JS Kiddie writeup. Solving two picoCTF web challenges for… | by @radekk | Mediumをご覧ください。
続くwhile文では「resultの最後の要素が0であれば取り除く」というのを繰り返して末尾の連続する0を取り除いており、その後最後に画像のsrcを設定。
以上がコードの中身。
ここからやるべきは正しい16桁のキーを見つけることだが、総当たりで探すには少しばかり数が多すぎる。候補を絞り込むために、pngのファイルシグネチャに着目。pngは先頭16バイトが 137 80 78 71 13 10 26 10 0 0 0 13 73 72 68 82 となるので、bytesの中身から正しい入力キーを逆算できそう。
ともあれ1行になっている状態じゃぁ読みにくいので、簡単なプログラムを書いて16列になるように整列表示
// 雑に書いてます。見辛かったらごめんなさい、 #include <iostream> #include <vector> #include <iomanip> using namespace std; int main() { int byte_num, count16=0; vector<int> splited_bytes; while(cin >> byte_num){ splited_bytes.push_back(byte_num); } for (auto it = splited_bytes.begin(); it != splited_bytes.end(); ++it){ count16++ ; cout << setw(3) << *it << " "; if(count16 == 16){ count = 0; cout << endl; } } }
出力(全45行)↓
これを見るだけで、51081803[a][b][c]63640 まで絞れる。
([a][c]は2or3or4, [b]は3or4or5or6)
このレベルなら総当たりでもいいかなって思って、試すと
51081803[4][5][3]63640 を入力した時に画像が出てきた。
読み込むと picoCTF{066cad9e69c5c7e5d2784185c0feb30b}
これを提出したら無事正解できた。長かった...
余談だけども、htmlの画像指定にbase64が使えることは今回初めて知った。「画像をhtmlに直接埋め込むことでサーバへのHTTPリクエストを削減でき高速化につながる」というメリットもあるらしい（画像が小さい場合に限る）
疲れたのでこの辺で。
pico CTFでweb問題を解いてみる #2
web問題writeupの第二回目です
picobrowser
https://play.picoctf.org/practice/challenge/9?category=1&page=1
問題文には「picobrowserだけがflagを表示できる」と書いてあった。とりあえずpicobrowserと検索してみたらandroidアプリがヒットしたけれど...もし仮に「このアプリをインストールしてページを見ろ」ってことだとすると、iOS勢じゃ解けないっぽいし、とりあえず保留にして別の方法を考えることにした ※
さて、このページには"flag"と書いてあるボタンのみが設置されており、試しにクリックしてみるものの「 You're not picobrowser! Mozilla/5.0 ~~~」と表示されてしまう。そこで「ブラウザ 偽る」とか調べてみると、”ユーザーエージェント”とかいうものが出てきた。どうやらこれを使うっぽい。さらに調べていくと、chromeのデベロッパーツールにはnetwork conditionsという項目があり、そこで任意のブラウザ名に変更できるということだったので、"picobrowser"に変更してから"flag"ボタンを押してみると、見事flagを取得できた。
※問題を解いた後、興味本位でアプリDLしてflagを見れるか確認してみたけど「You're not picobrowser!」って表示されてしまい、笑ってしまった。
Web Gauntlet
https://play.picoctf.org/practice/challenge/88?category=1&page=1
問題文には「adminとしてログインしてみろ」と書いてある。問題サイトに飛んでみるとログインフォームがあって、usernameとpasswordという項目がある。SQLインジェクションだと思うが、添付ページを見てみるとどうやら"or"というキーワードはフィルター処理されてるみたいなので、「'OR 1=1」とか入力しても無駄っぽい。
とりあえずユーザー名に"admin"、パスワードに適当な文字を入力してみると
SELECT * FROM users WHERE username='admin' AND password='a'
と表示された。このSQL文が実行されているっぽい。
ユーザ名に 「admin'--」、パスワードには適当な文字列を入力してみた。
SELECT * FROM users WHERE username='admin' -- AND password='a'
無事突破できた。
...と思ったらRound2という表示とともに別のフォームが出てきた。添付ページを見ると、今度は [or] [and] [like] [=] [--] というワードがフィルター処理されてしまってるらしいのでRound1の方法は使えない。SQLコメントの別の書き方について調べてみたら/* */とかが出てきたので。ユーザ名「admin' /*」パスワード「*/ '」とか試してみたんだけど...まぁ正しい文になってないし当然うまくいかない。ネットで20分くらい色々なSQLを見た時、ふと、[;]を使えばSQLを終了できるのではないかという考えに至って、ユーザー名に「admin';」と入力してみたところ突破できた。
Round3に入った。 [>] [<] が追加でフィルターになっている。 [;]が禁止になっていないなら多分Round2と同じようにやれば解けそうだなぁと思ったら案の定解けた。
Round4では [admin]という単語そのものがフィルターになってて使えなくなった。adminという単語を使わずにadminユーザーの情報を持ってこなければいけないらしい。そこで、adminの一部を大文字にしてみたり、単語の中に/**/を挿入してみたり、admadminin(adminという文字が取り除かれるとadminになる)とかも試したけれど全て無駄だった。万策尽きたのでwriteUPを探すことにした...
解法の一つとしてUNION句を使うやり方が紹介されていた。データーベースの中ではadminが一番最初の行にあるだろうという予想のもとで、「UNIONで複数のクエリを結合」→「LIMIT 1を指定することで一番上のものを取得する」という手順によって解いていた。SQLコードで示すと
SELECT * FROM users WHERE username='bob' UNION SELECT * FROM users LIMIT 1;
これで行ける
...と思いきや実はまだダメ。空白文字が禁止されているらしい。
SQL Injection: Bypassing Common Filters - PortSwiggerを見てみると、
/**/は空白文字に置換して扱ってくれるということが書いてあるので、
ユーザー名を bob'/**/UNION/**/SELECT/**/*/**/FROM/**/users/**/LIMIT/**/1;とし、パスワードに適当な文字列を入れたところうまく行った。
（参考writeup: https://www.youtube.com/watch?v=ZQj5tSwaG0k）
次にRound5。ここにきて[union]が禁止されてしまった。いろいろ調べてみたところ、sqlでは||による文字列の連結が行えるということだったので、adminをaとdminに分割してみた。つまり
SELECT * FROM users WHERE username='a'||'dmin';
としてみた。無事突破できた（多分Round4もこのやり方なら突破できただろうと思う）
こうしてflagを獲得したのであった↓
picoCTF{y0u_m4d3_1t_96486d415c04a1abbbcf3a2ebe1f4d02}
flag入力する時に気づいたけど、pico CTFの問題ページにヒント載ってるので、次詰まったらまずそこをみようと思った。
Open-to-admins
https://play.picoctf.org/practice/challenge/1?category=1&page=1
"管理者として"、"14:00ぴったり"にボタンを押すとフラグが得られるとのこと。色々調べたけど分からなかったのでヒントを見るとcookieが役に立つと書いてあった。前に似たような問題を解いた時はcookieの値を書き換えるだけで大丈夫だったけど、今回はadminとかtimeとかいう属性は一つもない。調べていくキーワードとかも全然思い浮かばなかったので潔くwriteupを見た。ついでに、いい機会だと思ったので改めてcookie(ついでにセッション)についても勉強しなおした。
さて結果から言うと「adminという属性を追加して値をtrueにし、timeという属性を追加して値を1400に」するというのが本問の答えっぽくて、実際それで解けた。内心「運じゃん」と思った。picoCTFは問題の良し悪しを評価できるようになっているのだがこの問題だけ異様にbadが多い。そういうことだと思う...。
picoCTF{0p3n_t0_adm1n5_132f8585}
これで200点問題まではおしまい。
なんかもうwriteup無しでやっていけるのか不安だけど、それでも、わからなかった部分はちゃんと理解して進めるようにしたい。
pico CTFでweb問題を解いてみる #1
前書き
最近Webまわりの勉強をしていて、HTML, CSS, JavaScript, Ruby, Rails, PHP, SQL, NodeJSあたりを(一部は復習しつつ)一通り触ってみました。とりあえず次のステップとして、学んだことを活かして簡単なものを作ってみる...のもよいと思ったのですが、学んだことを使ってそのまま自力で実装したところでどうしても"汚い"ものが出来そうだと思ったので、まずはいろんなコードに触れてみることを優先することにしました。
色々考えたあげく、WebまわりのCTFを解いてみるという発送に至りました。よくある脆弱性をしっかりと把握しておくことはサービスを開発する上でも非常に重要なことだと思いますし、周辺知識を固めたり、いろんなコードを読むという意味でもCTFは非常に良い教材だと思います。
で、どの常設CTFがいいかなぁと思ってぱぱっとググってみたところ、picoCTFあたりが求めているものに近そうだったので (それに教材をじっくり選ぶ時間の方が無駄かなと思うので) こちらをやってみようと思います。とりあえず分野は"Web exploitation"に絞って網羅的にやっていくことにします。
なお、writeupについては散々ネットに転がっていますし、本記事はあくまでも個人的な備忘録として残すための目的で書くつもりです。
Insp3ct0r
https://play.picoctf.org/practice/challenge/18?category=1&page=1
指定されているサイトに飛んでみたら、「このページはHTML、CSS、Javascriptで書かれています」という記述があったので、とりあえずソースを表示してこれらを確認してみる。
するとHTMLには
<!-- Html is neat. Anyways have 1/3 of the flag: picoCTF{tru3_d3 -->
CSSには、
/* You need CSS to make pretty pages. Here's part 2/3 of the flag: t3ct1ve_0r_ju5t */
/* Javascript sure is neat. Anyways part 3/3 of the flag: _lucky?2e7b23e3} */
という感じで、それぞれコメントとしてflagが載っていたので、連結すると
picoCTF{tru3_d3t3ct1ve_0r_ju5t_lucky?2e7b23e3}
logon
https://play.picoctf.org/practice/challenge/46?category=1&page=1
指定サイトに飛んだところ、ログインフォームが表示された。とりあえずIDとパスワードに適当な文字列を入力してみたところ、「Success: You logged in! Not sure you'll be able to see the flag though」というメッセージが表示された（その後、IDの部分をadminに変更したり、全て空白でログインを試みても同様のメッセージが表示された）
最初はSQLインジェクションとか使うのかなぁと思っていたけどなんか違うっぽいので、とりあえずいろいろ見てみていたら、Cookieの項目の中に"admin"というものがあって"False"が設定されていた。ここをTrueに書き換えてみてページを再読み込みしてみるとFlagを得ることができた。
picoCTF{th3_c0nsp1r4cy_l1v3s_0c98aacc}
where are the robots
https://play.picoctf.org/practice/challenge/4?category=1&page=1
指定サイトに飛ぶと、「Welcome Where are the robots?」という文字だけが表示されたシンプルなサイトに飛んだ。ざっくりソースとかcookieとか見てみたけど役に立ちそうなものは何もない。そもそもrobotsってなんだろうって思ってとりあえず「web robots」とggってみた。すると検索候補にrobots.txtとか出てきたので、これだ！と思ってその辺りを色々見てみた。
「あぁ、robotってウェブのクローラーのことか〜」とかいろいろ思いながら読んで、とりあえずrobots.txtというファイルがどっかにあるんだろうということはわかった。さらに調べていくとrobots.txtはサイトのルートディレクトリに設置されているということだったので、指定サイトに *****/robots.txtと入力すると、
User-agent: * Disallow: /1bb4c.html
と表示された。 これをもとに、*****/1bb4c.html と入力すると、flagが記載されたページに飛んだ。
picoCTF{ca1cu1at1ng_Mach1n3s_1bb4c}
dont-use-client-side
https://play.picoctf.org/practice/challenge/66?category=1&page=1
サイトに飛んだら、「This is the secure login portal Enter valid credentials to proceed」と書いてあって、小さい入力ホームが添えられていた。とりあえずいつものようにページのソースとか覗いてみたら、
<script type="text/javascript"> function verify() { checkpass = document.getElementById("pass").value; split = 4; if (checkpass.substring(0, split) == 'pico') { if (checkpass.substring(split*6, split*7) == '706c') { if (checkpass.substring(split, split*2) == 'CTF{') { if (checkpass.substring(split*4, split*5) == 'ts_p') { if (checkpass.substring(split*3, split*4) == 'lien') { if (checkpass.substring(split*5, split*6) == 'lz_b') { if (checkpass.substring(split*2, split*3) == 'no_c') { if (checkpass.substring(split*7, split*8) == '5}') { alert("Password Verified") } } } } } } } } else { alert("Incorrect password"); } } </script>
というjsのコードがあった。flagは、文字列を並び替えれば得られる。
picoCTF{no_clients_plz_b706c5}
Client-side-again
https://play.picoctf.org/practice/challenge/69?category=1&page=1
とりあえず問題のタイトルがclient-sideということなのでソースを見てみた。
<script type="text/javascript"> var _0x5a46=['f49bf}','_again_e','this','Password\x20Verified','Incorrect\x20password','getElementById','value','substring','picoCTF{','not_this'];(function(_0x4bd822,_0x2bd6f7){var _0xb4bdb3=function(_0x1d68f6){while(--_0x1d68f6){_0x4bd822['push'](_0x4bd822['shift']());}};_0xb4bdb3(++_0x2bd6f7);}(_0x5a46,0x1b3));var _0x4b5b=function(_0x2d8f05,_0x4b81bb){_0x2d8f05=_0x2d8f05-0x0;var _0x4d74cb=_0x5a46[_0x2d8f05];return _0x4d74cb;};function verify(){checkpass=document[_0x4b5b('0x0')]('pass')[_0x4b5b('0x1')];split=0x4;if(checkpass[_0x4b5b('0x2')](0x0,split*0x2)==_0x4b5b('0x3')){if(checkpass[_0x4b5b('0x2')](0x7,0x9)=='{n'){if(checkpass[_0x4b5b('0x2')](split*0x2,split*0x2*0x2)==_0x4b5b('0x4')){if(checkpass[_0x4b5b('0x2')](0x3,0x6)=='oCT'){if(checkpass[_0x4b5b('0x2')](split*0x3*0x2,split*0x4*0x2)==_0x4b5b('0x5')){if(checkpass['substring'](0x6,0xb)=='F{not'){if(checkpass[_0x4b5b('0x2')](split*0x2*0x2,split*0x3*0x2)==_0x4b5b('0x6')){if(checkpass[_0x4b5b('0x2')](0xc,0x10)==_0x4b5b('0x7')){alert(_0x4b5b('0x8'));}}}}}}}}else{alert(_0x4b5b('0x9'));}} </script>
javascriptがだらだらと書いてあったが...前問と違って読みにくい。調べてみたところ、google chromeにはコードを整形してくれる機能がついてるっぽいので、とりあえずそれを使ってみた。
<script type="text/javascript"> var _0x5a46 = ['f49bf}', '_again_e', 'this', 'Password\x20Verified', 'Incorrect\x20password', 'getElementById', 'value', 'substring', 'picoCTF{', 'not_this']; (function(_0x4bd822, _0x2bd6f7) { var _0xb4bdb3 = function(_0x1d68f6) { while (--_0x1d68f6) { _0x4bd822['push'](_0x4bd822['shift']()); } }; _0xb4bdb3(++_0x2bd6f7); }(_0x5a46, 0x1b3)); var _0x4b5b = function(_0x2d8f05, _0x4b81bb) { _0x2d8f05 = _0x2d8f05 - 0x0; var _0x4d74cb = _0x5a46[_0x2d8f05]; return _0x4d74cb; }; function verify() { checkpass = document[_0x4b5b('0x0')]('pass')[_0x4b5b('0x1')]; split = 0x4; if (checkpass[_0x4b5b('0x2')](0x0, split * 0x2) == _0x4b5b('0x3')) { if (checkpass[_0x4b5b('0x2')](0x7, 0x9) == '{n') { if (checkpass[_0x4b5b('0x2')](split * 0x2, split * 0x2 * 0x2) == _0x4b5b('0x4')) { if (checkpass[_0x4b5b('0x2')](0x3, 0x6) == 'oCT') { if (checkpass[_0x4b5b('0x2')](split * 0x3 * 0x2, split * 0x4 * 0x2) == _0x4b5b('0x5')) { if (checkpass['substring'](0x6, 0xb) == 'F{not') { if (checkpass[_0x4b5b('0x2')](split * 0x2 * 0x2, split * 0x3 * 0x2) == _0x4b5b('0x6')) { if (checkpass[_0x4b5b('0x2')](0xc, 0x10) == _0x4b5b('0x7')) { alert(_0x4b5b('0x8')); } } } } } } } } else { alert(_0x4b5b('0x9')); } } </script>
かなり読みやすくなった。
この形は前問と同じ構造っぽくて、function_verify()でパスワードのチェックをしてるらしい。ただjavascriptの難読化が厄介で、2-30分ほど格闘したけど変数名とか綺麗に書き換えるのは(少なくとも今の自分のレベルだと)厳しかった。
まぁ前問の構造を踏まえて考えると _0x4b5b('0x**') という部分を見ればflagは得られそうだったため、console上でconsole.logを用いてひとつづつ出力し、並べてみたら正解にたどり着くことは可能だった。
picoCTF{not_this_again_ef49bf}
javascriptの難読化についていろいろ調べながらわかったけど、難読化はあくまでも”読みにくくしている”だけであって、セキュリティ対策としては不十分らしい（とはいえ難読化にはそのほかにもメリットとかはあるっぽい）
こちらのスライドがよかったので共有しておきます↓
JavaScript難読化読経
とりあえず続きはまた。
OverTheWire のbanditをやる（途中）
途中までだけど、とりあえず詰まってしまったのでできてるところまで...
周辺知識を理解するところまでが最終的な目標ですが、まずは解ききることを優先します。どうしてもわからない所はwrite upを見るつもりですがなるべく自分で...
※ちょっと放棄気味(18/12/29/14:34)
Level0→1
ユーザ名bandit0,ホスト名bandit.labs.overthewire.orgでsshするだけ。パスワードは書いてある通りbandit0に。
Level1→2
ホームディレクトリのreadmeをcat等で読むだけ
boJ9jbbUNNfktd78OOpsqOltutMc3MY1
Level2→3
-っていうファイル名なので、"cat -" とかやるとオプションと勘違いされちゃう。絶対パスで指定する。
$ cat /home/bandit1/-
CV1DtqXWVFXTvM2F0k09SHz0YwRINYA9
Level3→4
ファイル名にスペースが入ってるのでバックスラッシュ\でエスケープさせる
$cat spaces\ in\ this\ filename
UmHadQclWmgdLOKQ3YNgjWxGoRMb5luK
Level4→5
$ls -a すると、隠しファイル”.hidden”があったからcatで読む。
pIwrPrtPN36QITSp3EQaw936yaFoFgAB
Level5→6
”-file00”から”-file09”の9つのファイルがあってhuman-readableなものを探せってことだった。
$ file /home/bandit4/inhere/-file0*
って打ってみたら-file07だけASCII textだったのでcatで読んだ。
koReBOKuIDDepwhWk7jZC0RTdopnAYKh
Level6→7
inhereディレクトリのなかに更にmaybeinhere01からmaybeinhere19まであって、更にその中にもいくつかファイルがある。人間が読める,1033バイト,実行不可っていう条件があるのでfindコマンドで探すことにした。
$ find /home/bandit5/inhere/ -size 1033c
って打ったら、/home/bandit5/inhere/maybehere07/.file2だけが条件に当てはまった（他の条件は使わなかった）のでこれをcatした。
DXjZPULLxYr17uwoI01bNLQbtFemEgo7
Level7→8
level6と同じ感じだけれど今度は検索すべき範囲がサーバ全体っていうことに加えて条件も変わった。所有者はbandit7、所有グループはbandit6,サイズが33バイト。findのオプションについて調べていたら-lsが使えそうだったので
$ find / -size 33c -ls|grep bandit7
ってやったらだいぶ絞り込めた。
適当にcatして、/var/lib/dpkg/info/bandit7.passwordというところにあった。
HKBPTKQnIay4Fw76bEy8PVxKEDQRKTzs
Level8→9
”英単語 + flagっぽい文字列”っていうのがひたすら並んでた。
これはgrepするだけででいい。
cvX2JJa4CFALtqS87jk27qwqGhBM9plV
Level9→10
ひたすら並んでる中で、重複していない行のものがフラグだよってこと。“cat 重複”とかGoogleで調べてるうちにuniqコマンドがあったことを思い出した。
$ sort data.txt |uniq -u
UsvVyFSfZZWbi6wgC7dAFyFuR6jQQUhR
Level10→11
catすると一見文字化けして読めないように見えるけれど、いくつかの’=‘文字で始まるhuman-readableな文字列があるらしい。そういうことならstringsコマンドで良さそう。
$ strings data.txt とやって該当するものが見つかった
truKLdjsbJ5g7yyJ2X2R0o3a5HQJFuLk
Level11→12
Base64で暗号化されてるので、
$ base64 data.txt -d
でデコードするだけだった。（この程度なら反射的に解けちゃうんだけども、そもそも暗号周り全然知らないから勉強しなきゃなぁ…）
IFukwKGsFW8MOq3IRFqrxE1hxTNEbUPR
Level12→13
ROT13。戻してくれるページを調べて、そこに投げておしまい。
5Te8Y4drgCRfCx8ugdwuEX8KFC6k2EUu
Level13→14
去年一回解いたはずの問題なんだけど、改めて見たらそもそもhexdump(16進ダンプ)ってなんだっけって感じになって色々調べた。どうやらバイナリとか色んなデータをそのまま16進数の形式で表示するらしい。xxdコマンドの-rオプションを使えば復元出来るみたいなので、/tmp下にディレクトリを作って
$ xxd -r data.txt > /tmp/myname_yamahiro/test
とやってみて、次にこいつをfileコマンドで調べてみた。
/tmp/myname_yamahiro/test: gzip compressed data, was…(略)ということで、どうやらgzipで圧縮されているらしい。gzip -d testってやったらunknown suffix -- ignored って出てきて、どうやら拡張子を.gzにしないとダメみたいだったのでmv test test.gz でファイル名を変更してからgzip -d test.gzってやったらちゃんと展開できた。
ここで出てきたtestっていうファイル（さっきのtestとは別物）をfileコマンドで調べるとbzip2だったから、拡張子.bz2を付けて更に展開。
こんな感じで出てきたものを何度も展開していくとbata5.binというやつが出てくる…と思ったらこいつもtarだった時はイラッとしたけど、本当に最後まで展開したら8ZjyCRiBWFYkneahHwxCv3wb2a1ORpYLというflagが出てきた…疲れたなぁ。
Level14→15
次のlevelに進むために必要なパスワード(flag)が別のユーザしか読めないファイルに書いてある。パスワードはわからないけどssh鍵はあるということなので、sshの-iオプション使い、ssh -i sshkey.private bandit14@localhost で入って、さっきのファイルをcat。4wcYUJFw0k0XLShlDzztnTBHiqxU3b3e
Level15→16
ネットワークは今までロクに勉強してこなかったから、サーバに文字列投げるだけだけど分からなかった。仕方ないのでとりあえずnc(というコマンドがネットワークのスイスアーミーナイフってことだけは授業で習って知っていたので)調べた。…まぁncの一番基本的な使い方なので秒で出てきた。
nc localhost 30000 ってやって、前問で得たflagを投げてみたらcorrect!って言ってflagを得られた。BfMYroe26WYalil77FoDi9qh59eK5xNr
Level16→17
SSL暗号化通信してlocalhostの30001番ポートに前問のパスワードを投げる問題。openSSL調べて、ヒットしたサンプルをコピーしてごちゃごちゃやってたら出来たんだけど、そもそもopensslの引数のとり方とかなんかもう色々よくわからないから後で調べてまとめる（なので余裕があれば追記予定）
$ echo "BfMYroe26WYalil77FoDi9qh59eK5xNr"|openssl s_client -connect localhost:30001 -ign_eof
とやったらcorrect!と帰ってきてcluFn7wTiGryunymYOu4RcffSxQluehd
Level17→18（途中）
再びパスワード提出系の問題。ポート番号31000-32000のどこかがlistenになっているとのこと。
$ nmap -sT -p 31000-32000 localhost
とやってみると、ポート番号31518と31790の2つが開いていた。
echo "cluFn7wTiGryunymYOu4RcffSxQluehd"|openssl s_client -connect localhost:31518 -ign_eof
と
echo "cluFn7wTiGryunymYOu4RcffSxQluehd"|openssl s_client -connect localhost:31790 -ign_eof
どちらも試したら後者の方でcorrect!って帰ってきた。しかし今回得られたはflagではなくてRSA秘密鍵だった。これ使ってssh -iでログインするんだと思ったけれどホームディレクトリにはファイル作れないっぽいので、/tmp下に適当にファイル作ってコピペした。これでログインを試みたら、”他のユーザも見れるようになってるパーミッション”ではダメだよって起こられたから600に設定して再度試したけれどこれもダメ。今度のエラーは.ssh/known_hostsに書き込めないよってことみたい（そもそもls -aしても無い）。ここで手詰まり中。
2018年の某の応募課題を今更ながら...
一部書き換えてますが、2018年のseccampに応募したときに書いたやつです。落ちましたが。
アップするかどうか迷いましたが、"2018年ももう終わるしなんとなく上げておくかぁ”くらいの気持ちです。
----(以下本文)----
大学のSoralis演習室を使いました。
いきなりですが、”prtconf -D”を実行した時の結果が以下になります。
$prtconf -D
System Configuration: Oracle Corporation i86pc
Memory size: 65404 Megabytes
System Peripherals (Software Nodes):
i86pc
scsi_vhci, instance #0
disk, instance #3
disk, instance #1
disk, instance #2
disk, instance #0
pci, instance #0
pci8086,0 (pciex8086,6f00) (driver not attached)
pci8086,6f02 (pciex8086,6f02) (driver not attached)
pci8086,6f04 (pciex8086,6f04) (driver not attached)
pci8086,6f08 (pciex8086,6f08), instance #2
pci1000,9361 (pciex1000,5d), instance #0
iport, instance #1
pci8086,6f0a (pciex8086,6f0a), instance #3
pci108e,4852 (pciex8086,1528), instance #0
pci108e,4852 (pciex8086,1528), instance #1
pci8086,0 (pciex8086,6f20) (driver not attached)
pci8086,0 (pciex8086,6f21) (driver not attached)
pci8086,0 (pciex8086,6f22) (driver not attached)
pci8086,0 (pciex8086,6f23) (driver not attached)
pci8086,0 (pciex8086,6f24) (driver not attached)
pci8086,0 (pciex8086,6f25) (driver not attached)
pci8086,0 (pciex8086,6f26) (driver not attached)
pci8086,0 (pciex8086,6f27) (driver not attached)
pci8086,6f28 (pciex8086,6f28) (driver not attached)
pci8086,6f29 (pciex8086,6f29) (driver not attached)
pci8086,6f2a (pciex8086,6f2a) (driver not attached)
pci8086,0 (pciex8086,6f2c) (driver not attached)
pci108e,4852 (pciex8086,8d7c) (driver not attached)
pci108e,4852 (pciex8086,8d3a) (driver not attached)
pci108e,4852 (pciex8086,8d3b) (driver not attached)
pci108e,4852 (pciex8086,8d2d), instance #0
hub, instance #0
pci8086,8d10 (pciex8086,8d10) (driver not attached)
pci8086,8d1e (pciex8086,8d1e), instance #5
display (pciex102b,522), instance #0
pci108e,4852 (pciex8086,8d26), instance #1
hub, instance #1
hub, instance #2
device, instance #3
keyboard, instance #8
input, instance #9
mouse, instance #10
mouse, instance #11
communications, instance #0
isa (pciex8086,8d44), instance #0
asy, instance #0
pit_beep, instance #0
pci108e,4852 (pciex8086,8d02), instance #0
cdrom, instance #4
pci108e,4852 (pciex8086,8d22) (driver not attached)
ioapics (driver not attached)
ioapic, instance #0 (driver not attached)
ioapic, instance #1 (driver not attached)
pci, instance #1
pci8086,6f80 (pciex8086,6f80) (driver not attached)
pci8086,6f32 (pciex8086,6f32) (driver not attached)
pci8086,6f83 (pciex8086,6f83) (driver not attached)
pci8086,6f90 (pciex8086,6f90) (driver not attached)
pci8086,6f33 (pciex8086,6f33) (driver not attached)
pci8086,6f93 (pciex8086,6f93) (driver not attached)
pci8086,6f81 (pciex8086,6f81) (driver not attached)
pci8086,6f36 (pciex8086,6f36) (driver not attached)
pci8086,6f37 (pciex8086,6f37) (driver not attached)
pci8086,6f76 (pciex8086,6f76) (driver not attached)
pci8086,6fe0 (pciex8086,6fe0) (driver not attached)
pci8086,6fe1 (pciex8086,6fe1) (driver not attached)
pci8086,6fe2 (pciex8086,6fe2) (driver not attached)
pci8086,6fe3 (pciex8086,6fe3) (driver not attached)
pci8086,6fe4 (pciex8086,6fe4) (driver not attached)
pci8086,6fe5 (pciex8086,6fe5) (driver not attached)
pci8086,6fe6 (pciex8086,6fe6) (driver not attached)
pci8086,6fe7 (pciex8086,6fe7) (driver not attached)
pci8086,6ff8 (pciex8086,6ff8) (driver not attached)
pci8086,6ff9 (pciex8086,6ff9) (driver not attached)
pci8086,6fe0 (pciex8086,6ffc) (driver not attached)
pci8086,6fe0 (pciex8086,6ffd) (driver not attached)
pci8086,6fe0 (pciex8086,6ffe) (driver not attached)
pci8086,6f1d (pciex8086,6f1d) (driver not attached)
pci8086,6f34 (pciex8086,6f34) (driver not attached)
pci8086,6f1e (pciex8086,6f1e) (driver not attached)
pci8086,6f7d (pciex8086,6f7d) (driver not attached)
pci8086,6f1f (pciex8086,6f1f) (driver not attached)
pci8086,6fa0 (pciex8086,6fa0) (driver not attached)
pci8086,6f30 (pciex8086,6f30) (driver not attached)
pci8086,6fa8 (pciex8086,6fa8) (driver not attached)
pci8086,6f71 (pciex8086,6f71) (driver not attached)
pci8086,6faa (pciex8086,6faa) (driver not attached)
pci8086,6fab (pciex8086,6fab) (driver not attached)
pci8086,6fac (pciex8086,6fac) (driver not attached)
pci8086,6fad (pciex8086,6fad) (driver not attached)
pci8086,6fae (pciex8086,6fae) (driver not attached)
pci8086,6faf (pciex8086,6faf) (driver not attached)
pci8086,6fb0 (pciex8086,6fb0) (driver not attached)
pci8086,6fb1 (pciex8086,6fb1) (driver not attached)
pci8086,6fb2 (pciex8086,6fb2) (driver not attached)
pci8086,6fb3 (pciex8086,6fb3) (driver not attached)
pci8086,6fbc (pciex8086,6fbc) (driver not attached)
pci8086,6fbd (pciex8086,6fbd) (driver not attached)
pci8086,6fbe (pciex8086,6fbe) (driver not attached)
pci8086,6fbf (pciex8086,6fbf) (driver not attached)
pci8086,6fb4 (pciex8086,6fb4) (driver not attached)
pci8086,6fb5 (pciex8086,6fb5) (driver not attached)
pci8086,6fb6 (pciex8086,6fb6) (driver not attached)
pci8086,6fb7 (pciex8086,6fb7) (driver not attached)
pci8086,6f68 (pciex8086,6f68) (driver not attached)
pci8086,6f6e (pciex8086,6f6e) (driver not attached)
pci8086,6f6f (pciex8086,6f6f) (driver not attached)
pci8086,6fd0 (pciex8086,6fd0) (driver not attached)
pci8086,6fb8 (pciex8086,6fb8) (driver not attached)
pci8086,6fb9 (pciex8086,6fb9) (driver not attached)
pci8086,6fba (pciex8086,6fba) (driver not attached)
pci8086,6fbb (pciex8086,6fbb) (driver not attached)
pci8086,6f98 (pciex8086,6f98) (driver not attached)
pci8086,6f99 (pciex8086,6f99) (driver not attached)
pci8086,6f9a (pciex8086,6f9a) (driver not attached)
pci8086,6fc0 (pciex8086,6fc0) (driver not attached)
pci8086,6f9c (pciex8086,6f9c) (driver not attached)
pci8086,6f88 (pciex8086,6f88) (driver not attached)
pci8086,6f8a (pciex8086,6f8a) (driver not attached)
pci, instance #2
pci8086,6f02 (pciex8086,6f02), instance #6
pci108e,4852 (pciex8086,1528), instance #2
pci108e,4852 (pciex8086,1528), instance #3
pci8086,6f08 (pciex8086,6f08) (driver not attached)
pci8086,0 (pciex8086,6f20) (driver not attached)
pci8086,0 (pciex8086,6f21) (driver not attached)
pci8086,0 (pciex8086,6f22) (driver not attached)
pci8086,0 (pciex8086,6f23) (driver not attached)
pci8086,0 (pciex8086,6f24) (driver not attached)
pci8086,0 (pciex8086,6f25) (driver not attached)
pci8086,0 (pciex8086,6f26) (driver not attached)
pci8086,0 (pciex8086,6f27) (driver not attached)
pci8086,6f28 (pciex8086,6f28) (driver not attached)
pci8086,6f29 (pciex8086,6f29) (driver not attached)
pci8086,6f2a (pciex8086,6f2a) (driver not attached)
pci8086,0 (pciex8086,6f2c) (driver not attached)
fw, instance #0
sb, instance #1
socket, instance #2
cpu, instance #0
cpu, instance #1
cpu, instance #2
cpu, instance #3
cpu, instance #4
cpu, instance #5
cpu, instance #6
cpu, instance #7
cpu, instance #8
cpu, instance #9
cpu, instance #10
cpu, instance #11
socket, instance #3
cpu, instance #12
cpu, instance #13
cpu, instance #14
cpu, instance #15
cpu, instance #16
cpu, instance #17
cpu, instance #18
cpu, instance #19
cpu, instance #20
cpu, instance #21
cpu, instance #22
cpu, instance #23
used-resources (driver not attached)
fcoe, instance #0
iscsi, instance #0
agpgart, instance #0
options, instance #0
pseudo, instance #0
vga_arbiter, instance #0
xsvc, instance #0
intel-iommu, instance #0
intel-iommu, instance #1
partconfはシステム構成を出力するコマンドで、-Dオプションを指定すると、周辺機器ごとにそれを管理するために使用されているデバイスドライバの名前を表示してくれます。インデントで階層構造を表現してます（最初はこれをどうやって読むのかも分かりませんでした）
つまり以下の部分は、
pci, instance #0
pci8086,0 (pciex8086,6f00) (driver not attached)
pci8086,6f02 (pciex8086,6f02) (driver not attached)
pci8086,6f04 (pciex8086,6f04) (driver not attached)
pci8086,6f08 (pciex8086,6f08), instance #2
pci1000,9361 (pciex1000,5d), instance #0
iport, instance #1
pci8086,6f0a (pciex8086,6f0a), instance #3
pci108e,4852 (pciex8086,1528), instance #0
下図ようになってます
（ちなみにここで、実行結果の方で「driver not attached 」となっている部分がありますが、これはデバイスが繋がっていない(あるいは使用中ではない)ために、デバイスインスタンスに現在接続されているドライバがないことを意味していて、ドライバは、デバイスがアクセスされると自動的にロードされデバイスが使用されなくなると自動的にアンロードされます）
ここで、pci8086とpci1000などが何を意味しているのかが気になりました。「pciex8086は恐らくpci expressのことだろう」という感じで多少の類推はできるのですが、考えてもそれ以上のことが分からなかったので調べました。
The PCI ID Repositoryを見たら、どうやらこれらはデバイス名であるらしいことがわかりました。例えば”pciex8086,6f02”だと（https://pci-ids.ucw.cz/read/PC/8086/6f04）PCI Express Root Port 2と書いてあって、詳細はともかく、「何をするためのものか」くらいは調べればなんとなく分かる状態になりました。
それがわかった上で、以下の部分を見てみます。
pci, instance #2
pci8086,6f02 (pciex8086,6f02), instance #6
pci108e,4852 (pciex8086,1528), instance #2
pci108e,4852 (pciex8086,1528), instance #3
まずいちばん上の”pci instance #2”と書いてあるところがおそらくホスト-PCIブリッジで、ここには今pciex8086,6f02が繋がれています。この記事によると、PCI Expressのシステムを構成する要素の一つにはルートコンプレックスというものが存在し、そこには1つ以上のPCIeポートがあるということなので、恐らくpci8086 6f02がそのルートコンプレックスなのだろうと分かります。そして、その下層に２つ繋がっているpci108e,4852 (pciex8086,1528)を調べてみると、デバイス名がEthernet Server Adapter X540ということで、ネットワークに関する何かなのだということが分かりました。
他にも聞き覚えのないデバイスをいくつか調べてみました。
scsi_vhci
パソコンと周辺機器をつなぐ規格で主にハードディスクなどのドライブを接続するために使われるが、最近では同じ用途にUSBやIEEE1394を使用するのが一般的で、SCSIはあまり使われなくなった
ioapics
I/Oデバイスから受け取った割り込みを、CPUへ通知する
fcoe
イーサネットを通じてファイバチャネルのフレーム転送を行うためのもの。Storage Area Networkという、(名前通りに)ストレージをネットワークを経由して利用する仕組みを構築するために使われる
FCoeEと同じく、SANを利用する仕組みを実現するために使われる。上述したSCSIのデータをTCP/IPで利用できるようにするもの。
--(本文終わり)--
※他にも色々書きましたが、残っているのがこれだけでした。
なんか今になって読むと、もっと色々手動かせばできることあったんじゃない？って思います(まぁこれだけでもかなり時間かかった思い出あるのですが...)
OS学習メモ13 (MINIX本4.3-4.3.2章)
本自体は既に一回読んだんですが、復習を兼ねてこの記事を書くためにわざわざ”The MINIX book Operating system implementation”を図書館から借りてきました。持ち歩くのが重いったらないです(笑)。
洋書で読んでるので、もしかしたら英語の解釈違いによる致命的な間違いがある可能性もあるので…違和感感じたら各自改めて調べてください…。
4.3仮想記憶
昔は、利用可能なメモリよりも大きいプログラムを実行しなければならないときにプログラムをオーバレイという小さい断片に分けて実行させる方法を取っていた。オーバレイのスワップイン/アウトはシステムが行うにしても、オーバレイへの分割はプログラマの仕事で、これがまた結構面倒くさいからこれもコンピュータにやらせようってことになって仮想記憶が登場する。
仮想記憶の基本的な考え方は、プログラム、データ、スタックなどを合わせたサイズが物理メモリ量を超えることにある。つまりOSは、その時点でプログラムが使ってる部分だけメモリに残しておいて残りはディスクに置けばいいのである。
4.3.1 ページング
例えば MOV $t0 1000 というアセンブラ命令があったとすると、CPUはメモリアドレス1000の内容をt0にコピーする。この時プログラムが指定するアドレスは仮想アドレスで、これはMMU（Memory Management Unit）によって物理アドレスに変換される。仮想アドレス空間はページという単位に分割され、物理メモリ内における対応する単位はページフレームと呼ばれる（ページとページフレームは同じサイズであることが多い）
明らかに、ページ数>ページフレーム数であるから全てのページを物理メモリにマップすることは不可能なので(だから仮想メモリがあるわけなんだし)、実際のハードウェアでは、物理メモリ上にページが存在するか否かを示すpresent/absent bit(在/不在ビット)が各エントリにある。もしプログラムがマップされていないページを使おうとすると、CPUはOSに対して割り込みを引き起こす（この割り込みはページフォルトと呼ばれている）。これが発生すると、OSはあまり使用されていないページフレームを選び、その内容をディスクに書き込んで、空いたところに該当ページを読み込んで、変換テーブルを書き換えて、割り込みを起こした命令を再度実行する。
4.3.2 ページテーブル
仮想アドレスは「ページ番号を表す部分」と「オフセットを表す部分」に分割される。例えば16bitのアドレスの場合、上位4bitをページ番号に割り当てて(この時2^4=16個のページを持てる)、下位12bitは指定されたページ内のオフセット(0-4095)にしたりする。ページテーブルの目的は”ページ→ページフレーム”の変換であるが...2つの大きな問題がある。「1.ページテーブルが極端に大きくなること」と「2.変換が高速に行われなくてはいけないこと」である。
１、32ビットの仮想アドレス幅を持っているとすると、ページサイズが4KBとして約100万ページ(2^32/4KB)あることになる。これがもし64ビットなら4.5*10^15に…考えたくない。
２、メモリが参照される度に”仮想→物理”の変換がなされるという点に問題がある。典型的な命令は命令ワードとメモリオペランドを持っているので、一命令あたり1か2回,場合によってはそれ以上のページテーブル参照が必要になる。
大きなエントリを持って高速なページ変換を実現するというのは、コンピュータ設計の大きな制約条件になる。超高性能を要求されるマシンには深刻な問題だし、ローエンドなものに関してもコスト/性能比が非常に大事という意味では見逃すことが出来ない項目。
そこで、現実のコンピュータで使われているハードウェアの解決法の例↓
多階層ページテーブル
巨大なページテーブルを常にメモリ上に持たなければいけないという問題を抱えているので、多くのコンピュータではこの多階層ページテーブルを採用している。
(名前からある程度想像できると思うが)この方式では、アドレス32bitをいくつかのまとまりに分けてページテーブルを階層構造にすることで不要な部分をメモリに配置しないようにしている。具体的には、32を10/10/12の3つのまとまりに分け、最初の10bitはページテーブルのインデックス※として利用（第一層）,次の10bitは4MBのページテーブル(第二層)に、残る12bitをオフセットとして利用する。
※ちなみに第一層の1024個のエントリのうち、エントリ0はプログラムテキストのページテーブルを指しており、エントリ1023はスタックのページテーブルを指している。
これなら、100万ページのアドレス空間であるにも関わらず必要なのは4つの小さなページテーブルだけで済む（第一層のテーブル、それに対応する第二層のテーブル、それに加えて第二層エントリ0,1023)
これはあくまで2階層ページテーブルシステムであり、3階層,4階層…と拡張可能である。階層を追加すればその分柔軟にはなるが複雑になる
ページテーブルエントリの構成
エントリのサイズはコンピュータによって異なるが32ビットが通常サイズになっていて、ページフレーム番号,在/不在ビット,保護ビット,更新ビット,参照ビット,キャッシュ禁止を指示するビットの内容を含んでいる
・（最初の2つは説明を省略）
・protection bits(保護ビット)は、どんなアクセスが許されるかを示していて、単純な形であれば1ビットで”読み書き可能/読み出しのみ”を表している。
・modified (更新ビット)はページの使用履歴を示している（次に出てくる参照ビットも）。ページが読み込まれたらハードウェアが自動的に更新ビットをセットし、OSがこのページフレームを再利用する時に使われる。つまり、もしもページが更新されていたらそのページはディスクに書き戻さなければならないし、そうでなければディスク内のコピーとページが同一なので直ちに破棄できる。このビットはページの状態を表しているのでdirty bitと呼ばれることもある。
・referenced bit(参照ビット)は、そのページに参照した時にセットされ、ページフォルト発生時の追放ページを選ぶ根拠になる。
・最後のビットはページにキャッシュ禁止の指示をしている。これはデバイスレジスタ上にマップされたページに対して重要な意味を持っている。OSがI/Oをポーリングで待っている時（I/Oからのワードを読み続けている時）、CPU上のキャッシュが溢れたからといって古いキャッシュ内容のコピーを書き戻してはいけないので、このビットを使ってキャッシュをオフと指定する（...なので分離したI/O空間を持つメモリマップドI/Oを使っていないマシンではこのビットは不要）
ちょっと疲れたので半端ですが今日はここまで。
次回は4.3.3 TLB（Translation Lookaaside Buffers）の説明から。
余談:
先日研究室が決まりました。AI関係なのでこういったOSの知識って殆ど使わないんですけど、なんか個人的に好きなのでこの分野は趣味として続けようと思ってます。今のモチベーションとして、MINIX(バージョンは最新の3ではなく1)のソースを読んでみたいなって思っています。理論だけじゃなくて、実際にどう実装されているのかまで追ってみたいです。Linuxとかと違って教育用のOSなので1万行くらいですし、学生じゃないとそんなことしてる時間無さそうなので...春休みにでも。
OS学習メモ12 (MINIX本4.1-4.2章)
メモリ管理の章です。
4.3（仮想記憶）は少し長いので区切りの良いところまで。
メモリ管理システムは２つに分類できる。一つはプロセスの実行中にその内容をメモリとディスク間で移動するページング方式で、もう片方の方式ではそれを行わない（後者の方が単純なのでそちらから見ていく）
4.1.1 スワップ,ページングを必要としない単一プログラミング
最も単純なメモリ管理方式は、プログラムとOSがメモリを共有して同時に一つのプログラムしか実行しない方式である。これには３つの方法があって、「RAMの一番下にOSを配置する」、「メモリ先頭のROMにOSをを配置する」、「メモリの先頭のROMにはデバイスドライバを入れて、システムの残り部分をRAMの下の方に配置する」のいずれかである。ユーザがコマンドを叩けば、OSは要求されたプロセスを主メモリに読んで、実行する。プロセスが完了したらOSは次のコマンド入力を待つ。次のコマンドが入力されたら、対応プログラムを前に使用したものに上書きして読み込むという流れになる。
4.1.2 固定パーディションによるマルチプログラミング
実は4.1.1の仕組みは今日ではほとんど使われていない。現在のほとんどのシステムでは複数のプロセスを同時実行できる。これを実現する最も簡単な方法は単純にメモリを分割するという方法で、ジョブが到着するとそのジョブが入る最も小さなパーティションの待ち行列にジョブを入れるということを行う。しかしこの方式では待ち行列の作り方によって、ジョブ中に使われない領域ができたり、大きなパーティションに小さなジョブを入れてメモリを無駄にしてしまうといった問題が発生する。これを解決する手段として、「小さなパーティションを持っておく」とか「実行待ちのジョブに実行件を与えてk回以上スキップされない規則にする」というのがある。
4.1.3再配置と記憶保護
マルチプログラミングの実現において解決すべきなのが再配置と記憶保護の問題。
あるプログラムをリンクする時、リンカはそのプログラムがどのアドレスから開始するかを知る必要がある。（例えば最初の命令が、リンカによって生成された、バイナリファイル内の絶対アドレス100番にあるサブルーチンコールだとすると、もしもそのプログラムがアドレス200K番地にロードされた場合200K+100番地にサブルーチンコールをする必要がある。もちろん、300K番地にロードされた場合は300K+100番地である。）これが再配置の問題である。
この解決方法の一つは、メモリにプログラムをロードした時点で命令を書き換える方法、つまりプログラムが200K番地のところにロードされたなら各アドレス部に200Kを加算するという方法である。だが、ローディング中の再配置は記憶保護の問題を解決できない。悪意のあるプログラムが常に新しい命令列を作って実行するかもしれない。このため、再配置と記憶保護の別の方法として、ベースレジスタと境界レジスタの２つの特殊なハードウェアレジスタを用いることがある。あるプロセスがスケジュールされると、ベースレジスタにはパーティションの先頭アドレス、境界レジスタにはパーティションの長さが入り、メモリアドレス生成の度に自動的にベースレジスタの内容がアクセス前に加算されるようになる。アドレスは現在のパーティション外のメモリにアクセスしないように境界レジスタによって保護されていて、これらは改竄されることもない。
4.2 スワッピング
スワッピングとは、プロセス全体を主記憶にロードして暫く実行させた後で、ディスクに吐き出してプロセスを停止するというのを繰り返す方法で、ここまでの固定パーティションの方式とは違ってパーティションの数や位置やサイズが動的に変化する。この分、柔軟性は高まったといえるけれども、メモリを割り当てたり開放するための管理の複雑さは増している。スワッピングを繰り返すとメモリの中に小さな空き領域が出来るので、プロセスを移動することによってそれらを一箇所にまとめることが出来る（これはメモリコンパクションと呼ばれる）。そして肝心のスワッピングだが、プロセスにどのくらいのメモリ量を割り当てるかは重要な問題である。
動的にメモリを割り当てる歳に、OSははそれを管理する必要がある。使用状況の管理には一般に２つの方法ービットマップによる管理とリストによる管理ーがある。
4.2.1 ビットマップによるメモリ管理
あらかじめ”単位”を決めてメモリを分割し（数ワードとか数KBとか）、その単位ごとに「空き」ならば0,「使用中」ならば1をつけて管理する方法。当然ながらこの”単位”を小さくすればするほどビットマップは大きくなる。この方法はメモリサイズと割り当てる単位によって決まるので、一定サイズのメモリを使って全メモリの管理を可能とする簡単な方法であるが、与えられたビットパターンをビットマップ上から探すのは一般的に処理が遅くなるという問題点がある。
4.2.2 リンクリストによるメモリ管理
パーティションをリスト構造にして連結して管理する方法。それぞれのリンクには「空き/使用中」「各パーティションの先頭アドレス」「各パーティションの長さ」「次のパーティションの情報」が入っている。以下はリストを管理するためのアルゴリズムである。
ファーストフィットは該当プロセスのメモリ容量を最初に満たす空きリストを見つけるまで探すもの。ネクストフィットはファーストフィットと同じように空きを探すが、見つかった位置を記憶しておいて、次にコールされるとそのリストの場所から求める空きリストを探す（ファーストフィットと違って最初からは探さない）。ベストフィットは、全リストを調べて空き容量が最小になるエントリを求める。ワーストフィットは、プロセスに割り当てた後で空きと成る部分で最大になるような選択法。クイックフィットは、比較的よく要求されるサイズごとに別々の空きリストを作って管理する。
4.3は今読んでいます。
