什么是程序验证?

[拼音]：chengxu yanzheng

[外文]：verificafion of programs

研究程序正确性的理论。为了解一个程序是否正确地实现了预定的目标，通常是规定一些初始数据，试验性地执行这个程序，测试其是否能产生所要的答案。如果发现有误，就检查和修改所编的程序，直至对所有规定的初始数据，都能产生预期的结果。这种方法称为程序调试。但是，程序对不同的初始数据的加工过程是不同的，而初始数据的取值范围往往又十分广泛。因此，使用调试方法穷尽程序的各种可能加工过程以确保程序的正确性，几乎是不可能实现的。因此，调试方法只能发现程序的错误，而不能确保程序无误。程序验证则是研究如何使用数学方法严格证明一个程序是符合其预定的目标的，因而是正确无误的。

美籍匈牙利科学家J.诺伊曼于1947年发表的论文中就提到程序正确性证明。美国科学家R.W.弗洛依德于1967年系统地提出验证程序正确性的归纳断言方法，引起了计算机科学界研究程序验证的热潮。英国科学家C.A.R.霍尔于1969年将归纳断言方法形式化，提出程序验证的公理系统。1969年以来又陆续出现很多使用归纳断言方法或者结构归纳法的自动程序验证系统，其中以70年代中期实现的波伊尔－莫尔程序验证系统最为著名。70年代以来还出现能辅助用户正确编制程序的实用的半自动化程序验证系统。在使用这种系统时，用户必须协助系统完成程序验证中创造性最强的部分工作。

下面的框图代表一个非负整数的除法程序。x1是被除数；x2是除数；z1中存放程序加工后得到的商；z2中存放得到的余数;y1、y2是程序加工时使用的工作单元。START 表示程序的起始，HALT表示程序的终止。方框中是同时赋值语句，如

(y1，y2):＝(O，x1)

表示将y1置0值的同时，将y2的值置为x1。圆框内是测试语句，用于控制程序加工的流程。如框图中的语句

y2≥x2

表示当y2的值大于等于x2时，程序按yes的箭头继续执行；否则按no的箭头继续执行。

为验证程序，必须首先将程序所要实现的目标形式化，即使用数学公式表达程序加工的初始数据的范围(称作输入谓词)和程序加工的结果（称作输出谓词）。

若约定各个变量的取值都是整数，上述除法程序的输入谓词和输出谓词分别为

在用归纳断言方法证明程序正确性时，还必须在程序的框图中设置一些数学公式，称作断言，表示程序执行到该处时，程序中变量应满足的数学关系。输入谓词可选作起点处的断言，而输出谓词可选作终止点处的断言。

在除法程序中设置三个断言，A处和C处的断言分别为上述输入和输出谓词，B处断言为

(x1＝y1x2+y2)&(y2≥0) (1)

反映了y1、y2中存放商数和余数的中间结果值。

验证程序的正确性，就是证明在程序的任何一种可能的加工过程中所设置的断言都是成立的。程序的一个加工过程就是框图中的一个流程。除法程序的所有可能的流程都是由图上的三条路径组合而成：由A至B;由B出发回到B;由B至C。这样，验证程序的正确性，就是证明对任一条路径，只要起点的断言成立，则终点的断言也成立。

以第二条路径为例，它是一条环路。要证明下列命题：若程序执行到环路的起点B时，断言(1)成立，则程序执行一周，再达到B点时，断言(1)仍然成立。

环行该圈，就是在(y2≥x2)成立的条件下，执行赋值语句

(y1，y2):＝(y1+1，y2-x2)

而上述语句的执行结果是使 y1的取值为执行前y1的值加1，y2的取值为执行前y2的值与x2的差，其他变量的值不变。为保证执行该赋值语句后断言(1)仍然成立，就要求将断言(1)中的y1代为(y1+1)，y2代为(y2-x2)后得到的公式在执行该语句前成立。即

(x1=(y1+1)x2+(y2-x2))&(y2-x2≥0) (2)

在执行上述赋值语句前成立。但已知执行该语句前断言①和测试条件(y2≥x2)均成立。由此推断公式②是成立的。这样就完成了对第二条路径的验证。对其余两条路径的验证也是类似的。从而可以证明除法程序的正确性。

归纳断言方法是由建立断言和对各条路径逐条验证两部分组成的。建立断言是一种创造性的工作，而验证路径的工作尽管繁琐，却是机械的。如何由计算机系统协助用户归纳出合适的断言，是程序验证研究中的重要课题。

用上述方法只能证明在输入谓词成立的前提下，程序终止时输出谓词一定成立。但不能证明在输入谓词成立时，程序一定能终止。不讨论程序终止性的程序验证称为程序部分正确性的验证。包括终止性的验证，则称为程序完全正确性的验证。

程序验证技术除了用于证明程序的正确性，或辅助用户编制正确程序外，还可从程序正确性角度评价程序设计方法和程序设计语言的优劣。但是，保证程序正确性的有效办法，不是在编制程序后再去验证，而是设法在编制过程中，使用适当的技术，使产生的程序是正确无误的。这类技术叫作程序综合和程序变形。程序验证技术和程序综合变形技术相互参照，共同发展。