Advanced Computing, Mathematics and Data
Research Highlights

March 2015

StreamWorks: Pattern Detection for Your Protection

Novel graph method detects cyber-attack patterns in complex computing networks

Results: As the perils of cyber security breaches continue to plague industries, governments, and citizens throughout the world, the need to detect these infiltrating events, as well as identify their attack patterns, in complex computing networks as they emerge in real time remains a paramount concern and growing challenge. In their work involving streaming graphs, scientists at Pacific Northwest National Laboratory and Washington State University, devised a novel framework called StreamWorks that categorizes cyber attacks as graph patterns, which then can be examined using a continuous search (query) on a single, large streaming dynamic graph. “Continuous Query” focuses on finding matches for queries in a data stream as soon as they happen, which is in contrast to ad hoc querying supported by databases such as MySQL or Neo4J that aim to efficiently query a large, non-changing data set.

Example patterns searched by StreamWorks. Enlarge Image.

Using two real-world data sets—an online news stream from The New York Times and Internet network traffic from the Center for Applied Internet Data Analysis—their method produced efficient continuous queries on dynamic graphs with speedups up to 100x greater than current methods that do not support real-time subgraph pattern matching.

Why it Matters: As the volume and throughput of network traffic or data sets rise exponentially, the inability to detect adversarial actions in real-time provides an asymmetric advantage to attackers. Meanwhile, the need to protect intellectual properties and customer data only continues to grow in priority for corporations and government agencies worldwide. Identifying precursor events and patterns as they emerge will go a long way in evading and mitigating the computer network intrusions and threats that have potentially criminal, even dangerous, consequences and have made cyber security a multi-billion dollar industry.

“In the high-stakes cyber security domain, processing streaming updates to a dynamic graph database accumulating multiple data sources, such as network flow firewall logs, is important for realizing real-time situational awareness,” said Sutanay Choudhury, a computer scientist with PNNL’s Data Sciences group and the paper’s lead author.

Methods: For their work, the researchers needed to register patterns in data sets as a graph query and continuously perform said query on the graph as it evolved over time. Notably, the graphs are heterogeneous, or multi-relational, meaning a single data stream can have diverse characteristics. For example, in graph terms, this would mean different edge types for cyber security and varied node and edge types in social media. Rather than looking for matches within an entire graph, the selective search method exploits the data’s heterogeneity by searching smaller subgraphs ordered by their selectivity, obtained using the single-edge level and 2-edge path distribution from the graph stream. The resulting decomposition is stored in a data structure, or subgraph join tree (SJ-tree), that tracks matching subgraphs and combines them to produce larger matches.

From there, the join order provides a heuristic technique for assembling matches without seeking every possible way to do so, thereby curtailing some of the cost associated with more broad searches. The team’s “lazy search” graph algorithm, triggered only if a new edge is the most selective subgraph in the query or if one of the vertices in that edge participates in a match with the preceding subgraph in the join order, also limits the amount of partial matches that are tracked to subgraphs.

A map-based visualization interface to associate traffic patterns with origins and destination. Enlarge Image.

The researchers used the online news stream and network traffic from CAIDA, as well as a synthetic social media stream, data sets to examine how selectivity distribution of subgraphs played out. They compared the performance of multiple combinations of query decomposition execution methods. They also provided a “Relative Selectivity” rule for engaging an optimum search strategy. Their efforts showed that the distribution of 2-edge subgraphs is heavily skewed and a query decomposition strategy that exploits this skew using the “lazy search” algorithm will be consistently efficient.

What’s Next? The subgraph-selectivity-based approach proposed in this work is an initial start for tackling the problem of continuous pattern detection. More investigation is needed to provide accurate selectivity estimation. The team actively is working on a distributed implementation of the Continuous Query engine, which will afford the capability to scale in an HPC cluster. Additional research efforts can leverage work on query performance modeling and approximate algorithms. Supporting expressive, rich queries requires computations with high time and space complexity. A continuous stream processing system cannot afford to spawn computations that exceed a time or memory bound. Predicting query performance from the knowledge of stream statistics and using approximate algorithms provide a natural path toward that goal.

Acknowledgment: This work is supported by PNNL’s High Performance Data Analytics program.

PNNL Research Team: George Chin (Principal Investigator, NSD); Sutanay Choudhury (co-PI), Khushbu Agarwal, Sherman Beus, and Vivek Datla (all FCSD). 

Reference:
Choudhury S, L Holder, G Chin Jr, K Agarwal, and JT Feo. 2015. “A Selectivity-based Approach to Continuous Pattern Detection in Streaming Graphs.” In 18th International Conference on Extending Database Technology (ICDT 2015). March 23-27, 2015, Brussels, Belgium. 

Related:

• Chin Jr G, S Choudhury, and K Agarwal. 2014. “StreamWorks—A System for Real-Time Graph Pattern Matching on Network Traffic.” Presented at FloCon 2015, January 12-15, 2015, Portland, Oregon.
• Chin Jr G, S Choudhury, JT Feo, and L Holder. 2014. “Predicting and Detecting Emerging Cyberattack Patterns Using StreamWorks.” In Proceedings of the 9th Annual Cyber and Information Security Research Conference (CISR’14), pp.93-96, April 8-10, 2014, Oak Ridge, Tennessee. Association for Computing Machinery, New York. DOI: 10.1145/2602087.2602111.
• Lieberman M, S Choudhury, M Hughes, D Patrone, S Hider, C Piatko, M Chapman, JP Marple, and D Silberberg. 2014. “Parasol: An Architecture for Cross-Cloud Federated Graph Querying.” In Proceedings of the DanaC: Workshop on Data Analytics in the Cloud, pp. 1-4. June 22, 2014, Snowbird, Utah. Association for Computing Machinery, New York. DOI: 10.1145/2627770.2627771.
• Joslyn C, S Choudhury, D Haglin, B Howe, B Nickless, and B Olsen. 2013. “Massive Scale Cyber Traffic Analysis: A Driver for Graph Database Research.” In Proceedings of the First International Workshop on Graph Data Management Experience and Systems (GRADES 2013), Article No. 3. June 23, 2013, New York, New York. Association for Computing Machinery, New York. DOI: 10.1145/2484425.2484428.
• Choudhury S, LB Holder, JT Feo, and G Chin Jr. “Fast Search for Multi-Relational Graphs.” In Proceedings of the Workshop on Dynamic Networks Management and Mining (DyNetMM '13), pp. 1-8. June 23, 2013, New York, New York. Association for Computing Machinery, New York. DOI: 10.1145/2489247.2489251.
• Choudhury S, LB Holder, G Chin Jr, A Ray, S Beus, and JT Feo. 2013. “StreamWorks—A System for Dynamic Graph Search.” In Proceedings of the 2013 ACM SIGMOD International Conference on Management of Data (SIGMOD '13), pp. 1101-1104. June 22-27, 2013, New York, New York. Association for Computing Machinery, New York. DOI: 10.1145/2463676.2463697.