Basel Alomair

Andrew Clark, Phillip Lee, Basel Alomair et al.

Biological processes, including cell differentiation, organism development, and disease progression, can be interpreted as attractors (fixed points or limit cycles) of an underlying networked dynamical system. In this paper, we study the problem of computing a minimum-size subset of control nodes that can be used to steer a given biological network towards a desired attractor, when the networked system has Boolean dynamics. We first prove that this problem cannot be approximated to any nontrivial factor unless P=NP. We then formulate a sufficient condition and prove that the sufficient condition is equivalent to a target set selection problem, which can be solved using integer linear programming. Furthermore, we show that structural properties of biological networks can be exploited to reduce the computational complexity. We prove that when the network nodes have threshold dynamics and certain topological structures, such as block cactus topology and hierarchical organization, the input selection problem can be solved or approximated in polynomial time. For networks with nested canalyzing dynamics, we propose polynomial-time algorithms that are within a polylogarithmic bound of the global optimum. We validate our approach through numerical study on real-world gene regulatory networks.

Andrew Clark, Basel Alomair, Linda Bushnell et al.

We consider random walks in which the walk originates in one set of nodes and then continues until it reaches one or more nodes in a target set. The time required for the walk to reach the target set is of interest in understanding the convergence of Markov processes, as well as applications in control, machine learning, and social sciences. In this paper, we investigate the computational structure of the random walk times as a function of the set of target nodes, and find that the commute, hitting, and cover times all exhibit submodular structure, even in non-stationary random walks. We provide a unifying proof of this structure by considering each of these times as special cases of stopping times. We generalize our framework to walks in which the transition probabilities and target sets are jointly chosen to minimize the travel times, leading to polynomial-time approximation algorithms for choosing target sets. Our results are validated through numerical study.

Yuetai Li, Yichen Feng, Zhangchen Xu et al.

Current benchmarks for occupational AI agents are scoped primarily by economic values, telling a replacement story. We introduce JobBench, which evaluates AI agents on the workflows that experts identify as high-priority for delegation, empowering humans based on their needs instead of replacing them with GDP value. JobBench covers 130 agentic tasks across 35 occupations. Each task is packaged as a workspace of heterogeneous reference files, requiring the agent to reason through the cluttered information streams of real professional work. Outputs are graded by a fact-anchored chain of rubrics, averaging 35.6 binary criteria per task. We evaluate 36 models; the strongest, Claude Opus~4.7 under Claude Code, reaches only 45.9 %. We hope JobBench shifts the community's target labour-market effect from replacement to enhancement: building agents that do what humans actually want delegated, not only what is most economically valuable.

Andrew Clark, Basel Alomair, Linda Bushnell et al.

Networked systems are systems of interconnected components, in which the dynamics of each component are influenced by the behavior of neighboring components. Examples of networked systems include biological networks, critical infrastructures such as power grids, transportation systems, and the Internet, and social networks. The growing importance of such systems has led to an interest in control of networks to ensure performance, stability, robustness, and resilience. A widely-studied method for controlling networked systems is to directly control a subset of input nodes, which then steer the remaining nodes to their desired states. This article presents submodular optimization approaches for input node selection in networked systems. Submodularity is a property of set functions that enables the development of computationally tractable algorithms with provable optimality bounds. For a variety of physically relevant systems, the physical dynamics have submodular structures that can be exploited to develop efficient input selection algorithms. This article will describe these structures and the resulting algorithms, as well as discuss open problems.

Yuetai Li, Fengqing Jiang, Yichen Feng et al.

Many online decision problems over combinatorial actions are addressed via convex relaxations, leading to online convex optimization with piecewise linear objectives and induced polyhedral structure. We show that regret in such problems is governed by \emph{polyhedral instability}: the number of changes of the active region. Under full information feedback and fixed partition assumptions, if $\mathrm{RS}_T$ denotes the number of region switches and $V_{\max}$ the maximum number of vertices per region, we prove $\Regret_T= Θ(\sqrt{(1+\mathrm{RS}_T)\,T\,\log V_{\max}})$ interpolating between experts-like and dimension-dependent OCO rates. For online submodular--concave games under Lovász convexification, this reduces to the permutation-switch count $\mathrm{SC}_T$, yielding the matching rate $\Regret_T= Θ(\sqrt{(1+\mathrm{SC}_T)\,T\,\log n})$. Experiments on synthetic and real combinatorial problems (shortest path, influence maximization) validate the predicted scaling and indicate that low-instability regimes can arise in practice without explicit enumeration of actions.

Fengqing Jiang, Yuetai Li, Yichen Feng et al.

Hypergraphs provide a natural framework to model higher-order interactions in scientific, social, and biological systems. Hypergraph neural networks (HGNNs) aim to learn from such data, yet it remains unclear which higher-order structures these models can represent. We show that hypergraph expressivity is governed by which small patterns an architecture can detect and count. We formalize this via homomorphism densities, which measure how often a structural motif appears in a hypergraph. Combining classical homomorphism-count completeness with invariant approximation, we show that homomorphism densities generate all continuous hypergraph invariants and organize them into a strict hierarchy indexed by hypertree width. This yields a Width Wall: a fundamental architectural limit beyond which no hidden dimension, training procedure or fixed-depth HGNN can represent invariants requiring wider patterns. Our framework provides a unified characterization of 15 HGNN architectures, precisely identifies information lost by clique expansion, and motivates density-aware models that extend expressivity beyond bounded-width message passing. We experimentally validate this finding on an APPLICATION NODE CLASSIFICATION SUITE of real-world hypergraphs, where the Width Wall predicts when graph-reduction baselines fail and when density features help.

Julien Piet, Maha Alrashed, Chawin Sitawarin et al. · pku

Large Language Models (LLMs) are attracting significant research attention due to their instruction-following abilities, allowing users and developers to leverage LLMs for a variety of tasks. However, LLMs are vulnerable to prompt-injection attacks: a class of attacks that hijack the model's instruction-following abilities, changing responses to prompts to undesired, possibly malicious ones. In this work, we introduce Jatmo, a method for generating task-specific models resilient to prompt-injection attacks. Jatmo leverages the fact that LLMs can only follow instructions once they have undergone instruction tuning. It harnesses a teacher instruction-tuned model to generate a task-specific dataset, which is then used to fine-tune a base model (i.e., a non-instruction-tuned model). Jatmo only needs a task prompt and a dataset of inputs for the task: it uses the teacher model to generate outputs. For situations with no pre-existing datasets, Jatmo can use a single example, or in some cases none at all, to produce a fully synthetic dataset. Our experiments on seven tasks show that Jatmo models provide similar quality of outputs on their specific task as standard LLMs, while being resilient to prompt injections. The best attacks succeeded in less than 0.5% of cases against our models, versus 87% success rate against GPT-3.5-Turbo. We release Jatmo at https://github.com/wagner-group/prompt-injection-defense.

Zhanhao Hu, Xiao Huang, Patrick Mendoza et al.

Large Language Models (LLMs) pose a significant risk of safety misalignment after finetuning, as models can be compromised by both explicitly and implicitly harmful data. Even some seemingly benign data can inadvertently steer a model towards misaligned behaviors. To address this, we introduce GradShield, a principled filtering method that safeguards LLMs during finetuning by identifying and removing harmful data points before they corrupt the model's alignment. It removes potentially harmful data by computing a Finetuning Implicit Harmfulness Score (FIHS) for each data point and employs an adaptive thresholding algorithm. We apply GradShield to multiple utility fine-tuning tasks across varying levels of harmful data and evaluate the safety and utility performance of the resulting LLMs using various metrics. The results show that GradShield outperforms all baseline methods, consistently maintaining an Attack Success Rate (ASR) below $6\%$ while preserving utility performance.

Yangruibo Ding, Yanjun Fu, Omniyyah Ibrahim et al.

In the context of the rising interest in code language models (code LMs) and vulnerability detection, we study the effectiveness of code LMs for detecting vulnerabilities. Our analysis reveals significant shortcomings in existing vulnerability datasets, including poor data quality, low label accuracy, and high duplication rates, leading to unreliable model performance in realistic vulnerability detection scenarios. Additionally, the evaluation methods used with these datasets are not representative of real-world vulnerability detection. To address these challenges, we introduce PrimeVul, a new dataset for training and evaluating code LMs for vulnerability detection. PrimeVul incorporates a novel set of data labeling techniques that achieve comparable label accuracy to human-verified benchmarks while significantly expanding the dataset. It also implements a rigorous data de-duplication and chronological data splitting strategy to mitigate data leakage issues, alongside introducing more realistic evaluation metrics and settings. This comprehensive approach aims to provide a more accurate assessment of code LMs' performance in real-world conditions. Evaluating code LMs on PrimeVul reveals that existing benchmarks significantly overestimate the performance of these models. For instance, a state-of-the-art 7B model scored 68.26% F1 on BigVul but only 3.09% F1 on PrimeVul. Attempts to improve performance through advanced training techniques and larger models like GPT-3.5 and GPT-4 were unsuccessful, with results akin to random guessing in the most stringent settings. These findings underscore the considerable gap between current capabilities and the practical requirements for deploying code LMs in security roles, highlighting the need for more innovative research in this domain.

Tianneng Shi, Kaijie Zhu, Zhun Wang et al. · berkeley

Despite their potential, recent research has demonstrated that LLM agents are vulnerable to prompt injection attacks, where malicious prompts are injected into the agent's input, causing it to perform an attacker-specified task rather than the intended task provided by the user. In this paper, we present PromptArmor, a simple yet effective defense against prompt injection attacks. Specifically, PromptArmor prompts an off-the-shelf LLM to detect and remove potential injected prompts from the input before the agent processes it. Our results show that PromptArmor can accurately identify and remove injected prompts. For example, using GPT-4o, GPT-4.1, or o4-mini, PromptArmor achieves both a false positive rate and a false negative rate below 1% on the AgentDojo benchmark. Moreover, after removing injected prompts with PromptArmor, the attack success rate drops to below 1%. We also demonstrate PromptArmor's effectiveness against adaptive attacks and explore different strategies for prompting an LLM. We recommend that PromptArmor be adopted as a standard baseline for evaluating new defenses against prompt injection attacks.

Aidan Wen, Norah A. Alzahrani, Jingzhi Jiang et al.

We introduce SeedAIchemy, an automated LLM-driven corpus generation tool that makes it easier for developers to implement fuzzing effectively. SeedAIchemy consists of five modules which implement different approaches at collecting publicly available files from the internet. Four of the five modules use large language model (LLM) workflows to construct search terms designed to maximize corpus quality. Corpora generated by SeedAIchemy perform significantly better than a naive corpus and similarly to a manually-curated corpus on a diverse range of target programs and libraries.

Fengqing Jiang, Yichen Feng, Yuetai Li et al.

The convergence of LLM-powered research assistants and AI-based peer review systems creates a critical vulnerability: fully automated publication loops where AI-generated research is evaluated by AI reviewers without human oversight. We investigate this through \textbf{BadScientist}, a framework that evaluates whether fabrication-oriented paper generation agents can deceive multi-model LLM review systems. Our generator employs presentation-manipulation strategies requiring no real experiments. We develop a rigorous evaluation framework with formal error guarantees (concentration bounds and calibration analysis), calibrated on real data. Our results reveal systematic vulnerabilities: fabricated papers achieve acceptance rates up to . Critically, we identify \textit{concern-acceptance conflict} -- reviewers frequently flag integrity issues yet assign acceptance-level scores. Our mitigation strategies show only marginal improvements, with detection accuracy barely exceeding random chance. Despite provably sound aggregation mathematics, integrity checking systematically fails, exposing fundamental limitations in current AI-driven review systems and underscoring the urgent need for defense-in-depth safeguards in scientific publishing.

Phillip Lee, Andrew Clark, Basel Alomair et al.

Malware propagation poses a growing threat to networked systems such as computer networks and cyber-physical systems. Current approaches to defending against malware propagation are based on patching or filtering susceptible nodes at a fixed rate. When the propagation dynamics are unknown or uncertain, however, the static rate that is chosen may be either insufficient to remove all viruses or too high, incurring additional performance cost. In this paper, we formulate adaptive strategies for mitigating multiple malware epidemics when the propagation rate is unknown, using patching and filtering-based defense mechanisms. In order to identify conditions for ensuring that all viruses are asymptotically removed, we show that the malware propagation, patching, and filtering processes can be modeled as coupled passive dynamical systems. We prove that the patching rate required to remove all viruses is bounded above by the passivity index of the coupled system, and formulate the problem of selecting the minimum-cost mitigation strategy. Our results are evaluated through numerical study.

Andrew Clark, Basel Alomair, Linda Bushnell et al.

Synchronization underlies phenomena including memory and perception in the brain, coordinated motion of animal flocks, and stability of the power grid. These synchronization phenomena are often modeled through networks of phase-coupled oscillating nodes. Heterogeneity in the node dynamics, however, may prevent such networks from achieving the required level of synchronization. In order to guarantee synchronization, external inputs can be used to pin a subset of nodes to a reference frequency, while the remaining nodes are steered toward synchronization via local coupling. In this paper, we present a submodular optimization framework for selecting a set of nodes to act as external inputs in order to achieve synchronization from almost any initial network state. We derive threshold-based sufficient conditions for synchronization, and then prove that these conditions are equivalent to connectivity of a class of augmented network graphs. Based on this connection, we map the sufficient conditions for synchronization to constraints on submodular functions, leading to efficient algorithms with provable optimality bounds for selecting input nodes. We illustrate our approach via numerical studies of synchronization in networks from power systems, wireless networks, and neuronal networks.