Mahmoud Abdelsalam
email: mahmoud.abdelsalam@utsa.edu

Ram Krishnan
email: ram.krishnan@utsa.edu

Ravi Sandhu
email: ravi.sandhu@utsa.edu

Online Malware Detection in Cloud Auto-Scaling Systems Using Shallow Convolutional Neural Networks

Keywords: Security, Auto-Scaling, Online Malware Detection, Cloud IaaS, Deep Learning, Convolutional Neural Networks

This paper introduces a novel online malware detection approach in cloud by leveraging one of its unique characteristics-auto-scaling. Auto-scaling in cloud allows for maintaining an optimal number of running VMs based on load, by dynamically adding or terminating VMs. Our detection system is online because it detects malicious behavior while the system is running. Malware detection is performed by utilizing process-level performance metrics to model a Convolutional Neural Network (CNN). We initially employ a 2d CNN approach which trains on individual samples of each of the VMs in an auto-scaling scenario. That is, there is no correlation between samples from different VMs during the training phase. We enhance the detection accuracy by considering the correlations between multiple VMs through a sample pairing approach. Experiments are performed by injecting malware inside one of the VMs in an auto-scaling scenario. We show that our standard 2d CNN approach reaches an accuracy of 90%. However, our sample pairing approach significantly improves the accuracy to 97%.

Introduction

Cloud computing characteristics [START_REF] Mell | The nist definition of cloud computing[END_REF] enable novel attacks and malware [START_REF] Dahbur | A survey of risks, threats and vulnerabilities in cloud computing[END_REF][START_REF] Gholami | Security and privacy of sensitive data in cloud computing: a survey of recent developments[END_REF][START_REF] Grobauer | Understanding cloud computing vulnerabilities[END_REF][START_REF] Gruschka | Attack surfaces: A taxonomy for attacks on cloud services[END_REF][START_REF] Jensen | On technical security issues in cloud computing[END_REF][START_REF] Xiao | Security and privacy in cloud computing[END_REF]. In particular, cloud has become a major target for malware developers since a large number of Virtual Machines (VMs) are similarly configured. Automatic provisioning and auto configuration tools have led to the widespread use of auto-scaling, where VMs scalein/out on demand. Applications utilizing auto-scaling architectures 4 is one of the most prevalent in cloud. As a result, a malware that infects one VM can be easily reused to infect other VMs that are similarly configured or imaged. To that end, cloud has become a very interesting target to most attackers.

In malware analysis, files are scanned before execution on the actual system either through static or dynamic analysis. Once an executable/application is deemed to be benign, it executes on the system without further monitoring. Such methods often fall short in the case of cloud malware injection [START_REF] Gruschka | Attack surfaces: A taxonomy for attacks on cloud services[END_REF], a threat where an attacker injects a malware to manipulate the victim's VMs, because the initial scan is usually bypassed or malware is injected into an already scanned benign application. Consequentially, the need for online malware detection, where you continuously monitor the whole system for malware, has become a necessity.

Few works [START_REF] Abdelsalam | Clustering-based IaaS cloud monitoring[END_REF][START_REF] Dawson | Phase space detection of virtual machine cyber events through hypervisor-level system call analysis[END_REF][START_REF] Pannu | Aad: Adaptive anomaly detection system for cloud computing infrastructures[END_REF][START_REF] Wang | EbAT: online methods for detecting utility cloud anomalies[END_REF][START_REF] Watson | Malware detection in cloud computing infrastructures[END_REF] exist in the domain of online malware detection in cloud. Typically, machine learning is used in online malware detection. First, a set of system features are selected and used to build a model. Then, this model is used for malware detection. Some works use system calls while others use performance metrics. Although such works target cloud systems in some sense, there is no real difference between standard online malware detection methods and cloud-specific methods except in the features selected for machine learning, where cloud-specific methods restrict the selection of features to those that can only be fetched through the hypervisor. One can argue that such works focus on malware detection in VMs running on a hypervisor.

However, what makes cloud computing powerful is the novel characteristics that they support [START_REF] Mell | The nist definition of cloud computing[END_REF] such as on-demand self-service, resource pooling and rapid elasticity via auto-scaling. In this paper, we explore malware detection approaches that can leverage specific cloud characteristics. In particular, we focus on auto-scaling. The high-level idea is that in an auto-scaling scenario, where multiple VMs are spawned based on demand, each of those VMs is typically a replica. This means the "behavior" of those VMs need to closely correspond with each other. If a malware were to be injected online into one of those VMs, the infected VM's behavior will likely deviate at some point in time. Our work seeks to detect such deviations when they occur. A sophisticated attacker can attempt to simultaneously inject malware into multiple VMs, which could induce similar behavior across those VMs, and thereby escape our detection mechanisms. This is an interesting challenge and we plan this for future work. This paper focuses on malware detection when exactly one of the VMs in an auto-scaling environment is compromised.

In terms of the approach, first, we introduce and discuss a cloud-specific online malware detection approach. It applies 2d CNN, a deep learning approach, for online malware detection by utilizing system process-level performance metrics. A 2d input matrix/image is represented as the unique processes × selected features. We assume that similarly configured VMs should have similar behavior, so we train a single model for VMs that belongs to the same group such as the group of application servers in a 3-tier auto-scaling web architecture of web servers, application servers and database servers. Next, we introduce a new approach that leverages auto-scaling. Here, we consider correlations between multiple VMs by pairing samples from pairs of those VMs. Samples collected at the same time from multiple VMs are paired and fed into CNN as a single sample.

CNN is chosen because of its simplicity and training speed as opposed to other deep learning approach (e.g. Recurrent Neural Networks). Also, for the sake of practicality, we show that even a shallow CNN (LeNet-5) trained only for a few epochs can be effective for online malware detection. In summary the contributions of this paper are two-fold:

-We introduce a 2d CNN based online malware detection approach for multiple VMs.

-We improve 2d CNN by introducing a new approach by pairing samples from different VMs to accommodate for correlations between those VMs.

To the best of our knowledge, our work is the first to leverage cloud-specific characteristics for online malware detection. The remainder of this paper is organized as follows. Section 2 discusses related work on cloud-specific online malware detection. Section 3 explains the key intuition about the idea presented. Section 4 outlines the methodology including the architecture of the CNN models. Section 5 describes the experiments conducted and results. Finally, Section 6 summarizes and concludes this paper.

Related Work

Many research works address the problem of online malware detection using different set of features and machine learning algorithms. Some works [START_REF] Dawson | Phase space detection of virtual machine cyber events through hypervisor-level system call analysis[END_REF][START_REF] Dini | Madam: a multi-level anomaly detector for android malware[END_REF][START_REF] Luckett | Neural network analysis of system call timing for rootkit detection[END_REF] focus on using systems calls while others [START_REF] Alazab | Zero-day malware detection based on supervised learning algorithms of api call signatures[END_REF][START_REF] Pirscoveanu | Analysis of malware behavior: Type classification using machine learning[END_REF][START_REF] Tobiyama | Malware detection with deep neural network using process behavior[END_REF] focus on using API calls. Others [START_REF] Ozsoy | Malware-aware processors: A framework for efficient online malware detection[END_REF][START_REF] Xu | Malware detection using machine learning based analysis of virtual memory access patterns[END_REF] focus on using memory features or performance counters [START_REF] Demme | On the feasibility of online malware detection with performance counters[END_REF].

Only a few research works address the problem of cloud malware detection since many of the standalone malware detection approaches work for detecting malware in single VMs in the cloud as well. Most, if not all, of the cloud-specific malware detection techniques falls under the online malware detection category (including anomaly detection approaches). Furthermore, they all focus on extracting features from the hypervisor since it adds another security layer.

Dawson et al. [START_REF] Dawson | Phase space detection of virtual machine cyber events through hypervisor-level system call analysis[END_REF] focus on rootkits and intercept system calls through the hypervisor to be used as features. Their system call analysis is based on a non linear phase-space algorithm to detect anomalous behavior. Evaluation is based on the dissimilarity among phase-space graphs over time.

Wang [START_REF] Wang | EbAT: online methods for detecting utility cloud anomalies[END_REF] introduced Entropy based Anomaly Testing (EbAT), an online analysis system of multiple system-level metrics (e.g. CPU utilization and memory utilization) for anomaly detection. The proposed system used a light-weight analysis approach and showed a good potential in detection accuracy and monitoring scalability. However, the evaluation used did not show pragmatic and realistic cloud scenarios.

Azmandian et al. [START_REF] Azmandian | Virtual machine monitor-based lightweight intrusion detection[END_REF] propose an anomaly detection approach where all features are extracted directly from the hypervisor. Various performance metrics are collected per process (e.g., disk i/o, network i/o) and unsupervised machine learning techniques like K-NN and Local Outlier Factor (LOF) are used.

Classification of VMs is used for anomaly detection. Pannu et al. [START_REF] Pannu | Aad: Adaptive anomaly detection system for cloud computing infrastructures[END_REF] propose an adaptive anomaly detection system for cloud. It focused mainly on various faults within the cloud infrastructure. Although this work is not directly addressing malware, such technique is valid for malware detection since malware can cause faults in VMs, thus worth mentioning. It used a realistic testbed experimentation comprising 362-node cloud in a university campus. The results showed a good potential with over 87% of anomaly detection sensitivity. One of the drawbacks of this work lies within using twoclass SVM. Therefore, it suffers from a data imbalance problem (where there is an imbalance of data from various classes during the training period), which led to several false classification of new anomalies.

The work by Watson et al. [START_REF] Watson | Malware detection in cloud computing infrastructures[END_REF] is similar to [START_REF] Pannu | Aad: Adaptive anomaly detection system for cloud computing infrastructures[END_REF] but directly addressed detecting malicious behavior in the cloud. It tried to overcome the drawbacks in [START_REF] Pannu | Aad: Adaptive anomaly detection system for cloud computing infrastructures[END_REF] by using one class Support Vector Machine (SVM) for detection of malware in cloud infrastructure. The approach gathers features at the system and network levels. The system level features are gathered per process which includes memory usage, memory usage peak, number of threads and number of handles. The network level features are gathered using the CAIDA's CoralReef5 tool. The study shows high accuracy results; however, it uses known-to-be highly active malware that easily skew the system's resource utilization (e.g., by forking many processes).

In our earlier work [START_REF] Abdelsalam | Clustering-based IaaS cloud monitoring[END_REF], we showed that malware can be effectively detected using black-box VM-level performance and resource utilization metrics (such as CPU and memory utilization). Although, the work showed promising results for highly active malware (e.g., ransomware), it is not as effective for low-profile malware that would not impact black-box level resource utilization significantly. Subsequently, we introduced a CNN based online malware detection method for low-profile malware [START_REF] Abdelsalam | Malware detection in cloud infrastructures using convolutional neural networks[END_REF]. This work utilized resource utilization metrics for various processes within a VM. The method was able to detect low-profile malware with accuracy of 90%. Although, this work yielded good results, it targeted a single VM much like other related works. Unlike our prior work and other related works, this paper targets malware detection when multiple VMs are running, while leveraging specific cloud characteristics such as auto-scaling.

Key Intuition

In classification-based process-level online malware detection methods, a machine learning model is trained on benign and malicious samples of processes where the goal is to classify a new input sample. The data collection phase, usually, works by running a VM for some time (benign phase) and then injecting a malware (malicious phase) while logging the required data. This is referred to as a single run. The data set includes multiple runs with same/different malware which is later divided into training and test data sets. In other words, given sample X at time t (X t ), the task is to compare X t to previously seen samples of the training data set. For a single run, we deal with individual samples of a single VM. Thus, we refer to this approach as Single VMs Single Samples (SVSS) which is shown in Figure 1.

SVSS can work in an auto-scaling scenario where we have a trained model for each auto-scaling tier; however, input samples will lose some information. Note that multiple runs of a single VM is not the same as multiple VMs running at the same time. The reason depends mostly on the architecture in place. If a VM has some effects over another VM, then input samples from single VM in multiple runs will lose this information. To that end, we extend SVSS and build an auto-scaling testbed where we can learn from multiple VMs running at the same time. We refer to it as Multiple VMs Single Sample (MVSS). The MVSS approach, however, has a disadvantage in the context of process-level performance metrics. Processes have a very dynamic nature, meaning spikes are always happening. These spikes are mostly due to sudden events or traffic surges. For example, Figure 2 shows two different runs of the same process for the number of voluntary context switches. No malware is running inside either of the two VMs. During the training phase, two patterns will be learned, a smooth recurring up and down pattern and a pattern where there can be some spikes. During the testing phase, if either pattern is seen, it will be regarded as benign.

On the other hand, Figure 3 shows one run of the same unique process in 10 VMs (belongs to the same group of VMs in an auto-scaling scenario). VMs are running at the same time in an auto-scaling scenario. The red colored process belongs to a VM where a malware was injected. There are two major spikes in the figure. The first spike happened in the same unique process of all the VMs. If one of the processes did not have that spike and it was classified as benign, it might be a misclassification since such spike should happen to all VMs at the same time. The second spike (caused by the malware injected) is only observed in the infected VM which should be classified as malicious. In simple words, observing a noticeable enough spike by a particular process should be classified as malicious (i.e., second spike). However, sudden behavior changes can happen (i.e., first spike) and flagging an observed spike always as malicious can cause many misclassifications. As such, considering multiple VMs, spikes that are observed in a particular process in all VMs at the same time shouldn't be classified as malicious since it can be caused by any sudden change in behavior (e.g. sudden increase in the number requests to web server). MVSS and SVSS will lose such correlations between VMs since they learn from individual samples regardless the scenario. Consequentially, we introduce a new approach where the correlation of multiple VMs is utilized by pairing samples (at the same time). In other words, given sample X of VM vm i at time t (X vmi t ), the idea is to compare X vmi t to previously seen paired samples of multiple VMs. We refer to this approach as Multiple VMs Paired Samples (MVPS).

Methodology

Detailed explanation of CNN is left out of this paper. However, it will suffice to say that CNN is a deep learning approach used extensively in image recognition. Hence, it takes 2d images as input. In our work, the first dimension represents the processes in the system and the second dimension represents the features collected for each process. Consider a sample X at a particular time t, that records n features (performance metrics) per process for m processes in VM vm, such that:

X vmt =        f 1 f 2 . . . f
      
Table 1 shows the process-level performance features which can be fetched through the hypervisor. CNN requires a specific process to remain in the same row (in the input matrix) for all inputs in a single run. This means that process ID (PID) can not simply be used directly. Processes get killed and get created frequently so a PID identifying one process might identify a different process later on. For that reason, we define a unique process which is identified by three elements: process name (name), command line used to execute the process (cmd) and hash of binary executable (if applicable). In addition, unique processes help in smoothing the number of processes in a highly active server since most malware creates new non-unique processes. show two different experiments (each with a different malware) where the number of total standard processes are compared to the number of unique processes. Red portions are the start of malware execution. As shown in the figure, the total number of processes in such a highly active VM does not help much in revealing the malware behavior as opposed to the number of unique processes. Throughout this paper the terms process and unique process are used interchangeably where both refer to unique process.

Malware Detection in Multiple VMs using Single Samples (MVSS)

This is a relatively straight-forward task. We target multiple VMs in an auto-scaling scenario. Figure 5 shows the approach used in MVSS. In MVSS we have samples X vmi tk from multiple VMs running at the same time, where X is a sample of VM vm i at time t k . Samples from many runs are collected and are fed to the CNN optimizer where the learning process takes place. Then the trained CNN model is used for predictions. The MVPS approach is inspired by the duplicate questions problem in online Q&A forums like Stack Overflow and Quora. The problem focuses on determining semantic equivalence between questions pairs. It is a binary classification problem where two questions Q 1 and Q 2 are given and the task is to determine whether they are duplicates.

Based on the aforementioned assumption that VMs that belong to the same group should behave similarly, we use the same analogy to tackle our problem. To that end, we change the formalization of our problem by using the above duplicate questions problem concept except, in our case, we are given two samples X vmi tk and X vmj tk from different VMs, where X vmi tk is a 2d matrix (image in CNN terminology) that belongs to vm i at time t k and X vmj tk is a 2d matrix that belongs to vm j at the same time t k . Figure 6 shows the pairing samples approach. Our goal is to find whether X vmi tk and X vmj tk are duplicates (similar). This is done by pairing the two samples as an input to CNN. Two samples are considered similar if they are benign, whereas two samples are considered not similar if either one of them is malicious (red bordered samples are malicious).

By pairing samples, we are actually taking into account the correlations between samples of different VMs. This is due to the fact that CNN works by finding spatial correlation within images. MVPS works in an auto-scaling scenario where there are at least two VMs of the same group. Note that it is important that we only pair samples of the same time as pairing samples of different times might have completely different values if the behavior of the VMs has changed over time. For example, a web server handling one request per sec at time t 1 will have a completely different behavior than a web server handling 100 requests per sec at time t 2 . Consequentially, pairing two samples taken at two different times might mislead the classifier if the behavior of the VMs changed over time.

Pairing all samples is a very time consuming operation. In addition, that will introduce a class imbalance problem since we are only infecting a single VM. Although, we believe that infecting multiple VMs is hard to occur at the exact same time in practice, not the least because a malware needs time to infect other similarly configured VMs. Like mentioned earlier we set this for future work. Consequentially, as shown in Figure 6, we pair a malicious sample with all benign samples from other machines at a particular time. On the other hand, we pair each benign sample sequentially with the sample of the following VM.

Experiment Setup and Results

CNN Model Architecture

A deep CNN model would require considerably larger processing power. In reality, this might not be affordable. For the sake of practicality, we chose to work with a shallow CNN. We show that even a shallow CNN can achieve near optimal results in our pairing approach. Figure 7 shows the CNN model used in this work. We chose LeNet-5 [START_REF] Lecun | Gradient-based learning applied to document recognition[END_REF] CNN model. Although, it is currently by no means one of the state-of-the-art CNN models, its shallowness makes it one of the best candidates in practice. Note that in the context of online malware detection, the model might need to be trained multiple times based on the deployed workloads in place. For example, a 3-tier web architecture and a Hadoop architecture might need different trained models.

The CNN model receives a standardized 2d matrix. Lenet-5 CNN consists of 7 layers (excluding the input layer). The input layer is a 2d matrix of 120 × 45 (120 × 90 for MVPS), representing a sample of maximum 120 processes and 45 features. For empty processes (i.e., processes that do not run at the start time but might start in the future), rows are padded with zeros. The first layer is a convolutional layer with 32 kernels of size 5 × 5 with zero padding ending. This results in a 32 feature maps of size 120 × 45. The second layer is a max pool layer of size 2 ×2 which downsizes each dimension by a magnitude of 2, resulting in a 32 feature maps of size 60 × 23 (60 × 45 for MVPS). The third layer, another convolutional layer with 64 kernels of size 60 × 23, is followed by a max pool layer which results in 64 down sized feature ReLU activation is used after every convolutional and fully connected layer (excluding the last fully connected layer). Adam Optimizer, a stochastic gradient descent with automatic learning rate adaptation, is used to train the model. Adam optimizer learning rate is a maximum change threshold to control how fast the learning process can be (set to 1e -5). The optimizer works by minimizing the loss function (mean cross entropy). Random grid search is used to tune the CNN parameters (e.g., mini batch size).

Experimental Setup

Our experiments were conducted on an Openstack testbed. Figure 8 shows the 3-tier web architecture built on top of our testbed, with auto-scaling enabled on the web and application server layers. The scalability policy is based on the average CPU utilization of the total VMs of each tier (scalability group). It scales-out if the average CPU utilization is above 70% and scales-in if the average CPU utilization is less than 30%. The number of servers spawned in each tier were between 2 and 10 based on the traffic

Period of malware activity

Collect 28 different process performance metrics every 10 seconds for ≃ 100 processes The data collection process is shown in Figure 9. Each of our experiments was 1 hour long. The first 30 minutes is the clean phase. The second 30 minutes is malicious phase where a malware is injected. A set of 113 malware were used for each of the different experiments. Malware binaries were randomly obtained from VirusTotal7 . All firewalls were disabled and an internet connection was provided to avoid any hindrance to the malware's malicious intentions. Samples were collected at 10 second intervals, so during a single experiment 360 samples were collected for one VM.

Evaluation

We use four evaluation metrics.

P recision =

T P T P + F P Recall = T P T P + F N Accuracy = T P + T N T P + T N + F P + F N F score = 2 × P recision × Recall P recision + Recall Precision is the number of correct malware predictions. Recall is the number of correct malware predictions over the number of true malicious samples. Accuracy is the measure of correct classification. F score is the harmonic mean of precision and recall. True Positive (T P ) refers to malicious activity that occurred and was correctly predicted. False Positive (F P ) refers to malicious activity that did not occur but was wrongly predicted. True Negative (T N ) refers to malicious activity that did not occur and was correctly predicted. False Negative (F N ) refers to malicious activity that occurred but was wrongly predicted.

MVSS and MVPS Results

Like most standard machine learning classification problems, data was split into three sets: training (60%), validation (20%) and testing (20%) sets. We split on the 113 experiments to 67, 23 and 23 respectively. This ensures that validation and testing phases are Figure 10 shows the results of MVSS optimized classifier. The optimized classifier yields accuracy of 90% while precision, recall and fscore are 85% on the test data set. This approach achieved good results compared to the similar simple 2d CNN approach in [START_REF] Abdelsalam | Malware detection in cloud infrastructures using convolutional neural networks[END_REF]. There are two reasons for this improvement. First, increasing the number of data (113 malware experiments as opposed to 25). Second, using data from multiple VMs as opposed to a single VM; however, we still had to filter part of the data to balance our data sets (i.e., balance the ratio of benign to malicious samples).

Figure 11 shows the results of MVPS optimized classifier. There is a significant increase in the four evaluation metrics when compared to the MVSS classifier. The optimized chosen MVPS classifier had a highest accuracy of 98.2% during the validation phase. It yielded a 96.9% accuracy on the test data set. Fscore, recall and precision all jumped to 91% on the test data set. The main reason for this high improvement is that the MVPS approach finds correlations between the multiple VMs running at the same time which is very beneficial in an auto-scaling scenario.

In both cases, mini-batch size of size 64 and learning rate of 1e -5 yielded the best results. The CNN model was trained only for 20 epochs. Note that we do not use a dropout layer (to avoid over-fitting) since it is not useful when using a shallow CNN trained for only a few epochs.

Conclusion And Future Work

In this paper, we introduced an online malware detection approach to leverage the behavior correlation between multiple VMs in an auto-scaling scenario. The approaches introduced used 2d CNN for malware detection. First, we introduced the MVSS method which targets multiple VMs using single individual samples. MVSS achieved good results with an accuracy of 90%. Then, we introduced MVPS which targets multiple VMs using paired samples. MVPS takes the previous approach a step forward by pairing samples from multiple VMs which helps in finding correlations between the VMs. MVPS showed a considerable improvement over MVSS with an accuracy of 96.9%. In the future, we plan to use different use case scenarios such as Hadoop and Containers as well as perform an analysis using different CNN models architecture. We also plan to perform an analysis to evaluate the effectiveness of ordering the processes and features in the input matrix. Finally, we plan to develop techniques to handle the situation when multiple VMs are infected simultaneously by an attacker. One direction, instead of using pairs of samples, is to use tuples of samples (3-tuple, 4-tuple or more).

Fig. 1 :Fig. 2 :

 12 Fig. 1: Single VMs Single Samples (SVSS)

Fig. 3 :

 3 Fig. 3: Number of used voluntary context switches over 30 minutes for one run of 10 VMs in an auto-scaling scenario.

Fig. 4 :

 4 Fig. 4: Total number of standard processes versus the number of unique processes in VMs in an auto-scaling scenario.

  Figures 4 (a) -(b) and (c) -(d)

Fig. 5 :Fig. 6 :

 56 Fig. 5: Multiple VMs Single Sample (MVSS)

Fig. 7 :

 7 Fig. 7: CNN Model (LeNet-5)

  Fig. 8: 3-tier Web Application

Fig. 9 :

 9 Fig. 9: Data collection overview

Fig. 10 :

 10 Fig. 10: Optimized MVSS CNN classifier results

Fig. 11 :

 11 Fig. 11: Optimized MVPS CNN classifier results

Table 1 :

 1 Process-level performance metrics Memory information Amount of memory swapped out to disk, Proportional set size, Resident set size, Unique set size, Virtual memory size, Number of dirty pages, Amount of physical memory, text resident set, Memory used by shared libraries Network information Number of received bytes, Number of sent bytes Others Process status, Number of used threads, Number of opened file descriptors

	Metric Category	Description
	CPU information	CPU usage percent, CPU times in user space & kernel space, CPU times
		of children processes in user space & system space.
	Context switches	Number of context switches voluntary & involuntary
	IO counters	Number of read requests, write requests, read bytes, written bytes, read
		chars, written chars

Amazon architecture references. https://aws.amazon.com/architecture/

CoralReef Suite: https://www.caida.org/tools/measurement/coralreef/

NS2 manual. http://www.isi.edu/nsnam/ns/doc/node509.html

VirusTotal website. https://www.virustotal.com

Acknowledgment

This work is partially supported by NSF CREST Grant HRD-1736209, DoD ARL Grant W911NF-15-1-0518, and NSF CAREER Grant CNS-1553696.


Wladimir De La Cadena
email: wladimir.delacadena@uni.lu

Daniel Kaiser
email: daniel.kaiser@uni.lu

Asya Mitseva
email: asya.mitseva@uni.lu

Andriy Panchenko

Thomas Engel
email: thomas.engel@uni.lu

Analysis of Multi-path Onion Routing-based Anonymization Networks

Anonymization networks (e.g., Tor) help in protecting the privacy of Internet users. However, the benefit of privacy protection comes at the cost of severe performance loss. This performance loss degrades the user experience to such an extent that many users do not use anonymization networks and forgo the privacy protection offered. Thus, performance improvements need to be offered in order to build a system much more attractive for both new and existing users, which, in turn, would increase the security of all users as a result of enlarging the anonymity set. A well-known technique for improving performance is establishing multiple communication paths between two entities. In this work, we study the benefits and implications of employing multiple disjoint paths in onion routing-based anonymization systems. We first introduce a taxonomy for designing and classifying onion routing-based approaches, including those with multi-path capabilities. This taxonomy helps in exploring the design space and finding attractive new feature combinations, which may be integrated into running systems such as Tor to improve users' experience (e.g., in web browsing). We then evaluate existing implementations (together with relevant design variations) of multi-path onion routing-based approaches in terms of performance and anonymity. In the course of our practical evaluation, we identify the design characteristics that result in performance improvements and their impact on anonymity.

Introduction

In modern society, people disclose a large quantity of digital traces via the Internet. Hence, privacy is attracting more and more attention and has become a serious concern. Anonymization is a basic technical means for achieving privacy. Despite the variety of approaches proposed for anonymous communication, only a few have reached widespread deployment. Currently, Tor [START_REF] Dingledine | Tor: The Second-generation Onion Router[END_REF] is the most popular low-latency anonymization network designed for TCP-based applications, serving more than two million daily users 3 . The main objective of Tor is to hide the identities (i.e., IP addresses) of users who communicate through the Internet. To start a connection via Tor, the user runs local software, an onion proxy (OP), and creates a virtual tunnel, referred to as a circuit, to the destination over three nodes, known as onion relays (ORs) [START_REF] Dingledine | Tor Protocol Specification[END_REF]. The ORs are run by volunteers who determine the amount of bandwidth they are willing to share. Depending on their position on the circuit, the ORs are denoted as entry, middle, and exit. Via a Diffie-Hellman key exchange, the user negotiates a distinct symmetric key with each OR on the circuit. The symmetric keys are used to encrypt the actual user data in multiple layers of encryption [START_REF] Dingledine | Tor Protocol Specification[END_REF]. While forwarding user traffic, each OR on the circuit removes (or adds, depending on the direction) a layer of encryption. This ensures that none of the ORs on the circuit knows both the source and the destination of a connection at the same time. Along a circuit, user traffic travels encapsulated in fixed-size units referred to as cells.

Due to the diverse resource capabilities of ORs and their dynamic nature -anybody can join the network by running an OR or leave the network at any time -Tor suffers from both high congestion and latency. This often leads to significant delays for users which, in turn, may discourage them from using the network. Since the strength of anonymity provided by Tor strongly depends on the number of users, the protection of Tor clients utilizing the network is weakened by any user leaving the network. Therefore, performance improvements are necessary to make the system more attractive for both new and existing users. This will further improve the security of all users due to the increased anonymity set.

In response to this, a significant amount of research has focused on optimizing Tor's performance by improving its circuit processing [START_REF] Alsabah | DefenestraTor: Throwing Out Windows in Tor[END_REF][START_REF] Tang | An Improved Algorithm for Tor Circuit Scheduling[END_REF][START_REF] Tschorsch | Tor is Unfair -And What to Do about It[END_REF], transport mechanisms [START_REF] Reardon | Improving Tor Using a TCP-over-DTLS Tunnel[END_REF][START_REF] Tschorsch | Mind the Gap: Towards a Backpressure-based Transport Protocol for the Tor Network[END_REF][START_REF] Viecco | UDP-OR: A Fair Onion Transport Design[END_REF], and relay selection algorithms [START_REF] Akhoondi | LASTor: A Low-Latency AS-Aware Tor Client[END_REF][START_REF] Snader | Path Selection for Performance-and Security-Improved Onion Routing[END_REF][START_REF] Wang | Congestion-Aware Path Selection for Tor[END_REF], analyzing relay recruiting techniques [START_REF] Ghosh | A TorPath to TorCoin: Proof-of-Bandwidth Altcoins for Compensating Relays[END_REF][START_REF] Jansen | LIRA: Lightweight Incentivized Routing for Anonymity[END_REF][START_REF] Jansen | From Onions to Shallots: Rewarding Tor Relays with TEARS[END_REF], and adopting throttling methods [START_REF] Jansen | Throttling Tor Bandwidth Parasites[END_REF] to reduce the load on the network. However, none of this work has investigated the performance benefits of multiple, disjoint paths used at overlay level when transmitting user data for a single Tor client. Although a few works [START_REF] Alsabah | The Path Less Travelled: Overcoming Tor's Bottlenecks with Traffic Splitting[END_REF][START_REF] Yang | mTor: A Multipath Tor Routing Beyond Bandwidth Throttling[END_REF] have suggested concrete approaches to deploying multi-path techniques in Tor, their evaluations are limited by unrealistic and outdated conditions.

In this paper, we present an up-to-date review of existing multi-path approaches particularly designed for Tor and similar onion routing-based lowlatency anonymization systems. By conducting experimental evaluations at different scales, we analyze the state-of-the-art multi-path anonymization techniques in terms of the performance gain and anonymity implications of each approach. Our contribution is two-fold:

1. We provide a systematic survey of currently-existing multi-path approaches for Tor and other similar onion routing-based anonymization systems as well as techniques that allow adding multi-path capability. To this end, we introduce a taxonomy for onion routing-based low-latency designs with a focus on multi-path approaches and classify the existing related works accordingly. 2. We conduct a comprehensive evaluation to compare these approaches in terms of both performance and anonymity. Based on the results from our evaluation and our theoretical analysis, we discuss which design choices should be considered to achieve a desired set of properties in new systems.

Related Work

To improve the performance of the Tor network, a significant amount of research has focused on exploring a variety of relay selection algorithms, e.g., by trying to avoid congested ORs [START_REF] Wang | Congestion-Aware Path Selection for Tor[END_REF], considering the geographical location [START_REF] Akhoondi | LASTor: A Low-Latency AS-Aware Tor Client[END_REF] or bandwidth [START_REF] Snader | A Tune-up for Tor: Improving Security and Performance in the Tor Network[END_REF][START_REF] Snader | Improving Security and Performance in the Tor Network through Tunable Path Selection[END_REF] of chosen ORs. Another group of works [START_REF] Dingledine | Performance Improvements on Tor or, Why Tor is slow and what we're going to do about it[END_REF][START_REF] Murdoch | Comparison of Tor Datagram Designs[END_REF][START_REF] Reardon | Improving Tor Using a TCP-over-DTLS Tunnel[END_REF] criticizes the transport design applied by Tor, i.e., circuits from several users are multiplexed through a single TCP connection between two ORs. This may slow down the performance of interactive circuits. In response to this, several works evaluate advanced circuit scheduling mechanisms [START_REF] Tang | An Improved Algorithm for Tor Circuit Scheduling[END_REF][START_REF] Tschorsch | Tor is Unfair -And What to Do about It[END_REF], propose improved congestion control algorithms [START_REF] Alsabah | DefenestraTor: Throwing Out Windows in Tor[END_REF][START_REF] Reardon | Improving Tor Using a TCP-over-DTLS Tunnel[END_REF] or even replacing the underlying transport protocol [START_REF] Loesing | Evaluation of a libutp-based Tor datagram implementation[END_REF][START_REF] Viecco | UDP-OR: A Fair Onion Transport Design[END_REF] to optimize the utilization of available bandwidth in Tor. In contrast to our study, these works did not evaluate the effect of multi-path techniques in Tor. Nevertheless, these proposals complement our work and their coexistence can further improve the performance and harden the security of Tor. Karaoglu et al. [START_REF] Karaoglu | Multi Path Considerations for Anonymized Routing: Challenges and Opportunities[END_REF] propose a multi-path routing scenario which emulates the operation of multi-path TCP [START_REF] Handley | TCP Extensions for Multipath Operation with Multiple Addresses[END_REF]. Here, the Tor client is responsible for splitting and sending the traffic through multiple disjoint circuits to a web server which, in turn, is required to merge the received data. Thus, the authors do not require any modification in the core Tor network. However, Karaoglu et al. consider only a unidirectional scenario, in which the client uploads a file to the web server. Furthermore, the authors do not make any comparison with existing state-ofthe-art multi-path approaches proposed for Tor or other onion routing-based anonymization systems. Last, but not least, Ries et al. [START_REF] Ries | Comparison of Low-Latency Anonymous Communication Systems -Practical Usage and Performance[END_REF] compare different low-latency anonymization networks with respect to their usability and the level of anonymity that they provide. Unlike our work, there is no evaluation of the applicability of multi-path techniques within these anonymization networks.

Multi-path in Anonymization Systems

Using multiple paths in anonymization systems has been also considered in previous theoretical analyses, simulations, and non onion routing approaches. The objectives pursued by those works were: passive attack resilience [START_REF] Feigenbaum | Preventing Active Timing Attacks in Low-latency Anonymous Communication[END_REF][START_REF] Serjantov | Message Splitting Against the Partial Adversary[END_REF], multi-path as a means of anonymity [START_REF] Katti | Information Slicing: Anonymity Using Unreliable Overlays[END_REF], and performance improvements [START_REF] Karaoglu | Multi Path Considerations for Anonymized Routing: Challenges and Opportunities[END_REF][START_REF] Snader | Path Selection for Performance-and Security-Improved Onion Routing[END_REF]. However, only three systems have been fully developed and implemented as multi-path onion routing-based approaches. Two of these, Conflux [START_REF] Alsabah | The Path Less Travelled: Overcoming Tor's Bottlenecks with Traffic Splitting[END_REF] and mTor [START_REF] Yang | mTor: A Multipath Tor Routing Beyond Bandwidth Throttling[END_REF], are extensions to vanilla Tor that adapt its traffic management design to utilize multiple circuits; the third, MORE [START_REF] Landsiedel | Dynamic Multipath Onion Routing in Anonymous Peer-To-Peer Overlay Networks[END_REF], comprises a multi-path design over UDP where each cell travels along a different circuit. To our knowledge, there is no fully-developed multi-path approach that is both UDP-based and uses, as Tor does, fixed circuits per data transfer. For a more comprehensive analysis of standard transport protocol (UDP, TCP)-based multi-path approaches, we consider closing this gap in the design space to be necessary and so added multi-path support to UDP-OR [START_REF] Viecco | UDP-OR: A Fair Onion Transport Design[END_REF] as a further contribution; we refer to the result as mUDP-OR. We chose enhancing UDP-OR because it is fully-developed and relies on standard transport protocols (see section 4). The remainder of this section describes the multi-path onion routing-based systems analyzed and evaluated in this paper.

Conflux

In this design (see [START_REF] Alsabah | The Path Less Travelled: Overcoming Tor's Bottlenecks with Traffic Splitting[END_REF]), the OP builds multiple circuits with the same exit OR. Once those circuits are created, the OP sends a cell with a random nonce towards the exit OR as an identifier of the multi-path structure. To send each cell, the OP and the exit OR, known as end-points, select one of the multiple circuits according to its congestion, which is estimated as the time interval between the 100 th cell being sent, and the corresponding sendme4 being received. Cells that arrive out-of-order to the end-points are merged and sorted using a 4-byte sequence number included in the cell's payload. Conflux presents results from an implementation that supports only two circuits. For our analysis, we have enhanced the Conflux's design in order to support m circuits.

mTor

Here (see [START_REF] Yang | mTor: A Multipath Tor Routing Beyond Bandwidth Throttling[END_REF]), the multi-path structure and cell merging procedure is similar to Conflux. However, end-points choose one of the multiple circuits according to its current stream-level window 5 value. The end-point drops cells to the circuits in a first-in-first-out manner, while their stream window is greater than zero.

MORE

In MORE (see [START_REF] Landsiedel | Dynamic Multipath Onion Routing in Anonymous Peer-To-Peer Overlay Networks[END_REF]), it is required that the client participates as OR within the network (peer-to-peer network). To send data, the client OR captures TCP data via a TUN device 6 and encapsulates it in cells, which will each be sent across a different circuit. This means that no initial circuit establishment takes place, but that each cell travels along its own randomly-chosen path. To guarantee reliability of cells traveling along different routes, MORE takes advantage of the TUN device's functionality and provides an IP overlay service for tunneling TCP data. In this sense, a multi-path layer TCP session exists between sender and receiver. To discover each cell's route, an intermediary OR onion-decrypts and reads the corresponding successor node from the header. To reduce the computational cost of re-setting up a cryptographic context for each cell, MORE uses elliptic curve cryptography (ECC). While using one circuit for each cell increases the resilience against traffic analysis attacks, it also considerably reduces performance.

mUDP-OR

Here (see [START_REF] Viecco | UDP-OR: A Fair Onion Transport Design[END_REF]), the multi-path structure and circuit identification is performed in a manner similar to Conflux. However, ORs in a circuit communicate with each other using the UDP transport protocol. This circuit is used for tunneling TCP application data. Instead of encapsulating complete TCP segments, an end-point builds cells, appending to the header the necessary TCP fields (e.g. sequence numbers) to reconstruct a TCP packet at the other end-point. This TCP virtual connection is realized by setting up a SOCKS proxy in the exit OR, and establishing a virtual tunnel from a virtual TUN device in the OP. We implemented two strategies to dispatch cells into the circuits. In the first, the end-point chooses the circuit in a round robin (RR) manner with a configurable number of cells per circuit. In the second, the end-point randomly chooses through which circuit the next cell will be sent. We leverage the existing circuitlayer TCP session to merge cells arriving from different circuits. In this sense, the existing virtual end-to-end TCP connection is agnostic to the circuit(s) used.

Classifying Design Choices

In this section we introduce a hierarchical taxonomy for classifying and discussing onion routing design choices. The top level classes of our taxonomy comprise traffic management, path selection, and circuit construction; Figure 1 illustrates our taxonomy. We focus on the multi-path aspects and the effect of adding multi-path capabilities. Based on the structure of our taxonomy, we classify and discuss the multi-path OR approaches introduced in the previous section.

Traffic Management

The traffic management class comprises design choices which are concerned with transmitting data over already-established circuits in an anonymization overlay network; specifically regarding providing a TCP-like end-to-end service and scheduling decisions. This class is a key element of designing OR approaches and significantly affects performance. It also has an effect on anonymity, as feedback mechanisms might leak information, allowing for fingerprinting attacks [START_REF] Reardon | Improving Tor Using a TCP-over-DTLS Tunnel[END_REF].

We classify traffic management into OR-link layer, circuit layer, and multipath layer. These layers are intertwined, as their combination must provide the same service as a direct TCP connection, namely reliability, congestion control, and flow control. Inter-layer dependency causes some issues, the most prominent of which is cross-circuit interference [START_REF] Wang | Congestion-Aware Path Selection for Tor[END_REF]. In general, cross-circuit interference is a consequence of OR-link layer connection artifacts affecting virtually independent circuits, because several circuit-layer connections share the same OR-link.

OR-Link Layer: The OR-link layer comprises the transport connection between ORs. We classify the OR-link layer design according to which of reliability, congestion control, and flow control it incorporates. Tor uses TCP on the OR-link layer, realizing reliability, congestion control, and flow control on this layer. Since Tor multiplexes all circuit segments over a single OR-link layer connection (TCP connection) between ORs and TCP mechanisms are agnostic to these circuits, it is subject to cross-circuit interference; specifically, because of shared I/O buffers and congestion control. Shared I/O buffers are a problem because segments are taken out of the shared TCP buffer on a first-come-firstserved basis, no matter which circuit they are associated with. This leads to high latency for all circuits in the presence of high-throughput circuits that congest the shared TCP I/O buffer. This, in turn, may render interactive sessions using a low-throughput circuit over the same TCP connection unusable, as there is no means for prioritizing an interactive session.

Congestion control causes TCP connections to be throttled in the case of a congestion event 7 ; thus, if a congestion event occurs related to a single circuit, all circuits over the same TCP connection are throttled. Even without congestion control, reliability8 would cause cross-circuit interference because the recovery from packet loss in one circuit would also affect all other circuits sharing the same TCP connection.

Two classes of solutions addressing Tor's cross-circuit interference have been proposed; firstly, dedicating a TCP connection to each circuit segment [START_REF] Alsabah | PCTCP: Per-circuit TCP-over-IPsec Transport for Anonymous Communication Overlay Networks[END_REF]; and secondly, using a simple transport protocol, e.g., UDP [START_REF] Viecco | UDP-OR: A Fair Onion Transport Design[END_REF]. Conflux and mTor are Tor extensions that add the multi-path layer while inheriting this weakness of Tor. mUDP-OR and MORE both use UDP as a transport protocol, avoiding cross-circuit interference. However, this countermeasure leads to aggressive traffic 9 , which might congest the network. This issue has been addressed in [START_REF] Tschorsch | Mind the Gap: Towards a Backpressure-based Transport Protocol for the Tor Network[END_REF].

A multi-path based mitigation technique for cross-circuit interference on the OR-link layer, which to our knowledge has not yet been discussed, would be the use of multi-path TCP [START_REF] Handley | TCP Extensions for Multipath Operation with Multiple Addresses[END_REF] as a transport protocol. Since multi-path TCP handles scheduling among the various TCP sub-streams on the transport layer, it is not suited to circuit-aware scheduling. Still, having several TCP sub-streams would lower the risk of cross-circuit interference while potentially multiplexing several circuits over a single connection hiding them in an anonymity set. However, especially in congested networks, having several TCP connections also increases the aggressiveness of traffic [START_REF] Tschorsch | How (not) to build a transport layer for anonymity overlays[END_REF].

Circuit Layer: The circuit layer comprises a single overlay connection between an OP and an exit OR. As with the OR-link layer, we classify the circuit layer design by which of reliability, congestion control, and flow control it incorporates. The Tor circuit layer protocol [START_REF] Dingledine | Tor Protocol Specification[END_REF] does not implement reliability, since it is already provided by TCP at the OR-link layer. It provides flow control with a fixed-sizewindow-based mechanism and no congestion control. Reliability methods do not benefit from inter OR-link or inter-layer communication and thus should be realized on one layer exclusively. Flow control and congestion control can benefit from inter OR-link and inter-layer interaction [START_REF] Tschorsch | Mind the Gap: Towards a Backpressure-based Transport Protocol for the Tor Network[END_REF], and thus may be (partially) realized on several layers. Both having a fixed-size window for flow control and not providing congestion control have been identified as the major performance limiting factors of Tor [START_REF] Alsabah | Performance and Security Improvements for Tor: A Survey[END_REF]. Prioritization of interactive connections on the circuitlevel has been proposed by Tang et al. [START_REF] Tang | An Improved Algorithm for Tor Circuit Scheduling[END_REF] as a mitigation technique for crosscircuit interference, making interactive connections more responsive.

Conflux and mTor also inherit the properties of Tor for the circuit layer. mUDP-OR tunnels TCP, meaning the onion proxy and the exit node have a virtual TCP connection; thus, mUDP-OR provides all of flow control, congestion control, and reliability on the circuit layer. MORE is an overlay IP service where TCP data can be tunneled, making it part of the same class as mUDP-OR. The advantage of both mUDP-OR and MORE is being able to avoid cross-circuit interference. However, the OP-to-exit feedback loop for congestion control and reliability realization is very long and therefore not responsive. If a packet is dropped on the first circuit segment, this packet loss is detected at the end of the last circuit segment and the notification of this event needs to travel all the way back. The same problem occurs for adapting the TCP congestion window. Further, because mUDP-OR tunnels kernel-level TCP, the feedback across the whole circuit allows OS fingerprinting attacks [START_REF] Reardon | Improving Tor Using a TCP-over-DTLS Tunnel[END_REF].

A further property we use to classify the circuit layer by is circuit to ORlink mapping. The circuit to OR-link mapping decides how circuit segments are mapped to connections between the corresponding pair of ORs. Realizations comprise (1) n : 1, where all circuit segments between a pair of ORs are multiplexed over one transport connection, (2) 1 : 1, where each circuit segment is mapped to a dedicated transport connection, and (3) n : m, where several circuit segments between a pair of ORs are multiplexed over a set of transport connections. While (1) may suffer from cross-circuit interference (e.g., when reliability is provided) but offers the best anonymity properties, (2) prevents cross-circuit inference but may allow passive attackers to infer which circuit a given packet is associated with, which in turn might allow association with the sender. A compromise is provided by (3) which reduces cross-circuit interference while still hiding packets in an anonymity set. Tor implements strategy [START_REF]The Tor Relay Guide[END_REF], which is inherited by Conflux and mTor. mUDP-OR also implements this strategy. MORE implements strategy (2) and further uses a new circuit for each (set of) cell(s). The multi-path TCP based solution described above is an example of (3).

We also classify the circuit layer by its circuit scheduling method. If several circuits share a transport connection, cells associated with various circuits are multiplexed over this connection. Circuit-layer scheduling is concerned with how to choose which cell from various circuit-level output queues should be the next to be put into the transport-level output queue. We classify circuit scheduling methods into (1) ad hoc, and (2) metric-based. Ad hoc methods do not depend on a metric; subclasses are, e.g., (1a) random, where cells are randomly taken from input queues and put into the output queue, and (1b) round robin. Metric-based methods collect information about available circuits. This information is used to calculate a metric, based on which scheduling decisions are made. A subclass is (2a) traffic class prioritization, where specific traffic classes, e.g., traffic from an interactive connection, are prioritized. ( 1) is simple to implement and neither consumes additional computational power nor needs extra network messages. However, as shown in [START_REF] Alsabah | Performance and Security Improvements for Tor: A Survey[END_REF], (2) provides superior overall performance.

Prior to 2012, Tor used round robin as its scheduler. Then, an improved scheduler based on the recent circuit's activity was implemented [START_REF] Tang | An Improved Algorithm for Tor Circuit Scheduling[END_REF]. Most recently, in 2017 a new scheduler called KIST [START_REF] Jansen | Never Been KIST: Tor's Congestion Management Blossoms with Kernel-Informed Socket Transport[END_REF] was introduced. It uses feedback from the kernel to prioritize the traffic of each circuit's queue. Conflux and mTor inherit this characteristic from Tor. mUDP-OR does not maintain circuit-level queues and therefore directly passes cells to the transport layer. Because MORE has a 1 : 1 mapping between circuit segments and OR-links, it too does not implement any circuit-level scheduling and leaves this task to the transport layer. Not having a circuit-level queue decreases feedback time and total queueing delay, but comes at the cost of not having the advantages of circuit scheduling.

Multi-Path Layer: The multi-path layer incorporates sets of circuits jointly building communication channels. We classify the multi-path layer design by which of congestion control and flow control it considers. While it is a feasible design choice for the multi-path layer to be agnostic to both flow control and congestion control, the realization of reliability for a multi-path approach always includes the multi-path layer. The subclasses of multi-path reliability are merge and full reliability. The former expects the underlying circuits to provide a reliable ordered stream of cells -either by realizing reliability on the OR-link layer or on the circuit layer -and merges cells coming from different circuits. The latter collects all packets from the associated circuits and fully implements reliability. Having reliability on the multi-path layer allows for sending control information on less-congested circuits to reduce feedback time.

While Tor does not offer multi-path capabilities, both Conflux and mTor can be seen as multi-path extensions to vanilla Tor. As Tor already provides reliability and congestion control on the OR-link layer and flow control on the circuit layer, both solutions apply the merge strategy on the multi-path layer. Since mUDP-OR is a multi-path extension of UDP-OR, which already provides a means for anonymizing a reliable connection, mUDP-OR adds merge on top of the circuit layer provided by UDP-OR. MORE sends cell(s) over a different unreliable circuit; thus, full reliability is performed at the multi-path layer.

Another multi-path layer design choice is multi-path scheduling. While circuit scheduling decides from which circuit-level queue the next cell is put into the transport-level queue, multi-path scheduling decides over which circuit a given cell should be sent. The classes of scheduling algorithms, however, are the same as for circuit scheduling. New subclasses are (2b) congestion-based, where cells are sent through less congested circuits, (2c) round trip time (RTT) based, where circuits with lower RTT are prioritized, and (2d) tunable, which is a tunable combination of the other subclasses. As multi-path layer scheduling allows for congestion control which, in turn, leads to more even utilization of circuits, it also helps in mitigating cross-circuit interference. Both Conflux and mTor implement congestion-based scheduling. While Conflux's scheduling strategy has a very long feedback loop (see section 3), mTor implements a more responsive method based on the stream-level receive window size. Still, in absolute terms, the feedback loop is long. The mTor scheduling algorithm improves the throughput of bulk transfers while not negatively affecting interactive sessions. The default scheduler used in mUDP-OR is round robin. MORE is special in this case, as it creates new circuits on the fly for each cell and sends cells over the respective newly-created circuit. Thus, it depends on path selection and circuit construction discussed in the following subsections. The scheduling itself is therefore ad hoc, because a cell is scheduled to the only available circuit at a given point in time.

Multi-path TCP [START_REF] Handley | TCP Extensions for Multipath Operation with Multiple Addresses[END_REF] could be used not only on the OR-link layer, but also on the circuit and multi-path layers, tunneling multi-path TCP's sub-streams on the circuit layer and using its scheduling and merging strategy on the multi-path layer. While this solution has the advantage of using an established protocol, it comes with little flexibility for adapting it to be a Tor transport. Such a solution should not use TCP at the OR-link layer as this would lead to TCP over TCP throttling effects [START_REF] Titz | Why TCP Over TCP Is A Bad Idea[END_REF].

Summarizing the realization of TCP functionality, all approaches directly use TCP and do not introduce custom designs. Both Conflux and mTor use TCP on the OR-link layer, mUDP-OR uses TCP on the circuit layer, and MORE uses TCP10 on the multi-path layer. Like Tor, Conflux and mTor add only a simple flow control mechanism on the circuit layer. More sophisticated approaches tailored to anonymization overlay networks (see, e.g., [START_REF] Tschorsch | Mind the Gap: Towards a Backpressure-based Transport Protocol for the Tor Network[END_REF]) have not as yet been used in the context of multi-path onion routing.

Circuit Construction

This design class comprises the considerations for building the path(s) that the OP will employ. The only subclass of circuit construction is the number of circuits required by the OP for exchanging data. The subclass single circuit is valid for Tor, since only one circuit is required by the OP for a data transfer. If multiple circuits are required, the design choice needs to specify where the merging/splitting points are. This in turn defines how many ORs per position (entry, middle, or exit) can compose a circuit. This design choice influences anonymity, performance and implementation complexity. Conflux, mTor, and mUDP-OR enlarge the bandwidth capacity of the last hop by building extra middle-to-exit connections. From the anonymity perspective, using multiple entry ORs may improve the resilience against some attacks (see section 6). None of the considered approaches merge on a middle OR; this scheme would represent a more complex implementation but at the same time an easier deployment in the network, since there are fewer requirements for starting a middle OR in Tor [START_REF]The Tor Relay Guide[END_REF].

Another class refers to the topology formed by the selected ORs. Conflux, mTor, and mUDP-OR form a partial mesh, since each entry OR communicates with one middle OR. MORE tends to form a full mesh as the number of sent cells increases.

Lastly, the linking subclass refers to the mechanism to associate/save several circuits as a singular structure upon their creation. In Conflux, mTor and mUDP-OR, multiple circuits are referred by an end-point under a common identifier exchanged via a control cell. This type of linking comprises the subclass identifier. The other subclass, cell-based, is used by MORE. Here, paths are not linked in the construction process, but their cells will be grouped during the data transmission based on their header. This linking class is strongly related to the scheduling from the multi-path layer, and choosing it properly results in faster multi-path build times, and a more secure multi-path structure.

Path Selection

Preemptively, more than the required circuits can be built before streams are attached to them. This design choice determines which of the built path(s) will be next used for the data transfer. Once the path(s) are selected, the OP sends cells based on the traffic management design choices.

The subclass selection criteria determines which parameter(s) must be considered for defining which circuit(s) will be employed. In Tor, after discarding circuits with slow build times, the newest available is chosen. Other parameters such as RTT, congestion, or a tunable combination of these may be also considered. The subclass stream attachment comprises special choices for multi-path approaches. In contrast to Tor, where the stream will be directly attached to a single circuit, multiple circuits allow this attachment to be fixed, when the set of selected circuits does not change after they are chosen, or to be dynamic when the set of selected circuits may change during the data transfer. When the set of selected circuits changes as dynamically as in MORE, this design choice determines the multi-path layer scheduling.

To sum up, the top level classes of the taxonomy address the design choices to be considered before user data is sent (path selection and circuit construction), and for the data transmission itself (traffic management). In our evaluation, we identify the effects of the design choices employed by the analyzed approaches.

Performance Evaluation

In this section, we evaluate each approach within two scenarios: on an isolated private local network, and in a larger network using the NetMirage11 emulator.

Private Local Network Experiment

We use this experiment to understand the differences between all designs without external influence. In a local network we set up seven ORs, one client for measurements, four web servers, and up to 30 clients to generate load on the employed circuit(s). Three metrics are reported on the client: TTFB (Time to First Byte), and download times (DT) for HTTP web (320 KiB) and bulk (1 MiB) requests 12 . Furthermore, on each OR the CPU usage was periodically logged. Considering that there are no congestion effects from other sources in an isolated network, we evaluated each approach with the round robin multi-path scheduler. This also ensures that multiple circuits will be equitably used. Effects of congestion-based schedulers are evaluated in the second scenario.

Multi-path Circuits and Load Balancing: In the left columns of Table 1 we present the average CPU load on each OR for the maximum number of clients. For multiple circuits, we present results for only one of them, since values in others are similar. It is clearly observable that the load assigned to each OR is decreased by using multiple circuits simultaneously. Furthermore, it is noticeable that translating the reliability and congestion control tasks to the end-points (in mUDP-OR and MORE) results in a higher load on them. We also observe that entry ORs are more loaded than others (except by MORE) in the circuit due to the cryptographic operations performed.

Client Performance: Performance metrics are presented in the right columns of Table 1. As an expected consequence of the dynamic stream attachment in MORE, its clients experience the slowest download times, making it unfeasible to complete data transfers in many cases (e.g., for bulk downloads). We confirm that a UDP-based approach such as mUDP-OR responds faster than a TCPbased approach. In contrast to Conflux and mTor, our multi-path enhancement to UDP-OR did not produce the desired improvements due to the still-existing very long feedback for retransmissions and acknowledgments.

Larger-Scale Experiment

Currently, the Shadow [START_REF] Jansen | Shadow: Running Tor in a Box for Accurate and Efficient Experimentation[END_REF] tool is widely used for large-scale Tor simulations. However, due to lack of support for some required functions (e.g., TUN devices) in Shadow, we opted for the NetMirage tool for building a common testbed. We based our experiment on the PlanetLab and Tor topologies included in version 1.12.1 of the Shadow simulator. It consisted of 303 nodes distributed all over the world, where we set up 206 web clients, 22 bulk clients, 14 exit nodes, 59 non-exit nodes and 14 web servers. Web clients performed successive downloads of 320 KiB data, waiting randomly from 0 to 20 seconds between each download, and bulk clients downloaded 1 MiB sequentially without pausing. Client Performance: For every approach, each design variation13 was emulated for two hours (see Figure 2 and Figure 3). We observe that, in a congested environment, mUDP-OR only outperforms other approaches in the TTFB metric. Moreover, the congestion-based scheduling techniques of mTor and Conflux do not profit completely from the utilization of multiple circuits; this may explain why the RR scheduler performs better, particularly for bulk downloads. Thus, it is necessary to develop a more efficient circuit congestion estimation procedure. Since Tor does not directly access the congestion information provided by TCP for each OR link, the estimations done in the circuit layer are not completely reliable and may not represent the state of the circuit at that moment. We observe that the improvements in downloading data are more advantageous to bulk transfers. Moreover, the TCP-based approaches outperform the UDP-based ones in terms of download speed for nearly all the 228 clients.

Network Scalability: In this experiment we incrementally introduced up to 228 clients (10% bulk and 90% web clients) and measured TTFB and download speed for each iteration (see Figure 4). The fast first response of mUDP-OR is clearly advantageous within a congested network; however, clients of Conflux and mTor download data faster. We observe that the download speed for all approaches stabilizes to its minimum value when around 140 clients are present. After this point, differences between all approaches remain constant. We notice that using RR for multi-path scheduling scales better, due to the equitable usage of network resources. It is also noticeable that congestion-based mechanisms perform better in a lightly-congested environment; this reinforces the intuition that the employed congestion estimation techniques are not fully precise. We refrain from comparing MORE in this regard due to its poor performance.

Design Recommendations

From the performed evaluations we identify that any design (single or multipath) based on UDP, provides a fast first response. This feature comes however, at the cost of a degraded performance. If fast download speed is desired (e.g., in web browsing), the design should use the TCP protocol on the OR-link layer together with an effective congestion-based multi-path scheduler. If the objective is to ease the burden on ORs, the round robin scheduler ensures an equitable traffic distribution. If performance is not of the essence -for instance in non-time-sensitive applications like messaging or microblogging -even higher anonymity can be achieved by systems with the characteristics of MORE.

Anonymity Analysis

In this section, we address the anonymity implications produced by using multiple paths in the context of the evaluated approaches.

Client Multi-path Circuits Compromise

A circuit becomes compromised if an attacker gains control over both its edges. An adversary that controls a fraction of entry and exit nodes (f g and f x ), can compromise any single circuit with a probability P (c) ≈ f g f x [START_REF] Alsabah | The Path Less Travelled: Overcoming Tor's Bottlenecks with Traffic Splitting[END_REF][START_REF] Das | Securing Anonymous Communication Channels under the Selective DoS Attack[END_REF]. For multipath clients employing m entries and one exit OR, this expression becomes

P m (c) ≈ f x (1 -(1 -f g ) m )
. This expression is valid for all evaluated approaches; however, for MORE, an adversary must compromise many more than m circuits to fully affect one client, which means that this approach provides higher levels of anonymity. Even though P m (c) ≥ P (c), this difference is negligible even in the presence of a powerful attacker14 .

Using Multiple Entry Onion Routers

To make the probability of de-anonymization vanishingly small, Tor clients try to choose the same entry OR from the priority-ordered primary list 15 . Since a multi-path client uses m entries, they should be taken from a primary list of minimum size m. In order to evaluate the anonymity implications, we leverage the framework presented in [START_REF] Imani | Guard Sets in Tor using AS Relationships[END_REF] together with metrics and adversary models presented in [START_REF] Hayes | Guard Sets for Onion Routing[END_REF]. Two adversary models are considered for client using m entries, the first determines that a client is compromised if at least one entry is controlled, which may be valid for confirmation and correlation attacks [START_REF] Hayes | Traffic Confirmation Attacks Despite Noise[END_REF]. The second, defines a compromised client if and only if all m entries are controlled, which may be valid for website fingerprinting attacks [START_REF] Hayes | k-fingerprinting: A Robust Scalable Website Fingerprinting Technique[END_REF][START_REF] Panchenko | Website Fingerprinting at Internet Scale[END_REF][START_REF] Rimmer | Automated Website Fingerprinting through Deep Learning[END_REF][START_REF] Wang | Effective Attacks and Provable Defenses for Website Fingerprinting[END_REF]. Both models are valid for designs that assign streams to a fixed set of circuits (Conflux, mTor and mUDP-OR). For systems with dynamic stream attachment (MORE), the models are valid during the usage interval of the circuits. Using consensus data from 2015, we simulated 500,000 clients and a high-resource adversary controlling 10% of the overall entry bandwidth. Figure 5 shows the mean compromise rate (CR) of 50 simulations. We notice that, for the second adversary model, the CR decreases exponentially with each additional entry. Conversely, if one from m entries is enough to compromise a client, they become around twice as vulnerable.

Lastly, we analyze the guard fingerprinting attack 16 , where using multiple entries decreases the mean anonymity set size (A). Currently, each Tor client shares its entry OR with on average another 1,000 users (A = 1000). If clients used m paths, A would drastically decrease to 2×10 6 ( 2000 m )

. Using the Tor source code, we simulated the creation of primary lists for 83,000 clients. For m = 1, we experimentally obtained A = 112, while for m = 2 roughly 90% of clients had a unique pair of entries, and the user with the largest anonymity set shared its entries with another 14 users. For this attack, the dynamism of MORE is also favorable, because all clients tend to use all nodes as entries. Thus, A converges to its upper limit (the total number of clients).

To sum up, the anonymity advantages of using multiple entry ORs, together with the presented performance gains, are compelling reasons to enhance systems such as Tor with multi-path capabilities. The main constraint is the fact that Fig. 5. Fraction of compromised clients (Compromise Rate) during one year: Single, two, and three entries refer to the second adversary model. In the scenario labeled as COMB, 60% of the clients use a single entry, 20% two entries and 20% three entries.

using multiple entries is not considered in the latest Tor specification, however future research directions [START_REF] Imani | Guard Sets in Tor using AS Relationships[END_REF] aim to give more flexibility in this regard.

Conclusions and Future Work

Onion routing-based approaches (e.g., Tor) can leverage multi-path capabilities as a means of enhancing the users' experience through performance improvement. To investigate these capabilities, have presented a comprehensive analysis and evaluation of multi-path onion routing approaches regarding their design choices and realizations. By using the proposed taxonomy, we presented important guidelines to be followed not only for future multi-path onion routing-based designs, but also for other types of anonymization systems. For future multi-path designs, greater performance improvements are expected if the current congestion estimation mechanisms can be refined to reflect the actual transport layer congestion into the multi-path layer. Furthermore, other aspects such as anonymity and load balancing should be taken into consideration when designing the multi-path circuit structure and scheduling mechanisms. We notice that for some attacks (e.g., guard fingerprinting) a considerable modification in the current node selection strategy is needed to guarantee a level of anonymity. Meanwhile, for other attacks such as website fingerprinting a quantitative analysis of their impact is required.

In future work we also plan to address cross-circuit interference, which is a significant problem in Tor, with mitigation techniques that often affect anonymity. We plan to analyze trade-offs between using different subsets of the mechanisms that TCP offers on the OR-link layer and specifically look into alternative congestion control methods. We want to improve performance while still avoiding network congestion, and also protect anonymity by not introducing end-to-end feedback and so opening additional attack vectors.

Fig. 1 .

 1 Fig. 1. Taxonomy of design choices for onion routing-based approaches

Fig. 2 .

 2 Fig. 2. Time to first byte for web and bulk clients

Fig. 3 .

 3 Fig. 3. Download speed for web and bulk clients

Fig.

  Fig. Performance metrics for different number of clients

Table 1 .

 1 CPU usage percentage on the onion routers, and performance metrics for the maximum number of clients. 57.87 ± 2.16 49.85 ± 1.82 31.74 ± 1.15 0.027 ± 0.005 0.059 ± 0.003 0.113 ± 0.008 2 33.22 ± 2.25 31.01 ± 2.21 31.51 ± 2.22 0.016 ± 0.002 0.052 ± 0.0005 0.082 ± 0.002 3 27.24 ± 1.94 22.78 ± 1.56 32.94 ± 2.28 0.014 ± 0.003 0.049 ± 0.0007 0.079 ± 0.0024 mTor 1 57.87 ± 2.16 49.85 ± 1.82 31.74 ± 1.15 0.027 ± 0.005 0.059 ± 0.003 0.113 ± 0.008 2 25.10 ± 2.21 23.19 ± 1.73 32.51 ± 2.26 0.012 ± 0.002 0.055 ± 0.001 0.079 ± 0.003 3 13.45 ± 0.97 14.62 ± 0.85 32.90 ± 2.27 0.017 ± 0.003 0.049 ± 0.0007 0.081 ± 0.002 mUDP-OR 1 88.31 ± 1.51 86.89 ± 1.48 71.33 ± 1.24 0.002 ± 0.0003 0.031 ± 0.0018 0.076 ± 0.005 2 36.75 ± 2.51 32.67 ± 2.79 73.48 ± 3.09 0.002 ± 0.0001 0.034 ± 0.0017 0.081 ± 0.001 3 22.73 ± 3.11 24.45 ± 3.27 75.30 ± 3.21 0.0024 ± 0.0001 0.035 ± 0.001 0.113 ± 0.014

		CPU Usage on the OR	Client Performance Metrics
	Approach Paths Entry	Middle	Exit	TTFB[s] DT Web [s] DT Bulk[s]
	Conflux 1 MORE 1 2	6.73 ± 0.14 6.93 ± 0.19 75.92 ± 2.34 0.014 ± 0.004 6.65 ± 0.13 6.93 ± 0.2 70.09 ± 2.24 0.014 ± 0.004	1.41 ± 0.007 1.37 ± 0.19	N.A N.A
	3	6.57 ± 0.11 6.52 ± 0.08 68.19 ± 2.48 0.016 ± 0.006	1.39 ± 0.014	N.A

https://metrics.torproject.org/userstats-relay-country.html, October 2018.

Cell used for flow control: an end-point sends it to acknowledge the arrival of 100 cells within a circuit, or

cells within a stream.[START_REF] Alsabah | PCTCP: Per-circuit TCP-over-IPsec Transport for Anonymous Communication Overlay Networks[END_REF] As part of the flow control, the stream-level window caps the maximum amount of cells to 500 per stream at any moment.[START_REF] Alsabah | Performance and Security Improvements for Tor: A Survey[END_REF] A TUN device is a virtual kernel network interface that works as a bridge between the user and kernel spaces.

A congestion event might, e.g., be a packet loss.

The realization of reliability is typically intertwined with congestion control.

MORE uses TCP when anonymizing a reliable service. Because MORE provides an IP service on the overlay, it can also be used without providing TCP functionality at all.

https://crysp.uwaterloo.ca/software/netmirage/

Values presented with 95% confidence and based on 200 repetitions.

Two design variations were evaluated: the number of paths (labeled as 1,2,3) and the multi-path scheduler (labeled as RR for round robin and CB for congestion based).

An adversary controlling 20% of the total bandwidth (ca. 60 Gbit/s in Tor) is considered as very powerful; in this case P (c) ≈ 4% and Pm(c) ≈ 9.8% for m = 3.

[START_REF] Hayes | Guard Sets for Onion Routing[END_REF] From all ORs with entry flags listed in the consensus, by default, a client filters three ORs from several lists, choosing the first that is reachable as its entry

OR.[START_REF] Hayes | k-fingerprinting: A Robust Scalable Website Fingerprinting Technique[END_REF] Guard ORs refer to the entry ORs regularly selected by a client. This set of nodes may be used as a fingerprint for de-anonymizing a client.

Acknowledgments: We thank the anonymous reviewers for their useful comments, and all authors of the evaluated approaches for providing their source code and assistance. This research was funded by the Luxembourg National Research Fund (FNR) within the CORE Junior Track project PETIT.