High-performance Shannon entropy calculation and regex secret detection benchmarks in Python and Rust

Starred Gists，GitHub Gist，即时分享代码、笔记与代码片段。关注

Fast Shannon Entropy Secret Detection Benchmark

Comparative implementations in Python 3 and Rust demonstrating zero-allocation frequency table calculation for detecting high-entropy credentials (AWS keys, GitHub tokens, JWTs, Base64 secrets).

Mathematical Foundation

Shannon Entropy measures information density (in bits per symbol):

$H(X) = -\sum_{i=1}^{n} P(x_i) \log_2 P(x_i)$

Where:

$n \le 256$ is the distinct alphabet byte space
$P(x_i) = \frac{\text{count}(x_i)}{N}$ is empirical probability
Thresholds:
- English source code / comments: $2.5 - 3.8\text{ bits/char}$
- Hex hashes / UUIDs: $3.5 - 3.9\text{ bits/char}$
- Base64 / Encrypted Tokens:
  amp;gt; 4.3\text{ bits/char}$

Performance Highlights

Implementation	Ops/Sec	Allocation Overhead
Python `collections.Counter`	~120,000 ops/s	High (dict alloc per call)
Python Bytearray Lookup	~680,000 ops/s	Low (reused byte table)
Rust Stack-allocated Slice	> 14,500,000 ops/s	Zero heap allocation

Running the Examples

# Run Python benchmark
python benchmark_entropy.py

# Compile and run Rust benchmark
rustc -O entropy_scanner.rs && ./entropy_scanner

	"""
	Benchmark Shannon Entropy Calculation in Python
	Compares naive string counting, Counter-based, and bytearray table lookup.
	"""

	import math
	import time
	import random
	import string
	from collections import Counter
	from typing import Dict, List, Tuple


	def shannon_entropy_naive(data: str) -> float:
	"""Calculate Shannon entropy using standard math.log2 and dict."""
	if not data:
	return 0.0
	length = len(data)
	counts = Counter(data)
	entropy = 0.0
	for count in counts.values():
	p = count / length
	entropy -= p * math.log2(p)
	return entropy


	def shannon_entropy_byte_array(data: bytes) -> float:
	"""Optimized byte-array frequency table entropy calculation."""
	length = len(data)
	if length == 0:
	return 0.0
	counts = [0] * 256
	for b in data:
	counts[b] += 1

	inv_length = 1.0 / length
	log2_inv = 1.0 / math.log(2.0)
	entropy = 0.0
	for count in counts:
	if count > 0:
	p = count * inv_length
	entropy -= p * math.log(p) * log2_inv
	return entropy


	def is_high_entropy(data: str, threshold: float = 4.5) -> bool:
	"""Determine if a token represents high randomness (API keys, secrets)."""
	return shannon_entropy_byte_array(data.encode('utf-8')) >= threshold


	def run_benchmark(iterations: int = 25000) -> None:
	print(f"=== Shannon Entropy Python Benchmark ({iterations:,} iterations) ===")

	# Generate test corpus
	alphabet = string.ascii_letters + string.digits + "+/="
	samples = [
	"".join(random.choices(alphabet, k=random.randint(20, 64)))
	for _ in range(1000)
	]

	# 1. Counter based
	t0 = time.perf_counter()
	for i in range(iterations):
	sample = samples[i % len(samples)]
	_ = shannon_entropy_naive(sample)
	t1 = time.perf_counter()
	duration_naive = t1 - t0
	ops_sec_naive = iterations / duration_naive
	print(f"Counter-based implementation: {duration_naive:.4f}s \| {ops_sec_naive:,.0f} ops/sec")

	# 2. Byte array table
	byte_samples = [s.encode('utf-8') for s in samples]
	t0 = time.perf_counter()
	for i in range(iterations):
	sample = byte_samples[i % len(byte_samples)]
	_ = shannon_entropy_byte_array(sample)
	t1 = time.perf_counter()
	duration_bytes = t1 - t0
	ops_sec_bytes = iterations / duration_bytes
	print(f"Bytearray lookup table: {duration_bytes:.4f}s \| {ops_sec_bytes:,.0f} ops/sec")
	print(f"Speedup: {ops_sec_bytes / ops_sec_naive:.2f}x\n")

	# Test sample entropy values
	test_cases: List[Tuple[str, str]] = [
	("English text", "The quick brown fox jumps over the lazy dog"),
	("Low entropy string", "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"),
	("Hex digest (32 chars)", "e3b0c44298fc1c149afbf4c8996fb924"),
	("AWS Secret Access Key", "wJalrXUtnFEMI/K7MDENG/bPxRfiCYEXAMPLEKEY"),
	("High entropy base64", "4k8aQxZ+9YlKmT2p1gNxRtV8sDuW3+Q=="),
	]

	print("Sample Token Analysis:")
	for label, text in test_cases:
	ent = shannon_entropy_byte_array(text.encode('utf-8'))
	flag = "FLAGGED SECRET" if ent >= 4.0 else "SAFE / LOW"
	print(f" [{ent:.3f} bits/byte] {label:<24}: {text[:30]:<30} -> {flag}")


	if __name__ == "__main__":
	run_benchmark()

	//! High-speed Shannon Entropy & Secret Scanner in Rust
	//! Designed for zero-allocation git diff scanning.

	use std::time::Instant;

	/// Calculate Shannon entropy using a fixed 256-element frequency table.
	/// Operates directly on raw byte slices without heap allocation.
	#[inline]
	pub fn shannon_entropy(bytes: &[u8]) -> f64 {
	if bytes.is_empty() {
	return 0.0;
	}

	let mut freq = [0u32; 256];
	for &b in bytes {
	freq[b as usize] += 1;
	}

	let len = bytes.len() as f64;
	let inv_len = 1.0 / len;
	let mut entropy = 0.0;

	for &count in freq.iter() {
	if count > 0 {
	let p = count as f64 * inv_len;
	entropy -= p * p.log2();
	}
	}

	entropy
	}

	/// Fast candidate secret validator with sliding window
	pub fn scan_for_secrets<'a>(text: &'a str, min_len: usize, threshold: f64) -> Vec<(&'a str, f64)> {
	let mut findings = Vec::new();
	for token in text.split_whitespace() {
	// Strip common wrapping delimiters
	let clean = token.trim_matches(\|c\| c == '"' \|\| c == '\'' \|\| c == '`' \|\| c == ';' \|\| c == ',');
	if clean.len() >= min_len {
	let ent = shannon_entropy(clean.as_bytes());
	if ent >= threshold {
	findings.push((clean, ent));
	}
	}
	}
	findings
	}

	fn main() {
	println!("=== Rust Fast Shannon Entropy Scanner Benchmark ===");

	let corpus = [
	"const AWS_KEY = \"AKIAIOSFODNN7EXAMPLE\";",
	"const SECRET = \"wJalrXUtnFEMI/K7MDENG/bPxRfiCYEXAMPLEKEY\";",
	"let regular_comment = \"this is a completely normal developer comment\";",
	"let base64_rand = \"9V/m+FqJzG7p2e8xLaK+Wn0sQdZ1vC4yM6rPt=\" ;",
	];

	let iterations = 1_000_000;
	let start = Instant::now();
	let mut dummy_sum = 0.0;

	for i in 0..iterations {
	let line = corpus[i % corpus.len()];
	let findings = scan_for_secrets(line, 16, 4.2);
	for (_, score) in findings {
	dummy_sum += score;
	}
	}

	let elapsed = start.elapsed();
	let throughput = iterations as f64 / elapsed.as_secs_f64();

	println!("Scanned {} iterations in {:.3?}", iterations, elapsed);
	println!("Throughput: {:.2} million evaluations/sec", throughput / 1_000_000.0);
	println!("Verification checksum: {:.2}", dummy_sum);
	}

添加评论

点踩

分享查看原文

参与讨论