Triereme: Speeding up hybrid fuzzing through efficient query scheduling

Elia Geretto; Julius Hohnerlein; Cristiano Giuffrida; Herbert Bos; Erik Van Der Kouwe; Klaus V. Gleissenthall

doi:10.1145/3627106.3627173

Triereme: Speeding up hybrid fuzzing through efficient query scheduling

Elia Geretto, Julius Hohnerlein, Cristiano Giuffrida, Herbert Bos, Erik Van Der Kouwe, Klaus V. Gleissenthall

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

89 Downloads (Pure)

Abstract

Hybrid fuzzing, the combination between fuzzing and concolic execution, holds great promise in theory, but has so far failed to deliver all the expected advantages in practice due to its high overhead. The cause is the large amount of time spent in the SMT solver. As a result, hybrid fuzzers often lose out to simpler, yet faster techniques. This issue remains despite novel query pruning techniques that reduce the number and complexity of solver queries as they preclude other crucial optimizations like incremental solving. We introduce Triereme, a method to speed up the hybrid fuzzer's concolic engine by reducing the time spent in the SMT solver. Triereme uses a trie (or prefix tree) data structure to schedule and cache solver queries, exploiting common prefixes. This design is made possible by decoupling concolic tracing from concolic solving. As a result, Triereme manages to reconcile pruning with incremental solving, reaping their combined benefits. In our tests, Triereme speeds up concolic executions by 6.1x on average in FuzzBench [22] and improves coverage progress in 79% of the benchmarks.

Original language	English
Title of host publication	ACSAC 2023
Subtitle of host publication	Proceedings of the 39th Annual Computer Security Applications Conference
Publisher	Association for Computing Machinery
Pages	56-70
Number of pages	15
ISBN (Electronic)	9798400708862
DOIs	https://doi.org/10.1145/3627106.3627173
Publication status	Published - 2023
Event	39th Annual Computer Security Applications Conference, ACSAC 2023 - Austin, United States Duration: 4 Dec 2023 → 8 Dec 2023

Publication series

Name	ACM International Conference Proceeding Series

Conference

Conference	39th Annual Computer Security Applications Conference, ACSAC 2023
Country/Territory	United States
City	Austin
Period	4/12/23 → 8/12/23

Bibliographical note

Funding Information:
This work was supported by EZK through AVR
“Memo” and by NWO through “INTERSECT” and “Vulcan”.

Publisher Copyright:
© 2023 Owner/Author.

Funding

This work was supported by EZK through AVR “Memo” and by NWO through “INTERSECT” and “Vulcan”.

Funders	Funder number
Nederlandse Organisatie voor Wetenschappelijk Onderzoek	INTERSECT, Vulcan (VI.Veni.202.212)

Keywords

concolic execution
fuzzing
hybrid fuzzing
program analysis

Access to Document

10.1145/3627106.3627173

Triereme: Speeding up hybrid fuzzing through efficient query schedulingFinal published version, 1.36 MB

Persistent URL (handle)

Persistent link

Cite this

Geretto, E., Hohnerlein, J., Giuffrida, C., Bos, H., Van Der Kouwe, E., & V. Gleissenthall, K. (2023). Triereme: Speeding up hybrid fuzzing through efficient query scheduling. In ACSAC 2023 : Proceedings of the 39th Annual Computer Security Applications Conference (pp. 56-70). (ACM International Conference Proceeding Series). Association for Computing Machinery. https://doi.org/10.1145/3627106.3627173

@inproceedings{4428bd3d14fe4790b05d955c26cf940c,

title = "Triereme: Speeding up hybrid fuzzing through efficient query scheduling",

abstract = "Hybrid fuzzing, the combination between fuzzing and concolic execution, holds great promise in theory, but has so far failed to deliver all the expected advantages in practice due to its high overhead. The cause is the large amount of time spent in the SMT solver. As a result, hybrid fuzzers often lose out to simpler, yet faster techniques. This issue remains despite novel query pruning techniques that reduce the number and complexity of solver queries as they preclude other crucial optimizations like incremental solving. We introduce Triereme, a method to speed up the hybrid fuzzer's concolic engine by reducing the time spent in the SMT solver. Triereme uses a trie (or prefix tree) data structure to schedule and cache solver queries, exploiting common prefixes. This design is made possible by decoupling concolic tracing from concolic solving. As a result, Triereme manages to reconcile pruning with incremental solving, reaping their combined benefits. In our tests, Triereme speeds up concolic executions by 6.1x on average in FuzzBench [22] and improves coverage progress in 79% of the benchmarks.",

keywords = "concolic execution, fuzzing, hybrid fuzzing, program analysis",

author = "Elia Geretto and Julius Hohnerlein and Cristiano Giuffrida and Herbert Bos and {Van Der Kouwe}, Erik and {V. Gleissenthall}, Klaus",

note = "Funding Information: This work was supported by EZK through AVR “Memo” and by NWO through “INTERSECT” and “Vulcan”. Publisher Copyright: {\textcopyright} 2023 Owner/Author.; 39th Annual Computer Security Applications Conference, ACSAC 2023 ; Conference date: 04-12-2023 Through 08-12-2023",

year = "2023",

doi = "10.1145/3627106.3627173",

language = "English",

series = "ACM International Conference Proceeding Series",

publisher = "Association for Computing Machinery",

pages = "56--70",

booktitle = "ACSAC 2023",

}

Geretto, E, Hohnerlein, J, Giuffrida, C , Bos, H , Van Der Kouwe, E & V. Gleissenthall, K 2023, Triereme: Speeding up hybrid fuzzing through efficient query scheduling. in ACSAC 2023 : Proceedings of the 39th Annual Computer Security Applications Conference. ACM International Conference Proceeding Series, Association for Computing Machinery, pp. 56-70, 39th Annual Computer Security Applications Conference, ACSAC 2023, Austin, United States, 4/12/23. https://doi.org/10.1145/3627106.3627173

Triereme: Speeding up hybrid fuzzing through efficient query scheduling. / Geretto, Elia; Hohnerlein, Julius; Giuffrida, Cristiano et al.
ACSAC 2023 : Proceedings of the 39th Annual Computer Security Applications Conference. Association for Computing Machinery, 2023. p. 56-70 (ACM International Conference Proceeding Series).

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

TY - GEN

T1 - Triereme: Speeding up hybrid fuzzing through efficient query scheduling

AU - Geretto, Elia

AU - Hohnerlein, Julius

AU - Giuffrida, Cristiano

AU - Bos, Herbert

AU - Van Der Kouwe, Erik

AU - V. Gleissenthall, Klaus

PY - 2023

Y1 - 2023

N2 - Hybrid fuzzing, the combination between fuzzing and concolic execution, holds great promise in theory, but has so far failed to deliver all the expected advantages in practice due to its high overhead. The cause is the large amount of time spent in the SMT solver. As a result, hybrid fuzzers often lose out to simpler, yet faster techniques. This issue remains despite novel query pruning techniques that reduce the number and complexity of solver queries as they preclude other crucial optimizations like incremental solving. We introduce Triereme, a method to speed up the hybrid fuzzer's concolic engine by reducing the time spent in the SMT solver. Triereme uses a trie (or prefix tree) data structure to schedule and cache solver queries, exploiting common prefixes. This design is made possible by decoupling concolic tracing from concolic solving. As a result, Triereme manages to reconcile pruning with incremental solving, reaping their combined benefits. In our tests, Triereme speeds up concolic executions by 6.1x on average in FuzzBench [22] and improves coverage progress in 79% of the benchmarks.

AB - Hybrid fuzzing, the combination between fuzzing and concolic execution, holds great promise in theory, but has so far failed to deliver all the expected advantages in practice due to its high overhead. The cause is the large amount of time spent in the SMT solver. As a result, hybrid fuzzers often lose out to simpler, yet faster techniques. This issue remains despite novel query pruning techniques that reduce the number and complexity of solver queries as they preclude other crucial optimizations like incremental solving. We introduce Triereme, a method to speed up the hybrid fuzzer's concolic engine by reducing the time spent in the SMT solver. Triereme uses a trie (or prefix tree) data structure to schedule and cache solver queries, exploiting common prefixes. This design is made possible by decoupling concolic tracing from concolic solving. As a result, Triereme manages to reconcile pruning with incremental solving, reaping their combined benefits. In our tests, Triereme speeds up concolic executions by 6.1x on average in FuzzBench [22] and improves coverage progress in 79% of the benchmarks.

KW - concolic execution

KW - fuzzing

KW - hybrid fuzzing

KW - program analysis

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

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

U2 - 10.1145/3627106.3627173

DO - 10.1145/3627106.3627173

M3 - Conference contribution

AN - SCOPUS:85180147335

T3 - ACM International Conference Proceeding Series

SP - 56

EP - 70

BT - ACSAC 2023

PB - Association for Computing Machinery

T2 - 39th Annual Computer Security Applications Conference, ACSAC 2023

Y2 - 4 December 2023 through 8 December 2023

ER -

Geretto E, Hohnerlein J, Giuffrida C , Bos H , Van Der Kouwe E , V. Gleissenthall K. Triereme: Speeding up hybrid fuzzing through efficient query scheduling. In ACSAC 2023 : Proceedings of the 39th Annual Computer Security Applications Conference. Association for Computing Machinery. 2023. p. 56-70. (ACM International Conference Proceeding Series). Epub 2023 Dec 4. doi: 10.1145/3627106.3627173

Triereme: Speeding up hybrid fuzzing through efficient query scheduling

Abstract

Publication series

Conference

Bibliographical note

Funding

Keywords

Access to Document

Persistent URL (handle)

Other files and links

Fingerprint

Cite this