# Cost-aware Feature Selection for
IoT Device Classification

Biswadeep Chakraborty, Dinil Mon Divakaran, Ido Nevat, Gareth W. Peters, Mohan
Gurusamy Biswadeep Chakraborty<EMAIL_ADDRESS>is with Georgia
Institute of Technology. Dinil Mon Divakaran<EMAIL_ADDRESS>corresponding author) is with Trustwave (Singapore). Ido Nevat (ido.nevat@tum-
create.edu.sg) is with TUMCREATE (Singapore). Gareth W. Peters
<EMAIL_ADDRESS>is with Department of Actuarial Mathematics and
Statistics, Heriot-Watt University (United Kingdom). Mohan Gurusamy
<EMAIL_ADDRESS>is with National University of Singapore (Singapore).

###### Abstract

Classification of IoT devices into different types is of paramount importance,
from multiple perspectives, including security and privacy aspects. Recent
works have explored machine learning techniques for fingerprinting (or
classifying) IoT devices, with promising results. However, existing works have
assumed that the features used for building the machine learning models are
readily available or can be easily extracted from the network traffic; in
other words, they do not consider the costs associated with feature
extraction. In this work, we take a more realistic approach, and argue that
feature extraction has a cost, and the costs are different for different
features. We also take a step forward from the current practice of considering
the misclassification loss as a binary value, and make a case for different
losses based on the misclassification performance. Thereby, and more
importantly, we introduce the notion of risk for IoT device classification. We
define and formulate the problem of cost-aware IoT device classification. This
being a combinatorial optimization problem, we develop a novel algorithm to
solve it in a fast and effective way using the Cross-Entropy (CE) based
stochastic optimization technique. Using traffic of real devices, we
demonstrate the capability of the CE based algorithm in selecting features
with minimal risk of misclassification while keeping the cost for feature
extraction within a specified limit.

##  I Introduction

The rapid growth of the Internet of Things (IoT) market is also having an
impact on the threat landscape of the cyber space [1]. We now have attacks
that compromise large numbers of IoT devices, subsequently using them as bots
for launching different kinds of large-scale attacks (e.g., DDoS attacks) that
result in significant losses [2, 3]. Attackers often explore and exploit
vulnerabilities to gain access to machines. In this IoT era, it is now
possible to exploit a few vulnerabilities of just one device type, and
compromise hundreds of thousands of devices of the same type using the same
exploits.

To detect and prevent attacks on and from IoT devices, one of the important
tasks is to identify the type of devices connected to a network. Device
identification is useful in keeping track of various device types in a
network, which consequently helps in analyzing and defending against potential
vulnerabilities of various IoT devices. In addition, a mitigation
solution—such as blocking devices with newly known vulnerabilities—can be
implemented quickly, if the network administrator knows the identities (brand,
model number, functionality, etc.) of the devices connected to the network.
Recent years have seen research proposals on identifying IoT devices,
particularly by analyzing their network traffic (e.g., see [4, 5, 6] and [7]).
Existing solutions often use machine-learning based approaches to fingerprint
IoT devices, by extracting a number of features from IoT traffic. For
instance, in the case of supervised or semi-supervised approaches (e.g., [8]
and [9]), the features extracted are used to train a classification model to
differentiate IoT devices while in operation.

A common underlying assumption of the device classification works in the
literature is that all features can be easily extracted from the traffic and
that there is no difference—technical or otherwise—in extracting any two
different features. However, we argue that, such an assumption misses out some
important points. Extraction of features from traffic incurs a cost, and
different features have different costs for extraction. We identify three
types of feature-extraction costs:

1\. Computational cost: When network traffic characteristics are used for
classifying devices, the relevant features are computed by reading and
processing traffic at a router, a gateway or a server to which the traffic is
mirrored to. That is, there is cost involved in computing a feature from
packets, and different features may incur different computational costs. For
example, searching for a specific pattern, say, malware signature/hash, in
packets is computationally more expensive than counting the number of packets.

2\. Memory cost: Feature extraction also involves use of memory to store the
(running) value of a feature. For example, storing the number of packets
traversing a link requires just one counter, but to count the number of
packets of each connection that is active at a link requires maintenance of a
hash table or some variants [10]. And memory is an extremely valuable resource
in routers and gateways. Indeed, traditionally ISP routers use sampled NetFlow
[11] to capture and aggregate meta-information of traffic flows, due to
resource constraints at the router. With NetFlow, information which is often
assumed to be easily available (e.g., size of each packet in a connection) is
not collected.

3\. Privacy cost: The third factor that decides the cost of a feature is
privacy. Some features, such as those extracted from payloads of (unencrypted)
network traffic, can reveal sensitive or even confidential information of end-
users [12]. In fact, DNS or even DNS over HTTPS (that is, DNS over encrypted
HTTP connection) can reveal sensitive information related to users
communication [13, 14]. Privacy concerns imply that, either some features
might be unavailable (i.e., cost is infinite) or there would be some cost
incurred to obtain such data, for example by paying for the data with user’s
consent or by anonymizing the data to minimize privacy leak.

Therefore, we argue that, a solution for device identification (or
classification) should take the cost of features into consideration. This in
turn means, the performance of a device classification solution is dependent
on the cost of features used, since the cost may exclude some important
features. A solution developer would need to be conscious of the budget
available for deploying the solution.

Previous works also assume no difference in device misclassification, in that
they were not concerned by the misclassification class to which an incorrect
assignment was made. In practice, not only the fact that a misclassification
took place is important, it is also important to consider which class the
device was misclassified under as this could have ramifications for actions
and costs. Previous works also assume no difference in device
misclassification; i.e., they were not concerned of the type a given device is
being misclassified into. However, such an approach overlooks important
aspects IoT devices. An IoT device, say a camera, might be from vendor X with
model name Y; but the same vendor might have multiple models for the product
camera. Consider the different misclassifications possible: (i) [camera, X, Y]
gets classified as smart bulb, (ii) [camera, X, Y] gets classified as [camera,
A, B], and (iii) [camera, X, Y] gets classified as [camera, X, Z]. Clearly,
the third misclassification is more acceptable than the first two, since the
functionality and brand name were correct; and the first misclassification is
the worst result to have among the three. Therefore, we argue the need to
consider multiple losses due to misclassifications that essentially captures
the differences in misclassifications.

In this work, we address the problem of classifying IoT devices, under the
realistic assumptions that (i) features have associated costs, (ii) a solution
developer has a budget constraint, and (iii) there could be different kinds of
losses due misclassifications. Different from existing works, the challenge
here is to develop a cost-optimal IoT device classification solution with high
accuracy.

Our contributions are the following:

  1. 1.

We introduce the notion of feature cost and budget constraint in the problem
of IoT device classification. Furthermore, going beyond the current way of
treating misclassification as a binary value, we consider multiple losses due
to misclassification (Sec. III-D), and introduce the notion of risk (Sec.
III-E) to evaluate a classifier’s performance. Subsequently, we formulate the
feature-selection problem under constrained budget as an optimization problem
(Section IV).

  2. 2.

We present and develop a cross-entropy (CE) based algorithm (Section V), that
solves the optimization problem efficiently. In comparison to a brute force
approach which has to run a classifier exponential number of times, the number
of executions (of classifier) that the CE algorithm has to run is linear in
its two parameters.

  3. 3.

We conduct extensive experiments using traffic of real IoT devices, analyzing
a brute force approach, multiple greedy algorithms and our proposed CE-based
algorithm, comprehensively.

We believe our framework for cost-optimal feature selection is also applicable
for other problems, where features have associated costs and solution
deployment has a budget constraint. Examples of such problems in the domain of
network traffic analysis include the traditional network application
classification [15], botnet detection [16], anomaly detection in traditional
[17, 18] as well as IoT [19] networks, etc.

After defining the system model in Section III, we formulate the optimisation
problem in Section IV. In Section V, we develop the CE-based algorithm.
Subsequently, in Section VI, we present three greedy algorithms for selecting
features while respecting the provided budget. We carry out experiments and
present results in Section VII.

##  II Related works

Fingerprinting or identification of hosts, operating systems, etc. has been a
problem of interest for many years now (e.g., see [20]). Similarly, there have
been works on fingerprinting devices; for instance Gao et al. [21] proposed to
identify wireless access points by applying a wavelet-based approach on frame
arrival time differences. With the emergence of IoT devices, research works
have looked into inferring different aspects of IoT devices from their network
traffic [22, 23]. For example, the work in [23] reveals private and sensitive
information of users at a smart home are leaked by analyzing only the
encrypted network traffic.

Identification of IoT devices is of use to different entities, such as
enterprises and ISPs. For an enterprise, identification helps in asset
tracking as well as for securing the devices from potential vulnerability
exploitation; whereas, for ISPs, knowing the type of different devices
connected to its network might help in mitigation of large-scale attacks. For
instance, Yang et al. [24] generated fingerprints of devices using neural
algorithms, which were used to discover millions of devices connected to a
network.

Recent works have been exploring machine learning models for IoT device
fingerprinting. A common approach is to employ supervised machine learning, to
train a single classifier for each device [4, 5]; and these set of classifiers
are subsequently used for predicting a traffic session (or sequence of first
$n$ packets) of a device. If a device traffic is predicted to be of multiple
types (or classes), then another metric (such as edit distance [25]) is used
to break the tie. In our previous work [9], we combined both supervised and
unsupervised approaches for identifying known devices as well as grouping
unknown devices of the same type across different networks. We explored large
number of features extracted from network traffic, and the empirical study
based on 16 IoT devices confirmed with other works that, devices can be
classified based on network traffic features with high accuracy.

There are also works that consider the cost of including different features,
although not in the IoT settings (e.g., [26, 27]). We briefly discuss a few
here. In [28] the authors used a particle swarm optimization approach for
cost-based feature selection in order to get a Pareto front of non-dominated
solutions which gives both high accuracy and low cost. Among other works, Min
et. al formulated cost-constrained feature selection as a CSP (constraint
satisfaction problem) [29]; while they proposed a heuristic solution, they
assumed decisions as given, and the notion of risk was not considered within
the scope of the work. There are also works that included a cost evaluation
function as part of existing feature selection approaches; for example, two
filter-based feature selection methods were experimented in [30]. Another
interesting approach was proposed in [31], wherein the cost of feature
selection was made part of the SVM classification model for a credit scoring
application.

However, to the best of our knowledge, previous works did not consider the
cost of different features that are extracted for training and classifying
devices. Neither did they consider the risk of misclassification, in
particular when the loss due to wrong classification can be different
depending on the classification result. We consider these important aspects in
our work here.

##  III System model

We describe the system model in this section. Below, we first state the
assumptions of the system, and then go on to define misclassification loss as
well as our concept of risk. The commonly referred notations are listed in
Table I.

TABLE I:  Table of Notations Term | Definition
---|---
$\mathbf{f}$ |  | Feature vector, constituting of the features abstracting
---
network traffic characteristics. $|\mathbf{f}|=m$
$\mathbf{c}$ |  | Cost vector, constituting of the costs associated
---
with each of the $m$ features. $|\mathbf{c}|=m$
$\mathbf{v}$ |  | A binary vector denoting the features selected
---
from $\mathbf{f}$. $|\mathbf{v}|=m$
$\lambda$ | Feature budget
$R(\mathbf{v})$ |  | Risk score, based on the selected
---
feature vector $\mathbf{v}$
$\mathcal{L}$ |  | Loss Matrix where element $l_{i,j}$ represents
---
misclassification loss. $|\mathcal{L}|=n\times n$

###  III-A Traffic and features

Let $\mathcal{D}$ denote the set of devices considered for classification in a
network; furthermore, let $n=|\mathcal{D}|$. Corresponding to a device
$d\in\mathcal{D}$, assume $q_{d}$ units of traffic have been stored and made
available for the purpose of device classification. For simplicity, and
without loss of generality, we assume $q$ units of traffic are available for
every device. Let $\mathcal{T}^{d}$ denote the traffic of device $d$. Each
unit of traffic (a connection or a session) of $\mathcal{T}^{d}$ is processed
to extract the feature vector. We use $\mathbf{f}$ to represent the $m$
features of interest in our problem:

$\mathbf{f}=[f_{1},f_{2},\dots,f_{m}];\quad\mathbf{f}\in\mathbb{R}^{m}.$

Denote by $\mathcal{E}(.)$ the function for feature extraction. For an input
traffic data $\mathcal{T}^{d}$ of device $d$, $\mathcal{E}(\mathcal{T}^{d})$
produces a matrix $\mathcal{S}^{d}$ of extracted features corresponding to all
units of traffic:

$\mathcal{S}^{d}:=\left[\begin{array}[]{cccc}{s^{d}_{1,1}}&{s^{d}_{1,2}}&{\cdots}&{s^{d}_{1,m}}\\\
{s^{d}_{2,1}}&{s^{d}_{2,2}}&{\cdots}&{s^{d}_{2,m}}\\\
{\vdots}&{\vdots}&{\vdots}&{\vdots}\\\
{s^{d}_{q,1}}&{s^{d}_{q,2}}&{\cdots}&{s^{d}_{q,m}}\end{array}\right],$ (1)

where $s^{d}_{j,k}$ denotes the $k^{\text{th}}$ feature extracted from the
$j^{\text{th}}$ traffic unit of device $d$. To generalize, we use $\mathbf{s}$
to denote an extracted feature vector of a device. Obviously, $\mathbf{s}$ is
of length $m$. Note that, $\mathcal{S}^{d},\forall d\in\mathcal{D}$ form the
dataset $\mathbb{X}$ used for training and testing the classification model.
We use $\mathbb{X}^{\texttt{train}}$ and $\mathbb{X}^{\texttt{test}}$ to
denote the partition of the dataset for, training and testing, respectively.

###  III-B Cost of feature extraction

Features characterise different aspects of the network traffic, and are
obtained by processing network traffic. Therefore, feature extraction involves
cost in terms of resources required for processing and storing the feature,
and sometimes for even purchasing the feature. With a slight abuse of
notation, we use $\mathcal{E}_{f_{k}}(.)$ the function to extract feature
$f_{k},1\leq k\leq m$. Therefore the cost of extracting a feature $f_{k}$ will
be denoted by:

$c_{k}=\texttt{cost}(\mathcal{E}_{f_{k}});\quad\forall k\in[1,2,\dots,m],$

and the cost vector is defined as:

$\mathbf{c}=[c_{1},c_{2},\dots,c_{m}];\quad\mathbf{c}\in\mathbb{R}_{+}^{m}.$

###  III-C Supervised classification of devices

We consider supervised machine learning approaches for IoT classification,
wherein traffic data is labelled and provided for training the classifier. The
trained model, denoted by $\mathcal{M}$, is subsequently used in an
operational environment to differentiate devices into different types.

Given the matrices of extracted features $\mathcal{S}^{d},\forall
d\in\mathcal{D}$, the classification model $\mathcal{M}$ maps $\mathbf{s}$ to
one of the devices types $\\{d_{1},d_{2},\dots,d_{n}\\}$. The output of a
machine learning model $\mathcal{M}$ is usually represented using an $n\times
n$ confusion matrix $\mathcal{X}_{\mathcal{M}}$ that is processed to obtain
relevant performance metrics, such as precision and recall. The element in the
$i^{\text{th}}$ row and $j^{\text{th}}$ column of the confusion matrix,
$x_{i,j}$, represents the number of data points (or instances) of class $j$
that were predicted to be of class $i$ by the classifier. Given the confusion
matrix, we now define $p_{i,j}$, the probability of misclassification, as the
probability that an instance of class $j$ is predicted as an instance of class
$i$. That is if $\widehat{d}$ is the predicted device and $d$ is the actual
device, then we define the probability of classifying $d=j$ as $\widehat{d}=i$
is given as:

$\displaystyle{\widehat{p}_{i,j}}=\operatorname{Pr}(\widehat{d}=i|d=j)$
$\displaystyle=\frac{x_{i,j}}{\sum_{k=1}^{n}x_{k,j}}.$ (2)

For a classification model $\mathcal{M}$, we define an $n\times n$
misclassification matrix $\hat{\mathcal{P}}_{\mathcal{M}}$ with elements
$\widehat{p}_{i,j}$’s. For simplicity, henceforth, we drop the subscript and
denote the misclassification matrix as $\mathcal{P}$.

###  III-D Misclassification loss

Assume that the classifier is tasked to predict the class of a device $d_{i}$.
We represent a device $d_{i}$ as as an ordered pair $<$ type, brand $>$, where
type indicates the type of the device, e.g., a camera or a speaker, while
brand represents the brand of the item, e.g., Sony or Samsung. When the
classification model (mis)classifies a device $d_{i}=<t_{i},b_{i}>$ as
$d_{j}=<t_{j},b_{j}>$, there is a loss incurred; we denote this
misclassification loss as $l_{i,j}$, and the corresponding loss matrix
$\mathcal{L}$:

$\mathcal{L}:=\left[\begin{array}[]{cccc}{0}&{l_{1,2}}&{\cdots}&{l_{1,n}}\\\
{l_{2,1}}&{0}&{\cdots}&{l_{2,n}}\\\ {\vdots}&{\vdots}&{\vdots}&{\vdots}\\\
{l_{n,1}}&{l_{n,2}}&{\cdots}&{0}\end{array}\right].$ (3)

This loss matrix is a user-defined parameter and depends on the types of
devices considered for classification. While this allows for a generic
definition of the misclassification losses as deemed right by the user, we
later provide (in Section VII-C) the specific definition used in this work for
the purpose of illustration as well as for experimentation.

###  III-E Cyber Risk

Using these definitions, we define the cyber risk of the model. While
$\mathbf{f}$ is the vector of features of interest, not all features might be
available for modeling, given features have cost, and a solution is
constrained by the available budget. We use a binary vector $\mathbf{v}$ to
indicate whether a feature is selected or not.

$\mathbf{v}=\left[v_{1},\dots,v_{m}\right],$

where

$v_{k}=\left\\{\begin{array}[]{ll}{1,}&{\text{if the }k^{\text{th }}\text{
feature selected }}\\\ {0,}&{\text{if the }k^{\text{th }}\text{ feature is not
selected }}\end{array}\right.$

Next, we define cyber risk. Given a classifier $\mathcal{M}$, loss matrix
$\mathcal{L}$, feature budget $\lambda$, the extracted data (for the selected
features indicated by $\mathbf{v}$) $\mathbb{X}_{\mathbf{v}}$, and a feature
selection vector $\mathbf{v}$, the cyber risk score
$R(\mathbf{v},\mathcal{M},\mathcal{L},\lambda,\mathbb{X}_{\mathbf{v}})$ is the
expected sum of the losses due to misclassifications. Since we are considering
the risk score for a fixed classifier model, for a fixed number of devices and
traffic data, we may simplify the risk score by denoting it as
$R(\mathbf{v})$. Formally, the cyber risk score or the risk score, based on
the set of selected features (captured by $\mathbf{v}$), is defined as the sum
of the product of the probability of misclassification and the losses
associated with misclassification of each device ($l_{i,j}$), which is given
by:

$\displaystyle R(\mathbf{v})$
$\displaystyle=\sum_{i=1}^{n}\sum_{j=1}^{n}\operatorname{Pr}(\widehat{d}=i|d=j;\mathbf{v})\times
l_{i,j}$ (4)

##  IV Problem Definition - Optimal Feature Selection under Budget Constraint

This work looks into the problem of minimizing the cyber risk associated with
classification of IoT devices, by selecting the optimal set of features from a
universal feature set, whilst keeping the feature cost less than the budget
available.

Problem Definition: Given the misclassification matrix $\mathcal{P}$ for a
given feature vector $\mathbf{f}$, and the loss matrix $\mathcal{L}$, we aim
to find the optimal feature vector (via $\mathbf{v}$) which minimizes the
cyber risk score $R(\mathbf{v})$, under a budget constraint $\lambda$.

Thus, the optimization problem may be defined as:

$\displaystyle\mathbf{v}_{s}=$
$\displaystyle\underset{\mathbf{v}\in\\{0,1\\}^{m}}{\arg\min}R(\mathbf{v})$
(5) s.t $\displaystyle\sum_{j=1}^{m}{c}_{j}v_{j}\leq\lambda,$

where $R(\mathbf{v})$ is as defined in Eq. 4.

The optimization problem presented in Eq. 5 has some unique properties making
it a non-trivial problem to solve. Firstly, the cyber risk function
$R(\mathbf{v})$ used as the principle objective function, is not an analytic
function. Hence, using methods to solve continuous optimization problems, like
the gradient descent is not feasible in this scenario. This is mainly because
the gradient descent uses the Newton’s Method to find the optimal solution
which in turn uses a well-defined continuous objective function; and
$R(\mathbf{v})$ is not a continuous function. Moreover, another important
constraint to use such methods requires the objective function, the constraint
equations and the domain space to be convex in nature. In our scenario, we do
not know whether we have a closed-form analytical expression for the risk
score which is the objective function. This is because it is dependent on the
classification model and the features selected. Though a probabilistic model
for a simple classifier like the Naive-Bayes classifier can be obtained, we
cannot say the same for any general classifier, for example the Decision tree
or the Random Forest classifiers. Thus, in a general sense, it is not possible
to get an analytical expression for the risk score defined in Eq. 4. The best
we can do is to obtain a point-wise evaluation of the objective function which
is the minimum requirement to attempt a solution to this optimization problem.
We observe that the constraint functions are affine in nature, and since all
affine functions are convex, the constraint functions are also convex in
nature. This leaves us with the domain space ($m$-dimensional binary subspace)
for the optimization problem.

Since the domain space is not convex in nature, we can safely conclude that
the problem is not a convex optimization problem, and cannot be solved by
using convex optimization tools. Therefore, the optimal way to solve such
problems is via a combinatorial search over all possible combinations of
features by the brute force method which is not a very efficient way. In
classes of problem such as the one posed in this paper,a subsequent brute
force enumeration of all possibilities is computationally prohibitive and as
such a stochastic search based approach needs to be developed in practice. In
the next section, we explore the cross entropy technique for searching the
entire subspace in an efficient way to potentially converge to the global
optima.

##  V Feature Selection via Cross Entropy Method

In this section we develop a novel algorithm to solve the feature selection
under budget constraints, presented in Eq. 5. As mentioned before, this is a
non-convex combinatorial optimization problem. To overcome this computational
difficulty, we develop a novel algorithm via a Monte Carlo sampling approach,
which has a low computational complexity. Specifically, we use the cross
entropy (CE) technique, which is based on the Importance Sampling Technique
which is known to be an effective solution in computational approaches to
otherwise solving NP-hard problems. The CE converts the deterministic
optimisation problem into a stochastic couterpart, see details in [32]. It
then approximates the optimal sampling distribution by minimizing the
Kullback-Leibler (KL) divergence [33]. Without loss of generality, we may
change the optimization problem in Eq. 5 to a maximization problem, that is:

$\mathbf{v}^{*}=\underset{\mathbf{v}\in\\{0,1\\}^{m}}{\arg\max}\quad\mathcal{U}(\mathbf{v}),\quad\text{s.t.}\quad\mathbf{c}^{T}\mathbf{v}\leq\lambda$
(6)

where $\mathcal{U}(\mathbf{v})=\frac{1}{R(\mathbf{v})}$.

Instead of searching for the optimal solution directly, like in the case of a
brute force search based approach, the CE places a probability distribution on
the set of $m$-dimensional binary features $(\mathbf{v}\in\\{0,1\\}^{m})$,
thus transforming the problem into estimation.

In our model, since the selection of a feature is indicated by a binary
variable (“select” or “don’t select”), we use an independent Bernoulli random
variable to indicate this choice for each of the $m$ features. The Bernoulli
distribution has a single variable parameter $p$ , i.e., for the $k$-th
feature this is given by $\\{p_{k}\\}_{k=1}^{m}$, and is a member of the
Natural Exponential Families (NEF) of distributions [34]. This is a big
advantage, since under the NEF, the parameter of the distribution can be
estimated analytically in closed form via the Maximum Likelihood Estimator
(MLE), making the CE easy to implement. At each iteration of the CE method
there are three steps:

  1. S1

Generate samples: generate $\eta$ independent samples of binary sets given by
$\mathbf{w}^{[i]}=\\{w^{[i]}_{1},w^{[i]}_{2}\ldots,w^{[i]}_{m}\\}$, where
$w^{[i]}_{k}\sim\texttt{Bernoulli}(p_{k});1\leq i\leq\eta$.

  2. S2

Selection of elite samples: from those $\eta$ samples, we select only those
samples which satisfy the budget constraint (ie.
$\mathbf{c}^{T}\mathbf{w}^{[i]}\leq\lambda$) to obtain a subset of
$\eta^{\prime}\leq\eta$ samples. Next, from this subset we select only the
“elite” samples—those for which the objective function value exceeds a pre-
defined threshold, defined via a quantile value $\rho$. This choice is
indicated by
$\mathbbm{1}\left(\mathcal{U}(\mathbf{w}^{[i]})\geq\gamma\right)$, where
$\gamma$ is the $(1-\rho)^{\text{th}}$-sample quantile of
$\mathcal{U}_{1:\eta^{\prime}}$.

  3. S3

Estimation of parameters: using only this subset of elite samples, we re-
estimate the parameters of the Bernoulli random variable
$\\{p_{k}\\}_{k=1}^{m}$ via the MLE, given by

$\widehat{p}_{k}=\frac{\sum\limits_{i=1}^{\eta^{\prime}}\mathbbm{1}\left(\mathbf{w}^{[i]}_{j}=1\right)\overbrace{\mathbbm{1}\left(\mathcal{U}(\mathbf{w}^{[i]})\geq\gamma\right)}^{\text{Choose
elite
samples}}}{\sum\limits_{i=1}^{\eta^{\prime}}\mathbbm{1}\left(\mathcal{U}(\mathbf{w}^{[i]})\geq\gamma\right)},\\\
k=\\{1,\cdots,m\\}.$ (7)

The three steps of the algorithm are then iterated until a stopping rule is
met, for example, if the algorithm has converged to a local maxima or has
exhausted a pre-defined number of iterations. The parameter $\rho$ is the
quantile value, and is commonly set to $0.9$. The resulting algorithm is
presented in Algorithm 1, where in Step 10 we have introduced the parameter
$\alpha\in[0,1]$ which controls the learning rate of the algorithm, thus
avoiding getting trapped in local maxima, see details in [33].

It is important to note that $v_{k}$, where $1\leq k\leq m$, denotes whether
the $k^{\text{th}}$ feature is selected by the algorithm. We iterate the cross
entropy algorithm until the convergence criterion is met, which in this work,
translates to reaching the maximum number of iterations ($T_{\max}$).

Input:
$\mathbb{X}^{\texttt{train}},\mathbb{X}^{\texttt{test}},\eta,\rho\in[0,1),\alpha,\beta,\lambda,\mathbf{c}$

1

2Initialisse vague prior:
$\mathbf{\widehat{p}}=\left[\widehat{p}_{1},\widehat{p}_{2},\ldots,\widehat{p}_{m}\right]$
such that $p_{k}=0.5,\forall k$

3 while  _stopping criterion not met_ do

4 Step 1:

5 Generate $\eta$ independent samples of binary sets given by
$\mathbf{w}^{[i]}=\left[w^{[i]}_{1},w^{[i]}_{2},\ldots,w^{[i]}_{m}\right]$,
where $w^{[i]}_{k}\sim\texttt{Bernoulli}(\widehat{p}_{k});\quad 1\leq
i\leq\eta,1\leq k\leq m$.

6 Step 2:

7 From $\eta$ samples, remove all samples that do not satisfy the constraint
$\mathbf{c}^{T}\mathbf{w}^{[i]}<\lambda$. Let the new indices be
$i={1,\ldots,\eta^{\prime}}$.

8
$\mathcal{X}=\mathcal{M}(\mathbb{X}^{\texttt{train}}_{\mathbf{w}^{[i]}},\mathbb{X}^{\texttt{test}}_{\mathbf{w}^{[i]}})$

9 Compute $\hat{\mathcal{P}}$, from $\mathcal{X}$ as given in Eq. 2.

10 Compute
$\mathcal{U}_{i}=\mathcal{U}(\mathbf{w}^{[i]}),i={1,\ldots,\eta^{\prime}}$.

11 Compute $\gamma$, the $(1-\rho)^{\text{th}}$-sample quantile of
$\mathcal{U}_{1:\eta^{\prime}}$.

12 Step 3:

13 Re-estimate model parameters via the MLE:
$\widehat{p}_{k}=\alpha\frac{\sum\limits_{i=1}^{\eta^{\prime}}\mathbbm{1}\left(\mathbf{w}^{[i]}_{j}=1\right)\mathbbm{1}\left(\mathcal{U}(\mathbf{w}^{[i]})\geq\gamma\right)}{\sum\limits_{i=1}^{\eta^{\prime}}\mathbbm{1}\left(\mathcal{U}(\mathbf{w}^{[i]})\geq\gamma\right)}+(1-\alpha)\widehat{p}_{k}$,
$\forall k$

14 end while

15

16For each $p_{k}$, make the final binary decision as follows:
$v_{k}=\left\\{\begin{array}[]{ll}{1,}&{p_{k}\geq\beta}\\\ {0,}&{\text{
Otherwise }}\end{array}\right.\forall k\in\left[1,\dots,m\right]$ where
$\beta$ is a pre-defined threshold.

17

18return $\mathbf{v}^{*}=\left[v_{1},v_{2},\ldots,v_{m}\right].$

Algorithm 1 Cross Entropy Based Feature Selection

Computational Complexity: The computational complexity of the CE algorithm for
feature selection is characterized by the number of independent samples used
$\eta$, the feature size $m$ and the stopping criterion. In Algorithm 1, the
calculation of $\mathcal{U}(\mathbf{w}^{[i]})$ is the most computationally
expensive step. This is because the computation of
$\mathcal{U}(\mathbf{w}^{[i]})$ involves using a classifier and matrix
multiplication of the misclassification matrix and the loss matrix. Thus, this
step becomes the bottleneck for the performance of the algorithm, which leads
us to conclude that the complexity of computation of this step will also be
the dominant component of the complexity of the entire algorithm. Now, the
complexity of computation of the $\mathcal{U}(\mathbf{w}^{[i]})$ is given by
$\mathcal{O}(\eta\times\mathcal{C}(m;\Psi)\times T_{\max})$ where $T_{\max}$
is the number of iterations and $\mathcal{C}(m;\Psi))$ denotes the complexity
of the classifier in terms of the feature length $m$ and other parameters
$\Psi$ specific to the classifier. For example, if we use the Naive-Bayes
classifier, $\mathcal{C}(m;\Psi)=\mathcal{O}(N_{\texttt{train}}m)$, where
$N_{\texttt{train}}$ is the number of training examples and $m$ is the number
of features. Since the number of samples is a constant for each iteration, the
dependent parameters for the complexity of the algorithm may be reduced down
to $\eta$ and $T_{\max}$, which are also the only free parameter that can be
controlled by us. The values of $\eta$ and $T_{\max}$ are determined based on
the trade-off between the computational budget and the required detection
performance.

##  VI Feature selection via brute-force and greedy approaches

In this section we develop algorithmic alternatives to the CE technique that
will act as comparisons to our proposed approach. We first present the brute-
force approach for solving the optimization problem (Eq. 5). Subsequently, we
also develop three greedy heuristics that use different strategies for
selecting features for device classification.

###  VI-A Brute Force Method

The brute force approach is presented in Algorithm 2. The algorithm selects
each combination of the features (via the vector $\mathbf{v}$), and evaluates
the risk score if the cost of the features is within the budget constraint
($\lambda$). Of all such feature combinations, one that minimizes the risk
score is the optimal set of features for device classification. Though this
method gives the optimal solution over the feature space, the computational
complexity of searching over the entire parameter space exhaustively is
prohibitively high. Thus, this approach gives us an upper bound on the run-
time complexity of the algorithm, and also a lower bound on the risk.

Computational Complexity: The exhaustive search in the algorithm means that,
for a feature vector of length $m$, the while loop is executed $2^{m}$ times.
For each of the $2^{m}$ executions, a classifier has to be trained (and
tested) to determine the loss associated with the selected feature vector.
Thus, the overall complexity of the brute force search algorithm is given by
$\mathcal{O}(2^{m}\times\mathcal{C}(m;\Psi))$.

1

Input: $\mathbb{X}^{\texttt{train}},\mathbb{X}^{\texttt{test}}$, $\mathbf{c}$,
$\lambda$, $\mathbf{f}$, $\mathcal{M}$,$\mathcal{L}$

2

3$i\leftarrow 1,R_{\min}\leftarrow\infty$ $\triangleright$ initializations

4 $\mathbf{v}\leftarrow\left[0,\dots,0\right]_{(1\times m)}$

5 while  _ $i\leq 2^{m}$_ do

6 $\mathbf{v}\leftarrow\texttt{Binary}(i)$ $\triangleright$ $v_{k}$ is $k$-th
digit in the Binary representation of $i,\quad 1\leq k\leq m$

7 if  _$\mathbf{c}^{T}\mathbf{v} <\lambda$_ then

8

9
$\mathcal{X}\leftarrow\mathcal{M}(\mathbb{X}^{\texttt{train}}_{\mathbf{v}},\mathbb{X}^{\texttt{test}}_{\mathbf{v}})$

10 Compute $\hat{\mathcal{P}}$, from $\mathcal{X}$ as given in Eq. 2

11 Compute $R(\mathbf{v})$ according to Eq. 4

12 if  _$R(\mathbf{v}) <R_{\min}$_ then

13 $R_{\min}\leftarrow R(\mathbf{v})$

14 $\mathbf{v}_{s}\leftarrow\mathbf{v}$

15

16 end if

17

18 end if

19 $i\leftarrow i+1$

20

21 end while

return $\mathbf{v}_{s}$

Algorithm 2 Brute Force Feature Selection

###  VI-B Greedy Algorithms

As the name suggests, greedy algorithms are efficient ways to solve an
optimization problem, with the down side being that, they might end up with a
local optimum. We define three intuitive greedy approaches in this section;
they differ on the parameter (referred to as key) they used to select the next
feature for classification. The general steps for these three greedy
approaches are given in Algorithm 3. First, the feature indices are sorted
based on an input parameter key. Subsequently, in each iteration within the
while loop, the algorithm selects one feature at a time, constrained by the
budget, thereby eventually forming the feature vector (indicated by
$\mathbf{v}$) for classification.

####  VI-B1 Cost-based greedy algorithm (CGA)

In this approach, the feature cost ($\mathbf{c}$) is used as the input
parameter key to sort the (indices of) features. Therefore, this simple greedy
algorithm selects the minimal cost feature at each iteration. This would
reveal the performance of classification, if only feature cost is used as a
criterion to select the features.
Complexity: The sorting algorithm takes $\mathcal{O}(m\log m)$ time for $m$
features. The classifier has to be trained only once in this case, after the
selection of all the features. Hence, the complexity of this algorithm is
$\mathcal{O}(m\log m+\mathcal{C}(m;\Psi))$.

####  VI-B2 Risk-based greedy algorithm (RGA)

Next, we define a risk based approach. We train a classifier using only one
feature at a time, and we do this for all features constituting $\mathbf{f}$.
For each classifier corresponding to each feature $f_{i},1\leq i\leq m$, we
compute the risk using Eq. 4. The vector of risk scores of length $m$ is then
provided as input parameter key to Algorithm 3. Therefore, RGA algorithm
attempts to select the features that correspond to the least risk scores,
under the assumption that the risk due to (say) two features is equal to the
sum of the risk due to the individual features.
Complexity: The classifier is run $m$ times to build $m$ models, and obtain
their corresponding risks. Therefore, the overall complexity is
$\mathcal{O}(m\log m+m\times\mathcal{C}(m;\Psi))$

1

Input: $\mathbb{X}^{\texttt{train}},\mathbb{X}^{\texttt{test}}$, $\mathbf{c}$,
$\lambda$, $\mathbf{f}$, $\mathcal{M}$, $\mathcal{L}$, key

2

3$\Phi\leftarrow\arg\texttt{sort}(\mathbf{f}$, key) $\triangleright$ Obtain
the sorted indices

4 $i\leftarrow 1$

5 $\mathbf{v}\leftarrow\left[0,\dots,0\right]_{(1\times m)}$

6 while  _$i\leq m$_ do

7

8 $\mathbf{v}_{\left[\Phi(i)\right]}\leftarrow 1$ $\triangleright$
$\mathbf{v}_{\left[j\right]}$ denotes the $j$-th index of $\mathbf{v}$

9 if  _$\mathbf{c}^{T}\mathbf{v} >\lambda$_ then

10 $\mathbf{v}_{\left[\Phi(i)\right]}\leftarrow 0$

11 end if

12 $i\leftarrow i+1$

13

14 end while

15$\mathcal{X}\leftarrow\mathcal{M}(\mathbb{X}^{\texttt{train}}_{\mathbf{v}},\mathbb{X}^{\texttt{test}}_{\mathbf{v}})$

16Compute $\hat{\mathcal{P}}$, from $\mathcal{X}$ as given in Eq. 2

17Compute $R(\mathbf{v})$ according to Eq. 4

return $\mathbf{v}$

Algorithm 3 Greedy Feature Selection

####  VI-B3 Value-based greedy algorithm (VGA)

Finally, we also consider how valuable a feature is based on both the accuracy
and the feature cost. For each feature $f_{i}\in\mathbf{f}$, we train the
classifier similar to what we did in the RGA approach. The $\text{F}_{1}$
score is computed for each of $f_{i}$ and is denoted by $\texttt{acc}(f_{i})$.
As defined in Sec. III-B, $c_{i}$ denotes the cost of feature $f_{i}$. Thus,
we define the value of a feature $f_{i}$ as:

$\texttt{density}_{i}=\frac{\texttt{acc}(f_{i})}{c_{i}},\quad 1\leq i\leq m$

The vector of values is then passed as the parameter key to Algorithm 3.

Complexity: Like the previous greedy algorithm, in this algorithm too, the
classifier is run $m$ times to train the model for the $m$ features
independently. Therefore, the complexity is $\mathcal{O}(m\log
m+m\times\mathcal{C}(m;\Psi))$.

##  VII Performance Evaluation

In this section, we describe the experiments performed to evaluate the
different algorithms presented in the previous sections. After a briefing on
the dataset used, we describe how we estimated costs of features (in Section
VII-B). We also define the loss matrix used for experiments in this work
(Section VII-C). The first set of experiments we carry out (in Section VII-D)
are to evaluate a selected set of classification models. Subsequently, we
evaluate brute force, CE and greedy algorithms, first under no budget
constraints (Section VII-E), and then later we evaluate CE and greedy
algorithms when budget is fixed (Section VII-F). In Section VII-F, we also
perform further analysis to compare CE algorithm with the best greedy
algorithm.

###  VII-A Real datasets for experiments

For the experiments, we used network traffic from 15 different IoT devices as
listed in Table I. The devices were connected to the Internet via a gateway,
where the network traffic was captured. The traffic was split into intervals
of 15 minutes each, and the number of sessions captured for each device is
shown in Table II. From the network data of the IoT devices, 111 features were
extracted (see [9] for the list of features).

TABLE II: Information on IoT devices used Label | Device | Brand |  | Sessions
---
Captured
1 | Echo Dot | Amazon | 490
2 | Smart Remote | Broadlink | 480
3 |  | Camera
---
(DCS700L)
D-Link | 384
4 |  | Camera
---
(DCS5030L)
D-Link | 410
5 |  | Smart Socket
---
(DSPW215)
D-Link | 672
6 | Chromecast | Google | 297
7 | Home Control | Google | 529
8 | Smart Socket | Oittm | 394
9 | Hue Light | Phillips | 644
10 | Smart Things | Samsung | 587
11 |  | Smart Bulb
---
(LB100)
TP-Link | 482
12 |  | Camera
---
(NCS250)
TP-Link | 587
13 |  | Camera
---
(NCS450)
TP-Link | 494
14 |  | Smart Socket
---
(HS100)
TP-Link | 452
15 |  | Smart Socket
---
(HS110)
TP-Link | 387

###  VII-B Feature costs

As described earlier, the extraction of each feature has a cost. We argue that
the cost of feature extraction is a function of three factors: the
computational power (or computational complexity) of the extraction process,
the memory used, and the confidentiality of the information related to that
feature. Therefore, we break the cost into three components, each
corresponding to compute power, memory and privacy. Finding the exact cost due
to each component and how to integrate those component costs into a single
cost value is outside the scope of this work. Instead, we simplify the cost of
each component to be in one of three levels {low, medium, high}. We illustrate
the concept of assigning costs to feature using examples in the Appendix.

The total cost of a feature $f_{i}$ can be defined as:

$\text{Cost}_{i}=g_{i}(\text{compute cost},\text{memory cost},\text{privacy
cost}),$

where $g_{i}(.)$ is a function computing the total cost of the feature
extraction process. For our purposes, we define $g_{i},1\leq i\leq m$ to be
the median of the three input cost components. While there are other ways of
integrating component costs (like, “cost is always high if privacy cost is
high”), we stick to this simple definition for our work here. For example,
consider the feature of ‘connection length, in number of packets’. To extract
this feature, connection (that is, a 5-tuple flow) identifier has to be hashed
and stored in a data structure such as a hash table, and the number of packets
needs to be counted [35]. The computational cost is medium since a hashing is
required for every arriving packet, and hash table operations would at worst
case be be linear with the number of packets (e.g., for insertion of new
5-tuple flow in the traditional hash table), besides flows have to be
regularly removed from the table once they become inactive. The memory
requirement is assigned as high due to the necessity to maintain a hash table.
The privacy cost is considered low, as only packet counts of connections are
extracted, and no private information (e.g., visited websites) is extracted.
Therefore, the cost of extracting connection length is medium.

###  VII-C Loss matrix, $\mathcal{L}$

We introduced the concept of misclassificaiton loss in Section III-D. Ideally,
the loss matrix is an input provided by the users, based on how they perceive
the loss due to misclassification errors. For the purpose of this work, we
define the loss matrix as follows.

When the classifier classifies a device $d_{i}=<t_{i},b_{i}>$ as
$d_{j}=<t_{j},b_{j}>$, the loss value $l_{i,j}$ is calculated as
$l_{i,j}=2*f(t_{i},t_{j})+f(b_{i},b_{j}),$ where $f(x_{i}~{},x_{j})=1$ if
$x_{i}\neq x_{j}$ and $0$ if $x_{i}=x_{j}$. Taking every device pair, we
follow this definition to derive the values for the loss matrix $\mathcal{L}$
in the experiments here. It is to be noted that we are giving a higher value
of loss if the classifier cannot classify the type of the device even if it
gets the right brand. For example, if the classifier classifies a Samsung
camera as a Sony camera, the loss value $l_{i,j}=2\times 0+1=1.$ But if it
classifies the device as Samsung (Smart things) Hub, then the loss
$l_{i,j}=2*1+0=2$.

###  VII-D Comparison of classifiers

The cyber risk score $R(\mathbf{v})$ of a feature vector $\mathbf{v}$ depends
on the misclassification matrix which is in turn derived from the confusion
matrix of the classifier. As such, the choice of classifier plays an important
role in evaluating the performance of the system. We selected four different
classification models—Gaussian Naive-Bayes classifier, SVM (support vector
machine) with RBF kernel, Decision tree and Random Forest, and compared their
performances based on accuracy and the execution time. We use
$\text{F}_{1}$-score (the harmonic mean of precision and recall) to represent
the accuracy of the classifier.

All the experiments in this work are carried out on an 8-core Intel Core
i7-2600 running at 3.8GHz CPU and equipped with 16GB of RAM. For comparing the
time of execution, we consider both the training and the testing times of the
classifiers. Fig. 1 plots the time taken for each classifier for training and
predicting on the traffic session of IoT devices. The X-axis here (as well as
in all figures in this paper) denotes the number of features considered for an
experiment; therefore, each point on the X-axis corresponds to an independent
run of the experiment with that many number of features given as input. Since
the number of experiments increases with the number of features, we limit the
total number of features provided as input in each experiment to 69; beyond 69
features, the experiments did not provide any new insights.

From Fig. 1, we observe that the Decision tree classifier and the Naive-Bayes
classifier take the least time for model building and prediction.

Figure 1: Execution time of classifiers for varying number of features $m$
Figure 2: Classification accuracy as a function of the number of features $m$

We also plot the accuracy of the different classifiers in Fig. 2; all of them
achieve high $\text{F}_{1}$-scores. Since Decision tree classifier has much
less time of execution, while also having high $\text{F}_{1}$-score,
henceforth we use Decision tree for the rest of the experiments to evaluate
cost-aware feature selection algorithms.

###  VII-E Evaluation of algorithms without budget constraint

Next, we compare the five different algorithms discussed in sections V and VI,
by varying the number of features $m$ and with no budget constraint,
$\lambda\rightarrow\infty$. We evaluate their performance based on (i) the
time of execution and (ii) the cyber risk score.

As mentioned above, for each experiment, we need to provide a set of features;
and the algorithms are supposed to find the best features from the given input
set of features. To do this, for each evaluation, we can start with a minimum
feature set and increase the set by one feature for each experiment. That is,
since we have 69 features, if we start with a singleton set and keep adding
one feature for every new experiment, we would need 69 experiments. However,
this is under the assumption that, we know the sequence in which the features
should be added to the set. Consider adding the most discriminatory feature as
the last one to the growing set of features; this means no other experiment
would use this important feature for evaluation. On the other hand, the ideal
case would be to generate all possible sequences — 69! in our case, and carry
out experiments by expanding set from a minimum size to the maximum of 69
features, for each sequence.

Since this is not computationally feasible, unless stated otherwise, we
generate sequence of ranked features. To this end, we use the feature ranking
mechanism described in our previous work [36] where the features are ranked
according to their ability to discriminate between every pair of devices by
combining the results from multiple statistical tests. In order to compare and
evaluate the algorithms, we take the full set of ordered feature vector
$\mathbf{f}$ (obtained via ranking), and select the first nine features from
it as $\mathbf{\bar{f}}=\left[f_{1},f_{2},\dots,f_{9}\right]$. For each
subsequent iteration, we add the next feature in the ranked order to our
selected feature vector and calculate the time of execution and the risk score
of all the five algorithms using the new set of selected features. Thus for
the $t^{th}$ iteration, the selected feature vector is represented as
$\mathbf{\bar{f}}=\left[f_{1},f_{2},\dots,f_{t+9}\right];t=0,1,2,\dots,61$,
where $|\mathbf{\bar{f}}|=t+9$. Therefore, the algorithm must be iterated 61
times, such that, when $t=61$, all the 69 features will be explored. We
proceed to the analyses next.

####  VII-E1 Execution time analysis

The comparison of the execution times of the different algorithms help us to
get an estimate of their computational complexities in practice.

In this section, we compare the time of execution for the CE algorithm with
respect to the brute force and the greedy algorithms, under no budget
constraint ($\lambda\rightarrow\infty$).

From Fig. 3, we observe that the time of execution for the brute force
algorithm increases exponentially as the number of features in the feature set
increases. Thus, though the brute force algorithm has a low time of execution
for small feature sets, it is extremely high for larger ones. This is why we
limit the experiment on the brute force to 25 features. The greedy algorithms
perform the best with respect to the execution time, which gradually increases
with increasing $m$. Though the proposed CE algorithm takes more time than the
greedy algorithm, its execution time is much lower than the brute force
approach. Also, the growth in run-time with increasing number of features is
marginal for the CE algorithm, thereby indicating the ability of the algorithm
to scale.

Figure 3: Execution time as a function of number of features $m$ with
$\lambda\rightarrow\infty$

####  VII-E2 Risk analysis

The risk score $R(\mathbf{v})$ is another important parameter to evaluate the
performance of the feature selection algorithms as we aim to minimize the risk
score by the optimal selection of features. The graphs for the risk scores of
the five different algorithms under consideration without any budget
constraint is plotted in Fig. 4. Since this scenario does not constrain the
budget, i.e., $\lambda\rightarrow\infty$, note that, the three greedy
algorithms will always choose all the features provided and thus, no
difference is expected in the performance (in terms of accuracy and risk
score) of the three different greedy approaches. We observe that the brute
force algorithm gives the best risk score since it performs an exhaustive
search over all possible combinations of the provided features. However, it
can also be observed that the cross entropy algorithm is close in performance
to that of the brute force method, and ultimately converges to the minimal
risk score of 1. Due to this convergence, it may be concluded that any feature
more than the first 63 (in the ranked order) is redundant in the
classification of the devices when using the cross-entropy algorithm. In
addition to this, it can also be observed that though the greedy algorithms
select all the features, they do not give the best results. This highlights
the necessity for the selection of an optimal set of features, and that the
selection of a higher number of features does not necessarily imply a better
risk score.

Figure 4: Risk score $R(\mathbf{v})$ as a function of number of features $m$
with $\lambda\rightarrow\infty$

###  VII-F Evaluation of algorithms under budget constraint

Figure 5: Risk score $R(\mathbf{v})$ as a function of the number of features $m$ for greedy algorithms with low and high budget $\lambda=\left\\{50,200\right\\}$ TABLE III: Comparison of Greedy Algorithms |  | Feature Budget
---
$\lambda=50$
| Feature Budget
---
$\lambda=200$
| CGA | VGA | RGA | CGA | VGA | RGA
Mean | 68.28 | 64.82 | 98.03 | 69.79 | 70.04 | 68.11
| Standard
---
Deviation
41.97 | 36.72 | 51.62 | 18.25 | 18.84 | 20.79

Comparison of greedy algorithms: We first compare the performance of the three
different greedy algorithms under budget constraint to determine the best-
performing greedy algorithm. We consider two cases: one with low budget for
features, $\lambda=50$, and another with high feature budget, $\lambda=200$.
We plot the risk scores of the three greedy algorithms Fig. 5.

Similar to previous experiments, each point on the X-axis on Fig. 5 denotes
the number of features given as input to the algorithms. However, to limit the
number of experiments, we start with nine features and add three features with
every new experiment. Therefore the point 30 on the X-axis means, 30 features
were given as input to the algorithms in the experiment, and the next point
corresponds to 33 features given as input. We observe that, all the three
greedy algorithms have similar performance when the budget is high. With high
budget, all features given at input can be selected for building the
classifier. However, this is not the case for lower budget—under tighter
budget constraint, we see that the three algorithms have different
performances as they choose different (subsets of) features from the given
list of input features. For easier comparison, we also provide the mean and
standard deviation of risk scores for each of the algorithms in Table III.
From these results, it can be seen than VGA performs better than the other two
under low budget (while all three have comparable performance under high
budget).

An interesting aspect to note in the low-budget case is that, the risk scores
do not decrease monotonically with increasing features provided at the input,
instead we see spikes in the risk score (Fig. 5). To understand this, let us
consider the first spike—the point on the X-axis where the first 24 ranked
features are added. Observe, all three algorithms experience a spike in the
risk score at this point. We present the analysis of VGA. Compared to the
previous point on the X-axis, i.e., the experiment corresponding to the first
21 features, the features mdns len mean, mdns duration, mdns num ans, and http
time mean were newly added to the classifier model by VGA, but more
importantly the features dns num qns , dns qry cls, http len mean, and tcp
keep alive were removed by the algorithm. We further used the SHAP method [37]
to estimate the contributions of different features in classifying the
devices. SHAP uses the concept of Shapley values from Game theory, to explain
the predictions of a machine learning model in a similar way as computing the
contributions of players in a game. Using the SHAP method, we note that, the
second-most important feature in the list of first 21 features was tcp keep
alive, and this was removed by VGA in the next experiment when three more
features were added. Besides, none of the MDNS related features that were
newly added by VGA were in the top eight most contributing features. We
observe a similar removal of important features in both RGA and CGA, thus
rendering them ineffective in selecting the most discriminative features to
minimize risk.

Based on the above experiments, to compare the performance of the greedy
methods with the CE algorithm, we select VGA as the candidate as it gives the
best performance among three greedy approaches.

Comparison of CE algorithm and VGA, for ranked and random ordering of
features: The risk score calculated is dependent on the ordering of the
features $\mathbf{f}$ and hence to test the performance of the algorithms, we
carry out the experiments for not only the ranked feature vector, but also for
randomly ordered features. The risk score $R(\mathbf{v})$ is a function of the
feature budget $\lambda$. Therefore, similar to the previous scenario, we
compare the risk score as a function of the number of features $m$ for a low
budget ($\lambda=50$) and high budget ($\lambda=200$). For CE, we set the
number of samples, $\eta=1000$ and $T_{\max}=500$; and compare CE with and VGA
algorithms. Fig. 6 plots the results when the input provided was the ranked
feature vector. CE is seen to outperform VGA under both low and high budgets.
The CE algorithm consistently achieves lower risk score with increasing
features, in comparison to VGA.

Under low budget constraint, we can clearly see that the CE algorithm
outperforms the greedy method for all feature lengths $m<70$. We observe a
similar trend in Fig. 7, when randomly ordered features are provided as input.
In this scenario, we evaluate the results for five different randomly ordered
feature sequences, and show the standard deviation of the risk scores
obtained. We observe that the risk score’s standard deviation is high for
small feature length, which is quite intuitive as the small number of features
(given as input) can be significantly different with every random sample. Thus
the risk score also varies with different input features provided. We also
note that the standard deviation of the risk scores of the CE algorithm is
always low (and extremely low for the the high-budget scenario), showing the
utility of the proposed algorithm.

Figure 6: Risk score $R(\mathbf{v})$ as a function of the number of features
$m$ with discrete $\lambda$ for CE and VGA algorithms for ranked features
Figure 7: Risk score $R(\mathbf{v})$ as a function of the number of features
$m$ with discrete $\lambda$ for CE and VGA algorithms for randomly ordered
features

Comparison of CE algorithm and VGA under varying budget: Finally, we compare
the risk scores for the CE algorithm for varying feature budgets. The features
are provided in ranked order. Since we now have two parameters to vary ($m$
and $\lambda$), for this set of experiments, we keep the numner of samples
$\eta=250$ and the number of iterations $T_{\max}=50$ for the CE algorithm.

We also conducted a similar experiment for VGA. In order to have a visual
comparative analysis of the performance of the CE algorithm with the greedy
algorithm, we take the difference between their risk scores for each $m$ and
$\lambda$. The resultant 3D graph for
$R_{\texttt{CE}}(\mathbf{v})-R_{\texttt{VGA}}(\mathbf{v})$ is plotted in Fig.
8. The part of the graph which is greater than 0 (above the $z=0$ plane)
denotes the conditions where the cross-entropy method has greater risk than
the greedy algorithm. The risk score achieved by CE is lower than that of VGA
for most cases, except when both, the budget is very low, and the number of
features is high. For large $m$ and a small $\lambda$, the CE algorithm
rejects most of the initial samples, prohibiting the algorithm to select the
optimal set of features possible, thus resulting in a high risk score.
However, on increasing the budget, the risk score is seen to decrease.
Besides, as seen in the previous set of experiments, the performance of CE can
be improved by increasing the number of samples and the number of iterations.

Figure 8: $R_{\texttt{CE}}(\mathbf{v})-R_{\texttt{VGA}}(\mathbf{v})$ as a
function of the number of features $m$ and the feature budget $\lambda$

##  VIII Conclusions

In this work, we motivated, defined and focused on the problem of feature
selection for IoT device classification considering the fact that there is a
budget constraint for features in practice. For this purpose, we also defined
the notion of risk of misclassification. To obtain the optimal solution to
this problem, one has to perform a combinatorial search over the solution
space. Therefore, we developed a cross entropy based algorithm for solving the
optimization problem. We carried out experiments using traffic of real IoT
devices; our experiments showed that not only is CE algorithm practical and
much faster than the brute force approach, it also obtains low risk score for
classification and performs better than than value-based greedy algorithm in
most cases.

## Acknowledgement

This research is supported by the National Research Foundation, Prime
Minister’s Office, Singapore under its Corporate Laboratory@University Scheme,
National University of Singapore, and Singapore Telecommunications Ltd.

## References

  * [1] Symantec, “ISTR 2019: Internet of Things Cyber Attacks Grow More Diverse,” 2019, https://www.symantec.com/blogs/expert-perspectives/istr-2019-internet-things-cyber-attacks-grow-more-diverse.
  * [2] M. Antonakakis, T. April, M. Bailey, M. Bernhard, E. Bursztein, J. Cochran, Z. Durumeric, J. A. Halderman, L. Invernizzi, M. Kallitsis, D. Kumar, C. Lever, Z. Ma, J. Mason, D. Menscher, C. Seaman, N. Sullivan, K. Thomas, and Y. Zhou, “Understanding the Mirai Botnet,” in _Proc. 26th USENIX Security Symposium_ , 2017, pp. 1093–1110.
  * [3] S. Herwig, K. Harvey, G. Hughey, R. Roberts, and D. Levin, “Measurement and Analysis of Hajime: a Peer-to-peer IoT Botnet,” in _Proc. NDSS_ , 2019.
  * [4] Y. Meidan, M. Bohadana, A. Shabtai, J. D. Guarnizo, M. Ochoa, N. O. Tippenhauer, and Y. Elovici, “ProfilIoT: A Machine Learning Approach for IoT Device Identification Based on Network Traffic Analysis,” in _Proc. ACM SAC_ , 2017, pp. 506–509.
  * [5] M. Miettinen, S. Marchal, I. Hafeez, N. Asokan, A.-R. Sadeghi, and S. Tarkoma, “IoT Sentinel: Automated device-type identification for security enforcement in IoT,” in _Proc. IEEE 37th International Conference on Distributed Computing Systems (ICDCS)_ , 2017, pp. 2177–2184.
  * [6] S. Dong, Z. Li, D. Tang, J. Chen, M. Sun, and K. Zhang, “Your Smart Home Can’t Keep a Secret: Towards Automated Fingerprinting of IoT Traffic with Neural Networks,” _CoRR_ , vol. abs/1909.00104, 2019. [Online]. Available: http://arxiv.org/abs/1909.00104
  * [7] S. Marchal, M. Miettinen, T. D. Nguyen, A. Sadeghi, and N. Asokan, “AuDI: Toward Autonomous IoT Device-Type Identification Using Periodic Communication,” _IEEE Journal on Selected Areas in Communications_ , vol. 37, no. 6, pp. 1402–1412, June 2019.
  * [8] A. Sivanathan, H. H. Gharakheili, F. Loi, A. Radford, C. Wijenayake, A. Vishwanath, and V. Sivaraman, “Classifying IoT Devices in Smart Environments Using Network Traffic Characteristics,” _IEEE Transactions on Mobile Computing_ , vol. 18, no. 8, pp. 1745–1759, Aug 2019.
  * [9] V. Thangavelu, D. M. Divakaran, R. Sairam, S. S. Bhunia, and M. Gurusamy, “DEFT: A Distributed IoT Fingerprinting Technique,” _IEEE Internet of Things Journal_ , vol. 6, no. 1, pp. 940–952, Feb 2019\.
  * [10] V. Sivaraman, S. Narayana, O. Rottenstreich, S. Muthukrishnan, and J. Rexford, “Heavy-Hitter Detection Entirely in the Data Plane,” in _Proc. ACM Symposium on SDN Research, (SOSR ’17)_ , 2017, pp. 164–176.
  * [11] B. Claise, B. Trammell, and P. Aitken, “Specification of the IP flow information export (IPFIX) protocol for the exchange of flow information,” Internet Requests for Comments, RFC Editor, STD 77, 2013. [Online]. Available: http://www.rfc-editor.org/rfc/rfc7011.txt
  * [12] N. Apthorpe, D. Reisman, and N. Feamster, “A Smart Home is No Castle: Privacy Vulnerabilities of Encrypted IoT Traffic,” in _Workshop on Data and Algorithmic Transparency (DAT’16)_ , 2016.
  * [13] N. Weaver, C. Kreibich, and V. Paxson, “Redirecting DNS for ads and profit,” in _USENIX Workshop on Free and Open Communications on the Internet (FOCI)_ , 2011.
  * [14] S. Siby, M. Juárez, C. Díaz, N. Vallina-Rodriguez, and C. Troncoso, “Encrypted DNS -> privacy? A traffic analysis perspective,” in _Proc. NDSS_ , 2020.
  * [15] D. M. Divakaran, S. Le, Y. S. Liau, and V. L. L. Thing, “SLIC: Self-Learning Intelligent Classifier for Network Traffic,” _Computer Networks_ , vol. 91, pp. 283–297, 2015.
  * [16] L. Bilge, D. Balzarotti, W. Robertson, E. Kirda, and C. Kruegel, “DISCLOSURE: Detecting botnet command and control servers through large-scale netflow analysis,” in _Proc. ACSAC_ , 2012.
  * [17] I. Nevat, D. M. Divakaran, S. G. Nagarajan, P. Zhang, L. Su, L. L. Ko, and V. L. L. Thing, “Anomaly Detection and Attribution in Networks With Temporally Correlated Traffic,” _IEEE/ACM Transactions on Networking_ , vol. 26, no. 1, pp. 131–144, Feb 2018.
  * [18] Q. P. Nguyen, K. W. Lim, D. M. Divakaran, K. H. Low, and M. C. Chan, “GEE: A Gradient-based Explainable Variational Autoencoder for Network Anomaly Detection,” in _Proc. IEEE Conference on Communications and Network Security (CNS)_ , June 2019, pp. 91–99.
  * [19] T. D. Nguyen, S. Marchal, M. Miettinen, M. H. Dang, N. Asokan, and A. Sadeghi, “Dïot: A federated self-learning anomaly detection system for iot,” in _Proc. IEEE ICDCS_ , 2019.
  * [20] Z. Shamsi, A. Nandwani, D. Leonard, and D. Loguinov, “Hershel: single-packet OS fingerprinting,” in _ACM SIGMETRICS Performance Evaluation Review_ , vol. 42, no. 1. ACM, 2014, pp. 195–206.
  * [21] K. Gao, C. Corbett, and R. Beyah, “A passive approach to wireless device fingerprinting,” in _2010 IEEE/IFIP International Conference on Dependable Systems & Networks (DSN)_. IEEE, 2010, pp. 383–392.
  * [22] R. R. Maiti, S. Siby, R. Sridharan, and N. O. Tippenhauer, “Link-layer device type classification on encrypted wireless traffic with COTS radios,” in _Proc. ESORICS_ , 2017, pp. 247–264.
  * [23] N. Apthorpe, D. Reisman, S. Sundaresan, A. Narayanan, and N. Feamster, “Spying on the smart home: Privacy attacks and defenses on encrypted iot traffic,” _arXiv preprint arXiv:1708.05044_ , 2017.
  * [24] K. Yang, Q. Li, and L. Sun, “Towards automatic fingerprinting of IoT devices in the cyberspace,” _Computer Networks_ , vol. 148, pp. 318–327, 2019.
  * [25] F. J. Damerau, “A Technique for Computer Detection and Correction of Spelling Errors,” _Commun. ACM_ , vol. 7, no. 3, p. 171–176, Mar. 1964. [Online]. Available: https://doi.org/10.1145/363958.363994
  * [26] S. Ma and J. Huang, “Penalized feature selection and classification in bioinformatics,” _Briefings in bioinformatics_ , vol. 9, no. 5, pp. 392–403, 2008.
  * [27] R. Tavenard and S. Malinowski, “Cost-aware early classification of time series,” in _Joint European Conference on Machine Learning and Knowledge Discovery in Databases_. Springer, 2016, pp. 632–647.
  * [28] Y. Zhang, D.-w. Gong, and J. Cheng, “Multi-objective particle swarm optimization approach for cost-based feature selection in classification,” _IEEE/ACM transactions on computational biology and bioinformatics_ , vol. 14, no. 1, pp. 64–75, 2015.
  * [29] F. Min, Q. Hu, and W. Zhu, “Feature selection with test cost constraint,” _International Journal of Approximate Reasoning_ , vol. 55, no. 1, pp. 167–179, 2014.
  * [30] V. Bolón-Canedo, I. Porto-Díaz, N. Sánchez-Maroño, and A. Alonso-Betanzos, “A framework for cost-based feature selection,” _Pattern Recognition_ , vol. 47, no. 7, pp. 2481–2489, 2014.
  * [31] S. Maldonado, J. Pérez, and C. Bravo, “Cost-based feature selection for support vector machines: An application in credit scoring,” _European Journal of Operational Research_ , vol. 261, no. 2, pp. 656–665, 2017.
  * [32] S. Asmussen, D. P. Kroese, and R. Y. Rubinstein, “Heavy tails, importance sampling and cross–entropy,” _Stochastic Models_ , vol. 21, no. 1, pp. 57–76, 2005.
  * [33] P.-T. De Boer, D. P. Kroese, S. Mannor, and R. Y. Rubinstein, “A tutorial on the cross-entropy method,” _Annals of operations research_ , vol. 134, no. 1, pp. 19–67, 2005.
  * [34] M. Collins, S. Dasgupta, and R. E. Schapire, “A generalization of principal components analysis to the exponential family,” in _Advances in neural information processing systems_ , 2002, pp. 617–624.
  * [35] D. M. Divakaran, K. L. Ling, S. Le, and V. Thing, “REX: Resilient and Efficient Data Structure for Tracking Network Flows,” _Computer Networks_ , vol. 118, pp. 37–53, 2017.
  * [36] B. A. Desai, D. M. Divakaran, I. Nevat, G. W. Peter, and M. Gurusamy, “A feature-ranking framework for iot device classification,” in _11th International Conference on Communication Systems & Networks (COMSNETS)_, 2019, pp. 64–71.
  * [37] S. M. Lundberg and S.-I. Lee, “A Unified Approach to Interpreting Model Predictions,” in _Advances in Neural Information Processing Systems 30 (NIPS 2017)_ , I. Guyon, U. V. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett, Eds., 2017, pp. 4765–4774.

## Appendix: Feature cost

In this section we demonstrate how feature costs are estimated for a given IoT
device. We defined the cost vector $\mathbf{c}$ to indicate the cost
associated with each of the extracted features. The feature cost is divided
into three different components. First, we analyze the memory required for the
extraction of the features from the network traffic. Next, we focus on the
computational complexity of the algorithm required for extracting the feature.
And lastly, we analyze the intrusiveness of a feature into the privacy aspects
of a device or user. For example, let us consider the feature dns_num_ans,
which denotes the the number of answers returned for DNS queries. While only a
register is required to store the (running) value of this feature, a small
buffer has to be maintained to temporarily store (unprocessed) DNS answers
extracted from packet payloads (to absorb traffic bursts); therefore, we
define the memory cost as medium. Similarly, this feature is computed by
simple additions to the counter in the register. Therefore we can assume a low
computational complexity. Finally, since the feature is extracted from the DNS
responses (i.e., packet payload), which can leak considerable information
(e.g., see [13]), we assign a high privacy cost to the feature. Table IV
provides the logic we have used to define the three cost components for
extracting any given feature from network traffic. To define the total cost of
extracting a feature, we take the median of all three costs (memory, compute
and privacy).

TABLE IV: Cost logic considered for experiments

# | Parameters | Cost
---|---|---
memory | compute power | privacy
1 |  | Single register
---
(constant memory)
| Counters
---
(e.g., $\min,\max$, etc.)
| Features extracted
---
from packet headers
low
2 |  | Small buffer
---
(e.g., queue)
| Maintenance of
---
hash tables
| Extraction of
---
application data (e.g., URL)
medium
3 |  | Hash table or
---
multiple registers
| Pattern matching
---
or sorting
| Features extracted from
---
packet payloads
high