Khóa luận Chống tấn công che khuất trong các mạng ngang hàng - mai hữu tiến

ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ Mai Hữu Tiến CHỐNG TẤN CÔNG CHE KHUẤT TRONG CÁC MẠNG NGANG HÀNG KHOÁ LUẬN TỐT NGHIỆP ĐẠI HỌC HỆ CHÍNH QUY Ngành: Công nghệ thông tin Cán bộ hướng dẫn: TS. Nguyễn Đại Thọ HÀ NỘI - 2009 Lời cảm ơn Trước tiên, tôi xin chân thành cảm ơn các thày cô giáo trong khoa Công nghệ Thông tin trường Đại học Công Nghệ - Đại học Quốc gia Hà Nội đã dạy dỗ và chỉ bảo nhiệt tình cho tôi trong suốt bốn năm học qua. Tôi xin gửi lời cảm ơn sâu sắc nhất tới TS. Nguyễn Đại Thọ - phó chủ nhiệm bộ môn Mạng và Truyền thông máy tính, là người hướng dẫn trực tiếp cho tôi trong quá trình thực hiện khóa luận. Thày đã cho tôi nhiều ý tưởng và kinh nghiệm quý báu để hoàn thành khóa luận này. Tôi xin chân thành cảm gia đình, bạn bè và người thân đã luôn động viên và giúp đỡ tôi trong thời gian qua. Đây là chỗ dựa tinh thần vững chắc và là nguồn động viên to lớn giúp tôi vượt qua khó khăn trong thời gian thực hiện khóa luận cũng như trong cuộc sống. Tôi xin chân thành cảm ơn! Hà Nội, ngày 24/05/2009 Sinh viên Mai Hữu Tiến Tóm tắt Trong mạng ngang hàng, một node muốn giao tiếp với các node khác trong mạng đều phải thông qua các node mà nó có liên kết trực tiếp tới, các node này được gọi là các hàng xóm của nó. Trong quá trình các thông điệp được gửi, các node hàng xóm đóng vai trò như các bộ định tuyến, nó giúp chuyển tiếp các thông điệp tới đích một cách chính xác. Đặc trưng này của mạng ngang hàng là điểm yếu mà kẻ tấn công muốn lợi dụng. Một kẻ tấn công nếu điều khiển được các node hàng xóm của node chuẩn thì nó có thể “che khuất” node chuẩn với các node khác trong mạng, hình thức tấn công như vậy được gọi là tấn công che khuất. Có một phương pháp phòng chống tấn công che khuất hiệu quả được Atul Singh – một giảng viên của trường đại học Rice (Mỹ) cùng các đồng nghiệp đưa ra được trình bày trong bài báo [1] đó là phương pháp kiểm tra ẩn danh dựa vào việc giới hạn bậc của các node trong mạng. Để có thể đánh giá hiệu quả của phương pháp này, tôi đã xây dựng một chương trình mô phỏng phương pháp kiểm tra ẩn danh, kết quả thử nghiệm cho thấy có tới hơn 90% các node gây hại bị phát hiện. Mục lục Các chữ viết tắt Từ viết tắt Từ gốc Nghĩa tiếng Việt CRT Constraints routing table Ràng buộc bảng định tuyến DHT Distributed hash table Bảng băm phân tán GT-ITM Georgia Tech Internetwork Topology Models Mô hình topo liên mạng của trường Georgia PNS Proximity neighbor selection Lựa chọn hàng xóm lân cận P2P Peer to peer Mạng ngang hàng Hình ảnh Hình 1: Không gian định danh Pastry 4 bit với sáu khóa được ánh xạ vào năm node 10 Hình 2: Bảng định tuyến, tập lá, tập lân cận của node có định danh 10233102 12 Hình 3: Các node gây hại chia mạng xếp chồng ra làm hai mạng con. 20 Hình 4: Tập Con trỏ ngược - Back pointer set 27 Hình 5: A kiểm tra B thông qua node trung gian I 28 Hình 6: Minh họa mạng giao vận nhánh – Transit stub 33 Hình 7:Các loại thông điệp trong kiểm tra ẩn danh 37 Đồ thị Biểu đồ 1: Tỉ lệ node gây hại bị phát hiện trong thí nghiệm 1 41 Biểu đồ 2: Tỉ lệ node chuẩn không vượt qua được kiểm tra trong thí nghiệm 1 42 Biểu đồ 3:Tỉ lệ node gây hại bị phát hiện trong thí nghiệm 2 43 Biểu đồ 4: Tỉ lệ node chuẩn bị kết luận nhầm là node gây hại trong thí nghiệm 2 43 Mở đầu Số người dùng Internet tính đến năm 2008 là hơn 1,46 tỉ người (số liệu từ trang Internetworldstats.com) so với 35.000 người năm 1987 và tăng tới 46% trong hai năm từ 2006 đến 2008 (theo tờ Washington Post), điều này chứng tỏ Internet đang có tốc độ tăng trưởng rất cao trên toàn thế giới. Với sự phát triển nhanh của số người dùng Internet như vậy, mô hình phục vụ client-server đang dần bộc lộ điểm yếu của mình đó là việc quá tải băng thông dẫn đến server không thể đáp ứng hết tất cả yêu cầu từ phía client khi lượng client kết nối tới server quá cao. Một trong những công nghệ được hi vọng có thể giải quyết việc quá tải băng thông trong mô hình client-server đó chính là công nghệ mạng ngang hàng. Ngày nay, mạng ngang hàng đang dần trở nên phổ biến và thu hút được rất nhiều sự quan tâm của người dùng, các nhà phát triển ứng dụng và các nhà nghiên cứu. Giống như mô hình client-server, mạng ngang hàng cũng phải đối mặt với nguy cơ bị tấn công từ phía những kẻ xấu muốn phá hoại mạng và khống chế máy tính của người sử dụng. Một trong những mục đích chính của người sử dụng Internet đó là chia sẻ dữ liệu mà mình có như các bộ phim, hình ảnh, bài hát… với người thân và những người khác trên toàn thế giới, công nghệ mạng ngang hàng có thể đáp ứng tốt nhu cầu này và nó đang được sử dụng phổ biến. Có những lúc cao điểm, mạng chia sẻ file ngang hàng đã chiếm tới 90% băng thông của mạng Internet (theo tờ Washington Post). Ngoài ứng dụng chia sẻ file, còn có một ứng dụng nổi bật dựa trên mạng ngang hàng không thể không nói tới đó là ứng dụng gửi tin nhắn tức thời với các nhà cung cấp dịch vụ nổi tiếng như ICQ, Yahoo, AOL,... Mạng ngang hàng đã quá phổ biến và đang là mục tiêu phá hoại của những kẻ xấu. Sẽ là thảm họa lớn cho người dùng khi bị kẻ xấu tấn công, nhất là trong mạng ngang hàng, bởi các máy tham gia vào mạng đều bình đẳng với nhau, thường không có một sự quản lý tập trung nào trong mạng. Do đó, kẻ tấn công có thể dễ dàng gia nhập vào mạng thực hiện các hành vi phá hoại như ngăn cản giao tiếp giữa các máy, khống chế việc gửi và nhận dữ liệu, cấy các chương trình phá hoại vào máy người dùng, phát tán các mã độc… Các dạng tấn công thường gặp trong mạng ngang hàng đó là: tấn công mạo nhận, tấn công che khuất, tấn công bằng các file độc … Trong các cách tấn công này, thì tấn công che khuất là phổ biến và khó phòng chống nhất. Muốn thực hiện tấn công che khuất, kẻ tấn công phải đưa các node gây hại vào trong tập hàng xóm của các node chuẩn, nếu tỉ lệ node gây hại trong tập hàng xóm của các node chuẩn càng cao thì hiệu quả của tấn công che khuất sẽ càng cao. Để có thể đưa các node phá hoại vào các tập hàng xóm, node phá hoại thường lợi dụng quá trình node mới tham gia vào mạng và quá trình cập nhật tập hàng xóm theo chu kì. Trong các quá trình này, tập hàng xóm của các node chuẩn sẽ được bổ xung node mới và thay thế các node lỗi, đây thời cơ thích hợp để node gây hại được đưa vào trong tập hàng xóm của các node chuẩn. Khi đã chiếm được nhiều vị trí trong tập hàng xóm của các node chuẩn, node gây hại có thể “che khuất” các node chuẩn với các node khác trong mạng, bởi khi gửi thông điệp cho các node khác đều phải qua các node gây hại trong tập hàng xóm, do đó mọi giao tiếp của node chuẩn với các node khác đều bị node gây hại khống chế và kiểm soát. Với cách thức tấn công như vậy, các node gây hại có thể khống chế toàn bộ băng thông và dữ liệu truyền trong mạng khi đã “che khuất” được nhiều node chuẩn. Trước các tác hại do tấn công che khuất có thể gây ra, vấn đề cấp thiết đó là cần có một cơ chế hiệu quả ngăn chặn các hành vi “che khuất” của các node gây hại trong mạng ngang hàng để đảm bảo cho mạng hoạt động bình thường và ổn định. Phương pháp chống tấn công che khuất có thể được áp dụng trong kháng lỗi của mạng và để xây dựng mô hình kháng lỗi Byzantine[7] trong mạng nói chung và mạng ngang hàng nói riêng. Sự nguy hiểm của tấn công che khuất cùng với sự phổ biến của mạng ngang hàng cho ta thấy ý nghĩa to lớn và tầm quan trọng của chống tấn công che khuất trong thực tiễn. Do các yêu cầu thực tế đó, khóa luận này sẽ nghiên cứu phương pháp phòng chống tấn công che khuất, cụ thể là phương pháp được nêu ra trong bài báo [1] của tác giả Atul Singh cùng các đồng nghiệp tại trường đại học Rice của Mỹ. Trong bài báo này đã đưa ra một phương pháp phòng chống tấn công che khuất bằng cách tiến hành kiểm tra ẩn danh các node hàng xóm, kết hợp với việc giới hạn bậc của các node tham gia vào mạng để tìm ra các node gây hại và loại bỏ chúng ra khỏi tập hàng xóm. Phương pháp này lấy ý tưởng từ thực tế đó là một node gây hại muốn thực hiện tấn công che khuất cần có bậc trong và bậc ngoài (hay số liên kết vào và liên kết ra của node) rất cao, cao hơn bậc trong và bậc ngoài của các node chuẩn khác, do đó để hạn chế tấn công cần làm giảm bậc của các node gây hại, và có thể phát hiện các node gây hại bằng việc kiểm tra ẩn danh các node có trong mạng. Đáng chú ý là phương pháp này có thể áp dụng cho cả hai dạng mạng ngang hàng có cấu trúc và không có cấu trúc. Do không có được mã nguồn chương trình của tác giả dùng trong bài báo[1], tôi đã vận dụng kiến thức tìm hiểu được trong bài báo để tự xây dựng một chương trình mô phỏng hoạt động của cơ chế kiểm tra ẩn danh trong mạng ngang hàng có cấu trúc Pastry. Sau khi chạy chương trình mô phỏng cơ chế kiểm tra ẩn danh để phát hiện các node gây hại trong mạng, kết quả thu được là rất cao, có tới 90% các node gây hại bị phát hiện dựa vào cơ chế kiểm tra này. Khóa luận này được trình bày theo năm chương chính, nội dung chính gồm: Chương 1. Tổng quan về mạng xếp chồng: giúp ta hiểu mạng xếp chồng là gì và các dạng mạng xếp chồng phổ biến của nó, cùng với mô tả chi tiết mạng xếp chồng ngang hàng có cấu trúc Pastry. Chương 2. Tấn công trong mạng ngang hàng: đề cập đến hai dạng tấn công chính trong mạng ngang hàng là tấn công che khuất và tấn công mạo nhận. Chương 3. Các cơ chế phòng chống tấn công che khuất: nêu ra các biện pháp chống tấn công che khuất với biện pháp chính là kiểm tra ẩn danh dựa vào giới hạn bậc của các node trong mạng. Chương 4: Mô phỏng và đánh giá cơ chế kiểm tra ẩn danh dựa trên Pastry: trình bày về xây dựng chương trình mô phỏng cùng với kết quả và nhận xét các thí nghiệm mô phỏng. Chương 5. Kết luận: đưa ra các nhận xét tổng quát về chống tấn công che khuất dựa vào kiểm tra ẩn danh. Chương 1. TỔNG QUAN VỀ MẠNG XẾP CHỒNG 1.1. Giới thiệu mạng xếp chồng Sự phát triển nhanh chóng của khoa học máy tính đang biến đổi cuộc sống của chúng ta từng ngày. Chưa bao giờ con người có thể giao tiếp, trao đổi thông tin và dữ liệu cho nhau thuận tiện và dễ dàng như ngày nay, đó là nhờ vào mạng Interner. Mạng Internet giúp liên kết các vùng miền, các quốc gia, các châu lục, nó mang cả thế giới đến gần nhau hơn bất chấp khoảng cách địa lý. Mạng Internet là một dạng mạng xếp chồng phổ biến nhất, đa phần các mạng mà chúng ta đang sử dụng là mạng xếp chồng. Vậy mạng xếp chồng là gì? Định nghĩa cho mạng xếp chồng [5] là: Mạng xếp chồng là một mạng ảo bao gồm các node và các kết nối vật lý được xây dựng dựa trên một mạng có sẵn với mục đích cung cấp các dịch vụ mạng mà mạng nó dựa trên không thể đáp ứng được. Mạng xếp chồng là một lớp của kiếm trúc mạng ảo dựa trên mạng vật lý, chúng cung cấp khả năng tương tác trực tiếp với người dùng. Mạng Internet chúng ta đang sử dụng là một mạng xếp chồng được xây dựng dựa trên mạng cục bộ (ví dụ như Ethernet), đường điện thoại. Mạng xếp chồng cung cấp cho chúng ta rất nhiều tiện ích cùng với cơ hội tiếp cận và sử dụng một lượng lớn tài nguyên không ngừng tăng cao có trên mạng Internet. Mạng xếp chồng cho phép các nhà phát triển mạng cùng người sử dụng có thể thiết kế và cài đặt dễ dàng môi trường truyền thông của riêng mình hay một giao thức thức dựa trên mạng Internet, cũng như định tuyến dữ liệu và quản lý các file được chia sẻ. Việc định tuyến dữ liệu trong mạng xếp chồng rất linh hoạt, nó có thể phát hiện và tránh tắc nghẽn mạng một cách nhanh chóng bằng cách chuyển đổi tuyến đường đi dựa trên nhiều độ đo khác nhau, ví dụ như thăm dò độ trễ. Các node trong mạng xếp chồng được liên kết tới rất nhiều các node khác nhờ vào cơ chế định tuyến mềm dẻo. Cũng giống như các liên kết mạng vật lý đã có, một node có thể giao tiếp liên tục với một node khác thông qua mạng xếp chồng. Với những lợi ích mà mạng xếp chồng mang lại, việc phát triển mạng xếp chồng là một xu hướng tất yếu trong tương lai. Với việc có càng nhiều node tham gia vào mạng xếp chồng sẽ giúp cho việc chia sẻ lượng lớn tài nguyên thông tin mạng Internet càng đạt hiệu quả cao. Các dạng điển hình của mạng xếp chồng bao gồm: Mạng xếp chồng đa phát (Multicast overlay) Mạng xếp chồng ngang hàng (Peer-to-peer overlay) Mạng xếp chồng tải file song song (Parallel file downloading overlay) Mạng định tuyến xếp chồng (Routing overlay) Có rất nhiều ứng dụng của mạng xếp chồng đang được sử dụng rộng rãi trong cuộc sống như ứng dụng chia sẻ file BitTorrent, hay điện thoại VoIP của Skyper… Nhưng trong bài khóa luận này chỉ chú trọng đến mạng xếp chồng ngang hàng. Mạng xếp chồng ngang hàng được chia ra làm hai dạng chính là mạng xếp chồng có cấu trúc (Structured overlay network) và mạng xếp chồng không có cấu trúc (Unstructured overlay network). 1.2. Mạng xếp chồng ngang hàng Mạng ngang hàng dựa trên hệ thống mạng xếp chồng đã thu hút được rất nhiều sự quan tâm của các nhà nghiên cứu và đã có nhiều hệ thống được xây dựng và đưa vào sử dụng trong cuộc sống hàng ngày. Có thể kể đến như ứng dụng chia sẻ file ngang hàng Gnutella, Kazaa. Ngoài ra, còn có rất nhiều các nghiên cứu hoạt động của Bảng băm phân tán (Distributed Hash Table) trên mạng xếp chồng như CAN, Chord và Pastry. Hệ thống xếp chồng ngang hàng được mô tả như một hệ thống phân tán, trong đó tất cả các node có vai trò như nhau và tất cả giao tiếp là đối xứng. Hệ thống này có rất nhiều khả năng quan trọng như: phân quyền điều khiển, tự tổ chức, khả năng điều chỉnh và mở rộng. Một trong những yêu cầu quan trọng trong mạng xếp chồng ngang hàng đó là cung cấp thuật toán hiệu quả cho việc duy trì liên kết trong mạng. Mỗi node trong mạng xếp chồng ngang hàng duy trì những con trỏ tới tập các node hàng xóm, đó là một tập chứa lượng nhỏ các node của mạng xếp chồng. Các con trỏ đó được sử dụng để duy trì liên kết xếp chồng, mỗi node có thể liên kết tới bất kì node nào trong mạng nhờ vào các con trỏ hàng xóm. Các con trỏ hàng xóm đó cũng được dùng để đáp ứng các chức năng chương trình ứng dụng. Hơn nữa, cập nhật tập hàng xóm sẽ thay đổi thông tin thành viên, các node hàng xóm được truy vấn để cung cấp thông tin về các con trỏ hàng xóm đó. 1.2.1. Tổng quan mạng xếp chồng ngang hàng không có cấu trúc Một mạng ngang không có cấu trúc khi các liên kết giữa các node trong mạng xếp chồng được thiết lập một cách ngẫu nhiên (hay không theo một quy luật nào). Những mạng như thế vậy dễ dàng được xây dựng vì một máy mới khi muốn tham gia mạng có thể lấy các liên kết có sẵn của một máy khác đang ở trong mạng để tạo thành liên kết mới của riêng mình. Khi một node muốn tìm một dữ liệu trong mạng xếp chồng không cấu trúc, yêu cầu tìm kiếm sẽ được truyền trên toàn mạng để tìm ra càng nhiều máy chia sẻ càng tốt. Hệ thống này thể hiện rõ nhược điểm đó là: không đảm bảo tìm kiếm sẽ thành công. Đối với tìm kiếm các dữ liệu phổ biến được chia sẻ trên nhiều máy, tỉ lệ thành công là khá cao, ngược lại, nếu dữ liệu chỉ được chia sẻ trên một vài máy thì xác suất tìm thấy là khá thấp. Tính chất này là hiển nhiên vì trong mạng ngang hàng không cấu trúc, không có bất kì mối tương quan nào giữa một máy tính và dữ liệu nó quản lý trong mạng, do đó yêu cầu tìm kiếm được chuyển đi một cách ngẫu nhiên đến một số máy trong mạng. Số lượng máy trong mạng càng lớn thì khả năng tìm thấy thông tin càng nhỏ. Một nhược điểm khác của hệ thống này là do không có định hướng, một yêu cầu tìm kiếm thường được chuyển cho một số lượng lớn máy trong mạng làm tiêu tốn một lượng lớn băng thông của mạng, dẫn đến hiệu quả tìm kiếm chung của mạng thấp. Các mạng xếp chồng ngang hàng phổ biến hiện nay là Napster, Gnutella, Fasttrack và eDonkey2000. 1.2.2. Tổng quan mạng xếp chồng ngang hàng có cấu trúc Mạng xếp chồng ngang hàng có cấu trúc khắc phục nhược điểm của mạng ngang hàng không có cấu trúc bằng cách sử dụng hệ thống Bảng băm phân tán (Distributed Hash Table - DHT). Hệ thống này định nghĩa liên kết giữa các node trong mạng xếp chồng theo một thuật toán cụ thể, đồng thời xác định chặt chẽ mỗi node sẽ chịu trách nhiệm đối với một phần dữ liệu chia sẻ trong mạng. Với cấu trúc này, khi một máy cần tìm một dữ liệu, nó chỉ cần áp dụng một giao thức chung để xác định node nào chịu trách nhiệm cho dữ liệu đó và sau đó liên lạc trực tiếp đến node đó để lấy kết quả. Giao thức này sử dụng bảng băm với các khóa. DHT tạo ra một hạ tầng cơ sở có thể sử dụng để xây dựng lên các dịch vụ phức tạp, một số hệ thống sử dụng mạng xếp chồng có cơ chế DHT là: BitTorrent: Phân tán file. BitTorrent lựa chọn sử dụng một DHT như một người theo dõi phân phối để cung cấp theo kế hoạch giữa client đang download một file đặc biệt. The Circle: Chia sẻ file và tán gẫu. Codeen: Web caching. Coral Content Distribution Network. CSpace: Các giao tiếp an toàn. Dijjer: Freenet-like mạng phân tán. eMule: Chia sẻ file. FAROO: Công cụ nghiên cứu Web Peer to Peer. GNUnet : Freenet-like mạng phân tán. I2P: Mạng nạc danh. JXTA: Mã nguồn mở P2P. Limewire:P2P Chia sẻ file có gắn java applet gọi DHT. NEOnet: Chia sẻ file. Warez P2P: Chia sẻ file. YaCy: Công cụ nghiên cứu phân tán. 1.2.2.1. Bảng băm phân tán DHT là một lớp các hệ thống phân tán không tập trung cung cấp dịch vụ tra cứu tương tự như một bảng băm: cặp khóa-giá trị được lưu trữ trong DHT, và những node tham gia có thể truy vấn dữ liệu thuận tiện bằng cách đưa ra một khóa. Việc duy trì ánh xạ từ khóa ra giá trị được phân tán giữa các node, bằng cách này sự thay đổi trong một tập các node tham gia chỉ gây ra sự gián đoạn nhỏ. Điều này cho phép DHT có thể mở rộng ra một số lượng rất lớn các node và kiểm soát được sự tham gia của node mới, sự ra đi hay lỗi của các node cũ. DHT nhấn mạnh vào các thuộc tính sau: Phi tập trung (Decentralization): Các node tham gia cấu thành hệ thống không có thành phần trung tâm làm điều phối mạng. Khả năng mở rộng: Hệ thống vẫn có thể hoạt động hiệu quả với hàng nghìn hoặc hàng triệu node. Khả năng chịu lỗi: Hệ thống vẫn có thể làm việc ổn định ngay cả khi có các sự kiện node tham gia, rời bỏ, lỗi diễn ra liên tục. Kỹ thuật khóa được sử dụng để đạt được mục đích là mỗi node chỉ cần liên kết với một số ít các node khác trong hệ thống, thường là O(logN) với N là số node tham gia. Vì vậy sự thay đổi trong các thành viên chỉ ảnh hưởng đến một phần nhỏ của hệ thống. Khi các thành phần này được đặt ở đúng vị trí của nó, thì cách thức sử dụng DHT cho việc lưu trữ và truy vấn dữ liệu sẽ được diễn ra như sau: Không gian khóa được sử dụng là một số rất lớn, có thể là các chuỗi 160 bit. Để lưu trữ một file với tên gọi filename và dữ liệu data trong DHT, giá trị băm của filename theo thuật toán SHA-1 được tính toán, tạo ra một khóa k có độ dài 160 bit,và một thông điệp put(k,data) được gửi tới một node bất kì tham gia trong DHT. Thông điệp được chuyển từ node này sang node khác thông qua mạng xếp chồng cho đến khi nó tới node cuối cùng chịu trách nhiệm quản lý khóa k, được xác định nhờ cách thức phân chia không gian khóa, ở đó cặp (k,data) được lưu trữ. Mọi node có thể truy xuất nội dung của file bằng cách băm filename để sinh ra khóa k và hỏi một node bất kì trong DHT để tìm dữ liệu ứng với khóa k đó với một thông điệp get(k). Thông điệp lại được định tuyến qua mạng xếp chồng tới node chịu trách nhiệm quản lý khóa k, node này sẽ trả lời với dữ liệu data được lưu trữ. Một số thiết kế DHT tìm đến tính bảo mật chống lại những người tham gia có mưu đồ xấu và cho phép người tham gia ẩn danh tính, mặc dù điều này không phổ biến trong các hệ thống mạng chia sẻ file ngang hàng. DHT phải giải quyết những vấn đề cơ bản của các hệ thống phân tán đó là: cân bằng tải, toàn vẹn dữ liệu, hiệu năng. 1.2.2.2. Cách thức phân chia không gian khóa Hầu hết DHT đều sử dụng một dạng băm nhất quán (Consistent hash) để ánh xạ các khóa vào các node. Kỹ thuật này áp dụng một hàm δ(k1, k2) định nghĩa một khái niệm trừu tượng về khoảng cách giữa hai khóa k1 và k2. Mỗi node được gán một khóa đơn được gọi là định danh (identifier). Một node với định danh i sở hữu tất cả các khóa mà i là định danh gần nhất của các khóa này, ước lượng theo hàm δ. Ví dụ : Hệ thống Chord có không gian định danh dạng vòng tròn, và δ(k1, k2) là khoảng cách đi theo chiều kim đồng hồ xung quanh đường tròn từ khóa k1 tới khóa k2. Do đó, không gian khóa đường tròn được chia thành các cung liên tiếp mà điểm cuối của cung này là các định danh ID của các node. Nếu i1 và i2 là hai ID liền kề nhau thì node có định danh ID i2 sở hữu tất cả các khóa nằm giữa i1 và i2. Hàm băm nhất quán có một thuộc tính quan trọng thuộc về bản chất đó là việc gỡ bỏ hay thêm vào các node chỉ làm thay đổi một tập các khóa sở hữu bởi các node có định danh liền kề, và các node khác thì không bị ảnh hưởng. Vì mọi thay đổi trong quyền sở hữu đều gây ra những di chuyển tốn kém băng thông của các đối tượng được lưu trữ trong DHT từ node này đến node khác, nên việc giảm thiểu việc sắp xếp lại sẽ tăng tính hiệu quả cho việc hỗ trợ các yêu cầu vào ra của node hay các sự cố lỗi của các node. Không gian khóa trong DHT rất đa dạng, có thể là không gian định danh một chiều như Chord và Pastry hoặc đa chiều như CAN. 1.3. Mạng xếp chồng ngang hàng có cấu trúc Pastry Mạng xếp chồng có cấu trúc Pastry sẽ được sử dụng trong mô phỏng được trình bày trong chương 4, do đó khóa luận này sẽ trình bày chi tiết về hệ thống Pastry, đại diện cho mạng xếp chồng ngang hàng có cấu trúc. Hệ thống định tuyến phân tán Pastry được đưa ra bởi Rowstron và Druschel vào năm 2001. Được xây dựng dựa trên cơ chế DHT. Mục đích chính của nó đó là tạo ra mạng ngang hàng phi tập trung hoàn toàn. Việc định tuyến của hệ thống được dựa trên việc đánh số gần nhau giữa các định danh. Ngoài việc chú trọng tới số bước trong định tuyến, Rowstron và Druschel cũng quan tâm tới miền mạng để đánh giá hiệu quả định tuyến trong Pastry. 1.3.1. Không gian định danh Trong Pastry, mỗi node và thành phần dữ liệu được gắn với l bit định danh, đó là một số nguyên nằm trong khoảng từ 0 cho tới 2l-1, thông thường l bằng 128. Không gian định danh của Pastry được bố trí dạng vòng tròn giống như Chord. Đối với node, định danh được hiểu là NodeId, còn với dữ liệu thì nó là khóa (key). Hình 1: Không gian định danh Pastry 4 bit với sáu khóa được ánh xạ vào năm node Trong hình 1 là không gian định danh của Pastry với l = 4, số định danh có thể có trong hệ thống là 24 = 16, b = 2 nên các định danh là các số trong hệ cơ số 22 = 4. Các node có trong hệ thống là N01 có định danh là 01, N10, N21, N23, N33 và N01. Các khóa là K01 có định danh là 01, K03, K22, K32 và K33 Định danh trong Pastry là một chuỗi số cơ số 2b, thông thường b bằng 4 tức định danh là các số trong hệ cơ số 16. Một khóa được đặt (quản lý) tại node có nodeId được đánh số gần với khóa nhất. Ví dụ như khóa K01 được đặt tại node N01, khóa K03 được đặt tại node N10. Độ chênh giữa giá trị của khóa K22 với hai node N21 và node N23 là bằng nhau, do đó khóa K22 có thể được hai node đó quản lí. 1.3.2. Thông tin dùng trong định tuyến Trạng thái của một node Pastry được chia làm 3 thành phần chính, đó là: Bảng định tuyến (Routing table) Tập lá (Leaf set) Tập lân cận (Neighborhoot set) Bảng định tuyến dùng để chứa các liên kết tới các node khác trong không gian định danh. Tập lá của một node chứa các node có định danh gần với định danh với nó. Các node gần nhau về mặt vị trí mạng sẽ được đưa vào trong tập lân cận. Pastry đo vị trí mạng dựa trên độ đo lân cận mạng vô hướng, độ đo này dựa trên hạ tầng cơ sở mạng có thể dựa trên số bước IP hoặc khoảng cách địa lý của các node. Hàng thứ 0 Hàng thứ 3 Mục thêm Hình 2: Bảng định tuyến, tập lá, tập lân cận của node có định danh 10233102 Trong quá trình định tuyến, các node chỉ sử dụng thông tin liên kết từ tập lá và bảng định tuyến của mình để xác định node đích nhận dữ liệu. 1.3.3. Trạng thái node 1.3.3.1. Bảng định tuyến Bảng định tuyến được kí hiệu là tập R. Bảng định tuyến của một node Pastry bao gồm l/b hàng, với 2b-1 mục trong mỗi hàng. Thứ tự hàng trong bảng định tuyến được tính từ 0, hàng 0 là hàng trên cùng của bảng. Trong bảng định tuyến của node n, mục ở hàng thứ i chứa các định danh của node Pastry có i số đầu tiên trong nodeId giống với i số đầu tiên trong nodeId của node n, việc so sánh này được tính lần lượt từng vị trí tương ứng với nhau của hai định danh và bắt đầu từ số đầu tiên bên trái. Nếu không có định danh của node nào thỏa mãn tính chất trên thì vị trí đó trong bảng định tuyến để trống. Do không gian định danh là rất lớn so với số lượng node có thể tham gia vào mạng, nên các hàng đánh số càng cao càng thưa hay số các mục trong bảng định tuyến để trống càng nhiều. Quá trình định tuyến sẽ lựa chọn node có các số đầu trong định danh phù hợp, và nó cũng khai thác vị trí mạng để lựa chọn node gần theo độ đo lân cận mạng. Để dễ hiểu hơn, ta sẽ xem xét bảng định tuyến của node có nodeId là 10233102 như trong hình 2. Trong mục được khoanh ở hình 2, mục này chỉ đến node có nodeId là 10222302, nó ở hàng thứ ba, do đó nó có ba số đầu tiên trong nodeId là 102 giống với ba số đầu trong nodeId của node chủ bảng định tuyến này. Sau ba số đầu tiên là số ở vị trí thứ tư có giá trị là 2, tương ứng với giá trị của mục được thêm trong cùng một cột với nó. 1.3.3.2. Tập lá Bảng định tuyến sắp xếp các nodeId theo các số ở đầu định danh. Để tăng hiệu quả tìm kiếm tập lá L của một node n chứa 2*2b node được đánh số (định danh) gần n nhất. Tập lá của node n được chia thành hai phần bằng nhau, mỗi phần có 2b định danh node, một phần chứa định danh của các node có nodeId lớn hơn nodeId của n và một phần chứa các định danh của node có nodeId nhỏ hơn nodeId của n. Bảng định tuyến và tập lá là hai nguồn thông tin chính cho việc định tuyến. 1.3.3.3. Tập lân cận Thay cho việc lưu định danh các node được đánh số gần nhau như tập lá, tập lân cận M của node n chứa các node gần với node n theo độ đo lân cận mạng. Tuy nhiên, tập này không được sử dụng trong quá trình định tuyến, nó chỉ dùng để duy trì vị trí mạng trong thông tin định tuyến. 1.3.4. Phương pháp định tuyến Định tuyến trong Pastry được chia làm hai bước chính. Đầu tiên, node tiến hành kiểm tra xem khóa k có nằm trong phạm vi tập lá của nó không. Nếu có, điều đó có nghĩa rằng khóa k được quản lý bởi node gần với các node trong tập lá. Do đó, node sẽ chuyển truy vấn tớ node trong tập lá được đánh số gần với khóa k nhất. Trong trường hợp là chính nó tức node đang xét có định danh gần với khóa k nhất thì quá trình định tuyến thành công. Nếu khóa k không nằm trong phạm vi của tập lá, thì truy vấn cần chuyển tiếp dựa vào bảng định tuyến. Trong trường hợp này, node n sẽ cố gắng chuyển truy vấn tới node trong bảng định tuyến có số lượng chữ số đầu trong nodeId giống với các số đầu trong khóa k nhiều hơn so với n. Nếu không có mục nào trong bảng định tuyến phù hợp, thì truy vấn được chuyển tiếp cho node có số chữ số đầu trong nodeId giống với các chữ số đầu trong khóa k nhiều như đố với nodeId của n như gần hơn n. 1.3.5. Khả năng tự tổ chức Trong thực tế, Pastry cần giải quyết các vấn đề node mới tham gia vào hệ thống, node rời khỏi hệ thống và node lỗi có thể xảy ra bất chợt trong khi vẫn phải duy trì tốt hoạt động định tuyến. Node mới tham gia hệ thống Trướng khi tham gia vào hệ thống Pastry, một node cần lựa chọn nodeId. Pastry cho phép một node tự lựa chọn nodeId của chính nó. Tuy nhiên việc tham gia có thể có nhiều yêu cầu hạn chế. Thông thường, một nodeId được tạo ta bằng cách băm giá trị khóa công khai của node hoặc địa chỉ IP của node. Để tham gia, node mới n cần biết một node Pastry k dựa vào độ đo lân cận mạng. Sau đó, node n cần khởi tạo các trạng thái cho mình bao gồm bảng định tuyến, tập lá, tập lân cận. Do k gần với n, nên các node trong tập lân cận của k là sự lựa chọn phù hợp cho n, do đó n sao chép tập lân cận của k để tạo ra tập lân cận cho riêng mình. Để tạo bảng định tuyến và tập lá, node n cần tìm kiếm thông tin về các node Pastry gần với n trong không gian định danh. Để làm được điều đó, n tiến hành gửi một thông điệp “join” đặc biệt thông qua node k với khóa là định danh của n. Theo quy tắc định tuyến chuẩn, thì truy vấn được chuyển tới đích là node c có nodeId được đánh số gần nhất với nodeId của n. Do đó, tập lá của node c phù hợp với n, nên n sao chép tập lá của c để tạo tập lá cho mình. Yêu cầu gia nhập tác động tới tất cả các node, với việc được chuyển tiếp yêu cầu hướng tới c, các thông tin định tuyến trong các lần chuyển tiếp đó được cung cấp cho n. Bảng định tuyến của node n được khởi tạo từ thông tin định tuyến của các node bắt đầu từ hàng thứ 0. Hàng này không liên quan đến nodeId của n, nên n có thể sử dụng các mục ở hàng thứ 0 của bảng định tuyến node K làm hàng số 0 trong bảng định tuyến của mình. Nếu n và k không có số ở đầu định danh của cả hai node giống nhau thì node n không thể sử dụng thêm các hàng khác của k. Thông điệp yêu cầu tham gia từ n tới c thông qua các node v1, v2...vn, với số lượng tăng dần các chữ số đầu định danh giống nhau giữa n và vi. Do vậy, hàng thứ nhất của bảng định tuyến của v1 là một lựa chọn tốt cho hàng thứ nhất trong bảng định tuyến của node n. Tương tự cho hàng thứ hai trong bảng định tuyến của n với node v2. Dựa vào các thông tin định tuyến đó, bảng định tuyến của node n được hình thành. Cuối cùng, node mới n gửi trạng thái của nó tới tất cả các node trong dữ liệu định tuyến của mình. Các node đó có thể cập nhật lại bảng định tuyến của mình cho phù hợp. Do mỗi node chỉ chứa thông tin về một lượng nhỏ các node trong Pastry, nên việc đến và rời đi của một node chỉ ảnh hưởng đến một lượng nhỏ các node trong hệ thống Pastry. Node lỗi Node lỗi được phát hiện khi có một node thử liên lạc với node lỗi. Chỉ khi định tuyến đòi hỏi phải tiếp xúc với các node trong bảng định tuyến và tập lá, đó chính là nguyên nhân gây ra chậm trễ trong phát hiện node lỗi. Với các node trong tập lân cận, do chúng không tham gia vào quá trình định tuyến nên cần kiểm tra chúng thường xuyên theo chu kỳ. Các node lỗi cần đưa ra khỏi bảng định tuyến để đảm bảo cho quá trình định tuyến diễn ra một cách chính xác. Để thay thế node lỗi ở mục i hàng j của bảng định tuyến ( ta kí hiệu là), node liên hệ với một node khác để tham khảo hàng i. Các mục trong hàng j tương ứng của node từ xa được xem xét cho vị trí trong bảng định tuyến cần thay thế. Do đó nó có thể sao chép mục của node từ xa cho bảng định tuyến của nó sau khi đã kiểm tra sự tồn tại của node được dùng để thay thế. Trường hợp node trong mục định sao chép cũng lỗi thì có thể thăm dò node khác trong hàng j để thay thế mục . Nếu không có node nào còn sống có các số đầu trong nodeId phù hợp có thể dùng được bằng phương pháp này, thì tiến hành mở rộng xem xét các node thông qua truy vấn các node trong hàng Rj-1. Phương pháp thay thế này có xác suất thành công cao. Node rời hệ thống Pastry có thể duy trì trạng thái thông tin định tuyến khi xuất hiện node lỗi, việc xử lý node rời hệ thống cũng được thực hiện tương tự như vậy, nhưng có thêm quá trình xử lý dữ liệu liên quan đến node rời đi. 1.3.6. Thực hiện định tuyến Pastry tối ưu hóa việc định tuyến và xác định vị trí node chịu trách nhiệm về khóa, nó cố gắng đồng thời việc giảm số bước chuyển tiếp để tới được node đích và khai thác vị trí mạng để làm giảm chi phí cho mỗi bước nhảy. Độ dài định tuyến Lược đồ định tuyến trong Pastry về cơ bản chia không gian định danh thành hai miền với kích thước 2n với n là cấp số nhân của 2b. Chỉ dẫn định tuyến từ miền bậc cao tới miền bậc thấp, do đó làm giảm lượng không gian định danh phải tìm kiếm trong mỗi bước. Số bước định tuyến trung bình sẽ là một hàm logarithm của kích thước hệ thống. Nếu tất cả thông tin định tuyến của tất cả các node là chính xác và không có node lỗi nào, sẽ có ba trường hợp trong sơ đồ định tuyến: Trường hợp thứ nhất, các node chuyển tiếp truy vấn thông qua bảng định tuyến, truy vấn được chuyển tiếp tới node có số chữ số đầu trong nodeID trùng với khóa truy vấn nhiều hơn so với node hiện thời. Số node có nodeId như vậy sẽ được giảm theo với hệ số thấp nhất là 2b trong từng bước. Do đó thông điệp tới đích chỉ trong vòng log2n(N) bước. Trường hợp thức hai, thông điệp truy vấn được chuyển tiếp qua tập lá. Nó làm tăng số bước lên một. Trường hợp thứ ba, khóa không nằm trong miền tập lá và cũng không có mục nào trong bảng định tuyến phù hợp hơn node hiện thời. Do đó, truy vấn được chuyển tiếp cho node có chung số chữ số đầu trong nodeId bằng với số chữ số đầu của nodeId hiện thời chung với khóa, nhưng node được chọn để chuyển tiếp thông điệp đó có nodeId gần với khóa hơn node hiện thời. Việc này sẽ làm tăng số bước định tuyến. Với tập lá có kích thước vừa phải |L| = 2*2b, xác suất trường hợp này xảy ra nhỏ hơn 0.6%. Mức độ phức tạp trung bình của phần định tuyến còn lại là O(log2b(N)), cao hơn giá trị của b nhưng phải trả giá cho việc định tuyến nhanh hơn này đó là tăng các trạng thái cần quản lý trong mỗi node. Do đó, với b thông thường bằng 4 nhưng hoạt động của Pastry có thể lựa chọn sự đánh đổi thích hợp đối với từng ứng dụng. Vị trí mạng Bằng cách khai thác vị trí mạng, tối ưu định tuyến trong Pastry không chỉ hướng tới việc làm giảm số bước mà còn giảm chi phí cho mỗi bước. Nhờ sử dụng bảng định tuyến của node để gửi thông điệp, nó có thể chọn node có các số đầu trong định danh phù hợp trong các mục của bảng định tuyến. Bằng việc lựa chọn các node gần theo tiêu chí vị trí của mạng, độ dài của mỗi tuyến đường sẽ được giảm đến mức tối thiểu.  Chương 2. TẤN CÔNG TRONG MẠNG NGANG HÀNG Mạng máy tính mang lại nhiều lợi ích thiết thực cho con người, tuy nhiên nó cũng luôn ẩn chứa những nguy hiểm cho máy tính và người sử dụng nó. Những nguy hiểm đó đến từ những kẻ có mục đích xấu, chúng luôn muốn lợi dụng mạng máy tính để thực hiện những hành vi phá hoại. Thật khó có thể tưởng tưởng nổi hậu quả của việc mất cắp thông tin trong thời buổi phát triển mạnh mẽ của ngành công nghệ thông tin ngày nay. Kẻ xấu có thể tấn công vào máy tính của bạn, phá hoạt hệ thống mạng hoặc máy tính bạn sử dụng. Tài liệu cá nhân của bạn có thể bị đánh cắp, và chỉ một giây sau nó có thể được công bố cho toàn bộ thế giới biết đến. Một công ty có thể bị phá sản nếu tài liệu mật về sản phẩm mới hay kế hoạch kinh doanh bị đối thủ cạnh tranh nắm được. An ninh quốc gia cũng bị ảnh hưởng lớn nếu thông tin bí mật quân sự bị kẻ xấu có được và đưa lên mạng cho toàn thế giới biết đến… Mạng máy tính càng phát triển thì nguy cơ bị tấn công cũng tăng cao. Không có gì là hoàn hảo cả, do đó luôn có những lỗ hổng trong mạng để kẻ xấu lợi dụng vào những hành động phá hoại. Trong mô hình giao tiếp thông thường giữa máy khách và máy chủ, thì bên bị tấn công cao thường là máy chủ. Khi máy chủ bị tấn công, hệ thống bị tê liệt, kẻ tấn công có thể thực hiện những hành vi đen tối của mình. Đố với mạng xếp chồng ngang hàng, các máy tính tham gia có vai trò như nhau, vừa đóng vai trò máy khách vừa có vai trò là máy chủ. Một đặc điểm quan trọng trong mạng xếp chồng ngang hàng đó là, một node sử dụng các node khác trong mạng như một bộ định tuyến. Do đó dữ liệu và thông tin truyền đi giữa hai node có sự tham gia của nhiều node khác. Sẽ rất nguy hiểm nếu một trong các node tham gia định tuyến chuyển tiếp dữ liệu lại là một node gây hại. Sự bình đẳng trong mạng ngang hàng giúp kẻ tấn công dễ dàng tham gia vào mạng và phá hoại sự ổn định của mạng. Do đó việc nghiên cứu và tìm giải pháp chống lại những kẻ xấu muốn tấn công mạng là một yêu cầu quan trọng và đang thu hút nhiều sự quan tâm của mọi người. Mục tiêu của khóa luận này đó là tìm hiểu các phương pháp chống tấn công trong mạng xếp chồng. Có hai dạng tấn công chính thường được kẻ xấu sử dụng để tấn công mạng ngang hàng đó là tấn công mạo nhận (Sybil attack) và tấn công che khuất (Eclipse attack). Nội dung mà khóa luận này đề cập đến đó là phương pháp chống tấn công che khuất, tuy nhiên cũng cần phải nói qua về tấn công mạo nhận, bởi tấn công mạo nhận cũng có một vài đặc điểm giống với tấn công che khuất. 2.1. Tấn công mạo nhận Trước hết tôi xin đưa ra định nghĩa về tấn công mạo nhận [2] như sau: Tấn công mạo nhận là dạng tấn công mà kẻ tấn công phá hoại hệ thống mạng ngang hàng bằng cách tạo ra một lượng lớn các node ảo và sử dụng chúng để tạo ra ảnh hưởng lớn trong mạng ngang hàng. Hệ thống mạng ngang hàng có thể gặp nguy hiểm bởi quá trình khởi tạo định danh cho mỗi node mới muốn gia nhập vào mạng. Mức độ nguy hiểm của mạng phụ thuộc và mức độ cho phép các đối tượng mới không có một liên kết đáng tin cậy nào tham gia vào mạng. Tấn công mạo nhận lợi dụng đặc tính của mạng ngay hàng, đó là mỗi node cần duy trì liên kết tới các node hàng xóm của nó, đặc tính này giúp cho mạng xếp chồng hình thành và duy trì. Kiểu tấn công này sẽ rất nguy hiểm đối với hệ thống mạng ngang hàng có cấu trúc sử dụng cơ chế bảng băm phân tán như mạng CAN, Chord, Pastry và Tapestry. Bởi, trong cơ chế DHT mỗi node cần duy trì một tập các node hàng xóm mà nó liên kết tới, và tập này được hình thành với những quy tắc riêng đối với mỗi loại mạng dùng DHT. Kẻ tấn công có thể biết dễ dàng định danh của một node trong mạng, từ đó nó có thể sinh ra các định danh ảo trong mạng để đưa các định danh ảo đó vào tập hàng xóm của các node. Khi đạt được mục tiêu, tức trong mạng có rất nhiều định danh ảo do kẻ tấn công sinh ra thì nó có thể kiểm soát lưu lượng, dữ liệu và các thông tin truyền trong mạng. Bởi mỗi node trong mạng muốn truyền thông điệp hay dữ liệu thì các node mà nó liên hệ để gửi dữ liệu đi đó là các node trong tập hàng xóm của nó, như vậy các node sẽ gửi dữ liệu tới node tấn công mạng. Kẻ tấn công có quyền quyết định chuyển tiếp hay không dữ liệu đó. Sẽ rất nguy hiểm khi kẻ tấn công có thể nắm được một lượng lớn các định danh trong mạng xếp chồng có cấu trúc. Nếu tỉ lệ node ảo mà nó sinh là vô hạn thì nó có thể chiếm tới gần như là 100% các node trong mạng, như vậy nó có thể che khuất các node chuẩn khác trong mạng. Như vậy, chỉ cần một node gây hại có thể khống chế toàn bộ mạng xếp chồng ngang hàng. 2.2. Tấn công che khuất Tấn công che khuất là một dạng chung của tấn công trong mạng xếp chồng. Trong tấn công che khuất, một kẻ tấn công điều khiển một lượng lớn các đối tượng là thành viên trong tập hàng xóm của node chuẩn. Trong trường hợp này, một nhóm các node gây hại liên kết với nhau để lừa các node chuẩn bằng cách đưa các node gây hại vào tập hàng xóm của các node chuẩn. Bằng việc thực hiện tấn công che khuất, kẻ tấn công có thể điều khiển một phần đáng kể của mạng xếp chồng. Hơn nữa, một lượng lớn các node gây hại có thể che khuất nhiều node chuẩn để điều khiển toàn bộ mạng xếp chồng. Các node xếp chồng không thể chuyển tiếp một cách chính xác các thông điệp và mạng sẽ không được quản lý. Hình 3: Các node gây hại chia mạng xếp chồng ra làm hai mạng con. Tấn công che khuất lợi dụng tập hàng xóm của các node để tiến hành tấn công mạng xếp chồng. Để có thể tấn công, kẻ tấn công nhắm tới tập hàng xóm của các node chuẩn. Chúng tìm cách đưa các node gây hại vào tập trong các tập hàng xóm của các node chuẩn, khi thành công các node chuẩn muốn gửi dữ liệu cũng như các thông điệp đều đi qua các node gây hại trước. Như vậy, các node gây hại có thể quyết định gửi hay không gửi các dữ liệu và thông điệp đó tới node đích. Các node gây hại có thể đưa các node gây hại khác vào trong tập hàng xóm của các node chuẩn nhờ dựa vào quá trình xin tham gia vào mạng của các node mới. Nếu node mới tham gia liên hệ đầu tiên với một node gây hại, thì tập hàng xóm mà nó có chính là tập các node do node gây hại đó đưa cho và hiển nhiên tập này chứa các node gây hại có thông đồng với node gây hại mà node mới liên hệ đầu tiên. Ngoài ra, node gây hại còn có thể xâm nhập vào tập hàng xóm của các node trong quá trình duy trì liên kết mạng được thực hiện theo chu kì. Quá trình này sẽ tìm và loại bỏ các node lỗi ra khỏi các tập hàng xóm và thay thế vào đó là các node khác đang hoạt động. Các node gây hại lợi dụng quá trình này để làm tăng số lượng các node gây hại trong các tập hàng xóm của các node chuẩn. Tấn công che khuất cần một lượng nhất định các node gây hại thông đồng với nhau mới có thể thực hiện thành công. Chúng liên kết với nhau, “che khuất” mạng, làm cho các node chuẩn chỉ biết đến chúng và mọi liên hệ tới các node chuẩn khác đều bị chi phối và khống chế. Tấn công che khuất giống như dạng nâng cao của tấn công người ở giữa (Man in the middle attack). Nếu chỉ có một node gây hại thực hiện tấn công che khuất (điều này rất khó thực hiện được), thì nó có thể thực hiện các hành động như: Node gây hại tấn công mặt phẳng điều khiển (control plane) bằng các vô hiệu hóa việc định tuyến lại các thông điệp. Node gây hại có thể loại bỏ các thông điệp mà nó nhận được, nhằm mục đích chia cắt mạng. Node gây hại có thể tấn công mặt phẳng dữ liệu (data plane) bằng cách tiêm nhiễm file độc hoặc yêu cầu lại các file độc nhân danh một node vô hại, các file đó sẽ được lưu vào bộ đệm hoặc sao chép nhiều lần. Như vậy, chỉ với một kẻ thực hiện tấn công che khuất cũng có thể gây ảnh hưởng tới hệ thống, tuy nhiên để cuộc tấn công đạt hiểu quả cao thì cần có nhiều node cùng tham gia tấn công. Với chỉ một lượng nhỏ các node cũng có thể thực hiện tấn công che khuất. 2.3. So sánh tấn công mạo nhận và tấn công che khuất Tấn công mạo nhận ở một mức độ nào đó cũng giống với tấn công che khuất. Cả hai dạng tấn công đều hướng tới mục đích kiểm soát tập hàng xóm của các node chuẩn. Bởi chỉ có như vậy, chúng mới có thể chi phối được quá trình giao tiếp của node chuẩn với các node khác trong mạng, khống chế được lưu lượng trong mạng và điều khiển mạng theo mưu đồ của mình. Tuy nhiên, tấn công mạo nhận cần sinh ra các node ảo, càng nhiều node ảo thì khả năng thành công của tấn công mạo nhận càng cao. Nhưng việc tạo các node ảo sẽ khó thành công khi hệ thống mạng kiểm soát chặt chẽ việc cấp định danh cho các node mới muốn tham gia vào mạng. Trong tấn công che khuất lại khác, nó dùng các node thực, chính là các node gây hại. Thay vì đưa các node ảo vào trong tập hàng xóm của node chuẩn, các node gây hại trong tấn công che khuất đưa các node gây hại khác vào. Tấn công che khuất có thể thành công với lượng nhỏ các node gây hại trong mạng cùng thông đồng với nhau. Trong tấn công mạo nhận, một node gây hại hoạt động đơn lẻ để sinh ra rất nhiều node ảo để tấn công mạng. Chương 3. CÁC CƠ CHẾ PHÒNG CHỐNG TẤN CÔNG CHE KHUẤT 3.1. Một số phương pháp phòng chống tấn công che khuất Ta có thể nhận thấy rằng phương pháp tấn công che khuất mạng xếp chồng đều tập trung vào kiểm soát tập hàng xóm của các node. Do đó, để có thể phòng chống tấn công hiệu quả cần tập chung quản lý tập hàng xóm, cần sinh ra một cơ chế để đảm bảo cho tập hàng xóm luôn an toàn trước các node gây hại để chống lại các cuộc tấn công. Đã có các biện pháp bảo vệ phi tập trung chống lại các cuộc tấn công che khuất được đưa ra, các biện pháp này đòi hỏi phải bổ xung thêm các quy tắc lựa chọn tập hàng xóm. Các phương pháp này đều hướng tới hai loại: ràng buộc cấu trúc và ràng buộc lân cận. Ràng buộc cấu trúc chặt chẽ hơn – Stronger structural constraints Các mạng chồng như CAN, Chord nguyên bản và Pastry với bảng định tuyến có ràng buộc nhất định (Constraints routing table – CRT)[5] cải thiện mạnh mẽ ràng buộc cấu trúc trong tập hàng xóm. Mỗi thành viên trong tập hàng xóm được xác định là một node trong mạng xếp chồng có định danh gần nhất với một điểm riêng biệt trong không gian định danh. Ràng buộc này đánh bại các cuộc tấn công che khuất với hai điều kiện như sau: Đầu tiên, mỗi điểm nút có một định danh duy nhất và không thể giả mạo được. Việc này có thể được thực hiện được nhờ dựa vào một cơ quan ngoại tuyến đáng tin cậy đưa ra bản mã hóa của định danh đã được ký, bằng cách này có thể chống được tấn công mạo nhận. Thứ hai, mạng xếp chồng cần có cơ chế tìm ra node đang sống trong mạng có định danh gần nhất với một vị trí bất kỳ được yêu cầu trong không gian định danh. Cơ chế này đảm bảo rằng một truy vấn đến một node có định danh được chọn ngẫu nhiên có khả năng là node gây hại cũng bằng xác suất chọn ngẫu nhiên một node là node gây hại. Phương pháp định tuyến cổ điển có thể đạt được điều này bằng cách kết hợp với việc xác thực định danh tin cậy, kiểm tra mật độ định danh, nhận biết định tuyến dư thừa bằng cách sử dụng bảng định tuyến. Điều trở ngại lớn nhất trong việc sử dụng ràng buộc cấu trúc mạnh đó là nó sẽ làm mất tính linh hoạt trong việc lựa chọn hàng xóm, cản trở việc tối ưu hóa mạng xếp chồng bằng cách sử dụng cơ chế lựa chọn hàng xóm gần (Proximity neighbor selection – PNS)[6]. Hơn nữa, để đảm bảo an toàn cho định tuyến cổ điển sẽ tốn chi phí rất cao. Proximity constraint – Ràng buộc gần Hildrum và Kubiatowicz [3] đưa ra một phương pháp bảo vệ chống lại tấn công che khuất hoàn toàn khác biệt với phương pháp được đưa ra ở trên, phương pháp này dựa trên việc lựa chọn các hàng xóm gần. Mỗi node lựa chọn các node làm tập hàng xóm cho mình sao cho liên kết tới các node đó có độ chễ nhỏ nhất và chúng thỏa mãn yêu cầu ràng buộc cấu trúc của một tập hàng xóm. Chỉ có một lượng nhỏ các node gây hại có thể đáp ứng được độ trễ mạng thấp, do đó các node gây hại khó có thể tăng cường tấn công che khuất hệ thống. Phương pháp bảo vệ này cần đảm bảo rằng việc đo độ trễ không bị thao túng bởi các phần tử tấn công. Nếu độ chính xác của phép đo là 1ms và có một lượng lớn các node xếp chồng có giá trị đo nằm trong khoảng này thì việc phòng chống không có hiệu quả. Trên thực tế, có rất nhiều node khác nhau cùng xuất hiện trong dải độ trễ hẹp. Hơn nữa kết quả thực nghiệm đã chỉ ra rằng với các giá trị độ trễ thực tế được đo tính trên mạng Internet, hiệu quả của biện pháp phòng thủ dựa trên PNS sẽ giảm dần khi kích thước mạng chồng tăng lên. Nhận xét Có thể nhận thấy rằng việc duy trì những ràng buộc cấu trúc có thể tạo ra một phòng tuyến bảo vệ hiệu quả chống lại các cuộc tấn công che khuất, nhưng nó cũng tạo ra những khoản chi phí phụ trội và cản trở việc tối ưu hóa những ứng dụng quan trọng như PNS. Mặt khác, phương pháp phòng thủ dựa trên ràng buộc gần chỉ có hiệu quả với mạng có kích thước nhỏ. 3.2. Cơ chế giới hạn bậc Để có thể chống tấn công che khuất, có một phương pháp đã được đưa đó là cơ chế giới hạn bậc [1]. Cơ chế giới hạn bậc có thể áp dụng cho cả mạng ngang hàng có cấu trúc và mạng ngang hàng không có cấu trúc. Đây là một cơ chế khá hữu hiệu để chống tấn công che khuất. Bậc ở đây dùng để chỉ các liên kết tới các node trong mạng xếp chồng. Bậc trong của một node là số các liên kết trỏ tới node đó, bậc ngoài là số liên xuất phát từ nó đi tới các node khác. Một node A có chứa node B trong tập hàng xóm của nó, như vậy có nghĩa là node A trỏ tới node B, ta gọi liên kết từ A tới node B là một liên kết ngoài của node A. Số liên kết ngoài của A được gọi là bậc ngoài của A, bậc ngoài của một node bằng số node có trong tập hàng xóm của node đó. Node A trỏ tớ node B, liên kết đó được coi là liên kết trong của node B, số liên kết trong đó là bậc trong của B. Ý tưởng cơ bản đằng sau cho cơ chế phòng chống này rất đơn giản: Trong tấn công che khuất, bậc trong của các node gây hại cao hơn giá trị bậc trong trung bình của các node chuẩn. Bởi các node gây hại nằm trong rất nhiều tập hàng xóm của các node chuẩn trong mạng thì mới có thể tiến hành “che khuất” khống chế mạng và các node. Do đó, nếu chúng ta giới hạn bậc trong của mỗi node, thì sẽ làm giảm số node gây hại có trong tập hàng xóm của các node chuẩn, làm cho kẻ tấn công khó có thể thực hiện ý đồ “che khuất” của mình. Khi ta áp dụng cơ chế ép giới hạn bậc, các node chuẩn có thể chọn các hàng xóm của nó từ một tập phụ các node xếp chồng có bậc trong nhỏ hơn giới hạn cho phép. Cơ chế đó cũng bao gồm việc giới hạn bậc ngoài của các node, nếu không các node gây hại có thể sử dụng bậc trong của các node chuẩn để chặn các node chuẩn trỏ tới các node chuẩn khác. Vậy các node chuẩn cần chọn các hàng xóm từ một tập gồm các node xếp chồng có bậc trong và bậc ngoài nhỏ hơn giới hạn cho phép. Phương pháp giới hạn bậc đòi hỏi mỗi node cần có một chứng nhận xác thực, mỗi định danh của node được gắn kèm với một khóa công khai. Ngoài ra, mạng xếp chồng còn phải hỗ trợ việc định tuyến an toàn nguyên thủy sử dụng CRT. Đánh giá Phương pháp giới hạn bậc rất hữu hiệu trong phòng chống tấn công che khuất, nó có thể khống chế tỉ lệ node gây hại có trong tập hàng xóm của các node chuẩn. Có thể chứng minh điều này bằng toán học một cách dễ dàng. Gọi N là tổng số node trong hệ thống và giá trị trung bình của bậc trong và bậc ngoài của các node tương ứng là O và I. Gọi f là tỉ lệ các node gây hại, f ’ là tỉ lệ các mục hàng xóm của node chuẩn tham chiếu tới các node gây hại. Ta dễ dàng đưa ra nhận xét rằng tổng các liên kết chỉ tới tới node gây hại là: Ttotal=NfI Tổng các liên kết đi ra từ node chuẩn là : Ototal=N( 1-f )O Với f ’Ototal là tổng số các liên kết từ node chuẩn chỉ tới các node gây hại, ta có: f ’Ototal ≤ Ttotal Sau khi giản ước bất đảng thức trên ta có f ’≤. Làm cho I=O chúng ta có: f ’≤ Như vậy, tỉ lệ các node gây hại trong tập hàng xóm không vượt quá tỉ lệ của node gây hại so với số node chuẩn có trong mạng khi ta thiết lập số bậc trong bằng số bậc ngoài. Khi tăng giá trị trung bình bậc trong I làm tăng f ’, node gây hại có thể lợi dụng tỉ lệ lớn bậc trong của các node chuẩn và tăng hiệu quả của tấn công che khuất. Cơ chế phân phối để giới hạn bậc Để thực thi kĩ thuật này, cần giới hạn bậc trong và bậc ngoài đối với mỗi node. Chúng ta tóm tắt cơ chế phân tán dựa trên truy vấn để đảm bảo việc giới hạn bậc. Chúng ta giả định rằng đã có một kĩ thuật để xác nhận thông điệp để ngăn các node gây hại ở giữa phản hồi giả các truy vấn, giống như chữ kí số. Mỗi thông điệp truy vấn bao gồm thời gian lúc truy vấn được xác thực trong trong phản hồi để đảm bảo tính chuẩn xác. Chúng ta cũng giả định trong mạng tồn tại một cơ chế đảm bảo rằng việc phân phối định danh node một cách chính xác, để chắc chắn rằng các node gây hại không thể sở hữu nhiều định danh và không thể chọn định danh mà chúng muốn. Mỗi node A trong mạng xếp chồng cần duy trì một tập chứa tất cả các node mà trong tập hàng xóm của nó có chứa node A. Chúng ta gọi đó là tập Con trỏ ngược (Back pointer set) của A. Theo định kì, A kiểm tra từng thành viên trong tập hàng xóm của nó thông qua việc hỏi tập con trỏ ngược của node đó. Nếu số mục trong tập con trỏ ngược trả về lớn hơn giới hạn bậc trong hoặc A không nằm trong tập con trỏ ngược thì A loại bỏ thành viên đó khỏi tập hàng xóm của nó. Trong quá trình kiểm tra, chúng ta cần đảm bảo rằng node đang được kiểm tra không biết được node A. Nếu không, node được kiểm tra có thể tạo dễ dàng một tập con trỏ ngược với kích thước phù hợp và có A. Hình 4: Tập Con trỏ ngược - Back pointer set Để ngăn chặn kẻ tấn công chi phối bậc trong của node chuẩn, mỗi node B kiểm tra thường xuyên các thành viên trong tập con trỏ ngược của nó bằng việc hỏi chúng tập hàng xóm mà nó sở hữu. Nếu B không nằm trong tập hàng xóm được trả về hoặc kích thước tập hàng xóm trả về lớn hơn giới hạn bậc ngoài, B loại bỏ các node đó khỏi tập con trỏ ngược của mình. Các node được kiểm tra cũng không được biết được B. Kĩ thuật này có thể dùng để đảm bảo rằng giá trị trung bình của bậc trong và bậc ngoài được giới hạn. Khi giới hạn được thiết lập tới giá trị trung bình của đồ thị xếp chồng, tỉ lệ tập hàng xóm của node chuẩn bị điều khiển bởi node gây hại chỉ là f/(1-f) với f là tỉ lệ node gây hại trong mạng xếp chồng. 3.3. Cơ chế kiểm tra ẩn danh Để kĩ thuật ở được trình bày ở trên hoạt động, chúng ta cần sử dụng một đường kết nối ẩn danh (Anonymous channel) giữa node tiến hành kiểm tra và node đang bị kiểm tra. Với việc kiểm tra ẩn danh ta có thể phát hiện các node gây hại, từ đó loại bỏ chúng ra khỏi tập hàng xóm của node chuẩn. Sự thăm dò đó là kiểm tra ẩn danh thông qua một node trung gian ngẫu nhiên trong mạng xếp chồng. Nếu node trung gian đó là một node chuẩn thì nó sẽ chuyển tiếp yêu cầu tới node đích mà không để lộ danh tính của node yêu cầu. Nếu node trung gian là node gây hại, nó có thể làm lộ danh tính của node yêu cầu cho node bị kiểm tra (nếu node bị kiểm tra là node gây hại) hoặc nó có thể vứt bỏ thông điệp kiểm tra (nếu như node được kiểm tra là node chuẩn). Hơn nữa, một node gây hại có thể quyết định loại bỏ yêu cầu kiểm tra khi node trung gian là node chuẩn. Hình 5: A kiểm tra B thông qua node trung gian I Tuy nhiên, khi node gây hại lựa chọn trả lời yêu cầu kiểm tra tới nó thông qua node trung gian chuẩn, nó có thể lời bằng một tập con ngẫu nhiên với kích thước cho phép với các node lấy từ tập con trỏ ngược của nó. Để đạt được hiệu quả cao, chúng ta cần thực hiện kiểm tra mỗi node nhiều lần, với các node trung gian ngẫu nhiên khác nhau để có thể thu thập đủ dữ liệu từ đó đưa ra quyết định node bị kiểm tra là node gây hại hay node chuẩn. Cơ chế kiểm tra Đối với mỗi node hàng xóm, chúng ta tiến hành n cuộc kiểm tra trước khi đánh giá, mỗi yêu cầu kiểm tra đòi hỏi node hàng xóm trả về một tập con trỏ ngược của chính nó. Trong lúc kiểm tra, một node ngẫu nhiên được chọn trong mạng xếp chồng chuyển tiếp thông điệp kiểm tra tới node hàng xóm bị kiểm tra. Nếu như tập con trỏ ngược trả về có chứa node yêu cầu kiểm tra thì đó là một cuộc kiểm tra thành công. Nếu tập con trỏ ngược trả về không chứa node thực hiện kiểm tra, thì đó là một cuộc kiểm tra thất bại. Nếu một phản hồi nhận được không nằm trong khoảng giới hạn thời gian cho phép thì nó sẽ được xem xét nên loại bỏ hay không. Sau n lần kiểm tra đã hoàn thành hoặc có một lỗi xảy ra, các bước thực hiện kế tiếp là: Bước 1: Nếu lỗi xảy ra trong tất cả các cuộc kiểm tra thì node đích là một node gây hại. Nếu không ta chuyển sang bước 2. Bước 2: Ta tính tỉ lệ thành công trong n cuộc kiểm tra đã thực hiện. Nếu tỉ lệ đó nhỏ hơn (1-k/n), thì node được kiểm tra bị coi như là node gây hại. Giá trị của k là số thất bại chúng ta cho phép xảy ra trong n lần kiểm tra. Phân tích Trước tiên chúng ta cần định nghĩa các thuật ngữ được nói đến trong quá trình phân tích. Khi một node gây hại nhận một thông điệp kiểm tra thông qua một node chuẩn, nó quyết định trả lời hay không với một xác suất c và tập trả về chứa node thực hiện kiểm tra có xác suất p. Xét node A chứa B trong tập hàng xóm, B là node gây hại và A là node chuẩn. Giả sử rằng A gửi thông điệp kiểm tra thông qua I, I là một node trung gian ngẫu nhiên. Xác suất I là node gây hại là f. Kích thước tập con trỏ ngược của B là |M|, với |M|>X, trong đó X là giới hạn cho phép của tập con trỏ ngược. Với mỗi lần kiểm tra, xác xuất để A có trong tập kết quả trả về là f+(1-f )pc, đồng nghĩa với việc B sẽ qua được cuộc kiểm tra dù I là node gây hại hay không và B trả lời cuộc kiểm tra bằng một tập node chứa A với xác suất p. Đối với node chuẩn, giá trị kì vọng của số phản hồi thành công là n(1-f ) trong số n cuộc kiểm tra, ta chỉ tính các cuộc kiểm tra đi qua node trung gian là node chuẩn. Tuy nhiên, việc một node chuẩn bị tình nghi là node gây hại có thể xảy ra (xác thực lỗi). Xác thực lỗi có thể xảy ra khi tỉ lệ node trung gian được chọn là node gây hại lớn hơn f và chúng loại bỏ các thông điệp kiểm tra, đó là nguyên nhân làm cho node chuẩn bị coi là node gây hại. Do đó, trong quá trình kiểm tra chúng ta cần đánh dấu node gây hại ngay khi số phản hồi thành công mà ta nhận được nhỏ hơn n-k. k là một giá trị cụ thể quy định số xác thực lỗi mà ta cho phép. Chúng ta cần xác định giá trị thích hợp của k. Xác suất k node trong n node trung gian là node gây hại được tính bởi công thức f k(1-f )n-k, giả sử rằng mỗi node trung gian là node gây hại với xác suất f. Cũng cần chú ý rằng n-k cần phải lớn hơn nf, nếu không một node gây hại chỉ có thể phản hồi khi thông điệp kiểm tra tới thông qua một node gây hại khác và sẽ không bao giờ phản hồi khi thông điệp kiểm tra đến từ một node chuẩn. Chúng ta gán cho k một giá trị sao cho xác suất ở trên là rất nhỏ và cũng thỏa mãn yêu cầu n - k > nf. Bây giờ chúng ta tìm giá trị của p và c để một node gây hại có thể có để tránh né khỏi cuộc kiểm tra. Để tránh bị phát hiện, node gây hại cần phải đưa ra được trả lời chính xác ít nhất là n-k lần, do đó: Sau khi giản ước các số hạng ta có: Cả pi và ci đều nhỏ hơn 1, nên ta có thể viết: Do đó chúng ta có: Chia cả 2 vế cho n ta có: Vế bên trái là giá trị trung bình của p trong n lần kiểm tra, kí hiệu là pavg. Ta cũng kí hiệu cavg là giá trị trung bình cả c trong n lần kiểm tra. Theo đó, nhờ việc duy trì xác suất trung bình là trong n lần kiểm tra đối với cả hai giá trị c và p, một node gây hại có thể tránh bị phát hiện trong bước 2 của quá trình kiểm tra. Giá trị của p và c nhỏ hơn giá trị trên, thì chúng sẽ bị phát hiện là node gây hại trong bước 2. Bây giờ cần tính giá trị lớn nhất của kích thước tập con trỏ ngược mà một node gây hại có thể có mà không bị phát hiện trong bước 2 của quá trình kiểm tra. Một node gây hại phản hồi lại với một tập ngẫu nhiên có kích thước X là tập con của tập con trỏ ngược có kích thước |M| của nó khi có yêu cầu kiểm tra từ một node trung gian chuẩn. Do đó, ta có: pavg = , kết hợp với: pavg= Ta có: ≥ Điều này có nghĩa là một node gây hại có thể duy trì một tập con trỏ ngược có kích thước: |M| Giá trị này lớn hơn X, và như vậy node gây hại sẽ không bị phát hiện trong bước 2 của quá trình kiểm tra. Tuy nhiên, chú ý rằng xác suất của thông điệp phản hồi mà tập con trỏ ngược không chứa node thực hiện kiểm tra trong mỗi lần kiểm tra là (1-f)(1-p)c. Nghĩa là, một thông điệp kiểm tra đến từ một node chuẩn và node gây hại lựa chọn phản hồi bằng một tập con trỏ ngược không chứa node kiểm tra. Với xác suất này lớn hơn không, một node gây hại cuối cùng cũng sẽ bị phát hiện trong bước 1 của quá trình kiểm tra. Chương 4. MÔ PHỎNG VÀ ĐÁNH GIÁ CƠ CHẾ KIỂM TRA ẨN DANH DỰA TRÊN PASTRY 4.1. Hình trạng mạng và các file thư viện liên kết động trong mô phỏng 4.1.1. Hình trạng mạng mô phỏng Để mô phỏng mạng Pastry, mô hình mạng được sử dụng là mô hình mạng giao vận nhánh (Transit-stub). Mô hình mạng giao vận phân nhánh tạo ra đồ thị phân cấp bằng cách sinh ra các kết nối giao vận và các miền nhánh (stub domain). Có thể miêu tả một cách đơn giản và dễ hiểu cách hình thành mạng giao vận nhánh như sau: đầu tiên dựng lên đồ thị kết nối ngẫu nhiên; Mỗi node trong đồ thị tượng trưng cho toàn bộ một miền giao vận (transit domain). Mỗi node trong đồ thị đó sau đó được thay thế bởi một đồ thị kết nối ngẫu nhiên khác, đại diện cho topo xương sống của một miền giao vận. Tiếp đó, từ mỗi node trong từng miền giao vận, chúng ta sinh ra một đồ thị kết nối ngẫu nhiên đại diện cho miền nhánh gắn vào node đó. Cuối cùng chúng ta thêm các cạnh liên kết giữa các node, một đầu cạnh từ miền giao vận và một từ miền nhánh hay từ các miền nhánh riêng biệt với nhau. Hiển nhiên, nếu đồ thị ngẫu nhiên được sinh ra là kết nối hoàn toàn (liên thông hoàn toàn), thì mô hình được xây dựng là đồ thị liên thông. Hình 6: Minh họa mạng giao vận nhánh – Transit stub Mô hình mạng dùng trong mô phỏng được tạo ra bởi chương trình sinh mô hình mạng GT-ITM . Các file dữ liệu cho mô hình mạng bao gồm: ts5050.sc ts5050-distances.out ts5050-routes.out Mô hình mạng mô phỏng này có 5050 bộ định tuyến và có thể mô phỏng cho 505.000 node. 4.1.2. Các file thư viện liên kết động trong chương trình Để có thể thực hiện mô phỏng mạng Pastry, cần sử dụng bộ thư viện các lớp và hàm cho mạng ngang hàng có cấu trúc Pastry do hãng Microsoft xây dựng và phát triển.Bộ thư viện này gồm ba file đó là: Simulator.dll MessageRouting.dll Pastry.dll File thư viện MessageRouting.dll cung cấp các lớp và lớp trừu tượng dùng để xử lý các thông điệp trong mạng Pastry, lớp trừu tượng quan trọng nhất mà file này cung cấp được sử dụng trong mô phỏng là public abstract class Application. Lớp này có hai phương thức đáng quan tâm là: public abstract bool ContinueRouting(MessageRouting.RouteMsg msg) Phương thức này được thực thi trong quá trình chuyển tiếp thông điệp trong mạng. protected abstract void ProcessMessage(MessageRouting.RouteMsg msg) Khi thông điệp được chuyển tới đích, phương thức này được gọi và thực thi. File thư viện động Simulator.dll cung cấp các lớp để tải mô hình mạng mô phỏng với lớp chính được sử dụng là public class Sim.Trong chương trình mô phỏng, ta cần khởi tạo một đối tượng lớp Sim với các tham số truyền vào là ba file mạng mô phỏng sinh bởi chương trình GT-ITM được nêu ở trên. File Pastry.dll cung cấp các lớp mô tả các đối tượng có trong mạng Pastry bao gồm: public class LeafSet public class RouteTable public class NeighbourhoodSet public class Node : MessageRouting.Node public class NodeIdAddressBind : MessageRouting.NodeIdAddressBind public class NodeId : MessageRouting.NodeId 4.2. Xây dựng chương trình mô phỏng kiểm tra ẩn danh 4.2.1. Mô tả chương trình Chương trình được viết bằng ngôn ngữ C#, với các file thư viện được xây dựng và phát triển bởi hãng Microsoft. Cơ chế kiểm tra ẩn được thực hiện dựa trên chương trình mô phỏng mạng Pastry, mạng Pastry ở đây có không gian định danh với l = 128 bit, tức có thể đánh định danh cho 2128 node hoặc khóa. Số của định danh là số trong hệ cơ số 16. Cơ chế kiểm tra ẩn danh dựa vào việc giới hạn bậc để phát hiện ra các node gây hại trong hệ thống. Do đó, ta cần ấn định một số node trong mạng làm node gây hại và chọn ra một giới hạn bậc trong phù hợp. Gọi tỉ lệ node gây hại có trong mạng là f, ta sẽ chọn các node làm node gây hại là các node có số bậc trong cao nhất, tức là những node có kích thước tập con trỏ ngược lớn nhất. Gọi số node có trong mạng là N, ta chọn xấp xỉ f*N node làm node gây hại và một giới hạn bậc b sao cho tất cả các node gây hại được chọn có bậc trong cao hợn giới hạn bậc b và tất cả các node chuẩn có bậc trong nhỏ hơn hoặc bằng giới hạn bậc cho phép đó. Trong tấn công che khuất, các node gây hại thông đồng với nhau để thực hiện che khuất các node khác trong mạng, do đó một node gây hại biết các node gây hại khác là các node nào. Truy vấn kiểm tra ẩn danh đòi hỏi node bị kiểm tra trả về tập con trỏ ngược của nó. Tập con trỏ ngược này phải chứa node tiến hành kiểm tra và kích thước tập con trỏ ngược phải nhỏ hơn bằng giới bậc cho phép thì mới được coi là kiểm tra thành công. Do node gây hại cần có nhiều node chuẩn chứa nó trong tập hàng xóm để có thể thực hiện âm mưu che khuất, nên các node gây hại có kích thước tập con trỏ ngược rất lớn. Mỗi khi có truy vấn kiểm tra ẩn danh tới, nó sẽ phải quyết định có trả lời hay không. Nếu không trả lời thì sẽ bị tình nghi là node gây hại, nếu trả lời nó phải chọn một tập con ngẫu nhiên từ tập con trỏ ngược của nó để phản hồi về cho node kiểm tra. Tập con trỏ ngược trả lời cho cuộc kiểm tra có thể có hoặc không chứa node tiến hành kiểm tra, và xác suất có node kiểm tra bằng giới hạn bậc của mạng chia cho kích thước tập con trỏ ngược của nó. Chương trình kiểm tra ẩn danh sẽ cho tất cả các node chuẩn thực hiện kiểm tra ẩn danh đối với các node có trong tập hàng xóm của nó. Số lần kiểm tra ẩn danh đối với mỗi node hàng xóm sẽ được thay đổi với các giá trị khác nhau. Đây là cơ chế kiểm tra ẩn danh nên trong quá trình kiểm tra cần một node trung gian để chuyển tiếp thông điệp truy vấn kiểm tra từ node kiểm tra tới node bị kiểm tra nhằm che dấu danh tính node tiến hành và node bị kiểm tra. Node trung gian trong mỗi truy vấn kiểm tra sẽ được chọn ngẫu nhiên từ các node có trong hệ thống và khác với node kiểm tra và bị kiểm tra. Do node trung gian chọn ngẫu nhiên, nên nó có thể là một node gây hại, nếu node trung gian được chọn là node gây hại nó sẽ thực hiện hành động phá hoại cuộc kiểm tra. Nếu node bị kiểm tra là node chuẩn, nó sẽ loại bỏ yêu cầu kiểm tra và trả lời cho node kiểm tra rằng kiểm tra thất bại. Như vậy node kiểm tra sẽ tình nghi node hàng xóm chuẩn của nó là node gây hại. Nếu node bị kiểm tra là node gây hại, nó sẽ thông đồng với node gây hại đó và gửi cho node kiểm tra một tập con trỏ ngược có chứa node kiểm tra, và node kiểm tra coi đó là một truy vấn kiểm tra ẩn danh thành công. Thông điệp cài đặt dùng trong kiểm tra ẩn danh được chia làm bốn loại thông điệp: CHALLENGE_REQ_1: Thông điệp truy vấn gửi từ node kiểm tra tới node trung gian. CHALLENGE_REQ_2: Thông điệp truy vấn gửi từ node trung gian tới node bị kiểm tra. X Y Z CHALLENGE_REQ_1 CHALLENGE_REQ_2 CHALLENGE_RES_2 CHALLENGE_RES_1 Hình 7:Các loại thông điệp trong kiểm tra ẩn danh CHALLENGE_RES_1: Thông điệp phản hồi từ node bị kiểm tra gửi cho node trung gian. CHALLENGE_RES_2: Thông điệp phản hồi từ node trung gian gửi cho node tiến hành kiểm tra. Dựa vào loại thông điệp ta có thể xác định các hành động tiếp theo của mỗi node nhận được thông điệp của quá trình kiểm tra ẩn danh. 4.2.2. Các file chương trình File Test.cs File Test là file chính của chương trình mô phỏng, có chứa hàm main của chương trình. Các thuộc tính quan trọng trong lớp này bao gồm: Mảng lưu trữ tập hàng xóm của tất cả các ndoe trong mạng: public static ArrayList[] NeighborSet Mảng lưu trữ con trỏ ngược của tất cả các node trong mạng: public static ArrayList[] BackPointerSet Mảng chứa tất cả các node trong mạng: public static ArrayList All_Node Mảng chứa các node gây hại trong mạng public static ArrayList MaliciousNodes Tỉ lệ node gây hại trong mạng: static double F Giới hạn bậc trong của các node: public static int bound Một số phương thức chính của lớp Test: Phương thứ public void createMaliciousNodeSet(double fMaliciousNode):Phương thức này sẽ khởi tạo các node gây hại và lưu vào trong mảng MaliciousNodes, số lượng các node gây hại sẽ chiếm tỉ lệ fMaliciousNode trong tổng số các node trong mạng, đồng thời phương thức này cũng sẽ xác định giới hạn bậc trong bound của mạng. Giá trị bound được xác định sao cho tất cả các node gây hại có bậc trong cao hơn giá trị này, và các node chuẩn có bậc trong nhỏ hơn hoặc bằng giá trị bound. Phương thức public static Node CreateNodes(int numNodes):Dùng khởi tạo một lượng node bằng numNodes cho mạng. Phương thức public static void SendMessages(int nodes, int time): Phương thức này được gọi để gửi các thông điệp kiểm tra trong mạng. Hai tham số truyền vào là số node mạng và lượng thời thời gian để gửi các thông điệp truy vấn. Các node chuẩn được dùng để gửi các thông điệp truy vấn kiểm tra ẩn danh, đích của thông điệp chính là các node trong tập hàng xóm của nó. Phương thức khởi tạo: public Test(): Trong phương thức này sẽ khởi tạp mạng mô phỏng Sim s = Sim(string netFile, string routesFile, string distancesFile, Simulator.CheckIgnore ignore), trong đó các file netFile, routesFile, distancesFile là các file mô hình mạng được sinh ra bởi GT-ITM. Ngoài các phương thức trên còn có các phương thức để liệ kê kết quả kiểm tra showResult(), phương thức khởi tạo tập hàng xóm getNeighbor(Pastry.NodeIdAddressBind NodeBind) và tập con trỏ ngược createBackPointerSet() của các node trong mạng. File AuditingApplication.cs File này mô tả lớp AuditingApplication được kế thừa từ lớp trừu tượng MessageRouting.Application có trong file thư viện MessageRouting.dll. Lớp AuditingApplication có thuộc tính quan trọng là : private Node myServer: Chứa node đích của thông điệp được gửi đi. Trong lớp này có các phương thức xử lý các thông điệp kiểm tra, mọi quá trình xử lý các thông điệp kiểm tra được gửi đi đều được xử lý trong phương thức: protected override void ProcessMessage(MessageRouting.RouteMsg mrMsg) Phương thức này sẽ nhận dạng loại thông điệp kiểm tra dựa vào thuộc tính MessageType của thông điệp. Có bốn loại thông điệp, hai thông điệp truy vấn và hai thông điệp phản hồi đã được nói đến trong phần 4.1.2. Nếu node trung gian trong kiểm tra là node gây hại nó sẽ báo cho node tiến hành kiểm tra rằng không có phản hồi khi node bị kiểm tra là node chuẩn. Và nó trả về một thông điệp cho node kiểm tra giúp node bị kiểm vượt qua lần kiểm tra đó. Nếu node trung gian là node chuẩn, nó sẽ chuyển tiếp thông điệp kiểm tra đới đích. Nếu node đích là node chuẩn, nó sẽ phản gửi phản hồi lại cho node trung gian, và tất nhiên nó qua được lần kiểm tra này. Nếu node gây hại là node đích của cuộc kiểm tra, nó sẽ chọn trả lời hoặc không trả lời. Nếu trả lời, nó sẽ sinh một tập con từ tập con trỏ ngược của nó với các node trong tập con được lấy ngẫu nhiên, kích thước tập con này có thể bằng giới hạn bậc trong. File Message.cs Trong file này mô tả lớp Message, lớp này được kế thừa từ từ lớp RouteMsg được cung cấp trong file thư viện Pastry.dll. Lớp này mô tả các thông điệp được gửi đi, các thuộc tính của lớp này là: Danh sách tập con trỏ ngược trả về: public ArrayList list Tập con trỏ ngược của node bị kiểm tra trả về sẽ được lưu trong mảng này. Thuộc tính lưu thông tin node kiểm tra và node đích: public Pastry.NodeIdAddressBind aud_sour public Pastry.NodeIdAddressBind aud_dest Thuộc tính để xác định có phản hồi từ node bị kiểm tra hay không public bool has_res Khi có phản hồi từ node bị kiểm tra, giá trị của thuộc tính này được thiết lập bằng true, hoặc khi node trung gian là node gây hại thực hiện phá hoại loại cuộc kiểm tra thì nó sẽ sinh thông điệp phản hồi cho node đích với giá trị thuộc tính này thiết lập bằng false. Ngoài ra còn có bốn giá trị để thiết lập cho bốn loại thông điệp trong kiểm tra được thiết lập giá trị không đổi cho lớp này là: public const int CHALLENGE_REQ_1 = 2111; public const int CHALLENGE_REQ_2 = 2222; public const int CHALLENGE_RES_1 = 3111; public const int CHALLENGE_RES_2 = 3222; 4.3. Thí nghiệm và nhận xét Tôi sẽ tiến hành hai thí nghiệm để đánh giá hiệu quả của phương pháp kiểm tra ẩn danh. Trong hai thí nghiệm, số node trong mạng đều không đổi và bằng 5000. Tỉ lệ node gây hại là 0.2, tức trong mạng sẽ có khoảng 1000 node là node gây hại và 4000 node là node chuẩn. Mỗi thí nghiệm sẽ chạy chương trình mô phỏng năm lần, mỗi lần chạy có số lần lặp kiểm tra trên mỗi node là khác nhau. Gọi số lần kiểm tra trên mỗi node là n, giá trị tương ứng của n trong mỗi lần chạy chương trình là 8, 12, 16, 20 và 24. Gọi k là số cuộc kiểm tra mà một node bị kiểm tra phải vượt qua để được coi là node chuẩn, ngược lại nếu không qua sẽ bị coi là node gây hại. Ta sẽ thay k lần lượt bằng n/4, n/2 và 3n/4, và từ đó tính tỉ lệ node gây hại bị phát hiện được tương ứng với mỗi giá trị k. 4.3.1. Thí nghiệm 1 Trong thí nghiệm 1 này, ta giả định kích thước tập con trỏ ngược của node gây hại trong mạng lớn hơn 1.2 lần kích thước tập con trỏ ngược của các node chuẩn, tức xác suất để node gây hại chọn được tập con trỏ ngược để phản hồi kiểm tra có chứa node kiểm tra là xấp xỉ 1/1.2 hay 83%, điều này có nghĩa rằng khả năng node phá hoại vượt qua cuộc kiểm tra là rất cao. Kết quả Biểu đồ 1: Tỉ lệ node gây hại bị phát hiện trong thí nghiệm 1 Trong biểu đồ trên, trục tung là tỉ lệ node gây hại bị phát hiện, trục hoành là số kiểm tra đối với mỗi node. Ta có thể thấy rằng, tăng số lượng kiểm tra sẽ tăng tỉ lệ node gây hại bị phát hiện trong mạng, nhưng với k = n/4 thì ngược lại, tỉ lệ node gây hại bị phát hiện có xu hướng giảm và ở giá trị k này, tỉ lệ node gây hại bị phát hiện là thấp nhất, gần như bằng 0. Ta tăng giá trị của k lên n/2 và 3n/4 thì tỉ lệ node gây hại bị phát hiện tăng rõ rệt, đặc biệt với k = 3n/4 tỉ lệ phát hiện đều trên 0.8 và gần tới 1. Biểu đồ 2: Tỉ lệ node chuẩn không vượt qua được kiểm tra trong thí nghiệm 1 Trong biểu đồ này, trục tung là tỉ lệ node chuẩn bị kết luận nhầm là node gây hại, trục hoành là số lần kiểm tra với mỗi node. 4.3.2. Thí nghiệm 2 Trong thí nghiệm này, ta thiết lập tỉ lệ node gây hại trong mạng là 0.2, các node gây hại được chọn là các node có kích thước tập con trỏ ngược lớn nhất bởi tập con trỏ ngược lớn chính là đặc điểm nổi bật của một node gây hại. Chương trình tiến hành chọn tự động và chọn ra được 985 node đóng vai trò node gây hại. Các node gây hại này có tổng kích thước tập con trỏ ngược là 107258, chiếm tới 42% tổng kích thước tập con trỏ ngược của tất cả các node trong mạng. Giới hạn bậc được chương trình chọn ở đây bằng 62. Tức tất cả các node gây hại có bậc trong lớn hơn 62 và các node chuẩn có bậc trong nhỏ hơn hoặc bằng 62. Kích thước trung bình tập con trỏ ngược của node gây hại là 108. Xác suất trung bình để tập con trỏ ngược do node gây hại trả về có chứa node kiểm tra là xấp xỉ 57%. Kết quả Biểu đồ 3:Tỉ lệ node gây hại bị phát hiện trong thí nghiệm 2 Biểu đồ 4: Tỉ lệ node chuẩn bị kết luận nhầm là node gây hại trong thí nghiệm 2 Trong cả hai biể đồ trên, trục tung là tỉ lệ phát hiện và trục hoành là số lần kiểm tra với mỗi node. 4.3.3. Nhận xét Trong hai thí nghiệm trên, tỉ lệ node gây hại bị phát hiện là rất cao với k = 3n/4. Đạt từ 0.8 đến gần bằng 1, đặc biệt với 24 cuộc kiểm tra và k = 3n/4 số node gây hại bị phát hiện trong cả hai lần thí nghiệm đều cao hơn 0.97. Chứng tỏ phương pháp kiểm tra ẩn danh rất hiệu quả trong phát hiện các node gây hại. Trong hai biểu đồ 1 và 3, chỉ có riêng đường tỉ lệ node gây hại bị phát hiện với k = n/4 có xu hướng đi xuống khi ta tăng số lần kiểm tra, trái với hai đường n/2 và 3n/4 có xu hướng đi lên khi tăng số lần kiểm tra. Sự đi xuống của tỉ lệ phát hiện với k = n/4 hoàn toàn hợp lý và tuân theo “Quy tắc phân phối xác suất nhị thức”[8]. Trong ba giá trị của k được thiết lập để đánh giá, ta thấy với k = 3n/4 đạt hiệu quả cao nhất trong phát hiện node gây hại, tuy nhiên nó lại có tỉ lệ kết luận node chuẩn là node gây hại cao nhất, và tỉ lệ này nằm trong khoảng 0.1 đến 0.2. Tỉ lệ kết luận nhầm đối với k = n/4 và n/2 là rất thấp, và gần như bằng 0. Trong thí nghiệm 1 có tỉ lệ node gây hại bị phát hiện thấp hơn so với tỉ lệ node gây hại bị phát hiện trong thí nghiệm 2, điều này có thể giải thích là do xác suất node gây hại chọn được một tập con trỏ ngược phù hợp có chứa node kiểm tra trong thí nghiệm 1 là 83%, cao hơn trong thí nghiệm 2 là 57%, do đó số node gây hại có khả năng qua được cuộc kiểm tra cao hơn. Điều này đúng với công thức tỉ lệ node gây hại qua được cuộc kiểm tra: f+(1-f )pc được nói đến trong phần 3.3. Trong đó f là tỉ lệ node gây hại trong mạng, p là xác suất node gây hại phản hồi kiểm tra và c là xác suất node gây hại chọn được tập con trỏ phù hợp để phản hồi. Để lý giải cho việc đi xuống của hai đường k = n/4 trong đồ thị 1, ta sẽ áp dụng quy tắc tính phân phối xác suất nhị thức để chứng minh cho sự đi xuống của đường này là đúng. Trong thí nghiệm 1, xác suất node gây hại qua được một cuộc kiểm tra là : S = f+(1-f )pc = 0.2 + (1-0.2)* 0.5 * 0.83 = 0.532 Với giả thiết rằng, node gây hại chọn trả lời thông điệp kiểm tra với xác suất p=0.5. Theo quy tắc tính phân phối xác suất nhị thức, tỉ lệ node gây hại không qua được ít nhất 2 trong 8 cuộc kiểm tra là: P1 = S0(1-S) 8 + S1(1-S) 7 = 0.0232 Tỉ lệ node không qua được ít nhất là 3 trong 12 cuộc kiểm tra là: P2= S0(1-S) 12 + S1(1-S) 11+S2(1-S) 10 = 0.0110 Tỉ lệ node không qua được ít nhất là 4 trong 16 cuộc kiểm tra là: P3 = S0(1-S) 16 + S1(1-S) 15+S2(1-S) 14 + S3(1-S) 13 = 0.0052 Tỉ lệ node không qua được ít nhất 5 trong 20 cuộc kiểm tra và 6 trong 24 cuộc kiểm tra là: P4= 0.0025, P5 = 0.0012 . Ta thấy rằng P1> P2> P3 >P4 >P5 mặc dù số lần kiểm tra tăng. Tuy nhiên chỉ có đường k=n/4 đi xuống, 2 đường còn lại đều đi lên. Thật vậy, áp dụng cách chứng minh trên ta có xác suất để node gây hại không qua được ít nhất là 4 trong 8 cuộc kiểm tra là: P’1 = = 0.2957. Tương tự ta có xác suất để node gây hại không qua được ít nhất 6, 8, 10, 12 trong 12, 16, 20 và 24 cuộc kiểm tra là: P’2= 0.3039, P’3= 0.3052, P’4= 0.3040, P’5=0.3013. Các giá trị của P’1, P’2, P’3, P’4, P’5 đều phù hợp với đường k = n/2 trong đồ thị 1. Sự biến đổi của các đường trong các đồ thị khác đều có thể chứng minh được là đúng đắn bằng phương pháp chứng minh trên. Nhận xét rằng, để kiểm tra ẩn danh đạt hiệu quả cao nhất ta nên chọn số lần kiểm tra là 24 với số kiểm tra thành công để được coi là node chuẩn là 18, như vậy tỉ lệ node gây hại bị phát hiện lên tới trên 0.9, và số node chuẩn bị kết luận nhầm là node gây hại có tỉ lệ nhỏ hơn 0.2. Điều này hoàn toàn chấp nhận được vì gần như là tất cả các node gây hại đều bị loại bỏ và ta chỉ phải bổ xung lại một lượng nhỏ các node chuẩn bị loại bỏ nhầm. Chương 5. KẾT LUẬN Phương pháp kiểm tra ẩn danh để phát hiện các node gây hại cần dựa vào cơ chế giới hạn bậc trong và bậc ngoài của các node trong mạng xếp chồng. Mỗi node ngoài việc phải duy trì tập hàng xóm cần phải duy trì tập con trỏ ngược, điều này đòi hỏi tăng chi phí để duy trì tập con trỏ ngược. Để có thể đưa ra giới hạn bậc, cần có một sự quản lý tập chung cho tất cả các node trong mạng, điều này làm cho mạng không còn là là mạng ngang hàng đúng nghĩa mà trở thành mạng lai giữa P2P và mạng máy khách-máy chủ. Phương pháp kiểm tra ẩn danh tỏ ra hữu hiệu trong phát hiện các node gây hại khi các node này có tập con trỏ ngược lớn hơn giới hạn cho phép. Tuy nhiên, nếu các node gây hại có tập con trỏ ngược không quá giới hạn bậc thì sẽ không thể phát hiện được chúng. Tuy nhiên, nếu node gây hại có tập con trỏ ngược phù hợp với giới hạn bậc thì nó cũng có hiệu quả trong tấn công thấp, nhưng một phần nào đó vẫn có thể gây hại cho mạng. Tài liệu tham khảo Tài liệu tiếng Anh [1] Atul Singh, Tsuen-Wan .Johnny. Ngan, Peter Druschel., and Dan S. Wallach, Eclipse Attacks on Overlay Networks: Threats and Defenses, 2002 [2] J. R. Douceur. The Sybil Attack. In Proceedings of 1st International Workshop on Peer-to-Peer Systems (IPTPS), Cambridge, MA, Mar. 2002. [3] K. Hildrum and J. Kubiatowicz. Asymptotically ef_cient approaches to fault-tolerance in peer-to-peer networks. In Proceedings of 17th International Symposium on Distributed Computing, Sorrento, Italy, Oct. 2003. [4] Miguel Castro, Microsoft Research; Peter Druschel, Rice University; Ayalvadi Ganesh and Antony Rowstron, Microsoft Research; Dan S. Wallach, Rice University, Secure Routing for Structured Peer-to-Peer Overlay Networks [5] M. Castro, P. Druschel, A. Ganesh, A. Rowstron, and D. S. Wallach. Secure routing for structured peer-to-peer overlay networks. In Proceedings of USENIX Operating System Design and Implementation(OSDI), Boston, MA, Dec. 2002. [6] M. Castro, P. Druschel, Y. C. Hu, and A. Rowstron. Proximity neighbor selection in tree-based structured peer-to-peer overlays. Technical Report MSR-TR-2003-52, Microsoft Research, June 2003. [7] M. Castro and B. Liskov, "Practical Byzantine fault-tolerance and proactive recovery", ACM Transactions on Computer Systems (TOCS), Volume 20, Issue 4, November 2002. [8] R. Steinmetz and K. Wehrle (Eds.): P2P Systems and Applications, LNCS 3485, pp. 1-5, 2005. Tài liệu tiếng Việt [8] Cao Hào Thi, Xác suất thống kê, phần 5.2.2. Phân phối xác suất (Probability Distribution), trang 48, năm 2008. [9]