python 中 Z3 的按位运算

Question

我又一次为 Z3 而苦恼。我正在尝试从我用 IDA 反汇编的二进制文件构建代码：

此函数被调用 0x80 次。 ecx 初始化为 0x40。 [rdi+8] 用 0xDEADFACEDEADBEEF 初始化。 rsi 从我试图找到的向量 "vec" 中获取每个字节，它的值只能是 0x30、0x31 和 0x32。我不确定我的逻辑是否正确，或者我没有使用正确的 Z3 功能。它不是 SAT，它应该是，因为最终向量 'v1' 在我的问题中应该包含值 0x123456701234567。我的代码：

from z3 import *

def set_number(vec,size): #vec
    for i in range(0, size * 8 - 8, 8):
        val = Extract(i + 7, i, vec)
        val = BV2Int(val,False)
        return Or(val==0x30,val == 0x31, val == 0x32)

s = z3.Solver()

size = 0x80
ecx = 0x40
v1 = BitVecVal(0xDEADFACEDEADBEEF,64)
vec = BitVec("inf",size*8) # <content from d.d file>
s.add(set_number(vec,size)) #40 bytes of {0,1,2}

for i in range(0, size*8-8, 8):
    val = Extract(i + 7, i, vec)
    val = BV2Int(val,False)
    if(val == 0x30):
        v1 = RotateLeft(v1, ecx)
        v1 = v1 >> 1
        v1 *= 2
        v1 = RotateRight(v1, ecx)
        ecx = ecx - 1
        s.add(ecx>=0)
    elif(val == 0x31):
        s.add(ecx<40 and ecx>=0)
        ecx = ecx+1
        v1 = RotateLeft(v1,ecx)
        v1 = v1 >> 1
        v1 *= 2
        v1 = RotateRight(v1,ecx)
        ecx = ecx+1
    elif (val==0x32):
        s.add(ecx < 40 and ecx >= 0)
        ecx = ecx + 1
        v1 = RotateLeft(v1, ecx)
        v1 = v1 >> 1
        v1 *= 2
        v1 = v1 | 1
        v1 = RotateRight(v1, ecx)
        ecx = ecx+1
s.add(v1 == 0x123456701234567)
s.check()

一如既往，非常感谢！

Answer 1

这里有一些问题，但最重要的是您对 if-then-else 的使用。使用符号值时，不能使用 Python 的 if-then-else。相反，您必须使用 z3 的 If 构造。

在你的程序中，你的 if-then-else 被具体评估，因此你在最后得到一个虚假的断言。您可以通过在调用 check.

之前放置 print s.sexpr() 来验证这一点

首先将所有 if-then-else's 替换为对 If 函数的调用。在每个步骤中查看 s.sexpr()（假设在每个 add 之后）并确保它包含正确的表达式。这应该会引导您对问题进行适当的编码。从这里开始阅读：https://z3prover.github.io/api/html/namespacez3py.html#a782883a35d4c6a0be62cd5333645dbaf

z3 编码风格

以下是我如何在 z3py 中对您的问题进行编码。请注意，我只是音译了您的 python 代码，因此如果您的代码中有任何错误，它们将被保留。请注意所有符号 "if-then-else" 计算是如何通过调用 z3py 的 If.

单独完成和合并的

from z3 import *

size = 0x80
vec = BitVec("inf", size * 8)

s = Solver()

# Every byte in vec is either 0x30, 0x31 or 0x32
for i in range(0, size*8, 8):
    b = Extract(i+7, i, vec)
    s.add(Or(b == 0x30, b == 0x31, b == 0x32))

def setLastBit(v):
    return Concat(Extract(63, 1, v), BitVecVal(1, 1))

def clearLastBit(v):
    return Concat(Extract(63, 1, v), BitVecVal(0, 1));

def if30(inp, ecx):
    inp = RotateLeft(inp, ecx)
    inp = clearLastBit(inp)
    inp = RotateRight(inp, ecx)
    ecx = ecx - 1
    return inp, ecx

def if31(inp, ecx):
    ecx = ecx + 1
    inp = RotateLeft(inp, ecx)
    inp = clearLastBit(inp)
    inp = RotateRight(inp, ecx)
    ecx = ecx + 1
    return inp, ecx

def if32(inp, ecx):
    ecx = ecx + 1
    inp = RotateLeft(inp, ecx)
    inp = setLastBit(inp)
    inp = RotateRight(inp, ecx)
    ecx = ecx + 1
    return inp, ecx

v1  = BitVecVal(0xDEADFACEDEADBEEF, 64)
ecx = BitVecVal(0x40, 64)

for i in range(0, size*8, 8):
    val   = Extract(i + 7, i, vec)
    val30 = if30(v1, ecx)
    val31 = if31(v1, ecx)
    val32 = if32(v1, ecx)
    v1    = If(val == 0x30, val30[0], If(val == 0x31, val31[0], val32[0]))
    ecx   = If(val == 0x30, val30[1], If(val == 0x31, val31[1], val32[1]))

s.add(v1 == 0x123456701234567)

print (s.sexpr())
print (s.check())

当我运行不幸的是，z3 打印了内部生成的程序（您可以检查它以了解引擎盖下的工作原理），但它不会很快回来说sat 或 unsat。这可能有多种原因：

您编码的算法可能不太正确。我建议在编写程序时研究它，并确保它捕获了您的意图。查看您是否可以按照生成的程序进行操作（您可以在关键位置添加 print (s.sexpr()) 以查看每一步生成的代码。
如果编码不正确，那么希望您能以这种方式修复它并让 z3 找到您的 vec 值。如果它是正确的，但 z3 没有在合理的时间内回答您的查询，那么这只是意味着这个问题对 z3 来说太难处理了。我建议保持 vec 简短：不要使用当前的 64 字节大小，而是从更小的大小开始，看看 z3 是否可以处理它。（先说几个字节。）如果你对算法的理解是正确的，那也可以进行进一步的调试。

祝你好运！

python 中 Z3 的按位运算

bitwise operations with Z3 in python

python

bit-manipulation

z3

z3 编码风格