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.
1University of California, Davis
Numbers
At a Glance
faster_log and serde_yml both labelled higher than the originalsAbstract
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
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.
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.
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.
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.
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
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
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
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},
}