8.2.4. Bounded Model Checking (BMC)

Bounded Model Checking (BMC) is a formal verification technique that searches for violations of properties within a bounded time frame. It is particularly useful for detecting corner cases in the design.

Bounded Model Checking (BMC) is a specific method used in formal verification, which focuses on checking if certain properties of a system hold true within a specified time limit. This means that instead of examining all possible behaviors and states of a design, BMC looks only at those that occur within a set number of time intervals (or 'time frames'). The main advantage of BMC is its efficiency in finding issues or 'bugs' that may arise from unique or extreme conditions, known as corner cases.

Think of BMC like testing a car under certain conditions. Instead of driving the car across every possible terrain, you decide to drive it only on smooth roads for specific distances (like 5 kilometers). You want to see if it performs well under these limited but realistic conditions, just like BMC checks only a certain number of clock cycles.

BMC is used to find design bugs within a limited scope of time, often during early stages of design or for designs with known temporal properties. It can be applied to verify properties such as "A should always be true within N cycles."

The application of Bounded Model Checking is critical during the early stages of design or when working with systems that operate under specific timing conditions. It can verify whether certain conditions (like a signal being true) are maintained for a given number of cycles. This approach allows designers to catch potential bugs early, hence saving time and resources in later stages of the design process.

Imagine you are baking a cake and want to ensure that it rises properly within 30 minutes in the oven. You check the cake every so often within that time frame (like setting timers at 10, 20, and 30 minutes) to see if it has risen. This is similar to how BMC checks if specific conditions within the design hold true during defined cycles.

BMC explores a limited number of clock cycles and checks if the specified properties hold within this time window. If a property violation is found within the bounds, the tool generates a counterexample (sequence of events that led to the violation).

In BMC, the process begins with defining a set number of clock cycles to examine. The verification tool then checks if the specified properties are valid within these cycles. If an issue is found—meaning a property that is supposed to hold true does not—the tool generates a counterexample. This counterexample is crucial as it provides a specific sequence of events that demonstrates the failure, helping designers quickly identify and fix the problem.

Think of BMC as a security camera focused on a specific area of a house. If the camera captures an intruder (a property violation) during the time it was set to monitor, it can then show the sequence of events (the footage) that led to identifying the intruder. This provides clear evidence and helps homeowners understand how to enhance their security measures.

Tools: Cadence JasperGold and Mentor Graphics Questa Formal provide BMC capabilities.

To perform Bounded Model Checking, specialized tools are used that can automate the verification process. Cadence JasperGold and Mentor Graphics Questa Formal are examples of such tools. They are designed to efficiently conduct BMC, allowing designers to explore the state space of the design while focusing on specific time frames and properties.

Using a tool for BMC is like using a specialized app on your smartphone that tracks your workouts. Just as the app helps you focus on your fitness goals (like specific exercises over a set timeframe), BMC tools help engineers focus on verifying part of their designs within specific parameters.

BMC can be used to verify that a finite state machine (FSM) never enters a state where the output is invalid, within a specific number of clock cycles.

An example application of Bounded Model Checking is in the context of a finite state machine (FSM). BMC can check that the FSM does not reach any invalid states within a defined number of cycles, ensuring that the machine operates correctly under expected conditions. This specific verification can help catch errors early in the design process, which could lead to significant issues if left unaddressed.

Consider a traffic light controller as an FSM. BMC ensures that the traffic light cannot simultaneously display both red and green (an invalid state) in the first ten cycles after it is powered on. This is similar to how traffic regulations work; they are designed to prevent dangerous situations to keep drivers and pedestrians safe.

--