Minimax Detection (MAD) for Computer Security: A Dynamic Program Characterization

Muhammed O. Sayin, Dinuka Sahabandu, Muhammad Aneeq uz Zaman, Radha Poovendran, Tamer Basar

Research output: Chapter in Book/Report/Conference proceedingChapter


In this chapter, we propose and analyze a cohesive minimax detection (MAD) mechanism for modern computing systems, e.g., a computer or a network of computers. MAD monitors system-level activities across the entire system in order to assess them together. It evaluates system-level activities at two orthogonal directions, in terms of their likeliness (similar to anomaly detection) and riskiness (similar to signature-based detection). It also provides analytical guarantees for minimax performance, i.e., minimizes the system's detection cost that is maximized by an adversary, called MAX, seeking to intervene into the system. To this end, we model the interaction between MAD and MAX by a zero-sum game. A major challenge, however, is the comprehensive assessment of activities across the entire system, which corresponds to a game at an enormous size. To address this challenge, we model MAD as evaluating the system's activities within a hierarchical tree. This enables us to decompose the game into a nested structure and therefore we can compute minimax detection strategies via a dynamic program similar to backward induction in extensive form games.
Original languageEnglish (US)
Title of host publicationGame Theory and Machine Learning for Cyber Security
EditorsCharles A Kamhoua, Christopher D Kiekintveld, Fei Fang, Quanyan Zhu
PublisherWiley-IEEE Press
Number of pages22
ISBN (Electronic)9781119723950, 9781119723943
ISBN (Print)9781119723929
StatePublished - Jun 16 2021


  • anomaly detection
  • dynamic programming
  • game theory
  • computer security
  • signature-based detection

ASJC Scopus subject areas

  • General Engineering


Dive into the research topics of 'Minimax Detection (MAD) for Computer Security: A Dynamic Program Characterization'. Together they form a unique fingerprint.

Cite this