Skip to main content

unityrs_testkit/
mutate.rs

1//! G3b's seeded mutator (plan section 6): every builder output, mutated by
2//! three operators, and both dumpers read every mutant.
3//!
4//! - **Fields.** Every field the build of an output writes into it (each
5//!   4- and 8-byte integer, [`crate::writer`]: every count, length, size and
6//!   offset, zero-valued ones included, and every other integer of those
7//!   widths) becomes two mutants: the field set negative (-1 or the type's
8//!   minimum) and set huge (the type's maximum, or 2^30 or 2^40). The
9//!   output is built again with that one field replaced as it is written
10//!   ([`crate::writer::with_fields`]), so a field inside a compressed block,
11//!   or in a file a bundle holds, is changed before the block is compressed
12//!   and the bundle's sizes are computed. A field belongs to the outputs
13//!   whose bytes change when it alone is replaced; one that changes no
14//!   output (a build kept only for its length) is no output's.
15//! - **Bit flips.** One to eight random bits.
16//! - **Truncation.** The input cut at a random length below its own.
17//!
18//! Each output's field mutants come first, in write order, then
19//! [`RANDOM_PER_INPUT`] mutants alternate bit flips and truncations. Each
20//! output's generator is [`SEED`] mixed with the FNV-1a hash of its name, and
21//! picks each field's value from its pair; a mutant's label says what was
22//! done (`f<field>.<le|be><4|8><n|h>`, the field's number among the output's
23//! own, `b<bits>`, `t<length>`). The mutants depend only on the builders'
24//! code, never on how many threads made them.
25
26use std::collections::HashMap;
27
28use crate::rng::Rng;
29use crate::writer::{Field, with_fields};
30
31/// The master seed (recorded in the gate's report).
32pub const SEED: u64 = 0x6733_6200_5031_0001;
33
34/// Bit flips and truncations per output, after its field mutants.
35pub const RANDOM_PER_INPUT: usize = 80;
36
37/// One mutant: what was done, and the bytes.
38#[derive(Clone, Debug, PartialEq, Eq)]
39pub struct Mutant {
40    /// The operator and its argument.
41    pub label: String,
42    /// The mutated bytes.
43    pub bytes: Vec<u8>,
44}
45
46/// Named outputs, in build order.
47pub type Outputs = Vec<(String, Vec<u8>)>;
48
49fn fnv1a(name: &[u8]) -> u64 {
50    name.iter().fold(0xcbf2_9ce4_8422_2325, |h, b| {
51        (h ^ u64::from(*b)).wrapping_mul(0x0000_0100_0000_01B3)
52    })
53}
54
55/// All the field's bits set.
56fn mask(f: &Field) -> u64 {
57    if f.width >= 8 {
58        u64::MAX
59    } else {
60        (1u64 << (8 * f.width)) - 1
61    }
62}
63
64/// The negative pair and the huge pair for a field of `width` bytes.
65fn pairs(width: usize) -> ([u64; 2], [u64; 2]) {
66    if width == 4 {
67        ([0xFFFF_FFFF, 0x8000_0000], [0x7FFF_FFFF, 1 << 30])
68    } else {
69        ([u64::MAX, 1 << 63], [i64::MAX.unsigned_abs(), 1 << 40])
70    }
71}
72
73/// `run` over `jobs` on up to `threads` threads; result `i` is `run(&jobs[i])`.
74fn parallel<J: Sync, R: Send>(
75    jobs: &[J],
76    threads: usize,
77    run: &(dyn Fn(&J) -> R + Sync),
78) -> Vec<R> {
79    let threads = threads.clamp(1, jobs.len().max(1));
80    if threads == 1 {
81        return jobs.iter().map(run).collect();
82    }
83    let mut all: Vec<(usize, R)> = Vec::with_capacity(jobs.len());
84    std::thread::scope(|s| {
85        let handles: Vec<_> = (0..threads)
86            .map(|t| {
87                s.spawn(move || {
88                    jobs.iter()
89                        .enumerate()
90                        .skip(t)
91                        .step_by(threads)
92                        .map(|(i, j)| (i, run(j)))
93                        .collect::<Vec<_>>()
94                })
95            })
96            .collect();
97        for h in handles {
98            // A builder that panics is a bug in the builders: pass it on.
99            match h.join() {
100                Ok(part) => all.extend(part),
101                Err(e) => std::panic::resume_unwind(e),
102            }
103        }
104    });
105    all.sort_by_key(|(i, _)| *i);
106    all.into_iter().map(|(_, r)| r).collect()
107}
108
109/// The outputs of a build with `overrides`, by name.
110fn rebuild(
111    build: &(dyn Fn() -> Outputs + Sync),
112    overrides: &[(usize, u64)],
113) -> HashMap<String, Vec<u8>> {
114    with_fields(overrides, build).0.into_iter().collect()
115}
116
117/// One field mutant to make: an output, a field, its value, the label.
118struct Planned {
119    output: usize,
120    field: usize,
121    value: u64,
122    label: String,
123}
124
125/// Every output of `build` with its mutants (module docs), the work spread
126/// over `threads` threads. `build` must give the same outputs, under names
127/// that do not repeat, each time it runs.
128#[must_use]
129pub fn mutants_of(
130    build: &(dyn Fn() -> Outputs + Sync),
131    threads: usize,
132) -> Vec<(String, Vec<Mutant>)> {
133    let (base, fields) = with_fields(&[], build);
134    // The outputs each field changes when it alone is replaced by its
135    // complement.
136    let ids: Vec<usize> = (0..fields.len()).collect();
137    let owners: Vec<Vec<usize>> = parallel(&ids, threads, &|k| {
138        let f = &fields[*k];
139        let again = rebuild(build, &[(*k, !f.value & mask(f))]);
140        base.iter()
141            .enumerate()
142            .filter(|(_, (name, bytes))| again.get(name).is_some_and(|b| b != bytes))
143            .map(|(o, _)| o)
144            .collect()
145    });
146    let mut own: Vec<Vec<usize>> = vec![Vec::new(); base.len()];
147    for (k, os) in owners.iter().enumerate() {
148        for o in os {
149            own[*o].push(k);
150        }
151    }
152    // Each output's field values come from its own generator, which then
153    // drives its random operators.
154    let mut rngs: Vec<Rng> = base
155        .iter()
156        .map(|(name, _)| Rng::new(SEED ^ fnv1a(name.as_bytes())))
157        .collect();
158    let mut planned: Vec<Vec<Planned>> = Vec::with_capacity(base.len());
159    for (o, ks) in own.iter().enumerate() {
160        let mut row = Vec::with_capacity(2 * ks.len());
161        for (i, k) in ks.iter().enumerate() {
162            let f = &fields[*k];
163            let end = if f.big_endian { "be" } else { "le" };
164            let (neg, huge) = pairs(f.width);
165            for (tag, pair) in [("n", neg), ("h", huge)] {
166                let pick = rngs[o].below(2);
167                // A field already at the picked value takes the other one.
168                let value = if pair[pick] == f.value {
169                    pair[1 - pick]
170                } else {
171                    pair[pick]
172                };
173                row.push(Planned {
174                    output: o,
175                    field: *k,
176                    value,
177                    label: format!("f{i}.{end}{}{tag}", f.width),
178                });
179            }
180        }
181        planned.push(row);
182    }
183    // A field one output alone holds is replaced together with one such
184    // field of each other output (no output sees another's: [`make`]); a
185    // field that several outputs hold is replaced on its own.
186    let rounds = planned.iter().map(Vec::len).max().unwrap_or(0);
187    let mut batches: Vec<Vec<&Planned>> = (0..rounds)
188        .map(|r| {
189            planned
190                .iter()
191                .filter_map(|row| row.get(r))
192                .filter(|p| owners[p.field].len() == 1)
193                .collect()
194        })
195        .collect();
196    batches.extend(
197        planned
198            .iter()
199            .flatten()
200            .filter(|p| owners[p.field].len() > 1)
201            .map(|p| vec![p]),
202    );
203    let made: Vec<Vec<(usize, usize, Mutant)>> = parallel(&batches, threads, &|batch| {
204        make(build, &base, &fields, &planned, batch)
205    });
206    let mut by_output: Vec<Vec<(usize, Mutant)>> = vec![Vec::new(); base.len()];
207    for (o, order, m) in made.into_iter().flatten() {
208        by_output[o].push((order, m));
209    }
210    base.into_iter()
211        .zip(by_output)
212        .zip(rngs.iter_mut())
213        .map(|(((name, data), mut fm), rng)| {
214            fm.sort_by_key(|(order, _)| *order);
215            let mut out: Vec<Mutant> = fm.into_iter().map(|(_, m)| m).collect();
216            out.extend(random_mutants(&data, rng));
217            (name, out)
218        })
219        .collect()
220}
221
222/// The mutants `batch` makes, `(output, order, mutant)`, its fields replaced
223/// in one build. A replaced field whose value changes how many fields its
224/// build writes after it (the LZ4-compressed length of a nested bundle sets
225/// how many blocks the bundle holding it has) numbers every later field
226/// otherwise, so the batch's later replacements would land on other fields
227/// than planned, of other outputs or of none: a batch whose build writes
228/// fields of other widths, or another count of them, than the plain build,
229/// or gives a replaced field another value, is made one field at a time.
230fn make(
231    build: &(dyn Fn() -> Outputs + Sync),
232    base: &Outputs,
233    fields: &[Field],
234    planned: &[Vec<Planned>],
235    batch: &[&Planned],
236) -> Vec<(usize, usize, Mutant)> {
237    let overrides: Vec<(usize, u64)> = batch.iter().map(|p| (p.field, p.value)).collect();
238    let (outputs, written) = with_fields(&overrides, build);
239    let shape = |f: &Field| (f.width, f.big_endian);
240    let numbered = written.len() == fields.len()
241        && written.iter().map(shape).eq(fields.iter().map(shape))
242        && batch
243            .iter()
244            .all(|p| written.get(p.field) == fields.get(p.field));
245    if batch.len() > 1 && !numbered {
246        return batch
247            .iter()
248            .flat_map(|p| make(build, base, fields, planned, &[*p]))
249            .collect();
250    }
251    let again: HashMap<String, Vec<u8>> = outputs.into_iter().collect();
252    batch
253        .iter()
254        .filter_map(|p| {
255            let (name, bytes) = &base[p.output];
256            // A replacement that leaves the output as it was is no mutant.
257            let got = again.get(name).filter(|b| *b != bytes)?;
258            let order = planned[p.output].iter().position(|q| q.label == p.label)?;
259            Some((
260                p.output,
261                order,
262                Mutant {
263                    label: p.label.clone(),
264                    bytes: got.clone(),
265                },
266            ))
267        })
268        .collect()
269}
270
271/// [`RANDOM_PER_INPUT`] mutants of `data`, bit flips and truncations by turns.
272fn random_mutants(data: &[u8], rng: &mut Rng) -> Vec<Mutant> {
273    let mut out = Vec::with_capacity(RANDOM_PER_INPUT);
274    let mut flip = true;
275    while out.len() < RANDOM_PER_INPUT && !data.is_empty() {
276        let mut bytes = data.to_vec();
277        let label = if flip {
278            let bits = 1 + rng.below(8);
279            rng.flip_bits(&mut bytes, bits);
280            // Two flips of one bit cancel: flip another until it differs.
281            while bytes == data {
282                rng.flip_bits(&mut bytes, 1);
283            }
284            format!("b{bits}")
285        } else {
286            let n = rng.below(data.len());
287            bytes.truncate(n);
288            format!("t{n}")
289        };
290        flip = !flip;
291        out.push(Mutant { label, bytes });
292    }
293    out
294}
295
296/// G3b's inputs: every builder output the gate mutates, `(name, bytes)`:
297/// the format matrix ([`crate::bundle::matrix`]) and every file of every
298/// Environment scene, those some of whose loads are dependencies, those
299/// `find_file` is recorded on and those whose walk races another load
300/// (its file among the scene's) included ([`crate::env::scenes`],
301/// [`crate::env::dependency_scenes`], [`crate::env::find_scenes`],
302/// [`crate::env::race_scenes`]; named `scene-<scene>-<file>`), but a
303/// WebFile ([`is_web_file`]): P1 refuses one (plan section 1), so the dump
304/// writes no record of the entries UnityPy reads from it.
305#[must_use]
306pub fn builder_outputs() -> Outputs {
307    let mut out = crate::bundle::matrix();
308    for (scene, s) in every_scene() {
309        for (name, bytes) in s.files.into_iter().chain(s.resolver) {
310            if is_web_file(&bytes) {
311                continue;
312            }
313            let name = String::from_utf8_lossy(&name).replace('/', "_");
314            out.push((format!("scene-{scene}-{name}"), bytes));
315        }
316    }
317    out
318}
319
320/// Every Environment scene of every list, by name, a race scene's other
321/// file among its files.
322fn every_scene() -> Vec<(&'static str, crate::env::Scene)> {
323    let dependency = crate::env::dependency_scenes()
324        .into_iter()
325        .map(|(scene, d)| (scene, d.scene));
326    let find = crate::env::find_scenes()
327        .into_iter()
328        .map(|(scene, f)| (scene, f.scene));
329    let race = crate::env::race_scenes().into_iter().map(|(scene, r)| {
330        let mut s = r.scene;
331        s.files.push(r.other);
332        (scene, s)
333    });
334    crate::env::scenes()
335        .into_iter()
336        .chain(dependency)
337        .chain(find)
338        .chain(race)
339        .collect()
340}
341
342/// Whether `bytes` are a WebFile by UnityPy's detection: a signature that
343/// starts `UnityWebData` or `TuanjieWebData` (`docs/CANONICAL_DUMP.md`
344/// section 4.2, `l0`'s rule 4).
345#[must_use]
346pub fn is_web_file(bytes: &[u8]) -> bool {
347    bytes.starts_with(b"UnityWebData") || bytes.starts_with(b"TuanjieWebData")
348}
349
350/// G3b's mutants: [`mutants_of`] the [`builder_outputs`].
351#[must_use]
352pub fn gate_mutants(threads: usize) -> Vec<(String, Vec<Mutant>)> {
353    mutants_of(&builder_outputs, threads)
354}
355
356#[cfg(test)]
357mod tests {
358    use super::{Outputs, RANDOM_PER_INPUT, builder_outputs, mutants_of};
359    use crate::bundle::{TestCodec, compress};
360    use crate::writer::{ByteWriter, with_fields};
361
362    /// A count, a `u16` (no field) and a big-endian length.
363    fn body(count: u32) -> Vec<u8> {
364        let mut w = ByteWriter::le();
365        w.u32(count)
366            .u16(0xAAAA)
367            .set_big_endian(true)
368            .u64(3)
369            .bytes(b"xyz");
370        w.into_inner()
371    }
372
373    /// A zero count and a length, plain; the same inside an LZ4 block whose
374    /// stored size follows it; and a build kept only for its length.
375    fn small() -> Outputs {
376        let plain = body(0);
377        let packed = compress(TestCodec::Lz4, &body(3));
378        let mut w = ByteWriter::be();
379        w.u32(u32::try_from(packed.len()).unwrap()).bytes(&packed);
380        let wrapped = w.into_inner();
381        let only_its_length = body(9).len();
382        vec![
383            ("plain".into(), plain),
384            ("wrapped".into(), wrapped),
385            ("sized".into(), vec![0; only_its_length]),
386        ]
387    }
388
389    #[test]
390    fn every_field_of_every_output_is_set_negative_and_huge() {
391        let all = mutants_of(&small, 1);
392        let names: Vec<&str> = all.iter().map(|(n, _)| n.as_str()).collect();
393        assert_eq!(names, ["plain", "wrapped", "sized"]);
394        let labels = |o: usize| -> Vec<&str> {
395            all[o]
396                .1
397                .iter()
398                .filter(|m| m.label.starts_with('f'))
399                .map(|m| m.label.as_str())
400                .collect()
401        };
402        // The zero count and the big-endian length, each both ways.
403        assert_eq!(labels(0), ["f0.le4n", "f0.le4h", "f1.be8n", "f1.be8h"]);
404        // The two inside the block, then the block's stored size, written last.
405        assert_eq!(
406            labels(1),
407            [
408                "f0.le4n", "f0.le4h", "f1.be8n", "f1.be8h", "f2.be4n", "f2.be4h"
409            ]
410        );
411        // The third output holds no field of the build it was sized by.
412        assert_eq!(labels(2), Vec::<&str>::new());
413        // The zero count set negative, the rest unchanged.
414        let base = small();
415        let m = &all[0].1[0];
416        assert!(
417            [[0xFF; 4], [0, 0, 0, 0x80]].contains(&<[u8; 4]>::try_from(&m.bytes[..4]).unwrap())
418        );
419        assert_eq!(m.bytes[4..], base[0].1[4..]);
420        // The count inside the block is replaced before it is compressed.
421        let w = &all[1].1[1];
422        let size = usize::try_from(u32::from_be_bytes(w.bytes[..4].try_into().unwrap())).unwrap();
423        let inner = lz4_flex::block::decompress(&w.bytes[4..4 + size], 17).unwrap();
424        let count = u32::from_le_bytes(inner[..4].try_into().unwrap());
425        assert!([0x7FFF_FFFF, 1 << 30].contains(&count), "{count:#x}");
426        assert_eq!(inner[4..], body(3)[4..]);
427        // Then the random operators.
428        for (_, ms) in &all {
429            let random = ms.iter().filter(|m| !m.label.starts_with('f')).count();
430            assert_eq!(random, RANDOM_PER_INPUT);
431        }
432    }
433
434    /// Two outputs: the first holds sixteen zero counts LZ4-packed, then a
435    /// field per byte of the packing, so replacing a count changes how many
436    /// fields it writes, as a nested bundle's packed length sets how many
437    /// blocks the bundle holding it has.
438    fn renumbering() -> Outputs {
439        let mut counts = ByteWriter::le();
440        for _ in 0..16 {
441            counts.u32(0);
442        }
443        let packed = compress(TestCodec::Lz4, &counts.into_inner());
444        let mut per_byte = ByteWriter::le();
445        for _ in 0..packed.len() {
446            per_byte.u32(1);
447        }
448        let mut second = ByteWriter::le();
449        second.u32(2).u32(3);
450        vec![
451            ("first".into(), [packed, per_byte.into_inner()].concat()),
452            ("second".into(), second.into_inner()),
453        ]
454    }
455
456    /// A field whose replacement renumbers the fields after it is not
457    /// replaced together with another output's field (review round 4: the
458    /// batch replaced whatever field took the other's number, so the second
459    /// output's mutants were lost or replaced another field than labelled).
460    #[test]
461    fn a_field_that_renumbers_later_fields_is_replaced_alone() {
462        let base = renumbering();
463        let all = mutants_of(&renumbering, 1);
464        let fields = |o: usize| all[o].1.iter().filter(|m| m.label.starts_with('f'));
465        let second: Vec<&str> = fields(1).map(|m| m.label.as_str()).collect();
466        assert_eq!(second, ["f0.le4n", "f0.le4h", "f1.le4n", "f1.le4h"]);
467        for m in fields(1) {
468            // The one field its label names replaced, the other as built.
469            let at = if m.label.starts_with("f0") { 0 } else { 4 };
470            let keep = 4 - at;
471            assert_eq!(
472                m.bytes[keep..keep + 4],
473                base[1].1[keep..keep + 4],
474                "{}",
475                m.label
476            );
477            assert_ne!(m.bytes[at..at + 4], base[1].1[at..at + 4], "{}", m.label);
478        }
479        let (_, written) = with_fields(&[], renumbering);
480        assert_eq!(fields(0).count(), 2 * (written.len() - 2));
481    }
482
483    #[test]
484    fn the_mutants_do_not_depend_on_the_threads() {
485        assert_eq!(mutants_of(&small, 1), mutants_of(&small, 3));
486    }
487
488    #[test]
489    fn the_gate_mutates_every_field_of_its_outputs() {
490        let inputs = builder_outputs();
491        assert!(inputs.len() > 98, "{}", inputs.len());
492        let mut names: Vec<&String> = inputs.iter().map(|(n, _)| n).collect();
493        names.sort();
494        names.dedup();
495        assert_eq!(names.len(), inputs.len(), "names repeat");
496        // The builders give the same bytes and fields each time, which the
497        // attribution of fields to outputs rests on.
498        assert_eq!(
499            with_fields(&[], builder_outputs),
500            with_fields(&[], builder_outputs)
501        );
502        let all = super::gate_mutants(4);
503        assert_eq!(all.len(), inputs.len());
504        let mut no_field = Vec::new();
505        for ((name, data), (n, ms)) in inputs.iter().zip(&all) {
506            assert_eq!(name, n);
507            assert!(
508                ms.iter().all(|m| m.bytes != *data),
509                "{name}: a mutant is its input"
510            );
511            let fields = ms.iter().filter(|m| m.label.starts_with('f')).count();
512            assert_eq!(fields % 2, 0, "{name}: {fields} field mutants");
513            if fields == 0 {
514                no_field.push(name.as_str());
515            }
516            assert_eq!(ms.len(), fields + RANDOM_PER_INPUT, "{name}");
517        }
518        // Only a resource file of raw bytes holds no field.
519        assert_eq!(
520            no_field,
521            [
522                "scene-resolver_loads-CAB-H2.resS",
523                "scene-find_file_kinds-top.resS",
524                "scene-find_file_kinds-r.resS",
525                "scene-find_file_listing-x.resS"
526            ]
527        );
528    }
529
530    /// Every file of every Environment scene is an output, a dependency
531    /// scene's, a `find_file` scene's and a race scene's (its other file
532    /// too) included (fix passes 6 and 11 each added the first scene of a
533    /// list of its own, which G3b's outputs left out), but the one WebFile,
534    /// which P1 refuses. The files expected are taken from each list's own
535    /// function, never from `every_scene`, which `builder_outputs` reads:
536    /// taken from it (fix pass 14), the test passed with the base or the
537    /// dependency list dropped from G3b's outputs (review round 15).
538    #[test]
539    fn every_file_of_every_scene_is_an_output() {
540        type Files = Vec<(Vec<u8>, Vec<u8>)>;
541        fn files(s: crate::env::Scene) -> Files {
542            s.files.into_iter().chain(s.resolver).collect()
543        }
544        let inputs = builder_outputs();
545        let lists: [(&str, Vec<(&str, Files)>); 4] = [
546            (
547                "scenes",
548                crate::env::scenes()
549                    .into_iter()
550                    .map(|(scene, s)| (scene, files(s)))
551                    .collect(),
552            ),
553            (
554                "dependency_scenes",
555                crate::env::dependency_scenes()
556                    .into_iter()
557                    .map(|(scene, d)| (scene, files(d.scene)))
558                    .collect(),
559            ),
560            (
561                "find_scenes",
562                crate::env::find_scenes()
563                    .into_iter()
564                    .map(|(scene, f)| (scene, files(f.scene)))
565                    .collect(),
566            ),
567            (
568                "race_scenes",
569                crate::env::race_scenes()
570                    .into_iter()
571                    .map(|(scene, r)| {
572                        let mut all = files(r.scene);
573                        all.push(r.other);
574                        (scene, all)
575                    })
576                    .collect(),
577            ),
578        ];
579        let (mut count, mut web) = (0, Vec::new());
580        for (list, scenes) in lists {
581            assert_ne!(scenes.len(), 0, "{list}");
582            for (scene, files) in scenes {
583                for (name, bytes) in files {
584                    let name = String::from_utf8_lossy(&name).replace('/', "_");
585                    let name = format!("scene-{scene}-{name}");
586                    if super::is_web_file(&bytes) {
587                        web.push(name);
588                        continue;
589                    }
590                    assert!(
591                        inputs.iter().any(|(n, b)| *n == name && *b == bytes),
592                        "{list}: {name} is no output"
593                    );
594                    count += 1;
595                }
596            }
597        }
598        assert_eq!(web, ["scene-find_file_kinds-w.web"]);
599        assert_eq!(inputs.len(), crate::bundle::matrix().len() + count);
600    }
601}