Btor2MLIR: A Format and Toolchain for Hardware Verification

Imagine you are a detective trying to solve a mystery, but the clues are written in a secret code that only a few specialists can read. In the world of computer science, this "secret code" is the language used to describe how computer chips (hardware) are supposed to behave. Engineers build these chips to run everything from your phone to the satellites in space, but if there is even a tiny mistake in the design, the whole system can crash or act strangely. To prevent this, researchers use "formal methods"—mathematical tools that act like super-powered spell-checkers to prove a design is perfect before it is ever built.

For a long time, these spell-checkers spoke different languages. Some spoke "BTOR2," a format popular in hardware competitions, while others spoke "LLVM-IR," a language used by software compilers to check code. It was like having a translator who only knew how to translate from French to English, and another who only knew Spanish to English. If you wanted to use a French translator to check a Spanish book, you were out of luck. You had to build a whole new translator from scratch every time. This paper introduces a new, magical translator called BTOR2MLIR. It sits in the middle, acting as a universal bridge that lets hardware designs speak to software tools without needing to reinvent the wheel every time.

The Problem: Too Many Dialects, Not Enough Bridges

In the world of hardware verification, the BTOR2 format has become the standard way to describe circuits for competitions like the Hardware Model Checking Competition (HWMCC). Think of BTOR2 as a very specific, efficient dialect for describing how a digital circuit counts, adds numbers, or checks for errors. Tools like BTORMC are built specifically to read this dialect and check if the circuit is safe.

However, the world of software verification is huge and powerful. Tools like SEAHORN are experts at checking software code written in the LLVM-IR language. These tools are incredibly mature, having been refined over decades by massive projects like the LLVM compiler infrastructure. They have built-in features for optimizing code, finding bugs, and running simulations.

The problem is that these two worlds rarely talk to each other. To use a powerful software tool to check a hardware design, researchers had to write custom, one-off translators. It was like trying to fit a square peg in a round hole every single time. These translators often had to re-implement basic features (like how to handle numbers or loops) that already existed in the software tools, leading to wasted effort and potential errors.

The Solution: The Universal Adapter (BTOR2MLIR)

The authors of this paper, Joseph Tafese, Isabel Garcia-Contreras, and Arie Gurfinkel from the University of Waterloo, decided to build a better bridge. They created BTOR2MLIR, a new format and toolchain based on MLIR (Multi-Level Intermediate Representation).

To understand MLIR, imagine a giant, modular Lego set. Instead of building a whole new castle from scratch every time you want to build a different type of house, MLIR gives you a base set of bricks (dialects) that you can snap together. You can define a new "hardware" brick that looks and acts exactly like BTOR2, but it snaps directly into the existing "software" Lego structure.

Here is how their new tool works:

1. The Translator: They built a "BTOR Dialect" inside MLIR. This is a direct, lossless translation of the BTOR2 format. If you have a BTOR2 file, BTOR2MLIR can turn it into this MLIR dialect instantly.
2. The Bridge: Because MLIR is designed to be extensible, they created a "conversion pass" that turns their BTOR Dialect into the standard LLVM Dialect. This is the magic step. It takes the hardware description and turns it into a format that software tools like SEAHORN can understand natively.
3. The Result: The output is LLVM-IR, a language that software verification engines can eat up and analyze.

The Experiment: Does It Actually Work?

The team didn't just build the bridge; they drove a truck across it to see if it held. They took a collection of real-world hardware benchmarks from the HWMCC competition (specifically the 2020 and 2019 sets) and ran them through their new toolchain.

First, they checked for correctness. They took a BTOR2 file, converted it to their MLIR format, and then converted it back to BTOR2. They compared the original and the round-tripped file. The result? They were identical. The safety properties (the rules the circuit must follow) were preserved perfectly. Even in tricky cases where the original tools timed out or ran out of memory, their round-tripped versions sometimes solved the problem, suggesting the translation didn't introduce any errors.

Next, they tested performance. They connected their tool to SEAHORN, a famous software model checker, and BOOLECTOR, a fast solver. They compared this new "hybrid" pipeline against BTORMC, the gold-standard tool that was built specifically for BTOR2.

The results were surprising and encouraging:

• Speed: In many cases, the hybrid pipeline (BTOR2MLIR + SEAHORN + BOOLECTOR) was competitive with, and sometimes faster than, the dedicated BTORMC tool. For example, in the "19/mann" category of benchmarks, the hybrid approach solved 44 instances in about 3,190 seconds, whereas BTORMC took longer or timed out on more instances.
• Flexibility: The tool successfully handled complex operations like division and bit-vectors, proving that the "Lego bricks" of MLIR could handle the heavy lifting of hardware logic.
• Limitations: The authors were honest about what their tool couldn't do yet. It currently supports bitvectors and arrays but does not yet handle "fairness" and "justice" constraints (rules about how a system behaves over infinite time). Also, while it works well, it didn't completely crush the dedicated hardware tools in every single category; it was a strong contender, not a total replacement.

Why This Matters

The paper doesn't claim to have solved all of hardware verification. Instead, it suggests a new way of thinking. By using the mature, robust infrastructure of the LLVM compiler (which powers tools for everything from video games to web browsers), hardware researchers can stop reinventing the wheel.

The authors show that you can take a hardware design, translate it into a universal language, and then use powerful, existing software tools to check it. This opens the door for rapid prototyping. If a researcher wants to try a new verification technique, they don't need to build a whole new engine; they just need to plug their idea into the MLIR framework.

In the future, the team plans to connect this bridge to even more tools, like KLEE (a symbolic execution engine) and LIBFUZZER (a fuzzing tool), which are currently used for software but could revolutionize how we find bugs in hardware. They also plan to generate other formats like AIGER and SMT-LIB.

Ultimately, BTOR2MLIR is a proof of concept that the walls between hardware and software verification are coming down. It suggests that by speaking a common language, we can make our digital world safer, faster, and easier to build.