Simple Machines Community Forum

SMF Development => Bug Reports => Fixed or Bogus Bugs => Topic started by: dougiefresh on July 31, 2015, 09:12:39 AM

Title: REPORT: Potentially "Fatal Flaw" in SMF's bbcode parser
Post by: dougiefresh on July 31, 2015, 09:12:39 AM


POTENTIALLY "FATAL FLAW" IN SMF'S PARSER



Several days ago, I was notified about a potentially "fatal flaw" in SMF's bbcode parser.  It occurs when a particular bbcode, such as my Post and PM Inline Attachments (http://custom.simplemachines.org/mods/index.php?mod=3770) mod, has a large number of parameters, such as 14+.

What happens in the original SMF code:
(1) A simple array ($preg) is built with a regex expression for each of the parameters.
(1) Another array ($orders) is built with all possible permutations of the parameters from $preg.
(2) The $orders array is checked for a match, up until a match is found.

Why is this a problem?  Well, the permutation process is the issue here.  A bbcode with 14 parameters generates 98,306 permutations, taking little more than quarter a second on my system PER USE and using 90MB of memory!!  Checking for 15 parameters crashes my forum with an out-of-memory error because it attempts to allocate more than 128MB of memory!

Using this array of permutations, I started my tests with the included script below:
$parameters = array(
'id' => array('match' => '(\d+)', 'validate' => 'ILA_Param_ID'),
'width' => array('optional' => true, 'match' => '(\d+)', 'validate' => 'ILA_Param_Width'),
'height' => array('optional' => true, 'match' => '(\d+)', 'validate' => 'ILA_Param_Height'),
'float' => array('optional' => true, 'match' => '(left|right|center)', 'validate' => 'ILA_Param_Float'),
'margin' => array('optional' => true, 'match' => '(\d+)', 'validate' => 'ILA_Param_Margin'),
'margin-left' => array('optional' => true, 'match' => '(\d+)', 'validate' => 'ILA_Param_Margin_Left'),
'margin-right' => array('optional' => true, 'match' => '(\d+)', 'validate' => 'ILA_Param_Margin_Right'),
'margin-top' => array('optional' => true, 'match' => '(\d+)', 'validate' => 'ILA_Param_Margin_Top'),
'margin-bottom' => array('optional' => true, 'match' => '(\d+)', 'validate' => 'ILA_Param_Margin_Bottom'),
'border-style' => array('match' => '(dotted|dashed|solid|double|groove|ridge|inset|outset)', 'validate' => 'ILA_Param_Border_Style'),
'border-width' => array('optional' => true, 'match' => '(\d+)', 'validate' => 'ILA_Param_Border_Width'),
'border-color' => array('optional' => true, 'match' => '(#[\da-fA-F]{3}|#[\da-fA-F]{6}|[A-Za-z]{1,20}|rgb\(\d{1,3}, ?\d{1,3}, ?\d{1,3}\))', 'validate' => 'ILA_Param_Border_Color'),
'scale' => array('optional' => true, 'match' => '(true|false|yes|no)', 'validate' => 'ILA_Param_Scale'),
'msg' => array('optional' => true, 'match' => '(new|\d+)', 'validate' => 'ILA_Param_Msg'),
'msg2' => array('optional' => true, 'match' => '(new|\d+)', 'validate' => 'ILA_Param_Msg'),
'msg3' => array('optional' => true, 'match' => '(new|\d+)', 'validate' => 'ILA_Param_Msg'),
'msg4' => array('optional' => true, 'match' => '(new|\d+)', 'validate' => 'ILA_Param_Msg'),
'msg5' => array('optional' => true, 'match' => '(new|\d+)', 'validate' => 'ILA_Param_Msg'),
'msg6' => array('optional' => true, 'match' => '(new|\d+)', 'validate' => 'ILA_Param_Msg'),
'msg7' => array('optional' => true, 'match' => '(new|\d+)', 'validate' => 'ILA_Param_Msg'),
'msg8' => array('optional' => true, 'match' => '(new|\d+)', 'validate' => 'ILA_Param_Msg'),
'msg9' => array('optional' => true, 'match' => '(new|\d+)', 'validate' => 'ILA_Param_Msg'),
'msgA' => array('optional' => true, 'match' => '(new|\d+)', 'validate' => 'ILA_Param_Msg'),
'msgB' => array('optional' => true, 'match' => '(new|\d+)', 'validate' => 'ILA_Param_Msg'),
);

(Yes, I added some parameters that aren't in my Post & PM Inline Attachments mod....  Specifically, everything from msg2 and down!)

I've attached a test script to show what happens when the permutations array is built.  Here is the output from my localhost system:
Quote
TEST # 5 : 5 parameters
=================================================
Size before "permute" function is executed: 5,246,024
Size after "permute" function is executed: 5,266,576
Time Taken: 0.00011181831359863 seconds
Array Elements: 50

TEST # 6 : 6 parameters
=================================================
Size before "permute" function is executed: 5,246,200
Size after "permute" function is executed: 5,306,368
Time Taken: 0.00025010108947754 seconds
Array Elements: 130

TEST # 7 : 7 parameters
=================================================
Size before "permute" function is executed: 5,246,376
Size after "permute" function is executed: 5,410,520
Time Taken: 0.00060391426086426 seconds
Array Elements: 322

TEST # 8 : 8 parameters
=================================================
Size before "permute" function is executed: 5,246,552
Size after "permute" function is executed: 5,675,480
Time Taken: 0.0015487670898438 seconds
Array Elements: 770

TEST # 9 : 9 parameters
=================================================
Size before "permute" function is executed: 5,246,760
Size after "permute" function is executed: 6,388,688
Time Taken: 0.0037760734558105 seconds
Array Elements: 1794

TEST # 10 : 10 parameters
=================================================
Size before "permute" function is executed: 5,246,976
Size after "permute" function is executed: 8,066,328
Time Taken: 0.0089709758758545 seconds
Array Elements: 4098

TEST # 11 : 11 parameters
=================================================
Size before "permute" function is executed: 5,247,208
Size after "permute" function is executed: 12,023,288
Time Taken: 0.020859003067017 seconds
Array Elements: 9218

TEST # 12 : 12 parameters
=================================================
Size before "permute" function is executed: 5,247,392
Size after "permute" function is executed: 21,272,456
Time Taken: 0.052258014678955 seconds
Array Elements: 20482

TEST # 13 : 13 parameters
=================================================
Size before "permute" function is executed: 5,247,640
Size after "permute" function is executed: 42,637,392
Time Taken: 0.11318302154541 seconds
Array Elements: 45058

TEST # 14 : 14 parameters
=================================================
Size before "permute" function is executed: 5,247,816
Size after "permute" function is executed: 91,495,328
Time Taken: 0.24853491783142 seconds
Array Elements: 98306

TEST # 15 : 15 parameters
=================================================
Size before "permute" function is executed: 5,247,968

Fatal error: Allowed memory size of 134217728 bytes exhausted (tried to allocate 35 bytes) in D:\Website\clean\Sources\Subs.php on line 874
The time for under 5 parameters is negliable.  Notice that the time taken for up to 8 parameters is almost non-existance, but more parameters than that cause the permute function to take more and more time to generate all the possible permutations of the parameters.  14 parameters take just under a quarter second PER TAG USE!!!  15 parameters actually crashed the script....

By the way, the error message returned by the script referred to this function (pointed to by >>>):
// This gets all possible permutations of an array.
function permute($array)
{
$orders = array($array);

$n = count($array);
$p = range(0, $n);
for ($i = 1; $i < $n; null)
{
$p[$i]--;
$j = $i % 2 != 0 ? $p[$i] : 0;

$temp = $array[$i];
>>> $array[$i] = $array[$j];
$array[$j] = $temp;

for ($i = 1; $p[$i] == 0; $i++)
$p[$i] = 1;

$orders[] = $array;
}

return $orders;
}
Title: Re: REPORT: Potentially "Fatal Flaw" in SMF's bbcode parser
Post by: dougiefresh on July 31, 2015, 09:12:50 AM


STEPS TO CORRECT THE FLAW


In Sources/Subs.php, find this code:
Code (Find) Select
return $orders;
}

and add this after it:
Code (Add After) Select


// Rearranges all parameters to be in the right order.  Returns TRUE if no parameters are leftover.
function_param_order($message, &$parameters, &$out)
{
$params = explode(' ', substr($message, 0, strpos($message, ']')));
unset($params[0]);
$order = array();
$out = $old = '';
foreach ($params as $param)
{
if (strpos($param, '=') === false)
$order[$old] .= ' ' . $param;
else
$order[$old = substr($param, 0, strpos($param, '='))] = substr($param, strpos($param, '=') + 1);
}
foreach ($parameters as $key => $ignore)
{
$out .= (isset($order[$key]) ? ' ' . $key . '=' . $order[$key] : '');
unset($order[$key]);
}
return count($order) == 0;
}


Find this code:
Code (Find) Select
$preg = array();
foreach ($possible['parameters'] as $p => $info)
$preg[] = '(\s+' . $p . '=' . (empty($info['quoted']) ? '' : '&quot;') . (isset($info['match']) ? $info['match'] : '(.+?)') . (empty($info['quoted']) ? '' : '&quot;') . ')' . (empty($info['optional']) ? '' : '?');

// Okay, this may look ugly and it is, but it's not going to happen much and it is the best way of allowing any order of parameters but still parsing them right.
$match = false;
$orders = permute($preg);
foreach ($orders as $p)
if (preg_match('~^' . implode('', $p) . '\]~i', substr($message, $pos1 - 1), $matches) != 0)
{
$match = true;
break;
}

// Didn't match our parameter list, try the next possible.
if (!$match)
continue;

and replace it with this:
Code (Replace) Select

// START: Dougiefresh's faster parse_bbc function
if (!fix_param_order(($test = substr($message, $pos1 - 1)), $possible['parameters'], $replace_str))
continue;
$preg = '';
foreach ($possible['parameters'] as $p => $info)
$preg .= '(\s+' . $p . '=' . (empty($info['quoted']) ? '' : '&quot;') . (isset($info['match']) ? $info['match'] : '(.+?)') . (empty($info['quoted']) ? '' : '&quot;') . ')' . (empty($info['optional']) ? '' : '?');
if (!preg_match('~^' . $preg . '\]~i', ($test = $replace_str . substr($test, strpos($test, ']'))), $matches))
continue;
$message = substr($message, 0, $pos1 - 1) . $test;
// END: Dougiefresh's faster parse_bbc function





Okay, this isn't plain English, so I'll translate what the modifications do.....

My solution to this issue has several steps:
(1) Internally rearrange the parameters into the proper order and return the number of unused parameters, as well as the replacement string.
(2) If there are unused parameters, then this can't be the bbcode we're looking for.  Continue to next bbcode...
(3) TEST the replacement string made in STEP 2 to see if the parameters match what that particular bbcode expects.
(4) If STEP 3 is not a match, continue to next bbcode...
(5) Replace the bbcode in question with the rearranged version.

Why is this important?  Several reasons:
(1) Memory is saved by not having to generate all possible permutations of a particular parameter set.
(2) Time is saved (at least with larger sets) by NOT having to generate a large number of permutations.
(3) Time is saved (at least with larger sets) by NOT having to test a large number of permutations.
(4) Irritation by the user because they don't have to deal with "blank screens of death" due to out-of-memory situations.

Please note that this mod leaves the permute function in place, as other mods or future forum versions may need the built-in functionality.




EDIT: Replaced erroneous "replace" operation with "add after"....  Whoops!
Title: Re: REPORT: Potentially "Fatal Flaw" in SMF's bbcode parser
Post by: dougiefresh on July 31, 2015, 09:18:29 AM
I've also posted a new mod that corrects this issue.  It's called Faster SMF BBCode Parser (http://custom.simplemachines.org/mods/index.php?mod=4069).  No, as of this writing, it hasn't been approved yet, so please don't comment that there is nothing there!
Title: Re: REPORT: Potentially "Fatal Flaw" in SMF's bbcode parser
Post by: Kindred on July 31, 2015, 09:33:41 AM
Hmmm.... needs some review... but, Dougie... would you be willing to submit this as a PR on github?
(there are potential license issues with us including fixes offered on the forum, while a gitHub PR clearly indicates the intention to submit...


BTW: Nice job!
Title: Re: REPORT: Potentially "Fatal Flaw" in SMF's bbcode parser
Post by: dougiefresh on July 31, 2015, 10:08:42 AM
Thanks!  Tell me how to submit one on GitHub and I will.
Title: Re: REPORT: Potentially "Fatal Flaw" in SMF's bbcode parser
Post by: margarett on July 31, 2015, 10:19:37 AM
A submission to GH is to be added to 2.1's codebase, not 2.0 ;)

Have you worked with GH before? If not, you need to fork 2.1's repo then do the changes on your own (forked) repo, then finally create a PR for ours. Don't forget to sign your PR's!
I use SourceTree for handling the code flow from GH to my PC.
Title: Re: REPORT: Potentially "Fatal Flaw" in SMF's bbcode parser
Post by: Kindred on July 31, 2015, 10:30:29 AM
Well, anything submitted to 2.1 can also be backported to 2.0 :P
(and I don't think the BBC parser has changed between 2.0 and 2.1)

It's just the Intellectual Property/copyright rights that need to be covered, since we are an actual company
Title: Re: REPORT: Potentially "Fatal Flaw" in SMF's bbcode parser
Post by: dougiefresh on July 31, 2015, 02:21:28 PM
It's been submitted at GitHub.  Hopefully, I did it right.....
Title: Re: REPORT: Potentially "Fatal Flaw" in SMF's bbcode parser
Post by: Kindred on July 31, 2015, 02:25:16 PM
Thanks!  :D
Title: Re: REPORT: Potentially "Fatal Flaw" in SMF's bbcode parser
Post by: Illori on July 31, 2015, 02:28:59 PM
https://github.com/SimpleMachines/SMF2.1/pull/2956

each commit has to be signed off

something like

Signed-off-by: yournamehere [email protected]

that PR can not be merged until it is signed off.
Title: Re: REPORT: Potentially "Fatal Flaw" in SMF's bbcode parser
Post by: dougiefresh on July 31, 2015, 04:27:31 PM
I signed off on it
Title: Re: REPORT: Potentially "Fatal Flaw" in SMF's bbcode parser
Post by: Illori on July 31, 2015, 04:32:36 PM
you signed off the PR not the commit. if you dont know how to modify the commit, it may be easier to create a new branch commit the change and sign off then make a new PR [and close the old.]
Title: Re: REPORT: Potentially "Fatal Flaw" in SMF's bbcode parser
Post by: Kindred on July 31, 2015, 04:46:33 PM
you know...   the sign off on the PR should be sufficient. We do not need to beat people over the head when they try to contribute
Title: Re: REPORT: Potentially "Fatal Flaw" in SMF's bbcode parser
Post by: Illori on July 31, 2015, 06:08:39 PM
actually it is not as the PR is not what is merged it is the commits that we see in the log. if the commit is not signed off the commit log will not have the sign off and we may never know if they did sign off.

we have been telling people on github to sign off the commits for years.
Title: Re: REPORT: Potentially "Fatal Flaw" in SMF's bbcode parser
Post by: Antes on July 31, 2015, 07:24:28 PM
Quote from: Kindred on July 31, 2015, 04:46:33 PM
you know...   the sign off on the PR should be sufficient. We do not need to beat people over the head when they try to contribute

People can edit their PR messages afaik, so they can remove the "sign-off" part and cause trouble deeply.
Title: Re: REPORT: Potentially "Fatal Flaw" in SMF's bbcode parser
Post by: live627 on July 31, 2015, 07:33:33 PM
I can add his sign to my merge commit.
Title: Re: REPORT: Potentially "Fatal Flaw" in SMF's bbcode parser
Post by: Biology Forums on July 31, 2015, 08:21:30 PM
Thanks for the fix.
Title: Re: REPORT: Potentially "Fatal Flaw" in SMF's bbcode parser
Post by: Kindred on July 31, 2015, 08:22:38 PM
Thank you, live
Title: Re: REPORT: Potentially "Fatal Flaw" in SMF's bbcode parser
Post by: dougiefresh on August 01, 2015, 09:45:58 AM
I'm sorry.  I'm new to GitHub and I didn't understand.  Let me fix that....

EDIT: Tried to edit commit.  Wasn't able to.  Tried to delete commit.  Couldn't figure out how to do that, either.  Deleted account and recreated account, recreated commit and PR.  Signed off on the commit....
Title: Re: REPORT: Potentially "Fatal Flaw" in SMF's bbcode parser
Post by: Kindred on August 01, 2015, 03:20:01 PM
thanks for jumping through the hoops. dougie
Title: Re: REPORT: Potentially "Fatal Flaw" in SMF's bbcode parser
Post by: Ninja ZX-10RR on August 01, 2015, 03:48:38 PM
Not to be rude but this time... Did you even try to READ that code? Short answer: NO.

This drove me really mad, not for the error in itself because everyone makes mistakes and I don't blame dougie at all for it, as it's just a typo. However, if you 1) review the code 2) merge the pull request, you should  *at least* READ it before doing the above (and actually testing it doesn't hurt either, it takes literally one minute to apply the fix on a test forum).
So why am I being somewhat rude? Here you go, read it: function_param_order($message, &$parameters, &$out) and should obviously be function fix_param_order($message, &$parameters, &$out)
Nobody tested it - when I did, I had a white page.

Now you will blame me for attacking etc... But I am not attacking, I am just noticing issues and reporting them. And this one is a serious issue with the whole procedure.

Also... That code fails anyway, for other reasons.
Title: Re: REPORT: Potentially "Fatal Flaw" in SMF's bbcode parser
Post by: Kindred on August 01, 2015, 04:05:09 PM
well, actually, you ARE attacking, because it is obviously YOU who has not read closely enough.

He submitted a pull request.
All requests and submissions are reviewed before being accepted and included...

thank you for your suggestion on a correction, but get off your bloody high horse.
Title: Re: REPORT: Potentially "Fatal Flaw" in SMF's bbcode parser
Post by: Ninja ZX-10RR on August 01, 2015, 04:10:12 PM
Quote from: Kindred on August 01, 2015, 04:05:09 PM
All requests and submissions are reviewed before being accepted and included...
And that's where the flaw is. Nobody reviewed it! Even I, being dumb at php coding, could see such things.

Quote from: Kindred on August 01, 2015, 04:05:09 PM
thank you for your suggestion on a correction,
You're welcome.

Quote from: Kindred on August 01, 2015, 04:05:09 PMbut get off your bloody high horse.
I just told the guys in charge to read what they do, before doing it, to prevent the old bugs that occurred with the latest versions etc. And someone saying multiple times you are better than his own self is not really on a high horse, but more someone who recognizes what he can do (suggest fixes/improvements, being support team elsewhere) and what he cannot do (code better than devs). ;)

Regards
Title: Re: REPORT: Potentially "Fatal Flaw" in SMF's bbcode parser
Post by: Suki on August 01, 2015, 04:19:46 PM
The code hasn't been merged, so claiming nobody has reviewed it is kinda premature. The code has been posted yesterday (my time) and I only got a chance to see it today, the rest of the devs will see it when they got time to see it too.  Please have some patient ;)

I still haven't have a look at the PR, will do when I have sufficient amount of time to properly review it and test it.

Thank you for pointing out that typo, it has been noted duly noted, thanks.
Title: Re: REPORT: Potentially "Fatal Flaw" in SMF's bbcode parser
Post by: Ninja ZX-10RR on August 01, 2015, 05:19:59 PM
Aah, if that is the case then it's alright, thanks :) You know I was a bit like wtf ;D
Title: Re: REPORT: Potentially "Fatal Flaw" in SMF's bbcode parser
Post by: dougiefresh on August 02, 2015, 12:11:10 PM
 ::) Ah, crap!  Now that you pointed that out, I've fixed it in my mod and made a comment in the GitHub about what I meant to use instead of what I did....

@Ninja ZX-10RR: I never claimed to be perfect.  I make mistakes, just like everybody else.  Yup, sad to say, I missed that one!   :-[  Funny, my copy of Sources/Subs.php worked fine with the modified code, but I don't know how a small part of it disappeared from the edit for mod.  I made my commit based on the mod I wrote....
Title: Re: REPORT: Potentially "Fatal Flaw" in SMF's bbcode parser
Post by: Joshua Dickerson on August 02, 2015, 12:34:52 PM
Without testing it out, I don't think this works the same as the original. I don't think the following works:

[bbc param=&quot;This is a test message&quot; /]

[bbc param=&quot;[josh]&quot; /]

[url=http://www.simplemachines.org/community/index.php?action=something;boards[]=1;boards[]=2]Some link[/url]
Title: Re: REPORT: Potentially "Fatal Flaw" in SMF's bbcode parser
Post by: Joshua Dickerson on August 02, 2015, 01:35:46 PM
Without testing it, I think this saves a lot of RAM without losing any functionality. It will allow you to get a lot more parameters but not infinite.

In Subs.php, find:
// This is long, but it makes things much easier and cleaner.
if (!empty($possible['parameters']))
{
$preg = array();
foreach ($possible['parameters'] as $p => $info)
$preg[] = '(\s+' . $p . '=' . (empty($info['quoted']) ? '' : '&quot;') . (isset($info['match']) ? $info['match'] : '(.+?)') . (empty($info['quoted']) ? '' : '&quot;') . ')' . (empty($info['optional']) ? '' : '?');

// Okay, this may look ugly and it is, but it's not going to happen much and it is the best way
// of allowing any order of parameters but still parsing them right.
$match = false;
$orders = permute($preg);
foreach ($orders as $p)
if (preg_match('~^' . implode('', $p) . '\]~i', substr($message, $pos1 - 1), $matches) != 0)
{
$match = true;
break;
}

// Didn't match our parameter list, try the next possible.
if (!$match)
continue;


Replace // This is long, but it makes things much easier and cleaner.
if (!empty($possible['parameters']))
{
// Didn't match our parameter list, try the next possible.
if (!find_bbc_parameters($possible['parameters'], substr($message, $pos1 - 1), $matches))
continue;


Add this to Subs.php
/**
* Find the correct order for the BBC parameters in a string
*
* @param array $parameters
* @param string $message_part
* @param array &$matches
*
* @return bool
*/
function find_bbc_parameters(array $parameters, $message_part, &$matches)
{
$preg = array();
foreach ($parameters as $p => $info)
{
$preg[] = '(\s+' . $p . '=' . (empty($info['quoted']) ? '' : '&quot;') . (isset($info['match']) ? $info['match'] : '(.+?)') . (empty($info['quoted']) ? '' : '&quot;') . ')' . (empty($info['optional']) ? '' : '?');
}

// Okay, this may look ugly and it is, but it's not going to happen much and it is the best way
// of allowing any order of parameters but still parsing them right.
$match = false;
$orders = permute(array_keys($preg));

foreach ($orders as $keys)
{
$match_string = '~^';
foreach ($keys as $key)
{
$match_string .= $preg[$key];
}
$match_string .= '\]~i';

if (preg_match($match_string, $message_part), $matches) != 0)
{
$match = true;
break;
}
}

return $match;
}


As two added benefits, it gets rid of the $orders array and doesn't do so much string copying with the substr() in the loop.

marg edit: fixed the code as per Joshua's next post
Title: Re: REPORT: Potentially "Fatal Flaw" in SMF's bbcode parser
Post by: Joshua Dickerson on August 02, 2015, 02:54:39 PM
SMF won't let me edit my post. At the find_bbc_matches call: find_bbc_matches should be find_bbc_parameters and $possible should be $possible['parameters']
Title: Re: REPORT: Potentially "Fatal Flaw" in SMF's bbcode parser
Post by: dougiefresh on August 02, 2015, 04:50:45 PM
Submitted a new PR and commit....

@Joshua: I think you're missing the whole point.  The issue is the PERMUTE function!  Please go back and read the first post....  ::) :P  And yes, I did attempt using the permute function with array_keys.  That actually produced a LARGER array than with the parameter regex's, which I truly don't understand....
Title: Re: REPORT: Potentially "Fatal Flaw" in SMF's bbcode parser
Post by: dougiefresh on August 02, 2015, 06:45:15 PM
Quote from: Joshua Dickerson on August 02, 2015, 12:34:52 PM
[url=http://www.simplemachines.org/community/index.php?action=something;boards[]=1;boards[]=2]Some link[/url]
I tested this with both my code and SMF's original code.  Neither renders the link as it should....

Quote from: Joshua Dickerson on August 02, 2015, 12:34:52 PM
[bbc param=&quot;This is a test message&quot; /]

[bbc param=&quot;[josh]&quot; /]

You're going to have to provide an actual example of what you're referring to that I can actually test against.
Title: Re: REPORT: Potentially "Fatal Flaw" in SMF's bbcode parser
Post by: Illori on August 02, 2015, 08:02:37 PM
maybe

[code=replace]text[/code] would be an example of what he is saying. you can also put replace in quotes.
Title: Re: REPORT: Potentially "Fatal Flaw" in SMF's bbcode parser
Post by: margarett on August 03, 2015, 08:07:34 AM
Just to add a bit more to this...

The issue is also being discussed @elkarte.net and Spuds noticed an important "detail"
http://www.elkarte.net/community/index.php?topic=2805.msg19158#msg19158

It seems that some permutations are already not calculated and you should have blown PHP's memory limit wayyyy before the 14th parameter...

I would agree with their assertion: basically fix the wrong permutations and limit the number of parameters to 5 or 6. While your findings are good, I'm not sure if anyone will ever use that many parameters and just the fact that you allow that many memory to be drained (optimized or not) is an *excellent* way of allowing a DoS in your forum...
Title: Re: REPORT: Potentially "Fatal Flaw" in SMF's bbcode parser
Post by: dougiefresh on August 03, 2015, 07:18:37 PM
I've fixed the fix_param_order function so that it correctly deals with situations like this:
[tag="abc]def[esdf]"]
The new code reads like this:
// Rearranges all parameters to be in the right order.  Returns TRUE if no parameters are leftover.
function fix_param_order($message, &$parameters, &$out)
{
$test = substr($message, 0, $pos = strpos($message, ']'));
while (substr_count($test, '"') % 2 !== 0)
{
$pos += ($pos1 = strpos(substr($message, $pos), '"'));
if ($pos1 === false)
break;
$test = substr($message, 0, ($pos += strpos(substr($message, $pos), ']')));
}
$params = explode(' ', $test);
unset($params[0]);
$order = array();
$out = $old = '';
foreach ($params as $param)
{
if (strpos($param, '=') === false)
$order[$old] .= ' ' . $param;
else
$order[$old = substr($param, 0, strpos($param, '='))] = substr($param, strpos($param, '=') + 1);
}
foreach ($parameters as $key => $ignore)
{
$out .= (isset($order[$key]) ? ' ' . $key . '=' . $order[$key] : '');
unset($order[$key]);
}
return count($order) == 0;
}


Quote from: margarett on August 03, 2015, 08:07:34 AM
I would agree with their assertion: basically fix the wrong permutations and limit the number of parameters to 5 or 6. While your findings are good, I'm not sure if anyone will ever use that many parameters and just the fact that you allow that many memory to be drained (optimized or not) is an *excellent* way of allowing a DoS in your forum...
I frankly disagree, but not interested in arguing about it right now.  Yeah, DoS's are not desirable in any way, and frankly, I had no idea that it was a problem until it was reported.  I fixed my mod as soon as I could, because obviously it's not a good thing to crash a forum  :P

BTW, My mod has been doing the "rearrange the parameters" thing for a while in order to correctly process the message IDs parameter at the end of the tag usage.....  Seems like a good thing to try...  O:)  So I did a parse_bbc fix on the Post & PM ILA mod to do the rearranging of the parameters (again), then run a single regex to check to see if that parameter mix is found.  Works....

EDIT: I wanna say this.  My solution (if I can ever get it working to y'all's satisfaction) is a cheaper alternative, memory and time-wise, to permutating a number of parameters then test to see which permutation is the correct one.  Granted, the performance difference on tags with few parameters doesn't make much of a difference, but it makes a difference the more parameters a tag has.... Just my two cents....
Title: Re: REPORT: Potentially "Fatal Flaw" in SMF's bbcode parser
Post by: live627 on August 03, 2015, 11:33:26 PM
Quote
I would agree with their assertion: basically fix the wrong permutations and limit the number of parameters to 5 or 6.
+1
Title: Re: REPORT: Potentially "Fatal Flaw" in SMF's bbcode parser
Post by: margarett on August 04, 2015, 04:45:14 AM
@dougie, much respect for your hard work and passion ;)

Yet, you need to understand that *any* change we could put into "production" regarding parse_bbc needs to *extremely* evaluated. It's probably the biggest, oldest and most important function in SMF's code... The fact that it hasn't been touched for *years* (which is not necessarily a good thing :P ) also confirms this.

The thing with the sheer number of parameters (and the memory loophole that exists here) is that... no one actually will use them. Heck, most people don't even know the BBCodes if there aren't buttons around, let alone add 6, 7, 8 parameters to it and do it correctly...
And by working the beast which is parse_bbc in order to "fix" an edge case, we might be messing many other cases which are now working great. It needs *serious* test and benchmarking before it ever gets to the code...
Overall that many parameters is (IMO) poor UI. It should be preferable to split a BBC in 2 or something like that, instead of stuffing an endless list or arguments which, quite frankly, no one will have the patience to use...
Title: Re: REPORT: Potentially "Fatal Flaw" in SMF's bbcode parser
Post by: Colin on August 05, 2015, 11:47:30 AM
You could simply keep track of the max amount of BBC code parameters and if a user passes in more than the max then simply throw an error before trying to evaluate and find a match. I think Dougie's solution is something we should adopt, regardless if it is used often now.
Title: Re: REPORT: Potentially "Fatal Flaw" in SMF's bbcode parser
Post by: Joshua Dickerson on August 05, 2015, 01:51:30 PM
Quote from: dougiefresh on August 02, 2015, 04:50:45 PM
Submitted a new PR and commit....

@Joshua: I think you're missing the whole point.  The issue is the PERMUTE function!  Please go back and read the first post....  ::) :P  And yes, I did attempt using the permute function with array_keys.  That actually produced a LARGER array than with the parameter regex's, which I truly don't understand....
I didn't miss the point at all. The issue is with the RAM consumption and the time. The cause is the permute() function. Since you didn't provide a solution, I just tweaked the current, working solution to better handle RAM and the amount of iterations it is likely to do.

Good work on your solution. I would like to see it tested further but it looks good.
Title: Re: REPORT: Potentially "Fatal Flaw" in SMF's bbcode parser
Post by: dougiefresh on August 20, 2015, 03:58:28 AM
My Faster SMF BBCode Parser (http://www.simplemachines.org/community/index.php?topic=539070.0) mod has been released, so maybe it will be tested more....  Btw, I've closed my pull requests until a better solution to the problem has been thoroughly tested and is satisfactory to the testers/users...
Title: Re: REPORT: Potentially "Fatal Flaw" in SMF's bbcode parser
Post by: Joshua Dickerson on August 22, 2015, 04:42:21 AM
I don't have an SMF install right now, but should this line us &quot; instead of "?
$tpos += ($pos1 = strpos(substr($message, $tpos), '"'));
Title: Re: REPORT: Potentially "Fatal Flaw" in SMF's bbcode parser
Post by: dcmouser on August 31, 2015, 11:56:23 PM
Great work, dougie.
Title: Re: REPORT: Potentially "Fatal Flaw" in SMF's bbcode parser
Post by: dougiefresh on September 01, 2015, 04:37:15 PM
Quote from: Joshua Dickerson on August 22, 2015, 04:42:21 AM
I don't have an SMF install right now, but should this line us &quot; instead of "?
$tpos += ($pos1 = strpos(substr($message, $tpos), '"'));
Hmmmm.....  That's a good question.  Let me test and see....

Quote from: dcmouser on August 31, 2015, 11:56:23 PM
Great work, dougie.
Thanks....
Title: Re: REPORT: Potentially "Fatal Flaw" in SMF's bbcode parser
Post by: dougiefresh on September 04, 2015, 09:07:12 AM
UPDATE: The nightly version of SMF 2.1 Beta 2 has addressed this issue so that memory issues as described in the first post cannot crash the forum in this way....
Title: Re: REPORT: Potentially "Fatal Flaw" in SMF's bbcode parser
Post by: Joshua Dickerson on September 04, 2015, 03:46:22 PM
In testing of your function, it takes about ~18% more time for the most common usages (<4 parameters). With more parameters, your implementation might be faster but there's no default BBC that has 4+ parameters and I doubt there are many mod BBC that have that. So, I think the best implementation is the one that is currently used.
Title: Re: REPORT: Potentially "Fatal Flaw" in SMF's bbcode parser
Post by: Joshua Dickerson on September 04, 2015, 03:48:37 PM
In testing, I did find a bug though.

(https://www.simplemachines.org/community/proxy.php?request=http%3A%2F%2Favatars.simplemachinesweb.com%2Fsmf%2Favatar_23_1337883444.png&hash=ba7f46a5fe23a4f1554495142e927e70e874f24c)

<img src="http://avatars.simplemachinesweb.com/smf/avatar_23_1337883444.png" alt="Test height=100" width="100" class="bbc_img resized" style="cursor: pointer;">