論文の概要: 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の場合)までのインクリメンタルなアプローチが、単純無作為なランダムな方法として空でない多くの有効なテストケースを生み出します。
私たちは、アプローチの単純さと汎用性が、実際に広く採用されることにつながると信じています。
関連論文リスト
- Preference Optimization for Reasoning with Pseudo Feedback [100.62603571434167]
提案手法では,解のラベル付けを関連するテストケースに対する評価として行うことで,推論タスクに対する疑似フィードバックを生成する手法を提案する。
本研究では,擬似フィードバックを優先最適化に用いる数学的推論と符号化の両タスクについて実験を行い,両タスク間の改善を観察する。
論文 参考訳（メタデータ） (2024-11-25T12:44:02Z) - Not All Votes Count! Programs as Verifiers Improve Self-Consistency of Language Models for Math Reasoning [24.386388107656334]
本稿では,プログラムベースの検証を用いて,潜在的に誤った推論経路をフィルタリングするPROVEを提案する。
バニラ多数決に頼る代わりに、我々の手法は、対応するプログラム出力が生成された解と矛盾する解を拒絶する。
PROVEは、すべてのデータセットとモデルサイズにわたる数学的推論タスクを解決するために、バニラ投票を一貫して上回っている。
論文 参考訳（メタデータ） (2024-10-16T14:24:55Z) - B4: Towards Optimal Assessment of Plausible Code Solutions with Plausible Tests [16.19318541132026]
ベイズフレームワーク内では、解と試験の間の観測された通過状態の後続確率に基づいて最適な選択戦略が定義されることを示す。
本稿では,この最適(計算不可能な)戦略を近似するための効率的な手法を提案する。
論文 参考訳（メタデータ） (2024-09-13T10:22:08Z) - Easy over Hard: A Simple Baseline for Test Failures Causes Prediction [13.759493107661834]
NCCheckerは、失敗したテストログの障害原因を自動的に識別するツールである。
当社のアプローチには,ログの抽象化,ルックアップテーブルの構築,障害発生予測という,3つの主要なステージがあります。
我々は,10K以上のテストログを持つ実世界の産業データセット上で,プロトタイプを開発し,ツールの評価を行った。
論文 参考訳（メタデータ） (2024-05-05T12:59: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) - ALGO: Synthesizing Algorithmic Programs with LLM-Generated Oracle
Verifiers [60.6418431624873]
大きな言語モデル(LLM)は、機能記述からコードを実装するのに優れているが、アルゴリズムの問題に悩まされている。
我々は,アルゴリズムプログラムを LLM 生成 Oracle で合成するフレームワーク ALGO を提案し,その生成をガイドし,その正確性を検証する。
実験の結果,ALGOを装着すると,Codexモデルよりも8倍,CodeTよりも2.6倍の1サブミッションパス率が得られることがわかった。
論文 参考訳（メタデータ） (2023-05-24T00:10:15Z) - Teaching Large Language Models to Self-Debug [62.424077000154945]
大規模言語モデル(LLM)は、コード生成において素晴らしいパフォーマンスを達成した。
本稿では,大規模言語モデルで予測プログラムを数発のデモでデバッグする自己デバッグを提案する。
論文 参考訳（メタデータ） (2023-04-11T10:43:43Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。