Bottom-Up Generation

Concept

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.

First seen 8/4/2026

Last seen 8/4/2026

Evidence 4 chunks

Wiki v1

WIKI

Definition

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

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

READ FULL ARTICLE →

NEIGHBORHOOD

No graph connections found for this entity yet. It may appear in future ingestion runs.

explore full graph →

RELATIONSHIPS

1 connections

ChiGen ← implements 100% 2e

ChiGen is described as a 'bottom-up' fuzzer that generates Verilog designs using bottom-up generation methodology.

LINKED ENTITIES

1 links

ChiGen IMPLEMENTS Extracted graph relationship

CITATIONS

7 sources

7 citations — click to expand

[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