Coverage Frontier Analysis Tutorial

Say you have a function and you want to determine, for some set of concrete inputs, which conditionals are only ever taken in one direction. This is sometimes called the “coverage frontier” and the concept is described at more length elsewhere in these docs. Why would you want to know that? Well, if the set of inputs is large then the coverage frontier tells you exactly which conditionals are not well served by those inputs, since they are only ever taken in one direction.

The CoverageFrontier analysis computes exactly this; for some set of execution traces (each of which generates a TraceExecutionHint), it analyses the sequences of instructions to identify conditionals that are half-covered, meaning only one branch is ever taken. These are the coverage frontier.

For this tutorial, you will consider a program that contains the following function foo which takes a single argument (in the edi register).

┌ 31: sym.foo (int64_t arg1);
│ `- args(rdi) vars(1:sp[0xc..0xc])
│           0x00001149      55             push rbp
│           0x0000114a      4889e5         mov rbp, rsp
│           0x0000114d      897dfc         mov dword [var_4h], edi     ; arg1
│           0x00001150      8b45fc         mov eax, dword [var_4h]
│           0x00001153      83e001         and eax, 1
│           0x00001156      85c0           test eax, eax
│       ┌─< 0x00001158      7507           jne 0x1161
│       │   0x0000115a      b824000000     mov eax, 0x24               ; '$'
│      ┌──< 0x0000115f      eb05           jmp 0x1166
│      ││   ; CODE XREF from sym.foo @ 0x1158(x)
│      │└─> 0x00001161      b842000000     mov eax, 0x42               ; 'B'
│      │    ; CODE XREF from sym.foo @ 0x115f(x)
│      └──> 0x00001166      5d             pop rbp
└           0x00001167      c3             ret
[0x00001060]>

The argument is copied into eax and tested to determine if it is odd or even, which is used to decide the conditional branch at 0x1158. The function returns either 0x24 or 0x42 based on the whether or not the argument edi is even. Given how this function operates, if you execute it just once, you should see just one of the branches of 0x1158 execute. In this case, 0x1158 is certain to be in the coverage frontier. However, if you execute the function more than once with both odd and even inputs, or if you just run it a lot of times with random inputs, then it is very likely to hit both branches, meaning 0x1158 will not be in the coverage frontier.

There is a script in the SmallWorld test suite used to exercise and verify the CoverageFrontier analysis. This script harnesses the function foo above (setting the entry point to 0x1149), in the program cf that is pre-compiled in that testing directory. The script contains a lot that is either boilerplate or relevant only to testing. Let’s focus on the parts of it that make use of the CoverageFrontier. First, there is code that sets up a hinter and creates the CoverageFrontier analysis object.

    hinter = hinting.Hinter()
    hinter.register(CoverageFrontierHint, collect_hints)

The script registers a function to collect the CoverageFrontierHint that is output by the analysis. Only one such hint will be output by the analysis when it is run.

hints = []


def collect_hints(hint):

The script creates num_micro_exec traces, using the TraceExecution analysis. For each, a different and random value is assigned to rdi which is the input to the function foo. Each of these runs of TraceExecution will output a TraceExecutionHint that is consumed by the CoverageFrontier analysis.

    for i in range(num_micro_exec):
        logger.info(f"\nmicro exec number {i}")
        random.seed(seed + i)
        te = TraceExecution(hinter, num_insns=num_insns, seed=seed + i)
        machine_copy = copy.deepcopy(machine)
        cpu = machine_copy.get_cpus()[0]
        # choose random value for the input to this function
        cpu.rdi.set_content(random.randint(0, 0xFFFFFF))

After all these traces have been created and hinted, we run the CoverageFrontier analysis

    # NB: covg frontier `run` method doesnt actually use the machine input
    # it just works from TraceExecution hints.
    cf.run(machine)

The upshot of all this should be that we collect a single CoverageFrontierHint which will be in the global hint[0]. This hint’s coverage_frontier set is output with code like this (where h = hint[0]).

    )
    for pc in h.coverage_frontier:
        assert pc in e
        assert len(e[pc]) == 1

Here is the complete script, which contains some code to harness the cf program as well as some needed for testing.

import copy
import logging
import pathlib
import random
import sys

import smallworld
from smallworld import hinting
from smallworld.analyses import (  # Colorizer, ColorizerReadWrite, ColorizerSummary
    CoverageFrontier,
    TraceExecution,
)
from smallworld.hinting.hints import CoverageFrontierHint

# setup logging and hinting
smallworld.logging.setup_logging(level=logging.DEBUG)

logger = logging.getLogger(__name__)

# configure the platform for emulation
platform = smallworld.platforms.Platform(
    smallworld.platforms.Architecture.X86_64, smallworld.platforms.Byteorder.LITTLE
)

# create a machine
machine = smallworld.state.Machine()

# create a CPU and add it to the machine
cpu = smallworld.state.cpus.CPU.for_platform(platform)

path = pathlib.Path(__file__).parent.resolve()
code = smallworld.state.memory.code.Executable.from_elf(
    open(f"{path}/cf", "rb"), address=0x000
)
machine.add(code)

# Create a stack and add it to the state
stack = smallworld.state.memory.stack.Stack.for_platform(platform, 0x10000, 0x4000)
machine.add(stack)
rsp = stack.get_pointer()
cpu.rsp.set(rsp)

entry_point = 0x1149
exit_point = 0x1167

cpu.rip.set(entry_point)
machine.add(cpu)
machine.add_exit_point(exit_point)


hints = []


def collect_hints(hint):
    hints.append(hint)


# num_micro_exec   How many micro executions.
# num_insn:        how many (max) instructions to execute from entry
# seed:            seed for RNG
def test(num_micro_exec, num_insns, seed):
    global hints

    hints = []

    hinter = hinting.Hinter()
    hinter.register(CoverageFrontierHint, collect_hints)
    cf = CoverageFrontier(hinter)

    for i in range(num_micro_exec):
        logger.info(f"\nmicro exec number {i}")
        random.seed(seed + i)
        te = TraceExecution(hinter, num_insns=num_insns, seed=seed + i)
        machine_copy = copy.deepcopy(machine)
        cpu = machine_copy.get_cpus()[0]
        # choose random value for the input to this function
        cpu.rdi.set_content(random.randint(0, 0xFFFFFF))
        te.run(machine_copy)

    # NB: covg frontier `run` method doesnt actually use the machine input
    # it just works from TraceExecution hints.
    cf.run(machine)

    h = hints[0]

    e = {}
    for from_pc, to_pc_list in h.edges:
        e[from_pc] = to_pc_list
        print(f"0x{from_pc:x}", end="")
        if from_pc in h.branches:
            print(" [branch] ", end="")
        print(" -> [", end="")
        for to_pc in to_pc_list:
            print(f" 0x{to_pc_list[0]:x}", end="")
        print("]")

    print(
        f"Coverage frontier for {h.num_traces} traces contains {len(h.coverage_frontier)} branches"
    )
    for pc in h.coverage_frontier:
        assert pc in e
        assert len(e[pc]) == 1
        print(f"  half-covered branch @ 0x{pc:x}")

    return hints


if __name__ == "__main__":
    try:
        num_micro_exec = int(sys.argv[1])
        num_insns = int(sys.argv[2])
        seed = int(sys.argv[3])
    except:
        logger.info("Error in one or more args")
        logger.info("""Usage: colorizer_test.py num_insns buflen fortytwos seed
num_micro_exec  How many micro executions.
num_insns:       How many (max) instructions to execute from entry for each micro exec.
seed:           Seed for random number generator.""")
        sys.exit(1)

    _ = test(num_micro_exec, num_insns, seed)

The script takes three arguments. The first is the number of micro-executions or traces to run, each of which is an execution of the function foo. The second sets a maximum number of instructions to execute. The third argument is a seed for the random number generator.

If we run script, asking it to create a single trace, as noted earlier, we can only execute one branch of the jne at 0x1158, so the coverage frontier will contain that branch instruction.

$ python3 coverage_frontier_test.py 1 100 1233 2> /dev/null
0x1149 -> [ 0x114a]
0x114a -> [ 0x114d]
0x114d -> [ 0x1150]
0x1150 -> [ 0x1153]
0x1153 -> [ 0x1156]
0x1156 -> [ 0x1158]
0x1158 [branch]  -> [ 0x115a]
0x115a -> [ 0x115f]
0x115f -> [ 0x1166]
Coverage frontier for 1 traces contains 1 branches
  half-covered branch @ 0x1158

And if we ask for three or more traces, with this same seed, we will have enough execution diversity to have hit both branches, and our coverage frontier will be empty.

$ python3 coverage_frontier_test.py 3 100 1233 2> /dev/null
0x1149 -> [ 0x114a]
0x114a -> [ 0x114d]
0x114d -> [ 0x1150]
0x1150 -> [ 0x1153]
0x1153 -> [ 0x1156]
0x1156 -> [ 0x1158]
0x1158 [branch]  -> [ 0x115a 0x115a]
0x115a -> [ 0x115f]
0x115f -> [ 0x1166]
0x1161 -> [ 0x1166]
Coverage frontier for 3 traces contains 0 branches

The function foo is not a complicated one; consider it a toy example. If it were much larger or more complicated, then determining, merely by inspection, what conditionals were likely to easily covered would be very difficult. The CoverageFrontier can figure this out for you directly.

Further Reading

See the CoverageFrontier Concepts page for more details.