5.8.1 Z3

Z3 是一个由微软开发的可满足性摸理论（Satisfiability Modulo Theories，SMT）的约束求解器。所谓约束求解器就是用户使用某种特定的语言描述对象（变量）的约束条件，求解器将试图求解出能够满足所有约束条件的每个变量的值。Z3 可以用来检查满足一个或多个理论的公式的可满足性，也就是说,它可以自动化地通过内置理论对一阶逻辑多种排列进行可满足性校验。目前其支持的理论有：

  • equality over free 函数和谓词符号
  • 实数和整形运算(有限支持非线性运算)
  • 位向量
  • 阵列
  • 元组/记录/枚举类型和代数（递归）数据类型
  • …

因其强大的功能，Z3 已经被用于许多领域中，在安全领域，主要见于符号执行、Fuzzing、二进制逆向、密码学等。另外 Z3 提供了多种语言的接口，这里我们使用 Python。

安装

在 Linux 环境下，执行下面的命令：

  1. $ git clone https://github.com/Z3Prover/z3.git
  2. $ cd z3
  3. $ python scripts/mk_make.py --python
  4. $ cd build
  5. $ make
  6. $ sudo make install

另外还可以使用 pip 来安装 Python 接口（py2和py3均可），这是二进制分析框架 angr 里内置的修改版：

  1. $ sudo pip install z3-solver

Z3 理论基础

Op Mnmonics Description
0 true 恒真
1 flase 恒假
2 = 相等
3 distinct 不同
4 ite if-then-else
5 and n元 合取
6 or n元 析取
7 iff implication
8 xor 异或
9 not 否定
10 implies Bi-implications

使用 Z3

先来看一个简单的例子：

  1. >>> from z3 import *
  2. >>> x = Int('x')
  3. >>> y = Int('y')
  4. >>> solve(x > 2, y < 10, x + 2*y == 7)
  5. [y = 0, x = 7]

首先定义了两个常量 x 和 y，类型是 Z3 内置的整数类型 Int，solve() 函数会创造一个 solver，然后对括号中的约束条件进行求解，注意在 Z3 默认情况下只会找到满足条件的一组解。

  1. >>> simplify(x + y + 2*x + 3)
  2. 3 + 3*x + y
  3. >>> simplify(x < y + x + 2)
  4. Not(y <= -2)
  5. >>> simplify(And(x + 1 >= 3, x**2 + x**2 + y**2 + 2 >= 5))
  6. And(x >= 2, 2*x**2 + y**2 >= 3)
  7. >>>
  8. >>> simplify((x + 1)*(y + 1))
  9. (1 + x)*(1 + y)
  10. >>> simplify((x + 1)*(y + 1), som=True)     # sum-of-monomials：单项式的和
  11. 1 + x + y + x*y
  12. >>> t = simplify((x + y)**3, som=True)
  13. >>> t
  14. x*x*x + 3*x*x*y + 3*x*y*y + y*y*y
  15. >>> simplify(t, mul_to_power=True)          # mul_to_power 将乘法转换成乘方
  16. x**3 + 2*y*x**2 + x**2*y + 3*x*y**2 + y**3

simplify() 函数用于对表达式进行化简，同时可以设置一些选项来满足不同的要求。更多选项使用 help_simplify() 获得。

同时，Z3 提供了一些函数可以解析表达式：

  1. >>> n = x + y >= 3
  2. >>> "num args: ", n.num_args()
  3. ('num args: ', 2)
  4. >>> "children: ", n.children()
  5. ('children: ', [x + y, 3])
  6. >>> "1st child:", n.arg(0)
  7. ('1st child:', x + y)
  8. >>> "2nd child:", n.arg(1)
  9. ('2nd child:', 3)
  10. >>> "operator: ", n.decl()
  11. ('operator: ', >=)
  12. >>> "op name:  ", n.decl().name()
  13. ('op name:  ', '>=')

set_param() 函数用于对 Z3 的全局变量进行配置，如运算精度，输出格式等等：

  1. >>> x = Real('x')
  2. >>> y = Real('y')
  3. >>> solve(x**2 + y**2 == 3, x**3 == 2)
  4. [x = 1.2599210498?, y = -1.1885280594?]
  5. >>>
  6. >>> set_param(precision=30)
  7. >>> solve(x**2 + y**2 == 3, x**3 == 2)
  8. [x = 1.259921049894873164767210607278?,
  9.  y = -1.188528059421316533710369365015?]

逻辑运算有 And、Or、Not、Implies、If，另外 == 表示 Bi-implications。

  1. >>> p = Bool('p')
  2. >>> q = Bool('q')
  3. >>> r = Bool('r')
  4. >>> solve(Implies(p, q), r == Not(q), Or(Not(p), r))
  5. [q = False, p = False, r = True]
  6. >>>
  7. >>> x = Real('x')
  8. >>> solve(Or(x < 5, x > 10), Or(p, x**2 == 2), Not(p))
  9. [x = -1.4142135623?, p = False]

Z3 提供了多种 Solver，即 Solver 类，其中实现了很多 SMT 2.0 的命令，如 push, pop, check 等等。

  1. >>> x = Int('x')
  2. >>> y = Int('y')
  3. >>> s = Solver()    # 创造一个通用 solver
  4. >>> type(s)         # Solver 类
  5. <class 'z3.z3.Solver'>
  6. >>> s
  7. []
  8. >>> s.add(x > 10, y == x + 2)   # 添加约束到 solver 中
  9. >>> s
  10. [x > 10, y == x + 2]
  11. >>> s.check()       # 检查 solver 中的约束是否满足
  12. sat                 # satisfiable/满足
  13. >>> s.push()        # 创建一个回溯点，即将当前栈的大小保存下来
  14. >>> s.add(y < 11)
  15. >>> s
  16. [x > 10, y == x + 2, y < 11]
  17. >>> s.check()
  18. unsat               # unsatisfiable/不满足
  19. >>> s.pop(num=1)    # 回溯 num 个点
  20. >>> s
  21. [x > 10, y == x + 2]
  22. >>> s.check()
  23. sat
  24. >>> for c in s.assertions():    # assertions() 返回一个包含所有约束的AstVector
  25. ...     print(c)
  26. ...
  27. x > 10
  28. y == x + 2
  29. >>> s.statistics()  # statistics() 返回最后一个 check() 的统计信息
  30. (:max-memory   6.26
  31.  :memory       4.37
  32.  :mk-bool-var  1
  33.  :num-allocs   331960806
  34.  :rlimit-count 7016)
  35. >>> m = s.model()   # model() 返回最后一个 check() 的 model
  36. >>> type(m)         # ModelRef 类
  37. <class 'z3.z3.ModelRef'>
  38. >>> m
  39. [x = 11, y = 13]
  40. >>> for d in m.decls():         # decls() 返回 model 包含了所有符号的列表
  41. ...     print("%s = %s" % (d.name(), m[d]))
  42. ...
  43. x = 11
  44. y = 13

为了将 Z3 中的数和 Python 区分开，应该使用 IntVal()、RealVal() 和 RatVal() 分别返回 Z3 整数、实数和有理数值。

  1. >>> 1/3
  2. 0.3333333333333333
  3. >>> RealVal(1)/3
  4. 1/3
  5. >>> Q(1, 3)      # Q(a, b) 返回有理数 a/b
  6. 1/3
  7. >>>
  8. >>> x = Real('x')
  9. >>> x + 1/3
  10. x + 3333333333333333/10000000000000000
  11. >>> x + Q(1, 3)
  12. x + 1/3
  13. >>> x + "1/3"
  14. x + 1/3
  15. >>> x + 0.25
  16. x + 1/4
  17. >>> solve(3*x == 1)
  18. [x = 1/3]
  19. >>> set_param(rational_to_decimal=True) # 以十进制形式表示有理数
  20. >>> solve(3*x == 1)
  21. [x = 0.3333333333?]

在混合使用实数和整数变量时，Z3Py 会自动添加强制类型转换将整数表达式转换成实数表达式。

  1. >>> x = Real('x')
  2. >>> y = Int('y')
  3. >>> a, b, c = Reals('a b c')        # 返回一个实数常量元组
  4. >>> s, r = Ints('s r')              # 返回一个整数常量元组
  5. >>> x + y + 1 + a + s
  6. x + ToReal(y) + 1 + a + ToReal(s)   # ToReal() 将整数表达式转换成实数表达式
  7. >>> ToReal(y) + c
  8. ToReal(y) + c

现代的CPU使用固定大小的位向量进行算术运算，在 Z3 中，使用函数 BitVec() 创建位向量常量，BitVecVal() 返回给定位数的位向量值。

  1. >>> x = BitVec('x', 16)     # 16 位，命名为 x
  2. >>> y = BitVec('x', 16)
  3. >>> x + 2
  4. x + 2
  5. >>> (x + 2).sexpr()         # .sexpr() 返回内部表现形式
  6. '(bvadd x #x0002)'
  7. >>> simplify(x + y - 1)     # 16 位整数的 -1 等于 65535
  8. 65535 + 2*x
  9. >>> a = BitVecVal(-1, 16)   # 16 位，值为 -1
  10. >>> a
  11. 65535
  12. >>> b = BitVecVal(65535, 16)
  13. >>> b
  14. 65535
  15. >>> simplify(a == b)
  16. True

Z3 在 CTF 中的运用

re PicoCTF2013 Harder_Serial

题目如下，是一段 Python 代码，要求输入一段 20 个数字构成的序列号，然后程序会对序列号的每一位进行验证，以满足各种要求。题目难度不大，但完全手工验证是一件麻烦的事，而使用 Z3 的话，只要定义好这些条件，就可以得出满足条件的值。

  1. import sys
  2. print ("Please enter a valid serial number from your RoboCorpIntergalactic purchase")
  3. if len(sys.argv) < 2:
  4.   print ("Usage: %s [serial number]"%sys.argv[0])
  5.   exit()
  7. print ("#>" + sys.argv[1] + "<#")
  9. def check_serial(serial):
  10.   if (not set(serial).issubset(set(map(str,range(10))))):
  11.     print ("only numbers allowed")
  12.     return False
  13.   if len(serial) != 20:
  14.     return False
  15.   if int(serial[15]) + int(serial[4]) != 10:
  16.     return False
  17.   if int(serial[1]) * int(serial[18]) != 2:
  18.     return False
  19.   if int(serial[15]) / int(serial[9]) != 1:
  20.     return False
  21.   if int(serial[17]) - int(serial[0]) != 4:
  22.     return False
  23.   if int(serial[5]) - int(serial[17]) != -1:
  24.     return False
  25.   if int(serial[15]) - int(serial[1]) != 5:
  26.     return False
  27.   if int(serial[1]) * int(serial[10]) != 18:
  28.     return False
  29.   if int(serial[8]) + int(serial[13]) != 14:
  30.     return False
  31.   if int(serial[18]) * int(serial[8]) != 5:
  32.     return False
  33.   if int(serial[4]) * int(serial[11]) != 0:
  34.     return False
  35.   if int(serial[8]) + int(serial[9]) != 12:
  36.     return False
  37.   if int(serial[12]) - int(serial[19]) != 1:
  38.     return False
  39.   if int(serial[9]) % int(serial[17]) != 7:
  40.     return False
  41.   if int(serial[14]) * int(serial[16]) != 40:
  42.     return False
  43.   if int(serial[7]) - int(serial[4]) != 1:
  44.     return False
  45.   if int(serial[6]) + int(serial[0]) != 6:
  46.     return False
  47.   if int(serial[2]) - int(serial[16]) != 0:
  48.     return False
  49.   if int(serial[4]) - int(serial[6]) != 1:
  50.     return False
  51.   if int(serial[0]) % int(serial[5]) != 4:
  52.     return False
  53.   if int(serial[5]) * int(serial[11]) != 0:
  54.     return False
  55.   if int(serial[10]) % int(serial[15]) != 2:
  56.     return False
  57.   if int(serial[11]) / int(serial[3]) != 0:
  58.     return False
  59.   if int(serial[14]) - int(serial[13]) != -4:
  60.     return False
  61.   if int(serial[18]) + int(serial[19]) != 3:
  62.     return False
  63.   return True
  65. if check_serial(sys.argv[1]):
  66.   print ("Thank you! Your product has been verified!")
  67. else:
  68.   print ("I'm sorry that is incorrect. Please use a valid RoboCorpIntergalactic serial number")

首先创建一个求解器实例，然后将序列的每个数字定义为常量：

  1. serial = [Int("serial[%d]" % i) for i in range(20)]

接着定义约束条件，注意，除了题目代码里的条件外，还有一些隐藏的条件，比如这一句：

  1. solver.add(serial[11] / serial[3]  == 0)

因为被除数不能为 0，所以 serial[3] 不能为 0。另外，每个序列号数字都是大于等于 0，小于 9 的。最后求解得到结果。

完整的 exp 如下，其他文件在 github 相应文件夹中。

  1. from z3 import *
  3. solver = Solver()
  5. serial = [Int("serial[%d]" % i) for i in range(20)]
  7. solver.add(serial[15] + serial[4]  == 10)
  8. solver.add(serial[1]  * serial[18] == 2 )
  9. solver.add(serial[15] / serial[9]  == 1)
  10. solver.add(serial[17] - serial[0]  == 4)
  11. solver.add(serial[5]  - serial[17] == -1)
  12. solver.add(serial[15] - serial[1]  == 5)
  13. solver.add(serial[1]  * serial[10] == 18)
  14. solver.add(serial[8]  + serial[13] == 14)
  15. solver.add(serial[18] * serial[8]  == 5)
  16. solver.add(serial[4]  * serial[11] == 0)
  17. solver.add(serial[8]  + serial[9]  == 12)
  18. solver.add(serial[12] - serial[19] == 1)
  19. solver.add(serial[9]  % serial[17] == 7)
  20. solver.add(serial[14] * serial[16] == 40)
  21. solver.add(serial[7]  - serial[4]  == 1)
  22. solver.add(serial[6]  + serial[0]  == 6)
  23. solver.add(serial[2]  - serial[16] == 0)
  24. solver.add(serial[4]  - serial[6]  == 1)
  25. solver.add(serial[0]  % serial[5]  == 4)
  26. solver.add(serial[5]  * serial[11] == 0)
  27. solver.add(serial[10] % serial[15] == 2)
  28. solver.add(serial[11] / serial[3]  == 0)    # serial[3] can't be 0
  29. solver.add(serial[14] - serial[13] == -4)
  30. solver.add(serial[18] + serial[19] == 3)
  32. for i in range(20):
  33.     solver.add(serial[i] >= 0, serial[i] < 10)
  35. solver.add(serial[3] != 0)
  37. if solver.check() == sat:
  38.     m = solver.model()
  39.     for d in m.decls():
  40.         print("%s = %s" % (d.name(), m[d]))
  42.     print("".join([str(m.eval(serial[i])) for i in range(20)]))

Bingo!!!

  1. $ python exp.py
  2. serial[2] = 8
  3. serial[11] = 0
  4. serial[3] = 9
  5. serial[4] = 3
  6. serial[1] = 2
  7. serial[0] = 4
  8. serial[19] = 2
  9. serial[14] = 5
  10. serial[17] = 8
  11. serial[16] = 8
  12. serial[10] = 9
  13. serial[8] = 5
  14. serial[6] = 2
  15. serial[9] = 7
  16. serial[5] = 7
  17. serial[13] = 9
  18. serial[7] = 4
  19. serial[18] = 1
  20. serial[15] = 7
  21. serial[12] = 3
  22. 42893724579039578812
  23. $ python harder_serial.py 42893724579039578812
  24. Please enter a valid serial number from your RoboCorpIntergalactic purchase
  25. #>42893724579039578812<#
  26. Thank you! Your product has been verified!

这一题简直是为 Z3 量身定做的，方法也很简单，但 Z3 远比这个强大，后面我们还会讲到它更高级的应用。

参考资料