Game Theory in Digital Forensics

Game Theory in
Digital Forensics
- G LEN BA N K S
What is Game Theory?
• “Game theory is a branch of modern applied mathematics that aims to
analyze various problems of conflict between parties that have
opposed, similar or simply different interests”. (Nisioti, Antonia, et al.)
• Try to quantify winning, losing, and how to play and use that to
calculate best strategies.
Game Theory Terminology
• x X is a “strategy” for player 1
• y  Y is a “strategy” for player 2
• A pair of (x, y) is called a “situation”
• K is the “payoff”, given a situation
• A is the matrix of payoffs for the two players
(Terminology from: Nisioti, Antonia, et al. “Game-Theoretic Decision

Support for Cyber Forensic Investigations.”)
Modeling How To Choose a Tool
• Let’s call choosing a carving tool a “game”.
• Using a specific carving tool is a “strategy” for player 1.
• We will call the “Time sensitive”, “File sensitive”, and “Equally
sensitive” cases the “strategies” for player 2.
• A “situation” will be a combination of tool x sensitivity.
(Using an example from the article “A Game Theoretic Approach for

Digital Forensic Tool Selection” by Umit and Tugba Karabiyik)
Calculating Payoff
• To create a Payoff matrix, we need to give values to the tools.
• The first step is to figure out how to assign points. We will do so using
the following set of equations.
• We can define as the points assigned for succeeding in a test case.
will be the faster tool, and will be the slower tool.
• Then we can run a few tests and average the result. This will give us a
likelihood of success
Carving Tool x Sensitivity Payoff Matrix
• The two tools we have are Scalpel and Photorec.
• We can use this matrix as our percent chance of success when comparing both
products. (e.g., 0.23 is 23% chance of success)
Sensitivity Scalpel Photorec
Time Sensitive 0.23 1
File Sensitive 0.85 0.5
Equally Sensitive 0.16 0.5
Effectiveness
• Using different algorithms for deciding which tool to use, we can
simulate the increase in effectiveness for using the appropriate tool.
Sensitivity Algorithm Average Total Payoff

Time Sensitive E-Greedy Multi-Armed Bandit 92.03
Time Sensitive Randomization 61.619
File Sensitive E-Greedy Multi-Armed Bandit 79.598
File Sensitive Randomization 67.701
Equally Sensitive E-Greedy Multi-Armed Bandit 44.693
Equally Sensitive Randomization 32.96
Effectiveness
• Between 18% and 57% more effective to prioritize the better tool.
• Higher algorithm effectiveness is tied to a greater difference between the
effectiveness of the tools.
Sensitivity Algorithm Average Total Payoff
Time Sensitive E-Greedy Multi-Armed Bandit 92.03
Time Sensitive Randomization 61.619
File Sensitive E-Greedy Multi-Armed Bandit 79.598
File Sensitive Randomization 67.701
Equally Sensitive E-Greedy Multi-Armed Bandit 44.693
Equally Sensitive Randomization 32.96
Game Theory In Digital Forensics
• Digital Forensics is complex.
• Digital Forensics is not a “zero-sum” game.
• However, certain aspects are somewhat easy to model.
• Having quantitative methods for evaluating strategies allows for
defensible optimization.
• (Fancy way of saying that being able to assign values and use math to choose how
you do investigations will look better in court.)
Questions?
Sources Cited
Leon A Petrosyan, and Nikolay A Zenkevich. Game Theory (Second Edition). World Scientific, 2016.
EBSCOhost,
https://search-ebscohost-com.mutex.gmu.edu/login.aspx?direct=true&db=nlebk&AN=1194620&site=ehost-li
ve
.
Bolon, Thomas. How to Never Lose at Tic-Tac-Toe. Book Country, 2013.
Nisioti, Antonia, et al. “Game-Theoretic Decision Support for Cyber Forensic Investigations.” Sensors (Basel,
Switzerland), vol. 21, no. 16, MDPI, 2021, p. 5300–, https://doi.org/10.3390/s21165300.
Backup slides
A “Simple” Example
Rules:
- One player chooses a symbol (let’s say Player 1 starts with “O”) and places
it on the Board.
- The second player places their symbol (“X”) on the Board in another
location.
- Players take turns placing their symbols until the board is filled or a
player wins
- A player wins if their symbol occupies an entire row, column, or diagonal.
Note:
- A game lasts at most 9 turns.
- If both players play optimally, the game ends in a draw
- Player 1 has an advantage, as there are more situations where they win.
- The game is “zero-sum”, meaning if a player wins, the other loses
Tic Tac Toe Strategies
• Player 1 has 9C1 + 9C2 + 9C3 + 9C4 + 9C5
= 381 strategies. A strategy for 1 move
• Player 2 has 9C0 + 9C1 + 9C2 + 9C3 + 9C4

= 256 strategies.
• Using “Choose”, since the order doesn’t matter.
Tic Tac Toe Strategies
• Player 1 has 9C1 + 9C2 + 9C3 + 9C4 + 9C5
= 381 strategies. A strategy for 2 moves
• Player 2 has 9C0 + 9C1 + 9C2 + 9C3 + 9C4

= 256 strategies.
• Using “Choose”, since the order doesn’t matter.
Tic Tac Toe Situations
• Situations take into account both players’
A situation where each player has
moves. moved twice
• If you count rotations and reflections of a
board as a single position, there are 138
“terminal” board positions.
• 91 are won by player 1 (There are 131,184 ways to
get to one of these board positions)
• 44 are won by player 2
• 3 are a draw.
Tic Tac Toe Payoffs
• Payoff, K(x,y) is positive if player 1 gains
advantage. It is negative if player 2 gains
advantage.
• In a zero-sum game, player 2’s payoff is -K(x,y)
• We could calculate the payoff K(x,y) as the
number of future situations where player 1
could win minus the number that player 2 could
win.
Tic Tac Toe Payoffs
• Assuming that O is first, what is the payoff of
the current situation?
• There are three remaining situations:
• One where X wins.
• One where the players draw.
• One where the game has not concluded.
• 0 – 1 = -1

Game Theory in Digital Forensics

Uploaded by

Copyright:

Available Formats

Game Theory in Digital Forensics

Uploaded by

Document Information

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Game Theory in Digital Forensics

Uploaded by

Copyright:

Available Formats

Game Theory in

(Terminology from: Nisioti, Antonia, et al. “Game-Theoretic Decision

(Using an example from the article “A Game Theoretic Approach for

Sensitivity Algorithm Average Total Payoff

Bolon, Thomas. How to Never Lose at Tic-Tac-Toe. Book Country, 2013.

• Player 2 has 9C0 + 9C1 + 9C2 + 9C3 + 9C4

• Player 2 has 9C0 + 9C1 + 9C2 + 9C3 + 9C4

You might also like