Abstract
This paper presents Robust Positive Equality (RPE), an advancement in formal verification techniques for the logic of Equality with Uninterpreted Functions (EUF). By transitioning from symbol-level to application-level analysis of positive contexts, RPE overcomes the fragility of traditional Positive Equality (PE) methods. We demonstrate that RPE significantly prunes the search space for solvers, leading to order-of-magnitude speedups on complex software verification benchmarks where traditional methods often fail.
Introduction
In the field of formal verification, determining the validity of logic formulas is essential for ensuring the correctness of hardware and software systems. A primary logic used for this purpose is Equality with Uninterpreted Functions (EUF). To check the validity of an EUF formula, solvers explore various interpretations—assignments of values to variables and functions—to determine if any assignment can make the formula false.
A significant breakthrough in this area was the introduction of Positive Equality (PE). PE observed that if a function symbol appears only in "positive" contexts (e.g., in equalities like $f(x) = y$, but never in inequalities like $f(x) \neq y$), the solver can ignore a vast number of redundant interpretations. However, PE suffers from a major "all-or-nothing" flaw: if a function symbol appears in a negative context even once, the entire symbol loses its positive status. This makes the technique fragile and often ineffective for real-world benchmarks where functions are frequently used in mixed contexts.
Robust Positive Equality (RPE)
The authors propose Robust Positive Equality (RPE) to address the limitations of PE. The core insight is that positivity is a property of a term's specific location within a formula's syntax tree, rather than an inherent property of the function symbol itself.
Technical Contributions
- Granular Labeling: Instead of partitioning function symbols, RPE partitions individual function applications into "p-terms" (positive) and "g-terms" (general). A term is classified as a p-term if it never appears in a negative equation or as a control for an
if-then-else(ITE) block. - Robust Maximal Diversity Theorem: The authors prove a new theorem showing that to check validity, one only needs to consider "robustly maximally diverse" interpretations. This set of interpretations is a strict subset of those required by the older PE method, mathematically guaranteeing that RPE is a stronger reduction technique.
- Topological Ordering and Complexity: The effectiveness of RPE depends on the order in which terms are processed. The authors demonstrate that finding the optimal ordering to maximize the number of positive terms is NP-complete, via a reduction from the Maximum Independent Set problem.
- Greedy Heuristic: To manage the NP-completeness, a greedy algorithm is employed to order function symbols based on their potential for positive applications, ensuring the solver remains efficient in practice.
Evaluation and Results
The RPE approach was evaluated using two primary sets of software verification benchmarks: Translation Validation of Compilers (the cv series) and BLAST device-driver verification (the bl series). These benchmarks represent complex, real-world formulas containing hundreds of variables.
Key Findings
- State-Space Reduction: In illustrative examples, RPE reduced the number of required interpretations from 3,125 (under PE) to just 4—a 781-fold reduction.
- Performance Gains: On the
cv46benchmark, where the original PE method timed out after 1,800 seconds, RPE successfully solved the formula in 100.5 seconds. Similarly, in thecv22benchmark, RPE increased the number of identified positive variables from 1 to 16, reducing solve time by approximately 35%. - Solver Efficiency: While the RPE analysis introduces a small overhead (typically <10%), it consistently produces smaller Boolean formulas that underlying SAT solvers, such as mChaff, can process significantly faster.
Conclusion and Future Work
Robust Positive Equality provides a more resilient and powerful framework for EUF logic reduction by focusing on individual term applications. While the optimization of term ordering is computationally difficult, the use of greedy heuristics allows RPE to deliver substantial performance improvements in practice.
Future research directions include refining the handling of "general terms" that share symbols with other terms and integrating RPE with advanced range allocation methods to further optimize the encoding of integer variables into Boolean logic.
Summary updated