stix_matcher/
eval.rs

1//! Evaluation: leaf comparisons, comparison expressions, and observation expressions.
2
3use std::collections::BTreeMap;
4
5use stix_model::{ObjectStore, ObjectView, StixValue};
6use stix_pattern::ast::{
7    Comparison, ComparisonExpression, ComparisonOperand, ComparisonOperator, Literal,
8    ObservationExpression, Pattern,
9};
10
11use crate::compare::{value_cmp_literal, value_eq_literal, value_in_set};
12use crate::error::MatchError;
13use crate::observation::Observation;
14use crate::pattern_ops::{like_matches, regex_matches};
15use crate::resolve::resolve_path;
16use crate::result::MatchResult;
17use crate::subset::{is_subset, is_superset};
18
19/// Evaluate a single `Comparison` against a single object, dereferencing through
20/// `store` where the path requires it. Honors the leaf's `negated` flag.
21pub fn eval_comparison(obj: &dyn ObjectView, c: &Comparison, store: Option<&ObjectStore>) -> bool {
22    let values = resolve_path(obj, &c.path, store);
23
24    let base = if c.operator == ComparisonOperator::Exists {
25        !values.is_empty()
26    } else {
27        values
28            .iter()
29            .any(|v| operator_holds(v, c.operator, &c.value))
30    };
31
32    base ^ c.negated
33}
34
35/// Whether a single resolved value satisfies a (non-EXISTS) operator + operand.
36fn operator_holds(value: &StixValue, op: ComparisonOperator, operand: &ComparisonOperand) -> bool {
37    use std::cmp::Ordering;
38
39    // `IN` is the only operator that takes a set operand.
40    if op == ComparisonOperator::In {
41        return match operand {
42            ComparisonOperand::Set(set) => value_in_set(value, set),
43            ComparisonOperand::Literal(lit) => value_in_set(value, std::slice::from_ref(lit)),
44        };
45    }
46
47    let lit = match operand {
48        ComparisonOperand::Literal(l) => l,
49        // A non-IN operator with a set operand is ill-formed; never matches.
50        ComparisonOperand::Set(_) => return false,
51    };
52
53    match op {
54        ComparisonOperator::Equal => value_eq_literal(value, lit),
55        ComparisonOperator::NotEqual => !value_eq_literal(value, lit),
56        ComparisonOperator::GreaterThan => value_cmp_literal(value, lit) == Some(Ordering::Greater),
57        ComparisonOperator::GreaterThanOrEqual => matches!(
58            value_cmp_literal(value, lit),
59            Some(Ordering::Greater | Ordering::Equal)
60        ),
61        ComparisonOperator::LessThan => value_cmp_literal(value, lit) == Some(Ordering::Less),
62        ComparisonOperator::LessThanOrEqual => matches!(
63            value_cmp_literal(value, lit),
64            Some(Ordering::Less | Ordering::Equal)
65        ),
66        ComparisonOperator::Like => string_op(value, lit, like_matches),
67        ComparisonOperator::Matches => string_op(value, lit, regex_matches),
68        ComparisonOperator::IsSubset => string_op(value, lit, is_subset),
69        ComparisonOperator::IsSuperset => string_op(value, lit, is_superset),
70        // Handled above / not reachable here.
71        ComparisonOperator::In | ComparisonOperator::Exists => false,
72    }
73}
74
75/// Apply a `(value_str, literal_str) -> bool` operator, requiring both sides to be
76/// strings.
77fn string_op(value: &StixValue, lit: &Literal, f: impl Fn(&str, &str) -> bool) -> bool {
78    let v = match value.as_str() {
79        Some(s) => s,
80        None => return false,
81    };
82    let l = match lit {
83        Literal::String(s) | Literal::Timestamp(s) | Literal::Binary(s) | Literal::Hex(s) => s,
84        _ => return false,
85    };
86    f(v, l)
87}
88
89/// Evaluate a comparison expression against one observation using binding
90/// enumeration: each distinct referenced object-type is bound to one object of
91/// that type from the observation (or none); the expression matches if some
92/// binding makes the boolean tree true. This gives correct "same object" semantics
93/// for `AND` within an observation while staying cheap (observations are small).
94pub fn eval_comparison_expression(
95    expr: &ComparisonExpression,
96    observation: &Observation,
97    store: Option<&ObjectStore>,
98) -> bool {
99    // Distinct object types referenced anywhere in the expression.
100    let mut types: Vec<String> = Vec::new();
101    collect_types(expr, &mut types);
102
103    // Candidate objects per referenced type (indices into observation.objects).
104    let candidates: Vec<Vec<usize>> = types
105        .iter()
106        .map(|t| {
107            observation
108                .objects
109                .iter()
110                .enumerate()
111                .filter(|(_, o)| o.type_() == Some(t.as_str()))
112                .map(|(i, _)| i)
113                .collect()
114        })
115        .collect();
116
117    // Enumerate one choice per type (or `None` when a type has no candidate).
118    let mut binding: BTreeMap<String, usize> = BTreeMap::new();
119    enumerate_bindings(&types, &candidates, 0, &mut binding, &|binding| {
120        eval_tree(expr, observation, binding, store)
121    })
122}
123
124/// Recursively collect distinct object types referenced by an expression's leaves.
125fn collect_types(expr: &ComparisonExpression, out: &mut Vec<String>) {
126    match expr {
127        ComparisonExpression::Test(c) => {
128            if !out.contains(&c.path.object_type) {
129                out.push(c.path.object_type.clone());
130            }
131        }
132        ComparisonExpression::And(a, b) | ComparisonExpression::Or(a, b) => {
133            collect_types(a, out);
134            collect_types(b, out);
135        }
136    }
137}
138
139/// Try every assignment of one candidate object per type; return true as soon as
140/// `predicate` accepts a binding. Types with no candidates are simply absent from
141/// the binding map (their leaves evaluate to false).
142fn enumerate_bindings(
143    types: &[String],
144    candidates: &[Vec<usize>],
145    idx: usize,
146    binding: &mut BTreeMap<String, usize>,
147    predicate: &dyn Fn(&BTreeMap<String, usize>) -> bool,
148) -> bool {
149    if idx == types.len() {
150        return predicate(binding);
151    }
152    if candidates[idx].is_empty() {
153        // No object of this type; leave it unbound and continue.
154        return enumerate_bindings(types, candidates, idx + 1, binding, predicate);
155    }
156    for &obj_idx in &candidates[idx] {
157        binding.insert(types[idx].clone(), obj_idx);
158        if enumerate_bindings(types, candidates, idx + 1, binding, predicate) {
159            binding.remove(&types[idx]);
160            return true;
161        }
162    }
163    binding.remove(&types[idx]);
164    false
165}
166
167/// Evaluate the boolean tree under a fixed binding.
168fn eval_tree(
169    expr: &ComparisonExpression,
170    observation: &Observation,
171    binding: &BTreeMap<String, usize>,
172    store: Option<&ObjectStore>,
173) -> bool {
174    match expr {
175        ComparisonExpression::Test(c) => match binding.get(&c.path.object_type) {
176            Some(&obj_idx) => eval_comparison(&observation.objects[obj_idx], c, store),
177            None => false,
178        },
179        ComparisonExpression::And(a, b) => {
180            eval_tree(a, observation, binding, store) && eval_tree(b, observation, binding, store)
181        }
182        ComparisonExpression::Or(a, b) => {
183            eval_tree(a, observation, binding, store) || eval_tree(b, observation, binding, store)
184        }
185    }
186}
187
188/// Evaluate a whole pattern against a list of observations.
189///
190/// Phase 1: single observations and observation-level `AND`/`OR`. `FOLLOWEDBY` and
191/// qualifiers (`WITHIN`/`REPEATS`/`START..STOP`) are parsed but return
192/// `MatchError::Unsupported` rather than silently passing.
193pub fn eval_pattern(
194    pattern: &Pattern,
195    observations: &[Observation],
196    store: Option<&ObjectStore>,
197) -> Result<MatchResult, MatchError> {
198    let mut matched = Vec::new();
199    let is_match =
200        eval_observation_expression(&pattern.expression, observations, store, &mut matched)?;
201    if is_match {
202        matched.sort_unstable();
203        matched.dedup();
204        Ok(MatchResult::matched(matched))
205    } else {
206        Ok(MatchResult::no_match())
207    }
208}
209
210/// Returns whether the observation expression matches, accumulating the indices of
211/// observations that satisfied any `[ ... ]` leaf into `matched`.
212fn eval_observation_expression(
213    expr: &ObservationExpression,
214    observations: &[Observation],
215    store: Option<&ObjectStore>,
216    matched: &mut Vec<usize>,
217) -> Result<bool, MatchError> {
218    match expr {
219        ObservationExpression::Observation(comparison) => {
220            let mut any = false;
221            for (i, obs) in observations.iter().enumerate() {
222                if eval_comparison_expression(comparison, obs, store) {
223                    matched.push(i);
224                    any = true;
225                }
226            }
227            Ok(any)
228        }
229        ObservationExpression::And(a, b) => {
230            let left = eval_observation_expression(a, observations, store, matched)?;
231            let right = eval_observation_expression(b, observations, store, matched)?;
232            Ok(left && right)
233        }
234        ObservationExpression::Or(a, b) => {
235            let left = eval_observation_expression(a, observations, store, matched)?;
236            let right = eval_observation_expression(b, observations, store, matched)?;
237            Ok(left || right)
238        }
239        ObservationExpression::FollowedBy(_, _) => Err(MatchError::Unsupported(
240            "FOLLOWEDBY sequencing is not yet implemented".to_string(),
241        )),
242        ObservationExpression::Qualified { .. } => Err(MatchError::Unsupported(
243            "observation qualifiers (WITHIN/REPEATS/START..STOP) are not yet implemented"
244                .to_string(),
245        )),
246    }
247}
248
249#[cfg(test)]
250mod tests {
251    use super::*;
252    use stix_model::StixObject;
253    use stix_pattern::ast::{
254        Comparison, ComparisonOperand, ComparisonOperator, Literal, ObjectPath, PathStep,
255    };
256
257    fn obj(json: serde_json::Value) -> StixObject {
258        StixObject::from_json(json).unwrap()
259    }
260
261    fn cmp(
262        object_type: &str,
263        key: &str,
264        operator: ComparisonOperator,
265        negated: bool,
266        value: ComparisonOperand,
267    ) -> Comparison {
268        Comparison {
269            path: ObjectPath {
270                object_type: object_type.to_string(),
271                steps: vec![PathStep::Key(key.to_string())],
272            },
273            operator,
274            negated,
275            value,
276        }
277    }
278
279    fn lit(s: &str) -> ComparisonOperand {
280        ComparisonOperand::Literal(Literal::String(s.to_string()))
281    }
282
283    #[test]
284    fn equality_against_object() {
285        let o =
286            obj(serde_json::json!({"type": "ipv4-addr", "id": "ipv4-addr--1", "value": "1.2.3.4"}));
287        let c = cmp(
288            "ipv4-addr",
289            "value",
290            ComparisonOperator::Equal,
291            false,
292            lit("1.2.3.4"),
293        );
294        assert!(eval_comparison(&o, &c, None));
295
296        let c2 = cmp(
297            "ipv4-addr",
298            "value",
299            ComparisonOperator::Equal,
300            false,
301            lit("9.9.9.9"),
302        );
303        assert!(!eval_comparison(&o, &c2, None));
304    }
305
306    #[test]
307    fn negation_inverts() {
308        let o = obj(serde_json::json!({"type": "file", "id": "file--1", "name": "evil.exe"}));
309        let c = cmp(
310            "file",
311            "name",
312            ComparisonOperator::Equal,
313            true,
314            lit("evil.exe"),
315        );
316        assert!(!eval_comparison(&o, &c, None));
317    }
318
319    #[test]
320    fn exists_checks_presence() {
321        let o = obj(serde_json::json!({"type": "file", "id": "file--1", "name": "x"}));
322        let present = cmp(
323            "file",
324            "name",
325            ComparisonOperator::Exists,
326            false,
327            lit("ignored"),
328        );
329        assert!(eval_comparison(&o, &present, None));
330        let absent = cmp(
331            "file",
332            "size",
333            ComparisonOperator::Exists,
334            false,
335            lit("ignored"),
336        );
337        assert!(!eval_comparison(&o, &absent, None));
338    }
339
340    #[test]
341    fn in_set_against_object() {
342        let o =
343            obj(serde_json::json!({"type": "ipv4-addr", "id": "ipv4-addr--1", "value": "8.8.8.8"}));
344        let set = ComparisonOperand::Set(vec![
345            Literal::String("1.1.1.1".into()),
346            Literal::String("8.8.8.8".into()),
347        ]);
348        let c = cmp("ipv4-addr", "value", ComparisonOperator::In, false, set);
349        assert!(eval_comparison(&o, &c, None));
350    }
351
352    #[test]
353    fn issubset_against_object() {
354        let o = obj(
355            serde_json::json!({"type": "ipv4-addr", "id": "ipv4-addr--1", "value": "198.51.100.5"}),
356        );
357        let c = cmp(
358            "ipv4-addr",
359            "value",
360            ComparisonOperator::IsSubset,
361            false,
362            ComparisonOperand::Literal(Literal::String("198.51.100.0/24".into())),
363        );
364        assert!(eval_comparison(&o, &c, None));
365    }
366
367    use crate::observation::Observation;
368    use stix_pattern::ast::ComparisonExpression;
369
370    fn observation(objs: Vec<serde_json::Value>) -> Observation {
371        Observation::new(objs.into_iter().map(obj).collect())
372    }
373
374    fn test_expr(c: Comparison) -> ComparisonExpression {
375        ComparisonExpression::Test(c)
376    }
377
378    #[test]
379    fn single_test_matches_some_object() {
380        let o = observation(vec![
381            serde_json::json!({"type": "ipv4-addr", "id": "ipv4-addr--1", "value": "1.2.3.4"}),
382            serde_json::json!({"type": "domain-name", "id": "domain-name--1", "value": "evil.example"}),
383        ]);
384        let expr = test_expr(cmp(
385            "domain-name",
386            "value",
387            ComparisonOperator::Equal,
388            false,
389            lit("evil.example"),
390        ));
391        assert!(eval_comparison_expression(&expr, &o, None));
392    }
393
394    #[test]
395    fn and_requires_same_object_binding() {
396        // Two constraints on `file` must be satisfied by ONE file object.
397        let matching = observation(vec![
398            serde_json::json!({"type": "file", "id": "file--1", "name": "evil.exe", "size": 10}),
399        ]);
400        let split = observation(vec![
401            serde_json::json!({"type": "file", "id": "file--1", "name": "evil.exe", "size": 99}),
402            serde_json::json!({"type": "file", "id": "file--2", "name": "ok.txt", "size": 10}),
403        ]);
404        let expr = ComparisonExpression::And(
405            Box::new(test_expr(cmp(
406                "file",
407                "name",
408                ComparisonOperator::Equal,
409                false,
410                lit("evil.exe"),
411            ))),
412            Box::new(test_expr(cmp(
413                "file",
414                "size",
415                ComparisonOperator::Equal,
416                false,
417                ComparisonOperand::Literal(Literal::Integer(10)),
418            ))),
419        );
420        assert!(eval_comparison_expression(&expr, &matching, None));
421        // No single file is both name=evil.exe AND size=10, so this must not match.
422        assert!(!eval_comparison_expression(&expr, &split, None));
423    }
424
425    #[test]
426    fn or_matches_either_branch() {
427        let o = observation(vec![
428            serde_json::json!({"type": "ipv4-addr", "id": "ipv4-addr--1", "value": "1.2.3.4"}),
429        ]);
430        let expr = ComparisonExpression::Or(
431            Box::new(test_expr(cmp(
432                "ipv4-addr",
433                "value",
434                ComparisonOperator::Equal,
435                false,
436                lit("9.9.9.9"),
437            ))),
438            Box::new(test_expr(cmp(
439                "ipv4-addr",
440                "value",
441                ComparisonOperator::Equal,
442                false,
443                lit("1.2.3.4"),
444            ))),
445        );
446        assert!(eval_comparison_expression(&expr, &o, None));
447    }
448
449    use stix_pattern::parse;
450
451    #[test]
452    fn single_observation_matches_across_set() {
453        let observations = vec![
454            observation(vec![
455                serde_json::json!({"type": "ipv4-addr", "id": "ipv4-addr--1", "value": "1.1.1.1"}),
456            ]),
457            observation(vec![
458                serde_json::json!({"type": "ipv4-addr", "id": "ipv4-addr--2", "value": "1.2.3.4"}),
459            ]),
460        ];
461        let pattern = parse("[ipv4-addr:value = '1.2.3.4']").unwrap();
462        let result = eval_pattern(&pattern, &observations, None).unwrap();
463        assert!(result.is_match());
464        assert_eq!(result.observations(), &[1]);
465    }
466
467    #[test]
468    fn observation_and_needs_both() {
469        let observations = vec![
470            observation(vec![
471                serde_json::json!({"type": "ipv4-addr", "id": "ipv4-addr--1", "value": "1.1.1.1"}),
472            ]),
473            observation(vec![
474                serde_json::json!({"type": "domain-name", "id": "domain-name--1", "value": "evil.example"}),
475            ]),
476        ];
477        let yes = parse("[ipv4-addr:value = '1.1.1.1'] AND [domain-name:value = 'evil.example']")
478            .unwrap();
479        assert!(eval_pattern(&yes, &observations, None).unwrap().is_match());
480
481        let no = parse("[ipv4-addr:value = '1.1.1.1'] AND [domain-name:value = 'good.example']")
482            .unwrap();
483        assert!(!eval_pattern(&no, &observations, None).unwrap().is_match());
484    }
485
486    #[test]
487    fn followedby_is_unsupported() {
488        let observations = vec![observation(vec![
489            serde_json::json!({"type": "ipv4-addr", "id": "ipv4-addr--1", "value": "1.1.1.1"}),
490        ])];
491        let pattern =
492            parse("[ipv4-addr:value = '1.1.1.1'] FOLLOWEDBY [ipv4-addr:value = '2.2.2.2']")
493                .unwrap();
494        let err = eval_pattern(&pattern, &observations, None).unwrap_err();
495        assert!(matches!(err, crate::error::MatchError::Unsupported(_)));
496    }
497
498    #[test]
499    fn qualifier_is_unsupported() {
500        let observations = vec![observation(vec![
501            serde_json::json!({"type": "ipv4-addr", "id": "ipv4-addr--1", "value": "1.1.1.1"}),
502        ])];
503        let pattern = parse("[ipv4-addr:value = '1.1.1.1'] REPEATS 2 TIMES").unwrap();
504        let err = eval_pattern(&pattern, &observations, None).unwrap_err();
505        assert!(matches!(err, crate::error::MatchError::Unsupported(_)));
506    }
507}
stix_matcher/eval.rs

stix_matcher/
eval.rs
