Shin: Shrinking inputs in Pharo

You found an input that breaks your program, for example, a 3 KB JSON document, or a 200-character regex, or an SVG path that makes the renderer hang. Before you can debug it, you want the smallest input that still shows the problem, right?

That is what Shin does. You give it an input and a way to recognize the problem, and it removes everything that doesn’t matter.

shrinker := ShinDDminPaperShrinker new.
shrinker oracle: (ShinBooleanInputOracle from: [ :string | string includes: $e ]).
shrinker shrink: 'asqjjkqsbdvieqvsbdoivbq'. "=> 'e'"

Shin is a Pharo library with self-contained implementations of the main input-reduction algorithms (delta debugging, HDD, Perses-like grammar reduction, Nautilus, Vulcan, ProbDD, CDD, WDD, SADD…), plus a small framework to benchmark them against each other.

Installation

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

This also loads Gnocco (grammars and parsing), NeoJSON, and PBA. Benchmark plots use Roassal, which ships with Pharo.

Three concepts: Shrinker, Oracle, and Grammar

The three are independent: any oracle works with any shrinker, and a grammar is only needed by the tree-based shrinkers. That’s what makes it easy to compare algorithms on exactly the same problem.

Every shrinker is used the same way:

shrinker := SomeShrinker new.
shrinker grammar: aGrammar. "only for grammar-based shrinkers"
shrinker oracle: anOracle.
smallest := shrinker shrink: input.

The result always still satisfies the oracle.

Shrinking strings and collections

Flat shrinkers see the input as a sequence (a String or any Collection) and remove elements. They know nothing about syntax.

shrinker := ShinDDminFuzzingBookShrinker new.
shrinker oracle: (ShinBooleanInputOracle from: [ :s |
	(s includes: $e) and: [ s includes: $a ] ]).
shrinker shrink: 'kjdsfhkjqsdhfehdkjsqfhkjsa'. "=> 'ea'"

Each element is handled independently, so repeated elements are not a problem:

shrinker oracle: (ShinBooleanInputOracle from: [ :s | s includesSubstring: 'bug' ]).
shrinker shrink: 'zzbzzuzzgzzbugzz'. "=> 'bug'"

Collections other than strings keep their class:

shrinker oracle: (ShinBooleanInputOracle from: [ :array | array includes: 4 ]).
shrinker shrink: #(1 2 3 4 5 6 7 8). "=> #(4)"

Flat shrinkers available: ShinDDminPaperShrinker, ShinDDminFuzzingBookShrinker, ShinProbDDShrinker, ShinCDDShrinker, ShinWDDminShrinker, ShinWDDProbShrinker.

The catch: a flat shrinker happily produces inputs that are no longer syntactically valid. If your program rejects them early, the oracle says “no”, and the reduction stalls. For structured inputs, use a grammar.

Shrinking structured grammar-based inputs

Grammar-based shrinkers parse the input into a tree and reduce the tree. Every candidate they try is valid according to the grammar, so the oracle spends its time on meaningful inputs.

Using a bundled grammar

Shin ships an arithmetic-expression grammar. Let’s find the smallest expression that still divides by zero:

shrinker := ShinVulcanShrinker new.
shrinker grammar: AritExpressionGrammar new.
shrinker oracle: ShinDivideZeroOracle new.
shrinker shrink: '((8500/(208000*80))+(165468468)*(423-12)*(999/(12+88)))/(((145*4)-580)*3)+((456)*12)-(89/(45+(12*8)))+(77*14)'.

The benchmarks also use grammars for regexes (GncRegexGrammar), JSON (JSONGrammar), Markdown/Microdown (ExtendedMarkdownGrammar), SVG paths (SvgPathGrammar) and Roassal graph scripts (RoassalGraphGrammar).

Writing your own grammar

Grammars are Gnocco grammars: a subclass of GncGrammar with one slot per non-terminal (names start with nt) and a defineGrammar method. Here is a grammar for lists of numbers such as [12,7,345]:

GncGrammar << #NumberListGrammar
	slots: { #ntStart. #ntItems. #ntNumber. #ntDigit };
	package: 'MyProject'.
NumberListGrammar >> defineGrammar [
	ntStart --> '[' , ']' | '[' , ntItems , ']'.
	ntItems --> ntNumber | ntNumber , ',' , ntItems.
	ntNumber --> ntDigit | ntDigit , ntNumber.
	ntDigit --> ($0 - $9).
	^ ntStart
]

--> defines the rules of a non-terminal, | separates alternatives, , concatenates, strings are literals, and ($0 - $9) is a character range.

Now shrink a list while keeping two equal numbers:

shrinker := ShinHDDShrinker new.
shrinker grammar: NumberListGrammar new.
shrinker oracle: (ShinBooleanInputOracle from: [ :s |
	| numbers |
	numbers := (s copyFrom: 2 to: s size - 1) substrings: ','.
	numbers size ~= numbers asSet size ]).
shrinker shrink: '[12,7,345,8,7,90]'. "=> '[7,7]'"

Every intermediate candidate is a well-formed list, and so is the result.

Shin Grammar-based shrinkers

Oracles: Deciding what “still fails” means

The oracle is where you encode what you are preserving. Shin evaluates the original input once to get a baseline, then asks the oracle, for every candidate, whether it still matches that baseline.

Ready-made oracles

Boolean oracles

ShinBooleanInputOracle from: [ :input | [ MyParser parse: input. false ]
	on: MyParserError do: [ true ] ]

Catch the error you are looking for inside the block, as above. Grammar-based shrinkers treat any other exception as “the problem disappeared”, but flat shrinkers let it propagate, and the reduction stops.

Preserving code coverage

Useful to find a small input that still exercises the same code, for instance to turn a fuzzer finding into a readable test:

oracle := ShinCoverageOracle new
	methodsToInstrument: RxMatcher package methods;
	evalBlock: [ :regex | regex asRegex matches: regex minimalStringMatching ];
	yourself.
shrinker := ShinDDminFuzzingBookShrinker new oracle: oracle; yourself.
shrinker shrink: 'b+bc||'.

The coverage oracle instruments the methods with metalinks once per reduction, and removes them when it finishes (even if it is interrupted).

Preserving a performance problem

oracle := ShinExecutionTimeOracle new
	evalBlock: [ :input | MySlowParser parse: input ];
	threshold: 0.9;
	yourself.

Candidates are kept as long as they stay at least 90% as slow as the original.

Writing your own oracle

Subclass ShinInputOracle (or ShinThresholdOracle for numeric scores) and implement:

ShinInputOracle << #LongestLineOracle
	package: 'MyProject'.
LongestLineOracle >> evalInput: input [
	^ (input lines collect: #size) inject: 0 into: [ :a :b | a max: b ]
]
LongestLineOracle >> accepts: input from: baseline [
	^ (self evalInput: input) = baseline
]
LongestLineOracle >> valueBound: aBound [
	^ aBound
]

Thanks a lot for reading! 🙂

Source code, issues, and datasets: https://github.com/FedeLoch/Shin