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 
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 

November, 2010

U.S. Department of Commerce 

Gary Locke, Secretary 

National Institute of Standards and Technology 

Patrick D. Gallagher, Director
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. 

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). 

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 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. 

Constructing Tests for DOM Events 

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: 

• Tests in the XML representation language, 

• XSLT stylesheets necessary to generate the Java and 

ECMA Script bindings, 

• 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. 

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. 
Event Name Param. Tests 

Abort 3 12 

Blur 5 24 

Click 15 4352 

Change 3 12 

dblClick 15 4352 

DOMActivate 5 24 

DOMAttrModified 8 16 

DOMCharacterDataModified 8 64 

DOMElementNameChanged 6 8 

DOMFocusIn 5 24 

DOMFocusOut 5 24 

DOMNodeInserted 8 128 

DOMNodeInsertedIntoDocument 8 128 

DOMNodeRemoved 8 128 

DOMNodeRemovedFromDocument 8 128 

DOMSubTreeModified 8 64 

Error 3 12 

Focus 5 24 

KeyDown 1 17 

KeyUp 1 17 

Load 3 24 

MouseDown 15 4352 

MouseMove 15 4352 

MouseOut 15 4352 

MouseOver 15 4352 

MouseUp 15 4352 

MouseWheel 14 1024 

Reset 3 12 

Resize 5 48 

Scroll 5 48 

Select 3 12 

Submit 3 12 

TextInput 5 8 

Unload 3 24 

Wheel 15 4096 

Total Tests 36626 

Table 1. DOM Level 3 Events Tests – Exhaustive 

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. 

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. 

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. 

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. 
Figure 1. XML infosets generated from IDLs used as input to Test Accelerator. 
Event Name Num 

param 

2-way 

Tests 

3-way 

Tests 

4-way 

Tests 

5-way 

Tests 

6-way 

Tests 

Abort 3 8 12 12 12 12 

Blur 5 10 16 24 24 24 

Click 15 18 40 86 188 353 

Change 3 8 12 12 12 12 

dblClick 15 18 40 86 188 353 

DOMActivate 5 10 16 24 24 24 

DOMAttrModified 8 8 16 16 16 16 

DOMCharacterDataModified 8 32 62 64 64 64 

DOMElementNameChanged 6 8 8 8 8 8 

DOMFocusIn 5 10 16 24 24 24 

DOMFocusOut 5 10 16 24 24 24 

DOMNodeInserted 8 64 128 128 128 128 

DOMNodeInsertedIntoDocument 8 64 128 128 128 128 

DOMNodeRemoved 8 64 128 128 128 128 

DOMNodeRemovedFromDocument 8 64 128 128 128 128 

DOMSubTreeModified 8 32 64 64 64 64 

Error 3 8 12 12 12 12 

Focus 5 10 16 24 24 24 

KeyDown 1 9 17 17 17 17 

KeyUp 1 9 17 17 17 17 

Load 3 16 24 24 24 24 

MouseDown 15 18 40 86 188 353 

MouseMove 15 18 40 86 188 353 

MouseOut 15 18 40 86 188 353 

MouseOver 15 18 40 86 188 353 

MouseUp 15 18 40 86 188 353 

MouseWheel 14 16 40 82 170 308 

Reset 3 8 12 12 12 12 

Resize 5 20 32 48 48 48 

Scroll 5 20 32 48 48 48 

Select 3 8 12 12 12 12 

Submit 3 8 12 12 12 12 

TextInput 5 8 8 8 8 8 

Unload 3 16 12 24 24 24 

Wheel 15 20 44 92 214 406 

Total Tests 702 1342 1818 2742 4227 

Table 2. DOM 3 Level Tests – Combinatorial 
Table 3. Comparison of t-way with exhaustive test set size. 

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. 

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. 

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. 

FIGURE 2. DOM COMPARED WITH OTHER APPLICATIONS

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. 

Test Results t Tests % of 

Original Pass Fail Not Run 

2 702 1.92% 202 27 473 

3 1342 3.67% 786 27 529 

4 1818 4.96% 437 72 1309 

5 2742 7.49% 908 72 1762 

6 4227 11.54% 1803 72 2352 
References 

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). 

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. 

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 

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. 

9. World Wide Web Consoritum, DOM Level 3 Events 

Specification, 8 Sept 2009. http://www.w3.org/TR/DOMLevel-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. 

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. 
This page was intentionally left blank. 

 1