プログラムの自動テスト

はじめに

長い間、プログラムの動的分析はソフトウェアの欠陥を検出するには重すぎるアプローチであり、結果は労力とリソースを正当化しないと考えられていました。 ただし、現代のソフトウェア業界の発展における2つの重要な傾向により、この問題を改めて見直すことができます。 一方では、ソフトウェアの量と複雑さが絶えず増加しているため、エラーを検出し、品質管理を自動で行う手段は、有用で需要があります。 一方、現代のコンピューティングシステムの生産性の継続的な成長により、ますます複雑化するコンピューティングの問題を効率的に解決できます。 SAGE 、 KLEE 、 Avalancheなどの動的解析の分野における最近の研究は、このアプローチに固有の複雑さにもかかわらず、少なくとも一部のクラスのプログラムではその使用が正当化されることを示しています。

動的分析と静的分析

動的分析のより効果的な代替手段として、静的分析がしばしば検討されます。 静的分析の場合、考えられるエラーの検索は、たとえばアプリケーションのソースコードによって、調査中のプログラムを起動せずに実行されます。 通常、この場合、抽象的なプログラムモデルが構築されますが、これは実際には分析の対象です。

この場合、静的解析の次の特徴を強調する必要があります。

• プログラムの個々のフラグメント（通常は個々の関数または手順）の個別の分析が可能です。これにより、分析の複雑さの非線形の増加に対処するかなり効果的な方法が提供されます。
• 誤検知が発生する可能性があるのは、抽象モデルを構築するときに一部の詳細が無視されるか、モデルの分析が網羅的でないためです。
• 欠陥が検出されると、まず、検出された欠陥の真理を検証する問題（ 偽陽性 ）があり、次に、プログラムが特定の入力データで起動されたときに発見された欠陥を再現する問題があります。

静的分析とは異なり、プログラムの実行中に動的分析が実行されます。 この場合：

• プログラムを実行するには、いくつかの入力が必要です。
• 動的分析は、特定の入力データによって定義されたパス上でのみ欠陥を検出します。 プログラムの他の部分にある欠陥は検出されません。
• ほとんどの実装では、プログラムでエラーが発生したときにエラーが検出されるため、誤検知の出現は除外されます。 したがって、検出されたエラーは、プログラムモデルの分析に基づいて行われた予測ではなく、その発生の事実のステートメントです。

申込み

自動テストの主な目的は、Webサーバー、SSHクライアント/サーバー、サンドボックス、ネットワークプロトコルなど、入力データの操作性とセキュリティが最も重要な優先事項であるプログラムです。

ファズテスト（ファジング）

ファジングは、無効なデータ、意図しないデータ、またはランダムなデータをプログラムの入力に送信するテスト手法です。



このアプローチの主なアイデアは、ランダムに「突然変異」させることです。 任意の場所で予想される入力データを変更します。 すべてのファザーはほぼ同じように機能し、特定のバイトまたは一連のバイトで入力データを変更する際にいくつかの制限を設定できます。 例として、 zzuf（linux） 、minifuzz（Windows）、filefuzz（Windows）を挙げることができます。 プロトコルファザー： PROTOS（WAP、HTTP応答、LDAP、SNMP、SIP）（Java） 、 SPIKE（linux） ファザーフレームワーク： Sulley（複雑なデータ構造を作成するためのフレームワーク） 。

ファズテストは、自動テスト、ブルートフォースメソッドの先駆けです。 このアプローチの利点のうち、そのシンプルさだけが際立っています。 明らかな欠点は、ファザーがプログラムの内部構造について何も知らないことであり、最終的にはコードを完全にカバーするために、 天文学的な数のオプションを並べ替えることを余儀なくされます（ご想像のとおり、完全な列挙は入力データO（c ^ n）のサイズから指数関数的に成長します） c> 1）。

新世代のファザー（レビュー）

自動テストのアイデアの論理的ではあるがそれほど単純ではない継続は、研究中のプログラムの詳細を考慮して、可変入力データに制限を課すことができるアプローチとプログラムの出現でした。

プログラムでタグ付きデータを追跡する

シンボリックまたはマークされた（ 汚染された ）データの概念が導入されました-外部ソース（標準入力ストリーム、ファイル、環境変数など）からプログラムによって受信されたデータ。 この問題の一般的な解決策は、open、close、read、write、lseek（Avalanche、KLEE）のシステムコールのセットをインターセプトすることです。

コード計測

調査中のプログラムのコードは、分析に便利な形式に縮小されます。 たとえば、内部valgrind （Avalanche）表現が使用されたり、解析しやすいllvmバイトコードプログラム（KLEE）が分析されます。



インストルメントされたコードにより、潜在的に危険な命令（たとえば、ゼロによる除算またはNULLポインターの逆参照）とそのオペランド、およびマークされたデータに依存する分岐命令を簡単に見つけることができます。 指示を分析すると、ツールはマークされたデータの論理条件を作成し、実行可能性の要求をブール式の「ソルバー」（ SAT Solver ）に送信します。

ブール制約の解決

SAT Solvers-ブール式の実行可能性の問題を解決します。 彼らは質問に答えます：与えられた式は常に実行され、常にではない場合、値のセットが発行され、それが偽です。 このようなソルバーの作業の結果は、 定理証明からバイオインフォマティクスの遺伝暗号アナライザーまで、幅広い分析プログラムで使用されます。 このようなプログラムは、それ自体が興味深いものであり、個別に検討する必要があります。 例： STP 、 MiniSAT 。

環境モデリング

ブール式の「ソルバー」の条件を自動的に生成するには、システムコールのインターセプトに加えて、アナライザーはタスクを形式化する必要があります。 入力ファイル、レジスタのセット、およびプログラムのアドレス空間（メモリ）は、ブール「ソルバー」の配列を使用して表されます。

プログラム内のパスを検索する

「ソルバー」から応答を受け取った後、ツールは入力データの条件を受け取り、調査中の条件付き遷移を反転するか、常に真または偽であることを発見します。 条件の各バリアントは、プログラム内に新しい独立したパスを作成します。プログラムは、各パスと条件を個別に満たすために考慮する必要があります。 入力に応じて、各分岐命令のパス「 fork 」。 新しい入力データは、調査中のプログラムの以前に開かれていないベースブロックを開く場合があります。 徹底的なテストを行うには、プログラムで可能なすべてのパスの完全な列挙が必要です。 パスの数の増加率は、ブルートフォース法（〜O（2 ^ n）、nは入力データに応じた条件付き遷移の数）と比較して大幅に減少しますが、依然として重要です。 アナライザーは、特定のパスの分析に優先順位を付けるために、さまざまなヒューリスティックを使用せざるを得ません。 特に、カバーされていない（新しい）基本ブロック（Avalanche、KLEE）の最大数をカバーするパスの選択とランダムパス（KLEE）の選択を区別します。

雪崩

Avalancheは、動的解析によるソフトウェア欠陥検出ツールです。 Avalancheは、Valgrindが提供するプログラムの動的インスツルメンテーション機能を使用して、プログラム実行パスを収集および分析します。 この分析の結果は、プログラムでエラーが発生した入力データのセット、または以前に実行されなかったため、まだ検証されていないプログラムフラグメントをバイパスできる新しいテストデータのセットです。 したがって、単一のテストデータセットを使用して、Avalancheは反復動的分析を実装します。このテストでは、さまざまな自動生成されたテストデータに対してプログラムが繰り返し実行されます。

仕事の一般的なスキーム

Avalancheツールは4つの主要コンポーネントで構成されます。2つのValgrind拡張モジュール（プラグイン） -TracegrindおよびCovgrind 、STP制約検証ツール、および制御モジュール。



Tracegrindは、分析されたプログラム内のタグ付きデータのフローを動的に監視し、失敗した部分をバイパスし、危険な操作をトリガーするための条件を収集します。 これらの条件は、制御モジュールによってSTPに送信され、実行可能性が調査されます。 条件のいずれかが実行可能である場合、STPは、条件を真にする条件（入力ファイルのバイトを含む）に含まれるすべての変数の値を決定します。

• 危険な操作の操作の条件が満たされた場合、プログラムは、検出されたエラーを確認するために、対応する入力ファイルを使用して（今回は計装なしで）コントロールモジュールによって再度起動されます。
• プログラムの失敗した部分をバイパスするための実行可能な条件は、新しいプログラムの起動のための可能な入力ファイルのセットを決定します。 したがって、各プログラムの開始後、STPツールは、後続の分析開始のために多数の入力ファイルを自動的に生成します。
• 次に、この「最も興味深い」入力データのセットから選択するというタスクが発生します。 まず、最も可能性の高いエラーの発生を処理する入力データ。 この問題を解決するために、プログラムで以前に渡されたベースブロックの数であるヒューリスティックメトリックが使用されます（ベースブロックは、Valgrindフレームワークで定義された意味でここで理解されます）。 ヒューリスティック値を測定するには、Covgrindコンポーネントを使用します。その機能には、実行時エラーの修正も含まれます。 CovgrindはTracegrindよりもはるかに軽いモジュールなので、以前に受信したすべての入力ファイルのヒューリスティック値を比較的迅速に測定し、最高値の入力ファイルを選択することができます。

制限事項

• マークされた1つの入力ファイルまたはソケット
• エラー分析は、nullポインターの参照解除とゼロ除算に限定されます。

結果

Avalancheのバグ検出パフォーマンスは、多数のオープンソースプロジェクトでテストされています。

• qtdump （libquicktime-1.1.3）。 ヌルポインターの逆参照に関連する3つの欠陥、1つ-無限ループの存在、別の場合には、不正なアドレスへのアピール（セグメンテーションエラー）。 一部の欠陥は開発者によって修正されています。
• flvdumper （gnash-0.8.6）。 障害がすぐに発生するのは、アプリケーションが使用するブーストライブラリの例外が原因です（ブーストライブラリの内部ポインターの1つがゼロであることが判明します）。 アプリケーション自体は発生した例外をキャッチしないため、プログラムはSIGABRTシグナルで終了します。 欠陥は開発者によって修正されています。
• cjpeg （libjpeg7）。 アプリケーションはファイルからゼロ値を読み取り、適切な検証なしにそれを除数として使用します。これにより、浮動小数点例外が発生し、SIGFPEシグナルでプログラムが終了します。 欠陥は開発者によって修正されています。
• swfdump （swftools-0.9.0）。 両方の欠陥の発生は、nullポインターの逆参照に関連しています。

クリー

KLEEは、疑わしい場所を探すのではなく、可能な限り多くのコードをカバーし、プログラム内のパスの徹底的な分析を行うという点で、Avalancheとは多少異なります。 一般に、KLEEスキームは雪崩に似ていますが、他の基本的なツールを使用して問題を解決します。これにより、制限が課され、利点が得られます。

• Avalancheで使用されるvalgrindのインストルメンテーションの代わりに、KLEEはllvmバイトコードでプログラムを解析します。 したがって、これにより、llvmバックエンドがあるプログラミング言語でプログラムを分析できます。
• ブール制約の問題を解決するために、KLEEはSTPも使用します。
• また、KLEEは約50のシステムコールをインターセプトし、複数の仮想プロセスが互いに干渉することなく並行して実行できるようにします。
• STPへのリクエストの最適化とキャッシュ。

KLEEは、 シンボリックプロセスが並行して実行されるシンボリック仮想マシンです（用語KLEE： statesのフレームワークで）。各プロセスは、検討中のプログラムのパスの1つです。 このようなプロセスの分岐を（システムによってではなく）プログラムの各ブランチに効果的に実装すると、多数のパスを同時に分析できます。

移動した一意のパスごとに、KLEEはそのパスに沿って移動するために必要な入力データのセットを保存します。

KLEE機能を使用すると、指定された入力データの全範囲にわたって、2つの関数の等価性を低コストでチェックできます（広範なAPIが提供されます）（ 機能するプロトタイプに対して同一の機能をチェックし、リファクタリングします ）。

次の例は、この機能を示しています。

unsigned mod_opt （ unsigned x、 unsigned y ） {

if （ （ y ＆ −y ） == y ） // 2のべき乗？

return x ＆ （ y− 1 ） ;

他に

x ％ yを返し ます。

}

符号なし mod （ 符号なし x、 符号なし y ） {

x ％ yを返し ます。

}

int main （ ） {

符号なし x、y ;

シンボリック（ ＆ x、 sizeof （ x ） ） ;

シンボリック（ ＆ y、 sizeof （ y ） ） ;

assert （ mod （ x、y ） == mod_opt （ x、y ） ） ;

0を 返し ます 。

}

この例でKLEEを実行すると、入力値の範囲全体（y！= 0）で2つの関数の等価性を検証できます。 アサーションの条件が満たされないという問題を解決するために、可能なすべてのパスを列挙することに基づいて、KLEEは、値の範囲全体で2つの関数が同等であるという結論に達します。

結果

実際のテスト結果を得るために、著者はcoreutils 6.11のプログラムセット全体を分析しました。 コードカバレッジの平均割合は94％でした。 合計で、プログラムは3321セットの入力データを生成し、指定された割合のコード全体をカバーできるようにしました。 また、パッケージの開発者によってプログラムの実際の欠陥として認識された10の固有のエラーが見つかりました。これは、このプログラムセットが20年以上にわたって開発されており、ほとんどのエラーが解消されたためです。

制限事項

• マルチスレッドアプリケーション、シンボリック浮動小数点データ（STP制限）、アセンブラー挿入のサポートはありません。
• テストされたアプリケーションは、llvm-byteコード（およびそのライブラリ！）にコンパイルする必要があります。
• 効果的な分析を行うには、コードを編集する必要があります。

予備調査結果

もちろん、動的分析は、個々のプログラマーやプログラマーのチームがタスクを解決するのに役立つツールの中にニッチを見つけるでしょう。 は、プログラム内のエラーを見つける効果的な方法であると同時に、プログラムにエラーがないことを証明するものです！ 場合によっては、そのようなツールは非常に重要です（ミッションクリティカルなソフトウェア：RTOS、生産管理システム、航空ソフトウェアなど）。

おわりに

記事のトピック（雪崩とKLEEでのいくつかの経験の結果、KLEEとAvalancheの比較、S2Eのレビュー（https://s2e.epfl.ch）（Selection Symbolic Execution））は、Habrの読者からの肯定的なフィードバックの対象となります。



この記事には、次の作品の断片が含まれています： avalanche_article 、 KLEE 、 fuzzテストの使用 。