# Presentation: 381529

## My Life With Bugs, or, Why I Believe in Combinatorial Testing

- Paul E. Black
- National Institute of Standards and Technology
- _http://www.nist.gov/_
- paul.black@nist.gov

## Outline

**SAMATE, my current program, briefly**
**Some tough and bizarre bugs**
**How many conditions do faults need?**
**Combinatorial Testing**
**What is it?**
**Why does it work?**
**State of the Art**

- Paul E. Black

## What is NIST?

**U.S. National Institute of Standards and Technology**
**A non-regulatory agency in Dept. of Commerce**
**3,000 employees + adjuncts**
**Gaithersburg, Maryland and Boulder, Colorado**
**Primarily research, not funding**
**Over 100 years in standards and measurements: from dental ceramics to text retrieval, from quantum computers to fire codes, from body armor to DNA forensics, from biometrics to whale blubber**

- Paul E. Black

## The NIST SAMATE Project

***Software Assurance Metrics And Tool Evaluation***** (SAMATE) project is sponsored in part by DHS**
**Began 2004 to help improve software assurance**
**Current areas of concentration**
**Source code security analyzers**
**Studies of tool effectiveness**
**Web application scanners**
***Binary analyzers***
***Software labels***
**Web site     http://samate.nist.gov/**

- Paul E. Black

**Notes:**
Interagency agreement betwieen NIST and DHS

## Source Code Security Analyzers

**C,**
**C++, **
**...**
**binary**

**Weaknesses**
**&**
**Vulnerabilities**

**Static **
**Analyzer**

- Examine source code or binary for adherence to guidelines, weaknesses, etc.
- To assess tools, we wrote and collected thousands of test cases in a SAMATE Reference Dataset (SRD)

**SRD**
**Test Cases**

- Paul E. Black

## SRD: an Open Resource

- Paul E. Black

## Slide 7

- Paul E. Black

## Slide 8

- Paul E. Black

**Notes:**
Unfiltered, or tainted, input allows arbitrary files to be read and written. 

## Outline

**SAMATE, my current program, briefly**
**Some tough and bizarre bugs**
**How many conditions do faults need?**
**Combinatorial Testing**
**What is it?**
**Why does it work?**
**State of the Art**

- Paul E. Black

## Wrong Date

**IBM System 3/10 - punched card input**
**Daily boot-up set system date with a card**
**In 1979 the daily run didn’t print any up-coming payment notices ...**
**Tiny program printed sys **
**     ****data as 1978!**
**Checked date card, but it**
**     ****said 1979!**

- Paul E. Black

## Bad Character

**Application: IC design parser**
**Input: computer chip design, 2D, WYSIWYG**
**Output: network list, plain text**
**Failure: one strange character**
- (V-WIRE_32 (A_[0..31] B_[0..31]) (Y_[0..31])
-      ((G_0 (Y_0) T-WIRE (A_0 B_0)) (G_1 (Y_1) T-WIRE (A_1 B_1))
-       (G_8 (Y_8) T-GIRE (A_8 B_8)) (G_9 (Y_9) T-WIRE (A_9 B_9))
-       (G_10 (Y_10) T-WIRE (A_10 B_10)) (G_11 (Y_11) T-WIRE (A_11 B_11))
**Could not reproduce on my machine; *****could***** on engineer’s**
**Different places or chars on other runs: memory overwrite?**
**No hint of code overwrite (common in C)**
**Made a table of *****where***** the failure was in output file: all had same low-order bits in hex**
**Conclusion: flaky bit in output hardware**

- Paul E. Black

## Lisp Error

**Circuit simulator driven by a built-in Lisp, a language with lists & garbage collection**
**Designer had a bizarre error: some computations got wrong answers!**
**I could reproduce that error, but it came and went and changed in similar cases**
**In an attempt to track it down, I**
**Wrote a “shadow” floating point math module**
**Garbage collected after every operation**
**Changed the heap size**

- Paul E. Black

## Lisp Error Solution

**Problem: wrong free list set up**

- Paul E. Black

## Testing is like a seatbelt ...

- Paul E. Black

## Outline

**SAMATE, my current program, briefly**
**Some tough and bizarre bugs**
**How many conditions do faults need?**
**Combinatorial Testing**
**What is it?**
**Why does it work?**
**State of the Art**

- Paul E. Black

## Software Failure Analysis

**NIST studied software failures in many fields including 15 years of FDA medical device recalls**
**Would pairwise testing find all errors?  **
**If not, then how many interactions would we need to test to find all errors?**
**e.g.,  failure occurs if**** pressure < 10                       (1-way interaction)**** pressure < 10 & volume > 300****                                               (2-way interaction)**

- Paul E. Black

## What interactions do we need to test to find ALL faults?

**Maximum interactions for fault triggering****for these applications was 6**
**Wallace, Kuhn  2001 – medical devices ****98% of flaws were pairwise interactions, ****no fault required > 4-way interactions to trigger**
**Kuhn, Reilly  2002 – web server, browser; ****no fault required > 6-way interactions to trigger**
**Kuhn, Wallace, Gallo  2004 – large NASA distributed database; ****no fault required > 4 interactions to trigger**
**Reasonable evidence that maximum interaction strength for fault triggering is relatively small**

- Paul E. Black

**Notes:**
Devil’s advocate: or, really complex faults with lots of interactions are never reported: they can’t be reproduced, “it’s a random glitch”, etc.

## Maximum interactions for fault triggering for 4 domains

- % triggered

- Interactions

- Paul E. Black

## Outline

**SAMATE, my current program, briefly**
**Some tough and bizarre bugs**
**How many conditions do faults need?**
**Combinatorial Testing**
**What is it?**
**Why does it work?**
**State of the Art**

- Paul E. Black

## A simple example

- Paul E. Black

## How Many Tests Would It Take?

**There are 10 effects, each can be on or off**
**All combinations is 2****10**** = 1,024 tests**
**too many to visually check ...**
**Let’s look at all 3-way interactions ...**

- Paul E. Black

**Notes:**
After all, testing all 3-way interactions catches between 90% and 98% of all faults.

## Now How Many Would It Take?

**There are       = 120 3-way interactions.**
**Naively 120 x 2****3**** = 960 tests.**
**Since we can pack 3 triples into each test, we need no more than 320 tests.**
**Each test exercises many triples:**
**                   ****0 0 0 1 1 1 0 1 0 1**

**We oughta be able to pack a lot in one test, so what’s the smallest number we need?**

- Paul E. Black

**Notes:**
Anyone care to hazard a guess as to the smallest number of tests we need?

## All Triples Take Only 13 Tests

- Paul E. Black

## A Real-World Example

- Plan:  flt, flt+hotel, flt+hotel+car
- From: CONUS, HI, AK, Europe, Asia ...
- To: CONUS, HI, AK, Europe, Asia ...
- Compare:  yes, no
- Date-type: exact, 1to3, flex
- Depart: today, tomorrow, 1yr, Sun, Mon ...
- Return: today, tomorrow, 1yr, Sun, Mon ...
- Adults: 1, 2, 3, 4, 5, 6
- Minors: 0, 1, 2, 3, 4, 5
- Seniors: 0, 1, 2, 3, 4, 5

-  No silver bullet because:      Many values per variable      Need to abstract values   But we can still increase information per test

- Paul E. Black

## Does It Really Work?

**Traffic Collision Avoidance               System (TCAS) module**
**Used in previous testing research**
**41 versions seeded with errors**
**12 variables: 7 boolean, two 3-value, one 4-value, two 10-value**
**All flaws found with 5-way coverage**

- Paul E. Black

## Outline

**SAMATE, my current program, briefly**
**Some tough and bizarre bugs**
**How many conditions do faults need?**
**Combinatorial Testing**
**What is it?**
**Why does it work?**
**State of the Art**

- Paul E. Black

## Why? A Geometric Intuition

- Paul E. Black

**Notes:**
Emboss
Engrave
Hidden
Superscript
Subscript

## Naïve Test Approach

**Test all off, all on, each one on**
**7 tests total**

- Paul E. Black

**Notes:**
Suppose we don’t want to test every combination. What would be a good set of tests? Let’s see: a simple approach is to test all off, test all on, then test each one on (and the others off). That’s a total of 7 tests. But how good is that set of tests?
Let’s plot our tests.
(CLICK) All off is in the lower left corner.
(CLICK) All on is in the upper, right corner.
The other five tests, one factor on at a time are in the other corners (CLICK), close to the test with everything off.
Hmmm, those don’t seem to cover the behavior space very well. Can we do better?

## How Combinatorial Tests Look

- Paul E. Black

## Outline

**SAMATE, my current program, briefly**
**Some tough and bizarre bugs**
**How many conditions do faults need?**
**Combinatorial Testing**
**What is it?**
**Why does it work?**
**State of the Art**

- Paul E. Black

## Combinatorial Testing Requires a Lot of Tests

**For *****n***** variables with *****v***** values each, the number of *****k*****-way combinations is**
**The test set is a covering array**
**Finding a covering array is NP hard**
**Assume 30 parameters                           with 5 values each. All                                4-way combinations are                      covered by 3,800 tests**

- Paul E. Black

**Notes:**
Combinatorial testing, like any thorough testing criterion, requires a lot of tests.

## Lots of Tests (cont.)

| k | # test cases |
| --- | --- |
| 2-way | 156 |
| 3-way | 461 |
| 4-way | 1,450 |
| 5-way | 4,309 |
| 6-way | 11,094 |

- Paul E. Black

## Combinatorial Testing Research

**Huge increases in performance & scalability **
**Proof-of-concept demonstrations**
**Applied modeling and simulation**

- Paul E. Black

## Summary

**Combinatorial testing makes sense where**
**More than ~8 variables and less than 300 - 400**
**Logical or numeric interaction of variables**
**New algorithms make large-scale combinatorial testing possible**
**Beta release of open source tools in December**
**New public catalog of covering arrays**
**http://csrc.nist.gov/acts**

- Paul E. Black

**Notes:**
If there are few variables, exhaustive testing makes sense.  If there are many variables, it takes far too long (many days) to generate covering arrays

## Seeking Participants

**Contribute test cases to **_**SRD**_
**Comment on specifications and tests**
**Join SAMATE email list with ideas on**
**Static binary analyzers**
**Software labels**
**Use Combinatorial Test Generation Tools**

**Paul E. Black**
**SAMATE Project Leader**
**paul.black@nist.gov**

**Rick Kuhn**
**Combinatorial Testing**
**kuhn@nist.gov**

- Paul E. Black

## Society has 3 options:

**Learn how to make software that **_***works***_
**Limit size or authority of software**
**Accept failing software**

- Paul E. Black

**Notes:**
“Size” means size, complexity, style, language features, etc.: anything which keeps us from assuring the quality of the software.

Subject: [sci.space.tech] Re: Delta vs TitanOn Sat, 08 Jan 2005 07:14:45 +0000, Henry Spencer wrote:> The software for the MOST astronomy satellite doesn't get anywhere near such elaborate attention.> But then, the software basically can't do anything to break MOST.  And no,> that's not an accident -- we worked hard to make sure of that!> > For example, on a typical satellite, loss of attitude control is a> terrible emergency, because it means the solar arrays are no longer> pointed at the Sun and you've only got (at most) a few hours until the> batteries are drained.  Spacecraft have died that way. 
> > MOST was in a random tumble for a month after launch, while some other> problems were solved.  Nobody worried.  The spacecraft has solar arrays on> all six sides -- not enough for full power, but enough for crucial> functions (main computer and radio receivers).  And when the batteries> approach empty, the power system hardware switches off everything except> crucial functions.  (It tries to switch off everything, but there are no> power switches on the computer and the receivers.)> > The result is software that's *far* cheaper to develop.  Also a more> robust spacecraft:  even the inordinately expensive classical process
> can *and does* make mistakes, which can kill spacecraft.  MOST is
> essentially unkillable.  (Credit where due:  we got this approach from
> the Amsat people, who do the amateur-radio satellites.)> > You couldn't quite do that for things with time-critical functions, like> aircraft and launchers.  Even there, though, it would be interesting to> see how far you *could* get in designing the total system to survive> imperfect software, rather than assuming the software must be perfect and> will be made so regardless of cost.