Gimme a Break

Recently, Linux kernel developers have picked up use of Coverity Scan by addressing new defects found in recently submitted patches. One developer, Dave Jones, noticed a change to remove a fall through comment on a switch case:

>    case MPOL_BIND:
> -          /* Fall through */
>    case MPOL_INTERLEAVE:
>            nodes = pol->v.nodes;
>            break;

Any reason not to leave this ?

"missing break" is the 2nd most common thing that Coverity picks up.
Most of them are false positives like the above, but the lack of
annotations in our source makes it time-consuming to pick through them
all to find the real bugs.

Another dev replies:

    Check out things like drivers/mfd/wm5110-tables.c that do things like:

        switch (reg) {
        case ARIZONA_SOFTWARE_RESET:
        case ARIZONA_DEVICE_REVISION:
        case ARIZONA_CTRL_IF_SPI_CFG_1:
        case ARIZONA_CTRL_IF_I2C1_CFG_1:
        case ARIZONA_CTRL_IF_I2C2_CFG_1:
        case ARIZONA_CTRL_IF_I2C1_CFG_2:
        case ARIZONA_CTRL_IF_I2C2_CFG_2:
        ...

    and that file has over 1,000 case statements.  Having a

        /* fall through */

    for all of them would be pretty annoying.

Actually, the MISSING_BREAK checker doesn't report cases like this. There are 14 distinct idioms we've identified (so far) where switch cases that fall through are likely to be false positives, and we suppress them by default. Here are a few of these idioms that MISSING_BREAK takes into account:

Empty Cases

If there are no statements between the start and end cases, such as the examples above, no defect is reported. Therefore, the comment could be removed without a false positive being introduced, and we would not report false positives for the over 1,000 case labels in wm5110-tables.c.

Terminated Branches

Consider this example:

 switch (x) {
    case 1:
      x++;
    case 2:
    case 3:
      break;       // No defect reported
    }

In this case, the subsequent case labels immediately break. In this case, inserting a break would not change the program behavior, so we do not report.

Comment Heuristic

If a comment is the last line of a case label, we suppress by default:

switch (int x) {
    case 1:
      x++;
      // fall through       <-- this comment causes suppression
    case 2:
      x++;
    }

We also suppress a case label if there is a comment that matches [^#]fall.?thro?u, even if it's not on the last line.

Countdown Heuristic

It's fairly common to have a "countdown" switch statement where each case falls through to the next case. This is used as a form of loop unrolling for things like memory or string copying (see Duff's device):

 switch (length) {
    ...
    case 3:
      *p++=(char)(value>>16);
    case 2:
      *p++=(char)(value>>8);
    case 1:
      *p++=(char)value;
    default:
      break;
    }

When we recognize code that appears to be doing this deliberately, we suppress the defects automatically.

Trade-Offs

There are checker options to control many of these heuristics if a user wants to adjust the detection settings. Normally, the checker attempts to minimize false positive rates, which means most of these suppression heuristics are on by default.

For the Linux kernel specifically, we've observed that when there are multiple MISSING_BREAK reports within a single function, the false positive rate is much higher. There is a checker option maxReportsPerFunction that should probably be set to 3 (or even 2). This will automatically suppress defects if more than the specified number of defects are found within one function. This is a blunt tool to use, but empirically it greatly reduces the number of false positives in the Linux kernel. Of course, the trade-off is that it might cause us to miss real defects, but we estimate that only 5% of the real defects in Linux are lost by this heuristic. It seems like the right trade-off for day to day scanning, with perhaps a more thorough review only rarely. Our Scan team is working with the Linux kernel developers to adjust the settings according to their needs - other users of Coverity should examine how much tolerance they have for the noise that remains after all of the heuristics have been applied. Most code bases don't have as many MISSING_BREAK reports as the Linux kernel appears to, so they probably don't need any tuning at all.

We also have some ideas for improving this checker to lower the false positive rate while not losing any of the real defects. That work is ongoing and experimental. We will certainly take a look at the results of our experiments on the Linux kernel when making improvements to this checker going forward. Any kernel developers have ideas on what distinguishes the real missing break bugs from the rest? Send us a note!

Since this is a security blog, what's the connection to security? See CWE 484.