Steganography + Harry Potter = New toy at Fred and George Weasley’s Wizard Wheezes

-Please scroll down for English-

Theo phản hồi lần trước, các bài post của mình từ giờ trở đi sẽ được bố cục gồm phần thuật ngữ và phần thí nghiệm, nhằm giúp cho các bạn không chuyên nắm được các định nghĩa và ý tưởng của mình.



THUẬT NGỮ

Mô hình ngôn ngữ (Language model): là mô hình phân bố xác suất của một chuỗi từ. Chẳng hạn cho 1 chuỗi có m từ, ta sẽ gán cho cụm này một xác suất tương ứng. Nó có tên gọi khác là dự đoán chuỗi từ (word sequence prediction), được ứng dụng rộng rãi trong các bài toán xử lý ngôn ngữ tự nhiên, xử lý tiếng nói…

Ngữ liệu (Corpus): là tập bao gồm các đối tượng văn bản như câu, bài báo, tiểu thuyết … là đối tượng tương tác chính trong xử lý ngôn ngữ tự nhiên.

Mô hình n-gram: là một mô hình ngôn ngữ, dựa trên việc đếm các cụm có n từ liên tiếp để xác định khả năng tồn tại của chúng. Với n = 1, đó đơn thuần là đếm tần suất xuất hiện của 1 từ. Người ta thường chọn n = 3. Một câu sẽ được tích bằng tích xác suất các từ cấu tạo nên câu (tuân theo Chain rule), tuy nhiên từng cặp n từ liên tiếp chứ không xét hết 1 lượt(bổ sung giả định Marokv). Bạn chỉ cần hiểu rằng kết quả sẽ cho ra chuỗi từ có khả năng đi chung với nhau nhất dựa trên ngữ liệu dùng để huấn luyện.

Làm trơn(Smoothing): điều khó khăn trong xử lý mô hình n-gram là, giả sử ngữ liệu có 100 từ vựng, tuy nhiên đi sau từ A chỉ thấy từ B và từ C. Việc không tồn tại trong ngữ liệu không có nghĩa rằng trong thực tế, không có từ D đi sau từ A. Do đó, người ta nghĩ ra các kĩ thuật khác nhau để trung hòa xác suất cho 2 từ đã thấy và 98 từ còn lại chưa thấy (kể cả A), sao cho đảm bảo tổng của chúng vẫn bằng 1.

Ẩn dữ liệu (Steganography): là lĩnh vực mà người ta chèn những đoạn thông tin mật vào các vật chủ như hình ảnh, văn bản mà không thể phân biệt bằng mắt thường. Chẳng hạn với một bức ảnh, ta biến đổi thông điệp ẩn sang dạng bit và giấu nó vào bit cuối cùng của mỗi pixel trong ảnh. Chúng ta sẽ quan tâm 3 đặc điểm trong ẩn dữ liệu: tính vô hình (invisibility-làm sao không để phát hiện bằng giác quan), tính mạnh mẽ (robustness-khả năng phục hồi khi vật chủ bị tấn công) và tính chứa (capacity-bao nhiêu bit thông điệp có thể chứa trong vật chủ).



Ý tưởng này tình cờ đến với mình trong môn học Ẩn dữ liệu và chia sẻ thông tin của thầy Nguyễn  Tiến Huy, trong bài giảng thầy có đoạn: “Trong ẩn dữ liệu trên văn bản, việc tìm cách ẩn dữ liệu vào văn bản sẽ dễ dàng hơn rất nhiều so với việc từ thông điệp muốn giấu, tạo một văn bản tương ứng”. Mình liền chợt nghĩ: “Tại sao không làm cách ngược lại?”

Nung nấu ý định từ đó, tranh thủ thời gian rảnh trước thi, mình tranh thủ cài đặt thử. Ý tưởng khá đơn giản: huấn luyện mô hình 2-gram (bi-gram) trên ngữ liệu là tập 1 Harry Potter của J.K.Rowling mà chưa áp dụng kĩ thuật làm trơn nào. Thông điệp muốn truyền đạt sẽ mã hóa sang dạng bit. Khởi đầu bằng việc chọn 1 từ ngẫu nhiên tồn tại trong dữ liệu, các từ tiếp theo được phát sinh theo quy tắc:

  • Nếu bit muốn nhúng là 1, chọn từ có xác suất đi theo cao nhất.
  • Nếu bit muốn nhúng là 0, chọn từ có xác suất đi theo cao nhì.
  • Nếu danh sách từ khả dĩ chỉ có 1 từ, chọn từ đó mà không nhúng bit nào.

THỰC NGHIỆM:

Mình có thử nghịch một chút trước khi vào vấn đề chính trên chương 1 của bộ truyện (4.670 từ) :))

Phát sinh văn bản 100 từ bằng cách luôn chọn từ có xác suất cao nhất, bắt đầu bằng từ “The”. Có thể thấy chúng bị vòng lặp, bởi trong đó từ “dinner” bị lặp.

The step of saying he walked back inside Harry ‘ time craning over dinner all ; cats couldn ‘ time craning over dinner all ; cats couldn ‘ time craning over dinner all ; cats couldn ‘ time craning over dinner all ; cats couldn ‘ time craning over dinner all ; cats couldn ‘ time craning over dinner all ; cats couldn ‘ time craning over dinner all ; cats couldn ‘ time craning over dinner all ; cats couldn ‘ time craning over dinner all ; cats couldn ‘ time craning over dinner all ; cats couldn ‘ time by the place ,

Phát sinh văn bản 100 từ bằng cách chọn từ ngẫu nhiên trong danh sách các từ theo sau, bắt đầu bằng từ “The”. Cấu trúc ngữ pháp bảo toàn, tuy nhiên với người biết Tiếng Anh sẽ thấy có gì đó không ổn :))

The building at Dumbledore calmly . Yes , judging by his briefcase , on their leather boots were moving around its all , like yourself should be if I expect to take it if it until the little boy anywhere . All this over to a legend – moon spectacles . In his secretary not even sure his feet in reply . On the weather . Harry . It swelled to me , have you see you do with my way ? Howard , who told me that at Dumbledore and James Potter wasn’t a roar as wide smile at the subject as though hoping to see that Professor McGonagall faintly ,

Phát sinh văn bản bằng ý tưởng trình bày ở trên, thông điệp nhúng “Harry Potter”. Thông điệp được xác định kết thúc khi gặp cụm từ “.Marauder’s Map.” Cấu trúc câu lạ lẫm, đáng nghi ngờ :((

The street . He didn’t think this man ‘ t be a large order of his mind . He was a very useful as though she said Professor McGonagall . . He didn’t think this man had a very day , but they were the cat had been watching him , but they were whispering excitedly , but no reason for something . He was a very day , said Dumbledore , but they were the street . . . He was still as though she didn’t seem at the street . He was a very useful as though she said.
Marauder’s Map.

Thử làm lại với ngữ liệu là toàn bộ quyển “Harry Potter và Hòn đá phù thủy” xem sao, từ khởi đầu được chọn ngẫu nhiên.

In here , and a bit more . He had been a few minutes to be able ter do you , and a bit more . ” said Harry . He was the other two . ” said Ron , ” Harry . ” Harry . He had a few seconds before he said Ron , and a bit of them . ” said Harry . ” said Harry . ” Harry . He was a bit more than he said Ron . ” Harry . ” Harry , and the door . He had been in.
Marauder’s Map.

Văn bản trông cực kì đáng nghi, dễ thấy là lỗi lặp từ “Harry”. Cũng phải thôi khi tên nhân vật chính xuất hiện nhiều lần nhất trong chuyện, do đó là từ hay đi sau nhiều từ nhất. Ta cùng thử đánh giá hiệu quả của phương pháp này trên 3 phương diện của Ẩn dữ liệu:

  • Tính tàng hình: dù giữ nguyên dạng văn bản và đa số tuân thủ ngữ pháp, nhưng dễ dàng thấy về mặt ý nghĩa của câu còn yếu kém. Với 2-gram, dữ liệu càng nhiều thì hiệu quả càng tệ. Nên chọn ngữ liệu ít hoặc train thử trên mô hình 3-gram. Cũng cần cải tiến thêm khâu tiền xử lý văn bản.
  • Tính mạnh mẽ: khi giải mã, chỉ cần dựa theo kết quả lấy từ mô hình để trích xuất ngược ra thông điệp. Thông điệp sẽ sai đoạn văn phát sinh bị mất, thêm hoặc tráo từ. Tuy nhiên các thông điệp trước đó không bị ảnh hưởng.
  •  Khả năng chứa: ý tưởng áp dụng là mỗi tự đại diện cho 1 bit. Bạn có thể tạo 1 list 4 từ để mã hóa cho 2 bit và tương tự. Nhưng mình dự đoán như vậy đoạn văn phát sinh sẽ dài hơn bạn kì vọng. Thử nhé :))

Được sự cho phép của thầy, mình chia sẻ source code kèm dữ liệu chương 1 Harry Potter, bạn có thể download bên dưới và chạy thử. Lưu ý ngữ liệu này phục vụ mục đích khoa học, bạn không có quyền sao chép và đưa cho bên thứ ba.

Source code: https://github.com/hovinh/steganography.git




According to previous replies, I decide from now on my post will be structured as followed: Terminology and Experiment, in hope that it can help for people from different field can catch up my idea.



TERMINOLOGY

Language model: is the probability distribution of a sequence of words. If you have a sequence with m words, I will assign a probability for it. This concept is also called word sequence prediction, broadly applied in Natural Language Processing, Speech Processing…

Corpus: a collection of documents such as sentences, papers, novels… is main interactive object in Natural Language Processing.

N-gram model: is a kind of language model, based on counting the frequeny of n-words phrase to determine its probability of existence. With n = 1, it is trivial for counting the number of appearance of 1 word. We usually choose n = 3. A generated sentence will be calculated by multiplying all probability of individual words (Chain rule). However, each n-words phrase will be counted seperately (Markov assumption). You only need to know that output will be a sequence in which contains all the most probable words can go along together in training corpus.

Smoothing: the hardest part in processing n-gram model is that, if we assumed the corpus having 100 words in vocabulary, we only see word B and C come after word A. That does not mean in practical, there is no other words can come after A. So that, scientists developed many different technique to normalize probabilty of B, C and 98 other words(including A itself), with respect to the sum probability will be equal to 1.

Steganography: the field in which people insert hidden message in hosts like images, documents without being noticed by ordinary human eyes. For example, with 1 pictures, we can first convert message into bits, then hide it in the last bit of each pixel. We evaluate about 3 characteristic of a steganography technique with 3 characteristic: invisibility – how to not be detected by human’s senses, robustness-how to recover message when hosts attacked, and capacity – how many bits of message can be stored in host.



I came up with this idea when studying in Steganography 101 class of Msc Nguyen Tien Huy. In his lecture, there is a part: “In hiding data on text, finding a way to hide data in text is easier than generating a text from the message.” Then I thought: “Why not?”

With that in mind, using my leisure time before the storm (I mean final exam :)) ), I implemented it. The idea is quite simple: train a 2-gram (bi-gram) model on corpus “Harry Potter and the Sorcerer’s Stone” of J.K. Rowling without applying any Smoothing method. The message will be encoded into bits. Starting by choosing a random word in corpus, the following words will be generated by this rule:

  • If embedded bit is 1, choose the word has highest probability.
  • If embedded bit is 0, choose the word has second highest probability.
  • If the length of list of possible word is 1, choose it with no embedding any bit.

EXPERIMENT:

I play a little bit with chapter 1 of the book (4.670 words) :))

Generate 100-words document by always choosing the word has highest probability, starting with “The”. We can see there is a loop here because the word “dinner” showed up twice.

The step of saying he walked back inside Harry ‘ time craning over dinner all ; cats couldn ‘ time craning over dinner all ; cats couldn ‘ time craning over dinner all ; cats couldn ‘ time craning over dinner all ; cats couldn ‘ time craning over dinner all ; cats couldn ‘ time craning over dinner all ; cats couldn ‘ time craning over dinner all ; cats couldn ‘ time craning over dinner all ; cats couldn ‘ time craning over dinner all ; cats couldn ‘ time craning over dinner all ; cats couldn ‘ time by the place ,

Generate 100-words document by choosing random words in the list of following words, start with “The”. The grammar structure is fine, but in the eyes of English learner, there is something wrong here :))

The building at Dumbledore calmly . Yes , judging by his briefcase , on their leather boots were moving around its all , like yourself should be if I expect to take it if it until the little boy anywhere . All this over to a legend – moon spectacles . In his secretary not even sure his feet in reply . On the weather . Harry . It swelled to me , have you see you do with my way ? Howard , who told me that at Dumbledore and James Potter wasn’t a roar as wide smile at the subject as though hoping to see that Professor McGonagall faintly ,

Generate document with idea above, embedded message is “Harry Potter”. The end of message is determined when meet the word “.Marauder’s Map.” The structure is weird and suspicious:((

The street . He didn’t think this man ‘ t be a large order of his mind . He was a very useful as though she said Professor McGonagall . . He didn’t think this man had a very day , but they were the cat had been watching him , but they were whispering excitedly , but no reason for something . He was a very day , said Dumbledore , but they were the street . . . He was still as though she didn’t seem at the street . He was a very useful as though she said.
Marauder’s Map.

Try again with the full book, choosing the starting word randomly.

In here , and a bit more . He had been a few minutes to be able ter do you , and a bit more . ” said Harry . He was the other two . ” said Ron , ” Harry . ” Harry . He had a few seconds before he said Ron , and a bit of them . ” said Harry . ” said Harry . ” Harry . He was a bit more than he said Ron . ” Harry . ” Harry , and the door . He had been in.
Marauder’s Map.

The document is extremely suspicious, easy to be seen is the word “Harry” is repeated many time. It makes sense because the name of  the protagonist is the most common word in the story, so that it is also the word following a lot of words most. Let’s try to evaluate the efficiency of this proposed method in 3 main aspects of Steganography:

  • Invisibility: even though keeping the document form and follow grammar, it easily to see that the meaning of sentence is weak. With 2-gram, the bigger the corpus, the worse it is. You should try with small corpus or 3-gram model. Preprocessing step is also need to be concerned.
  • Robustness: When extracting message, we only need to based on the trained model to extract the message. The message will be extracted wrongly if you add, delete or replace word. However, the previous part is not affected.
  •  Capacity  ability: my idea use each word representing for 1 bit. You can make word represent for 2, 3 or more bits based on the length of probable list of following words. I predict the output will be longer than you expected. You should try it :))

With the allowance of my supervisor, I share my source code with the corpus of Chapter of the first book of Harry Potter. You can download and try running it. Warning: this corpus is for purely scientific puspose, you are not allowed to copy in any forms and give it to a third party.

Source code: https://github.com/hovinh/steganography.git

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.