Return to Video

Alternate Histories - Software Testing

  • 0:00 - 0:03
    Alternate history is a genre of fiction where we explore what would have happened to the world
  • 0:03 - 0:05
    had some historical event turned out differently.
  • 0:05 - 0:07
    For example, we might have an alternate history now exploring
  • 0:07 - 0:09
    what would have happened if the Allies hadn't won World War II.
  • 0:09 - 0:12
    What we're going to do is look at a few alternate history examples where we're going to try
  • 0:12 - 0:16
    to explore the question, "What would've happened if certain groups of people in the past had used
  • 0:16 - 0:19
    random testing in addition to whatever other kinds of testing they were doing?"
  • 0:19 - 0:23
    And we're going to sort of specifically focus on the question, "Would random testing have been likely
  • 0:23 - 0:26
    to alter the outcome of some famous software bugs but would have not made much difference?
  • 0:26 - 0:28
    Would it have not been a very useful technique?"
  • 0:28 - 0:32
    And so the first case study we're going to look at is the FDIV bug in Intel Pentium chips.
  • 0:32 - 0:36
    And so in 1994, it came to the world's attention that the FDIV instruction supported by
  • 0:36 - 0:40
    Intel's Pentium processor was flawed and so FDIV is an instruction that you would use
  • 0:40 - 0:42
    to perform floating point division.
  • 0:42 - 0:47
    If we're writing an assembly language for a Pentium, we would issue the FDIV instruction
  • 0:47 - 0:52
    with two operands and what do we do is compute the quotient of a divided by b.
  • 0:52 - 0:54
    And so what happened is there's a bug in FDIV.
  • 0:54 - 0:57
    And what had happened was the implementation of FDIV, that is to say
  • 0:57 - 1:01
    the hardware implementation of this machine instruction was intended to be very fast.
  • 1:01 - 1:03
    The Pentium was at that time a very high performance processor.
  • 1:03 - 1:08
    And the way FDIV was fast, at least in part, was because it did part of its work using table lookups.
  • 1:08 - 1:11
    So there was this table of values stored in the Pentium's hardware.
  • 1:11 - 1:13
    What had happened was somewhere on the way to fabrication
  • 1:13 - 1:16
    some of the values had not been loading correctly into the table.
  • 1:16 - 1:20
    So part of the lookup table, I believe it was 5 entries, contained the wrong results.
  • 1:20 - 1:24
    And for some values of A and B passed to the FDIV instruction, looking up these wrong results
  • 1:24 - 1:27
    in the lookup table would cause it to do the wrong thing.
  • 1:27 - 1:31
    This wasn't an extremely major error in the sense that it would return a million instead of 0
  • 1:31 - 1:35
    but rather it was off in sort of some number of places after the decimal point.
  • 1:35 - 1:39
    The reason that the flaws in FDIV went undetected for sometime was that only about
  • 1:39 - 1:43
    1 in 9 Billion randomly selected inputs would actually trigger the bug.
  • 1:43 - 1:48
    And so now the question we need to ask ourselves is given this relatively low observed failure rate
  • 1:48 - 1:53
    on random inputs, would random testing have been a good way to find the Pentium FDIV bug?
  • 1:53 - 1:55
    And the answer is almost certainly yes.
  • 1:55 - 1:58
    So what we're going to do now is try to figure out about how long it would've taken Intel
  • 1:58 - 2:00
    to find this bug using random testing.
  • 2:00 - 2:03
    And so the first thing we're going to need to do is make an assumption about
  • 2:03 - 2:05
    how many tests per second they can run.
  • 2:05 - 2:09
    And so it's not as if in 1994 they have modern multigigahertz hardware available
  • 2:09 - 2:12
    but rather these Pentiums ran at around 60 MHz.
  • 2:12 - 2:16
    And so what we're going to say for the sake of argument is that it took 10 Ãľs
  • 2:16 - 2:19
    to perform an FDIV and verify its result.
  • 2:19 - 2:24
    So in other words, at 60 MHz, I'm assuming that it would take about 600 cycles
  • 2:24 - 2:26
    to check a particular input for FDIV.
  • 2:26 - 2:31
    Now let's try to work out the math.
Title:
Alternate Histories - Software Testing
Description:

more » « less
Video Language:
English
Team:
Udacity
Project:
CS258: Software Testing
Duration:
02:30
Udacity Robot edited English subtitles for 05-22 Alternate Histories
Udacity Robot edited English subtitles for 05-22 Alternate Histories
Gundega added a translation

English subtitles

Revisions Compare revisions