EUVIMEDEUVIMED entdecken
Crossref

LOW-LEVEL CODE SEMANTIC EQUIVALENCE CHECKER

P.A. Putro

Программирование / Programming and Computer Software · 2025 · (6) · 53

DOI: 10.7868/s3034584725060047 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Программирование / Programming and Computer Software, 2025. Verfasst von P.A. Putro.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

The main difficulty in the function equivalence checking procedure is the presence of loops in the functions being checked. If there are no loops, it is possible to simply construct SMT formulas for these functions, link their inputs and outputs according to ABI, and pass them to SMT-solver for equivalence checking. However, in the presence of loops, it is also necessary to provide sufficient invariants of these loops, which is in general an undecidable task and requires human involvement. When proving equivalivalence of programs at the machine code level, manual inference of invariants can become difficult due to its low readability, even when considering the use of a disassembler. This justifies the need for research on creating approaches to automated program equivalence proofs. This paper presents an approach for automated equivalence checking of machine code level functions with loops, which allows to prove equivalalence of such loop optimizations as loop unrolling and loop pealing. The approach uses – a new method of function alignment based on the analysis of the reachability of basic blocks of code. Function alignment is a necessary step for the subsequent procedure of invariant inference, which is possible only if loops are equalized by the number of iterations. The approach uses SyGuS-solver for invariant inference, which also distinguishes it from other existing equivalence proof approaches that use their own solutions for this purpose.

Zitieren

APA

Putro, P. (2025). LOW-LEVEL CODE SEMANTIC EQUIVALENCE CHECKER. Программирование / Programming and Computer Software, 53. https://doi.org/10.7868/s3034584725060047

Vancouver

Putro P. LOW-LEVEL CODE SEMANTIC EQUIVALENCE CHECKER. Программирование / Programming and Computer Software. 2025:53. doi:10.7868/s3034584725060047

BibTeX
@article{Putro2025,
  author = {Putro, P.A.},
  title = {LOW-LEVEL CODE SEMANTIC EQUIVALENCE CHECKER},
  journal = {Программирование / Programming and Computer Software},
  year = {2025},
  number = {6},
  pages = {53},
  doi = {10.7868/s3034584725060047}
}
Kostenlos starten →