ホーム » スタッフ » 斉藤徹 » 講義録

講義録」カテゴリーアーカイブ

2024年3月
 12
3456789
10111213141516
17181920212223
24252627282930
31  

検索・リンク

サーバ移行作業で2015年以前のテスト問題が消えた

サーバの移行作業を行ったけど、その際に自分のホームディレクトリ配下に置いてあった、過去のテスト問題のデータが消えた。エビデンス用に学校で保管してあるデータからコピーして、2015年以降は復活できたけど。

データベース期末試験で鳥山明氏を…

先日の #データベース の正規化のテスト問題。最近の原作と作画の分担された作品との対比という点で、 #鳥山明 さんのお名前を使わせてもらっていた。

2023年度 情報構造論 講義録

2023-情報ネットワーク基礎-講義録

授業アンケート 2023 後期

情報工学演習(2EI)

84.3  ポイントと高い評価であった。プログラミングコンテストを用いた演習内容の発表では、こちらが想定してた難易度の高い問題について説明したものが少なく、来年度は制約などを設けたいと思った。

情報ネットワーク基礎(3EI)

87.4 ポイントと高い評価であった。感想でもわかりやすかったとか、雑談が面白かったといった具体的な意見ももらえ、授業はうまくいったと思える。

情報構造論(4EI)

86.0 ポイントと高い評価であった。

データベース(5EI)

86.3 ポイントと高い評価であった。選択科目ながらも興味を持ってもらえたと思える。もう少し踏み込んだ内容に改善すべき所については、説明資料などの改善をすすめていきたい。

関数ポインタ

関数ポインタとコールバック関数

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による理解度確認テスト
  • 標的型攻撃メールがウィルス対策ソフトでは防ぐことが難しい理由を述べよ。
  • ファイアウォールでは、どういった処理を行うのか説明せよ。

暗号化とパスワード

暗号化

有線LANで1本のケーブルを共有したり無線でデータをやりとりする場合、通信の盗聴が行われると危険である。
前回の授業で紹介したように、簡単な置換式暗号などでは暗号の解読ができてしまう。

暗号化アルゴリズム

1980年頃には DES(Data Encryption Standard) がアメリカでの標準的な暗号化として使われていたが、コンピュータの性能があがると共に解読される危険性が高まってきた。そこで2000年頃にはAES(Advanced Encryption Standard) が使われるようになった。どちらも共通鍵を用いてデータをブロック(固定長のデータ)単位で暗号化する共通鍵ブロック暗号方式であり、暗号の鍵の長いものは暗号解読が困難となっている。

1980年頃に開発された RSA 暗号(開発者の名前より) は、巨大な数字の素因数分解が困難なことを利用した、公開鍵暗号方式の1つである。

最近、量子コンピュータを用いた暗号解析が話題となっている。量子力学の原理を計算に応用したコンピュータで、スーパーコンピュータで1万年かかる暗号解読のような処理が200秒で終わってしまうかもしれないと言われている。

公開鍵暗号方式とは…

以前に使われていた暗号化の方式は、暗号化の鍵と復号化の鍵に同じものを用いる共通鍵方式であった。
しかし、この鍵をどうやって相手に渡すか…が問題となっていた。(鍵を相手に渡す瞬間のデータを盗聴されると危険)

このため、最近では公開鍵暗号方式が中心となっている。この方式は「暗号化するため専用公開鍵」と、「暗号化を復号するための秘密鍵」をペアにして用いる。公開鍵は、暗号化するため専用なので、この鍵が他の人に見られても、暗号を復号することはできない。

公開鍵だけでは成り済ました別人と通信してしまう可能性[1]がある。そこで通信相手が本物かどうかを、認証局とよばれる第三者機関によって証明書で確認する。HTTPを暗号化したHTTPSでは、SSL証明書と呼ばれる。最近のブラウザでは、URLの左側の鍵マーク🔒からSSL証明書を確認することができる。

[1] DNSサーバの脆弱性を利用して、間違ったIPアドレスを教えさせる DNSポイズニング が行われると、利用者を間違ったサーバに接続させることが可能。

パスワード解読方法

ログインなどで使われるパスワードは、どのように破られるのだろうか?

  • ブルートフォース攻撃:単純に全ての文字を試す方式。文字の組み合わせ問題なので、パスワード文字列長をNとした場合、数字だけ(10N)とか英字だけ(26N)といった組み合わせでは、短時間に解読されてしまう。数字,大文字,小文字,記号などを交えたパスワードが理想。
  • 英単語辞書を用いた辞書攻撃:パスワードが長い場合、文字列の全ての組み合わせを試すには長い時間が必要となる。しかし、パスワードはユーザが記憶して使うことから覚えやすい単語が使われる。このため英単語辞書の文字を組み合わせることで、解読時間を短くできる場合がある。
  • 漏えいパスワードによる辞書攻撃:サーバへのリモート接続などができてしまった場合、パスワード情報が盗まれる場合がある。この時、別なサイトに同じパスワードを使っていると、その漏えいしたパスワードで別のサイトも接続ができてしまう。これらのことから、同じパスワードを使いまわすことは避けるべきである。
  • ソーシャル攻撃:パスワードには、簡単に覚えられるように自宅の電話番号、誕生日、家族の名前といったものを使う人が多い。このため、SNS で相手に友達登録をしてもうことで、こういった情報を手に入れ、パスワードを破る方法。最近の有名人の個人情報漏洩はこの手の攻撃が多い。

    ソーシャル攻撃は、”元クラッカー” ケビン・ミトニックが有名

  • パスワードスプレー攻撃:login 画面などにブルートフォース攻撃を加えて簡単にパスワードが破られるのは問題となる。このため、短時間に何度も login 操作をできないように、数回のパスワード入力に失敗すると一定時間 login ができなくなるような対策が取られる。しかし、プログラムを使ってブルートフォース攻撃をするのであれば、攻撃間隔を空ければいい。攻撃者は、その代わりにネットワークの別のコンピュータでブルートフォース攻撃をすればいい。時間当たりの攻撃回数が少ないため、通常ユーザのパスワード間違いと区別ができないので、気づかないうちにパスワード破りに成功するかもしれない。このため、長期間パスワードを変更しないユーザは、不正利用被害が発生する可能性がある。

攻撃が難しいパスワードへ

先に述べたような、login に使うパスワードなどは、ブルートフォース攻撃をうけると解読は時間の問題となる。これらの対策として毎回違う鍵(パスワード)を使えばいい。

  • ワンタイムパスワード:使い捨てのパスワードをあらかじめ沢山作っておき、接続の度に次のパスワードを用いる方式。あるいは、時間から特殊な計算方法で生成されるパスワード。時間と共に変化するのでその度毎に違うパスワードとなる。毎回違うパスワードを入力するため、パスワード表を常に持ち歩いたり、入力が面倒なので数字だけを使うことが多く、この方法だけでは使いにくい。(次週に多要素認証などの解説も行う)

多要素認証

パスワードはブルートフォース攻撃をうければ、いつかはパスワードが破られる危険性がある。こういった対策で最も重要な方法が、多要素認証(2段階認証)である。

この方式では、通常のパスワード入力の後に、以下の様な方式でワンタイムパスワードを入力することでログインが可能となる。

  • 携帯電話にテキストメッセージ(SMS)でワンタイムパスワードを送る。
  • かかってきた電話の機械音声のワンタイムパスワードを伝える。
  • 時間で変化するワンタイムパスワード生成アプリの数字を入力する。
  • メールで送られてきたワンタイムパスワードを含んだURLにアクセスする。
  • 認証画面に表示されたQRコードのURLにアクセスする。


SMSやワンタイムパスワードアプリは、携帯電話などを常に持ち歩いていることが本人確認となっている。このような方式では、携帯電話などを失くすとシステムが使えなくなるので、バックアップコード(非常時用のパスワード)の保存や、login先とは別のメールアドレスを登録してあることが重要となる。

CAPTCHA

最近では、フリーで取得できるメールアドレスをプログラムで動くロボットで自動生成し、そのアカウントを使ってspamを送るなどの手口が問題となっている。このため、接続してきた相手が人間か判定することがある。判定には、読みづらく加工された英字を入力させたり、パズルを解かせるといった方法が使われる。

元々は、読みづらい文字はコンピュータでは画像解析しづらいことから、CAPTCHA が使われるが、最近では機械学習によって解析ができるようになってきた。

セキュリティキー

SMSやメールを使ったワンタイムパスワードによる多要素認証も、間にネットワークを挟むと多要素認証では問題となる。そこで、もっと複雑な暗号で多要素認証を行うために、セキュリティキーが使われる。

多要素認証が必要になると、パソコンにセキュリティキーを差し込むことで認証が行われる。現在では FIDO(Fast IDentity Online)や FIDO2 といった規格のものが普及している。

ハッキング

インターネットの用語でハッカー(Hacker)は、コンピュータを使って悪いことをする人という意味でよく使われている。しかし元々は「主にコンピュータや電気回路一般について常人より深く高度な技術的知識を持ち、その知識を利用して技術的な課題をクリアする人々のこと」(Wikipedia引用)という意味で使われていた。このため本来は「優秀なエンジニアへの最大級の誉め言葉」として使われており、ハッカー以上の技術者を ウィザード/wizard や グル/guru と呼称することもある。

しかしながら一部のハッカーの中で、その技術を悪用する人も出てきたことから、インターネットで悪いことをする人という意味で使われることも増えてきた。そこで、悪いことをする人は別な呼び方をしようということで、攻撃を加えるひとはクラッカーと呼ぶことが多い。最近では、正義のためのハッカー = ホワイト・ハッカー、悪いハッカー = ブラック・ハッカー という表現も使われるが、黒人差別主義につながる用語ということで、正義のためのハッカーには最近はエシカル・ハッカー(高い倫理観と道徳心を兼ね備えている高い技術を持ったハッカー)という言葉を使う。

理解度確認

  • Formsによる理解度確認テスト
  • 標的型攻撃メールがウィルス対策ソフトでは防ぐことが難しい理由を述べよ。
  • ファイアウォールでは、どういった処理を行うのか説明せよ。

NoSQLと Google Firestore

データベースシステムとして、最近は NoSQL (Not Only SQL) が注目されている。この中で、広く使われている物として、Google Firestore などが有名である。教科書以外の最近のデータベースの動向ということで、最後に NoSQL の説明を行う。

リレーショナルデータベースシステムの問題

リレーショナルデータベースのシステムでは、大量の問い合わせに対応する場合、データのマスターとなるプライマリサーバに、そのデータの複製を持つ複数のセカンダリサーバを接続させる方式がとられる。しかしながら、この方式ではセカンダリサーバへのデータ更新を速やかにプライマリサーバに反映させる、さらにその結果が他のセカンダリサーバに反映させる必要があることから、大量のデータに大量の問い合わせがあるようなシステムでは、これらのデータ同期の性能が求められる。しかも、プライマリサーバが故障した場合の復旧なども考えると、こういったプライマリ・セカンダリ・サーバ構成での運用・管理は大変である。

NoSQLの利点

NoSQLのデータベースでは、すべてのデータを複数のサーバ(別のデバイス,ネットワーク)に冗長化したうえで分散して保存する。この際に、どのサーバがプライマリサーバといった概念はない。もし1つのサーバが故障したとしても、分散して保存されたデータから元のデータを自動的に修復できるような構造となっている。

データの分散保存であれば、ハードディスクの RAID システムなども関連知識となるであろう。

  • RAID0 – ストライピング(データを別デバイスに分散保存し、並行読み出しで高速化)
  • RAID1 – ミラーリング(データを複数デバイスに同じものを書き込んで、データ故障耐性を実現)
  • RAID5 – データを複数デバイスに分散保存する際に、データ誤り訂正のデータも分散保存し、高速化と故障耐性を実現
  • RAID6 – データ誤り補正のデータを複数もたせて、分散保存

リレーショナルデータベースで大量のユーザからアクセスされる場合、データが安全に取り扱うことができたり、システムに障害が発生した時の対応や、システムのスケーラビリティ(利用状況に応じて処理するプロセッサなどを増やしたり減らしたりする機能)が重要となる。NoSQLのシステムでは、中心となるプライマリサーバを作るのではなく、データを複数のシステムに分散して保存し、障害が発生しても、分散したデータから自動的にデータを修復できるような構成とする。

NoSQLのシステムでは、データ格納形式から、キーバリューストア型、カラムストア型、ドキュメントデータベース、グラフデータベースに分類される。最も代表的なものは、保存するデータ(Value)に対し検索するためのキー(Key)だけの基本的なデータ検索だけを提供する キーバリューストア(Key-Value store)である。こういった構成ではSQLとは違い、複数のテーブルをまたがった検索などができない(サブコレクションなどを使えば代用可能)。

Google の Firestore

NoSQLのデータベースを構築したのは、Google が先駆けであった。現在、このGoogle の NoSQL のシステムは、Firestore として利用されている。(データベースはFireBase)

Firestore は、ドキュメントモデルデータベースの一種であり、すべてのデータはドキュメントとコレクションに保存される。ドキュメントは、データベースでのレコードに相当するが、属性名とそれに対応したデータの JSON オブジェクトである。コレクションは、キーにより対応するドキュメントを取り出せるデータ群である。ドキュメントの中に、サブコレクションを保存することもできる。

参照カウンタの問題とガベージコレクタ

前回の授業では、共有のあるデータ構造では、データの解放などで問題が発生することを示し、その解決法として参照カウンタ法などを紹介した。今日は、参照カウンタ法の問題を示した上で、ガベージコレクタなどの説明を行う。

共有のあるデータの取扱の問題

前回の講義を再掲となるが、リスト構造で集合計算おこなう場合の和集合を求める処理を考える。

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( c ) ;
   list_del( b ) ;
   list_del( a ) ; // list_del(c)ですでに消えている
}                  // このためメモリー参照エラー発生

このようなプログラムでは、下の図のようなデータ構造が生成されるが、処理が終わってリスト廃棄を行おうとすると、bの先のデータは廃棄済みなのに、list_del(c)の実行時に、その領域を触ろうとして異常が発生する。

参照カウンタ法

上記の問題は、b の先のリストが c の一部とデータを共有しているために発生する。この解決方法として簡単な方法では、参照カウンタ法が用いられる。

参照カウンタ法では、データを参照するポインタの数をデータと共に保存する。

  • データの中にポインタ数を覚える参照カウンタを設け、データを生成した時に1とする。
  • 処理の中で共有が発生すると、参照カウンタをカウントアップする。
  • データを捨てる際には、参照カウンタをカウントダウンし、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にならないので、取扱いが苦手。

ガベージコレクタ

では、循環リストの発生するようなデータで、共有が発生するような場合には、どのようにデータを管理すれば良いだろうか?
最も簡単な方法は、「処理が終わっても使い終わったメモリを返却しない」方法である。ただし、このままでは、メモリを使い切ってしまう。

そこで、廃棄処理をしないまま、ゴミだらけになってしまったメモリ空間を再利用するのが、ガベージコレクタである。
ガベージコレクタは、貸し出すメモリ空間が無くなった時に起動され、

  1. すべてのメモリ空間に、「不要」の目印をつける。(mark処理)
  2. 変数に代入されているデータが参照している先のデータは「使用中」の目印をつける。(mark処理)
  3. その後、「不要」の目印がついている領域は、だれも使っていないので回収する。(sweep処理)


この方式は、マークアンドスイープ法と呼ばれる。ただし、このようなガベージコレクタが動く場合は、他の処理ができず処理が中断されるので、コンピュータの操作性という点では問題となる。

最近のプログラミング言語では、参照カウンタとガベージコレクタを取り混ぜた方式でメモリ管理をする機能が組み込まれている。このようなシステムでは、局所変数のような関数に入った時点で生成され関数終了ですぐに不要となる領域は、参照カウンタで管理し、大域変数のような長期間保管するデータはガベージコレクタで管理される。

大量のメモリ空間で、メモリが枯渇したタイミングでガベージコレクタを実行すると、長い待ち時間となることから、ユーザインタフェースの待ち時間に、ガベージコレクタを少しづつ動かすなどの方式もとることもある。

ガベージコレクタが利用できる場合、メモリ管理を気にする必要はなくなってくる。しかし、初心者が何も気にせずプログラムを書くと、使われないままのメモリがガベージコレクタの起動まで放置され、場合によっては想定外のタイミングでのメモリ不足による処理速度低下の原因となる場合もある。手慣れたプログラマーであれば、素早くメモリを返却するために、使われなくなった変数には積極的に null を代入するなどのテクニックを使う。

プログラム言語とメモリ管理機能

一般的に、C言語というとポインタの概念を理解できないと使えなかったり、メモリ管理をきちんとできなければ危険な言語という点で初心者向きではないと言われている。

C言語は、元々 BCPLB言語を改良してできたプログラム言語であった。これに、オブジェクト指向の機能を加えた C++ が作られた。C++ という言語の名前は、B言語→C言語と発展したので、D言語(現在はまさにD言語は存在するけど)と名付けようという意見もあったが、C++ を開発したビャーネ・ストロヴストルップは、ガベージコレクタのようなメモリ管理機能が無いことから、D言語を名乗るには不十分ということで、C言語を発展させたものという意味でC++と名付けている。

こういった中で、C++をベースとしたガベージコレクタなどを実装した言語としては、Java が挙げられる。オブジェクト指向をベースとしたマルチスレッドやガベージコレクタに加え、仮想マシンによる実行で様々なOS(やブラウザ)で動かすことができる。

最近注目されている言語の1つとして、C言語の苦手であった「メモリ安全性」や実行効率を考えて開発されたものに Rust が挙げられる。メモリ管理や効率などの性能から、最近では Linux の開発言語に Rust を部分的に導入されている。


C言語でデータが保存される領域は大きく以下の3つに分類される。

  1. 静的データ領域(大域変数領域)
  2. スタック領域(局所変数)
  3. ヒープ領域(malloc(),free()で管理される領域)

2,3は、処理の途中で領域が作られ不要になったら消える領域であり動的メモリ領域という。

局所変数とスタック

局所変数は、関数に入った時に作られるメモリ領域であり、関数の処理を抜けると自動的に開放されるデータ領域である。

関数の中で関数が呼び出されると、スタックに戻り番地情報を保存し、関数に移動する。最初の処理で局所変数領域が確保され、関数を終えると局所変数は開放される。
この局所変数の確保と開放は、最後に確保された領域を最初に開放される(Last In First Out)ことから、スタック上に保存される。

baz()の中で、「*((&c)+8) = 123 ;」を実行したら、bar()のxを書き換えられるかも…(実際の関数呼び出し時に保存される情報はもう少し複雑:コールスタック/Wikipedia)

こういった変数の並び順を悪用し、情報の読み書きを防ぐために、局所変数の保存場所の順序を入れ替えたり、メモリのアドレス空間配置のランダム化などが行われたりする。

 

システム

最新の投稿(電子情報)

アーカイブ

カテゴリー