論文の概要: GraphFuzz: Automated Testing of Graph Algorithm Implementations with Differential Fuzzing and Lightweight Feedback
- arxiv url: http://arxiv.org/abs/2502.15160v1
- Date: Fri, 21 Feb 2025 02:47:05 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-02-24 16:10:32.498909
- Title: GraphFuzz: Automated Testing of Graph Algorithm Implementations with Differential Fuzzing and Lightweight Feedback
- Title（参考訳）: GraphFuzz: 差分ファジィと軽量フィードバックを備えたグラフアルゴリズム実装の自動テスト
- Authors: Wenqi Yan, Manuel Rigger, Anthony Wirth, Van-Thuan Pham,
- Abstract要約: グラフアルゴリズム実装のための最初の自動フィードバック誘導ファジィフレームワークであるGraphFuzzを紹介する。
私たちの重要なイノベーションは、コードカバレッジフィードバックと組み合わせたり、完全に置き換えたりする、軽量でアルゴリズム固有のフィードバックシグナルを特定することです。
GraphFuzzは、クラッシュトリガバグとロジックバグの両方を検出するために差分テストを適用している。
- 参考スコア（独自算出の注目度）: 7.099737083842058
- License:
- Abstract: Graph algorithms, such as shortest path finding, play a crucial role in enabling essential applications and services like infrastructure planning and navigation, making their correctness important. However, thoroughly testing graph algorithm implementations poses several challenges, including their vast input space (i.e., arbitrary graphs). Moreover, through our preliminary study, we find that just a few automatically generated graphs (less than 10) could be enough to cover the code of many graph algorithm implementations, rendering the code coverage-guided fuzzing approach -- one of the state-of-the-art search algorithms -- less efficient than expected. To tackle these challenges, we introduce GraphFuzz, the first automated feedback-guided fuzzing framework for graph algorithm implementations. Our key innovation lies in identifying lightweight and algorithm-specific feedback signals to combine with or completely replace the code coverage feedback to enhance the diversity of the test corpus, thereby speeding up the bug-finding process. This novel idea also allows GraphFuzz to effectively work in both black-box (i.e., no code coverage instrumentation/collection is required) and grey-box setups. GraphFuzz applies differential testing to detect both crash-triggering bugs and logic bugs. Our evaluation demonstrates the effectiveness of GraphFuzz. The tool has successfully discovered 12 previously unknown bugs, including 6 logic bugs, in 9 graph algorithm implementations in two popular graph libraries, NetworkX and iGraph. All of them have been confirmed and and 11 bugs have been rectified by the libraries' maintainers.
- Abstract（参考訳）: 最短経路探索などのグラフアルゴリズムは、インフラストラクチャ計画やナビゲーションといった重要なアプリケーションやサービスの実現において重要な役割を果たす。
しかし、グラフアルゴリズムの実装を徹底的にテストすると、膨大な入力空間(すなわち任意のグラフ)を含むいくつかの課題が生じる。
さらに、予備的な調査を通じて、いくつかの自動生成されたグラフ(10未満)だけで、多くのグラフアルゴリズム実装のコードをカバーでき、コードカバレッジ誘導ファジィアプローチ、すなわち最先端の検索アルゴリズムの1つである -- は、予想より効率的ではないことが分かりました。
これらの課題に対処するために、グラフアルゴリズム実装のための最初のフィードバック誘導ファジィフレームワークであるGraphFuzzを紹介した。
私たちの重要なイノベーションは、テストコーパスの多様性を高めるために、ライトウェイトでアルゴリズム固有のフィードバックシグナルをコードカバレッジフィードバックと組み合わせたり、完全に置き換えたりすることです。
この新しいアイデアにより、GraphFuzzはブラックボックス(コードカバレッジインスツルメンテーションやコンパイルは不要)とグレーボックスのセットアップの両方で効果的に動作する。
GraphFuzzは、クラッシュトリガバグとロジックバグの両方を検出するために差分テストを適用している。
評価はGraphFuzzの有効性を示す。
このツールは6つのロジックバグを含む12の既知のバグを、人気のあるグラフライブラリであるNetworkXとiGraphの9つのグラフアルゴリズム実装で発見することに成功した。
いずれも確認されており、ライブラリのメンテナによって11のバグが修正されている。
関連論文リスト
- GraphFSA: A Finite State Automaton Framework for Algorithmic Learning on Graphs [18.95453617434051]
GraphFSAは、与えられたグラフの各ノード上で動作する有限状態オートマトンを学ぶように設計されている。
セルラーオートマトン問題に対してGraphFSAを試験し、その能力を簡単なアルゴリズム設定で示す。
メインのアプリケーションとして、より精巧なグラフアルゴリズムを学ぶことに集中します。
論文 参考訳（メタデータ） (2024-08-20T17:49:47Z) - Efficient Contextual Bandits with Uninformed Feedback Graphs [48.77120088347271]
フィードバックグラフを持つバンディットは、完全な情報と古典的なバンディットの問題を補間する強力なオンライン学習モデルである。
ここでは,2乗損失ではなくログ損失を用いてグラフを学習し,良好な後悔の保証を得ることが重要であることを示す。
論文 参考訳（メタデータ） (2024-02-12T23:50:47Z) - GSINA: Improving Subgraph Extraction for Graph Invariant Learning via
Graph Sinkhorn Attention [52.67633391931959]
グラフ不変学習(GIL)は,グラフデータとそのラベル間の不変性を発見するための効果的な手法である。
グラフシンクホーン注意機構(GSINA)を提案する。
GSINAは、制御可能な空間性と柔らかさを持つ有意義で微分可能な不変部分グラフを得ることができる。
論文 参考訳（メタデータ） (2024-02-11T12:57:16Z) - The Graph Lottery Ticket Hypothesis: Finding Sparse, Informative Graph
Structure [18.00833762891405]
Graph Lottery Ticket (GLT)仮説: グラフごとに非常に疎いバックボーンが存在する。
本研究は,グラフ学習アルゴリズムの性能に直接影響を及ぼす関心の指標を8つ研究する。
任意のグラフでこれらのGLTを見つけるための単純で効率的なアルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-12-08T00:24:44Z) - NAS-Bench-Graph: Benchmarking Graph Neural Architecture Search [55.75621026447599]
NAS-Bench-Graphは、GraphNASの統一的、再現可能、効率的な評価をサポートする調整されたベンチマークである。
具体的には,26,206のユニークなグラフニューラルネットワーク(GNN)アーキテクチャを網羅した,統一的で表現力のあるコンパクトな検索空間を構築する。
提案したベンチマークに基づいて,GNNアーキテクチャの性能を検索テーブルから直接取得できるが,それ以上の計算は行わない。
論文 参考訳（メタデータ） (2022-06-18T10:17:15Z) - GraphHop++: New Insights into GraphHop and Its Enhancement [37.61655151222875]
GraphHopと呼ばれる拡張ラベル伝搬(LP)法が最近提案されている。
グラフ畳み込みネットワーク(GCN)は、様々なネットワーク上の半教師付きノード分類タスクにおいて優れる。
グラフ上で定義された特定の正規化問題に対して、グラフホップが代替的な最適化を提供することを示す。
論文 参考訳（メタデータ） (2022-04-19T03:58:47Z) - Synthetic Graph Generation to Benchmark Graph Learning [7.914804101579097]
グラフ学習アルゴリズムは多くのグラフ解析タスクで最先端のパフォーマンスを達成した。
1つの理由は、グラフ学習アルゴリズムのパフォーマンスをベンチマークするために実際に使用されるデータセットが極めて少ないためである。
本稿では,合成グラフの生成と,制御シナリオにおけるグラフ学習アルゴリズムの挙動について検討する。
論文 参考訳（メタデータ） (2022-04-04T10:48:32Z) - Graphon based Clustering and Testing of Networks: Algorithms and Theory [11.3700474413248]
ネットワークに価値のあるデータは、幅広いアプリケーションで遭遇し、学習の課題を提起する。
本稿では,2つのクラスタリングアルゴリズムについて述べる。
さらに、グラフ2サンプルテスト問題に対する提案した距離の適用性について検討する。
論文 参考訳（メタデータ） (2021-10-06T13:14:44Z) - Deep Fraud Detection on Non-attributed Graph [61.636677596161235]
グラフニューラルネットワーク(GNN)は不正検出に強い性能を示している。
ラベル付きデータは大規模な産業問題、特に不正検出には不十分である。
よりラベルのないデータを活用するための新しいグラフ事前学習戦略を提案する。
論文 参考訳（メタデータ） (2021-10-04T03:42:09Z) - Learnable Graph Matching: Incorporating Graph Partitioning with Deep
Feature Learning for Multiple Object Tracking [58.30147362745852]
フレーム間のデータアソシエーションは、Multiple Object Tracking(MOT)タスクの中核にある。
既存の手法は、主にトラックレットとフレーム内検出の間のコンテキスト情報を無視する。
そこで本研究では,学習可能なグラフマッチング手法を提案する。
論文 参考訳（メタデータ） (2021-03-30T08:58:45Z) - Online Dense Subgraph Discovery via Blurred-Graph Feedback [87.9850024070244]
我々は高密度サブグラフ発見のための新しい学習問題を導入する。
まず,確率の高いほぼ最適解を求めるエッジ時間アルゴリズムを提案する。
そして、理論的保証のあるよりスケーラブルなアルゴリズムを設計する。
論文 参考訳（メタデータ） (2020-06-24T11:37:33Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。