wafrift_evolution/search/
mod.rs

1//! Search algorithms for evolutionary WAF bypass discovery.
2
3use crate::evolution::{Chromosome, GenePool};
4use crate::types::{Budget, EvolutionError, OracleVerdict, SearchStats};
5use rand::rngs::StdRng;
6use std::cmp::Ordering;
7
8/// A candidate requested for evaluation, with a stable evaluation ID.
9#[derive(Debug, Clone)]
10pub struct EvalCandidate {
11    /// Stable ID used to correlate results.
12    pub id: u64,
13    /// The chromosome to evaluate.
14    pub chromosome: Chromosome,
15}
16
17/// Result of submitting evaluations back to the algorithm.
18#[derive(Debug, Clone, Copy, PartialEq, Eq)]
19pub enum SubmitResult {
20    /// The algorithm accepted all results.
21    Accepted,
22    /// Some evaluation IDs were unknown.
23    UnknownIds(usize),
24}
25
26/// Core trait implemented by all search algorithms.
27///
28/// Each algorithm manages its own internal state (population, archive,
29/// temperature, tabu list, etc.). The [`EvolutionEngine`](crate::evolution::EvolutionEngine)
30/// handles caching, budgeting, and batching on top of this trait.
31pub trait SearchAlgorithm: Send + Sync + std::fmt::Debug {
32    /// Algorithm name.
33    fn name(&self) -> &'static str;
34
35    /// Initialize the algorithm with a seed population.
36    fn initialize(&mut self, population: Vec<Chromosome>, gene_pool: &GenePool, rng: &mut StdRng);
37
38    /// Request up to `n` candidates for parallel evaluation.
39    ///
40    /// Returns candidates with stable IDs. The caller evaluates them and
41    /// later calls [`submit_evaluations`](SearchAlgorithm::submit_evaluations).
42    fn request_evaluations(&mut self, n: usize, rng: &mut StdRng) -> Vec<EvalCandidate>;
43
44    /// Submit evaluation results.
45    ///
46    /// The ID in each tuple must match an ID previously returned by
47    /// `request_evaluations`.
48    fn submit_evaluations(&mut self, results: Vec<(u64, OracleVerdict)>);
49
50    /// Check whether the algorithm thinks search should stop.
51    fn should_terminate(&self, stats: &SearchStats, budget: &Budget) -> bool;
52
53    /// Get the best chromosome found so far.
54    fn best(&self) -> Option<&Chromosome>;
55
56    /// Serialize internal state to bytes.
57    fn checkpoint(&self) -> Result<Vec<u8>, EvolutionError>;
58
59    /// Restore internal state from bytes.
60    fn restore(&mut self, bytes: &[u8]) -> Result<(), EvolutionError>;
61
62    /// Snapshot the algorithm's current "live" chromosomes — the set
63    /// the engine is actively searching from.
64    ///
65    /// Population-based algorithms (`NoveltySearch`, `MapElites`)
66    /// return their full pool. Single-state algorithms (`HillClimbing`,
67    /// `SimulatedAnnealing`, `TabuSearch`) return the singleton
68    /// current/best so the engine sees `len() == 1` and reports
69    /// "no pairwise diversity yet" rather than zero.
70    ///
71    /// Used by [`EvolutionEngine::diversity_score`](crate::evolution::EvolutionEngine::diversity_score)
72    /// to drive adaptive mutation pressure. Cloning is acceptable here
73    /// because callers run it at engine-tick rate, not per-evaluation.
74    fn population_snapshot(&self) -> Vec<Chromosome> {
75        self.best().cloned().into_iter().collect()
76    }
77
78    /// Deep-clone this algorithm into a fresh trait object.
79    ///
80    /// The default implementation falls back to a `checkpoint` →
81    /// `restore` round-trip via serde_json — correct for any
82    /// algorithm that implements those, but slow on large grids /
83    /// archives because every chromosome is JSON-serialised.
84    ///
85    /// Concrete algorithms override this with a direct in-memory
86    /// `Clone` to bypass the serde round-trip — typically 10-100×
87    /// faster on populated state. The override is what
88    /// [`EvolutionEngine::clone`](crate::evolution::EvolutionEngine)
89    /// uses on the proxy path, where allocation spikes from JSON
90    /// were the original blocker.
91    fn clone_box(&self) -> Box<dyn SearchAlgorithm> {
92        // The trait can't construct a fresh same-typed instance
93        // without help from the algorithm registry, so the default
94        // implementation is intentionally a panic for out-of-tree
95        // algorithms — they should override `clone_box` with a real
96        // `Clone`-based path. The 5 in-tree algorithms always
97        // override.
98        panic!(
99            "default clone_box is unreachable for in-tree algorithms; \
100             out-of-tree algorithms must override this method"
101        );
102    }
103}
104
105/// Convert non-finite fitness values into a strict worst-case sentinel.
106///
107/// NaN and +/-inf break partial ordering semantics and can lock algorithms
108/// into never-accept states. Mapping them to `-inf` keeps comparisons total.
109#[must_use]
110pub(crate) fn comparable_fitness(value: f64) -> f64 {
111    if value.is_finite() {
112        value
113    } else {
114        f64::NEG_INFINITY
115    }
116}
117
118#[must_use]
119pub(crate) fn fitness_cmp(a: f64, b: f64) -> Ordering {
120    comparable_fitness(a)
121        .partial_cmp(&comparable_fitness(b))
122        .unwrap_or(Ordering::Equal)
123}
124
125pub mod hill_climb;
126pub mod map_elites;
127pub mod novelty;
128pub mod sim_anneal;
129pub mod tabu;
130
131pub use hill_climb::HillClimbing;
132pub use map_elites::MapElites;
133pub use novelty::NoveltySearch;
134pub use sim_anneal::SimulatedAnnealing;
135pub use tabu::TabuSearch;
wafrift_evolution/search/mod.rs

wafrift_evolution/search/
mod.rs
