Luận văn Tóm tắt Máy véctơ hỗ trợ đa lớp và ứng dụng phát hiện tấn công mạng

HỌC VIỆN CÔNG NGHỆ BƯU CHÍNH VIỄN THÔNG --------------------------------------- NGUYỄN ĐỨC HIỂN MÁY VÉCTƠ HỖ TRỢ ĐA LỚP VÀ ỨNG DỤNG PHÁT HIỆN TẤN CÔNG MẠNG Chuyên ngành: KHOA HỌC MÁY TÍNH Mã số: 60.48.01 TÓM TẮT LUẬN VĂN THẠC SỸ KĨ THUẬT HÀ NỘI – NĂM 2012 Luận văn được hoàn thành tại: HỌC VIỆN CÔNG NGHỆ BƯU CHÍNH VIỄN THÔNG Người hướng dẫn khoa học: PGS.TS. NGÔ QUỐC TẠO Phản biện 1: TS. Trần Nguyên Ngọc. Phản biện 2: PGS. TS. Đỗ Năng Toàn. Luận văn sẽ được bảo vệ trước Hội đồng chấm luận văn thạc sĩ tại Học viện Công nghệ Bưu chính Viễn thông Vào lúc: ....giờ.....ngày 20 tháng 01 năm 2013 Có thể tìm hiểu luận văn tại: - Thư viện của Học viện Công nghệ Bưu chính Viễn thông 1 I. MỞ ĐẦU - Lý do chọn đề tài: Mặc dù ra đời chưa lâu nhưng mạng Internet đã phát triển mạnh mẽ và có ảnh hưởng sâu rộng trong tất cả các lĩnh vực của đời sống con người. Bên cạnh những lợi ích to lớn thì nó cũng mang lại là những phiền phức và nguy cơ không nhỏ cho các tổ chức và người dùng kết nối vào Internet, trong đó có các nguy cơ đến từ tấn công mạng. Số lượng các cuộc tấn công mạng trên toàn thế giới không ngừng tăng về số lượng cũng như mức độ nguy hiểm của chúng. Các cuộc tấn công mạng có thể gây ra những hậu quả nghiêm trọng về kinh tế, chính trị thậm chí ảnh hưởng tới an ninh của một quốc gia. Việc phát hiện và xử lý thủ phạm gây ra các cuộc tấn công là cực kì khó khăn. Giải pháp kỹ thuật phổ biến cho vấn đề này là phát hiện sớm các cuộc tấn công mạng để từ đó có giải pháp thích hợp xử lý chúng. - Những vấn đề còn tồn tại: Rất nhiều kỹ thuật đã được áp dụng để phát hiện một kết nối mạng là tấn công mạng hay không với hiệu quả khá cao, chẳng hạn như SVM, iSVM, Neural network… Nhưng thực tế luôn đòi hỏi độ chính xác phải cao hơn nữa. - Mục đích nghiên cứu: Mục đích của đề tài là nghiên cứu kỹ thuật M- SVM ứng dụng vào việc phát hiện và phân loại tấn công trong không gian mạng để nâng cao hơn nữa độ chính xác của hệ thống phát hiện tấn công mạng. - Đối tượng và phạm vi nghiên cứu: Kỹ thuật M-SVM và ứng dụng M- SVM vào việc phân loại các kết nối mạng trên bộ dữ liệu KDD cup 99. Trong chương trình đánh giá phát hiện tấn công mạng của Cơ quan Quản lý Nghiên cứu Dự Án Bộ quốc phòng Mỹ (DARPA), một môi trường đã được thiết lập để thu được các dữ liệu thô về TCP/IP dump cho một mạng được mô phỏng giống như mạng LAN của Không lực Hoa Kỳ. Với mỗi kết nối TCP/IP, 41 đặc trưng số và phi số được trích xuất. Dữ liệu được sử dụng trong cuộc thi kdd cup 1999 là một phiên bản của bộ dữ liệu này. Các cuộc tấn công thuộc về bốn loại chính: DOS, R2L, U2R, Probing. Dữ liệu kdd cup 1999 có thể tải từ địa chỉ: 2 - Phương pháp nghiên cứu: Nghiên cứu và cài đặt kỹ thuật Máy véc tơ hỗ trợ đa lớp. Thu thập và tiền xử lý các bộ dữ liệu mẫu hiện có về tấn công mạng. Áp dụng SVMs trên dữ liệu đã xử lý, so sánh, đánh giá hiệu quả của kỹ thuật SVMs trong việc phát hiện tấn công mạng. II. NỘI DUNG Chương 1 - TỔNG QUAN VỀ PHÁT HIỆN TẤN CÔNG MẠNG 1.1. Tấn công mạng 1.1.1. Khái niệm tấn công mạng Có rất nhiều cách hiểu khác nhau về tấn công mạng, theo Sandeep Gutta thì tấn công mạng (cyber attack hay intrusion) có thể được định nghĩa là một loạt các hoạt động máy tính nguy hiểm đe dọa và làm tổn hại tới sự bảo mật và tính toàn vẹc của một máy thính hay hệ thống mạng. Tấn công mạng phá vỡ hoạt động bình thường của hệ thống máy tính và có thể truy nhập trái phép hoặc phá hủy thông trin trong các hệ thống máy tính [11]. Theo một cách khác tấn công mạng có thể được định nghĩa là bất kì hành động nào cố gắng làm tổn hại sự toàn vẹn, bí mật, tính sẵn sàng của một tài nguyên hoặc đi ngược lại mục tiêu bảo mật của một tài nguyên nào đó. 1.1.2. Các kiểu tấn công mạng Có rất nhiều kiểu tấn công mạng nhưng ta có thể phân chúng vào bốn loại chính như sau : DoS - Denial of Service attack : Tấn công kiểu DoS là những tấn công làm cho tài nguyên máy tính (ví dụ Web server) không khả dụng với người dùng thực sự [11]. Dạng phổ biến nhất của tấn DoS là làm cho tài nguyên máy tính quá bận vì bị sử dụng toàn bộ với rất nhiều yêu cầu vô ích đến mức người dùng thực sự không thể sử dụng nó. Có rất nhiều biến thể của tấn công DoS bao gồm TCP-SYN Flood, ICMP/UDP Flood, Smurf, Ping of Death, Teardrop, Mailbomb, Apache2. R2L - Remote to Local attack :Trong loại tấn công này, tin tặc cố gắng đạt được quyền truy cập khu vực vào hệ thống máy tính bằng việc gửi các gói tin tới hệ thống thông qua mạng. Một vài cách phổ biến mà loại này thực hiện là đoán mật khẩu thông qua phương pháp từ điển brute-force, FTP Write,… 3 U2R - User to Root attack : Trong lớp tấn công này, tin tặc với quyền của một người dùng bình thường cố gắng để đạt được quyền truy nhập cao nhất (đặc quyền của người quản trị hệ thống) vào hệ thống một cách bất hợp pháp.Một cách phổ biến của lớp tấn công này là thực hiện bằng phương pháp gây tràn bộ đệm. Probe – Surveillance : Trong loại tấn công này, tin tặc quét mạng hoặc máy tính để tìm ra điểm yếu dễ tấn công mà thông qua đó tin tặc có thể khai thác hệ thống. Điều này có phần giống như theo dõi, giám sát hệ thống. Một cách phổ biến của loại tấn công này là thực hiện thông qua việc quét các cổng của hệ thống máy tính. Bằng việc này, tin tặc có thể lấy được thông tin về cổng đang mở, dịch vụ đang chạy, và rất nhiều thông tin chi tiết nhạy cảm khác như địa chỉ IP, địa chỉ MAC, các luật tường lửa đang sử dụng, … 1.2. Bài toán phát hiện xâm nhập mạng Khi một máy tính hay một hệ thống hoạt động trên môi trường mạng, sẽ có rất nhiều kết nối giữa nó và các máy tính, các thiết bị khác. Trong những kết nối đó có những kết nối đang tìm cách tấn công hệ thống để đạt được mục đích nào đó. Bản thân mỗi máy tính đều có những cơ chế để tự bảo vệ nhưng nó có những điểm yếu và thực sự không đủ sức chống lại các cuộc tấn công mới với mức độ nguy hiểm ngày càng lớn hơn. Bên cạnh đó các máy tính hay hệ thống cũng phải chịu các nguy cơ đến từ các hành vi vi phạm chính sách an toàn và bảo mật công nghệ thông tin một cách vô tình hay hữu ý. Bài toán được đặt ra là cần có cơ chế để phát hiện sớm các cuộc tấn công để từ đó có những biện pháp ngăn chặn hoặc giảm thiểu tối đa những thiệt hại, tác động do các cuộc tấn công gây ra. 1.2.1. Phát hiện xâm nhập mạng Phát hiện xâm nhập mạng là quá trình theo dõi các sự kiện xảy ra trong một hệ thống máy tính hoặc mạng máy tính và phân tích chúng để tìm ra các dấu hiệu sự cố có thể xảy ra, đó là các vi phạm hoặc các mối đe dọa sắp xảy ra vi phạm các chính sách bảo mật máy tính, các chính sách sử dụng được chấp nhận hoặc thực hành bảo mật tiêu chuẩn. 4 1.2.2. Phân loại hệ thống phát hiện xâm nhập mạng Các IDS có thể giám sát các sự kiện ở 3 cấp độ khác nhau : mạng (network), máy trạm (host), ứng dụng (application). Chúng có thể phân tích các sự kiện bằng việc sử dụng một trong các phương pháp : dựa trên dấu hiệu (signature-based), dựa trên dị thường (anomaly-based) và phân tích trạng thái giao thức (statefull protocol analysic). Bên cạnh việc theo dõi và phân tích các sự kiện để nhận dạng các hoạt động không mong muốn, các loại cộng nghệ IDS thường thực hiện các chức năng sau : - Ghi lại thông tin liên quan tới các sự kiện được quan sát. - Thông báo cho quản trị hệ thống về các sự kiện quan trọng quan sát được. - Đưa ra các báo cáo về các sự kiện đã quan sát hoặc cung cấp chi tiết về các sự kiện đặc biệt cần được quan tâm. Có hai cách để phân loại IDS đó là dựa trên phương pháp giám sát và dựa trên phương pháp phân tích của IDS. Dựa trên phương pháp giám sát Hệ thống phát hiện xâm nhập dựa trên mạng (Network-based Intrution Detection System - NIDS) : Đây là loại phổ biến nhất của sản phẩm thương mại. Cơ chế phát hiện tấn công của nó là giám sát và theo dõi các gói tin mạng. Điểm mạnh của IDS kiểu này là chỉ với một số ít các IDS được đặt ở vị trí tốt có thể giám sát được một mạng lớn. Việc triển khai IDS dựa trên mạng ít tác động tới hiệu suất của mạng hiện có. Chúng có thể tạo ra tính an toàn cao chống lại các cuộc tấn công. Điểm yếu của IDS dựa trên mạng là nó khó xử lý toàn bộ các gói tin trong một mạng lớn hoặc bận. Hệ thống phát hiện xâm nhập dựa trên máy trạm (Host-based Intrution Detection System – HIDS) phân tích hoạt động trên một máy tính riêng biệt. Vì vậy chúng phải thu thập thông tin từ máy trạm mà chúng đang giám sát. Điều này cho phép một IDS phân tích các hoạt động trên trạm rất tốt và quyết định chính xác tiến trình và user nào đang thực hiện các hoạt động nguy hại trên hệ điều hành. 5 Trong các tổ chức đã triển khai NIDS thì việc triển khai HIDS có thể là một đề xuất để tăng thêm mức bảo vệ.. Dựa trên phương pháp phân tích Hệ thống phát hiện xâm nhập dựa trên dấu hiệu (Signature-based IDS). Dấu hiệu (signature) có thể là các thông tin về các kết nối nguy hiểm đã biết trước. Phát hiện dựa trên dấu hiệu (signature-based detection) là quá trình so sánh signature với sự kiện quan sát được để nhận dạng sự cố có thể xảy ra. Phát hiện dựa trên dấu hiệu là phương pháp phát hiện đơn giản nhất bởi vì nó chỉ so sánh hoạt động hiện thời, với danh sách các dấu hiệu bằng hoạt động so sách chuỗi. Ưu thế của phương pháp này là rất hiệu quả trong việc phát hiện sự tấn công mà không tạo ra số lượng lớn các cảnh báo sai. Nhược điểm của nó là chỉ phát hiện được các cuộc tấn công mà nó đã biết trong quá khứ hay nói khác đi là đã có trong cơ sở dữ liệu signature, do vậy hệ thống phải liên tục cập nhật các dấu hiệu của các cuộc tấn công mới. Hệ thống phát hiện xâm nhập dựa trên dị thường (Anomaly-based IDS) : Phát hiện dựa trên dấu hiệu dị thường là quá trình so sánh các định nghĩa của những gì được coi hoạt động bình thường so với các sự kiện quan sát để xác định độ lệch đáng kể (significal deviation). IDS sử dụng phát hiện dựa trên dị thường có những cấu hình (profile) đại diện cho hành vi bình thường của người sử dụng, máy chủ, kết nối mạng hay các ứng dụng... Các cấu hình được phát triển bằng việc quan sát các đặc trưng của các hoạt động thông thường trong một khoảng thời gian. Lợi ích chủ yếu của phương thức phát hiện dựa trên dị thường là nó rất hiệu quả trong việc phát hiện các mối nguy hiểm không được biết trước đó. 1.3. Một số kỹ thuật phát hiện tấn công mạng 1.3.2. Kỹ thuật Haystack Haystack sử dụng thuật toán phát hiện dị thường theo thống kê, nó được thông qua như như thành phần cốt lõi của việc giám sát máy trạm trong hệ thống phát hiện xâm nhập phân tán (DIDS) ( Axelsson, 1999). Thuật toán này phân tích hoạt động của người dùng tương ứng với một quá trình gồm 4 bước : 6 Bước thứ nhất, thuật toán tạo ra véctơ phiêm giao dịch (session) đại diện cho các hoạt động của người dụng với phiên làm việc riêng biệt. Véctơ session X = biểu diễn số lượng của các thuộc tính đa dạng được sử dụng để đại diện cho hoạt động của người dùng trong phiên làm việc đơn. Ví dụ, các thuộc tính bao gồm thời gian phiên làm việc, số lượng file được mở để đọc. Bước thứ hai, thuật toán tạo ra một véctơ Bernoulli để đại diện cho các thuộc tính vượt ra ngoài khoảng cho một phiên làm việc riêng biệt. Một véctơ ngưỡng T = , trong đó ti là một bộ của mẫu được sử dụng để hỗ trợ bước này. Véctơ ngưỡng được lưu trữ trong một cấu hình cá nhân. Véctơ Bernoulli B= được tạo ra sao cho bi được thiết lập là 1 nếu xi rơi ra khỏi phạm vi ti và bi được thiết lập bằng 0 trong trường hợp còn lại. Bước thứ ba, thuật toán tạo ra một điểm số trọng số xâm nhập cho mỗi loại xâm nhập riêng biệt, từ véctơ Bernoulli và véctơ trọng số xâm nhập. Mỗi nhóm và mỗi cặp loại xâm nhập có một véctơ trọng số xâm nhập W = <w1, w2, …,wn>, trong đó mỗi wi liên quan tới tầm quan trọng của thuộc tính thứ i trong véctơ Bernoulli để phát hiện kiểu xâm nhập riêng biệt. Điểm số trọng số xâm nhập đơn giản là tổng các trọng số wi, trong đó thuộc tính thứ i rơi ra khỏi phạm vi ti. Đó là, Điểm trọng số xâm nhập = ∑ ܾ௜ݓ௜௡ଵ Bước cuối cùng, thuật toán tạo ra một thương số khả nghi đại diện cho mức độ khả nghi của phiên làm việc này, nó được so sánh với tất cả các phiên làm việc khác cho một loại xâm nhập riêng biệt. Đặc biệt, thương số khả nghi là xác suất mà điểm số trọng số xâm nhập của phiên làm việc ngẫu nhiên ít hơn hoạc bằng điểm số trọng số xâm nhập được tính toán ở bước trước. 1.3.2. Kỹ thuật Neural Network. Fox, Henning, Reed và Simmonian (1990) lần đầu tiên cố gắng mô hình hóa hệ thống và hành vi người dùng bằng mạng nơron (neural nework). Lựa chọn mạng nơron của họ là bản đồ tự tổ chức Kohonen (Kohonen’s self- organizing map – Kohonen SOM), là một kiểu kỹ thuật học không giám sát, có 7 thể phát hiện ra cấu trúc cơ bản của dữ liệu mà không có mẫu trước về các hoạt động xâm nhập hay hoạt động bình thường. Họ sử dụng SOM như một bộ phận giám sát chạy ngầm theo thời gian thực, báo động cho một hệ chuyên gia phức tạp hơn. Trong hệ thống mẫu đầu tiên của họ, 11 tham số hệ thống có thể sử dụng được từ dữ liệu thống kê hiệu suất của hệ thống được định nghĩa như đầu vào của mô hình SOM. Những tham số này bao gồm : CPU usage, paging activity, mailer activity, disk accesses, memory usage, average session time, number of users, absentee jobs, reads of help files, failed log-ins, multiple log-ins. Tuy nhiên, nghiên cứu của họ chỉ ra kết quả của duy nhất một chương trình mô phỏng tấn công virus, nó không đủ để đưa ra một kết luận quan trọng. Trong một cố gắng áp dụng mạng nơron khác vào việc phát hiện dị thường, Ghosh, Wanken và Charron (1998) đề xuất sử dụng một mạng lan truyền ngược (back-propagation network) để giám sát các chương trình đang chạy. Một mạng lan truyền ngược được phát triển cho việc học có giám sát. Nó cần các mẫu hoạt động thông thường và xâm nhập (dữ liệu huấn luyện) để xây dựng mô hình phát hiện xâm nhập. Như một mạng bao gồm một lớp đầu vào, ít nhất một lớp ẩn (nơron không được kết nối trực tiếp với nốt đầu vào hoặc ra) và một lớp đầu ra. Thông thường, không có kết nối giữa các nơron trong cùng lớp hoặc giữa những nơron trong một lớp với những nơron trong lớp trước đó. Chu kỳ huấn luyện của mạng lan truyền ngược diễn ra trong 2 giai đoạn. Trong giai đoạn thứ nhất, đầu vào được gửi tới mạng và được lan truyền tới đầu ra của mạng. Trong giai đoạn thứ hai, đầu ra thực tế của mạng được so sánh với 1 đầu ra tiêu chuẩn. Nếu véctơ không được chấp nhận, mạng cập nhật trọng số bắt đầu ở nơron đầu ra. Sau đó thay đổi trong các trọng số được tính toán cho lớp trước và đổ qua các lớp của nơron hướng về phía nơron đầu vào. Ghosh và công sự đã đề xuất sử dụng đầu vào chương trình và bên trong chương trình như đầu vào của mạng lan truyền ngược. Một kết quả đáng chú ý là họ đã cải tiến hiệu quả phát hiện bằng việc sử dụng dữ liệu được tạo ngẫu nhiên như đầu vào dị thường. Bằng việc xem xét các dữ liệu được tạo một cách ngẫu nhiên, mạng nhận được nhiều dữ liệu huấn luyện hơn bổ sung cho dữ liệu huấn luyện thực tế. 8 Cũng giống như mô hình phát hiện dựa trên thống kê dị thường, việc quyết định các tham số đầu vào cho mạng nơron phát hiện dị thường là vấn đề khó khăn. Thêm vào đó, việc gán trọng số khởi tạo cho mạng nơron cũng là câu hỏi chưa được giải quyết. Kinh nghiệm của Ghosh và cộng sự đã chỉ ra rằng trọng số khởi tạo khác nhau có thể dẫn tới bộ phát hiện dị thường với hiệu quả khác nhau. 1.3.3. Kỹ thuật khai phá và phân tích dữ liệu kiểm toán. Khai thác và phân tích dữ liệu kiểm toán ( Audit data analysis and mining – ADAM) đề xuất áp dụng các kỹ thuật khai phá dữ liệu vào việc khám phá các mẫu dị thường trong một lượng lớn dữ. ADAM sử dụng vài kỹ thuật liên quan tới khai phá dữ liệu giúp phát hiện các hoạt động mạng bất thường như các luật kết hợp (association rules), bộ ước lượng giả Bayes (Pseudo Beyes estimator), Kỹ thuật thứ ba ADAM sử dụng là kỹ thuật phân lớp. 9 Chương 2 – MÁY VÉCTƠ HỖ TRỢ 2.1 Tổng quan về máy véctơ hỗ trợ 2.1.1. Giới thiệu máy véctơ hỗ trợ Máy véctơ hỗ trợ (Support vector machine – SVM) là một thuật toán học máy nổi tiếng được sử dụng để giải quyết bài toán phân lớp. Thuật toán SVM ban đầu được phát minh bởi Vladimir N. Vapnik và thuật toán SVM tiêu chuẩn hiện nay được đề xuất bởi Vladimir N. Vapnik và Corinna Cortes năm 1995. SVM đã được áp dụng rất thành công trong việc giải quyết các vấn đề của thế giới thực như nhận dạng văn bản [9], nhận dạng hình ảnh [2], nhận dạng chữ viết tay [15], phân loại thư rác điện tử [6], phát hiện xâm nhập mạng [10],[12]… Ban đầu thuật toán SVM được thiết kế cho bài toán phân lớp nhị phân. Ý tưởng chính của nó như sau : Cho X= {xi} là tập các véctơ trong không RD và xi thuộc một trong hai lớp yi = -1 hoặc yi = +1. Ta có tập điểm dữ liệu huấn luyện được biểu diễn như sau : {xi, yi} với i = 1…l, yi ∈ {-1, 1}, l là số điểm dữ liệu huấn luyện Giả sử rằng dữ liệu là phân tách tuyến tính, nghĩa là ta có thể vẽ một đường thẳng trên đồ thị của x1 và x2 phân tách hai lớp khi D = 2 và một siêu phẳng trên đồ thị của x1, x2… xD phân tách hai lớp với D > 2. Mục tiêu của SVM là xây dựng một siêu phẳng giữa hai lớp sao cho khoảng cách từ nó tới các điểm gần siêu phằng nhất của hai lớp là cực đại. Siêu phẳng có thể được mô tả bởi phương trình : w . x + b = 0 trong đó: . là phép nhân véctơ vô hướng. w là véctơ pháp tuyến của siêu phẳng. ௕||௪|| là khoảng cách vuông góc từ siêu phẳng tới gốc tọa độ. Véctơ hỗ trợ là những điểm dữ liệu gần siêu phẳng phân tách nhất. 10 Hình học véctơ chỉ ra rằng lề bằng ଵ ‖௪‖ và việc cực đại hóa nó với ràng buộc (2.3) giống với việc tìm kiếm: min ||w|| thỏa mãn yi(xi . w + b) - 1 ≥ 0 ∀i (2.6) Khi đã tìm được w0, b0 thỏa mãn (2.6), một mẫu mới x’ sẽ được phân lớp bằng cách sử dụng mô hình: Người ta chỉ ra rằng nếu các véctơ huấn luyện được phân tách mà không có lỗi bởi một siêu phẳng thì xác suất lỗi mắc phải trên một mẫu kiểm tra được giới hạn bởi tỉ lệ giữa giá trị kì vọng của số lượng véctơ hỗ trợ và số lượng véctơ huấn luyện [3] : E[Pr(error)] ≤ ܧ[ܵố ݒéܿ ݐơ ℎỗ ݐݎợợ] ܵố ݒéܿ ݐơ ℎݑấ݊ ݈ݑݕệ݊ 2.2. Mô hình SVM cho bài toán hai lớp 2.2.1. Mô hình primal Cho X = {xi, i = 1,…,n} là một tập các véctơ trong không ℝௗ, và nhãn lớp của xi là yi ∈ Y = {-1,+1} . Ta có tập điểm dữ liệu huấn luyện được biểu diễn như sau: T={(xi, yi) ; i = 1…n ; yi ∈ {-1, 1}}, trong đó n là số điểm dữ liệu huấn luyện. Như đã trình bày trong phần 2.1.1, để cực đại hóa lề người ta cực tiểu hóa ||w||. Điều này cũng tương tự như cực tiểu hóa ଵ ଶ ‖ݓ‖ଶ nhưng việc thay thế ||w|| với ଵ ଶ ‖ݓ‖ଶ giúp bài toán có thể giải quyết dễ dàng hơn. Để xác định được bộ phân lớp (w,b) người ta giải quyết bài toán tối ưu như sau: ݉݅݊௪,௕ ଵଶ ‖ݓ‖ଶ thỏa mãn: yi(xi . w + b) - 1 ≥ 0 i, i=1,…,n. (2.2) Bài toán (2.2) là một bài toán tối ưu dạng toàn phương. Mô hình này thường được gọi là SVM biên cứng. Trong thực tế, ta thường sử dụng biên mềm bằng cách chấp nhận một số lượng nhỏ các mẫu 11 phân lớp sai trong giới hạn chấp nhận được. Việc này được thực hiện bằng cách thêm vào tham số nới lỏng không âm ߦ௜, i = 1, …n: xi . w + b ≥ +1 - ߦ௜ cho yi = +1 (2.3) xi . w + b ≤ -1 - ߦ௜ cho yi = -1 (2.4) ߦ௜ ≥ 0 ∀௜ (2.5) Có thể kết hợp hai phương trình trên thành: yi(xi . w + b) – 1 + ߦ௜ ≥ 0 với ߦ௜ ≥ 0 ∀௜ (2.6) Chúng ta có mô hình SVM biên mềm như sau: min௪,௕ 12 ‖ݓ‖ଶ + ܥ ෍ߦ௜௡ ௜ୀଵ sao cho: ݕ௜ (ݔ௜ .ݓ + ܾ) − 1 + ߦ௜ 0 ∀݅ = 1, …n. (2.7) 2.2.2. Mô hình dual  Ta xét biểu thức Lagrange của bài toán tối ưu hóa (2.2): L୔ = L(୵,ୠ,஑) = ଵଶ ‖ݓ‖ଶ− ∑ ߙ௜௡௜ୀଵ [ݕ௜(ݓ. ݔ௜ + ܾ) − 1] (2.8) Trong đó, ߙ௜ là nhân tử Lagrange. Ta cần tìm điểm yên ngựa (ݓ଴,ܾ଴, ߙ଴) bởi vì hàm Lagrange sẽ phải được cực tiểu hóa theo w và b, cực đại hóa theo ߙ௜ không âm. Phương trình (2.8) có thể viết lại như sau: L୔ = L