(57)【要約】【課題】プログラム中に含まれる複数の変数あるいは複数の式からなる条件文についても的確に検出することができるプログラム解析方法およびプログラムを提供する。【解決手段】プログラム内に、複数の変数を含む条件文が与えられているときに、用いられている最大の係数あるいは最大の法を選択して、その値をｐとし、条件文に用いられている複数の変数に対して、それぞれの変数の値を０からｐ−１の値に設定して、設定したすべての値について、ｍｏｄｐにおける条件文が常に真もしくは偽となるか否かを判断する。【選択図】図１
2008102576.tif 000002
【特許請求の範囲】
【請求項１】
抽象解釈を用いて、複数の変数あるいは複数の式からなり、常に真または偽と判定される条件文をプログラム内から検出するプログラム解析方法。
【請求項２】
プログラム内に、複数の変数を含む条件文が与えられているときに、
用いられている最大の係数あるいは最大の法を選択して、その値をｐとする第１のステップと、
条件文に用いられている複数の変数に対して、それぞれの変数の値を０からｐ−１の値に設定する第２のステップと、
設定したすべての値について、ｍｏｄ＿ｐにおける条件文が常に真もしくは偽となるか否かを判断する第３のステップと、
を備えたことを特徴とするプログラム解析方法。
【請求項３】
プログラム内に、複数の式からなる条件文が与えられているときに、
用いられているすべての法の最小公倍数をｐと設定する第１のステップと、
条件文に用いられている複数の変数に対して、それぞれの変数の値を０からｐ−１の値に設定する第２のステップと、
設定したすべての値について、ｍｏｄ＿ｐにおける条件文が常に真もしくは偽となるか否かを判断する第３のステップと、
を備えたことを特徴とするプログラム解析方法。
【請求項４】
プログラム内に、複数の変数を含む条件文が与えられているときに、
用いられている最大の係数あるいは最大の法を選択して、その値をｐとする第１のステップと、
条件文に用いられている複数の変数に対して、それぞれの変数の値を０からｐ−１の値に設定する第２のステップと、
設定したすべての値について、ｍｏｄ＿ｐにおける条件文が常に真もしくは偽となるか否かを判断する第３のステップと、
をコンピュータに実行させるためのプログラム。
【請求項５】
プログラム内に、複数の式からなる条件文が与えられているときに、
用いられているすべての法の最小公倍数をｐと設定する第１のステップと、
条件文に用いられている複数の変数に対して、それぞれの変数の値を０からｐ−１の値に設定する第２のステップと、
設定したすべての値について、ｍｏｄ＿ｐにおける条件文が常に真もしくは偽となるか否かを判断する第３のステップと、
をコンピュータに実行させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、抽象解釈を用いたプログラム解析方法およびプログラムに関する。
【背景技術】
【０００２】
一般に、プログラムには、利用者に対して秘密にすべきアルゴリズムを含む場合がある。こうした秘密にすべきアルゴリズムを利用者による解析から守るためには、何らかの対策を講じる必要がある。
【０００３】
その対応策の一つとして、プログラムの機能を保ちつつ、解析を困難にする難読化と呼ばれる手法があり、プログラム内の制御構造を複雑にしたり、プログラム内にダミーコードを挿入したりする方法が知られている。こうしたプログラムの難読化を実現するためには、ｏｐａｑｕｅ  ｐｒｅｄｉｃａｔｅと呼ばれる、常に真あるいは偽と判定される条件文を用いることが必要である。
【０００４】
具体的には、常に真と判定される条件分岐ブロックの中に、命令文を移動したり、常に偽と判定される条件分岐ブロックの中に、ダミーコードを挿入する等の処理を施すことによってプログラムの解析を困難にすることができる。
【０００５】
一方で、上記のように難読化されたプログラムに対して、抽象解釈を用いて、プログラム中のｏｐａｑｕｅ  ｐｒｅｄｉｃａｔｅを検出する方法が提案されている（例えば、非特許文献１参照。）。
【非特許文献１】Ｍｉｌａ  Ｄａｌｌａ  Ｐｒｅｄａ  ａｎｄ  Ｒｏｂｅｒｔｏ  Ｇｉａｃｏｂａｚｚｉ、“Ｏｐａｑｕｅ  Ｐｒｅｄｉｃａｔｅｓ  Ｄｅｔｅｎｔｉｏｎ  ｂｙ  Ａｂｓｔｒａｃｔ  Ｉｎｔｅｒｐｒｅｔａｔｉｏｎ、”Ｐｒｏｃ．ｏｆ  ＥＡＡＩ  ２００６．
【発明の開示】
【発明が解決しようとする課題】
【０００６】
しかしながら、上記の従来の方法では、ある与えられた関数ｆ（ｘ）がすべての整数ｘに対して、ｎで割り切れるかどうかのみに対する判定方法が示されているのみである。すなわち、上記の従来の方法においては、１つの変数のみが含まれる単一の式から構成されるｏｐａｑｕｅ  ｐｒｅｄｉｃａｔｅのみをその対象としている。そのため、複数の変数を含む条件文、例えば、「すべての整数ｘ、ｙに対して、７ｘ2−ｙ2≠１」や「すべての整数に対して、２｜ｘ2＋ｘ＋ｙ」等の条件文を検出することができないという問題があった。
【０００７】
そこで、本発明は、上述の課題に鑑みてなされたものであり、プログラム中に含まれる複数の変数あるいは複数の式からなる条件文についても、これらを的確に検出することができるプログラム解析方法およびプログラムを提供することを目的とする。
【課題を解決するための手段】
【０００８】
本発明は、上記の課題を解決するために以下の事項を提案している。
（１）本発明は、抽象解釈を用いて、複数の変数あるいは複数の式からなり、常に真または偽と判定される条件文をプログラム内から検出するプログラム解析方法を提案している。
【０００９】
この発明によれば、抽象解釈を用いることにより、プログラム内にある単一の変数からなる条件文のみならず、複数の変数あるいは複数の式からなる条件文についてもこれらを的確に検出することができる。
【００１０】
（２）本発明は、プログラム内に、複数の変数を含む条件文が与えられているときに、用いられている最大の係数あるいは最大の法を選択して、その値をｐとする第１のステップ（例えば、図１のステップＳ１０１に相当）と、条件文に用いられている複数の変数に対して、それぞれの変数の値を０からｐ−１の値に設定する第２のステップ（例えば、図１のステップＳ１０２に相当）と、設定したすべての値について、ｍｏｄ＿ｐにおける条件文が常に真もしくは偽となるか否かを判断する第３のステップ（例えば、図１のステップＳ１０３からステップＳ１０６に相当）と、を備えたことを特徴とするプログラム解析方法を提案している。
【００１１】
この発明によれば、プログラム内に、複数の変数を含む条件文が与えられているときに、用いられている最大の係数あるいは最大の法を選択して、その値をｐとし、条件文に用いられている複数の変数に対して、それぞれの変数の値を０からｐ−１の値に設定して、設定したすべての値について、ｍｏｄ＿ｐにおける条件文が常に真もしくは偽となるか否かを判断する。
【００１２】
したがって、複数の変数を含む条件文がプログラム内に存在する場合であっても、この条件文を的確に検出することができる。
【００１３】
（３）本発明は、プログラム内に、複数の式からなる条件文が与えられているときに、用いられているすべての法の最小公倍数をｐと設定する第１のステップ（例えば、図４のステップＳ４０１に相当）と、条件文に用いられている複数の変数に対して、それぞれの変数の値を０からｐ−１の値に設定する第２のステップ（例えば、図４のステップＳ４０２に相当）と、設定したすべての値について、ｍｏｄ＿ｐにおける条件文が常に真もしくは偽となるか否かを判断する第３のステップ（例えば、図４のステップＳ４０３からステップＳ４０６に相当）と、を備えたことを特徴とするプログラム解析方法を提案している。
【００１４】
この発明によれば、プログラム内に、複数の式からなる条件文が与えられているときに、用いられているすべての法の最小公倍数をｐと設定し、条件文に用いられている複数の変数に対して、それぞれの変数の値を０からｐ−１の値に設定して、設定したすべての値について、ｍｏｄ＿ｐにおける条件文が常に真もしくは偽となるか否かを判断する。
【００１５】
したがって、複数の式からなる条件文がプログラム内に存在する場合であっても、この条件文を的確に検出することができる。
【００１６】
（４）本発明は、プログラム内に、複数の変数を含む条件文が与えられているときに、用いられている最大の係数あるいは最大の法を選択して、その値をｐとする第１のステップ（例えば、図１のステップＳ１０１に相当）と、条件文に用いられている複数の変数に対して、それぞれの変数の値を０からｐ−１の値に設定する第２のステップ（例えば、図１のステップＳ１０２に相当）と、設定したすべての値について、ｍｏｄ＿ｐにおける条件文が常に真もしくは偽となるか否かを判断する第３のステップ（例えば、図１のステップＳ１０３からステップＳ１０６に相当）と、をコンピュータに実行させるためのプログラムを提案している。
【００１７】
この発明によれば、プログラム内に、複数の変数を含む条件文が与えられているときに、コンピュータにより、用いられている最大の係数あるいは最大の法を選択して、その値をｐとし、条件文に用いられている複数の変数に対して、それぞれの変数の値を０からｐ−１の値に設定して、設定したすべての値について、ｍｏｄ＿ｐにおける条件文が常に真もしくは偽となるか否かを判断する。
【００１８】
したがって、複数の変数を含む条件文がプログラム内に存在する場合であっても、この条件文を的確に検出することができる。
【００１９】
（５）本発明は、プログラム内に、複数の式からなる条件文が与えられているときに、用いられているすべての法の最小公倍数をｐと設定する第１のステップ（例えば、図４のステップＳ４０１に相当）と、条件文に用いられている複数の変数に対して、それぞれの変数の値を０からｐ−１の値に設定する第２のステップ（例えば、図４のステップＳ４０２に相当）と、設定したすべての値について、ｍｏｄ＿ｐｐにおける条件文が常に真もしくは偽となるか否かを判断する第３のステップ（例えば、図４のステップＳ４０３からステップＳ４０６に相当）と、をコンピュータに実行させるためのプログラムを提案している。
【００２０】
この発明によれば、プログラム内に、複数の式からなる条件文が与えられているときに、コンピュータにより、用いられているすべての法の最小公倍数をｐと設定し、条件文に用いられている複数の変数に対して、それぞれの変数の値を０からｐ−１の値に設定して、設定したすべての値について、ｍｏｄ＿ｐにおける条件文が常に真もしくは偽となるか否かを判断する。
【００２１】
したがって、複数の式からなる条件文がプログラム内に存在する場合であっても、この条件文を的確に検出することができる。
【発明の効果】
【００２２】
本発明によれば、プログラム内にある単一の変数からなる条件文のみならず、複数の変数あるいは複数の式からなる条件文についてもこれらを的確に検出することができるという効果がある。
【００２３】
また、上記のような条件文を自動的に検出することにより、プログラム解析の観点から、冗長な条件分岐やダミーコードを除去することができるため、プログラムの解析がより容易になるという効果がある。
【００２４】
さらに、上記のような条件文を自動的に検出することにより、プログラムの保護の観点から、脆弱な条件文を検出して、これをより強固な条件文に置き換えることにより、プログラムの保護強化を図ることができるという効果がある。
【発明を実施するための最良の形態】
【００２５】
以下、本発明の実施形態について、図面を用いて、詳細に説明する。
なお、本実施形態における構成要素は適宜、既存の構成要素等との置き換えが可能であり、また、他の既存の構成要素との組合せを含む様々なバリエーションが可能である。したがって、本実施形態の記載をもって、特許請求の範囲に記載された発明の内容を限定するものではない。
【００２６】
＜第１の実施形態＞
図１を用いて、本実施形態の処理について説明する。
なお、本実施形態は、プログラム中に存在する複数の変数を含む条件文を検出するプログラムの解析方法を示したものである。
【００２７】
＜処理フロー＞
本実施形態の処理は、図１に示すように、まず、条件文に用いられている最大の係数もしくは最大の法を選択し、この値をｐとする（ステップＳ１０１）。次に、条件文に用いられている複数の変数に対して、それぞれの変数の値を０からｐ−１に設定する（ステップＳ１０２）
【００２８】
さらに、設定した値に対して、ｍｏｄ＿ｐにおける条件文の真偽を確認する（ステップＳ１０３）。そして、ｐｎ回の試行において、条件文が常に真または偽になるかを判定し（ステップＳ１０４）、条件文が常に真または偽になると判定した場合には、この条件文がｏｐａｑｕｅ  ｐｒｅｄｉｃａｔｅであると判断する（ステップＳ１０５）。一方で、条件文が常に真または偽にならないと判定した場合には、この条件文がｏｐａｑｕｅ  ｐｒｅｄｉｃａｔｅでないと判断する（ステップＳ１０６）。
【００２９】
したがって、本実施形態によれば、上記の処理を実行することにより、複数の変数を含む条件文がプログラム内に存在する場合であっても、この条件文がｏｐａｑｕｅ  ｐｒｅｄｉｃａｔｅであるか否かを的確に検出することができる。
【００３０】
次に、具体的な事例を用いた判定方法について説明する。
＜実施例１＞
本実施例では、複数の変数を含む条件文「すべての整数ｘ、ｙに対して、ａｘ2−ｂｙ2≠ｃ」について、その判定方法を図２を用いて説明する。
【００３１】
まず、ａとｂが、ａ＞ｂなる関係にあるかどうかを判断する（ステップＳ２０１）。ここで、ａ＞ｂである場合（ステップＳ２０１の「Ｙｅｓ」）には、ｙ＝０、１、２、・・・ａ−１において、−ｂｙ2＝ｃ％ａがすべてｙに対して成立するか否かを判定する（ステップＳ２０２）。なお、ここで、「ｃ％ａ」とは、ｃをａで割ったときの剰余である。
【００３２】
そして、ｙ＝０、１、２、・・・ａ−１において、−ｂｙ2＝ｃ％ａがすべてｙに対して成立する場合には、この条件文がｏｐａｑｕｅ  ｐｒｅｄｉｃａｔｅであると判断する（ステップＳ２０３）。一方、ｙ＝０、１、２、・・・ａ−１において、−ｂｙ2＝ｃ％ａがすべてｙに対して成立しない場合には、この条件文がｏｐａｑｕｅ  ｐｒｅｄｉｃａｔｅでないと判断する（ステップＳ２０４）。
【００３３】
また、ａとｂが、ａ≦ｂの関係にある場合（ステップＳ２０１の「Ｎｏ」）には、ｘ＝０、１、２、・・・ｂ−１において、ａｘ2＝ｃ％ｂがすべてｘに対して成立するか否かを判定する（ステップＳ２０５）。なお、ここで、「ｃ％ｂ」とは、ｃをｂで割ったときの剰余である。
【００３４】
そして、ｘ＝０、１、２、・・・ｂ−１において、ａｘ2＝ｃ％ｂがすべてｘに対して成立する場合には、この条件文がｏｐａｑｕｅ  ｐｒｅｄｉｃａｔｅであると判断する（ステップＳ２０７）。一方、ｘ＝０、１、２、・・・ｂ−１において、ａｘ2＝ｃ％ｂがすべてｘに対して成立しない場合には、この条件文がｏｐａｑｕｅ  ｐｒｅｄｉｃａｔｅでないと判断する（ステップＳ３０６）。
【００３５】
以上のように、上記のタイプの条件文の場合には、ｍａｘ｛ａ、ｂ｝回の試行により、条件文がｏｐａｑｕｅ  ｐｒｅｄｉｃａｔｅであるか否かを判定することができる。例えば、条件文「７ｘ2−ｙ2≠１」がｏｐａｑｕｅ  ｐｒｅｄｉｃａｔｅであるかどうかを判定する際には、上記のａ＞ｂなる関係であることから、−ｙ2≠１がｙ＝０、１、２、３、４、５、６に対して成立するか否かを判定する。なお、本例では、すべてのｙに対して、−ｙ2≠１が成立するため、この条件文は、ｏｐａｑｕｅ  ｐｒｅｄｉｃａｔｅであると判断することができる。
【００３６】
＜実施例２＞
本実施例では、複数の変数を含む条件文「ｐ｜ｆ（ｘ１、ｘ２、・・・、ｘｎ）」について、その判定方法を図３を用いて説明する。
【００３７】
まず、条件文に用いられている変数（ｘ１、ｘ２、・・・、ｘｎ）に対して、それぞれの変数の値に、０からｐ−１の値を独立に設定したとき、すなわち、ｐｎ回の試行を行ったときに、条件文が常に真または偽になるか否かを判定する（ステップＳ３０１）。
【００３８】
そして、ｐｎ回の試行において、条件文「ｐ｜ｆ（ｘ１、ｘ２、・・・、ｘｎ）」が、常に真もしくは偽である場合（ステップＳ３０１の「Ｙｅｓ」）には、この条件文がｏｐａｑｕｅ  ｐｒｅｄｉｃａｔｅであると判断する（ステップＳ３０２）。一方で、ｐｎ回の試行において、条件文「ｐ｜ｆ（ｘ１、ｘ２、・・・、ｘｎ）」が、常に真もしくは偽でない場合（ステップＳ３０１の「Ｎｏ」）には、この条件文がｏｐａｑｕｅ  ｐｒｅｄｉｃａｔｅでないと判断する（ステップＳ３０３）。
【００３９】
以上のように、上記のタイプの条件文の場合には、ｐｎ回の試行を実行することにより、条件文がｏｐａｑｕｅ  ｐｒｅｄｉｃａｔｅであるか否かを判定することができる。例えば、条件文「２｜ｘ2＋ｘ＋４ｙ」がｏｐａｑｕｅ  ｐｒｅｄｉｃａｔｅであるかどうかを判定する際には、（ｘ、ｙ）＝（０、０）、（０、１）、（１、０）、（１、１）について、条件文「２｜ｘ2＋ｘ＋４ｙ」が成立するか否かを判断する。
【００４０】
＜第２の実施形態＞
図４を用いて、本実施形態の処理について説明する。
なお、本実施形態は、プログラム中に存在する複数の式を含む条件文を検出するプログラムの解析方法を示したものである。
【００４１】
＜処理フロー＞
本実施形態の処理は、図４に示すように、まず、条件文に用いられているすべての法の最小公倍数をｐとする（ステップＳ４０１）。次に、条件文に用いられている複数の変数に対して、それぞれの変数の値を０からｐ−１に設定する（ステップＳ４０２）。
【００４２】
さらに、設定した値に対して、ｍｏｄｐにおける条件文の真偽を確認する（ステップＳ４０３）。そして、ｐｎ回の試行において、条件文が常に真または偽であるか否かを判定し（ステップＳ４０４）、条件文が常に真または偽である場合（ステップＳ４０４の「Ｙｅｓ」）には、この条件文がｏｐａｑｕｅ  ｐｒｅｄｉｃａｔｅであると判断する（ステップＳ４０５）。一方で、条件文が常に真または偽にならないと判定した場合には、この条件文がｏｐａｑｕｅ  ｐｒｅｄｉｃａｔｅでないと判断する（ステップＳ４０６）。
【００４３】
したがって、本実施形態によれば、上記の処理を実行することにより、複数の式を含む条件文がプログラム内に存在する場合であっても、この条件文がｏｐａｑｕｅ  ｐｒｅｄｉｃａｔｅであるか否かを的確に検出することができる。
【００４４】
なお、上記の処理をコンピュータ読み取り可能な記録媒体に記録し、この記録媒体に記録されたプログラムをコンピュータに読み込ませ、実行することによって本発明のプログラム解析方法を自動的に実現することができる。ここでいうコンピュータシステムとは、ＯＳや周辺装置等のハードウェアを含む。
【００４５】
また、「コンピュータシステム」は、ＷＷＷ（Ｗｏｒｌｄ  Ｗｉｄｅ  Ｗｅｂ）システムを利用している場合であれば、ホームページ提供環境（あるいは表示環境）も含むものとする。また、上記プログラムは、このプログラムを記憶装置等に格納したコンピュータシステムから、伝送媒体を介して、あるいは、伝送媒体中の伝送波により他のコンピュータシステムに伝送されても良い。ここで、プログラムを伝送する「伝送媒体」は、インターネット等のネットワーク（通信網）や電話回線等の通信回線（通信線）のように情報を伝送する機能を有する媒体のことをいう。
【００４６】
また、上記プログラムは、前述した機能の一部を実現するためのものであっても良い。さらに、前述した機能をコンピュータシステムにすでに記録されているプログラムとの組合せで実現できるもの、いわゆる差分ファイル（差分プログラム）であっても良い。
【００４７】
以上、この発明の実施形態につき、図面を参照して詳述してきたが、具体的な構成はこの実施形態に限られるものではなく、この発明の要旨を逸脱しない範囲の設計等も含まれる。
【図面の簡単な説明】
【００４８】
【図１】本発明の第１の実施形態に係る処理フローである。
【図２】本発明の実施例１に係る処理フローである。
【図３】本発明の実施例２に係る処理フローである。
【図４】本発明の第２の実施形態に係る処理フローである。
【図１】
2008102576.tif 000003
【図２】
2008102576.tif 000004
【図３】
2008102576.tif 000005
【図４】
2008102576.tif 000006