Routers, relying on routing protocols to determine how data packets travel across the Internet, serve as the backbone of modern networks. Vulnerable routing protocols can lead to serious consequences, including data leaks and network congestion. This work focuses on validating the implementation of a key class of routing protocols known as Interior Gateway Protocols (IGPs). Unlike communication protocols such as TCP/IP, which define structured data packets and state machines to facilitate communication, IGPs are designed to automatically manage the network topology. Thus, conventional techniques, which primarily focus on communication correctness, cannot be applied directly to IGPs. We propose ToDiff, a differential validation technique to uncover IGP bugs in three steps: (1) it uses a network generation algorithm to create random yet valid IGP networks, (2) it applies a semantics-guided program synthesizer to generate equivalent topological programs, and (3) it simulates the network via the equivalent topological programs, with any discrepancies suggesting the presence of a potential bug. We have evaluated ToDiff on the implementation of two common IGP protocols, OSPF and IS-IS. The results demonstrate that ToDiff outperforms existing approaches. To date, our tool has successfully identified 26 bugs, all confirmed or fixed by developers.

When proving to a third party that a software system is free from critical memory bugs, software vendors often face the problem of having to reveal their source code, so that the third party can scan the source code using static analysis tools. However, such transparency poses a significant threat to vendors, as the source code typically contains proprietary algorithms, core technical innovations, or trade secrets, exposing them to potential intellectual property risks. In this paper, we present a solution that offers a balance between transparency and code privacy, allowing software vendors to provide minimal source code information while justifying the sufficiency of bug detection. To this end, we propose DIReducer, which reduces source code information, a.k.a. debug information, from non-stripped binaries while preserving its utility for memory bug detection. DIReducer consists of two components: selective pruning and type minimization. The former eliminates redundant debug information, and the latter is proven to be NP-hard and minimizes type-related debug information by reducing it to the classic set-cover problem, which offers a near-optimal solution. Experimental results show that we can reduce 95% of debug information while maintaining similar bug detection capability compared to using full debug information or the source code.

Butterfly (a cyclic graph motif) counting is a fundamental task with many applications in graph analysis, which aims at computing the number of butterflies in a large graph. With the rapid growth of graph data, it is more and more challenging to do butterfly counting due to the super-linear time complexity and large memory consumption. In this paper, we study I/O-efficient algorithms for doing butterfly counting on hierarchical memory. Existing algorithms of the kind cannot guarantee I/O optimality. Observing that in order to count butterflies, it suffices to "witness" a subgraph instead of the whole structure, a new class of algorithms called semi-witnessing algorithm is proposed. We prove that a semi-witnessing algorithm is not restricted by the lower bound Ømega(|E|2/MB) of a witnessing algorithm, and give a new bound of Ømega(min(|E|2/MB, |E|/|V| √M B)). We further develop the IOBufs algorithm that manages to approach the I/O lower bound, and thus claim its optimality. Finally, we make efforts to parallelize IOBufs to further improve the performance and scalability. We show in the experiment that IOBufs significantly outperforms the state-of-the-art algorithms EMRC and BFC-EM. In addition, IOBufs can scale to conducting butterfly counting on the Clueweb graph with 37 billion edges and quintillions (10^18 ) of butterflies.