Nowadays VANETs are being used to ensure road safety and reduce traffic congestion. Vehicles exchange real time position with one another through basic safety messages and these periodic updates must be authenticated for safety purpose. Malicious vehicles can broadcast spoofed position and such an insider attack cannot be dealt with cryptography and digital signature. However, previous machine learning-based approaches that used distributed data-centric misbehaviour detection schemes could detect such attacks in most of the scenarios. However, in case of smarter attacks in a sparse network (where the attacker vehicle pretend to be stand still even though it is on the move), previous solutions could not always detect such attacks. We propose a novel detection scheme which outperforms previously published methods in this specific scenario. For evaluating the performance of this approach, we have used VeReMi dataset, a public repository for the malicious node detection in VANETs. We combine three consecutive basic safety messages and surpass currently existing methods in detecting eventual stop attacks, especially in sparse networks. Our proposed method can help in securing VANET, thereby preventing fatal accidents.

Abstract A graph $G = (V,E)$ is called a pairwise compatibility graph (PCG) if it admits a tuple $(T, d_{min},d_{max})$ of an edge-weighted tree $T$ of non-negative edge weights with leaf set $L$, two non-negative real numbers $d_{min} \leq d_{max}$ such that each vertex $u^{\prime} \in V$ represents a leaf $u \in L$ and $G$ has an edge $(u^{\prime},v^{\prime}) \in E$ if and only if the distance between the two leaves $u$ and $v$ in the tree $T$ lies within interval $[d_{min}, d_{max}]$. It has been proven that not all graphs are PCGs. A graph $G$ is called a $k$-interval PCG if there exists an edge-weighted tree $T$ and $k$ mutually exclusive intervals of non-negative real numbers such that there is an edge between two vertices in $G$ if and only if the distance between their corresponding leaves in $T$ lies within any of the $k$ intervals. It is known that every graph $G$ is a $k$-interval PCG for $k=|E|$, where $E$ is the set of edges of $G$. It is thus interesting to know the smallest value of $k$ for which $G$ is a $k$-interval PCG. In this paper, we show that grid graphs and a subclass of $3$D grid graphs are $2$-interval PCGs.