server/lib/src/advisory_index.rs
//! **The CVE lookup as an index** (lane T10): `(ecosystem, package)` → the
//! advisories about that package, built once when the advisory set is loaded.
//!
//! modgunn's `OsvScanner::scan` answers every lookup with `AdvisoryDb::query`, a
//! linear filter over every advisory (270k for the real OSV dumps of PyPI, npm
//! and crates.io). This index buckets the advisory positions by the same
//! canonical key `Advisory::matches` compares (`canonical_eco`, `canonical_pkg`),
//! lower-cased, so a lookup reads one bucket.
//!
//! **Same answers, by construction.** The bucket only narrows the candidates:
//! every candidate is still confirmed by `Advisory::matches`, and the bucket keeps
//! the advisories in their original order. The lower-casing can only put MORE
//! advisories in a bucket than `matches` accepts (npm names are case-sensitive),
//! never fewer, so the result is exactly `AdvisoryDb::query`'s, in its order.
//! The verdict is then assembled by modgunn's own `Policy::assemble`, the same
//! call `OsvScanner::scan` makes.
use std::collections::HashMap;
use modgunn::scan::{canonical_eco, canonical_pkg};
use crate::security::{Advisory, AdvisoryDb, Artifact, ArtifactRef, OsvScanner, Verdict};
/// The `(ecosystem, package)` index over one [`AdvisoryDb`]. It holds positions
/// into that db, so it is only ever used beside the db it was built from
/// ([`IndexedOsvScanner`] keeps the two together).
#[derive(Debug, Clone, Default)]
pub struct AdvisoryIndex {
buckets: HashMap<(String, String), Vec<u32>>,
/// The canonical ecosystems with at least one advisory (H32-FAILCLOSED).
ecosystems: std::collections::HashSet<String>,
/// How many advisories the index was built over (a cheap mismatch guard).
len: usize,
}
fn key(ecosystem: &str, name: &str) -> (String, String) {
(
canonical_eco(ecosystem).to_ascii_lowercase(),
canonical_pkg(ecosystem, name).to_ascii_lowercase(),
)
}
impl AdvisoryIndex {
/// Build the index over `db` (one pass over the advisories).
pub fn build(db: &AdvisoryDb) -> Self {
let mut buckets: HashMap<(String, String), Vec<u32>> = HashMap::new();
for (i, adv) in db.advisories.iter().enumerate() {
buckets
.entry(key(&adv.ecosystem, &adv.package))
.or_default()
.push(i as u32);
}
let ecosystems = buckets.keys().map(|(e, _)| e.clone()).collect();
Self {
buckets,
ecosystems,
len: db.advisories.len(),
}
}
/// **Has the database any advisory for `ecosystem`?** A scan in an ecosystem with none
/// cannot judge (H32-FAILCLOSED); one with no advisory feed at all
/// ([`crate::promote::identity::NO_ADVISORY_ECOSYSTEM`]) wants none.
pub fn covers(&self, ecosystem: &str) -> bool {
!crate::promote::identity::has_advisory_ecosystem(ecosystem)
|| self
.ecosystems
.contains(&canonical_eco(ecosystem).to_ascii_lowercase())
}
/// The number of distinct `(ecosystem, package)` buckets.
pub fn bucket_count(&self) -> usize {
self.buckets.len()
}
/// The advisories in `db` affecting `artifact`: exactly `db.query(artifact)`,
/// in the same order. `db` must be the db this index was built over.
pub fn matching<'a>(&self, db: &'a AdvisoryDb, artifact: &ArtifactRef) -> Vec<&'a Advisory> {
if self.len != db.advisories.len() {
// Not the db this index was built over: answer the slow, right way.
return db.query(artifact);
}
match self.buckets.get(&key(&artifact.ecosystem, &artifact.name)) {
None => Vec::new(),
Some(idx) => idx
.iter()
.map(|&i| &db.advisories[i as usize])
.filter(|a| a.matches(artifact))
.collect(),
}
}
}
/// modgunn's [`OsvScanner`] with its advisories indexed: the same verdicts as
/// `OsvScanner::scan`, with the lookup reading one bucket.
#[derive(Debug, Clone)]
pub struct IndexedOsvScanner {
inner: OsvScanner,
index: AdvisoryIndex,
}
impl IndexedOsvScanner {
/// Index `inner`'s advisories once.
pub fn new(inner: OsvScanner) -> Self {
let index = AdvisoryIndex::build(&inner.advisories);
Self { inner, index }
}
/// The scanner behind the index (its policy and advisories).
pub fn scanner(&self) -> &OsvScanner {
&self.inner
}
/// The index.
pub fn index(&self) -> &AdvisoryIndex {
&self.index
}
/// The advisories affecting `artifact`, as `AdvisoryDb::query` gives them.
pub fn matching(&self, artifact: &ArtifactRef) -> Vec<&Advisory> {
self.index.matching(&self.inner.advisories, artifact)
}
/// Has the database any advisory for `ecosystem` ([`AdvisoryIndex::covers`])?
pub fn covers(&self, ecosystem: &str) -> bool {
self.index.covers(ecosystem)
}
/// The verdict `OsvScanner::scan` gives, through the index.
pub fn scan(&self, artifact: &Artifact) -> Verdict {
self.scan_waived(artifact, &[])
}
/// [`scan`](Self::scan) with `waived` advisories asserted `not_affected`
/// (HOL-VEX-WAIVER): modgunn's `Policy::vex_not_affected`, the matcher seam, for this
/// one verdict.
pub fn scan_waived(&self, artifact: &Artifact, waived: &[String]) -> Verdict {
let matched = self.matching(&artifact.artifact);
if waived.is_empty() {
return self
.inner
.policy
.assemble(&self.inner.advisories.rev, artifact, &matched);
}
let mut policy = self.inner.policy.clone();
policy.vex_not_affected.extend(waived.iter().cloned());
policy.assemble(&self.inner.advisories.rev, artifact, &matched)
}
}
#[cfg(test)]
mod tests {
use super::*;
use crate::security::{Policy, ScanEngine, Severity};
use modgunn::versions::RangeEvent;
fn adv(id: &str, eco: &str, pkg: &str, versions: &[&str]) -> Advisory {
Advisory::basic(
id,
eco,
pkg,
versions.iter().map(|v| v.to_string()).collect(),
Severity::High,
id,
)
}
/// Advisories that exercise every rule `Advisory::matches` has: the pip/pypi
/// fold, PEP 503 names, case-sensitive npm and cargo names, NuGet case folding,
/// exact versions, ranges, all-versions rows and a withdrawn row.
fn db() -> AdvisoryDb {
let mut withdrawn = adv("W-1", "npm", "lodash", &[]);
withdrawn.withdrawn = true;
AdvisoryDb::new(
"fixture",
vec![
adv("P-1", "pypi", "zope-interface", &["5.0"]),
adv("P-2", "PyPI", "Django", &["4.2.0"]),
adv("P-3", "pip", "requests", &[]),
adv("P-4", "pypi", "requests", &["2.31.0"]),
adv("N-1", "npm", "lodash", &["4.17.20"]),
adv("N-2", "npm", "Lodash", &["4.17.20"]),
withdrawn,
adv("N-3", "npm", "@scope/pkg", &[]),
adv("C-1", "cargo", "tokio", &[]).with_ranges(vec![
RangeEvent::Introduced("1.0.0".into()),
RangeEvent::Fixed("1.18.4".into()),
]),
adv("C-2", "cargo", "Tokio", &[]),
adv("G-1", "nuget", "Newtonsoft.Json", &["12.0.1"]),
adv("M-1", "maven", "org.example:lib", &["1.0"]),
adv("P-5", "pypi", "requests", &["2.32.3"]),
],
)
}
fn artifact(eco: &str, name: &str, ver: &str) -> ArtifactRef {
ArtifactRef {
ecosystem: eco.into(),
name: name.into(),
version: ver.into(),
blob_sha256: "00".into(),
}
}
fn ids(v: &[&Advisory]) -> Vec<String> {
v.iter().map(|a| a.id.clone()).collect()
}
#[test]
fn the_index_gives_the_advisories_the_linear_scan_gives_in_its_order() {
let db = db();
let index = AdvisoryIndex::build(&db);
let cases = [
("pypi", "zope.interface", "5.0"),
("pip", "Zope_Interface", "5.0"),
("pip", "django", "4.2.0"),
("pypi", "DJANGO", "4.2.0"),
("pip", "requests", "2.31.0"),
("pip", "requests", "2.32.3"),
("pypi", "Requests", "1.0"),
("npm", "lodash", "4.17.20"),
("npm", "Lodash", "4.17.20"),
("npm", "LODASH", "4.17.20"),
("npm", "lodash", "4.17.21"),
("npm", "@scope/pkg", "0.0.1"),
("cargo", "tokio", "1.18.0"),
("cargo", "tokio", "1.18.4"),
("cargo", "Tokio", "9.9.9"),
("nuget", "newtonsoft.json", "12.0.1"),
("nuget", "Newtonsoft.Json", "12.0.1"),
("maven", "org.example:lib", "1.0"),
("maven", "org.example:LIB", "1.0"),
("npm", "requests", "2.31.0"),
("cargo", "absent", "1.0"),
("", "", ""),
];
let mut hits = 0;
for (eco, name, ver) in cases {
let a = artifact(eco, name, ver);
let linear = ids(&db.query(&a));
let indexed = ids(&index.matching(&db, &a));
assert_eq!(indexed, linear, "{eco} {name} {ver}");
hits += linear.len();
}
assert!(
hits >= 15,
"the fixtures must exercise real matches, got {hits}"
);
}
#[test]
fn the_indexed_scanner_gives_the_verdicts_of_modgunns_scanner() {
let scanner = OsvScanner::new(Policy::default(), db());
let indexed = IndexedOsvScanner::new(scanner.clone());
for (eco, name, ver) in [
("pip", "requests", "2.31.0"),
("npm", "lodash", "4.17.21"),
("cargo", "tokio", "1.17.0"),
] {
let a = crate::security::artifact_from_coords_with_digest(eco, name, ver, "ab", false);
assert_eq!(
serde_json::to_value(indexed.scan(&a)).unwrap(),
serde_json::to_value(scanner.scan(&a)).unwrap(),
"{eco} {name} {ver}"
);
}
}
#[test]
fn an_index_over_another_db_still_answers_right() {
let index = AdvisoryIndex::build(&AdvisoryDb::default());
let db = db();
let a = artifact("npm", "lodash", "4.17.20");
assert_eq!(ids(&index.matching(&db, &a)), ids(&db.query(&a)));
}
}