mathematics.と説明されています。形式手法として紹介されることも多いです。(PDF)形式的検証は、記述として検証する方法から数学的にプログラムが正しく実行されることを検証する仕組みまで含みます。数学的な形式的検証では、可能な限り、全ての状態を検証できるようにしてプログラムが正しく実行できることの証明を試みます。DbC)も形式的検証の1つの方法です。セキュリティ問題)の確率も爆発的に増えることが解ります。形式的検証の歴史はとても古くBC1800年ころ1のバビロニアンの時代まで遡ります。BC400年ころにはPlatoも研究1していたようです。身近な20世紀前半の1930年頃には「コンピューター」の開発に取り組んでいたアラン・チューリング、フォン・ノイマンらにより盛んに研究1されるようになります。形式的手法の研究と実践は既に50、60年代の欧州では盛んだった2そうです。コンピューターシステムエンジニアリングに於ける形式的検証は70年代に欧州を中心に仕様記述方法として発展し、80年代にモデル検査手法も開発されます。1990年代にはモデル検査と手法ツールの「SPIN」「SMV」「Uppaal」などが無償で公開されます。Diagram)は状態を0と1で表せる為、コンピューターハードウェア設計と相性がよくデジタル回路設計で実用的に利用されてきました。Reductionによる通信プロトコルの検証などが行われています。ソフトウェア分野では出遅れていた感が拭えない日本でしたが、2000年代にUMLが流行り出した頃、形式的検証もモデルやコードを検証する仕組みとして一部の企業では導入されています。SONY(フェリカネットワークス)がモバイルFeliCaを開発した際には仕様を10万行にも及ぶVDM++を記述し、仕様段階で440件のバグを修正した3としています。聞きなれない方も多いかもしれない形式的検証ですが、契約プログラミング(契約による設計)はソフトウェア開発者の多くが知っていると思います。これも形式的検証手法の一種です。形式的検証は、デジタル回路設計に於ては確立した実用的な手法であり、ソフトウェア設計でも実用的に使われています。借りて簡単に紹介します。4を知っている方なら「基本的には契約プログラミングと同じだ」と理解ると思います。条件(ASSERT)が成立することを検証(確認)することにより、プログラムが正しく実行されることを検証(証明)できるようにすること形式検証では求めます。プログラムが正しく実行されることを検証(証明)するには、全ての状態(入力を処理の結果)を検証(証明)しなければなりません。基本的な考え方としては次の図のような検証を行い、正しく実行されることを証明します。推論による証明は”全てのケースを総当たりせず”に正しく実行を可能であることを証明します。生成による証明は”全てのケースを総当たりして”、正しく実行を可能であることを証明します。全てのコードを推論によって簡単に「正しさを証明」できるなら良いのですが、現実のプログラムはそういうモノではありません。簡単に推論により証明できるなら既に、バグがないソフトウェアを保証するツール、が世の中の常識になっているでしょう。全てのケースを総当たりして正しさを検証せざるを得ない、が現状です。このため実際に総当たり的に検証する、といったアプローチが取られています。Unitテストも”総当たり型”の検証方法ですが、形式的検証とは考えられていません。全てのケースを総当たりして正しさを検証せざるを得ない、このため実際に総当たり的に検証する、といっても簡単なプログラムならまだしも実用的なプログラムになると、「全てのケースを総当たり」する「組み合わせ」は簡単に膨大な数になります。ある入力が32bit整数だとします。まで、約43億のパターンがあります。43億になり、およそ1.8e+19のパターンを総当たりすることになります。膨大な数ですが、実用的なプログラムの入力は32bit整数が2つではありません。整数のみでなく文字列やもっと複雑な構造体的なデータを当たり前に取り扱います。単純なケースを少し考えただけで、まともに真の総当たりで検証することは不可能と解ります。計算できない程の大量のパターンが爆発的に発生する問題が「組み合わせ爆発」問題です。実用的なプログラムの複雑性だと簡単に「組み合わせ爆発」が発生します。このため、総当たり的な形式検証では「組み合わせ爆発」が起きない様、仕組み的な工夫はもちろん、必要でない入力は徹底的に廃除します。先ほどの32bit整数2つを入力として持つプログラムは”0〜100′′までの値しか取らない場合、”0〜100′′だけの入力を考えます。100たったの1万になり容易に検証可能な組み合わせ数になります。実際に形式検証で処理の正しさを証明しようとすると、パラメーターのパターンの掛け算になるので、個々のパラメーターの範囲がかなり絞られていてもかなり簡単に「組み合わせ爆発」が起きます。実際にはプログラムの実行経路は多数の組み合わせがあります。一つ一つの関数(ローレベルのライブラリなども含む)が受け入れる変数の範囲は膨大だからです。それが何千、何万も存在します。”無効な入力”の動作まで含めて”正しく処理”しよう、とするのは無謀と言えます。経路の組み合わせ爆発プログラムの場合、経路の組み合わせに加え、”状態の組み合わせ”がある。この為、プログラムでは簡単に組み合わせ爆発が発生する。プログラムに与える入力値は厳格に入力バリデーションするプログラムに与える入力値は厳格に入力バリデーションする、これはセキュアコーディングの第1原則です。プログラムが受け入れるべきでない入力値に対して、正しく動作することを証明しようとすること、は無駄でしかありません。仕様として”絶対に正しく実行できない”ことが判っているからです。)は、形式的検証でも、実際のプログラムでも廃除しなければなりません。セキュアコーディングの入力バリデーションで廃除される入力は、上記の図の赤い部分(不正な入力値)です。形式的検証で「本来検証の必要がないパターンを生む入力」とは「入力バリデーションで廃除される入力」です。「本来検証の必要がないパターンを生む入力」(不正な入力)、をプログラム中の処理に渡す事は全くの無駄であるだけでなく、不要な複雑性を生み、不必要なバグやセキュリティ問題の原因となります。入力とロジックのバリデーションが混同されています。勘違いしないよう注意。セキュアなアプリケーション構造のイメージ図は以下のようになります。契約による設計と信頼境界線まとめ厳格な入力バリデーションは形式的検証の主要な要素ではありませんが、形式的検証には絶対に欠かせない前提条件です。他のプログラムの複雑な要素と比べれば、厳格に入力バリデーションを行うことは簡単なことです。厳格な入力バリデーションをやらずに「プログラムの正しさを証明」しようとしても、原理的に無理です。原理:コンピュータは妥当な入力でしか正しく動作できないこの原理は変えられません。“apple”」の正しい答えは求めようがありません。6「脆弱性があったら、その脆弱性だけに着目して局所的に対策するの良い(入力検証はオマケ)」とする考え方もあります。この考え方では正しく動作することを網羅的に検証し証明することは非常に困難です。適切な入力検証がない場合、不具合を発生させる入力の組み合わせ数はコンピューターで処理することさえ不可能なほど膨大になります。これを漏れ無く人間が管理することは不可能です。動作できなくなる状況、を完全に解消することも不可能です。9「見つけた脆弱性をその場限り、場当たり的、尚かつ入力バリデーションなし、で一つ一つ潰していく」はベストプラクティスどころか、非論理的/非現実的なアンチプラクティスです。10入力バリデーションは、非常に重要ですが、セキュアなソフトウェア構築のほんの入り口に過ぎません。入り口から間違えてしまうと出口が遠くなるばかりです。8アプリケーションレベルでの入力バリデーションはセキュアなソフトウェア開発の基礎の基礎ですが、入力バリデーションがセキュリティ対策ではない、と勘違いさせられている開発者も少なくないと思います。10年以上も情報セキュリティ機関であるIPAが誤ったセキュアプログラミングを啓蒙し続けた影響は小さくないでしょう。参考:IPAは基礎的誤りを明示し、正しい原則を開発者に啓蒙すべき科学的なアプローチのセキュリティの基本概念は難しくありません。基本概念を知っているだけでも格段にセキュアなソフトウェアが作れるようになります。セキュリティ問題)の可能性が大幅に減少することが理解ったと思います。契約プログラミングのみで形式的検証は可能になりません。Unitテストなどから与えられた制約が維持されているか、チェックする必要があります。ファジングテストも制約違反の発見に役立ちます。これらのテストの網羅性が高ければ高いほど契約プログラミングによる形式的検証の精度が上がります。過去に議論した方には「クライアントが送ってくる値」に「攻撃者が攻撃ツールなどで送ってくる値」まで含めている方がいました。当然ですが、「クライアント送ってくる値」とは「正当で全うなユーザーが通常通り使って送信できる値」であり、攻撃ツールや異常な使い方をした場合の値まで含みません。“apple”」の正しい答え、”apple”をASCIIの合計とする、とするようなビジネスロジックも世の中にはあるかも知れません。“apple”」の正しい答え、はありません。「問題になった箇所でエラーにしてしまえば良い」と考えるかも知れませんが、出鱈目な入力を許可していると「エラーになる箇所」を特定することは、出鱈目な入力を許可することによって組み合わせ爆発が起こり、非常に困難です。Fastに反するアンチプラクティスです。↩ファジング(入力パラメーターに出鱈目な値を設定してテストする手法)でセキュリティ問題やバグが簡単に見つかります。この事実だけでも入力検証なしに出鱈目なデータ受け入れは行ってはならない、と解ります。ファジングは形式的検証ではなく、網羅性がありません。Fast原則に基づかないソフトウェア構造の場合、単純に問題を解決することが不可能なケースが複数あります。“セキュリティのゲーム”は攻撃者にとって圧倒的に有利なルールで行われます。攻撃者はたった1つの攻撃可能な箇所を見つけるだけで勝ちです。守る側は全ての問題に対処しなければなりません。その場しのぎ、モグラ叩きの対策でもマシにはなりますがマシでは困ります。良い設計や対策がある場合はそれを採用しないと”セキュリティのゲーム”に負けてしまいます。紹介エレクトロニック・サービス・イニシアチブのWebシステムのコンサルタントのブログです。PHPの開発、PHP4.x/5.xレガシーPHPセキュリティパッチサービスなどを行っています。ブログのサブタイトルを「書かない日記」としているのは、ブログを始めた時にあまり書かないつもりで始めたのでこのサブタイトルになっています。yohgaki@ohgaki.net私が記述したブログ中のコードは記載が無い場合はMITライセンスです。その他のコードは参考リンクなどのライセンス情報を参照ください。