Anna Mpanti

Andrea D'Ascenzo, Giuseppe F. Italiano, Sotiris Kanellopoulos et al.

Computing paths in graph structures is a fundamental operation in a wide range of applications, from transportation networks to data analysis. The beer path problem, which captures the option of visiting points of interest, such as gas stations or convenience stops, prior to reaching the final destination, has been recently introduced and extensively studied in static graphs. However, existing approaches do not account for temporal information, which is often crucial in real-world scenarios. For instance, transit services may follow fixed schedules, and shops may only be accessible during certain hours. In this work, we introduce the notion of beer paths in temporal graphs, where edges are time-dependent and certain vertices (beer vertices) are active only at specific time instances. We formally define the problems of computing earliest-arrival, latest-departure, fastest, and shortest temporal beer paths and propose efficient algorithms for these problems under both edge stream and adjacency list representations. The time complexity of each of our algorithms is aligned with that of corresponding temporal pathfinding algorithms, thus preserving efficiency. Additionally, we present preprocessing techniques that enable efficient query answering under dynamic conditions, for example new openings or closings of shops. We achieve this through appropriate precomputation of selected paths or by transforming a temporal graph into an equivalent static graph.

Anna Mpanti, Stavros D. Nikolopoulos, Leonidas Palios

In the domain of software watermarking, we have proposed several graph theoretic watermarking codec systems for encoding watermark numbers $w$ as reducible permutation flow-graphs $F[π^*]$ through the use of self-inverting permutations $π^*$. Following up on our proposed methods, we theoretically study the oldest one, which we call W-RPG, in order to investigate and prove its resilience to edge-modification attacks on the flow-graphs $F[π^*]$. In particular, we characterize the integer $w\equivπ^*$ as strong or weak watermark through the structure of self-inverting permutations $π^*$ which encodes it. To this end, for any integer watermark $w \in R_n=[2^{n-1}, 2^n-1]$, where $n$ is the length of the binary representation $b(w)$ of $w$, we compute the minimum number of 01-modifications needed to be applied on $b(w)$ so that the resulting $b(w')$ represents the valid watermark number $w'$; note that a number $w'$ is called valid (or, true-incorrect watermark number) if $w'$ can be produced by the W-RPG codec system and, thus, it incorporates all the structural properties of $π^* \equiv w$.

Anna Mpanti, Stavros D. Nikolopoulos, Iosif Polenakis

In this work we propose a graph-based model that, utilizing relations between groups of System-calls, distinguishes malicious from benign software samples and classifies the detected malicious samples to one of a set of known malware families. More precisely, given a System-call Dependency Graph (ScDG) that depicts the malware's behavior, we first transform it to a more abstract representation, utilizing the indexing of System-calls to a set of groups of similar functionality, constructing thus an abstract and mutation-tolerant graph that we call Group Relation Graph (GrG); then, we construct another graph representation, which we call Coverage Graph (CvG), that depicts the dominating relations between the nodes of a GrG graph. Based on the research so far in the field, we pointed out that behavior-based graph representations had not leveraged the aspect of the temporal evolution of the graph. Hence, the novelty of our work is that, preserving the initial representations of GrG and CvG graphs, we focus on augmenting the potentials of theses graphs by adding further features that enhance its abilities on detecting and further classifying to a known malware family an unknown malware sample. To that end, we construct periodical instances of the graph that represent its temporal evolution concerning its structural modifications, creating another graph representation that we call Temporal Graphs. In this paper, we present the theoretical background behind our approach, discuss the current technological status on malware detection and classification and demonstrate the overall architecture of our proposed detection and classification model alongside with its underlying main principles and its structural key-components.

Anna Mpanti, Stavros D. Nikolopoulos

Software watermarking has received considerable attention and was adopted by the software development community as a technique to prevent or discourage software piracy and copyright infringement. A wide range of software watermarking techniques has been proposed among which the graph-based methods that encode watermarks as graph structures. Following up on our recently proposed methods for encoding watermark numbers $w$ as reducible permutation flow-graphs $F[π^*]$ through the use of self-inverting permutations $π^*$, in this paper, we extend the types of flow-graphs available for software watermarking by proposing two different reducible permutation flow-graphs $F_1[π^*]$ and $F_2[π^*]$ incorporating important properties which are derived from the bitonic subsequences composing the self-inverting permutation $π^*$. We show that a self-inverting permutation $π^*$ can be efficiently encoded into either $F_1[π^*]$ or $F_2[π^*]$ and also efficiently decoded from theses graph structures. The proposed flow-graphs $F_1[π^*]$ and $F_2[π^*]$ enrich the repository of graphs which can encode the same watermark number $w$ and, thus, enable us to embed multiple copies of the same watermark $w$ into an application program $P$. Moreover, the enrichment of that repository with new flow-graphs increases our ability to select a graph structure more similar to the structure of a given application program $P$ thereby enhancing the resilience of our codec system to attacks.