U.S. Department of Energy

Pacific Northwest National Laboratory

GRADIENT: Graph Analytic Approach for Discovering Irregular Events, Nascent and Temporal

Principle Investigator: 

Finding a time-ordered signature within large graphs is a computationally complex problem due to the combinatorial explosion of potential patterns. The Graph Analytic Approach for Discovering Irregular Events Nascent and Temporal (GRADIENT) project is designed to search and understand that problem space.

Approach

The focus of GRADIENT is to take big data (e.g., phone and email records or Windows event logs) and transform that data into a complex graph problem. In doing this, the amount of data can be reduced at the expense of increased complexity of the problem. Although the problem is more complex, the wealth of knowledge in graph theory to explore and characterize the data can be leveraged. Graphs shed light on important structural aspects within the data. This allows identification of the big picture of how the network topology is being used.

Impact

The impact of GRADIENT is threefold. First, our pattern finding thrust is designed to reduce data size for analysts. By searching through the massive dataset for patterns that analysts and SMEs have identified as relevant, they can explore each significant pattern more deeply rather than the whole dataset shallowly. Our second impact is change characterization of graphs. We compare instances of the same graph over different time periods. This allows for inspection of exactly how the graph has evolved. This evolution can have signatures of its own that typify its behavior. Finally, we have developed a reachability metric that quantifies the level of risk in a computer network to advanced persistent threats like pass-the-hash.

Project Staff: 
Emilie Hogan, Dan Best, Bill Nickless, Peter Hui, John Johnson

GRADIENT: Graph Analytic Approach for Discovering Irregular Events, Nascent and Temporal

Finding a time-ordered signature within large graphs is a computationally complex problem due to the combinatorial explosion of potential patterns. GRADIENT is designed to search and understand that problem space.
| Pacific Northwest National Laboratory