Raspberry Pi 4をJTAGデバッグしてみる(FTDI C232HM-DDHSL-0使用)

f:id:hikalium:20210718212859j:plain
JTAGアダプタとシリアルケーブルがつながったRaspberry Pi 4

概要

Raspberry Piでベアメタルプログラミングをするときに、CPUが今実際にどこの命令を実行しているか、メモリ上にどのような値が存在するか…などの情報を確認できると、デバッグが非常に楽になります。それを可能にしてくれるのが、JTAGというインターフェイスです。

今回は、FTDI社製のケーブルを使用して、Raspberry Pi 4のJTAGにアクセスしてみました。前半部分はケーブル固有の話もあるので、他のJTAGケーブルをお持ちの方は、それぞれのマニュアルを参照して適宜読み替えていただく必要があります。一方後半部分は、openocdを使ってJTAG経由でRaspberry Pi 4の情報を取得する一般的な方法について説明しますので、みなさんの環境でも役立つかもしれません。参考にしていただければ幸いです。

主な登場人物

  • Raspberry Pi 4 Model B
    • BCM2711というSoCが載っています。
  • FTDI C232HM-DDHSL-0
    • このケーブルはMPSSE(Multi-Protocol Synchronous Serial Engine) といって、モードを切り替えればJTAG以外にもSPIやI2Cといった通信もできるようです。
    • C232HM-DDHSL-0とC232HM-EDHSL-0の違いは、通信に使う電圧レベルです(3.3Vと5.0V)。Raspberry PiのGPIOは3.3Vなので、間違えないようにしましょう。
  • FTDI TTL-232RG-VREG3V3-WE
    • このケーブルはJTAG通信には関係ないですが、Raspberry PiのUART(シリアルポート)を読むために使っています。ベアメタルプログラミングするなら、基本的にシリアルは生命線になるので、シリアルを読めるケーブルは何らかのものを持っておくとよいと思います。
    • 例によって、これも電圧レベルによって似た品番のものがあるので、他の変換ケーブルやボードを使う際も、3.3Vのものを買うようにしましょう。
    • ちなみにこのケーブルは末端が電線剥き出しでコネクタがついてないので、私はそれをブレッドボードに刺してそこからRasPiに延ばしています。コネクタがついているタイプのものも他の製品だとあるようなので、そっちを買った方が便利かもしれません。

決戦結線の時

というわけで早速ケーブルとRasPiをつないでゆきます。RasPiの電源を落としてから作業しましょう。

落とし穴としては、RasPiのGPIOピンの番号と、物理ピン番号(GPIOヘッダ上の位置)は異なる、というところです。

詳しくはRaspberry Pi 公式のドキュメントに解説があるので、それをチェックしてください。

(以下はあくまでも参考として、鵜呑みにせずに自分で本当に合っているかチェックしながら接続してください!)

JTAG ⇔ C232HM-DDHSL-0

ケーブル自体のデータシートも参考にしてください。

ケーブルの色 GPIOピン番号 物理ピン番号 GPIOヘッダを右上においたときの場所
Brown (TMS) 27 (ARM_TMS) 13 上から7番目の左
Grey (TRST) 22 (ARM_TRST) 15 上から8番目の左
Blue (RTCK) 23 (ARM_RTCK) 16 上から8番目の右
Green (TDO) 24 (ARM_TDO) 18 上から9番目の右
Orange (TCK) 25 (ARM_TCK) 22 上から11番目の右
Yellow (TDI) 26 (ARM_TDI) 37 上から19番目の左=下から2番目の左
Black (GND) GND 39, etc... 一番左下など

RTCKを使わない記事もインターネット上にはありましたが、これをつなぐと通信が格段に安定したのでこのようにしています。

UART ⇔ TTL-232RG-VREG3V3-WE

ケーブル自体のデータシートも参考にしてください。

ケーブルの色 GPIOピン番号 物理ピン番号 GPIOヘッダを右上においたときの場所
Yellow(RXD) 14 8 上から4番目の右
Black(GND) GND 9, etc... 上から5番目の左など
Orange(TXD) 15 10 上から5番目の右

接続イメージ

全部つないでみたときの参考写真を貼っておきました。(写真の向きは、GPIOヘッダを左上にみたときの例なので、上の説明と対応させる場合は、90度首を傾けてみてください。)

シリアル変換ケーブルから伸びている線は、写真上側のブレッドボードでジャンパワイヤに変換されてきているので、上の説明に書かれている色と、写真中の線の色は一致しません。

画面左側、JTAGアダプタから伸びている線の色は、上に書いてある説明と一致します。

f:id:hikalium:20210718213206j:plain
JTAGアダプタとシリアル出力の接続例

ソフトウエアの設定

今回の環境は macOS 11.4ですが、Linuxなどの他の環境でも、似たような設定をすれば動作するはずです。

openocdをインストールする

最新のopenocdをHomebrew経由でインストールします。

brew install openocd --HEAD

私の環境では、以下のようなエラーメッセージが出ました。

$ brew install openocd --HEAD
...
==> Installing open-ocd --HEAD
==> ./bootstrap nosubmodule
==> ./configure --prefix=/usr/local/Cellar/open-ocd/HEAD-cff0e41 --enable-buspir
==> make install
Error: An unexpected error occurred during the `brew link` step
The formula built, but is not symlinked into /usr/local
Cannot link open-ocd
Another version is already linked: /usr/local/Cellar/open-ocd/0.10.0
Error: Cannot link open-ocd
Another version is already linked: /usr/local/Cellar/open-ocd/0.10.0

このエラーは、すでに他のバージョンのopenocdがインストールされている場合に表示されます。この場合、インストールした最新のopenocdにはPATHが通っていない状態になっていますので、パスを直接指定して実行してあげる必要があります。(もちろん、強制的にPATHを通す(link)することも可能ですが、各自の判断にお任せします。)

私の環境では、/usr/local/Cellar/open-ocd/HEAD-cff0e41/bin/openocdにインストールされていましたので、これを直接実行できることを確認します。

$ /usr/local/Cellar/open-ocd/HEAD-cff0e41/bin/openocd --version
Open On-Chip Debugger 0.11.0+dev-00236-gcff0e417d-dirty (2021-06-28-20:42)
Licensed under GNU GPL v2
For bug reports, read
    http://openocd.org/doc/doxygen/bugs.html

バージョン情報が正しく表示されればOKです。

Raspberry Pi 側でJTAGインターフェイスを有効化する

デフォルトでは、JTAGインターフェイスは無効になっており、該当するピンは通常のGPIOポートとして機能するように設定されています。

JTAGを有効化するには、Raspberry PiのSDカード内にある config.txtというファイルの[all]セクションの配下に、以下のような記述を追加します。

enable_jtag_gpio=1

これにより、起動時にRaspberry Piのファームウエアがこの設定ファイルを読み込んだ際に、JTAGを有効化してくれます。

詳しくは、公式のドキュメントを参照してください。

ついでにシリアルポート出力とかも有効化しておく

enable_uart=1

参考: 私のconfig.txtの末尾はこうなっている

他にもいろいろ設定を入れてこんな感じになっています。参考までに。(この記事で解説したことを試すには、上で説明した2つを設定するだけで大丈夫なはずです。)

...
[all]
#dtoverlay=vc4-fkms-v3d
arm_64bit=1
init_uart_clock=48000000
init_uart_baud=115200
enable_uart=1
enable_jtag_gpio=1

openocdの設定

それでは早速openocdを使っていきたいのですが、使うためにはいくつか設定ファイルを作成する必要があります。

インターフェイスの設定

まず、以下のような内容のファイルを作成しc232hm-edhsl-0.cfgという名前で保存します。

adapter driver ftdi
ftdi_vid_pid 0x0403 0x6014
ftdi_device_desc C232HM-DDHSL-0

# ftdi_layout_init <values> <directions>
# initial value:
# 0078 = 0000 0000 0001 1000
# TRST, TMS=1, all others zero
# initial direction:
# 0111 = GPIOL3=RTCK=input, GPIOL2=dontcare=output, GPOL1=SRST=output, GPIOL0=TRST=output
# 1011 = [1=TMS=output, 0=TDO=input, 1=TDI=output, 1=TCK=output]
ftdi_layout_init 0x0018 0x007b

# GPIOL0 is TRST
ftdi_layout_signal nTRST -data 0x0010

(参考にしたブログ記事 のものに比べると、最新のopenocdに合わせて少し修正してあります。)

このファイルには、使用するJTAGアダプタ(今回の場合はFTDI C232HM-DDHSL-0)に固有の設定が記載されています。そのため、別のJTAGアダプタを使用する際は、それに合ったファイルを作成する必要があります。場合によっては標準で提供されていることもあるので、他のアダプタをお使いの方は各自で調べてみてください。

ターゲットの設定

次に、以下のような内容のファイルを作成しraspi4.cfgという名前で保存します。

set _CHIPNAME bcm2711
set _DAP_TAPID 0x4ba00477

adapter speed 1000

transport select jtag
reset_config trst_and_srst

telnet_port 4444

# create tap
jtag newtap auto0 tap -irlen 4 -expected-id $_DAP_TAPID

# create dap
dap create auto0.dap -chain-position auto0.tap

set CTIBASE {0x80420000 0x80520000 0x80620000 0x80720000}
set DBGBASE {0x80410000 0x80510000 0x80610000 0x80710000}

set _cores 4

set _TARGETNAME $_CHIPNAME.a72
set _CTINAME $_CHIPNAME.cti
set _smp_command ""

for {set _core 0} {$_core < $_cores} { incr _core} {
    cti create $_CTINAME.$_core -dap auto0.dap -ap-num 0 -baseaddr [lindex $CTIBASE $_core]

    set _command "target create ${_TARGETNAME}.$_core aarch64 \
                    -dap auto0.dap  -dbgbase [lindex $DBGBASE $_core] \
                    -coreid $_core -cti $_CTINAME.$_core"
    if {$_core != 0} {
        set _smp_command "$_smp_command $_TARGETNAME.$_core"
    } else {
        set _smp_command "target smp $_TARGETNAME.$_core"
    }

    eval $_command
}

eval $_smp_command
targets $_TARGETNAME.0

(こちらも、参考にした記事をベースに、最新のopenocdに合わせて少し修正を加えたものになります。)

このファイルには、デバッグ対象のデバイス(今回の場合はRaspberry Pi 4 / BCM2711)に固有の設定が記載されています。そのため、もし異なるボードをJTAGデバッグしたい場合には、それぞれに合ったファイルを作成して使用する必要があります。

動かしてみる

では、編集済みのconfig.txtが入ったRaspberry Pi OS入りのSDカードをRaspberry Pi 4に挿入し、JTAGケーブルやシリアル変換ケーブルをPCにさして、最後にRaspberry Pi 4に電源をさして起動してみましょう。その後、以下のコマンドを実行してみてください。

/usr/local/Cellar/open-ocd/HEAD-cff0e41/bin/openocd -f c232hm-edhsl-0.cfg -f raspi4.cfg

(最初のopenocdへのパスは、適宜環境に合わせて読みかえてください。)

すべてが正しく動作していれば、以下のような出力が得られ、サーバーが待受状態になります。

$ /usr/local/Cellar/open-ocd/HEAD-cff0e41/bin/openocd -f c232hm-edhsl-0.cfg -f raspi4.cfg
Open On-Chip Debugger 0.11.0+dev-00236-gcff0e417d-dirty (2021-06-28-20:42)
Licensed under GNU GPL v2
For bug reports, read
    http://openocd.org/doc/doxygen/bugs.html
Info : Listening on port 6666 for tcl connections
Info : Listening on port 4444 for telnet connections
Info : clock speed 1000 kHz
Info : JTAG tap: auto0.tap tap/device found: 0x4ba00477 (mfg: 0x23b (ARM Ltd), part: 0xba00, ver: 0x4)
Info : bcm2711.a72.0: hardware has 6 breakpoints, 4 watchpoints
Info : bcm2711.a72.1: hardware has 6 breakpoints, 4 watchpoints
Info : bcm2711.a72.2: hardware has 6 breakpoints, 4 watchpoints
Info : bcm2711.a72.3: hardware has 6 breakpoints, 4 watchpoints
Info : starting gdb server for bcm2711.a72.0 on 3333
Info : Listening on port 3333 for gdb connections

openocdとのやりとり

参考:

上の出力に書かれている通り、telnetなどで4444番ポートにアクセスすると、openocdとおはなしできます。

$ telnet localhost 4444
Trying ::1...
telnet: connect to address ::1: Connection refused
Trying 127.0.0.1...
Connected to localhost.
Escape character is '^]'.
Open On-Chip Debugger
> 

ここにコマンドを打つと、いろいろ見れます。

targets: 各ターゲット(今回の場合CPUコア)を一覧表示できる

> targets
    TargetName         Type       Endian TapName            State       
--  ------------------ ---------- ------ ------------------ ------------
 0* bcm2711.a72.0      aarch64    little auto0.tap          running
 1  bcm2711.a72.1      aarch64    little auto0.tap          running
 2  bcm2711.a72.2      aarch64    little auto0.tap          running
 3  bcm2711.a72.3      aarch64    little auto0.tap          running

targets bcm2711.a72.1のように、TargetNameを指定すれば、現在選択しているtargetを変更できる。

halt: 実行を停止させる。

> halt
bcm2711.a72.1 cluster 0 core 1 multi core
bcm2711.a72.2 cluster 0 core 2 multi core
bcm2711.a72.2 halted in AArch64 state due to debug-request, current mode: EL2H
cpsr: 0x000003c9 pc: 0x80
MMU: disabled, D-Cache: disabled, I-Cache: disabled
bcm2711.a72.3 cluster 0 core 3 multi core
bcm2711.a72.3 halted in AArch64 state due to debug-request, current mode: EL2H
cpsr: 0x000003c9 pc: 0x80
MMU: disabled, D-Cache: disabled, I-Cache: disabled
bcm2711.a72.0 cluster 0 core 0 multi core
bcm2711.a72.0 halted in AArch64 state due to debug-request, current mode: EL2H
cpsr: 0x600003c9 pc: 0x813d8
MMU: disabled, D-Cache: disabled, I-Cache: disabled
bcm2711.a72.1 halted in AArch64 state due to debug-request, current mode: EL2H
cpsr: 0x000003c9 pc: 0x80
MMU: disabled, D-Cache: disabled, I-Cache: disabled
> targets
    TargetName         Type       Endian TapName            State       
--  ------------------ ---------- ------ ------------------ ------------
 0  bcm2711.a72.0      aarch64    little auto0.tap          halted
 1* bcm2711.a72.1      aarch64    little auto0.tap          halted
 2  bcm2711.a72.2      aarch64    little auto0.tap          halted
 3  bcm2711.a72.3      aarch64    little auto0.tap          halted

reg: レジスタを表示する

> reg                  
===== Aarch64 registers
(0) x0 (/64): 0x000000000000006c (dirty)
(1) x1 (/64): 0x00000000ffffffff
(2) x2 (/64)
...

dirtyと書かれているデータは、openocdがキャッシュしているものなので、もし生の値を反映させたかったら、以下のようにすると強制的に読み書きできる。

reg x0 force

キャッシュ情報とかも見れます

> aarch64 cache_info
L1 I-Cache: linelen 64, associativity 3, nsets 256, cachesize 48 KBytes
L1 D-Cache: linelen 64, associativity 2, nsets 256, cachesize 32 KBytes
L2 D-Cache: linelen 64, associativity 16, nsets 1024, cachesize 1024 KBytes

メモリの読み書きもできちゃいます!たとえば0x80000(raspberry pi 4におけるカーネルのロードアドレス)をみると

>  mdw 0x80000
0x00080000: d53800a1

と書いてありますが、今回起動したイメージの先頭を確認してみると

$ hexdump -C kernel8.img | head -n 1
00000000  a1 00 38 d5 21 04 40 92  42 01 00 58 3f 00 02 eb  |..8.!.@.B..X?...|

たしかに一致していますね!

gdbとあわせて使う

参考: GDB and OpenOCD (OpenOCD User’s Guide)

openocdの起動時のメッセージを注意深く読むと、gdbのサーバーも待ち受けていることがわかります。

Info : starting gdb server for bcm2711.a72.0 on 3333
Info : Listening on port 3333 for gdb connections

ということで、さっそくつないでみましょう。今回使ったgdbのバージョンは以下の通り。

$ gdb --version | head -n 1
GNU gdb (GDB) 9.2

まず、gdbを引数なしで起動します。

gdb

そのあと、gdbのプロンプトに、アーキテクチャとターゲット情報を打ち込んで、リモートデバッグをはじめます。

私が試した例では、config.txtにarm_64bit=1と書いた状態でaarch64のバイナリを実行している状態なので、以下のようにaarch64をターゲットとして指定します。

(gdb) set architecture aarch64
The target architecture is assumed to be aarch64
(gdb) target extended-remote localhost:3333
Remote debugging using localhost:3333
warning: No executable has been specified and target does not support
determining executable automatically.  Try using the "file" command.
0x00000000000813d8 in ?? ()

一方、Raspberry Pi OSは記事執筆現在は32bit(armv7l)で動作しているので、もしそのようなターゲットをデバッグしたい場合は、aarch64の代わりにarmv8-aにするとよいでしょう。

set architecture armv8-a
target extended-remote localhost:3333

もし間違ったarchを指定していたら、以下のようなエラーメッセージが出るので、そのときは別のarchを指定してやり直せばOKです。

warning: Selected architecture armv8-a is not compatible with reported target architecture aarch64
warning: Architecture rejected target-supplied description

さて、これでgdbがつながったので、デバッグし放題です。いつものinfo registersとかもばっちり動きます。

(gdb) info registers
x0             0x0                 0
x1             0x8192d             530733
x2             0x2                 2
x3             0x80264             524900
...

もちろん、今実行しているバイナリが手元にあれば、それを読み込んでgdbデバッグすることもできます。

$ file target/aarch64-unknown-none-softfloat/release/kernel
target/aarch64-unknown-none-softfloat/release/kernel: ELF 64-bit LSB executable, ARM aarch64, version 1 (SYSV), statically linked, with debug_info, not stripped

$ gdb target/aarch64-unknown-none-softfloat/release/kernel
GNU gdb (GDB) 9.2
...
(gdb) target extended-remote localhost:3333
Remote debugging using localhost:3333
0x00000000000813d8 in kernel::kernel_main ()
(gdb) disas
Dump of assembler code for function _ZN6kernel11kernel_main17h947565f396a80a38E:
   0x0000000000080fd4 <+0>:   sub sp, sp, #0xc0
   0x0000000000080fd8 <+4>:   stp x30, x27, [sp, #112]
(gdb) c
Continuing.

loadコマンドをつかえば、バイナリを動的にメモリ上にロードすることだってできちゃいます。

(gdb) load
Loading section .text, size 0x1674 lma 0x80000
Loading section .rodata, size 0x4c5 lma 0x81678
Loading section .got, size 0x10 lma 0x81b40
Loading section .data, size 0x20 lma 0x81b50
Start address 0x0000000000080000, load size 7017
Transfer rate: 63 KB/sec, 1754 bytes/write.

raspberry piJTAGインターフェイスにはSRSTピンが生えていないため、gdbmonitor resetコマンドを利用してチップをリセットしてロードしたプログラムを再実行させることはできませんが、プログラムカウンタ(pc)を変更することはできるので、代わりに使うといいかもしれません。

(gdb) set $pc=0x80000
(gdb) c

というわけで、とっても便利なJTAGを活用して、皆様も楽しいRasPiベアメタル開発の時間をお過ごしください!

付録: openocdがうまくいかないとき

Error: no device found
Error: unable to open ftdi device with vid 0403, pid 6014, description 'C232HM-DDHSL-0', serial '*' at bus location '*'

→そもそもJTAGアダプタがPCにつながっていない/認識されていない。

Error: JTAG scan chain interrogation failed: all ones
Error: Check JTAG interface, timings, target power, etc.
Error: Trying to use configured scan chain anyway...
Error: auto0.tap: IR capture error; saw 0x0f not 0x01
Warn : Bypassing JTAG setup events due to errors
Error: Invalid ACK (7) in DAP response
Error: JTAG-DP STICKY ERROR

デバッグ対象のデバイスの電源が入っていない/まだ起動直後でJTAGが有効化されてない/配線が間違っている/enable_jtag_gpio=1の設定変更が正しく反映されていない。

liumOS 2020年の進化を振り返る

この記事は自作OS Advent Calendar 2020の「最初の4つの素数の和」日目の記事として作成されました。

liumOSについて

liumOSは、NVDIMM(Non-volatile DIMM, 不揮発性メインメモリ)をネイティブにサポートしている、珍しいタイプの自作OSです。2018年7月26日に開発を開始して以来、記事執筆時点で682 commitsを数えるほどに成長しました。主要開発者はhikaliumですが、後述する通り、ここ数ヶ月間はd0iasmさんにも手伝っていただいていました。

2018年には、自作OSからNVDIMMを触る方法について自作OS Advent Calendar 2018の記事で紹介しましたので、NVDIMMについて知らないよという方や、興味のある方はそちらもぜひお読みください。

hikalium.hatenablog.jp

今年は、かなり色々なものをliumOS上に実装して遊んでいたので、この記事ではそのうちのいくつかについて紹介してみたいと思います。

Adlibを利用したMIDI再生機能

これはOSの中核的な機能ではありませんが、デバイスドライバの実装の一環として、Adlibという非常に古いサウンドバイスのドライバを書いて、さらにMIDIファイルのパーサを書いて再生できるようにしました。実は中学生の頃に開発していた自作OSでもMIDIファイルの再生を試みていたことはあるのですが、当時はビープ音で無理やりなんとか和音を出そうとして結局失敗した記憶があり、その当時のMIDIパーサを再利用してN年越しの目標を達成したのでした。

デモ動画はこちらです。(音が鳴るので注意。)


liumOS Adlib MIDI再生デモ

virtio-netドライバの追加とICMP, DHCPへの対応

前菜を楽しんでいただけたところで、メインディッシュですが、なんとliumOSにネットワーク通信機能を追加しました。

たとえば、pingに応答するデモはこちらです。


liumOS pingデモ

冒頭でさらっと流されていますが、なんとDHCPIPアドレスその他が自動的に割り当てられている点にも注目です!

f:id:hikalium:20201217022248p:plain
ipコマンドで割り当てられたIPアドレスを確認している図

NICドライバとしては、仮想入出力デバイスvirtioのうちのひとつである、virtio-netを実装しています。また、GPD Micro PCで採用されているRTL8168というRealtek社製のNICについても現在ドライバの実装を進めているところです。

UDP通信への対応、ソケットシステムコールの部分的実装、簡単なブラウザアプリの実装

さて、pingができるなら、もうなんでもできますね!だって、パケットを送受信するだけですから。(本当に?)

ということで、UDPプロトコルと、ソケット関連システムコールをいくつか実装し、d0iasmさんによって書かれた簡易ブラウザアプリケーションが動くように環境を整備しました。

たとえば、このようにliumOS内のクライアントから、Linux上で動くサーバーにリクエストを投げればHTMLが返ってきますし、

f:id:hikalium:20201217025756p:plain
liumOS内からHTTPのやりとりをしている図

これをパースしてMarkdownに整形するという簡易ブラウザまで動いてしまいます!

f:id:hikalium:20201217025918p:plain
同じHTTPのやりとりだが、出力をパースしてMarkdownに整形して出力している簡易ブラウザの図

どうですか?自作OSでも、これくらいなら少し頑張ればできるんです!

Web+DB Press Vol.120の特集「自作OS×自作ブラウザで学ぶ Webページが表示されるまで」をd0iasmさんと執筆した

さて、このようなことをしていましたら、ありがたいことに技術評論社Web+DB Press編集部よりお声がけをいただき、自作OSと自作ブラウザを通して、Webページが表示されるまでの流れを、文字通り上から下まで一通り追ってゆく記事を執筆させていただく機会を得ました。

gihyo.jp

Webページが表示されるまでに、HTTPのリクエストがどのようにしてパケットにまで落とし込まれて、レスポンスとしてのHTMLがどのようなパスを通って運ばれてゆき、最終的に目に見える形になるのか、ということを解説した、合計36ページの特集となっておりますので、面白そう!と思っていただけたなら、ぜひ書店で内容を確認したり、購入して読んでいただけたりしたら大変嬉しく思います。12/24発売です!

この特集の概要の紹介や、デモを交えた動画を近日中にアップロードする予定ですので、そちらもお楽しみに!

www.youtube.com

今後の展望など

やりたいことは無限にあって永遠に楽しめるのが自作OSのよいところですが、ある程度目標を立てておいたほうが物事を進めやすいのは確かです。ということで、いくつかここで私がやりたいと思っていることを書き連ねておくことにします。

GUIサポートを向上させる

現在のところ、liumOSにはほとんどGUIと呼べるものがありません。画面描画を行うAPIはアプリケーションに対して提供されていませんし、入力インターフェイスについても、ほんの少し前にPS/2マウスのサポートがやっと入ったほどです。そのため、先ほど紹介した特集でも、CUIブラウザを実装するのがやっとの状態でした。

せっかくブラウザの下回りができたなら、CSSで文字を大きく表示したり色を変えたり、なんなら文字列を<blink>させたいですよね?(とはいえblinkタグはすでに廃止されていますが…。)

ということで、ある程度の描画がアプリケーション側からできるような仕組みを近いうちに用意し、ついでにブラウザの実装も拡張したいなあと思っています。

RustでOS本体を書き直す

現在のliumOSはC++で書かれています。C++が使えるだけでもC言語に比べれば大きな進歩だったのですが、やはりメモリ安全性という面ではC言語と五十歩百歩と言わざるを得ません。最近応用が広がってきたRustであれば、より安全にプログラムを書くことができます。ということで、Rustでカーネルを書き直すことを現在検討しています。すでに、Rustで書かれたカーネルを従来のliumOSローダーが起動できるところまでは確認しているため、あとは実装するだけという状況なのですが、うまいことインクリメンタルにできないものか、考えつつ現在進めているところです。(まあ、いつか気分が乗った時にえいやっと書き換えることになりそうな気がしますが…。)

ネットワーク機能の拡張

現在のliumOSのネットワークまわりはかなりアドホックに実装されており、複数のNICをうまく扱えない、ソケットの実装がはりぼてすぎる、たまにドライバがこけるなどの問題が発生しています。特に、ドライバを書くというのは自作OSにとって頭の痛い問題ですが、私としてはネットワークドライバほど実装しておいしいものは他にないのではないかと考えています。というのも、基本的な機能としては「パケットを送信する」「パケットを受信する」の2つしかありませんし、ネットワークの先になにがあるかを私たちは意識する必要がないからです。たとえば、自作OSでファイルを保存できるところまで到達しているケースはかなり少ない(liumOSはNVDIMMに対応しているのでなんでも保存できる!…と言い張ることができるかもしれない)ですが、ネットワーク通信さえ対応してしまえば、保存すべきファイルをネットワーク越しに送信するようにすることで、自作OS側でドライバを書かなくて済む可能性が出てきます。(もちろん、各種プロトコルを実装する必要がありますが…。)あと、自作OS同士が独自のプロトコルで通信するのをみてみたい、という気持ちもかなりあります。ということで、おそらくネットワーク周りの機能はそれなりに重点的に進めていくことになるような気がしています。

おわりに

そういうわけで、今年もいろいろな機能がliumOSには生えましたし、今後も生やしていくつもりではいるのですが、ここで大事なことをひとつ。

自分が楽しいと思えることをやっていきましょう!最初から完璧なものを作る必要はありません。なにせ、一番のユーザーは自分自身なのですから。

自分以外のユーザーが出てきたら、そのときはそのときでまた考えましょう!(なおliumOSにはついにアプリ開発者(@d0iasm)が登場したので、大急ぎでテストを書いたりドキュメントの修正をしたりしていました。もちろんこれも楽しいからやってるんですけどね!)

ということで、このご時世で家にいる時間も多くなってきていると思いますので、皆様ぜひ暖かい部屋でゆっくりしながら、のんびりとした自作OSライフをお楽しみください!ではでは!

SECCON 2020 OnlineCTF writeup -- SCSBX:Reversing

概要

f:id:hikalium:20201011204310p:plain

今年も例年のように、チームHarekazeの一員として出ました。チームの結果は2123点で11位/579チーム(何らかのFLAGを提出したチーム数)でした。 そのうち、私はSCSBX:Reversingを解いて129ポイントを稼ぎました。(st98さんが一人で1552ポイントも稼いでおり目を回しています。)

あと、同じSCSBXをテーマにしたSCSBX:Escapeや、脆弱なkernel moduleの秘孔を突くkstackという問題にも挑戦しましたが、時間内に解くまでにはいたりませんでした。

ということで、挑戦した各問題の解法 or 挑戦のようすを書いておきます。

SCSBX:Reversing

f:id:hikalium:20201011194731p:plain

ソースコードの公開された独自のバイトコード処理系と、それ向けに書かれたアプリケーションのバイナリが与えられています。 そのアプリケーションは、入力がフラグであるか否かを教えてくれるものでした。

$ ./scsbx seccon.bin 
FLAG: hogehoge
Wrong!!

ということで、その処理をみてみれば、どのような入力が期待されているのか、つまりフラグがわかりそうです。ということで、読んでいきましょう。

VMソースコードを読んでみる

ファイルとしてはこんな感じ。

$ ls
Makefile          instr_logic.cpp  main.cpp
instr_arith.cpp   instr_mem.cpp    scsbx.cpp
instr_branch.cpp  instr_sys.cpp    scsbx.hpp

C++で書かれているんですねー。たとえば、scsbx.cppの中をみてみると、

void SCSBX::__cpu_exec(u8 instr)
{
  u32 val;

  switch(instr) {
    /* Memory Operation */
  case INS_PUSH:
    val = *(u32*)(&code[pc+1]);
    __stack_push(val);
    pc += 4;
    break;
  case INS_POP:
    __stack_pop();
    break;
  case INS_DUP:
    __stack_dup();
    break;
  case INS_XCHG:
    __stack_xchg();
    break;
  case INS_LOAD32:
    __mem_load32();
    break;
  case INS_LOAD64:
    __mem_load64();
    break;
  case INS_STORE8:
    __mem_store8();

という感じで、非常に素直に書かれています。

また、DOCS.md というファイルも含まれていたのでみてみると、命令形式についての説明やメモリレイアウトについても書かれていました。めっちゃ親切。

### Instruction
Every instruction except for `push` is 1-byte long.
`push` accepts a 4-byte value to push into the stack.
**SCSBX is proudly open-sourced!**
Check the source code for more details.
0x00000000 +-------------------+
           |                   |
           |     Free Space    |
0x55540000 +-------------------+
           | Machine Code (R-) |
           +-------------------+
           |                   |
           |     Free Space    |
           |                   |
0xfffe0000 +-------------------+
           |     Stack (RW)    |
0xffff0000 +-------------------+  ^^^ user-space ^^^
           |  Guard Page (--)  |
0xffffffff +-------------------+  vvv  VM-space  vvv
           |    VM instance    |
           |        ...        |

とりあえず、PUSH命令以外はすべて1バイトのスタックマシンということがわかったので、さくっとディスアセンブラを書きます。というか、VMソースコードを改造して、オプションを渡したらdisasしてくれるようにしました。その出力がこちら。

$ ./scsbx ../seccon.bin -d
00000000: 20 00001000: push
00000005: 20 DEAD0000: push
0000000A: 62: map
0000000B: 20 00000256: push
00000010: 34: call
00000011: 20 0000020A: push
00000016: 34: call
00000017: 20 47414C46: push
0000001C: 20 DEAD0004: push
00000021: 28: store32
00000022: 20 0000203A: push
00000027: 20 DEAD0008: push
0000002C: 27: store16
0000002D: 20 00000006: push
00000032: 20 DEAD0004: push
00000037: 61: write
00000038: 20 00000040: push
0000003D: 20 DEAD000A: push
00000042: 60: read
00000043: 20 00000008: push
00000048: 20 0000010E: push
...

やっぱりスタックマシンだし長いですね。というわけで、じっとこれを見つめてデコンパイラごっこをします。

私なりのやり方としては、大体以下のような手順を踏みました。

  1. 分岐命令を境に、命令列をブロックに分ける。
  2. 上から辿っていって何をやっているかお気持ちを理解する
  3. 複雑な部分では、スタックを書いて追いながらロジックを推定する

たとえばこんな感じに、スタックの使われ方を書いていったり、

<check_loop()>
/*
[0] k
[1] v
*/
00000135: 20 00000000: push
0000013A: 22: dup
0000013B: 20 00000001: push
00000140: 20 00000001: push
00000145: 23: xchg
00000146: 41: sub
/*
[0] k - 1
[0] k
[1] v
*/
00000147: 20 00000008: push
0000014C: 42: mul
/*
[0] (k - 1) * 8
[0] k
[1] v
*/
0000014D: 20 DEAD000A: push
00000152: 40: add
/*
[0] (k - 1) * 8 + 0xDEAD000A
[0] k
[1] v
*/

...(省略)

00000183: 20 00000001: push
00000188: 23: xchg
/*
[2] k
[0] v | (*p - *q) | (*(p + 4) - *(q + 4))
*/
00000189: 20 00000001: push
0000018E: 20 00000001: push
00000193: 23: xchg
00000194: 41: sub
/*
[2] k - 1
[0] v | (*p - *q) | (*(p + 4) - *(q + 4))
*/

これを元にC言語ベースの擬似コードに落とし込んだりしてみました。

int main(int argc, char *argv) {
  // 00000000
  // map [DEAD0000 - DEAD1000)
  InitEncFlag();
  // 0000020A
  *(uint32_t *)&mem[0] = 0x06D35BCD;
  // 00000017
  // read 0x40 bytes into *0xDEAD000A
  strncpy(&mem[0xA], "SECCON{[\x20-\x7e]+}", 0x40);
  uint32_t i = 8; // pushed at +00000043
  // 0000010E
  // [] i
  while(i) {
    // 0000004E
    // 000000DD
    // Stack after 00000097
    // []: *((8-i) * 8 + 0xDEAD000E) = v1
    // []: *(8-i) * 8 + 0xDEAD000A) = v2
    // []: (8-i) * 8 + 0xDEAD000A
    // []: (8-i) * 8 + 0xDEAD000E
    // []: i
    uint32_t v1 = *((8-i) * 8 + 0xE + mem);
    uint32_t v2 = *((8-i) * 8 + 0xA + mem);
    uint32_t p = 3; // pushed at +00000098
    // 000000DD
    while(p) {
      // 000000A3
      // []: p
      // []: v1
      // []: v2
      p--;
      uint32_t c = v2;
      v2 = v1;
      v1 = random_num(v1) ^ c;
    }
    // 000000F3
    // []: p
    // []: v1
    // []: v2
    // []: (8-i) * 8 + 0xDEAD000A
    // []: (8-i) * 8 + 0xDEAD000E
    // []: i
    *((8-i) * 8 + 0xE + mem) = v1;
    *((8-i) * 8 + 0xA + mem) = v2;
    i--;  // 00000102 - 0000010D
    // 0000010E
  };
  // check if flag_buf is same as flag_encrypted
  ...
}

さて、デコンパイラの気持ちを理解したところで、このプログラムは大体以下のような処理を行っていることがわかりました。

  1. 作業用のメモリ領域[0xDEAD0000 - 0xDEAD1000)をmapする
  2. そのメモリ領域に符号化されたフラグを展開する(0xDEAD004A から0x40バイト)
  3. 0xDEAD0000番地に値0x06D35BCDを格納する(おそらく何らかのシード値、後のロジックで使われる)
  4. ユーザーからの入力を受け取る(0x40バイト、これは0xDEAD000A番地から0x40バイトの空間に格納される)
  5. 上の擬似コードに書いたような処理を行って、ユーザーからの入力を符号化する
  6. 符号化した入力(0xDEAD000Aからの0x40バイト)と、展開しておいた符号化済みのフラグ値(0xDEAD004Aからの0x40バイト)を比較する
  7. それらが一致したらCorrect, 一致しなければWrong!!と出力して終了する

さて、肝心のstep5の処理ですが、擬似コードとしてはこんな感じです。(enc()がその処理)

uint32_t random_num(uint32_t v) {
  // 00000216
  uint32_t *dead0000 = (uint32_t *)&mem[0];
  *dead0000 = (*dead0000 * 0x77F - 0x32A) % 0x0x305EB3EA;
  return ~(v ^ *dead0000);
}
void enc() {
  uint32_t i = 8; // pushed at +00000043
  // 0000010E
  while(i) {
    // 0000004E
    // 000000DD
    uint32_t v1 = *((8-i) * 8 + 0xE + mem);
    uint32_t v2 = *((8-i) * 8 + 0xA + mem);
    uint32_t p = 3; // pushed at +00000098
    // 000000DD
    while(p) {
      // 000000A3
      p--;
      uint32_t c = v2;
      v2 = v1;
      v1 = random_num(v1) ^ c;
    }
    // 000000F3
    *((8-i) * 8 + 0xE + mem) = v1;
    *((8-i) * 8 + 0xA + mem) = v2;
    i--;  // 00000102 - 0000010D
    // 0000010E
  }
}

要するに、8バイトを1セットとして符号化するのを8回くりかえすことで、8*8 = 64 = 0x40バイトの領域を符号化しているわけです。 また、random_num()と仮においた処理は、0xDEAD0000番地のメモリ内容という状態を持っているため、呼び出しには副作用があります。 とはいえ、基本的にやっていることは、その8バイトの中で前後4バイトずつの部分をxorしているだけで、入力と出力は各桁ごとに独立に変化します。 結局、random_num()の状態に注意しつつ、8バイトずつのセットの各文字を順に確定させてゆけば、フラグがわかりそうです。(これなら最大でも256 * 8 * 8通り調べればいけますね。)

というわけで、このアイディアをかんたんなC言語のプログラムに落とし込みました。

#include <stdint.h>
#include <stdio.h>

uint32_t dead0000 = 0x06D35BCD;

uint32_t random_num(uint32_t v) {
  // 00000216
  dead0000 = (dead0000 * 0x77F - 0x32A) % 0x305EB3EA;
  return ~(v ^ dead0000);
}

uint64_t enc(uint64_t v) {
  uint32_t v1 = v >> 32;
  uint32_t v2 = v;
  uint32_t p = 3;  // pushed at +00000098
  while (p) {
    p--;
    uint32_t c = v2;
    v2 = v1;
    v1 = random_num(v1) ^ c;
  }
  return ((uint64_t)v1 << 32) | v2;
}

uint8_t mem[64];

void InitEncFlag() {
  // 00000256
  *(uint32_t *)&mem[4 * 0x0] = 0x46761223;
  *(uint32_t *)&mem[4 * 0x1] = 0x54BEA5C5;
  *(uint32_t *)&mem[4 * 0x2] = 0x7A22E8F6;
  *(uint32_t *)&mem[4 * 0x3] = 0x5DB493C9;
  *(uint32_t *)&mem[4 * 0x4] = 0x055D175E;
  *(uint32_t *)&mem[4 * 0x5] = 0x022FCD33;
  *(uint32_t *)&mem[4 * 0x6] = 0x42C46BE6;
  *(uint32_t *)&mem[4 * 0x7] = 0x6D10A0E8;
  *(uint32_t *)&mem[4 * 0x8] = 0x53F4C278;
  *(uint32_t *)&mem[4 * 0x9] = 0x7279EC2A;
  *(uint32_t *)&mem[4 * 0xA] = 0x5491FB39;
  *(uint32_t *)&mem[4 * 0xB] = 0x49AC421F;
  *(uint32_t *)&mem[4 * 0xC] = 0x49AB3A37;
  *(uint32_t *)&mem[4 * 0xD] = 0x47855812;
  *(uint32_t *)&mem[4 * 0xE] = 0x5718BB05;
  *(uint32_t *)&mem[4 * 0xF] = 0x0540FB5B;
}

int main(int argc, char *argv[]) {
  InitEncFlag();
  char buf[64 + 1] = "SECCON{........";

  for (int i = 0; i < 8; i++) {
    for (int k = 0; k < 8; k++) {
      for (char c = 0x20; c <= 0x7E; c++) {
        buf[k] = c;
        uint32_t prev_dead0000 = dead0000;
        uint64_t e = enc(*(uint64_t *)buf);
        uint8_t *p = (uint8_t *)&e;
        dead0000 = prev_dead0000;
        if (p[k] == mem[k + i * 8]) {
          break;
        }
      }
    }
    uint64_t e = enc(*(uint64_t *)buf);
    printf("%.8s", buf);
  }

  return 0;
}

気をつけるべき点は、forの中でencを実行する際に、毎回dead0000の内容を戻しているところですね。(少し冗長ですが色々ためしていたせいである。)

というわけで、以下のような出力を得ました。

$ ./solve2 
SECCON{TfuRYYVaz8Us696t3JWNxZZPsXEmdL7cCmgzpgxXKarUOnIwhSj9tQ}~~

SECCON{の後にはTがきそう(きっと英語のメッセージ的にTheとかがきそうだから)と思っていて、最初の8桁だけ試してTがでてきてわーいと思っていたのですが、全部出してみたら乱数フラグでちょっと意外でした。(ちゃんと通ってほっとした。)

追記

このアルゴリズムはFeistel構造と呼ばれるものらしい。

ja.wikipedia.org

SCSBX:Escape

ところでこのSCSBX(SecCon SandBoX), reversingだけでなくsandboxの問題としても登場していました。

f:id:hikalium:20201011202618p:plain

こちらは、リモートで動いているSCSBXにいい感じのバイナリを送りつけて、思い通りの動きをさせてshellをゲットしような!という問題だったのだと思います。

SCSBXの説明文にこんな一文がありますが、

### Direct Memory Access
SCSBX allows the program to directly access to the host memory.
This may sound dangerous but the program can only use the 32-bit
address space. Since SCSBX runs on a 64-bit machine with PIE enabled,
there's no way the user can read/write the VM memory directly.

明らかにこれはアヤシイ!と思いますよね。というわけで、じっとソースコードを見つめると、

void SCSBX::__sys_unmap()
{
  u64 address = ((u64)__stack_pop()) & ~0xfff;
  __assert_address_valid(address);

  for(auto itr = memmap.begin(); itr != memmap.end(); ++itr) {
    if (address == itr->first) {
      memmap.erase(itr);
      munmap((void*)address, itr->second);
      return;
    }
  }

  throw MEMORY_ERROR;
}

ほう、munmapの戻り値を確認しないとは勇気がありますね?というところを見つけられます。これは何に役立つかと言うと、メモリマップで言う

0x00000000 +-------------------+
           |                   |
           |     Free Space    |
0x55540000 +-------------------+
           | Machine Code (R-) |
           +-------------------+
           |                   |
           |     Free Space    |
           |                   |
0xfffe0000 +-------------------+
           |     Stack (RW)    |
0xffff0000 +-------------------+  ^^^ user-space ^^^
           |  Guard Page (--)  |
0xffffffff +-------------------+  vvv  VM-space  vvv
           |    VM instance    |
           |        ...        |

Guard Pageを除去するのに使えます。というのも、このGuard Pageは、実際にmapされているわけではなく、

SCSBX::SCSBX(u8 *_code, u32 _size)
{
  /* Guard page */
  memmap.push_back(std::make_pair((u64)STACK_BASE + (u64)STACK_SIZE_INIT,
                                  0x100000000 - (u64)STACK_BASE - (u64)STACK_SIZE_INIT));
}

という感じでVMの初期化時に「確保済みのメモリ領域」として予約されているだけなのです。この結果として、VMはこの領域にアクセスするとマップされていないのでSEGVがおきるし、マップしようにもマップ済みなのでmapを実行できない…はずなのですが、先ほどのようにmunmap命令が実行されると、munmapの結果にかかわらずこのmemmapというリストから除去が行われるため、なんとこの領域をmunmapしてから再度mmapすれば、普通にアクセスできるようになってしまうというバグがあったわけです。

で、ここにアクセスできると何がやばいかというと、Stackが伸びていくとやがてこのGuardPageにあたり、さらにそこを超えるとVM instance、つまりクラスSCSBXのインスタンスが確保されている領域を上書きできてしまうのです。

というわけで、たとえばこうすれば

  // unmap guard page
  instr_push(0xffff0000);
  instr_unmap();
  // map again
  instr_push(0x00010000);
  instr_push(0xffff0000);
  instr_map();

あとはstackをばんばん伸ばすだけでやがてこの構造体を上書きできるようになります。

class SCSBX {
private:
  /* fields */
  std::vector<std::pair<u64, u32>> memmap;

  u32 pc;
  int status;

  u8* code;
  u32* stack;
  u32 code_size;
  u32 capacity;
  u32 top;
...
  virtual void __assert_address_valid(u64 address);
  virtual void __assert_range_valid(u64 address, u64 size);
  virtual void __assert_resource_available(u64 address, u32 size);
...
};

しかもこの構造体、virtual関数としてアドレス範囲チェック系の重要な関数のポインタが記録されている場所でもあるので、ここをいい感じにRETを指すポインタように上書きすれば、チェックを全部回避することも、さらに任意のアドレスに実行を飛ばすこともできます。

…というところまでわかって、時間切れでした。ざんねん。

pythonが得意ではないので、hashのチャレンジレスポンスを解きつつ、ペイロードを突っ込むスクリプトを将来また書かなくてもいいようにここに貼っておきます。

from pwn import *
import itertools
import hashlib
import string
import sys

print(sys.argv[1])
f = open(sys.argv[1], "rb")
attack_bytes = f.read()

table = string.ascii_letters + string.digits + "._"

p = remote('pwn-neko.chal.seccon.jp', 19001)
ret = p.recvline().decode("utf-8") 
# ret = 'sha256("????LFx0jSq8mYA4oZC_.Kuw") = ca67aa308662f39b8e294a99120588102a94

hashval = ret.split("=")[-1].strip()
print(hashval)
suffix = ret.split("\"")[1].replace("?", "")
print(suffix)

for v in itertools.product(table, repeat=4):
    if hashlib.sha256((''.join(v) + suffix).encode()).hexdigest() == hashval:
        prefix = ''.join(v)
        break
else:
    print("[-] Solution not found :thinking_face:")

print("[+] Prefix = " + prefix)
p.sendline(prefix)
p.recvuntil('size')
p.sendline(str(len(attack_bytes)))
p.recvuntil('code')
p.sendline(attack_bytes)
p.interactive()

kstack

f:id:hikalium:20201011204833p:plain

なんか/proc/stackというファイルに対するioctlを生やすkernel moduleが入ったマシンにつながるので、そいつのバグを突いて権限昇格しようね、という問題だったようです。 QEMUで実行できるようイメージと引数の書かれたシェルスクリプトが一緒に配られていて、めちゃくちゃ親切でうれしかったです。

ioctlの仕様としては、ioctl(fd, CMD_PUSH, &value)を発行すると、その値がユーザーランドからカーネル空間のスタック(実体は各要素がkmalloc(GFP_KERNEL)で確保されたLinked List)に格納され、ioctl(fd, CMD_POP, &value)を発行すると、そのカーネル空間のスタックからユーザーランドに値がコピーされていく、というものでした。 ちなみに、そのLinked Listの各要素には、格納したタスクのtgidが一緒に記録されていて、あるtgidが記録したデータに対する操作はそのtgidからしかできないようになっていました。

これについては全然進捗がなくて、複数タスクから同時にPOP処理をかけたら、解放された領域を指し続けるLinked Listが構成できそうとか、pidがぐるっと一周したらどうなる?とか色々あったのですが、結局時間も割けなくてとけませんでした。もっとカーネルに詳しくなりたいですね。

作問者による簡易解説ツイート

感想

バイナリおいしい!あとカーネルむずかしい…。

全体的に、問題のクオリティがかなり上がっているという印象を受けました。とてもよいことだと思います。それに、何より問題を解くのが楽しかったです。(可視化とかも面白かった。)

運営のみなさん本当にお疲れ様でした!ありがとうございましたー!

ISUCON10予選 meguryohikaの記録

ISUCON10の予選にmeguryohikaとして @megumish_unsafe, @systemctl_ryoto と共に出たのでその記録です。

結果としては、初期スコア500点台から、900点台の、1000点に届きそうかな?というところまでは行けたものの、最後のベンチマーク前に複数台構成にしようとして失敗した結果スコアがつかずおしまいでした。来年もまたやりたいですね!

ISUCONは参加者だけじゃなくて運営にも降りかかる…

午前10:00から試合開始ということで、前日は人々とイカをやるのも午前1時までにとどめておき、無事健康的な午前起床を達成しました。

ところが、その少しまえに、こんなツイートが運営から…

ということで、私の目覚める前からISUCONは始まっていたようです。私たちの開始は昼ごろまで遅れたけれど。(運営のみなさんお疲れ様でした!)

正午までの暇を持て余して環境が整う

2時間の余裕を得た我々は、「二度寝するなよ!」というネタをやったり、眠気覚ましにご飯を買いにいく人々が出たりと自由な雰囲気が漂っていました。

私も、あまりにも暇だったので、ちょうど横にあるLinuxマシンを、負荷をかけている際のCPU統計などを表示するのに適したようにセットアップしたいなあという気持ちになって、apt updateしたり、NVIDIAGPUドライバを入れたりしていました。(なんとドライバを入れていなかったので、1024*768の解像度になっていた…これでは流石にきついと思ったので急いでセットアップした。)

そんなわけで、少し環境がリッチになったあたりで、試合開始が12:20からになるとの連絡が。やっていきましょう!

試合開始…からのポータルが503 Service Unavailable

我々はGoで実装を進めるつもりだった&初期実装がGoと書いてあったので、早速ベンチマーカーを回そうとしたところ…なんとポータルが503に。ISUCONむずかしいね…。

というわけで、しばらくベンチマーカーの結果は拝めそうになかったので、megumish氏はソースコードやリソースの退避とデプロイスクリプトの作成を、ryotoさんはbotを弾くnginx configをさっと書いてくれたり、ソースを読んでSQL的にヤバそうなところがないかをしらべてくれたりしていました。私はアプリを実際に触ってみて、遅い部分とか面白い部分がないかをしらべてみていました。「なぞって検索」なる、地図上に領域を描いて物件を検索できるページがあったのにはびっくりしました。また、今回は前回までと異なり、サイトへのログインという概念がなかったため、その点でも度肝を抜かれました。(ついつい/adminが存在しないか調べてしまったが、なかった…。)

14:00の定時報

前回までの反省と、チームでこれまで練習してきたことを生かして、今回は1時間ごとにさくっと進捗共有会をすることにしました。そして、進捗共有がおわったら、強制的に5分間休憩タイムをとることにしていました。これは体力を消耗しないという点では非常によい戦略だったと思います。(今までは終盤になると、精神的にもかなり疲れがきていたのですが、今回は最後までゆったりできたので割とおすすめです。)

このあたりで、megumish氏がデプロイスクリプトを完成させていて、次はredisを入れてキャッシュできるものはやっていこうか、という流れになっていました。 ryotoさんはAPIの各エンドポイントをみ終わって、いくつか修正できそうな点がみつかったので直していく、という話になっていました。

私は、やっと初のベンチを走らせてみて、nginxのログをkataribeでフォーマットしてどのエンドポイントを直すのがよさそうか議論する材料を用意しました。

Top 20 Sort By Total
Count   Total    Mean  Stddev    Min  P50.0  P90.0  P95.0  P99.0    Max  2xx  3xx  4xx  5xx  TotalBytes   MinBytes  MeanBytes   MaxBytes  Request
  105  40.860  0.3891  0.4355  0.046  0.178  1.085  1.397  1.698  2.000  103    0    2    0     1700275          0      16193      33967  POST /api/estate/nazotte HTTP/1.1
  411  33.686  0.0820  0.0246  0.031  0.078  0.115  0.123  0.151  0.206  411    0    0    0     4989248      12139      12139      12153  GET /api/chair/low_priced HTTP/1.1
  411  31.674  0.0771  0.0266  0.032  0.072  0.115  0.127  0.155  0.182  411    0    0    0     5500577      13383      13383      13398  GET /api/estate/low_priced HTTP/1.1
   86  14.241  0.1656  0.0457  0.087  0.157  0.234  0.247  0.271  0.271   86    0    0    0     1429937      16627      16627      16642  GET /api/estate/search?page=0&perPage=25&rentRangeId=1 HTTP/1.1
   67  10.303  0.1538  0.0388  0.093  0.138  0.213  0.223  0.259  0.259   67    0    0    0     1124707      16786      16786      16801  GET /api/estate/search?page=0&perPage=25&rentRangeId=2 HTTP/1.1
   72  10.238  0.1422  0.0348  0.094  0.132  0.194  0.205  0.230  0.230   72    0    0    0     1199601      16660      16661      16682  GET /api/estate/search?page=0&perPage=25&rentRangeId=0 HTTP/1.1

トータルでかかった時間としては、やはり「なぞって検索」が重く、次いで物件と椅子の安い順に上位20件をリストアップするlow_pricedが、一回一回は重くないものの、回数が多いためけっこう負荷になっていることがわかりました。あとは、検索部分が重く、今回のサービスの検索では、かなり多種多様な条件を指定できることがわかっていたので、何らかの高速化が必要だろうね、という話になりました。

例えば、searchで指定する条件には、各物件や椅子の属性(features)というのがあって、これはDBにはカンマ区切りの文字列として格納されているのですが、検索時にはそれらのAND条件を指定できる、というもので、当初の実装では全件リードが走っている状態になっており、まあ重いのは致し方ないかな、という感じでした。

改善のアイディアとしては、featuresの各要素は固定で50件であることから、各属性に対応するboolのカラム50列をDBに追加して、ついでにindexも貼ってあげればいい感じになるんじゃないか?と考えて、以後私はそれに取り組むことにしました。

ちなみに、初期状態でのベンチ終了時点では、データが3万件それぞれのテーブル(chair, estate)に入っており、初期データには2万9500件入っている、ということがわかっていました。なので、実行時に動的に増加する分は、最初は500件ということです。(おそらく、負荷レベルが向上すると、ここが増えたのでしょうが、残念ながらそこまで行きつきませんでした…。)

また、単一サーバー(1 core, 2GB RAM)でDB, Webアプリを同時に動かしている状態でベンチマークをかけても、CPU時間は100%に張り付く一方、メモリ消費量は500MBもいかない程度で、swapも全く発生していないという点に気付きました。かなりCPUに集中した負荷がかかっていたようです。当初、私はこれがMySQLのメモリ設定が厳しすぎるせいだと考えて、緩和する設定を入れてみたのですが、残念ながら全く使用量が増えなかったので、ボトルネックは別の部分にあったようです。

15:00の定期報告

このあたりで、megumish氏はGET chair/low_pricedの結果をキャッシュできないか奮闘していました。

ryotoさんは、全く貼られていなかったindexをDBに貼ったところ、100点程度のスコア向上がみられたと報告していました。

また、なぞって検索に関して、矩形で大まかに物件をフィルタしたあと、その各物件に対して、GIS関連の関数を用いて、描かれたポリゴンの内部にその物件が存在するか否かをチェックしているということがわかり、これをDBに毎回投げるのではなく、Goの側でうまく処理できないかということを検討していました。

私は、先ほど言ったMySQL周りのチューニングが効果ゼロだったことを報告して、もしかするとDBやアプリを複数サーバーに分散させる必要があるのかもしれないと言いつつ、とりあえずfeaturesをbooleanでDBの複数カラムに格納するものに着手するという話になっていました。

16:00の定期報告

megumish氏は、キャッシュの大まかな実装はできたけれど、うまくベンチが通らず四苦八苦していました。

ryotoさんは、椅子を購入すると、物件がrecommendされる(椅子が通るような玄関の間口をもつ家がリコメンドされるシステムだった!)機能のぶぶんを、事前にテーブルを作成することで高速化できないか挑戦していました。

私は、chairのfeaturesをカラム化することを引き続き挑戦していました。

17:00

ほぼ同上。だんだんつらくなってくるね。

f:id:hikalium:20200913000124p:plain
縦に長すぎるchairのschemaの図(実際にはf50まで続いたあと、さらに同じ個数のindexが張られている)

18:00

megumish氏は、キャッシュをするのはいいけれど、レースコンディションがおきたらどうなるんだろう?という問題に頭を悩ませていました。

ryotoさんは、椅子に合った不動産をおすすめする部分の改善目処がつきそうという報告をしており、それが終わり次第、なぞって検索に取り掛かるという目標を掲げていました。

私は、featuresをカラムにし終わったものの、なぜかベンチマークが通らない問題で時間をつぶしていました。(サーバーにデプロイしてみるとうまく動いているように見えた。)

糖分が足りなくなってきたので、ここらへんでクレープをたべました。おいしかったです。

f:id:hikalium:20200912233946j:plain

19:00

megumish氏の実装のバグが取れたとの報告。JSONが正しく吐けていなかったみたい。とりあえずうまくいったら、次は複数台構成の検討に入るとのこと。

ryotoさんは、物件おすすめ機能をあきらめました。というのも、冷静に考えると、事前計算をする処理はかなり重く、また椅子や物件を追加するAPIの時間制限はわりと厳しかったため、時間内に事前計算を終わらせられそうにないというのが理由でした。

今思えば、全部を事前計算せずとも、一度計算したものをキャッシュしておく、などの方策がとれたかもしれないなあ、という感想が浮かんできました。(後から振り返るとそういうアイディアが思いつく。)

私は、クレープの糖分をもってしてもバグを解決できず、なんでだーと頭を抱えていました。

さいご

最後ぎりぎりになって、ryotoさんがなぞって検索のジオメトリ計算の部分をgolangに持ってくることに成功し、これで+300程度になりました。

さらに、私もベンチマークが失敗する理由に気付き(デプロイ時に走るDB初期化と、ベンチマーク時に走るinitialize/内でのDB初期化で異なるデータを流し込んでいた)、なんとかマージに成功。

最終的に、これでスコアが900点ちょい出たのですが、複数台構成を試そうとしてぎりぎりまでryotoさんが頑張ったものの、間に合わず終了時刻を迎えました。いやはや、よくがんばりました…。

反省点

  • 複数台構成を練習時にもあまりできておらず、本番でも手間取って間に合わずじまいになってしまった。練習でできないことは本番でもできないよ!
  • 当初リストアップしていた修正できそうな点のうち、ひとつを見過ごしてしまっていた。(終わった後に気づいた。)
    • 報告会を定期的にしていたのは非常によかったが、ToDoの管理が不十分だった。見ないToDoに意味はないよ!
  • 複数台構成の件にもつながるが、本番サーバー以外に実行環境を用意できていれば、もう少し開発を効率的に行えたかもしれない。

まとめ

来年はさらに準備して望みたい…またがんばりましょう!おつかれさまでした!

f:id:hikalium:20200912235608p:plain
14:30頃のつかの間の15位の図

追記: チームメンバーのryotoさんとツイート被りしていたことが判明(終わるまで全く気づかなかった)(みんな考えることは同じである)

C言語から0番地へアクセスする方法についての個人的まとめ

発端はuchan_nos氏によるこのツイートでした。

それに対する私のリプライ:

私はこれで話が終わると思っていたのだが、どうやらそうではなかったらしく、色々な視点からの意見が加わりながら、話は混沌を極めたのでした…。

ということで、ここに私のこのツイートに対しての見解とか、わかったことをまとめておこうと思います。

私のリプライの背景について

uchanさんが求める「0番地にデータを書きたい」という課題設定を、私はこのように解釈しました。

  • C言語において、整数0をポインタに変換すると、それはNULLポインタになる
  • C言語において、NULLポインタへのアクセスは未定義動作である
  • したがって、0番地にデータを書くことはできないのではないだろうか?
  • これをすり抜ける方法はあるか?

これを受けて、私はこのように考えました。

  • NULLポインタへのアクセスが未定義となるのはコンパイル時の話である
  • ではコンパイル時にNULLポインタであるとコンパイラにバレなければ未定義動作にならないのではないだろうか?
  • じゃあアドレス1を代入してポインタをつくり、それを引き算して0番地へのポインタをつくれば、コンパイラは見逃してくれるのではないだろうか?

そして、以下のコード片が生まれたわけです。

uint8_t *p = 1;  p--; *p = v;

ここで、vは何らかのuint8_t型の書き込みたいデータである(と文脈からわかると期待)。

仕様上の問題

しかしその後、有識者の人々がにわかにざわつき始めた。そして、私の提示したコードはやはり動かないということをherumiさんがありがたくも指摘してくださったわけです。

では仕様上、単なる0番地への代入コードや、私の書いたコードがなぜうまく動かないのかをみていきましょう。

0をポインタにキャストするとそれはnull pointerになる (6.3.2.3 - 3)

この仕様によれば、整数定数0となるような定数式をポインタにキャストすると、それはnull pointerになる。 そして、null pointerは、いかなるオブジェクトや関数へのポインタとも等しくならないことが保証されている。

null pointerを用いた間接参照は未定義動作になる (6.5.3.2 - 4)

この仕様によれば、*演算子を用いた間接参照をするときに、その参照が「無効なもの」であるとき、*演算子の挙動は未定義となる。 ここでいう「無効なもの」には、null pointerも含まれると注釈102に書かれている。


したがって、0番地に1を書き込もうとして *(uint8_t *)0 = 1; と書いてもこれは未定義動作になる これは、整数定数0をポインタにキャストしたもの(uint8_t *)0がnull pointerであり(ここまでは定義された動作)、これへの間接参照が「null pointerを用いた間接参照」になるためである。

この、null pointerへの間接参照を回避するための方法として私が編み出したのがuint8_t *p = 1; p--; *p = v;であるが、これも以下の仕様によって「処理系定義」の動作になる。

整数からポインタへの変換は処理系定義である (6.3.2.3 - 5)

この仕様によれば、整数からポインタへの変換を行ってもよいが、その結果は処理系定義になるという。 つまり、たとえアドレス1を表現しようとして(uint8_t *)1と書いても、その内部表現が整数1と等しくなるとは保証されないということである。


したがって、uint8_t *p = 1; p--; *p = v;と書いても、最初のuint8_t *p = 1;の段階でpがどこを指しているかは処理系の動作に完全に依存し、1番地を指しているとは限らないため、私の提案した方法は残念ながら処理系定義の結果になる。

しかも、最適化によって、コンパイラ*p=v;のタイミングでpがnull pointerになることを推測してしまう場合があるらしく、そうするとこれは未定義動作になってしまう。(これがherumiさんにご指摘いただいた部分。)

まじか、最適化の結果未定義動作を踏むこともあるのか、つらいな…。

じゃあどうすればいいのか

これは多くの人がすでに指摘している通りで、かつ私も同意する結果なのですが、

「処理系定義の動作に依存することなくメモリの0番地にC言語から読み書きをすることは不可能である」

が答えです。

これは、そもそもC言語には「メモリの何番地」に該当する概念がなく、ポインタへの整数値の代入も処理系定義であることが原因であるため、どうしようもありません。

なんとかできないの?

いくつかの点に目をつぶれば、まあ結果的に実現することは可能です。

*(uint8_t *)(0) = 1; とその派生

これは、今まで説明してきた理由によれば未定義動作となるため、鼻から悪魔が出てきてもおかしくありません。早速Compiler Explorerでやってみましょう。

x86-64 gcc 9.2 x86-64 clang 9.0.0
*(uint8_t *)(0) = 1; with -O0 OK OK
*(uint8_t *)(0) = 1; with -O3 NG(ud2) NG(ud2)

残念ながら悪魔は出てきませんでしたが、最適化を有効にするとやはりud2ですね。しかし、最適化を無効にすれば一応期待通りのコードが得られます。

と、ここで気になるWarningがclangから出力されていることに気付きました。

<source>:3:5: warning: indirection of non-volatile null pointer will be deleted, not trap [-Wnull-dereference]

    *(uint8_t *)(0) = 1;

    ^~~~~~~~~~~~~~~

<source>:3:5: note: consider using __builtin_trap() or qualifying pointer with 'volatile'

1 warning generated.

Compiler returned: 0

ほう?volatileをつけると何か変わるんですかね。やってみましょう。

x86-64 gcc 9.2 x86-64 clang 9.0.0
*(uint8_t * volatile)(0) = 1; with -O0 OK OK
*(uint8_t * volatile)(0) = 1; with -O3 NG(ud2) NG(ud2)

あれ、volatiileをつける場所、こっちじゃないの?

x86-64 gcc 9.2 x86-64 clang 9.0.0
*(volatile uint8_t *)(0) = 1; with -O0 OK OK
*(volatile uint8_t *)(0) = 1; with -O3 NG(ud2) OK

なるほど、こうすれば、clangでは最適化を有効にしていても、volatile 修飾をすることで有効なコードを吐いてくれるようです。gccは規格通りだめみたいですが…。

uint8_t *p = 1; p--; *p = 1; とその派生

この手法は、null pointer dereference が未定義動作になる挙動を回避した(つもりだった)ものです。(もちろん、この挙動は整数からポインタへの変換という処理系定義の動作に依存しています。)

x86-64 gcc 9.2 x86-64 clang 9.0.0
uint8_t *p = 1; p--; *p = 1; with -O0 OK OK
uint8_t *p = 1; p--; *p = 1; with -O3 NG(ud2) NG(ud2)

しかし、最適化によって前半の結果pがnull pointerになることが推測されてしまっており、その結果ud2が生成されていますね。ということで、最適化を無効にするためにvolatile をつけてあげましょう。

x86-64 gcc 9.2 x86-64 clang 9.0.0
uint8_t * volatile p = 1; p--; *p = 1; with -O0 OK OK
uint8_t * volatile p = 1; p--; *p = 1; with -O3 OK OK
volatile uint8_t * p = 1; p--; *p = 1; with -O3 NG(ud2) OK

おー、確かに動きはしますね。でもポインタ演算が入ってしまいますが…。

volatile修飾をポインタ変数ではなく、その指す値につけてみると、ポインタ演算に関する最適化は両者とも走るようになり、gccでは想定通りud2になったんですが、なんとclangでは最適化された結果である0番地への代入mov byte ptr [0], 1 が生成されました。 clangはvolatileがついてたらnull pointerのdereferenceも許容してくれるってことみたいですね。

追記: -fno-delete-null-pointer-checks というフラグをコンパイル時につける

clangとgccの両方で期待通り動くようです。gccのドキュメントにおける記載はここにあります。なるほどud2になる挙動は、「絶対に引っかかることがコンパイル時にわかっている(実行時に行われる可能性がある)null pointer checkを、コンパイル時にud2に置き換える」という最適化によるものなんですね。

ところで調べていたら、このコンパイルオプションが追加されたClangへのパッチを見つけました。曰く:

Support for this option is needed for building Linux kernel. This is a very frequently requested feature by kernel developers.

More details : https://lkml.org/lkml/2018/4/4/601

なるほど、やはりLinux Kernel開発者からの熱い要望があったんですね。(lkmlのリンクに飛ぶと、Linusの熱い言葉が見れるのでおすすめです。)入ったのが比較的最近(2018年中頃)というのも面白いですね。

(Thanks @herumi, @kazuho !)

追記: __attribute__((address_space(1))) をポインタ変数につける(LLVM/clang限定)

id:uenoku さんのコメント曰く:

id:uenoku

既出でしたら申し訳ないですが、clangならllvm::NullPointerIsDefinedをtrueにすることを考えれば良いので以下のようなコードがかけます https://godbolt.org/z/x5cXf4

Compiler Explorerでの結果 のうち、f1, f2は前述した-fno-delete-null-pointer-checksによるもの、f3がこの手法です。

address_space(n) というattributeは、そのポインタがどのアドレス空間のものかを指定するもので、デフォルトはaddress_space(0)になっています。そしてこのAddress Spaceの値が、null pointerへの参照が定義された動作かを判定するLLVMの関数bool llvm::NullPointerIsDefined(const Function *F, unsigned AS) @ lib/IR/Function.cpp に渡されます。この関数の実装を見てみると:

bool Function::nullPointerIsDefined() const {
  return getFnAttribute("null-pointer-is-valid")
          .getValueAsString()
          .equals("true");
}

bool llvm::NullPointerIsDefined(const Function *F, unsigned AS) {
  if (F && F->nullPointerIsDefined())
    return true;

  if (AS != 0)
    return true;

  return false;
}

AS(address space)が0以外のとき、常にtrueを返すことがわかります。これで、null pointerへの参照が未定義動作ではないよとコンパイラに教えることができるわけです。なるほどー。

(Thanks id:uenoku !)

まとめ

  • C言語はやはり難しい
  • こんな記事を書いて時間をつぶしている場合ではなかった
  • でも仕様書を読むのも楽しいのでおすすめ

参考文献

  • (n1570.pdf)

2019年概観

2019年を時系列に振り返る。Twitter埋め込みが大量にあるので注意。

  • 1月
    • さくらインターネットで委託研究員としてNVDIMMたちと戯れていた(4月まで)
    • liumOS本格始動
    • VR環境が整備された
    • 試される大地に行った




  • 5月
    • プラサミ+自作OSもくもく会

  • 6月
    • 某社の面接を受けた
    • ハッカーズチャンプルー登壇 @ 琉球大学 docs.google.com

  • 7月

  • 8月
    • ドワンゴでバイトを開始した(継続中)
    • 某社からオファーをもらったので承諾
    • セキュキャンでRuiさんとともにCコンパイラゼミの講師を担当
    • ラボユースキャンプに卒業生として参加




まとめ

今年もなんだかんだ活発に活動していた。本当にえらい!

タスクを積みすぎるところは反省点なので、来年はある程度自制することも覚えましょう。(すでに積み上がったタスクを眺めながら。)

来年もよい年になりますように。

SECCON CTF 2019 Final competition Q4 "box" write-up

2019-12-22に開催されたSECCONの国際決勝に、hiww, h_noson, st98ともにHarekazeとして参加しました。(昨年は国内決勝に参加してました。)

順位はあまり振るわず、14チーム中11位でしたが、個人的には問題4の"box"のattackフラグを全部回収できたので大満足です。ということで、問題4の私なりの解き方についてまとめておきます。

"box"問題概要

今回は6つ大問がありましたが、そのうちの4問目でした。問題としては、stripされたx86バイナリと、それに特定の入力を与えた際の分岐トレース結果が配布されるので、同一の分岐トレースが得られるような入力をみつける、というものです。

……あれ?この話前にも聞いたことがありますね。そうです、今年の予選では、完全に同様の形式の問題(follow-me)が出されていたのでした。

hikalium.hatenablog.jp

ということで、あとはやるだけです。

Attackフラグとしては、box1から4と名付けられた4つの問題がダウンロードできるので、それを解いて入力をAPIに投げるとフラグが得られます。

Defenceフラグとしては、box1に類似した問題が1時間ごとに出され、それをその時間内に解いてAPIに投げるとチームのtokenを設置できるのですが、ちょっと厳しかったので諦めました(後述)。

では、box1から4まで順に見ていきましょう。

box1

入力形式の特定

とりあえず普通のLinuxバイナリなので実行してみます。

$ ./box 
usage: ./box formula

なるほど…式を引数で渡すんですね。

$ ./box '1+3'
error: unhandled char '+'

うーん、だめですね。じゃああれかな、予選の時と同じ入力形式なのかな?

./box '1,3,+'
error: unhandled char ','

違うみたい…。(ここから試行錯誤することしばらく。)

$ ./box ''
error: stack is empty
$ ./box '0'
error: stack is empty
$ ./box '00'
error: stack is empty
$ ./box '000'
error: stack is empty
$ ./box '0000'
0

あー…なるほど?(さらにしばらく試行錯誤して。)

$ ./box '00010002a'
3
$ ./box '00010002b'
-1
$ ./box '00010002c'
2
$ ./box '00010002d'
1
$ ./box '00010002e'
2
$ ./box '00010002f'
5
$ ./box '00010002g'
error: unhandled char 'g'

なるほど、演算子はa-fなんですね。(なぜアセンブリを読まないのか(つかれてたので))。

トレースをみてみる

$ cat box.trace        
[                                                                         
{"event": "image_load", "image_name": "***/box1", "image_id": 1, "base_addr": "0x557a93890000", "image_size": "0x135f"},
{"event": "image_load", "image_name": "/lib64/ld-linux-x86-64.so.2", "image_id": 2, "base_addr": "0x7fb95ac8c000", "image_size": "0x26c23"},
{"event": "image_load", "image_name": "[vdso]", "image_id": 3, "base_addr": "0x7ffc905a6000", "image_size": "0x100a"},
{"event": "image_load", "image_name": "/lib/x86_64-linux-gnu/libc.so.6", "image_id": 4, "base_addr": "0x7fb9464a4000", "image_size": "0x3f0adf"},
{"event": "branch", "inst_addr": "0x557a9389064e", "branch_taken": true}, 
{"event": "branch", "inst_addr": "0x557a93890ed4", "branch_taken": false},
{"event": "branch", "inst_addr": "0x557a938907f5", "branch_taken": true},
{"event": "branch", "inst_addr": "0x557a93890786", "branch_taken": true},
{"event": "branch", "inst_addr": "0x557a93890ef4", "branch_taken": false},
{"event": "branch", "inst_addr": "0x557a938906b0", "branch_taken": true}, 
{"event": "branch", "inst_addr": "0x557a93890690", "branch_taken": true}, 
{"event": "branch", "inst_addr": "0x557a93890e3f", "branch_taken": true}, 
{"event": "branch", "inst_addr": "0x557a938906c0", "branch_taken": true}, 
...
]

こんな感じでJSONが書かれています。 base_addrは最初の要素に書いてあるので、ちゃんとやるなら引き算をすれば、適当にするなら下4桁をとればファイル内のアドレスになりそうです。 というわけで、objdumpと照らし合わせればすべてわかりそう…でもせっかくトレーサーのソースも与えられているし、あとのことも考えるとトレーサーの環境を用意した方がよくない?という気持ちになったので用意することに。

トレーサーの環境構築

問題で配布されているファイルの中には、トレース出力を得るために使ったトレーサーのソースも含まれていました。なので、これを実行したいのですが、これはIntel Pinというライブラリに依存しているので、適当にPinのソースコードを落としてきてビルドします。そして、Pinを用いたサンプルコードのディレクトリに行って、サンプルのうちひとつをコピーし、それのソースとMakefileを書き換えて、トレーサーのライブラリファイルをビルドしました。

/path/to/pin/source/tools/branchtrace $ ls
branchtrace.cpp  branchtrace.out  debugtrace.cpp  makefile  makefile.rules  obj-intel64
/path/to/pin/source/tools/branchtrace $ ls obj-intel64/
branchtrace.o  branchtrace.so

このbranchtrace.soというのがトレーサーになります。

トレーサーの実行

branchtrace.soを直接実行することはできないので、pinを介して呼び出します。以下のような感じで。

q4/box1$ /path/to/pin/pin -t /path/to/pin/source/tools/branchtrace/obj-intel64/branchtrace.so -- ./box '00010002a'
3
q4/box1$ cat branchtrace.out | head -n 7
[
{"event": "image_load", "image_name": "/vagrant/seccon2019df/q4/box1/box", "image_id": 1, "base_addr": "0x55aa08e61000", "image_size": "0x135f"},
{"event": "image_load", "image_name": "/lib64/ld-linux-x86-64.so.2", "image_id": 2, "base_addr": "0x7f4f2c012000", "image_size": "0x26c23"},
{"event": "image_load", "image_name": "[vdso]", "image_id": 3, "base_addr": "0x7fff31bb3000", "image_size": "0x100a"},
{"event": "image_load", "image_name": "/lib/x86_64-linux-gnu/libc.so.6", "image_id": 4, "base_addr": "0x7f4f1782a000", "image_size": "0x3f0adf"},
{"event": "branch", "inst_addr": "0x55aa08e6164e", "branch_taken": true},
{"event": "branch", "inst_addr": "0x55aa08e61ed4", "branch_taken": false},

できましたね!

結果を整形する

pinの出力してくれるtrace結果はまあまあ綺麗なのですが、各分岐のアドレスがイメージ内の相対ではないので、配布されたものと手元では値が異なり比較が面倒です。 ということで、ささっとスクリプトを書いて整形してくれるようにしましょう。私はNodejsが好きな変人なのでnodejsで書いたprint.jsがこちら。

const fs = require('fs');

const filename = process.argv[2];
const parseTrace =
    (fileName) => {
      const trace = JSON.parse(fs.readFileSync(fileName, 'utf-8'));
      const base_addr = parseInt(trace[0].base_addr, 16);
      const branches = trace.filter(e => (e.inst_addr != undefined)).map(e => {
        if (e.event === 'call') {
          return {
            'addr': (parseInt(e.inst_addr, 16) - base_addr).toString(16),
            'target': (parseInt(e.target_addr, 16) - base_addr).toString(16)
          };
        }
        return {
          'addr': (parseInt(e.inst_addr, 16) - base_addr).toString(16),
          'taken': e.branch_taken
        };
      });
      return branches;
    }

const print =
    (branches) => {
      for (var i = 0; i < branches.length;) {
        const b = branches[i];
        var count = 0;
        while (i < branches.length && branches[i].addr == b.addr &&
               branches[i].taken == b.taken) {
          count++;
          i++;
        }
        console.log(`${JSON.stringify(b)} * ${count}`);
      }
      console.log(branches.length);
    }

const branches = parseTrace(filename);
print(branches);

最初のほうでは気づかなかったのですが、同じ分岐をぐるぐる回る際もけっこうあって、それを *Nと表示した方がわかりやすかったので、そうしていたりします。(色々適当に工夫しながらできあがった完成形。) また、あとのほうでjmp ccだけでなくcallも出てきたので、それにも一応対応してます。

実行するとこんな感じです。

q4/box1$ node print.js box.trace | head -n 5
{"addr":"64e","taken":true} * 1
{"addr":"ed4","taken":false} * 1
{"addr":"7f5","taken":true} * 1
{"addr":"786","taken":true} * 1
{"addr":"ef4","taken":false} * 1

よいよい、みやすくなった。

入力と分岐の対応関係を調べる

本当ならファジングなり、静的解析でツールを使うなり、ちゃんとやったほうが早いと思うのですが、私はobjdumpしかわからないので、バイナリのobjdumpを横においておきながら、入力と分岐を変化させて、トレーサーをぶん回しながら、どういう挙動をしているのか調べます。

メモの断片:

XXXXYYYYa
{"addr":"ddc","taken":true},
{"addr":"bac","taken":false},
{"addr":"bb6","taken":false},
{"addr":"964","taken":true},
{"addr":"964","taken":true},
{"addr":"a21","taken":true},
{"addr":"a31","taken":true},* Y+1 times
{"addr":"9c4","taken":true},
{"addr":"bf5","taken":true},

00020001b
{"addr":"ddc","taken":true},
{"addr":"bac","taken":false},
{"addr":"bb6","taken":true},
{"addr":"bfe","taken":false},
{"addr":"964","taken":true},
{"addr":"964","taken":true},
{"addr":"9c4","taken":true},
{"addr":"c3d","taken":true},

00200010c

{"addr":"ddc","taken":true},                                                                                                                                                                                                                                  
{"addr":"bac","taken":false},                                                                                                                                                                                                                                 
{"addr":"bb6","taken":true},                                                                                                                                                                                                                                  
{"addr":"bfe","taken":true},                                                                                                                                                                                                                                  
{"addr":"c46","taken":false},                                                                                                                                                                                                                                 
{"addr":"964","taken":true},                                                                                                                                                                                                                                  
{"addr":"964","taken":true},                                                                                                                                                                                                                                  
{"addr":"a5c","taken":true},                                                                                                                                                                                                                                  
{"addr":"a82","taken":true},                                                                                                                                                                                                                                  
{"addr":"a94","taken":true}, // opR + 1                                                                                                                                                                                                                                                                                                                                                                                                                                                              
{"addr":"9c4","taken":true},                                                                                                                                                                                                                                  
{"addr":"c85","taken":true}, 

なるほど、結局のところ

XXXXYYYYa -> XXXX+YYYY
XXXXYYYYb -> XXXX-YYYY
XXXXYYYYc -> XXXX*YYYY
XXXXYYYYd -> min(XXXX, YYYY)
XXXXYYYYe-> max(XXXX, YYYY)

という感じの逆ポーランド記法電卓なんですねー(X, Yは数字) あと、addとmulでは、右辺の値に対応して、途中の分岐の呼ばれる数が変わるんですねーということがわかりました。

ということで、適当に合いそうな入力を考えて、トレース……よし、合っていそう。では、投げましょう。私はこんな入力をえらびました。

001000000012ce0010a0000b

わーい!次にいきましょうー

box2

なんだ楽勝じゃん、次もどうせ入力が違うだけなのでは?と思ったのですが

$ ./box
usage: ./box input

どうも入力はformura、つまり式ではないようです。色々入れてみましょう。

$ ./box hoge
_t
$ ./box hogehoge
#^L8
$ ./box hogehogehoge
ɿAV
$ ./box hogehogehogefuga
@%Zyr
$ ./box hogehogehogefugassssssssssssssssssssssssss
-2"qC
$ ./box hogehogehogefugasssssssssssssssssssssssssssssssssssssss
N?sG>*AA^8>PwvƴP
$ ./box hogehogehogefugassssssssssssssssssssssssssssssssssssssssssss
z:R
   Rc-OgGOx

おお?なんか印字不能な文字を出してくるときもありますね。それに、入力と出力の対応も不明です。困った。 とりあえずobjdump...と。

     8c9:       c6 45 e0 27             movb   $0x27,-0x20(%rbp)
     8cd:       c6 45 e1 51             movb   $0x51,-0x1f(%rbp)
     8d1:       c6 45 e2 90             movb   $0x90,-0x1e(%rbp)
     8d5:       c6 45 e3 79             movb   $0x79,-0x1d(%rbp)
     8d9:       c6 45 e4 66             movb   $0x66,-0x1c(%rbp)
     8dd:       c6 45 e5 b7             movb   $0xb7,-0x1b(%rbp)
     8e1:       c6 45 e6 25             movb   $0x25,-0x1a(%rbp)
     8e5:       c6 45 e7 61             movb   $0x61,-0x19(%rbp)
     8e9:       c6 45 e8 45             movb   $0x45,-0x18(%rbp)
     8ed:       c6 45 e9 63             movb   $0x63,-0x17(%rbp)
     8f1:       c6 45 ea c3             movb   $0xc3,-0x16(%rbp)
     8f5:       c6 45 eb f8             movb   $0xf8,-0x15(%rbp)
     8f9:       c6 45 ec f4             movb   $0xf4,-0x14(%rbp)
     8fd:       c6 45 ed 96             movb   $0x96,-0x13(%rbp)
     901:       c6 45 ee a5             movb   $0xa5,-0x12(%rbp)
     905:       c6 45 ef 2e             movb   $0x2e,-0x11(%rbp)
     909:       48 8b 85 00 ff ff ff    mov    -0x100(%rbp),%rax
     910:       48 8b 40 08             mov    0x8(%rax),%rax
     914:       48 89 85 18 ff ff ff    mov    %rax,-0xe8(%rbp)
     91b:       48 8b 85 18 ff ff ff    mov    -0xe8(%rbp),%rax
     922:       48 89 c7                mov    %rax,%rdi
     925:       e8 86 fd ff ff          callq  6b0 <strlen@plt>

なんか16回movしてそのあとstrlenしている…16という数字があやしいな?

と思いながらトレースをしていたところ、以下の事実を発見した。

$ node trace.js ./box '0' | tail -n 1
821
$ node trace.js ./box '0123' | tail -n 1
821
$ node trace.js ./box '0123456789abcdef' | tail -n 1
821
$ node trace.js ./box '0123456789abcdefg' | tail -n 1
1535
$ node trace.js ./box '0123456789abcdefghi' | tail -n 1
1535
$ node trace.js ./box '0123456789abcdef0123456789abcdef' | tail -n 1
1535
$ node trace.js ./box '0123456789abcdef0123456789abcdef0' | tail -n 1
2249

ここでtrace.jsは、私が適当に書いたトレーサーをラップするスクリプトで、最後にトレースの総分岐数が出てくるのですが、なぜか入力が16文字増えるごとに段階的に分岐数が増える。しかも、トレース結果をみると、同じ分岐回数なら、分岐の内容は一切変わっていない。

16文字の境界を超えるごとに、分岐数は1535-821 == 2249 - 1535 == 714増えるから、つまるところ16*N+1以上16*N+16文字(N >=0)の入力を与えた時、その総分岐数は821+N*714になるというわけです。

さて、与えられたtraceの総分岐数は8675であったから、この式で逆算すると(8675-821)/714 => 11となるわけです。おお、まじか、ぴったり整数じゃん!(ここで嬉しい気分になる。)

というわけで、気軽に16*11+16 => 192文字のファイルを生成して送りつけました。わーい!

box3

box2がさくっと終わったので、どんどんやっていこうーとなった流れで到達したbox3は、めっちゃ楽しかった。だって

$ ./box 
usage: ./box filename

と出たので、適当にtouchしたファイルを食べさせたら

./box empty.txt 


[!] Not implemented: code=0


EAX = 00000000
ECX = 00000000
EDX = 00000000
EBX = 00000000
ESP = 00007c00
EBP = 00007c00
ESI = 00000000
EDI = 00000000
EIP = 00007c00

見慣れたレジスタ名が出てきたんですもの。しかも、0x7c00!!!!!(この嬉しさを理解したい方は30日でできるOS自作入門かIntel SDMでも読んでおいてください。)

これは十中八九エミュレーターだろう、と思ったので、早速NOPを食べさせると

$ echo '90' | xxd -r -p > nop.bin
$ ./box nop.bin 


[!] Not implemented: code=0


EAX = 00000000
ECX = 00000000
EDX = 00000000
EBX = 00000000
ESP = 00007c00
EBP = 00007c00
ESI = 00000000
EDI = 00000000
EIP = 00007c01

たしかにさっきより1バイト進んでから死んでますね。やったね!

どんな命令が実装されているのか特定する

そうきたら、あとはこの子の実装状況と動作のようすを解明してあげるだけです。 最初は、Intel SDM Vol.2のopcode表をみて適当にあたりをつけていたのですが、あまりにもきつかったので方針転換しました。

幸運にもNOPが実装されていることはわかったので、NOPの数を変えてトレースしてみましょう。

トレース結果は長いのですが、着目すべき点はただ一つ: call命令のトレース結果だけです。私のprint.jsでは、call命令の場合はtargetというメンバを記録するようにしているので、それでgrepをかけます。

$ echo '90' | xxd -r -p > nop1.bin
$ echo '90 90' | xxd -r -p > nop2.bin
$ node trace.js ./box nop1.bin | grep target
{"addr":"3b2d","target":"2e44"} * 1
$ node trace.js ./box nop2.bin | grep target
{"addr":"3b2d","target":"2e44"} * 1
{"addr":"3b2d","target":"2e44"} * 1

なるほど…つまるところ、+0x2e44のところがNOPの命令を処理しているようですね。

どうしてcall命令にのみ着目すればいいのかというと、たいていのCPUエミュレータは、動作を高速にするために、入力された命令のバイトを配列の添字として、関数ポインタの配列にアクセスして各処理を呼び出すからです。(作ってみるとわかるこの気持ち。)

というわけで、call命令のtargetを見れば、どの命令が実行されているのかわかりそうですね。

では、求めるべきトレース結果から、どの命令が使われているか抽出してみましょう。とりあえずcall命令だけを抜き出してみると、

$ node print.js box.trace | grep target
{"addr":"3b2d","target":"2ebd"} * 1
{"addr":"3b2d","target":"2ebd"} * 1
{"addr":"3b2d","target":"2159"} * 1
{"addr":"3b2d","target":"28fd"} * 1
{"addr":"3b2d","target":"1ead"} * 1
{"addr":"3b2d","target":"2389"} * 1
{"addr":"3b2d","target":"317d"} * 1
{"addr":"3b2d","target":"2159"} * 1
{"addr":"3b2d","target":"28fd"} * 1
{"addr":"3b2d","target":"1ead"} * 1
{"addr":"3b2d","target":"2389"} * 1
{"addr":"3b2d","target":"317d"} * 1
{"addr":"3b2d","target":"2159"} * 1
{"addr":"3b2d","target":"28fd"} * 1
{"addr":"3b2d","target":"1ead"} * 1
{"addr":"3b2d","target":"2389"} * 1
{"addr":"3b2d","target":"317d"} * 1
{"addr":"3b2d","target":"2159"} * 1
{"addr":"3b2d","target":"28fd"} * 1
{"addr":"3b2d","target":"1ead"} * 1
{"addr":"3b2d","target":"2389"} * 1
{"addr":"3b2d","target":"317d"} * 1
{"addr":"3b2d","target":"2159"} * 1
{"addr":"3b2d","target":"28fd"} * 1
{"addr":"3b2d","target":"1ead"} * 1
{"addr":"3b2d","target":"2389"} * 1
{"addr":"3b2d","target":"317d"} * 1
{"addr":"3b2d","target":"2159"} * 1
{"addr":"3b2d","target":"28fd"} * 1
{"addr":"3b2d","target":"3269"} * 1

おー、やはりindirectなcall命令は1箇所しかないんですね。で、このtargetの一意なリストは以下です。

$ node print.js box.trace | grep target | cut -d \" -f 8 | sort | uniq
1ead
2159
2389
28fd
2ebd
317d
3269

さて、ここからどうやって命令オペコードを知ればよいでしょうか。

さきほど言ったように、このエミュレータは命令オペコードをテーブルの添字にすることで関数ポインタを得て、それをcallしているはずです。 では、そのテーブルはどこにあるのか…objdumpをみるとあやしいところを見つけました。

    340b:   55                      push   %rbp
    340c:   48 89 e5                mov    %rsp,%rbp
    340f:   48 83 ec 10             sub    $0x10,%rsp
    3413:   ba 00 08 00 00          mov    $0x800,%edx
    3418:   be 00 00 00 00          mov    $0x0,%esi
    341d:   48 8d 3d 7c 2c 20 00    lea    0x202c7c(%rip),%rdi        # 2060a0 <__cxa_finalize@plt+0x2055f0>
    3424:   e8 f7 d5 ff ff          callq  a20 <memset@plt>
    3429:   48 8d 05 7d ea ff ff    lea    -0x1583(%rip),%rax        # 1ead <__cxa_finalize@plt+0x13fd>
    3430:   48 89 05 71 2c 20 00    mov    %rax,0x202c71(%rip)        # 2060a8 <__cxa_finalize@plt+0x2055f8>
    3437:   48 8d 05 0c eb ff ff    lea    -0x14f4(%rip),%rax        # 1f4a <__cxa_finalize@plt+0x149a>
    343e:   48 89 05 7b 2c 20 00    mov    %rax,0x202c7b(%rip)        # 2060c0 <__cxa_finalize@plt+0x205610>
    3445:   48 8d 05 02 ec ff ff    lea    -0x13fe(%rip),%rax        # 204e <__cxa_finalize@plt+0x159e>
    344c:   48 89 05 c5 2c 20 00    mov    %rax,0x202cc5(%rip)        # 206118 <__cxa_finalize@plt+0x205668>
    3453:   48 8d 05 62 ec ff ff    lea    -0x139e(%rip),%rax        # 20bc <__cxa_finalize@plt+0x160c>
    345a:   48 89 05 87 2d 20 00    mov    %rax,0x202d87(%rip)        # 2061e8 <__cxa_finalize@plt+0x205738>
    3461:   48 8d 05 f1 ec ff ff    lea    -0x130f(%rip),%rax        # 2159 <__cxa_finalize@plt+0x16a9>
    3468:   48 89 05 f9 2d 20 00    mov    %rax,0x202df9(%rip)        # 206268 <__cxa_finalize@plt+0x2057b8>
    346f:   48 8d 05 8b ed ff ff    lea    -0x1275(%rip),%rax        # 2201 <__cxa_finalize@plt+0x1751>
    3476:   48 89 05 fb 2d 20 00    mov    %rax,0x202dfb(%rip)        # 206278 <__cxa_finalize@plt+0x2057c8>
    347d:   48 8d 05 25 ee ff ff    lea    -0x11db(%rip),%rax        # 22a9 <__cxa_finalize@plt+0x17f9>
    3484:   48 89 05 f5 2d 20 00    mov    %rax,0x202df5(%rip)        # 206280 <__cxa_finalize@plt+0x2057d0>
    348b:   48 8d 05 89 ee ff ff    lea    -0x1177(%rip),%rax        # 231b <__cxa_finalize@plt+0x186b>
    3492:   48 89 05 ef 2d 20 00    mov    %rax,0x202def(%rip)        # 206288 <__cxa_finalize@plt+0x2057d8>
    3499:   c7 45 fc 00 00 00 00    movl   $0x0,-0x4(%rbp)

何やらばんばんleaして代入してますね。しかも、関数のアドレスっぽいです。もう少し下の方をみると

    3677:   48 8d 05 c6 f7 ff ff    lea    -0x83a(%rip),%rax        # 2e44 <__cxa_finalize@plt+0x2394>
    367e:   48 89 05 9b 2e 20 00    mov    %rax,0x202e9b(%rip)        # 206520 <__cxa_finalize@plt+0x205a70>

NOP命令だとわかっている、0x2e44の関数ポインタを代入しているところをみつけました! どうもこのテーブルの先頭は、ソースの流れ的に

    341d:   48 8d 3d 7c 2c 20 00    lea    0x202c7c(%rip),%rdi        # 2060a0 <__cxa_finalize@plt+0x2055f0>

曰く0x2060a0のようです。では、この予想が正しいか調べてみましょう。

  • NOPのオペコードは0x90
  • NOPの関数ポインタはオフセット0x206520に格納されている
  • ポインタの大きさは8bytes
  • 関数ポインタのテーブルは0x2060a0から始まっている?

関数ポインタのテーブルをop_tableとしたとき、

op_table[0x90] == <+0x2e44のアドレス>

になっていてほしいわけです。これはつまり

*(op_table + 8 * 0x90) == <+0x2e44のアドレス>

というのと等価ですから、格納されるべきアドレスは、テーブルの先頭op_tableから8 * 0x90 == 1152離れているはずです。op_tableを0x2060a0とすれば、その結果は…

0x2060a0 + 8 * 0x90 => 0x206520

ビンゴ!NOPの関数ポインタが代入されているアドレスと一致しますね!!

というわけで、これでテーブルを生成するコードで各関数がテーブルのどのオフセットに格納されているか調べれば、対応するオペコードがわかりそうです。

…とりあえず、テーブル内の各オフセットと対応するオペコードはスクリプトでさくっと生成しました。

[
  [ '2060a8', '1' ],  [ '2060c0', '4' ],
  [ '206118', 'f' ],  [ '2061e8', '29' ],
  [ '206268', '39' ], [ '206278', '3b' ],
  [ '206280', '3c' ], [ '206288', '3d' ],
  [ '2063e0', '68' ], [ '2063f0', '6a' ],
  [ '206420', '70' ], [ '206428', '71' ],
  [ '206430', '72' ], [ '206438', '73' ],
  [ '206440', '74' ], [ '206448', '75' ],
  [ '206460', '78' ], [ '206468', '79' ],
  [ '206480', '7c' ], [ '206490', '7e' ],
  [ '206498', '7f' ], [ '2064b8', '83' ],
  [ '2064e0', '88' ], [ '2064e8', '89' ],
  [ '2064f0', '8a' ], [ '2064f8', '8b' ],
  [ '206508', '8d' ], [ '206520', '90' ],
  [ '2066b8', 'c3' ], [ '2066d8', 'c7' ],
  [ '2066e8', 'c9' ], [ '206708', 'cd' ],
  [ '2067c0', 'e4' ], [ '2067e0', 'e8' ],
  [ '2067e8', 'e9' ], [ '2067f8', 'eb' ],
  [ '206800', 'ec' ], [ '206810', 'ee' ],
  [ '206840', 'f4' ], [ '206898', 'ff' ]
]

そして、あとはobjdumpの結果とIntel SDM Vol.2をじーっと見つめると…

1ead -> 2060a8 -> 0x01  -> ADD Ev,Gv
2159 -> 206268 -> 0x39  -> CMP Ev,Gv
2389                    -> INC r32
28fd -> 206498 -> 0x7f  -> JNLE / JG
2ebd ->                 -> mov r32, imm32
317d -> 2067f8 -> 0xeb  -> short Jb
3269 -> 206840 -> 0xf4  -> HLT

はい!

incとmovに関しては、オペコード内にレジスタエンコーディングされている(つまり、複数のオペコードが同じ操作を表現する)ので、バイナリ中でもループを回して代入されていました。なのでちょっと歯抜けです。(INCとかがオフセットいくつで実装されているかを調べたりして突き止めた。)

さて、あとはprint.jsを拡張して、トレース結果からオペコードを表示してみるか…となったんですが

PROLOGUE                           
mov r32, imm32                     
mov r32, imm32                     
CMP Ev,Gv                          
{"addr":"bdf","taken":false} * 1   
{"addr":"be6","taken":true} * 1    
{"addr":"a20","taken":true} * 1    
{"addr":"c7d","taken":true} * 1    
{"addr":"cbf","taken":true} * 1    
{"addr":"cd6","taken":true} * 1    
{"addr":"d0e","taken":true} * 1                                                                
{"addr":"13a1","taken":false} * 1                                                                                           
{"addr":"13bc","taken":true} * 1
{"addr":"1cb5","taken":false} * 1
{"addr":"1cca","taken":true} * 1
{"addr":"1cf1","taken":true} * 1
{"addr":"1d2d","taken":false} * 1
{"addr":"1d41","taken":true} * 1
{"addr":"1e86","taken":true} * 1 
{"addr":"1d67","taken":true} * 1
{"addr":"21f8","taken":true} * 1                       
JNLE / JG                                                                                                                                                      
ADD Ev,Gv                                                                                                                                                      
INC r32                                                         
...
INC r32
short Jb
CMP Ev,Gv
{"addr":"bdf","taken":false} * 1
{"addr":"be6","taken":true} * 1
{"addr":"a20","taken":true} * 1
{"addr":"c7d","taken":true} * 1
{"addr":"cbf","taken":true} * 1
{"addr":"cd6","taken":true} * 1
{"addr":"d0e","taken":true} * 1
{"addr":"13a1","taken":false} * 1
{"addr":"13bc","taken":true} * 1
{"addr":"1cb5","taken":true} * 1
{"addr":"1cf1","taken":true} * 1
{"addr":"1d2d","taken":true} * 1
{"addr":"1e86","taken":true} * 1
{"addr":"1d67","taken":true} * 1
{"addr":"21f8","taken":true} * 1
JNLE / JG
JNLE / JG taken
HLT->END
444

これはCMP Ev, Gvの分岐列だけベタで、あとは命令の名前で表示してみたんですが、なぜか微妙に長さが違います。考えられるのは…演算結果によって分岐が変わるということです。 CMP命令は、引き算の結果に合わせてフラグレジスタを設定しますから、いかにもありそうなかんじです。また、分岐命令についても分岐列の長さが1命令程度変動する時があり、これは分岐が行われたか否かを示しているようでした。 というわけで、うまくつじつまを合わせるとこんな感じのアセンブリ列をバイナリにして食べさせてあげたトレース結果を投げると(長い)フラグが降ってきました。うれしいね!

.intel_syntax noprefix

mov eax, 1
mov ebx, 5
cmp eax, ebx
jg out
add ecx, edx
inc eax
jmp a
a:
cmp edx, ebx
jg out  # false
add ecx, edx
inc eax
jmp b
b:
cmp edx, ebx
jg out  # false
add ecx, edx
inc eax
jmp d
d:
cmp edx, ebx
jg out  # false
add ecx, edx
inc eax
jmp e
e:
cmp eax, ebx
jg cccc  
cccc:
add ecx, edx
inc eax
jmp g
g:
cmp ebx, edx
jg out  # true
add ecx, edx
inc eax
jmp f
f:
out:
hlt

コンパイルとバイナリの抽出は以下のような感じで。(out.binがおいしいバイナリです。)

gcc -m16 -c -o test.o test.S && objcopy -O binary test.o out.bin

さあ、次もいきましょう!!

box4

さて、次は何かな、と思ったら

$ md5sum box3/box box4/box
d8614ad07b9efbb87a6049bd7b5da1c7  box3/box
d8614ad07b9efbb87a6049bd7b5da1c7  box4/box

同じバイナリじゃないですか!やったね、スクリプトが流用できるよ!

追加の命令列を特定

2c33 -> 2064e8 -> 0x89  -> MOV Ev,Gv
23e7 ->            -> DEC r32
24c3 ->                 -> POP r32
251a ->  2063e0 -> 0x68  -> PUSH lz
2645 -> 206440 -> 0x74  -> JZ/JE
2695 -> 206448 -> 0x75  -> JNZ/JNE
3144 -> 2067e8 -> 0xe9  -> JMP near Jz

かんたんだね!

print.jsを拡張

  • 分岐のtaken/not taken
  • OF(オーバーフローフラグ)の表示を追加

Parser for SECCON 2019 final q4 box4

このスクリプトを、与えられたトレース結果に適用すると、こんなかんじの出力が得られます。

$ node print.js box.trace
PROLOGUE
PUSH imm32
PUSH imm32
PUSH imm32
PUSH imm32
POP r32
POP r32
DEC r32 ZF=false OF=false
MOV r/m32,r32
ADD Ev,Gv
DEC r32 ZF=false OF=false
JNZ/JNE
JNZ/JNE taken?
ADD Ev,Gv
DEC r32 ZF=true OF=false
JNZ/JNE
CMP Ev,Gv ZF=false
JZ/JE
JMP near Jz
POP r32
DEC r32 ZF=false OF=false
MOV r/m32,r32
ADD Ev,Gv
DEC r32 ZF=true OF=false
JNZ/JNE
CMP Ev,Gv ZF=false
JZ/JE
JMP near Jz
POP r32
DEC r32 ZF=false OF=false
MOV r/m32,r32
ADD Ev,Gv
DEC r32 ZF=false OF=false
JNZ/JNE
JNZ/JNE taken?
ADD Ev,Gv
DEC r32 ZF=false OF=false
JNZ/JNE
JNZ/JNE taken?
ADD Ev,Gv
DEC r32 ZF=true OF=false
JNZ/JNE
CMP Ev,Gv ZF=true
JZ/JE
JZ/JE taken
HLT->END
613

もうほとんどアセンブリだね!

入力バイナリを錬成

メモ書き込みですがこんな感じでとけた。

.intel_syntax noprefix

//PUSH lz
//PUSH lz
//PUSH lz
//PUSH lz

.byte 0x68, 0x02, 0x00, 0x00, 0x00
.byte 0x68, 0x02, 0x00, 0x00, 0x00
.byte 0x68, 0x02, 0x00, 0x00, 0x00
.byte 0x68, 0x02, 0x00, 0x00, 0x00

//POP r32
//POP r32
//DEC r32 ZF=false : r32 != 1
//MOV Ev,Gv
//ADD Ev,Gv
//DEC r32 ZF=false : r32 != 1
//JNZ/JNE
//JNZ/JNE taken?

pop edx // edx = 1
pop esi // esi = 1
dec edx // op != 0
mov ecx,edx
add edx,eax
dec esi
jne fake
fake:

//ADD Ev,Gv
//DEC r32 ZF=true : r32 == 1
//JNZ/JNE
//CMP Ev,Gv ZF=false
//JZ/JE
//JMP near Jz

add ecx,ecx
dec esi // op should be 1
jnz c
c:
cmp eax,ecx
jz d
.byte 0xe9, 0x00, 0x00, 0x00, 0x00
d:

//POP r32
//DEC r32 ZF=false
//MOV Ev,Gv
//ADD Ev,Gv
//DEC r32 ZF=true
//JNZ/JNE

pop ebx
dec ebx
mov ecx,ebx
add edi,ecx
dec ebx
jne e
e:

//CMP Ev,Gv ZF=false
//JZ/JE
//JMP near Jz

cmp eax,ecx
jz p
.byte 0xe9, 0x00, 0x00, 0x00, 0x00
p:

//POP r32
//DEC r32 ZF=false
//MOV Ev,Gv
//ADD Ev,Gv
//DEC r32 ZF=false
//JNZ/JNE
//JNZ/JNE taken

pop ebx
dec ebx
mov ecx,ecx
add edi,ecx
dec edi
jne q
q:

//ADD Ev,Gv
//DEC r32 ZF=false
//JNZ/JNE
//JNZ/JNE taken
add edi,ecx
dec edi
jnz m
m:

//ADD Ev,Gv
//DEC r32 ZF=true
//JNZ/JNE
add ecx,ecx
dec ebx
jne n
n:

//CMP Ev,Gv ZF=true
//JZ/JE
//JZ/JE taken
cmp eax,eax
jz s
s:

//HLT->END
hlt

あれ、Defenceポイントはどうしたの?

box1のvariantってことだったので、演算子とかは一緒かなと思っていたのですが、完全に変わっていたのでつらかった。自動化するにはちゃんとファジングとかデコンパイラを活用する必要がありそうだなあという気持ちになりました。強くなりたいです。

他に何をやりましたか?

MimuraのフラッシュをダンプしてFATを読む試みをしたりした。でもうまくいかなかった。st98さんが実機を持って帰ったので朗報を期待している。

Bad mouseをst98さんが解いてくれたのだが、実機を持っていなかったようなので、去年かどこかで配られたのを家に置いてあった私が代わりに実行しました。 マウスが動いてフラグが塗られるのは楽しかった。しかし、待ち時間が長かった…(st98さん曰く、もっとwaitを短くできたらしいのでそうするといいと思います。)

以下、塗られたフラグの実際の画像です。

f:id:hikalium:20191222231359p:plain
FLAG for Bad Mouse

まとめ

問題4はめっちゃ楽しかった。作問者の友利奈緒さん、いい問題をありがとうございます!

坂井さんの問題は、ちょっとやる気が出なかったです。私のバイナリ鍛錬が足りないのも要因ですが、単純にあまり問題がおもしろくなかったのと、ディフェンスポイントの入りかたにゲーム性がないなどの問題もあったと私は思います。来年はアーキの数で殴るタイプではない、面白く解けるマルチアーキテクチャ問題を期待しています…。

とはいえ、全体的には楽しめたのでよかったです。SECCONはSECCONなので!と私は思っています。

運営のみなさま、ありがとうございました。