Ume: Property Testing and Performance Fuzzing

As we know, the bugs that hurt are usually in the ones we didn’t think about, the ones that are hidden on the edge of a range, in nested JSON files, in regular expressions that take four seconds to execute a single match… Those…

Ume helps you search for those inputs. You describe how to build a receiver and the set of arguments for a method and what should hold about the result. Then, Ume:

• Generates thousands of cases and checks your properties on each one.
• Measures every execution (time, method calls, allocations, coverage, bytecodes, GCs).
• Guides the search with those metric measurements, and it keeps mutating the inputs that made the code work hardest.
• Segments what it found: errors, property failures, and metric outliers.
• Turns the findings into ordinary Pharo unit tests.

The same engine covers classic property-based testing and performance fuzzing. This guide walks through both with small examples.

Installing

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

Writing a Property

Let’s start by checking that factorial behaves as its definition says. Three ingredients are needed:

"1. How to build the receiver generator"
receiver := UmeGenerator oneOf: (10 to: 100).
"2. What must hold. The block receives the receiver, the arguments and the result"
property := [ :n :args :result | n * (n - 1) factorial = result ].
"3. A schema ties them to the method under test"
schema := UmeSchema new
    receiverConstraint: receiver;
    property: property;
    method: Integer >> #factorial.

Then let a runner execute it:

runner := UmeRunner test: schema times: 1000.
runner collectAllCases.   "keep every case, not only the remarkable ones"
result := runner run.

A method with arguments gets one constraint per argument:

schema := UmeSchema new
    receiverConstraint: UmeGenerator oneOf: (SmallInteger minVal to: SmallInteger maxVal));
    argumentConstraints: {
      UmeGenerator oneOf: (SmallInteger minVal to: SmallInteger maxVal)
    };
    property: [ :a :args :result | result = (a + args first) ];
    method: SmallInteger >> #+.

When to stop

A campaign can be resumed later from its result: result continueFor: 5 minutes or result continue: 1000.

Ume Result

run returns a UmeResult:

result tests.        "the collected cases (UmeTest instances)"
result topCases.     "the cases that set a new record during the search"
result totalCoverage. "coverage accumulated over the whole campaign"
result totalTime.

Every case knows its receiver, its arguments, and how the execution went:

test := result tests first.
test receiver.
test arguments.
test result isSuccess.   "the property held"
test result isFail.      "the property did not hold"
test result isError.     "the method raised an error"
test time.               "how long it took"

Where is the bug?

Ume groups the problems for you and points at suspicious code:

bugs := result localizeBugs.
bugs uniqueErrors.    "one report per distinct error"
bugs uniqueFailures.  "property violations"
bugs uniqueOutliers.  "performance outliers (see section 6)"

Failure reports rank the executed methods with a spectrum-based fault-localisation score. A method that runs in most failing cases and few passing ones comes first:

bugs uniqueFailures first suspectedMethods.

Ume Generators

Generators are the objects that produce values. The most common ones:

Building a richer object, such as a collection filled with generated items:

itemGen := UmeGenerator oneOf: (1 to: 100).
collection := UmeGenerator
    onceInstance: [ :instance :props |
        (1 to: 50) atRandom timesRepeat: [
          instance add: (props at: 'item') gen ].
      instance
    ] of: OrderedCollection.
receiver := UmeObjectConstraint new
    generator: collection;
    props: { 'item' -> itemGen }.

Need real object graphs, with back-pointers and constraints between fields? That is what Mate does. Its grammars plug into Ume as generators and mutators (UmeOGGrammarDerivationMutator).

Performance: From bugs to slow inputs

Here is the part that makes Ume different from a classic property-based testing tool. A property that is always true still leaves something to search for: cost.

The runner can be guided by a measurement. After each case, Ume compares what it measured with the best values seen so far. When a case beats a record, it becomes a top case, and the generators are told to build on it. Over time, the search drifts toward the inputs that make the code work hardest.

runner := UmeRunner test: schema for: 10 minutes.
runner guidedByMethodsCalls.
result := runner run.

Raw measurements are grouped into logarithmic buckets (ln of the value, rounded). A case taking 101 µs instead of 100 µs isn’t news. One taking 10× longer is. This keeps measurement noise from steering the search.

Guiding by method calls works much like PerfFuzz: every method is its own objective. An input that only makes one inner loop run much more often still counts as progress, even if total time hasn’t moved yet. That’s often the first step toward a pathological input.

A complete example: slow JSON documents

mutator := (UmeGrammarDerivationMutator from: JSONGrammar new) maxInputSize: 200.
json := UmeCorpusGenerator new
    seeds: { '{"a":[1,2,{"b":null}]}' };
    mutationsPerIteration: 3;
    mutators: { mutator };
    heuristic: UmePickBestElementDifferenceHeuristic new.
schema := UmeSchema new
    receiverConstraint: (UmeObjectConstraint new generator: (UmeGenerator always: NeoJSONReader));
    argumentConstraints: { UmeObjectConstraint new generator: json };
    property: [ :reader :args :result | true ];
    method: NeoJSONReader class >> #fromString:.
runner := UmeRunner test: NeoJSONReader class >> #fromString: from: schema for: 10 minutes.
runner guidedByMethodsCalls.
result := runner run.
result topCases last arguments first.   "the most demanding document found"

The same recipe has been applied to RxMatcher (regular expressions), Microdown, DataFrame, SVG parsing and Roassal graph layouts.

Mutating structured inputs

UmeCorpusGenerator keeps a corpus of interesting inputs. At each step it picks one, applies a mutator a few times and tries the result. Inputs that set a record are added to the corpus. Ume ships three families of mutators, from fast and blind to slow and structure-aware:

You don’t have to choose one. Give the generator several and let a scheduler learn which mutator pays off:

json := UmeCorpusGenerator new
    seeds: someSeeds;
    mutators: {
        UmeGrammarLiteralsMutator from: JSONGrammar new.
        UmeGrammarDerivationMutator from: JSONGrammar new.
        UmeAddByteMutator new.
        UmeByteFlipMutator new.
        UmeDelByteMutator new
    }; mutatorSelector: UmeMOPTMutatorSelector new.

How the next input is picked from the corpus is a heuristic too: UmeRandomSelectorHeuristic, UmeTournamentSelectorHeuristic, UmePickBestElementDifferenceHeuristic (the best case for some measured key).

The corpus can also be compacted to the smallest set of inputs that still holds every record: generator minimizeCorpus.

Explaining slow inputs

A slow input alone isn’t enough: you want to know why it’s slow. Ume compares each top case with the previous one and reports what grew:

outlier := result localizeBugs uniqueOutliers last.
outlier delta.             "which measurements grew, and by how much"
outlier suspectedMethods.  "methods this case executed that the previous record did not"

Charts help too (they use Roassal):

result plotByExecutionTime.     "time per case"
result plotByImprovements.      "when the records were broken"
result plotOutliers open.       "box plots of the outliers for time, memory, score and coverage"

To analyse a campaign somewhere else:

result exportAsCSV: 'json-campaign.csv'.   "one row per case: time, improvement, mutation metadata, inputs"
result writeToFile: 'json-campaign.ston'.  "the whole result, serialised with STON"

Keeping what you found as tests

A fuzzing campaign is only worth something if what it finds stays found. Subclass UmeUnitTest, describe the search once, and Ume writes the test methods for you:

UmeUnitTest << #PlayerDamageTest
    package: 'MyGame-Tests'.
PlayerDamageTest >> targetMethod [ ^ Player >> #damage ]
PlayerDamageTest >> receiverGenerator [
    ^ self
        corpusGenFrom: (Player new name: 'fede'; characterClass: Rogue new; level: 1; missingExperienceForNextLevel: 0)
        mpi: 3
        mutators: { UmeOGGrammarDerivationMutator from: MatePlayerGrammarByLang new }
]
PlayerDamageTest >> argumentGenerators [ ^ #() ]
PlayerDamageTest >> assert: receiver arguments: arguments result: result [ ^ result >= 0 ]
PlayerDamageTest >> guidedBy [ self guidedByMethodsCalls ]
PlayerDamageTest >> generateTests [
    <script: 'self new generateTests'>
    super generateTests: 10 minutes
]

Click the script. After ten minutes, the class has new methods such as:

test_692162816 [
    self doTest: {
        'method' -> (Player >> #damage) selector.
        'receiver' -> 'Player{#name:''odqi'',#characterClass:Rogue{},#level:1,#missingExperienceForNextLevel:542890132034813952}'.
        'arguments' -> '[]'.
    } asDictionary
]

Inputs are stored as STON, so the tests are plain Pharo methods: they run in the Test Runner and in CI and can be committed. generateRegressionTests: goes one step further: each test also stores the measurements of its case, so it fails if the input stops behaving as recorded.

Takeaway

• Instrumentation has a cost. Measuring calls and coverage means installing metalinks on every method in scope. Start with testWithLowCost: (only the target method). Widen the scope (methodsToInstrument:, package coverage) when the search stops finding new records.
• Prefer counting to timing. Time is noisy: the machine, the GC, and the JIT all leave their mark. Method calls, bytecodes and allocations are deterministic, so guide with them and use time to confirm the final candidates. When you do measure time, don’t run several campaigns in parallel on the same machine.
• Bound your inputs. Mutators accept maxInputSize:. Without a bound, “slowest input” quickly becomes “longest input”, which isn’t interesting. Fix a size, then find the shape that is slowest at that size.
• Invalid inputs are inputs too. Character mutators produce plenty of invalid JSON or regexes. That’s how you find crashes in parsers, but it also costs iterations. Grammar mutators keep inputs valid when validity is what you need.
• Collect what you need. By default, the runner keeps only top cases and errors, which keeps long campaigns light. Call collectAllCases if you want every case (for example, to analyse the whole run or to see every property failure).

Thanks a lot for reading! 🙂