No description available.

Regular expressions (regexes) are a widely-used yet little-studied software component. Engineers use regexes to match domain-specific languages of strings. Unfortunately, many regex engine implementations perform these matches with worst-case polynomial or exponential time complexity in the length of the string. Because they are commonly used in user-facing contexts, super-linear regexes are a potential denial of service vector known as Regular expression Denial of Service (ReDoS). Part I gives the necessary background to understand this problem. In Part II of this dissertation, I present the first large-scale empirical studies of super-linear regex use. Guided by case studies of ReDoS issues in practice (Chapter 3), I report that the risk of ReDoS affects up to 10% of the regexes used in practice (Chapter 4), and that these findings generalize to software written in eight popular programming languages (Chapter 5). ReDoS appears to be a widespread vulnerability, motivating the consideration of defenses. In Part III I present the first systematic comparison of ReDoS defenses. Based on the necessary conditions for ReDoS, a ReDoS defense can be erected at the application level, the regex engine level, or the framework/runtime level. In my experiments I report that application-level defenses are difficult and error prone to implement (Chapter 6), that finding a compatible higher-performing regex engine is unlikely (Chapter 7), that optimizing an existing regex engine using memoization incurs (perhaps acceptable) space overheads (Chapter 8), and that incorporating resource caps into the framework or runtime is feasible but faces barriers to adoption (Chapter 9). In Part IV of this dissertation, we reflect on our findings. By leveraging empirical software engineering techniques, we have exposed the scope of potential ReDoS vulnerabilities, and given strong motivation for a solution. To assist practitioners, we have conducted a systematic evaluation of the solution space. We hope that our findings assist in the elimination of ReDoS, and more generally that we have provided a case study in the value of data-driven software engineering. / Doctor of Philosophy / Software commonly performs pattern-matching tasks on strings. For example, when validating input in a Web form, software commonly tests whether an input fits the pattern of a credit card number or an email address. Software engineers often implement such string-based pattern matching using a tool called regular expressions (regexes). Regexes permit software engineers to succinctly describe the sequences of characters that make up common "languages" like the set of valid Visa credit card numbers (16 digits, starting with a 4) or the set of valid emails (some characters, an '@', and more characters including at least one'.'). Using regexes on untrusted user input in this manner may be a dangerous decision because some regexes take a long time to evaluate. These slow regexes can be exploited by attackers in order to carry out a denial of service attack known as Regular expression Denial of Service (ReDoS). To date, ReDoS has led to outages affecting hundreds of websites and tens of thousands of users. While the risk of ReDoS is well known in theory, in this dissertation I present the first large-scale empirical studies measuring the extent to which slow regular expressions are used in practice. I found that about 10% of real regular expressions extracted from hundreds of thousands of software projects can exhibit longer-than-expected worst-case behavior in popular programming languages including JavaScript, Python, and Ruby. Motivated by these findings, I then consider a range of ReDoS solution approaches: application refactoring, regex engine replacement, regex engine optimization, and resource caps. I report that application refactoring is error-prone, and that regex engine replacement seems unlikely due to incompatibilities between regex engines. Some resource caps are more successful than others, but all resource cap approaches struggle with adoption. My novel regex engine optimizations seem the most promising approach for protecting existing regex engines, offering significant time reductions with acceptable space overheads.

Uma decomposição de um grafo G é um conjunto D = {H_1,... , H_k } de subgrafos de G dois-a-dois aresta-disjuntos que cobre o conjunto das arestas de G. Se H_i é isomorfo a um grafo fixo H, para 1<=i<=k, então dizemos que D é uma H-decomposição de G. Neste trabalho, estudamos o caso em que H é um caminho de comprimento fixo. Para isso, primeiramente decompomos o grafo dado em trilhas, e depois fazemos uso de um lema de desemaranhamento, que nos permite transformar essa decomposição em trilhas numa decomposição somente em caminhos. Com isso, obtemos resultados para três conjecturas sobre H-decomposição de grafos no caso em que H=P_\\ell é o caminho de comprimento \\ell. Dois desses resultados resolvem versões fracas das Conjecturas de Kouider e Lonc (1999) e de Favaron, Genest e Kouider (2010), ambas para grafos regulares. Provamos que, para todo inteiro positivo \\ell, (i) existe um inteiro positivo m_0 tal que se G é um grafo 2m\\ell-regular com m>=m_0, então G admite uma P_\\ell-decomposição; (ii) se \\ell é ímpar, existe um inteiro positivo m_0 tal que se G é um grafo m\\ell-regular com m>=m_0, e G contém um m-fator, então G admite uma P_\\ell-decomposição. O terceiro resultado diz respeito a grafos altamente aresta- conexos: existe um inteiro positivo k_\\ell tal que se G é um grafo k_\\ell-aresta-conexo cujo número de arestas é divisível por \\ell, então G admite uma P_\\ell-decomposição. Esse resultado prova que a Decomposition Conjecture de Barát e Thomassen (2006), formulada para árvores, é verdadeira para caminhos. / A decomposition of a graph G is a set D = {H_1,...,H_k} of pairwise edge-disjoint subgraphs of G that cover the set of edges of G. If H_i is isomorphic to a fixed graph H, for 1<=i<=k, then we say that D is an H-decomposition of G. In this work, we study the case where H is a path of fixed length. For that, we first decompose the given graph into trails, and then we use a disentangling lemma, that allows us to transform this decomposition into one consisting only of paths. With this approach, we tackle three conjectures on H-decomposition of graphs and obtain results for the case H=P_\\ell is the path of length \\ell. Two of these results solve weakenings of a conjecture of Kouider and Lonc (1999) and a conjecture of Favaron, Genest and Kouider (2010), both for regular graphs. We prove that, for every positive integer \\ell, (i) there is a positive integer m_0 such that, if G is a 2m\\ell-regular graph with m>=m_0, then G admits a P_\\ell-decomposition; (ii) if \\ell is odd, there is a positive integer m_0 such that, if G is an m\\ell-regular graph with m>=m_0 containing an m-factor, then G admits a P_\\ell-decomposition. The third result concerns highly edge-connected graphs: there is a positive integer k_\\ell such that if G is a k_\\ell-edge-connected graph whose number of edges is divisible by \\ell, then G admits a P_\\ell-decomposition. This result verifies for paths the Decomposition Conjecture of Barát and Thomassen (2006), on trees.

Neste trabalho estudamos problemas de evolução da forma \'d \' úpsilond\' SUP. \' úpsilon\' t\'\' + A (t,\'úpsilon\' )\' úpsilon\' = f(t,\'úpsilon\' ) \'úpsilon\'(0) = \' \' úpsilon\' IND. 0\' \', em um espaço de Banach X onde A(t, \'úpsilon\' ) : D \'está contido em\' X \'SETA \' X é um operador linear fechado e setorial para cada (t, \' úpsilon\' ). Quando o operador A(t, \' úpsilon\' ) é independente de \' úpsilon\' , isto é, A(t, \' úpsilon\') = A(t), mostramos um resultado de exitência, unicidade, continuidade relativamente a dados iniciais e continuação para o caso em que a não linearidade f tem crescimento crítico. Se A(t, \'úpsilon\' ) depende do tempo e do estado, então mostramos um resultado de existência, unicidade com f tendo crescimento sub-crítico semelhante aos resultados encontrados em [7, 33] / In this work we study initial value problems of the form \' d \'úpsilon\' SUP. dt + A (t, \'úpsilon\')\'úpsilon\' = f (t, \'úpsilon\' ) \' úpsilon\' (0) = \' úpsilon IND.0\', in a Banach space X where A(t,\' úpsilon\' ) : D \' this contained \' X \' ARROW\' X is an unbounded closed linear operator which is sectorial for each (t,\' úpsilon\' ). When the operator family A(t, \' úpsilon\' ) is independent of \' úpsilon\' , that is, A(t, \' úpsilon\' ) = A(t), we show a result on local well posedness and continuation with the nonlinearity f growing critically. If A(t,\' úpsilon\' ) depends on the time t and on the state \' úpsilon\' we show a local well posedness and continuation result that is similar to the result found in [7, 33]

Submitted by Cássia Santos (cassia.bcufg@gmail.com) on 2016-08-05T13:23:07Z No. of bitstreams: 2 Dissertação - Isabela de Freitas Morais - 2016.pdf: 4449432 bytes, checksum: 0dfddae749b3f5da42fc04aad7f208ac (MD5) license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) / Approved for entry into archive by Luciana Ferreira (lucgeral@gmail.com) on 2016-08-05T13:27:36Z (GMT) No. of bitstreams: 2 Dissertação - Isabela de Freitas Morais - 2016.pdf: 4449432 bytes, checksum: 0dfddae749b3f5da42fc04aad7f208ac (MD5) license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) / Made available in DSpace on 2016-08-05T13:27:36Z (GMT). No. of bitstreams: 2 Dissertação - Isabela de Freitas Morais - 2016.pdf: 4449432 bytes, checksum: 0dfddae749b3f5da42fc04aad7f208ac (MD5) license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) Previous issue date: 2016-05-11 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior - CAPES / The school part in society is extremely important. It is at school that cultural and ideological foundations are guided in the child and youth's life to develop socially, in the best way. Schools as a place of learning, socialization and exchange of experiences, it is necessary to think what are the educational policies of inclusion of students with disabilities, global development disorders and high skills / giftedness, established at national and regional level. Guided by the philosophy of equal inclusion of all students in regular Brazilian schools, and in particular in the city of Goiânia - Goiás, this research will focus on analyzing, critically, educational documents from Brazil and Goiás, regarding to the inclusion of disabled students in the regular school system and the reality presented in the public high schools from Goiânia. The general objective is to verify how is the current inclusion situation in mainstream education of disabled students and with special educational needs. Regular attendance at school is a rights guaranteed to all or any citizen, but these ideas and ideals cannot remain only on paper, therefore the execution of this research is justified in trying to investigate if everything which was put, officially, in laws of inclusion is being practiced in public high schools in Goiânia. The law guarantees equal rights to all citizens, it depends on us the role of checking and collect its application to everyone who can enjoy the legitimate rights guaranteed by the state. Respecting the difference of the other the quest for justice are tools to be used in pursuit of a better society for all. / O papel da escola na sociedade é de grande importância. É na escola que os fundamentos culturais e ideológicos são pautados na vida da criança e do jovem para que se desenvolvam, socialmente, da melhor forma. Sendo a escola um espaço de aprendizagem, socialização e troca de experiências, é necessário pensar quais são as políticas educacionais de inclusão de alunos com deficiência, transtornos globais do desenvolvimento e altas habilidades/superdotação, estabelecidas a nível nacional e regional. Pautada na filosofia de inclusão igualitária de todos os discentes nas escolas regulares de ensino brasileiras, e em específico na cidade de Goiânia – Goiás, esta dissertação focará em analisar, de forma crítica, os documentos educacionais nacionais e de Goiás, no que tange à inclusão de alunos deficientes no sistema regular de ensino e à realidade apresentada nas escolas públicas estaduais de nível médio de Goiânia. O objetivo geral é verificar como está a situação de inclusão dos alunos deficientes e com necessidades educacionais especiais no sistema regular de ensino. A frequência regular na escola é um dos direitos de todo e qualquer cidadão, mas essas ideias e ideais não podem ficar somente no papel, portanto, a execução desta pesquisa se justifica na tentativa de investigar se tudo o que está posto, oficialmente, nas leis de inclusão está sendo praticado nas escolas públicas estaduais de ensino de Goiânia. A lei garante o direito igual a todos os cidadãos, cabe a nós o papel de verificar e cobrar sua aplicação para que todos possam gozar dos direitos legítimos garantidos pelo Estado. O respeito à diferença do outro e a busca pela justiça são ferramentas que devem ser utilizadas em busca de uma sociedade melhor para todos.

Made available in DSpace on 2016-03-15T19:42:26Z (GMT). No. of bitstreams: 1 Rosangela Nezeiro da Fonseca Jacob.pdf: 1474630 bytes, checksum: 7b55d03a0fb7788942349c44bb86107a (MD5) Previous issue date: 2012-08-17 / Perkins School for the Blind / Students with sensory disabilities have multiple forms of communication and language that is very specific, and this is the great challenge of regular school, when at the inclusion of these students in the common room. Thus, the present study was based on the definitions and characterizations of sensory and multiple disabilities in the forms of communication pre-symbolic and symbolic, highlighting the possibilities of communication and language of individuals with this disability. With the support of the theory of Vigotski and the Bakhtin's theory contributions, it is discussed and investigated the extent of trade between pairs for effective communication and language of individuals. In order to understand the dialogic processes between teacher and student with multiple sensory disabilities, the research had as information-gathering interviews, observations and video recordings. The analysis of the collected material led to the conclusion that the student enrolled in a teacher s class room, who received expert advice on the specific forms of communication and language of students with multiple sensory disabilities perform adjustments as the effective inclusion of students, however, the teacher that did not receive the same orientation, despite the intention of the adjustments, did not make real the actions that allow the inclusion of the student. / Alunos com múltipla deficiência sensorial apresentam formas de comunicação e linguagem bastante específicas, sendo este o grande desafio da escola regular, quando da inclusão destes alunos na sala comum. Deste modo, a presente pesquisa fundamentou-se nas definições e caracterizações da múltipla deficiência sensorial e nas formas de comunicação pré-simbólica e simbólica, destacando as possibilidades de comunicação e linguagem de indivíduos com esta deficiência. Com suporte na teoria de Vigotski e contribuições da teoria de Bakhtin, discutiu-se e investigou-se a importância das trocas entre os pares para a efetivação da comunicação e linguagem dos indivíduos. Com o objetivo de conhecer os processos dialógicos entre professor e aluno com múltipla deficiência sensorial, a pesquisa teve como recurso de coleta de informações: entrevistas, observações e registros em vídeo. A análise do material coletado levou à conclusão de que o aluno matriculado em sala de professora que recebeu orientação especializada sobre as especificidades das formas de comunicação e linguagem de alunos com múltipla deficiência sensorial realiza adequações para a efetiva inclusão do aluno; no entanto, a professora que não recebeu a mesma orientação, apesar da intenção para as adequações, não consegue concretizar ações que viabilizem a inclusão do aluno.

Made available in DSpace on 2016-03-15T19:43:34Z (GMT). No. of bitstreams: 1 Bruna Bellinato Scrivanti Santana.pdf: 6645668 bytes, checksum: 746399cc3dac36b0c30009306ed15ba8 (MD5) Previous issue date: 2009-08-13 / Fundo Mackenzie de Pesquisa / This study refers to the educational inclusion of students with intellectual disabilities in Londrina - Paraná, according to testimony from four teachers of municipal schools. The objective of this study was to systematize and analyze the performance of these types of teachers from 1st to 5th year of the mainstream of what actually happens in the classroom with the deaf student rights - the possibilities and difficulties, adjustments, material support and specific courses for professionals from the public, for the care of students with intellectual disabilities in regular education. This dissertation is composed of two chapters. The first, on the theoretical foundation is on education of children with intellectual disabilities with data from the historical relations of special education in Brazil, its characteristics and conceptual changes, to the proposal of inclusion of students with intellectual disabilities in regular education. It also describes data on intellectual disabilities, their characteristics, the question of diagnosis and assessment and placement of educational assessment in accordance with the CIF, as opposed to physician placement in accordance with the ICD. In the second chapter highlights interviews with teachers in the municipality of the regular education with a data collection was performed from August 2008 to June 2009, and with the consent of research subjects, the interviews were recorded. The data were analyzed based on the categories listed in the schedule of the interviews and organized in the framework of convergence and divergence in relation to work performed in regular education with students with intellectual disabilities. Data were collected from four teachers of municipal schools, which make the process of inclusion in your classroom. The analysis showed ways of working to somewhat in municipal schools that follow or should follow a standard procedure for the inclusion of students with intellectual disabilities in the classroom, the schools surveyed. A big surprise was the unpreparedness of teachers to see the students with intellectual disabilities in regular education. / Este estudo se refere à inclusão escolar de alunos com deficiência intelectual no Município de Londrina Paraná, segundo depoimentos de quatro professoras da rede municipal de ensino. O objetivo central desta pesquisa foi o de sistematizar e analisar as formas de atuação dessas professoras do 1º ao 5º ano do ensino regular, do que de fato acontece em sala de aula com o aluno deficiente intelectual as possibilidade e dificuldades, as adequações, material de apoio e cursos específicos aos profissionais da rede pública, para o atendimento do aluno com deficiência intelectual no ensino regular. Esta dissertação está composta por dois capítulos. O primeiro, referente à fundamentação teórica, é sobre a Educação da criança com deficiência intelectual com dados das relações históricas da educação especial no Brasil, suas características e transformações conceituais, até a proposta da inclusão do aluno com deficiência intelectual no ensino regular. Descreve também dados sobre a deficiência intelectual, suas características, a questão do diagnóstico e avaliação e o posicionamento da avaliação educacional em concordância com a CIF, em contraposição ao posicionamento médico em concordância com a CID. No segundo capítulo, destaca as entrevistas realizadas no município com professoras da rede regular de educação,com uma coleta de dados que foi realizada no período de agosto de 2008 a junho de 2009, e com a autorização dos sujeitos da pesquisa, as entrevistas foram gravadas. Os dados foram analisados a partir de categorias referenciadas no roteiro das entrevistas e organizados em quadro de convergências e divergências, em relação ao trabalho realizado no ensino regular com os alunos com deficiência intelectual. Foram coletados dados de quatro professoras da rede Municipal de ensino, que fazem o processo de inclusão em sua sala de aula. A análise evidenciou formas de trabalho pouco convergentes em escolas municipais que seguem ou deveriam seguir um padrão para o processo de inclusão do aluno com deficiência intelectual em sala de aula, nas escolas pesquisadas. Uma grande surpresa foi o despreparo dessas professoras para o atendimento dos alunos com deficiência intelectual no ensino regular.

In formal language theory, studying shortest strings in languages, and variations thereof, can be useful since these strings can serve as small witnesses for properties of the languages, and can also provide bounds for other problems involving languages. For example, the length of the shortest string accepted by a regular language provides a lower bound on the state complexity of the language. In Chapter 1, we introduce some relevant concepts and notation used in automata and language theory, and we show some basic results concerning the connection between the length of the shortest string and the nondeterministic state complexity of a regular language. Chapter 2 examines the effect of the intersection operation on the length of the shortest string in regular languages. A tight worst-case bound is given for the length of the shortest string in the intersection of two regular languages, and loose bounds are given for two variations on the problem. Chapter 3 discusses languages that are defined over a free group instead of a free monoid. We study the length of the shortest string in a regular language that becomes the empty string in the free group, and a variety of bounds are given for different cases. Chapter 4 mentions open problems and some interesting observations that were made while studying two of the problems: finding good bounds on the length of the shortest squarefree string accepted by a deterministic finite automaton, and finding an efficient way to check if a finite set of finite words generates the free monoid. Some of the results in this thesis have appeared in work that the author has participated in \cite{AngPigRamSha,AngShallit}.

In formal language theory, studying shortest strings in languages, and variations thereof, can be useful since these strings can serve as small witnesses for properties of the languages, and can also provide bounds for other problems involving languages. For example, the length of the shortest string accepted by a regular language provides a lower bound on the state complexity of the language. In Chapter 1, we introduce some relevant concepts and notation used in automata and language theory, and we show some basic results concerning the connection between the length of the shortest string and the nondeterministic state complexity of a regular language. Chapter 2 examines the effect of the intersection operation on the length of the shortest string in regular languages. A tight worst-case bound is given for the length of the shortest string in the intersection of two regular languages, and loose bounds are given for two variations on the problem. Chapter 3 discusses languages that are defined over a free group instead of a free monoid. We study the length of the shortest string in a regular language that becomes the empty string in the free group, and a variety of bounds are given for different cases. Chapter 4 mentions open problems and some interesting observations that were made while studying two of the problems: finding good bounds on the length of the shortest squarefree string accepted by a deterministic finite automaton, and finding an efficient way to check if a finite set of finite words generates the free monoid. Some of the results in this thesis have appeared in work that the author has participated in \cite{AngPigRamSha,AngShallit}.

This thesis considers spectral approaches to finding maximum cocliques in graphs. We focus on the relation between the eigenspaces of a graph and the size and location of its maximum cocliques. Our main result concerns the computational problem of finding the size of a maximum coclique in a graph. This problem is known to be NP-Hard for general graphs. Recently, Codenotti et al. showed that computing the size of a maximum coclique is still NP-Hard if we restrict to the class of circulant graphs. We take an alternative approach to this result using quotient graphs and coding theory. We apply our method to show that computing the size of a maximum coclique is NP-Hard for the class of Cayley graphs for the groups $\mathbb{Z}_p^n$ where $p$ is any fixed prime. Cocliques are closely related to equitable partitions of a graph, and to parallel faces of the eigenpolytopes of a graph. We develop this connection and give a relation between the existence of quadratic polynomials that vanish on the vertices of an eigenpolytope of a graph, and the existence of elements in the null space of the Veronese matrix. This gives a us a tool for finding equitable partitions of a graph, and proving the non-existence of equitable partitions. For distance-regular graphs we exploit the algebraic structure of association schemes to derive an explicit formula for the rank of the Veronese matrix. We apply this machinery to show that there are strongly regular graphs whose $\tau$-eigenpolytopes are not prismoids. We also present several partial results on cocliques and graph spectra. We develop a linear programming approach to the problem of finding weightings of the adjacency matrix of a graph that meets the inertia bound with equality, and apply our technique to various families of Cayley graphs. Towards characterizing the maximum cocliques of the folded-cube graphs, we find a class of large facets of the least eigenpolytope of a folded cube, and show how they correspond to the structure of the graph. Finally, we consider equitable partitions with additional structural constraints, namely that both parts are convex subgraphs. We show that Latin square graphs cannot be partitioned into a coclique and a convex subgraph.