galoisinc / yapall

A precise and scalable pointer analysis for LLVM, written in Ascent

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.

For more information, see the documentation.

Acknowledgments

This material is based upon work supported by the Defense Advanced Research Projects Agency (DARPA) under Contract No. N66001-21-C-4023. Any opinions, findings and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of DARPA.

Distribution

DISTRIBUTION STATEMENT A. Approved for public release: distribution unlimited.

yapall's Issues

Compute byte offsets of GEPs

On the Irving example, 65% of GEPs have all-constant indices. On Jackson, it's 93%. With information about type sizes, these GEPs can be translated into byte-offsets. Given information about allocation sizes, we can then discard points-to facts that would involve adding offsets that go beyond the end of allocations, or even go so far as #36. This would improve both performance and precision. This would require work upstream in the llvm-ir crate to reproduce LLVM's type-size computations.

admin: Publish v0.1

Requires #5, #15.

ci: Build docs

ci: Build Nix flake in CI

If it takes much longer than the normal build, perhaps we could run it just on the main branch.

Rust tests failing with LLVM version mismatch regarding opaque pointers

yapall> error: Opaque pointers are only supported in -opaque-pointers mode (Producer: 'LLVM15.0.7' Reader: 'LLVM 14.0.6')
yapall> error: test failed, to rerun pass `--test pointer`

(See https://github.com/GaloisInc/yapall/actions/runs/6029699696/job/16359835202?pr=47#step:5:950 or https://github.com/GaloisInc/yapall/actions/runs/6030069826/job/16361088971?pr=50)

This is a specific instance of the general issues noted by #46

ci: Run tests

Requires #1.

build: Switch to a crates.io release of Ascent

Waiting on s-arash/ascent#17

Simplify span-duration-counting tracing layer

Here's a simpler implementation of NanoCountLayer:

use std::time::{Duration, SystemTime};

use tracing::{debug, Id, Subscriber};
use tracing_subscriber::{layer::Context, registry::LookupSpan, Layer};

#[derive(Debug, Default)]
pub(crate) struct MilliCountLayer;

impl<S> Layer<S> for MilliCountLayer
where
    S: Subscriber + for<'lookup> LookupSpan<'lookup>,
{
    fn on_enter(&self, id: &Id, ctx: Context<'_, S>) {
        if let Some(span) = ctx.span(id) {
            span.extensions_mut().insert(SystemTime::now());
        }
    }

    fn on_exit(&self, id: &Id, ctx: Context<'_, S>) {
        if let Some(span) = ctx.span(id) {
            if let Some(time) = span.extensions().get::<SystemTime>() {
                let elapsed = time.elapsed().unwrap_or(Duration::ZERO);
                debug!("{}: {}ms", span.name(), elapsed.as_millis())
            }
        }
    }
}

Consider linking C++ programs against libc++ bitcode

... as a way to achieve soundness without writing many signatures. Crux does this, we can take inspiration from them.

tests: undef.c no longer produces an `undef` constant

This test was used to demonstrate proper handling of the undef constant, but it no longer seems to generate one.

nix: Fix tests in Nix flake

It's my impression that the Nix flake can't yet successfully run the test suite. We should investigate this further.

doc: Section on contributing

build: Update dependencies

With dependabot, or cargo update.

nix: Run tests with `lit`

As described here.

irving_precision test failing

The irving_precision test is failing (see https://github.com/GaloisInc/yapall/actions/runs/6029699696/job/16359835202?pr=47#step:5:960). This is a specific instance of the general failures noted in #46.

Offset-based memory model

Right now, a pointer stored to a single, concrete field of a struct or index in an array will be retrieved in a load from any field or index. We should instead adopt a memory model that separates these. This would involve:

• For each GEP expression and instruction with all concrete indices, calculating the offset added to the base pointer
• For each (basic) allocation a, a new allocation a[*] which represents loads/stores at an unknown offset
• "Sub-allocations" a[n] for concrete offsets n that have been calculated via GEPs - though care must be taken such that there is only a bounded number of such suballocations.
• Rules relating loads and stores from the a[n] and a[*]

This would be a significant undertaking, and would require #37.

ci: Run rustfmt, clippy

Investigate test `sig_arg_memcpy_arg_o0`

yapall/tests/pointer.rs

Lines 992 to 995 in 282ac3e

	// XFAIL(TODO)
	#[test]
	#[should_panic(expected = "Bug!")]
	fn sig_arg_memcpy_arg_o0() {

doc: Installation from source from Github using `cargo`

Model varargs

yapall/tests/pointer.rs

Lines 1652 to 1665 in 282ac3e

	// XFAIL(TODO): Can't handle exceptions yet
	#[test]
	#[should_panic(expected = "assertion failed: points_to_something")]
	fn varargs_o1() {
	let module = sound("varargs.c", 1);
	let _out = check(&module);
	}
	#[test]
	#[should_panic(expected = "assertion failed: points_to_something")]
	fn varargs_o2() {
	let module = sound("varargs.c", 2);
	let _out = check(&module);
	}

rustc version support policy (MSRV)

What are the intentions for supporting versions of rustc (i.e. what version range is intended)? I'm asking because the CI here uses nixpkgs-unstable, but I have another project which includes yapall and builds against nixos-23.05, and the latter provides rustc 1.69.0. The latest dependabot changes caused updates that are no longer compatible with that version of rustc:

yapall> configuring
yapall> building
yapall> Executing cargoBuildHook
yapall> ++ env CC_x86_64-unknown-linux-gnu=/nix/store/7wkshj58fcsl1f3zyi67qsxgl1p8nki1-gcc-wrapper-12.2.0/bin/cc CXX_x86_64-unknown-linux-gnu=/nix/store/7wkshj58fcsl1f3zyi67qsxgl1p8nki1-gcc-wrapper-12.2.0/bin/c++ CC_x86_64-unknown-linux-gnu=/nix/store/7wkshj58fcsl1f3zyi67qsxgl1p8nki1-gcc-wrapper-12.2.0/bin/cc CXX_x86_64-unknown-linux-gnu=/nix/store/7wkshj58fcsl1f3zyi67qsxgl1p8nki1-gcc-wrapper-12.2.0/bin/c++ cargo build -j 8 --target x86_64-unknown-linux-gnu --frozen --release
yapall> error: package `clap_derive v4.4.0` cannot be built because it requires rustc 1.70.0 or newer, while the currently active rustc version is 1.69.0
yapall> Either upgrade to rustc 1.70.0 or newer, or use
yapall> cargo update -p [email protected] --precise ver
yapall> where `ver` is the latest version of `clap_derive` supporting rustc 1.69.0
error: builder for '/nix/store/q9wlw6i02ms08p57i9bapg5l9l8rzblh-yapall-0.0.0.drv' failed with exit code 101

For that project, I am not building other rust packages so I can update, but it would be good to be intentional about which versions of rustc are intended to be supported and ensure the CI validates that version range.

ci: Host docs on Github pages

Requires #2.

doc: Building from source requires LLVM

This should be documented.

feat: Export results as CSV

The yapall binary should (by default) export analysis results in CSV format using the csv crate.

doc: CHANGELOG

doc: Link to OOPSLA paper

admin: Protect main branch

Requires #1.

doc: Installation from pre-compiled binaries

Requires #5.

ci: Release workflow

Should build binaries. Note to self: remove -march=native from rustc-flags.

Investigate test `template_vec_o0`

yapall/tests/pointer.rs

Lines 1552 to 1555 in 282ac3e

	// XFAIL(TODO)
	#[test]
	#[should_panic(expected = "assertion failed: points_to_something")]
	fn template_vec_o0() {

build: Switch to a Github release of llvm-ir

ci: Run tests with `lit`

As described here.

Model LLVM exception handling (for C++)

doc: Describe signatures

doc: Code of conduct

ci: Build