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).

CPU and device virtualization technology allows applications to be hosted on cloud platforms; some of the resulting benefits are lower cost and greater elasticity. In such cloud hosted applications, some components reside on the cloud while others, such as end users and components tied to physical devices, are located outside the cloud. Many applications, e.g., telecom services, have stringent latency requirements in terms of within how much time certain procedures must be completed. The application latency is strongly determined by the locations of all the interacting components that are both within and outside the cloud. In this paper, we study the problem of determining the optimal placement of the application components in the cloud so that the latency requirements of the application can be met. We present a precise formulation of the placement problem which includes a specification of the cloud platform, and collective latency expressions for application-level latency requirements. We show that Message Sequence Charts (MSCs), a widely-used mechanism for describing the execution of application procedures, can be naturally translated into our formalism of collective latency expressions. We present placement algorithms that exploit the Euclidean triangular inequality property of network topologies: (a) an exact algorithm for determining the most optimal placement but which has a worst-case exponential running time, and (b) an algorithm for determining a close to-optimal placement that has a fast polynomial running time. Additionally, we present an exact technique for partitioning a placement problem into smaller sub problems so that greater efficiency and accuracy can be achieved. We evaluate the performance of the algorithms on a representative telecom application --- a distributed deployment of the LTE Mobility Management Entity (MME). Our evaluation results show that our approximate algorithm can outperform a random placement by up to 49% for finding a successful placement.

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.

Many topology discovery systems rely on traceroute to discover path information in public networks. However, for some routers, traceroute detects their existence but not their address; we term such routers anonymous routers. This paper considers the problem of inferring the network topology in the presence of anonymous routers. We illustrate how obvious approaches to handle anonymous routers lead to incomplete, inflated, or inaccurate topologies. We formalize the topology inference problem and show that producing both exact and approximate solutions is intractable. Two heuristics are proposed and evaluated through simulation. These heuristics have been used to infer the topology of the 6Bone, and could be incorporated into existing tools to infer more comprehensive and accurate topologies.

Increased platform heterogeneity and varying resource availability in distributed systems motivates the design of resource-aware applications, which ensure a desired performance level by continuously adapting their behavior to changing resource characteristics. In this paper, we describe an application-independent adaptation framework that simplifies the design of resource-aware applications. This framework eliminates the need for adaptation decisions to be explicitly programmed into the application by relying on two novel components: (1) a tunability interface, which exposes adaptation choices in the form of alternate application configurations while encapsulating core application functionality, and (2) a virtual execution environment, which emulates application execution under diverse resource availability enabling off-line collection of information about the resulting behavior. Together, these components permit automatic run-time decisions on when to adapt by continuously monitoring resource conditions and application progress, and how to adapt by dynamically choosing the application configuration that is most appropriate for the prescribed user preference. We evaluate the framework using an interactive distributed image visualization application. The framework permits automatic adaptation to changes in CPU load and network bandwidth by choosing a different compression algorithm or by controlling the image transmission sequence so as to satisfy user preferences of visualization quality and timeliness.