Opensource internals

BuzzHouse's Grammar Drifts: How a Fuzzer Stops Repeating Itself

18 min read Jay Hubbert

BuzzHouse generates SQL from a protobuf grammar whose per-operation probabilities are bounded intervals that drift by 10% every 500 draws, so the fuzzer keeps moving to new shapes of query.

TL;DR: BuzzHouse does not pick “the next kind of expression” with a fixed coin flip. Every kind has a probability interval, the intervals are re-randomised by ±10 % every 500 draws (“drifting”), and the enabled set is recomputed from the current depth, width and query context. The grammar therefore moves through the space of queries instead of camping in it.

A random query generator has one job that is much harder than it sounds: not repeating itself.

The naive implementation is a fixed weight per choice — “40 % literals, 30 % column references, 30 % function calls” — and it fails in a specific and well-known way. The generator has a mode. The mode is the shape of query that the fixed weights make most likely, and after a few thousand iterations the fuzzer is generating that shape over and over. The rare-but-valuable shapes — the deep nest, the correlated subquery, the CASE inside a window frame — are generated at a rate of 0.1 % and are effectively never seen.

There is a second, subtler failure. The generator must not produce queries that are trivial in the sense that matters for the oracle: a predicate that is constantly FALSE, an expression that never touches a column, a GROUP BY whose key is a literal. Those queries are valid, they run, they produce a consistent answer, and they teach the fuzzer nothing. Worse, a trivial predicate makes the correctness oracle vacuously true — both the grouped and the flat rewrite return zero, so the oracle “passes” without ever comparing anything.

BuzzHouse’s answer has three parts: a grammar that is a data structure, not a string; a probability model that drifts; and a budget on the size and shape of what it generates.

The pipeline, from context to a chosen operation:

text 
   context (depth, width, query level, flags)
            |
            v
   expMask[op] = ...              <- which operations are legal right now
            |
            v
   ProbabilityGenerator.setEnabled(mask)
            |
            v
   zero the disabled ones, renormalise, clamp to the declared intervals
            |
            v
   buildCdf()  ->  nextOp(): binary search on a uniform draw
            |
            v
   every 500 draws: applyDrift() -> renormalise -> clamp -> buildCdf

The grammar is a protobuf, not a string

The first decision is that the fuzzer never writes SQL text directly. It builds a typed AST, described in a protobuf schema:

proto 
// src/Client/BuzzHouse/Proto/SQLGrammar.proto:674
message ComplicatedExpr {
    oneof complicated_expr_oneof {
        ExprSchemaTableColumn expr_stc = 1;
        UnaryExpr unary_expr = 2;
        BinaryExpr binary_expr = 3;
        ExprColAlias alias_expr = 4;
        CastExpr cast_expr = 5;
        ExprBetween expr_between = 6;
        ExprIn expr_in = 7;
        ExprAny expr_any = 8;
        ExprTruthTests expr_truth_tests = 9;
        ExprCase expr_case = 10;
        ExprExists expr_exists = 11;
        ExprLike expr_like = 12;
        CondExpr expr_cond = 13;
        ExplainQuery subquery = 14;
        SQLFuncCall func_call = 15;
        WindowFuncCall window_call = 16;
        IntervalExpr interval = 17;
        string columns = 18;
        ExprList array = 19;
        ExprList tuple = 20;
        SQLIdentifier table = 21;
        LambdaExpr lambda = 22;

The oneof is the important part: an expression is exactly one of these kinds, and the protobuf runtime enforces that. A text-based generator has to decide, at every point, “am I now emitting an operator or an operand?”, and the two decisions can get out of sync, producing a stream of ) characters. A protobuf AST cannot get out of sync, because there is only one thing to fill in at a time.

The AST is then serialised to SQL text in one place, at the very end:

cpp 
// src/Client/BuzzHouse/AST/SQLProtoStr.cpp:6029
void SQLQueryToString(String & ret, const SQLQuery & query)
{
    SingleSQLQueryToString(ret, query.single_query());
    for (int i = 0; i < query.parallel_queries_size(); i++)
    {
        ret += " PARALLEL WITH ";
        SingleSQLQueryToString(ret, query.parallel_queries(i));
    }
    ret += ";";
}

This has a pleasant side effect for a SQL fuzzer: the generated statement is structurally valid SQL by construction, so the errors the fuzzer sees are overwhelmingly semantic ones (unknown column, wrong type, cannot compare) rather than parse failures, and the fuzzer does not waste its time re-discovering that a stray ) is a syntax error. It also means the AST can be inspected, counted, and reasoned about independently of the text.

The contextual mask: what is even possible right now

Not every operation is legal in every context, and the generator encodes that as a mask — a bit per operation — that is recomputed before every draw.

cpp 
// src/Client/BuzzHouse/Generator/SQLExpression.cpp:1227
    expMask[static_cast<size_t>(ExpOp::Predicate)] = this->fc.max_depth > this->depth;
    expMask[static_cast<size_t>(ExpOp::CastExpr)] = this->fc.max_depth > this->depth;
    expMask[static_cast<size_t>(ExpOp::UnaryExpr)] = this->fc.max_depth > this->depth;
    expMask[static_cast<size_t>(ExpOp::IntervalExpr)] = this->fc.max_depth > this->depth;
    expMask[static_cast<size_t>(ExpOp::ColumnsExpr)]
        = this->fc.max_depth > this->depth && (this->allow_not_deterministic || this->levels[this->current_level].inside_aggregate);
    expMask[static_cast<size_t>(ExpOp::CondExpr)] = this->fc.max_depth > this->depth && this->fc.max_width > this->width;
    expMask[static_cast<size_t>(ExpOp::CaseExpr)] = this->fc.max_depth > this->depth && this->fc.max_width > this->width;

and further down, the operations that depend on the query context rather than on the size budget:

cpp 
// src/Client/BuzzHouse/Generator/SQLExpression.cpp:1239
    expMask[static_cast<size_t>(ExpOp::WindowFuncExpr)] = this->fc.max_depth > this->depth
        && this->levels[this->current_level].allow_window_funcs && !this->levels[this->current_level].inside_aggregate;
    expMask[static_cast<size_t>(ExpOp::TableStarExpr)]
        = (this->allow_not_deterministic || this->levels[this->current_level].inside_aggregate)
        && std::find_if(level_rels.begin(), level_rels.end(), has_rel_name_lambda) != level_rels.end();
    expMask[static_cast<size_t>(ExpOp::LambdaExpr)] = this->fc.max_depth > this->depth && this->fc.max_width > this->width;
    expMask[static_cast<size_t>(ExpOp::ProjectionExpr)] = this->inside_projection;
    expMask[static_cast<size_t>(ExpOp::DictExpr)] = this->fc.max_depth > this->depth && collectionHas<SQLDictionary>(has_dictionary_lambda);
    expMask[static_cast<size_t>(ExpOp::JoinExpr)] = this->fc.max_depth > this->depth && collectionHas<SQLTable>(has_join_table_lambda);
    expMask[static_cast<size_t>(ExpOp::StarExpr)] = this->allow_not_deterministic || this->levels[this->current_level].inside_aggregate;

Note what is not in that list: Literal and ColumnRef. Their mask entries are commented out:

cpp 
// src/Client/BuzzHouse/Generator/SQLExpression.cpp:1225
    /// expMask[static_cast<size_t>(ExpOp::Literal)] = true;
    /// expMask[static_cast<size_t>(ExpOp::ColumnRef)] = true;

The masks start out all-true in the constructor and these two are never disabled, which means an expression is always rooted in either a literal or a column reference. That is the structural version of “liveness”: the generator cannot wander into a state where an expression is built out of nothing but operators.

The same idea governs the predicate grammar, where the mask is a function of the remaining depth and width budget:

cpp 
// src/Client/BuzzHouse/Generator/SQLExpression.cpp:605
    predMask[static_cast<size_t>(PredOp::UnaryExpr)] = this->fc.max_depth > this->depth;
    predMask[static_cast<size_t>(PredOp::BinaryExpr)] = this->fc.max_depth > this->depth && this->fc.max_width > (this->width + 1);
    predMask[static_cast<size_t>(PredOp::BetweenExpr)] = this->fc.max_depth > this->depth && this->fc.max_width > (this->width + 2);
    predMask[static_cast<size_t>(PredOp::InExpr)] = this->fc.max_depth > this->depth && this->fc.max_width > this->width;
    predMask[static_cast<size_t>(PredOp::AnyExpr)]
        = this->fc.max_depth > this->depth && this->fc.max_width > (this->width + 1) && this->allow_subqueries;
    predMask[static_cast<size_t>(PredOp::IsTruthExpr)] = this->fc.max_depth > this->depth;
    predMask[static_cast<size_t>(PredOp::ExistsExpr)] = this->fc.max_depth > this->depth && this->allow_subqueries;
    predMask[static_cast<size_t>(PredOp::LikeExpr)] = this->fc.max_depth > this->depth;
    predMask[static_cast<size_t>(PredOp::SearchExpr)] = this->fc.max_depth > this->depth;
    predMask[static_cast<size_t>(PredOp::OtherExpr)] = this->fc.max_depth > this->depth;

BETWEEN needs three operands and therefore two units of width; ANY/ALL needs a subquery and therefore allow_subqueries. When the budget runs out, the mask empties itself and the generator falls back to a literal:

cpp 
// src/Client/BuzzHouse/Generator/SQLExpression.cpp:596
void StatementGenerator::generatePredicate(RandomGenerator & rg, Expr * expr)
{
    if (this->fc.max_depth <= this->depth)
    {
        /// In the worst case, not a single option can be picked
        this->generateLiteralValue(rg, true, expr);
        return;
    }

The budget: depth and width

The two numbers that control all of this are in the configuration, and they are small:

cpp 
// src/Client/BuzzHouse/Generator/FuzzConfig.h:380
    uint32_t max_depth = 3;
    uint32_t max_width = 3;

depth is the nesting level of the expression tree; width is the number of sibling sub-expressions at the current level. Both are plain counters on the generator:

cpp 
// src/Client/BuzzHouse/Generator/StatementGenerator.h:202
    uint32_t depth = 0;
    uint32_t width = 0;

and every recursive generator maintains them by hand. A binary expression spends one unit of width and one of depth:

cpp 
// src/Client/BuzzHouse/Generator/SQLExpression.cpp:1363
        case ExpOp::BinaryExpr: {
            BinaryExpr * bexpr = expr->mutable_comp_expr()->mutable_binary_expr();
            std::uniform_int_distribution<uint32_t> binop_range(
                rg.nextSmallNumber() < 9 ? static_cast<uint32_t>(BinaryOperator::BINOP_CONCAT) : 1,
                static_cast<uint32_t>(BinaryOperator_MAX));

            bexpr->set_op(static_cast<BinaryOperator>(binop_range(rg.generator)));
            this->depth++;
            this->generateExpression(rg, bexpr->mutable_lhs());
            this->width++;
            this->generateExpression(rg, bexpr->mutable_rhs());
            this->width--;
            this->depth--;
        }
        break;

Why is the budget so tight? Two reasons. First, a fuzzer that generates queries nobody can read is a fuzzer whose failures nobody can reproduce. Second — and this is the one that matters for the oracle — a deep, wide expression is a query whose result is hard to attribute: when the oracle finds a mismatch, you want the smallest possible reproducer. A depth of 3 and a width of 3 means the generated expression is a tree of at most a handful of nodes, and the HAVING-versus-flat rewrite differs in one place.

The width counter is also what keeps the number of rows of the result bounded. The correctness oracle sums a predicate over the table; a predicate that fans out into a CASE with eight branches multiplies the work for no extra coverage.

The probability model: intervals, not weights

Now the part that keeps the fuzzer moving. Each kind of operation has not a weight but a probability interval, and the generator’s state is a probability vector over the operations:

cpp 
// src/Client/BuzzHouse/Generator/ProbabilityGenerator.h:13
enum class ProbabilityStrategy
{
    Balanced = 0,
    BoundedRealism,
    Drifting
};

struct ProbabilityBounds
{
    double min = 0.0;
    double max = 1.0;
};

The intervals are declared per generator, with a comment naming the operation, so the shape of the language is readable in the source:

cpp 
// src/Client/BuzzHouse/Generator/StatementGenerator.cpp:133
    , predGen(ProbabilityGenerator(
          static_cast<ProbabilityStrategy>(rg.randomInt<uint32_t>(0, 2)),
          rg.nextInFullRange(),
          {{
              {0.03, 0.30}, /// UnaryExpr
              {0.10, 0.50}, /// BinaryExpr
              {0.05, 0.20}, /// BetweenExpr
              {0.02, 0.15}, /// InExpr
              {0.02, 0.15}, /// AnyExpr
              {0.05, 0.20}, /// IsNullExpr
              {0.02, 0.15}, /// ExistsExpr
              {0.03, 0.20}, /// LikeExpr
              {0.10, 0.35}, /// SearchExpr
              {0.03, 0.05} /// OtherExpr
          }},
          "SQL predicates"))

Read those intervals as: “a binary predicate is between 10 % and 50 % likely; an EXISTS is between 2 % and 15 % likely; OtherExpr — the catch-all — is between 3 % and 5 %.” The catch-all has a narrow interval on purpose: it is the operation that produces whatever the generator has not thought of, and it should be rare but not vanishing.

Note the strategy: the generator picks one of the three strategies at random for each of the five generators:

cpp 
// src/Client/BuzzHouse/Generator/StatementGenerator.cpp:46
    , SQLGen(ProbabilityGenerator(
          static_cast<ProbabilityStrategy>(rg.randomInt<uint32_t>(0, 2)),

so a single run may use Balanced for statements and Drifting for predicates, and the next run with a different seed will use a different mix. The strategy is part of the seed, so the run is reproducible.

Balanced draws an exponential weight per operation and rejects the draw if the ratio between the largest and the smallest weight is too extreme:

cpp 
// src/Client/BuzzHouse/Generator/ProbabilityGenerator.cpp:147
std::vector<double> ProbabilityGenerator::genBalanced()
{
    /// Resample a few times to avoid extreme skew among enabled ops.
    for (int attempt = 0; attempt < std::max(1, balanced_resample_attempts); ++attempt)
    {
        std::vector<double> w(nvalues, 0.0);
        std::exponential_distribution<double> exp_dist(1.0);
        for (size_t i = 0; i < nvalues; ++i)
            w[i] = enabled_values[i] ? (exp_dist(generator) + kEpsilon) : 0.0;

        normalizeEnabledInPlace(w, enabled_values);

        const auto [mn, mx] = minmaxEnabled(w, enabled_values);
        const double ratio = (mn > 0.0) ? (mx / mn) : std::numeric_limits<double>::infinity();
        if (ratio <= balanced_max_ratio)
            return w;
    }

The acceptance threshold is balanced_max_ratio = 6.0 — no operation may be more than six times more likely than the least likely one. Twenty resampling attempts, then give up and take the last draw.

BoundedRealism draws each operation uniformly inside its own interval and then renormalises, so the result respects the declared plausibility of each operation while still being random.

Drifting starts from BoundedRealism and then moves the distribution, periodically, for the whole life of the run:

cpp 
// src/Client/BuzzHouse/Generator/ProbabilityGenerator.cpp:197
void ProbabilityGenerator::applyDrift()
{
    /// drift only enabled ops
    std::uniform_real_distribution<double> unif(-drift_strength, drift_strength);
    std::vector<double> w = probabilities;

    for (size_t i = 0; i < nvalues; ++i)
    {
        if (!enabled_values[i])
        {
            w[i] = 0.0;
            continue;
        }
        w[i] = w[i] * (1.0 + unif(generator));
        w[i] = std::max(w[i], 0.0);
    }

    normalizeEnabledInPlace(w, enabled_values);
    clampToBoundsAndRenormEnabled(w, enabled_values);
    probabilities = w;
}

Each enabled operation’s probability is multiplied by a random factor in [0.9, 1.1], the vector is renormalised, and the result is clamped back into the declared intervals. The drift is triggered by a counter, not by a clock:

cpp 
// src/Client/BuzzHouse/Generator/ProbabilityGenerator.h:33
    /// Drifting controls
    uint64_t drift_every_n_ops = 500;
    double drift_strength = 0.10; /// ±10%

so every 500 draws the distribution wobbles by at most ±10 %. Over a run of a million draws that is two thousand wobbles, and because the wobble is multiplicative and the clamp is a projection back into the intervals, the distribution performs a random walk inside the plausible region rather than collapsing to a corner. EXISTS, which starts between 2 % and 15 %, will wander up to 15 %, get clamped, drift down towards 2 %, get clamped again.

The call site says it plainly:

cpp 
// src/Client/BuzzHouse/Generator/SQLExpression.cpp:1260
    switch (static_cast<ExpOp>(expGen.nextOp())) /// drifts over time

The clamp: water-filling

The clamping step is the mathematically interesting part. After a drift, the probabilities may violate the declared intervals, and the intervals are not independent: they must still sum to 1. A naive “clamp each to its own interval” would break the sum. The implementation is a small water-filling algorithm: clamp the violated ones, take the leftover mass, and redistribute it proportionally among the ones that are still free.

cpp 
// src/Client/BuzzHouse/Generator/ProbabilityGenerator.cpp:316
    std::vector<bool> fixed(nvalues, false);
    for (int iter = 0; iter < kClampMaxIterations; ++iter)
    {
        for (size_t i = 0; i < nvalues; ++i)
        {
            if (!enabled[i])
            {
                p[i] = 0.0;
                fixed[i] = true;
                continue;
            }

            if (p[i] < bounds[i].min)
            {
                p[i] = bounds[i].min;
                fixed[i] = true;
            }
            else if (p[i] > bounds[i].max)
            {
                p[i] = bounds[i].max;
                fixed[i] = true;
            }
            else
                fixed[i] = false;
        }

        double used = 0.0;
        for (size_t i = 0; i < nvalues; ++i)
            used += p[i];
        double remaining = 1.0 - used;

        if (std::fabs(remaining) < kEpsilon)
        {
            /// tiny adjustment to first enabled op
            for (size_t i = 0; i < nvalues; ++i)
            {
                if (enabled[i])
                {
                    p[i] += remaining;
                    break;
                }
            }
            normalizeEnabledInPlace(p, enabled);
            return;
        }

        double free_mass = 0.0;
        for (size_t i = 0; i < nvalues; ++i)
            if (enabled[i] && !fixed[i])
                free_mass += p[i];

        if (free_mass <= 0.0)
        {
            /// No free vars left; nudge first enabled and exit
            for (size_t i = 0; i < nvalues; ++i)
                if (enabled[i])
                {
                    p[i] += remaining;
                    break;
                }
            normalizeEnabledInPlace(p, enabled);
            return;
        }

        for (size_t i = 0; i < nvalues; ++i)
            if (enabled[i] && !fixed[i])
                p[i] += remaining * (p[i] / free_mass);
    }

The iteration count is capped at kClampMaxIterations = 10 — “the loop converges in a handful of passes in practice; the cap is a safety net so a pathological bounds set cannot spin forever”. The bounds are also validated for feasibility before any of this: the enabled subset’s minimums must be able to sum to 1, and so must its maximums.

cpp 
// src/Client/BuzzHouse/Generator/ProbabilityGenerator.cpp:310
    if (sum_min > 1.0 + kEpsilon)
        throw DB::Exception(DB::ErrorCodes::BUZZHOUSE, "Inconsistent bounds for enabled subset at {} (cannot min sum to 1)", description);
    if (sum_max < 1.0 - kEpsilon)
        throw DB::Exception(DB::ErrorCodes::BUZZHOUSE, "Inconsistent bounds for enabled subset at {} (cannot max sum to 1)", description);

This is a configuration error, and the fuzzer refuses to start rather than silently generating garbage. That is the right call: a fuzzer whose grammar is inconsistent will find “bugs” that are really just its own confusion.

Drawing from the distribution

The final piece is the sampling itself. The generator keeps a cumulative distribution and does a binary search, with a careful fix for the floating-point edge case where the last bucket is disabled:

cpp 
// src/Client/BuzzHouse/Generator/ProbabilityGenerator.cpp:83
size_t ProbabilityGenerator::nextOp(const bool tick)
{
    if (tick)
        this->tick();

    const double u = uniform_unit(generator);

    /// Binary search for the first bucket whose cdf is strictly greater than u.
    /// O(log N) per sample versus the previous O(N) linear scan. The CDF is built so the
    /// last enabled bucket has cdf == 1.0 (see buildCdf); disabled buckets keep the running
    /// sum unchanged so they cannot be picked unless u falls exactly on a tie, which is
    /// vanishingly unlikely with uniform_real_distribution.
    const auto it = std::upper_bound(cdf.begin(), cdf.end(), u);
    if (it == cdf.end())
        return lastEnabledIndex();
    const size_t idx = static_cast<size_t>(it - cdf.begin());
    /// Guard the FP-edge case where u rounds up onto a disabled trailing bucket whose CDF
    /// was forced to 1.0 prior to this fix.
    return enabled_values[idx] ? idx : lastEnabledIndex();
}

and the CDF builder, which pins the last enabled bucket to exactly 1.0 and carries that forward over the disabled tail:

cpp 
// src/Client/BuzzHouse/Generator/ProbabilityGenerator.cpp:219
void ProbabilityGenerator::buildCdf()
{
    double running = 0.0;

    for (size_t i = 0; i < nvalues; ++i)
    {
        running += probabilities[i];
        cdf[i] = running;
    }
    /// Pin the LAST ENABLED bucket's cdf to exactly 1.0 so floating-point drift in the
    /// running sum can never leave a sliver of probability that maps to a disabled trailing
    /// bucket. Previously this unconditionally set cdf[nvalues - 1] = 1.0, which gave the
    /// disabled last bucket the full upper tail of the unit interval.
    const size_t last_enabled = lastEnabledIndex();
    cdf[last_enabled] = 1.0;
    /// Carry that 1.0 forward over any disabled trailing buckets so upper_bound still
    /// terminates inside the cdf array for u close to 1.0.
    for (size_t i = last_enabled + 1; i < nvalues; ++i)
        cdf[i] = 1.0;
}

The comment preserves the bug it fixed, which is the kind of comment worth having: the old code gave the disabled last bucket the entire upper tail of the unit interval, so a query could occasionally ask for an operation the mask had just forbidden.

Determinism when it matters

The drifting distribution is great for exploration and terrible for reproducibility — unless the seed fixes it. The whole generator is driven by a single PCG generator:

cpp 
// src/Client/BuzzHouse/Generator/RandomGenerator.h:128
    pcg64_fast generator;

    RandomGenerator(const uint64_t in_seed, const uint32_t min_string_length, const uint32_t max_string_length, const bool limited)
        : seed(in_seed ? in_seed : randomSeed())

and the drift counter is a plain counter, not a clock, so the sequence of distributions is a pure function of the seed.

But there is one more thing: for an oracle run, the query must be deterministic, or the two runs of the “same” query will differ for reasons that have nothing to do with the bug. The generator has an explicit switch for this:

cpp 
// src/Client/BuzzHouse/Generator/StatementGenerator.h:195
    bool allow_not_deterministic = true;

and the oracle turns it off around the generation of the query:

cpp 
// src/Client/BuzzHouse/Generator/QueryOracle.cpp:1636
    gen.setAllowNotDetermistic(false);
    gen.enforceFinal(true);
    gen.generatingPeerQuery(pq);
    gen.setAllowEngineUDF(peer_query != PeerQuery::ClickHouseOnly);

enforceFinal(true) matters too: it forces SELECT ... FINAL, so the comparison is against the merged state of the table and not against whatever partial state a background merge happens to have left behind. Two runs of the same query against a table that is being merged in the background can legitimately differ; FINAL removes that degree of freedom.

The switch also appears in the literal generator, where a non-deterministic literal (randomString, now()) is only allowed in a “complex” position:

cpp 
// src/Client/BuzzHouse/Generator/SQLExpression.cpp:199
    litMask[static_cast<size_t>(LitOp::LitRandStr)] = complex && this->allow_not_deterministic;

A different fuzzer, for contrast

BuzzHouse is not the only fuzzer in the tree. src/Common/QueryFuzzer.cpp — 9 471 lines — takes the opposite approach: it takes a real query, parses it into a real ClickHouse AST, and mutates the AST in place. The mutation loop is guarded by a check for a mutation that changed nothing:

cpp 
// programs/client/FuzzLoop.cpp:301
            query_to_execute = ast_to_process->formatForErrorMessage();
            if (fuzz_step > 0 && query_to_execute == base_before_fuzz)
            {
                fmt::print(stderr, "Got boring AST\n");
                continue;
            }

That is the “liveness” check in its most literal form: if the fuzzed AST formats to the same text as the original, the mutation was a no-op and the step is skipped. The same idea, applied to a generated grammar, is the structural guarantee that Literal and ColumnRef are never masked out.

The two fuzzers are complementary: the AST fuzzer explores around real queries, the BuzzHouse generator explores the space of queries. The repository runs both.

Trade-offs

What the design buys.

  • Coverage that moves. The drift is a random walk inside a plausible region, so the fuzzer spends its time on shapes that are plausible for a real user, while still moving between them. A fixed-weight generator explores one shape thoroughly and the rest not at all.
  • No syntax errors. The protobuf grammar makes a malformed query structurally impossible, so the failures the fuzzer reports are about semantics.
  • Bounded queries. Depth 3, width 3 means a reproducer is small enough to paste into a bug report.
  • Determinism where it counts. The oracle path disables non-determinism and forces FINAL, so a mismatch is a mismatch and not a race.

What it costs.

  • The bounds are hand-maintained and they matter. An interval that is too wide makes the distribution meaningless; too narrow and the drift has nowhere to go. There are five generators with 28 + 18 + 23 + 10 + 22 operations between them, and every one of those numbers is a tuning decision somebody had to make.
  • The drift is blind. ±10 % every 500 draws is a heuristic. It does not know that a shape has been under-explored; it just wanders. A coverage-guided fuzzer would know, and would be strictly better at this.
  • The clamp is O(N) per drift and O(N) per rebuild, and the CDF is rebuilt on every mask change, which happens on every expression generation. For a grammar with 23 operations that is trivial; it is not free.
  • Trivial predicates are still possible. If the generated predicate happens to be constantly FALSE, the correctness oracle compares zero with zero and passes without testing anything. The structural guarantee is that an expression is rooted in a literal or a column, not that it is selective. Making the oracle reject a vacuous comparison (e.g. requiring the first query’s count to be strictly between 0 and the table’s row count) would be an obvious improvement, and it is not implemented.
  • The masking rules are the real complexity. The grammar’s semantics live in ~30 lines of expMask[...] = ... conditions that encode “a window function is not allowed inside an aggregate”, “a * is not allowed in an oracle query”, “a dictionary expression needs a dictionary in scope”. Every new SQL feature means new conditions, and a missing condition means the fuzzer generates invalid SQL and the failure is reported as a server error rather than a fuzzer bug.

The one thing to remember: the interesting part is not that the fuzzer generates random SQL — that is easy. The interesting part is that the distribution over SQL is a first-class, bounded, slowly moving object, and that the mask makes the grammar contextual rather than merely random.

The part people get wrong: “random” and “uniform” are not the same thing, and neither is “plausible”. A generator that samples uniformly over the SQL grammar produces mostly nonsense; one that samples from fixed weights produces mostly the same thing. BuzzHouse’s answer — intervals, plus a mask, plus a slow random walk — is a compromise between the two.

ClickhouseTestingFuzzingInternals