Zhikai Wang Homepage

Heteroclinic.net logo

www.heteroclinic.net

	Regular Expression for IPV4 Discussion of the Grammar Checking servers' log is the basic task for system administrators. We always need to find the burried information. For example, the IPV4 addresses recorded in different log files. First, we discuss the regular expression for ASCII strings represent number 0 to 255. To show it clearly, we didn't merge the identical entries. Latex formula: $ D \rightarrow 0\|1[0-9]\{0,1,2\}\|2[0-9]\{0,1\}\|2[0-4][0-9]\|25[0-5]\|[3-9][0-9]\{0,1\}$ We draw the digram of the spanning tree for ASCII strings represent number 0 to 255. Second, we discuss the regular expression for an IP address V4 $P$for private network. $P \rightarrow D_1.D_2.D_3.D_4 $\\ $ D_i \rightarrow 0\|1[0-9]\{0,1,2\}\|2[0-9]\{0,1\}\|2[0-4][0-9]\|25[0-5]\|[3-9][0-9]\{0,1\}$, where $i=1,2,3,4$ But search strings matching pattern $P$ is not sufficient. For examples, 025.13.23.34, or 10.12.13.14.someisp.com, or 1.2.3.4.5.6.7 are not the information we are seeking. So the grammar is not context free. We need a wrapper pattern to validate a minimum context that the objective pattern is in. This wrapper pattern is dfined as $W$. Our assumption is that a valid string of ip address is delimited by a character that is not [0-9] or `.', or by begin of line `\verb\|^\| ' and end of line `\$'. $W \rightarrow ( [\verb\|^\| 0-9.]\| \verb\|^\| ) P ( [\verb\|^\| 0-9.]\|)\$ $\\ $P \rightarrow D_1.D_2.D_3.D_4 $\\ $D_i \rightarrow 0\|1[0-9]\{0,1,2\}\|2[0-9]\|24[0-9]\|25[0-5]$, where $i=1,2,3,4$.
	Regular Expression for IPV4 Practice with egrep W e give the example by using egrep. egrep -o '([^0-9.]\|^)(([0-9]\|1([0-9]){1,2}\|2[0-9]\|2[0-4][0-9]\|25[0-5]\|[3-9][0-9])\.){3}([0-9]\|1([0-9]){1,2}\|2[0-9]\|2[0-4][0-9]\|25[0-5]\|[3-9][0-9])([^0-9.]\|$)' atest.txt \| egrep -o '(([0-9]\|1([0-9]){1,2}\|2[0-9]\|2[0-4][0-9]\|25[0-5]\|[3-9][0-9])\.){3}([0-9]\|1([0-9]){1,2}\|2[0-9]\|2[0-4][0-9]\|25[0-5]\|[3-9][0-9])' The example file `atest.txt': fesefefefef 80.76.5.154 - - [19/Feb/2012:03:42:25 -0500] "GET / HTTP/1.1" 200 10734 "-" "Mozilla/5.0 (compatible; Baiduspider/2.0; +http://www.baidu.com/search/spider.html)" sfe 157.56.4.201 - - [19/Feb/2012:03:42:44 -0500] "GET /blog/?feed=comments-rss2 HTTP/1.1" 404 203 "-" "msnbot-UDiscovery/2.0b (+http://search.msn.com/msnbot.htm)" s207.46.12.225 - - [19/Feb/2012:03:51:00 -0500] "GET /blog/?feed=comments-rss2 HTTP/1.1" 404 203 "-" "msnbot-UDiscovery/2.0b (+http://search.msn.com/msnbot.htm)" 61.135.249.51s - - [19/Feb/2012:03:58:17 -0500] "GET / HTTP/1.1" 200 10734 "-" "Mozilla/5.0 (compatible; YodaoBot/1.0; http://www.yodao.com/help/webmaster/spider/; )" 207.241.s237.220 - - [19/Feb/2012:04:02:05 -0500] "GET /robots.txt HTTP/1.0" 404 208 "-" "Mozilla/5.0 (compatible; archive.org_bot +http://www.archive.org/details/archive.org_bot)" 207.s241.237.220 - - [19/Feb/2012:04:02:09 -0500] "GET /press.html HTTP/1.0" 200 5172 "-" "Mozilla/5.0 (compatible; archive.org_bot +http://www.archive.org/details/archive.org_bot)" 207.dddd46.199.229 - - [19/Feb/2012:04:09:48 -0500] "GET /robots.txt HTTP/1.1" 404 208 "-" "msnbot-media/1.1 (+http://search.msn.com/msnbot.htm)" dd 0.0.0.0 255.255.255.255 255.25.256.25 00.1.1.00 0.255.255.0 1.2.3.4 1.02.3.4 258.2.2.0 23.3.3.2. 1.2.3.4.5. 10.10.10.1.some-isp.com The results, we believe masks and broadcasts are valid ip addresses: 80.76.5.154 157.56.4.201 207.46.12.225 61.135.249.51 0.0.0.0 255.255.255.255 0.255.255.0 1.2.3.4 Some other log examples. The ip address may not be delimited by white spaces. iptables: Mar 8 10:40:23 xxx-server kernel: IN=bond0 OUT= MAC=00:a0:d1:e9:a0:ae:00:90:fb:1b:85:e0:08:00 SRC=70.55.67.65 DST=38.145.11.134 LEN=52 TOS=0x00 PREC=0x20 TTL=117 ID=28429 DF PROTO=TCP SPT=30531 DPT=443 WINDOW=8192 RES=0x00 SYN URGP=0 A log4j item 138505 [Thread-0] INFO EchoServer - Accepted connection from:Socket[addr=/192.166.10.47,port=22429,localport=8082] It is produced by the following Java lines. SocketChannel tmpfrontchannel = ssc.accept(); logger.info("Accepted connection from:"+ tmpfrontchannel.socket()); If you find something wrong, please leave me a message by email.
	Concurrency Basics: V. Different Sleeping Values Our updated version of program is #include <Windows.h> #include <iostream> #include <queue> #include <time.h> class Task { protected: HANDLE mutex; bool halted ; int id ; int repeattimes ; public: friend DWORD WINAPI runTask(void); Task (int nid, int nrep,HANDLE nmutex ) : halted(false), id(nid),repeattimes(nrep),mutex(nmutex) { } void halt () { halted = true; } void setHalted (bool nb ) { halted = nb; } bool getHalted () { return halted; } virtual ~Task() { } }; DWORD WINAPI runTask(void lp) { Task * md = (Task)lp; int sleeptime = 20; WaitForSingleObject(md->mutex,INFINITE); std::cout<<md->id<<":\t"<<md->repeattimes<<std::endl; ReleaseMutex(md->mutex); int i = 0; while( !md->halted && (i++ < md->repeattimes) ) { Sleep(sleeptime); } md->halted = true; WaitForSingleObject(md->mutex,INFINITE); std::cout<<md->id<<":\t"<<md->halted<<" i:"<<i<<std::endl; ReleaseMutex(md->mutex); return 0; }; std::queue<HANDLE> handles; HANDLE tmphandle = NULL; int main() { HANDLE mutex = CreateMutex(NULL, false, NULL);; srand ( time(NULL) ); int ul = 350; int ll = 1*50; unsigned int num = 20; unsigned int i =0 ; for (i=0; i< num; i++) { tmphandle = CreateThread(0,0,&runTask, new Task(i,rand()% (ul-ll) + ll,mutex) , 0,0); if (NULL != tmphandle) { handles.push(tmphandle); } else { std::cout<<i<<" failed to start!"<<std::endl; } } Sleep(5000); if (NULL != mutex) { CloseHandle(mutex); mutex = NULL; } std::cout<<" End of main()."<<std::endl; return 0; } We set different sleeping value in the main function to observe how the program behave. We know set ll as 1000ms, ul as 3000ms. First we set Sleep(800). 0: 77 1: 96 2: 55 3: 65 4: 137 5: 147 6: 140 7: 52 8: 138 9: 55 10: 108 11: 118 12: 87 13: 116 14: 86 15: 135 16: 85 17: 92 18: 85 19: 145 End of main(). Second we set Sleep(2000). 0: 60 1: 83 2: 141 3: 122 4: 129 5: 68 6: 97 7: 65 8: 83 9: 144 10: 126 11: 85 12: 80 13: 106 14: 63 15: 128 16: 64 17: 128 18: 102 19: 106 0: 1 i:61 14: 1 i:64 16: 1 i:65 7: 1 i:66 5: 1 i:69 12: 1 i:81 1: 1 i:84 8: 1 i:84 11: 1 i:86 6: 1 i:98 End of main(). Third we set Sleep(5000). 0: 98 1: 64 2: 72 3: 73 4: 57 5: 51 6: 148 7: 91 8: 142 9: 69 10: 114 11: 135 12: 108 13: 124 14: 62 15: 131 16: 108 17: 124 18: 88 19: 135 5: 1 i:52 4: 1 i:58 14: 1 i:63 1: 1 i:65 9: 1 i:70 2: 1 i:73 3: 1 i:74 18: 1 i:89 7: 1 i:92 0: 1 i:99 12: 1 i:109 16: 1 i:109 10: 1 i:115 13: 1 i:125 17: 1 i:125 15: 1 i:132 11: 1 i:136 19: 1 i:136 8: 1 i:143 6: 1 i:149 End of main(). From the above experiments, we know all the child threads exit as the main function terminated. Our current implementation doesn't show each child thread status if we end our program in such a way. So we know why need the condition variables. The usage will be shown in the next section.
	Concurrency Basics: VI. Use Condition Variable We modify the program accordingly. #include <Windows.h> #include <iostream> #include <deque> #include <time.h> class Task { protected: HANDLE mutex; bool halted ; int id ; int repeattimes ; public: friend DWORD WINAPI runTask(void); Task (int nid, int nrep,HANDLE nmutex ) : halted(false), id(nid),repeattimes(nrep),mutex(nmutex) { } void halt () { halted = true; } void setHalted (bool nb ) { halted = nb; } bool getHalted () { return halted; } virtual ~Task() { } }; DWORD WINAPI runTask(void lp) { Task * md = (Task)lp; int sleeptime = 20; WaitForSingleObject(md->mutex,INFINITE); std::cout<<md->id<<":\t"<<md->repeattimes<<std::endl; ReleaseMutex(md->mutex); int i = 0; while( !md->halted && (i++ < md->repeattimes) ) { Sleep(sleeptime); } md->halted = true; WaitForSingleObject(md->mutex,INFINITE); std::cout<<md->id<<":\t"<<md->halted<<" i:"<<i<<std::endl; ReleaseMutex(md->mutex); return 0; }; std::deque<Task > tasks; std::deque<HANDLE> handles; HANDLE tmphandle = NULL; int main() { HANDLE mutex = CreateMutex(NULL, false, NULL);; srand ( time(NULL) ); int ul = 350; int ll = 150; unsigned int num = 20; unsigned int i =0 ; for (i=0; i< num; i++) { Task * tmptaskpt = new Task(i,rand()% (ul-ll) + ll ,mutex); tmphandle = CreateThread(0,0,&runTask, tmptaskpt , 0,0); if (NULL != tmphandle) { handles.push_back(tmphandle); } else { std::cout<<i<<" failed to start!"<<std::endl; } tasks.push_back(tmptaskpt); } Sleep(800); // Use condition variables for (std::deque<Task >::const_iterator iter = tasks.begin(); iter != tasks.end(); iter++) (*iter).halt(); Sleep(200); //Sleep again to terminate the child threads, should be longer than the slice time. if (NULL != mutex) { CloseHandle(mutex); mutex = NULL; } std::cout<<" End of main()."<<std::endl; return 0; } Again we try to let the threads terminate prematurely by Sleep(800). 0: 102 1: 140 2: 136 3: 69 4: 81 5: 113 6: 145 7: 81 8: 74 9: 63 10: 80 11: 144 12: 63 13: 79 14: 67 15: 131 16: 59 17: 76 18: 86 19: 98 2: 1 i:40 19: 1 i:39 3: 1 i:40 4: 1 i:40 5: 1 i:40 6: 1 i:40 7: 1 i:40 8: 1 i:40 9: 1 i:40 10: 1 i:40 11: 1 i:40 12: 1 i:40 13: 1 i:40 14: 1 i:40 15: 1 i:40 16: 1 i:40 17: 1 i:40 18: 1 i:40 0: 1 i:41 1: 1 i:41 End of main(). Now we can check the child threads' status.

	Regular Expression for IPV4 Discussion of the Grammar Checking servers' log is the basic task for system administrators. We always need to find the burried information. For example, the IPV4 addresses recorded in different log files. First, we discuss the regular expression for ASCII strings represent number 0 to 255. To show it clearly, we didn't merge the identical entries. Latex formula: $ D \rightarrow 0\|1[0-9]\{0,1,2\}\|2[0-9]\{0,1\}\|2[0-4][0-9]\|25[0-5]\|[3-9][0-9]\{0,1\}$ We draw the digram of the spanning tree for ASCII strings represent number 0 to 255. Second, we discuss the regular expression for an IP address V4 $P$for private network. $P \rightarrow D_1.D_2.D_3.D_4 $\\ $ D_i \rightarrow 0\|1[0-9]\{0,1,2\}\|2[0-9]\{0,1\}\|2[0-4][0-9]\|25[0-5]\|[3-9][0-9]\{0,1\}$, where $i=1,2,3,4$ But search strings matching pattern $P$ is not sufficient. For examples, 025.13.23.34, or 10.12.13.14.someisp.com, or 1.2.3.4.5.6.7 are not the information we are seeking. So the grammar is not context free. We need a wrapper pattern to validate a minimum context that the objective pattern is in. This wrapper pattern is dfined as $W$. Our assumption is that a valid string of ip address is delimited by a character that is not [0-9] or `.', or by begin of line `\verb\|^\| ' and end of line `\$'. $W \rightarrow ( [\verb\|^\| 0-9.]\| \verb\|^\| ) P ( [\verb\|^\| 0-9.]\|)\$ $\\ $P \rightarrow D_1.D_2.D_3.D_4 $\\ $D_i \rightarrow 0\|1[0-9]\{0,1,2\}\|2[0-9]\|24[0-9]\|25[0-5]$, where $i=1,2,3,4$.
	Regular Expression for IPV4 Practice with egrep W e give the example by using egrep. egrep -o '([^0-9.]\|^)(([0-9]\|1([0-9]){1,2}\|2[0-9]\|2[0-4][0-9]\|25[0-5]\|[3-9][0-9])\.){3}([0-9]\|1([0-9]){1,2}\|2[0-9]\|2[0-4][0-9]\|25[0-5]\|[3-9][0-9])([^0-9.]\|$)' atest.txt \| egrep -o '(([0-9]\|1([0-9]){1,2}\|2[0-9]\|2[0-4][0-9]\|25[0-5]\|[3-9][0-9])\.){3}([0-9]\|1([0-9]){1,2}\|2[0-9]\|2[0-4][0-9]\|25[0-5]\|[3-9][0-9])' The example file `atest.txt': fesefefefef 80.76.5.154 - - [19/Feb/2012:03:42:25 -0500] "GET / HTTP/1.1" 200 10734 "-" "Mozilla/5.0 (compatible; Baiduspider/2.0; +http://www.baidu.com/search/spider.html)" sfe 157.56.4.201 - - [19/Feb/2012:03:42:44 -0500] "GET /blog/?feed=comments-rss2 HTTP/1.1" 404 203 "-" "msnbot-UDiscovery/2.0b (+http://search.msn.com/msnbot.htm)" s207.46.12.225 - - [19/Feb/2012:03:51:00 -0500] "GET /blog/?feed=comments-rss2 HTTP/1.1" 404 203 "-" "msnbot-UDiscovery/2.0b (+http://search.msn.com/msnbot.htm)" 61.135.249.51s - - [19/Feb/2012:03:58:17 -0500] "GET / HTTP/1.1" 200 10734 "-" "Mozilla/5.0 (compatible; YodaoBot/1.0; http://www.yodao.com/help/webmaster/spider/; )" 207.241.s237.220 - - [19/Feb/2012:04:02:05 -0500] "GET /robots.txt HTTP/1.0" 404 208 "-" "Mozilla/5.0 (compatible; archive.org_bot +http://www.archive.org/details/archive.org_bot)" 207.s241.237.220 - - [19/Feb/2012:04:02:09 -0500] "GET /press.html HTTP/1.0" 200 5172 "-" "Mozilla/5.0 (compatible; archive.org_bot +http://www.archive.org/details/archive.org_bot)" 207.dddd46.199.229 - - [19/Feb/2012:04:09:48 -0500] "GET /robots.txt HTTP/1.1" 404 208 "-" "msnbot-media/1.1 (+http://search.msn.com/msnbot.htm)" dd 0.0.0.0 255.255.255.255 255.25.256.25 00.1.1.00 0.255.255.0 1.2.3.4 1.02.3.4 258.2.2.0 23.3.3.2. 1.2.3.4.5. 10.10.10.1.some-isp.com The results, we believe masks and broadcasts are valid ip addresses: 80.76.5.154 157.56.4.201 207.46.12.225 61.135.249.51 0.0.0.0 255.255.255.255 0.255.255.0 1.2.3.4 Some other log examples. The ip address may not be delimited by white spaces. iptables: Mar 8 10:40:23 xxx-server kernel: IN=bond0 OUT= MAC=00:a0:d1:e9:a0:ae:00:90:fb:1b:85:e0:08:00 SRC=70.55.67.65 DST=38.145.11.134 LEN=52 TOS=0x00 PREC=0x20 TTL=117 ID=28429 DF PROTO=TCP SPT=30531 DPT=443 WINDOW=8192 RES=0x00 SYN URGP=0 A log4j item 138505 [Thread-0] INFO EchoServer - Accepted connection from:Socket[addr=/192.166.10.47,port=22429,localport=8082] It is produced by the following Java lines. SocketChannel tmpfrontchannel = ssc.accept(); logger.info("Accepted connection from:"+ tmpfrontchannel.socket()); If you find something wrong, please leave me a message by email.
	Concurrency Basics: V. Different Sleeping Values Our updated version of program is #include <Windows.h> #include <iostream> #include <queue> #include <time.h> class Task { protected: HANDLE mutex; bool halted ; int id ; int repeattimes ; public: friend DWORD WINAPI runTask(void); Task (int nid, int nrep,HANDLE nmutex ) : halted(false), id(nid),repeattimes(nrep),mutex(nmutex) { } void halt () { halted = true; } void setHalted (bool nb ) { halted = nb; } bool getHalted () { return halted; } virtual ~Task() { } }; DWORD WINAPI runTask(void lp) { Task * md = (Task)lp; int sleeptime = 20; WaitForSingleObject(md->mutex,INFINITE); std::cout<<md->id<<":\t"<<md->repeattimes<<std::endl; ReleaseMutex(md->mutex); int i = 0; while( !md->halted && (i++ < md->repeattimes) ) { Sleep(sleeptime); } md->halted = true; WaitForSingleObject(md->mutex,INFINITE); std::cout<<md->id<<":\t"<<md->halted<<" i:"<<i<<std::endl; ReleaseMutex(md->mutex); return 0; }; std::queue<HANDLE> handles; HANDLE tmphandle = NULL; int main() { HANDLE mutex = CreateMutex(NULL, false, NULL);; srand ( time(NULL) ); int ul = 350; int ll = 1*50; unsigned int num = 20; unsigned int i =0 ; for (i=0; i< num; i++) { tmphandle = CreateThread(0,0,&runTask, new Task(i,rand()% (ul-ll) + ll,mutex) , 0,0); if (NULL != tmphandle) { handles.push(tmphandle); } else { std::cout<<i<<" failed to start!"<<std::endl; } } Sleep(5000); if (NULL != mutex) { CloseHandle(mutex); mutex = NULL; } std::cout<<" End of main()."<<std::endl; return 0; } We set different sleeping value in the main function to observe how the program behave. We know set ll as 1000ms, ul as 3000ms. First we set Sleep(800). 0: 77 1: 96 2: 55 3: 65 4: 137 5: 147 6: 140 7: 52 8: 138 9: 55 10: 108 11: 118 12: 87 13: 116 14: 86 15: 135 16: 85 17: 92 18: 85 19: 145 End of main(). Second we set Sleep(2000). 0: 60 1: 83 2: 141 3: 122 4: 129 5: 68 6: 97 7: 65 8: 83 9: 144 10: 126 11: 85 12: 80 13: 106 14: 63 15: 128 16: 64 17: 128 18: 102 19: 106 0: 1 i:61 14: 1 i:64 16: 1 i:65 7: 1 i:66 5: 1 i:69 12: 1 i:81 1: 1 i:84 8: 1 i:84 11: 1 i:86 6: 1 i:98 End of main(). Third we set Sleep(5000). 0: 98 1: 64 2: 72 3: 73 4: 57 5: 51 6: 148 7: 91 8: 142 9: 69 10: 114 11: 135 12: 108 13: 124 14: 62 15: 131 16: 108 17: 124 18: 88 19: 135 5: 1 i:52 4: 1 i:58 14: 1 i:63 1: 1 i:65 9: 1 i:70 2: 1 i:73 3: 1 i:74 18: 1 i:89 7: 1 i:92 0: 1 i:99 12: 1 i:109 16: 1 i:109 10: 1 i:115 13: 1 i:125 17: 1 i:125 15: 1 i:132 11: 1 i:136 19: 1 i:136 8: 1 i:143 6: 1 i:149 End of main(). From the above experiments, we know all the child threads exit as the main function terminated. Our current implementation doesn't show each child thread status if we end our program in such a way. So we know why need the condition variables. The usage will be shown in the next section.
	Concurrency Basics: VI. Use Condition Variable We modify the program accordingly. #include <Windows.h> #include <iostream> #include <deque> #include <time.h> class Task { protected: HANDLE mutex; bool halted ; int id ; int repeattimes ; public: friend DWORD WINAPI runTask(void); Task (int nid, int nrep,HANDLE nmutex ) : halted(false), id(nid),repeattimes(nrep),mutex(nmutex) { } void halt () { halted = true; } void setHalted (bool nb ) { halted = nb; } bool getHalted () { return halted; } virtual ~Task() { } }; DWORD WINAPI runTask(void lp) { Task * md = (Task)lp; int sleeptime = 20; WaitForSingleObject(md->mutex,INFINITE); std::cout<<md->id<<":\t"<<md->repeattimes<<std::endl; ReleaseMutex(md->mutex); int i = 0; while( !md->halted && (i++ < md->repeattimes) ) { Sleep(sleeptime); } md->halted = true; WaitForSingleObject(md->mutex,INFINITE); std::cout<<md->id<<":\t"<<md->halted<<" i:"<<i<<std::endl; ReleaseMutex(md->mutex); return 0; }; std::deque<Task > tasks; std::deque<HANDLE> handles; HANDLE tmphandle = NULL; int main() { HANDLE mutex = CreateMutex(NULL, false, NULL);; srand ( time(NULL) ); int ul = 350; int ll = 150; unsigned int num = 20; unsigned int i =0 ; for (i=0; i< num; i++) { Task * tmptaskpt = new Task(i,rand()% (ul-ll) + ll ,mutex); tmphandle = CreateThread(0,0,&runTask, tmptaskpt , 0,0); if (NULL != tmphandle) { handles.push_back(tmphandle); } else { std::cout<<i<<" failed to start!"<<std::endl; } tasks.push_back(tmptaskpt); } Sleep(800); // Use condition variables for (std::deque<Task >::const_iterator iter = tasks.begin(); iter != tasks.end(); iter++) (*iter).halt(); Sleep(200); //Sleep again to terminate the child threads, should be longer than the slice time. if (NULL != mutex) { CloseHandle(mutex); mutex = NULL; } std::cout<<" End of main()."<<std::endl; return 0; } Again we try to let the threads terminate prematurely by Sleep(800). 0: 102 1: 140 2: 136 3: 69 4: 81 5: 113 6: 145 7: 81 8: 74 9: 63 10: 80 11: 144 12: 63 13: 79 14: 67 15: 131 16: 59 17: 76 18: 86 19: 98 2: 1 i:40 19: 1 i:39 3: 1 i:40 4: 1 i:40 5: 1 i:40 6: 1 i:40 7: 1 i:40 8: 1 i:40 9: 1 i:40 10: 1 i:40 11: 1 i:40 12: 1 i:40 13: 1 i:40 14: 1 i:40 15: 1 i:40 16: 1 i:40 17: 1 i:40 18: 1 i:40 0: 1 i:41 1: 1 i:41 End of main(). Now we can check the child threads' status.