ホーム » スタッフ (ページ 67)
「スタッフ」カテゴリーアーカイブ
文字列のハッシュ値と共有のあるデータの取り扱い
文字列のハッシュ値
ここまでで説明した事例は、電話番号をキーとするものであり、余りを求めるだけといったような簡単な計算で、ハッシュ値が求められた。しかし、一般的には文字列といったような名前から、ハッシュ値が欲しいことが普通だろう。
ハッシュ値は、簡単な計算で、見た目デタラメな値が求まればいい。 (ただしく言えば、ハッシュ値の出現確率が極力一様であること)。一見規則性が解らない値として、文字であれば文字コードが考えられる。複数の文字で、これらの文字コードを加えるなどの計算をすれば、 偏りの少ない値を取り出すことができる。
int hash_func( char s[] ) {
int sum = 0 ;
for( int i = 0 ; s[i] != '¥0' ; i++ ) {
sum = sum + s[i] ;
}
return sum % SIZE ;
}
文字列順で異なる値となるように
前述のハッシュ関数は、”ABC”さんと”CBA”さんでは、同じハッシュ値が求まってしまう。文字列順で異なる値が求まるように改良してみる。
int hash_func( char s[] ) {
int sum = 0 ;
for( int i = 0 ; s[i] != '¥0' ; i++ ) {
sum = sum*2 + s[i] ;
// sum = (sum * 小さい素数 + s[i]) % 大きい素数 ;
}
return sum % SIZE ;
}
共有のあるデータの取扱の問題
リスト構造で集合計算の和集合を求める処理を考える。
// 集合和を求める処理
struct List* join( struct List* a , struct List* b )
{ struct List* ans = b ;
for( ; a != NULL ; a = a->next )
if ( !find( ans , a->data ) )
ans = cons( a->data , ans ) ;
return ans ;
}
void list_del( struct List* p )
{ // ダメなプログラムの例
while( p != NULL ) { // for( ; p != NULL ; p = p->next )
struct List* d = p ; // free( p ) ;
p = p->next ;
free( d ) ;
}
}
void main() {
// リストの生成
struct List* a = cons( 1 , cons( 2 , cons( 3 , NULL ) ) ) ;
struct List* b = cons( 2 , cons( 3 , cons( 4 , NULL ) ) ) ;
struct List* c = join( a , b ) ; // c = { 1, 1, 2, 3 }
// ~~~~~~~ ここは b
// a,b,cを使った処理
// 処理が終わったのでa,b,cを捨てる
list_del( a ) ;
list_del( b ) ;
list_del( c ) ; // list_del(b)ですでに消えている
} // このためメモリー参照エラー発生
このようなプログラムでは、c=join(a,b) ; が終わると下の図のようなデータ構造となる。しかし処理が終わってリスト廃棄list_del(c), list_del(b), listdel(a)を行おうとすると、bの先のデータは廃棄済みなのに、list_del(c)の実行時に、その領域を触ろうとして異常が発生する。
参照カウンタ法
上記の問題は、b の先のリストが c の一部とデータを共有しているために発生する。この解決方法として簡単な方法では、参照カウンタ法が用いられる。
参照カウンタ法では、データを参照するポインタの数をデータと共に保存する。
- データの中にポインタ数を覚える参照カウンタを設け、データを生成した時に１とする。
- 処理の中で共有が発生すると、参照カウンタをカウントアップする。
- データを捨てる際には、参照カウンタをカウントダウンし、0になったら本当にそのデータを消す。
struct List {
int refc ; // 参照カウンタ
int data ; // データ
struct List* next ; // 次のポインタ
} ;
void list_del( strcut List* p ) { // 再帰で全廃棄
if ( p != NULL
&& --(p->refc) <= 0 ) { // 参照カウンタを減らし
list_del( p->next ) ; // 0ならば本当に消す
free( p ) ;
}
}
ただし、参照カウンタ法は、循環リストではカウンタが0にならないので、取扱いが苦手。
参照カウンタ法が用いられている事例をあげよ。
ガベージコレクタ
では、循環リストの発生するようなデータで、共有が発生するような場合には、どのようにデータを管理すれば良いだろうか？
最も簡単な方法は、処理が終わっても、使い終わったメモリを返却しない、方法である。ただし、このままでは、メモリを使い切ってしまう。
そこで、廃棄処理をしないまま、ゴミだらけになってしまったメモリ空間を再利用するのが、ガベージコレクタである。
ガベージコレクタは、貸し出すメモリ空間が無くなった時に起動され、
- すべてのメモリ空間に、「不要」の目印をつける。(unmark処理)
- 変数に代入されているデータが参照している先のデータは「使用中」の目印をつける。(mark処理)
- その後、「不要」の目印がついている領域は、だれも使っていないので回収する。(sweep処理)
この方式は、マークアンドスイープ法と呼ばれる。ただし、このようなガベージコレクタが動く場合は、他の処理ができず処理が中断されるので、コンピュータの操作性という点では問題となる。
最近のプログラミング言語では、参照カウンタとガベージコレクタを取り混ぜた方式でメモリ管理をする機能が組み込まれている。このようなシステムでは、局所変数のような生成され関数終了といったすぐに不要となる領域は、ガベージコレクタで管理し、大域変数のような長期間保管するデータはガベージコレクタで管理される。
データベースの物理設計
データベース後半課題
データベース後半の課題は「卒業研究の対象をデータベースとして設計」とする。
情報系の卒研テーマであれば、処理対象のデータの中にはデータベースで管理するのがふさわしい対象について設計せよ。実験系の卒研テーマであれば、実験結果の表をデータベースで管理するとした場合の設計を行うこと。どちらでもない卒研で、卒研のテーマの中にデータベース化すべき対象が無い場合は、身の回りの帳票(例えばコンビニのレシートなど)をデータベース化することを検討すること。
レポートで記載する内容は、以下の通りとする。
- 卒業研究におけるデータベース化する対象の説明
- データベースをトップダウン設計する際の
- 実体と関連を抽出するまでの説明
- 正規化を行う経過の説明
- 上記を踏まえたトップダウン設計でのER図
- データベースをボトムアップ設計する際の
- 対象とする帳票に相当するデータの一例と説明
- レベル分けや正規化を行う経過の説明
- 上記を踏まえたボトムアップ設計でのER図
- 考察
- トップダウン設計とボトムアップ設計に違いがあれば、設計の見直しの過程の説明
- 両設計方法から分かったこと
データベースの物理設計
データベースの物理的設計は、データベースの格納法法や管理方法を決定する。この際には、ディスク容量の見積もりやメモリ量の見積もりが重要となる。
ディスク容量の見積もり
データベースでは、B木(以降で解説予定)などが用いられることが1つのB木のノード(データブロック)の構造をおおまかに示す。各データブロックには、そのブロックを管理するためのページ制御の情報と、実データへのポインタとなるスロット情報と、実データからなる。
実データは、すべてのデータが固定長であれば、そのデータ長とブロック毎のデータ数にページ制御の容量を加えれば良い。しかし、データ長は可変であることが多い。この場合は、データの更新でデータ長が長くなると、その後ろのデータをずらす処理が頻発すると、データ管理の効率が悪い。
そこで、実データの間には、データ長が増えた時の空き領域を設けておく。この比率がPCTFREEと呼ばれ、この領域が埋まった時にのみデータをずらす処理を行う。
また、データベースへのデータの削除を行う場合、データが１つ消える度にデータブロックの構成を変化させると効率が悪く、通常はデータ削除の目印をつけるだけとすることが多い。データ削除で空きがふえた時だけ、データブロックの構成を変えたり、データ追加の際にデータを追加する。この比率は、PCTUSEDと呼ばれる。
このため、ハードディスク容量の見積もりでは、PCTFREE,PCTUSEDを考慮する必要がある。
一般的には、容量を減らす観点であれば、PCTFREEはなるべく小さく、PCTUSEDはなるべく大きい方が望ましいが、データの更新で追加・削除・修正が頻発するのであれば、PCTFREEはある程度大きく、PCTUSEDはある程度小さい方がよい。このため、PCTFREE+PCTUSED < 100 となるようにチューニングすることが多い。
また、実際のデータとは別に、データを高速に検索するためのインデックスファイルが作られるので、この容量も別途考慮が必要となる。
補足：残り予定：トランザクション処理, 内部構造, テスト前レポート課題
usacloud
さくらのクラウド上のサーバを、実験・演習用に使っているけど、未使用時に起動していると課金も増えるので、極力電源を落としたい。調べると、さくらのクラウドであれば usacloud という CLI により操作ができるみたい。
同じネタを「機構管理の Azure のサーバでも極力電源を落とせ」と言われているけど、利用者のいるWebサーバなので困難。
APIキーの取得
usacloud の説明を見ているけど、API キーの取得画面の出し方が変更になっているみたい。さくらのクラウドホームにて、APIキーを発行
usacloud のインストール
usacloud のドキュメントには、
curl -fsSL https://releases.usacloud.jp/usacloud/repos/install.sh | bash
と書かれていたけど、debian の apt の GPG エラーでインストールに失敗したので、usacloud_0.31.1-1_all.deb をダウンロードし、dpkg -i *.deb でインストール。
先の手順で作ったAPIキーを登録
[root]# usacloud config Setting SakuraCloud API Token => Enter token: xxxxxxxx-xxxx-xxxx-xxxx-xxxxxxxxxxxx Setting SakuraCloud API Secret => Enter secret: xxx...xxx Setting SakuraCloud Zone => Enter zone[is1a/is1b/tk1a/tk1v]: is1b Setting Default Output Type => Enter default-output-type[table/json/yaml/csv/tsv]: json Written your settings to /root/.usacloud/default/config.json
サーバの操作コマンド
設定が終われば、サーバの起動や停止もコマンド一発
((( サーバの起動 ))) $ sudo usacloud server boot 名前 $ sudo usacloud server wait-for-boot 名前 ((( シャットダウン ))) $ sudo usacloud server shutdown 名前 $ sudo usacloud server wait-for-down 名前 ((( サーバ一覧 ))) $ sudo usacloud server list $ sudo usacloud server list -q 11xxxxxxxxxx $ sudo usacloud server list --output-type table +--------------+---------+-----+--------+------------+--------------------+--------+----------------+ | ID | Name | CPU | Memory | Commitment | IPAddress | Status | Host | +--------------+---------+-----+--------+------------+--------------------+--------+----------------+ | 11xxxxxxxxxx | nitfcei | 2 | 2048MB | standard | xxx.xxx.xxx.xxx/24 | up | sac-xxxx-xxxxx | +--------------+---------+-----+--------+------------+--------------------+--------+----------------+ $
LEGO MindStorms のハードウェア情報
LEGO を IchigoJam とか Raspberry Pi で触れないかと、ハードウェアの回路的情報を知りたくなって探してみた。
Linux演習 – LOG解析
Linux は利用者に様々なサービスを提供するサーバで広く利用されている。しかし、幅広いサービス提供となると、中にはウィルス拡散や個人情報収集のための悪意のあるアクセスも増えてくる。
このためサーバでは、アクセスを受けた時の状況を記録し保存する。このような情報はアクセス履歴、ログと呼ぶ。
ログの中には、以下のような情報が混在することになるが、大量の 1. や 2. 目的のアクセスの中に、3. や 4. といったアクセスが混ざることになるが、これを見逃すとシステムに不正侵入を受ける可能性もある。
- 本来の利用者からのアクセス
- 検索システムの情報収集(クローラーからのアクセス)
- 不正な情報収集のためのアクセス
- システムの不備を探して不正侵入などを試みるアクセス
今回の演習では、電子情報の web サーバのとある1日のアクセス履歴ファイルを用い、パイプ機能を使い様々なフィルタを使い LOG解析の練習を行う。
アクセス履歴の解析
Webサーバのアクセス履歴が、/home0/Challenge/2.2-LOG.d/access.log に置いてある。このファイルで簡単な確認をしてみよう。
(( ファイルの場所に移動 )) $ cd /home0/Challenge/2.2-LOG.d/ (( .asp という文字を含む行を表示 )) $ grep .asp access.log
電子情報のWebサーバには、.asp (WindowsのWebサーバで動かすプログラムの拡張子) など存在しない。明らかに設定不備を探すための攻撃である。
これを見ると、grep で .asp を含む行が抜粋され、.asp の部分が強調されていることで、攻撃を簡単に確認できる。しかしこれは画面行数で10件程度が確認できるが、本当は何回攻撃を受けたのだろうか？この場合は、行数をカウントする”wc -l” を使えばいい。
(( アクセス回数を数える )) $ grep .asp access.log | wc -l 37
access.log の各項目の意味
電子情報のWebサーバの access.log に記録されている各項目の意味は以下の通り。
| 項目 | log項目 | 内容 |
|---|---|---|
| 1 | %h | リモートホスト。WebサーバにアクセスしてきたクライアントのIPアドレス |
| 2 | %l | リモートログ名。説明略。通常は “-“ |
| 3 | %u | ログインして操作するページでのユーザ名。通常は “-“ |
| 4 | %t | アクセスを受けた時刻 |
| 5 | %r | 読み込むページ。アクセス方法(GET/POSTなど)と、アクセスした場所。 |
| 6 | %>s | ステータスコード。(200成功,403閲覧禁止,404Not Found) |
| 7 | %b | 通信したデータのバイト数。 |
| 8 | %{Referer}i | Referer どのページからアクセスが発生したのか |
| 9 | %{User-Agent}i | User-Agent ブラウザ種別(どういったブラウザからアクセスされたのか) |
以下に、フィルタプログラムを活用して、色々な情報を探す例を示す。実際にコマンドを打って何が表示されるか確認しながら、フィルタプログラムの意味を調べながら、何をしているか考えよう。
.asp を使った攻撃を探す
(( .asp を試す最初の履歴を探す )) $ grep "\.asp" access.log | head -1 49.89.249.9 - - [20/Dec/2019:09:19:06 +0900] "POST /Include/md5.asp HTTP/1.1" 404 64344 "https://www.ei.fukui-nct.ac.jp/Include/md5.asp" "Mozilla/4.0 (compatible; MSIE 9.0; Windows NT 6.1)" (( 49.89.249.9 がどんなアクセスを試みているのか探す )) $ grep ^49.89.249.9 access.log | head 49.89.249.9 - - [20/Dec/2019:09:19:06 +0900] "POST /Include/md5.asp HTTP/1.1" 404 64344 "https://www.ei.fukui-nct.ac.jp/Include/md5.asp" "Mozilla/4.0 (compatible; MSIE 9.0; Windows NT 6.1)" 49.89.249.9 - - [20/Dec/2019:09:19:06 +0900] "POST /inc/md5.asp HTTP/1.1" 404 61056 "https://www.ei.fukui-nct.ac.jp/inc/md5.asp" "Mozilla/4.0 (compatible; MSIE 9.0; Windows NT 6.1)"
- ステータスコードが404は”Not Found”なので、読み出しに失敗している。
- IPアドレス検索で、49.89.249.9 がどこのコンピュータか調べよう。
攻撃の時間を確認
(( 49.89.249.9 がどんな時間にアクセスを試みているのか探す ))
$ grep ^49.89.249.9 access.log | awk '{print $4;}'
[20/Dec/2019:09:19:06
[20/Dec/2019:09:19:06
[20/Dec/2019:09:19:07
:
- 不正アクセスを試みている時間を調べると、そのアクセス元の09:00～17:00に攻撃していることがわかる場合がある。どういうこと?
ページの閲覧頻度を確認
(( /~t-saitoh/ 見たIPアドレスと頻度 ))
$ grep "/~t-saitoh/" access.log | awk '{print $1;}' | sort | uniq -c | sort -g -r | head
38 151.80.39.78
35 151.80.39.209
32 203.104.143.206
31 5.196.87.138
:
- grep – “/~t-saitoh/”のページをアクセスしているデータを抽出
- awk – 項目の先頭(IPアドレス)だけ抽出
- sort – IPアドレス順に並べる(同じIPアドレスならその数だけ重複した行になる)
- uniq – 重複している行数を数える
- sort -g -r – 先頭の重複数で大きい順にソート
- head – 先頭10行だけ抽出
(( /~t-saitoh/ 見たIPアドレスと頻度 )) (( t-saitoh のテスト問題のページを誰が見ているのか? )) $ grep "/~t-saitoh/exam/" access.log 5.196.87.156 - - [20/Dec/2019:06:36:02 +0900] "GET /~t-saitoh/exam/db2009/ex2009-5-1.pdf HTTP/1.1" 200 20152 "-" "Mozilla/5.0 (compatible; AhrefsBot/6.1; +http://ahrefs.com/robot/)" : (( クローラーのアクセスが多くてよくわからないので bot を含まない行を抽出 )) $ grep "/~t-saitoh/exam/" access.log | grep -v -i bot | lv 213.242.6.61 - - [20/Dec/2019:06:33:12 +0900] "GET /%7Et-saitoh/exam/ HTTP/1.0" 200 19117 "http://www.ei.fukui-nct.ac.jp/%7Et-saitoh/exam/" "Mozilla/5.0 (Windows NT 6.1; WOW64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/67.0.3396.87 Safari/537.36 OPR/54.0.2952.64 (Edition Yx)" 188.163.109.153 - - [20/Dec/2019:06:43:04 +0900] "GET /%7Et-saitoh/exam/ HTTP/1.0" 200 19117 "http://www.ei.fukui-nct.ac.jp/%7Et-saitoh/exam/" "Mozilla/5.0 (Windows NT 6.1; WOW64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/66.0.3359.170 Safari/537.36 OPR/53.0.2907.99" 188.163.109.153 - - [20/Dec/2019:06:43:05 +0900] "POST /cgi-bin/movabletype/mt-comments.cgi HTTP/1.0" 404 432 "http://www.ei.fukui-nct.ac.jp/%7Et-saitoh/exam/" "Mozilla/5.0 (Windows NT 6.1; WOW64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/66.0.3359.170 Safari/537.36 OPR/53.0.2907.99" 45.32.193.50 - - [20/Dec/2019:07:06:15 +0900] "GET /~t-saitoh/exam/apply-prog.html HTTP/1.0" 200 5317 "http://www.ei.fukui-nct.ac.jp/" "Mozilla/5.0 (Windows NT 5.2) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/63.0.3239.132 Safari/537.36"
- この結果を見ると mt-comments.cgi というアクセスが見つかる。どうも コメントスパム(ブログのコメント欄に広告を勝手に書き込む迷惑行為)をしようとしている。
ネットワーク攻撃への対処
今回の access.log のアクセス履歴解析は、Webサーバへのアクセスへの基本的な対処となる。しかし、もっと違うネットワーク接続ではどのような対処を行うであろうか？
一般的には、
- サーバにネットワークアクセスの記録ソフトを使う(例ネットワークプロトコルアナライザーWireShark)
- ファイアウォールのアクセス履歴を解析
授業内レポート
- ここまでのLOG解析の例の１つについて、どういう考え方でフィルタを使っているのか、自分の言葉で説明せよ。
- LOG 解析のためのコマンドを考え、その実行結果を示し、それから何が判るか説明せよ。
(例) コメントスパムを何度も試す危ないアクセス元は〇〇である。
Linux演習 – リダイレクトとパイプ
Linux演習の第２弾として、リダイレクトとパイプについて説明し、LOG解析の演習を行う。
標準入出力とリダイレクト
出力リダイレクト
C言語のプログラミングで、プログラムの実行結果をレポートに張り付ける時はどのように行っているだろうか？多くの人は、実行画面を PrintScreen でキャプチャした画像を張り付けているかもしれない。しかし、数十行にわたる結果であれば何度もキャプチャが必要となる。
そこで、今日の最初はリダイレクト機能について説明する。
“gcc ファイル.c” は、C言語のプログラムをコンパイルし、a.out という実行ファイルを生成する。”./a.out” にてプログラムを実行する。実行する命令に、“> ファイル名” と書くと、通常の出力画面(標準出力) をファイル名に記録してくれる。これを出力リダイレクトと呼ぶ。また、“>> ファイル名” と書くと、既存ファイルの後ろに追記してくれる。
s53599xx@nitfcei:~$ cat helloworld.c
#include <stdio.h>
int main() {
printf( "Hello World\n" ) ;
return 0 ;
}
s53599xx@nitfcei:~$ gcc helloworld.c
s53599xx@nitfcei:~$ ./a.out
Hello World
s53599xx@nitfcei:~$ ./a.out > helloworld.txt
s53599xx@nitfcei:~$ cat helloworld.txt
Hello World
s53599xx@nitfcei:~$ ./a.out >> helloworld.txt
s53599xx@nitfcei:~$ cat helloworld.txt
Hello World
Hello World
入力リダイレクト
次に、1行に名前と3教科の点数が書いてある複数行に渡るデータの各人の平均点を求めるプログラムを考える。
s53599xx@nitfcei:~$ cp /home0/Challenge/2.1-RedirectPipe.d/avg-each-low.c .
s53599xx@nitfcei:~$ cat avg-each-low.c
#include <stdio.h>
// ((input)) ((output))
// saitoh 43 54 82 saitoh 59.67
// tomoko 89 100 32 tomoko 73.67
// mitsuki 79 68 93 mitsuki 80.00
int main() {
char name[ 100 ] ;
int point[ 3 ] ;
while( scanf( "%s%d%d%d" ,
name , &point[0] , &point[1] , &point[2] ) == 4 ) {
double sum = 0.0 ;
for( int i = 0 ; i < 3 ; i++ )
sum += point[i] ;
printf( "%s %6.2f\n" , name , sum / 3.0 ) ;
}
return 0 ;
}
s53599xx@nitfcei:~$ gcc avg-each-low.c
s53599xx@nitfcei:~$ ./a.out
saitoh 43 54 82 入力
saitoh 59.67 出力
tomoko 89 100 32 入力
tomoko 73.67 出力
^D ← Ctrl-D を押すとファイル入力を終了
しかし、プログラムの書き方を間違えてプログラムを修正していると、動作確認のたびに何度も同じデータを入力するかもしれないが、面倒ではないだろうか？
プログラムを実行する時に、“< ファイル名” をつけると、通常はキーボードから入力する所を、ファイルからの入力に切り替えて実行することができる。このようなscanf()を使う時のようなプログラムの入力を標準入力といい、それをファイルに切り替えることを入力リダイレクトと呼ぶ。
s53599xx@nitfcei:~$ cp /home0/Challenge/2.1-RedirectPipe.d/name-point3.txt . s53599xx@nitfcei:~$ cat name-point3.txt saitoh 43 54 82 tomoko 89 100 32 mitsuki 79 68 93 s53599xx@nitfcei:~$ ./a.out < name-point3.txt saitoh 59.67 tomoko 73.67 mitsuki 80.00
この入力リダイレクトと出力リダイレクトを合わせて使うこともできる。
s53599xx@nitfcei:~$ ./a.out < name-point3.txt > name-avg.txt s53599xx@nitfcei:~$ cat name-avg.txt saitoh 59.67 tomoko 73.67 mitsuki 80.00
パイプ
先の名前と3教科のプログラムの結果から、全員の平均点をも計算したい場合、どのようなプログラムを作るだろうか？C言語だけの知識なら、各人の行のデータを計算するループの中に、全員の合計と人数を求めるプログラムを書いて、最後に平均点を出力するだろう。
一方で、複数人の名前と平均点のデータから平均点を求めるプログラムを書いて、前述のプログラムの実行結果を使う人もいるだろう。
以下の例では、“gcc -o avg-each-row avg-each-row.c” で、avg-each-row という実行ファイル、“gcc -o avg-all avg-all.c” で、avg-all という実行ファイルを生成し、avg-each-row で入力リダイレクト・出力リダイレクトを使って、name-avg.txt を作り、avg-all を入力リダイレクトで、最終結果を表示している。
s53599xx@nitfcei:~$ cp /home0/Challenge/2.1-RedirectPipe.d/avg-all.c .
s53599xx@nitfcei:~$ cat avg-all.c
#include <stdio.h>
// ((input)) ((output))
// saitoh 59.67 73.11
// tomoko 73.67
// mitsuki 80.00
int main() {
char name[ 100 ] ;
double point ;
double sum = 0 ;
int count = 0 ;
while( scanf( "%s%lf" , name , &point ) == 2 ) {
sum += point ;
count++ ;
}
printf( "%6.2f\n" , sum / (double)count ) ;
return 0 ;
}
s53599xx@nitfcei:~$ gcc -o avg-each-low avg-each-low.c
s53599xx@nitfcei:~$ gcc -o avg-all avg-all.c
s53599xx@nitfcei:~$ ./avg-each-low < name-point3.txt > name-avg.txt
s53599xx@nitfcei:~$ ./avg-all < name-avg.txt
71.11
しかし、いちいち入出力の結果を name-avg.txt を作るのは面倒である。であれば、以下の様なイメージで処理をすれば答えが求まる。
name-point3.txt→(avg-each-row)→name-avg.txt→(avg-all)→結果
これは、パイプ機能を使って以下の様に動かすことができる。
s53599xx@nitfcei:~$ ./avg-each-low < name-point3.txt | ./avg-all 71.11 s53599xx@nitfcei:~$ cat name-point3.txt | ./avg-each-low | ./avg-all 71.11
プログラムを実行する時に、“A | B” ように書くと、プログラムA の標準出力結果を、プログラムB の標準入力に接続させて、2つのプログラムを実行できる。このような機能を、パイプと呼ぶ。上記例の2つめ “cat… | ./avg-each-low | ./avg-all” では3つのプログラムをパイプでつないでいる。
リダイレクトのまとめ
| 入力リダイレクト(標準入力) | 実行コマンド < 入力ファイル |
| 出力リダイレクト(標準出力) | 実行コマンド > 出力ファイル |
| 出力リダイレクト(標準出力の追記) | 実行コマンド >> 出力ファイル |
| 標準エラー出力のリダイレクト | 実行コマンド 2> 出力ファイル |
| パイプ コマンドAの標準出力をコマンドBの標準入力に接続 |
コマンドA | コマンドB |
C言語のコンパイルまとめ
| C言語のコンパイル(実行ファイルはa.out) | gcc ソースファイル |
| 実行ファイル名を指定してコンパイル | gcc -o 実行ファイル ソースファイル |
フィルタプログラム
パイプを使うと、標準入力からデータをもらい・標準出力に結果を出力するような簡単なプログラムを組み合わせて、様々な処理が簡単にできる。こういったプログラムは、フィルタと呼ぶ。
簡単な例として、入力をすべて大文字に変換するプログラム(toupper)、入力文字をすべて小文字に変換するプログラム(tolower)が、下記の例のように保存してあるので動作を確かめよ。
s53599xx@nitfcei:~$ cp /home0/Challenge/2.1-RedirectPipe.d/toupper.c .
s53599xx@nitfcei:~$ gcc -o toupper toupper.c .
s53599xx@nitfcei:~$ cat toupper.c | ./toupper
#INCLUDE <STDIO.H>
#INCLUDE <CTYPE.H>
INT MAIN() {
INT C ;
WHILE( (C = GETCHAR()) != EOF )
PUTCHAR( TOUPPER( C ) ) ;
RETURN 0 ;
}
s53599xx@nitfcei:~$ cp /home0/Challenge/2.1-RedirectPipe.d/tolower.c .
s53599xx@nitfcei:~$ gcc -o tolower tolower.c
s53599xx@nitfcei:~$ cat tolower.c | ./tolower
(((何が出力されるか答えよ)))
よく使われるフィルタのまとめ
| 文字パターンを含む行だけ出力 | grep 文字パターン |
| 文字パターンを含まない行を出力 文字パターンを正規表現でマッチングし該当行を出力 大文字小文字を区別しない |
grep -v 文字パターン grep -e 正規表現 grep -i 文字パターン |
| 入力文字数・単語数・行数をカウント(word counter) | wc |
| 入力行数をカウント | wc -l |
| データを昇順に並べる | sort |
| データを降順に並べる 先頭を数字と見なしてソート |
sort -r sort -g |
| 同じ行データが連続したら1つにまとめる | uniq |
| 同じ行が連続したら1つにまとめ、連続した数を出力 | uniq -c |
| 空白区切りで指定した場所(1番目)を抽出 | awk ‘{print$1;}’ |
| 入力の先頭複数行を表示(10行) | head |
| 入力の末尾複数行を表示(10行) | tail |
| 指定した行数だけ、先頭/末尾を表示 | head -行数 tail -行数 |
Linux演習 – ファイル操作
Linux演習サーバへの接続
Unix(Linux)は、インターネットでのサーバとして広く活用されている。Linuxを試すには、Windows ならば WSL や Cygwin であったり、Mac でも使える仮想OSの VMware, VirrtualBox を使うこともでる。今回の演習では、全員が同じ環境で使うために、クラウド環境にサーバを準備した。クラウドのunixサーバを利用する場合には、リモートログインのための ssh が一般的である。
一方、教室のWiFi環境では、HTTP,HTTPS の通信しか使えないことから、ssh が通常利用できない。そこで、この演習では、特殊な使い方だが、HTTPS(443) ポートを使う。
$ ssh -p 443 情報処理センターID@演習サーバ
- 演習サーバの接続方法(学内のみ) – サーバへの攻撃を極力へらすために非公開。
- パスワード入力時にタイプミスした時は、Ctrl-U で最初から入力のやり直しができる。
- サーバの設置先の問題で、パスワード入力後20秒ほど待つ必要があるので注意。
ファイル操作の基本
まずは基本操作をしてみよう。ls コマンド(list) は、ディレクトリ内にあるファイルの一覧を表示する。cat コマンド(catalog)は、指定されたファイルの内容を表示する。
s53599xx@nitfcei:~$ ls
helloworld.c Maildir
s53599xx@nitfcei:~$ ls -l
total 8
-rw-r--r-- 1 s53599xx students 76 Dec 21 14:30 helloworld.c
drwx------ 5 s53599xx students 4096 Dec 21 14:30 Maildir
s53599xx@nitfcei:~$ cat helloworld.c
#include <stdio.h>
int main() {
printf( "Hello World\n" ) ;
return 0 ;
}
s53599xx@nitfcei:~$
ファイルをコピーするには cp コマンド(copy)、不要なファイルを消すには rm コマンド(remove)を使う。
s53599xx@nitfcei:~$ cp helloworld.c test.c s53599xx@nitfcei:~$ ls -l total 8 -rw-r--r-- 1 s53599xx students 76 Dec 21 14:30 helloworld.c drwx------ 5 s53599xx students 4096 Dec 21 14:30 Maildir -rw-r--r-- 1 s53599xx students 76 Dec 21 14:40 test.c s53599xx@nitfcei:~$ rm test.c s53599xx@nitfcei:~$ ls -l total 8 -rw-r--r-- 1 s53599xx students 76 Dec 21 14:30 helloworld.c drwx------ 5 s53599xx students 4096 Dec 21 14:30 Maildir s53599xx@nitfcei:~$
ファイル詳細表示の説明
ls -l で表示される詳細の内容は以下の通り。
| 属性 | リンク数 | 所有者 | グループ | サイズ | 日付 | ファイル名 |
|---|---|---|---|---|---|---|
| – rw- r– r– | 1 | s53599xx | students | 76 | Dec 21 14:30 | helloworld.c |
| d rwx — — | 5 | s53599xx | students | 4096 | Dec 21 14:30 | Maildir |
| – | d | -: 通常ファイル, d:ディレクトリ | ||||
| rw- | rwx | 所有者が r:読み出し, w:書き込み, -: 権限なし ファイルなら、x:実行可能 ディレクトリなら、x:ディレクトリに入れる |
||||
| r – – | – – – | グループの rwx の属性 r– は 読み込みだけ許可 | ||||
| r – – | – – – | その他の rwx の属性 — は、読み書き禁止 | ||||
基本的なファイル操作コマンド一覧
| 操作 | Linux | Windows |
|---|---|---|
| ディレクトリ一覧(list) ディレクトリ詳細 |
ls 場所 ※ ls -l 場所 |
dir /w 場所 ※ dir 場所 |
| ※ 省略時はカレントディレクトリ | ||
| ファイル表示(catalog) | cat 場所 | type 場所 |
| ファイルコピー(copy) | cp コピー元 コピー先 cp コピー元 コピー先ディレクトリ |
copy コピー元 コピー先 |
| ファイル削除(remove) | rm 場所 | del 場所 |
| ディレクトリ作成(make dir) | mkdir 場所 | md 場所 |
| ディレクトリ削除(remove dir) | rmdir 場所 | rmdir 場所 |
| カレントディレクトリ移動 (change directory) |
cd 場所 | cd 場所 ドライブの場合は ドライブ名: |
| 所有者を変更(change owner) | chown 所有者 場所 | |
| グループを変更(change group) | chgrp グループ 場所 | |
| 属性を変更(change mode) | chmod 属性 場所 | ←属性の書き方 |
ワイルドカード文字
ls などのコマンドで、複数のファイルを対象とするとき、ワイルドカード文字が使える。
| 任意の1文字 ? |
(例) $ ls aaa.c ab.c abc.c bcd.c defgh.c hij.cxx $ ls a?.c ab.c $ ls ???.c aaa.c abc.c bcd.c |
| 任意の文字 * |
(例) $ ls a*.c aaa.c ab.c abc.c $ ls *.cxx jij.cxx |
相対PATHと絶対PATH
ファイルの場所を指定するには、2つの方法がある。
絶対PATHは、木構造の根(ルートディレクトリ / で表す) からの経路のディレクトリ名を”/”で区切って書き連ねる。ルートディレクトリからの場所であることを示すために、先頭を / で始める。住所を /福井県/越前市/宮谷町/斉藤家 と書くようなもの。
相対PATHは、現在注目しているディレクトリ(カレントディレクトリと呼ぶ)からの経路を書く。住所でいうと、/福井県/越前市 に注目している状態で、宮谷町/斉藤家 と書くようなもの。
上記の絵であれば、/home/tsaitoh/helloworld.c を、相対PATHで書く場合、s53599xx の一つ上にさかのぼって場所を指定することもできる。一つ上のディレクトリ(親ディレクトリ)は .. (ピリオド2つ)
この場合、” $ cat ../tsaitoh/helloworld.c ” の様な相対PATHでもアクセスできる。
カレントディレクトリ自身を表す場合は、. (ピリオド1つ)を使う。
/home/s53599xx/helloworld.c の場所は、” $ cat ./helloworld.c ” と書くこともできる。
CTF風に演習
ここで、ディレクトリの場所の書き方が理解できたかを練習してみよう。
/home0/Challenge/1-CTF.d の下にフォルダがいくつかあり、その中にさらにファイルがある。このファイルの中には、FLAG{なんとか} と書いた部分がある。この「なんとか」の部分を速く見つけ出して答えよう。
上記フォルダには、5つの問題 Task1 , Task2 , Task3 , Task4 , Task5 がある。
Task2 , Task3 では、以下のコマンドを使う。(ヒントはTaskフォルダの0ReadMeを読め)
| 操作 | Linux |
|---|---|
| ページャで表示(空白で次のページ,qで停止) | more ファイルの場所 |
| 元に戻れるページャ(less) | less ファイルの場所 |
| 多機能ページャ(文字コード判別) | lv ファイルの場所 |
| 漢字コード変換 | nkf ファイルの場所 nkf -j ファイル JISコードで表示 nkf -s ファイル Shift-JISコードで表示(Windows) nkf -e ファイル EUCコードで表示 nkf -w ファイル UTF-8 で表示(Mac,Linux) |
Task4 , Task5 には、難易度をあげるためのトリックがしかけてある。(ヒント 0ReadMe)
授業内レポート
- 自分でみつけられたフラグを以下の様に答えよ。(できた所までで良い)
Task1 = FLAG{なんとか}
Task2 = … - Task1 で答えを見つけるまでに実行したコマンドとその途中結果を簡単にまとめよ。
できれば、実行したコマンドを、相対PATH形式、絶対PATH形式で答えよ。
$ cd /home0/Challenge/1-CTF.d/Task1
$ ls
0ReadMe brain concussion persons
history コマンドは、過去に実行したコマンドを表示してくれる。
Linux初心者向けCTF
オペレーティンス・システムの授業の中でちょっとしたLinux演習を授業中に行うことになった。
Linux 環境は、さくらクラウドの上に準備した。学校の教室にてBYODパソコンを用いて行いたいので、WSL や VMplayer などを各自でインストールして演習を行うことも考えたが、環境が違うと演習が行いづらいので、さくらクラウドを用いることとした。
演習サーバへの接続
教室は http, https での接続しかできないように設定してあるので、通常の方法ではクラウドに接続させるのは困難。そこで、さくらクラウドのサーバは、この演習専用とし、https(443)ポートを ssh に割り当て接続させる。
(( Windows 10 ならば cmd.exe にて )) C:..> ssh -p 443 演習室ID@演習サーバ Password: 演習室のパスワード -- この段階で20秒ほどかかる -- [~]$
CTF形式の演習
簡単に cd , ls , cat や ページャ(more,less,lv) と 漢字コード変換 nkf などを説明し、絶対PATH,相対PATHの概念を説明したあと、CTF形式の演習問題を用意した。
指定したフォルダ /home/Challenge の配下に、以下のフォルダを設け、ファイル内に記載された FLAG{答え} 形式のものを答えてもらう。
- Task1 – 普通に探すだけ
- Task2 – 複数行のファイルで ページャを使わないと見逃す様にしてあるファイルの中から探す。ファイルの中に空白を含むファイル名も置いておく。
- Task3 – cmd.exe などの環境だと文字コードの問題があるので、nkf を使って読ませる。JIS, Shift-JIS, EUC-JP, UTF-8 などばらまいておく。
- Task4 – シンボリックリンクでディレクトリが再起的ループするようにしたディレクトリの中から探す。ハイフンを含むファイル名や、chmod で読めないファイル、入れないディレクトリも置いておく。
- これを通して、chmod , ls -al , などの説明を行う。
- Task5 – セキュリティ意識を持ってもらうための演習。.bashrc には、PATH=.:/usr/bin:/bin となるように設定してある。この状態で、ディレクトリ内に、killall -KILL bash のシェルスクリプトを記載した、ls, cat, more, nkf を置いておく。
- これを通して、サーチPATHの説明を行う。
答えの確認方法
答えといっても、ディレクトリ構造を cd , ls , cat しながら、さらうだけなので、大したことはない。Linux 管理者なら、以下で終わるネタ。
$ find /home0/Challenge -type f -exec nkf -w {} ¥; | grep FLAG
ハッシュ法
ここまでの授業では、配列(データ検索は、登録順保存ならO(N)、２分探索ならO(log N)となる)、単純リスト(データ検索(シーケンシャルアクセスしかできないのでO(N)となる)、2分探索木( O(log N) ) といった手法を説明してきた。しかし、もっと高速なデータ検索はできないのであろうか？
究極のシンプルなやり方(メモリの無駄)
最も簡単なアルゴリズムは、電話番号から名前を求めるようなデータベースであれば、電話番号自身を配列添え字番号とする方法がある。しかしながら、この方法は大量のメモリを必要とする。
// メモリ無駄遣いな超高速方法
struct PhoneName {
int phone ;
char name[ 20 ] ;
} ;
// 電話番号は6桁とする。
struct PhoneName table[ 1000000 ] ; // 携帯電話番号ならどーなる!?!?
// 配列に電話番号と名前を保存
void entry( int phone , char* name ) {
table[ phone ].phone = phone ;
strcpy( table[ phone ].name , name ) ;
}
// 電話番号から名前を調べる
char* search( int phone ) {
return table[ phone ].name ;
}
しかし、50人程度のデータであれば、電話番号の末尾2桁を取り出した場合、同じ数値の人がいることは少ないであろう。であれば、電話番号の末尾2桁の値を配列の添え字番号として、データを保存すれば、配列サイズは100件となり、メモリの無駄を減らすことができる。
ハッシュ法
先に述べたように、データの一部を取り出して、それを配列の添え字番号として保存することで、高速にデータを読み書きできるようにするアルゴリズムはハッシュ法と呼ばれる。データを格納する表をハッシュ表、データの一部を取り出した添え字番号はハッシュ値、ハッシュ値を得るための関数がハッシュ関数と呼ばれる。
// ハッシュ衝突を考えないハッシュ法
#define HASH_SIZE 100 ;
struct PhoneName table[ HASH_SIZE ] ;
// ハッシュ関数
int hash_func( int phone ) {
return phone % HASH_SIZE ;
}
// 配列に電話番号と名前を保存
void entry( int phone , name ) {
int idx = hash_func( phone ) ;
table[ idx ].phone = phone ;
strcpy( table[ idx ].name , name ) ;
}
// 電話番号から名前を調べる
char* search( int phone ) {
int idx = hash_func( phone ) ;
return table[ idx ].name ;
}
ただし、上記のプログラムでは、電話番号の末尾2桁が偶然他の人と同じになることを考慮していない。
例えば、データ件数が100件あれば、同じ値の人も出てくるであろう。このように、異なるデータなのに同じハッシュ値が求まることを、ハッシュ衝突と呼ぶ。
たとえ話で言うなら、100個の椅子が連番付きで並んでいて、自分の電話番号末尾2桁の場所に座ろうとしたら、先に座っている人がいるような状態である。このような状態で、あなたなら何処に座るだろうか？
ハッシュ関数に求められる特性
ハッシュ関数は、できる限り同じような値が求まるものは、ハッシュ衝突が多発するので、避けなければならない。例えば、6桁の電話番号の先頭2桁であれば、電話番号の局番であり、同じ学校の人でデータを覚えたら、同じ地域の人でハッシュ衝突が発生してしまう。また、ハッシュ値を計算するのに、配列の空き場所を一つ一つ探すような方式では、データ件数に比例した時間がかかり、高速なアルゴリズムでなくなってしまう。このことから、ハッシュ関数には以下のような特徴が必要となる。
- 同じハッシュ値が発生しづらい(一見してデタラメのように見える値)
- 簡単な計算で求まること。
- 同じデータに対し常に、同じハッシュ値が求まること。
オープンアドレス法
先の椅子取りゲームの例え話であれば、先に座っている人がいた場合、最も簡単な椅子に座る方法は、隣が空いているか確認して空いていたらそこに座ればいい。
これをプログラムにしてみると、以下のようになる。このハッシュ法は、求まったアドレスの場所にこだわらない方式でオープンアドレス法と呼ばれる。
// オープンアドレス法
// table[] は大域変数で0で初期化されているものとする。
// 配列に電話番号と名前を保存
void entry( int phone , name ) {
int idx = hash_func( phone ) ;
while( table[ idx ].phone != 0 )
idx = (idx + 1) % HASH_SIZE ;
}
table[ idx ].phone = phone ;
strcpy( table[ idx ].name , name ) ;
}
// 電話番号から名前を調べる
char* search( int phone ) {
int idx = hash_func( phone ) ;
while( table[ idx ].phone != 0 ) {
if ( table[ idx ].phone == phone )
return table[ idx ].name ;
idx = (idx + 1) % HASH_SIZE ;
}
return NULL ; // 見つからなかった
}
注意：このプログラムは、ハッシュ表すべてにデータが埋まった場合、無限ループとなるので、実際にはもう少し改良が必要である。
チェイン法
前に述べたオープンアドレス法は、ハッシュ衝突が発生した場合、別のハッシュ値を求めそこに格納する。配列で実装した場合であれば、ハッシュ表以上の データ件数を保存することはできない。
チェイン法は、同じハッシュ値のデータをグループ化して保存する方法。 同じハッシュ値のデータは、リスト構造とするのが一般的。
#define SIZE 100
int hash_func( int ph ) {
return ph % SIZE ;
}
struct PhoneNameList {
int phone ;
char name[ 20 ] ;
struct PhoneNameList* next ;
} ;
struct PhoneNameList* hash[ SIZE ] ; // NULLで初期化
struct PhoneNameList* cons( int ph ,
char* nm ,
struct PhoneNameList* nx ) {
struct PhoneNameList* ans ;
ans = (struct PhoneNameList*)malloc(
sizeof( struct PhoneNameList ) ) ;
if ( ans != NULL ) {
ans->phone = ph ;
strcpy( ans->name , nm ) ;
ans->next = nx ;
}
return ans ;
}
void entry( int phone , char* name ) {
int idx = hash_func( phone ) ;
hash[ idx ] = cons( phone , name , hash[ idx ] ) ;
}
char* search( int phone ) {
int idx = hash_func( phone ) ;
struct PhoneNameList* p ;
for( p = hash[ idx ] ; p != NULL ; p = p->next ) {
if ( p->phone == phone )
return p->name ;
}
return NULL ;
}
コンテスト入賞で校長表敬
HIT2019にて、優秀賞をなった3EIグループと、高専デザコンAM部門で審査員特別賞となった専攻科グループで校長表敬を行いました。
