Bài 5: Dự Đoán Nhánh & Lỗ Hổng Bảo Mật Spectre

Mở đầu: khi pipeline không biết lệnh nào sẽ đến tiếp theo

Bài 4 giải quyết xung đột DỮ LIỆU giữa các lệnh chồng lấp trong pipeline — nhưng còn một loại xung đột khác, nguy hiểm hơn về mặt THÔNG LƯỢNG: lệnh rẽ nhánh có điều kiện (BEQ, BNE) làm CPU không biết lệnh NÀO sẽ chạy tiếp theo cho tới khi chính nhánh đó được tính toán xong (ở giai đoạn EX, tức 2-3 chu kỳ SAU khi IF đã lỡ nạp lệnh tiếp theo). Đây là xung đột điều khiển (control hazard) — và cách CPU hiện đại giải quyết nó (đoán trước rồi chạy suy đoán) vô tình mở ra lỗ hổng bảo mật phần cứng nghiêm trọng nhất lịch sử: Spectre.

1. Xung đột điều khiển (Control Hazards) & sự cần thiết của dự đoán

Với lệnh BEQ, CPU chỉ biết CHẮC CHẮN địa chỉ lệnh tiếp theo sau khi tính xong điều kiện so sánh ở giai đoạn EX (theo mô hình Bài 4: EX là giai đoạn thứ 3 trong 5 giai đoạn IF-ID-EX-MEM-WB). Nhưng pipeline đã phải NẠP (IF) 2 lệnh kế tiếp ngay trong 2 chu kỳ liền sau đó — nếu không đoán trước, CPU buộc phải DỪNG nạp lệnh (stall) cho tới khi biết kết quả, mất đúng 1-3 chu kỳ mỗi lần rẽ nhánh (tuỳ CPU rẽ nhánh được giải quyết ở giai đoạn nào). Với chương trình có nhánh xuất hiện dày đặc — mọi if/else, mọi vòng lặp — chi phí này cộng dồn cực lớn nếu không xử lý.

2. Bộ dự đoán nhánh tĩnh & động: FSM 1-bit và 2-bit bão hoà

Cách đơn giản nhất — dự đoán tĩnh (luôn đoán Không-nhảy, hoặc luôn đoán Nhảy) — chỉ đúng khoảng 50% với nhánh ngẫu nhiên. Dự đoán động ghi nhớ LỊCH SỬ của chính nhánh đó để đoán thông minh hơn, dựa trên tính lặp lại rất cao của nhánh trong vòng lặp thực tế.

// Bo du doan 1-bit: chi nho KET QUA LAN GAN NHAT, doan y het lan do
function makeBranchPredictor1Bit() {
  let state = 0; // 0 = doan Khong-nhay (N), 1 = doan Nhay (T)
  return {
    predict: () => (state === 1 ? 'T' : 'N'),
    update: (actual) => { state = actual === 'T' ? 1 : 0; },
  };
}
// Verified: tren chuoi vong lap long nhau (TTTTN lap 3 lan, 15 nhanh),
// bo 1-bit chi doan dung 9/15 = 60%

Bộ dự đoán 2-bit bão hoà (saturating counter) dùng 4 trạng thái thay vì 2 — một lần đoán sai ĐƠN LẺ chỉ đẩy trạng thái qua một nấc liền kề chứ KHÔNG lật ngay dự đoán, nên "chịu đựng" được nhiễu nhỏ tốt hơn hẳn:

// 0=Rat-khong-nhay 1=Hoi-khong-nhay 2=Hoi-nhay 3=Rat-nhay; doan T khi state>=2
function makeBranchPredictor2Bit() {
  let state = 0;
  return {
    predict: () => (state >= 2 ? 'T' : 'N'),
    update: (actual) => {
      state = actual === 'T' ? Math.min(3, state + 1) : Math.max(0, state - 1);
    },
  };
}
// BHT (Branch History Table): moi DIA CHI lenh re nhanh co MOT bo du doan
// 2-bit RIENG (lap chi muc theo pc) - cac nhanh khac nhau co xu huong khac nhau
function makeBranchHistoryTable() {
  const table = new Map();
  // ... entryFor(pc) tra ve/tao bo du doan 2-bit rieng cho dia chi pc ...
}
// Verified: CUNG chuoi 15 nhanh o tren, bo 2-bit dung 10/15 = 66,7% (tot hon 1-bit)

3. Tính toán CPI hiệu dụng & chi phí đoán sai

Mỗi lần đoán SAI, pipeline phải xả (flush) các lệnh đã nạp nhầm hướng và nạp lại đúng hướng — tốn PenaltyCycles chu kỳ hoàn toàn lãng phí. CPI hiệu dụng cộng thêm đúng phần chi phí này vào CPI lý tưởng:

$$CPI_{eff} = CPI_{ideal} + \text{BranchFrequency} \times \text{MispredictionRate} \times \text{PenaltyCycles}$$

Bài toán thực tế: chương trình có 20% lệnh là rẽ nhánh, bộ dự đoán đạt tỷ lệ đoán sai 10%, mỗi lần đoán sai phạt 3 chu kỳ, CPI lý tưởng $=1$ — verified thật: $CPI_{eff} = 1 + 0,2 \times 0,1 \times 3 = \mathbf{1,06}$. Nghĩa là chỉ riêng đoán sai nhánh đã làm CPU chậm đi 6% so với lý tưởng, dù tỷ lệ đoán sai chỉ 10% — vì CPI hiệu dụng nhân dồn CẢ BA yếu tố (tần suất nhánh × tỷ lệ sai × số chu kỳ phạt).

function effectiveCPI(cpiIdeal, branchFrequency, mispredictionRate, penaltyCycles) {
  return cpiIdeal + branchFrequency * mispredictionRate * penaltyCycles;
}
// Verified: effectiveCPI(1, 0.2, 0.1, 3) === 1.06
// Verified: effectiveCPI(1, 0, 0.1, 3) === 1 (khong co nhanh nao -> dung CPI ly tuong)

4. Thực thi suy đoán (Speculative Execution) & Lỗ hổng Spectre

Sau khi ĐOÁN hướng nhánh, CPU hiện đại không chỉ nạp lệnh mà còn chạy trước (speculative execution) các lệnh ở nhánh được đoán — kể cả các lệnh LOAD dữ liệu từ bộ nhớ vào cache. Nếu đoán ĐÚNG, kết quả được "chính thức hoá" (commit) bình thường. Nếu đoán SAI, CPU khôi phục đúng trạng thái kiến trúc (registers, bộ nhớ) như chưa từng chạy các lệnh đó — nhưng có MỘT dấu vết KHÔNG bị xoá: trạng thái cache. Dữ liệu đã được nạp suy đoán vẫn NẰM TRONG cache dù kết quả kiến trúc bị huỷ bỏ.

Spectre (công bố 2018) khai thác đúng dấu vết này: kẻ tấn công huấn luyện bộ dự đoán nhánh để ép CPU nạn nhân THI HÀNH SUY ĐOÁN một đoạn mã đọc dữ liệu bí mật (vd ngoài biên mảng, vượt qua kiểm tra bounds-check mà CPU chưa kịp xác nhận), rồi dùng thời gian truy cập cache (cache-timing side-channel attack — đo xem một địa chỉ có nằm trong cache hay không qua độ trễ đọc) để SUY RA giá trị bí mật đó, dù kết quả kiến trúc của phép tính suy đoán đã bị huỷ hoàn toàn. Đây KHÔNG phải lỗi phần mềm đơn lẻ — nó khai thác chính CƠ CHẾ suy đoán mà mọi CPU hiệu năng cao hiện đại đều cần để đạt tốc độ.

// 1. Huan luyen bo du doan: goi ham voi index HOP LE nhieu lan
//    -> bo du doan "tin tuong" nhanh bounds-check se la TRUE
// 2. Goi lai voi index NGOAI BIEN (vuot mang that su)
//    -> CPU DOAN nhanh check van TRUE, THI HANH SUY DOAN doc du lieu
//       ngoai bien vao thanh ghi, dung no lam chi so doc tiep 1 mang khac
//    -> gia tri bi mat gio la 1 phan CHI SO dia chi trong cache
// 3. Khi CPU phat hien doan SAI: KHOI PHUC kien truc (thanh ghi/bo nho)
//    -> NHUNG cache VAN con dau vet (dia chi vua duoc doc vao cache)
// 4. Ke tan cong do THOI GIAN truy cap tung dia chi ung vien
//    -> dia chi nao nhanh (co trong cache) = suy ra dung 1 phan gia tri bi mat

5. Thực hành: Mô phỏng dự đoán nhánh 2-bit

Chọn một cấu trúc điều khiển bên dưới để chạy ĐỒNG THỜI cả bộ dự đoán 1-bit và 2-bit (dùng đúng engine đã verify) — ô xanh là đoán ĐÚNG, ô đỏ là đoán SAI, so sánh trực tiếp tỷ lệ dự đoán chính xác thực tế của 2 bộ trên CÙNG một chuỗi nhánh:

Tóm lược

• ✅ Xung đột điều khiển: CPU chỉ biết chắc hướng rẽ nhánh sau EX, nhưng đã phải nạp lệnh tiếp theo trước đó — mất 1-3 chu kỳ mỗi nhánh nếu không đoán trước.
• ✅ Verified: bộ dự đoán 1-bit đúng 60% trên vòng lặp lồng nhau (dao động ở mỗi biên vòng lặp); 2-bit bão hoà đúng 66,7% (chịu được 1 lần nhiễu đơn lẻ).
• ✅ BHT lưu lịch sử RIÊNG theo từng địa chỉ nhánh — các nhánh khác nhau có xu hướng khác nhau, không thể gộp chung một bộ dự đoán.
• ✅ Verified: $CPI_{eff} = CPI_{ideal} + \text{BranchFreq} \times \text{MispredictRate} \times \text{Penalty}$ — 20% nhánh, 10% đoán sai, phạt 3 chu kỳ → CPI tăng 6% (1 → 1,06).
• ✅ Spectre khai thác dấu vết CACHE còn sót lại sau khi thực thi suy đoán bị huỷ — không có bản vá phần mềm nào loại bỏ hoàn toàn mà không tốn hiệu năng, vì gốc rễ nằm ở phần cứng.

Trắc nghiệm ôn tập