14940267
Integrating Software Engineering Methods and Petri Nets for the Specification and Prototyping of Complex Information Systems
We present a Petri net based framework called G-Net for the modular design of complex information systems. The motivation of this framework is to integrate Petri net theory with a modular, objectoriented approach for the specification and prototyping of complex software systems. We use the client/server example to illustrate the G-Net specification of distributed systems, and how such a specification can be translated into a Predicate/Transition net for formal analysis. The differences between G-Net and hierarchical Petri net, as well as some limitations of the transformation technique, are then discussed.
2725088
Architecture-driven modeling of real-time concurrent systems with applications in FMS
Abstract Petri nets have become increasingly popular for flexible manufacturing systems (FMS) modeling and control because they accurately capture the concurrent, non-deterministic and time-dependent properties of the systems. While offering many advantages, conventional Petri net models suffer from some serious problems that limit their usability as design models for complex FMS. Central to these problems is the lack of an engineering support for incremental design, refinement, and analysis of large-scale systems. In this paper, we present an architecture-driven approach for the modeling and design of FMS that effectively addresses the problems while leveraging the strengths of Petri nets. The approach has two major aspects: The first is a Net-based and Object-based Architectural Model (NOAM) that introduces a well-founded architectural framework into the Petri nets notation and lays a foundation to support formal design. The second is a modeling method based on NOAM that uses architecture decomposition and refinement as the basis to reduce design complexity, to provide smooth transition from informal to formal design, and to support incremental refinement and analysis. A case study using NOAM for FMS modeling is provided to show the applicability of our approach.
14596334
A formal approach to designing secure software architectures
Software architecture plays a central role in developing software systems that provide basic functionality and satisfy critical properties such as reliability and security. However, little has been done to formally model software architectures and to systematically enforce required properties. We aim to propose a formal approach to designing secure software architectures. We use the software architecture model (SAM), a general software architecture model combining Petri nets and temporal logic, as the underlying formalism. Architecture design consists of the functionality part and the security part. Guidelines are proposed to design functionality of software architectures at both element level and composition level. Software security is enforced by stepwise refinement.
9746543
Design an Interoperable Mobile Agent System Based on Predicate Transition Net Models
Mobile agents provide an effective and flexible style to develop advanced distributed systems. In order to promote interoperability and ensure the quality of mobile agent systems, it is necessary to formalize software architecture of mobile agent systems. In this paper, we not only define the software architecture of interoperable mobile agent systems using predicate transition nets, but also analyze the interoperability between agents. In addition, a formal model-driven design method to develop mobile agent systems is described with examples. Our method naturally integrates formal methods and practical approaches in the agent system design phase. The method can be used to develop other complex software systems as well.
10829689
A Framework for the Modeling and Prototyping of Distributed Information Systems
The major issues in designing Distributed Information Systems (DIS) include localization of control and data, inherent concurrency, intensive interactions among computation agents, history sensitivity, dynamic configuration and continuous system change and evolution. We propose a framework, called the G-Net model, for the specification, modeling and prototyping of DIS. The G-Net model not only provides a flexible notation to represent the executable specification of DIS through G-Net instantiation, but also offers a novel style of decentralized concurrent computation, allowing flexible inter-agent communication and interaction. A prototype of the G-Net framework has been implemented on workstations connected by a local network.
24822225
Achieving a Better Middleware Design through Formal Modeling and Analysis
207130140
Guest Editors' Introduction: Special Issue on Embedded Software Engineering
Embedded systems, typically components of larger electro-mechanical systems with the purpose of controlling or helping such systems to achieve their overall goals, are playing an increasingly critical role in modern society and economy. According to David Tennenhouse, Chief Scientist of Intel and former director of DARPA ISO, 98% of all current computer applications are embedded systems. The market for embedded computer applications has shown explosive growth with tremendous applications in, for example, telecommunications, health-care, manufacturing, remote monitoring, and transportation, to name a few. An important trend is that embedded systems are becoming increasingly complex, software-intensive and distributed. For instance, it was projected that software written for cellular phones will reach from 2 to 5 million lines of code in the next few years. While this underscores the growing importance of software it also raises some concerns since methods of developing embedded software are lagging far behind hardware advances. The unique characteristics of embedded systems, such as complex control logic, severe limitations on resources (e.g. memory and power consumption), hard real-time constraints, and stringent performance and dependability requirements, are stressing the limits of mainstream architectures, languages, tools, and techniques. Much of the embedded software development today depends on intensive manual programming and costly yet error-prone testing methods for quality assurance. Further, current embedded software development techniques use monolithic designs which are not scalable, configurable, or adaptable. These problems have resulted in long product cycles, cost overruns, and poor system quality. These problems, if not addressed, will escalate, and significantly hinder the development and deployment of complex embedded systems. This special issue on embedded software engineering is aimed at stimulating research interests in this important emerging area, which merges software engineering methodologies and techniques with embedded system development techniques. After careful reviews, five papers were selected for the special issue. Collectively,
6786934
Concurrently Non-Malleable Zero Knowledge in the Authenticated Public-Key Model
We consider a type of zero-knowledge protocols that are of interest for their practical applications within networks like the Internet: efficient zero-knowledge arguments of knowledge that remain secure against concurrent man-in-the-middle attacks. As negative results in the area of concurrent non-malleable zero-knowledge imply that protocols in the standard setting (i.e., under no setup assumptions) can only be given for trivial languages, researchers have studied such protocols in models with setup assumptions, such as the common reference string (CRS) model. This model assumes that a reference string is honestly created at the beginning of all interactions and later available to all parties (an assumption that is satisfied, for instance, in the presence of a trusted party). A growing area of research in Cryptography is that of reducing the setup assumptions under which certain cryptographic protocols can be realized. In an effort to reduce the setup assumptions required for efficient zeroknowledge arguments of knowledge that remain secure against concurrent man-in-the-middle attacks, we consider a model, which we call the Authenticated Public-Key (APK) model. The APK model seems to significantly reduce the setup assumptions made by the CRS model (as no trusted party or honest execution of a centralized algorithm are required), and can be seen as a slightly stronger variation of the Bare Public-Key (BPK) model from [8, 30], and a weaker variation of the registered public-key model used in [3]. We then define and study man-in-the-middle attacks in the APK model. Our main result is a constant-round concurrent non-malleable zero-knowledge argument of knowledge for any polynomial-time relation (associated to a language in NP), under the (minimal) assumption of the existence of a one-way function family. We also show time-efficient instantiations of our protocol, in which the transformation from a 3-round honest-verifier zero-knowledge argument of knowledge to a 4-round concurrently non-malleable zero-knowledge argument of knowledge for the same relation incurs only O(1) (precisely, a small constant) additional modular exponentiations, based on known number-theoretic assumptions. Furthermore, the APK model is motivated by the consideration of some man-inthe-middle attacks in models with setup assumptions that had not been considered previously and might be of independent interest. We also note a negative result with respect to further reducing the setup assumptions of our protocol to those in the (unauthenticated) BPK model, by showing that concurrently non-malleable zero-knowledge arguments of knowledge in the BPK model are only possible for trivial languages.
42696276
Concurrently Non-malleable Black-Box Zero Knowledge in the Bare Public-Key Model
In this paper we study the possibility of reducing the setup assumptions under which concurrent non-malleable zero knowledge protocol can be realized. A natural model choice is the bare public-key (BPK) model of [6], a model with very minimal setup assumptions. Our main contribution is to show in this model the following about constant-round concurrent non-malleable black-box zero-knowledge arguments. 
They can be constructed from any one-way function for any language in $\mathcal{NP}$. Here, our construction takes 5 rounds, and we can reduce it to a 4-round (round-optimal) argument under existence of one-way permutations. 
Under number-theoretic assumptions, they admit a time-efficient instantiation for some specific $\mathcal{NP}$ languages (e.g., all languages having efficient Σ protocols, for which we can implement our construction using only $\mathcal{O}(1)$ modular exponentiations). 
 
 
 
Compared to the non-black-box construction in a concurrent work of [OPV, ICALP 2008] in this model, our protocol (even the construction from one-way function) is significantly more time- and round-efficient and can be based on more general assumptions.
1196454
Resolving the Simultaneous Resettability Conjecture and a New Non-Black-Box Simulation Strategy
Canetti, Goldreich, Goldwasser, and Micali (STOC 2000) introduced the notion of resettable zero-knowledge proofs, where the protocol must be zero-knowledge even if a cheating verifier can reset the prover and have several interactions in which the prover uses the same random tape. Soon afterwards, Barak, Goldreich, Goldwasser, and Lindell (FOCS 2001) studied the closely related notion of resettable soundness, where the soundness condition of the protocol must hold even if the cheating prover can reset the verifier to have multiple interactions with the same verifier's random tape. The main problem left open by this work was whether it is possible to have a single protocol that is simultaneously resettable zero knowledge and resettably sound. We resolve this question by constructing such a protocol. At the heart of our construction is a new non-black-box simulation strategy, which we believe to be of independent interest. This new strategy allows for simulators which "marry'' recursive rewinding techniques (common in the context of concurrent simulation) with non-black-box simulation. Previous non-black-box strategies led to exponential blowups in computational complexity in such circumstances, which our new strategy is able to avoid.
2501651
A Fast Line Segment Based Dense Stereo Algorithm Using Tree Dynamic Programming
Many traditional stereo correspondence methods emphasized on utilizing epipolar constraint and ignored the information embedded in inter-epipolar lines. Actually some researchers have already proposed several grid-based algorithms for fully utilizing information embodied in both intra- and inter-epipolar lines. Though their performances are greatly improved, they are very time-consuming. The new graph-cut and believe-propagation methods have made the grid-based algorithms more efficient, but time-consuming still remains a hard problem for many applications. Recently, a tree dynamic programming algorithm is proposed. Though the computation speed is much higher than that of grid-based methods, the performance is degraded apparently. We think that the problem stems from the pixel-based tree construction. Many edges in the original grid are forced to be cut out, and much information embedded in these edges is thus lost. In this paper, a novel line segment based stereo correspondence algorithm using tree dynamic programming (LSTDP) is presented. Each epipolar line of the reference image is segmented into segments first, and a tree is then constructed with these line segments as its vertexes. The tree dynamic programming is adopted to compute the correspondence of each line segment. By using line segments as the vertexes instead of pixels, the connection between neighboring pixels within the same region can be reserved as completely as possible. Experimental results show that our algorithm can obtain comparable performance with state-of-the-art algorithms but is much more time-efficient.