💻 computer science

Cargo Sherlock: An SMT-Based Checker for Software Trust Costs

This paper introduces Cargo Sherlock, an SMT-based framework that quantifies software trust by formally combining metadata-driven human factors and code analysis to detect supply chain attacks in Rust dependencies.

Original authors: Muhammad Hassnain, Anirudh Basu, Ethan Ng, Caleb Stanford

Published 2026-02-04

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Muhammad Hassnain, Anirudh Basu, Ethan Ng, Caleb Stanford

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are building a house (your software project). To finish it, you need to buy bricks, windows, and doors from other people (third-party software libraries). Most of the time, you just grab the nearest box labeled "Brick" and hope it's good quality. But what if someone swapped the real bricks for fake ones filled with explosives? That's a supply chain attack.

The paper introduces a tool called Cargo Sherlock that helps you decide if those "bricks" are safe before you use them. Instead of just guessing, it acts like a super-organized detective who calculates a "Trust Cost" for every piece of software you want to use.

Here is how it works, broken down into simple concepts:

1. The "Trust Cost" Analogy

Think of trusting a piece of software like taking out a loan.

Low Trust Cost: You trust the software easily. Maybe it's from a famous builder (a well-known author), or it has been inspected by a certified inspector (an audit). You are willing to "pay" a low cost to believe it's safe.
High Trust Cost: You have to stretch your imagination to believe it's safe. Maybe the author is a stranger, the software has never been audited, or it has very few downloads. To believe it's safe, you have to make a huge leap of faith. That "leap" costs a lot.

Cargo Sherlock's job is to find the cheapest way to convince yourself that a piece of software is safe. If the cheapest way to believe it is safe still costs a fortune (a high number), the tool tells you: "Hey, this is risky. Don't use it."

2. How the Detective Solves the Puzzle

The tool uses a mathematical logic engine (called SMT) to solve a puzzle. Imagine you have a list of clues (assumptions) you can use to prove a library is safe:

Clue A: "It has 1 million downloads." (Cost: Low, because popularity usually means safety).
Clue B: "It was audited by Google." (Cost: Very Low, because Google is trusted).
Clue C: "The author is a random person with no history." (Cost: High, because it's a big risk).

The tool looks at all the dependencies (the software's own "ingredients") and tries to build a chain of logic. It asks: "What is the cheapest combination of clues that proves this code is safe?"

Scenario 1 (Safe): A popular library has 1 million downloads. The tool says, "Okay, Clue A is enough. The total cost is low. Verdict: SAFE."
Scenario 2 (Dangerous): A suspicious library has no downloads, a new author, and no audits. The tool tries to find a cheap clue but can't. The only way to prove it's safe is to assume "It's safe for no reason," which has a massive cost. Verdict: CRITICAL RISK.

3. The "Human Factor"

Usually, computers only look at code. But humans trust things based on reputation, download counts, and audits. Cargo Sherlock is special because it mixes math with human intuition.

It lets you set the rules. You can say, "I trust audits from Company X more than Company Y," or "I don't trust code with too many downloads because it might be a bot farm."
It makes these human feelings auditable. Instead of a black box saying "Trust Level: 85%," it says, "We trust this because it passed an audit by Google (Cost: 5) and has many downloads (Cost: 10)."

4. What the Tool Found (The Results)

The authors tested Cargo Sherlock on real and fake scenarios:

Typosquatting (Fake Names): Attackers often create fake libraries with names that look almost like real ones (e.g., serde_yml instead of serde_yaml). When the tool checked these fakes, the "Trust Cost" skyrocketed because the authors were unknown and the downloads were suspiciously low. The tool correctly flagged them as dangerous.
AI-Generated Code: They tested a library maintained by AI that had low-quality code. The tool gave it a higher risk score than the original human-maintained version because the "author" changed and the code quality dropped.
Known Vulnerabilities: The tool found that even some libraries listed as "vulnerable" by other databases still looked "safe" to Cargo Sherlock if they were very popular. This is a warning: Popularity doesn't always mean safety.

5. Speed and Scale

The tool has two ways of solving the puzzle:

The Slow Way: Tries every possible combination. It works for small projects but gets stuck on big ones.
The Fast Way: Uses a smart shortcut (Horn Clauses) that works like a super-efficient detective. It can handle libraries with hundreds of dependencies without crashing, giving results in minutes.

Summary

Cargo Sherlock is a tool for software developers that turns the vague feeling of "Does this look safe?" into a concrete number. It calculates the minimum price you have to pay in trust to believe a piece of software is safe. If that price is too high, it warns you to stay away, helping prevent supply chain attacks before they happen.

Note: The paper explicitly states this tool is for the Rust programming language ecosystem (libraries called "crates").

Technical Summary: Cargo Sherlock

Problem Statement

Software supply chain attacks, such as the SolarWinds incident, the XZ Utils backdoor, and malicious Rust libraries like rustdecimal and faster_log, pose significant threats to open-source ecosystems. Existing detection methods fall into two categories:

Formally Checkable Tools: Static analysis, fuzzing, and type systems that provide concrete syntactic or semantic guarantees but are often limited to specific program properties.
Human-Centric Trust: Industry practices relying on heuristics like download counts, author reputation, and manual audits. While practical, these lack formal guarantees, making it difficult to understand how trust assumptions compose or to formally verify the reasoning behind trusting a dependency.

The core problem addressed is the lack of a framework that can quantify trust in a formally checkable manner while incorporating human factors (e.g., metadata, audit history) that developers actually rely on. The authors aim to create a system where trust is specific, auditable, configurable, and composable.

Methodology

The paper proposes Cargo Sherlock, a tool for quantifying supply chain trust in Rust libraries (crates) using Satisfiability Modulo Theories (SMT). The approach is built on the Minimum Trust Problem.

The Minimum Trust Problem

The authors formalize trust as a logical optimization problem:

Inputs: A set of candidate assumptions ( $\Gamma$ ) about a software dependency (e.g., "if the crate has many downloads, it is safe"), a conclusion ( $c$ , e.g., "the crate is safe"), and a cost function ( $C$ ) assigning a cost to each assumption.
Goal: Find a subset of assumptions $\Delta \subseteq \Gamma$ such that $\Delta$ logically entails $c$ ( $\Delta \models c$ ) and the sum of costs in $\Delta$ is minimized.
Interpretation: A lower "trust cost" implies a stronger, more justifiable argument for safety based on the user's configured assumptions. Higher costs indicate riskier code requiring more "faith" to trust.

Algorithms

Two algorithms are proposed to solve the Minimum Trust Problem:

Naive Algorithm (Algorithm 1): Encodes the problem using quantifiers over propositional variables and linear integer arithmetic. It recursively constructs a formula representing the dependency tree and uses an SMT solver to find the minimum cost. This approach is correct but computationally expensive due to nested quantifiers.
Horn Clause Algorithm (Algorithm 2): Restricts assumptions to acyclic definite Horn clauses. It uses an unfolding procedure (similar to SLD resolution) to transform the problem into a Disjunctive Normal Form (DNF) formula. It then employs a binary search over the cost space using quantifier-free SMT queries. While the generated formula can be exponential in the worst case, this approach is significantly more efficient in practice.

Complexity: The general Minimum Trust Problem is shown to be $\Sigma^P_2$ -hard. The restriction to Horn clauses (HORN-MINTRUST) is proven to be NP-complete, justifying the use of SMT solvers.

Implementation and Design

Cargo Sherlock is a Python-based tool that integrates:

Data Collection: Aggregates metadata from crates.io (downloads, stars, authors), GitHub, RustSec (vulnerabilities), Cargo Vet (audit reports), and static analysis tools (Miri, Cargo Scan).
Relational Model: Organizes data into entities (Crates, Authors, Audits, Dependencies, Tool Results).
Assumption Types:
- Positive: Justifications for safety (e.g., trusted author, passed audit, no side effects).
- Negative: Justifications for distrust (e.g., presence in RustSec, flagged by Miri).
- Parameterized: Costs that vary continuously based on metadata (e.g., number of downloads).
Output: Computes a Trust Cost and a Distrust Cost (0–100 scale). These are combined to produce a severity label (Safe, Low/Medium/High Severity, Critical).

Key Contributions

Formal Model: A formalization of the supply chain trust problem as a Minimum Trust Problem solvable via SMT, satisfying requirements for specificity, auditability, configurability, and composability.
Algorithms: Two algorithms for solving the problem, including an optimized Horn-clause-based approach that handles large dependency trees more effectively than the naive quantifier-based method.
Tool Implementation: A working prototype (Cargo Sherlock) for Rust that integrates real-world metadata and program analysis results to compute trust costs.
Evaluation: An empirical study demonstrating the tool's ability to detect synthetic and real-world supply chain attacks and its scalability.

Evaluation Results

The authors evaluated Cargo Sherlock on four research questions:

RQ1 (Synthetic Typosquatting): When tested on synthetic typosquatting variants of the top 100 Rust crates, the tool assigned significantly higher trust costs and severity labels (often "Critical") compared to the original, safe crates. Most original crates were labeled "Safe," while typosquats were flagged as risky due to lower download counts and untrusted authors.
RQ2 (Real-World Incidents):
- faster_log: A malicious typosquat of fast_log. Cargo Sherlock correctly assigned a "Critical" label (Trust: 75, Distrust: 80) compared to the original's "Medium Severity" (Trust: 37, Distrust: 73), driven by the untrusted author and side effects.
- serde_yml: An AI-maintained fork of serde_yaml. The tool assigned a "Low Severity" label to the fork (vs. "Safe" for the original), primarily due to the change in authorship, despite similar distrust costs.
RQ3 (Known Vulnerabilities): When tested against 592 crates listed in the RustSec database (with RustSec-specific assumptions disabled), many were still labeled "Safe" or "Low Severity." This indicates that popularity (high download counts) can mask known vulnerabilities in the trust model, suggesting users might perceive vulnerable crates as safe if they rely solely on popularity metrics.
RQ4 (Scalability):
- Algorithm 1: Failed to scale, timing out or crashing on crates with more than ~10 dependencies.
- Algorithm 2: Successfully evaluated crates with up to 150 dependencies within a 10-minute window, demonstrating practical scalability for most real-world scenarios.

Significance and Claims

The paper claims that Cargo Sherlock provides a formally checkable framework for quantifying software trust that bridges the gap between rigorous formal methods and the heuristic-based practices of industry developers.

Specificity: Unlike black-box machine learning approaches, Cargo Sherlock produces a specific set of assumptions (e.g., "trusted by Alice," "high downloads") that justify the trust cost, making the reasoning auditable.
Configurability: Users can adjust the costs of assumptions (e.g., penalizing AI-maintained code or rewarding specific auditors) to align with their risk tolerance.
Composability: The model allows trust costs to be composed across dependency trees, enabling a holistic view of supply chain risk.

The authors conclude that while the tool effectively identifies risky dependencies (like typosquats and untrusted forks), it also highlights the limitations of current trust metrics: popular crates with high download counts may still harbor vulnerabilities that the tool might classify as "Safe" if the specific vulnerability is not explicitly modeled in the assumptions. The tool is open-source and available for use in Rust development workflows.