(57)【要約】      （修正有）【課題】  プロセッサの内部構造に大きな影響を与えることなく、主にキャッシュ・メモリに対して改良を加えることでスタック・スマッシングを判別可能なキャッシュ・メモリ及びその制御方法を提供する。【解決手段】  プロセッサからキャッシュ・メモリに書き込むべきデータが関数戻りアドレス値である場合には、通常通りキャッシュ・メモリに書き込むべきデータをオリジナルデータとして書き込むと共に、当該オリジナルデータと同一内容のレプリカデータを作成しオリジナルデータと対応付けてキャッシュ・メモリに書き込む。オリジナルデータがプロセッサから関数戻りアドレスとして読み出される場合には、オリジナルデータとレプリカデータとが一致するか否かを比較する。スタック・スマッシングがなされた場合にはオリジナルデータが改ざんされ、レプリカデータと比較した場合に不一致となって改ざんがあったことが判別できる。【選択図】  図２
2005338946.tif 000002
【特許請求の範囲】
【請求項１】
プロセッサからキャッシュ・メモリに書き込むべきデータがあるとき、当該書き込むべきデータが関数戻りアドレス値である場合には、通常通りキャッシュ・メモリに書き込むべきデータをオリジナルデータとして書き込むと共に、当該オリジナルデータと同一内容のレプリカデータを作成しオリジナルデータと対応付けてキャッシュ・メモリに書き込み、
オリジナルデータがプロセッサから関数戻りアドレスとして読み出されるとき、当該オリジナルデータに対応するレプリカデータを読み出し、オリジナルデータとレプリカデータとが一致するか否かを比較することを
特徴とするキャッシュ・メモリ制御方法。
【請求項２】
前記請求項１に記載のキャッシュ・メモリ制御方法において、
前記レプリカデータのキャッシュ・メモリからの追い出しを禁止することを
特徴とするキャッシュ・メモリ制御方法。
【請求項３】
プロセッサからキャッシュ・メモリに書き込むべきデータがあるとき、当該書き込むべきデータが関数戻りアドレス値である場合には、通常通りキャッシュ・メモリに書き込むべきデータをオリジナルデータとして書き込むと共に、当該オリジナルデータと同一内容のレプリカデータを複数作成しオリジナルデータとそれぞれ対応付けてキャッシュ・メモリに書き込み、
オリジナルデータがプロセッサから関数戻りアドレスとして読み出されるとき、当該オリジナルデータに対応するレプリカデータを読み出し、オリジナルデータと少なくとも１つのレプリカデータとが一致するか否かを比較することを
特徴とするキャッシュ・メモリ制御方法。
【請求項４】
前記請求項１または３に記載のキャッシュ・メモリ制御方法において、
レプリカデータの書き込みに伴い、LRUまたはMRUアルゴリズムに基づきキャッシュ・メモリ中からデータの追い出しを行い当該追い出し部分にレプリカデータの書き込みを行うことを
特徴とするキャッシュ・メモリ制御方法。
【請求項５】
前記請求項１ないし４に記載のキャッシュ・メモリ制御方法において、
前記オリジナルデータとの比較が終了したレプリカデータが存在する場合には、かかるレプリカデータを優先的に追い出し対象とすることを
特徴とするキャッシュ・メモリ制御方法。
【請求項６】
プロセッサが実行する命令列を監視する命令監視手段を設け、当該命令監視手段が現在のメモリ・アクセスが関数戻りアドレスを対象としていることを検出する前記１ないし５に記載のキャッシュ・メモリ制御方法を適用したキャッシュ・メモリ。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、スタック・スマッシングに対する防御方法に関し、解析/変換を必要としない動的検出型の防御方法となるキャッシュ・メモリ及びその制御方法に関する。
【背景技術】
【０００２】
近年、バッファ・オーバフローの脆弱性を活用した悪質プログラムによる被害が急増している。例えば、代表的なものとして2001年に猛威を振ったCode Redや、2003年のBlasterなどがある。悪質プログラムは、攻撃対象となるコンピュータが正規アプリケーションを実行している最中にバッファ・オーバフローを引き起こさせ、強制的にプログラムの実行制御を乗っ取る。したがって、特権モードでの実行中にバッファ・オーバフローが発生した場合、悪質プログラムは特権モードで実行されることになる。その結果、ファイルの削除や改ざんが可能となり多大なる被害をもたらす。CERTによって発せられた勧告(1996〜2001年)の内、バッファ・オーバフローに関連するものの割合を図1０に示す。図から分かるように、多くの悪質プログラムはバッファ・オーバフローの脆弱性を利用しており、その防御策が極めて重要となる。
【０００３】
悪質プログラムは、関数呼び出し後にバッファ・オーバフローを引き起こしてスタックを破壊する(スタック・スマッシングという)。そして、関数呼出し側への戻りアドレスを悪質プログラム・コードの先頭アドレスへと改ざんすることで、プログラムの実行制御を乗っ取る。このようなスタック・スマッシングの原因となるバッファ・オーバフローの脆弱性は、strcpyやstrcatなどのC標準ライブラリ内に存在する。これらの関数では、文字列をローカル変数に代入する際に領域サイズのチェックを行わない。そのため、ローカル変数で指定したバッファ・サイズより大きな文字列等を代入した場合、確保されたローカル変数メモリ領域の境界を越えて書込みを行う。
【０００４】
スタック・スマッシング発生時の様子を図１１に示す。ここでは、strcpyを用いて文字列コピーを行う関数gが、関数fによって呼出される場合を想定している。通常、関数gが呼出された際、関数fへの戻りアドレスをスタックに保存する。そして、関数gでの処理終了後、この戻りアドレスをPCに復元する事で関数呼出し側へと実行制御が移る。これに対し、バッファ境界をチェックしない文字列コピーによりスタック・スマッシングが発生した場合、スタック領域に対して悪質プログラム・コードが上書きされる。また、関数fへの戻りアドレスが悪質コードの先頭アドレスへと改ざんされる。その結果、呼出し元関数fへ復帰する際には改ざんされた戻りアドレスが用いられ、その結果としてスタック内部の悪質プログラム・コードへと実行制御が移る。
【０００５】
これまでに、スタック・スマッシングに対する様々な防御方法が提案された。これらは、バッファ・オーバフロー回避のためのコード解析や変換の有無、ならびに、スタック・スマッシングの検出時期によって以下のように分類できる。
【０００６】
（１）静的解析かつ静的検出型：プログラム・コードを静的に解析してバッファ・オーバフロー発生可能場所を検査する。例えば、文字列操作に限定し、「コピー元の文字列サイズ」が「コピー先のローカル変数領域サイズ」を超えていないか検査する方法などがある（参考文献１：D.Wagner, J.S.Foster, E.A.Brewer, and A.Aiken, "A First Step Towards Automated Detection of Buffer Overrun Vulnerabilities," Proc. of the Network and Distributed System Security Symposium, Feb. 2000.）。
【０００７】
（２）静的解析/変換かつ動的検出型：プログラムの静的解析により、スタック・スマッシングを検出するためのコード変換をコンパイル時に行う。参考文献２（U.Erlingsson and F.B.Schneider, "SASI Enforcement of Security Policies: A Retrospective," Proc. of the  workshop on New security paradigm, 1999.）で提案されたSASIでは、実行の振舞いを監視するリファレンス・モニタ(RM)をコード中に挿入する。例えば、バッファ・オーバフローの危険性があるコード部分に対し、領域チェックを行うためのRMコードを挿入する。また、参考文献３（C.Cowan, C.Pu, D.Maier, H.Hinton, J.Walpole, P.Bakke, S.Beattie, A.Grier, P.Wagle, and Q.Zhang, "StackGuard: Automatic Adaptive Detection and Prevention of Buffer-Overflow Attacks," Proc. of 7th USENIX Security Symposium, Jan, 1998.）で提案されたStackGuardでは、canary wordと呼ばれる乱数を生成して戻りアドレスと共にスタックへ格納する。canaryは戻りアドレスの直後にプッシュされるため、スタック・スマッシングが発生した場合にはcanary値も改ざんされる。よって、関数呼出し時と復帰時のcanary値を比較する事で戻りアドレスの改ざんを検査できる。
【０００８】
（３）動的解析/変換かつ動的検出型：プログラム実行中にコードの解析や変換を行う。先に説明した静的解析や変換を行う方式とは異なり、オブジェクト・コードの互換性を保つ事ができる。具体的には、バイナリ変換を行うことで、リファレンス・モニタに相当するバッファ・オーバフロー検査用コードを動的に生成する方法などがある（参考文献４：A.Baratloo, N.Singh, and T.Tsai, "Transparent Run-Time Defense Against Stack Smashing Attacks," Proc. of 2000 USENIX Annual Technical Conference, June 2000.）（参考文献５：K.Scott and J.Davidson, "Safe Virtual Execution Using Software Dynamic Translation," Proc. of the 18th Computer Security Applications Conference, Dec. 2002.）。
【０００９】
（４）解析/変換を必要としない動的検出型：コード解析や変換を行う事無く、戻りアドレス保護を実現する方式である。ソフトウェア・アプローチとしては、安全性を保障したCライブラリ(libsafeと呼ばれる)を提供する方法や、OSの介在により動的にcanaryを追加する方法などが提案されている（参考文献４参照）（参考文献６：M.Frantzen and M.Shuey, "StackGhost: Hardware Facilitated Stack Protection," Proc. of the 10th USENIX Security Symposium, Aug. 2001.）。一方、ハードウェア・アプローチとしては、プロセッサ内部に戻りアドレス専用スタックであるSRAS(Secure Return Address Stack)を搭載する方法が提案されている（参考文献７：R。B。Lee、 D。K。Karig、 J。P。McGregor、 and Z。Shi、 "Enlisting Hardware Architecture to Thwart Malicious Code Injection、" Proc。 of the Int。 Conf。 on Security in Pervasive Computing、 Mar。 2003。）。戻りアドレスをプッシュする際、それと同時にSRASにも戻りアドレスを書込む。そして、関数から復帰する時、メモリ・スタックならびにSRASからポップした戻りアドレスを比較する。比較結果が不一致であればスタック・スマッシングが発生していることになる。
【非特許文献１】R。B。Lee、 D。K。Karig、 J。P。McGregor、 and Z。Shi、 "Enlisting Hardware Architecture to Thwart Malicious Code Injection、" Proc。 of the Int。 Conf。 on Security in Pervasive Computing、 Mar。 2003。
【発明の開示】
【発明が解決しようとする課題】
【００１０】
本発明では、前記分類中（４）解析/変換を必要としない動的検出型のハードウェア・アプローチの１つである前記SRASに着目した。このSRASによれば、オブジェクト・コードの互換性を完全に保つことができ、また、CライブラリやOSといったシステム・ソフトウェアの変更は伴わない。しかしながら、前記したようにSRASは、小容量スタック・メモリとしてプロセッサ内部に実装され、関数呼出しのネストに伴い容量が不足した場合には，保護された安全な主記憶領域との間でエントリの追出し/リフィルが行われるという課題を有する。また、SRASはスタックのため、単体でLIFO動作と異なる関数制御(例えばsetjmpやlongjmp)に対応することができないという課題を有する。さらに、プロセッサの内部構造に大きな影響を与えるという課題を有し、実製品化導入の困難性を有している。
【００１１】
本発明は前記課題を解決するためになされ、プロセッサの内部構造に大きな影響を与えることなく、主にキャッシュ・メモリに対して改良を加えることでスタック・スマッシングを判別可能なキャッシュ・メモリ及びその制御方法を提供することを目的とする。
【課題を解決するための手段】
【００１２】
本発明に係るキャッシュ・メモリ制御方法は、プロセッサからキャッシュ・メモリに書き込むべきデータがあるとき、当該書き込むべきデータが関数戻りアドレス値である場合には、通常通りキャッシュ・メモリに書き込むべきデータをオリジナルデータとして書き込むと共に、当該オリジナルデータと同一内容のレプリカデータを作成しオリジナルデータと対応付けてキャッシュ・メモリに書き込み、オリジナルデータがプロセッサから関数戻りアドレスとして読み出されるとき、当該オリジナルデータに対応するレプリカデータを読み出し、オリジナルデータとレプリカデータとが一致するか否かを比較するものである。このように本発明においては、プロセッサからキャッシュ・メモリに書き込むべきデータがあるとき、当該書き込むべきデータが関数戻りアドレス値である場合には、通常通りキャッシュ・メモリに書き込むべきデータをオリジナルデータとして書き込むと共に、当該オリジナルデータと同一内容のレプリカデータを作成しオリジナルデータと対応付けてキャッシュ・メモリに書き込み、オリジナルデータがプロセッサから関数戻りアドレスとして読み出されるとき、当該オリジナルデータに対応するレプリカデータを読み出し、オリジナルデータとレプリカデータとが一致するか否かを比較するので、スタック・スマッシングがなされた場合にはオリジナルデータが改ざんされ、レプリカデータと比較した場合には不一致となって改ざんがあったことを判別することができる。特に、本発明はキャッシュ・メモリ制御方法を改良してなされるものであり、プロセッサの内部構造に与える影響が少なく導入も行い易い。したがって、アウト・オブ・オーダ実行や高度な分岐予測機構を搭載した複雑なプロセッサに対しても容易に適用できる。また、前記SRASと異なり、LIFO動作と異なる関数制御(例えばsetjmpやlongjmp)の場合でもソフトウェアの介在無しに対応できる。さらには、前記したSRASと異なり、キャッシュ・メモリ内部のレプリカデータを作成しているため、大量の戻りアドレスを格納することができ、追い出しにも該当し難い。
【００１３】
また、本発明に係るキャッシュ・メモリ制御方法は必要に応じて、前記レプリカデータのキャッシュ・メモリからの追い出しを禁止するものである。このように本発明においては、レプリカデータのキャッシュ・メモリからの追い出しを禁止するので、レプリカデータのキャッシュ・メモリからの追い出しがなく、レプリカデータは必ずキャッシュ・メモリ上に存在し、オリジナルデータとの比較を必ず行うことができ、すなわち、スタック・スラッシングの発生を常に判別することができる。
【００１４】
また、本発明に係るキャッシュ・メモリ制御方法は、プロセッサからキャッシュ・メモリに書き込むべきデータがあるとき、当該書き込むべきデータが関数戻りアドレス値である場合には、通常通りキャッシュ・メモリに書き込むべきデータをオリジナルデータとして書き込むと共に、当該オリジナルデータと同一内容のレプリカデータを複数作成しオリジナルデータとそれぞれ対応付けてキャッシュ・メモリに書き込み、オリジナルデータがプロセッサから関数戻りアドレスとして読み出されるとき、当該オリジナルデータに対応するレプリカデータを読み出し、オリジナルデータと少なくとも１つのレプリカデータとが一致するか否かを比較するものである。このように本発明においては、プロセッサからキャッシュ・メモリに書き込むべきデータがあるとき、当該書き込むべきデータが関数戻りアドレス値である場合には、通常通りキャッシュ・メモリに書き込むべきデータをオリジナルデータとして書き込むと共に、当該オリジナルデータと同一内容のレプリカデータを複数作成しオリジナルデータとそれぞれ対応付けてキャッシュ・メモリに書き込み、オリジナルデータがプロセッサから関数戻りアドレスとして読み出されるとき、当該オリジナルデータに対応するレプリカデータを読み出し、オリジナルデータと少なくとも１つのレプリカデータとが一致するか否かを比較するので、レプリカデータを複数作成し、オリジナルデータと対応付けてキャッシュ・メモリに書き込まれており、一部のレプリカデータがキャッシュ・メモリから追い出しがなされた場合でも残りのレプリカデータでオリジナルデータとの比較ができ、オリジナルデータとの比較ができるように信頼性を向上させることができる。ここで、作成される複数レプリカデータの数は多いほど信頼性を向上させることができるが、キャッシュ・メモリ上の領域を確保する必要があり追い出しの発生率を高める要因ともなる。
【００１５】
また、本発明に係るキャッシュ・メモリ制御方法は必要に応じて、レプリカデータの書き込みに伴い、LRUまたはMRUアルゴリズムに基づきキャッシュ・メモリ中からデータの追い出しを行い当該追い出し部分にレプリカデータの書き込みを行うものである。MRUアルゴリズムに基づき追い出しを行った場合には、レプリカデータが追い出しの対象とされ難くなるため安全性は向上する。しかしながら、キャッシュ・ヒット率が低下する。一方、LRUアルゴリズムに基づき追い出しを行った場合には、レプリカデータが追い出しの対象とされ易くなるため安全性は低下するものの、キャッシュ・ヒット率が改善する。
【００１６】
また、本発明に係るキャッシュ・メモリ制御方法は必要に応じて、前記オリジナルデータとの比較が終了したレプリカデータが存在する場合には、かかるレプリカデータを優先的に追い出し対象とするものである。このように本発明においては、前記オリジナルデータとの比較が終了したレプリカデータが存在する場合には、かかるレプリカデータを優先的に追い出し対象とするので、通常キャッシュ・メモリは採用するLRUアルゴリズムに基づき追い出し対象となるデータを特定するが、既に役目を果たしたレプリカデータが再び使用される可能性が低く、かかるレプリカデータを追い出し対象とすることで、キャッシュ・ヒット率を向上させることができる。
【００１７】
また、本発明に係るキャッシュ・メモリは必要に応じて、プロセッサが実行する命令列を監視する命令監視手段を設け、当該命令監視手段が現在のメモリ・アクセスが関数戻りアドレスを対象としていることを検出するものである。このように本発明においては、プロセッサが実行する命令列を監視する命令監視手段を設け、当該命令監視手段が現在のメモリ・アクセスが関数戻りアドレスを対象としていることを検出するので、プロセッサ自ら関数戻りアドレスを対象とするメモリ・アクセスであることをキャッシュ・メモリに出力信号を出力して知らせることなく、キャッシュ・メモリが主体的となって、命令監視手段によりプロセッサからのメモリ・アクセスが関数戻りアドレスを対象とするものか否かを判別することができ、プロセッサが本発明に係るキャッシュ・メモリ特有の動作を行う必要がなく、すなわち、プロセッサに設計変更が生じることなく導入が行い易い。
【発明を実施するための最良の形態】
【００１８】
（本発明の第１の実施形態）
本発明の第１の実施形態に係るキャッシュ・メモリ制御方法を図１ないし図４に基づき説明する。図１は一般のセットアソシエイティブ方式のキャッシュ・メモリの構成図、図２は本実施形態に係るセットアソシエイティブ方式のキャッシュ・メモリの構成図及び図３及び図４は本実施形態に係るキャッシュ・メモリの動作フローチャートである。
【００１９】
本実施形態に係るキャッシュ・メモリ制御方法は、プロセッサからキャッシュ・メモリに書き込むべきデータがあるとき、この書き込むべきデータが関数戻りアドレス値である場合には、通常通りキャッシュ・メモリに書き込むべきデータをオリジナルデータとして書き込むと共に、このオリジナルデータと同一内容のレプリカデータを作成しオリジナルデータと対応付けてキャッシュ・メモリに書き込み、オリジナルデータがプロセッサから関数戻りアドレス値として読み出されるとき、オリジナルデータに対応するレプリカデータを読み出し、オリジナルデータとレプリカデータとが一致するか否かを比較する構成である。
【００２０】
このキャッシュ・メモリ制御方法を具体的にキャッシュ・メモリ連装方式の１つであるセットアソシエイティブ方式のキャッシュ・メモリに適用した場合について説明する。ここで、まず、一般のセットアソシエイティブ方式のキャッシュ・メモリについて制御方法の観点から図１に基づき説明を行う。なお、他のキャッシュ・メモリ連装方式であっても適用することができ、例えば、フルアソシエイティブ方式のキャッシュ・メモリ連装方式には適用することができる。
【００２１】
一般のセットアソシエイティブ方式のキャッシュ・メモリは、図１に示すように、複数のタグ１１（tag）を配列要素として持つタグ部１２と、かかるタグ１１に対応して所定データ領域を確保しているデータ領域２１を配列要素として持つデータ領域部２２とから構成されるウェイ３１（way）を複数有する。また、タグ１１（又はデータ領域）の配列要素番号順に、インデックスが割り付けられている。そして、タグを上位ビットとし、インデックスを下位ビットとするメモリ参照アドレスが示すメモリのデータをキャッシュ・メモリはデータ領域２１に書き込んでいる。このセットアソシエイティブ方式のキャッシュ・メモリの動作を、ストア（Store）、ロード（Load）の動作に分けて順に説明する。まず、ストアは、プロセッサからデータと共にメモリ参照アドレスがキャッシュ・メモリに対して送られてくる。キャッシュ・メモリはこのメモリ参照アドレスを所定上位ビットをタグとし、残りの下位ビットをインデックスとし、インデックスに基づきセット４１が特定され、タグが同一のウェイ３１があれば選択し、かかる同一のウェイ３１がない場合には適当にウェイ３１を選択する。選択されたウェイ３１のタグ部１２に書き込み、さらに、このタグ部１２に対応するデータ領域２１に対してプロセッサからのデータを上書きする。ここで、キャッシュ・メモリの書き込み方式はライトバック方式とする。次にロードは、プロセッサからメモリ参照アドレスがキャッシュ・メモリに対して送られてくる。キャッシュ・メモリはこのメモリ参照アドレスをストアと同様にタグとインデックスに分け、インデックスに対応するセット４１を読み出し、読み出された各データ領域２１のデータのうち比較器において各データのタグとメモリ参照アドレス中のタグとを比較し該当するデータをプロセッサに送り出す。それと同時に、比較器において送り出された各データのタグとメモリ参照アドレス中のタグとを比較し、該当するデータがあるか否かの旨をプロセッサに通知する。
【００２２】
次に、本発明のキャッシュ・メモリについて図２に基づき前記一般のセットアソシエイティブ方式のキャッシュ・メモリ（以下、一般のキャッシュ・メモリとする）と比較しながら説明する。本発明のキャッシュ・メモリにあっては、読み出し専用のレプリカデータ（セットアソシエイティブ方式では各データ領域２１のデータをラインと呼ぶ場合もあり、この呼称に従えばレプリカラインとなる）を同一セット４１内に作成した点、ウェイ３１の各タグとデータ領域２１の組合せに対してレプリカデータ用のフラグ（R-flag）を設けた点、レプリカデータ用のマルチプレクサ（Replica-MUX）を備えた点、比較器においてタグの照合するだけでなく前記レプリカデータ用のフラグも照合する点、さらに、比較器により照合し読み出されたオリジナルデータとレプリカデータの比較を行うデータ内容比較器５１を備えた点が、前記一般のキャッシュ・メモリとの相違点となる。この相違により、セットアソシエイティブ方式において、前記したようなレプリカデータをオリジナルデータと対応付け、また、オリジナルデータとレプリカデータとが一致するか否かを比較することが可能となる。ただし、一つの実装形式に過ぎず、本発明がこの実装方式に限定されるものではない。
レプリカデータ用のフラグは、対応するデータ領域２１内のデータがレプリカデータであるか否かを示すものであり、１ビットからなる。
【００２３】
また、前記一般のキャッシュ・メモリは、データ領域２１に書き込む又は読み出す対象が関数戻りアドレスか否かに拘らず、同じようにストア又はロードを行っているが、本発明のキャッシュ・メモリは、書き込むべきデータが関数戻りアドレス値である場合、関数戻りアドレス値として読み出される場合に処理を切り分けているため、対象となるデータが関数戻りアドレス値であるか否かを判断する必要がある。プロセッサは自己の動作であるため、簡易にはプロセッサの通知によりキャッシュ・メモリは前記関数戻りアドレス値であるか否かを判断することができる。より望ましくは、キャッシュ・メモリがプロセッサの通知を受けることなく単独で、例えば、プロセッサの命令種別に基づき判断したり、または、プロセッサ内の関数戻りアドレス専用のレジストを見張っておき、かかるレジストにデータが書き込まれキャッシュ・メモリに送り出されることにより、実現することができる。このような実現方法によれば、プロセッサの本キャッシュ・メモリによる仕様変更は最小限に抑えられるという長所を有する。
【００２４】
次に、本実施形態に係るキャッシュ・メモリの動作について図３及び図４に基づき説明する。ここで、キャッシュ・ヒットの場合について説明するが、ミスの場合でもライン・リプレイスがなされることを除けば、同様の動作となる。
【００２５】
まず、キャッシュ・メモリは、プロセッサからの通知に基づき関数戻りアドレス値を対象とするストア若しくはロードであるか否かを判断し（ステップ１０１）、関数戻りアドレス値を対象とするものではないと判断した場合には、前記した通りの一般のキャッシュ・メモリの動作がなされてストア若しくはロードを行う。ここで、関数戻りアドレス値を対象としなければ、レプリカデータ用の動作はなされない。前記ステップ１０１において、キャッシュ・メモリにより関数戻りアドレス値を対象とするものであると判断された場合には、操作命令がストアかロードのどちらであるかを判断する（ステップ１０２）。キャッシュ・メモリがストアと判断した場合には、一般のキャッシュ・メモリと同様に、メモリ参照アドレスの中のインデックスを用いてアクセス対象となるセット４１（参照セットする）を特定する（ステップ１０３）。そして、特定された参照セット内において、同一タグ１１を有し、レプリカデータ用のフラグが無効であるデータ領域２１に関数戻りアドレス値をオリジナルデータとして書き込む（ステップ１０４）。
【００２６】
ここまでの動作説明ではキャッシュ・ミスを想定していないが、前記オリジナルデータでキャッシュ・ミスが生じる場合を想定する場合には、特定された参照セット内において、同一タグ１１を有し、レプリカデータ用のフラグが無効であるデータ領域２１があるか否かを判断し、あると判断された場合に関数戻りアドレス値をオリジナルデータとして書き込み、ないと判断された場合にMRUアルゴリズムに基づきウェイ３１を選択し、かかるウェイ３１のデータ領域２１に関数戻りアドレス値をオリジナルデータとして書き込むといった動作が挿入された構成となる。
【００２７】
次に、前記参照セットにおいて、同一タグ１１を有し、レプリカデータ用のフラグが有効であるレプリカデータ用のデータ領域２１があるか否かを判断する（ステップ２０１）。かかるレプリカデータ用のデータ領域２１があると判断した場合には、かかるレプリカデータ用のデータ領域２１に前記オリジナルデータと同一の関数戻りアドレス値を書き込む（ステップ２０２）。ステップ２０１において、かかるレプリカデータ用のデータ領域２１がないと判断した場合には、MRUアルゴリズムに基づきウェイ３１を選択し、かかるウェイ３１のデータ領域２１に前記オリジナルデータと同一の関数戻りアドレス値を書き込む（ステップ２０３）。ここで、書き込んだデータ領域２１に対応するレプリカデータ用のフラグが無効の場合には、有効にしておく。また、MRUアルゴリズムを選択したのは、レプリカデータがライン・リプレイスの対象となり難くなり、安全性が向上するからである。しかしながら、キャッシュ・ヒット率が低下する可能性がある。一方、LRUアルゴリズムを採用していれば、レプリカデータがライン・リプレイスの対象となり易くなり、安全性は低下するものの、キャッシュ・ヒット率の低下を小さくすることができる。
【００２８】
前記ステップ１０２において、操作命令がロードであると判断した場合には、プロセッサからのメモリ参照アドレスからインデックスを導き、かかるインデックスから参照セットを特定する（ステップ３０１）。参照セットの全データ領域２１のデータとタグ１１とを読み出す（ステップ３０２）。比較器においてメモリ参照アドレスのタグと読み出されたタグ１１とを比較し、タグが同一のデータをプロセッサに送り出す（ステップ３０３）。ここで、キャッシュ・ミスが生じた場合には、ライン・リプレイスがなされる。
【００２９】
次に、参照セットにおいて、同一タグを有し、レプリカデータ用のフラグが有効であるレプリカデータ用のデータ領域２１があるか否かを判断する（ステップ４０１）。かかるレプリカデータ用のデータ領域２１がない場合には、その旨（単にレプリカデータがないだけでなく、レプリカデータがないため安全性を保障することができない旨であってもよい）をプロセッサに伝える（ステップ４０２）。かかるレプリカデータ用のデータ領域２１がある場合には、かかるデータ領域２１のレプリカデータをデータ内容比較器５１に出力する（ステップ４０３）。データ内容比較器５１は、プロセッサに出力されたオリジナルデータをも受け取り、入力されたレプリカデータとの比較を行う（ステップ４０４）。データ内容比較器５１がオリジナルデータとレプリカデータとが一致していると判断した場合には、何もせずに終了する（ステップ４０５）。前記ステップ４０４において、データ内容比較器５１がオリジナルデータとレプリカデータとが一致していないと判断した場合には、プロセッサにその旨（単に、一致していないだけでなく、スタックスマッシングが発生している可能性がある旨を伝える）を出力して終了する（ステップ４０６）。
【００３０】
前記ステップ４０５においては、安全である旨のSafe信号をプロセッサに出力してもよい。この場合であっても、プロセッサはSafe信号を入力されるまで待つ必要はなく、少なくとも悪質コードに制御が移行する前までにプロセッサが認識できればよい。このようにSafe信号を導入した場合であっても、キャッシュ・アクセス時間の増加は殆んど生じない。
【００３１】
このように本実施形態に係るキャッシュ・メモリの制御方法によれば、プロセッサからキャッシュ・メモリに書き込むべきデータがあるとき、当該書き込むべきデータが関数戻りアドレス値である場合には、通常通りキャッシュ・メモリに書き込むべきデータをオリジナルデータとして書き込むと共に、当該オリジナルデータと同一内容のレプリカデータを作成しオリジナルデータと対応付けてキャッシュ・メモリに書き込み、オリジナルデータがプロセッサから関数戻りアドレスとして読み出されるとき、当該オリジナルデータに対応するレプリカデータを読み出し、オリジナルデータとレプリカデータとが一致するか否かを比較するので、スタック・スマッシングがなされた場合にはオリジナルデータが改ざんされ、レプリカデータと比較した場合には不一致となって改ざんがあったことを判別することができる。
【００３２】
なお、本実施形態においては、関数戻りアドレス値を対象としないストアである場合にはレプリカデータ用のフラグを用いていないが、参照セットを特定した後のウェイ３１を選択する場合に、かかるレプリカデータ用のフラグを見るようにすることもでき、すなわち、レプリカデータ用のフラグが有効となっている場合には、かかるデータ領域２１にデータを書き込まない構成にすることもでき、常に、レプリカデータがキャッシュ・メモリ上にあることが保障され、必ず、オリジナルデータとレプリカデータとの比較が可能となる。このとき、関数戻りアドレスを対象とするロードが終了した後に、かかる関数戻りアドレスに係るレプリカデータ用のフラグを無効にする必要がある。それは、かかるレプリカデータ用のフラグにより、かかるラインにはライン・リプレイスが生じることなく、プロセスの終了までキャッシュ・メモリが解放されなくなるからである。
【００３３】
また、本実施形態においては、キャッシュ・メモリがLRUアルゴリズムに基づきライン・リプレイスの対象とするラインを決定することができるが、既に関数戻りアドレスがロードされていて使用済みのレプリカデータが存在する場合には、かかるレプリカデータを優先的にライン・リプレイスの対象とすることができる。この実現は、LRUアルゴリズムを構成するフラグ、若しくは、表の内容を変更することにより実現することができる。これによれば、再び書き込まれる可能性が低いレプリカデータを包含するラインがライン・リプレイスの対象となって、キャッシュ・ヒット率を向上させることができる。
【００３４】
（本発明の第２の実施形態）
本発明の第２の実施形態に係るキャッシュ・メモリ制御方法を前記図３及び図４に基づき説明する。
本実施形態に係るキャッシュ・メモリ制御方法は、プロセッサからキャッシュ・メモリに書き込むべきデータがあるとき、当該書き込むべきデータが関数戻りアドレス値である場合には、通常通りキャッシュ・メモリに書き込むべきデータをオリジナルデータとして書き込むと共に、当該オリジナルデータと同一内容のレプリカデータを複数作成しオリジナルデータとそれぞれ対応付けてキャッシュ・メモリに書き込み、オリジナルデータがプロセッサから関数戻りアドレスとして読み出されるとき、当該オリジナルデータに対応するレプリカデータを読み出し、オリジナルデータと少なくとも１つのレプリカデータとが一致するか否かを比較する構成である。前記第１の実施形態に係るキャッシュ・メモリ制御方法との違いは、オリジナルデータに対するレプリカデータを複数作成し、それぞれオリジナルデータと対応付けて書き込むことである。
【００３５】
本実施形態に係るキャッシュ・メモリでも前記第１の実施形態に係るキャッシュ・メモリ連装方式の１つであるセットアソシエイティブ方式のキャッシュ・メモリに適用した場合について説明する。オリジナルデータと複数のレプリカデータとの総和が連想度を超えることはできないため、レプリカデータは「連想度―１」［個］を生成することができることとなる。このようにレプリカデータを前記第１の実施形態に係るキャッシュ・メモリと異なり、複数生成することで、ライン・リプレイスが生じて一個のレプリカデータが他のデータに上書きされた場合であっても、他のレプリカデータが残っているので、オリジナルデータとレプリカデータとの比較は可能となり、信頼性を高めることができるメリットがある。
【００３６】
次に、本実施形態に係るキャッシュ・メモリの動作について説明する。大部分は前記第１の実施形態に係る動作と重複するため、相違するステップのみを指摘する。ストアにおいては、前記ステップ１０５まで同一の動作であり、ステップ２０１ないしステップ２０３をレプリカデータの個数に応じてループして行い、かかる個数のレプリカデータを生成する必要がある。ロードにおいては、前記ステップ４０１では、１つのレプリカデータがあればオリジナルデータとの比較が可能となるため、複数のレプリカデータがキャッシュ・メモリ上にある場合には、かかる複数のレプリカデータの中から１つのレプリカデータを選択する。その余の動作は同じである。
【００３７】
このように本実施形態に係るキャッシュ・メモリ制御方法によれば、プロセッサからキャッシュ・メモリに書き込むべきデータがあるとき、当該書き込むべきデータが関数戻りアドレス値である場合には、通常通りキャッシュ・メモリに書き込むべきデータをオリジナルデータとして書き込むと共に、当該オリジナルデータと同一内容のレプリカデータを複数作成しオリジナルデータとそれぞれ対応付けてキャッシュ・メモリに書き込み、オリジナルデータがプロセッサから関数戻りアドレスとして読み出されるとき、当該オリジナルデータに対応するレプリカデータを読み出し、オリジナルデータと少なくとも１つのレプリカデータとが一致するか否かを比較するので、レプリカデータを複数作成し、オリジナルデータと対応付けてキャッシュ・メモリに書き込まれており、一部のレプリカデータがキャッシュ・メモリから追い出しがなされた場合でも残りのレプリカデータでオリジナルデータとの比較ができ、オリジナルデータとの比較ができるように信頼性を向上させることができる。ここで、作成される複数レプリカデータの数は多いほど信頼性を向上させることができるが、キャッシュ・メモリ上の領域を確保する必要があり追い出しの発生率を高める要因ともなる。
【実施例】
【００３８】
以下、本発明に係るキャッシュ・メモリの実施に相当する実験を行ったので、以下説明する。始めに、実験環境を説明する。提案方式の有効性を評価するため、 SimpleScalarツールセットVer.3.0dを改良して本発明に係るキャッシュ・メモリ（以下、SCacheとする）を実装した（参考文献：SimpleScalar Tool Sets, http://www.simplescalar.com/）。また、SPEC2000ベンチマーク・サイトより7つの整数プログラムと4つの浮動小数点プログラムを用いてアウト・オブ・オーダ実行のサイクルレベル・シミュレーションを行った（参考文献：SPEC(Standard Performance Evaluation Corporation, http://www.specbench.org/）。入力データとしてはSPECより提供されるsmall inputを使用している。L1データ・キャッシュ・サイズは16KB、ラインサイズは32B、連想度は4と仮定し、その他のプロセッサ構成に関する詳細なパラメータはSimplescalarのデフォルト値を用いた。SCacheでは、戻りアドレスがロードされる時、レプリカ・ラインが存在する場合には安全性を保障できる。以下の式で安全性を評価する。
2005338946.tif 000003
【００３９】
ここで、Nraldはプログラム実行におけるIRAロードの総数である。ここでIRA(Issued Return Address)ロードとは、キャッシュ・メモリに対して発行された戻りアドレス・ロードの事である。また、Nv-raldは戻りアドレス改ざんを検出できない(安全性を保障できない)IRAロード総数を示す。一方、消費エネルギーに関しては以下の式で評価する。
2005338946.tif 000004
【００４０】
ここで、ErdとEwtは、それぞれ、L1キャッシュ・メモリの読出し/書込み総消費エネルギーである。また、Ewbはレプリカ・ラインの作成に伴うライトバック総消費エネルギーを表す。さらに、Empはキャッシュ・ミス発生において消費されるエネルギーを示す。実際には、0.18μmCMOSプロセスを用いて1ウェイ分(4KB)のSRAMアレイのレイアウト設計ならびに負荷容量抽出を行い、プリチャージ動作も含めた1ビット当たりの読出し/書込み消費エネルギーを測定した。また、その結果に基づき、キャッシュ・アクセスにおける消費エネルギーを換算した。なお、Empの値はメモリ階層構造に大きく依存する。そこで、1回の下位メモリ階層アクセスに要するエネルギーは、従来型キャッシュ・メモリにおける平均読出し消費エネルギーの10倍と仮定した。
【００４１】
（実験結果（安全性））本評価ではキャッシュ・メモリの連想度を4と仮定しているため、LRUまたはMRUアルゴリズムに基づき最大3個のレプリカ・ラインを生成可能である。そこで、これらの組合せに関して安全性を評価した。実験結果を図５に表す。また、従来キャッシュ(CONV)におけるミス率とIRAロード数(Nrald)、ならびに、各SCacheモデルにおけるミス率を図８に示す。ここで、LRU1RならびにLRU2Rは、それぞれ、LRU配置アルゴリズムに基づき1個もしくは2個のレプリカ・ラインを生成するモデルである。同様に、MRU1RとMRU2Rは配置アルゴリズムにMRU方式を用いている。ALLは、参照セット中の全ライン(ただし、マスタ・ラインを除く)にレプリカ・ラインを生成する。
【００４２】
本シミュレーションではL1キャッシュ・ミス時のライン置換えアルゴリズムにLRU方式を採用している。そのため、LRU1Rで作成したレプリカ・ラインは他アクセスによって容易にキャッシュ・メモリから追出される。これに対し、LRU2Rではレプリカ・ラインのキャッシュ生存期間が長くなるため、より高い安全性を実現している。また、同様の理由により、MRU方式の採用によっても安全性は向上している。全てのSCacheモデルを比較した場合、ALLが最も高い安全性を達成しており、多くのプログラムで99.7%以上のIRAロードの安全性を保障することができた。一方、図８で示すように、生成するレプリカ・ライン数の増加、または、MRU方式の採用に伴い、キャッシュ・ミス率が高くなっている。したがって、性能を重視する場合には、ミス率の低下と安全性の向上を考慮してMRU1Rを選択することが適切であると考える。なお、SCacheでの戻りアドレス書込み時、前記したように、同一タグを有するレプリカ・ラインがすでに存在する場合にはそれらへの上書きを行う。よって、LRU領域にこのようなレプリカ・ラインが存在する場合、MRU1RはLRU1Rと同じ動作となる。そのため、MRU方式においても、作成されるレプリカ・ライン数を増加することで安全性が向上する。
【００４３】
（実験結果(消費エネルギー)）前記消費エネルギー・モデルに基づき評価した結果を図６に示す。ここで、図６は、不必要なウェイ・アクセスを回避するウェイ予測キャッシュ（参考文献：K.Inoue, T.Ishihara, and K.Murakami, "Way-Predicting Set-Associative Cache for High Performance and Low Energy Consumption," Proc. of the Int. Symp.on Low Power Electronics and Design, pp. 273--275, Aug. 1999.）を基準とした際の消費エネルギー・オーバヘッドを表している。この図６から、レプリカ・ライン数の増加に伴いオーバヘッドが大きくなっている事が分かる。特に、最も多くのレプリカ・ラインを生成するALLでは、最大で約23%の消費エネルギー・オーバヘッドが発生した(197.parser)。
【００４４】
消費エネルギーを詳細に解析するため、前記式(2)に関する内訳を測定した。その結果を図７に示す。ここでは、紙面の都合上、消費エネルギー・オーバヘッドが最も大きな2つの整数プログラム(197.parser，255.vortex)と浮動小数点プログラム(177.mesa，183.equake)、ならびに、最もオーバヘッドが小さい2つのプログラム(181.mcf，179.art)での結果を示している。従来キャッシュ(CONV)と比較して、読出し消費エネルギーErdは全てのSCacheモデルにおいてほぼ同じ増加率である。これは、レプリカ・ライン作成数ならびに配置アルゴリズムに関わらず、戻りアドレス・ロード発行時に全てのウェイが活性化されるためである。反対に、書込み消費エネルギーEwtは作成されるレプリカ・ライン数に比例して増加する。また、Empはミス率の増加に伴い大きくなっている。特に177.mesaにおいて、従来方式と比較した場合、ALLモデルは大幅なヒット率の低下を引き起こしており(図８を参照)、その影響によるEmpの増加が顕著に現れている。
【００４５】
オーバヘッドの小さい181.mcfならびに190.artとその他を比較した場合、これら2つのプログラムではキャッシュ・ミスによる消費エネルギーが多くの割合を占めている。実際、図８で示すように、これらプログラムのミス率は極めて高い。このように、従来のミス率と比較して、SCacheによるミス率の増加が十分小さい場合、Empに関する消費エネルギー・オーバヘッドが隠蔽される。また、本評価で基準としているウェイ予測方式では、ミス率の増加と共にウェイ予測による消費エネルギー削減効果が低減する。これらの理由により、SCacheの採用に伴う消費エネルギー・オーバヘッドは小さくなったものと考える。
一方、全てのプログラムにおいて、LRU1RとMRU1R、LRU2RとMRU2Rをそれぞれ比較した場合、消費エネルギーに関する差は殆ど見られない。生成するレプリカ・ライン数が同じ場合、配置アルゴリズムには関係なくキャッシュ消費エネルギーはほぼ同一となる。これに対し、MRU方式の場合はヒット率の低下を招くが、それによる消費エネルギー・オーバヘッドが比較的小さかった。このような結果を考慮し、レプリカ・ラインの配置アルゴリズムにはMRU方式が適していると考える。
【００４６】
（実験結果（性能））SCacheではレプリカ・ラインをキャッシュ内セットに生成するため、キャッシュ・ミス率の増加に伴う性能オーバヘッドが生じる。各ベンチマークにおける性能オーバヘッドを図９に示す。生成するレプリカ・ライン数が最大であるALLモデルにおいて、最悪の場合でも性能低下は1.1%(177.mesa)である。また、その他のモデルに関しては、197.paserを除く全てのプログラムにおいて0.2%以下の性能オーバヘッドである。これは、保護すべき戻りアドレスの数に対し、データキャッシュ・メモリは十分な容量を有するためである。以上より、提案手法による性能低下は無視できる程度に小さいと考える。
【００４７】
（結論）本稿では、スタック・スマッシングに対するアーキテクチャ・アプローチとしてセキュア・キャッシュ(SCache)を提案した。SCacheでは、キャッシュ・メモリの大容量領域を活用して戻りアドレスを保護する。実験を行った結果、多くのプログラムで99.7%以上の戻りアドレス・ロードに関して安全性を保障することができた。また、消費エネルギー解析を行った結果、安全性を重要視する場合には全てのラインに複製を生成するALLモデルが、一方、ある程度の安全性を維持しつつ低消費エネルギー化が要求される場合にはMRU方式に基づくMRU1Rが適切であると分かった。
【図面の簡単な説明】
【００４８】
【図１】一般のセットアソシエイティブ方式のキャッシュ・メモリの構成図である。
【図２】第１の実施形態に係るセットアソシエイティブ方式のキャッシュ・メモリの構成図である。
【図３】本発明の第１の実施形態に係るキャッシュ・メモリの動作フローチャートである。
【図４】本発明の第１の実施形態に係るキャッシュ・メモリの動作フローチャートである。
【図５】実施例の危険な戻りアドレス・ロード発生率を示すグラフである。
【図６】実施例の消費エネルギー・オーバヘッドを示すグラフである。
【図７】実施例の消費エネルギーの内訳を示すグラフである。
【図８】実施例のキャッシュ・ミス率の表である。
【図９】実施例の性能のオーバヘッドの示すグラフである。
【図１０】バッファ・オーバフロー示すグラフである。
【図１１】スタック・スマッシングの動作原理を示す図である。
【符号の説明】
【００４９】
１１  タグ
１２  タグ部
２１  データ領域
２２  データ領域部
３１  ウェイ
４１  セット
５１  データ内容比較器
【図１】
2005338946.tif 000005
【図２】
2005338946.tif 000006
【図３】
2005338946.tif 000007
【図４】
2005338946.tif 000008
【図５】
2005338946.tif 000009
【図６】
2005338946.tif 000010
【図７】
2005338946.tif 000011
【図８】
2005338946.tif 000012
【図９】
2005338946.tif 000013
【図１０】
2005338946.tif 000014
【図１１】
2005338946.tif 000015