使约束求解器更难解决约束?

Make a constraint more difficult to solve for a constraint solver?

我是 SMT 求解的新手,我写信是想咨询一些建议和指示,以了解什么是真正 difficult constraint 的 SMT 求解器可以求解的,例如 Z3。

我尝试调整位向量的长度,例如通过以下方式:

>>> a = BitVec("a", 10000)
>>> b = BitVec("b", 10000)
>>> c = a >> 18 + 6 - 32 + 69 == b <<12 + 7 * 32
>>>
>>> s = Solver()
>>> s.add(c)
>>> s.check()

虽然直觉上这可能会导致相当大的搜索 space,但事实证明 Z3 仍然做得很好并且可以迅速解决它。

我知道一些加密哈希函数或数学公式(例如 Collat​​z 猜想)可能会使约束求解变得非常困难。但这似乎很极端。另一方面,例如假设我有以下约束:

a * 4 != b + 5

如何让约束求解器更难求解?有什么通用的方法吗?我的印象是,不知何故,约束变成了 "non-linear",然后就很难了。但我仍然不清楚它是如何工作的。

=================================

感谢您提供的所有友好注释和有见地的帖子。我非常感激!

所以这里根据@usr的建议做了一些初步的测试:

c = BitVec("c", 256)

for i in range(0, 10):
    c = c ^ (c << 13) + 0x51D36335;

s = Solver()
s.add(c == 0xdeadbeef)
print (s.check())
print (s.model())


➜  work time python test.py
sat
[c = 37865234442889991147654282251706833776025899459583617825773189302332620431087]
python test.py  0.38s user 0.07s system 81% cpu 0.550 total

Bitvector 逻辑总是可判定的;所以虽然事情可能需要很长时间,但 z3 可以解决所有的位向量问题。当然,如果涉及的位向量大小很大,那么求解器可能需要很长时间,或者 运行 内存不足才能找到解决方案。乘法和加密算法是典型的例子,随着比特大小的增加总是会导致困难。

另一方面,我们有非线性整数问题。他们没有决策程序,虽然 z3 "tries its best," 出于理论上的原因,此类问题通常超出范围。您可以在 stack-overflow 帖子中找到许多此类实例。这是最近的一个:

如果您只想查看 Z3 "work really hard",您可以尝试数字因式分解,例如a * b = constant 并输入质数或大合数。

或者,构建一个简单的哈希函数并获得原像:

我所做的是查看 SHA-1 是如何定义的。然后,我实现了一个简单的版本。 SHA-1 由非常简单的操作组成,例如移位、加法、异或。从这个模板中,您可以构建一个简单的哈希函数用于测试目的。然后你说 y = hash(x) && y = 0x1234 Z3 会给你 x 这是原像。

为了娱乐大家,我现场编一个简单的哈希函数:

BitVec currentValue = input;

for (i = 0 to 10)
 currentValue = currentValue ^ (currentValue <<< 13) + 0x51D36335;

BitVec hash = currentValue;

这是一个实用的哈希实现(但不安全)。您可以玩操作、回合数和位向量大小。您可以断言 hash = someConstant 以获得原像。例如,让 Z3 给你一个 input 结果是零散列。

您还可以应用更多奇特的约束,例如 input == hashhash % 1234 == 0 && hash & 0xF == 7。只要有足够的计算能力,Z3 完全可以满足任何条件。

我个人觉得这种能力非常迷人。