Nowadays, extended state machines are prominent requirements specification techniques due to their capabilities of modeling complex systems in a compact way. These machines extend the standard state machines with variables and have transitions guarded by enabling predicates and may include variable update statements. Given a system modeled as an extended state machine, with possibly infinite state space and some non-controllable (parameterized) interactions, a pruning procedure is proposed to symbolically derive a maximal sub-machine of the original system that satisfies certain conditions; namely, some safeness and absence of undesirable deadlocks which could be produced during pruning. In addition, the user may specify, as predicates associated with states, some general goal assertions that should be preserved in the obtained sub-machine. Further, one may also specify some specific requirements such as the elimination of certain undesirable deadlocks at states, or fail states that should never be reached. Application examples are given considering deadlock avoidance and loops including infinite loops over non-controllable interactions showing that the procedure may not terminate. In addition, the procedure is applied for finding a controller of a system to be controlled. The approach generalizes existing work in respect to the considered extended machine model and the possibility of user defined control objectives written as assertions at states.

The “Game Hack” Scam (GHS) is a mostly unreported cyberattack in which attackers attempt to convince victims that they will be provided with free, unlimited “resources” or other advantages for their favorite game. The endgame of the scammers ranges from monetizing for themselves the victims time and resources by having them click through endless “surveys”, filing out “market research” forms, etc., to collecting personal information, getting the victims to subscribe to questionable services, up to installing questionable executable files on their machines. Other scams such as the “Technical Support Scam”, the “Survey Scam”, and the “Romance Scam” have been analyzed before but to the best of our knowledge, GHS has not been well studied so far and is indeed mostly unknown. In this paper, our aim is to investigate and gain more knowledge on this type of scam by following a data-driven approach; we formulate GHS-related search queries, and used multiple search engines to collect data about the websites to which GHS victims are directed when they search online for various game hacks and tricks. We analyze the collected data to provide new insight into GHS and research the extent of this scam. We show that despite its low profile, the click traffic generated by the scam is in the hundreds of millions. We also show that GHS attackers use social media, streaming sites, blogs, and even unrelated sites such as change.org or jeuxvideo.com to carry out their attacks and reach a large number of victims. Our data collection spans a year; in that time, we uncovered 65,905 different GHS URLs, mapped onto over 5,900 unique domains.We were able to link attacks to attackers and found that they routinely target a vast array of games. Furthermore, we find that GHS instances are on the rise, and so is the number of victims. Our low-end estimation is that these attacks have been clicked at least 150 million times in the last five years. Finally, in keeping with similar large-scale scam studies, we find that the current public blacklists are inadequate and suggest that our method is more effective at detecting these attacks.

It is well known that many phishing attacks are variations of previous phishing attacks. We evaluate here the feasibility of applying Pawlik and Augsten's recent implementation of Tree Edit Distance (AP-TED) calculations as a way to compare DOMs and identify similar phishing attack instances. We also compare this tree method with an existing method that uses the distance between tag vectors to quantity similarity between phishing sites. We observe that no single distance method perfectly detects all types of phishing attack variations. We find that the tree method is more demanding for computing equipment, but it better discriminates the similarity with known attacks. We also introduce a method to reduce the volume of calculations by 99.4% when calculating pairwise edit distance on trees with respect to AP-TED calculations on all data.

The so-called ``phishing'' attacks are one of the important threats to individuals and corporations in today's Internet. Combatting phishing is thus a top-priority, and has been the focus of much work, both on the academic and on the industry sides. In this paper, we look at this problem from a new angle. We have monitored a total of 19,066 phishing attacks over a period of ten months and found that over 90% of these attacks were actually replicas or variations of other attacks in the database. This provides several opportunities and insights for the fight against phishing: first, quickly and efficiently detecting replicas is a very effective prevention tool. We detail one such tool in this paper. Second, the widely held belief that phishing attacks are dealt with promptly is but an illusion. We have recorded numerous attacks that stay active throughout our observation period. This shows that the current prevention techniques are ineffective and need to be overhauled. We provide some suggestions in this direction. Third, our observation give a new perspective into the modus operandi of attackers. In particular, some of our observations suggest that a small group of attackers could be behind a large part of the current attacks. Taking down that group could potentially have a large impact on the phishing attacks observed today.

Abstract The dynamic behavior of a car can be modeled as a hybrid system involving continuous state changes and discrete state transitions. We show that the control of safe (collision free) lane change maneuvers in multi-lane traffic on highways can be described by finite state machines extended with continuous variables coming from the environment. We use standard theory for controller synthesis to derive the dynamic behavior of a lane-change controller. Thereby, we contrast the setting of interleaving semantics and synchronous concurrent semantics. We also consider the possibility of exchanging knowledge between neighboring cars in order to come up with the right decisions. Finally, we address compositional verification using an assumption-guarantee paradigm.

New Web technologies, like AJAX, result in more responsive and interactive Web applications, sometimes called Rich Internet Applications (RIAs). Crawling techniques developed for traditional Web applications are not sufficient for crawling RIAs. The inability to crawl RIAs is a problem that needs to be addressed for at least making RIAs searchable and testable. We present a new methodology, called “model-based crawling”, that can be used as a basis to design efficient crawling strategies for RIAs. We illustrate model-based crawling with a sample strategy, called the “hypercube strategy”. The performances of our model-based crawling strategies are compared against existing standard crawling strategies, including breadth-first, depth-first, and a greedy strategy. Experimental results show that our model-based crawling approach is significantly more efficient than these standard strategies.

Testing the reliability of an application usually requires a good usage model that accurately captures the likely sequences of inputs that the application will receive from the environment. Markov usage models and their variations have been found to be well suited for generating test cases that are statistically close to what the application is expected to receive when in production. In this article, we study the specific case of web applications. We present an evaluation method for estimating the accuracy of various reliability-testing usage models. The method is based on comparison between observed users' traces and traces inferred from the usage model. Our method gauges the accuracy of the reliability-testing usage model by calculating the sum of goodness-of-fit values of each traces and scaling the result between 0 and 1.

Crawling is a necessary step for testing web applications for security. An important concept that impacts the efficiency of crawling is state equivalence. This paper proposes two techniques to improve any state equivalence mechanism. The first technique detects parts of the pages that are unimportant for crawling. The second technique helps identifying session parameters. We also present a summary of our research on crawling techniques for the new generation of web applications, so-called Rich Internet Applications (RIAs). RIAs present new security and crawling challenges that cannot be addressed by traditional techniques. Solving these issues is a must if we want to continue benefitting from automated tools for testing web applications.

This paper deals with performance modeling of distributed applications, service compositions and workflow systems. From the functional perspective, the distributed application is modeled as a collaboration involving several roles, and its behavior is defined in terms of a composition from several sub-collaborations using the standard sequencing operators found in UML Activity Diagrams and similar formalisms. From the performance perspective, each collaboration is characterized by a certain number of independent input events and dependent output events, and the performance of the collaboration is defined by the minimum delays that apply for a given output event in respect to each input event on which it depends. We use a partial order to model these delays. The paper explains how these minimum delays can be measured through testing. It also provides general formulas by which the performance of a composed collaboration can be calculated from the performance of its constituent subcollaborations and the control structure which determines the order of execution of these sub-collaborations. Proofs of correctness for these formulas are given and a simple example is discussed throughout the paper.

In this comment, several errors in Chlamtac et al., 1996, Lightpath (Wavelength) Routing in Large WDM Networks and one error in Xu et al., 2000, Dynamic Routing and Assignment of Wavelength Algorithms in Multifiber Wavelength Division Multiplexing Networks are pointed out. We present corrections to the errors.

In this paper, we propose a distributed approach for the least constraining slot allocation scheme in all-optical TDM networks (LC) that was introduced in a previous work. The driving force behind our proposal is the employment of the LC scheme in a GMPLS context. After describing the basic data model and messaging parameters, we focus on defining an efficient LC resource status update scheme, which is essential to achieve compatibility with GMPLS' periodic link state update standards. Basically, we reduce the rate of resource status updates from once per call to once per few calls, and measure the impact on network performance.

We present a study on the static resource allocation in lightpath routed WDM networks, where each request is associated with a service grade. The goal is to maintain certain acceptance ratios for the requests of all grades, as well as to minimize the resource consumption. We propose a model of static grade-of-service (GoS) differentiation as minimizing the total rejection and cost penalty. Then, we use the Lagrangian relaxation and subgradient methods to solve the problem. The results of using static GoS differentiation are presented.

Various static resource allocation algorithms have been used in WDM networks to allocate resources such as wavelength channels, transmitters, receivers, and wavelength converters to a given set of static lightpath demands, based on certain design objectives. However, although optimized resource allocations can be obtained, it remains an open issue how to determine which resources are bottlenecks to achieve better performance. Existing static resource allocation algorithms do not explicitly measure the impact of a given resource on the design objective. In this paper, we propose such a measurement based on the Lagrangian relaxation (LR) framework We use the optimized values of Lagrange multipliers as a direct measurement of the criticality of resources. Such a quantitative measurement can be naturally acquired along with the optimization process to obtain the optimal solution (or a near optimal solution) to the static routing and wavelength assignment (RWA) problem. Such a measurement helps to identify critical resources, and thus to decide the best way to add or reallocate resources.

Node clustering is an effective solution for achieving good performance and high reliability for peer-to-peer (P2P) systems. To improve the performance of a clustered P2P system, it is important to balance the service load among the clusters in the system. In this paper, we describe a diffusive load balancing scheme for clustered P2P systems, which dynamically adjusts the size of the clusters, by moving nodes among the clusters, based on their service demands and node resource capacities. Our simulations show that the proposed load balancing scheme significantly improves the performance of a P2P system in terms of balanced available capacity.

The advantages and issues in deploying a fast photonic network on top of a reconfigurable WDM network are discussed. The agile photonic network is deployed as another user of the reconfigurable optical WDM network (RON), with the reconfigurable optical switches setting up the optical circuits that define the virtual topology for the agile network. The services provided by the agile network are then carried over the wavelengths that are assigned to it by the global control plane of the RON. Such deployment would allow the agile network to provide the fast optical time division multiplexing (OTDM) scheduling techniques warranted for fast-changing, low-capacity traffic flows typical of metropolitan and access networks; while sustained, high-capacity flows would remain in whole lightpaths provided at the RON level to other users. Connectivity options are described for edge and core nodes, as well as the functionality requirements of the global control plane that would manage such a deployment.

Today's online reputation systems lack one important feature: globality. Users build a reputation within one community, and sometimes several reputations within several communities, but each reputation is only valid within the corresponding community. Moreover, such reputation is usually aggregated by the online platform's provider, giving the inquiring agent no say in the process. This paper proposes one way of dealing with this problem. We introduce an online reputation centralizer that collects raw reputation data about users from several online communities and allows for it to be aggregated according to the inquiring agent's requirements, using a stochastic trust model, and taking into account factors that qualify a user's reputation.

Formal models are often considered for software systems specification, and are helpful for verifying that certain properties are respected, or for automatically generating the implementation code corresponding to the model, or again for conformance testing, for the automatic generation of test cases to check an implementation against the formal specification. Variations of finite state machine (FSM) models have been mostly used for conformance testing, while the otherwise very popular formal model of Petri nets is seldom mentioned in this context. In this paper, we look at the question of conformance testing when the model is provided in the form of a 1-safe Petri net. We provide a general framework for conformance testing, and give algorithms for deriving test cases under different assumptions: besides the adaptation of methods originally developed for FSMs which lead to exponentially long test sequences, we have identified cases for which polynomial testing algorithms for free-choice Petri nets can be provided. These results are significant when modeling concurrent systems, as exemplified by workflow modeling.

Several overlay-based live multimedia streaming platforms have been proposed in the recent peer-to-peer streaming literature. In most of the cases, the overlay neighbors are chosen randomly for robustness of the overlay. However, this causes nodes that are distant in terms of proximity in the underlying physical network to become neighbors, and thus data travels unnecessary distances before reaching the destination. For efficiency of bulk data transmission like multimedia streaming, the overlay neighborhood should resemble the proximity in the underlying network. In this paper, we exploit the proximity and redundancy properties of a recently proposed clique-based clustered overlay network, named eQuus, to build efficient as well as robust overlays for multimedia stream dissemination. To combine the efficiency of content pushing over tree structured overlays and the robustness of data-driven mesh overlays, higher capacity stable nodes are organized in tree structure to carry the long haul traffic and less stable nodes with intermittent presence are organized in localized meshes. The overlay construction and fault-recovery procedures are explained in details. Simulation study demonstrates the good locality properties of the platform. The outage time and control overhead induced by the failure recovery mechanism are minimal as demonstrated by the analysis.

This paper is concerned with compositional specification of services using UML 2 collaborations, activity and interaction diagrams. It addresses the problem of realizability: given a global specification, can we construct a set of communicating state machines whose joint behavior is precisely the specified one? We approach the problem by looking at how collaboration behaviors may be composed using UML activity diagrams. We classify realizability problems from the point of view of each composition operator, and discuss their nature and possible solutions. This brings a new look at already known problems: we show that given some conditions, some problems can already be detected at an abstract collaboration level, without needing to look into detailed interactions.

We study the resilience of MPLS flows over an agile all-photonic star WDM network (AAPN). On the basis of our previous inter-area optimal routing architecture, we propose and develop a dynamic inter-area shared segment-based protection (SSP) framework. We consider the dynamic protection for optimal inter-area working paths and improve the recovery time by segment-based protection. We develop a distributed partial routing information management to increase the scalability in multi-area networks while maintaining good performance compared with the case of complete information. By simulation, we show that our framework outperforms existing scheme. Furthermore, our approach shows its good potential to be a protection solution for inter-AS protection.

Emerging grid applications desire not only high bandwidth but also the ability to control the topology and traffic engineering of the underlying networks, through Web service interfaces. To achieve that goal, we present an advanced user controlled lightpath provisioning (UCLP) system, where network resources and grid resources are both modeled as Web services and are seamlessly integrated into workflows.

This paper studies the blocking performance of a class of all-optical overlaid-star TDM networks using a least- congested-path routing strategy in path selection. An analytical model is proposed to estimate the call blocking probability in such networks. This model takes link-load correlation into account and thus can provide accurate estimation of the blocking performance. The accuracy of the analytical model is verified by comparing analytical results with simulation results.

This paper presents a simple and efficient algorithm for timeslot allocation in agile all-photonic network (AAPN) cores working under a time division multiplexing (TDM) mode, called the Quick Birkhoff-von Neumann Decomposition Algorithm (QBvN). The time complexity of QBvN can reach O(Nn) for a N×N switch with a TDM frame size of n. Another version of QBvN, called QBvN-cover, is also proposed to provide guaranteed scheduling with configuration overhead. For QBvN-cover, the bound of the number of generated switch configurations is provided and hence the necessary speedup for AAPN cores. Under stream-type, continuous bit rate traffic, QBvN-cover shows superior delay performance compared with other heuristics in the literature. Although QBvN-cover is unlike other BvN algorithms that use a service matrix as input, we show that service matrix construction from traffic demand is necessary for QBvN-cover to perform well.

A semi-analytical method based on alternate projections on a linear vector space is used to construct a service matrix from a traffic matrix, where the traffic matrix represents the bandwidth requested by the edge nodes and the service matrix represents how the bandwidth will be distributed by the core of an optical star network that operates in a Time Division Multiplexing mode. The algorithm iterates over a mathematical expression of complexity O(N^2), where N denotes the number of edge nodes. The complexity of the method is therefore O(kN^2) where k denotes the number of iterations needed to converge. With N large enough one observes that k\le\leN and hence this expression tends to O(N^2). Results show that the service matrices obtained with this projection method have very high measures of similarity to the original traffic matrix, with an average similarity greater than 95% for N \geqslant 32 . The method is robust to inadmissible/bursty traffic and yields equal or improved delay performance in the optical network compared to other allocation methods.

Summary form only given. Shared protection aims to provide the same level of protection, against a single link failure, as the dedicated one while using less network resources. In this paper, we present the issue of survivability in a time slotted optical networks deploying DWDM. To guarantee the recovery and to maintain the performance of the service, sufficient resource needs to be available at the setup time of the protection. However it is possible to optimize the protection capacity. Indeed the primary traffic is composed of a set of flows, which may be going through different paths. Therefore a protection could be found using just enough resources by sharing the backup among many flows. We propose here a technique to identify and provision the protection using the minimum necessary resources. In particular, we present an algorithm that computes the optimal protection required for a primary traffic from a source to a destination, and the maximum capacity that could be used, on each link, for the protection. We prove through simulation results that this shared mesh protection scheme can significantly reduce the required network protection capacity.

Shared protection aims to provide the same level of protection, against failure, as the dedicated one while using less network resources. In this paper we present the issue of survivability in a time slotted optical networks deploying DWDM. To guarantee the recovery, sufficient resource needs to be available at the setup time of the protection. However it is possible to optimize the protection capacity. Indeed the primary traffic is composed of a set of flows, which may be going through different paths. Therefore a protection could be found using just enough resources by sharing the backup among many flows. We propose here a technique to identify and provision the protection using the minimum necessary resources. We prove through simulation results that this shared mesh protection scheme can significantly reduce the required network protection capacity

The tremendous growth of the Internet has introduced a number of interoperability problems for distributed multimedia applications. These problems are related to the heterogeneity of client devices, network connectivity, content formats, and user's preferences. The purpose of this paper is to present a framework for transcoding multimedia streams. The proposed infrastructure takes into consideration the profile of communicating devices, network connectivity, exchanged content format, context description, and available customization services to find a chain of services that could be applied to adapt the content to the required needed format. Part of the framework is a QoS-based selection algorithm that finds the best sequence of adaptation services which can maximize users' satisfaction with the delivered content.

The development of appropriate test cases is an important issue for conformance testing of protocol implementations and other reactive software systems. A number of methods are known for the development of a test suite based on a specification given in the form of a finite state machine. In practice, the system requirements evolve throughout the lifetime of the system and the specifications are modified incrementally. We adapt four well-known test derivation methods, namely, the HIS, W, Wp, and UIOv methods, for generating tests that would test only the modified parts of an evolving specification. Some application examples and experimental results are provided. These results show significant gains when using incremental testing in comparison with complete testing, especially when the modified part represents less than 20 percent of the whole specification.

Abstract Ubiquitous computing environment is defined by the shift of computing technology from the desktop to the background. One of its most notable attributes is its potential to extend the scope of service and personal mobility. This paper describes an agent‐based architecture that brings personal and service mobility to the ubiquitous computing environment. A software agent, running on a portable device carried by the user, leverages the existing service discovery protocols to learn about all services available in the vicinity of the user. Short‐range wireless technology such as Bluetooth can be used to build a personal area network connecting only devices that are close enough to the user. Acting on behalf of the user and based on a number of aspects, the software agent runs a quality of service (QoS) negotiation and selection algorithm to select the most appropriate available service(s) to be used for a given communication session. The software agent selects as well the configuration parameters for each service. The proposed architecture supports also service hand‐off to recompense for service volatility during user movement. Copyright © 2004 John Wiley & Sons, Ltd.

In recent years, a lot of research effort has been dedicated to the management of quality of service (QoS), mainly in the fields of telecommunication networks and multimedia systems. Emerging applications such as electronic commerce, health-care applications, digital publishing or data mining also have requirements regarding the quality of service, the cost of service, the quality of data to be delivered, the accuracy and precision of the retrieved data. These examples show the need to consider the concept of QoS from a broader perspective, requiring the collaboration of all the distributed system components involved. In this paper, we propose an approach to integrate user-defined QoS requirements, together with the dynamic properties of the system components involved, into a distributed query processing environment. We then propose a query optimization strategy in which multiple goals may be considered with separate cost models. Furthermore, we discuss some experiment results confirming the effectiveness of our approach.

An experimental prototype for server selection using an independent brokerage service is described This prototype is composed of four main components: instrumented Apache Web servers, monitoring agents, a QoS broker, and client emulator. The role of the broker is to distribute client sessions to a set of replicated servers. It is designed to support different types of selection policies and hay the capability to collect performance data from the servers. We include in our description the technique used to instrument Apache servers and our implementation of the server-broker protocol that we have developed. Our implementation of the QoS broker and the technique used to collect data for the performance parameters of interest are also described. We use our prototype to study the performance of server selection algorithms under realistic conditions. The experimental environment and an analysis of the experimental results are presented.

In this paper, we present a protocol that allocates resources in communication networks in order to assure specific QoS characteristics as requested by new connections. The design takes into consideration the possibility for the network allocation to adapt to application requirements.The proposed protocol uses a Bandwidth Preemptive Algorithm that permits adaptive bandwidth allocation in multicast, multi-stream environments. This design has been inspired by the one proposed by Sakate [1] where a centralized methodology is used. In our approach, we use a distributed methodology where we change the behavior of the communication service and allow the continuation of the service under more severe conditions. In other words, when there is a lack of bandwidth for a new connection, the communication service will try to find the missing bandwidth within the existent connections (or streams) when looking for a feasible path on a hop-by-hop basis, starting from the destination to an a on-tree node.

In this paper, we present a method for the synthesis of extended Petri net-based distributed specifications. Our method finds an optimal allocation of resources (computational data) that optimizes the derived distributed specification, based on some reasonable communication-cost criteria.

The World-Wide Web has been a remarkably successful system for distributing hypertext documents. The basic model for Web interaction is that a client requests a page of data which can include images and hyperlinks within it. This interaction model is inadequate for real-time multimedia (MM) applications, since the Web and its associated set of protocols, e.g. HTTP, do not support the real-time transfer of the continuous media (Audio/Video). Several solutions have been proposed to support real-time playout of continuous media via the Web, e.g. Netscape. Most of these solutions do not provide means to the user to negotiate the desired presentation quality (in terms of quality of service (QoS) parameters settings); even the proposals that provide QoS negotiation (more generally QoS management) are used in a rather static manner, that is, the video/audio servers are a priori known. The authors propose to integrate in the WWW a dynamic QoS management approach that allows (1) the user to negotiate the desired QoS; and (2) and to select the "best" video/audio server which might support the user requirements. This activity is based on the general structure of multimedia documents and associated QoS parameters, called meta-data, which they developed under an ongoing CITR project. The main objective of the paper is to integrate meta-data associated with MM document in WWW e.g. Netscape; this will allow one to use dynamic QoS management protocols.

Most current approaches in designing and implementing distributed multimedia (MM) presentational applications have concentrated on the performance of the continuous media file servers in terms of seek-time overhead and real-time disk scheduling; particularly, the quality of service (QoS) negotiation mechanisms they provide are used in a rather static manner, i.e. these mechanisms are restricted to the evaluation of the capacity of certain system components. In contrast to those approaches, we propose a general QoS negotiation framework that supports the dynamic choice of a configuration of system components to support the QoS requirements of the user of a specific application: we consider different possible system configurations and select an optimal one to provide the appropriate QoS support. We document the design and implementation of a QoS negotiation procedure for distributed MM presentational applications, such as news-on-demand. The negotiation procedure described is an instantiation of the general framework for QoS negotiation. Our proposal differs in many respect with the negotiation functions provided by existing approaches: (1) the negotiation process uses an optimization approach to find a configuration of system components which supports the user requirements, (2) the negotiation process supports the negotiation of a MM document and not only a single monomedia object, (3) the QoS negotiation takes into account the cost to the user; (4) the negotiation process may be used to support automatic adaptation to react to QoS degradations, without intervention by the user/application.

We propose an efficient algorithm for constructing optimized protocol converters to achieve interoperability between heterogeneous computer networks. This method first generates constraints from existing protocols and imposes them to channel specifications, which removes message sequences of the channel specifications that do not contribute to system progress. Then, an optimized converter is generated from a given deterministic service specification, the two protocol specifications and the modified channel specifications. The observation equivalence is used to compare the service specification and the internetworking system. Compared with related works reported by Calvert and Lam (1989), our method has two advantages: (1) it generates an optimized converter; and (2) it needs less computation.

The use of formal description techniques allows the partial automation of the design, the validation, and the implementation of communication protocols and distributed algorithms. In this paper, we present a methodology for validation of distributed algorithms and protocols, and our experiences of using the Estelle language, and a simulation and validation tool, called Veda, to simulate and validate complex distributed algorithms for the distributed implementation of multi-rendezvous. Some design errors in published distributed rendezvous algorithms were found. We obtain from these experiences heuristic guidelines for trouble shooting of distributed algorithms.

In Kant et al. (1992), a method of protocol synthesis, using basic LOTOS (BL) as a specification language, is proposed. In the present paper, we generalize this method. We propose an extended basic LOTOS (EBL) to specify the service and the protocol. With EBL, events are associated with enabling conditions and transformation functions that depend on global variables. Next, we propose a method to synthesize protocols using EBL as a specification language. This method is inspired by the concept of transactions.

In protocol engineering, a common approach for system design and implementation is to verify if an implementation specification (or any lower level specification) satisfies its service specification. If an implementation specification does not satisfy its service specification, it is necessary to find out the faults and correct them. In this paper, we present an efficient algorithm for verifying whether an implementation satisfies its service specification related by the testing equivalence and the reduction relation, and generating diagnostic information if an implementation does not satisfy its service specification, based on the transformation of the service specification into a special deterministic machine, called refusal graph, and the coupled product of the refusal graph and the implementation.

This paper describes the development of Tango, an automatic generator of backtracking trace analysis tools for single-process specifications written in the formal description language, Estelle. A tool generated by Tango automatically checks the validity of any execution trace against the given specification, and supports a number of checking options. The approach taken was to modify an Estelle-to-C++ compiler. Discussion about nondeterministic specifications, multiple observation points, and on-line trace analysis follow. Trace analyzers for the protocols LAPD and TP0 have been tested and performance results are evaluated. Issues in the analysis of partial traces are also discussed.

It is shown in this paper that the problem of deciding if a test suite generated from a finite state machine provides complete fault coverage can be converted into the problem of minimizing the test tree representing the test suite. A fault coverage analysis procedure, capable of deciding if a given test suite provides complete fault coverage in respect to a given FSM specification, is then developed. The core of this procedure is a state minimization procedure developed specifically for the class of FSMs whose graphic representations are trees. The fault coverage analysis procedure can cope with partially specified FSM specifications which need not be reduced and faults that increase the number of states up to a chosen upper bound. Two necessary and one sufficient conditions, which in some cases may simplify the fault coverage analysis, are also presented.>

Communication protocols are the rules that govern the communication between the different components within a distributed computer system. Since protocols are implemented in software and/or hardware, the question arises whether the existing hardware and software testing methods would be adequate for the testing of communication protocols. The purpose of this paper is to explain in which way the problem of testing protocol implementations is different from the usual problem of software testing. We review the major results in the area of protocol testing and discuss in which way these methods may also be relevant in the more general context of software testing.

We propose an automatic analysis and test case derivation method for LOTOS expressions with data values. We introduce the class of P-LOTOS expressions where the data types are restricted to Presburger arithmetic. That is, only the integer and Boolean types are used, and the operators of the integers are restricted to addition, subtraction, and comparison. For this class, we give an algorithm for deriving a set of test cases (a test suite). The algorithm is carried out by using a decision procedure for integer linear programming problems. We also give solutions for the deadlock detection problem, the detection of nonexecutable branches, and the detection of nondeterministic behaviors. We have implemented a tool for the analysis and test selection based on our techniques. The derivation of a test suite for a simplified Session protocol is described as an example.>

Presents a method of generating test sequences for concurrent programs and communication protocols that are modeled as communicating nondeterministic finite-state machines (CNFSMs). A conformance relation, called trace-equivalence, is defined within this model, serving as a guide to test generation. A test generation method for a single nondeterministic finite-state machine (NFSM) is developed, which is an improved and generalized version of the Wp-method that generates test sequences only for deterministic finite-state machines. It is applicable to both nondeterministic and deterministic finite-state machines. When applied to deterministic finite-state machines, it yields usually smaller test suites with full fault coverage than the existing methods that also provide full fault coverage, provided that the number of states in implementation NFSMs are bounded by a known integer. For a system of CNFSMs, the test sequences are generated in the following manner: a system of CNFSMs is first reduced into a single NFSM by reachability analysis; then the test sequences are generated from the resulting NFSM using the generalized Wp-method.>

The signal save construct is one of the features distinguishing SDL from traditional high-level specification and programming languages. However, this feature increases the difficulties of testing SDL-specified software. We present a testing approach consisting of the following three phases: SDL specifications are first abstracted into finite state machines with save constructs, called SDL-machines; the resulting SDL-machines are then transformed into equivalent finite state machines without save constructs if this is possible; and, finally, test cases are selected from the resulting finite state machines. Since there are many existing methods for the first and third phases, we mainly concentrate upon the second phase and come up with a method of transforming SDL-machines into equivalent finite state machines, which preserve the same input/output relationship as in the original SDL-machines. The transformation method is useful not only for testing but also for verifying SDL-specified software.>

The authors propose a generalized diagnostic algorithm for the case where more than one fault (output or transfer) may be present in one of the transitions of a deterministic system represented by a set of communicating finite state machines (CFSMs). Such an algorithm localizes the faulty transition in the distributed system once the fault has been detected. It generates, if necessary, additional diagnostic test cases which depend on the observed symptoms and which permit the location of the detected faults. The algorithm guarantees the correct diagnosis of any single or double fault (output and/or transfer) in at most one of the transitions of a deterministic system which is represented by a set of communicating FSMs. A simple example is used to demonstrate the functioning of the different steps of the proposed diagnostic algorithm.>

A model and a formal specification of the personal communication service obtained by the application of an object-oriented system design methodology is presented and described using the executable object-oriented specification language Mondel. The goal of developing a specification of PCS is primarily to introduce some structure and formalism in its description, which has so far been done informally, and also to provide a better understanding of its constituent elements and their interrelationships. As Mondel is an executable specification language, simulation is used to verify the basic functionality defined in this specification of PCs. Simulation using various scenarios also provides a means of presenting the different concepts of PCS.>

The authors propose a generalized diagnostic algorithm for the case where more than one fault (output and/or transfer) may be present in the transitions of a system represented by a deterministic finite state machine (FSM). If existing faults are detected, this algorithm permits the generation of a minimal set of diagnoses, each of which is formed by a set of transitions (with specific types of faults) suspected of being faulty. The occurrence in an implementation of all the faults of a given diagnosis allows the explanation of all observed implementation outputs. The algorithm guarantees the correct diagnosis of certain configurations of faults (output and/or transfer) in an implementation, which are characterized by a certain type of independence of the different faults. The authors also propose an approach for selecting additional test cases, which allows the reduction of the number of possible diagnoses. A simple example is used to demonstrate the different steps of the algorithm.>

An algorithm that localizes the faulty transition in a deterministic finite state machine (FSM) once the fault has been detected is presented. The diagnostic algorithm generates, if necessary, additional diagnostic test cases which depend on the observed symptom and which permit the location of the detected fault. The algorithm guarantees the diagnosis of any single fault in an FSM. An application example, explaining the functioning of the algorithm, is provided.>

It is noted that the evolution of specifications is necessary to accommodate the evolution of requirements and design decisions during the software development and maintenance process. The authors are concerned with formal description techniques that allow the development of executable specifications, especially executable object-oriented specifications of distributed systems. They propose a two-level model for the evolution of large object-oriented specifications. The first level deals with the dynamic modification of types (classes) while the second level deals with the modification of modules. To allow for dynamic modification of types and modules, the authors have developed a reflection-based technique using meta-objects in which the modification operations are defined. In their approach, they have defined a set of structural and behaviour constraints to ensure the specification consistency after its modification at both levels.>

Presents test selection criteria for Prolog programs which are based on control flow. The control flow in Prolog programs is not obvious because of the declarative nature of Prolog. The authors present two types of control flow graphs to represent the hidden control flow of Prolog programs explicitly. A fault model is developed for Prolog programs for guidance on test selection. Test selection criteria are given in terms of the coverage on these control flow graphs. Under the given fault model, the effectiveness of these criteria is analyzed in terms of fault detection capability of the test cases produced with these criteria.>

A method for the selection of appropriate test case, an important issue for conformance testing of protocol implementations as well as software engineering, is presented. Called the partial W-method, it is shown to have general applicability, full fault-detection power, and yields shorter test suites than the W-method. Various other issues that have an impact on the selection of a suitable test suite including the consideration of interaction parameters, various test architectures for protocol testing and the fact that many specifications do not satisfy the assumptions made by most test selection methods (such as complete definition, a correctly implemented reset function, a limited number of states in the implementation, and determinism), are discussed.>

The purpose of this study is to define principles that apply to the design of communication gateways between heterogeneous computer systems, and to identify strategies to solve incompatibilities in a systematic manner. The importance of communication service common properties is explored in detail. The modification of the service available for interworking due to subset selection and service concatenation is discussed. Various methods of adaptation are described. Two architectural options for the design of communication gateways are explored, namely, conversion at the service level or at the PDU (protocol data unit) level. While the former is conceptually simpler, various optimizations are possible through the latter approach. A method for deriving the specification of a protocol adapter from the two protocol specifications is given. All these issues are illustrated by a number of simple examples.>

Gateways are introduced for interworking between several, possibly heterogeneous, distributed computer systems. A gateway has to provide for the necessary adaptation between the communication protocols used in the interconnected networks. The adaptation problem is best handled by considering the communication services of the interconnected systems. Once the problem is solved at this level, the remaining problem of conversion between the incompatible communication protocols used in the different systems can be solved automatically, as demonstrated for the case of a simple example of data transmission service from a sender to a receiver process.>

The service specification concept has acquired an increasing level of recognition by protocol designers. This architectural concept influences the methodology applied to service and protocol definition. Since the protocol is seen as the logical implementation of the service, one can ask whether it is possible to formally derive the specification of a protocol providing a given service. This paper addresses this question and presents an algorithm for deriving a protocol specification from a given service specification. It is assumed that services are described by expressions, where names identifying both service primitives and previously defined services are composed using operators for sequence, parallelism and alternative. Services and service primitives may have input and output parameters. Composition of services from predefined services and service primitives is also permitted. The expression defining the service is the basis for the protocol derivation process. The algorithm presented fully automates the derivation process. Future work will focus on the optimization of traffic between protocol entities and on applications.

Previous papers describe an algorithm for deriving a specification of protocol entities from a given service specification. A service specification defines a particular ordering for the execution of service primitives at the different service access points using operators for sequential, parallel and alternative executions. The derived protocol entities ensure the correct ordering by exchanging appropriate synchronization messages, between one another through the underlying communication medium.

The authors explore a testing approach where the concern for selecting the appropriate test input provided to the implementation under test (IUT) is separated as much as possible from the analysis of the observed output. Particular emphasis is placed on the analysis of the observed interactions of the IUT in order to determine whether the observed input/output trace conforms to the IUT's specification. The authors consider this aspect of testing with particular attention to testing of communication protocol implementations. Various distributed test architectures are used for this purpose, where partial input/output traces are observable by local observers at different interfaces. The error-detection power of different test configurations is determined on the basis of the partial trace visible to each local observer and their global knowledge about the applied test case. The automated construction of trace analysis modules from the formal specification of the protocol is also discussed. Different transformations of the protocol specification may be necessary to obtain the reference specification, which can be used by a local or global observer for checking the observed trace. Experience with the construction of an arbiter for the OSI (open systems interconnection) transport protocol is described.>

Methods of limiting the impact of communication delays on the logical behavior of distributed systems are considered. It is assumed that a distributed system is described in terms of a number of interconnected modules, and each module is described in terms of its possible states and the possible state transitions. Transitions may be initiated spontaneously by a module and may give rise to output messages, which will be received, after some possible delay, by another module as an input. Otherwise, transitions may be initiated by received input. If the system has the property called regularity, its behavior is logically independent of the communication delays. A simple condition for regularity is given. This condition is the basis for the implementation of counter-based synchronization conditions in a distributed environment. Weaker forms of regularity, which make abstraction of internal operations invisible from the point of view of an outside observer, are also considered. The application of these concepts to the design of module interfaces involving 'collisions' and to communication including timeouts is discussed in some detail with examples.>

The use of formal specifications in software development allows the use of certain automated tools during the specification and software development process. Formal description techniques have been developed for the specification of communication protocols and services. This paper describes the partial automation of the protocol implementation process based on a formal specification of the protocol to be implemented. An implementation strategy and a related software structure for the implementation of state transition oriented specifications is presented. Its application is demonstrated with a much simplified Transport protocol. The automated translation of specifications into implementation code in a high-level language is also discussed. A semiautomated implementation strategy is explained which highlights several refinement steps, part of which are automated, which lead from a formal protocol specifieation to an implementation. Experience with several full implementations of the OSI Transport protocol is described.

Formal description techniques (FDT's) are being developed for the specification of communication protocols and other distributed systems. Some of them (namely SDL and Estelle) are based on an extended state transition model and promote a "transition-oriented" specification style. Another one (namely Lotos) and most highlevel programming languages promote a style which is called "structured." The correspondence compares these two specification styles in the framework of rendezvous interactions between different system modules. The advantages of each of the two styles are discussed in relation with an example of a virtual ring mutual exclusion protocol. Transformation rules between the two approaches are given. An extension to the state transition oriented FDT's is also suggested in order to allow for a structured specification style.

Communication protocol testing can be done with a test architecture consisting of remote Lower Tester and local Upper Tester processes. For real protocols, tests can be designed based on the formal specification of the protocol which uses an extended finite state machine model. The specification is transformed into a simpler form consisting of normal form transitions. It can then be modeled by a control and a data flow graph. The graphs are decomposed into subtours and data flow functions, respectively. Tests are designed by considering parameter variations of the input primitives of each data flow function and determining the expected outputs. The methodology gives complete test coverage of all data flow functions and control paths in the specification. Functional fault models are proposed for functions that are not formally specified.

Article Free Access Share on Deriving protocol specifications from service specifications Authors: G von Bochmann Département d'IRO, Université de Montréal, C.P. 6128, Succursale A, Montréal, Québec, H3C 3J7, Canada Département d'IRO, Université de Montréal, C.P. 6128, Succursale A, Montréal, Québec, H3C 3J7, CanadaView Profile , R Gotzhein Département d'IRO, Université de Montréal, C.P. 6128, Succursale A, Montréal, Québec, H3C 3J7, Canada Département d'IRO, Université de Montréal, C.P. 6128, Succursale A, Montréal, Québec, H3C 3J7, CanadaView Profile Authors Info & Claims SIGCOMM '86: Proceedings of the ACM SIGCOMM conference on Communications architectures & protocolsSeptember 1986Pages 148–156https://doi.org/10.1145/18172.18190Published:01 August 1986Publication History 33citation398DownloadsMetricsTotal Citations33Total Downloads398Last 12 Months22Last 6 weeks4 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

Protocol testing for the purpose of certifying the implementation's adherence to the protocol specification can be done with a test architecture consisting of remote tester and local responder processes generating specific input stimuli, called test sequences, and observing the output produced by the implementation under test. It is possible to adapt test sequence generation techniques for finite state machines, such as transition tour, characterization, and checking sequence methods, to generate test sequences for protocols specified as incomplete finite state machines. For certain test sequences, the tester or responder processes are forced to consider the timing of an interaction in which they have not taken part; these test sequences are called nonsynchronizable. The three test sequence generation algorithms are modified to obtain synchronizable test sequences. The checking of a given protocol for intrinsic synchronization problems is also discussed. Complexities of synchronizable test sequence generation algorithms are given and complete testing of a protocol is shown to be infeasible. To extend the applicability of the characterization and checking sequences, different methods are proposed to enhance the protocol specifications: special test input interactions are defined and a methodology is developed to complete the protocol specifications.

The higher-level communication protocols in computer networks, such as belonging to the OSI Transport through Application layers, are usually considered to have an end-to-end significance, that is the entities executing the protocol reside at the two respective ends of the connection, close to the application users. This question of end-to-end significance was in particular an issue in the discussion of the meaning of acknowledgements in the Transport layer, and in the distinction between the OSI Network and Transport layers.

Various performance parameters are defined which characterize the quality of service offered by a layer of the OSI model. In particular the parameters for the Transport and Network are considered. The set of parameters are classified into:

Protocol testing for the purpose of certifying the implementation's adherence to the protocol specification can be done with an architecture which includes a remote Tester and a local Responder processes generating specific input stimuli called test sequences. It is possible to adapt test sequence generation methods of finite state machines, namely transition tour, characterization and checking sequence methods to generate test sequences for protocols specified as incomplete finite state machines. For certain test sequences, the Tester or Responder processes are forced to consider the timing of an interaction in which they have not taken part; these test sequences are called nonsynchronizable. The three test sequence generation algorithms are modified to obtain synchronizable test sequences. Checking the protocol designs for intrinsic synchronization problems is also discussed.

Specification methods for distributed systems is the underlying theme of this paper. A model of communicating processes with rendezvous interactions is assumed as a basis for the discussion. The possible interactions by a process, and the interconnection between several subprocesses within a process are specified using the concept of ports, which are specified separately. Step-wise refinement of process specifications and associated verification rules are considered. The step-wise refinement of port specifications and associated interactions is considered as well. After the presentation of an introductory example, the paper discusses the basic concepts of the specification method. They are then applied to more complex examples. The step-wise wefinement of ports and interactions is demonstrated by a hardware interface for which an abstract specification and a more detailed implementation is given. Proof rules for verifying the consistency of detailed and more abstract specifications are discussed in some detail.

The problem of elaborating the specification for the submodules of a system is considered.A new method for the construction of submodule specifications is described.If the system is to consist of n submodules and the system as well as (n -1) submodules are specified, then the method described determines the specification of the additional nth submodule.A formula is given which defines the specification of the additional submodule in the general case where module specifications are given in terms of sets of possible execution sequences, and interaction occurs when several modules participate in the execution of an atomic interaction.For the restricted context of finite-state machines, a constructive algorithm for the evaluation of the formula is given.The use of this design method is demonstrated by examples, including a simple communication protocol involving error detection and retransmission.Possible applications in other areas, as well as remaining problems, are indicated.

The use of temporal logic for the specification of hardware modules is explored. Temporal logic is an extension of conventional logic. While traditional logic is useful for specifying combinational circuits, it is shown how the extensions of temporal logic apply to the specification of memory, as well as the safeness and liveness properties of active circuits representing processes. These ideas are demonstrated by the example of a self-timed arbiter. An implementation of the arbiter is also given, and its formal verification by a kind of reachability analysis is discussed. This verification approach is also useful for finding design errors, as demonstrated by an example.

Experience with the use of formal descriptions of communication services and protocols is described. The paper focuses on the experience of the authors with the extended state transition model which is proposed as a standard formal description technique (FDT) for the services and protocols in the OSI environment. The first part of the paper refers to various example specifications, including transport protocol and service specifications, and discusses the suitability of the specification method and possible extensions. In the remaining part, the use of such formal specifications during the phases of system design, implementation, and testing is described. Various approaches to protocol design validation, implementation, and assessment of implementations are discussed, with emphasis on the last point. The experience with several of these approaches is described in the paper, and further details may be found in the references.

Different approaches have been used for the formal specification and verification of communication protocols. This paper explains the approach of nsing a general transition model which combines aspects of finite state transition diagrams and programming languages. Different ways of structuring a protocol into separate modules or functions are also discussed. The main part of the paper describes a method for exactly specifying the communication service provided by a protocol. Two aspects of a service specification are distinguished: 1) the local properties which characterize the interface through which the service may be accessed, and 2) the global properties which describe the "end-to-end" communication characteristics of the service. It is shown how the specification method is related to the general transition model for protocol specification. Verification is discussed briefly with emphasis on the use of invariant assertions in the context of finite state as well as programming language protocol descriptions. The discussed topics are demonstrated with examples based on the HDLC classes of procedures and the X.25 Virtual Circuit data transmission service.

While early protocol design efforts had to rely largely on seat-of-the-pants methods, a variety of more rigorous techniques have been developed recently. This paper surveys the formal methods being applied to the problems of protocol specification, verification, and implementation. In the specification area, both the service that a protocol layer provides to its users and the internal operations of the entities that compose the layer must be defined. Verification then consists of a demonstration that the layer will meet its service specification and that each of the components is correctly implemented. Formal methods for accomplishing these tasks are discussed, including state transition models, program verification, symbolic execution, and design rules.

This paper describes experience with an implementation of the X25 communication protocols for accessing public data networks. Ihe implementation effort is characterized by: 1) the development of a formalized protocol specification on which all further implementation work is based, and 2) the use of Concurrent Pascal as the implementation language. The main features of the formalized protocol specification are given, and a method for deriving a protocol implementation based on parallel processes, monitors, and classes is explained. The overall structure of the system and the step-wise refinements leading to the complete implementation are discussed. Some comments on the possible implementation on multiple microprocessors are also given.

The paper presents a compiler writing system which is believed to be portable and easily usable. Similar in philosophy to a bottom-up compiler writing system built previously, this system generates compilers for top-down syntax analysis. The system allows the use of regular expressions for the specification of the syntax of the language to be compiled, and the use of inherited and synthesised attributes for the specification of the semantics. The generated compilers are written in PASCAL. The second part of the paper discusses the system in view of certain aspects that are important for the user of a compiler writing system. Among these aspects are discussed the coverage of different problem areas, such as lexical and syntactic analysis, specification of semantics, error treatment, etc. the simplicity and flexibility of the system's use, and the conciseness and readability of the compiler specification language. The portability of the system is obtained by using PASCAL as the implementation language, and as language for the generated compilers.

This paper discusses the problem of allocating storage for the activation records of procedure calls within a system of parallel processes. A compile time storage allocation scheme is given, which determines the relative address within the memory segment of a process for the activation records of all procedures called by the process. This facilitates the generation of an efficient run-time code. The allocation scheme applies to systems in which data and procedures can be shared among several processes. However, recursive procedure calls are not supported.

In view of the size and complexity of modern operating systems, this paper proposes their subdivision into a set of smaller functional modules and the implementation of a number of their functions on separate hardware processors. The information transfer requirements resulting from physically separated system components are examined and the adaptation of a standard end-to-end protocol is suggested for an efficient solution to the interprocess communication problems.