Enhancing Line-Range Queries for Multi-Variant Patch Filtering in Rust

• Typ der Arbeit: Bachelorarbeit
• Status der Arbeit: in Planung
• Projekte: CADOS
• Betreuer: Tobias Landsberg, Daniel Lohmann

Deploying software updates is a costly endeavor for both vendors and customers. Each update requires building, testing and possibly verifying the software on the vendor's end. For the customer, an update may result in a disruption of service with all its costs. In practice, this is one of the reasons for "patch gaps." In an environment of statically configurable software, where each customer has its specific configuration resulting in its own variant, the costs scale with the number of customers.

To improve the situation, for each variant, we store the actually used lines of the source code in an interval tree. When a patch is made available, we compare the changed lines against the used ones. If a patch only modifies unused lines, we can ignore it. However, currently, each variant has its own interval tree resulting in a linear complexity for the comparison and in conceivably storing redundant data.

The goal of this thesis is to fix these problems. One approach would be designing a multi-variant interval tree. Instead of a lookup resulting in information on whether a given line is used, it would provide a list of affected variants. This requires modifying and profiling the existing code base which is why knowledge of the Rust programming language is strongly recommended.