IEEE Consumer Electronics Magazine - January/February 2022 - 53

by monitoring them with a controlled vehicle.
Our approach differs by abstracting the signals
encoded in the data frames and instead focusing
on the relationship between sets of frames in
time to identify which messages correspond to
the vehicle functions in a manner that does not
require any special equipment and can be done
without controlled vehicle experimentation or
substantial automotive expertise.
CLUSTER-BASED REVERSE
ENGINEERING
Raw CAN is unlabeled and requires proprietary
information from the manufacturer to
reverse engineer. Our approach to reverse engineer
the relationship between CAN messages
and vehicle functions with low domain expertise
relies on unsupervised machine learning-clustering-to
identify related groups of messages.
Clustering machine learning techniques assume
that instances of a particular class have data
profiles that cluster into centroids. Each new
data point can then be classified according to its
distance from that centroid.
At a high level, our reverse engineering process
involves reading CAN data, calculating the
distances between all CAN IDs, merging nearest
IDs together to form clusters, and using these
clusters to classify unknown CAN IDs. The merging
of clusters and termination of clustering
depends on the specific clustering algorithm
approach. When clustering completes, our
hypothesis is that the merged clusters group the
different CAN messages together by their respective
functions.
We use the Euclidean distance metric by
mapping each message to a point in the x-y
plane based on its timestamp. The CAN ID and
data field are extracted from CAN data frames to
use as features, in addition to the receive timestamp.
This information is available in all CAN
log formats and are standard to all vehicles
regardless of their manufacturer, make, or
model. For all messages, we set the x value to
the origin, so the distance function reduces to
the L1 norm of jy1 y2j, the timestamps of messages
m1 and m2, respectively.
We generate a distance matrix for clustering
by calculating the distance between the last
transmissions of each ID. We smooth the
January/February 2022
distances by applying the arithmetic mean over
the distances calculated in the final 100 transmissions
of a captured CAN log. The distance
matrix then shows the distance between each ID
based on the averaged distance between their
last few transmissions. This matrix is used as
input to the clustering approaches. We use and
compare the following four clustering algorithms
for our approach to reverse engineering.
Agglomerative hierarchical (AH) clustering is
based on k-means clustering. It ensures that two
nearby points are placed in the same cluster. In
our approach, this means that each CAN ID is
assigned as a single cluster and as we iterate
through the IDs and their respective distance
measurements, then CAN ID clusters are merged
starting with the nearest neighbor. The advantage
of this approach is that if certain CAN IDs
have a known function, the functions of
unknown CAN IDs can be determined by their
clustering.
Genetic algorithm (GA) clustering uses randomized
adaptive search heuristics that imitate
the biological process of natural selection. Any
GA starts with a set of randomly generated
states of chromosomes known as the population.
A fitness function that influences the next
generation of states is calculated by measuring
the quality of the clustering for each state. In our
case, each state is a distance metric of a particular
CAN ID from all other CAN IDs. We use a variant
of the GA that requires the user to specify
the number of clusters manually.
Density-based spatial clustering of applications
with noise (DBSCAN) defines a cluster as a
maximal set of density-connected points. The
algorithm requires two parameters: maximum
radius of the neighborhood (Eps) and the minimum
number of points in the Eps neighborhood
of a point (MinPts). We varied Eps from 0 1
with an increment of 0.05 and MinPts from 1 10
with an increment of 1 to find a good parameter
to cluster CAN IDs. We chose DBSCAN because it
helps to discover structures in data that are difficult
to observe.
Expectation maximization clustering with
Gaussian mixture models (EM-GMM) is a type of
soft clustering algorithm in which clusters may
overlap. It starts by assuming that all the data
points are Gaussian distributed. Each cluster
53
IEEE Consumer Electronics Magazine - January/February 2022

Table of Contents for the Digital Edition of IEEE Consumer Electronics Magazine - January/February 2022
