ホーム » スタッフ (ページ 2)
「スタッフ」カテゴリーアーカイブ
情報構造論ガイダンス2024
基本的なガイダンス
情報構造論のシラバスを、ここに示す。プログラムを作成する上で、どのような考え方で作れば処理速度が速いのかを議論する。基本的に、4回のテストのたびに、レポート課題を実施する。各テスト毎の評価は、テスト素点と、「テスト素点×60%+レポート評価×40%」の良い方とする。テストに自信のない人は、レポート課題をきちんと提出すること。
プログラムを評価する3つのポイント
まずは以下を読む前に、質問。
- あなたが”良い”プログラムを作るために何を考えて作りますか? ※1
- ここまでの段階で3つの要点を考えメモしてください。
具体的な言葉で要点を考えると、いろいろなものがでてくるだろうが、端的なポイントにまとめると、次の3つに分類できるはずである。
- プログラムの速度
- プログラムのわかり易さ
- メモリの使用量
プログラムを作る場合、この3要素がトレードオフの関係にある。プログラムの速度を優先すると、プログラムが分かり難くなったり、メモリを大量浪費するものだったりする。
メモリの使用量の影響
メモリを大量に使用すると、どういった影響がでるのか? OSの機能を知らないと、メモリ(主記憶)を使い果たしたら、プログラムが動かないと思うかもしれないけど、最近のOSは仮想メモリ機能があるため、主記憶がメモリが足りなければ待機状態のプロセスのメモリを補助記憶に保存することで、プログラムを動かすことはできる。(仮想記憶)
しかし、プロセスが切り替わる度に、補助記憶への読み書きが発生するため、処理性能は低下する。(スワッピング)
int 型のメモリ使用量は?
int 型は、プログラムで扱う一般的な整数を扱うのに十分なデータ型。
32bit の0/1情報の組み合わせで、232通りの情報が表現でき、負の数も扱いたいことから2の補数表現を用いることで、-231~0~231-1 の範囲を扱うことができる。231 = 2×210×210×210 ≒ 2×10003
32bit = 4byte
ソフトウェアとアルゴリズムとプログラム
用語として、ソフトウェア、アルゴリズム、プログラムという表現があるが、この違いは何か?
- アルゴリズム – 計算手順の考え方。
- プログラム – アルゴリズムを特定のプログラム言語によって記述したもの。
- ソフトウェア – プログラムと、その処理に必要なデータ。
(日本語を変換するプログラムは、日本語の辞書データが無いと動かない/役に立たない) - パラダイム – プログラムをどう表現すると分かりやすいか?
トレードオフ関係をプログラムで確認
例えば、配列の中から、目的データを探すプログラムの場合、最も簡単なプログラムは以下の方法であろう。
// ((case-1)) // 単純サーチ O(N) #define SIZE 1024 int main() { int a[ SIZE ] = { 52 , 14 , 82 , 62 , 15 } ; // 配列 int size = 5 ; // 実際のデータ数(Nとする) int key = 62 ; // 探すデータ for( int i = 0 ; i < size ; i++ ) // 先頭から1つづつ比較、シンプル if ( a[i] == key ) { printf( "Find %d¥n" , key ) ; break ; } } }
import java.util.*; public class Main { public static void main(String[] args) throws Exception { int a[] = { 52 , 14 , 82 , 62 , 15 } ; int key = 62 ; for( int i = 0 ; i < a.length ; i++ ) { if ( a[i] == key ) { System.out.println( "Find " + key ) ; break ; } } } } // import java.util.Arrays; // こういった正当なJavaのプログラムでは、 // public class Main { // データ件数が大きくなった時の挙動がわからない // public static void main( String[] args ) { // Integer a[] = { // 52 , 14 , 82 , 62 , 15 // Integer型 int 型は何が違うの? // } ; // if ( Arrays.asList( a ).contains( 62 ) ) { // System.out.println("配列内に値が存在しています。"); // } // } // }
しかし、もっと早く探したいのであれば、2分探索法を用いるだろう。でも、このプログラムは、case-1 のプログラムよりは分かり難い。(速度⇔わかり易さ)
// ((case-2)) // 2分探索法 O(log N) // 速いけど、プログラムは分かりにくく(複雑に)なった int main() { int a[] = { 14 , 15 , 52 , 62 , 82 // データはあらかじめ昇順に並べておく } ; int L=0 , R= 5 ; while( L != R ) { int M = (L + R) / 2 ; if ( a[M] == key ) break ; else if ( a[M] < key ) L = M + 1 ; else R = M ; } }
import java.util.*; public class Main { public static void main(String[] args) throws Exception { int a[] = { 14 , 15 , 52 , 62 , 82 // データはあらかじめ昇順に並べておく } ; int key = 62 ; int L = 0 ; int R = a.length ; while( L != R ) { int M = (L + R) / 2 ; if ( a[M] == key ) break ; else if ( a[M] < key ) L = M + 1 ; else R = M ; } } }
でももっと速いプログラムとしたければ、大量のメモリを使えば一発でデータを探せる。(速度⇔メモリ使用量)
// ((case-3)) // 添字がデータ O(1) // 探すデータが電話番号 272925 のような 6 桁ならば、データを以下の様に保存すればいい。 int a[ 1000000 ] ; a[ 272925 ] = 272925 ; : // データを探したければ a[ 電話番号 ] で探せばいい printf( "%d\n" , a[ 621111 ] ) ; // 処理速度はクソ速いけど、メモリは大量消費
良いプログラムを作るとは
プログラムを作る時には、メモリが大量に使えるのなら、速いものを使えばいい。だけど実際には、そのシステムには限られた予算があるだろう。
実際には、限られた予算からメモリやCPUが決まり、その会社の人員やら経験やらでプログラム開発に使える時間がきまる。プログラムをデザインするとは、限られた条件の中で、適切な速度のコンピュータ、適切な量のメモリでコンピュータを用意し、限られた納期の中でシステムを完成させることである。
皆さんも、ゲームを買った時、処理速度が遅くてキャラクターがカクカク動いたら幻滅するでしょ?ゲームがバグですぐに変な動きしたらキレるでしょ!(参考) 発売日の予定どおりに買えなかったらさみしいでしょ!!プログラムがでかすぎてローディングに時間がかかったら、寝ちゃうでしょ!!!
サーバ移行作業で2015年以前のテスト問題が消えた
サーバの移行作業を行ったけど、その際に自分のホームディレクトリ配下に置いてあった、過去のテスト問題のデータが消えた。エビデンス用に学校で保管してあるデータからコピーして、2015年以降は復活できたけど。
hilite=nslookup/// って何?
なにげなく、WordPress な Web の accesslog を見ていたら、下記のようなログが大量(8000件/日越え)に残ってる。
3.224.220.101 - - [07/Mar/2024:09:17:32 +0900] "GET /2019/09/27/hoge-meta/?hilite=nslookup//////////...(略)...//// HTTP/1.1" 200 19136 "-" "Mozilla/5.0 (Macintosh; Intel Mac OS X 10_10_1) AppleWebKit/600.2.5 (KHTML, like Gecko) Version/8.0.2 Safari/600.2.5 (Amazonbot/0.1; +https://developer.amazon.com/support/amazonbot)"
hilite=… は、WordPress の検索プラグインが使うパラメータ WordPressで記事の特定部分を目立たせる際のパラメータ。大量の////が並ぶので、プラグインへのバッファオーバーフロー攻撃かと思うけど、ググってもそういった類の報告は見つからない。
amazonbot というのがユーザエージェントに残ってるし、確認するとどのユーザエージェントも amazonbot 。IPアドレスも散らばっているけど、逆引きすると amazonbot のアドレス。クローラーが暴走してるのかな。意味不明で不気味。
(追記)
確認を続けると、数日前の LOG だと、/// の長さがちょっと短い。さらにさかのぼっていくと次第に短くなっている。hilite=nslookup が出てきた最初は、下記の通り。この段階では “/” はナシだな。
xx.xx.xx.xx - - [29/Feb/2024:07:00:01 +0900] "GET /2023/11/16/network-layer-ip-address-2023/?hilite=nslookup HTTP/1.1" 200 19165 "-" "Mozilla/5.0 (compatible; AhrefsBot/7.0; +http://ahrefs.com/robot/)" xx.xx.xx.xx - - [29/Feb/2024:12:42:46 +0900] "GET /2023/11/16/network-layer-ip-address-2023/?hilite=nslookup HTTP/1.1" 200 70965 "-" "ICC-Crawler/2.0 (Mozilla-compatible; ; http://ucri.nict.go.jp/en/icccrawler.html)"
該当記事をみると、講義録の nslookup を目立たせるために、?hilite=nslookup で自分の記事にリンク張ってる。こんなもんで、変なアクセスが増えてるの?どっちにしろ、クローラーのバグっぽいな。
となると、amazonbot のクローラー禁止するか。
((( robots.txt ))) User-agent: Amazonbot Disallow: /
2023年度 情報構造論 講義録
- 情報構造論ガイダンス2023
- 繰り返し処理と処理時間の見積もり
- 再帰呼び出しと処理時間の見積もり
- ポインタ処理
- ポインタとメモリの使用効率
- malloc()とfree()
- 様々なデータの覚え方のレポート課題
- fgetsではみ出たら
- リスト構造の導入
- リスト処理
- リストへの追加処理
- スタックと待ち行列
- 集合とリスト処理
- ランダムアクセス・シーケンシャルアクセスから双方向リスト
- 双方向リストとdeque
- 2分探索木
- AVL木と2分ヒープ
- 意思決定木と演算子
- 2分木による構文木とデータベースとB木
- コンパイラと正規表現とBNF記法
- ハッシュ法
- チェイン法と共有のあるデータの問題
- 参照カウンタの問題とガベージコレクタ
- 関数ポインタ
授業アンケート 2023 後期
情報工学演習(2EI)
84.3 ポイントと高い評価であった。プログラミングコンテストを用いた演習内容の発表では、こちらが想定してた難易度の高い問題について説明したものが少なく、来年度は制約などを設けたいと思った。
情報ネットワーク基礎(3EI)
情報構造論(4EI)
データベース(5EI)
関数ポインタ
関数ポインタとコールバック関数
JavaScript のプログラムで、以下のようなコーディングがよく使われる。このプログラムでは、3と4を加えた結果が出てくるが、関数の引数の中に関数宣言で使われるfunctionキーワードが出てきているが、この意味を正しく理解しているだろうか?
このような (function()…)は、無名関数と呼ばれている。(=>を使った書き方はアロー関数と呼ばれている) これは「関数を引数として渡す機能」と、「一度しか使わないような関数にいちいち名前を付けないで関数を使うための機能」であり、このような機能は、関数を引数で渡す機能はC言語では関数ポインタと呼ばれたり、新しいプログラム言語では一般的にラムダ式などと呼ばれる。
// JavaScriptの無名関数の例 3+4=7 を表示 console.log( (function( x , y ) { return x + y ; })( 3 , 4 ) ) ; // 無名関数 console.log( ((x,y) => { return x + y ; })( 3 , 4 ) ) ; // アロー関数
C言語の関数ポインタの仕組みを理解するために、以下のプログラムを示す。
int add( int x , int y ) { return x + y ; } int mul( int x , int y ) { return x * y ; } void main() { int (*f)( int , int ) ; // fは2つのintを引数とする関数へのポインタ f = add ; // f = add( ... ) ; ではないことに注意 printf( "%d¥n" , (*f)( 3 , 4 ) ) ; // 3+4=7 // f( 3 , 4 ) と書いてもいい f = mul ; printf( "%d¥n" , (*f)( 3 , 4 ) ) ; // 3*4=12 }
このプログラムでは、関数ポインタの変数 f を定義している。「 int (*f)( int , int ) ; 」 は、“int型の引数を2つ持つ、返り値がint型の関数”へのポインタであり、「 f = add ; 」では、f に加算する関数addを覚えている。add に実引数を渡す()がないことに注目。C言語であれば、関数ポインタ変数 f には、関数 add の機械語の先頭番地が代入される。
そして、「 (*f)( 3 , 4 ) ; 」により、実引数を3,4にて f の指し示す add を呼び出し、7 が答えとして求まる。
こういう、関数に「自分で作った関数ポインタ」を渡し、その相手側の関数の中で自分で作った関数を呼び出してもらうテクニックは、コールバックとも呼ばれる。コールバック関数を使うC言語の関数で分かり易い物は、クイックソートを行う qsort() 関数だろう。qsort 関数は、引数にデータを比較するための関数を渡すことで、様々な型のデータの並び替えができる。
#include <stdio.h> #include <stdlib.h> // 整数を比較するコールバック関数 int cmp_int( int* a , int* b ) { return *a - *b ; } // 実数を比較するコールバック関数 int cmp_double( double* a , double* b ) { double ans = *a - *b ; if ( ans == 0.0 ) return 0 ; else if ( ans > 0.0 ) return 1 ; else return -1 ; } // ソート対象の配列 int array_int[ 5 ] = { 123 , 23 , 45 , 11 , 53 } ; double array_double[ 4 ] = { 1.23 , 12.3 , 32.1 , 3.21 } ; void main() { // 整数配列をソート qsort( array_int , 5 , sizeof( int ) , (int(*)(const void*,const void*))cmp_int ) ; // ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~この分かりにくい型キャストが必要なのがC言語の面倒な所 for( int i = 0 ; i < 5 ; i++ ) printf( "%d\n" , array_int[ i ] ) ; // 実数配列をソート qsort( array_double , 4 , sizeof( double ) , (int(*)(const void*,const void*))cmp_double ) ; // ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ for( int i = 0 ; i < 5 ; i++ ) printf( "%f\n" , array_double[ i ] ) ; }
無名関数
コールバック関数を使っていると、データを比較するだけの関数とか簡単な短い処理が使われることが多い。こういった処理を実際に使われる処理と離れた別の場所に記述すると、プログラムが読みづらくなる。この場合には、その場で関数の名前を持たない関数(無名関数)を使用する。(C++の無名関数機能は、最近のC++の文法なのでテストには出さない)
void main() { int (*f)( int , int ) ; // fは2つのintを引数とする関数へのポインタ f = []( int x , int y ) { return x + y ; } ; // add を無名関数化 printf( "%d¥n" , (*f)( 3 , 4 ) ) ; // 3+4=7 // mul を無名関数にしてすぐに呼び出す3*4=12 printf( "%d¥n" , []( int x , int y ) { return x * y ; }( 3 , 4 ) ) ; // メモ:C++11では、ラムダ式=関数オブジェクト // C++14以降は、変数キャプチャなどの機能が追加されている。 }
C++の変数キャプチャとJavaScriptのクロージャ
JavaScript のクロージャ
JavaScriptにおいて、関数オブジェクトの中で、その周囲(レキシカル環境)の局所変数を参照できる機能をクロージャと呼ぶ。クロージャを使うことでグローバルな変数や関数の多用を押さえ、カプセル化ができることから、保守性が高まる。
// JavaScriptにおけるクロージャ function foo() { let a = 12 ; // 局所変数 console.log( (function( x , y ) { return a + x + y ; // 無名関数の外側の局所変数aを参照できる })( 3 , 4 ) ) ; } foo() ;C++の変数キャプチャ
C++でも無名関数などでクロージャと同様の処理を書くことができるようにするために変数キャプチャという機能がC++14以降で使うことができる。
// C++のラムダ関数における変数キャプチャ void main() { int a = 12 ; printf( "%d\n" , [a]( int x , int y ) { // 変数キャプチャ[a]の部分 return a + x + y ; // 局所変数aをラムダ関数内で参照できる。 }( 3 , 4 ) ) ; return 0 ; }
セキュリティ対策
セキュリティ
バッファオーバーフロー
クラッカーがサーバを攻撃する場合、サーバ上のプログラムの脆弱性を利用する。
サーバプログラムの脆弱性を利用する最も典型的な攻撃方法には、バッファオーバーフローがある。
こういった問題が含まれるアプリケーションは危険であり、こういった脆弱性が見つかったらプログラムの更新が重要である。
マルウェア
ウィルスとは、パソコン利用者の上で動く、感染能力のある悪意のあるプログラム。機械語で書かれたものや、オフィスソフトのマクロ機能で動くものもある。パソコン内の情報を利用して、ウィルス付きメールを自動的に送ることが多い。(メールソフトを使うなど、人の操作が必要なもの)
ウィルスは元々、愉快犯によるものが一般的であったが、感染したパソコンのファイルを暗号化し、暗号化を復元するために、ネットバンキングへのお金の振り込みを要求(身代金=ransom)するようなランサムウェアが増えている。
ウォームとは、脆弱性のあるネットワークプログラムに、バッファオーバーフローを引き起こすようなデータを送りつけて、ウィルスを送りつけたり、そのコンピュータを踏み台にしてネットワークを利用した攻撃をさらに行うもの。(ネットワークを介して悪意のあるプログラムを起動させるもの)
通常、インターネットからの攻撃を防ぐために、各組織ではFireWall(後述)を設置している。一方、FireWallの内側では、防御されていることから内部のコンピュータからの攻撃に甘く、無防備であることが多い。そこで、FireWall の内側のコンピュータに、メールなどの添付ファイルでマルウェアを送付・感染させることで、FireWall内で被害が拡大することもある。
このような、FireWall 内部での感染・被害拡大を狙ったマルウェアは、トロイの木馬型と呼ばれる。
ネットワークを介した攻撃では、攻撃対象のコンピュータを乱数で得られたIPアドレスや、そのアドレスを1つづつ増やしながら攻撃を行うことが多い。こういった攻撃は絨毯攻撃と呼ぶ。
ボットとはロボットを略した単語で、ウォームの中で「外部からの命令で動くもの」を指す。マルウェアのボットの中には感染しても表面上は何もせず、クラッカーの動かすインターネットの掲示板などを監視し、そこに書かれた命令を見て spam 送信や、DoS攻撃を行うものがある。
DoS攻撃(Denial of Service attack) – サーバなどに大量のデータを送りつけたりすることで、サーバがその処理に手間取り、他の利用者のサービスに悪影響を引き起こさせる攻撃。ボットからのDoS攻撃は、インターネットの様々なIPアドレスから攻撃を受けるためFireWallで防ぐことも困難である。分散DoS攻撃(Distributed DoS Attack)
最近では、ウィルスやウォームの区別が難しいため、マルウェアと呼ぶ。
ファイアウォール
サーバで動かしているプログラムにバッファオーバーフローのような不備が残っていて、全世界のどこからでもこういった不備があるプログラムに簡単に接続できたとしたら、極めて危険である。
サーバで動くプログラムは、接続するためのポート番号が決まっているので、相手のコンピュータのIPアドレスが分かったら攻撃を仕掛けてくるかもしれない。
FireWall は、これらの接続をできなくするための方法で、例えば学内のWebサーバへの攻撃を防ぎたいのなら、ルータで「宛先ポート番号が80のパケットは廃棄」といった設定をすればよい。また、危険な攻撃を加えてくるコンピュータのIPアドレスがわかっている場合は、「送信元IPアドレスXX.XX.XX.XXのパケットは廃棄」という設定をすればよい。こういった、ポート番号やIPアドレスを見てパケットを遮断するルータは、FireWall(防火壁)と呼ばれる。
よくある設定であれば、ポート番号23(telnet),137,139(Windows ファイル共有),513(リモートデスクトップ)を禁止など(拒否リスト型/ブラックリスト型)、基本は全面禁止だけどポート番号22(ssh)は許可(許可リスト型/ホワイトリスト型)など。
セキュリティ対策
- OSの更新・インストールアプリケーションの更新
バッファオーバーフローのような脆弱性が無いようにソフトウェアを更新することが重要。
Windows で、インストールされているソフトの更新では、winget が便利!!
- 不審なメールは開かない
添付ファイルにマルウェアがしかけられている可能性。リンクや画像ファイルを開くと、実際に使われているメールアドレスとして迷惑メールが増える可能性がある。 - 危険なWebサイトをアクセスしない
OSやブラウザの脆弱性から、マルウェア被害の可能性。 - パソコンで不要なサービスを動かさない
ファイル共有や、リモート接続のサーバを不用意に動かさない。 - ウィルス対策ソフトをインストール&更新
ウィルス対策ソフトは、新しく発生したマルウェアの命令などのパターンを保存しておき、同じパターンのものをマルウェアとして判定する。- マルウェアは日々新しいものが作られるため、ウィルス対策ソフトのメーカーから、常に新しいマルウェアのパターンをダウンロード&更新が重要。
- OSの脆弱性が見つかった場合、ウィルス対策ソフトのメーカーがマルウェアパターンを登録する前にマルウェアが届く場合がある。ゼロディ攻撃
- 特定の企業を攻撃する場合は、その企業専用のウィルスを作る場合もある。このためマルウェアパターンが無いため、ウィルス感染の可能性がある。標的型攻撃
- 最近では、ブラウザによるWebアクセスからの感染を防ぐために危険なURLへのアクセスを監視したり、危険なIPアドレス・ポート番号へのアクセスを監視する機能も含まれている。パーソナルファイアウォール機能
- このパソコンは重要な情報が入っていないから、ウィルスに感染しても放置するのは危険。他のコンピュータを攻撃する踏み台、DoS攻撃のボット、トロイの木馬となって危険の元となる。
一般的に、Apple社のiPhone iOS では、ウィルス対策ソフトは不要である。これは、App Store でアプリを公開するためには、プログラムのソースコードを提出した上での審査があり、デバイスも、App Store 以外からのアプリをインストールできないため、マルウェアのインストールがほぼ不可能なためである。一方、Google 社の Android は、アプリの審査が甘く、Google Play アプリ以外からのソフトのインストールも可能であり、ウィルス対策ソフトが必要である。
理解度確認
- Formsによる理解度確認テスト
- 標的型攻撃メールがウィルス対策ソフトでは防ぐことが難しい理由を述べよ。
- ファイアウォールでは、どういった処理を行うのか説明せよ。