|
|
Heuristics in String Solving
Řezáč, Michal ; Havlena, Vojtěch (oponent) ; Síč, Juraj (vedoucí práce)
This work aims on identifying heuristics and strategies used in modern string solvers and evaluating their impact on the effectiveness of the solving. In particular, two solvers -- cvc5 and Z3 -- are examined. The thesis describes the techniques used by SMT solvers and the strategies implemented by string solvers. The evaluation of the effectiveness of the heuristics was performed by disabling them directly in the code of the tools mentioned and then evaluating the impact on solving the sets of standard benchmarks. The result of this work is summary of a set of specific heuristics and a description of the structure of the tools cvc5 and Z3. The measurements failed to demonstrate the actual impact of the heuristics identified and described.
|
|
|
Transducers in Automata Library Mata
Chocholatý, David ; Lengál, Ondřej (oponent) ; Holík, Lukáš (vedoucí práce)
We implement finite transducers in a new fast and simple automata library Mata. Finite transducers are finite state machines modelling rational relations. Our primary use case for finite transducers is encoding replace operations (replacing a word or a regular pattern with a string literal). A recent automata-based SMT string solver Z3-Noodler uses Mata as a backbone of its decision procedure. Z3-Noodler needs finite transducers to analyse string manipulating programs with replace operations. The analysis of said programs used in web applications prevents software attacks such as cross-site scripting (XSS) or code injection. The distinctive features of Mata include simplicity (simple to use, modify and extend) and efficiency (fast to run). We design the representation and algorithms for finite transducers to fit the simplicity and efficiency requirements. We inherit and extend the existing data structures and algorithms for finite automata in Mata to represent the finite transducers and their operations. The representation for finite transducers serves as a common data structure and interface for the finite transducers and future representation of automata using multi-terminal binary decision diagrams to handle large alphabets. We further extend the design with algorithms to construct finite transducers modelling replace operations defined in SMT-LIB. Finally, we run an experimental evaluation of performance of finite transducers in Mata on a new benchmark with replace operations from runs of Z3-Noodler and from solving problems in pattern matching.
|
|
|
String Constraint Solving Through Parikh Images
Bartoš, Petr ; Havlena, Vojtěch (oponent) ; Holík, Lukáš (vedoucí práce)
This bachelor thesis aims to implement an alternative way of solving string constraints using the so-called flattening algorithm. The algorithm makes use of Parikh images and parametric flat automata to effectively convert string constraints to linear arithmetic, which allows for leveraging powerful SMT solvers. Solving constraints as an algebraic problem is supposed to be more efficient than standardly used automata-based techniques, as it avoids common pitfalls, such as state-space exposion. The thesis covers the theoretical knowledge required to understand the flattening algorithm and introduces alternative modern solution strategies. The implementation results are then compared to other solvers using conventional competition benchmarks. The conducted experiments show that while the speed of the implementation compared to other state-of-the-art solvers is worse, the effectiveness of the underapproximation itself is fairly promising, thus yielding mixed results.
|
host ::
RSS.