如何通过LLVM和Z3实现程序验证器

Question

我需要用LLVM和Z3，实现一个程序验证器原型，例如对于以下程序

int main() {
  int n, k, j;
  n = input();
  assume(n > 0);
  k = input();
  assume(k > n);
  j = 0;
  while (j < n) {
    j++;
    k--;
  }
  assert(k >= 0);
  return 0;
}

其通过llvm生成的ll文件主要内容如下

define dso_local i32 @main() #0 {
entry:
  %call = call i32 (...) @input()
  %cmp = icmp sgt i32 %call, 0
  %conv = zext i1 %cmp to i32
  call void @assume(i32 %conv)
  %call1 = call i32 (...) @input()
  %cmp2 = icmp sgt i32 %call1, %call
  %conv3 = zext i1 %cmp2 to i32
  call void @assume(i32 %conv3)
  br label %while.cond

while.cond:                                       ; preds = %while.body, %entry
  %k.0 = phi i32 [ %call1, %entry ], [ %dec, %while.body ]
  %j.0 = phi i32 [ 0, %entry ], [ %inc, %while.body ]
  %cmp4 = icmp slt i32 %j.0, %call
  br i1 %cmp4, label %while.body, label %while.end

while.body:                                       ; preds = %while.cond
  %inc = add nsw i32 %j.0, 1
  %dec = add nsw i32 %k.0, -1
  br label %while.cond

while.end:                                        ; preds = %while.cond
  %cmp6 = icmp sge i32 %k.0, 0
  br i1 %cmp6, label %if.then, label %if.else

if.then:                                          ; preds = %while.end
  br label %if.end

if.else:                                          ; preds = %while.end
  call void @__assert_fail(i8* getelementptr inbounds ([7 x i8], [7 x i8]* @.str, i64 0, i64 0), i8* getelementptr inbounds ([10 x i8], [10 x i8]* @.str.1, i64 0, i64 0), i32 14, i8* getelementptr inbounds ([11 x i8], [11 x i8]* @__PRETTY_FUNCTION__.main, i64 0, i64 0)) #3
  unreachable

if.end:                                           ; preds = %if.then
  ret i32 0
}

我需要通过Z3验证__assert_fail不可达

目前已经有基本框架

using namespace llvm;

using InstMapTy = std::map<Value *, unsigned int>;
using DefMapTy = std::map<Value *, std::set<Value *>>;

class Extractor {
public:
  Extractor() : AllVariableVector(C), Queries(C) {
    Solver = new z3::fixedpoint(C);
    Params = new z3::params(C);
    Params->set("engine", "spacer");
    Solver->set(*Params);
  }

  ~Extractor() {
    delete Solver;
    delete Params;
  }

  z3::fixedpoint *getSolver() { return Solver; }
  z3::context &getContext() { return C; }
  z3::func_decl_vector &getQueries() { return Queries; }

  void initialize(Function &F);
  void extractConstraints(Instruction *I, z3::expr_vector &Assertions);
  void extractConstraints(BasicBlock *BB);
  void addQuery(z3::func_decl &Q) { Queries.push_back(Q); }
  z3::expr_vector transition(BasicBlock *BB, BasicBlock *Succ);

private:
  z3::context C;
  z3::fixedpoint *Solver;
  z3::params *Params;
  z3::check_result Result;
  z3::func_decl_vector Queries;
  std::map<BasicBlock *, std::set<Value *>> FreeVariables;
  std::map<BasicBlock *, z3::func_decl> BBRelations;
  std::map<BasicBlock *, z3::expr_vector> FreeVariableVector;
  z3::expr_vector AllVariableVector;
};

在对直接跳转分支进行处理时

if (BranchInst *BI = dyn_cast<BranchInst>(&BB->back())) {
  if (BI->isUnconditional()) {
    BasicBlock *Succ = BI->getSuccessor(0);
    z3::func_decl &SuccRel = BBRelations.at(Succ);
    z3::expr_vector Propagation = transition(BB, Succ);
    z3::expr SuccTuple = SuccRel(Propagation);

    z3::expr R0
             = z3::forall(allVariableVector, z3::implies(BBTuple && And, SuccTuple));
    
    Solver->add_rule(R0, C.str_symbol(“”));
  }
}

目前问题在于，我不知道 z3::func_decl &SuccRel、 transition(BB, Succ)的作用是什么，z3::forall(allVariableVector, z3::implies(BBTuple && And, SuccTuple))不知道怎么写，不知道BBTuple和SuccTuple的内容。请结合代码示例给我几个z3::forall(allVariableVector, z3::implies(BBTuple && And, SuccTuple))的具体内容，同时对SuccRel、transition做出一定的解释

Answer 1

z3::func_decl代表一个关系函数,SuccRel就是后继基本块的关系函数，BBTuple和SuccTuple分别代表当前基本块和后继基本块的表达式,内容可以是基本块中的变量等
参考 http://rightingcode.org/tutorials/popl20/index.html

Answer 2

参考一下

z3::expr x = C.int_const("x");
z3::expr y = C.int_const("y");
z3::expr_vector allVariableVector(C);
allVariableVector.push_back(x);
allVariableVector.push_back(y);
 
z3::expr BBTuple = (x > 0) && (y < 10);
z3::expr And = (x + y) > 5;
z3::expr SuccTuple = x > y;
 
z3::expr R0 = z3::forall(allVariableVector, z3::implies(BBTuple && And, SuccTuple));

Answer 3

通过LLVM和Z3实现程序验证器
CLion开发，编译，配置LLVM，SVF，Z3
可以参考下

CLion开发，编译，配置LLVM，SVF，Z3_Canliture的博客-CSDN博客 LLVM，Z3都安装好后，我的SVF版本是2.6，打开CLion就可以直接跑了。如果SVF找不到Z3，可以设置一下CMake变量，例如。解压后再创建一个目录叫做z3-build。构建类型：RelWithDebInfo。 https://blog.csdn.net/qq_37206105/article/details/131593765

https://blog.csdn.net/zhangqianqian57/article/details/105216164

Answer 4

z3::func_decl：这是Z3中的一个类，用于表示函数声明。SuccRel 可能是自己定义的一个函数名称，需要先在Z3中注册这个函数，才能使用它的名称。
transition(BB, Succ)：这是一个函数调用，其中BB和Succ是参数。BB可能代表一个基本块（basic block），而Succ可能是表示这个基本块的的一个或多个后继基本块。
z3::forall(allVariableVector, z3::implies(BBTuple && And, SuccTuple))：这是一个逻辑公式，使用了Z3中的forall（forall）和implies（蕴含）操作符。

Answer 5

z3::func_decl，表示函数声明，说明是z3中的一个类

Answer 6

transition(BB, Succ)表示调用从当前基本块到后继基本块的转移关系的函数

Answer 7

采用chatgpt：
在使用LLVM和Z3实现程序验证器时，z3::func_decl和transition函数是用于定义程序的状态转换关系和生成约束的关键部分。

z3::func_decl表示一个函数声明，用于定义程序中的关系。在这种情况下，BBRelations是一个BasicBlock到z3::func_decl的映射，用于存储每个基本块的关系。SuccRel是指向后继基本块的函数声明，表示状态转换关系。

transition函数用于生成基本块之间的状态转换约束。它接受当前基本块BB和后继基本块Succ作为输入，并返回一个z3::expr_vector，其中包含从当前基本块到后继基本块的状态转换约束。这些约束用于定义从一个基本块到另一个基本块的状态转换条件。

下面是一个示例，演示如何使用z3::forall来构建约束：

z3::expr_vector transition(BasicBlock *BB, BasicBlock *Succ) {
  // 创建一个空的约束向量
  z3::expr_vector Constraints(C);

  // 获取当前基本块的关系
  z3::func_decl &BBRel = BBRelations.at(BB);

  // 构建约束，比如对于当前基本块的某个指令I
  // I 的操作数之间的关系可以通过以下方式表示：
  // Constraints.push_back(z3::implies(BBRel(arg1, arg2, ...), z3::and_(...)));

  // 返回约束向量
  return Constraints;
}

在使用z3::forall时，你需要定义关系的输入参数，并使用z3::implies将关系的前提条件与结论进行连接。在这个示例中，BBTuple表示当前基本块的关系元组，And是其他与当前基本块关系相关的约束。SuccTuple是后继基本块的关系元组。

要创建一个z3::func_decl，你需要定义函数声明的名称、参数类型和返回类型。在程序验证器的上下文中，它表示基本块之间的状态转换关系。这些关系可以通过约束来定义，这些约束描述了基本块之间状态的限制条件。

请注意，上述代码片段只是一个示例，并不完整。你需要根据你的具体需求来定义约束和关系，并在程序验证器的其他部分中使用它们。

希望这能够帮助你理解z3::forall、z3::func_decl和transition函数的作用。

Answer 8

引用GPT : 在给出z3::forall(allVariableVector, z3::implies(BBTuple && And, SuccTuple))的具体内容之前，让我先解释一下SuccRel和transition(BB, Succ)的作用。

1. SuccRel：SuccRel是一个用于表示控制流从当前基本块（BB）到其后继基本块（Succ）的关系的函数声明（func_decl）。通过建立这样的关系，我们可以在Z3求解器中表示当前基本块与后继基本块之间的约束条件。

2. transition(BB, Succ)：transition函数用于根据两个基本块之间的跳转关系创建一个过渡关系。它接受当前基本块（BB）和后继基本块（Succ）作为输入，并返回一个Z3表达式向量，表示控制流从BB到Succ的状态转移。

现在，让我们详细看一下z3::forall(allVariableVector, z3::implies(BBTuple && And, SuccTuple))的内容。这部分代码使用了Z3的forall量化子来定义一个规则，该规则将成为约束的一部分。具体内容如下：

1. allVariableVector是一个包含所有变量的Z3表达式向量。这个向量中应该包含程序中的所有自由变量和约束中涉及的其他变量。

2. BBTuple是一个表示当前基本块（BB）的状态的Z3元组（tuple）。它包含了BB基本块中所有涉及的变量的值。

3. And是一个Z3逻辑AND操作符，用于将多个条件连接起来。您在这里应该添加关于当前基本块状态（BBTuple）的任何其他约束条件。

4. SuccTuple是一个表示后继基本块（Succ）的状态的Z3元组。您可以使用transition(BB, Succ)函数获得该状态转移的条件约束。

因此，z3::forall(allVariableVector, z3::implies(BBTuple && And, SuccTuple))将创建一个对所有变量进行量化的约束规则，该规则表明如果当前基本块的状态（BBTuple）和其他约束条件（And）满足时，那么这些条件会隐含地导致后继基本块的状态（SuccTuple）成立。

Answer 9

该回答引用GPT:在给出具体的 z3::forall 内容之前，先解释一下 SuccRel 和 transition 的作用。

1. SuccRel：SuccRel 是一个函数声明，表示了当前基本块 BB 和其后继基本块 Succ 之间的关系。在这个框架中，基本块之间的关系可以用一个函数来表示。BBRelations 是一个存储基本块关系的映射表，通过 BBRelations.at(Succ) 可以获取 Succ 的关系函数。

2. transition：transition 函数用于生成从当前基本块 BB 到后继基本块 Succ 的转移约束。转移约束描述了程序在从 BB 跳转到 Succ 时，变量之间的关系或约束条件。它返回一个 z3::expr_vector，包含了这些转移约束。

接下来，给出一个示例来说明 z3::forall(allVariableVector, z3::implies(BBTuple && And, SuccTuple)) 的具体内容。假设我们有两个基本块 BB1 和 BB2，其中 BB1 是当前基本块，BB2 是 BB1 的后继基本块。我们希望描述从 BB1 跳转到 BB2 的转移约束。

z3::expr_vector transition = generateTransition(BB1, BB2);
z3::expr BBTuple = BBRelations.at(BB1)(FreeVariableVector.at(BB1));
z3::expr SuccTuple = BBRelations.at(BB2)(FreeVariableVector.at(BB2));

z3::expr transitionFormula = z3::forall(allVariableVector, z3::implies(BBTuple && transition, SuccTuple));
Solver->add_rule(transitionFormula, C.str_symbol(""));

在上述示例中，generateTransition(BB1, BB2) 是一个生成转移约束的函数，它返回一个 z3::expr_vector，表示从 BB1 跳转到 BB2 的转移约束。FreeVariableVector.at(BB1) 和 FreeVariableVector.at(BB2) 分别表示基本块 BB1 和 BB2 中的自由变量，它们是在 Extractor 类中提前收集的。

BBTuple 和 SuccTuple 分别表示 BB1 和 BB2 的关系函数应用到自由变量上的结果。transitionFormula 利用 z3::forall 来量化所有变量，并使用 z3::implies 表示转移约束的条件。最后，使用 Solver->add_rule 将转移约束添加到求解器中。

请注意，上述示例是一种可能的实现方式，具体的内容和约束条件需要根据实际情况进行调整。

Answer 10

根据代码示例以及你提供的信息，我可以给出一些关于z3::forall(allVariableVector, z3::implies(BBTuple && And, SuccTuple))的具体内容以及对SuccRel和transition的解释。

首先，z3::func_decl &SuccRel是一个函数声明对象，它表示了一个关系符号，该关系符号将在后续的Z3规则中使用。在这里，SuccRel代表了从当前基本块到后继基本块的关系。

其次，transition(BB, Succ)是一个函数，用于生成从当前基本块到后继基本块的转换约束。它返回一个表达式向量 (expr_vector)，其中包含了用于描述转换条件的Z3表达式。

关于z3::forall(allVariableVector, z3::implies(BBTuple && And, SuccTuple))，你需要理解以下几个部分的含义：

allVariableVector：这是一个 Z3 表达式向量，包含了所有程序中的变量。
BBTuple：这是一个表示当前基本块状态的 Z3 元组，包含了当前基本块中所有自由变量的约束。
And：这是一个表示其他约束条件的 Z3 表达式，它可以与当前基本块状态一起影响转换。
SuccTuple：这是一个表示后继基本块状态的 Z3 元组，包含了后继基本块中所有自由变量的约束。
你需要根据具体情况来构建这些表达式。根据你给出的代码片段，你可以使用如下示例作为z3::forall(allVariableVector, z3::implies(BBTuple && And, SuccTuple))的具体内容：

cpp
z3::expr_vector BBTuple(C); // 创建一个空的 Z3 元组 BBTuple
BBTuple.push_back(Var1 == Value1); // 添加元素表示变量 Var1 等于 Value1
BBTuple.push_back(Var2 < Value2); // 添加元素表示变量 Var2 小于 Value2
// ...

z3::expr And = (Var3 == Var4 && Var5 > Value3); // 创建一个与语句，包含多个条件

z3::expr_vector SuccTuple(C); // 创建一个空的 Z3 元组 SuccTuple
SuccTuple.push_back(Var6 >= Value4); // 添加元素表示变量 Var6 大于等于 Value4
SuccTuple.push_back(Var7 != Value5); // 添加元素表示变量 Var7 不等于 Value5
// ...

z3::expr forallExpr = z3::forall(allVariableVector, z3::implies(BBTuple && And, SuccTuple));

请注意，上述只是示例，并且具体的表达式内容需要根据你的程序和约束条件进行修改。

Answer 11

首先，让我们逐个解释一下您提到的几个问题点。

1. z3::func_decl &SuccRel：这是一个表示后继基本块关系的函数声明。在该示例中，BBRelations 是一个映射，将每个基本块映射到一个关系函数。SuccRel 是用来表示当前基本块到后继基本块的关系的函数声明。它在代码中用于构建转移关系表达式。

2. transition(BB, Succ)：这是一个用于生成从当前基本块到后继基本块的转移关系的函数。它返回一个包含转移关系的 Z3 表达式向量。在示例中，transition 函数根据输入的当前基本块 BB 和后继基本块 Succ，生成了转移关系。

3. z3::forall(allVariableVector, z3::implies(BBTuple && And, SuccTuple))：这是一个量化公式，用于表示对所有变量的量化约束。在这里，allVariableVector 是一个 Z3 表达式向量，包含了所有变量。BBTuple 和 SuccTuple 分别是转移关系的表达式，它们描述了当前基本块和后继基本块之间的关系。z3::implies 函数表示蕴含关系，即如果 BBTuple 和 And 都成立，则 SuccTuple 也必须成立。

在给出具体内容之前，需要知道您的具体需求和定义的变量。以下是一个示例，假设存在变量 x 和 y：

z3::expr x = C.int_const("x");
z3::expr y = C.int_const("y");
z3::expr_vector allVariableVector(C);
allVariableVector.push_back(x);
allVariableVector.push_back(y);

z3::expr BBTuple = (x > 0) && (y < 10);
z3::expr And = (x + y) > 5;
z3::expr SuccTuple = x > y;

z3::expr R0 = z3::forall(allVariableVector, z3::implies(BBTuple && And, SuccTuple));

在上述示例中，x 和 y 是整数类型的变量。BBTuple 表示当前基本块的关系条件，例如 x > 0 且 y < 10。And 表示另一个关系条件，例如 (x + y) > 5。SuccTuple 表示后继基本块的关系条件，例如 x > y。最后，通过 z3::forall 和 z3::implies 构建了量化公式 R0。

请根据您的具体需求和定义的变量，将示例中的条件和变量进行调整和扩展。

Answer 12

该代码通过使用Z3求解器来验证是否存在不可达的__assert_fail语句，Extractor类初始化了Z3求解器，并定义了一些成员变量用于存储和组织约束信息，在处理直接跳转分支时，根据继续基本块获取关系函数SuccRel和过渡条件Propagation，通过构建一个量化表达式，利用SuccRel和Propagation定义了一个规则R0，并将其添加到求解器中，需要进一步补充z3::forall部分的具体内容，包括BBTuple和SuccTuple的构建方式及约束关系的定义