Cost-aware Feature Selection for IoT Device Classification

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.

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 solutionsuch 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 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) 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) 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) 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 waveletbased 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 nondominated 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.

A. Traffic and features
Let D denote the set of devices considered for classification in a network; furthermore, let n = |D|. Corresponding to a device d ∈ 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 T d denote the traffic of device d.
Each unit of traffic (a connection or a session) of T d is processed to extract the feature vector.
We use f to represent the m features of interest in our problem: Denote by E(.) the function for feature extraction. For an input traffic data T d of device d, E(T d ) produces a matrix S d of extracted features corresponding to all units of traffic: where s d j,k denotes the k th feature extracted from the j th traffic unit of device d. To generalize, we use s to denote an extracted feature vector of a device. Obviously, s is of length m. Note that, S d , ∀d ∈ D form the dataset X used for training and testing the classification model. We use X train and X test to denote the partition of the dataset for, training and testing, respectively.

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 E f k (.) the function to extract feature f k , 1 ≤ k ≤ m. Therefore the cost of extracting a feature f k will be denoted by: represented using an n×n confusion matrix X M that is processed to obtain relevant performance metrics, such as precision and recall. The element in the i th row and j 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 d is the predicted device and d is the actual device, then we define the probability of classifying d = j as d = i is given as: For a classification model M, we define an n × n misclassification matrixP M with elements p i,j 's. For simplicity, henceforth, we drop the subscript and denote the misclassification matrix as P.

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.
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.

E. Cyber Risk
Using these definitions, we define the cyber risk of the model. While 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 v to indicate whether a feature is selected or not.
Next, we define cyber risk. Given a classifier M, loss matrix L, feature budget λ, the extracted data (for the selected features indicated by v) X v , and a feature selection vector v, the cyber 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(v). Formally, the cyber risk score or the risk score, based on the set of selected features (captured by 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:

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 P for a given feature vector f , and the loss matrix L, we aim to find the optimal feature vector (via v) which minimizes the cyber risk score R(v), under a budget constraint λ.
Thus, the optimization problem may be defined as: where R(v) is as defined in Eq. 4.
The optimization problem presented in Eq. 5 has some unique properties making it a nontrivial problem to solve. Firstly, the cyber risk function R(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(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: . 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 (v ∈ {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 } m k=1 , 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: S1 Generate samples: generate η independent samples of binary sets given by S2 Selection of elite samples: from those η samples, we select only those samples which satisfy the budget constraint (ie. c T w [i] ≤ λ) to obtain a subset of η ≤ η 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 ρ. This choice is indicated S3 Estimation of parameters: using only this subset of elite samples, we re-estimate the parameters of the Bernoulli random variable {p k } m k=1 via the MLE, given by 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 ρ 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 α ∈ [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 ≤ k ≤ m, denotes whether the k 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 ).  Step 1:

4
Generate η independent samples of binary sets given by Step 2: ComputeP, from X as given in Eq. 2.

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.

A. Brute Force Method
The brute force approach is presented in Algorithm 2. The algorithm selects each combination of the features (via the vector v), and evaluates the risk score if the cost of the features is within the budget constraint (λ). 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.

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 v) for classification. 2) 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 f . For

Algorithm 2: Brute Force Feature Selection
Input: X train , X test , c, λ, f , M,L ComputeP, from X as given in Eq.  12 ComputeP, from X as given in Eq. 2 13 Compute R(v) according to Eq. 4 14 return v the value of a feature f i as: 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 O(m log m + m × C(m; Ψ)).

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.

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).

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:   extracted, and no private information (e.g., visited websites) is extracted. Therefore, the cost of extracting connection length is medium.

C. Loss matrix, 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 Taking every device pair, we follow this definition to derive the values for the loss matrix 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 × 0 + 1 = 1. But if it classifies the device as Samsung (Smart things) Hub, then the loss l i,j = 2 * 1 + 0 = 2.

D. Comparison of classifiers
The cyber risk score R(v) of a feature vector 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 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 We also plot the accuracy of the different classifiers in Fig. 2; all of them achieve high F 1scores. Since Decision tree classifier has much less time of execution, while also having high F 1 -score, henceforth we use Decision tree for the rest of the experiments to evaluate cost-aware feature selection algorithms.  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 f (obtained via ranking), and select the first nine features from it asf = [f 1 , f 2 , . . . , f 9 ]. 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 asf = [f 1 , f 2 , . . . , f t+9 ] ; t = 0, 1, 2, . . . , 61, where |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.   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.
2) Risk analysis: The risk score R(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., λ → ∞, 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.

F. Evaluation of algorithms under budget constraint
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, λ = 50, and another with high feature budget, λ = 200. We plot the risk scores of the three greedy algorithms 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) 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 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(v) is a function of the feature budget λ. Therefore, similar to the previous scenario, we compare the risk score as a function of the number of features m for a low budget (λ = 50) and high budget (λ = 200). For CE, we set the number of samples, η = 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.
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 λ), for this set of experiments, we keep the numner of samples η = 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 λ. The resultant 3D graph for R CE (v) − R VGA (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 λ, 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.

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.

APPENDIX: FEATURE COST
In this section we demonstrate how feature costs are estimated for a given IoT device. We defined the cost vector 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).