臺灣博碩士論文加值系統

本論文探討大規模無線感測網路中，攻擊者入侵感測器並偽造傳輸資料的問題。在未來物聯網生態中，大規模無線感測網路為一關鍵技術，應用層面廣泛。無線感測網路通常包含許多感測器及一訊息彙整中心。感測器偵測周圍狀況後，將偵測結果壓縮，透過無線通道傳輸至訊息彙整中心，並由訊息彙整中心整合所有訊息做出最終判斷。然而，無線感測器多處於開放或公共環境中，缺乏物理保護，同時無線訊號易受雜訊及干擾影響，因此無線感測網路具有易出錯或受到入侵的弱點。其中一種針對無線感測網路的惡意入侵稱為Byzantine攻擊，在Byzantine攻擊中，攻擊者入侵感測器並傳送偽造之訊息至訊息彙整中心，試圖誤導訊息彙整中心使之做出錯誤的判斷。與一般通道錯誤相比，具有針對性的攻擊所造成的系統損失往往較為嚴重，而本研究之目的即為設計對抗攻擊之感測演算法。

近年來已有許多研究探討在無線感測網路中之偽造訊息攻擊。在閱讀相關文獻後，我們發現多數研究所使用之數學模型假設每一感測器在每次傳送中均有同樣之機率成為被入侵之感測器，並傳送偽造訊息。然而，此假設與現況不盡相符，因此我們提出了修正之機率模型來描述遭受入侵的無線感測網路，並以複合假設檢定探討此攻擊問題。我們參考了W. Hoeffding於1965年對於複合假設檢定問題的研究成果，依照我們所提出之問題模型進行修改，得到了Hoeffding-type偵測演算法。對於Hoeffding-type演算法，我們提出了理論效能分析，並討論當訊息彙整中心對於攻擊資訊的認知不完全時，此演算法之表現。

訊息彙整中心能夠以兩種不同模式應用偵測演算法進行防禦：
1. 直接偵測(Direct Detect)：訊息彙整中心沒有任何關於被入侵感測器身份之信息，直接彙整所有訊息。
2. 分組後偵測(Clustering and Detect)：訊息彙整中心具有除了感測器訊息以外的額外資訊，並能夠利用此資訊辨識受入侵之感測器，並將感測器分為兩組。針對兩組感測器，訊息彙整中心分別進行偵測並整合兩組之結果。

由於分組後偵測模式與直接偵測相比具有額外之資訊幫助，分組後偵測模式所能達到的效能較佳，也能夠避免感測網路因入侵而失去功能，除非所有感測器均被入侵。

In this thesis, we study the problem of Byzantine attacks in large scale wireless sensor networks (WSNs). WSN is a critical technology in the future Internet of Things era, supporting various applications such as smart home, environmental monitoring, Internet of vehicles, etc. A WSN generally consists of some sensors and a fusion center (FC). Each sensor makes an observation about a phenomenon of interest, and transmits local message to the FC, who then makes a final decision based on those messages. Due to the exposed nature of the sensors and the characteristics of wireless channel, WSN is prone to be attacked and faulty. One of the attacks against WSN is called the Byzantine attack, which the attacker compromises some sensors and sends falsified messages to the FC. Unlike channel errors caused by noise or interference, Byzantine attack is targeted and may be more harmful to the system. It''s thus an important and challenging goal to design a robust system that is immune to the attack, and this is the purpose of our research.

The effect of Byzantine attack has been studied a lot in recent years, however, many works formulate it as a simple hypothesis testing problem by assuming each sensor being independently compromised with probability alpha_t, where alpha_t is the fraction of Byzantine sensors. We call this model the i.i.d. mixture model since the local messages are i.i.d. to a mixture distribution. It''s easy to obtain the optimal error exponent in this problem formulation, however, we are not satisfied with the model since in practice it''s unlikely an attacker randomly attack the sensors each time. To fix this assumption, we introduce a parameter that indicates the indices of compromised sensors and formulate the Byzantine attack as a composite hypothesis testing problem.

Using the idea of Hoeffding test in conventional composite hypothesis testing, we propose a "Hoeffding-type test''. The Hoeffding-type test depends only on the type of local messages, and achieves an error exponent which is the same as the optimal exponent in i.i.d. mixture model. We also show that it''s easy to generalize the Hoeffding-type test so that it becomes universal over all possible attack distributions. Since Hoeffding-type test only uses the type information, we further propose an "Order-aware Hoeffding-type test''. In the order-aware test, we perform joint detection of the indices parameter and the underlying hypothesis by brute-force search. Although the order-aware test seems to be using more information than the Hoeffding-type test, we show that they are equivalent in the asymptotic regime.

The proposed detect algorithms can be applied in two kinds of defense scheme:
1. Direct Detect: FC has no information on the identities of Byzantine sensors and performs detection with all local messages
2. Clustering and Detect: FC will first identifies the Byzantines and clusters the sensors into two groups through some side information. For each group, independent detection is performed then results from both groups are combined using 0-AND rule.

We show that the Clustering Detect scheme performs better than Direct Detect scheme, and FC can''t be blinded unless all sensors are compromised. Finally, some numerical results are presented to compare the two defense scheme.

誌謝 iii
摘要 v
Abstract vii

1 Introduction 1
1.1 Motivation 1
1.2 Related Works 5
1.3 Thesis Organization 6
1.4 Notations and Abbreviations 7

2 Background 11
2.1 Information Theoretic and Probabilistic Tools 11
2.1.1 Kullback-Leibler Divergence 11
2.1.2 Method of Types 12
2.1.3 Convergence of Empirical Distributions 13
2.2 Hypothesis Testing (Centralized Detection) 13
2.2.1 Simple Binary Hypothesis Testing 14
2.2.2 Composite Hypothesis Testing 17
2.2.3 Centralized Detection 19
2.3 A Model of Wireless Sensor Networks (Decentralized Detection) 19
2.3.1 Problem Formulation 20
2.4 A Model of WSN with Byzantine Attacks 21
2.4.1 i.i.d. Mixture Model 21
2.4.2 Byzantine Attacks Schemes 23
2.4.3 Optimal Attack Distributions and Blinding Power 25

3 Decentralized Detection with Byzantine Attack - Direct Detect Defense Scheme and Hoeffding-type Test 29
3.1 Introduction 29
3.2 Problem Formulation 30
3.2.1 WSN with Byzantine Attack Model 30
3.2.2 Two Defense Schemes 33
3.2.3 Neyman-Pearson Formulation in the Composite Hypothesis Framework 34
3.3 Preliminaries 35
3.3.1 Ideas from the Conventional Hoeffding Test 35
3.3.2 Convergence of the Type of Local Messages 35
3.3.3 Rare Event Probability of Local Messages 37
3.4 Hoeffding-type Test 39
3.4.1 Proof of Result 40
3.5 Universal Hoeffding-type Test 41
3.5.1 Proof of Result 43
3.5.2 Imperfect Knowledge of Attack Power 44
3.5.3 Summary of the Test: An Information Geometrical Interpretation 47
3.6 Can We Do Better Than the Hoeffding-type Test? 49
3.6.1 Order-aware Hoeffding Type Test 50
3.6.2 Discussion 51

4 Byzantine Identification by Anchor Sensor 53
4.1 Problem Formulation 54
4.2 Byzantine Identification Algorithm (Hamming Distance Based) 55
4.2.1 Performance under Different Window Length T 57
4.2.2 The Role of Anchor Sensor 59
4.2.3 Numerical Evaluation 60
4.3 A Revised Byzantine Identification Algorithm (Type Based) 61
4.3.1 Introduction 61
4.3.2 Performance Analysis and Numerical Evaluation 62
4.4 Other Possible Identification Methods Utilizing an Anchor Sensor 63

5 Clustering and Detect Defense Scheme 65
5.1 Introduction 65
5.2 Clustering and Detect Scheme 66
5.2.1 Clustering 66
5.2.2 Detect 67
5.3 Perfect Side Information Case 69
5.4 Noisy Side Information Case: Identification by Anchor Sensor 70
5.4.1 Clustering Using Byzantine Identification Algorithm 71
5.4.2 Design of Intermediate Tests 71
5.4.3 Proof of Result 74
5.5 Strategic Game Between the Byzantines and Fusion Center 76
5.6 Numerical Results 78

6 Conclusion 81
6.1 Summary 81
6.2 Generalization of Results 82
6.3 Future Work 83

Bibliography 85

[1] I. F. Akyildiz, W. Su, Y. Sankarasubramaniam, and E. Cayirci, “A survey on sensor networks,” IEEE Communication Magazine, August 2002.

[2] J. Yick, B. Mukherjee, and D. Ghosal, “Wireless sensor network survey,” Computer Networks, 2008.

[3] A. Al-Fuqaha, M. Guizani, M. Mohammadi, M. Aledhari, and M. ayyash, “Internet of things: A survey on enabling technologies, protocols, and applications,” IEEE Communication Surveys and Tutorials, vol. 17, no. 4, 2015.

[4] R. R. Tenny and N. R. Sandell, “Detection with distributed sensors,” IEEE Transactions on Aerospace and Electronic Systems, 1981.

[5] J. N. Tsitsiklis, “Decentralized detection by a large number of sensors,” Mathematics of Control, Signals and Systems, vol. 1, 1988.

[6] G. Polychronopoulos and J. N. Tsitsiklis, “Explicit solutions for some simple decentralized detection problems,” IEEE Transactions on Aerospace and Electronic Systems, vol. 26, no. 2, 1990.

[7] T.-Y. Wang, Y. S. Han, P. K. Varshney, and P.-N. Chen, “Distributed fault-tolerant classification in wireless sensor networks,” IEEE Journal on Selected Areas in Communications, vol. 23, no. 4, pp. 724–734, 2005.

[8] L. Lamport, R. Shostak, and M. Pease, “The byzantine generals problem,” AMC Transactions on Programming Languages and Systems, vol. 4, July 1982.

[9] S. Marano, V. Matta, and L. Tong, “Distributed detection in the presense of byzantine attacks,” IEEE Transactions on Signal Processing, vol. 57, January 2009.

[10] B. Kailkhura, Y. S. Han, S. Brahma, and P. K. Varshney, “Asymptotic analysis of distributed bayesian detection with byzantine data,” IEEE Signal Processing Letters, vol. 22, May 2015.

[11] B. Kailkhura, Y. S. Han, S. Brahma, and P. K. Varshney, “Distributed bayesian detection in the presence of byzantine data,” IEEE Transactions on Signal Processing, vol. 63, October 2015.

[12] M. Barni and B. Tondi, “The source identification game: An information-theoretic perspective,” IEEE Transactions on Information Forensics and Security, 2013.

[13] B. Tondi, M. Barni, and N. Merhav, “Detection games with a fully active attacker,” IEEE International Workshop on Information Forensics and Security, 2015.

[14] T. M. Cover and J. A. Thomas, Elements of Information Theory. Wiley-Interscience, 2nd ed., 2006.

[15] P. Billingsley, Probability and Measure. John Wiley and Sons, third ed., 1995.

[16] I. H. Wang, Lecture Notes on Information Theory. 2016.

[17] Y. Polyanskiy and Y. Wu, Lecture Notes on Information Theory. 2016.

[18] W. Hoeffding, “Asymptotically optimal tests for multinomial distributions,” The Annals of Mathematical Statistics, vol. 36, no. 2, 1965.

[19] B. Kailkhura, Y. S. Han, S. Brahma, and P. K. Varshney, “On convert data falsification attacks on distributed detection system,” International Symposium on Communications and Information Technologies, 2013.

[20] L. Zhang, G. Ding, Q. Wu, Y. Zou, Z. Han, and J. Wang, “Byzantine attack and defense in cognitive radio networks: A survey,” IEEE Communication Surveys and Tutorials, vol. 17, no. 3, 2015.