15th Estonian Winter School in Computer Science (EWSCS)
XV Eesti Arvutiteaduse Talvekool

Palmse, Estonia, February 28 -March 5, 2010

Student Talks 2010 (abstracts)

A Type Checker for Multi-Targeted Parser Specifications

Andrey Breslav
University of Tartu, Inst. of Computer Science, Estonia

Parser generators are used to generate translators from context-free grammars with annotations. They produce code in a target language (e.g., C or Java) which can be used, for example, in a compiler. The generated code may contain errors if the annotations are inconsistent, for example, violate type system restrictions. Most parser generators do not check the grammars and may happily produce code that does not compile.

In this talk I will present a parser generator which ensures the typing constraints for annotations and does not generate code with type errors. Its type system is abstract and may be instantiated for a particular target language such as Java or C. Polymorphic types and functions are supported, as well as local type inference. This enables a multi-target parsing generation to be safe and less complicated to develop.

Comparative Testing of Face Detection Algorithms

Nikolay Degtyarev
Tula State University, Russia

The face detection tasks are getting more and more required in the modern world. This is caused by the development of security systems in response to terrorist acts. In addition, these algorithms are wildly used in interactive user interfaces, in commercials industry to count the number of consumers, entertaiment services and etc. However, until recently, there were no practical and independent comparisons of FD algorithms.

In our work, we present the results of comparative tests of 6 algorithms. These tests are based on proposed method of face detection algorithms comparison, that allow to compare algorithms which yield results in different representations. The main approach used in this research is routine testing of algorithms on unique datasets, followed by comparing the output to manually marked faces.

At the end of the work, we are introducing a possible way of the combination of the algorithms.

The result of this work was presented in the Proceedings of14th Conference onMathematical Methods of Pattern Recognition. This is joint work with O.S. Seredin and I.A. Krestinin.

Security of Message Authentication Codes in the Presence of Key-Dependent Messages

Madeline Gonzalez
Cybernetica AS, Estonia

In recent years, significant progress has been made in understanding the security of encryption and signature schemes in the presence of key-dependent plaintexts. Here, we motivate the security of a setting where an adversary can access a message authentication code (MAC) on a key-dependent message and propose a way to formalize the security of MACs in the presence of key-dependent messages (KD-EUF). Like signature schemes, MACs have a verification algorithm, and hence the users must be stateful. We then present a stateful scheme (MAC-ver) that offers KD-EUF security; furthermore, the MAC-ver construction has the advantage that the size of the users' state does not depend on the number of messages authenticated.

Pattern Matching in Sliding Windows

Alexander Kharitonov
Moscow State University, Fac. of Mechanics and Mathematics,, Russia

We consider the problem of maintaining a substring index over a sliding window of a large string.

The applicability of classic data structures for strings, such as tries, suffix trees and suffix automata, to this problem will be reviewed, including known complexity results about suffix trees and suffix automata. With respect to the sliding window problem, there is a complexity gap between suffix trees and suffix automata by a factor of window width.

Our main result concerns maintainting a compact suffix automaton over a sliding window. A compact suffix automaton can be viewed as a certain minimization of a suffix tree (in automata-theoretic sense) or as a result of edge compaction of a suffix automaton. We will show that the compact suffix automaton inherits its complexity characteristics with respect to the sliding window problem from the suffix automaton and not from the suffix tree, which was first proven in 2008 by Dvorak and Senft.

We will present an algorithm for maintaining the compact suffix automaton over a sliding window which has an average-case performance of O(n log k) on a random input string, where n is the string length and k is the window width.

Thus, if we consider average-case performance on random strings, the complexity gap between the suffix tree and the compact suffix automaton can be reduced to a logarithmic factor.

Interesting open questions to be presented are whether it is possible to update the data structure in some lazy manner, sacrificing O(1) query time or O(k) storage space to reduce the construction time to o(n log k).

Response Space Exploration during Automatic Selection of DoS Countermeasures

Gabriel Klein
Fraunhofer Institute for Communication, Information Processing and Ergonomics, Germany

Due to the ever increasing number of attacks against computer systems especially denial-of-service attacks it is advisable to implement systems that automatically select adequate response measures without human intervention in order to apply first responses before the administrator arrives or to provide a reliable decision support mechanism. GrADAR (Graph-based Automated DoS Attack Response) is a methodology for assessing the effects of attack countermeasures on the availability of resources in a networked scenario by evaluating their effects in a model that is updated during run-time. In GrADAR, resources and their availability are modelled as labelled nodes in a directed graph. The graph's edges signify availability dependency relationships between the resources. Real-world response measures are represented in the graph space by modifying the graph, i.e. adding and/or removing vertices or edges or changing availability values of resources. Thereafter, the relationships between the resources are used to quantify the effects of these changes on the availability of dependent resources. Responses are evaluated with respect to multiple metrics such as, e.g. expected success or application costs. The most appropriate response is then applied to the actual network.

This has been shown to work well for known and explicitly specified countermeasures. However, it might be possible that previously unknown response measures have a better overall effect on services' availability than those in the set of known responses. It is therefore necessary to perform response space exploration to find new responses. In order to find better response actions than the ones which are already known, we propose to decompose the graph equivalent of a response measure into atomic parts, each consisting of e.g. a single change of availability or added dependency relationship. By intelligently "concatenating" these atomic response steps it is possible to create novel, potentially more complex responses. Since the effect on resource availability of such a concatenated response is practically arbitrary, it is necessary to solve an optimisation problem with respect to the metrics mentioned above. One possibility how this can be done is by linear optimisation. However, in the case of attack response it is possible that there are multiple equally good intermediate solutions which should all be considered further. Thus, it is advisable to use optimisation techniques that are able to cope with a population of optimal candidates to avoid restriction to local minima. One possibility for this is the use of genetic programming. Although this might incur loss of real-time response selection in the current GrADAR iteration, the following iteration could benefit from additional response measures to choose from. Another option could be an offline usage scenario in which all possible combinations of availability values are taken into account.

Lambek Grammars with One Division and One Primitive Type

Stepan Kuznetsov
Moscow State University, Fac. of Mechanics and Mathematics, Russia

The following theorem is proved: a formal language (possibly, with the empty word) is context-free if and only if it is generated by some L*(;p)-grammar, where L*(;p) is the Lambek calculus with one division and one primitive type allowing empty premises. To prove that any context-free language is generated by some L*(;p)-grammar (the other implication follows from Pentus' theorem), we use a modification of Gaifman's theorem that allows the empty word to be in the language and then use a substitution of types that reduces derivability in L*() to derivability in L*(;p).

Almost the same idea works for L(;p) (the variant of L*(;p) which doesn't allow empty premises), therefore a formal language without the empty word is context-free if and only if it is an L(;p)-language.

The key lemma of this work was published in Moscow State University Mathematics Bulletin Vol. 64, No. 2 (April 2009). The L(;p) variant of the theorem was presented at the Structures and Deduction 2009 workshop at ESSLLI 2009, Bordeaux, France.

On Graph Rewriting, Reduction and Evaluation*

Ian Zerny
Aarhus University, Dept. of Computer Science, Denmark

We inter-derive two prototypical styles of graph reduction: reduction machines la Turner and graph rewriting systems la Barendregt et al. To this end, we adapt Danvy et al.s mechanical program derivations from the world of terms to the world of graphs. We also outline how to inter-derive a third style of graph reduction: a graph evaluator.

* Ian Zerny. On Graph Rewriting, Reduction, and Evaluation. Tenth Symposium on Trends in Functional Programming (TFP 2009). ed. Zoltn Horvth, Viktria Zsk, Peter Achten, and Pieter Koopman. May 2009, pp. 164178.

Valid CSS! Valid XHTML 1.0 Strict Last changed November 26, 2014 19:55 EET by local organizers, ewscs10(at)cs.ioc.ee
EWSCS'10 page: http://cs.ioc.ee/ewscs/2010/