랜덤에 대해..

urmajest의 이미지

웜의 propagation에 대한 간단한 시뮬레이션을 하고 있습니다.

2^32의 IPv4의 어드레스 스페이스 중에 10만개의 vulnerable(웜에

감염될 수 있는) 호스트를 할당하고,

초기에 1개의 호스트가 감염된 상태에서 감염비율이 어떻게 증가하는지를

보기위함입니다.

웜이 감염된 호스트는 다음과 같은 방법을 통해 감염시킬 호스트를 선택합니다.

unsigned int randomAddr = ((rand() % 256) << 24) + ((rand() % 256) << 16) + ((rand() % 256) << 8) + (rand() % 256);

unsigned int에 mapping시켜 랜덤 어드레스를 생성하고,

randomAddr < 100000인 주소가 susceptible 호스트의 주소이죠

그런데, 이와같은 시뮬레이션을 할 때

pentium 3 933, linux 시스템에서는

기대되는 결과값이 나오는데요..

amd athlon xp, windows xp 와 amd durn , windows 2003 server

두개의 시스템에서는 불특정한 어떤 지점에서 더 이상 감염된 호스트 수가

증가하지 않는 것입니다.

즉, 랜덤 값을 생성할 때에 특정한 값을 피해서(?) 생성이 되는 것처럼 보이는데요

두 시스템의 차이점 이라면(linux, windows)

RAND_MAX값이 다르다는 것입니다.

linux의 경우는 2^32 -1 (확실히 기억이 -_-), windows의 경우는 2^15 -1

이더군요.

그렇지만 modulo를 통해 계산을 해주므로 차이가 있을 것 같진 않네요

이러한 현상이 os에 기인하는 것인지 아니면 processor에 기인하는 것인지.

궁금합니다.

참고 삼아 간단한 코드를 올려봅니다.

#include <iostream>
using namespace std;
#include <fstream>
#include <cmath>
#include <ctime>
typedef struct {
	unsigned int addr;
	bool infected;
	short tick;
	bool probing;
} hostdef;
hostdef* host;
bool keepGoing;

void probe(int hostNum)
{
	unsigned int randomAddr = ((rand() % 256) << 24) + ((rand() % 256) << 16) + ((rand() % 256) << 8) + (rand() % 256);
	if (randomAddr < 100000)
		host[randomAddr].infected = true; 
}
int main()
{
	ofstream fout("result.txt", ios_base::trunc);
	
	srand(time(NULL));
	host = new hostdef[100000];
	for (unsigned int i = 0; i < 100000; i++) {
		host[i].addr = i;
		host[i].infected = false;
		host[i].tick = 0;
		host[i].probing = false;
	}
	host[0].infected = true;
	host[0].probing = true;
	keepGoing = true;
	unsigned long long time = 0;
	while (keepGoing)
	{

		int numInfected = 0;

		for (unsigned int i = 0; i < 100000; i++) {
			
			if (host[i].probing) { 
				probe(i);
				++numInfected;
			} else if (host[i].infected) {
				host[i].tick = host[i].tick + 1;
				if (host[i].tick == 4000)
					host[i].probing = true;
				++numInfected;
			}
		}
		if (time % 4000 == 0) 
			fout << "time : " << time << " infected num : " << numInfected << endl;
		++time;
		if (numInfected > 95000) {
				delete[] host;
				fout.close();
				exit(1);
			}
	}	
	return 1;
}
afsadfsaf의 이미지

;;복잡해서 잘 모르겠지만, 제가 알고있는 한도 내에서 말씀드려 보자면..

어떤 랜덤생성 알고리즘들은 나중에 결국 자신을 반복해서 생성한다고 하더군요...

결국, 컴파일러를 바꿔보시면 될겁니다.;
rand() 라이브러리함수 알고리즘의 차이점 때문일테니까요..

아마도 -_-;;

L-System

lsj0713의 이미지

C언어의 난수는 진짜 난수가 아닙니다.

http://groups.google.co.kr/groups?selm=96ta0r%249o4%241%40news2-2.kornet.net
http://groups.google.co.kr/groups?selm=3510E8A6.794B%40secns.sec.samsung.co.kr

재미있는 것은 C 표준이 rand() 함수에 예측 가능할 것을 요구하고 있다는 것입니다.

http://groups.google.co.kr/groups?selm=96rfm4%2463g%241%40news.netple.com
http://groups.google.co.kr/groups?selm=bbfrc5%2438c%241%40news.hananet.net

BSD 시스템의 경우에는 random() 함수가 좀 더 품질 좋은 난수를 생성한다고 하니 고려해 보십시오. BSD 시스템이 아니더라도, 사용하고 계신 컴파일러가 좀 더 품질좋은 난수 생성 함수를 제공하고 있을 가능성이 큽니다. 사용하고 계신 컴파일러의 메뉴얼을 찾아보시길 권하는 바입니다. (gcc면 glibc 메뉴얼, VC++ 이면 MSDN)

전웅의 이미지

몇가지 첨언합니다.


이 글의 잘못된 부분은 full thread 에서 이 글에 이어진 글을 참고하시기 바랍니다.


역사적으로 rand 는 "random" 에서, srand 의 s 는 "seed" 에서 온 것입니다.

그리고 순전히 표준 시간 함수에만 의존하는 seed 에 대해서는 다음 글을 참고하시기 바랍니다.

http://groups.google.co.kr/groups?selm=bak14f%24hoi%241%40news.hananet.net

lsj0713 wrote:
BSD 시스템의 경우에는 random() 함수가 좀 더 품질 좋은 난수를 생성한다고 하니 고려해 보십시오. BSD 시스템이 아니더라도, 사용하고 계신 컴파일러가 좀 더 품질좋은 난수 생성 함수를 제공하고 있을 가능성이 큽니다. 사용하고 계신 컴파일러의 메뉴얼을 찾아보시길 권하는 바입니다. (gcc면 glibc 메뉴얼, VC++ 이면 MSDN)

(implementation 이 지원해준다면) 더 품질 좋은 random number 를 얻을 수 있는 /dev/random 에 대해서는 다음 글을 참고하시기 바랍니다.

http://groups.google.co.kr/groups?selm=bahmej%24ev3%241%40news.hananet.net

그럼...

--
Jun, Woong (woong at gmail.com)
http://www.woong.org

urmajest의 이미지

작성해주신 답변들을 보니 아무래도 vc++ 에서의 rand()함수가 문제였나보네요.

시뮬레이션의 모델이 sql slammer였는데, 거기서 사용한 방법을

그대로 사용하였습니다 ^^

x = (x * 214013 + 2531011) % 2^32

prng인데.. microsoft에서 사용하는 방법이라고도 하더군요

역시나 rand()함수를 사용하는 것보다는 evenly distribute하는 것 같습니다

그럼...

mach의 이미지

실제 세계를 시뮬레이션해보기 위해서는 좋은(?) random()함수를 사용하셔야 하겠지요. 그냥 랜덤한 랜덤함수를 사용해서는 안되겠지요?
그냥 랜덤이란 말그대로 랜덤이고, 좋은 랜덤은 해당 시뮬레이션 모델에 근접한 랜덤함수를 의미합니다. 오래전에 통계학(--;별로 안좋아함)시간에 어떤 시스템은 어떤 분포를 가지고, 또다른 어떤 시스템은 어떤 분포를 가지고, 이제 기억에 남는것은 Poison distribution과 Normal Distribution등이네요.그것도 그래프만 대충 --;.
랜덤함수에서 나오는 값들도 이 분포에 걸맞게 나오도록 함수를 제작하여 사용하면 그냥 랜덤(?!)한 함수를 사용하는 것보다는 보다 실제 모델에 근접한 시뮬레이션을 해볼 수 있다는 것이 요지입니다.
추천으로 netsim이라는 시뮬레이터를 소개합니다. netsim은 네트워크를 시뮬레이션해볼 수 있는 C++수준에서 제작한 시뮬레이터입니다. 음 보다 정확히는 C Preprocessor수준에서 간단한 매크로 언어를 정의하고 매크로언어로 네트워크를 묘사할 수 있는 언어지요. 그리고 물론 시뮬레이션이 가능합니다. 토큰링을 묘사해본 기억이 있으며, 링크의 고장등등을 테스트(시뮬레이션) 해볼 수 있었던 도구로 기억됩니다. 캠브리지대학의 석사과정에 있던 사람이 만들었다가 그거로 박사학위논문쓰고 책도 쓰고 그랬던 것으로 기억합니다
netsim에서는 5-6개정도의 서로다른 분포를 가지는 랜덤함수를 제공했었던것으로 기억합니다. 즉, 랜덤함수에서 나오는 난수를 통계내어보면 통계책에서 보던 특정 분포를 가지게되는 것이지요. 각 상황을 랜덤함수를 바꿔가며 테스트해보았지요.

Quote:
어떤 네트워크가 있는데 임의의 사고(사건,이벤트)가 X분포에 근접하게 발생한다면 해당 네트워크의 진행(프로세스)은 다음과 같다.

각종 분포에 따르는 난수를 발생시키는 함수들을 사용하여 여러가지 사례로 비교 분석해볼 수 있었던 것으로 기억합니다.(오래 전이라.......)
어쩌면 버전업되어 보다 좋은 도구들이 나왔는지도 모르겠네요.
제가 알기로 컴파일러가 제공하는 기본적인 rand()함수는 그 분포가 일정한 값을 가지는 것으로 아는데.......
이를테면
Quote:
|
|
|
+--------------------------(일정)
|
|
|-----------------------------
0

꼭 일정해야만 한다면 모를까? 그렇지 않다면 다른 시도를 해보시는게 좋은듯합니다. 단지 랜덤하면 안될것같습니다.

------------------ P.S. --------------
지식은 오픈해서 검증받아야 산지식이된다고 동네 아저씨가 그러더라.

댓글 달기

Filtered HTML

  • 텍스트에 BBCode 태그를 사용할 수 있습니다. URL은 자동으로 링크 됩니다.
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param><hr>
  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.

BBCode

  • 텍스트에 BBCode 태그를 사용할 수 있습니다. URL은 자동으로 링크 됩니다.
  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param>
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.

Textile

  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • You can use Textile markup to format text.
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param><hr>

Markdown

  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • Quick Tips:
    • Two or more spaces at a line's end = Line break
    • Double returns = Paragraph
    • *Single asterisks* or _single underscores_ = Emphasis
    • **Double** or __double__ = Strong
    • This is [a link](http://the.link.example.com "The optional title text")
    For complete details on the Markdown syntax, see the Markdown documentation and Markdown Extra documentation for tables, footnotes, and more.
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param><hr>

Plain text

  • HTML 태그를 사용할 수 없습니다.
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.
  • 줄과 단락은 자동으로 분리됩니다.
댓글 첨부 파일
이 댓글에 이미지나 파일을 업로드 합니다.
파일 크기는 8 MB보다 작아야 합니다.
허용할 파일 형식: txt pdf doc xls gif jpg jpeg mp3 png rar zip.
CAPTCHA
이것은 자동으로 스팸을 올리는 것을 막기 위해서 제공됩니다.