puffin/
claims.rs

1use std::any::TypeId;
2use std::cell::{Ref, RefCell, RefMut};
3use std::collections::HashMap;
4use std::fmt::Debug;
5use std::ops::Deref;
6use std::rc::Rc;
7use std::slice::{Iter, IterMut};
8
9use comparable::Comparable;
10use itertools::Itertools;
11
12use crate::agent::AgentName;
13use crate::algebra::dynamic_function::TypeShape;
14use crate::differential::{ClaimDiff, TraceDifference};
15use crate::protocol::{EvaluatedTerm, ProtocolTypes};
16use crate::trace::StepNumber;
17
18pub trait Claim: EvaluatedTerm<Self::PT> + Debug + Comparable + PartialEq {
19    type PT: ProtocolTypes;
20
21    fn agent_name(&self) -> AgentName;
22    fn id(&self) -> TypeShape<Self::PT>;
23    fn inner(&self) -> Box<dyn EvaluatedTerm<Self::PT>>;
24    fn set_step(&mut self, step: Option<StepNumber>);
25    fn get_step(&self) -> Option<StepNumber>;
26}
27
28pub trait SecurityViolationPolicy {
29    type C: Claim;
30
31    fn check_violation(claims: &[Self::C]) -> Option<&'static str>;
32}
33
34#[derive(Default, Clone, Debug, PartialEq)]
35pub struct ClaimList<C: Claim> {
36    claims: Vec<C>,
37}
38
39impl<C: Claim> ClaimList<C> {
40    pub fn iter(&self) -> Iter<'_, C> {
41        self.claims.iter()
42    }
43
44    pub fn iter_mut(&mut self) -> IterMut<'_, C> {
45        self.claims.iter_mut()
46    }
47
48    /// finds the last claim matching `type`
49    #[must_use]
50    pub fn find_last_claim_by_type<T: 'static>(&self, agent_name: AgentName) -> Option<&C> {
51        self.find_last_claim(agent_name, TypeShape::<C::PT>::of::<T>())
52    }
53
54    #[must_use]
55    pub fn find_last_claim(&self, agent_name: AgentName, shape: TypeShape<C::PT>) -> Option<&C> {
56        self.claims
57            .iter()
58            .rev()
59            .find(|claim| claim.id() == shape && claim.agent_name() == agent_name)
60    }
61
62    #[must_use]
63    pub fn slice(&self) -> &[C] {
64        &self.claims
65    }
66}
67
68impl<C: Claim> ClaimList<C> {
69    pub fn log(&self) {
70        // TODO: skip logging completely during fuzzing -> more performance
71        log::debug!(
72            "New Claims: {}",
73            &self
74                .claims
75                .iter()
76                .map(|claim| claim.type_name().to_string())
77                .join(", ")
78        );
79        for claim in &self.claims {
80            log::trace!("{:?}", claim);
81        }
82    }
83}
84
85impl<C: Claim> From<Vec<C>> for ClaimList<C> {
86    fn from(claims: Vec<C>) -> Self {
87        Self { claims }
88    }
89}
90
91fn filter_claims<C: Claim>(claim: &C, blacklist: &Option<Vec<TypeId>>) -> bool {
92    if let Some(b) = blacklist {
93        if b.iter().any(|x| *x == claim.id().into()) {
94            return false;
95        }
96    }
97
98    true
99}
100
101impl<C: Claim> ClaimList<C> {
102    #[must_use]
103    pub const fn new() -> Self {
104        Self { claims: vec![] }
105    }
106
107    pub fn claim_sized(&mut self, mut claim: C) {
108        claim.set_step(None);
109        self.claims.push(claim);
110    }
111
112    /// compares two claim lists and returns a list of differences
113    pub fn compare(&self, other: &Self) -> Result<(), Vec<TraceDifference>> {
114        let blacklist = <C::PT as ProtocolTypes>::differential_fuzzing_claims_blacklist();
115
116        // filter out claims that are in the blacklist and group them by agent
117        let mut self_claims_filtered: HashMap<AgentName, Vec<&C>> = self
118            .claims
119            .iter()
120            .filter(|x| filter_claims(*x, &blacklist))
121            .fold(HashMap::new(), |mut acc, c| {
122                acc.entry(c.agent_name()).or_insert(vec![]).push(c);
123                acc
124            });
125
126        let mut other_claims_filtered: HashMap<AgentName, Vec<&C>> = other
127            .claims
128            .iter()
129            .filter(|x| filter_claims(*x, &blacklist))
130            .fold(HashMap::new(), |mut acc, c| {
131                acc.entry(c.agent_name()).or_insert(vec![]).push(c);
132                acc
133            });
134
135        // deduplicate similar adjacent claims, keeping the order
136        self_claims_filtered.iter_mut().for_each(|(_, v)| {
137            v.dedup_by(|x, y| x.comparison(y) == comparable::Changed::Unchanged)
138        });
139
140        other_claims_filtered.iter_mut().for_each(|(_, v)| {
141            v.dedup_by(|x, y| x.comparison(y) == comparable::Changed::Unchanged)
142        });
143
144        log::trace!("Comparing claim lists");
145
146        let mut keys: Vec<_> = self_claims_filtered
147            .keys()
148            .into_iter()
149            .chain(other_claims_filtered.keys().into_iter())
150            .collect();
151        keys.sort();
152
153        let mut diffs = vec![];
154
155        // for each agent, compare the claims of both lists and find differences in types and inner
156        // values
157        for k in keys.iter().dedup() {
158            let empty = vec![];
159            let s = self_claims_filtered.get(k).unwrap_or(&empty);
160            let o = other_claims_filtered.get(k).unwrap_or(&empty);
161
162            for i in 0..usize::max(s.len(), o.len()) {
163                match (s.get(i), o.get(i)) {
164                    (None, Some(b)) => {
165                        diffs.push(TraceDifference::Claims(ClaimDiff::DifferentTypes {
166                            agent: b.agent_name().into(),
167                            index: i,
168                            first_type: "()".into(),
169                            second_type: b.inner().type_name().into(),
170                        }))
171                    }
172                    (Some(a), None) => {
173                        diffs.push(TraceDifference::Claims(ClaimDiff::DifferentTypes {
174                            agent: a.agent_name().into(),
175                            index: i,
176                            first_type: a.inner().type_name().into(),
177                            second_type: "()".into(),
178                        }))
179                    }
180                    (Some(a), Some(b)) => match a.comparison(b) {
181                        comparable::Changed::Changed(changes) => {
182                            diffs.push(TraceDifference::Claims(ClaimDiff::InnerDifference {
183                                agent: a.agent_name().into(),
184                                index: i,
185                                diff: format!("{:?}", changes),
186                            }))
187                        }
188                        comparable::Changed::Unchanged => (),
189                    },
190                    _ => (),
191                }
192            }
193        }
194
195        if diffs.len() > 0 {
196            Err(diffs)
197        } else {
198            Ok(())
199        }
200    }
201}
202
203#[derive(Default, Clone, PartialEq, Debug)]
204pub struct GlobalClaimList<C: Claim> {
205    claims: Rc<RefCell<ClaimList<C>>>,
206}
207
208impl<C: Claim> GlobalClaimList<C> {
209    #[must_use]
210    pub fn new() -> Self {
211        Self {
212            claims: Rc::new(RefCell::new(ClaimList::new())),
213        }
214    }
215
216    #[must_use]
217    pub fn deref_borrow(&self) -> Ref<'_, ClaimList<C>> {
218        self.claims.deref().borrow()
219    }
220
221    #[must_use]
222    pub fn deref_borrow_mut(&self) -> RefMut<'_, ClaimList<C>> {
223        self.claims.deref().borrow_mut()
224    }
225
226    pub fn compare(&self, other: &Self) -> Result<(), Vec<TraceDifference>> {
227        self.claims.borrow().compare(&other.claims.borrow())
228    }
229}