Aktuální informace FIT ke koronaviru najdete zde.

Automorphisms of the cube n^d

Autoři
Valla, T.; Dvořák, P.
Rok
2021
Publikováno
Discrete Mathematics. 2021, 2021(344(3)), ISSN 0012-365X.
Typ
Článek
Anotace
Consider a hypergraph n^d where the vertices are points of the d-dimensional cube [n]^d and the edges are all sets of n points such that they are in one line. We study the structure of the group of automorphisms of n^d, i.e., permutations of points of [n]^d preserving the edges. In this paper we provide a complete characterization. Moreover, we consider the Colored Cube Isomorphism problem of deciding whether for two colorings of the vertices of n^d there exists an automorphism of n^d preserving the colors. We show that this problem is GI-complete.

Backward Pattern Matching on Elastic Degenerate Strings

Autoři
Procházka, P.; Holub, J.; Cvacho, O.; Krčál, L.
Rok
2021
Publikováno
Proceedings of 14th International Joint Conference on Biomedical Engineering Systems and Technologies (BIOSTEC 2021). Lisboa: SCITEPRESS – Science and Technology Publications, Lda, 2021. p. 50-59. vol. 3. ISSN 2184-4305. ISBN 978-989-758-490-9.
Typ
Stať ve sborníku
Anotace
Recently, the concept of Elastic Degenerate Strings (EDS) was introduced as a way of representing a sequenced population of the same species. Several on-line Elastic Degenerate String Matching (EDSM) algorithms were presented so far. Some of them provide practical implementation. We propose a new on-line EDSM algorithm BNDM-EDS. Our algorithm combines two traditional algorithms BNDM and the Shift-And that were adapted to the specifics needed by Elastic Degenerate Strings. BNDM-EDS is running in O (Nmd m w e) worst-case time. This implies O (Nm) time for small patterns, where m is the length of the searched pattern, N is the size of EDS, and w is the size of the computer word. The algorithm uses O (N + n) space, where n is the length of EDS. BNDM-EDS requires a simple preprocessing step with time and space O (m). Experimental results on real genomic data show superiority of BNDM-EDS over state-of-the-art algorithms.

Binary intersection formalized

Autoři
Starosta, Š.; Holub, Š.
Rok
2021
Publikováno
Theoretical Computer Science. 2021, 866 14-24. ISSN 0304-3975.
Typ
Článek
Anotace
We provide a reformulation and a formalization of the classical result by Juhani Karhumäki characterizing intersections of two languages of the form $\{x,y\}^* \cap \{u,v\}^*$. We use the terminology of morphisms which allows to formulate the result in a shorter and more transparent way, and we formalize the result in the proof assistant Isabelle/HOL.

Data Structures to Represent a Set of k-long DNA Sequences

Autoři
Holub, J.; Chikhi, R.; Medvedev, P.
Rok
2021
Publikováno
ACM Computing Surveys. 2021, 54(1), 17:1-17:22. ISSN 0360-0300.
Typ
Článek
Anotace
The analysis of biological sequencing data has been one of the biggest applications of string algorithms. The approaches used in many such applications are based on the analysis of k-mers, which are short fixed-length strings present in a dataset. While these approaches are rather diverse, storing and querying a k-mer set has emerged as a shared underlying component. A set of k-mers has unique features and applications that, over the past 10 years, have resulted in many specialized approaches for its representation. In this survey, we give a unified presentation and comparison of the data structures that have been proposed to store and query a k-mer set. We hope this survey will serve as a resource for researchers in the field as well as make the area more accessible to researchers outside the field.

Detection of HTTPS Brute-Force Attacks with Packet-Level Feature Set

Autoři
Hynek, K.; Čejka, T.; Luxemburk, J.
Rok
2021
Publikováno
11th Annual Computing and Communication Workshop and Conference (CCWC2021). Piscataway (New Jersey): IEEE, 2021. p. 0115-0123. ISBN 978-0-7381-4394-1.
Typ
Stať ve sborníku
Anotace
This paper presents a novel approach to detect brute-force attacks against web services in high-speed networks. The prevalence of brute-force attacks is so high that service providers, such as ISPs or web-hosting providers, cannot depend on their customers' host-based defenses. Moreover, the rising usage of encryption makes it more difficult to detect attacks on the network level. In our research, we created a dataset, which consists of 1.8 million extended IP flows from a backbone network combined with IP flows generated with three popular open-source brute-forcing tools. We identified a distinctive packet-level feature set and trained a machine-learning classifier with a false positive rate of 10^-4 and a true positive rate (the ratio of discovered attacks) of 0.938. The achieved results surpass the state-of-the-art solutions and show that the developed HTTPS brute-force detection algorithm is viable for production deployment.

Detection of HTTPS Brute-Force Attacks with Packet-Level Feature Set

Autoři
Hynek, K.; Čejka, T.; Luxemburk, J.
Rok
2021
Publikováno
11th Annual Computing and Communication Workshop and Conference (CCWC2021). Piscataway (New Jersey): IEEE, 2021. p. 0115-0123. ISBN 978-0-7381-4394-1.
Typ
Stať ve sborníku
Anotace
This paper presents a novel approach to detect brute-force attacks against web services in high-speed networks. The prevalence of brute-force attacks is so high that service providers, such as ISPs or web-hosting providers, cannot depend on their customers' host-based defenses. Moreover, the rising usage of encryption makes it more difficult to detect attacks on the network level. In our research, we created a dataset, which consists of 1.8 million extended IP flows from a backbone network combined with IP flows generated with three popular open-source brute-forcing tools. We identified a distinctive packet-level feature set and trained a machine-learning classifier with a false positive rate of 10^-4 and a true positive rate (the ratio of discovered attacks) of 0.938. The achieved results surpass the state-of-the-art solutions and show that the developed HTTPS brute-force detection algorithm is viable for production deployment.

Efficiency Near the Edge: Increasing the Energy Efficiency of FFTs on GPUs for Real-Time Edge Computing

Autoři
Adámek, K.; Novotný, J.; Thiyagalingam, J.; Armour, W.
Rok
2021
Publikováno
IEEE Access. 2021, 9 18167-18182. ISSN 2169-3536.
Typ
Článek
Anotace
The Square Kilometer Array (SKA) is an international initiative for developing the world's largest radio telescope with a total collecting area of over a million square meters. The scale of the operation, combined with the remote location of the telescope, requires the use of energy-efficient computational algorithms. This, along with the extreme data rates that will be produced by the SKA and the requirement for a real-time observing capability, necessitates in-situ data processing in an edge style computing solution. More generally, energy efficiency in the modern computing landscape is becoming of paramount concern. Whether it be the power budget that can limit some of the world's largest supercomputers, or the limited power available to the smallest Internet-of-Things devices. In this article, we study the impact of hardware frequency scaling on the energy consumption and execution time of the Fast Fourier Transform (FFT) on NVIDIA GPUs using the cuFFT library. The FFT is used in many areas of science and it is one of the key algorithms used in radio astronomy data processing pipelines. Through the use of frequency scaling, we show that we can lower the power consumption of the NVIDIA A100 GPU when computing the FFT by up to 47% compared to the boost clock frequency, with less than a 10% increase in the execution time. Furthermore, using one common core clock frequency for all tested FFT lengths, we show on average a 43% reduction in power consumption compared to the boost core clock frequency with an increase in the execution time still below 10%. We demonstrate how these results can be used to lower the power consumption of existing data processing pipelines. These savings, when considered over years of operation, can yield significant financial savings, but can also lead to a significant reduction of greenhouse gas emissions.

Emerging Technologies: Challenges and Opportunities for Logic Synthesis

Autoři
Fišer, P.; Bosio, A.; Cantan, M.; Marchand, C.; O'Connor, I.; Poittevin, A.; Traiola, M.
Rok
2021
Publikováno
Proceedings of 24th International Symposium on Design and Diagnostics of Electronic Circuits and Systems. Piscataway (New Jersey): IEEE, 2021. p. 93-98. ISBN 978-1-6654-3595-6.
Typ
Stať ve sborníku
Anotace
In computer engineering, logic synthesis is a process by which an abstract specification of desired circuit behavior is turned into a design implementation in terms of logic gates. Historically, logic synthesis was tightly related to the physical implementation of the logic gates. Nowadays, pushed by the forecasted end of Moore's law, several emerging technologies (e.g., nanodevices, optical computing, quantum computing) are candidates to either replace or co-exist with the \textit{de facto} standard CMOS technology. The main consequence of the rising of those emerging technologies is that the logic synthesis has to face new issues and, at the same time, exploits new opportunities. The goal of this paper is thus to present three emerging technologies (Vertical Nanowire Field Effect Transistors, Ferroelectric Transistors, and Memristors), how to use them to implement logic gates, and the main challenges and issues for the logic synthesis.

Emulating Centralized Control in Multi-Agent Pathfinding Using Decentralized Swarm of Reflex-Based Robots

Autoři
Surynek, P.; Chudý, J.; Popov, N.
Rok
2021
Publikováno
Proceedings of the 2020 IEEE International Conference on Systems, Man, and Cybernetics. Los Alamitos: IEEE Computer Society, 2021. p. 3998-4005. ISBN 978-1-7281-8526-2.
Typ
Stať ve sborníku
Anotace
Multi-agent pathfinding (MAPF) represents a core problem in robotics. In its abstract form, the task is to navigate agents in an undirected graph to individual goal vertices so that conflicts between agents do not occur. Many algorithms for finding feasible or optimal solutions have been devised. We focus on the execution of MAPF solutions with a swarm of simple physical robots. Such execution is important for understanding how abstract plans can be transferred into reality and vital for educational demonstrations. We show how to use a swarm of reflex-based Ozobot Evo robots for MAPF execution.

Formally verified speculation and deoptimization in a JIT compiler

Autoři
Vítek, J.; Barrière, A.; Blazy, S.; Flückiger, O.; Pichardie, D.
Rok
2021
Publikováno
Proceedings of the ACM on Programming Languages (PACMPL). 2021, 5(POPL), 1-26. ISSN 2475-1421.
Typ
Článek
Anotace
Just-in-time compilers for dynamic languages routinely generate code under assumptions that may be invalidated at run-time, this allows for specialization of program code to the common case in order to avoid unnecessary overheads due to uncommon cases. This form of software speculation requires support for deoptimization when some of the assumptions fail to hold. This paper presents a model just-in-time compiler with an intermediate representation that explicits the synchronization points used for deoptimization and the assumptions made by the compiler's speculation. We also present several common compiler optimizations that can leverage speculation to generate improved code. The optimizations are proved correct with the help of a proof assistant. While our work stops short of proving native code generation, we demonstrate how one could use the verified optimization to obtain significant speed ups in an end-to-end setting. © 2021 Owner/Author.

Graph isomorphism restricted by lists

Autoři
Knop, D.; Klavík, P.; Zeman, P.
Rok
2021
Publikováno
Theoretical Computer Science. 2021, 860 51-71. ISSN 0304-3975.
Typ
Článek
Anotace
The complexity of graph isomorphism (GRAPHISO) is a famous problem in computer science. For graphs G and H, it asks whether they are the same up to a relabeling of vertices. In 1981, Lubiw proved that list restricted graph isomorphism (LISTISO ) is NP -complete: for each u∈V(G), we are given a list L(u)⊆V(H) of possible images of u. After 35 years, we revive the study of this problem and consider which results for GRAPHISO can be modified to solve LISTISO. We prove: 1) Under certain conditions, GI -completeness of a class of graphs implies NP -completeness of LISTISO. 2) Several combinatorial algorithms for GRAPHISO can be modified to solve LISTISO: for trees, planar graphs, interval graphs, circle graphs, permutation graphs, and bounded treewidth graphs. 3) LISTISO is NP -complete for cubic colored graphs with sizes of color classes bounded by 8 with all lists of size at most 3.

Improving Classification of Malware Families using Learning a Distance Metric

Rok
2021
Publikováno
Proceedings of the 7th International Conference on Information Systems Security and Privacy. Madeira: SciTePress, 2021. p. 643-652. ISSN 2184-4356. ISBN 978-989-758-491-6.
Typ
Stať ve sborníku
Anotace
The objective of malware family classification is to assign a tested sample to the correct malware family. This paper concerns the application of selected state-of-the-art distance metric learning techniques to malware families classification. The goal of distance metric learning algorithms is to find the most appropriate distance metric parameters concerning some optimization criteria. The distance metric learning algorithms considered in our research learn from metadata, mostly contained in the headers of executable files in the PE file format. Several experiments have been conducted on the dataset with 14,000 samples consisting of six prevalent malware families and benign files. The experimental results showed that the average precision and recall of the k-Nearest Neighbors algorithm using the distance learned on training data were improved significantly comparing when the non-learned distance was used. The k-Nearest Neighbors classifier using the Mahalanobis distance metric learned by the Metric Learning for Kernel Regression method achieved average precision and recall, both of 97.04% compared to Random Forest with a 96.44% of average precision and 96.41% of average recall, which achieved the best classification results among the state-of-the-art ML algorithms considered in our experiments.

Joint direct and transposed sparse matrix-vector multiplication for multithreaded CPUs

Rok
2021
Publikováno
Concurrency and Computation: Practice and Experience. 2021, ISSN 1532-0626.
Typ
Článek
Anotace
Repeatedly performing sparse matrix‐vector multiplication (SpMV) followed by transposed sparse matrix‐vector multiplication (SpMᵀV) with the same matrix is a part of several algorithms, for example, the Lanczos biorthogonalization algorithm and the biconjugate gradient method. Such algorithms can benefit from combining parallel SpMV and SpMᵀV into a single operation we call ‘joint direct and transposed sparse matrix‐vector multiplication’ (SpMMᵀV). In this article, we present a parallel SpMMᵀV algorithm for shared‐memory CPUs. The algorithm uses a sparse matrix format that divides the stored matrix into sparse matrix blocks and compresses the row and column indices of the matrix. This sparse matrix format can be also used for SpMV, SpMᵀV, and similar sparse matrix‐vector operations. We expand upon existing research by suggesting new variants of the parallel SpMMᵀV algorithm and by extending the algorithm to efficiently support symmetric matrices. We compare the performance of the presented parallel SpMMᵀV algorithm with alternative approaches, which use state‐of‐the‐art sparse matrix formats and libraries, using sparse matrices from real‐world applications. The performance results indicate that the median performance of our proposed parallel SpMMᵀV algorithm is up to 45% higher than of the alternative approaches.

Measuring Mancúr Olson: What is the Influence of Culture and Institutions & Policies on Economic Development?

Autoři
Evan, T.; Bolotov, I.
Rok
2021
Publikováno
Prague Economic Papers. 2021, 1-26. ISSN 2336-730X.
Typ
Článek
Anotace
Mancúr Olson Jr. wrote his influential study Big Bills left on the Sidewalk: Why Some Countries are Rich, and Others Poor in 1996. In his paper, Olson claimed that the differences in economic development between countries are caused by just two factors: institutions & policies and culture. We attempt to test his conjecture through econometric modelling by combining and comparing it with a broadly defined orthodox production function in an indirect neoclassical notation (Solow-Minhas-Arrow-Chenery’s SMAC framework). The ‘pseudo-production function’ obtained is econometrically sound and of similar explanatory power to models including economic variables, although we find strong evidence of interdependence between capital-labour share and institutions & policies and culture. We consider the test, performed on panel data from 154 countries over 5-year averages from 1980–2014, to be robust and consistent with Olson’s ideas.

On the Edge-Length Ratio of 2-Trees

Autoři
Blažej, V.; Fiala, J.; Liotta, G.
Rok
2021
Publikováno
Graph Drawing and Network Visualization. Cham: Springer, 2021. p. 85-98. Lecture Notes in Computer Science. vol. 12590. ISSN 0302-9743. ISBN 978-3-030-68765-6.
Typ
Stať ve sborníku
Anotace
We study planar straight-line drawings of graphs that minimize the ratio between the length of the longest and the shortest edge. We answer a question of Lazard et al. [Theor. Comput. Sci. {\bf 770} (2019), 88--94] and, for any given constant $r$, we provide a $2$-tree which does not admit a planar straight-line drawing with a ratio bounded by $r$. When the ratio is restricted to adjacent edges only, we prove that any $2$-tree admits a planar straight-line drawing whose edge-length ratio is at most $4 + \varepsilon$ for any arbitrarily small $\varepsilon > 0$, hence the upper bound on the local edge-length ratio of partial $2$-trees is $4$.

On the Intersections of Non-homotopic Loops

Autoři
Blažej, V.; Opler, M.; Šileikis, M.; Valtr, P.
Rok
2021
Publikováno
Algorithms and Discrete Applied Mathematics. Cham: Springer, 2021. p. 196-205. Lecture Notes in Computer Science. vol. 12601. ISSN 0302-9743. ISBN 978-3-030-67898-2.
Typ
Stať ve sborníku
Anotace
Let $V = \{v_1, \dots, v_n\}$ be a set of $n$ points in the plane and let $x \in V$. An \emph{$x$-loop} is a continuous closed curve not containing any point of $V$, except of passing exactly once through the point $x$. We say that two $x$-loops are \emph{non-homotopic} if they cannot be transformed continuously into each other without passing through a point of $V$. For $n=2$, we give an upper bound $2^{O(k)}$ on the maximum size of a family of pairwise non-homotopic $x$-loops such that every loop has fewer than $k$ self-intersections and any two loops have fewer than $k$ intersections. This result is inspired by a very recent result of Pach, Tardos, and T\'oth who proved the upper bounds $2^{16k^4}$ for the slightly different scenario when $x\not\in V$.

PFP Compressed Suffix Trees

Autoři
Holub, J.; Boucher, C.; Cvacho, O.; Gagie, T.; Manzini, G.; Navarro, G.; Rossi, M.
Rok
2021
Publikováno
Proceedings of the Workshop on Algorithm Engineering and Experiments (ALENEX2021). Philadelphia: SIAM, 2021. p. 60-72. ISBN 978-1-61197-647-2.
Typ
Stať ve sborníku
Anotace
Prefix-free parsing (PFP) was introduced by Boucher et al. (2019) as a preprocessing step to ease the computation of Burrows-Wheeler Transforms (BWTs) of genomic databases. Given a string S, it produces a dictionary D and a parse P of overlapping phrases such that BWT(S) can be computed from D and P in time and workspace bounded in terms of their combined size |PFP(S)|. In practice D and P are significantly smaller than S and computing BWT(S) from them is more efficient than computing it from S directly, at least when S is the concatenation of many genomes. In this paper, we consider PFP(S) as a data structure and show how it can be augmented to sup- port full suffix tree functionality, still built and fitting within O(|PFP(S)|) space. This entails the efficient computation of various primitives to simulate the suffix tree: computing a longest common extension (LCE) of two positions in S; reading any cell of its suffix array (SA), of its inverse (ISA), of its BWT, and of its longest common prefix array (LCP); and computing minima over ranges and next/previous smaller value queries over the LCP. Our experimental results show that the PFP suffix tree can be efficiently constructed for very large repetitive datasets and that its operations perform competitively with other compressed suffix trees that can only handle much smaller datasets.

Representation of PE Files using LSTM Networks

Autoři
Jureček, M.; Kozák, M.
Rok
2021
Publikováno
Proceedings of the 7th International Conference on Information Systems Security and Privacy. Madeira: SciTePress, 2021. p. 516-525. ISSN 2184-4356. ISBN 978-989-758-491-6.
Typ
Stať ve sborníku
Anotace
An ever-growing number of malicious attacks on IT infrastructures calls for new and efficient methods of protection. In this paper, we focus on malware detection using the Long Short-Term Memory (LSTM) as a preprocessing tool to increase the classification accuracy of machine learning algorithms. To represent the malicious and benign programs, we used features extracted from files in the PE file format. We created a large dataset on which we performed common feature preparation and feature selection techniques. With the help of various LSTM and Bidirectional LSTM (BLSTM) network architectures, we further transformed the collected features and trained other supervised ML algorithms on both transformed and vanilla datasets. Transformation by deep (4 hidden layers) versions of LSTM and BLSTM networks performed well and decreased the error rate of several state-of-the-art machine learning algorithms significantly. For each machine learning algorithm considered in our experiments, the LSTM-based transformation of the feature space results in decreasing the corresponding error rate by more than 58.60 %, in comparison when the feature space was not transformed using LSTM network.

Segmentation of color images using mean curvature flow and parametric curves

Autoři
Pauš, P.; Yazaki, S.
Rok
2021
Publikováno
Discrete and Continuous Dynamical Systems. Series S. 2021, 14(3), 1123-1132. ISSN 1937-1632.
Typ
Článek
Anotace
Automatic detection of objects in photos and images is beneficial in various scientific and industrial fields. This contribution suggests an algorithm for segmentation of color images by the means of the parametric mean curvature flow equation and CIE94 color distance function. The parametric approach is enriched by the enhanced algorithm for topological changes where the intersection of curves is computed instead of unreliable curve distance. The result is a set of parametric curves enclosing the object. The algorithm is presented on a test image and also on real photos.

Side-channel attack on Rainbow post-quantum signature

Autoři
Novotný, M.; Pokorný, D.; Socha, P.
Rok
2021
Publikováno
Proceedings of the 2021 Design, Automation & Test in Europe (DATE). New Jersey: IEEE, 2021. p. 565-568. ISSN 1558-1101. ISBN 978-3-9819263-5-4.
Typ
Stať ve sborníku
Anotace
Rainbow, a layered multivariate quadratic digital signature, is a candidate for standardization in a competition-like process organized by NIST. In this paper, we present a CPA side-channel attack on the submitted 32-bit reference implementation. We evaluate the attack on an STM32F3 ARM microcontroller,successfully revealing the full private key. Furthermore, we propose a simple masking scheme with minimum overhead.

Filtr

Za obsah stránky zodpovídá: doc. Ing. Štěpán Starosta, Ph.D.