GT 3: Ứng dụng trong dòng dữ liệu và bảo mật

3. Vài ứng dụng của thử nhóm bất ứng biến

Muthu Muthukrishnan là một khoa học gia máy tính có rất nhiều đóng góp nặng ký trong nhiều nhánh khác nhau: cơ sở dữ liệu, thuật toán, dòng dữ liệu, v.v. Gần đây anh chuyển về Google làm về các thuật toán ad bidding, một nhánh “hot” liên kết kinh tế học và KHMT; có thể xem là một phần của môn “kinh tế tính toán” — còn non trẻ nhưng rất thú vị. Muthukrishan cũng là một trong các khoa học gia vui vẻ dễ gần nhất mà tôi biết. Một lần giới thiệu Muthu nói chuyện, tôi hỏi anh muốn giới thiệu như thế nào, anh bảo giới thiệu thế này: “đây là Muthu, anh ta sẽ nói chuyện”. Muthukrishnan và Cormode mấy năm trước có một bài báo rất thú vị ở hội nghị FUN với nhan đề “Làm thế nào để tăng tỉ lệ nhận bài của các hội nghị đỉnh”. Tôi đã giới thiệu bài này trong một blog post cũ.

Hai bài trước đã bàn về khái niệm thử nhóm bất ứng biến tổ hợp và một vài kết quả cơ bản. Trước khi nói đến các kết quả sâu hơn thì ta quay lại mô tả chi tiết một vài ứng dụng. Ứng dụng đầu tiên do Cormode và Muthukrishnan đề xuất là cho một bài toán trong dòng dữ liệu.

3.1. Một ứng dụng trong dòng dữ liệu

Dòng dữ liệu là một nhánh nghiên cứu khá mới và đầy tiềm năng, dù hai năm đổ lại đây có vẻ hơi bế tắc.

Trong phạm vi của bài này ta chỉ thảo luận một bài toán của dòng dữ liệu: tính các phần tử tần suất cao (heavy hitter). Đại khái, giả sử ta có một router phải xử lý rất nhiều gói dữ liệu trên mạng. (Các routers ở trung tâm của Internet phải xử lý một gói dữ liệu trong vòng vài nano-giây hay thậm chí ít hơn.) Mỗi gói dữ liệu có địa chỉ đích đến. Nếu ta đang quan sát các gói dữ liệu trên dòng các gói đi qua router (cả nhiều triệu gói) mà trong đó có “rất nhiều” gói có cùng đích đến thì có khả năng là đia chỉ đó đang bị tấn công DoS. Ngược lại, nếu quá nhiều gói có cùng địa chỉ nguồn thì máy nguồn có lẽ đang bị một con sâu nhiễm và nó đang quét mạng. Trong ngữ cảnh khác, các ISPs có thể muốn thống kê xem trong số các gói dữ liệu gửi qua mạng của họ, có một số địa chỉ nào xuất hiện với tần suất cao hay không. Còn đây là một ứng dụng khác hẳn: các công ty như Google và Yahoo có rất nhiều “click streams” — triệu triệu clicks con chuột mỗi ngày. Họ có thể muốn biết hiện nay website nào được click nhiều nhất.

Từ những vấn đề thực tế như vậy, chúng ta có thể định dạng bài toán tính các phần tử tần suất cao trong một dòng dữ liệu. Giả sử ta có một dòng {m} gói, trong đó {m} cực lớn và không biết trước. Mỗi gói có nhãn trong tập nhãn {[N]}, trong đó {N} cũng rất lớn. Ví dụ, nếu tập nhãn là các địa chỉ IP thì {N} có thể lên đến {2^{32}}. Chúng ta muốn thiết kế một thuật toán chỉ ra các nhãn có tần suất lớn hơn {m/(d+1)}, trong đó {d} là một tham số (thường là hằng số). Bài toán là thiết kế một thuật toán, xử lý từng gói từng gói một trong dòng, sao cho thời gian chạy và tổng bộ nhớ dùng cho thuật toán là sub-linear trên các tham số {N}{m}.

Chú ý rằng có nhiều cách để định nghĩa bài toán tìm nhãn tần suất lớn này, tùy theo ứng dụng thực tế. Ví dụ, chúng ta có thể muốn tìm {d} phần tử xuất hiện nhiều nhất (không nhất thiết phải lớn hơn {m/(d+1)} lần.)

Ví dụ 1 (Bài toán phần tử đa số) Nếu {d=1} thì ta cần thiết kế một thuật toán trả về nhãn nào xuất hiện nhiều hơn {m/2} lần. Đây là một bài tập rất tốt cho các bạn làm quen với các dòng dữ liệu. Dĩ nhiên, chúng ta không thể dùng một dãy gồm {N} phần tử để đếm nhãn vì như vậy tổng không gian dùng sẽ là {\Omega(N)}. Làm thế nào làm được việc này trong thời gian và không gian polo-log{(m,N)}?

Sau đây là một lời giải rất dễ thương của Fischer và Salzberg; trước đó Boyer và Moore cũng đã đề xuất lời giải tương tự trong một báo cáo kỹ thuật (technical report).

Thuật toán Boyer-Moore-Fischer-Salzberg

Chúng ta sẽ lưu trữ một biến đếm counter và một nhãn, gọi là nhãn hiện hành

1. gán counter =1 và nhãn đầu tiên trong dòng dữ liệu là nhãn hiện hành

2. với mỗi nhãn mới {a} trong dòng dữ liệu (từ nhãn thứ 2 trở đi)

  • nếu {a} giống nhãn hiện hành thì tăng counter lên 1.
  • nếu {a} khác nhãn hiện hành
    • nếu (counter == 0) thì thay nhãn hiện hành bằng {a} và gán counter = 1;
    • nếu (counter > 0) thì giảm counter đi 1

Thuật toán trên chỉ dùng bộ nhớ với kích thước {\Theta(\log N + \log m)}, dĩ nhiên là tối ưu. Khi kết thúc, nếu có tồn tại một phần tử đa số (xuất hiện hơn {m/2} lần) thì phần tử đa số chính là nhãn hiện hành. Rất tiếc là nếu không có phần tử đa số thì thuật toán này không phân biệt được. Có thể chứng minh được rằng một thuật toán luôn luôn chỉ ra được phần tử đa số (hoặc báo cáo là không tồn tại phần tử đa số) buộc phải dùng không gian cỡ {\Omega(m)}. Do đó, nếu chỉ được phép dùng không gian cỡ poly-log thì buộc chúng ta phải chấp nhận các giải pháp xấp xỉ. Ngoài ra, đã có rất nhiều các bài báo khác đưa ra các lời giải tổng quát hơn cho {d>1}, xem bài mới nóng hổi của Cormode-Hadjieleftheriou ở CACM 2009 và các tham khảo trong đó.

Thuật toán như trên và các mở rộng của nó không giải quyết được trường hợp khi ta trừ bớt một nhãn khỏi dòng dữ liệu. Ví dụ, xét dòng dữ liệu là các đơn đặt hàng trên mạng của Amazon, trong đó nhãn của một mặt hàng có thể là loại mặt hàng chẳng hạn. Một cái click của một trong số cả triệu người dùng Amazon sẽ tạo ra một nhãn mới. Nhưng người dùng cũng có thể click để hủy bỏ một đơn hàng đã đặt trước đó. Như vậy, một biến thể của bài toán tính các phần tử tần suất cao đòi hỏi thuật toán cho phép xóa nhãn nữa.

Có một giải pháp của Cormode-Muthukrishnan dựa trên ý tưởng thử nhóm như sau. Giả sử ta có một ma trận {d}-phân-cách {{\bf M}=(m_{ij})} với {t} hàng và {N} cột. Như sẽ thấy trong một bài viết tới, không cần phải xây dựng ma trận này cụ thể ra (vì nếu không sẽ cần không gian {\Omega(tN)}). Ta biết cách thiết kế một thuật toán hiệu quả để xác định xem {m_{ij}=1} hay không. Lưu trữ {t} bộ đếm {c_1, c_2, \dots, c_t}, khởi tạo bằng {0}. Mỗi khi có một nhãn {j} mới tới, nếu {m_{ij}=1} thì tăng {c_i} lên {1}. Còn nếu nhãn {j} được xóa đi thì giảm {c_i} đi {1}, cho với mọi {i}{m_{ij}=1}. Ta cũng đếm tổng số {c} các gói đã đến cho đến thời điểm này, và giảm hoặc tăng {c} tùy theo phần tử mới trong dòng dữ liệu có phải xóa hay không. Tổng số không gian dùng là {O(t\log m)}. Nếu nhãn {j} xuất hiện với tần suất nhiều hơn {c/(d+1)} thì {c_i > c/(d+1)} với mỗi bộ đếm {i}{m_{ij}=1}. Để đơn giản vấn đề, ta sẽ giả sử rằng các nhãn tần suất thấp xuất hiện với tổng tần suất nhiều nhất là {c/(d+1)}. (Có cách để làm mềm cái giả thiết này, nhưng điều đó không quan trọng trong ngữ cảnh của bài này.) Như vậy, nếu {c_i \leq m/(d+1)} thì tất cả các nhãn mà bộ đếm này đếm đều là các nhãn tần suất thấp. Vì thế, từ vector bộ đếm ta có thể xây dựng vector kết quả thử nhóm {{\bf r} \in \{0,1\}^t} bằng cách đặt {r_i = 1} nếu và chỉ nếu {c_i > m/(d+1)}. Theo bài của Cormode-Hadjieleftheriou ở trên thì giải pháp dựa trên thử nhóm cạnh tranh được với các giải pháp khác vì nó có lợi điểm là rất chính xác và nhanh, tuy vẫn còn dùng hơi nhiều không gian.

Giải pháp này rất cần một thuật toán giải mã chạy trong thời gian poly-log{(N)}, sẽ được thảo luận trong một bài tiếp theo. Đây là một động cơ để chúng ta đi tìm cách giải mã kết quả thử nhóm trong thời gian poly{(t, \log N)} cho một ma trận {d}-phân-cách {t \times N}.

3.2. Hai ứng dụng trong bảo mật

Trong bảo mật, chúng ta thường phải kiểm tra tính vẹn toàn dữ liệu (data integrity). Cách thường dùng là kèm với dữ liệu một dạng mã kiểm tra lỗi hoặc mã khôi phục lỗi (error detection, error correction codes). Phương pháp này được dùng mọi nơi, trong đĩa cứng, CD, DVD, gói dữ liệu mạng, vân vân. Đơn giản là ta thường tính giá trị băm (hash value) dùng một hàm băm tốt nào đó và tính lại giá trị này để xác minh tính toàn vẹn dữ liệu. Đây là dạng mã kiểm tra lỗi thông dụng nhất. Giả sử ta phải chứa {N} món dữ liệu trong một cấu trúc dữ liệu nào đó. Ví dụ như mỗi đỉnh của một cây nhị phân, hoặc mỗi nốt trong một danh sách liên kết (linked list), hoặc mỗi nốt trong một danh sách nhảy quãng (skip list), đều có thể là một món dữ liệu. Để kiểm tra tính toàn vẹn dữ liệu, chúng ta có thể chứa {N} giá trị băm của từng món. Sau đó, để kiểm tra tính toàn vẹn, ta tính lại giá trị băm của cả {N} món. Goodrich-Atallah-Tamassia gợi ý chúng ta tính giá trị băm của nhiều tập con của các món dữ liệu này. Khi cần kiểm tra, nếu một giá trị băm không trùng thì ta biết một món trong tập con bị thay đổi. Đến đây, các bạn có thể đoán được rằng ta chỉ cần lưu trữ {O(d^2\log N)} giá trị băm thôi và đã có thể chỉ ra các món dữ liệu bị thay đổi rồi.

Một ứng dụng thứ hai trong bảo mật là ứng dụng để xác minh chữ ký điện tử. Nếu ta có một văn kiện điện tử đã ký dùng khóa riêng, ta có thể dùng khóa công cộng để xác minh chữ ký dễ dàng. Tuy nhiên, nếu phải làm điều này với hàng triệu văn kiện thì cũng tốn nhiều thời gian. Ý tưởng của môn “mật mã hàng loạt” (batch cryptography) là làm thế nào giảm thời gian chạy của các thuật toán mật mã học bằng cách xử lý hàng loạt các tác vụ loại này cùng một lúc. Dĩ nhiên là cái thuật toán chữ ký điện tử phải được thiết kế để nó có thể xác minh hàng loạt một cách hiệu quả được. Thuật toán xác minh chữ ký hàng loạt có tính chất sau đây: có thể đưa cho thuật toán xác minh một nhóm các văn kiện đã ký — thuật toán trả về {0} nếu tất cả các văn kiện đều được xác minh và {1} nếu ít nhất một văn kiện bị lỗi. Một số thuật toán xác minh hàng loạt đã được đề nghị, xem bài này, và bài này cùng các tham khảo trong chúng. Các bạn có thể đoán phần còn lại: các ma trận {d}-phân-cách cho ta biết nên nhóm các văn kiện như thể nào để xác minh hàng loạt. Lý do mà ta cân phiên bản bất ứng biến là vì ta có thể có chạy song song các phép thử trên nhiều bộ vi xử lý cùng một lúc. Bài báo của Zaverucha và Stinson so sánh các giải pháp thử nhóm khác nhau cho bài này. Các cấu hình multi-core hứa hẹn sẽ càng ngày càng phổ dụng. Còn các thuật toán ứng biến thì có bản chất tuần tự. Do đó thử nhóm bất ứng biến là một công cụ quan trọng.

Chủ đề : Bảo mật và mật mã học, Thuật ToánBookmark the permalink. Trackbacks are closed, but you can post a comment.

One Comment

  1. Posted 15/07/2011 at 8:34 am | Permalink

    Bài viết hay lắm! Mình cũng khoái cái vụ mã hóa này lắm nha! có dịp trao đổi thêm với bạn há!

Post a Comment

Your email is never published nor shared. Required fields are marked *

You may use these HTML tags and attributes <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

*
*