Interprocedural control flow reconstruction

Andrea Flexeder; Bogdan Mihaila; Michael Petter; Helmut Seidl

doi:10.1007/978-3-642-17164-2_14

Interprocedural control flow reconstruction

Andrea Flexeder, Bogdan Mihaila, Michael Petter, Helmut Seidl

Informatics 2 - Chair of Formal Languages, Compiler Construction, Software Construction

Technical University of Munich

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

14 Scopus citations

Abstract

In this paper we provide an interprocedural algorithm for reconstructing the control flow of assembly code in presence of indirect jumps, call instructions and returns. In case that the underlying assembly code is the output of a compiler, indirect jumps primarily originate from high-level switch statements. For these, our methods succeed in resolving indirect jumps with high accuracy. We show that by explicitly handling procedure calls, additional precision is gained at calls to procedures exiting the program as well as through the analysis of side-effects of procedures onto the local state of the caller. Our prototypical implementation applied to real-world examples shows that this approach yields reliable and meaningful results with decent efficiency.

Original language	English
Title of host publication	Programming Languages and Systems - 8th Asian Symposium, APLAS 2010, Proceedings
Pages	188-203
Number of pages	16
DOIs	https://doi.org/10.1007/978-3-642-17164-2_14
State	Published - 2010
Event	8th Asian Symposium on Programming Languages and Systems, APLAS 2010 - Shanghai, China Duration: 28 Nov 2010 → 1 Dec 2010

Publication series

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

Conference

Conference	8th Asian Symposium on Programming Languages and Systems, APLAS 2010
Country/Territory	China
City	Shanghai
Period	28/11/10 → 1/12/10

Keywords

binary analysis
control flow reconstruction
reverse engineering
static analysis

Access to Document

10.1007/978-3-642-17164-2_14

Cite this

Flexeder, A., Mihaila, B., Petter, M., & Seidl, H. (2010). Interprocedural control flow reconstruction. In Programming Languages and Systems - 8th Asian Symposium, APLAS 2010, Proceedings (pp. 188-203). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 6461 LNCS). https://doi.org/10.1007/978-3-642-17164-2_14

@inproceedings{cde6b33703e14c05a175a72e798838c4,

title = "Interprocedural control flow reconstruction",

abstract = "In this paper we provide an interprocedural algorithm for reconstructing the control flow of assembly code in presence of indirect jumps, call instructions and returns. In case that the underlying assembly code is the output of a compiler, indirect jumps primarily originate from high-level switch statements. For these, our methods succeed in resolving indirect jumps with high accuracy. We show that by explicitly handling procedure calls, additional precision is gained at calls to procedures exiting the program as well as through the analysis of side-effects of procedures onto the local state of the caller. Our prototypical implementation applied to real-world examples shows that this approach yields reliable and meaningful results with decent efficiency.",

keywords = "binary analysis, control flow reconstruction, reverse engineering, static analysis",

author = "Andrea Flexeder and Bogdan Mihaila and Michael Petter and Helmut Seidl",

year = "2010",

doi = "10.1007/978-3-642-17164-2_14",

language = "English",

isbn = "364217163X",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

pages = "188--203",

booktitle = "Programming Languages and Systems - 8th Asian Symposium, APLAS 2010, Proceedings",

note = "8th Asian Symposium on Programming Languages and Systems, APLAS 2010 ; Conference date: 28-11-2010 Through 01-12-2010",

}

Flexeder, A, Mihaila, B, Petter, M & Seidl, H 2010, Interprocedural control flow reconstruction. in Programming Languages and Systems - 8th Asian Symposium, APLAS 2010, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 6461 LNCS, pp. 188-203, 8th Asian Symposium on Programming Languages and Systems, APLAS 2010, Shanghai, China, 28/11/10. https://doi.org/10.1007/978-3-642-17164-2_14

Interprocedural control flow reconstruction. / Flexeder, Andrea; Mihaila, Bogdan; Petter, Michael et al.
Programming Languages and Systems - 8th Asian Symposium, APLAS 2010, Proceedings. 2010. p. 188-203 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 6461 LNCS).

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

TY - GEN

T1 - Interprocedural control flow reconstruction

AU - Flexeder, Andrea

AU - Mihaila, Bogdan

AU - Petter, Michael

AU - Seidl, Helmut

PY - 2010

Y1 - 2010

N2 - In this paper we provide an interprocedural algorithm for reconstructing the control flow of assembly code in presence of indirect jumps, call instructions and returns. In case that the underlying assembly code is the output of a compiler, indirect jumps primarily originate from high-level switch statements. For these, our methods succeed in resolving indirect jumps with high accuracy. We show that by explicitly handling procedure calls, additional precision is gained at calls to procedures exiting the program as well as through the analysis of side-effects of procedures onto the local state of the caller. Our prototypical implementation applied to real-world examples shows that this approach yields reliable and meaningful results with decent efficiency.

AB - In this paper we provide an interprocedural algorithm for reconstructing the control flow of assembly code in presence of indirect jumps, call instructions and returns. In case that the underlying assembly code is the output of a compiler, indirect jumps primarily originate from high-level switch statements. For these, our methods succeed in resolving indirect jumps with high accuracy. We show that by explicitly handling procedure calls, additional precision is gained at calls to procedures exiting the program as well as through the analysis of side-effects of procedures onto the local state of the caller. Our prototypical implementation applied to real-world examples shows that this approach yields reliable and meaningful results with decent efficiency.

KW - binary analysis

KW - control flow reconstruction

KW - reverse engineering

KW - static analysis

UR - http://www.scopus.com/inward/record.url?scp=78650753665&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-17164-2_14

DO - 10.1007/978-3-642-17164-2_14

M3 - Conference contribution

AN - SCOPUS:78650753665

SN - 364217163X

SN - 9783642171635

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 188

EP - 203

BT - Programming Languages and Systems - 8th Asian Symposium, APLAS 2010, Proceedings

T2 - 8th Asian Symposium on Programming Languages and Systems, APLAS 2010

Y2 - 28 November 2010 through 1 December 2010

ER -

Interprocedural control flow reconstruction

Abstract

Publication series

Conference

Keywords

Access to Document

Other files and links

Fingerprint

Cite this