C言語でhello worldを書く

これは Yahoo! JAPAN 2018年度新卒有志でつくる[Yahoo! JAPAN 18 新卒 Advent Calendar 2018](https://adventar.org/calendars/3388) の10日目の記事です。

Yahoo! JAPAN 2018年新卒の瀧ヶ平です。
この記事ではC言語でhello worldを書きます。

この記事の内容は CentOS7上及びgcc version4.8.5で検証しています。

## hello worldの流れ

一般にC言語でhello worldを書く場合以下のようなコードを書きます。

```c
#include <stdio.h>

int main(void) {
  printf("hello world");
  return 0;
}
```

このコードはx86_64 GNU/Linux環境においてgcc-4.8.5で `gcc -O2 -S -o hello.S hello.c` コマンドによって以下のようにコンパイルされます。


```
	.file	""
	.section	.rodata.str1.1,"aMS",@progbits,1
.LC0:
	.string	"hello world"
	.section	.text.startup,"ax",@progbits
	.p2align 4,,15
	.globl	main
	.type	main, @function
main:
.LFB11:
	.cfi_startproc
	subq	$8, %rsp
	.cfi_def_cfa_offset 16
	movl	$.LC0, %edi
	xorl	%eax, %eax
	call	printf
	xorl	%eax, %eax
	addq	$8, %rsp
	.cfi_def_cfa_offset 8
	ret
	.cfi_endproc
.LFE11:
	.size	main, .-main
	.ident	"GCC: (GNU) 4.8.5 20150623 (Red Hat 4.8.5-28)"
	.section	.note.GNU-stack,"",@progbits
```

主に重要なのは以下の部分です。

```
	movl	$.LC0, %edi
	xorl	%eax, %eax
	call	printf
```

`$.LC0` というアドレスを `edi` レジスタへと追加し、 `printf` 関数をcallしています。

これはx86_64 System-V ABIによって関数の第一引数は `rdi` レジスタに格納することが決まっているからですね。 (`edi` レジスタは `rdi` レジスタの下位32ビット) 

## **強い**hello worldへ

せっかくアドベントカレンダーを書くのにこれで終わってしまうのはなんだか忍びないため、もっと**強い**hello worldを目指していきたいと思います。
「強いhello world」とはどんなものでしょうか？
私は文字列を用いて `hello world` を明示せずにできたら他とは違う、強いものになるのでないかと考えました。
そして私は、以前社内向けの記事で以下のようなhello worldを書きました。

```c
#include <unistd.h>
#include <stdlib.h>

void (*a)(void);
char h = 0x00, e = 0x00, l = 0x00, o = 0x00, w = 0x00, r = 0x00, d = 0x00, sp = 0x00;

void search() {
  while(1) {
    char *b = (char *)a;
    switch(*b) {
      case 0x68:
        h = *b;
        break;
      case 0x65:
        e = *b;
        break;
      case 0x6c:
        l = *b;
        break;
      case 0x6f:
        o = *b;
        break;
      case 0x77:
        w = *b;
        break;
      case 0x72:
        r = *b;
        break;
      case 0x64:
        d = *b;
        break;
      case 0x20:
        sp = *b;
        break;
      default:
        break;
    }
    if(h && e && l && o && w && r && d && sp) break;
    a++;
  };
}


int main() {
  a = search;
  a();
  write(1, &h, 1);
  write(1, &e, 1);
  write(1, &l, 1);
  write(1, &l, 1);
  write(1, &o, 1);
  write(1, &sp, 1);
  write(1, &w, 1);
  write(1, &o, 1);
  write(1, &r, 1);
  write(1, &l, 1);
  write(1, &d, 1);
}
```

これは機械語となった `search` 関数のポインタを起点に必要となる文字を探索し、見つけた文字でhello worldを出力するプログラムです。

後にこのコードは私の上司により以下のようなコードに改善されました。

```c
#include <unistd.h>

char *a = "";
char h = 0x00, e = 0x00, l = 0x00, o = 0x00, w = 0x00, r = 0x00, d = 0x00, sp = 0x00;

int main() {
  while(1) {
    switch(*a) {
      case 0x68:
        h = *a;
        break;
      case 0x65:
        e = *a;
        break;
      case 0x6c:
        l = *a;
        break;
      case 0x6f:
        o = *a;
        break;
      case 0x77:
        w = *a;
        break;
      case 0x72:
        r = *a;
        break;
      case 0x64:
        d = *a;
        break;
      case 0x20:
        sp = *a;
        break;
      default:
        break;
    }
    if(h && e && l && o && w && r && d && sp) break;
    a--;
  };
  write(1, &h, 1);
  write(1, &e, 1);
  write(1, &l, 1);
  write(1, &l, 1);
  write(1, &o, 1);
  write(1, &sp, 1);
  write(1, &w, 1);
  write(1, &o, 1);
  write(1, &r, 1);
  write(1, &l, 1);
  write(1, &d, 1);
}
```

探索の方向をポインタ `a` からマイナス方向に探索することで確実に必要な文字を見つけることに成功しています。

特にリンカスクリプトや `pragma` などの属性が指定されない場合、初期化されたポインタ変数の配置される位置は実際のプログラムコードよりも後に配置されます。

```c
char *a = "";
int main(void) {
  return *a;
}
```

このようなコードを `test.c` として保存し、 `gcc -o test test.c && objdump -D test` を実行し確認すると、
実際に、 `main` 関数は `.text` セクション、 `a` 変数は `.data` セクションに配置されており、それぞれのアドレスは

```
00000000004003e0 <main>:
```

```
Disassembly of section .data:

0000000000601020 <__data_start>:
        ...

0000000000601028 <a>:
  601028:	70 05                	jo     60102f <a+0x7>
  60102a:	40 00 00             	add    %al,(%rax)
```

(私の環境での一例ですが)実際にメモリに展開されるアドレスはポインタ `a` の指すアドレス `0x400570` の方が `main` 関数より後になっていることが分かります。この値は `readelf` で確かめると 

```
There are 31 section headers, starting at offset 0x1920:

Section Headers:
  [Nr] Name              Type             Address           Offset
       Size              EntSize          Flags  Link  Info  Align
(中略)
  [13] .plt.got          PROGBITS         00000000004003d0  000003d0
       0000000000000008  0000000000000000  AX       0     0     8
  [14] .text             PROGBITS         00000000004003e0  000003e0
       0000000000000172  0000000000000000  AX       0     0     16
  [15] .fini             PROGBITS         0000000000400554  00000554
       0000000000000009  0000000000000000  AX       0     0     4
  [16] .rodata           PROGBITS         0000000000400560  00000560
       0000000000000011  0000000000000000   A       0     0     8
  [17] .eh_frame_hdr     PROGBITS         0000000000400574  00000574
       0000000000000034  0000000000000000   A       0     0     4
```

となっており `.rodata` 内を指しています。 
そして、`.text` セクションにある比較命令の引数で実際に必要な文字のASCIIコードが使われているため確実に必要な文字がそろうというわけです。
またセクション情報を見ると `.rodata` から `.text` のセクションは割り当てが行なわれています。
そのため、SEGVなど起こることなくプログラムが動作するというわけです。

## もっと**強く**

しかしこの hello world 少し弱そうに見えませんか？
なぜなら、実際に `hello world` それぞれの文字が実際のコードに含まれてしまっているからです。

もっと趣向を凝らせば、例えばある命令の16進表現に対応する数値からの各文字の差分を加減算することで
完全に `hello world` の文字を追いだしてhello worldができるはずです。

というわけで、[x86_64の命令リスト](http://ref.x86asm.net/coder64.html)を見てみましょう。

このなかで確実に含まれている命令がどれか考えてみます。

`return 0;` をmain関数の最後などで利用する場合 `xor %eax, %eax` が入ることは自明です。

- ABIによって関数の返り値は `%eax` に代入すること
- [Intel® 64 and IA-32 Architectures Optimization Reference Manual](https://www.intel.com/content/dam/www/public/us/en/documents/manuals/64-ia-32-architectures-optimization-manual.pdf)によって
  0を任意のレジスタに代入する際はレジスタの排他的論理和をとること

が決まっているからです。
よって、 `0x31` および `0xc0` が候補に入ります。

また、関数の実行が終了し呼び出し元に戻る際には `ret` 命令が呼ばれることがわかっています。
そのため、 `0xc3` についても確実に存在すると見てよいでしょう。

他にももっといろいろな候補やテクニックがありますが、ひとまずは `0xc3` を基準にしていきましょう。

### 世界に挨拶していく

まず基準となる0xc3を見つけます。

```c
char *a = "";
int main(void) {
  while(1) {
    if(*a == (char) 0xc3) break;
    a--;
  }
  
  char b = *a;
  // 見つけた後の処理
  return 0;
}
```

見つけた後はまず `h` を出力する必要があるので、必要なヘッダファイルをincludeします。
その後、 `0xc3` と `h` のASCIIコードとの差を計算し、そのまま出力用変数へ代入します。

```c
#include <unistd.h>

char *a = "";

int main(void) {
  while(1) {
    if(*a == (char) 0xc3) break;
    a--;
  }

  char b = *a;
  b = b + (char)-0x5b;
  write(1, &b, 1);
  return 0;
}
```

この調子で他の文字も出力していくと次のようなコードになります。

```c
#include <unistd.h>

char *a = "";
char subs[] = {(char)-0x5b, (char)-0x3, (char)0x7, (char)0x0, (char)0x3, (char)-0x4f, (char)0x57, (char)-0x8, (char)0x3, (char)-0x6, (char)-0x8};

int main(void) {
  while(1) {
    if(*a == (char) 0xc3) break;
    a--;
  }

  char b = *a;
  for(int i=0; i < 11; i++) {
    b = b + subs[i];
    write(1, &b, 1);
  }
  return 0;
}
```

面倒なので差分を計算しfor文に任せましたが、以上のようなかたちになりました。

## さらに強い hello worldへ

実行時に文字列を生成するアイデアは良いのですが、なんだかまだ物足りない気がしますね。
そこで今度は実行時のバイナリを書き換えることで `hello world` を生成してみることにします。

### 関数トップから11バイト出力する

順を追ってやっていきましょう。
実行時のバイナリを書き換える際、再度実行するであろう領域を書き換えた場合今後の処理に不具合が起こる可能性があります。
そこで

1. 出力用の関数を用意し
2. 関数トップからすでに実行済みの11バイトの値を書き換えることで `hello world` を生成
3. 関数トップのアドレスとオフセット11を引数に `write` システムコールを実行

という方法でhello worldを出力することにします。

x86_64 Linuxでは関数の最初は必ず

```
pushq %rbp
movq %rsp, %rbp
```

となっていて ([参考: x86呼び出し規約](https://en.wikipedia.org/wiki/X86_calling_conventions)) 
先ほどのx86_64の命令リストのページを見ると、 機械語は

`pushq` 命令は `0x50 + r` (rはレジスタ番号)となっているため
  - `0x50 + 0x5 = 0x55` 
  
そして、 次は64ビットレジスタ同士の `movq` なので

- REX prefix `0x48`
  - 上位4ビットは固定で0b0100
  - 下位4ビットは上位から
    - オペランドが64ビットであれば1
    - modR/Mの `reg` ビットの拡張
    - SIBの `index` フィールドの拡張
    - ModRM の `r/m`、SIB の `base`、またはオペコードの `reg` の各フィールドの拡張
- `movq` に対応する `0x89`
- `%rsp` から `%rbp` へなので `0xe5`
  - modR/Mは ([参考: Jun's Homepage Assembly Proggraming 命令の内部フォーマットとアドレッシングモード](https://www.mztn.org/lxasm64/amd05.html)) 
    - 実行アドレスがレジスタを指しているため `mod` が `0b11`
    - `reg` が `%rsp` からなので `0b100`
    - `r/m` が `%rbp` なので `0b101`
  - そのため `0b11100101 = 0xe5`
  
よって以下のようになります。
  
```
55 (pushq %rbp)
48 89 e5 (movq %rsp, %rbp)
```

これを利用すると、関数最初のアドレスから11バイト (hello worldの文字数分) を出力するにはこの次の命令に

```
leaq -x(%rip), %rsi
```

として、 `write` システムコール第二の引数にアドレスを入れてあげればよさそうです。 (xはプログラムカウンタripから関数トップのアドレスとの差分)
システムコールの引数とレジスタの対応は `man syscall` を参考にしてください。

そして、 `leaq x(%rip), %rsi` という命令は機械語になると以下のようになります。

```
48 8d 35 00 00 00 00
```

最後4バイトの部分が指定したレジスタ (今回は%rip) からのオフセットになります。
よって、この命令が実行される際の `%rip` の値から11バイトほど前を `%rsi` にいれてあげれば、関数トップのポインタを第2引数にいれられそうです。
つまり、 `leaq -11(%rip), %rsi` が必要となり、結果として欲しい機械語は `48 8d 35 f5 ff ff ff` のようになります。 (`f5 ff ff ff` は-11のリトルエンディアン表現)

こちらも

- REX prefix `0x48`
- `leaq` に対応する `0x8d`
- `%rsi` に対し `%rip` から一定位置のアドレスを入れるため `35`
  - modR/Mを考えると rip相対アドレッシングなので (参考 [Intel® 64 and IA-32 Architectures Software Developer’s Manual](https://software.intel.com/en-us/download/intel-64-and-ia-32-architectures-sdm-combined-volumes-1-2a-2b-2c-2d-3a-3b-3c-3d-and-4) Vol. 2A 2-12)
    - `mod` が `0b00`
    - `reg` が `%rsi` なので `0b110`
    - `r/m`が `0b101`
  - よって `0b00110101 = 0x35`
- オフセットが `-11` なので `f5 ff ff ff`

となることから確認できます。
 
そして、 `write` システムコールの番号、出力先ファイル記述子 (第一引数)、出力バイト数(第三引数) をそれぞれ指定し、syscall命令を呼びます。
アセンブリで表現すると以下のような形ですね。

```
movq $1, %rax
movq $1, %rdi
movq $11, %rdx
syscall
```

そして、これらの命令は以下の機械語に対応します。 (各行が上の各行の命令と対応します)

```
48 c7 c0 01 00 00 00
48 c7 c7 01 00 00 00
48 c7 c2 0b 00 00 00
0f 05
```

これらの最初3行も、 REX prefix `0x48` と即値からレジスタへの `movq` に対応する `c7` および 最後の4バイトは即値に対応し、
対象となるレジスタそれぞれに対し modR/Mを考えると

- `%rax` は `0b11000000 = 0xc0`
  - `mod` はレジスタなので `0b11`
  - `reg` は `reg` の値が要らず、オペコード拡張の値が0なので `0b000`
  - `r/m` が `%rax` より `0b000`
- `%rdi` は `011000111 = 0xc7`
  - `mod` と `reg` は同様、 `r/m` は `0b111`
- `%rdx` は `0b11000010 = 0xc2`
  - `mod` と `reg` は同様、 `r/m` は `0b010`

そして `syscall` は2バイト命令で `0x0f 0x05` に対応します。

そして、関数の終わりでは `pushq` した `%rbp` レジスタの値を `%rbp` に戻し呼び出し元関数に戻る必要があるため

```
popq %rbp
retq
```

を実行する必要があります。そしてこれらは

```
5d
c3
```

という機械語に対応します。

それぞれ1バイト命令で `poq %rbp` は `0x58 + r`、 `retq` は `0xc3` になっています。 

ここまでの命令を並べてみると

```
pushq %rbp
movq %rsp, %rbp
leaq -11(%rip), %rsi
movq $1, %rax
movq $1, %rdi
movq $11, %rdx
syscall
popq %rbp
retq
```

となり、機械語は

```
55
48 89 e5
48 8d 35 f5 ff ff ff
48 c7 c0 01 00 00 00
48 c7 c7 01 00 00 00
48 c7 c2 0b 00 00 00
0f 05
5d
c3
```

のような形になります。
これをC言語の文字列リテラルにすると

```c
char *code = "\x55\x48\x89\xe5\x48\x8d\x35\xf5\xff\xff\xff\x48\xc7\xc0\x01\x00\x00\x00\x48\xc7\xc7\x01\x00\x00\x00\x48\xc7\xc2\x0b\x00\x00\x00\x0f\x05\x5d\xc3";
```

となります。
そしてCでは文字列であろうと関数ポインタにキャストしてしまえば実行できてしまうため (仕様上では未定義ですが)

```c

int main(void) {
  char *code = "\x55\x48\x89\xe5\x48\x8d\x35\xf5\xff\xff\xff\x48\xc7\xc0\x01\x00\x00\x00\x48\xc7\xc7\x01\x00\x00\x00\x48\xc7\xc2\x0b\x00\x00\x00\x0f\x05\x5d\xc3";
  void (*f)(void) = code;
  f();
  return 0;
}
```

のようなコードをコンパイル、実行し `xxd` にパイプすると

```
5548 89e5 488d 35f5 ffff ff
```

が得られ、実際に書いた機械語と一致していることが分かります。

つまり、 `leaq -11(%rip), %rsi` の後にこれらの11バイトを調整する命令を記述すれば、`hello world` の文字を生成できそうです。

### 関数トップから11バイトを調整する

というわけで、以下のようなアセンブリを適切な位置に追加すれば解決しますね。

```
addl	$19, (%rsi)
addl	$29, 1(%rsi)
addl	$-29, 2(%rsi)
addl	$-121, 3(%rsi)
addl	$39, 4(%rsi)
addl	$-109, 5(%rsi)
addl	$66, 6(%rsi)
addl	$122, 7(%rsi)
addl	$114, 8(%rsi)
addl	$108, 9(%rsi)
addl	$100, 10(%rsi)
```

そしてこれらの命令は以下の機械語になります。

```
83 06 13
83 46 01 1d
83 46 02 e3
83 46 03 87
83 46 04 27
83 46 05 93
83 46 06 42
83 46 07 7a
83 46 08 72
83 46 09 6c
83 46 0a 64
```

`addl $19, (%rsi)` も `addl` が `0x83` に対応し、modR/Mは

- `mod` は `r/m` がレジスタの差すアドレスなので `0b00`
- `reg` は使わず、オペコード拡張は `/0` なので `0b000`
-  `r/m` は `%rsi` なので `0b110`

から `0x06` でその後は即値が入り、 `0x13` となります。

さらに `addl $29, 1(%rsi)` のような1バイトオフセット付きの場合は `addl` の `0x83` は共通で

- `mod` は `r/m` がレジスタ + 8ビットオフセットなので `0b01`
- `reg` は同様で `0b000`
- `r/m` も同様に `0b110`

から `0x46` となり、その後1バイトが `%rsi` からのオフセット、さらにその後1バイトが即値になります。

## hello worldの機械語を作成する

ここまでの命令を適切に並べると

```
pushq %rbp
movq %rsp, %rbp
leaq -11(%rip), %rsi
addl	$19, (%rsi)
addl	$29, 1(%rsi)
addl	$-29, 2(%rsi)
addl	$-121, 3(%rsi)
addl	$39, 4(%rsi)
addl	$-109, 5(%rsi)
addl	$66, 6(%rsi)
addl	$122, 7(%rsi)
addl	$114, 8(%rsi)
addl	$108, 9(%rsi)
addl	$100, 10(%rsi)
movq $1, %rax
movq $1, %rdi
movq $11, %rdx
syscall
popq %rbp
retq
```

機械語としては

```
55
48 89 e5
48 8d 35 f5 ff ff ff
83 06 13
83 46 01 1d
83 46 02 e3
83 46 03 87
83 46 04 27
83 46 05 93
83 46 06 42
83 46 07 7a
83 46 08 72
83 46 09 6c
83 46 0a 64
48 c7 c0 01 00 00 00
48 c7 c7 01 00 00 00
48 c7 c2 0b 00 00 00
0f 05
5d
c3
```

これを文字列リテラルにすると

```c
char *code = "\x55\x48\x89\xe5\x48\x8d\x35\xf5\xff\xff\xff\x83\x06\x13\x83\x46\x01\x1d\x83\x46\x02\xe3\x83\x46\x03\x87\x83\x46\x04\x27\x83\x46\x05\x93\x83\x46\x06\x42\x83\x46\x07\x7a\x83\x46\x08\x72\x83\x46\x09\x6c\x83\x46\x0a\x64\x48\xc7\xc0\x01\x00\x00\x00\x48\xc7\xc7\x01\x00\x00\x00\x48\xc7\xc2\x0b\x00\x00\x00\x0f\x05\x5d\xc3";
```

となります。

しかし、このまま実行しても、変数が格納されている領域は書き換え不可能になっているためすこし工夫します。

```c
#include <sys/mman.h>
#include <string.h>

const unsigned int CODE_LEN = 79;

int main()
{
  void *output = mmap(NULL, CODE_LEN, (PROT_READ | PROT_WRITE | PROT_EXEC), (MAP_PRIVATE | MAP_ANONYMOUS), -1, 0);
  char *code = "\x55\x48\x89\xe5\x48\x8d\x35\xf5\xff\xff\xff\x83\x06\x13\x83\x46\x01\x1d\x83\x46\x02\xe3\x83\x46\x03\x87\x83\x46\x04\x27\x83\x46\x05\x93\x83\x46\x06\x42\x83\x46\x07\x7a\x83\x46\x08\x72\x83\x46\x09\x6c\x83\x46\x0a\x64\x48\xc7\xc0\x01\x00\x00\x00\x48\xc7\xc7\x01\x00\x00\x00\x48\xc7\xc2\x0b\x00\x00\x00\x0f\x05\x5d\xc3";
  memcpy(output, code, CODE_LEN);
  void (*o)(void) = output;
  o();
  return 0;
}
```

`mmap` で読み書き実行が可能な領域を確保し、そこに `code` を書き込んでから実行します。
これにより実行時に命令部を書き換えてもSegmentation faultせずに実行できます。

[wandboxでの実行例がこちら](https://wandbox.org/permlink/4ZTCx7JU2dVKVhT4)になります。
しっかりとhello worldできていますね。

## 最後に

一般に多くの人は機械語を手書きするのに向いていないので、なかなか機械語を理解するという転機が人に訪れることはあまりないですが、この記事がきっかけになればうれしいです。

みなさんも自分だけのhello worldを書いて友達に自慢しましょう。