2

コンテキスト：z3を使用して制限付きJavaプログラムの検証について調査します。線形化問題の最適化モデルを取得したいと思います。標準的なアプローチは、不満のケースが見つかるまでモデルを段階的に検索することです。しかし、パフォーマンスは問題のようであり、z3 c / c ++ apiをツールに統合するJNIを導入することにより、コードの移植性が損なわれます。

ここで、Javaメソッドのすべての入力に制約を追加したいと思います。私は量配列を使用します（ヒープをモデル化するために配列の理論を使用します）。ただし、z3は、満足のいく問題が発生すると、常に「不明」をすぐに返します。モデルを生成することは不可能のようです。z3、INST_GENのオプションがあることに気づき、それを理解しようとしています。次の式をz3にフィードします。

(set-option :INST_GEN true)
(define-sort S () (_ BitVec 2))
(declare-fun s () S)
(assert (= s (_ bv0 2)))

(define-sort A () (Array S S))
(push) ;; 1st case    
(assert (forall ((a A)) (= (select a s) s)))
(check-sat)
(get-model)
(pop)

(push) ;; 2nd case
(declare-fun a () A)
(assert (forall ((t S)) (= (select a t) t)))
(check-sat)
(get-model)
(pop)

(push) ;; 3rd case
(check-sat)
(get-model)
(pop)

1番目と2番目のケースの両方で、z3はLinuxでは「セグメンテーション違反」を返しますが、Windows7ではクラッシュします。両方のz3はバージョン4.0、x64です。

3番目のケースでは、定量化フリーであり、Z3はモデルを正常に生成します

sat 
(model (define-fun s () (_ BitVec 2) #b00) )

私の最初の質問は、このオプションがどのように機能するかです。配列を列挙しますか？

2番目の質問は、z3が、配列の定量化に関する満たされていない問題に対して「unsat」を正常に返す可能性があることに気付きました。z3は、制限されたインデックスと要素を使用して、定量化された配列で満足のいく問題でモデルを生成するためのオプションまたはアプローチをサポートしていますか？たとえば、if-then-else句を使用します。

読んでいただきありがとうございます！どんな提案でも大歓迎です！

4

1 に答える 1

2

まず、オプションINST_GENは実験の一部でした。外部ユーザーに公開されるべきではありませんでした。このオプションは真剣にテストされていません。将来のバージョンでは非表示になります。申し訳ありません。

第2に、一般に、Z3は、配列を定量化する満足のいく問題で失敗します。次のチュートリアル（セクションQuantifiers）では、Z3が完成している多くのフラグメントについて説明します。

最後に、Z3には多くの異なるエンジン/ソルバーがあります。ただし、インクリメンタルソルビングをサポートしているのはそのうちの1つだけです。push/コマンドが使用されると、 Z3popは自動的にこのインクリメンタルソルバーに切り替わります。pushandコマンドを削除するとpop、Z3は2番目の問題が満たされることを示すことができます。変更された例へのリンクは次のとおりです：http：//rise4fun.com/Z3/apcQ。

于 2012-07-13T05:56:27.523 に答える