一个统一的程序验证框架
作者:
基金项目:

本文研究得到博士点基金资助.


A UNIFIED FRAMEWORK FOR PROGRAM VERIFICATION
  • 摘要
  • | |
  • 访问统计
  • |
  • 参考文献 [1]
  • |
  • 相似文献 [20]
  • | | |
  • 文章评论
    摘要:

    本文提出了一个简单的方法,其中程序和其性质都由一个逻辑:时序逻辑中的公式表示.文中给出了一个程序的转换模块的定义,提出了时序执行语义的概念.它是一个时序公式,精确地说明了一个程序.将时序逻辑作为规范语言,程序正确性就意味着说明程序的公式蕴含说明性质的公式,其中蕴含即为一般的逻辑蕴含.因此,本文的方法为并发程序的规范及验证提供了一个统一的框架.它允许充分利用现有的用于证明并发系统时序性质的各种完全证明系统.一个缓冲系统的简单例子用来说明本文的方法.此例子表明本文的方法是可行的.

    Abstract:

    This paper presents a simpler approach in which both a program and its properties are specified by formulas in the same logic: the temporal logic. A transition module of a program is defined and the notion of temporal run semantics, which is a temporal formula precisely characterizing the program is presented. Taken temporal logic as specification language, the correctness of a program means that the formula specifying the program implies the formula specifying the property, where implies is ordinary logical implication. Therefore this approach gives a unified framework for specifying and verifying concurrent programs and allows a full utilization of the existing comprehensive proof systems developed for proving temporal properties of systems. A simple example of a buffer system is presented to illustrate this method and show that the approach is very promising.

    参考文献
    1 Goguen A.Thatcher J W,Wagner E G.An initial algebra approach to the specification,correctness, and imple- mentation of abstract data types.In:Current Trends in Programming Methodology,Prentice-Hall,1978,4:8C ~149. 2 Milner R.A calculus of communicating systems.In:Lec.Notes in Comp.Sci.94, Springer-Verlag. 1980. 3 Tang C S.XYZ a program development environment based on temporal logic.In:Proc.Conf.on Prog. Lang. and Syst.1983.7~19. 4 Tang C S.Toward a unified logic basis for programming languages.In; Mason R E A ed.Information Processing 83,North-Holland,1983.425~429. 5 Pnueli A.The temporal semantics of concurrent programs.Theor.Comp.Sci.,1981,13:1~20. 6 Manna Z,Pnueli A.Verification of concurrent programs:a temporal proof systems.In:de Bakker J W,van Leeuwen J eds.Foundations ofComputer Science IV,Distributed Systems:Part 2,Amsterdam,1983.163~255. 7 Manna Z, Pnueli A.How tO cook a temporal proof system for your pet language.In:Proc.10th ACM Symp. Princ.of Prog.Lang.,Austin,Texas,1983.141~154. 8 Manna Z.Pnueli A.The temporal logic of reactive and concurrent system:specification.New York:Spinger-Ver— lag,1991. 9 Owicki S,Lamport L.Proving liveness properties of concurrent programs.ACM Trans.on Prog.Lang.and Sys..1982,4(3):455~495. 10 Manna Z,Pnueli A.Adequate proof principles for invariance and liveness properties of concurrent systems.Sci. Comput.Prog.,1984,32:257~289. 11 Manna Z.Pnueli A.Completing the temporal picture.Theor.Comp.Sci.,199l,83(1):97~130. 12 Lamport L.What good is temporal logic? In:Mason R E A ed.Information Processing 83,North-Holland, 19R3.657~668. 13 Pnueli A.Specification and verification of reactive systems.In:Kugler H J ed.Information Processing 86,North- Holland.1986.845~858. 14 Lamport L.The temporal logic of actions.ACM Trans.on Prog.Lang.and Sys.,1994,16(3):872~923.
    引证文献
    网友评论
    网友评论
    分享到微博
    发 布
引用本文

贾国平,郑国梁.一个统一的程序验证框架.软件学报,1997,8(2):107-114

复制
分享
文章指标
  • 点击次数:3303
  • 下载次数: 5126
  • HTML阅读次数: 0
  • 引用次数: 0
历史
  • 最后修改日期:1996-01-26
文章二维码
您是第19867352位访问者
版权所有:中国科学院软件研究所 京ICP备05046678号-3
地址:北京市海淀区中关村南四街4号,邮政编码:100190
电话:010-62562563 传真:010-62562533 Email:jos@iscas.ac.cn
技术支持:北京勤云科技发展有限公司

京公网安备 11040202500063号