puffin/algebra/
signature.rs

1use std::collections::HashMap;
2
3use itertools::Itertools;
4use libafl_bolts::rands::Rand;
5use once_cell::sync::Lazy;
6
7use super::atoms::Function;
8use crate::algebra::atoms::Variable;
9use crate::algebra::dynamic_function::{
10    make_dynamic, DescribableFunction, DynamicFunction, DynamicFunctionShape, FunctionAttributes,
11    TypeShape,
12};
13use crate::algebra::Matcher;
14use crate::protocol::ProtocolTypes;
15use crate::trace::{Query, Source};
16
17pub type FunctionDefinition<PT> = (DynamicFunctionShape<PT>, Box<dyn DynamicFunction<PT>>);
18
19/// Records a universe of functions.
20/// Signatures are containers for types and function symbols. They hold references to the concrete
21/// implementations of functions and the types of variables.
22pub struct Signature<PT: ProtocolTypes> {
23    pub functions_by_name: HashMap<&'static str, FunctionDefinition<PT>>,
24    pub functions_by_typ: HashMap<TypeShape<PT>, Vec<FunctionDefinition<PT>>>,
25    pub functions: Vec<FunctionDefinition<PT>>,
26    pub types_by_name: HashMap<&'static str, TypeShape<PT>>,
27    pub attrs_by_name: HashMap<&'static str, FunctionAttributes>,
28    /// Minimal generation depth and size per function symbol, see [`Self::min_gen_depth`] and
29    /// [`Self::min_gen_size`].
30    min_cost_by_name: HashMap<&'static str, Cost>,
31    /// Minimal generation depth and size per type, see [`Self::min_gen_depth_of_type`] and
32    /// [`Self::min_gen_size_of_type`].
33    min_cost_by_typ: HashMap<TypeShape<PT>, Cost>,
34    /// Per type, the symbols returning it, ordered by increasing minimal depth, see
35    /// [`Self::choose_function_within`].
36    functions_by_typ_by_depth: HashMap<TypeShape<PT>, DepthOrdered<PT>>,
37}
38
39/// What building the cheapest closed term rooted at a symbol (or of a type) costs.
40#[derive(Clone, Copy, Debug, PartialEq, Eq)]
41struct Cost {
42    /// Levels needed, in the sense of the term zoo's depth budget: `1` for a constant.
43    depth: u16,
44    /// Nodes needed, in the sense of [`crate::algebra::TermType::size`]: `1` for a constant.
45    size: usize,
46}
47
48/// The symbols returning one given type, ordered by increasing minimal generation depth, so that
49/// the ones that fit a depth budget are a prefix of `functions`.
50struct DepthOrdered<PT: ProtocolTypes> {
51    functions: Vec<FunctionDefinition<PT>>,
52    /// `costs[i]` is the minimal cost of `functions[i]`; sorted by increasing depth.
53    costs: Vec<Cost>,
54}
55
56impl<PT: ProtocolTypes> DepthOrdered<PT> {
57    /// Uniformly picks one of the symbols that can build a closed term within both budgets.
58    fn choose_within<R: Rand>(
59        &self,
60        depth: u16,
61        size: usize,
62        rand: &mut R,
63    ) -> Option<&FunctionDefinition<PT>> {
64        // Deep enough is a prefix (the costs are sorted by depth). Select uniformly among those
65        // also fitting the size budget, using reservoir sampling in one pass.
66        let deep_enough = self.costs.partition_point(|cost| cost.depth <= depth);
67        let mut seen = 0usize;
68        let mut chosen: Option<usize> = None;
69        for (index, cost) in self.costs[..deep_enough].iter().enumerate() {
70            if cost.size <= size {
71                seen += 1;
72                if rand.below_or_zero(seen) == 0 {
73                    chosen = Some(index);
74                }
75            }
76        }
77        chosen.map(|index| &self.functions[index])
78    }
79}
80
81impl<PT: ProtocolTypes> std::fmt::Debug for Signature<PT> {
82    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
83        writeln!(f, "functions; {:?}", self.functions)
84    }
85}
86
87impl<PT: ProtocolTypes> Signature<PT> {
88    /// Construct a `Signature` from the given [`FunctionDefinition`]s.
89    #[must_use]
90    pub fn new(definitions: Vec<(FunctionDefinition<PT>, FunctionAttributes)>) -> Self {
91        let attrs_by_name: HashMap<&'static str, FunctionAttributes> = definitions
92            .clone()
93            .iter()
94            .map(|((shape, _dynamic_fn), attrs)| (shape.name, *attrs))
95            .collect();
96        let functions_by_name: HashMap<&'static str, FunctionDefinition<PT>> = definitions
97            .clone()
98            .into_iter()
99            .map(|((shape, dynamic_fn), _attrs)| (shape.name, (shape, dynamic_fn)))
100            .collect();
101
102        let functions_by_typ: HashMap<TypeShape<PT>, Vec<FunctionDefinition<PT>>> = definitions
103            .clone()
104            .into_iter()
105            .map(|(fd, _attrs)| fd)
106            .into_group_map_by(|(shape, _dynamic_fn)| shape.return_type.clone());
107
108        let types_by_name: HashMap<&'static str, TypeShape<PT>> = definitions
109            .clone()
110            .into_iter()
111            .map(|((shape, _dynamic_fn), _attrs)| {
112                let used_types: Vec<TypeShape<PT>> = shape // vector of the argument shapes + return type
113                    .argument_types
114                    .iter()
115                    .cloned()
116                    .chain(vec![shape.return_type])
117                    .collect::<Vec<TypeShape<PT>>>();
118                used_types
119            })
120            .unique()
121            .flatten()
122            .map(|typ| (typ.name, typ))
123            .collect();
124
125        let (min_cost_by_name, min_cost_by_typ) = Self::compute_min_costs(&definitions);
126
127        let functions_by_typ_by_depth = functions_by_typ
128            .iter()
129            .map(|(typ, functions)| {
130                // Symbols with no closed term at any depth are dropped: no budget makes them
131                // usable, and keeping them would put them in the deep-enough prefix.
132                let mut ordered: Vec<(Cost, FunctionDefinition<PT>)> = functions
133                    .iter()
134                    .filter_map(|function| {
135                        min_cost_by_name
136                            .get(function.0.name)
137                            .map(|cost| (*cost, function.clone()))
138                    })
139                    .collect();
140                ordered.sort_by_key(|(cost, _)| cost.depth);
141                let (costs, functions) = ordered.into_iter().unzip();
142                (typ.clone(), DepthOrdered { functions, costs })
143            })
144            .collect();
145
146        Self {
147            functions_by_name,
148            functions_by_typ,
149            functions: definitions.into_iter().map(|(fd, _attrs)| fd).collect(),
150            types_by_name,
151            attrs_by_name,
152            min_cost_by_name,
153            min_cost_by_typ,
154            functions_by_typ_by_depth,
155        }
156    }
157
158    /// Least fixed point of
159    /// - `depth(f) = 1 + max { depth(t) | t argument type of f }` (so `1` for a constant),
160    /// - `size(f) = 1 + sum { size(t) | t argument type of f }` (so `1` for a constant),
161    /// - `cost(t) = the pointwise min over the symbols returning t`.
162    ///
163    /// Symbols with an argument type no function can build, and the types only such symbols
164    /// return, are absent from the returned maps: no closed term exists for them at any cost.
165    fn compute_min_costs(
166        definitions: &[(FunctionDefinition<PT>, FunctionAttributes)],
167    ) -> (HashMap<&'static str, Cost>, HashMap<TypeShape<PT>, Cost>) {
168        use std::collections::hash_map::Entry;
169
170        /// Records `cost` for `key`, keeping the best of each component. Returns whether the map
171        /// changed.
172        fn improve<K: Eq + std::hash::Hash>(
173            map: &mut HashMap<K, Cost>,
174            key: K,
175            cost: Cost,
176        ) -> bool {
177            match map.entry(key) {
178                Entry::Vacant(entry) => {
179                    entry.insert(cost);
180                    true
181                }
182                Entry::Occupied(mut entry) => {
183                    let best = Cost {
184                        depth: entry.get().depth.min(cost.depth),
185                        size: entry.get().size.min(cost.size),
186                    };
187                    let changed = best != *entry.get();
188                    entry.insert(best);
189                    changed
190                }
191            }
192        }
193
194        let mut by_name: HashMap<&'static str, Cost> = HashMap::new();
195        let mut by_typ: HashMap<TypeShape<PT>, Cost> = HashMap::new();
196
197        // Each round either adds an entry or strictly decreases one, and both components are
198        // bounded below by 1, so this terminates. In practice it converges in as many rounds as
199        // the deepest chain of types, and it runs once per signature at start-up.
200        loop {
201            let mut changed = false;
202
203            for ((shape, _dynamic_fn), _attrs) in definitions {
204                let mut cost = Cost { depth: 1, size: 1 };
205                let mut buildable = true;
206                for argument in &shape.argument_types {
207                    match by_typ.get(argument) {
208                        Some(argument_cost) => {
209                            cost.depth = cost.depth.max(argument_cost.depth.saturating_add(1));
210                            cost.size = cost.size.saturating_add(argument_cost.size);
211                        }
212                        None => {
213                            // No closed term for that argument type (yet)
214                            buildable = false;
215                            break;
216                        }
217                    }
218                }
219                if !buildable {
220                    continue;
221                }
222
223                changed |= improve(&mut by_name, shape.name, cost);
224                changed |= improve(&mut by_typ, shape.return_type.clone(), cost);
225            }
226
227            if !changed {
228                break;
229            }
230        }
231
232        (by_name, by_typ)
233    }
234
235    /// The minimal depth at which the term zoo can build a closed term rooted at `name`: `1` for a
236    /// constant, `1 + max` over the argument types otherwise. Matches the budget accounting of
237    /// [`crate::fuzzer::term_zoo`], so a generation attempt for `name` with a budget below this can
238    /// only fail.
239    ///
240    /// `None` when no closed term is rooted at `name` at any depth (some argument type has no
241    /// closed term), which also means `name` is unknown to this signature.
242    #[must_use]
243    pub fn min_gen_depth(&self, name: &str) -> Option<u16> {
244        self.min_cost_by_name.get(name).map(|cost| cost.depth)
245    }
246
247    /// The size, in nodes, of the smallest closed term rooted at `name`: `1` for a constant,
248    /// `1 + sum` over the argument types otherwise. Same conventions as [`Self::min_gen_depth`].
249    #[must_use]
250    pub fn min_gen_size(&self, name: &str) -> Option<usize> {
251        self.min_cost_by_name.get(name).map(|cost| cost.size)
252    }
253
254    /// Same as [`Self::min_gen_depth`], for the shallowest closed term of the given type.
255    #[must_use]
256    pub fn min_gen_depth_of_type(&self, typ: &TypeShape<PT>) -> Option<u16> {
257        self.min_cost_by_typ.get(typ).map(|cost| cost.depth)
258    }
259
260    /// Same as [`Self::min_gen_size`], for the smallest closed term of the given type.
261    ///
262    /// Note this is a lower bound rather than an achievable cost: the shallowest and the smallest
263    /// term of a type need not be the same one, and the two components are minimised separately.
264    #[must_use]
265    pub fn min_gen_size_of_type(&self, typ: &TypeShape<PT>) -> Option<usize> {
266        self.min_cost_by_typ.get(typ).map(|cost| cost.size)
267    }
268
269    /// Uniformly picks a symbol of the given type that the term zoo can build a closed term for
270    /// within `depth` levels and `size` nodes.
271    ///
272    /// `None` when the type is unknown or when no symbol of that type is that cheap.
273    pub fn choose_function_within<R: Rand>(
274        &self,
275        typ: &TypeShape<PT>,
276        depth: u16,
277        size: usize,
278        rand: &mut R,
279    ) -> Option<&FunctionDefinition<PT>> {
280        self.functions_by_typ_by_depth
281            .get(typ)?
282            .choose_within(depth, size, rand)
283    }
284
285    /// Create a new [`Function`] distinct from all existing [`Function`]s.
286    pub fn new_function<F: 'static + DescribableFunction<PT, Types>, Types>(
287        f: &'static F,
288    ) -> Function<PT> {
289        let (shape, dynamic_fn) = make_dynamic(f);
290
291        Function::new(shape, dynamic_fn.clone())
292    }
293
294    #[must_use]
295    pub fn new_var_with_type<T: 'static, M: Matcher>(
296        source: Option<Source>,
297        matcher: Option<M>,
298        counter: u16,
299    ) -> Variable<PT>
300    where
301        PT: ProtocolTypes<Matcher = M>,
302    {
303        let type_shape = TypeShape::<PT>::of::<T>();
304        Self::new_var(type_shape, source, matcher, counter)
305    }
306
307    #[must_use]
308    pub fn new_var<M: Matcher>(
309        type_shape: TypeShape<PT>,
310        source: Option<Source>,
311        matcher: Option<M>,
312        counter: u16,
313    ) -> Variable<PT>
314    where
315        PT: ProtocolTypes<Matcher = M>,
316    {
317        let query = Query {
318            source,
319            matcher,
320            counter,
321        };
322        Variable::new(type_shape, query)
323    }
324}
325
326pub type StaticSignature<PT> = Lazy<Signature<PT>>;
327
328pub const fn create_static_signature<PT: ProtocolTypes>(
329    init: fn() -> Signature<PT>,
330) -> StaticSignature<PT> {
331    Lazy::new(init)
332}
333
334#[macro_export]
335macro_rules! define_signature {
336    ($name_signature:ident<$protocol_types:ident>, $($f:path $([$flags:expr])*)+) => {
337        use $crate::algebra::signature::create_static_signature;
338        use $crate::algebra::signature::StaticSignature;
339        use $crate::algebra::signature::Signature;
340
341        /// Signature which contains all functions defined in the `tls` module. A signature is responsible
342        /// for linking function implementations to serialized data.
343        ///
344        /// Note: Changes in function symbols may cause deserialization of term to fail.
345        #[allow(unused_mut)]
346        pub static $name_signature: StaticSignature<$protocol_types> = create_static_signature(|| {
347
348            let definitions = vec![
349                $(
350                    {
351                        let mut attrs = FunctionAttributes::default();
352                        {  // Process option attributes
353                            $(
354                                let flag = stringify!($flags);
355                                match flag {
356                                    "opaque" => attrs.is_opaque = true,
357                                    "list" => attrs.is_list = true,
358                                    "get" => attrs.is_get = true,
359                                    "no_gen" => attrs.no_gen = true,
360                                    "no_bit" => attrs.no_bit = true,
361                                    "no_det" => attrs.no_det = true,
362                                    _ => {},
363                                }
364                            )*
365                        }
366                        ($crate::algebra::dynamic_function::make_dynamic(&$f), attrs)
367                    }
368                ),+
369            ];
370            Signature::new(definitions)
371        });
372    };
373}