[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ skip to main content
10.1007/978-3-030-98785-5_10guideproceedingsArticle/Chapter ViewAbstractPublication PagesConference Proceedingsacm-pubtype
Article

RouteInfer: Inferring Interdomain Paths by Capturing ISP Routing Behavior Diversity and Generality

Published: 28 March 2022 Publication History

Abstract

Accurate inference of interdomain paths between arbitrary source and destination is the foundation for many research areas, especially for the security of the Internet routing system. The widely used method to solve this problem is using standard policies based on the business relationship model, but it is far from satisfactory. We conduct an in-depth analysis on the inherent limitations of the path inference by standard routing policies and show that the routing behaviors of ISPs are diverse and standard import policies are oversimplified. Then we develop RouteInfer, an algorithm for accurately inferring interdomain paths by capturing ISP routing behaviors diversity and generality. RouteInfer uses a 3-layer policy model to extract the fine-grained policies and coarse-grained policies of ASes and can achieve high accuracy as well as good generalization ability. After extracting policies, we find another inherent challenge that there is still a huge number of ASes without inferred policies. To overcome this challenge, RouteInfer formulates the prediction of route decisions as a ranking problem and develops a learning-based approach especially for predicting route decisions. We carefully design node, link, and path features based on the understanding of actual route decisions. Overall, on average, RouteInfer achieves 81.64% accuracy. Compared with state-of-the-art inference algorithms, RouteInfer increases the inference accuracy by about 30.04% to 182.3%. Furthermore, we analyze the inferred policies and the route decision model to understand routing behaviors deeply. We find that many ASes set fine-grained policies for CDN ASes. Besides, most of the violations of the standard preference rule are related to p2p links in European IXPs.

References

[1]
Lychev, R., Goldberg, S., Schapira, M.: BGP security in partial deployment: is the juice worth the squeeze? In: Proceedings of the ACM SIGCOMM 2013 Conference on SIGCOMM, pp. 171–182 (2013)
[2]
Cohen, A., Gilad, Y., Herzberg, A., Schapira, M.: Jumpstarting BGP security with path-end validation. In: Proceedings of the 2016 ACM SIGCOMM Conference, pp. 342–355 (2016)
[3]
Gilad, Y., Cohen, A., Herzberg, A., Schapira, M., Shulman, H.: Are we there yet? On RPKI’s deployment and security. In: NDSS (2017)
[4]
Madhyastha, H.V., Katz-Bassett, E., Anderson, T.E., Krishnamurthy, A., Venkataramani, A.: iPlane nano: path prediction for peer-to-peer applications. In: NSDI, vol. 9, pp. 137–152 (2009)
[5]
Apostolaki, M., Marti, G., Müller, J., Vanbever, L.: SABRE: protecting bitcoin against routing attacks. In: 26th Annual Network and Distributed System Security Symposium, NDSS 2019, San Diego, California, USA, 24–27 February 2019 (2019)
[6]
Tran, M., Shenoi, A., Kang, M.S.: On the routing-aware peering against network-eclipse attacks in bitcoin. In: 30th USENIX Security Symposium (USENIX Security 21) (2021)
[7]
Apostolaki, M., Zohar, A., Vanbever, L.: Hijacking bitcoin: routing attacks on cryptocurrencies. In: 2017 IEEE Symposium on Security and Privacy (SP), pp. 375–392. IEEE (2017)
[8]
Tran, M., Choi, I., Moon, G.J., Vu, A.V., Kang, M.S.: A stealthier partitioning attack against bitcoin peer-to-peer network. In: 2020 IEEE Symposium on Security and Privacy (SP), pp. 894–909. IEEE (2020)
[9]
Nasr, M., Zolfaghari, H., Houmansadr, A.: The waterfall of liberty: decoy routing circumvention that resists routing attacks. In: Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security, pp. 2037–2052 (2017)
[10]
Houmansadr, A., Wong, E.L., Shmatikov, V.: No direction home: the true cost of routing around decoys. In: 21st Annual Network and Distributed System Security Symposium, NDSS 2014, San Diego, California, USA, 23–26 February 2014 (2014)
[11]
RisNithyanand, R., Starov, O., Zair, A., Gill, P., Schapira, M.: Measuring and mitigating AS-level adversaries against Tor. In: 23rd Annual Network and Distributed System Security Symposium, NDSS 2016, San Diego, California, USA, 21–24 February 2016. The Internet Society (2016)
[12]
Gao L and Rexford J Stable internet routing without global coordination IEEE/ACM Trans. Netw. 2001 9 6 681-692
[13]
Mühlbauer W, Uhlig S, Bingjie F, Meulle M, and Maennel O In search for an appropriate granularity to model routing policies ACM SIGCOMM Comput. Commun. Rev. 2007 37 4 145-156
[14]
Anwar, R., Niaz, H., Choffnes, D., Cunha, Í., Gill, P., Katz-Bassett, E.: Investigating interdomain routing policies in the wild. In: Proceedings of the 2015 Internet Measurement Conference, pp. 71–77 (2015)
[15]
Mühlbauer W, Feldmann A, Maennel O, Roughan M, and Uhlig S Building an AS-topology model that captures route diversity ACM SIGCOMM Comput. Commun. Rev. 2006 36 4 195-206
[16]
Qiu, J., Gao, L.: AS path inference by exploiting known AS paths. In: Proceedings of IEEE GLOBECOM. Citeseer (2005)
[17]
Singh, R., Tench, D., Gill, P., McGregor, A.: PredictRoute: a network path prediction toolkit. In: Proceedings of the ACM on Measurement and Analysis of Computing Systems, vol. 5, no. 2, pp. 1–24 (2021)
[18]
Gill P, Schapira M, and Goldberg S Modeling on quicksand: dealing with the scarcity of ground truth in interdomain routing data ACM SIGCOMM Comput. Commun. Rev. 2012 42 1 40-46
[19]
Gao L On inferring autonomous system relationships in the internet IEEE/ACM Trans. Netw, 2001 9 6 733-745
[20]
Mao, Z.M., Qiu, L., Wang, J., Zhang, Y.: On AS-level path inference. In: Proceedings of the 2005 ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Systems, pp. 339–349 (2005)
[21]
Deng W, Mühlbauer W, Yang Y, Zhu P, Xicheng L, and Plattner B Shedding light on the use of AS relationships for path inference J. Commun. Netw. 2012 14 3 336-345
[22]
Giotsas, V., Zhou, S.: Valley-free violation in internet routing - analysis based on BGP community data. In: 2012 IEEE International Conference on Communications (ICC), pp. 1193–1197. IEEE (2012)
[23]
Tian Z, Shen S, Shi W, Xiaojiang D, Guizani M, and Xiang Yu A data-driven method for future internet route decision modeling Futur. Gener. Comput. Syst. 2019 95 212-220
[24]
Luckie, M., Huffaker, B., Dhamdhere, A., Giotsas, V., Claffy, K.C.: AS relationships, customer cones, and validation. In: Proceedings of the 2013 Conference on Internet Measurement Conference, pp. 243–256 (2013)
[25]
The Internet Routing Registry - RADb. https://www.radb.net/
[27]
AS Rank: A ranking of the largest Autonomous Systems. https://asrank.caida.org/
[28]
Liu, T.-Y.: Learning to rank for information retrieval (2011)
[29]
Burges CJC From RankNet to LambdaRank to LambdaMART: an overview Learning 2010 11 23–581 81
[30]
Routeviews - University of Oregon Route Views Project. http://www.routeviews.org/routeviews/
[33]
Jasinska, E., Hilliard, N., Raszuk, R., Bakker, N.: RFC7947: internet exchange BGP route server (2016)
[34]
Oliveira R, Pei D, Willinger W, Zhang B, and Zhang L The (in) completeness of the observed Internet AS-level structure IEEE/ACM Trans. Netw. 2009 18 1 109-122
[35]
Alaettinoglu C Routing Policy Specification Language (RPSL) RFC 1999 2622 1-69
[41]
Internet Exchange Point Datasets—PCH. https://www.pch.net/ixp/data
[42]
Burges, C., et al.: Learning to rank using gradient descent. In: Proceedings of the 22nd International Conference on Machine Learning, pp. 89–96 (2005)
[43]
Burges, C., Ragno, R., Le, Q.: Learning to rank with nonsmooth cost functions. In: Advances in Neural Information Processing Systems, vol. 19, pp. 193–200 (2006)
[44]
Chang, Y., Chapelle, O., Liu, T.-Y.: The Yahoo! learning to rank challenge. http://learningtorankchallenge.yahoo.com
[45]
Giotsas, V., Luckie, M., Huffaker, B., Claffy, K.C.: Inferring complex as relationships. In: Proceedings of the 2014 Conference on Internet Measurement Conference, pp. 23–30 (2014)
[46]
Jin, Y., Scott, C., Dhamdhere, A., Giotsas, V., Krishnamurthy, A., Shenker, S.: Stable and practical AS relationship inference with Problink. In: 16th USENIX Symposium on Networked Systems Design and Implementation (NSDI 19), pp. 581–598 (2019)
[47]
Jin, Z., Shi, X., Yang, Y., Yin, X., Wang, Z., Wu, J.: TopoScope: recover AS relationships from fragmentary observations. In: Proceedings of the ACM Internet Measurement Conference, pp. 266–280 (2020)
[49]
Smith, J.M., Birkeland, K., McDaniel, T., Schuchard, M.: Withdrawing the BGP re-routing curtain: understanding the security impact of BGP poisoning through real-world measurements. In: NDSS (2020)

Cited By

View all
  • (2024)What is the next hop to more granular routing models?Proceedings of the 23rd ACM Workshop on Hot Topics in Networks10.1145/3696348.3696859(343-351)Online publication date: 18-Nov-2024
  • (2023)Replication: 20 Years of Inferring Interdomain Routing PoliciesProceedings of the 2023 ACM on Internet Measurement Conference10.1145/3618257.3624799(16-29)Online publication date: 24-Oct-2023

Index Terms

  1. RouteInfer: Inferring Interdomain Paths by Capturing ISP Routing Behavior Diversity and Generality
      Index terms have been assigned to the content through auto-classification.

      Recommendations

      Comments

      Please enable JavaScript to view thecomments powered by Disqus.

      Information & Contributors

      Information

      Published In

      cover image Guide Proceedings
      Passive and Active Measurement: 23rd International Conference, PAM 2022, Virtual Event, March 28–30, 2022, Proceedings
      Mar 2022
      690 pages
      ISBN:978-3-030-98784-8
      DOI:10.1007/978-3-030-98785-5

      Publisher

      Springer-Verlag

      Berlin, Heidelberg

      Publication History

      Published: 28 March 2022

      Author Tags

      1. Interdomain path inference
      2. BGP routing policy
      3. Network measurement

      Qualifiers

      • Article

      Contributors

      Other Metrics

      Bibliometrics & Citations

      Bibliometrics

      Article Metrics

      • Downloads (Last 12 months)0
      • Downloads (Last 6 weeks)0
      Reflects downloads up to 22 Feb 2025

      Other Metrics

      Citations

      Cited By

      View all
      • (2024)What is the next hop to more granular routing models?Proceedings of the 23rd ACM Workshop on Hot Topics in Networks10.1145/3696348.3696859(343-351)Online publication date: 18-Nov-2024
      • (2023)Replication: 20 Years of Inferring Interdomain Routing PoliciesProceedings of the 2023 ACM on Internet Measurement Conference10.1145/3618257.3624799(16-29)Online publication date: 24-Oct-2023

      View Options

      View options

      Figures

      Tables

      Media

      Share

      Share

      Share this Publication link

      Share on social media