1use std::collections::HashMap;
4use std::sync::Mutex;
5
6use anyhow::Result;
7use fnprint_db::{Corpus, Db};
8use fnprint_emu::{Config, MicroExec};
9use fnprint_loader::{Func, FuncSource};
10use fnprint_sig::Fingerprint;
11use rayon::prelude::*;
12
13pub const MIN_COMPLEXITY: u32 = 4;
15pub const SAME_THRESH: f64 = 0.88;
17pub const LOW_COVERAGE_ADVISORY: f32 = 0.15;
26const SEEDS: [u64; 4] = [0, 0x9e3779b9, 0x1234_5678, 0xdead_beef];
28
29static EMU_LOCK: Mutex<()> = Mutex::new(());
38
39#[derive(serde::Serialize, serde::Deserialize)]
40pub struct IndexedFunc {
41 pub name: Option<String>,
42 pub entry: u64,
43 pub source: FuncSource,
44 pub fp: Fingerprint,
45 #[serde(default = "default_coverage")]
49 pub coverage: f32,
50}
51
52fn default_coverage() -> f32 {
57 1.0
58}
59
60pub use fnprint_trace::EffectTrace;
63pub use fnprint_sig::SIG_LEN;
66
67pub fn warm_pool() {
71 let _: u64 = (0..256u64).into_par_iter().sum();
72}
73
74pub fn source_str(s: FuncSource) -> &'static str {
75 match s {
76 FuncSource::Symtab => "symtab",
77 FuncSource::DynSym => "dynsym",
78 FuncSource::EhFrame => "eh_frame",
79 }
80}
81
82pub fn index_bytes(bytes: &[u8], cfg: Config) -> Result<Vec<IndexedFunc>> {
84 index_bytes_shard(bytes, cfg, 0, 1)
85}
86
87pub fn index_bytes_shard(
97 bytes: &[u8],
98 cfg: Config,
99 shard_idx: usize,
100 shard_count: usize,
101) -> Result<Vec<IndexedFunc>> {
102 let shard_count = shard_count.max(1);
103 let shard_idx = shard_idx.min(shard_count - 1);
104 let loaded = fnprint_loader::load(bytes)?;
105 let image = &loaded.image;
106
107 let mut symbols: HashMap<u64, String> = HashMap::new();
111 for f in &loaded.funcs {
112 if let Some(n) = &f.name {
113 symbols.insert(f.entry, n.clone());
114 }
115 }
116
117 let out: Vec<IndexedFunc> = loaded
118 .funcs
119 .par_iter()
120 .enumerate()
121 .filter(|(i, _)| i % shard_count == shard_idx)
125 .map(|(_, f)| f)
126 .filter(|f| f.size > 0 && image.code_at(f.entry, 1).is_some())
127 .map(|f: &Func| {
128 let traces = {
133 let _g = EMU_LOCK.lock().unwrap_or_else(|e| e.into_inner());
134 let ex = MicroExec::new(cfg.clone());
135 ex.run_explore(image, f, &symbols, &SEEDS)
138 };
139 let coverage = traces.iter().map(|t| t.coverage).fold(0.0f32, f32::max);
143 IndexedFunc {
144 name: f.name.clone(),
145 entry: f.entry,
146 source: f.source,
147 fp: Fingerprint::from_traces(&traces),
148 coverage,
149 }
150 })
151 .collect();
152
153 Ok(out)
154}
155
156pub fn index_to_db(bytes: &[u8], binary: &str, db: &Db, cfg: Config) -> Result<usize> {
157 let funcs = index_bytes(bytes, cfg)?;
158 for f in &funcs {
159 db.insert(
160 binary,
161 f.name.as_deref(),
162 f.entry,
163 source_str(f.source),
164 &f.fp,
165 )?;
166 }
167 Ok(funcs.len())
168}
169
170pub struct Changed {
173 pub name: String,
174 pub similarity: f64,
175}
176
177#[derive(Default)]
178pub struct MatchReport {
179 pub same: usize,
180 pub changed: Vec<Changed>,
181 pub only_a: Vec<String>,
182 pub only_b: Vec<String>,
183 pub compared: usize,
184 pub low_signal: usize,
186}
187
188pub fn match_by_name(a: &[IndexedFunc], b: &[IndexedFunc]) -> MatchReport {
191 let mut bmap: HashMap<&str, &IndexedFunc> = HashMap::new();
192 for f in b {
193 if let Some(n) = &f.name {
194 bmap.insert(n.as_str(), f);
195 }
196 }
197 let mut amap: HashMap<&str, &IndexedFunc> = HashMap::new();
198 for f in a {
199 if let Some(n) = &f.name {
200 amap.insert(n.as_str(), f);
201 }
202 }
203
204 let mut rep = MatchReport::default();
205 for (name, fa) in &amap {
206 match bmap.get(name) {
207 Some(fb) => {
208 rep.compared += 1;
209 if fa.fp.complexity < MIN_COMPLEXITY || fb.fp.complexity < MIN_COMPLEXITY {
212 rep.low_signal += 1;
213 continue;
214 }
215 let sim = fa.fp.similarity(&fb.fp);
216 if sim >= SAME_THRESH {
217 rep.same += 1;
218 } else {
219 rep.changed.push(Changed {
220 name: name.to_string(),
221 similarity: sim,
222 });
223 }
224 }
225 None => rep.only_a.push(name.to_string()),
226 }
227 }
228 for name in bmap.keys() {
229 if !amap.contains_key(name) {
230 rep.only_b.push(name.to_string());
231 }
232 }
233 rep.changed.sort_by(|x, y| {
237 x.similarity
238 .total_cmp(&y.similarity)
239 .then_with(|| x.name.cmp(&y.name))
240 });
241 rep.only_a.sort();
242 rep.only_b.sort();
243 rep
244}
245
246pub struct Named {
249 pub entry: u64,
250 pub guess: String,
251 pub from_binary: String,
252 pub similarity: f64,
253}
254
255fn best_in_corpus<C: Corpus>(
259 fp: &Fingerprint,
260 db: &C,
261 all: &[fnprint_db::FuncRec],
262) -> Result<Option<(f64, String, String)>> {
263 let cands = db.candidates(fp)?;
264 let pool: &[fnprint_db::FuncRec] = if cands.is_empty() { all } else { &cands };
265 let mut best: Option<(f64, String, String)> = None;
266 for c in pool {
267 if c.fp.complexity < MIN_COMPLEXITY {
268 continue;
269 }
270 let cname = match &c.name {
271 Some(n) => n,
272 None => continue,
273 };
274 let sim = fp.similarity(&c.fp);
275 let better = match best.as_ref() {
280 None => true,
281 Some((s, bn, bb)) => {
282 sim > *s
283 || (sim == *s
284 && (cname.as_str(), c.binary.as_str()) < (bn.as_str(), bb.as_str()))
285 }
286 };
287 if better {
288 best = Some((sim, cname.clone(), c.binary.clone()));
289 }
290 }
291 Ok(best)
292}
293
294pub fn query_corpus<C: Corpus>(
297 target: &[IndexedFunc],
298 corpus: &C,
299 threshold: f64,
300) -> Result<Vec<Named>> {
301 let named = corpus.all()?; let mut out = Vec::new();
303 for f in target {
304 if f.fp.complexity < MIN_COMPLEXITY || f.fp.shingles == 0 {
305 continue;
306 }
307 if let Some((sim, name, bin)) = best_in_corpus(&f.fp, corpus, &named)? {
308 if sim >= threshold {
309 out.push(Named {
310 entry: f.entry,
311 guess: name,
312 from_binary: bin,
313 similarity: sim,
314 });
315 }
316 }
317 }
318 out.sort_by(|a, b| b.similarity.total_cmp(&a.similarity));
319 Ok(out)
320}
321
322#[derive(Clone, Copy, PartialEq, Eq, Debug)]
325pub enum Verdict {
326 Vulnerable,
328 Patched,
330 Inconclusive,
332}
333
334pub struct TriageHit {
335 pub entry: u64,
336 pub verdict: Verdict,
337 pub vuln_sim: f64,
338 pub vuln_name: String,
339 pub patched_sim: f64,
340 pub patched_name: String,
341 pub coverage: f32,
346}
347
348impl TriageHit {
349 pub fn margin(&self) -> f64 {
352 self.vuln_sim - self.patched_sim
353 }
354}
355
356fn verdict_order(v: Verdict) -> u8 {
357 match v {
359 Verdict::Vulnerable => 0,
360 Verdict::Inconclusive => 1,
361 Verdict::Patched => 2,
362 }
363}
364
365pub fn triage<C: Corpus>(
374 target: &[IndexedFunc],
375 vuln: &C,
376 patched: &C,
377 min_sim: f64,
378 margin: f64,
379) -> Result<Vec<TriageHit>> {
380 let vuln_all = vuln.all()?;
381 let patched_all = patched.all()?;
382 let mut out = Vec::new();
383 for f in target {
384 if f.fp.complexity < MIN_COMPLEXITY || f.fp.shingles == 0 {
385 continue;
386 }
387 let (vuln_sim, vuln_name) = best_in_corpus(&f.fp, vuln, &vuln_all)?
388 .map(|(s, n, _)| (s, n))
389 .unwrap_or((0.0, String::new()));
390 let (patched_sim, patched_name) = best_in_corpus(&f.fp, patched, &patched_all)?
391 .map(|(s, n, _)| (s, n))
392 .unwrap_or((0.0, String::new()));
393
394 let top = vuln_sim.max(patched_sim);
395 let verdict = if top < min_sim {
396 Verdict::Inconclusive
397 } else if vuln_sim - patched_sim >= margin {
398 Verdict::Vulnerable
399 } else if patched_sim - vuln_sim >= margin {
400 Verdict::Patched
401 } else {
402 Verdict::Inconclusive
403 };
404 out.push(TriageHit {
405 entry: f.entry,
406 verdict,
407 vuln_sim,
408 vuln_name,
409 patched_sim,
410 patched_name,
411 coverage: f.coverage,
412 });
413 }
414 out.sort_by(|a, b| {
415 verdict_order(a.verdict)
416 .cmp(&verdict_order(b.verdict))
417 .then(b.vuln_sim.total_cmp(&a.vuln_sim))
418 });
419 Ok(out)
420}
421
422pub struct EvalResult {
425 pub scored: usize,
427 pub rank1: usize,
429 pub rr_sum: f64,
431 pub tp: usize,
433 pub fp: usize,
434 pub fn_: usize,
436 pub ranks: Vec<usize>,
439 pub abstained: usize,
442}
443
444impl EvalResult {
445 pub fn rank1_acc(&self) -> f64 {
446 if self.scored == 0 {
447 0.0
448 } else {
449 self.rank1 as f64 / self.scored as f64
450 }
451 }
452 pub fn mrr(&self) -> f64 {
453 if self.scored == 0 {
454 0.0
455 } else {
456 self.rr_sum / self.scored as f64
457 }
458 }
459 pub fn precision(&self) -> f64 {
460 let d = self.tp + self.fp;
461 if d == 0 {
462 0.0
463 } else {
464 self.tp as f64 / d as f64
465 }
466 }
467 pub fn recall(&self) -> f64 {
468 let d = self.tp + self.fn_;
469 if d == 0 {
470 0.0
471 } else {
472 self.tp as f64 / d as f64
473 }
474 }
475 pub fn recall_at(&self, k: usize) -> f64 {
478 if self.scored == 0 {
479 return 0.0;
480 }
481 let hits = self.ranks.iter().filter(|&&r| r <= k).count();
482 hits as f64 / self.scored as f64
483 }
484 pub fn abstain_rate(&self) -> f64 {
487 if self.scored == 0 {
488 0.0
489 } else {
490 self.abstained as f64 / self.scored as f64
491 }
492 }
493}
494
495pub fn eval(a: &[IndexedFunc], b: &[IndexedFunc]) -> EvalResult {
498 let bsig: Vec<&IndexedFunc> = b
499 .iter()
500 .filter(|f| f.fp.complexity >= MIN_COMPLEXITY && f.fp.shingles > 0 && f.name.is_some())
501 .collect();
502
503 let mut res = EvalResult {
504 scored: 0,
505 rank1: 0,
506 rr_sum: 0.0,
507 tp: 0,
508 fp: 0,
509 fn_: 0,
510 ranks: Vec::new(),
511 abstained: 0,
512 };
513
514 for fa in a {
515 if fa.fp.complexity < MIN_COMPLEXITY || fa.fp.shingles == 0 {
516 continue;
517 }
518 let aname = match &fa.name {
519 Some(n) => n.as_str(),
520 None => continue,
521 };
522 if !bsig.iter().any(|f| f.name.as_deref() == Some(aname)) {
524 continue;
525 }
526 let mut scored: Vec<(f64, &str)> = bsig
529 .iter()
530 .filter_map(|f| f.name.as_deref().map(|n| (fa.fp.similarity(&f.fp), n)))
531 .collect();
532 scored.sort_by(|x, y| y.0.total_cmp(&x.0));
533 let Some(&(top_sim, top_name)) = scored.first() else {
534 continue; };
536 res.scored += 1;
537
538 if top_name == aname {
539 res.rank1 += 1;
540 }
541 if let Some(pos) = scored.iter().position(|(_, n)| *n == aname) {
542 res.rr_sum += 1.0 / (pos as f64 + 1.0);
543 res.ranks.push(pos + 1); }
545
546 let predicted_same = top_sim >= SAME_THRESH;
548 if !predicted_same {
549 res.abstained += 1; }
551 let correct = top_name == aname;
552 match (predicted_same, correct) {
553 (true, true) => res.tp += 1,
554 (true, false) => res.fp += 1,
555 (false, true) => res.fn_ += 1,
556 (false, false) => {}
557 }
558 }
559 res
560}
561
562pub fn dump_traces(
565 bytes: &[u8],
566 name: &str,
567 cfg: Config,
568) -> Result<Vec<fnprint_trace::EffectTrace>> {
569 let loaded = fnprint_loader::load(bytes)?;
570 let image = &loaded.image;
571 let mut symbols: HashMap<u64, String> = HashMap::new();
572 for f in &loaded.funcs {
573 if let Some(n) = &f.name {
574 symbols.insert(f.entry, n.clone());
575 }
576 }
577 let f = loaded
578 .funcs
579 .iter()
580 .find(|f| f.name.as_deref() == Some(name))
581 .ok_or_else(|| anyhow::anyhow!("no function named {name}"))?;
582 let ex = MicroExec::new(cfg);
583 Ok(ex.run_explore(image, f, &symbols, &SEEDS))
584}
585
586#[cfg(test)]
587mod tests {
588 use super::*;
589
590 fn ifunc(name: &str, sig_seed: u64, complexity: u32) -> IndexedFunc {
594 IndexedFunc {
595 name: Some(name.to_string()),
596 entry: 0,
597 source: FuncSource::Symtab,
598 fp: fnprint_sig::Fingerprint {
599 sig: (0..fnprint_sig::SIG_LEN as u64)
600 .map(|i| i.wrapping_mul(sig_seed))
601 .collect(),
602 shingles: 20,
603 complexity,
604 capped: false,
605 },
606 coverage: 1.0,
607 }
608 }
609
610 #[test]
611 fn identical_indexes_report_no_changes() {
612 let a = vec![ifunc("foo", 3, 10), ifunc("bar", 7, 10)];
613 let b = vec![ifunc("foo", 3, 10), ifunc("bar", 7, 10)];
614 let rep = match_by_name(&a, &b);
615 assert_eq!(rep.changed.len(), 0);
616 assert_eq!(rep.same, 2);
617 }
618
619 #[test]
620 fn changed_behavior_is_flagged() {
621 let a = vec![ifunc("foo", 3, 10)];
622 let b = vec![ifunc("foo", 999, 10)]; let rep = match_by_name(&a, &b);
624 assert_eq!(rep.changed.len(), 1);
625 }
626
627 #[test]
628 fn low_signal_not_called_changed() {
629 let a = vec![ifunc("foo", 3, 2)];
631 let b = vec![ifunc("foo", 999, 2)];
632 let rep = match_by_name(&a, &b);
633 assert_eq!(rep.changed.len(), 0);
634 assert_eq!(rep.low_signal, 1);
635 }
636
637 #[test]
638 fn triage_leans_to_matching_side() {
639 let vuln = Db::open_memory().unwrap();
643 vuln.insert("v1", Some("f"), 0x1000, "symtab", &ifunc("f", 3, 10).fp)
644 .unwrap();
645 let patched = Db::open_memory().unwrap();
646 patched
647 .insert("v2", Some("f"), 0x1000, "symtab", &ifunc("f", 999, 10).fp)
648 .unwrap();
649
650 let looks_vuln = triage(&[ifunc("x", 3, 10)], &vuln, &patched, 0.5, 0.1).unwrap();
651 assert_eq!(looks_vuln[0].verdict, Verdict::Vulnerable);
652 assert!(looks_vuln[0].margin() > 0.0);
653
654 let looks_patched = triage(&[ifunc("x", 999, 10)], &vuln, &patched, 0.5, 0.1).unwrap();
655 assert_eq!(looks_patched[0].verdict, Verdict::Patched);
656 }
657
658 #[test]
659 fn low_coverage_is_advisory_not_a_gate() {
660 let vuln = Db::open_memory().unwrap();
665 vuln.insert("v1", Some("f"), 0x1000, "symtab", &ifunc("f", 3, 10).fp)
666 .unwrap();
667 let patched = Db::open_memory().unwrap();
668 patched
669 .insert("v2", Some("f"), 0x1000, "symtab", &ifunc("f", 999, 10).fp)
670 .unwrap();
671
672 let mut t = ifunc("x", 3, 10);
673 t.coverage = 0.0;
674 let hits = triage(&[t], &vuln, &patched, 0.5, 0.1).unwrap();
675 assert_eq!(hits[0].verdict, Verdict::Vulnerable);
676 assert_eq!(
677 hits[0].coverage, 0.0,
678 "coverage carried through for display"
679 );
680 }
681
682 #[test]
683 fn triage_abstains_when_nothing_close() {
684 let vuln = Db::open_memory().unwrap();
686 vuln.insert("v1", Some("f"), 0x1000, "symtab", &ifunc("f", 3, 10).fp)
687 .unwrap();
688 let patched = Db::open_memory().unwrap();
689 patched
690 .insert("v2", Some("f"), 0x1000, "symtab", &ifunc("f", 999, 10).fp)
691 .unwrap();
692
693 let hits = triage(&[ifunc("x", 55555, 10)], &vuln, &patched, 0.9, 0.1).unwrap();
694 assert_eq!(hits[0].verdict, Verdict::Inconclusive);
695 }
696}