15843617
Routing with Locality on Meshes with Buses
Routing with locality is studied for meshes with buses. In this problem, packets' distances are bounded by a value,d, which is less than the diameter of the network. This problem arises naturally when specific known algorithms are implemented on meshes. Solving this problem in ordinary meshes requires at least a routing time ofdsteps. To do better than this, we propose adding a kind of short bus to ordinary meshes. By using a technique which we call iterative walk-and-ride, we show how the routing time can be reduced by approximately one-third for solving the problem (including the multipacket version) on one- and two-dimensional short-bus meshes. The bounds we develop are tight.
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.
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.
8305500
Efficient video similarity measurement and search
We consider the use of meta-data and/or video-domain methods to detect similar videos on the Web. Meta-data is extracted from the textual and hyperlink information associated with each video clip. In the video domain, we apply an efficient similarity detection algorithm called video signature. The idea is to form a signature for each clip by selecting a small number of its frames that are most similar to a set of random seed images. We then apply a statistical pruning algorithm to allow fast detection on very large databases. Using a small ground-truth set, we achieve 90% recall and 95% precision using only 8% of the total number of operations required without pruning. For a database of around 46,000 video clips crawled from the Web, the video signature technique significantly outperforms meta-data in precision and recall. We show that even better performance can be achieved by combining them together. Based on our measurements, each video clip in our database has, on average, 1.53 similar copies.
15472127
An integrated method for effective behaviour analysis of distributed systems
Behavioral analysis is a valuable aid for the design and maintenance of well-behaved distributed systems. Dataflow and reachability analyses are two orthogonal, but complementary, behavioral analysis techniques. Individually, each of these techniques may be inadequate for the analysis of large-scale distributed systems. On the one hand, dataflow analysis algorithms, while tractable, may not be sufficiently accurate to provide meaningful detection of errors. On the other hand, reachability analysis, while providing exhaustive analysis, may be computationally too expensive for complex systems. In this paper, we present a method which integrates dataflow and reachability analysis techniques to provide a flexible and effective means for analysing distributed systems at the preliminary and final design stages respectively. We also describe some effective measures taken to improve the adequacy of the individual analysis techniques using the concepts of action dependency and context constraints. A prototype supporting the method has been built, and its performance is described in this paper. A realistic example of a distributed track control system is used as a case study.<<ETX>>
40916031
Stress Testing of Distributed Multimedia Software Systems
With the advance in network technologies, the use of distributed multimedia data has become very popular. Distributed multimedia systems are complex and error prone. While there are well established testing techniques for the functionalities of such systems, the technique of stress testing to improve test efficiency has not received much attention. It has been argued that faults are more likely to occur in situations where there is a fierce competition for resources. When the system is heavily loaded, errors like mismanagement of buffers can be easily identified. In this paper, we present several criteria for selecting test cases, and describe two methods for generating test cases which maximize system resource usage. Our approach is based on symbolic execution and constraint solving. An example is given to illustrate the concepts and techniques.
10130400
A commutative encrypted protocol for the privacy protection of watermarks in digital contents
Analysis by Forrester research revealed that 18% of global exports will flow online in 2004 and that the volume of e-commerce will surpass $400 billion. Digital rights protection is a major issue in the e-commerce of multimedia contents. Watermarking technology has been proposed as a promising enabling technology for the rights protection of multimedia digital contents. A unique watermark is embedded in each piece of multimedia contents before it is distributed to a customer. When unauthorized copies of a piece of contents are found, the customer who owns the contents can be readily identified by means of the embedded watermark. However, the unauthorized copies may also come from the content provider itself. It is therefore a challenging problem to determine whether an unauthorized copy is distributed by an unethical customer or by an unethical content provider. In this paper, we propose a watermarking protocol to address the problem using cryptographic technologies. Our protocol employs a commutative encryption algorithm to protect the privacy of watermarks. Information is doubly locked by two encryption keys kept separately by a customer and a content provider. In the protocol, a customer only gets a piece of watermarked multimedia contents in a transaction and the content provider has no idea how the watermark is formed. This facilitates the authority to determine the unethical party in case of unauthorized distribution of digital contents. We also discuss a couple of common attacks and show that our protocol can defend successfully against them.
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.