Tài liệu Bảo vệ tính riêng tư trong xử lý câu truy vấn trên dòng dữ liệu

ĐẠI HỌC QUỐC GIA TP. HCM TRƯỜNG ĐẠI HỌC BÁCH KHOA O BÁO CÁO TỔNG KẾT KẾT QUẢ ĐỀ TÀI KHCN CẤP TRƯỜNG Tên đề tài BẢO VỆ TÍNH RIÊNG TƯ TRONG XỬ LÝ CÂU TRUY VẤN TRÊN DÒNG DỮ LIỆU Mã số đề tài: T-KHMT-2012-23 Thời gian thực hiện: 01/02/2012 – 01/02/2013 Chủ nhiệm đề tài: Nguyễn Ngọc Thiên An Đồng chủ nhiệm đề tài: PGS.TS. Đặng Trần Khánh Thành phố Hồ Chí Minh – Tháng 01/2013 Danh sách các cán bộ tham gia thực hiện đề tài 1. PGS. TS. Đặng Trần Khánh – Bộ môn Hệ Thống Thông Tin – Khoa Khoa Học & Kỹ Thuật Máy Tính. 2. KS. Nguyễn Ngọc Thiên An – Bộ môn Hệ Thống Thông Tin – Khoa Khoa Học & Kỹ Thuật Máy Tính. Nghiên cứu bảo vệ tính riêng tư trong xử lý câu truy vấn cho dòng dữ liệu MỤC LỤC MỤC LỤC .............................................................................................................................................................. 3 1. Nội dung đăng ký ..................................................................................................................................... 4 2. Kết quả thực hiện..................................................................................................................................... 4 3. 2.1. Tìm hiểu tổng quan vấn đề xử lý truy vấn trên dòng dữ liệu ....................................... 4 2.2. Tìm hiểu các kỹ thuật làm mờ dữ liệu cho dòng dữ liệu ................................................ 6 2.3. Đề xuất giải pháp bảo vệ tính riêng tư trong xử lý truy vấn trên dòng dữ liệu ..... 6 2.4. Hiện thực demo cho giải pháp đề xuất ............................................................................... 15 2.5. Viết bài báo khoa học cho hội nghị/tạp chí chuyên ngành......................................... 18 Kết quả mới ............................................................................................................................................. 18 3.1. Đánh giá theo lý thuyết ............................................................................................................ 19 3.2. Đánh giá theo thực nghiệm .................................................................................................... 20 4. Đề xuất ứng dụng .................................................................................................................................. 22 5. Báo cáo kinh phí .................................................................................................................................... 24 6. Báo cáo quyết toán ............................................................................................................................... 25 7. Danh mục tài liệu tham khảo ........................................................................................................... 25 8. Kết luận và kiến nghị ........................................................................................................................... 27 PHỤ LỤC............................................................................................................................................................ 29 3 Nghiên cứu bảo vệ tính riêng tư trong xử lý câu truy vấn cho dòng dữ liệu 1. Nội dung đăng ký Phần này liệt kê những nội dung đã được đăng ký trong thuyết minh đề tài. a. Tìm hiểu tổng quan vấn đề xử lý truy vấn trên dòng dữ liệu:  Các yêu cầu cơ bản trong xử lý truy vấn trên dòng dữ liệu.  Các kỹ thuật xử lý truy vấn trên dòng dữ liệu.  Các kỹ thuật tối ưu trong xử lý truy vấn trên dòng dữ liệu.  Đánh giá, so sánh các điểm yếu, điểm mạnh của các kỹ thuật trên. b. Tìm hiểu các kỹ thuật làm mờ dữ liệu cho dạng dữ liệu theo dòng:  Tìm hiểu các giải thuật làm mờ dữ liệu dựa trên kỹ thuật k-anonymity.  Tìm hiểu các kỹ thuật khác hỗ trợ cho việc bảo vệ tính riêng tư như: indexing, lý thuyết xác suất, mạng neuron,…  Đánh giá, so sánh các điểm yếu, điểm mạnh của các kỹ thuật trên. c. Đề xuất giải pháp để bảo vệ tính riêng tư trong xử lý câu truy vấn trên dữ liệu dòng:  Xây dựng giải thuật bảo vệ tính riêng tư trong xử lý câu truy vấn trên dữ liệu dòng.  Đề xuất kiến trúc cho hệ thống. d. Hiện thực một demo nhỏ cho giải pháp đề xuất. e. Viết bài báo khoa học cho hội nghị/tạp chí chuyên ngành. f. Viết báo cáo tổng hợp và nghiệm thu đề tài. 2. Kết quả thực hiện Phần này trình bày cụ thể các kết quả đã đạt được theo nội dung đã thuyết minh đăng ký. 2.1. Tìm hiểu tổng quan vấn đề xử lý truy vấn trên dòng dữ liệu a. Các yêu cầu cơ bản trong xử lý truy vấn trên dòng dữ liệu:  Ảnh hưởng của các đặc tính dòng dữ liệu (liên tục, không giới hạn và tốc độ nhanh) lên việc xử lý truy vấn.  Các loại tác vụ gây khó khăn cho việc xử lý truy vấn trên dòng dữ liệu: stateful và blocking. 4 Nghiên cứu bảo vệ tính riêng tư trong xử lý câu truy vấn cho dòng dữ liệu Bảng 1 - Tổng quan về các kỹ thuật xử lý truy vấn trên Dòng dữ liệu Kỹ thuật Chỉnh sửa câu truy vấn Chỉnh sửa dữ liệu Kết quả chính xác Kết quả gần đúng Precise Filtering Có Không Có Không Data Merging Không Có Có Không Blind Không Có Không Có Random Không Có Không Có Uniform Không Có Không Có Lấy dữ liệu đồng bộ Semantic Không Có Có Có Sử dụng vị từ Limiting processing Có Không Không Có Punctu -ation Punctuations Không Có Có Không Windo -wing Windowing Có Không Có Không Sampling Không Có Không Có Histograms Không Có Không Có Wavelets Không Có Không Có Sketches Không Có Không Có Micro-cluster based summarization Không Có Không Có Nhóm phương pháp Filter -ing Synop -ses Data Dropping (Load shedding) 5 Mô tả Tinh lọc lại dữ liệu bằng các bộ lọc Kết hợp, gom nhóm dữ liệu Loại bỏ dữ liệu khi thiếu tài nguyên Loại bỏ dữ liệu ngẫu nhiên Giới hạn xử lý trên các phần tử chọn lọc Dựa vào cấu trúc bên trong của dòng dữ liệu để xây dựng và chèn dấu ngắt Sử dụng các mốc thời gian để phân chia dòng dữ liệu Lấy mẫu tập dữ liệu gốc Phân chia dữ liệu theo một trường thành các bucket Phân rã theo hướng phân cấp hàm Biến đổi tuyến tính dữ liệu gốc Sử dụng vector đặc trưng theo thời gian Nghiên cứu bảo vệ tính riêng tư trong xử lý câu truy vấn cho dòng dữ liệu b. Các kỹ thuật xử lý và tối ưu việc truy vấn trên dòng dữ liệu:  Stream Filtering: Precise Filtering, Data Merging, Data Dropping (Blind/Random/Uniform/Semantic/Limiting processing).  Punctuation  Windowing  Synopses: Sampling, Histograms, Wavelets, Sketches, Micro-cluster based summarization. c. Đánh giá, so sánh các điểm yếu, điểm mạnh của các kỹ thuật nói trên. Bảng 1 tổng kết các đặc tính của các loại kỹ thuật kể trên. 2.2. Tìm hiểu các kỹ thuật làm mờ dữ liệu cho dòng dữ liệu a. Tìm hiểu các giải thuật làm mờ dữ liệu dựa trên kỹ thuật k-anonymity:  Stream K-anonYmity (SKY)  Sliding Window Anonymization Framework (SWAF)  Continuously Anonymizing STreaming data via adaptive cLustEring (CASTLE)  Fast Anonymizing Algorithm for Numerical Streaming daTa (FAANST). b. Tìm hiểu ứng dụng xác suất thống kê trong bảo vệ tính riêng tư thông qua một giải thuật. c. Đánh giá, so sánh các điểm yếu, điểm mạnh của các kỹ thuật trên. 2.3. Đề xuất giải pháp bảo vệ tính riêng tư trong xử lý truy vấn trên dòng dữ liệu a. Tìm hiểu các giải thuật lấy mẫu dòng dữ liệu dựa trên reservoir (Reservoir-based Sampling):  Lấy mẫu theo reservoir có kích thước cố định (Fixed Reservoir Sampling).  Lấy mẫu theo reservoir có kích thước thay đổi (Variable Reservoir Sampling). b. Đề xuất kiến trúc cho hệ thống. Kiến trúc đề xuất được minh họa trong Hình 1 với các thành phần cơ bản sau: 6 Nghiên cứu bảo vệ tính riêng tư trong xử lý câu truy vấn cho dòng dữ liệu  Bộ phận “Điều phối đầu vào”: chịu trách nhiệm quản lý, điều phối các phần tử dữ liệu đến liên tục của dòng dữ liệu gốc.  Bộ phận “Lấy mẫu”: chịu trách nhiệm lấy mẫu trên dữ liệu đầu vào theo giải thuật lấy mẫu thiên vị thời gian bằng reservoir có kích thước thay đổi (Variable Reservoir Sampling). Bộ phận này sẽ duy trì một mẫu động cho dòng dữ liệu gốc đang đến liên tục.  Bộ phận “Làm mờ”: chịu trách nhiệm làm mờ các dữ liệu đã được lấy mẫu để che giấu các thông tin riêng tư.  Bộ phận lưu trữ “Mẫu đã làm mờ”: lưu trữ mẫu động đã được làm mờ của dòng dữ liệu. Mẫu này thay đổi theo tình trạng của dòng dữ liệu đến.  Bộ phận “Dữ liệu tĩnh”: lưu trữ các dữ liệu tĩnh cần thiết khác cho việc truy vấn.  Bộ phận “Kế hoạch truy vấn”: là nơi lưu trữ các câu truy vấn được thiết lập sẵn.  Bộ phận “Xử lý truy vấn”: thực hiện các câu truy vấn đã được lập sẵn và lưu trữ trong “Kế hoạch truy vấn” lên các phần tử dữ liệu nằm trong mẫu dữ liệu đã được làm mờ của dòng dữ liệu và các dữ liệu tĩnh có sẵn trên hệ thống.  Bộ phận “Bộ đệm đầu ra”: là nơi chứa các câu trả lời cho các câu truy vấn. Hình 1 - Kiến trúc tổng quan cho giải pháp đề xuất 7 Nghiên cứu bảo vệ tính riêng tư trong xử lý câu truy vấn cho dòng dữ liệu Quy trình hoạt động của hệ thống tuân theo chiều các mũi tên trong Hình 1. Khi các phần tử dữ liệu đến, nó được xử lý bởi bộ phận “Điều phối đầu vào”. Sau đó, dữ liệu được đưa đến bộ phận “Lấy mẫu” và “Làm mờ” để xử lý. Kết quả của việc xử lý này là cấu trúc tóm lược của dòng dữ liệu đã được làm mờ và được lưu trữ tại bộ phận “Lưu trữ mẫu đã làm mờ”. Bộ phận “Xử lý truy vấn” sẽ thực hiện các câu truy vấn được lưu trong “Kế hoạch truy vấn” trên dữ liệu lấy từ các bộ phận “Lưu trữ mẫu đã làm mờ” và “Lưu trữ dữ liệu tĩnh”. Kết quả truy vấn sẽ được đưa đến “Bộ đệm đầu ra” để xuất ra ngoài. c. Xây dựng giải thuật bảo vệ tính riêng tư trong xử lý câu truy vấn trên dòng dữ liệu:  Giải thuật tích hợp Synopses và kỹ thuật làm mờ theo K-Anonymity: Dòng dữ liệu đến sẽ được xử lý bởi giải thuật lấy mẫu để tạo ra một cấu trúc tóm lược (Synopses) động cho dòng dữ liệu gốc. Bảng 2 minh họa mã giả của phương pháp lấy mẫu được xây dựng theo giải thuật lấy mẫu thiên vị thời gian bằng reservoir có kích thước thay đổi (Variable Reservoir Sampling). Trong đó, chúng tôi tích hợp thêm hai thủ tục ADD() và REMOVE(). Đây là hai thủ tục dùng để áp dụng kỹ thuật làm mờ lên mẫu dữ liệu. Hai thủ tục này quản lý việc cập nhật reservoir (qua việc thêm phần tử vào và loại phần tử ra khỏi reservoir) để các phần tử nằm trong reservoir luôn đạt được tiêu chuẩn K-Anonymity. Trong đoạn mã giả có sử dụng một số hàm/thủ tục như sau:  READ_NEXT_ITEM(S): đọc phần tử dữ liệu kế tiếp của dòng dữ liệu.  RANDOM_REAL(a,b): sinh ra một số ngẫu nhiên kiểu số thực thuộc [a,b).  RANDOM_INT(a,b): sinh ra một số ngẫu nhiên kiểu số nguyên thuộc [a,b).  ADD(d,j): thêm phần tử dữ liệu d vào vị trí có chỉ số j của reservoir. Hàm này thuộc giải thuật làm mờ dữ liệu, sẽ được trình bày rõ hơn trong phần kế tiếp.  REMOVE(j): loại bỏ khỏi reservoir phần tử dữ liệu tại chỉ số vị trí j. Hàm này thuộc giải thuật làm mờ dữ liệu, sẽ được trình bày rõ hơn trong phần kế tiếp. 8 Nghiên cứu bảo vệ tính riêng tư trong xử lý câu truy vấn cho dòng dữ liệu Bảng 2 – Mã giả của giải thuật lấy mẫu Tham số đầu vào: Dòng dữ liệu S, kích thước reservoir thật nmax, tham số đặc trưng λ 1. Khởi tạo reservoir ; 2. // giới hạn trên của kích thước reservoir ảo 3. ; // hệ số giảm của 4. 5. ; // giới hạn dưới của ; // số phần tử dữ liệu hiện tại trong reservoir 6. // kích thước hiện tại của reservoir ảo 7. ; // xác suất thêm phần tử dữ liệu vào mẫu 8. WHILE (NOT EOF) DO 9. ; 10. 11. ; IF ( ) THEN 12. 13. ; IF ( ; 15. ; ELSE 17. ; 18. ; 19. // ) THEN 14. 16. // IF ( ) THEN 20. ; 21. 22. ; IF ( ) THEN 23. ; 24. ; 25. 26. END IF; ; 9 // Nghiên cứu bảo vệ tính riêng tư trong xử lý câu truy vấn cho dòng dữ liệu 27. IF ( ) THEN 28. ; 29. ; 30. END IF; 31. END IF; 32. 33. END IF; END IF; 34. END WHILE;  Cây phân cấp đặc trưng hóa dữ liệu (Specialization Tree) Trong giải pháp đề xuất, chúng tôi dựa trên giải thuật SKY để xây dựng hai thủ tục ADD() và REMOVE(). Ý tưởng chính của phương pháp làm mờ này là sử dụng Cây phân cấp đặc trưng hóa dữ liệu (Specialization Tree), gọi tắt là cây SP:  SP là cây có hướng, biểu diễn sự đặc trưng hóa cho các bộ giá trị thuộc tính của các phần tử dữ liệu. Do chúng ta chỉ cần che giấu các thuộc tính quasi-identifier (là các thuộc tính có khả năng làm lộ danh tính cá nhân) nên các nốt trong SP chỉ liên quan đến các thuộc tính quasi-identifier của các phần tử dữ liệu. {  Mỗi thuộc tính quasi-identifier } đều có một cây phân cấp tổng quát hóa miền dữ liệu (Domain Generalization Hierachies) được định nghĩa trước.  Mỗi nốt trong cây SP là một cấu trúc gồm các thông số: o : nhãn của nốt. o : số lượng các phần tử dữ liệu trong reservoir được làm mờ bởi nhãn của nốt này. o : danh sách các chỉ số vị trí của các phần tử trong reservoir được liên kết với nốt này.  Mỗi nốt SP có nhãn từ o là một vector có dạng 〈 DGH . Có một cạnh có hướng từ nốt thỏa 〉, trong đó đến nốt DGH chứa cạnh ( ) 10 được rút ra trong cây SP nếu: ( )DGH . Nghiên cứu bảo vệ tính riêng tư trong xử lý câu truy vấn cho dòng dữ liệu . o  Xét về ý nghĩa, các nốt lá trong cây SP là các nốt cụ thể nhất. Càng lên cao, các nốt càng tổng quát hóa. Nốt gốc có độ tổng quát hóa cao nhất. Hình 2 – Ví dụ về “Cây phân cấp đặc trưng hóa dữ liệu” (SP Tree) Các cây SP và DGHi cần được xây dựng trước. Hình 2 đưa ra một ví dụ minh họa cho cấu trúc của cây SP (trên hình chỉ thể hiện nhãn của từng nốt). Các phần tử dữ liệu của cây SP này gồm 3 thuộc tính là giới tính, tuổi, học vấn. Nhãn của các nốt trong cây SP được sử dụng cho việc làm mờ các phần tử dữ liệu. Giá trị các thuộc tính quasi-identifier của từng phần tử dữ liệu sẽ được thay thế bằng nhãn của một nốt thích hợp trong cây SP. Nhãn đó có thể bằng đúng bộ giá trị thật của các thuộc tính quasi-identifier hoặc có giá trị tổng quát hơn. Chỉ những phần tử dữ liệu nào được làm mờ bởi các nhãn được sử dụng bởi ít nhất k phần tử dữ liệu thì mới có thể được truy xuất bởi bộ phận xử lý câu truy vấn. Nói cách khác, những nhãn có số lượng phần tử dữ liệu liên kết với nó nhỏ hơn k thì những phần tử đó chưa thể được truy xuất bởi bộ phận xử lý câu truy vấn. 11 Nghiên cứu bảo vệ tính riêng tư trong xử lý câu truy vấn cho dòng dữ liệu Mỗi phần tử dữ liệu khi được đưa vào reservoir sẽ có một trong hai trạng thái: trạng thái ẩn và trạng thái hiển thị. Trạng thái ẩn là khi phần tử dữ liệu đó nằm trong reservoir nhưng chưa được làm mờ (do đang chờ tìm được nhãn thích hợp đạt đủ điều kiện K-Anonymity) nên bị ẩn để không thể bị truy xuất bởi bộ phận xử lý câu truy vấn. Trạng thái hiển thị là khi phần tử dữ liệu đó đã được làm mờ thành công và có thể được truy xuất bởi bộ phận xử lý câu truy vấn. Khi một phần tử dữ liệu mới được thêm vào reservoir, mặc định nó sẽ mang trạng thái ẩn. Sau khi được làm mờ thành công, nó sẽ chuyển sang trạng thái hiển thị. Để quản lý việc gán nhãn cho các phần tử dữ liệu trong reservoir, mỗi phần tử dữ liệu trong reservoir sẽ có cấu trúc như sau:   : giá trị thật sự của phần tử dữ liệu.  : nốt trong SP để làm mờ . Thủ tục ADD(): Thủ tục ADD() chịu trách nhiệm làm mờ các phần tử dữ liệu được đưa vào reservoir. Khi một phần tử dữ liệu SP một nốt có nhãn được đưa vào reservoir, ADD() tìm trên cây là tổng quát hóa của giá trị các thuộc tính quasi-identifier của . Đồng thời, để tối thiểu hóa lượng thông tin bị mất khi làm mờ bằng việc tổng quát hóa, nhãn phải là nhãn chi tiết nhất trong các nhãn có thể chọn. Do vậy, việc tìm kiếm nhãn sẽ được thực hiện từ gốc cây SP cho đến khi tìm được nốt có nhãn là nhãn tổng quát hóa chi tiết nhất của . Nếu là một nốt đã được dùng làm mờ cho ít nhất k phần tử dữ liệu, ta lập tức áp dụng và chuyển để làm mờ cho từ trạng thái ẩn thành trạng thái hiển thị. Nếu số lượng phần tử dữ liệu đang được liên kết với bằng k – 1 thì sau khi thêm vào danh sách đó, toàn bộ các phần tử trong danh sách liên kết với đều được áp dụng để làm mờ ngay lập tức và chuyển trạng thái từ ẩn sang hiển thị. Ngược lại hai trường hợp trên, ta chỉ thêm vào danh sách liên kết của và chờ cho đến khi đạt đủ điều kiện K- Anonymity thì sẽ được làm mờ. Đoạn mã giả trong Bảng 3 minh họa cho thủ tục 12 Nghiên cứu bảo vệ tính riêng tư trong xử lý câu truy vấn cho dòng dữ liệu ADD() với 2 tham số đầu vào: là phần tử dữ liệu cần được đưa vào reservoir và được làm mờ, là chỉ số vị trí trong reservoir của . Bảng 3 – Mã giả của thủ tục ADD() trong giải thuật làm mờ ADD (item d, index i) ; 1. 2. ; 3. 4. 5. 6. IF THEN 7. 8. 9. ELSE 10. 11. IF THEN FOR EACH IN DO ; 12. 13. 14. 15. END FOR; END IF; 16. END IF;  Thủ tục REMOVE(): Thủ tục REMOVE() chịu trách nhiệm loại một phần tử dữ liệu khỏi reservoir sao cho các phần tử đang có trạng thái hiển thị trong reservoir vẫn thỏa điều kiện KAnonymity. Khi một phần tử bị loại khỏi reservoir, nếu nốt SP mà nó đang liên kết có số phần tử dữ liệu liên kết giảm xuống thấp hơn k, toàn bộ các phần tử dữ liệu trong danh sách liên kết đó sẽ được làm mờ lên một nốt cha gần nhất đang có sẵn ít nhất 1 phần tử dữ liệu liên kết (tức là nốt sẽ thỏa điều kiện K-Anonymity). Đoạn 13 Nghiên cứu bảo vệ tính riêng tư trong xử lý câu truy vấn cho dòng dữ liệu mã giả trong Bảng 4 minh họa cho thủ tục REMOVE() với một tham số đầu vào là chỉ số vị trí của phần tử dữ liệu cần được loại bỏ khỏi reservoir. Bảng 4 – Mã giả của thủ tục REMOVE() trong giải thuật làm mờ REMOVE (index i) ; 1. 2. ; 3. 4. 5. IF THEN 6. 7. FOR EACH j IN 8. ; DO ; 9. 10. ; 11. ; 12. ; 13. 14. END FOR; 15. END IF; Trong hai đoạn mã giả của thủ tục ADD() và REMOVE() có sử dụng một số hàm/thủ tục như sau:  SEARCH_SP(d): Tìm trên cây SP (bắt đầu từ gốc) cho đến khi tìm được nốt chi tiết nhất có chứa d.  FIND_NEAREST_FATHER(s): Tìm trên cây SP nốt cha gần nhất của s thỏa điều kiện đang có sẵn ít nhất một phần tử dữ liệu liên kết.  ANONYMIZE(i,g): làm mờ phần tử dữ liệu i bằng nhãn g.  ADD_TO_LIST(i,h): thêm chỉ số vị trí i vào danh sách h. 14 Nghiên cứu bảo vệ tính riêng tư trong xử lý câu truy vấn cho dòng dữ liệu  REMOVE_FROM_LIST(i,h): xóa chỉ số vị trí i khỏi danh sách h.  DISPLAY(i): chuyển trạng thái của i từ ẩn thành hiển thị. Để tránh trường hợp xấu nhất có thể xảy ra là một phần tử dữ liệu phải chờ quá lâu tại một nốt SP để được làm mờ, ta có thể bổ sung thêm một hàm D được dùng để kiểm tra xem liệu có phần tử nào phải chờ đợi việc làm mờ quá lâu hay không (vượt ngưỡng δ được quy định trước). Nếu có, phần tử đó sẽ được làm mờ ngay lập tức với nốt cha tổng quát đủ điều kiện K-Anonymity gần với nốt hiện tại nhất. 2.4. Hiện thực demo cho giải pháp đề xuất Để chứng tỏ tính khả thi, khả năng hiện thực hóa và sự hiệu quả so với các giải thuật đang tồn tại, chúng tôi đã hiện thực một chương trình demo giải thuật SKY và giải thuật sử dụng Synopses (giải thuật được xây dựng trong đề tài nghiên cứu này). Chương trình xuất thông báo trong quá trình chạy thông qua giao diện Console và xuất một số kết quả ra file text. Chương trình cho phép chạy hai giải thuật trên cùng một tập dữ liệu. Mỗi giải thuật đều sẽ làm mờ tập dữ liệu đầu vào. Trong quá trình chạy, các bước và thông tin xử lý của từng bước sẽ được hiển thị lên màn hình Console để người dùng tiện theo dõi. Hình 3 thể hiện một phần màn hình Console khi bắt đầu chạy giải thuật SKY. Hình 4 thể hiện một phần màn hình Console khi kết thúc giải thuật SKY với số lượng dữ liệu đã xử lý và thời gian thực thi được hiển thị cuối cùng. Tương tự, Hình 5 và Hình 6 thể hiện màn hình Console khi chạy giải thuật sử dụng Synopses. 15 Nghiên cứu bảo vệ tính riêng tư trong xử lý câu truy vấn cho dòng dữ liệu Hình 3 – Màn hình Console khi bắt đầu chạy giải thuật SKY Hình 4 – Màn hình Console khi kết thúc chạy giải thuật SKY 16 Nghiên cứu bảo vệ tính riêng tư trong xử lý câu truy vấn cho dòng dữ liệu Hình 5 – Màn hình Console khi bắt đầu chạy giải thuật sử dụng Synopses Hình 6 – Màn hình Console khi kết thúc chạy giải thuật sử dụng Synopses 17 Nghiên cứu bảo vệ tính riêng tư trong xử lý câu truy vấn cho dòng dữ liệu Đồng thời trong quá trình một giải thuật đang chạy, bộ phận xử lý truy vấn sẽ thực hiện câu truy vấn cho trước trên những dữ liệu đã được làm mờ để tính ra các giá trị thống kê cần thiết. Các giá trị thống kê tính được trong quá trình chạy sẽ được xuất ra một file text như được minh họa trong Hình 7. Hình 7 – Kết quả xử lý truy vấn tại các thời điểm 2.5. Viết bài báo khoa học cho hội nghị/tạp chí chuyên ngành Bài báo kết quả của đề tài nghiên cứu được đăng trong tạp chí quốc tế với thông tin chi tiết như bên dưới: A. N. T. Nguyen, K. T. Dang, N. Thoai, H. N. Duong, “Preserving Privacy in Data Streams Query Processing on Synopses,” Int. J. Industrial Electronics, Control & Robotics (a selected paper from IES2012), ISSN 2231-4903, vol. 2, no. 1, pp. 22-26, Jan.-Jun. 2012. (Nội dung bài báo được đính kèm trong phần Phụ Lục) 3. Kết quả mới Giải thuật bảo vệ tính riêng tư trong xử lý truy vấn trên dòng dữ liệu bằng phương pháp sử dụng Synopses do chúng tôi đề xuất có kết quả tốt hơn giải thuật SKY cả về mặt lý thuyết và thực nghiệm. 18 Nghiên cứu bảo vệ tính riêng tư trong xử lý câu truy vấn cho dòng dữ liệu 3.1. Đánh giá theo lý thuyết Các giải thuật được đánh giá qua các thông số:  Hiệu quả của việc xử lý câu truy vấn:  Thời gian xử lý: ∑ Qua tính toán, ta có được: ∑ ( ) ∑ ( (Trong đó: Do ) ) là một hằng số, còn N là đại diện cho lượng dữ liệu đến rất lớn, vô định, không thể xác định trước, nên thời gian xử lý của giải thuật chúng tôi đề xuất tối ưu hơn.  Tài nguyên sử dụng: Trong giải thuật chúng tôi đề xuất, việc sử dụng cấu trúc tóm lược (Synopses) giúp duy trì một bản tóm tắt nhỏ gọn của dòng dữ liệu trong bộ nhớ để cho việc xử lý truy vấn được nhanh chóng. Ngược lại, việc xử lý trên dữ liệu được làm mờ bởi SKY phải được thực hiện trên toàn dòng dữ liệu, nên chắc chắn đòi hỏi một lượng bộ nhớ rất lớn để lưu giữ, thậm chí là vượt ngoài dung lượng tài nguyên sẵn có của hệ thống bởi dung lượng khổng lồ là một bản chất đặc trưng của dòng dữ liệu. Cụ thể, SKY phải xử lý truy vấn trên lượng dữ liệu không biết trước số lượng, trong khi giải thuật của chúng tôi xử lý trên một mẫu có kích thước tối đa với là một hằng số. 19 Nghiên cứu bảo vệ tính riêng tư trong xử lý câu truy vấn cho dòng dữ liệu  Chất lượng của kết quả truy vấn: Trong cả hai giải thuật, dữ liệu được dùng để xử lý truy vấn đều là dữ liệu đã được làm mờ bằng cách tổng quát hóa, nên kết quả truy vấn đều là dạng kết quả gần đúng. Tuy nhiên do số lượng dữ liệu để xử lý truy vấn trong SKY được giữ nguyên so với dữ liệu gốc nên kết quả xử lý truy vấn của SKY chắc chắn sẽ chính xác hơn kết quả của giải pháp do chúng tôi đề xuất. Tuy nhiên trong phần nghiên cứu về giải thuật lấy mẫu, tác giả của giải thuật lấy mẫu đã nghiên cứu thực nghiệm và cho thấy rằng sai số của kết quả truy vấn trên mẫu nằm trong giới hạn cho phép và phù hợp với dạng ứng dụng thống kê, tổng hợp. 3.2. Đánh giá theo thực nghiệm Hai giải thuật được chạy trên cùng tập dữ liệu mẫu Employees của MySQL. Thông tin cụ thể về tập dữ liệu và các thông số dùng để chạy thực nghiệm:  Schema: emp_no, first_name, last_name, birth_date, gender, hire_date, dept_name, title, salary.  Các thuộc tính định danh bị bỏ đi: emp_no, first_name, last_name.  Các thuộc tính tựa-định danh (quasi-identifier): birth_date, gender, hire_date, dept_name, title.  Thuộc tính chứa thông tin nhạy cảm và không bị làm mờ: salary.  Tổng số lượng dữ liệu: 265,332 dòng. Trong đó, 20,000 dòng được sử dụng làm dữ liệu để xây dựng cây SP. 245,332 dòng còn lại được dùng để mô phỏng dòng dữ liệu đến.  Tham số k: lần lượt là 300, 400, 500.  Xác suất lấy mẫu sử dụng cho giải thuật của chúng tôi: 1.  Thời gian ngưng giữa các lần truy vấn: 500 mili giây.  Câu truy vấn: SELECT AVG(salary) FROM AnonymizedData  Kết quả chính xác của câu truy vấn trên: 71998.5715 20