Payload attribution can be an important element in network forensics. Given a history of packet transmissions and an excerpt of a possible packet payload, a payload attribution system (PAS) makes it feasible to identify the sources, destinations, and the times of appearance on a network of all the packets that contained the specified payload excerpt. A PAS, as one of the core components in a network forensics system, enables investigating cybercrimes on the Internet by, for example, tracing the spread of worms and viruses, identifying who has received a phishing e-mail in an enterprise, or discovering which insider allowed an unauthorized disclosure of sensitive information. Due to the increasing volume of network traffic in today's networks, it is infeasible to effectively store and query all the actual packets for extended periods of time in order to allow analysis of network events for investigative purposes; therefore, we focus on extremely compressed digests of the packet activity. We propose several new methods for payload attribution, which utilize Rabin fingerprinting, shingling, and winnowing. Our best methods allow building practical payload attribution systems, which provide data reduction ratios greater than 100:1 while supporting efficient queries with very low false positive rates. We demonstrate the properties of the proposed methods and specifically analyze their performance and practicality when used as modules of a network forensics system ForNet. Our experimental results outperform current state-of-the-art methods both in terms of false positives and data reduction ratio. Finally, these approaches directly allow the collected data to be stored and queried by an untrusted party without disclosing any payload information nor the contents of queries.

Given a history of packet transmissions and an excerpt of a possible packet payload, the payload attribution problem requires the identification of sources, destinations and the times of appearance on a network of all the packets that contained such payload. A module to solve this problem has recently been proposed as the core component in a network forensics system. Network forensics provides useful tools for investigating cybercrimes on the Internet, by, for example, tracing the spread of worms and viruses, identifying who has received a phishing email in an enterprise, or discovering which insider allowed an unauthorized disclosure of sensitive information.

Motivated by visibility problems in three dimensions, we investigate the complexity and construction of the set of tangent lines in a scene of three-dimensional polyhedra. We prove that the set of lines tangent to four possibly intersecting convex polyhedra in $\mathbb{R}^3$ with a total of n edges consists of $\Theta(n^2)$ connected components in the worst case. In the generic case, each connected component is a single line, but our result still holds for arbitrarily degenerate scenes. More generally, we show that a set of k possibly intersecting convex polyhedra with a total of n edges admits, in the worst case, $\Theta(n^2k^2)$ connected components of maximal free line segments tangent to at least four polytopes. Furthermore, these bounds also hold for possibly occluded lines rather than maximal free line segments. Finally, we present an $O(n^2 k^2 \log n)$ time and $O(nk^2)$ space algorithm that, given a scene of k possibly intersecting convex polyhedra, computes all the minimal free line segments that are tangent to any four of the polytopes and are isolated transversals to the set of edges they intersect; in particular, we compute at least one line segment per connected component of tangent lines.

We consider a class of geometric facility location problems in which the goal is to determine a set X of disks given by their centers (tj) and radii (rj) that cover a given set of demand points Y∈R2 at the smallest possible cost. We consider cost functions of the form Εjf(rj), where f(r)=rα is the cost of transmission to radius r. Special cases arise for α=1 (sum of radii) and α=2 (total area); power consumption models in wireless network design often use an exponent α>2. Different scenarios arise according to possible restrictions on the transmission centers tj, which may be constrained to belong to a given discrete set or to lie on a line, etc.We obtain several new results, including (a) exact and approximation algorithms for selecting transmission points tj on a given line in order to cover demand points Y∈R2; (b) approximation algorithms (and an algebraic intractability result) for selecting an optimal line on which to place transmission points to cover Y; (c) a proof of NP-hardness for a discrete set of transmission points in R2 and any fixed α>1; and (d) a polynomial-time approximation scheme for the problem of computing a minimum cost covering tour (MCCT), in which the total cost is a linear combination of the transmission cost for the set of disks and the length of a tour/path that connects the centers of the disks.

The processing capabilities of wireless sensor nodes enable to aggregate redundant data to limit total data flow over the network. The main property of a good aggregation algorithm is to extract the most representative data by using minimum resources. From this point of view, sampling is a promising aggregation method, that acts as surrogate for the whole data, and once extracted can be used to answer multiple kinds of queries (such as AVG, MEDIAN, SUM, COUNT, etc.), at no extra cost. Additionally, sampling also preserves the correlation info within multi-dimensional data, which is quite valuable for further data mining. In this paper, we propose a novel, distributed, weighted sampling algorithm to sample sensor network data and compare to an existing random sampling algorithm, which to the best of our knowledge is the only algorithm to work in this kind of setting

We present an algorithm to enumerate the pointed pseudotriangulations of a given point set, based on the greedy flip algorithm of Pocchiola and Vegter [Discrete Comput. Geom. 16 (1996), pp. 419–453]. Our two independent implementations agree and allow us to experimentally verify or disprove conjectures on the numbers of pointed pseudotriangulations and triangulations of a given point set. (For example, we establish that the number of triangulations is bounded by the number of pointed pseudotriangulations for all sets of up to 10 points.)

This work addresses the problem of efficient reactive management of topological predicates in MOD (Moving Objects Databases) settings. Detecting the satisfiability of such predicates in mobile and dynamic environments requires management of continuous and persistent conditions. We introduce two dynamical topological predicates: moving-along and moving-towards and we present efficient algorithmic solutions for their processing. Based on this, we subsequently take a deeper insight in the behavioral aspects of a MOD which manages them and we argue that the traditional ECA (Event Condition Action) paradigm, while it may ensure correct behavior, is not well-suited for enabling the users to declaratively specify some of the parameters that may affect the efficiency aspect of the reactive behavior. Towards this end, we introduce the (ECA)2 (Evolving and Context-Aware Event-Condition-Action) paradigm as a tool for specification of the triggers used by a MOD that handles requests which span over a time-interval in dynamic environments.

Payload attribution is an important problem often encountered in network forensics. Given an excerpt of a payload, finding its source and destination is useful for many security applications such as identifying sources and victims of a worm or virus. Although IP traceback techniques have been proposed in the literature, these techniques cannot help when we do not have the entire packet or when we only have an excerpt of the payload.

For many geometric problems, there are efficient algorithms that surprisingly use very little extra space other than the given array holding the input. For many geometric query problems, there are efficient data structures that need no extra space at all other than an array holding a permutation of the input. In this paper, we obtain the first such space-economical solutions for a number of fundamental problems, including three-dimensional convex hulls, two-dimensional Delaunay triangulations, fixed-dimensional range queries, and fixed-dimensional nearest neighbor queries.

We prove that the lines tangent to four possibly intersecting convex polyhedra in ℝ3 with n edges in total form Θ(n2) connected components in the worst case. In the generic case, each connected component is a single line, but our result still holds for arbitrary degenerate scenes. More generally, we show that a set of kconvex polyhedra with a total of n edges admits, in the worst case, Θ(n2k2)connected components of (possibly occluded) lines tangent to any four of these polyhedra. We also show a lower bound of Ω(n2k2) on the number of non-occluded maximal line segments tangent to any four of these k convex polyhedra.

Many algorithmic problems are interesting to both theoreticians and practitioners, but in a different manner. While the theoreticians have traditionally focused on worst-case scenarios which is often not very useful in practice, the practitioners are sometimes stuck in the hacking culture and arrive at solutions that only work well in a few specific cases. An example of such an algorithmic problem is ray shooting.Imposing some data structure to support ray-shooting queries usually helps to improve the efficiency of the algorithm. We focus on one such data structure---the octree. It is flexible and adaptive and has many applications. However, its degree of adaptiveness usually depends on manually selected parameters controlling its termination criteria. It is difficult to fix a set of parameter values that is good for all possible scenes. One approach to resolve this problem is to construct a data structure which tunes itself to the input without using arbitrary preset parameters, so that a single algorithm is suitable for all situations. Surprisingly, only a few investigations have focused on this approach compared to the huge amount of research papers on ray shooting from both the theoreticians and the practitioners. We take some steps in this direction by evaluating several octree construction schemes for use in ray shooting, some widely used in the computer graphics literature (such as bounding the number of objects in a leaf and the maximum depth) and some developed in companion papers as part of this research (cost-driven k-greedy termination criteria). Our experimental results show that the octrees constructed using our schemes are better than those built with a priori fixed parameters.Our octree construction algorithm is driven by a simple cost predictor and has been proven elsewhere to approximate the optimal tree to within a constant factor. We fine-tune the predictor and observe the behavior of our algorithm on octrees built to support a simple ray tracing engine and compare its performance with those of commonly used alternatives. It appears to work well in practice.

A variety of mining and analysis problems --- ranging from association-rule discovery to contingency table analysis to materialization of certain approximate datacubes --- involve the extraction of knowledge from a set of categorical count data. Such data can be viewed as a collection of "transactions," where a transaction is a fixed-length vector of counts. Classical algorithms for solving count-data problems require one or more computationally intensive passes over the entire database and can be prohibitively slow. One effective method for dealing with this ever-worsening scalability problem is to run the algorithms on a small sample of the data. We present a new data-reduction algorithm, called EASE, for producing such a sample. Like the FAST algorithm introduced by Chen et al., EASE is especially designed for count data applications. Both EASE and FAST take a relatively large initial random sample and then deterministically produce a subsample whose "distance" --- appropriately defined --- from the complete database is minimal. Unlike FAST, which obtains the final subsample by quasi-greedy descent, EASE uses epsilon-approximation methods to obtain the final subsample by a process of repeated halving. Experiments both in the context of association rule mining and classical χ2 contingency-table analysis show that EASE outperforms both FAST and simple random sampling, sometimes dramatically.

The ray shooting problem arises in many different contexts. For example, solving it efficiently would ...

We introduce the concept of a {\em sensitive $\varepsilon$-approximation} and use it to derive a more efficient algorithm for computing $\varepsilon$-nets. We define and investigate product range spaces, for which we establish sampling theorems analogous to the standard finite VC-dimensional case. This generalizes and simplifies results from previous works. Using these tools, we give a new deterministic algorithm for computing the convex hull of n points in $\mbox{\smallBbb R}^d$. The algorithm is obtained by derandomization of a randomized incremental algorithm, and its running time of O(nlog n + n{\lfloor d/2\rfloor})$ is optimal for any fixed dimension $d\geq 2$.

The main goal of this paper is to show how a simple modification of the formulation of an algorithm by Clarkson and Shor can handle the case of degenerate sets of points for computing convex hulls on-line in Ji@, d 2 2. At the same time, a simple analysis allows to maintain the expected time complexity within O(nld/21).Th's I analysis uses connections between regions, pivots, flags, and barycentric triangulations.

International audience

International audience

This paper presents a theoretical and experimental study on two different methods to evaluate the sign of a determinant with integer entries. The ilrst one is a method based on the Gram-Schmidt ortho,gonalisation process which has been proposed by Clark:son [Cla92]. We review the analysis of Clarkson and propose a variant of his method. The second method is arAextension ton x n determinants of the ABDPY method [ABD+94] which works only for 2 x 2 and 3 x 3 determinants. Both methods compute the signs of a n x n determinants whose entries are integers on b bits, by using an exact arithmetic on only b + O(n) bits. Furthermore, both methods are adaptive, dealing quickly with easy cases and resorting to the full-length computation only for null determinants.

We animate two deterministic polynomial time methods for finding a separator for two nested convex polyhedra in 3d. While this problem is NP-complete, we show a reduction to set cover. We then animate the greedy method and the weighted method.

We give a deterministic polynomial time method for finding a set cover in a set system (X,ℜ) of VC-dimension d such that the size of our cover is at most a factor of O(dlog(dc)) from the optimal size, c. For constant VC-dimension set systems, which are common in computational geometry, our method gives an O(logc) approximation factor. This improves the previous Θ(log |X|) bound of the greedy method and beats recent complexity-theoretic lower bounds for set covers (which don't make any assumptions about VC-dimension). We give several applications of our method to computational geometry, and we show that in some cases, such as those that arise in 3-d polytope approximation and 2-d disc covering, we can quickly find O(c)-sized covers.

We introduce the concept of a sensitive /spl epsi/-approximation, and use it to derive a more efficient algorithm for computing /spl epsi/-nets. We define and investigate product range spaces, for which we establish sampling theorems analogous to the standard finite VC-dimensional case. This generalizes and simplifies results from previous works. We derive a simpler optimal deterministic convex hull algorithm, and by extending the method to the intersection of a set of balls with the same radius, we obtain an O(nlog/sup 3/ n) deterministic algorithm for computing the diameter of an n-point set in 3-dimensional space.>

We investigate the complexity of halfspace range searching: Given n points in d-space, build a data structure that allows us to determine efficiently how many points lie in a query halfspace. We establish a tradeoff between the storage m and the worst-case query time t in the Fredman/Yao arithmetic model of computation. We show that t must be at least on the order of (n/log n)1-((d-1)/(d(d+1))m1/d.