Shin is a Pharo library that provides implementations of state-of-the-art reducers: working, self-contained implementations of the most influential input-minimization and grammar-based reduction algorithms, including delta debugging, Hierarchical Delta Debugging (HDD), Nautilus, ProbDD, CDD, WDDProb, WDDmin, and Vulcan's reducers, so they can be reused and compared directly. Each reducer takes a potentially large input that triggers the behavior of interest and produces a much smaller input that still reproduces the same behavior. Shin is grammar-aware: it can parse inputs into a concrete syntax tree and reduce the tree, so the minimized output always stays valid according to the grammar.
Beyond the algorithms, Shin provides an architecture to benchmark shrinking algorithms. It separates three orthogonal concerns, shrinker, oracle, and grammar, and ships with ready-to-run benchmark classes and datasets for several input languages (regex, SVG, JSON, Microdown, arithmetic expressions), so different reducers can be evaluated head-to-head on the same corpora and reported with plots.
Load the latest stable version using Metacello:
Metacello new
baseline: 'Shin';
repository: 'github://FedeLoch/Shin:main';
onConflictUseIncoming;
load.The quickest way to shrink a string is to use the classic ddmin shrinker with a boolean oracle:
shrinker := ShinDDminPaperShrinker new.
shrinker oracle: (ShinBooleanInputOracle from: [ :string | string includes: $e ]).
(shrinker shrink: 'asqjjkqsbdvieqvsbdoivbq') "=> 'e'"Shin separates three orthogonal concerns:
- Shrinker — the reduction algorithm that iteratively tries to remove or simplify parts of the input.
- Oracle — decides whether a given candidate input still triggers the behavior of interest.
- Grammar — (optional, for tree-based shrinkers) describes the input language so reductions stay syntactically valid.
Shin provides the following shrinkers. Tree-based ones are grammar-aware.
| Shrinker | Type | Description |
|---|---|---|
ShinDDminPaperShrinker |
Array/string | Classic delta-debugging ddmin from the original delta-debugging paper. |
ShinDDminPaperCustomShrinker |
Array/string | ddmin variant with custom recursion/statistics callbacks. |
ShinDDminFuzzingBookShrinker |
Array/string | ddmin variant following Zeller's "The Fuzzing Book". |
ShinHDDShrinker |
Grammar tree | Hierarchical Delta Debugging, applies ddmin level by level over the parse tree. |
ShinGRABRShrinker |
Grammar tree | Grammar-based reduction that replaces subtrees with grammar-derived smaller candidates. |
ShinNautilusShrinker |
Grammar tree | Reward-based reduction inspired by Nautilus, repeatedly minimizing the "worst" node. |
ShinVulcanShrinker |
Grammar tree | Combines a main reducer (HDD) with auxiliary reducers: identifier replacement, subtree reduction, and tree-based Linear Example-based Edition (LEE). |
ShinProbDDShrinker |
Array/string | Probabilistic delta debugging, models the probability of each element being kept in the result and selects subsets that maximize expected reduction gain, learning from test history instead of following ddmin's fixed removal order. |
ShinCDDShrinker |
Array/string | Counter-based delta debugging, a simplified version of ProbDD that replaces probability computations with counters, skipping inefficient complement/repeated deletion attempts. |
ShinWDDminShrinker |
Array/string | Weighted ddmin, partitions elements by size (weight) instead of count, with an extra deletion pass to ensure 1-minimality. |
ShinWDDProbShrinker |
Array/string | Weighted ProbDD, factors element size into the probabilistic model to prioritize removing larger elements. |
An oracle decides whether a candidate input still reproduces the target behavior.
ShinInputOracle is the abstract base class; the following implementations are provided:
| Oracle | Description |
|---|---|
ShinBooleanInputOracle |
Runs a boolean block on the input (e.g. "does it raise an error?"). |
ShinDivideZeroOracle |
Detects division-by-zero in arithmetic expressions. |
ShinExecutionTimeOracle |
Checks execution time against a threshold. |
ShinThresholdOracle |
Base class that accepts an input if its bound is above a fraction (threshold, default 0.95) of the original bound. |
ShinCoverageOracle |
Preserves code-coverage properties (uses C2CoverageCollector to instrument methods). |
ShinMethodCallsOracle |
Preserves the set of methods called by the execution. |
ShinFeedbackTableOracle |
Compares a feedback table against the baseline. |
For tree-based shrinkers, provide a grammar and an oracle. For example, minimizing an arithmetic expression that contains a division by zero:
shrinker := ShinVulcanShrinker new.
shrinker grammar: AritExpressionGrammar new.
shrinker oracle: ShinDivideZeroOracle new.
input := '((8500/(208000*80))+(165468468)*(423-12)*(999/(12+88)))/(((145*4)-580)*3)+((456)*12)-(89/(45+(12*8)))+(77*14)'.
minimized := shrinker shrink: input.Shin provides ready-to-use benchmark classes per input language (regex, SVG, JSON, Microdown, arithmetic expressions). Each one sets its own grammar and test corpus, simply pick one, add the shrinker classes you want to compare, and run it:
bench := ShinShrinkingRegexBenchmark new.
bench shrinkers: { ShinHDDShrinker. ShinGRABRShrinker. ShinNautilusShrinker }.
report := bench bench.To benchmark a shrinker on your own corpus, subclass ShinShrinkingBenchmark and populate grammar and tests (a list of ShinShrinkerTest instances built with input:oracle:) in #initialize.
report plotInputReduction. "plot % input reduction across tests"
report plotProblemPreservation. "plot % problem preservation"
report plotTotalTime. "plot elapsed time (log scale)"
report plotNeededReductions. "plot number of needed reductions"
report plotFailedReductions. "plot number of failed reductions"
report saveAsFile: 'results.json'.Plots are built with Roassal and benchmark results can be exported as JSON.
- Pharo (current stable release supported by the CI workflow).
- Roassal, used for benchmark plot generation.
- Delta debugging: Zeller 1999
- Hierarchical Delta Debugging (HDD): Misherghi & Su
- Nautilus: Astrauskas et al.
- Vulcan: FuzzBench
- Perses: Perses
- The Fuzzing Book: Zeller et al.
- Probabilistic Delta Debugging: ProbDD
- CDD, a simplified version of ProbDD: CDD
- WDD: Weighted Delta Debugging: WDD
- WDD: Weighted Probabilistic Delta Debugging: WDD
This project is licensed under the terms shown in the repository.