当前位置：文档之家 › 一种用于指针程序验证的指针逻辑

一种用于指针程序验证的指针逻辑

  • 格式：pdf
  • 大小：857.80 KB
  • 文档页数：12

ISSN 1000-9825, CODEN RUXUEW E-mail: jos@iscas.ac.cn Journal of Software, Vol.21, No.3, March 2010, pp.415−426 http://www.jos.org.cn doi: 10.3724/SP.J.1001.2010.03620 Tel/Fax: +86-10-62562563 © by Institute of Software, the Chinese Academy of Sciences. All rights reserved.

一种用于指针程序验证的指针逻辑∗ 陈意云1,2, 李兆鹏1,2+, 王志芳1,2, 华保健1,2 1(中国科学技术大学 计算机科学与技术学院,安徽 合肥 230026)

2(中国科学技术大学 苏州研究院 软件安全实验室,江苏 苏州 215123)

Pointer Logic for Verification of Pointer Programs CHEN Yi-Yun1,2, LI Zhao-Peng1,2+, WANG Zhi-Fang1,2, HUA Bao-Jian1,2 1(School of Computer Science and Technology, University of Science and Technology of China, Hefei 230026, China)

2(Software Security Laboratory, Suzhou Institute for Advanced Study, University of Science and Technology of China, Suzhou 215123,

China) + Corresponding author: E-mail: zpli@mail.ustc.edu.cn

Chen YY, Li ZP, Wang ZF, Hua BJ. Pointer logic for verification of pointer programs. Journal of Software, 2010,21(3):415−426. http://www.jos.org.cn/1000-9825/3620.htm

Abstract: This paper improves and extends the pointer logic that has been designed for verifying pointer programs. Its main contribution is that a concept of legal sets of access paths is presented, which simplifies elementary operations on access paths and makes inference rules of the logic easier to understand. Furthermore, the logic with inference rules is extended for local reasoning and for function construction, making the logic used conveniently in the context of function calls. Key words: software safety; Hoare logic; pointer logic; proof-carrying code; certifying compiler

摘 要: 本文改进并扩展先前为验证指针程序提出的指针逻辑,主要贡献是提出了合法访问路径集合的概念,极大地简化了访问路径上的基本运算,并使得指针逻辑推理规则变得易理解.另外,增加了局部推理规则和函数构造的推理规则,使得指针逻辑可以方便地用于有函数调用的场合. 关键词: 软件安全;Hoare逻辑;指针逻辑;携带证明的代码;出具证明的编译器 中图法分类号: TP301 文献标识码: A

携带证明的代码(proof-carrying code,简称PCC)[1]作为一种新的代码范型(paradigm),给编程语言的研究领

域带来了巨大挑战:其一是寻找表达力更强的逻辑或类型系统来规范或推理高级语言或低级语言程序的性质;其二是研究出具证明的编译技术. 对于第1个挑战,类型化汇编语言[2]和类型细化的理论[3]是两种基于类型方式的典型研究,而PCC、携带基础逻辑证明的FPCC(foundational proof-carrying code)[4]、经过验证的汇编编程CAP(certifying assembly programming)[5]和基于栈的经过验证的汇编编程SCAP(stack-based certifying assembly programming)[6]是基于

逻辑方式的典型研究.基于类型的技术和基于逻辑的技术是互补的,近年来,一些研究人员倾向于组合这两种技

∗ Supported by the National Natural Science Foundation of China under Grant Nos.90718026, 60928004 (国家自然科学基金) Received 2008-01-16; Accepted 2009-03-31 416 Journal of Software 软件学报 Vol.21, No.3, March 2010

术.应用类型系统ATS[7]将程序状态引入类型系统,依靠ATS与Hoare逻辑的相似性,以ATS来编码Hoare逻辑,

从而可以在类型系统上模拟Hoare逻辑的推理. 对于第2个挑战,Necula作为先驱者实现了一个叫作Touchstone的出具证明编译器(certifying compiler)[8],

它包含一个类型安全的C语言小子集的传统编译器,还有为该编译器生成的汇编代码自动产生类型安全证明的证明器.Touchstone的主要限制是在指针类型和动态存储分配方面.随后,Colby等人实现了Special J[9],这是

Java语言较大子集的一个出具证明编译器,它把Java字节代码编译成英特尔IA32体系结构的目标代码. 近年来,我们研究了将出具证明编译和携带证明代码的技术应用到有显式内存管理的编程语言.我们设计了有动态内存分配和回收机制的类C小语言PointerC[10],其基本安全策略要求程序运行时不出现通过NULL

指针或悬空指针(dangling pointer)进行存取指向对象的操作、不把NULL指针或悬空指针作为free函数调用的实在参数、不发生内存泄漏等.我们采用一种基于逻辑的和基于类型的技术相结合的方式来推导程序的性质.为了使类型系统简单并保证语言的安全性,我们在定型规则(typing rule)中增加了约束语法表达式的值的副条件.为了静态检查这些副条件,我们为PointerC语言设计了一种指针逻辑[11,12],它是Hoare逻辑的一种拓展,新

颖之处是,将精确的指针分析应用于程序验证.指针逻辑可用来从前向后收集各指针是NULL指针、悬空指针还是有效指针(valid pointer,有指向对象的指针)的信息,收集各有效指针之间相等与否的信息.所收集信息用来证明指针程序是否满足定型规则的副条件,以支持对指针程序的安全性验证和其他性质的验证.我们完成了PointerC语言安全性和指针逻辑可靠性的证明[13],并实现了PointerC出具证明编译器的一个原型[12,14]. 本文是对指针逻辑前期设计的改进和扩展,主要贡献如下: (1) 提出了合法(legal)访问路径集合的概念,极大地简化了访问路径上基本运算的定义,并使得指针逻辑推理规则变得直观和易理解; (2) 增加了局部推理规则和函数构造的推理规则,使得指针逻辑可以方便地用于有函数调用的场合; (3) 与广泛使用的分离逻辑进行了深入比较.指针逻辑相当于高级语言层面的分离逻辑,其优于分离逻辑之处是能够防止内存泄漏. 本文全面介绍重新设计的指针逻辑:第1节介绍PointerC语言.第2节介绍指针逻辑的重新设计.第3节给出采用指针逻辑的一个证明实例.第4节比较指针逻辑和分离逻辑.第5节是相关工作的比较.第6节是总结.

1 PointerC语言 PointerC是一个强调指针类型的类C小语言,它略去函数声明部分的语法(如图1所示),其类型系统可见文 献[10].

Fig.1 Syntax of PointerC language 图1 PointerC语言语法 在PointerC中,指针类型的变量只能用于赋值、相等与否比较、存取指向对象等运算以及作为函数的参数;指针算术和取地址运算(&)被禁止.malloc和free被看成是PointerC预定义的函数,并且满足安全程序的最基本

(Program) program::=structdeclist vardeclist stmtlist (Structure Decl. List) structdeclist::=structdeclist structdec|ε (Structure Decl.) structdec::=struct id{vardeclist}; (Variable Decl. List) vardeclist::=vardeclist vardec|ε (Variable Decl.) vardec::=type idlist; (Identifier List) idlist::=idlist, id|id (Type) type::=bool|int|struct id∗ (Statement List) stmtlist::=stmtlist stmt|stmt (Statement) stmt::=lval=exp; |lval=malloc(struct id); |if (boolexp) block else block |while (boolexp) block |free (lval); (Block) block::=stmt|{stmtlist} (Expression) exp::=number|NULL|lval|−exp|exp+exp|exp–exp|exp×exp|… (Bool Expression) boolexp::=true|false|exp==exp|exp!=exp|… |¬boolexp|boolexp∧boolexp|boolexp∨boolexp (L-value) lval::=id|lval->id (Natual Number) number::=0|1|2|…

合集下载

形式化验证：从混成系统到CPS

形式化验证：从混成系统到CPS

卜　磊南京大学形式化验证：从混成系统到CPS关键词：形式化验证　混成系统　CPS混成系统是一种嵌入在物理环境下的实时系统，一般由离散组件和连续组件连接组成，组件之间的行为由计算模型控制。

经典混成系统一般分为离散层和连续层，其构成体现了计算机科学和控制理论的交叉。

在连续层，通过系统变量对时间的微分方程来描述系统的实际控制操作模型以及系统中参数的演变规律。

而在离散层，则通过状态机、佩特里网等高抽象层次模型来描述系统的逻辑控制转换过程。

在两层之间通过一定的接口和规则将连续层的信号与离散层的控制模式进行关联和转换。

大多数复杂实时控制系统，都包含连续变化的物理层与离散变化的决策控制层之间的交互过程，因此混成系统在工业控制和国防等领域大量存在，特别是安全系统，如交通运输、航空航天、医疗卫生、工业控制等。

随着在人们生活中的应用越来越广，重要性越来越高，人们对相应系统的质量特别是可信性的需求快速提升，系统失效所带来的灾难也越来越大。

在交通运输方面，车载导航系统的小小失误就可能造成交通事故，而飞机导航系统的失误则可能导致机毁人亡。

在国防领域，对软件系统的错误已经进入零容忍度阶段。

因此，如何对混成系统进行有效的可信性保障成为一个亟待解决的问题。

一般而言，测试、仿真[2,3]等技术是研究和保障软件质量的主要方法。

这些方法主要以运行系统为发现问题的主要手段。

由于人力无法穷尽地遍历系统所有可能的运行输入和场景，也就不足以保证检测的完备性，这可能会给系统后期运行留下安全隐患。

因此，在对系统错误零容忍的安全攸关的系统领域，采用可证明系统模型正确性的形式化验证理论和技术[4,5]来对系统模型进行安全性验证就显得极为重要，这也成为了相关领域近期的主要关注点。

混成系统形式化验证形式化方法形式化方法(formal method)混成系统实时嵌入式系统，特别是复杂的实时控制系统，广泛存在着这样一类子系统：它们行为中的离散化逻辑控制与连续性的时间行为相互依赖，相互影响，彼此互为依存，息息相关。

深入了解Windows句柄到底是什么（句柄是逻辑指针，或者是指向结构体的指针，图文并茂，非。。。

深入了解Windows句柄到底是什么（句柄是逻辑指针，或者是指向结构体的指针，图文并茂，非。。。

深⼊了解Windows句柄到底是什么（句柄是逻辑指针，或者是指向结构体的指针，图⽂并茂，⾮。

总是有新⼊门的Windows程序员问我Windows的句柄到底是什么，我说你把它看做⼀种类似指针的标识就⾏了，但是显然这⼀答案不能让他们满意，然后我说去问问度娘吧，他们说不⾏⽹上的说法太多还难以理解。

今天⽐较闲，我上⽹查了查，光是百度百科词条“句柄”中就有好⼏种说法，很多叙述还是错误的，天知道这些误⼈⼦弟的⼈是想⼲什么。

这⾥我列举词条中的关于句柄的叙述不当之处，⾄于如何不当先不管，继续往下看就会明⽩:1.windows 之所以要设⽴句柄，根本上源于管理机制的问题—，简⽽⾔之数据的地址需要变动，变动以后就需要有⼈来记录管理变动，（就好像户籍管理⼀样），因此系统⽤句柄来记载数据地址的变更。

2.如果想更透彻⼀点地认识句柄，我可以告诉⼤家，句柄是⼀种指向的。

通常我们说句柄是WINDOWS⽤来标识被应⽤程序所建⽴或使⽤的对象的唯⼀整数。

这句话是没有问题的，但是想把这句话对应到具体的内存结构上就做不到了。

下⾯我们来详细探讨⼀下Windows中的句柄到底是什么。

1.虚拟内存结构要理解这个问题，⾸先不能避开Windows的虚拟内存结构。

对于这个问题已有前⼈写了⽐较好的解释，这⾥我为了保证博客连贯性，直接贴上需要的部分(原⽂是讲解JVM虚拟机的性能提升的⽂章，在其中涉及到了虚拟内存的内容，解释的⾮常好，这⾥我截取这部分略加修改，这⾥是)我们知道，CPU是通过寻址来访问内存的。

32位CPU的寻址宽度是 0~0xFFFFFFFF ，计算后得到的⼤⼩是4G，也就是说可⽀持的物理内存最⼤是4G。

但在实践过程中，碰到了这样的问题，程序需要使⽤4G内存，⽽可⽤物理内存⼩于4G，导致程序不得不降低内存占⽤。

为了解决此类问题，现代CPU引⼊了（Memory Management Unit 内存管理单元）。

MMU 的核⼼思想是利⽤虚拟地址替代物理地址，即CPU寻址时使⽤虚址，由 MMU 负责将虚址映射为物理地址。

c语言实验报告实验

c语言实验报告实验

c语言实验报告实验C 语言实验报告实验一、实验目的本次 C 语言实验的主要目的是通过实际操作和编程实践，加深对 C 语言基本语法、数据类型、控制结构、数组、指针等重要概念的理解和掌握，提高编程能力和解决实际问题的能力。

二、实验环境本次实验使用的编程环境为 Visual Studio 2019，操作系统为Windows 10。

三、实验内容1、基本数据类型和运算符的使用定义不同类型的变量，如整数型（int）、浮点型（float、double）、字符型（char）等，并进行赋值和运算操作。

熟悉各种运算符的优先级和结合性，包括算术运算符（＋、、、／、％）、关系运算符（＞、＜、＞＝、＜＝、＝＝、！＝）、逻辑运算符（＆＆、｜｜、！）、位运算符（＆、｜、＾、～、＜＜、＞＞）等。

2、控制结构的应用使用ifelse 语句实现条件判断，根据不同的条件执行相应的代码块。

运用 switch 语句进行多分支选择，处理不同的情况。

利用 for 循环、while 循环和 dowhile 循环实现重复执行的操作，例如计算数列的和、打印特定的图案等。

3、数组和字符串的操作定义和使用一维数组、二维数组，进行数组元素的访问、赋值和遍历。

掌握字符串的存储和处理方式，使用字符数组和字符串函数（如strlen、strcpy、strcmp 等）进行字符串的操作。

4、指针的应用理解指针的概念和指针变量的定义，通过指针访问变量和数组元素。

实现指针与数组、指针与函数的结合使用，体会指针在程序中的灵活运用。

5、函数的定义和调用编写自定义函数，实现特定的功能，如计算阶乘、判断素数等。

掌握函数的参数传递方式（值传递和地址传递），理解函数的返回值。

6、结构体和共用体的使用定义结构体类型，创建结构体变量，访问结构体成员。

了解共用体的概念和使用场景，比较结构体和共用体的区别。

四、实验步骤1、实验准备打开 Visual Studio 2019 开发环境，创建一个新的 C 语言项目。

易语言整数型转子程序指针

易语言整数型转子程序指针

易语言整数型转子程序指针易语言是一种面向计算机编程的高级程序设计语言，它拥有简单易学的特点，适用于初学者入门编程。

在易语言中，整数型转子程序指针是一种非常重要的概念，它对于程序的实现和优化起到了关键性的作用。

本文将以整数型转子程序指针为主题，一步一步地进行详细解析和回答相关问题。

一、整数型转子程序指针的概念整数型转子程序指针是指将整数类型的变量作为指针变量来使用的一种技术。

在易语言中，整数型转子程序指针是一种特殊的指针，它不仅可以指向某个地址的数据，还可以通过修改指针中存储的整数值来实现对程序的控制。

二、整数型转子程序指针的定义和使用在易语言中，我们可以通过以下步骤来定义和使用整数型转子程序指针：1. 首先，需要定义一个整数型的变量，用来存储指针的值。

我们可以使用整数类型的变量来表示指针，例如：Pointer: 整数。

2. 然后，需要将整数型变量设置为转子程序指针类型。

可以使用“设为指针”命令来实现，例如：设为指针(Pointer)。

3. 接下来，可以将该变量的值设置为任意一个整数，作为转子程序指针所指向的地址。

我们可以使用赋值语句来实现，例如：Pointer = 地址。

4. 最后，可以使用转子程序指针来实现对程序的控制。

通过修改指针中存储的整数值，可以切换到不同的代码段，以实现流程的跳转和控制。

三、整数型转子程序指针的应用场景整数型转子程序指针在易语言中有着广泛的应用场景，以下是一些常见的应用场景：1. 循环控制：通过修改转子程序指针的值，可以实现循环的控制。

当转子程序指针的值为0时，跳转到循环体的起始位置；当转子程序指针的值为1时，跳转到循环体的结束位置；可以通过循环计数器来控制循环的次数。

2. 条件控制：通过修改转子程序指针的值，可以实现条件的控制。

当转子程序指针的值为0时，跳转到条件为假的代码段；当转子程序指针的值为1时，跳转到条件为真的代码段；可以通过判断条件的结果来修改转子程序指针的值。