シンボリック実行とSATソルバーの違いは何ですか？

Question

私の理解は、シンボルの実行が特定のパスと悪いパターンを扱いますが、SATソルバー、または一般的な充満性モジュロ理論は、プログラムのはるかに堅牢な分析を提供します。

誰かが上記の声明を検証することができ、（簡単に）これら2つの正式な検証方法論の違いを説明してくださいか？

Answer 1

tl; DR：それらは基本入力と出力が異なります。 SATおよびSMTソルバーはどのプログラムがあるかわかりません。彼らは数学的な式についてはい、またはいいえの質問に答えるツールです。一方、記号の実行はプログラムを分析する方法です。記号の実行は通常、SATおよびSMTソルバーに依存していますが、その逆のまわりではありません。

---

SATおよびSMTソルバープログラムとの関係には何もしないでください。代わりに、SATまたはSMTソルバーは入力として数学的に説明されている「式」、および答え、おおまかに、それが真実か偽であるかどうか。 （3番目のオプションが許可されていることが多く、ソルバーが回答を把握できない場合は不明です。）

例えば、SATソルバーへの入力可能入力は(a and not b) or (not a and c)です。すなわち、ここではa、b、およびcがブール値（0または1）の定数である数式です。 SATソルバーは、a、b、およびcの値を選択することによって、式が本当であるかどうかを判断することになっています。 SMTソルバーは似ていますが、a、b、およびcは、整数、文字列、機能などを使用して、より複雑な式に置き換えられます。

---

シンボル実行は、プログラムを実行する派手な方法であるが、プログラムの実行を目的とした方法ではありません。代わりに、プログラムは、いわゆる「シンボリック」値を使用して実行されます。これは、優しいプレースホルダーです。その意味の例として、x + 3 = y^2のような関数があるとします。現在、f(x) = if x > 0 then 1 else 0が3より大きいため、通常、Pref(3) = 1を入力することによってプログラムを実行します。シンボリック実行では、プレースホルダ変数3を入力してプログラムを実行し、2つのケースを得るためにプログラムを評価します.0またはinput。これは役に立たないように思えるかもしれませんが、それはプログラムを分析する強力な方法であることになります。

---

2つのの間の接続は、記号の実行が実行中にSMTソルバーに頼ることがしばしば依存し、特定のパスが実際に可能なか、または破棄されるべきかどうかを把握します。たとえば、SMTソルバーを使用して、input > 0 and answer = 1が可能かどうかを判断できます（答えはYESです。たとえば、input <= 0 and answer = 0）。このようにして、SMTは、記号の実行が可能なものの背後にある「推進力」のようなものです。