論文の概要: Algorithmic Complexity Attacks on Dynamic Learned Indexes
- arxiv url: http://arxiv.org/abs/2403.12433v1
- Date: Tue, 19 Mar 2024 04:46:56 GMT
- ステータス: 処理完了
- システム内更新日: 2024-03-20 15:22:07.548264
- Title: Algorithmic Complexity Attacks on Dynamic Learned Indexes
- Title(参考訳): 動的学習指標に基づくアルゴリズム的複雑度攻撃
- Authors: Rui Yang, Evgenios M. Kornaropoulos, Yue Cheng,
- Abstract要約: 本稿では,ALEXの最悪のシナリオを対象とした,アルゴリズム的複雑性攻撃(ACA)に関する最初の体系的な研究について述べる。
まず、データノード上のACAは、ALEXのギャップ化された配列レイアウトを利用する。
第2に、内部ノード上のACAは、ALEXの壊滅的なコスト軽減機構を利用する。
第3に、ACAは、実際の鍵分布とデータノードの線形モデルとの相違を高めるために、病的挿入を生成する。
- 参考スコア(独自算出の注目度): 8.477808921777951
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Learned Index Structures (LIS) view a sorted index as a model that learns the data distribution, takes a data element key as input, and outputs the predicted position of the key. The original LIS can only handle lookup operations with no support for updates, rendering it impractical to use for typical workloads. To address this limitation, recent studies have focused on designing efficient dynamic learned indexes. ALEX, as the pioneering dynamic learned index structures, enables dynamism by incorporating a series of design choices, including adaptive key space partitioning, dynamic model retraining, and sophisticated engineering and policies that prioritize read/write performance. While these design choices offer improved average-case performance, the emphasis on flexibility and performance increases the attack surface by allowing adversarial behaviors that maximize ALEX's memory space and time complexity in worst-case scenarios. In this work, we present the first systematic investigation of algorithmic complexity attacks (ACAs) targeting the worst-case scenarios of ALEX. We introduce new ACAs that fall into two categories, space ACAs and time ACAs, which target the memory space and time complexity, respectively. First, our space ACA on data nodes exploits ALEX's gapped array layout and uses Multiple-Choice Knapsack (MCK) to generate an optimal adversarial insertion plan for maximizing the memory consumption at the data node level. Second, our space ACA on internal nodes exploits ALEX's catastrophic cost mitigation mechanism, causing an out-of-memory error with only a few hundred adversarial insertions. Third, our time ACA generates pathological insertions to increase the disparity between the actual key distribution and the linear models of data nodes, deteriorating the runtime performance by up to 1,641X compared to ALEX operating under legitimate workloads.
- Abstract(参考訳): Learned Index Structures (LIS)は、ソートインデックスをデータ分散を学習し、データ要素キーを入力として取り、予測されたキーの位置を出力するモデルとして見ている。
オリジナルのLISは、更新をサポートせずにルックアップ操作のみを処理することができ、典型的なワークロードで使用するには実用的ではない。
この制限に対処するため、最近の研究では、効率的な動的学習インデックスの設計に焦点が当てられている。
ALEXは動的学習インデックス構造のパイオニアとして、適応的なキー空間分割、動的モデル再トレーニング、読み書き性能を優先する高度なエンジニアリングとポリシーを含む一連の設計選択を取り入れることで、ダイナミズムを可能にする。
これらの設計選択は平均ケースのパフォーマンスを改善するが、ALEXのメモリ空間と最悪のシナリオにおける時間複雑さを最大化する敵の振る舞いを許容することで、柔軟性とパフォーマンスに重点を置いて攻撃面を増大させる。
本稿では,ALEXの最悪のシナリオを対象とした,アルゴリズム複雑性攻撃(ACA)に関する最初の体系的な研究を示す。
本稿では,空間ACAと時間ACAの2つのカテゴリに分類される新しいACAを紹介する。
まず、データノード上のACAは、ALEXのギャップ化された配列レイアウトを利用して、Multiple-Choice Knapsack(MCK)を使用して、データノードレベルでのメモリ消費を最大化する最適な逆挿入計画を生成する。
第2に、内部ノード上のACAは、ALEXの壊滅的なコスト軽減機構を利用して、数百の逆挿入でメモリ外エラーを引き起こします。
第3に、ACAは、実際のキー分布とデータノードの線形モデルとの格差を増大させるために、病理的な挿入を生成し、ALEXが正常なワークロードで動作しているのに対して、実行時の性能を最大1,641X劣化させる。
関連論文リスト
- OrCo: Towards Better Generalization via Orthogonality and Contrast for Few-Shot Class-Incremental Learning [57.43911113915546]
FSCIL(Few-Shot Class-Incremental Learning)は、問題空間を限られたデータで拡張するパラダイムを導入する。
FSCILの手法は、データが漸進的に到着するにつれて、破滅的な忘れ込みの課題に直面している。
表現空間における特徴の直交性と対照的な学習という2つの基本原理に基づいて構築されたOrCoフレームワークを提案する。
論文 参考訳(メタデータ) (2024-03-27T13:30:48Z) - ALISA: Accelerating Large Language Model Inference via Sparsity-Aware KV Caching [9.884452250478216]
我々は,KVキャッシングによる課題に対処するアルゴリズム-システム共設計ソリューションであるALISAを提案する。
アルゴリズムレベルでは、ALISAはスパースウィンドウ注意(SWA)アルゴリズムを介して新しいトークンを生成する上で最も重要なトークンを優先順位付けする。
システムレベルでは、ALISAは3フェーズのトークンレベルの動的スケジューリングを採用し、キャッシュと再計算の間のトレードオフを最適化する。
論文 参考訳(メタデータ) (2024-03-26T01:46:34Z) - AcceleratedLiNGAM: Learning Causal DAGs at the speed of GPUs [57.12929098407975]
既存の因果探索法を効率的に並列化することにより,数千次元まで拡張可能であることを示す。
具体的には、DirectLiNGAMの因果順序付けサブプロデューサに着目し、GPUカーネルを実装して高速化する。
これにより、遺伝子介入による大規模遺伝子発現データに対する因果推論にDirectLiNGAMを適用することで、競争結果が得られる。
論文 参考訳(メタデータ) (2024-03-06T15:06:11Z) - Large-scale Fully-Unsupervised Re-Identification [78.47108158030213]
大規模未ラベルデータから学ぶための2つの戦略を提案する。
第1の戦略は、近傍関係に違反することなく、それぞれのデータセットサイズを減らすために、局所的な近傍サンプリングを行う。
第2の戦略は、低時間上限の複雑さを持ち、メモリの複雑さを O(n2) から O(kn) に k n で還元する新しい再帰的手法を利用する。
論文 参考訳(メタデータ) (2023-07-26T16:19:19Z) - Mode-wise Principal Subspace Pursuit and Matrix Spiked Covariance Model [12.381700512445805]
行列データに対して行次元と列次元の両方に隠れたバリエーションを抽出するために,モードワイド・プリンシパル・サブスペース・スーツ (MOP-UP) と呼ばれる新しいフレームワークを導入する。
提案フレームワークの有効性と実用性は、シミュレーションと実データの両方の実験を通して実証される。
論文 参考訳(メタデータ) (2023-07-02T13:59:47Z) - NumS: Scalable Array Programming for the Cloud [82.827921577004]
タスクベース分散システム上でNumPyのような表現を最適化する配列プログラミングライブラリであるNumSを提案する。
これはLoad Simulated Hierarchical Scheduling (LSHS)と呼ばれる新しいスケジューラによって実現される。
LSHSは、ネットワーク負荷を2倍減らし、メモリを4倍減らし、ロジスティック回帰問題において実行時間を10倍減らし、Rayの性能を向上させる。
論文 参考訳(メタデータ) (2022-06-28T20:13:40Z) - Highly Parallel Autoregressive Entity Linking with Discriminative
Correction [51.947280241185]
自己回帰リンクを全ての潜在的な言及に対して並列化する,非常に効率的な手法を提案する。
我々のモデルは以前の生成法より70倍高速で精度が高い。
論文 参考訳(メタデータ) (2021-09-08T17:28:26Z) - Regularization Can Help Mitigate Poisoning Attacks... with the Right
Hyperparameters [1.8570591025615453]
機械学習アルゴリズムは、トレーニングデータの一部を操作してアルゴリズムのパフォーマンスを低下させる、中毒攻撃に対して脆弱である。
通常、正規化ハイパーパラメータが一定であると仮定する現在のアプローチは、アルゴリズムの堅牢性に対する過度に悲観的な見方をもたらすことを示す。
本稿では,攻撃が過度パラメータに与える影響を考慮し,エフェミニマックスの双レベル最適化問題としてモデル化した新たな最適攻撃定式化を提案する。
論文 参考訳(メタデータ) (2021-05-23T14:34:47Z) - Sublinear Least-Squares Value Iteration via Locality Sensitive Hashing [49.73889315176884]
本稿では、実行時の複雑さをアクション数にサブリニアに持つ最初の証明可能なLeast-Squares Value Iteration(LSVI)アルゴリズムを提示する。
我々は, 近似最大内積探索理論と強化学習の後悔分析との関係を構築する。
論文 参考訳(メタデータ) (2021-05-18T05:23:53Z) - Regularisation Can Mitigate Poisoning Attacks: A Novel Analysis Based on
Multiobjective Bilevel Optimisation [3.3181276611945263]
機械学習(ML)アルゴリズムは、アルゴリズムのパフォーマンスを意図的に劣化させるためにトレーニングデータの一部が操作される、中毒攻撃に対して脆弱である。
2レベル問題として定式化できる最適毒殺攻撃は、最悪のシナリオにおける学習アルゴリズムの堅牢性を評価するのに役立つ。
このアプローチはアルゴリズムの堅牢性に対する過度に悲観的な見方をもたらすことを示す。
論文 参考訳(メタデータ) (2020-02-28T19:46:10Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。