Publikace

Článek

10.1007/s11416-024-00519-z

Katedra informační bezpečnosti

Machine learning has proven to be a valuable tool for automated malware detection, but machine learning systems have also been shown to be subject to adversarial attacks. This paper summarizes and compares related work on generating adversarial malware samples, specifically malicious Windows Portable Executable files. In contrast with previous research, we not only compare generators of adversarial malware examples theoretically, but we also provide an experimental comparison and evaluation for practical usability. We use gradient-based, evolutionary-based, and reinforcement-based approaches to create adversarial samples, which we test against selected antivirus products. The results show that applying optimized modifications to previously detected malware can lead to incorrect classification of the file as benign. Moreover, generated malicious samples can be effectively employed against detection models other than those used to produce them, and combinations of methods can construct new instances that avoid detection. Based on our findings, the Gym-malware generator, which uses reinforcement learning, has the greatest practical potential. This generator has the fastest average sample production time of 5.73 s and the highest average evasion rate of 44.11%. Using the Gym-malware generator in combination with itself further improved the evasion rate to 58.35%. However, other tested methods scored significantly lower in our experiments than reported in the original publications, highlighting the importance of a standardized evaluation environment.

Článek

10.1103/PhysRevC.109.014616

Katedra počítačových systémů

We combine the ab initio symmetry-adapted no-core shell model (SA-NCSM) with the single-particle Green's function approach to construct optical potentials rooted in first principles. Specifically, we show that total cross sections and phase shifts for neutron elastic scattering from a 4He target with projectile energies between 0.5 and 10 MeV closely reproduce the experiment. In addition, we discuss an important new development that resolves a long-standing issue with spurious center-of-mass motion in the Green's function formalism for many-body approaches. The new development opens a path for first-principle predictions of cross sections for elastic scattering of single-nucleon projectiles, nucleon capture, and deuteron breakup reactions, feasible for a broad range of open-shell spherical and deformed nuclei in the SA-NCSM approach.

Stať ve sborníku

10.5220/0012385600003636

Katedra aplikované matematiky

This paper addresses exact approaches to multi-agent collective construction problem which tasks a group of cooperative agents to build a given structure in a blocksworld under the gravity constraint. We propose a generalization of the existing exact model based on mixed integer linear programming by accommodating varying agent action durations. We refer to the model as a fraction-time model. The introduction of action durations enables one to create a more realistic model for various domains. It provides a significant reduction of plan execution duration at the cost of increased computational time, which rises steeply the closer the model gets to the exact real-world action duration. We also propose a makespan estimation function for the fraction-time model. This can be used to estimate the construction time reduction size for cost-benefit analysis. The fraction-time model and the makespan estimation function have been evaluated in a series of experiments using a set of benchmark st ructures. The results show a significant reduction of plan execution duration for non-constant duration actions due to decreasing synchronization overhead at the end of each action. According to the results, the makespan estimation function provides a reasonably accurate estimate of the makespan.

Článek

10.1016/j.dam.2023.11.021

Katedra teoretické informatiky

The average-case complexity of a branch-and-bound algorithm for MIN DOMINATING SET problem in random graphs in the G(n, p) model is studied. We identify phase transitions between subexponential and exponential average-case complexities, depending on the growth of the probability p with respect to the number n of nodes. (c) 2023 Elsevier B.V. All rights reserved.

Článek

10.1007/s11416-024-00513-5

Katedra informační bezpečnosti

A large amount of new malware is constantly being generated, which must not only be distinguished from benign samples, but also classified into malware families. For this purpose, investigating how existing malware families are developed and examining emerging families need to be explored. This paper focuses on the online processing of incoming malicious samples to assign them to existing families or, in the case of samples from new families, to cluster them. We experimented with seven prevalent malware families from the EMBER dataset, four in the training set and three additional new families in the test set. The features were extracted by static analysis of portable executable files for the Windows operating system. Based on the classification score of the multilayer perceptron, we determined which samples would be classified and which would be clustered into new malware families. We classified 97.21% of streaming data with a balanced accuracy of 95.33%. Then, we clustered the remaining data using a self-organizing map, achieving a purity from 47.61% for four clusters to 77.68% for ten clusters. These results indicate that our approach has the potential to be applied to the classification and clustering of zero-day malware into malware families.

Článek

10.1007/s11416-024-00516-2

Katedra informační bezpečnosti

Because of its world-class results, machine learning (ML) is becoming increasingly popular as a go-to solution for many tasks. As a result, antivirus developers are incorporating ML models into their toolchains. While these models improve malware detection capabilities, they also carry the disadvantage of being susceptible to adversarial attacks. Although this vulnerability has been demonstrated for many models in white-box settings, a black-box scenario is more applicable in practice for the domain of malware detection. We present a method of creating adversarial malware examples using reinforcement learning algorithms. The reinforcement learning agents utilize a set of functionality-preserving modifications, thus creating valid adversarial examples. Using the proximal policy optimization (PPO) algorithm, we achieved an evasion rate of 53.84% against the gradient-boosted decision tree (GBDT) detector. The PPO agent previously trained against the GBDT classifier scored an evasion rate of 11.41% against the neural network-based classifier MalConv and an average evasion rate of 2.31% against top antivirus programs. Furthermore, we discovered that random application of our functionality-preserving portable executable modifications successfully evades leading antivirus engines, with an average evasion rate of 11.65%. These findings indicate that ML-based models used in malware detection systems are sensitive to adversarial attacks and that better safeguards need to be taken to protect these systems.

Stať ve sborníku

Katedra teoretické informatiky

In the Multiagent Path Finding (MAPF for short) problem, we focus on efficiently finding non-colliding paths for a set of k agents on a given graph G, where each agent seeks a path from its source vertex to a target. An important measure of the quality of the solution is the length of the proposed schedule l, that is, the length of a longest path (including the waiting time). In this work, we propose a systematic study under the parameterized complexity framework. The hardness results we provide align with many heuristics used for this problem, whose running time could potentially be improved based on our Fixed-Parameter Tractability (FPT) results. We show that MAPF is W[1]-hard with respect to k (even if k is combined with the maximum degree of the input graph). The problem remains NP-hard in planar graphs even if the maximum degree and the makespan l are fixed constants. On the positive side, we show an FPT algorithm for k+l. As we continue, the structure of G comes into play. We give an FPT algorithm for parameter k plus the diameter of the graph G. The MAPF problem is W[1]-hard for cliquewidth of G plus l while it is FPT for treewidth of G plus l.

Článek

10.1016/j.comgeo.2023.102055

Katedra aplikované matematiky

A framework, which is a (possibly infinite) graph with a realization of its vertices in the plane, is called flexible if it can be continuously deformed while preserving the edge lengths. We focus on flexibility of frameworks in which 4-cycles form parallelograms. For the class of frameworks considered in this paper (allowing triangles), we prove that the following are equivalent: flexibility, infinitesimal flexibility, the existence of at least two classes of an equivalence relation based on 3- and 4-cycles and being a non -trivial subgraph of the Cartesian product of graphs. We study the algorithmic aspects and the rotationally symmetric version of the problem. The results are illustrated on frameworks obtained from tessellations by regular polygons.

Článek

10.1016/j.comnet.2023.110147

Katedra číslicového návrhu

Network traffic monitoring based on IP Flows is a standard monitoring approach that can be deployed to various network infrastructures, even the large ISP networks connecting millions of people. Since flow records traditionally contain only limited information (addresses, transport ports, and amount of exchanged data), they are also commonly extended by additional features that enable network traffic analysis with high accuracy. These flow extensions are, however, often too large or hard to compute, which then allows only offline analysis or limits their deployment only to smaller-sized networks. This paper proposes a novel extended IP flow called NetTiSA (Network Time Series Analysed) flow, based on analysing the time series of packet sizes. By thoroughly testing 25 different network traffic classification tasks, we show the broad applicability and high usability of NetTiSA flow. For practical deployment, we also consider the sizes of flows extended by NetTiSA features and evaluate the performance impacts of their computation in the flow exporter. The novel features proved to be computationally inexpensive and showed excellent discriminatory performance. The trained machine learning classifiers with proposed features mostly outperformed the state-of-the-art methods. NetTiSA finally bridges the gap and brings universal, small-sized, and computationally inexpensive features for traffic classification that can be scaled up to extensive monitoring infrastructures, bringing the machine learning traffic classification even to 100 Gbps backbone lines.

Článek

10.1080/17445760.2023.2291349

Katedra počítačových systémů

Each generation of CPU provides more resources and new features. These increase the ability to perform algorithms faster and with a higher degree of parallelism. The article discusses methods used to optimise CRC generation algorithms for long data blocks with consideration of the capabilities of contemporary systems. We analysed known software CRC algorithms and combined all known principles into a solution scalable in multiple CPU cores on single and multi-socket systems. Various algorithms were evaluated on contemporary multicore systems with 1 × 4, 1 × 64, 2 × 12, and 4 × 26 cores. The results show how the performance is affected by the architecture of the memory subsystem. Compared to the original sequential Sarwate algorithm, our algorithms are 48.0, 51.1, 38.0, and 28.8 times faster.

Článek

10.1177/10943420231183697

Katedra počítačových systémů

High performance computing (HPC) applications that work with redundant sequences of data can benefit from their deduplication. We study this problem on the symmetry-adapted no-core shell model (SA-NCSM), where redundant sequences of different kinds naturally emerge in the data of the basis of the Hilbert space physically relevant to a modeled nucleus. For a fast solution of this problem on multicore architectures, we propose and present three multithreaded algorithms, which employ either concurrent hash tables or parallel sorting methods. Furthermore, we present evaluation and comparison of these algorithms based on experiments performed with real-world SA-NCSM calculations. The results indicate that the fastest option is to use a concurrent hash table, provided that it supports sequences of data as a type of table keys. If such a hash table is not available, the algorithm based on parallel sorting is a viable alternative.

Článek

10.1016/j.exmath.2024.125571

Katedra aplikované matematiky

We consider expansions of vectors by a general class of multidimensional continued fraction algorithms. If the expansion is eventually periodic, then we describe the possible structure of a matrix corresponding to the repetend and use it to prove that a number of vectors have an eventually periodic expansion in the Algebraic Jacobi–Perron algorithm. Further, we give criteria for vectors to have purely periodic expansions; in particular, the vector cannot be totally positive.

Článek

10.1016/j.eswa.2023.121164

Katedra aplikované matematiky

Relevance-based ranking is a popular ingredient in recommenders, but it frequently struggles to meet fairness criteria because social and cultural norms may favor some item groups over others. For instance, some items might receive lower ratings due to some sort of bias (e.g. gender bias). A fair ranking should balance the exposure of items from advantaged and disadvantaged groups. To this end, we propose a novel post-processing framework to produce fair, exposure-aware recommendations. Our approach is based on an integer linear programming model maximizing the expected utility while satisfying a minimum exposure constraint. The model has fewer variables than previous work and thus can be deployed to larger datasets and allows the organization to define a minimum level of exposure for groups of items. We conduct an extensive empirical evaluation indicating that our new framework can increase the exposure of items from disadvantaged groups at a small cost of recommendation accuracy

Článek

10.1007/s42979-023-02493-7

Katedra informační bezpečnosti

Most of the currently used cryptosystems are not secure in the presence of cryptographically relevant quantum computers. As the research in quantum technologies proceeds, a need for quantum-safe cryptography is imminent. NTRU is a post-quantum public-key cryptosystem based on lattices and was a finalist in the 3rd round of the post-quantum standardization process organized by the National Institute of Standards and Technology (NIST). This paper aims to study the implementation security of the cryptosystem with respect to an attacker with access to power leakage. Such a threat model is relevant especially, but not only, for embedded devices. We studied a countermeasure implementation of the NTRU decryption algorithm from An et al. (Appl Sci https://doi.org/10.3390/app8112014 , 2018) that claimed its security against power attacks. This paper revisits an attack presented in as reported by Rabas (In: Proceedings of the9th International Conference on Information Systems Security and Privacy,ICISSP 2023, Lisbon, 2023) that shows it is in fact vulnerable even in the case of just a single trace available to the enemy for extracting the key. We then describe a new profiling template attack on the implementation and show experimental results of the attack using the same datasets, resulting in a comparison of these two methods and further confirmation of the vulnerability of the algorithm even to generic profiling attacks. Several possible types of countermeasures are discussed.

Stať ve sborníku

10.1609/aaai.v38i9.28822

Katedra teoretické informatiky

We study the computational complexity of fairly allocating a set of indivisible items under externalities. In this recently-proposed setting, in addition to the utility the agent gets from their bundle, they also receive utility from items allocated to other agents. We focus on the extended definitions of envy-freeness up to one item (EF1) and of envy-freeness up to any item (EFX), and we provide the landscape of their complexity for several different scenarios. We prove that it is NP-complete to decide whether there exists an EFX allocation, even when there are only three agents, or even when there are only six different values for the items. We complement these negative results by showing that when both the number of agents and the number of different values for items are bounded by a parameter the problem becomes fixed-parameter tractable. Furthermore, we prove that two-valued and binary-valued instances are equivalent and that EFX and EF1 allocations coincide for this class of instances. Finally, motivated from real-life scenarios, we focus on a class of structured valuation functions, which we term agent/item-correlated. We prove their equivalence to the "standard" setting without externalities. Therefore, all previous results for EF1 and EFX apply immediately for these valuations.

Stať ve sborníku

10.1137/1.9781611977912.59

Katedra teoretické informatiky

We consider the following general model of a sorting procedure: we fix a hereditary permutation class C, which corresponds to the operations that the procedure is allowed to perform in a single step. The input of sorting is a permutation π of the set [n] = {1, 2,…,n}, i.e., a sequence where each element of [n] appears once. In every step, the sorting procedure picks a permutation σ of length n from C, and rearranges the current permutation of numbers by composing it with σ. The goal is to transform the input π into the sorted sequence 1, 2,…,n in as few steps as possible. Formally, for a hereditary permutation class C and a permutation π of [n], we say that C can sort π in k steps, if the inverse of π can be obtained by composing k (not necessarily distinct) permutations from C. The C-sorting time of π, denoted st(C; π), is the smallest k such that C can sort π in k steps; if no such k exists, we put st(C; π) = +∞. For an integer n, the worst-case C-sorting time, denoted wst(C; n), is the maximum of st(C; π) over all permutations π of [n]. This model of sorting captures not only classical sorting algorithms, like insertion sort or bubble sort, but also sorting by series of devices, like stacks or parallel queues, as well as sorting by block operations commonly considered, e.g., in the context of genome rearrangement. Our goal is to describe the possible asymptotic behavior of the function wst(C; n), and relate it to structural properties of C. As the main result, we show that any hereditary permutation class C falls into one of the following five categories: • wst(C; n) = +∞ for n large enough, • wst(C; n) = Θ(n2), • Ω(√n) ≤ wst(C; n) ≤ O(n), • Ω(log n) ≤ wst(C; n) ≤ O(log2 n), or • wst(C; n) = 1 for all n ≥ 2. In addition, we characterize the permutation classes in each of the five categories.

Článek

10.1016/j.jcta.2024.105904

Katedra aplikované matematiky

Let H be an HD0L-system. We show that there are only finitely many primitive words v with the property that , for all integers k, is an element of the factorial language of H. In particular, this result applies to the set of all factors of a morphic word. We provide a formalized proof in the proof assistant Isabelle/HOL as part of the Combinatorics on Words Formalized project.

Stať ve sborníku

10.1007/978-981-97-2340-9_19

Katedra teoretické informatiky

Arguably, one of the most central tasks in the area of social network analysis is to identify important members and communities of a given network. The importance of an agent is traditionally measured using some well-defined notion of centrality. In this work, we focus on betweenness centrality, which is based on the number of shortest paths that an agent intersects. This measure can be naturally generalized from a single agent to a group of agents. Specifically, we study the computation complexity of the k-Maximum Betweenness Centrality problem, which consists in finding a group of size $k$ whose betweenness centrality exceeds a given threshold. Since this problem is NP-complete in general, we use the framework of parameterized complexity to reveal at least some tractable fragments. From this perspective, we show that the problem is W[1]-hard and in XP when parameterized by the group size $k$. As the threshold value is not a useful parameter in this context, we focus on the structural restrictions of the underlying social network. In this direction, we show that the problem admits FPT algorithms with respect to the vertex cover number, the distance to clique, or the twin-cover number and the group size combined.

Stať ve sborníku

Katedra aplikované matematiky

Jde o vzpomínku na známou matematickou soutěž v Československu a nyní v České republice. Soutěž u nás existuje již 70 let, její předchůdkyní byla časopisecká soutěž v Rozhledech matematicko- přírodovědných.

Článek

10.1016/j.forsciint.2023.111765

Katedra teoretické informatiky
Katedra počítačových systémů

This work presents an automated data-mining model for age-at-death estimation based on 3D scans of the auricular surface of the pelvic bone. The study is based on a multi-population sample of 688 individuals (males and females) originating from one Asian and five European identified osteological collections. Our method requires no expert knowledge and achieves similar accuracy compared to traditional subjective methods. Apart from data acquisition, the whole procedure of pre-processing, feature extraction and age estimation is fully automated and implemented as a computer program. This program is a part of a freely available web-based software tool called CoxAGE3D. This software tool is available at https://cox-age3d.fit.cvut.cz/ Our age-at-death estimation method is suitable for use on individuals with known/un-known population affinity and provides moderate correlation between the estimated age and actual age (Pearson's correlation coefficient is 0.56), and a mean absolute error of 12.4 years.& COPY; 2023 Elsevier B.V. All rights reserved.