Vulnerable Implementation for Unordered Map

Understanding Vulnerabilities of Unordered Map:

Secure Unordered Map from Collision Attacks:

A simple code snippet illustrates the vulnerability by measuring execution time for different primes:

C++

#include <ctime>
#include <iostream>
#include <unordered_map>

const int N = 2e5;

void insert_numbers(long long x)
{
    clock_t begin = clock();
    std::unordered_map<long long, int> numbers;

    for (int i = 1; i <= N; i++)
        numbers[i * x] = i;

    long long sum = 0;

    for (const auto& entry : numbers)
        sum += (entry.first / x) * entry.second;

    std::cout << "x = " << x << ": " << std::fixed
            << static_cast<double>(clock() - begin) / CLOCKS_PER_SEC
            << " seconds, sum = " << sum << "\n";
}

int main()
{
    insert_numbers(107897);
    insert_numbers(126271);

    return 0;
}
// Note: differences in language semantics, standard libraries, data structure
//implementations, and time measurement mechanisms can lead to 
//variations in execution time and output.

Java

import java.util.HashMap;
import java.util.Map;

public class Main {
    static final int N = 200000;

    static void insertNumbers(long x) {
        long startTime = System.nanoTime();
        Map<Long, Integer> numbers = new HashMap<>();

        for (int i = 1; i <= N; i++) {
            numbers.put((long) i * x, i);
        }

        long sum = 0;

        for (Map.Entry<Long, Integer> entry : numbers.entrySet()) {
            sum += (entry.getKey() / x) * entry.getValue();
        }

        double elapsedTime = (System.nanoTime() - startTime) / 1e9;
        System.out.printf("x = %d: %.6f seconds, sum = %d%n", x, elapsedTime, sum);
    }

    public static void main(String[] args) {
        insertNumbers(107897);
        insertNumbers(126271);
    }
}
// Note: differences in language semantics, standard libraries, data structure
//implementations, and time measurement mechanisms can lead to 
//variations in execution time and output.

Python

import time

N = int(2e5)

def insert_numbers(x):
    # Measure the start time
    begin = time.time()
    # Initialize an empty dictionary to store numbers and their corresponding indices
    numbers = {}

    # Populate the dictionary with numbers and their indices
    for i in range(1, N + 1):
        numbers[i * x] = i

    # Initialize sum
    sum_val = 0

    # Calculate the sum by iterating through the dictionary
    for key, value in numbers.items():
        sum_val += (key // x) * value

    # Calculate the time taken and print the result using the format method
    print("x = {}: {:.6f} seconds, sum = {}".format(x, time.time() - begin, sum_val))

def main():
    # Call insert_numbers function with different values of x
    insert_numbers(107897)
    insert_numbers(126271)

if __name__ == "__main__":
    main()
# Note: differences in language semantics, standard libraries, data structure
# implementations, and time measurement mechanisms can lead to 
# variations in execution time and output.

using System;
using System.Collections.Generic;
using System.Diagnostics;

public class Program
{
    const int N = 200000;

    // Method to insert numbers into a dictionary and calculate sum
    static void InsertNumbers(long x)
    {
        // Start measuring time
        Stopwatch stopwatch = new Stopwatch();
        stopwatch.Start();

        // Dictionary to store key-value pairs
        Dictionary<long, int> numbers = new Dictionary<long, int>();

        // Insert numbers into the dictionary
        for (int i = 1; i <= N; i++)
        {
            numbers[i * x] = i;
        }

        // Variable to store the sum
        long sum = 0;

        // Calculate sum using dictionary entries
        foreach (var entry in numbers)
        {
            sum += (entry.Key / x) * entry.Value;
        }

        // Stop measuring time
        stopwatch.Stop();

        // Output the result
        Console.WriteLine($"x = {x}: {stopwatch.Elapsed.TotalSeconds} seconds, sum = {sum}");
    }

    // Main method, entry point of the program
    public static void Main(string[] args)
    {
        // Call InsertNumbers method with different values
        InsertNumbers(107897);
        InsertNumbers(126271);
    }
}

// Note: differences in language semantics, standard libraries, data structure
//implementations, and time measurement mechanisms can lead to 
//variations in execution time and output.

JavaScript

// Import the 'performance-now' module to measure time in milliseconds
const { performance } = require('perf_hooks');

const N = 2e5;

// Function to insert numbers into a dictionary and calculate their sum
function insertNumbers(x) {
    // Measure the start time
    const begin = performance.now();
    // Initialize an empty object to store numbers and their corresponding indices
    const numbers = {};

    // Populate the object with numbers and their indices
    for (let i = 1; i <= N; i++) {
        numbers[i * x] = i;
    }

    // Initialize sum
    let sum = 0;

    // Calculate the sum by iterating through the object
    for (const key in numbers) {
        sum += Math.floor(key / x) * numbers[key];
    }

    // Calculate the time taken and print the result using the 'toFixed' method
    console.log(`x = ${x}: ${(performance.now() - begin).toFixed(6)} milliseconds, sum = ${sum}`);
}

// Main function
function main() {
    // Call insertNumbers function with different values of x
    insertNumbers(107897);
    insertNumbers(126271);
}

// Call the main function to execute the code
main();

// Note: differences in language semantics, standard libraries, data structure
//implementations, and time measurement mechanisms can lead to 
//variations in execution time and output.

Output:

x = 107897: 0.062000 seconds, sum = 2666686666700000
x = 126271: 56.123000 seconds, sum = 2666686666700000

Optimization for Unordered Map O(1) operations

C++ provides convenient data structures like std::set and std::map, tree-based structures with operations taking O(log n) time. With C++11, hash-based alternatives were introduced: std::unordered_set and std::unordered_map. However, concerns arise regarding potential vulnerabilities and efficiency in real-world scenarios. In this article, we’re going to explore strategies to optimize unordered maps for O(1) operations and address security issues.

Table of Content

Implementation of Unordered Map
Understanding Vulnerabilities of Unordered Map
Vulnerable Implementation for Unordered Map
Secure Unordered Map from Collision Attacks
Better Implementation of Unordered Map

Vulnerable Implementation for Unordered Map

Optimization for Unordered Map O(1) operations

Similar Reads