An Abstract Interpretation-Based Framework for Control Flow Reconstruction from Binaries

Johannes Kinder; Florian Zuleger; Helmut Veith

doi:10.1007/978-3-540-93900-9_19

An Abstract Interpretation-Based Framework for Control Flow Reconstruction from Binaries

Johannes Kinder, Florian Zuleger, Helmut Veith

Department of Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

832 Downloads (Pure)

Abstract

Due to indirect branch instructions, analyses on executables commonly suffer from the problem that a complete control flow graph of the program is not available. Data flow analysis has been proposed before to statically determine branch targets in many cases, yet a generic strategy without assumptions on compiler idioms or debug information is lacking. We have devised an abstract interpretation-based framework for generic low level programs with indirect jumps which safely combines a pluggable abstract domain with the notion of partial control flow graphs. Using our framework, we are able to show that the control flow reconstruction algorithm of our disassembly tool Jakstab produces the most precise overapproximation of the control flow graph with respect to the used abstract domain.

Original language	English
Title of host publication	Proc. 10th Int. Conf. Verification, Model Checking, and Abstract Interpretation (VMCAI 2009)
Publisher	Springer
Pages	214-228
DOIs	https://doi.org/10.1007/978-3-540-93900-9_19
Publication status	Published - 2009

Access to Document

10.1007/978-3-540-93900-9_19

vmcai09Accepted author manuscript, 256 KB

Cite this

@inproceedings{b900d9fa09cd40c5bb8dc8cdd72e28b9,

title = "An Abstract Interpretation-Based Framework for Control Flow Reconstruction from Binaries",

abstract = "Due to indirect branch instructions, analyses on executables commonly suffer from the problem that a complete control flow graph of the program is not available. Data flow analysis has been proposed before to statically determine branch targets in many cases, yet a generic strategy without assumptions on compiler idioms or debug information is lacking. We have devised an abstract interpretation-based framework for generic low level programs with indirect jumps which safely combines a pluggable abstract domain with the notion of partial control flow graphs. Using our framework, we are able to show that the control flow reconstruction algorithm of our disassembly tool Jakstab produces the most precise overapproximation of the control flow graph with respect to the used abstract domain.",

author = "Johannes Kinder and Florian Zuleger and Helmut Veith",

year = "2009",

doi = "10.1007/978-3-540-93900-9_19",

language = "English",

pages = "214--228",

booktitle = "Proc. 10th Int. Conf. Verification, Model Checking, and Abstract Interpretation (VMCAI 2009)",

publisher = "Springer",

}

TY - GEN

T1 - An Abstract Interpretation-Based Framework for Control Flow Reconstruction from Binaries

AU - Kinder, Johannes

AU - Zuleger, Florian

AU - Veith, Helmut

PY - 2009

Y1 - 2009

N2 - Due to indirect branch instructions, analyses on executables commonly suffer from the problem that a complete control flow graph of the program is not available. Data flow analysis has been proposed before to statically determine branch targets in many cases, yet a generic strategy without assumptions on compiler idioms or debug information is lacking. We have devised an abstract interpretation-based framework for generic low level programs with indirect jumps which safely combines a pluggable abstract domain with the notion of partial control flow graphs. Using our framework, we are able to show that the control flow reconstruction algorithm of our disassembly tool Jakstab produces the most precise overapproximation of the control flow graph with respect to the used abstract domain.

AB - Due to indirect branch instructions, analyses on executables commonly suffer from the problem that a complete control flow graph of the program is not available. Data flow analysis has been proposed before to statically determine branch targets in many cases, yet a generic strategy without assumptions on compiler idioms or debug information is lacking. We have devised an abstract interpretation-based framework for generic low level programs with indirect jumps which safely combines a pluggable abstract domain with the notion of partial control flow graphs. Using our framework, we are able to show that the control flow reconstruction algorithm of our disassembly tool Jakstab produces the most precise overapproximation of the control flow graph with respect to the used abstract domain.

U2 - 10.1007/978-3-540-93900-9_19

DO - 10.1007/978-3-540-93900-9_19

M3 - Conference contribution

SP - 214

EP - 228

BT - Proc. 10th Int. Conf. Verification, Model Checking, and Abstract Interpretation (VMCAI 2009)

PB - Springer

ER -