stix_matcher/
eval.rs

1//! Evaluation: leaf comparisons, comparison expressions, and observation expressions.
2
3use std::collections::{BTreeMap, BTreeSet};
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<&str> = Vec::new();
101    collect_types(expr, &mut types, &mut BTreeSet::new());
102
103    // Candidate objects per referenced type (indices into observation.objects).
104    // A type with no candidate stays unbound, so its leaves evaluate to false;
105    // only the types that do have candidates take part in the enumeration.
106    let bound: Vec<(&str, Vec<usize>)> = types
107        .into_iter()
108        .map(|t| {
109            let candidates: Vec<usize> = observation
110                .objects
111                .iter()
112                .enumerate()
113                .filter(|(_, o)| o.type_() == Some(t))
114                .map(|(i, _)| i)
115                .collect();
116            (t, candidates)
117        })
118        .filter(|(_, candidates)| !candidates.is_empty())
119        .collect();
120
121    enumerate_bindings(&bound, |binding| {
122        eval_tree(expr, observation, binding, store)
123    })
124}
125
126/// Collect the distinct object types referenced by an expression's leaves, in
127/// first-seen order. Recurses over nesting depth only (bounded by the parser);
128/// chain operands are iterated.
129fn collect_types<'e>(
130    expr: &'e ComparisonExpression,
131    out: &mut Vec<&'e str>,
132    seen: &mut BTreeSet<&'e str>,
133) {
134    match expr {
135        ComparisonExpression::Test(c) => {
136            if seen.insert(&c.path.object_type) {
137                out.push(&c.path.object_type);
138            }
139        }
140        ComparisonExpression::And(xs) | ComparisonExpression::Or(xs) => {
141            for x in xs {
142                collect_types(x, out, seen);
143            }
144        }
145    }
146}
147
148/// Try every assignment of one candidate object per type; return true as soon as
149/// `predicate` accepts a binding. Every type in `bound` has at least one
150/// candidate. Iterates like an odometer (the last type varies fastest), so the
151/// number of types costs no stack.
152fn enumerate_bindings(
153    bound: &[(&str, Vec<usize>)],
154    predicate: impl Fn(&BTreeMap<String, usize>) -> bool,
155) -> bool {
156    let mut choice = vec![0usize; bound.len()];
157    let mut binding: BTreeMap<String, usize> = bound
158        .iter()
159        .map(|(t, candidates)| (t.to_string(), candidates[0]))
160        .collect();
161    loop {
162        if predicate(&binding) {
163            return true;
164        }
165        // Advance to the next assignment, or stop after the last one.
166        let mut i = bound.len();
167        loop {
168            if i == 0 {
169                return false;
170            }
171            i -= 1;
172            let (t, candidates) = &bound[i];
173            choice[i] += 1;
174            if choice[i] == candidates.len() {
175                choice[i] = 0;
176            }
177            binding.insert(t.to_string(), candidates[choice[i]]);
178            if choice[i] != 0 {
179                break;
180            }
181        }
182    }
183}
184
185/// Evaluate the boolean tree under a fixed binding.
186fn eval_tree(
187    expr: &ComparisonExpression,
188    observation: &Observation,
189    binding: &BTreeMap<String, usize>,
190    store: Option<&ObjectStore>,
191) -> bool {
192    match expr {
193        ComparisonExpression::Test(c) => match binding.get(&c.path.object_type) {
194            Some(&obj_idx) => eval_comparison(&observation.objects[obj_idx], c, store),
195            None => false,
196        },
197        // A chain is the left-associative `(a && b) && c`: short-circuiting
198        // left to right, exactly as `all`/`any` do.
199        ComparisonExpression::And(xs) => {
200            xs.iter().all(|x| eval_tree(x, observation, binding, store))
201        }
202        ComparisonExpression::Or(xs) => {
203            xs.iter().any(|x| eval_tree(x, observation, binding, store))
204        }
205    }
206}
207
208/// Evaluate a whole pattern against a list of observations.
209///
210/// Phase 1: single observations and observation-level `AND`/`OR`. `FOLLOWEDBY` and
211/// qualifiers (`WITHIN`/`REPEATS`/`START..STOP`) are parsed but return
212/// `MatchError::Unsupported` rather than silently passing.
213pub fn eval_pattern(
214    pattern: &Pattern,
215    observations: &[Observation],
216    store: Option<&ObjectStore>,
217) -> Result<MatchResult, MatchError> {
218    let mut matched = Vec::new();
219    let is_match =
220        eval_observation_expression(&pattern.expression, observations, store, &mut matched)?;
221    if is_match {
222        matched.sort_unstable();
223        matched.dedup();
224        Ok(MatchResult::matched(matched))
225    } else {
226        Ok(MatchResult::no_match())
227    }
228}
229
230/// Returns whether the observation expression matches, accumulating the indices of
231/// observations that satisfied any `[ ... ]` leaf into `matched`.
232fn eval_observation_expression(
233    expr: &ObservationExpression,
234    observations: &[Observation],
235    store: Option<&ObjectStore>,
236    matched: &mut Vec<usize>,
237) -> Result<bool, MatchError> {
238    match expr {
239        ObservationExpression::Observation {
240            expression: comparison,
241            ..
242        } => {
243            let mut any = false;
244            for (i, obs) in observations.iter().enumerate() {
245                if eval_comparison_expression(comparison, obs, store) {
246                    matched.push(i);
247                    any = true;
248                }
249            }
250            Ok(any)
251        }
252        // Chains are the left-associative binary form, which evaluates every
253        // operand in order (no short-circuit, so each operand's matching
254        // observations are recorded) and stops at the first error.
255        ObservationExpression::And(xs) => {
256            let mut all = true;
257            for x in xs {
258                all &= eval_observation_expression(x, observations, store, matched)?;
259            }
260            Ok(all)
261        }
262        ObservationExpression::Or(xs) => {
263            let mut any = false;
264            for x in xs {
265                any |= eval_observation_expression(x, observations, store, matched)?;
266            }
267            Ok(any)
268        }
269        ObservationExpression::FollowedBy(_) => Err(MatchError::Unsupported(
270            "FOLLOWEDBY sequencing is not yet implemented".to_string(),
271        )),
272        ObservationExpression::Qualified { .. } => Err(MatchError::Unsupported(
273            "observation qualifiers (WITHIN/REPEATS/START..STOP) are not yet implemented"
274                .to_string(),
275        )),
276    }
277}
278
279#[cfg(test)]
280mod tests {
281    use super::*;
282    use stix_model::StixObject;
283    use stix_pattern::ast::{
284        Comparison, ComparisonOperand, ComparisonOperator, Literal, ObjectPath, PathStep,
285    };
286
287    fn obj(json: serde_json::Value) -> StixObject {
288        StixObject::from_json(json).unwrap()
289    }
290
291    fn cmp(
292        object_type: &str,
293        key: &str,
294        operator: ComparisonOperator,
295        negated: bool,
296        value: ComparisonOperand,
297    ) -> Comparison {
298        Comparison {
299            path: ObjectPath {
300                object_type: object_type.to_string(),
301                steps: vec![PathStep::Key(key.to_string())],
302                span: Default::default(),
303            },
304            operator,
305            negated,
306            value,
307            span: Default::default(),
308        }
309    }
310
311    fn lit(s: &str) -> ComparisonOperand {
312        ComparisonOperand::Literal(Literal::String(s.to_string()))
313    }
314
315    #[test]
316    fn equality_against_object() {
317        let o =
318            obj(serde_json::json!({"type": "ipv4-addr", "id": "ipv4-addr--1", "value": "1.2.3.4"}));
319        let c = cmp(
320            "ipv4-addr",
321            "value",
322            ComparisonOperator::Equal,
323            false,
324            lit("1.2.3.4"),
325        );
326        assert!(eval_comparison(&o, &c, None));
327
328        let c2 = cmp(
329            "ipv4-addr",
330            "value",
331            ComparisonOperator::Equal,
332            false,
333            lit("9.9.9.9"),
334        );
335        assert!(!eval_comparison(&o, &c2, None));
336    }
337
338    #[test]
339    fn negation_inverts() {
340        let o = obj(serde_json::json!({"type": "file", "id": "file--1", "name": "evil.exe"}));
341        let c = cmp(
342            "file",
343            "name",
344            ComparisonOperator::Equal,
345            true,
346            lit("evil.exe"),
347        );
348        assert!(!eval_comparison(&o, &c, None));
349    }
350
351    #[test]
352    fn exists_checks_presence() {
353        let o = obj(serde_json::json!({"type": "file", "id": "file--1", "name": "x"}));
354        let present = cmp(
355            "file",
356            "name",
357            ComparisonOperator::Exists,
358            false,
359            lit("ignored"),
360        );
361        assert!(eval_comparison(&o, &present, None));
362        let absent = cmp(
363            "file",
364            "size",
365            ComparisonOperator::Exists,
366            false,
367            lit("ignored"),
368        );
369        assert!(!eval_comparison(&o, &absent, None));
370    }
371
372    #[test]
373    fn in_set_against_object() {
374        let o =
375            obj(serde_json::json!({"type": "ipv4-addr", "id": "ipv4-addr--1", "value": "8.8.8.8"}));
376        let set = ComparisonOperand::Set(vec![
377            Literal::String("1.1.1.1".into()),
378            Literal::String("8.8.8.8".into()),
379        ]);
380        let c = cmp("ipv4-addr", "value", ComparisonOperator::In, false, set);
381        assert!(eval_comparison(&o, &c, None));
382    }
383
384    #[test]
385    fn issubset_against_object() {
386        let o = obj(
387            serde_json::json!({"type": "ipv4-addr", "id": "ipv4-addr--1", "value": "198.51.100.5"}),
388        );
389        let c = cmp(
390            "ipv4-addr",
391            "value",
392            ComparisonOperator::IsSubset,
393            false,
394            ComparisonOperand::Literal(Literal::String("198.51.100.0/24".into())),
395        );
396        assert!(eval_comparison(&o, &c, None));
397    }
398
399    use crate::observation::Observation;
400    use stix_pattern::ast::ComparisonExpression;
401
402    fn observation(objs: Vec<serde_json::Value>) -> Observation {
403        Observation::new(objs.into_iter().map(obj).collect())
404    }
405
406    fn test_expr(c: Comparison) -> ComparisonExpression {
407        ComparisonExpression::Test(c)
408    }
409
410    #[test]
411    fn single_test_matches_some_object() {
412        let o = observation(vec![
413            serde_json::json!({"type": "ipv4-addr", "id": "ipv4-addr--1", "value": "1.2.3.4"}),
414            serde_json::json!({"type": "domain-name", "id": "domain-name--1", "value": "evil.example"}),
415        ]);
416        let expr = test_expr(cmp(
417            "domain-name",
418            "value",
419            ComparisonOperator::Equal,
420            false,
421            lit("evil.example"),
422        ));
423        assert!(eval_comparison_expression(&expr, &o, None));
424    }
425
426    #[test]
427    fn and_requires_same_object_binding() {
428        // Two constraints on `file` must be satisfied by ONE file object.
429        let matching = observation(vec![
430            serde_json::json!({"type": "file", "id": "file--1", "name": "evil.exe", "size": 10}),
431        ]);
432        let split = observation(vec![
433            serde_json::json!({"type": "file", "id": "file--1", "name": "evil.exe", "size": 99}),
434            serde_json::json!({"type": "file", "id": "file--2", "name": "ok.txt", "size": 10}),
435        ]);
436        let expr = ComparisonExpression::And(vec![
437            test_expr(cmp(
438                "file",
439                "name",
440                ComparisonOperator::Equal,
441                false,
442                lit("evil.exe"),
443            )),
444            test_expr(cmp(
445                "file",
446                "size",
447                ComparisonOperator::Equal,
448                false,
449                ComparisonOperand::Literal(Literal::Integer(10)),
450            )),
451        ]);
452        assert!(eval_comparison_expression(&expr, &matching, None));
453        // No single file is both name=evil.exe AND size=10, so this must not match.
454        assert!(!eval_comparison_expression(&expr, &split, None));
455    }
456
457    #[test]
458    fn or_matches_either_branch() {
459        let o = observation(vec![
460            serde_json::json!({"type": "ipv4-addr", "id": "ipv4-addr--1", "value": "1.2.3.4"}),
461        ]);
462        let expr = ComparisonExpression::Or(vec![
463            test_expr(cmp(
464                "ipv4-addr",
465                "value",
466                ComparisonOperator::Equal,
467                false,
468                lit("9.9.9.9"),
469            )),
470            test_expr(cmp(
471                "ipv4-addr",
472                "value",
473                ComparisonOperator::Equal,
474                false,
475                lit("1.2.3.4"),
476            )),
477        ]);
478        assert!(eval_comparison_expression(&expr, &o, None));
479    }
480
481    fn eq_test(object_type: &str, value: &str) -> ComparisonExpression {
482        test_expr(cmp(
483            object_type,
484            "value",
485            ComparisonOperator::Equal,
486            false,
487            lit(value),
488        ))
489    }
490
491    /// An n-ary chain evaluates exactly as the left-associative binary chain
492    /// it stands for. The nested form below breaks the parser's flattening
493    /// invariant on purpose, to serve as the reference.
494    #[test]
495    fn comparison_chains_match_their_left_assoc_binary_form() {
496        let o = observation(vec![
497            serde_json::json!({"type": "ipv4-addr", "id": "ipv4-addr--1", "value": "1.2.3.4"}),
498            serde_json::json!({"type": "domain-name", "id": "domain-name--1", "value": "a.example"}),
499        ]);
500        let leaves = [
501            eq_test("ipv4-addr", "1.2.3.4"),
502            eq_test("ipv4-addr", "9.9.9.9"),
503            eq_test("domain-name", "a.example"),
504            eq_test("url", "absent"),
505        ];
506        for a in &leaves {
507            for b in &leaves {
508                for c in &leaves {
509                    type Build = fn(Vec<ComparisonExpression>) -> ComparisonExpression;
510                    for build in [ComparisonExpression::And as Build, ComparisonExpression::Or] {
511                        let chain = build(vec![a.clone(), b.clone(), c.clone()]);
512                        let nested = build(vec![build(vec![a.clone(), b.clone()]), c.clone()]);
513                        assert_eq!(
514                            eval_comparison_expression(&chain, &o, None),
515                            eval_comparison_expression(&nested, &o, None),
516                            "{chain:?}"
517                        );
518                    }
519                }
520            }
521        }
522    }
523
524    #[test]
525    fn many_distinct_types_in_one_chain() {
526        // Types absent from the observation are left unbound; a long chain of
527        // them must neither recurse per type nor change the result.
528        let o = observation(vec![
529            serde_json::json!({"type": "ipv4-addr", "id": "ipv4-addr--1", "value": "1.2.3.4"}),
530        ]);
531        let mut xs: Vec<ComparisonExpression> = (0..10_000)
532            .map(|i| eq_test(&format!("type-{i}"), "x"))
533            .collect();
534        assert!(!eval_comparison_expression(
535            &ComparisonExpression::Or(xs.clone()),
536            &o,
537            None
538        ));
539        xs.push(eq_test("ipv4-addr", "1.2.3.4"));
540        assert!(eval_comparison_expression(
541            &ComparisonExpression::Or(xs),
542            &o,
543            None
544        ));
545    }
546
547    #[test]
548    fn observation_chains_match_their_left_assoc_binary_form() {
549        let observations = vec![
550            observation(vec![
551                serde_json::json!({"type": "ipv4-addr", "id": "ipv4-addr--1", "value": "1.1.1.1"}),
552            ]),
553            observation(vec![
554                serde_json::json!({"type": "ipv4-addr", "id": "ipv4-addr--2", "value": "2.2.2.2"}),
555            ]),
556            observation(vec![
557                serde_json::json!({"type": "ipv4-addr", "id": "ipv4-addr--3", "value": "3.3.3.3"}),
558            ]),
559        ];
560        let leaf = |v: &str| ObservationExpression::Observation {
561            expression: Box::new(eq_test("ipv4-addr", v)),
562            span: Default::default(),
563        };
564        let leaves = [leaf("1.1.1.1"), leaf("3.3.3.3"), leaf("9.9.9.9")];
565        let run = |e: ObservationExpression| {
566            eval_pattern(&Pattern { expression: e }, &observations, None).unwrap()
567        };
568        for a in &leaves {
569            for b in &leaves {
570                for c in &leaves {
571                    type Build = fn(Vec<ObservationExpression>) -> ObservationExpression;
572                    for build in [
573                        ObservationExpression::And as Build,
574                        ObservationExpression::Or,
575                    ] {
576                        let chain = build(vec![a.clone(), b.clone(), c.clone()]);
577                        let nested = build(vec![build(vec![a.clone(), b.clone()]), c.clone()]);
578                        // Same verdict and the same matched observations.
579                        assert_eq!(run(chain.clone()), run(nested), "{chain:?}");
580                    }
581                }
582            }
583        }
584        // OR reports the observations of every operand that matched.
585        let r = run(ObservationExpression::Or(vec![
586            leaf("1.1.1.1"),
587            leaf("9.9.9.9"),
588            leaf("3.3.3.3"),
589        ]));
590        assert_eq!(r.observations(), &[0, 2]);
591    }
592
593    use stix_pattern::parse;
594
595    #[test]
596    fn single_observation_matches_across_set() {
597        let observations = vec![
598            observation(vec![
599                serde_json::json!({"type": "ipv4-addr", "id": "ipv4-addr--1", "value": "1.1.1.1"}),
600            ]),
601            observation(vec![
602                serde_json::json!({"type": "ipv4-addr", "id": "ipv4-addr--2", "value": "1.2.3.4"}),
603            ]),
604        ];
605        let pattern = parse("[ipv4-addr:value = '1.2.3.4']").unwrap();
606        let result = eval_pattern(&pattern, &observations, None).unwrap();
607        assert!(result.is_match());
608        assert_eq!(result.observations(), &[1]);
609    }
610
611    #[test]
612    fn observation_and_needs_both() {
613        let observations = vec![
614            observation(vec![
615                serde_json::json!({"type": "ipv4-addr", "id": "ipv4-addr--1", "value": "1.1.1.1"}),
616            ]),
617            observation(vec![
618                serde_json::json!({"type": "domain-name", "id": "domain-name--1", "value": "evil.example"}),
619            ]),
620        ];
621        let yes = parse("[ipv4-addr:value = '1.1.1.1'] AND [domain-name:value = 'evil.example']")
622            .unwrap();
623        assert!(eval_pattern(&yes, &observations, None).unwrap().is_match());
624
625        let no = parse("[ipv4-addr:value = '1.1.1.1'] AND [domain-name:value = 'good.example']")
626            .unwrap();
627        assert!(!eval_pattern(&no, &observations, None).unwrap().is_match());
628    }
629
630    #[test]
631    fn followedby_is_unsupported() {
632        let observations = vec![observation(vec![
633            serde_json::json!({"type": "ipv4-addr", "id": "ipv4-addr--1", "value": "1.1.1.1"}),
634        ])];
635        let pattern =
636            parse("[ipv4-addr:value = '1.1.1.1'] FOLLOWEDBY [ipv4-addr:value = '2.2.2.2']")
637                .unwrap();
638        let err = eval_pattern(&pattern, &observations, None).unwrap_err();
639        assert!(matches!(err, crate::error::MatchError::Unsupported(_)));
640    }
641
642    #[test]
643    fn qualifier_is_unsupported() {
644        let observations = vec![observation(vec![
645            serde_json::json!({"type": "ipv4-addr", "id": "ipv4-addr--1", "value": "1.1.1.1"}),
646        ])];
647        let pattern = parse("[ipv4-addr:value = '1.1.1.1'] REPEATS 2 TIMES").unwrap();
648        let err = eval_pattern(&pattern, &observations, None).unwrap_err();
649        assert!(matches!(err, crate::error::MatchError::Unsupported(_)));
650    }
651}
stix_matcher/eval.rs

stix_matcher/
eval.rs
