Watermarking Relational Databases Presented by Mohamed Shehab 11 22 2005 1 Talk Outline Introductory Material General Watermarking Model Attacks WM Technique 1 Agrawal et al WM Technique 2 Sion et al Future Challenges and References 11 22 2005 2 What is Watermarking A watermark is a signal that is securely imperceptibly and robustly embedded into original content such as an image video or audio signal producing a watermarked signal The watermark describes information that can be used for proof of ownership or tamper proofing 11 22 2005 3 What is Watermarking Cont Watermark Robust Fragile Robust Watermark for proof of ownership copyrights protection Fragile Watermark for tamper proofing data integrity 11 22 2005 4 Why Watermarking Digital Media Video Audio Images Text are easily copied and easily distributed via the web Database outsourcing is a common practice Stock market data Consumer Behavior data Walmart Power Consumption data Weather data Effective means for proof of authorship Signature and data are the same object Effective means of tamper proofing Integrity 11 22 2005 information is embedded in the data 5 Why is Watermarking Possible Real world datasets can tolerate a small amount of error without degrading their usability Meteorological data used in building weather prediction models the wind vector and temperature accuracies in this data are estimated to be within 1 8 m s and 0 5 C Such constraints bound the amount of change or alteration to that can be performed on the data 11 22 2005 6 What defines the usability constraints Usability constraints are application dependent Alterations performed by the watermark embedding should be unidentifiable by the human visual system in images video For consumer behavior data watermarking should preserve periodicity properties of the data 11 22 2005 7 What defines the usability constraints Cont 11 22 2005 Courtesy of http maps google com 8 Watermark Desirable Properties Detectability Key Based System Can be easily detected only with the knowledge of the secret key Robustness Watermark cannot be easily destroyed by modifying the watermarked data Imperceptibility Presence of the watermark is unnoticeable Blind System Watermark detection does not require the knowledge of the original data 11 22 2005 9 Talk Outline Introductory Material General Watermarking Model Attacks WM Technique 1 Agrawal et al WM Technique 2 Sion et al Future Challenges and References 11 22 2005 10 Watermarking Model Watermark W 100100100 Watermark Encoder Watermarked Data DW Attacker Channel Attacked Data D W Watermark Decoder Data D Secret Key Ks Decoded Watermark WD 100100100 11 22 2005 11 Relational and multimedia data A multimedia object consists of a large number of bits with considerable redundancy Thus the large watermark hiding bandwidth The relative spatial temporal positioning of various pieces of a multimedia object typically does not change Tuples of a relation on the other hand constitute a set and there is no implied ordering between them Portions of a multimedia object cannot be dropped or replaced arbitrarily without causing perceptual changes in the object However a pirate of a relation can simply drop some tuples or substitute them with tuples from other relations 11 22 2005 12 Attacker Model Attacker has access to only the watermarked data set The attacker s goal is to weaken or even erase the embedded watermark and at the same time keep the data usable Attacker s Dilemma Possible Attacks Tuple deletion Tuple alteration Tuple insertion 11 22 2005 13 Talk Outline Introductory Material General Watermarking Model Attacks WM Technique 1 Agrawal et al WM Technique 2 Sion et al Future Challenges and References 11 22 2005 14 WM Technique 1 Agrawal et al Watermarking of numerical data Technique dependent on a secret key Uses markers to locate tuples to hide watermark bits Hides watermark bits in the least significant bits 11 22 2005 15 WM Technique 1 Encoder Watermark W 100100100 Watermark Encoder Watermarked Data DW Attacker Channel Attacked Data D W Watermark Decoder Data D Secret Key Ks Decoded Watermark WD 100100100 Instead Watermark is a function of the data and the secret key 11 22 2005 16 WM Technique 1 Encoder Assumptions K e m and v are randomly selected by the data owner and are kept secret K is the secret key e least significant bits can be altered in a number without affecting its usability Example e 3 101101101 1011101 m used for marker selection v is the number of attributes used in the watermarking process 11 22 2005 17 WM Technique 1 Encoder For all tuples r in D r MAC H K r P K if r MAC mod m 0 Marker Selection i r MAC mod v Selected Attribute b r MAC mod e Selected LSB index if r MAC mod 2 0 MAC is even Else 11 22 2005 Set bit b of r Ai Clear bit b of r Ai 18 WM Technique 1 Encoder MAC mod v MAC mod m PKey 1 1234 4 2345 0 3390 9 4455 Attribute 0 Attribute 1 Attribute v 1 1010101010 010111011 MAC is H K r P K 11 22 2005 MAC mod e 19 WM Technique 1 Decoder Watermark W 100100100 Watermark Encoder Watermarked Data DW Attacker Channel Attacked Data D W Watermark Decoder Data D Secret Key Ks Decoded Watermark WD 100100100 11 22 2005 20 WM Technique 1 Decoder Match Total Count 0 For all tuples r in D r MAC H K r P K if r MAC mod m 0 Total Count i r MAC mod v Selected Attribute b r MAC mod e Selected LSB index if r MAC mod 2 0 MAC is even if bit b of r Ai is Set Match Else Marker Selection If bit b of r Ai is Clear Match Compare Match Total count Threshold 11 22 2005 21 WM Technique 1 Decoder MAC mod v MAC mod m PKey 1 1234 4 2345 0 3390 9 4455 Attribute 0 Attribute 1 Attribute v 1 1010101010 010111011 MAC is H K r P K 11 22 2005 MAC mod e 22 WM Technique 1 Strengths Computationally efficient O n Tuple sorting not required Incremental Updatability 11 22 2005 23 WM Technique 1 Weaknesses No provision of multi bit watermark all operations are dependent only on the secret key Not resilient to alteration attacks LSB can be easily manipulated by simple numerical alterations Shift LSB bits to the right left Requires the presence of a primary key in the watermarked relation Does not handle other usability constraints such as Category 11 22 2005 preserving usability constraints 24 Talk Outline Introductory Material General Watermarking Model Attacks WM Technique 1 Agrawal et al WM Technique 2 Sion et al Future Challenges and References 11 22 2005 25 WM Technique 2 Sion et al Watermarking of numerical data Technique dependent on a secret key