論文の概要: 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劣化させる。

関連論文リスト

• LOCAL: Learning with Orientation Matrix to Infer Causal Structure from Time Series Data [13.390666123493409]
  LOCALは動的因果構造を復元するための効率的で実装が容易で制約のない手法である。 ACMLは学習可能な優先度ベクトルとGumbel-Sigmoid関数を用いて因果マスクを生成する。 DGPLは因果学習を分解された行列生成物に変換し、高次元データの動的因果構造をキャプチャする。
  論文  参考訳（メタデータ） (2024-10-25T10:48:41Z)
• Sparser is Faster and Less is More: Efficient Sparse Attention for Long-Range Transformers [58.5711048151424]
  SPARSEK Attention(SPARSEK Attention)は、計算およびメモリ障害を克服するために設計された、新しいスパースアテンション機構である。 提案手法では,各クエリに対して一定数のKVペアを選択するために,スコアリングネットワークと差別化可能なトップkマスク演算子であるSPARSEKを統合する。 実験結果から,SPARSEK注意は従来のスパースアテンション法よりも優れていた。
  論文  参考訳（メタデータ） (2024-06-24T15:55:59Z)
• Parsimonious Optimal Dynamic Partial Order Reduction [1.5029560229270196]
  本稿では,Parsimonious-Optimal DPOR(POP)を提案する。 POPは、(i)同じ人種の複数の逆転を避ける擬似的な人種反転戦略を含む、いくつかの新しいアルゴリズム技術を組み合わせている。 我々のNidhuggの実装は、これらの手法が並列プログラムの解析を著しく高速化し、メモリ消費を抑えられることを示している。
  論文  参考訳（メタデータ） (2024-05-18T00:07:26Z)
• 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)
• AcceleratedLiNGAM: Learning Causal DAGs at the speed of GPUs [57.12929098407975]
  既存の因果探索法を効率的に並列化することにより,数千次元まで拡張可能であることを示す。 具体的には、DirectLiNGAMの因果順序付けサブプロデューサに着目し、GPUカーネルを実装して高速化する。 これにより、遺伝子介入による大規模遺伝子発現データに対する因果推論にDirectLiNGAMを適用することで、競争結果が得られる。
  論文  参考訳（メタデータ） (2024-03-06T15:06:11Z)
• Mode-wise Principal Subspace Pursuit and Matrix Spiked Covariance Model [13.082805815235975]
  行列データに対して行次元と列次元の両方に隠れたバリエーションを抽出するために,モードワイド・プリンシパル・サブスペース・スーツ (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)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。