In cloud computing, it is desirable if suspicious activities can be detected by automatic anomaly detection systems. Although anomaly detection has been investigated in the past, it remains unsolved in cloud computing. Challenges are: characterizing the normal behavior of a cloud server, distinguishing between benign and malicious anomalies (attacks), and preventing alert fatigue due to false alarms. We propose CloudShield, a practical and generalizable real-time anomaly and attack detection system for cloud computing. Cloudshield uses a general, pretrained deep learning model with different cloud workloads, to predict the normal behavior and provide real-time and continuous detection by examining the model reconstruction error distributions. Once an anomaly is detected, to reduce alert fatigue, CloudShield automatically distinguishes between benign programs, known attacks, and zero-day attacks, by examining the reconstruction error distributions. We evaluate the proposed CloudShield on representative cloud benchmarks. Our evaluation shows that CloudShield, using model pretraining, can apply to a wide scope of cloud workloads. Especially, we observe that CloudShield can detect the recently proposed speculative execution attacks, e.g., Spectre and Meltdown attacks, in milliseconds. Furthermore, we show that CloudShield accurately differentiates and prioritizes known attacks, and potential zero-day attacks, from benign programs. Thus, it significantly reduces false alarms by up to 99.0%.

As mobile devices are becoming ubiquitous, regularly interacting with a variety of user interfaces (UIs) is a common aspect of daily life for many people. To improve the accessibility of these devices and to enable their usage in a variety of settings, building models that can assist users and accomplish tasks through the UI is vitally important. However, there are several challenges to achieve this. First, UI components of similar appearance can have different functionalities, making understanding their function more important than just analyzing their appearance. Second, domain-specific features like Document Object Model (DOM) in web pages and View Hierarchy (VH) in mobile applications provide important signals about the semantics of UI elements, but these features are not in a natural language format. Third, owing to a large diversity in UIs and absence of standard DOM or VH representations, building a UI understanding model with high coverage requires large amounts of training data. Inspired by the success of pre-training based approaches in NLP for tackling a variety of problems in a data-efficient way, we introduce a new pre-trained UI representation model called ActionBert. Our methodology is designed to leverage visual, linguistic and domain-specific features in user interaction traces to pre-train generic feature representations of UIs and their components. Our key intuition is that user actions, e.g., a sequence of clicks on different UI components, reveals important information about their functionality. We evaluate the proposed model on a wide variety of downstream tasks, ranging from icon classification to UI component retrieval based on its natural language description. Experiments show that the proposed ActionBert model outperforms multi-modal baselines across all downstream tasks by up to 15.5%.

Spectre and Meltdown attacks and their variants exploit hardware performance optimization features to cause security breaches. Secret information is accessed and leaked through covert or side channels. New attack variants keep appearing and we do not have a systematic way to capture the critical characteristics of these attacks and evaluate why they succeed or fail.In this paper, we provide a new attack-graph model for reasoning about speculative execution attacks. We model attacks as ordered dependency graphs, and prove that a race condition between two nodes can occur if there is a missing dependency edge between them. We define a new concept, “security dependency”, between a resource access and its prior authorization operation. We show that a missing security dependency is equivalent to a race condition between authorization and access, which is a root cause of speculative execution attacks. We show detailed examples of how our attack graph models the Spectre and Meltdown attacks, and is generalizable to all the attack variants published so far. This attack model is also very useful for identifying new attacks and for generalizing defense strategies. We identify several defense strategies with different performance-security tradeoffs. We show that the defenses proposed so far all fit under one of our defense strategies. We also explain how attack graphs can be constructed and point to this as promising future work for tool designers.

Benefiting from the advance of deep learning (DL) technology, Internet-of-Things (IoT) devices and systems are becoming more intelligent and multifunctional. They are expected to run various DL inference tasks with high efficiency and performance. This requirement is challenged by the mismatch between the limited computing capability of edge devices and large-scale deep neural networks. Edge-cloud collaborative systems are then introduced to mitigate this conflict, enabling resource-constrained IoT devices to host arbitrary DL applications. However, the introduction of third-party clouds can bring potential privacy issues to edge computing. In this article, we conduct a systematic study about the opportunities of attacking and protecting the privacy of edge-cloud collaborative systems. Our contributions are twofold: 1) we first devise a set of new attacks for an untrusted cloud to recover arbitrary inputs fed into the system, even if the attacker has no access to the edge device's data or computations, or permissions to query this system and 2) we empirically demonstrate that solutions that add noise fail to defeat our proposed attacks, and then propose two more effective defense methods. This provides insights and guidelines to develop more privacy-preserving collaborative systems and algorithms.

The prevalence of deep learning has drawn attention to the privacy protection of sensitive data. Various privacy threats have been presented, where an adversary can steal model owners' private data. Meanwhile, countermeasures have also been introduced to achieve privacy-preserving deep learning. However, most studies only focused on data privacy during training, and ignored privacy during inference.

Numerous cloud-based services are provided to help customers develop and deploy deep learning applications. When a customer deploys a deep learning model in the cloud and serves it to end-users, it is important to be able to verify that the deployed model has not been tampered with. In this paper, we propose a novel and practical methodology to verify the integrity of remote deep learning models, with only black-box access to the target models. Specifically, we define Sensitive-Sample fingerprints, which are a small set of human unnoticeable transformed inputs that make the model outputs sensitive to the model's parameters. Even small model changes can be clearly reflected in the model outputs. Experimental results on different types of model integrity attacks show that we proposed approach is both effective and efficient. It can detect model integrity breaches with high accuracy (>99.95%) and guaranteed zero false positives on all evaluated attacks. Meanwhile, it only requires up to 103× fewer model inferences, compared with non-sensitive samples.

Cache side-channel attacks aim to breach the confidentiality of a computer system and extract sensitive secrets through CPU caches. In the past years, different types of side-channel attacks targeting a variety of cache architectures have been demonstrated. Meanwhile, different defense methods and systems have also been designed to mitigate these attacks. However, quantitatively evaluating the effectiveness of these attacks and defenses has been challenging. We propose a generic approach to evaluating cache side-channel attacks and defenses. Specifically, our method builds a deep neural network with its inputs as the adversary's observed information, and its outputs as the victim's execution traces. By training the neural network, the relationship between the inputs and outputs can be automatically discovered. As a result, the prediction accuracy of the neural network can serve as a metric to quantify how much information the adversary can obtain correctly, and how effective a defense solution is in reducing the information leakage under different attack scenarios. Our evaluation suggests that the proposed method can effectively evaluate different attacks and defenses.

A program's use of CPU caches may reveal its memory access pattern and thus leak sensitive information when the program performs secret-dependent memory accesses. In recent studies, it has been demonstrated that cache side-channel attacks that extract secrets by observing the victim program's cache uses can be conducted under a variety of scenarios, among which the most concerning are cross-VM attacks and those against SGX enclaves. In this paper, we propose a mechanism that leverages hardware transactional memory (HTM) to enable software programs to defend themselves against various cache side-channel attacks. We observe that when the HTM is implemented by retrofitting cache coherence protocols, as is the case of Intel's Transactional Synchronization Extensions, the cache interference that is necessary in cache side-channel attacks will inevitably terminate hardware transactions. We provide a systematic analysis of the security requirements that a software-only solution must meet to defeat cache attacks, propose a software design that leverages HTM to satisfy these requirements and devise several optimization techniques in our implementation to reduce performance impact caused by transaction aborts. The empirical evaluation suggests that the performance overhead caused by the HTM-based solution is low.

Hardware security features need to strike a careful balance between design intrusiveness and completeness of methods. In addition, they need to be flexible, as security threats continuously evolve. To help address these requirements, this paper proposes a novel framework where Record and Deterministic Replay (RnR) is used to complement hardware security features. We call the framework RnR-Safe. RnR-Safe reduces the cost of security hardware by allowing it to be less precise at detecting attacks, potentially reporting false positives. This is because it relies on on-the-fly replay that transparently verifies whether the alarm is a real attack or a false positive. RnR-Safe uses two replayers: an always-on, fast Checkpoint replayer that periodically creates checkpoints, and a detailed-analysis Alarm replayer that is triggered when there is a threat alarm. As an example application, we use RnR-Safe to thwart Return Oriented Programming (ROP) attacks, including on the Linux kernel. Our design augments the Return Address Stack (RAS) with relatively inexpensive hardware. We evaluate RnR-Safe using a variety of workloads on virtual machines running Linux. We find that RnR-Safe is very effective. Thanks to the judicious RAS hardware extensions and hypervisor changes, the checkpointing replayer has an execution speed comparable to the recorded execution. Also, the alarm replayer needs to handle very few false positives.

The papers in this special section focus on security in computer architectures. Computer architectures are profoundly affected by a new security landscape, caused by the dramatic evolution of information technology over the past decade. First, secure computer architectures have to support a wide range of security applications that extend well beyond the desktop environment, and that also include handheld, mobile, and embedded architectures, as well as high-end computing servers. Second, secure computer architectures have to support new applications of information security and privacy, as well as new information security standards. Third, secure computer architectures have to be protected and be tamperresistant at multiple abstraction levels, covering network, software, and hardware. This Special Section in Transactions on Computers aims to capture this evolving landscape of secure computing architectures, to build a vision of opportunities and unresolved challenges.

Cloud customers need assurances regarding the security of their virtual machines (VMs), operating within an Infrastructure as a Service (IaaS) cloud system. This is complicated by the customer not knowing where his VM is executing, and on the semantic gap between what the customer wants to know versus what can be measured in the cloud. We present CloudMonatt, an architecture for monitoring a VM's security health. We show a full prototype based on the OpenStack open source cloud software. We also verify CloudMonatt to show that there are no security vulnerabilities that could allow an attacker to subvert its protection. As such, we conduct a systematic security verification of CloudMonatt. We model and verify the network protocols within the distributed system, as well as interactions of hardware/software modules inside the cloud server. Our results show that CloudMonatt is capable of delivering this monitoring and attestation service to customers in an unforgeable and reliable manner.

In cloud computing, network Denial of Service (DoS) attacks are well studied and defenses have been implemented, but severe DoS attacks on a victim's working memory by a single hostile VM are not well understood. Memory DoS attacks are Denial of Service (or Degradation of Service) attacks caused by contention for hardware memory resources on a cloud server. Despite the strong memory isolation techniques for virtual machines (VMs) enforced by the software virtualization layer in cloud servers, the underlying hardware memory layers are still shared by the VMs and can be exploited by a clever attacker in a hostile VM co-located on the same server as the victim VM, denying the victim the working memory he needs. We first show quantitatively the severity of contention on different memory resources. We then show that a malicious cloud customer can mount low-cost attacks to cause severe performance degradation for a Hadoop distributed application, and 38X delay in response time for an E-commerce website in the Amazon EC2 cloud. Then, we design an effective, new defense against these memory DoS attacks, using a statistical metric to detect their existence and execution throttling to mitigate the attack damage. We achieve this by a novel re-purposing of existing hardware performance counters and duty cycle modulation for security, rather than for improving performance or power consumption. We implement a full prototype on the OpenStack cloud system. Our evaluations show that this defense system can effectively defeat memory DoS attacks with negligible performance overhead.

Denial of service (DOS) attacks are a serious threat to network security. These attacks are often sourced from virtual machines in the cloud, rather than from the attacker's own machine, to achieve anonymity and higher network bandwidth. Past research focused on analyzing traffic on the destination (victim's) side with predefined thresholds. These approaches have significant disadvantages. They are only passive defenses after the attack, they cannot use the outbound statistical features of attacks, and it is hard to trace back to the attacker with these approaches. In this paper, we propose a DOS attack detection system on the source side in the cloud, based on machine learning techniques. This system leverages statistical information from both the cloud server's hypervisor and the virtual machines, to prevent network packages from being sent out to the outside network. We evaluate nine machine learning algorithms and carefully compare their performance. Our experimental results show that more than 99.7% of four kinds of DOS attacks are successfully detected. Our approach does not degrade performance and can be easily extended to broader DOS attacks.

Authentication of smartphone users is important because a lot of sensitive data is stored in the smartphone and the smartphone is also used to access various cloud data and services. However, smartphones are easily stolen or co-opted by an attacker. Beyond the initial login, it is highly desirable to re-authenticate end-users who are continuing to access security-critical services and data. Hence, this paper proposes a novel authentication system for implicit, continuous authentication of the smartphone user based on behavioral characteristics, by leveraging the sensors already ubiquitously built into smartphones. We propose novel context-based authentication models to differentiate the legitimate smartphone owner versus other users. We systematically show how to achieve high authentication accuracy with different design alternatives in sensor and feature selection, machine learning techniques, context detection and multiple devices. Our system can achieve excellent authentication performance with 98.1% accuracy with negligible system overhead and less than 2.4% battery consumption.

Authentication of smartphone users is important because a lot of sensitive data is stored in the smartphone and the smartphone is also used to access various cloud data and services. However, smartphones are easily stolen or co-opted by an attacker. Beyond the initial login, it is highly desirable to re-authenticate end-users who are continuing to access security-critical services and data. Hence, this paper proposes a novel authentication system for implicit, continuous authentication of the smartphone user based on behavioral characteristics, by leveraging the sensors already ubiquitously built into smartphones. We propose novel context-based authentication models to differentiate the legitimate smartphone owner versus other users. We systematically show how to achieve high authentication accuracy with different design alternatives in sensor and feature selection, machine learning techniques, context detection and multiple devices. Our system can achieve excellent authentication performance with 98.1% accuracy with negligible system overhead and less than 2.4% battery consumption.

We present CloudShelter, an architecture to protect virtual machines' memory availability from undesired resource contention on the cloud servers. We introduce a new micro-architectural metric: Memory Round Trip Time, to quantify VMs' memory QoS. Using this metric, (1) CloudShelter defines new QoS options for customers when launching VMs. These options can guarantee VMs' memory QoS at different levels even when they face intensive contention with co-located VMs; (2) CloudShelter periodically monitors VMs' memory QoS at runtime: once QoS violations against customers' demands are detected, CloudShelter places this VM into an isolated environment to eliminate contention. CloudShelter can reduce 30.1% performance interference from LLC/DRAM contention and 81.6% interference from bus contention1.

The risks of publishing privacy-sensitive data have received considerable attention recently. Several de-anonymization attacks have been proposed to re-identify individuals even if data anonymization techniques were applied. However, there is no theoretical quantification for relating the data utility that is preserved by the anonymization techniques and the data vulnerability against de-anonymization attacks. In this paper, we theoretically analyze the de-anonymization attacks and provide conditions on the utility of the anonymized data (denoted by anonymized utility) to achieve successful de-anonymization. To the best of our knowledge, this is the first work on quantifying the relationships between anonymized utility and de-anonymization capability. Unlike previous work, our quantification analysis requires no assumptions about the graph model, thus providing a general theoretical guide for developing practical de-anonymization/anonymization techniques. Furthermore, we evaluate state-of-the-art de-anonymization attacks on a real-world Facebook dataset to show the limitations of previous work. By comparing these experimental results and the theoretically achievable de-anonymization capability derived in our analysis, we further demonstrate the ineffectiveness of previous de-anonymization attacks and the potential of more powerful de-anonymization attacks in the future.

Security-critical data can leak through very unexpected side channels, making side-channel attacks very dangerous threats to information security. Of these, cache-based side-channel attacks are some of the most problematic. This is because caches are essential for the performance of modern computers, but an intrinsic property of all caches - the different access times for cache hits and misses - is the property exploited to leak information in time-based cache side-channel attacks. Recently, different secure cache architectures have been proposed to defend against these attacks. However, we do not have a reliable method for evaluating a cache's resilience against different classes of cache side-channel attacks, which is the goal of this paper.

We propose Secure Pick Up (SPU), a convenient, lightweight, in-device, non-intrusive and automatic-learning system for smartphone user authentication. Operating in the background, our system implicitly observes users' phone pick-up movements, the way they bend their arms when they pick up a smartphone to interact with the device, to authenticate the users.

Cache side channel attacks are serious threats to multi-tenant public cloud platforms. Past work showed how secret information in one virtual machine (VM) can be extracted by another co-resident VM using such attacks. Recent research demonstrated the feasibility of high-bandwidth, low-noise side channel attacks on the last-level cache (LLC), which is shared by all the cores in the processor package, enabling attacks even when VMs are scheduled on different cores. This paper shows how such LLC side channel attacks can be defeated using a performance optimization feature recently introduced in commodity processors. Since most cloud servers use Intel processors, we show how the Intel Cache Allocation Technology (CAT) can be used to provide a system-level protection mechanism to defend from side channel attacks on the shared LLC. CAT is a way-based hardware cache-partitioning mechanism for enforcing quality-of-service with respect to LLC occupancy. However, it cannot be directly used to defeat cache side channel attacks due to the very limited number of partitions it provides. We present CATalyst, a pseudo-locking mechanism which uses CAT to partition the LLC into a hybrid hardware-software managed cache. We implement a proof-of-concept system using Xen and Linux running on a server with Intel processors, and show that LLC side channel attacks can be defeated. Furthermore, CATalyst only causes very small performance overhead when used for security, and has negligible impact on legacy applications.

To access sensitive information, some recent advanced attacks have been successful in exploiting implicit flows in a program in which sensitive data affects the control path and in turn affects other data. To track the sensitive data through implicit flows, several software and hardware based approaches have been proposed, but they suffer from the non-negligible performance overhead. In this paper, we propose a hardware tracking engine for implicit flow, called the implicit flow tracking unit (IFTU). By adopting the tracking scheme for implicit flow and mapping it to the specialized hardware, our solution can efficiently perform the implicit flow tracking with reasonable area costs.

Discusses the current state of the journal, reports on current and future areas of exploration and research, and presents new editors.

The widespread use of smartphones gives rise to new security and privacy concerns. Smartphone thefts account for the largest percentage of thefts in recent crime statistics. Using a victim's smartphone, the attacker can launch impersonation attacks, which threaten the security of the victim and other users in the network. Our threat model includes the attacker taking over the phone after the user has logged on with his password or pin. Our goal is to design a mechanism for smartphones to better authenticate the current user, continuously and implicitly, and raise alerts when necessary. In this paper, we propose a multi-sensors-based system to achieve continuous and implicit authentication for smartphone users. The system continuously learns the owner's behavior patterns and environment characteristics, and then authenticates the current user without interrupting user-smartphone interactions. Our method can adaptively update a user's model considering the temporal change of user's patterns. Experimental results show that our method is efficient, requiring less than 10 seconds to train the model and 20 seconds to detect the abnormal user, while achieving high accuracy (more than 90%). Also the combination of more sensors provide better accuracy. Furthermore, our method enables adjusting the security level by changing the sampling rate.

Cloud customers need guarantees regarding the security of their virtual machines (VMs), operating within an Infrastructure as a Service (IaaS) cloud system. This is complicated by the customer not knowing where his VM is executing, and on the semantic gap between what the customer wants to know versus what can be measured in the cloud. We present an architecture for monitoring a VM's security health, with the ability to attest this to the customer in an unforgeable manner. We show a concrete implementation of property-based attestation and a full prototype based on the OpenStack open source cloud software.

We present an effective implementation of the Prime+Probe side-channel attack against the last-level cache. We measure the capacity of the covert channel the attack creates and demonstrate a cross-core, cross-VM attack on multiple versions of GnuPG. Our technique achieves a high attack resolution without relying on weaknesses in the OS or virtual machine monitor or on sharing memory between attacker and victim.

Caches are integral parts in modern computers; they leverage the memory access patterns of a program to mitigate the gap between the fast processors and slow memory components.

Side-channel attacks try to breach confidentiality and retrieve critical secrets through the side channels. Cache memories are a potential source of information leakage through side-channel attacks, many of which have been proposed. Meanwhile, different cache architectures have also been proposed to defend against these attacks. However, there are currently no means for comparing and evaluating the effectiveness of different defense solutions against these attacks.

In cloud computing, most of the computations and data in the data center do not belong to the cloud provider. This leaves owners of applications and data concerned about cyber and physical attacks which may compromise the confidentiality, integrity or availability of their applications or data. While much work has looked at protection from software (cyber) threats, very few have looked at physical attacks and physical security in data centers. In this work, we present a novel set of cyber defense strategies for physical attacks in data centers. We capitalize on the fact that physical attackers are constrained by the physical layout and other features of a data center which provide a time delay before an attacker can reach a server to launch a physical attack, even by an insider. We describe how a number of cyber defense strategies can be activated when an attack is detected, some of which can even take effect before the actual attack occurs. The defense strategies provide improved security and are more cost-effective than always-on protections in the light of the fact that on average physical attacks will not happen often -- but can be very damaging when they do occur.

This article consists of a collection of slides from the author's conference presentation on hardware security. Some of the specific topics discussed include: examples of using Moving Target Defense for Secure Hardware design (DHS/AFRL project); system performance evaluations; network security considerations; secure processors; dynamic information flow tracking; software-hardware security verification; security measurement techniques; types of security attacks; supply chain security options; hardware trojans; security CAD tools; trust management issues; cyber-physical systems; and secure software design, new problems and solutions.

Presents a collection of slides covering the following topics: system security; security threat models; security design methodology; access control practices; cryptography; and security protocols.

Presents a collection of slides covering the following topics: cyber security; software-only security; hardware support; hardware chip vendors; and hardware security.

Correctly functioning caches have been shown to leak critical secrets like encryption keys, through various types of cache side-channel attacks. This nullifies the security provided by strong encryption and allows confidentiality breaches, impersonation attacks and fake services. Hence, future cache designs must consider security, ideally without degrading performance and power efficiency. We introduce a new classification of cache side channel attacks: contention based attacks and reuse based attacks. Previous secure cache designs target only contention based attacks, and we show that they cannot defend against reuse based attacks. We show the surprising insight that the fundamental demand fetch policy of a cache is a security vulnerability that causes the success of reuse based attacks. We propose a novel random fill cache architecture that replaces demand fetch with random cache fill within a configurable neighborhood window. We show that our random fill cache does not degrade performance, and in fact, improves the performance for some types of applications. We also show that it provides information-theoretic security against reuse based attacks.

Dependability in cloud computing applications can be negatively affected by various attacks or service abuses. To come ahead of this threat, we propose an economic measure to deter attacks and various service abuses in cloud computing applications. Our proposed defense is based on requiring a service user to pay a small deposit, using digital currency, before invoking the service. Once they are done using the service, and there has been no detected abuse or attack, the deposit is paid back by the service provider to the service user. If an attack or an abuse is detected, the service user is not paid back and the service provider gets to keep the deposit. We propose the use of micro payments with a decentralized nature and small transaction fees, such as the Bit coin digital currency. Moreover, thanks to the existence of money exchanges which convert the Bit coin currency to real world currency, service providers can recoup loses when they exchange the confiscated deposits for real world currency.

In this paper we present our vision for Security on Demand in cloud computing: a system where cloud providers can offer customized security for customers' code and data throughout the term of contract. Security on demand enables security-focussed competitive service differentiation and pricing, based on a threat model that matches the customer's security requirements for the virtual machine he is leasing. It also enables a cloud provider to bring in new secure servers to the data center, and derive revenue from these servers, while still using existing servers. We show a framework where customers' security requests can be expressed and enforced by leveraging the capabilities of servers with different security architectures.

Virtualization has become a standard part of many computer systems. A key part of virtualization is the all-powerful hypervisor which manages the physical platform and can access all of its resources, including memory assigned to the guest virtual machines (VMs). Continuing releases of bug reports and exploits in the virtualization software show that defending the hypervisor against attacks is very difficult. In this work, we present hypervisor-secure virtualization - a new research direction with the goal of protecting the guest VMs from an untrusted hypervisor. We also present the HyperWall architecture which achieves hypervisor-secure virtualization, using hardware to provide the protections. HyperWall allows a hypervisor to freely manage the memory, processor cores and other resources of a platform. Yet once VMs are created, our new Confidentiality and Integrity Protection (CIP) tables protect the memory of the guest VMs from accesses by the hypervisor or by DMA, depending on the customer's specification. If a hypervisor does become compromised, e.g. by an attack from a malicious VM, it cannot be used in turn to attack other VMs. The protections are enabled through minimal modifications to the microprocessor and memory management units. Whereas much of the previous work concentrates on protecting the hypervisor from attacks by guest VMs, we tackle the problem of protecting the guest VMs from the hypervisor.

We propose a software-hardware architecture, DataSafe, that realizes the concept of self-protecting data: data that is protected by a given policy whenever it is accessed by any application -- including unvetted third-party applications. Our architecture provides dynamic instantiations of secure data compartments (SDCs), with hardware monitoring of the information flows from the compartment using hardware policy tags associated with the data at runtime. Unbypassable hardware output control prevents confidential information from being leaked out. Unlike previous hardware information flow tracking systems, DataSafe software architecture bridges the semantic gap by supporting flexible, high-level software policies for the data, seamlessly translating these policies to efficient hardware tags at runtime. Applications need not be modified to interface to these software-hardware mechanisms. DataSafe architecture is designed to prevent illegitimate secondary dissemination of protected plaintext data by authorized recipients, to track and protect data derived from sensitive data, and to provide lifetime enforcement of the confidentiality policies associated with the sensitive data.

Building a secure computing system requires careful coordination among all layers in the system from hardware to software. Even if secure by itself, a higher layer protection mechanism may be bypassed if lower layer software or hardware is vulnerable. Additionally, hardware complements software through its efficiency, tamper resistance, etc. There have been significant efforts recently in hardware communities that aim to leverage hardware strengths to secure software layers, and also to secure hardware itself. This tutorial presents some of these hardware-enhanced security techniques to the security community.

Future trustworthy computer systems should provide built-in support for at least the cornerstone security properties of confidentiality, integrity and availability. Access control can help significantly towards achieving this. However, in today's computing landscape, traditional access control implemented only in software may be either insufficient or non-optimal. We discuss some of these situations. Furthermore, fine-grained access control and usage control mechanisms implemented in software are themselves subject to attack, and may impose heavy performance overheads. Can new hardware architecture improve the security achievable by software mechanisms for access control and usage control? If so, what types of hardware support are most useful while retaining the flexibility of software protection mechanisms? What can software do, to help hardware achieve the best results?

Cloud computing is quickly becoming the platform of choice for many web services. Virtualization is the key underlying technology enabling cloud providers to host services for a large number of customers. Unfortunately, virtualization software is large, complex, and has a considerable attack surface. As such, it is prone to bugs and vulnerabilities that a malicious virtual machine (VM) can exploit to attack or obstruct other VMs -- a major concern for organizations wishing to move to the cloud. In contrast to previous work on hardening or minimizing the virtualization software, we eliminate the hypervisor attack surface by enabling the guest VMs to run natively on the underlying hardware while maintaining the ability to run multiple VMs concurrently. Our NoHype system embodies four key ideas: (i) pre-allocation of processor cores and memory resources, (ii) use of virtualized I/O devices, (iii) minor modifications to the guest OS to perform all system discovery during bootup, and (iv) avoiding indirection by bringing the guest virtual machine in more direct contact with the underlying hardware. Hence, no hypervisor is needed to allocate resources dynamically, emulate I/O devices, support system discovery after bootup, or map interrupts and other identifiers. NoHype capitalizes on the unique use model in cloud computing, where customers specify resource requirements ahead of time and providers offer a suite of guest OS kernels. Our system supports multiple tenants and capabilities commonly found in hosted cloud infrastructures. Our prototype utilizes Xen 4.0 to prepare the environment for guest VMs, and a slightly modified version of Linux 2.6 for the guest OS. Our evaluation with both SPEC and Apache benchmarks shows a roughly 1% performance gain when running applications on NoHype compared to running them on top of Xen 4.0. Our security analysis shows that, while there are some minor limitations with cur- rent commodity hardware, NoHype is a significant advance in the security of cloud computing.

Network utility maximization has been widely used to model resource allocation and network architectures. However, in practice, often it cannot be solved optimally due to complexity reasons. Thus motivated, we address the following two questions in this paper: 1) Can suboptimal utility maximization maintain queue stability? 2) Can underoptimization of utility objective function in fact benefit other network design objectives? We quantify the following intuition: A resource allocation that is suboptimal with respect to a utility maximization formulation maintains maximum flow-level stability when the utility gap is sufficiently small and information delay is bounded, and it can still provide a guaranteed size of stability region otherwise. Utility-suboptimal rate allocation can also enhance other network performance metrics, e.g., it may reduce link saturation. These results provide a theoretical support for turning attention from optimal but complex solutions of network optimization to those that are simple even though suboptimal.

New security architectures are difficult to prototype and test at the design stage. Fine-grained monitoring of the interactions between hardware, the operating system and applications is required. We have designed and prototyped a testing framework, using virtualization, that can emulate the behavior of new hardware mechanisms in the virtual CPU and can perform a wide range of hardware and software attacks on the system under test.

Many applications require protection of secret or sensitive information, from sensor nodes and embedded applications to large distributed systems. The confidentiality of data can be protected by encryption using symmetric-key ciphers, and the integrity of the data can be ensured by using a cryptographic hash function to calculate a "digital fingerprint." In this paper, we propose reconfigurable FPGA hardware components that enable rapid deployment of cryptographic and other algorithms. The novelty of our hardware components is in their general-purpose design which enables easy mappings of algorithms to allow customizations of data protection for different usage scenarios. Since we utilize only a small part of an FPGA chip, our design can be readily integrated with other processing needs of a mobile device, a sensor node or a System-on-Chip. Important block ciphers like the Advanced Encryption Standard (AES) as well as advanced cryptographic hash algorithms like Whirlpool map well onto our general-purpose components. Our solution facilitates easy hardware implementation of customizable encryption and hashing solutions, with area and speed performance comparable to custom FPGA implementations targeted at a specific cipher or hash algorithm. We achieve the best efficiency in Mbps/slice for Whirlpool. Furthermore, the components that we have proposed can be used for many other applications - not just for implementing block ciphers and cryptographic hash functions.

We present Bastion, a new hardware-software architecture for protecting security-critical software modules in an untrusted software stack. Our architecture is composed of enhanced microprocessor hardware and enhanced hypervisor software. Each trusted software module is provided with a secure, fine-grained memory compartment and its own secure persistent storage area. Bastion is the first architecture to provide direct hardware protection of the hypervisor from both software and physical attacks, before employing the hypervisor to provide the same protection to security-critical OS and application modules. Our implementation demonstrates the feasibility of bypassing an untrusted commodity OS to provide application security and shows better security with higher performance when compared to the Trusted Platform Module (TPM), the current industry state-of-the-art security chip. We provide a proof-of-concept implementation on the OpenSPARC platform.

Cloud computing is a disruptive trend that is changing the way we use computers. The key underlying technology in cloud infrastructures is virtualization -- so much so that many consider virtualization to be one of the key features rather than simply an implementation detail. Unfortunately, the use of virtualization is the source of a significant security concern. Because multiple virtual machines run on the same server and since the virtualization layer plays a considerable role in the operation of a virtual machine, a malicious party has the opportunity to attack the virtualization layer. A successful attack would give the malicious party control over the all-powerful virtualization layer, potentially compromising the confidentiality and integrity of the software and data of any virtual machine. In this paper we propose removing the virtualization layer, while retaining the key features enabled by virtualization. Our NoHype architecture, named to indicate the removal of the hypervisor, addresses each of the key roles of the virtualization layer: arbitrating access to CPU, memory, and I/O devices, acting as a network device (e.g., Ethernet switch), and managing the starting and stopping of guest virtual machines. Additionally, we show that our NoHype architecture may indeed be "no hype" since nearly all of the needed features to realize the NoHype architecture are currently available as hardware extensions to processors and I/O devices.

Secure communications in wireless ad hoc networks require setting up end-to-end secret keys for communicating node pairs. Due to physical limitations and scalability requirements, full key-connectivity can not be achieved by key pre-distribution. In this paper, we develop an analytical framework for the on-demand key establishment approach. We propose a novel security metric, called REM resilience vector to quantify the resilience of any key establishment schemes against Revealing, Erasure, and Modification (REM) attacks. Our analysis shows that previous key establishment schemes are vulnerable under REM attacks. Relying on the new security metric, we prove a universal bound on achievable REM resilience vectors for any on-demand key establishment scheme. This bound that characterizes the optimal security performance analytically is shown to be tight, as we propose a REM-resilient key establishment scheme which achieves any vector within this bound. In addition, we develop a class of low complexity key establishment schemes which achieve nearly-optimal REM-attack resilience.

This paper describes a new basis for the implementation of the shifter functional unit in microprocessors that can implement new advanced bit manipulations as well as standard shifter operations. Our design is based on the inverse butterfly and butterfly data path circuits, rather than the barrel shifter or log-shifter designs currently used. We show how this new shifter can implement the standard shift and rotate operations, as well as more advanced extract, deposit, and mix operations found in some processors. Furthermore, it can perform important new classes of even more advanced bit manipulation instructions like arbitrary bit permutations, bit gather (or parallel extract), and bit scatter (or parallel deposit) instructions. Thus, our new functional unit performs the functionality of three functional units-the basic shifter, the multimedia-mix unit, and the advanced bit manipulation functional unit, while having a latency only slightly longer than that of the log-shifter. For performing only the existing functions of a shifter, it has significantly smaller area.

Registers in processors generally contain words or, with the addition of multimedia extensions, short vectors of subwords of bytes or 16-bit elements. In this paper, we view the contents of registers as vectors or matrices of individual bits. However, the facility to operate efficiently on the bit-level is generally lacking. A commodity processor usually only has logical and shift instructions and occasionally population count instructions. Perhaps the most powerful primitive bit-level operation is the bit matrix multiply (BMM) instruction, currently found only in supercomputers like Cray. This instruction multiplies two ntimesn bit matrices. In this paper, we show the power of BMM. We propose and analyze new processor instructions that implement simpler BMM primitive operations more suitable for a commodity processor. We show the impact of BMM on the performance of critical application kernels and discuss its hardware cost.

Not too bad. A rate allocation that is suboptimal with respect to a utility maximization formulation still maintains the maximum flow-level stability when the utility gap is sufficiently small, and provides a minimum size of stability region otherwise. Utility-suboptimal allocation may also enhance other network performance metrics, e.g., it may increase network throughput and reduce link saturation. Quantifying these intuitions, this paper provides a theoretical support for turning attention from optimal but complex solutions of network optimization to those that are simple even though suboptimal.

Caches ideally should have low miss rates and short access times, and should be power efficient at the same time. Such design goals are often contradictory in practice. Recent findings on efficient attacks based on information leakage in caches have also brought the security issue up front. Design for security introduces even more restrictions and typically leads to significant performance degradation. This paper presents a novel cache architecture that can simultaneously achieve the above goals. Specifically, cache miss rates are reduced with dynamic remapping and longer cache indices, access-time overhead overcome with astute low-level circuit design, and information leakage thwarted by a security-aware cache replacement algorithm together with the performance enhancing mechanisms. We present both theoretical analysis and experimental results, using the SPEC2000 suite to evaluate the cache miss behavior, and CACTI and HSPICE to validate the circuit design. Our results show that the proposed cache architecture has low miss rates comparable to a highly associative cache and short access times and power efficiency close to that of a direct-mapped cache. At the same time it can thwart cache-based software side-channel attacks, providing both legacy and security-enhanced software a much higher degree of security. Additional benefits that the proposed cache architecture can bring, like fault tolerance and hot-spot mitigation, are also discussed briefly.

This paper describes a new basis for the implementation of a shifter functional unit. We present a design based on the inverse butterfly and butterfly datapath circuits that performs the standard shift and rotate operations, as well as more advanced extract, deposit and mix operations found in some processors. Additionally, it also supports important new classes of even more advanced bit manipulation instructions recently proposed: these include arbitrary bit permutations, bit scatter and bit gather instructions. The new functional unit's datapath is comparable in latency to that of the classic barrel shifter. It replaces two existing functional units-shifter and mix-with a much more powerful one.

Using small, pre-computed tables is a well-known technique for improving the performance of expensive computations with small operands. However, as the performance gap between CPU and memory continues to increase, table lookup in main memory may no longer be beneficial. Instead of doing table lookups in memory, this paper proposes table lookup instruction support to accelerate Rabin fingerprinting and Reed-Solomon erasure coding over Galois fields. Both are core computations in emerging main-stream systems such as bandwidth optimized protocol engines, capacity optimized storage systems, and content-distribution networks. We show that the proposed instructions are both beneficial and easy to implement. A simple table lookup instruction that addresses four 256-entry tables in parallel can speed up Rabin fingerprinting and anchoring by a factor of 2.6 and Reed-Solomon coding by a factor of 1.5.

We propose minimalist new hardware additions to a microprocessor chip that protect cryptographic keys in portable computing devices which are used in the field but owned by a central authority. Our authority-mode architecture has trust rooted in two critical secrets: a Device Root Key and a Storage Root Hash, initialized in the device by the trusted authority. Our architecture protects trusted software, bound to the device, which can use the root secrets to protect other sensitive information for many different usage scenarios. We describe a detailed usage scenario for crisis response, where first responders are given transient access to third-party sensitive information which can be securely accessed during a crisis and reliably revoked after the crisis is over.

In lightweight mobile ad hoc networks, both probabilistic and deterministic key management schemes are fragile to node fabrication attacks. Our simulation results show that the Successful Attack Probability (SAP) can be as high as 42.6% with the fabrication of only 6 copies from captured nodes comprising only 3% of all nodes. In this paper, we propose two low-cost secure-architecture-based techniques to improve the security against such node fabrication attacks. Our new architectures, specifically targeted at the sensor-node platform, protect long-term keys using a root of trust embedded in the hardware System-on-a-Chip (SoC). This prevents an adversary from extracting these protected long-term keys from a captured node to fabricate new nodes. The extensive simulation results show that the proposed architecture can significantly decrease the SAP and increase the security level of key management for mobile ad hoc networks.

Known covert channel based on splitting algorithms in Medium Access Control (MAC) protocols requires the receiver's knowledge of the sender's identity. In this paper we present a new covert channel that does not have this restriction. In such a channel, multiple senders may operate independently without knowing each other, and the receiver can learn the transmitted information without knowing the identity of any covert sender a priori. These properties make the channel robust to malfunctioning senders, and more importantly help protect the secrecy of senders' identity which is essential for covert communications. We also analyze the capacity of our proposed covert channel.

Software cache-based side channel attacks are a serious new class of threats for computers. Unlike physical side channel attacks that mostly target embedded cryptographic devices, cache-based side channel attacks can also undermine general purpose systems. The attacks are easy to perform, effective on most platforms, and do not require special instruments or excessive computation power. In recently demonstrated attacks on software implementations of ciphers like AES and RSA, the full key can be recovered by an unprivileged user program performing simple timing measurements based on cache misses.

It is widely believed that although being more complex, a probabilistic key predistribution scheme is much more resilient against node capture than a deterministic one in lightweight wireless ad hoc networks. Backed up by the surprisingly large successful attack probabilities computed in this paper, we show that the probabilistic approaches have only limited performance advantages over deterministic approaches. We first consider a static network scenario as originally considered in the seminal paper by Eschenauer and Gligor [1], where any node capture happens after the establishment of all pairwise links, and show that the deterministic approach can achieve a performance as good as the probabilistic one. Furthermore in a mobile network, the probabilistic key management as described in [1] can lead to a successful attack probability of one order of magnitude larger than the one in a static network.

Cryptographic algorithms, irrespective of their theoretical strength, can be broken through weaknesses in their implementations. The most successful of these attacks are side-channel attacks which exploit unintended information leakage, e.g., timing information, power consumption, etc., from the implementation to extract the secret key. We propose a novel framework for implementing side-channel attacks where the attack is modeled as a search problem which takes the leaked information as its input, and deduces the secret key by using a satisfiability solver, a powerful Boolean reasoning technique. This approach can substantially enhance the scope of side-channel attacks by allowing a potentially wide range of internal variables to be exploited (not just those that are trivially related to the key). The proposed technique is particularly suited for attacking cryptographic software implementations which may inadvertently expose the values of intermediate variables in their computations (even though, they are very careful in protecting secret keys through the use of on-chip key generation and storage). We demonstrate our attack on standard software implementations of three popular cryptographic algorithms: DES, 3DES, and AES. Our attack technique is automated and does not require mathematical expertise on the part of the attacker

Security protocols, such as IPSec and SSL, are being increasingly deployed in the context of networked embedded systems. The resource-constrained nature of embedded systems and, in particular, the modest capabilities of embedded processors make it challenging to achieve satisfactory performance while executing security protocols. A promising approach for improving performance in embedded systems is to use application-specific instruction set processors that are designed based on configurable and extensible processors. In this paper, we perform a comprehensive performance analysis of the IPSec protocol on a state-of-the-art configurable and extensible embedded processor (Xtensa from Tensilica Inc.). We present performance profiles of a lightweight embedded IPSec implementation running on the Xtensa processor, and examine in detail the various factors that contribute to the processing latencies, including cryptographic and protocol processing. In order to improve the efficiency of IPSec processing on embedded devices, we then study the impact of customizing an embedded processor by synergistically 1) configuring architectural parameters, such as instruction and data cache sizes, processor-memory interface width, write buffers, etc., and 2) extending the base instruction set of the processor using custom instructions for both cryptographic and protocol processing. Our experimental results demonstrate that upto 3.2times speedup in IPSec processing is possible over a popular embedded IPSec software implementation

Information leakage through covert channels and side channels is becoming a serious problem, especially when these are enhanced by modern processor architecture features. We show how processor architecture features such as simultaneous multithreading, control speculation and shared caches can inadvertently accelerate such covert channels or enable new covert channels and side channels. We first illustrate the reality and severity of this problem by describing concrete attacks. We identify two new covert channels. We show orders of magnitude increases in covert channel capacities. We then present two solutions, Selective Partitioning and the novel random permutation cache (RPCache). The RPCache can thwart most cache-based software side channel attacks, with minimal hardware costs and negligible performance impact

Current microprocessor instruction set architectures are word oriented, with some subword support. Many important applications, however, can realize substantial performance benefits from bitoriented instructions. We propose the parallel extract (pex) and parallel deposit (pdep) instructions to accelerate compressing and expanding selections of bits. We show that these instructions can be implemented by the fast inverse butterfly and butterfly network circuits. We evaluate latency and area costs of alternative functional units for implementing subsets of advanced bit manipulation instructions. We show applications exhibiting significant speedup, 3.41x on average over a basic RISC architecture, and 2.48x on average over an instruction set architecture (ISA) that supports extract and deposit instructions.

On public communication networks such as the Internet, data confidentiality can be provided by symmetric key ciphers. One of the most common operations used in symmetric key ciphers are table lookups. These frequently constitute the largest fraction of the execution time when the ciphers are implemented using a typical RISC-like instruction set. To accelerate these table lookups, we describe a new hardware module, called PTLU (for parallel table lookup), which consists of multiple lookup tables that can be accessed in parallel. A novel combinational circuit included in the module can optionally perform simple logic operations on the data read from the tables. On a single issue 64-bit RISC processor, PTLU provides maximum speedups of 7.7x for AES and 5.4x for DES. With wordsize scaling, PTLU speedups are significantly higher than that available through more conventional architectural techniques such as superscalar or VUW execution.

We propose "secret-protected (SP)" architecture to enable secure and convenient protection of critical secrets for a given user in an on-line environment. Keys are examples of critical secrets, and key protection and management is a fundamental problem - often assumed but not solved /sup n/derlying the use of cryptographic protection of sensitive files, messages, data and programs. SP-processors contain a minimalist set of architectural features that can be built into a general-purpose microprocessor to provide protection of critical secrets and their computations, without expensive or inconvenient auxiliary hardware. SP-architecture also requires a trusted software module, a few modifications to the operating system, a secure I/O path to the user, and a secure installation process. Unique aspects of our architecture include: decoupling of user secrets from the devices, enabling users to securely access their keys from different networked computing devices; the use of symmetric master keys rather than more costly public-private key pairs; and the avoidance of any permanent or factory-installed device secrets.

The growing number of instances of breaches in information security in the last few years has created a compelling case for efforts towards secure electronic systems. Embedded systems, which will be ubiquitously used to capture, store, manipulate, and access data of a sensitive nature, pose several unique and interesting security challenges. Security has been the subject of intensive research in the areas of cryptography, computing, and networking. However, despite these efforts, security is often mis-construed by designers as the hardware or software implementation of specific cryptographic algorithms and security protocols. In reality, it is an entirely new metric that designers should consider throughout the design process, along with other metrics such as cost, performance, and power..This paper is intended to introduce embedded system designers and design tool developers to the challenges involved in designing secure embedded systems. We attempt to provide a unified and holistic view of embedded system security by first analyzing the typical functional security requirements for embedded systems from an end-user perspective. We then identify the implied challenges for embedded system architects, as well as hardware and software designers (e.g., tamper-resistant embedded system design, processing requirements for security, impact of security on battery life for battery-powered systems, etc.). We also survey solution techniques to address these challenges, drawing from both current practice and emerging research, and identify open research problems that will require innovations in embedded system architecture and design methodologies.

Many computer security threats involve execution of unauthorized foreign code on the victim computer. Viruses, network and email worms, Trojan horses, backdoor programs used in denial of service attacks are a few examples. In this paper, we present an architectural technique, which we call runtime execution monitoring (REM), to detect program flow anomalies associated with such malicious code. The key idea in REM is the verification of program code at the hash block (similar to a basic block) level. This is achieved by pre-computing keyed hashes (HMACs) for each hash block during program installation, and then verifying these values during program execution. By verifying program code integrity at the hash block level, REM can monitor instructions whose behavior is typically exploited by malicious code, such as branch, call, return instructions. Performance degradation with REM averages 6.4% on our benchmark programs, which can be reduced to under 5% by increasing the size of the L1 instruction cache.

3D graphics is an important component in the workload of today's computing platforms. Many ISA extensions for 3D graphics have been proposed and implemented. We describe PLX FP, a new floating-point extension to the PLX architecture, designed to support very efficiently the essential operations needed for the 3D graphics pipeline. Very high performance floating-point 3D graphics processing is achieved, using a low-cost PLX processor.

Summary form only given. Approaches to cyber security have focused on reactive measures, perimeter security and software implementations. In contrast, we propose a proactive approach to cyber security, where every component, hardware, software or networking, has secure or trustworthy operation as a primary design goal. Architecture for cyber security must be defined at many levels. At the foundational level, if we want core hardware and software to be more responsible for cyber security, what architectural features must be included? How do we translate business and personal security needs, in addition to military and national security needs, into scalable technology features? In this talk, we focus on processors as the engines of the Information Age upon which all software runs. What does it mean for a processor to be security-aware? We illustrate with a few examples. In the area of e-commerce and e-business, we discuss how the processor can make cyber transactions more trustworthy. Can cryptography algorithms, and security protocols, be radically accelerated to provide needed confidentiality, data integrity, digital signatures and user authentication, in an automatic and painless way? In the area of service availability, we discuss whether the processor can provide defenses against misuse of computers by malicious third parties. Are there ways processor architecture can be enhanced to detect, prevent or mitigate potentially disastrous Distributed Denial of Service attacks? What are the processor and software vendors’ responsibilities in providing best-effort security features? What are the technical, policy and social challenges in digital rights management (DRM) with regard to built-in anti-piracy mechanisms? Many of these issues have legal, economic, social and ethical aspects, in addition to technological possibilities and limitations. We propose that it is time to consider how technology in general, and processor architecture in particular, can be designed to facilitate greater security and trust in cyberspace transactions and services.

Symmetric-key block ciphers encrypt data, providing data confidentiality over the public Internet. For interoperability reasons, it is desirable to support a variety of symmetric-key ciphers efficiently. We show the basic operations performed by a variety of symmetric-key cryptography algorithms. Of these basic operations, only bit permutation is very slow using existing processors, followed by integer multiplication. New instructions have been proposed recently to accelerate bit permutations in general-purpose processors, reducing the instructions needed to achieve an arbitrary n-bit permutation from O(n) to O(log(n)). However, the serial data-dependency between these log(n) permutation instructions prevents them from being executed in fewer than log(n) cycles, even on superscalar processors. Since application specific instruction processors (ASIPs) have fewer constraints on maintaining standard processor datapath and control conventions, can we achieve even faster permutations? We propose six alternative ASIP approaches to achieve arbitrary 64 bit permutations in one or two cycles, using new BFLY and IBFLY instructions. This reduction to one or two cycles is achieved without increasing the cycle time. We compare the latencies of different permutation units in a technology independent way to estimate cycle time impact. We also compare the alternative ASIP architectures and their efficiency in performing arbitrary 64 bit permutations.

We propose two new instructions, swperm and sieve, that can be used to efficiently complete an arbitrary bit-level permutation of an n-bit word with or without repetitions. Permutations with repetitions are rearrangements of an ordered set in which elements may replace other elements in the set; such permutations are useful in cryptographic algorithms. On a four-way superscalar processor, we can complete an arbitrary 64-bit permutation with repetitions of 1-bit subwords in 11 instructions and only four cycles using the two proposed instructions. For subwords of size 4 bits or greater, we can perform an arbitrary permutation with repetitions of a 64-bit register in a single cycle using a single swperm instruction. This improves upon previous results by requiring fewer instructions to permute 4-bit or larger subwords packed in a 64-bit register and fewer execution cycles for 1-bit subwords on wide superscalar processors. We also demonstrate that we can accelerate the performance of the popular DES block cipher using the proposed instructions. We obtain a DES performance improvement of at least 55% in constrained embedded environments and an improvement of 71% on a four-way superscalar processor when applying DES as a cryptographic hash function.

Multimedia processing in software has been significantly accelerated by the addition of subword-parallel instructions to the instruction set architectures (ISAs) of modem microprocessors. While some of these multimedia instructions are simple and effective, others are very complex, requiring large, special-purpose functional units that are not practical for constrained environments such as handheld multimedia information appliances. For such environments, low-power and low-cost are as important as the high performance required for real-time multimedia processing and the general-purpose programmability required to support an ever growing range of applications. In this paper, we introduce PLX, a concise ISA that selects the most useful features from the first two generations of multimedia instructions added to microprocessors, and explores new ISA features for high-performance yet low-cost multimedia processing with small footprint processors. PLX is unique in that it is designed from scratch as a fully subword-parallel architecture with novel features like datapath scalability from 32-bit to 128-bit words, and a new definition of predication for reducing conditional branches. We illustrate the use of PLX's architectural features with four frequently used multimedia kernels: discrete cosine transform, pixel padding, clip test and median filter. Our performance results show that a 64-bit PLX implementation achieves significant speedups compared to a basic 64-bit RISC processor and to IA-32 processors with MMX and SSE multimedia extensions. PLX's datapath scalability feature often provides an additional 2x speedup in a cost-effective way.

Subword parallelism has succeeded in accelerating many multimedia applications. Subword permutation instructions have been proposed to efficiently rearrange subwords in or among registers. Bit-level permutation instructions have also been proposed recently for their importance in cryptography. However, important algorithms, especially those with many conditional control dependencies such as sorting, have not exploited the advantage of subword parallel instructions. In this paper, we show how one of the bit permutation instructions, GRP, can be used for fast sorting. In the process, we demonstrate the versatility of this permutation instruction for uses other than bit permutations. This versatility is important in considering the addition of a new instruction to a general-purpose processor. The results show that our sorting methods have a significant speedup even when compared with the fastest sorting algorithms. We also discuss the hardware implementation of the GRP instruction and compare its latency to a typical processor's cycle time.

PLX is a small, fully subword-parallel instruction set architecture (ISA) designed for very fast multimedia processing, especially in constrained environments requiring low cost and power, such as handheld multimedia information appliances. In PLX, we select the most useful multimedia instructions added previously to microprocessors. We also introduce a few novel features: a new definition of predication requiring very few bits in each predicated instruction, and datapath scalability from 32-bit to 128-bit words, which allows different degrees of subword parallelism without any changes to the ISA. Performance results from basic multimedia kernels testify to PLX's superiority for multimedia processing.

Encryption algorithms commonly use table lookups to perform substitution, which is a confusion primitive. The use of table lookups in this way is especially common in the more recent encryption algorithms, such as the AES finalists like Twofish and MARS, and the AES winner, Rijndael. Workload characterization studies indicate that these algorithms spend a significant fraction of their execution cycles on performing these table lookups, more specifically on effective address calculations. The study considers the five AES finalists (MARS, RC6, Rijndael, Serpent and Twofish) and studies the effect of different addressing modes that can be used to calculate the effective addresses during the table lookups. We report our findings for four different addressing modes and on varying width EPIC processors. The results indicate that speedups exceeding 2/spl times/ can be obtained when fast addressing modes are used.

We propose two new instructions, swperm and sieve, that can be used to efficiently complete an arbitrary bit-level permutation of an n-bit word with or without repetitions. Permutations with repetitions are rearrangements of an ordered set in which elements may replace other elements in the set; such permutations are useful in cryptographic algorithms. On a 4-way superscalar processor, an arbitrary 64-bit permutation with repetitions of 1-bit subwords can be completed in 11 instructions and only 4 cycles using the two proposed instructions. For subwords of size 4 bits or greater, an arbitrary, permutation with repetitions of a 64-bit register can be completed in a single cycle using a single swperm instruction. This improves upon previous permutation instruction proposals that require log(r) sequential instructions to permute r subwords of a 64-bit word without repetitions. Our method requires fewer instructions to permute 4-bit or larger subwords packed in a 64-bit register and fewer execution cycles for 1-bit subwords on wide superscalar processors.

We discuss the integer and floating-point multimedia instructions in the IA-64 instruction-set architecture (ISA). These

MicroSIMD architectures incorporating subword parallelism are very efficient for application-specific media processors as well as for fast multimedia information processing in general-purpose processors. This paper addresses the unsolved problem of the need to permute the subwords packed in registers for maximum parallelism performance, especially for two-dimensional (2-D) multimedia algorithms. We propose a new systematic approach for identifying the fundamental data rearrangement needs in current and future 2-D pixel processing programs based on the hierarchical decomposition of frames and objects into atomic 2-D structures. We define new subword permutation instructions, Check, Excheck, Exchange, and Permset that achieve these data rearrangements across multiple registers. We also define an alphabet of subword permutation primitives, including these new instructions and the Mix instruction defined for PA-RISC MAX-2 and IA-64, which supports the data rearrangement needs of 2D frames and objects. We show the sufficiency and efficiency of this alphabet for achieving all possible permutations of hierarchical 2-D blocks.

Permutation is widely used in cryprographic algorithms. However, it is not well-supported in existing instruction sets. In this paper, two instructions, PPERM3R and GRP, are proposed for efficient software implementation of arbitrary permutations. The PPERM3R instruction can be used for dynamically specified permutations; the GRP instruction can be used to do arbitrary n-bit permutations with up to lg(n) instructions. In addition, a systematic method for determining the instruction sequence for performing an arbitrary permutation is described.

This paper proposes a new way of efficiently doing arbitrary n-bit permutations in programmable processors modeled on the theory of omega and flip networks. The new om-flip instruction we introduce can perform any permutation of n subwords in log n instructions, with the subwords ranging from half-words down to single bits. Each omflip instruction can be done in a single cycle, with very efficient hardware implementation. The omflip instruction enhances a programmable processor's capability for handling multimedia and security applications which use subword permutations extensively.

Cost-sensitive consumer multimedia devices based on MPEG and JPEG type algorithms tend to have multiplications by constants, rather than by variables. In this paper we show how slightly enhanced adders may be used to perform these constant multiplications with higher performance than more expensive hardware multipliers, using low-cost preshift-add instructions. We were able to find the shortest instruction sequences for all 8-bit integer constants and nearly shortest sequences for 12-bit constants and 15-bit constants. We have achieved an average instruction length of 3.055 for 8-bit integer case, 4.2643 and 4.2782 for the two 12-bit constant cases and 5.07673 for the 15-bit constant case. Based on our preshifter design, we evaluate the area and delay of a 16-bit preshift-adder and compare it with a 16/spl times/16 multiplier. We show that the simpler preshift-adders achieve a speedup of more than 2X compared to multipliers with similar area cost for typical algorithms like DCT and IDCT.

Virtual private networks (VPNs) allow two or more parties to communicate securely over a public network. Using cryptographic algorithms and protocols, VPNs provide security services such as confidentiality, host authentication and data integrity. The computation required to provide adequate security, however, can significantly degrade the performance. We characterize the extent to which data compression can alleviate this performance problem in a VPN implemented with the IP Security Protocol (IPsec). We use a system model for IPsec transactions to derive an inequality that specifies the conditions required for data compression to improve performance. We generate performance results for many combinations of network types, data types, packet sizes, and encryption, authentication and compression algorithms. We find that compression usually improves the performance when using 10 Mbps or slower networks, but compression only improves the performance in systems with 100 Mbps or 1 Gbps networks when using computationally intensive encryption algorithms.

With the popularity of multimedia acceleration instructions such as MMX, MPEG decompression is increasingly executed on general purpose processors instead of dedicated MPEG hardware. The gap between processor speed and memory access means that a significant amount of time is spent in the memory system. As processors get faster-both in terms of higher clock speeds and increased instruction level parallelism-the time spent in the memory system becomes even more significant. Data prefetching is a well-known technique for improving cache performance. While several studies have examined prefetch strategies for scientific and commercial applications, this paper focuses on video applications. Data is presented for three types of hardware-prefetching schemes: the stream buffer, the stride prediction table (SPT), and the stream cache, as well as a new software-directed prefetching technique based on emulation of the hardware SPT. Up to 90% of the misses that would otherwise occur with no prefetching are eliminated. The stream cache can cut execution time by more than half with the addition of a relatively small amount of additional hardware. Software prefetching achieves nearly equal performance with minimal additional hardware. Techniques presented in this paper can be used to improve performance in a general-purpose CPU or an embedded MPEG processor. Performance gains achieved for MPEG benchmarks apply equally effectively to similar multimedia applications.

In this papel; we describe several methods which can improve the performance of the baseline H.263 encoder: All of our improvements were implemented in sofrware using the Telenor ~2.0 codec.We begin by presenting results of our optimization of the Telenor sofnvare, which reduced the computation time of the encoder by four rimes its original value.Next, we characterize individual parts of the encoder and observe how the distribution of computation time varies with input sequence and motion search type.Based on our characterization, we then propose two methods to reduce computation in the motion estimatol; discrete cosine transform, and quantizel; using a technique that detects all-zero coeficients in macrobIocks.Our combined results ultimately reduces the computational time of the original Telenor encoder by four to nine times its original value.LO repttbfkh.LO post or1 servm or lo redistribute 10 lisls, requires specific

Traditional video decoders require use of specially designed video decompression processors. We present novel algorithmic and architectural enhancements that allowed for the first time the real-time decompression of MPEG-1 video and audio streams on a low-end, general purpose RISC processor. For video decompression, efficient algorithmic implementations were derived by examining the Huffman decoder, the inverse quantizer and the inverse DCT as a single system. For audio decompression, a new DCT based implementation of the subband filtering operation yields 30% speed improvement in the audio decoding process and 17% speed improvement in overall audio and video decoding. Besides algorithmic enhancements, a new set of "multimedia" instructions and minor changes in the design of a traditional RISC ALU allowed increased parallelism of pixel-based operations with minimal design and control overhead. Experimental results show that with the synergistic combination of algorithmic and architectural enhancements a multimedia-enhanced RISC processor can achieve higher decoding rates than generic RISC and CISC processors, even when these processors operate at higher clock rates and have larger instruction and data caches.>