(57)【要約】【課題】静的解析の手法を採りながらクリティカルなデータを検出する。【解決手段】少なくともメモリとレジスタを備えるコンピュータ上で実行されるプログラムであり、データの読み書きと保持のための領域である通常データ領域と該プログラムの実行を制御するための重要なクリティカルデータが保持される領域とが該メモリ内で完全に分離されないという実行のされ方をするプログラムの解析方法であって、ソフトウェアの脆弱性の中でも最も深刻なクラスの脆弱性の１つで、該通常データ領域への書込み命令が該クリティカルデータへの書込みを生起させるというバッファオーバーフローの脆弱性について、前記プログラムに含まれる該脆弱性の検出を、該プログラムの実行に先立って、該プログラムのソースコードのコンパイル過程で現れる中間言語コードを解析することによって行なう。【選択図】  図１
2004171064.tif 000002
【特許請求の範囲】
【請求項１】
少なくともメモリとレジスタを備えるコンピュータ上で実行されるプログラムであって、データの読み書きと保持のための領域である通常データ領域と該プログラムの実行を制御するための重要なクリティカルデータが保持される領域とが該メモリ内で完全に分離されないという実行のされ方をするプログラムについての解析方法であって、
ソフトウェアの脆弱性の中でも最も深刻なクラスの脆弱性の一つで、該通常データ領域への書込み命令が該クリティカルデータへの書込みを生起させるというバッファオーバーフローの脆弱性について、前記プログラムに含まれる該脆弱性の検出を、該プログラムの実行に先立って、該プログラムのソースコードのコンパイル過程で現れる中間言語コードを解析することによって行なうことを特徴とするバッファオーバーフロー静的解析方法。
【請求項２】
前記プログラムのソースコードのコンパイルによりファイル出力された前記中間言語コードを読み込み、該中間言語コードの字句解析および構文解析を行なう第１のステップと、
前記プログラム実行時にメモリ中のスタック上に現れるデータ構造であり、前記通常データ領域と前記クリティカルデータを含むデータ構造であるフレームの構造を同定し、さらに、お互いに制御が遷移しあう中間言語ブロックの集まりとして記述される前記中間言語コードについて、中間言語ブロックと中間言語ブロック間遷移関係を同定する第２のステップと、
転送元と転送先を含む転送命令文や、遷移の条件式を含む遷移命令文や、関数呼出を示す呼出命令文を構成要素として含む前記中間言語ブロックにおいて、メモリ上の位置とレジスタと演算子の組合せという形をしている転送先について、スタック上を転送先とするような転送命令文を転送先の組合せの形から選び出して危険転送命令文とし、該危険転送命令文の転送先に対する遡及を行なって「領域指定項」＋「指数項」形式の転送先遡及項を求める第３のステップと、
該危険転送命令文の転送元に対する遡及を行なって転送元遡及項を求め、この転送元遡及項の中にメモリ上の特定の位置を含む危険転送命令文を選別して選別危険転送命令文とする第４のステップと、
前記中間言語ブロックのそれぞれが含む前記遷移命令文の条件式に対する遡及を行なって条件式遡及項を求め、該条件式遡及項と前記中間言語ブロック間遷移関係とから、中間言語ブロックに制御が遷移したとき満たされる条件である突入条件についての突入条件遡及項を求める第５のステップと、
前記転送先遡及項における前記「領域指定項」は転送先となっている通常データ領域を示すが、前記フレーム中において、この転送先となっている通常データ領域の位置とクリティカルデータの位置との差分値を求め、該転送先遡及項における前記「指数項」と該差分値が等しいという条件をバッファオーバーフロー条件とする第６のステップと、
前記選別危険転送命令文のそれぞれが属する前記中間言語ブロックの前記突入条件遡及項と前記バッファオーバーフロー条件とを比較して、該突入条件の真から該バッファオーバーフロー条件の偽が演繹される場合に、その選別危険転送命令文を破棄する第７のステップと、
破棄されずに残された選別危険転送命令文のバッファオーバーフロー条件と、該が選別危険転送命令文が属する中間言語ブロックの突入条件遡及項を表示する第８のステップと、
を備えることを特徴とする請求項１のバッファオーバーフロー静的解析方法。
【請求項３】
前記第２のステップにおいて、中間言語関数を構成要素として含む前記中間言語コードから、該中間言語関数のそれぞれに対応して実行時に前記メモリの前記スタック上に現れる前記フレームの構造を同定するサブステップと、前記中間言語ブロックの集合である該中間言語関数から、前記遷移命令文については最大１つだけ含むような前記中間言語ブロックを同定するサブステップと、前記中間言語ブロックのそれぞれが含む前記呼出命令文を抽出して何れの中間言語関数を何れの中間言語関数から呼び出すかを同定して全ての中間言語ブロックについてその情報を集積することにより中間言語関数の呼出関係を同定するサブステップと、前記中間言語ブロックのそれぞれが含む遷移命令文を抽出して何れの中間言語ブロックから何れの中間言語ブロックへ制御が遷移する可能性があるのかを同定して１つの中間言語関数に属する中間言語ブロックの全てについてその情報を集積することにより各中間言語関数に属する中間言語ブロックの間の遷移関係を同定するサブステップと、を備えることを特徴とする請求項２に記載のバッファオーバーフロー静的解析方法。
【請求項４】
前記第３のステップにおける前記危険転送命令文、前記第４のステップにおける前記選別危険転送命令文、前記第５のステップにおける前記遷移命令文に対して行なわれる遡及は、前記転送命令文の列によってデータが転送元から転送先へ転送されていく過程を、転送命令文の列において転送先から転送元へという逆方向に辿ることで遡及項を同定する処理であり、前記第３ないし第５ステップにおける遡及項は、通常データ領域に含まれるデータ項目と前記呼出命令文により呼び出される中間言語間数と演算子とを組み合わせた形式で表現するものであることを特徴とする請求項２に記載のバッファオーバーフロー静的解析方法。
【請求項５】
少なくともメモリとレジスタを備えるコンピュータ上でのプログラムで、該メモリ内でデータ値を読み書きおよび保持するための通常データ領域と、該プログラムの挙動を決定するために重要なクリティカルデータが保持される領域が該メモリ内で完全に分離されないという実行のされ方をするプログラムを実行する際に、該通常データ領域への書込み命令が該クリティカルデータへの書込みを生起させるバッファオーバーフローの脆弱性について、前記プログラムに含まれる該脆弱性の検出を、該プログラムの実行に先立って、該プログラムのソースコードのコンパイル過程で現れる中間言語コードを解析することによって行なうバッファオーバーフロー静的解析プログラムであって、
前記ソースコードのコンパイル過程で出力される前記中間言語コードを読み込み、該中間言語コードの字句解析および構文解析を行なう第１の手順と、
中間言語関数を構成要素として含む前記中間言語コードから、該中間言語関数のそれぞれに対応して実行時に前記メモリの前記スタック上に現れる前記フレームの構造を同定する副手順と、前記中間言語ブロックの集合である該中間言語関数から、前記遷移命令文については最大１つだけ含むような前記中間言語ブロックを同定する副手順と、前記中間言語ブロックのそれぞれが含む前記呼出命令文を抽出して何れの中間言語関数を何れの中間言語関数から呼び出すかを同定して全ての中間言語ブロックについてその情報を集積することにより中間言語関数の呼出関係を同定する副手順と、前記中間言語ブロックのそれぞれが含む遷移命令文を抽出して何れの中間言語ブロックから何れの中間言語ブロックへ制御が遷移する可能性があるのかを同定して１つの中間言語関数に属する中間言語ブロックの全てについてその情報を集積することにより各中間言語関数に属する中間言語ブロックの間の遷移関係を同定する副手順と、を備え、前記通常データ領域とクリティカルデータを含むフレームであって、実行時に前記メモリのスタック上に各中間言語関数に対応して現れるフレームの構造を同定し、各中間言語関数が含む中間言語ブロックを同定し、各中間言語関数に属する前記中間言語ブロック間の遷移関係を同定する第２の手順と、
転送先と転送元を含む転送命令文や、遷移の条件式を含む遷移命令文や、関数呼出を示す呼出命令文を構成要素として含む前記中間言語ブロックにおいて、メモリ上の位置とレジスタと演算子の組合せという形をしている転送先について、スタック上を転送先とする転送命令文を転送先の組合せの形から選び出して危険転送命令文とし、該危険転送命令文の全てについて転送先に対する遡及を行なって「領域指定項」＋「指数項」形式の転送先遡及項を求める第３の手順と、
該危険転送命令文の転送元に対する遡及を行なって転送元遡及項を求め、この転送元遡及項の中に特定のメモリ上の位置を含む危険転送命令文を選別して選別危険転送命令文とする第４の手順と、
前記中間言語ブロックのそれぞれが含む遷移命令文の条件式に対する遡及を行なって条件式遡及項を求め、該条件式遡及項と前記遷移関係とから前記中間ブロックのそれぞれに制御命令が遷移したとき満たされる条件である突入条件についての突入条件遡及項を求める第５の手順と、
前記転送先遡及項における前記「領域指定項」が示す通常データ領域に関して前記フレーム中の該通常データ領域の位置とクリティカルデータの位置との差分値を求め、該転送先遡及項における前記「指数項」と前記差分値が等しいという条件をバッファオーバーフロー条件とする第６の手順と、
前記選別危険転送命令文のそれぞれが属する前記中間言語ブロックの前記突入条件遡及項と前記バッファオーバーフロー条件とを比較して、前記突入条件の真から前記バッファオーバーフロー条件の偽が演繹される場合に、その選別危険転送命令文を破棄する第７の手順と、
破棄されずに残された選別危険転送命令文についてのバッファオーバーフロー条件と、該バッファオーバーフロー条件が属する中間言語ブロックの突入条件遡及項とを表示する第８の手順と、
を備えることを特徴とするバッファオーバーフロー静的解析プログラム。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、バッファオーバーフロー静的解析方法およびプログラムに係り、特に安全性の多少の不安と引き換えに処理速度の高速性を追求したタイプのプログラム言語について、その実行前に、そのプログラムが含むバッファオーバーフローを静的に解析して検出するプログラムに関する。
【０００２】
【従来の技術】
コンピュータのセキュリティ上の欠陥の要因はさまざまであるが、プログラム自体に潜む脆弱性が原因となる場合が少なくない。このような脆弱性の中でも、バッファオーバーフローに関する脆弱性についての報告が多い。また、攻撃者に任意のコードを実行されたりするなどの被害の深刻さが最も目立つのもバッファオーバーフローである。ソフトウェアの記述言語としては、Ｃ＋＋言語を含むＣ言語（共に登録商標）やＪａｖａ（登録商標）が最も普及している。
【０００３】
Ｊａｖａについては言語の設計段階から型安全性に配慮が図られており、バッファオーバーフローを含むプログラム脆弱性の問題は、実装やバイトコード検証系などのようなバーチャルマシン（仮想計算機・仮想記憶装置）の問題に帰着する。実際に、Ｊａｖａプログラムのバッファオーバーフローがセキュリティ上の欠陥として問題となることは少ない。
【０００４】
これに比べて、Ｃプログラムでは、スタックの構造上バッファオーバーフローが発生し易いため、これに起因するセキュリティ上の欠陥の問題は深刻なものがある。Ｃプログラムにおいては、既存のバッファオーバーフロー検出手法が存在しているが、現時点では、プログラム実行前にバッファオーバーフローを体系的に検出する方法や、バッファオーバーフローを網羅的に検出する方法で成功しているものはない。
【０００５】
上述したＣプログラムにおけるバッファオーバーフローに起因するコンピュータセキュリティの脆弱性の問題について詳しく説明する。コンピュータプログラムの脆弱性の報告例において、プログラムの脆弱性に関するものは、一定の割合を占めている。その中で、最も報告例が多いものは、バッファオーバーフローの問題であり、被害の深刻さが最も目立つものもバッファオーバーフローの問題である。
【０００６】
１９９９年以降２０００年始めまでに、例えばＣＶＥ、ＣＥＲＴ、ＳｅｃｕｒｉｔｙＦｏｃｕｓ．ｃｏｍなどのインターネットの各ウェブサイトに報告された脆弱性情報について、サイト間の重複を除いた正味の報告件数が図１６に示された表に纏められている。これらの報告では、ソフトウェアの不適切な設定や運用により発生する脆弱性が多い。プログラム自体に内在する脆弱性として、バッファオーバーフロー以外で目立つものはフォーマットストリングバグやメモリリークがある。
【０００７】
バッファオーバーフローに対する攻撃とこの攻撃による被害について、被害の深刻さに従って概略的に分類すると、以下の３種類のものがある。被害の軽微な法から順に、第１の被害、第２の被害、第３の被害とする。なお、下記の説明における「プロセス」とは、プログラムを実行する単位のことをいう。
【０００８】
まず、第１の被害は、プロセスの実行を妨害する攻撃に起因するものである。この第１の被害は、攻撃者がプログラム中のバッファオーバーフローを攻撃したときに、そのプロセスがクラッシュすることにより発生する。具体的には、そのプロセスに関連するサービスが停止してしまうなどの被害が出るが、被害の範囲は概ねそのプロセスに関係する部分に限定されており、軽微なものである。
【０００９】
次に、第２の被害は、プロセスの実行を部分的に制御する攻撃に起因するものである。この第２の被害は、攻撃者がプログラム中のバッファオーバーフローを攻撃したときに、そのプロセスにおける制御条件等が書き換えられることにより発生する。具体的な被害は、そのプロセスが稼動しているサイトの資源の枯渇等に繋がる可能性もあり、サイトの全体にわたって被害が広がる虞もあるので、中程度のものである。
【００１０】
最後に、第３の被害は、プロセスを乗っ取る攻撃に起因するものである。この第３の被害は、攻撃者がプログラム中のバッファオーバーフローを攻撃したときに、そのプロセスの実行制御が完全に攻撃者に奪われてしまうことにより発生する。具体的な被害は、攻撃者がそのプロセスの実行権限において攻撃コードを実行できるようになってしまうことである。特に、ルート権限のプロセスにおいてこの第３の被害が発生するような攻撃が行なわれると、サイト全体が攻撃者によって乗っ取られてしまうような最悪の事態をも招き兼ねない。
【００１１】
以上のような被害が生じるバッファオーバーフローの種類と検出対象について説明する。バッファオーバーフローの概括的な定義は、開発者がデータ格納場所として想定したデータ格納領域以外の場所にあふれ出したデータが書き込まれてしまうことをいう。しかしながら、現在では「バッファオーバーフロー」という用語の意味は狭義・広義の２通りの何れかの意味を有するものとして用いられている。
【００１２】
狭義のバッファオーバーフローは、ソフトウェア実行中に作成されるデータ領域の中に存在するコード実行制御に関するクリティカル（重要）な部分に対してデータが書き込まれることをいう。このコード実行制御に関するクリティカルな部分は、Ｃ言語で言えば、スタック中のＲＥＴ（ｒｅｔｕｒｎ）アドレスが代表的なものである。本来は他の部分へ書き込まれるべきデータがこのクリティカルな部分に書き込まれてしまうような脆弱性を狭義のバッファオーバーフローとする。攻撃者は、狭義のバッファオーバーフローを有するソフトウェアに対しては、上記第１の被害から第３の被害までを結果するような攻撃を行なうことができる。この狭義のバッファオーバーフローを発生させるような攻撃者からの攻撃のことをスタック・スマッシング（ｓｔａｃｋ  ｓｍａｓｈｉｎｇ）とも呼んでいる。
【００１３】
広義のバッファオーバーフローは、クリティカルな部分以外の部分に対してもデータを書き換えることができるような場合をいう。広義のバッファオーバーフローを有するソフトウェアに対しては、攻撃者は第１の被害を結果するような攻撃を行なうことができ、また、場合によっては、上記第２の被害を結果するような攻撃が行なわれる可能性もある。
【００１４】
広義のバッファオーバーフローを完全に検出することができるのであれば、狭義のバッファオーバーフローを検出する方法を考える意義は薄れるが、後述する広義のバッファオーバーフローを検出する幾つかの方法が何れも欠陥を含んでいること、広義のバッファオーバーフローに比べて狭義のバッファオーバーフローを突かれた場合の被害の方が甚大であり検出ツールの提案に対する差し迫ったニーズがあること、広義よりも狭義のバッファオーバーフローの方が、形態が明確で解析し易いこと、等を考慮すると、狭義のバッファオーバーフロー検出を静的解析の対象とすることは妥当なものである。
【００１５】
この「静的解析」は、Ｃプログラムソースそのもの、またはこのＣソースがコンパイラ等により変換された中間言語の段階でバッファオーバーフローが発生する可能性があるか否かを検出するものであり、中間言語がアッセンブラ等によりさらに変換された機械語をそのプログラムの実行中に検出する動的解析と対比されている。
【００１６】
ソフトウェアの記述言語としてはＪａｖａの伸長もみられるが、依然としてＣプログラムが最も重要なものである。したがって、このＣプログラムにおけるバッファオーバーフロー対策を講じることには大きな意義がある。Ｃプログラムはそのスタックの構造が単純であるため、バッファオーバーフローが発生し易い。Ｃプログラムは、安全性よりも処理速度に重点をおいた言語であるため、実行時のデータ構造をなるべく単純にして、それに対する安全性のチェックを行なわないことが処理系設計の際の基本設計となっており、バッファオーバーフローに対する安全性はこの基本思想とトレードオフの関係になっている。
【００１７】
Ｃプログラムにおけるバッファオーバーフローを検出する従来の検出方法または検出ツールとしては、バッファオーバーフローが内在することが判明している標準ライブラリ中の関数（例えば、ｓｔｒｃｐｙ等）があり、ソースコードで探索して見つけ出してより安全な関数に書き換えるためのツールを用いる手法、スタック中のＲＥＴアドレスの近傍にダミーデータを配置してその値を監視する手法、ソースプログラム中の注釈や機械語コードを解析する手法がある。
【００１８】
【発明が解決しようとする課題】
しかしながら、これら従来の検出方法やツールは、バッファオーバーフローにおける常習的な原因となる標準ライブラリ関数を見つけるだけのものであり、プログラマが作成したプログラム部分に起因するバッファオーバーフローを見つけるものではない。したがって、ユーザプログラミングを含むプログラムのバッファオーバーフロー検出ツールとしては全く不十分である。ただし、このようなツールを用いて標準ライブラリ中の危険な関数を置き換えておくことは、プログラムの脆弱性をなくす上では必要条件であるとはいえる。
【００１９】
スタック中のＲＥＴアドレスの近傍にダミーデータを配置しておいて、プログラム実行時にそのダミーデータが書換わるか否かを常時監視して、書換わった場合にはＲＥＴアドレスも書換えられた可能性があるものとしてユーザに知らせるツールが提案されており、代表的なものとしてはスタックガード（Ｓｔａｃｋ  Ｇｕａｒｄ）などがある。また、ＩＢＭ社のプロポリス（Ｐｒｏ  Ｐｏｌｉｃｅ）もこの系列に属するツールである。
【００２０】
なお、このダミーデータをスタックガードにおいては、「カナリア」と呼んでいるので、以下、このダミーデータのことをカナリアと呼び、ダミーデータを埋め込むこの方式をカナリア方式と呼ぶことにする。このように、プログラム実行時にバッファオーバーフローを検出することを「動的検出」というが、この動的検出には以下のような問題があった。
【００２１】
まず、ダミーデータが書き換えられるか否かを常時監視することにより、プログラムの実行速度の低下が大きくなり、プログラムの安全性よりも実行時の処理速度の高速化を志向するＣ言語の設計方針とは矛盾することになる。また、デバッグ段階ではなく実用段階でこのツールを使用することには問題がある。
【００２２】
バッファオーバーフローを動的に検出するということは、プログラムへの特定の入力時にバッファオーバーフローが発生したことをプログラムの実行時に事後的に検出することであり、バッファオーバーフローの発生場所や、プログラムへの入力を含むバッファオーバーフローの発生条件などを網羅的に検出するものではない。
【００２３】
カナリア方式のツールを用いてバッファオーバーフローを完全に防止することは動的解析にあっては原理的に不可能であり、また、ツールを繰り返し適用してデバッグに時間を費やしてバッファオーバーフローを１つずつ取り除いていくとしても、プログラムがどの程度安全になったのかを保証することができる理論的な根拠が確立されたとはいえない。
【００２４】
狭義のバッファオーバーフローを検出する場合、スタック上での書き換えがスタック上のＲＴＥアドレスの位置に来るか否かが重要である。ダミーデータであるカナリアを埋め込む場合は、カナリアを埋め込まない通常の場合と比較するとＲＥＴアドレスの位置を狂わせてしまうことになる。したがって、カナリアを埋め込まない場合に発生する可能性のある狭義のバッファオーバーフローを検出することができないという問題がある。
【００２５】
ソースコード中の注釈を利用して、静的解析によりバッファオーバーフローを検出する方法としてエルシーエルイント（ＬＣＬｉｎｔ）がある。このようなソースコード以外の部分にプログラマが付加的情報を与える方法においては、適切な付加的情報が与えられた場合には効果を発揮するが、このような適切な付加的情報を与えることは、プログラマに多大の負荷を掛けることになり、特に大規模なプログラムの場合にはその負荷は無視することができないほど甚大である。エルシーエルイント（ＬＣＬｉｎｔ）自体は解析対象を特定の関数に限定しているために、その関数を検出することができるバッファオーバーフローは限られている。
【００２６】
機械語に操作的な意味を与えて機械語コードを抽出して解釈することにより、バッファオーバーフローを検出する方法が提案されている。元のソースコードがどのような言語で記述されているのかに関係なく検出が可能な方法であるが、実際にバッファオーバーフローが問題となっているソフトウェアはＣプログラムが多いため、Ｃ言語の場合には機械語でなく中間言語を解析対象とすればよい。
【００２７】
もしも機械語を検出対象にした場合には、異なる機械語セット毎に操作的意味を与える必要もあり、また、バッファオーバーフローを検出することができたとしてもどのような構造が原因となってバッファオーバーフローが発生したのかを特定することには非常な困難が伴うものであると考えられる。解析の対象を中間言語とすれば、このような問題を回避することができる。
【００２８】
この発明は上記問題点を除去するためになされたものであり、プログラムのソースコードから機械語コードへのコンパイル過程で現れる中間言語コードを静的に解析することで、そのプログラムに潜在するバッファオーバーフロー脆弱性を検出する、正確には、バッファオーバーフローが生起する条件を求めることができるバッファオーバーフロー静的解析方法およびプログラムを提供することを目的としている。
【００２９】
【課題を解決するための手段】
この発明の第１の基本構成に係るバッファオーバーフロー静的解析方法は、少なくともメモリとレジスタを備えるコンピュータ上で実行されるプログラムであって、データの読み書きと保持のための領域である通常データ領域と該プログラムの実行を制御するための重要なクリティカルデータが保持される領域とが該メモリ内で完全に分離されないという実行のされ方をするプログラムについての解析方法であって、ソフトウェアの脆弱性の中でも最も深刻なクラスの脆弱性の一つで、該通常データ領域への書込み命令が該クリティカルデータへの書込みを生起させるというバッファオーバーフローの脆弱性について、前記プログラムに含まれる該脆弱性の検出を、該プログラムの実行に先立って、該プログラムのソースコードのコンパイル過程で現れる中間言語コードを解析することによって行なうことを特徴としている。
【００３０】
この発明に係るバッファオーバーフロー静的解析方法は、上記第１の基本構成を備えるものにおいて、前記プログラムのソースコードのコンパイルによりファイル出力された前記中間言語コードを読み込み、該中間言語コードの字句解析および構文解析を行なう第１のステップと、前記プログラム実行時にメモリ中のスタック上に現れるデータ構造であり、前記通常データ領域と前記クリティカルデータを含むデータ構造であるフレームの構造を同定し、さらに、お互いに制御が遷移しあう中間言語ブロックの集まりとして記述される前記中間言語コードについて、中間言語ブロックと中間言語ブロック間遷移関係を同定する第２のステップと、転送元と転送先を含む転送命令文や、遷移の条件式を含む遷移命令文や、関数呼出を示す呼出命令文を構成要素として含む前記中間言語ブロックにおいて、メモリ上の位置とレジスタと演算子の組合せという形をしている転送先ついて、スタック上を転送先とするような転送命令文を転送先の組合せの形から選び出して危険転送命令文とし、該危険転送命令文の転送先に対する遡及を行なって「領域指定項」＋「指数項」形式の転送先遡及項を求める第３のステップと、該危険転送命令文の転送元に対する遡及を行なって転送元遡及項を求め、この転送元遡及項の中にメモリ上の特定の位置を含む危険転送命令文を選別して選別危険転送命令文とする第４のステップと、前記中間言語ブロックのそれぞれが含む前記遷移命令文の条件式に対する遡及を行なって条件式遡及項を求め、該条件式遡及項と前記中間言語ブロック間遷移関係とから、中間言語ブロックに制御が遷移したとき満たされる条件である突入条件についての突入条件遡及項を求める第５のステップと、前記転送先遡及項における前記「領域指定項」は転送先となっている通常データ領域を示すが、前記フレーム中において、この転送先となっている通常データ領域の位置とクリティカルデータの位置との差分値を求め、該転送先遡及項における前記「指数項」と該差分値が等しいという条件をバッファオーバーフロー条件とする第６のステップと、前記選別危険転送命令文のそれぞれが属する前記中間言語ブロックの前記突入条件遡及項と前記バッファオーバーフロー条件とを比較して、該突入条件の真から該バッファオーバーフロー条件の偽が演繹される場合に、その選別危険転送命令文を破棄する第７のステップと、破棄されずに残された選別危険転送命令文のバッファオーバーフロー条件と、該が選別危険転送命令文が属する中間言語ブロックの突入条件遡及項を表示する第８のステップと、を備えることを特徴としても良い。
【００３１】
上記第１ないし第８のステップを含む構成に係るものにおいて、前記第２のステップにおいて、中間言語関数を構成要素として含む前記中間言語コードから、該中間言語関数のそれぞれに対応して実行時に前記メモリの前記スタック上に現れる前記フレームの構造を同定するサブステップと、前記中間言語ブロックの集合である該中間言語関数から、前記遷移命令文については最大１つだけ含むような前記中間言語ブロックを同定するサブステップと、前記中間言語ブロックのそれぞれが含む前記呼出命令文を抽出して何れの中間言語関数を何れの中間言語関数から呼び出すかを同定して全ての中間言語ブロックについてその情報を集積することにより中間言語関数の呼出関係を同定するサブステップと、前記中間言語ブロックのそれぞれが含む遷移命令文を抽出して何れの中間言語ブロックから何れの中間言語ブロックへ制御が遷移する可能性があるのかを同定して１つの中間言語関数に属する中間言語ブロックの全てについてその情報を集積することにより各中間言語関数に属する中間言語ブロックの間の遷移関係を同定するサブステップと、を備えることを特徴としても良い。
【００３２】
また、上記第１ないし第８のステップを備えるバッファオーバーフロー静的解析方法において、前記第３のステップにおける前記危険転送命令文、前記第４のステップにおける前記選別危険転送命令文、前記第５のステップにおける前記遷移命令文に対して行なわれる遡及は、前記転送命令文の列によってデータが転送元から転送先へ転送されていく過程を、転送命令文の列において転送先から転送元へという逆方向に辿ることで遡及項を同定する処理であり、前記第３ないし第５ステップにおける遡及項は、通常データ領域に含まれるデータ項目と前記呼出命令文により呼び出される中間言語間数と演算子とを組み合わせた形式で表現するものであることを特徴とする。
【００３３】
また、本発明の第２の基本構成に係るバッファオーバーフロー静的解析プログラムは、少なくともメモリとレジスタを備えるコンピュータ上のプログラムで、該メモリ内でデータ値を読み書きおよび保持するための通常データ領域と、該プログラムの挙動を決定するために重要なクリティカルデータが保持される領域が該メモリ内で完全に分離されないという実行のされ方をするプログラムを実行する際に、該通常データ領域への書込み命令が該クリティカルデータへの書込みを生起させるバッファオーバーフローの脆弱性について、前記プログラムに含まれる該脆弱性の検出を、該プログラムの実行に先立って、該プログラムのソースコードのコンパイル過程で現れる中間言語コードを解析することによって行なうバッファオーバーフロー静的解析プログラムであって、前記ソースコードのコンパイル過程で出力される前記中間言語コードを読み込み、該中間言語コードの字句解析および構文解析を行なう第１の手順と、中間言語関数を構成要素として含む前記中間言語コードから、該中間言語関数のそれぞれに対応して実行時に前記メモリの前記スタック上に現れる前記フレームの構造を同定する副手順と、前記中間言語ブロックの集合である該中間言語関数から、前記遷移命令文については最大１つだけ含むような前記中間言語ブロックを同定する副手順と、前記中間言語ブロックのそれぞれが含む前記呼出命令文を抽出して何れの中間言語関数を何れの中間言語関数から呼び出すかを同定して全ての中間言語ブロックについてその情報を集積することにより中間言語関数の呼出関係を同定する副手順と、前記中間言語ブロックのそれぞれが含む遷移命令文を抽出して何れの中間言語ブロックから何れの中間言語ブロックへ制御が遷移する可能性があるのかを同定して１つの中間言語関数に属する中間言語ブロックの全てについてその情報を集積することにより各中間言語関数に属する中間言語ブロックの間の遷移関係を同定する副手順と、を備え、前記通常データ領域とクリティカルデータを含むフレームであって、実行時に前記メモリのスタック上に各中間言語関数に対応して現れるフレームの構造を同定し、各中間言語関数が含む中間言語ブロックを同定し、各中間言語関数に属する前記中間言語ブロック間の遷移関係を同定する第２の手順と、転送先と転送元を含む転送命令文や、遷移の条件式を含む遷移命令文や、関数呼出を示す呼出命令文を構成要素として含む前記中間言語ブロックにおいて、メモリ上の位置とレジスタと演算子の組合せという形をしている転送先について、スタック上を転送先とする転送命令文を転送先の組合せの形から選び出して危険転送命令文とし、該危険転送命令文の全てについて転送先に対する遡及を行なって「領域指定項」＋「指数項」形式の転送先遡及項を求める第３の手順と、該危険転送命令文の転送元に対する遡及を行なって転送元遡及項を求め、この転送元遡及項の中に特定のメモリ上の位置を含む危険転送命令文を選別して選別危険転送命令文とする第４の手順と、前記中間言語ブロックのそれぞれが含む遷移命令文の条件式に対する遡及を行なって条件式遡及項を求め、該条件式遡及項と前記遷移関係とから前記中間ブロックのそれぞれに制御命令が遷移したとき満たされる条件である突入条件についての突入条件遡及項を求める第５の手順と、前記転送先遡及項における前記「領域指定項」が示す通常データ領域に関して前記フレーム中の該通常データ領域の位置とクリティカルデータの位置との差分値を求め、該転送先遡及項における前記「指数項」と前記差分値が等しいという条件をバッファオーバーフロー条件とする第６の手順と、前記選別危険転送命令文のそれぞれが属する前記中間言語ブロックの前記突入条件遡及項と前記バッファオーバーフロー条件とを比較して、前記突入条件の真から前記バッファオーバーフロー条件の偽が演繹される場合に、その選別危険転送命令文を破棄する第７の手順と、破棄されずに残された選別危険転送命令文についてのバッファオーバーフロー条件と、該バッファオーバーフロー条件が属する中間言語ブロックの突入条件遡及項とを表示する第８の手順と、を備えることを特徴とする。
【００３４】
【発明の実施の形態】
以下、この発明に係るバッファオーバーフロー静的解析方法およびプログラムの実施形態について添付図面を参照しながら詳細に説明する。まず、この発明のより原理的な構成を備える第１実施形態に係るバッファオーバーフロー静的解析方法について図１のフローチャートを用いて説明する。
【００３５】
第１実施形態に係るバッファオーバーフロー静的解析方法は、少なくともメモリとレジスタを備えるコンピュータ上で実行されるプログラムであって、データの読み書きと保持のための領域である通常データ領域と該プログラムの実行を制御するための重要なクリティカルデータが保持される領域とが該メモリ内で完全に分離されないという実行のされ方をするプログラムについてのバッファオーバーフロー静的解析方法において、ソフトウェアの脆弱性の中でも最も深刻なクラスの脆弱性の一つで、該通常データ領域への書込み命令が該クリティカルデータへの書込みを生起させるというバッファオーバーフローの脆弱性について、前記プログラムに含まれる該脆弱性の検出を、該プログラムの実行に先立って、該プログラムのソースコードのコンパイル過程で現れる中間言語コードを解析することによって行なうことを基本構成としている。
【００３６】
図１に示すように、第１実施形態に係るバッファオーバーフロー静的解析方法は、具体的には、上記の構成の方法において、第１のステップＳＴ１ないし第８のステップＳＴ８を備えている。第１のステップＳＴ１においては、ソースコードをコンパイルして該ソースコードの前記関数に１対１で対応する中間言語関数の定義を含む中間言語コードに変換して、該中間言語コードの字句および構文を解析する。
【００３７】
第２のステップＳＴ２においては、前記通常データ領域とクリティカルデータを含むフレームであって、実行時に前記メモリのスタック上に各中間言語関数に対応して現れるフレームの構造を同定し、各中間言語関数が含む中間言語ブロックを同定し、各中間言語関数に属する前記中間言語ブロック間の遷移関係を同定する。ここで、メモリにおけるスタックは、フレームが積み上げられた構造を有している。実行コードの実行時には、１つの中間言語関数に対応して１つのフレームがメモリのスタック上に現れることになる。
【００３８】
第３のステップＳＴ３においては、転送元と転送先を含む転送命令文や、遷移の条件式を含む遷移命令文や、関数呼出を示す呼出命令文を構成要素として含む前記中間言語ブロックにおいて、メモリ上の位置とレジスタと演算子の組合せという形をしている転送先について、スタック上を転送先とするような転送命令文を転送先の組合せの形から選び出して危険転送命令文とし、該危険転送命令文の転送先に対する遡及を行なって「領域指定項」＋「指数項」形式の転送先遡及項を求める。
【００３９】
第４のステップＳＴ４においては、該危険転送命令文の転送元に対する遡及を行なって転送元遡及項を求め、この転送元遡及項の中に特定のメモリ上の位置を含む危険転送命令文を選別して選別危険転送命令文とする。
【００４０】
第５のステップＳＴ５においては、前記中間言語ブロックのそれぞれが含む遷移命令文の条件式に対する遡及を行なって条件式遡及項を求め、該条件式遡及項と前記遷移関係とから前記中間ブロックのそれぞれに制御命令が遷移したとき満たされる条件である突入条件についての突入条件遡及項を求める。
【００４１】
第６のステップＳＴ６においては、前記転送先遡及項における前記「領域指定項」は転送先となっている通常データ領域を示すが、前記フレーム中において、この転送先となっている通常データ領域の位置とクリティカルデータの位置との差分値を求め、該転送先遡及項における前記「指数項」と該差分値が等しいという条件をバッファオーバーフロー条件とする。
【００４２】
第７のステップＳＴ７においては、前記選別危険転送命令文のそれぞれが属する前記中間言語ブロックの前記突入条件遡及項と前記バッファオーバーフロー条件とを比較して、該突入条件の真から該バッファオーバーフロー条件の偽が演繹される場合に、その選別危険転送命令文を破棄する。
【００４３】
最後に、第８のステップＳＴ８においては、破棄されずに残された選別危険転送命令文についてのバッファオーバーフロー条件と、該バッファオーバーフロー条件が属する中間言語ブロックの突入条件遡及項とを表示する。
【００４４】
以上のような第１実施形態の各ステップを有する本発明に係るバッファオーバーフロー静的解析方法においては、ソースコードを解析するのではなく、また実行コードから動的検出を行なうのでもなく、中間言語コードを静的解析の対象としている。上述のような危険なバッファオーバーフローが発生する条件はフレームとレジスタ群の構造に依存している。フレームの構造とレジスタ群の構造は、中間言語コードの段階で初めて確定され、ソースコードを静的解析したとしても危険なバッファオーバーフローが発生する条件を求めることは困難である。
【００４５】
実行コードの文法や命令セットは、実行されるマシン（コンピュータ）により異なるのに対して、中間言語コードにおいては文法や命令セットがマシンに依存しない。したがって、バッファオーバーフローの静的解析プログラムにおいてマシンに依存しないものを作成するには中間言語コードを静的解析することが必要である。
【００４６】
中間言語コードは、プロローグと、中間言語ブロックと、エピローグと、を含み、一般に中間言語ブロックは複数のブロックを含んでおり、また、中間言語ブロックのラベルであるラベル文も含まれている。
【００４７】
メモリ上の位置とレジスタと演算子の組合せである転送元、および、メモリ上の位置とレジスタと演算子の組合せである転送先については、転送元から転送先への転送を命令する転送命令文により定義されており、この転送命令文は転送元−転送先の関係を示している。
【００４８】
他の関数の呼出を命令する命令文としては、呼出命令文がある。さらに、条件式、条件式が真の場合の遷移先ラベル、条件式が偽の場合の遷移先ラベルを含むような、他の中間言語ブロックへ制御の遷移を命令する遷移命令文もある。中間言語ブロックは、ラベル文、転送命令文の集合、呼出命令文の集合、遷移命令文等を含んでいる。
【００４９】
次に、図２ないし図１５を参照しながら、より詳細な具体例としての本発明の第２実施形態に係るバッファオーバーフロー静的解析プログラムについて説明する。第１実施形態はバッファオーバーフロー静的解析方法に関するものであったが、この第２実施形態は静的解析方法をソフトウェアにより実現するためにバッファオーバーフロー静的解析プログラムに適用したものである。
【００５０】
まず、第２実施形態に係るバッファオーバーフロー静的解析プログラムに関して、コードとマシンの構造について説明する。図２には、プログラムの作成から実行までの形態が左側に示すコードと右側に示すマシンとにより対応して表記されている。
【００５１】
プログラム言語で記述されたソースプログラムは、コンパイラによりコンパイルされるが、その過程で中間言語コードが現れる。この中間言語コードがコンパイラおよびリンカにより処理されて、実行形式である機械語コードになる。機械語コードがマシン上で実行される時、マシンのメモリ上にスタック領域が確保され、そこにフレームというデータ構造をプッシュ（ｐｕｓｈ）およびポップ（ｐｏｐ）することが行なわれる。ヒープ領域や機械語コードを格納するコード領域も確保される。そしてマシン内に用意されたレジスタ群、および、スタックやヒープを書き換えていくことにより計算が進んでいく。このようなプログラムの作成から実行までの形態はＣ言語を始め多くの手続き型プログラミング言語で採用されている。
【００５２】
次に、図３を参照しながら、Ｃプログラミング言語におけるプログラムの作成から実行までの形態について説明する。Ｃ言語のプログラムの作成から実行までの形態は上述した一般の場合に沿ったものである。後の説明に必要な部分をより詳細に記しておく。Ｃプログラムのソースコードは関数の定義を中心とする。Ｃプログラムの場合、中間言語コードはＲＴＬ（Ｒｅｇｉｓｔｅｒ  Ｔｒａｎｓｆｅｒ  Ｌａｎｇｕａｇｅ）コードと呼ばれている。
【００５３】
このＲＴＬコードは、文字通り、レジスタ間のデータ転送という形でコードが記述されている。ソースコードの関数は、ＲＴＬコードの一定のコードの固まりへとコンパイルされるが、これをここでは中間言語関数と呼ぶ。スタックとレジスタ群の細かい構造はこのＲＴＬコードがコンパイラにより生成された時点で決定され、その情報はＲＴＬコードの中に表現されている。
【００５４】
中間言語コードを解析対象とすることは、図４に示す表によりその長所と短所を理解することができる。前述したように、スタックやレジスタが関係する事象を解析するには、ソースコードではなくＲＴＬコードを解析する必要がある。また、機械語コードは、マシン内部での１つ１つの挙動を記述しているために、記述が低レベル過ぎて静的解析には向かないばかりでなく、マシン毎に機械語コードが異なるので、静的解析を行うツールをマシン毎に開発しなければならない。以上の長所・短所をまとめた表が図４に示されている。狭義バッファオーバーフロー検出にはＲＴＬコードを解析対象としなければならない。
【００５５】
次に、フレームの構造について説明する。まず、スタック上のフレームとレジスタの関係について、図５を参照しながら説明する。ＧＣＣ（Ｇｎｕ  Ｃ  Ｃｏｍｐｉｌｅｒ）においてスタック上のフレームとレジスタは次のように用意される。フレームは大きく分けて４つの項目からなるが、項目の並びや大きさ、各項目間に入る余白はコンパイラインストールオプションおよびコンパイルオプションによって異なる。レジスタの本数や種類も含め、ＲＴＬコードが生成された時点でこれらは確定する。ＧＣＣ以外のコンパイラでも上記と同様なことが言える。ＲＥＴアドレス等のクリティカルデータの位置もＲＴＬコードが生成された時点で確定する。
【００５６】
次に、フレームの例について、図６を参照しながら説明する。図６はフレームの例を示しており、図６は、ソースコードの関数Ｓｕｂ＿ｐｒｏｃの呼出しに対応する部分の機械語コードの実行が行なわれた時点でのフレームと、レジスタが指す先を示している。実際は、図中のデータ間に余白が入る。
【００５７】
次に、狭義のバッファオーバーフローとなるコードとその攻撃方法について、図７を参照しながら、説明する。狭義のバッファオーバーフローを起こし得るものは、スタック上の非プリミティブなデータに対する代入である。そのソースコードとしての形は多様であるが、代表的なものは「ａ［ｂ］＝ｃ」という形のものである。この時、このコードが図７の▲１▼▲２▼▲３▼のような条件を満たすと、このコードが狭義のバッファオーバーフローを起こし、攻撃者により図７にあるような攻撃方法で攻撃される。▲２▼や▲３▼を満たすようなソースコードに対応するＲＴＬコードを検出するのがこの第２実施形態に係るプログラムの目的である。
【００５８】
中間言語コードの構造は、図８に示すようになっている。図８において、１つの関数に対するＲＴＬコードは、プロローグとエピローグに挟まれた複数のＲＴＬブロックの形で並んでいる。各ＲＴＬブロックは、先頭のラベル（ｌａｂｅｌ）文と末尾のジャンプ（ｊｕｍｐ）文によって挟まれたセット（ｓｅｔ）文およびコール（ｃａｌｌ）文およびノート（ｎｏｔｅ）文の並びという形をしている。先頭のラベル（ｌａｂｅｌ）文や末尾のジャンプ（ｊｕｍｐ）文が無いＲＴＬブロックも存在する）。ジャンプ（ｊｕｍｐ）文直前のセット文は、ジャンプ（ｊｕｍｐ）文専用に使われるレジスタｃｃ０をセットする。
【００５９】
セット文はＲＴＬコード上では複雑な形をしているが、その本質的な部分を模式とすると図８に示すようになる。セット（ｓｅｔ）文はオブ（ｏｆ）項で示されるデータを（ａｔ）項で示される場所に転送する。オブ（ｏｆ）項とアット（ａｔ）項は、レジスタや定数や演算子を組み合せて表現される。これが、レジスタ転送言語（Ｒｅｇｉｓｔｅｒ  Ｔｒａｎｓｆｅｒ  Ｌａｎｇｕａｇｅ）と呼ばれる所以となっている。コール（ｃａｌｌ）文とジャンプ（ｊｕｍｐ）文も同様に模式として示す。なお、これらＲＴＬコードにおける概念は請求項における次の概念の具体例である。すなわち、セット（ｓｅｔ）文は転送命令文、アット（ａｔ）項は転送元、コール（ｃａｌｌ）文は呼出命令文、ジャンプ（ｊｕｍｐ）文は遷移命令文の具体例である。
【００６０】
次に、第２実施形態に係るバッファオーバーフロー静的解析プログラムの手順について、図９を参照しながら説明する。手順をフローとして図９に示す。ＲＴＬブロックの実行の遷移、ＲＴＬブロック遷移関係、項の形とそれが表すもの、遡及について、以下の手順毎に説明する。なお、大きな手順は、図１の静的解析方法の各ステップに対応しているので、ＳＴ１ないしＳＴ８の符号を重複使用して対応させ、各手順における詳細な副手順については符号２１ないし７１で説明する。
【００６１】
図９において、第１の手順ＳＴ１では、ＲＴＬコードの字句・構文解析が行なわれる。次に、第２の手順ＳＴ２では、中間言語関数の解析が行なわれる。具体的には、副手順２１において、各中間言語関数に対応したフレームが実行時にメモリ上のスタック上に現れるが、ＲＥＴアドレス等のクリティカルデータの位置を含めたフレームの構造（図５およびぞの対応説明参照）を同定する。また、副手順２２においては、各中間言語関数において、中間言語関数が含むＲＴＬブロックを同定する。
【００６２】
次に、手順ＳＴ３でＲＴＬブロックの解析を行なっている。より詳細には、副手順３１において、各ＲＴＬブロックにおいてそのＲＴＬブロックが含むコール（ｃａｌｌ）文を抽出し、どの中間言語関数をどの中間言語関数から呼び出すかを同定して、全ＲＴＬブロックについてその情報を集積することで中間言語関数の呼出関係を同定する。
【００６３】
次に、副手順３２において、各ＲＴＬブロックにおいてそのＲＴＬブロックが含むジャンプ（ｊｕｍｐ）文を抽出し、どのＲＴＬブロックからどのＲＴＬブロックへ制御が遷移する可能性があるかを同定して、一つの中間言語関数に属するＲＴＬブロック全てについてその情報を集積することで、各中間言語関数に属するＲＴＬブロックの間の遷移関係（図１０と図１１および後述するこれらの対応説明を参照）を同定する。
【００６４】
次に、手順ＳＴ４において、バッファオーバーフローを起こしそうなセット（ｓｅｔ）文の選別を行なっている。より詳細には、副手順４１において、メモリ上の位置とレジスタと演算子の組合せであるアット（ａｔ）項はその組合せの形からその（ａｔ）項がスタック上であるかどうか判断できるが（図１２を参照しながら後述する）、各ＲＴＬブロックにおいて、そのようなスタック上をアット（ａｔ）項とする危険セット（ｓｅｔ）文、すなわち、図７の▲２▼を満たすセット（ｓｅｔ）文を選別していることになるが、その全てについて、アット（ａｔ）項に対する遡及を行ない、「領域指定項＋指数項」という形の遡及項を求める。遡及については、図１３および図１４を用いて後述する。
【００６５】
次に、副手順４２において、危険セット（ｓｅｔ）文のオブ（ｏｆ）項に対する遡及を行なってその遡及項を求め、その遡及項の中に、特定のメモリ上の位置が含まれているような危険セット（ｓｅｔ）文を選別して、選別危険セット（ｓｅｔ）文とする。すなわち、図７の▲３▼を満たすセット（ｓｅｔ）文を選別していることになる。
【００６６】
次に、手順ＳＴ５において、ＲＴＬブロック突入条件の抽出を行なう。副手順５１において、各ＲＴＬブロックが含むジャンプ（ｊｕｍｐ）文の条件式に対する遡及を行なって、条件式に対する遡及項を求める。次に、副手順５２において、先に同定したＲＴＬブロック間の遷移関係と、上の条件式の遡及項から、各ＲＴＬブロックの突入条件（図１５を参照して後述する）を遡及項の形で求める。
【００６７】
次に、手順ＳＴ６において、手順ＳＴ４で選別されたセット文についてバッファオーバーフロー条件を抽出する。具体的には、副手順６１において、選別危険セット文のアット項について、その遡及項中の領域指定項はフレーム中にある通常データ領域を表すが、その一をフレーム中のクリティカルデータの一の差分値を求めて、遡及項中の指数項とその差分値が等しいという式をバッファオーバーフロー条件とすることを各線別危険転送命令文に対して行なっている。
【００６８】
次に、手順ＳＴ７において、ブロック突入条件からバッファオーバーフローの生起を検証する。副手順７１において、各選別危険セット（ｓｅｔ）文において、それが属するＲＴＬブロックの突入条件の遡及項とバッファオーバーフロー条件を比べて、前者が満たされている時、後者が満たされないという場合は、その選別危険セット（ｓｅｔ）文を破棄する。
【００６９】
最後に、手順ＳＴ８において、結果を出力する。具体的には、副手順８１において、破棄されずに残っている各選別危険セット（ｓｅｔ）文について、バッファオーバーフロー条件とそれが属するＲＴＬブロックの突入条件の遡及項を表示して結果出力とする。
【００７０】
以上のフローチャートにおける中間言語ブロックの実行の遷移や、遡及、ブロック突入条件などについて、図１０から図１５を参照しながら詳述する。まず、図１０を参照しながら、ＲＴＬブロックの実行の遷移について説明する。
【００７１】
あるブロックに実行が遷移するには、そのブロックへ遷移する可能性のあるブロックにおいてある条件を満たさなければならない。これをＲＴＬブロック突入条件と呼ぶ。例えば、図１０のような模式例の場合、ＲＴＬブロック１００に実行が突入するには、ＲＴＬブロック９９の＠１においてｃｃ０に偽がセット（ｓｅｔ）されＲＴＬブロック９９からＲＴＬブロック１００への遷移が起きるか、ＲＴＬブロック１０１の＠２においてｃｃ０に真がセット（ｓｅｔ）されＲＴＬブロック１０１からＲＴＬブロック１００に遷移が起きる必要がある。
【００７２】
次に、図１１を参照しながら、ＲＴＬブロック遷移関係について説明する。上述したように、ＲＴＬブロックはジャンプ（ｊｕｍｐ）文により遷移するが、どのＲＴＬブロックからどのＲＴＬブロックへの遷移が起こり得るかをグラフにしたのが図１１である。図１０における模式例の場合のＲＴＬブロック遷移関係を示している。
【００７３】
図１２を参照しながら、項の形とそれが表すものについて説明する。セット（ｓｅｔ）文のアット（ａｔ）項やオブ（ｏｆ）項の中には、特定のパターンの項がよく現れる。その形を見ればそれがソースコード上の何を表しているかが分かる。代表的なものが図１２に示されている。特に注目する形は「ｅｂｐ＋負定数＋ｅａｘ等テンポラリレジスタ」という形のもので、これは図７における「スタック上の非プリミティブなデータに対する代入」が行われる際に必ず現れる。この形の項はローカルな領域（配列や構造体等）の指数ｅａｘで示される要素を表している。
【００７４】
次に、図１３および図１４を参照しながら、遡及について説明する。狭義バッファオーバーフローの検出手続きにおいて使われる重要な手続きである遡及についてである。レジスタｅｂｐやｅｓｐは定数との和という形でソースコード内の変数や関数引数等に対応する。一方、テンポラリレジスタ（ｅａｘやｅｃｘやｅｄｘ等）はソースコード内の変数や関数引数等と直接関係ないがセット（ｓｅｔ）文を上に辿っていくことでそれらにたどり着く。ある時点でのレジスタやメモリ上の値が（ソースコード上の変数や関数引数のうち）どのデータから作られたものなのかを求める手続きが遡及である。１つのＲＴＬブロック内で遡及を行うことによって、任意の地点の任意のテンポラリレジスタはソースコード上の変数や関数引数といったデータに辿り着くことになる。遡及の結果、通常データ領域に含まれる項目とコール（ｃａｌｌ）文で呼び出される中間言語関数、および演算子を組み合せた項が得られるが、これを遡及項と呼ぶ。ジャンプ（ｊｕｍｐ）文の条件式も同様な遡及が可能である。
【００７５】
最後に、図１５を参照しながら、ブロック突入条件について説明する。ＲＴＬブロックの遷移関係と各ＲＴＬブロックのジャンプ（ｊｕｍｐ）条件遡及項から、あるＲＴＬブロックに実行が突入するための条件が出てくる。例えば、図１５に示されるような遷移関係の場合、ブロック４のブロック突入条件は、（１ｅｑ真＆３ｅｑ真）  ｏｒ  （１ｅｑ偽＆５ｅｑ真）となる。
【００７６】
以上のように、本願発明は第１実施形態に係るバッファオーバーフロー静的解析方法によっても、第２実施形態に係るバッファオーバーフロー静的解析プログラムによっても実現することができ、何れのカテゴリーの発明によっても、従来は全く考慮されなかった中間言語コードを静的に解析することにより、狭義のバッファオーバーフローの脆弱性を解析することができる。
【００７７】
【発明の効果】
以上、詳細に説明したように、本発明に係るバッファオーバーフロー静的解析方法およびプログラムによれば、ソフトウェアの脆弱性の中で最も深刻なものの１つである、通常データ領域への書込み命令がクリティカルデータへの書込みを生起させるバッファオーバーフローの脆弱性を、プログラムの実行に先立って、プログラムのソースコードのコンパイル過程で現れる中間言語コードを解析することにより検出することができるので、静的解析の手法を採りながら、ソフトウェアの最も深刻な脆弱性であるバッファオーバーフローの検出を行なうことが可能となる。
【図面の簡単な説明】
【図１】本発明の第１実施形態に係るバッファオーバーフロー静的解析プログラムの動作を説明するフローチャートである。
【図２】本発明の第２実施形態に係るバッファオーバーフロー静的解析プログラムのソースから実行までの状態を示すブロック図である。
【図３】同じく、Ｃ言語の場合のソースから実行までの状態を示すブロック図である。
【図４】狭義のバッファオーバーフローの解析対象としてどのコードが好ましいかを示す表である。
【図５】ＧＣＣのスタック上の（ａ）フレームと（ｂ）レジスタとの具体例を示す説明図である。
【図６】フレームの例を示す説明図である。
【図７】狭義のバッファオーバーフローとなるコードとその攻撃方法を示す説明図である。
【図８】ＲＴＬコードの構造を示す説明図である。
【図９】本発明の第２実施形態に係るバッファオーバーフロー静的解析プログラムの処理手順を図１の符号との対応の下に示すフローチャートである。
【図１０】ＲＴＬブロックの実行の遷移を示す説明図である。
【図１１】ＲＴＬブロックのブロック間遷移関係を示す説明図である。
【図１２】項の形を項が表すものとを示す説明図である。
【図１３】遡及について示す説明図である。
【図１４】同じく遡及について示す説明図である。
【図１５】ブロック突入条件について示す説明図である。
【図１６】ソフトウェアの脆弱性の報告件数を示す表である。
【符号の説明】
ＳＴ１  第１のステップ（字句構文の解釈）
ＳＴ２  第２のステップ（ブロック間の遷移関係の同定）
ＳＴ３  第３のステップ（転送先遡及項を求める）
ＳＴ４  第４のステップ（選別危険転送命令文とする）
ＳＴ５  第５のステップ（突入条件遡及項を求める）
ＳＴ６  第６のステップ（バッファオーバーフロー条件を求める）
ＳＴ７  第７のステップ（条件不充足による命令文の破棄）
ＳＴ８  第８のステップ（結果出力）
【図１】
2004171064.tif 000003
【図２】
2004171064.tif 000004
【図３】
2004171064.tif 000005
【図４】
2004171064.tif 000006
【図５】
2004171064.tif 000007
【図６】
2004171064.tif 000008
【図７】
2004171064.tif 000009
【図８】
2004171064.tif 000010
【図９】
2004171064.tif 000011
【図１０】
2004171064.tif 000012
【図１１】
2004171064.tif 000013
【図１２】
2004171064.tif 000014
【図１３】
2004171064.tif 000015
【図１４】
2004171064.tif 000016
【図１５】
2004171064.tif 000017
【図１６】
2004171064.tif 000018