バッファ、キャッシュ

バッファ(buffer、バッファー)とは、元々は物理的な衝撃を吸収して和らげる緩衝器の意味である。この言葉がコンピュータなど情報処理機器の中で電気的に似たような働きをする部分に対して用いられる。

緩衝器としては機械的な仕組みとして構造物で前後の物理的干渉を断ち切って前後関係による悪影響を防止する目的であったが、電気や電子分野などの発展によってこれらの分野でも「バッファ」は転用され、これらの分野では吸収による緩衝に替わり、前後の相互干渉による悪影響を隔離することや時間的差違を補正する遅延や一時記憶など整合を図り矛盾を解決する機能や手段となっており、これらを緩衝と呼んでいる。

機械や装置などの機構部分を成し使用される場合は「バッファー」と呼ぶ場合が多いが英語の綴りは同じである。JIS Z8301によって語尾に長音符号を付けないとする規格もあり、電気的な緩衝での用法の場合は長音符号を付けない表記が多い。本記事では電気・電子装置での用法について記述し、他の用法や分野は曖昧さ回避である「バッファー」を参照のこと。

デジタル機器での補助記憶装置などの入出力装置と、CPU・制御装置などの内部処理装置との間で信号をやり取りする際に、入出力と処理との間で時間のズレを吸収・調整をするために一時的に情報を記憶する装置や記憶領域のこと。

データ構造的にいえばキューやスタックという、情報を一時的に蓄える記憶領域などは、「バッファー領域」と呼ばれることが多い。

例としては次のようなものがある。

汎用ロジックICなどでの1ビットから数ビット単位の時間差の吸収(緩衝)
ビデオカードフレームバッファ
ハードディスクのドライブ(トラック)バッファ
MS-DOSのセクタバッファ
プリンタバッファ
インターネット上のストリーミング配信のバッファ

電気信号の整形・増幅回路の例としては次のようなものがある。

バス・バッファ:コンピュータの内部配線での整形・増幅回路
スリー・ステート・バッファ:"0"、"1"、ハイインピーダンスの3種類の出力状態をとるデジタル信号の整形・増幅回路

キャッシュ (英: cache) は、CPUのバスやネットワークなど様々な情報伝達経路において、ある領域から他の領域へ情報を転送する際、その転送遅延を極力隠蔽し転送効率を向上するために考案された記憶階層の実現手段である。実装するシステムに応じてハードウェア・ソフトウェア双方の形態がある(今後コンピュータのプログラムなども含め全ての転送すべき情報をデータと表す)。

転送元と転送先の中間に位置し、データ内容の一部とその参照を保持する。データ転送元への転送要求があり、それへの参照が既にキャッシュに格納されていた場合は、元データからの転送は行わずキャッシュが転送を代行する(この状態をキャッシュヒット、キャッシュに所望のデータが存在せず元データから転送する状態をキャッシュミスという。なお、由来は不明で和製英語と思われるが日本の一部の文献及び資格試験において「キャッシュミスヒット」という用語が使われている)。もしくは出力データをある程度滞留させ、データ粒度を高める機能を持つ。これらによりデータの2種の局所性、すなわち時間的局所性と空間的局所性を活用し、データ転送の冗長性やオーバヘッドを低減させることで転送効率を向上させる。

コンピュータの各記憶領域を始めとして、ネットワークやデータベース、GPUDSPなど様々なシステムの様々な階層に搭載されている。

データを保持する記憶装置のコストバランスは、通常小容量×高速≒大容量×低速が成り立つ。小容量×高速記憶装置の代表はCPUレジスタであり、大容量×低速記憶装置の代表はハードディスクや磁気テープなどの補助記憶装置である。記憶装置の理想は大容量×高速アクセスであるが、通常コストパフォーマンスが悪く実現困難である。そのため小容量×高速、中容量×中速、大容量×低速など複数段階にまたがった記憶構造とし(一般にCPUなどバスマスタに近い側を上位レベル、遠い側を下位レベルとする)、各レベルを各々下位レベルの一時記憶として用いることで代替する。この構造を記憶階層という。

記憶階層のうちキャッシュに該当する、L1キャッシュとL2キャッシュについて、上位のL1キャッシュに存在するデータが下位のL2キャッシュにもデータが存在する方式(インクルージョンキャッシュ)と、上位のL1キャッシュに存在するデータが下位のL2キャッシュに必ずしもデータが存在しない方式(ビクティムキャッシュ)がある。

データの再利用率とその時間的特性を示す言葉。ある領域のデータ転送が行われて、同一データの転送が再度、近い時間内に行われている場合を時間的局所性があるという。CPUにおける命令キャッシュや、ウェブブラウザなどにおけるファイル単位のデータ保持などは、転送が行われた近い期間にループや戻るボタンなどによる再転送要求を期待して、アクセスがあったデータをある程度後まで保持しておく。逆に音声のようなストリームデータなどは時間的局所性はあまりなく、下記にある空間的局所性に頼った効率化を図る必要がある。

データの格納位置に対する偏在性を示す言葉。ある領域のデータ転送が行われて、近い時間内に、連続ないし近傍領域のデータ転送が行われている場合を空間的局所性があるという。真にランダムに転送されるべきデータというのは少なく、大抵のデータには空間的局所性が存在する。一般的にデータ転送でスループットよりレイテンシ、すなわちデータ転送帯域より転送距離が問題となる場合は、小さなデータを何度も転送するよりも少ない回数でより多くのデータを転送することで効率向上する場合が多い。従って転送元は空間的局所性を期待して未要求の近傍データも同時に送り、キャッシュにより未要求データを保持することで、キャッシュ下位レベルとの転送セット回数を削減しようとする。CPUキャッシュメモリのラインサイズは、この空間的局所性に鑑みて決定される。

1961年 マンチェスタ大学のTom Kilburnらが開発中のコンピュータAtlasに仮想記憶機構を搭載
1962年 Kilburnらが論文"One-level storage system"を発表
1965年 ケンブリッジ大学のMV Wilkesがキャッシュに関する最初の論文"Slave Memories and Dynamic Storage Allocation"を発表(論文ではキャッシュをスレーブメモリと呼んだ)
1965年 ケンブリッジ大学でGordon Scarrottがダイレクトマップ方式の命令キャッシュを実装
1967年 最初のキャッシュ搭載商用マシンIBM System/360 Model 85が完成(16-32KB, 80-160ns)。1968年発売
1968年 IBMのDonald H. GibsonらがIBM System/360 Model 85の性能評価に関する論文"Structural Aspects of the System/360 Model 85 I: General Organization."を発表。そのなかで初めてキャッシュという用語が使用された

バッファオーバーラン(英: buffer overrun)、バッファオーバーフロー(英: buffer overflow)とは、コンピュータのプログラムにおける、設計者が意図していないメモリ領域の破壊が起こされるバグのひとつ、またはそれにより引き起こされた現象を言う。

バッファオーバーランはコンピュータセキュリティ上の深刻なセキュリティホールとなりうるため、バッファオーバーランが起こる可能性のあるコンピュータプログラムはすぐに修正する必要がある。 バッファオーバーランは、現在もっとも重大なセキュリティホールのひとつと考えられている。あるプログラムでバッファオーバーラン脆弱性が発見されると、一般に高い優先度で修正作業が行われ、更新バージョンのプログラムや修正パッチの公開・配布などが行われる。

コンピュータプログラムを作るとき、固定長のバッファとよばれる領域を確保してそこにデータを保存するという手法がよく使われる。

たとえば、電子メールアドレスは200文字を超えないだろうと予想して

200文字分の領域をバッファとして用意する。
ユーザが200文字より長いメールアドレスを入力する。
プログラムがバッファの大きさをチェックせずに入力データを書き込む。
バッファとして確保した領域をはみだしてデータが書き込まれてしまう。
これがバッファオーバーランである。仮にはみ出した部分にプログラムの動作上意味を持つデータがあれば、これを上書きして破壊することにより、プログラムはユーザの意図しない挙動を示すであろう。

このようにバッファオーバーランは、プログラムが用意したバッファの大きさを超えてデータを書き込んでしまうバグである。

C言語の標準入出力関数であるgets関数はバッファ長のチェックを行わないで標準入力をバッファに書き込むので、この関数を使う全てのプログラムには、バッファオーバーランによる不正動作の危険性がある。また使い方が分かりやすいという理由でC言語初心者向けの入門プログラミングでしばしば用いられるscanf関数も書式指定を誤った場合は同じ危険性を持っている[1]。これらの関数を実用的なプログラムで用いる場合には注意が必要である。

次のプログラムはgets関数を用いた例である(セキュリティ上、gets関数はそれ自体をテストする以外の目的で使用されるべきではない。Linux Programmer's Manualには「gets()は絶対に使用してはならない。」と書かれている)。バッファ長として200バイト確保されている。gets関数はバッファの長さについては関知しないため、200バイトを超えても改行文字かEOFが現れなければバッファオーバーランが発生する。

#include <stdio.h>
int main(int argc, char *argv[])
{
char buf[200];
gets(buf);
....
}
gets関数の代わりにfgets関数を用いることで、この問題を回避できる(fgets#getsを置き換える例等を参照)。fgets関数にはバッファのサイズを渡すことができ、このバイト数を超えてバッファに書き込みを行わない。したがってバッファサイズが正しく設定されていれば、fgets関数においてバッファオーバーランは起こり得ない。

これ以外のC言語の標準文字列処理関数の多くにも同様の問題(脆弱性)がある。

オペレーティングシステム(OS)によっては、プログラムのコード領域とデータ領域を区別せず、コードがデータ領域に書かれていてもそのまま実行してしまう物がある。

もっとも典型的なバッファオーバーランは、データ領域のうちでもスタック領域に対するものである。前述のバッファがスタック領域に割り当てられたものである場合(この割当てはC言語の自動変数で典型的である)、はみ出したデータがスタック領域の当該バッファ割当て部分よりも外の部分を書き換えてしまう。一方、スタック領域にはプログラムカウンタにリストアされるべきサブルーチンからのリターンアドレスが格納されているが、そのリターンアドレスをバッファーオーバーランしたデータで書き換えてしまうことになる。これを利用した攻撃をReturn-to-libc攻撃と呼ぶ。

バッファーオーバーラン等の不正動作に対する保護機能がないようなOS上で実行されるアプリケーションソフトウェアでは、プログラム作成者ないし利用ユーザの意図の有無に関わらず、常にこの危険性を含んでいる。現在大衆向けに販売されているOSの多くは、このようなメモリ保護機能を持たないことが問題の根底にある。

クラッカーは、このバッファオーバーランを意図的に起こしてデータの改竄やコンピュータシステムの損壊につながる操作をおこなう(通常は、ワームウイルス等の不正プログラムを作成し、それに攻撃を実行させる)。

通常は、不正アクセスの手段として不正なデータをコンピュータに対して送信すると言うことがあるが、バッファオーバーラン攻撃を行う場合には、送信データに不正なプログラムのコード(シェルコード)を挿入し、さらに前述のスタック領域上のリターンアドレス等を、この不正コードが存在するアドレスに書き換える事等により、任意の不正なコードを相手のコンピュータにおいて実行させ、OS上の管理者権限を不正に奪取するなどさまざまな攻撃を行う。

近年、コンピュータの制御を乗っ取り、攻撃を行うウイルスはバッファオーバーランを利用した物が多い。脆弱性を示すために作られたプログラムExploitを悪用し、そのプログラムにウイルス機能を載せた物が大多数を占める。2003年8月インターネットトラフィックにおいてバックグラウンドノイズとされるトラフィックが1kbps未満から突然30〜40kbpsに跳ね上がった。これはWindowsのRPCサブシステムにおけるバッファオーバーランによるセキュリティホールを攻撃し、制御を乗っ取り自らウイルスを放出するMSBlastウイルスによる攻撃が全世界規模で発生したためである。

C言語でかかれ、古いライブラリ関数を多用している、そして多くの文字列処理を行っている、"sendmail"プログラムは近年こそ毎年のペースまで下がったが、以前は毎月のようにバッファオーバーランによるセキュリティホールが発覚し、修正されていた。そしてsendmailを突破口としてセキュリティを破られたシステムはとても多く、その数はWinnyによる情報流出を上回るものである。このようなセキュリティ上の観点から(またライセンスの関係もあるが)sendmailを標準プログラムから排除する動きがあり、いくつかのOSディストリビューションの標準セットからsendmailは取り除かれてしまった。

バッファオーバーフローに起因する脆弱性を利用したエクスプロイトは、コンピュータ・アーキテクチャオペレーティングシステム、メモリ領域によって大きく内容が異なる。たとえば、ヒープ領域(動的メモリ確保で利用される領域)に対するエクスプロイトはコールスタックに対するそれとは大きく異なる。

悪意のある利用者がスタックベースのバッファオーバーフローを発生させてプログラムの処理を操作する際には、以下のような方法が用いられる。

スタック上でバッファの近くにあるローカル変数の値を上書きして、プログラムの動作を攻撃者にとって有利なように変更する。
スタックフレーム中の戻りアドレスを上書きする。関数から戻る際、攻撃者が指定したリターンアドレス(通常はユーザの入力を格納しているバッファ)から処理が再開されるようにする。
後で実行される関数ポインタ[2]
または例外ハンドラを書き換える。

ここで、ユーザの入力したデータのアドレスは未知であるが、アドレスがレジスタに格納されていることは分かっているという場合には、トランポリン(trampolining)と呼ばれる手法が利用される。この手法では、ユーザの入力したデータにジャンプするオペコードのアドレスをリターンアドレスへ上書きする。例えばアドレスがレジスタRに格納されている場合、jump R(あるいはcall Rなど)というオペコードが格納されているアドレスにジャンプさせることでユーザの入力したデータを実行させる。この手法で使用するオペコードはDLLや実行ファイルの中のものを利用する。ただし、一般的にオペコードのアドレスにヌル文字が含まれていてはならず、また処理に使用するオペコードのアドレスはアプリケーションやオペレーティングシステムのバージョンによって異なる。Metasploitプロジェクトはこのような目的に適したオペコードのデータベースの一つであり、Windowsで使用できるオペコードが記載されている[3]。

名前が似ているスタックオーバーフローと混同しないよう注意すること。

また、このような脆弱性はファジングを使用して発見されることが多い[4]。

ヒープ領域で発生するバッファオーバーフローはヒープオーバーフローと呼ばれ、エクスプロイトもスタックベースのオーバーフローとは異なる。ヒープ領域上のメモリはアプリケーションの実行時に動的に確保され、一般的にはプログラムのデータが格納される。エクスプロイトは、何らかの方法でこのデータを破壊し、アプリケーションが内部構造(例えば連結リストのポインタ)を上書きするように仕向けることで行われる。基本的なヒープオーバーフローのテクニックでは、動的メモリ確保で使われる連結リストの連結部分(mallocメタデータなど)を上書きし、その結果のポインタを使ってプログラムの関数ポインタを上書きする。

マイクロソフトのGDI+におけるJPEG処理の脆弱性は、ヒープオーバーフローの危険性を示す例といえる[5]。

バッファの読み込みや実行の前に行われるバッファの操作が原因で、エクスプロイトが失敗する場合もある。このような操作を利用してエクスプロイトの脅威を軽減することはできるが、それでもエクスプロイトが不可能にはならない。バッファに対する操作としては大文字小文字変換、メタ文字の除去、非英数字のフィルタリングなどがあるが、これらの処理をくぐり抜けるテクニックも存在する(英数字コード(w:alphanumeric code)、ポリモルフィックコード、自己書き換えコード、Return-to-libc攻撃など)。また、侵入検知システムをすり抜けるのにも同様の方法が使用できる。また場合によっては、コードがUnicodeエンコードされている場合など、実際にはリモートから任意のコードの実行が可能であるにも関わらず、発見者によってただのDoSであると不正確に伝えられているような脆弱性もある[6]。

実世界においてエクスプロイトを確実に実行させるためには、克服しなければならない様々な課題が存在する。例えば、アドレス中のNULLバイト、シェルコードの位置のばらつき、環境ごとの差異、各種の攻撃対策などが挙げられる。

NOPスライドは、スタックバッファオーバーフローを利用するテクニックとして最古のものであり、また最も広く知られているものでもある[7]。

このテクニックでは、攻撃のためにはバッファの正確なアドレスを知る必要があるという問題に対し、攻撃のターゲットとなる領域を拡大させることで問題を解決する。このためには、スタック中のかなり広い区域がNOP命令で破壊されている必要がある。攻撃者が入力したデータの末尾(NOP命令の後)には、シェルコードが位置するバッファの先頭への相対ジャンプ命令が格納されている。ここで、NOP命令の集まりはNOPスレッドと呼ばれるが、これは戻りアドレスをNOP領域のどのアドレスで上書きしたとしても、NOP命令の上を「スライド」していき、末尾のジャンプ命令により実際の悪意あるコードへ転送が行われるためである。 このテクニックを利用すれば、攻撃者は比較的小さなシェルコードの場所を推測する代わりに、スタック上のどこにNOPスレッドがあるかだけを推測するだけでよい[8]。

このテクニックは頻繁に使用されるため、このパターンのNOP命令は多くの侵入防止システムベンダーでシェルコードの判定に使用されている。ただし、NOPスライディングを通常のNOP命令だけで構成する必要はないという点には注意すべきである。シェルコードの実行と直接関係ない箇所では、マシンの状態を変更しなければどのような命令でもNOP命令の代わりに使用できる。このため、エクスプロイトの作成者側では、シェルコードの実行に影響を及ぼさない任意の命令をランダムに選んでNOPスレッドを構成することが常套手段となっている[9]。

この手法は攻撃が成功する確率を劇的に増加させるが、問題がないわけではない。このテクニックではスタック中でNOPスレッドの領域を指すオフセットを推測することになるため、このテクニックを使用したエクスプロイトはある程度運に依存することになる[10]。この推測を誤ると、通常の場合ターゲットとなるプログラムはクラッシュし、システムアドミニストレータに攻撃の動きを警戒されることになってしまう。またそれとは別に、NOPスレッドが非常に多くのメモリを必要とするという問題もある。これはNOPスレッドが役に立つためにはそのサイズが十分に大きい必要があるためだが、これはNOPスライドで影響を受けるバッファの割り当てサイズが小さく、かつ現在のスタックの深さが浅い場合(すなわち、現在のスタックフレームの末尾からスタックの先頭までの間に十分なスペースがないとき)に問題となる。こういった問題にもかかわらずNOPスライドがいまだに重要なテクニックであり続けているのは、所与のプラットフォーム、環境、状況によってはNOPスライドが唯一利用可能な攻撃方法となる場合がしばしばあるためである。

jump to registerとは、NOPスレッドの格納領域もスタックのオフセットの推測も必要とせずに、スタックバッファオーバーフローを用いた確実なエクスプロイトを可能にするテクニックである。戦略としては、リターンポインタを上書きして、レジスタへ格納されている既知のポインタへのジャンプを起こさせる(このポインタはコントロールされたバッファ、ひいてはシェルコードを指している)。例えばレジスタAがバッファの先頭へのポインタを格納しているとすると、そのときレジスタAをオペランドにとる任意のjumpまたはcall命令が実行フローの支配権を得るのに使用できる[11]。

実際には、特定のレジスタへのジャンプ命令を意図的に含めないようにしたプログラムもある。よくある解決法としては、プログラムのメモリ中の固定の位置にあるオペコードの中に、使える命令のインスタンスが意図せず作られているのを探してくる方法がある。左図はそのような意図しないインスタンスの例で、i386のjmp esp命令が作られている。この命令のオペコードはFF E4である[12]。

この2バイトの並びは、call DbgPrint命令の先頭から1バイトオフセットした位置(アドレス0x7C941EED)にある。攻撃者がプログラムのリターンアドレスをこのアドレスで上書きしたら、プログラムはまず最初に0x7C941EEDへジャンプし、オペコードFF E4をjmp espと解釈する。そしてスタックの先頭へジャンプし、攻撃者の指定したコードを実行する[13]。

このテクニックが利用可能な場合、脆弱性の重大性は相当に高くなる。これは、処理を自動化してもほぼ確実に攻撃が成功するほどエクスプロイトの成功率が高くなるためである。そのため、これはスタックバッファオーバーフロー脆弱性を利用するインターネットワームにおいて最もよく使われるテクニックとなっている[14]。

また、この方法を使えば、Windowsプラットフォームにおいては上書きしたリターンアドレスの後ろにシェルコードを配置することもできる。実行ファイルは多くの場合アドレス0x00400000から配置され、またx86はリトルエンディアンアーキテクチャのため、リターンアドレスの末尾のバイトは必ずNULLになる。そのため、バッファへのコピーはそこで終了されてしまい、それ以降には何も書き込まれない。これにより、シェルコードのサイズはバッファのサイズに制限されることになるが、これは場合によっては非常に厳しい制限となる。一方DLLはハイメモリ(アドレス0x01000000より上)に配置されるため、アドレスにNULLバイトが含まれないようにできる。そのため、この方法であれば上書きするリターンアドレスがNULLバイト(あるいはその他の禁止された文字)を含まないようにできる。このようにDLLを使った方法はDLLトランポリン(DLL Trampolining)などとも呼ばれる。