Processes with infinite liveness requirements

In this paper we develop a deterministic process algebra for describing and reasoning about liveness requirements of infinite behaviour systems beyond the ones usually captured by non-deterministic process models. These liveness requirements refer to the capability of processes to engage spontaneously in some actions and to wait passively for the triggering of other actions by other processes. A semantic theory based on three equivalent semantic domains (denotational, operational, and axiomatic) is developed for the language of process terms.     

OSI多方一致性测试

一致性测试的目的是测试疲则系统（或实现）是否符合有关标准，多方测试的应用领域是协议步及到多于两方的场合，本文开放系统互连多方测试的一般方法。     

When is partial trace equivalence adequate?

Two processes arepartial trace equivalent iff they can perform the same sequences of actions in isolation. Partial trace equivalence is perhaps the simplest possible notion of process equivalence. In general, it is too simple: it is not usually an adequate semantics. We investigate the circumstances under which it is adequate, which are surprisingly rich. We give two substantial classes of languages for which partial traces are adequate. In one class, partial trace equivalence suffices for total correctness, and operations such as true sequencing are possible; but all processes are determinate and silent moves are not possible. The other class — which includes many standard process calculi, such as CCS and CSP — admits indeterminacy and silent moves, but partial traces only suffice for partial correctness and true sequencing is not definable.Supported by NSF grant (CCR-9003441)     

Ready to preorder: The case of weak process semantics

Recently, Aceto, Fokkink and Ingólfsdóttir proposed an algorithm to turn any sound and ground-complete axiomatisation of any preorder listed in the linear time-branching time spectrum at least as coarse as the ready simulation preorder, into a sound and ground-complete axiomatisation of the corresponding equivalence—its kernel. Moreover, if the former axiomatisation is ω-complete, so is the latter. Subsequently, de Frutos Escrig, Gregorio Rodríguez and Palomino generalised this result, so that the algorithm is applicable to any preorder at least as coarse as the ready simulation preorder, provided it is initials preserving. The current paper shows that the same algorithm applies equally well to weak semantics: the proviso of initials preserving can be replaced by other conditions, such as weak initials preserving and satisfying the second τ-law. This makes it applicable to all 87 preorders surveyed in “the linear time-branching time spectrum II” that are at least as coarse as the ready simulation preorder. We also extend the scope of the algorithm to infinite processes, by adding recursion constants. As an application of both extensions, we provide a ground-complete axiomatisation of the CSP failures equivalence for BCCS processes with divergence.     

基于进程代数的UML序列图的形式语义

UML序列图用于建模实例间动态交互过程．但UML规范并没有给出其形式化的动态语义,这不利于对模型进行形式化验证和证明。本文把序列图中的事件动作及其执行序列映射为进程代数中的进程表达式,利用进程代数语义框架来构建UML序列图的形式语义。首先,建立了序列图到进程代数的语义映射规则;然后用Plotkin风格的结构化操作语义给出并证明务件组合算子演绎规则;最后,归纳定义了算子次序约束条件并证明了其可终止性。     

A Consistent Causality-Based View on a Timed Process Algebra Including Urgent Interactions

This paper discusses a timed variant of a process algebra akin to LOTOS, baptized UPA, in a causality-based setting. Two timed features are incorporated—a delay function which constrains the occurrence time of atomic actions and an urgency operator that forces (local or synchronized) actions to happen urgently. Timeouts are typical urgent phenomena. A novel timed extension of event structures is introduced and used as a vehicle to provide a denotational causality-based semantics for UPA. Recursion is dealt with by using standard fixpoint theory. In addition, an operational semantics is presented based on separate time- and action-transitions that is shown to be consistent with the event structure semantics. An interleaving semantics for UPA is immediately obtained from the operational semantics. By adopting this dual approach the well-developed timed interleaving view is extended with a consistent timed partial order view and a comparison is facilitated of the partial order model and the variety of existing (interleaved) timed process algebras.     

Semantic Issues in the Verification of Agent Communication Languages

This article examines the issue of developing semantics for agent communication languages. In particular, it considers the problem of giving a verifiable semantics for such languages—a semantics where conformance (or otherwise) to the semantics could be determined by an independent observer. These problems are precisely defined in an abstract formal framework. Using this framework, a number of example agent communication frameworks are defined. A discussion is then presented, of the various options open to designers of agent communication languages, with respect the problem of verifying conformance.     

A process algebra to formalize the Lyee methodology

Over the last years, various methodologies and techniques have been elaborated and proposed to improve one or many aspects related to the software development life cycle. However, despite the great effort in this research field, the production of clearly understood and modifiable systems still an ambitious goal and far from reached. This is due, on one hand, to the complexity and the subtlety of software themselves and, on the other hand, to the limitations of the current methodologies. Recently, a new and very promising methodology, called Lyee, has been proposed. Intended to deal efficiently with a wide range of software problems related to different field, Lyee allows the development of software by simply defining their requirements.

Nevertheless, since both the semantics of Lyee generated software together with the process of automatic generation of software from requirements are described using informal language, difficulties and confusions may arise when trying to understand and study this methodology.

The main purpose of this paper is to formalize, using a process algebra, the process of automatic generation of softwares together with the semantics of Lyee generated softwares. Actually, process algebra naturally supports many concepts of the Lyee methodology and consequently formalize them simply and elegantly. It offers to the Lyee methodology an abstract machine more suitable than the Von-Newman one. In fact, this new abstract machine consider a program as chemical solution when molecules (different vectors of the lyee methodology) interact together to reach a collective goal.     

Abstraction and Testing in CSP

Restricted views of process behaviour result in a form of abstraction which is useful in the construction of specifications involving fault-tolerance and atomicity. This paper presents an operational characterisation of abstraction for refusable and non-refusable events in terms of testing. This view is a generalisation of standard notions of testing, and is given a new denotational characterisation encapsulated within the CSP denotational semantics. It informs, reinforces and extends the traditional denotational approach to abstraction. Received February 2000 / Accepted in revised form April 2000     

周期性可定实时并行进程的进化代数分析

对应用进化代数(EA),即目前的抽象状态机(AbstractStateMachine–ASM),描述可定时实时并行进程进行了研究,进化代数采用第一顺序逻辑(First-OrderLogic)定义或解释计算机问题,描述不同的抽象等级并且逻辑地描述计算机算法,因此非常适合描述并行进程复杂的运行过程,并逻辑地精确推导进程调度。     

Step semantics for “true” concurrency with recursion

We present a variety of denotational linear time semantics for a language with recursion and true concurrency in a form of synchronous co-operation, which in the literature is known as step semantics. We show that this can be done by a generalization of known results for interleaving semantics. A general method is presented to define semantical operators and denotational semantics in the Smyth powerdomain of streams. With this method, first a naive and then more sophisticated semantics for synchronous co-operation are developed, which include such features as interleaving and synchronization. Then we refine the semantics to deal with a bounded number of processors, subatomic actions, maximal parallelism and a real-time operator. Finally, it is indicated how to apply these ideas to branching-time models, where it becomes possible to analyze deadlock behaviour as well as a form of true concurrency. John-Jules Meyer received his Master's degree in Mathematics in 1979 from the University of Leiden, and his Ph.D. degree in 1985 from the Free University Amsterdam. He is currently a Professor of Theoretical Computer Science, both at the Free University Amsterdam and at the University of Nijmegen. His current research interests include semantics of programming languages and logics for computer science, in particular artifical intelligence. Erik de Vink received the M.S. degree in Mathematics from the University of Amsterdam. He is currently a Junior Researcher at the Department of Mathematics and Computer Science of the Free University Amsterdam. At the moment his main research concerns the semantics of concurrent and logic programming languages.     

Approximating Markovian testing equivalence

Several approaches have been proposed to relax behavioral equivalences for fine-grain models including probabilities and time. All of them face two problems behind the notion of approximation, i.e., the lack of transitivity and the efficiency of the verification algorithm. While the typical equivalence under approximation is bisimulation, we present a relaxation of Markovian testing equivalence in a process algebraic framework. In this coarser setting, we show that it is particularly intuitive to manage separately three different dimensions of the approximation-execution time, event probability, and observed behavior-by illustrating in each case, results concerning the two problems mentioned above. Finally, a unified definition combining the three orthogonal aspects is provided in order to favor trade-off analyses.     

Estimating the maximum information leakage

Preventing improper information leaks is a greatest challenge of the modern society. In this paper, we present a technique for measuring the ability of several families of adversaries to set up a covert channel. Our approach relies on a noninterference based formulation of security which can be naturally expressed by semantic models of the program execution. In our analysis the most powerful adversary is measured via a notion of approximate process equivalence. Even if finding the most powerful adversary is in general impractical, we show that this requires only a finite number of checks for a particular family of adversaries which are related to a probabilistic information flow property.

网管接口实现一致性声明文稿的定义方法

通过对部分现有网络管理接口实现一致性声明文稿共性的分析,总结出了实现一致性声明文稿的分类和所应涉及的范围,提出了通用的一致性声明文稿的基本组成,并给出了其一般的定义原则。此外,还指出了现有的一致性声明文稿模板中存在的某些不足之处,并提供了相应的改善方法。     

基于TCL的DHCP协议冒烟测试

介绍了基于TCL的协议冒烟测试系统,对DHCP协议进行形式化分析,生成EFSM图,采用UIO方法生成一致性测试序列,并在该系统上针对提供DHCP服务的各网络设备进行了DHCP协议的冒烟测试,在实际应用中取得了较好的测试效率,缩短了产品研发周期,降低了风险,提高了产品的可靠性。     

A Deterministic Logical Semantics for Esterel

Esterel is a synchronous design language for the specification of reactive systems. There exist two main semantics for Esterel. On the one hand, the logical behavioral semantics provides a simple and compact formalization of the behavior of programs using SOS rules. But it does not ensure deterministic executions for all programs and all inputs. As non-deterministic programs have to be rejected as incorrect, this means it defines behaviors for incorrect programs, which is not convenient. On the other hand, the constructive semantics is deterministic (amongst other properties) but at the expense of a much more complex formalism. In this work, we construct and thoroughly analyze a new deterministic semantics for Esterel that retains the simplicity of the logical behavioral semantics, from which it derives. In our view, it provides a much better framework for formal reasoning about Esterel programs.     

协同CAD系统中的并发控制机制

并发操作是协同CAD系统中至关重要的问题。该文提出了并发操作控制机制的设计原则,阐述了基于语义的并发控制机制利用嵌套事务来解决传统图档事务并发控制中的数据一致性低、中间版本不易维护等问题,结合实际给出了博士CAD系统中并发控制的系统模型,并作了相应的说明。     

基于标记变迁系统的可信计算平台信任链测试

可信计算是当今世界信息安全领域的重要潮流之一.根据国家有关规定,信息安全产品需要经过测评认证,但目前国内外对可信计算测试的理论与技术研究还非常不完善,也无相应测试工具或系统,这必然影响可信计算的发展.该文着眼于规范定义的信任链行为特征,以进程代数作为指称语义描述工具,以标记变迁系统作为操作语义,对规范定义的信任链行为特征进行了形式化描述,提出了一种基于标记变迁系统的信任链测试模型框架.针对信任链规范与实现之间的问题,从易测性出发对测试集进行了有效约简;并论证了信任链的规范实现与规范说明之间的关系,为测试用例构造方法提供了理论依据,从而解决了信任链测试这一难题.     

一种基于形式化描述的测试序列生成改进方法

动生成测试序列始终是软件工程中一项极为困难的工作．国际标准化组织（ＩＳＯ）一直致力于协议一致性测试方法与形式化描述技术的研究．本文讨论了基于形式化描述的协议测试序列生成方法中的问题,特别是提出了“部分Ｔ序列叠加算法”对使用ＵＩＯ序列生成测试序列的方法做了进一步改进,大大减少了测试开销．     

SCHOOL: a Small Chorded Object-Oriented Language

Chords are a declarative synchronisation construct based on the Join-calculus, available in the programming language C-omega. To our knowledge, chords have no formal model in an object-oriented setting. In this paper we suggest SCHOOL, a formal model for an imperative, object-oriented language with chords. We give an operational semantics and type system, and can prove soundness of the type system.