Luận văn Đảm bảo công bằng trong các ứng dụng cộng tác ngang hàng

-1- ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGH NGUYỄN XUÂN LÔ ĐẢM BẢO CÔNG BẰNG TRONG CÁC ỨNG DỤNG CỘNG TÁC NGANG HÀNG Ngành: Công nghệ thông tin Chuyên ngành: Truyền dữ liệu và Mạng máy tính Mã số: 60 48 15 LUẬN VĂN THẠC SĨ NGƯỜI HƯỚNG DẪN KHOA HỌC: PGS.TS HỒ SĨ ĐÀM Hà Nội – 2011 -2- LỜI CAM ĐOAN Tôi xin cam đoan toàn bộ nội dung của bản luận văn với tên “Đảm bảo công bằng trong các ứng dụng cộng tác ngang hàng” là do tôi tự nghiên cứu, tham khảo và phát triển các ý, các giải thuật theo yêu cầu của đề tài luận văn. Nội dung bản luận văn chưa từng được công bố, phát hành hoặc sao chép dưới bất kì hình thức nào. Nếu sai, tôi xin chịu hoàn toàn mọi trách nhiệm ! Hà Nội, ngày 13/6/2011 Người cam đoan Nguyễn Xuân Lô -3- LỜI CẢM ƠN Em xin chân thành cảm ơn các Thầy, Cô giáo khoa Công nghệ Thông tin trường Đại học Công nghệ - Đại học Quốc gia Hà Nội; các Thầy, Cô giáo trong và ngoài trường Đại học Công nghệ đã giảng dạy, giúp đỡ, tạo điều kiện cho em học tập, nghiên cứu để có tri thức bậc Sau đại học. Đặc biệt, em xin bày tỏ lòng biết ơn sâu sắc tới Thầy giáo - Phó Giáo sư Tiến sĩ Hồ Sĩ Đàm đã tận tình hướng dẫn, chỉ bảo để em hoàn thành luận văn. Tôi cũng xin chân thành cảm ơn tới tất cả các bạn học viên cao học K14 ngành Công nghệ thông tin trường Đại học Công nghệ - Đại học Quốc gia Hà Nội đã giúp đỡ tôi trong thời gian học tập và làm luận văn. Mặc dù đã có nhiều cố gắng, song do trình độ năng lực còn hạn chế, nên luận văn không tránh khỏi thiếu sót. Rất mong nhận được sự góp ý, quan tâm của các Thầy, Cô cùng toàn thể các bạn và những ai quan tâm tới luận văn. Một lần nữa, tôi xin chân thành cảm ơn. Hà Nội, tháng 6 năm 2011 Người làm luận văn Nguyễn Xuân Lô -4- MỤC LỤC Trang Chương Mở đầu .................................................................................................................................5 Lý do chọn đề tài............................................................................................................................ 5 Mục đích nghiên cứu...................................................................................................................... 5 Nội dung nghiên cứu...................................................................................................................... 5 Bố cục luận văn .............................................................................................................................. 6 Chương 1: Những vấn đề chung..........................................................................................................7 1.1. Ứng dụng phân tán.................................................................................................................. 7 1.2. Ứng dụng cộng tác ngang hàng................................................................................................ 9 1.3. Mạng ngang hàng Peer – to - Peer (P2P).................................................................................10 1.4. Một số mạng chia sẻ file .........................................................................................................10 1.5. Thuật toán và độ phức tạp thuật toán ....................................................................................13 Chương 2: Suy luận tin cậy trong mạng ngang hàng ..........................................................................19 2.1. Khái niệm tin cậy và quản lí tin cậy .........................................................................................19 2.2. Mô hình tin cậy ......................................................................................................................19 2.3. Xác định người cộng tác .........................................................................................................22 2.4. Mô hình suy luận....................................................................................................................23 2.5. Mô hình hệ thống tin cậy NICE: ..............................................................................................24 2.6. Tính toán tin cậy phân tán trong NICE.....................................................................................28 2.7. Các hệ thống tin cậy khác .......................................................................................................36 Chương 3: Đảm bảo công bằng với các ứng dụng cộng tác trong mạng ngang hàng .........................38 3.1. Giới thiệu ...............................................................................................................................38 3.2. Bài toán..................................................................................................................................39 3.3. Giao dịch dựa trên cookie.......................................................................................................43 3.4. Kiểm tra tính tin cậy của các cookie ........................................................................................46 3.5. Áp dụng mô hình tin cậy NICE đảm bảo công bằng trong ứng dụng chia sẻ file BitTorrent ......51 3.6. Chương trình Demo và các kết quả thu được..........................................................................58 Kết luận và hướng nghiên cứu ..........................................................................................................69 Tài liệu tham khảo ............................................................................................................................70 -5- Chương Mở đầu Lý do chọn đề tài Hiện nay mạng ngang hàng Peer - to - Peer (P2P) cùng với các ứng dụng của nó đang nổi lên và ngày càng chiếm nhiều thị phần trong đời sống. Các mô hình ứng dụng chia sẻ file dữ liệu đã được triển khai nhiều ở các công ty, xí nghiệp, trường học và đã và đang đem lại nhiều lợi ích. Để có thể sử dụng mạng P2P hiệu quả thì người sử dụng phải cộng tác với nhau. Chia sẻ file và cộng tác trong các ứng dụng P2P là đặc trưng tiêu biểu của mạng ngang hàng. Tuy nhiên trong quá trình cộng tác với nhau nảy sinh nhiều vấn đề, ví dụ như cách chia sẻ file, quyền truy cập lấy tài liệu, thứ tự ưu tiên lấy tài liệu, kiểm tra tính tín cậy trong cộng tác, ảnh hưởng trong giao dịch đến băng thông và hiệu năng của mạng, vấn đề bảo mật,... đặc biệt là trong môi trường cộng tác nhưng có tính phí. Để có thể cải thiện được một môi trường cộng tác hiệu quả hơn trong các ứng dụng P2P, làm cho nó ngày càng phát triển, thì đã có rất nhiều các công trình nghiên cứu trong và ngoài nước và cũng đạt được nhiều thành tựu. Với những lý do trên mà tôi chọn đề tài nghiên cứu “Đảm bảo công bằng trong các ứng dụng cộng tác ngang hàng”, với mong muốn nghiên cứu về một lĩnh vực nhỏ trong ứng dụng P2P, và góp một phần vào việc nâng cao hiệu quả trong ứng dụng cộng tác ngang hàng. Mục đích nghiên cứu Mục đích nghiên cứu của đề tài là: - Phân biệt ứng dụng (người) cộng tác và không cộng tác. - Tìm được giải thuật định giá và kiểm tra tính tin cậy của ứng dụng cộng tác. - Áp dụng kết quả nghiên cứu vào các ứng dụng cộng tác trong mạng P2P. Nội dung nghiên cứu - Ứng dụng cộng tác trong mạng P2P - Suy luận tin cậy trong mạng P2P, mô hình độ tin cậy ngang hàng của NICE. - Đảm bảo công bằng cho các ứng dụng cộng tác trong mạng P2P. -6- + Vấn đề công bằng trong mạng. + Áp dụng mô hình tin cậy NICE đảm bảo công bằng trong ứng dụng chia sẻ file BitTorrent. + Mô phỏng và đánh gía hiệu năng. Bố cục luận văn Luận văn gồm 4 chương: Chương mở đầu: trình bày về lí do chọn đề tài nghiên cứu, mục đích nghiên cứu, nội dung nghiên cứu. Chương 1: Những vấn đề chung: Trình bày các khái niệm cơ bản về ứng dụng phân tán và ứng dụng cộng tác, các khái niệm trong mạng ngang hàng, giải thuật và độ phức tạp của giải thuật. Chương 2: Suy luận tin cậy trong mạng ngang hàng: Trình bày về các khái niệm tin cậy, định giá tin cậy, mô hình tin cậy NICE làm nền tảng cho áp dụng vào ứng dụng của chương 3. Chương 3: Đảm bảo công bằng với các ứng dụng cộng tác ngang hàng: Chương này trình bày về những khái niệm công bằng, đảm bảo công bằng trong các ứng dụng chủ/khách và ngang hàng, giao dịch dựa trên cookie và kiểm tra tính tin cậy của cookie. Chương này cũng tập trung trình bày việc áp dụng mô hình NICE vào một ứng dụng nhỏ trong mạng BitTorrent và chương trình demo cùng kết quả. -7- Chương 1: Những vấn đề chung 1.1. Ứng dụng phân tán Theo tác giả Dinesh C. Verma [2]. Phần này trình bày những khái niệm cơ bản về ứng dụng phân tán, lĩnh vực liên quan đến cộng tác ngang hàng. a) Khái niệm ứng dụng phân tán: Bao gồm hai hoặc nhiều module phần mềm chạy trên các máy tính khác nhau, tương tác với nhau thông qua mạng truyền thông kết nối giữa các máy tính. Các vấn đề chủ yếu cần quyết định khi xây dựng ứng dụng phân tán – Ứng dụng cần bao nhiêu module phần mềm – Triển khai các module phần mềm trên các máy tính khác nhau như thế nào – Bằng cách nào mỗi module phần mềm phát hiện ra các module khác nó cần giao tiếp b) Kiến trúc client/server Kiến trúc client/server là cách tổ chức một ứng dụng phân tán bao gồm hai modules phần mềm khác nhau: – Module server với chỉ một thể hiện trong hệ thống. – Module client với nhiều thể hiện trong hệ thống. Về mặt giao tiếp trong hệ thống: Chỉ diễn ra giữa module server và các module client. Đặc trưng của kiến trúc client/server là có một module server làm điểm trung tâm trong giao tiếp. Các client không giao tiếp trực tiếp với nhau mà chỉ giao tiếp với module server. Trong kiến trúc client/server, server thường chứa nhiều phần mềm phức tạp, trong khi clients thì đơn giản. Với lợi ích của trình duyệt web trong hầu hết các máy tính, thì đây là kiến trúc hầu như dành để phát triển các ứng dụng phân tán vì rằng chúng có thể sử dụng một trình duyệt web chuẩn làm client. Vấn đề phát hiện để giao tiếp: Mỗi client cần phát hiện địa chỉ mạng của server:  Server chạy trên cổng và địa chỉ IP biết trước với các client  Client kết nối với server theo địa chỉ mạng đã biết -8-  Server không cần biết trước bất kỳ thông tin nào về các client Trên Internet, client chỉ cần biết địa chỉ IP của server vì số hiệu cổng của client đã được chuẩn hóa. • Ưu điểm – Đơn giản hóa công việc bảo trì và nâng cấp • Module server thường phức tạp hơn module client lại được đặt ở chỉ một máy tính • Hiện nay thường trình duyệt Web được sử dụng làm client, người phát triển ứng dụng không cần phát triển và bảo trì • Nhược điểm Không sử dụng hiệu quả sức mạnh tính toán của các máy client như máy server c) Kiến trúc ngang hàng Kiến trúc P2P là cách tổ chức nhiều module phần mềm giống nhau, mỗi module chạy trên một máy tính khác nhau giao tiếp với nhau. Theo cách này thì có thể coi mỗi máy tính vừa chạy module client yêu cầu truy nhập dịch vụ vừa chạy module server cung cấp dịch vụ cho các máy tính khác. + Vấn đề phát hiện Mỗi máy tính cần biết địa chỉ mạng của các máy tính khác nó muốn giao tiếp + Ưu và nhược điểm Tận dụng sức mạnh kết hợp và khả năng mở rộng, tuy nhiên vấn đề bảo trì và nâng cấp phần mềm khó khăn hơn. d) Vấn đề khám phá Để có thể giao tiếp với nhau mỗi module cần biết nơi gửi thông báo cho các module khác (Tức địa chỉ mạng gồm địa chỉ IP và số cổng). - Các giải pháp phát hiện địa chỉ: + Cố định số cổng, cho tất cả các module biết địa chỉ IP và số cổng của các module khác. Điều này làm được bằng cách: Có thể mã cứng vào chương -9- trình, tuy nhiên cũng giống như phương pháp cấu hình địa chỉ IP tĩnh trên mạng -> cần phối hợp tổng thể tránh đụng độ số cổng. + Địa chỉ IP và số cổng của các module khác được cung cấp như các tham số cấu hình. Phương pháp này có nhược điểm đối với các ứng dụng quy mô lớn đòi hỏi nhiều công sức cấu hình. 1.2. Ứng dụng cộng tác ngang hàng Một ứng dụng cộng tác là một ứng dụng chia sẻ các thành phần tài nguyên của chúng để cho các thành viên khác trong nhóm cộng tác sử dụng. Nói một cách khác, một ứng dụng cộng tác là một ứng dụng phân bổ một tập con tài nguyên của nó cho việc sử dụng của các máy khác trong ứng dụng. Tài nguyên phân bổ ở đây là bộ xử lí, băng thông, dữ liệu lưu trữ,…, của ứng dụng cộng tác. Khi các ứng dụng cộng tác với nhau, chúng tạo thành các nhóm cộng tác. Các nhóm cộng tác, trong thực tế, hiện nay có thể kể đến một lớp rộng lớn các ứng dụng, bao gồm các ứng dụng dòng đa phương tiện trực tuyến, các ứng dụng hội nghị đa thành phần và các ứng dụng P2P…, và có thể là một hạ tầng cơ sở cộng tác. Tuy vậy các hệ thống cộng tác chỉ thi hành tốt nhất nếu tất cả mọi người sử dụng làm việc, cộng tác và cung cấp chia sẻ tài nguyên của họ tới hệ thống. Quan điểm của hệ thống cộng tác là không duy nhất trong liên mạng. Trong thực tế các gói tin vận chuyển trong Internet là sự cộng tác mạo hiểm khi dùng các tài nguyên chia sẻ ở các bộ định tuyến (router). Mục đích hướng tới đối với những ứng dụng cộng tác là các ứng dụng đầu cuối, nơi cung cấp một platform trong việc thực hiện các ứng dụng phân tán rộng lớn theo kiểu cộng tác. Rõ ràng, một số các tài nguyên phân tán rộng lớn có thể có được qua Internet trong sự cộng tác. Đây cũng chính là xu hướng của các ứng dụng cộng tác ngang hàng Peer-to-Peer (P2P), và những thế hệ tiếp theo của các ứng dụng P2P dựa trên các khái niệm của sự chia sẻ tài nguyên phân tán cộng tác. -10- 1.3. Mạng ngang hàng Peer – to - Peer (P2P) Định nghĩa: Theo tài liệu của Ralf Steinmetz [7] trang 21 thì Oram et al đưa ra định nghĩa cơ bản về hệ thống Peer – to – Peer như sau: [a Peer-to-Peer system is] a self-organizing system of equal, autonomous entities (peers) [which] aims for the shared usage of distributed resources in a networked environment avoiding central services. Mạng P2P không có khái niệm máy trạm (client) hay máy chủ (server), mà chỉ có khái niệm các nốt (peers) đóng vai trò cả client và server. Theo Karl Aberer, Zoran Despotovic [4] thì các nốt khi tham gia trao đổi trong cộng đồng mạng sẽ cung cấp truy cập tới các tài nguyên tính toán của chính nó. Một mạng P2P có thể được đặc trưng bởi các tính chất sau: - Không có sự sắp đặt trung tâm (Các máy không chịu sự sắp đặt của một máy khác). - Không có cơ sở dữ liệu trung tâm (Cơ sở dữ liệu là phân tán). - Không có máy nào bao trùm hệ thống (Các máy là ngang hàng). - Các máy tự trị - Các máy và các kết nối là không tin cậy. 1.4. Một số mạng chia sẻ file 1.4.1. Mạng chia sẻ file P2P: - Là mạng P2P phổ biến và nổi tiếng nhất trên Internet hiện nay. + Chức năng chủ yếu của mạng là cho phép tìm kiếm và truyền dữ liệu dựa trên giao thức IP (Internet Protocol). + Để truy cập vào mạng P2P này, người dùng chỉ cần download và cài đặt phần mềm ứng dụng phù hợp cho máy tính của mình. + Có nhiều mạng P2P và phần mềm ứng dụng P2P tồn tại hiện nay. Một số phần mềm chỉ sử dụng được cho 1 mạng P2P nhất định, một số hoạt động được với nhiều mạng P2P khác nhau. + Một số mạng P2P nổi tiếng trên Internet như: BitTorent, Gnutella,... -11- 1.4.2. Chia sẻ file trong mạng ngang hàng - Có thể nói ứng dụng được sử dụng nhiều nhất của mạng ngang hàng đó là chia sẻ file. - Theo ước tính khoảng 50% (có thời điểm đến 75% ) lưu lượng mạng trên Internet được cho là để trao đổi các file đặc biệt là các file âm nhạc (hơn 1 tỷ các file âm nhạc được download mỗi tuần). - Đặc điểm của vấn đề chia sẻ file là các máy (Peer) có các file được download với vai trò là một Client làm cho chúng luôn sẵn sàng với các Peer khác trong vai trò của một Server. - Vấn đề chủ yếu cho mạng ngang hàng nói chung và cho vấn đề chia sẻ file nó riêng là vấn đề tìm kiếm. Trong ngữ cảnh của hệ thống chia sẻ file, có ba mô hình khác nhau được phát triển: mô hình flooded request, mô hình thư mục trung tâm và mô hình hướng tài liệu. Các mô hình này được minh hoạ qua các ứng dụng thực của mạng ngang hàng sau: Gnutella, Naspter và FreeNet. Gnutella : Trong hệ thống Gnutella, không có sự tập trung hoá, các file được lưu trữ trên các Peer của hệ thống, khi có yêu cầu tìm kiếm một file máy tính sẽ gửi yêu cầu này tới tất cả các peer là láng giềng của nó và quá trình này được lặp lại cho tới khi tìm thấy máy chứa file cần tìm. Tiếp theo là quá trình trao đổi file trực tiếp giữa hai máy tính trong mạng. Hiện nay phần mềm nổi tiếng sử dụng phương pháp tìm kiếm và chia sẻ file dạng này là Bittorent. Naspter : Trong hệ thống Naspter, có sự tập trung hoá. Khi một máy tham gia vào mạng, danh mục các file sẽ được đăng ký và lưu trữ trên Server trung tâm, khi có yêu cầu tìm kiếm, máy tính sẽ hỏi Server trung tâm về vị trí của file. Sau đó việc trao đổi file được thực hiện giữa hai máy tính với nhau. FreeNet: Trong hệ thống Freenet, file không được lưu trữ trên đĩa cứng của các peer cung cấp chúng mà được lưu trữ ở các vị trí khác trong mạng. Mục đích của việc phát triển mạng Freenet là làm cho thông tin được lưu trữ và truy cập mà không cần biết định danh. Với các tổ chức như vậy, chủ sở hữu của một node mạng cũng không biết được tài liệu gì được lưu trữ trên đĩa cứng của máy anh ta. Vì lý do này mà các Peer và các file được cung cấp các số định danh khác nhau. Khi một file được tạo, nó được truyền qua các peer láng giềng tới các peer có số định danh gần với số định danh của file nhất và được lưu trữ ở đó. 1.4.3. Một số giao thức sử dụng trong các mạng chia sẻ file -12- a) Hệ thống Gnutella Giao thức trong Gnutella là giao thức tìm kiếm phân tán. Giao thức Gnutella được định nghĩa là lối vào để các servent truyền thông qua mạng. Nó bao gồm một tập các đặc tả được sử dụng cho truyền thông dữ liệu giữa các servent và một tập các qui tắc chủ yếu trao đổi bên trong các servent của các đặc tả. Mặc dù giao thức Gnutella hỗ trợ tìm kiếm theo dạng chủ-khách truyền thống, nhưng nét đặc biệt của Gnutella là mô hình không tập trung, dạng peer- to-peer chính nó. Trong mô hình này, mỗi máy khách cũng đồng thời là máy chủ. Chính vì vậy, Gnutella còn được gọi là servents thực hiện công việc của cả máy chủ lẫn máy khách. Chúng cung cấp các giao diện phía máy khách để cho người sử dụng phát ra các truy vấn và xem các kết quả tìm kiếm được, trong khi ở cùng thời điểm chúng cũng truy cập các truy vấn ở các servent khác, kiểm tra tính tương phản của tập dữ liệu cục bộ, và trả lời đối với các kết quả tương xứng. Do tính phân tán tự nhiên của chính nó, mà một mạng servents áp dụng giao thức Glutella sẽ có khả năng kháng lỗi rất cao, việc xử lí của mạng sẽ không bị ngắt nếu như có một tập các servent xảy ra tình trạng offline. Việc tìm kiếm trong mạng ngang hàng theo cơ chế lan truyền giữa các máy gây ra sự chiếm dụng băng thông đường truyền lớn. Trong Gnutella, các máy vận chuyển truy vấn của các máy khác làm ngập lụt hệ thống. Mỗi thông báo vận chuyển tiêu thụ băng thông và bộ xử lí ở mỗi nút nó viếng thăm. Cải thiện vấn đề này chính là khả năng cân bằng tải của mạng. b) Hệ thống dựa trên giải thuật Chord Trong Chord, tài liệu được ánh xạ tới nút đặc biệt sử dụng hàm băm. Tuy vậy mỗi máy phục vụ một tài liệu, tài liệu này trong thực tế được sở hữu bởi một vài nút khác trong hệ thống. Như vậy các máy trong hệ thống tiêu thụ tài nguyên của chúng để phục vụ các tài liệu đối với các nút khác trong hệ thống. Tình trạng này là không duy nhất đối với Chord; tất cả các hệ thống xác định dựa trên việc băm, bao gồm CAN, Bayeux, Pastry, đều có tính chất này. Điều đó có thể làm được nhằm xây dựng một hệ thống trong đó các nút chỉ phục vụ một điểm tới tài liệu và cũng để thực hiện các hệ thống cân bằng tải khác nhau. Như vậy, -13- ngay cả trong hệ thống được cân bằng tải tốt nhất, có thể nhất thời xảy ra quá tải khi một lượng lớn các tài nguyên cục bộ được tiêu thụ do các dịch vụ mở rộng. c) Một số các giao thức dòng phương tiện dựa trên chuyển mạch Trong các giao thức này, các nút dành hết tài nguyên (giống như băng thông) để phục vụ cho các nút con của nó. Trong mỗi ví dụ trên, bất kì một người sử dụng riêng lẻ có thể chọn không để dành tài nguyên cục bộ cho các yêu cầu mở rộng, nhưng vẫn nhận được đầy đủ lợi ích của hệ thống. Trong các trường hợp khác, được tích hợp và chính xác các hàm của hệ thống tiêu thụ trong mỗi người sử dụng đang thực hiện toàn bộ giao thức phân tán không ích kỉ và đúng đắn. Như vậy, bằng kinh nghiệm triển khai các hệ thống, như Gnutella và Napster trước đó, diễn tả rằng chỉ một tập nhỏ các máy đưa ra như vậy ích kỉ dịch vụ đối với cộng đồng chung, trong khi phần lớn những người sử dụng sử dụng các dịch vụ được đưa ra bởi một ít hào phóng này. Mục đích của công việc này là xác định hiệu quả số ít hào phóng và dạng tất cả những người sử dụng mà đưa ra các dịch vụ cục bộ đối với cộng đồng chung. 1.5. Thuật toán và độ phức tạp thuật toán 1.5.1. Thuật toán [14] Thuật toán (algorithm) là một trong những khái niệm quan trọng nhất trong tin học, là một trong hai thành tố cấu tạo nên chương trình máy tính (cấu trúc dữ liệu + giải thuật = chương trình). Theo PGS.TS Hồ Sĩ Đàm [13] định nghĩa thì thuật toán là một dãy hữu hạn các thao tác, sắp xếp theo một trật tự xác định, sau khi thực hiện, từ Input ta nhận được Output cần tìm. 1.5.2. Các đặc trưng chính của thuật toán [14]: a) Input: Mỗi thuật toán cần có một số (có thể bằng không) dữ liệu vào (input). Đó là các giá trị cần đưa vào khi thuật toán bắt đầu làm việc. Các dữ liệu này cần được lấy từ các tập hợp cụ thể nào đó. b) Output: Mỗi thuật toán cần có một hoặc nhiều dữ liệu ra (output). Đó là các giá trị có quan hệ hoàn toàn xác định với các dữ liệu vào và là kết quả của sự thực hiện thuật toán. -14- c)Tính xác định : Mỗi bước của thuật toán cần phải được mô tả một cách chính xác, chỉ có một cách hiểu duy nhất. d) Tính khả thi: Tất cả các phép toán có mặt trong các bước của thuật toán phải đủ đơn giản, nghĩa là các phép toán phải sao cho, ít nhất về nguyên tắc có thể thực hiện được bởi con người chỉ bằng giấy trắng và bút chì trong một khoảng thời gian hữu hạn. e) Tính kết thúc (tính đóng): Với mọi bộ dữ liệu vào thỏa mãn các điều kiện của dữ liệu vào (tức là được lấy ra từ các tập giá trị của các dữ liệu vào), thuật toán phải kết thúc (dừng) sau một số hữu hạn các bước thực hiện. f) Tính chi tiết [13]: Phụ thuộc vào đối tượng thực hiện g) Tính phổ dụng [13]: Thuật toán có thể áp dụng với một lớp các bài toán khi thay đổi đầu vào (input). h) Tính hiệu quả [13]: Được đặc trưng bởi 2 yếu tố: Thời gian (Tốc độ xử lý) và không gian (Dung lượng lưu trữ). • Ví dụ minh họa: Bài toán: tìm phần tử lớn nhất trong 1 dãy hữu hạn các số nguyên a1, a2,..,an. • Thuật toán: – Bước 1:Đặt giá trị cực đại tạm thời max = a1 – Bước 2: So sánh số nguyên tiếp sau với max • Nếu số nguyên tiếp sau lớn hơn đặt max = số nguyên tiếp sau – Bước 3: Lặp lại bước trên nếu còn số nguyên trong dãy – Bước 4: Dừng khi không còn số nguyên nào.  Số nguyên = max chính là phần tử lớn nhất • Chứng minh: thuật toán trên hội đủ các tính chất của thuật toán – Đầu vào: dãy các số nguyên a1,…. an – Đầu ra: số lớn nhất trong dãy đó – Tính xác định và khả thi: thuật toán gồm 1 phép gán, 1 vòng lặp hữu hạn và phép so sánh  các bước đều được xác định chính xác và có thể thi hành. -15- – Tính hữu hạn: thuật toán luôn luôn kết thúc sau khi tất cả các số nguyên được kiểm tra – Tính hiệu quả: thuật toán luôn kết thúc trong 1 khoảng thời gian hữu hạn. – Tính phổ dụng: có thể áp dụng thuật toán này tìm số cực đại cho bất kỳ dãy số nguyên nào 1.5.3. Độ phức tạp của thuật toán Hiệu quả của thuật toán được phân tích như thế nào? Khi giải một bài toán, chúng ta cần chọn trong số các thuật toán, một thuật toán mà chúng ta cho là “tốt” nhất. Các thước đo tính hiệu quả của 1 thuật toán: – Thời gian mà máy tính sử dụng để giải bài toán theo thuật toán đang xét khi các giá trị đầu vào có kích thước xác định  Độ phức tạp thời gian – Dung lượng bộ nhớ để thực hiện thuật toán khi các giá trị đầu vào có kích thước xác định  Độ phức tạp không gian a) Lựa chọn thuật toán: Dễ hiểu, dễ cài đặt và dễ ghi chép. Sử dụng các tài nguyên hiệu quả. b) Ký pháp Giả sử T(n) là thời gian thực hiện TT và f(n), g(n), h(n) là các hàm xác định dương. - Hàm Theta lớn: T(n) là hàm Theta lớn của g(n): T(n) =Θ(g(n)) nếu  các hằng số dương c1, c2, n0 sao cho với mọi n>= n0 : c1 g(n) <= T(n) <= c2 g(n) - Hàm Omega lớn: T(n) là hàm Omega lớn của g(n): T(n)=Ω(g(n)) nếu  c và n0 sao cho với mọi n>= n0 thì -16- T(n) >= c.g(n) - Hàm O lớn: T(n) là hàm Omega lớn của g(n), T(n) =O (g(n)) nếu  c và n0 sao cho với mọi n>= n0 : T(n) <=c g(n) g(n) còn gọi là giới hạn trên của T(n). c) Các tính chất (i) Tính bắc cầu: nếu f(n)= O(g(n)) và g(n)= O(h(n)) thì f(n)= O(h(n)) (ii) Tính phản xạ: f(n)=O(f(n)) d) Xác định độ phức tạp - Quy tắc hằng số: Nếu P có T(n)= O(c1f(n)) thì gọi P là có độ phức tạp O(f(n)). CM: T(n)= O(c1f(n)) nên tồn tại c0>0 và n0 >0 để T(n) <= c0.c1 f(n) với mọi n>= n0. Đặt c=c0.c1 ta có điều cần CM. - Quy tắc lấy Max Nếu P có T(n)= O( f(n)+g(n)) thì P có độ phức tạp là O(max( f(n), g(n))). CM: T(n) = O(f(n)+g(n)) nên tồn tại n0>0 và c>0 để T(n) <= cf(n) + cg(n), với mọi n>= n0 vậy T(n) =n0. Từ đó suy điều cần CM. - Quy tắc cộng Nếu P1 có T1(n) = O(f(n) và P2 có T2(n)= O(g(n)), khi đó: T1(n) +T2(n) = O(f(n) +g(n)). CM: Vì T1(n)= O(f(n)) nên  các hàng số c1 và n1 sao cho T(n) <= c1.f(n) n: n>= n1. Vì T2(n) =O(g(n)) nên  các hàng số c2 và n2 sao cho T(n) <= c1.g(n) n: n>= n2 Chọn c= max (c1,c2) và n0 = max(n1, n2) ta có n: n n>= n0: T(n) = T1(n) + T2(n) <= c1f(n) + c2g(n)<= cf(n) +cg(n) = c(f(n)+g(n)). - Quy tắc nhân -17- Nếu P có T(n)= O(f(n)). Khi đó nếu thực hiện k(n) lần P với k(n)=O(g(n)) thì độ phức tạp là O(f(n) g(n)). CM: Thời gian thực hiện k(n) lần đoạn chương trình P sẽ là k(n) T(n), theo định nghĩa: ck>=0 và nk >0 để k(n) = nk cT>=0 và nT >0 để T(n) = nT Vậy với mọi n >= max(nT,nk) ta có k(n)T(n) <= ckcT(f(n)g(n)). e) Áp dụng đánh giá chương trình - Câu lệnh đơn thực hiện một thao tác => Áp dụng qui tắc hằng số - Câu lệnh hợp thành là dãy các câu lệnh => Áp dụng qui tắc tổng - Câu lệnh rẽ nhánh dạng If ..Then..Else. => Áp dụng qui tắc Max - Các câu lệnh lặp => Áp dụng qui tắc Nhân Các thuật ngữ dùng cho độ phức tạp của thuật toán Độ phức tạp Thuật ngữ O(1) Độ phức tạp hằng số O(logn) Độ phức tạp logarit O(n) Độ phức tạp tuyến tính O(nlogn) Độ phức tạp nlogn O(nb) Độ phức tạp đa thức O(bn) b>1 Độ phức tạp hàm mũ O(n!) Độ phức tạp giai thừa g) Độ phức tạp tính toán và dữ liệu vào: - Trường hợp tốt nhất: T(n) là thời gian ít nhất. - Trường hợp xấu nhất: T(n) là thời gian lớn nhất. - Trường hợp trung bình: dữ liệu vào tuân theo một phân bố xác suất nào đó. h) Phép toán tích cực: -18- Là các phép toán thực hiện nhiều nhất trong chương trình. Trong một chương trình, nếu các phép toán tích cực chiếm thời gian chủ yếu, còn các phép toán khác chiếm thời gian không đáng kể, thì độ phức tạp thời gian của chương trình được tính theo các phép toán tích cực. -19- Chương 2: Suy luận tin cậy trong mạng ngang hàng 2.1. Khái niệm tin cậy và quản lí tin cậy a) Khái niệm tin cậy [1]: Tin cậy là mức đặc thù của sự khẳng định chủ quan theo nghĩa một agent sẽ thực hiện một hành động đặc thù trước khi bị giám sát và trước khi gây ảnh hưởng trong phạm vi của hành động. Có ba vấn đề trong định nghĩa tin cậy trên, đó là:  Tin cậy là chủ quan  Tin cậy là ảnh hưởng của những hành động mà không thể giám sát  Mức độ tin cậy phụ thuộc vào các hành động chính nó gây ảnh hưởng như thế nào. b) Quản lí tin cậy [4]: Là cơ cấu cho phép thiết lập tin cậy lẫn nhau. Nổi tiếng là phép đo giúp nhận biết được (bằng trực tiếp hay gián tiếp) các tương tác sớm của các agent và được sử dụng để định giá mức độ tin cậy của một agent so với một agent khác. Tồn tại nhiều phương pháp quản lí tin cậy, tập trung vào các đặc trưng về mặt ngữ nghĩa của mô hình tin cậy. Các phương pháp này chưa tương xứng với độ tin cậy của chúng trong cơ sở dữ liệu tập trung hoặc đòi hỏi tới sự duy trì trong nhận biết tổng thể một agent để cung cấp dữ liệu trong các tương tác sớm. Cũng có những phương pháp quản lí tin cậy dựa trên cả hai phương diện: quản lí dữ liệu và mức ngữ nghĩa. 2.2. Mô hình tin cậy Trong phần này sẽ trình bày tin cậy được định nghĩa như thế nào trong mô hình tin cậy do Alfarez Abdul-Rahman & Stephen Hailes [1] đề xuất thông qua mô tả các phần tử của nó. 2.2.1. Agents Các agent là những thực thể có khả năng thực thi giao thức đề cử (Recommendation Protocol). Đây là điểm khác biệt giữa các agent với các thực thể tĩnh (như máy in hay ổ đĩa chẳng hạn). Mọi thực thể đều có thể được đề cử, nhưng chỉ có các agent là có thể gửi và nhận các đề cử. 2.2.2. Các quan hệ tin cậy -20- Một quan hệ tin cậy tồn tại giữa Alice và Bob khi Alice nắm giữ niềm tin về những điều tin cậy của Bob. Tuy vậy, niềm tin theo hướng ngược lại không cần thiết ở cùng thời điểm. Trong trường hợp khác, quan hệ tin cậy của Alice chỉ là một hướng. Các đặc tính của quan hệ tin cậy là: - Nó luôn xảy ra giữa hai thực thể - Nó không đối xứng (chỉ là một hướng) - Nó là điều kiện chuyển tiếp (bắc cầu) Có hai kiểu quan hệ khác nhau đáng lưu ý là: + Nếu Alice tin cậy Bob thì đây là kiểu quan hệ tin cậy trực tiếp. + Nếu Alice tin cậy Bob để đưa ra đề cử về sự tin cậy của các thực thể khác, thì đây là quan hệ tin cậy đề cử giữa Alice và Bob. Các quan hệ tin cậy chỉ tồn tại bên trong cơ sở dữ liệu của chính mỗi agent. 2.2.3. Loại tin cậy Các agent sử dụng loại tin cậy để biểu thị tin cậy đối với các agent khác theo các cách khác nhau phụ thuộc vào các đặc trưng riêng hoặc theo khía cạnh mà thực thể xem xét ở thời điểm hiện tại. Ví dụ: Chúng ta tin cậy CA chứng thực cặp khóa công cộng (loại Kí- khóa), nhưng không làm chứng cho các trạng thái tin tưởng của sự nắm giữ khóa (loại Tin tưởng). 2.2.4. Giá trị tin cậy Các giá trị tin cậy được sử dụng để giới thiệu các mức độ tin cậy khác nhau mà một agent có thể có với các agent khác. -21- Theo nghĩa tự nhiên thì không có một hệ thống giá trị vũ trụ vì nó sử dụng ứng dụng riêng biệt. Tuy vậy việc chuẩn hóa là quan trọng để một hệ thống được đề xuất. Các giá trị tin cậy trong mô hình này là tương phản với mỗi loại và độc lập với các giá trị tin cậy của loại khác. Có hai kiểu giá trị tin cậy được sử dụng: a) Giá trị tin cậy trực tiếp: thích hợp với quan hệ tin cậy trực tiếp. b) Giá trị tin cậy đề cử : thích hợp với các quan hệ tin cậy đề cử. Sau đây là mô tả cho từng trường hợp cụ thể: Giá trị Ý nghĩa -1 Không tin cậy 0 Bỏ qua, không thể tạo được quan hệ tin cậy về agent 1 Giá trị tin cậy cực tiểu (thấp nhất) 2 Giá trị tin cậy trung bình. Hầu hết các thực thể có giá trị tin cậy này 3 Giá trị tin cậy tốt 4 Hoàn toàn tin cậy thực thể này Giá trị Ý nghĩa -1 Không tin cậy 0 Bỏ qua, không thể tạo được quan hệ tin cậy về agent 1 2 3 4 Tính chính xác của quyết định của đề cử cho sở hữu tính chất tin cậy Ngữ nghĩa giá trị tin cậy trực tiếp Ngữ nghĩa giá trị tin cậy đề cử -22- 2.2.5. Danh tiếng và đề cử Danh tiếng của một agent là chuỗi ba thành phần: định danh (hoặc tên) của agent, loại tin cậy và giá trị tin cậy của agent. Reputation = {Name, Trust-Category, Trust-Value} Một đề cử là một thông tin tin cậy được truyền đạt, trong đó có chứa thông tin danh tiếng. Mỗi agent lưu các bản ghi danh tiếng trong cơ sở dữ liệu riêng của chính nó và sử dụng thông tin này để tạo các đề cử tới các agent khác. 2.3. Xác định người cộng tác Phần này giới thiệu kĩ thuật trong việc xác định những người cộng tác và không cộng tác. Những người sử dụng riêng lẻ có thể suy ra và gán các giá trị “tin cậy” cho những người sử dụng khác. Những giá trị tin cậy được suy ra giống như một người sử dụng xem xét những người sử dụng khác để cùng cộng tác, và được sử dụng để định giá trị tài nguyên trong hệ thống. Phân tích vấn đề suy luận tin cậy theo các giải pháp phân tán trong 2 phần: + Một là thành phần suy luận tin cậy cục bộ mà yêu cầu thông tin tin cậy giữa những thành phần đứng đầu trong hệ thống như đầu vào (input) + Hai là thành phần tìm kiếm phân tán mà có khả năng tập hợp thông tin tin cậy riêng lẻ này để sử dụng như đầu vào đối với các giải thuật suy luận cục bộ. Các hệ thống tồn tại như vậy, ví dụ e-bay, có hệ thống định giá người sử dụng tập trung. Các hệ thống trao đổi tài nguyên khác, như MojoNation cũng thực hiện các giải pháp suy luận tin cậy tập trung. Mục đích đặt ra của các hệ thống là cho phép các ứng dụng mở nơi người sử dụng không đăng kí với một ủy quyền trở thành một thành phần của hệ thống. Các giải pháp tập trung không phân chia trong các hệ thống mở, từ đó những người sử dụng nguy hiểm có thể vượt qua dịch vụ “tin cậy” ở trung tâm với các giao dịch giả mạo. Sử dụng nhiều nhất hệ thống suy luận tin cậy được phân quyền có lẽ là trang Web PGP. Trong hệ thống suy luận tin cậy được phân quyền có thể sử dụng để dự đoán qua các mức tin cậy tùy ý. Không có thành phần thứ 3 tin cậy hoặc nơi tập trung thông tin tin cậy trong hệ thống. Những người sử dụng trong hệ thống chỉ dự -23- trữ thông tin rõ ràng có thể sử dụng đối với lợi ích sở hữu của họ. Một giải thuật phân chia công bằng với lượng dự trữ được giới hạn ở mỗi nút, và có thể sử dụng để thực hiện hiệu quả các ứng dụng phân tán rộng lớn. Hơn nữa các giải pháp trong hệ thống tin cậy cho phép những người sử dụng đơn lẻ tính toán các giá trị tin tưởng cục bộ đối với những người sử dụng khác sử dụng giải thuật suy luận lựa chọn của chính họ, và vì vậy có thể sử dụng để thực hiện một loạt chính sách khác. 2.4. Mô hình suy luận Trong bài viết này, giả sử rằng các hệ thống P2P có thể được phân tích bên trong tập các giao dịch 2 thành phần: Một giao dịch đơn có thể có quan hệ hoạt động nhẹ giống như vận chuyển một truy vấn Gnutella hoặc tiềm tàng một họat động tài nguyên nặng hơn giống như thuê máy chủ tài liệu Chord. Đồng thời cũng giả sử rằng hệ thống gồm có một tập các nút “tốt” mà luôn luôn thực hiện dưới các giao thức chính xác và trọn vẹn, nghĩa là những người tốt luôn thi hành cuối của một giao dịch của họ. Mục đích công việc ở đây là phát triển các giải thuật cho phép những người sử dụng “tốt” định danh được những người “tốt” khác, và như vậy tạo được các nhóm cộng tác thiết thực (robust). Đây là các nhóm máy, với xác suất cao, mỗi thành phần tham gia hoàn thành đầy đủ cuối mỗi giao dịch của họ. Một đề cử về họ các giải thuật phân tán có thể được sử dụng bởi người sử dụng để tính toán giá trị tin cậy đối với mỗi người sử dụng. Giá trị tin cậy đối với nút B ở nút A là độ đo giống như nút A tin tưởng giao dịch với nút B sẽ thành công. Trong hệ thống, mỗi người sử dụng lưu trữ một số giới hạn các thông tin về bao nhiêu người sử dụng khác tin cậy họ, và giải thuật chọn những thông tin gì để lưu trữ và làm thế nào để tìm lại được những thông tin này. Một trong những thông tin thích hợp được tập hợp, những người sử dụng đơn lẻ có thể sử dụng các giải thuật suy luận cục bộ khác để tính toán các giá trị tin cậy. Điều quan trọng cần lưu ý là thừa nhận các nút tốt có khả năng xác định được khi một giao dịch thành công. Rõ ràng trong nhiều trường hợp không rõ được có hay chăng một giao dịch thất bại (ví dụ khi một nút thỉnh thoảng không phục vụ các tài liệu Chord mà nó tự thuê). Thường khó khăn hơn khi xác định phần nào một giao dịch thất bại do bởi hệ thống thất bại hoặc do bởi người sử dụng không cộng tác. -24- Ví dụ: Xem xét trường hợp khi tất cả những người sử dụng cộng tác nhưng tài liệu không được phục vụ, từ đó mạng thất bại. Đây là vấn đề vốn có ở bất kì một hệ thống suy luận tin cậy nào dựa trên các giao dịch chất lượng (quality). Một hệ thống suy luận tin cậy lí tưởng, trong quá khứ, sẽ có khả năng phân loại tất cả những người sử dụng thành các lớp cộng tác hoặc không cộng tác mà không có lỗi. Tuy vậy, điều này không có khả năng trong thực tế vì những người không cộng tác có thể khởi động bên ngoài những người cộng tác. Một số hệ thống, chẳng hạn NICE [8], đã đưa ra được các giải thuật với các mục đích sau:  Cho phép các nút “tốt” tìm các nút khác nhanh hiệu quả: Các nút tốt sẽ có khả năng xác định các nút tốt khác ngoài sự mất mát một lượng lớn các tài nguyên tác động qua lại với các nút nguy hiểm. Điều này cho phép NICE nhanh chóng hình thành các nhóm cộng tác thiết thực.  Các nút nguy hiểm và tương tự sẽ không có khả năng bẻ gãy các nhóm cộng tác bằng cách đưa các thông tin thiếu tới các nút tốt. Đặc biệt, NICE phát triển các giao thức trong đó các nút nguy hiểm nhanh chóng bị tỉa bớt ra ngoài các nhóm cộng tác. Xa hơn, NICE giả thiết các nút nguy hiểm có thể khuếch tán tùy ý thông tin tin cậy, và tập các nút tốt cùng dạng sẽ nhanh chóng chống lại các cuộc tấn công dạng này. 2.5. Mô hình hệ thống tin cậy NICE: NICE là viết tắt của “NICE is the Internet Cooperative Environment” (NICE là môi trường cộng tác trên Internet). Mục đích của NICE là cung cấp phạm vi các giải thuật tính toán tin cậy phân tán. NICE là một platform đối với việc thực hiện các ứng dụng phân tán cộng tác. Các ứng dụng trong NICE mở rộng truy cập tới các tài nguyên ở xa bằng việc trao đổi các tài nguyên cục bộ. Các giao dịch trong NICE bao gồm các trao đổi an toàn các chứng thực tài nguyên. Các chứng thực này có thể được giữ lại với các tài nguyên được đặt tên (ở xa). Những người không cộng tác có thể mở rộng truy cập “tự do” tới các tài nguyên ở xa bằng cách phát hành các chứng thực mà các chứng thực này rốt cuộc không được giữ lại. -25- NICE cung cấp một dịch vụ API tới các ứng dụng đầu cuối và được phân tầng giữa các giao thức tầng ứng dụng và tầng vận chuyển. Kiến trúc thành phần của NICE được giới thiệu ở hình trên. Các ứng dụng tương tác qua lại với NICE sử dụng NICE API, và phát ra lời gọi để tìm các tài nguyên thích ứng. Tất cả các giao thức đổi chác, mua bán, bồi thường được thực hiện bên trong NICE và không bộc lộ tới ứng dụng. Các giao thức con này chia sẻ thông tin bên trong chính nó và được điều khiển bởi người sử dụng sử dụng các chính sách theo nút (per-node). Các máy NICE được sắp xếp bên trong giao thức báo hiệu (signaling) sử dụng giao thức đa phát tầng ứng dụng. Tất cả các thông báo đặc trưng giao thức NICE khi gửi sử dụng đơn phát trực tiếp hoặc đa phát qua giao thức báo hiệu này. Định danh người sử dụng NICE: sau đây sử dụng thuật ngữ nhóm người sử dụng (user) và nút (node) theo dạng tổng quát. Trong NICE, mỗi người sử dụng chọn một định danh kiểu PGP (See www.pgpi.org). Định danh chứa một bản mã chuỗi nhận dạng và một khóa công cộng. Khóa kết hợp với định danh NICE được sử dụng trong việc kí các chứng thực tài nguyên, trong trao đổi tài nguyên và trong việc gán các giá trị tin cậy. Điều đó là quan trọng để lưu ý rằng không khóa với cả không định danh NICE cần thiết để được đăng kí ở một trung tâm ủy quyền bất kì; tuy vậy, cho dù NICE sử dụng các khóa chung, nhưng không đòi hỏi bất kì dạng PKI toàn cục. Tuy thế, NICE có thể được sử dụng để thực hiện các ứng dụng P2P mở bên ngoài bất kì trung tâm ủy quyền nào. Vì lẽ không có trung tâm đăng kí ủy quyền trong NICE, một người sử dụng có thể tạo ra một số tùy ý các khóa và giả mạo. Tuy vậy, trong NICE, sự định giá được ghép với định danh và nó có lợi để bảo vệ khóa đơn của người sử dụng và không thay đổi các khóa thường xuyên. Tính -26- chất này làm cho các ứng dụng của NICE chống được một số các tấn công DoS, điều mà xảy ra được với các hệ thống P2P khác. Trong NICE, các hành động ứng dụng ở xa được chuyển thành các yêu cầu tài nguyên cục bộ, và nếu tiện lợi, các tài nguyên cục bộ này được đổi chác với các tài nguyên khác ở các nút ở xa (Nó cũng được tham gia để mua bán các tài nguyên thành phần thứ 3 mà lẽ ra chỉ là đổi chác các tài nguyên cục bộ). Hy vọng không phải mọi yêu cầu ở xa chuyển qua NICE; thay vào đó, những người sử dụng trao đổi và mua bán các đơn vị tài nguyên (giống như 100Mb lưu trữ trong 10 ngày, vv). Các tài nguyên đã được xác định sử dụng một phiên bản đơn giản của W3 RDF. NICE cung cấp các dịch vụ sau đây:  Xác định và quảng cáo tài nguyên  Bảo đảm việc trao đổi và mua bán tài nguyên  Định giá “tin cậy” phân tán. Các máy trong NICE đổi chác tài nguyên bằng việc trao đổi các thông báo “giao dịch”. Một thông báo giao dịch định danh tập các tài nguyên chủ yếu tự nguyện để trao đổi. Sự tích hợp của thông báo giao dịch để đảm bảo sử dụng chữ kí băm đồng hành theo thông báo. Trong NICE sử dụng sơ đồ dựa trên Beaconing để mở rộng việc thông báo và xác định các tài nguyên có hiệu lực. NICE sử dụng một giải thuật trao đổi mới dựa trên các giao thức vận chuyển để trao đổi các chứng thực tài nguyên. Giao thức này đảm bảo rằng không bộ phận nào có thể thu được một chứng thực có thể dùng được ngoài những chứng thực có hiệu lực được phát hành. Các chứng thực tài nguyên này cuối cùng được giữ ở các nút phát hành. Các nút tốt luôn luôn giữ bất kì chứng thực mà chúng phát ra, trong khi các nút nguy hiểm có thể chọn không làm như vậy. Trong phạm vi của NICE, mục đích đặc biệt của bài viết này là phát triển các giải thuật để định danh các nút mà phát ra (hoặc giữ) các chứng thực tốt. NICE mô tả thành phần suy luận tin cậy, các kết quả của hệ thống này được sử dụng để định giá các tài nguyên trong NICE như thế nào. Chính sách định giá và mua bán : Mục đích của các chính sách mặc định trong NICE là giới hạn các tài nguyên mà có thể bị tiêu thụ bởi các nhóm người nguy hiểm. Các chính sách -27- này được kết hợp với sự tính toán tin cậy được sử dụng để định danh các nút không hoạt động (misbehaving). Trong thực tiễn, những người sử dụng NICE có thể sử dụng bất kì chính sách riêng biệt, và có thể cố gắng để được số tài nguyên lớn nhất qua mua bán số tài nguyên được họ sở hữu. Mục đích chính của các chính sách mặc định là cho phép những người sử dụng tốt hình thành các nhóm cộng tác và không bị mất một lượng lớn tài nguyên cho những người nguy hiểm. Các chính sách định giá và mua bán được sử dụng để đề phòng chống lại những người sử dụng mà phát hành các chính sách tài nguyên giả mạo sử dụng nhiều đặc tính giống NICE. Trong NICE sử dụng 2 cơ cấu để bảo vệ sự tích hợp nhóm như sau: - Định giá dựa trên tin cậy Trong định giá dựa trên tin cậy, các tài nguyên được định giá tỉ lệ tương hỗ độ tin cậy nhận biết được. Giả sử khoảng giá trị tin cậy giữa 0 và 1, và xem xét giao dịch đầu tiên giữa Alice và Bob nơi suy ra được giá trị tin cậy từ Alice tới Bob là TAlice(Bob) =0.5 và TBob(Alice) =1.0. Theo định giá dựa trên tin cậy, Alice sẽ chỉ đổi chác với Bob nếu Bob tỏ ra có nhiều tài nguyên hơn cái anh ta nhận trở về. Lưu ý rằng Bob điều khiển nhiều giao dịch thành công hơn với Alice, giá chênh lệch sẽ giảm. Chính sách này là động cơ thúc đẩy bởi sự quan sát rằng Alice mua bán với độ tin cậy thấp cô ta gặp nguy cơ lớn không nhận được dịch vụ trở lại, mà được phản ánh trong sự định giá. - Các giới hạn mua bán dựa trên tin cậy Trong các chính sách này, thay vì thay đổi giá của tài nguyên, chính sách thay đổi tổng số tài nguyên mà Alice mua bán. Ví dụ, trong cốt chuyện giữa Alice và Bob, Alice có thể cho phép Bob lưu trữ 1 Mb dữ liệu ở máy của cô ấy trong 1 ngày, và từ từ tăng lưu trữ và thời gian khi cô ấy hoàn thành việc lưu trữ các chứng thực tài nguyên của Bob. Chính sách này đảm bảo rằng khi mua bán chủ yếu bằng quan hệ tin cậy thấp, Alice kề cận với số tài nguyên cô ta có thể mất. Phân loại đối tượng người sử dụng trong NICE Có 3 đối tượng người sử dụng: Người sử dụng tốt: Những người sử dụng tốt luôn thực hiện giao thức đúng đắn. Nếu người sử dụng tốt quan hệ với người sử dụng tốt khác thì giá trị cookie được kí luôn là 1. -28- Những người sử dụng bình thường: Những người sử dụng bình thường luôn thực hiện giao thức đúng đắn. Tuy vậy khi một người sử dụng bình thường quan hệ qua lại với một người khác, kết quả các giao dịch trong định giá cookie trong khoảng giữa 0.0 và 1.0, trung bình là 0.7. Những người sử dụng nguy hiểm: mỗi người sử dụng nguy hiểm luôn báo độ tin cậy tuyệt đối (giá trị cookie là 1.0) với mỗi người sử dụng nguy hiểm khác. Những người sử dụng nguy hiểm quan hệ qua lại với người sử dụng không nguy hiểm khác thì người sử dụng nguy hiểm tạo ra giá trị cookie tin cậy cao (giữa 0.9 và 1.0) hoặc rất thấp (khoảng giữa 0.0 và 0.1). Xác xuất giao dịch thất bại là giống nhau và ngẫu nhiên. 2.6. Tính toán tin cậy phân tán trong NICE Giả sử rằng với mỗi giao dịch trong hệ thống, mỗi người sử dụng liên quan tạo một bản tuyên bố được ký (và gọi là cookie) về chất lượng của giao dịch. Ví dụ: xem xét giao dịch đầy đủ t giữa những người sử dụng Alice và Bob trong đó Alice tiêu thụ một tập tài nguyên của Bob. Sau khi giao dịch hoàn thành, Alice kí một cookie với tình trạng c mà cô ấy đã hoàn thành đầy đủ giao dịch t với Bob. Bob có thể chọn lưu trữ cookie c này được kí bởi Alice cho việc sử dụng sau này để chứng tỏ độ tin cậy của Bob với những người sử dụng khác, bao gồm cả Alice. Như tiến trình hệ thống, mỗi giao dịch tạo một cookie mới và được lưu trữ bởi những người sử dụng khác. (Rõ ràng các cookie sẽ hết hạn hoặc trong trường hợp khác sẽ bị hủy). Sau đây là mô tả giải thuật suy luận tin cậy trong phạm vi của đồ thị có hướng T và gọi là đồ thị tin cậy. Các đỉnh trong T thể hiện chính xác những người sử dụng trong hệ thống. Có một cạnh nối trực tiếp từ Alice tới Bob nếu và chỉ nếu Bob lưu giữ một cookie của Alice. Giá trị của cạnh Alice → Bob biểu thị Alice tin cậy Bob bao nhiêu, và phụ thuộc vào tập các cookie Bob nắm giữ của Alice. Chú ý rằng mỗi giao dịch trong hệ thống có thể thêm một cạnh có hướng mới khác trong đồ thị tin cậy, hoặc dán lại nhãn giá trị của cạnh đã có với giá trị tin cậy mới của nó. Giả sử rằng phiên bản hiện tại của đồ thị tin cậy T là có hiệu lực với Alice và thừa nhận Alice mong muốn tính toán một giá trị tin cậy đối với Bob. Nếu Alice và Bob có các giao dịch trước, sau đó Alice có thể tìm kiếm giá trị của cạnh Alice → Bob trong T. Tuy vậy, giả sử Alice và Bob không bao giờ có -29- một giao dịch trước. Alice có thể suy ra giá trị tin cậy đối với Bob bằng các đường có hướng tiếp theo (kết thúc ở Bob) trong đồ thị tin cậy. 2.6.1. Suy luận tin cậy trong đồ thị tin cậy Xem xét đường dẫn có hướng A0 → A1 →…→ Ak trong T. Mỗi cặp kế tiếp là những người sử dụng có các giao dịch trực tiếp với người khác, và các giá trị cạnh là độ đo nói lên Ai tin cậy bao nhiêu Ai+1. Cho một đường dẫn như vậy, A0 có thể suy ra số các giá trị tin cậy hợp lý đối với Ak, bao gồm giá trị nhỏ nhất của một cạnh bất kì trong đường dẫn hoặc tích của các giá trị tin cậy dọc theo đường dẫn. Gọi các giá trị tin cậy suy ra được này là sự khỏe mạnh (strength) của đường dẫn A0 → Ak. Bài toán suy luận là những gì khó hơn tính toán độ khỏe mạnh của các đường dẫn tin cậy vì rằng có thể có nhiều đường dẫn giữa 2 nút, và những đường dẫn này có thể chia sẻ các cạnh hoặc các đỉnh. Suy luận tin cậy tập trung không tập trung ở bài viết này, nhưng nó quan trọng cho việc sử dụng giải thuật suy luận thiết thực. Trong mô tả sau đây, giả sử A (Alice) truy cập tới đồ thị tin cậy, và muốn suy ra giá trị tin cậy đối với B (Bob): Đường dẫn khỏe nhất: Lấy một tập các đường dẫn giữa Alice và Bob, Alice chọn đường dẫn khỏe nhất và sử dụng giá trị tin cậy nhỏ nhất trong đường dẫn làm giá trị tin cậy đối với Bob. Độ khỏe của một đường dẫn có thể được tính bằng cách làm cực tiểu giá trị cạnh dọc theo đường dẫn hoặc tính tích của tất cả các cạnh dọc theo đường dẫn. Cho đồ thị tin cậy, việc đo độ tin cậy này có thể tính được bằng cách sử dụng tìm kiếm theo chiều sâu (depth-first search). Trong ví dụ mô tả trong hình 2, có sử dụng hàm cực tiểu để tính độ khỏe của đường dẫn. Trong ví dụ này, đường dẫn khỏe nhất là AEFB, và Alice suy ra mức tin cậy là 0.8 đối với Bob. Hình 2: Đồ thị tin cậy -30- Phương pháp tính trung bình trọng số theo các đường dẫn rời rạc khỏe nhất: Thay cho sự lựa chọn chỉ đường dẫn khỏe nhất, Alice có thể chọn cách góp từ tất cả các đường dẫn rời rạc. Tập các đường dẫn rời rạc này không duy nhất, nhưng tập các đường dẫn rời rạc khỏe nhất là và có thể tính được bằng cách sử dụng các luồng mạng với sự thu hẹp luồng trong các đỉnh. Cho một tập các đường dẫn rời rạc, Alice có thể tính giá trị tin cậy đối với Bob bằng việc tính trung bình trọng số của độ khỏe của tất cả các đường rời rạc khỏe nhất. Trọng số được gán cho đường Alice→X→... →Bob là giá trị của cạnh Alice → X (được giải thích là Alice trực tiếp tin cậy X bao nhiêu). Trong ví dụ trong hình 2, ACDB là đường rời rạc khác (với độ khỏe mạnh 0.6), và suy ra giá trị tin cậy từ Alice tới Bob là 0.72. Cách tính như sau: Trước tiên tìm đường dẫn khỏe nhất (AEFB, hoặc 0.9 -> 0.8 ->0.9 với trọng sô cực tiểu 0.8), loại bỏ các cạnh đó, tìm đường khỏe nhất tiếp theo (ACDB, 0.6 -> 0.7 -> 0.9 với trọng số cực tiểu là 0.6). Như vậy, lấy 2 đường, Alice tính được trung bình cực tiểu của mỗi đường, trọng số tính được bằng giá trị của chặng (hop) sau cùng. Theo đó, đường AEFB có trọng số cực tiểu 0.8 với liên kết AE có giá trị 0.9, cũng tương tự đường ACDB có trọng số cực tiểu 0.6 với liên kết chặng sau cùng (AC) có trọng số 0.6. Vậy trung bình trọng số tính được là (0.6*0.6 + 0.8*0.9)/ (0.6 + 0.9) và bằng 0.72. Cả hai giải thuật này đều thiết thực trong ý nghĩa rằng không có giá trị cạnh nào được sử dụng nhiều hơn một lần, và các giá trị tin cậy được tính luôn luôn bị chặn trên bởi giá trị tin cậy cực tiểu của một đường. Trước khi bất kì một giải thuật cục bộ như vậy được sử dụng, đồ thị tin cậy thu được có thể thay đổi, và các giá trị (cạnh) được gán cho các cookie. Chú ý rằng để suy ra độ tin cậy đối với Bob, Alice không cần toàn bộ đồ thị tin cậy, mà chỉ cần tập các đường từ cô ấy tới Bob. 2.6.2. Gán các giá trị cho các cookie Về ý tưởng, sau mỗi giao dịch, có thể thực hiện được việc gán một số thực trong khoảng giá trị thực [0, 1] cho chất lượng của giao dịch và số được gán này là giá trị của cookie. Trong một số trường hợp, các giao dịch có thể được tổ chức như vậy là có thể thực hiện được: như trường hợp giả sử rằng Alice chuyển mã và cung cấp 400 Kbps dòng video cho Bob ở 128 Kbps, và theo sự chấp thuận trước, Bob kí một cookie với giá trị 0.75 cho Alice. Trường hợp giao dịch tương tự có thể cho kết quả một cookie với giá trị 0.9 nếu Alice -31- thực hiện việc cung cấp dòng 256 Kbps. Trong nhiều trường, tuy vậy, không rõ phải gán số thực như thế nào để đảm bảo đo chất lượng các giao dịch. Như trong ví dụ trước, Alice có thể tuyên bố rằng cô ấy đã cung cấp dòng 256 Kbps, trong khi xảy ra xung đột mạng ở đường liên kết truy cập tới Bob làm giảm chất lượng xuống còn 128Kbs. Điều đó, trong thực tế, dễ tạo ra các trường hợp không thực hiện được việc kiểm tra chất lượng của dịch vụ. Tuy vậy, trong hầu hết các trường hợp đều có thể gán giá trị {0, 1} cho một giao dịch, nghĩa là có hay chăng một giao dịch thành công hay thất bại. Trong ví dụ trước, Bob và Alice thương lượng tỉ lệ ngưỡng (64 kbps) ở thời điểm mà Bob xem xét giao dịch thành công, và gán cookie giá trị 1 cho Alice bất chấp việc có hay chăng dữ liệu đã được phân phối ở 65.5 Kbps hoặc 400 Kbps. Xa hơn nữa, đối với nhiều giao dịch, như việc phân phối dòng phương tiện, thì có thể thực hiện với một phần để bỏ qua giao dịch nếu chất lượng dịch vụ ban đầu không vượt quá ngưỡng giá trị 0. 2.6.3. Suy luận tin cậy phân tán: Giải thuật cơ bản Phần này mô tả những người sử dụng xác định thông tin tin cậy về những người sử dụng khác trong một hệ thống như thế nào. Giải thuật phân tán này thực hiện như sau: Mỗi người sử dụng lưu trữ một tập các cookie được kí, các cookie được kí này là kết quả nhận được từ các giao dịch trước đó. Giả sử Alice muốn sử dụng một vài tài nguyên ở nút của Bob. Có 2 khả năng: hoặc Alice đã có sẵn các cookie của Bob, hoặc cả Alice và Bob không có bất kì một giao dịch nào như vậy. (Có một khả năng thứ 3 là Alice đã loại bỏ các cookie của Bob, nhưng trường hợp này được coi giống như Alice không có cookie của Bob). Trong trường hợp Alice sẵn có các cookie của Bob, cô ấy giới thiệu chúng cho Bob. Bob có thể xác nhận rằng các cookie này thực sự là của anh ấy từ khi anh ấy kí chúng. Nhận được các cookie này, Bob có thể tính ngay giá trị tin cậy đối với Alice. Trong trường hợp khi mà Alice không có cookie của Bob. Vậy thì Alice sẽ tìm kiếm các cookie của Bob từ các nút của những người mà cô ấy nắm giữ các cookie. Giả sử Alice có một cookie của Carol và Carol có cookie của Bob. Carol đưa cho Alice một bản sao các cookie mà cô ấy nhận từ Bob, Alice sau đó sẽ giới thiệu 2 cookie cho Bob: một của Bob đưa cho Carol và một của Carol đưa cho Alice, kết quả là Alice nói với Bob: “Anh không biết tôi nhưng tôi tin tưởng Carol và Carol tin tưởng tôi”. Nói chung Alice có thể tạo nhiều “đường -32- cookie” như vậy bằng cách tìm kiếm đệ quy qua hàng xóm của cô ta. Kết quả là Alice làm ngập lụt các truy vấn bởi các cookie của Bob dọc theo các cạnh cookie mà các cạnh này kết thúc ở mỗi nút, bắt đầu với nút sở hữu của cô ta. Sau khi tìm kiếm hết, cô ta có thể mô tả Bob bằng sự kết hợp các đường dẫn có hướng mà tất cả các đường dẫn này bắt đầu từ Bob và kết thúc ở Alice. Lưu ý rằng các đường dẫn cookie này đúng bằng sự kết hợp các cạnh có hướng trong đồ thị tin cậy mà được sử dụng trong suy luận tin cậy tập trung. Thêm nữa, với tập các cookie này, Bob có thể sử dụng sơ đồ tập trung bất kì để suy ra giá trị tin cậy đối với Alice. Sơ đồ cơ bản này có một vài điểm lưu ý là:  Nếu Alice muốn sử dụng tài nguyên của Bob, cô ta sẽ tìm kiếm các cookie của Bob. Điều này tương phản với sơ đồ tương tự trong đó các nút tự chúng giữ các bản ghi của các giao dịch trước của chúng. Không như thiết lập, nếu Bob không biết Alice, anh ta sẽ bắt đầu tìm kiếm Alice qua các nút mà anh ta tin cậy. Một người sử dụng nguy hiểm Eve có thể dễ dàng gắn một cuộc tấn công từ chối dịch vụ (DoS) bằng cách liên tiếp hỏi các nút khác để tìm kiếm các ủy nhiệm của Eve. Trong trường hợp các nút chuyển các truy vấn đại diện các nút khác chỉ nếu các nút ủy quyền đã kí cookie, và như vậy, ngầm tin cậy chúng ở một chừng mực nào đó.  Alice dự trữ các cookie được thừa nhận dưới dạng “X tin cậy Alice”. Hơn nữa, Alice chỉ dành vùng dự trữ các đối tượng mà cô ta có thể sử dụng cho lợi ích của mình, và như vậy, có một động cơ xây dựng trong hệ thống để dự trữ các cookie. Trong thực tế, nếu Bob kí một cookie giá trị thấp cho Alice, cô ta có thể loại bỏ các cookie này ngay, vì lẽ điều này giống như có một công bố rằng Bob không tin cậy Alice. Nói chung, người sử dụng dự trữ các cookie nhiều nhất cho mục đích sở hữu của họ, và không chuyển các thông báo của những người sử dụng mà họ không tin cậy.  Dự trữ bản ghi giao dịch trong hệ thống là hoàn toàn phân tán, và nếu hai nút quản lý một số lớn các giao dịch giả mạo, chỉ khi chúng chọn nắm giữ trạng thái kết quả. Ngược với điều này, là trong dự trữ giao -33- dịch trung tâm, các nút này có thể dễ dàng gắn một tấn công DoS bằng cách làm ngập dự trữ giao dịch với các bản ghi giao dịch giả mạo. 2.6.4. Phép lọc Truy vấn làm lụt phần nào không có khả năng sử dụng các tài nguyên phân tán, và những nút nguy hiểm thường xóa mọi thông tin về những hành động xấu của chúng bằng cách vứt bỏ các cookie giá trị thấp mà chúng nhận được. Sau đây là 3 cách lọc của sơ đồ cơ bản. - Tìm kiếm hiệu quả: Thủ tục làm ngập lụt đệ qui được mô tả ở trên tìm tất cả các cookie tồn tại đối với ủy nhiệm đã cho. Tuy vậy nó rất không hiệu quả, vì lẽ nó thăm số nút ở mỗi bậc lớn lên theo hàm mũ. Hơn nữa, trừ phi việc làm lụt bằng lí do này hay lí do khác được rút ngắn, ví dụ bằng việc sử dụng thu hồi trùng lặp hoặc bằng việc sử dụng trường thời gian sống (time-to-live) trong các truy vấn, thì một vài tìm kiếm có thể luân chuyển mãi trong hệ thống. Việc tìm kiếm được xem xét để sử dụng cấu trúc tìm kiếm P2P, giống như Chord, để xác định các cookie. Các giao thức sử dụng ở đây giống như nhiều giao thức định tuyến trong Internet và có những đặc tính như: không thừa nhận sự tồn tại của các bảng định tuyến, phải thiết thực để chống lại sự mất mát các packet, chống lại các nút nguy hiểm,...và để việc tìm kiếm hiệu quả hơn còn phải cần tới cơ cấu hỗ trợ khác nữa. Thay cho mọi đường dẫn tương ứng tới tất cả các cookie, ta chỉ chuyển tiếp một truy vấn tới một số các nút (điển hình là 5) từ một nút bất kì. Tuy vậy, nếu chúng ta chọn chuyển tiếp các nút ngẫu nhiên, chúng ta vẫn sẽ có một phép tìm kiếm hàm mũ, mặc dù với cơ số nhỏ hơn! Thay vì như vậy, chúng ta mở rộng giao thức cơ bản như sau: bất cứ khi nào một nút nhận một cookie từ các nút khác, nó cũng nhận bản ghi nhớ của tất cả các cookie của các nút đó ở các -34- nút ở xa. Vì lẽ đó, trong cài đặt số các cookie ở mỗi nút là hoàn toàn nhỏ (điển hình khoảng 40 so với 2048 nút hệ thống), bản ghi nhớ này có thể được mã hóa sử dụng ít hơn 1000 bits trong bộ lọc Bloom. Như vậy, không gian dự trữ được yêu cầu cho bản ghi nhớ là không đáng kể (khoảng 128 bytes) nhưng chúng cho phép chúng ta trực tiếp tìm kiếm các cookie đặc biệt với sự chính xác rất cao. Tư tưởng sử dụng bản ghi nhớ trong tìm kiếm được sử dụng sớm, ví dụ như tìm kiếm trong bộ nhớ cache.Trong thực tế, trường hợp tìm kiếm cơ bản sử dụng các bộ lọc Bloom yếu; trong các thí nghiệm cho thấy không cần sử dụng mọi bộ lọc Bloom yếu – chỉ một mức lọc là đủ. Cuối cùng mỗi nút cũng giữ một bản ghi nhớ các tìm kiếm thực thi gần đây và sử dụng bản ghi nhớ này để ngăn chặn các truy vấn trùng nhau. Trong cài đặt, khi chọn các nút để chuyển tiếp, luôn chọn các nút mà bản ghi nhớ biểu thị chúng có cookie đối với node cần tìm kiếm. Tuy vậy có thể xảy ra rằng không gặp trong bản ghi nhớ bất kì ở một nút; trong trường hợp này, ta chọn lại các nút để chuyển tiếp một cách ngẫu nhiên. Vì vậy chỉ chuyển tiếp ngẫu nhiên các nút được chọn nếu truy vấn ở bên trong số các chặng định trước xa nguồn truy vấn. Như vậy, trong phiên bản tìm kiếm cuối cùng, một truy vấn xảy ra từ nguồn, có thể chọn các nút ngẫu nhiên, nhưng việc làm lụt nhanh chóng được dừng lại trừ phi gặp (hit) trong bản ghi nhớ chặng tiếp theo. Ví dụ: Minh họa thủ tục tìm kiếm dựa trên bản ghi nhớ (hình 3): Alice muốn sử dụng tài nguyên Bob có, nhưng lại không có các cookie của Bob. Vì vậy Alice bắt đầu tìm kiếm một đường cookie tới Bob. Trong hình 3-0 mô tả trạng thái đầu của các cookie và các bản ghi nhớ của mỗi người sử dụng, ví dụ Alice có cookie giá trị 0.9 từ C, và bản ghi nhớ của cô từ C thể hiện rằng C có cookie từ D. Với ví dụ này giả sử bậc tìm kiếm là 3, và chặng làm lụt ngẫu nhiên giới hạn là 1. Alice đầu tiên gửi truy vấn không chỉ tới các nút có bản ghi nhớ gặp (chẳng hạn E), nhưng cũng tới các nút ngẫu nhiên (chẳng hạn C và D) như được minh họa trong hình 3-1. Sau khi nhận truy vấn, E tìm cookie của Bob và trả lại truy vấn cho Alice. Khi C nhận truy vấn, anh ta tìm truy vấn mà hàng xóm của anh ta không có bản ghi nhớ đối với Bob, vì vậy không chuyển tiếp truy vấn đi nữa. Theo vậy, D chuyển truy vấn tới G (hình 3-2) khi G có bản ghi nhớ đối với Bob, và G trả lại truy vấn cho Alice với cookie cô ta nhận được từ Bob. Hình 3-3 mô tả 2 đường Alice tìm kiếm, với đường khỏe nhất được in dậm. -35- - Các Cookie từ chối: Một nhược điểm lớn với sơ đồ nguyên bản là các giao dịch định giá thấp tiềm tàng nguy cơ không được ghi vào trong hệ thống. Xem xét kịch bản sau đây: Eve sử dụng một tập các tài nguyên của Alice, nhưng không cung cấp các tài nguyên đã thỏa thuận mà cô ta đã hứa. Trong sơ đồ nguyên bản, Alice sẽ kí một cookie định giá thấp cho Eve. Eve sẽ không có động cơ để giữ cookie này và sẽ nhanh chóng hủy nó, vì vậy xóa luôn bản ghi bất kì về ý đồ xấu của cô ta. Thay vì như vậy, Alice tạo cookie này và tự mình lưu trữ nó. Đó là điều lí thú của Alice để nắm giữ cookie này; ít nhất cô ấy sẽ không tin cậy Eve lâu như cô ấy có cookie này. Tuy vậy “các cookie từ chối” này có thể cũng được sử dụng bởi những người sử dụng tin cậy Alice. Giả sử Eve ở lần tiếp theo muốn quan hệ qua lại với Bob. Trước khi Bob chấp nhận một giao dịch với Eve, Bob có thể bắt đầu tìm kiếm các cookie từ chối đối với Eve. Thủ tục tìm kiếm như sau: đi theo các cạnh tin cậy cao bên ngoài Bob và kết thúc khi tìm thấy một cookie từ chối đối với Eve. Kết quả là việc tìm kiếm trả lại một danh sách những người mà Bob tin cậy, đó là những người có các giao dịch từ chối với Eve trước đó. Nếu Bob khám phá đủ một tập các cookie từ chối đối với Eve, anh ta có thể chọn giải pháp không đếm xỉa đến các giấy ủy quyền của Eve và không đi cùng cô ta đề xuất giao dịch. Điều này quan trọng để lưu ý rằng Bob chỉ bắt đầu tìm kiếm cookie từ chối khi Eve đã tạo một tập các giấy ủy nhiệm tin cậy đầy đủ; trường hợp khác, Bob lại tạo ra sự tấn công DoS khi anh ta tiếp tục tìm kiếm cookie xấu. Trong cài đặt, ta giữ một tập các bản ghi nhớ đối với các cookie từ chối, nhưng thực hiện bộ lọc Bloom tìm kiếm trực tiếp đối với các cookie từ chối này chỉ trong các nút lân cận. - Danh sách ưu tiên: Để khám phá tiềm tàng các nút tốt hiệu quả, mỗi người sử dụng giữ một danh sách ưu tiên. Với mỗi người sử dụng, các nút trong danh sách ưu tiên chứa một tập những người sử dụng khác mà người sử dụng đó không điều khiển được giao dịch với họ ngay. Tuy vậy các nút này được ưu tiên vì lẽ chủ sở hữu danh sách ưu tiên tin tưởng chúng có thể tiềm tàng các máy tin cậy cao. Các nút được chứa trong danh sách ưu tiên như sau: giả sử Alice điều khiển tìm kiếm cookie thành công đối với Bob và cho P là đường dẫn cookie được khám phá giữa Alice và Bob. Alice thêm tất cả những người sử dụng trong P đó là những người có giá trị tin cậy rất cao (1.0 trong cài đặt) tới danh sách tin -36- cậy của cô ấy. Triển vọng là chỉ những người sử dụng mà Alice không có các bản ghi giao dịch là được thêm vào danh sách ưu tiên của cô ấy. Tóm tắt giải thuật định giá tin cậy phân tán làm việc như sau: Các nút yêu cầu tài nguyên giới thiệu giấy ủy nhiệm của chúng cho người sở hữu tài nguyên. Mỗi giấy ủy nhiệm là một tập các chứng thực được kí hình thành từ người sở hữu tài nguyên. Tùy thuộc tập các ủy quyền, người sở hữu tài nguyên có thể chọn để điều khiển tìm kiếm ưu tiên. Tin cậy cuối cùng được tính là hàm của cả các giấy ủy nhiệm và các ưu tiên. 2.7. Các hệ thống tin cậy khác Chủ đề “tin cậy” trong các hệ thống phân tán sử dụng các tính chất tin cậy của xã hội. Công việc này dựa vào kinh nghiệm sở hữu agent để đạt được đoạn [-1, 1] – là đoạn tin cậy được chuộng, nhưng không suy ra được tin cậy qua các agent. Ở phần trên đã giới thiệu mô hình tin cậy do nhóm Abdul-Rahman [1] mô tả, có quan hệ với kinh nghiệm trực tiếp và thông tin danh tiếng. Mô hình này có thể được sử dụng, giống như trong NICE để suy ra tin cậy. Trong một bài viết khác, Yu et al. [5] đề xuất một cách tính toán độ tin cậy thực trong đoạn [-1, 1] từ những tương tác trực tiếp với các agent khác. Sản phẩm của các giá trị tin cậy được sử dụng với tính toán danh tiếng, và các agent không ưa thích tránh được bằng việc quan sát các giao dịch xấu khuếch tán thông tin về agent trên toàn mạng. Công việc này chủ yếu là sử dụng các cơ cấu xã hội trong sắp đặt những người sử dụng thuộc lĩnh vực điện tử, và các kĩ thuật được phát triển ở đây cũng được sử dụng trong NICE. Hệ thống khác [4] tập trung vào việc quản lí và tìm kiếm dữ liệu quan hệ tin cậy, và sử dụng một cơ sở dữ liệu phân tán P2P lựa chọn, trong đó lưu giữ những đề xuất riêng nếu các giao dịch với chúng không thỏa. Khi một agent p muốn định giá sự tin cậy với một agent q, nó gửi một truy vấn dữ liệu đề xuất mà bao hàm q, và quyết định độ tin cậy của q với dữ liệu được trả về, sử dụng một công thức được định sẵn. Tuy vậy hệ thống này hoàn toàn giả thiết rằng tất cả các thành phần tham gia tương tự nhau sẵn sàng chia sẻ tải dữ liệu chung, cái mà không thật đúng trong nhiều hệ thống P2P. Một hệ thống như vậy cũng có điểm yếu đối với các cuộc tấn công DoS, như không có sự ngăn cản giới hạn việc thêm tùy ý các đề xuất vào trong hệ thống. -37- PGP [10] là một mô hình tin cậy phân tán khác tập trung vào việc cung cấp định danh những người nắm giữ khóa. PGP sử dụng ngưỡng định nghĩa người sử dụng để quyết định một khóa là tin cậy hay không, và những người giới thiệu khác có thể tin cậy một tập nhất định các mức tin cậy khác nhau. Không giống như NICE, tin cậy trong PGP chỉ theo một mức gián tiếp; ví dụ nếu A thử tin cậy B, có thể có nhiều nhất một người, C, trong đường tin cậy giữa A và B. Cũng có một số các web site cộng đồng, như e-bay và Advogato (xem www.advogato.org) sử dụng các mô hình tin cậy để phục vụ người sử dụng. Tuy vậy tất cả dữ liệu đối với các site này được lưu trữ ở cơ sở dữ liệu tập trung tin cậy, điều này không phù hợp với các hệ thống mở, và dẫn đến thường tạo ra khả năng và điểm chọn lựa thất bại. -38- Chương 3: Đảm bảo công bằng với các ứng dụng cộng tác trong mạng ngang hàng 3.1. Giới thiệu Vấn đề đặt ra đối với các ứng dụng cộng tác trong mạng ngang hàng là khi một ứng dụng chia sẻ tài nguyên của mình cho những người sử dụng khác trong nhóm cộng tác thì ứng dụng này được đánh giá về sự cộng tác như thế nào, và khi các ứng dụng cùng muốn lấy tài nguyên tại một nút thì mỗi ứng dụng sẽ được xem xét thứ tự về quyền ưu tiên ra sao ? Đảm bảo công bằng trong chia sẻ tài nguyên, đặc biệt khi có nhiều ứng dụng cùng muốn lấy tài nguyên từ một nguồn chia sẻ tài nguyên, thì ứng dụng phải nhận biết được nhau, tin cậy được với nhau, đồng thời phải có một cơ chế ưu tiên trong cấp phát nguồn tài nguyên chia sẻ (vì ứng dụng nào cũng muốn giành lấy tài nguyên chia sẻ đó). Tin cậy và quản lí được tin cậy là một vấn đề đặc biệt quan trọng trong môi trường P2P, nơi mà thường xuyên bắt gặp các agent chưa nhận biết được. Đảm bảo công bằng cho các ứng dụng cộng tác ngang hàng theo nghĩa một ứng dụng lấy nhiều tài nguyên, thì phải có quyền khai thác từ nhiều nơi. Tuy vậy, quyền khai thác (giành lấy tài nguyên) và thứ tự ưu tiên sẽ được xem xét. Có rất nhiều các ứng dụng, đặc biệt là các trang Web trong thương mại điện tử sử dụng phương pháp định giá trị người sử dụng thông qua việc tính điểm trên trang Web của mình. Mỗi người sử dụng khi muốn lấy tài liệu trên Website sẽ được gắn một tài khoản với tên gọi “accountname” và được tính điểm, khởi đầu là 0. Nếu muốn lấy tài nguyên (downnload dữ liệu chẳng hạn), thì số điểm của “accountname” phải thỏa mãn ở mức tối thiểu nào đó (điều này phụ thuộc vào qui định ngưỡng tối thiểu và cách tính điểm của mỗi trang Website). Chẳng hạn nếu muốn download một tài liệu thì số điểm của “accountname” phải có ít nhất là 250 điểm, và khi upload một tài liệu thì người sử dụng có thể được cộng thêm 250-500 điểm vào tài khoản “accountname”. Càng nhiều điểm thì dung lượng hoặc số tập tin có thể được download sẽ càng lớn. Nếu số điểm ít thì chỉ có thể download được một số ít tập tin của Website hoặc không, lúc này người sử dụng được khuyến cáo nạp tiền hoặc upload dữ liệu vào tài khoản của mình (có thể qua tin nhắc SMS hoặc mua thẻ,…). -39- Cũng có Website (như Thư viện số - www.thuvienso.info) tính giới hạn số ngày cho người sử dụng download tài liệu. Khi đăng kí tài khoản trên Website này, người sử dụng được cấp một tài khoản. Mỗi lần đăng nhập và muốn download tài liệu của Website này, người sử dụng được kiểm tra tài khoản và số ngày giới hạn còn lại để được download dữ liệu của Website. Nếu muốn nạp tiền cho tài khoản, người sử dụng có thể nhắn tin SMS theo cú pháp “TVS username” và gởi 8717 (mỗi tin nhắn 15000VNĐ và được 5 ngày download dữ liệu không hạn chế), hoặc Thanh toán 200.000 VNĐ (365 ngày sử dụng không giới hạn) bằng cách gửi tiền qua ngân hàng. Một số Website còn sử dụng thanh toán tiền để download tài liệu qua thẻ thanh toán điện tử trên mạng. Trong các mạng ngang hàng, khi một ứng dụng chia sẻ tài nguyên và có bảo mật, đặt password cho thư mục chia sẻ chẳng hạn, thì các máy muốn lấy tài nguyên là thư mục chia sẻ này cần phải chứng minh được quyền hạn của mình với ứng dụng chia sẻ thông qua password của thư mục chia sẻ cấp. Điều này đặc biệt quan trọng trong các ứng dụng ngang hàng của các cơ quan, tổ chức, cá nhân sử dụng thương mại điện tử, vì nó liên quan đến vấn đề tài chính, danh tiếng, lợi ích,… của các đối tượng này. 3.2. Bài toán 3.2.1. Đặt vấn đề Khi một ứng dụng B (có thể là các peer) có nhu cầu truy cập (lấy hoặc chia sẻ tài nguyên hệ thống) tại một nút mạng A nào đó thì sẽ được xem xét để đảm bảo tính tin cậy, hợp pháp đối với nút mạng A. Ngoài ra khi nhiều ứng dụng cùng có nhu cầu lấy tài nguyên tại một nút thì cần phải phân quyền ưu tiên, và nếu ứng dụng nào đã chia sẻ nhiều tài nguyên hơn trong hệ thống cộng tác thì sẽ được quyền ưu tiên cao hơn trong truy cập giành tài nguyên của hệ thống. Để thỏa được điều này, giải pháp đề xuất là nút ứng dụng cấp phát tài nguyên (nút A) sẽ kiểm tra các ứng dụng (các peer-nút B) cần lấy hoặc chia sẻ tài nguyên. Nếu B muốn lấy tài nguyên thì A sẽ kiểm tra B thông qua tổng giá trị các cookie (số điểm như trong cách tính của Website thương mại) có được của mỗi ứng dụng (mỗi peer). Số các cookie này ở mỗi ứng dụng có được khi ứng dụng đó chia sẻ tài nguyên. Trường hợp B muốn chia sẻ tài nguyên thì A và B sẽ thực hiện giao dịch về chia sẻ tài nguyên. Rõ ràng nếu một ứng dụng càng -40- chia sẻ nhiều tài nguyên thì số cookie (và tương ứng tổng giá trị các cookie) mà ứng dụng này có được sẽ càng lớn, và như vậy quyền truy cập, ưu tiên của ứng dụng này sẽ càng cao. Ví dụ về việc một ứng dụng (hoặc người sử dụng) chia sẻ tài nguyên để được tính điểm vào hệ thống có thể được tiến hành như ở một số các Website như sau: nếu muốn tải một tài liệu của Website thì số điểm của người đó phải ở một mức tối thiểu nào đó. Trong trường hợp không đủ điểm để download tài liệu, thì người sử dụng phải thêm số điểm vào tài khoản của mình trên Website bằng cách upload tài liệu của mình lên Website hoặc nạp tiền vào tài khoản của mình trên Website đó. Càng upload nhiều tài liệu (hoặc nạp nhiều tiền vào tài khoản Website) thì sẽ càng có nhiều điểm trong tài khoản của mình trên Website đó. Thường thì khi upload một tài liệu, tài khoản của người upload sẽ được cộng thêm một số điểm, hoặc gửi một tin nhắn theo cú pháp của Website qui định thì được cộng thêm một số điểm (như đã mô tả trong phần 3.2 trên). Ví dụ trên được áp dụng trong mô hình mạng Client/Server. Trong mạng P2P cũng có thể áp dụng vì mỗi máy vừa đóng vai trò Client, vừa đóng vai trò Server. 3.2.2. Bài toán Sau đây là bài toán và giải thuật tương ứng đảm bảo công bằng cho các ứng dụng cộng tác ngang hàng: a) Input: Tập các node (peer) chia sẻ tài nguyên b) Output: - Xác định các node (các peer) cần cộng tác (lấy/chia sẻ) tài nguyên với các node khác. - Kiểm tra độ tin cậy của các peer, tính giá trị tin cậy mỗi peer. c) Giải thuật kiểm tra và tính giá trị tin cậy các peer: i) Kiểm tra trực tiếp tài khoản của peer cần cộng tác (kí hiệu là B) trong cơ sở dữ liệu của máy chia sẻ tài nguyên (kí hiệu là A): i1- Nếu đúng (bao gồm user name và password) thì kiểm tra giá trị tài khoản (là tổng điểm) của B. -41- - Nếu muốn download thì kiểm tra ngưỡng download (so sánh giá trị tài khoản với mức giá trị tối thiểu được phép download). Nếu thỏa ngưỡng download thì xếp hạng thứ tự từ cao xuống thấp về giá trị tài khoản với những peer khác cùng muốn download, thực hiện thủ tục giao dịch dựa trên cookie (phần 3.3.2) và kết thúc. Nếu không thỏa thì thông báo không đủ điều kiện, ra đề nghị (nếu cần) và kết thúc. - Nếu muốn chia sẻ tài nguyên thì thực hiện thủ tục giao dịch dựa trên cookie (phần 3.3.2) và kết thúc. i2- Nếu sai (chưa tồn tại tài khoản trực tiếp) thì sang bước ii. ii) Kiểm tra B qua hàng xóm - Nếu tìm thấy thì thực hiện bước i1. - Nếu không tìm thấy thì thông báo không đủ điều kiện, ra đề nghị (nếu cần) và kết thúc. 3.3.3. Đánh giá thuật toán Chứng minh thuật toán trên hội đủ các tính chất của thuật toán - Đầu vào: Tập các node (peer) chia sẻ tài nguyên - Đầu ra: - Xác định các node (các peer) cần cộng tác (lấy/chia sẻ tài nguyên) với các node khác. Kiểm tra độ tin cậy của các peer, tính giá trị tin cậy mỗi peer. - Tính xác định và khả thi: thuật toán có các bước kiểm tra tài khoản và giá trị tài khoản có sử dụng vòng lặp hữu hạn (vì số nút hữu hạn) và các phép so sánh  các bước đều được xác định chính xác và có thể thi hành. - Tính hữu hạn: thuật toán luôn luôn kết thúc sau khi tất cả các nút được kiểm tra - Tính hiệu quả: thuật toán luôn kết thúc trong 1 khoảng thời gian hữu hạn. - Tính phổ dụng: có thể áp dụng thuật toán này tìm nút bất kỳ trong dãy các nút. 3.3.4. Độ phức tạp của thuật toán -42- Về thời gian: Trong thuật toán này, ta thấy phép toán tích cực là phép tìm kiếm. Tùy thuộc vào cơ sở dữ liệu lưu tại mỗi nút và phương pháp sắp xếp, tìm kiếm mà thời gian thực hiện của chương trình dài hay ngắn. Trường hợp tốt nhất là tìm kiếm trực tiếp tại cơ sở dữ liệu của nút chia sẻ dữ liệu (nút A). Trường hợp xấu nhất là phải tìm trong lân cận hàng xóm, đồng thời phải sử dụng phép toán so sánh khóa và thông qua máy tin cậy AH(C) trong giao dịch tin cậy dựa trên cookie (phần 3.3.2). Nếu cơ sở dữ liệu có n bản ghi (tại nút A và hàng xóm), đồng thời sử dụng giao dịch tin cậy dựa trên cookie ,thì độ phức tạp của thuật toán cỡ n*n*n hay n3. 3.3.5. Các ví dụ mô phỏng thuật toán Ví dụ 1: Giao dịch qua thẻ ATM Một khách hàng (A) sử dụng thẻ ATM của ngân hàng X rút tiền qua case ATM của ngân hàng Y. Tại case giao dịch Y: - A cho thẻ vào ATM - Y kiểm tra tài khoản A (tìm kiếm) qua ngân hàng của Y, sau đó qua hàng xóm X. - Tìm thấy, Y đề nghị A nhập password (thỏa thuận giao dịch). - A nhập mật khẩu. - Y kiểm tra A qua hàng xóm X. Nếu sai thì ra thông báo và đề nghị làm lại (thỏa thuận giao dịch), nếu vẫn sai thì hủy giao dịch, nếu đúng sang bước kế tiếp. - Y yêu cầu A nhập số tiền cần rút - A nhập số tiền - Y kiểm tra số tiền trong tài khoản của A qua người nắm giữ tài khoản của A (là X). Nếu số tiền A nhập để rút vượt quá số tiền trong tài khoản của A có (sau khi trừ phí dịch vụ và số dư tài khoản của A), thì Y ra thông báo đề nghị A nhập lại, trường hợp ngược lại chuyển sang bước tiếp theo. - Y trả tiền cho A (Y cung cấp dịch vụ) và trừ vào tài khoản của A. Y giữ phần trừ này để giao dịch với X. -43- - Quá trình A nhập tiền và Y phục vụ diễn ra cho đến khi A không còn tiền để rút hoặc thỏa thuận với Y ngừng cung cấp dịch vụ thì chấm dứt. Ví dụ 2: Trường hợp gọi điện thoại khác mạng cũng diễn ra tương tự. Trong phần tiếp theo sẽ trình bày giao dịch dựa trên cookie cho các ứng dụng trong giao dịch cộng tác với nhau và kiểm tra tính tin cậy của các cookie của một peer đối với peer chia sẻ tài nguyên. 3.3. Giao dịch dựa trên cookie 3.3.1. Cấu trúc của một cookie [6] 5 trường thông tin đầu tiên: - Issuing date and time (tính theo mili giây) cùng với Serial Number và Owner ID: cung cấp định danh duy nhất của cookie. Đây là yêu cầu nhằm phát hiện cookie trùng lặp. - Account ID: dùng để xác định một cookie minh bạch cho một ứng dụng xác định. Đây là trường lựa chọn. - Signature SK: là chữ kí thông tin được chứa trong 4 trường trên, được kí với khóa riêng của hệ thống, nhằm ngăn sự giả mạo. 3 trường tiếp theo (Transaction Data): Ngày giao dịch, đối tượng tham gia giao dịch và thông tin chất lượng dịch vụ giao dịch. 2 trường cuối: Định danh nhà cung cấp dịch vụ và chữ kí chủ sở hữu nhằm tránh cookie bị đánh cắp. 3.3.2. Giao dịch [6] Trong các giao dịch, hệ thống kiểm soát dựa vào cookie sẽ kiểm soát việc sử dụng tài nguyên, dịch vụ hoặc kết hợp cả hai. Sử dụng dịch vụ được đánh giá cao hơn sử dụng tài nguyên. Một cookie có thể chứa thông tin về các tài nguyên được sử dụng và thông tin giá trị của dịch vụ chính nó. -44- Thông tin được thêm vào cookie trước khi nó được gửi tới nhà cung cấp dịch vụ. Bằng cách này, thông tin chứa trong cookie có thể được sử dụng làm cơ sở cho các cơ cấu thanh toán mở rộng. a) Giao dịch chuẩn (1) Người tiêu thụ dịch vụ C yêu cầu dịch vụ (2) Người cung cấp dịch vụ P thông báo cho C về các điều khoản và điều kiện của dịch vụ, bao gồm số cookie của dịch vụ mà nó chờ nhận lại. Nếu C chấp thuận các điều trên thì phase quá trình cung cấp dịch vụ bắt đầu được tiến hành. + Cookie có thể được vận chuyển trước, sau hoặc trong quá trình cung cấp dịch vụ. + Trước khi 1 cookie được vận chuyển, C điền thông tin kiểm soát yêu cầu. C không khuyến khích làm giả thông tin này vì nó chỉ ảnh hưởng tới cookie trao đổi của P (3) C kí vào cookie với khóa riêng thuộc sở hữu của nó và gửi tới P. (4) P sử dụng khóa chung của C kiểm tra chữ kí của cookie nhận được. Chữ kí có thể là định danh chủ sở hữu hoặc yêu cầu dịch vụ. Vì vậy P có thể sửa đổi được thông tin này. + P có thể ngừng cung cấp dịch vụ nếu phát hiện dữ liệu kiểm soát sai. + Các thành phần cùng tham gia giao dịch có thể cố gắng thu các cookie bằng cách không thanh toán các cookie sau khi nhận một dịch vụ hoặc bằng cách không phân phát dịch vụ sau khi nhận các cookie. => Để tránh các giao dịch đó có thể dùng cách phân chia thành phần -45- (5) C gửi một cookie được kí tới P sau khi P đã phân phát một thành phần của dịch vụ. Ví dụ: C gửi mỗi cookie sau mỗi Mbytes dữ liệu nhận được từ 5 Mbytes vận chuyển file. b) Giao dịch tin cậy Trong khi thực hiện các giao dịch thì giao dịch sau cùng thường có động cơ gian lận đối với các giao dịch khác. Thường thì giao dịch sau cùng vẫn nhận được đầy đủ các lợi ích, nhưng không chịu phân phát các thành phần của nó. Thủ tục sau đây sẽ hạn chế động cơ gian lận đó: (1) C gửi yêu cầu dịch vụ cho P (2) P nhận yêu cầu và gửi lại C các điều kiện và điều khoản của giao dịch, bao gồm số lượng các cookie được yêu cầu. (3) C trả lời với các định danh của cookie được dùng và gửi các cookie tới giao dịch. (4) P liên hệ với máy tin cậy AH(C), là máy chịu trách nhiệm nắm giữ tài khoản của C, để kiểm tra tính hiệu lực của các cookie mà C gửi (5) Máy AH(C) đóng dấu vào danh sách cookie với nhãn “planned to spend”. Những cookie này không có hiệu lực trong các giao dịch khác (6) Nếu tất cả các cookie có hiệu lực, P thông báo C rằng phase giao dịch có thể bắt đầu. -46- (7) C bắt đầu giao dịch bằng việc gửi các cookie chưa đánh dấu tới P. Lúc này C không còn cookie và không kí được nữa, nhưng P cũng không thể thay đổi cookie để sở hữu cho mình vì P không muốn cung cấp thêm dịch vụ. (8) P cung cấp các dịch vụ chấp nhận được. (9) Nếu C quên không gửi các cookie đã kí thì P có thể đề nghị các cookie chưa kí tới AH(C). Thủ tục chứng tỏ khi giao dịch bắt đầu thì các cookie cũng rời khỏi danh sách và C bị mất cookie. Phần thêm trong tiêu thụ kép có thể không bị phát hiện, nhưng bị vô hiệu hóa. Hệ thống danh tiếng đã nói ở trên có thể cung cấp nhiều hơn nữa khả năng chống lại các hành vi hiểm độc. c) Chấm dứt giao dịch Khi hai máy thỏa thuận muốn chấm dứt giao dịch, C không mất các cookie của mình, P thông báo tới AH(C) để xóa nhãn đánh dấu “planned to spend” được đánh dấu trong danh sách cookie. 3.4. Kiểm tra tính tin cậy của các cookie Để có thể đảm bảo được tính tin cậy của cookie trong mỗi giao dịch thì cần đảm bảo các điều kiện sau đây: a) Những người sử dụng hệ thống dựa vào cookie đều có định danh rõ ràng và không đổi. Điều này có thể thực hiện được bằng cách: + Qua sự xác minh cặp khóa riêng/khóa công cộng. Hiện nay có thể sử dụng phần mềm trong việc tạo ra cặp khóa theo chuẩn RSA, một trong những phần mềm nổi tiếng đó là PGP. Ở Việt Nam cho đến thời điểm này Bộ Công thương là chủ quản qui định về vấn đề đăng kí, sử dụng, giải quyết các vấn đề về sử dụng chữ kí số theo chuẩn RSA. + Qua chứng thực được phát ra từ một ủy quyền b) Có một máy danh tiếng trong hệ thống P2P: + Phát hiện được các hành vi gian lận mà các máy kĩ thuật không thể phát hiện được. + Gán một giá trị danh tiếng cho mỗi máy để đại diện tính tin cậy của máy đó như sau: Mỗi máy phát ra các nhãn cá nhân dùng để giao dịch với các -47- máy khác. Nếu máy A yêu cầu một dịch vụ từ máy B, máy A sẽ trả lại cho máy B một số các nhãn của máy B. Trong kiểu giao dịch này không có sự giới hạn việc một máy được phép phát ra bao nhiêu nhãn. Tuy nhiên nếu phát ra quá nhiều nhãn thì trong sự so sánh các dịch vụ được trả giá của nó, các nhãn sẽ không có giá trị, đồng thời các máy sẽ khó khăn trong việc kiếm được các nhãn khác, theo lí các nút sẽ không mong muốn tậu các nhãn của nó (càng nhiều nhãn thì càng phải cung cấp nhiều dịch vụ). + Theo cách này, giao thức các nhãn kết hợp 1 đồng tiền ảo và 1 máy danh tiếng. Có 3 giao thức cơ bản của hệ thống kiểm soát dựa trên cookie: Thu nạp cookie, kiểm tra tiêu thụ kép và thanh toán. 3.4.1. Thu nạp cookie Xử lí thu nạp cookie là thay đổi các cookie ngoài mà một máy tập hợp được thành những cookie mới được phát hành bởi máy đó. Việc này tựa như các ngân hàng ủy quyền thanh toán cho khách hàng của mình thông qua các giao dịch không cùng ngân hàng, khi một khách hàng chuyển/rút tiền tài khoản của mình (tài khoản thuộc ngân hàng A) qua tài khoản khác (thuộc ngân hàng B), chẳng hạn tại các cây ATM. Có 8 bước của thủ tục thu nạp cookie: -48- (1): Máy thay đổi EP xác định một máy tin cậy TP. Các máy tin cậy có đủ tư cách để thay đổi các cookie và xử lí thành phần của khóa riêng của hệ thống. (2): Máy EP gửi tập N các cookie ngoài (Fn1, Fn2, …, FnN) được nó tập hợp tới máy TP. Máy TP kiểm tra các cookie ngoài theo sự hợp lệ của nó. Chỉ những cookie được kí bởi người chủ và tiêu thụ chỉ một lần là có hiệu lực thay đổi. (3): Máy TP sử dụng hàm thu nạp M=A (Fn1, Fn2, …, FnN) tính toán M cookie mới máy EP phải nhận lại đối với các cookie ngoài. Đó là M cookie chưa được kí (Un1, Un2, …, UnM). Hàm thu nạp M là tổng quát và có thể thi hành đối với form bất kì. (4): Máy TP xác định các máy tin cậy ở xa. Lúc này máy EP không được phép chọn các máy đại diện tin cậy nữa, nhằm giảm sự gian lận cộng tác tiềm tàng. Số các máy tin cậy được yêu cầu để kí một cookie được xác định bằng việc sử dụng sơ đồ chia sẻ bí mật. Độ tin cậy của hệ thống tăng tỉ lệ với kích cỡ số các máy tin cậy. (5): Máy TP gửi các cookie mới tới các máy tin cậy này. (6): Mỗi máy tin cậy mới này kí các cookie bằng khóa riêng của hệ thống của nó. (7): Các cookie (Pn1, Pn2, …, PnM) được vận chuyển ngược trở lại máy EP. (8): Kết thúc, máy EP tổ chức các cookie riêng thành các cookie mới (Tn1, Tn2, …, TnM) Tính chất quan trọng của hàm thu nạp làm tăng thêm độ tự do trong hệ thống. Với một hàm thu nạp thích hợp, các hệ thống kinh tế đặc trưng có thể được vận hành. 3.4.2. Kiểm tra tiêu thụ kép - Điều kiện kiểm tra: Cookie phải có định danh rõ ràng - Kiểm tra như sau: -49- + Mỗi máy có một tập các máy nắm giữ tài khoản được tổ chức theo bảng băm phân tán (DHT), ví dụ như bảng băm Pastry. + Các máy nắm giữ tài khoản nắm giữ một danh sách các cookie hiện tại được phát hành tới người sở hữu tài khoản. Danh sách được điền thêm thông tin yêu cầu trong khi thu nạp cookie. + Sau khi một cookie mới được tạo (bước 3-thu nạp cookie), máy TP gửi danh sách các cookie mới này tới các máy nắm giữ tài khoản (EP) (bước 3-kiểm tra cookie). + Trong khi cookie được kiểm tra tính hiệu lực (theo thủ tục thu nạp cookie), máy TP sẽ yêu cầu các máy nắm giữ tài khoản chịu trách nhiệm đối với cookie, nếu cookie có hiệu lực (bước 2-kiểm tra cookie). + Các máy nắm giữ tài khoản sẽ di rời cookie từ danh sách. Nếu cookie không ở trong danh sách, nó là một cookie không có hiệu lực. Máy TP sẽ hủy bỏ cookie và cơ cấu danh tiếng sẽ được thông báo về tình trạng này. - Tránh thông báo lừa lọc + Thông báo gửi đến máy nắm giữ tài khoản phải được kí với khóa riêng của người gửi. - Giữ danh sách nhất quán giữa các máy nắm giữ tài khoản -50- + Tất cả những máy nắm giữ tài khoản đối với một tài khoản xác định thực hiện trao đổi danh sách bất cứ khi nào tập các máy nắm giữ tài khoản thay đổi. + Thay đổi tập nắm giữ này chỉ khi các máy của tập này kết nối hoặc rời khỏi hệ thống. Kiểm tra nhất quán chỉ cần thiết nếu người gửi không nhận được tất cả các thông báo xác nhận. 3.4.3. Đánh giá về an toàn và tin cậy  Mục đích - Làm cho việc sử dụng cơ cấu kiểm soát để cung cấp thông tin được chính xác. - Hệ thống dựa trên cookie được thiết kế để cung cấp độ tin cậy ở mức cao đối với các hệ thống phân tán.  Sự ăn cướp - Các cookie được thiết kế để thích nghi với sự ăn cướp. + Các cookie chứa định danh của chủ sở hữu và không thể thay đổi được khi bị phát hiện bên ngoài nhờ chữ kí hệ thống. + Các cookie tiêu thụ chứa người nhận cookie, được bảo mật nhờ chữ kí của người sở hữu.  Sự giả mạo - Cookie phải chắc chắn chỉ được người chủ hoặc ủy quyền phát hành tạo ra và phải được kí bởi khóa riêng của nó. - Chữ kí hệ thống trong mỗi một cookie là cơ sở đảm bảo dữ liệu của cookie không bị thay đổi và các máy khác không thể tạo được các cookie như vậy. + Chữ kí hệ thống ngăn cản giả mạo và quyết định độ tin cậy của hệ thống. + Cũng cần tránh sự cố ý lừa gạt.  Tiêu thụ kép - Việc xác định tiêu thụ kép dựa vào việc nắm giữ dữ liệu ở những máy nắm giữ tài khoản. -51- - Người sử dụng có thể làm sai lệch danh sách cookie của họ ở máy nắm giữ tài khoản hoặc di chuyển các cookie từ danh sách cookie của những máy khác. Điều này tránh được vì: - Ngăn không cho phép các máy gửi bất kì truy vấn hoặc đòi hỏi nào tới danh sách tài khoản. - Các vi phạm luật được báo cáo tới máy danh tiếng của hệ thống. - Bằng thủ tục thu nạp cookie. - Trường date and time được tạo theo mili giây và là số tuần tự ngẫu nhiên, rất khó đoán được chính xác. - Các hệ thống dựa trên cookie lưu trữ các cookie cục bộ (tự backup, luôn nghĩ tiêu thụ kép bị phát hiện). - Cookie phải được nhận biết rõ ràng: có định danh duy nhất, có thông tin kiểm soát như trong cookie có quy định về tên, loại ứng dụng, dung lượng ứng dụng chia sẻ,… - Có cơ cấu xây dựng trong hệ thống kiểm soát để kiểm tra. 3.5. Áp dụng mô hình tin cậy NICE đảm bảo công bằng trong ứng dụng chia sẻ file BitTorrent 3.5.1. Giới thiệu về BitTorrent 3.5.1.1. Tổng quan về BitTorrent BitTorrent là một mạng chia sẻ file được sáng lập bởi Bram Cohen. BitTorrent là một ứng dụng P2P với mục đích phân phối các file có dung lượng lớn nhanh và hiệu quả qua việc upload băng thông của các máy (peer) khi các máy này download dữ liệu. Nền tảng của vấn đề là phân chia các file thành các block có kích thước như nhau (mỗi block chiếm khoảng 32 đến 256 kbs) để các máy download đồng thời các block từ nhiều máy. Các block ở xa được chia nhỏ hơn để có thể sử dụng đường ống (pipelining) theo các yêu cầu. Giả sử bạn có 1 file dung lượng 1GB và 300 người cần, sẽ cần rất nhiều thời gian để chia sẻ 300GB dữ liệu. Nhưng nếu bạn chia file thành các mảnh nhỏ gửi cho mọi người và họ lại chia sẻ các mảnh đó cho người khác cho đến khi ai ai cũng có file hoàn chỉnh thì sẽ nhanh hơn rất nhiều. Các trang web lớn có thể sử dụng BitTorrent để cập nhật cho các phần mềm của họ, bằng cách này họ sẽ giảm được chi phí trả cho băng thông. Tốc độ của BitTorrent rất đáng kinh ngạc, chỉ mất vài giờ để truyền tải các file cực kỳ lớn. Một vài trang web đã ra đời dựa theo công nghệ này phân phát các nội dung có bản quyền. Ngay lập tức, các tổ -52- chức như MPAA đã đổ lỗi cho công nghệ này, điều đó hoàn toàn sai, thực tế lỗi là ở các cá nhân sử dụng công nghệ cho mục đích trái phép. Dù thế nào đi nữa, BitTorrent không phải sinh ra để phát tán tài nguyên bất hợp pháp, nó là một phát minh của Bram để giúp cho việc truyền tải trở nên nhanh hơn trong thế giới mạng. Nó được sử dụng trên các trang web trên khắp thể giới và Bram tự hào về điều này. 3.5.1.2. Các khái niệm và hoạt động của BitTorrent: Torrent: Mỗi một file lớn có hiệu lực download được gọi là một torrent. Thường thì torrent là một file mang phần mở rộng .torrent nhận từ server. File .torrent này chứa thông tin về dữ liệu muốn down (chứ không phải là bản thân dữ liệu đó). User có thể save file .torrent đó trên máy của mình, sau đó mở nó bằng trình BitTorrent để tiến hành việc download. Hoặc, bạn có thể down ngay bằng cách click thẳng vào link trên trang web - cách này mất thêm chút công sức nếu muốn down lại file đó sau này. BitTorrent không giống các mạng P2P khác như là eD2K hoặc FastTrack, bạn không thể search được file A bằng cách sử dụng các chương trình BitTorrent. Thay vào đó bạn phải vào các trang web có danh sách các file Torrent. Các file Torrent này chứa các thông tin về file A mà bạn muốn download và chứa thông tin về các “tracker” mà bạn phải kết nối để bắt đầu download. Các “tracker” là các máy chủ trung tâm, nó lưu giữ thông tin về từng người đang chia sẻ các file A, và các phần mà họ có. Khi bạn download file Torrent, và open nó, chương trình BitTorrent (như là. Bit Torrent, Bit Tornado, Azureus, ...vvv.) sẽ chạy và kết nối đến các tracker. Tracker sẽ kết nối bạn đến Seeds và Peers – những người đang chia sẻ file A này và quá trình download của bạn sẽ bắt đầu. Đến khi bạn có ít nhất một “mảnh” của file A, bạn đã có thể upload “mảnh” đó cho những người chưa có. Như vậy bạn đã có thể thấy rằng BitTorrent khác với các mạng P2P khác : cần có file Torrent cho các file (hoặc thư mục) mà bạn muốn download hoặc chia sẻ. Tracker: Có một thành phần trung tâm cho biết nơi mà một peer có thể lấy dữ liệu từ các node trong hệ thống, thành phần trung tâm này gọi là tracker. Tracker nhận updates từ các node định kì 30 phút giống như các nút khi kết nối hoặc rời torrent. Các trang web liệt kê các file torrent (như là torrentbox.com) có những tracker của họ để quản lý việc download và chia sẻ giữa mọi người. File torrent phải có thông tin chi tiết về tracker. Do đó bạn muốn kết nối đến tracker nào thì chỉ có thể sử dụng file torrent được tạo cho tracker đó. Có các phần mềm để giúp bạn thiết lập các tracker riêng và tạo file torrent. -53- Một server nằm trên mạng internet, phối hợp hoạt động của các trình BitTorrent. Khi bạn mở một file torrent, máy tính của bạn sẽ liên lạc với tracker để lấy danh sách các peer cần kết nối. Trong quá trình down file torrent, thỉnh thoảng máy tính của bạn sẽ lại liên lạc với tracker, thông báo cho tracker biết bạn đã down và up bao nhiêu, còn bao nhiêu nữa là down xong,... Nếu bạn chuẩn bị down một file mà tracker của nó hiện đang mất kết nối, bạn sẽ không thể tạo kết nối. Nếu đang down mà tracker mất kết nối, bạn vẫn có thể tiếp tục quá trình truyền tải file với các peer hiện có, nhưng sẽ không kết nối thêm được với peer mới nào khác. Thường các lỗi với tracker ít khi xảy ra trong một thời gian dài, do đó bạn chỉ việc chờ đợi và để mở trình BitTorrent. Seed: Một node trong hệ thống mà sau khi hoàn thành việc sao chép đầy đủ các file và có thể phục vụ cho các node khác thì được gọi là một seed. Seeds là những người đã có 100% file hoặc thư mục (file hoặc thư mục hoàn chỉnh) và vẫn đang tiếp tục upload cho những người khác. Một máy tính có bản copy hoàn hảo của file torrent bạn muốn down. Khi quá trình down của bạn kết thúc, bạn sẽ hoạt động như một seed cho đến khi bạn bấm Finish hoặc đóng hoàn toàn trình BitTorrent lại. Thường thì bạn nên seed một file đã down xong cho người khác. Đồng thời, khi một file torrent mới được đưa lên tracker, một ai đó phải seed nó cho người khác down. Hãy nhớ rằng, tracker không biết tí gì về nội dung thực sự của file, vì thế luôn cần phải có ít nhất một máy đóng vai trò seed. Reseed: Với một file torrent mà số seed của nó là con số 0 tròn trĩnh (hoặc không có đủ số peer để tạo thành một bản copy hoàn hảo), thì dù muốn hay không tất cả những gì các peer nhận được cũng sẽ là một file không hoàn chỉnh, vì không ai trong swarm đó có các phần còn thiếu. Khi điều đó xảy ra, một ai đó với file hoàn chỉnh (seed) sẽ phải đứng ra kết nối với swarm để tiến hành việc truyền tải các phần còn thiếu. Nó gọi là reseed. Thường thì khi một yêu cầu reseed được đưa ra và được chấp thuận, người được yêu cầu phải đảm bảo mình sẽ để trình BitTorrent của mình mở trong một thời gian nhất định, tạo điều kiện cho file torrent đó có thể được nhiều người down hơn. Swarm: Một nhóm các máy tính kết nối với nhau thông qua một file torrent. Ví dụ, nếu trình BitTorrent của bạn báo bạn đang nối với 10 peers và 3 seeds, thì điều đó nghĩa là trong swarm đó có 13 người (không kể bạn). Peer: -54- Peer là những người chưa có đủ 100% file (file chưa hoàn chỉnh) đang download các phần mà họ chưa có đồng thời upload các phần họ đã có cho người khác. Peer là một máy tính khác trên mạng internet. Bạn tạo kết nối với peer và truyền tải dữ liệu với nó. Thường thì một peer không có cả 100 % file mà bạn muốn down (nếu có nó sẽ được gọi là seed). Một vài người khi nói đến peer lại nghĩ tới leecher, những kẻ sau khi down xong không chịu để trình BitTorrent chạy tiếp và hoạt động như một seed. Leecher: Một node mà trong khi đang download các file nhưng vẫn phục vụ các block mà node này hiện có cho các node khác thì được gọi là leecher. Thường thì Leechers là những người download file nhưng không upload hoặc giảm mức upload xuống mức thấp nhất. Share rating: Nếu bạn dùng một trình BitTorrent với giao diện GUI, bạn sẽ thấy thông số share rating hiện trên giao diện. Nó đơn giản chỉ là tỉ lệ bạn up trên tỉ lệ down. Nếu thông số share ratio là 1.0, điều đó có nghĩa là lượng bạn down bằng với lượng bạn up. Số này càng cao thì nghĩa là bạn đóng góp càng nhiều. Nếu bạn thấy share ratio là vô cùng, thì nghĩa là bạn đang seed một file - bạn up nhưng không down. Vì lợi ích của người khác, hãy giữ cho share ratio của bạn lớn nhất có thể. Các trang có file torrent Có rất nhiều trang web liệt kê các file torrent. Bạn chọn rồi down load file torrent về. Sau đó open bằng chương trình BitTorrent của bạn. Ngay lập tức, bạn sẽ được kết nối với tracker và bắt đầu download. Một số trang web đó là: mininova.org Torrentbits.org TorrentReactor.com FileList.org – Phải đăng ký ... Tầm quan trọng của việc Upload. Việc upload trên BitTorrent là đương nhiên và cần thiết. Đặt trường hợp bạn đang download file có 3 seeds và 800 peers, và việc chia sẽ đã hoàn tất ở một số peers. Giả sử bạn là 1 peer đã download xong nhưng chỉ upload 10% của file rồi ngừng. Việc làm này sẽ dẫn đến hậu quả rất xấu bởi vì bạn làm vậy thì nhiều người khác cũng có thể làm như vậy, sau đó sẽ có rất ít seeds và có thể sẽ không còn seeds và những người chưa hoàn tất sẽ không có file hoàn chỉnh. Nếu -55- tất cả mọi người đều có thói quen ngừng upload ngay khi download xong thì file đó sẽ không tồn tại lâu. Hãy đảm bảo rằng dung lượng upload của bạn bằng với dung lượng download hoặc hơn. Nếu ai đó download 700MB và upload 700MB thì vẫn chưa tốt. Để file đó có thể tồn tại lâu và những người khác còn được download về với tốc độ cao, mọi người hãy cố upload bằng 150% dung lượng mình download. Khi bạn đã download xong, hãy tiếp tục upload đến khi bạn đạt tỉ lệ này. Các tracker luôn cấm các leechers do đó luôn theo dõi việc download/upload của bạn. Nếu bạn thích BitTorrent, đừng thử hoặc cố đánh lừa nó. Cơ chế hoạt động của BitTorrent Khi một node mới kết nối với một torrent, nó sẽ liên hệ với tracker để nắm được danh sách tập ngẫu nhiên các seed hoặc leecher có trong hệ thống hiện tại. Node mới sau đó sẽ thử thiết lập tới khoảng 40 node tồn tại hiện có trong hệ thống để trở thành hàng xóm với các node này. Nếu số các node hàng xóm của một nút thấp hoặc giảm xuống dưới 20 (do các node đó rời hệ thống - chẳng hạn) thì node mới này sẽ liên hệ lại với tracker để được bổ sung thêm các node mà node này có thể kết nối tới được. Mỗi một node sẽ tìm kiếm thời điểm thích hợp (thời cơ) để download các khối từ các node khác (hàng xóm) và upload các khối tới các node hàng xóm này. Thường thì một nút có thể chọn một vài khối mà nó có thể download. Nó sử dụng chính sách local rarest first (ưu tiên cục bộ-LRF) trong việc chọn các block để download, nghĩa là node thử download các khối được sao chép ít nhất xung quanh các hàng xóm của node đó. Chính sách tit-for-tat (có đi có lại – TFT) được sử dụng để cảnh giác chống lại cái gọi là free-riding, nghĩa là: một node sẽ thích hơn việc upload cho các node hàng xóm đã cung cấp cho node này tỉ lệ download tốt nhất. Mỗi một node giới hạn số các upload đồng thời thành một số nhỏ, số này vào khoảng 5. Các seed không có gì để download, nhưng chúng cho một chính sách như nhau, đó là chúng upload tới 5 nodes mà có tỉ lệ download cao nhất. Cơ cấu được sử dụng để giới hạn số các upload đồng thời gọi là choking (ngăn chặn, điều tiết), đó là khoảng thời gian từ chối của một node để upload tới hàng xóm. Chỉ những kết nối để chọn hàng xóm (vào khoảng 5) là unchoked ở bất kỳ thời điểm nào. Một node tính toán tỉ lệ download nhận được từ hàng xóm của nó từ 10 giây để quyết định hàng xóm này (chưa bị chokes) sẽ bị choke để thay thế bởi một hàng xóm khác. BitTorrent cũng kết hợp một chính sách gọi là optimistic unchoke (unchoke lạc quan) trong một node, trong việc unchoke bình thường đã mô tả ở trên, trong unchoke chọn ngẫu nhiên hàng xóm bất chấp tỉ lệ download đạt được từ hàng xóm đó. Optimistic unchoke thực hiện 30 giây mỗi lần. Cơ cấu này cho -56- phép các node khám phá các node hàng xóm thường có tỉ lệ download cao, giống như cho phép các node mới nhận được block đầu tiên của chúng. Có thể nói BitTorrent là một giao thức được tạo ra phục vụ cho quá trình truyền tải file. Dưới hình thức kết nối peer-to-peer, người sử dụng kết nối trực tiếp với nhau để gửi và nhận các phần của một file. Một server trung tâm, dưới tên gọi tracker, được lập ra để xác định vị trí những người dùng ấy. Tracker mang nhiệm vụ duy nhất là quản lý các kết nối, nó không cần biết gì về nội dung file đang được truyền tải, bởi thế ngay cả khi tracker có băng thông cực nhỏ, một số lượng người dùng cực lớn vẫn có thể tham gia vào việc truyền tải file. Điểm cơ bản trong BitTorrent chính là việc người dùng thực hiện việc up và down cùng một lúc trong khi băng thông được tổ chức sao cho tối ưu nhất. BitTorrent được thiết kế để khi số người dùng càng tăng cao thì càng làm việc hiệu quả