In this paper we present an algorithm for segmenting English sentences, without spaces, into their constituent words based on a dictionary using a variation of the Viterbi algorithm. We call this variation the dictionary based Viterbi algorithm for word boundary identification. The input to the algorithm is a sequence of English words which are not space separated and the output is list of the top-k possible word segmentations. The top-k segmentation of the input into the constituent words is determined on the basis of an optimality criteria applied to a scoring function which computes the "segmentation score" of each possible word sequence for the given input. Our implementation works from the back (right) of the input string and creates a data structure for storing the possible word boundaries during the first pass. The data structure consists of an index (a list of nodes) of length equal to the number of input characters in the string. The ithnode in the index contains a pointer to the optimal list of words for the substring starting at position i of the input sequence. The list of possible breakdowns including the optimal one is collected during a second pass through the data structure. Due to the way the initial data structure is built during the first pass we call our algorithm the Reverse Sequence Search (RSS) algorithm. We report experimental results on several datasets including the entire Brown corpus with over one million words to show how fast our algorithm works. We also compare our implementation with a dynamic programming implementation provided by Norvig [1] which is one of the classical algorithms for the problem of word segmentation. Furthermore we show that our algorithm runs in O(n) time and space.

Passwords continue to remain an important authentication technique. The probabilistic context-free grammar-based password cracking system of Weir et al. was an important addition to dictionary-based password cracking approaches. In this paper, we show how to substantially improve upon this system by systematically adding keyboard patterns and multiword patterns (two or more words in the alphabetic part of a password) to the context-free grammars used in the probabilistic password cracking. Our results on cracking multiple data sets show that by learning these new classes of patterns, we can achieve up to 22% improvement over the original system. In this paper, we also define metrics to help analyze and improve attack dictionaries. Using our approach to improving the dictionary, we achieve an additional improvement of ~33% by increasing the coverage of a standard attack dictionary. Combining both approaches, we can achieve a 55% improvement over the previous system. Our tests were done over fairly long password guessing sessions (up to 85 billion) and thus show the uniform effectiveness of our techniques for long cracking sessions.

Password creation policies attempt to help users generate strong passwords but are generally not very effective and tend to frustrate users. The most popular policies are rule based which have been shown to have clear limitations. In this paper we consider a new approach that we term analyze-modify that ensures strong user passwords while maintaining usability. In our approach we develop a software system called AMP that first analyzes whether a user proposed password is weak or strong by estimating the probability of the password being cracked. AMP then modifies the password slightly (to maintain usability) if it is weak to create a strengthened password. We are able to estimate the strength of the password appropriately since we use a probabilistic password cracking system and associated probabilistic context-free grammar to model a realistic distribution of user passwords. In our experiments we were able to distinguish strong passwords from weak ones with an error rate of 1.43%. In one of a series of experiments, our analyze-modify system was able to strengthen a set of weak passwords, of which 53% could be easily cracked to a set of strong passwords of which only 0.27% could be cracked with only a slight modification to the passwords. In our work, we also show how to compute and use various entropy measures from the grammar and show that our system remains effective with continued use through a dynamic updating capability.

In this paper we attempt to determine the effectiveness of using entropy, as defined in NIST SP800-63, as a measurement of the security provided by various password creation policies. This is accomplished by modeling the success rate of current password cracking techniques against real user passwords. These data sets were collected from several different websites, the largest one containing over 32 million passwords. This focus on actual attack methodologies and real user passwords quite possibly makes this one of the largest studies on password security to date. In addition we examine what these results mean for standard password creation policies, such as minimum password length, and character set requirements.

Choosing the most effective word-mangling rules to use when performing a dictionary-based password cracking attack can be a difficult task. In this paper we discuss a new method that generates password structures in highest probability order. We first automatically create a probabilistic context-free grammar based upon a training set of previously disclosed passwords. This grammar then allows us to generate word-mangling rules, and from them, password guesses to be used in password cracking. We will also show that this approach seems to provide a more effective way to crack passwords as compared to traditional methods by testing our tools and techniques on real password sets. In one series of experiments, training on a set of disclosed passwords, our approach was able to crack 28% to 129% more passwords than John the Ripper, a publicly available standard password cracking program.

This paper describes the design and development of a software system to support law enforcement in investigating and prosecuting email based crimes. It focuses on phishing scams which use emails to trick users into revealing personal data. The system described in this paper, called the Undercover Multipurpose Anti-Spoofing Kit (UnMask), will enable investigators to reduce the time and effort needed for digital forensic investigations of email-based crimes. A novel aspect of UnMask is its use of a database to not only store information related to the email and its constituent parts (such as IP addresses, links, domain names), but also to organize a workflow to automatically launch UNIX tools to collect additional information from the Internet. The retrieved information is in turn added to the database. Reports can then be automatically generated according to the needs of the forensic investigator, including correlations across multiple email data stored in the database. UnMask is a working system. To the best of our knowledge, UnMask is the first comprehensive system that can automatically analyze emails and generate forensic reports that can be used for subsequent investigation and prosecution.

We consider a variation of a constrained Steiner minimal tree problem that is applicable for multicast conferencing. We assume a network having a cost and delay values associated with each edge. Then, we find an optimal shared tree with minimal cost subject to the constraint that the delay between any two nodes of the tree must be bounded by some maximal value. Such a constraint on the delay is appropriate for an application such as a multicast conference that uses a shared tree. We consider a new heuristic algorithm for solving this problem. Our approach is inspired by Lagrangian relaxation techniques. We first develop a novel distance metric on trees, termed delta diameter. Using this metric, our algorithm then uses a Prim-like labeling algorithm coupled with the Takahashi Matsuyama Steiner tree algorithm. Simulation results show how cost and delay can be traded off smoothly. Using simulation, we also compare our heuristic with the optimal achievable. We believe that our approach is practical for dynamically building shared trees to support applications such as real-time video conferencing with delay constraints.

Hazard situations in safety-critical systems are typically complex, so there is a need for means to detect complex hazards and react in a timely and meaningful way. This paper addresses the problem of hazard detection through the development of an online analysis tool. The approach allows the user to specify complex multi-source hazards using a query-like language, uses both synchronous and asynchronous online checking approaches to balance efficiency and expressiveness, accommodates dynamic applications through dynamic constraint addition, and supports distributed and parallel applications running in heterogeneous environments.

With the rapid deployment of high speed networks and the increased use of applications that blend voice, data, and video traffic, protocols have to be looked at anew. The problem of trying to conserve bandwidth is being replaced by the problems of overcoming latency and processing bottlenecks. In this paper, we introduce the conflicting demands in implementing reliable multicast and then present a new heuristic that balances the tradeoffs by using redundancy while not loading the network excessively.>

This paper describes a new specification model called the dynamic coordinated concurrent activities (DCCA) model and shows its utility for the specification of coordination protocols needed in manufacturing control systems. The principal advantage of this model lies in the ease with which a distributed implementation of the specified controls may be automatically generated from the formal specification itself in this paper, the authors describe some specific DCCA features, such as dynamic processes, structured states and a versatile means of specifying predicates on such states- these features facilitate obtaining a largely generic and reusable specification of a real-world FMC. The authors emphasize the elegant methodology for obtaining the distributed implementation automatically.>

Informal specifications of protocols are often imprecise and incomplete and are usually not sufficient to ensure the correctness of even very simple protocols. Consequently, formal specification methods, such as finite-state models, are increasingly being used. The selection/resolution (S/R) model is a finite-state model with a powerful communication mechanism that makes it easy to describe complex protocols as a collection of simple finite-state machines. A software environment, called SPANNER, has been developed to specify and analyze protocols specified with the S/R model. SPANNER provides the facility to compute the joint behavior of a number of finite-state machines and to check if the “product” machine has inaccessible states, states corresponding to deadlocks, and loops corresponding to livelocks. So far, however, SPANNER has had no facility to systematically deal with liveness conditions. For example, one might wish to specify that, although a communication channel is unreliable, a message will get through if it is sent infinitely often, and to check that the infinite behavior of the protocol viewed as an infinite sequence will always be in some ω-regular set (possibly specified in terms of a formula in temporal logic or as an ω-automata). In this paper we show that with very minor modifications to the implemented system it is possible to substantially extend the type of properties that can be specified and checked by SPANNER. This is done by extending the S/R model to include acceptance conditions found in automatons on infinite words, which permits the incorporation of arbitrary liveness conditions into the model. We show how these extensions can be easily incorporated into SPANNER (and into essentially any finite-state verification system) and how the resulting system is used to automatically verify the correctness of protocols.

The SPANNER software environment for the specification and analysis of concurrent process coordination and resource sharing coordination is described. In the SPANNER environment, one can formally produce a specification of a distributed computing problem, and then verify its validity through reachability analysis and simulation. SPANNER is based on a finite-state machine model called the selection/resolution model. The capabilities of SPANNER are illustrated by the analysis of two classical coordination problems: (1) the dining philosophers; and (2) Dijkstra's concurrent programming problem. In addition, some of the more recently implemented capabilities of the SPANNER system are discussed, such as process types and cluster variables.>

SPANNER is a software package for the specification, analysis, and evaluation of protocols. It is based on a mathematical model of coordinating processes called the selection/resolution model.