The Center for Education and Research in Information Assurance and Security (CERIAS)

The Center for Education and Research in
Information Assurance and Security (CERIAS)

Reports and Papers Archive


Browse All Papers »       Submit A Paper »


Five Years of Gateways and Hackers

Bill Cheswick
Added 2002-07-26

Scheduling Support for an Internetwork of Heterogeneous Autonomous Processors

CSD-TR-92-006
Steve Chapin,Eugene Spafford
Added 2002-07-26

Extending Mutation Testing to Find Environmental Bugs

John Campbell,Douglas Comer
Added 2002-07-26

A Taxonomy of Computer Program Security Flaws

Alan R. Bull,Carl E. Landwehr,John P. McDermott,William S. Choi
Added 2002-07-26

Computer Virus Writing in Bulgaria

Vesselin Bontchev
Added 2002-07-26


The ADB Compromise, Report 1.5, Number 26

Matt Bishop
Added 2002-07-26


Hidden Patterns Statistics

P. Flajolet, Y. Guivarch, W. Szpankowski, B. Vallee

Two fundamental problems in combinatorics on words and string manipulation are string matching and sequence comparison. In string matching one searches for all occurrences of a given {it string}, understood as a sequence of consecutive symbols, in a text. In sequence comparison a {it subsequence} rather than a string is searched in a text The string matching problem has been extensively studied in literature from algorithmic and probabilistic points of view. The sequence comparison problem,  also known as {it hidden pattern} problem, is harder and it has been much less investigated. In this paper we study the number of occurrences of a given pattern~$w$ of length $m$ as a subsequence in a random text of length $n$ generated by a memoryless source. In particular, we consider two versions of this problem, namely the {\\it unconstrained} one in which the subsequence $w$ can appear anywhere in the text, and the {\\it constrained} one that puts bounds on the distances between symbols of the word $w$. We determine the mean and the variance of the number of occurrences, and establish a Gaussian limit law. These results are obtained via combinatorics on words, formal languages, and methods of analytic combinatorics based on generating functions and moment methods. The motivation to study this problem comes from an attempt at finding a reliable threshold for intrusion detections, from textual data processing applications, and from molecular biology.

Added 2002-07-26

Collaboration Using Roles

Matt Bishop
Added 2002-07-26


Watchdogs-Extending the UNIX File System

Brian N. Bershad,C. Brian Pinkerton
Added 2002-07-26

A Formal Protection Model of Security in Distributed Systems

G. Benson,I. Akyildiz,W. Appelbe
Added 2002-07-26