T3-3 · 符号执行

条件分支语句与控制流相关的符号执行

以下三个C函数都是取绝对值的潜在实现方法。这里我们仅仅举例说明验证它们的一个简单性质:如果调用它们时的参数不为INT_MIN,那么它们就能安全运行,并且其返回值非负。

以下三个C函数都是取绝对值的潜在实现方法。这里我们仅仅举例说明验证它们的一个简单性质:如果调用它们时的参数不为INT_MIN,那么它们就能安全运行,并且其返回值非负。

int abs0(int x)
/*@ Require INT_MIN < x && x <= INT_MAX
    Ensure __return >= 0 */
{
  if (x < 0) {
    return - x;
  }
  else {
    return x;
  }
}
int abs1(int x)
/*@ Require INT_MIN < x && x <= INT_MAX
    Ensure __return >= 0 */
{
  if (x < 0) {
    x = - x;
  }
  return x;
}
int abs2(int x)
/*@ Require INT_MIN < x && x <= INT_MAX
    Ensure __return >= 0 */
{
  if (x > 0) {
    return x;
  }
  return - x;
}

if语句的符号执行

以其中abs0函数的符号执行为例,它的符号执行是从“进入函数体”开始的,这一初始步骤生成的断言是:

INT_MIN < x_30 && x_30 <= INT_MAX && store_int(&x, x_30)

如果后续x的值发生变化,那么这个x_30可以被看作x@pre。如果x的值还未发生变化,那么这个x_30就既是x的初始值又是x的当前值。

接下去要符号执行的是if语句,该语句的判定条件是x < 0这一表达式。QCP的符号执行模块会发现,当x_30 < 0时,这个条件为真,当x_30 >= 0时,这个条件为假。因此,符号执行器会为该if语句的两个分支分别生成一个断言,if-true分支得到断言

x_30 < 0 && INT_MIN < x_30 && x_30 <= INT_MAX && store_int(&x, x_30)

if-false分支(即else分支)得到断言

x_30 >= 0 && INT_MIN < x_30 && x_30 <= INT_MAX && store_int(&x, x_30)

当在IDE中将光标指向if-true分支的开头时,按Ctrl+Right快捷键可以看到当前分支的符号执行结果:

image-3-3-1
image-3-3-1

return语句的符号执行

if-true分支中,abs函数会返回- x。这个C表达式- x的值就是- x_30。QCP的符号执行模块会分两步完成该return语句的符号执行。首先是符号计算出将要返回的数值:

x_30 < 0 && INT_MIN < x_30 && x_30 <= INT_MAX && __return == - x_30 && store_int(&x, x_30)

其次是释放局部变量(含形参)所占据的内存空间:

x_30 < 0 && INT_MIN < x_30 && x_30 <= INT_MAX && __return == - x_30

由于x_30表示的是形参x的初始值,这个return断言也可以写作以下形式:

x@pre < 0 && INT_MIN < x@pre && x@pre <= INT_MAX && __return == - x@pre

值得一提的是,IDE给出反馈时,右边栏将此断言列为Return断言,而非我们之前见到的Normal断言。它的意思是,即将在一个符合该断言的程序状态上退出该函数体的执行,而非要基于这个程序状态继续执行当前光标处之后的程序。

image-3-3-2
image-3-3-2

符号执行进入if-false分支的情形

当在IDE中,将光标指向if-false分支的开头时,按Ctrl+Right快捷键可以看到当前分支的符号执行结果:

image-3-3-3
image-3-3-3

此时IDE会同时显示当前分支的Normal断言以及先前分支的Return断言。如前面提到的那样,当前分支的Normal断言用基本分离逻辑断言和简明分离逻辑断言表述分别是:

x_30 >= 0 && INT_MIN < x_30 && x_30 <= INT_MAX && store_int(&x, x_30)
x@pre >= 0 && INT_MIN < x@pre && x@pre <= INT_MAX && x == x@pre

在此基础上符号执行return x语句会得到

x@pre >= 0 && INT_MIN < x@pre && x@pre <= INT_MAX && _return == x@pre

这也是Return断言,IDE此时会把两条Return断言收集在一起显示。

image-3-3-4
image-3-3-4

if语句结束后的情形

abs0函数的if语句两分支都是return语句,因此程序本就不会执行到if语句之后的部分(当然,这条if语句之后也没有别的语句了),相应的,如果查看if语句结束后的符号执行结果,其仅包含两条Return断言,而没有Normal断言。

image-3-3-5
image-3-3-5

退出函数体时要检查的条件

在推出函数体时,QCP会检查是否所有的Return断言都能推出Ensure条件。就abs0而言,就需要证明以下两条性质:

x_30 < 0 && INT_MIN < x_30 && x_30 <= INT_MAX && __return == - x_30 |-- __return >= 0
x_30 >= 0 && INT_MIN < x_30 && x_30 <= INT_MAX && __return == x_30 |-- __return >= 0

QCP会确认,这两条数学推导确实成立。至此,QCP就完成了abs0函数的验证。

abs1函数的符号执行

abs1函数与abs0函数稍有不同。它的if语句只有一个分支,并且其中只有普通赋值语句而没有return语句。

int abs1(int x)
/*@ Require INT_MIN < x && x <= INT_MAX
    Ensure __return >= 0 */
{
  if (x < 0) {
    x = - x;
  }
  return x;
}

当QCP符号执行到if-true分支结束时,符号执行的结果是一个Normal断言,而不是之前abs0中的Return断言。其使用基本分离逻辑断言和简明分离逻辑断言分别可以如下表述(其中x_30和前面一样对应x@pre):

x_30 < 0 && INT_MIN < x_30 && x_30 <= INT_MAX && store_int(&x, - x_30)
x@pre < 0 && INT_MIN < x@pre && x@pre <= INT_MAX && x == - x@pre

在工具中,可以看到如下反馈信息:

image-3-3-6
image-3-3-6

if语句结束之后,QCP的符号执行会收集将两个Normal断言收集起来(包括没有出现的if-false分支断言),用基本分离逻辑断言写出就是:

x_30 < 0 && INT_MIN < x_30 && x_30 <= INT_MAX && store_int(&x, - x_30)
x_30 >= 0 && INT_MIN < x_30 && x_30 <= INT_MAX && store_int(&x, x_30)

用简明分离逻辑断言写出就是:

x@pre < 0 && INT_MIN < x@pre && x@pre <= INT_MAX && x == - x@pre
x@pre >= 0 && INT_MIN < x@pre && x@pre <= INT_MAX && x == x@pre

当然,如果要在工具中让IDE显示这些符号执行的结果,那么会遇到一些小麻烦。原因是abs1if语句没有else分支,但是当光标停在if-true分支结束处时,工具并不知道后续是否还有else分支,因此QCP工具此时只会显示if-true分支的结束条件。

image-3-3-7
image-3-3-7

要让工具同时显示两个分支的符号执行结果(相当于整个if语句的符号执行结果)可以手动添加一个空的else分支。

image-3-3-8
image-3-3-8

当然,无论有没有把这个空的else分支写出来,QCP都会基于两个分支的汇总继续后续的推理。就abs1函数而言,QCP推导return x的符号执行结果时,会根据前面的两条Normal断言得到两条Return断言。

image-3-3-9
image-3-3-9

当然,这两条Return断言都能推出Ensure条件,至此QCP也完成了abs1的验证。

abs2函数的符号执行

abs2函数又与前两个函数不同。

int abs2(int x)
/*@ Require INT_MIN < x && x <= INT_MAX
    Ensure __return >= 0 */
{
  if (x > 0) {
    return x;
  }
  return - x;
}

它的if-true分支是一个return语句,其符号执行会产生一个Return断言。它没有if-false分支,相当于这个分支为空,会产生一个Normal断言。要在工具中查看整个if语句的符号执行结果,还是需要像前面一样手动添加一个空的else分支。

image-3-3-10
image-3-3-10

这两个断言中只有Normal断言会由于后续语句的符号执行。最终,在return - x之后的符号执行结果如下:

image-3-3-11
image-3-3-11