(57)【特許請求の範囲】
【請求項１】
物理記憶容量及び前記物理記憶容量より小さい論理記憶容量を有するフラッシュベース固体データ記憶装置に格納されたデータを消去するデータ消去装置であって、
予め決定された基準を満たす非圧縮性データのシーケンスを取得するように構成したデータ提供部であって、前記予め決定された基準は、前記予め決定された基準を満たす非圧縮性データのシーケンスの圧縮性又は非圧縮性を表す統計的尺度を備え、前記非圧縮性データのシーケンスは、前記非圧縮性データの一つ以上のブロックに分割され、前記非圧縮性データの一つ以上のブロックのサイズの和は、前記フラッシュベース固体データ記憶装置の前記論理記憶容量以上であるデータ提供部と、
前記フラッシュベース固体データ記憶装置に対して、前記フラッシュベース固体データ記憶装置に現在格納されているデータを上書きするために記憶用の非圧縮性データの一つ以上のブロックを提供するように構成したデータ書込み部と、
を備えるデータ消去装置。
【請求項２】
前記統計的尺度は、予め決定されたしきい値を超えるデータの圧縮性を表す予め決定された統計的検定を用いながら前記非圧縮性データのシーケンスに基づいて取得したＰ値を備える請求項１に記載のデータ消去装置。
【請求項３】
前記統計的検定は、重なりのあるテンプレート適合検定、離散フーリエ変換（スペクトル）検定又はＭａｕｒｅｒのユニバーサル統計検定を備える請求項２に記載のデータ消去装置。
【請求項４】
前記非圧縮性データのシーケンスを取得することは、前記予め決定された基準を満たす疑似乱数データのシーケンスを生成するように構成した乱数発生器を用いることを備える請求項１に記載のデータ消去装置。
【請求項５】
前記乱数発生器を用いることは、ＫＩＳＳ乱数発生器、Ｘｏｒｓｈｉｆｔ乱数発生器及びメルセンヌ・ツイスタ乱数発生器の一つに対する繰り返しの呼出しを備える請求項４に記載のデータ消去装置。
【請求項６】
前記非圧縮性データのシーケンスを取得することは、予め決定された規則に従って圧縮データのシーケンスを生成するために原始データを圧縮するデータ圧縮器を用いることを備える請求項１に記載のデータ消去装置。
【請求項７】
前記原始データは、乱数発生器を用いることによって取得される請求項６に記載のデータ消去装置。
【請求項８】
前記データ圧縮器は、デフレートデータ圧縮器又はＢＺｉｐ２データ圧縮器を備える請求項６に記載のデータ消去装置。
【請求項９】
前記データ提供部は、前記非圧縮性データの一つ以上のブロックの一つ以上の追加のセットを取得するように更に構成され、前記追加のセットのそれぞれの前記非圧縮性データの一つ以上のブロックのサイズの和は、前記フラッシュベース固体データ記憶装置の記憶容量以上であり、
前記データ書込み部は、前記フラッシュベース固体データ記憶装置に対して、前記フラッシュベース固体データ記憶装置に現在格納されているデータを上書きするために記憶用の非圧縮性データの一つ以上のブロックの一つ以上の追加のセットを一度に１セットずつ提供するように更に構成した請求項１に記載のデータ消去装置。
【請求項１０】
前記データ書込み部は、前記フラッシュベース固体データ記憶装置への記憶のために最近設けた前記非圧縮性データの一つ以上のブロックのそれぞれの部分が前記フラッシュベース固体データ記憶装置に格納されていることを確認するために、前記フラッシュベース固体データ記憶装置に格納されたデータの一つ以上の選択した部分と、前記フラッシュベース固体データ記憶装置への記憶のために最近設けた前記非圧縮性データの一つ以上のブロックのそれぞれの部分とを比較するように更に構成された請求項１に記載のデータ消去装置。
【請求項１１】
前記データ書込み部は、前記フラッシュベース固体データ記憶装置への記憶のための前記非圧縮性データの一つ以上のブロックの提供後、前記フラッシュベース固体データ記憶装置の全てのユーザアドレス指定可能記憶位置の初期化を行うために配置されたファームウェアレベルサニタイズコマンドを前記フラッシュベース固体データ記憶装置に対して供給するように構成された請求項１に記載のデータ消去装置。
【請求項１２】
前記データ書込み部は、前記ファームウェアレベルサニタイズコマンドの供給後、前記フラッシュベース固体データ記憶装置への記憶のために最近設けた前記非圧縮性データの一つ以上のブロックのそれぞれの部分がもはや前記フラッシュベース固体データ記憶装置に格納されていないことを確認するために、前記フラッシュベース固体データ記憶装置に格納されたデータの一つ以上の選択した部分と、前記フラッシュベース固体データ記憶装置への記憶のために最近設けた前記非圧縮性データの一つ以上のブロックのそれぞれの部分とを比較し、これによって、前記ファームウェアレベルサニタイズコマンドの成功した供給の表示を提供するように構成された請求項１１に記載のデータ消去装置。
【請求項１３】
データ記憶装置に格納されたデータを消去するシステムであって、
請求項１に記載のデータ消去装置と、
圧縮性データの対応する一つ以上のブロックを提供するために非圧縮性データの一つ以上のブロックに対する圧縮を行い、データの一つ以上の圧縮されたブロックの各々に対して、前記圧縮性データのブロックのサイズは、前記非圧縮性データの対応するブロックのサイズ以上であり、かつ、前記圧縮性データの一つ以上のブロックを物理メモリに格納するように構成したデータ記憶装置と、
を備えるシステム。
【請求項１４】
物理記憶容量及び前記物理記憶容量より小さい論理記憶容量を有するフラッシュベース固体データ記憶装置に格納されたデータを消去する方法であって、
予め決定された基準を満たす非圧縮性データのシーケンスを取得することであって、前記予め決定された基準は、前記予め決定された基準を満たす非圧縮性データのシーケンスの圧縮性又は非圧縮性を表す統計的尺度を備え、前記非圧縮性データのシーケンスは、前記非圧縮性データの一つ以上のブロックに分割され、前記非圧縮性データの一つ以上のブロックのサイズの和は、前記フラッシュベース固体データ記憶装置の前記論理記憶容量以上であることと、
前記フラッシュベース固体データ記憶装置に対して、前記フラッシュベース固体データ記憶装置に現在格納されているデータを上書きするために記憶用の非圧縮性データの一つ以上のブロックを提供することと、
を備える方法。
【請求項１５】
前記統計的尺度は、予め決定されたしきい値を超えるデータの圧縮性を表す予め決定された統計的検定を用いながら前記非圧縮性データのシーケンスに基づいて取得したＰ値を備える請求項１４に記載の方法。
【請求項１６】
前記統計的検定は、重なりのあるテンプレート適合検定、離散フーリエ変換（スペクトル）検定又はＭａｕｒｅｒのユニバーサル統計検定を備える請求項１５に記載の方法。
【請求項１７】
前記非圧縮性データのシーケンスを取得することは、前記予め決定された基準を満たす疑似乱数データのシーケンスを生成するように構成した乱数発生器を用いることを備える請求項１４に記載の方法。
【請求項１８】
前記乱数発生器を用いることは、ＫＩＳＳ乱数発生器、Ｘｏｒｓｈｉｆｔ乱数発生器及びメルセンヌ・ツイスタ乱数発生器の一つに対する繰り返しの呼出しを備える請求項１７に記載の方法。
【請求項１９】
前記非圧縮性データのシーケンスを取得することは、予め決定された規則に従って圧縮データのシーケンスを生成するために原始データを圧縮するデータ圧縮器を用いることを備える請求項１４に記載の方法。
【請求項２０】
前記原始データは、乱数発生器を用いることによって取得される請求項１９に記載の方法。
【請求項２１】
前記データ圧縮器は、デフレートデータ圧縮器又はＢＺｉｐ２データ圧縮器を備える請求項１９に記載の方法。
【請求項２２】
前記非圧縮性データの一つ以上のブロックの一つ以上の追加のセットを取得することであって、前記追加のセットのそれぞれの前記非圧縮性データの一つ以上のブロックのサイズの和は、前記フラッシュベース固体データ記憶装置の記憶容量以上であることと、
前記フラッシュベース固体データ記憶装置に対して、前記フラッシュベース固体データ記憶装置に現在格納されているデータを上書きするために記憶用の非圧縮性データの一つ以上のブロックの一つ以上の追加のセットを一度に１セットずつ提供することと、
を更に備える請求項１４に記載の方法。
【請求項２３】
前記フラッシュベース固体データ記憶装置への記憶のために最近設けた前記非圧縮性データの一つ以上のブロックのそれぞれの部分が前記フラッシュベース固体データ記憶装置に格納されていることを確認するために、前記フラッシュベース固体データ記憶装置に格納されたデータの一つ以上の選択した部分と、前記フラッシュベース固体データ記憶装置への記憶のために最近設けた前記非圧縮性データの一つ以上のブロックのそれぞれの部分とを比較することを更に備える請求項１４に記載の方法。
【請求項２４】
前記フラッシュベース固体データ記憶装置への記憶のために前記非圧縮性データの一つ以上のブロックを設けた後に、前記フラッシュベース固体データ記憶装置の全てのユーザアドレス指定可能記憶位置の初期化を行うために配置されたファームウェアレベルサニタイズコマンドを前記フラッシュベース固体データ記憶装置に対して供給することを更に備える請求項１４に記載の方法。
【請求項２５】
前記ファームウェアレベルサニタイズコマンドの発行後、前記フラッシュベース固体データ記憶装置への記憶のために最近設けた前記非圧縮性データの一つ以上のブロックのそれぞれの部分がもはや前記フラッシュベース固体データ記憶装置に格納されていないことを確認するために、前記フラッシュベース固体データ記憶装置に格納されたデータの一つ以上の選択した部分と、前記フラッシュベース固体データ記憶装置への記憶のために最近設けた前記非圧縮性データの一つ以上のブロックのそれぞれの部分とを比較し、これによって、前記ファームウェアレベルサニタイズコマンドの成功した供給の表示を提供することを更に備える請求項２４に記載の方法。
【請求項２６】
前記フラッシュベース固体データ記憶装置において、圧縮性データの対応する一つ以上のブロックを提供するために非圧縮性データの一つ以上のブロックに対する圧縮を行うことであって、データの一つ以上の圧縮ブロックの各々に対して、前記圧縮性データのブロックのサイズは、前記非圧縮性データの対応するブロックのサイズ以下であることと、
前記圧縮性データの一つ以上のブロックを前記フラッシュベース固体データ記憶装置の物理メモリに格納することと、
を更に備える請求項１４に記載の方法。
【請求項２７】
格納されるプログラムコードを有する少なくとも一つのコンピュータ読取可能非一時的記憶媒体を備え、プログラムは、装置によって実行するときに、物理記憶容量及び前記物理記憶容量より小さい論理記憶容量を有するフラッシュベース固体データ記憶装置に格納されたデータを消去する方法であって、予め決定された基準を満たす非圧縮性データのシーケンスを取得することであって、前記予め決定された基準は、前記予め決定された基準を満たす非圧縮性データのシーケンスの圧縮性又は非圧縮性を表す統計的尺度を備え、前記非圧縮性データのシーケンスは、前記非圧縮性データの一つ以上のブロックに分割され、前記非圧縮性データの一つ以上のブロックのサイズの和は、前記フラッシュベース固体データ記憶装置の記憶容量以上であることと、前記フラッシュベース固体データ記憶装置に対して、前記フラッシュベース固体データ記憶装置に現在格納されているデータを上書きするために記憶用の非圧縮性データの一つ以上のブロックを提供することと、を備える方法を少なくとも装置に実行させるコンピュータプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、記憶装置に格納されたデータを消去する装置、システム、方法及びコンピュータプログラムに関する。特に、本発明の例示する実施の形態は、ＳＳＤ記憶装置に格納されたデータを信頼できる方法で消去する方法、装置、システム及びコンピュータプログラムに関する。
【背景技術】
【０００２】
高いレベルのセキュリティを要求するエリア、すなわち、政府機関又は軍事機関は、特定のレベルの脅威エージェントによって検索できないように記憶装置からデータを安全に消去する手法を要求する。民間事業及び他のユーザは、不揮発性メモリからのデータの不十分な除去により機密情報が別の人によってアクセス可能にならないことを確認する意欲を保持することもあり得る。さらに、プライバシー及びデータ保護法案の継続的な採用は、個人情報又は機密情報の安全な方法での消去にますます移行することを意味する。
【０００３】
磁気ハードディスク又はＵＳＢペンドライブのような記憶装置からのデータ復元を安全に防止するための一般的な方法は、予め決定された上書きパターンを用いてディスクのアドレス指定可能な部分の全てに少なくとも一回上書きすることである。そのようなデータの上書きに対する多くの規格が存在し、これらの規格は、国家機関及び／又は軍事機関の異なるセキュリティ要求及び情報に要求されるセキュリティの知覚レベルの解釈、例えば、「極秘」又は「機密」に基づく。大抵の場合におけるデータの上書きによって、消去プロセス後の記憶装置の継続的な使用が可能になり、これは、継続的な使用による利点としてディスクを物理的に破壊することより更に価値がある。
【０００４】
ストレージ技術におけるここ数年を超える開発は、ソリッドステートドライブ（ＳＳＤ）を大量市場に提供した。磁気ハードディスクとは異なり、ＳＳＤは、典型的には、可動部に依存しないＮＡＮＤフラッシュベース半導体装置である。ＳＳＤが非常に長い期間存在していないので、セキュリティ態様の開発及び装置を制御するために要求される統一基準の遷移期間は今も続いている。一例として、“Ｒｅｌｉａｂｌｙ  Ｅｒａｓｉｎｇ  Ｄａｔａ  Ｆｒｏｍ  Ｆｌａｓｈ−ｂａｓｅｄ  Ｓｏｌｉｄ  Ｓｔａｔｅ  Ｄｒｉｖｅｓ”の表題のＷｅｉ等からの最近の研究において出版された実験によって得られるデータは、全てのＳＳＤ製造者がＳＳＤの関連のあるコマンドセット（すなわち、ＳＣＳＩ又はＡＴＡ）の完全な実現に成功していないと結論を出し、これによって、（一つ以上の）データ消去コマンドの一貫性のない成功によってデータのセキュリティの脆弱性が生じうる。
【発明の概要】
【発明が解決しようとする課題】
【０００５】
本発明の目的は、ＳＳＤのようなデータ記憶装置に記憶されたコンテンツを効果的かつ確実に消去する手法を提供することである。
【課題を解決するための手段】
【０００６】
本発明の第１の態様によれば、データ記憶装置に格納されたデータを消去するデータ消去装置を提供し、データ消去装置は、予め決定された基準を満たす非圧縮性データのシーケンスを取得するように構成したデータ提供部であって、非圧縮性データのシーケンスは、非圧縮性データの一つ以上のブロックに分割され、非圧縮性データの一つ以上のブロックのサイズの和は、データ記憶装置の記憶容量以上であるデータ提供部と、データ記憶装置に対して、データ記憶装置に現在格納されているデータを上書きするために記憶用の非圧縮性データの一つ以上のブロックを提供するように構成したデータ書込み部と、を備える。
【０００７】
本発明の第２の態様によれば、データ記憶装置に格納されたデータを消去するデータ消去装置を提供し、データ消去装置は、少なくとも一つのプロセッサと、一つ以上のプログラムのコンピュータプログラムコードを有する少なくとも一つのメモリを備え、少なくとも一つのメモリ及びコンピュータプログラムコードは、少なくとも一つのプロセッサによって、少なくとも予め決定された基準を満たす非圧縮性データのシーケンスを装置に取得させ、非圧縮性データのシーケンスは、非圧縮性データの一つ以上のブロックに分割され、非圧縮性データの一つ以上のブロックのサイズの和は、データ記憶装置の記憶容量以上であり、データ記憶装置に対して、データ記憶装置に現在格納されているデータを上書きするために記憶用の非圧縮性データの一つ以上のブロックを提供するように構成される。
【０００８】
本発明の第３の態様によれば、データ記憶装置に格納されたデータを消去するシステムを提供し、システムは、本発明の第１の態様又は第２の態様のデータ消去装置と、圧縮データの対応する一つ以上のブロックを提供するために非圧縮性データの一つ以上のブロックに対する圧縮を行い、データの一つ以上の圧縮ブロックの各々に対して、圧縮データのブロックのサイズは、非圧縮性データの対応するブロックのサイズ以上であり、かつ、物理メモリの圧縮データの一つ以上を格納するように構成したデータ記憶装置と、を備える。
【０００９】
本発明の第４の態様によれば、データ記憶装置に格納されたデータを消去する方法を提供し、方法は、予め決定された基準を満たす非圧縮性データのシーケンスを取得することであって、非圧縮性データのシーケンスは、非圧縮性データの一つ以上のブロックに分割され、非圧縮性データの一つ以上のブロックのサイズの和は、データ記憶装置の記憶容量以上であることと、データ記憶装置に対して、データ記憶装置に現在格納されているデータを上書きするために記憶用の非圧縮性データの一つ以上のブロックを提供することと、を備える。
【００１０】
本発明の第５の態様によれば、コンピュータプログラムを提供し、コンピュータプログラムは、一つ以上のプロセッサによって実行するときに本発明の第４の態様による方法を少なくとも装置に実行させる一つ以上の命令の一つ以上のシーケンスを含む。
【００１１】
コンピュータプログラムを、例えば、格納されるプログラムコードを有する少なくとも一つのコンピュータ読取可能非一時的記憶媒体を備え、プログラムは、装置によって実行するときに本発明の第４の態様による方法を少なくとも装置に実行させるコンピュータプログラム製品のような揮発性又は不揮発性コンピュータ読取可能記録媒体で実施することができる。
【００１２】
本発明の全態様に亘って、予め決定された基準を満たす非圧縮性データのシーケンスは、予め決定された基準を満たす非圧縮性データのシーケンスの圧縮性又は非圧縮性を表す統計的尺度を備えることができる。
【００１３】
本明細書で提示される発明の例示的な実施の形態は、添付した特許請求の範囲の適用性に制限を課すものと解釈すべきでない。動詞「備える」及びその派生語を、本明細書では、言及しない特徴の存在を除外しない取り除かれた制限として用いる。後に説明する特徴は、特に明記しない限り互いに自由に結合できる。
【００１４】
発明の特徴として考えられる新規の形態を、特に、添付した特許請求の範囲で説明する。しかしながら、構成及び動作の方法の両方に関する発明それ自体は、発明の追加の目的及び利点とともに、添付図面に関連して読むときの特定の実施の形態の以下の詳細な説明から最もよく理解される。
【図面の簡単な説明】
【００１５】
【図１】図１は、本発明の実施の形態による配置を図式化して示す。
【図２】図２は、データ記憶装置を図式化して示す。
【図３】図３は、本発明の実施の形態によるデータ消去装置を備える配置を図式化して示す。
【図４】図４は、本発明の実施の形態による方法を示す。
【図５】図５は、本発明の実施の形態による装置を図式化して示す。
【発明を実施するための形態】
【００１６】
図１は、データ記憶装置１２０に接続したデータ消去装置１１０を備える例示的な配置１００を図式化して示す。データ消去装置１１０は、情報、例えば、書込みデータをデータ記憶装置１２０に提供するように構成され、データ消去装置１１０を、情報、例えば、読出しデータをデータ記憶装置１２０から受信することができる。データ消去装置１１０を、データ記憶装置１２０とそれに接続したエンティティ(entity)、例えば、データ消去装置１１０との間の通信及び／又は（一つ以上の）データ転送プロトコルを規定するホストインタフェース１３０を介してデータ記憶装置に接続することができる。
【００１７】
ホストインタフェース１３０は、従来知られている各規格に従う、例えば、シリアルＡＴＡ（ＳＡＴＡ）、パラレルＡＴＡ（ＰＡＴＡ）、スモールコンピュータシステムインタフェース（ＳＣＳＩ）、シリアルアタッチドＳＣＳＩ（ＳＡＳ）、ユニバーサルシリアルバス（ＵＳＢ）、ペリフェラルコンポーネントインターコネクトエクスプレス（ＰＣＩ  Ｅｘｐｒｅｓｓ又はＰＣＩｅ）若しくは不揮発性メモリエクスプレス（ＮＶＭ  ｅｘｐｒｅｓｓ又はＮＶＭｅ）に従うインタフェース又はデータ記憶装置１２０と他のエンティティとの間の通信及びデータ転送に適切な任意の対応するインタフェースを備えることができる。
【００１８】
図２は、データ記憶装置１２０の一例としてのソリッドステートドライブ（ＳＳＤ）装置２００を図式化して示す。ＳＳＤ装置２００は、記憶部２１０及び制御部２２０を備える。
【００１９】
記憶部２１０は、物理記憶容量を提供する一つ以上の記憶素子２１２−１，２１２−２，２１２−３，．．．，２１２−ｎ、例えば、一つ以上のＮＡＮＤフラッシュチップ又はデータの不揮発性記憶を行う他のタイプの一つ以上のメモリチップを備える。各メモリチップによって、予め決定されたデータ量を記憶することができ、データ量の和は、ＳＳＤ装置２００の全体に亘る物理記憶容量を規定する。
【００２０】
制御部２２０は、記憶部２１０へのデータの書込み及び記憶部２１０からのデータの読出しを制御するように構成される。制御部２２０は、典型的には、データ圧縮器２２２と、ウェアレベリング部２２４とを備える。しかしながら、ＳＳＤ装置２００を、データ圧縮器２２２を有することなく設けることもできる。
【００２１】
データ圧縮器２２２を、存在する場合には、ＳＳＤ装置２００に書き込むデータを圧縮するとともにＳＳＤ装置２００から読み出すデータを解凍するように構成することができる。特に、データ圧縮器２２２を、ＳＳＤ装置２００に書き込まれるデータを予め決定された圧縮手法に従って無損失圧縮を行うとともにＳＳＤ装置２００から読み出したデータに対して対応する解凍を行うように構成することができる。そのような圧縮手法は、典型的には、ＳＳＤ装置２００に書き込まれたデータのブロックの固有の冗長性を利用し、したがって、圧縮性能は、典型的には、ＳＳＤ装置２００に書き込まれるデータの特性に依存する。複数の適切な圧縮手法及び対応する解凍手法は、従来知られている。ＳＳＤ装置２００に書き込まれるデータの圧縮は、一つ以上の記憶素子２１２−１，２１２−２，２１２−３，．．．，２１２−ｎによって提供される物理メモリに実際に書き込まれるデータ量を減少させるのに役立つ。
【００２２】
ウェアレベリング部２２４は、予め決定された規則のセットに従って、データの圧縮されたブロックのユニット、例えば、バイト又はワードを一つ以上の記憶素子２１２−１，２１２−２，２１２−３，．．．，２１２−ｎに亘って分配するように構成される。したがって、ウェアレベリング部２２４は、予め決定された規則のセットに従って、データの圧縮されたブロックのユニットを格納するための物理メモリアドレスを決定するように構成される。そのような予め決定された規則のセットは、典型的には記憶部２１０の一つ以上の記憶素子２１２−１，２１２−２，２１２−３，．．．，２１２−ｎを均一に用いることを目的として物理メモリアドレスの使用を時間とともに動的に管理するために用いられる。特に、予め決定された規則のセットは、記憶部２１０の全ての記憶素子に対する書込み数を考慮して記憶部２１０の任意の記憶素子への累積的な書込み数を最小にしようと試みる。一例として、Ｍ個の記憶素子の使用を要求する圧縮されたデータのＮ個のユニットに対する書込みを行うために、ウェアレベリング部２２８を、これまで書込みを行った記憶素子を昇順に順序を付けるとともに圧縮されたデータのＮ個のユニットを記憶するために昇順リストの最初のＭ個の記憶素子を選択するように概念的に構成することができる。書込み数が増大するに従って所定のタイプの記憶素子、例えば、ＮＡＮＤフラッシュチップの信頼性が低下するので、記憶素子のそのような均一の使用は、ＳＳＤ装置２００の寿命を延ばすのに役に立つ。
【００２３】
データ圧縮器２２２及びウェアレベリング部２２４によって設けられた機能は、ＳＳＤ装置２００に対するインタフェースの論理メモリアドレスから記憶部２１０の対応する物理メモリアドレスへの変換とみなすことができる。その結果、データ圧縮器２２２及びウェアレベリング部２２４を、論理メモリアドレスと対応する物理メモリアドレスとの間のマッピングを行う単一のエンティティを提供するものとみなすことができる。そのようなエンティティを、データ変換部、（フラッシュ）変換層等のような変換部と称することができる。
【００２４】
変換部は、マッピングテーブル２２６、又は、例えば、占有された論理メモリアドレスの各々及び対応する物理メモリアドレスを記録することによって論理メモリアドレスと対応する物理メモリアドレスとの間のマッピングを行う他の適切なデータ構造を利用することができる。マッピングテーブル２２６は、記憶部２１０の効率的な使用を容易にするために占有された及び／又は占有されていない論理メモリアドレス及び／又は物理メモリアドレスの表示を更に提供することができる。マッピングテーブル２２６を、制御部２２０に備えられたメモリ及び／又は変換部によってアクセス可能なＳＳＤ装置２２０内の他の場所のメモリに設けることができる。特に、一つ以上の記憶素子２１２−１，２１２−２，２１２−３，．．．，２１２−ｎの一つ以上を、マッピングテーブル（又は対応するデータ構造）の不揮発性記憶を行うために用いることができる。特に、マッピングテーブル２２６を、ＳＳＤ装置２００が動作中でないとき、例えば、オンに切り替えられていないとき又は動作電力が供給されないときに記憶部に格納することができ、それに対し、マッピングテーブル２２６を、ＳＳＤ装置２００が動作中であるときに効率的にアクセスすることができるようにするために制御部２２０に設けられたメモリに格納することができる。
【００２５】
変換部は、データ圧縮器２２２及びウェアレベリング部２２４の動作を制御するとともにＳＳＤ装置２００を用いるエンティティに対するインタフェース、例えば、コマンド及びＳＳＤ装置２００に書き込むための又はＳＳＤ装置２００から読み出すためのデータを受信するホストインタフェース１３０を設けるためのコントローラ２２８を更に備える。特に、データのブロックをＳＳＤ装置２００の論理メモリアドレスに書き込むための命令又はコマンドに応答して、コントローラ２２８を、圧縮器２２２によってデータのブロックを記憶部２１０に書き込むデータのブロックの圧縮されたブロックに圧縮させ、ウェアレベリング部２２４によって記憶素子すなわちデータの圧縮されたブロックを記憶するのに用いる（一つ以上の）物理メモリアドレスを決定させ、決定した（一つ以上の）物理メモリアドレスに対してデータの圧縮されたブロックを書き込み、かつ、それに従ってマッピングテーブル２２６を更新するように構成することができる。
【００２６】
同様に、ＳＳＤ装置２００の論理メモリアドレスからデータのブロックを読み出す命令又はコマンドに応答して、コントローラ２２８を、論理メモリアドレスに対応する（一つ以上の）物理メモリアドレスを決定するためにマッピングテーブル２２６にアクセスし、決定した（一つ以上の）物理メモリアドレスからデータの圧縮されたブロックを読み出し、データ圧縮器２２２によってデータの圧縮されたブロックをデータの解凍されたブロックに解凍させ、かつ、データの解凍したブロックを提供するように構成することができる。
【００２７】
制御部２２０は、マッピングテーブル、圧縮された又は圧縮すべきデータ、解凍された又は解凍すべきデータ等の一時記憶のためにコントローラによってアクセス可能な他の素子又は部分、例えば、データバッファを備えることができる。データバッファは、例えば、一つ以上のＤＲＡＭユニット又は他のタイプの揮発性若しくは不揮発性記憶装置を備えることができる。制御部は、例えば、記憶されたデータのインテグリティを確保するための誤り訂正部を更に備えることができる。誤り訂正部を、例えば、リードソロモン符号、（一つ以上の）ゴーレイ符号、（一つ以上の）ハミング符号に基づいて誤り訂正コーディングを行うように構成することができる。
【００２８】
データ圧縮器２２２、ウェアレベリング部２２４及びコントローラ２２８を、一つ以上の物理装置の論理的又は機能的な部分／モジュールとして設けることができる。特に、制御部２２０は、プロセッサ及びメモリを備えることができ、データ圧縮器２２２、ウェアレベリング部２２４及びコントローラ２２８を、メモリに格納されたソフトウェアとして、例えば、プロセッサによって実行するときにデータ圧縮器２２２、ウェアレベリング部２２４及びコントローラ２２８に割り当てられた動作、手順及び／又は機能をＳＳＤ装置２００によって実行させる一つ以上の命令の一つ以上のシーケンスを備える一つ以上のコンピュータプログラムとして設けることができる。メモリを、マッピングテーブル２２６を格納するとともにデータバッファに対する記憶容量を設けるために更に用いることができる。
【００２９】
圧縮及び／又はウェアレベリングのために、ＳＳＤ装置２００の物理記憶容量は、論理記憶容量と異なることがある。特に、圧縮は、少なくとも理論的には、物理記憶容量が論理記憶容量より小さくなるようにすることができる。それに対し、ウェアレベリング機能は、少なくとも理論的には、論理記憶容量より大きい物理記憶容量を利用することができ、これを、（記憶容量の）オーバープロビジョニングと称することができる。論理記憶容量を、ＳＳＤ装置２００を用いるエンティティによって見ることができるようなＳＳＤ装置２００の記憶容量とみなすことができる。論理記憶容量は、論理メモリアドレスが参照するアドレス指定可能な記憶容量も提供する。以下、特に明記しない限り、ＳＳＤ装置２００又は一般的なデータ記憶装置の記憶容量への言及は、論理記憶容量を言及する。
【００３０】
用語ＳＳＤ又はＳＳＤ装置を、固体記憶装置の一部の形態を利用する装置のアレイをカバーする包括的な用語として用いることができるが、本書では、用語ＳＳＤ又はＳＳＤ装置を、上述したように記憶部２１０及び制御部２２０を備える大容量記憶装置２００を言及するために用いる。
【００３１】
それに対し、ＳＳＤ装置２００を、データ消去装置１１０を用いることができるデータ記憶装置１２０の一例として用いるが、データ消去装置１１０を他のタイプのデータ記憶装置とともに同様に用いることができる。特に、データ消去装置１１０は、ＳＳＤ装置２００又は上述したように圧縮及び／又はウェアレベリングを行う他の記憶装置に格納されたデータの消去において特に有利であるが、データ消去装置１１０を、任意のデータ記憶装置に格納されたデータを消去するために同様に用いることができる。
【００３２】
以下、データ消去装置１１０を、論理エンティティとして説明する。実際には、データ消去装置１１０を複数の異なる方法で実現することができる。データ消去装置１１０を、データ消去装置１１０に対する後に説明する動作、手順及び／又は機能を実行するように構成したスタンドアローン装置又は複数の装置として設けることができる。他の例として、データ消去装置１１０を、他の装置によってホストされる一つの装置又は複数の装置として設けることができる。更に別の例として、データ消去装置１１０を、ソフトウェア手段、例えば、プロセッサによって実行するときにデータ消去装置１１０に対する後に説明する動作、手順及び／又は機能を装置によって実行させるコンピュータ読出し可能命令を備える一つ以上のコンピュータプログラムとして設けることができる。
【００３３】
図３は、ホストインタフェース１３０を介してデータ記憶装置１２０に接続したデータ消去装置１１０を図式化して示す。データ消去装置１１０は、データ提供部１１２及びデータ書込み部１１４を備える。データ記憶装置１２０は、後に説明するように圧縮及び／又はウェアレベリングを行うＳＳＤ装置２００又は他のタイプのデータ記憶装置を備えることができる。
【００３４】
データ提供部１１２は、予め決定された基準を満たす非圧縮性データのシーケンスを取得するように構成され、非圧縮性データのシーケンスは、非圧縮性データの一つ以上のブロックに分割され、非圧縮性データの一つ以上のブロックのサイズの和は、データ記憶装置の記憶容量以上である。予め決定された基準を、好適には、非圧縮性データのシーケンスの非圧縮性の程度、したがって、非圧縮性データの一つ以上のブロックの非圧縮性の程度に関連させ、予め決定された基準は、非圧縮性の一つ以上のブロックの非圧縮性の表示として用いることができる単一の基準又は一つ以上の個別の基準を備えることができる。非圧縮性データの一つ以上のブロックの絶対的な非圧縮性を意味するように、予め決定された基準を決定することができる。代わりに、予め決定された基準を満たす程度の非圧縮性を示しながらある程度の圧縮性を理論的に及び／又は実際に可能になるようにすることができ、典型的には、結果的にデータの各ブロックの非圧縮性が実用的なものとなるように、予め決定された基準を決定することができる。その結果、本書で用いられる用語非圧縮性データは、絶対的な非圧縮性データ又は非圧縮性のレベルに対する予め決定された基準を満たす程度まで非圧縮性であるデータを言及することができる。
【００３５】
非圧縮性データのシーケンスを、非圧縮データの一つ以上のブロックとしてデータ提供部１１２に提供することができ、又は、代わりに、データ供給部１１２を、非圧縮性データを、例えば、データの連続的なストリームとして又は複数のデータセクションとして取得するとともに非圧縮性データのストリーム又はデータセクションを非圧縮性データの一つ以上のブロックに配置するように構成することができる。
【００３６】
データ書込み部１１４は、データ記憶装置に現在格納されているデータを上書きするために記憶用のデータ記憶装置１２０に非圧縮性データの一つ以上のブロックを提供するように構成される。その結果、データ記憶装置１２０に現在格納されているデータは、一つ以上の非圧縮性データブロックに置き換えられ、したがって、データ記憶装置１２０から消去される。
【００３７】
一般的には、データ消去装置は、データ記憶装置１２０の全てのアドレス指定可能な記憶場所を上書きするために非圧縮データの一つ以上のブロックを提供するように構成される。一般的なケースでは、それは、記憶された全てのデータを消去するためにデータ記憶装置１２０の記憶容量以上の結合されたサイズを有する任意のデータの一つ以上のデータブロックを書き込むのに十分となり得るが、これは、例えば、記憶させるためのデータの圧縮及び／又はウェアレベリングを行うことができるＳＳＤ装置２００又は任意のデータ記憶装置の場合には、データ記憶措置１２０の物理メモリに実際に書き込まれるデータの量を減少させるかもしれない圧縮機能及び／又は所定の論理メモリアドレスに書き込まれるデータをデータ記憶装置の外部にある目に見えない物理メモリアドレスに書き込むかもしれないウェアレベリング機能のために十分でないことがある。
【００３８】
その結果、予め決定された基準を満たす非圧縮性データの一つ以上のブロックの書込みの利点は、圧縮機能、例えば、データ圧縮器２２２がデータ記憶装置１２０の物理メモリに実際に書き込まれるデータの量を減少させることを確実にすることである。それに対し、データ記憶装置１２０の記憶容量以上の結合されたサイズを有する非圧縮性データの一つ以上のブロックの利点は、ウェアレベリング機能、例えば、ウェアレベリング部２２４が典型的にはデータ記憶装置１２０の外部で知られないように論理メモリアドレスと対応する物理メモリアドレスとの間のマッピングを行うにもかかわらずデータ記憶装置１２０の全ての物理記憶場所が上書きされることを確実にすることである。その結果、データ記憶装置１２０の記憶容量以上の結合されたサイズを有する非圧縮性データの一つ以上のブロックを取得すること及びデータ記憶装置１２０に格納される一つ以上のブロックを提供することは、データ記憶装置１２０に格納されるデータの確実な消去に寄与する。
【００３９】
それに対し、データ記憶装置１２０の記憶容量以上の結合されたサイズを有する−任意のデータの代わりの−非圧縮性データの一つ以上のブロックを、圧縮及び／又はウェアレベリングを行わないデータ記憶装置に格納されたデータの上書きのために全く自然に同様に適用することができる。
【００４０】
非圧縮性データの一つ以上のブロックに基づいて用いられるデータのシーケンスを、データシーケンスを生成する乱数発生器（ＲＮＧ）を適用することによってランダム又は疑似ランダムデータとして取得することができる。実際には、真のランダムプロセスを利用することができない、又は、そのようなプロセスの適用は非実用的となり得るので、典型的には、疑似乱数発生器（ＰＲＮＧ）に依存すれば十分である。本書では、用語ＲＮＧ及び用語ＰＲＮＧの両方を、典型的にはソフトウェア手段によって提供され、本質的にはＰＲＮＧである乱数発生器を言及するために用いる。したがって、無損失圧縮手法により実際に非圧縮性にするために、特に、ＳＳＤ装置２００のデータ圧縮器２２２のようなデータ記憶装置１２０に書き込まれるデータを圧縮するように動作する圧縮器によって非圧縮性にするために十分にランダムであるデータを取得するためにＲＮＧ又はＰＲＮＧを用いることができる。ここでは、用語「無損失圧縮」は、データのブロックの圧縮及びそれに続く解凍において情報が損失しないように復元を行うことができる圧縮を言及する。
【００４１】
実際には、データ提供部１１２は、典型的には、データ記憶装置１２０によって行われる圧縮の詳細の知識を何も有しない。その結果、データ提供部１１２は、全く圧縮することができない又は予め規定された程度までしか圧縮することができないデータを生成するためにデータ記憶装置１２０によって適用される圧縮手法の特性を生かすことができないことがある。したがって、ランダムデータのシーケンスを、好適には、無損失圧縮手法を用いたデータの圧縮を実際にはできなくする程度のランダム性を示すのに十分なサイズのブロックに分割する。
【００４２】
乱数又はランダムな文字のシーケンスを備える真のランダムデータは、情報を損失することなく圧縮することができないデータの一例であり、したがって、換言すれば、そのようなデータの無損失圧縮は可能でない。これを、後に説明するようにランダムデータとして高品質の乱数を言及する二つの幾分直接的な公理の分析によって説明することができる。
【００４３】
公理１：高品質の乱数の無損失圧縮が、データの一部の組合せが他の組合せより可能性が高い場合のみ可能となる。
公理２：高品質の乱数の任意のストリングが、その他のストリングと同様に起こり得る。
【００４４】
Ａが集合を意味するものとし、
【数１】
0006313489.tif 000002
を有する＜Ｂｋ＞がＡの全てのあり得るストリングから成るものとし、Ｒが、Ａに属するストリングをランダムに選ぶプロセスを意味するものとし、Ｐｋを、ｋ番目のストリングを選択するＲの可能性とする。さらに、Ｐｉが、ｉ番目のストリングを選択する可能性がＲによって選択した＜Ｂｋ＞の任意のストリングの平均の可能性より高いことを示すと仮定する場合、公理２は適用できず、その結果、Ｒは、＜Ｂｋ＞に属する他のストリングより可能性の高いストリングが存在する場合には高品質のＲＮＧでない。したがって、「高品質の乱数の無損失圧縮が可能でない」という主張は、背理法によって証明される。
【００４５】
さらに、これに関連して、インド国のニューデリーに所在するＰＨＩ  Ｌｅａｒｎｉｎｇ  Ｐｒｉｖａｔｅ  Ｌｉｍｉｔｅｄにより２００８年に刊行されたＫ．Ｒ．Ｃｈｏｗｄｈａｒｄｙによる“Ｆｕｎｄａｍｅｎｔａｌｓ  ｏｆ  Ｄｉｓｃｒｅｔｅ  Ｍａｔｈｅｍａｔｉｃａｌ  Ｓｔｒｕｃｔｕｒｅｓ”の４０頁に記載した鳩の巣原理は、無損失圧縮の概念を更に詳しく説明している。鳩の巣原理は、ｈ個の穴及びこれらの穴の合計ｐ羽の鳩が存在するとともにｈ＜ｐである場合にはある穴には１羽より多い鳩が存在する必要があることを述べる。すなわち、等しくないサイズの二つの有限集合の間のマッピングがある場合、小さいほうの集合の少なくとも一つの要素が大きいほうの集合の一つより多い要素と組になる必要がある。鳩の巣原理を、Ｃｈｏｗｄｈａｒｄｙによって表されるように、鳩の巣原理の結果が誤りであると仮定すると各鳩の巣が最大でも１羽の鳩を含むと仮定できるという矛盾によって証明することができる。したがって、それは、ｈ羽以下の鳩から成る。しかしながら、ｐ羽の鳩が存在し、かつ、ｐ＞ｈであり、これは矛盾している。したがって、鳩の巣原理に基づいて取得した等しくないサイズの二つの有限集合の間のマッピングは正確である。
【００４６】
鳩の巣原理に基づいて、無損失圧縮を行う圧縮器がシャノンのエントロピーの演算アナログ(computational analog)である演算エントロピー(computational entropy)によって極限集合より下のデータを圧縮できないことを知る。これに関連して、例えば、ＳＩＡＭ  Ｊｏｕｒｎａｌ  ｏｎ  Ｃｏｍｐｕｔｉｎｇ，  Ｖｏｌ．２８  Ｉｓｓｕｅ  ４，  Ａｕｇｕｓｔ  １９９９，  ｐａｇｅｓ１３６４−１３９６の
【化１】
0006313489.tif 000003
による”Ａ  ｐｓｅｕｄｏｒａｎｄａｍ  Ｇｅｎｅｒａｔｏｒ  ｆｒｏｍ  ａｎｙ  Ｏｎｅ−Ｗａｙ  Ｆｕｎｃｔｉｏｎ”の５〜６頁において、演算エントロピーｇ（Ｘ）及びＹが演算的に区別できない場合にはｇ（Ｘ）は少なくともＹのシャノンのエントロピーと定義される。ｇ（Ｘ）が疑似乱数発生器である場合、ｇ（Ｘ）の演算エントロピーは、入力Ｘのシャノンのエントロピーより大きく、この意味では、ｇ（）はエントロピーを増大する。
【００４７】
これは、非圧縮性又は略非圧縮性であるランダムデータを無損失圧縮手法によって生成する手法を開発するのに利用できる疑似乱数発生器の有用な特性である。関連した話では、Ｔｈｅ  Ｃｏｍｐｕｔｅｒ  Ｊｏｕｒｎａｌ，Ｖｏｌ．４２，Ｎｏ．４，１９９９，ｐａｇｅ２７０−２８３のＣ．Ｓ．Ｗａｌｌａｃｅ  ａｎｄ  Ｄ．Ｌ．Ｄｏｗｅによる“Ｍｉｎｉｍｕｍ  Ｍｅｓｓａｇｅ  Ｌｅｎｇｔｈ  ａｎｄ  Ｋｏｌｍｏｇｏｒｏｖ  Ｃｏｍｐｌｅｘｉｔｙ”の２７２頁において、ストリングがランダムソース(random source)に由来したという仮説を任意の標準的な統計的検定によって否定させるか否かを問うことによって、有限ストリングのランダム性が、通常、アクセスされ、これによって、データのランダム性、したがって、非圧縮性にアクセスする有用なツールを提供することが知られている。
【００４８】
上述したように、データ提供部１１２を、予め決定された基準を満たすランダムデータのシーケンスをＰＲＮＧを用いることによって取得するように構成することができる。特に、非圧縮性データを取得することは、予め決定された基準を満たすランダムのシーケンス又は疑似ランダムデータ、例えば、乱数を発生する、換言すれば、十分なランダム性の乱数のシーケンスを発生するように構成した乱数発生器を用いることを備えることができる。データ記憶装置１２０の記憶容量以上の結合されたサイズを有する非圧縮性データの一つ以上のブロックに分割するのに十分な長さを有する乱数のシーケンスを提供するために、ＰＲＮＧに対する繰り返しの呼出しを発することができる。その結果、無損失圧縮手法によって圧縮することができないＰＲＮＧによって提供されるランダムデータのシーケンスを、非圧縮性データの一つ以上のブロックの基礎として用いることができる。
【００４９】
適切なＰＲＮＧの一例は、例えば、ＵＣＬ  ｂｉｏｉｎｆｏｒｍａｔｉｃｓ  Ｇｒｏｕｐ，ＵＫ，２０１０のＤ．Ｊｏｎｅｓによる“Ｇｏｏｄ  Ｐｒａｃｔｉｃｅ  ｉｎ  （Ｐｓｅｕｄｏ）  Ｒａｎｄｏｍ  Ｎｕｍｂｅｒ  Ｇｅｎｅｒａｔｉｏｎ  ｆｏｒ  Ｂｉｏｉｎｆｏｒｍａｔｉｃｓ  Ａｐｐｌｉｃａｔｉｏｎｓ”の２頁にも記載されている以下のＡＮＳＩ−Ｃソースコードによって説明され、この場合、このＰＲＮＧを、ＫＩＳＳ  ＰＲＮＧと称する。この例を、後に第１の例示的なＰＲＮＧとも称する。
【化２】
0006313489.tif 000004
【００５０】
上述した第１の例示的なＰＲＮＧは、三つのタイプのＰＲＮＧを組み合わせた複合乱数発生器である。すなわち、第１の例示的なＰＲＮＧは、従来知られているキャリー付き乗算ＰＲＮＧ、ＸｏｒｓｈｉｆｔＰＲＮＧ及び線形合同ＰＲＮＧの組合せを備える。これら三つのＰＲＮＧタイプのそのような組合せは、１０＾４０００００００を超える周期を生成することができる複合ＰＲＮＧを提供する。
【００５１】
研究論文Ｘｏｒｓｈｉｆｔ  ＲＮＧｓ（２００３）において、ジョージ・マーサグリアは、「ランダム性のテストを非常に良好にパスすると思われる．．．非常に高速な乱数発生器の分類の説明」を述べている。発生器は、発生器が２ｋ−１の周期を有し、この場合、ｋ＝３２，６４，９６，１２８，１９２であるという点でスケーラブルである。
【００５２】
これらＲＮＧは、種々の方法でＸｏｒｓｈｉｆｔ動作の一連の組合せを適用することによって動作する。マーサグリアは、ランダム性のテストを行うとともに従来知られている一連のＤｉｅｈａｒｄテストの全てをパスするときにこれらのＲＮＧが良好に機能すると報告している。
【００５３】
Ｃプログラミング言語において、基本的なＸｏｒｓｈｉｆｔ動作は、左シフトのためのｙ＾（ｙ＜＜ａ）及び右シフトのためのｙ＾（ｙ＞＞ａ）によって行われる。ＸｏｒｓｈｉｆｔＲＮＧは、種々のＲＮＧを形成するために種々のシフト及び異なる論証を用いて異なるＸｏｒｓｈｉｆｔを組み合わせることによって開発される。
【００５４】
マーサグリアは、Ｘｏｒｓｈｉｆｔ動作の理論を次のように述べている。
「四つの乱数種ｘ，ｙ，ｚ，ｗが与えられた場合に呼出しごとに三つのＸｏｒｓｈｉｆｔ動作のみによって２１２８−１個のランダムな３２ビットの整数を提供するＣプロシージャの主要部分を以下に示す。
【数２】
0006313489.tif 000005
そのようなプロシージャは、非常に高速であり、典型的には２００００００００／秒を超え、結果的に得られる整数は、適用されたランダム性の全てのテストをパスする。」
【００５５】
後に第２の例示的なＰＲＮＧとも称するマーサグリアによるＸｏｒｓｈｉｆｔＲＮＧの一例は、２192−２32の周期を有し、ＡＮＳＩ  Ｃソースコードとして以下のように示される。
【化３】
0006313489.tif 000006
【００５６】
メルセンヌ・ツイスタ（ＭＴ）は、一様疑似乱数を生成するアルゴリズムである。松本及び西村によれば、学術論文Ｍｅｒｓｅｎｎｅ  Ｔｗｉｓｔｅｒ：Ａ  ６２３−ｄｉｍｅｎｓｉｏｎａｌｌｙ  ｅｑｕｉｄｓｔｒｉｂｕｔｅｄ  ｕｎｉｆｏｒｍ  ｐｓｅｕｄｏｒａｎｄｏｍ  ｎｕｍｂｅｒ  ｇｅｎｅｒａｔｏｒにおいて、メルセンヌ・ツイスタは、２１９９３７−１の非常に長い周期を示す。ＭＴは、従来知られている一連のＤｉｅｈａｒｄテストを含むランダム性の種々のテストをパスすることで知られている。
【００５７】
松本及び西村は、アルゴリズムを次のように説明している。
以下の説明において、ボールド体のｘは、（右に最下位ビットを有する）サイズｗのマシンワードによって識別される有限な二つの要素の２進数フィールドＦ２＝｛０，１｝に亘るｗ次元の行ベクトルであるワードベクトル(word vector)を表す。アルゴリズムは、０と２w−１の間の一様疑似乱数整数とみなされるワードベクトルの配置を形成する。２w−１によって除算することによって、各ワードベクトルは［０，１］の実数とみなされる。以下の線形回帰はアルゴリズムの基礎となる。
【数３】
0006313489.tif 000007
複数の定数、回帰の次数である整数ｎ、（
【数４】
0006313489.tif 000008
の定義に隠れている）整数ｒ、０≦ｒ≦ｗ−１、整数ｍ、１≦ｍ≦ｎ及びＦ２のエントリを有する定数ｗ×ｗ行列Ａを有する。
Ｘ０，Ｘ１，．．．，Ｘｎ−１をイニシャルシード(initial seed)として与える。この場合、発生器は、ｋ＝０を有する上記回帰によってｘｎを発生する。ｋ＝１，２，．．．とすることによって、発生器は、ｘｎ＋１，ｘｎ＋２，．．．を決定する。
回帰の右辺において、
【数５】
0006313489.tif 000009
は、ｘｋの「上位ｗ−ｒビット」を意味し、
【数６】
0006313489.tif 000010
は、ｘｋ＋１の「下位ｒビット」を意味する。したがって、Ｘ＝（ｘｗ−１，ｘｗ−２，．．．，ｘ０）である場合、定義により、Ｘｕは、ｗ−ｒビットベクトル（ｘｗ−１，．．．，ｘｒ）となり、Ｘｌは、ｒビットベクトル（ｘｒ−１，．．．，ｘ０）となる。したがって、
【数７】
0006313489.tif 000011
は、連結(concatenation)、すなわち、Ｘｋの上位ｗ−ｒビット及びＸｋ＋１の下位ｒビットをこの順序で連結することによって得られるワードベクトルとなる。その後、行列Ａは、このベクトルにより右から乗算される。
最後に、Ｘｋ＋ｍにこのベクトル（
【数８】
0006313489.tif 000012
は、ビット単位のモジュロ２加算(bitwise addition modulo two)）を加算し、その後、次のベクトルＸｋ＋ｎを発生する。
【００５８】
以下のＡＮＳＩ−Ｃコードは、
【化４】
0006313489.tif 000013
で提供されるようなＭＴ  ＲＮＧを実現する例を示す。このソースコードは、例えば、グイド・ヴァンロッサムによる“Ｐｙｔｈｏｎ  Ｔｕｔｏｒｉａｌ”の表題の文献の第２版、ＩＳＢＮ９７８−４−８７３１１−４４２−２においても提供され、それに対し、ＭＴ  ＲＮＧに関連する情報を、例えば、
【化５】
0006313489.tif 000014
で見つけることができる。ＭＴ  ＲＮＧを、後に、第３の例示的なＰＲＮＧと称する。
【化６】
0006313489.tif 000015
【化７】
0006313489.tif 000016
【化８】
0006313489.tif 000017
【化９】
0006313489.tif 000018
【００５９】
非圧縮性データの一つ以上のブロックに分割するのに適切な予め決定された基準を満たす非圧縮データのシーケンスの他の例は、事前に圧縮されたデータのシーケンスである。したがって、ＰＲＮＧを用いる代わりに又はＰＲＮＧを用いるのに加えて、非圧縮性データのシーケンスを取得することは、予め決定された基準を満たす非圧縮性データのシーケンスを生成するために原始データを圧縮するデータ圧縮器を用いることを備えることができる。原始データを、基本的には、任意のデータ、例えば、ＰＲＮＧを用いることによって取得したデータとすることができる。原始データを提供するために用いられるＰＲＮＧは、典型的には、厳密な要求を満たすデータのシーケンスを提供する必要はないが、例えば、多数のプログラミング言語の標準ライブラリに設けられた標準的な乱数発生器は、典型的には、この目的には十分である。
【００６０】
データ圧縮器を、非圧縮性データのシーケンスとして使用可能な圧縮データのシーケンスを生成するために一つ以上の予め決定された規則に従って原始データを圧縮するように構成することができる。一つ以上の予め決定された規則は、用いられる圧縮手法を規定する。好適には、圧縮手法は、データ記憶装置１２０によって用いられる圧縮手法と類似し又は部分的に類似することができ、これによって、原始データからあらゆる冗長性が除去され、データ記憶装置１２０によって用いられる圧縮手法は、後の圧縮で利用することができる。しかしながら、データ記憶装置１２０で適用される圧縮手法と異なる圧縮手法を同じように適用することができ、圧縮手法がデータから冗長性を減少又は除去する役割を果たすので、その結果、所定のタイプの任意の適切な圧縮手法によって圧縮されたデータは、典型的には、異なるタイプの圧縮手法によって更に著しく圧縮することができない。
【００６１】
適切なデータ圧縮器の一例は、Ｚｌｉｂであり、例えば、
【化１０】
0006313489.tif 000019
を参照のこと。Ｚｌｉｂは、デフレートアルゴリズムを実現する無損失データ圧縮ライブラリであり、かつ、ポータブルアクロスプラットフォーム(portable across platform)である。デフレートは、ＬＺ７７アルゴリズム及びハフマン符号の組合せに基づく無損失圧縮アルゴリズムである。デフレートアルゴリズムは、ポインタを有する繰り返しストリングを配置及び整合するとともに一般的な記号を短い表現に置換しながら一般的でない記号を長い表現に置換することによって圧縮を実現する。Ｚｌｉｂの開発者は、典型的な圧縮比を２：１と５：１との間で変更することができると主張しているが、速度と圧縮の間にトレードオフが生じることがあり、圧縮されるデータに応じて異なるストラテジが用いられうる。Ｚｌｉｂは、Ｍａｃ  ＯＳ（登録商標）Ｘ及びＬｉｎｕｘ（登録商標）を含む多数のソフトウェアプラットフォームによって用いられる。
【００６２】
適切なデータ圧縮器の他の例は、ＢＺｉｐ２である。ＢＺｉｐ２は、圧縮中に順番に生じた後に解凍中に順番が逆転するファイル又は他のデータを種々の技術を用いて圧縮する圧縮ライブラリである。ＢＺｉｐ２によって実行される圧縮は、１００ｋＢと９００ｋＢとの間のサイズのデータブロックで行われる。連長圧縮（ＲＬＥ）が、一連のデータ(runs of data)を単一値として記録するために用いられる。その後、Ｂｕｒｒｏｗｓ−Ｗｈｅｅｌｅｒ変換（ＢＷＴ）が適用され、データのブロックの可逆的な変換を用いる。圧縮は、変換中に生じず、代わりに、データは、相補アルゴリズム(complementary algorithm)による圧縮を更に簡単にするよう変更される。頻繁に再発する文字列を同一の文字のストリングに変換するためにＢＷＴを用いた後、記号をインデックス付きアレイに置換するためにＭｏｖｅ−ｔｏ−Ｆｒｏｎｔ変換を適用する。この場合、最も一般的なソースシンボル(source symbols)を短いビットストリングを用いて表現するためにハフマン符号が用いられ、これによってファイルのサイズを圧縮する。
【００６３】
非圧縮性データの一つ以上のブロックの提供の基礎として利用可能な予め決定された基準を満たす非圧縮性データのシーケンスに関連した予め決定された基準は、予め決定されたしきい値より下にある又は予め決定されたしきい値を超える非圧縮性データのシーケンスの非圧縮性及び／又はランダム性を表す統計的尺度を備えることができ、しきい値は、尺度の特性に依存する。それに対し、同等の手法は、非圧縮性データのシーケンスの圧縮性及び／又は予測可能性のレベルを表す統計的尺度を用いることができ、予め決定された基準は、予め決定されたしきい値より下にある又は予め決定されたしきい値を超えるそのような統計的尺度を備えることができ、しきい値は、尺度の特性に依存する。特に、予め決定された基準は、非圧縮性データのシーケンスに基づいて、例えば、それぞれの予め決定されたしきい値を超える（又は超えない）非圧縮性データのシーケンスの一つ以上のランダムに選択したセグメント又は一つ以上の予め決定されたセグメントに基づいて取得した統計的尺度を備えることができる。予め決定された基準は、典型的には、ＰＲＮＧ、データ圧縮器又は非圧縮性データの他のソースから取得した非圧縮性データに同様に適用することができる。
【００６４】
シーケンスを評価し又はランダム性のレベルを決定するためにシーケンスに適用することができる複数の統計的検定が存在する。アメリカ国立標準技術研究所（ＮＩＳＴ）は、（Ｐ）ＲＮＧによって提供されたランダム性のレベルを示すことを目的とした一連の統計的尺度を開発した。ＮＩＳＴは、ランダム性を「確率論的性質：すなわち、ランダムシーケンスの性質を、確率に関連して特徴付けし及び説明することができる。真のランダムシーケンスに適用するときの統計的検定の起こりそうな結果は、先験的に知られ、確率的な表現で記載することができる。」と定義する。
【００６５】
統計的検定に関連して、ＮＩＳＴは、「統計的仮説検定が役に立つ理由は、基準分布(reference distribution)及び臨界値がランダム性の試論に依存しかつそれに基づいて生成されるからである。ランダム性の仮定が実際に間近のデータ(data at hand)に当てはまる場合、結果的に得られる計算されたデータ上の検定統計値は、臨界値を超える確率が非常に低い（例えば、０．０１％）。それに対し、計算した検定統計値が臨界値を超える場合（すなわち、低い確率事象が実際に生じる場合）、統計的仮説検定の観点から、低い確率現象は自然に起こるべきではない。したがって、計算した検定統計値が臨界値を超える場合、ランダム性の最初の仮定は疑わしい又は不完全であるという結論に至る。この場合、統計的仮説検定は、Ｈ０（ランダム性）を拒否し、かつ、Ｈａ（非ランダム性）を受け入れるという結論を生じる。」を書き加える。
【００６６】
テストスイートの出力（Ｐ値）を議論するに当たり、ＮＩＳＴは、「これらのテストに対し、テストによって評価されるような非ランダム性が与えられる場合、各Ｐ値は、テストされたシーケンスよりランダムでないシーケンスを完全な乱数発生器が発生した確率となる。テストに対するＰ値が１に等しいと決定された場合、シーケンスは、完全なランダム性を有するように見える。０のＰ値は、シーケンスが完全に非ランダムであるように見えることを表す。Ｐ値≧０．０１は、シーケンスが９９％の信頼性をもってランダムであるとみなされることを意味する。Ｐ値≦０．０１は、シーケンスが９９％の信頼性をもって非ランダムであると結論付けられたことを意味する。」と言明している。
【００６７】
テストスイートは、ＮＩＳＴのコンピュータセキュリティ部門と統計工学部門との間(between Computer Security and Statistical Engineering divisions)の協力の結果である種々の異なるテストからなる。以下、試験方法の詳細な説明を有する三つの例を提供する。
【００６８】
したがって、非圧縮性のレベルを決定する適切な手法は、非圧縮性データのシーケンスが実際には非ランダムであり、したがって、予測可能及び／又はある程度圧縮可能であるという帰無仮説を有する統計的検定を実行することを備えることができる。その結果、そのような統計的検定の結果として予め決定されたしきい値を超えるＰ値は、圧縮性データのシーケンスが十分な程度まで非圧縮性であることを表す役割を果たす。以下の例において、予め決定されたしきい値を、９９％の信頼水準を有する非圧縮性を表す０．０１に設定する。しかしながら、所望される程度のデータの保証された非圧縮性の観点から異なる信頼水準を適用するために、本発明の範囲を逸脱することなく異なるしきい値を用いることができる。
【００６９】
非圧縮性データのシーケンスの非圧縮性を表す予め決定された基準として用いることができる統計的尺度を決定するために用いることができる統計的検定の第１の例として、重なりのあるテンプレート適合検定がある。この検定は、データのシーケンスから任意長の特定パターンを探索するように設計される。データのシーケンスは、どのくらいの頻度でパターンがビットストリーム内に再発するかを見るためにビット単位で分析される。検定の目的は、データのシーケンスが非周期的であるか否かを決定することである。圧縮性／非ランダムビットストリームは、整合パターンを示し、０．０１のしきい値より下のＰ値を次々と生成する。
【００７０】
テンプレート適合検定を、例えば、ＮＩＳＴによる“Ａ  ｓｔａｔｉｓｔｉｃａｌ  Ｔｅｓｔ  Ｓｕｉｔｅ  ｆｏｒ  Ｒａｎｄｏｍ  ａｎｄ  Ｐｓｅｕｄｏｒａｎｄｏｍ  Ｎｕｍｂｅｒ  Ｇｅｎｅｒａｔｏｒ  ｆｏｒ  Ｃｒｙｐｔｏｇｒａｐｈｉｃ  Ａｐｐｌｉｃａｔｉｏｎｓ”の表題の文献に記載されているような（ａ）〜（ｆ）までの以下のステップを用いて説明することができる。この文献を、例えば、
【化１１】
0006313489.tif 000020
で見つけることができ、文書番号ＳＰ８００−２２  Ｒｅｖ．１ａとも称する。テンプレート適合検定の以下の説明において、ｍは、テンプレートのビット長を表し、ｎは、ビットストリングの長さを表し、εは、生成したビットのシーケンスを表し、Ｂは、整合されるｍビットテンプレートを表し、Ｋは、自由度の数を表し、Ｍは、テストされるεのサブストリングのビット長を表し、Ｎは、ｎの独立ブロックの数を表す。
ａ）シーケンスを、長さＭを有するＮ個の独立ブロックに分割する。
ｂ）Ｎブロックの各々におけるＢの発生回数を計算する。整合の探索は、シーケンスにｍビット窓(m-bit window)を形成し、当該窓内のビットとＢとを比較し、整合があるときにはカウンタを増分することによって進行する。窓は、各検査後に１ビットに亘ってスライドし、例えば、ｍ＝４であり、最初の窓がビット４２からビット４５を含む場合、次の窓は、ビット４３からビット４６によって構成される。サブストリングにおいてＢの発生がないときにｖ０を増分し、Ｂの発生が１回であるときにｖ１を増分し、．．．、Ｂの発生が５回以上であるときにｖ５を増分するようにアレイＶｉを増分することによって、各ブロックのＢの発生回数を記録する。
ｃ）ｖ０のクラスに対応する理論的確率Πｉを計算するために用いられるλ及びηの値を計算する。
【数９】
0006313489.tif 000021
ｄ）Ｘ2（ｏｂｓ）＝
【数１０】
0006313489.tif 000022
を計算する。この場合、Π０＝０．３６４０９１，Π１＝０．１８５６５９，Π２＝０．１３９３８１，Π３＝０．１００５７１，Π４＝０．０７０４３２及びΠ５＝０．１３９８６５である。
ｅ）Ｐ値＝
【数１１】
0006313489.tif 000023
を計算する。この場合、ｉｇａｍｃ（）は、例えば、Ｃｅｐｈｅｓ  Ｃ−ｌａｎｇｕａｇｅ  Ｓｐｅｃｉａｌ  ｆｕｎｃｔｉｏｎｓ  ｍａｔｈ  ｌｉｂｒａｒｙ
【化１２】
0006313489.tif 000024
又は
【化１３】
0006313489.tif 000025
において提供される不完全ガンマ関数を表す。
ｆ）（１％レベルにおける）規則の決定。計算したＰ値が０．０１より小さい場合、シーケンスが非ランダムであると結論付ける。そうでない場合、シーケンスがランダムであると結論付ける。
【００７１】
結果的には、重なりのあるテンプレート適合検定の結果、すなわち、結果的に得られるＰ値を、Ｐ値が０．０１以上である場合に予め決定された基準を満たすように非圧縮性データのシーケンスの非圧縮性に対する予め決定された基準として用いることができる。
【００７２】
非圧縮性データのシーケンスの非圧縮性を表す予め決定された基準として用いることができる統計的尺度を決定するために用いることができる統計的検定第２の例として、離散フーリエ変換（スペクトル）検定がある。この検定の目的は、シーケンスの離散フーリエ変換のピーク高さに注目することによってビットストリームが周期的なパターンを示すか否かを検出することである。各パターンが互いに近接して見つけられる場合、好ましくない結果が生じ、データは、非ランダム／圧縮性であるとみなされる。
【００７３】
離散フーリエ変換（スペクトル）検定を、例えば、ＮＩＳＴによる“Ａ  Ｓｔａｔｉｓｔｉｃａｌ  Ｔｅｓｔ  Ｓｕｉｔｅ  ｆｏｒ  Ｒａｎｄｏｍ  ａｎｄ  Ｐｓｅｕｄｏｒａｎｄｏｍ  Ｎｕｍｂｅｒ  Ｇｅｎｅｒａｔｏｒｓ  ｆｏｒ  Ｃｒｙｐｔｏｇｒａｐｈｉｃ  Ａｐｐｌｉｃａｔｉｏｎｓ”の表題の文献にも記載されている（ａ）〜（ｉ）の以下のステップを用いて説明することができる。離散フーリエ変換（スペクトル）検定の以下の説明において、ｎは、ビットストリングの長さを表し、εは、テストされるビットのシーケンスを表し、ｄは、９５％しきい値より下にある周波数成分の観察される数と予測される数との間の正規化差である。
ａ）入力シーケンス（ε）の０及び１を、シーケンスＸ＝ｘ１，ｘ２，．．．，ｘｎを形成するために−１及び＋１の値に変換し、この場合、ｘｉ＝２εｉ−１である。
ｂ）離散フーリエ変換（ＤＦＴ）をＸに適用してＳ＝ＤＦＴ（Ｘ）を生成する。複素変数のシーケンスを生成し、これは、異なる周波数におけるビットのシーケンスの周期的な成分を表す。
ｃ）Ｍ＝
【数１２】
0006313489.tif 000026
を計算する。この場合、Ｓ’は、Ｓの最初のｎ／２要素からなるサブストリングであり、モジュロ関数(modulus function)は、ピーク高さのシーケンスを生成する。
ｄ）Ｔ＝
【数１３】
0006313489.tif 000027
＝９５％ピーク高さしきい値を計算する。ランダム性の仮定の下では、テストから得られる値の９５％はＴを超えるべきではない。
ｅ）Ｎ０＝．９５ｎ／２を計算する。Ｎ０は、Ｔより小さい（ランダム性の仮定の下で）予測される理論的なピーク数（９５％）である。
ｆ）Ｎ１＝ＭにおけるＴより小さい実際に観察されるピーク数を計算する。
ｇ）ｄ＝
【数１４】
0006313489.tif 000028
を計算する。
ｈ）Ｐ値＝
【数１５】
0006313489.tif 000029
を計算し、この場合、ｅｒｆｃは、ｍａｔｈ．ｈのヘッダ及びそれに対応する数値演算ライブラリに含まれるＡＮＳＩ  Ｃの関数である。
ｉ）（１％レベルにおける）規則の決定。計算したＰ値が０．０１より小さい場合、シーケンスが非ランダムであると結論付ける。そうでない場合、シーケンスがランダムであると結論付ける。
【００７４】
結果的には、離散フーリエ変換（スペクトル）検定の結果、すなわち、結果的に得られるＰ値を、Ｐ値が０．０１以上である場合に予め決定された基準を満たすような非圧縮性データのシーケンスの非圧縮性に対する予め決定された基準として用いることができる。
【００７５】
非圧縮性データのシーケンスの非圧縮性を表す予め決定された基準として用いることができる統計的尺度を決定するために用いることができる統計的検定第３の例として、Ｍａｕｒｅｒのユニバーサル統計検定がある。Ｍａｕｒｅｒのユニバーサル統計検定は、情報の損失なく著しく圧縮することができるか否かを決定するのに適用することができる。その結果、著しい圧縮性データシーケンスは非ランダムとみなされ、それに対し、著しく圧縮することができないデータシーケンスはランダムとみなされる。Ｍａｕｒｅｒのユニバーサル統計検定の出力値は、情報の損失なく圧縮することができない程度までデータシーケンスがランダムであるか否かを表し、これによって、（疑似ランダム）データのシーケンスの非圧縮性及び／又はランダム性を表す統計的尺度の一例を提供する。
【００７６】
換言すれば、Ｍａｕｒｅｒのユニバーサル統計検定の目的は、バイナリシーケンスを圧縮することができるか否かを検出することである。著しい圧縮性のシーケンスは、非ランダムとみなされる。例えば、ＲＮＧの出力は、出力シーケンスを圧縮することができない場合にはこのテストをパスすべきである。テストは、整合するパターン間のビット数を検査する間にシーケンス全体について調べることを含む。テストは、情報の損失なくシーケンスを著しく圧縮することができるか否かを検出する。
【００７７】
Ｍａｕｒｅｒのユニバーサル統計検定を、例えば、ＮＩＳＴによる“Ａ  Ｓｔａｔｉｓｔｉｃａｌ  Ｔｅｓｔ  Ｓｕｉｔｅ  ｆｏｒ  Ｒａｎｄｏｍ  ａｎｄ  Ｐｓｅｕｄｏｒａｎｄｏｍ  Ｎｕｍｂｅｒ  Ｇｅｎｅｒａｔｏｒｓ  ｆｏｒ  Ｃｒｙｐｔｏｇｒａｐｈｉｃ  Ａｐｐｌｉｃａｔｉｏｎｓ”の表題の文書で見つけられる（ａ）〜（ｆ）の以下のステップによって説明することができる。Ｍａｕｒｅｒのユニバーサル統計検定の以下の説明において、Ｌは、各ブロックの長さを表し、Ｑは、初期化シーケンスのブロック数を表し、ｎは、ビットストリングの長さを表し、εは、テストされるビットのシーケンスを表す。
ａ）ｎビットシーケンス（ε）を、二つのセグメントに分割する。初期化シーケンスは、Ｑ個のＬビット非重複ブロック(non-overlapping block)からなり、テストセグメントは、Ｋ個のＬビット非重複ブロックからなる。完全なＬビットブロックを形成しないシーケンスの端にとどまるビットは、捨てられる。最初のＱブロックは、テストを初期化するために用いられる。残りのＫブロックは、テストブロックである（Ｋ＝［ｎ／Ｌ］−Ｑ）。
ｂ）初期化セグメントを用いることによって、テーブルが、あり得るＬビット値の各々に対して形成される（すなわち、Ｌビット値は、テーブルのインデックスとして用いられる）。各Ｌビットブロックの最後の発生のブロック数は、テーブルに表記される（すなわち、１〜Ｑのｉに対して、Ｔｊ＝ｉ。この場合、ｊは、ｉ番目のＬビットブロックのコンテンツの十進表現である。）。
ｃ）テストセグメントのＫブロックの各々を調べ、同一のＬビットブロックの最後の発生からのブロック数（すなわち、ｉ−Ｔｊ）を決定する。テーブルの値を現在のブロックの位置（すなわち、Ｔｊ＝ｉ）に置換する。Ｋ個のブロックで検出した距離の全てのｌｏｇ２の和（ｓｕｍ）を累算するために同一のＬビットブロックの再発間の計算した距離を加算する（すなわち、ｓｕｍ＝ｓｕｍ＋ｌｏｇ２（ｉ−Ｔｊ））。
ｄ）検定統計量：ｆｎ＝
【数１６】
0006313489.tif 000030
を計算する。この場合、Ｔｊは、ｉ番目のＬビットブロックのコンテンツの十進表現に対応するテーブル項目である。
ｅ）Ｐ値＝
【数１７】
0006313489.tif 000031
を計算する。この場合、ｅｒｆｃは、ｍａｔｈ．ｈのヘッダ及びそれに対応する数値演算ライブラリに含まれるＡＮＳＩ−Ｃの関数であり、ｅｘｐｅｃｔｅｄＶａｌｕｅ（Ｌ）及びσを、“Ｈａｎｄｂｏｏｋ  ｏｆ  Ａｐｐｌｉｅｄ  Ｃｒｙｐｔｏｇｒａｐｈｙ”からの事前計算された値のテーブルから取得する。ランダム性の仮定の下では、サンプル平均ｅｘｐｅｃｔｅｄＶａｌｕｅ（Ｌ）は、所定のＬビット長の演算された統計量の理論的に予測される値である。理論的な標準偏差は、σ＝
【数１８】
0006313489.tif 000032
によって与えられ、この場合、ｃ＝
【数１９】
0006313489.tif 000033
である。
ｆ）計算したＰ値が０．０１未満である場合、シーケンスが非ランダムであると結論付けられ、そうでない場合、シーケンスがランダムであると結論付けられる。
【００７８】
その結果、Ｍａｕｒｅｒのユニバーサル統計検定の結果、すなわち、計算されたＰ値を、非圧縮性データのシーケンスの非圧縮性に対する予め決定された基準として用いることができ、Ｐ値が０．０１以上である場合に予め決定された基準を満たす。
【００７９】
データシーケンスの非圧縮性を評価するのに適した統計検定の三つの例を、（Ｐ）ＲＮＧから生じたデータのシーケンス、データ圧縮器から生じたデータのシーケンス又は異なるタイプのデータ源から生じたデータのシーケンスの非圧縮性を評価するのに同様に適用することができる。
【００８０】
データ提供部１１２を、メモリから、又は、メモリから非圧縮性データのシーケンスを読み出すとともに読み出したシーケンスを非圧縮データの一つ以上のブロックに分割することによって、非圧縮性データの一つ以上のブロックを取得するように構成することができる。非圧縮性データのブロック及び／又はシーケンス非圧縮性データを、並行して実行する他のプロセスによってメモリに格納し、又は、これらを事前に生成するとともにデータを事前に格納することができる。メモリを、データ消去装置１１０の構成要素として、データ消去装置をホストする装置の構成要素として又はデータ提供部１１２によってアクセスすることができる個別の装置の構成要素として、データ提供部１１２に対して利用することができる。
【００８１】
代わりに、データ提供部１１２を、非圧縮性データの一つ以上のブロックに分割するために非圧縮性データのシーケンスを生成する予め決定されたプロセス又は方法を適用することによって非圧縮性データの一つ以上のブロックを取得するように構成することができる。プロセス又は方法は、上述したようにＰＲＮＧ、例えば、第１の例示的なＰＲＮＧ、第２の例示的なＰＲＮＧ、第３の例示的なＰＲＮＧ及び／又は予め決定された基準を満たす非圧縮性データのシーケンスを提供するのに適切であると考えられる他のＲＰＮＧ、又は、予め決定された基準を満たす非圧縮性データのシーケンスを提供するように構成されたデータ圧縮器を用いることを備えることができる。
【００８２】
非圧縮性データの一つ以上のブロックは等しいサイズを有することができ、又は、非圧縮性データの一つ以上のブロックは異なるサイズを示すことができる。一つ以上のデータブロックのサイズをＳｉ，ｉ＝１，．．．，ｎで表し、データ記憶装置１２０の記憶容量をＣで表す場合、データ記憶装置１２０の記憶容量以上の非圧縮性データの一つ以上のブロックのサイズの和の要件を、
【数２０】
0006313489.tif 000034
と定式化することができる。基本的には任意のブロックサイズＳｉを適用できるのに対し、単一のブロックデータのサイズＳｉを、例えば、５１２バイトから４ギガバイトまでの範囲の適切なサイズとすることができる。非圧縮性データの一つ以上のブロックのサイズを、データ記憶装置１２０の記憶容量Ｃの観点から及び／又はホストインタフェース１３０の特性又は性能の観点から選択することができる。しかしながら、典型的には、Ｓｉ＜＜Ｃ、すなわち、データ記憶装置１２０の記憶容量より著しく小さいサイズを有する非圧縮性データのブロックが用いられる。
【００８３】
データ消去装置１１０を、データ記憶装置１２０の全ての物理メモリ位置の上書きを保証するためにデータ提供部１１２及びデータ書込み部１１４に対して上述した動作を１回以上行うように構成することができる。データ記憶装置１２０の記憶容量以上の結合されたサイズを有する非圧縮性データの一つ以上のブロックのセットの書込みを、（単一の）書込みパスと称することができる。したがって、データ消去プロセスは、全体としては一つ以上の上書きパスを備えることができる。
【００８４】
これに関連して、データ提供部１１２を、非圧縮性データの一つ以上のブロックの一つ以上の追加のセットを取得するように構成することができ、追加のセットのそれぞれの非圧縮性データの一つ以上のブロックのサイズの和は、データ記憶装置の記憶容量以上である。非圧縮性データの一つ以上のブロックの一つ以上の追加のセットを、好適には、非圧縮性データの最初の一つ以上のブロックの提供の基礎として用いられるような非圧縮性データの同一シーケンスに基づいて取得する。代わりに、場合によっては異なる特性を有する予め決定された基準を満たす非圧縮性データの個別のシーケンスを、非圧縮性データの一つ以上の追加のセットの基礎として用いることができる。しかしながら、非圧縮性データの一つ以上のブロックの各セットを、好適には、非圧縮性データの一つ以上のブロックのセットのブロックに亘って十分なレベルの非圧縮性を保持するのを保証するために非圧縮性データの単一のシーケンスに基づいて設ける。
【００８５】
さらに、データ書込み部１１４を、データ記憶装置１２０に対して、データ記憶装置に現在格納されているデータを上書きするために記憶用の非圧縮性データの一つ以上のブロックの一つ以上の追加のセットを一度に１セットずつ提供するように構成することができる。換言すれば、記憶のためにデータ記憶装置１２０に提供される非圧縮性データの一つ以上のブロックの追加のセットの各々は、単一の上書きパスを表す。
【００８６】
データ書込み部１１４を、データ記憶装置１２０へのデータの成功した上書きを検証するように構成することもできる。これに関連して、データ書込み部１１４を、データ記憶装置１２０に格納したデータの一つ以上の選択した部分と、データ記憶装置への記憶のために最近設けた非圧縮性データの一つ以上のブロックのそれぞれの部分とを比較するように構成することができる。検証を、データ記憶装置１２０への非圧縮性データの一つ以上のブロックの最初の提供後及び／又はデータ記憶装置１２０への非圧縮性データの一つ以上のブロックの一つ以上の追加のセットの提供後に実行することができる。検証は、データ記憶装置への記憶のために最近設けた非圧縮性データの一つ以上のブロックのそれぞれの部分が実際にデータ記憶装置に格納されるのを確認するのに役に立ち、したがって、データ記憶装置１２０の論理メモリの一つ以上の部分のそれぞれに以前に格納したデータの成功した上書きの表示を提供する。
【００８７】
一つ以上の選択した部分は、データ記憶装置１２０の論理メモリの一つ以上の部分の予め規定されたセットを備える。代わりに又は追加して、選択した部分は、例えば、固定した又はランダムに選択したサイズを有するデータ記憶装置１２０の論理メモリの一つ以上のランダムに選択した部分を備えることができ、これによって、データ記憶装置１２０の記憶部に設けられたデータの観点からデータ消去プロセスの成功のスポットチェックを提供する。更に別の例として、（一つ以上の）選択した部分は、データ記憶装置１２０の全記憶容量をカバーすることができ、これによって、上書きプロセスの完全な検証を提供する。データ記憶装置に格納されたデータの選択した部分の全てが、記憶のために最近設けた非圧縮性データの一つ以上のブロックの各部分と同一である場合、検証を成功したものとみなすことができる。
【００８８】
データ消去装置１１０を、予め決定された回数すなわち１回以上の上書きパスを適用するように構成することができる。代わりに、データ消去装置１１０を、検証の結果の観点から複数の上書きパスを選択するように構成することができる。一例として、データ書込み部１１４を、上書きパスのそれぞれの後に成功した上書きを検証するとともに、予め決定された回数の上書きパスの結果としての記憶装置１２０へのデータの成功した上書きに出くわしたときにデータ消去プロセスを完了したと見なすように構成することができる。
【００８９】
上述した動作、手順及び／又は機能に加えて、データ消去装置１１０を、データ記憶装置１２０に格納されたデータの完全な消去を更に保証するための別の手段を適用するように構成することができる。
【００９０】
一例として、データ消去装置１１０を、データ記憶装置１２０内にファームウェアレベルコマンドを発行してデータ記憶装置１２０の全てのユーザアドレス指定可能記憶位置の初期化を行うことによってデータ記憶装置１２０に現在格納されているデータを消去する内部プロセスをデータ記憶装置１２０に適用させるように構成されたコマンドを、データ記憶装置１２０に供給するように構成することができる。そのようなコマンドを、サニタイズコマンドと称することができ、コマンドを、例えば、データ書込み部１１４によって発行することができる。データ書込み部１１４を、例えば、非圧縮性データの一つ以上のブロックによるデータ記憶装置１２０へのデータの成功した上書きの検証に関連して上述したようにしてサニタイズコマンドの成功を検証するように更に構成することができる。特に、サニタイズコマンドの検証は、非圧縮性データの一つ以上のブロックのそれぞれの部分がもはやデータ記憶装置に格納されていないことを確認するために、データ記憶装置１２０に格納されたデータの一つ以上の選択した部分と、データ記憶装置への記憶のために設けた非圧縮性データの一つ以上のブロックのそれぞれの部分とを比較し、これによって、サニタイズコマンドの成功した供給の表示を提供する。
【００９１】
サニタイズコマンドのフォーマットは、典型的には、データ消去装置１１０及びデータ記憶装置１２０に接続するホストインタフェース１３０に依存する。一例として、ホストインタフェース１３０がＡＴＡインタフェースを備える場合、サニタイズコマンドは、各インタフェース又はプロトコルに従って“ＳＥＣＵＲＩＴＹ  ＥＲＡＳＥ  ＵＮＩＴ”コマンド又は“ＳＡＮＩＴＩＺＥ”コマンドセットを備えることができる。他の例として、ホストインタフェース１３０がＳＣＳＩコマンドを備える場合、サニタイズコマンドは、各インタフェース又はプロトコルに従って“ＦＯＲＭＡＴ  ＵＮＩＴ”コマンドを備えることができる。
【００９２】
データ消去装置１１０の構造ユニット、例えば、データ提供部１１２及びデータ書込み部１１４に割り当てられた動作、手順及び／又は機能を、異なる方法でこれらの部分の間で分けることができる。さらに、データ消去装置１１０は、データ提供部１１２及びデータ書込み部１１４に割り当てられた動作、手順及び／又は機能の一部を実行するように構成することができる別の部分又はユニットを備えることができる。それに対し、データ提供部１１２及びデータ書込み部１１４に割り当てられた動作、手順及び／又は機能を、データ消去装置１１０内の単一の部分又は単一の処理装置に割り当てることができる。
【００９３】
特に、データ消去装置１１０を、データ記憶装置１２０に記憶されたデータを消去する機器として設けることができ、データ消去機器は、予め決定された基準を満たす非圧縮性データのシーケンスを取得する手段であって、非圧縮性データのシーケンスは、非圧縮性データの一つ以上のブロックに分割され、非圧縮性データの一つ以上のブロックのサイズの和はデータ記憶装置の記憶容量以上である手段と、データ記憶装置に対して、データ記憶装置に現在格納されているデータを上書きするために記憶用の非圧縮性データの一つ以上のブロックを提供する手段と、を備える。
【００９４】
データ消去装置１１０に関連した上述した動作、手順及び／又は機能を、対応する動作、手順及び／又は機能を実現する方法の形態で説明することもできる。これに関連する一例として、図４は、データ記憶装置１２０に格納されたデータを消去する例示的な方法４００を示す。したがって、方法４００は、説明に役立つ例としての役割を果たし、データ消去装置１１０に関連した上述した動作、手順及び／又は機能の異なる組合せを提供する別の方法を、本発明の範囲を逸脱することなく提供することができる。
【００９５】
方法４００は、データ提供部１１２に関連して上述するとともにブロック４１０に示すように、非圧縮性に関連する予め決定された基準を満たす非圧縮性データのシーケンスから抽出される非圧縮データの一つ以上のブロックを取得することを備える。予め決定された基準は、例えば、データ提供部１１２に関連して上述したように、予め決定されたしきい値を超えるデータのシーケンスの非圧縮性を表す一つ以上の統計的尺度を備える。非圧縮性データのシーケンスは、例えば、データ提供部１１２に関連して説明したように、例えば、提供する乱数のランダム性に関連する予め決定された基準を満たす乱数発生器から、又は、場合によってはランダムな原始データをこの関連で予め決定された基準を満たす非圧縮性データのシーケンスに圧縮するために予め決定された規則を適用するデータ圧縮器から発生することができる。
【００９６】
方法４００は、ブロック４２０に示すとともにデータ書込み部１１４に関連して上述したように、データ記憶装置１２０に対して、データ記憶装置１２０に現在格納されているデータを上書きするために記憶用の非圧縮性データの一つ以上のブロックを提供することを更に備えることができる。
【００９７】
その結果、方法４００は、非圧縮性データの一つ以上のブロックに対して、圧縮性データのブロックのサイズが非圧縮性データの対応するブロックのサイズ以上となるように、データ記憶装置１２０の物理メモリに書き込まれ、したがって、格納された圧縮性データの対応する一つ以上のブロックを提供するために非圧縮性データの一つ以上のブロックに対する圧縮をデータ記憶装置１２０で行うことを任意に更に備えることができる。方法４００は、データ記憶装置１２０の物理メモリに圧縮性データを格納することを任意に更に備えることができる。方法４００は、現在の上書きパスを完了するためにデータ記憶装置１２０の記憶に対して非圧縮性データの十分な数のブロックを提供するまでブロック４１０及び４２０で説明した処理の繰り返しを備えることができる。上書きパスを完了することは、非圧縮性データのブロックの結合されたサイズがデータ記憶装置１２０の記憶容量以上となるようにデータ記憶装置１２０への格納のための非圧縮性データのブロックを（取得すること及び）提供することを備える。したがって、ブロック４３０に示すような現在の上書きパスを完了したか否かのテストは、現在の上書きパス中にデータ記憶装置１２０に提供される非圧縮性データのブロックの累算したサイズがデータ記憶装置１２０の記憶容量以上であるか否かをチェックすることを備えることができる。累算したサイズがデータ記憶装置１２０の記憶容量以上であることに応答して、方法４００は、ブロック４４０又は４５０に進み、それに対し、累算したサイズがデータ記憶装置１２０の記憶容量未満であることに応答して、方法４１０は、ブロック４１０に戻る。
【００９８】
方法４００は、ブロック４４０に示すとともにデータ書込み部１１４に関連して上述したように、データ記憶装置１２０に格納するために最近設けた非圧縮性データの一つ以上のブロックの各部分が実際に格納されているのを検証するために、データ記憶装置１２０に格納されたデータの一つ以上の選択した部分と記憶用に最近設けた非圧縮性データの一つ以上のブロックの各部分とを比較することを、任意に更に備えることができる。
【００９９】
方法４００は、ブロック４１０〜４３０又は４４０で言及した動作、手順及び／又は機能を任意に繰り返すことができる。換言すれば、これは、上述したように、（予め決定された）複数の上書きパスを設けることに対応する。特に、方法４００は、ブロック４５０に示すように、現在の上書きパスが最後のものであるか否かをチェックすることができる。チェックは、例えば、データ消去装置１１０に関連して上述したように、予め決定された数の上書きパスを完了したか否か及び／又はブロック４４０で言及した任意の検証がデータ記憶装置１２０に以前に格納されたデータの成功した上書きを表すか否かを備えることができる。その結果、現在の上書きパスが最後のものでないことに応答して、方法４００は、次の上書きパスのためにブロック４１０に進み、それに対し、現在の上書きパスが最後のものであることに応答して、方法４００を完了したものとみなすことができ、したがって、データ記憶装置１２０に以前に格納されたデータを、安全に上書きされたものとみなすことができ、又は、方法４００は、データ消去装置１１０に関連して上述するとともにブロック４６０で示すように、用いたホストインタフェース１３０に応じてサニタイズコマンドを任意に発行することができる。ブロック４６０で言及したサニタイズを、例えば、ブロック４１０の前で、ブロック４３０（又は４４０）と４５０との間で、又は、ブロック４５０と４１０との間で代わりに又は追加して実行することができる。
【０１００】
図５は、プロセッサ５１０と、メモリ５２０と、他の装置との無線通信又は有線通信を行うことができるネットワークカード又はネットワークアダプタのような通信インタフェース５３０と、を備える例示的な装置を図式的に示す。プロセッサ５１０は、メモリ５２０からの読出し及びメモリ５２０への書込みを行うように構成される。装置５００は、データ、コマンド及び／又は他の入力をプロセッサ５１０に供給し及び／又はデータ及び他の入力をプロセッサ５１０から受信するユーザインタフェース５４０を更に備えることができ、ユーザインタフェース５４０は、例えば、ディスプレイ、キーボード又はキー、マウス又は各ポインティングデバイス、タッチスクリーン等を備える。装置５００は、図５の例に示さない他の構成要素を備えることができる。
【０１０１】
プロセッサ５１０を単一の構成要素として図５の例で示すが、プロセッサ５１０を、一つ以上の個別の構成要素として実現することができる。メモリ５２０を単一の構成要素として示すが、メモリ５２０を、一つ以上の個別の構成要素として実現することができ、その一部又は全てを、統合／取外し自在とすることができ、及び／又は、永久的／半永久的／ダイナミック／キャッシュメモリとすることができる。
【０１０２】
装置５００を、十分な処理能力を有する専用又は汎用装置として、例えば、携帯電話、カメラ、ビデオカメラ、音楽プレーヤ、ゲーム機、ラップトップコンピュータ、デスクトップコンピュータ、サーバ装置、携帯情報端末（ＰＤＡ）、インターネットタブレット、テレビ受像機等として実現することができる。代わりに、装置５００を、上述したようにデータ消去装置１１０として動作するための専用の装置として実現することができる。
【０１０３】
メモリ５２０は、プロセッサ５１０にロードするとともにプロセッサ５１０によって実行されるときに装置５００の動作を制御するコンピュータ読取可能命令を備えるコンピュータプログラム５５０を格納することができる。一例として、コンピュータプログラム５５０は、一つ以上の命令の一つ以上のシーケンスを有することができる。コンピュータプログラム５５０を、コンピュータプログラムコードとして設けることができる。プロセッサ５１０は、コンピュータプログラム５５０に含まれる一つ以上の命令の一つ以上のシーケンスをメモリ５２０から読み出すことによってコンピュータプログラム５５０をロードし及び実行することができる。一つ以上の命令の一つ以上のシーケンスを、一つ以上のプロセッサによって実行するときに、データ消去装置１１０に関連して上述した動作、手順及び／又は機能を装置、例えば、装置５００によって実現させるように構成することができる。
【０１０４】
したがって、装置５００は、少なくとも一つのプロセッサ５１０と、一つ以上のプログラムに対するコンピュータプログラムコードを含む少なくとも一つのメモリ５２０と、を備えることができ、少なくとも一つのメモリ５２０及びコンピュータプログラムコードは、データ消去装置１１０に関連して上述した動作、手順及び／又は機能を少なくとも一つのプロセッサ５１０により装置５００に実行させるように構成される。
【０１０５】
コンピュータプログラム５５０を、装置と独立して設けることができ、コンピュータプログラム５５０を、任意の適切な受渡機構(delivery mechanism)を介して装置５００に設けることができる。一例として、受渡機構は、格納されたプログラムコードを有する少なくとも一つのコンピュータ読取可能非一時的記憶媒体を備え、プログラムコードは、装置によって実行されるときに、データ消去装置１１０に関連して上述した動作、手順及び／又は機能を実行するために処理を装置によって少なくとも実現させる。受渡機構を、例えば、コンピュータ読取可能記憶媒体、コンピュータプログラム製品、記憶装置、ＣＤ−ＲＯＭのような記録媒体、ＤＶＤ、対応する光媒体、コンピュータプログラム５５０を目に見える方法で実現する製品等とすることができる。他の例として、受渡機構を、信頼性をもってコンピュータプログラム５５０を転送するように構成した信号とすることができる。
【０１０６】
プロセッサへの言及は、プログラマブルプロセッサだけでなく、フィールドプログラマブルゲートアレイ（ＦＰＧＡ）、特定用途向け集積回路（ＡＳＩＣ）、信号プロセッサ等のような専用回路も含むことを理解すべきである。前述の説明で説明した特徴を、明確に説明した組合せ以外の組合せで用いることができる。機能を所定の特徴を参照して説明したが、これらの機能を、説明した又は説明していない他の特徴によって実行することができる。特徴を所定の実施の形態を参照しながら説明したが、これらの特徴は、説明した又は説明していない他の実施の形態に存在することができる。
【図１】
0006313489.tif 000035
【図２】
0006313489.tif 000036
【図３】
0006313489.tif 000037
【図４】
0006313489.tif 000038
【図５】
0006313489.tif 000039