Efficient Regular Expression Pattern Matching for Network Intrusion Detection Systems using Modified Word-based Automata

Network Intrusion Detection Systems (NIDS) intercept the traffic at an organization's network periphery to thwart intrusion attempts. Signature-based NIDS compares the intercepted packets against its database of known vulnerabilities and malware signatures to detect such cyber attacks. These signatures are represented using Regular Expressions (REs) and strings. Regular Expressions, because of their higher expressive power, are preferred over simple strings to write these signatures. We present Cascaded Automata Architecture to perform memory efficient Regular Expression pattern matching using existing string matching solutions. The proposed architecture performs two stage Regular Expression pattern matching. We replace the substring and character class components of the Regular Expression with new symbols. We address the challenges involved in this approach. We augment the Word-based Automata, obtained from the re-written Regular Expressions, with counter-based states and length bound transitions to perform Regular Expression pattern matching. We evaluated our architecture on Regular Expressions taken from Snort rulesets. We were able to reduce the number of automata states between 50% to 85%. Additionally, we could reduce the number of transitions by a factor of 3 leading to further reduction in the memory requirements.

Simulation of potential and electric field across faulty ceramic disc insulator string

Ceramic/Porcelain insulators are widely used in power transmission lines to provide mechanical support for High voltage conductors in addition to withstand electrical stresses. As a result of lightning, switching or temporary over voltages that could initiate flashover under worst weather conditions, and to operate within interference limits. Given that the useful life in service of the individual insulator elements making up the insulator strings is hard to predict, they must be verified periodically to ensure that adequate line reliability is maintained at all times. Over the years utilities have adopted few methods to detect defective discs in a string, subsequently replacement of the faulty discs are being carried out for smooth operation. But, if the insulator is found to be defective in a string at some location that may not create any changes in the field configuration, there is no need to replace to avoid manpower and cost of replacement. Due to deficiency of electric field data for the existing string configuration, utilities are forced to replace the discs which may not be essentially required. Hence, effort is made in the present work to simulate the potential and electric field along the normal and with faults induced discs in a string up to 765 kV system voltages using Surface Charge Simulation Method (SCSM). A comparison is made between simulated results, experimental and field data and it was found that the computed results are quite acceptable and useful.

Generating string solutions in BTZ

Integrability of classical strings in the BTZ black hole enables the construction and study of classical string propagation in this background. We first apply the dressing method to obtain classical string solutions in the BTZ black hole. We dress time like geodesics in the BTZ black hole and obtain open string solutions which are pinned on the boundary at a single point and whose end points move on time like geodesics. These strings upon regularising their charge and spins have a dispersion relation similar to that of giant magnons. We then dress space like geodesics which start and end on the boundary of the BTZ black hole and obtain minimal surfaces which can penetrate the horizon of the black hole while being pinned at the boundary. Finally we embed the giant gluon solutions in the BTZ background in two different ways. They can be embedded as a spiral which contracts and expands touching the horizon or a spike which originates from the boundary and touches the horizon.

OTCYMIST: Otsu-Canny minimal spanning tree for born-digital images

Text segmentation and localization algorithms are proposed for the born-digital image dataset. Binarization and edge detection are separately carried out on the three colour planes of the image. Connected components (CC's) obtained from the binarized image are thresholded based on their area and aspect ratio. CC's which contain sufficient edge pixels are retained. A novel approach is presented, where the text components are represented as nodes of a graph. Nodes correspond to the centroids of the individual CC's. Long edges are broken from the minimum spanning tree of the graph. Pair wise height ratio is also used to remove likely non-text components. A new minimum spanning tree is created from the remaining nodes. Horizontal grouping is performed on the CC's to generate bounding boxes of text strings. Overlapping bounding boxes are removed using an overlap area threshold. Non-overlapping and minimally overlapping bounding boxes are used for text segmentation. Vertical splitting is applied to generate bounding boxes at the word level. The proposed method is applied on all the images of the test dataset and values of precision, recall and H-mean are obtained using different approaches.

Black hole formation in fuzzy sphere collapse

We study the collapse of a fuzzy sphere, that is a spherical membrane built out of D0-branes, in the Banks-Fischler-Shenker-Susskind model. At weak coupling, as the sphere shrinks, open strings are produced. If the initial radius is large then open string production is not important and the sphere behaves classically. At intermediate initial radius the backreaction from open string production is important but the fuzzy sphere retains its identity. At small initial radius the sphere collapses to form a black hole. The crossover between the later two regimes is smooth and occurs at the correspondence point of Horowitz and Polchinski.

Structure constants of beta deformed super Yang-Mills

We study the structure constants of the N = 1 beta deformed theory perturbatively and at strong coupling. We show that the planar one loop corrections to the structure constants of single trace gauge invariant operators in the scalar sector is determined by the anomalous dimension Hamiltonian. This result implies that 3 point functions of the chiral primaries of the theory do not receive corrections at one loop. We then study the structure constants at strong coupling using the Lunin-Maldacena geometry. We explicitly construct the supergravity mode dual to the chiral primary with three equal U(1) R-charges in the Lunin-Maldacena geometry. We show that the 3 point function of this supergravity mode with semi-classical states representing two other similar chiral primary states but with large U(1) charges to be independent of the beta deformation and identical to that found in the AdS(5) x S-5 geometry. This together with the one-loop result indicate that these structure constants are protected by a non-renormalization theorem. We also show that three point function of U(1) R-currents with classical massive strings is proportional to the R-charge carried by the string solution. This is in accordance with the prediction of the R-symmetry Ward identity.

Packaging of Polyvinylidene fluoride nasal sensor for biomedical applications

This paper presents the design technique that has been adopted for packaging of Polyvinylidene fluoride (PVDF) nasal sensor for biomedical applications. The PVDF film with the dimension of length 10mm, width 5mm and thickness 28 mu m was firmly adhered on one end of plastic base (8mmx5mmx30 mu m) in such a way that it forms a cantilever configuration leaving the other end free for deflection. Now with the leads attached on the surface of the PVDF film, the cantilever configuration becomes the PVDF nasal sensor. For mounting a PVDF nasal sensor, a special headphone was designed, that can fit most of the human head sizes. Two flexible strings are soldered on either side of the headphone. Two identical PVDF nasal sensors were then connected to either side of flexible string of the headphone in such a way that they are placed below the right and left nostrils respectively without disturbing the normal breathing. When a subject wares headphone along with PVDF nasal sensors, two voltage signals due to the piezoelectric property of the PVDF film were generated corresponding to his/her nasal airflow from right and left nostril. The entire design was made compact, so that PVDF nasal sensors along with headphone can be made portable. No special equipment or machines are needed for mounting the PVDF nasal sensors. The time required for packaging of PVDF nasal sensors was less and the approximate cost of the entire assembly (PVDF nasal sensors + headphone) was very nominal.

Correlation between local structural dynamics of proteins inferred from NMR ensembles and evolutionary dynamics of homologues of known structure

Conformational changes in proteins are extremely important for their biochemical functions. Correlation between inherent conformational variations in a protein and conformational differences in its homologues of known structure is still unclear. In this study, we have used a structural alphabet called Protein Blocks (PBs). PBs are used to perform abstraction of protein 3-D structures into a 1-D strings of 16 alphabets (a-p) based on dihedral angles of overlapping pentapeptides. We have analyzed the variations in local conformations in terms of PBs represented in the ensembles of 801 protein structures determined using NMR spectroscopy. In the analysis of concatenated data over all the residues in all the NMR ensembles, we observe that the overall nature of inherent local structural variations in NMR ensembles is similar to the nature of local structural differences in homologous proteins with a high correlation coefficient of .94. High correlation at the alignment positions corresponding to helical and beta-sheet regions is only expected. However, the correlation coefficient by considering only the loop regions is also quite high (.91). Surprisingly, segregated position-wise analysis shows that this high correlation does not hold true to loop regions at the structurally equivalent positions in NMR ensembles and their homologues of known structure. This suggests that the general nature of local structural changes is unique; however most of the local structural variations in loop regions of NMR ensembles do not correlate to their local structural differences at structurally equivalent positions in homologues.

Efficient Dictionary for Salted Password Analysis

User authentication is essential for accessing computing resources, network resources, email accounts, online portals etc. To authenticate a user, system stores user credentials (user id and password pair) in system. It has been an interested field problem to discover user password from a system and similarly protecting them against any such possible attack. In this work we show that passwords are still vulnerable to hash chain based and efficient dictionary attacks. Human generated passwords use some identifiable patterns. We have analysed a sample of 19 million passwords, of different lengths, available online and studied the distribution of the symbols in the password strings. We show that the distribution of symbols in user passwords is affected by the native language of the user. From symbol distributions we can build smart and efficient dictionaries, which are smaller in size and their coverage of plausible passwords from Key-space is large. These smart dictionaries make dictionary based attacks practical.

Clemaps: Multiple Alignment Of Protein Structures Based On Conformational Letters

CLEMAPS is a tool for multiple alignment of protein structures. It distinguishes itself from other existing algorithms for multiple structure alignment by the use of conformational letters, which are discretized states of 3D segmental structural states. A letter corresponds to a cluster of combinations of three angles formed by C-alpha pseudobonds of four contiguous residues. A substitution matrix called CLESUM is available to measure the similarity between any two such letters. The input 3D structures are first converted to sequences of conformational letters. Each string of a fixed length is then taken as the center seed to search other sequences for neighbors of the seed, which are strings similar to the seed. A seed and its neighbors form a center-star, which corresponds to a fragment set of local structural similarity shared by many proteins. The detection of center-stars using CLESUM is extremely efficient. Local similarity is a necessary, but insufficient, condition for structural alignment. Once center-stars are found, the spatial consistency between any two stars are examined to find consistent star duads using atomic coordinates. Consistent duads are later joined to create a core for multiple alignment, which is further polished to produce the final alignment. The utility of CLEMAPS is tested on various protein structure ensembles.

Metric representation of DNA sequences

A metric representation of DNA sequences is borrowed from symbolic dynamics. In view of this method, the pattern seen in the chaos game representation of DNA sequences is explained as the suppression of certain nucleotide strings in the DNA sequences. Frequencies of short nucleotide strings and suppression of the shortest ones in the DNA sequences can be determined by using the metric representation.

Self-similarity limits of genomic signatures

It is shown that metric representation of DNA sequences is one-to-one. By using the metric representation method, suppression of nucleotide strings in the DNA sequences is determined. For a DNA sequence, an optimal string length to display genomic signature in chaos game representation is obtained by eliminating effects of the finite sequence. The optimal string length is further shown as a self-similarity limit in computing information dimension. By using the method, self-similarity limits of bacteria complete genomic signatures are further determined.

Recurrence plot analysis of DNA sequences

Recurrence plot technique of DNA sequences is established on metric representation and employed to analyze correlation structure of nucleotide strings. It is found that, in the transference of nucleotide strings, a human DNA fragment has a major correlation distance, but a yeast chromosome's correlation distance has a constant increasing. (C) 2004 Elsevier B.V All rights reserved.

Critical current anisotropy in high temperature superconductors

After nearly 15 years of research effort, High Temperature Superconductors (HTS) are finding a wide range of practical applications. A clear understanding of the factors controlling the current carrying capacity of these materials is a prerequisite to their successful technological development. The critical current density (Jc) in HTS is directly dependent on the structure and pinning of the Flux Line Lattice (FLL) in these materials. This thesis presents an investigation of the Jc anisotropy in HTS. The use of thin films grown on off c-axis (vicinal) substrates allowed the effect of current directions outside the cuprate planes to be studied. With this experimental geometry Berghuis, et al. (Phys. Rev. Lett. 79, 12, pg. 2332) observed a striking flux channelling effect in vicinal YBa2Cu3O7-δ (YBCO) films. By confirming, and extending, this observation, it is demonstrated that this is an intrinsic effect. The results obtained, appear to fit well with the predictions of a field angle dependent cross-over from a three dimensional rectilinear FLL to a kinked lattice of strings and pancakes. The pinning force density for movement of strings inside the cuprate planes is considerably less than that on vortex pancake elements. When the FLL is entirely string-like this reduced pinning leads to the observed channelling minima. It is observed that anti-phase boundaries enhance the Jc in vicinal YBCO films by strongly pinning vortex strings. The effect on the FLL structure cross-over of increasing anisotropy has been elucidated using de-oxygenated vicinal YBCO films. Intriguingly, the counter intuitive prediction that the range of applied field angle for which the kinked lattice is fully developed reduces with increasing anisotropy, appears to be confirmed. Although vortex channelling cannot be observed in c-axis YBCO films, the pinning force density for vortex string channelling has been extracted by observing string dragging. By studying the effect of rotating the applied field at a constant angle to the cuprate planes, it is possible to observe the cross-over into the string pancake regime in c-axis films. In the 3D region, the observed behaviour is well explained by the anisotropic Ginzburg-Landau model. Measurements were also made on thin films of the much more anisotropic Bi 2Sr2CaCu2O8+x material, grown on vicinal substrates. The absence of any flux channelling effect and clear adherence to the expected Kes-Law behaviour in the observed Jc characteristics does not provide evidence for the existence of the predicted ‘crossing lattice’ in Bi 2Sr2CaCu2O8+x .

Synthetic molecular machines for active self-assembly : prototype algorithms, designs, and experimental study

Computer science and electrical engineering have been the great success story of the twentieth century. The neat modularity and mapping of a language onto circuits has led to robots on Mars, desktop computers and smartphones. But these devices are not yet able to do some of the things that life takes for granted: repair a scratch, reproduce, regenerate, or grow exponentially fast–all while remaining functional.

This thesis explores and develops algorithms, molecular implementations, and theoretical proofs in the context of “active self-assembly” of molecular systems. The long-term vision of active self-assembly is the theoretical and physical implementation of materials that are composed of reconfigurable units with the programmability and adaptability of biology’s numerous molecular machines. En route to this goal, we must first find a way to overcome the memory limitations of molecular systems, and to discover the limits of complexity that can be achieved with individual molecules.

One of the main thrusts in molecular programming is to use computer science as a tool for figuring out what can be achieved. While molecular systems that are Turing-complete have been demonstrated [Winfree, 1996], these systems still cannot achieve some of the feats biology has achieved.

One might think that because a system is Turing-complete, capable of computing “anything,” that it can do any arbitrary task. But while it can simulate any digital computational problem, there are many behaviors that are not “computations” in a classical sense, and cannot be directly implemented. Examples include exponential growth and molecular motion relative to a surface.

Passive self-assembly systems cannot implement these behaviors because (a) molecular motion relative to a surface requires a source of fuel that is external to the system, and (b) passive systems are too slow to assemble exponentially-fast-growing structures. We call these behaviors “energetically incomplete” programmable behaviors. This class of behaviors includes any behavior where a passive physical system simply does not have enough physical energy to perform the specified tasks in the requisite amount of time.

As we will demonstrate and prove, a sufficiently expressive implementation of an “active” molecular self-assembly approach can achieve these behaviors. Using an external source of fuel solves part of the the problem, so the system is not “energetically incomplete.” But the programmable system also needs to have sufficient expressive power to achieve the specified behaviors. Perhaps surprisingly, some of these systems do not even require Turing completeness to be sufficiently expressive.

Building on a large variety of work by other scientists in the fields of DNA nanotechnology, chemistry and reconfigurable robotics, this thesis introduces several research contributions in the context of active self-assembly.

We show that simple primitives such as insertion and deletion are able to generate complex and interesting results such as the growth of a linear polymer in logarithmic time and the ability of a linear polymer to treadmill. To this end we developed a formal model for active-self assembly that is directly implementable with DNA molecules. We show that this model is computationally equivalent to a machine capable of producing strings that are stronger than regular languages and, at most, as strong as context-free grammars. This is a great advance in the theory of active self- assembly as prior models were either entirely theoretical or only implementable in the context of macro-scale robotics.

We developed a chain reaction method for the autonomous exponential growth of a linear DNA polymer. Our method is based on the insertion of molecules into the assembly, which generates two new insertion sites for every initial one employed. The building of a line in logarithmic time is a first step toward building a shape in logarithmic time. We demonstrate the first construction of a synthetic linear polymer that grows exponentially fast via insertion. We show that monomer molecules are converted into the polymer in logarithmic time via spectrofluorimetry and gel electrophoresis experiments. We also demonstrate the division of these polymers via the addition of a single DNA complex that competes with the insertion mechanism. This shows the growth of a population of polymers in logarithmic time. We characterize the DNA insertion mechanism that we utilize in Chapter 4. We experimentally demonstrate that we can control the kinetics of this re- action over at least seven orders of magnitude, by programming the sequences of DNA that initiate the reaction.

In addition, we review co-authored work on programming molecular robots using prescriptive landscapes of DNA origami; this was the first microscopic demonstration of programming a molec- ular robot to walk on a 2-dimensional surface. We developed a snapshot method for imaging these random walking molecular robots and a CAPTCHA-like analysis method for difficult-to-interpret imaging data.