Towards Verification of C Programs: Axiomatic Semantics of the C-kernel Language

With the aim of the verification of programs in the C-light language [1], its kernel C-kernel is separated, and an axiomatic semantics for it is suggested. A theorem on soundness of the axiomatic semantics of C-kernel with respect to its operational semantics is proved. The C-light language is used as an input language of the program verification system, which includes a translator to C-kernel and a generator of the correctness conditions for C-kernel programs, which is based on its axiomatic semantics.     

Formalizing Java-MaC

The Java-MaC framework is a run-time verification system for Java programs that can be used to dynamically test and enforce safety policies. This paper presents a formal model of the Java-MaC safety properties in terms of an operational semantics for Middleweight Java, a realistic subset of full Java. This model is intended to be used as a framework for studying the correctness of Java-MaC program instrumentation, optimizations, and future experimentation with run-time monitor expressiveness. As a preliminary demonstration of this model's applicability for these tasks, the paper sketches a correctness result for a simple program instrumentation scheme.     

基于XYZ/SE的软件部分正确性验证

针对软件形式化描述和正确性验证研究中存在的问题,提出了基于XYZ/SE的统一框架研究该问题。在该框架下,基于逐步求精思路对软件进行抽象;对软件整体进行形式化描述和部分正确性验证;对抽象得到的软件各部分进行形式化描述和部分正确性验证;进行调整和验证,即：如果推导结果与预期不一致,则需要重写相关程序或者回溯检查推导过程是否存在错误,直至程序部分正确性得到验证为止。以国库信息处理系统为对象,分析了基于XYZ/SE的统一框架性能。分析表明,基于该框架能够对软件的不同抽象层次进行规范描述,实现从抽象（静态语义）到具体（动态语义）的平滑过渡。同时,基于XYZ/SE的统一框架也可以表示Hoare逻辑推演规则。     

Some applications of topology to program semantics

The relationship between programs and the set of partial correctness assertions that they satisfy, constitutes a Galois connection. The topology resulting from this Galois connection is closely related to the Lindenbaum baum topology for the language in which these partial correctness assertions are stated. This relationship provides us with a tool for understanding the incompleteness of Hoare Logics and for answering certain natural questions about the connection between the relational semantics and the partial correctness assertion semantics for programs, especially in connection with the question of modularity of programs. Two questions to which we shall find topological answers in this paper are “When is a language expressive for a program?”, and “When can we have rules of inference which are adequate to infer the properties of the complex program ±#β from those of its components ±,β?” We also obtain a natural answer to the question “What can the set{(A, B)|{A}±{B} is true) look like for arbitraryα?”.     

以太坊中间语言的可执行语义

智能合约是实现各类区块链应用的核心软件程序.近期,以太坊区块链平台（Ethereum）上的智能合约暴露出大量错误和安全隐患,在国际上引发了智能合约形式化验证的研究热潮.为提供高可信度的验证结果,智能合约程序语言的形式化必不可少.本工作对以太坊中间语言Yul进行形式化,首次给出了其类型系统和小步操作语义的形式化定义.该语义为可执行语义（executable semantics）,由120个Yul语言程序组成的测试集进行测试.本工作在Isabelle/HOL证明辅助工具中完成,为基于定理证明的智能合约正确性、安全性验证奠定了基础.     

基于函数式语义的循环和递归程序结构通用证明技术

各类安全攸关系统的可靠运行离不开软件程序的正确执行.程序的演绎验证技术为程序执行的正确性提供高度保障.程序语言种类繁多,且用途覆盖高可靠性场景的新式语言不断涌现,难以为每种语言设计支撑其程序验证任务的整套逻辑规则,并证明其相对于形式语义的可靠性和完备性.语言无关的程序验证技术提供以程序语言的语义为参数的验证过程及其可靠性结果.对每种程序语言,提供其形式语义后可直接获得面向该语言的程序验证过程.提出一种面向大步操作语义的语言无关演绎验证技术,其核心是对不同语言中循环、递归等可导致无界行为的语法结构进行可靠推理的通用方法.特别地,借助大步操作语义的一种函数式形式化提供表达程序中子结构所执行计算的能力,从而允许借助辅助信息对子结构进行推理.证明所提出验证技术的可靠性和相对完备性,通过命令式、函数式语言中的程序验证实例初步评估了该技术的有效性,并在Coq辅助证明工具中形式化了所有理论结果和验证实例,为基于辅助证明工具实现面向大步语义的语言无关程序验证工具提供了基础.     

Using Program Transformations to Provide Safety Properties for Real-Time Systems

The process of showing that a program satisfies some particular properties with respect to its specification is called program verification. Axiomatic semantics is a verification method that makes assertions describing properties about the states of a program. There exists a transformation from the assertions of a program's verification proof to executable assertions. The latter may be embedded in the program to make it fault tolerant. An axiomatic proof system for concurrent programs is applied to generate executable assertions in a real time distributed environment. A train set example is used as modelproblem.     

VST-Floyd: A Separation Logic Tool to Verify Correctness of C Programs

The Verified Software Toolchain builds foundational machine-checked proofs of the functional correctness of C programs. Its program logic, Verifiable C, is a shallowly embedded higher-order separation Hoare logic which is proved sound in Coq with respect to the operational semantics of CompCert Clight. This paper introduces VST-Floyd, a verification assistant which offers a set of semiautomatic tactics helping users build functional correctness proofs for C programs using Verifiable C.     

Formal Techniques for Analysing Scenarios using Message Sequence Charts

This paper describes light-weight formal techniques based on Message Sequence Charts (MSCs) for capturing and validating early requirements and design. Our focus is on ease of use in specifying, simulating and validating scenarios, and checking their desired properties efficiently. We discuss how the formalism of High Level Message Sequence Charts (HMSCs or MSC'96), can be used to capture scenarios in use cases, thus enabling the use of tools for analysing them. We then present two formal semantics for HMSCs – an intuitive linear time semantics based on runs, and an operational semantics in terms of a labelled transition system. Next we present a way of describing desired properties of use case scenarios using templates, for validating scenarios with respect to informal requirements. The correctness properties of a collection of MSCs can then be established by efficient algorithms for finding paths in a directed graph representing the precedence relation on the events of the MSCs. We have implemented the operational semantics and the verification algorithms in the form of a simulation and verification tool for analysing scenarios.     

A residualizing semantics for the partial evaluation of functional logic programs

Recent proposals for multi-paradigm declarative programming combine the most important features of functional, logic and concurrent programming into a single framework. The operational semantics of these languages is usually based on a combination of narrowing and residuation. In this paper, we introduce a non-standard, residualizing semantics for multi-paradigm declarative programs and prove its equivalence with a standard operational semantics. Our residualizing semantics is particularly relevant within the area of program transformation where it is useful, e.g., to perform computations during partial evaluation. Thus, the proof of equivalence is a crucial result to demonstrate the correctness of (existing) partial evaluation schemes.     

A WSDL-based type system for asynchronous WS-BPEL processes

We tackle the problem of providing rigorous formal foundations to current software engineering technologies for web services, and especially to WSDL and WS-BPEL, two of the most used XML-based standard languages for web services. We focus on a simplified fragment of WS-BPEL sufficiently expressive to model asynchronous interactions among web services in a network context. We present this language as a process calculus-like formalism, that we call ws-calculus, for which we define an operational semantics and a type system. The semantics provides a precise operational model of programs, while the type system forces a clean programming discipline for integrating collaborating services. We prove that the operational semantics of ws-calculus and the type system are ‘sound’ and apply our approach to some illustrative examples. We expect that our formal development can be used to make the relationship between WS-BPEL programs and the associated WSDL documents precise and to support verification of their conformance.     

Verification of programs with procedure-type parameters

Summary A verification system is developed for proving the correctness of programs containing procedures with procedure-type parameters. The system, which reduces programs and their specifications to assertions to be proved in ordinary logic, is shown to be logically sound. The reduction process is controlled by the syntax of the program and is completely mechanical, requiring no human intervention. The resulting assertions involve higher-order predicates, but they engender no significant difficulties which are not already present in ordinary first-order theories.Our system views the intermediate objects in the reduction process as extended programs, thereby making verification a much less abstruse process. Treating logical assertions as commands appeals strongly to a programmer's intuition.This research was partially supported by the National Science Foundation under grant MCS77-24236     

Formal verification of Ada programs

The Penelope verification editor and its formal basis are described. Penelope is a prototype system for the interactive development and verification of programs that are written in a rich subset of sequential Ada. Because it generates verification conditions incrementally, Penelope can be used to develop a program and its correctness proof in concert. If an already-verified program is modified, one can attempt to prove the modified version by replaying and modifying the original sequence of proof steps. Verification conditions are generated by predicate transformers whose logical soundness can be proven by establishing a precise formal connection between predicate transformation and denotational definitions in the style of continuation semantics. Penelope's specification language, Larch/Ada, belongs to the family of Larch interface languages. It scales up properly, in the sense that one can demonstrate the soundness of decomposing an implementation hierarchically and reasoning locally about the implementation of each node in the hierarchy     

Towards verification of C# programs: A three-level approach

In the paper, a new three-level approach to the verification of sequential object-oriented programs is presented. It is applied to an expressive subset C#-light of the C# language, which includes all basic sequential constructs of the latter. At the first stage, the C#-light language is translated into the intermediate C#-kernel language. At the second stage, lazy correctness conditions are generated by means of the axiomatic semantics developed for C#-kernel. These conditions are lazy because they may include special functional symbols representing postponed extraction of invariants of labeled statements, as well as postponed invocations of methods and delegates. At the third stage, these conditions are refined with the use of operational semantics algorithms. Such an approach simplifies the axiomatic semantics and makes it possible to uniquely derive correctness conditions. An example of verification of a C#-light program is presented.     

Verification of distributed programs using representative interleaving sequences

Summary We present a formal proof method for distributed programs. The semantics used to justify the proof method explicitly identifies equivalence classes of execution sequences which are equivalent up to permuting commutative operations. Each equivalence class is called an interleaving set or a run. The proof rules allow concluding the correctness of certain classes of properties for all execution sequences, even though such properties are demonstrated directly only for a subset of the sequences. The subset used must include a representative sequence from each interleaving set, and the proof rules, when applicable, guarantee that this is the case. By choosing a subset with appropriate sequences, simpler intermediate assertions can be used than in previous formal approaches. The method employs proof lattices, and is expressed using the temporal logic ISTL. Shmuel Katz received his B.A. in Mathematics and English Literature from U.C.L.A., and his M.Sc. and Ph.D. in Computer Science (1976) from the Weizmann Institute in Rechovot, Israel. From 1976 to 1981 he was at the IBM Israel Scientific Center. Presently, he is on the faculty of the Computer Science Department at the Technion in Haifa, Israel. In 1977–1978 he visited for a year at the University of California, Berkeley, and in 1984–1985 was at the University of Texas at Austin. He has been a consultant and visitor at the MCC Software Technology Program, and in 1988–1989 was a visiting scientist at the I.B.M. Watson Research Center. His research interests include the methodology of programming, specification methods, program verification and semantics, distributed programming, data structures, and programming languages. Doron Peled was born in 1962 in Haifa. He received his B.Sc. and M.Sc. in Computer Science from the Technion, Israel in 1984 and 1987, respectively. Between 1987 and 1991 he did his military service. He also completed his D.Sc. degree in the Technion during these years. Dr. Peled was with the Computer Science department at Warwick University in 1991–1992. He is currently a member of the technical staff with AT & T Bell Laboratories. His main research interests are specification and verification of programs, especially as related to partial order models, fault-tolerance and real-time. He is also interested in semantics and topology.This research was carried out while the second author was at the Department of Computer Science, The Technion, Haifa 32000, Israel     

Web服务编排描述语言WS-CDL的形式化模型框架

Web服务编排描述语言WS-CDL从全局的角度定义了一组Web服务之间的协作和交互必须遵守的规则。作为一个基于XML的描述性规范语言,WS-CDL缺乏形式化的模型和验证机制,难以保证协作和交互的正确性。本文针对WS-CDL规范提出了一个基于全局的形式化模型框架Abstract WS-CDL,包括语法、同构关系和操作语义,同时定义了一套从该模型框架到基于Pi-演算描述的局部模型的映射规则,最后通过案例分析给出了全局和局部2个层次的模型验证方法。     

Contributions to the semantics of logic perpetual processes

Summary Logic perpetual processes (logic programs with infinite data structures) have been given several formal (operational and fixpoint) semantics. In this paper, we compare the various semantics and define a formal characterization of a least fixpoint semantics, which is based on a modified version of the logic programs and which is satisfactory for a large class of logical perpetual processes. Our results show that all the proposed fixpoint semantics are not equivalent to the operational semantics and suggest an improvement of the least fixpoint approach.     

Mechanically verifying concurrent programs with the Boyer-Mooreprover

A proof system suitable for the mechanical verification of concurrent programs is described. This proof system is based on Unity, and may be used to specify and verify both safety and liveness properties. However, it is defined with respect to an operational semantics of the transition system model of concurrency. Proof rules are simply theorems of this operational semantics. This methodology makes a clear distinction between the theorems in the proof system and the logical inference rules and syntax which define the underlying logic. Since this proof system essentially encodes Unity in another sound logic, and this encoding has been mechanically verified, this encoding proves the soundness of this formalization of Unity. This proof system has been mechanically verified by the Boyer-Moore prover. This proof system has been used to mechanically verify the correctness of a distributed algorithm that computes the minimum node value in a tree     

Counterexample-guided Spatial Flow Model Checking Methods for C Code

Software verification has always been a popular research topic to ensure the correctness and security of software. However, due to the complex semantics and syntax of programming languages, the formal methods for verifying the correctness of programs have the problems of low accuracy and low efficiency. In particular, the state change in address space caused by pointer operations makes it difficult to guarantee the verification accuracy of existing model checking methods. By combining model checking and sparse value-flow analysis, this paper designs a spatial flow model to effectively describe the state behavior of C code at the symbolic-variable level and address-space level and proposes a model checking algorithm of CounterExample-Guided Abstraction refinement and Sparse value-flow strong update (CEGAS), which enables points-to-sensitive formal verification for C code. This paper establishes a C-code benchmark containing a variety of pointer operations and conducts comparative experiments on the basis of this benchmark. These experiments indicate that in the task of analyzing multi-class C code features, the model checking algorithm CEGAS proposed in this paper can achieve outstanding results compared with the existing model checking tools. The verification accuracy of CEGAS is 92.9%, and the average verification time of each line of code is 2.58 ms, both of which are better than those of existing verification tools.     

A framework for computer-aided validation

This paper presents a framework for augmenting independent validation and verification (IV&V) of software systems with computer-based IV&V techniques. The framework allows an IV&V team to capture its own understanding of the application as well as the expected behavior of any proposed system for solving the underlying problem by using an executable system reference model, which uses formal assertions to specify mission- and safety-critical behaviors. The framework uses execution-based model checking to validate the correctness of the assertions and to verify the correctness and adequacy of the system under test.