Formal language constrained shortest path problems are concerned with finding shortest paths in labeled graphs. These labeled paths have the constraint that the concatenation of labels along a path constitute a valid string in some formal language \Lambda over alphabet \Sigma. These problems are well studied where the formal language is regular or context-free, and have been used in a variety of applications ranging from databases, to transportation planning, to programming languages. Barrett, Jacob, and Marathe's best algorithm for the context-free language constrained path problem runs in O(|V|^3|N| |P|) time, where N is the set of non-terminals for the input grammar and P is the set of productions (expressed in Chomsky Normal Form). We present a work and time efficient distributed version of this algorithm that may be distributed on up to O(|V| |N|) nodes.

Abstract Relative location information helps build vehicle topology maps. Such maps provide location information of nearby vehicles to drivers. In building a vehicle topology, one must consider various attacks on vehicular networks. Also the localization system should protect the drivers' identity and make it difficult for the adversary to track vehicles. Many techniques have been proposed for relative positioning and location verification. Due to the high speed and the strict security requirements, the existing relative positioning and location verification techniques are not directly applicable to vehicular networks. Hence, we present a scheme called Privacy‐preserving Secure Relative Location Determination (P‐SRLD), which securely determines the relative locations of a set of wirelessly connected vehicles based on the relative locations of each vehicle's surrounding vehicles. P‐SRLD uses cryptographic keys to authenticate location messages and vehicle's cryptographic pseudonym to identify the vehicle to protect vehicle's driver's privacy. To defend against Sybil attacks, P‐SRLD employs registration and relative location message verification mechanisms. It defends wormhole and blackhole attacks by probabilistically monitoring losses of relative location messages. Analysis and simulation results show that P‐SRLD is lightweight and is resilient to Sybil, wormhole and some other attacks. Copyright © 2008 John Wiley & Sons, Ltd.

This paper describes a proof-of-concept system for detecting insider threats. The system measures insider behavior by observing a user’s processes and threads, information about user mode and kernel mode time, network interface statistics, etc. The system is built using Microsoft’s Windows Management Instrumentation (WMI) implementation of the Web Based Enterprise Management (WBEM) standards. It facilitates the selection and storage of potential digital evidence based on anomalous user behavior with minimal administrative input.

A digital chain of custody is an account documenting digital data at a particular place and time. This paper gives a method of validating and authenticating a digital chain of custody using an algorithm by Jakobsson and by providing a new algorithm that compliments Jakobsson's algorithm. Our method assumes specialized hardware. The physical hardware is assumed to be memory and processor constrained. Our new algorithm is an online algorithm that generates a hash chain of n hash elements without knowledge of n before it starts. At the same time, as n grows our new algorithm stores only the [log n] pebbles which are inputs for Jakobsson's amortized hash chain traversal algorithm. Jakobsson's algorithm is then used to validate hash elements and thus the digital chain of custody. The complimentary algorithm presented here is used to generate and store the hash chain. The compact representation used by these algorithms is useful to store a large digital chain of custody on a small and constrained device. Our proposed method allows the use of constrained devices to validate complex and ephemeral data such as shipping manifests and handling logs.

This paper gives a new way of showing that certain constant degree graphs are graph expanders. This is done by giving new proofs of expansion for three permutations of the Gabber–Galil expander. Our results give an expansion factor of $\frac{3}{16}$ for subgraphs of these three‐regular graphs with $(p-1)^2$ inputs for p prime. The proofs are not based on eigenvalue methods or higher algebra. The same methods show the expected number of probes for unsuccessful search in double hashing is bounded by $\frac{1}{1-\alpha}$, where α is the load factor. This assumes a double hashing scheme in which two hash functions are randomly and independently chosen from a specified uniform distribution. The result is valid regardless of the distribution of the inputs. This is analogous to Carter and Wegman’s result for hashing with chaining. This paper concludes by elaborating on how any sufficiently sized subset of inputs in any distribution expands in the subgraph of the Gabber–Galil graph expander of focus. This is related to any key distribution having expected $\frac{1}{1 - \alpha}$ probes for unsuccessful search for double hashing given the initial random, independent, and uniform choice of two universal hash functions.

This paper proposes using collisions of Pareto random variables in traffic analysis and in generating fictitious network traffic that follows various Pareto distributions. Pareto distributions are commonly found in network statistics, but the distributions may be truncated or overlapping, thus making it hard to estimate their sample parameters. Therefore, this paper investigates methods of computing parameters of binned collisions of Pareto random variables. This paper explores an indicator variable approach to analyzing collisions of Pareto random variables. These collisions are initially modeled by the birthday problem or paradox and then they are extended to understand independence of collisions. This paper's use of indicator variables simplifies the calculation of higher moments for binned collisions of Pareto random variables

MOTIVATION: In the maximum parsimony (MP) method, the tree requiring the minimum number of changes (discrepancy) to explain the given set of DNA or amino acid sequences is chosen to represent their evolutionary relationships. To find the MP tree, the branch-and-bound algorithm is normally used. For a partial phylogenetic-tree (one that has a subset of the organisms) the traditional algorithm assigns a cost equal to the discrepancy of the partial phylogenetic-tree. We propose a single column discrepancy heuristic which increases this cost by predicting a minimum additional discrepancy needed to attach the sequences yet to be added to the partial phylogenetic-tree. A dynamic Max-mini order of sequence addition is also proposed to quickly terminate branch-and-bound search paths that are guaranteed to lead to suboptimal solutions. RESULTS: We studied the running time of 47 problems generated from 17 data sets. The use of single column discrepancy heuristic speeded up the computation to 2.4-fold for static and 18.2-fold for dynamic search order. The improvement appeared to increase exponentially with the number of sequences. The proposed strategies are also likely to be useful in speeding up the MP tree search using heuristic searches that are based on branch-and-bound-like algorithms. CONTACT: [email protected]

The matrix chain ordering problem is to find the cheapest way to multiply a chain of n matrices, where the matrices are pairwise compatible but of varying dimensions. Here we give several new parallel algorithms including $O(\lg^3 n)$-time and $n/\!\lg n$-processor algorithms for solving the matrix chain ordering problem and for solving an optimal triangulation problem of convex polygons on the common CRCW PRAM model. Next, by using efficient algorithms for computing row minima of totally monotone matrices, this complexity is improved to $O(\lg^2 n)$ time with n processors on the EREW PRAM and to $O(\lg^2 n \lg \lg n)$ time with $n/ \! \lg \lg n$ processors on a common CRCW PRAM\@. A new algorithm for computing the row minima of totally monotone matrices improves our parallel MCOP algorithm to $O(n \lg^{1.5} n)$work and polylog time on a CREW PRAM\@. Optimal log-time algorithms for computing row minima of totally monotone matrices will improve our algorithm and enable it to have the same work as the sequential algorithm of Hu and Shing [SIAM J. Comput., 11 (1982), pp. 362--373; SIAM J. Comput., 13 (1984), pp. 228--251].