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à

Hai chữ viết tắt sẽ theo suốt mục này. FSM là finite state machine — máy trạng thái hữu hạn: một cơ chế chỉ có vài trạng thái xác định, và một quy tắc cố định nói rằng đang ở trạng thái này, gặp sự kiện kia thì chuyển sang trạng thái nào. Đèn giao thông là một FSM ba trạng thái. Bộ dự đoán nhánh dưới đây là FSM với 2 hoặc 4 trạng thái, và "sự kiện" của nó là kết quả thật của lần rẽ nhánh vừa rồi.

BHT là Branch History Table — bảng lịch sử nhánh: thay vì dùng MỘT bộ dự đoán cho cả chương trình, CPU giữ một bảng tra theo địa chỉ lệnh, để mỗi lệnh rẽ nhánh có bộ dự đoán RIÊNG của nó. Cần thế vì các nhánh khác nhau có thói quen khác nhau: nhánh thoát vòng lặp gần như luôn "nhảy", còn nhánh kiểm tra lỗi gần như luôn "không nhảy" — trộn chúng vào một bộ đếm thì cả hai đều đoán tệ hơn.

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ế.

// 1-bit predictor: remembers ONLY the MOST RECENT outcome, and predicts the same.
function makeBranchPredictor1Bit() {
  let state = 0; // 0 = predict Not-taken (N), 1 = predict Taken (T)
  return {
    predict: () => (state === 1 ? 'T' : 'N'),
    update: (actual) => { state = actual === 'T' ? 1 : 0; },
  };
}
// Verified on the nested-loop sequence (TTTTN repeated 3 times, 15 branches):
// the 1-bit predictor gets only 9/15 = 60% right.

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:

// States: 0=Strongly-not-taken 1=Weakly-not-taken 2=Weakly-taken 3=Strongly-taken.
// Predict T once state >= 2. One wrong guess only nudges the state one notch, so a
// single blip does NOT flip the prediction.
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): every branch ADDRESS gets its OWN 2-bit predictor,
// indexed by pc - different branches have different habits.
function makeBranchHistoryTable() {
  const table = new Map();
  const entryFor = (pc) => {
    if (!table.has(pc)) table.set(pc, makeBranchPredictor2Bit());
    return table.get(pc);
  };
  return {
    predict: (pc) => entryFor(pc).predict(),
    update: (pc, actual) => entryFor(pc).update(actual),
    size: () => table.size,
  };
}
// Verified on the SAME 15-branch sequence: the 2-bit predictor gets 10/15 = 66.7%
// right - better than the 1-bit one.

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 (no branches at all -> the ideal CPI)

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. Train the predictor: call the function many times with a VALID index
//    -> the predictor comes to "trust" that the bounds-check branch is TRUE
// 2. Call it again with an OUT-OF-BOUNDS index (past the real array)
//    -> the CPU PREDICTS the check is still TRUE and SPECULATIVELY reads the
//       out-of-bounds data into a register, using it to index a second array
//    -> the secret value is now part of an ADDRESS that entered the cache
// 3. When the CPU notices the misprediction it RESTORES architectural state
//    (registers and memory)
//    -> BUT the cache still holds the trace (that address is now cached)
// 4. The attacker TIMES a read of each candidate address
//    -> whichever address is fast (i.e. cached) reveals part of the secret

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