puffin/algebra/
dynamic_function.rs

1//! This module provides traits for calling rust functions dynamically.
2//!
3//! All functions which implement the `DynamicFunction` trait can be called by passing an array of
4//! [`EvaluatedTerm`]s to it. The return value is again of type [`EvaluatedTerm`].
5//!
6//! Rust is a statically typed language. That means the compiler would be able to statically verify
7//! that a term evaluates without any type errors.
8//!
9//! While this is generally an advance, in the case of our fuzzer this is not very helpful.
10//! The fuzzer should be able to mutate the term trees arbitrarily. Of course, we also have
11//! to check for the types during runtime. If types are not compatible then, the evaluation
12//! of the term will fail. But this is not something that can be done during compile time.
13//! Therefore, we introduced a trait for dynamically typed functions on top of statically
14//! typed Rust functions.
15//!
16//! Each function which implements the following trait can be made into a dynamic function:
17//!
18//! ```rust
19//! use puffin::algebra::error::FnError;
20//!
21//! type ConcreteFunction<A1, A2, A3, R> = dyn Fn(A1, A2, A3) -> Result<R, FnError>;
22//! ```
23//!
24//! where `A1`, `A2`, `A3` are argument types and `R` is the return type. From these statically
25//! typed function we can generate dynamically types ones which implement the following trait:
26//!
27//! ```rust
28//! use std::any::Any;
29//!
30//! use puffin::algebra::error::FnError;
31//! use puffin::protocol::{EvaluatedTerm, ProtocolTypes};
32//!
33//! pub trait DynamicFunction<PT: ProtocolTypes>:
34//!     Fn(&Vec<Box<dyn EvaluatedTerm<PT>>>) -> Result<Box<dyn EvaluatedTerm<PT>>, FnError>
35//! {
36//! }
37//! ```
38//!
39//! Note, that both functions return a `Result` and therefore can gracefully fail.
40//!
41//! `DynamicFunctions` can be called with an array of any type implementing the `EvaluatedTerm`
42//! trait. The result must also implement `EvaluatedTerm`. Rust offers a unique ID for each type.
43//! Using this type we can check during runtime whether types are available. The types of each
44//! variable, constant and function are preserved and stored alongside the `DynamicFunction`.
45//!
46//! The following function is a simple example for a constant:
47//!
48//! ```rust
49//! use puffin::algebra::error::FnError;
50//!
51//! pub fn fn_some_value() -> Result<u32, FnError> {
52//!     Ok(42)
53//! }
54//! ```
55//!
56//! It returns one possibility for the cipher suites which could be sent during a `ClientHello`.
57use std::any::{type_name, TypeId};
58use std::collections::hash_map::DefaultHasher;
59use std::fmt;
60use std::hash::{Hash, Hasher};
61use std::marker::PhantomData;
62
63use itertools::Itertools;
64use serde::de::Visitor;
65use serde::{de, Deserialize, Deserializer, Serialize, Serializer};
66
67use super::error::FnError;
68use crate::protocol::{EvaluatedTerm, ProtocolTypes};
69
70/// Describes the attributes of a [`DynamicFunction`]
71#[derive(Serialize, Deserialize, Debug, Clone, Copy, Default)]
72pub struct FunctionAttributes {
73    /// Whether the function symbol computes "opaque" message such as encryption, signature,
74    /// MAC, AEAD, Formally: all symbols whose concretization does not contain a single
75    /// conretization of its arguments
76    pub is_opaque: bool,
77    /// Whether the function symbol computes a list such as `fn_append_certificate`.
78    pub is_list: bool,
79    /// Whether the function symbol computes a strict sub-term (accessed function symbols).
80    /// Incidentally, its concretization does not contain all the conretizations of its arguments.
81    /// Examples: `fn_get_server_key_share`.
82    pub is_get: bool,
83    /// Whether we usually fail and thus prevent from trying to generate terms with that function
84    /// symbols at top-level. This will reduce the scope of the GenerateMutator.
85    pub no_gen: bool,
86    /// Symbols we will never MakeMessage on, thus disabling applying any of the bit-level
87    /// mutations.
88    pub no_bit: bool,
89    /// Symbols for which computations are not deterministic
90    pub no_det: bool,
91}
92// TODO: add a uni test for making sure the given attributes are correct
93
94/// Describes the shape of a [`DynamicFunction`]
95#[derive(Serialize, Deserialize, Debug, Clone)]
96#[serde(bound = "PT: ProtocolTypes")]
97pub struct DynamicFunctionShape<PT: ProtocolTypes> {
98    pub name: &'static str,
99    pub argument_types: Vec<TypeShape<PT>>,
100    pub return_type: TypeShape<PT>,
101}
102
103impl<PT: ProtocolTypes> Eq for DynamicFunctionShape<PT> {}
104impl<PT: ProtocolTypes> PartialEq for DynamicFunctionShape<PT> {
105    fn eq(&self, other: &Self) -> bool {
106        self.name.eq(other.name) // name is unique
107    }
108}
109
110impl<PT: ProtocolTypes> Hash for DynamicFunctionShape<PT> {
111    fn hash<H: Hasher>(&self, state: &mut H) {
112        self.name.hash(state);
113    }
114}
115
116impl<PT: ProtocolTypes> DynamicFunctionShape<PT> {
117    #[must_use]
118    pub fn arity(&self) -> u16 {
119        self.argument_types.len() as u16
120    }
121
122    #[must_use]
123    pub fn is_constant(&self) -> bool {
124        self.arity() == 0
125    }
126}
127
128impl<PT: ProtocolTypes> fmt::Display for DynamicFunctionShape<PT> {
129    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
130        write!(
131            f,
132            "{}({}) -> {}",
133            self.name,
134            self.argument_types
135                .iter()
136                .map(|typ| typ.name.to_string())
137                .join(","),
138            self.return_type.name
139        )
140    }
141}
142
143/// Hashes [`TypeId`]s to be more readable
144fn hash_type_id(type_id: &TypeId) -> u64 {
145    let mut hasher = DefaultHasher::new();
146    type_id.hash(&mut hasher);
147    hasher.finish()
148}
149
150fn format_args<PT: ProtocolTypes, P: AsRef<dyn EvaluatedTerm<PT>>>(anys: &[P]) -> String {
151    format!(
152        "({})",
153        anys.iter()
154            .map(|any| {
155                let id = &any.as_ref().as_any().type_id();
156                format!("{:x}", hash_type_id(id))
157            })
158            .join(",")
159    )
160}
161
162/// Cloneable type for dynamic functions. This trait is automatically implemented for arbitrary
163/// closures and functions of the form: `Fn(&Vec<Box<dyn Any>>) -> Box<dyn Any>`
164///
165/// [`Clone`] is implemented for `Box<dyn DynamicFunction>` using this trick:
166/// <https://users.rust-lang.org/t/how-to-clone-a-boxed-closure/31035/25>
167///
168/// We want to use Any here and not `VariableData` (which implements Clone). Else all returned types
169/// in functions `op_impl.rs` would need to return a cloneable struct. Message for example is not.
170pub trait DynamicFunction<PT: ProtocolTypes>:
171    Fn(&Vec<Box<dyn EvaluatedTerm<PT>>>) -> Result<Box<dyn EvaluatedTerm<PT>>, FnError> + Send + Sync
172{
173    fn clone_box(&self) -> Box<dyn DynamicFunction<PT>>;
174}
175
176impl<F, PT: ProtocolTypes> DynamicFunction<PT> for F
177where
178    F: 'static
179        + Fn(&Vec<Box<dyn EvaluatedTerm<PT>>>) -> Result<Box<dyn EvaluatedTerm<PT>>, FnError>
180        + Clone
181        + Send
182        + Sync,
183{
184    fn clone_box(&self) -> Box<dyn DynamicFunction<PT>> {
185        Box::new(self.clone())
186    }
187}
188
189impl<PT: ProtocolTypes> fmt::Debug for Box<dyn DynamicFunction<PT>> {
190    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
191        write!(f, "DynamicFunction")
192    }
193}
194
195impl<PT: ProtocolTypes> fmt::Display for Box<dyn DynamicFunction<PT>> {
196    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
197        write!(f, "DynamicFunction")
198    }
199}
200
201impl<PT: ProtocolTypes> Clone for Box<dyn DynamicFunction<PT>> {
202    fn clone(&self) -> Self {
203        (**self).clone_box()
204    }
205}
206
207/// This trait is implemented for function traits in order to:
208/// * describe their shape during runtime
209/// * wrap them into a [`DynamicFunction`] which is callable with arbitrary data
210///
211/// Adapted from <https://jsdw.me/posts/rust-fn-traits/> but using type ids
212pub trait DescribableFunction<PT: ProtocolTypes, Types> {
213    fn name(&'static self) -> &'static str;
214    fn shape() -> DynamicFunctionShape<PT>;
215    fn make_dynamic(&'static self) -> Box<dyn DynamicFunction<PT>>;
216}
217
218macro_rules! dynamic_fn {
219    ($($arg:ident)* => $res:ident) => (
220    impl<F,PT : ProtocolTypes, $res: 'static, $($arg: 'static),*>
221        DescribableFunction<PT, ($res, $($arg),*)> for F
222    where
223        F: (Fn($(&$arg),*)  -> Result<$res, FnError>) + Send + Sync,
224        $res: Send + Sync,
225        R: EvaluatedTerm<PT>,
226        $($arg: Send + Sync),*
227    {
228        fn shape() -> DynamicFunctionShape<PT> {
229            DynamicFunctionShape::<PT> {
230                name: std::any::type_name::<F>(),
231                argument_types: vec![$(TypeShape::<PT>::of::<$arg>()),*],
232                return_type: TypeShape::<PT>::of::<$res>(),
233            }
234        }
235
236        fn name(&'static self) -> &'static str {
237            std::any::type_name::<F>()
238        }
239
240        fn make_dynamic(&'static self) -> Box<dyn DynamicFunction<PT>> {
241            #[allow(unused_variables)]
242            Box::new(move |args: &Vec<Box<dyn EvaluatedTerm<PT>>>| {
243                #[allow(unused_mut)]
244                let mut index = 0;
245
246                let result: Result<$res, FnError> = self($(
247                       #[allow(unused_assignments)]
248                       #[allow(clippy::mixed_read_write_in_expression)]
249                       {
250                           if let Some(arg_) = args.get(index)
251                                    .ok_or_else(|| {
252                                        let shape = Self::shape();
253                                        FnError::Malformed(format!("Missing argument #{} while calling {}.", index + 1, shape.name))
254                                    })?
255                                    .as_any().downcast_ref::<$arg>() {
256                               index += 1;
257                               arg_
258                           } else {
259                               let shape = Self::shape();
260                               return Err(FnError::Malformed(format!(
261                                    "Passed argument #{} of {} did not match the shape {}. Hashes of passed types are {}.",
262                                    index + 1,
263                                    shape.name,
264                                    shape,
265                                    format_args(args)
266                               )));
267                           }
268                       }
269                ),*);
270
271                result.map(|result| Box::new(result) as Box<dyn EvaluatedTerm<PT>>)
272            })
273        }
274    }
275    )
276}
277
278dynamic_fn!( => R);
279dynamic_fn!(T1 => R);
280dynamic_fn!(T1 T2 => R);
281dynamic_fn!(T1 T2 T3 => R);
282dynamic_fn!(T1 T2 T3 T4 => R);
283dynamic_fn!(T1 T2 T3 T4 T5 => R);
284dynamic_fn!(T1 T2 T3 T4 T5 T6 => R);
285dynamic_fn!(T1 T2 T3 T4 T5 T6 T7 => R);
286dynamic_fn!(T1 T2 T3 T4 T5 T6 T7 T8 => R);
287dynamic_fn!(T1 T2 T3 T4 T5 T6 T7 T8 T9 => R);
288dynamic_fn!(T1 T2 T3 T4 T5 T6 T7 T8 T9 T10 => R);
289
290pub fn make_dynamic<F: 'static + DescribableFunction<PT, Types>, PT: ProtocolTypes, Types>(
291    f: &'static F,
292) -> (DynamicFunctionShape<PT>, Box<dyn DynamicFunction<PT>>) {
293    (F::shape(), f.make_dynamic())
294}
295
296#[derive(Copy, Clone, Debug)]
297pub struct TypeShape<PT: ProtocolTypes> {
298    inner_type_id: TypeId,
299    pub name: &'static str,
300    phantom: PhantomData<PT>,
301}
302
303impl<PT: ProtocolTypes> TypeShape<PT> {
304    #[must_use]
305    pub fn of<T: 'static>() -> Self {
306        Self {
307            inner_type_id: TypeId::of::<T>(),
308            name: type_name::<T>(),
309            phantom: PhantomData,
310        }
311    }
312}
313
314impl<PT: ProtocolTypes> From<TypeShape<PT>> for TypeId {
315    fn from(shape: TypeShape<PT>) -> Self {
316        shape.inner_type_id
317    }
318}
319
320impl<PT: ProtocolTypes> Eq for TypeShape<PT> {}
321impl<PT: ProtocolTypes> PartialEq for TypeShape<PT> {
322    fn eq(&self, other: &Self) -> bool {
323        self.inner_type_id == other.inner_type_id
324    }
325}
326
327impl<PT: ProtocolTypes> Hash for TypeShape<PT> {
328    fn hash<H: Hasher>(&self, state: &mut H) {
329        self.inner_type_id.hash(state);
330    }
331}
332
333impl<PT: ProtocolTypes> fmt::Display for TypeShape<PT> {
334    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
335        write!(f, "{}", self.name)
336    }
337}
338
339impl<PT: ProtocolTypes> Serialize for TypeShape<PT> {
340    fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
341    where
342        S: Serializer,
343    {
344        serializer.serialize_str(self.name)
345    }
346}
347
348impl<'de, PT: ProtocolTypes> Deserialize<'de> for TypeShape<PT> {
349    fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
350    where
351        D: Deserializer<'de>,
352    {
353        struct TypeShapeVisitor<PT: ProtocolTypes>(PhantomData<PT>);
354
355        impl<'de, PT: ProtocolTypes> Visitor<'de> for TypeShapeVisitor<PT> {
356            type Value = TypeShape<PT>;
357
358            fn expecting(&self, formatter: &mut fmt::Formatter) -> fmt::Result {
359                formatter.write_str("a TypeShape")
360            }
361
362            fn visit_str<E>(self, v: &str) -> Result<Self::Value, E>
363            where
364                E: de::Error,
365            {
366                let typ = PT::signature()
367                    .types_by_name
368                    .get(v)
369                    .ok_or_else(|| de::Error::missing_field("could not find type"))?;
370                Ok(typ.clone())
371            }
372        }
373
374        deserializer.deserialize_str(TypeShapeVisitor(PhantomData))
375    }
376}