Fast Three-Valued Abstract Bit-Vector Arithmetic

0556720 - ÚI 2023 RIV CH eng C - Konferenční příspěvek (zahraniční konf.)
Onderka, J. - Ratschan, Stefan
Fast Three-Valued Abstract Bit-Vector Arithmetic.
Verification, Model Checking, and Abstract Interpretation. Cham: Springer, 2022 - (Finkbeiner, B.; Wies, T.), s. 242-262. Lecture Notes on Computer Science, 13182. ISBN 978-3-030-94582-4. ISSN 0302-9743.
[VMCAI 2022: International Conference on Verification, Model Checking, and Abstract Interpretation /23./. Philadelphia (US), 16.01.2022-18.01.2022]
Institucionální podpora: RVO:67985807
Klíčová slova: Formal verification * Three-valued abstraction * Computer arithmetics * Addition and multiplication * Pseudo-Boolean modular inequality
Obor OECD: Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
http://dx.doi.org/10.1007/978-3-030-94583-1_12

Abstraction is one of the most important approaches for reducing the number of states in formal verification. An important abstraction technique is the usage of three-valued logic, extensible to bit-vectors. The best abstract bit-vector results for movement and logical operations can be computed quickly. However, for widely-used arithmetic operations, efficient algorithms for computation of the best possible output have not been known up to now. In this paper, we present new efficient polynomial-time algorithms for abstract addition and multiplication with three-valued bit-vector inputs. These algorithms produce the best possible three-valued bit-vector output and remain fast even with 32-bit inputs. To obtain the algorithms, we devise a novel modular extreme-finding technique via reformulation of the problem using pseudo-Boolean modular inequalities. Using the introduced technique, we construct an algorithm for abstract addition that computes its result in linear time, as well as a worst-case quadratic-time algorithm for abstract multiplication. Finally, we experimentally evaluate the performance of the algorithms, confirming their practical efficiency.
Trvalý link: http://hdl.handle.net/11104/0330868