PaperlayerView exact revision on arXiv

Source-linked AI summary

Hoss: Fast Oblivious Semantic Search with Heterogeneous GPU-CPU-TEE Architecture

Jianzhang Du, Weijie Huang, Chenghong Wang, Nicolas Tsagareli, Yukui Luo, XiaoFeng Wang, Zhongshu Gu

arXiv:2609.04522v1cs.CR

TL;DR

Oblivious semantic search must protect data contents and access patterns while avoiding the substantial overhead of existing ORAM-based approaches. Hoss combines GPU and CPU TEEs, keeping hot-path HNSW traversal in GPU private memory and using oblivious host accesses for lower graph layers. Up to 99× speedup over Compass is reported, though standard obliviousness does not hide timing or volume leakage.

  • Problem

    Oblivious semantic search must protect data contents and access patterns while avoiding the substantial overhead of existing ORAM-based approaches.

  • Method

    Hoss combines GPU and CPU TEEs, keeping hot-path HNSW traversal in GPU private memory and using oblivious host accesses for lower graph layers.

  • Results

    Up to 99× speedup over Compass is reported, with larger gains at scale.

  • Takeaways & Limitations

    Hoss shows that strong security can coexist with efficient, scalable HNSW-based retrieval within its supported setting.

  • Takeaways & Limitations

    Standard obliviousness does not hide timing or volume leakage, while the infrastructure assumes GPU HBM may not contain the entire index.

Abstract

from arXiv · show

Semantic search is widely deployed in modern AI systems, but protecting both data contents and access patterns remains challenging. The current state-of-the-art system, Compass, achieves oblivious semantic search by building an optimized ORAM over HNSW graphs. However, even with aggressive optimizations, it still incurs large overheads. Closing this performance gap is fundamentally difficult: Compass has already removed most cryptographic overheads, leaving ORAM accesses as the dominant cost, which are constrained by well-known Omega(log N) bandwidth lower bounds. Our key insight is that traditional ORAM overhead stems from the assumption of limited private memory, whereas modern GPU TEEs provide large private memory (Pmem) that blinds internal access patterns (Hunt et al., NSDI '23). This shift opens a new design space. We therefore propose Hoss, a first-of-its-kind oblivious semantic search system with a heterogeneous CPU-GPU TEE architecture that supports fast, scalable search with low cost of ownership. In Hoss, the GPU TEE's large Pmem hosts the hot-path HNSW traversal, while the lower layers of the graph, if they exceed GPU capacity, are offloaded to CPU TEEs. The system invokes oblivious primitives only when accessing these lower layers. The availability of large Pmem also enables new optimization opportunities. For example, Hoss features a host-access ORAM mechanism that goes beyond traditional performance constraints and incorporates several data-dependent optimizations that are not possible in prior designs. We implement a prototype of Hoss and benchmark it against Compass. Our results show that Hoss achieves up to 67x speedup while maintaining high recall, with larger gains at scale.

1 Introduction

Hoss targets the privacy leakage and high overhead of oblivious semantic search by using GPU-TEE private memory for hot-path HNSW traversal and CPU TEEs for lower layers. Its prototype reports substantial speedups over Compass while maintaining high recall.

  • Introduction: Semantic retrieval can leak query semantics and user intent through data-dependent memory-access patterns, even when data is encrypted.Existing cloud deployments also expose plaintext queries and embeddings, creating privacy, trust, and proprietary-data concerns.
  • Introduction: Compass provides end-to-end oblivious semantic search with reasonable accuracy and scalability, but still incurs seconds-level latency on million-scale datasets.Compass builds an optimized ORAM over HNSW indexes, leaving ORAM access overhead as a central performance barrier.
  • A new opportunity: Large GPU-TEE private memory changes the design space because internal HBM access patterns are hidden from the adversary.This permits data-dependent operations on the GPU hot path while retaining oblivious mechanisms for exposed host-memory accesses.
  • Our Contributions: Hoss uses a heterogeneous GPU-CPU-TEE architecture, keeping upper-layer HNSW search in GPU private memory and offloading lower layers to CPU TEEs.The layer structure provides clean boundaries, while oblivious accesses are used for host-resident lower layers.
  • Prototype and evaluation: Hoss achieves up to 99× speedup over Compass, with larger gains at larger dataset scales.The prototype is implemented in CUDA C++ and evaluated against state-of-the-art systems.

2 Background

Similarity search uses vector embeddings and approximate nearest-neighbor indexes to retrieve similar items efficiently at scale. HNSW is a multilevel graph method, while TEEs and ORAM address confidentiality and access-pattern leakage.

  • Similarity Search: Approximate nearest-neighbor search sacrifices a small amount of accuracy to avoid impractical exhaustive search over large, high-dimensional datasets.Specialized indexes accelerate retrieval without scanning every data point.
  • Similarity Search: HNSW organizes embeddings in a multilevel graph, using coarse greedy routing in upper layers and broader candidate expansion at the bottom layer.The parameter ef controls the breadth of base-layer exploration, trading latency for recall.
  • TEEs and ORAMs: TEE-protected programs can still leak access patterns through shared microarchitectural resources and observable external memory channels.Potentially exposed channels include caches, TLBs, DRAM buses, PCIe links, DMA buffers, and board-level traces.
  • TEEs and ORAMs: ANN searches are especially vulnerable to access-pattern leakage because their memory traces depend strongly on the data and query.Consequently, CPU TEEs alone are insufficient for securing these algorithms.
  • TEEs and ORAMs: ORAM hides which logical memory location was accessed by producing pseudorandom physical accesses, while OMAPs extend the abstraction to arbitrary-key stores.OMAPs generally incur additional I/O bandwidth costs.

3 Threat Models & Security Goals

Hoss is formulated as secure outsourced computing with a powerful adversary observing exposed channels. Its security goal requires indistinguishable leakage transcripts for equal-length HNSW traversal paths, under stated memory and TEE assumptions.

  • Threat Model: The model includes a data owner, an untrusted cloud server providing TEE resources, and an authenticated analyst issuing semantic queries.The data owner outsources an HNSW-organized dataset and search to the cloud.
  • Threat Model: The adversary may compromise software layers and physically observe off-chip channels, while cloud organizational integrity and TEE protections are trusted.The threat model treats administrators, software, co-located tenants, and exposed interconnects as untrusted or observable.
  • Security Goals: Hoss defines obliviousness by requiring indistinguishable leakage transcripts for any two queries whose HNSW traversal lengths match at every layer.The definition follows the standard ORAM approach of comparing logical access sequences with equal lengths.
  • Infrastructure Assumptions: The infrastructure model assumes GPU HBM may not hold the entire ANN index, while comparatively larger host-side private memory stores the remainder.The study uses an in-memory setting, assumes no trusted multi-GPU memory stitching, and parameterizes HBM capacity as a fraction of host memory.

4 Hoss System Design

Hoss redesigns oblivious HNSW search around large GPU-TEE private memory, using GPU-resident traversal and CPU-TEE ORAM only for offloaded lower layers. Its sorted linear-table layout, device-side execution, and HNSW-specific CORAM optimizations align storage and access patterns with GPU execution while reducing host I/O overhead.

  • 4 Hoss System Design: Hoss stores upper HNSW layers in GPU HBM and offloads lower layers to CPU-TEE memory, invoking ORAM only for host-resident accesses.The layer-wise partition uses GPU private memory for the hot path and CPU TEE memory for capacity beyond GPU HBM.
  • 4.1 Storage Layout: Hoss flattens each HNSW layer into a compact table sorted by node ID, enabling direct O(1) addressing within and across layers.Persistent temporary IDs and fixed-size node slots eliminate pointer chasing and match fixed-size ORAM address-value accesses.
  • 4.1 Storage Layout: Upper-layer GPU storage separates graph structure from embeddings, while host records co-locate neighbors and embeddings to halve oblivious I/O invocations.The GPU layout avoids embedding duplication; the host layout prioritizes fewer transfers over storage capacity.
  • 4.2 Execution model: A persistent GPU search kernel keeps query state and ORAM control on device, bypassing CPU step-by-step coordination and materializing results only at the end.The execution model uses preallocated storage and device-side ORAM calls after traversal reaches host-resident layers.
  • 4.3 GPU-Assisted Coalesced ORAM: CORAM coalesces distinct HNSW neighbor accesses without changing their observable distribution and replaces randomized load balancing with uniform remapping for SIMD-friendly execution.Uniform remapping raises asymptotic bandwidth from O(log log N) to O(log N log log N), while simplifying the hot path for practical sizes.
  • 4.3 GPU-Assisted Coalesced ORAM: GPU stash management is a critical bottleneck because naive dynamic scans, reshuffling, and full-tuple movement create irregular traffic and synchronization pressure.This motivates stash-specific optimization rather than treating the stash as one dynamically rearranged container.

5 Hoss Analysis

Hoss’s analysis establishes obliviousness for its CORAM host access and derives bandwidth, coalescing, and stash-size guarantees for final-layer HNSW expansions.

  • Security analysis: Hoss’s CORAM host access satisfies the obliviousness definition for any final-layer expansion with neighbor list size at most M.The proof compares equal-length query traces and uses random remapping, dummy reads, batching, and TEE memory encryption.
  • Bandwidth complexity: Total query bandwidth is linear in the number of neighbor-expansion invocations, so the per-expansion bounds extend to full queries.This section uses one neighbor expansion as the unit for host-I/O analysis.
  • Bandwidth complexity: With probability at least 1−1/N, one non-coalesced neighbor expansion transfers at most M·ℓmax blocks when K=Θ(N).The bound uses the maximum randomized page load ℓmax, with overflow probability at most 1/N for the stated block-sizing choice.
  • Bandwidth complexity: Coalescing reduces expected host page reads to M−Θ(M^2/K), saving Θ(M^2/K) relative to M non-coalesced reads when M=o(K).The bound follows by counting distinct host pages touched by M independently randomized accesses across K pages.

6 Evaluation

Hoss is evaluated against Compass and Bolt across end-to-end performance, normalized overhead, memory usage, scalability, and ORAM microbenchmarks. It consistently improves performance while maintaining modest memory overhead and limited degradation when more HNSW layers are offloaded.

  • 6.2 End-to-End Performance Benchmark: Up to 99× speedup: Hoss outperforms Compass across all tested settings at 0.9 recall, with larger gains on larger datasets.At 0.98 recall, Hoss still achieves speedups over Compass, including up to 45× on MSMarco at 0.9 recall.
  • 6.2 End-to-End Performance Benchmark: Up to 357× normalized slowdown: Compass often exceeds 100× overhead, whereas Hoss remains below 6× in most cases.SIFT1M has the largest slowdown because its lower dimensionality makes ORAM overhead more prominent; higher-dimensional datasets are more dominated by data movement.
  • 6.2 End-to-End Performance Benchmark: Below 12% stash usage: sustained stress accesses keep the maximum stash size well below 12% of total data entries.GPU memory for the position map and maximum stash accounts for about 5.5% of total storage, while host-memory limits prevent direct extreme-scale stress testing.
  • 6.3 CORAM Micro-benchmark: Up to 101× speedup: Hoss outperforms Bolt when varying data-entry counts, primarily because its linear layout enables direct position-map lookups.The advantage narrows with dataset size because Bolt has O(log log N) bandwidth cost versus Hoss’s O(log N log log N), but Hoss still reaches 27× speedup.
  • 6.3 CORAM Micro-benchmark: Up to 44× speedup: Hoss consistently improves over Bolt when scaling value size.The benchmark uses Bolt’s data format and scale settings, with address–value entries containing a 4B address and an 8B default value.
  • 6.4 Offloading Mode Experiments: Only 6% overhead: offloading all HNSW layers adds modest latency relative to offloading only L0 at recall 0.9.Upper layers shrink exponentially and perform fewer node accesses, while higher-recall final-layer work further amortizes additional offloading overhead.

7 Discussion

Hoss’s design supports broader oblivious-system capabilities while identifying extensions and leakage concerns that remain outside its current scope.

  • Extensions: The paper leaves full exploration of Hoss’s broader extensions to future work.This scope boundary applies to the briefly discussed extensions beyond the core system.
  • Volume and timing hiding: Hoss follows standard obliviousness but requires padding, fixed execution, and in-GPU filtering to address timing and volume leakage.Upper-layer timing can vary, while offloaded layers expose data-dependent volume patterns from skipped nodes and early stopping.
  • Inter-query parallelism: Hoss’s Pmem-based design can coordinate parallel accesses while preserving ORAM invariants, providing a foundation for inter-query parallelism.Conflicting accesses can be handled through remapping and randomized dummy accesses, although identical accesses within a batch are not currently supported.
  • Adapting to other oblivious systems: Hoss’s CPU-bypassed execution and GPU-assisted ORAM can extend beyond HNSW semantic search to graph algorithms, relational databases, and time-series databases.New graph workloads primarily require a changed access interface while reusing the ORAM backend.
  • Dynamic index support: Hoss can support dynamic HNSW index management by combining oblivious search with bounded graph updates under pre-allocated ORAM storage.Insertions identify neighbors through oblivious search, while deletions can use lazy deletion.

8 Related Work

Prior oblivious systems hide access patterns through ORAM, oblivious algorithms, or secure hardware, but generally remain constrained by limited private memory and associated overheads.

  • ORAM and oblivious data systems: Oblivious data-processing research spans ORAM abstractions, oblivious algorithms, and end-to-end systems such as ZeroTrace, Oblix, and ObliDB.These approaches target hiding execution memory accesses from inputs or protecting data-processing systems with obliviousness guarantees.
  • ORAM and oblivious data systems: Compass provides state-of-the-art oblivious semantic search using an optimized ORAM for HNSW indexes, but traditional systems remain subject to ORAM lower bounds.Prior work commonly assumes O(1)-sized private memory or requires a trusted proxy or client.
  • Secure memory hardware: Secure-memory hardware conceals access channels without oblivious primitives, but existing designs typically target limited-capacity resources and are not general-purpose.Examples include registers, BRAMs, and specialized memory nodes.
  • Accelerator TEEs: Accelerator TEE research has expanded beyond CPU TEEs toward GPU-based designs, including production confidential-computing deployments.CPU examples include Intel SGX, AMD SEV, and Arm TrustZone; GPU TEEs have become a dominant accelerator direction.

9 Conclusion

Hoss revisits the privacy–performance tension in oblivious semantic search by using GPU HBM as larger private memory within a heterogeneous GPU-CPU TEE architecture.

  • Conclusion: Hoss treats GPU HBM as larger private memory to reduce reliance on expensive ORAM operations.The design combines GPU and CPU enclaves for secure, scalable HNSW-based retrieval.
  • Conclusion: Hoss confines data-dependent execution to trusted environments while supporting efficient oblivious semantic search.

A Open Science

The Hoss artifacts are publicly available in an anonymous repository with materials for reproducing the paper’s main experiments.

  • Open Science: The anonymous repository includes implementation, experiment scripts, benchmark workloads, configuration files, dataset-preparation and plotting scripts, and reproduction instructions.

B Ethical Considerations

Hoss is intended to reduce privacy leakage in legitimate outsourced semantic-search deployments, especially for sensitive workloads. The paper identifies security-guarantee over-interpretation as the main ethical risk and limits its claims through explicit threat-model and infrastructure assumptions.

  • Hoss targets privacy leakage in outsourced search for biomedical retrieval, enterprise search, and private retrieval-augmented generation.
  • The evaluation uses benchmark datasets and system-level performance measurements without human subjects, new personal data, or private user queries.
  • The threat analysis is limited to a specified model and supports evaluation of a defensive system rather than attacks on deployed third-party systems.
  • Hoss assumes standard TEE protections, encrypted inter-TEE communication, and dedicated GPU TEE execution, excluding availability attacks, malicious inputs, and invasive physical side channels.
  • Although the technology could have undesirable applications, the authors frame its intended use as reducing privacy leakage under legal, organizational, and access-control requirements.

C Generative AI Usage

The authors used ChatGPT only for minor editorial assistance, including grammar, spelling, and light style polishing. They manually reviewed and verified all AI-assisted edits.

  • ChatGPT was used only for grammar checking, spelling correction, and light style polishing, not for scientific content, citations, or technical claims.
  • The authors manually reviewed and verified all AI-assisted edits.
Loading 2609.04522v1…