JP2022512051A - メモリ完全性チェックのための完全性ツリー - Google Patents

Abstract

装置４は、メモリ中に記憶されたデータへのアクセスを制御するメモリ・アクセス回路１２と親ノードと子ノードとの間の関連付けがポインタによって与えられる完全性ツリー２６を使用してメモリ中に記憶されたデータの完全性を検証するメモリ完全性チェック回路２０と備える。これは、ツリーのメモリ・フットプリントを低減するのを助ける。

Description

本技法は、データ処理の分野に関する。より詳細には、本技法は、メモリ・セキュリティに関する。

いくつかのデータ処理システムは、潜在的な攻撃者に公開されてはならない秘密又は機密情報の処理に関与するソフトウェアを実行する必要があり得る。しかしながら、攻撃者によって改ざんできないメモリ中にすべてのそのような情報を記憶するのに十分な容量を与えることは実行不可能であり得、したがって、時々、攻撃に弱いメモリに一部の機密情報をエクスポートすることが必要であり得る。たとえば、オンチップに記憶されるデータは、攻撃に対してセキュアであり得るが、オンチップ・メモリ・ストレージは、限定され得、したがって、オフチップの外部メモリにデータを書き込む必要があり得る。攻撃者は、外部メモリからのデータを読み取ること、或いはデータが外部メモリにパスされるときにそれをインターセプトすること、若しくは／又はそのような外部に記憶されたデータが処理システムにその後で戻されるときに不正確な挙動を行わせようと試みて外部メモリ中に記憶されたデータ値を改ざんすることが可能であり得る。

秘匿性を与えるために、潜在的に安全でないメモリに記憶されるデータは、メモリにパスされること、及びメモリから読み取る上で解読されることの前に暗号化され得る。しかしながら、これは、改ざんのリスクに対処することができない。改ざんから保護するために、データがメモリから読み取られるときに、メモリからデータが記憶されてからデータが変更されていないことをチェックするために完全性チェックが与えられ得る。

「Ｓｏｍｅ Ｅｆｆｉｃｉｅｎｔ Ａｒｃｈｉｔｅｃｔｕｒｅ Ｓｉｍｕｌａｔｉｏｎ Ｔｅｃｈｎｉｑｕｅｓ」、Ｒｏｂｅｒｔ Ｂｅｄｉｃｈｅｋ、１９９０年冬季ＵＳＥＮＩＸ Ｃｏｎｆｅｒｅｎｃｅ、５３～６３ページ

少なくともいくつかの実例は、
メモリ中に記憶されたデータへのアクセスを制御するためのメモリ・アクセス回路と、複数のノードを備える完全性ツリーを使用してメモリ中に記憶されたデータの完全性を検証するためのメモリ完全性チェック回路とを備える装置であって、複数のノードは、メモリ中に記憶されたデータの対応するアドレス・ブロックの検証のための少なくとも１つの完全性タグを備える少なくとも１つのリーフ・エントリを備える少なくとも１つのリーフ・ノードと、少なくとも１つのブランチ・エントリを備える少なくとも１つのブランチ・ノードであって、ブランチ・ノードの子ノードのアドレスを指定するためのポインタであって、子ノードは、リーフ・ノードであるか、又は完全性ツリーのさらなるブランチ・ノードである、ポインタと、子ノードの対応するブランチ・エントリ又はリーフ・エントリの検証のための少なくとも１つの完全性チェック値とを備える少なくとも１つのブランチ・ノードとを含む、装置を提供する。

少なくともいくつかの実例は、メモリ中に記憶されたデータへのアクセスを制御することと、複数のノードを備える完全性ツリーを使用してメモリ中に記憶されたデータの完全性を検証することとを含む方法であって、複数のノードは、少なくとも１つのリーフ・エントリを備える少なくとも１つのリーフ・ノードであって、各リーフ・エントリは、メモリ中に記憶されたデータの対応するアドレス・ブロックの検証のための少なくとも１つの完全性タグを備える、少なくとも１つのリーフ・ノードと、少なくとも１つのブランチ・エントリを備える少なくとも１つのブランチ・ノードであって、各ブランチ・エントリは、ブランチ・ノードの子ノードのアドレスを指定するためのポインタであって、子ノードは、リーフ・ノードであるか、又は完全性ツリーのさらなるブランチ・ノードである、ポインタと、子ノードの対応するブランチ・エントリ又はリーフ・エントリの検証のための少なくとも１つの完全性チェック値とを備える、少なくとも１つのブランチ・ノードとを含む、方法を提供する。

少なくともいくつかの実例は、命令の実行のための命令実行環境を与えるようにホスト・データ処理装置を制御するためのコンピュータ・プログラムであって、命令実行環境のシミュレートされたアドレス空間へのアクセスを制御するためのメモリ・アクセス・プログラム論理と、複数のノードを備える完全性ツリーを使用してシミュレートされたアドレス空間内のアドレスに記憶されたデータの完全性を検証するためのメモリ完全性チェック・プログラム論理とを備え、複数のノードは、メモリ中に記憶されたデータの対応するアドレス・ブロックの検証のための少なくとも１つの完全性タグを備える少なくとも１つのリーフ・エントリを備える少なくとも１つのリーフ・ノードと、少なくとも１つのブランチ・エントリを備える少なくとも１つのブランチ・ノードであって、ブランチ・ノードの子ノードのアドレスを指定するためのポインタであって、子ノードは、リーフ・ノードであるか、又は完全性ツリーのさらなるブランチ・ノードである、ポインタと、子ノードの対応するブランチ・エントリ又はリーフ・エントリの検証のための少なくとも１つの完全性チェック値とを備える少なくとも１つのブランチ・ノードとを含む、コンピュータ・プログラムを提供する。

記憶媒体は、上で説明されたコンピュータ・プログラムを記憶し得る。記憶媒体は、非一時的媒体であり得る。

本技法のさらなる態様、特徴、及び利点は、添付の図面と併せて読み取られるべきである実例の以下の説明から明らかになろう。

メモリ完全性チェック回路の装置を備える一実例を概略的に示す図である。 完全性チェックにおいて使用するための完全性ツリーの一実例を示す図である。 改ざんから保護されるべき保護領域のサイズに応じたサイズのメモリの連続する領域を占有するマークル・ツリーとして完全性ツリーが実装される代替手法を示す図である。 ツリーの親ノードと子ノードとの間の関連付けを与えるために使用されるポインタを用いて完全性ツリーが構築される一実例を示す図である。 アドレス空間内で同じく不連続であるいくつかの他のアドレス領域を保護するためにアドレス空間のいくつかの不連続なアドレス領域中に記憶された完全性ツリーを使用することの一実例を示す図である。 ハッシュのツリーとしてツリーを実装することの第１の実例を示す図である。 ツリーによってそれら自体保護されない対応するハッシュを計算するためのナンスとして使用されるカウンタのツリーとしてツリーを実装することの第２の実例を示す図である。 図７の第２の実例におけるカウンタを表す２つの実例を示す図である。 完全性ツリーのリーフ・ノードにおいて完全性タグを更新するための流れを示す流れ図である。 完全性ツリーを使用してデータの所与のアドレス・ブロックの完全性を検証するための方法の一実例を示す流れ図である。 完全性ツリーに追加のレベルを追加するための一方法を示す流れ図である。 使用され得るシミュレータの一実例を示す図である。

装置は、メモリ内に記憶されたデータへのアクセスを制御するためのメモリ・アクセス回路とメモリ中に記憶されたデータの完全性を検証するためのメモリ完全性チェック回路とを有し得る。たとえば、完全性の検証は、メモリ中に記憶されたデータを改ざんする攻撃者を検出するためのものであり得る。たとえば、メモリは、メモリ・アクセス回路とメモリ完全性チェック回路とを備える集積回路とは別個の集積回路上のオフチップ・メモリとすることもできる。

完全性の検証は、記憶されたデータとメモリ完全性チェック回路によって維持された完全性メタデータとの間の比較に依存し得る。たとえば、メモリにデータを書き込むときに、メモリ完全性チェック回路は、メモリ中に記憶されたデータのプロパティに基づいて完全性メタデータを生成することができ、次いで、メモリからデータを読むときに、データが書き込まれてからそれが変更されたのかどうかをチェックするために前に記憶された完全性メタデータが使用され得る。しかしながら、そのような完全性メタデータは、必要とされるアドレス範囲にわたってデータを保護するためのすべてのメタデータを与えるために有意な量のストレージ・スペースを要求することがある。しばしば、メモリ・アクセス回路と同じ集積回路上のオンチップ・メモリなどの攻撃者に攻撃されやすくないストレージ・ユニット中にデータを保持する容量は、限定され得る。したがって、実際には、保護されるべきデータを記憶するのと同じメモリに完全性メタデータの少なくとも一部を記憶する必要があり得る。これは、メタデータを攻撃に弱くさせることがあり、したがって、完全性メタデータは、それ自体、それが読み取られるとき、同じくメモリ中に記憶され得るさらなるメタデータに基づいて注目する実際のデータと同様に完全性の検証を受けることがある。注目するデータのための一連の完全性チェックとデータを検証するために必要な完全性メタデータの各部分とを管理するために、いくつかのノードを備える完全性ツリーとしてメタデータを表すことが有用であり、ここで、ルート・ノードは、ルート・ノードの子ノードであるいくつかのブランチ・ノードを検証するために使用され得、それらのブランチ・ノードの各々は、次いで、それらのより前のブランチ・ノードの子ノードであるさらなるブランチ・ノードを検証するために使用され得、以下、メモリ中に記憶されたデータの対応するアドレス・ブロックの検証のために使用され得るリーフ・ノードに達するまで同様である。

完全性ツリーを実装するための１つの手法では、アドレス空間の単一の連続するブロックが、完全性ツリーを使用してデータが保護されるべきである保護領域として定義され得、アドレス空間の別の連続するブロックは、保護アドレス範囲全体を保護することが可能になるのに十分なノードを含むことになる完全性ツリーに適応するために前もって事前に割り振られる。この手法では、所与のツリー・ノードが記憶されるアドレスは、完全性ツリーのベース・アドレスと、ツリーを使用して完全性が検証されるべきである保護領域中のデータ・ブロックのターゲット・アドレスとから計算され得る。

しかしながら、この手法は、いくつかの問題に悩まされ得る。メモリ完全性ツリーがアドレス空間の単一の連続ブロックに記憶されている必要があるので、すでに他の目的のために割り振られていないツリーを格納するためのアドレスの大きい連続するブロックを発見することが困難であり得るので、これは、完全性ツリーによってデータが保護され得る保護領域の最大サイズを限定する傾向があることになる。したがって、実際には、この手法では、保護アドレス範囲の範囲を、たとえば、１２８メガバイトのオーダーで、あるサイズに限定することが普通である。効率的なメモリ管理は、保護アプリケーション・ページ又は仮想マシン・ページを記憶するために物理的ロケーションを自由に選定する能力を必要とし得るので、特定のアドレス範囲に保護を限定することは、プロセッサ上で動作するオペレーティング・システムに厳しい制限を提示することがある。

別の問題は、データが保護され得る潜在的な保護アドレス範囲全体に適応するために完全性ツリーは前もって事前に割り振られ得るので、したがって、オペレーティング・システムがその保護アドレス範囲内のページのサブセットにのみ極秘データを割り振ることを選定した場合でも、全保護アドレス範囲にわたって完全性ツリーを実装することの完全なメモリ・フットプリントがすでに発生しており、したがって、完全性ツリーのノードのごく一部のみが保護アドレス範囲内の特定のブロックの完全性を検証するための完全性メタデータを与えるものとして実際に定義されている場合でも、オペレーティング・システムは、完全性ツリーのために割り振られたアドレス空間の連続する部分に他のデータを割り振ることが可能でない。

以下で説明される技法では、メモリ完全性チェック回路は、ツリーのブランチ・ノードとそれの子ノードとの間の関連付けを与えるためにポインタを使用する完全性ツリーを使用してメモリ中に記憶されたデータの完全性を検証する。したがって、ツリーは、メモリ内に記憶されたデータの対応するアドレス・ブロックの検証のための少なくとも１つの完全性タグを備える少なくとも１つのリーフ・エントリを備える少なくとも１つのリーフ・ノードと、少なくとも１つのブランチ・エントリを備える少なくとも１つのブランチ・ノードとを含み得る。ブランチ・エントリは、ブランチ・ノードの子ノードのアドレスを指定するためのポインタ（ここで、子ノードは、リーフ・ノードであるか、又は完全性ツリーのさらなるブランチ・ノードであるか、のいずれかである）を備え、また、子ノードの対応するブランチ・エントリ又はリーフ・エントリの検証のための少なくとも１つの完全性チェック値を指定する。

ポインタが各ブランチ・エントリ内に追加の記憶容量を必要とするであろうことと、同じく、メモリ中に記憶されるデータの所与のブロックを検証するための関係するリーフ・エントリの位置を特定するためのツリーの横断は、ツリーのルートからリーフ・ノードまで下のポインタの跡を追うことを必要とするであろうことをポインタの使用が意味するであろうこととが予想され得るので、ブランチ・ノードとそれの子ノードとの間の関連付けを与えるためのそのようなポインタの使用は、反直観的であるように見られ得、したがって、検証されるべきデータのブロックのアドレスに基づいてリーフ・モードに直接インデックス付けすることが可能である手法と比較してリーフ・ノードの位置を特定するために何らかの追加のレイテンシが発生し得る。しかしながら、発明者は、そのようなレイテンシが他の動作に関連するレイテンシの下にそれを隠すことによって緩和され得、したがって、予想するであろうほど有意な問題でないと認識した。

一方、ブランチ・ノードとそれの子ノードとの間の関連付けを与えるためにポインタを使用することによって、これは、ツリーによって保護されるべきであるデータの実際の個人のアドレス・ブロックが位置するであろう潜在的な保護範囲ではなく、これらの保護されたアドレス・ブロックを保護するために必要とされるいくつかの完全性ツリー・ノードのための空間を割り振るメモリ割り振りコストのみを発生しながら、（物理的メモリ全体にわたる範囲が与えられるが）完全性ツリーが潜在的に大きいメモリ範囲を保護することを可能にする。限定されたアドレス範囲又はある連続するブロック内のアドレスに制限されることなしにオペレーティング・システムがメモリ空間中の任意の所望のアドレスに保護されるべきデータと完全性ツリーのノードとを自由に割り振ることができ得るので、これは、メモリ完全性ツリーを維持するオーバーヘッドを大幅に低減し、ツリーを使用したオペレーティング・システムの設計を簡略化する。

上で説明されたように、メモリ中の所与のデータ・ブロックの検証はまた、それらの親ノードに基づく完全性ツリーのいくつかのノードの検証を伴い得る。所与のブランチ・エントリが検証されるべきであるとき、所与のブランチ・エントリの親ノード中に指定されている完全性チェック値は、ポインタを含めその所与のブランチ・エントリのコンテンツを検証するために使用され得る。したがって、ブランチ・エントリによって指定された完全性チェック値だけでなく、ポインタも検証され得る。これは、攻撃者が完全性チェックを避けようと試みて所与のブランチ・エントリによって指定されたポインタを改ざんすることから守る。

メモリ完全性チェック回路は、完全性ツリーが、メモリ・アドレス空間内のアドレス・ブロックの不連続なグループに対応するリーフ・エントリを指定する１つ又は複数のリーフ・ノードを含むように構成されることをサポートし得、ここで、アドレス・ブロックの不連続なグループ間のアドレス・ブロックの少なくとも１つの介在グループは、完全性ツリーによって保護されていない。したがって、完全性が完全性ツリーによって保護される保護されたアドレス・ブロックは、メモリの連続するブロック内に記憶されている必要がなく、オペレーティング・システムがそれが好きな任意の物理アドレスにそれの極秘データを割り振ることができるので、これはオペレーティング・システムの開発をはるかに単純にする。

また、メモリ完全性チェック回路は、完全性ツリーが、メモリ・アドレス空間内のアドレス・ブロックの２つ以上の不連続なグループに記憶されたノードを含むように構成されることをサポートし得、ここで、アドレス・ブロックの不連続なグループ間のアドレス・ブロックの少なくとも１つの介在グループは、割り振られていないメモリと、前記完全性ツリー以外のデータを記憶するために割り振られたメモリとのうちの少なくとも１つを備える。この場合も、これは、オペレーティング・システムによるメモリ割り振りの管理を簡略化し、また、上で説明された手法の場合のように、完全性ツリーのメモリ・フットプリントが、ツリーによって潜在的に保護される可能性がある連続する領域のサイズではなく、ツリーによって実際に保護される不連続に位置するアドレス・ブロックのサイズに比例し得ることを意味する。

メモリ中に記憶されたデータの所与のアドレス・ブロックのターゲット・アドレスを指定する要求に応答して、メモリ完全性回路は、ルート・ノードから所与のアドレス・ブロックに対応する完全性タグを備える所与のリーフ・ノードまでの完全性ツリーのトップダウン横断をトリガし得る。これは、リーフ・ノードにおいて開始し、次いで、ルート・ノードに達するまで親ノードから子ノードに進むボトムアップ方式でツリーが一般に横断されることになる上で説明された手法と対照をなす。

完全性ツリーのトップダウン横断では、横断は、各ブランチ・ノード中のポインタの跡を追って親ノードから子ノードに進み得る。したがって、横断は、ルート・ノードから所与のリーフ・ノードまでの経路上にある完全性ツリーのいくつかの親子ノード・ペアを伴い得る。所与の親ノードと所与の子ノードとを備える所与の親子ノード・ペアの場合、メモリ完全性チェック回路は、所与の親ノードの対応する親エントリによって指定されたポインタと所与のアドレス・ブロックのターゲット・アドレスに基づいて識別されたオフセットとに基づいて計算されるメモリ・アドレスから所与の子ノードの対応する子エントリを読み取る、読み取り動作をトリガし得る。また、メモリ完全性チェック回路は、所与の親ノードの対応する親エントリ中に指定されている対応する完全性チェック値に基づいて、対応する子エントリの完全性を検証する、検証動作を実行し得る。

ツリーの次のレベルの子ノードが読み取られ得る前に親ノード中のポインタが読み取られる必要があることになるので、このトップダウン横断は、完全性チェックのレイテンシを増加させることが予想され得る。しかしながら、この追加のレイテンシは、トップダウン横断の前のステップから親エントリに対して実行される検証動作と並行して子エントリの位置を特定するために読み取り動作を実行することによって緩和され得る。すなわち、対応する親エントリの完全性が所与の親ノード自体の親ノード（すなわち、子ノードの祖父ノード）中に指定されている対応する完全性チェック値に基づいて検証されている間に、親ノードの検証が成功する場合に子ノードの位置を特定する際の遅延を低減するために所与の子ノードの対応する子エントリを読み取る、読み取り動作が並行してトリガされ得る。

メモリ完全性チェック回路は、ブランチ・エントリ内のヌル・インジケータを指定するツリーのブランチ・ノードをサポートし得る。ヌル・インジケータは、そのブランチ・エントリの下に入るいかなるアドレスもメモリ完全性ツリーによる保護を必要とするものとしてまだ割り振られていないことを示し得、したがって、そのブランチ・エントリの下にさらなるブランチ・ノードもリーフ・ノードもない。したがって、メモリ完全性ツリーは、完全なツリー構造を形成する必要がない。代わりに、完全性ツリーのメモリ・フットプリントが、上で説明された手法の場合のように保護を必要とする連続するアドレス領域のサイズではなく保護される必要があるデータの実際の量を追跡することを保証するために保護を必要とするより多くのデータがメモリに割り振られるので、ノードはツリーに割り振られ得る。

メモリ完全性チェック回路は、次いで、ルート・ノードから所与のリーフ・ノードまでの経路上に、所与のアドレス・ブロックのための対応するブランチ・エントリがヌル・インジケータを指定するブランチ・ノードを検出したことに応答してトップダウン横断を停止し得るので、ヌル・インジケータの使用は有用であり得る。これは、メモリ中のあるアドレス・ブロックが保護を必要としない比較的迅速な検出を可能にし、したがって、トップダウン横断全体を完了する必要がない。これは、完全性チェックのパフォーマンスの影響を低減するのを助ける。

ヌル・インジケータは、様々な方法で表されることがある。１つの実例では、ヌル・インジケータは、特定のヌル値を指定する所与のブランチ・エントリ中に指定されている完全性チェック値を備え得る。

しかしながら、ヌル・インジケータがヌル値を指定するポインタを備えることは特に有用であり得る。ヌル値は、１つの単一の所定の値とすることも、あるサブセットのビットを共有する値のグループとすることもできる。たとえば、１つの実例では、ポインタは、それがヌル値を表す場合は１に、それが実際のアドレス・ポインタを表す場合は０に設定される特定のビット（たとえば、最下位ビット）を有することができる。

完全性ツリーのトップダウン横断は、いくつかの異なるタイプの要求によってトリガできる。たとえば、メモリ中の所与のブロックへの読み取り又は書き込みアクセスを要求しているメモリ・アクセス要求は、要求されたブロックのデータが有効であり、改ざんされていないのかどうかを検証するためにツリーの横断をトリガすることができる。代替的に、メモリ中の新たに割り振られたブロックのための完全性タグの追加を要求するタグ追加要求が発行でき、これは、次いで、完全性ツリーの対応するリーフ・ノードにおける完全性タグの更新につながることになる。しかしながら、ツリーに新しい完全性タグを追加するために、これは、次いで、新たに追加された完全性タグに一致するように更新されるべきリーフ・ノードの親ノード及びより高いノードにおいて対応する完全性チェック値又はタグを必要とし得、したがって、それらの更新を実行する前に、更新を実行することの前にノードのすべて自体が有効であることをどんな方法でも検証することが必要とされ得、そうでない場合、より高いノードのうちの１つの攻撃者の改ざんが検出されないままである可能性がある。したがって、所与のリーフ・ノードに追加の完全性タグを追加する要求自体は、上で説明された検証を伴うトップダウン横断を必要とし得る。

メモリ・アクセスについて、ヌル・インジケータが、上で説明されたように、ブランチ・ノードの所与のブランチ・エントリにおいて検出されるとき、メモリ完全性チェック回路は、単に、メモリ・アクセス要求によってアクセスされるように要求された所与のアドレス・ブロックを完全性の検証が必要とされない保護されていないアドレス・ブロックとして扱い、したがって、メモリ・アクセスを進めることが可能であるか、又は、代替的に、メモリ・アクセス要求は、アドレス・ブロックが保護されていたか若しくは保護されていなかったかを区別することなしに所与のアドレス・ブロックについて完全性の検証が成功したという指示を戻すことか、のいずれかが可能である。

タグ追加要求の場合、トップダウン横断は、対応するブランチ・エントリがヌル・インジケータを指定する所与のブランチ・ノードを検出する場合、メモリ完全性回路は、所与のブランチ・ノードのさらなる子ノードを記憶するためのメモリ・アドレス空間を割り振るようにソフトウェアをトリガし、次いで、さらなる子ノードのために割り振られたものとしてソフトウェアによって指定されたアドレスを示すように所与のブランチ・ノードの対応するブランチ・エントリのポインタを更新し得る。また、ポインタ自体が示されたヌルを表さなかった場合、メモリ完全性チェック回路はまた、対応するブランチ・エントリの別の部分によって表されるヌル・インジケータを消去し得る。ポインタがヌル・インジケータを表す場合、さらなる子ノードのために割り振られたアドレスに一致するようなポインタの更新は、ヌル・インジケータを消去するのに十分であり得る。どちらにしても、ポインタ・ベースのツリー構造の使用は、処理回路上で実行されるソフトウェアがさらなる子ノードを記憶するために割り振られたアドレスの選択における完全な自由を有し得ることを意味する。これは、アドレス割り振りについてはるかに単純に言及する。

上で説明された完全性チェックは、所与のアドレス・ブロックのためのデータへのアクセスを要求するメモリ・アクセス要求に応答して実行される唯一のタイプのチェックでないことがある。さらに、メモリ・アクセス回路はまた、所与のアドレス・ブロックがアクセスされるのを許可されるのかどうかをチェックするためにアクセス許可チェックを実行し得る。たとえば、このアクセス許可チェックは、処理回路のどの特権レベルが所与のアドレス・ブロックにアクセスすることを許可されるのかを制限する属性又はアドレス・ブロックが読み取り専用であるのか若しくは読み取りと書き込みとの両方が行われ得るのかを指定する属性などの所与のアドレス・ブロックのための様々な属性を指定するページ・テーブルに基づくことができる。アクセス許可チェックの別の形態は、所与のアドレス・ブロックが動作のセキュアな領域又はあまりセキュアでない領域に関連付けられているのかどうかについてチェックすることであり得、したがって、セキュアな領域に関連するアドレスは、あまりセキュアでない領域で動作するコードによってアクセスされることを妨げられ得る。また、いくつかのアーキテクチャは、所与のアドレス領域について、どの他の処理がデータにアクセスすることを許可されるのかを指定することを可能にされた所有者プロセスを定義する所有権テーブルを与え得る。これは、より低い特権動作状態で動作する所有者プロセスが、より高い特権レベルで実行されるより高い特権プロセスを、所有者プロセスに所有されている領域中に記憶されたデータにアクセスすることから除外することを可能にすることができる。したがって、いくつかの実例では、メモリ・アクセス・チェックはまた、そのような所有権テーブルに基づき得る。

実行されるアクセス許可チェックの特定のタイプにかかわらず、アクセス許可チェックは、いくつかのレイテンシを招き得る。たとえば、アクセス許可チェックがメモリ中に記憶されたテーブルに基づく場合、次いで、許可定義テーブルの必要とされるエントリがまだキャッシュされていない場合、メモリからエントリをフェッチするのにある程度の時間がかかり得る。

したがって、いくつかの実例では、メモリ・アクセス回路によって実行されるアクセス許可チェックが完了する前に、メモリ・アクセス回路は、アクセスがメモリ完全性チェック回路に要求された所与のアドレス・ブロックのアドレスを指定するヒント信号を与え得る。ヒント信号に応答して、メモリ・アクセス回路によって実行されるアクセス許可チェックが完了する前に、メモリ完全性回路は、完全性ツリーの少なくとも１つのノードの読み取りをトリガし得る。したがって、メモリ完全性チェック回路は、メモリ・アクセス許可チェックが実行されている期間中に完全性ツリーのノードを読み取ることを開始することができるので、これは、完全性チェック回路に関連するレイテンシのうちの一部を隠すことができる。たとえば、メモリ完全性チェック回路は、与えられたヒントに基づいて完全性ツリー・ノードのそれのキャッシュをウォーム・アップすることができる。次いで、アクセスがアクセス許可チェックに失敗したとメモリ・アクセス回路がその後に決定した場合でも、後続の要求は、依然として、そのキャッシングから恩恵を受けることができるので、メモリ完全性チェック回路のキャッシュをウォーム・アップすることは依然として有用であり得る。したがって、この手法は、完全性チェックのパフォーマンスを改善することができる。

完全性ツリーのノードは、完全性ツリーによって保護されたデータと同じメモリ中に記憶できる。代替的に、ノード 完全性ツリーは、完全性ツリーによって保護されたデータを記憶するメモリとは異なるメモリ中に記憶できる。上で説明された完全性ツリー構成は、異なるメモリ・タイプ中に記憶された構造を使用して１つのメモリ・タイプを保護することを可能にする。たとえば、完全性ツリー・ノードは、完全性チェックを実行するパフォーマンス・コストを低減するために、保護データ自体を記憶するメモリと比較して低減されたアクセス・レイテンシでメモリ中に記憶できる。

完全性ツリーのルート・ノードは、メモリ完全性チェック回路と同じ集積回路内に与えられるオンチップ・メモリ中に記憶され得る。オンチップ・メモリとプロセッサ・コアとの間の通信経路が外部に露出されていないので、オンチップ・メモリは、改ざんから保護され得、したがって、これは、ルート・ノードが完全性ツリー全体の信用の起点（root of trust）として働くことを可能にする。

ルート・ノードは、完全性ツリーのトップレベルのブランチ・ノードのアドレスを指定するポインタであって、トップレベルのブランチ・ノードは、ルート・ノードの子ノードである、ポインタを備え得る。また、ルート・ノードは、トップレベルのブランチ・ノードの対応するブランチ・エントリの検証のための少なくとも１つの完全性チェック値を指定し得る。場合によっては、ルート・ノードは、トップレベルのブランチ・ノード内の異なるブランチ・エントリにそれぞれ対応する複数の完全性チェック値を備え得る。

メモリ中にいかなる保護データをも記憶する前に固定された事前に割り振られたサイズの完全性ツリーが割り振られる上で説明された手法の場合とは異なり、上で説明されたポインタを使用する手法では、ツリーによって保護された一部の保護データがメモリ中にすでに記憶された後に完全性ツリーに追加のレベルを追加することが可能である。したがって、完全性ツリーにレベルを追加することの要求に応答して、メモリ完全性チェック回路は、完全性ツリーの新しいトップレベルのブランチ・ノードを新しいトップレベルのブランチ・ノードを記憶するために割り振られたものとしてソフトウェアによって指定されたアドレスに記憶することであって、新しいトップレベルのブランチ・ノードは、ポインタとルート・ノードによって前に指定された少なくとも１つの完全性チェック値とを含む、記憶することと、新しいトップレベルのブランチ・ノードを記憶するために割り振られたアドレスを指定するようにルート・ノードのポインタを更新することと、新しいトップレベルのブランチ・ノードのコンテンツに対応するようにルート・ノードの少なくとも１つの完全性チェック値を更新することとを行うように構成され得る。したがって、完全性ツリー上のレベルの数について事前に決定する必要がない。追加のレベルは、必要とされたときに単に追加され得、これは、すでに割り振られた保護データの量を保護するために必要とされる量のスペースのみが必要とされるようにツリーのメモリ・フットプリントを限定するのに再び役立つ。効果的に、新しいレベルが完全性ツリーに追加されるとき、ルート・ノードの前のコンテンツは、（新しいトップレベルのブランチ・ノードの他のエントリがヌル・インジケータを指定した状態で）新しいトップレベルのブランチ・ノード・ルート内の新しいブランチ・エントリになるためにメモリに出て記憶され、次いで、ルート・ノードは、その新しいトップレベルのブランチ・ノードをポイントし、新しいトップレベルのブランチ・ノードの非ヌル・エントリのコンテンツと対応する少なくとも１つの完全性チェック値を含むように更新される。

ツリーのブランチ・エントリ内の完全性チェック値は、様々な方法で実装され得る。１つの実例では、各完全性チェック値は、そのブランチ・エントリのポインタによってポイントされる子ノードの対応するブランチ・エントリ又はリーフ・エントリの関数として導出された完全性タグを備え得る。たとえば、各完全性タグは、対応するブランチ・エントリ又はリーフ・エントリのハッシュであり得、したがって、全体的なツリーは、そのエントリの記憶された値に基づいてそれのハッシュを計算し、その子ノードの親であるブランチ・エントリ内に記憶された完全性タグと計算されたハッシュを比較することによって子ノード内の所与のエントリが検証され得るハッシュのツリーを形成する。ハッシュはまた、リプレイ・アタックから保護するためにフレッシュネスを与えるためにカウンタに基づくことができる。

代替的に、所与のブランチ・ノードの所与のブランチ・エントリについて、各完全性チェック値は、所与のブランチ・エントリのポインタによってポイントされる子ノードの対応するブランチ・エントリ又はリーフ・エントリ中に記憶された対応する完全性タグを計算するための少なくとも１つの完全性ナンス（１回使用される数）を備え得る。この場合、子ノードの所与の子ノード又はリーフ・エントリ中にある完全性タグは、（ｉ）子ノードの親エントリ中に記憶された完全性ナンスと（ｉｉ）その 子ノード・エントリの他のコンテンツとの関数として導出されることになる。したがって、所与のブランチ・エントリは、子ノードのそれぞれのブランチ・エントリ又はリーフ・エントリに対応する完全性ナンスのグループを指定し得、これは、完全性ナンスのグループと所与のブランチ・ノードの親ノード中に指定されている完全性ナンスとの関数として導出される共有完全性タグによって保護され得る。

完全性タグを計算するための完全性ナンスの使用は、タグによって保護された対応するデータがそれから変更されているので期限切れであるが（対応するデータの更新の前にキャプチャされた）完全性タグの前の有効値を攻撃者が与えようと試みるリプレイ・アタックから保護するためにフレッシュネスを保証するのに有用であり得る。完全性ナンスは、対応する完全性タグが更新されるたびに変更される乱数であり得るか、又は完全性タグが更新されるたびに変更される任意の他の値とすることができる。しかしながら、完全性ナンスを実装する単純な方法は、対応する完全性タグの更新が行われるたびに増分される遭遇を単調増加するものとしてあり得る。そのような完全性ナンス又はカウンタを使用する手法では、ツリーのメモリ・フットプリントを低減するための１つの手法は、ツリーが各ブランチ・ノードにおいて完全性ナンスのための完全性保護を与えるだけで、対応する完全性タグを保護しないことであり得る。上で説明されたハッシュ・ツリーとは異なり、カウンタ・ツリー又はナンス・ツリーでは、所与のブランチ・エントリ又はリーフ・エントリのコンテンツを保護するタグは、そのブランチ・エントリ又はリーフ・エントリ自体とともに記憶される。

ツリーが、完全性ナンスのツリーに基づくとき、所与のブランチ・エントリ内の完全性ナンスの各グループは、その所与のブランチ・エントリに対応する子ノードの各ブランチ・エントリ若しくはリーフ・エントリのために独立して指定された非分割カウンタのグループとして、又は子ノードのそれぞれのブランチ・エントリ又はリーフ・エントリ間で共有される主カウンタと子ノードの各ブランチ・エントリ又はリーフ・エントリのために別個に指定される副カウンタとの組み合わせとして各分割カウンタが表される分割カウンタのグループとして、のいずれかとして実装され得る。分割カウンタの使用は、所与のブランチ・エントリ内に与えられるグループ・カウンタの全体的なサイズを低減するのを助けることができる。分割カウンタでは、所与の子エントリのための副カウンタは、対応する子エントリが更新されるときに増分されることになり、副カウンタを増分することがオーバーフローを生じる場合、対応する主カウンタ自体が、更新され得、次いで、これは、その主カウンタを備えるブランチ・エントリによってポイントされる子ノードのそれぞれのブランチ・エントリ又はリーフ・エントリ内のタグ値のすべての再計算を必要とし得る。

したがって、本技法は、ハッシュのツリー又はカウンタ（ナンス）のツリーのいずれかを包含する。完全性ツリーに追加のレベルを追加する上記の実例では、それの完全性チェック値を新しいトップレベルのブランチ・ノードのコンテンツと対応させるようにルート・ノードが更新されるとき、これは、新しいトップレベルのブランチ・ノードのコンテンツに基づいてルート・ノードの新しい完全性タグを計算することによって、又は新しいトップレベルのブランチ・ノードのタグを計算するために使用されるナンス値に一致するようにルート・ノードのナンスを更新することによって、のいずれかによって行われ得る。

完全性チェックを管理することに加えて、メモリ完全性チェック回路はまた、メモリに書き込む際にデータを暗号化することと、それを読む込む際にデータを解読することとを行うことができる。

上で説明された技法は、ハードウェア中にメモリ完全性チェック回路の機能を与える特注の回路を有する物理デバイス中に実装され得る。したがって、これが、ハードウェア中に与えられるメモリ完全性チェック回路によって自動的に行われることができるので、処理装置上で実行されるソフトウェアは、完全性検証動作が実行されていることに気づく必要がない。したがって、ソフトウェアが、保護されたアドレスに書き込まれるようにデータに命令するとき、メモリ・セキュリティ回路は、メモリにそれを書き込むより前にデータを暗号化し、対応する完全性ツリー・ノードの生成及び／又はメモリが攻撃者によって損なわれていない完全性ツリーに基づく検証を制御することができる。同様に、ソフトウェアによる保護されたメモリ領域への読み取り時に、メモリ・セキュリティ・ハードウェアは、読み取られたデータの解読と読み取られたデータが依然として有効であることを検証するための完全性ツリー・ノードのチェックとを制御し得る。

しかしながら、他の実例では、暗号化／解読、完全性ツリー・ノードの生成、及び記憶された完全性ツリーに基づく完全性検証動作は、そのようなメモリ・セキュリティ動作を自動的に実行するためのハードウェアをそれ自体で有しない装置内の汎用処理回路上で実行されるソフトウェアによって実行され得る。たとえば、ソフトウェアは、その制御下にあるそれの下で動作する他のアプリケーションをサポートし得るオペレーティング・システム、ハイパーバイザ、より高い特権レベルで実行するソフトウェア、又はシステム・ファームウェアなどのプラットフォーム・レベルのコードであり得る。たとえば、仮想マシン又はシミュレータ・プログラムは、ハードウェアがメモリ完全性チェック回路を実際に有するかのように、仮想マシン若しくはシミュレータ・プログラムがメモリ・アクセス命令をインターセプトした状態で、並びにそのような命令、データの暗号化若しくは解読をトリガすること、又は完全性ツリーを維持すること及び／若しくは完全性ツリーに基づいてデータの完全性を検証することのための動作をトリガすることに応答してアプリケーション・コードを実行し得る。したがって、いくつかの実例では、本技法は、上で説明されたような方法を提供するようにデータ処理装置を制御するためにコンピュータ・プログラムを記憶する記憶媒体を提供し得る。

図１は、データ処理演算を実行するためにプログラム命令を実行するための少なくとも１つのプロセッサ・コア６を含む集積回路又はシステム・オンチップ４を備えるデータ処理システム２の一実例を概略的に示す。図１が１つのプロセッサ・コアのみを示すが、場合によっては、システム・オンチップ４は、複数のプロセッサを備え得る。各プロセッサ・コア又はプロセッサ・コア・クラスタは、キャッシュ８（又は複数のレベルのキャッシュ８、１０）を有し得る。メモリ・コントローラ１２は、システム・オンチップ４とは別個の集積回路上にあるオフチップ・メモリ１４へのアクセスを制御するためのメモリ・アクセス回路として働く。オンチップのデータへのアクセスが攻撃者によって改ざんすることが困難であり得るが、システム・オンチップの端部は信用境界として働くことがあり、その境界を越えて通過するあらゆるデータは、メモリ・コントローラ１２とオフチップ・メモリ１４との間の物理チャネル１６上でデータをインターセプトすることによって、又はオフチップ・メモリ１４中に記憶される間にデータを読み取る若しくは変更することによって攻撃に弱くなり得る。図１が、信用境界がシステム・オンチップの端部に対応する一実例を示すが、他の場合には、潜在的な攻撃に対する信用境界を越えてデータを公開する可能性があるシステム・オンチップ内の信用境界がある可能性がある。

システム・オンチップ４は、システムへの物理的なアクセスを有し、マイクロプロセッサとオフチップ・システム・メモリ１４との間で交換されているデータ又はコードを観測及び／又はリプレイする能力を有する悪意のある敵からオフチップ・メモリ１４に記憶されるデータを保護するために与えられるメモリ完全性チェック回路２０を含み得る。メモリ１４は、保護されるべきデータ２４並びにデータ２４の検証において使用される完全性ツリー・メタデータ２６を記憶する。

メモリ完全性チェック回路２０は、オフチップ・メモリ１４に書き込まれているデータを暗号化し、オフチップ・メモリから読み取られ戻されたデータを解読するための暗号化／解読回路３２を含む。これは、オフチップ・メモリ１４から読み取られているか又はそれの上に記憶されているデータを悪意のある観測者が暗号化されていない状態で見るのを防げることによってプライバシーを与える。暗号化及び解読によって使用される暗号化鍵は、システム・オンチップ上のオンチップ・メモリ（たとえば、ＳＲＡＭ）３４内に又はメモリ完全性チェック回路２０自体内に記憶され得る。任意の知られている技法が暗号化及び解読のために使用され得、暗号化鍵を保護するための任意の知られている手法が使用され得る。

メモリ完全性チェック回路２０はまた、以下で検証回路３６と概して呼ばれる完全性ツリー生成及び検証回路３６を含む。検証回路３６は、メモリ１４中で完全性ツリー２６を維持することを担当する。完全性ツリーは、メモリ１４中に現在記憶されたデータがそれがその領域に書き込まれたときと依然として同じであるのかどうかを検証するためのいくつかの情報を与え得る。データの完全性のチェックは、たとえば、認証コードを生成するために使用される秘密鍵が未知のものであるとき、攻撃者が特定のデータ値に関連する認証コードを力づくで推測するのを計算量的に実行不可能にする機能を使用する、ＡＥＳ－ＧＣＭ又はＳＨＡ－２５６などの一方向暗号関数を使用して記憶されたデータから生成され得るメッセージ認証コード（ＭＡＣ）を使用して達成され得る。認証コードは、データ２４と一緒に又は別個のデータ構造中に記憶され得る。データ値のための記憶されたＭＡＣは、記憶されたＭＡＣを生成するために使用される同じ一方向関数を使用して記憶されたデータから導出された計算されたＭＡＣに対してチェックされ、記憶されたＭＡＣと計算されたＭＡＣとの間に不一致が検出される場合、これは、データが改ざんされていることを示し得る。

しかしながら、ＭＡＣのみを与えることは、すべての攻撃を防げるのに十分でないことがある。別のタイプの攻撃は、システムへの物理的なアクセスをもつ悪意のある人が、暗号化データとバス上に前に観測されたＭＡＣとの正当な組み合わせを記憶し、次いで、システムの動作を損なうように、古い値をもつ所与のメモリ・ロケーションにあるデータを破損する意図で後でバス上でこれらをリプレイする、リプレイ・アタックであり得る。そのようなリプレイ・アタックは、完全性ツリー２６を使用して防げられ得、これは、ツリーの各リーフ・ノードが、保護されたメモリ領域２２中のデータ２４のブロックのうちの１つが有効であることを検証するための完全性データを与え、リーフ・ノードの親ノードが、リーフ・ノード自体が有効であることをチェックするための完全性データをさらに与えるノードのツリー構造を与え得る。親ノード自体は、ツリーのさらなる親ノードを使用してチェックされ得、これは、ツリーがツリーのルートまで横断されている間続き、それにより、検証の最終的なソースを与え得る。オンチップ・メモリ３４中に記憶されたルート・ノード３８は、ツリーのルートが真正であることを検証するために使用され得る。

メモリ完全性チェック・ユニット２０は、アドレスを計算するためのアドレス計算回路４０を有し得、そのアドレスにおいて、特定のデータ・ブロックをチェックするのに必要な完全性ツリー２６のノードは、保護メモリ領域２２中に位置する。任意選択で、メモリ・セキュリティ・ユニット２０はまた、オフチップ・メモリ１４から再び読み取られなければならない場合よりも速いアクセスのために完全性ツリーの最近使用されたノードをキャッシュするためのキャッシュ４２を有し得る。代替的に、メモリ完全性チェック・ユニット２０は、プロセッサ・コア６によっても使用され得るキャッシュ１０のうちの１つへのアクセスを有することができ、したがって、共有されたキャッシュ１０内の完全性ツリー２６からのデータのキャッシングはまた、メモリ完全性チェック・ユニット２０の動作を高速化するのを助けることができる。

以下で説明される技法は、データ２４の完全性を保護するタグを記憶するために完全性ツリー２６のために使用され得る新規の完全性保護構造（ネスト保護テーブル（ＮＰＴ：Nested Protection Table））を使用し、これは、パフォーマンスを犠牲にすることなしに保護されたキャッシュ・ラインが任意にサイズ決定された潜在的な保護範囲内の任意の場所に位置することを可能にしながら、（既存の完全性ツリー解決策が必要とするので）Ｏ｛潜在的な保護範囲｝の代わりにＯ｛実際の保護範囲｝にのみ比例するメモリ・フットプリントを必要とする。図２は、オンチップ・メモリ３４中に記憶されたルート・ノード３８とオフチップ・メモリ１４中に記憶されたいくつかのブランチ・ノード４４及びリーフ・ノード４６とを備える完全性ツリー２６の一実例を示す。ルート・ノード３８以外の各ノードは、所与の親ノードの子ノードであり、ここで、親ノードは、子ノードの完全性の検証中に使用され得る何らかの情報を与える。

各リーフ・ノード４６は、オフチップ・メモリ１４をアドレス指定するために使用されるアドレス空間の対応する保護されたアドレス・ブロック４８を検証するための完全性タグを与える（たとえば、保護されたアドレス・ブロックは１つのＤＲＡＭキャッシュ・ラインであり得るが、他の例は、異なる粒度でタグを与えることができる）。完全性タグは、（ＤＲＡＭキャッシュ・ラインなどの）メモリ・オブジェクトを認証するために使用される値である。タグは、オブジェクトによって計算されたハッシュ又は（キーを使用して計算された）ＭＡＣ値であり得る。どちらの場合も、フレッシュネスを保証し、対リプレイ保護を与えるためにタグを計算するときに追加の入力としてランニング・カウンタが使用され得る。

タグは、一般に、オフチップ・メモリ１４（たとえば、ＤＲＡＭ）中に記憶され、したがって、タグ自体の完全性も保証されなければならない。したがって、リーフ・ノード４６は、リーフ・ノード４６の親ノード（この実例では、レベル３のブランチ・ノード４４）によって与えられた完全性チェック値を使用して検証でき、そのブランチは、次いで、そのブランチ・ノードの親ノード（この実例では、レベル２のブランチ・ノード４４）によって与えられた完全性チェック値を使用して検証でき、以下、ルート・ノード３８がレベル０のブランチ・ノードの完全性を検証するために使用されるまでなどツリーを上に同様に行われる。このようにして、信用境界（たとえば、システム・オンチップの境界）内に与えられるルート・ノードは、信用境界を越えて記憶される完全性ツリー２６とデータ２４との完全性を保証するための信用の起点として使用され得る。

マークル・ツリー構成などのハッシュ・ツリーは、完全性タグの真正性を効率的に確認するための１つの機構である。これは、完全性タグにわたってハッシュ値の（たとえば、固定数の子孫：バイナリ、３値などをもつ）ｎ進ツリーを管理することによって達成される。保護されたオブジェクトと、それらの対応する完全性タグと、これらのタグを保護するハッシュ・ツリー・ノードとは、信用できないメモリ中に記憶される。ハッシュ・ツリー・ルートは、信用できるメモリ中に位置し、したがって、セキュアな認証チェーンを形成することが可能になる。上で説明されたハッシュ・ツリーの一変形形態は、保護されていないメモリ中にタグ自体を記憶し続けながら、タグのためにツリー・ベースの保護を提供することなしにタグを計算するために使用されるカウンタ値のみを保護する完全性ツリーを形成している。

信用できないメモリの完全性及びフレッシュネスを保証するのに良好な方法を有することは、あらゆる信用できる実行環境における基本要件である。それは、また、ホスト・ソフトウェア・メモリ管理に厳しい制限を提示することなしにメモリ・フットプリント及びパフォーマンスに関して解決するのが困難な問題である。マークル・ツリーを使用した実装は、ツリーによって保護できる保護アドレス範囲のサイズを厳しく限定する傾向がある。

これは、図３に示されるように、既存の完全性の実装が、保護された完全性である単一の限定された連続するＤＲＡＭアドレス範囲５０を定義することと、アドレス範囲全体を保護する対応するハッシュ・ツリー５２を形成することとに基づくからである。この手法では、ハッシュ・ツリー５２は、完全なツリーを形成し、任意の個々のツリー・ノード４４、４６のアドレスは、検証されるべき保護されたブロック４８のアドレスから直接的に計算され得る（アドレスは、関係するリーフ・ノード４６又はブランチ・ノード４４に直接インデックス付けするために使用され得る）。（解決策に応じて保護アドレス範囲の最高１６％であり得る）ハッシュ・ツリーのメモリ・フットプリントは、保護されるべき潜在的な範囲５０全体に適応するために前もって事前に割り振られる。ハッシュ・ツリー５２は、アドレス空間の単一の連続する領域を占有する必要がある。保護アドレス範囲が大きい場合、ハッシュ・ツリー５２に適応するのに十分なサイズの単一の割り振られていない領域を発見することは困難であり得るので、これは、問題になり得る。また、それらの最適化されたメモリ管理は、保護されたアプリケーション・ページ又はＶＭページを記憶するための物理ロケーションを自由に選定する能力を必要とするので、特定のアドレス範囲に保護を限定することはオペレーティング・システムに厳しい制限を提示することに留意されたい。

以下で説明される技法は、実際の保護されるメモリ・サイズのコストのみを発生しながらシステムの物理的メモリ全体にわたることができるメモリ範囲を保護するためのセキュアな完全性チェーン構造を形成することを可能にする。さらに、技法は、異なるメモリ・タイプ（たとえば、レイテンシ低減ＤＲＡＭ（Reduce Latency DRAM））中に記憶された構造を使用して１つのメモリ・タイプ（たとえば、低電力ＤＲＡＭ（Low Power DRAM）又は高帯域メモリ（High Bandwidth Memory）又はさらには永続メモリ（Persistent Memory））を保護することを可能にする。

図４の実例に示されるように、これは、新規のマルチレベルの完全性が保護されたネスト・テーブルを使用して達成され、ここで、テーブル中のタグ５６は、メモリ中でのそれらのロケーションへのポインタ５８とともに子タグのグループを保護する。テーブルは、システム・マップ内の任意のロケーション中に位置し得るページから構成され、したがって、事前プロビジョニングされたメモリのないセキュアな完全性ツリーを形成する。したがって、図５に示されるように、データの保護された領域と完全性ツリー自体との両方が、割り振られていない領域又は間に他のデータのために割り振られた領域をもつアドレス空間中のいくつかの不連続な領域にあり得る。

ネスト保護テーブル２６（完全性ツリー）内のリーフ・ページ４６は、複数のタグ・グループ６０（リーフ・エントリ）中で互いにグループ化される完全性タグ６１を保持し、ここで、各タグは、保護されたメモリ・チャンク（アドレス・ブロック）に対応する。

ブランチ・ページ４４は、複数のタグ・グループ（ブランチ・エントリ）６２を含み、ここで、各タグ・グループ６２は、子ページ（次のレベルのさらなるブランチ・ページ４４又はリーフ・ページ４６のいずれか）に対応し、タグ・グループ内の各タグ５６は、子ページ中の対応するタグ・グループ６２又は６０の完全性を保護する。

最初に、テーブルは、空であり、メモリを消費しない。リーフ・ページ４６は、ソフトウェアがキャッシュ・ライン又は完全性が保護されるべきページを登録するときに追加され、対応するリーフ・ページは、ネスト・テーブル２６中の予想されるロケーションに発見されない。ＮＰＴに追加されるリーフ・ページ及びブランチ・ページの物理的なページ・ロケーションは、管理ソフトウェアによって任意に定義され、これらは、任意の特殊な保護保証を必要としない。

ネスト保護テーブルを横断することは、リーフ・ページに達することと、タグを保護する完全性チェーンのタグを計算することとの２つの目的をサービスする。以下で説明される実例は、線形横断によって導入されるレイテンシを緩和するためにこれらの動作がどのように並列化されるのかを示す。

ネスト保護テーブル（ＮＰＴ）は、以下の３つの理由により古典的なｎ進の完全性ツリーでない。
－ 親ノードと子ノードとの間の接続は、ポインタ関連付けを通して行われ、典型的なｎ進ツリーの場合に行われるようなインデックス演算を使用しない。
－ テーブル中のポインタはヌルであり、したがって、必ずしも完全なツリーであるとは限らない構造を形成し得る。
－ ツリー中の各ブランチ・レベルは、前の「アリティ」とは異なるアリティを有し得る（及び一般に有することになる）。

キャッシュ・ラインは、タグが完全性ページ・テーブル中に発見される場合にのみ完全性計算を必要とする。ヌル指示がブランチ・ページ４４中に発見されるとき横断が停止され得るので、これは、キャッシュ・ラインが（ツリー全体を横断することなしに）保護を必要としないクイック検出を可能にする。

ネスト保護テーブルのサイズは、動的に拡張及び収縮する。また、所与のＮＰＴによってカバーされる潜在的なアドレス範囲（たとえば、６４ＧＢ）は、最大限にサポートされる物理アドレス範囲（たとえば、６４ＴＢ）で任意のオフセットから開始して定義され得る。高パフォーマンスは、キャッシングと推測とを使用し、それのキャッシュをウォーム・アップすること可能にするアクセス制御エンジンからネスト保護エンジンへのヒント信号を活用することによって達成され得る。

より詳細には、図４に示されるように、ネスト保護テーブル２６は、以下の原則に基づく。
１．タグ６１、５６は、メモリ・チャンク（一般に、キャッシュ・ライン）の真正性を検証することを可能にする値である。タグ計算部分で説明されるようにメモリ・チャンクによってタグを計算するための様々な方法がある。
２．タグ・グループ６０、６２は、連続するメモリ・チャンク（一般に、キャッシュ・ライン）内に位置するタグの集合である。
３．リーフ・ページ４６は、複数のタグ・グループ６０（リーフ・エントリ）を含んでいる。
ａ．タグ・グループ６０中の各タグ６１は、メモリのチャンクを保護する。
ｂ．リーフ・ページ中のいくつかのタグ・グループ６０は、タグ・サイズ、リーフ・ページ・サイズ、及びタグ・グループ・サイズによって定義される。
ｉ．一実例として、４ＫＢのリーフ・ページは、６４個のタグ・グループを含み得、ここで、各グループは、それぞれ６４ビットの８つのタグを含んでおり、各タグは、６４Ｂのメモリを保護し、したがって、リーフ・ページ全体は、メモリの３２ＫＢのブロックを保護する。
４．ブランチ・ページ４４は、複数のブランチ・エントリ６２を含んでおり、ここで、各エントリ６２は、以下のパラメータを含む。
ａ．ネクスト・ポインタ（NextPointer）５８。これは、リーフ・ページ又は次のレベルのブランチ・ページのいずれかをポイントし得る。
ｂ．タグ・グループ５６。各タグがネクスト・ポインタによってポイントされるページ中の対応するエントリを保護するタグのグループ（完全性チェック値、たとえば、ハッシュ、ＭＡＣ、又はカウンタ）。
ｉ．ネクスト・ポインタ５８がリーフ・ページ４６をポイントする場合、タグは、リーフ・ページ４６中の対応するタグ・グループ６０を保護する。
ｉｉ．ネクスト・ポインタ５８がブランチ・ページ４４をポイントする場合、タグは、ブランチ・ページ中のネクスト・ポインタ５８とタグ・グループ６２とから構成されるエントリ６２を保護する。
５．ルート・テーブル３８は、レベル０のブランチ・ページ（レベル０は単一のページを含む）をポイントするベース・ポインタ６４と単一のタグ・グループ６２とを含んでおり、ここで、各タグは、レベル０のブランチ・ページ中の対応するエントリ６２を保護する。
ａ．ルート・テーブル３８は、チップ境界内に常駐し、ＮＰＴ全体のための信用の起点として働く。

図４は、最高８ＧＢのメモリを保護することができるネスト保護テーブルの一実例を示し、ここで、ページ・サイズは４ＫＢであり、タグ・サイズは、５６ビットであると仮定される。各ページ中のエントリの数は、ブランチ・レベルに従って変動する。
－ リーフ・ページは、６４個のタグ・グループを含み、ここで、各グループは８つのタグを記憶する。
－ レベル３のブランチ・ページは、８つのエントリを含み、ここで、各エントリは、６４個のタグとポインタとを含む。
－ レベル２のブランチ・ページは、６を含む。
－ ４エントリ、ここで、各エントリは、８つのタグとポインタとを含む。
－ レベル１のブランチ・ページは、８つのエントリを含み、ここで、各エントリは、６４個のタグとポインタとを含む。
－ レベル０のブランチ・ページは、６４個のエントリを含み、ここで、各エントリは、８つのタグとポインタとを含む。
－ オンチップ・ルート・テーブルは、ベース・ポインタと６４個のタグとを含む。

図６及び図７は、ネスト保護ブランチとリーフ・ページとのために提案された２つの変形形態を示す。両方の変形形態では、完全性コンテキストを記憶するように要求されるメモリは、オンデマンドで割り振られる。

図６に示されるように、変形形態１では、リーフ・ページは、対応するキャッシュ・ラインによって計算される実際のタグ値を含んでいる。ブランチ・ページ４４の各ブランチ・エントリ６２は、それぞれがそのブランチ・エントリ６２のポインタ５８によってポイントされる子ノードの対応するブランチ・エントリ６２又はリーフ・エントリ６０のコンテンツによって計算されるいくつかのタグ値（ハッシュ又はＭＡＣ）を含んでいる。

図７に示されるように、変形形態２では、リーフ・ページは以下を含んでいる。
１．キャッシュ・ライン・タグを計算するときに追加の入力として使用されるナンス（１回だけ使用される番号（Number used Once））値７０。ナンスは、タグのフレッシュネスを保証することが可能で、単調カウンタとして実装され得る。変形形態２では、カウンタの完全性のみがＮＰＴによって保護される必要がある。
２．各タグが対応するキャッシュ・ラインを保護し、対応するナンスを使用して計算されるタグ７２。これがカウンタを保護することによって間接的に保証されるので、タグの完全性はＮＰＴによって保護される必要がない。

タグとカウンタとの両方は、リーフ・ページ内の対応するタグ・グループとタグ・カウンタとの下でグループ化される。所与のリーフ・エントリ６０は、タグ７２のグループとカウンタ（ナンス）７０の対応するグループとを備える。
リーフ・ページは、カウンタ・グループとそれらの対応するタグ・グループとのロケーションを指定するあらかじめ定義された構造を有する。これは、所与の物理アドレスに対応するカウンタ及びタグのロケーションへの直接アクセスを可能にする。

一方、変形形態２では、ブランチ・ページ４４の所与のブランチ・エントリ６２は、ポインタ６２と、カウンタ（ナンス）７４のグループと、そのブランチ・ページ４４の親ノードの対応するブランチ・エントリ６２によって与えられた対応するカウンタを使用してカウンタ・グループ７４によって計算される単一のタグ値７６とを備える。同様に、カウンタ・グループ７４中の各カウンタは、そのブランチ・ページ４４の子であるブランチ・ノード又はリーフ・ノード内のそれぞれの子エントリの計算において使用される。

したがって、カウンタの完全性は、カウンタ・グループを形成し、グループの完全性を保護するそのような各グループにカウンタ・タグ７６を追加することによって保証される。カウンタ・タグ計算への入力は、カウンタ・グループの親ノードからの追加のカウンタ値である。変形形態２の利点は、保護されたカウンタがタグよりも著しく小さくなり得、したがって、それの完全性を保護するメモリ・コストがより低くなるということである。

図６及び図７の２つの変形形態は、メモリ・フットプリントと計算レイテンシとの間でトレードオフを図ることを可能にする。したがって、ブランチ・ページ４４のブランチ・エントリ中の完全性チェック値は、子ページ４４の対応する子エントリのコンテンツに基づいて生成されるいずれかの完全性タグ（ハッシュ又はＭＡＣ）であり得るか、又は子ページ４４の子エントリ中のカウンタ・タグ７６の計算において使用されるカウンタであり得る。

図８に示されるように、変形形態２では、リーフ・ノード又はブランチ・ノードの所与のエントリ中のカウンタ・グループ７０、７４のために検討され得る以下の２つの可能な構造がある。
１．グループ中の各カウンタが暗号要件によって定義された全幅を有する非分割カウンタ・グループ（図８の右側）。
２．副カウンタのグループは、任意の副カウンタがオーバーフローするときはいつでも増分される単一の主カウンタを共有し、したがって、カウンタを記憶するときにビットを節約することができる分割カウンタ・グループ（図８の左側）。分割カウンタの実装では、副カウンタがオーバーフローし、主カウンタが、所与のブランチ・エントリ６２中で増分されるとき、カウンタ・グループ・タグ７６は、所与のブランチ・エントリ６２のポインタ６２によってポイントされる子ページ中の子エントリのすべてのために再計算される必要があることになる。

ネスト保護テーブル（ＮＰＴ）２６を管理するための及びメモリを認証するためにそれを使用するための動作は、（オンチップのネスト保護エンジン（ＮＰＥ）として働く）メモリ完全性チェック回路２０によって実行される。ＮＰＥは、以下の動作を実行する。

タグを追加し、タグを更新すること
ソフトウェアは、ＮＰＴに対応するタグを追加するようにＮＰＥ２０に要求することによってキャッシュ・ライン・アドレスを保護することに対するそれの関心を登録する。キャッシュ・ライン自体が加算されるときに読み取られていないか又はタグを追加するときに初期化されていない場合、完全性値がキャッシュ・ラインによって計算されるとき、タグは、最初に０に設定され、後に１に設定される修飾子ビットを含み得る。代替的に、キャッシュ・ラインは、加算演算の一部として読み取られ得、それの完全性値が計算され、タグに書き込まれる。

キャッシュ・ラインよりも高い粒度で動作することは、ＮＰＴのためのより高いレベルのメモリ効率を保証することになるが、ソフトウェアは、任意のレベルの粒度（キャッシュ・ライン、ページ、又はページのブロック）で完全性についての関心を登録することを選定することができる。

ＮＰＴにタグを追加する動作又はＮＰＴ中のタグを更新する動作は、変形形態１の場合では図９に示されるように統一シーケンスに基づく。

注：流れの各ステージにおいて、ポインタ値がヌルである場合、以下の動作を実行する。
ａ．メモリ中にページを割り振り、割り振られたページのアドレスに現在のステージにあるポインタを設定する（ポインタは後でタグ計算に含まれることになる）。
ｂ．新しいページをゼロに初期化する。
ｃ．追加されたページ中の対応する子タグ・グループ（又はグループ）によってタグを計算することによって更新されたポインタのエントリ中のタグ・グループを初期化する。
タグを更新するための流れは、次のように要約され得る。
１．オフセットのセットに物理アドレス［ＭＳＢ：０］を区分し（図９を参照）、ここで、各オフセットは、異なるＮＰＴレベル２に対応する。
２．ポインタにアドレス・オフセットを追加することによってそれのベース・ポインタから開始し、読み取り結果のコンテンツから次のレベルにポインタを抽出してＮＰＴを走査する。
３．読み取られている各エントリから次のレベルのポインタを抽出し、次の読み取りをサブミットすることに並行してそれに対してタグ検証演算を実行する。
４．リーフ・ページに達し、それからタグ・グループを読み取るとき、更新されたキャッシュ・ラインによって計算されるタグがそのグループに書き込まれる。
５．次いで、リーフ・タグ・グループからルート・タグ・グループまでのチェーン上のすべてのタグ・グループが、再計算され、メモリに記憶される。

タグ計算方法（タグ検証、タグ計算演算）：
タグを計算するためのいくつかのオプションがあり、ここでは、いくつかの例示的な方式しかリストしていない。まず第一に、２つの事例を区別する。
・ ハッシュ・ツリーの事例（変形形態１）では、ハッシュすべきメッセージｍは、ポインタとそれと一緒にパックされるハッシュのグループとによって形成される。
・ カウンタ・ツリーの事例（変形形態２）では、メッセージｍは、ポインタとそれと一緒にパックされるカウンタのグループとの連結であり得、また、親ノード中に対応するカウンタｃ_ｐをも含み得る。分割カウンタ・グループ構造が使用される場合、カウンタのグループは、それのセットの副カウンタをもつ主カウンタとなるように意図されるが、親ノード中のカウンタｃ_ｐは、主カウンタの、及び子ノードに対応する副カウンタの連結になる。

メッセージｍが定義されると、それのハッシュを計算することの問題がある。いくつかの方法は、以下の通りである。
１．ＳＨＡ－２、ＳＨＡ－３、ＳｉｐＨａｓｈなどの標準的に又は一般的に使用されるハッシュ関数を使用する。カウンタ・ツリーの場合、親カウンタｃ_ｐがメッセージ中に含まれる。
２．カーター－ウェッグマン・ユニバーサル・ハッシュ関数を使用する。ｍ＝ｍ_１｜ｍ_２｜．．｜ｍ_ｒを書き込み、ここで、ｍ_１…ｍ_ｒ－１は、同じビット長ｂのものであり、ｍ_ｒは、同じビット長のものであるか又はｂビットにパディングされるかのいずれかである。次いで、最初にガロア体Ｆ中で
ｈ’＝Σ_ｉ＝１ ^ｒｍ_ｉ・χ^ｉ
を計算し、ここで、χ∈Ｆは、非ゼロの秘密値であり、次いで、
ｈ＝ｈ’＋Ｅ_Ｋ（ｃ_ｐ）として結果を暗号化し（加算は同じガロア体中にある）、
ここで、Ｅ_Ｋ（）は、秘密グローバル鍵Ｋを使用する暗号化関数である。
代替的に、暗号化は、
ｈ＝Ｅ_Ｋ（ｈ’＋ｃ_ｐ）
として実行され得るが、この場合、ｈ’の計算は、Ｅ_Ｋ（）の呼び出しと並行して実行されないことがある。
３．（ＡＥＳなどの）ブロック暗号アルゴリズムを選定し、鍵を使用してｍを暗号化することによって完全性チェック値を生成することによって、標準ＭＡＣを使用する。
注：ＮＰＴを記憶するメモリが他の考慮事項により暗号化される場合、親カウンタｃ_ｐが常にｍ中に含まれる限り暗号化ステップは省略され得る。

キャッシュ・ラインを検証すること
キャッシュ・ラインを検証する動作は、変形形態１の場合では図１０に示されるようにシーケンスに基づく。（図９について上で説明されたステップ１～３と同様）

図１０の左上のハードウェア・ビューに示されるように、計算とツリーの横断とは並行して行われ、したがって、１つの動作のレイテンシは他方によって隠される。図は、この並列化をサポートするハードウェア・エンジンを示す。

変形形態１について上で説明されたようなタグを検証することとタグを更新することとの動作はまた、以下の小さい変更点とともに変形形態２に適用可能である。
－ タグを検証すること
〇キャッシュ・ライン・タグを検証するとき、そのタグに対応するカウンタが計算に含まれる。
〇カウンタ・タグを検証することは、カウンタ・グループ中のすべてのカウンタと親カウンタとによってタグを計算することによって実行される。
－ キャッシュ・ライン・タグを更新するとき、そのタグに関連するカウンタが増分され、増分されたカウンタのあらゆる親カウンタも増分される。次いで、このチェーンにわたるタグ・カウンタが更新されたカウンタ値によって再計算される。
図９及び図１０に示された正確な詳細は、一実例にすぎず、たとえば、物理アドレスの各オフセット部分中のツリー・レベルの数及びビットの数は変動できることが諒解されよう。

タグを除去すること
キャッシュ・ラインがもはや保護される必要がないとき、タグは、ソフトウェアが０に更新する各タグ中の単一ビットの修飾子フラグを定義することによってデータベースから除去できる。複数のタグ又はタグ・グループを修飾する単一のフラグを有することも可能である。
タグ修飾子がゼロ化されるときはいつでも、ソフトウェア又はＮＰＥ２０はまた、ページ中の追加のタグが０であるのかどうかをチェックすることができる。ページ中のすべてはタグ・グループにわたってチェックを実行することによって、ページ全体がＮＰＴから除去され得る。

完全性保護が必要とされるのかどうかをチェックする
キャッシュ・ラインがアクセスされるときはいつでも、ＮＰＥは、完全性保護がそれに必要とされないことを迅速に解決することができる。これは、ヌル・ポインタ又は無効なタグに到着するまでＮＰＴを横断することによって行われる（無効なタグは、予約された値をもつタグ又は修飾子＝０をもつタグであり得る）。一般にメモリの小部分のみが完全性を保護されるので、ヌル・ポインタがすぐに発見されることになるので、本方法は、横断が完全性を必要としない大多数のキャッシュ・ラインのために短くなるであろうことを保証する。システムはまた、キャッシュ・ラインのために完全性が必要とされるのかどうかについての読み取り又は書き込み動作に関するヒントを追加することによってこのプロセスを増強することができる。

パフォーマンスの向上
マークル・ツリーに適用可能なパフォーマンスの向上方法（すなわち、キャッシング及び投機的実行）はまた、それ自体の変形形態をもつＮＰＴに適用可能であり得る。

ＮＰＴエントリをキャッシュすること：パフォーマンスを高速化するために、ＮＰＴの要素がＮＰＥ２０のキャッシュ４２内にキャッシュされ得る。ブランチ・ページ・エントリ、リーフ・ページ・エントリ、又は｛物理アドレス，カウンタ，タグ｝タプルのいずれかがキャッシュされ得る。

投機的実行：キャッシュ・ラインの完全性を検証することは、必ずしもユーザのデータの復帰をブロックする必要があるとは限らない。ＮＰＥは、検証の流れを完了する前にユーザにデータを投機的に戻し、完全性エラーが発生すると不揮発性記憶装置又は外部ＩOデバイスへのすべての更新をブロックするアボート信号を使用し得る。このようにして、システム状態は、エラーがシステムの境界の外部に伝搬する前にセキュリティ保護される。

上記の上に、メモリ・アクセス回路１２からのヒント信号８２に基づく新しいパフォーマンスの向上方法を提案する。セキュアなシステム中で、ＭＭＵ動作は、それのキャッシュへの物理アドレスのロードと、実際のロード／記憶動作が実行される前にアドレスに対する追加のアクセス制御チェックを実行することとを生じ得る。図１に示されるように、物理アドレスがＴＬＢ８０又はＭＭＵに知られると、これらの構成要素は、特定の物理アドレスについてＮＰＥにヒント８２を送ることができ、したがって、ＮＰＥは、許可チェック回路８４によって実行される任意のアクセス許可チェックが完了するのを待つことなしに、対応するブランチ・ページ・エントリを読み取ることを開始することによってそれのキャッシュをウォーム・アップすることができる。このようにして、並列化が、ＭＭＵアクセス制御チェックと所与のキャッシュ・ライン・アクセスの完全性チェックとの間で達成される。図１が、ＴＬＢ８０中にキャッシュされるページ・テーブル・エントリに基づいて許可チェックを実行することの一実例を示すが、ヒントを生成するために他のタイプのアクセス許可チェックを実行することも可能であろう。

図１１は、完全性ツリー２６に追加のレベルを追加するためにメモリ完全性チェック回路２０によって実行され得る別の動作を示す。ステップ１００において、ソフトウェアは、追加のツリー・レベルを追加することを求める要求を送ることをトリガし得る。それに応答して、ステップ１０２において、完全性ツリー検証／生成回路３６は、要求中にソフトウェアによって指定されたアドレスにおいてオフチップ・メモリ１４に新しいレベル０のブランチ・ノード４４を記憶する。新しいレベル０のブランチ・ノードは、テーブルのルート・ノード３８中に前に指定されたパラメータに対応するパラメータを指定することになる。したがって、前にレベル０のブランチ・ノードであったブランチ・ノード４４は、レベル１のブランチ・ノードになることになり、レベル１のブランチ・ノードは、レベル２のブランチ・ノードになることになり、以下同様に行われる。新しいレベル０のブランチ・ノードでは、タグ・グループ（ブランチ・エントリ）６２のうちの１つは、ルート・ノード３８の前のコンテンツに対応し、同じブランチ・ページ４４中のすべての他のブランチ・エントリ６２は、それらのエントリの下にいかなるさらなる子ノードもまだないことを示すためにヌル・インジケータを与えるポインタ５８を用いて設定され得る。ステップ１０４において、完全性ツリー検証及び生成回路３６は、メモリに割り振られた新しいレベル０のブランチ・ノードのアドレスを指定するためにルート・ノード３８中のポインタ６４を更新する。ステップ１０６において、完全性ツリー検証／生成回路３６は、新しいトップレベルのブランチ・ノード４４のコンテンツに対応するためにルート・ノード３８の少なくとも１つの完全性チェック値を更新する。上で説明された変形形態１が使用される場合、ルート・テーブル内の各タグは、新しいレベル０のブランチ・ノード４４の対応するエントリ６２のハッシュに基づいて更新され得る（ここで、ハッシュは、ポインタとタグとの両方に基づく）。変形形態２が使用される場合、ルート・テーブル６４内のカウンタは、新しいレベル０のブランチ・ノードの各エントリ内の対応するカウンタ・ハッシュを計算するために使用される値に更新され得る。

図１２は、使用され得る一シミュレータ実装形態を示す。より前に説明された実施例が、関係する技法をサポートする特定の処理ハードウェアを動作させるための装置及び方法に関して本発明を実装するが、コンピュータ・プログラムを使用することによって実装される本明細書で説明される実施例に従って命令実行環境を与えることも可能である。そのようなコンピュータ・プログラムは、それらがハードウェア・アーキテクチャのソフトウェア・ベースの実装形態を与える限り、しばしば、シミュレータと呼ばれる。様々なシミュレータ・コンピュータ・プログラムは、エミュレータと、仮想マシンと、モデルと、動的バイナリ・トランスレータを含むバイナリ・トランスレータとを含む。一般に、シミュレータ実装形態は、シミュレータ・プログラム２１０をサポートする、随意にホスト・オペレーティング・システム２２０を実行するホスト・プロセッサ２３０上で動作し得る。一部の構成では、ハードウェアと与えられた命令実行環境及び／又は同じホスト・プロセッサ上に与えられた複数の別個の命令実行環境との間にシミュレーションの複数のレイヤがあり得る。歴史的に、妥当な速度で実行するシミュレータ実装形態を与えるために強力なプロセッサが必要とされてきたが、そのような手法は、適合性又は再使用の理由のために別のプロセッサにネイティブなコードを実行する要望があるときなどいくつかの状況で正当化され得る。たとえば、シミュレータ実装形態は、ホスト・プロセッサ・ハードウェアによってサポートされない追加の機能を命令実行環境に与え得るか、又は異なるハードウェア・アーキテクチャに一般に関連する命令実行環境を与え得る。シミュレーションの概要は、「Ｓｏｍｅ Ｅｆｆｉｃｉｅｎｔ Ａｒｃｈｉｔｅｃｔｕｒｅ Ｓｉｍｕｌａｔｉｏｎ Ｔｅｃｈｎｉｑｕｅｓ」、Ｒｏｂｅｒｔ Ｂｅｄｉｃｈｅｋ、１９９０年冬季ＵＳＥＮＩＸ Ｃｏｎｆｅｒｅｎｃｅ、５３～６３ページで与えられる。

実施例が特定のハードウェア構成体又は特徴を参照しながら前に説明された程度まで、シミュレート実施例では、等価な機能が好適なソフトウェア構成体又は特徴によって提供され得る。たとえば、特定の回路が、コンピュータ・プログラム論理として一シミュレート実施例中に実装され得る。同様に、レジスタ又はキャッシュなどのメモリ・ハードウェアは、ソフトウェア・データ構造として一シミュレート実施例中に実装され得る。前に説明された実施例において参照されるハードウェア要素のうちの１つ又は複数がホスト・ハードウェア（たとえば、ホスト・プロセッサ２３０）上に存在する構成では、いくつかのシミュレート実施例は、適切な場合、ホスト・ハードウェアを利用し得る。

シミュレータ・プログラム２１０は、（非一時的媒体であり得る）コンピュータ可読記憶媒体上に記憶され得、シミュレータ・プログラム２１０によってモデル化されているハードウェア・アーキテクチャのアプリケーション・プログラム・インターフェースと同じである（アプリケーションと、オペレーティング・システムと、ハイパーバイザとを含み得る）ターゲット・コード２００にプログラム・インターフェース（命令実行環境）を与える。したがって、上で説明されたものを含むターゲット・コード２００のプログラム命令は、シミュレータ・プログラム２１０を使用して命令実行環境の中から実行され得、したがって、上で説明された装置４のハードウェア特徴を実際に有しないホスト・コンピュータ２３０がこれらの特徴をエミュレートすることができる。シミュレータ・プログラム２１０は、上で説明されたメモリ・アクセス回路１２とメモリ完全性チェック回路２０との機能をエミュレートするメモリ・アクセス・プログラム・アクセス・プログラム論理２１２とメモリ完全性チェック・プログラム論理２１４とを有し得る。

本出願中で、「～するように構成される」という言葉は、装置の要素が定義された動作を実行することが可能な構成を有することを意味するために使用される。このコンテキストでは、「構成」は、ハードウェア又はソフトウェアの相互接続の構成又は方式を意味する。たとえば、本装置は、定義された動作を与える専用ハードウェアを有し得るか、又はプロセッサ若しくは他の処理デバイスは、機能を実行するようにプログラムされ得る。「するように構成される」は、本装置要素が定義された動作を与えるために何らかの方法で変更される必要があることを暗示しない。

本発明の例示的な実施例が添付の図面を参照しながら本明細書において詳細に説明されているが、本発明は、それらの正確な実施例に限定されないことと、様々な変更及び修正が、添付の特許請求の範囲によって定義されたように本発明の範囲及び趣旨から逸脱することなく当業者によって本明細書中で実施され得ることを理解されたい。

Claims (25)

1. メモリ中に記憶されたデータへのアクセスを制御するためのメモリ・アクセス回路と、
   複数のノードを備える完全性ツリーを使用して前記メモリ中に記憶されたデータの完全性を検証するためのメモリ完全性チェック回路と
   を備える装置であって、前記複数のノードは、
   前記メモリ中に記憶されたデータの対応するアドレス・ブロックの検証のための少なくとも１つの完全性タグを備える少なくとも１つのリーフ・エントリを備える少なくとも１つのリーフ・ノードと、
   少なくとも１つのブランチ・エントリを備える少なくとも１つのブランチ・ノードであって、
   前記ブランチ・ノードの子ノードのアドレスを指定するためのポインタであって、前記子ノードは、リーフ・ノードであるか、又は前記完全性ツリーのさらなるブランチ・ノードである、ポインタと、
   前記子ノードの対応するブランチ・エントリ又はリーフ・エントリの検証のための少なくとも１つの完全性チェック値と
   を備える少なくとも１つのブランチ・ノードと
   を含む、装置。
2. 前記メモリ完全性チェック回路は、所与の前記ブランチ・ノードの親ノード中に指定されている対応する完全性チェック値に基づいて、前記ポインタを含む所与のブランチ・エントリによって指定された情報の完全性を検証するように構成された、
   請求項１に記載の装置。
3. 前記メモリ完全性チェック回路は、前記完全性ツリーが、メモリ・アドレス空間内のアドレス・ブロックの不連続なグループに対応するリーフ・エントリを指定する１つ又は複数のリーフ・ノードを含むように構成されることをサポートするように構成され、ここで、アドレス・ブロックの前記不連続なグループ間のアドレス・ブロックの少なくとも１つの介在グループは、前記完全性ツリーによって保護されていない、
   請求項１又は２に記載の装置。
4. 前記メモリ完全性チェック回路は、前記完全性ツリーが、メモリ・アドレス空間内のアドレス・ブロックの２つ以上の不連続なグループに記憶されたノードを含むように構成されることをサポートするように構成され、ここで、アドレス・ブロックの前記不連続なグループ間のアドレス・ブロックの少なくとも１つの介在グループが、
   割り振られていないメモリと、
   前記完全性ツリー以外のデータを記憶するために割り振られたメモリと
   のうちの少なくとも１つを備える、
   請求項１から３までのいずれか一項に記載の装置。
5. 前記メモリ中に記憶されたデータの所与のアドレス・ブロックのターゲット・アドレスを指定する要求に応答して、前記メモリ完全性チェック回路は、ルート・ノードから前記所与のアドレス・ブロックに対応する前記完全性タグを備える所与のリーフ・ノードまでの前記完全性ツリーのトップダウン横断をトリガするように構成された、
   請求項１から４までのいずれか一項に記載の装置。
6. 前記トップダウン横断において、前記ルート・ノードから前記所与のリーフ・ノードまでの経路上の前記完全性ツリーの所与の親子ノード・ペアについて、前記所与の親子ノード・ペアは、所与の親ノードと所与の子ノードとを備え、前記メモリ完全性チェック回路は、
   前記所与の親ノードの対応する親エントリによって指定された前記ポインタと前記所与のアドレス・ブロックの前記ターゲット・アドレスに基づいて識別されたオフセットとに基づいて計算されるメモリ・アドレスから前記所与の子ノードの対応する子エントリを読み取る、読み取り動作をトリガすることと、
   前記所与の親ノードの前記対応する親エントリ中に指定されている対応する完全性チェック値に基づいて前記対応する子エントリの完全性を検証する、検証動作を実行することと
   を行うように構成された、
   請求項５に記載の装置。
7. 前記所与の親ノードが前記完全性ツリーのルート・ノード以外のノードであるとき、
   前記メモリ完全性チェック回路は、前記トップダウン横断の前のステップのための前記検証動作を実行することと並行して前記所与の子ノードの前記対応する子エントリを読み取る前記読み取り動作をトリガすべきであり、前記前のステップのための前記検証動作は、前記所与の親ノードの親ノード中に指定されている対応する完全性チェック値に基づいて、前記対応する親エントリの完全性を検証することを備える、
   請求項６に記載の装置。
8. 前記メモリ完全性チェック回路は、前記ルート・ノードから前記所与のリーフ・ノードまでの経路上に、前記所与のアドレス・ブロックのための対応するブランチ・エントリがヌル・インジケータを指定するブランチ・ノードを検出したことに応答して前記トップダウン横断を停止するように構成された、
   請求項５から７までのいずれか一項に記載の装置。
9. 前記ヌル・インジケータは、
   ヌル値を指定する前記ポインタ、
   ヌル値を指定する前記所与のアドレス・ブロックに対応する前記完全性チェック値
   のうちの１つを備える、
   請求項８に記載の装置。
10. 前記トップダウン横断が、メモリ中の前記所与のアドレス・ブロックへのメモリ・アクセスをトリガするためのメモリ・アクセス要求によってトリガされ、前記トップダウン横断は、前記対応するブランチ・エントリが前記ヌル・インジケータを指定するブランチ・ノードを検出するとき、前記メモリ完全性チェック回路は、
    前記所与のアドレス・ブロックを、完全性検証が必要とされない保護されていないアドレス・ブロックとして扱うことと、
    前記所与のアドレス・ブロックについて完全性検証が成功したという指示を戻すことと
    のうちの少なくとも１つを実行するように構成された、
    請求項８又は９に記載の装置。
11. 前記トップダウン横断は、前記完全性ツリーの対応するリーフ・ノードへの前記所与のアドレス・ブロックのための完全性タグの追加を要求するタグ追加要求によってトリガされ、前記トップダウン横断は、前記対応するブランチ・エントリが前記ヌル・インジケータを指定する所与のブランチ・ノードを検出するとき、前記メモリ完全性チェック回路は、
    前記所与のブランチ・ノードのさらなる子ノードを記憶するためにメモリ・アドレス空間を割り振るようにソフトウェアをトリガすることと、
    前記さらなる子ノードのために割り振られるものとして前記ソフトウェアによって指定されたアドレスを示すように前記所与のブランチ・ノードの前記対応するブランチ・エントリの前記ポインタを更新することと
    を行うように構成された、
    請求項８から１０までのいずれか一項に記載の装置。
12. 所与のアドレス・ブロックのためのデータへのアクセスを要求するメモリ・アクセス要求に応答して、前記メモリ・アクセス回路は、
    前記所与のアドレス・ブロックがアクセスされることを許可されるのかどうかをチェックするためにアクセス許可チェックを実行することと、
    前記アクセス許可チェックが完了する前に、前記メモリ完全性チェック回路に前記所与のアドレス・ブロックのアドレスを指定するヒント信号を与えることと
    を行うように構成された、
    請求項１から１１までのいずれか一項に記載の装置。
13. 前記ヒント信号に応答して、前記メモリ・アクセス回路によって実行される前記アクセス許可チェックが完了する前に、前記メモリ完全性チェック回路は、前記完全性ツリーの少なくとも１つのノードの読み取りをトリガするように構成された、
    請求項１２に記載の装置。
14. 前記メモリ完全性チェック回路は、前記完全性ツリーによって保護された前記データを記憶する同じメモリからルート・ノード以外の前記完全性ツリーのノードを読み取るように構成された、
    請求項１から１３までのいずれか一項に記載の装置。
15. 前記メモリ完全性チェック回路は、異なるメモリから、前記完全性ツリーによって保護された前記データを記憶する前記メモリに、ルート・ノード以外の前記完全性ツリーのノードを読み取るように構成された、
    請求項１から１３までのいずれか一項に記載の装置。
16. 前記メモリ完全性チェック回路は、前記メモリ完全性チェック回路と同じ集積回路内に与えられるオンチップ・メモリから、前記完全性ツリーのルート・ノードを読み取るように構成された、
    請求項１から１５までのいずれか一項に記載の装置。
17. 前記ルート・ノードは、
    前記完全性ツリーのトップレベルのブランチ・ノードのアドレスを指定するためのポインタであって、前記トップレベルのブランチ・ノードは、前記ルート・ノードの子ノードである、ポインタと、
    前記トップレベルのブランチ・ノードの対応するブランチ・エントリの検証のための少なくとも１つの完全性チェック値と
    を備える、
    請求項１６に記載の装置。
18. 前記完全性ツリーにレベルを追加することの要求に応答して、前記メモリ完全性チェック回路は、
    前記完全性ツリーの新しいトップレベルのブランチ・ノードを、前記新しいトップレベルのブランチ・ノードを記憶するために割り振られたものとして、ソフトウェアによって指定されたアドレスに記憶することであって、前記新しいトップレベルのブランチ・ノードは、前記ポインタと前記ルート・ノードによって前に指定された前記少なくとも１つの完全性チェック値とを含む、記憶することと、
    前記新しいトップレベルのブランチ・ノードを記憶するために割り振られた前記アドレスを指定するように前記ルート・ノードの前記ポインタを更新することと、
    前記新しいトップレベルのブランチ・ノードのコンテンツに対応するように前記ルート・ノードの前記少なくとも１つの完全性チェック値を更新することと
    を行うように構成された、
    請求項１７に記載の装置。
19. 所与のブランチ・ノードの所与のブランチ・エントリ中で、各完全性チェック値は、前記所与のブランチ・エントリの前記ポインタによってポイントされた前記子ノードの前記対応するブランチ・エントリ又はリーフ・エントリの関数として導出される完全性タグを備える、
    請求項１から１８までのいずれか一項に記載の装置。
20. 所与のブランチ・ノードの所与のブランチ・エントリ中で、各完全性チェック値は、前記所与のブランチ・エントリの前記ポインタによってポイントされた前記子ノードの前記対応するブランチ・エントリ又はリーフ・エントリ中に記憶された対応する完全性タグを計算するための少なくとも１つの完全性ナンスであって、前記対応する完全性タグは、前記完全性ナンスと前記子ノードの前記対応するブランチ・エントリ又はリーフ・エントリの他のコンテンツとの関数として導出される、少なくとも１つの完全性ナンスを備える、
    請求項１から１８までのいずれか一項に記載の装置。
21. 前記所与のブランチ・エントリは、前記子ノードのそれぞれのブランチ・エントリ又はリーフ・エントリに対応する完全性ナンスのグループを指定し、共有完全性タグは、完全性ナンスの前記グループと前記所与のブランチ・ノードの親ノード中に指定されている完全性ナンスとの関数として導出される、
    請求項２０に記載の装置。
22. 完全性ナンスの前記グループは、
    前記子ノードの各ブランチ・エントリ又はリーフ・エントリのために独立して指定された非分割カウンタのグループと、
    分割カウンタのグループであって、各分割カウンタは、前記子ノードの前記それぞれのブランチ・エントリ又はリーフ・エントリ間で共有される主カウンタと、前記子ノードの各ブランチ・エントリ又はリーフ・エントリのために別個に指定される副カウンタとの組み合わせとして表される、分割カウンタのグループと
    のうちの１つを備える、
    請求項２１に記載の装置。
23. メモリ中に記憶されたデータへのアクセスを制御することと、
    複数のノードを備える完全性ツリーを使用して、前記メモリ中に記憶されたデータの完全性を検証することと
    を含む方法であって、前記複数のノードは、
    少なくとも１つのリーフ・エントリを備える少なくとも１つのリーフ・ノードであって、各リーフ・エントリは、前記メモリ中に記憶されたデータの対応するアドレス・ブロックの検証のための少なくとも１つの完全性タグを備える、少なくとも１つのリーフ・ノードと、
    少なくとも１つのブランチ・エントリを備える少なくとも１つのブランチ・ノードであって、各ブランチ・エントリは、
    前記ブランチ・ノードの子ノードのアドレスを指定するためのポインタであって、前記子ノードは、リーフ・ノードであるか、又は前記完全性ツリーのさらなるブランチ・ノードである、ポインタと、
    前記子ノードの対応するブランチ・エントリ又はリーフ・エントリの検証のための少なくとも１つの完全性チェック値と
    を備える、少なくとも１つのブランチ・ノードと
    を含む、方法。
24. 請求項２３に記載の方法を実行するようにデータ処理装置を制御するための
    コンピュータ・プログラム。
25. 命令の実行のための命令実行環境を与えるようにホスト・データ処理装置を制御するためのコンピュータ・プログラムであって、
    前記命令実行環境のシミュレートされたアドレス空間へのアクセスを制御するためのメモリ・アクセス・プログラム論理と、
    複数のノードを備える完全性ツリーを使用して前記シミュレートされたアドレス空間内のアドレスに記憶されたデータの完全性を検証するためのメモリ完全性チェック・プログラム論理とを備え、前記複数のノードは、
    メモリ中に記憶されたデータの対応するアドレス・ブロックの検証のための少なくとも１つの完全性タグを備える少なくとも１つのリーフ・エントリを備える少なくとも１つのリーフ・ノードと、
    少なくとも１つのブランチ・エントリを備える少なくとも１つのブランチ・ノードであって、
    前記ブランチ・ノードの子ノードのアドレスを指定するためのポインタであって、前記子ノードは、リーフ・ノードであるか、又は前記完全性ツリーのさらなるブランチ・ノードである、ポインタと、
    前記子ノードの対応するブランチ・エントリ又はリーフ・エントリの検証のための少なくとも１つの完全性チェック値と
    を備える少なくとも１つのブランチ・ノードと
    を含む、コンピュータ・プログラム。

Images