Graph Optimization and Programming through Interval Reduction: Case for Secure Control Flow Graph Analysis

Abstract

Control Flow Graphs (CFGs) provide a central representation for reasoning about program structure, but their increasing size can limit both manual interpretation and automated analysis. This paper revisits interval-based reduction as a structurally grounded approach to CFG simplification. Based on classical notions of dominance, intervals, and reducibility, we reformulate the reduction process in an explicit algorithmic form and study the structural properties preserved by the resulting derived graphs. The proposed approach is implemented and evaluated on a diverse collection of CFGs, with comparison to Sequential Node Merging as a baseline reduction technique. The results indicate that interval reduction offers a principled way to reduce graph complexity while maintaining the hierarchical organization of control flow, thereby supporting its use in modern program analysis settings, including software security and reliability. Our results guarantee a formal basis for future malware-detection frameworks built upon interval-reduced control-flow graphs.