Achieving Coverage

CGI Decoder

CGI encoding is used in URLs (i.e., Web addresses) to encode characters that would be invalid in a URL, such as blanks and certain punctuation:

• Blanks are replaced by +
• Other invalid characters are replaced by %xx, where xx is the two-digit hexadecimal equivalent.

def cgi_decode(s: str) -> str:
    """Decode the CGI-encoded string `s`:
       * replace '+' by ' '
       * replace "%xx" by the character with hex number xx.
       Return the decoded string.  Raise `ValueError` for invalid inputs."""

    # Mapping of hex digits to their integer values
    hex_values = {
        '0': 0, '1': 1, '2': 2, '3': 3, '4': 4,
        '5': 5, '6': 6, '7': 7, '8': 8, '9': 9,
        'a': 10, 'b': 11, 'c': 12, 'd': 13, 'e': 14, 'f': 15,
        'A': 10, 'B': 11, 'C': 12, 'D': 13, 'E': 14, 'F': 15,
    }

    t = ""
    i = 0
    while i < len(s):
        c = s[i]
        if c == '+':
            t += ' '
        elif c == '%':
            digit_high, digit_low = s[i + 1], s[i + 2]
            i += 2
            if digit_high in hex_values and digit_low in hex_values:
                v = hex_values[digit_high] * 16 + hex_values[digit_low]
                t += chr(v)
            else:
                raise ValueError("Invalid encoding")
        else:
            t += c
        i += 1
    return t

Black-box testing

In the above case, we thus would have to test cgi_decode() by the features specified and documented, including:

• testing for correct replacement of '+';
• testing for correct replacement of "%xx";
• testing for non-replacement of other characters; and
• testing for recognition of illegal inputs.

Here are four assertions (tests) that cover these four features. We can see that they all pass:

assert cgi_decode('+') == ' '
assert cgi_decode('%20') == ' '
assert cgi_decode('abc') == 'abc'

try:
    cgi_decode('%?a')
    assert False
except ValueError:
    pass

Black-box testing has the advantage of detecting errors in a program’s expected behavior. Since it doesn’t rely on the actual code, tests can be designed even before the program is built. However, the downside is that black-box testing focuses only on what the program is supposed to do, not how it does it. As a result, it may miss certain details in the implementation, leaving parts of the code untested because the tests are only based on the specifications and not the full scope of the code.

White-box testing

White-box testing is closely tied to the concept of covering structural features of the code. If a statement in the code is not executed during testing, for instance, this means that an error in this statement cannot be triggered either. White-box testing thus introduces a number of coverage criteria that have to be fulfilled before the test can be said to be sufficient. The most frequently used coverage criteria are:

• Statement coverage – each statement in the code must be executed by at least one test input.
• Branch coverage – each branch in the code must be taken by at least one test input. (This translates to each if and while decision once being true, and once being false.) Besides these, there are far more coverage criteria, including sequences of branches taken, loop iterations taken (zero, one, many), data flows between variable definitions and usages, and many more.

Let us consider cgi_decode(), above, and reason what we have to do such that each statement of the code is executed at least once. We’d have to cover:

• The block following if c == '+'
• The two blocks following if c == '%' (one for valid input, one for invalid)
• The final else case for all other characters.

This creates a situation similar to black-box testing, where the tests focus on specified behaviors. This happens often because programmers usually implement different behaviors in separate parts of the code. By testing those specific locations, the tests naturally end up covering the various behaviors outlined in the program’s specification. So, even though the tests are based on the program’s behavior, they still manage to cover much of the underlying code. The downside is that it may miss non-implemented behavior: If some specified functionality is missing, white-box testing will not find it.

Tracing executions

A great advantage of white-box testing is that it allows automatic tracking of whether certain parts of the code were executed during testing. This is done by adding special functionality to monitor the program’s execution. As the program runs, this functionality records which lines of code were executed, and afterward, this data is provided to the programmer. The programmer can then focus on creating tests to cover any uncovered parts of the code.

An important part of white-box testing is “tracing.” In Python, tracing can be automated with the sys.settrace(f) command, where f is a function that the interpreter calls every time a line of code is executed. By analyzing this tracing data, you can determine the code coverage — the percentage of code that has been tested. Higher coverage is better, as it indicates that more of the code has been tested, reducing the likelihood of undetected errors.