はじめに
最近、https://twitter.com/reiya_2200/status/1130761526959267841 のtweetで制約付きのCプログラミング課題がありました。
パッと思いつくのはmain再帰ですが、それはあまり面白みが無いということで、機械語埋め込みを組んでみたので、ネタにしてみました。
なお、前提として x86_64 Linux + gcc、再現環境はUbuntu18 ( WSL/Windows10 ) です。
同じLinuxでも、環境が違えばまた振る舞いも大きく変わり得ます。悪しからずご注意ください。
素直な埋め込み
まずはコード
ということで tweetしたのは、機械語を素直に埋め込んだ次のコードでした。
#include <stdio.h>
int main(int argc,char *argv[]) {
static char __attribute__((section(".text"))) s[]="1\xc0H\x83\xc7\bH\x8b\27H\x85\xd2t\t\xf\xbe\22\215D\20\xd0\xeb\xeb\xc3";
return !printf("%d\n",((int(*)(void*))s)(argv));
}
実行すると次のように、ちゃんと引数に指定した1桁の数字の合計を出力しています。
※なんかWarningが出てるけど気にしない。
$ gcc emb1.c
/tmp/ccfyvQPW.s: Assembler messages:
/tmp/ccfyvQPW.s:3: Warning: ignoring changed section attributes for .text
$ ./a.out 4 6 4 9
23
慣れてる人には不要な気もしますが、一応解説してみます。
関数の実装と機械語化
方針としては、合計を計算する部分を関数として実装し、それを機械語化するというものです。
簡単に実装するなら、次のようなコードが考えられます。
int sum(void *pv) {
char **pc=pv;
int s=0;
while ( *++pc ) {
s+=**pc-'0';
}
return s;
}
なお、引数pvはargvが渡ってくることを想定しています。argvの示すchar*配列は最後NULLポインタで終端されてますから、実はargcなしで処理することができます。
※argvの示す配列の先頭要素は捨てることにも要注意
これをコンパイルし、機械語を確認すると次のようになります。
$ gcc -c -Os -fno-asynchronous-unwind-tables -fno-stack-protector sum.c && objdump -SCr sum.o
sum.o: file format elf64-x86-64
Disassembly of section .text:
0000000000000000 <sum>:
0: 31 c0 xor %eax,%eax
2: 48 83 c7 08 add $0x8,%rdi
6: 48 8b 17 mov (%rdi),%rdx
9: 48 85 d2 test %rdx,%rdx
c: 74 09 je 17 <sum+0x17>
e: 0f be 12 movsbl (%rdx),%edx
11: 8d 44 10 d0 lea -0x30(%rax,%rdx,1),%eax
15: eb eb jmp 2 <sum+0x2>
17: c3 retq
これにより、関数部分の機械語は、16進で 31,c0,48,83,… というコード列になるということです。これを、ASCII文字範囲なら印字可能文字で表現するとう短く表すと、"1\xc0H\x83\xc7\bH\x8b\27H\x85\xd2t\t\xf\xbe\22\215D\20\xd0\xeb\xeb\xc3"になります。
なお、コードを短くするために gcc の -Os (サイズ最適化) や、その他余分?な処理がコードに埋め込まれるのを抑止するオプションを指定しています。できればASCII文字として短くするオプションが欲しかったところですが、それはないのでしようがありません。
機械語の埋め込み
ということで、関数部分の機械語が分かりました。
これをコード中に、普通の文字列として埋め込んであげれば良いです。
あとは、文字列のアドレスを関数のアドレスとみなして関数呼び出しに使うだけです。printfの中で((int(*)(void*))s)(argv)としているのがそれで、int(*)(void*)というのが今回の関数のアドレスの型 ( void*を引数とし、intを返す関数へのポインタ ) であり、それにキャストを行っています。
#include <stdio.h>
int main(int argc,char *argv[]) {
static char __attribute__((section(".text"))) s[]="1\xc0H\x83\xc7\bH\x8b\27H\x85\xd2t\t\xf\xbe\22\215D\20\xd0\xeb\xeb\xc3";
return !printf("%d\n",((int(*)(void*))s)(argv));
}
しかし、注意が2点あります。それは文字列sの配置についてです。
- スタック領域に配置されるのを抑止するため
staticを指定すること - ELFのセクションの中で実行可能コードの領域(
.textセクション)に配置されるよう、attributeを指定すること
今時は、想定しないメモリ領域がコードとして実行されないような仕掛けがあります。上記の指定がないと、いざ該当の機械語コードを実行しようとしても、SEGVを引き起こすことになります。
今回のケースのように、コンパイラが実行可能コードと正しく判断できない場合に備えて必要な知識と言えるでしょう。
main関数内に直接埋め込み
実装概要
しかし、先ほどのコードにはやや不満があります。それはattributeによってELFのセクション構造が見えてしまうからです。
もっとスマートに機械語を埋め込む方法はないのでしょうか。…ということで、次のコードを書きました。
#include <stdio.h>
int main(int argc,char *argv[]) {
asm volatile(".string \"H\\x83\\xc6\\bH\\x8b\\x6H\\x85\\xc0t\\xf\\xf\\xbe\\0\\x8d|\\x7\\xcf\\x89|$\\f\\xeb\\xe7\\xb0\"");
return !printf("%d\n",argc-1);
}
ちゃんとこれでも動作することが分かります。
$ gcc emb2.c
$ ./a.out 4 6 4 9
23
タネと仕掛け
もちろんタネは簡単です。C言語コード中にアセンブリコードを埋め込むasm volatile命令で、.string疑似命令を指定すると、その箇所に文字列に相当する機械語が埋め込まれるのです。
※素直にアセンブリ命令を埋め込めばよいのでは、というのは言わない約束です。
コンパイル後できたa.outを逆アセンブルして確認してみます。
$ objdump -SCr a.out | sed -ne '/<main>:$/,+20p'
000000000000064a <main>:
64a: 55 push %rbp
64b: 48 89 e5 mov %rsp,%rbp
64e: 48 83 ec 10 sub $0x10,%rsp
652: 89 7d fc mov %edi,-0x4(%rbp)
655: 48 89 75 f0 mov %rsi,-0x10(%rbp)
659: 48 83 c6 08 add $0x8,%rsi
65d: 48 8b 06 mov (%rsi),%rax
660: 48 85 c0 test %rax,%rax
663: 74 0f je 674 <main+0x2a>
665: 0f be 00 movsbl (%rax),%eax
668: 8d 7c 07 cf lea -0x31(%rdi,%rax,1),%edi
66c: 89 7c 24 0c mov %edi,0xc(%rsp)
670: eb e7 jmp 659 <main+0xf>
672: b0 00 mov $0x0,%al
674: 8b 45 fc mov -0x4(%rbp),%eax
677: 83 e8 01 sub $0x1,%eax
67a: 89 c6 mov %eax,%esi
67c: 48 8d 3d a1 00 00 00 lea 0xa1(%rip),%rdi # 724 <_IO_stdin_used+0x4>
683: b8 00 00 00 00 mov $0x0,%eax
688: e8 93 fe ff ff callq 520 <printf@plt>
この中でアドレス659の48,83,c6,08から、アドレス672のb0,00までが埋め込まれた部分です。
なお、アドレス672の命令は実際に処理されるものではありませんが、埋め込む文字列にはNUL文字(00)が追加されるのを捌けるように、00 で終わる命令として仕込んでいます。
※.string疑似命令では、b0 までの部分を文字列として指定します。
元になったコード
さて、この埋め込まれたコードについてです。
これは、シンプルに次のような処理を想定しています。
つまり、argcを合計としてそのまま計算結果を保存してしまおうということです。
※ただし、ループはargc-1回分しか実行されないため、最後のprintfで更に1引いて対処するようにしています。
#include <stdio.h>
int main(int argc,char *argv[]) {
while ( *++argv ) { argc+=**argv-'0'-1; }
return !printf("%d\n",argc-1);
}
さて、x86_64 Linuxの関数呼び出し規約(calling convention)によると、第一引数のargcはrdiレジスタ(32bit部分はedi)、第二引数のargvはrsiレジスタに保存されています。なので、それらを直接ループ処理してしまえばO.K.です。
659: add $0x8,%rsi # argvを1要素分進める
65d: mov (%rsi),%rax # argvの要素をraxに読み込み
660: test %rax,%rax # NULLポインタ判定
663: je 674 # NULLポインタ検出時、埋め込み部分の直後へジャンプ
665: movsbl (%rax),%eax # 文字をeaxに読み込み
668: lea -0x31(%rdi,%rax,1),%edi # argc(edi)に加算
66c: mov %edi,0xc(%rsp) # ediをスタックの領域に保存
670: jmp 659 # 埋め込み部分の先頭へジャンプ
672: mov $0x0,%al # ダミー命令
ただし、最適化を行わない場合、printf時に使用するargcは、レジスタ直ではなく、一旦スタックに保存した値を使っているようでした。なので、アドレス66cの命令により、esiレジスタを変更した結果をスタックにも反映するようにしました。
なお、最適化を行うと逆にargcを退避するスタック領域は用意されないため、アドレス66cの命令でスタックを壊してしまうことになります。なので、出力は意図通りなのですが、mainを抜けるところでSEGVを引き起こしてしまうことに注意が必要です。
$ gcc -O3 emb2.c
$ ./a.out 4 6 4 9
23
Segmentation fault (core dumped)
終わりに
いかがでしたでしょうか。堕落したCプログラマのレベル -10のレベル-9相当の気分が味わえるかな、と思いコードを組み紹介しました。
最後に一応、出題者の想定解と思われるmain再帰も ( 一応組めるんだからね! ということで ) 置いておきます。
#include <stdio.h>
int main(int argc,char *argv[]) {
return argc>0 ? !printf("%d\n",main(0,argv+1)) : *argv ? **argv-'0'+main(0,argv+1) : 0;
}