BrainfuckインタプリタをAssemblyで書き直してみた。
先日の池袋バイナリ勉強会に行ったときの記事を覚えてますでしょうか?
ここにあるようにC++でBrainfuckのインタプリタを書いたのですが、このコードをコンパイルした実行ファイルの大きさがゆうに100kBいってしまっていて、もっと軽くならないものかと思ってたんですよね・・・
そこで、今回はBrainfuckのインタプリタをAssembly言語で最初から書き直してみました。
それではどうぞ!
[c]
;Brainfuck.asm bits 16 org 100h
;メモリ初期化 mov cx,799h set: mov bx,cx mov byte [mem+bx],0 loop set
;コード変換 mov ah,09h mov dx,msg0 int 21h mov ah,01h int 21h sub al,30h mov byte [cvt],al
;Inputメッセージ mov ah,09h mov dx,crlf int 21h mov dx,msg1 int 21h mov dx,crlf int 21h
;Brainfuckコード入力 mov ah,01h input: int 21h cmp al,0dh jz domsg inc word [len] mov bx,[len] mov byte [cmd+bx],al jmp input
;コード実行 domsg: mov ah,09h mov dx,crlf int 21h mov dx,msg2 int 21h mov dx,crlf int 21h
main: inc word [cps] mov bx,[cps]
cmp byte [cmd+bx],'-' jz decr
cmp byte [cmd+bx],'>' jz next
cmp byte [cmd+bx],'<' jz back
cmp byte [cmd+bx],',' jz getc
cmp byte [cmd+bx],'.' jz putc
;変換分岐 cmp byte [cvt],1 jz cnvrt
;変換不必要 cmp byte [cmd+bx],'+' jz incr
cmp byte [cmd+bx],'[' jz lin
cmp byte [cmd+bx],']' jz lout
;変換必要 cnvrt: cmp byte [cmd+bx],':' jz incr
cmp byte [cmd+bx],']' jz lin
cmp byte [cmd+bx],'\' jz lout
done: mov bx,[mps] cmp byte [mem+bx],0 js err cmp word [mps],0 js err mov dx,[len] cmp [cps],dx js main mov ax,4c00h int 21h
;エラー処理 err: mov ah,09h mov dx,msg3 int 21h mov ax,4c00h int 21h
;+ incr: mov bx,[mps] inc byte [mem+bx] jmp done
;- decr: mov bx,[mps] dec byte [mem+bx] jmp done
;> next: inc word [mps] jmp done
;< back: dec word [mps] jmp done
;. putc: mov bx,[mps] mov dl,[mem+bx] mov ah,02h int 21h jmp done
;, getc: mov ah,08h int 21h mov bx,[mps] mov byte [mem+bx],al jmp done
;[ lin: mov bx,[mps] cmp byte [mem+bx],0 jz skip mov bx,[cps] push bx jmp done
skip: inc word [cps] mov bx,[cps] ;変換分岐 cmp byte [cvt],1 jz scnvrt ;変換不要 cmp byte [cmd+bx],'[' jz li cmp byte [cmd+bx],']' jz ld ;変換必要 scnvrt: cmp byte [cmd+bx],']' jz li cmp byte [cmd+bx],'\' jz ld jmp skip
li: inc byte [lev] jmp skip
ld: cmp byte [lev],0 jz done dec byte [lev] jmp skip
;] lout: pop bx mov word [cps],bx dec word [cps] jmp done
msg0 db "Do you need convert code? (Y:1,N:other)>>$" msg1 db "Input Brainfuck code!$" msg2 db "Output$" msg3 db "Error!!$" crlf db 0dh,0ah,"$" cvt db 0 cmd resb 800h cps dw 0 mem resb 800h mps dw 0 len dw 0 lev db 0
[/c]
ソースコードは多少長く長くなりましたが、実行ファイルの大きさはなんと4.5kB!びっくりするほど小さくなりました~
あ、でもここでは命令用・実行用メモリをそれぞれ0x800個、つまり十進数で2048個取っているのですが、Brainfuckの仕様通りに実行用メモリの数を30000個取るようにすると30kBほどに膨れ上がってしまうんです。その代わり、やはり演算は相変わらずめちゃくちゃ早いですw
ダウンロードは先日と同様こちらからどうぞ。Brainfuckインタプリタ
また来週くらいに同様の勉強会があるようなので、続きをやりに行こうと思います!!
バイナリ勉強会 #1
池袋で行われているバイナリ勉強会に初めて、友人と参加させて頂きました。
確か去年も一緒に前期試験が終わった直後に勉強会に参加して、その時は八王子まで出向いた気がします。でもそこでの勉強会は失敗だったんだよな・・・orz
まぁそんな前のことはどうでもいいのですねww
まずは大体半年程度を通してのカリキュラムを見せて頂きました。
基礎編ではBrainf*ckのインタプリタの自作から始まり、Cコンパイラの自作、UNIX V6でカーネル入門等々と続きます。
今日はその第一回なので、最初の最初にGtk#(初耳)でBrainf*ckのインタプリタをC#で作ります。
C#初めてで大丈夫かな・・・?とか思ったのですが、指示に従って進めていくとJavaの先代だけあって結構似通ったところがあって理解も進みます。
ひとまずこれがほとんど完成したところで昼食をはさんで後半戦に望みます。
お次の指示は、自分の好きな言語で何でもいいのでファイルから読み込んでBrainf*ckのインタプリタを作れとのこと。
ここで最初はC言語で作ろうと思ったのですが、気がついたら何故かC++で作ってましたww
今更なのですが、ここでBrainfuckの仕様を説明します。(引用:wikipedia Brainfuck)
処理系は次の要素から成る: Brainfuckプログラム、インストラクションポインタ(プログラム中のある文字を指す)、少なくとも30000個の要素を持つバイトの配列(各要素はゼロで初期化される)、データポインタ(前述の配列のどれかの要素を指す。最も左の要素を指すよう初期化される)、入力と出力の2つのバイトストリーム。
Brainfuckプログラムは、以下の8個の実行可能な命令から成る(他の文字は無視され、読み飛ばされる)。
>:
ポインタをインクリメントする。ポインタをptrとすると、C言語の「ptr++;」に相当する。<:
ポインタをデクリメントする。C言語の「ptr--;
」に相当。+:
ポインタが指す値をインクリメントする。C言語の「(*ptr)++;
」に相当。-:
ポインタが指す値をデクリメントする。C言語の「(*ptr)--;
」に相当。.:
ポインタが指す値を出力に書き出す。C言語の「putchar(*ptr);
」に相当。,:
入力から1バイト読み込んで、ポインタが指す先に代入する。C言語の「*ptr=getchar();
」に相当。[:
ポインタが指す値が0なら、対応する]
の直後にジャンプする。C言語の「while(*ptr){
」に相当。]:
ポインタが指す値が0でないなら、対応する[
(の直後)にジャンプする。C言語の「}
」に相当。
・・・開発始める前にちゃんと仕様読めば良かったなぁ。最初[には絶対に一回は入るように作っちゃうから失敗するんだよねww
そんな感じでなんだかんだで完成したのが以下になります。数ヶ月ぶりのちゃんとしたコーディングなので、完全に感覚が鈍っててコードが汚いのは勘弁してください。
[cpp]
include <iostream>
include <fstream>
include <cstdio>
using namespace std;
void func(char,char,int,int,int*); int loop[128]={};
int main(void){ ifstream ifs; char c,cmd[2048]={},mem[30000]={}; int i=0,cps=0,mps=0,lps=0;
ifs.open("text.bf",ios::in);
if(!ifs){ cout << "ファイルが存在しません。" << endl; return -1; }
for(i=0;!ifs.eof();i++){ ifs.get(c); cmd[i]=c; } while(cps<i-1) func(cmd,mem,&cps,&mps,&lps);
ifs.close(); return 0; }
void func(char cmd,char mem,int cps,int mps,int *lps){ int lev = 0;
switch(cmd[cps]){ case '>': ++mps; break;
case '<': --*mps; break;
case '+': ++mem[*mps]; break;
case '-': --mem[*mps]; break;
case '[': if(mem[mps]>0){ ++lps; loop[lps]=cps; } else{ int lev=1;
do{
++*cps;
switch(cmd[*cps]){
case '[':
++lev;
break;
case ']':
--lev;
break;
}
}while(lev!=0||cmd[*cps]!=']');
} break;
case ']': if(mem[mps]>0) cps=loop[lps]; else --lps; break;
case '.': cout << mem[*mps]; break;
case ',': mem[mps]=getchar(); break; } ++cps; } [/cpp]
ここで初めは","に対して『cin >> mem[*mps]』を使ってたのですが、これだと改行コードが含まれないことが判明したのでgetchar()にしました。 途中break文ごとコメントアウトして何で正常に動かないのだろうとかいうミスをやらかしたりしましたが、結果的に完成したのでよしとしましょう。 ここに完成品を置いておきますね。これはファイル読み込みではなく標準入力にしておきます。
さて、一通り済んだところで残り時間もわずかになりましたが、次の講座のためにMinGWを準備してbinutilsのインストールまでやっておきます。 ・・・ただここで『性能の違い』というものを見せ付けられました。自分のほう(Atom)が先にビルト始めたのに、友人のPC(i5)の方が完全に先に処理を終えるというwwww
まぁこんな感じで久しぶりに良い勉強会に当たったようなので、これから常連さんにでもなろうかと思っています。
これからもよろしくお願いします!
東工大受けてきました
あぁ、もうあれからまた一年が経ったんですね・・・
お久しぶりです、少し時間に余裕が出来たので3ヶ月ぶりの更新となります。
題名にあったとおり、本日東京工業大学の入試を受けてきました。
一通り全力は出し切ったつもりでいますが、なんというか数学がう~ん
後は結果を待つのみです。
あ、あと先日早稲田大学も受験したのですが、結果は『合格』の前に余計な二文字が付いていました。
正式な結果は来月の8日と18日に出るようですが、ちょっと望み薄感は否めないです。
まだ後期試験が残っているのでそこまで遊んではいられませんが、最近めっきり疎かになっていた開発を少し再開しようと思います。
短いですが、今日はこの辺でノシ
ブラインドSQLインジェクション
今日は久しぶりにセキュリティ関係について書き残そうと思います!
皆さん、世の中のサイトの何割位に脆弱性があると思いますか?
正解はなんと、9割方のページに何らかの欠陥があるという調査結果が出ているそうです、、、
今日はその脆弱性をつく手法の中で、『ブラインドSQLインジェクション』というものについてちょっとだけ説明しようと思います。
皆さんはSQLインジェクションについては知っていると思いますが、よく見かける文献にある実行例はどれもテーブル名等々が分かっている状態で実行するのがほとんど。ぺネトレーションテストを行う場合、当たり前ですが攻撃者はそんな中の情報は知らない前提で行うものです。
まずはSQLインジェクションについて少し。
これはアプリケーションのセキュリティーホールを利用して、任意のSQL文を注入(inject)し実行させ、データベースを不正に操作することを指します。
例えば、以下のようなSQL文があるとします。以下実行環境をMicrosoft社のSQLServerとします。
SELECT * FROM user WHERE id = '(会員ID)' AND pass ='(パスワード)';
ウェブのSQLインジェクションに対して未対策のログインフォームで、ID「testid」は分かっているがパスワードが不明な場合、ID欄に『testid'; --』と入力すると以下のような文ができます。
SELECT * FROM user WHERE id = 'testid'; --' AND pass ='(パスワード)';
『--』以降はコメントアウトとして処理されるため、パスワードの如何に関わらず「testid」さんとして問題なくログインできます。仮にパスワードの入力判定をしている場合でも、適当な値を入力さえしていれば通ってしまいます。
たとえIDが分かっていなくても、『' OR 1=1; --』と入力すれば、
SELECT * FROM user WHERE id = '' OR 1=1; --' AND pass ='(パスワード)';
となり、idカラムにどんな値が入力されようと『1=1』は常に真なのでuserテーブル内の全てのレコードが選択されます。
ここまで原理が分かってしまえば後は何でもし放題ですよね?w
試しに『'; UPDATE user SET pass=''; --』と入力したとすると、、、とんでもないですね。
SELECT * FROM user WHERE id = ''; UPDATE user SET pass=''; --
ログインは出来ず、一瞬失敗したかな?と思いますが、その裏では全てのパスワードが削除されているのです。あぁおそろしや・・・・・
ここで疑問が生じますよね?
『おい、なんでテーブル名がuserで、カラム名がpassということが分かってんだよ!』
・・・その通りです、ゴメンナサイ。ここで登場するのがブラインドSQLインジェクションです。
原理はとっても簡単で、『最初のテーブル名は1文字目がuか?2文字目はsか?』なんて事を延々と続けていけばいいんです。条件文にサブクエリを含ませて、その真偽によって判断します。
テーブル名を取得するためには
SELECT name FROM sysobjects WHERE xtype = 'U';
とすれば良いです。
試しに『' OR (SELECT count(name) FROM sysobjects WHERE xtype = 'U') > 0 --』を入力します。これは(テーブル数)>0は真かどうかを見ているので、テーブルがひとつでもあればログインできます。これを使えばサーバー内にあるテーブル数は確定できますね?(別に使うこと無いけどww)
では続いて先頭のテーブル名を得てみましょう。
『' OR lower(substring*1 >= 'n' --』
まず『SELECT min(name) FROM sysobjects WHERE xtype = 'U'』で先頭のテーブル名を取得し、これを以下'user'とします。substring('user',x,y)でx文字目からy文字取得し、ここでは'u'となります。lower()によって小文字へ変換されるため、決定が容易になります。
'u'は'n'以降なのでここでログインは成功します。次に'n'を't'として真、'x'として偽、'v'として偽、'u'として真なので1文字目が'u'と定まります。
それでも心配なら、『>= 'u' --』を『= 'u' --』として確実に確認してみるのもいいでしょう。
次は2文字目の確認です。substring()の引数を(x,y)=(1,2)として'un','ut'・・・としても間違ってはいませんが、毎回毎回'u'を打つのは非効率的です。なので、(x,y)=(2,1)とすれば'n'として真、't'として偽、'q'として真、's'として真より2文字目が's'と決定します。
これを繰り返して'user'まで求まったとします。しかし、ここで決定したぞ!と喜んではいけません。まだ4文字目も以降名前が続く可能性は十分あるからです。
『' OR (SELECT count(name) FROM sysobjects WHERE xtype = 'U' AND name = 'user') > 0 --』として真なら'user'テーブルは存在し、晴れて先頭のテーブル名を決定することができました。
'user'の次のテーブル名を取得するには、
『' OR lower(substring*2 >= 'n' 』として同じ事を繰り返せばOKです!ww
今回はSQL Serverを対象としましたが、それ以外は以下のようにすれば良いです。
Oracle select * from all_objects where object_type='TABLE';
PostgreSQL select * from pg_tables where not tablename like 'pg%' order by tablename;
H2 select * from INFORMATION_SCHEMA.tables;
では、今日はここまで~