一种用于指针程序安全性证明的指针逻辑陈意云华保健葛琳王志芳（中国科学技术大学计算机科学与技术系，合肥230026）（中国科学技术大学苏州研究院软件安全实验室，苏州215123）摘要：在高可信软件的各种性质中，安全性是关注的重点，其中软件满足安全策略的证明方法是研究的热点之一。本文根据我们所设想的安全程序的设计和证明框架，为类C语言的一个子集设计了一个指针逻辑系统。该逻辑系统是Hoare逻辑系统的一种扩展，它用推理规则来表达每一种语句引起指针信息的变化情况。它可用来对指针程序进行精确的指针分析，所获得信息用来证明指针程序是否满足定型规则的附加条件，以支持程序的安全性验证。该逻辑系统也可用来证明指针程序的其它性质。关键词：软件安全，指针逻辑，Hoare逻辑，指针分析，类型系统中图法分类号：TP3011引言在高可信的各种要求中，安全性（包括safety和security）是关注的重点。Safety是指软件运行时不引起危险、灾难的能力，而security是指软件系统对数据和信息提供保密性、完整性、可用性、真实性保障的能力。本文所讲的安全性主要是指safety，但是软件的safety和security是有联系的，黑客通常就是利用缓冲区溢出、数组访问越界、悬空指针访问等低级的safety错误，来破坏系统和获取未经授权的控制等。因此提高safety有助于保证security。程序性质证明（而不是历史上的程序正确性证明）领域近十年来有了很大的发展，许多学者提出了不同的思路，这些思路主要采取基于类型的或基于逻辑的方法，用于高级语言程序或低级语言程序的性质证明。基于类型方法的典型研究有类型化汇编语言（TypedAssemblyLanguage）[1]和类型细化（typerefinement）理论[2]的研究。基于逻辑方法的典型研究有携带证明的代码（Proof-CarryingCode，简称PCC）[3]和FPCC（FoundationalProof-CarryingCode）框架[4]。ZhongShao的携带证明汇编编程项目CAP（CertifiedAssemblyProgramming）[5]和基于栈的CAP（SCAP）[6]是典型的基于逻辑的研究项目。基于逻辑的方法和基于类型论的方法有很大的互补性，近年来出现了一些结合这两种方法的研究。一种结合两者的研究是HongweiXi等进行的ATS（AppliedTypeSystem）项目的研究[7]，他们扩展类型系统，将程序状态引入类型系统，依靠ATS与Hoare逻辑的相似性，以ATS来编码Hoare逻辑，从而可以在他们的类型系统上模拟Hoare逻辑的推理。在国际上这些研究的基础上，我们认为，对于那些有高安全性要求的软件，程序设计和证明的一种新方式将是：（1）程序设计者将软件的安全策略等描述成程序应满足的规范，连同程序一起提交给编译器；（2）编译器生成为证明程序满足规范所需的验证条件，并且利用内嵌的定理证明器自动地或交互地证明这些验证条件；（3）编译器在把源程序翻译成目标代码的同时，将源程序满足规范的证明翻译成目标代码满足等效规范的证明，这样的编译器称为出具证明的编译器（certifyingcompiler）；（4）在目标代码一级由证明检验器利用代码所携带的证明自动进行代码满足规范的检验。该框架的优点是，它向程序设计者提供源级而不是目标级的程序性质证明方法，以提高安全程序的开发效率，同时它将编译器、证明器等排除出受信任的计算基础（TrustedComputingBase，简称TCB），以尽量缩小系统的TCB。本文介绍我们在这个框架的初步实现中，为类C语言的一个子集PointerC设计的一个指针逻辑系统，它是Hoare逻辑的一种扩展，本质上是一种精确的指针分析（pointeranalysis）工具。它可用来从前向后收集各指针是NULL指针、悬空指针（danglingpointer）还是有效指针（有指向对象的指针）的信息，收集各有效指针之间相等与否的信息。所收集信息用来证明指针程序是否满足定型规则（typingrule）的附加条件，以支持对指针程序的安全性验证及其它性质的验证。本文的组织如下：第二节介绍有关指针安全的一些基本概念，第三节是指针逻辑的设计，第四节给出一个证明实例，第五节是相关工作比较，第六节是总结。2基本知识首先介绍PointerC在指针运算方面的限制。在PointerC中，指针类型的变量只能用于赋值、相等和不相等比较、存取指向对象等运算以及作为函数（...
