臺灣博碩士論文加值系統

網路編碼仍一全新的通訊概念，不同於傳統的儲存再傳送之傳輸方式，網路編碼允許節點將收到的訊息進行編碼後才傳送出去，而此方式已在理論上被證明能為網路帶來更好的吞吐量並增加通訊頻寬的使用率，尤其在群播式的通訊中更能提升效率，為通訊領域帶來了典範的轉移。由於需求快數增長的無線網路之通訊方式本質即為群播式，網路編碼更找到大顯身手的環境，其能力和可應用之範圍遂而成為研究焦點，如：點對點傳輸、資料備份系統以及交換機制等。但也正因為網路編碼將訊息混合後再傳送的特性，使得實施網路編碼的網路環境面臨了全新的安全議題，尤其是以竄改封包內容進行破壞的拜占庭攻擊。

實施網路編碼之網路環境對於惡意節點蓄意地修改傳輸資訊所造成的錯誤極為脆弱，一個竄改後的訊息在經過與其它訊息的混合後將會影響更多節點，破壞程度便大大地增加，降低了網路傳輸的可信度。網路編碼在帶來效率提升的同時也會將錯誤的影響範圍擴散，甚至可能僅因一個錯誤而造成整體通訊的癱瘓。本研究旨在基於隨機線性網路編碼的特性，提出一分散式的惡意節點定位法，以找出實施拜占庭攻擊的惡意節點之所在位置，並隔絕這些節點以阻斷它們的攻擊。

Network coding is an elegant technique where, instead of simply relaying the packets of information they receive, the nodes of a network are allowed to combine \emph{several} packets together for transmission and this technique can be used to achieve the maximum possible information flow in a network. Recent implementations of network coding for wired and wireless environments have demonstrated its practical benefits, especially in multicast communication. Because communication in wireless environment is essentially multicast, network coding has highly attracted research attention in this field. Due to that one transmitting information is actually combination of multiple other information , network coding has variety of applications such as P2P, redundant data storage, switch and etc. However, this special characteristic also exposes network coding systems to a wide range of error attacks, especially Byzantine attacks. When some adversary nodes generate error data in the network with network coding, those erroneous information will be mixed at intermeidate nodes and thus corrupt all the information reaching a destination. In short, network coding will propagate errors.

Recent research has shown that network coding can be combined with classical cryptography for secure communication, such as using concept of ECC (error correcting code) to perform end-to-end error correction or misbehavaior detection. Nevertheless, when it comes to Byzantine attacks, these results have limited effect. In fact, unless we find out those adversary nodes and isolate them, network coding may perform much worse than pure routing in the presence of malicious nodes. Our research develops a distributed hierarchical algorithm based on random linear network coding to locate malicious nodes.

標題頁 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . i
授權書 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ii
學位考試委員會審定書 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iii
誌謝 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iv
摘要 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . v
Abstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . vi
Content . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . vii
List of Tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . x
List of Figures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xi
Chapter 1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
Chapter 2 Network Coding . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
2.1 The benefits of network coding . . . . . . . . . . . . . . . . . . . . . . . 3
vii2.2 Optimal throughput . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
2.3 Network coding in wireless networks . . . . . . . . . . . . . . . . . . . . 7
2.4 The benefit of being opportunistic . . . . . . . . . . . . . . . . . . . . . 8
Chapter 3 Security Issue of Network Coding . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
3.1 Byzantine attack in network coding . . . . . . . . . . . . . . . . . . . . 11
3.2 Error Propagation due to network coding . . . . . . . . . . . . . . . . . . 12
3.3 Existing schemes against Byzantine faults . . . . . . . . . . . . . . . . . 18
3.3.1 Misbehavior Detection . . . . . . . . . . . . . . . . . . . . . . . 19
3.3.2 End-to-end Error Correction . . . . . . . . . . . . . . . . . . . . 20
3.3.3 Network tomography with network coding . . . . . . . . . . . . 21
Chapter 4 Hierarchical Adversary Identification Algorithm for RLNC . . . . . . . . . . 24
4.1 Threat model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
4.2 System model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
Chapter 5 Analysis and Simulation Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
5.1 Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
5.1.1 Error propagation and time stamp . . . . . . . . . . . . . . . . . 32
5.1.2 Range of shifting . . . . . . . . . . . . . . . . . . . . . . . . . . 33
viii5.1.3 Overhead . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
5.2 Simulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
5.2.1 Setup environment . . . . . . . . . . . . . . . . . . . . . . . . . 35
5.2.2 Simulation results . . . . . . . . . . . . . . . . . . . . . . . . . 36
Chapter 6 Conclusions and the future works . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
6.1 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
6.2 The future works . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
Appendix A:Analysis of the Shift Scheme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50

[1] R. Ahlswede, N. Cai, S. yen Robert Li, and R. W. Yeung, “Network information flow,” IEEE Transactions on Information Theory, vol. 46, no. 4, pp. 1204–1216, 2000.
[2] S. Katti, H. Rahul, W. Hu, D. Katabi, M. M´edard, and J. Crowcroft, “Xors in the air: practical wireless network coding,” IEEE/ACM Transactions on Networking, vol. 16, pp. 497–510, 2008.
[3] H. Yao, S. Jaggi, and M. Chen, “Network coding tomography for network failures,” in Proceedings of the 29th conference on Information Communications, 2010, pp. 91–95.
[4] T. Matsuda, T. Noguchi, and T. Takine, “Survey of network coding and its applica-tions,” IEICE Transactions on Communications, vol. 94-B, pp. 698–717, 2011.
[5] S. yen Robert Li, S. Member, R. W. Yeung, and N. Cai, “Linear network coding,” IEEE Transactions on Information Theory, vol. 49, pp. 371–381, 2003.
[6] R. Koetter, M. M´edard, and S. Member, “An algebraic approach to network coding,” IEEE/ACM Transactions on Networking, vol. 11, pp. 782–795, 2003.
[7] A. Dougherty, C. Freiling, and K. Zeger, “Insufficiency of linear coding in network information flow,” IEEE Transactions on Information Theory, 2005.
[8] T. Ho, R. Koetter, M. Medard, D. R. Karger, and M. Effros, “The benefits of coding over routing in a randomized setting,” in Proceedings of 2003 IEEE International Symposium on Information Theory, 2003.
[9] S. Deb, M. M´edard, and C. Choute, “Algebraic gossip: a network coding approach to optimal multiple rumor mongering,” IEEE Transactions on Information Theory, vol. 14, pp. 2486–2507, Jun. 2006.
[10] D. Mosk-aoyama and D. Shah, “Information dissemination via network coding,” in the 2006 IEEE International Symposium on Information Theory, 2006.
[11] D. S. Lun, M. M´edard, and M. Effros, “On coding for reliable communication over packet networks,” in Proc. 42nd Annual Allerton Conference on Communication, Control, and Computing, 2004.
[12] T. Ho, B. Leong, R. Koetter, M. Medard, M. Eros, and D. R. Karger, “Byzantine modification detection in multicast networks using randomized network coding,” in the 2004 IEEE International Symposium on Information Theory, 2004, p. 143.
[13] D. Charles, K. Jain, and K. Lauter, “Signatures for network coding,” 2006 40th Annual Conference on Information Sciences and Systems, vol. 1, no. 1, pp. 3–14, Mar. 2009.
[14] M. N. Krohn, “On-the-fly verification of rateless erasure codes for efficient content distribution,” in Proceedings of the IEEE Symposium on Security and Privacy, 2004, pp. 226–240.
[15] F. R. K. Ralf Koetter, “Coding for errors and erasures in random network coding,” in IEEE Transactions on Information Theory, 2008.
[16] D. Silva, F. R. Kschischang, and R. Koetter, “A rank-metric approach to error control in random network coding,” IEEE Transactions on Information Theory, vol. 54, pp. 3951–3967, 2008.
[17] D. Silva and F. R. Kschischang, “Using Rank-Metric codes for error correction in random network coding,” in 2007 IEEE International Symposium on Information Theory, 2007, pp. 796–800.
[18] D. Silva, F. R. Kschischang, and R. K¨otter, “Capacity of random network coding under a probabilistic error model,” 24th Biennial Symposium on Communications, 2008.
[19] S. Jaggi, M. Langberg, S. Katti, T. Ho, D. Katabi, M. Medard, and M. Effros, “Re-silient network coding in the presence of byzantine adversaries,” IEEE Transactions on Information Theory, vol. 54, pp. 2596–2603, 2008.
[20] M. Coates, A. Hero, R. Nowak, and B. Yu, “Internet tomography,” IEEE Signal Processing Magazine, vol. 19, pp. 47–65, 2002.