Conventional datacenters, based on wired networks, entail high wiring costs, suffer from performance bottlenecks, and have low resilience to network failures. In this paper, we investigate a radically new methodology for building wire-free datacenters based on emerging 60-GHz radio frequency (RF) technology. We propose a novel rack design and a resulting network topology inspired by Cayley graphs that provide a dense interconnect. Our exploration of the resulting design space shows that wireless datacenters built with this methodology can potentially attain higher aggregate bandwidth, lower latency, and substantially higher fault tolerance than a conventional wired datacenter while improving ease of construction and maintenance.

Conventional datacenters, based on wired networks, entail high wiring costs, suffer from performance bottlenecks, and have low resilience to network failures. In this paper, we investigate a radically new methodology for building wire-free datacenters based on emerging 60GHz RF technology. We propose a novel rack design and a resulting network topology inspired by Cayley graphs that provide a dense interconnect. Our exploration of the resulting design space shows that wireless datacenters built with this methodology can potentially attain higher aggregate bandwidth, lower latency, and substantially higher fault tolerance than a conventional wired datacenter while improving ease of construction and maintenance.

When lock-based parallel programs execute on conventional multi-core hardware, faulty software can cause hard-to-debug race conditions in critical sections that violate the contract between locks and their protected shared variables. This paper proposes new hardware support for enforcing isolation of critical section execution. It can detect and tolerate races, allowing programs to execute race-free. Our hardware scheme targets the existing large code base of locked-based parallel programs written in type unsafe languages such as C and C++. Our approach works directly on unmodified executables. An evaluation of 13 programs from the SPLASH2 and PARSEC suites shows that the cost of the additional hardware and the impact on the overall execution time is minimal for these applications. Our mechanism is complementary to hardware transactional memory in that it uses similar structures but focuses on enhancing the reliability of existing lock-based programs.

A new technology breakthrough which allows any standard Bluetooth mobile phone to access information services using the same selective and deliberate gesture envisioned for NFC. This technology is called Bluetooth Touchpoint, and it consists of reconfigurable coverage that combines NFC-like, close-proximity communications with the long-range, roaming solution of today's Bluetooth devices. Phase shifting technology combined with a unique antenna configuration makes this realization possible. Therefore, as the world moves toward contactless, wireless communication links, it is believed that the near ubiquity of Bluetooth in mobile devices makes this technology an excellent choice for delivering the benefits of NFC today without the wait, effort and cost associated with adopting NFC globally.

We introduce ToleRace, a runtime system that allows programs to detect and even tolerate asymmetric data races. Asymmetric races are race conditions where one thread correctly acquires and releases a lock for a shared variable while another thread improperly accesses the same variable. ToleRace provides approximate isolation in the critical sections of lock-based parallel programs by creating a local copy of each shared variable when entering a critical section, operating on the local copies, and propagating the appropriate copies upon leaving the critical section. We start by characterizing all possible interleavings that can cause races and precisely describe the effect of ToleRace in each case. Then, we study the theoretical aspects of an oracle that knows exactly what type of interleaving has occurred. Finally, we present software implementations of ToleRace and evaluate them on multithreaded applications from the SPLASH2 and PARSEC suites.

The quality of results to Web search queries is substantially limited because of the cost and short processing times allowed at search engine's data center to retrieve relevant pages, augment ads, and present them to the end-user. We tackle such an i

When logging onto a remote server, s, from a distrusted terminal, c, one can leak secrets such as passwords and account data to malware. To address this problem, we rely on a trusted personal device, p, as the interface available to users for entering their login credentials. In our proposal, p would send the credentials to s using a tunneled TLS session routed via c. The tunneling would be done within an existing TLS session established between c and s. Upon validating the credentials, s would enable c to access the user account. Consequently, c would never see in plain-text user's credentials. As a powerful application, we show that p could use our protocol to execute a credit-card-like payment at a point-of-sale terminal, c, using an account managed by the card-issuing bank, s.

We explore several local and global strategies for adaptive scan ordering of transform coefficients in JPEG XR/HD Photo. This codec applies a global adaptive scan-order heuristic with respect to an effective localized predictor. The global ordering heuristic, although simple, performs as well as localized techniques that are computationally significantly more complex. We conclude that effective localized prediction not only minimizes but also essentially randomizes coefficient residuals, so that a global statistic is sufficient to deliver near-optimal compression performance.

In this paper we analyze practical issues related to an adversarial inversion of biometric templates constructed without any cryptographically-secure protection features. The inversion in most cases is considered an ill-defined problem as the template captures only a small subset of the physical presence of a specific biometric trait. We apply our practical approach to an existing iris-based biometric system and demonstrate that “inverted” iris images pass matching tests even when encoded like barcodes.

Reputation in online economic systems is typically quantified using counters that specify positive and negative feedback from past transactions and/or some form of transaction network analysis that aims to quantify the likelihood that a network user will commit a fraudulent transaction. These approaches can be deceiving to honest users from numerous perspectives. We take a radically different approach with the goal of guaranteeing to a buyer that a fraudulent seller cannot disappear from the system with profit following a set of fabricated transactions that total a certain monetary limit. Even in the case of stolen identity, such an adversary cannot produce illegal profit unless a buyer decides to pay over the suggested limit.

Because data races represent a hard-to-manage class of errors in concurrent programs, numerous approaches to detect them have been proposed and evaluated. We specifically consider asymmetric races, a subclass of all race conditions, where a programmer’s thread correctly acquires and releases a lock for a given variable, while another thread causes a race by improperly accessing this variable. We introduce ToleRace, a runtime system that allows programs to either tolerate or detect asymmetric races based on local replication of shared state. ToleRace provides an approximation of atomicity in critical sections by creating local copies of shared variables when a critical section is entered and propagating the appropriate copy when the critical section is exited. We characterize the possible interleavings that can cause races and precisely describe the effect of ToleRace in each case. We study the theoretical aspects of an oracle that knows exactly what type of interleaving has occurred. Then, we present a software implementation of ToleRace on top of a dynamic instrumentation tool. We evaluate our implementation on multithreaded applications from the SPLASH2 and PARSEC suites and show that its overhead is acceptable, i.e., a factor of two on average.

We propose a simple, user-friendly tool which aims to offer comparative shopping to the consumer with minimal distraction. The key idea is to detect whether a specific Web-page is commercial, i.e., whether it sells an individual product or service. The detection is performed in real-time at the client with focus on exceptionally low false positives. For each commercial page, we identify the product name $P$ from its hypertext and send $P$ to a knowledge server which responds with a list $\mathbb{L}$ of URLs at which $P$ is sold in increasing order of pricing. The browser then presents $\mathbb{L}$ in an non-invasive fashion to the user, resulting in a simple and effective shopping experience. We present certain statistical properties of collected commercial Web-pages, introduce a novel classifier for Boolean spaces, and compare its performance to SVM-QP.

Reputation in on-line economic systems is typically quantified using counters that specify positive and negative feedback from past transactions and/or some form of transaction network analysis that aims to quantify the likelihood that a network user will commit a fraudulent transaction. These approaches can be deceiving to honest users from numerous perspectives. We take a radically different approach with a goal to guarantee to a buyer that a seller cannot disappear from the system with profit following a set of transactions that total a certain monetary limit. Even in the case of stolen identity, an adversary cannot produce illegal profit unless a buyer decides to pay over the suggested sales limit.

Results to Web search queries are ranked using heuristics that typically analyze the global link topology, user behavior, and content relevance. We point to a particular inefficiency of such methods: information redundancy. In queries where learning about a subject is an objective, modern search engines return relatively unsatisfactory results as they consider the query coverage by each page individually, not a set of pages as a whole. We address this problem using essential pages. If we denote as $\mathbb{S}_Q$ the total knowledge that exists on the Web about a given query $Q$, we want to build a search engine that returns a set of essential pages $E_Q$ that maximizes the information covered over $\mathbb{S}_Q$. We present a preliminary prototype that optimizes the selection of essential pages; we draw some informal comparisons with respect to existing search engines; and finally, we evaluate our prototype using a blind-test user study.

High fidelity is a demanding requirement for data hiding, especially for images with artistic or medical value. This correspondence proposes a high-fidelity image watermarking for annotation with robustness to moderate distortion. To achieve the high fidelity of the embedded image, we introduce a visual perception model that aims at quantifying the local tolerance to noise for arbitrary imagery. Based on this model, we embed two kinds of watermarks: a pilot watermark that indicates the existence of the watermark and an information watermark that conveys a payload of several dozen bits. The objective is to embed 32 bits of metadata into a single image in such a way that it is robust to JPEG compression and cropping. We demonstrate the effectiveness of the visual model and the application of the proposed annotation technology using a database of challenging photographic and medical images that contain a large amount of smooth regions.

Financial efficiency is the premier performance measure for most systems. Existing economic ecosystems for distribution of multimedia leave a lot to be desired: client-server platforms do not scale well resulting in substantial operational costs, whereas peer-to-peer platforms cannot police copyright control and are thus notorious for not being able to capitalize on its vast delivery potential. In this paper, we introduce an economic model that aims at predicting financial performance of both client-server and viral distribution systems for multimedia. The model consists of several probabilistic components: a global scale-free viral network of users and a localized user-behavior model that abstracts marketing, pricing, and executed transactions. The model uses simulation to predict relative economic behavior. In order to showcase our model, we compared the popular "on-line store" distribution system to the recently proposed off-line incentive-based viral ecosystem for multimedia. We also constructed an efficient dynamic pricing scheme and evaluated its performance in considered multimedia distribution scenarios.

In our paper “Coping with Viral Diversity in HIV Vaccine Design” [1], we presented several approaches to incorporate viral variability within vaccine immunogens, including judicious choice of natural strains. Most of our approaches included at least one collinear gene length corresponding to the Center-of-Tree (COT) sequence, which has near-optimal peptide coverage for a single gene. Inclusion of a COT sequence and optimizing the rest of the immunogen for coverage, as suggested in [2], yielded a construct (COT+) with the greatest coverage of peptide diversity, minimally sacrificing peptide coverage in comparison with unconstrained diversity optimization. Fischer et al. [3] introduced mosaics—a different approach to increasing coverage while maintaining collinearity using an optimization algorithm based on simulated recombination. In their response to Nickle et al. [1], Fischer et al. [4] suggest that maintaining full collinearity of viral gene sequences with native viral proteins is the only tractable approach to producing immunogens inclusive of viral variability. This claim was based on the observation that mosaics had slightly higher coverage than COT+ at 3× and 4× strain lengths, despite the fact that all mosaic components are constrained to be collinear with the full gene. However, as we pointed out, a variety of optimization algorithms can be used to perform coverage optimization, with computationally intensive approaches typically yielding better results. Figure 1 compares the coverage of mosaics with COT+ constructs produced by two optimization algorithms—the simple greedy extension described in Nickle et al. [1], which can be implemented in hours and run in seconds on any modern personal computer, and the more complex combinatiorial optimization approach of [5] run for one day on a cluster of 300 PCs. We also include the coverage of a construct optimized without any collinearity constraints, derived using the Kirovski et al. [5] algorithm. The coverage of COT+ created by combinatorial optimization is greater than that of mosaics, especially at larger lengths where even the simple greedy algorithm surpasses the mosaic coverage. Furthermore, the optimized COT+ coverage is almost identical to the coverage of constructs optimized with no collinearity constraints, indicating that the price for imposing a constraint on the immunogen to include a single virus-like strain is small. Figure 1 Comparison of Peptide Coverage Scores Achievable with Different Immunogen Formats and Algorithms Fischer and colleagues also argued that COT+ creates unnatural peptide sequences by concatenation. However, similar concatenation of their mosaics would have produced about 18 unnatural 9-mer peptides. Furthermore, the COT+ approach can be tuned to both penalize the introduction of unnatural peptides on concatenation, and to define the number of segments to be separately expressed, and thus reduce the requirement for concatenation. Several additional inferences were made in the response by Fischer et al. that should be commented upon. First, COT+ may, of course, be optimized for arbitrary HIV clades or combinations of clades, but the publication of our paper in PLoS Computational Biology reflects our focus on approaches to immunogen design rather than on the production of an exhaustive series of constructs. Also, just as in the mosaic approach, COT+ can be optimized to exclude rare variants (referred to as smoothing in our paper). Fischer et al. also discussed disappointing unpublished findings on the immunogenicity induced against Nef by a construct obtained by fusing a full-length Gag gene and the central portion of the Nef gene. However, these results can only be fairly assessed in light of what would be expected for the full-length Nef protein, and in the case of cellular immune responses, in the context of the same MHC specificities. However, these controls were not provided. We certainly agree that there are substantial challenges to the establishment of a multivalent CD8 response, yet multiple strategies have been and are being devised to overcome this important problem. For example, different groups have shown that CD8+ T cell responses can be successfully elicited against CD8+ T cell epitope strings when they are separated by short linker sequences and not in the context of the native protein, implying that they can be processed and presented in vivo [6–11]. Finally, despite 25 years of AIDS research and intensive yet uniformly failed efforts to develop an AIDS vaccine, the scientific community is poorly positioned to determine which, if any, approach to vaccine immunogen design will prove successful. Thus, arguing over methodologies developed with the same goal of incorporating variability has little significance as long as we do not know whether maximizing variability or inclusion of the entire full-length viral proteins are valid strategies. It may very well be that removing certain epitopes could be a more judicious approach than an overall epitope maximization strategy [12]. Indeed, the flexibility afforded by the COT+ approach, which is not limited to full-length proteins, may well prove superior to immunization with full-length viral protein immunogens.

Digital fingerprinting is an emerging tool to protect multimedia content from unauthorized distribution by embedding a unique fingerprint into each user's copy. Although several fingerprinting schemes have been proposed in related work, disproportional effort has been targeted towards identifying effective collusion attacks on fingerprinting schemes. Recent introduction of the gradient attack has refined the definition of an optimal attack and demonstrated strong effect on direct-sequence, uniformly distributed, and Gaussian spread spectrum fingerprints when applied to synthetic signals. In this paper, we apply the gradient attack on an existing well-engineered video fingerprinting scheme, refine the attack procedure, and demonstrate that the gradient attack is effective on Laplace fingerprints. Finally, we explore an improvement on fingerprint design to thwart the gradient attack. Results suggest that Laplace fingerprint should be avoided. However, we show that a signal mixed of Laplace and Gaussian fingerprints may serve as a design strategy to disable the gradient attack and force pirates into averaging as a form of adversary collusion.

Device pairing is a significant problem for a large class of increasingly popular resource-constrained wireless protocols such as Bluetooth. The objective of pairing is to establish a secure wireless communication channel between two specific devices without a public-key infrastructure, a secure near-field communication channel, or electrical contact. In this paper, we use a surprising user-device interaction as a solution to this problem. By adding a 3-axis accelerometer, a device can sense its motion in local Cartesian space relative to the inertial space. The idea is to have two devices in a fixed, relative position to each other. The joint object is then moved randomly in 3D for several seconds. The unique and difficult to reproduce motion generates approximately the same distinct signal at each accelerometer. The difference between the signals in the two inertially conjoined sensors should be relatively small under normal motion induced manually except for a fixed attitude offset. The objective is to derive a deterministic key at both sides with maximized entropy that will be used as a private key for symmetric encryption. Currently, our prototype produces 9-20 bits of entropy per second of usual manual motion using off-the-shelf components.

We introduce a novel compression paradigm to generalize a class of Lempel-Ziv algorithms for lossy compression of multimedia. Based upon the fact that music, in particular electronically generated sound, has substantial level of repetitiveness within a single clip, we generalize the basic Lempel-Ziv compression algorithm to support representing a single window of audio using a linear combination of filtered past windows. In this positioning paper, we present a detailed overview of the new lossy compression paradigm, we identify the basic challenges such as similarity search and present preliminary experimental results on a benchmark of electronically generated musical pieces

Billions of dollars allegedly lost to piracy of multimedia have recently triggered the industry to rethink the way music and movies are distributed. As encryption is vulnerable to rerecording, currently all copyright protection mechanisms tend to rely on watermarking. A watermark is an imperceptive secret hidden in a host signal. In this paper, we analyze the security of multimedia copyright protection systems that use watermarks by proposing a new breed of attacks on generic watermarking systems. A typical replacement attack relies upon the observation that multimedia content is often highly repetitive. Thus, the attack procedure replaces each signal block with another, perceptually similar block computed as a combination of other similar blocks found either within the same media clip or within a library of media clips. Assuming the blocks used to compute the replacement are marked with distinct secrets, we show that if the computed replacement block is at some minimal distance from the original marked block, a large portion of the embedded watermark is removed. We describe the logistics of the attack and an exemplary implementation against a spread-spectrum data hiding technology for audio signals.

With the emergence of software delivery platforms, code compression has become an important system component that strongly affects performance. This article presents PPMexe, a compression mechanism for program binaries that analyzes their syntax and semantics to achieve superior compression ratios. We use the generic paradigm of prediction by partial matching (PPM) as the foundation of our compression codec. PPMexe combines PPM with two preprocessing steps: ( i ) instruction rescheduling to improve prediction rates and ( ii ) heuristic partitioning of a program binary into streams with high autocorrelation. We improve the traditional PPM algorithm by ( iii ) using an additional alphabet of frequent variable-length supersymbols extracted from the input stream of fixed-length symbols. In addition, PPMexe features ( iv ) a low-overhead mechanism that enables decompression starting from an arbitrary instruction of the executable, a property pivotal for runtime software delivery. We implemented PPMexe for x86 binaries and tested it on several large applications. Binaries compressed using PPMexe were 18--24% smaller than files created using off-the-shelf PPMD, one of the best available compressors

In this paper we introduce a novel visual perception model that aims to quantify the localized tolerance to noise for arbitrary imagery. The model is built by mixing the outputs from entropy and a differential localized standard deviation filter. The mixture is then low-pass filtered and normalized to provide a model that produces substantially better perceptual hi-fidelity than existing tools of similar complexity. Although there exist numerous applications for the new model, from compression to medical imaging and denoising, we demonstrate its efficacy using an image annotation application. The objective is to embed 32 bits of meta-data into a single image in a way that is robust to aggressive JPEG compression and cropping. We demonstrate the effectiveness of the novel model as well as the developed annotation technology using a database of high-challenge images

We propose a novel platform for building off-line markets for digital content. The key objective is to enable an arbitrary user of specific digital content to resell it to other users in an off-line peer-to-peer manner so that part of the proceeds go to content's copyright holder. Most importantly, one part of the revenues is retained by the seller as an incentive for participating in the distributed economy. To address this objective, a transaction is finalized and incentives distributed to the seller on-line using a client-server architecture. Technologically, such systems can be readily created, for example, by adding a communication tool such as Bluetooth to a portable media player such as the iPod. We present a threat model for the proposed system and devise a novel protocol that relies on traditional public-key cryptography to ensure secure and efficient off-line transactions of arbitrary digital content. As a consequence, in our system copyright holders can control the pricing and recruit a powerful marketing and sales force with marginal investment and via various types of incentives, users are offered the ability to sell or purchase content they like anywhere, anytime, and to/from anyone.

Deep submicrometer technology scaling has two major ramifications on the design process. First, reduced feature size significantly increases wire delay, thus resulting in critical paths being dominated by global interconnect rather than gate delays. Second, an ultrahigh level of integration mandates design of systems-on-chip that encompass numerous design blocks of decreased functional granularity and increased communication demands. The convergence of these two factors emphasizes the importance of the on-chip bus network as one of the crucial high-performance enablers for future systems-on-chip. An on-chip bus-network design methodology and corresponding set of tools which, for the first time, close the synthesis loop between system and physical design have been developed. The approach has three components: a communication profiler, a bus-network designer, and a fast approximate floorplanner. The communication profiler collects run-time information about the traffic between system cores. The bus-network design component optimizes the bus-network structure by coordinating information from the other two components. The floorplanner aims at creating a feasible floorplan; it also sends feedback about the most constrained parts of the network. The effectiveness of our bus-network design approach on a number of multicore designs is demonstrated

Recently, design reuse has emerged as a dominant design and system-integration paradigm for modern systems on silicon. However, the intellectual-property-business model is vulnerable to many dangerous obstructions, such as misappropriation and copyright fraud. The authors propose a new method for intellectual-property protection that relies upon design watermarking at the combinational-logic-synthesis level. They introduce two protocols for embedding user- and tool-specific information into a logic network while performing multilevel logic minimization and technology mapping, two standard-optimization processes during logic synthesis. The hidden information can be used to protect both the design and the synthesis tool. The authors demonstrate that the difficulty of erasing or finding a valid signature in the synthesized design can be made arbitrarily computationally difficult. In order to evaluate the developed-watermarking method, the authors applied it to a standard set of real-life benchmarks, where high probability of authorship was achieved with negligible overhead on solution quality

In this paper, we propose EyeCerts, a biometric system for the identification of people which achieves offline verification of certified, cryptographically secure documents. An EyeCert is a printed document which certifies the association of content on the document with a biometric feature-a compressed version of a human iris in this work. The system is highly cost-effective since it does not require high complexity, hard-to-replicate printing technologies. Further, the device used to verify an EyeCert is inexpensive, estimated to have approximately the same cost as an off-the-shelf iris-scanning camera. As a central component of the EyeCert system, we present an iris analysis technique that aims to extract and compress the unique features of a given iris with a discrimination criterion using limited storage. The compressed features should be at maximal distance with respect to a reference iris image database. The iris analysis algorithm performs several steps in three main phases: 1) the algorithm detects the human iris by using a new model which is able to compensate for the noise introduced by the surrounding eyelashes and eyelids, 2) it converts the isolated iris using a modified Fourier-Mellin transform into a standard domain where the common radial patterns of the human iris are concisely represented, and 3) it optimally selects, aligns, and near-optimally compresses the most distinctive transform coefficients for each individual user. Using a low-quality imaging system (sub-U.S.$100), a /spl chi//sup 2/ error distribution model, and assuming a fixed false negatives rate of 5%, EyeCert caused false positives at rates better than 10/sup -5/ and as low as 10/sup -30/ for certain users.

Digital watermarking has been introduced in the 1990s as a complementary technology for copyright protection. In an effort to anticipate hostile behavior of adversaries, the research community is constantly introducing new attacks to benchmark watermarking systems. In this paper, we present a generic attack strategy based on block replacement. As multimedia content is often highly repetitive, the attack exploits signal's self-similarities to replace each signal block with another, perceptually similar one. Guided by the principles of the proposed attack framework, we implemented three attack algorithms for different types of multimedia content: video shots, audio tracks and still images. Finally, considering the effectiveness of the proposed algorithms, we identify the properties that a watermark should have to counter this attacking strategy

A certificate of authenticity (COA) is an inexpensive physical object that has a random unique structure with high cost of near-exact reproduction. An additional requirement is that the uniqueness of COA's random structure can be verified using an inexpensive device. Bauder was the first to propose COA created as a randomized augmentation of a set of fixed-length fibers into a transparent gluing material that randomly fixes once for all the position of the fibers within. Recently, Kirovski (2004) showed that linear improvement in the compression ratio of a point-set compression algorithm used to store fibers' locations, yields exponential increase in the cost of forging a fiber-based COA instance. To address this issue, in this paper, we introduce a novel, generalized heuristic that compresses M points in an N-dimensional grid with computational complexity proportional to O(M/sup 2/). We compare its performance with an expected lower bound. The heuristic can be used for numerous other applications such as storage of biometric patterns.

Summary form only given. We introduced (Kirovski and Landau (2004)) a memory-based model of the source signal, which explores multimedia repetitiveness to improve upon compression rates achieved by classic memoryless or simple prediction-based audio compression algorithms such as MP3. The representation error is masked using a psycho-acoustic filter. The goal of the masking function is to set the error such that reconstruction of audible samples is exact whereas the reconstruction of inaudible samples is such that the absolute magnitude of the error is minimized. We compute the entropy of the quantized pointers to all blocks, the quantized pointers to the applied transforms, the quantized scalars used to create the linear combination of transformed blocks, and the error vector returned.

The difficulty of building an effective digital rights management system stems from the fact that traditional cryptographic primitives such as encryption or scrambling do not protect audio or video signals once they are played in plain-text. This fact, commonly referred to as "the analog hole," has been responsible for the popularity of multimedia file sharing which cannot be controlled, at least technically, by content's copyright owners. In this paper, we explore a specific issue in multimedia fingerprinting as an answer to "the analog hole" problem. We analyze the collusion resistance of three large classes of spread-spectrum fingerprints using a recently introduced collusion procedure, the gradient attack. Surprisingly, we show that the collusion resistance of direct-sequence and uniformly distributed spread spectrum fingerprints is a small constant that does not depend on the object size, whereas bounded Gaussian fingerprints demonstrate significantly better robustness to the gradient attack.

The generalized Lempel-Ziv (GLZ) paradigm for lossy compression for audio relies upon the fact that music, in particular electronically generated sound, has a substantial level of repetitiveness within a single clip. Thus, GLZ compresses each of the overlapped and transformed windows of the audio using a linear combination of filtered past windows. Following the introduction of the basic GLZ algorithm, in this paper, we empirically analyze several key algorithm components. We analyze the design of simple band-pass filters used during the similarity search, we investigate the distributions of weights used to create the linear combinations, and finally, we explore how beat detection can be used to significantly speed up the similarity search process. We present preliminary experimental results on a benchmark of electronically generated musical pieces.

The difficulty of building an effective digital rights management system stems from the fact that traditional cryptographic primitives such as encryption or scrambling do not protect audio or video signals once they are played in plain-text. This fact, commonly referred to as "the analog hole," has been responsible for the popularity of multimedia file sharing which cannot be controlled, at least technically, by content's copyright owners. In this paper, we explore a specific issue in multimedia fingerprinting as an answer to "the analog hole" problem. We analyze the collusion resistance of spread-spectrum fingerprints with an arbitrary probability distribution of their source using a recently introduced collusion procedure, the gradient attack

Rapid prototyping and development of in-circuit and FPGA-based emulators as key accelerators for fast time-to-market has resulted in a need for efficient error correction mechanisms. Fabricated or emulated prototypes upon error diagnosis require an effective engineering change (EC). We introduce a novel design methodology which consists of pre- and post-processing techniques that enable EC with minimal perturbation. Initially, in a synthesis preprocessing step, the original design specification is augmented with additional design constraints which ensure flexibility for future correction. Upon alteration of the initial design, a new post-processing technique achieves the desired functionality with near-minimal perturbation of the initially optimized design. The key contribution is a constraint manipulation technique which enables the reduction of an arbitrary EC problem into its corresponding classical synthesis problem. As a result, in both pre- and post-processing for EC, classical synthesis algorithms can be used to enable flexibility and perform the correction process. We demonstrate the developed EC methodology on a set of behavioral and system synthesis tasks.

This paper describes the point compression for certificates of authenticity (COA), which are digitally signed physical objects that have a random unique structure. The certificates of authenticity satisfies three requirements: (i) the cost of creating and signing original COAs is small (ii) the cost of exact of near-exact replication of COA's physical structure is several orders of magnitude larger than creating an original, and (iii) the cost of verifying the authenticity of a signed COA is small. The straightforward point compression algorithm is developed to address information about the random structure of the physical object.

This paper proposes EyeCerts, a biometric system for identification of people, which achieves off-line verification of certified, cryptographically secure documents. An EyeCert is a printed document, which certifies the association of a given text with a biometric feature-a compressed version of a human iris in this work. As a central component of the EyeCert system, an iris analysis technique that extracts and compresses the unique features of a given iris using limited storage is presented. The compressed features should be at maximal distance with respect to a reference iris image database. The iris analysis algorithm performs several steps in three main phases: (i) it detects the human iris, (ii) it converts the isolated iris using a modified Fourier-Mellin transform into a standard domain where the common radial patterns of the human iris are concisely represented, and (iii) it optimally selects, aligns, and near-optimally compresses the most distinctive transform coefficients for each individual user. Using a low quality imaging system (sub-US$100) and developed and readily available low complexity processing techniques, the overall system is shown to have probabilities of false negative and false positive on the order of 10/sup -5/.

We present FACECERTS, a simple, inexpensive, and cryptographically secure identity certification system. A FACECERT is a printout of person's portrait photo, an arbitrary textual message, and a 2D color bar-code which encodes an RSA signature of the message hash and the compressed representation of the face encompassed by the photo. The signature is created using the private key of the party issuing the ID. Verification is performed by a simple, intelligent, and off-line scanning device that contains the public key of the issuer. The system does not require smart cards. More interestingly, the ID does not need to be printed by a high-end printer, it can be printed anywhere. We present a novel algorithm for compressing faces and investigate the reliability of the crucial components of the system.

Billions of dollars allegedly lost to piracy of multimedia have recently triggered the industry to rethink the way music and movies are distributed. As encryption is vulnerable to re-recording, currently all copyright protection mechanisms tend to rely on watermarking. In order to analyze the security of such systems, a new breed of replacement attacks has recently been proposed that strongly affects most modern watermarking systems. A typical replacement attack relies upon the observation that multimedia content is often highly repetitive. Thus, the attack procedure replaces each signal block with another, perceptually similar block computed as a combination of other similar blocks found either within the same media clip or within a library of media clips. We demonstrate that by randomizing the attack algorithm, its performance can be improved in almost all aspects - attack efficacy, distortion, speed, and size of the look-up media library. We describe the logistics of the new attack and an exemplary implementation against a spread-spectrum data hiding technology for audio signals.

This paper discusses the certificates of authenticity (COAs) that are digitally signed physical objects with a unique random structure. The random structure of a fiber-based COA relies on the fact that if one end-point of a fiber is exposed to light, the other one illuminates. A COA instance is compressed and then combined with the cryptographic hash. Each COA instance is associated with message recovery using issuer's public key. The key optimization goal in this system is to compress as much of the entropy of COA's random structure. The key parameter of the point-compression problem is: computing the COA model, encoding pixel-to-pixel vectors, and heuristically solving the asymmetric traveling salesman problem. The encoding can be done using arithmetic vector. A heuristic is developed that aims at solving point-compression problem and the compression rate is obtained much better.

Preventing execution of unauthorized software on a given computer plays a pivotal role in system security. The key problem is that although a program at the beginning of its execution can be verified as authentic, its execution flow can be redirected to externally injected malicious code using, for example, a buffer overflow exploit. We introduce a novel, simplified, hardware-assisted intrusion prevention platform. Our platform introduces overlapping of program execution and MAC verification. It partitions a program binary into blocks of instructions. Each block is signed using a keyed MAC that is attached as a footer to the block. When the control flow reaches a particular block, its instructions are speculatively executed, while dedicated hardware verifies the attached MAC at run-time. The computation state is preserved during speculative execution using a mediating buffer placed between the processor and L1 data cache. Upon MAC verification, the results from this buffer are propagated externally. Central to this paper is the proposal of a novel optimization technique that initially identifies instructions that are likely to stall execution, and reorders basic blocks within a given instruction block to minimize the execution overhead. While the presented optimization technique is problem specific, it is flexible such that it can be adjusted for different optimization goals. Preliminary results showed that our optimization methods produced an average overhead reduction of 60% on the SPEC2000 benchmark suite and Microsoft Visual FoxPro.

One of the prime reasons movie and music studios have ignored the Internet for open-networked multimedia content delivery, has been the lack of a technology that can support a secure digital rights management (DRM) system on a general purpose computer. The difficulty of building an effective multimedia DRM stems from the fact that traditional cryptograic primitives such as encryption or scrambling do not protect audio or video signals once they are played in plain-text. This fact, commonly referred to as "the analog hole," has been responsible for the popularity of multimedia file sharing which cannot be controlled, at least technically, by content's copyright owners.

We introduce a novel compression paradigm to generalize a class of Lempel-Ziv algorithms for lossy compression of multimedia. Based upon the fact that music, in particular electronically generated sound, has substantial level of repetitiveness within a single clip, we generalize the basic Lempel-Ziv compression algorithm to support representing a single window of audio using a linear combination of filtered past windows. In this positioning paper, we present a detailed overview of the new compression paradigm, we identify the basic challenges such as similarity search and present preliminary experimental results on a benchmark of electronically generated musical pieces.

A certificate of authenticity (COA) is an inexpensivephysical object that has a random unique structure with a highcost of exact reproduction. An additional requirement is that theuniqueness of COA's random structure can be verified using aninexpensive device. Donald Bauder was the first to propose COA screated as a randomized augmentation of a set of fixed-length fibers into a transparent gluing material that fixes once for all the position of the fibers within. The statistics of the positioning of fibers is used as a source of randomness that is difficult to replicate.As oppose to recording authentic fiber-based COA structures in adatabase, we use public-key cryptography to authenticate COAs.During certification, the unique property of the physical objectis extracted, combined with an arbitrary text, signed with the private key of the issuer, and the signature is encoded andprinted as a barcode on the COA. Since the capacity of the barcodeis limited, the goal of any COA system is to contain in the signed message as much information about the random structure of the physical object as possible. In this paper, we show that the cost of forging a particular COA instance is exponentially proportional to the improvement in compressing COA's random features. Next, we formally define the compression objective, show that finding its optimal solution is an NP-hard problem, and propose a heuristic that improves significantly upon best standard compression methods.

Computational forensic engineering (CFE) aims to identify the entity that created a particular intellectual property (IP). Specifically, our goal is to identify the synthesis tool or compiler which was used to produce a specific design or program. Rather than relying on watermarking content or designs, the generic CFE methodology analyzes the statistics of certain features of a given IP and quantizes the likelihood that a well known source has created it. In this paper, we describe the generic methodology of CFE and present a set of techniques that, given a set of compilation tools, identify the one used to generate a particular hardware/software design. The generic CFE approach has four phases: 1) feature and statistics data collection; 2) feature extraction; 3) entity clustering; and 4) validation. In addition to IP protection, the developed CFE paradigm can have other potential applications: optimization algorithm selection and tuning, benchmark selection, and source-verification for mobile code.

With the emergence of software delivery platforms such as Microsoft's .NET, the reduced size of transmitted binaries has become a very important system parameter, strongly affecting system performance. We present two novel pre-processing steps for code compression that explore program binaries' syntax and semantics to achieve superior compression ratios. The first preprocessing step involves heuristic partitioning of a program binary into streams with high auto-correlation. The second preprocessing step uses code optimization via instruction rescheduling in order to improve prediction probabilities for a given compression engine. We have developed three heuristics for instruction rescheduling that explore tradeoffs of the solution quality versus algorithm run-time. The pre-processing steps are integrated with the generic paradigm of prediction by partial matching (PPM) which is the basis of our compression codec. The compression algorithm is implemented for x86 binaries and tested on several large Microsoft applications. Binaries compressed using our compression codec are 18-24% smaller than those compressed using the best available off-the-shelf compressor.

The prediction by partial matching (PPM) algorithm uses a cumulative frequency count of input symbols in different contexts to estimate its probability distribution. Compression ratios yielded by the PPM algorithm have not instigated broader use of this scheme mainly because of its high demand for computational resources. An algorithm that improves the memory usage by the PPM model is presented. The algorithm identifies and removes portions of the PPM model, which are not contributing toward better modeling of the input data. As a result, our algorithm improves the average compression ratio up to 7% under the memory limitation constraint at the expense of increased computation. Under the constraint of maintaining the same level of compression ratios, the algorithm reduces the memory usage up to 70%.

Summary form only given. The proposed electronic systems for personal ID verification need to connect to a remote database and retrieve a stored photo for the comparison with the image on the ID. Unlike these systems, FaceCerts is an off-line person identification system that relies on public-key cryptography for provable security, while deploying a standard-quality low-cost color printing process. The basic requirement for the face compression algorithm in this system is discussed. A simple printing and scanning process combined with the face compression and matching software provides strong reliability of the FaceCerts system, resulting in relatively low likelihood of false negatives and cryptographically strong likelihood of a false positive.

We present a technique for compression of shortest paths routing tables for wireless ad hoc networks. The main characteristic of such networks is that geographic location of nodes determines network topology. As opposed to encoding individual node locations, at each node our approach groups the remaining nodes in the network into regions. All shortest paths to nodes in a specific region are routed via the same neighboring node. In this paper, we propose an algorithm for dividing a network field into distinct regions to minimize routing table size while guaranteeing shortest path routes. We show that this problem is NP-hard, propose a heuristic to find efficient solutions, and empirically demonstrate the resulting system performance from the perspective of compression ratio and scalability. In our experiments, routing tables compressed using this technique, require 88.9% to 97.9% less storage than uncompressed tables.In order to achieve energy efficient routing, we propose an augmentation to the original routing mechanism that enables load balancing flexibility along with guaranteed shortest path routing at the expense of larger routing tables. Preliminary experiments estimate 10% lifetime extension of network nodes with a tradeoff of an increase in the size of routing tables. Finally, we propose a compression technique that aims at representing trajectories in a sensing network in a compact manner. This approach relies on trajectory prediction using three weighted Markov models, a local, regional and global one, all of them with context-length equal to one. Finally, we discuss a range of possible applications that rely on the developed prediction and routing models.

Recently, the electronic design automation industry has adopted the intellectual property (IP) business model as a dominant system-on-chip development platform. Since copyright fraud has been recognized as the most devastating obstruction to this model, a number of techniques for IP protection have been introduced. Most of them rely on a selection of a global solution to a design optimization problem according to a unique user-specific digital signature. Although such techniques provide strong proof of authorship, they fail to provide an effective procedure for watermark detection when a protected core design is augmented into a larger design. To address this fundamental issue, we introduce local watermarks, an IP protection technique which facilitates watermark detection in many realistic design and adversarial scenarios, while satisfying the demand for low overhead and design transparency. We demonstrate the efficiency of the new IP protection paradigm by applying its principles to a set of behavioral synthesis tasks such as operation scheduling and template matching.

Preventing execution of unauthorized software on a given computer plays a pivotal role in system security. The key problem is that although a program at the beginning of its execution can be verified as authentic, while running, its execution flow can be redirected to externally injected malicious code using, for example, a buffer overflow exploit. Existing techniques address this problem by trying to detect the intrusion at run-time or by formally verifying that the software is not prone to a particular attack.We take a radically different approach to this problem. We aim at intrusion prevention as the core technology for enabling secure computing systems. Intrusion prevention systems force an adversary to solve a computationally hard task in order to create a binary that can be executed on a given machine. In this paper, we present an exemplary system--SPEF--a combination of architectural and compilation techniques that ensure software integrity at run-time. SPEF embeds encrypted, processor-specific constraints into each block of instructions at software installation time and then verifies their existence at run-time. Thus, the processor can execute only properly installed programs, which makes installation the only system gate that needs to be protected. We have designed a SPEF prototype based on the ARM instruction set and validated its impact on security and performance using the MediaBench suite of applications.

Engineering change (EC) is a technique that enables a designer to rapidly perform minor specification alternations while minimally resynthesizing only small portions of the specification throughout several levels of design abstraction. In this paper, we introduce the first EC-based synthesis technique for coordinated design optimization in multiple steps. The technique has four phases: optimization region identification, feedback formulation, resynthesis in first step, and finally resynthesis in the second design step. To demonstrate the technique, we focus on behavioral synthesis and transformation, scheduling, and register assignment steps. We developed a generic EC-based approach for design optimization during multiple consecutive synthesis steps. Next, we show how one can use EC to enhance coordinated application of transformations and scheduling, and scheduling and register assignment.

With the emergence of software delivery platforms such as Microsoft's .NET, code compression has become one of the core enabling technologies strongly affecting system performance. We present PPMexe - a set of compression mechanisms for executables that explores their syntax and semantics to achieve superior compression rates. The fundament of PPMexe is the generic paradigm of prediction by partial matching (PPM). We combine PPM with two pre-processing steps: instruction rescheduling to improve prediction rates and partitioning of a program binary into streams with high auto-correlation. We improve the traditional PPM algorithm by using: an additional alphabet of frequent variable-length super-symbols extracted from the input stream of fixed-length symbols and a low-overhead mechanism that enables decompression starting from an arbitrary instruction of the executable, a feature pivotal for run-time software delivery. PPMexe was implemented for x86 binaries and tested on several large Microsoft applications. Binaries compressed using PPMexe were 16-23% smaller than files created using PPMD, the best available compressor.

Spread-spectrum (SS) watermarking has been one of the oldest methodologies for hiding data in multimedia signals. Recently, it has been demonstrated that simple block repetition codes provide strong robustness of such watermarks to noise addition and limited arbitrary geometric transformations. In order to further investigate the security of such watermarks, we explore in this paper their robustness with respect to watermark estimation attacks. In such attacks, the adversary has knowledge of the watermark algorithm, except the secret keys. We present a modification of the traditional SS watermark detector that forces the adversary to increase the amount of noise to be proportional to the signal amplitude, in order to remove an SS watermark.

Billions of dollars allegedly lost to piracy of multimedia content have recently triggered the industry to rethink the way how music and movies are distributed on the Internet. As encryption is vulnerable to digital or analog re-recording, currently almost all copyright protection mechanisms rely to certain extent on watermarking, i.e. hiding of imperceptive secrets into a host signal. In this paper, we propose a new breed of attacks on generic watermarking systems, which recognizes that multimedia content is often highly repetitive, identifies subsets of signal blocks that are similar, and finally permutes these blocks. Assuming the permuted blocks have been marked with distinct secrets, it can be shown that any watermark detector is facing a task of exponential complexity to reverse the permutations as a preprocessing step for watermark detection. In this paper, we describe the logistics of the attack and a recipe for its implementation against an audio watermarking technology.

We present a new dual watermarking and fingerprinting system, where initially all copies of a protected object are identically watermarked using a secret key, but individual detection keys are distinct. By knowing a detection key, an adversary cannot recreate the original content from the watermarked content. However, knowledge of any one detection key is sufficient for modifying the object so that a detector using that key would fail to detect the marks. Detectors using other detection keys would not be fooled, and such a modified object necessarily contains enough information about the broken detector key - the fingerprint. Our dual system limits the scope of possible attacks, when compared to classic fingerprinting systems. Under optimal attacks, the size of the collusion necessary to remove the marks without leaving a detectable fingerprint is superlinear in object size, whereas classic fingerprinting has a lower bound on collusion resistance that is approximately fourth root in object size. By using our scheme one can achieve collusion resistance of up to 900,000 users for a two hour high-definition video.

Recently, the Internet revolutionized many activities from entertainment to marketing and business. Two key underlying Internet technologies, efficient data delivery and hypertext, demonstrated exceptional potential as new application enablers. In this paper, we present a novel Hypermedia-Aided Design (HAD) collaboration framework that facilitates new communication and data presentation paradigms to improve the effectiveness of typical EDA applications. The framework leverages on the advantages of using semantic multicast as a communication backbone and quantized hypermedia presentations as an efficient data organization, retrieval, and presentation model. Semantic multicast is a global communication tool that relies on an inter-network of proxies to provide content discovery and semantics-based profile-driven data dissemination services. We introduce the notion of a quant, an atomic interactive multimedia information primitive with embedded hyperlinks. We demonstrate how interest-specific quant retrieval and concatenation can enable more focused collaboration.

Deep submicron technology has two major ramifications on the design process: (i) critical paths are being dominated by global interconnect rather than gate delays and (ii) ultra high levels of integration mandate designs that encompass numerous intra-synchronous blocks with decreased functional granularity and increased communication demands. These factors emphasize the importance of the on-chip bus network as the crucial high-performance enabler for future systems-on-chip. By using independent functional blocks with programmable connectivity, designers are able to build systems-on-chip capable of supporting different applications with exceptional levels of resource sharing. To address challenges in this design paradigm, we have developed a methodology that enables efficient bus network design with approximate timing verification and floorplanning of multi-purpose systems-on-chip in early design stages. The design platform iterates system synthesis and floorplanning to build min-area floorplans that satisfy statistical time constraints of applications. We demonstrate the effectiveness of our bus network design approach using examples from a multimedia benchmark suite.

We present several mechanisms that enable effective spread-spectrum audio watermarking systems: prevention against detection desynchronization, cepstrum filtering, and chess watermarks. We have incorporated these techniques into a system capable of reliably detecting a watermark in an audio clip that has been modified using a composition of attacks that degrade the original audio characteristics well beyond the limit of acceptable quality. Such attacks include: fluctuating scaling in the time and frequency domain, compression, addition and multiplication of noise, resampling, requantization, normalization, filtering, and random cutting and pasting of signal samples.

Watermarking has been adopted as a technology of choice for many applications related to e-commerce of audio content. We present a brief summary of a set of spread-spectrum watermarking techniques for effective covert communication over an audio signal carrier. Watermark robustness is enabled using redundant spread-spectrum for prevention against de-synchronization attacks. We improve watermark inaudibility by detecting and not watermarking blocks of audio where a spread spectrum sequence, if added to the frequency spectrum, would be audible. Finally, we overview the security limitations of our technology with respect to parameter selection and position it with respect to three main applications of watermarking: (a) content screening, (b) tracing unlicensed content distribution, and (c) robust metadata.

Symbolic debuggers are system-development tools that can accelerate the validation speed of behavioral specifications by allowing a user to interact with an executing code at the source level. In response to a user query, the debugger must retrieve and display the value of a source variable in a manner consistent with user expectations with respect to the source statement where execution has halted. However, when a behavioral specification has been optimized using transformations, values of variables may either be inaccessible in the runtime state or inconsistent with user expectations. We address the problem that pertains to the retrieval of source values for the globally optimized behavioral specifications. We present a new approach for symbolic debugging. The implementation of the new debugging approach poses several optimization tasks. We formulate the optimization tasks and develop heuristics to solve them. We demonstrate the effectiveness of the proposed approach on a set of designs.

No abstract available.

The proliferation of the Internet has affected the business model of almost all semiconductor and VLSI CAD companies that rely on intellectual property (IP) as their main source of revenues. The fact that IP has become more accessible and easily transferable, has influenced the emergence of copyright infringement as one of the most common obstructions to e-commerce of IP.

The semiconductor industry has adopted the intellectual property (IP) business model as a dominant system-on-chip development platform. Since copyright fraud has been recognized as the most devastating obstruction to this model, a number of techniques for IP protection have been introduced. Most of them rely on a selection of a global solution to an optimization problem according to a unique user-specific digital signature. Although such techniques may provide convincing proof of authorship with little hardware overhead, they fail to protect design partitions, do not provide an easy procedure for watermark detection, and are not capable of detecting the watermark when the design or its part is augmented in another larger design. Since these demands are of the highest interest for the IP business, we introduce localized watermarking as an IP protection technique which enables these features while satisfying the demand for low-cost and transparency. We have applied the new watermarking technology to template mapping, a behavioral synthesis task. This watermarking method has been tested on a set of real-life benchmarks where high likelihood of authorship has been achieved with negligible overhead in solution quality.

Deep submicron technology scaling has two major ramifications on the design process. First, reduced feature size significantly increases wire delay, thus resulting in critical paths being dominated by global interconnect rather than gate delays. Second, ultra high level of integration mandates design of systems-on-chip that encompass numerous intra-synchronous blocks with decreased functional granularity and increased communication demands. To address these issues we have developed an on-chip bus network design methodology and corresponding set of tools which, for the first, time, close the synthesis loop between system and physical design. The approach has three components: a communication profiler, a bus network designer, and a fast approximate floorplanner. The communication profiler collects run-time information about the traffic between system cores. The bus network design component optimizes the bus network structure by coordinating information from the other two components. The floorplanner aims at creating a feasible floorplan and to communicate information about the most constrained parts of the network.

Symbolic debuggers are system development tools that can accelerate the validation speed of behavioral specifications by allowing a user to interact with an executing code at the source level. In response to a user query, the debugger retrieves the value of a source variable in a manner consistent with respect to the source statement where execution has halted. However, when a behavioral specification has been optimized using transformations, values of variables may be inaccessible in the run-time state. We have developed a set of techniques that, given a behavioral specification CDFG, enforce computation of a selected subset V/sub cut/ of user variables such that (i) all other variables /spl upsi//spl isin/CDFG can be computed from V/sub cut/ and (ii) this enforcement has minimal impact on the optimization potential of the computation. The implementation of the new debugging approach poses several optimization tasks. We have formulated the optimization tasks and developed heuristics to solve them. The effectiveness of the approach has been demonstrated on a set of benchmark designs.

Due to the growth of both design complexity and the number of gates per pin, functional debugging has emerged as a critical step in the development of a system-on-chip (SOC). Traditional approaches, such as system emulation and simulation, are becoming increasingly inadequate to address the system debugging needs. Design simulation is two to ten orders of magnitude slower than emulation and, thus, is used primarily for short, focused test sequences. Emulation has the required speed but imposes strict limitations on signal observability and controllability. We introduce a new debugging approach for programmable SOC's that leverages the complementary advantages of emulation and simulation. We propose a set of tools, transparent to both the design and debugging process, that enables the user to run long test sequences in emulation and, upon error detection, roll back to an arbitrary instance in execution time and switch over to simulation-based debugging for full design visibility and controllability. The efficacy of the developed approach is dependent upon the method for transferring the computation from one execution domain to another. Although the approach can be applied to any computational model, we have developed a suite of optimization techniques that enable computation transfer in a mixed synchronous data flow semi-infinite stream random-access machine computation model. This computation model is frequently used in many communications and multimedia SOCs. The effectiveness of the developed debugging methodology has been demonstrated on a set of multicore designs where combined emulation-simulation has been enabled with low hardware and performance overhead.

Many modern multimedia applications such as image and video processing are characterized by a unique combination of arithmetic and computational features: fixed-point arithmetic, a variety of short data types, high degree of instruction-level parallelism, strict timing constraints, and high computational requirements.Computationally intensive algorithms usually boost device's power dissipation which is often key to the efficiency of many communications and multimedia applications.Although recently virtually all general-purpose processors have been equipped with multiprecision operations, the current generation of behavioral synthesis tools for application-specific systems does not utilize this power/performance optimization paradigm.In this paper, we explore the potential of using multiple precision arithmetic units to effectively support synthesis of low-power application-specific integrated circuits.We propose a new architectural scheme for collaborate addition of sets of variable precision data.We have developed a novel resource allocation and computation assignment methodology for a set of multiple precision arithmetic units.The optimization algorithms explore the trade-off of allocating low-width bus structures and executing multiple-cycle operations.Experimental results indicate strong advantages of the proposed approach.

Due to the unavoidable need for system debugging, performance tuning, and adaptation to new standards, the engineering change (EC) methodology has emerged as one of the crucial components in synthesis of systems-on-chip.We introduce a novel design methodology which facilitates design-for-EC and post-processing to enable EC with minimal perturbation.Initially, as a synthesis pm-processing step, the original design specification is augmented with additional design constraints which ensure flexibility for future correction.Upon alteration of the initial design, a novel post-processing technique achieves the desired functionality with a near-minimal perturbation of the initially optimized design.The key contribution we introduce is a constraint manipulation technique which enables reduction of an arbitrary EC problem into its corresponding classical synthesis problem.As a result, in both pre-and post-processing for EC, classical synthesis algorithms can be used to enable flexibility and perform the correction process.We demonstrate the developed EC methodology on a set of behavioral and system synthesis tasks.

The convergence of applications (Internet and embedded applications) and technology (reuse and very high integration level) trends resulted in a strong need for design of soft real-time DSP systems-on-silicon. We developed a new hierarchical modular approach for synthesis of area efficient soft real-time DSP systems-on-silicon. This synthesis strategy employs a number of optimization intensive scheduling, performance monitoring, and allocation steps. The backbone of the optimization approach is a novel online scheduling algorithm which uses meta-algorithmic techniques for on-the-fly heuristic selection and parameter tuning. Resource allocation refers to a predetermined lower-bound system performance, to perform a branch-and-bound resource allocation search for an area-efficient multiprocessor configuration where each processor has local instruction and data cache. In order to bridge the gap between the profiling, modeling, and synthesis tools of the two traditionally independent synthesis domains (architecture and CAD), we develop a new synthesis and evaluation platform which integrates the existing modeling, profiling, and simulation tools with the new developed system-level synthesis tools. The effectiveness of the approach is demonstrated on the industrial strength MediaBench benchmark suite.

Rapid prototyping and development of in-circuit and FPGA-based emulators as key accelerators for fast time-to-market has resulted in a need for fast error correction mechanisms. The fabricated or emulated prototypes upon error diagnosis require quick and as much as possible flexible engineering change (EC). However, this problem has initiated research activity mainly in the logic synthesis domain. We introduce the first set of EC protocols for behavioral synthesis. The protocols support both the pre- and post-processing EC paradigms. In addition, instead of developing special algorithms for EC which is the adopted research model, as a key contribution, we show that using protocols which facilitate constraint manipulation of the initial design specification there is no need for development of specialized EC algorithms. The EC process is performed using the standard optimization algorithms on the modified design. Nevertheless, as shown on a number of behavioral synthesis tasks including: resource assignment, design partitioning, and operation scheduling, the approach provides variable and guaranteed flexibility for incremental synthesis with minimal hardware overhead.

We give the first study of copy detection techniques for VLSI CAD applications; these techniques are complementary to previous watermarking-based IP protection methods in finding and proving improper use of design IP. After reviewing related literature (notably in the text processing domain), we propose a generic methodology for copy detection based on determining basic elements within structural representations of solutions (IPs), calculating (context-independent) signatures for such elements, and performing fast comparisons to identify potential violators of IP rights. We give example implementations of this methodology in the domains of scheduling, graph coloring and gate-level layout; experimental results show the effectiveness of our copy detection schemes as well as the low overhead of implementation. We remark on open research areas, notably the potentially deep and complementary interaction between watermarking and copy detection.

Recently, a number of techniques for IP protection have been introduced that rely on a selection of a global solution to an optimization problem according to a unique user-specific digital signature. Although such techniques may provide convincing proof of authorship with low hardware overhead, they fail to protect parts of design, do not provide an easy procedure for watermark detection, and are not capable of detecting the watermark when the design or its part is augmented in another larger design. Since these demands are of the highest interest for the IP business, we introduce localized watermarking as an IP protection technique that enables these features while satisfying the demand for low-cost and transparency. We propose a set of protocols that implement the new watermarking methodology at the operation scheduling design level. We have demonstrated that the difficulty of erasing or finding another signature in the synthesized design can be made arbitrarily computationally difficult. The watermarking method has been tested on a set of real-life benchmarks where high likelihood of authorship has been achieved with negligible overhead in solution quality.

The growing class of portable systems, such as personal computing and communication devices, has resulted in a new set of system design requirements, mainly characterized by dominant importance of power minimization and design reuse. The energy efficiency of systems-on-a-chip (SOC) could be much improved if one were to vary the supply voltage dynamically at run time. We developed the design methodology for the low-power core-based real-time SOC based on dynamically variable voltage hardware. The key challenge is to develop effective scheduling techniques that treat voltage as a variable to be determined, in addition to the conventional task scheduling and allocation. Our synthesis technique also addresses the selection of the processor core and the determination of the instruction and data cache size and configuration so as to fully exploit dynamically variable voltage hardware, which results in significantly lower power consumption for a set of target applications than existing techniques. The highlight of the proposed approach is the nonpreemptive scheduling heuristic, which results in solutions very close to optimal ones for many test cases. The effectiveness of the approach is demonstrated on a variety of modern industrial strength multimedia and communication applications.

Due to the increasing popularity of multimedia and communications applications, requirements for application-specific systems typically include design flexibility and data management ability. Since the development of such systems is a market-driven task, reducing the time to market and manufacturing cost, while still satisfying application performance requirements, is an important system synthesis requirement. We have developed a new approach for area optimization of core-based systems. The approach uses basic block relocation in order to reduce the number of cache misses and, thus, enable hardware savings during system synthesis. Given a processor model, a cache model, and a set of nonpreemptive tasks with timing constraints, the goal of the synthesis framework is to select a system configuration (processor, I-cache, and D-cache) of minimal area that satisfies the performance constraints. The system synthesis framework has two key components. The first component is a code optimization engine that relocates basic blocks within a given assembly program in order to reduce the number of cache misses. The second component is a search mechanism that leverages the improvements in code performance obtained by the first component to select the most area-efficient system configuration. In order to bridge the gap between the profiling and modeling tools, we have constructed a new performance evaluation platform. It integrates the existing modeling, profiling, and simulation tools with the developed system-level synthesis tools. The effectiveness of the synthesis approach is demonstrated on a variety of modern real-life multimedia and communication applications.

Growing design complexity has made functional debugging of application-specific integrated circuits crucial to their development. Two widely used debugging techniques are simulation and emulation. Design simulation provides good controllability and observability of the variables in a design, but is two to ten orders of magnitude slower than the fabricated design. Design emulation and fabrication provide high execution speed, but significantly restrict design observability and controllability. To facilitate debugging, and in particular error diagnosis, we introduce a novel cut-based functional debugging paradigm that leverages the advantages of both emulation and simulation. The approach enables the user to run long test sequences in emulation, and upon error detection, roll-back to an arbitrary instance in execution time, and transparently switch over to simulation-based debugging for full design visibility and controllability. The new debugging approach introduces several optimization problems. We formulate the optimization tasks, establish their complexity, and develop most-constrained least-constraining heuristics to solve them. The effectiveness of the new approach and accompanying algorithms is demonstrated on a set of benchmark designs where combined emulation and simulation is enabled with low hardware overhead.

We developed a new modular synthesis approach for design of low-power core-based data-intensive application-specific systems on silicon. The power optimization is conducted in three steps: minimization of instruction cache misses, placement of frequently executed sequential basic blocks of code in consecutive Gray code addressed memory locations, and processor and cache application-driven selection for low power. In order to bridge the gap between the profiling and modeling tools from the two traditionally disjoint synthesis domains (architecture and CAD), we developed a new synthesis and evaluation platform. The platform integrates the existing modeling, profiling, and simulation tools with the developed system-level synthesis tools. The effectiveness of the approach is demonstrated on a variety of modern industrial-strength multimedia and communication applications.

The growing class of portable systems, such as personal computing and communication devices, has resulted in a new set of system design requirements, mainly characterized by dominant importance of power minimization and design reuse. We develop the design methodology for the low power core-based real-time system-on-chip based on dynamically variable voltage hardware. The key challenge is to develop effective scheduling techniques that treat voltage as a variable to be determined, in addition to the conventional task scheduling and allocation. Our synthesis technique also addresses the selection of the processor core and the determination of the instruction and data cache size and configuration so as to fully exploit dynamically variable voltage hardware, which result in significantly lower power consumption for a set of target applications than existing techniques. The highlight of the proposed approach is the non-preemptive scheduling heuristic which results in solutions very close to optimal ones for many test cases. The effectiveness of the approach is demonstrated on a variety of modern industrial-strength multimedia and communication applications.

We have developed a new algorithm and software for graph coloring by systematically combining several algorithm and software development ideas that had crucial impact on the algorithm's performance. The algorithm explores the divide-and-conquer paradigm, global search for constrained independent sets using a computationally inexpensive objective function, assignment of most-constrained vertices to least-constraining colors, reuse and locality exploration of intermediate solutions, search time management, post-processing lottery-scheduling iterative improvement, and statistical parameter determination and validation. The algorithm was tested on a set of real-life examples. We found that hard-to-color real-life examples are common especially in domains where problem modeling results in denser graphs. Systematic experimentations demonstrated that for numerous instances the algorithm outperformed all other implementations reported in literature in solution quality and run-time.

Modern image and video processing applications are characterized by a unique combination of arithmetic and computational features: fixed point arithmetic, a variety of short data types, high degree of instruction-level parallelism, strict timing constraints, high computational requirements, and high cost sensitivity. The current generation of behavioral synthesis tools does not address well this type of application. In this paper we explore the potential of using multiple precision arithmetic units to effectively support implementation of image and video processing applications as application specific integrated circuits. A new architectural scheme for collaborate addition of sets of variable precision data is proposed as well as an allocation and assignment methodology for multiple precision arithmetic units. Experimental results indicate the strong advantages of the proposed approach.

Recently, design reuse has emerged as a dominant integrated system design and integration paradigm. However, the intellectual property (IP) business model is vulnerable to a number of potentially devastating obstructions, such as misappropriation and intellectual property fraud. We propose a new method for IP protection (IPP) which facilitates design watermarking at the combinational logic synthesis level. We developed protocols for embedding designer- and/or tool-specific information into a logic network while performing multi-level logic minimization and technology mapping. We demonstrate that the difficulty of erasing author's signature or finding another signature in the synthesized design can be made arbitrarily computationally difficult. We also developed a statistical method which enables us to establish the strength of the proof of authorship. The watermarking method has been tested on a standard set of real-life benchmarks where exceptionally high probability of authorship has been achieved with negligible overhead in solution quality.

MS~CTDue totheexponentird growth of both design complexity and the number of gates per pin, functional debugging has emerged as a critical step in the development of a system-on-chip.We introduce a novel debugging approach for programmable systems-on-chip.The new method leverages the advantagw of the two complementary functional execution approaches, emdation and simdation.We have developed a set of tools, transparent to both the design and debug~ng process, which enabl= the user to run long test sequences in emdation, and upon error detection, roll-back to an arbitrary instance in execution time, and switch over to simtiationbased debugging for fu~design visibility md contro~abifity.The efficacy of the approach is dependent on the method for transferring the computation from one execution domain to another.To enable effective transfer of the computation state, we have identifid a set of optimization tasks, established their computation complexity, and developed an efficient suite of optimization dgoritbms.

Successive, well organized application of transformations has beenwidely recognized as an exceptionally effective, but complex anddifficult CAD task. We introduce a new potential-driven statisticalapproach for ordering transformations. Two new synthesis ideasare the backbone of the approach. The first idea is to quantifythe characteristics of all transformations and the relationship betweenthem based on their potential to reorganize a computationsuch that the complexity of the corresponding implementation isreduced. The second one is based on the observation that transformationsmay disable each other not only because they prevent theapplication of the other transformation, but also because both transformationstarget the same potential of the computation. These twoobservations drastically reduce the search space to find efficient andeffective scripts for ordering transformations. A key algorithmicnovelty is that both conceptual and optimization insights as well asall optimization algorithms are automatically derived by organizedexperimentation and statistical methods. On a large set of diversereal-life examples improvements in throughput, area, and power bylarge factors have been obtained. Both qualitative and quantitativestatistical analysis indicate effectiveness, high robustness, and consistencyof the new approach for ordering transformations.

We present a system-level approach for power optimization undera set of user specified costs and timing constraints of hard real-timedesigns. The approach optimizes all three degrees of freedom forpower minimization, namely switching activity, effective capacityand voltage supply.We first define two key associated optimization problems, processorallocation and task assignment, and establish their computationalcomplexity. Efficient algorithms are developed for bothsystem design problems. The statistical analysis of comprehensiveexperimental results and their comparison with the developed conservativeand optimistic sharp lower bounds, clearly indicates thequality of the proposed optimization techniques.

Although the undeniable importance of high quality, efficient and effective DSP synthesis benchmark has been firmly and widely established, until now the emphasis of benchmarking has been restricted on assembling individual examples. In this paper we introduce the "ideal candidate benchmark methodology" which poses the development of the benchmark as well as defines a statistical and optimization problem. We first outline the goals and requirements relevant for the benchmark development. After discussing the computational complexity of the benchmark selection problem, we present a simulated annealing-based algorithm for solving this computationally intractable optimization task. Using this approach from 150 examples we select 12 examples for the new DSP Quant benchmark for DSP hard Real-Time applications. The DSP benchmark is statistically validated, and its application to the analysis and development of system-level synthesis algorithms is demonstrated,.

We developed a new hierarchical modular approach for synthesis of area-minimal core-based data-intensive systems. The optimization approach employs a novel global least-constraining most-constrained heuristic to minimize the instruction cache misses for a given application, instruction cache size and organization. Based on this performance optimization technique, we constructed a strategy to search for a minimal area processor core, and an instruction and data cache which satisfy the performance characteristics of a set of target applications. The synthesis platform integrates the existing modeling, profiling, and simulation tools with the developed system-level synthesis tools. The effectiveness of the approach is demonstrated on a variety of modern real-life multimedia and communication applications.

We introduce a novel cut-based debugging paradigm. It coordinates design emulation and simulation and enables fast transition from one to another. Emulation or functional implementation is used for fast application execution; simulation provides complete design observability and controllability. The implementation of the new debugging approach poses several CAD tasks. We formulate the optimization tasks and develop constraint-based heuristics to solve them. Effectiveness of the approach is demonstrated on a set of designs.

Cost and power consumption are two of the most important design factors for many embedded systems, particularly consumer devices. Products such as personal digital assistants, pagers with integrated data services and smart phones have fixed performance requirements but unlimited appetites for reduced cost and increased battery life. Program compression is one technique that can be used to attack both of these problems. Compressed programs require less memory, thus reducing the cost of both direct materials and manufacturing. Furthermore, by relying on compressed memory, the total number of memory references is reduced. This reduction saves power by lowering the traffic on high-capacitance buses. This paper discusses a new approach to implementing transparent program compression that requires little or no hardware support. Procedures are compressed individually, and a directory structure is used to bind them together at run-time. Decompressed procedures are explicitly cached in ordinary RAM as complete units, thus resolving references within each procedure. This approach has been evaluated on a set of 25 embedded multimedia and communications applications, and results in an average memory reduction of 40% with a run-time performance overhead of 10%.