commits

Clone the repository to access all 8 commits.

• slides/
• .gitignore
• Makefile
• README.md
• base64.c
• base64.h
• channels.scm
• manifest.scm

An Introduction to Symbolic Execution

Material for an introduction to symbolic execution, a presentation at Hackover’26.

This repository includes the files required to experiment with the live demonstration from the presentation. Specifically, it includes the setup required to verify the Base64 implementation provided by the RIOT operating system. The original, unmodified source code is available on GitHub.

Usage

Ideally, use this repository with Guix:

$ guix time-machine -C channels.scm -- shell -m manifest.scm

Within the Guix shell run the following commands:

$ make sim

Alternatively, you can also try to use KLEE’s Docker image:

$ docker run --rm  -v "$(pwd):/code" -it klee/klee

Within the container run:

$ cd /code
$ make sim

Tweaking the Example

The example uses a fixed-size input buffer, defaulting to 3 bytes. The size can be configured through the INPUT_SIZE variable, for example:

$ INPUT_SIZE=2 make -B

For an input size of 3 bytes, 625 execution paths should be discovered. On my hardware, this takes around 2 minutes. Depending on the size, the number of execution paths, and the time required to discover them will vary.

Further, it is possible to experiment with various KLEE optimizations to speed up this example. A technique particularly beneficial to this example is state merging. To enable state merging, invoke make as follows:

$ CFLAGS=-DKLEE_STATE_MERGING make -B

This will merge multiple execution paths of getsymbol / getcode into a single conjugated SMT-LIB expression. Thereby, increasing SMT-LIB query complexity but reducing the number of execution paths.

To play around with other optimizations, refer to the KLEE documentation.

More Information

The following material provides more background information:

• Symbolic Execution for Software Testing: Three Decades Later
• A Survey of Symbolic Execution Techniques

Further, the KLEE documentation includes additional practical examples:

1. Testing a Regular Expression Library
2. Testing GNU coreutils