Requests firewall (Java 17)

README.md

Java 17 Firewall

A Java "firewall" that given a list of blacklisted ips (with wildcards) and a list of ips can return a list of int where each number indicates if the request is successful or blocked.

A request is blocked if it matches one of the blacklisted patterns or if another successful request was made in the last 5 seconds (rate limiter).

The implementation uses a Trie for fast ip look ups and backtracking.

Solution.java

package com.conizzoli.demo;

import java.util.Arrays;
import java.util.HashMap;

public class Solution {
  public static void main(String[] args) {
    System.out.println(Arrays.toString(Solution.filterRequests(
      new String[]{"1.0.100.*", "192.168.*.*"},
      new String[]{"1.0.100.*", "10.10.10.10", "1.0.100.1", "192.168.1.1", "192.168.1.1", "192.168.1.1", "192.168.1.1", "10.10.10.10"}
    )));
  }

  public static int[] filterRequests(String[] filters, String[] requests) {
    var result = new int[requests.length];
    var trie = new Trie(filters);

    for (var i = 0; i < requests.length; i++) {
      var request = requests[i];
      var isValid = Solution.isValidForRateLimiter(request, requests, i, result)
        && !Solution.isIpBlacklisted(trie, request);
      result[i] = isValid ? 1 : 0;
      requests[i] = isValid ? requests[i] : "";
    }

    return result;
  }

  private static boolean isValidForRateLimiter(String request, String[] requests, int index, int[] validRequests) {
    for (var i = Math.max(0, index - 4); i < index; i++) {
      if (requests[i].equals(request) && validRequests[i] == 1) {
        return false;
      }
    }

    return true;
  }

  private static boolean isIpBlacklisted(Trie trie, String request) {
    return trie.hasWordWithWildcards(request);
  }
}

class Trie {
  private final TrieNode root;

  public Trie(String[] strings) {
    this.root = new TrieNode();

    for (var string : strings) {
      var node = this.root;
      for (var letter : string.toCharArray()) {
        node = node.getOrAdd(letter);
      }
      node.markAsWord();
    }
  }

  public boolean hasWordWithWildcards(String word) {
    return this.hasWordWithWildcardsRecursive(word, 0, this.root);
  }

  private boolean hasWordWithWildcardsRecursive(String word, int index, TrieNode node) {
    if (node == null) {
      return false;
    }

    if (index == word.length()) {
      return node.isWord();
    }

    var letter = word.charAt(index);

    // Check for perfect match
    var result = this.hasWordWithWildcardsRecursive(word, index + 1, node.get(letter));

    // Check for wildcard match
    var wildcardNode = node.get('*');
    result = result || this.hasWordWithWildcardsRecursive(word, index + 1, wildcardNode);
    if (wildcardNode != null) {
      result = result || this.hasWordWithWildcardsRecursive(word, index + 1, node);
    }

    return result;
  }
}

class TrieNode {
  private final HashMap<Character, TrieNode> children = new HashMap<>();
  private boolean isWord = false;

  public TrieNode getOrAdd(char letter) {
    var node = this.children.get(letter);

    if (node == null) {
      node = new TrieNode();
      this.children.put(letter, node);
    }

    return node;
  }

  public TrieNode get(char letter) {
    return this.children.get(letter);
  }

  public void markAsWord() {
    this.isWord = true;
  }

  public boolean isWord() {
    return this.isWord;
  }
}

SolutionTest.java

package com.conizzoli.demo;

import static org.junit.jupiter.api.Assertions.*;

import java.util.stream.Stream;
import org.junit.jupiter.params.ParameterizedTest;
import org.junit.jupiter.params.provider.Arguments;
import org.junit.jupiter.params.provider.MethodSource;

public class SolutionTest {
  @ParameterizedTest
  @MethodSource("provideFilterRequestsUseCases")
  void itFiltersRequests(String[] filters, String[] requests, int[] expectedResult) {
     int[] results = Solution.filterRequests(filters, requests);
     assertArrayEquals(expectedResult, results);
  }

  static Stream<Arguments> provideFilterRequestsUseCases() {
    return Stream.of(
      Arguments.of(new String[]{"192.168.*.*"}, new String[]{"192.168.1.1", "192.169.1.1"}, new int[]{0, 1}),
      Arguments.of(new String[]{"10.0.*.*", "172.16.1.*"}, new String[]{"10.0.0.1", "172.16.1.2", "172.16.2.1"}, new int[]{0, 0, 1}),
      Arguments.of(new String[]{}, new String[]{"8.8.8.8", "1.1.1.1"}, new int[]{1, 1}),
      Arguments.of(new String[]{"*.*.*.*"}, new String[]{"192.168.1.1", "10.0.0.1"}, new int[]{0, 0}),
      Arguments.of(new String[]{"192.168.1.*", "10.*.*.*"}, new String[]{"192.168.1.100", "10.1.1.1", "172.16.0.1"}, new int[]{0, 0, 1}),
      Arguments.of(new String[]{"172.20.*.*", "192.168.1.1"}, new String[]{"172.20.1.1", "192.168.1.1", "192.168.1.2"}, new int[]{0, 0, 1}),
      Arguments.of(new String[]{"192.*.*.1", "10.10.*.*"}, new String[]{"192.168.0.1", "10.10.1.1", "192.168.1.2"}, new int[]{0, 0, 1}),
      Arguments.of(new String[]{"172.16.*.1", "192.168.2.*"}, new String[]{"172.16.0.1", "192.168.2.2", "172.16.1.2"}, new int[]{0, 0, 1}),
      Arguments.of(new String[]{"*.*.1.1", "*.*.2.2"}, new String[]{"192.168.1.1", "10.0.2.2", "172.16.3.3"}, new int[]{0, 0, 1}),
      Arguments.of(new String[]{"192.168.1.1", "10.0.0.*", "172.16.*.2"}, new String[]{"192.168.1.1", "10.0.0.2", "172.16.1.2", "172.17.1.2"}, new int[]{0, 0, 0, 1}),

      Arguments.of(new String[]{}, new String[]{"192.168.1.1", "192.168.1.1", "192.168.1.1", "192.168.1.1", "192.168.1.1", "192.168.1.1"}, new int[]{1, 0, 0, 0, 0, 1}),
      Arguments.of(new String[]{}, new String[]{"192.168.1.1", "10.0.0.1", "192.168.1.1", "10.0.0.1", "192.168.1.1", "10.0.0.1"}, new int[]{1, 1, 0, 0, 0, 0}),
      Arguments.of(new String[]{}, new String[]{"192.168.1.1", "192.168.1.1", "192.168.1.1", "192.168.1.1", "192.168.1.1", "192.168.1.1", "192.168.1.1", "192.168.1.1", "192.168.1.1", "192.168.1.1"}, new int[]{1, 0, 0, 0, 0, 1, 0, 0, 0, 0})
    );
  }
}