The minimum initial marking problem MIM of Petri nets is described as follows: "Given a Petri net and a firing count vector X, find an initial marking M0, with the minimum total token number, for which there is a sequence δ of transitions such that each transition t appears exactly X(t) times in δ, the first transition is enabled at M0 and the rest can be fired one by one subsequently." This paper proposes two heuristic algorithms AAD and AMIM + and shows the following (1) and (2) through experimental results: (1) AAD is more capable than any other known algorithm; (2) AMIM + can produce M0, with a small number of tokens, even if other algorithms are too slow to compute M0 as the size of an input instance gets very large.

This letter describes a permutation attack (PA) to the subsampling-based watermarking scheme where the high correlations between subimages obtained by subsampling the original image are used for watermark embedding. We show that the correlations can also be easily used to attack the watermarking scheme through a simple permutation procedure, while the quality degradation of attacked watermarked image is visually acceptable. Experimental results show the efficiency of the proposed attack algorithm.

In recently proposed asymmetric watermarking schemes, the public detection is less robust than the private detection. To resolve this problem, a robust asymmetric watermarking scheme using the multiple detection watermarks for public detection is proposed in this letter. In this scheme, the private watermark used for embedding is constructed by secretly selecting the partial elements of those public watermarks. It provides the same robustness for the public and the private detections, and the robustness is demonstrated in the computer simulations.

This paper proposes a novel boundary scan test scheme for intellectual property (IP) core identification via watermarking. The core concept is embedding a watermark identification circuit (WIC) and a test circuit into the IP core at the behavior design level. The procedure depends on current IP-based design flow. This scheme can detect the identification of the IP provider without the need to examine the microphotograph after the chip has been manufactured and packaged. This scheme can successfully survive synthesis, placement, and routing and identify the IP core at various design levels. Experimental results have demonstrated that the proposed approach has the potential to solve the IP identification problem.

We proposed 3D-mesh watermarking using CEGI distribution that has robustness against mesh simplification, cropping, vertex randomization, and rotation and which does not need the original model for detection the watermark. The proposed algorithm embeds the watermark bits into the normal vector direction of meshes that are mapped into the cells that have the large magnitude of complex weight in patch CEGIs. The watermark can be detected based on the known center point of each patch and the rank table of the cell in each patch instead of original model. Experimental results verified that the proposed algorithm has robustness against the attacks.

This paper proposes a quantization-based image-quality guaranteed watermarking (IQGW) method using a nonorthogonal discrete wavelet transformation. An IQGW method generates watermarked images of a desired image quality for any image, neither with trial and error nor with image-dependent parameters. To guarantee the image-quality, the proposed method adjusts the energy of the watermark sequence to be embedded based on the relationship between a nonorthogonally transformed domain and the spatial domain for the signal energy. This proposed method extracts the embedded watermark by quantization of watermarked coefficients, no reference image, thus, is required. In addition, it is capable of controlling the objective and subjective image-quality of a watermarked image independently. With features mentioned above, the proposed method is suitable for real-time embedding of Motion JPEG 2000 videos. Moreover, it is able to fuse quantization- and correlation-based watermarking.

In this letter, a novel wavelet-based semi-fragile watermarking scheme is presented which exploiting the time-frequency feature of discrete wavelet transform (DWT) and high sensitivity on initial value of chaotic map. We also analyze the robustness to mild modification and fragility to malicious attack of our scheme. Its application includes tamper detection, image verification and copyright protection of multimedia content. Simulation results show the scheme can detect and localize malicious attacks with high peak signal-to-noise ratio (PSNR), while tolerating certain degree of JPEG compression and channel additive white Gaussian noise (AWGN).

This letter presents a speech watermarking scheme that is combined with CELP (Code Excited Linear Prediction) speech coding for speech authentication. The excitation codebook of CELP is partitioned into three parts and labeled '0', '1' and 'any' according to the private key. Watermark embedding process chooses the codebook whose label is the same as the watermark bit and combines it with the codebook labeled 'any' for CELP coding. A statistical method is employed to detect the watermark, and the watermark length for authentication and detection threshold are determined by false alarm probability and missed detection probability. The new codebook partition technique produces less distortion, and the statistical detection method guarantees that the error probability can be controlled under prescribed level.

Fingerprinting is a technique to add identifying marks to each copy of digital contents in order to enhance traceability to a distribution system. Collusion attacks, in which the attackers collect two or more fingerprinted copies and try to generate an untraceable copy, are considered to be a threat for the fingerprinting system. With the aim of enhancing collusion security to the fingerprinting system, several collusion secure codes, such as c-frameproof code, c-secure frameproof code and c-identifiable parent property code, have been proposed. Here, c indicates the maximum number of colluding users. However, a practical construction of the above codes is still an issue because of the tight restrictions originated from their combinatorial properties. In this paper, we introduce an evaluation of frameproof, secure frameproof, and identifiable parent property by the probability that a code has the required property. Then, we focus on random codes. For frameproof and secure frameproof properties, we estimate the average probability that random codes have the required property where the probability is taken over the random construction of codes and random construction of coalitions. For the estimation, we assume the uniform distribution of symbols of random codes and the symbols that the coalitions hold. Therefore, we clarify the adequacy of the assumptions by comparison with numerical results. The estimates and numerical results resemble, which implies the adequacy of the assumption at least in the range of the experiment.

This letter presents an image rectification scheme that can be used by any image watermarking algorithms to provide robustness against rotation, scaling and translation (RST) transformations.

AF service class in Diffserv by realizes minimum bandwidth guarantee with the use of differentiated drop precedence property marked on each packet. In the context of a multiple domains environment, however, QoS of individual flow is not always preserved due to the re-marking behavior forced at the domain boundaries. Focusing on this point, this paper proposes new packet re-marking schemes that can improve the per-flow QoS of AF service traversing multiple domains. The basic concept of the schemes distinguishes packets re-marked to out-of-profile at the domain boundaries from those already marked as out-of-profile at the time of entering the network, and allows the re-marked packet to recover back to in-of-profile, thus regaining its rightful QoS within the networks. The performance of the proposed schemes is evaluated through simulation. The results on UDP flows show the effectiveness of the proposed schemes for reducing packet losses on the flow through multiple domains and preserving fairness between flows. Simulations on TCP flows show that the proposed schemes improve the throughput of the flows through multiple domains. The proposed scheme is especially effective on the transfer time of short TCP flows such as Web traffic, whose throughput is affected more seriously by a single packet loss due to its flow control mechanisms.

Digital watermarks on pictures must have the ability to survive various image processing operations while not causing degradation of picture quality. Random geometric distortion is one of the most difficult kinds of image processing for a watermark to survive, and this problem has become a central issue in watermarking research. Previous methods for dealing with random geometric distortion have been based on searches, special watermark patterns, learning, or additional data such as original pictures. Their use, however, is accompanied by large computational overhead or by operational inconvenience. This paper therefore proposes a method based on embedding watermark patterns in two of the three color planes constituting a color picture so that these two planes have a specific covariance. The detection of the embedded information is based on the covariance between these two planes. Random geometric distortion distorts all the constituent color planes of a picture in the same way and thus does not affect the covariance between any two. The covariance-based detection is therefore immune to the distortion. The paper clarifies that detection error would occur whenever the inherent covariance (the covariance in the original picture) overrides the covariance made by watermarking. The two constituent planes having the minimum inherent covariance are therefore selected and their inherent covariance is reduced by shifting one of them and using a noise-reduction preprocess. Experimental evaluations using StirMark confirmed that 64 bits embedded in 256256-pixel pictures can be correctly detected without using searches, special patterns, learning, or additional data.

In this paper, we propose a new fragile watermarking scheme that can be used to verify three-dimensional (3-D) polygonal models by detecting unauthorized alterations. In order to generate a binary watermark sequence, we combine a binary random sequence generated by the user key with a binary logo sequence using the bit-wise exclusive OR operation. The binary watermark sequence is embedded into 3-D triangle strips by perturbing their vertex coordinates. The proposed watermarking scheme can identify specific locations that have been changed. Changes of the vertex coordinates in the watermarked 3-D model are reflected in the extracted watermark image, which indicates the attacked area. Experimental results demonstrate that we can detect various modifications of the watermarked 3-D model: translation, rotation, scaling, randomization of points, polygon simplification, geometry compression, and local deformation.

A novel public watermarking algorithm based on chaotic properties is proposed. Thanks to good randomness and easy reproducibility of chaos, firstly the watermark is permuted by chaotic sequences, then a small number of reference points are selected randomly in the middle frequency bands of DCT domain, and the variable number disorder watermark bits are embedded into the neighborhood of each reference point according to chaotic sequences. The experimental results show the invisibility and robustness.

Based on Radon transform, a novel method for registering a periodic (self-referencing) watermark is presented. Although the periodic watermark is widely used as a countermeasure for affine transformation, there is no known efficient method to register it. Experimental results show that the proposed method is effective for registering the watermark from an image that had undergone both affine transformations and severe lossy compression.

A new scheme for watermarking based on vector quantization (VQ) over a binary symmetric channel is proposed. By optimizing VQ indices with genetic algorithm, simulation results not only demonstrate effective transmission of watermarked image, but also reveal the robustness of the extracted watermark.

Effective counteraction to Distributed Denial-of-Services (DDoS) attacks is a pressing problem over the Internet. For this counteraction, it is considered important to locate the router interfaces closest to the attackers in order to effectively filter a great number of identification jammed packets with spoofed source addresses from widely distributed area. Edge sample (ES) based Probabilistic Packet Marking (PPM) is an encouraging method to cope with source IP spoofing, which usually accompanies DDoS attacks. But its fragmentation of path information leads to inefficiency in terms of necessary number of packets, path calculation time and identification accuracy. We propose Branch Label (BL) based PPM to solve the above inefficiency problem. In BL, a whole single path information is marked in a packet without fragmentation in contrast to ES based PPM. The whole path information in packets by the BL approach is expressed with branch information of each router interfaces. This brings the following three key advantages in the process of detecting the interfaces: quick increase in true-positives detected (efficiency), quick decrease in false-negatives detected (accuracy) and fast convergence (quickness).

Conventional authentication methods, proposed mainly for gray-scale and color images, are not appropriate for palette images, which usually contain simple contents with a limited number of colors. In this paper, a new approach is proposed to verify the integrity of palette images and to locate tampered regions without re-quantization and re-indexing processes. The proposed approach is based on a combined use of both the fragile watermarking and the digital signature approaches, taking the advantages of both approaches and avoiding their drawbacks. To protect a block of an image, authentication signals are first generated according to a secret key. Based on an embeddability property defined in the study, the pixels of each block are classified as embeddable or non-embeddable. Only the former ones are used to embed the authentication signals. A corresponding digital signature is generated as well to compensate the possibly limited embedding capacity of the embeddable pixels that are insufficient in number. To authenticate a block, the recovered authentication signals, yielded from the extracted watermark and the received digital signature, are compared with the one generated according to the correct secret key, to prove the block's legitimacy. The effectiveness and the security of the proposed method are analyzed and tested with a variety of palette images. The results indicate that the proposed method can offer high authentication accuracy as well as maintain a good tradeoff between the authentication signal portability and the resulting image quality.

A robust watermarking scheme based on the time-spread echo method is proposed in this letter. The embedding process is achieved by subband decomposition of a host signal and by controlling the amount of distortion, i.e., power of watermark, of each subband according to the Signal to Mask Ratio (SMR) calculated from MPEG psychoacoustic model. The decoding performance and robustness of the proposed method were evaluated.

This paper proposed a new watermarking algorithm and implementation in hardware, by which the watermarking process and an image compression process can operate in conjunction, in parallel, and/or without degrading the performance of the compression process. The goal of the proposed watermarking scheme is to provide the bases to insist the ownership and to authenticate integrity of the watermark-embedded image by detecting the errors and their positions without the original image (blind watermarking). Our watermarking scheme is to replace the watermark with one or several bit-plane(s) of the DC subband after 2DDWT (2-Dimensional Discrete Wavelet Transform) decomposition which is the basic transformation in DWT-based image compression such as JPEG2000. If more than one bit-plane is involved, the position to embed each watermark bit is randomly selected among the bit-planes by a random number generated with an LFSR (Linear Feedback Shift Register). Experimental results showed that for all the considered attacks except the high compression by JPEG, the error ratios in the extracted watermarks by our algorithm were below 3% and the extracted watermarks were unambiguously recognizable in all the cases. The hardware (FPGA)-implemented result could operate stably in 82 MHz clock frequency. This hardware was merged to DWT-based image compression codec which runs in a real-time in 66 MHz of clock frequency. This resulted in the real-time operation for codec and watermarking together in 66 MHz of clock frequency. The watermarking scheme used 4,037 LABs (24%) of the hardware resource of APEX20KC EP20K400CF672-7 from Altera.