Cargo Sherlock

An SMT-based checker for software trust in the Rust supply chain — formalizing the "minimum trust problem", evaluated on synthetic typosquats and known real incidents on crates.io.

FormaliSE ’26 · ACM · DOI 10.1145/3793656.3793687

Cargo Sherlock

An SMT-based checker that quantifies trust in Rust crates by combining program-analysis results with the metadata developers already rely on (downloads, authors, audits, stars). We formalize the minimum trust problem; Cargo Sherlock combines a trust cost and a distrust cost into a severity label.

Muhammad Hassnain1 · Anirudh Basu1 · Ethan Ng1 · Caleb Stanford1

1University of California, Davis

Numbers

At a Glance

2
Algorithms
naive SMT encoding and a Horn-clause algorithm, solved with Z3
3
Kinds of Assumptions
positive · negative · parameterized, each with a user-configurable cost
100
Synthetic Typosquats
all labelled riskier than the original, except those with no side effects and only safe dependencies (labelled SAFE)
2
Real Incidents
faster_log and serde_yml both labelled higher than the originals
150+
Scalability
scales to crates with over 150 dependencies within 10 minutes

Abstract

Overview

Supply-chain attacks threaten open-source software ecosystems. This paper proposes a formal framework for quantifying trust in third-party software dependencies that is both formally checkable — formalized in satisfiability modulo theories (SMT) — and incorporates human factors like the number of downloads, the number of authors, and other metadata developers already use to identify trustworthy software in practice.

We use data from both software-analysis tools and metadata to build a first-order relational model of software dependencies. To obtain an overall trust cost combining these factors, we propose a formalization based on the minimum trust problem, which asks for the minimum-cost set of assumptions that can be used to prove that the code is safe.

We implement these ideas in Cargo Sherlock, targeted for Rust libraries (crates), incorporating a list of candidate assumptions motivated by quantifiable trust metrics identified in prior work. Our evaluation shows that Cargo Sherlock can be used to identify synthetically generated supply-chain attacks and known incidents involving typosquatted and poorly AI-maintained crates, and that its performance scales to Rust crates with many dependencies.

Framework

The Minimum Trust Problem

1

Candidate assumptions

Each assumption is a reason a developer might give for trusting a crate, with a cost. Positive: trusted author, passed audit, no side effects with safe dependencies. Negative (for distrust): listed in RustSec, flagged by Miri, unsafe dependency. Parameterized: cost varies smoothly with downloads, GitHub stars/forks, or number of side effects. Assumptions are not necessarily true facts; they are the arguments users actually make.

2

Logical encoding

Assumptions are propositional formulas (e.g. “if the crate has many downloads, it is safe”), and the conclusion is fixed: the library is safe. Dependencies compose: a crate’s assumptions can depend on its dependencies being safe.

3

Minimum-cost assumption set

Find the cheapest subset of assumptions that entails the conclusion; its total cost is the trust cost. Algorithm 1 encodes this with quantifiers over linear integer arithmetic; Algorithm 2 restricts to acyclic Horn clauses and uses quantifier-free SMT queries.

4

Distrust and severity

A separate distrust model computes the cheapest argument that the crate is unsafe. The final severity label (SAFE … CRITICAL) combines both: lower trust cost and higher distrust cost are better.

5

Complexity

The general problem (MINTRUST) is Σ2P-hard; the Horn-clause restriction (HORN-MINTRUST) is NP-complete — intractable in general, but within reach of SMT solvers.

Pipeline

How Cargo Sherlock Checks a Crate

High-level overview of Cargo Sherlock: inputs from crates.io, GitHub, RustSec, audit reports and static analysis tools flow into Cargo Sherlock and a relational model; a consistency checker takes user-provided costs; trust and distrust models solve for minimum costs; a synthesizer combines them into a list of assumptions and a trust cost.
Figure 2 from the paper — high-level overview of Cargo Sherlock.

Cargo Sherlock collects data from crates.io, GitHub, Cargo Vet audit reports, RustSec, and analysis tools (Miri, Cargo Scan) into a relational model. The user supplies assumption costs (defaults are provided), and a consistency checker validates them. A trust model and a distrust model each use Z3 to find their minimum-cost assumption set, and a synthesizer combines them into the assumptions, costs, and severity label shown to the user.

Data model

The Underlying Entity-Relationship Model

Entity-relationship diagram: a crate has git data, name, version and downloads, and has tool results, audits, authors and dependencies; audits contain organization, criteria, version, delta and notes; authors have a name and trust label.
Figure 3 from the paper — Cargo Sherlock entity-relationship (ER) model.

The primary entities are Crates, Authors, Audits, Dependencies and Tool Results; name, version, downloads and git data (stars, forks) are crate attributes. This model is the data layer: candidate assumptions are instantiated over it, then handed to the solver.

Example output

What a Cargo Sherlock Report Looks Like

Cargo Sherlock example output on the anyhow crate: trust cost 5 (low, green), distrust cost 71 (high, red), label SAFE, with the assumptions for trusting listed in green and assumptions for distrusting listed in red.
Figure 1 from the paper — Cargo Sherlock example output on anyhow-1.0.97. Lower trust cost is better; higher distrust cost is better.

Results

Evaluation

Research question Setup Result
RQ1 Synthetic typosquats Typosquatted copies of the 100 most-downloaded crates: name and author changed, code unchanged, downloads set to 171 Originals: 73% SAFE, none above LOW_SEVERITY. Typosquats: 72 CRITICAL, 3 HIGH, but 25 still SAFE (no side effects, safe dependencies). Label rose in all other cases.
RQ2 Malicious typosquat faster_log, a typosquat of fast_log that exfiltrates private keys from log files fast_log: MEDIUM_SEVERITY (trust 37, distrust 73). faster_log: CRITICAL (trust 75, distrust 80).
RQ2 AI-maintained fork serde_yml, a fork of the unmaintained serde_yaml with substantial AI-generated code serde_yaml: SAFE (6 / 70). serde_yml: LOW_SEVERITY (32 / 70), driven mainly by the change in authorship.
RQ3 Known vulnerable crates 592 crate-version pairs from RustSec, with RustSec-based assumptions removed Most labelled SAFE or LOW_SEVERITY. Vulnerable crates tend to be popular (~75% are in the top 10% by downloads), so SAFE does not mean vulnerability-free.
RQ4 Scalability 953 random crates from crates.io, 600 s timeout Algorithm 1: 298 succeeded, 500 timed out, 155 crashed; infeasible beyond ~10 dependencies. Algorithm 2: 900 succeeded, 48 timed out, 5 crashed; scales to ~150 dependencies. Runtime grows exponentially.

Takeaway. Under the paper’s “rational developer” user model, Cargo Sherlock’s labels would steer a user away from most of the synthetic typosquats and from both real incidents studied. It is not a vulnerability detector: known-vulnerable crates that are popular are often labelled SAFE. Every result is explainable — the tool prints the assumptions behind each cost, so a reviewer can see why a crate got its label and adjust costs they disagree with.

Fun fact

Why "Sherlock"?

The project was originally called RHS — “Right Hand Side” — because when the group was brainstorming projects, there were two on the whiteboard: one on the left side (“LHS”) and one on the right (“RHS”). The names stuck. We briefly considered Rust Holmes Sherlock to keep the acronym; the detective ended up in the name but the acronym did not survive.

Cite

BibTeX

@inproceedings{Hassnain2026CargoSherlock,
  author    = {Hassnain, Muhammad and Basu, Anirudh and
               Ng, Ethan and Stanford, Caleb},
  title     = {Cargo Sherlock: An SMT-Based Checker for
               Software Trust Costs},
  year      = {2026},
  publisher = {Association for Computing Machinery},
  address   = {New York, NY, USA},
  url       = {https://doi.org/10.1145/3793656.3793687},
  doi       = {10.1145/3793656.3793687},
  booktitle = {Proceedings of the IEEE/ACM 14th International
               Conference on Formal Methods in Software Engineering},
  pages     = {1--12},
  numpages  = {12},
  location  = {Rio de Janeiro, Brazil},
  series    = {FormaliSE '26},
}