34167551
A Lower Bound for Permutation Routing on Two-Dimensional Bused Meshes
We prove a 0.691n lower bound for the permutation routing problem in n×n meshes with row and column buses whose propagation delay is one time unit. For meshes having non-unit-time buses, we use similar arguments to derive some simple lower bounds for the permutation routing problem.
42848873
Time Lower Bounds for Permutation Routing on Multi-Dimensional Bused Meshes
We present time lower bounds for the permutation routing problem on three- and higher-dimensional n x…x n meshes with buses. We prove an (r–1)n/r lower bound for the general case of an r-dimensional bused mesh, r≥2, which is not as strong for low-dimensional as for higher-dimensional cases. We then use a different approach to construct a 0.705n lower bound for the three-dimensional case.
6490713
An Architecture for an Adaptive Intrusion-Tolerant Server
We describe a general architecture for intrusion-tolerant enterprise systems and the implementation of an intrusion-tolerant Web server as a specific instance. The architecture comprises functionally redundant COTS servers running on diverse operating systems and platforms, hardened intrusion-tolerance proxies that mediate client requests and verify the behavior of servers and other proxies, and monitoring and alert management components based on the EMERALD intrusion-detection framework. Integrity and availability are maintained by dynamically adapting the system configuration in response to intrusions or other faults. The dynamic configuration specifies the servers assigned to each client request, the agreement protocol used to validate server replies, and the resources spent on monitoring and detection. Alerts trigger increasingly strict regimes to ensure continued service, with graceful degradation of performance, even if some servers or proxies are compromised or faulty. The system returns to less stringent regimes as threats diminish. Servers and proxies can be isolated, repaired, and reinserted without interrupting service.
18650610
Modeling multistep cyber attacks for scenario recognition
Efforts toward automated detection and identification of multistep cyber attack scenarios would benefit significantly from a methodology and language for modeling such scenarios. The Correlated Attack Modeling Language (CAML) uses a modular approach, where a module represents an inference step and modules can be linked together to detect multistep scenarios. CAML is accompanied by a library of predicates, which functions as a vocabulary to describe the properties of system states and events. The concept of attack patterns is introduced to facilitate reuse of generic modules in the attack modeling process. CAML is used in a prototype implementation of a scenario recognition engine that consumes first-level security alerts in real time and produces reports that identify multistep attack scenarios discovered in the alert stream.
10409164
Denial of service against the Domain Name System
Because many network services rely on the Domain Name System, denial-of-service attacks against it can be particularly damaging. This article analyzes such threats and reviews existing and proposed countermeasures for addressing them.
14602428
A formal-specification based approach for protecting the domain name system
Many network applications depend on the security of the domain name system (DNS). Attacks on the DNS can cause denial of service and entity authentication to fail. In our approach, we use formal specifications to characterize DNS clients and DNS name servers, and to define a security goal. A name server should only use DNS data that is consistent with data from name servers that manage the corresponding domains (i.e. authoritative name servers). To enforce the security goal, we formally specify a DNS wrapper that examines the incoming and outgoing DNS messages of a name server to detect messages that could cause violations of the security goal, cooperates with the corresponding authoritative name servers to diagnose those messages, and drops the messages that are identified as threats. Based on the wrapper specification, we implemented a wrapper prototype and evaluated its performance. Out experiments show that the wrapper incurs reasonable overhead and is effective against DNS attacks such as cache poisoning and certain spoofing attacks.
9354416
Verification of liveness properties using compositional reachability analysis
The software architecture of a distributed program can be represented by a hierarchical composition of subsystems, with interacting processes at the leaves of the hierarchy. Compositional reachability analysis (CRA) is a promising state reduction technique which can be automated and used to derive in stages the overall behaviour of a distributed program based on its architecture. Conventional CRA however has a limitation. The properties available for analysis after composition and reduction are constrained by the set of actions that remain globally observable. The liveness properties which involve internal actions of subsystems may therefore not be analysed. In this paper, we extend compositional reachability analysis to check liveness properties which may involve actions that are not globally observable. In particular, our approach permits the hiding of actions independently of the liveness properties that are to be verified in the final graph. In addition, it supports the simultaneous checking of multiple properties (both liveness and safety), and identifies those properties that are violated. The effectiveness of the extended technique is illustrated using a case study of a Reliable Multicast Transport Protocol (RMTP) with over 96,000 states and 660,000 transitions.
1708697
Enhancing compositional reachability analysis with context constraints
Compositional techniques have been proposed for traditional reachability analysis in order to introduce modularity and to control the state explosion problem. While modularity has been achived, state explosion is still a problem. Indeed, this problem may even be exacerbated as a locally minimised subsystem may contain many states and transitions forbidden by its context or environments. This paper presents a method to alleviate this problem effectively by including context constraints in local subsystem minimisation. The global behaviour generated using the method is observationally equivalent to that generated by compositional reachability analysis without the inclusion of context constraints.Context constraints, specified as interface processes, are restrictions imposed by the environment on subsystem behaviour. The minimisation produces a simplified machine that describes the behaviour of the subsystem constrained by its context. This machine can also be used as a substitute for the original subsystem in the subsequent steps of the compositional reachability analysis. Interface processes capturing context constraints can be specified by users or automatically constructd using a simple algorithm. The concepts in the paper are illustrated with a clients/server system.
37251779
Integrating heterogeneous Web services with WebXcript
Despite recent uprising of the Web services technology for programmed interfaces of business-to-business (B2B) e-commerce services (e-services) over the Internet, most sites (e.g., online purchases) can only support Hypertext Markup Language (HTML) for human interactions through Web browsers. Automating client access to these services generally requires developing sophisticated programs to simulate human access by handling HTML pages and forms. However, these HTML interfaces vary across Web sites, and are often subjected to changes. Client maintenance is therefore tedious and expensive. This paper presents a novel approach to automate dialogs with Web-based services, using a high-level script language, called WebXcript. WebXcript provides features for HTML forms based dialogues and XML messaging. The XML syntax of WebXcript further enables convenient user authoring and easy engine development with extensively available XML tools. It supports expected responses and exception handling. We further propose a wrapper architecture to integrate heterogeneous Web services based on WebXcript. We demonstrate the applicability of our approach with examples in integrating distributed information, online ordering, and XML messaging.
8159009
A Three-Layer Framework for Cross-Organizational e-Contract Enactment
In an e-commerce environment, contracts are important for attaining business process interoperability and enforcing their proper enactment. An e-contract is the computerized facilitation or automation of a contract in a cross-organizational business process. We find that e-contract facilitation can be divided into multiple levels and perspectives, which has not been adequately addressed before. In this paper, we present a framework for e-contract enactment with three layers, viz., business layer, structural layer, and implementation layer. In the business layer, e-contracts are defined through analyzing the contract clauses to business rules and business entities. In the structural layer, requirements for the E-contract enactment workflow are elucidated through requirement analysis to cover both static and dynamic aspects. In the implementation layer, workflows and cross-organizational interoperating interfaces are implemented using contemporary Enterprise Java Bean and Web services. In this paper, we present the methodology and process for engineering the functional aspects of e-contracts from high-level business-view down to implementation layer based on this framework, illustrated with an investment example. The framework allows an e-contract to be seamlessly defined and enacted. The framework is modeled in UML.
15410506
Fast similarity search on video signatures
Video signatures are compact representations of video sequences designed for efficient similarity measurement. In this paper, we propose a feature extraction technique to support fast similarity search on large databases of video signatures. Our proposed technique transforms the high dimensional video signatures into low dimensional vectors where similarity search can be efficiently performed. We exploit both the upper and lower bounds of the triangle inequalities in approximating the high-dimensional metric, and combine this approximation with the classical PCA to achieve the target dimension. Experimental results on a large set of Web video sequences show that our technique outperforms fastmap, Haar wavelet, PCA, and triangle-inequality pruning.