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

Direct link
BETA
Kargén, Ulf
Publications (4 of 4) Show all publications
Kargén, U. (2019). Scalable Dynamic Analysis of Binary Code. (Doctoral dissertation). Linköping: Linköping University Electronic Press
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
Kargén, U. & Shahmehri, N. (2015). Turning programs against each other: high coverage fuzz-testing using binary-code mutation and dynamic slicing. In: 2015 10TH JOINT MEETING OF THE EUROPEAN SOFTWARE ENGINEERING CONFERENCE AND THE ACM SIGSOFT SYMPOSIUM ON THE FOUNDATIONS OF SOFTWARE ENGINEERING (ESEC/FSE 2015) PROCEEDINGS: . Paper presented at 10th Joint Meeting on Foundations of Software Engineering (pp. 782-792). New York, NY, USA: Association for Computing Machinery (ACM)
Open this publication in new window or tab >>Turning programs against each other: high coverage fuzz-testing using binary-code mutation and dynamic slicing
2015 (English)In: 2015 10TH JOINT MEETING OF THE EUROPEAN SOFTWARE ENGINEERING CONFERENCE AND THE ACM SIGSOFT SYMPOSIUM ON THE FOUNDATIONS OF SOFTWARE ENGINEERING (ESEC/FSE 2015) PROCEEDINGS, New York, NY, USA: Association for Computing Machinery (ACM), 2015, p. 782-792Conference paper, Published paper (Refereed)
Abstract [en]

Mutation-based fuzzing is a popular and widely employed black-box testing technique for finding security and robustness bugs in software. It owes much of its success to its simplicity; a well-formed seed input is mutated, e.g. through random bit-flipping, to produce test inputs. While reducing the need for human effort, and enabling security testing even of closed-source programs with undocumented input formats, the simplicity of mutation-based fuzzing comes at the cost of poor code coverage. Often millions of iterations are needed, and the results are highly dependent on configuration parameters and the choice of seed inputs. In this paper we propose a novel method for automated generation of high-coverage test cases for robustness testing. Our method is based on the observation that, even for closed-source programs with proprietary input formats, an implementation that can generate well-formed inputs to the program is typically available. By systematically mutating the program code of such generating programs, we leverage information about the input format encoded in the generating program to produce high-coverage test inputs, capable of reaching deep states in the program under test. Our method works entirely at the machine-code level, enabling use-cases similar to traditional black-box fuzzing. We have implemented the method in our tool MutaGen, and evaluated it on 7 popular Linux programs. We found that, for most programs, our method improves code coverage by one order of magnitude or more, compared to two well-known mutation-based fuzzers. We also found a total of 8 unique bugs.

Place, publisher, year, edition, pages
New York, NY, USA: Association for Computing Machinery (ACM), 2015
Keywords
Fuzz testing, fuzzing, black-box, dynamic slicing, program mutation
National Category
Computer Sciences
Identifiers
urn:nbn:se:liu:diva-128810 (URN)10.1145/2786805.2786844 (DOI)000382568700067 ()978-1-4503-3675-8 (ISBN)
Conference
10th Joint Meeting on Foundations of Software Engineering
Available from: 2016-05-31 Created: 2016-05-31 Last updated: 2019-08-16
Kargén, U. & Shahmehri, N. (2014). Efficient Utilization of Secondary Storage for Scalable Dynamic Slicing. In: Randall Bilof (Ed.), Proceedings of the 2014 IEEE 14th International Working Conference on Source Code Analysis and Manipulation: . Paper presented at 14th IEEE International Working Conference on Source Code Analysis and Manipulation, Victoria, British Columbia, Canada, September 28-29, 2014 (pp. 155-164). IEEE
Open this publication in new window or tab >>Efficient Utilization of Secondary Storage for Scalable Dynamic Slicing
2014 (English)In: Proceedings of the 2014 IEEE 14th International Working Conference on Source Code Analysis and Manipulation / [ed] Randall Bilof, IEEE , 2014, p. 155-164Conference paper, Published paper (Refereed)
Abstract [en]

Dynamic program slicing is widely recognized as a powerful aid for e.g. Program comprehension during debugging. However, its widespread use has been impeded in part by scalability issues that occur when constructing the dynamic dependence graph necessary to compute dynamic slices. A few seconds of execution time on a modern CPU can easily yield dynamic dependence graphs on the order of tens of gigabytes in size. Existing methods either produce imprecise slices, incur large time overheads during slice computation, or run out of memory for long program executions. By carefully designing our method to take advantage of locality, we are able to efficiently use secondary storage for dynamic dependence graphs, thus allowing our method to scale to long program executions. Our prototype implementation runs directly on x86 executables, eliminating problems with e.g. Binary-only libraries. We show in our experiments that graphs can be constructed for program runs with billions of executed instructions, at slowdowns ranging from 62x to 173x. Our optimized format also allows graphs to be traversed at speeds of several million dependence edges per second.

Place, publisher, year, edition, pages
IEEE, 2014
Keywords
binary analysis, debugging, dynamic dependence graph, dynamic slicing, x86
National Category
Computer Sciences
Identifiers
urn:nbn:se:liu:diva-117289 (URN)10.1109/SCAM.2014.24 (DOI)000358876700020 ()978-0-7695-5304-7 (ISBN)
Conference
14th IEEE International Working Conference on Source Code Analysis and Manipulation, Victoria, British Columbia, Canada, September 28-29, 2014
Available from: 2015-04-22 Created: 2015-04-22 Last updated: 2019-08-16
Kargén, U. & Shahmehri, N. (2012). InputTracer: A Data-flow Analysis Tool for Manual Program Comprehension of x86 Binaries. In: Juan E. Guerrero (Ed.), Proceedings of the 2012 IEEE 12th International Working Conference on Source Code Analysis and Manipulation: . Paper presented at 12th IEEE International Working Conference on Source Code Analysis and Manipulation, Riva del Garda, Trento, Italy, September 23-24, 2012 (pp. 138-143). IEEE
Open this publication in new window or tab >>InputTracer: A Data-flow Analysis Tool for Manual Program Comprehension of x86 Binaries
2012 (English)In: Proceedings of the 2012 IEEE 12th International Working Conference on Source Code Analysis and Manipulation / [ed] Juan E. Guerrero, IEEE , 2012, p. 138-143Conference paper, Published paper (Refereed)
Abstract [en]

Third-party security analysis of closed-source programs has become an important part of a defense-in-depth approach to software security for many companies. In the absence of efficient tools, the analysis has generally been performed through manual reverse engineering of the machine code. As reverse engineering is an extremely time-consuming and costly task, much research has been performed to develop more powerful methods for analysis of program binaries. One such popular method is dynamic taint analysis (DTA), which is a type of runtime data-flow analysis, where certain input data is marked as tainted. By tracking the flow of tainted data, DTA can, for instance, be used to determine which computations in a program are affected by a certain part of the input. In this paper we present InputTracer, a tool that utilizes DTA for aiding in manual program comprehension and analysis of unmodified x86 executables running in Linux. A brief overview of dynamic taint analysis is given, followed by a description of the tool and its implementation. We also demonstrate the tool’s ability to provide exact information on the origin of tainted data through a detailed use case, where the tool is used to find the root cause of a memory corruption bug.

Place, publisher, year, edition, pages
IEEE, 2012
Keywords
dynamic taint analysis, binary analysis, x86, program comprehension, Valgrind
National Category
Computer Sciences
Identifiers
urn:nbn:se:liu:diva-80317 (URN)10.1109/SCAM.2012.16 (DOI)978-1-4673-2398-7 (ISBN)
Conference
12th IEEE International Working Conference on Source Code Analysis and Manipulation, Riva del Garda, Trento, Italy, September 23-24, 2012
Available from: 2012-08-23 Created: 2012-08-23 Last updated: 2018-01-12
Organisations

Search in DiVA

Show all publications