use aho_corasick::AhoCorasick;
use regex_syntax::hir::literal::{ExtractKind, Extractor};
use regex_syntax::hir::{Capture, Class, Hir, HirKind, Repetition};
use regex_syntax::parse;
use super::matcher::Signature;
const MIN_LITERAL_LEN: usize = 3;
const MAX_ALTERNATION_LITERALS: usize = 32;
pub trait Prefilter: Send + Sync {
fn candidates(&self, response: &str) -> Vec<usize>;
}
#[derive(Debug)]
pub struct LiteralPrefilter {
automaton: AhoCorasick,
literal_owner: Vec<usize>,
always_run: Vec<usize>,
signature_count: usize,
}
impl LiteralPrefilter {
pub fn build(signatures: &[Signature]) -> Self {
let mut literals: Vec<Vec<u8>> = Vec::new();
let mut literal_owner: Vec<usize> = Vec::new();
let mut always_run: Vec<usize> = Vec::new();
for (idx, signature) in signatures.iter().enumerate() {
match required_literals(signature.pattern()) {
Some(lits) => {
for lit in lits {
literals.push(lit);
literal_owner.push(idx);
}
}
None => always_run.push(idx),
}
}
let automaton = AhoCorasick::builder()
.ascii_case_insensitive(true)
.build(&literals)
.expect("aho-corasick construction over signature literals");
Self {
automaton,
literal_owner,
always_run,
signature_count: signatures.len(),
}
}
}
impl LiteralPrefilter {
#[cfg(test)]
pub(crate) fn always_run(&self) -> &[usize] {
&self.always_run
}
}
impl Prefilter for LiteralPrefilter {
fn candidates(&self, response: &str) -> Vec<usize> {
let mut selected = vec![0u64; self.signature_count.div_ceil(64).max(1)];
let mut candidates = self.always_run.clone();
for &owner in &self.always_run {
selected[owner / 64] |= 1u64 << (owner % 64);
}
for m in self.automaton.find_overlapping_iter(response) {
let owner = self.literal_owner[m.pattern().as_usize()];
let (word, bit) = (owner / 64, 1u64 << (owner % 64));
if selected[word] & bit == 0 {
selected[word] |= bit;
candidates.push(owner);
}
}
candidates.sort_unstable();
candidates
}
}
fn required_literals(pattern: &str) -> Option<Vec<Vec<u8>>> {
let hir = folded(&parse(pattern).ok()?);
if let Some(set) = literal_set(&hir, ExtractKind::Prefix) {
return Some(set);
}
if let Some(inner) = required_set(&hir) {
return Some(inner);
}
literal_set(&hir, ExtractKind::Suffix)
}
fn folded(hir: &Hir) -> Hir {
match hir.kind() {
HirKind::Class(class) => match case_pair(class) {
Some(lower) => Hir::literal([lower]),
None => hir.clone(),
},
HirKind::Repetition(rep) => Hir::repetition(Repetition {
sub: Box::new(folded(&rep.sub)),
..rep.clone()
}),
HirKind::Capture(capture) => Hir::capture(Capture {
sub: Box::new(folded(&capture.sub)),
..capture.clone()
}),
HirKind::Concat(parts) => Hir::concat(parts.iter().map(folded).collect()),
HirKind::Alternation(branches) => Hir::alternation(branches.iter().map(folded).collect()),
_ => hir.clone(),
}
}
fn case_pair(class: &Class) -> Option<u8> {
let members: Vec<u32> = match class {
Class::Unicode(class) => class
.ranges()
.iter()
.flat_map(|range| u32::from(range.start())..=u32::from(range.end()))
.take(3)
.collect(),
Class::Bytes(class) => class
.ranges()
.iter()
.flat_map(|range| u32::from(range.start())..=u32::from(range.end()))
.take(3)
.collect(),
};
let [upper, lower] = members[..] else {
return None;
};
let lower = u8::try_from(lower).ok()?;
(lower.is_ascii_lowercase() && u32::from(lower.to_ascii_uppercase()) == upper).then_some(lower)
}
fn case_triple(class: &Class) -> Option<Vec<Vec<u8>>> {
let Class::Unicode(class) = class else {
return None;
};
let members: Vec<u32> = class
.ranges()
.iter()
.flat_map(|range| u32::from(range.start())..=u32::from(range.end()))
.take(4)
.collect();
let (lower, third) = match members[..] {
[0x4B, 0x6B, 0x212A] => ('k', '\u{212A}'),
[0x53, 0x73, 0x17F] => ('s', '\u{17F}'),
_ => return None,
};
Some(vec![vec![lower as u8], third.to_string().into_bytes()])
}
fn exact_set(hir: &Hir) -> Option<Vec<Vec<u8>>> {
match hir.kind() {
HirKind::Literal(literal) => Some(vec![literal.0.to_vec()]),
HirKind::Class(class) => case_triple(class),
HirKind::Capture(capture) => exact_set(&capture.sub),
HirKind::Concat(parts) => parts.iter().try_fold(vec![Vec::new()], |run, part| {
joined(&run, &exact_set(part)?)
}),
HirKind::Alternation(branches) => {
let mut set = Vec::new();
for branch in branches {
set.extend(exact_set(branch)?);
}
(set.len() <= MAX_ALTERNATION_LITERALS).then_some(set)
}
_ => None,
}
}
fn joined(before: &[Vec<u8>], after: &[Vec<u8>]) -> Option<Vec<Vec<u8>>> {
if before.len() * after.len() > MAX_ALTERNATION_LITERALS {
return None;
}
Some(
before
.iter()
.flat_map(|head| {
after.iter().map(move |tail| {
let mut literal = head.clone();
literal.extend_from_slice(tail);
literal
})
})
.collect(),
)
}
fn literal_set(hir: &Hir, kind: ExtractKind) -> Option<Vec<Vec<u8>>> {
let mut extractor = Extractor::new();
extractor.kind(kind);
let seq = extractor.extract(hir);
let literals = seq.literals()?; if literals.is_empty() {
return None;
}
let mut out = Vec::with_capacity(literals.len());
for literal in literals {
if literal.as_bytes().is_empty() {
return None;
}
out.push(literal.as_bytes().to_vec());
}
Some(out)
}
fn required_set(hir: &Hir) -> Option<Vec<Vec<u8>>> {
match hir.kind() {
HirKind::Literal(literal) => {
(literal.0.len() >= MIN_LITERAL_LEN).then(|| vec![literal.0.to_vec()])
}
HirKind::Capture(capture) => required_set(&capture.sub),
HirKind::Repetition(rep) if rep.min >= 1 => required_set(&rep.sub),
HirKind::Concat(parts) => {
let mut sets: Vec<Vec<Vec<u8>>> = parts.iter().filter_map(required_set).collect();
sets.extend(exact_runs(parts));
sets.into_iter()
.filter(|set| set.iter().all(|literal| literal.len() >= MIN_LITERAL_LEN))
.max_by(|a, b| {
let shortest = |set: &Vec<Vec<u8>>| set.iter().map(Vec::len).min();
shortest(a)
.cmp(&shortest(b))
.then_with(|| b.len().cmp(&a.len()))
})
}
HirKind::Alternation(branches) => {
let mut set = Vec::new();
for branch in branches {
set.extend(required_set(branch)?);
}
(set.len() <= MAX_ALTERNATION_LITERALS).then_some(set)
}
_ => None,
}
}
fn exact_runs(parts: &[Hir]) -> Vec<Vec<Vec<u8>>> {
let mut runs = Vec::new();
let mut run: Option<Vec<Vec<u8>>> = None;
for part in parts {
match (exact_set(part), run.take()) {
(Some(set), Some(before)) => match joined(&before, &set) {
Some(longer) => run = Some(longer),
None => {
runs.push(before);
run = Some(set);
}
},
(Some(set), None) => run = Some(set),
(None, before) => runs.extend(before),
}
}
runs.extend(run);
runs
}
#[cfg(test)]
mod tests {
use super::*;
use crate::fingerprint::signature::MatchRule;
use proptest::prelude::*;
fn sig(pattern: &str) -> Signature {
Signature::new(
"svc",
&MatchRule {
name: None,
pattern: pattern.to_string(),
version_group: None,
vendor: None,
product: None,
context: None,
example: None,
metadata: None,
},
)
}
#[test]
fn selects_by_prefix_literal_and_skips_non_candidates() {
let sigs = [sig(r"^SSH-[\d.]+-OpenSSH"), sig(r"^HTTP/1\.[01]")];
let pf = LiteralPrefilter::build(&sigs);
let ssh = pf.candidates("SSH-2.0-OpenSSH_9.6");
assert!(ssh.contains(&0));
assert!(!ssh.contains(&1)); }
#[test]
fn selects_by_inner_literal() {
let sigs = [sig(r"^(\S{1,64}) FTP Server \(Version ([\d.]+)\)")];
let pf = LiteralPrefilter::build(&sigs);
assert!(
pf.candidates("host.example FTP Server (Version 1.2.3)")
.contains(&0)
);
assert!(pf.candidates("SSH-2.0-OpenSSH_9.6").is_empty());
}
#[test]
fn unfilterable_pattern_is_always_a_candidate() {
let sigs = [sig(r"^\d{1,3}\.\d{1,3}\.\d{1,3}\.\d{1,3}$")];
let pf = LiteralPrefilter::build(&sigs);
assert!(pf.candidates("anything at all").contains(&0));
}
#[test]
fn a_signature_is_listed_once_however_many_of_its_literals_hit() {
let sigs = [
sig(r"^(?:Postfix|Sendmail|Exim) SMTP"),
sig(r"^HTTP/1\.[01]"),
];
let pf = LiteralPrefilter::build(&sigs);
let response = "Postfix SMTP / Sendmail SMTP / Exim SMTP / Postfix SMTP";
let owned = pf.literal_owner.iter().filter(|&&o| o == 0).count();
assert!(owned > 1, "the alternation gives it several literals");
assert_eq!(pf.candidates(response), vec![0]);
}
#[test]
fn case_insensitive_literal_still_selects() {
let sigs = [sig(r"^Server: nginx")];
let pf = LiteralPrefilter::build(&sigs);
assert!(pf.candidates("server: NGINX/1.25").contains(&0));
}
#[test]
fn a_case_insensitive_pattern_is_narrowed_by_its_letters() {
let sigs = [sig(r"(?i)^(.{0,64}) Linux ([\w.-]*)$")];
let pf = LiteralPrefilter::build(&sigs);
assert!(pf.always_run().is_empty(), "left to run on everything");
assert!(pf.candidates("host LINUX 6.1.0").contains(&0));
assert!(pf.candidates("host linux 6.1.0").contains(&0));
assert!(pf.candidates("host FreeBSD 14.1").is_empty());
}
#[test]
fn a_letter_whose_class_is_wider_than_its_two_cases_is_not_read_as_a_literal() {
let pattern = r"(?i)^.{0,8}kernel";
let response = "\u{212A}ERNEL";
assert!(
regex::Regex::new(pattern)
.expect("compiles")
.is_match(response),
"the Kelvin sign is a k to the pattern"
);
let pf = LiteralPrefilter::build(&[sig(pattern)]);
assert!(pf.candidates(response).contains(&0));
}
#[test]
fn a_word_split_by_a_k_or_an_s_is_narrowed_by_each_spelling_of_it() {
let pattern = r"(?i)^(.{0,256}?BSD)[ /-]([\d.]+)";
let pf = LiteralPrefilter::build(&[sig(pattern)]);
assert!(pf.always_run().is_empty(), "left to run on everything");
let matching = regex::Regex::new(pattern).expect("compiles");
for response in [
"FreeBSD 14.1",
"freebsd-13.2",
"Free B\u{17F}D 1",
"B\u{17F}D/9",
] {
if matching.is_match(response) {
assert!(
pf.candidates(response).contains(&0),
"{response:?} matches and was not selected"
);
}
}
assert!(
matching.is_match("B\u{17F}D/9"),
"the long s is an s to the pattern"
);
assert!(pf.candidates("Linux 6.1").is_empty());
let kernel = LiteralPrefilter::build(&[sig(r"(?i)^.{0,8}kernel")]);
assert!(kernel.always_run().is_empty(), "left to run on everything");
assert!(kernel.candidates("\u{212A}ERNEL").contains(&0));
assert!(kernel.candidates("KERNEL").contains(&0));
}
#[test]
fn a_required_alternation_narrows_by_its_branches() {
let sigs = [sig(r"^(.{0,16}) (?:Junos|ScreenOS) ([\d.]+)$")];
let pf = LiteralPrefilter::build(&sigs);
assert!(pf.always_run().is_empty(), "left to run on everything");
assert!(pf.candidates("fw1 ScreenOS 6.3").contains(&0));
assert!(pf.candidates("r1 Junos 23.4").contains(&0));
assert!(pf.candidates("r1 IOS 15.2").is_empty());
}
proptest! {
#[test]
fn candidates_never_panics_on_arbitrary_input(response in "(?s).*") {
let sigs = [sig(r"^HTTP/\d"), sig(r"Server: (\w+)"), sig(r"^\d{3} ")];
let pf = LiteralPrefilter::build(&sigs);
let _ = pf.candidates(&response);
}
}
}