2007-06-02　Exploiting実習-第0回その2　Defolos

■コンパイルテスト

　Ｃ言語のコンパイルおよび、アセンブリ言語のコンパイルテストを行った。

●例題0.1

・ユークリッド互除法でやると楽：最古のアルゴリズムで、『原論』で紹介された
【手順】
１．xをyで割って、商をa1、あまりをb1とする
２．yをb1で割って、商をa2、あまりをb2とする
３．b1をb2で割って、商をa3、あまりをb3とする 

　ということを延々と繰り返していく。最終的には必ず割り切ることができる数値が見つかり、それが最大公約数

【ヒント】
まず、０以下の数値を排除します
a,bの二つの変数を用意し、aにはx/yを、ｂにはそのあまりを入れます。もしｂが０になれば終了です
割り切れていないようなら、xをy
に変更し、yを先ほど出したあまりに換えます
これをぐるぐるまわすといつか処理が終わるはずです

○ソースコード

-----euc.c
#include <stdio.h>

int euclid(int x, int y);

int main(void){
	int x, y;
	scanf("%d %d", &x, &y);
	printf("%d\n", euclid(x,y));
	return 0;
}

int euclid(int x, int y){

	int q, r;

	if(x == 0 || y == 0){
		return 1;
	}
	if(x < 0){
		x =- x;
	}
	if(y < 0){
		y =- y;
	}
	while(1){
		q = x / y;
		r = x - (q * y);
		if(r == 0){
			break;
		}
		x = y;
		y = r;
	}
	return y;
}
-----

○解説
　はじめにいずれかの値が0でないかをチェックする。次に、負の値が入力された場合には負の数から同じ数だけ引いて正の数に変更する。後は無限ループ内でqにx割るyを、rにx割るyのあまりを求める。もしもあまりが0になったら無限ループから抜け出し、そのときのyを解答として戻す。あまりが0ではないときにはxをyに変更してyを先ほど求めたあまりにする。


【別解】
　ユークリッド互除法は再帰で書くとシンプルにかける

○ソースコード

再帰を用いる場合の解答例

-----euc.c
#include <stdio.h>

int euclid(int x, int y);

int main(void){
        int x, y;
        scanf("%d %d", &x, &y);
        printf("%d\n", euclid(x,y));
        return 0;
}

int euclid(int x, int y){
        if(y == 0){
                return x;
        }
        else{
                return euclid(y, x%y);
        }
}
-----

○解説
　euclid関数中では、もしyが0であればそのときのxを正解として返す。このyはあまりの部分なので、あまりが0のときにxを返すアルゴリズムにしたがっている。あまりが0ではないときにはxのところに今のyを入れ、yのところにx割るyのあまりを入れる。
　ポイントはプロトタイプ宣言をしっかり行うという点、確実にいつか停止するようにするという2点。

○コンパイルと実行

　gccを使う。-oは実行ファイルに名前をつけるときのオプションで、省略するとa.outになる。-Wallは詳細な警告を表示する。実行時にはカレントディレクトリから指定する必要がある。

-----
defolos@glazheim:~$ gcc -o euc.exe -Wall euc.c
defolos@glazheim:~$ ./euc.exe
1234 987
1
defolos@glazheim:~$ ./euc.exe
432 4
4
defolos@glazheim:~$ ./euc.exe
57 11
1
-----

　それぞれテストデータの答えは1,4,1である。

●例題0.2

　アセンブリにもいくつか種類があるがGASを使う。←gdbのコードでも利用されている
　GAS:GNUが開発したアセンブラでgccでコンパイル可能

・エントリポイント
　どこからプログラムが始まるのかを記したもの。main:は表札のようなもの。

.global main
main:

・ディレクティブ
　アセンブラへの解釈の指定

.code32←32ビットで動作することを指定
.text←文字列であることを指定
.data←データであることを指定

・命令
　文字列表示のような高級な命令は無い。値を入れる、引き算するなどを組み合わせて必要な処理を実現する。

movl $4, %eax

　lは32ビットであることを明確にする記号。bなどもある。「〜する、〜を〜に」という文法である。

・データの宣言
　msg:はラベルで、アドレスにかけられた表札のようなもの。.asciiディレクティブは文字列を指定する。"hello"が文字列。

msg: .ascii "hello"

○ソースコード

　画面への表示にはシステムコールを使う。システムコール：ＯＳが用意してくれている機能。関数っぽいもの。出力にはwriteをつかう。

ssize_t write(int fd, const void *buf, size_t count);
戻り値　　ディスクリプタ　　文字列のアドレス　　出力したい文字数

　eaxにはシステムコール番号、ebxには第一引数、ecxに第二引数・・・と設定した後にシステムコール割り込みをＯＳに発信する。それによってＯＳがシステムコールを実行してくれる。writeはシステムコール番号は4。

-----hello.s
.code32
 
.data
msg: .ascii "Hello!"
 
.global main
main:

movl $4, %eax
movl $0, %ebx
movl $msg, %ecx
movl $6, %edx
int $0x80
ret
-----

○解説
　はじめに、コードが32ビットで動くことを指定する。次にデータの宣言であることを指定するために.dataディレクティブを指定。msgラベルをつけて"Hello!"を宣言する。
　次にエントリポイントを指定。eaxに4を、ebxに0を、ecxには第三引数の文字列へのアドレスを入れるが、ラベルはアドレスの表札なので、表札を数値として認識させることでアドレスをレジスタに入れることができる。後はedxに6を入れ、割り込みを発生させる（int $0x80）最後に、プログラムが終わりであることを告げるretを書く。

○コンパイルと実行

　コンパイルにはgccを使う。改行コードを出力していないので、プロンプトも続けて表示される。

-----
defolos@glazheim:~$ gcc hello.s
defolos@glazheim:~$ ./a.out
Hello!defolos@glazheim:~$ 
-----

■講義メモ

●sshへのログイン・操作に対するトラブル

・サーバへのアクセスができているのかをまず確認（pingなど用いる）

＞アクセス自体できない
　sshが立ってるか確認
　Diceが起動しているか、イベントが適切か確認
　ifconfigで表示されるIPアドとポートマッピングが適切か確認
　MyDNSの期限を確認

＞ログインができない
　ユーザを作成しているか確認
　パスワードを確認
　ssh設定ファイルで接続を許可しているか確認

＞ファイルの保存などができない
　ディレクトリのパーミッションを確認　(ls -al)
　ユーザのホームディレクトリがあるか確認
　ディレクトリの所有者を確認
　所有権、パーミッションがおかしければ修正
　chown chmodなど

●例題について

　簡単すぎたかも？←5分で解答できた例より
　例題0.2はソースコードを提示して、それについて解説したほうが良かったかも