使约束求解器更难解决约束?
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
仍然做得很好并且可以迅速解决它。
我知道一些加密哈希函数或数学公式(例如 Collatz 猜想)可能会使约束求解变得非常困难。但这似乎很极端。另一方面,例如假设我有以下约束:
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 == hash
或 hash % 1234 == 0 && hash & 0xF == 7
。只要有足够的计算能力,Z3 完全可以满足任何条件。
我个人觉得这种能力非常迷人。
我是 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
仍然做得很好并且可以迅速解决它。
我知道一些加密哈希函数或数学公式(例如 Collatz 猜想)可能会使约束求解变得非常困难。但这似乎很极端。另一方面,例如假设我有以下约束:
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 == hash
或 hash % 1234 == 0 && hash & 0xF == 7
。只要有足够的计算能力,Z3 完全可以满足任何条件。
我个人觉得这种能力非常迷人。