An Adaptive Pruning Algorithm for Spoofing Localisation Based on Tropical Geometry

Emmanouil Theodosis, Petros MaragosarXiv 2018 · OpenReview

Abstract

The problem of spoofing attacks is increasingly relevant as digital systems are becoming more ubiquitous. Thus the detection of such attacks and the localisation of attackers have been objects of recent study. After an attack has been detected, various algorithms have been proposed in order to localise the attacker. In this work we propose a new adaptive pruning algorithm inspired by the tropical and geometrical analysis of the traditional Viterbi pruning algorithm to solve the localisation problem. In particular, the proposed algorithm tries to localise the attacker by adapting the leniency parameter based on estimates about the state of the solution space. These estimates stem from the enclosed volume and the entropy of the solution space, as they were introduced in our previous works.

Introduction

In modern network security, identifying a spoofing attack is only the first step. Once detected, the critical challenge shifts to localisation: pinpointing the physical or logical origin of the malicious actor. The Viterbi algorithm is frequently employed for this task, modelling the attacker's path as a sequence of hidden states inferred from observed network requests. However, the computational complexity of Viterbi in large-scale networks necessitates the use of pruning techniques. Traditional pruning relies on a fixed leniency parameter ($\theta$), which often fails to account for dynamic network conditions, leading to either excessive computational overhead or the loss of the optimal solution path.

Tropical Geometry and the Viterbi Algorithm

The core innovation of this research is the application of Tropical Geometry to analyse the Viterbi algorithm's solution space. By reformulating the Viterbi update laws using "min-plus" algebra, the set of all valid solutions at any given time step can be represented as a tropical polytope—a high-dimensional geometric shape.

Tropical halfspace (a) and Tropical polytope (b) representing the solution space.

This geometric abstraction allows researchers to quantify the state of the search space using two primary metrics:

  1. Normalized Volume ($\nu$): This metric measures the breadth of the current solution space.
  2. Entropy ($\epsilon$): Derived from information theory, entropy serves as a measure of "surprise," indicating how well the current model fits incoming data. High entropy often signals a shift in the attacker's behaviour.

The Adaptive Pruning Algorithm

The proposed AdaptivePruning algorithm dynamically adjusts the leniency parameter $\theta$ to optimise the search process. Unlike static pruning, which uses a constant threshold, this approach monitors the geometric properties of the tropical polytope to decide when and how to adapt.

Schematic of the Viterbi algorithm with pruning windows defined by leniency parameters $\theta_0$ and $\theta_1$.

The adaptation logic follows a two-step trigger:

  • Detection: If the current entropy ($\epsilon$) deviates from its historical average beyond a threshold ($\alpha$), the algorithm identifies a change in the environment.
  • Adjustment: The algorithm then modifies $\theta$ by a factor $\beta$ to maintain a consistent "search volume." This ensures that the algorithm examines a sufficient portion of the solution space without wasting resources on highly improbable paths.

Experimental Evaluation

The algorithm was tested in a simulated network environment featuring benevolent users and a malevolent attacker. Benevolent traffic followed a standard Poisson distribution, while the attacker exhibited a significantly higher request rate ($\lambda_d$). To test the adaptive capabilities, the attacker's request rate was varied every 1,000 iterations, simulating an intelligent adversary attempting to mask their identity.

Results indicate that the adaptive mechanism successfully tracks the attacker's changing behaviour. By maintaining a stable "search volume," the algorithm avoids the computational explosion associated with overly lenient parameters while preserving localisation accuracy. This approach ensures the system is always looking at a "fair" amount of the solution space, preventing it from becoming too narrow and missing the target.

Conclusion and Future Work

By viewing the Viterbi algorithm through the lens of tropical geometry, this work provides a robust framework for adaptive parameter tuning in cybersecurity applications. Future research will focus on evaluating the algorithm against real-world network traffic, which often exhibits "bursty" patterns that differ from simulated Poisson distributions, and further optimising the computational overhead of calculating geometric metrics in real-time.

Summary updated

Abstract

The problem of spoofing attacks is increasingly relevant as digital systems are becoming more ubiquitous. Thus the detection of such attacks and the localisation of attackers have been objects of recent study. After an attack has been detected, various algorithms have been proposed in order to localise the attacker. In this work we propose a new adaptive pruning algorithm inspired by the tropical and geometrical analysis of the traditional Viterbi pruning algorithm to solve the localisation problem. In particular, the proposed algorithm tries to localise the attacker by adapting the leniency parameter based on estimates about the state of the solution space. These estimates stem from the enclosed volume and the entropy of the solution space, as they were introduced in our previous works.
BibTeX
@misc{theodosis2018adaptive,
  author = {Emmanouil Theodosis and Petros Maragos},
  title = {{An Adaptive Pruning Algorithm for Spoofing Localisation Based on Tropical Geometry}},
  year = {2018},
  eprint = {1811.01017},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1811.01017},
}
Figure