Dissertations / Theses on the topic 'Determinitic Finite Automaton'

This thesis is submitted in partial fulfillment of the requirements for the degree of Doctor of Philosophy (Ph.D) in the FASTAR group of the Department of Computer Science, University of Pretoria, South Africa. I present a number of algorithms for constructing minimal acyclic deterministic finite automata (MADFAs), most of which I originally derived/designed or co-discovered. Being acyclic, such automata represent finite languages and have proven useful in applications such as spellchecking, virus-searching and text indexing. In many of those applications, the automata grow to billions of states, making them difficult to store without using various compression techniques — the most important of which is minimization. Results from the late 1950’s show that minimization yields a unique automaton (for a given language), and later results show that minimization of acyclic automata is possible in time linear in the number of states. These two results make for a rich area of algorithmics research; automata and algorithmics research are relatively old fields of computing science and the discovery/invention of new algorithms in the field is an exciting result. I present both incremental and nonincremental algorithms. With nonincremental techniques, the unminimized acyclic deterministic finite automaton (ADFA) is first constructed and then minimized. As mentioned above, the unminimized ADFA can be very large indeed — often even too large to fit within the virtual memory space of the computer. As a result, incremental techniques for minimization (i.e. the ADFA is minimized during its construction) become interesting. Incremental algorithms frequently have some overhead: if the unminimized ADFA fits easily within physical memory, it may still be faster to use nonincremental techniques. The presentation used in this thesis has a few unusual characteristics:

• Few other presentations follow a correctness-by-construction style for presenting and deriving algorithms. The presentations given here include correctness arguments or sketches thereof.
• The presentation is taxonomic — emphasizing the similarities and differences between the algorithms at a fundamental level.
• While it is possible to present these algorithms in a formal-language-theoretic setting, this thesis remains somewhat closer to the actual implementation issues.
• In several chapters, new algorithms and interesting new variants of existing algorithms are presented.
• It gives new presentations of many existing algorithms — all in a common format with common examples.
• There are extensive links to the existing literature.

Thesis (PhD)--University of Pretoria, 2011.
Computer Science
unrestricted

In this thesis, we present a content based packet filtering Architecture in Linux using Deterministic Finite Automata and iptables framework. New generation firewalls and intrusion detection systems not only filter or inspect network packets according to their header fields but also take into account the content of payload. These systems use a set of signatures in the form of regular expressions or plain strings to scan network packets. This scanning phase is a CPU intensive task which may degrade network performance. Currently, the Linux kernel firewall scans network packets separately for each signature in the signature set provided by the user. This approach constitutes a considerable bottleneck to network performance. We implement a content based packet filtering architecture and a multiple string matching extension for the Linux kernel firewall that matches all signatures at once, and show that we are able to filter network traffic by consuming constant bandwidth regardless of the number of signatures. Furthermore, we show that we can do packet filtering in multi-gigabit rates.

This project is about security of computer networks using Intrusion Detection Systems. IDS contain rules for detection expressed with regular expressions, which are for detection represented by finite-state automata. The complexity of this detection with non-deterministic and deterministic finite-state automata is explained. This complexity can be reduced with help of regular expressions grouping. Grouping algorithm and approaches for speedup and improvement are introduced. One of the approches is Genetic algorithm, which can work real-time. Finally Random search algorithm for grouping of regular expressions is presented. Experiment results with these approches are shown and compared between each other.

La morphologie de la langue arabe est riche, complexe, et hautement flexionnelle. Nous avons développé une nouvelle approche pour la morphologie traditionnelle arabe destinés aux traitements automatiques de l’arabe écrit. Cette approche permet de formaliser plus simplement la morphologie sémitique en utilisant Unitex, une suite logicielle fondée sur des ressources lexicales pour l'analyse de corpus. Pour les verbes (Neme, 2011), j’ai proposé une taxonomie flexionnelle qui accroît la lisibilité du lexique et facilite l’encodage, la correction et la mise-à-jour par les locuteurs et linguistes arabes. La grammaire traditionnelle définit les classes verbales par des schèmes et des sous-classes par la nature des lettres de la racine. Dans ma taxonomie, les classes traditionnelles sont réutilisées, et les sous-classes sont redéfinies plus simplement. La couverture lexicale de cette ressource pour les verbes dans un corpus test est de 99 %. Pour les noms et les adjectifs (Neme, 2013) et leurs pluriels brisés, nous sommes allés plus loin dans l’adaptation de la morphologie traditionnelle. Tout d’abord, bien que cette tradition soit basée sur des règles dérivationnelles, nous nous sommes restreints aux règles exclusivement flexionnelles. Ensuite, nous avons gardé les concepts de racine et de schème, essentiels au modèle sémitique. Pourtant, notre innovation réside dans l’inversion du modèle traditionnel de racine-et-schème au modèle schème-et-racine, qui maintient concis et ordonné l’ensemble des classes de modèle et de sous-classes de racine. Ainsi, nous avons élaboré une taxonomie pour le pluriel brisé contenant 160 classes flexionnelles, ce qui simplifie dix fois l’encodage du pluriel brisé. Depuis, j’ai élaboré des ressources complètes pour l’arabe écrit. Ces ressources sont décrites dans Neme et Paumier (2019). Ainsi, nous avons complété ces taxonomies par des classes suffixées pour les pluriels réguliers, adverbes, et d’autres catégories grammaticales afin de couvrir l’ensemble du lexique. En tout, nous obtenons environ 1000 classes de flexion implémentées au moyen de transducteurs concatenatifs et non-concatenatifs. A partir de zéro, j’ai créé 76000 lemmes entièrement voyellisés, et chacun est associé à une classe flexionnelle. Ces lemmes sont fléchis en utilisant ces 1000 FST, produisant un lexique entièrement fléchi de plus 6 millions de formes. J’ai étendu cette ressource entièrement fléchie à l’aide de grammaires d’agglutination pour identifier les mots composés jusqu’à 5 segments, agglutinés autour d’un verbe, d’un nom, d’un adjectif ou d’une particule. Les grammaires d’agglutination étendent la reconnaissance à plus de 500 millions de formes de mots valides, partiellement ou entièrement voyelles. La taille de fichier texte généré est de 340 mégaoctets (UTF-16). Il est compressé en 11 mégaoctets avant d’être chargé en mémoire pour la recherche rapide (fast lookup). La génération, la compression et la minimisation du lexique prennent moins d’une minute sur un MacBook. Le taux de couverture lexical d’un corpus est supérieur à 99 %. La vitesse de tagger est de plus de 200 000 mots/s, si les ressources ont été pré-chargées en mémoire RAM. La précision et la rapidité de nos outils résultent de notre approche linguistique systématique et de l’adoption des meilleurs choix pratiques en matière de méthodes mathématiques et informatiques. La procédure de recherche est rapide parce que nous utilisons l’algorithme de minimisation d’automate déterministique acyclique (Revuz, 1992) pour comprimer le dictionnaire complet, et parce qu’il n’a que des chaînes constantes. La performance du tagger est le résultat des bons choix pratiques dans les technologies automates finis (FSA/FST) car toutes les formes fléchies calculées à l’avance pour une identification précise et pour tirer le meilleur parti de la compression et une recherche des mots déterministes et efficace
We developed an original approach to Arabic traditional morphology, involving new concepts in Semitic lexicology, morphology, and grammar for standard written Arabic. This new methodology for handling the rich and complex Semitic languages is based on good practices in Finite-State technologies (FSA/FST) by using Unitex, a lexicon-based corpus processing suite. For verbs (Neme, 2011), I proposed an inflectional taxonomy that increases the lexicon readability and makes it easier for Arabic speakers and linguists to encode, correct, and update it. Traditional grammar defines inflectional verbal classes by using verbal pattern-classes and root-classes. In our taxonomy, traditional pattern-classes are reused, and root-classes are redefined into a simpler system. The lexicon of verbs covered more than 99% of an evaluation corpus. For nouns and adjectives (Neme, 2013), we went one step further in the adaptation of traditional morphology. First, while this tradition is based on derivational rules, we found our description on inflectional ones. Next, we keep the concepts of root and pattern, which is the backbone of the traditional Semitic model. Still, our breakthrough lies in the reversal of the traditional root-and-pattern Semitic model into a pattern-and-root model, which keeps small and orderly the set of pattern classes and root sub-classes. I elaborated a taxonomy for broken plural containing 160 inflectional classes, which simplifies ten times the encoding of broken plural. Since then, I elaborated comprehensive resources for Arabic. These resources are described in Neme and Paumier (2019). To take into account all aspects of the rich morphology of Arabic, I have completed our taxonomy with suffixal inflexional classes for regular plurals, adverbs, and other parts of speech (POS) to cover all the lexicon. In all, I identified around 1000 Semitic and suffixal inflectional classes implemented with concatenative and non-concatenative FST devices.From scratch, I created 76000 fully vowelized lemmas, and each one is associated with an inflectional class. These lemmas are inflected by using these 1000 FSTs, producing a fully inflected lexicon with more than 6 million forms. I extended this fully inflected resource using agglutination grammars to identify words composed of up to 5 segments, agglutinated around a core inflected verb, noun, adjective, or particle. The agglutination grammars extend the recognition to more than 500 million valid delimited word forms, partially or fully vowelized. The flat file size of 6 million forms is 340 megabytes (UTF-16). It is compressed then into 11 Mbytes before loading to memory for fast retrieval. The generation, compression, and minimization of the full-form lexicon take less than one minute on a common Unix laptop. The lexical coverage rate is more than 99%. The tagger speed is 5000 words/second, and more than 200 000 words/s, if the resources are preloaded/resident in the RAM. The accuracy and speed of our tools result from our systematic linguistic approach and from our choice to embrace the best practices in mathematical and computational methods. The lookup procedure is fast because we use Minimal Acyclic Deterministic Finite Automaton (Revuz, 1992) to compress the full-form dictionary, and because it has only constant strings and no embedded rules. The breakthrough of our linguistic approach remains principally on the reversal of the traditional root-and-pattern Semitic model into a pattern-and-root model.Nonetheless, our computational approach is based on good practices in Finite-State technologies (FSA/FST) as all the full-forms were computed in advance for accurate identification and to get the best from the FSA compression for fast and efficient lookups

Disertační práce se zabývá rychlým vyhledáváním regulárních výrazů v síťovém provozu s použitím technologie FPGA. Vyhledávání regulárních výrazů v síťovém provozu je výpočetně náročnou operací využívanou převážně v oblasti síťové bezpečnosti a v oblasti monitorování provozu vysokorychlostních počítačových sítí. Současná řešení neumožňují dosáhnout požadovaných multigigabitových propustností při dodržení všech požadavků, které jsou na vyhledávací jednotky kladeny. Nejvyšších propustností dosahují implementace založené na využití inovativních hardwarových architektur implementovaných v FPGA případně v ASIC. Tato disertační práce popisuje nové architektury vyhledávací jednotky, které jsou vhodné pro implementaci jak v FPGA tak v ASIC. Základní myšlenkou navržených architektur je využití perfektní hashovací funkce pro implementaci přechodové tabulky konečného automatu. Dále byla navržena architektura, která umožňuje uživateli zanést malou pravděpodobnost chyby při vyhledávání a tím snížit paměťové nároky vyhledávací jednotky. Disertační práce analyzuje vliv pravděpodobnosti této chyby na celkovou spolehlivost systému a srovnává ji s řešením používaným v současnosti. V rámci disertační práce byla provedena měření vlastností regulárních výrazů používaných při analýze provozu moderních počítačových sítí. Z provedené analýzy vyplývá, že velká část regulárních výrazů je vhodná pro implementaci pomocí navržených architektur. Pro dosažení vysoké propustnosti vyhledávací jednotky práce navrhuje nový algoritmus transformace abecedy, který umožňuje, aby vyhledávací jednotka zpracovala více znaků v jednom kroku. Na rozdíl od současných metod, navržený algoritmus umožňuje konstrukci automatu zpracovávajícího libovolný počet symbolů v jednom taktu. Implementované architektury dosahují v porovnání se současnými metodami úspory paměti zlepšení až 200MB.

On traite de la reconnaissance des mots bi-infinis par un automate fini: on demontre que tout langage reconnaissable de mots infinis peut etre reconnu par un automate co-deterministe; on etend aux mots bi-infinis, le theoreme de mcnaughton; on etudie les proprietes de l'ensemble des facteurs d'un mot bi-infini dans le cas ou cet ensemble est reconnaissable; on determine par un theoreme d'existence d'automate minimal

Le concept d’automate, central en théorie des langages, est l’outil d’appréhension naturel et efficace de nombreux problèmes concrets. L’usage intensif des automates finis dans un cadre algorithmique s ’illustre par de nombreux travaux de recherche. La correction et l’ évaluation sont les deux questions fondamentales de l’algorithmique. Une méthode classique d’ évaluation s’appuie sur la génération aléatoire contrôlée d’instances d’entrée. Les travaux d´écrits dans cette thèse s’inscrivent dans ce cadre et plus particulièrement dans le domaine de la génération aléatoire uniforme d’automates finis.L’exposé qui suit propose d’abord la construction d’un générateur aléatoire d’automates à pile déterministes, real time. Cette construction s’appuie sur la méthode symbolique. Des résultats théoriques et une étude expérimentale sont exposés.Un générateur aléatoire d’automates non-déterministes illustre ensuite la souplesse d’utilisation de la méthode de Monte-Carlo par Chaînes de Markov (MCMC) ainsi que la mise en œuvre de l’algorithme de Metropolis - Hastings pour l’ échantillonnage à isomorphisme près. Un résultat sur le temps de mélange est donné dans le cadre général .L’ échantillonnage par méthode MCMC pose le problème de l’évaluation du temps de mélange dans la chaîne. En s’inspirant de travaux antérieurs pour construire un générateur d’automates partiellement ordonnés, on montre comment différents outils statistiques permettent de s’attaquer à ce problème
The concept of automata, central to language theory, is the natural and efficient tool to apprehendvarious practical problems.The intensive use of finite automata in an algorithmic framework is illustrated by numerous researchworks.The correctness and the evaluation of performance are the two fundamental issues of algorithmics.A classic method to evaluate an algorithm is based on the controlled random generation of inputs.The work described in this thesis lies within this context and more specifically in the field of theuniform random generation of finite automata.The following presentation first proposes to design a deterministic, real time, pushdown automatagenerator. This design builds on the symbolic method. Theoretical results and an experimental studyare given.This design builds on the symbolic method. Theoretical results and an experimental study are given.A random generator of non deterministic automata then illustrates the flexibility of the Markov ChainMonte Carlo methods (MCMC) as well as the implementation of the Metropolis-Hastings algorithm tosample up to isomorphism. A result about the mixing time in the general framework is given.The MCMC sampling methods raise the problem of the mixing time in the chain. By drawing on worksalready completed to design a random generator of partially ordered automata, this work shows howvarious statistical tools can form a basis to address this issue

Les systèmes embarqués mobiles font partis intégrante de notre quotidien. Afin de les rendre plus adaptésaux usages, ils ont été miniaturisés et leur autonomie a été augmentée, parfois de façon très considérable.Toutefois, les propositions d’amélioration butent désormais sur les possibilités de la technologie des circuitsintégrés. Pour aller plus loin, il faut donc envisager de repenser la chaîne de traitement du signal afin deréduire la consommation de ces dispositifs. Cette thèse développe une approche originale pour exploiterefficacement l’échantillonnage par traversée de niveaux d’une part et, d’autre part, associe cet échantillonnageà une logique évènementielle afin de réduire drastiquement la consommation d’énergie des systèmesintégrés autonomes. Une méthode de discrétisation adaptée à une application de reconnaissance de signauxphysiologiques, utilisée comme exemple dans cette thèse, y est présentée. Un premier prototype en logiqueévènementielle (asynchrone) sur circuit FPGA a permis de valider cette stratégie et de démontrer les bénéficesde cet échantillonnage dédié en termes de réduction de l’activité par rapport à un échantillonnage uniforme.Un second prototype en logique asynchrone et conçu en technologie CMOS AMS 0.35 μm a permis de validerpar simulation électrique un gain extrêmement important sur la consommation électrique du dispositif
Our everyday life is highly dependent on mobile embedded systems. In order to make them suitable to differentapplications, they have underwent size reduction and lifetime extension. However, these improvementsare currently limited by the possibilities of the integrated circuits technologies. In order to push back theboundaries, it is necessary to reconsider the whole digital signal processing chain from scratch to sustain thepower consumption reduction in this kind of system. This work develops on the first hand a strategy thatsmartly uses the level-crossing sampling scheme and on the other combines this sampling method with eventlogicto highly reduce the power consumption in mobile embedded systems. A discretisation method adaptedto the recognition of physiological patterns application is described. A first event-logic (asynchronous) prototypeimplemented on FPGA proved the potential benefits that an adapted sampling scheme could offersto reduce activity compared to a uniform sampling scheme. Electrical simulations performed on a secondprototype, also designed in asynchronous logic, with CMOS AMS 0.35 μm technology, validated a high gainin power consumption

Technological advancements have transformed the way people interact with the world. The Internet now forms a critical infrastructure that links different aspects of our life like personal communication, business transactions, social networking, and advertising. In order to cater to this ever increasing communication overhead there has been a fundamental shift in the network infrastructure. Modern network routers often employ software programmable network processors instead of ASIC-based technology for higher throughput performance and adaptability to changing resource requirements. This programmability makes networking infrastructure vulnerable to new class of network attacks by compromising the software on network processors. This issue has resulted in the need for security systems which can monitor the behavior of network processors at run time. This thesis describes an FPGA-based security monitoring system for multi-core network processors. The implemented security monitor improves upon previous hardware monitoring schemes. We demonstrate a state machine based hardware programmable monitor which can track program execution flow at run time. Applications are analyzed offline and a hash of the instructions is generated to form a state machine sequence. If the state machine deviates from expected behavior, an error flag is raised, forcing a network processor reset. For testing purposes, the monitoring logic along with the multi-core network processor system is implemented in FPGA logic. In this research, we modify the network processor memory architecture to improve security monitor functionality. The efficiency of this approach is validated using a diverse set of network benchmarks. Experiments are performed on the prototype system using known network attacks to test the performance of the monitoring subsystem. Experimental results demonstrate that out security monitor approach provides an efficient monitoring system in detecting and recovering from network attacks with minimum overhead while maintaining line rate packet forwarding. Additionally, our monitor is capable of defending against attacks on processor with a Harvard architecture, the dominant contemporary network processor organization. We demonstrate that our monitor architecture provides no network slowdown in the absence of an attack and provides the capability to drop packets without otherwise affecting regular network traffic when an attack occurs.

碩士
國立臺灣大學
資訊管理學研究所
100
There exist many security threats on the Internet, and the most notorious is malware. Malware (malicious software) refers to programs that have malicious intention and per- form some harmful actions. Typical malware includes viruses, worms, trojan horses, and spyware. The rst line of defense to deter malware is malware detector. Each malware detector has its own analysis method. The most basic and prevalent methods used in commercial malware detectors are based on syntactic signature matching. It is widely recognized that this detection mechanism cannot cope with advanced malware. Advanced malware uses program obfuscation to alter program structures and therefore can evade the detection easily. However, the semantics of a malware instance is usually preserved after obfuscation. So, it is feasible to develop a malware detector that is based on pro- gram semantics. In this thesis, we propose a semantics-based approach to malware analysis. Observing recently proposed methods for malware detection, we notice that string-based signatures are still used widely. It is natural to extend from string to tree, which is more general and can carry more semantics. Therefore, we use trees as signatures. Our malware detector requires a set of malware instances and a set of benign programs. The semantics of each input program is extracted and represented as a system call dependence graph. The graph is then transformed into a tree. With the set of trees generated from malware and benign programs, we use the method of grammatical inference to learn a 3-valued deter- ministic nite tree automaton (3DFT). A 3DFT has three di erent nal states: accept, reject, and unknown. If we take this 3DFT as the malware detector, it outputs three di erent values. If an input program is a malware instance, the detector outputs true. If an input program is a benign program, the detector outputs false. Otherwise, it outputs unknown. According to our experiments, our detector exhibits very low false positives. However, there is a tradeo that many programs are identi ed as unknown.

碩士
國立中興大學
資訊科學研究所
93
This thesis presents two string matching algorithms. The first algorithm constructs a string matching finite automaton (called mc-DFA) for multi-class of keystrings with infix checking and then applies this mc-DFA to process the matching procedure for a given text in a single pass. This algorithm can output the occurrences of multiple keystrings in a text concurrently. An algorithm used to minimize mc-DFA is also given and studied. The second algorithm applies the failure function to detect the occurrence of a prefix square when a string is on-line inputted. Some properties concerning these two algorithms are studied to show the time complexity of these two string matching algorithms.

A Failure Deterministic Finite Automaton (FDFA) o ers a deterministic and a compact representation of an automaton that is used by various algorithms to solve pattern matching problems e ciently. An abstract, concept lattice based algorithm called the DFA - Homomorphic Algorithm (DHA) was proposed to convert a deterministic nite automata (DFA) into an FDFA. The abstract DHA has several nondeterministic choices. The DHA is tuned into four decisive and specialized variants that may potentially remove the optimal possible number of symbol transitions from the DFA while adding failure transitions. The resulting specialized FDFA are: MaxIntent FDFA, MinExtent FDFA, MaxIntent-MaxExtent FDFA and MaxArcReduncdancy FDFA. Furthermore, two output based investigations are conducted whereby two speci c types of DFA-to-FDFA algorithms are compared with DHA variants. Firstly, the well-known Aho-Corasick algorithm, and its DFA is converted into DHA FDFA variants. Empirical and comparative results show that when heuristics for DHA variants are suitably chosen, the minimality attained by the Aho-Corasick algorithm in its output FDFAs can be closely approximated by DHA FDFAs. Secondly, testing DHA FDFAs in the general case whereby random DFAs and language equivalent FDFAs are carefully constructed. The random DFAs are converted into DHA FDFA types and the random FDFAs are compared with DHA FDFAs. A published non concept lattice based algorithm producing an FDFA called D2FA is also shown to perform well in all experiments. In the general context DHA performed well though not as good as the D2FA algorithm. As a by-product of general case FDFA tests, an algorithm for generating random FDFAs and a language equivalent DFAs was proposed.
Dissertation (MSc)--University of Pretoria, 2016.
tm2016
Computer Science
MSc
Unrestricted

Yes
Regular language inference, initiated by Angluin, has many developments, including applications in software engineering and testing. However, the capability of finite automata to model the system data is quite limited and, in many cases, extended finite state machine formalisms, that combine the system control with data structures, are used instead. The application of Angluin-style inference algorithms to extended state machines would involve constructing a minimal deterministic extended finite state machine consistent with a deterministic 3-valued deterministic finite automaton. In addition to the usual, accepting and rejecting, states of finite automaton, a 3-valued deterministic finite automaton may have “don't care” states; the sequences of inputs that reach such states may be considered as accepted or rejected, as is convenient. The aforementioned construction reduces to finding a minimal deterministic finite automaton consistent with a 3-valued deterministic finite automaton, that preserves the deterministic nature of the extended model that also handles the data structure associated with it. This paper investigates fundamental properties of extended finite state machines in relation to Angluin's language inference problem and provides an inference algorithm for such models.
The full-text of this article will be released for public view at the end of the publisher embargo on 17 Sep 2021.

The rampant growth of the Internet has been coupled with an equivalent growth in cyber crime over the Internet. With our increased reliance on the Internet for commerce, social networking, information acquisition, and information exchange, intruders have found financial, political, and military motives for their actions. Network Intrusion Detection Systems (NIDSs) intercept the traffic at an organization’s periphery and try to detect intrusion attempts. Signature-based NIDSs compare the packet to a signature database consisting of known attacks and malicious packet fingerprints. The signatures use regular expressions to model these intrusion activities. This thesis presents a memory efficient pattern matching system for the class of regular expressions appearing frequently in the NIDS signatures. Proposed Cascaded Automata Architecture is based on two stage automata. The first stage recognizes the sub-strings and character classes present in the regular expression. The second stage consumes symbol generated by the first stage upon receiving input traffic symbols. The basic idea is to utilize the research done on string matching problem for regular expression pattern matching. We formally model the class of regular expressions mostly found in NIDS signatures. The challenges involved in using string matching algorithms for regular expression matching has been presented. We introduce length-bound transitions, counter-based states, and associated counter arrays in the second stage automata to address these challenges. The system uses length information along with counter arrays to keep track of overlapped sub-strings and character class based transition. We present efficient implementation techniques for counter arrays. The evaluation of the architecture on practical expressions from Snort rule set showed compression in number of states between 50% to 85%. Because of its smaller memory footprint, our solution is suitable for both software based implementations on network chips as well as FPGA based designs.