(57)【要約】プログラムが装置のメモリに収まらない場合、本システム、方法、コンピュータプログラムプロダクトはプログラム全体を分割する。パーティションの実行直前に、必要に応じて、サーバから埋込み型装置に最小安全プログラムパーティションをダウンロードする。プログラムの制御流れ挙動に関する情報が漏洩しないように、プログラムのコードおよびデータを分割する。このため、攻撃者は、サーバから装置にダウンロードされるプログラムパーティションを観察することによって、プログラムがどのように分岐するか、また、プログラムの制御流れがどのような状況かを推測することはできない。この不正使用防止特性は、感知可能情報の保持、および／または、金融取引等の重要な計算を行うことができるスマートカード等の安全埋込み型装置にとって有用である。
2005528689.tif 000002
【特許請求の範囲】
【請求項１】
装置に送信するプログラムを分割する方法において、
プログラムを解析することによって、前記プログラムの少なくとも一つの再帰関数および少なくとも一つの非再帰関数を識別することと、
前記再帰関数および非再帰関数の識別を用いて、プログラムを複数のプログラムパーティションに分割することとを備え、
前記複数のプログラムパーティションの少なくとも一つを装置に送信するとき、前記複数のプログラムパーティションが前記プログラムの制御流れ情報を漏らさない、
プログラム分割方法。
【請求項２】
さらに、前記複数のプログラムパーティションの少なくとも一つを装置に送信し、実行することを備える、請求項１に記載のプログラム分割方法。
【請求項３】
コンピュータプログラムコードによって、前記プログラムの解析を行う、請求項１に記載のプログラム分割方法。
【請求項４】
コンピュータプログラムコードによって、プログラムを複数のプログラムパーティションに分割する、請求項１に記載のプログラム分割方法。
【請求項５】
さらに、前記複数のプログラムパーティションの少なくとも二つを併合して併合プログラムパーティションを生成することを備える、請求項１に記載のプログラム分割方法。
【請求項６】
さらに、前記複数のプログラムパーティションの少なくとも二つを併合して併合プログラムパーティションを生成する前に、装置のメモリ容量を決定することを備える、請求項５に記載のプログラム分割方法。
【請求項７】
さらに、前記併合プログラムパーティションを装置に送信することを備える、請求項５に記載のプログラム分割方法。
【請求項８】
前記再帰関数および非再帰関数の前記識別を用いてプログラムを分割することが、前記再帰関数および非再帰関数の前記識別を用いてプログラムを複数の最小安全プログラムパーティションに分割することを備える、請求項１に記載のプログラム分割方法。
【請求項９】
前記最小安全プログラムパーティションのいずれかをさらに分割することによって制御情報を決定することができるように、最小安全パーティションを分割する、請求項８に記載のプログラム分割方法。
【請求項１０】
再帰関数または非再帰関数の実行時、各最小安全パーティションを一定の順序で装置に送信する、請求項８に記載のプログラム分割方法。
【請求項１１】
さらに、前記最小安全プログラムパーティションの少なくとも二つを併合して安全併合プログラムパーティションを作成することを備える、請求項８に記載のプログラム分割方法。
【請求項１２】
さらに、前記装置に、前記複数のプログラムパーティションの少なくとも一つをキャッシュするために割り当てられたメモリを確保することを備える、請求項１に記載のプログラム分割方法。
【請求項１３】
装置にダウンロードするプログラムを分割する方法において、
装置の必要メモリを超える大きさのプログラムを供給することと、
プログラムを解析することによって、前記プログラムの少なくとも一つの再帰関数および少なくとも一つの非再帰関数を識別することと、
前記再帰関数および非再帰関数の識別を用いて、プログラムを複数のプログラムパーティションに分割することと、
プログラム全体が装置に常駐することなく、前記プログラムの実行中のコードおよびデータが装置に完全に常駐するように、前記複数のプログラムパーティションの少なくとも一つを装置に送信することと、
を備えるプログラム分割方法。
【請求項１４】
コンピュータプログラムコードによって、前記プログラムの解析を行う、請求項１３に記載のプログラム分割方法。
【請求項１５】
コンピュータプログラムコードによって、プログラムを複数のプログラムパーティションに分割する、請求項１３に記載のプログラム分割方法。
【請求項１６】
前記複数のプログラムパーティションの少なくとも二つを併合して併合プログラムパーティションを生成することと、
前記併合プログラムパーティションを前記装置に送信することと、
をさらに備える請求項１３に記載のプログラム分割方法。
【請求項１７】
さらに、前記複数のプログラムパーティションの少なくとも二つを併合する前に、装置のメモリ容量を識別することを備える、請求項１６に記載のプログラム分割方法。
【請求項１８】
前記再帰関数および非再帰関数の前記識別を用いてプログラムを分割することが、前記再帰関数および非再帰関数の前記識別を用いてプログラムを複数の最小安全プログラムパーティションに分割することを備える、請求項１３に記載のプログラム分割方法。
【請求項１９】
前記最小安全プログラムパーティションのいずれかをさらに分割することによって、プログラムパーティションを装置に送信するとき、前記プログラムの制御情報を決定することができるように、最小安全パーティションを分割する、請求項１８に記載のプログラム分割方法。
【請求項２０】
再帰関数または非再帰関数の実行時、各安全パーティションを一定の順序で装置に送信する、請求項１８に記載のプログラム分割方法。
【請求項２１】
さらに、前記最小安全プログラムパーティションの少なくとも二つを併合して安全併合プログラムパーティションを作成することを備える請求項１８に記載のプログラム分割方法。
【請求項２２】
前記少なくとも二つの最小安全プログラムパーティションを併合することによって、装置に送信するパーティションの数を減らす、請求項２１に記載のプログラム分割方法。
【請求項２３】
さらに、前記装置に、前記複数のプログラムパーティションの少なくとも一つをキャッシュするために割り当てられたメモリを確保することを備える、請求項１３に記載のプログラム分割方法。
【請求項２４】
装置にプログラムパーティションを記憶する方法において、
大きすぎて装置に常駐できないプログラムの実行可能部分を備える少なくとも一つのプログラムパーティションをサーバに要求することと、
前記少なくとも一つのプログラムパーティションを前記装置のメモリに記憶することと、
前記少なくとも一つのプログラムパーティションを前記装置で実行することと、
を備えるプログラムパーティション記憶方法。
【請求項２５】
さらに、前記少なくとも一つのプログラムパーティションを実行した直後に、前記少なくとも一つのプログラムパーティションを前記メモリから除去することによって、メモリに追加コンテンツを記憶できるようにすることを備える、請求項２４に記載のプログラムパーティション記憶方法。
【請求項２６】
さらに、前記少なくとも一つのプログラムパーティションを再実行することを前記装置が知らない場合、前記少なくとも一つのプログラムパーティションを前記メモリから除去することを備える、請求項２４に記載のプログラムパーティション記憶方法。
【請求項２７】
さらに、前記少なくとも一つのプログラムパーティションを装置に再送信することを備える、請求項２５に記載のプログラムパーティション記憶方法。
【請求項２８】
装置にプログラムパーティションを記憶する方法において、
プログラムを解析することによって、前記プログラムの少なくとも一つの再帰関数および少なくとも一つの非再帰関数を識別することと、
前記再帰関数および非再帰関数の識別を用いて、プログラムを複数のプログラムパーティションに分割することと、
プログラムの実行に必要なプログラムブロックに対応するパーティションのみを装置に記憶することと、
を備えるプログラムパーティション記憶方法。
【請求項２９】
パーティションの記憶が、プログラムの実行に必要なプログラムブロックに対応するパーティションのみを選択的に記憶することを備え、この選択的記憶が装置によって行われる、請求項２８に記載のプログラムパーティション記憶方法。
【請求項３０】
装置に送信するプログラムを分割するコンピュータプログラムプロダクトにおいて、
前記コンピュータプログラムプロダクトが、
コンピュータ可読コード手段が埋め込まれたコンピュータ使用可能媒体を備え、
前記コンピュータ可読コード手段が、
プログラムを解析することによって、前記プログラムの少なくとも一つの再帰関数および少なくとも一つの非再帰関数を識別するコンピュータ可読プログラムコード手段と、
前記再帰関数および非再帰関数の識別を用いて、プログラムを複数のプログラムパーティションに分割するコンピュータ可読プログラムコード手段とを備え、
前記複数のプログラムパーティションの少なくとも一つを装置に送信するとき、前記複数のプログラムパーティションが前記プログラムの制御流れ情報を漏らさない、
プログラム分割コンピュータプログラムプロダクト。
【請求項３１】
さらに、前記複数のプログラムパーティションの少なくとも一つを装置に送信し実行するコンピュータ可読プログラムコード手段を備える、請求項３０に記載のプログラム分割コンピュータプログラムプロダクト。
【請求項３２】
さらに、前記複数のプログラムパーティションの少なくとも二つを併合して併合プログラムパーティションを生成するコンピュータ可読プログラムコード手段を備える、
請求項３０に記載のプログラム分割コンピュータプログラムプロダクト。
【請求項３３】
さらに、前記複数のプログラムパーティションの少なくとも二つを併合する前に、装置のメモリ容量を識別するコンピュータ可読プログラムコード手段を備える、請求項３２に記載のプログラム分割コンピュータプログラムプロダクト。
【請求項３４】
さらに、前記併合プログラムパーティションを装置に送信するコンピュータ可読プログラムコード手段を備える、請求項３２に記載のプログラム分割コンピュータプログラムプロダクト。
【請求項３５】
前記再帰関数および非再帰関数の前記識別を用いてプログラムを分割するコンピュータ可読プログラムコード手段が、前記再帰関数および非再帰関数の前記識別を用いてプログラムを複数の最小安全プログラムパーティションに分割するコンピュータ可読プログラムコード手段を備える、請求項３０に記載のプログラム分割コンピュータプログラムプロダクト。
【請求項３６】
前記最小安全プログラムパーティションのいずれかをさらに分割することによって制御流れ情報を決定することができるように、最小安全パーティションを分割する、請求項３５に記載のプログラム分割コンピュータプログラムプロダクト。
【請求項３７】
再帰関数または非再帰関数の実行時、各安全パーティションを一定の順序で装置に送信する、請求項３５に記載のプログラム分割コンピュータプログラムプロダクト。
【請求項３８】
さらに、前記最小安全プログラムパーティションの少なくとも二つを併合して安全併合プログラムパーティションを作成するコンピュータ可読プログラムコード手段を備える、請求項３５に記載のプログラム分割コンピュータプログラムプロダクト。
【請求項３９】
さらに、前記複数のプログラムパーティションの少なくとも一つをキャッシュするために割り当てられたメモリを前記装置に確保するコンピュータ可読プログラムコード手段を備える、請求項３０に記載のプログラム分割コンピュータプログラムプロダクト。
【請求項４０】
メモリが限られた装置にプログラムの一部のみをダウンロードし該装置で該プログラム部分を実行するように、プログラムを分割するシステムにおいて、
前記システムが、
装置の必要メモリを超える大きさのプログラムが常駐するメモリを含むサーバと、
前記サーバと通信する装置とを備え、
前記サーバが、
プログラムを解析することによって、前記プログラムの少なくとも一つの再帰関数および少なくとも一つの非再帰関数を識別し、
前記再帰関数および非再帰関数の識別を用いて、プログラムを複数のプログラムパーティションに分割し、
前記複数のプログラムパーティションの少なくとも一つを装置に送信することによって、
プログラム全体が装置に常駐することなく、前記プログラムの実行中の部分が装置に完全に常駐するように動作することができる、
プログラム分割システム。
【請求項４１】
前記サーバが、前記複数のプログラムパーティションの少なくとも一つを受信するのに使用できる前記装置のメモリを決定するように動作することができる、請求項４０に記載のプログラム分割システム。
【請求項４２】
前記サーバが、前記複数のプログラムパーティションの少なくとも二つを併合して、装置に送信する併合パーティションを作成することによって、装置に送信する個々のパーティションの数を減らすように動作することができる、請求項４０に記載のプログラム分割システム。
【請求項４３】
前記装置がスマートカードを備える、請求項４０に記載のプログラム分割システム。
【請求項４４】
セキュリティ装置にプログラムの一部のみをダウンロードするようにプログラムを分割するシステムにおいて、
前記システムが、
プログラムを記憶し、プログラムを複数のプログラムパーティションに分割するように動作することができるサーバと、
前記サーバと通信し、前記サーバから前記複数のプログラムパーティションの少なくとも一つを受信する装置とを備え、
前記複数のプログラムパーティションの少なくとも一つを装置に送信するとき、前記複数のプログラムパーティションが前記プログラムの制御流れ情報を漏らさない、
プログラム分割システム。
【請求項４５】
前記サーバが、前記複数のプログラムパーティションの少なくとも一つを受信するのに使用できる前記装置のメモリを決定するように動作することができる、請求項４４に記載のプログラム分割システム。
【請求項４６】
前記サーバが、前記複数のプログラムパーティションの少なくとも二つを併合して、装置に送信する併合パーティションを作成することによって、装置に送信する個々のパーティションの数を減らすように動作することができる、請求項４４に記載のプログラム分割システム。
【請求項４７】
前記装置がスマートカードを備える、請求項４４に記載のプログラム分割システム。
【請求項４８】
セキュリティ装置にプログラムの一部のみをダウンロードするようにプログラムを分割するコンピュータプログラムプロダクトにおいて、
前記コンピュータプログラムプロダクトが、
コンピュータ可読コード手段が埋め込まれたコンピュータ使用可能媒体を備え、
前記コンピュータ可読コード手段が、
装置の必要メモリを超える大きさのプログラムを供給するコンピュータ可読プログラムコード手段と、
プログラムを解析することによって、前記プログラムの少なくとも一つの再帰関数および少なくとも一つの非再帰関数を識別するコンピュータ可読プログラムコード手段と、
前記再帰関数および非再帰関数の識別を用いて、プログラムを複数のプログラムパーティションに分割するコンピュータ可読プログラムコード手段と、
プログラム全体が装置に常駐することなく、前記プログラムの実行中の部分が装置に完全に常駐するように、前記複数のプログラムパーティションの少なくとも一つを装置に送信するコンピュータ可読プログラムコード手段とを備える、
プログラム分割コンピュータプログラムプロダクト。
【請求項４９】
前記複数のプログラムパーティションの少なくとも二つを併合して併合プログラムパーティションを生成するコンピュータ可読プログラムコード手段と、
前記併合プログラムパーティションを前記装置に送信するコンピュータ可読プログラムコード手段とをさらに備える、
請求項４８に記載のプログラム分割コンピュータプログラムプロダクト。
【請求項５０】
さらに、装置を調べて、前記複数のプログラムパーティションの少なくとも二つを併合する前に装置のメモリ容量を決定するコンピュータ可読プログラムコード手段を備える、請求項４８に記載のプログラム分割コンピュータプログラムプロダクト。
【請求項５１】
前記再帰関数および非再帰関数の前記識別を用いてプログラムを分割するコンピュータ可読プログラムコード手段が、前記再帰関数および非再帰関数の前記識別を用いてプログラムを複数の最小安全プログラムパーティションに分割するコンピュータ可読プログラムコード手段を備える、請求項４８に記載のプログラム分割コンピュータプログラムプロダクト。
【請求項５２】
前記最小安全プログラムパーティションのいずれかをさらに分割することによって、プログラムパーティションを装置に送信するとき、前記プログラムの制御情報を決定することができるように、最小安全パーティションを分割する、請求項５１に記載のプログラム分割コンピュータプログラムプロダクト。
【請求項５３】
再帰関数または非再帰関数の実行時、各安全パーティションを一定の順序で装置に送信する、請求項５１に記載のプログラム分割コンピュータプログラムプロダクト。
【請求項５４】
さらに、前記最小安全プログラムパーティションの少なくとも二つを併合して安全併合プログラムパーティションを作成するコンピュータ可読プログラムコード手段を備える、請求項５１に記載のプログラム分割コンピュータプログラムプロダクト。
【請求項５５】
前記少なくとも二つの最小安全プログラムパーティションの併合によって装置に送信する個々のパーティションの数を減らすように、前記安全併合プログラムパーティションを装置に送信する、請求項５４に記載のプログラム分割コンピュータプログラムプロダクト。
【請求項５６】
さらに、前記複数のプログラムパーティションの少なくとも一つをキャッシュするために割り当てられたメモリを前記装置に確保するコンピュータ可読プログラムコード手段を備える、請求項４８に記載のプログラム分割コンピュータプログラムプロダクト。
【請求項５７】
装置にダウンロードするプログラムを分割する方法において、
プログラムを解析することによって、前記プログラムの少なくとも一つの再帰関数および少なくとも一つの非再帰関数を識別し、
前記再帰関数および非再帰関数の識別を用いて、プログラムを複数のプログラムパーティションに分割し、
装置が要求する前記複数のプログラムパーティションの少なくとも一つを識別し、これにより、前記少なくとも一つのプログラムパーティションを装置に送信すると、プログラム全体が装置に常駐することなく、前記少なくとも一つのプログラムパーティションがプログラムの関数を能動的に実行し、
送信されたパーティションの実行に必要な必要最低限のプログラムデータを識別し、識別された必要最低限のプログラムデータを装置にダウンロードする
ことを備えるプログラム分割方法。
【請求項５８】
一部のみが装置で実行するプログラムを供給し、
プログラムを複数の最小安全パーティションに分割し、
前記複数の最小安全パーティションの少なくとも一つに関連する少なくとも一つの呼び出し位置を識別し、
識別された前記少なくとも一つの呼び出し位置を用いて、装置で頻繁に実行される関数集合を識別し、
識別された関数集合のみを装置に記憶する
ことを備える装置性能最適化方法。
【請求項５９】
装置で頻繁に実行される関数集合を識別するステップにおいて、トレース分析を用いて、各呼び出し位置毎に、頻繁に実行される関数集合を識別することを備える、請求項５８に記載の装置性能最適化方法。
【請求項６０】
さらに、少なくとも一つの呼び出し位置を識別することによって、装置が実行可能関数を重複してロードしないようにすることを備える、請求項５８に記載の装置性能最適化方法。
【請求項６１】
プログラムを解析することによって、前記プログラムの少なくとも一つの再帰関数および少なくとも一つの非再帰関数を識別することと、
前記再帰関数および非再帰関数の識別を用いて、プログラムを複数のプログラムパーティションに分割することと、
装置のメモリを理想的なコードセグメント成分およびデータセグメント成分に分割するように勧告を装置に送信することとを備え、
前記複数のプログラムパーティションの少なくとも一つを装置に送信するとき、前記複数のプログラムパーティションが前記プログラムの制御流れ情報を漏らさない、
装置性能最適化方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、一般に、プログラム分割（partitioning）システム、プログラム分割方法、プログラム分割コンピュータプログラムプロダクトに関する。特に、本発明は、メモリが限られた装置でプログラムパーティション（partition）が動作するように、また、その装置にプログラムパーティションをダウンロードする際、不正使用防止性を確保するように、プログラムのコードおよびデータを分割するシステム、方法、コンピュータプログラムプロダクトに関する。
【０００２】
背景技術
不正使用防止性を有する安全な環境を提供する重要な埋込み型装置の一つとして、スマートカードがある。通常、スマートカードにおいてアプリケーションを実行する場合、データを暗号化してスマートカードにダウンロードし、スマートカードの内部でアプリケーション全体を実行する。この結果、重要な不正使用防止特性が得られる。アプリケーションのどの部分も外部に存在しないので、攻撃者にとって、スマートカードは内部で何が行われているか分からないブラックボックスのようなものである。すなわち、不正使用防止性を有するカードの外部からアプリケーションの特性を観察することはできない。
【０００３】
新世代のスマートカードの大きな問題は、メモリリソースの制約である。通常、スマートカードは８〜６４ＫＢのメモリしか持たず、このため、スマートカード上に大きなアプリケーションが存在することができない。通常、マルチベンダの複数のアプリケーションは、高い相互運用性を必要とするとともに、大量のリソースを必要とする。リソースの制約の他に、セキュリティに関連したオーバヘッドがあり、これにより、アプリケーション開発者が利用できるスペースがさらに少なくなる。例えば、複合型暗号化／解読方式、高度セキュリティ・トランザクションプロトコル、バイオメトリックコード等の種々の認証アプリケーションは、大きなデータセグメントおよび／またはコードセグメントを有し、スマートカードの内部にこれらの機能を収容することは大変な努力を要する。このため、スマートカードのアプリケーション領域は非常に限定されるとともにカスタマイズされてきた。複数のアプリケーションを容易にするため、および／または、カードに大きなアプリケーションを収容するため、アプリケーションを細かく分けなければならない。すなわち、スマートカードのメモリの場合、現在実行中または実行可能状態のアプリケーション部分しか保持しない。しかしながら、アプリケーションを分割することは、アプリケーションの一部がカードの外部に存在することを意味する。さらに、アプリケーションパーティションをスマートカードに送信した場合、アプリケーションの挙動が漏れてしまい、その結果、攻撃者がその挙動を利用して悪質な攻撃を開始するおそれがある。したがって、確実に、カードにダウンロードされるパーティションが情報を漏らさないようにしなければならない。
【０００４】
プログラムの挙動の結果として情報の漏洩が発生する多種多様な手段がある。これらの手段は、攻撃者が観察することができるプログラム特性に基づき、タイミング挙動、電力挙動、制御流れ挙動を含む。例えば、タイミングを観察することによってループが実行中であることを推測したり、消費電力を観察することによって多数回のメモリ動作が行われていることを推測したりすることができる。そして、この情報を利用して安全システムを不正使用することができる。タイミング情報や電力情報の漏洩はプログラム特性に関する情報を得るには比較的間接的なものであり、攻撃者は比較的複雑な実験を行って挙動差を得なければならない。一方、アプリケーションの制御流れ挙動の漏洩は非常に危険であり、攻撃者が挙動差を見つけ出すことは非常に簡単である。任意の分割化（partitioning）を行っても、制御流れ情報の漏洩が発生し、セキュリティの危険を引き起こすおそれがあり、これは、不正使用防止性を有する装置においてプログラムの分割化を行う際に生じる中心問題である。
【０００５】
図１Ａ、１Ｂを参照して、任意の分割化の潜在的危険を説明する。図１Ａはプログラムを基本ブロックに分割する基本的で単純な分割アルゴリズム１０を示し、図１Ｂはアルゴリズム１０に対応する制御流れ図（control flow diagram：ＣＦＧ）１１を示す。簡単に言うと、このアルゴリズム１０は、実行時に必要なプログラム部分のみのダウンロードを微調整することができる。
【０００６】
当業界で既知のＤｉｅ−ＨｅｌｌｍａｎやＲＳＡ等のシステムは、例えば、Ｒ−ｙｘｍｏｄ  ｎ計算からなる秘密鍵演算を含む場合がある。上記式において、ｎは公開され、ｙは傍受者によって求めることができる。攻撃者の目標は、秘密鍵であるｘを求めることである。問題を説明するため、Ｒ＝ｙｘｍｏｄ  ｎ（ここで、ｘの長さはｗビット）を計算する図１Ａの簡単なモジュラ累乗アルゴリズムを用いて実施すると想定することができる。この小さなコードパーティションの場合に対応するＣＦＧ１１を図１Ｂに示す。
【０００７】
アルゴリズムを用いて、スマートカードに送信されたプログラムを分割すると想定して、カード側が必要に応じてプログラムパーティションを要求する（すなわち、メモリ効率のために、カード側がどのプログラムパーティションもキャッシュしない）場合、ループ本体内において、現在調べているｘのビットが１の場合、ＩＦ部分を実行する（ブロック１６）ことが分かる。現在調べているｘのビットが０の場合、ＥＬＳＥ部分を実行する（ブロック１８）。アルゴリズムループ（ブロック１４、２０）の結果、一連のＩＦブロックまたはＥＬＳＥブロックがネットワークを介して送信される。攻撃者がこの順序を監視する場合、その知識から、攻撃者は、ｘのそれぞれのビットが０か１かを推測し、秘密鍵ｘを得ることができる。攻撃者はそれがＩＦ部分かＥＬＳＥ部分かを知る必要はなく、ＩＦ部分およびＥＬＳＥ部分を区別することができさえすれば、鍵ｘを推測することができる。その理由は、鍵、すなわち、その補数を推測したからである。このように、攻撃は、様々なプログラムパーティションの順序を利用して、プログラムの挙動を推論する。
【０００８】
図１Ａ、１Ｂに示す攻撃の種類の背後にある概念は、タイミング差や電力差の攻撃と同様である。各方法は、攻撃者が利用できる差から情報を利用しようとする。攻撃者は、送信時にネットワークからモバイルコードパケットを見つけ出し、それらを以前送信されたモバイルコードパケットと一致させた後、構築された順序から挙動を推測するようにすればいい。適当な計算能力およびネットワーク傍受を武器に、攻撃者はシステムのセキュリティの欠陥を利用することができる。また、ダウンロードされたパーティションが暗号化されていても、このような攻撃を防げないことが分かる。通常、所定のパーティションとそれを暗号化したものは一対一の関係なので、攻撃者は、送信された複数のパーティションを暗号化したものを一致させ、それらを順に並べた後、暗号化された順序から、暗号化されていない順序の場合と同じ情報を利用することができる。
【０００９】
上記例の場合、基本ブロック単位の分割化の大きな問題が、分割化によって得られたパーティションがすべての制御流れ情報を露呈させることであることが明らかである。ループが複数回繰り返された後、送信されたプログラムパーティションの順序を見ることによって、攻撃者は、ループが存在すること、どのパーティションがループの入口であるか、どのパーティションがループの終端部分であるかを知ることができる。また、攻撃者は、ループ本体内において、ＩＦ−ＥＬＳＥ構造が存在すること、どのパーティションが分岐を制御するプログラムパーティションであるかを知ることもできる。攻撃者はソースプログラムのすべての制御情報を事実上導出することができ、この結果、セキュリティホールが生じる可能性が大きくなる。
【００１０】
したがって、上記の説明および例から明らかなように、攻撃者が、ネットワークを介して送信され装置にダウンロードされるプログラムパーティションを観察することによって、プログラムの挙動を推測できないように、制御流れ情報を隠しながら、プログラムを分割するシステム、方法、コンピュータプログラムプロダクトが必要である。また、メモリが限られた装置にプログラムパーティションをダウンロードする際に不正使用防止性を確保しながら、その装置でプログラムパーティションが動作するように、プログラムのコードおよびデータを分割する方法とコンピュータプログラムプロダクトが必要である。
【００１１】
発明の概要
利用可能なメモリが限られた装置（例えば、スマートカード）でかなり大きいプログラムを実行しやすくするため、本発明のシステム、方法、コンピュータプログラムプロダクトは、プログラムが装置のメモリに収まらない場合、プログラム全体を分割する。実行直前に、要求に応じて、サーバから埋込み型装置に最小安全プログラムパーティションをダウンロードする。本システム、方法、コンピュータプログラムプロダクトは、プログラムの制御流れ挙動に関する情報が漏洩しないように、プログラムのコードおよびデータを分割する。すなわち、攻撃者は、サーバからダウンロードされるプログラムパーティションを観察することによって、プログラムがどのように分岐するか、また、プログラムの制御流れがどのような状況かを推測することはできない。この特性（本書では「不正使用防止性」と呼ぶ）は、感知可能情報の保持、および／または、金融取引等の重要な計算を行うことができるスマートカード等の安全埋込み型装置にとって有用である。
【００１２】
本発明の一側面によれば、本発明のシステム、方法、コンピュータプログラムプロダクトは、サーバ側（プログラムをサーバ側から装置に通信するシステム）で、モバイルコードプログラムのコードおよびデータを分割することによって、コードとそのコードがアクセスするデータの両方を含む独立したプログラムパーティションを得る。各プログラムパーティションに含まれる情報は各パーティションを実行するのに十分である。モバイルコードパーティションは、必要に応じて一つずつ装置（例えば、埋込み型装置）にダウンロードされる。一つのパーティションの実行が完了した後、サーバに次のパーティションを要求し、同時に、更新データ値をサーバに返送し、サーバ側でデータを一致させることができる。さらに、サーバ側で、要求された各パーティションを埋込み型装置に送る前に、各パーティションに対して中間形式（ＩＦ）レベルで動的最適化を行ってもよい。
【００１３】
スマートカードを挙げて本発明を説明しているが、本発明の方法およびコンピュータプログラムプロダクトが、セキュリティの向上やアプリケーション／データメモリを少なく済ませることの恩恵を受けるセキュリティ装置やメモリが限られた装置（例えば、携帯電話、セルラ電話、携帯用情報端末（ＰＤＡ）、ハンドヘルドコンピュータ等）にとって有用であることが分かる。
【００１４】
発明の詳細な説明
以下、本発明の好適な実施形態を示す添付図面を参照して、本発明をより詳細に説明する。但し、本発明は多種多様な形態で実施することができ、本書に記載の実施形態に限定されると考えるべきではない。すなわち、これらの実施形態は本開示を徹底的かつ完全にするためのものであり、当業者に本発明の範囲を十分に伝えるであろう。全体を通して同じ構成要素に同じ番号を付した。
【００１５】
図２は、本発明の一実施形態に係るプログラム分割（partitioning）システム３０を示すブロック図を示す。以下、ブロック図および流れ図を参照して、本発明のシステムおよび方法を説明することが分かる。ブロック図と流れ図のブロック、および、ブロック図と流れ図のブロックの組み合わせは、それぞれ、コンピュータプログラム命令によって実行できるものである。これらのコンピュータプログラム命令を汎用コンピュータ、専用コンピュータ、または、その他のプログラマブルデータ処理装置にロードして機構を生成することによって、コンピュータやその他のプログラマブルデータ処理装置で実行する命令が、流れ図の少なくとも一つのブロックで指定された関数を実行する手段を作成することができる。
【００１６】
また、コンピュータやその他のプログラマブルデータ処理装置に特定の方法で機能するように指示することができるコンピュータ可読メモリに上記のコンピュータプログラム命令を記憶させることによって、コンピュータ可読メモリに記憶された命令が、流れ図の少なくとも一つのブロックで指定された関数を実行する命令手段を含む製造項目を生成することができる。また、コンピュータプログラム命令をコンピュータやその他のプログラマブルデータ処理装置にロードして、一連の動作ステップをコンピュータやその他のプログラマブル装置で行い、コンピュータ実行処理を生成することによって、コンピュータやその他のプログラマブル装置で実行する命令が、流れ図の少なくとも一つのブロックで指定された関数を実行するステップを設けることができる。
【００１７】
したがって、ブロック図と流れ図のブロックは、指定された関数を実行する手段の組み合わせ、指定された関数を実行するステップの組み合わせ、指定された関数を実行するプログラム命令手段に対応している。また、ブロック図と流れ図の各ブロック、および、ブロック図と流れ図のブロックの組み合わせは、指定された関数やステップを実行する専用ハードウェア向きコンピュータシステム、または、専用ハードウェア・コンピュータ命令の組み合わせによって実施できるものである。
【００１８】
図２を再び参照すると、プログラム分割システム３０は、モバイルコードサーバ３３と、装置４２とを備える。サーバ３３と装置４２は、ネットワーク３９を介して互いに通信する。ネットワーク３９は、例えば、有線電気接続、赤外線通信路、セルラ接続、ブルートゥース無線接続、または、当業者に知られている同様の通信媒体から構成することができる。本発明の方法およびコンピュータプログラムプロダクトは、モバイルコードサーバ３３で動作してモバイルプログラム３２を分割することによって、メモリが限られた装置４２にモバイルプログラム３２のパーティション（partition）のみを送信する。各プログラムパーティションに含まれる情報は各パーティションを実行するのに十分であり、モバイルコードパーティションは必要に応じて一つずつ装置４２にダウンロードされる。装置４２は、モバイルプログラム３２の実行可能な分割部分を受信するだけにすぎないので、その限られたメモリのせいで別の方法では実行することができないプログラムを実行することができる。本発明の一実施形態では、装置４２は、メモリが限られた不正使用防止性を有する装置、例えば、スマートカードである。以下、装置４２としてスマートカードを挙げて説明するが、装置４２が、サーバ３３からプログラムを受信するセキュリティ装置やメモリが限られた装置、例えば、ＰＤＡ、携帯電話、ハンドヘルドコンピュータ等でもよいことが分かる。
【００１９】
本発明では、まず、モバイルコードプログラム３２はプログラムコード／プログラムデータ分析３４を受ける。以下にさらに詳細に説明するように、プログラムコード／プログラムデータ分析３４は、装置４２でプログラムパーティションを実行する直前に必要に応じてサーバ３３から装置４２にダウンロードすることができる安全プログラムパーティションを識別する。このような一連のパーティションは制御流れ情報を漏らさないので、安全プログラムパーティションは不正使用防止性を確保する。一例では、Ｌ１，Ｌ２，・・・，Ｌｎが、特定のプログラム分割法および装置キャッシュポリシ（本書では「クライアントポリシ」と呼ぶこともある）を用いてサーバ３３から装置４２に送信された一連のプログラムパーティションを示す場合、以下のプログラムパーティションの順序は、制御流れ情報を漏洩する（不正使用防止性を妨害する）順序である。
【００２０】
・・・，Ｌｉ，Ｌｋ，・・・，Ｌｉ，Ｌｍ，・・・
この順序では、プログラムパーティションＬｉはある時点でプログラムパーティションＬｋの前の順序で発生するが、後に、ＬｉはＬｋとは異なるプログラムパーティションＬｍの前に再び発生する。このような順序が発生すると、攻撃者は、プログラムパーティションＬｉが、ＬｋまたはＬｍへの実行経路を制御する制御ブロックである可能性があることを推測することができる。したがって、安全プログラムパーティションが、上記パーティション順序のような順序で二回発生することは決してあり得ないプログラムパーティションであることが分かる。本発明のシステム、方法、コンピュータプログラムプロダクトは安全パーティションの概念を用いて、装置４２に送信されたプログラムを分割する。さらに、最小安全パーティションは最も小さい安全パーティションなので、最小安全パーティションのサブパーティションはいずれも順序および制御情報を明らかにする。
【００２１】
図２を再び参照すると、本発明では、サーバ３３においてモバイルプログラム３２のコードおよびデータを分割することによって、コードとそのコードがアクセスするデータの両方を含む独立したプログラムパーティションが得られる。分割化を行っても、各プログラムパーティションに含まれる情報は各パーティションを実行するのに十分である。攻撃者は、サーバ３３から装置４２にダウンロードされたこれらのプログラムパーティションを観察することによって、プログラムがどのように分岐するか、また、プログラムの制御流れがどのような状況かを推測することはできない。この不正使用防止特性は、機密情報の保持、および／または、金融取引等の重要な計算を行うことができるスマートカード等の安全埋込み型装置にとって有用である。本発明の一態様によれば、プログラムコード／プログラムデータ分析３４は、ＣやＣ＋＋のモバイルプログラムをコンパイルするのに使用可能なプログラム分割アルゴリズム（図示せず）によって実施される。
【００２２】
プログラムパーティションを識別した後、サーバ３３はプログラムを複数のプログラムパーティション３６に分割する。プログラム分割プログラムによって分割化を行ってもよい。パーティションを生成した後、パーティションの動的最適化３８を行うことによって、依然確実に、結合したパーティションを装置４２に送信する時にプログラムの制御流れ挙動に関する情報を漏らさないようにしながら、最少数の安全プログラムパーティションを結合する。以下、併合（merging）アルゴリズムを参照して、パーティションの併合を詳細に説明する。パーティションを結合することによって、サーバ３３から装置４２への送信回数が最小限に減らされることが分かる。メモリ利用の観点から、安全パーティションをできるだけ小さくする、すなわち、最小安全パーティションにすることが好ましい。しかしながら、実行時にネットワークを介して多数のコード小片を送信すると、効率が非常に低下するおそれがあるので、隣接する最小安全パーティションを結合して大きなパーティションを形成してもよく、その結果、装置４２にパーティションを送信しても制御流れ情報の漏洩を発生させないので依然安全である。
【００２３】
また、動的最適化（プログラム分割プログラムによって行ってもよい）によって装置４２を調べて装置の必要メモリやキャッシュポリシを判断することによって、適宜の数および大きさのパーティションを装置４２に送信することができる。プログラムパーティションをサーバ３３から装置４２に送信する時に制御流れ情報が発見されないようにプログラムを分割する時、本発明のシステム、方法、コンピュータプログラムプロダクトが安全パーティションのみを選択することが重要であることが分かる。つまり、安全パーティションは、クライアントの要求に応じて送信される時にその順序が観察されてプログラムの制御流れ情報が漏洩することはない。本発明に係る安全分割化は、プログラムの分割・送信方法だけでなく、ネットワーク３９を介して装置４２にパーティションを送る方法とタイミングにも基づく。装置４２に何を送信するかは装置４２のキャッシュポリシ（例えば、入力されるプログラムパーティションの全部または一部をキャッシュするか否か）によって決まるので、プログラムの分割方法とパーティション管理のクライアントポリシの両方によって安全プログラム分割化が決まることは当業者には分かる。
【００２４】
本発明の一態様によれば、要求されたモバイルコードパーティション４０、４４を必要に応じて一つずつ装置４２にダウンロードする。本発明の一態様によれば、サーバ側で、要求された各パーティションを埋込み型装置に送る前に、各パーティションに対して中間形式（ＩＦ）レベルで動的最適化を行ってもよい。アセンブリコードでプログラムパーティションを送信しないので、中間形式よりも数倍長くなり得る２進形等の固有コードでパーティションを送信する場合より高速でサーバ３３と装置４２間の通信を行うことができる。
【００２５】
パーティションを受信すると、装置４２はパーティションマネージャ・パーティションローダ／リンカ４６を実行し、パーティションの目的の宛先を決定する。したがって、パーティションマネージャ４６は、パーティションを分解し、パーティションのメモリ内の位置を決める。プログラムの実行４８の後、装置４２は必要な実行結果（すなわち、更新データ値５０）をサーバ３３に返信する。装置４２はパーティションを実行するごとにデータ値を更新するとは限らないので、データ値の更新は任意である。実行４８の後、装置４２は次の送信要求５２をサーバに送信し、関数を実行するのに必要な次のパーティションを要求することができる。
【００２６】
上記のように、不正使用防止性はプログラム分割法とクライアントのキャッシュポリシの両方の影響を受ける。なぜならば、これらは共にネットワークを介して送信されるパーティションを決定するからである。本発明のシステム、方法、コンピュータプログラムプロダクトは、以下の三つの異なる装置キャッシュポリシ（１）〜（３）のいずれかに従って動作する装置にパーティションをダウンロードするように機能することができる。（１）「受信したパーティションをすべて保持する」、（２）「受信したパーティションのいずれも保持しない」、（３）「制御が戻ることが保障されたパーティションを保持する」。
【００２７】
「受信したパーティションをすべて保持する」というポリシによって、装置は、埋込みプログラムが実行を終了するまでサーバが装置に送るプログラムパーティションをすべて保持する。このポリシはメモリ効率が最低のポリシであり、クライアント装置に最大のメモリ負担をかける。今後二度とプログラムパーティションにアクセスしなくても、装置はローカルメモリにパーティションを保持しなければならないので、その結果、埋込み型装置の貴重なメモリリソースが無駄になる。しかしながら、装置はプログラムパーティションを永久記憶するので、このポリシでは、装置にプログラムパーティションを複数回送信する必要がないので、重大なセキュリティの問題が生じることはない。
【００２８】
「受信したパーティションのいずれも保持しない」というポリシによって、装置は、プログラムパーティションを実行した直後にプログラムパーティションを破棄する。装置は現在実行中の一つのプログラムパーティションを保持しさえすれば良いので、このポリシがクライアント装置にかけるメモリ負担は最小である。クライアントのメモリが非常に限られている場合、このポリシを適用することができる。クライアントはパーティションを一切保持しないので、必要に応じてすべてのプログラムパーティションを再送信しなければならない。
【００２９】
「制御が戻ることが保障されたパーティションを保持する」という三番目のポリシによって、装置は、制御が戻ることが保障された安全パーティションを保持する。このようなパーティションの例として、関数呼び出しを含む基本ブロックを考える。このポリシによって、関数呼び出しの後、このポリシによってメモリに保持される呼び出し基本ブロックに制御が戻ることが保障される。今後再アクセスされることが明らかなパーティションを保持するだけなので、このポリシがクライアント装置にかけるメモリ負担は、受信したパーティションをすべて保持するポリシの場合よりもずっと小さい。
【００３０】
次に、本発明に係るプログラム分割アルゴリズムについて考える。これらの分割アルゴリズムは、プログラムの制御流れ挙動に関する情報が漏洩しないように、プログラムのコードおよびデータを分割する。
【００３１】
本発明の一態様によれば、本発明のシステム、方法、コンピュータプログラムプロダクトは、モバイルプログラムの各関数に適用されたプログラム分割アルゴリズムを実施する。このため、本発明の一実施形態では、プログラムの分割化は関数毎に適用される。装置がスマートカードである実施形態を続けて説明すると、スマートカードが関数を実行するのに適したデータを持つスマートカードに当業界で周知の関数を送信することができる。次に、スマートカードは関数を実行し、関数を提供したサーバに応答する。上記のように、制御情報の漏洩は、サーバからパーティションを繰り返し送ることに起因する。したがって、プログラム実行時に関数を複数回呼び出すことができるかどうかは、不正使用防止性を有する分割アルゴリズムにとって重要である。
【００３２】
プログラムパーティション（すなわち、関数）を再送信すると制御流れ情報が漏洩するおそれがあるので、本発明の方法およびコンピュータプログラムプロダクトは、関数を非再帰（non-recurring）関数と再帰（recurring）関数に分類する。この分類を行った後で初めて、プログラムの分割化を行うことができる。
【００３３】
非再帰関数は、プログラム実行時に多くて一回呼び出される関数である。このため、プログラムが実行するために関数を装置に複数回送信する必要はない。非再帰関数の一例として、Ｃ言語の主関数がある。この関数はＣのプログラムにおいて一回だけ実行されるからである。非再帰関数の他の例として、プログラム初期設定関数やプログラム最終設定関数がある。一方、再帰関数は複数回呼び出され得る関数である。この関数によって、本発明のシステム、方法、コンピュータプログラムプロダクトが解消しようとする制御流れ情報漏洩の明白かつ重大な問題が生じる。
【００３４】
本発明では、簡単な静的プログラム解析の結果、関数が再帰関数であるか非再帰関数であるかが分かる。図３に、このような解析を行うＣ言語のアルゴリズム６０を示す。本発明の一態様によれば、アルゴリズム６０は、サーバ３３によって実行されるプログラム分割アルゴリズムの少なくとも一部からなる。アルゴリズム６０に示すように、まず、当業界で周知の増加プログラム呼び出しグラフを作成する。呼び出しグラフの各ノードは以下の三つの情報によって増加される。（１）関数の静的発生は一回だけかどうか、（２）ループ本体内で関数が呼び出されているかどうか、（３）関数のアドレスがファンクションポインタに割り当てられているかどうか。次に、増加呼び出しグラフの最初の横断を行う。
【００３５】
図４の流れ図において、アルゴリズム６０の関数をブロック図の形式で示す。この流れ図は、増加呼び出しグラフを構築した後、増加呼び出しグラフの非ルートノードを識別することを示す（ブロック６４）。次に、図４に示すように、各非ルートノードに対して一連の照会を行い、非ルートノードが非再帰かどうかを判定する。まず、アルゴリズムは、非ルートノードの静的発生が一回だけかどうかを判定する（ブロック６６）。ブロック６６でＮＯの場合、非ルートノードを再帰と示す（ブロック７２）。ブロック６６でＹＥＳの場合、アルゴリズムは、非ルートノードがループ本体内にあるかどうかを判定する（ブロック６８）。ブロック６８でＹＥＳの場合、非ルートノードを再帰と示す（ブロック７２）。次に、ブロック６８でＮＯの場合、アルゴリズムは、非ルートノードの固有の呼び出し関数が非再帰関数であるかどうかを判定する（ブロック７０）。ブロック７０でＮＯの場合、非ルートノードを再帰と示す（ブロック７２）。ブロック７０でＹＥＳの場合、アルゴリズムは、非ルートノードの関数がファンクションポインタに割り当てられているかどうかを判定する（ブロック７４）。ブロック７４でＹＥＳの場合、非ルートノードを再帰と示す（ブロック７２）。ブロック７４でＮＯの場合、非ルートノードを非再帰と示す（ブロック７６）。最後に、図示しないが、各非ルートノードはこの一連の照会に従い、この処理を用いて各非ルートノードを再帰か非再帰のいずれかで示す。
【００３６】
図３に示され図４のブロック図形式の流れ図によって表されるアルゴリズム６０が、増加呼び出しグラフに含まれず静的発生が無い関数を処理しないことが分かる。すなわち、関数の静的発生が無い場合、本発明の方法では、ファンクションポインタによって関数が呼び出されると仮定し、デフォルトで再帰関数として分類する。したがって、このアルゴリズム６０はポインタ解析を行わないので、保守的なアルゴリズムである。すなわち、関数のアドレスがファンクションポインタに割り当てられている時はいつも、アルゴリズム６０は関数が再帰関数であると仮定する。通常、非再帰関数は少数しかないので、アルゴリズム６０の保守性の影響は実際にはほとんど無い。
【００３７】
本発明の一態様によれば、関数が再帰関数であるか非再帰関数であるかを明らかにする簡単な静的プログラム解析は、プログラム分割アルゴリズムによって行われる。分割化の問題を非再帰関数分割化と再帰関数分割化に分類した後、プログラム分割アルゴリズムはプログラムを分割できる状態にある。次に、上記三つのクライアントキャッシュポリシに基づいて、本発明のプログラム分割アルゴリズムの関数を説明する。
【００３８】
まず、「受信したパーティションをすべて保持する」というポリシによって、クライアント装置は、受信するパーティションをすべて保持する。このため、プログラムのすべてのパーティションはネットワークを介して多くて一回送られる。このため、制御の漏洩はパーティションを繰り返し送信することに起因するので、制御の漏洩が発生する潜在的危険はない。したがって、任意の分割化を行うことができ、送信は安全なままである。最小安全パーティションは各基本プログラムブロックであり、サーバは、プログラム分割アルゴリズムを用いて、クライアントが要求する各プログラムパーティションを簡単に送出することができる。
【００３９】
一方、プログラム分割アルゴリズムは、「受信したパーティションのいずれも保持しない」というポリシと「制御が戻ることが保障されたパーティションを保持する」というポリシの両方によるパーティションの再送信を防止しなければならない。この理由は、装置のメモリがすべての条件下で実行する必要があるすべてのプログラム情報の永久コピーを保持しないので、これらの各ポリシによってパーティションを定期的かつ複数回送信する場合があるからである。これらの各ポリシの場合に本発明が実施する分割アルゴリズムについて説明する前に、不正使用防止性を有するプログラム分割化に対する関数呼び出しの効果について簡単に説明し、本発明の分割アルゴリズムの目的および作用を明らかにすべきである。
【００４０】
図５に基づいて、安全パーティション内のサンプル関数呼び出しを説明する。図５に示すように、安全パーティションＬ１１８０には、関数呼び出しＦ１８２がある。Ｆ１８２の関数本体９２を図５の右側に示す。クライアント装置で関数呼び出しが発生すると、装置は関数Ｆ１８２の安全パーティションを要求し、安全パーティションＬ１１８０を破棄し、「受信したパーティションのいずれも保持しない」というポリシによって入力プログラムパーティションが利用できるメモリを最大にする。関数Ｆ１８２の実行が完了すると、制御はＬ１１８０に戻る。次に、クライアントはＬ１１８０の再送信を要求する必要がある。したがって、ネットワークを介して送られたパーティションの順序は以下の通りである。
【００４１】
・・・，Ｌ１１８０，Ｌ２１８６，Ｌ２２８８，Ｌ２３９０，Ｌ１１８０，Ｌ１２８４，・・・
Ｌ１１８０の後にＬ２１８６とＬ１２８４がそれぞれ続く。これは厳密な不正使用防止性の定義に反する。なぜならば、Ｌ１１が制御パーティションである可能性があると見られる可能性があるからである。このため、「受信したパーティションのいずれも保持しない」というポリシによって、関数呼び出しのある関数を分割できないことが分かる。「制御が戻ることが保障されたパーティションを保持する」というポリシの場合も、同様の結果となる。しかしながら、Ｌ１１８０はＬ２１８６またはＬ１２８４への分岐を制御する制御ブロックではなく、上記順序から、攻撃者は関数内の目的の制御流れ情報を得ることはできない。最悪の場合、攻撃者が、Ｌ１１に関数呼び出しがあることと、Ｌ２１、Ｌ２２、Ｌ２３が関数本体からなることを知る可能性がある。しかしながら、「受信したパーティションのいずれも保持しない」というポリシと「制御が戻ることが保障されたパーティションを保持する」というポリシの両方によって、関数呼び出しが分岐時にプログラムの制御流れ情報を漏らすことはない。なぜならば、呼び出しの正常復帰を仮定して、関数呼び出しの後のブロックを常に実行するからである。すなわち、関数呼び出しは単にモジュラ設計を示しているだけであり、制御流れを変更するために効果的に利用することができないモジュール性情報を明らかにする可能性がある。
【００４２】
次に、非再帰関数と再帰関数を分割する場合、「受信したパーティションのいずれも保持しない」というポリシおよび「制御が戻ることが保障されたパーティションを保持する」というポリシによってプログラムを分割する方法とコンピュータプログラムプロダクトについて説明する。非再帰関数と再帰関数を分割する分割アルゴリズムは「受信したパーティションのいずれも保持しない」というポリシと「制御が戻ることが保障されたパーティションを保持する」というポリシの両方の場合と同じなので、各ポリシの分割アルゴリズムを同時に考える。
【００４３】
ここで非再帰関数の分割化について説明すると、二つ以上の別個のパーティションが特定のパーティションの後に続く可能性があるときループを実行する場合、本発明はループ本体を分割しない。図６Ａは、本発明の一例に係るループを含むＣＦＧ９４を示す。このループはパーティションＢ１、Ｂ２、Ｂ３、Ｂ４から構成される。Ｂ１の後にＢ２、Ｂ４、または、Ｂ３、Ｂ４が続く可能性があるので、ループを構成するパーティションがいっしょに残らなければならない、さもなければ、制御流れ情報にアクセスできることが分かる。その結果、本発明の方法およびコンピュータプログラムプロダクト、特に、プログラム分割アルゴリズムはループ本体（すなわち、ループを構成するパーティション）をいっしょに維持し、装置に送信する。
【００４４】
図７に、本発明の一実施形態に係る非再帰関数を分割するＣ言語のアルゴリズム１００を示す。アルゴリズム１００は「受信したパーティションのいずれも保持しない」というポリシに従って動作する装置用であるが、「制御が戻ることが保障されたパーティションを保持する」というポリシに従って動作する装置に同じアルゴリズム１００を適用することができる。アルゴリズム１００は、上記の規則を用いて最小安全パーティションを作成する。本発明の一態様によれば、プログラム分割アルゴリズムによってアルゴリズム１００を実施することができる。アルゴリズム１００を図６Ａの例に適用すると、最小安全パーティションは、Ｌ１＝Ｂ１、Ｂ２、Ｂ４、Ｌ２＝Ｂ５になるはずである。プログラムパーティションの実行順序はＬ１、Ｌ２によって与えられるが、ネットワークを介して送られた順序はＬ１、Ｌ２であり、これは不正使用防止性を有する。装置が所望の関数を実行するのに必ずしもＬ１のすべてのパーティションを必要とするわけではないことは当業者には分かる。例えば、装置がサブパーティションＢ１、Ｂ２、Ｂ４の流れを辿る場合があり、このとき、パーティションＢ３は実行には必要ない。しかしながら、このパーティションを装置に送信して不正使用防止性を維持する。なぜならば、該パーティションを含まないようにするためには、不正使用防止性を妨害する装置に該パーティションを再送信することが必要な場合があるからである。
【００４５】
次に、再帰関数を分割する方法とコンピュータプログラムプロダクトについて説明する。非再帰関数の分割化と同様に、再帰関数がループを含むと、サーバから装置にパーティションを送信する時に制御流れ情報が漏洩するおそれがある。したがって、ループ本体を分割できないという同じ規則が当てはまる。図８に、本発明の一実施形態に係る再帰関数を分割するＣ言語のアルゴリズム１０４を示す。アルゴリズム１０４は「受信したパーティションのいずれも保持しない」というポリシに従って動作する装置用であるが、「制御が戻ることが保障されたパーティションを保持する」というポリシに従って動作する装置に同じアルゴリズム１０４を適用することができる。アルゴリズム１０４は、上記の規則を用いて最小安全パーティションを作成する。また、プログラム分割アルゴリズムをサーバで実行することによって、アルゴリズム１０４を実施することができる。
【００４６】
再帰関数の分割アルゴリズム１０４は非再帰関数のアルゴリズム１００とほぼ同じであるが、サーバ側の実行時挙動は異なることが分かる。非再帰関数の場合、本発明に係るサーバは、クライアントの要求に応じて安全パーティションを送るだけである。しかし、再帰関数の場合、サーバは、再帰関数のすべての減少ノードを含む所定の安全パーティション順序を送る。しかしながら、この順序を任意の順序にすることはできない。図６Ｂは、本発明の別の例に係るＣＦＧパーティション順序９６を示す。例えば、図６Ｂでは、Ｒ１の前にＲ２を送信できない。すなわち、この順序は減少グラフノードのトポロジの順序に相当する。順序に与えられる減少グラフおよびトポロジの順序の非周期性のため、順序は不正使用防止性を有する。図６ＢのＣＦＧ９６の場合、サーバは、トポロジの順序、例えば、Ｒ１、Ｒ２、Ｒ３、Ｒ４、Ｒ５を予め決める。実行時、サーバは、制御流れにかかわらず、クライアントにこの順序を常に送出する。送られたプログラムパーティションの中には、ダミー安全パーティションがある。例えば、実際の実行経路がＲ１、Ｒ２、Ｒ５の場合、Ｒ３、Ｒ４はダミーパーティションである。
【００４７】
図７、８に基づいて上に説明した分割アルゴリズムが最も安全な最小パーティションを提供することが分かる。本発明のあまり好ましくない実施形態では、安全だが必ずしも最小ではないパーティションを識別することもできる。このようなパーティションを実行するため、以下のステップ（１）、（２）を行うことによって、主プログラムを安全領域に分割することができる。すなわち、（１）各ループの入口および各ループの終端部分の位置を決め、ノードの合併を安全領域とし、（２）ループ本体内に他の基本ブロックを形成する（但し、第１の安全領域、第２の安全領域には形成しない）。これらのステップは上記の非再帰関数の分割化と同様であるが、最小パーティションを確保しない。したがって、以下のステップ（１）〜（５）を行うことによって、手続きの本体を分割することができる。すなわち、（１）手続きの本体の減少ＣＦＧを作成し、（２）その手続きの減少ＣＦＧの入口ノードが最小安全領域そのものなので、最後の最小安全領域をこの安全領域に設定し、（３）最後の最小安全領域の減少ノードのすべての後続点の場合、すなわち、特定の後続点ノードのすべての先行点ノードの処理が完了した場合、この後続点ノードを現在の最小安全領域に追加し（これ以外には何も行わない）、（４）すべての後続点ノードを処理した後、最後の最小安全領域を現在の最小安全領域に設定し、（５）減少ＣＦＧの終端ノードの処理が完了するまで、ステップ（３）、（４）を繰り返す。これらのステップは上記の再帰関数の分割化の代替例であるが、上記分割化と同様である。但し、これらのステップは最小パーティションを確保しない。
【００４８】
上記のように、サーバ３３内のプログラム分割アルゴリズムによって、本書に記載の各アルゴリズムを実施することができる。したがって、プログラム分割アルゴリズムは、モバイルプログラム内の再帰関数と非再帰関数を効果的に識別することができ、上記方法に係るモバイルプログラムを分割することができる。また、装置のキャッシュポリシを与えられて、プログラム分割アルゴリズムはクライアント装置に適宜のパーティションを送信することができる。
【００４９】
プログラムの分割化を詳細に説明してきたが、本発明の別の態様がデータの分割化であることが分かる。スマートカード等のメモリが限られた装置が、プログラムの実行に利用できる限られたメモリだけでなく、データの記憶に利用できる限られたメモリも含むことが分かる。したがって、プログラムの分割化について上に説明した本発明のシステム、方法、コンピュータプログラムプロダクトを用いて、データの分割化を行うこともできる。特に、本発明を用いて、サーバ３３は、装置４２が現在のアルゴリズムを実行するのに必要なデータのみを送信することができる。クライアント側でプログラムパーティションを実行するためには、コードパーティションが必要とするデータが必要である。本発明の方法およびコンピュータプログラムプロダクトは、プログラムのデータセグメント全体に加えてスタックおよびヒープを送信するのではなく（非常に効率が悪い）、特定のコードパーティションがアクセスしたデータを送るだけである。
【００５０】
コードパーティションのデータアクセスは、以下の三つのカテゴリに分類することができる。（１）非デリファレンスデータアクセス：スタック内のローカル定義変数およびデータセグメント内のグローバル定義変数への直接アクセスに相当する（ポインタデリファレンスは行われない）、（２）非ヒープオブジェクトへのデリファレンスデータアクセス：ポインタは、スタックやプログラムデータセグメント内のオブジェクトを示すことができる。プログラムにおいて、これらのオブジェクトの静的定義と静的割り当てを行うので、このようなオブジェクトに対して静的に正確な情報のポイントを識別できる、（３）ヒープオブジェクトへのデリファレンスデータアクセス：ヒープオブジェクトを示すポインタ。ヒープオブジェクトの動的割り当てと動的解放を行う。図９、１０に、それぞれ、上記カテゴリのうち最初から二つのカテゴリのデータを分割するアルゴリズム１０８、１１０を示す。上記アルゴリズムと同様に、プログラム分割アルゴリズムによってこれらのアルゴリズムを実施することによって、プログラム分割アルゴリズムは、プログラムと分割されたプログラムの動作に必要なデータとの両方を効果的に分割することができる。三番目のカテゴリであるデリファレンスヒープアクセスについては、アクセスしたヒープオブジェクトの抽出には複雑さが伴うので、クライアント装置がこのアクセスを独立管理するのが好ましいことが分かる。
【００５１】
次に、本発明の別の方法である安全パーティションの併合について詳細に説明する。上記の方法（コンピュータプログラムプロダクトによって実施してもよい）、特に、プログラム分割アルゴリズムと同様に、安全パーティションの併合方法もサーバ３３内で行う。また、プログラム分割アルゴリズムによって安全パーティションの併合を行うことができる。
【００５２】
上記のアルゴリズムは、装置の異なるキャッシュポリシにより最小安全パーティションを識別する本発明の動作を示す。本書に記載の不正使用防止性を有する分割アルゴリズムによれば、各関数呼び出し時、送信される安全パーティションの順序が必ず同じになるように、関数本体を複数の安全パーティションに分割することによって、プログラムパーティションの順序の差からプログラム制御情報が漏洩しないようにする。このため、プログラム実行時の安全パーティションの送信順序は実際には所定かつ一定であり、毎回同じ順序が送信される。このような重要な特性のため、不正使用防止性を損なうことなく、隣接する安全パーティションを併合して大きなパーティションを形成することができる。
【００５３】
複数のパーティションを併合すると、装置にプログラムをダウンロードする送信時間が短縮される。最小安全パーティションは、実行時の細かい粒度により能率が悪くなる。この問題を多少とも解決するため、本発明は、装置で利用できるデータメモリ量およびコードメモリ量に対してスケーラブルな新規の解決法を提供する。これは、メモリ容量の制約のもとで隣接する最小安全パーティションを併合することによって行われる。そうすると不正使用防止特性が妨害されないことが分かる。
【００５４】
併合アルゴリズム（例えば、サーバ内のプログラム分割アルゴリズムや別の併合アルゴリズムによって実施される）は、装置のコードサイズの限界およびデータサイズの限界といったリソースの制限によって導かれる。したがって、併合アルゴリズムは、元の最小安全パーティションと、装置のコードサイズの限界およびデータサイズの限界とを入力とする。次に、コードパーティションの併合を行い、確実に、併合パーティション（すなわち、複数のパーティションの和）が装置のメモリリソースを超えないようにする。さらに、この併合はコードとデータの両方に行うことができる。したがって、データの併合結果は参照データの合併である。併合を行うため、本発明の方法は、項目のパーティションを求めることによって、以下の二つの条件下でパーティション数が最小になるようにする。すなわち、（１）パーティションは項目を並べ替えることができない、（２）元の一つの項目が単独でリソースの限界を超えた場合、その項目を他の項目と併合しない。図１１は、本発明の一実施形態に係る最小安全パーティションの併合アルゴリズム１１１を示す。
【００５５】
最後に、本発明のさらに別の態様によれば、本発明のシステム、方法、コンピュータプログラムプロダクトは、メモリ不足の装置のプログラム機能記憶能力をさらに最適化することができる。特に、メモリにパーティションを保持することが義務として要求されていない場合、必要に応じてサーバから必要なパーティションを取り出すのにかなりのオーバヘッドがかかることがある。例えば、装置とサーバがセルラネットワークを介して互いに通信する場合、これらの通信のコストが高くなることがある。安全パーティションの併合を行っても、通信とダウンロードに莫大なオーバヘッドがかかる可能性がある。実行時のオーバヘッドを削減するため、本発明、特に、プログラム分割アルゴリズムは、クライアント装置で関数のキャッシュを行うことができる。関数のキャッシュによって、クライアントは、関数集合のキャッシュ専用にメモリの一部を残すことができる。キャッシュされた関数を再呼び出しするとき、クライアントは、サーバに関数を要求するのではなく、ローカルメモリから直接関数を取り出す。プログラム分割アルゴリズム（以下「コンパイラ」と呼ぶこともある）によって、クライアントのメモリのプログラムの所定の位置にどの関数（少なくとも一つの関数）を保持すべきかを静的決定することができる。クライアント側の装置で動的にキャッシュから追い出すアルゴリズムを行うとコストがかかるので、静的方法が好ましい。
【００５６】
本発明の関数キャッシュ機構の枠組みは、以下の三つのステップ（１）〜（３）からなる。すなわち、（１）プログラム計測、（２）ホットファンクションセットの識別と最適化、（３）コンパイル／実行時環境の支援。特に、ある特定の関数集合（すなわち、ホットファンクションセット）は、ある期間の間プログラムによって定期的に呼び出される。関数のキャッシュによって、各呼び出し位置でホットファンクションセットを識別する。プログラム実行時、各呼び出し位置のホットファンクションセットの静的決定と固定を行う。各ユーザ定義関数呼び出し毎に、命令によって、呼び出し関数のＩＤ、呼び出し基本ブロックのＩＤ、呼び出された関数のＩＤをダンプする。このように、プログラムのどの位置でどの関数を呼び出すかという情報を用いてトレースを生成する。関数呼び出しのトレースを得た後、本発明の方法およびコンピュータプログラムプロダクトは、トレースのパターンを取り込むように動作することができる。ホットファンクションとは、所定の期間にわたってＩＤが高頻度のパターンに含まれる関数である。
【００５７】
次に、トレース分析アルゴリズムは、トレース領域のホットファンクションセットの生存期間を三段階に分ける。各段階毎に、異なる戦略を以下のように適用することができる。
【００５８】
（１）ホットセットの増大と安定化。この段階では、新しいホットセットが増大中であり、この領域のすべてのホットファンクションがホットセットに含まれていたわけではないと考えられる。この段階では、アルゴリズムによって、現在のホットセットが支障なく増大することができる。走査された呼び出しトレースの長さがホットセットの所定の最大サイズを超える場合、現在のホットセットは維持段階に入る。
【００５９】
（２）ホットセットの維持。この段階では、この領域のホットセットの増大が完了している。後続の関数呼び出しは、ホットセットのヒットを示すことになっている。この段階の時、ホットセットの増大完了後のホットセットの総失敗数を数える。失敗が所定の最大許容数を超える場合、現在のホットセットは破棄段階に入る。
【００６０】
（３）ホットセットの破棄。ホットセットの遷移点を示すホットセットの失敗が観察されるので、ホットセットはこの段階に入る。いったんホットセットがこの段階に入ると、ホットセットの関数を追い出し、関数のヒット数が所定の最低ヒット頻度以上の場合、現在調べている領域にこの関数をキャッシュするようにする。頻度を調べることによって、ホットセットのノイズを除去する。
【００６１】
トレース分析アルゴリズムには、いくつかの制御パラメータがある。ホットセットの最大サイズを大きくすることによって、トレースのより長いパターンを発見することができるが、同時に、ノイズを発生させるとともに複数のホットセットを結合して一つにまとめる危険を冒す。最大許容数の失敗は、ホットセットの最大サイズと同様の影響を及ぼす。最低ヒット頻度は、ホットセットのノイズをフィルタリングするとともに、発見したホットファンクションが十分なものであることを確実にする防護である。異なるプログラムは、それぞれ、異なる呼び出しトレースの挙動を示す。これらのパラメータによって、アプリケーション毎の性能と必要メモリのバランスを容易に見つけることができる。図１２のＣ言語のアルゴリズム１１２は、高レベルのトレース分析アルゴリズムを示す。
【００６２】
各呼び出し位置のホットファンクションセットは、その位置でキャッシュされる関数集合である。キャッシュ対象の集合は、位置によって異なる場合がある。コンパイル／実行時環境の支援は、ホットファンクションセットの遷移を可能にするために必要である。モバイルコードプログラムをコンパイルするとき、プログラム分割アルゴリズム（すなわち、コンパイラ）は、必要に応じて、ユーザ定義関数呼び出しの直前に関数呼び出しｕｐｄａｔｅ＿ｃａｃｈｅｄ＿ｆｕｎｃｔｉｏｎ（ｉｎｔ  ｃｕｒｒｅｎｔ＿ｆｕｎｃ＿ｉｄ，  ｉｎｔ  ｃｕｒｒｅｎｔ＿ＢＢ＿ｉｄ）を挿入する。実行時、呼び出し位置で現在キャッシュされている関数集合がキャッシュ対象の関数集合と等しいことをコンパイラが静的に確認できない場合、このような関数呼び出しが必要である。異なる集合が異なる結合端でキャッシュされているので、結合ノードでは、二つの集合が等しいかどうか分からない場合がある。モバイルプログラムは、挿入した関数呼び出しによりキャッシュされている関数を更新するように実行時環境に要求する。実行時環境は、プログラムをロードするとき、呼び出し位置のマップも対応するホットファンクションセットにロードする。実行時環境は、要求を受け取ると、現在の呼び出し位置の対応するホットファンクションセットを現在キャッシュされている関数と比較し、キャッシュ対象であるがローカルに利用できない関数を見つけ出した後、これらの関数をサーバに要求する。
【００６３】
各呼び出し位置でキャッシュされるホットファンクションセットが、トレース分析アルゴリズムの結果として知られていることが分かる。しかしながら、場合によっては、各呼び出し位置は異なるホットファンクションセットを有する。現在キャッシュされている関数集合を特定の呼び出し位置でキャッシュされる関数集合に動的に変更するため、更新キャッシュ関数呼び出しはその変更を計算することができる。プログラム分割アルゴリズムによって、この関数を実行することができる。各ユーザ定義手続き呼び出しの直前に呼び出しを行い、実行時性能のオーバヘッドを発生させるのが好ましい。一方、現在キャッシュされている関数集合がキャッシュ対象の関数集合と等しいことをコンパイラが保証できる場合、挿入された更新キャッシュ関数呼び出しは性能向上に必要ない。また、本発明の一態様によれば、二つのホットファンクションセットが等しくない場合、より簡単な呼び出しを用いることができ、この呼び出しが実行時環境に差を明示することによって、実行時環境が差自体を計算する必要がなくなり、その結果、コストが削減される。図１３Ａに一例を示す。
【００６４】
図１３Ａの例１１４では、基本ブロックＢ１１１５に関数呼び出しｆｏｏ（）がある。キャッシュ対象の集合は、ｆ１，ｆ２，ｆ３である。基本ブロックＢ２１１６の唯一の先行点はＢ１である。このため、プログラムがＢ２１１６に進むと、確実にＢ１１１５から制御が来る。このため、現在キャッシュされている集合が｛ｆ１，ｆ２，ｆ３｝であることが分かる。これは、関数呼び出し位置ｆｏｏ２（）のキャッシュ対象の集合と同じである。したがって、キャッシュされている関数集合を変更する更新キャッシュ関数呼び出しは必要ない。図１３Ｂは、更新キャッシュ関数呼び出しが必要な場合の例を示す。この例では、ブロックＢ３１２３は、二つの先行点、すなわち、ブロックＢ１１２１とブロックＢ２１２２を有する。現在キャッシュされている関数集合は、どの先行点から制御が来るかによって異なる。このため、静的には、実行時にどの集合が現在キャッシュされているかを知る方法がないので、更新キャッシュ関数呼び出しが必要である。図１４は、本発明の一態様に係る、更新キャッシュ関数呼び出しが必要かどうかを判定するＣ言語のアルゴリズム１２６を示す。
【００６５】
コンパイラが導き各呼び出し位置でキャッシュされる関数集合を識別した後、コンパイラはプログラムの必要メモリを導出することができる。まず、コンパイラは、各呼び出し位置のホットファンクションの必要メモリを確保して良好な性能を実現し、次に、特定のホットセットの実行中に見られる最小安全パーティションの最大サイズを調べる。コンパイラは、これら二つの和を、特定の呼び出し位置のコンパイラ推奨メモリ割り当てサイズとする。
【００６６】
本明細書に記載されているように、本発明は、安全埋込み型装置（例えば、スマートカード）に、効率的で不正使用防止性を有するプログラム分割化を提供する。本発明は、ネットワークを介して送られたプログラムパーティションの順序に顕著な差が無いので、装置にプログラムを送信する際に不正使用防止性を提供する。プログラムパーティションを受信する装置におけるパーティションのキャッシュの異なるポリシは、不正使用防止性を有するプログラム分割法と、装置の関数実行性能（例えば、装置内の必要メモリ、プログラムアプリケーションの実行速度等）に影響を与える。本発明の分割アルゴリズムは、アプリケーションを非常に細かい粒度の断片に分割することができる。しかしながら、更なる最適化を行わずに分割化を行うと実行時性能が低下するおそれがあるので、安全パーティションの併合および関数のキャッシュは、プログラムの分割化により発生する実行時オーバヘッドを低減させる二つの最適化である。
【００６７】
本書に記載の本発明の多くの変形例および他の実施形態は、上記説明および添付図面に示す記載内容の利益を有するこれらの発明が関連する当業者によって想起されるであろう。このため、本発明は多くの形態で実施することができ、上記の実施形態に限定されるものではないことが当業者には分かる。したがって、本発明は上記の具体的な実施形態に限定されるものではなく、変形例および他の実施形態は特許請求の範囲に含まれるものである。本書では具体的な用語を用いているが、これらの用語は一般的かつ説明的な意味で用いているにすぎず、限定するためのものではない。
【図面の簡単な説明】
【００６８】
このように、本発明を一般的な用語で説明してきたが、ここで、添付図面を参照する。尚、これらの図面は必ずしも一定のスケールで描かれているものではない。
【図１Ａ】プログラムの制御流れ情報を漏らす基本的な分割アルゴリズムの例を示す図である。
【図１Ｂ】図１Ａの基本的な分割アルゴリズムのブロック図の制御流れ図である。
【図２】本発明の一実施形態に係るプログラム分割システムを示すブロック図である。
【図３】本発明の一態様に係る、モバイルプログラム内の再帰関数と非再帰関数を見つけるＣ言語のアルゴリズムを示す図である。
【図４】本発明の一実施形態に係る、再帰関数と非再帰関数を識別する図３のアルゴリズムによって実行されるステップを示すブロック図の流れ図である。
【図５】本発明の一例に係る関数呼び出しを構成する安全パーティションの例を示す図である。
【図６Ａ】本発明の一例に係るループを構成する制御流れ図である。
【図６Ｂ】本発明の一例に係る別の制御流れ図である。
【図７】本発明の一態様に係る非再帰関数を分割するＣ言語のアルゴリズムを示す図である。
【図８】本発明の一態様に係る再帰関数を分割するＣ言語のアルゴリズムを示す図である。
【図９】本発明の一態様に係る、非デリファレンスデータアクセスのデータを分割するＣ言語のアルゴリズムを示す図である。
【図１０】本発明の一態様に係る、非ヒープオブジェクトへのデリファレンスデータアクセスのデータを分割するＣ言語のアルゴリズムを示す図である。
【図１１】本発明の一態様に係る最小安全パーティションを併合するＣ言語のアルゴリズムを示す図である。
【図１２】本発明の一態様に係る、関数のキャッシュに用いられるＣ言語のトレース分析アルゴリズムを示す図である。
【図１３Ａ】本発明の一態様に係る、更新キャッシュ関数呼び出しが必要ない場合の関数呼び出しの例を示す図である。
【図１３Ｂ】本発明の一態様に係る、更新キャッシュ関数呼び出しが必要ない場合の関数呼び出しの例を示す図である。
【図１４】本発明の一態様に係る、更新キャッシュ関数呼び出しが必要かどうかを判定するＣ言語のアルゴリズムを示す図である。
【図１Ａ】
2005528689.tif 000003
【図１Ｂ】
2005528689.tif 000004
【図２】
2005528689.tif 000005
【図３】
2005528689.tif 000006
【図４】
2005528689.tif 000007
【図５】
2005528689.tif 000008
2005528689.tif 000009
【図７】
2005528689.tif 000010
【図８】
2005528689.tif 000011
【図９】
2005528689.tif 000012
【図１０】
2005528689.tif 000013
【図１１】
2005528689.tif 000014
【図１２】
2005528689.tif 000015
【図１３Ａ】
2005528689.tif 000016
【図１３Ｂ】
2005528689.tif 000017
【図１４】
2005528689.tif 000018
【国際調査報告】
2005528689.tif 000019
2005528689.tif 000020
2005528689.tif 000021