論文の概要: Completeness of FSM Test Suites Reconsidered

• arxiv url: http://arxiv.org/abs/2410.19405v1
• Date: Fri, 25 Oct 2024 09:08:47 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-10-28 13:37:05.721182
• Title: Completeness of FSM Test Suites Reconsidered
• Title（参考訳）: FSMテストスイートの完全性再考
• Authors: Frits Vaandrager, Paul Fiterău-Broştean, Ivo Melse,
• Abstract要約: 有限状態機械(FSM)に対するテストスイートのemph$k$-$A$完全性の条件を示す。 予備的な証拠は、これらの障害ドメインがネットワークプロトコルのテストに実用的であることを示唆している。
• 参考スコア（独自算出の注目度）: 0.0
• License:
• Abstract: A fault domain that has been widely studied in black-box conformance testing is the class of finite state machines (FSMs) with at most $k$ extra states. Numerous methods for generating test suites have been proposed that guarantee fault coverage for this class. These test suites grow exponentially in $k$, so one can only run them for small $k$. But the assumption that $k$ is small is not realistic in practice. As a result, completeness for this fault domain has limited practical significance. As an alternative, we propose (much larger) fault domains that capture the assumption that when bugs in an implementation introduce extra states, these states can be reached via a few (at most $k$) transitions from states reachable via a set $A$ of common scenarios. Preliminary evidence suggests these fault domains, which contain FSMs with an exponential number of extra states (in $k$), are of practical use for testing network protocols. We present a sufficient condition for \emph{$k$-$A$-completeness} of test suites with respect to these fault domains, phrased entirely in terms of properties of their testing tree. Our condition implies $k$-$A$-completeness of two prominent test suite generation algorithms, the Wp and HSI methods. Counterexamples show that three other approaches, the H, SPY and SPYH methods, do not always generate $k$-$A$-complete test suites.
• Abstract（参考訳）: ブラックボックス適合性試験で広く研究されている断層領域は、有限状態機械(FSM)のクラスであり、最大で$k$余分な状態を持つ。 このクラスの障害カバレッジを保証するために、テストスイートを生成する多くの方法が提案されている。 これらのテストスイートは$k$で指数関数的に成長するので、小さな$k$でしか実行できない。 しかし、$k$が小さいという仮定は現実的には現実的ではない。 結果として、この断層領域の完全性は、実用的重要性に制限される。 代替として、実装中のバグが余分な状態を導入すると、これらの状態は、一般的なシナリオのセット$A$を介して、到達可能な状態からいくつかの(ほとんどの$k$で)遷移によって到達できるという仮定を捉える(非常に大きい)フォールトドメインを提案する。 予備的な証拠は、これらの障害ドメインは、指数関数的に多くの追加状態($k$)を持つFSMを含み、ネットワークプロトコルをテストするために実用的であることを示唆している。 テストスイートのこれらの障害ドメインに関して,テストツリーの特性を全て表現した,テストスイートの‘emph{$k$-$A$-completeness’ に十分な条件を提示する。 我々の条件は、Wp法とHSI法という2つの有名なテストスイート生成アルゴリズムの$k$-$A$完全性を意味する。 Counterexamplesは、H、SPY、SPYHの3つの他のアプローチが、必ずしも$k$-$A$-completeテストスイートを生成するわけではないことを示している。

関連論文リスト

• Nearly tight bounds for testing tree tensor network states [0.0]
  ツリーテンソルネットワーク状態(TTNS)は、シュミットランクが低いから多部量子状態を持つという概念を一般化する。 我々は、未知の純状態が、結合次元が最大$r$の$n$クォーディット上のTTNSであるかどうかをテストするタスクを研究する。 また,少数のコピーに対して一度に実施した測定値を用いて,テストの性能についても検討した。
  論文  参考訳（メタデータ） (2024-10-28T18:13:38Z)
• Testing the Feasibility of Linear Programs with Bandit Feedback [53.40256244941895]
  我々は,低回帰アルゴリズムと反復対数の漸近法則に基づくテストを開発する。 このテストが信頼できることを証明し、信号レベルに適応する'$Gamma,$ of any instance。 信頼性テストのサンプルコストに対して、最小限の$(Omegad/Gamma2)$で補う。
  論文  参考訳（メタデータ） (2024-06-21T20:56:35Z)
• Permutation tests for quantum state identity [0.0]
  n$未知の量子状態が等しいか不等であるかを決定する問題は、量子状態アイデンティティ問題として知られている。 置換テストはこのタスクに最適であることが知られており、2つの入力状態に対してはよく知られたスワップテストと一致する。 この研究は、量子状態のアイデンティティ問題(きめ細かい定式化)の基盤となる構造を捉えようとする。
  論文  参考訳（メタデータ） (2024-05-15T18:00:07Z)
• Collaborative non-parametric two-sample testing [55.98760097296213]
  目標は、null仮説の$p_v = q_v$が拒否されるノードを特定することである。 グラフ構造を効率的に活用する非パラメトリックコラボレーティブ2サンプルテスト(CTST)フレームワークを提案する。 提案手法は,f-divergence Estimation, Kernel Methods, Multitask Learningなどの要素を統合する。
  論文  参考訳（メタデータ） (2024-02-08T14:43:56Z)
• Reaching Goals is Hard: Settling the Sample Complexity of the Stochastic Shortest Path [106.37656068276902]
  本稿では,最短経路(SSP)問題において,$epsilon$-optimal Policyを学習する際のサンプル複雑性について検討する。 学習者が生成モデルにアクセスできる場合、複雑性境界を導出する。 我々は、$S$状態、$A$アクション、最小コスト$c_min$、およびすべての状態に対する最適ポリシーの最大期待コストを持つ最悪のSSPインスタンスが存在することを示す。
  論文  参考訳（メタデータ） (2022-10-10T18:34:32Z)
• Prioritized Variable-length Test Cases Generation for Finite State Machines [0.09786690381850353]
  モデルベーステスト(MBT)は、システムアンダーテストの一部が有限状態マシン(FSM)の特性を持つ場合のテストに有効な手法である。 本稿では,これらの要件をすべて満たしたテスト生成戦略を提案する。 本論文では,FSMの適用状況に応じて,機能的および非機能的ソフトウェア要件のテストにも適用可能である。
  論文  参考訳（メタデータ） (2022-03-17T20:16:45Z)
• Testing matrix product states [5.225550006603552]
  未知の状態$|psirangle$が特性試験モデルにおける行列積状態(MPS)かどうかをテストする。 MPS(英: MPS)は、量子多体系の研究で生じる物理関連量子状態のクラスである。
  論文  参考訳（メタデータ） (2022-01-05T21:10:50Z)
• Improved Sample Complexity for Incremental Autonomous Exploration in MDPs [132.88757893161699]
  我々は $epsilon$-optimal 目標条件付きポリシーのセットを学び、$ L$ ステップ内で段階的に到達可能なすべての状態を達成します。 DisCoは、コストに敏感な最短経路問題に対して$epsilon/c_min$-optimalポリシーを返すことができる最初のアルゴリズムです。
  論文  参考訳（メタデータ） (2020-12-29T14:06:09Z)
• Optimal Testing of Discrete Distributions with High Probability [49.19942805582874]
  高確率状態に着目して離散分布を試験する問題について検討する。 一定の要素でサンプル最適である近接性および独立性テストのための最初のアルゴリズムを提供する。
  論文  参考訳（メタデータ） (2020-09-14T16:09:17Z)
• Locally Private Hypothesis Selection [96.06118559817057]
  我々は、$mathcalQ$から$p$までの総変動距離が最良の分布に匹敵する分布を出力する。 局所的な差分プライバシーの制約は、コストの急激な増加を引き起こすことを示す。 提案アルゴリズムは,従来手法のラウンド複雑性を指数関数的に改善する。
  論文  参考訳（メタデータ） (2020-02-21T18:30:48Z)

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

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