Specification and Verification of Concurrent Programs Through Refinements

We present a framework for the specification and verification of reactive concurrent programs using general-purpose mechanical theorem proving. We define specifications for concurrent programs by formalizing a notion of refinements analogous to stuttering trace containment. The formalization supports the definition of intuitive specifications of the intended behavior of a program. We present a collection of proof rules that can be effectively orchestrated by a theorem prover to reason about complex programs using refinements. The proof rules systematically reduce the correctness proof for a concurrent program to the definition and proof of an invariant. We include automated support for discharging this invariant proof with a predicate abstraction tool that leverages the existing theorems proven about the components of the concurrent programs. The framework is integrated with the ACL2 theorem prover and we demonstrate its use in the verification of several concurrent programs in ACL2.     

The State of the Art in Agent Communication Languages

Like societies of humans, there is a need for agents in a multi-agent system to rely on one another, enlist the support of peers in order to solve complex tasks. Agents will be able to cooperate only through a meaningful communication language that can bear correctly their mental states and convey precisely the content of their messages. In search for the ideal agent communication language (ACL), several initiatives like the pioneering work of the Knowledge Sharing Effort and the Foundation for Intelligent Physical Agents (FIPA) are paving the way for a platform where all agents would be able to interact regardless of their implementation environment. ACL is a new field of study that could gain from a survey in expanding its application areas. For this purpose, we examine in this paper the state of the art in ACL design and suggest some principles for building a generalized ACL framework. We then evaluate some existing ACL models, and present the current issues in ACL research, and new perspectives. Received 22 July 1999 / Revised 23 March 2000 / Accepted 2 May 2000     

An Observation Approach to the Semantics of Agent Communication Languages

We show how a formal framework for the observation issue in computer systems can be used for the specification of an agent behavior, abstracting away from agent inner details while focusing on its interactive behavior. This model can also be used as a specification of agent communication languages (ACLs), providing the proper abstraction level to represent the conditions causing an agent to send a message, as well as its effect on the receiving agent. In particular, this approach generalizes upon existing ACL semantics, such as FIPA ACL, that relate agent communicative acts to the agent mental state. Since the observation framework induces a more abstract architecture than other known approaches, our semantics are likely to be applicable to a wider set of agent architectures, thus better supporting standardization aims. Some application examples are shown, describing how various aspects of ACL semantics can be specified within our framework.     

Affine parameter estimation from the trace transform

In this paper, we assume that we are given the images of two segmented objects, one of which may be an affinely distorted version of the other, and wish to recover the values of the parameters of the affine transformation between the two images. The images may also differ by the overall level of illumination. The multiplicative constant of such difference may also be recovered. We present a generic theoretical framework to solve this problem. In terms of this framework, other proposed methods may be interpreted. We show how, in this framework, one can recover the affine parameters in a way that is robust to various effects, such as occlusion and illumination variation. The proposed method is generic enough to be applicable also to matching two images that do not depict the same scene or object.     

A theoretical framework for multiple neural network systems

Multiple neural network systems have become popular techniques for tackling complex tasks, often giving improved performance compared to single network systems. For example, modular systems can provide improvements in generalisation through task decomposition, whereas multiple classifier and regressor systems typically improve generalisation through the ensemble combination of redundant networks. Whilst there has been significant focus on understanding the theoretical properties of some of these multi-net systems, particularly ensemble systems, there has been little theoretical work on understanding the properties of the generic combination of networks, important in developing more complex systems, perhaps even those a step closer to their biological counterparts. In this article, we provide a formal framework in which the generic combination of neural networks can be described, and in which the properties of the system can be rigorously analysed. We achieve this by describing multi-net systems in terms of partially ordered sets and state transition systems. By way of example, we explore an abstract version of learning applied to a generic multi-net system that can combine an arbitrary number of networks in sequence and in parallel. By using the framework we show with a constructive proof that, under specific conditions, if it is possible to train the generic system, then training can be achieved by the abstract technique described.     

A generic framework for constructing cross‐realm C2C‐PAKA protocols based on the smart card

A cross‐realm client‐to‐client password‐authenticated key agreement (C2C‐PAKA) protocol allows network clients from different realms managed by different servers to agree on a session key in an authentic manner based on easily memorizable passwords. In this paper, we present a generic framework for constructing a cross‐realm C2C‐PAKA protocol from any secure smart card‐based password authentication (PA‐SC) protocol. The security proof of our construction can be derived from the underlying PA‐SC protocol employing the same assumptions. Our generic framework appears to be the first one with provable security. In addition, compared with similar protocols, the instantiation of our construction achieves improved efficiency. Copyright © 2010 John Wiley & Sons, Ltd.     

基于扩展卡尔曼粒子滤波算法的神经网络训练

神经网络的训练是一种非线性系统的辨识问题,基本粒子滤波算法已被成功用于训练神经网络,但基本粒子滤波算法在建议分布的选择上并没有考虑当前时刻观测值的影响,本文针对该问题提出使用扩展卡尔曼滤波器来生成建议分布。由于扩展卡尔曼滤波器在传递近似建议分布的均值和协方差的过程中充分利用了观测值信息,从而可以更好地描述神经网络权值的后验概率分布。实验结果证明,使用扩展卡尔曼滤波器作为建议分布的粒子滤波算法性能明显优于基本粒子滤波算法。     

Petri net modules in the transformation-based component framework

Component-based software engineering needs to be backed by thorough formal concepts and modeling techniques. This paper combines two concepts introduced independently by the two authors in previous papers. On one hand, the concept of Petri net modules introduced at IDPT 2002 in Padberg [J. Padberg, Petri net modules, Journal on Integrated Design and Process Technology 6 (4) (2002) 105–120], and on the other hand a generic component framework for system modeling introduced at FASE 2002 in Ehrig et al. [H. Ehrig, F. Orejas, B. Braatz, M. Klein, M. Piirainen, A generic component concept for system modeling, in: Proceedings of FASE ’02, Lecture Notes in Computer Science, vol. 2306, Springer, 2002]. First we develop a categorical formalization of the transformation based approach to components that is based on pushouts. This is the frame in which we show that Petri net modules can be considered as an instantiation of the generic component framework. This allows applying the transformation based semantics and compositionality result of the generic framework to Petri net modules. In addition to general Petri net modules we introduce Petri net modules preserving safety properties which can be considered as another instantiation of pushout based formalization of the generic framework.     

A component framework for system modeling based on high-level replacement systems

The aim of this paper is to present a generic component framework for system modeling that satisfies main requirements for component-based development in software engineering. In this sense, we have defined a framework that can be used, by providing an adequate instantiation, in connection with a large class of semi-formal and formal modeling techniques. Moreover, the framework is also flexible with respect to the connection of components, providing a compositional semantics of components. This means more precisely that the semantics of a system can be inferred from the semantics of its components. In contrast to other component concepts for data type specification techniques, our component framework is based on a generic notion of transformations. In particular, refinements and transformations are used to express intradependencies, between the export interface and the body of a component, and interdependencies, between the import and the export interfaces of different components. The generic component framework generalizes module concepts for different kinds of Petri nets and graph transformation systems proposed in the literature, and seems to be also suitable for visual modeling techniques, including parts of the UML, if these techniques provide a suitable refinement or transformation concept. In this paper the generic approach is instantiated in two steps. First to high-level replacement systems generalizing the transformation concept of graph transformations. In a second step it is further instantiated to low-level and high-level Petri nets. To show applicability we present sample components from a case study in the domain of production automation as proposed in a priority program of the German Research Council (DFG).     

基于Spring Security ACL的系统访问控制研究

Spring Security ACL是一个权限访问控制框架,主要用来控制各种资源的访问权限。本文讲述Spring Security ACL的机制原理和理论研究,同时也通过一个简单的权限控制实现的例子演示Spring Security ACL的安全框架的实现方法和过程。     

Structured Theory Development for a Mechanized Logic

Experience has shown that large or multi-user interactive proof efforts can benefit significantly from structuring mechanisms, much like those available in many modern programming languages. Such a mechanism can allow some lemmas and definitions to be exported, and others not. In this paper we address two such structuring mechanisms for the ACL2 theorem prover: encapsulation and books. After presenting an introduction to ACL2, this paper justifies the implementation of ACL2s structuring mechanisms and, more generally, formulates and proves high-level correctness properties of ACL2. The issues in the present paper are relevant not only for ACL2 but also for other theorem-proving environments.     

A generic and parallel algorithm for 2D digital curve polygonal approximation

In this paper, we present a generic topological and geometrical framework which allows to define and control several parallel algorithms for 2D digital curve approximation. The proposed technique is based on combinatorial map simplifications guided by geometrical criteria. We illustrate the genericity of the framework by defining three contour simplification methods: a polygonal approximation one based an area deviation computation; a digital straight segments reconstruction one which guaranties to obtain a loss-less representation; and a moment preserving simplification one which simplifies the contours while preserving geometrical moments of the image regions. Thanks to a complete experimental evaluation, we demonstrate that the proposed methods can be efficiently implemented in a multi-thread environment to simplify labeled image contours.     

A Component Framework Based on High-Level Replacement Systems

This paper is based on two general concepts. The first one is a generic component framework for system modeling presented at FASE 2002, which is especially useful for graph- and net-based modeling techniques. The second one is the concept of high-level replacement systems, which has been studied within the last decade as an abstraction of the DPO-approach for graph transformation systems in a categorical framework, with instantiations to a large class of different modeling techniques. In this contribution both concepts are combined in the sense that the generic transformation concept - essentially used in the component framework - is instantiated by high-level replacement systems. As the main result we show how the properties for transformations required in the component framework can be shown in the case of high-level replacement systems. Moreover, some interesting extensions concerning multiple interfaces, union, and operational semantics of components are proposed.     

Secret handshakes from ID-based message recovery signatures: A new generic approach

Secret handshake scheme, as a relatively new cryptographic application, allows the members of a certain organization to secretly authenticate each other. In this paper, we present a new generic framework for transforming any ID-based message recovery signature to a secret handshake scheme, whose provability can be determined by the security of underlying signature. Based on our new generic framework, two concrete secret handshake schemes are elaborated, which originate from two different ID-based message recovery signatures and are provably secure against the chosen-message attack in the random oracle model.     

A Framework for Adaptive Fault-Tolerant Execution of Workflows in the Grid: Empirical and Theoretical Analysis

In this paper, we propose and evaluate a framework for fault tolerant workflow execution in Grid environments. Different from previous work in the literature, our system dynamically chooses an appropriate fault tolerance technique while using a user-defined rule-based system. We also provide a generic interface that can be used to add fault tolerance techniques to the framework. The results obtained with real workflows in an experimental Grid environment show that the overhead introduced by our framework in a failure-free execution is, in the worst evaluated case, approximately 10 %. Moreover, we show that, using our framework, workflows are able to execute successfully in the presence of failures and that the framework can dynamically choose an appropriate fault tolerance technique. The main contributions of our work are twofold: the developed framework and the model-based dependability analysis we performed on it. The purpose in carrying out a model-based dependability analysis consists on evaluating the interaction between our framework and the distributed Grid environment beyond the physical limitations of an empirical evaluation. By doing this, we provide means to plan the assurance of QoS in the Grid resource allocation, while applying the fault-tolerance mechanisms we implement in our framework regardless of the underlying middleware.     

Formal Proofs About Rewriting Using ACL2

We present an application of the ACL2 theorem prover to reason about rewrite systems theory. We describe the formalization and representation aspects of our work using the first-order, quantifier-free logic of ACL2 and we sketch some of the main points of the proof effort. First, we present a formalization of abstract reduction systems and then we show how this abstraction can be instantiated to establish results about term rewriting. The main theorems we mechanically proved are Newman's lemma (for abstract reductions) and Knuth–Bendix critical pair theorem (for term rewriting).     

A Framework for Community Information Systems

In this paper we present a generic framework architecture for Web-based community information systems (CIS). The framework has an open architecture based on COTS (commercial-off-the-shelf) software components and network technologies. We discuss how a component-based approach, a layered architecture model, and design patterns can be used to provide a common framework for CIS. The CIS framework architecture results in significant benefits that include reuse, a flexible user interface, powerful search mechanisms and an integrated and scalable architecture. XML and rule-based StyleSheet languages are used for storage, information search and graphical presentation at the server or client. The overall framework architecture, its individual components and the interaction among these components are outlined.     

Agent通信语言综述

作为Agent间通信的关键,Agent通信语言(AgentCommunicationLanguage,ACL)已经得到学术界和企业界的广泛研究。在综合分析国内外有关ACL文献的基础上,总结了ACL的起源和发展,设计了ACL的基本框架;并在此框架基础上,分析比较了各种ACL,尤其对两种主流ACL:KQML(KnowledgeQueryandManagementLanguage)和FIPAACL(TheFoundationforIntelligentPhysicalAgentsACL)进行比较分析,最后对ACL研究热点做了总结,概括了可能的进一步研究方向。