Source-linked AI summary
Dictionary-Guided Mutation Operators for Automated HDL Repair
Maisha Mastora, Dean Sullivan
TL;DR
HDL repair must search a large space while respecting strict grammar and semantic constraints that make generic mutations inefficient. The paper combines DUT-specific dictionary-guided mutations with lightweight simulation-divergence fault localization and targeted search, repairing 14 variants across six DUT families, including a six-edit case CirFix cannot repair, and reporting an 18× speedup on a shared two-edit benchmark.
Problem
Unconstrained HDL mutations often produce syntactically invalid candidates, while synthesis- and template-driven methods constrain generality or portability.
Method
The system derives DUT-specific token vocabularies with ANTLR, localizes faults from simulation divergence, and performs category-constrained targeted mutations before GP fallback.
Results
The system repairs 14 of 23 in-scope bug variants across five DUT families, including a six-edit variant CirFix cannot repair, and achieves up to an 18× speedup on shared benchmarks.
Takeaways & Limitations
Dictionary-constrained mutation guided by lightweight simulation-divergence FL is a practical and competitive HDL-repair strategy for common bug classes without formal analysis or synthesis.
Takeaways & Limitations
Greedy sequential repair fails when correctness requires coordinated simultaneous edits, motivating coordinated multi-token patch generation.
Abstract
from arXiv · showhide
Automated repair of Hardware Description Language (HDL) designs remains challenging due to the large search space of candidate repairs and the strict syntactic and semantic constraints imposed by HDL grammars. Generic mutation strategies overwhelmingly generate syntactically invalid candidates that waste compilation and simulation budget, while synthesis-driven and template-based approaches impose their own constraints on generality and portability. In this paper, we propose a dictionary-guided HDL repair system that combines ANTLR-derived DUT-specific mutation vocabularies with a simulation-divergence fault localization (FL) module. The mutation operator applies category-constrained token substitutions, insertions, and deletions directly to Verilog source via regex-based matching, without requiring AST manipulation or synthesis. The FL module identifies diverging output wires from a single simulation run and scores source lines by structural proximity to those signals, directing the mutation search toward high-suspicion regions. A deterministic targeted sweep exhausts all dictionary mutations on the highest-scored lines before falling back to a genetic programming (GP) search. Evaluated on the CirFix benchmark suite across six design under test (DUT) families, the proposed approach produces correct oracle-passing repairs on 14 bug variants, including a 6-edit multi-bug instance that CirFix cannot repair, and achieves an 18x speedup over CirFix on a two-edit benchmark variant. These results indicate that dictionary-constrained mutation operators, combined with lightweight simulation-divergence FL, are a practical and competitive approach to automated HDL repair for common bug classes without formal analysis or synthesis dependencies.
I. INTRODUCTION
HDL repair is difficult because unconstrained mutations frequently violate rich HDL grammars and waste evaluation resources. The paper addresses this with DUT-specific dictionary-guided mutation, simulation-divergence localization, and targeted search.
- Unconstrained token edits generate many syntactically invalid HDL candidates, consuming compilation and simulation budget.
- HDL grammars expose token classes and contextual constraints that support design-specific mutation vocabularies.
- The system combines ANTLR-derived structural and numeric vocabularies, simulation-divergence fault localization, category-constrained mutations, and targeted deterministic search.
- 14 bug variants were repaired across six DUT families, including variants CirFix cannot fix, with lower evaluation counts on several benchmarks.
- The approach derives mutation vocabularies automatically from each design, avoiding manual repair templates across common bug classes.
II. BACKGROUND AND RELATED WORK
HDL repair evaluates candidate designs through simulation or trace-based oracles because hardware behavior is concurrent, stateful, and timing-dependent. Existing approaches span AST-level genetic programming, bounded synthesis, symbolic regression, and signal-transition guidance, each with different scope constraints.
- HDL correctness is commonly evaluated against reference input-output traces using explicit testbench or golden-trace oracles.
- CirFix searches AST-level mutations with weighted oracle fitness but incurs high evaluation cost and relies on unconstrained token vocabularies or design-specific templates.
- RTL-Repair uses bounded synthesis, while SRepair and STRIDER use symbolic regression or signal-transition patterns for more specialized repair settings.
B. Fault Localization for Hardware
HDL fault localization can rank suspicious statements using learning or simulation signals. This paper uses divergence at output wires and regex-based structural tracing to guide repair without ASTs or learning.
- Learning-based HDL fault localization ranks suspicious statements from execution coverage and contextual token representations but leaves patch synthesis separate.
- The proposed FL identifies the first divergent output timestep and traces backward through source lines using regex-based structural relationships.
- The FL procedure requires no AST, no learning, and only one simulation of the buggy design.
- The approach is positioned within token-level fuzzing research, where language-structure-aware mutations improve valid, coverage-increasing exploration.
III. SYSTEM DESIGN
The system constructs a DUT-specific mutation vocabulary once from the buggy Verilog source, then uses it to guide repair mutations. ANTLR grammar traversal supplies context-aware tokens, while specialized numeric handling preserves widths and representations.
- A. Dictionary Construction: Dictionary construction runs once per DUT before repair, using ANTLR to parse the design and analyze its grammar ATN.
- A. Dictionary Construction: ANTLR grammar traversal enumerates literal tokens reachable from each source token’s rule context, producing structurally valid replacements.
- A. Dictionary Construction: Numeric dictionaries use bit-flip, zero, one, rotation, and adjacent-value neighborhoods without cross-width or cross-base substitutions.
- A. Dictionary Construction: Merged dictionaries provide union and intersection vocabularies across variants, with the union selected by default for coverage.
- B. Repair Pipeline: The repair pipeline performs one simulation-based FL pass, exhaustively sweeps top-scored lines, and sends the best partial candidate to GP if needed.
B. Simulation-Divergence Fault Localization
The system localizes likely fault lines from a single simulation divergence, then uses those scores to guide category-constrained source-level mutations. Regex-based analysis handles hardware-specific cases without AST parsing.
- A single buggy simulation identifies the first diverging timestep and affected output wires, which anchor backward source tracing.
- Regex-only analysis scores source lines from 0.1 to 1.0 according to their structural relationship to diverging signals.
- The localization distinguishes combinational and sequential logic and specifically detects missing edge qualifiers in sensitivity lists.
- Substitution replaces tokens with same-category dictionary entries, while identifiers remain restricted to names already present in the source.
- Insertion targets edge keywords, else, and unary logical operators, with sensitivity-list anchors restricted to edge keywords.
- Deletion excludes identifiers, operators, delimiters, module keywords, and net-type declarations to avoid syntactically broken or semantically undefined source.
D. Repair Pipeline
The repair procedure first exhausts targeted dictionary mutations on high-suspicion lines and then falls back to genetic programming when deterministic improvement is insufficient. Fitness is oracle-based compilation, simulation, and bitwise trace comparison.
- The procedure begins with fault localization, repeatedly applies targeted sweeps, and returns immediately when a candidate reaches fitness 1.0.
- The targeted sweep exhausts dictionary substitutions on top-scoring lines, inserts edge keywords near identifiers, and deletes eligible conditional tokens from lines scoring ≥0.7.
- Improved partial candidates trigger renewed fault localization, while previously swept lines are excluded and the process repeats for up to P passes.
- The GP fallback seeds 200 candidates with FL-biased single mutations, uses tournament selection and 0.7 mutation rate, and preserves the top 10% by elitism.
- The fallback runs for 10 generations across 5 independent restarts and terminates when any individual reaches fitness 1.0.
- Fitness compiles and simulates each candidate, compares output traces bitwise, weights x/z matches by ±2, and assigns zero to compilation failures.
A. Setup
The evaluation uses CirFix’s buggy Verilog designs, testbenches, and oracle traces across six DUT families, with fitness evaluations as the primary efficiency measure. Comparisons rerun both systems under identical local simulator conditions.
- The benchmark covers six DUT families: first_counter_overflow, fsm_full, lshift_reg, mux_4_1, decoder_3_to_8, and flip_flop.
- Designs whose original buggy source already achieves fitness 1.0 are excluded because their testbenches do not expose the injected bugs.
- The proposed system uses popsize=200, gens=10, restarts=5, mutation_rate=0.7, and dict_type=union.
- Both systems are rerun on the same machine and simulator, using iverilog because the commercial VCS simulator used in CirFix’s paper is unavailable.
- Fitness evaluation count is the primary efficiency metric because one evaluation is a complete compile-simulate-score cycle independent of machine and simulator.
- Under iverilog, vanilla CirFix with popsize=5000 did not finish within a practical time limit on non-template bugs, whereas the proposed system used popsize=200.
B. Results
Across the evaluated benchmark, the system repairs 14 in-scope variants and handles multi-edit and non-template cases that CirFix does not repair. Its reported efficiency advantage includes an 18× local speedup on one benchmark, with simulator differences noted as a caveat.
- Six additional variants are out of scope because they require changes outside the current mutation vocabulary, including commented-out code and port declaration changes.
- 14 of 23 in-scope variants are repaired, producing a 61% repair rate across five DUT families.
- The six-bug decoder_3_to_8 super-buggy variant is repaired in four targeted-sweep passes and 5374 evaluations, whereas CirFix does not repair it.
- The three-edit first_counter buggy counter variant is repaired through iterative targeted sweeping in 98 evaluations.
- The decoder_3_to_8 wadden buggy1 variant takes 776s locally versus CirFix’s reported 13,984s, an 18× speedup.
- Five additional variants are repaired by the proposed system but not CirFix, covering identifier substitution, plain integer, and unary operator bug classes.
V. DISCUSSION AND LIMITATIONS
The system’s evaluation is bounded by simulator comparability, weak oracle coverage, and mutation classes that require coordinated or currently unsupported edits. These limitations motivate multi-token operators, minimization, broader dictionaries, and weaker oracle dependence.
- Evaluation caveats: Wall-clock comparisons are not directly comparable when CirFix uses paper-reported VCS times and this evaluation uses iverilog.Local comparisons use iverilog on the same machine; VCS-based times are marked separately.
- Oracle limitations: Weak fsm_full oracle coverage permits oracle-passing patches that differ from the intended semantic fix.The testbench covers only 39 input combinations, while semantically correct fixes also pass the oracle.
- Multi-edit repair: Greedy sequential repair fails when correctness requires simultaneous multi-edit changes across related lines.The flip_flop swap and mux_4_1 case-label repair temporarily reduce fitness after isolated edits.
- Multi-edit repair: The lshift_reg blocking-to-non-blocking variant reaches fitness 0.8276 but requires four independent assignments to change together.The targeted sweep converts one assignment, whereas GP does not accumulate all four fixes.
- Patch quality: The current system can produce functionally correct but non-minimal patches because it lacks post-repair minimization.A spurious i<8→i<10 substitution survives the oracle after the correct negedge→posedge edit.
- Scope boundary: Several benchmark variants remain out of scope, including commented-code reinsertion, port-width changes, unsupported numeric-base conversions, and compile-time syntax errors.Extending dictionary construction is identified as a path toward broader coverage.
VI. CONCLUSION AND FUTURE WORK
The paper concludes that dictionary-guided mutation combined with simulation-divergence fault localization provides a portable HDL repair approach. Across the CirFix suite, it repairs 14 variants and reaches up to an 18× speedup, while future work targets coordinated edits, minimization, broader numeric coverage, and weaker oracle dependence.
- Conclusion: The system combines DUT-specific ANTLR-derived dictionaries with simulation-divergence fault localization and operates without AST manipulation, synthesis, or formal analysis.A single buggy-design simulation scores lines near diverging output wires for targeted and GP search.
- Results: 14 bug variants receive oracle-passing repairs across six CirFix DUT families.Table I reports the benchmark repair outcomes and associated scope annotations.
- Results: Up to 18× speedup is achieved on shared benchmarks, including multi-edit instances CirFix cannot repair.The reported result includes 3-edit and 6-edit multi-bug cases.
- Future work: Future work targets coordinated multi-token patches, delta-debugging minimization, expanded numeric dictionaries, and partial or property-based specifications.These directions address simultaneous edits, spurious edits, numeric coverage, and dependence on complete oracle traces.