論文の概要: Boosting Path-Sensitive Value Flow Analysis via Removal of Redundant Summaries
- arxiv url: http://arxiv.org/abs/2502.04952v2
- Date: Tue, 11 Feb 2025 10:41:53 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-02-12 14:09:07.916268
- Title: Boosting Path-Sensitive Value Flow Analysis via Removal of Redundant Summaries
- Title（参考訳）: 冗長なサプライヤーの除去による経路感度値フロー解析
- Authors: Yongchao Wang, Yuandao Cai, Charles Zhang,
- Abstract要約: 冗長な要約を効果的に識別し、排除できる最初のアプローチを提案する。
我々の同定アルゴリズムは、最先端の値フロー解析における時間とメモリオーバーヘッドを著しく低減することができる。
最大のテキスト化プロジェクトでは、識別アルゴリズムは、わずか17.31秒の追加オーバーヘッドで8107秒(2.25時間)の時間を短縮する。
- 参考スコア（独自算出の注目度）: 12.187048691454239
- License:
- Abstract: Value flow analysis that tracks the flow of values via data dependence is a widely used technique for detecting a broad spectrum of software bugs. However, the scalability issue often deteriorates when high precision (i.e., path-sensitivity) is required, as the instantiation of function summaries becomes excessively time- and memory-intensive. The primary culprit, as we observe, is the existence of redundant computations resulting from blindly computing summaries for a function, irrespective of whether they are related to bugs being checked. To address this problem, we present the first approach that can effectively identify and eliminate redundant summaries, thereby reducing the size of collected summaries from callee functions without compromising soundness or efficiency. Our evaluation on large programs demonstrates that our identification algorithm can significantly reduce the time and memory overhead of the state-of-the-art value flow analysis by 45\% and 27\%, respectively. Furthermore, the identification algorithm demonstrates remarkable efficiency by identifying nearly 80\% of redundant summaries while incurring a minimal additional overhead. In the largest \textit{mysqld} project, the identification algorithm reduces the time by 8107 seconds (2.25 hours) with a mere 17.31 seconds of additional overhead, leading to a ratio of time savings to paid overhead (i.e., performance gain) of 468.48 $\times$. In total, our method attains an average performance gain of 632.1 $\times$.
- Abstract（参考訳）: データ依存による値の流れを追跡するバリューフロー分析は、ソフトウェアバグの幅広い範囲を検出するために広く使われているテクニックである。
しかし、関数要約のインスタンス化が過度に時間とメモリ集約化されるにつれて、高い精度(パス感度)が必要な場合、スケーラビリティの問題はしばしば悪化する。
私たちが観察する主な原因は、チェック中のバグに関連があるかどうかに関わらず、関数に対する盲目的に計算したサマリーから生じる冗長な計算の存在である。
この問題に対処するため, 冗長な要約を効果的に識別・排除し, 音声や効率を損なうことなく, 収集した要約を発信者関数から除去する手法を提案する。
大規模プログラムに対する評価では, 同定アルゴリズムにより, 最先端値フロー解析の時間オーバーヘッドとメモリオーバーヘッドを, それぞれ45 %, 27 %削減できることが示されている。
さらに,余剰サマリーの80%近くを識別し,最小限の追加オーバーヘッドを発生させることにより,同定アルゴリズムは顕著な効率性を示す。
最大の \textit{mysqld} プロジェクトでは、識別アルゴリズムは17.31秒の追加オーバーヘッドで8107秒(2.25時間)の時間を短縮し、支払いオーバーヘッド(すなわちパフォーマンス向上)に対する時間節約の割合は468.48$\times$である。
合計すると,平均性能は632.1$\times$である。
関連論文リスト
- A Sample Efficient Alternating Minimization-based Algorithm For Robust Phase Retrieval [56.67706781191521]
そこで本研究では,未知の信号の復元を課題とする,ロバストな位相探索問題を提案する。
提案するオラクルは、単純な勾配ステップと外れ値を用いて、計算学的スペクトル降下を回避している。
論文 参考訳（メタデータ） (2024-09-07T06:37:23Z) - Posterior Sampling with Delayed Feedback for Reinforcement Learning with
Linear Function Approximation [62.969796245827006]
Delayed-PSVI は楽観的な値に基づくアルゴリズムであり、後続サンプリングによる雑音摂動により値関数空間を探索する。
我々のアルゴリズムは、未知の遅延が存在する場合に、$widetildeO(sqrtd3H3 T + d2H2 E[tau]$最悪の後悔を実現する。
遅延LPSVIのための勾配に基づく近似サンプリングスキームをLangevin動的に組み込んだ。
論文 参考訳（メタデータ） (2023-10-29T06:12:43Z) - Optimizing Retrieval-augmented Reader Models via Token Elimination [30.53636918279251]
我々は,検索した全てのパスが読者モデルの性能に与える影響と必要性を分析した。
提案手法は,実行時間を最大62.2%削減でき,性能は2%しか低下せず,場合によっては性能も向上することを示した。
論文 参考訳（メタデータ） (2023-10-20T17:41:36Z) - Equitable and Fair Performance Evaluation of Whale Optimization
Algorithm [4.0814527055582746]
すべてのアルゴリズムは、徹底的に、幾分、知的に評価されることが不可欠である。
最適化アルゴリズムの有効性を等しく、公平に評価することは、様々な理由から簡単なプロセスではない。
論文 参考訳（メタデータ） (2023-09-04T06:32:02Z) - An Accelerated Doubly Stochastic Gradient Method with Faster Explicit
Model Identification [97.28167655721766]
本稿では、分散正規化損失最小化問題に対する2倍加速勾配降下法(ADSGD)を提案する。
まず、ADSGDが線形収束率を達成でき、全体的な計算複雑性を低減できることを示す。
論文 参考訳（メタデータ） (2022-08-11T22:27:22Z) - DeLag: Using Multi-Objective Optimization to Enhance the Detection of
Latency Degradation Patterns in Service-based Systems [0.76146285961466]
DeLagは,サービスベースシステムの性能問題を診断するための,新しい自動検索ベースのアプローチである。
DeLagは、精度、リコール、異種性を最適化しながら、複数のレイテンシパターンを同時に検索する。
論文 参考訳（メタデータ） (2021-10-21T13:59:32Z) - Learning to Schedule [3.5408022972081685]
本稿では,ジョブが生み出す累積保持コストを最小限に抑えるための学習・スケジューリングアルゴリズムを提案する。
各タイムスロットにおいて、サーバはシステムに残されているジョブのランダム保持コストを受信しながらジョブを処理できる。
論文 参考訳（メタデータ） (2021-05-28T08:04:06Z) - Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
本稿では,線形モデルから信号整数を推定する古典整数最小二乗問題について検討する。
問題はNPハードであり、信号処理、バイオインフォマティクス、通信、機械学習といった様々な応用でしばしば発生する。
本稿では, 深いニューラルネットワークを用いて, 単純化されたメモリバウンドA*アルゴリズムの最適推定を推定し, HATSアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-01-07T08:00:02Z) - Stochastic Hard Thresholding Algorithms for AUC Maximization [49.00683387735522]
分散分類におけるAUCのためのハードしきい値決定アルゴリズムを開発した。
提案アルゴリズムの有効性と有効性を示す実験を行った。
論文 参考訳（メタデータ） (2020-11-04T16:49:29Z) - Real-time Semantic Segmentation with Fast Attention [94.88466483540692]
本稿では,高解像度画像と映像をリアルタイムにセマンティックセグメンテーションするための新しいアーキテクチャを提案する。
提案したアーキテクチャは我々の空間的注意の速さに依存しており、これは一般的な自己注意機構の単純かつ効率的な修正である。
複数のデータセットに対する結果から,既存の手法に比べて精度と速度が向上し,優れた性能を示した。
論文 参考訳（メタデータ） (2020-07-07T22:37:16Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。