llvm-ub-aware-interpreter (llubi)

UB-aware interpreter for LLVM debugging

Introduction

This tool is developed to save my life when debugging LLVM. Unlike lli, this interpreter is UB-aware, which means it will check immediate undefined behaviors during the execution and handle poison values properly. It is designed to be a debugging tool, so it is not optimized for performance. alive-exec should be a drop-in replacement of this tool. But it is slow and easy to get stuck in my experience. So this tool is designed to be more friendly to csmith and creduce.

Motivation

We have suffered from incorrect poison-generating/UB-implying annotations in LLVM for a long time. The most common mistake is that we forget to drop annotations after replacing one of its operands in place. In most cases, this kind of bugs will not be caught by end-to-end tests or real-world applications. But they will finally emerge when we do some aggressive optimizations with these incorrect annotations. With this interpreter, we can easily find out the incorrect annotations handling and fix them.

Here is an incomplete list of this kind of bugs:

• llvm/llvm-project#115976
• llvm/llvm-project#115890
• llvm/llvm-project#114879
• llvm/llvm-project#113997
• llvm/llvm-project#112666
• llvm/llvm-project#112476
• llvm/llvm-project#112356
• llvm/llvm-project#112350
• llvm/llvm-project#112078
• llvm/llvm-project#112076
• llvm/llvm-project#112068
• llvm/llvm-project#111934
• llvm/llvm-project#99436
• llvm/llvm-project#91691
• llvm/llvm-project#91178
• llvm/llvm-project#91127
• llvm/llvm-project#90380
• llvm/llvm-project#87042
• llvm/llvm-project#85536
• llvm/llvm-project#78621

Getting Started

git clone https://github.com/dtcxzyw/llvm-ub-aware-interpreter
cd llvm-ub-aware-interpreter
mkdir -p build && cd build
cmake .. -GNinja -DCMAKE_BUILD_TYPE=Release -DLLVM_DIR=/path/to/llvm/lib/cmake/llvm
cmake --build . -j
./llubi test.ll [--verbose]

Automatic UB-Free Test Case Reduction for Middle-End Miscompilation Bugs

test.sh:

#!/usr/bin/bash

MAX_STEPS=1000000
a=$(<path to llubi> --max-steps $MAX_STEPS --reduce-mode $1)
if [ $? -ne 0 ]; then
    exit 1
fi
<path to opt> <options> $1 -o $1.tmp
if [ $? -ne 0 ]; then
    exit 1
fi
b=$(<path to llubi> --max-steps $MAX_STEPS --reduce-mode $1.tmp)
if [ $? -ne 0 ]; then
    rm $1.tmp
    exit 0
fi
if [[ $a == $b ]]; then
    rm $1.tmp
    exit 1
fi
rm $1.tmp
exit 0

Usage:

clang -O3 -Xclang -disable-llvm-passes -emit-llvm -S test.c -o test.ll
llvm-reduce --test=test.sh --ir-passes="function(sroa,instcombine<no-verify-fixpoint>,gvn,simplifycfg,infer-address-spaces),inline" test.ll

Fuzzing with Csmith

python3 csmith.py <llvm install dir> <csmith install dir> <path to llubi> <test count> [emi]

If emi is set, it will enable the EMI-based mutation. For more details, please refer to Compiler validation via equivalence modulo inputs, PLDI'21.

Notes

• Undef values are not supported as we will eventually remove undef from LLVM in the future. In llubi, they are treated as zero values.
• FFI is not supported. Currently it only supports printf("%d", x) for csmith.

TODO

• TBAA support
• lifetime/invariant support
• Fine-grained UB check control