Conference
MC2: Rigorous and Efficient Directed Greybox Fuzzing
| العنوان: | MC2: Rigorous and Efficient Directed Greybox Fuzzing |
|---|---|
| المؤلفون: | Shah, Abhishek, She, Dongdong, Sadhu, Samanway, Singal, Krish, Coffman, Peter, Jana, Suman |
| بيانات النشر: | Association for Computing Machinery |
| سنة النشر: | 2022 |
| المجموعة: | The Hong Kong University of Science and Technology: HKUST Institutional Repository |
| مصطلحات موضوعية: | Automated vulnerability detection, Execution complexity, Greybox fuzzing, Monte carlo counting, Noisy binary search |
| الوصف: | Directed greybox fuzzing is a popular technique for targeted software testing that seeks to find inputs that reach a set of target sites in a program. Most existing directed greybox fuzzers do not provide any theoretical analysis of their performance or optimality. In this paper, we introduce a complexity-theoretic framework to pose directed greybox fuzzing as an oracle-guided search problem where some feedback about the input space (e.g., how close an input is to the target sites) is received by querying an oracle. Our framework assumes that each oracle query can return arbitrary content with a large but constant amount of information. Therefore, we use the number of oracle queries required by a fuzzing algorithm to find a target-reaching input as the performance metric. Using our framework, we design a randomized directed greybox fuzzing algorithm that makes a logarithmic (wrt. the number of all possible inputs) number of queries in expectation to find a target-reaching input. We further prove that the number of oracle queries required by our algorithm is optimal, i.e., no fuzzing algorithm can improve (i.e., minimize) the query count by more than a constant factor. We implement our approach in MC2 and outperform state-of-the-art directed greybox fuzzers on challenging benchmarks (Magma and Fuzzer Test Suite) by up to two orders of magnitude (i.e., 134times) on average. MC2 also found 15 previously undiscovered bugs that other state-of-the-art directed greybox fuzzers failed to find. |
| نوع الوثيقة: | conference object |
| اللغة: | English |
| تدمد: | 1543-7221 |
| Relation: | https://repository.hkust.edu.hk/ir/Record/1783.1-128690; CCS '22: Proceedings of the 2022 ACM SIGSAC Conference on Computer and Communications Security / Association for Computing Machinery. New York, NY : Association for Computing Machinery, 2022, p. 2595-2609; https://doi.org/10.1145/3548606.3560648; http://lbdiscover.ust.hk/uresolver?url_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rfr_id=info:sid/HKUST:SPI&rft.genre=article&rft.issn=1543-7221&rft.volume=&rft.issue=&rft.date=2022&rft.spage=2595&rft.aulast=Shah&rft.aufirst=Abhishek&rft.atitle=MC2%3A+Rigorous+and+Efficient+Directed+Greybox+Fuzzing&rft.title=Proceedings+of+the+ACM+Conference+on+Computer+and+Communications+Security; http://www.scopus.com/record/display.url?eid=2-s2.0-85143048074&origin=inward |
| DOI: | 10.1145/3548606.3560648 |
| الاتاحة: | https://repository.hkust.edu.hk/ir/Record/1783.1-128690 https://doi.org/10.1145/3548606.3560648 http://lbdiscover.ust.hk/uresolver?url_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rfr_id=info:sid/HKUST:SPI&rft.genre=article&rft.issn=1543-7221&rft.volume=&rft.issue=&rft.date=2022&rft.spage=2595&rft.aulast=Shah&rft.aufirst=Abhishek&rft.atitle=MC2%3A+Rigorous+and+Efficient+Directed+Greybox+Fuzzing&rft.title=Proceedings+of+the+ACM+Conference+on+Computer+and+Communications+Security http://www.scopus.com/record/display.url?eid=2-s2.0-85143048074&origin=inward |
| رقم الانضمام: | edsbas.E52B9D27 |
| قاعدة البيانات: | BASE |
| ResultId |
1 |
|---|---|
| Header |
edsbas BASE edsbas.E52B9D27 883 3 Conference conference 882.599182128906 |
| PLink |
https://search.ebscohost.com/login.aspx?direct=true&site=eds-live&scope=site&db=edsbas&AN=edsbas.E52B9D27&custid=s6537998&authtype=sso |
| FullText |
Array
(
[Availability] => 0
)
Array ( [0] => Array ( [Url] => https://repository.hkust.edu.hk/ir/Record/1783.1-128690# [Name] => EDS - BASE [Category] => fullText [Text] => View record in BASE [MouseOverText] => View record in BASE ) ) |
| Items |
Array
(
[Name] => Title
[Label] => Title
[Group] => Ti
[Data] => MC2: Rigorous and Efficient Directed Greybox Fuzzing
)
Array ( [Name] => Author [Label] => Authors [Group] => Au [Data] => <searchLink fieldCode="AR" term="%22Shah%2C+Abhishek%22">Shah, Abhishek</searchLink><br /><searchLink fieldCode="AR" term="%22She%2C+Dongdong%22">She, Dongdong</searchLink><br /><searchLink fieldCode="AR" term="%22Sadhu%2C+Samanway%22">Sadhu, Samanway</searchLink><br /><searchLink fieldCode="AR" term="%22Singal%2C+Krish%22">Singal, Krish</searchLink><br /><searchLink fieldCode="AR" term="%22Coffman%2C+Peter%22">Coffman, Peter</searchLink><br /><searchLink fieldCode="AR" term="%22Jana%2C+Suman%22">Jana, Suman</searchLink> ) Array ( [Name] => Publisher [Label] => Publisher Information [Group] => PubInfo [Data] => Association for Computing Machinery ) Array ( [Name] => DatePubCY [Label] => Publication Year [Group] => Date [Data] => 2022 ) Array ( [Name] => Subset [Label] => Collection [Group] => HoldingsInfo [Data] => The Hong Kong University of Science and Technology: HKUST Institutional Repository ) Array ( [Name] => Subject [Label] => Subject Terms [Group] => Su [Data] => <searchLink fieldCode="DE" term="%22Automated+vulnerability+detection%22">Automated vulnerability detection</searchLink><br /><searchLink fieldCode="DE" term="%22Execution+complexity%22">Execution complexity</searchLink><br /><searchLink fieldCode="DE" term="%22Greybox+fuzzing%22">Greybox fuzzing</searchLink><br /><searchLink fieldCode="DE" term="%22Monte+carlo+counting%22">Monte carlo counting</searchLink><br /><searchLink fieldCode="DE" term="%22Noisy+binary+search%22">Noisy binary search</searchLink> ) Array ( [Name] => Abstract [Label] => Description [Group] => Ab [Data] => Directed greybox fuzzing is a popular technique for targeted software testing that seeks to find inputs that reach a set of target sites in a program. Most existing directed greybox fuzzers do not provide any theoretical analysis of their performance or optimality. In this paper, we introduce a complexity-theoretic framework to pose directed greybox fuzzing as an oracle-guided search problem where some feedback about the input space (e.g., how close an input is to the target sites) is received by querying an oracle. Our framework assumes that each oracle query can return arbitrary content with a large but constant amount of information. Therefore, we use the number of oracle queries required by a fuzzing algorithm to find a target-reaching input as the performance metric. Using our framework, we design a randomized directed greybox fuzzing algorithm that makes a logarithmic (wrt. the number of all possible inputs) number of queries in expectation to find a target-reaching input. We further prove that the number of oracle queries required by our algorithm is optimal, i.e., no fuzzing algorithm can improve (i.e., minimize) the query count by more than a constant factor. We implement our approach in MC2 and outperform state-of-the-art directed greybox fuzzers on challenging benchmarks (Magma and Fuzzer Test Suite) by up to two orders of magnitude (i.e., 134times) on average. MC2 also found 15 previously undiscovered bugs that other state-of-the-art directed greybox fuzzers failed to find. ) Array ( [Name] => TypeDocument [Label] => Document Type [Group] => TypDoc [Data] => conference object ) Array ( [Name] => Language [Label] => Language [Group] => Lang [Data] => English ) Array ( [Name] => ISSN [Label] => ISSN [Group] => ISSN [Data] => 1543-7221 ) Array ( [Name] => NoteTitleSource [Label] => Relation [Group] => SrcInfo [Data] => https://repository.hkust.edu.hk/ir/Record/1783.1-128690; CCS '22: Proceedings of the 2022 ACM SIGSAC Conference on Computer and Communications Security / Association for Computing Machinery. New York, NY : Association for Computing Machinery, 2022, p. 2595-2609; https://doi.org/10.1145/3548606.3560648; http://lbdiscover.ust.hk/uresolver?url_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rfr_id=info:sid/HKUST:SPI&rft.genre=article&rft.issn=1543-7221&rft.volume=&rft.issue=&rft.date=2022&rft.spage=2595&rft.aulast=Shah&rft.aufirst=Abhishek&rft.atitle=MC2%3A+Rigorous+and+Efficient+Directed+Greybox+Fuzzing&rft.title=Proceedings+of+the+ACM+Conference+on+Computer+and+Communications+Security; http://www.scopus.com/record/display.url?eid=2-s2.0-85143048074&origin=inward ) Array ( [Name] => DOI [Label] => DOI [Group] => ID [Data] => 10.1145/3548606.3560648 ) Array ( [Name] => URL [Label] => Availability [Group] => URL [Data] => https://repository.hkust.edu.hk/ir/Record/1783.1-128690<br />https://doi.org/10.1145/3548606.3560648<br />http://lbdiscover.ust.hk/uresolver?url_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rfr_id=info:sid/HKUST:SPI&rft.genre=article&rft.issn=1543-7221&rft.volume=&rft.issue=&rft.date=2022&rft.spage=2595&rft.aulast=Shah&rft.aufirst=Abhishek&rft.atitle=MC2%3A+Rigorous+and+Efficient+Directed+Greybox+Fuzzing&rft.title=Proceedings+of+the+ACM+Conference+on+Computer+and+Communications+Security<br />http://www.scopus.com/record/display.url?eid=2-s2.0-85143048074&origin=inward ) Array ( [Name] => AN [Label] => Accession Number [Group] => ID [Data] => edsbas.E52B9D27 ) |
| RecordInfo |
Array
(
[BibEntity] => Array
(
[Identifiers] => Array
(
[0] => Array
(
[Type] => doi
[Value] => 10.1145/3548606.3560648
)
)
[Languages] => Array
(
[0] => Array
(
[Text] => English
)
)
[Subjects] => Array
(
[0] => Array
(
[SubjectFull] => Automated vulnerability detection
[Type] => general
)
[1] => Array
(
[SubjectFull] => Execution complexity
[Type] => general
)
[2] => Array
(
[SubjectFull] => Greybox fuzzing
[Type] => general
)
[3] => Array
(
[SubjectFull] => Monte carlo counting
[Type] => general
)
[4] => Array
(
[SubjectFull] => Noisy binary search
[Type] => general
)
)
[Titles] => Array
(
[0] => Array
(
[TitleFull] => MC2: Rigorous and Efficient Directed Greybox Fuzzing
[Type] => main
)
)
)
[BibRelationships] => Array
(
[HasContributorRelationships] => Array
(
[0] => Array
(
[PersonEntity] => Array
(
[Name] => Array
(
[NameFull] => Shah, Abhishek
)
)
)
[1] => Array
(
[PersonEntity] => Array
(
[Name] => Array
(
[NameFull] => She, Dongdong
)
)
)
[2] => Array
(
[PersonEntity] => Array
(
[Name] => Array
(
[NameFull] => Sadhu, Samanway
)
)
)
[3] => Array
(
[PersonEntity] => Array
(
[Name] => Array
(
[NameFull] => Singal, Krish
)
)
)
[4] => Array
(
[PersonEntity] => Array
(
[Name] => Array
(
[NameFull] => Coffman, Peter
)
)
)
[5] => Array
(
[PersonEntity] => Array
(
[Name] => Array
(
[NameFull] => Jana, Suman
)
)
)
)
[IsPartOfRelationships] => Array
(
[0] => Array
(
[BibEntity] => Array
(
[Dates] => Array
(
[0] => Array
(
[D] => 01
[M] => 01
[Type] => published
[Y] => 2022
)
)
[Identifiers] => Array
(
[0] => Array
(
[Type] => issn-print
[Value] => 15437221
)
[1] => Array
(
[Type] => issn-locals
[Value] => edsbas
)
)
)
)
)
)
)
|
| IllustrationInfo |