論文の概要: Towards the Systematic Testing of Regular Expression Engines

• arxiv url: http://arxiv.org/abs/2603.00311v1
• Date: Fri, 27 Feb 2026 21:00:31 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-03-10 12:52:36.575287
• Title: Towards the Systematic Testing of Regular Expression Engines
• Title（参考訳）: 正規表現エンジンの系統試験に向けて
• Authors: Berk Çakar, Dongyoon Lee, James C. Davis,
• Abstract要約: ReTestは、正規表現エンジンを体系的にテストするフレームワークである。 文法を意識したファジィングをハイコードカバレッジとメタモルフィックテストを組み合わせて、方言に依存しないテストオラクルを生成する。 PCREに関する予備評価では、ReTestは既存のファジィ手法よりも3倍高いエッジカバレッジを実現している。
• 参考スコア（独自算出の注目度）: 8.561133495117675
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Software engineers use regular expressions (regexes) across a wide range of domains and tasks. To support regexes, software projects must integrate a regex engine, whether provided natively by the language runtime (e.g., Python's re) or included as an external dependency (e.g., PCRE). However, these engines may contain bugs and introduce vulnerabilities. A common strategy for testing regex engines involves differential testing -- comparing outputs across different implementations. However, this approach is concerning because regex syntax and semantics vary significantly between dialects (e.g., POSIX vs. PCRE). Fuzzing is also utilized to ease testing of feature-rich regex implementations to expose defects, but naive byte-level mutations generate syntactically invalid inputs that exercise only parsing logic, not matching internals. In this work, we describe our progress towards ReTest, a framework that systematically tests regular expression engines by combining grammar-aware fuzzing for high code coverage with metamorphic testing to generate dialect-independent test oracles. So far, we have surveyed testing practices across 22 regex engines, analyzed 1,007 regex engine bugs and 156 CVEs to characterize failure modes, and curated 16 metamorphic relations for regexes derived from Kleene algebra. Our preliminary evaluation on PCRE shows that ReTest achieves 3x higher edge coverage than existing fuzzing approaches and has identified three new memory safety defects. We conclude by describing our next steps toward our ultimate goal: helping regex engine developers identify bugs without depending on a consistent cross-implementation standard.
• Abstract（参考訳）: ソフトウェアエンジニアは、さまざまなドメインやタスクにまたがって正規表現(regexes)を使用する。 regexをサポートするために、ソフトウェアプロジェクトは、言語ランタイム(例えばPythonのre)がネイティブに提供するか、外部依存(例えばPCRE)として含めるか、regexエンジンを統合する必要がある。 しかし、これらのエンジンにはバグが含まれ、脆弱性が導入される可能性がある。 regexエンジンをテストする一般的な戦略は、異なる実装間で出力を比較する差分テストである。 しかし、このアプローチは、regex構文と意味が方言(例えばPOSIX対PCRE)間で大きく異なるため、関係している。 ファジングはまた、機能豊富なregex実装のテストを簡単にして欠陥を公開するためにも使われるが、単純でバイトレベルの突然変異は構文的に無効な入力を生成し、内部と一致しない解析ロジックのみを実行する。 本稿では,文法を意識したファジングとメタモルフィックテストを組み合わせて,方言に依存しないテストオラクルを生成することで,正規表現エンジンを体系的にテストするフレームワークであるReTestについて述べる。 これまでに,22基のRegexエンジンにおけるテストプラクティスを調査し,故障モードを特徴付けるために1,007基のRegexエンジンバグと156基のCVEを分析し,Kleene代数から派生したRegexに対する16のメタモルフィック関係をキュレートした。 PCREの予備評価では、ReTestは既存のファジィ手法よりも3倍高いエッジカバレッジを実現し、3つの新たなメモリ安全性欠陥を同定した。 最終的な目標に向けての次のステップとして、regexエンジン開発者が一貫したクロス実装標準に依存することなくバグを特定するのを支援すること、を述べて締めくくります。

関連論文リスト

• Protocol Testing with I/O Grammars [45.68497486907946]
  本稿では,単一フレームワークにおける入力生成と出力チェックを組み合わせた新しいプロトコルテスト手法を提案する。 我々は、I/O文法が、テスト中のプログラムの出力検証を可能にするとともに、高度なプロトコルの特徴を正しく、完全に指定できることを実証する。
  論文  参考訳（メタデータ） (2025-09-24T16:41:04Z)
• Is Reuse All You Need? A Systematic Comparison of Regular Expression Composition Strategies [7.304676960008862]
  合成は一般的ですが 難しいエンジニアリング活動です 開発者はソースから既存のコンポジションを一般的に再利用する。 現在までに、これらの様々な構成戦略と比較する作業は行われていない。
  論文  参考訳（メタデータ） (2025-03-26T14:25:27Z)
• LlamaRestTest: Effective REST API Testing with Small Language Models [50.058600784556816]
  LlamaRestTestは、2つのLLM(Large Language Models)を使って現実的なテストインプットを生成する新しいアプローチである。 私たちは、GPTを使った仕様強化ツールであるRESTGPTなど、最先端のREST APIテストツールに対して、これを評価しています。 私たちの研究は、REST APIテストにおいて、小さな言語モデルは、大きな言語モデルと同様に、あるいは、より良く機能することができることを示しています。
  論文  参考訳（メタデータ） (2025-01-15T05:51:20Z)
• REST: Retrieval-Based Speculative Decoding [69.06115086237207]
  本稿では,言語モデル生成の高速化を目的とした新しいアルゴリズムであるRetrieval-Based Speculative Decoding(REST)を紹介する。 投機的復号化のためのドラフト言語モデルに依存する従来の方法とは異なり、RESTは検索の力を利用してドラフトトークンを生成する。 単一バッチ環境で7Bと13Bの言語モデルでベンチマークすると、RESTはコードやテキスト生成において1.62Xから2.36Xの大幅なスピードアップを達成する。
  論文  参考訳（メタデータ） (2023-11-14T15:43:47Z)
• RAP-Gen: Retrieval-Augmented Patch Generation with CodeT5 for Automatic Program Repair [75.40584530380589]
  新たな検索型パッチ生成フレームワーク(RAP-Gen)を提案する。 RAP-Gen 以前のバグ修正ペアのリストから取得した関連する修正パターンを明示的に活用する。 RAP-GenをJavaScriptのTFixベンチマークとJavaのCode RefinementとDefects4Jベンチマークの2つのプログラミング言語で評価する。
  論文  参考訳（メタデータ） (2023-09-12T08:52:56Z)
• InfeRE: Step-by-Step Regex Generation via Chain of Inference [15.276963928784047]
  本稿では,ステップ・バイ・ステップ推論の連鎖に表現の生成を分解するInfeREという新しいパラダイムを提案する。 我々は、NL-RX-TurkとKB13の2つの公開データセット上でInfeREを評価し、その結果を最先端のアプローチと人気のツリーベース生成アプローチであるTRANXと比較した。
  論文  参考訳（メタデータ） (2023-08-08T04:37:41Z)
• Improving Structured Text Recognition with Regular Expression Biasing [13.801707647700727]
  本研究では,ある形式に従う構造化テキストの認識の問題について検討する。 偏見の正規表現 (regexes) を指定することにより, 構造化テキストの認識精度を向上させることを提案する。
  論文  参考訳（メタデータ） (2021-11-10T23:12:05Z)
• Wasserstein Distance Regularized Sequence Representation for Text Matching in Asymmetrical Domains [51.91456788949489]
  WD-Matchと呼ばれる非対称領域におけるテキストマッチングに適した新しいマッチング手法を提案する。 WD-Matchでは、ワッサーシュタイン距離に基づく正規化器が定義され、異なる領域から投影される特徴ベクトルを正規化する。 WD-Matchのトレーニングプロセスは、ワッサースタイン距離によって正規化されるマッチング損失を最小限に抑えるゲームに相当する。
  論文  参考訳（メタデータ） (2020-10-15T12:52:09Z)
• Benchmarking Multimodal Regex Synthesis with Complex Structures [45.35689345004124]
  自然言語から正規表現(regex)を生成する既存のデータセットは、複雑さに制限されている。 従来のものと異なる新しい合成データセットであるStructuredRegexを3つの側面で紹介する。
  論文  参考訳（メタデータ） (2020-05-02T00:16:09Z)

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

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