Stories
Slash Boxes
Comments
NOTE: use Perl; is on undef hiatus. You can read content, but you can't post it. More info will be forthcoming forthcomingly.

All the Perl that's Practical to Extract and Report

use Perl Log In

Log In

[ Create a new account ]

Ovid (2709)

Ovid
  (email not shown publicly)
http://publius-ovidius.livejournal.com/
AOL IM: ovidperl (Add Buddy, Send Message)

Stuff with the Perl Foundation. A couple of patches in the Perl core. A few CPAN modules. That about sums it up.

Journal of Ovid (2709)

Monday January 05, 2009
05:28 AM

Code Coverage and the Zune Bug

[ #38221 ]

Many of you have probably heard of the Zune bug and some of you may have seen the source code of the bug. Specifically, the bug resides in this:

BOOL ConvertDays(UINT32 days, SYSTEMTIME* lpTime)
{
    int dayofweek, month, year;
    UINT8 *month_tab;

    //Calculate current day of the week
    dayofweek = GetDayOfWeek(days);

    year = ORIGINYEAR;

    while (days > 365)
    {
        if (IsLeapYear(year))
        {
            if (days > 366)
            {
                days -= 366;
                year += 1;
            }
        }
        else
        {
            days -= 365;
            year += 1;
        }
    }

    // Determine whether it is a leap year
    month_tab = (UINT8 *)((IsLeapYear(year))? monthtable_leap : monthtable);

    for (month=0; month<12; month++)
    {
        if (days <= month_tab[month])
            break;
        days -= month_tab[month];
    }

    month += 1;

    lpTime->wDay = days;
    lpTime->wDayOfWeek = dayofweek;
    lpTime->wMonth = month;
    lpTime->wYear = year;

    return TRUE;
}

Regardless of whether or not you know this programming language (C), you should be able to see what caused the Zune player to freeze. In fact, it's a common code smell: the arrow anti-pattern.

Still don't see it? Take a close look at that while/if/if loop. Still don't see it? Well, there was some discussion of this code over at Reddit. There was some talk about whether or not it would be possible to find this bug automatically and that's really an interesting topic. Some type inference systems can catch infinite loops (the paper that Mark Jason Dominus drew on for his Strong Typing and Perl talk). However, I doubt such inference could catch this bug.

Using type systems to find infinite loop bugs requires that you have a sound type system for your language ("sound type systems" has a very specific meaning), something Perl 5 does not have (Perl 6 won't, either). Microsoft has Terminator, software which looks for infinite loops and, while admitting it can't handle everything, can find many infinite loop bugs. But Terminator probably isn't going to work for us -- it appears to be geared towards C programs and in any event, dynamic languages cause all sorts of havoc with many analysis tools.

So what are we to do? Given that the code above is probably a small sample in many hundreds of thousands of lines of code, it's quite understandable how that could be missed. But can we avoid that?

Well, yeah, actually. It wouldn't be fully automatic, but the simple answer is more than just "write tests for you software". It's "use code coverage tools". Rewriting the problem in Perl (and reformatting to avoid the excessive horizontal whitespace):

1: while ( $days > 365 ){
2:    if ( is_leap_year($year) ) {
3:        if ( $days > 366 ) {
4:            $days -= 366;
5:            $year += 1;
6:        }
7:    }
8:    else {
9:        $days -= 365;
10:        $year += 1;
11:    }
12: }

Now does the problem stand out? What happens if $day == 366? Now we have a problem, but code coverage would have caught that.

Specifically, "conditional coverage" would have caught that the condition in line 3 was never false. Then, a sharp programmer could examine the coverage report and for those conditions which are easy to test, test them! It doesn't guarantee that your software is bug free, but it would have helped Microsoft avoid an embarrassing PR fiasco like this one.

The Fine Print: The following comments are owned by whoever posted them. We are not responsible for them in any way.
 Full
 Abbreviated
 Hidden
More | Login | Reply
Loading... please wait.
  • ... is despite all the vast amounts of code in the Microsoft mobile areas, there wasn't something reusable for that, because clearly someone's had to write it from scratch some time in the last 4 years.

  • First, I appreciate the schadenfreude here as much as the next hacker, but it appears this bug was in the Freescale code for the platform, not the code Microsoft wrote for the Zune. So it effects more than just Zunes...

    Second, the "some type inference systems" is misleading. The one type inference system that Andrew Koenig and MJD discuss is the Hindley-Milner [wikipedia.org] type system, which is used in ML and its descendants (OCaml, F#, Haskell, etc.). Koenig's example demonstrated that a recursive algorithm would

    • Thanks for the extra information.

      I think, ultimately, that part of the problem here could be alleviated by coupling things which must be coupled. For example, having a DayOfYear type with a type coercion system could partially help. Imagine the following type definition (in Perl 6, which doesn't do inferencing, of course, but bear with me):

      subset DayOfYear of Int where { 0 <= $_ <= 366 };

      Obviously, that still leaves edge cases, but I would imagine with inferencing, while you wouldn't get a compile

      • All of this, of course, if from a typing newbie, so if I'm talking complete bollocks, feel free to correct me!

        You're talking complete bollocks. :-)

        The kinds of things a strong static typing system can do is let you create types like DayOfYear, which let you specify a single calendar date, and prevents such nonsense like the 47th of April as being a "date". From there, you can create functions like addDays that take a DayOfYear and an integer number of days and return a new DayOfYear.

        What this code was doing was taking a count of days since the beginning of time, and figuring out the current date by subtractin

      • I think the mindblowingly clever technology you are looking for here is called a truth table. :-)