  Today, human security analysts collapse under the sheer volume of alerts they
have to triage during investigations. The inability to cope with this load,
coupled with a high false positive rate of alerts, creates alert fatigue. This
results in failure to detect complex attacks, such as advanced persistent
threats (APTs), because they manifest over long time frames and attackers tread
carefully to evade detection mechanisms. In this paper, we contribute a new
method to synthesize attack graphs from state machines. We use the network
direction to derive potential attack stages from single and meta-alerts and
model resulting attack scenarios in a kill chain state machine (KCSM). Our
algorithm yields a graphical summary of the attack, APT scenario graphs, where
nodes represent involved hosts and edges infection activity. We evaluate the
feasibility of our approach in multiple experiments based on the
CSE-CIC-IDS2018 data set. We obtain up to 446 458 singleton alerts that our
algorithm condenses into 700 APT scenario graphs resulting in a reduction of up
to three orders of magnitude. This reduction makes it feasible for human
analysts to effectively triage potential incidents. An evaluation on the same
data set, in which we embedded a synthetic yet realistic APT campaign, supports
the applicability of our approach of detecting and contextualizing complex
attacks. The APT scenario graphs constructed by our algorithm correctly link
large parts of the APT campaign and present a coherent view to support the
human analyst in further analyses.
