Assignment 2

Software Engineering - Fall 2026

A. Instructions

Assignment 2 due Nov 16th.

B. General hints

This page will be updated with more indications as I get more questions.

  1. If you get stuck at any stage, immediately contact me.
  2. Try to keep notes of everything you do and how you overcome issues. This will be useful later if you have to perform the same steps again.
  3. It may be easier to prepare your answers in a text file and copy/paste them into Blackboard when you are done.
  4. Your first steps could be as follows:
    • Install AFL++.
    • Read the documentation of AFL++ about how to use it effectively.
    • Download GLPK and first build it with a regular gcc/clang compiler (no AFL++). You may not need that, but it is a helpful check that everything works as it should.
    • Understand how to use GLPK from the command line (the executable is glpsol).
    • Run glpsol on an example file to check that it works.
    • Start fuzzing GLPK.
  5. Building and fuzzing commands quickly get complex (many parameters). It is often helpful to put such long commands into a script file (e.g. myscript.sh), make the script executable (chmod +x myscript.sh), then run the script file (./myscript.sh). This has the added advantage of allowing you to re-run the exact same building or fuzzing commands later.

C. Compiling GLPK (not platform-specific)

  1. Use GLPK’s ./configure script options to choose a compiler (e.g. AFL++’s compile-with-instrumentation scripts) and to choose compiler options (e.g. enabling ASan or UBSan). Run ./configure --help | less to see how to.
  2. Fuzzing will only work if you compile GLPK with static linking. Disable dynamic linking and enable static linking in the options of ./configure. It may be convenient to create a small script that calls ./configure with your chosen options.
  3. Whenever you re-run ./configure, you need to run make clean to make sure that the next compilation will re-build everything with your updated options.
  4. The -j option of make allows parallel (hence faster) compilations. For example, use -j 8 if your computer has 8 parallel threads.
  5. The glpsol executable is in the examples/ directory.
  6. If glpsol was already installed on your computer, beware of which glpsol executable you are running (you probably want to run the one you just compiled).
  7. You can use afl-clang-lto if it is available on your platform. Fuzzing will be slightly faster with afl-clang-lto, but compilation will be significantly slower. One option would be to test everything and start fuzzing with afl-clang-fast variants, and only use LTO for long (e.g. overnight) runs in an effort to find more crashes.
  8. You may need to compile GLPK multiple times (e.g. with clang or with afl-clang, with or without sanitizers, etc.) Once you successfully produce a glpsol executable, I would advise copying it somewhere for safekeeping.
  9. One downside of parallel builds is that understanding compilation errors can be harder. In such case, immediately re-run make without the -j option and try to fix the compilation error. Once it is fixed, you can interrupt the non-parallel build (control+C), then resume building in parallel.

D. Fuzzing GLPK

  1. For the starting set of input files, afl-fuzz works best with a limited number (5 to 20) of small valid files (smaller than, say, 10 kB, and can be as small as 5 to 10 bytes) that are different from each other. Invalid files can be included, but they are typically not useful. The examples/ directory in the GLPK source code contains many .mps files in the “fixed MPS” format (--mps option of glpsol), and .mod files in the GNU MathProg format (--math option of glpsol). For example files in the “free MPS” format, see https://miplib2010.zib.de/miplib3/miplib.html. For faster and more effective fuzzing, discard large input files, as well as input files that GLPK is slow to parse. It is also easier to understand bugs when the input files are small. One way to get smaller GNU MathProg files is to remove comments.

  2. The first time you run afl-fuzz, it may ask you to adjust system settings to allow it to run faster. Whenever those adjustments are easy to perform, it is recommended to follow its advice. For example, this command

    echo core | sudo tee /proc/sys/kernel/core_pattern

    is easy to run and is essentially required for AFL++ to work properly on Linux and WSL2.

  3. For fuzzing, you can compile with UBSan enabled to find more bugs, but do not enable ASan (it creates issues when used with AFL++). Once you found a crash, you can recompile with ASan enabled to help track down the bug.

  4. To focus on the input parsing code, use the --check option of glpsol to only run that code (for faster fuzzing).

  5. AFL++ may give you warnings about your input size, or your computer configuration. In such cases, read the instructions carefully. You can choose to address the issues or ignore them (the instructions explain how the warning can be discarded).

  6. When afl-fuzz is running, a red message indicating “no new paths” (or something similar) means that fuzzing is probably not working. The most common cause of that is that the fuzzed program (glpsol in our case) immediately exits with an error message.

    The first thing to try in such case is to run the same glpsol command outside of afl-fuzz, and make sure that everything is working fine.

    If it is, then there must be a difference between us running glpsol manually and afl-fuzz running it. The next two points could be causes for such difference.

  7. By default afl-fuzz chooses a name and directory for the “input” files it creates. If this confuses glpsol, the problem can be worked around with the -f option of afl-fuzz (see afl-fuzz -h for details), which forces it to use a fixed name and path for input files.

  8. If everything is running properly, afl-fuzz should find bugs within the first 2 to 5 minutes.

  9. Once afl-fuzz is running, it keeps looking for new crashes until you stop it. At first, it should be plenty enough to stop it after 5-10 crashes.

E. Understanding and fixing bugs

  1. Compilation with AFL++ instrumentation is slower. If you repeatedly modify the GLPK code and recompile it, it will be convenient to compile it without AFL++ whenever not fuzzing (remember to run make clean before or after ./configure every time).
  2. Assertion failures call abort(). A call to abort() ends a program. When run with valgrind, you get a stack trace at the point abort() was called (i.e. the functions that were called leading to abort()). On MacOS, valgrind may not work, in which case you can use lldb (see below).
  3. Feel free to modify the source code of GLPK to get more information about bugs. You can insert printf() statements, modify logic, etc.
  4. The grep command is useful for navigating a foreign codebase.
  5. GLPK parsers contains multiple bugs. If one bug seems too difficult to understand, try to find an other one. One way to make the fuzzer ignore a bug is to insert a regular exit() call before it is triggered. This will allow the fuzzer to find other bugs.
  6. The memory dedicated to storing the stack has a fixed limited size. Stack overflow bugs happen when the stack exceeds that allocated size. The two most common causes are:
    1. An out-of-bounds access to an on-stack array (an array stored in a local variable in a function).
    2. Infinite (or excessive) recursion (when a function calls itself, directly or indirectly).
  7. In case of stack overflow, ASan only displays the “top” of the stack, i.e. the most-recently called functions in the call stack, as opposed to the whole call stack (with main() at the “bottom”).
  8. You do not need to fully understand the input formats. However, it will be useful to know just enough about the formats to better understand GLPK’s parser code.

F. Hints specific to x86_64 Windows

  1. Run AFL++ on WSL2 (do not use WSL1).

  2. AFL++ Installation

    1. Option 1 (easy)
      • apt-get install afl++
    2. Option 2 (compile AFL++ from source, harder)
      • Instructions are here: https://github.com/AFLplusplus/AFLplusplus/blob/stable/docs/INSTALL.md. As far as I have been told, the docker-based instructions don’t seem to work, so it is probably better to skip them.

      • Your WSL2 distribution probably has a version of LLVM more recent than 18. Therefore, ignore the instructions aiming to install version 18 specifically, replacing

        sudo apt-get install -y lld-14 llvm-14 llvm-14-dev clang-14 || sudo apt-get install -y lld llvm llvm-dev clang

        by

        sudo apt-get install -y lld llvm llvm-dev clang

G. Hints specific to MacOS

  1. Make sure that your operating system is fully updated.

  2. Ensure Homebrew is installed

  3. AFL++ Installation

    1. Option 1 (easy)
      • brew install afl++
      • Note that there is no afl-clang-lto. It is ok, use afl-clang-fast instead.
      • By default, the afl binaries are in:
        • /opt/homebrew/afl-clang-fast
        • /opt/homebrew/afl-clang-fast++
        • /opt/homebrew/afl-fuzz
    2. Option 2 (compile AFL++ from source, harder)
      • The installation instructions for MacOS are here: https://github.com/AFLplusplus/AFLplusplus/blob/stable/docs/INSTALL.md#macos-on-x86_64-and-arm64 but they are a bit out of date, so before following them, first try this:

      • Just download AFL++ source and run make:

        git clone https://github.com/AFLplusplus/AFLplusplus
        cd AFLplusplus
        make
      • If you get the message “LLVM mode could not be built … please install llvm-13”, then make sure that llvm is installed with brew:

        brew install llvm

        then find the llvm-config utility, it should be somewhere like /opt/homebrew/Cellar/llvm/19.1.3/bin/ (the exact path will vary depending on the version of LLMV installed).

        Then, try to run AFL++’s Makefile again, but specifying where it can find llvm-config, like:

        LLVM_CONFIG=/opt/homebrew/Cellar/llvm/19.1.3/bin/llvm-config   make
      • You may get a message “LLVM LTO mode could not be build”. You can safely ignore this.

      • Test failure messages containing “assembler command failed” can be ignored as well, as long as you get afl-clang-fast and afl-clang-fast++.

      • Note the full paths of the afl-clang-fast and afl-clang-fast++ executable binaries. You will need them later.

  4. If you see a message

    ld: unsupported tapi file type '!tapi-tbd' in YAML file

    when trying to compile, then something went wrong with you system configuration. Find out where the ld utility is located by running:

    which ld

    You should get /opt/homebrew/bin/ld or /usr/local/bin/ld (or possibly /usr/bin/ld) but not anything to do with conda. If you see conda in ld’s path, then you must disable Anaconda.

    conda deactivate

    Note that even if it is deactivated now, Anaconda may have interferred with how LLVM, clang and AFL++ were installed. You may have, for example to re-run, with Anaconda deactivated,

    brew install afl++
  5. To get a stack trace, you can use lldb with the following command:

    lldb path/to/glpsol -o 'run -i path/to/crash/file' -o 'bt' -o 'quit'

    where you need to adjust path/to/bin/scip and -f path/to/crash/file.mps to your specific needs. Explanations:

    • We pass to lldb the path to the binary executable (and, optionally, additional parameters).
    • By default, lldb starts in an interactive mode in which we can type commands. The -o command command-line parameter is equivalent to typing command in interactive mode.
    • The run commands tells lldb to run the executable. We type after run the parameters we want to pass to the executable. In our case, we could want glpsol to read and solve a file, hence -i path/to/crash/file.
    • The bt commands tells lldb to print the stack trace.
    • The quit commands prevents lldb from entering interactive mode.
  6. If you get an error message about llvm-ar not being found, you need to update your PATH environment variable so that it can be found.

    • First make sure llvm is installed with brew:

      brew install llvm
    • Then, find the llvm-ar utility. It should be somewhere like /opt/homebrew/Cellar/llvm/19.1.3/bin/ (the exact path will vary depending on the version of LLMV installed). As a last resort, you can use the following commands to find the exact path (this will be a bit slow):

      find /usr -name llvm-ar
      find /opt -name llvm-ar
    • Next, you can run mfile.py with the PATH variable overriden:

      PATH=/opt/homebrew/Cellar/llvm/19.1.3/bin/:$PATH ./mfile.py
    • You can make this change permanent to the current shell session by running:

      export PATH=/opt/homebrew/Cellar/llvm/19.1.3/bin/:$PATH
    • You can make this change permanent to all shell sessions by adding the line above to your ~/.zshrc file. (However, remember that this will only apply to shell sessions opened after the change.)

  7. If you get an error message about MacOSX26.sdk not being found (or MacOSX14.sdk, or any other version, as long as it corresponds to the version of OSX you have installed), you can create that file. For example, if the message claims that /Library/Developer/CommandLineTools/SDKs/MacOSX26.sdk is not found, but you have /Library/Developer/CommandLineTools/SDKs/MacOSX.sdk (without the version 26 in the file name), then you create the missing file by running the following commands (adapt them to the version of the missing file):

    cd /Library/Developer/CommandLineTools/SDKs
    sudo ln -s MacOSX.sdk MacOSX26.sdk
    # your password will be prompted here
  8. If afl-fuzz complains about shmget() failing or other issues at startup, you may have to run:

    sudo afl-system-config

    before running afl-fuzz