| | This Article | |
| |
| |
| | Share | |
| |
| |
| | Bibliographic References | |
| |
| |
| | Add to: | |
| |
 Digg
 Furl
 Spurl
 Blink
 Simpy
 Google
 Del.icio.us
 Y!MyWeb
| |
| | Search | |
| |
| |
| | |
Detecting and Isolating Malicious Routers
July-September 2006 (vol. 3 no. 3)
pp. 230-244
Network routers occupy a unique role in modern distributed systems. They are responsible for cooperatively shuttling packets amongst themselves in order to provide the illusion of a network with universal point-to-point connectivity. However, this illusion is shattered—as are implicit assumptions of availability, confidentiality, or integrity—when network routers are subverted to act in a malicious fashion. By manipulating, diverting, or dropping packets arriving at a compromised router, an attacker can trivially mount denial-of-service, surveillance, or man-in-the-middle attacks on end host systems. Consequently, Internet routers have become a choice target for would-be attackers and thousands have been subverted to these ends. In this paper, we specify this problem of detecting routers with incorrect packet forwarding behavior and we explore the design space of protocols that implement such a detector. We further present a concrete protocol that is likely inexpensive enough for practical implementation at scale. Finally, we present a prototype system, called Fatih, that implements this approach on a PC router and describe our experiences with it. We show that Fatih is able to detect and isolate a range of malicious router actions with acceptable overhead and complexity. We believe our work is an important step in being able to tolerate attacks on key network infrastructure components.
[1] 230 X. Ao, “Report on DIMACS Workshop on Large-Scale Internet Attacks,” Sept. 2003, http://dimacs.rutgers.edu/Workshops/Attacks internet-attack-9-03.pdf.[2] K.J. Houle, G.M. Weaver, N. Long, and R. Thomas, “Trends in Denial of Service Attack Technology,” CERT Coordination Center, technical report, Oct. 2001, http://www.cert.org/archive/pdfDoS_trends.pdf .[3] C. Labovitz, A. Ahuja, and M. Bailey, “Shining Light on Dark Address Space,” Arbor Networks, technical report, Nov. 2001, http://research.arbornetworks.com/downloads/ research38 dark_address_space.pdf.[4] R. Thomas, “ISP Security BOF, NANOG 28,” June 2003, http://www.nanog.org/mtg-0306/pdfthomas.pdf .[5] Gauis, “Things to Do in Ciscoland When You're Dead,” Jan. 2000, http://www.phrack.org/phrack/56/p56-0x0a.org/ phrack/56p56-0x0a.[6] D. Taylor, “Using a Compromised Router to Capture Network Traffic,” unpublished technical report, July 2002, http://www.netsys.com/library/papersGRE_sniffing.PDF .[7] A.P. Kosoresow and S.A. Hofmeyr, “Intrusion Detection via System Call Traces,” IEEE Software, vol. 14, no. 5, pp. 35-42, 1997.[8] K. Jain and R. Sekar, “User-Level Infrastructure for System Call Interposition: A Platform for Intrusion Detection and Confinement,” Proc. Network and Distributed Systems Security Symp., 2000.[9] T. Garfinkel, “Traps and Pitfalls: Practical Problems in System Call Interposition Based Security Tools,” Proc. Network and Distributed Systems Security Symp., Feb. 2003.[10] A.T. Mizrak, Y.-C. Cheng, K. Marzullo, and S. Savage, “Fatih: Detecting and Isolating Malicious Routers,” DSN '05: Proc. 2005 Int'l Conf. Dependable Systems and Networks (DSN '05), pp. 538-547, 2005.[11] R. Perlman, “Network Layer Protocols with Byzantine Robustness,” PhD dissertation, MIT LCS TR-429, Oct. 1988.[12] L. Subramanian, V. Roth, I. Stoica, S. Shenker, and R. Katz, “Listen and Whisper: Security Mechanisms for BGP,” Proc. Symp. Networked Systems Design and Implementation, Mar. 2004.[13] S. Kent, C. Lynn, J. Mikkelson, and K. Seo, “Secure Border Gateway Protocol (Secure-BGP),” IEEE J. Selected Areas in Comm., vol. 18, no. 4, pp. 582-592, Apr. 2000.[14] Y.-C. Hu, A. Perrig, and D.B. Johnson, “Ariadne: A Secure On-Demand Routing Protocol for Ad Hoc Networks,” Proc. Eighth ACM Int'l Conf. MobiCom, Sept. 2002.[15] B.R. Smith and J. Garcia-Luna-Aceves, “Securing the Border Gateway Routing Protocol,” Proc. Global Internet '96, 1996.[16] S. Cheung, “An Efficient Message Authentication Scheme for Link State Routing,” Proc. Ann. Computer Security Applications Conf., pp. 90-98, 1997.[17] M.T. Goodrich, “Efficient and Secure Network Routing Algorithms,” provisional patent filing, Jan. 2001.[18] Y. Cosendai, M. Dacier, and P. Scotton, “Intrusion Detection Mechanism to Detect Reachability Attacks in PNNI Networks,” Recent Advances in Intrusion Detection, 1999.[19] Y. Jou, F. Gong, C. Sargor, X. Wu, S. Wu, H. Chang, and F. Wang, “Design and Implementation of a Scalable Intrusion Detection System for the Protection of Network Infrastructure,” Proc. DARPA Information Survivability Conf. & Exposition, vol. 2, pp. 69-83, 2000.[20] R. Perlman, Interconnections: Bridges and Routers. Addison Wesley Longman Publishing Co. Inc., 1992.[21] V.N. Padmanabhan and D. Simon, “Secure Traceroute to Detect Faulty or Malicious Routing,” SIGCOMM Comp. Comm. Rev., vol. 33, no. 1, pp. 77-82, 2003.[22] I. Avramopoulos, H. Kobayashi, R. Wang, and A. Krishnamurthy, “Highly Secure and Efficient Routing,” Proc. INFOCOM Conf., Mar. 2004.[23] I. Avramopoulos, H. Kobayashi, R. Wang, and A. Krishnamurthy, “Amendment to: Highly Secure and Efficient Routing,” amendment, Feb. 2004.[24] S. Cheung and K. Levitt, “Protecting Routing Infrastructures from Denial of Service Using Cooperative Intrusion Detection,” Proc. New Security Paradigms Workshop, 1997.[25] K.A. Bradley, S. Cheung, N. Puketza, B. Mukherjee, and R.A. Olsson, “Detecting Disruptive Routers: A Distributed Network Monitoring Approach,” Proc. IEEE Symp. Security and Privacy, pp. 115-124, May 1998.[26] J.R. Hughes, T. Aura, and M. Bishop, “Using Conservation of Flow as a Security Mechanism in Network Protocols,” Proc. IEEE Symp. Security and Privacy, pp. 132-131, 2000.[27] A. Herzberg and S. Kutten, “Early Detection of Message Forwarding Faults,” SIAM J. Computing, vol. 30, no. 4, pp. 1169-1196, 2000.[28] A. Shaikh, C. Isett, A. Greenberg, M. Roughan, and J. Gottlieb, “A Case Study of OSPF Behavior in a Large Enterprise Network,” IMW '02: Proc. Second ACM SIGCOMM Workshop Internet Measurment, pp. 217-230, 2002.[29] D. Watson, F. Jahanian, and C. Labovitz, “Experiences with Monitoring OSPF on a Regional Service Provider Network,” ICDCS '03: Proc. 23rd Int'l Conf. Distributed Computing Systems, p. 204, 2003.[30] Cisco Systems, “Load Balancing with Cisco Express Forwarding,” http://www.cisco.com/warp/public/cc/pd/ifaa/ pa/much/prodlitloadb_an.pdf, 2006.[31] Juniper Networks, “JUNOS 6.4 Routing Protocols Configuration Guide,” http://www.juniper.net/techpubs/software/ junos/junos64/swconfig64-routinghtml/, 2006.[32] R. Teixeira, K. Marzullo, S. Savage, and G.M. Voelker, “In Search of Path Diversity in ISP Networks,” Proc. ACM/SIGCOMM IMC, pp. 313-318, 2003.[33] J. Bellardo and S. Savage, “Measuring Packet Reordering,” Proc. ACM SIGCOMM Internet Measurement Workshop (IMW '02), 2002.[34] J.C. R. Bennett, C. Partridge, and N. Shectman, “Packet Reordering Is Not Pathological Network Behavior,” IEEE/ACM Trans. Networking (TON), vol. 7, no. 6, pp. 789-798, 1999.[35] G. Almes, S. Kalidindi, and M. Zekauskas, “A One-Way Packet Loss Metric for IPPM,” RFC 2680, IETF, Sept. 1999.[36] D. Pullin, A. Corlett, B. Mandeville, and S. Critchley, “Packet Reordering: The Minimal Longest Ascending Subsequence Metric,” Feb. 2002, http://www.globecom.net/ietf/draftdraft-critchley-mlas-reordering-00.txt .[37] A. Morton, L. Ciavattone, G. Ramachandran, S. Shalunov, and J. Perser, “Packet Reordering Metric for IPPM,” Mar. 2003, http://www.globecom.net/ietf/draftdraft-ietf-ippm-reordering-00.txt .[38] Cisco Systems, “Detecting and Analyzing Network Threats with NetFlow,” http://www.cisco.com/univercd/cc/td/doc/ product/software/ios124/124tcg /tnf_c/ch15 nfhtdt.pdf, 2006.[39] B.H. Bloom, “Space/Time Trade-Offs in Hash Coding with Allowable Errors,” Comm. ACM, vol. 13, no. 7, pp. 422-426, July 1970.[40] Y. Minsky, A. Trachtenberg, and R. Zippel, “Set Reconciliation with Nearly Optimal Communication Complexity,” Proc. Int'l Symp. Information Theory, p. 232, June 2001.[41] “Communications Assistance for Law Enforcement Act of 1994,” pub. L. No. 103-414, 108 Stat. 4279, 103rd Congress of the United States of Am.[42] S. Hanks, T. Li, D. Farinacci, and P. Traina, “Generic Routing Encapsulation GRE,” RFC 1701, IETF, Oct. 1994.[43] T.D. Chandra and S. Toueg, “Unreliable Failure Detectors for Reliable Distributed Systems,” J. ACM, vol. 43, no. 2, pp. 225-267, 1996.[44] A.T. Mizrak, K. Marzullo, and S. Savage, “Detecting Malicious Routers,” Univ. of California ay San Diego, technical report CS2004-0789, 2004, http://www.cs.ucsd.edu/Dienst/UI/2.0/Describe/ ncstrl.ucsd_cseCS2004-0789.[45] J. Black, S. Halevi, H. Krawczyk, T. Krovetz, and P. Rogaway, “UMAC: Fast and Secure Message Authentication,” Lecture Notes in Computer Science, vol. 1666, pp. 216-233, 1999.[46] GNU Zebra, http:/www.zebra.org, 2006.[47] J.T. Moy, “OSPF version 2,” RFC 2328, IETF, Apr. 1998.[48] D.L. Mills, “Network Time Protocol (version 3) Specification, Implementation,” RFC 1305, IETF, Mar. 1992.[49] Abilene Network, http:/abilene.internet2.edu/, 2006.[50] User Mode Linux, http:/user-mode-linux.sourceforge.net/, 2006.[51] P. Rogaway, “UMAC Performance (More),” www.cs.ucdavis. edu/~rogaway/umac/2000perf00bis.html , 2006.[52] N. Shah, “Understanding Network Processors,” Master's thesis, Univ. of California, Berkeley, Sept. 2001.[53] W. Feghali, B. Burres, G. Wolrich, and D. Carrigan, “Security: Adding Protection to the Network via the Network Processor,” Intel Technology J., vol. 06, pp. 40-49, Aug. 2002.[54] National Institute of Standards and Tech nology, “Data encryption Standard,” FIPS PUBS 46-3, Oct. 1999.[55] National Institute of Standards and Tech nology, “Advanced Encryption Standard,” FIPS PUBS 197, Nov. 2001.[56] N.G. Duffield and M. Grossglauser, “Trajectory Sampling for Direct Traffic Observation,” Proc. ACM SIGCOMM'00, pp. 271-282, 2000.[57] N. Spring, R. Mahajan, and D. Wetherall, “Measuring ISP Topologies with Rocketfuel,” Proc. ACM/SIGCOMM, pp. 133-145, 2002.[58] K.M. Chandy and L. Lamport, “Distributed Snapshots: Determining Global States of Distributed Systems,” ACM Trans. Computer Systems, vol. 3, no. 1, pp. 63-75, 1985.[59] L. Lamport, R. Shostak, and M. Pease, “The Byzantine Generals Problem,” ACM Trans. Programming Languages and Systems, vol. 4, no. 3, pp. 382-401, 1982.
Index Terms:
Communication/networking and information technology, network-level security and protection, network protocols, routing protocols, fault tolerance.
Citation:
Alper Tugay Mizrak, Yu-Chung Cheng, Keith Marzullo, Stefan Savage, "Detecting and Isolating Malicious Routers," IEEE Transactions on Dependable and Secure Computing, vol. 3, no. 3, pp. 230-244, July-Sept. 2006, doi:10.1109/TDSC.2006.34
