(57)【要約】      （修正有）【課題】コンピュータ読み取り可能デバイス内でコード化されたコード式における汚染性を推測するための方法。【解決手段】方法は、評価されることになるコンピュータ・プログラムの表現１０８を非一時的記憶媒体内に記憶すること、表現内でポインタ・キャスト・オペレーションを識別すること、識別されたキャスト・オペレーションが、ロー・メモリ・データ・タイプに対するポインタから構造化データ・タイプに対するポインタへのキャストを含むかどうかを判別すること、キャストされた構造化データ・タイプが外在性の標識に関連付けられているかどうかを判別すること、それによってアドレス指定されるデータを汚染されているものと指定すること、及び、汚染されているものと指定されたデータが、汚染性シンクとして働くコンピュータ・プログラム内のオペレーションによって消費されるかどうかを判別すること、を実行するように構成することを含む。【選択図】図１
2014056567.tif 000002
【特許請求の範囲】
【請求項１】
コンピュータ読み取り可能デバイス内でコード化されたコード式における汚染性を推測するための方法であって、
評価されることになるコンピュータ・プログラムの表現を非一時的記憶媒体内に記憶すること、
前記表現内でポインタ・キャスト・オペレーションを識別すること、
キャスト・オペレーションの識別に応答して、前記識別されたキャスト・オペレーションが、ロー・メモリ・データ・タイプに対するポインタから構造化データ・タイプに対するポインタへのキャストを含むかどうかを判別すること、
ロー・メモリ・ポインタが構造化データ・タイプに対するポインタにキャストされるという判別に応答して、キャストされた前記構造化データ・タイプが外在性の標識に関連付けられているかどうかを判別すること、
キャストされた前記構造化データ・タイプが外在性の標識に関連付けられているという判別に応答して、そのポインタによってアドレス指定される値を汚染されているものと指定すること、及び
汚染されているものと指定された値が、汚染性シンクとして働く前記コンピュータ・プログラム内のオペレーションによって消費されるものとして、前記表現内に示されるかどうかを判別すること、
を実行するようにコンピュータ・システムを構成することを含む、方法。
【請求項２】
識別されたキャスト・オペレーションに関連付けられた前記値を前記コンピュータ・プログラムがサニタイズすることを、前記表現が示すかどうかを判別するようにコンピュータ・システムを構成すること、
を更に含む、請求項１に記載の方法。
【請求項３】
識別されたキャスト・オペレーションに関連付けられた前記値を前記コンピュータ・プログラムがサニタイズすることを、前記表現が示すかどうかを判別すること、
識別されたキャスト・オペレーションに関連付けられた前記値が、汚染性シンクとして働く前記コンピュータ・プログラム内のオペレーションによって消費されること、及び、前記コンピュータ・プログラムが、識別されたキャスト・オペレーションに関連付けられた前記値をサニタイズしないことに応答して、そのサニタイズされていない値が前記シンクによって消費されることを報告すること、
を実行するようにコンピュータ・システムを構成することを更に含む、請求項１に記載の方法。
【請求項４】
前記コンピュータ・プログラムが、経路終了を介して、識別されたキャスト・オペレーションに関連付けられた前記値をサニタイズするためのオペレーションを含むことを、前記表現が示すかどうかを判別するようにコンピュータ・システムを構成すること、
を更に含む、請求項１に記載の方法。
【請求項５】
前記コンピュータ・プログラムが、値置換を介して、識別されたキャスト・オペレーションに関連付けられた前記値をサニタイズするためのオペレーションを含むことを、前記表現が示すかどうかを判別することを更に含む、請求項１に記載の方法。
【請求項６】
前記コンピュータ・プログラムが、経路終了及び変数置換のうちの少なくとも１つを介して、識別されたキャスト・オペレーションに関連付けられた前記値をサニタイズするためのオペレーションを含むことを、前記表現が示すかどうかを判別することを更に含む、請求項１に記載の方法。
【請求項７】
前記表現がソース・コードを含む、請求項１に記載の方法。
【請求項８】
前記表現が抽象構文木を含む、請求項１に記載の方法。
【請求項９】
前記表現がバイト・コードを含む、請求項１に記載の方法。
【請求項１０】
前記変換された表現が、タイプ及びキャスティングに関する充分なソースレベル情報を保持するオブジェクト・コードを含む、請求項１に記載の方法。
【請求項１１】
キャストされた構造化データ・タイプが外在性の標識に関連付けられているかどうかを判別することが、任意のフィールドがポインタ・タイプを有するかどうかを判別することを含む、請求項１に記載の方法。
【請求項１２】
キャストされた構造化データ・タイプとポインタ・タイプを有するフィールドとの関連付けが外在性を示す、請求項１に記載の方法。
【請求項１３】
キャストされた構造化データ・タイプが外在性の標識に関連付けられているかどうかを判別することが、前記キャストされたデータ・タイプ内のフィールド・サイズのダイバーシティと、前記キャストされたデータ・タイプがビット・フィールドを有するかどうかと、符号なしフィールドが存在するかどうかと、前記データ・タイプのパッキングと、を含むグループから、１つ又は複数の要因に重み付けすることを含む、請求項１２に記載の方法。
【請求項１４】
多数のフィールド、多くの異なるデータ・サイズ、ビット・フィールドの頻繁な使用、及び符号なしタイプの前記頻繁な使用が、外在性を示し、
ポインタ・タイプ・フィールドの存在が非外在性を示す、
請求項１３に記載の方法。
【請求項１５】
ポインタ・キャスト・オペレーションを識別することが、前記表現内のコード式を追跡することを含む、請求項１に記載の方法。
【請求項１６】
ポインタ・キャスト・オペレーションを識別することが、前記表現内のコード式を追跡することを含み、
汚染されているものと指定された値が、汚染性シンクとして働く前記コンピュータ・プログラム内のオペレーションによって消費されるものとして、前記表現内に示されるかどうかを判別することが、前記表現内のコード式を追跡することを含む、
請求項１に記載の方法。
【請求項１７】
汚染されているものと指定された前記値が、汚染性シンクとして働くオペレーションによって消費されるという判別に応答して、汚染性結果を報告することを更に含む、請求項１に記載の方法。
【請求項１８】
前記表現内のポインタ・キャスト・オペレーションを識別することが、明示的キャスト・オペレーションを識別することを含む、請求項１に記載の方法。
【請求項１９】
前記表現内のポインタ・キャスト・オペレーションを識別することが、暗黙的キャスト・オペレーションを識別することを含む、請求項１に記載の方法。
【請求項２０】
ポインタ・キャスト・オペレーションの前記表現から、汚染性シンクとして働く前記コンピュータ・プログラム内の前記オペレーションへの方向に、前記コンピュータ・プログラムをトラバースすることを更に含む、請求項１に記載の方法。
【請求項２１】
汚染性シンクとして働く前記コンピュータ・プログラム内の前記オペレーションから、前記ポインタ・キャスト・オペレーションの前記表現への方向に、前記コンピュータ・プログラムをトラバースすることを更に含む、請求項１に記載の方法。
【請求項２２】
コンピュータ・システムを、
評価されることになるコンピュータ・プログラムの表現を非一時的記憶媒体内に記憶すること、
前記表現内でポインタ・キャスト・オペレーションを識別すること、
キャスト・オペレーションの識別に応答して、前記識別されたキャスト・オペレーションが、ロー・メモリ・データ・タイプに対するポインタから構造化データ・タイプに対するポインタへのキャストを含むかどうかを判別すること、
ロー・メモリ・ポインタが構造化データ・タイプに対するポインタにキャストされるという判別に応答して、キャストされた前記構造化データ・タイプが外在性の標識に関連付けられているかどうかを判別すること、
キャストされた前記構造化データ・タイプが外在性の標識に関連付けられているという判別に応答して、そのポインタによってアドレス指定される値を汚染されているものと指定すること、及び
汚染されているものと指定された値が、汚染性シンクとして働く前記コンピュータ・プログラム内のオペレーションによって消費されるものとして、前記表現内に示されるかどうかを判別すること、
を実行するように構成することを含むプロセスをコンピュータに実行させるために、命令コードをコード化されたコンピュータ読み取り可能デバイスを含む、製品。
【請求項２３】
コンピュータ・プログラム・コードの静的分析中に、汚染性を評価するための手段と、
コード式が汚染性ソースを表すかどうかを判別するための手段と、
ポインタがキャストされるタイプが、前記ポインタが汚染されたデータを指示することを示唆するかどうかを評価するための手段と、
を備える、コンピュータ読み取り可能デバイス内でコード化されたコード式における汚染性を決定するためのシステム。
【発明の詳細な説明】
【背景技術】
【０００１】
ソフトウェア・コードは、しばしばエラーを含んでいる。これらエラーのいくつかは、印刷されたコードの目視検査によって容易に検出される。より微妙なエラーは、典型的には、ソフトウェア・デバッグ分析ツールの助けによってのみ発見される。
【０００２】
汚染分析（taint analysis）は、コンピュータ・プログラムがコンピュータ・システム上で実行されている場合、その制御外からの信用できないデータのソース・コード内での使用を検出することを含む。より具体的に言えば、汚染分析は、実行中のプログラムのアドレス・スペース内で作成された信用できるデータと、外部の潜在的に信用できないソースから何らかの方法でこのアドレスにコピーされたデータとを、区別することを含む。汚染分析は、典型的には、信用できないソースからの値がセキュリティ依存コンピュータ・システム・オペレーションに流入し得るかどうかを確立する、コンピュータ・プログラム・コードの情報フロー分析の形を含む。汚染分析は、汚染ソースから到達する信用できないデータを、汚染されているものとしてマーク付けすることを含み得る。データがコンピュータ・メモリを介し、様々なオペレーションを介して伝搬される場合、その汚染マーク付け情報がデータ自体と共に伝搬される。汚染分析は、動的デバッグ分析技法又は静的デバッグ分析技法或いはその両方の組み合わせの、いずれかで採用され得る。
【０００３】
動的ソフトウェア分析ツールは、ランタイム・エラー・チェックを実行する。ソフトウェア・エラーは、それらが発生した時点で捕捉され得る。例えば、制御がプログラム内の特定経路に分岐している場合、その経路に沿って発生するエラー（例えば区域外メモリ・アクセス）は検出され得る。動的分析ツールはデバッグ・プロセスではしばしば非常に有益であるが、欠点が無い訳ではない。特に、テスト中に複雑なソフトウェアを完全に働かせることが困難な場合がある。例えば、特に大規模プログラムにおいて、ソフトウェアがエンド・ユーザに公開される前に、すべての可能なプログラム挙動のうちのごくわずかな部分しか徹底的にテストできない可能性がある。ソフトウェアの稀にしか使用されない部分（例えば、条件付き分岐において稀に通過する経路）は、ソフトウェアがその分野で展開される前に決してテストされない可能性がある。
【発明の概要】
【発明が解決しようとする課題】
【０００４】
静的ソフトウェア分析ツールは、静的コード（すなわち、分析プロセス中に実行していないコード）上で動作する。静的分析は、コンピュータ・システムを物理的に構成するためのコードを実際に使用せずに、コードを使用して構成された実際のコンピュータ・システムのオペレーションをシミュレートするために、コンピュータ・プログラム・コード上で実行される。静的分析は、例えば、望ましくない依存性を発見し、コードの望ましい構造設計が維持されていることを保証するために、ソース・コードが規定されたコード化標準でコンパイルすることが保証可能なコードの理解を与える。静的分析は、動的分析ツールのみが使用される場合には容易に見逃されるエラーを検出することも可能である。例えば静的分析は、稀にトラバースされるか又はそれ以外のテストが困難な条件付き分岐経路内に含まれる、不正なオペレーションを検出し得る。この経路はソフトウェアのオペレーション中に稀にしか訪問されないため、このエラーは動的分析ツールを使用して検出されない可能性がある。
【課題を解決するための手段】
【０００５】
従来、静的汚染分析は、通常、汚染性ソースの識別、並びに、プログラムが汚染シンクに到達したかどうかを判別するためにプログラム内での実行の経路を手続き間的及び／又はグローバルに通る汚染された情報の伝搬及び追跡を含んでいる。残念なことに、汚染性ソースの識別に関する不完全な情報のみが用いられ得る。更に、たとえこうした分析が汚染のソースに関する正確な情報を有する場合であっても、経路の重複により、又は実用的な理由から必要となるメモリ・モデルの簡略化及び抽象化により、様々な経路を通り汚染性シンクまでコード・オペレーションの汚染を追跡することは困難な可能性がある。
【図面の簡単な説明】
【０００６】
【図１】いくつかの実施形態に従った、コンピュータ・プログラムの静的分析中に汚染性を評価するためのプロセスを示す図である。
【図２】いくつかの実施形態に従った、図１のプロセスを使用して実装される経路トラバース及びチェッカー・プロセスの細部を示すフロー図である。
【図３】いくつかの実施形態に従った、コード式が汚染性ソースを表すかどうかを判別するために図１のプロセスを使用して実装されるプロセスを示す図である。
【図４】いくつかの実施形態に従った、ポインタがキャスト（cast）されるタイプが、ポインタが汚染されたデータを指示するかどうかを評価するために、図１のプロセスを使用して実装されるプロセスを示す図である。
【図５】いくつかの実施形態に従った、例示コードを介した異なる経路を示す経路図である。
【図６】いくつかの実施形態に従った、例示コードを介した異なる経路を示す経路図である。
【図７】いくつかの実施形態に従った、例示コードを介した異なる経路を示す経路図である。
【図８】いくつかの実施形態に従った、ネストされた構造タイプを含む例示の構造タイプを示す図である。
【図９】いくつかの実施形態に従った、汚染性エラー報告を示すスクリーン・ショットである。
【図１０】本明細書で論じられる方法のうちのいずれかの１つ又は複数をコンピュータに実行させるために、内部で命令セットが実行され得る、コンピュータ処理システムを示すブロック図である。
【発明を実施するための形態】
【０００７】
一態様において、コンピュータ読み取り可能デバイス内でコード化されたコード式における汚染性を推測するための方法が提供される。コンピュータは、評価されることになるコンピュータ・プログラムの表現を非一時的記憶媒体内に記憶するように構成される。コンピュータは、ポインタ・キャスト・オペレーションを識別するために、表現内を検索するように構成される。識別されたキャスト・オペレーションが、ロー・メモリ・データ・タイプに対するポインタから構造化データ・タイプに対するポインタへのキャストを含むかどうかに関して、判別される。キャストされた構造化データ・タイプが外在性の標識に関連付けられているかどうかに関して、判別される。キャストされた構造化データ・タイプが外在性の標識に関連付けられているとの決定に応答して、そのポインタによってアドレス指定される値は汚染されているものと指定される。コンピュータは、汚染されているものと指定された値が汚染性シンクとして働くプログラム内のオペレーションによって消費されるかどうかを判別するために、表現内を検索するように構成される。
【０００８】
選択された用語の定義
本明細書で使用される「キャスト」は、別のコード式内で式のタイプを変更する単項演算子を意味する。キャスト・オペレーションの結果が使用される場合、データが古いタイプではなく新しいタイプであるかのように解釈される。この再解釈は指定された式に対してのみ適用され、プログラム内の他の場所では、キャストされた式のタイプは未変更のままである。
【０００９】
本明細書で使用される「データ・タイプ」は、整数、ブールなどの様々なデータ・タイプ、又は、例えば、そのタイプの値で実行可能なオペレーション及びそのタイプの値を格納可能な方法など、プログラミング言語Ｃでそのデータの可能な値を決定する「struct」タイプを指定して定義されるタイプなどの、定義済みタイプのうちの１つを識別する、分類を意味する。
【００１０】
本明細書で使用される「経路」は、一連の条件付き分岐アクション及びそれらの間の条件なしオペレーションを意味する。
【００１１】
本明細書で使用される「ロー・メモリ」は、更なる解釈又は内部構造なしに、バイト単位でのその開始位置（「アドレス」）及び範囲（長さ）によってのみ特徴付けられる、コンピュータ記憶デバイス（「メモリ」）の領域を意味する。コンピュータ言語「void*」は、しばしば、例えばメモリ位置ホルダとして働くため及びロー・メモリを示すために使用される。コンピュータ言語「char*」も、例えば非構造化メモリを示すために使用されている。
【００１２】
本明細書で使用される「サニタイズする（sanitize）」は、所与の値が、いくつかのオペレーションの定義ドメイン外にある特定の値又は値の範囲を有さないという点で、いくつかの特定の目的に適していることを保証するための手段を講じることを意味する。汚染された値のサニタイゼーションは、例えば、パススルー・コードの終了を含み得るか、又は汚染された値の異なる値への置換を含み得る。異なる特定のサニタイゼーション技法が、異なる種類の汚染性シンクに必要な場合がある。
【００１３】
本明細書で使用される「汚染」は、どの値が汚染されているかに関する情報を意味する。
【００１４】
本明細書で使用される「汚染された」又は「汚染性」は、値又は情報がコンピュータ・プログラムの制御外のソースから発せられたこと及びサニタイズされていない旨の、値又は情報のプロパティ又は特徴を意味する。この分野の文献が、たとえサニタイズされた後であってもしばしばこうした値を「汚染されている」などと言い表すことに留意されたい。
【００１５】
本明細書で使用される「汚染性シンク」は、汚染された値が、例えばある値又はオペランドの組み合わせの使用により、定義されていないか又は望ましくない挙動を有するコンピュータ・プログラム・オペレーションなどの害を及ぼし得る、コンピュータ・プログラム内のポイントを意味する。数学用語では、汚染性シンクは、そのオペランドのプログラミング言語タイプによって可能となる値セットのサブセットである、ドメインを伴う任意のオペレーションとみなすことが可能である。例えば、除算オペレーションの除数は、たとえその整数タイプがゼロであることが可能であっても、除数のドメインはゼロを除外する（すなわち、ゼロによる除算は定義されていない）ため、汚染性シンクである。
【００１６】
本明細書で使用される「汚染性ソース」は、例えばコンピュータ・プログラムのアドレス・スペース外からの値又は値の組み合わせのコピーなどの、汚染された値又は汚染された情報の元を意味する。
【００１７】
本明細書で使用される「経路のトラバース」は、時間順又は逆時間順のいずれかでの、経路に沿ったオペレーションの実際又はシミュレートされた実行を意味する。
【００１８】
本明細書で使用される「値」は、特定の実行経路に沿った特定のポイントで、変数又は式によって指定される値を意味する。変数又は式は、実行経路に沿った異なるポイントで異なる値を有し得る。
【００１９】
本明細書で使用される「変数」は、どのようにアドレス指定されるかにかかわらず、異なる時点で異なる値を含むことが可能な任意の記憶位置（メモリ又はレジスタ）を言い表す。
【００２０】
以下の説明は、汚染された値が汚染性シンク内に流入することをソース・コードが許可するかどうかを決定するために、いずれの当業者でもコンピュータ・システム構成及び関係する方法及び製品を作成及び使用できるようにするために提示される。本発明の趣旨及び範囲を逸脱することなく、当業者であれば実施形態に対する様々な修正が明らかとなり、本明細書に定義された一般原理は他の実施形態及び適用例に適用され得る。更に、以下の説明において、様々な細部が説明の目的で示される。しかしながら当業者であれば、これら特定の細部を用いることなく、本発明が実施され得ることを理解されよう。他のインスタンスにおいて、不必要な細部によって本発明の説明が不明瞭にならないために、良く知られたデータ構造及びプロセスはブロック図形式で示されている。異なる図面において、同じアイテムの異なるビューを表すために同一の参照番号が用いられ得る。以下で参照される図面内のフロー図は、プロセスを表すために用いられる。コンピュータ・システムは、これらのプロセスを実行するように構成される。フロー図は、コンピュータ・プログラム・コードに従ったコンピュータ・システムの構成を表すモジュールを含み、これらのモジュールを参照しながら説明される動作を実行する。したがって本発明は、示された実施形態に限定されるものと意図されず、本明細書で開示された原理及び特徴に一致する最も広い範囲に従うものとされる。
【００２１】
図１は、いくつかの実施形態に従った、コンピュータ・プログラムの静的分析中に汚染性を評価するためのプロセス１００を示す図である。モジュール１０２は、コンピュータ読み取り可能デバイス１０６内に記憶されたソース・コード１０４を、自動化静的コード分析に好適なコンピュータ読み取り可能デバイス１１０内の符号化された変換済み表現１０８に変換する。いくつかの実施形態において、ソース・コード１０４は、例えばＣ又はＣ＋＋などの静的にタイプ付けされた言語での人間作成コードを含み、変換済みコード表現１０８は、多くのフォーマット化の特性及び識別子がソース・コード表現１０４から除去され、残りのコードがコードの自動化静的分析に好適なツリー構造で編成された、抽象構文木（ＡＳＴ）構造を含む。一般に、ＡＳＴ構造は、典型的にはコンパイラの予備構文解析段階によって生成され得るような、ソース・コードのツリー構造表現を含む。ツリー構造は明瞭なコードの構造分解を含み、これによって自動化構造検索が実行され得る。ＡＳＴ構造を用いて、コンピュータ・プログラムのグラフィック表現が提供可能である。別の方法として、変換済みコードは、ＡＳＴの代わりに、例えばタイプ及びキャスティングに関する充分なソースレベル情報を保持する、バイト・コード或いはオブジェクト・コードを含み得る。
【００２２】
モジュール１１２は、変換済みコード構造１０８をトラバースする。いくつかの実施形態において、モジュール１１２は複数の経路をトラバースする。トラバースは、深さ優先、ポスト順、或いは、選択された表現１０８内に指定されたコード・オペレーションを時間順又は逆時間順のいずれかで処理するのに十分な何らかの他のトラバース順に、進行し得る。トラバースの過程で、モジュール１１２は、ソース、シンク、及びサニタイゼーションを含む分類セットにコード・オペレーションを分類し、トラバース中に１つ又は複数のコード・オペレーションによって消費される各値又は式に関する汚染性状態のインジケーションも作成及び伝搬する。
【００２３】
いくつかの実施形態において、モジュール１１２はサブモジュール１１４〜１１６を含む。コード表現１０８のトラバースの過程において、モジュール１１４は汚染性ソースを探索し、汚染性ソースの識別に応答して、汚染性ソースによって生成された値が汚染されている旨のインジケーションを非一時的記憶内に提供する。モジュール１１５は、値又は式（以下「値」という）の伝搬（例えばコピー）を探索する。値のコピーの検出に応答して、モジュール１１５は、コピーされた値が非一時記憶内で汚染されたものと示されているかどうかを判別し、コピーされた値が汚染されたものと示されている場合、この汚染はコピーされた値と共に伝搬される。システムが監視することになるあるサニタイゼーション・オペレーションが存在するが、サニタイゼーションはしばしば何らかの汚染された値がシンクに到達するのを防止することを含み、「防止」はしばしば直接観察できないため、サニタイゼーションの結果はしばしば容易に観察され得ないことを理解されよう。モジュール１１６は汚染性シンクを探索し（例えばオペランドによるオペレーション）、シンクの識別に応答して、モジュール１１２は、シンクに関連付けられたオペランド値が非一時的記憶内で汚染されたものと示されているかどうかを判別する。オペランドが汚染されている旨の決定に応答して、モジュール１１２はエラーの発生を報告する。
【００２４】
図２は、いくつかの実施形態に従った、モジュール１１２によって実装される経路トラバース及びチェッカー・プロセス２００の細部を示すフロー図である。例示のプロセス２００は、単一パスで経路をトラバース及びチェックする。プロセス２００は、複数経路を並行してトラバース及びチェックするようにも動作可能である。プロセス２００は、コード式の異なる特徴についてチェックする複数の意思決定モジュールを含む。意思決定モジュール２０２は、現行経路内に、未だに処理されていない別のコードが存在するかどうかを判別する。経路内のコード・オペレーションに対応するすべてのコード式が処理されている場合、経路は処理されるべき別のコード式を有さない。意思決定モジュール２０２が、現行経路について処理されるべき他のコード式は残っていない旨を決定すると、現行経路に関するトラバースは完了する。これに対して、意思決定モジュール２０２が、処理されるべき別のコード式が存在するものと決定すると、モジュール２０３は、経路内のコード・オペレーションに対応するコード式を選択する。意思決定モジュール２０４は、選択されたコード式が汚染性ソースを表すかどうかを判別（チェック）する。現在選択されている式が汚染性ソースを表す旨の決定に応答して、モジュール２０６は、汚染性ソースによって生成された値が汚染されている旨のインジケーションを非一時的媒体内に記憶する。
【００２５】
意思決定モジュール２１０は、現在選択されているコード式が値をサニタイズするオペレーションに対応するかどうかを判別（チェック）する。２つの異なる種類の汚染性サニタイゼーションは、例えば経路終了及び値置換である。終了を介したサニタイゼーションが経路上で使用され、サニタイゼーション・プロセスが汚染を識別した場合、経路のトラバースは終了する（図示せず）。意思決定モジュール２１０は、現在選択されているコード式が値置換を介してサニタイズされるかどうかを判別する。現在選択されているコード式が値置換を介してサニタイズされる旨の決定に応答して、モジュール２１５は、汚染された状態をクリアし、意思決定モジュール２０２に戻って、経路内に選択されることになる別のコード式が存在するかどうかを判別するように、コンピュータ・システムを構成する。
【００２６】
終了によるサニタイゼーションは、必ずしも現在探索されている経路全体の検索又はトラバースを終了しないことを理解されよう。むしろ終了によるサニタイゼーションは、その経路に沿って追跡されていた特定の汚染された値がデータ・フローの意味で「デッド（dead）」になることを示唆し、これはそれに対する参照がいっさい存在しないことを意味する。汚染性分析は、その経路、及び、他の値についての関連する汚染関係イベントが存在する場合はそこから分岐している任意の他の経路の、探索を続行することになる。したがって、いくつかの実施形態において、所与の経路に沿った検索は、汚染された値ごとではなく、経路に沿ったすべての汚染関係アクティビティについて「同時に」検索することを理解されよう。
【００２７】
意思決定モジュール２１０での、置換によるサニタイゼーションが存在しない旨の決定に続き、制御は意思決定モジュール２１６へと流れ、ここで現在選択されているコード式が汚染性シンクを構成するかどうかを判別する。意思決定モジュール２１６での、現在選択されているコード式が汚染性シンクを表す旨の決定（モジュール２１６での「はい」）に応答して、意思決定モジュール２１７は、汚染性シンクに関連付けられたオペランドが（記憶内で）汚染されたものと示されているかどうかを判別する。オペランドが汚染されていないとしてマーク付けされた旨の決定（モジュール２１７での「いいえ」）に応答して、制御は意思決定モジュール２０２へと流れる。オペランドが汚染されているとしてマーク付けされた旨の決定（モジュール２１７での「はい」）に応答して、モジュール２１８はエラーを報告し、トラバースはモジュール２０２に戻る。
【００２８】
意思決定モジュール２１６での現在選択されているコード式が汚染性シンクを表さない旨の決定（モジュール２１６での「いいえ」）に応答して、制御は意思決定モジュール２２０へと流れる。意思決定モジュール２２０は、現在選択されているコード式が分岐を示すかどうかを判別する。制御フローにおける分岐の識別（モジュール２２０での「はい」）に応答して、モジュール２２２は現行経路の各汚染された値について汚染性状態を模造する。すなわち、現行（分岐前）経路に関連付けられた各サニタイズされていない汚染された値について、モジュール２２２は、各新しい分岐経路についての記憶内に別々の汚染性インジケーションを作成する。モジュール２２２は、各新しい分岐経路のトラバースを実行するようにコンピュータ・システムを構成し、制御はこうした各分岐経路についてモジュール２０２へと流れる。その他の方法で、分岐が検出されない（モジュール２２０での「いいえ」）場合、制御はモジュール２０２へと流れ、トラバースはモジュール２０２に戻る。
【００２９】
経路トラバースは追加のモジュール（図示せず）を含むことが可能であり、代替実施形態において、経路トラバースに関与するモジュールの順序は変更可能であることを理解されよう。
【００３０】
図３は、いくつかの実施形態に従った、コード式が汚染性ソースを表すかどうかを判別するためのプロセス３００のある細部を示す図である。特に、図２のプロセス３００は、いくつかの実施形態においてモジュール２０４を実装する。意思決定モジュール３０２は、経路内で現在選択されているコード式がキャスト・オペレーションの発生を表すかどうかを判別する。こうしたキャストの発生が存在しない（モジュール３０２での「いいえ」）旨の意思決定モジュール３０２による決定に応答して、プロセス制御は図２のモジュール２１０へと流れる。そうでない（モジュール３０２での「はい」）場合、制御は意思決定モジュール３０４へと流れ、これが、識別されたキャスト・オペレーションが、ロー・メモリに対するポインタからさらなる構造化データ・タイプに対するポインタへのキャストを含むかどうかを判別する。いくつかの実施形態によれば、「さらなる構造化」タイプは、集約タイプ、構造タイプ、又は記録タイプを含む。非構造化タイプに対するポインタからさらなる構造化タイプに対するポインタへのポインタのキャストは、ポインタが指示するデータが汚染されている可能性を示す。一般に、これは２つの要因の組み合わせに従う。第１に、プロセス内外でデータをコピーするためのコンピュータ・システム機構は汎用的な傾向があり、特定の構造化タイプを使用するプログラム内で採用される特定の構造化タイプに気付かない傾向があるため、典型的には、汎用のロー・メモリ・タイプに関して指定される。第２に、プログラマは一般に理由なくタイプ・キャストを使用しないため、データが生起したプログラム内のどこかがタイプ情報が入手できる唯一の場所であったことから、キャストされている値はポインタ・ツー・ロー・メモリ（pointer-to-raw-memory）・タイプを有することが想定可能である。
【００３１】
識別されたキャストが、ロー・メモリに対するポインタからさらなる構造化タイプに対するポインタでない旨の意思決定モジュール３０４による決定（モジュール３０４での「いいえ」）に応答して、プロセス制御は図２のモジュール２１０へと流れる。そうでない場合（モジュール３０４での「はい」）、制御は意思決定モジュール３０６へと流れ、これが、ポインタがキャストされるタイプが、プログラムのアドレス・スペース外にある外部ソースなどの汚染されたソースから発生していることの標識を含むかどうかを判別する。ソースが汚染されている旨の意思決定モジュール３０６による決定（モジュール３０６での「はい」）に応答して、プロセス制御は図２のモジュール２０６へと流れる。そうでない場合（モジュール３０６での「いいえ」）、プロセス制御は図２のモジュール２１０へと流れる。
【００３２】
図４は、いくつかの実施形態に従った、ポインタがキャストされるタイプが、ポインタが汚染されたデータを指示することを示唆するかどうかを評価するための、プロセス４００を示す図である。例示のプロセス４００は、いくつかの実施形態において図３のモジュール３０６を実装するために使用される。モジュール４０２は、ポインタが間接的に汚染されたソースを指示するかどうかの判別に影響を及ぼす要因を識別するために、ポインタがキャストされるソース構造タイプを検査する。本明細書で使用される場合、「間接的に汚染されたソース」は、おそらく分析によって直接認識されないポイントで、汚染されたデータが以前に記憶された記憶位置である。「間接的に汚染されたソース」は、元の「直接」汚染性ソース自体が観察できないこと、又は直接汚染性ソースからのすべてのデータ・フローを追うことはできないが、汚染はどこにでも発生する可能性がある旨のインジケーションが観察できることのいずれかによって、「間接的に」又は「推測的に」汚染された記憶位置である。
【００３３】
本明細書で「排除（exclusion）」と呼ばれるある要因は、ソースが汚染性ソースでない旨の充分なインジケーションとみなされる。排除ではない他の要因は、ソース・タイプを汚染性ソースとして指定するかどうかを判別するためのスコアリング・システムを使用して、まとめて評価される。
【００３４】
表１Ａ及び表１Ｂは、いくつかの実施形態に従った評価の下で、ロー・メモリに対するポインタが、コンピュータ・プログラムの内部又は外部にあるデータに対するポインタにキャストされるかどうかを評価するために使用される要因を示す。一般に、汚染性は、内部アクティビティよりも外部アクティビティに関連付けられる可能性が高い。したがって、アクティビティがコンピュータ・プログラムの内部又は外部のいずれにあるかの標識は、汚染されている可能性がより高いかどうかのインジケーションでもある。いくつかの実施形態によれば、プロセス内部にあるデータは汚染されていないものとみなされ、プロセス外部にあるデータは汚染されているものとみなされる。
【００３５】
コンピュータ・プログラムは、主として、データ上でのオペレーション（算術など）、意思決定（条件付き分岐）、及び通信（何らかの「製造者」から何らかの「消費者」へのデータの搬送）の、３つのアクティビティからなる。したがって、コンピュータ・プログラムは大規模及び小規模に常時通信している。この大量の通信は厳密には単一の計算プロセスの内部にあり、プロセスは本質的にそれ自体と通信している。これは、プログラマによって実施される制御の程度、及びコンピュータ・アーキテクチャによって提供される保証により、どちらも可能であり、計算の効率性という理由のために、通信されている「メッセージ」の形成において多くの「ショート・カット」を用いるために内部通信に必要である。
【００３６】
長期記憶（例えばディスク・ファイル）のためのプロセスからその後の他のプロセスまでの１つのコンピュータ上で実行中の２つのプロセス間で直接、或いは、潜在的に異なるコンピュータ上で実行中のプロセス間でネットワークを介しての、いずれかでの外部通信は、制約及びコストの異なるセットの下で動作する。例えば外部通信は、情報を可能な最も小さなスペースにパックするように編成され、おそらくは他の異なる種類のコンピュータ上で、他のプロセスが確実かつ明確にデータを解釈できるようにフォーマット化される、傾向がある。典型的には外部通信に関連付けられるこれらの特徴は、内部通信にも関連付けられ得るが、これらの特徴のいくつかはプログラマが使用するのに不便であるため、ひとつには厳密に言えば内部通信に対して不必要に使用されない可能性があるという理由で、これらの特徴には、内部通信よりも外部通信との著しく強い相関関係が存在する。
【００３７】
表１Ａは、ロー・メモリに対するポインタがプロセスの内部にあるデータに対するポインタにキャストされていることを示す要因を一覧表示している。表１Ｂは、ロー・メモリに対するポインタがプロセスの外部にあるデータに対するポインタにキャストされていることを示す要因を一覧表示している。
【表１Ａ】
2014056567.tif 000003
【表１Ｂ】
2014056567.tif 000004
【００３８】
メモリ・アドレスが通常は単一のプロセス内又は単一のマシン上でのみ有意であるため、ポインタ・タイプを伴うフィールドを有する構造タイプに対するポインタは排除として働く。プロセス内通信に使用される構造タイプは、同じプロセス内の他のデータに対するポインタを頻繁に含むが、こうしたポインタは、最初にそれらを作成したコンピュータ・マシン上でのみ、及び、通常はそれらを作成した特定のプロセス内でのみ、有意である。ネットワークを介するか又は異なるプロセスからなどの信頼できないソースから、或いはディスク・ドライブ又は他の大容量記憶などの何らかの外部記憶から到達するデータは、最大の情報を最小のスペース（ビット）にパックしたいと望むことから、信頼できるソースから伝送されるデータよりも数多くのフィールド及びより大きなフィールド・サイズのダイバーシティを有する可能性が高い。
【００３９】
図４のフローの説明を続けると、モジュール４０４は、キャストされるデータ・タイプが排除の特徴を有するかどうかを判別する。表１Ａ〜１Ｂを参照されたい。排除の特徴を有する場合、制御は図２のモジュール２１０へと流れる。排除の特徴を有さない場合、モジュール４０６は、モジュール４０２によって識別された、ポインタがキャストされたソース構造タイプの特徴に基づいて、外在性スコアを生成する。いくつかの実施形態において、どの要因が排除であり、他の要因がどのようにして組み合わされ、重み付けされ、スコアリングされるかを決定するための基準は、特定の適用例に対するユーザのニーズ又は要件に従って指定又は構成され得ることが理解されよう。
【００４０】
ポインタがキャストされるソース構造タイプの特徴に応じてスコアを生成するようにモジュール４０６を構成する際の創造性には、例えばそれらの特徴を重み付けし、それらを単一のスカラ量に組み合わせ、最終的にその値が関連するしきい値を超えるかどうかを判断することなどの、かなりの余地がある。フィールド・サイズのダイバーシティ、ビット・フィールドの使用、及び符号なしタイプの使用は、例えば絶対量ではなく密度などで表され得る。例えば、フィールド数の対数を取り、異なるフィールド・サイズの数を加え、ビット・フィールドに関する追加の２ポイントを加え、少数の符号付きフィールドについては１を、又は多数の符号付きフィールドについては２を減じ、任意の浮動小数点フィールドについては２を減じ、構造全体のサイズが４の倍数でありそのレイアウト内にギャップが存在しない場合は１ポイントを加えることができる。これにより、典型的なネットワーク・パケット・ヘッダ構造については約１０のスコアが生じるが、典型的な「内部」タイプは約４のスコアが生じる可能性がある。これらの値を想定すると、しきい値８は、これらを妥当な信頼性をもって区別するはずである。
【００４１】
意思決定モジュール４０８は、計算されたスコアと経験的に決定されたしきい値とを比較することによって、ソース構造タイプが外部にあることをスコアが示すかどうかを判別する。外部にない場合、制御は図２のモジュール２１０へと流れる。外部にあると決定された場合、制御は図２のモジュール２０６へと流れる。
【００４２】
第１のコード例
【表２】
2014056567.tif 000005
【００４３】
この例では、コード「int tainted」（３行目）に関連付けられた値は、ロー・メモリ・ポインタの外部様タイプへのキャストに基づいて、現行プロセスに対して外部の出所（provenance）を有するものと推測される。オペレーティング・システム又はユーティリティ・プログラムは、この値を例えばプロセス外部の何らかのソースからコピーした可能性がある。この例では、キャストは、外部様構造タイプを非構造化タイプに重ね合わせる。したがって、変数値「tainted」は汚染されているものとして扱われる。コード「array[tainted]=0」（１０行目）によって表されるオペレーションは、値０を２スロット・アレイのスロットのうちの１つに割り当てるために汚染された値を使用する、汚染性シンクである。したがって、フィールド「some field」は汚染されているものとして扱われ、その汚染性が変数「tainted」にコピーされる。４行目のコードは、何らかの（例示の）分岐条件に基づくコード内の分岐オペレーションを表す。５〜６行目のコードは、終了オペレーションによるサニタイゼーションを表す。７〜８行目のコードは、置換オペレーションによるサニタイゼーションを表す。
【００４４】
図５は、表２に示された第２の例のコードを介した異なる経路を示す経路図である。図内の経路の集合における番号付けされた各ノードは、表２内のコードの同様に番号付けされた行に対応する。図１の経路トラバース・プロセスは、例示の汚染性ソース「int tainted」（３行目）から例示の汚染性シンク「array[tainted]=0」（コード１０行目）へと正順に進むか、又は、例示の汚染性シンク「array[tainted]=0」（コード１０行目）から例示の汚染性ソース「int tainted」（コード３行目）へと逆順に進んでよい。本明細書で開示された実施形態の１つの目的は、汚染性ソースに近接するか又は汚染性シンクに近接するトラバースを開始することであり、正方向経路トラバース及び逆方向経路トラバースの両方がこの目的を達成可能である。
【００４５】
コード４行目の条件が満たされた場合（true）、制御はコード５行目へ分岐する。５行目のコードは、変数パラメータ「tainted」の値が負の整数でないかどうかを判別する。５行目の条件コードが満たされた場合（tainted<0）、制御はコード６行目へ分岐し、経路は終了する。コード５行目からコード６行目への経路は、終了によるサニタイゼーションの例である。しかしながら、条件コード５行目が満たされない場合（false）、制御はコード７行目へ分岐する。
【００４６】
コード７行目で、変数「tainted」の値が１よりも大きい整数値であるかどうかについて判別される。ノード７の条件が満たされた場合（tainted>1）、制御はコード８行目へ分岐し、ここで「tainted」に非汚染値「１」を割り当てることによってその汚染状態がリセットされ、置換を介したサニタイゼーションを構成し、その後制御はコード１０行目に移る。しかしながら、ノード５の条件が満たされない場合、値「tainted」が安全である（すなわち「array」のインデックスとして適切である）と決定された後、制御はコード１０行目へ分岐する。
【００４７】
１つのテストのみが残されると、そのテストの一方の分岐は終了するか又は置換し、他方の分岐は単に以前に汚染された値を（実際には「排除によって」）サニタイズされた状態で残す。
【００４８】
しかしながら、コード４行目の条件が満たされない場合（false）、制御はコード１０行目へ分岐し、終了オペレーションによるサニタイゼーションをスキップし、その置換オペレーションによるサニタイゼーションをスキップする。この場合、「tainted」の値は汚染性シンク「array[tainted]=0」によって使用された場合に汚染されたまま残り、エラーが報告される。
【００４９】
経路トラバースの代替として、汚染性ソースであるとして識別された値が汚染性シンクによるサニタイゼーションなしで使用されるかどうかの判別は、データ・フロー分析を介して達成可能であり、この分析では、プログラム内のデータの直接フローの抽象グラフ表現が構築され、汚染されたプロパティがこのグラフを介して伝搬されることを理解されよう。
【００５０】
第２のコード例
５つの例示の関数「good1」、「good2」、「bad1」、「redmond_nobug」、及び「redmond_bug」が示される。データが汚染されていないものと決定される比較的単純な例示の関数（good1）と、データが汚染されていると決定される同様の対照的な関数（bad1）とを示すために、good1及びbad1の第１のペア例が与えられる。追加の例「good2」は、重要な例外を示す。データが初期に汚染されていると決定されるが、汚染性シンクへのすべての経路に沿って適切にサニタイズされる、より複雑な例示の関数（redmond_nobug）と、同じくデータが初期に汚染されていると決定されるが、汚染されたデータがそれに沿ってサニタイズされない汚染性シンクへの経路が存在する、同様の対照的な関数（redmond_bug）とを示すために、redmond_bug及びredmond_nobugの第２のペア例が与えられる。この参照により本明細書に明示的に組み込まれた付録Ａは、「good1」、「good2」、「bad1」、「redmond_nobug」、及び「redmond_bug」に関するコード・リストを示す。この参照により本明細書に明示的に組み込まれた付録Ｂは、関数bad(1)に関する例示のＡＳＴ構造を示す。
【００５１】
表３は、例示のコード・リストのコード３〜２７行目で宣言され、４つの例すべてに適用可能な、「struct」タイプのデータ構造を示す。
【表３】
2014056567.tif 000006
【００５２】
表４は、例示のコード・リストの２９行目で宣言され、４つの例すべてに適用可能な、２要素アレイを示す。
【表４】
2014056567.tif 000007
【００５３】
表５は、例示のコード・リストの３１〜３６行目で宣言された、「good1」関数の例を示す。
【表５】
2014056567.tif 000008
【００５４】
表６は、例示のコード・リストの３８〜４５行目で宣言された、「bad1」関数の例を示す。
【表６】
2014056567.tif 000009
【００５５】
表７は、例示のコード・リストの６５〜８０行目で宣言された、「good2」関数の例を示す。
【表７】
2014056567.tif 000010
【００５６】
表８は、例示のコード・リストの１０２〜１２２行目で宣言された、「redmond_nobug」関数の例を示す。
【表８】
2014056567.tif 000011
【００５７】
図６は、表８に示された第２の例のコードを介した異なる経路を示す経路図である。図内の経路の集合における番号付けされた各ノードは、表８内のコードの同様に番号付けされた行に対応する。図１の経路トラバース・プロセスは、経路に沿って正順又は逆順に進むことができる。
【００５８】
表９は、例示のコード・リストの７９〜１００行目で宣言された、「redmond_bug」関数の例を示す。
【表９】
2014056567.tif 000012
【００５９】
図７は、表９に示された第２の例のコードを介した異なる経路を示す経路図である。図内の経路の集合における番号付けされた各ノードは、表９内のコードの同様に番号付けされた行に対応する。図１の経路トラバース・プロセスは、経路に沿って正順又は逆順に進むことができる例示コードを介した異なる経路を示す経路図である。
【００６０】
「good1」関数の考察
「good1」関数又は手順は、コンピュータ・システムを構成するためにコンパイルされるように定義される。例示のコード・リストの３１行目は、変数パラメータ「p」が構造タイプ「struct foo」を指示することを示す関数定義「void good1(struct foo *p)」を与える。したがって、関数「good1」によって使用されるメモリは、「struct foo」として宣言された構造タイプに従ってレイアウトされる。コード・リストの３３行目は新しい変数「untainted」を定義し、これは構造タイプ「struct otherwise」に対するポインタであるものと定義される。「=」の左側を見ると、「struct otherwise * untainted」と示されている。コード・リストの３３行目は、新しい変数「untainted」を、ポインタ・フィールド「p->raw1」のコピーであるように初期設定するため、同じメモリ位置へのアクセスを提供する。３３行目はポインタ「p->raw1」を構造タイプ「struct otherwise」に対するポインタにキャストし、この「untainted」に対する初期値が「untainted」と同じタイプを有することを保証する。「struct foo」はフィールド「raw1」を「void」タイプに対するポインタとして定義し、これは、例えばプログラミング言語Ｃ及びＣ＋＋で、定義による、非特定的な、したがって非構造化のタイプであることを理解されよう。しかしながら、３３行目におけるキャストの結果として、その後コード・リストをコンパイルするコンパイラ・システム（図示せず）は、変数「untainted」を使用して、構造タイプ「struct otherwise」を使用する構造化方法で構造「struct foo」内に定義された「p->raw1」によって指示されたメモリ位置にアクセスする。
【００６１】
「より弱い」（すなわち非構造化）タイプ（例えば「void」）に対するポインタから、より特定的な（すなわちより構造化された）タイプ（例えば「struct otherwise」）に対するポインタへのキャスティング作業は、時折「ダウンキャスティング」と呼ばれる。当業者であれば、ダウンキャスティングという用語がタイプの想定されるグラフ描写（図示せず）を言い表し、ここでは、より弱く、より構造化されず、より汎用的なタイプが描写の上部に向かって表示され、より強く、より構造化され、より特定的なタイプが描写の下部に向かって表示されることを理解されよう。
【００６２】
コード・リストの３３行目は、数値０の定数が、２９行目（表４）に定義されたアレイの特定のメモリ位置に記憶されることを示す。具体的に言えば、定数値０は、アレイの「untainted->b」（「untainted」が「b」を指示する）によって識別されるメモリ要素に記憶されることになる。別の言い方をすれば、アレイへのインデックスは「untainted->b」のコンテンツによって決定される。フィールド「b」は構造「struct otherwise」内の記号フィールドであることに留意されたい。
【００６３】
「good2」関数の考察
「good2」関数は、コンピュータ・システムを構成するためにコンパイルされるように定義される。６７行目は、パラメータ値「param」（データ・タイプではない）を構造「struct network_packet_header」に対するポインタにキャストする。こうした関数は、複数の異なるタイプに引数を適用する汎用「コールバック」機構と共に使用され得る。こうした関数への引数は、恐らく同じプロセス内のどこからでも生じるため、特に汚染されやすくはない。
【００６４】
「bad1」関数の考察
「bad1」関数は、コンピュータ・システムを構成するためにコンパイルされるように定義される。例示のコード・リストの３８行目は、変数パラメータ「p」が構造「struct foo」を指示することを示す関数定義「void bad1(struct foo *p)」を宣言する。したがって、関数「bad1」によって使用されるメモリは、「struct foo」について宣言された構造タイプに従ってレイアウトされる。コード・リストの４０行目は新しい変数「tainted」を定義し、これは構造タイプ「struct network_packet_header」に対するポインタを有するものと定義される。「=」の左側を見ると、「struct network_packet_header * tainted」と示されている。コード・リストの４０行目は、新しい変数「tainted」を、ポインタ・フィールド「p->raw2」のコピーであるように初期設定するため、いくつかのメモリ位置へのアクセスを提供する。４０行目はポインタ「p->raw2」（「p」が「raw2」を指示する）を構造タイプ「struct network_packet_header*」に対するポインタにキャストし、この「tainted」に対する初期値が「tainted」と同じタイプを有することを保証する。「struct foo」はフィールド「raw2」を「char」タイプに対するポインタとして定義し、これは、この例ではプログラミング言語Ｃ及びＣ＋＋で、ロー・メモリを示すために使用される非構造化タイプであることを理解されよう。他の状況では、「char」は「string」であってよく、これは構造化タイプ又は単にロー・バイト・データである。４０行目におけるキャストの結果として、その後コード・リストをコンパイルするコンパイラ・システム（図示せず）は、変数「tainted」を使用して、構造「struct network_packet_header」を使用する構造化方法で構造「struct foo」内に定義された「p->raw2」によって指示されたメモリ位置にアクセスする。コード・リストの４２行目は、数値０の定数が、２９行目（表４）に定義されたアレイの特定のメモリ要素に記憶されることを示す。具体的に言えば、定数値０は、アレイの「tainted->a」（「tainted」が「a」を指示する）によって識別されるメモリ要素に記憶されることになる。別の言い方をすれば、アレイへのインデックスは「tainted->a」のコンテンツによって決定される。フィールド「a」は構造「struct network_packet_header」内の記号フィールドであることに留意されたい。
【００６５】
「redmond_nobug」関数の考察
「redmond_nobug」関数は、コンピュータ・システムを構成するためにコンパイルされるように定義される。例示のコード・リストの１０２行目は、変数パラメータ「p」が構造「struct foo」を指示することを示す関数定義「void redmond_nobug(struct foo *p)」を宣言する。したがって、関数「redmond_nobug」によって使用されるメモリは、「struct foo」の構造に従ってレイアウトされる。コード・リストの１０４〜１０５行目は新しい変数「p_buffer」を定義し、これは構造「struct network_packet_header」に対するポインタであるものと定義される。「=」の左側を見ると、「struct network_packet_header *p_buffer」と示されている。「=」の右側を参照すると、コード・リストの１０４〜１０５行目は、新しい変数「p_buffer」を、ポインタ・フィールド「p->inter->raw」のコピーであるように初期設定し、これ自体が「p->inter」によって指示された、したがって同じメモリへの構造化オブジェクトのポインタ・フィールドである。「struct intermediate」は、「raw」を「void」タイプのメモリ位置を指示するものとして定義する。１０４〜１０５行目はポインタ「p->inter->raw」（「p」が「raw」を指示する「inter」を指示する）を構造「struct network_packet_header」に対するポインタにキャストし、変数「p_buffer」の初期値が「p_buffer」と同じタイプを有することを保証する。
【００６６】
コード・リストの１０６行目は新しい変数「p_other」を定義し、これは構造「struct otherwise」に対するポインタであるものと定義される。「=」の左側を見ると、「struct otherwise *p_buffer」と示されている。コード・リストの１０６行目は、新しい変数「p_other」を、「p->raw2」のコピーであるように初期設定し、したがって、構造「struct foo」内にあるものを提供する。前述のように、「struct foo」はフィールド「raw2」を「char」タイプのメモリ位置を指示するものとして定義する。「=」の右側を参照すると、１０６行目は構造「struct otherwise」を指示するためにポインタ「p->raw2」（「p」が「raw2」を指示する）をキャストする。
【００６７】
コード・リストの１０８〜１２０行目は、コードによって定義されるプロセス内の最終ステップ（１２０行目）への３つの例示経路を提供し、これは２９行目で定義されたアレイに対する定数値０を記憶するためのものである。１０８〜１２０行目のコードの所期の目的は、そのコンテンツが、定数値０が記憶されることになるアレイの要素のインデックスを示す、メモリ位置「p_other->b」をサニタイズすることである。この例では、アレイは「int array[2]」として定義され、これは２つの要素のみを有するため、２つの可能な有効インデックス値、すなわち０及び１のみを有することを意味することに留意されたい。（「Ｃ」プログラミング言語では、アレイ・インデックスはゼロからカウントを開始する。）
【００６８】
図６は、「redmond_nobug」関数例のコードを介した異なる経路を示す経路図である。第１のパススルーは、１０４行目から１０６行目、１０８行目（条件＝false）、１１３行目（条件＝false）、１１７行目、１２０行目と進行する。１０８行目のコードは、変数「p_buffer->a」（p_bufferが「a」を指示する）の値が３であるかどうかをテストする。３でないと想定すると、制御は１１３行目のコードへと流れ、変数p_buffer->bの値が２より大きいか又は等しいかどうかが判別される。２より大きくも等しくもないと想定すると、制御は１１７行目のコードへと流れ、「p_buffer->b」の値が「p_other->b」にコピーされる。次に１２０行目で、定数値０が、「p_other->b」の値によって識別されるインデックス位置のアレイに記憶される。この経路の場合、１１３行目のコードが「p_buffer->b」の値をテストし、これが２より大きくも等しくもないことを発見し、１１７行目のコードが「p_other->b」のコンテンツの値を「p_other->b」にコピーする。したがって、値０が記憶されるアレイの要素を識別するために、インデックス０又は１が使用されることが知られている。アレイは（２９行目に定義されているように）２つの要素を有するため、問題はない。１２０行目のコードは、１１３行目でのテストによって０又は１であることがわかっており、値をサニタイズした、インデックス値「p_other->b」によって識別される要素に値０を記憶させる。
【００６９】
第２の経路は、１０４行目から１０６行目、１０８行目（条件＝true）、１０９行目、１１０行目、１２０行目と進行する。この第２の経路では、１０８行目のコードが変数「p_buffer->a」の値が３であると決定するものと想定する。１０９行目のコードは、値０をメモリ位置「p_other->b」に割り当てさせる。１１０行目のコードは、１２０行目へジャンプするように制御させ、ここでコードはインデックス値「p_other->b」によって識別された要素に値０を記憶させ、１０９行目での割り当てによって０であることがわかっており、その位置を置換によってサニタイズする。したがって、この第２の経路では、「p_other->b」は、２９行目で定義された２要素アレイに対する有効な（すなわち汚染されていない）インデックスとして使用される（１２０行目）。
【００７０】
第３の経路は、１０２行目から１０６行目、１０８行目（条件＝false）、１１３行目（条件＝true）、１１４行目へと進行する。この第３の経路は１２０行目のコードには到達せず、結果として定数値０をロードしない。第３の経路は、「p_other->b」が０又は１以外の値を含むため、完了せずに戻る。この第３の経路は終了によるサニタイゼーションの例であり、汚染された値が実際にその所期の用途に好適でないと決定すると、経路は終了する。
【００７１】
「redmond_bug」関数の考察
図７は、「redmond_bug」関数例のコードを介した異なる経路を示す経路図である。「redmond_bug」関数に関するコード（７９〜１００行目）は、「redmond_bug」関数の９７行目が、定数値０が記憶されることになるアレイへのインデックスを識別するために「p_buffer->b」の値を使用することを除いて、「redmond_nobug」関数（１０２〜１２１行目）のそれと同一である。汚染問題は、８１行目から８３行目、８５行目、８６行目、８７行目、９７行目へと、第２の経路に伴って生じる。８６行目は値０を「p_other->b」に割り当て、９７行目は「p_buffer->b」の値を使用して、値０をロードするアレイへのインデックスを決定する。しかしながら、上記で説明したように、第２の経路上には「p_buffer->b」の値のテストは存在しない（すなわち、９０行目は第２の経路の一部ではない）。したがって、「redmond_bug」関数で使用されるアレイのコンテンツに関するインデックスはサニタイズされず、汚染されたまま残り、１より大きい不正なインデックス値が使用されることになる可能性がある。
【００７２】
「good1」及び「bad1」及び「good2」の汚染性テスト
「good1」に関して、意思決定モジュール３０２は、関数「good1」が３３行目にキャストを含むものと決定する。意思決定モジュール３０４は、キャストがロー・メモリ・タイプ「void」から構造化タイプ「struct otherwise」であるものと決定する。「struct otherwise」へキャストされる構造タイプはポインタ・タイプのフィールド「char* b」を含むため、意思決定モジュール３０６は、データ構造タイプ「struct otherwise」が内部であり得ることを決定し、３３行目でのキャストは汚染性ソースとして識別されない。
【００７３】
「bad1」に関して、意思決定モジュール３０２は、関数「bad1」が４０行目にキャストを含むものと決定する。意思決定モジュール３０４は、キャストがロー・メモリ・タイプ「char*」から構造化タイプ「struct network_packet_header」であるものと決定する。「struct network_packet_header」へキャストされる構造タイプは「排除」を一切含まず、汚染性の標識、例えば良好にパックする異なるサイズの多数の符号なしフィールドを含むため、意思決定モジュール３０６は、構造タイプ「struct network_packet_header」が外部であり得ることを決定し、４０行目でのキャストは汚染性ソースとして識別される。汚染された伝搬機構は、ここで「*tainted」のフィールドが汚染されていることを想起し始め、これは汚染されていると知られている「*tainted」のフィールドであるため、汚染に敏感なオペランド「tainted->a」が汚染されていると知られているかどうかをチェックし、そこで汚染性エラーが報告される。
【００７４】
「good2」に関して、意思決定モジュール３０２は、関数「good2」が６７行目にキャストを含むものと決定する。モジュール３０４は、キャストされているポインタがパラメータであり、充分に外部データへのポインタではあり得ないものと決定する。したがって、意思決定モジュール３０４は制御フローをモジュール２０８に戻す。
【００７５】
「redmond_bug」及び「redmond_nobug」の汚染性テスト
「redmond_nobug」に関して、意思決定モジュール３０２は、関数「redmond_bug」が１０４〜１０６行目にキャストを含むものと決定する。意思決定モジュール３０４は、キャストが非構造化ロー・メモリ・タイプ「char*」から構造化タイプ「struct network_packet_header」であるものと決定する。「struct network_packet_header」へキャストされる構造タイプは「排除」を一切含まず、汚染性の標識、例えば良好にパックする異なるサイズの多数の符号なしフィールドを含むため、意思決定モジュール３０６は、構造タイプ「struct network_packet_header」が外部であり得ることを決定し、４０行目でのキャストは汚染性ソースとして識別される。
【００７６】
「redmond_bug」に関して、処理は本質的に以下と同じであるが、いくつかの重要な相違点を伴う。３つの可能な経路のそれぞれに関して、９７行目の汚染性シンク「array[p_buffer->b]=0;」で消費される値は「p_buffer->b」であると観察される。第２の経路に関して、意思決定モジュール２１６は、９７行目の汚染性シンク内で実際に使用される汚染された変数が「p_buffer->b」であると決定し、モジュール２１８は汚染性エラーを報告する。
【００７７】
暗黙的キャスト
上記のコンピュータ・プログラム・コード例、good1、good2、bad1は、コードが、より構造化されたデータ・タイプに対するポインタへのキャストを含むキャスト・オペレーションを明示的に示す、「明示的」キャストを含む。別の方法として、コンピュータ・プログラム・コードは、コードのコンパイラが、より構造化されたデータ・タイプへのキャストが必要であり、コード内にキャスト・オペレーションの明示的ステートメントが欠如しているにもかかわらず、キャストを自動的に実行することを理解する、「暗黙的」キャストを含み得る。
【００７８】
以下の表１０は、Ｃプログラミング言語を使用してキャスト・オペレーションを暗黙的に示すbad2コード関数の例である。表３の表現された構造は、void*がraw1に関連付けられること、及びchar*がraw2に関連付けられることを示していることに留意されたい。更に、表６の「bad1」関数の例がraw2を含み、表１０の「bad2」関数の例がraw1を含むことにも留意されたい。Ｃプログラミング言語では、例えばvoid*タイプからより構造化されたポインタ・タイプへの変換は暗黙的であり得る。これは、いくつかの実施形態において、Ｃコンパイラがvoid*からより構造化されたタイプへの暗黙的キャスト・オペレーションを理解し得、プログラム・コードがキャストを達成するためにキャスト・オペレーションを明示的に示す必要が無いことを意味する。例えば表１０のbad2コードでは、Ｃプログラミング言語コンパイラは、bad2コードがvoid*タイプからより構造化されたデータ・タイプに対するポインタへのキャストを暗黙的に示すことを理解する。
【表１０】
2014056567.tif 000013
【００７９】
図３の意思決定モジュール３０２は、キャストがコード内で明示的又は暗黙的に示されているかどうかにかかわらず、経路内で現在選択されているコード式がキャスト・オペレーションの発生を表すかどうかを判別することを理解されよう。
【００８０】
ネストされた構造タイプ
図８は、ネストされた構造タイプを含む例示の構造タイプを示す図である。これらはインターネットＩＰ及びＴＣＰパケット・ヘッダに関する実際のstructタイプのわずかに簡略化されたバージョンである。u_char、u_int8_t、u_int32_tなどのタイプは、すべて符号なしの整数タイプである。structタイプが、それら自体が（上記の「nread_ip」の例のように）structタイプであるフィールドを含む場合、その「ネストされた」structのフィールドは再帰的に、あたかも包含structのフィールドであるかのようにみなされる。したがって、こうしたネストされたstructタイプを効果的に「平坦化」した。これは、structタイプに対するポインタが存在する場合はtrueでないことに留意されたい。ネストされたstructタイプが排除（ポインタ・タイプ・フィールドなど）を含む場合、包含構造タイプを除外するように解釈されるべきである。
【００８１】
図９は、いくつかの実施形態に従った、汚染性エラー報告を示すスクリーン・ショットである。エラーを識別した後、元のソース・コード位置に関してＡＳＴ内で得られた情報が、元のソース・コードのコンテキストでエラーを示すために使用される。例示的なスクリーン・ショットは、「bad1」及び「redmond_bug」のコード例に関する例示の汚染性エラー報告を示す。
【００８２】
上記の実施形態は、第１に汚染されたソースを識別すること、更にその後、その汚染されたソースがシンクによって消費されるかどうかを判別し、それによってそのシンクを汚染性シンクと表現することによって進行するが、別の方法として、その逆順も可能である。これに代わって、第１にシンクを識別すること、更にその後、汚染されたソースがそのシンクによって消費されるかどうかを判別し、それによってそのシンクを汚染性シンクと表現することによって進行する。この代替手法では、シンクが識別されると、そのシンクによって消費されるソース・データが実行経路内で逆方向に追跡され、それらが汚染されているか否かを判別する。
【００８３】
順方向又は逆方向のいずれの追跡を使用するかにかかわらず、汚染されたソースを識別するためにキャスト・オペレーションを使用することの利点は、キャスト・オペレーションが通常は、データを消費するためのシンクと機能的に近似して実行される点であることを理解されよう。したがって、データが汚染されたシンクによって消費されるかどうかを確認するため（順方向追跡）、又は、シンクによって消費されるデータが汚染されているかどうかを判別するため（逆方向追跡）に必要な、実行経路を通じた追跡の量は、典型的には比較的短い。
【００８４】
代替として、追跡の代わりにデータ・フロー・グラフが採用され得る。データ・フロー・グラフは、プログラム変数、関数呼び出し戻り値などの他の値のソース、及び関数呼び出し引数などの他の値のシンクを表す、ノードと、割り当て、関数戻り、及び、データが縁部の一方の端にあるノードから他方にあるノードへと「流れる」ことを示す関数引数受け渡しを表す、それらのノード間の指向性縁部と、からなる。こうしたグラフにおけるノードは、汚染されたソースとして識別され得る。こうしたグラフ内の他のノードは、汚染性シンクとして識別され得る。汚染エラーは、汚染されたソース・ノードから始まり、いくつかの一連の指向性縁部及び他のノードをたどり、汚染性シンク・ノードで終わる、グラフを介した経路が存在する場合に発生する。ロー・メモリ・ポインタから外在性の標識を有する構造化タイプに対するポインタへのキャストは、キャストされる構造タイプのフィールドがこうしたデータ・フロー・グラフにおいて汚染されたソースとして扱われるべきであることの証拠の１つのソースである。
【００８５】
ハードウェア実施形態
図１０は、本明細書で論じられる方法のうちのいずれかの１つ又は複数をコンピュータに実行させるために、内部で命令セットが実行され得る、コンピュータ処理システムを示すブロック図である。いくつかの実施形態では、コンピュータはスタンドアロン・デバイスとして動作するか、又は他のコンピュータに接続（ネットワーク化）され得る。ネットワーク化された配置では、コンピュータは、サーバ・クライアント・ネットワーク環境におけるサーバ又はクライアント・コンピュータの容量内で、或いはピアツーピア（又は分散型）ネットワーク環境におけるピア・コンピュータとして、動作可能である。ネットワーク化された配置では、コンピュータは、サーバ・クライアント・ネットワーク環境におけるサーバ又はクライアント・コンピュータの容量内で、或いはピアツーピア（又は分散型）ネットワーク環境におけるピア・コンピュータとして、動作可能である。
【００８６】
実施形態は、従来のチャネルを介して販売又は使用許諾されることに加えて、例えばSoftware-as-a-Service（ＳａａＳ）、Application Service Provider（ＡＳＰ）、又はユーティリティ・コンピューティング・プロバイダによっても配置可能である。コンピュータは、サーバ・コンピュータ、パーソナル・コンピュータ（ＰＣ）、タブレットＰＣ、セットトップ・ボックス（ＳＴＢ）、携帯情報端末（ＰＤＡ）、携帯電話、或いは、そのデバイスによって行われる動作を指定する命令セットを（順次又はそれ以外の方法で）実行することが可能な任意の処理デバイスとすることができる。更に、単一のコンピュータのみが図示されているが、「コンピュータ」という用語は、本明細書で考察される方法のうちの任意の１つ又は複数を実行するための（１つ又は複数の）命令セットを、個別又は共同で実行する、任意のコンピュータの集合を含むと解釈されるものとする。
【００８７】
例示のコンピュータ処理システム１０００は、バス１００８を介して互いに通信する、プロセッサ１０２２（例えば中央処理ユニット（ＣＰＵ）、グラフィクス処理ユニット（ＧＰＵ）、又はその両方）、主メモリ１００４、及び静的メモリ１００６を含む。処理システム１０００は、ビデオ・ディスプレイ・ユニット１０１０（例えばプラズマ・ディスプレイ、液晶ディスプレイ（ＬＣＤ）、又は陰極線管（ＣＲＴ））を更に含むことができる。処理システム１０００は、英数字入力デバイス１０１２（例えばキーボード）、ユーザ・インターフェース（ＵＩ）ナビゲーション・デバイス１０１４（例えばマウス、タッチ・スクリーンなど）、ディスク・ドライブ・ユニット１０１６、信号生成デバイス１０１８（例えばスピーカ）、及びネットワーク・インターフェース・デバイス１０２０も含む。
【００８８】
ディスク・ドライブ・ユニット１０１６は、本明細書で説明される方法又は機能のうちの任意の１つ又は複数によって具体化又は使用される、命令及びデータ構造（例えばソフトウェア１０２４）の１つ又は複数のセットがその上に記憶される、コンピュータ読み取り可能記憶デバイス１０２２を含む。ソフトウェア１０２４は、主メモリ１００４などのコンピュータ読み取り可能記憶デバイス内に、及び／又は、処理システム１０００による実行中にプロセッサ１００２内に、完全に又は少なくとも部分的に常駐することも可能であり、主メモリ１００４及びプロセッサ１００２は、コンピュータ読み取り可能有形媒体も構築する。
【００８９】
更にソフトウェア１０２４は、いくつかの周知の転送プロトコル（例えばＨＴＴＰ）のうちのいずれか１つを使用するネットワーク・インターフェース・デバイス１０２０を介し、ネットワーク１０２６を通じて送信又は受信され得る。
【００９０】
コンピュータ読み取り可能記憶デバイス１０２２は、例示の実施形態内では単一の媒体として示されているが、「コンピュータ読み取り可能記憶デバイス」という用語は、１つ又は複数の命令セットを記憶する、単一媒体又は複数媒体（例えば、集中型又は分散型のデータベース、及び／又は関連付けられたキャッシュ及びサーバ）を含むものと解釈されるべきである。「コンピュータ読み取り可能記憶デバイス」という用語は、コンピュータによる実行のための命令セットを記憶、符号化、又は担持することが可能であり、更に本出願の方法のうちの任意の１つ又は複数をコンピュータに実行させる、或いは、こうした命令セットによって使用されるか又はそれらに関連付けられたデータ構造を記憶、符号化、又は担持することが可能である、任意の媒体を含むものとも解釈されるものとする。それに応じて「コンピュータ読み取り可能記憶デバイス」という用語は、ソリッド・ステート・メモリ並びに光及び磁気媒体を含むが、これらに限定されないと解釈されるものとする。
【００９１】
単一のインスタンスとして本明細書で説明された構成要素、オペレーション、又は構造には、複数のインスタンスが提供可能である。最後に、様々な構成要素、オペレーション、及びデータ・ストア間の境界は幾分任意であり、特定の例示の構成との関連において特定のオペレーションが示されている。機能の他の割り振りが想定され、本発明の範囲内に含まれ得る。一般に、例示的構成内で別々の構成要素として提示された構造及び機能は、組み合わせられた構造又は構成要素として実装され得る。同様に、単一の構成要素として提示された構造及び機能は、別々の構成要素として実装され得る。これら及び他の変形、修正、追加、及び改良は、本発明の範囲内に含まれる。
【００９２】
したがって、実施形態の前述の説明及び図面は、本発明の原理の単なる例示である。添付の特許請求の範囲内に定義された本発明の趣旨及び範囲から逸脱することなく、当業者による実施形態に対する様々な修正が可能である。
【００９３】
付録Ａ及び付録Ｂ
付録Ａはコード・リストである。付録Ｂは、付録Ａのコード・リストから生成された抽象構文木である。
付録Ａ及び付録Ｂは、この参照により本明細書に明示的に組み込まれる。
【００９４】
【表１００】
2014056567.tif 000014
【００９５】
【表２００】
2014056567.tif 000015
【００９６】
【表３００】
2014056567.tif 000016
【００９７】
【表４００】
2014056567.tif 000017
【図５】
2014056567.tif 000018
【図６】
2014056567.tif 000019
【図７】
2014056567.tif 000020
【図８】
2014056567.tif 000021
【図９】
2014056567.tif 000022
【図１】
2014056567.tif 000023
【図２】
2014056567.tif 000024
【図３】
2014056567.tif 000025
【図４】
2014056567.tif 000026
【図１０】
2014056567.tif 000027
【外国語明細書】
2014056567000001.pdf