Efficient FPGA-based regular expression pattern matching

An approach to the automatic generation of efficient Field Programmable Gate Arrays (FPGAs) circuits for the Regular Expression-based (RegEx) Pattern Matching problems is presented. Using a novel design strategy, as proposed, circuits that are highly area-and-time-efficient can be automatically generated for arbitrary sets of regular expressions. This makes the technique suitable for applications that must handle very large sets of patterns at high speed, such as in the network security and intrusion detection application domains. We have combined several existing techniques to optimise our solution for such domains and proposed the way the whole process of dynamic generation of FPGAs for RegEX pattern matching could be automated efficiently.

Design and implementation of a behaviorally typed programming system for web services

Dissertação apresentada na Faculdade de Ciências e Tecnologia da Universidade Nova de Lisboa para a obtenção do Grau de Mestre em Engenharia Informática.

Deciding Kleene Algebra Terms Equivalence in Coq

This paper presents a mechanically verified implementation of an algorithm for deciding the equivalence of Kleene algebra terms within the Coq proof assistant. The algorithm decides equivalence of two given regular expressions through an iterated process of testing the equivalence of their partial derivatives and does not require the construction of the corresponding automata. Recent theoretical and experimental research provides evidence that this method is, on average, more efficient than the classical methods based on automata. We present some performance tests, comparisons with similar approaches, and also introduce a generalization of the algorithm to decide the equivalence of terms of Kleene algebra with tests. The motivation for the work presented in this paper is that of using the libraries developed as trusted frameworks for carrying out certified program verification.

The InterPro database, an integrated documentation resource for protein families, domains and functional sites.

Signature databases are vital tools for identifying distant relationships in novel sequences and hence for inferring protein function. InterPro is an integrated documentation resource for protein families, domains and functional sites, which amalgamates the efforts of the PROSITE, PRINTS, Pfam and ProDom database projects. Each InterPro entry includes a functional description, annotation, literature references and links back to the relevant member database(s). Release 2.0 of InterPro (October 2000) contains over 3000 entries, representing families, domains, repeats and sites of post-translational modification encoded by a total of 6804 different regular expressions, profiles, fingerprints and Hidden Markov Models. Each InterPro entry lists all the matches against SWISS-PROT and TrEMBL (more than 1,000,000 hits from 462,500 proteins in SWISS-PROT and TrEMBL). The database is accessible for text- and sequence-based searches at http://www.ebi.ac.uk/interpro/. Questions can be emailed to interhelp@ebi.ac.uk.

Study of cox1 trans-splicing in Diplonema papillatum mitochondria

Diplonema papillatum est un organisme unicellulaire qui vit dans l’océan. Son génome mitochondrial possède une caractéristique spéciale: tous les gènes sont brisés en de multiples fragments qui s’appellent modules. Chaque module est codé par un chromosome différent. L’expression d’un gène exige des épissages-en-trans qui assemblent un ARN messager complet à partir de tous les modules du gène. Nous avons précédemment montré que le gène cox1 est encodé dans neuf modules avec six Us non encodés entre le module 4 et le module 5 de l’ARN messager mature [1]. Nous n’avons identifié aucune séquence consensus connue de site d’épissage près des modules. Nous spéculons qu’un ARN guide (gRNA) a dirigé l’épissage-en-trans du gène cox1 par un mécanisme qui est semblable à l’édition d’ARN par l’insertion/la suppression des Us chez les kinétoplastides, le groupe sœur des diplonémides. Nous avons trouvé que les six Us sont ajoutés au bout 3’ de l’ARN d’une façon semblable à ceux ajoutés par le TUTase lors de l’édition de l’insertion des Us chez les kinétoplastides. Nous avons construit des profils de gRNA de l’épissage-en-trans avec les expressions régulières basé sur notre connaissance des gRNAs dans l’édition d’ARN chez les kinétoplastides. Selon la complémentarité partielle entre le gRNA et les deux modules adjacents, nous avons généré des amorces pour RT-PCR visant à détecter des séquences qui sont assorties à un des profils de gRNA. Une expérience pilote in vitro n’a pas permis de reconstituer l’épissage-en-trans des modules 3, 4, et 5, suggérant que nous devons améliorer nos techniques.

Proposing a hybrid-intelligent framework to secure e-government web applications

One of the essential needs to implement a successful e-Government web application is security. Web application firewalls (WAF) are the most important tool to secure web applications against the increasing number of web application attacks nowadays. WAFs work in different modes depending on the web traffic filtering approach used, such as positive security mode, negative security mode, session-based mode, or mixed modes. The proposed WAF, which is called (HiWAF), is a web application firewall that works in three modes: positive, negative and session based security modes. The new approach that distinguishes this WAF among other WAFs is that it utilizes the concepts of Artificial Intelligence (AI) instead of regular expressions or other traditional pattern matching techniques as its filtering engine. Both artificial neural networks and fuzzy logic concepts will be used to implement a hybrid intelligent web application firewall that works in three security modes.

A new portal for the analysis of human splicing variants

Understanding alternative splicing is crucial to elucidate the mechanisms behind several biological phenomena, including diseases. The huge amount of expressed sequences available nowadays represents an opportunity and a challenge to catalog and display alternative splicing events (ASEs). Although several groups have faced this challenge with relative success, we still lack a computational tool that uses a simple and straightforward method to retrieve, name and present ASEs. Here we present SPLOOCE, a portal for the analysis of human splicing variants. SPLOOCE uses a method based on regular expressions for retrieval of ASEs. We propose a simple syntax that is able to capture the complexity of ASEs.

MWRegEx : monitor web de expresiones regulares

[ES] El Trabajo de Fin de Grado, Monitor Web de Expresiones Regulares (MWRegEx), es una herramienta basada en tecnologías web, desarrollada usando el entorno Visual Studio. El objetivo principal de la aplicación es dar apoyo a la docencia de expresiones regulares, en el marco de la enseñanza del manejo de ristras de caracteres en las asignaturas de programación del Grado en Ingeniería Informática.  La aplicación permite obtener el dibujo de un autómata de una expresión regular, facilitando su comprensión; además, permite aplicar la expresión a diferentes ristras de caracteres, mostrando las coincidencias encontradas, y ofrece una versión de la expresión adaptada a su uso en literales string de lenguajes como Java y otros. La herramienta se ha implementado en dos partes: un servicio web, escrito en C#, donde se realizan todos los análisis de las expresiones regulares y las ristras a contrastar; y un cliente web, implementado usando tecnología asp.net, con JavaScript y JQuery, que gestiona la interfaz de usuario y muestra los resultados. Esta separación permite que el servicio web pueda ser reutilizado con otras aplicaciones cliente. El autómata que representa una expresión regular esta dibujado usando la librería Raphaël JavaScript que permite manejar los elementos SVG. Cada elemento de la expresión regular tiene un dibujo diferente y único para así diferenciarlo. Toda la interfaz gráfica de usuario está internacionalizada de manera tal que pueda adaptarse a diferentes idiomas y regiones sin la necesidad de realizar cambios de ingeniería ni en el código. Tanto el servicio web como la parte cliente están estructurados para que se puedan agregar nuevas modificaciones sin que esto genere una onda expansiva a lo largo de las diversas clases existentes.

Scaleable Code Clone Detection

Code clone detection helps connect developers across projects, if we do it on a large scale. The cornerstones that allow clone detection to work on a large scale are: (1) bad hashing (2) lightweight parsing using regular expressions and (3) MapReduce pipelines. Bad hashing means to determine whether or not two artifacts are similar by checking whether their hashes are identical. We show a bad hashing scheme that works well on source code. Lightweight parsing using regular expressions is our technique of obtaining entire parse trees from regular expressions, robustly and efficiently. We detail the algorithm and implementation of one such regular expression engine. MapReduce pipelines are a way of expressing a computation such that it can automatically and simply be parallelized. We detail the design and implementation of one such MapReduce pipeline that is efficient and debuggable. We show a clone detector that combines these cornerstones to detect code clones across all projects, across all versions of each project.

The InterPro database, an integrated documentation resource for protein families, domains and functional sites

Signature databases are vital tools for identifying distant relationships in novel sequences and hence for inferring protein function. InterPro is an integrated documentation resource for protein families, domains and functional sites, which amalgamates the efforts of the PROSITE, PRINTS, Pfam and ProDom database projects. Each InterPro entry includes a functional description, annotation, literature references and links back to the relevant member database(s). Release 2.0 of InterPro (October 2000) contains over 3000 entries, representing families, domains, repeats and sites of post-translational modification encoded by a total of 6804 different regular expressions, profiles, fingerprints and Hidden Markov Models. Each InterPro entry lists all the matches against SWISS-PROT and TrEMBL (more than 1 000 000 hits from 462 500 proteins in SWISS-PROT and TrEMBL). The database is accessible for text- and sequence-based searches at http://www.ebi.ac.uk/interpro/. Questions can be emailed to interhelp@ebi.ac.uk.

The transformational implementation of JSD process specifications via finite automata representation

Conventional structured methods of software engineering are often based on the use of functional decomposition coupled with the Waterfall development process model. This approach is argued to be inadequate for coping with the evolutionary nature of large software systems. Alternative development paradigms, including the operational paradigm and the transformational paradigm, have been proposed to address the inadequacies of this conventional view of software developement, and these are reviewed. JSD is presented as an example of an operational approach to software engineering, and is contrasted with other well documented examples. The thesis shows how aspects of JSD can be characterised with reference to formal language theory and automata theory. In particular, it is noted that Jackson structure diagrams are equivalent to regular expressions and can be thought of as specifying corresponding finite automata. The thesis discusses the automatic transformation of structure diagrams into finite automata using an algorithm adapted from compiler theory, and then extends the technique to deal with areas of JSD which are not strictly formalisable in terms of regular languages. In particular, an elegant and novel method for dealing with so called recognition (or parsing) difficulties is described,. Various applications of the extended technique are described. They include a new method of automatically implementing the dismemberment transformation; an efficient way of implementing inversion in languages lacking a goto-statement; and a new in-the-large implementation strategy.

Mem Tri: Memory Forensics Triage Tool

This work explores the development of MemTri. A memory forensics triage tool that can assess the likelihood of criminal activity in a memory image, based on evidence data artefacts generated by several applications. Fictitious illegal suspect activity scenarios were performed on virtual machines to generate 60 test memory images for input into MemTri. Four categories of applications (i.e. Internet Browsers, Instant Messengers, FTP Client and Document Processors) are examined for data artefacts located through the use of regular expressions. These identified data artefacts are then analysed using a Bayesian Network, to assess the likelihood that a seized memory image contained evidence of illegal activity. Currently, MemTri is under development and this paper introduces only the basic concept as well as the components that the application is built on. A complete description of MemTri coupled with extensive experimental results is expected to be published in the first semester of 2017.

Normalização automática de descrições de hotéis

As descrições de produtos turísticos na área da hotelaria, aviação, rent-a-car e pacotes de férias baseiam-se sobretudo em descrições textuais em língua natural muito heterogénea com estilos, apresentações e conteúdos muito diferentes entre si. Uma vez que o sector do turismo é bastante dinâmico e que os seus produtos e ofertas estão constantemente em alteração, o tratamento manual de normalização de toda essa informação não é possível. Neste trabalho construiu-se um protótipo que permite a classificação e extracção automática de informação a partir de descrições de produtos de turismo. Inicialmente a informação é classificada quanto ao tipo. Seguidamente são extraídos os elementos relevantes de cada tipo e gerados objectos facilmente computáveis. Sobre os objectos extraídos, o protótipo com recurso a modelos de textos e imagens gera automaticamente descrições normalizadas e orientadas a um determinado mercado. Esta versatilidade permite um novo conjunto de serviços na promoção e venda dos produtos que seria impossível implementar com a informação original. Este protótipo, embora possa ser aplicado a outros domínios, foi avaliado na normalização da descrição de hotéis. As frases descritivas do hotel são classificadas consoante o seu tipo (Local, Serviços e/ou Equipamento) através de um algoritmo de aprendizagem automática que obtém valores médios de cobertura de 96% e precisão de 72%. A cobertura foi considerada a medida mais importante uma vez que a sua maximização permite que não se percam frases para processamentos posteriores. Este trabalho permitiu também a construção e população de uma base de dados de hotéis que possibilita a pesquisa de hotéis pelas suas características. Esta funcionalidade não seria possível utilizando os conteúdos originais. ABSTRACT: The description of tourism products, like hotel, aviation, rent-a-car and holiday packages, is strongly supported on natural language expressions. Due to the extent of tourism offers and considering the high dynamics in the tourism sector, manual data management is not a reliable or scalable solution. Offer descriptions - in the order of thousands - are structured in different ways, possibly comprising different languages, complementing and/or overlap one another. This work aims at creating a prototype for the automatic classification and extraction of relevant knowledge from tourism-related text expressions. Captured knowledge is represented in a normalized/standard format to enable new services based on this information in order to promote and sale tourism products that would be impossible to implement with the raw information. Although it could be applied to other areas, this prototype was evaluated in the normalization of hotel descriptions. Hotels descriptive sentences are classified according their type (Location, Services and/or Equipment) using a machine learning algorithm. The built setting obtained an average recall of 96% and precision of 72%. Recall considered the most important measure of performance since its maximization allows that sentences were not lost in further processes. As a side product a database of hotels was built and populated with search facilities on its characteristics. This ability would not be possible using the original contents.

Upregulation of gp91(phox) Subunit of NAD(P)H Oxidase Contributes to Erectile Dysfunction Caused by Long-term Nitric Oxide Inhibition in Rats: Reversion by Regular Physical Training

OBJECTIVES To test the hypothesis that glyco protein 91phox (gp91(phox)) subunit of nicotinamide adenine dinucleotide phosphate [NAD(P) H] oxidase is a fundamental target for physical activity to ameliorate erectile dysfunction (ED). Vascular risk factors are reported to contribute to ED. Regular physical exercise prevents cardiovascular diseases by increasing nitric oxide (NO) production and/or decreasing NO inactivation. METHODS Male Wistar rats received the NO synthesis inhibitor N(omega)-nitro-L-arginine methyl ester (L-NAME) for 4 weeks, after which animals were submitted to a run training program for another 4 weeks. Erectile functions were evaluated by in vitro cavernosal relaxations and intracavernous pressure measurements. Expressions of gp91(phox) subunit and neuronal nitric oxidase synthase in erectile tissue, as well as superoxide dismutase activity and nitrite/nitrate (NO(x)) levels were determined. RESULTS The in vitro acetylcholine-and electrical field stimulation-induced cavernosal relaxations, as well as the increases in intracavernous pressure were markedly reduced in sedentary rats treated with L-NAME. Run training significantly restored the impaired cavernosal relaxations. No alterations in the neuronal nitric oxidase synthase protein expression (and its variant penile neuronal nitric oxidase synthase) were detected. A reduction of NO(x) levels and superoxide dismutase activity was observed in L-NAME-treated animals, which was significantly reversed by physical training. Gene expression of subunit gp91(phox) was enhanced by approximately 2-fold in erectile tissue of L-NAME-treated rats, and that was restored to basal levels by run training. CONCLUSIONS Our study shows that ED seen after long-term L-NAME treatment is associated with gp91(phox) subunit upregulation and decreased NO bioavailability. Exercise training reverses the increased oxidative stress in NO-deficient rats, ameliorating the ED. UROLOGY 75: 961-967, 2010. (C) 2009 Elsevier Inc.