論文の概要: Indexing Context-Sensitive Reachability
- arxiv url: http://arxiv.org/abs/2109.01321v1
- Date: Fri, 3 Sep 2021 05:41:30 GMT
- ステータス: 処理完了
- システム内更新日: 2021-09-06 13:56:15.047666
- Title: Indexing Context-Sensitive Reachability
- Title(参考訳): インデクシングコンテキスト感度の到達可能性
- Authors: Qingkai Shi, Yongchao Wang, Charles Zhang
- Abstract要約: textscFlareは、文脈依存型データフロー解析のための従来のグラフ到達可能性問題から従来のグラフ到達性問題への還元である。
我々は,C/C++プログラムの文脈感性エイリアス解析と文脈感性情報フロー解析に適用した。
- 参考スコア(独自算出の注目度): 16.114012813668932
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Many context-sensitive data flow analyses can be formulated as a variant of
the all-pairs Dyck-CFL reachability problem, which, in general, is of sub-cubic
time complexity and quadratic space complexity. Such high complexity
significantly limits the scalability of context-sensitive data flow analysis
and is not affordable for analyzing large-scale software. This paper presents
\textsc{Flare}, a reduction from the CFL reachability problem to the
conventional graph reachability problem for context-sensitive data flow
analysis. This reduction allows us to benefit from recent advances in
reachability indexing schemes, which often consume almost linear space for
answering reachability queries in almost constant time. We have applied our
reduction to a context-sensitive alias analysis and a context-sensitive
information-flow analysis for C/C++ programs. Experimental results on standard
benchmarks and open-source software demonstrate that we can achieve orders of
magnitude speedup at the cost of only moderate space to store the indexes. The
implementation of our approach is publicly available.
- Abstract(参考訳): 多くの文脈に敏感なデータフロー解析は、全てのペア dyck-cfl 到達可能性問題の変種として定式化することができる。
このような高い複雑さは、コンテキストに敏感なデータフロー分析のスケーラビリティを著しく制限し、大規模なソフトウェアを分析するには手頃ではない。
本稿では,コンテキストに敏感なデータフロー解析のための,cfl到達可能性問題から従来のグラフ到達可能性問題への還元である \textsc{flare} を提案する。
この削減により、ほぼ一定時間でリーチビリティクエリに答えるために、ほぼ線形空間を消費する、リーチビリティインデクシングスキームの最近の進歩の恩恵を受けることができる。
我々は,C/C++プログラムの文脈感性エイリアス解析と文脈感性情報フロー解析に適用した。
標準ベンチマークとオープンソースソフトウェアによる実験結果から、インデックスを格納するための適度なスペースのみのコストで、桁違いのスピードアップを達成できることが示されている。
私たちのアプローチの実装は公開されています。
関連論文リスト
- AcceleratedLiNGAM: Learning Causal DAGs at the speed of GPUs [57.12929098407975]
既存の因果探索法を効率的に並列化することにより,数千次元まで拡張可能であることを示す。
具体的には、DirectLiNGAMの因果順序付けサブプロデューサに着目し、GPUカーネルを実装して高速化する。
これにより、遺伝子介入による大規模遺伝子発現データに対する因果推論にDirectLiNGAMを適用することで、競争結果が得られる。
論文 参考訳(メタデータ) (2024-03-06T15:06:11Z) - When Dataflow Analysis Meets Large Language Models [9.458251511218817]
本稿では,LLMDFAについて述べる。LLMDFAはLLLMを利用したデータフロー解析フレームワークで,コンパイルインフラを必要とせずに任意のコードスニペットを解析する。
LLMDFAは、要約に基づくデータフロー分析にヒントを得て、問題を3つのサブプロブレムに分解し、いくつかの重要な戦略によって効果的に解決する。
評価の結果,本設計は幻覚を緩和し,推論能力を向上し,データフロー関連バグの検出において高い精度とリコールが得られることがわかった。
論文 参考訳(メタデータ) (2024-02-16T15:21:35Z) - Building Interpretable and Reliable Open Information Retriever for New
Domains Overnight [67.03842581848299]
情報検索は、オープンドメイン質問応答(QA)など、多くのダウンストリームタスクにとって重要な要素である。
本稿では、エンティティ/イベントリンクモデルとクエリ分解モデルを用いて、クエリの異なる情報単位により正確にフォーカスする情報検索パイプラインを提案する。
より解釈可能で信頼性が高いが,提案したパイプラインは,5つのIRおよびQAベンチマークにおける通過カバレッジと記述精度を大幅に向上することを示す。
論文 参考訳(メタデータ) (2023-08-09T07:47:17Z) - Analysis and Optimization of Wireless Federated Learning with Data
Heterogeneity [72.85248553787538]
本稿では、データの不均一性を考慮した無線FLの性能解析と最適化と、無線リソース割り当てについて述べる。
ロス関数の最小化問題を、長期エネルギー消費と遅延の制約の下で定式化し、クライアントスケジューリング、リソース割り当て、ローカルトレーニングエポック数(CRE)を共同で最適化する。
実世界のデータセットの実験により、提案アルゴリズムは学習精度とエネルギー消費の点で他のベンチマークよりも優れていることが示された。
論文 参考訳(メタデータ) (2023-08-04T04:18:01Z) - Salesforce CausalAI Library: A Fast and Scalable Framework for Causal
Analysis of Time Series and Tabular Data [76.85310770921876]
観測データを用いた因果解析のためのオープンソースライブラリであるSalesforce CausalAI Libraryを紹介した。
このライブラリの目標は、因果関係の領域における様々な問題に対して、迅速かつ柔軟なソリューションを提供することである。
論文 参考訳(メタデータ) (2023-01-25T22:42:48Z) - Computing unsatisfiable cores for LTLf specifications [3.251765107970636]
有限トレース上の線形時間時間時間論理(LTLf)は、多くのアプリケーション領域で仕様を作成するためのデファクト標準になりつつある。
満足度チェックのための最先端手法を用いて、不満足なコアを抽出する4つのアルゴリズムを提案する。
結果は、異なるアルゴリズムやツールの実現可能性、有効性、相補性を示している。
論文 参考訳(メタデータ) (2022-03-09T16:08:43Z) - Provable Reinforcement Learning with a Short-Term Memory [68.00677878812908]
我々はPMDPsの新しいサブクラスについて研究し、その潜在状態は、最近の短い長さ$m$の履歴によって復号化することができる。
特に、リッチ・オブザーブレーション・セッティングにおいて、指数関数的にスケールするサンプル複雑性を持つ新しい「モーメントマッチング」アプローチを用いて、新しいアルゴリズムを開発する。
以上の結果から,これらの環境下での強化学習には短期記憶が十分であることが示唆された。
論文 参考訳(メタデータ) (2022-02-08T16:39:57Z) - ExClus: Explainable Clustering on Low-dimensional Data Representations [9.496898312608307]
次元の減少とクラスタリング技術は複雑なデータセットの分析に頻繁に使用されるが、それらの結果は容易には解釈できないことが多い。
本研究では, 直接解釈できない散乱プロット上で, クラスタ構造を解釈する際のユーザ支援について検討する。
本稿では,解釈可能なクラスタリングを自動的に計算する新しい手法を提案し,その説明は元の高次元空間にあり,クラスタリングは低次元射影においてコヒーレントである。
論文 参考訳(メタデータ) (2021-11-04T21:24:01Z) - A general sample complexity analysis of vanilla policy gradient [101.16957584135767]
政策勾配(PG)は、最も一般的な強化学習(RL)問題の1つである。
PG軌道の「バニラ」理論的理解は、RL問題を解く最も一般的な方法の1つである。
論文 参考訳(メタデータ) (2021-07-23T19:38:17Z) - A Complementarity Analysis of the COCO Benchmark Problems and
Artificially Generated Problems [0.0]
本稿では,このような単目的連続問題生成手法をCOCOベンチマーク問題セットと比較検討する。
このような表現により、可視化と相関解析技術を適用して、問題間の関係をさらに探求できることを示す。
論文 参考訳(メタデータ) (2021-04-27T09:18:43Z) - Comparative Analysis of Extreme Verification Latency Learning Algorithms [3.3439097577935213]
本稿では、EVLアルゴリズムのいくつかの弱点と強みを指摘するための総合的な調査と比較分析を行う。
この研究は、この分野の既存のアルゴリズムのレビューを研究コミュニティに提供するための、非常に最初の取り組みである。
論文 参考訳(メタデータ) (2020-11-26T16:34:56Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。