HERCULE: Attack story reconstruction via community discovery on correlated log graph

Kexin Pei, Zhongshu Gu, Brendan Saltaformaggio, Shiqing Ma, Fei Wang, Zhiwei Zhang, Luo Si, Xiangyu Zhang, Dongyan Xu

Research output: Chapter in Book/Report/Conference proceedingConference contribution

78 Scopus citations


Advanced cyber attacks consist of multiple stages aimed at being stealthy and elusive. Such attack patterns leave their footprints spatio-temporally dispersed across many different logs in victim machines. However, existing log-mining intrusion analysis systems typically target only a single type of log to discover evidence of an attack and therefore fail to exploit fundamental inter-log connections. The output of such single-log analysis can hardly reveal the complete attack story for complex, multi-stage attacks. Additionally, some existing approaches require heavyweight system instrumentation, which makes them impractical to deploy in real production environments. To address these problems, we present HERCULE, an automated multi-stage log-based intrusion analysis system. Inspired by graph analytics research in social network analysis, we model multi-stage intrusion analysis as a community discovery problem. HERCULE builds multi-dimensional weighted graphs by correlating log entries across multiple lightweight logs that are readily available on commodity systems. From these, HERCULE discovers any "attack communities" embedded within the graphs. Our evaluation with 15 well known APT attack families demonstrates that HERCULE can reconstruct attack behaviors from a spectrum of cyber attacks that involve multiple stages with high accuracy and low false positive rates.

Original languageEnglish (US)
Title of host publicationProceedings - 32nd Annual Computer Security Applications Conference, ACSAC 2016
PublisherAssociation for Computing Machinery
Number of pages13
ISBN (Electronic)9781450347716
StatePublished - Dec 5 2016
Externally publishedYes
Event32nd Annual Computer Security Applications Conference, ACSAC 2016 - Los Angeles, United States
Duration: Dec 5 2016Dec 9 2016

Publication series

NameACM International Conference Proceeding Series


Other32nd Annual Computer Security Applications Conference, ACSAC 2016
Country/TerritoryUnited States
CityLos Angeles

All Science Journal Classification (ASJC) codes

  • Software
  • Human-Computer Interaction
  • Computer Vision and Pattern Recognition
  • Computer Networks and Communications


Dive into the research topics of 'HERCULE: Attack story reconstruction via community discovery on correlated log graph'. Together they form a unique fingerprint.

Cite this