Program Debloating via Multi-Granularity Stochastic Optimization

Code reduction and program generality are two key factors affecting the effectiveness of feature-based debloating. These two factors are inherently in tension: reducing more code typically decreases program generality, and vice versa. Therefore, effective debloating must strike a good tradeoff between them. To this end, a previous technique, D ebop , addresses debloating as an optimization problem. It uses an objective function to quantify, for any debloated program that it generates, the reduction, generality, and their tradeoff, and employs a Markov-Chain-Monte-Carlo-based sampling approach for stochastic optimization, aiming to find the best sample, that is, the debloated program with the highest tradeoff score. Unfortunately, because D ebop uses a very simple mutation model, which reduces or recovers only one primitive statement (often a line of code) for sampling, its search ability is significantly limited, especially when the program is large and in scenarios where code reduction is prioritized over generality. To improve the stochastic search for better debloating, we propose M op , a new optimization-based technique that uses three mutation models targeting different code granularities for sample generation based on the code coverage (derived from the program execution with the feature-characterizing inputs), the coverage segments (exercised by unique subsets of features), and the statements. The use of these models accounts for both static code structure and dynamic program execution for sample generation and enables both aggressive and fine-grained exploration for improved optimization. However, as the optimization is guided by a set of inputs serving as the usage profile, it may mistakenly delete robustness-related code that is not covered by these inputs. Therefore, after the optimization, M op also performs fuzzing-guided code augmentation to enhance the robustness of the optimized program. To assess the effectiveness of M op , we implemented a prototype of the approach and applied it to an existing benchmark of 25 programs and a real-world database management system PostgreSQL for debloating. Our results are encouraging, as they show that M op can produce debloated programs with different tradeoffs and achieve a tradeoff score that is on average 15% (and in many cases 30%) higher than D ebop ’s. We also found that M op ’s code reduction ability is at least comparable to that of the state-of-the-art reduction-oriented techniques and that it can produce robustness-enhanced programs. Overall, the results demonstrate M op ’s improved proficiency for optimization-based debloating.