Caroline FONTAINE

Caroline FONTAINE


Chargée de Recherche CNRS

Dépt. Image et Traitement Information

Téléphone : 02 29 00 10 47
Télécopie : 02 29 00 10 98
Courriel : caroline.fontaine@telecom-bretagne.eu
TELECOM Bretagne
Vue aérienne

Examen Module DPC 2011-2012

 

Articles Disponibilité :
 

Tolérance aux fautes

 

Article 1 :

"Definition and Analysis of Hardware-and-Software Fault-tolerant Architectures"
J.-C. Laprie, J. Arlat, C. Béounes and K. Kanoun
IEEE Computer, 1990, 23, 7, pp. 39-51.

A structured definition of hardware- and software-fault-tolerant architectures is presented. Software-fault-tolerance methods are discussed, resulting in definitions for soft and solid faults. A soft software fault has a negligible likelihood or recurrence and is recoverable, whereas a solid software fault is recurrent under normal operations or cannot be recovered. A set of hardware- and software-fault-tolerant architectures is presented, and three of them are analyzed and evaluated. Architectures tolerating a single fault and architectures tolerating two consecutive faults are discussed separately. A sidebar addresses the cost issues related to software fault tolerance. The approach taken throughout is as general as possible, dealing with specific classes of faults or techniques only when necessary.

 

Article 2 :

"Using Passive Replicates in Delta-4 to provide dependable distributed Computing"

As part of the European Strategic Programme for Research in Information Technology (ESPRIT), the Delta-4 project is seeking to define an open, fault-tolerant, distributed computing architecture. The Delta-4 approach to fault-tolerance is based upon the replication of components on distinct host computers. Both active and passive replication strategies are contained within the framework of Delta-4.

This paper presents the philosophy behind the mechanisms used within the passive replication paradigm. In the Delta-4 approach, backward error recovery is achieved by integrating checkpointing with interprocess communication. This approach is seen to be applicable to both deterministic and non-deterministic programs.The paper includes a description of the implementation of such a system within the overall Delta-4 framework.

Article 3 :

"N-Version Programming: a fault-tolerance approach to reliability of Software Operation"

N-version programming is defined as the independent generation of N>=2 fuctionally equivalent programs from the same initial specification. A methodology of N-version programming has been devised and three types of special mechanisms have been identified that are needed to coordinate the execution of an N-version software unit and to compare the correspondent results generated by each version. Two experiments have been conducted to test the feasibility of N-version programming. The results of these experiments are discussed. In addition, constraints are identified that must be met for effective application of N-version programming.

 

Algorithmique distribuée

 

Article 4 :

"The Byzantine Generals Problem"
L. Lamport, R. Shostak and M. Pease
ACM Transactions on Programming Languages and Systems (TOPLAS), Volume 4 , Issue 3 (July 1982), Pages: 382 - 401.

Reliable computer systems must handle malfunctioning components that give conflicting information to different parts of the system. This situation can be expressed abstractly in terms of a group of generals of the Byzantine army camped with their troops around an enemy city. Communicating only by messenger, the generals must agree upon a common battle plan. However, one or more of them may be traitors who will try to confuse the others. The problem is to find an algorithm to ensure that the loyal generals will reach agreement. It is shown that, using only oral messages, this problem is solvable if and only if more than two-thirds of the generals are loyal; so a single traitor can confound two loyal generals. With unforgeable written messages, the problem is solvable for any number of generals and possible traitors. Applications of the solutions to reliable computer systems are then discussed.

Article 5 :

"Consensus in Synchronous Systems: A Concise Guided Tour"
M. Raynal
Proceedings of the 2002 Pacific Rim International Symposium on Dependable Computing (PRDC’02).

This paper is on consensus protocols for synchronous systems where processes can commit crash failures, omission failures or Byzantine failures. It presents and revisits consensus protocols coping with such failures in an increasing order of difficulty. The paper can be seen as a short tutorial whose aim is to make the reader familiar with synchrony assumptions, different definitions of the consensus problem, and a hierarchy of process failure models. An important concern of the paper lies in simplicity. In addition to the survey flavor of the paper, several results that are presented are new, among which the ones concerning the omission failure model.

Article 6 :

"Bounded Cost Algorithms for Multivalued Consensus Using Binary Consensus Instances"
J. Zhang and W. Chen
Information processing letters (2009), vol. 109, no17, pp. 1005-1009.

This paper presents two bounded cost algorithms that solve multivalued consensus using binary consensus instances. The first algorithm uses log n number of binary consensus instances where n is the number of processes, while the second algorithm uses at most 2k binary consensus instances, where k is the maximum length of the binary representation of all proposed values in the run. Both algorithms are significant improvements over the previous algorithm in [Papier 8], where the number of binary consensus instances needed to solve one multivalued consensus is unbounded.

Article 7 :

"Extending Binary Byzantine Agreement to Multivalued Byzantine Agreement"
R. Turpin and B. A. Coan
Inf. Process. Lett. 18(2): 73-76 (1984).

This paper presents an algorithm that extends any binary byzantine consensus algorithm to a multivalued byzantine one. It is a seminal paper in this domain but rather old. This paper is quite short, but since the way papers were written at this time is quite different than the actual way, it may increase the level of difficulty to understand it.

 

Articles Protection de Contenu :

 

Watermarking/Fingerprinting

 

Article 8 :

"An Asymmetric Fingerprinting Scheme Based on Tardos Codes"
A. Charpentier, C. Fontaine, T. Furon and I. Cox.
Inernational Workshop on Information Hiding 2011, LNCS 6958, pp. 43-58, Springer-Verlag, 2011.

Asymmetric fingerprinting protocols are designed to prevent an untrustworthy Provider incriminating an innocent Buyer. These protocols enable the Buyer to generate their own fingerprint by themself, and ensure that the Provider never has access to the Buyer’s copy of the Work. Until recently, such protocols were not practical because the collusion-resistant codes they rely on were too long. However, the advent of Tardos codes means that the probabilistic collusion-resistant codes are now sufficiently short that asymmetric fingerprint codes should, in theory, be practical.

Unfortunately, previous asymmetric fingerprinting protocols cannot be directly applied to Tardos codes, because generation of the Tardos
codes depends on a secret vector that is only known to the Provider. This knowledge allows an untrustworthy Provider to attack traditional
asymmetric fingerprinting protocols. We describe this attack, and then propose a new asymmetric fingerprinting protocol, specifically designed
for Tardos codes.

Article 9 :

"Expectation Maximisation decoding of Tardos probabilistic
fingerprinting code"
A. Charpentier, F. Xie, C. Fontaine, T. Furon.
IS&T/SPIE International Symposium on Electronic Imaging 2009 : Media Forensics and Security XI, Proceedings of the SPIE 7254, SPIE (2009).

This paper presents our recent works on multimedia fingerprinting, improving both the fingerprinting code and the watermarking scheme. Our first contribution focuses on deriving a better accusation process for the well known Tardos codes. It appears that Tardos orginal decoding is very conservative: its performances are guaranteed whatever the collusion strategy. Indeed, major improvements stem from the knowledge of the collusion strategy. Therefore, the first part of this paper investigates how it is possible to learn and adapt to the collusion strategy. Our solution is based on an iterative algorithm a la EM, where a better estimation of the collusion strategy yields a better tracing of the colluders, which in return yields a better estimation of the collusion strategy etc.

The second part of this paper focuses on the multimedia watermarking scheme. In a previous paper, we already used the ‘Broken Arrows’ technique as the watermarking layer for multimedia fingerprinting. However, a recent paper from A. Westfeld disclosed a flaw in this technique. We present here a counter-measure which blocks this security hole while preserving the robustness of the original technique.

Article 10 :

"A Blind, Fast and Robust Method for Geographical Data Watermarking"
Cyril Bazin, Jean-Marie Le Bars and Jacques Madelaine.
ACM Symposium on InformAtion, Computer and Communications Security -- ASIACCS'07, pp. 265-272, 2007.

The aim of this paper is to propose an efficient digital watermarking algorithm on geographical data. Our algorithm is fast, blind and robust. Thus, the original data is not needed in order to prove the authorship of the document and the watermark is resiliant against many transformations applied on the document.

The method we propose is based on a modification of parts of the data selected upon local criterias and a secret key. The local criterias use topological properties of a Delaunay mesh build on the original map. The local modifications of parts of the document introduce a statistical slant inside the document. The detection algorithm is a simple detection of this slant.

Experimental results illustrate the resiliance of the algorithm against different tranformations such as rotation, translation, data shuffling and cropping.

 

Broadcast Encryption et DRM

 

Article 11 :

" Design Rules for Interoperable Domains"
Gwenaël Doërr  and Ton Kalker 
DRM’08, October 27, 2008, Alexandria, Virginia, USA.

In this paper we argue that improved interoperability between DRM systems is likely to benefit to all the actors in the content value chain. Moreover, we describe a domain- based approach to DRM interoperability. We discuss in some detail configuration aspects of such interoperable domains, and how they affect certain social aspects such as marriage and divorce. We conclude that interoperable domains offer a much needed flexibility, allowing users to more easily move between vertical silos and offering content owners a more flexible environment for selling content.

Article 12 :

"Traitor Tracing for Prerecorded and Recordable Media"
H. Jin, J. Lotspiech and S. Nusser
DRM'04, 2004.

In this paper we are focusing on the use of a traitor tracing scheme for distribution models that are based on prerecorded or recordable physical media. When a pirated copy of the protected content is observed, the traitor tracing scheme allows the identification of at least one of the real subscribers who participated in the construction of the pirated copy. We show how we systematically assign the variations to users. We explore under what circumstances traitor tracing technology is applicable for media based distribution and then focus on two challenges specifically related to this form of distribution: We demonstrate a way to encode the variations on the disc that is mostly hidden from the attackers and also remarkably compatible with the existing DVD standard. We also present an efficient key management scheme to significantly reduce the requirement for non-volatile key storage on low-cost CE devices.

Article 13 :

"Efficient Key Management Based on the Subset Difference Method  for Secure Group Communication"
Y. Nakamura and H. Kikuchi
19th International Conference on Advanced Information Networking and Applications, AINA'05, IEEE, 2005.

A new algorithm for efficient key management for secure group communication in wireless ad hoc network with mobile nodes is presented. In order to address the dynamic receiver update operations such as leave or join, the subset difference (SD) method proposed by Naor et al. is introduced. The SD method allows senders to reduce drastically the size of ciphertext to be sent to 2r − 1 using a pseudo random number generator, where r is the number of revoked users (who leave the group). In the SD method, the subsets of authorized users are represented by some differences of two subsets such that i covers valid users and j excludes the revoked users in i. To have all subsets (i, j ) necessary to cover all valid users in a tree, a sender has to test all possible combinations of revoked users. A naive exhaustive search for the purpose takes O(r 3 ) time. This is a drawback of the SD method. Hence, to address the issue for finding the cover, we propose a new efficient algorithm to reduce the cost up to O(r log r log n) by introducing the technique for indexing nodes to be dealt with in the necessary subsets. In addition, we implement the proposed algorithm and demonstrate the performance in terms of processing time in this paper.

Article 14 :

"Digital Emulation of Consumer-Ownable Products"
P. Sweazey, T. Kalker and C. Thill
ICCE 2011


IEEE P1817 is defining a standard for consumer-ownable instances of digital creative works such as movies, music, books, and games. We avoid usage and sharing restrictions and supplier tethers for consumers. For copyright holders we block counterfeiting and preserve the item singularness.
                                                             

Technopôle Brest-Iroise - CS 83818 - 29238 Brest Cedex 3 - France
Tél : 33 (0)2 29 00 11 11 - Fax : 33 (0)2 29 00 10 00