liu.seSearch for publications in DiVA
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Speeding Up Bug Finding using Focused Fuzzing
Linköping University, Department of Computer and Information Science, Database and information techniques. Linköping University, Faculty of Science & Engineering.
Linköping University, Department of Computer and Information Science, Database and information techniques. Linköping University, Faculty of Science & Engineering.
2019 (English)In: Proceedings of the 13th International Conference on Availability, Reliability and Security, ACM Digital Library, 2019, article id 7Conference paper, Published paper (Refereed)
Abstract [en]

Greybox fuzzing has recently emerged as a scalable and practical approach to finding security bugs in software. For example, AFL — the current state-of-the-art greybox fuzzer — has found hundreds of vulnerabilities in popular software since its release in 2013. The combination of lightweight coverage instrumentation and a simple evolutionary algorithm allows AFL to quickly generate inputs that exercise new code. AFL also obviates the need to manually set ad-hoc fuzzing ratios, which has been a major limitation of classical black-box fuzzers. Instead, AFL's first fuzzing pass exhaustively applies a set of mutations to every byte of a program input. While this approach allows for more thorough exploration of the input space, and therefore improves the chances of finding complex bugs, it also drastically slows down the fuzzing progress for "heavyweight" programs, or programs that take large inputs. This makes AFL less suitable for fuzzing input formats with large size overhead, such as various document formats. In this paper, we propose focused fuzzing as a practical trade-off between thoroughness and speed, for fuzzers that employ input mutation. We extend the notion of code coverage to individual bytes of input, and show how forward dynamic slicing can be used to efficiently determine the set of program instructions that are affected by a particular input byte. This information can then be used to restrict expensive mutations to a small subset of input bytes. We implement focused fuzzing on top of AFL, and evaluate it on four "real-life" Linux programs. Our evaluation shows that focused fuzzing noticeably improves bug discovery, compared to vanilla AFL.

Place, publisher, year, edition, pages
ACM Digital Library, 2019. article id 7
Keywords [en]
fuzzing, AFL, dynamic slicing, focused fuzzing
National Category
Computer Sciences
Identifiers
URN: urn:nbn:se:liu:diva-152737DOI: 10.1145/3230833.3230867ISI: 000477981800013ISBN: 978-1-4503-6448-5 (electronic)OAI: oai:DiVA.org:liu-152737DiVA, id: diva2:1264211
Conference
13th International Conference on Availability, Reliability and Security, Hamburg, Germany, August 27 - 30, 2018
Available from: 2018-11-19 Created: 2018-11-19 Last updated: 2019-08-19
In thesis
1. Scalable Dynamic Analysis of Binary Code
Open this publication in new window or tab >>Scalable Dynamic Analysis of Binary Code
2019 (English)Doctoral thesis, comprehensive summary (Other academic)
Abstract [en]

In recent years, binary code analysis, i.e., applying program analysis directly at the machine code level, has become an increasingly important topic of study. This is driven to a large extent by the information security community, where security auditing of closed-source software and analysis of malware are important applications. Since most of the high-level semantics of the original source code are lost upon compilation to executable code, static analysis is intractable for, e.g., fine-grained information flow analysis of binary code. Dynamic analysis, however, does not suffer in the same way from reduced accuracy in the absence of high-level semantics, and is therefore also more readily applicable to binary code. Since fine-grained dynamic analysis often requires recording detailed information about every instruction execution, scalability can become a significant challenge. In this thesis, we address the scalability challenges of two powerful dynamic analysis methods whose widespread use has, so far, been impeded by their lack of scalability: dynamic slicing and instruction trace alignment. Dynamic slicing provides fine-grained information about dependencies between individual instructions, and can be used both as a powerful debugging aid and as a foundation for other dynamic analysis techniques. Instruction trace alignment provides a means for comparing executions of two similar programs and has important applications in, e.g., malware analysis, security auditing, and plagiarism detection. We also apply our work on scalable dynamic analysis in two novel approaches to improve fuzzing — a popular random testing technique that is widely used in industry to discover security vulnerabilities.

To use dynamic slicing, detailed information about a program execution must first be recorded. Since the amount of information is often too large to fit in main memory, existing dynamic slicing methods apply various time-versus-space trade-offs to reduce memory requirements. However, these trade-offs result in very high time overheads, limiting the usefulness of dynamic slicing in practice. In this thesis, we show that the speed of dynamic slicing can be greatly improved by carefully designing data structures and algorithms to exploit temporal locality of programs. This allows avoidance of the expensive trade-offs used in earlier methods by accessing recorded runtime information directly from secondary storage without significant random-access overhead. In addition to being a standalone contribution, scalable dynamic slicing also forms integral parts of our contributions to fuzzing. Our first contribution uses dynamic slicing and binary code mutation to automatically turn an existing executable into a test generator. In our experiments, this new approach to fuzzing achieved about an order of magnitude better code coverage than traditional mutational fuzzing and found several bugs in popular Linux software. The second work on fuzzing presented in this thesis uses dynamic slicing to accelerate the state-of-the-art fuzzer AFL by focusing the fuzzing effort on previously unexplored parts of the input space.

For the second dynamic analysis technique whose scalability we sought to improve — instruction trace alignment — we employed techniques used in speech recognition and information retrieval to design what is, to the best of our knowledge, the first general approach to aligning realistically long program traces. We show in our experiments that this method is capable of producing meaningful alignments even in the presence of significant syntactic differences stemming from, for example, the use of different compilers or optimization levels.

Place, publisher, year, edition, pages
Linköping: Linköping University Electronic Press, 2019. p. 73
Series
Linköping Studies in Science and Technology. Dissertations, ISSN 0345-7524 ; 1993
National Category
Computer Sciences
Identifiers
urn:nbn:se:liu:diva-157626 (URN)10.3384/diss.diva-157626 (DOI)9789176850497 (ISBN)
Public defence
2019-09-25, Planck, Hus F, Campus Valla, Linköping, 13:15 (English)
Opponent
Supervisors
Funder
CUGS (National Graduate School in Computer Science)ELLIIT - The Linköping‐Lund Initiative on IT and Mobile Communications
Available from: 2019-08-22 Created: 2019-08-16 Last updated: 2019-08-22Bibliographically approved

Open Access in DiVA

No full text in DiVA

Other links

Publisher's full text

Search in DiVA

By author/editor
Kargén, UlfShahmehri, Nahid
By organisation
Database and information techniquesFaculty of Science & Engineering
Computer Sciences

Search outside of DiVA

GoogleGoogle Scholar

doi
isbn
urn-nbn

Altmetric score

doi
isbn
urn-nbn
Total: 36 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf