Stavros D. Nikolopoulos

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.

Stavros D. Nikolopoulos, Iosif Polenakis

We study the propagation of a malicious software in a network of mobile devices, which are moving in a specific city area, and establish time bounds for the activation of a counter-measure, i.e., an antivirus or a cleaner in order to prevent pandemic. More precisely, given an initial infected population (mobile devices), we establish upper bounds on the time needed for a counter-measure to take effect after infection (response-time), in order to prevent the rest susceptible devices to get infected. Thus, within a period of time, we guarantee that not all the susceptible devices in the city get infected and the infected ones get sanitized. In our work, we first propose a malware propagation model along with a device mobility model and then, utilizing these models, we develop a simulator that we use to study the spread of malware in such networks. Finally, we provide experimental results for the pandemic prevention taken by our simulator for various response-time intervals.

Maria Chroni, Stavros D. Nikolopoulos

This work provides to web users copyright protection of their Portable Document Format (PDF) documents by proposing efficient and easily implementable techniques for PDF watermarking; our techniques are based on the ideas of our recently proposed watermarking techniques for software, image, and audio, expanding thus the digital objects that can be efficiently watermarked through the use of self-inverting permutations. In particular, we present various representations of a self-inverting permutation $π^*$ namely 1D-representation, 2D-representation, and RPG-representation, and show that theses representations can be efficiently applied to PDF watermarking. Indeed, we first present an audio-based technique for marking a PDF document $T$ by exploiting the 1D-representation of a permutation $π^*$, and then, since pages of a PDF document $T$ are 2D objects, we present an image-based algorithm for encoding $π^*$ into $T$ by first mapping the elements of $π^*$ into a matrix $A^*$ and then using the information stored in $A^*$ to mark invisibly specific areas of PDF document $T$. Finally, we describe a graph-based watermarking algorithm for embedding a self-inverting permutation $π^*$ into the document structure of a PDF file $T$ by exploiting the RPG-representation of $π^*$ and the structure of a PDF document. We have evaluated the embedding and extracting algorithms by testing them on various and different in characteristics PDF documents.

Stavros D. Nikolopoulos, Iosif Polenakis

In this paper we present an elaborated graph-based algorithmic technique for efficient malware detection. More precisely, we utilize the system-call dependency graphs (or, for short ScD graphs), obtained by capturing taint analysis traces and a set of various similarity metrics in order to detect whether an unknown test sample is a malicious or a benign one. For the sake of generalization, we decide to empower our model against strong mutations by applying our detection technique on a weighted directed graph resulting from ScD graph after grouping disjoint subsets of its vertices. Additionally, we have developed a similarity metric, which we call NP-similarity, that combines qualitative, quantitative, and relational characteristics that are spread among the members of known malware families to archives a clear distinction between graph-representations of malware and the ones of benign software. Finally, we evaluate our detection model and compare our results against the results achieved by a variety of techniques proving the potentials of our model.

Ioannis Chionis, Maria Chroni, Stavros D. Nikolopoulos

Software watermarking involves embedding a unique identifier or, equivalently, a watermark value within a software to prove owner's authenticity and thus to prevent or discourage copyright infringement. Towards the embedding process, several graph theoretic watermarking algorithmic techniques encode the watermark values as graph structures and embed them in application programs. Recently, we presented an efficient codec system for encoding a watermark number $w$ as a reducible permutation graph $F[π^*]$ through the use of self-inverting permutations $π^*$. In this paper, we propose a dynamic watermarking model, which we call WaterRPG, for embedding the watermark graph $F[π^*]$ into an application program $P$. The main idea behind the proposed watermarking model is a systematic use of appropriate calls of specific functions of the program $P$. More precisely, for a specific input $I_{key}$ of the program $P$, our model takes the dynamic call-graph $G(P, I_{key})$ of $P$ and the watermark graph $F[π^*]$, and produces the watermarked program $P^*$ having the following key property: its dynamic call-graph $G(P^*, I_{key})$ is isomorphic to the watermark graph $F[π^*]$. Within this idea the program $P^*$ is produced by only altering appropriate calls of specific functions of the input application program $P$. We have implemented our watermarking model WaterRPG in real application programs and evaluated its functionality under various and broadly used watermarking assessment criteria. The evaluation results show that our model efficiently watermarks Java application programs with respect to several watermarking metrics like data-rate, bytecode instructions overhead, resiliency, time and space efficiency. Moreover, the embedded watermarks withstand several software obfuscation and optimization attacks.