MAPPING POTENTIAL ATTACKERS AGAINST NETWORK SECURITY USING LOCATION AWARE REACHABILITY QUERIES ON GEO SOCIAL DATA

Hafara Firdausi, Bagus Jati Santoso, Rohana Qudus, Henning Titi Ciptaningtyas

Abstract


Attacks on network security can happen anywhere. Using Geo-Social Networks (GSN), i.e., a graph that combines social network data and spatial information, we can find the potential attackers based on the given location. In answering the graph-based problems, Reachability Queries are utilized. It verifies the reachability between two nodes in the graph. This paper addresses a problem defined as follows: Given a geo-social graph and a location area as a query point, we map potential attackers against network security using location-aware reachability queries. We employ the concepts of Reachability Minimum Bounding Rectangle (RMBR) and graph traversal algorithm, i.e., Depth-First Search (DFS), to answer the location-aware reachability queries. There are two kinds of the proposed solution, i.e., (1) RMBR-based solution map potential attackers by looking for intersecting RMBR values, and (2) Graph traversal-based solution map potential attackers by traversing the graph. We evaluate the performance of both proposed solutions using synthetic datasets. Based on the experimental result, the RMBR-based solution has much lower execution time and memory usage than the graph traversal-based solution.


Full Text:

PDF

References


M. Sarwat and Y. Sun, “Answering location-Aware graph reachability queries on geosocial data,” Proc. - Int. Conf. Data Eng., 2017, pp. 207–210.

N. Armenatzoglou, S. Papadopoulos, and D. Papadias, “A general framework for geoSocial query processing,” Proc. VLDB Endow., vol. 6, no. 10, 2013, pp. 913–924.

D. Wu, J. Shi, and N. Mamoulis, “Density-Based Place Clustering Using Geo-Social Network Data,” IEEE Trans. Knowl. Data Eng., vol. 30, no. 5, pp. 838–851, 2018.

R. R. Veloso, L. Cerf, W. Meira, and M. J. Zaki, “Reachability queries in very large graphs: A fast refined online search approach,” Adv. Database Technol. - EDBT 2014 17th Int. Conf. Extending Database Technol. Proc., vol. 1, no. c, pp. 511–522, 2014.

M. Du, A. Yang, J. Zhou, X. Tang, Z. Chen, and Y. Zuo, “HT: A Novel Labeling Scheme for k-Hop Reachability Queries on DAGs,” IEEE Access, vol. 7, pp. 172110–172122, 2019.

Y. Duan, X. Li, and L. Ding, “A reachability query method based on labeling index on large-scale graphs,” Proc. - 2015 Int. Conf. Comput. Sci. Comput. Intell. CSCI 2015, 2016, pp. 77–82.

R. Liang, H. Zhuge, X. Jiang, Q. Zeng, and X. He, “Scaling hop-based reachability indexing for fast graph pattern query processing,” IEEE Trans. Knowl. Data Eng., vol. 26, no. 11, pp. 2803–2817, 2014.

J. Su, Q. Zhu, H. Wei, and J. X. Yu, “Reachability Querying: Can It Be even Faster?,” IEEE Trans. Knowl. Data Eng., vol. 29, no. 3, pp. 683–697, 2017.

S. Zhou, P. Yuan, L. Liu, and H. Jin, “Mgtag: A multi-dimensional graph labeling scheme for fast reachability queries,” Proc. - IEEE 34th Int. Conf. Data Eng. ICDE, 2018, pp. 1376–1379.

H. Wei, J. X. Yu, C. Lu, and R. Jin, “Reachability querying: an independent permutation labeling approach,” VLDB J., vol. 27, no. 1, pp. 1191–1202, 2014.

T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, Introduction to Algorithms, Second Edition. 2001.

H. Yildirim and M. J. Zaki, “Graph indexing for reachability queries,” Proc. - Int. Conf. Data Eng., 2010, pp. 321–324.

J. Wood, “Minimum Bounding Rectangle,” in Encyclopedia of GIS, S. Shekhar and H. Xiong, Eds. Boston, MA: Springer US, 2008, pp. 660–661.




DOI: http://dx.doi.org/10.12962/j24068535.v19i2.a1071

Refbacks

  • There are currently no refbacks.