Skip to content

Latest commit

 

History

History
137 lines (82 loc) · 9.7 KB

attack-tree.md

File metadata and controls

137 lines (82 loc) · 9.7 KB

Attack Tree Analysis for mxgmn/wavefunctioncollapse

Objective: To cause a denial-of-service (DoS) or resource exhaustion in an application using the wavefunctioncollapse library, or to force the generation of predictable/undesirable output.

Attack Tree Visualization

Compromise Application using WavefunctionCollapse
├── 1. Denial of Service / Resource Exhaustion [HR]
│   ├── 1.1.  Infinite Loop / Non-Termination [HR]
│   │   ├── 1.1.1.  Craft Input Tileset with Contradictory Rules [CN] [HR]
│   │   │   └── 1.1.1.1.  Exploit Weak Constraint Checking (if present) [CN] [HR]
│   │   ├── 1.1.2.  Provide Extremely Large Output Dimensions [CN] [HR]
│   │   │   └── 1.1.2.1.  Bypass Input Validation (if present) [CN] [HR]
│   ├── 1.2.  Excessive Memory Consumption [HR]
│   │   ├── 1.2.1.  Provide Extremely Large Output Dimensions [CN] [HR]
│   │   │   └── 1.2.1.1.  Bypass Input Validation (if present) [CN] [HR]
│   │   ├── 1.2.2.  Use Very Large Input Tileset [CN] [HR]
│   │   │   └── 1.2.2.1.  Bypass Input Validation (if present) [CN] [HR]
│   └── 1.3.  Excessive CPU Consumption [HR]
│       ├── 1.3.1.  Provide Complex Tileset with Many Constraints [HR]
│       │   └── 1.3.1.1.  Bypass Input Validation (if present) [CN] [HR]
│       ├── 1.3.3 Provide Extremely Large Output Dimensions [CN] [HR]
│           └── 1.3.3.1. Bypass Input Validation (if present) [CN] [HR]
└── 2. Predictable / Undesirable Output
    ├── 2.1.  Manipulate Random Number Generator (RNG) [CN]
    │   ├── 2.1.1.  Predict RNG Seed (if exposed or predictable) [CN]
    │   │   └── 2.1.1.1.  Exploit Weak Seed Generation or Storage [CN]
        ├── 2.2.  Force Specific Tile Choices
        │   └── 2.2.1.1.  Exploit Weak Constraint Checking (if present) [CN]
        └── 2.3.  Bias Output Distribution
            └── 2.3.1.1.  Exploit Unprotected Access to Tile Weights [CN]

Attack Tree Path: 1. Denial of Service / Resource Exhaustion [HR]

  • Description: The attacker aims to cause the WFC algorithm to run indefinitely, consuming resources and preventing the application from functioning.

Attack Tree Path: 1.1. Infinite Loop / Non-Termination [HR]

  • Description: The attacker aims to cause the WFC algorithm to run indefinitely, consuming resources and preventing the application from functioning.

Attack Tree Path: 1.1.1. Craft Input Tileset with Contradictory Rules [CN] [HR]

  • Description: The attacker creates a tileset where the rules defining how tiles can connect are impossible to satisfy simultaneously. This forces the algorithm into an infinite loop as it tries to find a valid solution.
  • Example: A tileset where tile A can only be next to tile B, tile B can only be next to tile C, and tile C can only be next to tile A, but no tile can be next to itself.

Attack Tree Path: 1.1.1.1. Exploit Weak Constraint Checking (if present) [CN] [HR]

  • Description: If the application doesn't properly check for contradictory rules before running the WFC algorithm, this attack is trivial to execute.

Attack Tree Path: 1.1.2. Provide Extremely Large Output Dimensions [CN] [HR]

  • Description: The attacker specifies an extremely large width, height, or depth for the output grid. This can lead to excessive memory allocation or CPU usage, even if the tileset itself is simple.
  • Example: Requesting an output grid of size 1000000x1000000.

Attack Tree Path: 1.1.2.1. Bypass Input Validation (if present) [CN] [HR]

  • Description: If the application doesn't properly limit the size of the output dimensions, this attack is easily executed.

Attack Tree Path: 1.2. Excessive Memory Consumption [HR]

  • Description: The attacker aims to exhaust the application's available memory, causing it to crash or become unresponsive.

Attack Tree Path: 1.2.1. Provide Extremely Large Output Dimensions [CN] [HR]

  • Description: The attacker specifies an extremely large width, height, or depth for the output grid. This can lead to excessive memory allocation or CPU usage, even if the tileset itself is simple.
  • Example: Requesting an output grid of size 1000000x1000000.

Attack Tree Path: 1.2.1.1. Bypass Input Validation (if present) [CN] [HR]

  • Description: If the application doesn't properly limit the size of the output dimensions, this attack is easily executed.

Attack Tree Path: 1.2.2. Use Very Large Input Tileset [CN] [HR]

  • Description: The attacker provides a tileset with a huge number of individual tiles. This increases the memory required to store the tileset and the possible tile combinations.
  • Example: A tileset with tens of thousands of unique tiles.

Attack Tree Path: 1.2.2.1. Bypass Input Validation (if present) [CN] [HR]

  • Description: If the application doesn't limit the size or number of tiles in the tileset, this attack is easily executed.

Attack Tree Path: 1.3. Excessive CPU Consumption [HR]

  • Description: The attacker aims to overload the CPU, making the application slow or unresponsive.

Attack Tree Path: 1.3.1. Provide Complex Tileset with Many Constraints [HR]

  • Description: The attacker creates a tileset with a large number of complex rules governing how tiles can connect. This increases the computational cost of resolving constraints.
  • Example: A tileset where each tile has many specific rules about which other tiles it can be adjacent to, based on multiple factors.

Attack Tree Path: 1.3.1.1. Bypass Input Validation (if present) [CN] [HR]

  • Description: If the application doesn't limit the complexity or number of constraints in the tileset, this attack becomes more effective.

Attack Tree Path: 1.3.3. Provide Extremely Large Output Dimensions [CN] [HR]

  • Description: The attacker specifies an extremely large width, height, or depth for the output grid. This can lead to excessive memory allocation or CPU usage, even if the tileset itself is simple.
  • Example: Requesting an output grid of size 1000000x1000000.

Attack Tree Path: 1.3.3.1. Bypass Input Validation (if present) [CN] [HR]

  • Description: If the application doesn't properly limit the size of the output dimensions, this attack is easily executed.

Attack Tree Path: 2. Predictable / Undesirable Output

Attack Tree Path: 2.1. Manipulate Random Number Generator (RNG) [CN]

  • Description: The attacker aims to control or predict the random choices made by the WFC algorithm, thereby influencing the output.

Attack Tree Path: 2.1.1. Predict RNG Seed (if exposed or predictable) [CN]

  • Description: If the application uses a predictable or exposed seed for its random number generator, the attacker can determine the sequence of random numbers that will be generated and thus predict the output.
  • Example: Using the current timestamp as the seed without any additional entropy.

Attack Tree Path: 2.1.1.1. Exploit Weak Seed Generation or Storage [CN]

  • Description: This encompasses any vulnerability that allows the attacker to learn or guess the RNG seed.

Attack Tree Path: 2.2. Force Specific Tile Choices

Attack Tree Path: 2.2.1.1. Exploit Weak Constraint Checking (if present) [CN]

  • Description: If constraint checking is weak, an attacker can craft a tileset that, while appearing valid, severely limits the possible outputs, forcing specific tile choices or patterns.

Attack Tree Path: 2.3. Bias Output Distribution

Attack Tree Path: 2.3.1.1. Exploit Unprotected Access to Tile Weights [CN]

  • Description: If the application allows users to specify weights for different tiles (influencing their probability of being chosen), and if these weights are not properly validated or protected, the attacker can manipulate them to bias the output.