password_strength/analyzer/

pattern.rs

use crate::analyzer::Analyzer;
use std::collections::{HashMap, HashSet};
use unicode_segmentation::UnicodeSegmentation;

/// Represents a pattern string, typically part of a keyboard layout or sequence.
type PatternString = &'static str;
/// Represents a row on a standard keyboard layout.
type KeyboardRow = PatternString;
/// Represents a column (or diagonal) on a standard keyboard layout.
type KeyboardColumn = PatternString;
/// Represents a common character sequence (e.g., alphabet, numbers).
type CharSequence = PatternString;
/// Represents a common character substitution (original character, substituted character).
type Substitution = (&'static str, &'static str);

/// Configuration constants for pattern detection penalties.
const MIN_PATTERN_LENGTH: usize = 3;
const DEFAULT_MAX_KEYBOARD_PENALTY: f32 = 0.30;
const DEFAULT_MAX_REPEAT_PENALTY: f32 = 0.30;
const DEFAULT_MAX_SEQUENCE_PENALTY: f32 = 0.25;
const DEFAULT_MAX_SUBSTITUTION_PENALTY: f32 = 0.15;
const DEFAULT_HIGH_FREQUENCY_THRESHOLD: f32 = 0.35;

/// `PatternAnalyzer` analyzes passwords for common weak patterns.
///
/// It checks for:
/// - Keyboard patterns (e.g., "qwerty", "asdf").
/// - Repeated characters (consecutive like "aaa" or high frequency like "banana").
/// - Sequential characters (e.g., "abc", "123").
/// - Common character substitutions (e.g., "@" for "a", "3" for "e").
/// - Repeated sequences (e.g., "abcabc", "passpass").
///
/// Penalties are applied for each detected weakness, reducing the overall score from 1.0.
///
/// # Examples
///
/// ```
/// use password_strength::analyzer::{Analyzer, pattern::PatternAnalyzer};
///
/// let analyzer = PatternAnalyzer::default();
/// println!("Score for 'qwerty12345': {}", analyzer.analyze("qwerty12345"));
/// println!("Score for 'P@sswOrd!': {}", analyzer.analyze("P@sswOrd!"));
/// ```
#[derive(Debug, Clone)]
pub struct PatternAnalyzer {
    keyboard_rows: Vec<KeyboardRow>,
    keyboard_columns: Vec<KeyboardColumn>,
    char_sequences: Vec<CharSequence>,
    substitution_map: HashMap<char, Vec<char>>,
    substitution_chars: HashSet<char>,
    min_pattern_length: usize,
    max_keyboard_penalty: f32,
    max_repeat_penalty: f32,
    max_sequence_penalty: f32,
    max_substitution_penalty: f32,
    high_frequency_threshold: f32,
}

impl Default for PatternAnalyzer {
    fn default() -> Self {
        let substitution_patterns: Vec<Substitution> = vec![
            ("a", "@"),
            ("a", "4"),
            ("e", "3"),
            ("i", "1"),
            ("i", "!"),
            ("o", "0"),
            ("s", "$"),
            ("s", "5"),
            ("t", "7"),
            ("l", "1"),
        ];

        let mut substitution_map = HashMap::new();
        let mut substitution_chars = HashSet::new();
        for (original, substitution) in substitution_patterns {
            if let (Some(orig_char), Some(sub_char)) =
                (original.chars().next(), substitution.chars().next())
            {
                substitution_map
                    .entry(sub_char)
                    .or_insert_with(Vec::new)
                    .push(orig_char);
                substitution_chars.insert(sub_char);
            }
        }

        PatternAnalyzer {
            keyboard_rows: vec!["qwertyuiop", "asdfghjkl", "zxcvbnm", "`1234567890-="],
            keyboard_columns: vec![
                "`1qaz", "2wsx", "3edc", "4rfv", "5tgb", "6yhn", "7ujm", "8ik,", "9ol.", "0p;/",
                "-[", "='",
            ],
            char_sequences: vec!["abcdefghijklmnopqrstuvwxyz", "0123456789", "~!@#$%^&*()_+"],
            substitution_map,
            substitution_chars,
            min_pattern_length: MIN_PATTERN_LENGTH,
            max_keyboard_penalty: DEFAULT_MAX_KEYBOARD_PENALTY,
            max_repeat_penalty: DEFAULT_MAX_REPEAT_PENALTY,
            max_sequence_penalty: DEFAULT_MAX_SEQUENCE_PENALTY,
            max_substitution_penalty: DEFAULT_MAX_SUBSTITUTION_PENALTY,
            high_frequency_threshold: DEFAULT_HIGH_FREQUENCY_THRESHOLD,
        }
    }
}

impl PatternAnalyzer {
    /// Detects keyboard patterns (rows, columns, diagonals) in the password.
    /// Operates on the lowercase version of the password.
    fn detect_keyboard_patterns(&self, password_lowercase: &str) -> f32 {
        let mut penalty = 0.0;

        let all_keyboard_patterns = self
            .keyboard_rows
            .iter()
            .chain(self.keyboard_columns.iter());

        for pattern_set in all_keyboard_patterns {
            penalty += self.find_patterns_in_string(pattern_set, password_lowercase);
        }

        penalty.min(self.max_keyboard_penalty)
    }

    /// Helper function to find occurrences of patterns (and their reverses) from a source string within the password.
    fn find_patterns_in_string(&self, pattern_source: &str, password_lowercase: &str) -> f32 {
        let mut current_penalty = 0.0;
        let password_len = password_lowercase.graphemes(true).count();
        if password_len == 0 {
            return 0.0;
        }

        for len in self.min_pattern_length..=password_len {
            for password_subsequence in password_lowercase
                .graphemes(true)
                .collect::<Vec<&str>>()
                .windows(len)
            {
                let sub: String = password_subsequence.join("");
                let sub_rev: String = sub.chars().rev().collect();

                if pattern_source.contains(&sub) || pattern_source.contains(&sub_rev) {
                    current_penalty += 0.03 + (len as f32 - self.min_pattern_length as f32) * 0.015;
                }
            }
        }
        current_penalty
    }

    /// Detects repeated characters:
    /// 1. Consecutive identical characters (e.g., "aaa", "bbb"). Penalizes *each* run >= 3.
    /// 2. High frequency of any single character.
    fn detect_repeated_characters(&self, password: &str) -> f32 {
        let mut consecutive_penalty = 0.0;
        let mut frequency_penalty = 0.0;
        let graphemes: Vec<&str> = password.graphemes(true).collect();
        let password_len = graphemes.len();

        if password_len < 2 {
            return 0.0;
        }

        let mut current_consecutive_repeat = 1;
        for i in 1..password_len {
            if graphemes[i].eq_ignore_ascii_case(graphemes[i - 1]) {
                current_consecutive_repeat += 1;
            } else {
                if current_consecutive_repeat >= 3 {
                    consecutive_penalty +=
                        0.05 * (current_consecutive_repeat - (self.min_pattern_length - 1)) as f32;
                }
                current_consecutive_repeat = 1;
            }
        }
        if current_consecutive_repeat >= 3 {
            consecutive_penalty +=
                0.05 * (current_consecutive_repeat - (self.min_pattern_length - 1)) as f32;
        }

        let mut char_counts = HashMap::new();
        for g in &graphemes {
            for c in g.chars() {
                for lower_c in c.to_lowercase() {
                    *char_counts.entry(lower_c).or_insert(0) += 1;
                }
            }
        }

        let total_chars = password.chars().count() as f32;
        if total_chars > 0.0 {
            for count in char_counts.values() {
                let ratio = *count as f32 / total_chars;
                if ratio > self.high_frequency_threshold {
                    frequency_penalty += (ratio - self.high_frequency_threshold) * 0.5;
                }
            }
        }

        (consecutive_penalty + frequency_penalty).min(self.max_repeat_penalty)
    }

    /// Detects sequential characters (alphabetic, numeric, common symbols).
    /// Finds contiguous sequences and penalizes based on their length.
    /// Operates on the lowercase version of the password.
    fn detect_sequential_characters(&self, password_lowercase: &str) -> f32 {
        let mut penalty = 0.0;
        let pass_chars: Vec<char> = password_lowercase.chars().collect();
        let n = pass_chars.len();

        if n < self.min_pattern_length {
            return 0.0;
        }

        let mut i = 0;
        while i < n {
            let mut longest_sequence_len = 0;
            for sequence_source in &self.char_sequences {
                let source_chars: Vec<char> = sequence_source.chars().collect();
                let source_n = source_chars.len();

                for j in 0..source_n {
                    let mut current_match_len = 0;
                    while i + current_match_len < n && j + current_match_len < source_n {
                        if pass_chars[i + current_match_len] == source_chars[j + current_match_len]
                        {
                            current_match_len += 1;
                        } else {
                            break;
                        }
                    }

                    let mut current_rev_match_len = 0;
                    while i + current_rev_match_len < n && j + current_rev_match_len < source_n {
                        if pass_chars[i + current_rev_match_len]
                            == source_chars[source_n - 1 - (j + current_rev_match_len)]
                        {
                            current_rev_match_len += 1;
                        } else {
                            break;
                        }
                    }

                    longest_sequence_len = longest_sequence_len
                        .max(current_match_len)
                        .max(current_rev_match_len);
                }
            }

            if longest_sequence_len >= self.min_pattern_length {
                penalty +=
                    0.03 + (longest_sequence_len as f32 - self.min_pattern_length as f32) * 0.02;
                i += longest_sequence_len;
            } else {
                i += 1;
            }
        }

        penalty.min(self.max_sequence_penalty)
    }

    /// Detects common character substitutions (e.g., "@" for "a", "3" for "e").
    /// Penalizes based on the *presence* of substitution characters from the predefined list.
    fn detect_common_substitutions(&self, password: &str) -> f32 {
        let mut penalty: f32 = 0.0;
        let mut found_substitution_types = HashSet::new();

        for grapheme in password.graphemes(true) {
            if let Some(c) = grapheme.chars().next() {
                if self.substitution_chars.contains(&c) && found_substitution_types.insert(c) {
                    penalty += 0.04;
                }
            }
        }

        penalty.min(self.max_substitution_penalty)
    }

    /// Detects repeated patterns or sequences within the password (e.g., "abcabc", "testtest").
    fn detect_repeated_patterns(&self, password: &str) -> f32 {
        let mut penalty = 0.0;
        let graphemes: Vec<&str> = password.graphemes(true).collect();
        let n = graphemes.len();

        if n < self.min_pattern_length * 2 {
            return 0.0;
        }

        for len in self.min_pattern_length..=(n / 2) {
            let mut occurrences = HashMap::new();

            for i in 0..=(n - len) {
                let pattern_slice = &graphemes[i..(i + len)];
                let pattern_key: String = pattern_slice.join("").to_lowercase();

                for j in 0..=(n - len) {
                    if i == j {
                        continue;
                    }
                    let compare_slice = &graphemes[j..(j + len)];
                    let compare_key: String = compare_slice.join("").to_lowercase();

                    if pattern_key == compare_key {
                        *occurrences.entry(pattern_key.clone()).or_insert(0) += 1;
                        break;
                    }
                }
            }

            for count in occurrences.values() {
                if *count > 1 {
                    penalty += 0.02 + (len as f32 * 0.005) + (*count as f32 * 0.005);
                }
            }
        }

        penalty.min(self.max_repeat_penalty)
    }
}

impl Analyzer for PatternAnalyzer {
    /// Analyzes the password strength based on detected patterns.
    /// Returns a score between 0.0 (weakest) and 1.0 (strongest relative to patterns).
    fn analyze(&self, password: &str) -> f32 {
        let password_len = password.graphemes(true).count();

        if password_len < self.min_pattern_length {
            return 1.0;
        }

        let password_lowercase = password.to_lowercase();

        let mut score = 1.0;

        let keyboard_penalty = self.detect_keyboard_patterns(&password_lowercase);
        let repeat_penalty = self.detect_repeated_characters(password);
        let sequence_penalty = self.detect_sequential_characters(&password_lowercase);
        let substitution_penalty = self.detect_common_substitutions(password);
        let repeated_pattern_penalty = self.detect_repeated_patterns(password);

        score -= keyboard_penalty;
        score -= repeat_penalty;
        score -= sequence_penalty;
        score -= substitution_penalty;
        score -= repeated_pattern_penalty;

        score.clamp(0.0, 1.0)
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    fn default_analyzer() -> PatternAnalyzer {
        PatternAnalyzer::default()
    }

    macro_rules! assert_score_between {
        ($score:expr, $min:expr, $max:expr) => {
            assert!(
                $score >= $min && $score <= $max,
                "Score {} is not between {} and {}",
                $score,
                $min,
                $max
            );
        };
    }

    #[test]
    fn test_empty_password() {
        let analyzer = default_analyzer();
        assert_eq!(analyzer.analyze(""), 1.0, "Empty password score");
    }

    #[test]
    fn test_short_password() {
        let analyzer = default_analyzer();
        assert_eq!(analyzer.analyze("a"), 1.0, "Single char password score");
        assert_eq!(analyzer.analyze("ab"), 1.0, "Two char password score");
    }

    #[test]
    fn test_no_patterns() {
        let analyzer = default_analyzer();
        let score = analyzer.analyze("R#tG$yH7kL*p");
        assert_score_between!(score, 0.9, 1.0);
    }

    #[test]
    fn test_keyboard_row_pattern() {
        let analyzer = default_analyzer();
        let score_qwerty = analyzer.analyze("qwertyuiop");
        let score_asdf = analyzer.analyze("asdfghjkl");
        let score_zxcv = analyzer.analyze("zxcvbnm");
        let score_123 = analyzer.analyze("1234567890");
        let score_mixed = analyzer.analyze("myasdfpass");

        assert!(score_qwerty < 0.8, "qwerty penalty");
        assert!(score_asdf < 0.8, "asdf penalty");
        assert!(score_zxcv < 0.8, "zxcv penalty");
        assert!(score_123 < 0.8, "123 penalty");
        assert!(score_mixed < 1.0, "mixed asdf penalty");
    }

    #[test]
    fn test_keyboard_column_pattern() {
        let analyzer = default_analyzer();
        let score_qaz = analyzer.analyze("qazwsx");
        assert!(score_qaz < 1.0, "qaz column penalty expected");
    }

    #[test]
    fn test_keyboard_reversed_pattern() {
        let analyzer = default_analyzer();
        let score_rev_qwerty = analyzer.analyze("poiuytrewq");
        let score_rev_asdf = analyzer.analyze("lkjhgfdsa");
        assert!(score_rev_qwerty < 0.8, "reversed qwerty penalty");
        assert!(score_rev_asdf < 0.8, "reversed asdf penalty");
    }

    #[test]
    fn test_keyboard_case_insensitive() {
        let analyzer = default_analyzer();
        let score_upper = analyzer.analyze("QWERTY");
        let score_mixed = analyzer.analyze("qWeRtY");
        assert!(score_upper < 0.8, "Uppercase QWERTY penalty");
        assert!(score_mixed < 0.8, "Mixed case qwerty penalty");
    }

    #[test]
    fn test_repeated_consecutive_chars() {
        let analyzer = default_analyzer();
        let score_aaa = analyzer.analyze("testaaa");
        let score_aaaaa = analyzer.analyze("testaaaaa");
        let score_end = analyzer.analyze("testingggg");
        let score_multi = analyzer.analyze("aaabbbccc");

        assert!(score_aaa < 1.0, "aaa penalty");
        assert!(score_aaaaa < score_aaa, "aaaaa more penalized than aaa");
        assert!(score_end < 1.0, "end gggg penalty");
        assert!(
            score_multi < 0.9,
            "a multi-repeat penalty should be significant"
        );
    }

    #[test]
    fn test_repeated_chars_case_insensitive() {
        let analyzer = default_analyzer();
        let score_a_aaa = analyzer.analyze("testaAaa");
        assert!(score_a_aaa < 1.0, "aAaa penalty");
    }

    #[test]
    fn test_repeated_high_frequency() {
        let analyzer = default_analyzer();
        let score_banana = analyzer.analyze("banana");
        let score_papapa = analyzer.analyze("papapapapapapapa");
        let score_distinct = analyzer.analyze("abcdefghijkl");

        assert!(score_banana < 1.0, "banana frequency penalty");
        assert!(score_papapa < 0.7, "papapa high-frequency penalty");
        assert_score_between!(score_distinct, 0.70, 0.85);
    }

    #[test]
    fn test_sequential_alpha() {
        let analyzer = default_analyzer();
        let score_abc = analyzer.analyze("abcdef");
        let score_xyz = analyzer.analyze("uvwxyz");
        let score_rev = analyzer.analyze("fedcba");
        let score_mixed = analyzer.analyze("passabcword");

        assert!(score_abc < 1.0, "abc penalty expected");
        assert!(score_xyz < 1.0, "xyz penalty expected");
        assert!(score_rev < 1.0, "reversed abc penalty expected");
        assert!(score_mixed < 1.0, "mixed abc penalty expected");
    }

    #[test]
    fn test_sequential_numeric() {
        let analyzer = default_analyzer();
        let score_123 = analyzer.analyze("12345");
        let score_789 = analyzer.analyze("7890");
        let score_rev = analyzer.analyze("54321");
        let score_mixed = analyzer.analyze("pass123word");

        assert!(score_123 < 0.9, "123 penalty");
        assert!(score_789 < 0.9, "789 penalty");
        assert!(score_rev < 0.9, "reversed 123 penalty");
        assert!(score_mixed < 1.0, "mixed 123 penalty");
    }

    #[test]
    fn test_sequential_symbols() {
        let analyzer = default_analyzer();
        let score_sym = analyzer.analyze("!@#$%");
        if PatternAnalyzer::default()
            .char_sequences
            .iter()
            .any(|s| s.contains("!@#$"))
        {
            assert!(score_sym < 0.95, "Symbol sequence penalty");
        } else {
            println!("Symbol sequence is not explicitly tested if not in defaults.");
            assert!(score_sym <= 1.0);
        }
    }

    #[test]
    fn test_sequential_case_insensitive() {
        let analyzer = default_analyzer();
        let score_abc = analyzer.analyze("aBcDeF");
        assert!(score_abc < 0.9, "Mixed case sequence penalty");
    }

    #[test]
    fn test_substitutions() {
        let analyzer = default_analyzer();
        let score_p4ss = analyzer.analyze("p4ssw0rd");
        let score_l33t = analyzer.analyze("l33t$p34k!");
        let score_one = analyzer.analyze("password@");
        let score_none = analyzer.analyze("password");

        assert!(score_p4ss < 1.0, "p4ssw0rd sub penalty");
        assert!(
            score_l33t < score_p4ss,
            "l33t should have higher sub penalty"
        );
        assert!(score_one < 1.0, "Single sub penalty");
        assert!(
            score_none > score_p4ss,
            "No subs should score higher than subs"
        );
    }

    #[test]
    fn test_repeated_patterns() {
        let analyzer = default_analyzer();
        let score_abcabc = analyzer.analyze("abcabcabc");
        let score_testtest = analyzer.analyze("testtesttest");
        let score_abab = analyzer.analyze("ababababab");
        let score_complex = analyzer.analyze("abc123abc123");
        let score_case = analyzer.analyze("TestTest");

        assert!(score_abcabc < 0.9, "abcabc penalty");
        assert!(
            score_abcabc < score_testtest,
            "abcabcabc expected weaker than testtesttest"
        );
        assert!(score_abab < 0.9, "abab penalty");
        assert!(score_complex < 0.9, "complex repeat penalty");
        assert!(score_case < 0.9, "Case insensitive repeat penalty");
    }
}