受かったら応募用紙を晒すぞと思っていたので晒します。
選択問題 【1】：まずは、このプログラムが実行されているOSを特定しようと試みた。
問題で与えられた実行結果は
hoge address = 0x7fff539799f0
fuga address = 0x7fca11404c70
となっていて、Windows, Mac, Archlinuxで問題文のプログラムを実行して近いものを探した。
Windows(cygwin)での実行結果
hoge address = 0xffffcbe0
fuga address = 0x600010410
hoge address = 0xffffcbe0
fuga address = 0x600010410
hoge address = 0xffffcbe0
fuga address = 0x600010410
hoge address = 0xffffcbe0
fuga address = 0x600010410
Archlinuxでの実行結果
hoge address = 0x7ffc3117e0f0
fuga address = 0x1f77010
hoge address = 0x7ffe558d5710
fuga address = 0x17fa010
hoge address = 0x7ffe0ae4cd30
fuga address = 0x9fa010
hoge address = 0x7fff953936f0
fuga address = 0x2288010
Macでの実行結果
hoge address = 0x7fff595ffae0
fuga address = 0x7fee81403250
hoge address = 0x7fff5403fae0
fuga address = 0x7f8bbac03250
hoge address = 0x7fff555a1ae0
fuga address = 0x7fa592c03250
hoge address = 0x7fff5adf3ae0
fuga address = 0x7fc238c03250
Windowsではstackもmallocも固定アドレスだったが、ArchlinuxとMacではランダムになっていた。
これは、セキュリティ上固定アドレスだとエクスプロイトコードが書きやすく脆弱なのでわざとランダムにしているんだろうと考えた。
問題の実行結果に最も近いのはMacだったので、Macintoshのメモリ配置について調べた。
また、グローバル変数がメモリ上でどの領域に存在しているのかも気になったので問題のソースコードのメイン関数の前でint glob[10]という配列を作って、それも調べた。
globを加えた実行結果
hoge address = 0x7fff5e991ae0
fuga address = 0x7f84b3c03250
glob address = 0x10126f040
メモリ上で明らかにhogeやfugaよりも上にあることがわかる。
Appleの公式サイト(https://developer.apple.com/library/mac/documentation/Performance/Conceptual/ManagingMemory/Articles/VMPages.html#//apple_ref/doc/uid/20001985-CJBJFIDD)にvmmapというプロセスの仮想メモリのメモリ領域を表示するコマンドの情報があったので、これを使って調べた。
ソースコードの中のreturnの直前にscanfをおいて、vmmapコマンドでメモリマップを表示した。
実行結果は例えば以下のようになる。このような出力が得られるとき、以下のようなメモリマップが表示された。
hoge address = 0x7fff53515ae0
fuga address = 0x7faea1403200
glob address = 0x10c6eb040
メモリマップをすべて記載すると10000字を越えてしまうため、重要なところだけ記載した。
Process: a.out [36361] Path: /home/1588348124/a.out Load Address: 0x10c6ea000 Identifier: a.out Version: ??? Code Type: X86-64 Parent Process: bash [3160] Date/Time: 2016-05-27 17:47:34.708 +0900 Launch Time: 2016-05-27 17:46:25.684 +0900 OS Version: Mac OS X 10.11.4 (15E65) Report Version: 7 Analysis Tool: /Applications/Xcode.app/Contents/Developer/usr/bin/vmmap Analysis Tool Version: Xcode 7.3 (7D175) ---- Virtual Memory Map of process 36361 (a.out) Output report format: 2.4 -- 64-bit process VM page size: 4096 bytes ==== Writable regions for process 36361 REGION TYPE START - END [ VSIZE] PRT/MAX SHRMOD REGION DETAIL __DATA 000000010c6eb000-000000010c6ec000 [ 4K] rw-/rwx SM=COW /home/1588348124/a.out Kernel Alloc Once 000000010c6ed000-000000010c6ee000 [ 4K] rw-/rwx SM=PRV MALLOC metadata 000000010c6ef000-000000010c6f0000 [ 4K] rw-/rwx SM=ZER MALLOC metadata 000000010c6f1000-000000010c706000 [ 84K] rw-/rwx SM=PRV MALLOC metadata 000000010c708000-000000010c71d000 [ 84K] rw-/rwx SM=PRV Activity Tracing 000000010c71f000-000000010c91f000 [ 2048K] rw-/rwx SM=SHM MALLOC_TINY 00007faea1400000-00007faea1500000 [ 1024K] rw-/rwx SM=PRV DefaultMallocZone_0x10c6ee000 MALLOC_SMALL 00007faea1800000-00007faea2000000 [ 8192K] rw-/rwx SM=PRV DefaultMallocZone_0x10c6ee000 Stack 00007fff52d16000-00007fff53516000 [ 8192K] rw-/rwx SM=PRV thread 0 __DATA 00007fff6a445000-00007fff6a448000 [ 12K] rw-/rwx SM=COW /usr/lib/dyld __DATA 00007fff6a448000-00007fff6a481000 [ 228K] rw-/rwx SM=PRV /usr/lib/dyld __DATA 00007fff72d0b000-00007fff72d0c000 [ 4K] rw-/rwx SM=COW /usr/lib/system/libsystem_secinit.dylib __DATA 00007fff72d1e000-00007fff72d20000 [ 8K] rw-/rwx SM=COW /usr/lib/libauto.dylib __DATA 00007fff72df2000-00007fff72df3000 [ 4K] rw-/rwx SM=COW /usr/lib/system/libsystem_malloc.dylib __DATA 00007fff72f03000-00007fff72f05000 [ 8K] rw-/rwx SM=COW /usr/lib/system/libsystem_trace.dylib __DATA 00007fff72fdd000-00007fff72fe0000 [ 12K] rw-/rwx SM=COW /usr/lib/system/libsystem_kernel.dylib __DATA 00007fff73036000-00007fff73037000 [ 4K] rw-/rwx SM=COW /usr/lib/system/libcopyfile.dylib __DATA 00007fff7307c000-00007fff7307e000 [ 8K] rw-/rwx SM=COW /usr/lib/libc++abi.dylib __DATA 00007fff732c0000-00007fff732c8000 [ 32K] rw-/rw- SM=COW /usr/lib/system/libcorecrypto.dylib __DATA 00007fff732f8000-00007fff732f9000 [ 4K] rw-/rw- SM=COW /usr/lib/system/libkeymgr.dylib __DATA 00007fff732f9000-00007fff732fa000 [ 4K] rw-/rw- SM=COW /usr/lib/libDiagnosticMessagesClient.dylib __DATA 00007fff7350f000-00007fff73510000 [ 4K] rw-/rwx SM=COW /usr/lib/system/libsystem_coreservices.dylib __DATA 00007fff73589000-00007fff7358a000 [ 4K] rw-/rwx SM=COW /usr/lib/system/libsystem_coretls.dylib ==== Legend SM=sharing mode: COW=copy_on_write PRV=private NUL=empty ALI=aliased SHM=shared ZER=zero_filled S/A=shared_alias ==== Summary for process 36361 ReadOnly portion of Libraries: Total=98.9M resident=0K(0%) swapped_out_or_unallocated=98.9M(100%) Writable regions: Total=19.4M written=0K(0%) resident=0K(0%) swapped_out=0K(0%) unallocated=19.4M(100%) VIRTUAL REGION REGION TYPE SIZE COUNT (non-coalesced) =========== ======= ======= Activity Tracing 2048K 2 Kernel Alloc Once 4K 2 MALLOC guard page 16K 4 MALLOC metadata 180K 6 MALLOC_SMALL 8192K 2 see MALLOC ZONE table below MALLOC_TINY 1024K 2 see MALLOC ZONE table below STACK GUARD 56.0M 2 Stack 8192K 2 __DATA 1444K 42 __LINKEDIT 91.5M 4 __TEXT 7652K 43 shared memory 8K 3 =========== ======= ======= TOTAL 175.5M 102 VIRTUAL ALLOCATION BYTES REGION MALLOC ZONE SIZE COUNT ALLOCATED % FULL COUNT =========== ======= ========= ========= ====== ====== DefaultMallocZone_0x10c6ee000 9216K 179 26K 0% 2
以上のようになった。
ここで、hogeのアドレスの位置を確かめると、Writable regionsのStackの下のほうにあることが分かる。fugaは、MALLOC_TINYの最初のほうに確保されていて、globは__DATAの最初のほうに確保されていることが分かる。
fugaは、サイズが小さいときはMALLOC_TINYに置かれ、10000くらいを境にMALLOC_LARGEに入ることがわかった。
__DATAの大きさが4KBになっていたのでglobをちょうど4KBの配列にしたら溢れてもう一つの__DATA領域が確保されたので、__DATAの先頭にはなにかデータでないものが入っているのかと思いデバッガで見てみることにした。
lldbというデバッガを使った。
__DATAは最初40byteくらいだけ7fffから始まるメモリ上のポインタのようなものがあったが、それ以降残りは0になっていた。これを見て、今まで競技プログラミングなどで感じていた、グローバル変数は特に初期化しなくても0になるのに、ローカル変数は初期化しないと不定値が入っているという謎がとけた。ローカル変数は普通にスタックに積まれているので、スタックが縮んだりすると前のデータが残ってたりするのだなと思った。
選択問題 【3】：
参考にした本
プログラムはなぜ動くのか
OS自作入門
参考にしたサイト
http://park12.wakwak.com/~eslab/pcmemo/boot/boot4.html#bootldr
http://softwaretechnique.jp/OS_Development/kernel_loader1.html
補助記憶装置上に保存されているプログラムが実行される際には主記憶装置であるメモリにコピーされる。
HDDにあるプログラムをCPUが直接実行できない理由は、CPUはプログラムカウンタでメモリのアドレスを指定して、そこからプログラムを読み出すようになっているから。もしディスクのプログラムをCPUが直接実行できたとしても、ディスクの読出し速度は低速なので、ディスクのプログラムをメモリにロードしてから実行することがとても重要である。
もちろんメモリの容量が十分にあればプログラムをすべてメモリにロードしてから実行するほうが実行速度は速いが、メモリの空きが少なく、プログラムをすべて読み込む容量がない場合には補助記憶装置を仮想的にメモリとして扱う、仮想記憶という手法が取られる。
CPUはメモリ上のプログラムだけしか実行できないため、実際のメモリの内容とハードディスクの内容をスワップしながら(スワッピング)プログラムが実行される。主な仮想記憶の手法であるページング方式は、例えばWindowsなら1ページの大きさは4KBと決めて、プログラムの構造にかかわらずメモリとハードディスク間の置き換えを行う。
しかし仮想記憶は低速なHDDとのスワッピングを行うため非常に遅い。
メモリは電気的に記憶されるためパソコンの電源が切れると全ての記録が消えてしまうので、CPUがメモリ上のプログラムしか実行できないことを考えるとどうやってパソコンが起動しているのかが気になる。また、メモリの領域の割り当てやスワッピングなどを行うWindowsやLinuxなどのOSも、パソコンが起動した直後は実行されていないはずである。
パソコンの電源を入れてからOSが起動するまでのプロセスを知ることで、以上の疑問に答えることができると思ったので調べてみた。
前提知識として、BIOS、ブートストラップ・ローダについて。
BIOSとは、ROMに記憶されていて、あらかじめコンピュータに内蔵されているプログラムである。最近はUEFIが主流のようだが、調べた範囲だとBIOSの記述が多かったのでBIOSの話をする。
BIOSは、キーボード、HDDなどの基本制御プログラムのほか、ブートストラップ・ローダを起動する機能を持っている。
ブートストラップ・ローダとは、起動ドライブ（一般的にはハードディスクだが、CD-ROMやフロッピーディスクも可）の先頭領域に記憶された小さなプログラムのこと。ハードディスクなどに記録されたOSをメモリにロードして実行する役割を持っている。
流れとしては、コンピュータの電源を入れると、BIOSがハードウェアの正常動作を確認し、問題がなければブートストラップ・ローダを起動し、ブートストラップ・ローダがOSをメモリにロードして実行し、OSがハードディスクに保存されているプログラムをメモリにコピーして実行する。
細かな流れ
パソコンの電源が入ると、0xFFFF0のメモリアドレスに強制的にジャンプしてリアルモードで動作が始まる。
アドレス0xFFFF0の位置にはシステム BIOS先頭アドレスへのジャンプ命令があり、CPUはシステムBIOSの先頭から順次読み込んで処理(命令を実行)する。
割り込みベクタの用意をして、デバイスの検出・初期化・設定を行うコードをまとめた部分であるPOST(Power On Self Test)を実行する。
次に、ブートローダを読み込む。BIOSの設定画面でブートの優先順位が決められるので、BIOSは補助記憶装置を順番にめぐって、ブートローダの有無を確認するためにMASTER BOOT RECORD(MBR)を最初のセクタからメモリに読み込む。MBRには（プライマリ）ブートストラップローダが含まれている。フロッピーディスクなら512バイトでありCD-ROMなら2048バイト。
読み込んだ512バイトの最後の511バイト目と512バイト目がそれぞれ0x55と0xAAであれば正常なブートメディアだから、メモリの0x7C00番地に最初のセクタがコピーされる。
0x7C00にブートローダがコピーされるとその位置から処理を開始する。
処理がBIOSからブートローダに移る。
ブートローダーはパーティションテーブルの情報からアクティブな基本パーティションの開始位置に記録されたブートセクターを読み込む。
ブートセクタのIPL（イニシャル・プログラム・ローダー）に移る。
IPL の役目は NTFS (Windows のファイルシステム) で管理されている Ntldr (NT Loader) を検索し、ハードディスク上の記録位置 (セクター) を読み取ってロードすることにある。Ntldrは動作モードをプロテクトモードに切り替え、NTOSKRNLをロードし制御を渡す。NTOSKRNLはWindowsのカーネルで、メモリシステムやデバイスとの通信を司る。このとき、パソコンの画面にロゴが表示される。
その後、スクリーンがグラフィックモードに切り替えられログイン画面が表示され、Windowsのブートが完成する。
選択問題 【4】：
作成したC++ファイル。
第二引数にRHプロトコルのデータのファイル名"pyonpyhon.rh"をとる。
#include<fstream>
#include<arpa/inet.h>
#include<cstdio>
#include<cctype>
#include<algorithm>
#include<iterator>
#include<string.h>
#include<vector>
#include<iostream>
#include<cstdint>
using namespace std;
typedef struct PAC{
char Magic[2];
char Source[20];
char Destination[20];
uint32_t DataLength;
char* Data;
} PAC;
int solve(PAC *pac){
if(pac->Magic[0]!='R' || pac->Magic[1]!='H') // Condition 1
return 1;
if(!strcmp( pac->Source, "cocoa-san" ) && !strcmp( pac->Destination, "Chino")) //Condition 4
return 4;
transform((char *) pac->Source, pac->Source + 20,(char *)pac->Source,::tolower);
transform((char *)pac->Destination, pac->Destination + 20,(char *)pac->Destination,::tolower);
if(strcmp( pac->Source, "rise-san") && strcmp( pac->Source, "cocoa-san")) //Condition 2
return 2;
if(strcmp( pac->Destination, "chino-chan") && strcmp( pac->Destination, "chino")) //Condition 3
return 3;
if(strstr(pac->Data,"DandySoda") || strstr(pac->Data,"FrozenEvergreen" )) //Condition 6
return 6;
if(!strstr(pac->Data,"BlueMountain") && !strstr(pac->Data,"Columbia") && !strstr(pac->Data, "OriginalBlend")) //Co>
return 5;
return 0;
}
int main(int argc, char **argv){
if(argc<2){
printf("第二引数に読み込みたいバイナリファイルを指定してね\n");
return 0;
}
char* outfile=argv[1];
ifstream fin(outfile, ios::in | ios::binary);
if(!fin){
printf("cannot open outfile");
return 0;
}
while(!fin.eof()){
PAC pac;
fin.read( pac.Magic, 2 );
fin.read( pac.Source,20);
fin.read( pac.Destination, 20);
fin.read( (char *) &pac.DataLength, 4);
pac.DataLength=htonl(pac.DataLength);
pac.Data=(char *) malloc(pac.DataLength);
fin.read( pac.Data, pac.DataLength);
int res=solve(&pac);
if(res==0)
printf("PASS\n");
else
printf("REJECTED%d\n",res);
free(pac.Data);
}
fin.close();
return 0;
}
ファイルを読み込む処理について。
最初は、ファイルの中身をすべて文字列としてscanfしようと考えたが、null文字の処理がつらくなってしまうので、read関数でパケットごとにデータを読み込むようにした。
躓いたのが、DataLengthはuint32_tなので、ほかの配列などと違ってcharポインタにキャストした上にポインタを渡す必要があった。また、リトルエンディアンではなくビッグエンディアンだったので、その変換も考えた。Dataはcharポインタなので、最初mallocせずに実行したらSegmentation Faultしたが、それはメモリの領域を確保せずにDataLength長の文字列を入れたからだとわかり、mallocした。
solve関数について。
transformの中のtolowerに::を付けたのはglobal namespaceのtolowerだということを示すため。
condition 4は、大文字小文字の区別ありでSourceが"cocoa-san"かつDestinationが"Chino"だったらrejectするようにした。
実行結果は以下。
PASS
PASS
PASS
PASS
PASS
PASS
PASS
PASS
PASS
REJECTED
PASS
PASS
PASS
REJECTED
REJECTED
PASS
PASS
PASS
REJECTED
REJECTED
REJECTED
PASS
PASS
PASS
REJECTED
REJECTED
REJECTED
REJECTED
PASS
PASS
PASS
REJECTED
REJECTED
REJECTED
REJECTED
REJECTED
PASS
PASS
PASS
REJECTED
REJECTED
REJECTED
REJECTED
REJECTED
REJECTED
REJECTED
CPUサイクルとは何を測るのかわからなかったため、pyonpyon.rhを与えたときの実行時間とメモリ使用量を計測した。
timeはtimeコマンドで調べた。0.002sec total
psコマンドでメモリ使用量を調べた。VSZ 13069KiB RSS 2764KiB
選択問題 【8】：まずは参考にしたサイト
三村さんのマシン語をメモリ上に配置して実行可能にして実行する手法が非常に参考になった。
http://www.slideshare.net/SatoshiMimura/ss-10685328
http://go.mimumimu.net/rtYMKr
MSDN
https://msdn.microsoft.com/ja-jp/library/cc430204.aspx
初めになんとなく見たときに、retが連続していて妙に感じた。pushでアドレスが積まれてretで何回もそこに飛んでいることに気がついた。
上記の三村さんのコードを改造してwindowsで実行した。windbgというwindowsの64bitで使えるデバッガを使った。syscallはwindowsでは実行できなかったが、実行できたかのように例えばread呼び出し後にメモリを書き換えたりした。
書いたC++のソースコードは以下。
#include <windows.h>
#include <stdio.h>
#include<iostream>
using namespace std;
uint64_t code[32] = {0xDEADBEEFDDDDD,0};
int main(){
int d;
int a = 0,b = 0,c = 0;
scanf("%d",&d);
cout << VirtualAlloc((void*)0x40007f,300,MEM_RESERVE | MEM_COMMIT,PAGE_EXECUTE_READWRITE) << endl;
cout << GetLastError() << endl;
memcpy((void*)0x40007f,code,sizeof(code));
((int(*)(void))((void*)0x40007f))();
return 0;
}がんばったこと。
三村さんのサンプルコードはMac用だったので、VirtualAllocを使うように改造するのに苦労した。RESERVE(予約)してからCOMMIT(割り当て)した。
三村さんのおすすめはVirtualProtectだったが、それだと400080に領域を確保できなさそうだったのでVirtualAllocを使った。
scanfはwindbgでアタッチする時間稼ぎのために書いてある。
このようなC++のプログラムを書いて、最初にでてきた大量のエラーを読んでがんばってコンパイルを通した。できたexeファイルをバイナリエディタで開いて、DEADBEEFDDDDDDDを探し、codeの部分を下のデータで書き換えた。このexeファイルをwindbgで実行してscanfのところでattachした。で、gコマンドを打つとCC(int 3)のところで止まるので、そこからF10(step 実行）した。
ちなみに、codeの部分を書き換えるのは手打ちではなくキーボードシミュレータというソフトを使った。
バイナリを書き換えたコードは以下。
CC68190140006A016806014000681901400068290140006A3C6802014000681001400048B836151B25671A39635068020140006A0068060140006814014000680C0140006802014000682601400068140140006A07680A0140006AE0680801400068190140006A0868040140006A00681C0140006A0068060140006A006802014000C358C35AC35FC35DC359C34801ECC3483906C380340E55C30F05C34889E6415AC34889F1C348FFC97501C3415AC3
最初のCC以外は問題文と同じ。
実際に実行してみた結果。
まず、pushで普通にスタックに積んだあと、syscallでread関数のファイルディスクリプタが0の標準入力から8バイト受け取って、(環境依存だが私の環境では)ffffcb00を8バイト書き換えていることが分った。そこで、syscallは動かなくて800000002みたいなエラーがeaxに入っていたため、メモリを直接適当に書き換えた。
実行を進めたら、一バイトずつ、ffffcb00で入力を受け取ったバイナリと16新数の55をxorしていた。これを8回繰り返していた。
その後、[rsi]とraxをcmpしているところで、[rsi]は書き換えられたffffcb00からの8バイトで、raxには63391A67251B1536が入っていた。ここで、もし[rsi]とraxが異なると、0フラグが0になり、そのあとのjneで飛ばされた後にrdiが1にされた後syscallでexitしていた。
もし[rsi]とraxが一致した場合(無理やりzfを1にして試した)、jneで飛ばず、rdiが0でexitしていた。
ここで、[rsi]とraxが一致するというのは、syscallのreadのところで、63391A67251B1536と5555555555555555のxorに当たる文字列を入力した時で、その文字列を調べた。
結果、c@NP2Ol6という文字列を入力するとrdiが0になってきっとプロセスの終了コードが0になることがわかった。
感じた事。
c@NPのNはスペルミスなのかどうか・・。私が何か見落としてるのかどうか、心配になった。
ステップ実行してる間は見ただけでは全く想像もしてなかった挙動が見れてとても楽しかった。と同時に、いちいち実行しなくても読むだけで理解できるようになりたいと思った。
