Making symbolic execution promising by learning aggressive state-pruning strategy

Sooyoung Cha; Hakjoo Oh

doi:10.1145/3368089.3409755

Making symbolic execution promising by learning aggressive state-pruning strategy

Sooyoung Cha, Hakjoo Oh

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

10 Citations (Scopus)

Abstract

We present HOMI, a new technique to enhance symbolic execution by maintaining only a small number of promising states. In practice, symbolic execution typically maintains as many states as possible in a fear of losing important states. In this paper, however, we show that only a tiny subset of the states plays a significant role in increasing code coverage or reaching bug points. Based on this observation, HOMI aims to minimize the total number of states while keeping "promising"states during symbolic execution. We identify promising states by a learning algorithm that continuously updates the probabilistic pruning strategy based on data accumulated during the testing process. Experimental results show that HOMI greatly increases code coverage and the ability to find bugs of KLEE on open-source C programs.

Original language	English
Title of host publication	ESEC/FSE 2020 - Proceedings of the 28th ACM Joint Meeting European Software Engineering Conference and Symposium on the Foundations of Software Engineering
Editors	Prem Devanbu, Myra Cohen, Thomas Zimmermann
Publisher	Association for Computing Machinery, Inc
Pages	147-158
Number of pages	12
ISBN (Electronic)	9781450370431
DOIs	https://doi.org/10.1145/3368089.3409755
Publication status	Published - 2020 Nov 8
Event	28th ACM Joint Meeting European Software Engineering Conference and Symposium on the Foundations of Software Engineering, ESEC/FSE 2020 - Virtual, Online, United States Duration: 2020 Nov 8 → 2020 Nov 13

Publication series

Name	ESEC/FSE 2020 - Proceedings of the 28th ACM Joint Meeting European Software Engineering Conference and Symposium on the Foundations of Software Engineering

Conference

Conference	28th ACM Joint Meeting European Software Engineering Conference and Symposium on the Foundations of Software Engineering, ESEC/FSE 2020
Country/Territory	United States
City	Virtual, Online
Period	20/11/8 → 20/11/13

Bibliographical note

Publisher Copyright:
© 2020 ACM.

Keywords

Dynamic Symbolic Execution
Online Learning

ASJC Scopus subject areas

Software

Access to Document

10.1145/3368089.3409755

Cite this

Cha, S., & Oh, H. (2020). Making symbolic execution promising by learning aggressive state-pruning strategy. In P. Devanbu, M. Cohen, & T. Zimmermann (Eds.), ESEC/FSE 2020 - Proceedings of the 28th ACM Joint Meeting European Software Engineering Conference and Symposium on the Foundations of Software Engineering (pp. 147-158). (ESEC/FSE 2020 - Proceedings of the 28th ACM Joint Meeting European Software Engineering Conference and Symposium on the Foundations of Software Engineering). Association for Computing Machinery, Inc. https://doi.org/10.1145/3368089.3409755

Making symbolic execution promising by learning aggressive state-pruning strategy. / Cha, Sooyoung; Oh, Hakjoo.
ESEC/FSE 2020 - Proceedings of the 28th ACM Joint Meeting European Software Engineering Conference and Symposium on the Foundations of Software Engineering. ed. / Prem Devanbu; Myra Cohen; Thomas Zimmermann. Association for Computing Machinery, Inc, 2020. p. 147-158 (ESEC/FSE 2020 - Proceedings of the 28th ACM Joint Meeting European Software Engineering Conference and Symposium on the Foundations of Software Engineering).

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

Cha, S & Oh, H 2020, Making symbolic execution promising by learning aggressive state-pruning strategy. in P Devanbu, M Cohen & T Zimmermann (eds), ESEC/FSE 2020 - Proceedings of the 28th ACM Joint Meeting European Software Engineering Conference and Symposium on the Foundations of Software Engineering. ESEC/FSE 2020 - Proceedings of the 28th ACM Joint Meeting European Software Engineering Conference and Symposium on the Foundations of Software Engineering, Association for Computing Machinery, Inc, pp. 147-158, 28th ACM Joint Meeting European Software Engineering Conference and Symposium on the Foundations of Software Engineering, ESEC/FSE 2020, Virtual, Online, United States, 20/11/8. https://doi.org/10.1145/3368089.3409755

Cha S, Oh H. Making symbolic execution promising by learning aggressive state-pruning strategy. In Devanbu P, Cohen M, Zimmermann T, editors, ESEC/FSE 2020 - Proceedings of the 28th ACM Joint Meeting European Software Engineering Conference and Symposium on the Foundations of Software Engineering. Association for Computing Machinery, Inc. 2020. p. 147-158. (ESEC/FSE 2020 - Proceedings of the 28th ACM Joint Meeting European Software Engineering Conference and Symposium on the Foundations of Software Engineering). doi: 10.1145/3368089.3409755

Cha, Sooyoung ; Oh, Hakjoo. / Making symbolic execution promising by learning aggressive state-pruning strategy. ESEC/FSE 2020 - Proceedings of the 28th ACM Joint Meeting European Software Engineering Conference and Symposium on the Foundations of Software Engineering. editor / Prem Devanbu ; Myra Cohen ; Thomas Zimmermann. Association for Computing Machinery, Inc, 2020. pp. 147-158 (ESEC/FSE 2020 - Proceedings of the 28th ACM Joint Meeting European Software Engineering Conference and Symposium on the Foundations of Software Engineering).

@inproceedings{2ba25840d7934518b79759b836b6011f,

title = "Making symbolic execution promising by learning aggressive state-pruning strategy",

abstract = "We present HOMI, a new technique to enhance symbolic execution by maintaining only a small number of promising states. In practice, symbolic execution typically maintains as many states as possible in a fear of losing important states. In this paper, however, we show that only a tiny subset of the states plays a significant role in increasing code coverage or reaching bug points. Based on this observation, HOMI aims to minimize the total number of states while keeping {"}promising{"}states during symbolic execution. We identify promising states by a learning algorithm that continuously updates the probabilistic pruning strategy based on data accumulated during the testing process. Experimental results show that HOMI greatly increases code coverage and the ability to find bugs of KLEE on open-source C programs.",

keywords = "Dynamic Symbolic Execution, Online Learning",

author = "Sooyoung Cha and Hakjoo Oh",

note = "Publisher Copyright: {\textcopyright} 2020 ACM.; 28th ACM Joint Meeting European Software Engineering Conference and Symposium on the Foundations of Software Engineering, ESEC/FSE 2020 ; Conference date: 08-11-2020 Through 13-11-2020",

year = "2020",

month = nov,

day = "8",

doi = "10.1145/3368089.3409755",

language = "English",

series = "ESEC/FSE 2020 - Proceedings of the 28th ACM Joint Meeting European Software Engineering Conference and Symposium on the Foundations of Software Engineering",

publisher = "Association for Computing Machinery, Inc",

pages = "147--158",

editor = "Prem Devanbu and Myra Cohen and Thomas Zimmermann",

booktitle = "ESEC/FSE 2020 - Proceedings of the 28th ACM Joint Meeting European Software Engineering Conference and Symposium on the Foundations of Software Engineering",

}

TY - GEN

T1 - Making symbolic execution promising by learning aggressive state-pruning strategy

AU - Cha, Sooyoung

AU - Oh, Hakjoo

PY - 2020/11/8

Y1 - 2020/11/8

N2 - We present HOMI, a new technique to enhance symbolic execution by maintaining only a small number of promising states. In practice, symbolic execution typically maintains as many states as possible in a fear of losing important states. In this paper, however, we show that only a tiny subset of the states plays a significant role in increasing code coverage or reaching bug points. Based on this observation, HOMI aims to minimize the total number of states while keeping "promising"states during symbolic execution. We identify promising states by a learning algorithm that continuously updates the probabilistic pruning strategy based on data accumulated during the testing process. Experimental results show that HOMI greatly increases code coverage and the ability to find bugs of KLEE on open-source C programs.

AB - We present HOMI, a new technique to enhance symbolic execution by maintaining only a small number of promising states. In practice, symbolic execution typically maintains as many states as possible in a fear of losing important states. In this paper, however, we show that only a tiny subset of the states plays a significant role in increasing code coverage or reaching bug points. Based on this observation, HOMI aims to minimize the total number of states while keeping "promising"states during symbolic execution. We identify promising states by a learning algorithm that continuously updates the probabilistic pruning strategy based on data accumulated during the testing process. Experimental results show that HOMI greatly increases code coverage and the ability to find bugs of KLEE on open-source C programs.

KW - Dynamic Symbolic Execution

KW - Online Learning

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

U2 - 10.1145/3368089.3409755

DO - 10.1145/3368089.3409755

M3 - Conference contribution

AN - SCOPUS:85097188328

T3 - ESEC/FSE 2020 - Proceedings of the 28th ACM Joint Meeting European Software Engineering Conference and Symposium on the Foundations of Software Engineering

SP - 147

EP - 158

BT - ESEC/FSE 2020 - Proceedings of the 28th ACM Joint Meeting European Software Engineering Conference and Symposium on the Foundations of Software Engineering

A2 - Devanbu, Prem

A2 - Cohen, Myra

A2 - Zimmermann, Thomas

PB - Association for Computing Machinery, Inc

T2 - 28th ACM Joint Meeting European Software Engineering Conference and Symposium on the Foundations of Software Engineering, ESEC/FSE 2020

Y2 - 8 November 2020 through 13 November 2020

ER -

Making symbolic execution promising by learning aggressive state-pruning strategy

Abstract

Publication series

Conference

Bibliographical note

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this