Luận văn Một số thuật toán đảm bảo tính riêng tư trong hệ thống LBS

Hình 2-6 b) • Thu hẹp bán kính r thành r’ với . (Hình 2-6 c) Hình 2-6: Mở rộng vị trí từ vùng sang vùng [5] 2.3.1.3 Các dịch vụ về vị trí gần nhau Dịch vụ về vị trí gần nhau (Proximity-based Services) là loại dịch vụ dựa vào vị trí và thông tin so sánh giữa một ngƣỡng định trƣớc với khoảng cách giữa ngƣời sử dụng dịch vụ với các thực thể (di chuyển) khác [15]. Dịch vụ Friend-Finder là một loại dịch vụ thuộc nhóm dịch vụ này. Với loại dịch vụ nhƣ r r’ r’ r d θ a ) b ) c ) 30 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên vậy, ngoài việc cần bảo vệ tính riêng tƣ của ngƣời sử dụng dịch vụ khỏi kẻ tấn công, nhà cung cấp dịch vụ, mà còn chống lại cả đối tƣợng mà mình cần so sánh vị trí. Để dịch vụ về vị trí gần nhau cung cấp đƣợc dịch vụ cho khách hàng thì ngƣời sử dụng dịch vụ phải cung cấp vị trí của mình cho nhà cung cấp LBS. Nhƣ vậy, các hệ thống bảo vệ tính riêng tƣ cho loại dịch vụ này phải đảm bảo đáp ứng đƣợc yêu cầu tối thiểu về tính riêng tƣ cho ngƣời sử dụng và hạn chế việc tiết lộ vị trí của ngƣời dùng càng ít càng tốt. Hƣớng tiếp cận của bài báo [15] đƣa ra một hƣớng giải quyết cho bài toán bảo vệ tính riêng tƣ của ngƣời sử dụng dịch vụ về vị trí gần nhau; ngƣời sử dụng dịch vụ vẫn có thể xác định vị trí của các đối tƣợng gần mình mà vẫn đảm bảo tính riêng tƣ. Hình 2-7: Xác định điểm lân cận của A [15] Trong hƣớng tiếp cận [15], mỗi ngƣời sử dụng A sẽ có một ngƣỡng lân cận A để xác định các đối tƣợng lân cận mình. Nếu khoảng cách Eulic của 2 điểm A và B nhỏ hơn A thì điểm B gọi là lận cận của A [15]. A B d L A ( i ) L B ( j ) A a) Điểm B gần với điểm A c) Điểm B có thể gần với điểm A A B L B ( j ) L A ( i ) A b) Điểm B không gần với điểm A A B L B ( j ) A D L A ( i ) 31 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên Để đảm bảo tính riêng tƣ về vị trí của ngƣời sử dụng, thay vì phải sử dụng tọa độ vị trí địa lý thực của ngƣời A, ngƣời B thì từng tọa độ chính xác A, B sẽ đƣợc mở rộng thành vùng LA(i) và LB(j). Trong Hình 2-7, mô tả phƣơng pháp xác định xem điểm B có là vùng lân cận của điểm A không thông qua 2 vùng mở rộng LA(i) và LB(j). • Hình 2-7 (a): Nếu khoảng cách xa nhất D của 2 vùng mở rộng LA(i) và LB(j) nhỏ hơn ngƣỡng lân cận A của A thì điểm B sẽ là lân cận của A. • Hình 2-7 (b): Nếu khoảng cách ngắn nhất d của 2 vùng mở rộng LA(i) và LB(j) vẫn còn lớn hơn ngƣỡng lân cận A của A thì điểm B sẽ không là lân cận của A. • Hình 2-7 (c): Ngƣợc lại cả hai trƣờng hợp (a) và (b), nhà cung cấp dịch vụ LBS không thể xác định chính xác là điểm B có gọi là lân cận của A không, vì vậy, nhà cung cấp dịch vụ LBS chỉ khẳng định là điểm B có thể là lân cận của A. 2.3.2 Kỹ thuật che giấu không gian 2.3.2.1 Nhóm giải pháp k-anonymity Kỹ thuật che giấu không gian (Spatial Cloaking) của ngƣời sử dụng dịch vụ LBS trong công trình [10] đã đề nghị sử dụng thông tin vị trí của k-nặc danh (k-anonymous Location Information). Định nghĩa 1: Tính nặc danh (anonymity) trong vấn đề bảo vệ tính riêng tƣ là trạng thái không thể nào nhận biết đƣợc bên trong một tập các đối tƣợng bị theo dõi (anonymity set). 32 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên Định nghĩa 2: Một đối tƣợng đƣợc xem là k-anonymous đối với thông tin về vị trí khi và chỉ khi thông tin vị trí đại diện cho đối tƣợng đó không thể nào phân biệt đƣợc với thông tin vị trí của ít nhất k-1 đối tƣợng khác. Theo đề xuất của công trình [10], thay vì mỗi lần giao dịch với nhà cung cấp LBS, ngƣời sử dụng phải gửi thông tin vị trí chính xác của mình (x0, y0) thì thông tin không gian của ngƣời sử dụng sẽ bị che giấu, cụ thể là thông tin không gian sẽ là ([x1, x2], [y1, y2], [t1, t2]); trong đó, [x1, x2] và [y1, y2] mô tả một vùng 2 chiều có chứa (x0, y0), [t1, t2] là khoảng thời gian mà ngƣời dùng vẫn còn nằm trong vùng 2 chiều trên. Nhƣ vậy, một vị trí cho một đối tƣợng đƣợc xem là k- anonymous khi vị trí này không chỉ mô tả vị trí của đối tƣợng cần quan sát mà còn mô tả cả vị trí của k-1 đối tƣợng khác. Nói cách khác, tại cùng 1 thời điểm xem xét vị trí của ngƣời sử dụng thì vị trí đó đƣợc mở rộng ra một vùng có chứa k-1 ngƣời sử dụng khác. Hình 2-8: k-anonymity (k=10) Với k = 10 thì vị trí chính xác của ngƣời sử dụng sẽ đƣợc mở rộng ra thành phạm vi sao cho có chứa 10 ngƣời sử dụng dịch vụ tại cùng thời điểm. Vậy vị trí chính xác của ngƣời sử dụng dịch vụ đƣợc che giấu trong phạm vi vị trí của 9 ngƣời khác cùng sử dụng dịch vụ. Nếu k càng lớn thì tập các đối tƣợng theo dõi sẽ càng lớn, vùng mở rộng cho một vị trí càng rộng, do đó tính che giấu thông tin vị trí càng cao. 33 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên Để tính vùng diện tích cho giải pháp k-anonymity có nhiều thuật toán đã đƣợc đề xuất, trong đó có 3 thuật toán chính là Grid, Interval Cloaking, và nnASR 2.3.2.2 Thuật toán Grid Ý tƣởng: sắp xếp các ngƣời dùng (user) dựa trên vị trí của họ theo một chiều không gian, rồi phân chia thành các tập user bằng nhau. Sau đó, lại sắp xếp phân chia tập user chứa user gửi yêu cầu dịch vụ cần đƣợc bảo vệ (isuser), theo một chiều không gian khác. Tập user nhận đƣợc sau cùng chứa ít nhất k user sẽ đƣợc sử dụng để tìm vùng bao nhỏ nhất để trả về. Thực hiện: Giải thuật chia tập user thành các tập con qua hai bƣớc. - Bước 1: các user đƣợc sắp xếp dựa trên vị trí của họ theo các trục x, rồi đến trục y, và theo ID nếu vẫn còn trùng nhau. Tập các user có thứ tự này sẽ đƣợc chia thành các block gồm các user liên tiếp nhau, mỗi block có cùng số user, ngoại trừ block cuối cùng có thể chứa nhiều user hơn những block trƣớc nó. Chỉ các user cùng block với isuser mới đƣợc xem xét ở bƣớc thứ hai. - Bước 2: các user đƣợc sắp xếp dựa trên vị trí của họ theo trục y, rồi trục x, cuối cùng là ID. Sau khi sắp xếp xong, các user lại đƣợc chia ra tƣơng tự nhƣ bƣớc 1. Sau cùng, tập user cùng block với isuser đƣợc trả về. Minh họa: 34 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên Hình 2-9: Minh họa giải thuật Grid Giả sử i là ngƣời phát ra query, yêu cầu k = 2. Tập AS sẽ chứa định danh của tất cả các ngƣời dùng (20 phần tử). Đầu tiên các phần tử trong AS sẽ đƣợc sắp xếp theo giá trị tọa độ x của các phần tử. Số block đƣợc chia ra sẽ là = 3, số ngƣời dùng trong mỗi block là 20/3 = 6. Ngƣời dùng i sẽ thuộc block 1. Với block 1 gồm 6 phần tử, giải thuật lại tiếp tục sắp xếp các phần tử trong đó theo giá trị tọa độ y của các phần tử. Sau đó chia block 1 thành 3 block dựa trên thứ tự sắp xếp có đƣợc. Ngƣời dùng i sẽ thuộc block 1. Và block này sẽ đƣợc sử dụng để trả về. Algorithm: Grid Input: một request gốc, một số nguyên dương k Output: tập các người dùng chứa ít nhất k phần tử và có chứa người phát ra request r. Method: 1. Mảng AS được khởi tạo với ID của tất cả tập user (I). 2. nob≔ {Tính số block} 3. if (nob ≤ 1) return block chứa tất cả các ID của tập user (I). 35 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 4. for (dim ∈ {x, y}) do 5. if (dim = x) then 6. Sắp xếp mảng AS theo trục x, sau đó đến trục y, cuối cùng là ID của user 7. else 8. Sắp xếp mảng AS theo trục y, sau đó đến trục x, cuối cùng là ID của user 9. endif 10. issuerIndex ≔chỉ số của AS[issuerIndex] = issuer(r) 11. upb ≔ {số user trên mỗi block} 12. ibi ≔ {vị trí của block chứa isuser} 13. if (|AS| mod nob = 0 OR ibi < nob – 1) then 14. start ≔ ibi.upb 15. end ≔ start + upb – 1 16. else 17. start ≔ (nob – 1) . upb 18. end ≔ |AS| – 1 19. endif 20. AS ≔ AS[start]AS[end] 21. endfor 22. if (|AS| ≥ k) then 23. returntập ID của user trong mảng AS 24. else 25. return null 26. end if 2.3.2.3 Thuật toán Interval Cloaking Ý tƣởng: mục tiêu là tổng quát hóa yêu cầu dịch vụ theo chiều không gian hoặc thời gian. Đối với chiều không gian, lặp lại việc chia nhỏ vùng bao toàn bộ không gian vị trí. Tại mỗi bƣớc lặp, vùng hiện thời qprev đƣợc chia thành bốn vùng bằng nhau. Nếu có ít hơn k user nằm trong vùng q mà chứa issuer thì qprev đƣợc trả về. Ngƣợc lại, quá trình lặp tiếp tục xem q là vùng hiện thời. Đối 36 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên với chiều thời gian, đầu tiên tổng quát vị trí không gian (theo ý tƣởng trên) đến mức mong muốn thỏa giá trị độ phân giải (resolution) đƣợc truyền vào. Sau đó, chờ đến khi có đủ k user đi vào vùng không gian đƣợc tổng quát, trả về vùng này cùng với khoảng thời gian [t1, t2]. Thực hiện: Dƣới đây là phƣơng pháp tính vùng diện tích với chiều không gian cho k-anonymity với giải thuật Interval Cloaking[10]: Hình 2-10: Quy trình chọn ra vùng 5-anonymity cho điểm tô đỏ Với phƣơng pháp này, đầu tiên tính vùng không gian chứa tất cả ngƣời đang sử dụng dịch vụ, sau đó chia làm bốn vùng không gian này và chọn vùng không gian nhỏ hơn, có chứa vị trí chính xác của ngƣời sử dụng. Tiếp tục chia nhỏ vùng không gian đã chọn cho đến khi vùng không gian cuối cùng có chứa k ngƣời sử dụng dịch vụ. Algorithm: Interval Cloaking 1. Khởi tạo các vùng không gian q và qprev 2. Khởi tạo vùng không gian qcurrent là phần tư của vùng không gian q có chứa isuser (người yêu cầu dịch vụ cần được bảo vệ) 3. Khởi tạo p là vị trí của isuser 37 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 4. Nếu số lượng user nằm trong qcurrent<kmin thì trả về vùng qprev là vùng trước khi chia nhỏ lần cuối cùng 5. Chia vùng không gian q thành 4 góc phần tư bằng nhau 6. qprev := q 7. q := phần tư chứa p 8. Xóa các user nằm ngoài q trong qcurrent 9. Lặp lại từ bước 2 Nhận xét: Hƣớng tiếp cận [10] đã đƣa ra giải pháp che giấu không gian vị trí của ngƣời sử dụng dịch vụ dựa trên vị trí của k-1 ngƣời sử dụng dịch vụ xung quanh tại cùng thời điểm. Tuy nhiên, vùng không gian mở rộng cho vị trí của ngƣời sử dụng sẽ rất nhỏ nếu nhƣ vị trí của ngƣời dùng nằm trong một vùng có mật độ ngƣời sử dụng quá cao (quảng trƣờng, sân vận động,). Ngƣợc lại, trong vùng có mật độ ngƣời sử dụng quá thấp (sa mạc, khu vực thƣa dân cƣ, ) thì vùng không gian mở rộng sẽ cực kỳ lớn để đảm bảo tính riêng tƣ cho vị trí thực của ngƣời dùng, đồng thời, sẽ làm tăng số lƣợng kết quả truy vấn dịch vụ lên rất lớn tƣơng ứng với vùng không gian truy vấn lớn. Bên cạnh đó, mặc dù kẻ tấn công không thể xác định đƣợc vị trí chính xác của ngƣời dùng nhƣng nếu kẻ tấn công theo dõi quá trình truy vấn dữ liệu nhiều lần liên tục thì sẽ biết đƣợc lộ trình di chuyển của ngƣời sử dụng dịch vụ [8]. Hình 2-11: Theo dõi quá trình truy vấn dữ liệu Vùng xám chính là vùng mở rộng cho vị trí chính xác của ngƣời sử dụng, nhƣng quá trình thay đổi vị trí chính xác của ngƣời dùng thì không làm thay đổi nhiều về vùng mở rộng. 38 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 2.3.2.4 Thuật toán nearest neighbor ASR (nnASR) Ý tƣởng: tạo ra vùng bao chứa ngƣời tạo ra yêu cầu dịch vụ (isuser) có kích thƣớc nhỏ nhất có thể, bằng cách sửa lại phƣơng pháp làm mờ đơn giản nhất (naïve method - tìm k ngƣời dùng gần nhất). Thực hiện: với ngƣời dùng u cho trƣớc, đầu tiên xác định tập S chứa u và k – 1 ngƣời dùng gần u nhất. Từ S, chọn ngẫu nhiên ngƣời dùng u’. Vì vậy, xác suất để chọn đúng ngƣời dùng u ban đầu là 1/k. Sau đó tính toán tập S’ chứa u’ và k – 1 ngƣời dùng gần u’ nhất. Kế tiếp, tìm tập S’’ = S’⋃ {u}. Cuối cùng, tìm vùng bao hình chữ nhật hoặc hình tròn chứa hết vị trí các ngƣời dùng trong tập S’’ trên, rồi trả về kết quả. Hình 2-12: Minh họa giải thuật nnASR Giả sử U1 phát ra request với k = 3. Đầu tiên, hai ngƣời dùng gần nhất với U1 đƣợc tìm để tạo ra tập 3-ASR cho U1 là S0 = {U1, U2, U3}. Sau đó, giải thuật sẽ chọn ngẫu nhiên một ngƣời dùng trong ba ngƣời dùng thuộc S0. Giả sử đó là U3. Vùng 3-ASR của U3 đƣợc tìm ra là tập các ngƣời dùng S1 = {U3, U4, U5}. Tập ngƣời dùng S đƣợc xây dựng theo công thức S = S1⋃ {U1} = {U1, U3, U4, U5}. Tập này đƣợc dùng để tạo ra kết quả trả về là vùng bao (dạng hình tròn hoặc hình chữ nhật) bao phủ tất cả các ngƣời dùng trong S. Algorithm: nnASR Input: một người dùng và một số nguyên dương k 39 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên Output: tập các người dùng chứa ít nhất k phần tử và chứa người dùng ban đầu Method: 1. S ≔ {u} ⋃ {ui|uilà 1 trong k – 1 phần tử gần nhất của u} 2. Chọn ngẫu nhiên u’ ∈ S 3. S’ ≔ {u’} ⋃ {uj|ujlà 1 trong k – 1 phần tử gần nhất của u’} 4. S’’ ≔ S’ ⋃ {u} 5. return k-ASR of S’’ 2.3.3 Kỹ thuật làm rối thông tin (obfuscation technique) Nhằm bảo vệ tính riêng tƣ cho vị trí của ngƣời sử dụng dịch vụ, kỹ thuật làm rối thông tin vị trí (obfuscation technique) đã đƣợc đề xuất trong các công trình [8], [9]. Ý tƣởng chính của hƣớng tiếp cận này là trộn thêm các thông tin giả vào thông tin vị trí thật của ngƣời sử dụng trƣớc khi gửi toàn bộ thông tin thật và giả đến nhà cung cấp LBS. Với phƣơng pháp này, kẻ tấn công không xác định đƣợc thông tin nào trong số các thông tin gửi đi là của ngƣời sử dụng dịch vụ. Công trình [8] đề xuất hƣớng giải quyết là phát sinh các thông tin nhiễu (vị trí sai) và gửi đồng thời với vị trí thật của ngƣời sử dụng trong mỗi lần gửi thông tin yêu cầu truy vấn dịch vụ đến nhà cung cấp LBS. Hình 2-13: Quy trình hoạt động của hệ thống sử dụng kỹ thuật Dummy [8] 40 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên Lx = (Xx, Yx) là dữ liệu vị trí x của ngƣời sử dụng (vị trí này đƣợc ký hiệu là dấu chấm đen hình tròn trên hình). Thông điệp yêu cầu S gửi đến nhà cung cấp LBS gồm có các thông tin sau : Với u là định danh (ID) của ngƣời sử dụng, là tập các vị trí gửi đến LBS (trong đó, có m-1 vị trí giả đƣợc phát sinh ngẫu nhiên và 1 vị trí thật của ngƣời dùng). Khi nhà cung cấp dịch vụ nhận đƣợc thông điệp S thì sẽ phản hồi lại thông điệp R chứa tập kết quả tƣơng ứng với tập vị trí . Khi ngƣời dùng nhận đƣợc tập kết quả R thì chỉ ngƣời sử dụng biết đƣợc kết quả Dinào là đúng với vị trí thật của mình. Nhƣ vậy, nếu kẻ tấn công có theo dõi quá trình truy vấn dữ liệu thì với hƣớng tiếp cận sử dụng kỹ thuật phát sinh các thông điệp giả có thể làm cho việc suy đoán vị trí trở nên khó khăn. Hình 2-14: Chống theo dõi quá trình truy vấn dữ liệu [8] Bên cạnh đề xuất mô hình bảo vệ tính riêng tƣ về vị trí cho ngƣời sử dụng LBS, công trình [8] còn đề xuất 2 thuật toán phát sinh thông điệp giả ngẫu nhiên MN (Moving in a Neighborhood) và MLN (Moving in a Limited Neighborhood). Để kiểm soát các thông điệp giả đƣợc phát sinh ra (số lƣợng phát sinh cũng nhƣ vị trí phát sinh), công trình [9] đã đề nghị 2 thuật toán khác phát sinh 41 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên thông điệp dựa vào mô hình lƣới (virtual Grid) và dựa trên mô hình tròn (virtual circle) trong hệ thống PAD (Private-Area Aware Dummy). Hình 2-15: Phát sinh thông điệp giả dựa trên mô hình Circle [9] Hình 2-16: Phát sinh thông điệp g