論文の概要: ShadowProbe: Language-Extensible Detection of Hidden Algorithmic Complexity Vulnerabilities
- arxiv url: http://arxiv.org/abs/2607.05474v1
- Date: Mon, 06 Jul 2026 09:15:25 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-07-08 21:24:51.274073
- Title: ShadowProbe: Language-Extensible Detection of Hidden Algorithmic Complexity Vulnerabilities
- Title（参考訳）: ShadowProbe:隠れたアルゴリズム複雑度脆弱性の言語拡張性検出
- Abstract要約: アルゴリズム複雑度脆弱性(ACV)は、逆入力が最悪の実行動作を引き起こすときに発生する。
本稿では,軽量な静的解析によりACVを発見するためのフレームワークであるShadowProbeを紹介する。
CPython, Zig Rustc, vLLMなどの大規模システムに適用する。
- 参考スコア（独自算出の注目度）: 28.083603872030892
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Algorithmic Complexity Vulnerabilities (ACVs) arise when adversarial inputs trigger worst-case execution behavior, causing severe performance degradation or Denial-of-Service conditions. A key but underexplored source is shadow complexity: non-trivial computational costs hidden inside seemingly benign standard library APIs. Because these costs are invisible at call sites, attackers can exploit them to induce unexpected superlinear runtime behavior. Existing ACV detectors often rely on fuzzing, symbolic execution, or hybrid analysis, but they are usually language-specific, require substantial manual effort to construct harnesses, and depend on heavy runtime instrumentation. We present ShadowProbe, a scalable and language-extensible framework for discovering ACVs through lightweight static analysis, automated reconstruction of execution contexts, and Large Language Model (LLM) assisted test generation. ShadowProbe uses a structured multi-stage pipeline: it statically screens for candidate functions guided by shadow-complexity signals, reconstructs minimal executable contexts from project-level symbols, and synthesizes size-controlled inputs to probe worst-case behavior. It then validates candidates using execution-time measurements and robust statistical growth inference, separating true algorithmic blowups from runtime noise such as garbage collection and JIT compilation effects. We evaluate ShadowProbe on the WISE benchmark, where it consistently improves analysis efficiency over existing approaches. We further apply it to large-scale systems including CPython, the JDK, Zig, Rustc, and vLLM, uncovering many previously unknown ACVs, many of which have been confirmed and partially remediated by maintainers. These results show that ShadowProbe can identify hidden algorithmic risks across diverse real-world codebases.
- Abstract（参考訳）: アルゴリズム複雑度脆弱性(ACV)は、逆入力が最悪のケース実行動作を引き起こし、パフォーマンス劣化やサービス停止の原因となる。
非自明な計算コストは、一見した標準ライブラリAPIの中に隠されている。
これらのコストはコールサイトでは見えないため、攻撃者はそれらを悪用して予期せぬ超線形ランタイム動作を誘発することができる。
既存のAVV検出器はファジィング、シンボリック実行、あるいはハイブリッド分析に頼っていることが多いが、それらは言語固有のものであり、ハーネスを構築するためにかなりの手作業が必要であり、重いランタイム機器に依存している。
本稿では,軽量な静的解析,実行コンテキストの自動再構築,大規模言語モデル(LLM)によるテスト生成などを通じて,ACVを発見するためのスケーラブルで言語拡張可能なフレームワークであるShadowProbeを紹介する。
ShadowProbeは構造化されたマルチステージパイプラインを使用し、シャドウ複雑な信号で導かれる候補関数を静的にスクリーニングし、プロジェクトレベルのシンボルから最小限の実行可能なコンテキストを再構築し、サイズ制御された入力を合成し、最悪の場合の振る舞いを探索する。
そして、実行時測定と統計的成長の頑健な推測を使って候補を検証し、真のアルゴリズム的な爆発をガベージコレクションやJITコンパイル効果のような実行時ノイズから分離する。
WISEベンチマークでShadowProbeを評価し、既存のアプローチよりも解析効率を継続的に改善する。
さらに、CPython、JDK、Zig、Rustc、vLLMといった大規模システムにも適用し、これまで知られていなかった多くのACVを発見しました。
これらの結果は、ShadowProbeが様々な現実世界のコードベースにまたがる隠れたアルゴリズム上のリスクを識別できることを示している。
関連論文リスト
- FeedbackLLM: Metadata driven Multi-Agentic Language Agnostic Test Case Generator with Evolving prompt and Coverage Feedback [0.0]
テストケース生成に対する従来のアプローチは、しばしば手作業と計算オーバーヘッドの増大を伴う。
We propose FeedbackLLM, a novel language-agnostic test case generation framework based on tightly coupled two-stage approach。
提案アーキテクチャの性能は,CプログラムとPythonプログラムに関連する標準ベンチマークプログラムで評価される。
論文 参考訳（メタデータ） (2026-05-02T05:43:29Z) - DALC-CT: Dynamic Analysis of Low-Level Code Traces for Constant-Time Verification [0.08749675983608168]
低レベルの実行トレースの動的解析に基づく定数時間プログラムの検証手法を提案する。
我々は,DALC-CTというオープンソースのツールを開発し,この手法を用いてプログラムの一定時間検証を行った。
論文 参考訳（メタデータ） (2026-04-18T04:47:54Z) - Dynamic analysis enhances issue resolution [53.50448142467294]
DAIRA(Dynamic Analysis-enhanced Issue Resolution Agent)は、エージェントの推論サイクルに動的解析を組み込む自動修復フレームワークである。
テストトレース駆動の方法論によって駆動されるDAIRAは、軽量モニタを使用して重要なランタイムデータを抽出する。
Gemini 3 Flash Previewを使用すると、DAIRAは新たな最先端(SOTA)パフォーマンスを確立し、SWE-bench Verifiedデータセットで79.4%の解像度を達成する。
論文 参考訳（メタデータ） (2026-03-23T14:48:54Z) - ForgeryVCR: Visual-Centric Reasoning via Efficient Forensic Tools in MLLMs for Image Forgery Detection and Localization [62.03035862528452]
ForgeryVCRは、視覚中心推論(Visual-Centric Reasoning)を通じて、知覚できないトレースを明示的な視覚中間体に物質化するフレームワークである。
ForgeryVCRは、検出タスクとローカライゼーションタスクの両方において、最先端(SOTA)のパフォーマンスを達成する。
論文 参考訳（メタデータ） (2026-02-15T11:14:47Z) - Prism: Efficient Test-Time Scaling via Hierarchical Search and Self-Verification for Discrete Diffusion Language Models [96.0074341403456]
LLM推論を改善するための実用的な方法として、推論時計算が再導入されている。
テスト時間スケーリング(TTS)アルゴリズムの多くは、自動回帰デコーディングに依存している。
そこで我々は,dLLM のための効率的な TTS フレームワーク Prism を提案する。
論文 参考訳（メタデータ） (2026-02-02T09:14:51Z) - Multi-Agent Taint Specification Extraction for Vulnerability Detection [49.27772068704498]
コンテナ分析を使用した静的アプリケーションセキュリティテスト(SAST)ツールは、高品質な脆弱性検出結果を提供するものとして広く見なされている。
本稿では,Large Language Models (LLM) のセマンティック理解と従来の静的プログラム解析を戦略的に組み合わせたマルチエージェントシステムであるSemTaintを提案する。
私たちは、SemTaintを最先端のSASTツールであるCodeQLと統合し、これまでCodeQLで検出できなかった162の脆弱性の106を検出して、その効果を実証しています。
論文 参考訳（メタデータ） (2026-01-15T21:31:51Z) - Can LLMs Recover Program Semantics? A Systematic Evaluation with Symbolic Execution [1.5377279217726239]
難読化は、プログラムの理解、メンテナンス、テスト、脆弱性検出といったソフトウェアエンジニアリングタスクに永続的な課題をもたらす。
微調整言語モデルがプログラムを効果的に難読化し、分析可能性を取り戻すことができるかどうかを検討する。
論文 参考訳（メタデータ） (2025-11-24T13:55:20Z) - Hybrid Fuzzing with LLM-Guided Input Mutation and Semantic Feedback [0.0]
本稿では,静的および動的解析をLarge Language Model(LLM)誘導入力変異と意味フィードバックと統合したハイブリッドファジリングフレームワークを提案する。
本手法は,最先端のファジィよりも高速な時間対第一のバグ,意味的多様性の向上,およびユニークなバグの競合数を実現する。
論文 参考訳（メタデータ） (2025-11-06T02:38:24Z) - Taming Imperfect Process Verifiers: A Sampling Perspective on Backtracking [54.43083499412643]
言語モデルの生成能力をプロセス検証器と組み合わせたテストタイムアルゴリズムは、新しい推論能力を引き出すための有望なレバーを提供する。
提案手法は, 理論的に根拠付きバックトラックを用いて, 検証誤差に対して, 確実な堅牢性を実現するための新しいプロセス誘導型テスト時間サンプリングアルゴリズムであるVGBを導入する。
論文 参考訳（メタデータ） (2025-10-03T16:21:14Z) - FoC: Figure out the Cryptographic Functions in Stripped Binaries with LLMs [51.898805184427545]
削除されたバイナリの暗号関数を抽出するFoCと呼ばれる新しいフレームワークを提案する。
まず、自然言語における暗号関数のセマンティクスを要約するために、バイナリ大言語モデル(FoC-BinLLM)を構築した。
次に、FoC-BinLLM上にバイナリコード類似モデル(FoC-Sim)を構築し、変更に敏感な表現を作成し、データベース内の未知の暗号関数の類似実装を検索する。
論文 参考訳（メタデータ） (2024-03-27T09:45:33Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。