将 `str.indexof` 与 `int2bv` 一起使用时性能不佳

Question

我试图将位向量约束为等于字符串中空字节的索引。但是，我遇到了 int2bv 的性能问题。

作为问题的一个简单例子，这个问题（没有int2bv）立即解决：

; Solve time: 0m0.065s
(declare-const s String)
(declare-const len Int)
(assert (= (str.indexof s "[=11=]") len))
(assert (>= len 256)) ; 0x100
(assert (<= len 4095)) ; 0xFFF
(check-sat)
(get-model)

另一方面，使用 int2bv 的 "same" 问题（它允许更多的解决方案）需要将近 2 分钟：

; Solve time: 1m54.861s
(declare-const s String)
(declare-const len Int)
(assert (= (str.indexof s "[=12=]") len))
(assert (>= len 0))
(assert (not (= (bvand ((_ int2bv 12) len) #xF00) #x000)))
(check-sat)
(get-model)

在z3中有没有更好的方法来编码这种位向量字符串长度操作？ These slides z3strBV 声称有更好的支持，但他们的扩展似乎没有在标准 z3 发行版中实现。

我正在使用 z3 版本 4.8.0 - 64 位和运行 smt.string_solver=z3str3。

Answer 1

通过反复试验，我发现选项 smt.str.use_binary_search=true 将第二个问题的解决时间缩短到 2 秒以下！不过不确定为什么此选项的默认值为 false。

将 `str.indexof` 与 `int2bv` 一起使用时性能不佳

Bad performance when using `str.indexof` with `int2bv`

smt

z3