Traditional anomaly detectors that threshold traffic features, when applied at end-hosts, have high false positive rates due to ``spiky'' traffic. Being focused on volume, they cannot malware that generate very little traffic. We describe a system that address both these concerns. The central idea is that of tracking ``persistence'', how often end-hosts communicate with particular destination services ({\em atoms}), and "communality", which captures popularity across users. Using real traces, we develop heuristics to aggregate destinations into {\em atoms}. We construct whitelists on atoms that satisfy conditions on persistence and communality.

Our detection system, which tracks these measures for new atoms, exploits the fact that adding an atom to the whitelist is rare. Thus, when a bot periodically calls home under the radar, the associated atoms become significant. This allows malware detection even if the associated traffic is negligible. We validate the results with traces from real enterprise end-hosts and real botnets.

Furthermore, the derived whitelists account for most of the traffic; filtering out this traffic removes most of the "bursts" that cause false alarms. In addition, we demonstrate that incorporating other sources of information unrelated to the network, such as coarse-grained user activity, can explain a large number of (residual) false alarms.

The idea of using diversity as a defense mechanism has been explored in operating systems, however it has not been explored deeply as an approach to host-based anomaly detection. Although it is intuitive that diversity should help security, such an approach will never be adopted by enterprise IT departments until the benefits and tradeoffs have been carefully analyzed. In this paper, we undertake such a study. How much diversity is there among users that is relevent to anomaly detection? How do we measure benefit in the face of many tradeoffs? Can detectors really be configured to be sensitive to different attack levels, thereby empowering collaborative detection? To what extent can diversity make it harder for attackers to hide inside normal traffic patterns? To answer these questions, we develop a mathematical framework that allows many threshold-selection strategies to be formulated as optimization problems, and is general enough to be applicable to a broad set of anomaly detectors. Using traces from 350 laptops of enterprise users, we evaluate many solutions, and expose fundamental tradeoffs. We show that while diversity does bring many benefits, we find, surprisingly, that there do exist some homogeneous strategies whose performance may be acceptable depending on the tradeoffs tant an IT operator is willing to make.

Traditionally, user traffic profiling is performed by analyzing traffic traces collected on behalf of the user at aggregation points located in the middle of the network. However, the modern enterprise network has a highly mobile population that frequently moves in and out of its physical perimeter. Thus an in-the-network monitor is unlikely to capture full user activity traces when users move outside the enterprise perimeter. The distinct environments, such as the cubicle and the coffee shop (among others), that users visit, may each pose different constraints and lead to varied behavioral modes. It is thus important to ask: is the profile of a user constructed in one environment representative of the same user in another environment?

In this paper, we answer in the negative for the mobile population of an enterprise. Using real corporate traces collected at nearly 400 end-hosts for approximately 5 weeks, we study how end-host usage differs across three environments: inside the enterprise, outside the enterprise but using a VPN, and entirely outside the enterprise network. Within these environments, we examine three types of features: (i) environment lifetimes, (ii) relative usage statistics of network services, and (iii) outlier detection thresholds as used for anomaly detection. We find significant diversity in end-host behavior across environments for many features, thus indicating that profiles computed for a user in one environment yield inaccurate representations of the same user in a different environment.

In this paper we study a combinatorial optimization problem issued from on-board networks in satellites. In this kind of networks the entering signals (inputs) should be routed to amplifiers (outputs). The connections are made via expensive switches with four links available. The paths connecting inputs to outputs should be link-disjoint. More formally, we call {\it $\plk-$network } an undirected graph with $p+\lambda$ inputs, $p+k$ outputs and internal vertices of degree four. A $\plk-$network is \emph{valid} if it is tolerant to a restricted number of faults in the network, i.e. if for any choice of at most $\lambda$ faulty inputs and $k$ faulty outputs, there exist $p$ edge-disjoint paths from the remaining inputs to the remaining outputs. In the special case $\lambda=0$, a $\plk-$network is already known as a \emph{selector}.

Our optimization problem consists of determining $N\plk$, the minimum number of nodes in a valid $\plk-$network. For this, we present validity certificates and a quasi-partitioning technique from which derive lower bounds for $N\plk$. We also provide constructions, and hence upper bounds, based on expanders. The problem is very sensitive to the order of $\lambda$ and $k$. For instance, when $\lambda$ and $k$ are small compared to $p$, the question reduces to avoid certain forbidden local configurations. For larger values of $\lambda$ and $k$, the problem is to find graphs with a good expansion property for small sets. This leads us to introduce a new parameter called \emph{$\alpha$-robustness}. We use the $\alpha$-robustness to generalize our constructions to higher order values of $k$ and $\lambda$. In many cases, we provide asymptotically tight bounds for $N\plk$.

A new class of algorithms to estimate the cardinality of very large multisets using constant memory and doing only one pass on the data is introduced here. It is based on order statistics rather that on bit patterns in binary representations of numbers. Three families of estimators are analyzed. They attain a standard error of $\frac 1{\sqrt M}$ using $M$ units of storage, which places them in the same class as the best known algorithms so far. The algorithms have a very simple internal loop, which gives them an advantage in term of processing speed. For instance, a memory of only 12kB and only few seconds are sufficient to process a multiset with several million elements and to build an estimate with accuracy of order 2 percents. The algorithms are validated both by mathematical analysis and by simulations and experimentations on real internet traffic.

The problem we consider is issued from the design of efficient on-board networks in satellites (also called Traveling Wave Tube Amplifiers). Signals incoming in the network through ports have to be routed through an on-board network to amplifiers. The network is made of expensive switches with four links and subject to two types of constraints. First, the amplifiers may fail during satellite lifetime and cannot be repaired. Secondly, as the satellite is rotating on itself, all the ports are not well oriented and hence not available. Let us assume that we have $p+\lambda$ ports (inputs) and $p+k$ amplifiers (outputs), then a $\plk-$network is said to be \emph{valid} if, for any choice of $p$ inputs and $p$ outputs, there exist $p$ edge-disjoint paths linking all the chosen inputs to all the chosen outputs. Then, the objective is to design a valid network having the minimum number of switches denoted $N\plk$. The special case where $\lambda=0$, these networks were already studied as \emph{selectors}. Here we present validity certificates from which derive lower bounds for $N\plk$; we also provide constructions of optimal (or quasi optimal) networks for practical values of $ \lambda$ and $k$ ($1 \leq \lambda \leq k \leq 8$) and a general way to build networks for any $k$ and any $\lambda$.

A new algorithm is introduced to estimate the number of distinct flows (or connections) in a data stream. The algorithm maintains an accurate estimate of the number of distinct flows over a sliding window. It is simple to implement, parallelizes optimally, and has a very good trade-off between auxiliary memory and accuracy of the estimate: a relative accuracy of order $1/\sqrt{m}$ requires essentially a memory of order $m\ln(n/m)$ words, where $n$ is an upper bound on the number of flows to be seen over the sliding window. For instance, a memory of only $64 kB$ is sufficient to maintain an estimate with accuracy of order $4$ percents for a stream with several million flows. The algorithm has been validated both by simulations and experimentations on real traffic. It proves very efficient to monitor traffic and detect attacks.

A new algorithm is introduced to estimate the number $n$ of distinct elements in a multiset. This information has many applications in network monitoring and network security, as detecting Denial Of Service attacks. It is an extended version of the \hc~\cite{WZT90}. Its combination with a recently introduced algorithm, \mct~\cite{Gi05}, gives an algorithm, that estimates the number $n$ \emph{within few percents} while using a very small auxiliary memory, \emph{for any size of files}, from few units to millions (e.g. $96 kB$ is sufficient to attain a precision of $2 \%$). For some cardinalities, the precision is increased by a factor close to $4$, compared to the classical hit counting. The algorithm has been validated by simulations.

This paper deals with the design of on board networks in satellites (also called Traveling wave tube Amplifiers (TWTA)). These networks should connect signals arriving on some ports of the satellite to amplifiers, even in case of failures of some amplifiers. They are made of links and expensive switches each with 4 links. So, the aim is to design networks having as few switches as possible and satisfying the following property: \emph{there exist $p$ edge-disjoint paths from the $p$ signals arriving on $p + \lambda$ ports (inputs) to any set of $p$ amplifiers (outputs) chosen from the $p+k$ total number of outputs}. We call such networks \emph{valid $(p,\lambda,k)$-networks} and want to determine the minimum number of switches $\mathcal{N}(p, \lambda,k)$ of such networks. By symmetry we suppose $\lambda \leq k$ and we note $n:=p+k$. We give tight results for small values of $k$ and asymptotic results when $k = O(\log n)$ which are tight when $k=\Theta(\lambda)$ and when $\lambda=0$.

We introduce a new class of algorithms to estimate the cardinality of very large multisets using constant memory and doi ng only one pass on the data. It is based on order statistics rather that on bit patterns in binary representations of numbers. We analyse three families of estimators. They attain a standard error of $\frac 1{\sqrt M}$ using $M$ unit s of storage, which places them in the same class as the best known algorithms so far. They have a very simple internal loop, which g ives them an advantage in term of processing speed. The algorithms are validated on internet traffic traces.

There are two fundamental technology issues that challenge the robustness of IP backbones. First, SONET protection is gradually being removed because of its high cost (while SONET framing is kept for failure detection purposes). Protection and restoration are provided by the IP layer that operates directly over a DWDM infrastructure. Second, ISPs are systematically forced to use the shortest distance path between two Points of Presence in order to meet their promised SLAs. In this context, IP backbones are extremely vulnerable to fiber cuts that can bring down a significant fraction of the IP routes. We propose two solutions (an ILP model and a heuristic algorithm) to optimally map a given IP topology onto a fiber infrastructure. The version of the mapping problem that we address incorporates a number of real constraints and requirements faced by carriers today. The optimal mapping maximizes the robustness of the network while maintaining the ISP's SLA delay requirements. In addition, our heuristic takes into consideration constraints such as a shortage of wavelengths and priorities among POPs and routes. The heuristic is evaluated on the Sprint backbone network. We illustrate the tradeoffs between the many requirements.