---
title: SwarmFuzz
tags: paper
description: Paper Note
---
{%hackmd fF5VBppTTZCAXSIyr-crBQ %}


[SwarmFuzz: Discovering GPS Spoofing Attacks in Drone Swarms](https://ieeexplore.ieee.org/document/10202617) (Zheng et al., DSN 2023)

:::info
[TOC]
:::
## Introduction
* 本篇論文首先展示如何找到無人機群體的漏洞無人機進行攻擊，而漏洞稱為SPVs。
* 透過SwarmFuzz框架來調整攻擊參數攻擊無人機群體，測試無人機群系統的**受攻擊韌性**。

本文透過上述兩種方式對無人機群體作攻擊，作者提出，由於上述演算法並非針對無人機本身做攻擊而是針對群體移動演算法中的漏洞做欺騙，因此此攻擊手法**不容易被檢測**。

<span class="light r">🚨 現今技術**主要面臨的挑戰**:</span>

* 若無人機群體數量大，難以快速高效率的找到易受攻擊的無人機目標組合。
* 此外，目前模糊測試技術主要用來測試記憶體非法攻擊，較少用於測試無人機GPS欺騙攻擊。

<span class="light b">🚩 本文的**主要目標**:</span>

1. 找出**最具影響力的無人機作為目標無人機**，**距離障礙物最近的無人機作為受害無人機**。
1. 為了有效地造成碰撞，攻擊者應該找使受害無人機與**障礙物之間距離最小化的GPS欺騙參數**。

<span class="light">✔ 本文的**主要貢獻**:</span>

1. 提出了 SVG 概念，並利用中心性分析找出**可能導致碰撞的無人機配對**。
1. 設計了SwarmFuzz，一種使用SVG和梯度優化來有效找出**可能導致碰撞的SPV**。
1. 在一個流行的無人機群體控制演算法上做**SwarmFuzz的測試及評估**。
## Background and Threat Model
### Background
無人機群的控制演算法通常可分為**分散式**或是**集中式**。而集中式的方法通常容易因為單點故障而導致群體故障，<span class="light y">因此本文專注於探討**分散式群體控制演算法**</span>。

<span class="light b">分散式的**無人機群控制演算法**分為4步驟:</span>

1. **讀取階段**:每個集群成員讀取感測器數據（例如GPS、IMU）以獲取其目前的物理狀態（例如位置、速度）。
2. **訊息交換**:集群成員之間通過通信系統進行消息交換，交換物理狀態。
3. **距離計算**:每個無人機群體中的成員相互計算狀態差異（例如相對距離、相對速度）。
4. **無人機控制演算法**:根據各自無人機狀態與距離計算的結果各自透過演算法產生各自飛行控制命令。

<span class="light b">上述的**無人機群體控制演算法**有三個主要目標:</span>
1. **以任務為導向**，確保無人機群**向目的地移動**。
1. **確保無人機不會碰撞上障礙物**，透過保持無人機/障礙物之間的距離來確保無碰撞。
1. **保持一致的形態**，盡可能的聚合無人機群，**避免過於分散**。

因此，無人機中生成的最終控制命令主要包含三個子命令，每個子命令對應一個特定目標。群體控制算法中的一個關鍵組件是通過細致調整來平衡這些潛在衝突的目標。例如，在無人機到達目的地的路徑上有障礙物時，群體控制算法需**賦予目標（1）和（2）更高的權重**，以確保無人機向目的地移動同時避開障礙物。

### Threat Model
* **在GPS偽造攻擊**，攻擊者以比原始GPS信號更強的功率發射偽造的GPS訊號，使受害者的GPS接收器鎖定到攻擊者的訊號上。

⚙**論文中的威脅模型**:

假設攻擊者只能對無人機群中的**一個成員進行GPS欺騙攻擊**，相較於對多個無人機進行GPS欺騙攻擊需要更少的攻擊力量，並且使得攻擊更加隱蔽。

<span class="light r">攻擊者的目標是使一個**群體成員與預定路徑上的障礙物碰撞**。</span>

## Motivation Example and Challenges
本文首先展示一個高效率的群體控制算法，接著介紹了系統地尋找SPV所面臨的設計挑戰。

### Motivating example
在Swarm-lab 模擬器中模擬了一個由5個無人機組成的群集，用於執行任務。


* **圖(a)** 目標是到達預定的**目的地（旗幟）**，同時避開路徑上的**障礙物（紫色三角形）**。

圖中無人機5從右側避開障礙物。

* **圖(b)** 無人機群體間控制關係
* <span class="light b">**藍色箭頭**:每個無人機都有一個**朝目的地移動**的子速度。</span>
* <span class="light o">**橘色箭頭**:由於無人機1和無人機2之間的距離很短，將生成**相互排斥**的子速度</span>
* <span class="light">**綠色箭頭**:由於無人機1和無人機5之間的距離相對較長，無人機之間生成**相互吸引**的子速度。</span>

由於這些對應的速度可能**彼此衝突**，攻擊者可利用此點發起GPS欺騙攻擊，使目標無人機誤判位置並將其與群體通訊。這種誤差改變了目標無人機和受害無人機之間的相對距離，導致群體控制演算法產生不正確的控制指令，使受害無人機偏離航線，進而導致碰撞。

* 🎈 **Example** : 在圖( c )中，無人機4（目標無人機）受到GPS欺騙攻擊，向右偏。這種偏離增加了無人機4和無人機5（受害無人機）之間的間距，使無人機群體無法維持聚集。因此，根據無人機群體控制演算法目標（3），無人機4和無人機5之間會產生相互吸引的子速度（即綠色箭頭）。這個新的子速度，無人機5的整體速度（即紅色箭頭）指向障礙物，從而導致碰撞。根據目標（2），無人機5還具有避開障礙物的子速度。然而，由於其他目標生成的子速度大於避開障礙物的子速度，無人機5會飛向障礙物並與之碰撞，從而違反了群體的安全限制。

### Design Challenges
開發一種自動化方法來系統地且高效地尋找無人機群集中的SPV非常重要。

尋找無人機群集中的SPV將面臨兩個獨特的挑戰:
1. <span class="light">**尋找目標-受害者配對**</span> : 為了利用SPVs並發動悄無聲息的攻擊，需要戰略性地選擇合適的目標-受害者無人機配對。這是因為在大型無人機群中，可能的目標-受害者無人機配對的組合數量非常龐大，導致輸入空間非常大。

3. <span class="light b">**選擇欺騙參數**</span> : 進行GPS欺騙攻擊涉及兩個關鍵參數，即**欺騙方向**和**欺騙時間**。欺騙方向指的是目標無人機在GPS欺騙下偏離的方向（例如，右邊、左邊），而欺騙時間則是指GPS欺騙攻擊持續的時間長度。在目標無人機中選擇錯誤的欺騙參數（即方向和時間）將使受害無人機避免碰撞，從而達到攻擊的目的。

## Methodology
**SwarmFuzz 接受兩個輸入**:
1. 群體控制算法。
1. 任務參數（包括群體大小和位置）。

**SwarmFuzz 進行分為三個步驟**：
1. <span class="light">**初始測試**</span> : 在沒有任何攻擊的情況下進行初始測試。如果這個測試任務成功（即無碰撞），它將記錄任務訊息以**建立 Swarm Vulnerability Graph（SVG）**。
2. <span class="light b">**對SVG進行中心性分析**</span> : 分析每個具有特定偽造方向的無人機的影響，並使用此訊息來決定選擇目標-受害無人機對進行測試的順序（C1）。
3. <span class="light o">**找出攻擊參數**</span> : 對於具有特定偽造方向的目標-受害無人機對，它使用梯度優化搜尋最小化受害無人機與障礙物之間距離的偽造參數（**起始時間、持續時間**）。重複步驟（3），直到發生碰撞或達到預定的搜索迭代次數。如果發生碰撞，SwarmFuzz就找到了成功的SPV，並輸出目標-受害無人機對以及碰撞的偽造參數。否則，SwarmFuzz報告在任務中沒有發現SPV，並且這個任務對SPV具有抵抗能力。

### Test Definition and Initial Test Creation
<span class="light">**< T−V，ts，Δt，θ >**</span>

* T−V表示目標-受害者無人機對。
* ts表示欺騙開始時間。
* Δt表示欺騙持續時間。
* θ表示欺騙方向(僅分為左右 +1/-1)。

**系統將持續收集以下訊息：**
* 每個無人機i在每個時間點tj的位置（xi，yi，zi），即< xi，yi，zi，tj >。
* 任務期間每台無人機與障礙物之間的最小距離。
* 整體任務持續時間。

### Seed scheduling

**🔺 Def** : <span class="light o">**SVG = (N,E,W)**</span>
* N代表無人機群成員的節點集合。
* E是無人機之間連接的邊的集合。
* W是衡量每個無人機對其他無人機影響的權重集合。

<span class="light r">**最終產生的SVG是一個有向圖，邊的方向模擬影響的來源。**</span>

**💡 Goal** : <span class="light">**尋找目標-受害者配對**</span>

* 測量每個目標-受害無人機對的**惡意影響程度**。
* 選擇**影響程度**最大的無人機對進行攻擊測試。
* 然後利用圖論的**中心性分析來測量SVG中每個成員的影響力 **建構**Swarm Vulnerability Graph（SVG )** 圖。
* 選擇**影響力最大的成員作為目標無人機**，與**距離障礙物最近的無人機作為受害無人機**，以便按照影響程度的**遞減順序**來排序測試用的種子。


作者觀察到當<span class="light">**無人機彼此靠近時**，無人機成員之間的**影響最強烈**</span>。因此提出了一個計算SVG的方法 :

* 首先透過< xi，yi，zi，tj >**計算任務執行期間無人機成員間的平均距離。**
* 找到具有**最短平均距離的時間t**，並在t時使用群體的位置< xi，yi，zi，tclo > 建立 SVG。
* 分析當另一個無人機2在t時受到GPS欺騙時，無人機1的**速度改變方向**。
* 如果無人機1受到無人機2的惡意影響（即更靠近障礙物），創建一個Edge_e12。
* 最後，根據無人機i和無人機j之間的距離計算權重wij。

在SVG中，**只有在無人機j對無人機i具有惡意影響時，才添加Edge_eij**，<span class="light b">如果無人機j的欺騙偏差導致**無人機i和障礙物之間的距離減小**，則**無人機j對無人機i具有惡意影響**。<span>

🎈 <span class="light y"> **Computing Weights in the SVG** </span>

**Wij計算 : 無人機i和j之間的直角三角形的角α的 Cosine 值。**

**🚩 Centrality Analysis** : <span class="light">**PageRank**</span>
* **PageRank**可以適用於大型圖形計算。
* 如果某無人機可以造成更多成員受到惡意影響，**PageRank** 會將**無人機影響力會增加**。
* 如果某兩台無人機之間無法直接互相影響，**PageRank** 會將其**影響力會減小**。

✨**PageRank 參考資料** : https://towardsdatascience.com/pagerank-algorithm-fully-explained-dc794184b4af

**🚩 Seed Scheduling**
每台無人機遭受碰撞的機率取決於:
* 無人機 T − V 的影響分數。
* 無人機與障礙物之間距離 ( VDO )。

**Seed Scheduling** 根據VDO的遞增順序對每個受害無人機進行排序; 接著計算每對無人機組合的影響力總和；最後，對於每個受害無人機v，選擇具有最高總和影響力的無人機對應的目標無人機。

<span class="light r"> **缺舉例**

### Search-Based Fuzzing

💡 **找到適當的偽造參數（ts和Δt）**
* **ts : GPS欺騙攻擊的開始時間**
* **Δt : 欺騙攻擊的進行時間**


**優化問題 - 找到最小化目標函數f(ts, Δt) 使<span class="light ">受害無人機與障礙物之間的距離 < 0</span> 且 <span class="light o"> ts + Δt < tmission ( 無人機任務執行時間 )**。</span>

（圖(b)）。偽造時間過短Δt1會使它從左側錯過障礙物
（圖\(c)）。當時間增加到Δt2（圖5-\(c)）時，它導致碰撞。
（圖(d)）如果偽造時間過長並增加到Δt3，受害無人機會從右側避開障礙物。

因此，我們需要找到既不太短也不太長的偽造時間以造成碰撞。梯度引導優化。由於目標函數是凸函數，我們使用梯度引導搜索來高效地找到最優解。我們（1）計算目標函數f(ts, Δt)的偏導數，即∂f/∂ts和∂f/∂Δt；（2）根據方程1a更新偽造參數ts，並根據方程1b更新Δt。
lr代表學習率，用於縮放輸入更新，從而增強搜索速度。我們將ts和Δt的值限制為正數，因為時間不能為負。對於種子池中的每對目標-受害無人機種子，SwarmFuzz重複上述梯度引導搜索過程。如果發生碰撞，SwarmFuzz報告成功找到了SPV，並輸出< T − V, θ, ts, Δt >。然而，如果在最大搜索迭代次數內（以經驗設置 - 第V-A節），沒有發生碰撞，SwarmFuzz放棄當前種子，轉而處理種子池中的下一個種子。

## Evaluation