ホーム » t-saitoh の投稿 (ページ 2)

作者アーカイブ: t-saitoh

2021年2月
 123456
78910111213
14151617181920
21222324252627
28  

最新の投稿(電子情報)

アーカイブ

カテゴリー

トランザクション処理

トランザクション処理

トランザクション処理とは、相互に依存関係にある複数の処理を矛盾なく処理することであり、データベースでは、ACID特性(原子性,一貫性,隔離性,耐久性)がもとめられる。この時、直列化可能(様々な順序で処理できるかもしれないけど、矛盾しない結果となる処理順序が存在すること)であることが求められる。

例えば、以下のように、50万円のデータがあった時、入金処理と出金処理がほぼ同じタイミングで開始された場合、入金処理が終わらないうちに、出金処理が開始されると、以下の例では入金処理が無視されてしまう。

上記のような問題が発生しないようにするには、以下のように、入金処理の時点で他の更新処理を排除するLOCK処理を行い、入金データの書き込みを終えた時点でUNLOCK処理を行う、排他処理が重要となる。(ロックされている間は、アクセスを禁止する。)

同時実行制御

複数のトランザクションによるデータアクセスで、トランザクション処理を直列化可能にすることを、同時実行制御と呼ぶ。この方式には、2つの方法がある。

  1. ロッキング方式(悲観的制御)
    先行するトランザクションは、データにロックをかけ、他のトランザクションを一時的に排除する方式。後発の処理はアンロックされるまで待たされることことから、これが処理効率の低下となる。

    • ロッキング方式では、ロックをかける大きさ(粒度)が大きいと、待ち処理が発生する可能性が高い。一方で、粒度を小さくしようとすると、ロックの判定が難しくなり効率が低下する可能性も出てくる。
    • ロックの種類
      ロックには、読み出し中心のデータと書き込みで更新のかかるデータでは、ロックのかけ方が異なる。例えば、読み出し中のデータは値が変化しないことから、同じタイミングで読み出し処理が発生しても、待たせる必要は無い。
      この時、データを読み出す際にかける共有ロック(Read Lock)と、書き込みの際にかけるロック占有ロック(Write Lock)がある。
    • 2相ロッキングプロトコル
      トランザクションのロックの操作は、ロックをかける操作が続く成長相と、ロックを解除する操作が続く縮退相に分けて行うことが多い。これを2相ロッキングプロトコルと言う。
  2. 時刻印処理(楽観的制御)
    データの競合の発生頻度が低い場合には、ロッキング方式は待ち処理時間が無駄となるため、同時アクセスを許す方式。ただし、あとで処理の発生した時間(タイムスタンプ)を確認し不都合が判明した場合は、処理の記録をもとにロールバックしてやり直す方式。

デッドロック

複数のトランザクションの実行時には、相互の関係から、処理がうまく進まない場合も発生する。(お互いが相手の処理をロックする状態で、ロック解除が発生しない。)

このような状態をデッドロックと呼び、この状態が発生すると処理が停止してしまうこともある。このような状態は、避けられない場合もあるが、どの処理が何を使うのか、どのデータはどの処理の終了を待っているのかといった資源の状態をグラフ理論で表現したもの資源グラフをで表現し、グラフが巡回するようであれば、デッドロックが発生する。

共有のあるデータの取扱い

これまでの授業の中では、データを効率よく扱うためのデータ構造について議論をしてきた。これまでのプログラムの中では、データ構造のために動的メモリ(特にヒープメモリ)を多用してきた。ヒープメモリでは、malloc() 関数により指定サイズのメモリ空間を借りて、処理が終わったら free() 関数によって返却をしてきた。この返却を忘れたままプログラムを連続して動かそうとすると、返却されなかったメモリが使われない状態(メモリリーク)となり、メモリ領域不足から他のプログラムの動作に悪影響を及ぼす。

メモリリークを防ぐためには、malloc() で借りたら、free() で返すを実践すればいいのだが、複雑なデータ構造になってくると、こういった処理が困難となる。そこで、ヒープメモリの問題点について以下に説明する。

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

リスト構造で集合計算の和集合を求める処理を考える。

// 集合和を求める処理
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, 2, 3, 4 }
                                     //          ~~~~~~~ ここは 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 の一部とデータを共有しているために発生する。この解決方法として簡単な方法では、参照カウンタ法が用いられる。

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

  • データの中にポインタ数を覚える参照カウンタを設け、データを生成した時に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にならないので、取扱いが苦手。

unix i-nodeで使われている参照カウンタ

unixのファイルシステムでは、1つのファイルを別の名前で参照するハードリンクという機能がある。このため、ファイルの実体には参照カウンタが付けられている。unix では、ファイルを生成する時に参照カウンタを1にする。ハードリンクを生成すると参照カウンタをカウントアップ”+1″する。ファイルを消す場合は、基本的に参照カウンタのカウントダウン”-1″が行われ、参照カウンタが”0″になるとファイルの実体を消去する。

ガベージコレクタ

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

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

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


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

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

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

 

データベースの物理設計

データベース後半課題

データベース後半の課題は「卒業研究の対象をデータベースとして設計」とする。

情報系の卒研テーマであれば、処理対象のデータの中にはデータベースで管理するのがふさわしい対象について設計せよ。実験系の卒研テーマであれば、実験結果の表をデータベースで管理するとした場合の設計を行うこと。どちらでもない卒研で、卒研のテーマの中にデータベース化すべき対象が無い場合は、身の回りの帳票(例えばコンビニのレシートなど)をデータベース化することを検討すること。

レポートで記載する内容は、以下の通りとする。

  • 卒業研究におけるデータベース化する対象の説明
  • データベースをトップダウン設計する際の
    • 実体と関連を抽出するまでの説明
    • 正規化を行う経過の説明
    • 上記を踏まえたトップダウン設計でのER図
  • データベースをボトムアップ設計する際の
    • 対象とする帳票に相当するデータの一例と説明
    • レベル分けや正規化を行う経過の説明
    • 上記を踏まえたボトムアップ設計でのER図
  • 考察
    • トップダウン設計とボトムアップ設計に違いがあれば、設計の見直しの過程の説明
    • 両設計方法から分かったこと

データベースの物理設計

データベースの物理的設計は、データベースの格納法法や管理方法を決定する。この際には、ディスク容量の見積もりやメモリ量の見積もりが重要となる。

ディスク容量の見積もり

データベースでは、B木(以降で解説予定)などが用いられることが1つのB木のノード(データブロック)の構造をおおまかに示す。各データブロックには、そのブロックを管理するためのページ制御の情報と、実データへのポインタとなるスロット情報と、実データからなる。

実データは、すべてのデータが固定長であれば、そのデータ長とブロック毎のデータ数にページ制御の容量を加えれば良い。しかし、データ長は可変であることが多い。この場合は、データの更新でデータ長が長くなると、その後ろのデータをずらす処理が頻発すると、データ管理の効率が悪い。

そこで、実データの間には、データ長が増えた時の空き領域を設けておく。この比率がPCTFREEと呼ばれ、この領域が埋まった時にのみデータをずらす処理を行う。

また、データベースへのデータの削除を行う場合、データが1つ消える度にデータブロックの構成を変化させると効率が悪く、通常はデータ削除の目印をつけるだけとすることが多い。データ削除で空きがふえた時だけ、データブロックの構成を変えたり、データ追加の際にデータを追加する。この比率は、PCTUSEDと呼ばれる。

このため、ハードディスク容量の見積もりでは、PCTFREE,PCTUSEDを考慮する必要がある。

一般的には、容量を減らす観点であれば、PCTFREEはなるべく小さく、PCTUSEDはなるべく大きい方が望ましいが、データの更新で追加・削除・修正が頻発するのであれば、PCTFREEはある程度大きく、PCTUSEDはある程度小さい方がよい。このため、PCTFREE+PCTUSED < 100 となるようにチューニングすることが多い

また、実際のデータとは別に、データを高速に検索するためのインデックスファイルが作られるので、この容量も別途考慮が必要となる。

補足:残り予定:トランザクション処理, 内部構造, テスト前レポート課題

EI棟は丹南の先生で朝から除雪

雪で学生さんが休校となるなか、朝イチ学校にきていたのは、鯖江・越前市方面の先生ばっかり。福井方面の先生は、無理だろうなぁ。ということで、学科の出入り口は、西先生・小松先生・白崎さん・斉藤にて、除雪となりました。

この後、堀井さんが、ご自宅の除雪機を持ち込んで、改めて電子情報棟・専攻科棟・自転車小屋まわりの除雪をしてくれました。

{CAPTION}

sizeof(long int)

C言語のプログラミングで、型によってどの程度の数を記憶できるのかを説明することが多い。

注意して欲しい点としては、int型(32bit) = -231〜0〜231-1のあと、64bit を扱う場合はどう宣言するか。

今までは、long int は 実装により 32bit かもしれないし、64bit かもしれないので、64bit を使いたい場合は「gcc なら long long int 型を使って…」と説明していた。

しかし、説明資料を作っていたら、long int=32bit と思っていたけど、64bitだった。

改めて、最近の状況を確認したら、

  • OSが “x86” なら long int = 32bit , long long int = 64bit
  • OSが “x86_64” なら long int = 64bit , long long int = 64bit

なのね。

ハッシュ法

ここまでの授業では、配列(データ検索は、登録順保存ならO(N)2分探索なら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 ; // ひとつ後ろの席
   }                                // 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)となる。しかし、ハッシュ表がほぼ埋まっている状態だと、残りわずかな空き場所を探すようなもの。

チェイン法

前に述べたオープンアドレス法は、ハッシュ衝突が発生した場合、別のハッシュ値を求めそこに格納する。配列で実装した場合であれば、ハッシュ表のサイズ以上の データ件数を保存することはできない。

チェイン法は、同じハッシュ値のデータをグループ化して保存する方法。 同じハッシュ値のデータは、リスト構造とするのが一般的。

この処理にかかる時間は、データ件数が少なければ、O(1) となる。しかし、ハッシュ表のサイズよりかなり多いデータ件数が保存されているのであれば、ハッシュ表の先に平均「N/ハッシュ表サイズ」件のデータがリスト構造で並んでいることになるので、O(N) となってしまう。

#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 ;
}

文字列のハッシュ値

ここまでで説明した事例は、電話番号をキーとするものであり、余りを求めるだけといったような簡単な計算で、ハッシュ値が求められた。しかし、一般的には文字列といったような名前から、ハッシュ値が欲しいことが普通だろう。

ハッシュ値は、簡単な計算で、見た目デタラメな値が求まればいい。 (ただしく言えば、ハッシュ値の出現確率が極力一様であること)。一見規則性が解らない値として、文字であれば文字コードが考えられる。複数の文字で、これらの文字コードを加えるなどの計算をすれば、 偏りの少ない値を取り出すことができる。

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 ;
}

この後の授業の予定

  • 共有のあるデータの取り扱い(参照カウンタ法,ガベージコレクタ) (1/14)
  • 動的メモリ確保(malloc()とfreelist) (1/21)
  • オブジェクト指向 (1/28)
  • 予備 (2/4)

データベースの設計と正規形

データベースの設計において、重要な正規形についての説明

正規形

データベースにおいて、様々な不整合を防ぐために正しい設計が必要であることを 改めて説明し、それには正規形としての条件を満たしている必要があることを説明する。

第一正規形は、すべての要素が原子値である条件を満たせばいい。 要素の中が複数の項目であったり表形式のデータがあると、 表構造のリレーショナルデータベースにはできない。


キーの説明超キー(スーパーキー)とは、データベースで1つのデータを 選び出すために必要なデータ項目であり、複数の項目で1データを指定 できる場合もある。

候補キーとは、必要最小限の項目となっているものを指す。 1項目が抜けても選別できなくなるようであれば、候補キーとは言わない。 主キーとは、候補キーのなかで管理の都合上便利なもの。

データ項目の値が決まると、他のデータ項目が自動的に決まるものは、 従属関係があるという。

第1正規化 第2正規化

第二正規形は、部分従属がなく、すべての非キーデータ項目が、候補キーに 完全従属する場合をいう。

  • 完全従属とは、候補キーを構成する全てのデータ項目に、非キーデータ項目が従属していること。
  • 部分従属とは、候補キーを構成するデータ項目の一部のデータ項目に、非キー項目が従属していること。

この例において、単価は商品が決まれば自動的に求まる情報。 (単価が日々変化することはないという条件で…) これは、部分従属となる。他に部分従属となっている属性は何か?

  • 推移従属性とは、データ項目でA→B→Cと、次々と値が求められる関係を指す。

第三正規形とは、 候補キー以外の非キーデータ項目は、候補キーに完全従属し、 かつどの候補キーにも推移従属しない関係をいう。

第3正規化

上記の例では、単価と個数が決まれば、金額が求まる推移従属の関係が含まれている。

おまけ:BC正規形,第4,5正規形

この他にも、 さらに非キーからキーに関数従属性がある場合にそれを取り除く、 ボイスコッド正規形(BC正規化)。 「対称性のある多値従属性(キーを決めると複数データが該当)」を分解して得られる第4正規形や、 「元になるテーブルの結合従属性を維持して分解することにより得られる第5正規形などがある。

トップダウン設計・ボトムアップ設計

データベースの設計にあたって、実際の設計手順の説明を行う。

トップダウン設計では、対象業務を記述し、その中から名詞となっている実体を抽出する。 さらに動詞や形容詞のように記載されている関連を抽出する。 抽出した実体・関連では、あいまいであったり冗長であったりするので、整理したうえで、 その実体・関連をER図に表す。

ボトムアップ設計では、対象業務で実際に使われている入力帳票や結果の出力などを 見ながら、第1正規形を満たすように表を作っていく作業からおこなう。

トップダウン設計やボトムアップ設計で、 ER図や第一正規形を満たすような表が出来上がったら、 その属性の中で従属性を確認しながら、第2正規形・第3正規形へと整理していく。

残りの授業の予定

  1. データベースの物理設計(1/13)
  2. トランザクション処理(1/20)
  3. B木とB+木とハッシュ法(1/27)
  4. 予備 (2/3)

CTF実験とobjdumpの使い方

CTF実験で、objdump を使う問題の解説。

機械語の知識が必要なCTF問題

use-the-strings の問題では、ダウンロードすると Linux 実行ファイルが得られる

$ file use-the-strings
use-the-strings: ELF 64-bit LSB pie executable, x86-64, version 1 (SYSV)...
$ sudo apt-get install binutils    # binutilsはインストール済みかも
$ objdump -d use-the-strings       # use-the-stringsを逆アセンブル

逆アセンブルにより出力されたプログラムの最も主要な部分を示す。

上記プログラムの機械語を、C言語っぽく書くならば、以下のようになるだろう。

    reg_eax = memory( 0x2fde+reg_rip ) ; // 大域変数flagを取り出す
    if ( reg_eax != 0 ) goto label_105d ;
    reg_eax = 0 ;
    return ;
label_105d:
    push( reg_rax ) ;
    reg_rdi = 0xf9f+reg_rip ; // 出力文字の保存場所
    puts() ;                  // 以下のputsを呼び出す。
    reg_eax = 0 ;
    pop( reg_rdx ) ;
    return ;

ちなみに、この use-the-strings の元プログラムは、以下のような内容である。
flag の変数に 0 以外の値が入っていれば、本来の出力処理が行われるはずだが、大域変数初期化にて通常であれば動かない。

このため printf を動かすには、以下の方法があるだろう。

  1. if 文(機械語ならば jne 命令の部分)を書き換えて、printf が実行されるようにする。
    • 0x1058番地の jne(0x75) を jmp(0xeb) に書き換える。
  2. if文を実行する前に、大域変数 flag を0以外の値に書き換える。
    • 今回は、この方法の説明として、Cのソースプログラムとそのデバッガ情報を持った use-the-strings-gdb を使った方法を説明する。(ただし、Cのソースが手に入ったのなら答えもバレているはずだが…)
    $ gdb use-the-strings-gdb 
    GNU gdb (Debian 10.1-1+b1) 10.1
    :
    (gdb) break main         # ブレークポイントを設定
    Breakpoint 1 at 0x1050: file use-the-strings.c, line 33.
    (gdb) run                # プログラムを動かす
    Starting program: /home/t-saitoh/public_html/ctf/use-the-strings-gdb 
    
    Breakpoint 1, main () at use-the-strings.c:33
    33	  if ( flag ) {
                             # main() の先頭で一時停止
    (gdb) set flag=1         # 変数 flag に 1 を代入
    (gdb) continue           # 続きを実行させる
    Continuing.
    FLAG{UseTheStrings}      # 答えが表示された。
    [Inferior 1 (process 767940) exited normally]
    (gdb) quit               # デバッガを抜ける
    

そもそももっと簡単な方法がある

機械語の知識に興味を持ってもらうために、あえて、上記のような説明をしたけど、本来はもっと簡単な手法がある。

strings コマンドは、ファイル中の英数字などで表示可能な文字部分を抽出して表示する。

$ strings use-the-strings
/lib64/ld-linux-x86-64.so.2
libc.so.6
puts
:
$ strings use-the-strings | grep FLAG  # FLAGという文字を含むのが解っていれば
FLAG{UseTheStrings}

strings コマンドを使えばこの問題は極めて簡単に解けるが、ではCTFの難易度を高めるにはどうすればいいだろうか?

一般的に、ウィルス対策ソフトは、プログラム中の特定の機械語が、既知のウィルスの機械語パターンと一致しているかどうかで、ウィルスが含まれているか検知する。つまり、strings でバレない対策を考える…ということは、ウィルス作者が「如何にウィルス対策ソフトに見つからないウィルスを作るのか」ということに繋がる。

B木とデータベース

2分探索木の考え方を拡張したもので、B木がある。

B木の構造

2分木では、データの増減で木の組換えの発生頻度が高い。そこで、1つのノード内に複数のデータを一定数覚える方法をとる。B木では、位数=Nに対し、最大2N個のデータd0..d2N-1と、2N+1本のポインタp0..p2Nから構成される。piの先には、di-1<x<di を満たすデータが入った B木のノードを配置する。ただし、データの充填率を下げないようにするため、データは最小でもN個、最大で2N個を保存する。

B木からデータの検索

データを探す場合は、ノード内のデータ diの中から探し、見つからない場合は、ポインタの先のデータを探す。位数がある程度大きい場合、ノード内の検索は2分探索法が使用できる。また、1つのノード内の検索が終われば、探索するデータ件数は、1/N〜1/2Nとなることから、指数的に対象件数が減っていく。よって、検索時間のオーダは、O(logN) となる。

B木へのデータの追加

B木にデータを追加する場合は、ノード内に空きがあれば、単純にデータの追加を行う。ノード内のデータが2N個を越える場合は、以下のような処理を行う。

ノード内のデータと追加データを並べ、その中央値を選ぶ。この中央値より大きいデータは、新たにつくられたノードに移す。中央値のデータは上のノードに追加処理を行う。このような方法を取ることで、2分木のような木の偏りが作られにくい構造となるようにする。

データを削除する場合も同様に、データ件数がN個を下回る場合は、隣接するノードからデータを取ってくることで、N個を下回らないようにする。

B木とデータベース

このB木の構造は、一般的にデータベースのデータを保存するために広く利用されている。

データベースシステムでは、データを効率よく保存するだけでなく、データの一貫性が保たれるように作られている。
例えば、データベースのシステムが途中でクラッシュした場合でも、データ更新履歴の情報を元にデータを元に戻し、データを再投入して復旧できなければならない。データを複数の所からアクセスした場合に、その順序から変な値にならないように、排他制御も行ってくれる。

データベースで最も使われているシステムは、データすべてを表形式で扱うリレーショナル・データベースである。

((リレーショナル・データベースの例))
STUDENT                             RESULT
ID   | name     | grade | course    ID   | subject | point
-----+----------+-------+--------   -----+---------+-------
1001 | t-saitoh |  5    | EI        1001 | math    | 83
1002 | sakamoto |  4    | E         1001 | english | 65
1003 | aoyama   |  4    | EI        1002 | english | 90

((SQLの例))
select STUDENT.name, RESULT.subject, RESULT.point --射影--
   from STUDENT , RESULT                          --結合--
   where STUDENT.ID == RESULT.ID    -- 串刺し --   --選択--
         and RESULT.point >= 60 ;

((上記SQLをC言語で書いた場合))
for( st = 0 ; st < 3 ; st++ )                   // 結合
   for( re = 0 ; re < 3 ; re++ )
      if ( student[ st ].ID == result[ re ].ID  // 選択
        && result[ re ].point >= 60 )
           printf( "%s %s %d" ,                 // 射影
                   student[ st ].name ,
                   result[ re ].subject ,
                   result[ re ].point ) ;

B+木

データベースの処理では、目的のデータを O(log N) で見つける以外にも、全データに対する処理も重要である。この場合、全てのデータに対する処理では、単純なB木では再帰呼び出しが必要となる。しかし、他の表でも再帰処理を伴うと、プログラムは複雑になってしまう。

そこで、B木のデータを横方向に並べて処理を行う場合に、その処理が簡単になるように B+木が用いられる。
この方法では、末端のノードは、隣接するノードへのポインタを持つ。

データベースの設計とER図

データベースの設計

リレーショナル・データベースでは、データは表形式であればなんでも良い訳ではない。

例えば、学生の成績データが以下のような構造であった場合、

 ID   | name   | grade | subject  | teacher
------+--------+-------+----------+---------
20101 | aoyama |   1   | database | saitoh
20101 | aoyama |   1   | software | murata
20002 | suzuki |   2   | database | saitoh
20002 | suzuki |   2   | compiler | nomura
30203 | yamada |   3   | media    | ogoshi
  • 修正不整合: 授業担当が saitoh → sasaki のように変更になったら、複数のテーブルを修正しなければならない。大量のレコード修正は、時間がかかるし、その途中にシステムダウンしたらデータの整合性に問題が発生するかも。
  • 挿入不整合: 新しい科目 internet を追加したいけど、受講学生が決まらないとデータを挿入できない。
  • 削除不整合: yamada が受講を取りやめたら、科目 media も消えてしまう。

これらを考慮すると、以下のような3つの表で設計するべきである。

学生                      受講            科目
ID    | name   | grade    ID   | SubID   SubID | subject | teacher
------+--------+-------  ------+-------  ------+----------+--------
20101 | aoyama | 1       20101 | 1001     1001 | database | saitoh → sasaki
20002 | suzuki | 2       20101 | 1002     1002 | software | murata
30203 | yamada | 3       20002 | 1001     1003 | compiler | nomura
                         20002 | 1003     1004 | media    | ogoshi
                  消す→ 30203 | 1004     1005 | internet | foobar → 追加

データベースの設計では、(1)概念設計、(2)論理設計、(3)物理設計が行われる。

  • 概念設計:概念スキーマの決定(実体・関係モデルを使う)。上記の受講データベースの設計例
  • 論理設計:論理スキーマの決定。関係データベースで実装?ほかのデータベース?
  • 物理設計:物理スキーマの決定。データの格納方法や管理方法を決める。

実体関連モデル(ERモデル)

データベース設計では、実体関連モデル(ERモデル:Entity-Relation model)が使われる。 実体とは、モデル化しようとする対象で独立した存在となれるもの。 実体が持つ色々な特性は属性と呼ばれる。 属性の取りうる値の集合を定義域、同一種類の実体の集まりを実体集合と呼ぶ。 関連とは、実体同士の相互関係をモデル化したもの

実体関連図(ER図)では、実体を長方形、関連をひし形、属性を楕円で表現する。 属性で、キーとなるものには下線をつけて表す。

ER図で調べると、実際にはもっと細かい規定で表現が行われている。 参考:IDEF1X表記とIE表記