184. Firmware testing: levels, coverage, mutations, sanitizers

Section 182 showed what a bug costs once it survives into the field. Here we look at how to catch it, and how to tell whether a test suite really checks something or is just "green".

Everything runs on a live example: a frame parser for 0x55 — length — data — CRC-8, the same code that parses the UART stream in the firmware. It builds both on the board and on a PC, so every measurement below is real: gcc 12 in the stm-lab:1 image, coverage with gcov, mutations and a sanitizer.

What it is called in the documentation

Term	Meaning
unit test	a test of one module in isolation
integration / system test	a test of modules together; a test of the whole device
test harness, fixture	the test framework; setting up the environment before a test
code coverage: line / branch	share of lines or branches executed by the tests
mutation testing	breaking the code on purpose to see if the tests notice
mutant killed / survived	the tests failed on the broken code / the tests still passed
sanitizer (ASan, UBSan)	run-time checks for memory errors and undefined behavior
fuzzing	feeding random inputs
stub, mock	a stand-in for a dependency
regression test	a test that catches an old bug coming back

184.1 Three levels and what each one catches

The point of the split is the cost of a run. Unit tests take a fraction of a second on every change, so they catch a bug at the coding stage, where it costs an hour (section 182.2). System checks run before delivery, and that is also where the cost of a bug sits.

For firmware the rule is simple: separate the logic from the hardware. Frame parsing, calibration math, a state machine, a ring buffer — this is plain C with no registers, and it is tested on a PC. Everything that touches registers is hidden behind a thin layer, and the tests substitute a stub for it.

184.2 A module you can test without a board

The parser is a state machine with four states: wait for the start byte, read the length, collect the data, verify the CRC. An error returns the parser to the beginning:

case FR_LEN:
    if (b == 0u || b > FRAME_MAX) {
        frame_reset(p);
        return FRAME_ERR;
    }
    p->len = b;
    p->got = 0;
    p->state = FR_DATA;
    return FRAME_NONE;

It has not a single register access: the bytes arrive as a parameter. On the board it is fed by the UART interrupt, in the tests by an array. By gcov's count it is 45 lines of code and 22 branches.

184.3 A twenty-line test harness

No library is needed: we count checks and failures.

static int checks, failed;

static void check(int cond, const char *what)
{
    checks++;
    if (!cond) {
        failed++;
        printf("FAIL: %s\n", what);
    }
}

The tests are collected in a table, and -DUPTO=k runs only the first k, so you can see what each next test adds:

The whole suite is 8 tests and 15 checks, and a run takes a fraction of a second.

184.4 Coverage: what it tells you and what it does not

gcc --coverage and gcov -b count which lines and branches were executed:

The very first test, "correct frame", gives 91.11 % of lines: the happy path goes through almost the whole module. By the fourth test coverage hits the ceiling: 100 % of lines and 100 % of branches. It does not grow after that, and judging by it there seems to be no reason to write more tests.

Coverage honestly answers the question "what was never executed". It says nothing about whether the result was checked: a line executed without a single check of its result counts exactly the same as a checked one.

184.5 Mutation testing: a test for the tests themselves

The idea is simple: break the code with one edit and see whether the tests fail. If they do not, that edit is not covered by the tests. Mutations are taken in order, with no randomness: comparisons are swapped for neighboring ones (== for !=, < for <=), integer literals are increased by one. On our module this gave 48 mutants.

With 100 % line and branch coverage (four tests) only 34 of 48 are killed: 71 %. The full suite of eight tests kills 44: 92 %.

The most interesting one is the eighth test. It finishes off nine mutants at once, and all of them concern the CRC: the polynomial 0x07, the initial value, the bit counter. Why did the other tests not catch them? Because they computed the expected CRC with the very same code:

buf[5] = frame_crc8(data, 3);      /* ожидание из проверяемого кода */
...
check(frame_crc8(d, 3) == 0xC0u, "CRC-8 на известных данных");

The first line checks nothing about the CRC itself: break the polynomial and both the frame and the expected value change the same way. The second one does check, because the answer is written as a number obtained independently. Hence the rule: at least one test per algorithm must compare against a number, not against a call to the same code.

It is also useful to look at the four surviving mutants:

The first three are not a gap in the tests but redundant code: the reset assigns fields that are set again anyway before use. The fourth is a real gap, and more on it below.

184.6 Sanitizers and random inputs

The i <= p->len mutant copies one byte more than the frame holds. At length 32 this is a write past the end of the array, and the tests do not notice it: the extra byte lands in neighboring memory and breaks nothing. The same run, built with the checks -fsanitize=undefined -fsanitize=bounds-strict, fails at once:

runtime error: index 32 out of bounds for type 'uint8_t [32]'

The sanitizer knows nothing about our tests: it checks the code itself at run time. That is why unit tests are run twice: in a normal build and in a sanitizer build.

Along the way we find out where "flaky" tests come from. Another mutant, i < n to i <= n in the CRC calculation, reads one byte past the end of the array, and a normal build kills it only every other time: whatever happened to be in neighboring memory ends up in the CRC. That is why all measurements are built with -ftrivial-auto-var-init=zero: local variables are zeroed, and the run repeats number for number. In real firmware this same mutant is a read of an extra byte, and the sanitizers do not see it: the undefined and bounds checks do not know the size behind a pointer, and -fsanitize=address stays silent because the byte after data lies inside the same structure. Only tests catch it.

The second cheap tool is random inputs. A run of 2000000 random bytes through the parser (with our own generator, so that the run is repeatable):

The sanitizer did not say a word during the whole run. Four random frames per two million bytes is normal: for a frame to assemble, the random data has to match the CRC. The value of the run lies elsewhere: the parser rejected garbage 7786 times correctly and never once went past the array or hung.

184.7 What to keep in the pipeline

• Unit tests on every change: they take a fraction of a second (section 110).
• A second build with a sanitizer: the same tests, a different compiler flag.
• Coverage as a signal of what is untested, not as a goal: 100 % means "we did not forget to run anything", not "everything is checked".
• Mutations now and then: a run of 48 mutants over eight suites takes minutes, so they are not run on every change but before a release or on a schedule.
• A test for every bug found. The condition is already known, the test takes minutes to write, and it catches the bug coming back forever.

The payback is calculated exactly as in 182.3: the investment in the test harness against the hours saved on bugs that never reached the field.

184.8 Pitfalls

The test compares against a call to the same code. That is exactly why nine CRC mutants survived. At least one expected value must be an independent number.

100 % coverage is taken for quality. At 100 % of lines and branches 14 of 48 mutants survived.

Tests only for the happy path. A single "correct frame" test gives 91.11 % of lines and catches neither a corrupted CRC nor a wrong length.

Logic mixed with registers. Such a module cannot be built on a PC, and it is left with no unit tests at all.

Tests are not run with a sanitizer. A one-byte write past the end of an array goes unnoticed by a normal run for years, until someone reorders the fields of the structure.

A flaky test is left "as is for now". A test that sometimes fails is ignored by everyone within a week, and with it people stop reading the whole suite.

184.9 Summary

• Separate the logic from the hardware: frame parsing, calculations and state machines are tested on a PC in a fraction of a second, the bench and the product one level higher.
• Coverage shows what is untested, but not quality: 4 tests give 100 % of lines and branches, yet kill 34 of 48 mutants (71 %); 8 tests kill 44 of 48 (92 %).
• A test that computes the expected value with the same code does not check the algorithm: the eighth test with the number 0xC0 finished off nine CRC mutants at once.
• A sanitizer catches what the tests do not see: a write past the end of the array on a frame of maximum length.
• Random inputs are cheap: 2000000 bytes, 7786 rejected frames, not a single failure and not a single wrong length.

Full source code

frame.c: frame parsing, the code under test.

#include "frame.h"

void frame_reset(frame_parser_t *p)
{
    p->state = FR_WAIT;
    p->len = 0;
    p->got = 0;
    p->crc = 0;
}

uint8_t frame_crc8(const uint8_t *data, size_t n)
{
    uint8_t crc = 0x00u;
    for (size_t i = 0; i < n; i++) {
        crc ^= data[i];
        for (int bit = 0; bit < 8; bit++) {
            if (crc & 0x80u) {
                crc = (uint8_t)((crc << 1) ^ 0x07u);
            } else {
                crc = (uint8_t)(crc << 1);
            }
        }
    }
    return crc;
}

int frame_feed(frame_parser_t *p, uint8_t b, frame_t *out)
{
    switch (p->state) {
    case FR_WAIT:
        if (b == FRAME_START) {
            p->state = FR_LEN;
        }
        return FRAME_NONE;

    case FR_LEN:
        if (b == 0u || b > FRAME_MAX) {
            frame_reset(p);
            return FRAME_ERR;
        }
        p->len = b;
        p->got = 0;
        p->state = FR_DATA;
        return FRAME_NONE;

    case FR_DATA:
        p->data[p->got] = b;
        p->got++;
        if (p->got == p->len) {
            p->state = FR_CRC;
        }
        return FRAME_NONE;

    case FR_CRC:
    default:
        p->crc = frame_crc8(p->data, p->len);
        if (p->crc != b) {
            frame_reset(p);
            return FRAME_ERR;
        }
        out->len = p->len;
        for (uint8_t i = 0; i < p->len; i++) {
            out->data[i] = p->data[i];
        }
        frame_reset(p);
        return FRAME_READY;
    }
}

tests.c: the test suite for frame parsing.

/* Набор тестов к разбору кадра. UPTO=k — прогнать только первые k тестов. Раздел 184.
   Разборщик, кадр и данные объявлены static с запасным нулевым байтом в конце: тогда
   мутант, залезающий за границу массива, ведёт себя одинаково от прогона к прогону. */
#include <stdio.h>
#include <string.h>
#include "frame.h"

static int checks, failed;
static frame_parser_t p;
static frame_t out;

static void check(int cond, const char *what)
{
    checks++;
    if (!cond) {
        failed++;
        printf("FAIL: %s\n", what);
    }
}

/* прогнать массив байт через разборщик; вернуть последний результат */
static int feed_all(const uint8_t *b, size_t n)
{
    int r = FRAME_NONE;
    for (size_t i = 0; i < n; i++) {
        r = frame_feed(&p, b[i], &out);
    }
    return r;
}

static void test_good(void)
{
    static const uint8_t data[4] = {0x01, 0x02, 0x03, 0x00};
    static uint8_t buf[6] = {FRAME_START, 3, 0x01, 0x02, 0x03, 0};
    buf[5] = frame_crc8(data, 3);
    frame_reset(&p);
    check(feed_all(buf, 6) == FRAME_READY, "правильный кадр принят");
    check(out.len == 3 && memcmp(out.data, data, 3) == 0, "данные кадра совпали");
}

static void test_bad_crc(void)
{
    static const uint8_t data[3] = {0x10, 0x20, 0x00};
    static uint8_t buf[5] = {FRAME_START, 2, 0x10, 0x20, 0};
    buf[4] = (uint8_t)(frame_crc8(data, 2) ^ 0xFFu);
    frame_reset(&p);
    check(feed_all(buf, 5) == FRAME_ERR, "неверная CRC отвергнута");
    check(p.state == FR_WAIT, "после ошибки разборщик ждёт старт-байт");
}

static void test_bad_len(void)
{
    static const uint8_t zero[2] = {FRAME_START, 0};
    static const uint8_t big[2] = {FRAME_START, FRAME_MAX + 1};
    frame_reset(&p);
    check(feed_all(zero, 2) == FRAME_ERR, "длина 0 отвергнута");
    frame_reset(&p);
    check(feed_all(big, 2) == FRAME_ERR, "длина больше предела отвергнута");
}

static void test_garbage_before_start(void)
{
    static const uint8_t data[2] = {0xAA, 0x00};
    static uint8_t buf[7] = {0x00, 0xFF, 0x12, FRAME_START, 1, 0xAA, 0};
    buf[6] = frame_crc8(data, 1);
    frame_reset(&p);
    check(feed_all(buf, 7) == FRAME_READY, "мусор до старт-байта не мешает");
    check(out.len == 1 && out.data[0] == 0xAA, "кадр после мусора разобран");
}

static void test_max_len(void)
{
    static uint8_t data[FRAME_MAX + 1];
    static uint8_t buf[FRAME_MAX + 3];
    for (unsigned i = 0; i < FRAME_MAX; i++) {
        data[i] = (uint8_t)(i * 7 + 1);
    }
    buf[0] = FRAME_START;
    buf[1] = FRAME_MAX;
    memcpy(buf + 2, data, FRAME_MAX);
    buf[FRAME_MAX + 2] = frame_crc8(data, FRAME_MAX);
    frame_reset(&p);
    check(feed_all(buf, FRAME_MAX + 3) == FRAME_READY, "кадр предельной длины принят");
    check(out.len == FRAME_MAX, "длина предельного кадра верна");
}

static void test_start_inside_data(void)
{
    static const uint8_t data[3] = {FRAME_START, 0x55, 0x00};
    static uint8_t buf[5] = {FRAME_START, 2, FRAME_START, 0x55, 0};
    buf[4] = frame_crc8(data, 2);
    frame_reset(&p);
    check(feed_all(buf, 5) == FRAME_READY, "старт-байт внутри данных не ломает кадр");
}

static void test_two_frames(void)
{
    static const uint8_t d1[2] = {0x41, 0x00};
    static const uint8_t d2[2] = {0x42, 0x00};
    static uint8_t buf[8] = {FRAME_START, 1, 0x41, 0, FRAME_START, 1, 0x42, 0};
    buf[3] = frame_crc8(d1, 1);
    buf[7] = frame_crc8(d2, 1);
    frame_reset(&p);
    check(feed_all(buf, 4) == FRAME_READY && out.data[0] == 0x41, "первый кадр");
    check(feed_all(buf + 4, 4) == FRAME_READY && out.data[0] == 0x42, "второй кадр подряд");
}

static void test_crc_known(void)
{
    static const uint8_t d[4] = {0x31, 0x32, 0x33, 0x00};
    check(frame_crc8(d, 3) == 0xC0u, "CRC-8 на известных данных");
    check(frame_crc8(d, 0) == 0x00u, "CRC-8 пустых данных");
}

#ifndef UPTO
#define UPTO 8
#endif

typedef void (*test_fn)(void);

static const test_fn TESTS[] = {
    test_good,                  /* 1 — счастливый путь */
    test_bad_crc,               /* 2 — испорченная CRC */
    test_bad_len,               /* 3 — длина 0 и больше предела */
    test_garbage_before_start,  /* 4 — мусор до старт-байта */
    test_max_len,               /* 5 — кадр предельной длины */
    test_start_inside_data,     /* 6 — старт-байт внутри данных */
    test_two_frames,            /* 7 — два кадра подряд */
    test_crc_known,             /* 8 — CRC на известных данных */
};

int main(void)
{
    unsigned n = UPTO;
    if (n > sizeof(TESTS) / sizeof(TESTS[0])) {
        n = sizeof(TESTS) / sizeof(TESTS[0]);
    }
    for (unsigned i = 0; i < n; i++) {
        TESTS[i]();
    }
    printf("тестов: %u, проверок: %d, провалов: %d\n", n, checks, failed);
    return failed ? 1 : 0;
}

Next: section 185 "Dart for the firmware engineer: bytes, numbers, frame parsing".