Search for: All records

We consider the question of speeding up classic graph algorithms with machine-learned predictions. In this model, algorithms are furnished with extra advice learned from past or similar instances. Given the additional information, we aim to improve upon the traditional worst-case run-time guarantees. Our contributions are the following: (i) We give a faster algorithm for minimum-weight bipartite matching via learned duals, improving the recent result by Dinitz, Im, Lavastida, Moseley and Vassilvitskii (NeurIPS, 2021); (ii) We extend the learned dual approach to the single-source shortest path problem (with negative edge lengths), achieving an almost linear runtime given sufficiently accurate predictions which improves upon the classic fastest algorithm due to Goldberg (SIAM J. Comput., 1995); (iii) We provide a general reduction-based framework for learning-based graph algorithms, leading to new algorithms for degree-constrained subgraph and minimum-cost 0-1 flow, based on reductions to bipartite matching and the shortest path problem. Finally, we give a set of general learnability theorems, showing that the predictions required by our algorithms can be efficiently learned in a PAC fashion 

Processors nowadays are consistently equipped with debugging features to facilitate the program analysis. Specifically, the ARM debugging architecture involves a series of CoreSight components and debug registers to aid the system debugging, and a group of debug authentication signals are designed to restrict the usage of these components and registers. Meantime, the security of the debugging features is under-examined since it normally requires physical access to use these features in the traditional debugging model. However, ARM introduces a new debugging model that requires no physical access since ARMv7, which exacerbates our concern on the security of the debugging features. In this paper, we perform a comprehensive security analysis of the ARM debugging features, and summarize the security and vulnerability implications. To understand the impact of the implications, we also investigate a series of ARM-based platforms in different product domains (i.e., development boards, IoT devices, cloud servers, and mobile devices). We consider the analysis and investigation expose a new attacking surface that universally exists in ARM-based platforms. To verify our concern, we further craft Nailgun attack, which obtains sensitive information (e.g., AES encryption key and fingerprint image) and achieves arbitrary payload execution in a high-privilege mode from a low-privilege mode via misusing the debugging features. This attack does not rely on software bugs, and our experiments show that almost all the platforms we investigated are vulnerable to the attack. The potential mitigations are discussed from different perspectives in the ARM ecosystem. 

With the proliferation of using smart and connected devices in the transportation domain, these systems inevitably face security threats from the real world. In this work, we analyze the security of the existing traffic signal systems and summarize the security implications exposed in our analysis. Our research shows that the deployed traffic signal systems can be easily manipulated with physical/remote access and are vulnerable to an array of real-world attacks such as a diversionary tactic. By setting up a standard traffic signal system locally in our lab and partnering with a municipality, we demonstrate that not only can traffic intersections be manipulated to show deadly traffic patterns such as all-direction green lights, but traffic control systems are also susceptible to ransomware and disruption attacks. Through testing and studying these attacks, we provide our security recommendations and mitigations to these threats.