The Maximum τ‐Persistent Bipartition Problem: An Optimization Approach for Intrusion Detection in Heterogeneous In‐Vehicle Networks

ABSTRACT

The vulnerability of in‐vehicle communication networks to cyber threats has turned intrusion detection into a core research priority. Analyzing temporal communication patterns offers a powerful solution, given that normal vehicle operations rely on highly predictable, quasi‐periodic message exchanges. Consequently, any deviation from these regularities provides a reliable indicator of anomalous or malicious activity. Building on this observation, we propose a new approach that combines temporal analysis with a structural representation of network interactions. Specifically, we model interactions between electronic control units (ECUs) as a temporal graph , where nodes represent ECUs and time‐dependent edges capture communication patterns inferred from observed traffic. This representation enables the joint analysis of temporal and structural properties of the system. We observe that Denial of Service or flooding attack scenarios induce structured interaction patterns that can be naturally interpreted as bipartite graphs, where a set of compromised nodes systematically communicates with a distinct set of target nodes. Such persistent and asymmetric communication behaviors deviate from normal operation and provide a structural signature of malicious activity. Motivated by this insight, we introduce the maximum ‐persistent bipartition problem , an optimization problem that identifies a maximum‐cardinality bipartite subgraph that persists for at least timestamps in the temporal graph. We model it using integer programming and solve it through the state‐of‐the‐art solver Gurobi. Experiments on real in‐vehicle instances show that the method effectively detects attacks that directly affect communication timing, while experiments on synthetic temporal graphs compare the proposed approach with a degree‐based baseline and assess its computational scalability.