BF-DT: Achieving 100% Coverage in Automatic Hardware Assertion Generation

TL;DR

Automatic assertion generation is a holy grail in hardware verification to reduce the manual labor of writing SVA/PSL code. This paper presents BF-DT (Breadth-First Decision Tree), a mining technique that extracts complete design properties from simulation traces. By switching from depth-first variable partitioning to a breadth-first preposition-based approach with aggressive pruning, it ensures 100% coverage while maintaining high inference speed.

The Bottleneck: Why Manual Verification is Dying

As SoC (System-on-Chip) complexity grows, functional verification now consumes nearly 75% of the design cycle. While Assertion-Based Verification (ABV) is industry-standard, writing these assertions is still an entirely manual, error-prone effort.

Previous tools like GoldMine used Binary Decision Trees (BDT) to mine rules. However, BDTs have a fundamental flaw: they partition data variable-by-variable. This creates a search space mismatch. For $n$ features, the actual search space for all possible assertions is $3^n-1$, but BDTs only explore a subset ($2^{n+1}-2$), often missing the most "succinct" or "meaningful" properties.

Methodology: The Breadth-First Advantage

The core innovation is the Breadth-First Decision Tree (BF-DT). Instead of drilling down one path to find an assertion, the algorithm explores all single-antecedent possibilities, then all double-antecedents, and so on.

1. Preposition-wise Partitioning

Unlike standard trees that split on a variable (e.g., a), BF-DT splits on a specific state (e.g., a=0 OR a=1). This allows the algorithm to prioritize "good" paths that lead to an assertion faster.

2. Path Pruning (The "Included" Logic)

This is the "Secret Sauce." If the algorithm finds a high-level assertion like if b=0 then X=0, it identifies this as a Primary Assertion. Any future search path containing b=0 as a subset (e.g., if a=1 and b=0 then X=0) is immediately pruned. This ensures that the generated assertions are the most compact versions possible.

Fig 1: Comparison of standard Binary Decision Trees (which generate redundant paths) vs the proposed specific partitioning.

3. Bit-wise Optimization

To keep the search fast, the authors represent each variable's state using a 2-bit logic register (P_reg). This transforms complex set-inclusion checks into simple bit-wise AND and NOT operations, significantly boosting processing speed for millions of traces.

Experiments & Results

The authors tested BF-DT against standard logic functions (AND, XOR, Multiplexers). The results confirmed that BF-DT moves beyond "candidate assertions" to extract true design properties.

• Extraction Quality: For a 3-input function like $X=AB+BC$, the algorithm successfully extracted four primary assertions that perfectly define the logic, ignoring hundreds of redundant combinations.
• Scalability: For 33.5 million traces, the search time remains linear on a logarithmic scale, completing the task in approximately 1.5 hours.

Fig 2: Linearized search time vs number of traces, demonstrating feasible scalability for industrial-sized datasets.

Critical Analysis & Conclusion

The BF-DT approach is a significant step toward "Set-and-Forget" verification. By focusing on the abstraction level of the assertions (succinctness), it produces output that actually looks like it was written by a human expert.

Takeaway for Engineers:

• Success: 100% coverage and minimal redundancy.
• Limitation: Currently focused on combinational logic; while the paper mentions temporal signals (clocks), the complexity of sequential state machines may require more advanced heuristic pruning in future iterations.
• Future Work: Integration with Formal Verification tools (to verify the mined assertions against the RTL) and parallel computing to bring that 87-minute runtime down to seconds.

In short, BF-DT proves that in the world of data mining for hardware, breadth often beats depth when looking for the most fundamental truths of a design.