プログラム分析

コンピュータサイエンスにおいて、プログラム分析^[1]とは、正確性、堅牢性、安全性、活性などの特性に関してコンピュータプログラムの動作を分析するプロセスです。プログラム分析は、プログラムの最適化とプログラムの正確性という2つの主要領域に焦点を当てています。前者はリソース使用量を削減しながらプログラムのパフォーマンスを向上させることに焦点を当てており、後者はプログラムが想定どおりに動作することを保証することに焦点を当てています。

プログラム分析は、プログラムを実行せずに (静的プログラム分析)、実行時に (動的プログラム分析)、またはその両方の組み合わせで実行できます。

プログラムの正確性の観点から見ると、静的解析はプログラムの開発段階で脆弱性を発見することができます。^[2]静的解析は脆弱性の根本原因を突き止めるため、これらの脆弱性はテスト段階で発見されたものよりも修正が容易です。

多くの形式の静的分析は計算上決定不可能であるため、それを実行するメカニズムは必ずしも正しい答えで終了するとは限りません。その結果、偽陰性(コードに実際に問題があるのに「問題は見つかりません」と表示される) または偽陽性が発生するか、または間違った答えを返さないが終了しない可能性もあります。これらの制限にもかかわらず、静的分析は依然として価値があります。最初のタイプのメカニズムは脆弱性の数を減らす可能性があり、2 番目のメカニズムは特定のクラスの脆弱性が存在しないことを確実に保証する場合があります。

不適切な最適化は非常に望ましくありません。そのため、プログラム最適化のコンテキストでは、計算上決定不可能な分析を処理するための 2 つの主な戦略があります。

1. 最適化コンパイラのオプティマイザーなど、比較的短時間で完了することが予想されるオプティマイザーは、有限の時間で完了することが保証され、正しい最適化のみが見つかることが保証されている分析の切り捨てバージョンを使用することがあります。
2. サードパーティの最適化ツールは、誤った最適化を決して行わないように実装されている場合もありますが、場合によっては、誤った最適化が見つかるまで無期限に実行し続けることもあります (決して起こらない可能性もあります)。この場合、ツールを使用する開発者は、ツールを停止し、そのコード部分でツールが再度実行されないようにする必要があります (または、ツールが失敗するのを避けるためにコードを修正する必要があります)。

ただし、 Cなどの完全に指定されていない言語に適用できる 3 番目の戦略もあります。最適化コンパイラは、使用中の言語標準でセマンティクスが指定されていないソース コードに遭遇した場合、実行時に何でもする (クラッシュすることもある) コードを自由に生成できます。

制御フロー分析の目的は、プログラム実行中のさまざまな時点でどの関数を呼び出すことができるかに関する情報を取得することです。収集された情報は、ノードがプログラムの命令、エッジが制御フローを表す制御フロー グラフ(CFG) で表されます。コード ブロックとループを識別することで、CFG はコンパイラによる最適化の開始点になります。

データフロー分析は、プログラムの各ポイントの値と、それらの値が時間の経過とともにどのように変化するかに関する情報を収集するために設計された手法です。この手法は、コンパイラーがコードを最適化するときによく使用されます。データフロー分析の最もよく知られた例の 1 つは、汚染チェックです。これは、ユーザー提供のデータを含むすべての変数 (「汚染されている」、つまり安全でないと見なされる) を考慮し、それらの変数がサニタイズされるまで使用されないようにします。この手法は、SQL インジェクション攻撃を防ぐためによく使用されます。汚染チェックは、静的または動的に実行できます。

抽象解釈により、実際にプログラムを実行することなく、プログラムの実行可能性に関する情報を抽出できます。この情報は、コンパイラーが可能な最適化を探したり、特定の種類のバグに対してプログラムを認証したりするために使用できます。

型システムは、特定の要件を満たすプログラムに型を関連付けます。その目的は、プロパティに従って正しいと見なされる言語のプログラムのサブセットを選択することです。

• 型チェック– プログラムが型システムによって受け入れられるかどうかを確認します。

プログラミングでは、プログラミング オブジェクトの使用方法と実行内容を制限するために型チェックが使用されます。これは、コンパイラまたはインタープリタによって行われます。型チェックは、符号付きの値が符号なしの変数に関連付けられないようにすることで、脆弱性を防ぐのにも役立ちます。型チェックは、静的 (コンパイル時)、動的 (実行時)、またはその両方の組み合わせで実行できます。

静的な型情報 (推論されたもの、またはソース コード内の型注釈によって明示的に提供されたもの) は、ボックス化された配列をボックス化されていない配列に置き換えるなどの最適化を行うためにも使用できます。

エフェクト システムは、関数またはメソッドの実行によって生じるエフェクトを表すために設計された形式システムです。エフェクトは、何が実行され、何を使用して実行されるかをコード化します。通常、それぞれエフェクトの種類とエフェクトの領域と呼ばれます。^{[説明が必要]}

モデル検査とは、モデル(この文脈ではコードの正式なモデルを意味しますが、他の文脈ではハードウェアのモデルの場合もあります) が特定の仕様に準拠しているかどうかを確認するための厳密で形式的な自動的な方法を指します。コードには固有の有限状態の性質があり、仕様とコードは両方とも論理式に変換できるため、効率的なアルゴリズム手法を使用してシステムが仕様に違反しているかどうかを確認することができます。

動的解析では、プログラムの実行時の知識を使用して解析の精度を高め、実行時保護も提供できますが、問題の 1 回の実行しか解析できず、実行時チェックによってプログラムのパフォーマンスが低下する可能性があります。

ソフトウェアは、その品質と、想定どおりに確実に機能すること、および同時に機能する可能性のある他のソフトウェアと競合しないことを保証するためにテストする必要があります。テストは、入力を使用してプログラムを実行し、その動作と生成された出力を評価することによって実行されます。セキュリティ要件が指定されていない場合でも、攻撃者がソフトウェアを改ざんして情報を盗んだり、ソフトウェアの通常の動作を妨害したり、ソフトウェアをユーザーへの攻撃の拠点として使用したりできないようにするために、追加のセキュリティ テストを実行する必要があります。

プログラム監視は、リソースの使用状況、イベント、相互作用など、プログラムに関するさまざまな種類の情報を記録してログに記録します。これにより、異常な動作の原因を発見または特定することができます。さらに、セキュリティ監査を実行するためにも使用できます。プログラムの自動監視は、ランタイム検証と呼ばれることもあります。

プログラムの動作の特定のサブセットについて、プログラム スライシングは、選択した動作を生成する最小形式にプログラムを縮小することです。縮小されたプログラムは「スライス」と呼ばれ、指定された動作サブセットのドメイン内で元のプログラムを忠実に表現したものです。通常、スライスを見つけることは解決不可能な問題ですが、一連の変数の値によってターゲットの動作サブセットを指定することにより、データフロー アルゴリズムを使用して近似スライスを取得できます。これらのスライスは通常、開発者がデバッグ中にエラーの原因を見つけるために使用されます。

• 自動コードレビュー
• 言語ベースのセキュリティ
• 多変量
• プロファイリング（コンピュータプログラミング）
• プログラム検証
• 終了分析

• Agrawal, Hiralal; Horgan, Joseph R. 動的プログラム スライシング(PDF)。
• Chunlei, Wang; Gang, Zhao; Yiqi, Dai (2009)。 「バイナリ実行ファイルに対する効率的な制御フロー セキュリティ分析アプローチ」。2009第 2 回 IEEE 国際コンピュータ サイエンスおよび情報技術会議。pp.  272– 276。doi :10.1109/ ICCSIT.2009.5234950。ISBN 978-1-4244-4519-6.S2CID 10551500  。
• ニールソン、フレミング;ニールソン、ハンネ・リース; ハンキン、クリス (2005)。プログラム分析の原則。Springer Science+Business Media。

• ウィキメディア・コモンズのプログラム分析に関連するメディア