Boon Thau Loo

Lan Lu, Peiqi Yin, Isaac Yang et al.

Graph-based ANNS algorithms have gained increasing research interest and market adoption due to their efficiency and accuracy in retrieval. Existing approaches primarily rely on CPUs for graph index construction and retrieval, but this often requires significant time, especially for large-scale and high-dimensional datasets. Some studies have explored GPU-based solutions. However, GPUs are costly and their limited memory makes handling large datasets challenging. In this paper, we propose a novel end-to-end system ScaleGANN that enables users to efficiently construct graph indexes for large-scale, high-dimensional datasets by leveraging low-cost spot GPU resources in a distributed cloud system. ScaleGANN utilized the idea of divide-and-merge, with an optimized vector partitioning algorithm to further improve the indexing time and space efficiency while guaranteeing good index quality. Its novel resource allocation strategy realized multi-GPU indexing parallelism and overall cost-effectiveness for both build and query. Besides, we designed a task scheduler and cost model for better spot instance management and evaluation. We tested our system on large real-world datasets. Experiment results show that our approach can significantly accelerate the index build time to up to 9x times at even 6x lower price compared with the state-of-the-art extendable ANNS benchmark DiskANN.

Lei Shi, Yuepeng Wang, Rajeev Alur et al.

Debugging imperative network programs is a challenging task for developers because understanding various network modules and complicated data structures is typically time-consuming. To address the challenge, this paper presents an automated technique for repairing network programs from unit tests. Specifically, given as input a faulty network program and a set of unit tests, our approach localizes the fault through symbolic reasoning, and synthesizes a patch such that the repaired program can pass all unit tests. It applies domain-specific abstraction to simplify network data structures and utilizes modular analysis to facilitate function summary reuse for symbolic analysis. We implement the proposed techniques in a tool called NetRep and evaluate it on 10 benchmarks adapted from real-world software-defined networking controllers. The evaluation results demonstrate the effectiveness and efficiency of NetRep for repairing network programs.

Lei Shi, Yahui Li, Rajeev Alur et al.

Writing classification rules to identify malicious network traffic is a time-consuming and error-prone task. Learning-based classification systems automatically extract such rules from positive and negative traffic examples. However, due to limitations in the representation of network traffic and the learning strategy, these systems lack both expressiveness to cover a range of attacks and interpretability in fully describing the attack traffic's structure at the session layer. This paper presents Sharingan system, which uses program synthesis techniques to generate network classification programs at the session layer. Sharingan accepts raw network traces as inputs, and reports potential patterns of the attack traffic in NetQRE, a domain specific language designed for specifying session-layer quantitative properties. Using Sharingan, network operators can better analyze the attack pattern due to the following advantages of Sharingan's learning process: (1) it requires minimal feature engineering, (2) it is amenable to efficient implementation of the learnt classifier, and (3) the synthesized program is easy to decipher and edit. We develop a range of novel optimizations that reduce the synthesis time for large and complex tasks to a matter of minutes. Our experiments show that Sharingan is able to correctly identify attacks from a diverse set of network attack traces and generates explainable outputs, while achieving accuracy comparable to state-of-the-art learning-based intrusion detection systems.