Biblio

Website fingerprinting attack is a kind of traffic analysis attack that aims to identify the URL of visited websites using the Tor browser. Previous website fingerprinting attacks were based on batch learning methods which assumed that the traffic traces of each website are independent and generated from the stationary probability distribution. But, in realistic scenarios, the websites' concepts can change over time (dynamic websites) that is known as concept drift. To deal with data whose distribution change over time, the classifier model must update its model permanently and be adaptive to concept drift. Streaming algorithms are dynamic models that have these features and lead us to make a comparison of various representative data stream classification algorithms for website fingerprinting. Given to our experiments and results, by considering streaming algorithms along with statistical flow-based network traffic features, the accuracy grows significantly.

In this paper we provide a framework to analyze the effect of uniform sampling on graph optimization problems. Interestingly, we apply this framework to a general class of graph optimization problems that we call heavy subgraph problems, and show that uniform sampling preserves a 1-ε approximate solution to these problems. This class contains many interesting problems such as densest subgraph, directed densest subgraph, densest bipartite subgraph, d-max cut, and d-sum-max clustering. As an immediate impact of this result, one can use uniform sampling to solve these problems in streaming, turnstile or Map-Reduce settings. Indeed, our results by characterizing heavy subgraph problems address Open Problem 13 at the IITK Workshop on Algorithms for Data Streams in 2006 regarding the effects of subsampling, in the context of graph streams. Recently Bhattacharya et al. in STOC 2015 provide the first one pass algorithm for the densest subgraph problem in the streaming model with additions and deletions to its edges, i.e., for dynamic graph streams. They present a (0.5-ε)-approximation algorithm using \textasciitildeO(n) space, where factors of ε and log(n) are suppressed in the \textasciitildeO notation. In this paper we improve the (0.5-ε)-approximation algorithm of Bhattacharya et al. by providing a (1-ε)-approximation algorithm using \textasciitildeO(n) space.