ホーム » 2023
年別アーカイブ: 2023
ふくいソフトウェアコンペ大賞！
2023年12月23日に開催された、ふくいソフトウェアコンペティション2023にて、4EI 藤野間くん, 中西くん, 山腰くんによる「チャリレコ－ 1人1人の未来を守る次世代システム－」が、ふくいソフトウェアコンペの最優秀賞を受賞しました。
2023年最後の授業は休校かぁ…
自宅の外の雪の状態としては大した雪じゃないけど、休校になっちゃったなぁ…
WWWとhttpとサーチエンジン
WWWとhttp
WWWとは、ティム・バーナーズ=リーによって作られたサービスであり、元々は研究データの論文やデータの共有のために作られた。この際のWebサーバのデータのやり取りのためのプロトコルがhttp(Hyper Text Transfer Protocol)であり、ポート番号80のTCPを用いたものであり、最近では通信を暗号化したhttps(ポート番号443)も多く使われる。
httpでは、文字データの中に画像や音声といった情報に加え、他のデータへのリンクを埋め込むことができる HTML(Hyper Text Markup Language) のデータがやりとりされる。このHTML形式のデータを表示するためのソフトは、ブラウザと呼ばれる。
URL
WWWのデータの場所を示すものが、URL(Uniformed Resource Locator)であるが、最近ではインターネットが複雑化しLocator という表現が難しいため、URI(Uniformed Resource Identifier)と呼ぶようになってきた。
URLは基本的に、スキーマ://コンピュータ名/サーバ内ファイル位置 といった文字で構成される。URL は、HTTP だけでなく、インターネットの情報の場所を記述するために使われており、httpやhttps以外にも使う。
最近のブラウザは、スキーマ欄の”https://”やコンピュータ名の先頭の”www.”を省略することができる。また http は暗号通信を使わず危険であることから、警告メッセージが表示されたり、可能であれば https の通信に切り替えを試みられる。
http (Hyper Text Transfer Protocol) の流れ
httpのサーバ(Webサーバ)とブラウザでは、以下のような手順で処理が行われる。例えば http://www.ei.fukui-nct.ac.jp/~t-saitoh/index.html のページが表示されるまでを考えると、
- ブラウザのURL欄に、目的サイトのURLを入力。
- 基本的には、スキーマ欄に記載されたプロトコル(http)名から、ポート番号と通信方法(http)を決める。一般的な http 通信では、ポート番号には 80 を使う。
- コンピュータ名部分(www.ei.fukui-nct.ac.jp)を DNS に問合せして、得られたIPアドレスのコンピュータに接続。
- httpの最も簡単な GET メソッドでは、Webサーバに、サーバ内のファイル位置(/~t-saitoh/index.html)を伝えると、Webサーバは応答ヘッダ情報と応答本文の指定された場所のファイルの内容を返送する。(下図参照)
- HTML形式のデータが指定された場合、ブラウザはその HTML をどの様に表示するか判断しながら表示する。
このような予め保存されているWebページを返送する場合は静的ページと呼ばれる。サーバのデータベースなどを参照しながらページ内容を返送する場合は、動的ページと呼ばれ、Webサーバ内部でプログラムを動作させ、その結果のデータをブラウザに返す。
動的ページを生成するためのプログラム言語としては、様々な方法がある。(バックエンド言語)
- 言語 Perl による CGI(Common Gateway Interface)
- Webに特化した言語PHP
- サーバで 言語 Java を使ってページデータを生成(Apache Tomcat)
- サーバで 言語 JavaScript を使ってページデータを生成(Node.js)
また、最近のブラウザでは JavaScript を使って、Webページに表示される内容を動的に変化させることが多い。(フロントエンド)
https
httpでは、通信が平文で行われるため、同じサブネット内であれば通信内容を盗み見られる可能性がある。この通信を暗号化しながら行われるものが https である。ポート番号には一般的に 443 が使われる。暗号化通信は次週以降に説明を行う。
サーチエンジン
インターネットでは、大量のWebページが出現してきたため、自分の目的に応じてWebページを探す機能が必要となってきた。このような目的のWebページを検索してくれるシステムは、サーチエンジンと呼ばれる。
ディレクトリ型
最初に現れた検索システムは、ページ作者が自分のページのURLと内容となるキーワードをサーチエンジンに登録しておき、内容のカテゴリー別に、ページの紹介文章が表示されるディレクトリ型であった。(初期のYahoo)
しかし、登録するキーワード以外の文字で探そうとすると、情報を見つけることができない。
ロボット型
これらの問題を解決すべく登場したのが、Google のようなロボット型サーチエンジンである。
ロボット型の検索システムでは、クローラーとかロボット(あるいはボット)とか呼ばれるプログラムを使い、Webページの内容をダウンロードし、そこに記載された文字を使ってURLのデータベースを作成する。
- 与えられた URL の先のページをダウンロードする。
- ページ内の文字を単語に切り分けして、それぞれの単語とURLを関連付けてデータベースに保存
- ページ内にリンクが含まれていたら、そのURLで、この作業を再帰的に繰り返す。
サーチエンジンで検索が行われると、クローラーの処理で作られたデータベースに問い合わせ、見つかったURLの情報を表示する。
Googleなどでは、多くのユーザが探したいページを提供するために、たくさん使われている単語を重要語としたり、たくさんのページからリンクされているページを表示順上位に表示するような工夫をしている。
ページランキングを上げるためのWebページの工夫をすることを、SEO (Search Engine Optimization) という。しかし逆にページランキングを不当に上げようと特殊なテクニックのページ作りをする人もいるが、最近では不当なページ作りは逆にランキングが落とされるようになっている。
理解度確認
- URLが与えられてページが見れるまでに行われることを説明せよ。
- サーチエンジンのディレクトリ型とロボット型の違いを説明せよ。
データベースの物理設計
前回の授業の際に説明した、後半のレポート課題を改めてページの資料として提示し、前半はデータベースの物理設計の話を行う。後半は、レポート課題の時間とする。
データベース後半課題
データベース後半の課題は「卒業研究の対象をデータベースとして設計」とする。
情報系の卒研テーマであれば、処理対象のデータの中にはデータベースで管理するのがふさわしい対象について設計せよ。実験系の卒研テーマであれば、実験結果の表をデータベースで管理するとした場合の設計を行うこと。どちらでもない卒研で、卒研のテーマの中にデータベース化すべき対象が無い場合は、身の回りの帳票(例えばコンビニのレシートなど)をデータベース化することを検討すること。
レポートで記載する内容は、以下の通りとする。
- 卒業研究におけるデータベース化する対象の説明
- データベースをトップダウン設計する際の
- 実体と関連を抽出するまでの説明
- 正規化を行う経過の説明
- 上記を踏まえたトップダウン設計でのER図
- データベースをボトムアップ設計する際の
- 対象とする帳票に相当するデータの一例と説明
- レベル分けや正規化を行う経過の説明
- 上記を踏まえたボトムアップ設計でのER図
- 考察
- トップダウン設計とボトムアップ設計に違いがあれば、設計の見直しの過程の説明
- 両設計方法から分かったこと
データベースの物理設計
データベースの物理的設計は、データベースの格納法法や管理方法を決定する。この際には、ディスク容量の見積もりやメモリ量の見積もりが重要となる。
ディスク容量の見積もり
データベースでは、B木(以降で解説予定)などが用いられることが1つのB木のノード(データブロック)の構造をおおまかに示す。各データブロックには、そのブロックを管理するためのページ制御の情報と、実データへのポインタとなるスロット情報と、実データからなる。
実データは、すべてのデータが固定長であれば、そのデータ長とブロック毎のデータ数にページ制御の容量を加えれば良い。しかし、データ長は可変であることが多い。この場合は、データの更新でデータ長が長くなると、その後ろのデータをずらす処理が頻発すると、データ管理の効率が悪い。
そこで、実データの間には、データ長が増えた時の空き領域を設けておく。この比率がPCTFREEと呼ばれ、この領域が埋まった時にのみデータをずらす処理を行う。
また、データベースへのデータの削除を行う場合、データが１つ消える度にデータブロックの構成を変化させると効率が悪く、通常はデータ削除の目印をつけるだけとすることが多い。データ削除で空きがふえた時だけ、データブロックの構成を変えたり、データ追加の際にデータを追加する。この比率は、PCTUSEDと呼ばれる。
-- PCTFREE,PCTUSED の使い方の例 -- CREATE TABLE Person ( id INTEGER NOT NULL PRIMARY KEY , name VARCHAR( 20 ) , address VARCHAR( 30 ) , ) PCTFREE 10 PCTUSED 40 ; -- PCTFREE+PCTUSED < 100 --
このため、ハードディスク容量の見積もりでは、PCTFREE,PCTUSEDを考慮する必要がある。
一般的には、容量を減らす観点であれば、PCTFREEはなるべく小さく、PCTUSEDはなるべく大きい方が望ましいが、データの更新で追加・削除・修正が頻発するのであれば、PCTFREEはある程度大きく、PCTUSEDはある程度小さい方がよい。このため、PCTFREE+PCTUSED < 100 となるようにチューニングすることが多い。
例えば、ページサイズが4096バイト、ページ制御情報が32バイト、スロット制御情報が1データあたり4バイト、PCTFREEが30%、平均の1件あたりのデータ長が256バイトで、100000件を保存するとする。この場合、1ページ内でデータ用に使用できる領域は、(4096-32)✕(1-0.3) = 2844バイトとなる。この場合、1ページに保存できるデータは 2844÷(256+4) = 10.9 となり、最大で10件となる。このため、データを保存するために必要なデータ領域は 4096×(100000/10) = 40.9MB となる。単純にデータを覚えるだけであれば、本来なら 256×100000=25.6MB であるため、実際には1.6倍のデータ領域が必要であることが分かる。(教科書の説明より…)
また、実際のデータとは別に、データを高速に検索するためのインデックスファイルが作られるので、この容量も別途考慮が必要となる。
補足：残り予定：トランザクション処理, 内部構造, テスト前レポート課題
ハッシュ法
ここまでの授業では、配列(データ検索は、登録順保存ならO(N)、２分探索ならO(log N)となる、2分探索ができるのは配列がランダムアクセスができるからこそ)、単純リスト(データ検索(シーケンシャルアクセスしかできないので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件あれば、同じ値の人も出てくるであろう。このように、異なるデータなのに同じハッシュ値が求まることを、ハッシュ衝突と呼ぶ。
ハッシュ関数に求められる特性
ハッシュ関数は、できる限り同じような値が求まるものは、ハッシュ衝突が多発するので、避けなければならない。例えば、6桁の電話番号の先頭2桁であれば、電話番号の局番であり、同じ学校の人でデータを覚えたら、同じ地域の人でハッシュ衝突が発生してしまう。また、ハッシュ値を計算するのに、配列の空き場所を一つ一つ探すような方式では、データ件数に比例した時間がかかり、高速なアルゴリズムとは言えない。このことから、ハッシュ関数には以下のような特徴が必要となる。
- 同じハッシュ値が発生しづらい(一見してデタラメのように見える値)
- 簡単な計算で求まること。
- 同じデータに対し常に、同じハッシュ値が求まること。
ここで改めて、異なるデータでも同じハッシュ値が求まった場合、どうすれば良いのだろうか？
ハッシュ法を簡単なイメージで説明すると、100個の椅子(ハッシュ表)が用意されていて、1クラスの学生が自分の電話番号の末尾2桁(ハッシュ関数)の場所(ハッシュ値)に座るようなもの。自分のイスに座ろうとしたら、同じハッシュ値の人が先に座っていたら、どこに座るべきだろうか？
オープンアドレス法
先の椅子取りゲームの例え話であれば、先に座っている人がいた場合、最も簡単な椅子に座る方法は、隣が空いているか確認して空いていたらそこに座ればいい。
これをプログラムにしてみると、以下のようになる。このハッシュ法は、求まったアドレスの場所にこだわらない方式でオープンアドレス法と呼ばれる。
// オープンアドレス法
// table[] は大域変数で0で初期化されているものとする。
// 配列に電話番号と名前を保存
void entry( int phone , name ) {
int idx = hash_func( phone ) ;
while( table[ idx ].phone != 0 )
idx = (idx + 1) % HASH_SIZE ; // ひとつ後ろの席
} // idx++ でないのは何故？
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 ; // ひとつ後ろの席
} // idx++ でないのは何故？
return NULL ; // 見つからなかった
}
注意：このプログラムは、ハッシュ表すべてにデータが埋まった場合、無限ループとなるので、実際にはもう少し改良が必要である。
この実装方法であれば、ハッシュ表にデータが少ない場合は、ハッシュ値を計算すれば終わり。よって、処理時間のオーダはO(1)となる。しかし、ハッシュ表がほぼ埋まっている状態だと、残りわずかな空き場所を探すようなもの。
文字列のハッシュ値
ここまでで説明した事例は、電話番号をキーとするものであり、余りを求めるだけといったような簡単な計算で、ハッシュ値が求められた。しかし、一般的には文字列といったような名前から、ハッシュ値が欲しいことが普通だろう。
ハッシュ値は、簡単な計算で、見た目デタラメな値が求まればいい。 (ただしく言えば、ハッシュ値の出現確率が極力一様であること)。一見規則性が解らない値として、文字であれば文字コードが考えられる。複数の文字で、これらの文字コードを加えるなどの計算をすれば、 偏りの少ない値を取り出すことができる。
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 ;
}
理解度確認
毎年、冬休み期間中の自主的な理解度確認として、CBT を用いた理解度確認を行っています。今年も実施しますので、下記のシステムにログインし情報構造論では「ソフトウェア」(50分) を受講して下さい。
- https://cbt.kosen-ac.jp/
- 認証には、MS-365 のアカウントとパスワードでログインしてください。
ポート番号とファイアウォールとメール
ポート番号
サーバとなるコンピュータでは、1台のコンピュータで様々なサービスを提供することから、サービスを区別する必要がある。このためにポート番号が使われる。1台毎のコンピュータに割り当てられたIPアドレスを電話番号に例えるなら、ポート番号は内線電話番号に例えることができる。
サーバと通信する場合、サービスを提供するプログラムに応じて標準的なポート番号が決められている。サーバに届いたパケットは、ポート番号に応じてサービスプログラムを起動する。以下の表によく使われるポート番号の一例をあげる。
| ポート番号 | プロトコル | 概要 |
| 20 | ftp | ファイル転送(データ) |
| 21 | ftp | ファイル転送(命令) |
| 22 | ssh | リモート接続(暗号対策あり) |
| 23 | telnet | リモート接続(暗号化なし) |
| 25 | smtp | 電子メール送信 |
| 465 | smtps | 電子メール送信(暗号化) |
| 53 | DNS | ドメインネームサービス |
| 80 | http | Web |
| 443 | https | Web(暗号化) |
| 110 | pop3 | メールダウンロード |
| 995 | pop3s | メールダウンロード(暗号化) |
| 143 | imap | メール閲覧 |
| 993 | imaps | メール閲覧(暗号化) |
| 137,138,139 | netbios | Windows のファイル共有 |
通信パケットには、送信元IPアドレス、送信元ポート番号、送信先IPアドレス、送信先ポート番号の情報がある。
パソコンがサーバと通信する場合は、(1)自分のIPアドレスを送信元IPアドレス、(2)その時に使われていないポート番号をランダムに選び、送信元ポート番号とする。(3)通信相手のIPアドレスと、(4)通信先のサービスのポート番号をセットして、パケットを送付する。サーバは、サービスを要求してきたクライアントの送信先ポート番号をみて、対応するサーバのプログラムが動作する。プログラムの結果を送り返す時は、送信元と送信先のIPアドレス、ポート番号を入替えてパケットを送信する。
1024未満のポート番号(ウェルノウンポート番号)は、サービスを受けとるために用途が決められているので、通常の通信プログラムでは使われない。これ以外のポート番号は、通信の送信元のポート番号として使われ、エフェメラルポート番号と呼ばれる。
ファイアウォール
ネットワークのサービスの中には、組織外に見せたくないものも多い。また、インターネットでは、悪意のあるプログラマが通信して攻撃を加えてくるかもしれない。基本的には個々のサーバのプログラムで、送信元のプログラムのIPアドレスを見て接続を拒否することもできるが、末端のサーバで設定がいい加減だと攻撃をうけてしまうかもしれない。そこで、組織全体でネットワークを守る必要がでてくる。そこでルータなどの機能で、パケットの送信相手のポート番号や、送信元のIPアドレスをみて、パケットを廃棄する場合がある。こういう、ネットワークからの攻撃を防ぐ装置は、ファイアウォール(防火壁)と呼ばれる。
データベースサーバの保護するためにファイアウォールを設置する例を示す。Webサービスを提供するためのデータベースだけど、インターネットから接続されると情報漏洩が発生するかもしれない。そこでデータベースサーバ(mysql)に接続するための3306ポートは、ファイアウォール(ルータ)で組織外からは接続させない。
許可リスト方式と拒否リスト方式
ファイアウォールの設定では、信頼できる人だけを接続させる許可リスト方式と、怪しい人を除外する拒否リスト方式がある。
許可リスト方式は、接続していい相手のIPアドレスや、ポート番号だけをFireWallを通過させる方式。以前はホワイトリスト方式と呼ぶことが多かった。これとは逆に、攻撃をしてきそうな怪しいIPアドレスや、怪しいポート番号のパケットを捨てて接続させない方式は拒否リスト方式とよぶ。以前はブラックリスト方式と呼ぶことが多かった。学校のサーバは、学内への攻撃を防ぐため、ポート番号については http, https など以外の受信は許可リスト方式となっている。
メールが届くまで
電子メールは、非常に迅速にメッセージを相手に届けることができ、そのメッセージを蓄積・加工・編集・転送できる。また、音声や画像といった情報も、複雑な文字情報に置き換えることで、転送できるようになっている。
メールは、利用者のコンピュータに直接届けられるわけではなく、多くの場合はメールを蓄積するメールサーバに送られる。利用者がメールを読む場合、メールサーバから自分の端末に蓄積されたメッセージを読み込み、メッセージを確認する。このメールのやり取りにおいて、メールを送る時、あるいはメールサーバ間でメールを中継するときには、SMTP(Simple Mail Transfer Protocol) が用いられる。一方、メールサーバからメール
を読み出すときには、POP(Post Office Protocol) やIMAP(Internet Message Access Protocol) と呼ばれるプロトコルが用いられる。最近では、IMAPを使ったメールの読み書きをブラウザの中で実行できる WebMail が使われることが増えている。
メールが届くまでの流れは、aさんが”foo@bar.jp“に送る場合、
- aさんは、自分の組織のメールサーバに、SMTPでメールを送る。
- メールサーバは、メールアドレスのコンピュータ名部分”bar.jp“をDNSに問合せ、そのIPアドレスを調べ、そのコンピュータにSMTPでメールを送る。※
- “bar.jp“のメールサーバは、メールアドレスのユーザ名”foo“を取り出し、各ユーザ毎にメールを保存する。
- “foo”さんは、自分宛のメールを確認するために、POPまたはIMAPで自分のメールサーバ”bar.jp”に接続し、ユーザ名,パスワードで認証して自分宛のメールを受け取る。
※上記の手順２で、相手のメールサーバに直接送れない場合は、コンピュータ名のMXレコードをDNSに問合せを行い、そこで得られたメールサーバに中継を依頼する。
$ nslookup -query=MX fukui-nct.ac.jp. Non-authoritative answer: fukui-nct.ac.jp mail exchanger = 10 fukuinct-ac-jp01c.mail.protection.outlook.com.jp
上記手順4で自分のメールを読みだす際のプロトコルで、POPは一般的に、メールサーバから自分のメール閲覧ソフトに自分宛のメールをダウンロードして削除する。このため、様々なコンピュータでメールを読む人には不便となってきた。IMAPでは、メールを読んでも、既読の目印をつけサーバに残しておく方式であり、別のコンピュータでメールを閲覧したい時にもサーバ上のメールを読むことができる。メールをフォルダに分類して保存することもできる。最近利用される Webメール では、自分が利用しているメールサーバまでは Web の機能で接続し、Webサーバとメールサーバにて IMAP を使う。
通常、SMTPでメールを送る際には、ユーザ認証が行われない。このため、ウィルスに感染したプログラムから迷惑メール(spam)を出すことに利用されることが多い。そこで、SMTP送信の前にPOP/IMAP接続しユーザ認証を行った時だけメールを送ることができる、POP before SMTP(or IMAP before SMTP)といった方式をとる場合も多い。
POP, IMAP, SMTPでは、暗号化されない平文が使われることから、通信内容を暗号化して通信する POPS, IMAPS, SMTPS といったプロトコルも使用される。
理解度確認
- メールの送信から受信までの処理を、それに使われるプロトコルを交えて説明せよ。
- Forms による理解度確認
コンパイラと正規表現とBNF記法
コンパイラと言語処理系
2分木の応用の構文木について、この後説明を行うが、構文木を使うコンパイラなどの一般知識を事前に説明しておく。
高級言語で書かれたプログラムを計算機で実行するソフトウェアは、言語処理系と呼ばれる。その実行形式により
- インタプリタ(interpreter:通訳)
- ソースプログラムの意味を解析しながら、その意味に沿った処理を行う
- コンパイラ(compiler:翻訳)
- ソースプログラムから機械語を生成し、実行する際には機械語を実行
- トランスコンパイラ
- ソースから他の言語のソースコードを生成し、それをさらにコンパイルし実行
最初のC++の実装(Cfront)では、C++をトランスレータにかけてC言語を生成し、C言語のコンパイラで動かしていた。
- ソースから他の言語のソースコードを生成し、それをさらにコンパイルし実行
- バイトコードインタプリタ
- ソースからバイトコード(機械語に近いコードを生成)、実行時にはバイトコードの命令に沿った処理を行う
- エミュレーター
- 異なるCPUのコンピュータで、システムの動作や機能を模倣して動かすシステム。
近々の例であれば、AppleのARMベースM1チップで intel CPU の動きを真似て動作させる Rosetta2 がトピック。パソコンで古いファミコンのソフトを動かすといった技術もエミュレータ。- 同じCPUで異なるOSを動かす場合は、CPU仮想化。
- 異なるCPUのコンピュータで、システムの動作や機能を模倣して動かすシステム。
に分けられる。
C言語で機械語が生成されるまで
C言語のプログラムから、機械語の命令が生成されるまでは、以下のような処理が行われる。
一般的にコンパイラの処理というと、ソースコードから機械語を生成するまでの処理を指すが、C言語ではプリプロセッサ処理を含んだり、コンパイラの処理(ソースコードからオブジェクトファイル生成まで)のほかにリンク処理を含んで使われることも多い。
foo.c C言語のソース ↓ プリプロセッサ処理 cpp foo.c(#行の無いC言語のソース) ↓ コンパイラ gcc foo.obj(オブジェクトファイル/中間コード) unix系では foo.o ↓ (+) ← ライブラリ(scanf,printfなどの組み込み関数などをまとめたもの) ↓ リンカ(リンケージエディタ) ld foo.exe
コンパイラの処理
コンパイラが命令を処理する際には、以下の処理が行われる。
- 字句解析(lexical analysys)
文字列を言語要素(token)に分解 - 構文解析(syntax analysys)
tokenの並び順に意味を反映した構造を生成 - 意味解析(semantics analysys)
命令に合わせた中間コードを生成 - 最適化(code optimization)
中間コードを変形して効率よいプログラムに変換 - コード生成(code generation)
実際の命令コード(オブジェクトファイル)として出力
バイトコードインタプリタとは
例年だと説明していなかったけど最近利用されるプログラム言語の特徴を説明。
通常、コンパイラとかインタプリタの説明をすると、Java がコンパイラとか、JavaScript はインタプリタといった説明となる。しかし、最近のこういった言語がどのように処理されるのかは、微妙である。
(( Java の場合 )) foo.java (ソースコード) ↓ Java コンパイラ foo.class (中間コード) ↓ JRE(Java Runtime Engine)の上で 中間コードをインタプリタ方式で実行
あらかじめコンパイルされた中間コードを、JREの上でインタプリタ的に実行するものは、バイトコードインタプリタ方式と呼ぶ。
ただし、JRE でのインタプリタ実行では遅いため、最近では JIT コンパイラ(Just-In-Time Compiler)により、中間コードを機械語に変換してから実行する。
また、JavaScriptなどは(というか最近のインタプリタの殆どPython,PHP,Perl,…は)、一般的にはインタプリタに分類されるが、実行開始時に高級言語でかかれたコードから中間コードを生成し、そのバイトコードをインタプリタ的に動かしている。
しかし、インタプリタは、ソースコードがユーザの所に配布されて実行するので、プログラムの内容が見られてしまう。プログラムの考え方が盗まれてしまう。このため、変数名を短くしたり、空白を除去したり(…部分的に暗号化したり)といった難読化を行うのが一般的である。
トークンと正規表現(字句解析)
字句解析でトークンを表現するために、規定されたパターンの文字列を表現する方法として、正規表現(regular expression)が用いられる。
((正規表現の書き方)) 選言 「abd|acd」は、abd または acd にマッチする。 グループ化 「a(b|c)d」は、真ん中の c|b をグループ化 量化 パターンの後ろに、繰り返し何回を指定 ? 直前パターンが0個か1個 「colou?r」 * 直前パターンが0個以上繰り返す 「go*gle」は、ggle,gogle,google + 直前パターンが1個以上繰り返す 「go+gle」は、gogle,google,gooogle
正規表現は、sed,awk,Perl,PHPといった文字列処理の得意なプログラム言語でも利用できる。こういった言語では、以下のようなパターンを記述できる。
[文字1-文字2...] 文字コード1以上、文字コード2以下 「[0-9]+」012,31415,...数字の列 ^ 行頭にマッチ $ 行末にマッチ ((例)) [a-zA-Z_][a-zA-Z_0-9]* C言語の変数名にマッチする正規表現
構文とバッカス記法
言語の文法(構文)を表現する時、バッカス記法(BNF)が良く使われる。
((バッカス記法)) <表現> ::= <表現1...> | <表現2...> | <表現3...> | ... ;
例えば、加減乗除記号と数字だけの式の場合、以下の様なBNFとなる。
((加減乗除式のバッカス記法))
<加算式> ::= <乗算式> '+' <乗算式> 【要注意】わざと間違っている部分あり
| <乗算式> '-' <乗算式>
| <乗算式>
;
<乗算式> ::= <数字> '*' <乗算式>
| <数字> '/' <乗算式>
| <数字>
;
<数字> ::= [0-9]+
;
上記のバッカス記法には、間違いがある。”1+2+3″を正しく認識できない。どこが間違っているだろうか?
このような構文が与えられた時、”1+23*456″と入力されたものを、“1,+,23,*,456”と区切る処理が、字句解析である。
また、バッカス記法での文法に合わせ、以下のような構文木を生成するのが構文解析である。
＋ ／ ＼ １ ＊ ／ ＼ 23 456
理解度確認
- インタプリタ方式で、処理速度が遅い以外の欠点をあげよ。
- 情報処理技術者試験の正規表現,BNF記法問題にて理解度を確認せよ。
- ソースプログラムがコンパイラにより機械語が生成されるまでの処理について説明せよ。
ドメイン名とDNS
ドメイン名とDNS
インターネットでの通信では、IPプロトコルでコンピュータを指定するが、IPアドレスは無機質で覚えるのが大変であり、コンピュータに名前をつけて利用する。この際に、コンピュータの所属などが分かるようにしたものをドメイン名と呼ぶ。
例えば、電子情報工学科のドメイン名 www.ei.fukui-nct.ac.jp は、ピリオド部分で区切られ、以下のような意味を持つ。
- .jp – 国ドメイン(.uk イギリス,.ch 中国,アメリカは無し)
- .ac – 種別ドメイン(.co.jp,.com:会社,.ne.jp,net:ネットワーク系)
- fukui-nct – 組織ドメイン
- .ei. – サブドメイン(組織内が細分化されている場合)
- www. – ホスト名※
このような省略されていない、対象となるコンピュータを指定するためのドメイン名は、FQDN(Fully Qualified Domain Name)と呼ばれる。FQDNでの名前を ホスト名※ と呼ぶことも多い。
ただしアメリカでは、国ドメインを一般的に使わない※。また最近では、世界的な企業では国ドメインが意味をなさないので、アメリカ以外でも .com や .net といった、汎用トップレベルドメイン(gTLD)が使われる。様々なサービスを展開している企業では、組織種別が意味をなさないため、toyota.jp といった種別ドメインがないドメイン名も増えてきた。高専機構のドメイン名 kosen-ac.jp も、”kosen-ac” が高専機構の組織ドメイン名なので注意。
以下に、主要な組織ドメイン・国ドメインをあげる。
|
※はgTLD |
DNSのしくみ
DNSは、Domain Name Service であり、コンピュータ名(ドメイン名)から、IPアドレスを調べるサービスで、ポート番号53,UDPを使っている。
インターネットに接続する際には、最も身近なDNS※の情報が与えられ、ユーザがコンピュータ名を問い合わせると、身近なDNSがコンピュータのIPアドレスを返してくれる。この際に、検索結果はキャッシュとして一定期間保存される。身近なDNSがそのコンピュータ名を知らない場合は、上位のDNSに問い合わせを行い、DNSルートサーバもコンピュータ名をキャッシュしていない場合は、管理元の組織のDNSに問い合わせが行われる。このようにすることで特定のDNSサーバに問い合わせが集中しないようになっている(負荷分散)。 DNSサーバの情報は DHCP サーバからIPアドレスなどと一緒に取得することができる。
DNSと正引きと逆引き
DNSの使い方としては、一般的な使い方は、ドメイン名からIPアドレスを調べる正引きが多い。ブラウザは http://www.fukui-nct.ac.jp/ というURLが与えられたら、DNSに www.fukui-nct.ac.jp を問い合わせ、104.215.53.205 の結果が得られることで、http://104.215.53.205/ のコンピュータに接続を試みる。
これとは逆に、サーバ側では接続してきた相手のコンピュータが信頼できる相手か調べたい時がある。この時には IPアドレスからドメイン名を調べる逆引きを行う。これにより、IP アドレスをきちんと管理している組織であれば、ドメイン名が分かるのでどの組織から接続されているのか確認ができる。
DNSの情報を調べるためのコマンドは、nslookup を用いる。(詳細は以前の講義資料で確認)
DNSと様々な情報
DNS では、様々な情報が取得できる。IPアドレス以外にも、メールを送ってもらうサーバのIPアドレス(MXレコード)なども取得できる。
((( 正引きの例 ))) $ nslookup www.google.com Server: 172.31.208.1 Address: 172.31.208.1#53 Non-authoritative answer: Name: www.google.com Address: 142.250.206.228 # 調べる度に異なる値が返ってくるかも Name: www.google.com Address: 2404:6800:400a:804::2004 ((( 逆引きの例 ))) $ nslookup 142.250.206.228 228.206.250.142.in-addr.arpa name = kix06s10-in-f4.1e100.net. # 正引きと逆引きが一致していない例 Authoritative answers can be found from: ((( MX レコードを調べる例 ))) $ nslookup -query=MX fukui-nct.ac.jp # MXレコード = そのドメイン宛のメールはどのコンピュータに送ればいい？ Non-authoritative answer: fukui-nct.ac.jp mail exchanger = 10 fukuinct-ac-jp01c.mail.protection.outlook.com. ((( AAAA レコードを調べる例 ))) $ nslookup -query=AAAA www.google.com # AAAAレコード = IPv6アドレスを指定した正引き Non-authoritative answer: Name: www.google.com Address: 2404:6800:400a:813::2004
DNSとセキュリティ
DNSは、コンピュータ名とIPアドレスを対応付けるものであり、これには正引き(コンピュータ名からIPアドレスを求める)と、逆引き(IPアドレスからコンピュータ名を求める)がある。セキュリティ対策が厳しい場所では、
- 正引きを使うことで、特定の組織のドメイン名を持つコンピュータからのアクセスを許可/禁止する。(例:国ドメイン.xxからは接続拒否)
- 正引きで、コンピュータ名が登録されている所からのみ許可する。(例:組織ドメイン.fukui-nct.ac.jpからは接続許可)
- IPアドレスから逆引きして求めたコンピュータ名をさらに正引きして同じIPアドレスが求まるかを確認
といった対策を行う。
- DNSのドメイン名は、当初は最初に申請した人に割り当てられる。このため、nintendo.com といったドメイン名を、関係ない人が取得するといったトラブルがあった。(サイバースクワッティング)
- DNSを用いたクラッキングでは、ウィルスに感染させたパソコンに偽物のIPアドレスを教えることで、偽装した別コンピュータに誘導し個人情報を盗む手口がある。(DNSポイズニング)
- 他にもウィルスに感染させた大量のパソコンから、同時にルートサーバに大量のDNSの問合せを送ることで、処理能力を低下させると、インターネット全体でDNS参照ができなくなる攻撃もある。(DNSルートサーバへの分散DoSアタック)
- DNSは、他のコンピュータに接続するための重要な情報だが、独裁国家などでは国にとって不都合な情報が得られるドメイン名のIPアドレスを改ざんしアクセスできないようにすることもある。このため、Google 社では 覚えやすい 8.8.8.8 という IPアドレスの DNS サーバを提供している。この 8.8.8.8 は、DNS の返答速度も速いことから、ブラウザの表示速度を高速化するために自分のPCに設定する人も多い。
データべースの設計と正規形
昨年度までの試験問題を例に解説を行い、その後、データベースの設計において、重要な正規形についての説明の導入。
正規形
データベースにおいて、様々な不整合を防ぐために正しい設計が必要であることを 改めて説明し、それには正規形としての条件を満たしている必要があることを説明する。一般的に不整合が発生しないためには、以下の第1正規形、第2正規形、第3正規形を満たすように表を分ければよい。
第一正規形は、すべての要素が原子値である条件を満たせばいい。 要素の中が複数の項目であったり表形式のデータがあると、 表構造のリレーショナルデータベースにはできない。
- 中央省庁のデータ表記を統一：河野太郎行政・規制改革担当相のTweet
データベースと直接関係しないけど、データは原子値じゃないと困るというお話。 - 雑談 正しいデータとして扱えるドキュメントとは…
キーの説明：超キー(スーパーキー)とは、データベースで１つのデータを 選び出すために必要なデータ項目であり、複数の項目で１データを指定 できる場合もある。
候補キーとは、必要最小限の項目となっているものを指す。 １項目が抜けても選別できなくなるようであれば、候補キーとは言わない。 主キーとは、候補キーのなかで管理の都合上便利なもの。
データ項目の値が決まると、他のデータ項目が自動的に決まるものは、 従属関係があるという。
 |
 |
| 第1正規化 | 第2正規化 |
第二正規形は、部分従属がなく、すべての非キーデータ項目が、候補キーに 完全従属する場合をいう。
- 完全従属とは、候補キーを構成する全てのデータ項目に、非キーデータ項目が従属していること。
- 部分従属とは、候補キーを構成するデータ項目の一部のデータ項目に、非キー項目が従属していること。
この例において、単価は商品が決まれば自動的に求まる情報。 (単価が日々変化することはないという条件で…) これは、部分従属となる。他に部分従属となっている属性は何か？
- 推移従属性とは、データ項目でA→B→Cと、次々と値が求められる関係を指す。
第三正規形とは、 候補キー以外の非キーデータ項目は、候補キーに完全従属し、 かつどの候補キーにも推移従属しない関係をいう。
 |
| 第3正規化 |
上記の例では、単価と個数が決まれば、金額が求まる推移従属の関係が含まれている。
おまけ：BC正規形,第4,5正規形
この他にも、 さらに非キーからキーに関数従属性がある場合にそれを取り除く、 ボイスコッド正規形(BC正規化)。 「対称性のある多値従属性(キーを決めると複数データが該当)」を分解して得られる第4正規形や、 「元になるテーブルの結合従属性を維持して分解することにより得られる第5正規形などがある。
トランスポート層・TCPとUDP
前回の授業で説明が不足していた DHCP についての説明
DHCP
前回の IP では、異なるサブネットを繋ぐ役割としての Internet Protocol (IP) について説明をした。IP での通信では、IPアドレスが必要だが、正しく接続ができるためには、(1)IPアドレス、(2)サブネットマスク、(3)ゲートウェイアドレス が必要となる。しかし、この情報は初心者には設定が難しいし、IPアドレスが他の利用者と重複させないためには、きちんとした管理が必要となる。
この時に使われるのが DHCP(Dynamic Host Configuration Protocol) であり、通常のパソコンは、IPの自動設定としておけば、DHCP を用いて前述の(1),(2),(3) の情報が自動で設定される。DHCP機能は、一般的にルータや WiFi の AP(アクセスポイント)の中に組み込まれている。
DHCPサーバには、使用可能なIPアドレスを登録しておく。利用者が DHCP クライアントとして接続する際には、ブロードキャストパケットを使い、同じサブネット内に DHCP リクエストを送る。このリクエストを DHCPサーバが受信したら、サーバはクライアントに向かって、貸し出し用の IP アドレスの１つをクライアントに提供する(サブネットマスクやゲートウェイなども提供)。
データ通信ではノイズなどの影響で通信に失敗することがある。これらを補うためのTCPがある。またTCPの通信の欠点を補うUDPがある。この授業では、TCPとUDPによるトランスポート層の説明を行う。
TCP
TCP(Transmission Control Protocol/トランスミッションコントロールプロトコル)では、分割されたパケットを元の順序に組み上げたり、パケットが途中で消えた場合の再送などの処理を行う。この機能により確実に相手に送る機能が実現されている。
3way ハンドシェーク
TCPの通信では、最初に相互に通信が可能かを確認するハンドシェークが行われる。パケットには、SYN,ACK,FINといった種別を表すフラグがついており、SYNは接続確立の要求を表す。ACKは了解を表す。FINは切断要求を表す。通信開始の時には、(1)通信OK?、(2)OKだよ,そっちもOK?、(3)OKだよ! といった3つの通信パケットで確認してから通信を行う。この最初のやり取りを3way ハンドシェークという。
- SYN flood攻撃 – 3wayハンドシェークは、この後に送られてくるパケットを並び替えるためのメモリを準備などが必要となる。このため通信ルールを無視して相手にSYNパケットだけを大量に送ると相手はムダな準備作業により他の通信が困難になる場合がある。
SEQ番号,ACK番号
通信パケットには、SEQ番号(シーケンス番号/32bit)とACK番号(アクノリッジ番号/32bit)という情報がついており、送信元はACK番号を確認することで、どのパケットが正しく届いたのかを認識できる。3wayハンドシェーク時には、相手のSEQ番号に1を加えたACK番号をつけてパケットを返送することで通信が始められることが確認できる。実際のデータを送信する際には、受け取ったデータ長をSEQ番号に加えた値を、ACK番号にして受信に成功したことを相手に伝える。これにより、小分けにされたパケットで次に何を送れば良いのか判別できる。
(Acknowledge = 承認する)
通信で、パケット分割して送って、その一つ毎の返答を待つと、通信の待ち時間が増えてしまう。このため、相手が受け取り可能であれば、一度に前回の2倍のパケットを返信を待たずに送る。(ウィンドウサイズの拡大)
チェックサムとタイムアウト
通信では、送る途中でデータにノイズが混入したり、パケットが消失することがある。このため、パケットにはパケットのチェックサム(バイトデータを加算した値)を付けて送り、受信時に比較してノイズ混入でデータが壊れていないかを確認する。こういった際には、パケットが正しく届かない。パケットが消失したりして、通信相手からの返送が届かないで一定の待ち時間が経過することをタイムアウトと呼ぶ。この時、返信パケットにはデータのSEQ番号とACK番号の情報があるため、受け取りに失敗したパケットが判別できるので、送り側は失敗したパケットを再送する。
受け取り側は、同じくSEQ番号やACK番号を元にパケットの順番を正しく並べ戻すことができる。
TCP FINパケット
通信を切断する場合には、相互に切断して良いか確認する4回の通信で終了する。
UDP
TCPによる通信は、相手側からの受け取った返事を待ちながら通信を行う。このため、通信にかかる時間を要する。また、複数の利用者に一斉にデータをばらまくブロードキャスト通信では、個別のパケット欠落を修復しようとすると、処理が複雑になる。
これらの対応策として、UDP(User Datagram Protocol)がある。これは、TCP通信でのパケット分割や再送処理を行わない極めて単純な送信方法である。このため、相手側に正しくデータが送られる保証はない。確実に相手に送る必要があれば、確認や再送は上位プロトコルの責任となる。
UDP通信は返信を待つ必要がないので、動画・音声配信などのリアルタイム性が求められる通信でよく使われる。UDPは正しく通信ができずパケットが途絶えても、一時的に動画が止まるなり音声が止まるといったように、問題が少ないような場合に有用となる。
ICMP/ping
IPプロトコルのプロトコルの１つとして ICMP (Internet Control Message Protocol) がある。このプロトコルは、ネットワーク機器(ノード)の間で、通信の確認をするためのもので、ping コマンドや traceroute コマンドで使われる。
基本的に、ICMPパケットを相手コンピュータに送り、返事が返ってくるかを確認する。ping や traceroute は、返事が返ってくるまでの時間や、パケットをいくつ送っていくつ返ってきた…などの情報を表示することができ、相手コンピュータまでの通信路が正常かどうかが判断できる。
$ ping www.google.co.jp PING www.google.co.jp (172.217.25.163) 56(84) バイトのデータ 64 バイト応答 送信元 syd09s13-in-f3.1e100.net (172.217.25.163): icmp_seq=1 ttl=115 時間=7.85ミリ秒 64 バイト応答 送信元 syd09s13-in-f3.1e100.net (172.217.25.163): icmp_seq=2 ttl=115 時間=8.02ミリ秒 ^C # 途中で強制終了させるために Ctrl-C で止める ]$ traceroute www.google.co.jp traceroute to www.google.co.jp (172.217.25.163), 30 hops max, 60 byte packets 1 airstation.ei.fukui-nct.ac.jp (192.168.2.1) 0.355 ms 0.529 ms 0.549 ms (略) 9 108.170.243.33 (108.170.243.33) 8.245 ms 108.170.243.65 (108.170.243.65) 6.893 ms 6.936 ms 10 72.14.239.25 (72.14.239.25) 6.899 ms 7.125 ms 72.14.238.23 (72.14.238.23) 7.140 ms 11 syd09s13-in-f163.1e100.net (172.217.25.163) 7.014 ms 7.007 ms 6.961 ms
トランスポート層
OSI参照モデルでは、TCPプロトコルとUDPプロトコルをあわせてトランスポート層と呼び、TCP+UDPとネットワーク層のIPプロトコルでの通信が、今日のインターネット通信の基本プロトコルとなっており、総称して TCP/IPとかインターネット・プロトコル・スイート と呼ぶ。(suite=”一連のものや一緒に機能するものの集まり”/sweetじゃない)