112 年 國立中山大學資訊工程學系資訊安全碩士班《作業系統》

（1）Process Protection

（a）最小權限原則（Principle of Least Privilege）

核心觀念：
最小權限原則是指：每一個使用者、程序或系統元件，只能擁有完成目前工作所必需的最少權限，而且權限只在必要期間內有效。

可表示為：

$$\text{程序實際權限} \subseteq \text{完成任務所需權限}$$

例如，Web 服務程序只需：

• 讀取網站設定檔；
• 讀取網頁資料；
• 對日誌檔附加內容；
• 使用指定網路埠。

則不應同時擁有：

• 修改其他使用者檔案的權限；
• 讀取密碼資料庫的權限；
• 直接存取整個磁碟的權限；
• 核心模式或系統管理員權限。

可用下列方式表示：

$$\text{Web 程序} \longrightarrow \{\text{read config},\ \text{read web files},\ \text{append log}\}$$

而不是：

$$\text{Web 程序} \longrightarrow \{\text{所有檔案、所有裝置、核心及管理員權限}\}$$

解題方法：
回答時應包含「權限最少」與「使用期間最短」兩個重點。作業系統可透過使用者模式／核心模式、存取控制清單（ACL）、Capability、角色權限、沙箱及權限分離等機制實作。

安全效果：

1. 程序遭入侵時，攻擊者能取得的權限受到限制。
2. 降低 Trojan horse 或惡意程式造成的損害。
3. 防止不必要的檔案、記憶體及裝置存取。
4. 權限提升只在必要時發生，工作完成後立即撤除。

---

（b）Protection Domain

核心觀念：
Protection domain（保護領域）是程序目前可以使用的所有物件及其操作權限集合。

若物件集合為 $O$，操作權限集合為 $R$，則一個保護領域可表示為：

$$D=\{(O_i,R_i)\}$$

其中：

• $O_i$：受保護的物件，例如檔案、記憶體區域、裝置或程序；
• $R_i$：對該物件允許的操作，例如 read、write、execute、delete。

例如：

$$D_{\text{web}} = \{ (\text{config},\{\text{read}\}), (\text{log},\{\text{append}\}), (\text{network socket},\{\text{send},\text{receive}\}) \}$$

表示 Web 程序只能依照此領域中的權限存取資源。

Protection domain 也可用存取矩陣表示：

保護領域	設定檔	日誌檔	網路埠	核心記憶體
$D_{\text{web}}$	read	append	use	none
$D_{\text{user}}$	read/write	read	use	none
$D_{\text{kernel}}$	read/write	read/write	control	read/write

存取矩陣的一列就是一個 protection domain；矩陣中的內容則是該領域對各物件擁有的權限。

解題方法：

• 程序執行時，會在某一個 protection domain 中運作。
• 作業系統依據目前 domain 判斷是否允許存取。
• 若程序需要執行不同階段的工作，可透過合法的 domain switch 切換權限。
• 最小權限原則決定「應該給多少權限」；protection domain 則描述「目前實際擁有哪些權限」。

---

（2）CPU Scheduling

核心觀念與公式

所有程序均在時間 $0$ 到達，因此：

$$A_i=0$$

令：

• $B_i$：CPU burst time；
• $C_i$：completion time，程序完成的時間；
• $W_i$：等待時間。

本題都是非搶先式排程，因此：

$$W_i=C_i-B_i$$

平均等待時間為：

$$\overline{W} = \frac{\sum W_i}{n}$$

因為所有程序的到達時間都是 $0$，所以 completion time 也等於 turnaround time。

相同 burst time 的程序，題目未指定 tie-break，本解依照題目表格出現順序處理。

---

（a）First-Come, First-Served（FCFS）

解題方法：
FCFS 按照到達順序執行。所有程序同時到達，因此依題目列出的順序：

$$P_1\rightarrow P_2\rightarrow P_3\rightarrow P_4\rightarrow P_5\rightarrow P_6$$

Gantt chart：

$$0 \xrightarrow{P_1} 8 \xrightarrow{P_2} 10 \xrightarrow{P_3} 14 \xrightarrow{P_4} 16 \xrightarrow{P_5} 24 \xrightarrow{P_6} 30$$

程序	Burst time	Completion time $C_i$	等待時間 $W_i=C_i-B_i$
$P_1$	8	8	0
$P_2$	2	10	8
$P_3$	4	14	10
$P_4$	2	16	14
$P_5$	8	24	16
$P_6$	6	30	24

平均等待時間：

$$\overline{W}_{\text{FCFS}} = \frac{0+8+10+14+16+24}{6} = \frac{72}{6} = 12\text{ ms}$$

解題技巧：
FCFS 可直接累加 burst time 得到 completion time；等待時間則是該程序開始前所有 burst time 的總和。

---

（b）Shortest-Job-First（SJF）

解題方法：
所有程序一開始都已到達，且採用非搶先式 SJF，因此按照 burst time 由小到大排序：

程序	Burst time
$P_2$	2
$P_4$	2
$P_3$	4
$P_6$	6
$P_1$	8
$P_5$	8

因此執行順序為：

$$P_2\rightarrow P_4\rightarrow P_3\rightarrow P_6\rightarrow P_1\rightarrow P_5$$

Gantt chart：

$$0 \xrightarrow{P_2} 2 \xrightarrow{P_4} 4 \xrightarrow{P_3} 8 \xrightarrow{P_6} 14 \xrightarrow{P_1} 22 \xrightarrow{P_5} 30$$

程序	Burst time	Completion time $C_i$	等待時間 $W_i$
$P_1$	8	22	14
$P_2$	2	2	0
$P_3$	4	8	4
$P_4$	2	4	2
$P_5$	8	30	22
$P_6$	6	14	8

平均等待時間：

$$\overline{W}_{\text{SJF}} = \frac{0+2+4+8+14+22}{6} = \frac{50}{6} = \frac{25}{3} \approx 8.33\text{ ms}$$

解題技巧：

• SJF 的排序依據是 burst time，不是 priority。
• 相同 burst time 的程序只會互換各自的 completion time，平均等待時間不變。
• 在所有程序同時到達的條件下，非搶先式 SJF 通常能得到最低的平均等待時間。

---

（c）Non-preemptive Priority Scheduling

核心觀念：
題目指定 priority number 越小，優先權越高。非搶先式表示程序一旦開始執行，就會執行到完成，不會被新程序中斷。

依 priority 排序：

程序	Priority
$P_3$	1
$P_2$	2
$P_1$	3
$P_4$	4
$P_5$	5
$P_6$	6

執行順序：

$$P_3\rightarrow P_2\rightarrow P_1\rightarrow P_4\rightarrow P_5\rightarrow P_6$$

Gantt chart：

$$0 \xrightarrow{P_3} 4 \xrightarrow{P_2} 6 \xrightarrow{P_1} 14 \xrightarrow{P_4} 16 \xrightarrow{P_5} 24 \xrightarrow{P_6} 30$$

程序	Priority	Burst time	Completion time $C_i$
$P_1$	3	8	14
$P_2$	2	2	6
$P_3$	1	4	4
$P_4$	4	2	16
$P_5$	5	8	24
$P_6$	6	6	30

因此：

$$C_{P_1}=14,\quad C_{P_2}=6,\quad C_{P_3}=4,\quad C_{P_4}=16,\quad C_{P_5}=24,\quad C_{P_6}=30$$

---

（3）HDFS 與 YARN

HDFS（Hadoop Distributed File System）

核心觀念：
HDFS 是 Hadoop 的分散式檔案系統，目標是將大量資料分散儲存在多部一般伺服器上，提供高吞吐量、容錯及資料區域性。

架構如下：

$$\text{Client} \longrightarrow \text{NameNode：管理中繼資料}$$ $$\text{Client} \longleftrightarrow \text{DataNode：儲存實際資料區塊}$$

主要元件：

1. NameNode

   • 管理檔案系統 namespace。
   • 儲存檔名、目錄結構、權限及 block 與 DataNode 的對應關係。
   • 主要負責中繼資料，不直接儲存檔案內容。

2. DataNode

   • 將檔案切割成大型 blocks，儲存在本機磁碟。
   • 負責實際的資料讀寫。
   • 定期向 NameNode 回報 heartbeat 與 block report。

3. Client

   • 讀取資料時先向 NameNode 查詢 block 位置，再直接向 DataNode 讀取。
   • 寫入資料時由 NameNode 配置儲存位置，資料再寫入 DataNode。

主要特性：

• Block-based storage： 大檔案會切成大型資料區塊，便於分散儲存。
• Replication： 每個 block 通常具有多份副本，常見預設複本數為 3，實際數量由設定決定。
• 容錯能力： DataNode 故障時，NameNode 可偵測失效並重新複製遺失的 block。

(1) Advanced Persistent Threat (APT)

高階持續性威脅 (APT) 是指由具備高技術能力與豐富資源的攻擊團隊（如國家級組織或專業駭客集團），針對特定目標（如政府機關、關鍵基礎設施、大型企業）進行的長期、隱密且具針對性的網路攻擊行動。

• 高階 (Advanced)：採用零日漏洞 (Zero-day exploit)、社交工程 (Spear Phishing) 及客製化惡意軟體等進階攻擊技術。
• 持續性 (Persistent)：入侵後不以立即破壞為目的，而是長期隱匿潛伏 (Persistence)，維持存取權限並持續竊取敏感資料。
• 威脅 (Threat)：具備明確的政治、經濟或軍事動機，並對目標造成重大威脅。

【答案】APT 是一種由高資源組織發動，結合零日漏洞與社交工程等進階技術，針對特定高價值目標進行長期潛伏與資料竊取的針對性網路攻擊。

---

(2) Covert Channel / Side Channel Attack

• 隱蔽通道 (Covert Channel)：利用系統中非設計用於通訊的管道或共享資源（如 CPU 佔用率變化、 shared memory 存取時間差異、檔案鎖定狀態），違規繞過系統的安全存取控制策略 (Access Control Policies) 來傳輸秘密資訊。
• 側通道攻擊 (Side Channel Attack)：不直接對密碼學演算法的數學結構進行破解，而是透過觀察加密裝置在執行運算過程中所洩露的實體物理資訊（如執行時間差 Timing Information、耗電量 Power Consumption、電磁輻射 Electromagnetic Radiation、快取命中/未命中 Cache Hit/Miss）來推導出秘密金鑰。

【答案】隱蔽通道是利用非預期通訊管道繞過存取控制傳遞資料；側通道攻擊則是利用裝置運算時洩露的實體物理資訊（如時間差、功耗）來推導秘密金鑰。

---

(3) 同時達成機密性、完整性與不可否認性之密碼學演算法與機制

1. 所需密碼學演算法

• 機密性 (Confidentiality)：對稱加密演算法（如 AES）搭配非對稱加密演算法（如 RSA / ECC）構建混合加密系統 (Hybrid Cryptosystem)。
• 完整性 (Integrity)：密碼雜湊函數 (Cryptographic Hash Function，如 SHA-256)。
• 不可否認性 (Non-repudiation)：基於非對稱密碼學的數位簽章演算法 (Digital Signature Algorithm，如 RSA Signature / ECDSA)。

2. 保護訊息與傳輸步驟 (How)

設發送者為 A（擁有私鑰 $SK_A$、公鑰 $PK_A$），接收者為 B（擁有私鑰 $SK_B$、公鑰 $PK_B$），訊息為 $M$：

1. 數位簽章（確保 Integrity & Non-repudiation）：
   • 發送者 A 計算訊息雜湊值 $h = H(M)$。
   • 發送者 A 用自己的私鑰 $SK_A$ 對 $h$ 加密產生數位簽章 $S = E(SK_A, h)$。

核心觀念

本題考查 Hadoop 叢集中的兩個核心子系統：

• HDFS：負責分散式資料儲存。
• YARN：負責叢集資源管理與應用程式排程。

兩者的分工可整理如下：

子系統	主要責任	核心問題
HDFS	儲存大型檔案、提供容錯與高吞吐量存取	資料放在哪裡、如何保護資料
YARN	管理 CPU、記憶體等叢集資源，執行應用程式	哪個應用程式何時使用哪些資源

因此，Hadoop 應用程式通常是「資料放在 HDFS，運算資源由 YARN 分配」。

若檔案大小為 $F$、區塊大小為 $B$，則檔案所需的資料區塊數為：

$$N=\left\lceil \frac{F}{B}\right\rceil$$

若副本因子為 $r$，資料約需 $rF$ 的實體儲存空間。副本因子通常設為 $3$，但實際數值可以設定，不是固定規則。

解題方法

本題是簡答題，作答時應針對 HDFS 與 YARN 分別說明：

1. 系統架構與主要元件。
2. 資料或資源的運作流程。
3. 主要設計特色。
4. 適用情境與限制。
5. HDFS 與 YARN 如何互相配合。

---

一、Hadoop Distributed File System（HDFS）

1. HDFS 的定位

HDFS 是 Hadoop 的分散式檔案系統，設計目標是：

• 儲存非常大型的檔案與資料集。
• 將資料分散至多台一般伺服器。
• 在硬體故障時仍能繼續提供資料。
• 以高吞吐量支援大量資料的連續讀寫。

HDFS 假設硬體由許多一般化、可發生故障的機器組成，因此不依賴單一大型伺服器，而是透過資料分割與複製達成可靠性。

2. HDFS 架構

                    中繼資料請求
使用者程式／Client  ───────────────→  NameNode
        │                              │
        │ 直接讀寫資料區塊              │ 回傳區塊位置
        ▼                              ▼
   DataNode A  ←── 資料副本 ──→  DataNode B  ←──→  DataNode C

HDFS 主要包含以下元件：

（1）NameNode

NameNode 是 HDFS 的主要管理節點，負責保存檔案系統的中繼資料，例如：

• 檔案與目錄名稱。
• 權限與檔案屬性。
• 檔案被切成哪些資料區塊。
• 每個資料區塊存在哪些 DataNode。
• 副本數量與副本位置。

NameNode 主要管理「資料在哪裡」，不負責儲存使用者檔案的實際內容。若所有資料讀寫都經過 NameNode，會形成嚴重瓶頸，因此 Client 取得區塊位置後，會直接與 DataNode 傳輸資料。

（2）DataNode

DataNode 負責：

• 在本機磁碟儲存實際資料區塊。
• 回應 Client 的讀寫要求。
• 定期向 NameNode 傳送 Heartbeat。
• 定期傳送 Block Report，回報本機擁有哪些資料區塊。
• 執行資料區塊的建立、刪除與複製。

若 NameNode 長時間收不到某個 DataNode 的 Heartbeat，會判定該節點故障，並安排其他節點重新建立遺失的副本。

（3）Client

Client 負責：

• 向 NameNode 查詢檔案與區塊位置。
• 直接向 DataNode 讀寫資料。
• 在寫入時協調資料副本的傳送流程。

3. 資料區塊與副本機制

HDFS 不會把整個檔案放在單一磁碟，而會將檔案切成固定大小的區塊。區塊大小通常遠大於一般檔案系統，例如常見設定為 $128\text{ MB}$。

每個區塊通常會儲存多份副本。假設副本因子為 $3$：

Block 1 ─→ DataNode 1
        ─→ DataNode 2
        ─→ DataNode 3

副本配置通常會考量 Rack Awareness，盡量將副本分散到不同機架。如此即使某一台機器，甚至某一個機架發生故障，其他副本仍可提供服務。

副本機制帶來兩個重要效果：

• 容錯：節點故障時仍可從其他副本讀取資料。
• 讀取效能：Client 可選擇距離較近的副本，減少網路傳輸成本。

4. HDFS 讀取流程

HDFS 的讀取流程如下：

1. Client 向 NameNode 詢問檔案所包含的資料區塊及其副本位置。
2. NameNode 回傳各區塊的 DataNode 清單。
3. Client 選擇距離較近或負載較適合的 DataNode。
4. Client 直接從 DataNode 讀取資料。
5. 若某個 DataNode 失效，Client 可改讀另一個副本。
6. 讀取時會進行 Checksum 驗證，以偵測資料損壞。

重點是：NameNode 負責提供位置資訊，資料本身由 Client 與 DataNode 直接傳輸。

5. HDFS 寫入流程

寫入檔案時，Client 先向 NameNode 要求建立檔案，NameNode 再選擇適合的 DataNode 保存副本。

若副本因子為 $3$，可形成如下的寫入管線：

Client → DataNode A → DataNode B → DataNode C
       ← 確認訊息 ←       ←

流程如下：

1. Client 向 NameNode 要求建立檔案。
2. NameNode 選擇儲存區塊的 DataNode 與副本位置。
3. Client 將資料送至第一個 DataNode。
4. 第一個 DataNode 將資料轉送給下一個 DataNode。
5. 資料依序寫入所有副本。
6. 確認訊息沿管線反向傳回 Client。
7. 若某個 DataNode 故障，HDFS 會重新配置寫入管線或建立遺失副本。

6. HDFS 的主要特色

（1）高吞吐量

HDFS 適合大型檔案的連續讀寫，透過資料分割與平行處理，同時從多個 DataNode 讀取資料，可提高整體吞吐量。

（2）可擴充性

新增 DataNode 即可增加儲存容量與資料傳輸能力，屬於橫向擴充架構。

（3）容錯能力

HDFS 透過資料複製、Heartbeat、Block Report、Checksum 與自動重新複製，降低硬體故障造成資料遺失的風險。

（4）資料區域性

Hadoop 會盡量將運算工作安排在資料所在節點附近，減少大量資料跨網路傳送，這稱為 Data Locality。

（5）適合寫入一次、讀取多次

HDFS 採用接近 Write-Once-Read-Many 的設計，適合批次分析、日誌、資料倉儲與大型資料集。

HDFS 不適合：

• 大量小檔案。
• 需要低延遲的單筆查詢。
• 頻繁的隨機寫入。
• 頻繁修改檔案中間內容的資料庫型工作負載。

大量小檔案會增加 NameNode 的中繼資料負擔，因為 NameNode 必須在記憶體中管理檔案、目錄與區塊對應關係。

7. NameNode 與 Secondary NameNode 的陷阱

Secondary NameNode 的主要工作是定期建立 NameNode 中繼資料的 Checkpoint，將檔案系統映像與編輯記錄整理合併。

Secondary NameNode 不是 NameNode 的即時備份，也不是故障時可立即接管的 Standby NameNode。

在較新的 HDFS 高可用性架構中，會使用 Active NameNode、Standby NameNode 與共享編輯記錄機制來降低 NameNode 單點故障問題。

---

二、Yet Another Resource Negotiator（YARN）

1. YARN 的定位

YARN 是 Hadoop 的叢集資源管理與應用程式排程平台。它將原本集中在 MapReduce JobTracker 的工作拆開，使 Hadoop 不只支援 MapReduce，也能支援 Spark、Tez、Flink 等不同運算框架。

YARN 管理的資源通常包括：

• 記憶體。
• 虛擬 CPU 核心。
• 佇列容量。
• 應用程式優先權。
• 節點與機架區域性。

2. YARN 架構

核心觀念

本題考查「位址繫結（address binding）」：將程式中的符號位址，例如變數名稱、函式標籤，轉換成實際記憶體位址的時機。位址可分為：

• 符號位址：原始程式中的 x、函式名稱、標籤。
• 邏輯位址／虛擬位址：程式執行時所看到的位址。
• 實體位址：實際 RAM 中的位址。

三種繫結時機如下：

繫結時機	編譯器／載入器產生的位址	實體位置改變時的處理
編譯時繫結	絕對位址	必須重新編譯
載入時繫結	可重定位位址	載入時由載入器修正
執行時繫結	邏輯／虛擬位址	每次存取時由硬體轉換

---

解題方法與示意程式

以下程式表示指令會讀取並修改資料 x：

I0: LOAD  R1, [x]
I1: ADD   R1, 1
I2: STORE [x], R1

假設程式配置結果如下，且每個位址單位代表一條指令或一個資料位置：

• I0 的相對位移為 $0$
• I1 的相對位移為 $1$
• I2 的相對位移為 $2$
• 資料 x 的相對位移為 $100$

因此，程式內部的配置為：

$$\text{指令起點}=0,\qquad \text{x 的邏輯位址}=100$$

---

一、編譯時繫結（compile-time binding）

若在編譯時已知程式必須放在實體記憶體起始位址 $4000$，編譯器便可直接產生絕對位址。

此時：

$$\text{I0 的實體位址}=4000$$ $$\text{x 的實體位址}=4000+100=4100$$

因此，編譯器產生的指令可直接表示為：

I0: LOAD  R1, [4100]
I1: ADD   R1, 1
I2: STORE [4100], R1

指令與資料的繫結結果為：

項目	絕對實體位址
I0	$4000$
I1	$4001$
I2	$4002$
x	$4100$

這種方式的重點是：位址在編譯期間就已確定。若程式實際必須載入 $7000$，原本指向 $4100$ 的指令便會錯誤，必須重新編譯，使 x 改為 $7100$。

---

二、載入時繫結（load-time binding）

若編譯時不知道程式最後會放在記憶體的哪個位置，編譯器會產生可重定位程式，使用相對位移表示指令與資料位置。

此時指令可先表示為：

I0: LOAD  R1, [100]
I1: ADD   R1, 1
I2: STORE [100], R1

載入器選定程式起始位址為 $4000$ 後，再將所有需要重定位的位址加上基底位址：

$$\text{實體位址} = \text{程式內相對位移} + \text{載入起始位址}$$

因此：

$$\text{I0}=0+4000=4000$$ $$\text{x}=100+4000=4100$$

載入器會將資料參照修正為：

I0: LOAD  R1, [4100]
I1: ADD   R1, 1
I2: STORE [4100], R1

若程式被載入到 $7000$，載入器便會重新計算：

核心觀念

本題考的是作業系統中的安全性違反（security violations），核心可分為：

• Confidentiality（機密性）：未授權者不應讀取的資料被讀取或揭露。
• Integrity（完整性）：資料或系統內容遭未授權修改。
• Availability（可用性）：合法使用者無法在需要時取得資料或服務。
• Theft of service（服務竊用）：未授權使用系統資源。
• Denial of service（阻斷服務）：阻止合法使用者使用系統資源或服務。

本題沒有計算式，作答重點是根據「攻擊者做了什麼」以及「誰因此受到什麼影響」進行分類。

解題方法

判斷順序如下：

1. 未授權者若是讀取或洩漏資料，屬於機密性違反。
2. 若是修改資料或程式內容，屬於完整性違反。
3. 若是刪除、破壞、停止服務或耗盡資源，使服務無法使用，屬於可用性違反。
4. 若攻擊者的重點是非法使用資源並取得使用利益，屬於服務竊用。
5. 若攻擊者的重點是讓合法使用者不能使用服務，屬於阻斷服務。

各名詞說明

名稱	定義	作業系統中的例子
Breach of confidentiality<br>機密性違反	未經授權讀取、複製或揭露資料。	使用者讀取其他使用者的檔案、密碼檔或記憶體內容；竊聽網路封包取得帳號密碼。
Breach of integrity<br>完整性違反	未經授權修改、竄改或破壞資料的正確內容。	修改其他使用者的檔案、竄改資料庫紀錄、植入被修改的執行檔。
Breach of availability<br>可用性違反	使合法使用者無法在需要時取得資料或服務；

核心觀念

本題考查作業系統的「保護（protection）」機制，重點有二：

1. 最小權限原則（Principle of Least Privilege）：主體只取得完成工作所必需的最少權限。
2. 保護域（Protection Domain）：描述某個主體可以對哪些物件執行哪些操作的權限集合。

其中：

• 主體（subject）：使用者、行程、程序或服務。
• 物件（object）：檔案、記憶體區域、裝置、資料庫或其他資源。
• 權限（right）：對物件可執行的操作，例如讀取（read）、寫入（write）、執行（execute）。

---

(a) 最小權限原則

定義

最小權限原則要求：

每一個使用者、行程或系統元件，在執行特定工作時，只能擁有完成該工作所需的最少權限，且權限的有效時間應盡可能縮短。

若主體為 $S$，完成工作所需的權限集合為 $R_{\text{required}}$，實際授予的權限集合為 $R_{\text{granted}}$，則應滿足：

$$R_{\text{granted}} \approx R_{\text{required}}$$

不應授予與工作無關的額外權限：

$$R_{\text{granted}} - R_{\text{required}} = \varnothing$$

權限示意

假設網頁服務只需要：

• 讀取公開網頁檔案；
• 將錯誤訊息附加寫入日誌檔。

則可建立如下權限表：

主體	public.html	server.log	users.db	/etc/shadow
網頁服務	讀取	附加寫入	無權限	無權限
備份服務	讀取	讀取	讀取	無權限
系統管理員	讀寫	讀寫	讀寫	讀取

網頁服務不應直接擁有整個系統的管理員權限。即使網頁服務遭到攻擊，攻擊者能利用的權限也只限於公開網頁與日誌檔，無法直接修改使用者資料或讀取密碼雜湊檔。

安全效果

最小權限原則可降低：

1. 攻擊面：可被濫用的資源與操作數量減少。
2. 損害範圍：單一行程被入侵時，攻擊者可控制的資源有限。
3. 權限誤用風險：程式錯誤不容易造成整個系統受損。
4. 內部威脅：使用者或服務無法存取與工作無關的敏感資料。

作業系統中的實現方式

常見作法包括：

• 為不同服務建立不同的系統帳號。
• 使用檔案權限、ACL 或 capability 限制資源存取。
• 程式完成初始化後立即降權（drop privileges）。
• 只有在需要時暫時取得高權限，工作完成後立即撤銷。
• 將大型服務拆成多個互相隔離、各自具有有限權限的元件。
• 使用 user mode 與 kernel mode 隔離一般程式與核心操作。

解題技巧

判斷是否符合最小權限原則時，可問：

「若移除這項權限，該主體是否仍能完成工作？」

若答案為「可以」，該權限通常就是不必要的額外權限，應予以移除。

最小權限原則不是「權限越少越好」，而是「權限剛好足以完成指定工作」。

---

(b) 保護域

定義

保護域是某一個主體在特定時間所能存取的資源，以及對每項資源可執行操作的集合。

可形式化表示為：

$$D = \{(o_1, R_1), (o_2, R_2), \ldots, (o_n, R_n)\}$$

其中：

核心觀念

本題比較三種 CPU 排程演算法：

• FCFS（First-Come, First-Served）：依到達順序執行。本題所有程序同時在時間 $0$ 到達，因此依題目列出的順序排列。
• SJF（Shortest-Job-First）：每次選擇 CPU burst time 最短的程序。所有程序同時到達，因此可直接依 burst time 由小到大排序。
• 非搶先式優先權排程：每次選擇優先權最高的程序；題目指定優先權數字越小，代表優先權越高。

由於所有程序的到達時間皆為 $0$，完成時間可由甘特圖上的累計執行時間求得。

對於程序 $P_i$：

$$Completion\ Time_i = CPU\ 執行結束的時間$$ $$Waiting\ Time_i = Completion\ Time_i - Burst\ Time_i$$

原因是所有程序的到達時間皆為 $0$，一般公式

$$Waiting\ Time_i = Completion\ Time_i - Arrival\ Time_i - Burst\ Time_i$$

可簡化為上式。

---

（a）FCFS 排程

執行順序

依題目給定順序：

$$P_1 \rightarrow P_2 \rightarrow P_3 \rightarrow P_4 \rightarrow P_5 \rightarrow P_6$$

甘特圖

$$0 \quad\ \ 8 \quad 10 \quad\ \ 14 \quad 16 \quad\ \ 24 \quad\ \ 30$$ $$|P_1|P_2|P_3|P_4|P_5|P_6|$$

完成時間與等待時間

程序	Burst Time	開始時間	完成時間	Waiting Time
$P_1$	8	0	8	0
$P_2$	2	8	10	8
$P_3$	4	10	14	10
$P_4$	2	14	16	14
$P_5$	8	16	24	16
$P_6$	6	24	30	24

平均等待時間為：

$$\frac{0+8+10+14+16+24}{6} = \frac{72}{6} = 12\text{ ms}$$

因此，各程序完成時間為：

$$P_1=8,\quad P_2=10,\quad P_3=14,\quad P_4=16,\quad P_5=24,\quad P_6=30$$

平均等待時間為：

$$\boxed{12\text{ ms}}$$

---

（b）SJF 排程

排序方式

依 Burst Time 由小到大排列：

• $P_2$：$2$
• $P_4$：$2$
• $P_3$：$4$
• $P_6$：$6$
• $P_1$：$8$
• $P_5$：$8$

相同 Burst Time 的 $P_2$、$P_4$ 及 $P_1$、$P_5$，依原題出現順序處理。

執行順序

$$P_2 \rightarrow P_4 \rightarrow P_3 \rightarrow P_6 \rightarrow P_1 \rightarrow P_5$$

甘特圖

$$0 \quad 2 \quad 4 \quad\ \ 8 \quad\ \ 14 \quad\ \ 22 \quad\ \ 30$$ $$|P_2|P_4|P_3|P_6|P_1|P_5|$$

完成時間與等待時間

程序	Burst Time	開始時間	完成時間	Waiting Time
$P_1$	8	14	22	14
$P_2$	2	0	2	0
$P_3$	4	4	8	4
$P_4$	2	2	4	2
$P_5$	8	22	30	22
$P_6$	6	8	14	8

核心觀念

本題考查 Hadoop 的兩個核心子系統：

• HDFS（Hadoop Distributed File System）：分散式儲存層，負責將大型檔案切割後分散儲存在多台機器，並提供容錯與高吞吐量存取。
• YARN（Yet Another Resource Negotiator）：叢集資源管理與應用程式執行平台，負責分配 CPU、記憶體等資源，並管理分散式應用程式。

Hadoop 的整體架構可表示如下：

使用者應用程式
      │
      ├── HDFS：儲存檔案、管理資料區塊、提供資料存取
      │
      └── YARN：管理叢集資源、啟動與監控應用程式
                    │
              各節點上的 Container

因此，HDFS 解決「資料放在哪裡、如何可靠儲存」的問題；YARN 解決「計算工作如何取得資源並執行」的問題。

解題方法

回答此題時，應分別從「架構元件」與「主要特性」說明 HDFS、YARN，最後指出兩者在 Hadoop 中的分工。

一、HDFS 的架構與主要特性

1. 主從式架構

HDFS 主要由下列元件組成：

                 Client
                /      \
       metadata操作    資料讀寫
              │          │
          NameNode    DataNode
                         │
                多台 DataNode

• NameNode：管理檔案系統的命名空間與中繼資料，例如：

  • 檔案名稱與目錄結構
  • 檔案被切成哪些資料區塊
  • 每個資料區塊儲存在哪些 DataNode
  • 檔案權限與複本資訊

• DataNode：實際儲存資料區塊，並負責：

  • 回應用戶端的讀寫要求
  • 建立、刪除與複製資料區塊
  • 定期向 NameNode 回報狀態

• Client：先向 NameNode 查詢中繼資料，再直接與 DataNode 傳輸實際檔案內容。NameNode 不負責搬運所有檔案資料，因此可避免成為資料傳輸瓶頸。

2. 區塊化儲存

HDFS 不以完整檔案為單位儲存，而是將大型檔案切割成固定大小的區塊，例如 $128\ \mathrm{MB}$ 或 $256\ \mathrm{MB}$。

若檔案大小為 $F$，區塊大小為 $B$，所需區塊數為：

$$N=\left\lceil \frac{F}{B} \right\rceil$$

每個區塊會分散儲存在不同 DataNode，使 Hadoop 能夠平行讀取與處理大型資料。

3. 複本與容錯

HDFS 通常為每個區塊建立多份複本，複本數稱為 replication factor。若區塊數為 $N$、複本數為 $r$，邏輯資料大小為 $D$，則約需：

$$rD$$

的實體儲存空間，儲存成本約為 $r$ 倍。

當某一台 DataNode 故障時，NameNode 可根據其他複本恢復資料服務，並安排新的複製工作，使複本數回到設定值。HDFS 也會採用 rack awareness，將複本分散到不同機架，避免單一機架故障造成資料全部遺失。

4. NameNode 的中繼資料管理

NameNode 主要保存檔案系統中繼資料，而檔案內容由 DataNode 保存。DataNode 會定期送出：

• Heartbeat：表示節點仍然正常運作。
• Block report：回報本機擁有哪些資料區塊。

若 NameNode 在一段時間內沒有收到某個 DataNode 的 heartbeat，便會將該節點視為故障，並重新安排遺失區塊的複製。

現代 HDFS 可使用 NameNode High Availability，由 Active NameNode 與 Standby NameNode 提供高可用性，降低單一 NameNode 故障造成整個檔案系統無法使用的風險。

5. 高吞吐量與資料區域性

HDFS 的設計目標是處理大型檔案與大量連續資料，因此特別重視吞吐量，而非單筆資料的低延遲。

Hadoop 會盡量將計算工作安排在資料所在的節點，這稱為 data locality。計算移向資料可減少網路傳輸量，提高整體效能。

6. 寫入模式與一致性

HDFS 的典型設計接近 write-once-read-many：

• 檔案通常採一次寫入、多次讀取。
• 適合批次分析與大量循序讀取。
• 不適合頻繁修改檔案中間內容的工作。
• HDFS 支援 append，但不適合一般檔案系統常見的隨機更新。

寫入檔案時，Client 先向 NameNode 取得區塊配置，再將資料透過 DataNode pipeline 傳送：

Client → DataNode 1 → DataNode 2 → DataNode 3

第一個 DataNode 收到資料後再轉送給下一個 DataNode，藉此建立多份複本。

7. HDFS 的適用性與限制

適合：

• 大型檔案
• 批次處理
• 大量循序讀取
• 需要容錯的叢集儲存

限制：

• 小檔案過多會增加 NameNode 中繼資料負擔。
• 不適合低延遲、細粒度的隨機讀寫。
• 複本機制會增加實體儲存需求。
• NameNode 的中繼資料管理仍是系統設計的重要考量。

---

二、YARN 的架構與主要特性

YARN 將「叢集資源管理」與「應用程式執行邏輯」分離，使 Hadoop 不再只能執行 MapReduce，也能支援 Spark、Tez 等不同框架。

1. 主要元件

核心觀念

本題考的是「位址繫結」（address binding）：將程式中的指令與資料，從原始程式的符號名稱，逐步對應到記憶體中的實際位址。

程式位址會經過下列轉換：

$$\text{符號位址} \longrightarrow \text{可重定位位址} \longrightarrow \text{邏輯／虛擬位址} \longrightarrow \text{實體位址}$$

其中：

• 符號位址：如變數名稱 x、函式名稱 main。
• 可重定位位址：相對於程式起始位置的偏移量。
• 邏輯／虛擬位址：CPU 執行指令時產生的位址。
• 實體位址：實際 RAM 中的位址。

位址繫結可發生在三個時期：

繫結時期	主要工作	程式能否在執行中移動
編譯時期	將符號轉為絕對位址或相對位址	絕對位址程式不能任意移動
載入時期	Loader 決定實際載入位置並進行重定位	載入後不能直接移動
執行時期	每次存取記憶體時由硬體動態轉換位址	可以移動

---

解題方法：追蹤一份程式的指令與資料

以以下程式為例：

int x = 7;
int y;

int main() {
    y = x + 1;
}

編譯器與連結器將其配置成下列相對位置：

.text：
  0x0000：LOAD  R1, [0x0100]    // 讀取 x
  0x0004：ADD   R1, 1
  0x0008：STORE [0x0104], R1     // 寫入 y

.data：
  0x0100：x = 7
  0x0104：y = 0

此處的 0x0000、0x0100、0x0104 是相對於程式映像起點的位址，不一定是 RAM 中的實體位址。

---

一、編譯時期繫結

1. 起始記憶體位置已知

若編譯時已知程式必須從實體位址 0x4000 開始，編譯器可以直接產生絕對位址：

• main 的位址：

$$0x4000 + 0x0000 = 0x4000$$

• x 的位址：

$$0x4000 + 0x0100 = 0x4100$$

• y 的位址：

$$0x4000 + 0x0104 = 0x4104$$

指令可直接產生為：

0x4000：LOAD  R1, [0x4100]
0x4004：ADD   R1, 1
0x4008：STORE [0x4104], R1

此時指令本身的位置，以及指令中所引用的資料位址，都已在編譯時期綁定完成。

缺點是：若程式實際必須載入到 0x8000，所有與位址相關的指令都必須重新編譯或重新產生。

2. 起始位置未知：產生可重定位程式

一般作業系統在編譯時不知道程式未來會被載入哪一段記憶體，因此編譯器產生可重定位程式：

LOAD  R1, [0x0100]
STORE [0x0104], R1

編譯器同時建立重定位資訊，標記哪些欄位代表位址。此時：

• 指令與資料的位置以偏移量表示。
• x 位於資料區偏移量 0x0100。
• y 位於資料區偏移量 0x0104。
• 指令中的記憶體參照尚未綁定到最終實體位址。

實務上，外部函式與變數的符號解析也常由連結器完成，因此「編譯時期」通常包含編譯與連結階段。

---

二、載入時期繫結

Loader 讀取可重定位程式，選擇一個實際載入位置。假設程式起始位址為：

$$B = 0x4000$$

對任何相對位址 $r$，Loader 以重定位基底位址 $B$ 計算實際位址：

$$P = B + r$$

因此：

• 第一個指令：

$$P_{\text{instruction}} = 0x4000 + 0x0000 = 0x4000$$

• 資料 x：

$$P_x = 0x4000 + 0x0100 = 0x4100$$

• 資料 y：

$$P_y = 0x4000 + 0x0104 = 0x4104$$

Loader 會完成下列工作：

1. 將指令複製到 0x4000 起始的記憶體區域。
2. 將資料 x 與 y 放到對應位置。
3. 將指令中的 0x0100 修改為 0x4100。
4. 將指令中的 0x0104 修改為 0x4104。
5. 修正函式指標、全域指標及其他含有位址的資料。

載入後的結果如下：

0x4000：LOAD  R1, [0x4100]
0x4004：ADD   R1, 1
0x4008：STORE [0x4104], R1

0x4100：x = 7
0x4104：y = 0

核心觀念

本題考查作業系統中的安全性違反（security violations），核心可分為：

• 機密性（Confidentiality）：資訊不能被未授權者讀取。
• 完整性（Integrity）：資訊與系統狀態不能被未授權者修改。
• 可用性（Availability）：授權使用者需要時，應能正常使用系統資源。
• 服務竊取（Theft of service）：未經授權使用系統或他人的資源。
• 阻斷服務（Denial of service, DoS）：故意阻止合法使用者使用系統服務。

判斷時，先觀察攻擊者的主要動作：讀取、修改、阻止存取、未授權使用資源。

解題方法

可將每個名詞對應到「被侵犯的目標」與「攻擊者的行為」：

名稱	被侵犯的目標	主要行為
Breach of confidentiality	資訊機密性	未授權讀取或揭露
Breach of integrity	資料與系統正確性	未授權修改、插入或刪除
Breach of availability	正常使用權	使合法使用者無法存取
Theft of service	資源使用權	未授權消耗他人或系統資源
Denial of service	服務可用性	故意癱瘓或阻塞服務

各名詞詳解

1. Breach of confidentiality：機密性遭破壞

指未經授權的使用者或程式，讀取、複製或取得原本受保護的資料，使資訊暴露給不應知道的人。

作業系統中的例子包括：

• 一般使用者讀取其他使用者權限不足的檔案。
• 惡意程式竊取密碼檔、個人資料或記憶體中的機密資訊。
• 未授權程序讀取另一個程序的資料。
• 攻擊者攔截應受保護的檔案或程序內容。

重點是「資料被不該看到的人看到」，即使資料內容尚未被修改，也已構成機密性違反。

2. Breach of integrity：完整性遭破壞

指未經授權者修改、插入、刪除資料，或改變程式與系統狀態，使資訊不再正確、可靠或符合原本的設定。

作業系統中的例子包括：

• 惡意程式修改可執行檔，使使用者執行時被植入惡意行為。
• 攻擊者竄改檔案內容、使用者權限或系統組態。
• 未授權修改資料庫中的成績、帳務或登入紀錄。
• 刪除重要檔案，使系統資料不完整。

重點是「資料或系統狀態被不該修改的人改變」。刪除檔案同時也可能造成可用性遭破壞。

3. Breach of availability：可用性遭破壞

指合法且具授權的使用者，在需要使用系統資源或服務時，無法正常取得或使用它們。

造成方式包括：

核心觀念

APT（Advanced Persistent Threat，進階持續性威脅）是指具備高度技術、資源與明確目標的攻擊者，長期且隱密地入侵特定組織的資訊系統，持續維持存取權限，進行情報竊取、監控、破壞或其他惡意活動。

APT 的重點不只是使用惡意程式，而是「攻擊者＋攻擊目標＋長期攻擊行動」所形成的完整攻擊活動：

• Advanced（進階）：攻擊者可能使用客製化惡意程式、社交工程、零時差漏洞、權限提升與橫向移動等多種技術。
• Persistent（持續性）：入侵後會建立持久化機制，例如植入後門、建立隱藏帳號、修改服務或排程工作，使攻擊者即使系統重新啟動仍能再次進入。
• Threat（威脅）：攻擊者具有明確目的、能力與資源，可能造成機密資料外洩、系統破壞或長期監控。

因此，APT 通常由國家支持的組織、情報團體或資源充足的犯罪集團發動，常見目標包括政府機關、軍事單位、研究機構、金融機構與大型企業。

解題方法

本題要求解釋名詞，作答時應採用「完整定義＋拆解關鍵字＋攻擊特徵」的方式：

1. 先指出 APT 是一種針對特定目標的長期網路入侵活動。
2. 說明 Advanced、Persistent、Threat 三個字各自代表的意義。
3. 補充典型攻擊流程，例如偵察、初始入侵、建立持久化、權限提升、橫向移動、命令與控制，以及資料竊取。
4. 說明其主要特徵是隱密、持久與具有明確目的，而非一次性的攻擊。

典型流程可表示為：

核心觀念

題目中的 Convert Channel 應按資安標準術語理解為 Covert Channel（隱蔽通道）。本題考查作業系統中的非預期資訊流，以及它與 Side-Channel Attack（側通道攻擊） 的差異。

1. Covert Channel（隱蔽通道）

隱蔽通道是指：系統原本沒有提供資料交換功能，但兩個程序仍利用共享資源傳遞資訊的非預期通道。

典型情境是高安全等級程序 $H$ 與低安全等級程序 $L$ 不得直接通訊：

$$H \rightarrow L$$

程序 $H$ 將秘密資料編碼成共享資源的狀態，程序 $L$ 再觀察該狀態並解碼。

常見例子包括：

• $H$ 佔用檔案鎖，$L$ 觀察是否能取得鎖。
• $H$ 將資料寫入磁碟，$L$ 觀察磁碟使用量。
• $H$ 填滿 CPU Cache，$L$ 透過存取時間判斷 Cache 是否命中。
• $H$ 刻意消耗 CPU，$L$ 依據執行延遲解讀訊號。

隱蔽通道可分為：

• Storage Channel：透過改變共享資源的狀態傳遞資訊。
• Timing Channel：透過改變事件發生時間或執行延遲傳遞資訊。

2. Side-Channel Attack（側通道攻擊）

側通道攻擊是指：攻擊者不直接取得程式的秘密輸出，而是量測程式執行時產生的非預期物理或系統資訊，進而推測秘密資料。

可利用的側通道包括：

• 執行時間差異
• CPU Cache 命中與失誤
• 分支預測狀態
• 記憶體存取模式
• 功率消耗
• 電磁波洩漏

例如，加密程式依據金鑰位元存取不同的記憶體位置。攻擊者量測 Cache 命中與否造成的時間差，經過多次觀察後推導出金鑰內容。此攻擊不需要加密程式主動將金鑰傳給攻擊者。

解題方法

本題可採用「定義＋運作方式＋例子＋比較」作答：

1. 先指出 Covert Channel 是利用非預期共享資源進行程序間通訊。
2. 說明 Side-Channel Attack 是從執行過程的時間、Cache 或硬體訊號推測秘密。
3. 使用 Cache 作為共同例子，再依攻擊目的區分兩者：
   • 有傳送者刻意編碼資料，屬於隱蔽通道。

核心觀念

本題要求同時達成三種安全性：

安全性	目的	主要技術
機密性 Confidentiality	防止非授權者讀取訊息	加密演算法
完整性 Integrity	偵測訊息是否遭到竄改	雜湊函數、數位簽章
不可否認性 Non-repudiation	讓寄件者無法否認曾發送訊息	數位簽章

各項功能的意義如下：

1. 機密性：加密

   對訊息 $M$ 使用金鑰 $K$ 加密：

   $C=E_K(M)$

   收件者使用對應金鑰解密：

   $M=D_K(C)$

   實務上通常使用 AES 等對稱式加密，因為速度快。

2. 完整性：雜湊函數

   使用 SHA-256、SHA-3 等抗碰撞雜湊函數計算訊息摘要：

   $h=H(M)$

   訊息只要有任何變化，重新計算出的摘要就應不同。不過，單獨傳送雜湊值並不足夠，因為攻擊者可以同時修改訊息與雜湊值。因此，摘要必須搭配 MAC 或數位簽章保護。

3. 不可否認性：數位簽章

   寄件者使用自己的私密金鑰 $SK_S$ 對摘要簽章：

   $\sigma=\operatorname{Sign}_{SK_S}(h)$

   收件者使用寄件者的公開金鑰 $PK_S$ 驗證：

   $\operatorname{Verify}_{PK_S}(\sigma,H(M))=\text{true}$

   由於數位簽章使用寄件者私密金鑰，且公開金鑰可供他人驗證，因此具備訊息來源認證、完整性驗證及不可否認性。

解題方法：混合式加密搭配數位簽章

最適合本題的做法是「先簽章，再加密」。

設寄件者為 $S$，收件者為 $R$，原始訊息為 $M$。

寄件者端

1. 計算訊息摘要：

   $h=H(M)$

2. 使用寄件者私密金鑰產生數位簽章：

   $\sigma=\operatorname{Sign}_{SK_S}(h)$

3. 產生隨機的一次性工作金鑰 $K$，將訊息與簽章組合：

   $P=M\mathbin\Vert\sigma$

4. 使用對稱式加密演算法加密內容：

   $C=E_K(P)$

   實務上可使用 AES-GCM，使加密內容同時具備額外的竄改偵測能力。

5. 使用收件者公開金鑰 $PK_R$ 加密工作金鑰：

   $C_K=E_{PK_R}(K)$

6. 傳送：

   $(C_K,C)$

其中：

核心觀念

行動惡意軟體（mobile malware）是以智慧型手機、平板等行動裝置為目標，並意圖進行未經授權或有害行為的軟體。它可能竊取個人資料與帳號憑證、監視使用者、造成財務損失，或破壞裝置與資料的正常運作，危害資訊的機密性、完整性或可用性。

解題方法

核心觀念

本題考查「應用層的端到端安全（end-to-end security）」與安全協定的分類。

端到端安全是指資料從發送端應用程式傳送到接收端應用程式的整段路徑中，只有兩端能解讀或產生有效資料，中間的路由器、交換器、代理伺服器與轉送節點只能轉送資料，無法在不被發現的情況下竊聽或竄改。

通常包含：

• 機密性（confidentiality）：中間節點無法讀取內容。
• 完整性（integrity）：資料遭竄改時能被偵測。
• 身分驗證（authentication）：確認通訊對象確實是指定的主機或使用者。
• 部分協定另提供數位簽章、不可否認性與重放攻擊防護。

依保護對象可分成兩類：

1. 通道／工作階段型協定：保護一段持續的應用程式連線，例如 TLS、HTTPS、SSH。
2. 訊息／資料物件型協定：直接保護單一訊息或檔案，即使經過多個伺服器轉送仍維持加密，例如 OpenPGP、S/MIME。

解題方法：以 HTTPS／TLS 為例

HTTPS 是 HTTP over TLS。TLS 在實作上位於應用程式與傳輸層之間，但由應用程式直接使用，因此可為 HTTP 提供應用層的安全通道。

其主要流程如下：

1. 伺服器身分驗證與金鑰協商

   瀏覽器連線至 HTTPS 伺服器時，伺服器提供由憑證機構簽發的數位憑證，證明該公開金鑰屬於指定網域。TLS 1.3 通常使用 ECDHE 協商暫時性共享秘密，並由 HKDF 導出雙方的工作階段金鑰。

2. 加密 HTTP 資料

   HTTP 請求與回應會使用協商出的對稱金鑰加密。現代 TLS 通常使用 AES-GCM 或 ChaCha20-Poly1305 這類 AEAD 演算法，同時提供加密與完整性驗證：

   $C,T=\operatorname{AEAD\_Encrypt}(K,N,M,\text{AD})$

   其中 $M$ 是原始 HTTP 資料，$K$ 是工作階段金鑰，$C$ 是密文，$T$ 是驗證標籤。接收端若發現驗證標籤不正確，就拒絕該資料，因而能偵測竄改。

3. 中間節點只能轉送

   網路中的路由器只能看到 IP 位址、封包長度與傳送時間等部分資訊，無法讀取 HTTP 內容，也無法在不被偵測的情況下修改內容。因此，瀏覽器與 HTTPS 伺服器之間形成端到端的安全通道。