Public camera feeds are increasingly being opened to use by multiple authorities (e.g., police, fire, traffic) as well as to the public. Because of the difficulty and insecurity of sharing cryptographic keys, these data are available in the clear. However, authorities must have a mechanism to assure trust in the video, that is, to authenticate it. While lossless video is straightforward to authenticate by cryptographic means, lossy video as may result from UDP, wireless, or transcoded transmissions, is more difficult to authenticate. We describe a method that combines a concise and efficiently computed video fingerprint with public key cryptography. Essential components of our approach are: the procedure to combine inexact video fingerprint with exact digital signature to enable lossy authentication, and matching for misaligned video via a major incline approach. Experimental results relate video fingerprint length to authentication accuracy and latency (time to authentication).

This paper introduces a method for the efficient comparison and retrieval of near duplicates of a query video from a video database. The method generates video signatures from histograms of orientations of optical flow of feature points computed from uniformly sampled video frames concatenated over time to produce time series, which are then aligned and matched. Major incline matching, a data reduction and peak alignment method for time series, is adapted for faster performance. The resultant method is compact and robust against a number of common transformations including: flipping, cropping, picture-in-picture, photometric, addition of noise and other artifacts. We evaluate on the MUSCLE VCD 2007 dataset and a dataset derived from TRECVID 2009. Good precision (average 88.8%) at significantly higher speeds (average durations: 45 seconds for signature generation plus 92 seconds for a linear search of 81-second query video in a 300 hour dataset) than results reported in the literature are shown.

Various methods of content-based video copy detection have been proposed to find video copies in a large video database. In this paper, we represent video feature obtained by global and/or local detectors as signature time series. We observe that the curves of such time series under various kinds of modifications and transformations follow similar trends. Based on this observation, we propose to use linear segmentation to approximate the time series and extract major inclines from those linear segments. We develop a major incline-based fast alignment method to find potential alignment positions between the compared videos. Further, taking advantage of the major incline-based fast alignment, a Frame Insertion, Deletion, and Substitutions (FIDS) detection method is introduced to detect video copies in the presence of frame order changes. Our proposed solution is simple and generic. It can be combined with existing global or local feature descriptions, and with sequence or keyframe based matching schemes. It speeds up the video copy detection process by reducing the search space to the areas suggested by the potential alignments. Experiments using both the MUSCLE VCD 2007 and TRECVID CBCD 2009 datasets show that the proposed solution significantly accelerates the overall video copy detection process and at the same time achieves good precision.

Cloud platforms enable enterprises to lease computing power in the form of virtual machines. An important problem for such enterprise users is to understand how many and what kinds of virtual machines will be needed from clouds. We formulate demand for computing power and other resources as a resource allocation problem with multiplicity, where computations that have to be performed concurrently are represented as tasks and a later task can reuse resources released by an earlier task. We show that finding a minimized allocation is NP-complete. This paper presents an approximation algorithm with a proof of its approximation bound that can yield close to optimum solutions in polynomial time. Enterprise users can exploit the solution to reduce the leasing cost and amortize the administration overhead (e.g., setting up VPNs or configuring a cluster). Cloud providers may utilize the solution to share their resources among a larger number of users.

Batch resource allocation problem arises in the context of executing a sequence of automated system tests or distributed computations where resources are pooled together and flexibly matched with requests. Minimizing resource allocation for a batch of processes reduces the resource management (e.g., setup) cost for the batch while allowing more users to share the resource pool simultaneously. The salient characteristic of the batch resource allocation problem is that while resources can be reused across different processes they are subject to mutually exclusive use for any individual process. We show that resource allocation for a single process can be solved in polynomial time whereas the general optimization problem is NP-complete. This motivates us to consider heuristics that can yield close to optimum solutions in polynomial time. We design several such heuristics and present their experimental comparison. Our experiments show that a technique based on a min-cost max-flow algorithm combined with ranked removal yields the best solution while having smallest running time.

System-level test automation emulates testers' interactions with a System Under Test (SUT) to verify system properties. It is usually achieved through writing scripts in scripting languages, such as Perl or Tel, in order to feeding input to and correlating data from various interfaces of SUT. Test scripts, especially ones requiring thorough results analysis, can easily become complicated and hard to maintain as the software system evolves. ATTEST is a toolkit to address problems in test automation and maintenance. It provides easy-to-use mechanisms for helping testers to write and maintain automated test scripts through describing system behaviors at a high abstract level. It includes a Test Behavior Language (TBL) that uses innovative parameterized patterns to specify and validate trace-based properties abstractly but precisely. A compiler translates TBL specifications into executable scripts. Initial results show that TBL specifications range from 1/2 to 1/5 the size of their script counterparts and can save up to 5 times effort for developing test scripts. TBL demonstrates greater benefit as the complexity of the validation increases.

Execution traces produced by software systems during their operation can capture important runtime information, and thus are valuable sources for validating software functional properties. Automating the validation of such properties is currently achieved by writing test scripts, where most of the effort focuses on programming operations rather than specifying properties clearly. Improving this practice calls for domain-specific languages that can capture properties exhibited in traces at a higher abstract level.

Most documented efforts in fault-tolerant computing address the problem of recovering from failures that occur during normal system operation. To bring a system to a point where it can begin performing its duties first requires that the system successfully complete initialization. Large-scale distributed systems may take hours to initialize. For such systems, a key challenge is tolerating failures that occur during initialization, while still completing initialization in a timely manner. In this paper, we present a dependable initialization model that captures the architecture of the system to be initialized, as well as interdependencies among system components. We show that overall system initialization may sometimes complete more quickly if recovery actions are deferred as opposed to commencing recovery actions as soon as a failure is detected. This observation leads us to introduce a recovery decision function that dynamically assesses when to take recovery actions. We then describe a dependable initialization algorithm that combines the dependable initialization model and the recovery decision function for achieving fast initialization. Experimental results show that our algorithm incurs lower initialization overhead than that of a conventional initialization algorithm. This work is the first effort we are aware of that formally studies the challenges of initializing a distributed system in the presence of failures.

Building dependable distributed systems from commercial off-the-shelf components is of growing practical importance. For both cost and production reasons, there is interest in approaches and architectures that facilitate building such systems. The AQuA architecture is one such approach; its goal is to provide adaptive fault tolerance to CORBA applications by replicating objects. The AQuA architecture allows application programmers to request desired levels of dependability during applications' runtimes. It provides fault tolerance mechanisms to ensure that a CORBA client can always obtain reliable services, even if the CORBA server object that provides the desired services suffers from crash failures and value faults. AQuA includes a replicated dependability manager that provides dependability management by configuring the system in response to applications' requests and changes in system resources due to faults. It uses Maestro/Ensemble to provide group communication services. It contains a gateway to intercept standard CORBA IIOP messages to allow any standard CORBA application to use AQuA. It provides different types of replication schemes to forward messages reliably to the remote replicated objects. All of the replication schemes ensure strong, data consistency among replicas. This paper describes the AQuA architecture and presents, in detail, the active replication pass-first scheme. In addition, the interface to the dependability manager and the design of the dependability manager replication are also described. Finally, we describe performance measurements that were conducted for the active replication pass-first scheme, and we present results from our study of fault detection, recovery, and blocking times.

Building large-scale distributed object-oriented systems that provide multidimensional quality of service (QoS) in terms of fault tolerance, scalability, and performance is challenging. In order to meet this challenge, we need an architecture that can ensure that applications' requirements can be met while providing reusable technologies and software solutions. This paper describes techniques, based on the AQuA architecture, that enhance the applications' dependability and scalability by introducing two types of group members and a novel passive replication scheme. In addition, we describe how to make the management structure itself dependable by using the passive replication scheme. Finally, we provide performance measurements for the passive replication scheme.

The AQuA architecture provides adaptive fault tolerance to CORBA applications by replicating objects and providing a high-level method that an application can use to specify its desired level of dependability. This paper presents the algorithms that AQUA uses, when an application's dependability requirements can change at runtime, to tolerate both value faults in applications and crash failures simultaneously. In particular, we provide an active replication communication scheme that maintains data consistency among replicas, detects crash failures, collates the messages generated by replicated objects, and delivers the result of each vote. We also present an adaptive majority voting algorithm that enables the correct ongoing vote while both the number of replicas and the majority size dynamically change. Together, these two algorithms form the basis of the mechanism for tolerating and recovering from value faults and crash failures in AQuA.

Dependable distributed systems are difficult to build. This is particularly true if they have dependability requirements that change during the execution of an application, and are built with commercial off-the-shelf hardware. In that case, fault tolerance must be achieved using middleware software, and mechanisms must be provided to communicate the dependability requirements of a distributed application to the system and to adapt the system's configuration to try to achieve the desired dependability. The AQuA architecture allows distributed applications to request a desired level of availability using the Quality Objects (QuO) framework and includes a dependability manager that attempts to meet requested availability levels by configuring the system in response to outside requests and changes in system resources due to faults. The AQuA architecture uses the QuO runtime to process and invoke availability requests, the Proteus dependability manager to configure the system in response to faults and availability requests, and the Ensemble protocol stack to provide group communication services. Furthermore, a CORBA interface is provided to application objects using the AQuA gateway. The gateway provides a mechanism to translate between process-level communication, as supported by Ensemble, and IIOP messages, understood by Object Request Brokers. Both active and passive replication are supported, and the replication type to use is chosen based on the performance and dependability requirements of particular distributed applications.