• Login
    View Item 
    •   SMARTech Home
    • Undergraduate Research Opportunities Program (UROP)
    • Undergraduate Research Option Theses
    • View Item
    •   SMARTech Home
    • Undergraduate Research Opportunities Program (UROP)
    • Undergraduate Research Option Theses
    • View Item
    JavaScript is disabled for your browser. Some features of this site may not work without it.

    Chainsaw Before Scalpel: Dependency-Based Pre-processing for Program Reduction

    Thumbnail
    View/Open
    ROUSSKOV-UNDERGRADUATERESEARCHOPTIONTHESIS-2021.pdf (332.1Kb)
    Date
    2021-12
    Author
    Rousskov, Mark
    Metadata
    Show full item record
    Abstract
    Program reduction techniques, which aim to minimize the size of a program, have many applications, including software debloating, debugging, and optimization in general. Therefore, these techniques have been extensively studied for decades. Past work in this area has typically focused on either performing larger, more effective edits (e.g., Delta Debugging, Hierarchical Delta Debugging) or reducing the search space based on a language grammar (e.g., Perses, C-Reduce). Most of these techniques had a primary goal of minimal output size, with reduction speed only as a secondary goal. We propose Chainsaw, a novel approach that improves existing techniques by offloading a subset of the reduction to a pre-processing step. Since Chainsaw does not need to be as thorough as existing reducers, this creates an opportunity to take a new approach which can benefit overall end-to-end performance. Our key insight is that in practical application, a considerable amount of input code is not needed, and dependency analysis enables effective and fast identification of this removable code. This dependency analysis is both general, thus easily applicable to different languages, and inexpensive, thus amenable to a speedy pre-processing step. Such analysis can enable the higher-fidelity techniques previously developed to skip a significant quantity of work and produce better results more quickly. We also present a prototype tool based on our approach. Our tool finds unused sections of code by analyzing the dependencies between items in the input text and is straightforward to implement. We leverage existing analysis tooling via the Language Server Protocol to easily identify dependencies. Our initial results are promising and show that our approach is extremely fast and can yield up to twofold end-to-end speed improvement when used as a pre-processor with existing state-of-the-art techniques.
    URI
    http://hdl.handle.net/1853/66260
    Collections
    • School of Computer Science Undergraduate Research Option Theses [205]
    • Undergraduate Research Option Theses [862]

    Browse

    All of SMARTechCommunities & CollectionsDatesAuthorsTitlesSubjectsTypesThis CollectionDatesAuthorsTitlesSubjectsTypes

    My SMARTech

    Login

    Statistics

    View Usage StatisticsView Google Analytics Statistics
    facebook instagram twitter youtube
    • My Account
    • Contact us
    • Directory
    • Campus Map
    • Support/Give
    • Library Accessibility
      • About SMARTech
      • SMARTech Terms of Use
    Georgia Tech Library266 4th Street NW, Atlanta, GA 30332
    404.894.4500
    • Emergency Information
    • Legal and Privacy Information
    • Human Trafficking Notice
    • Accessibility
    • Accountability
    • Accreditation
    • Employment
    © 2020 Georgia Institute of Technology