Yet Another Pointer Analysis for LLVM

Yapall is a precise and scalable pointer analysis for LLVM. The output of Yapall can be used for a variety of program analysis tasks, including:

  • Creation of callgraphs with precise handling of indirect function calls and virtual method calls
  • Precise inter-procedural control- and data-flow analysis
  • Answering may-alias queries

Yapall is k-callsite sensitive for configurable k, field-, array-, and flow-insensitive, and performs on-the-fly callgraph construction. Yapall is written using Ascent and so is highly parallel.

Bibliography

To understand Yapall and how it works, you may want to review:

  • The pointer analysis tutorial of Smaragdakis and Balatsouras

  • Bravenboer, M. and Smaragdakis, Y., 2009, October. Strictly declarative specification of sophisticated points-to analyses. In Proceedings of the 24th ACM SIGPLAN conference on Object oriented programming systems languages and applications (pp. 243-262).

  • Balatsouras, G. and Smaragdakis, Y., 2016, September. Structure-sensitive points-to analysis for C and C++. In International Static Analysis Symposium (pp. 84-104). Springer, Berlin, Heidelberg.

Contributing

Thank you for your interest in Yapall! We welcome and appreciate all kinds of contributions. Please feel free to file and issue or open a pull request.

You may want to take a look at:

If you have questions, please ask them on the discussions page!

Installation

Pre-compiled binaries

Pre-compiled binaries are available on the releases page.

Fetching binaries with cURL

You can download binaries with curl like so (replace X.Y.Z with a real version number and TARGET with your OS):

curl -sSL https://github.com/GaloisInc/yapall/releases/download/vX.Y.Z/yapall_TARGET -o yapall

Build from source

To install from source, you'll need to install Rust and Cargo. Follow the instructions on the Rust installation page.

From the latest unreleased version on Github

To build and install the very latest unreleased version, run:

cargo install --git https://github.com/GaloisInc/yapall.git yapall

From a local checkout

See the developer's guide.

Usage

First, compile a program to LLVM bitcode:

clang -emit-llvm -O1 -c -fno-discard-value-names tests/pointer/soundness/alloca.c

Then, run yapall:

yapall --signatures signatures.json alloca.bc

Developer's guide

Build

To install from source, you'll need to install Rust and Cargo. Follow the instructions on the Rust installation page.

You'll also need the version of LLVM specified in the llvm-ir dependency in Cargo.toml (LLVM 14, at the time of writing).1 Follow the instructions on building llvm-sys to make it available to Cargo.

Then, get the source:

git clone https://github.com/GaloisInc/yapall
cd yapall

Finally, build everything:

cargo build --release

You can find binaries in target/release. Run tests with cargo test.

1

When run from the repository root, this command will show you the exact version: cargo read-manifest | jq '.dependencies|.[]|select(.name|contains("llvm"))|.features|.[0]'.

Example: Debian "bookworm"

Here's an end-to-end sequence of commands that installs the build and test dependencies of yapall on Debian bookworm:

apt-get update
UBUNTU_NAME="bookworm"
LLVM_MAJOR_VERSION="14"
wget -O - https://apt.llvm.org/llvm-snapshot.gpg.key | apt-key add -
echo "deb http://apt.llvm.org/${UBUNTU_NAME}/ llvm-toolchain-${UBUNTU_NAME}-${LLVM_MAJOR_VERSION} main" | tee /etc/apt/sources.list.d/llvm.list
apt-get -y install --no-install-recommends llvm-${LLVM_MAJOR_VERSION} llvm-${LLVM_MAJOR_VERSION}-dev
apt-get install libpolly-14-dev
apt-get -y install clang-${LLVM_MAJOR_VERSION}
apt-get -y install clang++-${LLVM_MAJOR_VERSION}

Features

See Cargo.toml for various build features. par enables parallel Ascent.

PGO

First, build a benchmark program. You'll want this to be as large as possible, but still small enough to be handled context-sensitively. For example:

clang++ -emit-llvm -O1 -c -fno-discard-value-names tests/medium/jackson.cpp

Then, build the instrumented binary:

cargo install cargo-pgo
rustup component add llvm-tools-preview
cargo pgo build

Collect data:

target/x86_64-unknown-linux-gnu/release/yapall --contexts 3 --quiet jackson.bc

Finally, build and install the optimized binary:

cargo pgo optimize
mv target/x86_64-unknown-linux-gnu/release/yapall /wherever

Docs

HTML documentation can be built with mdBook:

cd doc
mdbook build

Format

All code should be formatted with rustfmt. You can install rustfmt with rustup like so:

rustup component add rustfmt

and then run it like this:

cargo fmt

Lint

All code should pass Clippy. You can install Clippy with rustup like so:

rustup component add clippy

and then run it like this:

cargo clippy --workspace -- --deny warnings

Profile

Counts

To see cumulative time taken by each rule:

cargo install counts
cargo run --quiet --release -- --quiet --tracing --signatures signatures.json irving.bc 2> /tmp/nanos
counts -i -e /tmp/nanos

(You may also want to try with cargo run --features par.)

To see cumulative tuples generated by each rule:

cargo install counts
cargo run --quiet --release --features count -- --quiet --signatures signatures.json irving.bc 2> /tmp/nanos
counts -i -e /tmp/nanos

dhat

cargo build -q --release --features dhat-heap
./target/release/yapall --quiet --signatures signatures.json jackson.bc

Then, go to https://nnethercote.github.io/dh_view/dh_view.html to upload dhat-heap.json.

perf

cargo build -q --release
perf record ./target/release/yapall --signatures signatures.json jackson.bc

Poor Man's Profiler

cargo build -q --release
./target/release/yapall --signatures signatures.json jackson.bc &
./scripts/poor-mans-profiler.sh 10 > prof.txt

Samply

cargo install samply
cargo build --profile=profiling
samply record ./target/release/yapall --signatures signatures.json jackson.bc

Test

Running cargo test checks whether the pointer analysis correctly handles various LLVM features. Running lit tests/pointer/soundness checks whether the C test programs are compiling to the intended LLVM bitcode.

Warnings

Certain warnings are disallowed in the CI build. You can reproduce the behavior of the CI build by running cargo check, cargo build, or cargo test like so:

env RUSTFLAGS="@$PWD/rustc-flags" cargo check

Using a flag file for this purpose achieves several objectives:

  • It frictionlessly allows code with warnings during local development
  • It makes it easy to reproduce the CI build process locally
  • It makes it easy to maintain the list of warnings
  • It maintains forward-compatibility with future rustc warnings
  • It ensures the flags are consistent across all crates in the project

This flag file rejects all rustc warnings by default, as well as a subset of allowed-by-default lints. The goal is to balance high-quality, maintainable code with not annoying developers.

To allow a lint in one spot, use:

#![allow(unused)]
fn main() {
#[allow(name_of_lint)]
}

To enable these warnings on a semi-permanent basis, create a [Cargo configuration file][cargo-conf]:

mkdir .cargo
printf "[build]\nrustflags = [\"@${PWD}/rustc-flags\"]\n" > .cargo/config.toml