test = require 'tape'
ROOT = "../src"
if process.env.ROOT
ROOT = process.env.ROOT
scoring = require (ROOT + '/scoring')
matching = require (ROOT + '/matching')
log2 = scoring.log2
log10 = scoring.log10
nCk = scoring.nCk
EPSILON = 1e-10 # truncate to 10th decimal place
truncate_float = (float) -> Math.round(float / EPSILON) * EPSILON
approx_equal = (t, actual, expected, msg) ->
t.equal truncate_float(actual), truncate_float(expected), msg
test 'nCk', (t) ->
for [n, k, result] in [
[ 0, 0, 1 ]
[ 1, 0, 1 ]
[ 5, 0, 1 ]
[ 0, 1, 0 ]
[ 0, 5, 0 ]
[ 2, 1, 2 ]
[ 4, 2, 6 ]
[ 33, 7, 4272048 ]
]
t.equal nCk(n, k), result, "nCk(#{n}, #{k}) == #{result}"
n = 49
k = 12
t.equal nCk(n, k), nCk(n, n-k), "mirror identity"
t.equal nCk(n, k), nCk(n-1, k-1) + nCk(n-1, k), "pascal's triangle identity"
t.end()
test 'log', (t) ->
for [n, result] in [
[ 1, 0 ]
[ 2, 1 ]
[ 4, 2 ]
[ 32, 5 ]
]
t.equal log2(n), result, "log2(#{n}) == #{result}"
for [n, result] in [
[ 1, 0]
[ 10, 1]
[ 100, 2]
]
t.equal log10(n), result, "log10(#{n}) == #{result}"
n = 17
p = 4
approx_equal t, log10(n * p), log10(n) + log10(p), "product rule"
approx_equal t, log10(n / p), log10(n) - log10(p), "quotient rule"
approx_equal t, log10(Math.E), 1 / Math.log(10), "base switch rule"
approx_equal t, log10(Math.pow(n, p)), p * log10(n), "power rule"
approx_equal t, log10(n), Math.log(n) / Math.log(10), "base change rule"
t.end()
test 'search', (t) ->
m = (i, j, guesses) ->
i: i
j: j
guesses: guesses
password = '0123456789'
# for tests, set additive penalty to zero.
exclude_additive = true
msg = (s) -> "returns one bruteforce match given an empty match sequence: #{s}"
result = scoring.most_guessable_match_sequence password, []
t.equal result.sequence.length, 1, msg("result.length == 1")
m0 = result.sequence[0]
t.equal m0.pattern, 'bruteforce', msg("match.pattern == 'bruteforce'")
t.equal m0.token, password, msg("match.token == #{password}")
t.deepEqual [m0.i, m0.j], [0, 9], msg("[i, j] == [#{m0.i}, #{m0.j}]")
msg = (s) -> "returns match + bruteforce when match covers a prefix of password: #{s}"
matches = [m0] = [m(0, 5, 1)]
result = scoring.most_guessable_match_sequence password, matches, exclude_additive
t.equal result.sequence.length, 2, msg("result.match.sequence.length == 2")
t.equal result.sequence[0], m0, msg("first match is the provided match object")
m1 = result.sequence[1]
t.equal m1.pattern, 'bruteforce', msg("second match is bruteforce")
t.deepEqual [m1.i, m1.j], [6, 9], msg("second match covers full suffix after first match")
msg = (s) -> "returns bruteforce + match when match covers a suffix: #{s}"
matches = [m1] = [m(3, 9, 1)]
result = scoring.most_guessable_match_sequence password, matches, exclude_additive
t.equal result.sequence.length, 2, msg("result.match.sequence.length == 2")
m0 = result.sequence[0]
t.equal m0.pattern, 'bruteforce', msg("first match is bruteforce")
t.deepEqual [m0.i, m0.j], [0, 2], msg("first match covers full prefix before second match")
t.equal result.sequence[1], m1, msg("second match is the provided match object")
msg = (s) -> "returns bruteforce + match + bruteforce when match covers an infix: #{s}"
matches = [m1] = [m(1, 8, 1)]
result = scoring.most_guessable_match_sequence password, matches, exclude_additive
t.equal result.sequence.length, 3, msg("result.length == 3")
t.equal result.sequence[1], m1, msg("middle match is the provided match object")
m0 = result.sequence[0]
m2 = result.sequence[2]
t.equal m0.pattern, 'bruteforce', msg("first match is bruteforce")
t.equal m2.pattern, 'bruteforce', msg("third match is bruteforce")
t.deepEqual [m0.i, m0.j], [0, 0], msg("first match covers full prefix before second match")
t.deepEqual [m2.i, m2.j], [9, 9], msg("third match covers full suffix after second match")
msg = (s) -> "chooses lower-guesses match given two matches of the same span: #{s}"
matches = [m0, m1] = [m(0, 9, 1), m(0, 9, 2)]
result = scoring.most_guessable_match_sequence password, matches, exclude_additive
t.equal result.sequence.length, 1, msg("result.length == 1")
t.equal result.sequence[0], m0, msg("result.sequence[0] == m0")
# make sure ordering doesn't matter
m0.guesses = 3
result = scoring.most_guessable_match_sequence password, matches, exclude_additive
t.equal result.sequence.length, 1, msg("result.length == 1")
t.equal result.sequence[0], m1, msg("result.sequence[0] == m1")
msg = (s) -> "when m0 covers m1 and m2, choose [m0] when m0 < m1 * m2 * fact(2): #{s}"
matches = [m0, m1, m2] = [m(0, 9, 3), m(0, 3, 2), m(4, 9, 1)]
result = scoring.most_guessable_match_sequence password, matches, exclude_additive
t.equal result.guesses, 3, msg("total guesses == 3")
t.deepEqual result.sequence, [m0], msg("sequence is [m0]")
msg = (s) -> "when m0 covers m1 and m2, choose [m1, m2] when m0 > m1 * m2 * fact(2): #{s}"
m0.guesses = 5
result = scoring.most_guessable_match_sequence password, matches, exclude_additive
t.equal result.guesses, 4, msg("total guesses == 4")
t.deepEqual result.sequence, [m1, m2], msg("sequence is [m1, m2]")
t.end()
test 'calc_guesses', (t) ->
match =
guesses: 1
msg = "estimate_guesses returns cached guesses when available"
t.equal scoring.estimate_guesses(match, ''), 1, msg
match =
pattern: 'date'
token: '1977'
year: 1977
month: 7
day: 14
msg = "estimate_guesses delegates based on pattern"
t.equal scoring.estimate_guesses(match, '1977'), scoring.date_guesses(match), msg
t.end()
test 'repeat guesses', (t) ->
for [token, base_token, repeat_count] in [
[ 'aa', 'a', 2]
[ '999', '9', 3]
[ '$$$$', '$', 4]
[ 'abab', 'ab', 2]
[ 'batterystaplebatterystaplebatterystaple', 'batterystaple', 3]
]
base_guesses = scoring.most_guessable_match_sequence(
base_token
matching.omnimatch base_token
).guesses
match =
token: token
base_token: base_token
base_guesses: base_guesses
repeat_count: repeat_count
expected_guesses = base_guesses * repeat_count
msg = "the repeat pattern '#{token}' has guesses of #{expected_guesses}"
t.equal scoring.repeat_guesses(match), expected_guesses, msg
t.end()
test 'sequence guesses', (t) ->
for [token, ascending, guesses] in [
[ 'ab', true, 4 * 2 ] # obvious start * len-2
[ 'XYZ', true, 26 * 3 ] # base26 * len-3
[ '4567', true, 10 * 4 ] # base10 * len-4
[ '7654', false, 10 * 4 * 2 ] # base10 * len 4 * descending
[ 'ZYX', false, 4 * 3 * 2 ] # obvious start * len-3 * descending
]
match =
token: token
ascending: ascending
msg = "the sequence pattern '#{token}' has guesses of #{guesses}"
t.equal scoring.sequence_guesses(match), guesses, msg
t.end()
test 'regex guesses', (t) ->
match =
token: 'aizocdk'
regex_name: 'alpha_lower'
regex_match: ['aizocdk']
msg = "guesses of 26^7 for 7-char lowercase regex"
t.equal scoring.regex_guesses(match), Math.pow(26, 7), msg
match =
token: 'ag7C8'
regex_name: 'alphanumeric'
regex_match: ['ag7C8']
msg = "guesses of 62^5 for 5-char alphanumeric regex"
t.equal scoring.regex_guesses(match), Math.pow(2 * 26 + 10, 5), msg
match =
token: '1972'
regex_name: 'recent_year'
regex_match: ['1972']
msg = "guesses of |year - REFERENCE_YEAR| for distant year matches"
t.equal scoring.regex_guesses(match), Math.abs(scoring.REFERENCE_YEAR - 1972), msg
match =
token: '2005'
regex_name: 'recent_year'
regex_match: ['2005']
msg = "guesses of MIN_YEAR_SPACE for a year close to REFERENCE_YEAR"
t.equal scoring.regex_guesses(match), scoring.MIN_YEAR_SPACE, msg
t.end()
test 'date guesses', (t) ->
match =
token: '1123'
separator: ''
has_full_year: false
year: 1923
month: 1
day: 1
msg = "guesses for #{match.token} is 365 * distance_from_ref_year"
t.equal scoring.date_guesses(match), 365 * Math.abs(scoring.REFERENCE_YEAR - match.year), msg
match =
token: '1/1/2010'
separator: '/'
has_full_year: true
year: 2010
month: 1
day: 1
msg = "recent years assume MIN_YEAR_SPACE."
msg += " extra guesses are added for separators."
t.equal scoring.date_guesses(match), 365 * scoring.MIN_YEAR_SPACE * 4, msg
t.end()
test 'spatial guesses', (t) ->
match =
token: 'zxcvbn'
graph: 'qwerty'
turns: 1
shifted_count: 0
base_guesses = (
scoring.KEYBOARD_STARTING_POSITIONS *
scoring.KEYBOARD_AVERAGE_DEGREE *
# - 1 term because: not counting spatial patterns of length 1
# eg for length==6, multiplier is 5 for needing to try len2,len3,..,len6
(match.token.length - 1)
)
msg = "with no turns or shifts, guesses is starts * degree * (len-1)"
t.equal scoring.spatial_guesses(match), base_guesses, msg
match.guesses = null
match.token = 'ZxCvbn'
match.shifted_count = 2
shifted_guesses = base_guesses * (nCk(6, 2) + nCk(6, 1))
msg = "guesses is added for shifted keys, similar to capitals in dictionary matching"
t.equal scoring.spatial_guesses(match), shifted_guesses, msg
match.guesses = null
match.token = 'ZXCVBN'
match.shifted_count = 6
shifted_guesses = base_guesses * 2
msg = "when everything is shifted, guesses are doubled"
t.equal scoring.spatial_guesses(match), shifted_guesses, msg
match =
token: 'zxcft6yh'
graph: 'qwerty'
turns: 3
shifted_count: 0
guesses = 0
L = match.token.length
s = scoring.KEYBOARD_STARTING_POSITIONS
d = scoring.KEYBOARD_AVERAGE_DEGREE
for i in [2..L]
for j in [1..Math.min(match.turns, i-1)]
guesses += nCk(i-1, j-1) * s * Math.pow(d, j)
msg = "spatial guesses accounts for turn positions, directions and starting keys"
t.equal scoring.spatial_guesses(match), guesses, msg
t.end()
test 'dictionary_guesses', (t) ->
match =
token: 'aaaaa'
rank: 32
msg = "base guesses == the rank"
t.equal scoring.dictionary_guesses(match), 32, msg
match =
token: 'AAAaaa'
rank: 32
msg = "extra guesses are added for capitalization"
t.equal scoring.dictionary_guesses(match), 32 * scoring.uppercase_variations(match), msg
match =
token: 'aaa'
rank: 32
reversed: true
msg = "guesses are doubled when word is reversed"
t.equal scoring.dictionary_guesses(match), 32 * 2, msg
match =
token: 'aaa@@@'
rank: 32
l33t: true
sub: {'@': 'a'}
msg = "extra guesses are added for common l33t substitutions"
t.equal scoring.dictionary_guesses(match), 32 * scoring.l33t_variations(match), msg
match =
token: 'AaA@@@'
rank: 32
l33t: true
sub: {'@': 'a'}
msg = "extra guesses are added for both capitalization and common l33t substitutions"
expected = 32 * scoring.l33t_variations(match) * scoring.uppercase_variations(match)
t.equal scoring.dictionary_guesses(match), expected, msg
t.end()
test 'uppercase variants', (t) ->
for [word, variants] in [
[ '', 1 ]
[ 'a', 1 ]
[ 'A', 2 ]
[ 'abcdef', 1 ]
[ 'Abcdef', 2 ]
[ 'abcdeF', 2 ]
[ 'ABCDEF', 2 ]
[ 'aBcdef', nCk(6,1) ]
[ 'aBcDef', nCk(6,1) + nCk(6,2) ]
[ 'ABCDEf', nCk(6,1) ]
[ 'aBCDEf', nCk(6,1) + nCk(6,2) ]
[ 'ABCdef', nCk(6,1) + nCk(6,2) + nCk(6,3) ]
]
msg = "guess multiplier of #{word} is #{variants}"
t.equal scoring.uppercase_variations(token: word), variants, msg
t.end()
test 'l33t variants', (t) ->
match = l33t: false
t.equal scoring.l33t_variations(match), 1, "1 variant for non-l33t matches"
for [word, variants, sub] in [
[ '', 1, {} ]
[ 'a', 1, {} ]
[ '4', 2, {'4': 'a'} ]
[ '4pple', 2, {'4': 'a'} ]
[ 'abcet', 1, {} ]
[ '4bcet', 2, {'4': 'a'} ]
[ 'a8cet', 2, {'8': 'b'} ]
[ 'abce+', 2, {'+': 't'} ]
[ '48cet', 4, {'4': 'a', '8': 'b'} ]
[ 'a4a4aa', nCk(6, 2) + nCk(6, 1), {'4': 'a'} ]
[ '4a4a44', nCk(6, 2) + nCk(6, 1), {'4': 'a'} ]
[ 'a44att+', (nCk(4, 2) + nCk(4, 1)) * nCk(3, 1), {'4': 'a', '+': 't'} ]
]
match =
token: word
sub: sub
l33t: not matching.empty(sub)
msg = "extra l33t guesses of #{word} is #{variants}"
t.equal scoring.l33t_variations(match), variants, msg
match =
token: 'Aa44aA'
l33t: true
sub: {'4': 'a'}
variants = nCk(6, 2) + nCk(6, 1)
msg = "capitalization doesn't affect extra l33t guesses calc"
t.equal scoring.l33t_variations(match), variants, msg
t.end()
Codebase Browser
chromium