קולוקוויום וסמינרים

Insertion sequence elements (ISs) are short transposable DNA sequences that play a major role in genomic rearrangements in bacteria. Despite their importance and pervasiveness, IS-associated genomic architectures - defined by the spacing, order, and relative orientation of ISs - have not been systematically characterized. Here, we present a computational pipeline for identifying IS-associated architectures, from both assembled genomes and long-read sequencing data at single-molecule resolution. Applying this approach to large-scale microbial genomic datasets, we detected both known amplification structures and more complex architectures, uncovered a previously uncharacterized inverted-flank structure, and observed distributions of structural configurations across IS families and bacterial taxa within the analyzed dataset, suggesting associations between some structures and IS families.

Differential Cryptanalysis is among the most popular types of attacks used to analyze and find vulnerabilities in modern block ciphers. To conduct a differential attack, one must first find a high-probability differential of the block cipher.

Existing search methods involve either intimate knowledge of the specific cipher that is being attacked, or use of search algorithms whose runtime rises exponentially with the number of rounds over which the search is conducted.

We present a quantum-based search method for high probability iterative differentials whose runtime scales linearly in the number of rounds over which the search is conducted and is completely agnostic of the implementation details of the cipher. 

Communication protocols define how systems exchange information and coordinate actions. In security contexts, understanding these protocols is crucial for tasks such as finding vulnerabilities and analyzing malware. In practice, protocol specifications are often missing, outdated, or incomplete, forcing analysts to reverse engineer protocol behavior. Manual protocol reverse engineering is slow and requires significant expertise, while current automatic approaches are ill-equipped to deal with real protocols, due to state explosion, long execution times, or limited code coverage.

In this seminar, we present PALI, an automated system for learning protocols directly from target systems. PALI employs LLM-driven hybrid analysis to create and expand protocol state machines. It then validates the state machines by combining path-level testing with a minimal consistent DFA inference algorithm, based on carefully selected positive and negative examples. This process yields a minimal and reliable state machine consistent with the target system. We evaluated PALI on a wide variety of real and novel protocols, used by benign systems (such as HTTP and SMTP) and malicious ones (the GH0ST malware), achieving accurate state machines while significantly reducing manual analysis effort.

Dominating Set is a fundamental problem in graph theory: given a graph, find a minimum-weight subset of vertices such that every vertex is either selected or shares an edge with a selected vertex.

In online settings where vertices arrive sequentially, comparing algorithms against an offline optimum with full knowledge of the input leads to extremely strong lower bounds, where even a simple star graph shows that any online algorithm must have competitive ratio Ω(n), with n being the number of vertices, matching the trivial strategy of selecting all vertices.

We study the incremental dominating set problem, where the optimal algorithm is constrained to the same choices available to online algorithms. This introduces a benchmark that enables a meaningful comparison between algorithms.

We present the first results for vertex-weighted graphs and randomized algorithms in this model. For incremental dominating set, we give an O(Δ)-competitive deterministic algorithm and an O(log²Δ)-competitive randomized algorithm, where Δ is the maximum degree in the graph.

We extend these results to the Connected Dominating Set problem, which requires the dominating set to be connected. When the neighborhood of each arriving vertex is known in advance, we can improve the competitive ratio of deterministic algorithms to be polylogarithmic.

Finally, we establish matching lower bounds, showing that all our results are optimal up to constant factors.