Proving LTL Properties of Bitvector Programs and Decompiled Binaries

Yuandong Cyrus Liu, Chengbin Pang, Daniel Dietsch, Eric Koskinen, Ton Chanh Le, Georgios Portokalidis, Jun Xu

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

Abstract

There is increasing interest in applying verification tools to programs that have bitvector operations. SMT solvers, which serve as a foundation for these tools, have thus increased support for bitvector reasoning through bit-blasting and linear arithmetic approximations. In this paper we show that similar linear arithmetic approximation of bitvector operations can be done at the source level through transformations. Specifically, we introduce new paths that over-approximate bitvector operations with linear conditions/constraints, increasing branching but allowing us to better exploit the well-developed integer reasoning and interpolation of verification tools. We show that, for reachability of bitvector programs, increased branching incurs negligible overhead yet, when combined with integer interpolation optimizations, enables more programs to be verified. We further show this exploitation of integer interpolation in the common case also enables competitive termination verification of bitvector programs and leads to the first effective technique for linear temporal logic (LTL) verification of bitvector programs. Finally, we provide an in-depth case study of decompiled (“lifted”) binary programs, which emulate X86 execution through frequent use of bitvector operations. We present a new tool DarkSea, the first tool capable of verifying reachability, termination and LTL of lifted binaries.

Original languageEnglish
Title of host publicationProgramming Languages and Systems - 19th Asian Symposium, APLAS 2021, Proceedings
EditorsHakjoo Oh
Pages285-304
Number of pages20
DOIs
StatePublished - 2021
Event19th Asian Symposium on Programming Languages and Systems, APLAS 2021 - Chicago, United States
Duration: 17 Oct 202118 Oct 2021

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume13008 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference19th Asian Symposium on Programming Languages and Systems, APLAS 2021
Country/TerritoryUnited States
CityChicago
Period17/10/2118/10/21

Fingerprint

Dive into the research topics of 'Proving LTL Properties of Bitvector Programs and Decompiled Binaries'. Together they form a unique fingerprint.

Cite this