소수(prime number)란 1보다 큰 자연수 중 1과 자기 자신 두 개만을 약수로 갖는 수를 말한다. 합성수(composite number)란 1보다 큰 자연수 중 소수가 아닌 수를 말하며 3개 이상의 약수를 갖는다. 1은 소수도 합성수도 아니다. 5개의 자연수를 입력받아 소수인지 합성수인지를 판단하는 프로그램을 작성하시오.
입력형식
10억 이하의 자연수 5개가 공백으로 구분되어 주어진다.
출력형식
입력된 순서대로 한 줄에 한 개씩 소수이면 "prime number",
합성수이면 "composite number",
소수도 합성수도 아니면 "number one"이라고 출력한다.
<코드>
#include <stdio.h>#include <math.h>voidcheck_prime(int N)
{
int sq, count=0;
if(N==1)
{
printf("number one\n");
return;
}
sq = (int)sqrt(N);
for (int i = 2; i <= sq; i++)
{
if (!(N%i))
{
count++;
}
if(count>0)
break;
}
if(!count)
printf("prime number\n");
else
printf("composite number\n");
}
intmain()
{
int arr[5];
for(int i=0; i<5; i++)
scanf("%d", &arr[i]);
for(int i=0; i<5; i++)
check_prime(arr[i]);
return0;
}
1. load_names와 compare 함수의 기능을 수정하였으며 binary search를 수행한다. 2. 새로운 이름이 들어오면 제일 뒤에 추가하는 것이 아니라 정렬된 리스트를 유지하도록 위치를 찾아 삽입한다. 3. memmove함수를 사용해 구조체가 삽입될 위치 뒤에있는 리스트를 한칸씩 민다.
사용된 구조체도 이전 프로그램과 동일하다.
[tNames]
typedef struct {
int len; // 배열에 저장된 이름의 수int capacity; // 배열의 용량 (배열에 저장 가능한 이름의 수)
tName *data; // 이름 배열의 포인터
} tNames;
[tName]
typedef struct {
char name[20]; // 이름char sex; // 성별 M or Fint freq[MAX_YEAR_DURATION]; // 연도별 빈도
} tName;
해당 프로그램에는 총 6개의 함수가 정의되어 있다.
1. create_names: 이름 구조체를 초기화해준다.(len을 0으로, capacity를 1로 초기화한 후 구조체 포인터를 return한다)
2. load_names: 입력 파일을 읽어들인다.
3. compare: bsearch를 위한 비교 함수이다.
4. print_names: 구조체 배열을 화면에 출력해준다.
5. destroy_names: 이름 구조체 메모리를 해제해준다.
6. binary_search: 이진 탐색 함수이다. key가 발견되는 경우 배열의 인덱스를 return하고 key가 발견되지 않는 경우에 key가 삽입되어야 할 배열의 인덱스가 return된다.
대략적인 구조는 이전과 동일하지만 bsearch함수를 사용하여 이름이 삽입될 위치를 확인하고 기존에 존재했던 이름이면 freq변수의 해당 연도 인덱스에 추가만해주고 기존에 존재하지 않았던 이름이라면 메모리 확인을 해준 후 binary_search함수를 사용해서 tName배열에 삽입될 index를 return받은 뒤 memmove로 그 뒤에 있는 리스트를 한칸씩 미룬 후 그 위치에 이름, 성별, 빈도를 저장한다.
2. fake chunk1의 size 값을 지정한다. => free():invalid size오류 회피
3. fake chunk2의 size 값을 지정한다. => free():invalid next size오류 회피
※이 때 size값은 같은 값으로 해도 되고 top chunk처럼 큰 값으로 해도 된다.
4. chunk의 포인터를 원래의 정상적인 chunk가 아닌 fake chunk1을 가르키도록 한다.
5. chunk를 해제시킨다.
이렇게 되면 fake chunk1이 해제되어 fast bin에 들어가고, 같은 크기의 메모리가 할당될 때 fake chunk1이 다시 나타나는 그런 방법인데 여기서는 그냥 free만 무사히 시키면 되니까 8로 끝나는 주소에 size만 넣어줘서 fake chunk를 만들어주면 된다.
PIE는 걸려있지 않으므로 쓰기 권한이 있는 영역을 대충 골라서 fack chunk를 만들어준다.
bss영역인 0x601038쯤에 size를 적고 0x601040을 free()의 인자로 주자. size로는 적당히 0x30정도를 넣고 0x30만큼 뒤인 0x601068에 next chunk size로 아무 값이나 넣어주면 size check를 통과할 수 있을 것이다.
그러면 공격 시나리오를 다시 생각해보자.
1. ret 주소를 leak한다.
2. "1"을 입력하여 buf에 dummy(8byte)+ret address를 적어준다.
3. "3"을 입력하여 v7에 dummy 8byte를 입력하고 buf의 주소를 ret address로 바꿔준다.
4. 다시 "1"을 입력하여 ret address에 win함수의 주소+0x601038(fake chunk1 size address)를 넣는다.
파일에 이름, 성별, 빈도가 ","로 구분되어 있다. 파일을 한 줄씩 입력받으면서 ","를 tab으로 바꿔주고 sscanf로 tab을 구분 기호로 하여 name, sex, freq변수에 넣어준다.
이름을 입력받아서 중복 체크를 해준다. tName 구조체 배열의 길이만큼 구조체를 하나씩 확인하면서 성별과 이름이 같은 구조체가 있는지 확인한다. 만약 중복된 구조체가 존재한다면 freq의 해당 연도의 인덱스에 빈도를 저장한다.
만약 중복된 구조체가 존재하지 않는다면 tNames에 tName구조체를 추가해주어야 한다. 그 전에 capacity와 len이 같은지 확인하여 메모리가 꽉 차지 않았는지 확인해준다. 만약 메모리가 꽉찼다면 realloc을 사용해서 capacity*2만큼의 메모리를 재할당해준 후 capacity 값을 업데이트 해준다.
그 후 tNames의 data 배열 포인터 마지막에 name, sex, freq를 추가해주고 len값을 1 올려준다.
nationality는 24byte까지 입력이 가능하고, age에는 정수가 입력되며 name에는 32byte까지 입력이 가능하다. 아까 확인했었던 Get shell을 선택하게 되면 auth(&s)가 0이 아니라면 win함수가 실행이 된다. 여기서 s는 name이 저장되는 변수이다.
이 부분을 자세히 보면 v6의 크기는 0x10byte이지만 입력은 0x18byte를 받을 수 있어서 v7까지 덮을 수 있는데 age를 입력받는 부분에서 v7에 정수를 입력받을 수 있게 되어있다.
v6에 0x10만큼의 dummy값을 씌우고 v7에 got를 덮어주면 되는데 여기서 "%d"로 age에 입력을 받기 때문에 4byte만 덮을 수 있다. 그러므로 한번도 호출되지 않은 함수를 사용해야 된다. 한번이라도 호출 된 함수는 0x7fff... 이런식으로 6byte가 채워져 있어서 사용이 불가능하다. strcmp의 got를 덮어주고 age에서 win의 주소를 넣어주면 된다~!
