In today’s digital era of constant information sharing, ensuring the authenticity and integrity of digital documents—particularly portable document format (PDF) files—has become increasingly important. This paper introduces a watermarking scheme for PDF files by embedding quick response (QR) codes into the spatial domain of text color. The method takes a PDF and a QR code as input, resizing the QR code to match the length of the text on each page. The embedding process incorporates Arnold’s transformation and a permutation equal to the QR code’s size to secure both embedding and extraction. The QR code is applied by slightly altering the color of specific text characters that correspond to black pixels in the QR code image, achieving spatial-domain watermarking without degrading visual quality. Experimental evaluation demonstrates the method’s robustness against various attacks, with the watermarked PDFs achieving an average Peak Signal-to-Noise Ratio (PSNR) of 57.6 dB and Structural Similarity Index (SSIM) of 0.99. The extracted QR codes maintain PSNR values above 68.8 dB and SSIM equal to 1 after common processing attacks. The scheme also effectively detects malicious tampering, proving the potential of the proposed watermarking scheme in the protection of PDF files.

Software watermarking is a defense technique used to prevent or discourage software piracy by embedding a signature in the code. In ( Discrete Applied Mathematics 250 ( 2018 ) 145–164), a software watermarking system is presented which encodes an integer number w (i.e., a watermark) as a reducible permutation flow-graph [Formula: see text] embeddable in the code through the use of a self-inverting permutation [Formula: see text]. In this work, we theoretically investigate this watermarking system and exploit structural properties of the self-inverting permutation [Formula: see text] encoding the watermark in order to prove its resilience to edge-modification attacks on the flow-graph [Formula: see text]. Based on the minimum number of edge modifications needed to be applied on [Formula: see text] so that a different watermark can be extracted from the resulting graph, we give a characterization of the watermarks as strong, intermediate or weak and provide good recommendations for the choices of watermark.

In this paper we present a graph-based framework that, utilizing relations between groups of System-calls, detects whether an unknown software sample is malicious or benign, and classifies a malicious software to one of a set of known malware families. In our approach we propose a novel graph representation of dependency graphs by capturing their structural evolution over time constructing sequential graph instances, the so-called Temporal Graphs. The partitions of the temporal evolution of a graph defined by specific time-slots, results to different types of graphs representations based upon the information we capture across the capturing of its evolution. The proposed graph-based framework utilizes the proposed types of temporal graphs computing similarity metrics over various graph characteristics in order to conduct the malware detection and classification procedures. Finally, we evaluate the detection rates and the classification ability of our proposed graph-based framework conducting a series of experiments over a set of known malware samples pre-classified into malware families.

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.

Abstract: The intellectual property infringement in music due to the proliferation of the internet and the ease of creating and distributing identical digital objects has brought watermarking techniques to the forefront of digital rights protection. Towards this direction, a significant number of watermarking techniques have been proposed in recent years in order to create robust and imperceptible audio watermarks. In this work we propose an au-dio watermarking technique which efficiently and secretly embeds information, or equivalently watermarks, into an audio digital signal. Our technique is based on the main idea of a recently proposed image water-marking technique expanding thus the digital objects that can be efficiently watermarked through the use of self-inverting permutations. More precisely, our audio watermarking technique uses the 1D representation of self-inverting permutations and utilizes marking at specific areas thanks to partial modifications of the au-dio’s Discrete Fourier Transform (DFT); these modifications are made on the magnitude of specific frequency bands. We have evaluated the embedding and extracting algorithms by testing them on various and different in characteristics audio signals that were in WAV format and we have obtained positive results. The algorithms have been developed and tested using the mathematical software package Matlab. 1

In this paper, we consider the problems of co-biconnectivity and strong co-connectivity, i.e., computing the biconnected components and the strongly connected components of the complement of a given graph. We describe simple sequential algorithms for these problems, which work on the input graph and not on its complement, and which for a graph on n vertices and m edges both run in optimal O(n+m) time. Our algorithms are not data structure-based and they employ neither breadth-first-search nor depth-first-search. Unlike previous linear co-biconnectivity and strong co-connectivity sequential algorithms, both algorithms admit efficient parallelization. The co-biconnectivity algorithm can be parallelized resulting in an optimal parallel algorithm that runs in O(log2n) time using O((n+m)/log2n) processors. The strong co-connectivity algorithm can also be parallelized to yield an O(log2n)-time and O(m1.188/logn)-processor solution. As a byproduct, we obtain a simple optimal O(logn)-time parallel co-connectivity algorithm. Our results show that, in a parallel process environment, the problems of computing the biconnected components and the strongly connected components can be solved with better time-processor complexity on the complement of a graph rather than on the graph itself.

Abstract In this paper, we study a variant of the path cover problem, namely, the k‐fixed‐endpoint path cover problem. Given a graph G and a subset ${\cal T}$ of k vertices of V(G), a k‐fixed‐endpoint path cover of G with respect to ${\cal T}$ is a set of vertex‐disjoint paths ${\cal P}$ that covers the vertices of G such that the k vertices of ${\cal T}$ are all endpoints of the paths in ${\cal P}$ . The k‐fixed‐endpoint path cover problem is to find a k‐fixed‐endpoint path cover of G of minimum cardinality; note that, if ${\cal T}$ is empty, that is, k = 0, the stated problem coincides with the classical path cover problem. We show that the k‐fixed‐endpoint path cover problem can be solved in linear time on the class of cographs. More precisely, we first establish a lower bound on the size of a minimum k‐fixed‐endpoint path cover of a cograph and prove structural properties for the paths of such a path cover. Then, based on these properties, we describe an algorithm which, for a cograph G on n vertices and m edges, computes a minimum k‐fixed‐endpoint path cover of G in linear time, that is, in O(n+m) time. The proposed algorithm is simple, requires linear space, and also enables us to solve some path cover related problems, such as the 1HP and 2HP, on cographs within the same time and space complexity. © 2007 Wiley Periodicals, Inc. NETWORKS, Vol. 50(4), 231–240 2007

Due to the increasing reliance of society on the timely and reliable transfer of large quantities of information (such as voice, data, and video) across high speed communication networks, it is becoming important for a network to offer survivability, or at least graceful degradation, in the event of network failure. In this paper we aim to offer a solution in the selection of the K-best disjoint paths through a network by using graph theoretic techniques. The basic approach is to map an arbitrary network graph into a trellis graph which allows the application of computationally efficient methods to find disjoint paths. Use of the knowledge of the K-best disjoint paths for improving the survivability of ATM networks at the virtual path and virtual circuit level is discussed.