(57)【要約】【課題】  （例えば組み込みコンピューティング装置に）インストールするソフトウェアパッケージ群の依存関係を調べるシステムおよび方法を提供すること。【解決手段】  それにより、インストールの候補の最大の群を選択して、可能な限り少ない更新ステップで所与のパッケージの最大のバージョン更新を行うことが可能になり、同時にパッケージの依存性の制約を遵守する。更新の妥当性検証プロセスが、装置にダウンロードされた更新パッケージ群を編成し、妥当性を検証し、各グループにグラフを作成する。更新パッケージ間のパスを含むグラフデータを処理して更新の妥当性を検証し、同じバージョンに到達する２つ以上のパスが通っている場合には、重み（コスト）が最小であり、装置上の既存イメージに適用することができる最小かつ最適なパッケージ群の判定を行い、要求される更新を生成する。【選択図】  図４
2005182784.tif 000002
【特許請求の範囲】
【請求項１】
コンピューティング環境において、
装置にインストール可能な状態の更新パッケージ群を検討するステップであって、前記更新パッケージ間の依存関係と、前記装置にすでにインストールされている少なくとも１つの他のパッケージのパッケージデータとの依存関係とを判定するステップが含まれるステップと、
更新しようとするパッケージデータについて、インストールすべき少なくとも１つの更新パッケージ群を判定して、前記インストールの結果、前記パッケージデータの最新バージョンがインストールされるようにするステップと
を備えたことを特徴とする方法。
【請求項２】
装置にインストールできる状態の更新パッケージ群を調べるステップは、前記装置にインストールするためにキューに入れられた少なくとも１つの他のパッケージのパッケージデータから、前記更新パッケージ間の依存関係を判定するステップをさらに含むことを特徴とする請求項１に記載の方法。
【請求項３】
前記インストールの結果は、少なくとも２つの更新パッケージ群が、前記パッケージの最新バージョンをインストール可能であり、
最も低いインストールコストに基づく前記少なくとも２つの更新パッケージ群の１つを選択するステップをさらに備えたことを特徴とする請求項１に記載の方法。
【請求項４】
前記インストールすべき少なくとも１つのパッケージ群を判定するステップは、前記パッケージを表すノードを有するグラフを作成し、および前記ノード間で前記パッケージ間の依存関係に対応するパスを分析するステップを含むことを特徴とする請求項１に記載の方法。
【請求項５】
前記更新パッケージ群を検討するステップは、各パッケージの妥当性を検証するステップを含むことを特徴とする請求項１に記載の方法。
【請求項６】
前記各パッケージの妥当性を検証するステップは、ファイルがパッケージファイルの適切な型であるか否かを判定するステップを含むことを特徴とする請求項５に記載の方法。
【請求項７】
前記各パッケージの妥当性を検証するステップは、ファイルが、前記パッケージの内容を記述する関連付けられたマニフェストファイルを有するか否かを判定するステップを含むことを特徴とする請求項５に記載の方法。
【請求項８】
各パッケージに対応するノードをパッケージグラフに追加するステップをさらに備えたことを特徴とする請求項４に記載の方法。
【請求項９】
前記各パッケージに対応するノードをパッケージグラフに追加するステップは、該パッケージに対応するパッケージグラフがすでに存在するか否かを判定するステップと、パッケージグラフが存在する場合は、前記ノードを前記既存のパッケージグラフに追加し、パッケージグラフが存在しない場合は、新しいパッケージグラフを作成して、前記ノードを前記新しいパッケージグラフに追加するステップとを含むことを特徴とする請求項８に記載の方法。
【請求項１０】
前記パッケージグラフの各枝を処理するステップと、各枝の各ノードを処理して、各ノードを前記パッケージグラフに残すべきか否かを判定するステップとをさらに備えたことを特徴とする請求項８に記載の方法。
【請求項１１】
前記所与のノードを前記パッケージグラフに残すべきか否かを判定するために、各ノードを処理するステップは、前記所与のノードに親ノードを介して証明書チェーンが関連付けられているか否かを判定するステップと、関連付けられていない場合、前記パッケージグラフから前記ノードに対応する枝を切ることにより前記ノードを除去するステップとを含むことを特徴とする請求項１０に記載の方法。
【請求項１２】
証明書チェーンが前記所与のノードに関連付けられ、および各ノードを処理するステップは、前記所与のノードを前記パッケージグラフに残すべきか否かを判定するために、前記ノードに対応するパッケージが有効な署名を含んでいるか否かを検証するステップと、含んでいない場合は、前記パッケージグラフから前記所与のノードを起点とする前記枝を切ることにより前記ノードを除去するステップとをさらに含むことを特徴とする請求項１１に記載の方法。
【請求項１３】
前記署名は前記所与のノードについて有効であり、該ノードに基づく前記枝にデータを追加するステップをさらに備えたことを特徴とする請求項１２に記載の方法。
【請求項１４】
前記パッケージグラフを全探索し、加重が最も低い枝を見つけるステップと、その枝に対応する情報を更新リストに追加するステップとをさらに備えたことを特徴とする請求項１３に記載の方法。
【請求項１５】
少なくとも１つのノードが前記パッケージグラフに残り、および当該少なくとも１つの残るノードは、関連付けられた重みを有する枝にあり、前記パッケージグラフを全探索して加重が最も低い枝を見つけるステップと、該枝に対応する情報を更新リストに追加するステップとをさらに備えたことを特徴とする請求項１０に記載の方法。
【請求項１６】
更新グラフにパッケージを追加するステップをさらに備え、該各パッケージを処理するステップは、前記グラフ中で代表ノードを有する各パッケージに対応するパーティションを判定するステップと、そのノードの前記対応するパーティションに基づいて個々のリストに各ノードを追加することによりリスト毎に各ノードを並べ替えるステップとをさらに含むことを特徴とする請求項１５に記載の方法。
【請求項１７】
実行されると請求項１に記載の方法を実行するコンピュータ実行可能な命令を有することを特徴とする１つまたは複数のコンピュータ読取り可能な媒体。
【請求項１８】
コンピューティング装置において、
パッケージがインストールするのに妥当であるか否かについての情報を提供する妥当性検証コンポーネントと、
インストールが要求される少なくとも１つのパッケージのインストール群に対応する情報を入力し、
前記妥当性検証コンポーネントと通信して、インストールするのに妥当でないパッケージを前記インストール群から除去し、
前記装置にすでにインストールされているパッケージのパッケージデータ、および／または前記装置にインストールするためにキューに入れられたパッケージ間の依存関係を判定し、
前記依存関係に基づいて前記インストール群内のインストールすべき少なくとも１つの更新パッケージを判定し、前記インストールの結果、最新バージョンのパッケージデータが前記装置にインストールされる
ように構成された更新順序コンポーネントと
を備えたことを特徴とするシステム。
【請求項１９】
前記更新順序付けコンポーネントは、インストールコストの最も低いパッケージをインストールする更新パスを判定することを特徴とする請求項１に記載のシステム。
【請求項２０】
前記妥当性検証コンポーネントは、各パッケージに対応するファイルが適切な型のパッケージファイルであるか否かを判定することにより、各パッケージの妥当性を検証することを特徴とする請求項１９に記載のシステム。
【請求項２１】
前記妥当性検証コンポーネントは、ファイルが前記パッケージの内容を記述する関連付けられたマニフェストファイルを有するか否かを判定することにより、各パッケージの妥当性を検証することを特徴とする請求項１９に記載のシステム。
【請求項２２】
前記更新順序付けコンポーネントは、パッケージバージョンに相当するノードを有するグラフを作成し、および前記パッケージバージョン間の依存関係に対応する前記ノード間のパスを分析することによって前記更新パスを判定することを特徴とする請求項１９に記載のシステム。
【請求項２３】
前記更新順序付けコンポーネントは、前記ノード間に依存性情報に基づくエッジを構築することを特徴とする請求項１９に記載のシステム。
【請求項２４】
前記更新順序付けコンポーネントは、パッケージに対応するパッケージグラフがすでに存在するか否かを判定し、ならびに、パッケージグラフが存在する場合は前記ノードを前記存在するパッケージグラフに追加し、パッケージグラフが存在しない場合は、新しいパッケージグラフを作成し、および前記新しいパッケージグラフに前記ノードを追加することによって各パッケージに対応するノードをパッケージグラフに追加することを特徴とする請求項１９に記載のシステム。
【請求項２５】
前記更新順序付けコンポーネントは、前記パッケージグラフを全探索して加重が最も低い枝を見つけ、およびその枝に対応する情報を更新リストに追加することを特徴とする請求項２４に記載のシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、一般には、組み込みオペレーティングシステムを有するようなコンピューティング装置に関し、より詳細には、コンピューティング装置の不揮発性ストレージの更新に関する。
【背景技術】
【０００２】
携帯情報端末、現代の携帯電話、ハンドヘルドコンピュータ、ポケットサイズコンピュータなどのモバイルコンピューティング装置は、重要で一般的なユーザツールになりつつある。一般に、そうしたコンピューティング装置は、小型化されて極めて簡便になっており、さらに、消費するバッテリ電力は低減し、同時により高性能なアプリケーションの実行が可能になっている。
【０００３】
そのような装置を製造する過程で、通例組み込みオペレーティングシステムイメージがモノリシックなイメージファイルに作成され、各装置の不揮発性ストレージ（例えばＮＡＮＤ型またはＮＯＲ型のフラッシュメモリ、ハードディスクなど）に記憶される。その結果、そのような装置を時折更新することが必要となるか、あるいは望ましい。
【発明の開示】
【発明が解決しようとする課題】
【０００４】
しかし、モノリシックなオペレーティングシステムには、更新をインストールするためにモノリシックイメージ全体を入れ替えるために多量のリソース（例えば一時的ストレージや帯域幅）が必要とされることなどのいくつかの欠点がある。同時に、装置上の既存のパッケージインストール状態は変化する可能性があり、インストールのために待ち行列にある複数バージョンのパッケージがいくつもある可能性があるため、オペレーティングシステムの一部である下位群（ｓｕｂｓｅｔ）コンポーネントをインストールすることは困難な作業である。現在のところ、装置上のインストールされたイメージを照会して何をインストールすべきかを判断することができる、周知のインテリジェントなイメージ更新サーバインフラストラクチャは存在しない。しかし、そのようなサーバインフラストラクチャを開発することができたとしても、装置のインストール状態情報をサーバと共有することにはプライバシーの問題が伴うことが考えられる。必要とされるのは、多くの更新バージョンと、それらバージョン間の競合と依存性に対処することができる、装置側のデバイス更新に対応する効率的な方式である。
【課題を解決するための手段】
【０００５】
簡潔に述べると、本発明は、（例えば組み込み装置に）インストールするパッケージ群の依存関係を調べるシステムおよび方法に関し、それにより、インストールの候補の最大の群を選択して、可能な限り少ない更新ステップで所与のパッケージの最大のバージョン更新を行うことが可能になり、同時にパッケージの依存性の制約を遵守する。これは、装置の既存パッケージのインストール状態と、インストールするためにキューに入れられた複数のバージョンのパッケージとの両方を知ることによって達成される。
【０００６】
インストールしようとするパッケージはいずれも初めに有効性が確認される。有効性の確認とは、インストールのためにキューにあるパッケージの完全性を検討し、内容を検証し、更新の権限が（署名機構から）判定され、依存関係が判定されるプロセスを言う。一実装では、有効性の確認プロセスの結果は、確認の必要条件を満たすためにインストールすることができるパッケージのリストと、無効の理由を伴う、検証要件の１つまたは複数を満たさないためにインストールすることができないパッケージのリストとの２つのリストからなる。これらのリストは、インストールの順序に並べ替えることができる。
【０００７】
提供される更新バリデータ／妥当性検証プロセスは、一般に、装置にダウンロードされた更新パッケージ群を更新される対象パッケージに基づくグループに編成し、妥当性を検証する。各グループを処理して、装置の既存イメージに適用し、更新を行うことのできる最小かつ最適なパッケージ群を決定する。最小かつ最適なパッケージ群を決定するために、（対象パッケージに相当する）基本ノードから各葉ノードに複数のパスを有することができるグラフとしてパッケージを編成する。このグラフにより、パッケージ群を通る最適なパスを決定することが容易になり、それにより既存のデバイスパッケージを、最低のコストの（加重）更新を有する更新群の中で指定される各パッケージの更新可能な最新バージョンに更新することができる。そのため、グラフを作成すると、そのグラフを探索して（ｗａｌｋ）種々の妥当性検証を行う。さらに、同じバージョンに２つ以上のパスが通っている場合に最小の重み（コスト）を有し、装置を更新することができるより新しいバージョンを見つけることを試みる。
【０００８】
一実装では、妥当性検証プロセスは、例えば更新アプリケーションによって呼び出されるアプリケーションプログラミングインタフェースとしてアクセス可能である。妥当性検証プロセスは、（デバイスマニフェストファイルはパッケージを記述する）各パッケージのデバイスマニフェストファイルを探し、見つかると、そのパッケージが（そのパッケージの代表ノードとして）パッケージグラフに追加される。各マニフェストファイルが処理されると、グラフを処理することにより証明書情報を探す。グラフの処理には、親ノードの証明書チェーンを確認し、対応する枝が有効でなければ親ノードのツリーからその枝を切るステップが含まれる。署名照会を兼ねてグラフの枝とノードが処理されると、重みが最低の枝を判定し、呼び出し元エンティティに返される更新リストにその枝が追加される。
【０００９】
他の利点は、図面を参照して行う以下の詳細な説明から明らかになろう。
【発明を実施するための最良の形態】
【００１０】
（例示的動作環境）
図１に、そのようなハンドヘルドコンピューティング装置１２０の機能構成要素を示す。この構成要素には、プロセッサ１２２、メモリ１２４、ディスプレイ１２６、およびキーボード１２８（物理的なキーボード、仮想キーボード、あるいは両方）が含まれる。オーディオ入力を受信するマイクロフォン１２９がある場合がある。メモリ１２４には、一般に、揮発性メモリ（ＲＡＭなど）と不揮発性メモリ（例えばＲＯＭ、ＰＣＭＣＩＡカードなど）との両方が含まれる。マイクロソフト社のＷｉｎｄｏｗｓ（登録商標）オペレーティングシステムや他のオペレーティングシステムなどのオペレーティングシステム１３０がメモリ１２４に常駐し、プロセッサ１２２で実行される。
【００１１】
１つまたは複数のアプリケーションプログラム１３２がメモリ１２４にロードされ、オペレーティングシステム１３０上で実行される。アプリケーションの例には、電子メールプログラム、スケジュール管理プログラム、ＰＩＭ（個人情報管理）プログラム、ワードプロセッシングプログラム、表計算プログラム、インターネットブラウザプログラムなどが含まれる。ハンドヘルドパーソナルコンピュータ１２０は、メモリ１２４にロードされた通知マネジャ１３４も含むことができる。通知マネジャ１３４は、プロセッサ１２２で実行され、例えばアプリケーションプログラム１３２からの通知要求に対応する。また、後述のように、ハンドヘルドパーソナルコンピュータ１２０は、ハンドヘルドパーソナルコンピュータ１２０をネットワークに接続するのに適したネットワーキングソフトウェア１３６（例えば、ハードウェアドライバなど）とネットワークコンポーネント１３８（例えば、ラジオおよびアンテナ）とを含む。ネットワークへの接続には、通話を行うことが含まれる。
【００１２】
ハンドヘルドパーソナルコンピュータ１２０は、１つまたは複数のバッテリとして実装される電源１４０を有する。電源１４０はさらに、ＡＣアダプタや電力が供給されるドッキングクレードルなど、内蔵バッテリをオーバーライドまたは充電する外部電源を含むことができる。
【００１３】
図１のハンドヘルドパーソナルコンピュータ１２０には、３種類の外部通知機構、すなわち１つまたは複数の発光ダイオード（ＬＥＤ）１４２とオーディオジェネレータ１４４とを図示している。これらの装置は、直接電源１４０に結合されることができ、起動すると、ハンドヘルドパーソナルコンピュータのプロセッサ１２２と他のコンポーネントがバッテリ電力を節減するために電源を停止されていても、通知機構によって指定された時間の間電源の入った状態を保つ。ＬＥＤ１４２は、ユーザが動作を行うまで常に電源が入った状態を保つことが好ましい。現在のバージョンのオーディオジェネレータ１４４は、現在のハンドヘルドパーソナルコンピュータのバッテリ容量に対して消費電力が大きいので、システム休止のとき、または起動後いくらかの時間が経ったとき電源が切れるようにオーディオジェネレータ１４４を構成する。
【００１４】
図に示す基本的なハンドヘルドパーソナルコンピュータは、本発明を実施する上では、データを受信して、そのデータをプログラムした任意の方式で処理することができる携帯電話などの任意の装置と同等であることに留意されたい。
【００１５】
（インストールに有効なソフトウェア更新の判定）
本発明は、一般に、初期のソフトウェアまたはソフトウェア更新が組み込み装置のフラッシュメモリなどの不揮発性メモリに書き込まれる装置を含む、Ｍｉｃｒｏｓｏｆｔ  Ｗｉｎｄｏｗｓ（登録商標）ＣＥ．ＮＥＴに基づく携帯装置などの小型のモバイルコンピューティング装置に記憶されたソフトウェアの更新を対象とする。それでも、本発明は、コンピューティング全般に利益を提供し、したがって、他のコンピューティング装置と、ハードディスクドライブなどの各種のメモリおよび／または他の種類の記憶媒体を含む他の種類のストレージに適用することが可能である。説明を分かりやすくするため、以降の「フラッシュ」という用語は、装置の更新可能なストレージに関するものとして用いるが、任意の記憶機構が装置の更新可能なストレージと同等であることを理解されたい。さらに、「イメージ」という用語は一般に、既存イメージの一部のみが更新される場合であっても、初期のソフトウェアインストールイメージと、その後行われるイメージへのソフトウェア更新との概念を含む。
【００１６】
本発明の一態様によれば、自己完結したセキュアなエンティティの形態において利用可能なソフトウェア更新の適切な下位群が、組み込み装置の不揮発性ストレージに、効率的でインテリジェントな（かつフェールセーフな）方式で適用される。完全に全て入れ替える更新と、以前の更新への変更部分のみを含むことができる更新とを含む、各種のソフトウェア更新を適用することができる。これらのソフトウェア更新は、実行可能コードとデータの両方を含むことができ、実行可能コードは、インストール時の組み込み装置の仮想アドレス空間環境に合わせて個別に設定されている。
【００１７】
モノリシックな更新と異なり、初期の製造イメージが装置にインストールされると、そのイメージの更新を、本発明を介してイメージの個別の部分を更新することによって行うことができる。一実施形態において、これらの個別の部分はパッケージにカプセル化され、ここでパッケージは、イメージファイル（コード、データ、スクリプトなど）の自己記述型の群であり、署名されて、配布のためにパッケージ化されたコンポーネント群から構成されることができる。この実施形態では、オペレーティングシステムイメージ全体は、１つまたは複数のパッケージから作成され、各パッケージを、各パッケージの要件に応じて、個別に、または他のパッケージと合わせて更新することができる。
【００１８】
パッケージは、「標準（ｃａｎｏｎｉｃａｌ）」、「デルタ／差分」および「スーパー」形態を含む各種方式で構成することができ、それぞれの形態は、ソフトウェア更新に関して各種の目的を果たす。例えば、標準パッケージがパッケージ中の各ファイルの完全なコピーを含むのに対し、デルタ／差分パッケージは、そのファイルの以前の改定に基づくバイナリ差分のみを含む１つまたは複数のファイルを含む。デルタ／差分パッケージは、すでにインストールされている以前のバージョンに適用され、したがって通例は他のパッケージと比べてサイズが小さく、ダウンロードのコストとダウンロード時間を減らすために用いられる。スーパーパッケージは、他のパッケージを含み、相互に依存したパッケージを更新する場合など複数のパッケージをダウンロードすることが必要なときに利便を図るものとして用いられる。
【００１９】
標準パッケージは、オペレーティングシステムの機能とメタデータ（例えば特定のアプリケーションの実行可能なコードと、それに関連付けられたデータと構成情報）をパッケージの定義と関連付けることにより、作成プロセス中に生成される。デルタ／差分パッケージは、２つの標準パッケージの内容にバイナリ差分アルゴリズムを適用し、後述するように本発明に従って、デルタ／差分パッケージが、基となる標準パッケージバージョンとの依存関係を考慮することにより標準パッケージから生成される。
【００２０】
本発明の一態様によれば、装置にダウンロードされた更新パッケージ群を編成し、検証する更新バリデータ／妥当性検証プロセスが提供される。このプロセスの最初のステップで、更新する対象パッケージに基づいて、パッケージを一貫性のあるグループに編成する。パッケージをグループに編成すると、各グループを処理して、装置に存在するイメージに適用して更新を行うことができる最小かつ最適なパッケージ群を判定する。一貫性のあるグループは各々、装置上の同じ既存パッケージを対象とするパッケージ群からなる。新しいパッケージは各々、異なる基本バージョンを有し、異なる対象バージョンに適用することができる。
【００２１】
最小かつ最適なパッケージ群を決めるために、基本ノード（対象パッケージに相当する）から各葉ノードに複数のパスを通すことのできるグラフとしてパッケージを編成する。これは、このグラフを構成するパッケージ群を通る最適なパスの決定を容易にする。各グループを処理して、グループ中でインストールすべき最適なパッケージ群を判定し、それにより、更新群の中で指定される各パッケージの更新可能な最新バージョンに既存のデバイスパッケージを更新する。
【００２２】
各種の要素が、この処理の結果に影響する。例えば、依存性または署名を検証することができない場合は、その更新の枝がグラフから除去され、可能な枝があれば別の枝が試みられる。更新すべきデータの量によって、より効率的な枝が決まる。標準パッケージを使用せずに（すなわち、可能性としては複数のパッケージ中の少なくともいくらかのデルタを介して）更新を行う方式はいずれも、標準パッケージの各ファイルを書き込む（例えば明滅する（ｆｌａｓｈ））よりも効率的である可能性が高いので、標準パッケージは有限の重みを有するとみなすことに留意されたい。またはそれに替えて、標準パッケージに関して実質的な重みを有することが可能である。
【００２３】
したがって、ＮＫ（カーネル）パーティションか、またはシステムパーティションに各パッケージのグラフが作成され、パーティションは基本的に異なるファイルシステムであり、異なるプロパティを有することができ、これらのパーティションにパッケージの内容を記憶することができる。これについては、上述の「Creating File Systems Within a File In a Storage Technology-Abstracted Manner」という名称の関連特許出願に概説される。ＮＫパーティションに入れられる内容を有するパッケージは、ＩＭＧＦＳパーティションに内容が入れられるパッケージと同じ種類のパッケージであることに留意されたい。ただし、オペレーティングシステムのロード／ブートシーケンスは、ＮＫパーティションが最初にロードされ、ＮＫパーティションのドライバを使用してＩＭＧＦＳパーティションファイルを見つけ、ロードする点でＩＭＧＦＳパーティションに対するＮＫ更新とシステム更新とで異なる。
【００２４】
各更新パッケージについてのノードが、対応するパッケージのグラフに追加される。次いで、パッケージマニフェストに規定されるバージョンの依存関係を用いてグラフ中のノードを接続し、例えば、あるパッケージのバージョン２がパッケージのバージョン１をアップグレードすることができ、バージョン３がバージョン２をアップグレードすることができ（バージョン１はアップグレードしない）、それにより、バージョン１とバージョン２の間、バージョン２とバージョン３の間にエッジ接続が生じるが、バージョン１とバージョン３の間にはエッジ接続が生じない。上記のバージョン間の関係は一例に過ぎず、この関係は実際には、更新の構築の仕方に依存することを理解されたい。例えば、バージョン１のパッケージから更新されるバージョン３のパッケージを構築することが可能である。一般に、各更新パッケージは、特定のソースバージョンと特定の宛先（最終）バージョンとを有して、そのソースバージョンのみから更新することができる（ソースバージョンは必ずしも宛先バージョンの１つ前のバージョンとは限らない）。標準更新パッケージは、それより前のバージョンであればどのバージョンでも更新できることに留意されたい。
【００２５】
グラフを作成すると、例えば下記のように署名を検証するためなど各種の妥当性検証の目的でそのグラフを探索する。一般に、グラフ探索プロセスでは、各グラフのパスを全探索して、少なくとも同じバージョンに２つ以上のパスが通っている場合に最小の重み（コスト）を有し、装置を更新できるより新しいバージョンを見つけることを試みる。探索する際、あるノードが妥当と認識されない場合には、そのノードとそのパスは基本的にグラフから除去される。
【００２６】
上述の関連特許出願「Self-Describing Software Image Update Components」に記載されるパッケージマニフェストに関して、各パッケージの種類は、そのパッケージの内容と、（依存性情報を含む）より一般的なパッケージの特性の両方を完全に記述する（例えば．ｄｓｍの拡張子を有する）装置側マニフェストファイルを含んでいる。図２に、マニフェストファイルのレイアウトを表す。
【００２７】
下の表から分かるように、デバイスマニフェストのヘッダは、その特定のパッケージの系統を一意に参照するグローバル一意識別子（ＧＵＩＤ）と、特定のパッケージファイルを参照するバージョンを含んでいる。
【００２８】
【表１】
2005182784.tif 000003
【００２９】
【表２】
2005182784.tif 000004
【００３０】
これも見て分かるように、デバイスマニフェストヘッダは、現在のパッケージが依存しているパッケージのリストであり、各パッケージは、次の構造で記述される。
【００３１】
【表３】
2005182784.tif 000005
【００３２】
それぞれがＧＵＩＤで一意に記述されるパッケージはいくつあってもよく、パッケージのすべてのバージョンは同じＧＵＩＤを共有する。パッケージの依存の規則から、あるパッケージの依存するパッケージが、依存性リストで識別されるバージョン番号であるか、それより上の番号であることが求められる。パッケージは、指定されるバージョンがすでに装置にインストールされているか、またはインストールがまだ行われておらず、その依存性が満たされる（したがってそれがインストールされることが確実となる）場合、そのバージョンであるか、またはそのバージョンより上のバージョンである。
【００３３】
一実施形態では独自フォーマットのバイナリファイルである、装置側マニフェストファイルの情報へアクセスするために、共通のパッケージ情報ＡＰＩ（ＰａｃｋａｇｅＩｎｆｏＡＰＩ）が提供される。本発明は、パッケージ情報ＡＰＩを用いて、装置上のパッケージ、およびインストールが可能なためにキューに入っているパッケージの現在のインストール状態を判定する。ＡＰＩは、ビルドシステムＡＰＩならびに組み込み装置ＡＰＩとして存在して、パッケージファイル群のデバイスマニフェストファイルを効果的に解析する。一般に、パッケージ情報ＡＰＩは、装置上の既存のパッケージの列挙、特定のパッケージについてのシャドーオーダー情報（下記で説明する）の列挙、特定パッケージの依存性情報の列挙、および特定のパッケージに属するファイルのファイル名のリストの列挙を行う能力を提供する。パッケージ情報ＡＰＩはまた、ファイルシステムに装置側マニフェストとして記憶されているファイルを開く能力を提供し、特定のパッケージ中から装置側マニフェストを開いて、特定パッケージのパッケージ情報（例えば＿ＰＡＣＫＡＧＥＩＮＦＯ）を取り出す。パッケージ情報ＡＰＩはインターフェースも提供し、そのファイルへのパスを与えられて特定ファイルのＣＲＣ３２の値を計算して、そのパッケージへのパスを与えられて特定パッケージのＣＲＣ３２値を計算する。ＰａｃｋａｇｅＩｎｆｏＡＰＩコンポーネントは、下記で述べるＡＰＩの実装を含む。
【００３４】
以下のＡＰＩ群は、ＰａｃｋａｇｅＩｎｆｏＡＰＩとの外部インタフェースを定義する。データ型が以下のように記述される：
・ＨＰＫＧＥＮＵＭ−特定のパッケージ列挙群を識別するために使用される不透明データ型。
・ＨＰＫＧ−一意のパッケージを表すために使用される不透明データ型。
・ＨＲＥＳＵＬＴ−標準的なＣＯＭリターン型。
・ＲＥＦＧＵＩＤ−ＧＵＩＤ構造への参照。
・ＬＰＴＳＴＲ−ＴＣＨＡＲストリングへのポインタ。
・ＨＦＩＬＥＥＮＴＲＹ−ＦＩＬＥＥＮＴＲＹ情報を呼び出し元プログラムに渡すために用いられる不透明データ型。
【００３５】
次のＡＰＩは、最初の有効な（有効＝＝悪意のある「偽者」でない）パッケージを見つけ、そのパッケージ情報を取り出すのに必要なハンドルを提供する。
HRESULT Pkg_FindFirstPackage(
/*[out]*/HPKGENUM *phPkgEnum,
/*[out]*/HPKG *phPkg);
【００３６】
次のＡＰＩは、次の有効なパッケージを見つけ、そのパッケージ情報を取り出すのに必要とされるハンドルを提供する（Ｓ＿ＦＡＬＳＥは列挙の終わりを意味する）。
HRESULT Pkg_FindNextPackage(
/*[in]*/ HPKGENUM hPkgEnum,
/*[out]*/HPKG *phPkg);
【００３７】
次のＡＰＩは、パッケージ列挙子を閉じる。
HRESULT Pkg_FindClose (/* [in] */ HPKGENUM hPkgEnum);
【００３８】
次のＡＰＩは、装置側マニフェストファイルを「開き」、指定されたＧＵＩＤが、パッケージ情報を取り出すのに必要なハンドルを提供する。これは、ＦｉｎｄＦｉｒｓｔＰａｃｋａｇｅ／ＦｉｎｄＮｅｘｔＰａｃｋａｇｅ  ＡＰＩの使用に代わる方法である。
HRESULT Pkg_OpenPackageByGUID(
REFGUID guidPkg,,
/* [out]*/ HPKG *phPkg);
【００３９】
次のＡＰＩは、装置側マニフェストファイルを「開き」、指定された名前がパッケージ情報を取り出すのに必要なハンドルを供給する。これは、ＦｉｎｄＦｉｒｓｔＰａｃｋａｇｅ／ＦｉｎｄＮｅｘｔＰａｃｋａｇｅ  ＡＰＩの使用に代わる方法である。
HRESULT Pkg_OpenPackageByName(
LPCTSTR szFileName,,
/* [out] */ HPKG *phPkg);
／／（先にＰｋｇ＿ＦｉｎｄＦｉｒｓｔＰａｃｋａｇｅ、Ｐｋｇ＿ＦｉｎｄＮｅｘｔ
／／Ｐａｃｋａｇｅ、またはＰｋｇ＿ＯｐｅｎＰａｃｋａｇｅＢｙＧＵＩＤで開かれ
／／た）パッケージを「閉じる」
HRESULT Pkg_Close (HPKG hPkg);
／／シャドーパッケージを列挙する。Ｓ＿ＦＡＬＳＥは列挙の終了を意味する
HRESULT Pkg_GetNextShadowedPackage (HPKG hPkg, /*
[out] */ GUID *pguidShadowedPkg);
／／指定されたパッケージのＧＵＩＤの依存性の列挙を開始する
HRESULT Pkg_GetFirstDependentPackage(
HPKG hPkg,
/* [out] */ GUID pguidDependentPkg,
/* [out] */ DWORD*
pdwDependentPackageVersion);
／／所与のパッケージのＧＵＩＤ依存性の列挙を続ける。Ｓ＿ＦＡＬＳＥは列挙の終
／／了を意味する。
HRESULT Pkg_GetNextDependentPackage (HPKG hPkg, /*
[out] */ GUID *pguidDependentPkg, /* [out] */ DWORD
*pdwDependentPackageVersion);
／／パッケージにリストされるファイルの列挙を開始する。バッファの大きさが十分
／／でない場合（またはＮＵＬＬの場合）は、ｃｂＳｉｚｅを、最後のＮＵＬ文字も
／／含めて必要とされるバッファサイズに設定する
HRESULT Pkg_GetFirstFile(
HPKG hPkg,
/* [out] */ LPTSTR pszFileName,
/* [in/out] */ DWORD *cbSize);
／／パッケージ中のファイルを列挙する。Ｓ＿ＦＡＬＳＥは列挙の終了を意味する
HRESULT Pkg_GetNextFile (HPKG hPkg, /* [out] */
LPTSTR pszFilename, DWORD cbSize);
／／パッケージの一回限り発生する情報を取得する
HRESULT Pkg_GetPkgInfo (HPKG hPkg, /* [out]*/
PPACKAGEINFO pPackageInfo);
／／指定されたファイルをＤＳＭファイルとしてマッピングする。ファイルがＤＳＭ
／／ファイルでない場合はＥ＿ＦＡＩＬを返す
HRESULT PkgInfo_OpenByName (LPCTSTR szFullName);
／／指定されたパッケージに特定のファイルが含まれているかを判定する。名前付き
／／ファイルがパッケージの一部分である場合は、ＨＦＩＬＥＥＮＴＲＹが非ＮＵＬ
／／Ｌになる
HRESULT Pkg_ContainsFIle(
HPKG hPkg,
LPTSTR szFileName,
/* [out] */ HFILEENTRY ** pFileEntry);
／／指定されたパッケージのヘッダを検証する
HRESULT Pkg_ValidateHeader(
HPKG hPkg,
DWORD dwFileSize);
／／指定されたパッケージのＣＥＲＴデータをバッファにコピーする。バッファの大
／／きさが十分でない、またはＮＵＬＬの場合は、ｐｃｂＢｕｆｆｅｒＳｉｚｅが必
／／要とされるサイズに設定される
HRESULT Pkg_GetCERTData(
HPKG hPkg,
LPVOID lpBuffer,
DWORD* pcbBufferSize);
／／ＣＲＣ計算のＡＰＩ（このＡＰＩを試験で使用して、例えば装置に記憶さ
／／れたＣＲＣに照らして検証する）
HRESULT    Pkg_CalculateFileCRC (
LPCTSTR pszFilename,
/* [out] */ DWORD *pdwCRC);
HRESULT    Pkg_CalculatePackageCRC(
LPCTSTR pszPackageName,
/* [out] */ DWORD *pdwCRC);
／／ＣＡＢを開き、ＤＳＭを抽出し、ＤＳＭをマッピングする。ファイルが存在しな
／／い場合、またはＤＳＭでない場合はＥ＿ＦＡＩＬを返す
FRESULT PkgInfo_ExtractFrom (LPCTSTR szCABFile);
／／ＣＡＢＡＰＩによって返されたＨＣＡＢを得て、ＤＳＭを見つけ、抽出し、マッ
／／ピングする。ファイルが存在しない場合、またはＤＳＭでない場合にはＥ＿ＦＡ
／／ＩＬを返す
HRESULT PkgInfo_ExtractFromHCAB (HCAB hCab);
【００４０】
本発明の一態様によれば、インストールしようとするパッケージはいずれも最初に妥当性を検証される。パッケージの妥当性の検証とは、インストールのためにキューにあるパッケージの完全性を検討し、その内容を検証し、更新の権限を（署名機構から）判定し、そして依存関係を判定するプロセスを言う。一実施形態では、妥当性検証プロセスの結果として、２つのリストを備える。すなわち、検証の要件を満たすのでインストールすることができる１つまたは複数のパッケージのリスト、および各パッケージの無効の理由を伴う、検証の要件の１つまたは複数を満たさないためにインストールすることができない１つまたは複数のパッケージのリストである。これらのリストは、インストールの順序に並び替えられることができる。これらのリストは、デルタが適用される場合、必要とされるファイルがいずれも存在することを保証することに加えて、サイズを検討することによって決め、断片化を減らし、更新を行うのに十分なスペースを確保することができる。図３Ａおよび３Ｂに、妥当性検証プロセス全体を説明するフローチャートを示す。
【００４１】
一実施形態では、妥当性検証プロセスは、例えば更新アプリケーションによって呼び出されるＡＰＩとしてアクセスすることができる。検証しようとする更新のファイル名で呼び出され、そのインストールデータを返す関数と、呼び出し元プログラムが更新パッケージの格納されているディレクトリへパスを通す関数との２つの関数がある。説明を簡略化するために、ここでは、更新は一般にはディレクトリとして考える。
【００４２】
図３Ａおよび３Ｂで、例えば１つまたは複数のインストールすべきパッケージを含んだディレクトリを与えられると、いくつかの試験を行ってパッケージをインストールすることができるか否かを判定する。ステップ３００で、パッケージのディレクトリを取り出し、試験することにより、そのディレクトリが存在するか否か（ステップ３０２）、およびそのディレクトリがファイルを含むか否か（ステップ３０４）を判定する。ディレクトリが存在しない場合、またはファイルを含まない場合は、ステップ３０６を介してエラーメッセージが返され、妥当性検証プロセスは終了する。
【００４３】
ディレクトリが存在し、少なくとも１つのファイルがその中にある場合、ステップ３０８から３２２がループして各ファイルに繰返し行われ、各ファイルに試験を行う。ステップ３１０でそのファイルが適切なファイル型のパッケージファイルであるかどうかを試験する。適切なファイル型である場合は、ステップ３１２で、そのパッケージから装置側マニフェストファイル（ＤＳＭ）を抽出することを試みる。より詳細には、一実施形態では、ＣＡＢＡＰＩを使用して、ＣＡＢファイルとしてファイルを開くことを試みる。それが成功した場合は、ＤＳＭの抽出を試みる。ファイルをＣＡＢファイルとして読み込めない場合は、ＣＡＢファイルとして指定されたファイル名を読み込めなかったことを示すＨＲＥＳＵＬＴエラーコードとともに、その名前が不良パッケージのリストに記録される。ＤＳＭを抽出することができない場合は、そのＣＡＭにＤＳＭがなかったことを表すＨＲＥＳＵＬＴエラーコードとともに、そのファイルの名前が不良パッケージのリストに記録される。ＣＡＢファイルでない場合、またはデバイスマニフェストファイルが見つからないとステップ３１４で評価される場合は、残るパッケージファイルがなくなるまで、次のパッケージファイルを選択して、試験する。
【００４４】
装置側マニフェストファイルが見つかると、ステップ３１６を介してそのパッケージを（例えばそのパッケージを代表するノードとして）パッケージグラフに追加する。ステップ３１８の試験が成功しない場合は、ノードを作成できなかった結果として妥当性検証プロセスは（ステップ３２０で）終了する。
【００４５】
各ファイルが処理されたとき、ディレクトリ内の少なくとも１つのファイルがデバイスマニフェストファイルを有するパッケージファイルであった場合にはグラフは空でないはずである。グラフが空の場合（ステップ３２４）、どのファイルも妥当なパッケージではなく、プロセスはステップ３２６で終了する。そうでない場合、プロセスは図３Ｂのステップ３２８に続く。
【００４６】
図３Ｂのステップ３２８（とステップ３４８と）は、グラフ中の各枝を処理するループに相当し、ステップ３３０（とステップ３４４と）は、現在処理中の枝の各ノードを処理する入れ子ループに相当する。一般に、この処理では証明書情報を探し、これには、ステップ３３２と３３４を介して親ノードの証明書チェーンを調べ、見つからない場合はステップ３３６で親ノードからツリーの対応する枝を切ることが含まれる。
【００４７】
証明書情報が見つかった場合は、ステップ３３８および３４０を介して署名を検証する。証明書情報が見つかった場合は、（同じ結果を得る２つ以上のパスが通っている場合、他のパッケージと比較してどのパッケージを用いるかを決めるので、効率性を評価するために用いられる）重みデータをステップ３４２でノードに基づいて枝に加え、ステップ３４４を介して、残るノードがなくなるまで次のノードが選択される。加重情報は、パッケージが読み込まれるときに計算され、パスが作成されるときにそのパスの重みに加えられる。初期のグラフ構造は、パッケージが妥当であり、したがって署名情報を更新群内のすべてのパッケージに対して検証するのではなく、プロセスが使用したいパッケージについてのみ検証すればよいという前提の下で機能し、この前提により署名の検証回数が減る場合もある。ステップ３４０で署名が有効でない場合、ステップ３４６で現在のノードからその枝を切る。
【００４８】
このようにしてグラフの枝とノードの処理が完了すると、ステップ３５０で表すようにグラフを探索して、加重が最も低い枝を見つけ、返される更新リストにその枝を追加する。
【００４９】
本発明の一態様によれば、この妥当性検証プロセスは、インストールするのに妥当な最大の依存ソフトウェア更新の判定を可能にするバージョン依存性計算の要件を提供する。図４のブロック図で表すように、妥当性検証プロセス４０２は、更新整理コンポーネント４０４を含む、判定を行う各種コンポーネントに関連する（あるいはそれらのコンポーネントを含むと考えることができる）。更新整理コンポーネント４０４は、更新群４０８として装置にダウンロードされたパッケージ群のグラフ４０６を作成し、パッケージマニフェスト４１０から依存性情報を抽出して、他のパッケージ４１２が正しいバージョンで装置に（またキュー内のインストールパッケージ４１４に）存在することを確かめる。また、更新整理コンポーネント４０４は、既存のデバイスマニフェストファイル４１０と新たなデバイスマニフェストファイル４１２を解析して、依存性の要件に基づいてパッケージのインストール順序を生成する役割を担う。
【００５０】
図５Ａおよび５Ｂは、妥当性検証プロセスの更新整理プロセスを説明するフローチャートである。一般に、以前にインストールされたパッケージに対応する各既存のデバイスマニフェストファイルに対して、何らかの初期化および妥当性の検証を行うと（ステップ５００、５０２、５０４）、装置で保持されているパッケージのデバイスマニフェストファイルで定義されるように、そのパッケージを表すパッケージグラフが更新整理プロセスによって作成される。妥当性検証プロセスでは、パッケージ情報ＡＰＩを使用して既存のデバイスマニフェストを列挙できることに留意されたい。ステップ５０６で更新ディレクトリ内のパッケージがそのパッケージに適した基本グラフに加えられる。但し、適したグラフが存在しない場合、新しいパッケージ用のグラフが作成されるが、このグラフは非基本グラフとしてタグ付けされる。ノードは、マニフェストおよびパッケージに基づく情報を含んでおり、追加されると、バージョン情報を求めてグラフ内の他のノードを参照して、そのパッケージが更新することのできるバージョンに基づいて接続するノードを判定する。グラフに追加されるパッケージを更新することが可能な孤立ノードがグラフにある場合があることに留意されたい。グラフ作成プロセスは、グラフを構成するノードを探索し、新しいノードを更新することができる既存のノードがグラフに存在すれば適切なリンクを追加する。
【００５１】
インストールすべきパッケージが追加されると、パスを評価し、ファイルの妥当性の検証を行うために各グラフが探索される。グラフ中のパスは、ノードがグラフに追加されるときにリアルタイムで作成されることに留意されたい。下記で図６を参照して述べるように、パッケージが読み込まれると、更新バリデータは、各グラフを探索して、グラフに利用できるパス群から最適なパスを探す。グラフに用いるパスが選択されると、そのパス中のノードについての署名が検証される。特定ノードの署名が有効であると確認できない場合、無効なノードから始まるそのパスが切断され、次いでパス選択プロセスがそのグラフについて再度実行される。このプロセスは、あるパス中のノードが有効な署名を有すると判定されるか、または所与のグラフについて処理するパスがそれ以上なくなるまで反復される。
【００５２】
ステップ５１４で処理が成功した場合、更新整理プロセスは、図５Ｂのステップ５１８を続け、作成された各パッケージグラフについて、そのパッケージがＮＫパーティションの一部である場合は、ステップ５２２を介してパッケージ情報をＮＫリスト４１６（図４）に追加する。パッケージがＮＫパーティションの一部でない場合は、そのパッケージを他のリスト４１８（図４）に加える。すべてのパッケージグラフが処理されると、ステップ５３２を介して他のリスト４１８をＮＫリスト４１６に付け足す。この付け足しが成功したとステップ５３４で評価される場合、ＮＯＥＲＲＯＲ状態は、付け足されたＮＫリスト４１６と無効リスト４２０とともに戻される。
【００５３】
妥当性検証プロセス４０２の別の部分は、更新グラフを構築することを対象とし、装置の更新を構成するパッケージのグラフを作成する役割を担う更新グラフコンポーネント４２２によって達成される。装置にすでに存在する各パッケージを使用して独立グラフの基本ノードを作成する。一実施形態では、各パッケージは、パッケージノードオブジェクトによって表される。本実施形態では、各ノードオブジェクトは、ただ１つのパッケージグラフオブジェクトに含まれることに留意されたい。
【００５４】
図６にグラフ作成プロセスを示す。一般に、更新グラフ４２４（図４）は、ノードオブジェクト４３６の配列とエッジオブジェクト４２８の配列を含む２つの配列を含んでいる。エッジオブジェクトはノードを相互に接続する。新しいパッケージがグラフに追加されると、ステップ６００に表すように、そのパッケージについてのノードオブジェクトが作成され、ノード配列４２６に追加される。ステップ６０２でノードが作成されないと評価される場合、このプロセスは失敗する。
【００５５】
ステップ６０６および６０８で、そのパッケージに対応する既存のグラフを探す。グラフが見つからない場合、そのパッケージは新しいパッケージであることになり、ステップ６１０でそのパッケージに対してグラフが作成される（そしてステップ６１２を介してそのグラフが適切に作成されたことを保証する）。グラフの作成が成功すると、ステップ６１６でその新しいグラフが戻され、それ以外の場合は失敗が戻される。
【００５６】
ノードの作成が成功し、そのパッケージにグラフが見つかると、ステップ６０８からステップ６１８〜６３０を介してステップ６１８に分岐する。ノード配列内の各ノードについて、新しいノードの基本バージョンがその既存ノードのバージョン番号と一致する場合、更新グラフ４２４（図４）にエッジオブジェクトが作成されて、配列４２８に追加される。この状態で、エッジオブジェクトは、既存ノードをソースに、新しいノードをシンク（ｓｉｎｋ）に指定する。代わりに、既存ノードの基本バージョンが新しいノードのバージョン番号と一致する場合は、新しいノードをソースに、既存ノードをシンクに指定するエッジオブジェクトが作成される。
【００５７】
追加時に、どの既存ノードとも接続のないパッケージが追加されることが可能であることに留意されたい。この状況は、２つの結果の１つを通じて調整される。すなわち、（ａ）そのパッケージノードを介して到達することができるノードがなく、かつ更新内の他のパッケージノードを介してそのパッケージノードに到達するパスがない場合。この状況では、ノードは不良とマークされ、無効の更新リストに入れられる。（ｂ）後に追加されるパッケージがそのノードに接続する。この状況では、下記で図７Ａおよび７Ｂを参照して説明するように、ノードは、グラフを探索する段階で処理される。
【００５８】
さらに、２つのパッケージが同じ対象バージョンを有する場合には、２つの装置側マニフェストファイルが比較されることに留意されたい。２つのファイルが等しくない場合、両方のノードを無効ノードとする。どの所与のパッケージについても特定バージョンの装置側マニフェストファイルは、所与のパッケージを特定バージョンに更新するすべてのパッケージにおいて同じであるべきであるからである。
【００５９】
妥当性検証プロセスの別の部分として、更新グラフウォーカーコンポーネント４３０が、恐らくはグラフ中の複数のパスに基づいて、そのパッケージの最も高い最終バージョン番号を判定するために各パッケージグラフを横断する。探索する際、更新グラフウォーカーコンポーネント４３０は、グラフ中のパッケージのデジタル署名が有効か検証する。署名の検証の結果が無効な場合、その点でグラフが切断されて、無効なノードに接続するエッジがいずれも除去される。
【００６０】
最も高いバージョン番号が判定されると、依存するＧＵＩＤに一致するパッケージグラフを更新グラフ４２４に問い合わせることによって、そのノードの依存性が検証される。新しい更新グラフが確認されていない場合、更新グラフウォーカーは、新しいパッケージグラフに対して探索プロセスを開始する。依存性を満たすことができない場合、その枝は切られ、新しい枝が試みられる。切られた枝のノードを接続するエッジは除去される。すべての可能性のある枝を試みて、依存性の要件を満たすことができない場合、グラフ内のそれらのノードによって表されるパッケージは無効更新リストに移される。
【００６１】
図７Ａおよび７Ｂに横断プロセスの論理を示す。この横断プロセスは、グラフの基本ノードから開始する。ステップ７０２〜７０６によって表されるように、グラフの各エッジについて、そのエッジがそのノードをソースとして有するか否かを判定する（ステップ７０４）。そのノードに関連付けられたエッジがない場合は、終端ノードが検出されたことになり、終端ノードがステップ７０８〜７１８で扱われる。一般に、これらのステップでは、ノードのバージョン番号をグラフのバージョン番号と比較して（ステップ７１４）、ノードバージョンがグラフバージョンより高い場合、ステップ７１６でグラフバージョンをノードバージョンに更新して、プロセスは終了する（エラーは戻されない）。
【００６２】
代わりに、ステップ７０４でエッジがあったと判断された場合、プロセスは図７Ｂのステップ７２４に分岐してそのエッジにＣＥＲＴチェーンがあるかどうかを調べる。ステップ７２４でＣＥＲＴチェーンがないと判断された場合は、そのノードに対応する装置側マニフェストファイルからＣＥＲＴブロックを入手する。装置側マニフェストファイルにＣＥＲＴブロックがない場合は、ステップ７３０でノードが不良とマークされ、プロセスが戻ることに留意されたい。
【００６３】
ステップ７２４またはステップ７２８でＣＥＲＴデータがある場合、プロセスはステップ７３４に進んでそのデータを解読する。この解読が失敗した場合、ステップ７３０でノードを不良ノードとし、プロセスは戻る。
【００６４】
そうでない場合、エッジの終端にシンクノードを見つける試みがステップ７３８で行われ、ステップ７４０でシンクノードがないか否かについての試験が行われる。但し、シンクノードがない場合は、グラフの整合性エラーが記録され、プロセスはステップ７４２を介して戻る。
【００６５】
シンクノードが見つかった場合は、ＣＥＲＴデータを使用してそのシンクノードの妥当性を検証する（ステップ７４４）。シンクノードの署名が有効であると確認された場合、その関数が再帰的に呼び出され、ステップ７４８でシンクノードを渡し、図７Ａのステップ７２０に戻る。シンクノードが無効の場合は、そのエッジを不良エッジとする。
【００６６】
このようにして、最大の更新群が判定されて、有効な更新のリストとともに、順序付けられた更新リストとして戻される。これは、デバイスパッケージバージョンを最大にする最小数のパッケージに相当することができる。
【００６７】
上述の詳細な説明から分かるように、装置側のデバイス更新を扱う機構を提供する。この機構は、多数の更新バージョンと、それらバージョン間の矛盾と依存性に対処して、適用されるとデバイスパッケージのバージョンを最新にする最小数の有効パッケージを提供する。
【００６８】
本発明には各種の変更および代替の構成が可能であるが、その特定の例示的な実施形態を図面に示し、上記で詳細に説明した。ただし、本発明をここに開示される特定の形態に限定する意図はなく、反対に、本発明の趣旨および範囲内に該当するすべての変更、代替の構成、および同等なものを包含するものとすることを理解されたい。
【図面の簡単な説明】
【００６９】
【図１】本発明を組み込むことができるコンピュータシステムを概略的に表すブロック図である。
【図２】本発明の一態様によるパッケージの依存性情報を得るために使用されるマニフェストファイルの図である。
【図３Ａ】本発明の一態様による、依存性情報の処理を含む更新の妥当性検証プロセスを行う流れ図である。
【図３Ｂ】本発明の一態様による、依存性情報の処理を含む更新の妥当性検証プロセスを行う流れ図である。
【図４】本発明の一態様による更新の妥当性検証プロセスを行う各種機構を示すブロック図である。
【図５Ａ】本発明の一態様による、依存性情報の処理を含む更新の順序付けプロセスを行う流れ図である。
【図５Ｂ】本発明の一態様による、依存性情報の処理を含む更新の順序付けプロセスを行う流れ図である。
【図６】本発明の一態様による、パッケージの依存性を評価するためのグラフを作成する流れ図である。
【図７Ａ】本発明の一態様による、パッケージ更新グラフの横断を行う流れ図である。
【図７Ｂ】本発明の一態様による、パッケージ更新グラフの横断を行う流れ図である。
【符号の説明】
【００７０】
１２０  ハンドヘルドコンピューティング装置
２０２  マニフェストファイルのレイアウト
【図１】
2005182784.tif 000006
【図２】
2005182784.tif 000007
【図３Ａ】
2005182784.tif 000008
【図３Ｂ】
2005182784.tif 000009
【図４】
2005182784.tif 000010
【図５Ａ】
2005182784.tif 000011
【図５Ｂ】
2005182784.tif 000012
【図６】
2005182784.tif 000013
【図７Ａ】
2005182784.tif 000014
【図７Ｂ】
2005182784.tif 000015
【外国語明細書】
2005182784000001.pdf