1
..

ĐẠI HỌC THÁI NGUYÊN
TRƢỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THƠNG

LÊ HỒNG LONG

MỘT SỐ THUẬT TỐN ĐẢM BẢO TÍNH RIÊNG TƢ
TRONG HỆ THỐNG LBS

LUẬN VĂN THẠC SĨ CƠNG NGHỆ THƠNG TIN

Thái Ngun - 2014
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên

/>

2

MỤC LỤC
MỤC LỤC ............................................................................................................. 1
DANH MỤC CÁC TỪ VIẾT TẮT ...................................................................... 5
DANH MỤC HÌNH ẢNH .................................................................................... 7
PHẦN MỞ ĐẦU ................................................................................................. 10
CHƢƠNG I: TỔNG QUAN VỀ LOCATION BASED SERVICES ................. 13
1.1 Định nghĩa Location Based Services ......................................................... 13
1.2 Thành phần trong LBS ............................................................................... 14
1.3 Ứng dụng của LBS ..................................................................................... 15
1.4 Hệ tọa độ địa lý .......................................................................................... 16
1.5 Tính khoảng cách giữa các tọa độ địa lý.................................................... 18

1.6 Tổng quan về tính riêng tƣ trong LBS ....................................................... 19
1.6.1 Tính riêng tƣ......................................................................................... 19
1.6.2 Ngữ cảnh – Tính riêng tƣ trong mơi trƣờng ngữ cảnh động ............... 20
1.7 Nguy cơ bảo mật tính riêng tƣ trong LBS ................................................. 21
CHƢƠNG II: MỘT SỐ THUẬT TOÁN VÀ KỸ THUẬT BẢO VỆ TÍNH
RIÊNG TƢ CHO LBS ........................................................................................ 23
2.1 Tổng quan về kiến trúc hệ thống bảo vệ tính riêng tƣ ............................... 23
2.2 Các nhóm kỹ thuật bảo vệ tính riêng tƣ ..................................................... 25
2.3 Thuật tốn và kỹ thuật bảo vệ tính riêng tƣ ............................................... 27
2.3.1 Kỹ thuật mở rộng câu truy vấn ............................................................ 27
2.3.1.1 Mở rộng vị trí tọa độ thành vị trí vùng .......................................... 27
2.3.1.2 Mở rộng vị trí vùng thành vị trí vùng khác ................................... 28
2.3.1.3 Các dịch vụ về vị trí gần nhau ....................................................... 29
2.3.2 Kỹ thuật che giấu khơng gian .............................................................. 31
2.3.2.1 Nhóm giải pháp k-anonymity ........................................................ 31
2.3.2.2 Thuật toán Grid .............................................................................. 33
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên

/>

3

2.3.2.3 Thuật toán Interval Cloaking ......................................................... 35
2.3.2.4 Thuật toán nearest neighbor ASR (nnASR) .................................. 38
2.3.3 Kỹ thuật làm rối thông tin (obfuscation technique) ............................. 39
2.3.3.1 Sinh vật giả .................................................................................... 42
2.3.3.2 Thuật toán di chuyển trong một vùng lân cận ............................... 42
2.3.3.3 Thuật toán di chuyển trong một vùng giới hạn lân cận ................. 43
2.4 Một số mơ hình tấn cơng tính riêng tƣ và phƣơng pháp chống ................. 45
...................... 46

2.4.1.1 Location distribution attack ........................................................... 46
2.4.1.2 Phƣơng pháp chống tấn công......................................................... 47
2.4.1.3 Thuật toán CliqueCloak ................................................................. 48
r ..................... 52
2.4.2.1 Maximum movement boundary..................................................... 52
2.4.2.2 Kỹ thuật Patching .......................................................................... 53
2.4.2.3 Kỹ thuật Delaying .......................................................................... 53
2.4.2.4 So sánh độ hiệu quả giữa patching và delaying ............................ 54
2.4.2.5 Thuật toán IcliqueCloak ................................................................ 56
................................... 58
2.4.3.1 Querry Tracking Attack ................................................................. 58
2.4.3.2 Giải pháp để ngăn chặn sự tấn cơng .............................................. 60
2.4.3.3 Thuật tốn m-InvariantCloak......................................................... 61
CHƢƠNG III: CHƢƠNG TRÌNH MƠ PHỎNG ............................................... 65
3.1 Các cơng nghệ đã sử dụng ......................................................................... 65
3.1.1 Lập trình web ....................................................................................... 65
3.1.1.1 Sơ lƣợc về .Net Framework ........................................................... 65
3.1.1.2 Giới thiệu về ASP.Net ................................................................... 66
3.1.1.3 SQL và hệ quản trị cơ sở dữ liệu SQL Server ............................... 67
3.1.2 Google Maps API ................................................................................ 67
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên

/>

4

3.1.2.1 Google Maps Javascript API v3 .................................................... 68
3.1.2.2 Google Maps API Web Services ................................................... 68
3.1.2.3 Google Maps Android API v2 ....................................................... 69
3.1.3 Xây dựng ứng dụng trên di động ......................................................... 69

3.1.3.1 Ngơn ngữ lập trình Java ................................................................. 69
3.1.3.2 Hệ điều hành Android .................................................................... 70
3.2 Xây dựng mơ hình thử nghiệm .................................................................. 71
3.2.1 Phân tích lựa chọn mơ hình ................................................................. 71
3.2.2 Thiết kế hệ thống ................................................................................. 72
3.2.2.1 Mơ hình hệ thống ........................................................................... 72
3.2.2.2 Biểu đồ Ca sử dụng (Use case) của hệ thống ................................ 75
3.2.2.3 Biểu đồ triển khai hệ thống............................................................ 77
3.2.3 Xây dựng hệ thống ............................................................................... 78
3.2.3.1 Ứng dụng cho ngƣời dùng cuối ..................................................... 78
3.2.3.2 Ứng dụng quản trị hệ thống ........................................................... 80
KẾT LUẬN ......................................................................................................... 83
TÀI LIỆU THAM KHẢO ................................................................................... 85

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên

/>

5

DANH MỤC CÁC TỪ VIẾT TẮT
STT Từ viết tắt
1

3G

2

4G


Tiếng Anh

Tiếng Việt

Third-generation

Công nghệ truyền

technology

thông không dây thế hệ thứ ba

Fourth-generation

Công nghệ truyền

technology

thông không dây thế hệ thứ tƣ
Tập hợp hƣớng đối tƣợng các

3

ADO.Net

ActiveX Data Objects. Net thƣ viện cho phép tƣơng tác
với nguồn dữ liệu
Application Program

4


API

5

ASP

6

CSDL

7

GIS

8

GPRS

9

GPS

10

HTML

11

J2EE


Java Enterprise Edition

12

JSON

JavaScript Object Notation

Interface

Giao diện lập trình ứng dụng

Active Server Pages
Cơ sở dữ liệu
Geographic Information
System
General Packet Radio
Service

Hệ thống thông tin địa lý

Dịch vụ vô tuyến gói tổng hợp

Global Positioning System Hệ thống định vị tồn cầu
HyperText Markup

Ngơn ngữ đánh dấu siêu văn

Language


bản

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên

Nền tảng lập trình dành cho
việc phát triển ứng dụng
Một kiểu dữ liệu
trong JavaScript

/>

6

13

LBA

14

LBS

15

MBR

16

MMB


17

OOP

18

PDA

19

RDBMS

20

SP

21

SQL

Location-based

Ứng dụng có sử dụng thơng

Application

tin vị trí

Location-based Services


Dịch vụ dựa trên vị trí địa lý

Minimum Boundary
Rectangle

Hình chữ nhật bao nhỏ nhất

Maximum Movement

Vùng bao vị trí chính xác của

Boundary

ngƣời dùng

Object-oriented
programming
Personal Digital Assistant

Lập trình hƣớng đối tƣợng
Thiết bị kỹ thuật số hỗ trợ cá
nhân

Relational Database

Hệ thống quản trị cơ sở dữ

Management System

liệu quan hệ


Service Provider

Nhà cung cấp dịch vụ

Structured Query

Ngôn ngữ truy vấn mang tính

Language

cấu trúc

Transmission Control
22

TCP/IP

Protocol/Internet protocol

Bộ giao thức liên mạng

suite
23

WLAN

24

WORA


Wireless local area
network

Mạng cục bộ không dây

“Write once, Run

“Viết 1 lần, sử dụng ở bất kỳ

anywhere”

đâu”

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên

/>

7
DANH MỤC HÌNH ẢNH
Hình 1-1: LBS là sự kết hợp của nhiều cơng nghệ [4]........................................ 13
Hình 1-2: Các thành phần cơ bản của LBS ......................................................... 14
Hình 1-3: Một số phân loại của các ứng dụng LBS [16] .................................... 16
Hình 1-4: Bản đồ Trái Đất với vĩ tuyến (ngang) và kinh tuyến (dọc) ................ 18
Hình 1-5: Các kiểu ngữ cảnh khác nhau theo Nivala(2003) ............................... 20
Hình 2-1: Kiến trúc khơng hợp tác [12] .............................................................. 23
Hình 2-2: Kiến trúc tập trung [12] ...................................................................... 24
Hình 2-3: Kiến trúc ngang hàng [12] .................................................................. 25
Hình 2-4: Quy trình hoạt động của hệ thống Cloaking Agent [14] .................... 28
Hình 2-5: Vị trí thật và vị trí bị che giấu ............................................................. 28

Hình 2-6: Mở rộng vị trí từ vùng sang vùng [5] ................................................. 29
Hình 2-7: Xác định điểm lân cận của A [15] ...................................................... 30
Hình 2-8: k-anonymity (k=10) ............................................................................ 32
Hình 2-9: Minh họa giải thuật Grid..................................................................... 34
Hình 2-10: Quy trình chọn ra vùng 5-anonymity cho điểm tơ đỏ ...................... 36
Hình 2-11: Theo dõi quá trình truy vấn dữ liệu .................................................. 37
Hình 2-12: Minh họa giải thuật nnASR .............................................................. 38
Hình 2-13: Quy trình hoạt động của hệ thống sử dụng kỹ thuật Dummy [8] ..... 39
Hình 2-14: Chống theo dõi quá trình truy vấn dữ liệu [8] .................................. 40
Hình 2-15: Phát sinh thơng điệp giả dựa trên mơ hình Circle [9]....................... 41
Hình 2-16: Phát sinh thơng điệp giả dựa trên mơ hình Grid [9] ......................... 41
Hình 2-17: Minh họa 2 giải thuật sinh vật giả .................................................... 42
Hình 2-18: Phân bố user ...................................................................................... 47
Hình 2-19: Vùng giới hạn ................................................................................... 48
Hình 2-20: Vùng làm mờ .................................................................................... 48
Hình 2-21: Đồ thị giới hạn .................................................................................. 49
Hình 2-22: Đồ thị l-clique ................................................................................... 49
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên

/>

8

Hình 2-23: Maximum movement boundary........................................................ 52
Hình 2-24: Kỹ thuật Patching ............................................................................. 53
Hình 2-25: Kỹ thuật Delaying ............................................................................. 54
Hình 2-26: Đồ thị so sánh chất lƣợng và tính riêng tƣ của 3 loại kỹ thuật ......... 55
Hình 2-27: Đồ thị so sánh thời gian và vận tốc tối đa của 3 loại kỹ thuật .......... 55
Hình 2-28: Thời gian cloaking trung bình .......................................................... 57
Hình 2-29: Bảng thơng tin cƣ dân ....................................................................... 59

Hình 2-30: Bảng thơng tin suy đốn ................................................................... 59
Hình 2-31: Vùng làm mờ 3-anonimity ................................................................ 60
Hình 2-32: Mơ hình 3-anonymity, 2-diversity, 2-invarianve ............................. 61
Hình 3-1: Thành phần trong các phiên bản .NET Framework (2005 - 2010) .... 66
Hình 3-2: Mơ hình hệ thống mơ phỏng............................................................... 74
Hình 3-3: Biểu đồ Ca sử dụng của tác nhân Ngƣời dùng ................................... 75
Hình 3-4: Biểu đồ Ca sử dụng của tác nhân Ứng dụng Client ........................... 76
Hình 3-5: Biểu đồ Ca sử dụng của tác nhân Quản trị viên ................................. 76
Hình 3-6: Biểu đồ Ca sử dụng của tác nhân Dịch vụ Server .............................. 76
Hình 3-7: Biểu đồ triển khai hệ thống................................................................. 77
Hình 3-8: Giao diện khởi động ứng dụng ........................................................... 78
Hình 3-9: Danh sách các danh mục trong ứng dụng ........................................... 78
Hình 3-10: Giao diện mẫu tìm kiếm địa điểm .................................................... 78
Hình 3-11: Giao diện hiển thị kết quả tìm kiếm ................................................. 78
Hình 3-12: Giao diện mẫu thiết lập vị trí vật giả ................................................ 79
Hình 3-13: Giao diện mẫu cấu hình ứng dụng .................................................... 79
Hình 3-14: Giao diện thơng tin ứng dụng ........................................................... 79
Hình 3-15: Giao diện trang đăng nhập quản trị .................................................. 80
Hình 3-16: Giao diện danh sách nhóm địa điểm................................................. 81
Hình 3-17: Giao diện cập nhật thơng tin nhóm địa điểm .................................... 81
Hình 3-18: Giao diện danh sách địa điểm ........................................................... 82
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên

/>

9
Hình 3-19: Giao diện cập nhật thơng tin địa điểm .............................................. 82

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên


/>

10
PHẦN MỞ ĐẦU
Sự ra đời của các thế hệ điện thoại, các thiết bị di động thơng minh, có
khả năng kết nối internet, khai thác các dịch vụ đã làm cho các ứng dụng trên
chúng ngày càng trở lên phong phú, đa dạng, đặc biệt là các ứng dụng dịch vụ
dựa trên vị trí địa lý (Location-based Services - LBS) nhƣ các hệ thống dẫn
đƣờng, tìm kiếm địa điểm, trị chơi,… Các dịch vụ này đã mang lại nhiều lợi ích,
tiện lợi và làm cải thiện cuộc sống của con ngƣời. Việc giao tiếp, trao đổi dữ liệu,
giới thiệu ý tƣởng, mua bán hàng hóa và dịch vụ giữa con ngƣời với con ngƣời
khơng cịn giới hạn biên giới nữa khi mọi việc đều thực hiện thông qua mạng
Internet.
Bên cạnh các lợi ích nhƣ vậy, các ứng dụng cũng kèm theo những rủi ro
và thách thức mới liên quan đến quyền lợi riêng tƣ của ngƣời sử dụng dịch vụ
của các ứng dụng trên. Đặc trƣng của loại ứng dụng có sử dụng thơng tin vị trí
(Location-based Application - LBA) là phải theo vết di chuyển của ngƣời sử
dụng dịch vụ để từ đó xác định đƣợc vị trí tƣơng ứng và cung cấp dịch vụ tốt
nhất. Việc các thông tin vị trí của ngƣời dùng đƣợc trao đổi thƣờng xun trên
mạng gây mất an tồn thơng tin vị trí cá nhân. Tính riêng tư đƣợc đề cập đến
nhƣ là việc che giấu thơng tin vị trí của đối tƣợng chuyển động khi trao đổi trên
mạng. Tính riêng tƣ đƣợc đánh giá đặc biệt quan trọng trong LBS.
Một vài nghiên cứu trong những năm gần đây đã nêu lên những rủi ro bảo
mật và tính riêng tƣ cho ngƣời khai thác dịch vụ trực tuyến (nhƣđánh cắp định
danh, suy diễn dựa trên thông tin ngƣời dùng, bị giám sát trực tuyến và lừa
đảo, ...). Chính vì những lý do trên, Tổ chức Hợp tác và Phát triển kinh tế thế
giới - OECD (Organisation for Economic Co-operation and Development) đã
cảnh báo về vấn đề bảo vệ tính riêng tƣ trong các giao dịch trên mạng toàn cầu.
Hệ quả của việc sử dụng đa dạng thơng tin ngữ cảnh (vị trí địa lý, thơng
tin cá nhân, sở thích, tốc độ di chuyển, địa hình, sự phân bố dân cƣ...) trong ứng

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên

/>

11
dụng LBS gây rất nhiều khó khăn cho việc lựa chọn kỹ thuật phù hợp nhằm bảo
vệ đƣợc tính riêng tƣ của ngƣời dùng. Khó khăn này đến từ hai nguyên nhân
chính:
Những loại dịch vụ khác nhau yêu cầu các kỹ thuật bảo vệ tính riêng tƣ khác
nhau. Ví dụ: dịch vụ theo dõi di chuyển đòi hỏi phải biết chính xác vị trí của
ngƣời dùng. Trong trƣờng hợp này sử dụng giải thuật nhóm obfuscation sẽ
khơng phù hợp, trong khi các giải thuật nhóm k-anonymity lại là lựa chọn tốt.
Đối với cùng một dịch vụ, sự lựa chọn giải thuật bảo vệ tính riêng tƣ có thể
khác nhau tùy vào ngữ cảnh. Ví dụ: ngƣời dùng sử dụng dịch vụ tìm kiếm vị
trí xung quanh và sử dụng giải thuật obfuscation nhằm bảo vệ vị trí. Giải
thuật obfuscation giúp bảo vệ vị trí chính xác của ngƣời dùng bằng cách gửi
một vùng làm mờ bao gồm vị trí của ngƣời dùng trong đó. Tuy nhiên nếu
ngƣời dùng đang ở gần khu vực ao hồ thì vị trí của ngƣời dùng có thể bị phát
hiện bằng cách loại các vùng khơng đến đƣợc khỏi kết quả.
Việc đảm bảo tính riêng tƣ là nhu cầu của cả ngƣời dùng và nhà cung cấp
dịch vụ LBS. Một mặt, nhà cung cấp dịch vụ muốn thu hút ngƣời sử dụng bằng
cách cung cấp những dịch vụ an tồn đảm bảo đƣợc tính riêng tƣ của ngƣời
dùng. Mặt khác, nhà cung cấp vẫn có thể đảm bảo chất lƣợng cần thiết của dịch
vụ. Điều đó đồng nghĩa với phải có giải pháp giúp nhà cung cấp đƣa ra kỹ thuật
bảo vệ tính riêng tƣ phù hợp với ngữ cảnh mà vẫn đảm bảo chất lƣợng dịch vụ.
Nội dung luận văn là đƣa ra giải pháp để bảo vệ tính riêng tƣ cho ngƣời
dùng dịch vụ LBS bằng cách nghiên cứu, đánh giá các giải pháp và xây dựng
ứng dụng hiện thực hóa một giải pháp và thuật toán cụ thể. Một kết quả tốt thỏa
mãn mức độ riêng tƣ nhất định phải bảo vệ đƣợc thông tin nhạy cảm của ngƣời
dùng đồng thời không làm giảm nhiều chất lƣợng dịch vụ.

Cấu trúc trình bày của luận văn nhƣ sau: Chương 1 giới thiệu tổng quan
về LBS và các vấn đề liên quan, tiếp theo Chương 2 nghiên cứu các kỹ thuật,
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên

/>

12
mơ hình và các thuật tốn trong việc đảm bảo tính riêng tƣ của hệ thống LBS,
Chương 3 giới thiệu ứng dụng thử nghiệm hiện thực hóa một giải pháp và thuật
toán cụ thể. Phần kết luận nêu kết quả và chỉ ra các hƣớng nghiên cứu để phát
triển hệ thống trong tƣơng lai. Cuối cùng là phần tài liệu tham khảo.

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên

/>

13
CHƢƠNG I: TỔNG QUAN VỀ LOCATION BASED SERVICES
1.1 Định nghĩa Location Based Services
Location-based Services - viết tắt là LBS - có nghĩa là dịch vụ dựa trên vị
trí địa lý. Có rất nhiều định nghĩa khác nhau về LBS:
Định nghĩa 1 (Virrantaus et al, 2001) [17]: LBS là dịch vụ thông tin sử dụng bởi
với các thiết bị di động, thông qua mạng lƣới điện thoại di động và sử dụng các
khả năng xác định vị trí của thiết bị di động.
Định nghĩa 2 (OpenGeospatial Consortium, 2005)[11]:Một dịch vụ internet
không dây sử dụng thông tin địa lý phục vụ cho ngƣời sử dụng điện thoại di
động. Bao gồm các ứng dụng khai thác vị trí của một thiết bị đầu cuối di động.
Các định nghĩa trên mô tả LBS nhƣ là sản phẩm của sự kết hợp nhiều
công nghệ: GIS/cơ sở dữ liệu không gian; Internet; thiết bị di động/định vị tồn
cầu.


Hình 1-1: LBS là sự kết hợp của nhiều cơng nghệ[4]
LBS chính là sự tổ hợp của các cơng nghệ, bên cạnh đó, nó cho thấy sự
hình thành các hệ thống thơng tin tích hợp.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên

/>

14

1.2 Thành phần trong LBS
Các thành phần cơ bản tham gia cấu thành LBS đƣợc thể hiện trong hình:

Hình 1-2: Các thành phần cơ bản của LBS
Mobile Device(thiết bị di động): công cụ cho ngƣời sử dụng yêu cầu dịch
vụ, đồng thời thể hiện các kết quả trả về ở dạng lời nói, hình ảnh, văn bản,... Các
thiết bị có thể là PDA, điện thoại di động, máy tính xách tay, hoặc có thể là thiết
bị dẫn đƣờng của ơ tô.
Communication Network(mạng truyền thông): chuyển dữ liệu ngƣời
dùng và yêu cầu dịch vụ từ các thiết bị đầu cuối di động tới nhà cung cấp dịch
vụ và sau đó đƣa trả kết quả dịch vụ cho ngƣời sử dụng.
Positioning Component(thành phần định vị): LBS thƣờng địi hỏi vị trí
ngƣời sử dụng đã đƣợc xác định. Cách xác định phổ biến là sử dụng mạng thông
tin di động hoặc bằng cách sử dụng hệ thống định vị toàn cầu (GPS). Ngoài ra,
có thể sử dụng các trạm WLAN, các thiết bị có khả năng phát sóng vơ tuyến.
Cơng nghệ này đƣợc đặc biệt sử dụng trong các hệ thống định vị trong các cao
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên

/>


15
ốc, bảo tàng,... Lƣu ý rằng, nếu vị trí khơng đƣợc xác định tự động, nó có thể
cũng đƣợc quy định bởi ngƣời sử dụng.
Service and Content Provider(nhà cung cấp dịch vụ): các nhà cung cấp
dịch vụ cung cấp một số dịch vụ khác nhau cho ngƣời sử dụng và chịu trách
nhiệm trong việc xử lý yêu cầu dịch vụ. Các dịch vụ này cung cấp các tính tốn
về vị trí, tìm kiếm một con đƣờng, tìm kiếm các trang vàng hoặc tìm kiếm thơng
tin cụ thể trên các đối tƣợng mà ngƣời yêu cầu dịch vụ quan tâm. Tuy nhiên, các
nhà cung cấp dịch vụ thƣờng không trực tiếp lƣu trữ và duy trì tất cả các thơng
tin có thể đƣợc yêu cầu bởi ngƣời sử dụng. Vì vậy cơ sở dữ liệu địa lý và thơng
tin vị trí thƣờng sẽ do các bộ phận chức năng khác quản lý (ví dụ nhƣ cơ quan
lập bản đồ), hoặc do các đối tác kinh doanh (ví dụ nhƣ các trang vàng, các công
ty giao thông,...).
1.3 Ứng dụng của LBS
Đối với một cá nhân khi tiếp xúc một môi trƣờng mới, nhƣ chuyển nhà
hoặc nơi làm việc, một số hành vi và nhu cầu của họ có thể dự đốn đƣợc nhƣ:
tìm một nơi nào đó để ăn, một nhà thuốc tây, các trạm rút tiền cơng cộng, nơi
đón taxi, trạm xe bus... Khi ở nƣớc ngồi, có những u cầu bổ sung nhƣ: tìm
kiếm các điểm du lịch địa phƣơng, tìm khách sạn hay ngân hàng để đổi tiền. Khi
lái xe, có thể có các nhu cầu nhƣ giúp đỡ việc tìm kiếm một tuyến đƣờng tại một
thành phố mới đến hoặc yêu cầu dịch vụ sửa xe tại chỗ khi gặp sự cố.
Những nhu cầu tìm kiếm thơng tin liên quan địa lý nêu trên hồn tồn có
thể đƣợc đáp ứng bởi các ứng dụng mà LBS cung cấp. Trên các nhu cầu thực tế
của ngƣời dùng, chúng ta có thể xác định 5 loại nhu cầu chủ yếu về thông tin địa
lý [16]:
Định hƣớng và định vị trong khu vực
Điều hƣớng trong một khu vực, lập tuyến đƣờng
Tìm kiếm ngƣời hoặc thực thể
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên


/>

16
Xác nhận cá nhân hoặc đối tƣợng
Kiểm tra các sự kiện, xác định trạng thái của các đối tƣợng
Dựa trên các nhu cầu chủ yếu này, các nhà cung cấp dịch vụ LBS đã cho
ra đời nhiều ứng dụng đa dạng phục cho ngƣời dùng. Hình mơ tả tổng hợp và
phân loại một số các ứng dụng LBS phổ biến trên thế giới hiện nay.

Hình 1-3: Một số phân loại của các ứng dụng LBS [16]
Những giá trị mà LBS mang lại rất đặc trƣng và đa dạng so với các dịch
vụ khác. Ngƣời sử dụng dịch vụ này không chỉ tiết kiệm thời gian, chi phí mà
cịn có cơ hội khám phá những giá trị mới mà dịch vụ mang lại.
1.4 Hệ tọa độ địa lý
Hệ tọa độ địa lý cho phép tất cả mọi điểm trên Trái Đất đều có thể xác
định đƣợc bằng ba tọa độ của hệ tọa độ cầu tƣơng ứng với trục quay của Trái
Đất.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên

/>

17
Vĩ độ (ký hiệu: φ) của một điểm bất kỳ trên bề mặt Trái Đất là góc tạo
thành giữa đƣờng thẳng đứng tại điểm đó và mặt phẳng tạo bởi xích đạo. Đƣờng
tạo bởi các điểm có cùng vĩ độ gọi là vĩ tuyến. Tọa độ cực Bắc là 90° B; cực
Nam là 90° N. Vĩ tuyến 0° đƣợc chỉ định là đƣờng xích đạo, chia địa cầu thành
bán cầu Bắc và bán cầu Nam.
Kinh độ (ký hiệu: λ) của một điểm trên bề mặt Trái Đất là góc tạo ra
giữa mặt phẳng kinh tuyến đi qua điểm đó và mặt phẳng kinh tuyến gốc. Kinh
độ có thể là kinh độ Đông hoặc Tây, tạo thành từ một điểm trên bề mặt Trái Đất

và mặt phẳng tạo bởi đƣờng thẳng ngẫu nhiên nối hai cực Bắc Nam địa lý.
Những đƣờng thẳng tạo bởi các điểm có cùng kinh độ gọi làkinh tuyến. Tất cả
các kinh tuyến đều là nửa đƣờng trịn, và khơng song song với nhau (hội tụ tại
hai cực Bắc và Nam).
Độ cao, chiều cao, chiều sâu: để xác định hồn tồn một vị trí nằm trên,
ở trong hoặc ở phía trên bề mặt Trái Đất, ta cần phải xác định độ cao của điểm,
đƣợc định nghĩa bằng vị trí của điểm theo chiều thẳng đứng so với trung tâm của
hệ thống tham chiếu.
Bằng cách phối hợp góc vĩ độ và góc kinh độ, có thể xác định đƣợc vị trí
nằm ngang của bất kỳ điểm nào trên Trái Đất.
Cơng thức tính chiều rộng của một độ kinh độ tại vĩ độ :

trong đó bán kính độ kinh trung bình của Trái Đất Mr xấp xỉ bằng
6.367.449m.
Cơng thức tính độ rộng thực của một độ kinh độ tại vĩ độ :

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên

/>

18
trong đó bán kính xích đạoa = 6.378.137m và cực của Trái
Đấtb = 6.356.752,3m.

Hình 1-4: Bản đồ Trái Đất với vĩ tuyến (ngang) và kinh tuyến (dọc)
1.5 Tính khoảng cách giữa các tọa độ địa lý
Công thức Haversine là một đẳng thức đƣa ra các khoảng cách vòng cung
lý tƣởng (Great-circle distance) giữa hai điểm trên bề mặt khối cầu từ giá trị tọa
độ (kinh độ, vĩđộ) cho trƣớc của chúng.
Great-circle distance: Là khoảng cách ngắn nhất giữa hai điểm bất kì trên

bề mặt khối cầu tính dọc theo một hƣớng đi trên bề mặt khối cầu. Khoảng cách
giữa hai điểm trong không gian Euclidean là độ dài đoạn thẳng nối hai điểm đó.
Trong hình học cầu, đoạn thẳng đƣợc thay thế bằng đƣờng cong.
Do trái đất cũng có hình dạng gần nhƣ một khối cầu, các phƣơng trình cho
great-circle distance đóng vai trị rất quan trọng trong bài tốn tìm khoảng cách
ngắn nhất giữa các điểm trên bề mặt trái đất cũng nhƣ trong quá trình điều
hƣớng (định hƣớng đƣờng đi ngắn nhất cho các phƣơng tiện hàng không và
hàng hải).
Cơng thức Haversine tính khoảng cách theo bề mặt cầu của Trái Đất:
A(φ1, λ1); B(φ2, λ2)
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên

/>

19
Δφ = φ1– φ2; Δλ = λ1 – λ2
R = Bán kính Trái Đất (Quy ƣớc = 6,371km)
h = sin²(Δφ/2) + cos(φ1) * cos(φ2) * sin²(Δλ/2)
c = 2 * atan2(sqrt(h), sqrt(1−h))
Khoảng cách giữa 2 điểm d = R * c
1.6 Tổng quan về tính riêng tƣ trong LBS
1.6.1 Tính riêng tƣ
Tính riêng tƣ là yêu cầu của những cá nhân, nhóm, tổ chức có khả năng tự
quyết định khi nào, nhƣ thế nào, và thông tin nào về họ đƣợc truyền tải đến
ngƣời khác[4].
Tính riêng tƣ có thể xem nhƣ là một trở ngại lớn làm giảm sự phổ biến
của LBS. Trong thực tế ngƣời dùng muốn nhận đƣợc giá trị mà LBS mang lại
nhƣng không hề muốn thông tin vị trí của mình bị lộ cho ai khác biết. Do đó,
đảm bảo sự riêng tƣ cho ngƣời dùng LBS là một bài toán lớn cần phải giải quyết
để giúp LBS phát triển rộng rãi.

Nhƣ đã trình bày và phân tích ở trên, vị trí của ngƣời dùng là tham số cốt
lõi trong các hệ thống dịch vụ LBS, các dịch vụ LBS này chỉ có thể trả lời các
yêu cầu của ngƣời dùng khi họ cung cấp thông tin về vị trí hiện tại của mình. Vị
trí của ngƣời dùng đƣợc các công nghệ định vị hiện đại theo dõi và cập nhật một
cách chính xác, nếu khơng đƣợc bảo vệ thì đây sẽ là điểm yếu để kẻ địch lợi
dụng tấn công gây thiệt hại cho ngƣời dùng.
Theo Beresford et al. [6]: “Sự riêng tư của vị trí là khả năng ngăn cản
những người khác từ việc học một vị trí hiện tại hoặc vị trí đã biết”.Do đó sự
cần thiết phải bảo vệ tính riêng tƣ trong các ứng dụng LBS là sự cần thiết ngăn
chặn nhƣ: Theo dõi ngƣời dùng ở bất cứ chỗ nào hay khám phá ra các thói quen
cá nhân.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên

/>

20
1.6.2 Ngữ cảnh – Tính riêng tƣ trong mơi trƣờng ngữ cảnh động
Ngữ cảnh là các thơng tin có thể sử dụng để mô tả trạng thái của một thực
thể. Một thực thể có thể là con ngƣời, địa điểm, hoặc đối tƣợng đƣợc quan tâm
để gây ra tác động giữa ngƣời dùng và ứng dụng. Các nhà nghiên cứu đã phân
loại các kiểu ngữ cảnh khác nhau để thích hợp với ngƣời dùng khi truy cập
thông tin dịch vụ. Ví dụ, Schilit (1994) nhấn mạnh 3 vấn đề quan trọng của ngữ
cảnh: Bạn ở đâu (ngữ cảnh không gian), ai đi cùng bạn (ngữ cảnh xã hội) và cái
gì ở gần đây (ngữ cảnh thông tin).
Nivala (2003) đã phát triển một cách phân loại cho dịch vụ di động dựa
trên bản đồ. Có 9 kiểu ngữ cảnh đƣợc miêu tả:

Hình 1-5: Các kiểu ngữ cảnh khác nhau theo Nivala(2003)
Những nhà cung cấp LBS muốn đảm bảo chất lƣợng dịch vụ tốt hơn nên
sử dụng thêm thông tin ngữ cảnh kèm theo các yêu cầu dịch vụ của ngƣời dùng.

Thực tế, những kẻ tấn cơng vào tính riêng tƣ của ngƣời dùng có thể khai
thác những thơng tin sẵn có nhƣ địa hình, mơi trƣờng xung quanh ngƣời dùng
cùng với khả năng bắt đƣợc các yêu cầu dịch vụ để có thể xác định đƣợc các
thơng tin nhạy cảm liên quan đến ngƣời dùng. Ví dụ: nếu biết đƣợc ngƣời dùng
đang trong khu vực gần ao hồ, thì kẻ tấn cơng có thể loại trừ những vùng khơng
đặt chân đến đƣợc do đó khả năng đốn đƣợc vị trí của ngƣời dùng cao hơn.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên

/>

21
Nhƣ vậy, dữ liệu ngữ cảnh một mặt giúp tăng cƣờng chất lƣợng dịch vụ
LBS nhƣng mặt khác cũng là manh mối giúp kẻ tấn công khai thác đƣợc thông
tin riêng tƣ của ngƣời dùng. Trong môi trƣờng sử dụng dịch vụ LBS, ngƣời
dùng thƣờng xuyên thay đổi vị trí của mình, những thơng tin ngữ cảnh theo đó
cũng thay đổi theo. Việc đảm bảo tính riêng tƣ cho ngƣời dùng khi mà ngữ cảnh
thay đổi liên tục trở nên khó khăn hơn.
1.7 Nguy cơ bảo mật tính riêng tƣ trong LBS
Khi tham gia dịch vụ, ngƣời sử dụng mong muốn kẻ tấn cơng khơng có
khả năng liên kết các danh tính của họ với một thơng tin mà họ xem là nhạy cảm.
Trong trƣờng hợp của LBS, tồn tại rủi ro mà sự kết hợp này bị khám phá thơng
qua chính các các u cầu dịch vụ LBS đến các nhà cung cấp dịch vụ, gọi là kết
hợp nhạy cảm(sensitive association). Chính xác hơn, danh tính và thơng tin cá
nhân của một ngƣời dùng duy nhất có thể đƣợc suy dẫn từ yêu cầu dịch vụ.
Một cuộc tấn công bảo mật, hay tấn cơng nhằm vào tính riêng tƣ (privacy
attack) là một phƣơng pháp cụ thể đƣợc sử dụng bởi một kẻ tấn cơng để có đƣợc
sự kết hợp nhạy cảm trên. Các cuộc tấn công nhƣ vậy đƣợc phân loại chủ yếu
dựa vào sự đặc trƣng hóa đối tƣợng thực hiện tấn cơng, hay cịn gọi là mơ hình
tấn cơng (attack model). Một mơ hình tấn cơng nhƣ vậy có ba thành phần chính:
Các thơng tin nhạy cảm muốn khai thác: thông tin nhạy cảm là thông tin

mà kẻ tấn công muốn liên kết với một cá nhân cụ thể, đó có thể là sở thích,
thói quen, các thơng tin định danh,… hay vị trí của ngƣời đó.
Khả năng theo dõi các thông điệp trao đổi trong quá trình cung cấp dịch
vụ: các tấn cơng khác nhau có thể có những khả năng khác nhau để có
đƣợc những thông điệp trao đổi với nhà cung cấp dịch vụ, bằng cách nghe
trộm các kênh truyền thông hoặc bằng cách truy cập dữ liệu đƣợc lƣu trữ
tại các thiết bị đầu cuối.

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên

/>

22
Kiến thức nền và khả năng suy diễn có sẵn của kẻ tấn cơng: kẻ xấu có thể
có tiếp cận với tri thức bên ngồi, ví dụ danh bạ điện thoại, danh sách các
thành viên của một số hội nào đó, danh sách cử tri, và cả thơng tin về sự
hiện diện tại các địa điểm nhất định.
Thông qua các tri thức đó, kẻ tấn cơng dùng một số phƣơng pháp suy dẫn
(bao gồm các phép phân tích, thống kê,…) để liên kết thông tin từ các thông
điệp sử dụng dịch vụ với thơng tin bên ngồi.
Khi khơng có sẵn kiến thức nền, một mối đe dọa bảo mật chỉ tồn tại nếu
tồn tại các kết hợp nhạy cảm thu đƣợc từ các tin nhắn trong giao thức của dịch
vụ. Khi "toàn bộ" kiến thức nền đƣợc trang bị, các kết hợp nhạy cảm khơng cịn
bị giới hạn trong các yêu cầu dịch vụ. Nhƣ đã giới thiệu ở các phần trƣớc, LBS
là một dịch vụ đa ngữ cảnh, do đó khơng có sự giới hạn cụ thể về năng lực của
kẻ tấn cơng.
Tóm lại, các cuộc tấn cơng riêng tƣ không chỉ đƣợc phân loại về loại
thông tin nhạy cảm, khả năng theo dõi thơng điệp, mà cịn về kiến thức nền có
sẵn và khả năng phân tích của kẻ tấn công. Một số phân loại tấn công dựa vào
kiến thức nền của đối thủ:

Tấn công khai thác các thông tin khả định danh (quasi-identifier).
Tấn công tức thời (snapshot attack)hay các cuộc tấn công khai thác yếu tố
lịch sử (historical attack).
Tấn công khai thác một hay nhiều đối tƣợng khách hàng (single versus
multiple users).
Tấn công theo hiểu biết về cơ chế phịng vệ.

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên

/>

23
CHƢƠNG II: MỘT SỐ THUẬT TOÁN VÀ KỸ THUẬT BẢO VỆ TÍNH
RIÊNG TƢ CHO LBS
2.1 Tổng quan về kiến trúc hệ thống bảo vệ tính riêng tƣ
Hệ thống hỗ trợ bảo vệ tính riêng tƣ liên quan đến vị trí trong LBS tập
trung chủ yếu vào ba kiến trúc chính:
Kiến trúc không hợp tác (non-cooperative architecture): ngƣời dùng ý
thức việc bảo vệ vị trí của mình và tiến hành tại thiết bị di động cá nhân bằng
cách cung cấp các định danh giả, các thông tin đánh lạc hƣớng cho nhà cung cấp
dịch vụ nhằm bảo vệ thông tin riêng tƣ của mình.
Ví dụ: thay vì gửi vị trí chính xác của mình, ngƣời dùng sẽ gửi đến nhà
cung cấp dịch vụ 10 vị trí khác nhau bao gồm cả vị trí hiện tại của ngƣời dùng.
Kẻ tấn cơng sẽ khó để có thể xác định vị trí nào ngƣời dùng đang đứng. Về phía
nhà cung cấp dịch vụ sẽ tiến hành trả về kết quả liên quan đến 10 vị trí trên. Và
tại phía ngƣời dùng, nơi duy nhất biết đƣợc vị trí nào là thật sẽ tiến hành lọc các
kết quả và hiển thị kết quả đúng cho ngƣời dùng.

Hình 2-1: Kiến trúc khơng hợp tác [12]
Đây là phƣơng pháp hiện thực đơn giản và dễ dàng tích hợp với các cơng

nghệ đang có tuy nhiên nó lại có nhƣợc điểm là đẩy trách nhiệm bảo vệ tính

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên

/>

24
riêng tƣ về phía ngƣời dùng. Ngƣời dùng chỉ phụ thuộc vào kiến thức của mình
để tự bảo vệ thơng tin vị trí cá nhân.
Kiến trúc tập trung hóa (centralized architecture): với kiến trúc này một
thực thể trung tâm đƣợc đƣa ra để thu thập thông tin từ ngƣời dùng và cung cấp
cơ chế bảo vệ tính riêng tƣ cho mỗi ngƣời sử dụng dịch vụ. Thực thể trung tâm
này đƣợc ngƣời dùng tin tƣởng (trusted third party) đóng vai trò trung gian giữa
ngƣời dùng và nhà cung cấp dịch vụ. Nhiệm vụ chính của thực thể này là nhận
các yêu cầu dịch vụ của ngƣời dùng, các thông tin cá nhân của ngƣời dùng nhƣ
vị trí chính xác, các thông tin nhạy cảm,... và tiến hành làm mờ, che dấu các
thơng tin đó bằng các kỹ thuật bảo vệ, cuối cùng các thông tin làm mờ đƣợc gửi
đến nhà cung cấp dịch vụ. Thực thể trung tâm này cũng đóng vai trị nhận kết
quả trả về, tiến hành lọc các kết quả và chuyển về cho ngƣời sử dụng dịch vụ.

Hình 2-2: Kiến trúc tập trung [12]
Kiến trúc này giúp đảm bảo mức độ tính riêng tƣ cao cho ngƣời sử dụng
dịch vụ LBS đồng thời đảm bảo chất lƣợng dịch vụ tốt hơn. Hơn nữa kiến trúc
còn linh hoạt trong việc cung cấp các cơ chế bảo vệ tính riêng tƣ khác nhau và
khơng chỉ riêng cho bảo vệ thơng tin vị trí. Tuy nhiên mơ hình này lại có điểm
yếu là hiện thực phức tạp, hệ thống có thể bị hiện tƣợng thắt cổ chai nếu lƣợng
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên

/>


25
ngƣời đồng thời sử dụng dịch vụ q đơng. Ngồi ra việc bảo vệ kênh truyền dữ
liệu cũng là vấn đề quan trọng cần đƣợc xem xét.
Kiến trúc ngang hàng (peer-to-peer architecture): dựa trên sự phát triển
của công nghệ truyền thơng ngang hàng (peer-to-peer communication), trong
mơ hình kiến trúc này ngƣời dùng dịch vụ LBS hợp tác với nhau để đạt đƣợc
mức riêng tƣ cần thiết mà không cần đến một thực thể quản lý trung gian. Ngƣời
dùng tập hợp thành một nhóm và hợp tác với nhau làm cho kẻ tấn cơng và nhà
cung cấp dịch vụ khó có thể xác định đƣợc ngƣời dùng cụ thể nào đang thực sự
sử dụng dịch vụ LBS.

Hình 2-3: Kiến trúc ngang hàng [12]
Điểm yếu của kiến trúc này là không phải lúc nào ngƣời dùng cũng có thể
tập hợp đƣợc một nhóm để tiến hành ẩn danh. Thêm vào đó kiến trúc này cũng
không thể chống lại sự tấn công từ một thành viên nội bộ trong nhóm.
2.2 Các nhóm kỹ thuật bảo vệ tính riêng tƣ
Tính riêng tƣ của ngƣời dùng là một vấn đề phải quan tâm một cách đặc
biệt trong LBS. Trong đó, đảm bảo an tồn cho thơng tin về vị trí của ngƣời
dùng là cực kì quan trọng. Mặc dù đã có rất nhiều nghiên cứu để bảo vệ an tồn
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên

/>