Abstract
Malware checking is changing from being a local service to a cloud-assisted one where users' devices query a cloud server, which hosts a dictionary of malware signatures, to check if particular applications are potentially malware. Whilst such an architecture gains all the benefits of cloud-based services, it opens up a major privacy concern since the cloud service can infer personal traits of the users based on the lists of applications queried by their devices. Private membership test (PMT) schemes can remove this privacy concern. However, known PMT schemes do not scale well to a large number of simultaneous users and high query arrival rates. We propose a simple PMT approach using a carousel: circling the entire dictionary through trusted hardware on the cloud server. Users communicate with the trusted hardware via secure channels. We show how the carousel approach, using different data structures to represent the dictionary, can be realized on two different commercial hardware security architectures (ARM TrustZone and Intel SGX). We highlight subtle aspects of securely implementing seemingly simple PMT schemes on these architectures. Through extensive experimental analysis, we show that for the malware checking scenario our carousel approach surprisingly outperforms Path ORAM on the same hardware by supporting a much higher query arrival rate while guaranteeing acceptable response latency for individual queries.
Introduction
Cloud-based malware checking services, such as Google’s Verify Apps, offer significant advantages in terms of signature updates and computational offloading. However, they introduce a critical privacy risk: the service provider can observe every application queried by a user. This visibility allows providers to infer sensitive personal information, including age, religious affiliation, or health status, based on the specific apps installed on a device.
While cryptographic solutions like Private Set Intersection (PSI) exist, they are often too computationally intensive for high-scale cloud environments. Recent research has explored using Oblivious RAM (ORAM) within Trusted Execution Environments (TEEs) like Intel SGX. While ORAM provides strong privacy by hiding memory access patterns, it struggles with scalability. In scenarios with millions of users, the $O(m \log n)$ cost of ORAM (where $m$ is the number of queries and $n$ is the dictionary size) becomes a significant bottleneck. This paper addresses the need for a PMT solution that prioritizes high throughput—the ability to handle a massive volume of simultaneous queries—without compromising user privacy.
The Carousel Approach
The authors propose the Carousel Approach, a design pattern that leverages TEEs to protect privacy while maximizing throughput. Instead of the TEE fetching specific items from a database—which inherently leaks access patterns—the untrusted server continuously "circles" the entire dictionary through the TEE.
Key technical components include:
- Batch Processing: Queries are collected and held within the TEE for exactly one full carousel cycle. This ensures that response time is independent of the query's value or its position in the dictionary, preventing timing-based leakage.
- Hardware Implementation: The system was evaluated on both ARM TrustZone and Intel SGX. A key challenge in SGX is the lack of "private memory" available in TrustZone, requiring the implementation of "oblivious pages" to prevent side-channel attacks from observing page-level memory access patterns.
Data Structures and Performance
To optimize the "spin" time of the carousel, the researchers evaluated three different data structures for representing the dictionary. The goal was to minimize the time required to process a batch of queries against the full dictionary.
As shown in the table above, 4-ary Cuckoo Hashing emerged as the most effective method. It allows for $O(m + n)$ processing time and fits a dictionary of approximately 67 million signatures into roughly 98 MB, which is well within the memory constraints of modern TEEs.
Key Results
The "Cuckoo-on-a-Carousel" (CoaC) method was compared against a state-of-the-art Path ORAM implementation:
- Sustainable Throughput: On Intel SGX, the Carousel approach supported 3,720 queries/second, a 2.75x improvement over Path ORAM. On ARM TrustZone, it supported 1,025 queries/second, nearly 10x more than ORAM.
- Stability Under Load: While ORAM provides lower latency for single queries, its response times skyrocket once a certain query threshold is reached. The Carousel approach maintains stable latency (around 1 second) even as the number of simultaneous users grows, until hardware limits are hit.
Conclusion and Future Work
The Carousel approach demonstrates that for high-throughput cloud services, a simple "batch and cycle" strategy can outperform complex ORAM-based solutions. By prioritizing throughput over single-query latency, the system provides a scalable, privacy-preserving alternative for malware checking.
Future work includes addressing dictionary scaling beyond single-server memory limits by partitioning the dictionary across multiple TAs. Additionally, while the current implementation defends against deterministic page-level attacks, further research is needed to mitigate more sophisticated probabilistic cache-timing attacks, potentially through integration with frameworks like Sanctum.
Summary updated