Mate in 10 Minutes: Fuzzing Object Graph

Common fuzzers generate bytes, strings, or structured grammar-based inputs. Pharo programs, however, work with objects: a BlElement with children that point back to their parent, a Player whose level must stay between 0 and 99, a model where some fields may be nil and others never are.

Mate is a small language and toolkit for describing those object graphs. From one description you can:

• Generate valid objects, as many as you want, for testing and fuzzing;
• Guide generation with feedback, so it explores the shapes that matter;
• Validate existing objects against the description;
• Infer a description from real objects or from your test suite;
• Visualize how generation explored the grammar.

This guide walks through each use with small examples.

Installing

Metacello new
    baseline: 'Mate';
    repository: 'github://FedeLoch/Mate:main';
    onConflictUseIncoming;
    load.

Your first object grammar

Suppose we have a small game model:

Object << #Player
    slots: { #name . #characterClass . #level . #missingExperienceForNextLevel };
    package: 'MyGame'.

characterClass holds a Warrior, a Rogue or a Mage.

A Mate grammar says which classes each field may hold and which values are acceptable:

Player -> {
  name: ByteString,
  characterClass: Warrior | Rogue | Mage,
  level: { type: SmallInteger, between: 0 and: 99 },
  missingExperienceForNextLevel: { type: SmallInteger, greaterThan: 0 }
}

Read it as: a Player has a name that is a string, a characterClass that is one of three classes, a level from 0 to 99, and a strictly positive amount of missing experience.

To use it, subclass MateOGGrammar and return the description from defineObjectGraph:

MateOGGrammar << #PlayerGrammar
    package: 'MyGame'.
PlayerGrammar >> defineObjectGraph [
    ^ 'Player -> {
        name: ByteString,
        characterClass: Warrior | Rogue | Mage,
        level: { type: SmallInteger, between: 0 and: 99 },
        missingExperienceForNextLevel: { type: SmallInteger, greaterThan: 0 }
    }'
]

You can also load a grammar from a file:

grammar := MateOGGrammar fromFile: 'player.mate'.

Generating objects

grammar := PlayerGrammar new.
player := grammar gen: Player.
player level.           "=> always between 0 and 99"
player characterClass.  "=> a Warrior, a Rogue or a Mage"

Need a hundred?

players := (1 to: 100) collect: [ :i | grammar gen: Player ].

Values built for finding bugs

Mate does not pick values uniformly. It favours the values that tend to break code:

Constraints are always respected: a level declared between: 0 and: 99 will be 0, 1, 98, 99 and everything in between, but never 100.

Reproducible runs

When a generated object crashes your code, you want to get it back. Give the grammar a seed:

grammar := PlayerGrammar new.
grammar seed: 1234.
players := (1 to: 100) collect: [ :i | grammar gen: Player ].

The same seed produces the same sequence of objects.

The language at a glance

Here is a grammar for a hypothetical shop model that uses most of the language:

"Comments go between double quotes"
Shop -> {
  name: ByteString,
  rating: { type: Float, between: 0.0 and: 5.0 },
  stock: { type: SmallInteger, atLeast: 0 },
  status: { oneOf: { #open . #closed . #moved } },
  website: ByteString?,
  logo: (PNGImage | JPEGImage)?,
  products: { type: [ Product ], sizeBetween: 0 and: 20 },
  owner: { refType: Person },
  selfReferences: { products[ .shop ] }
}

Relationships between objects

Real object graphs are not trees. In Bloc, every child points back to its parent:

BlElement -> {
  children: BlChildrenArray,
  parent: { refType: BlElement },
  visuals: BlCustomVisuals | BlDefaultVisuals,
  constraints: BlLayoutCommonConstraints,
  selfReferences: { children.array[ .parent ] }
}
BlChildrenArray -> {
  array: { type: [ BlElement ], sizeBetween: 0 and: 10 }
}

children.array[ .parent ] reads: follow children, then array, and for each element set its parent to me. Every generated element tree is therefore consistent: child parent == element holds for every child.

Recursion

Grammars can be recursive (BlElement contains BlElements). Generation stops at a maximum depth (12 by default). At that depth, a field takes a simple value if its type allows one, and nil otherwise. You can tune this and how often nullable fields are nil:

grammar generator
    maxDerivationHeight: 6;
    nilProbability: 0.2.

Let’s stop for 5 seconds to drink a mate🧉… Let’s continue! 🙂

Guided fuzzing: Teaching the grammar what is interesting

Random generation finds shallow bugs. To go deeper, tell Mate which objects were interesting: they reached new code, were slow, or produced a bigger difference in the output. Mate keeps a reward for every choice it made while building that object (which union option, which value, which size) and favours the choices that paid off, while still exploring the rest. Under the hood, this is the UCT formula from Monte Carlo Tree Search.

grammar := PlayerGrammar new.
grammar seed: 42.
1 to: 1000 do: [ :i |
    | player score |
    player := grammar gen: Player.
    score := self newCoverageReachedBy: player.
    grammar backPropagate: score from: player ].

backPropagate:from: takes a generated object, works out its derivation, and rewards every choice in it. If you already have the derivation tree, use backpropagate:improvement: directly:

derivation := grammar gen: Player from: MateContext new.
player := derivation instance.
grammar backpropagate: derivation improvement: 42.

Mutating part of an object

Sometimes you want to keep an object and regenerate only one part of it. Take a node of the derivation tree, generate a variant, and swap it in. References such as parent are kept consistent:

derivation := grammar gen: BlElement from: MateContext new.
node := derivation edges at: 'children'.
variant := grammar genVariant: node.
grammar replace: node by: variant.

How much of the grammar did we explore?

grammar explorationPercentage.            "=> fraction of the grammar visited so far"
grammar explorationPercentageFrom: Player. "=> the same, counting only what is reachable from Player"

Validating objects

The same grammar can check objects that come from anywhere: your application, a file, a test.

grammar := PlayerGrammar new.
grammar parse: (Player new
    name: 'Fede';
    level: 42;
    characterClass: Rogue new;
    missingExperienceForNextLevel: 1).
"=> a derivation tree: the object is valid"
grammar parse: (Player new
    name: 'Fede';
    level: 500;
    characterClass: Rogue new;
    missingExperienceForNextLevel: 1).
"=> Error: Value 500 of type SmallInteger violates MateConstraint( min: 0 max: 99)"

parse: checks field types (subclasses are accepted), array sizes, value constraints, and selfReferences. It never modifies the object, and it handles cyclic graphs.

This makes Mate useful as an oracle too: generate objects, run an operation on them, and check that the result still matches the grammar.

Inferring a grammar from real objects

Writing a grammar by hand is not always practical. Mate can infer one from objects you already have:

grammar := MateOGGrammar fromObjects: { player1 . player2 . player3 }.
grammar mateDefinition.

Player -> {
	name: ByteString,
	characterClass: Mage | Rogue | Warrior,
	level: SmallInteger,
	missingExperienceForNextLevel: SmallInteger
}

Mate merges what it sees across all instances: field types become unions, arrays get the element types and size ranges observed, booleans become Boolean, and fields that hold classes become oneOf choices.

You can also infer a grammar from the objects your test suite builds:

grammar := MateOGGrammar fromTest: PlayerTest.

Every test is set up and run, and the objects held in its instance variables, plus its return value, are fed to the inference. Failing tests are skipped.

Inferred grammars are a starting point: they know the types but not yet the constraints (ranges, relationships). Edit the output of mateDefinition, which can be parsed back with no changes, and turn it into your hand-written grammar.

Seeing what happened

Mate uses Roassal to draw two things.

A derivation tree: how one object was built, with every choice made.

(PlayerGrammar new gen: Player from: MateContext new) render.

The grammar as a heat map: which declarations and options were visited most during generation.

grammar := MateBlocGrammar new.
100 timesRepeat: [ grammar gen: BlElement ].
grammar render.

Cheat sheet

Thanks for reading!! 🙂

Learn more in the repository and the other pages of this wiki.