目次

NIST IR 7773 日本語訳

英語タイトル : An Application of Combinatorial Methods to Conformance Testing for Document Object Model Events
日本語タイトル : 文書オブジェクトモデルイベントの適合性試験への組合せ手法の適用
公開日 : 2010-11-01
原文URL : https://csrc.nist.gov/pubs/ir/7773/final
翻訳編集 : 自動生成(有志による非公式の日本語訳), 原文取得日 : 2026-10-31, 訳文 : 55 / 56 ブロック

[要約] NIST IR 7773 は、文書オブジェクトモデル(DOM)イベントの適合性試験に組合せ手法を適用した事例を報告する文書です。DOM Level 3 Events を対象に、すでに網羅的な試験として適用されていた DOM 試験スイートと比較して、組合せ試験が小さい試験スイートで同じ水準の欠陥検出を達成できるかを調べています。NIST とテキサス大学アーリントン校が開発したツールを用いて 2-way から 6-way までの被覆配列を作成し、どの水準の t-way 相互作用が必要かという問いにも取り組みました。結論では、組合せ試験により、DOM と似た特性を持つ標準の適合性試験に必要なコストと時間を大幅に減らせることが示唆され、比較的強い 4-way の試験でも元の試験集合の大きさの 5% であったと述べています。

NISTIR 7773

NISTIR 7773

An Application of Combinatorial Methods to Conformance Testing for Document Object Model Events

文書オブジェクトモデルイベントの適合性試験への組合せ手法の適用

Carmelo Montanez
D. Richard Kuhn
Mary Brady
Richard M. Rivello
Jenise Reyes
Michael K. Powers

Carmelo Montanez
D. Richard Kuhn
Mary Brady
Richard M. Rivello
Jenise Reyes
Michael K. Powers

図表
[NIST logo — not reproduced on this unofficial site]

[NIST のロゴ。公的な標章のため、この非公式サイトには掲載していません。原本 PDF を参照してください。]

NISTIR 7773

NISTIR 7773

An Application of Combinatorial Methods to Conformance Testing for Document Object Model Events

文書オブジェクトモデルイベントの適合性試験への組合せ手法の適用

Carmelo Montanez
D. Richard Kuhn
Mary Brady
Richard M. Rivello
Jenise Reyes
Michael K. Powers

Carmelo Montanez
D. Richard Kuhn
Mary Brady
Richard M. Rivello
Jenise Reyes
Michael K. Powers

November, 2010

2010年11月

U.S. Department of Commerce
Gary Locke, Secretary

米国商務省
Gary Locke 長官

National Institute of Standards and Technology
Patrick D. Gallagher, Director

米国国立標準技術研究所
Patrick D. Gallagher 所長

An Application of Combinatorial Methods to Conformance Testing for Document Object Model Events

文書オブジェクトモデルイベントの適合性試験への組合せ手法の適用

Abstract—This report describes the use of combinatorial test methods to reduce the cost of testing for the Document Object Model Events standard while maintaining an equivalent level of assurance. More than 36,000 tests – all possible combinations of equivalence class values –were reduced by approximately a factor of 20 with no reduction in error detection effectiveness.

概要 — 本報告書は、文書オブジェクトモデルイベント標準の試験において、同等の保証水準を維持しながら試験のコストを削減するために、組合せ試験手法を用いた事例を説明します。同値クラスの値のあらゆる組合せである 36,000 件を超える試験は、誤り検出の有効性を損なうことなく、約 20 分の 1 に削減されました。

Introduction

はじめに

The Document Object Model (DOM) [9] is a standardized method for representing and interacting with components of XML, HTML, and XHTML documents. DOM lets programs and scripts access and update the content, structure, and style of documents dynamically, making it easier to produce web applications in which pages are accessed non-sequentially. DOM is standardized by the World Wide Web Consortium (W3C).

文書オブジェクトモデル(Document Object Model: DOM)[9] は、XML、HTML、XHTML 文書の構成要素を表現し、それらとやり取りするための標準化された方法です。DOM を使うと、プログラムやスクリプトが文書の内容、構造、スタイルに動的にアクセスして更新できるため、ページが順不同にアクセスされる Web アプリケーションを作りやすくなります。DOM は World Wide Web Consortium(W3C)によって標準化されています。

Since its origination in 1996 as a convention for accessing and modifying parts of Javascript web pages (known now as DOM Level 0), DOM has evolved as a series of standards offering progressively greater capabilities. Level 1 introduced a model that allowed changing any part of the HTML document, and Level 2 added support for XML namespaces, load and save, cascading style sheets (CSS), traversing the document, and working with ranges of content. Level 3 brings additional features, including keyboard event handling.

DOM は、1996 年に Javascript の Web ページの一部にアクセスし、変更するための規約(現在は DOM Level 0 と呼ばれます)として生まれて以来、段階的により高い機能を提供する一連の標準として発展してきました。Level 1 では HTML 文書のどの部分でも変更できるモデルが導入され、Level 2 では XML 名前空間、ロードと保存、カスケーディングスタイルシート(CSS)、文書のトラバース、内容の範囲の扱いへの対応が加わりました。Level 3 では、キーボードイベントの処理などの機能がさらに加わります。

DOM Level 3 Events [9] is a W3C Working Draft being written by the Web Applications Working group. Implemented in browsers, it is a generic platform and language neutral event system that allows registration of event handlers, describes event flow through a tree structure, and provides basic contextual information for each event. This work builds on the previous Document Object Model Level 2 events specifications. There are two basic goals in the design of DOM Level 3 Events. The first goal is to design an event system that allows registration of event listeners and describes an event flow through a tree structure. The second goal is to provide a common subset of the current event system used on DOM Level 3 Events browsers.

DOM Level 3 Events [9] は、Web Applications Working group が作成している W3C Working Draft です。ブラウザに実装されるもので、イベントハンドラの登録を可能にし、ツリー構造を通じたイベントフローを記述し、各イベントの基本的な文脈情報を提供する、汎用でプラットフォームおよび言語に依存しないイベントシステムです。この作業は、これまでの Document Object Model Level 2 events 仕様に基づいています。DOM Level 3 Events の設計には 2 つの基本的な目標があります。1 つ目の目標は、イベントリスナーの登録を可能にし、ツリー構造を通じたイベントフローを記述するイベントシステムを設計することです。2 つ目の目標は、DOM Level 3 Events のブラウザで現在使われているイベントシステムの共通部分集合を提供することです。

Constructing Tests for DOM Events

DOM イベントの試験の構築

DOM browser implementations typically contain tens of thousands of source lines of code. To help ensure successful implementations of this complex standard, NIST developed the DOM Conformance Test Suites, which include tests for many DOM components. Early DOM tests were hand-coded in a test language, then processed to produce ECMAScript and Java. In the current version of the test suites, tests are specified in an XML grammar, allowing easy mapping from specification to a variety of language bindings. Because the grammar is generated automatically [7] from the DOM specs, tests can be constructed quickly and correctly. Output of the test generation process includes the following components, which implementers can use in testing their product for DOM interoperability:

DOM のブラウザ実装は、通常、数万行のソースコードを含みます。この複雑な標準の実装を確実に成功させるため、NIST は、多くの DOM 構成要素の試験を含む DOM Conformance Test Suites を開発しました。初期の DOM 試験は試験用言語で手作業でコーディングされ、その後、処理して ECMAScript と Java が生成されました。現在の版の試験スイートでは、試験は XML 文法で記述されており、仕様から各種の言語バインディングへ容易に対応付けることができます。この文法は DOM 仕様から自動的に生成される [7] ため、試験を迅速かつ正確に構築できます。試験生成の過程の出力には次の構成要素が含まれ、実装者は DOM の相互運用性について自分の製品を試験する際にこれらを使用できます。

•Tests in the XML representation language,

•XML 表現言語による試験

•XSLT stylesheets necessary to generate the Java and ECMA Script bindings,

•Java および ECMA Script のバインディングを生成するために必要な XSLT スタイルシート

•Generated executable code.

•生成された実行可能コード

Tests for 35 (out of 36) DOM Events were generated. The specification defines each event with an Interface Definition Language (IDL), which in turn defines a number of functions for each event. A typical function can have anywhere from one to fifteen parameters. The API for each function is defined as an XML infoset, which specifies the abstract data model of the XML document using a predefined set of tags. The XML infosets were programmatically generated through a Java application. Since the IDL definition could be accessed directly from the specs web site; the web address was given as input to the Java application. This way the application could read and traverse them extracting just the information of our interest. In this case the function names and their respective parameters, argument names, etc., which became part of the XML file that was used to feed a test generation tool to automatically create the DOM Level 3 tests.

35 個(36 個のうち)の DOM イベントについて試験が生成されました。仕様は各イベントをインタフェース定義言語(Interface Definition Language: IDL)で定義しており、IDL は各イベントについて複数の関数を定義します。典型的な関数は 1 個から 15 個のパラメータを持つことがあります。各関数の API は XML infoset として定義されており、XML infoset は、あらかじめ定められたタグの集合を用いて XML 文書の抽象データモデルを規定します。XML infoset は Java アプリケーションによってプログラムで生成されました。IDL 定義は仕様の Web サイトから直接アクセスできたので、その Web アドレスが Java アプリケーションへの入力として与えられました。これにより、アプリケーションは IDL 定義を読み込んで走査し、必要な情報だけを抽出できました。ここでは、関数名とそれぞれのパラメータ、引数名などがそれにあたり、これらは、DOM Level 3 の試験を自動的に作成する試験生成ツールに与える XML ファイルの一部となりました。

Conventional category partitioning was used to select representative values for non-Boolean parameters. The initial test set was exhaustive across the equivalence classes, producing 36,626 tests that exercised all possible combinations of equivalence class elements. Note that this is not fully exhaustive – all possible value combinations – because such a test suite is generally intractable with continuous range parameters. It is however exhaustive with respect to the equivalence class elements. Thus this test suite will be referred to as the exhaustive test suite in the remainder of this report. Two different implementations were tested. The DOM events and number of tests for each are shown in Table 1. This set of exhaustive tests detected a total of 72 failures. Automated tools made it possible to construct tests programatically, greatly reducing the effort required for testing. However, human intervention is required to run individual tests and evaluate test results, so the conformance testing team sought ways to reduce the number of tests required without sacrificing quality.

非 Boolean のパラメータの代表値を選ぶために、従来のカテゴリ分割が用いられました。最初の試験集合は同値クラス全体にわたって網羅的であり、同値クラスの要素のあらゆる組合せを実行する 36,626 件の試験が作られました。ただし、これは完全に網羅的というわけではないことに注意してください。値のあらゆる組合せを網羅する試験スイートは、連続した範囲を持つパラメータがあると、一般に実現不可能だからです。しかし、同値クラスの要素に関しては網羅的です。そのため、本報告書の以降では、この試験スイートを網羅的試験スイートと呼びます。2 つの異なる実装が試験されました。DOM イベントと、それぞれの試験数を表 1 に示します。この網羅的試験の集合は、合計 72 件の不具合を検出しました。自動化ツールにより、試験をプログラムで構築できるようになり、試験に要する労力が大幅に減りました。しかし、個々の試験を実行して試験結果を評価するには人手が必要であるため、適合性試験チームは、品質を犠牲にせずに必要な試験数を減らす方法を探りました。

Event NameParam.Tests
Abort312
Blur524
Click154352
Change312
dblClick154352
DOMActivate524
DOMAttrModified816
DOMCharacterDataModified864
DOMElementNameChanged68
DOMFocusIn524
DOMFocusOut524
DOMNodeInserted8128
DOMNodeInsertedIntoDocument8128
DOMNodeRemoved8128
DOMNodeRemovedFromDocument8128
DOMSubTreeModified864
Error312
Focus524
KeyDown117
KeyUp117
Load324
MouseDown154352
MouseMove154352
MouseOut154352
MouseOver154352
MouseUp154352
MouseWheel141024
Reset312
Resize548
Scroll548
Select312
Submit312
TextInput58
Unload324
Wheel154096
Total Tests36626
イベント名パラメータ数試験数
Abort312
Blur524
Click154352
Change312
dblClick154352
DOMActivate524
DOMAttrModified816
DOMCharacterDataModified864
DOMElementNameChanged68
DOMFocusIn524
DOMFocusOut524
DOMNodeInserted8128
DOMNodeInsertedIntoDocument8128
DOMNodeRemoved8128
DOMNodeRemovedFromDocument8128
DOMSubTreeModified864
Error312
Focus524
KeyDown117
KeyUp117
Load324
MouseDown154352
MouseMove154352
MouseOut154352
MouseOver154352
MouseUp154352
MouseWheel141024
Reset312
Resize548
Scroll548
Select312
Submit312
TextInput58
Unload324
Wheel154096
試験総数36626

Table 1. DOM Level 3 Events Tests – Exhaustive

表 1. DOM Level 3 Events の試験 — 網羅的

Combinatorial Testing Approach

組合せ試験のアプローチ

Because the DOM test suite had already been applied with exhaustive (across equivalence values) tests against a variety of implementations, it provided a valuable opportunity to evaluate combinatorial testing [2, 3, 5, 7] on real-world software. If results showed that a much smaller test suite could achieve the same level of fault detection, then testing could be done at much less cost in staff time and resources. An obvious critical question in using this approach is – what level of t-way interaction is necessary? Can all faults be detected with 2-way (pairwise) tests, or does the application require 3-way, 4-way or higher strength tests? This work helped to address these questions as well.

DOM 試験スイートは、さまざまな実装に対して、すでに(同値の値にわたって)網羅的な試験として適用されていたため、実世界のソフトウェアで組合せ試験 [2, 3, 5, 7] を評価する貴重な機会となりました。結果が、はるかに小さい試験スイートで同じ水準の欠陥検出を達成できることを示せば、人員の時間と資源のコストをずっと減らして試験を行えます。このアプローチを使ううえで明らかに重要な問いは、どの水準の t-way 相互作用が必要かということです。すべての欠陥を 2-way(ペアワイズ)試験で検出できるのか、それとも、アプリケーションには 3-way、4-way、あるいはそれ以上の強度の試験が必要なのか。本作業は、これらの問いにも答える助けとなりました。

To investigate the effectiveness of combinatorial testing, covering arrays of 2-way through 6-way tests were produced, using a tool [7] developed by NIST and the University of Texas Arlington. Using t-way combinations can significantly reduce the number of tests as compared with exhaustive. For example, the mousedown event (Figure 1) requires 4,352 tests if all combinations are to be realized. Combinatorial testing reduces the set to 86 tests for 4-way coverage.

組合せ試験の有効性を調べるため、NIST とテキサス大学アーリントン校が開発したツール [7] を用いて、2-way から 6-way までの試験の被覆配列が作られました。t-way の組合せを使うと、網羅的な試験と比べて試験数を大幅に減らせます。たとえば、mousedown イベント(図 1)は、すべての組合せを実現するには 4,352 件の試験が必要です。組合せ試験では、4-way の被覆で 86 件の試験に減ります。

Table 2 details the number of parameters and number of tests produced for each of the 35 DOM events, for t = 2 through 6. That is, the tests covered all 2-way through 6-way combinations of values. Note that for events with few parameters, the number of tests is the same for the original test suite (Table 1) and combinatorial for various levels of t. For example, 12 tests were produced for Abort in the original and also for combinatorial testing at t = 3 to 6. This is because producing all n-way combinations for n variables is simply all possible combinations of these n variables, and Abort has 3 variables. This situation is not unusual when testing configurations with a limited number of values for each parameter. For nine of the 35 events (two Click events, six Mouse events, and Wheel), all combinations are not covered even with 6-way tests. For these events, combinatorial testing provides a significant gain in efficiency.

表 2 に、35 個の DOM イベントそれぞれについて、t = 2 から 6 までの場合のパラメータ数と生成された試験数を詳しく示します。つまり、試験は値の 2-way から 6-way までのあらゆる組合せを被覆しました。パラメータが少ないイベントでは、元の試験スイート(表 1)の試験数と、さまざまな t の水準の組合せ試験の試験数は同じになることに注意してください。たとえば、Abort では、元の試験スイートでも、t = 3 から 6 の組合せ試験でも、12 件の試験が作られました。これは、n 個の変数についてあらゆる n-way の組合せを作ることは、単にそれら n 個の変数の可能なすべての組合せを作ることであり、Abort には 3 個の変数があるためです。各パラメータの値の数が限られた構成を試験する場合、この状況は珍しくありません。35 個のイベントのうち 9 個(Click イベント 2 個、Mouse イベント 6 個、Wheel)では、6-way の試験でもすべての組合せは被覆されません。これらのイベントでは、組合せ試験により効率が大きく向上します。

Test Results

試験結果

Table 2 shows the faults detected for each event. All conditions flagged by the exhaustive test suite were also detected by three of the combinatorial testing scenarios (4, 5 and 6 way testing), which indicates that the implementation faults were triggered by 4-way interactions or less. Pairwise testing would have been inadequate for the DOM implementations, because 2-way and 3-way tests detected only 37.5% of the faults. As can be seen in Table 2, the exhaustive (all possible combinations) tests of equivalence class elements and the 4-way to 6-way combinatorial tests were equally successful in fault detection, indicating that exhaustive testing added no benefit. These findings are consistent with earlier studies [1, 4, 8] that showed that software faults are triggered by interactions of a small number of variables, for applications in a variety of domains. DOM testing was somewhat unusual in that exhaustive testing of equivalence class elements was possible at all. For most software, too many possible input combinations exist to cover even a tiny fraction of the exhaustive set, so combinatorial methods may be of greater benefit for these.

表 2 に、各イベントで検出された欠陥を示します。網羅的試験スイートが検出したすべての条件は、3 つの組合せ試験シナリオ(4-way、5-way、6-way の試験)でも検出されました。これは、実装の欠陥が 4-way 以下の相互作用によって引き起こされたことを示しています。DOM の実装に対しては、ペアワイズ試験では不十分だったはずです。2-way と 3-way の試験では、欠陥の 37.5% しか検出されなかったためです。表 2 からわかるように、同値クラスの要素の網羅的な(あらゆる組合せの)試験と、4-way から 6-way の組合せ試験は、欠陥検出において同等に成功しており、網羅的試験には利点が加わらなかったことを示しています。これらの知見は、さまざまな分野のアプリケーションについて、ソフトウェアの欠陥が少数の変数の相互作用によって引き起こされることを示した、以前の研究 [1, 4, 8] と整合しています。DOM の試験は、そもそも同値クラスの要素の網羅的な試験が可能であった点で、やや異例でした。大半のソフトウェアでは、可能な入力の組合せが多すぎて、網羅的な集合のごく一部すら被覆できないため、組合せ手法はそうしたソフトウェアにより大きな利点をもたらす場合があります。

図表

mousedown イベントの XML インフォセットのコードです。<event name = "mousedown" interface = "MouseEvent"> で始まり、<targetNodes><value>Element</value></targetNodes> の後に <function name = "initMouseEvent" level = "2"> が続きます。その中に引数ごとの <eargument> 要素があり、それぞれ name・type・targetAttribute の属性と、1〜2 行の <eargValue value = …> を持ちます。typeArg(型 "DOMString"、targetAttribute "type"、値 "mousedown")、canBubbleArg と cancelableArg(型 "boolean"、値 "true" と "false")、viewArg(型 "views::AbstractView"、値 "window")、detailArg・screenXArg・screenYArg・clientXArg・clientYArg(型 "long"、targetAttribute は "detail"・"screenX"・"screenY"・"clientX"・"clientY"、値 "5" と "-5")、ctrlKeyArg・altKeyArg・shiftKeyArg・metaKeyArg(型 "boolean"、targetAttribute は "ctrlKey"・"altKey"・"shiftKey"・"metaKey"、値 "true" と "false")です。最後に「...」と、閉じタグ </function> と </event> があります。原本では canBubbleArg・cancelableArg・viewArg・shiftKeyArg の行の末尾が右端で切れています。

Figure 1. XML infosets generated from IDLs used as input to Test Accelerator.

図 1. Test Accelerator への入力として使われる、IDL から生成された XML infoset。

Event NameNum param2-way Tests3-way Tests4-way Tests5-way Tests6-way Tests
Abort3812121212
Blur51016242424
Click15184086188353
Change3812121212
dblClick15184086188353
DOMActivate51016242424
DOMAttrModified8816161616
DOMCharacterDataModified83262646464
DOMElementNameChanged688888
DOMFocusIn51016242424
DOMFocusOut51016242424
DOMNodeInserted864128128128128
DOMNodeInsertedIntoDocument864128128128128
DOMNodeRemoved864128128128128
DOMNodeRemovedFromDocument864128128128128
DOMSubTreeModified83264646464
Error3812121212
Focus51016242424
KeyDown1917171717
KeyUp1917171717
Load31624242424
MouseDown15184086188353
MouseMove15184086188353
MouseOut15184086188353
MouseOver15184086188353
MouseUp15184086188353
MouseWheel14164082170308
Reset3812121212
Resize52032484848
Scroll52032484848
Select3812121212
Submit3812121212
TextInput588888
Unload31612242424
Wheel15204492214406
Total Tests7021342181827424227
イベント名パラメータ数2-way 試験数3-way 試験数4-way 試験数5-way 試験数6-way 試験数
Abort3812121212
Blur51016242424
Click15184086188353
Change3812121212
dblClick15184086188353
DOMActivate51016242424
DOMAttrModified8816161616
DOMCharacterDataModified83262646464
DOMElementNameChanged688888
DOMFocusIn51016242424
DOMFocusOut51016242424
DOMNodeInserted864128128128128
DOMNodeInsertedIntoDocument864128128128128
DOMNodeRemoved864128128128128
DOMNodeRemovedFromDocument864128128128128
DOMSubTreeModified83264646464
Error3812121212
Focus51016242424
KeyDown1917171717
KeyUp1917171717
Load31624242424
MouseDown15184086188353
MouseMove15184086188353
MouseOut15184086188353
MouseOver15184086188353
MouseUp15184086188353
MouseWheel14164082170308
Reset3812121212
Resize52032484848
Scroll52032484848
Select3812121212
Submit3812121212
TextInput588888
Unload31612242424
Wheel15204492214406
試験総数7021342181827424227

Table 2. DOM 3 Level Tests – Combinatorial

表 2. DOM Level 3 の試験 — 組合せ

tTests% of OriginalTest Results
PassFailNot Run
27021.92%20227473
313423.67%78627529
418184.96%437721309
527427.49%908721762
6422711.54%1803722352
t試験数元の試験数に対する割合試験結果
合格不合格未実行
27021.92%20227473
313423.67%78627529
418184.96%437721309
527427.49%908721762
6422711.54%1803722352

Table 3. Comparison of t-way with exhaustive test set size.

表 3. t-way の試験集合の大きさと網羅的な試験集合の大きさの比較。

The original test suite contained a total of 36,626 tests (Table 1) for all combinations of events, but after applying combinatorial testing, the set of tests is dramatically reduced depending on the t-way interactions algorithm, as shown in Table 3. It is important to note that combinatorial testing is constrained by some of the same limitations as other test methodologies. In particular, for most testing some method of abstracting parameter values, such as equivalence classes, must be used. The number of tests generated in combinatorial covering arrays is proportional to \(v^{t} \log n\), for t-way interactions where each of n parameters has v values. In cases where most parameters have a small number of discrete values, this is less of a limitation, but it was required for parameters such as screen X and Y values, and must be considered for most software testing.

元の試験スイートには、イベントのすべての組合せについて合計 36,626 件の試験が含まれていました(表 1)が、組合せ試験を適用すると、表 3 に示すように、試験の集合は t-way 相互作用のアルゴリズムに応じて劇的に減ります。組合せ試験は、ほかの試験方法論と同じ制約のいくつかを受けることに注意することが重要です。特に、ほとんどの試験では、同値クラスのようなパラメータ値を抽象化する何らかの方法を使わなければなりません。組合せ被覆配列で生成される試験数は、n 個のパラメータがそれぞれ v 個の値を持つ t-way 相互作用では \(v^{t} \log n\) に比例します。ほとんどのパラメータが少数の離散値しか持たない場合は、この制約はあまり問題になりませんが、画面の X 値や Y 値のようなパラメータでは必要であり、ほとんどのソフトウェア試験で考慮しなければなりません。

Table 2 also shows results for 2-way through 6-way testing. Notice that although the number of tests that successfully execute varies from t-way combination to t-way combination, the number of failures remains a constant at t = 2 and 3, and at t = 4 to 6. The last column shows the tests that did not execute to completion, in almost all cases due to non-support of the feature under test.

表 2 は、2-way から 6-way までの試験の結果も示しています。正常に実行された試験の数は t-way の組合せごとに異なりますが、失敗の数は t = 2 と 3 では一定で、t = 4 から 6 でも一定であることに注目してください。最後の列は、最後まで実行されなかった試験を示しており、ほぼすべての場合、試験対象の機能に対応していないことが原因です。

DOM results were consistent with previous findings that testing a small number of interactions (in this case 4-way) was sufficient to detect all errors. Comparing results of the DOM testing with previous data [1, 4] on t-way interaction failures (Figure 2), we can see that some DOM failures were more difficult to detect, in the sense that a smaller percentage of the total were found by 2-way and 3-way tests than for the other application domains. The unusual shape of the curve for DOM tests may result from the large number of parameters for which exhaustive coverage was reached (so that the number of tests remained constant after a certain point). There are thus two sets of events: a large set with few possible values which could be covered exhaustively with 2-way or 3-way tests, and a smaller set with a larger input space (from 1024 to 4352). In particular, nine events (click, dblClick, mouse events, and wheel) all have the same input space size, with number of tests increasing at the same rate for each, while for the rest, exhaustive coverage is reached at either t=2 or t=3. The ability to compare results of previously-conducted exhaustive testing with combinatorial testing provides an added measure of confidence in the applicability of these methods to this type of interoperability testing.

DOM の結果は、少数の相互作用(この場合は 4-way)を試験すればすべての誤りを検出するのに十分であるという、これまでの知見と整合していました。DOM の試験の結果を、t-way 相互作用の失敗に関するこれまでのデータ [1, 4](図 2)と比べると、一部の DOM の失敗は、ほかのアプリケーション分野より、全体のうち 2-way と 3-way の試験で見つかった割合が小さいという意味で、検出が難しかったことがわかります。DOM の試験の曲線の形が通常と異なるのは、網羅的な被覆に達したパラメータが多数あった(そのため、ある時点を過ぎると試験数が一定のままだった)ことが原因かもしれません。そのため、イベントには 2 つの集合があります。取りうる値が少なく、2-way または 3-way の試験で網羅的に被覆できる大きな集合と、入力空間がより大きい(1024 から 4352)小さな集合です。特に、9 個のイベント(click、dblClick、mouse イベント、wheel)はすべて入力空間の大きさが同じで、試験数も同じ割合で増加しますが、残りのイベントでは、t=2 または t=3 で網羅的な被覆に達します。以前に実施された網羅的試験の結果と組合せ試験の結果を比較できたことで、この種の相互運用性試験にこれらの手法を適用できるという確信が一段と高まりました。

図表

折れ線グラフです。縦軸は「Cumulative percent」(累積割合)で 0〜100、横軸は「Interaction strength」(相互作用の強さ)で 1〜6 です。凡例には Med. Dev.(医療機器)、Browser(ブラウザー)、Server(サーバー)、NASA、NW Sec(ネットワークセキュリティ)、DOM の 6 系列があります。目盛からの読み取り(概数)では、Med. Dev. は 1 で約 66、2 で約 97、3 で約 99、4 以降 100、NASA は 1 で約 68、2 で約 93、3 で約 98、4 以降 100、Browser は 1 で約 29、2 で約 76、3 で約 95、4 で約 97、6 で 100、Server は 1 で約 42、2 で約 70、3 で約 89、4 と 5 で約 96、6 で 100、NW Sec は 1 で約 17、2 で約 62、3 で約 87、4 で約 98、5 以降 100、DOM は 2 と 3 で 38、4〜6 で 100 です。

FIGURE 2. DOM COMPARED WITH OTHER APPLICATIONS

図 2. DOM とほかのアプリケーションの比較

Conclusions

結論

The DOM Events testing suggests that combinatorial testing can significantly reduce the cost and time required for conformance testing for standards with characteristics similar to DOM. What is the appropriate interaction strength to use in this type of testing? Intuitively, it seems that if no additional faults are detected by t-way tests, then it may be reasonable to conduct additional testing only for t+1 interactions, but no greater if no additional faults are found at t+1. In empirical studies of software failures, the number of faults detected at t > 2 decreased monotonically with t, and the DOM testing results are consistent with this earlier finding. Following this strategy for the DOM testing would result in running 2-way tests through 5-way, then stopping because no additional faults were detected beyond the 4-way testing. Alternatively, given the apparent insufficient fault detection of pairwise testing (see Figure 2), testers may prefer to standardize on a 4-way or higher level of interaction coverage. This option may be particularly attractive for an organization that produces a series of similar products and has enough experience to identify the most cost-effective level of testing. Even the relatively strong 4-way testing in this example was only 5% of the original test set size. Results in this study have been sufficiently promising for combinatorial methods to be applied in testing other interoperability standards.

DOM Events の試験は、組合せ試験により、DOM と似た特性を持つ標準の適合性試験に必要なコストと時間を大幅に減らせることを示唆しています。この種の試験で用いるべき相互作用の強度は、どの程度が適切でしょうか。直観的には、t-way の試験でそれ以上の欠陥が検出されなければ、t+1 の相互作用についてだけ追加の試験を行うのが妥当であり、t+1 でも欠陥が見つからなければそれ以上は行わなくてよいと考えられます。ソフトウェアの失敗に関する実証研究では、t > 2 で検出される欠陥の数は t とともに単調に減少しており、DOM の試験結果はこの以前の知見と整合しています。DOM の試験にこの戦略を適用すると、2-way から 5-way の試験を実行したところで、4-way の試験を超えて追加の欠陥が検出されなかったため停止することになります。あるいは、ペアワイズ試験では欠陥検出が明らかに不十分であること(図 2 参照)を考えると、試験者は、4-way 以上の水準の相互作用の被覆に標準化することを好むかもしれません。この選択肢は、類似の製品群を作っていて、最も費用対効果の高い試験の水準を特定するのに十分な経験を持つ組織にとって、特に魅力的でしょう。この例の比較的強い 4-way の試験でさえ、元の試験集合の大きさのわずか 5% でした。本研究の結果は、組合せ手法をほかの相互運用性標準の試験に適用するのに十分な有望さを示しています。

References

参考文献

1.K.Z. Bell, Optimizing Effectiveness and Efficiency of Software Testing: a Hybrid Approach, PhD Dissertation, North Carolina State University, 2006.

1.K.Z. Bell, Optimizing Effectiveness and Efficiency of Software Testing: a Hybrid Approach, PhD Dissertation, North Carolina State University, 2006.

2.Bryce, R. C.J. Colbourn, M.B. Cohen. A Framework of Greedy Methods for Constructing Interaction Tests. The 27th International Conference on Software Engineering (ICSE), St. Louis, Missouri, pages 146-155. (May 2005).

2.Bryce, R. C.J. Colbourn, M.B. Cohen. A Framework of Greedy Methods for Constructing Interaction Tests. The 27th International Conference on Software Engineering (ICSE), St. Louis, Missouri, pages 146-155. (May 2005).

3.Grindal, Mats, Offutt, Jeff, and Andler, Sten F. “Combination Testing Strategies: A Survey,” Journal of Software Testing, Verification and Reliability vol. 15, no. 3, pp. 167-199, 2005.

3.Grindal, Mats, Offutt, Jeff, and Andler, Sten F. “Combination Testing Strategies: A Survey,” Journal of Software Testing, Verification and Reliability vol. 15, no. 3, pp. 167-199, 2005.

4.Kuhn, D. R., D. Wallace, and A. Gallo, “Software Fault Interactions and Implications for Software Testing,” IEEE Transactions on Software Engineering, 30(6):418-421, 2004.

4.Kuhn, D. R., D. Wallace, and A. Gallo, “Software Fault Interactions and Implications for Software Testing,” IEEE Transactions on Software Engineering, 30(6):418-421, 2004.

5.Lei, Y. K.C. Tai. In-parameter order: a Test Generation Strategy for Pairwise Testing. Proceedings of the Third IEEE High Assurance Systems Engineering Symposium, pp. 254-261, IEEE, Nov. 1998.

5.Lei, Y. K.C. Tai. In-parameter order: a Test Generation Strategy for Pairwise Testing. Proceedings of the Third IEEE High Assurance Systems Engineering Symposium, pp. 254-261, IEEE, Nov. 1998.

6.National Institute of Standards and Technology. Test Accelerator. . http://www.itl.nist.gov/div897/docs/testacc.html

6.National Institute of Standards and Technology. Test Accelerator. . http://www.itl.nist.gov/div897/docs/testacc.html

7.National Institute of Standards and Technology. Automated Combinatorial Testing for Software. http://csrc.nist.gov/acts

7.National Institute of Standards and Technology. Automated Combinatorial Testing for Software. http://csrc.nist.gov/acts

8.Wallace, D.R. D.R. Kuhn. “Failure Modes in Medical Device Software: an Analysis of 15 Years of Recall Data”, International Journal of Reliability, Quality, and Safety Engineering, Vol. 8, No. 4, 2001.

8.Wallace, D.R. D.R. Kuhn. “Failure Modes in Medical Device Software: an Analysis of 15 Years of Recall Data”, International Journal of Reliability, Quality, and Safety Engineering, Vol. 8, No. 4, 2001.

9.World Wide Web Consoritum, DOM Level 3 Events Specification, 8 Sept 2009. http://www.w3.org/TR/DOM-Level-3-Events/

9.World Wide Web Consortium, DOM Level 3 Events Specification, 8 Sept 2009. http://www.w3.org/TR/DOM-Level-3-Events/

Acknowledgments: We are very grateful to Vadim Okun for a careful review and for suggesting some possible explanations for the fault detection rate at various t levels in the DOM testing.

謝辞: DOM の試験におけるさまざまな t の水準での欠陥検出率について、丁寧なレビューと、考えられる説明のいくつかをご提案くださった Vadim Okun 氏に深く感謝します。

Disclaimer: We identify certain software products in this document, but such identification does not imply recommendation by the US National Institute for Standards and Technology, nor does it imply that the products identified are necessarily the best available for the purpose.

免責事項: 本書では特定のソフトウェア製品を明記していますが、そのように明記することは、米国国立標準技術研究所による推奨を意味するものではなく、明記された製品が当該目的に利用可能な最良のものであると必ずしも意味するものでもありません。