ホーム » スタッフ » 斉藤徹 » 実験(斉藤)

実験(斉藤)」カテゴリーアーカイブ

2020年12月
 12345
6789101112
13141516171819
20212223242526
2728293031  

最新の投稿(電子情報)

アーカイブ

カテゴリー

CTF実験: unix 系開発環境のインストール

CTFでは、様々な unix 系の開発環境のコマンドが用いられる。

これらの環境を構築するためのメモを記載。

Windows の場合

macOS の場合

macOS で unix 系の開発環境を使う場合には、homebrew や MacPorts を用いることが多い。

CTFでよく使われるunix系パッケージ

((ファイル系))
file - ファイルの種別判定
zip  - zip,unzip(ファイル圧縮解凍)
gzip - gzip,gunzip(ファイル圧縮解凍-GNU)
nkf  - nkf(日本語漢字フィルタ)
hexcurse - hexcurse(バイナリエディタ)

((OS系))
gcc  - gcc(コンパイラ-GNU)
gdb  - gdb(デバッガ-GNU)
binutils - objdump(逆アセンブラ) ,
         - nm(オブジェクトファイルのシンボル出力) ,
         - strings(文字部分の出力)

((ネットワーク系))
telnet - telnet(telnetクライアント)
netcat-openbsd - nc(TCP/IP 汎用ツール)
bind9-dnsutils - nslookup, dig(DNS参照ツール)
whois - whois(ディレクトリサービスクライアント)

((ブラウザ系))
w3m  - w3m(テキストブラウザ)
wget - wget(テキストブラウザ+ダウンローダ)
curl - curl(ダウンローダ)

((使用上要注意))
nmap - nmap(ネットワーク調査ツール)
wireshark - wireshark(パケットキャプチャ)
          - windows用とかmac用のバイナリの方が便利

各unix系のインストールコマンド

((WSL2の場合))
$ sudo apt-get install gcc binutils

((Homebrew の場合))
$ sudo brew install gcc binutils

((MacPorts の場合))
$ sudo port install gcc binutils

専攻科実験: unix系 開発環境のインストール

コンパイラの技術と関数電卓プログラムの実験では、unix系の開発環境で一般的なコンパイラ作成用のツール flex , bison を用いる。これらの環境を構築するためのメモを記載。

Windows の場合

((ubuntuの場合))
$ sudo apt-get install gcc flex bison make

macOS の場合

macOS で unix 系の開発環境を使う場合には、homebrew や MacPorts を用いることが多い。

((Homebrew の場合))
$ sudo brew install gcc flex bison make

((MacPorts の場合))
$ sudo port install gcc flex bison make 

専攻科実験・コンパイラと関数電卓プログラム作成

コンパイラの技術と関数電卓プログラム(2)

前半では、1文字の数字と簡単な演算子で表現される計算式を再帰下降パーサで計算する処理で、演習を行った。

後半は、さらに実際のコンパイラに近いものとして、 C言語で広く使われている、字句解析ツール(lexical analyzer : lex or flex)、 構文解析ツール(parser : yacc or bison) を使って、 さらに現実的な関数電卓プログラムを作ってみる。

lex or flex による字句解析

lexは、字句解析のプログラムを自動生成するツール“%%”行の内側に、正規表現によるルールとその処理(アクション)を書き並べる。 また、“%{ … %}”の内側に、その処理に必要なC言語のソースを書き、 lex で処理を行うと、lex.yy.c というC言語のソースを出力する。

lex.yy.c の中には、yylex() という関数が自動的に作られ、次に示す構文解析ツールから呼び出される。

# flex は、lex の改良版。

(( mycalc.l ))
%{
#include <stdio.h>
// yaccが出力するヘッダファイル
#include "y.tab.h"

int yywrap( void )
{
   // 1: スキャナ終了
   // 0: yyin を切り替えて継続
   return 1 ;
}
%}
%%
"+"  return ADD ;
"-"  return SUB ;
"*"  return MUL ;
"/"  return DIV ;
"\n" return CR  ;
[0-9][0-9]* {
   // 入力はyytextに格納されている。
   int temp ;
   sscanf( yytext , "%d" , &temp ) ;
   yylval.int_value = temp ;
   // 返り値は、字句(トークン)の種別を表す定数
   return INT_LITERAL;
}
%%

このプログラムを、lex で処理させると、正規表現“+” 記号ADD という定数記号を割り振るとか、正規表現の数字列” [0-9][0-9]* “をみつけると、その正規表現に対する{〜}までに書かれたアクションを処理するため、文字列から数値を生成(sscanf)して、その場合の記号に INT_LITERAL という定数記号を割り振る…といった処理のプログラムを自動生成してくれる。(INT_LITERALは構文解析側で定義する定数)

yacc or bison

yacc ( Yet Another Compiler Compiler ) もしくはその改良版の bison は、構文解析のプログラムを自動生成してくれるツールである。構文をBNF記法で記載すると、字句解析ツール(lex等)を呼び出しながら構文に合わせたトークンの出現に応じた状態遷移のための「遷移テーブル」を自動生成し、 その遷移テーブルを用いた処理のプログラムをC言語で出力してくれる。

先に示した字句解析プログラム(lex)は、様々なトークン(C言語なら演算子やキーワード)とデータ(C言語なら数値や文字列)を返す。このデータには様々な場合考えられるので、 そのトークンに合わせたデータの型を “%union” の中に記載する(中身はC言語の共用体)。 “%%”〜”%%” の間には、BNF記法の(ルール)と、それに対応する処理(アクションは“{ }”の中の部分)を記載する。最初の“%{ … %}”の間には、それ以外の処理に必要なC言語の処理を記載する。

# bison(水牛)は、yacc(山牛)の改良版。

(( mycalc.y ))
%{
#include <stdio.h>
#include <stdlib.h>

// yacc が定義する内部関数のプロトタイプ宣言
#define YYDEBUG 1
extern  int  yydebug ;
extern  int  yyerror( char const* ) ;
extern  char *yytext ;
extern  FILE *yyin ;

// 最初に呼び出される関数yyparse()
extern  int  yyparse( void ) ;

// 字句解析を呼び出す関数yylex()
extern  int  yylex( void ) ;
%}

// 字句(トークン)の定義
%union {
   int  int_value;
}
%token <int_value>  INT_LITERAL
%token ADD SUB MUL DIV CR
%type  <int_value>   expression term primary_expression

%%
// 構文の定義
line_list  : line                // 行の繰り返し
           | line_list line
           ;

line       : expression CR       { printf( ">>%d\n" , $1 ) ; }
           ;

// 以下のBNFルールは、単純に再帰に置き換えると
//   無限に再帰して異常終了するものであることに注意
expression : term
           | expression ADD term { $$ = $1 + $3 ; }
           | expression SUB term { $$ = $1 - $3 ; }
           ;

term       : primary_expression
           | term MUL primary_expression { $$ = $1 * $3 ; }
           | term DIV primary_expression { $$ = $1 / $3 ; }
           ;

primary_expression
           : INT_LITERAL
           ;
%%

// 補助関数の定義
int yyerror( char const* str )
{
   fprintf( stderr , "parser error near %s\n" , yytext ) ;
   return 0 ;
}
int main( void )
{
   yydebug = 0 ;        // yydebug=1 でデバッグ情報表示
   yyin = stdin ;
   if ( yyparse() ) {   // 構文解析を開始
      fprintf( stderr , "Error ! Error ! Error !\n" ) ;
      exit( 1 ) ;
   }
}

yacc では、%%-%%の間に書かれたBNF記法によるルールとアクションをプログラムに変換してくれる。BNF記法の要素は、“要素 : ルール1 {アクション1} | ルール2 {アクション2} | … ;” といった構成になっている。要素 expression に対するルール expression$1 ADD$2 term$3では、ルールの各要素をアクションで参照する時には、$1,$2,$3 といった変数を利用できる。ルール「加算式($1) +($2) 乗算式($3)」という文になっている部分を見つけると、そのルールに対応するアクション“{ $$ = $1 + $3 ; }”「$1(加算式部分の値)と、$3(乗算式の部分)の値を加えて、$$(式の結果)に代入する」といった処理を生成してくれる。yyparse() 関数を呼び出すと、構文の一番最上部の line_list に相当する処理が起動される。yyerror()は、構文解析の途中で文法エラーになった時に呼び出される関数。

生成されるパーサの内容に興味があるなら、生成される y.tab.c の内容を読むと良い。

make と Makefile

これらのプログラムでは、字句解析プログラム mycalc.l から生成された lex.yy.c, y.tab.h と, 構文解析プログラム mycalc.y から生成された y.tab.c を組合せて1つの実行ファイルにコンパイルする。 これらの手順は煩雑なので、make ツールを使う。

make は、 Makefile に記載されている“ターゲット”と、それを作るために必要な“依存ファイル”、 “依存ファイル”から”ターゲット”を生成する処理“アクション”から構成される。 make は、ターゲットと依存ファイルの更新時間を比較し、 必要最小限の処理を行う。

基本的な Makefile の書き方は、

ターゲット: 依存ファイル...
        アクション       # アクションの前はタブ

の様に書き、依存ファイルが更新されていたら、アクションを実行し、ターゲットを更新する。

以下に、今回の課題で使用する Makefile を示す。

(( Makefile ))
# 最終ターゲット
mycalc:	y.tab.o lex.yy.o
        gcc -o mycalc y.tab.o lex.yy.o

# 構文解析処理
y.tab.o: mycalc.y
        bison -dy mycalc.y	# -dy : yacc互換モード
        gcc -c y.tab.c

# 字句解析処理
lex.yy.o: mycalc.l mycalc.y
        flex -l mycalc.l        # -l : lex互換モード
        gcc -c lex.yy.c

# 生成ファイルの削除ルール
clean:; rm mycalc y.tab.c y.tab.h lex.yy.c *.o

(( ファイルの依存関係のイメージ図 ))
mycalc.l           mycalc.y
  |     \           |
lex.yy.c  y.tab.h  y.tab.c
  |            \    |
lex.yy.o        y.tab.o
        \    /
         mycalc

この課題にあたり、後半の実験では flex, bison などの unix 系プログラミング環境を利用する。

macOS の利用者であれば MacPorts や Homebrew 、Windows 利用者であれば、wsl2(Windows subsystem for Linux) や Cygwinなどをインストールし実行すること。

今回の実験であれば、linux(Debian系)ならば、”sudo apt-get install flex bison gcc make” にて、必要なパッケージをインストールして実験を行うこと。

コンパイラの技術と関数電卓プログラム(1-2)

前回の実験資料では、再帰下降パーサについて説明し、サンプルプログラムを示した。

演算子の左結合・右結合

ここで、プログラムの実際の動きについて考えてみる。前回の乗除式の BNF 記法による定義は以下のようであった。

exp_乗徐式 ::= DIGIT '*' exp_乗徐式
            | DIGIT '/' exp_乗徐式
            | DIGIT
            ; 

このBNFによる文法において、1*2*3 を考えると、以下のように解析がすすむ。
しかし、これでは 1*(2*3) であり、右結合にて処理が行われたことになる。

   exp_乗徐式
  /|\
DIGIT| exp_乗徐式
 |  |   /|\   
 |  |DIGIT| exp_乗徐式
 |  |  | | |
 |  |  | | DIGIT
 |  |  | | |
  1  *  2  *  3

左結合とするには

これをC言語で一般的な、(1*2)*3 といった左結合の処理になるように、BNF 記法の文法を下記のように書き換えるかもしれない。

exp_乗徐式 ::= exp_乗徐式 '*' DIGIT
            | exp_乗徐式 '/' DIGIT
            | DIGIT
            ; 

しかし、このBNF記法をそのまま下記のような再帰に置き換えると、再帰が無限に続き異常終了してしまう。

int exp_MUL_DIV( ... ) {
   int left = exp_MUL_DIV( ... ) ;
   if ( **endp == '*' ) {
      (*endp)++ ;
      if ( isdigit( **endp ) ) {
         int right = **endp - '0' ;
         (*endp)++ ;
         return left + right ;
      }
   } else ...
      :
}

左結合のプログラムにする場合は、BNF記法の処理を杓子定規に再帰プログラムで記述する必要はない。

空白除去

プログラム中の空白を無視するのであれば、以下のような補助関数を作っておくと便利かな。使い方は考えること。

void skip( char**ppc ) {
   while( isspace( **ppc ) )
      (*ppc)++ ;
}

コンパイラの技術と関数電卓プログラム(1)

コンパイラを作るための技術の基礎を学んでもらうために、 簡単な関数電卓プログラム作成を課題とする。 基本は、printf( “%d” , eval( “1+2*3”) ) みたいな計算プログラムを作成する。

計算式から、計算処理を行う場合、演算子の優先順位を正しく処理できることが求められる。
一般的には、計算の機械語を生成する場合、データを準備して計算という方法であり、 逆ポーランド記法変換が行われる。
たとえば、”1+2×3″は、”1,2,+,3,×” といった表記に改められ、変換後の式は スタックを用いて、「値はpush,演算子はpop,pop,計算して,push」という 単純なルールで処理すれば、計算を行うことができる。

字句解析と構文解析

このような、計算式の処理を実行する場合、”1“,”+“,”2“,”✳︎“,”3“という 字句に切り分ける処理を、字句解析という。 この結果から、”式✳︎式”なら掛け算、”式+式”は足し算といった、 前後の字句の組合せから、構文木を生成する処理は、構文解析という。 コンパイラであれば、この後、最適化コード生成などが行われる。

C言語であれば、コンパイル前後には以下の処理が行われる。

  • プリプロセッサ処理
    ↓(#の無いCコード)
  • コンパイル処理
    • 字句解析  —  今回の実験
    • 構文解析  —  今回の実験のキモ
    • コード生成

    ↓(中間コード)

  • リンク処理 ← ライブラリ
  • 機械語

字句解析と正規表現

字句(トークン)の切り出しでは、その文法を説明する際には、正規表現などを用いる。
今回の実験の後半では、正規表現に合わせたプログラミングツール(flex)を用いるが、前半では正規表現に合わせた文字列処理をプログラムする必要がある。

簡単な正規表現
 . 任意の文字
 * 直前の0回以上の繰り返し
 + 直前の1回以上の繰り返し
 [0-9a-z] カッコの中の文字のいずれか - は範囲を示す。
 (a|b|c) 丸カッコの|区切りのうちのどれか。
 (例) C言語の変数の正規表現 [a-zA-Z_][a-zA-Z0-9_]*

構文解析の方法

構文解析では、構文を状態遷移として考え、この式の後にくる可能性のある状態は? という考えで解析を行う。 このような構文は、一般的にバッカス・ナウア記法(BNF)などで表現されることが多い。 また、簡単な構文解析であれば、

などが用いられる。

再帰下降パーサ

簡単な再帰下降パーサの演習として、1桁の数字と+,*演算子の処理プログラムを 考える。

加減,乗除の式のバッカス記法(BNF)
exp_加減 ::= exp_乗除 '+' exp_乗除
          | exp_乗除 '-' exp_乗除
          | exp_乗除               (注意)このBNFは若干間違っているよ!!
          ;
exp_乗除 ::= DIGIT '*' exp_乗除
          | DIGIT '/' exp_乗除
          | DIGIT
          ;
DIGIT   ::= [0-9]
          ;

練習として、上に示す再帰下降パーサに、 (1) “(“,”)” を含めた場合の、BNF 記法を考え、(2) 数値として複数桁が使えるようにし、 (3) 式を読みやすくする空白を処理できるように 改造せよ。

CTF問題とセキュリティ(4年実験)

この実験では、セキュリティコンテストのCTF問題(Capture The Flag競技)について、インターネットの仕組みを理解し、その問題の解き方を考え、新しく自分自身でCTF問題を作ってもらいます。

日程

実験は、4週にわたり、以下の日程で行います。

内容
1 (前半)暗号・ファイル・Web
2
3 (後半) プログラム作成・インターネット・OS
4

前半・後半でそれぞれ、問題例(もしくは自分で見つけたCTF問題)の1つの説明と、自作の問題を新しく作り説明をしてください。

提出物

  • 実験の目的
  • 問題例(or 自分で見つけたCTF問題)を1つ選び
    • 前半・後半それぞれについて
    • その問題が情報セキュリティにどう関係しているのか
    • 問題の解き方のしくみと解説
  • 自作問題について
    • 前半・後半それぞれ
    • その問題が情報セキュリティにどう関係しているのか
    • 問題の解き方、問題の作り方
    • しくみと解説
  • 提出先はこちらのTeams共有フォルダに。

PHPとセキュリティのレポート講評

5年生の前期実験で「PHPとセキュリティ」のテーマについて、レポートの採点を行った。

以下に、レポート記載での注意点や減点評価を行なったポイントをあげる。

レポートの記載書式について

  1. 電子レポート提出でも所属や報告者の記載をつけること。
    今回は、遠隔実験でPDFファイルのアップロード提出であったため、表紙のつけ忘れなどが見られた。印刷媒体で残す可能性を考慮し、文章内に所属・出席番号・氏名なりの記入は必須。
  2. 図番号・表番号を必ず引用すること。
    実験結果に図番号や表番号をつける習慣はみなさんついているが、本文中で必ず図番号や表番号を引用すること。前表によれば…はNG。「図1をみると…」「(表1参照)」などをつけること。図表は配置の都合で本文とは別のページに記載することもあるので、異なるページに配置されても、わかるように記載する必要がある。
  3. 章・節のインデントはしない。
    今回は減点対象としていないが、卒業論文や卒研中間報告では、節や小節でインデントをしないこと。
    特に、2段組みをする文書の場合、インデントが入るとただでさえ狭い1行が、スカスカになる。

    1. 論文書式ではダメな書き方
    この実験は...  □のようなインデントは不要!!
    ...であった。
    1.1 背景
    □□この問題の背景として...
    □□1.1.1 なんとかかんとか
    □□□なんとかかんとか
    

レポートの考察内容について

  1. PHPのプログラムの改良で、<input … maxlength=”xx”>とか、<input type=…> とか、<input … pattern=”xxx”>をとるといった考察があったが、これは不十分。例えば、Webページの HTML を、自分のサイトにコピーして、maxlenthやpatternを削除したページを作ってそこからPHPにデータを送ることで、相変わらずセキュリティの問題を引き起こすことが可能。HTMLのページを偽装しなくても、プログラムからphpに対して直接データを渡すこともできる。
    このため、送られてくる入力値のチェック(一般的にはサニタイジングと呼ばれる)は、php側でも十分に行う必要がある。
  2. password の管理については、/etc/shadow ファイルの話までしか調べていない考察があった。
    passwdコマンドは、SUID の説明と、その機能「一時的にpasswdコマンドの所有者rootの権限を借りる」の説明がないと減点とした。
    考察のヒントに記載した、自分のパスワードが変更できるのなら/etc/passwdへの書き込み権限があるはず…と同じで、自分のパスワードを変更可能なら/etc/shadowに書き込み権限がある…という話になってしまうから。

(追記)

レポートの採点結果つけたよ…とTeamsで伝えたら、ゾロゾロと自分の点数を聞きにくる人多数。いつも、レポート返却しても教室に放置されてるし、他の先生の評価で平均されるから、あまり気にしないと思ってた。

const char*s, char* const sの違い

専攻科実験のサンプルコードで、警告がでたことについて質問があったので説明。

(( サンプルコード sample.cxx ))
#include <stdio.h>
void foo( char* s ) {
  printf( "%s¥n" , s ) ;
}
int main() {
  foo( "ABC" ) ;
  return 0 ;
}

(( コンパイル時の警告 ))
$ g++ sample.cxx
test.cxx:6:6: warning: conversion from string literal
      to 'char *' is deprecated
      [-Wc++11-compat-deprecated-writable-strings]
  foo( "abcde" ) ;
       ^
1 warning generated.

警告を抑止する “-Wno-…” のオプションをつけて “g++ -Wno-c++11-compat-deprecated-writable-strings sample.cxx” でコンパイルすることもできるけど、ここは変数の型を厳格にするのが鉄則。

この例では、引数の “ABC” が書き換えのできない定数なので、const キーワードを付ければよい。ただし、宣言時の const の付け場所によって、意味が違うので注意が必要。

void foo( char const* s ) { // const char* s も同じ意味
   *s = 'A' ; // NG ポインタの先を書き換えできない
   s++ ;      // OK ポインタを動かすことはできる
}
void foo( char *const s ) {
   *s = 'A' ; // OK ポインタの先は書き込める
   s++ ;      // NG ポインタは動かせない
}
void foo( char const*const s ) {
   *s = 'A' ; // NG ポインタの先を書き換えできない
   s++ ;      // NG ポインタは動かせない
}

const を書く場所は?

int const x = 123 , y = 234 ; の場合、yは定数だろうか?

(( おまけ ))
#include <stdio.h>
int main() {
  int const x = 123 , y = 234 ; // x は定数だけど yは定数?
  x++ ; // 予想通りエラー
  y++ ; // yも定数なのでエラー
  int const s = 345 , const t = 456 ; // sもtも明らかに定数っぽい
  //                  ^ここで文法エラー

  // おまけのおまけ
  char* s , t ;   // s は文字へのポインタ、t は文字
  char  *s , *t ; // s は文字へのポインタ、t も文字へのポインタ
  return 0 ;
}

Visual Studio Code で印刷

実験や授業課題のレポート提出で、プログラムを印刷したものを提出してくれるけど、行を移動しながら何度もスクリーンキャプチャで保存した画像ファイルをWordに貼り付けて提出している人が多い。

いままでなら、「秀丸エディタで印刷してよ…」とか言ってたけど、最近は Visual Studio Code を利用しているみたいで、「プログラムの印刷の仕方がわからない」という人が多いようだ。

実際、Visual Studio Code はたまにしか使わないけど、確かに基本機能の中には印刷機能がないな….

今時、プログラムリストなんて紙媒体で印刷しないもんなんだろうけど、プログラム課題のレポートなら、コードは証拠だからな。

Visual Studio Code の PrintCode

こういう場合は、Visual Studio Code の拡張機能の PrintCode をインストールすればいい。

印刷する時は、F1 キーを押して、拡張コマンドの入力で printcode と打てば印刷される。

ただし、PrintCode は JavaScript を使って HTML を生成し印刷を行うため、Windowsでデフォルトブラウザが Internet Explorer の場合は動かない。このためデフォルトブラウザの変更により Chrome などを使う様に変更しておく必要あり。

Sublime Text なら Print to HTML

同じく、エディタが Sublime Text を使っているのなら、これも印刷機能が付いていないので、”Print to HTML”パッケージをインストールし、あとは、Shift+Alt+P で HTML 用に出力できるのでブラウザ側で印刷を行う。