Repository navigation
Home
You found an input that breaks your program, for example, a 3 KB JSON document, a 200-character regex, 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
- Three concepts: shrinker, oracle, grammar
- Shrinking strings and collections
- Shrinking structured inputs with a grammar
- Oracles: deciding what "still fails" means
- Measuring a reduction
- Benchmarking shrinkers
- Which shrinker should I use?
- Tips and pitfalls
- References
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.
| Concept | Question it answers | Example |
|---|---|---|
| Shrinker | How do I make the input smaller? |
ShinDDminPaperShrinker, ShinHDDShrinker, ShinVulcanShrinker
|
| Oracle | Does this smaller input still show the problem? | "it raises ZeroDivide", "it covers the same code" |
| Grammar | What does a valid input look like? (optional) |
AritExpressionGrammar, SvgPathGrammar
|
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.
Flat shrinkers see the input as a sequence (a String or any SequenceableCollection) 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.
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.
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).
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.
| Shrinker | Idea |
|---|---|
ShinHDDShrinker / ShinHDDPaperShrinker
|
Hierarchical Delta Debugging: ddmin applied level by level on the tree. |
ShinGRABRShrinker |
Replaces subtrees by smaller subtrees (or alternatives) of the same symbol, Perses style. |
ShinNautilusShrinker |
Replaces subtrees by the smallest derivation of their symbol. |
ShinVulcanShrinker |
HDD followed by auxiliary reducers: identifier replacement, subtree replacement and tree-based local exhaustive enumeration. |
ShinSADDminShrinker, ShinSAProbDDShrinker
|
Structure-aware ddmin / ProbDD: elements weighted by their position and shape in the tree. |
ShinSADDminHDDShrinker, ShinSAProbDDHDDShrinker
|
The two above, applied level by level inside HDD. |
ShinLazyPerfShrinker |
Batches subtree minimizations to save expensive oracle calls (designed for performance oracles). |
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.
| Oracle | Keeps inputs that… |
|---|---|
ShinBooleanInputOracle from: aBlock |
make the block answer true. The everyday choice. |
ShinDivideZeroOracle |
raise ZeroDivide when evaluated as Pharo code. |
ShinExecutionTimeOracle |
take at least threshold × the original execution time (default 95%). |
ShinMethodCallsOracle |
call at least threshold × as many instrumented methods as the original (default 95%). |
ShinCoverageOracle |
cover exactly the same code as the original. |
ShinFeedbackTableOracle |
keep a PBA profiling score at least threshold × the original. |
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.
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).
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.
Subclass ShinInputOracle (or ShinThresholdOracle for numeric scores) and implement:
| Method | Responsibility |
|---|---|
evalInput: input |
Measure the input (a Boolean, a number, a set…). Used to build the baseline. |
accepts: input from: baseline |
Answer whether input still shows the problem compared to baseline. |
valueBound: aBound |
Turn a measure into a number, used for the "% problem preservation" statistic. |
during: aBlock (optional)
|
Do an expensive setup/teardown once around a whole reduction. |
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
]profiledShrink: does the same work as shrink: and answers a dictionary with statistics:
result := shrinker profiledShrink: input.
result at: 'minimizedInput'. "the smallest input found"
result at: '%inputReduction'. "how much smaller, in %"
result at: 'neededReductions'. "oracle calls made"
result at: 'failedReductions'. "oracle calls that were rejected"
result at: 'totalTime'. "a Duration"
result at: '%problemPreservation'. "how much of the problem the result keeps"
result at: 'originalBound'. "the oracle's measure of the original input"
result at: 'minimizedBound'. "the oracle's measure of the result"neededReductions is exactly the number of times the oracle judged a candidate, which is usually the dominant cost of a reduction.
A benchmark is a corpus (inputs + oracle) and a grammar. You give it the shrinker classes to compare, and it runs each one on every input.
report := (ShinShrinkingAExprBenchmark for: { ShinHDDShrinker. ShinGRABRShrinker. ShinVulcanShrinker }) bench.
report plotInputReduction. "% input reduction per input"
report plotNeededReductions. "oracle calls"
report plotFailedReductions. "rejected oracle calls"
report plotTotalTime. "elapsed time (log scale)"
report plotProblemPreservation. "% problem preservation"
report saveAsFile: 'aexpr.json'. "raw results as JSON"| Input language | Coverage benchmark | Performance benchmark |
|---|---|---|
| Arithmetic expressions |
ShinShrinkingAExprBenchmark (divide by zero) |
|
| Regular expressions | ShinShrinkingRegexCoverageBenchmark |
ShinShrinkingRegexPerformanceBenchmark |
| JSON | ShinShrinkingJSONCoverageBenchmark |
ShinShrinkingJSONPerformanceBenchmark |
| Microdown | ShinShrinkingMicrodownCoverageBenchmark |
ShinShrinkingMicrodownPerformanceBenchmark |
| SVG paths | ShinShrinkingSVGCoverageBenchmark |
ShinShrinkingSVGPerformanceBenchmark |
| Roassal graphs | ShinShrinkingGraphCoverageBenchmark |
ShinShrinkingGraphPerformanceBenchmark |
Coverage benchmarks preserve the exact code coverage of the original input (ShinCoverageOracle); performance benchmarks preserve how many methods it calls (ShinMethodCallsOracle). The corpora live in datasets/.
Subclass ShinShrinkingBenchmark and fill grammar and tests in initialize:
ShinShrinkingBenchmark << #NumberListBenchmark
package: 'MyProject'.
NumberListBenchmark >> initialize [
| oracle |
super initialize.
grammar := NumberListGrammar new.
oracle := ShinBooleanInputOracle from: [ :s | s includesSubstring: '7' ].
tests := #( '[12,7,345]' '[1,2,3,4,5,6,77]' ) collect: [ :input |
ShinShrinkerTest input: input oracle: oracle ]
](NumberListBenchmark for: { ShinHDDShrinker. ShinGRABRShrinker }) bench saveAsFile: 'lists.json'.The shrinking-algorithms-benchmarks/ folder has one script per language. Each downloads Pharo 13, loads Shin and saves one JSON report per shrinker:
cd shrinking-algorithms-benchmarks
./run-svg.sh-
The input has no useful structure (bytes, a list of operations, a plain string) →
ShinDDminFuzzingBookShrinker. It's simple, robust, and the result is 1-minimal: no single element can be removed. -
The oracle is expensive and most elements are irrelevant →
ShinProbDDShrinkerorShinCDDShrinker. They learn which elements matter and usually need fewer oracle calls than ddmin. -
The input has a grammar → start with
ShinHDDShrinker(fast, predictable), orShinVulcanShrinkerwhen you want the smallest possible result and can afford more oracle calls. -
Replacing big subtrees by smaller ones of the same kind matters (e.g. replace a whole sub-expression by one of its operands) →
ShinGRABRShrinker. -
Each "the problem is still here" answer is slow, as with performance bugs →
ShinLazyPerfShrinker, which validates many reductions with a single oracle call. - Not sure? Write a small benchmark with a few of your inputs and compare. That's what the benchmark framework is for.
- Make the oracle deterministic. A flaky oracle makes any shrinker wander. For timing oracles, use a generous threshold.
- Make the oracle specific. "It raises an error" may be satisfied by a different error than the one you are chasing. Check the error class, and maybe its message.
-
Keep the oracle cheap. It is called many times (from dozens to thousands of calls per input).
profiledShrink:tells you exactly how many. -
Run more passes if needed.
shrinker maxIterations: 3repeats the reduction on its own result until it stops improving. -
Inputs outside the grammar are returned unchanged by
shrink:.profiledShrink:signals an error instead. -
Coverage benchmarks in Pharo 14. Pharo's
CoverageCollectorcan report empty node coverage when reused after an image save, and can leave metalinks installed when interrupted during installation.ShinCoverageOracleworks around both, so this only matters if you useCoverageCollectordirectly.
- Zeller & Hildebrandt, Simplifying and Isolating Failure-Inducing Input (ddmin), TSE 2002
- Misherghi & Su, HDD: Hierarchical Delta Debugging, ICSE 2006
- Sun et al., Perses: Syntax-Guided Program Reduction, ICSE 2018
- Aschermann et al., Nautilus: Fishing for Deep Bugs with Grammars, NDSS 2019
- Zeller et al., The Fuzzing Book, "Reducing Failure-Inducing Inputs"
- Wang et al., Probabilistic Delta Debugging (ProbDD), ESEC/FSE 2021
- Xu et al., Pushing the Limit of 1-Minimality of Language-Agnostic Program Reduction (Vulcan), OOPSLA 2023
- Zhang et al., Toward a Better Understanding of Probabilistic Delta Debugging (CDD), ICSE 2025
- Zhou et al., WDD: Weighted Delta Debugging, ICSE 2025
- SADD: Structure-Aware Delta Debugging, 2026
Source code, issues and datasets: https://github.com/FedeLoch/Shin