論文の概要: An Incremental Algorithm for Algebraic Program Analysis

• arxiv url: http://arxiv.org/abs/2412.10632v1
• Date: Sat, 14 Dec 2024 01:18:32 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-12-17 13:58:55.814783
• Title: An Incremental Algorithm for Algebraic Program Analysis
• Title（参考訳）: 代数的プログラム解析のためのインクリメンタルアルゴリズム
• Authors: Chenyu Zhou, Yuzhou Fang, Jingbo Wang, Chao Wang,
• Abstract要約: インクリメンタルアルゴリズムの目標は、プログラムの変更前に計算された中間結果を活用することで解析時間を短縮することである。 提案手法を実装し,DaCapoベンチマークスイートから13のJavaアプリケーション上で評価を行った。 ベースラインAPA法と2つの最先端APA法と比較して,本手法の高速化はプログラム解析の種類によって160Xから4761Xの範囲に及んでいる。
• 参考スコア（独自算出の注目度）: 6.333695701603308
• License:
• Abstract: We propose a method for conducting algebraic program analysis (APA) incrementally in response to changes of the program under analysis. APA is a program analysis paradigm that consists of two distinct steps: computing a path expression that succinctly summarizes the set of program paths of interest, and interpreting the path expression using a properly-defined semantic algebra to obtain program properties of interest. In this context, the goal of an incremental algorithm is to reduce the analysis time by leveraging the intermediate results computed before the program changes. We have made two main contributions. First, we propose a data structure for efficiently representing path expression as a tree together with a tree-based interpreting method. Second, we propose techniques for efficiently updating the program properties in response to changes of the path expression. We have implemented our method and evaluated it on thirteen Java applications from the DaCapo benchmark suite. The experimental results show that both our method for incrementally computing path expression and our method for incrementally interpreting path expression are effective in speeding up the analysis. Compared to the baseline APA and two state-of-the-art APA methods, the speedup of our method ranges from 160X to 4761X depending on the types of program analyses performed.
• Abstract（参考訳）: 本稿では,解析対象プログラムの変更に応じて,代数的プログラム解析(APA)を漸進的に実施する手法を提案する。 APAは、関心のプログラムパスの集合を簡潔に要約した経路表現を計算し、適切に定義された意味代数学を用いて経路表現を解釈し、興味のプログラム特性を得るという、2つの異なるステップからなるプログラム解析パラダイムである。 この文脈では、インクリメンタルアルゴリズムの目標は、プログラムが変化する前に計算された中間結果を活用することで解析時間を短縮することである。 主な貢献は2つあります。 まず,木をベースとした解釈手法とともに,木としての経路表現を効率的に表現するデータ構造を提案する。 次に,経路表現の変化に応じてプログラム特性を効率的に更新する手法を提案する。 提案手法を実装し,DaCapoベンチマークスイートから13のJavaアプリケーション上で評価を行った。 実験の結果,経路表現をインクリメンタルに計算する手法と経路表現をインクリメンタルに解釈する手法の両方が解析の高速化に有効であることが示唆された。 ベースラインAPA法と2つの最先端APA法と比較して,本手法の高速化はプログラム解析の種類によって160Xから4761Xの範囲に及んでいる。

関連論文リスト

• Icing on the Cake: Automatic Code Summarization at Ericsson [4.145468342589189]
  我々は,プロンプトの自動意味拡張(ASAP)という手法の性能評価を行った。 静的なプログラム解析や情報検索,あるいは模範的な存在を必要としない4つの単純なアプローチのパフォーマンスを比較した。
  論文  参考訳（メタデータ） (2024-08-19T06:49:04Z)
• Path-optimal symbolic execution of heap-manipulating programs [5.639904484784126]
  本稿では、当初、ヒープ操作プログラムに対して経路最適性を実現するシンボル実行アルゴリズムであるPOSEについて紹介する。 我々は,POSEアルゴリズムを小型で汎用的なオブジェクト指向プログラミング言語に形式化し,プロトタイプのシンボルエグゼキュータに形式化を実装し,データ構造を入力とするサンプルプログラムのベンチマークに対して,アルゴリズムを実験する。
  論文  参考訳（メタデータ） (2024-07-23T20:35:33Z)
• Weakly Supervised Semantic Parsing with Execution-based Spurious Program Filtering [19.96076749160955]
  本稿では,プログラムの実行結果に基づくドメインに依存しないフィルタリング機構を提案する。 私たちはこれらの表現に対して多数決を行い、他のプログラムと大きく異なる意味を持つプログラムを特定し、フィルタリングします。
  論文  参考訳（メタデータ） (2023-11-02T11:45:40Z)
• Lagrangian based A* algorithm for automated reasoning [0.0]
  重み付けはA*アルゴリズムの一部として導入され、効率が向上する。 このアルゴリズムの応用はUAV経路計画に適用される。
  論文  参考訳（メタデータ） (2023-06-28T17:01:03Z)
• Improved Tree Search for Automatic Program Synthesis [91.3755431537592]
  重要な要素は、有効なプログラムの空間における効率的な探索を可能にすることである。 ここでは2つの大きな異なるDSL上でのアート結果の状態を導くMCTSの変種を提案する。
  論文  参考訳（メタデータ） (2023-03-13T15:09:52Z)
• Trajectory-based Algorithm Selection with Warm-starting [2.3823600586675724]
  本研究では,アルゴリズムの性能予測シナリオにおいて,性能回帰モデルとアルゴリズム選択モデルの品質と精度について検討する。 ウォームスタートを用いたトラジェクトリベースラン毎のアルゴリズム選択の有望な性能を示す。
  論文  参考訳（メタデータ） (2022-04-13T14:00:55Z)
• Amortized Implicit Differentiation for Stochastic Bilevel Optimization [53.12363770169761]
  決定論的条件と決定論的条件の両方において、二段階最適化問題を解決するアルゴリズムのクラスについて検討する。 厳密な勾配の推定を補正するために、ウォームスタート戦略を利用する。 このフレームワークを用いることで、これらのアルゴリズムは勾配の偏りのない推定値にアクセス可能な手法の計算複雑性と一致することを示す。
  論文  参考訳（メタデータ） (2021-11-29T15:10:09Z)
• Searching for More Efficient Dynamic Programs [61.79535031840558]
  本稿では,プログラム変換の集合,変換プログラムの効率を評価するための単純な指標,およびこの指標を改善するための探索手順について述べる。 実際に、自動検索は初期プログラムの大幅な改善を見出すことができることを示す。
  論文  参考訳（メタデータ） (2021-09-14T20:52:55Z)
• Provably Faster Algorithms for Bilevel Optimization [54.83583213812667]
  バイレベル最適化は多くの重要な機械学習アプリケーションに広く適用されている。 両レベル最適化のための2つの新しいアルゴリズムを提案する。 両アルゴリズムが$mathcalO(epsilon-1.5)$の複雑さを達成し,既存のアルゴリズムを桁違いに上回っていることを示す。
  論文  参考訳（メタデータ） (2021-06-08T21:05:30Z)
• Bilevel Optimization: Convergence Analysis and Enhanced Design [63.64636047748605]
  バイレベル最適化は多くの機械学習問題に対するツールである。 Stoc-BiO という新しい確率効率勾配推定器を提案する。
  論文  参考訳（メタデータ） (2020-10-15T18:09:48Z)
• Process Discovery for Structured Program Synthesis [70.29027202357385]
  プロセスマイニングにおける中核的なタスクは、イベントログデータから正確なプロセスモデルを学ぶことを目的としたプロセス発見である。 本稿では,ターゲットプロセスモデルとして(ブロック-)構造化プログラムを直接使用することを提案する。 我々は,このような構造化プログラムプロセスモデルの発見に対して,新たなボトムアップ・アグリメティブ・アプローチを開発する。
  論文  参考訳（メタデータ） (2020-08-13T10:33:10Z)

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

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