ReVEAL: GNN-Guided Reverse Engineering for Formal Verification of Optimized Multipliers
Chen Chen, Daniela Kaufmann, Chenhui Deng, Zhan Song, Hongce Zhang, Cunxi Yu · 2025
Read ReVEAL: GNN-Guided Reverse Engineering for Formal Verification of Optimized Multipliers by Chen Chen, Daniela Kaufmann, Chenhui Deng, Zhan Song, Hongce Zhang, Cunxi Yu (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2512-22260.txt.
Introduction
Chen Chen, Daniela Kaufmann, and four co-authors present ReVEAL, a method that helps prove hardware multipliers correct. Algebraic checking methods struggle with large, heavily optimized multiplier circuits because they cannot see the hidden design. ReVEAL reverse-engineers that design using graph learning, reading structural cues of the circuit graph to recognize design patterns at scale.
The system was demonstrated across diverse multiplier benchmarks, where it improved both scaling and accuracy compared with older rule-based approaches. It also integrates smoothly with current checking flows. By recovering the architecture, ReVEAL supports the downstream algebraic proof strategies that finish the checking job. The work targets a practical bottleneck in chip design, where optimized arithmetic blocks resist standard checking tools.
Catalog record
| CREATOR | Chen Chen, Daniela Kaufmann, Chenhui Deng, Zhan Song, Hongce Zhang, Cunxi Yu |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 50 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2512-22260
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
ReVEAL: GNN-Guided Reverse Engineering for Formal Verification of Optimized Multipliers Chen Chen, Daniela Kaufmann, Chenhui Deng, Zhan Song, Hongce Zhang, Cunxi Yu Abstract We present ReVEAL , a graph-learning-based method for reverse engineering of multiplier architectures to improve algebraic circuit verification techniques. Our framework leverages structural graph features and learning-driven inference to identify architecture patterns at scale, enabling robust handling of large optimized multipliers. We demonstrate applicability across diverse multiplier benchmarks and show improvements in scalability and accuracy compared to traditional rule-based approaches. The method integrates smoothly with existing verification flows and supports downstream algebraic proof strategies. 1 Introduction Gate-level arithmetic circuits, in particular integer multipliers that have been optimized via logic synthesis, continue to pose significant challenges for current formal verification techniques. Despite notable advancements in computer algebra-based (CA) techniques [ 8 , 14 , 21 , 17 ] , these methods often rely on syntactic heuristics and hence struggle with synthesized circuits due to optimizations that obscure their original word-level structure [ 32 , 34 , 21 , 7 , 17 ] . Our goal is to verify such optimized circuits by reverse-mapping them back to their original non-optimized word-level representations that can be efficiently verified using algebraic reasoning. We ensure the correctness of this mapping through Boolean satisfiability (SAT)-based equivalence checking. Traditional computer algebra techniques reduce the task of circuit verification to an ideal membership test for the specification polynomial, typically utilizing Gröbner bases [ 5 ] to simplify the polynomials through backward rewriting. In [ 13 , 14 ] , an incremental column-wise verification approach together with adder substitution is used in the tool AMulet2 to handle unoptimized multipliers. However, the verification of optimized multipliers still presents significant challenges due to blow-ups in the intermediate rewriting steps. In RevSCA2 [ 21 ] this is addressed by algebraic reverse engineering to recover word-level components such as full adders and half adders. Most recently, DynPhaseOrderOpt [ 17 ] optimizes the encoding of the phases of occurring signals to enhance backward rewriting and keep the sizes of intermediate polynomials small. However, despite these advances, logic synthesis often applies aggressive optimizations that obscure the original circuit structure. As a result, many original atomic blocks cannot be restored through cut enumeration, which limits the effect of the aforementioned rewriting methods. Figure 1 : Overview of ReVEAL versus Conventional Tools Moreover, the inevitable occurrence of numerous OR chains and XOR gates in multiplier circuits further complicates polynomial rewriting, resulting in ongoing issues with monomial blow-ups. Recent work by Li et al. [ 19 ] reconstructs an adder tree from optimized multipliers to build a structurally similar reference design, and then verifies it via CA and SAT-based equivalence checking. However, such reconstruction-based reverse engineering fundamentally depends on explicit structural pattern matching, which is fragile under aggressive synthesis and technology mapping. As a result, boundary recovery can become expensive or fail entirely, and the approach is often architecture-specific (e.g., tailored to adder trees), making it difficult to handle diverse designs such as 4-2/compressor and counter-based Wallace trees, XOR-heavy addition structures, or Booth-encoded multipliers where PPG/PPA boundaries are blurred. Due to the above limitations of reconstruction-based methods [ 19 ] , ReVEAL instead formulates the task as a learning-based inference problem. Traditional reverse engineering largely depends on recovering explicit boundaries and subgraph patterns, which can be broken or smeared by aggressive synthesis. In contrast, GNNs can aggregate information over neighborhoods via message passing and encode both local motifs and broader connectivity trends, allowing ReVEAL to capture more optimization-invariant cues from the netlist graph and thus remain effective even when canonical structures are not directly recoverable. Our Contributions. In this work, we propose a novel domain-specific GNN-based reverse engineering approach for architectural identification and demonstrate its significant impact in orthogonally accelerating computer algebra-based formal verification techniques by addressing the aforementioned challenges. The contributions of this paper are as follows: • To the best of our knowledge, ReVEAL is the first framework to integrate machine learning (ML) techniques into an end-to-end formal verification pipeline for multiplier circuits, demonstrating significant improvements in both runtime and scalability. • We present a novel approach that combines cone extraction with word-level functional and structural features in GNNs. This method enables the model to focus on small graphs within the critical cone, avoiding the performance degradation and long training times typically associated with large graphs. • We compare ReVEAL with advanced (SAT+)CA-based verification tools. The results show that ReVEAL achieves a 4.90 \times speedup and a 19.97 \times reduction in memory usage compared to state-of-the-art CA tools. Additionally, ReVEAL outperforms SAT+CA methods with a 13.39 \times speedup. 2 Preliminaries In this section we provide background information on different multiplier architectures (Section 2.1 ), a short introduction to GNNs (Section 2.2 ), as well as a very brief discussion of SAT solvers and SAT sweeping (Section 2.3 ). 2.1 Multiplier Architectures Multipliers typically involve three stages: (1) Partial Product Generator (PPG) , (2) Partial Product Accumulator (PPA) , and (3) Final Stage Adder (FSA) . The PPG can employ either a simple approach that pairs corresponding bits of the multiplicands to generate each partial product using logical conjunction or a Booth encoding scheme to process multiple bits at a time. The PPA then sums these partial products using structures like Wallace trees, Dadda trees, or 4-to-2 compressor trees, which reduce gate delays and minimize sequential additions compared to traditional array accumulators. Finally, the FSA combines the last two rows of partial products using adders, which can be broadly categorized into non-tree-based and tree-based adders (e.g., Brent–Kung, Kogge–Stone, Sklansky, Han–Carlson), with tree adders typically showing more regular, highly connected prefix structures. We list the most common multiplier architectures in Table 1 . Table 1 : Categorization of Multiplier Architectures Stage Types 1 PPG \bullet Booth Encoding \bullet Simple 2 PPA \bullet Simple Array \bullet Wallace Tree \bullet Dadda Tree \bullet 4-to-2 Compressor Tree \bullet Counter-based Wallace Tree 3 FSA \bullet Ripple Carry Adder \bullet Carry Look-Ahead Adder \bullet Carry Skip Adder \bullet Serial Prefix Adder \bullet Brent-Kung Adder \bullet Sklansky Adder \bullet Han-Carlson Adder \bullet Ladner-Fischer Adder \bullet Kogge-Stone Adder Note: Tree adders are marked using blue cell colors. 2.2 Graph Neural Networks We refer readers to [ 10 ] for a comprehensive introduction to graph representation learning and GNNs. A GNN encodes a graph G=(V,E) into a more compact representation. Starting with initial node features \{\mathbf{x}^{(0)}_{i}\mid i\in V\} , GNNs iteratively update hidden state vectors \mathbf{x}^{(l)}_{i} using: \displaystyle\mathbf{m}^{(l)}_{i} \displaystyle=\text{AGGREGATE}^{(l)}\left(\{\mathbf{x}^{(l-1)}_{j}\mid j\in\mathcal{N}(i)\}\right), (1) \displaystyle\mathbf{x}^{(l)}_{i} \displaystyle=\text{COMBINE}^{(l)}\left(\mathbf{m}^{(l)}_{i},\mathbf{x}^{(l-1)}_{i}\right), (2) where \mathcal{N}(i) are the one-hop neighbors of node i . The AGGREGATE function (e.g., mean or max pooling) pools neighbor features, and the COMBINE function integrates this with the node’s current feature. After L layers, the set of vectors \{\mathbf{x}^{(L)}_{i}\mid i\in V\} capture the structural and feature information of the graph. A readout function then aggregates these into a graph embedding for classification, enabling GNNs to effectively model complex dependencies in circuit designs for various EDA applications. Building on this capability, recent research has explored the use of GNNs for reverse engineering tasks. HOGA [ 9 ] and GAmora [ 31 ] leverage gate-level Boolean reasoning to identify adders at the register transfer level (RTL), while the DeepGate family