論文の概要: Finding Cross-rule Optimization Bugs in Datalog Engines

• arxiv url: http://arxiv.org/abs/2402.12863v1
• Date: Tue, 20 Feb 2024 09:54:52 GMT
• ステータス: 処理完了
• システム内更新日: 2024-02-21 15:53:22.868792
• Title: Finding Cross-rule Optimization Bugs in Datalog Engines
• Title（参考訳）: データログエンジンにおけるクロスルール最適化のバグ発見
• Authors: Chi Zhang, Linzhang Wang, Manuel Rigger
• Abstract要約: インクリメンタル・ルール・アセスメント(IRE)と呼ばれる自動テスト手法を提案する。 IREはテストのオラクルとテストケース生成の問題に取り組む。 We implement IRE as a tool named Deopt and evaluation it on four Datalog engine。
• 参考スコア（独自算出の注目度）: 8.849383195527627
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Datalog is a popular and widely-used declarative logic programming language. Datalog engines apply many cross-rule optimizations; bugs in them can cause incorrect results. To detect such optimization bugs, we propose an automated testing approach called Incremental Rule Evaluation (IRE), which synergistically tackles the test oracle and test case generation problem. The core idea behind the test oracle is to compare the results of an optimized program and a program without cross-rule optimization; any difference indicates a bug in the Datalog engine. Our core insight is that, for an optimized, incrementally-generated Datalog program, we can evaluate all rules individually by constructing a reference program to disable the optimizations that are performed among multiple rules. Incrementally generating test cases not only allows us to apply the test oracle for every new rule generated-we also can ensure that every newly added rule generates a non-empty result with a given probability and eschew recomputing already-known facts. We implemented IRE as a tool named Deopt, and evaluated Deopt on four mature Datalog engines, namely Souffl\'e, CozoDB, $\mu$Z, and DDlog, and discovered a total of 30 bugs. Of these, 13 were logic bugs, while the remaining were crash and error bugs. Deopt can detect all bugs found by queryFuzz, a state-of-the-art approach. Out of the bugs identified by Deopt, queryFuzz might be unable to detect 5. Our incremental test case generation approach is efficient; for example, for test cases containing 60 rules, our incremental approach can produce 1.17$\times$ (for DDlog) to 31.02$\times$ (for Souffl\'e) as many valid test cases with non-empty results as the naive random method. We believe that the simplicity and the generality of the approach will lead to its wide adoption in practice.
• Abstract（参考訳）: Datalogは広く使われている宣言型論理プログラミング言語である。 データログエンジンは多くのクロスルール最適化を適用します。 このような最適化バグを検出するために,テストオラクルとテストケース生成問題に相乗的に取り組むインクリメンタルルール評価(IRE)と呼ばれる自動テスト手法を提案する。 テストオラクルの背後にある中核的な考え方は、最適化されたプログラムとクロスルール最適化のないプログラムの結果を比較することである。 我々の中核的な洞察は、最適化されたインクリメンタルに生成されたDatalogプログラムでは、参照プログラムを構築して複数のルール間で実行される最適化を無効にすることで、各ルールを個別に評価できるということです。 増分的にテストケースを生成することで、新しいルールが生成されるたびにテストオラクルを適用できるだけでなく、新しく追加されたルールが与えられた確率で空でない結果を生成し、既に知られている事実を再計算することも保証できます。 ireをdeoptというツールとして実装し,suuffl\'e,cozodb,$\mu$z,ddlogという4つの成熟したデータログエンジン上でdeoptを評価し,合計30のバグを発見した。 そのうち13つはロジックのバグで、残りはクラッシュとエラーのバグだった。 Deoptは、最先端のアプローチであるQueryFuzzで見つかったすべてのバグを検出することができる。 Deoptが特定したバグのうち、QueryFuzzは5.1のバグを検出できないかもしれない。 例えば、60のルールを含むテストケースでは、1.17$\times$(DDlogの場合)から31.02$\times$(Souffl\'eの場合)までのインクリメンタルなアプローチが、単純無作為なランダムな方法として空でない多くの有効なテストケースを生み出します。 私たちは、アプローチの単純さと汎用性が、実際に広く採用されることにつながると信じています。

関連論文リスト

• EquiBench: Benchmarking Code Reasoning Capabilities of Large Language Models via Equivalence Checking [54.354203142828084]
  本稿では,大規模言語モデルのコード推論能力を評価する新しい手法として等価チェックの課題を提案する。 EquiBenchは、4つのプログラミング言語と6つの等価カテゴリにまたがる2400のプログラムペアのデータセットである。 その結果,OpenAI o3-miniの精度は78.0%と高いことがわかった。
  論文  参考訳（メタデータ） (2025-02-18T02:54:25Z)
• Constant Optimization Driven Database System Testing [6.246028398098516]
  ロジックバグ(Logic bugs)とは、データベース管理システム(DBMS)が、与えられたクエリに対する誤った結果を静かに生成する可能性があるバグである。 我々は,データベースの論理バグを検出する新しいアプローチとして,定数最適化駆動型データベーステスト(CODDTest)を提案する。
  論文  参考訳（メタデータ） (2025-01-20T03:32:55Z)
• Simple and Provable Scaling Laws for the Test-Time Compute of Large Language Models [70.07661254213181]
  大規模言語モデルのテスト時間計算のための2つの原理的アルゴリズムを提案する。 理論的には、1つのアルゴリズムの故障確率は、そのテスト時間計算が大きくなるにつれて指数関数的に減衰する。
  論文  参考訳（メタデータ） (2024-11-29T05:29:47Z)
• Preference Optimization for Reasoning with Pseudo Feedback [100.62603571434167]
  提案手法では,解のラベル付けを関連するテストケースに対する評価として行うことで,推論タスクに対する疑似フィードバックを生成する手法を提案する。 本研究では,擬似フィードバックを優先最適化に用いる数学的推論と符号化の両タスクについて実験を行い,両タスク間の改善を観察する。
  論文  参考訳（メタデータ） (2024-11-25T12:44:02Z)
• B4: Towards Optimal Assessment of Plausible Code Solutions with Plausible Tests [16.19318541132026]
  ベイズフレームワーク内では、解と試験の間の観測された通過状態の後続確率に基づいて最適な選択戦略が定義されることを示す。 本稿では,この最適(計算不可能な)戦略を近似するための効率的な手法を提案する。
  論文  参考訳（メタデータ） (2024-09-13T10:22:08Z)
• Code-Optimise: Self-Generated Preference Data for Correctness and Efficiency [15.593172556501704]
  Code-Optimiseは、正確性(パス、フェール)とランタイムの両方を学習信号として組み込んだフレームワークです。 私たちのフレームワークは軽量で堅牢で、オーバーフィッティングを減らすためのソリューションを動的に選択します。 副生成物として、生成した溶液の平均長はMBPPで48%、HumanEvalで23%減少する。
  論文  参考訳（メタデータ） (2024-06-18T11:05:37Z)
• Evolutionary Generative Fuzzing for Differential Testing of the Kotlin Compiler [14.259471945857431]
  JetBrainsが開発したKotlinコンパイラのバグ発見における差分テストの有効性について検討する。 そこで我々は,K1コンパイラとK2コンパイラの入力プログラムを生成するブラックボックス生成手法を提案する。 ケーススタディでは,提案手法がK1とK2のバグを効果的に検出している。
  論文  参考訳（メタデータ） (2024-01-12T16:01:12Z)
• FuzzyFlow: Leveraging Dataflow To Find and Squash Program Optimization Bugs [92.47146416628965]
  FuzzyFlowはプログラム最適化をテストするために設計されたフォールトローカライゼーションとテストケース抽出フレームワークである。 我々は、データフロープログラム表現を活用して、完全に再現可能なシステム状態と最適化のエリア・オブ・エフェクトをキャプチャする。 テスト時間を削減するため,テスト入力を最小限に抑えるアルゴリズムを設計し,再計算のためのメモリ交換を行う。
  論文  参考訳（メタデータ） (2023-06-28T13:00:17Z)
• CodeT: Code Generation with Generated Tests [49.622590050797236]
  テストケースを自動的に生成するための事前学習言語モデルについて検討する。 CodeTは生成されたテストケースを使ってコードソリューションを実行し、次に最良のソリューションを選択します。 我々は,HumanEvalとMBPPのベンチマークを用いて,5種類の事前学習モデル上でCodeTを評価する。
  論文  参考訳（メタデータ） (2022-07-21T10:18:37Z)
• Bayesian Algorithm Execution: Estimating Computable Properties of Black-box Functions Using Mutual Information [78.78486761923855]
  多くの現実世界では、T関数の評価の予算を考えると、高価なブラックボックス関数 f の性質を推測したい。 本稿では,アルゴリズムの出力に対して相互情報を最大化するクエリを逐次選択する手法InfoBAXを提案する。 これらの問題に対してInfoBAXは、元のアルゴリズムで要求されるより500倍少ないクエリをfに使用する。
  論文  参考訳（メタデータ） (2021-04-19T17:22:11Z)
• Revisiting Bayesian Optimization in the light of the COCO benchmark [1.4467794332678539]
  本稿では,共通かつあまり一般的ではない設計選択のbo(gaussian process based)の性能への影響について,大規模な調査を行う。 この研究のために開発されたコードは、RパッケージDiceOptimの新バージョン(v2.1.1)をCRANで利用可能にしている。
  論文  参考訳（メタデータ） (2021-03-30T19:45:18Z)

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

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