Skip to content
STIMSMITH

Bottom-Up Generation

Concept WIKI v1 · 8/4/2026

In software and hardware testing, bottom-up generation is a methodology for synthesizing program or design code by first constructing a syntactically valid skeleton (a partial template) and then completing it through type/name inference and code injection, rather than by starting from a small valid core and expanding outward as in top-down generation. This approach is exemplified by the ChiGen Verilog fuzzer, which uses probabilistic grammars guided by k-gram production-rule statistics, Hindley-Milner type inference to assign names and types, and Li-Zhendong-style code injection enabled by data-flow analysis. By decoupling skeleton construction from completion, bottom-up generation can produce both semantically valid and intentionally invalid specifications, enabling broader coverage of language productions and richer fuzzing of tools such as EDA platforms and formal verifiers.

Definition

Bottom-up generation refers to a code-synthesis strategy in which a program or hardware-design source file is built in two phases:

  1. Skeleton construction – First, a syntactically valid but incomplete template (skeleton) of the target language is produced via a probabilistic grammar.
  2. Skeleton completion – Second, the skeleton is completed by inferring identifiers, types, and additional code, yielding a full source-level artifact.

This stands in contrast to top-down generation, where generation begins from a small valid kernel of syntax and the program is incrementally expanded outward while preserving semantic validity at every step.

Origin and Instantiation

The term bottom-up generation as a named technique is introduced in the paper "Bottom-Up Generation of Verilog Designs for Testing EDA Tools" (arXiv:2504.06295v1), which presents the open-source fuzzer ChiGen as its canonical realization.

In ChiGen, bottom-up generation is operationalized through three components:

  • Probabilistic grammars in which probabilities are assigned to sequences of production rules (modeled as k-grams), not to sequences of tokens. This governs how skeletons are sampled.
  • Type inference using the Hindley-Milner algorithm to assign names and types to the placeholder slots in the skeleton.
  • Code injection (referred to in the paper as "Li-Zhendong-style" injection) enabled by data-flow analysis, which fills in module bodies, expressions, and inter-statement dependencies.

Why a Bottom-Up Strategy?

The authors of the ChiGen paper argue that top-down Verilog fuzzers (e.g., Verismith, TransFuzz, VlogHammer) impose a requirement that every intermediate expansion remains semantically valid. This constraint limits the diversity of generated test cases and causes top-down fuzzers to cover fewer than 40% of the production rules of the Verilog-2005 (IEEE 1364-2005) grammar. Because the goal of fuzzing is to expose unexpected behaviors in tools under test — not to produce meaningful hardware — semantically invalid designs are just as useful as valid ones. Bottom-up generation deliberately relaxes the per-step validity requirement by separating skeleton creation from skeleton completion.

Applications

  • EDA tool fuzzing. ChiGen uses bottom-up generation to stress-test tools such as Verible, Verilator, and Yosys, and was originally developed to test Cadence's Jasper Formal Verification Platform. It has reportedly found zero-day bugs in these tools.
  • Benchmark synthesis. Because the process is generative rather than curated, bottom-up generation can augment existing static HDL benchmark collections (which are limited in size and increasingly needed for training large language models for Verilog) with newly generated samples on demand.
  • Other languages. The ChiGen authors hypothesize that the same combination — probabilistic grammars + Hindley-Milner inference + Li-Zhendong code injection — can automate code generation for any programming language, not just Verilog.

Comparison with Related Approaches

Approach Starting point Validity constraint Example tools
Top-down generation Minimal valid core Every expansion is semantically valid Verismith, TransFuzz, VlogHammer
Bottom-up generation Skeleton + completion Skeleton syntactically valid; output may be semantically invalid ChiGen
LLM-based generation Token sequence learned from corpora Validity is emergent, not enforced Various Verilog LLMs

Empirical Properties

  • Validity rate. With a lower bound of 500 tokens and a probabilistic context of length two or three, ChiGen produces roughly 30–40% semantically valid designs; with context length one the rate drops further because syntactic constraints are weakened.
  • Diversity and coverage. Bottom-up generation outperforms top-down Verilog fuzzers on structural diversity, code coverage, and bug-finding ability in the reported evaluation.
  • Modularity. Unlike Verismith (which, in the authors' paraphrase, "generates a set of Verilog modules one line at a time, making decisions locally"), bottom-up generation performs the entire generation as a single, more global, modular step.

See Also

References

  • J. V. A. Vieira et al., "Bottom-Up Generation of Verilog Designs for Testing EDA Tools," arXiv:2504.06295v1, April 2025.
  • IEEE Std 1364-2005, Verilog Hardware Description Language.

LINKED ENTITIES

1 links
ChiGen IMPLEMENTS

CITATIONS

7 sources
7 citations
[1] Bottom-up generation constructs a syntactically valid skeleton first and then completes it via type/name inference and code injection, rather than expanding from a minimal valid core. Bottom-Up Generation of Verilog Designs for Testing EDA Tools
[2] ChiGen is presented as a bottom-up fuzzer whose design rests on (i) probabilistic grammars, (ii) Hindley-Milner type inference, and (iii) data-flow-enabled code injection. Bottom-Up Generation of Verilog Designs for Testing EDA Tools
[3] Top-down Verilog fuzzers such as Verismith, TransFuzz, and VlogHammer start from a minimal valid core and only emit semantically valid designs, which limits diversity; such tools cover fewer than 40% of Verilog-2005 production rules. Bottom-Up Generation of Verilog Designs for Testing EDA Tools
[4] ChiGen uses a probabilistic grammar that assigns probabilities to sequences of production rules (k-grams), not to sequences of tokens. Bottom-Up Generation of Verilog Designs for Testing EDA Tools
[5] Verismith's authors describe their approach as local/line-at-a-time, contrasting with ChiGen's more global, modular, single-step generation. Bottom-Up Generation of Verilog Designs for Testing EDA Tools
[6] With a 500-token lower bound and probabilistic context of length two or three, ChiGen yields roughly 30–40% semantically valid designs; context length one yields fewer because syntactic constraints are weakened. Bottom-Up Generation of Verilog Designs for Testing EDA Tools
[7] The authors claim the same combination of probabilistic grammars, Hindley-Milner inference, and Li-Zhendong code injection could automate code generation for any programming language. Bottom-Up Generation of Verilog Designs for Testing EDA Tools