regex matching can be convinced to be TRUE if you're insistive enough?

[Stefan Winter]

Hi,

while working on server optimisations for one of our customers, I
stumbled upon something funny (2.1.10).

At one point, a huge regex needs to be executed. When the input string
has a length n < ??, and the regex doesn't match, the result is FALSE -
no surprise here.

If I make the input string long enough to m > ?? > n, and the regex
doesn't match, the result is TRUE.

That is not what I'd usually expect; and it has some uneasy
implications. Depending on what an incoming user manages to send, it
could convince to make the server take a wrong code path; maybe sneaking
in when he shouldn't.

A simple test case to prove this: in authorize, add

        update control {
                Bla  = "*1*
lkkgflaksdjfhklsajfdghaösfdlghaskljfdghalksdfjghaklsdfjghkdalsfjghaklsfdghaklsdfjghlaksdfghaklsdfjghsdaklfjghkladsfjgh",
                Bla += "*2*
lkkgflaksdjfhklsajfdghaösfdlghaskljfdghalksdfjghaklsdfjghkdalsfjghaklsfdghaklsdfjghlaksdfghaklsdfjghsdaklfjghkladsfjgh",
                Bla += "*3*
lkkgflaksdjfhklsajfdghaösfdlghaskljfdghalksdfjghaklsdfjghkdalsfjghaklsfdghaklsdfjghlaksdfghaklsdfjghsdaklfjghkladsfjgh",
                Bla += "*4*
lkkgflaksdjfhklsajfdghaösfdlghaskljfdghalksdfjghaklsdfjghkdalsfjghaklsfdghaklsdfjghlaksdfghaklsdfjghsdaklfjghkladsfjgh",
                Bla += "*5*
lkkgflaksdjfhklsajfdghaösfdlghaskljfdghalksdfjghaklsdfjghkdalsfjghaklsfdghaklsdfjghlaksdfghaklsdfjghsdaklfjghkladsfjgh",
                Bla += "*6*
lkkgflaksdjfhklsajfdghaösfdlghaskljfdghalksdfjghaklsdfjghkdalsfjghaklsfdghaklsdfjghlaksdfghaklsdfjghsdaklfjghkladsfjgh"
    }

        if ( "%{control:Bla[*]}" =~ /zzzz/ ) {
                update control {
                        Bla2 := "Hit!"
                }
        }

This doesn't match, and debug output tells you so:

Tue May 24 16:09:56 2011 : Info: ++? if ("%{control:Bla[*]}" =~ /zzzz/ )
Tue May 24 16:09:56 2011 : Info:        expand: %{control:Bla[*]} -> *1*
lkkgflaksdjfhklsajfdghaösfdlghaskljfdghalksdfjghaklsdfjghkdalsfjghaklsfdghaklsdfjghlaksdfghaklsdfjghsdaklfjghkladsfjgh
*2*
lkkgflaksdjfhklsajfdghaösfdlghaskljfdghalksdfjghaklsdfjghkdalsfjghaklsfdghaklsdfjghlaksdfghaklsdfjghsdaklfjghkladsfjgh
*3*
lkkgflaksdjfhklsajfdghaösfdlghaskljfdghalksdfjghaklsdfjghkdalsfjghaklsfdghaklsdfjghlaksdfghaklsdfjghsdaklfjghkladsfjgh
*4*
lkkgflaksdjfhklsajfdghaösfdlghaskljfdghalksdfjghaklsdfjghkdalsfjghaklsfdghaklsdfjghlaksdfghaklsdfjghsdaklfjghkladsfjgh
*5*
lkkgflaksdjfhklsajfdghaösfdlghaskljfdghalksdfjghaklsdfjghkdalsfjghaklsfdghaklsdfjghlaksdfghaklsdfjghsdaklfjghkladsfjgh
*6*
lkkgflaksdjfhklsajfdghaösfdlghaskljfdghalksdfjghaklsdfjghkdalsfjghaklsfdghaklsdfjghlaksdfghaklsdfjghsdaklfjghkladsfjgh

Tue May 24 16:09:56 2011 : Info: ? Evaluating ("%{control:Bla[*]}" =~
/zzzz/) -> FALSE
Tue May 24 16:09:56 2011 : Info: ++? if ("%{control:Bla[*]}" =~ /zzzz/ )
-> FALSE

Now, make the Bla blob larger:

        update control {
                RESTENA-Service-Type = "IMAP",
                Bla  = "*1*
lkkgflaksdjfhklsajfdghaösfdlghaskljfdghalksdfjghaklsdfjghkdalsfjghaklsfdghaklsdfjghlaksdfghaklsdfjghsdaklfjghkladsfjgh",
                Bla += "*2*
lkkgflaksdjfhklsajfdghaösfdlghaskljfdghalksdfjghaklsdfjghkdalsfjghaklsfdghaklsdfjghlaksdfghaklsdfjghsdaklfjghkladsfjgh",
                Bla += "*3*
lkkgflaksdjfhklsajfdghaösfdlghaskljfdghalksdfjghaklsdfjghkdalsfjghaklsfdghaklsdfjghlaksdfghaklsdfjghsdaklfjghkladsfjgh",
                Bla += "*4*
lkkgflaksdjfhklsajfdghaösfdlghaskljfdghalksdfjghaklsdfjghkdalsfjghaklsfdghaklsdfjghlaksdfghaklsdfjghsdaklfjghkladsfjgh",
                Bla += "*5*
lkkgflaksdjfhklsajfdghaösfdlghaskljfdghalksdfjghaklsdfjghkdalsfjghaklsfdghaklsdfjghlaksdfghaklsdfjghsdaklfjghkladsfjgh",
                Bla += "*6*
lkkgflaksdjfhklsajfdghaösfdlghaskljfdghalksdfjghaklsdfjghkdalsfjghaklsfdghaklsdfjghlaksdfghaklsdfjghsdaklfjghkladsfjgh",
                Bla += "*7*
lkkgflaksdjfhklsajfdghaösfdlghaskljfdghalksdfjghaklsdfjghkdalsfjghaklsfdghaklsdfjghlaksdfghaklsdfjghsdaklfjghkladsfjgh",
                Bla += "*8*
lkkgflaksdjfhklsajfdghaösfdlghaskljfdghalksdfjghaklsdfjghkdalsfjghaklsfdghaklsdfjghlaksdfghaklsdfjghsdaklfjghkladsfjgh",
                Bla += "*9*
lkkgflaksdjfhklsajfdghaösfdlghaskljfdghalksdfjghaklsdfjghkdalsfjghaklsfdghaklsdfjghlaksdfghaklsdfjghsdaklfjghkladsfjgh",
                Bla += "*A*
lkkgflaksdjfhklsajfdghaösfdlghaskljfdghalksdfjghaklsdfjghkdalsfjghaklsfdghaklsdfjghlaksdfghaklsdfjghsdaklfjghkladsfjgh"
}

And you will get a TRUE:

Tue May 24 16:11:42 2011 : Info: ++? if ("%{control:Bla[*]}" =~ /zzzz/ )
Tue May 24 16:11:42 2011 : Info:        expand: %{control:Bla[*]} -> *1*
lkkgflaksdjfhklsajfdghaösfdlghaskljfdghalksdfjghaklsdfjghkdalsfjghaklsfdghaklsdfjghlaksdfghaklsdfjghsdaklfjghkladsfjgh
*2*
lkkgflaksdjfhklsajfdghaösfdlghaskljfdghalksdfjghaklsdfjghkdalsfjghaklsfdghaklsdfjghlaksdfghaklsdfjghsdaklfjghkladsfjgh
*3*
lkkgflaksdjfhklsajfdghaösfdlghaskljfdghalksdfjghaklsdfjghkdalsfjghaklsfdghaklsdfjghlaksdfghaklsdfjghsdaklfjghkladsfjgh
*4*
lkkgflaksdjfhklsajfdghaösfdlghaskljfdghalksdfjghaklsdfjghkdalsfjghaklsfdghaklsdfjghlaksdfghaklsdfjghsdaklfjghkladsfjgh
*5*
lkkgflaksdjfhklsajfdghaösfdlghaskljfdghalksdfjghaklsdfjghkdalsfjghaklsfdghaklsdfjghlaksdfghaklsdfjghsdaklfjghkladsfjgh
*6*
lkkgflaksdjfhklsajfdghaösfdlghaskljfdghalksdfjghaklsdfjghkdalsfjghaklsfdghaklsdfjghlaksdfghaklsdfjghsdaklfjghkladsfjgh
*7*
lkkgflaksdjfhklsajfdghaösfdlghaskljfdghalksdfjghaklsdfjghkdalsfjghaklsfdghaklsdfjghlaksdfghaklsdfjghsdaklfjghkladsfjgh
*8*
lkkgflaksdjfhklsajfdghaösfdlghaskljfdghalksdfjghaklsdfjghkdalsfjghaklsfdghaklsdfjghlaksdfghaklsdfjghsdaklfjghkladsfjgh
*
Tue May 24 16:11:42 2011 : Info: ? Evaluating ("%{control:Bla[*]}" =~
/zzzz/) -> TRUE
Tue May 24 16:11:42 2011 : Info: ++? if ("%{control:Bla[*]}" =~ /zzzz/ )
-> TRUE

Note also that the debug output stops its string content output
prematurely, but that's not as bad as the string regex mis-matching.

My guess is that the breakage occurs when the string is longer than
what's printed out in debug mode, but I didn't really try.

Greetings,

Stefan Winter

-- 
Stefan WINTER
Ingenieur de Recherche
Fondation RESTENA - Réseau Téléinformatique de l'Education Nationale et de la Recherche
6, rue Richard Coudenhove-Kalergi
L-1359 Luxembourg

Tel: +352 424409 1
Fax: +352 422473


-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 262 bytes
Desc: OpenPGP digital signature
URL: <http://lists.freeradius.org/pipermail/freeradius-devel/attachments/20110524/0f9370e9/attachment.pgp>