fnprint_trace/lib.rs
1//! The arch-neutral effect model.
2//!
3//! The emulator produces a stream of these while a function runs. Everything
4//! here is deliberately independent of the CPU it came from and of absolute
5//! addresses, so an x86 trace and an arm trace of the same logic line up.
6
7use serde::{Deserialize, Serialize};
8
9/// Where a memory access landed, relative to something we seeded.
10/// Absolute addresses are useless for matching so we never keep them.
11#[derive(Clone, Copy, PartialEq, Eq, Debug, Serialize, Deserialize)]
12pub enum Region {
13 /// inside the buffer we pointed argument `k` at
14 Arg(u16),
15 /// on the stack (offset sign kept, magnitude bucketed)
16 Stack,
17 /// static/global data in the binary's own segments (.rodata/.data/.bss).
18 /// distinguishes table-driven code (crc32 reads a table, adler32 doesn't).
19 Global,
20 /// somewhere we lazily mapped that isn't an arg or the stack
21 Heapish,
22}
23
24/// What a value looks like, again without keeping the raw bits when they'd
25/// just be an address. Small constants carry real signal so we keep those.
26#[derive(Clone, Copy, PartialEq, Eq, Debug, Serialize, Deserialize)]
27pub enum ValueClass {
28 /// straight copy of the value we seeded into input `k`
29 Input(u16),
30 /// derived from input `k` (add/sub/mask etc, we saw it drift)
31 InputDeriv(u16),
32 Zero,
33 /// a small literal, kept exactly because e.g. `1` vs `-1` matters
34 SmallConst(i64),
35 /// big literal, almost always an address, so we drop the bits
36 BigConst,
37 Unknown,
38}
39
40/// Who a call went to.
41#[derive(Clone, PartialEq, Eq, Debug, Serialize, Deserialize)]
42pub enum CallTarget {
43 /// resolved to a name (plt/symbol)
44 Sym(String),
45 /// unresolved, bucketed by a rough distance class so recompiles still line up
46 Anon,
47}
48
49/// One observable thing the function did. Order matters.
50#[derive(Clone, PartialEq, Eq, Debug, Serialize, Deserialize)]
51pub enum Effect {
52 /// wrote `val` into `region` at a bucketed offset
53 Write {
54 region: Region,
55 off: i32,
56 val: ValueClass,
57 },
58 /// read a distinct field (region + offset). recorded once per field, so it
59 /// captures the *set* of struct fields a function touches, not every access.
60 Read {
61 region: Region,
62 off: i32,
63 },
64 /// first touch of a fresh region (shape signal: how many buffers it walks)
65 NewRegion(Region),
66 Call(CallTarget),
67 Syscall(u32),
68 /// a conditional branch happened here. we don't keep the outcome, just that
69 /// the function has a decision point at this point in the effect stream.
70 Branch,
71 Ret(ValueClass),
72 /// run hit a cap (loop/instr/time). still a usable partial.
73 Capped,
74}
75
76impl Effect {
77 /// Stable token for this effect. FNV-1a by hand so it does not depend on
78 /// std's hasher, which is not stable across toolchains. Same effect ->
79 /// same u64 forever, which is what the on-disk fingerprints rely on.
80 pub fn token(&self) -> u64 {
81 let mut h = Fnv::new();
82 match self {
83 Effect::Write { region, off, val } => {
84 h.tag(1);
85 region.hash(&mut h);
86 h.i32(*off);
87 val.hash(&mut h);
88 }
89 Effect::Read { region, off } => {
90 h.tag(8);
91 region.hash(&mut h);
92 h.i32(*off);
93 }
94 Effect::NewRegion(r) => {
95 h.tag(2);
96 r.hash(&mut h);
97 }
98 Effect::Call(t) => {
99 h.tag(3);
100 match t {
101 CallTarget::Sym(s) => {
102 h.tag(1);
103 for b in s.as_bytes() {
104 h.byte(*b);
105 }
106 }
107 CallTarget::Anon => h.tag(2),
108 }
109 }
110 Effect::Syscall(n) => {
111 h.tag(4);
112 h.u64(*n as u64);
113 }
114 Effect::Branch => h.tag(5),
115 Effect::Ret(v) => {
116 h.tag(6);
117 v.hash(&mut h);
118 }
119 Effect::Capped => h.tag(7),
120 }
121 h.0
122 }
123}
124
125impl Region {
126 fn hash(&self, h: &mut Fnv) {
127 match self {
128 Region::Arg(k) => {
129 h.tag(10);
130 h.u64(*k as u64);
131 }
132 Region::Stack => h.tag(11),
133 Region::Global => h.tag(13),
134 Region::Heapish => h.tag(12),
135 }
136 }
137}
138
139impl ValueClass {
140 fn hash(&self, h: &mut Fnv) {
141 match self {
142 ValueClass::Input(k) => {
143 h.tag(20);
144 h.u64(*k as u64);
145 }
146 ValueClass::InputDeriv(k) => {
147 h.tag(21);
148 h.u64(*k as u64);
149 }
150 ValueClass::Zero => h.tag(22),
151 ValueClass::SmallConst(v) => {
152 h.tag(23);
153 h.u64(*v as u64);
154 }
155 ValueClass::BigConst => h.tag(24),
156 ValueClass::Unknown => h.tag(25),
157 }
158 }
159}
160
161/// The full result of micro-executing one function.
162#[derive(Clone, Debug, Serialize, Deserialize)]
163pub struct EffectTrace {
164 pub effects: Vec<Effect>,
165 /// instructions retired before we stopped
166 pub instret: u64,
167 /// did we cut it off (loop/instr/time)
168 pub capped: bool,
169 /// fraction of the function's own code bytes we actually executed, in [0,1].
170 /// advisory confidence signal: a low value means most of the body sat behind
171 /// branches microexecution never took, so the print reflects little observed
172 /// behavior. surfaced to the analyst; not used to gate a verdict (complex
173 /// input-driven functions legitimately run almost none of their body).
174 pub coverage: f32,
175}
176
177impl EffectTrace {
178 pub fn tokens(&self) -> Vec<u64> {
179 self.effects.iter().map(|e| e.token()).collect()
180 }
181
182 /// rough "is there enough here to trust a match" gate. thunks and 2-effect
183 /// leaves all look alike, so callers use this to withhold confident hits.
184 pub fn complexity(&self) -> usize {
185 // count effects that actually say something, calls/writes weigh more
186 let mut c = 0usize;
187 for e in &self.effects {
188 c += match e {
189 Effect::Call(_) | Effect::Syscall(_) => 3,
190 Effect::Write { .. } | Effect::NewRegion(_) => 2,
191 Effect::Read { .. } => 1,
192 Effect::Ret(ValueClass::Input(_)) | Effect::Ret(ValueClass::InputDeriv(_)) => 1,
193 _ => 0,
194 };
195 }
196 c
197 }
198}
199
200// small fnv-1a. nothing fancy, just needs to be stable.
201pub struct Fnv(pub u64);
202impl Fnv {
203 pub fn new() -> Self {
204 Fnv(0xcbf29ce484222325)
205 }
206 #[inline]
207 pub fn byte(&mut self, b: u8) {
208 self.0 ^= b as u64;
209 self.0 = self.0.wrapping_mul(0x100000001b3);
210 }
211 pub fn tag(&mut self, t: u8) {
212 self.byte(t);
213 }
214 pub fn u64(&mut self, v: u64) {
215 for i in 0..8 {
216 self.byte((v >> (i * 8)) as u8);
217 }
218 }
219 pub fn i32(&mut self, v: i32) {
220 self.u64(v as i64 as u64);
221 }
222}
223impl Default for Fnv {
224 fn default() -> Self {
225 Self::new()
226 }
227}
228
229#[cfg(test)]
230mod tests {
231 use super::*;
232
233 #[test]
234 fn token_is_stable_and_distinct() {
235 let a = Effect::Write {
236 region: Region::Arg(0),
237 off: 8,
238 val: ValueClass::Input(1),
239 };
240 let b = Effect::Write {
241 region: Region::Arg(0),
242 off: 8,
243 val: ValueClass::Input(1),
244 };
245 let c = Effect::Write {
246 region: Region::Arg(0),
247 off: 16,
248 val: ValueClass::Input(1),
249 };
250 assert_eq!(a.token(), b.token());
251 assert_ne!(a.token(), c.token());
252 }
253
254 #[test]
255 fn complexity_withholds_tiny() {
256 let thunk = EffectTrace {
257 effects: vec![Effect::Ret(ValueClass::Input(0))],
258 instret: 2,
259 capped: false,
260 coverage: 1.0,
261 };
262 assert!(thunk.complexity() < 3);
263 let real = EffectTrace {
264 effects: vec![
265 Effect::NewRegion(Region::Arg(0)),
266 Effect::Write {
267 region: Region::Arg(0),
268 off: 0,
269 val: ValueClass::Input(1),
270 },
271 Effect::Call(CallTarget::Sym("memcpy".into())),
272 ],
273 instret: 40,
274 capped: false,
275 coverage: 1.0,
276 };
277 assert!(real.complexity() >= 3);
278 }
279}