만약 풀버전을 다운로드 받고 싶다면 sudo apt install ros-humble-desktop-full 명령을 실행할 것. (차이점 파악 필요..)
1.8 ROS2 동작에 필요한 패키지 설치 (통신 라이브러리, CLI 도구 등 포함)
sudo apt install ros-humble-ros-base
2. ROS2 설치 검증
검증 1 - 통신 가능 여부
ROS2의 'Hello World'를 통해 정상적으로 설치되었는지를 확인한다. 이는 두 개의 터미널로 데이터를 주고 받는 것이 가능한지를 확인함으로써 가능하다. Talker와 Listener가 있고 Talker가 터미널에서 출력하는 메시지를 Listener가 받아서 그대로 출력할 수 있는지를 검증한다.
Talker 실행 (C++ 기반)
source /opt/ros/humble/setup.bash
ros2 run demo_nodes_cpp talker
Listener 실행 (Python 기반)
source /opt/ros/humble/setup.bash
ros2 run demo_nodes_py listener
(ROS2는 C++과 Python을 함께 지원한다.)
위 명령들을 실행하면 두 터미널에서 다음과 같은 형태로 Talker가 출력한 값을 Listener가 받아와 그대로 출력하는 것을 확인할 수 있다.
매번 source /opt/ros/humble/setup.bash를 입력하는 것이 귀찮으니 .bashrc 파일에 넣어 터미널이 실행될 때 자동으로 실행되도록 하자
ROS2에서 패키지를 빌드하는 명령이 잘 수행되는지 여부를 판단하여 ROS2가 정상적으로 설치되었음을 확인한다.
soruce ~/opt/ros/humble/setup.bash
mkdir -p ~/robot/src/
cd ~/robot
colcon build --symlink-install
위 명령을 수행하면 다음과 같이 기존의 src 폴더와 더불어 build, install, log가 생성되며 이와 같이 생성된다면 ROS2가 정상적으로 설치된 것이다.
아래는 동일한 내용으로 위와 같이 WSL이 아니라 Ubuntu 22.04를 설치하여 빌드 가능함을 확인하였다.
3. Gazebo 설치
Gazebo는 시뮬레이션 환경이다. 개발한 로봇 관련 알고리즘을 하드웨어에 적용시키기 이전에 소프트웨어적인 시뮬레이션을 통해 정상적으로 동작하는지 검증하기 위해 사용한다. 실제와 같이 중력, 기압, 고도, 풍속 등의 요소 등을 적용하여 시뮬레이션 할 수 있다. Gazebo이외에 MS에서 만든 Airsim이나 JMavSim도 있지만 상대적으로 레퍼런스가 많아 개발에 조금 더 용이한 Gazebo를 설치한다. 참고로 아래는 오픈소스 시뮬레이터 비교 표다.
3.1 gazebo 설치
sudo apt-get -y install gazebo
(만약 gazebo 설치가 정상적으로 이뤄지지 않은 것 같다면 아래 명령 수행 - 차이점 파악 필요...)
sudo apt install ros-humble-gazebo-ros
위 명령을 통해 gazebo를 설치하고 난 뒤 다음과 같이 명령어를 수행하면 아래와 같이 Gazebo 시뮬레이터가 실행된다.
gazebo --verbose
만약 Failed to execute child process "dbus-launch" 에러가 발생하면 dbux-x11 패키지를 설치해줄 것
sudo apt install dbux-x11
4. ROS2 시각화 툴 설치 확인
ROS2에서 이뤄지는 통신 과정이나 시뮬레이션 상황을 시각화해서 보아야 할 때가 있다. rviz2가 시각화 도구다. ROS2 패키지 설치시 함께 설치된다. 아래와 같이 터미널에 rviz2를 실행하면 시각화 프로그램이 실행됨을 확인할 수 있다.
최근 많은 Redis 서버가 해킹당해 악성 봇넷으로 사용되고 있다고 한다. 그 이유는 Redis 서버에 인증없이 접속할 수 있다면 Redis 내부 명령어를 통해 악성코드를 실행할 수 있기 때문이다. 최근 Node JS로 개발 중인 서비스에서 캐시 DB로 Redis를 설치해 사용했다. 로컬에서 사용하니 실제로 서버 운영할 때 보안설정 하면되겠거니와 하며 인증없이 접속할 수 있도록 했었다. 하지만 로컬에 설치했던 Redis는 기본적으로 모든 네트워크와 연결 수립을 허용하는 것을 인지하지 못한 오판이었다. Redis는 기본 포트로 6379를 사용한다. 해커들은 6379 포트가 열린 IP를 브루트포싱하며 악성코드 실행을 위해 지속적으로 Redis 서버를 스캐닝 중에 있다. 다음과 같이 말이다.
redis-cli.exe를 통해 'monitor' 옵션을 설정해주면 내 Redis 서버를 스캐닝하는 외부 IP와 PORT를 확인할 수 있다. 또 만약 외부 IP에서 내 redis 서버에 임의의 key와 value를 설정하면 위 모니터링에 의해 값 설정 로그가 출력된다. 해커는 Redis 서버에 저장된 key-value를 탈취할 수 있지만, 휘발성격의 중요성이 떨어지는 데이터를 담는 Redis에선 key-value 탈취로 인한 피해보다 value에 악성페이로드를 담아 실행했을 때의 피해가 더 클 수 있다.
위 info 로그는 "redis-cli -h <IP> -p 6379 info" 명령을 수행하면 발생하는 로그다. 실제로 실행해보면 아래와 같이 서버, 클라이언트, 메모리, CPU 등의 각종 정보를 조회할 수 있다. 세부적으로 운영체제 정보나 설정파일 경로를 획득할 수 있으니 해커 입장에서 이후에 페이로드 구성에 활용할 수 있다.
위 각종 정보를 살펴보던 도중 Clients 영역에서 connected_clients가 3인 것을 볼 수 있었다. 로컬에서 사용했는데 연결된 클라이언트가 존재할 수 있는지 궁금해졌다. client list라는 명령어가 있었고 이를 통해 살펴보니 모르는 외부 IP와 연결되어 있었다. (나머지 2개는 실행했었던 redis-cli monitor와 redis-cli client였다.)
IP 주소를 조회해보니 어디 상하이가 찍혀 나왔다. 사이트에 들어가보니 e-commerce 관련 회사 홈페이지였고 C&C 서버로 쓰이고 있는 것 같다.
연결을 끊어줘야겠단 생각이 들었고 찾아보니 clinet kill 명령이 존재했다. 이를 통해 아래와 같이 중국 IP와의 연결을 끊어주었다.
이렇게 Redis 서버 보안에 주의를 돌리게 된 이유는 크게 두 가지다. 첫 번째는 지난밤 PC에서 비프음 보다 더 강렬한 소리가 났다. 이게 무슨 소리지?라고 어떻게 하면 이런 소리가 나지?라고 생각했다. 간단하게 윈도우 디펜더를 돌린 결과 아무 이상 없어 넘어갔다. 하지만 두 번째로 오늘 인증없이 접속 가능한 Redis 서버가 많고 많은 서버가 봇넷으로 사용되고 있음을 알게 됐다. 혹여 지난밤 소리와도 관련있지 않을까하여 Redis에 설정된 key 값과 운영체제에서 남기는 여러 로그를 분석해보았지만 다행히도 의심되는 흔적은 발견되지 않았다. 털리진 않았지만 이후 보안 설정도 개발과 병행해야겠단 생각으로 이어지게 됐다.
따라서 보안 설정 방법을 알아보던 중 KISA가 발간한 클라우드 취약점 점검 가이드에 Redis 시스템 취약점 점검 가이드가 있었고, 가이드에서 말하는 4가지 보안 설정을 해주었다. 첫 번째는 Redis 인증 패스워드 설정이다. Redis config 파일을 살펴보면 SECURITY 영역에 'requirepass'가 있다. 기본값은 주석처리되어 있지만 주석을 해제하고 우측에 인증 패스워드 값을 설정해준다.
두 번째는 binding 설정이다. 기본적으로 Redis 서버는 모든 네트워크와 연결 될 수 있다. 만약에 bind가 주석처리 되어 있다면 말이다. bind의 기본 값이 주석처리 되어 있지만 이를 해제하고 로컬(특정 IP)에서만 접속할 수 있도록 한다.
세 번째는 Slave 읽기 전용 모드 설정이다. redis는 master-slave 구조를 갖는다. master에 붙는 slave는 read-only 권한만을 가져서 master의 자원에 write할 수 없어야 한다. 하지만 이는 이미 아래와 같이 기본 설정으로 되어 있을 것이다. 그대로 두면 된다.
네 번째는 rename-command 설정이다. Redis에서는 보안 설정을 목적으로 rename-command를 제공한다. 이는 명령어를 다른 이름으로 치환하는 역할을 한다. 가령 예를 들어 CONFIG 명령을 사용하기 위해서는 b840fc로 시작하는 해시와 같은 예측할 수 없는 값으로 설정할 수 있다. 또는 CONFIG ""을 통해 아예 CONFIG 명령을 사용할 수 없도록 만들 수 있다.
보안 설정 미흡으로 시스템이 털리는 것은 사소한 판단에서도 기인할 수 있음을 느끼게 됐다. 앞으론 서버 보안 설정에 주의를 더 기울일 수 있도록 해야겠다. 다음에 Redis 서버 설치한다면 위 4가지 설정을 제일 먼저 하는 걸로. (그나저나 최근 이따금씩 PC나 다른 장치에서 들리는 비프음 같은 것은 뭘까 싶다.)
(PS: requirepass 주석해제 및 값 설정으로 패스워드 설정이 안된다면 redis-cli에서 "config set requirepass <password>" 명령어로 설정할 수 있음)
SELECT FACTORY_ID, FACTORY_NAME, ADDRESS
FROM FOOD_FACTORY
WHERE ADDRESS like "%강원도%"
ORDER BY FACTORY_ID ASC
Lv1. 동물의 아이디와 이름
SELECT ANIMAL_ID, NAME
FROM ANIMAL_INS
ORDER BY ANIMAL_ID ASC
Lv1. 모든 레코드 조회하기
SELECT *
FROM ANIMAL_INS
ORDER BY ANIMAL_ID ASC
Lv1. 상위 n개 레코드
SELECT NAME from ANIMAL_INS order by DATETIME asc limit 5
Lv1. 아픈 동물 찾기
SELECT ANIMAL_ID, NAME
FROM ANIMAL_INS
WHERE INTAKE_CONDITION = 'Sick'
ORDER BY ANIMAL_ID ASC
Lv1. 어린 동물 찾기
SELECT ANIMAL_ID, NAME
FROM ANIMAL_INS
WHERE INTAKE_CONDITION != 'Aged'
ORDER BY ANIMAL_ID ASC
Lv1. 여러 기준으로 정렬하기
SELECT ANIMAL_ID, NAME, DATETIME
FROM ANIMAL_INS
ORDER BY NAME ASC, DATETIME DESC
Lv1. 역순 정렬하기
SELECT NAME, DATETIME
FROM ANIMAL_INS
ORDER BY ANIMAL_ID DESC
Lv1. 조건에 맞는 회원수 구하기
SELECT COUNT(*)
FROM USER_INFO
WHERE DATE_FORMAT(JOINED, '%Y') = '2021'
AND (AGE >=20 and AGE<=29)
Lv2. 3월에 태어난 여성 회원 목록 출력하기
# SELECT MEMBER_ID, MEMBER_NAME, GENDER, DATE_FORMAT(DATE_OF_BIRTH, "%Y-%m-%d") as DATE_OF_BIRTH
# FROM MEMBER_PROFILE
# WHERE TLNO is not NULL and DATE_FORMAT(DATE_OF_BIRTH, '%m') = '03' and GENDER='W'
# ORDER BY MEMBER_ID ASC
SELECT MEMBER_ID, MEMBER_NAME, GENDER, DATE_FORMAT(DATE_OF_BIRTH, "%Y-%m-%d") as DATE_OF_BIRTH
FROM MEMBER_PROFILE
WHERE MONTH(DATE_OF_BIRTH) = 3
AND TLNO IS NOT NULL
AND GENDER = 'W'
ORDER BY MEMBER_ID ASC
Lv2. 재구매가 일어난 상품과 회원 리스트 구하기
SELECT USER_ID, PRODUCT_ID
FROM ONLINE_SALE
GROUP BY USER_ID, PRODUCT_ID
HAVING COUNT(*) >= 2
ORDER BY USER_ID ASC, PRODUCT_ID DESC
Lv4. 년, 월, 성별 별 상품 구매 회원 수 구하기
-- MySQL
SELECT YEAR(S.SALES_DATE) as YEAR, MONTH(S.SALES_DATE) as MONTH, I.GENDER as GENDER, count(DISTINCT(S.USER_ID)) as USERS
FROM USER_INFO as I RIGHT JOIN ONLINE_SALE as S ON (I.USER_ID = S.USER_ID)
WHERE I.GENDER IS NOT NULL
GROUP BY YEAR, MONTH, GENDER
ORDER BY YEAR, MONTH, GENDER ASC
Lv4. 서울에 위치한 식당 목록 출력하기
-- MySQL
SELECT I.REST_ID, I.REST_NAME, I.FOOD_TYPE, I.FAVORITES, I.ADDRESS, ROUND(AVG(R.REVIEW_SCORE), 2) as SCORE
FROM REST_INFO as I JOIN REST_REVIEW as R ON (I.REST_ID = R.REST_ID)
GROUP BY I.REST_ID
HAVING I.ADDRESS LIKE '서울%'
ORDER BY SCORE DESC, I.FAVORITES DESC
Lv4. 오프라인,온라인 판매 데이터 통합하기
SELECT *
FROM (
SELECT TO_CHAR(SALES_DATE, 'YYYY-MM-DD') as SALES_DATE, PRODUCT_ID, USER_ID, SALES_AMOUNT
FROM ONLINE_SALE
WHERE TO_CHAR(SALES_DATE, 'YYYY-MM') = '2022-03'
UNION ALL
SELECT TO_CHAR(SALES_DATE, 'YYYY-MM-dd') as SALES_DATE, PRODUCT_ID, NULL AS USER_ID, SALES_AMOUNT
FROM OFFLINE_SALE
WHERE TO_CHAR(SALES_DATE, 'YYYY-MM') = '2022-03'
)
ORDER BY SALES_DATE ASC, PRODUCT_ID ASC, USER_ID ASC
2. SUM, MAX, MIN
Lv1. 가장 비싼 상품 구하기
SELECT MAX(PRICE) as MAX_PRICE
FROM PRODUCT
Lv1. 최댓값 구하기
SELECT max(DATETIME)
FROM ANIMAL_INS
Lv2. 가격이 제일 비싼 식품의 정보 출력하기
-- 서브쿼리 이용해서 풀 것. 참고로 = 아닌 IN도 가능
SELECT PRODUCT_ID, PRODUCT_NAME, PRODUCT_CD, CATEGORY, PRICE
FROM FOOD_PRODUCT
WHERE PRICE = (SELECT MAX(PRICE) FROM FOOD_PRODUCT)
Lv2. 동물 수 구하기
SELECT count(ANIMAL_ID)
FROM ANIMAL_INS
Lv2. 중복 제거하기
SELECT count(unique(NAME))
FROM ANIMAL_INS
WHERE NAME is not NULL
Lv2. 최솟값 구하기
SELECT MIN(DATETIME)
FROM ANIMAL_INS
3. GROUP BY
Lv2. 가격대 별 상품 개수 구하기
SELECT TRUNC(price / 10000)*10000 as PRICE_GROUP, count(TRUNC(price / 10000)) as PRODUCTS
FROM PRODUCT
GROUP BY TRUNC(price / 10000)
ORDER BY TRUNC(price / 10000) ASC
Lv2. 고양이와 개는 몇 마리 있을까
SELECT ANIMAL_TYPE, count(ANIMAL_TYPE)
FROM ANIMAL_INS
GROUP BY ANIMAL_TYPE
order by ANIMAL_TYPE ASC
Lv2. 동명 동물 수 찾기
SELECT NAME, count(NAME) as COUNT
FROM ANIMAL_INS
WHERE NAME IS NOT NULL
GROUP BY NAME
HAVING count(*) >=2
ORDER BY NAME ASC
Lv2. 입양 시각 구하기(1)
-- SELECT TO_CHAR(DATETIME, 'HH24') as HOUR, count(TO_CHAR(DATETIME, 'HH24')) as COUNT
-- FROM ANIMAL_OUTS
-- WHERE TO_CHAR(DATETIME, 'HH24') BETWEEN '09' and '19'
-- GROUP BY TO_CHAR(DATETIME, 'HH24')
-- ORDER BY HOUR ASC
SELECT TO_CHAR(DATETIME, 'HH24') HOUR, COUNT(TO_CHAR(DATETIME, 'HH24')) COUNT
FROM ANIMAL_OUTS
GROUP BY TO_CHAR(DATETIME, 'HH24')
HAVING TO_CHAR(DATETIME, 'HH24') >= 9 and TO_CHAR(DATETIME, 'HH24') <= 19
ORDER BY TO_CHAR(DATETIME, 'HH24') ASC
Lv3. 즐겨찾기가 가장 많은 식당 정보 출력하기
SELECT FOOD_TYPE, REST_ID, REST_NAME, FAVORITES
FROM REST_INFO
WHERE (FOOD_TYPE, FAVORITES) in (SELECT FOOD_TYPE, MAX(FAVORITES)
FROM REST_INFO
GROUP BY FOOD_TYPE)
ORDER BY FOOD_TYPE DESC
Lv4. 입양 시각 구하기(2)
-- MySQL
SET @HOUR:= -1;
SELECT (@HOUR:= @HOUR+1) as HOUR, (SELECT COUNT(*) FROM ANIMAL_OUTS WHERE HOUR(DATETIME) = @HOUR) as COUNT
FROM ANIMAL_OUTS
WHERE @HOUR < 23
-- Oracle
SELECT HOUR, COUNT(B.DATETIME) COUNT FROM (SELECT LEVEL-1 HOUR
FROM DUAL
CONNECT BY LEVEL<=24)
A LEFT JOIN ANIMAL_OUTS B ON A.HOUR = TO_CHAR(B.DATETIME, 'HH24')
GROUP BY HOUR
ORDER BY HOUR ASC
4. IS NULL
Lv1. 경기도에 위치한 식품창고 목록 출력하기
-- SELECT WAREHOUSE_ID, WAREHOUSE_NAME, ADDRESS, NVL(FREEZER_YN, 'N') as FREEZER_YN
-- FROM FOOD_WAREHOUSE
-- WHERE ADDRESS like '경기도%'
-- ORDER BY WAREHOUSE_ID ASC
-- SELECT WAREHOUSE_ID, WAREHOUSE_NAME, ADDRESS, CASE WHEN FREEZER_YN IS NULL THEN 'N' ELSE FREEZER_YN END
-- FROM FOOD_WAREHOUSE
-- WHERE ADDRESS like '경기도%'
-- ORDER BY WAREHOUSE_ID ASC
SELECT WAREHOUSE_ID, WAREHOUSE_NAME, ADDRESS, DECODE(FREEZER_YN, null, 'N', FREEZER_YN) as FREEZER_YN
FROM FOOD_WAREHOUSE
WHERE ADDRESS like '경기도%'
ORDER BY WAREHOUSE_ID ASC
Lv1. 나이 정보가 없는 회원 수 구하기
SELECT count(USER_ID) as USERS
FROM USER_INFO
WHERE AGE IS NULL
Lv1. 이름이 없는 동물의 아이디
SELECT ANIMAL_ID
FROM ANIMAL_INS
WHERE NAME IS NULL
ORDER BY ANIMAL_ID ASC
Lv1. 이름이 있는 동물의 아이디
SELECT ANIMAL_ID
FROM ANIMAL_INS
WHERE NAME IS NOT NULL
ORDER BY ANIMAL_ID ASC
Lv2. NULL 처리하기
-- SELECT ANIMAL_TYPE, NVL(NAME, 'No name') as NAME, SEX_UPON_INTAKE
-- FROM ANIMAL_INS
-- ORDER BY ANIMAL_ID ASC
-- SELECT ANIMAL_TYPE, DECODE(NAME, null, 'No name', NAME) as NAME, SEX_UPON_INTAKE
-- FROM ANIMAL_INS
-- ORDER BY ANIMAL_ID ASC
SELECT ANIMAL_TYPE, CASE WHEN NAME IS NULL THEN 'No name' ELSE NAME END as NAME, SEX_UPON_INTAKE
FROM ANIMAL_INS
ORDER BY ANIMAL_ID ASC
5. JOIN
Lv2. 상품 별 오프라인 매출 구하기
SELECT PRODUCT_CODE, (PRICE * sum(S.SALES_AMOUNT)) AS SALES
FROM PRODUCT as P RIGHT JOIN OFFLINE_SALE as S ON P.PRODUCT_ID = S.PRODUCT_ID
GROUP BY S.PRODUCT_ID
ORDER BY SALES DESC, PRODUCT_CODE ASC
Lv3. 보호소에서 중성화한 동물
-- MYSQL
SELECT I.ANIMAL_ID, I.ANIMAL_TYPE, I.NAME
FROM ANIMAL_INS AS I INNER JOIN ANIMAL_OUTS AS O on I.ANIMAL_ID = O.ANIMAL_ID
WHERE I.SEX_UPON_INTAKE like '%Intact%' and O.SEX_UPON_OUTCOME not like '%Intact%'
Lv3. 없어진 기록 찾기
-- Oracle
SELECT O.ANIMAL_ID, O.NAME
FROM ANIMAL_OUTS O
WHERE O.ANIMAL_ID NOT IN (SELECT ANIMAL_ID FROM ANIMAL_INS)
ORDER BY O.ANIMAL_ID, O.NAME ASC
-- Oracle 2
SELECT O.ANIMAL_ID, O.NAME
FROM ANIMAL_OUTS O
WHERE NOT EXISTS (SELECT * FROM ANIMAL_INS I WHERE O.ANIMAL_ID = I.ANIMAL_ID)
ORDER BY ANIMAL_ID
-- MySQL 1
SELECT O.ANIMAL_ID, O.NAME
FROM ANIMAL_OUTS AS O LEFT JOIN ANIMAL_INS AS I ON O.ANIMAL_ID = I.ANIMAL_ID
WHERE I.ANIMAL_ID IS NULL;
Lv3. 오랜 기간 보호한 동물(1)
-- MySQL
SELECT NAME, DATETIME
FROM ANIMAL_INS
WHERE ANIMAL_ID NOT IN (SELECT ANIMAL_ID FROM ANIMAL_OUTS)
ORDER BY DATETIME ASC
LIMIT 0, 3
-- ORACLE
SELECT A.NAME, A.DATETIME
FROM (
SELECT I.NAME, I.DATETIME
FROM ANIMAL_INS I LEFT OUTER JOIN ANIMAL_OUTS O ON (I.ANIMAL_ID = O.ANIMAL_ID)
WHERE O.ANIMAL_ID IS NULL
ORDER BY I.DATETIME ASC
) A
WHERE ROWNUM <= 3
Lv3. 있었는데요 없었습니다
-- ORACLE
SELECT I.ANIMAL_ID, I.NAME
FROM ANIMAL_INS I LEFT JOIN ANIMAL_OUTS O ON I.ANIMAL_ID = O.ANIMAL_ID
WHERE I.DATETIME > O.DATETIME
GROUP BY I.ANIMAL_ID, I.NAME, I.DATETIME
ORDER BY I.DATETIME ASC
Lv4. 5월 식품들의 총매출 조회하기
SELECT P.PRODUCT_ID, P.PRODUCT_NAME, P.PRICE * sum(O.AMOUNT) as TOTAL_SALES
FROM FOOD_PRODUCT as P RIGHT JOIN FOOD_ORDER as O ON (P.PRODUCT_ID = O.PRODUCT_ID)
WHERE YEAR(PRODUCE_DATE) = 2022 and MONTH(PRODUCE_DATE) = 05 and P.PRODUCT_ID IS NOT NULL
GROUP BY P.PRODUCT_ID
ORDER BY TOTAL_SALES DESC, PRODUCT_ID ASC
Lv4. 그룹별 조건에 맞는 식당 목록출력하기
-- ORACLE
SELECT P.MEMBER_NAME AS MEMBER_NAME, R.REVIEW_TEXT AS REVIEW_TEXT, TO_CHAR(R.REVIEW_DATE, 'YYYY-MM-DD') AS REVIEW_DATE
FROM MEMBER_PROFILE P INNER JOIN REST_REVIEW R ON P.MEMBER_ID = R.MEMBER_ID
WHERE R.MEMBER_ID IN (SELECT MEMBER_ID -- 리뷰 쓴 개수가 COUNT(*)인 경우에 대해 GROUP BY후 사람들 ID 출력
FROM REST_REVIEW
GROUP BY MEMBER_ID -- 사람들이 리뷰 쓴 개수가 COUNT(*)인 경우에 대해 GROUP BY.
HAVING COUNT(*) = (SELECT MAX(COUNT(*)) -- 최대 리뷰 쓴 사람들의 개수를 구함
FROM REST_REVIEW
GROUP BY MEMBER_ID)
)
ORDER BY R.REVIEW_DATE
Lv5. 상품을 구매한 회원 비율 구하기
-- MySQL
SELECT YEAR(SALES_DATE) as YEAR, MONTH(SALES_DATE) as MONTH, count(DISTINCT(I.USER_ID)) as PUCHASED_USERS, ROUND(count(DISTINCT(I.USER_ID)) / (SELECT count(DISTINCT(USER_ID)) FROM USER_INFO WHERE YEAR(JOINED) = 2021),1) as PUCHASED_RATIO
FROM USER_INFO AS I RIGHT JOIN ONLINE_SALE as S ON (I.USER_ID = S.USER_ID)
WHERE I.USER_ID in (SELECT USER_ID FROM USER_INFO WHERE YEAR(JOINED) = 2021)
GROUP BY YEAR(SALES_DATE), MONTH(SALES_DATE)
ORDER BY YEAR, MONTH ASC
6. String, Date
Lv2. 오랜 기간 보호한 동물(2)
SELECT A.ANIMAL_ID, A.NAME
FROM ANIMAL_INS A, ANIMAL_OUTS B
WHERE A.ANIMAL_ID = B.ANIMAL_ID
ORDER BY DATEDIFF(A.DATETIME, B.DATETIME) limit 0, 2
Lv2. 이름에 el이 없는 동물 찾기
-- MySQL 1
SELECT ANIMAL_ID, NAME
FROM ANIMAL_INS
WHERE ANIMAL_TYPE = 'Dog' and (NAME like '%el%' or NAME like '%EL')
ORDER BY NAME ASC
-- MySQL 2
SELECT ANIMAL_ID, NAME
FROM ANIMAL_INS
WHERE ANIMAL_TYPE = 'Dog' AND UPPER(NAME) LIKE '%EL%'
ORDER BY UPPER(NAME) ASC
Lv2. 중성화 여부 파악하기
SELECT ANIMAL_ID, NAME, CASE WHEN SEX_UPON_INTAKE like '%Neutered%' or SEX_UPON_INTAKE like '%Spayed%' THEN 'O' ELSE 'X' END as 중성화
FROM ANIMAL_INS
ORDER BY ANIMAL_ID
Lv2. 카테고리 별 상품 개수 구하기
SELECT SUBSTRING(PRODUCT_CODE, 1, 2) as CATEGORY, count(SUBSTRING(PRODUCT_CODE, 1, 2)) as PRODUCTS
FROM PRODUCT
GROUP BY SUBSTRING(PRODUCT_CODE, 1, 2)
Lv2. DATETIME에서 DATE로 형 변환
-- ORACLE
SELECT ANIMAL_ID, NAME, TO_CHAR(DATETIME, 'YYYY-MM-DD') as 날짜
FROM ANIMAL_INS
ORDER BY ANIMAL_ID ASC
-- MYSQL
SELECT ANIMAL_ID, NAME, DATE_FORMAT(DATETIME, '%Y-%m-%d') AS 날짜
FROM ANIMAL_INS
ORDER BY ANIMAL_ID ASC
Lv3. 조건별로 분류하여 주문상태 출력하기
SELECT ORDER_ID, PRODUCT_ID, DATE_FORMAT(OUT_DATE, '%Y-%m-%d'),
IF (OUT_DATE <= '2022-05-01', '출고완료', IF(OUT_DATE IS NULL, '출고미정', '출고대기')) as 출고여부
FROM FOOD_ORDER
ORDER BY ORDER_ID ASC
신장 트리란 그래프 상에서 모든 노드가 사이클 없이 연결된 부분 그래프를 뜻한다. 이 부분 그래프는 여러개가 존재할 수 있다. 따라서 최소 신장 트리란 여러 개의 부분 그래프 중 모든 정점이 최소 간선의 합으로 연결된 부분 그래프이다.
(* 트리와 그래프 관계: 트리는 그래프 중에서 특수한 경우에 해당하는 자료구조로,사이클이 존재하지 않는 방향 그래프다)
최소 신장 트리의 활용
이런 최소 신장 트리는 실생활 곳곳에 활용된다. 예를 들어 도로 건설 문제에서 도시를 노드, 도로를 간선으로 두고 도시 간 이어지는 도로 길이를 최소화 할 때 사용된다. 또 네트워크에서 최적의 라우팅 경로를 선택할 때도 사용되며, 통신에서도 전화선 길이가 최소가 되는 케이블망 구축에 사용되는 등 여러 곳에서 활용된다.
최소 신장 트리 알고리즘
최소 신장 트리를 찾을 수 있는 알고리즘은 크게 2가지로 크루스칼(Kruscal), 프림(Prim) 알고리즘이 있다. 두 알고리즘 간 차이점은 크루스칼은 간선 중심이고 프림은 정점 중심 알고리즘이다. 간선이 적으면 크루스칼을, 간선이 많으면 프림을 사용하는 것이 좋다. 알고리즘 시간 복잡도는 크루스칼이 $O(E+\log (E))$, 프림이 $O(V+E) \log (V)$이다. 두 알고리즘의 공통점 중 하나는 음수 사이클이 있더라도 최소 신장 트리를 구할 수 있다. 본 포스팅에서는 크루스칼 알고리즘만 다룬다.
크루스칼 알고리즘 (Kruscal Algorithm)
크루스칼 알고리즘은 음의 가중치가 없는 무방향 그래프에서 최소 신장 트리를 찾는 알고리즘이다. 최소 신장 트리를 찾기 위해선 사이클 발생 여부를 판단할 수 있어야 한다. 사이클 발생 여부는 union find 알고리즘을 사용해서 판단한다. union find를 알면 크루스칼 알고리즘 이해에 도움되지만 모르더라도 아래 설명을 통해 어느정도 이해 가능할 것이다.
크루스칼 알고리즘은 크게 아래 3단계로 구성되며 2~3이 반복 수행된다.
1. 주어진 모든 간선을 오름차순 정렬 수행한다.
2. 정렬된 간선을 하나씩 확인하며 현재 간선이 노드 간 사이클을 발생시키는지 확인한다.
3. 사이클 발생시키지 않을 경우 최소신장트리에 포함, 사이클 발생할 경우 포함하지 않는다.
도식화 한 예시로 확인해보자. 예를 위해 아래와 같이 노드 6개와 간선 8개로 구성된 그래프가 있다 가정하자.
위 그림에서 간선의 비용 별로 오름차순 정렬해 주었다. 또 내부적으로 사이클 여부를 판별하기 위해 union-find 알고리즘을 사용하므로 부모 테이블을 만들어주고 초기값은 노드 자기자신으로 둔다. 이제 간선을 비용이 작은 순서대로 확인하기 위해 먼저 간선 (3,6)을 살펴보자.
노드 3, 6의 부모 노드를 살펴보면 각각 3, 6으로 다르기에 사이클이 발생하지 않는다. 따라서 최소 신장 트리에 (3, 6)을 포함시키고 부모 테이블에서 노드 6의 부모를 노드 3으로 업데이트 해준다. 참고로 일반적으로 부모 노드는 작은 노드 번호 기준으로 업데이트한다. 다음으로 노드 2, 3을 살펴보자
노드 2, 3의 부모 노드를 살펴보면 각각 2, 3으로 다르기에 사이클이 발생하지 않는다. 따라서 최소 신장 트리에 (2, 3)을 포함시키고 부모 테이블에서 노드 3의 부모를 노드 2로 업데이트 해준다. 이 때 노드 6도 부모 노드를 3으로 가지는 종속 관계에 있으므로 함께 바꿔준다. 다음으로 노드 1, 3을 살펴보자
노드 1, 3의 부모 노드를 살펴보면 각각 1, 2로 다르기에 사이클이 발생하지 않는다. 따라서 최소 신장 트리에 (1, 3)을 포함시키고 부모 테이블에서 노드 3의 부모를 노드 1로 업데이트 해준다. 이 때 노드 2, 6도 부모 노드를 2로 가지는 종속 관계에 있으므로 함께 바꿔준다. 다음으로 노드 2, 4를 살펴보자
노드 2, 4의 부모 노드를 살펴보면 각각 1, 4로 다르기에 사이클이 발생하지 않는다. 따라서 최소 신장 트리에 (2, 4)를 포함시키고 부모 테이블에서 노드 4의 부모를 노드 1로 업데이트 해준다. 다음으로 노드 1, 2를 살펴보자
노드 1, 2의 부모 노드를 살펴보면 각각 1, 1로 같아 사이클이 발생했다. 그러므로 최소 신장 트리에 포함시키지 않고, 부모 테이블 업데이트도 이뤄지지 않는다. 다음으로 노드 2, 5를 살펴보자
노드 2, 5의 부모 노드를 살펴보면 각각 1, 5로 다르기에 사이클이 발생하지 않는다. 따라서 최소 신장 트리에 (2, 5)를 포함시키고 부모 테이블에서 노드 5의 부모를 노드 1로 업데이트 해준다. 다음으로 노드 4, 5를 살펴보자
노드 4, 5의 부모 노드를 살펴보면 각각 1, 1로 같아 사이클이 발생했다. 그러므로 최소 신장 트리에 포함시키지 않고, 부모 테이블 업데이트도 이뤄지지 않는다. 다음으로 노드 5, 6를 살펴보자
노드 5, 6의 부모 노드를 살펴보면 각각 1, 1로 같아 사이클이 발생했다. 그러므로 최소 신장 트리에 포함시키지 않고, 부모 테이블 업데이트도 이뤄지지 않는다. 이것으로 최소 신장 트리를 찾는 크루스칼 알고리즘 동작이 종료된다. 동작 전과 동작 후를 비교해보자면 다음과 같다.
기존의 그래프 전체에서 사이클 없이 모든 정점을 최소 비용 간선으로 잇는 부분 그래프인 최소 신장 트리다. 이를 코드로 구현하면 다음과 같다.
""" This is input value. you can just copy and past it.
then you can get "[(3, 6), (2, 3), (1, 3), (2, 4), (2, 5)]" and "23"
6 8
1 2 7
1 3 5
2 3 2
2 4 6
2 5 9
3 6 1
4 5 11
5 6 12
"""
import sys
input = sys.stdin.readline
def find_parent(parent, x):
""" 부모 노드를 찾기 위해 재귀 수행"""
if parent[x] != x:
parent[x] = find_parent(parent, parent[x])
return parent[x]
def union_parent(parent, a, b):
""" 부모 노드 비교 후 부모 노드 업데이트 """
a = find_parent(parent, a)
b = find_parent(parent, b)
if a < b:
parent[b] = a
else:
parent[a] = b
if __name__ == "__main__":
V, E = map(int, input().split()) # make graph
graph = []
for _ in range(E):
a, b, cost = map(int, input().split())
graph.append([a, b, cost])
graph.sort(key=lambda x:x[2])
parent = [0] * (V+1) # make parent table
for i in range(1, V+1):
parent[i] = i
costs, mst = 0, [] # get mst
for i in range(E):
a, b, cost = graph[i]
if find_parent(parent, a) != find_parent(parent, b): # check cycle
union_parent(parent, a, b)
mst.append((a, b))
costs += cost
print (mst)
print (costs)
정보보안학 석사 과정을 졸업한지 1년 쯤 되어가고, 관심분야도 보안에서 딥러닝으로 바뀐지 꽤 오래 되었네요. 불현듯 자기 전 작년 종합시험 준비로 고통받던 때가 떠올라 이 글을 쓰게 됐습니다. 재학 기간 동안 두 번의 시험 기회가 있었고 첫 번째 기회를 날리는 고배를 마신 뒤 절치부심하는 마음으로 정리한 내용입니다. 중간/기말/종합시험 모두에 어느 정도 도움이 되리라 생각합니다. 가급적 논리적 서술이 가능하도록 정의, 배경, 특징, 장점, 단점, 차이점, 방법, 활용, 종류, 목표 등을 고려해 작성하였습니다. 아래에 예상 질문들은 강의 내용을 총 정리하다보니 자연스럽게 시험에서 이런 것을 물어볼 것 같다고 예상한 질문과 답안들입니다. 중간에 예상 답안이 부재한 경우는 2가지 이유입니다. 첫 번째는 교수님께서 매학기 수업마다 조금씩 설명을 더 해주거나 덜 해주는 파트가 있어 듣지 못해 정리할 수 없었던 부분입니다. 두 번째는 얼추 설명은 해주셨지만 정확히 이해 못하고 모호하게 알고 있는 부분은 지웠습니다. 댓글로 추가해주신다면 업데이트 하도록 하겠습니다. 또 틀린 부분이 있다면 지적해주시면 감사하겠습니다. 참고로 아래 내용들은 강의 요약 내용을 바탕으로 작성한 것이므로 포함하지 않는 내용과 설명들이 있습니다. 원본이 필요할 경우 댓글 남겨주시면 보내 드리겠습니다. 전체 글 내용은 고려대학교 정보보호대학원 김승주 교수님 보안공학 강의 내용을 기반으로 작성되었습니다.
보안공학이란 무엇인가?
H/W와 S/W를 만드는 개발 단계인 요구사항 분석, 설계, 구현, 배포, 유지보수에 이르기 까지 각 단계마다 모두 보안을 고려하고 제품을 판매하는 단계에서도 보안내재화가 이루어졌는지 제대로 이루어졌는지 확인하는 것이다.
보안공학의 목표는 무엇이고 왜 보안공학은 어려운가?
보안공학은 trusthworthy(dependable)한 시스템을 만드는 것을 목표로 한다. 보안공학은 random한 에러를 다루는 소프트웨어공학과 달리 random한 에러와 함께 의도적으로 발생한 intentional 에러도 함께 다루기 때문에 더 어렵다.
define & design approach: 보호해야할 자산을 정확하게 식별한 다음, 자산의 중요도와 이에 따른 요구사항을 정의하고 설계하는 것을 의미한다.
shift-left testing: 매 개발 단계마다 testing을 수행 함을 의미한다. shift-left testing에서 보안 담당자의 역할은 개발자가 testing에 사용할 수 있는 도구를 만들어 공급하고, 개발자가 진행한 testing에 대해 적절성 여부를 검증하는 작업을 진행한다. 이러한 shift-left testing은 자동화가 가능하고, 이른 단계에서 testing을 진행할 수 있다는 장점이 있다.
traceability:
만약 보안공학에서 보안내재화 개발 프로세스를 통해 요구사항분석부터 설계, 구현까지 완벽히 수학적으로 다 증명돼도 모의해킹이 필요한가?
모든 것을 수학적으로 증명했다 하더라도 모의해킹이 필요하다. 수학적 증명은 전제조건을 가지고 있으며 이 전제조건이 제대로 지켜지고 있는지를 검증하기 위해서는 모의해킹이 반드시 필요하다. 이는 수학적 증명과 모의해킹이 상호보완 하는 관계라고 볼 수 있다.
바람직한 S/W 요구사항 도출 조건의 6가지와 그 특징은 무엇인가?
Unambiguity: 다른 사람이 요구사항을 검토한 결과는 동일해야 하며 요구사항에 모호함이 없어야 한다.
Prioritization: 요구사항의 구현과 관련하여 우선순위가 부여되어야 한다.
Verifiability: 요구사항이 제품에 적절하게 구현되어야 하고, 검증하기 위한 Security Testing Requirement도 함께 도출되어야 한다.
Completeness: 모든 필요한 요구사항이 전부 도출되어야 한다. (지정된 모든 요구사항은 전달해야 하는 기능을 완전히 설명해야 한다)
Correctness: 해당 요구사항은 자체 모순을 가지거나 충돌되지 않고 그 기능을 정확하게 설명해야 한다.
Feasibility: 해당 요구사항은 자원 및 제약조건에서 실행 가능해야 한다.
보안성 평가에서 TCSEC의 보안등급 중 A2는 왜 사용하지 않는가?
TCSEC을 처음 만들 당시 A2 등급인 Code Proof(Code Assurance)까지 넣으려고 하였다. 하지만 TCSEC을 제작자는 Code Assurance의 입증이 어렵다고 판단하여 마지막에 A2를 제거하고 A1만 남겼다. Code Assurance는 Software testing과 Software verification으로 구성되는데, 특히 software testing에서 만약 소스코드가 대략 10,000줄이 이상 넘어가게 된다면 포인터 등으로 인한 복잡성 때문에 수학적 안정성 입증이 어려워지기 때문이다.
TCSEC의 단점을 서술하시오
보안등급평가에 있어 Assurance와 Functionality가 서로 분리되어 있지 않아, High Assurance임에도 불구하고 낮은 보안등급으로 평가하는 결점이 있다.
보안성 평가 표준인 CC, CAVP, CMVP, C&A, RMF A&A, DITSCAP에 대해 설명하시오.
CC: (개념) 보안성 평가와 관련해서 가장 권위있는 국제 표준이다. 보안성 평가 국제표준(ISO/IEC 15408)의 공통평가기준(CC)에 따라 정보보호시스템의 기능 및 취약성을 평가/인증하는 제도이다. (배경) 미국의 TCSEC으로부터 유럽연합의 ITSEC, 캐나다의 CPCPEC, FC 등이 만들어지게 되었고 이를 만든 각국가의 평가기관들은 국가적으로 독립된 평가 기준을 통합하는 프로젝트를 시작하였고 이를 CC 프로젝트라 하였다. CC 프로젝트는 TCSEC의 단점을 보완하고 기존의 평가 기준들간의 개념적/기술적 차이를 통합하여 국제 표준화를 만들자는 목표로 추진되어 만들어 졌다. (목적) CC인증은 평가과정에서 IT제품(H/W, F/W, S/W)에 적용되는 보안 기능과 보증수단에 대한 공통의 요구 사항들을 제시한다. 이를 통해 독립적으로 수행된 보안성 평가의 결과들을 비교할 수 있도록 한다. 평가 결과는 소비자가 IT 제품이 그들의 보안 요구를 충족시키는지 결정하는데 도움을 줄 수 있다.
CAVP (Cryptographic Algorithm Validation Program): 암호 알고리즘을 중심으로 제대로 구현되었는지를 검증한다.
CMVP (Cryptographic Module Validation Program): 특정한 암호 모듈이 특정한 암호 알고리즘을 올바르게 구현했느냐에 대한 구현 적합성을 시험/인증 한다. CMVP와 CC의 공통점은 제품이 요구사항분석단계부터 설계, 구현에 이르기까지 보안내재화 프로세스를 충실히 따랐는가를 본다. 이것이 발전해서 C&A 제도가 되었다.
C&A (Certification & Accrediation):
RMF A&A: 2015년 DoD Cyber Strategy를 발표했고, 이 내용은 전산시스템 뿐만 아니라 F35 스텔스 전투기나 무인 드론과 같은 첨단 무기체계들도 보안내재화 개발 프로세스를 적용하라는 것을 요구한 것이다. RMF A&A는 이러한 요구사항을 충족시키고 실제로 준수하였는지 평가하기 위해 만들어진 표준이다.
(다소 설명이 빈약하다 생각들어 몇몇 부분은 추가되면 좋을 것 같습니다)
CAVP, CMVP, CC, DITSCAP, NIST C&A, RMF A&A의 정의 및 비교와 국내외 정책비교를 서술하라.
EAL 보안성평가에서 낮은등급에서 높은등급이 되기 위해 필요한 조건은?
Requirements, functional specification, HLD, LLD, implementation에 대해 formal method로 정형명세화 하여 수학적으로 만족함을 입증하여야 한다.
Information Security, Information Assurance or Cybersecurity의 차이를 서술하시오
핵심 차이는 trusthworthy라고 할 수 있다. information security는 컴퓨터와 컴퓨터에 들어있는 전자적 정보를 지키는 것을 의미하며, cybersecurity는 사이버공간과 연동된 모든것을 지키는 것을 의미하는데 여기에는 digital과 non-digital 정보도 함께 포함된다.
걸프전이 최초의 Information Assurance인 이유는 무엇인가?
이 질문에 대해 답을 정리하진 못했습니다. 다만 이 예상 질문과 관련한 부분적인 내용들을 기술하면 다음과 같습니다.
걸프전의 맥락에서 사용되어 정리하고 가야할 용어인 information security와 cybersecurity가 있다. 두 용어의 큰 차이점이자 추구하는 목표는 trustworthy이다.
Information Security: 컴퓨터와 컴퓨터 속에 들어 있는 전자적인 데이터를 보호하겠다라는 의미를 가진다.
Informaton Assurance or Cybersecurity: 사이버공간과 연동된 모든 것을 보호하겠다라는 의미를 가지며, 그 모든 것은 전자적인 형태(digital)의 데이터여도 되고 전자적인 형태(non-digital)가 아니여도 된다.
걸프전은 정보보증(Information Assurance)이라는 패러다임 shift를 발생시킨 선구자 역할을 했다는 점에서 의미가 있다.
걸프전에서는 패러다임 shift가 information security에서 information assurance로 바뀌었고, 이는 적의 정보는 교란시키고 내 정보를 유지시키는 것이 중요하다고 인식하게 되면서 이를 위한 목표인 trustworthy를 달성하기 위함이다.
걸프전을 통해 Information Assurance가 중요해졌다. 이는 원할때 Access 가능해야 하고, 그 정보는 항상 relability와 security를 유지 가능해야 함을 의미한다.
Risk Management란 무엇이고, 구성요소와 이에 대한 정의는 무엇인가?
Risk Management는 기본적으로 Risk를 제거하는 것이 아니라 줄이는 것이다. 하지만 Risk를 줄인다하더라도 잔존 위협(Residual Risk)가 남아있게 된다. 이 때 이 잔존 위협을 어떻게 잘 관리할지 고려하는 것을 Risk Management라고 한다. 참고로 이를 위해선 자산별, 중요도 별 등급화가 되있어야 Risk를 측정할 수 있다. Risk Management 방법은 크게 4가지로, Risk Transfer, Risk Avoidance, Risk Reduction, Risk Retention이 존재한다.
Risk Transfer: 위협을 보험사와 같은 제 3자에게 전가하는 것을 의미한다.
Risk Avoidance: 위협을 회피하는 것을 의미하는 것으로 단적 예로 스마트TV에 카메라 떼는 것과 같다.
Risk Reduction: 보안 대책을 만들어 위험을 감소시키는 것을 의미한다.
Risk Retention: 위험의 확률이 낮으면 위험을 안고 가는 것을 의미한다.
결과적으로 이를 통해 Risk Avoidance를 제외하고 어떤 것이 ROI가 높은지 비교하여 그에 맞는 대응책을 세운 뒤, 높은 리스크부터 낮은 리스크로 대응해야 한다.
Risk Assessment의 특징과 그 한계를 설명하시오.
Risk Assessment는 quantitative risk analysis (정성적), qualitative risk analysis (정량적)로 크게 둘로 나뉜다. 리스크 분석은 정량적으로 분석하는 것이 객관성을 담보할 수 있다는 장점이 있지만 적용하고자 하는 사람의 탄탄한 수학적 이론이 뒷받침 되어야 하므로 실적용엔 무리가 있다. 따라서 무기체계분석이나 자동차보안성평가와 같은 필드에서는 정성적 분석 방법을 사용하는 것이 특징이다. (Risk = Probability * Damage Potential)
Shannon's perfect secrecy : 무한한 컴퓨팅 자원을 가진 passive attacker로 부터 암호문에서 평문에 대한 어떠한 정보(단, 1bit라도)도 누출되서는 안된다.
Goldwasser's semantic security : 유한한 컴퓨팅 자원을 가진 passive attacker로부터 암호문에서 평문에 대한 어떠한 정보(단, 1bit라도)도 노출되서는 안된다.
MDTD(Model Driven Test Design)가 test case create에 도움이 되는 이유는?
testing하려는 대상을 작은 task 단위로 모델링하여 해당 task에 집중적으로 testing할 수 있기 때문이다.
Model Checking 이론을 바탕으로 Code Assurance를 달성하는 방법 및 프로세스를 상세히 서술하시오.
프로그램을 model로 만들고 model checker에 requirement(ex: correctness property)를 넣었을 때 model checker에서 model이 requirement를 충족하는지에 대한 여부를 Yes/No로 알려준다. 만약 No의 경우에는 counter measure도 함께 알려준다. 결과적으로 model checker를 통해 해당 프로그램의 model이 requirement를 충족하는지 판단한다. (Model Checker는 완전 자동화가 가능하다는 장점이 있고, Automatic Theorem Prover에 비해 적용 범위가 작다는 단점이 있다.)
데이터 거버넌스에 대해 설명하시오
데이터거버넌스의 핵심은 데이터 사일로(칸막이) 문제로 인해 도입된 개념으로 데이터 활용을 위한 전사적인 경영체계라 할 수 있다. 조직은 이러한 데이터 거버넌스를 통해 데이터 활용 계획과 데이터 보호 계획을 수립하여 활용도를 극대화 시켜서 궁극적으로 데이터 사일로를 제거하는 것을 목표로 한다.
14가지 Security Design Principle과 각각이 의미하는 바를 서술하시오.
Least Privilege: 사람 또는 시스템에게 부여할 최소한의 권한을 부여하는 것을 의미한다. 하지만 이 최소권한의법칙을 지키기 위해 보안레벨을 사용자와 오브젝트 사이에 어떻게 설정해야 하는가는 쉽지 않다.
Fail-Safe Default: 두 가지 의미를 가진다. 첫 째는 명시적 허용이 아니면 거부를 의미한다. 예를 들어 방화벽 룰셋에 명시되지 않은 패킷이 있을 경우 drop하는 것과 같다. 둘 째는 만약 프로그램이 비정상 상태로 빠질 경우, 바로 직전에 안전했던 상태로 돌아가는 것을 의미한다. 이를 통해 프로그램을 항상 안전한 상태로 유지시킬 수 있게 한다. 예를 들어 윈도우 블루스크린이 표시되어 먹통이 되는 상태로 빠지지 않게 하는 것과 같다.
Economy of Mechanism: H/W, S/W를 개발할 때 가능한한 시스템을 단순하고 작은 사이즈로 설계하고 구현해야 함을 의미한다. 단순하고 작은 사이즈로 설계하는 것은 모듈화 설계와 같다. 장점은 요구사항을 달성하고 있는지 검증이 쉬워진다. 심플할수록 assurance level이 높아진다. simple and small이 의미하는 바는 검증하기 쉽도록하여 assurance level을 극대화 시킨다는 것이 핵심이다.
Complete Mediation: 자원에 접근할 때 마다 반드시 그 권한에 대해 확인해야하는 것을 의미한다. 모든 접근을 전부 확인하는 것을 zero-trust라고 한다. 하지만 실질적으로 모든 접근에 대한 확인은 부하로 인한 속도저하가 심해서 구현하기 어려운 것이 특징이다.
Design by Contract: 어떤 일을 처리할 때 항상 확인된 인터페이스를 통해서만 해당 일을 처리해야함을 의미한다. 예를 들어 중요한 시스템일수록 사전 정의된 인터페이스 또는 사전 정의된 프로토콜을 통해서만 중요 자원에 접근할수 있도록 하는 것을 의미한다.
Open Design: 어떤 시스템을 만들었을 때 그 시스템의 설계도나 소스코드가 공개되어도 안전도가 유지될 수 있어야 한다는 것을 의미하고, 시스템의 안전성을 설계도나 소스코드의 폐쇄성에 의존하지 않아야 한다는 것을 의미한다. 예를 들어 군에서 같은 모듈을 사용하는 무전기를 분실하게 되면 리버싱하여 소스코드를 알아낼 수 있기 때문에 시스템을 만들때 설계도나 소스코드가 공개됐다고 전제한 다음 시스템을 만들라는 것이다. 그래서 만약 안전하다면 오픈 디자인 원칙에 충실하다 할 수 있다. 동의어는 Kerckhoff's 법칙이라고도 하며, 반대말로 Security through Obsecurity 또는 Security by Obsecurity라고도 한다.
Seperation of Prvilege: 중요시스템에 접근할 때는 그 권한을 분산 또는 분리해야 함을 의미한다. 예를 들어 핵무기를 동작시킬 때 두 사람의 암호를 동시에 입력해야 작동하는 것과 같다.
Least Common Mechanism: 시스템의 공통 모듈을 최소화해서 활용해야 함을 의미한다. 이는 보안에서 한 부분에 문제가 생겼을 때 다른 부분으로 파급되는 것을 최소화하는 것이 중요하기 때문이다. 하지만 현실적용에는 어려운 부분이 있는데 이는 공통모듈을 쓰면 생산성은 높아지나, Economy of mechanism의 개념과 정면으로 위배되는 특징이 있기 때문에 시스템을 만들다보면 이 개념에 충실하기 쉽지 않은 것이 특징이다.
Psychological Acceptability: Usable Security라고도 부르며 이는 시스템이 사용하기 편리해야 함을 의미한다.
Defense in Depth: 보안 시스템을 둘 때 계층을 두어 한 계층이 뚫히더라도 다음 계층이 막아줄 수 있도록 시스템을 설계해야 함을 의미한다.
Effective Logging: 로그를 잘 남겨야 함을 의미하는 것으로, 개인정보보호법으로 인해 로그에 어떤 정보가 들어가면 안되는지 또한 중요해진 것이 특징이다.
Build In, Not Bolt On: 시스템을 개발한 다음 보안제품을 사서 쓸 것이 아니라, 처음 만들 때 보안이 Build In되도록 만들어야 함을 의미한다.
Design for Updating: 업데이트를 어떻게 할 것인가를 설계해야 함을 의미한다.
Centralized vs Decentralized: 중앙화 시킬 것인지 분산화 시킬 것인지를 의미한다.
What is 'sound'?
Threat Modeling의 개념과 절차적 특징을 서술하시오.
Threat Modeling은 목표 시스템에 대한 어떤 위협요소가 없는지를 공격자의 입장에서 체계적으로 분석할 수 있는 방법론을 의미한다. 이를 통해 목표 시스템의 attack surface 식별, 얼마만큼의 위협이 발생하는 가를 측정할 수 있다. 또한 보안대책과 보안대책에 대한 테스트와 같은 일련의 청사진을 도출해낼 수 있다는 것이 특징이다. 전반적인 프로세스는 다음과 같다.
DFD를 통해 우선적으로 모델링한 후 지켜야할 자산을 중요도 별로 우선순위를 식별한다.
분석대상 시스템에 대해 취약점정보와 관련된 attack library를 수집한다.
공격자의 관점에서 STRIDE를 이용하여 어떤 element에 취약점이 매핑될 수 있는지를 확인한다.
매핑된 정보를 기반으로 공격시나리오를 생성 후 attack tree로 표현한다.
SRIDE: 모델링된 시스템에서 element 별로 공격자의 입장에서 취약점을 도출할 수 있는 보안위협모델링 방법이다. Spoofing(위장), Tampering(변조), Repudiation(부인), Information DIsclosure(정보유출), Denial of Service(서비스거부), Elevation of prvilege(권한상승)으로 구성되어 있다. SRIDE에는 분석 방법이 2가지로 stride-per-element와 stride-per-interaction이 있다. stride-per-element는 element 별로 S,T,R,I,D,E 공격이 발생할 수 있을지 검증하는 것을 의미하고 stride-per-interaction은 trust boundary를 넘나드는 데이터 흐름들에 대해 중점적으로 분석하는 방법을 의미한다.
Attack Tree: 수집한 취약점 정보를 엮어 공격시나리오화 시킬 수 있는 방법으로, 하나의 목표 별로 하나의 Attack Tree가 만들어지는 것이 특징이다.
DREAD: DREAD는 5가지 항목으로 구성되어 있고 각각은 다음과 같다.
Damage Potential: 공격자가 굉장히 민감한 데이터를 탈취하거나 파괴할 수 있음을 의미한다.
Reproducibility: Timing winodow가 크거나 작음을 의미하는 것으로, Timing window가 작은 예시로는 컴퓨터가 부팅될 때만 공격이 가능하고 Timing winodw가 큰 예시로는 컴퓨가 켜져 있으면 언제든 가능할 때를 의미한다.
Exploitability: 공격 프로그램으로 만들기가 얼마나 쉬운가를 의미한다.
Affected Users: 공격으로부터 영향을 받는 사용자가 얼마나 많은가를 의미한다.
Discoverability: 해당 취약점을 얼마나 발견하기 쉬운가를 의미한다.
Risk score = DREAD/5이다. 이러한 Risk score의 단점은 절대적이지 않고 사람마다 상대적인 것이다. 따라서 2010년 이후 MS에선 더이상 사용하지 않고, security response center bulletin ratings를 사용해 사람마다 오차가 생기는 것을 막고자 하였다.
LINDDUN을 설명하시오.
LINDDUN은 DFD를 작성한 뒤 개인정보보호의 관점으로 보안위협식별을 수행하는 방법이다. LINDDUN을 이루는 구성요소와 이에 대한 설명은 아래와 같다.
Linkability:
Identifiability:
Non-repudiation:
Detectability:
Disclosure of Information:
Unawareness:
Non-compliance:
TARA를 설명하시오.
Threat Assessment and Remediation Analysis로 2011년 MITRE에서 만들어진 것으로, 국가의 지원을 받는 해커들이 있다는 전제하에 위협모델링을 어떻게 할 수 있을까를 위해 만들어졌다. 일반적인 해커와 달리 국가의 지원을 받는 해커는 기존의 Threat Modeling을 할 수 없는데 이는 투입비용의 한계가 없기 때문이다.
Structured Threat Assessment Process란 무엇인가?
핵심은 모의해킹과 위협모델링(Threat modeling)을 합쳐서 수행하는 것을 의미한다.
Formal Method의 특징을 서술하시오
어떤 시스템에 대한 요구사항을 수학적 기법을 이용하여 요구사항을 정확하게 기술하고 그 요구사항이 제대로 달성되었는지를 검증하는 것을 의미하는 것으로, 크게 formal specification과 formal verification으로 구성된다.
security policy는 security requirement의 집합으로, 어떤 것을 보호해야하고 그것을 어떻게 보호할 수 있을까를 의미한다.
security policy modeling은 좁은 의미로는 security policy를 정형명세로 기술해둔 것을 의미하고, 넓은 의미로는 security policy를 정형명세로 기술하고 그 요구사항이 제대로 충족되었는지를 검증까지 하는 것이다. 검증에는 두 가지 의미가 포함된다. requirement 간의 모순점이 없는지를 검증하고, 설계도가 요구사항을 전부 반영하여 제대로 설계되었는지를 검증한다.
또한 보안성평가의 국제표준인 CC을 확인하면 EAL1~EAL7이 있는데 EAL4까지는 security policy를 제출할 것을 요구하나 EAL5부터는 security policy model을 제출할 것을 요구한다. 여기서 model은 정형명세로 제출하는 것을 의미한다.
DAC의 개념, 특징, 장단점 등에 대해 서술하시오.
DAC은 임의적 접근통제정책을 의미하는 것으로 데이터의 소유주가 데이터에 접근가능한 권한을 결정할 수 있고, 운영체제에 의해 시행되는 것이 특징이다. 장점으로는 필요한 사람에게 권한을 부여할 수 있는 최소권한법칙을 달성하기 쉽고 협업이 편하다는 장점이 있다. 반면 카피에 취약한 구조로 내가 권한을 부여했던 사람이 다시 다른 사람에게 데이터에 접근하는 권한을 부여할 수 있다는 것이 단점이다. 따라서 군에서는 이를 사용할 수 없는데 이에 대안으로 만들어진 것이 강제적 접근정책인 MAC이다.
MAC의 개념, 특징, 장단점 등에 대해 서술하시오.
MAC은 강제적 접근통제정책을 의미하는 것으로 주체와 객체의 보안등급에 따라 허가 또는 제한하는 것이 특징이다. 중앙집중형으로 엄격한 보안을 제공할 수 있는 것이 장점이나 모든 접근에 대해 확인해야 하므로 성능 저하가 발생할 수 있다는 단점이 있다. 또한 최소권한의법칙을 충족하지 못한다는 단점이 있고, 이 때문에 보안레벨로만 접근권한을 통제하지 않고 Compartment의 개념을 추가하여 최소권한의법칙을 달성하고자 하는 MLS 정책이 만들어졌다.
BLP 모델의 개념, 특징, 장단점 등에 대해 서술하시오.
벨과 라파듈라는 MLS 정책또한 충분하지 않기 때문에 Define and Design Approach를 해야 한다고 주장하며 1973년 BLP 모델을 제시하였다. 가장 먼저 달성해야할 것을 정의하고, 접근통제정책이 올바르게 시행되려면 SS-Property, *-Property가 만족해야되어야 한다고 하였다.
SS-Property (Simple Security Property): 기존의 MLS의 특징인 사용자가 가진 보안등급과 compartment의 범위가 접근하려고 하는 object의 보안등급과 compartment 범위보다 커야지만 object에 접근할 수 있음을 의미한다.
*-Property (Start Property): 기존 MLS를 충족하는 시스템은 SS-Property만 충족한다는 단점을 보완하기 위해 나온 개념으로 subject가 SS-property를 만족했다는 전제하에 보안등급이 높은 object에서 데이터를 읽고 낮은 등급의 object에 쓰면 안된다는 것을 의미한다. 어떤 것을 충족하고 어떤 것을 충족하지 않는지를 명확히 표현하는 것이 중요하다는 것을 보였다는 점에서 의의가 있는 것도 특징이다.
BLP 모델은 security property를 기밀성 관점에서만 고려하기 때문에 무결성 관점을 고려하지 못한다는 단점이 있고, Covert Channel에 취약하다는 단점이 있다.
BLP 모델에서 권한이 높은 프로세스와 권한이 낮은 프로세스간의 통신 방법은 무엇인가?
권한이 높은 프로세스가 권한이 낮은 프로세스와 통신을 해야할 때가 있지만 권한이 높은 곳에서 낮은 곳으로의 데이터가 쓰이는 것을 막았기 때문에 데이터를 전달할 수 없다는 단점이 있다. 이를 해결하기 위한 대안이 2가지가 있는데 첫 번째는 subject security level을 순간적으로 낮추는 방법이 있고, 두 번째는 *-Property를 위반해도 되는 Trusted subject group을 생성하여 서로간의 등급이 다르더라도 데이터를 주고 받을 수 있도록 하는 방법이 있다. 첫 번째 방법을 실제로 구현한 것이 MULTICS이다.
McLean이 BLP 모델에서 비판한 평정속성은 무엇을 의미하는가?
Tranquility(평정속성): 시스템이 한 번 세팅되면 사용자들의 권한은 바뀌지 않음을 의미한다. 벨과 라파듈라는 BLP 모델의 전제를 평정속성으로 하였지만 McLean으로부터 전제조건이 위반되었다고 지적하였다.
BLP 모델에서 주어진 formal method를 참고하여 SS-Property를 표현하시오.
SS Property = No Read Up
A state $(b, M, f)$ satisfies the SS-Property if
$\forall (s, o, a) \in b,$ such that $a \in \{read, write\}$
$f_O(o) \leq f_S(s)$
a subject can only observe objects of lower classification.
read 또는 write를 하고 있는 모든 subject와 object에 대해 object의 보안등급이 subject의 보안등급보다 낮으면 모든 action은 read 또는 write이다.
BLP 모델에서 주어진 formal method를 참고하여 *-Property를 표현하시오.
BiBa 모델의 개념, 특징, 장단점 등에 대해 서술하시오.
BLP 모델이 나온 뒤 기밀성만 다룬다는 단점을 보완하기 위해 무결성 관점을 다루기 위해 나오게 된 것으로 BLP 모델과 logical dual이라 할 수 있다. 무결성 관점에서는 정보의 흐름이 높은 곳에서 낮은 곳으로 가야한다. BLP 모델과 동일하게 SS-property와 *-Property를 동일하게 주장하였다.
SS- property (Read up)
subject의 integrity level이 object의 integrity level보다 높거나 같아야 데이터를 읽을 수 있음을 의미한다.
*-property (Write down)
subject의 integrity level이 object의 integrity level보다 높거나 같아야데이터를 쓸 수 있음을 의미한다.
클락 윌슨의 상용 컴퓨터 시스템과 군 전용 시스템에 대한 비교 논문의 의의를 서술하시오.
1983년 클락윌슨이 상용컴퓨터시스템의 보안정책과 군에서 쓰는 보안정책의 비교논문을 낸 바 있다. 내용의 핵심은 군에서는 Integrity가 중요하지 않을지 모르나 상용시스템에서는 Confidentiality보다 Integrity가 훨씬 중요하기 때문에 Integrity와 관련한 security requirement를 명확히 정의하고 디자인하는 것이 중요하다고 주장하였다. 이 논문은 사람들이 접근통제정책이 confidentiality 뿐만 아니라 Integrity도 중요하다고 생각하게 되었다는 점에서 의의가 있다.
Clark-Wilson Model을 설명하시오
가장 큰 특징 & 종류 및 개념 Clark-Wilson 모델의 가장 큰 특징은 Well formed transaction을 정의했다는 것이고 이는 절차가 잘 정의된 프로세스를 의미한다. Clark-Wilson Model은 CDIs, UDIs, TP, IVPs의 4가지 요소로 구성된다.
CDIs: Contrained Data Items의 약자로 Integrity가 중요한 데이터셋을 의미한다.
UDIs: Unconstrained Data Items의 약자로 Integrity가 중요하지 않은 데이터셋을 의미한다.
TP: Transformation Procedures로 일종의 업무 매뉴얼을 의미하는 것으로 업무 매뉴얼에 따라 절차가 엄격히 정의된 프로세스를 통해서만 접근 가능한 것이 특징이다. 예컨데 CDIs에 접근하려는 USER는 반드시 TP를 통해서만 접근해야 한다.
IVPs: Integrity Verification Procedures의 약자로, 주기적으로 CDIs의 무결성이 올바르게 지켜지고 있는지를 검증한다.
이러한 Clark-Wilson 모델의 예는 은행시스템이 있다. 은행에서 돈과 관련된 모든 데이터는 CDIs에 해당하고 이외의 데이터는 UDIs에 해당한다. TP는 입금, 출금, 계좌이체와 같이 명확히 정해진 절차가 있고 이 절차에 따라 움직이는 것을 의미한다. 그리고 어제 은행이 가지고 있던 돈에서 오늘 들어온 돈을 더하고 나간 돈을 빼는 것과 같이 정기적으로 검증과정을 거치는 것을 IVPs라고 한다. Clark-Wilson 모델은 크게 두 개의 업적을 가진다. 첫 번째는 상용시스템에서 Integrity가 중요할 수 있음을 강조했다는 점이다. 두 번째는 기존 BLP, Biba모델은 사용자가 데이터에 접근한다 생각하였지만 Clark-Wilson은 사용자는 프로그램(TP)에 접근하고 프로그램이 데이터에 접근한다고 하였다.
HRU (Harrison-Ruzo-Ullman) 모델에 대해 서술하시오.
HRU 모델은 BLP 모델의 전제조건이었던 평정속성을 위반했다는 McLean에 비판에 의해 권한이 바뀌어도 보안을 유지할 수 있는 방안을 연구한 모델이다. 동작원리는 권한을 요구하는 요청이 올 경우 임시로 matrix를 변경해보고 state가 잘 유지되는지를 검증한다. 예를 들어 matrix를 바꿨을 때도 기존과 동일하게 SS-property가 충족되는지를 체크하는 것이다. 충족된다면 바꾸고 충족되지 않으면 바꾸지 않는다는 것이 기본 개념이다. 하지만 HRU 모델은 state가 잘 유지되는지를 체크하는 것이 쉽지 않다는 단점이 있다. 따라서 HRU 모델에서는 제약조건을 추가하였다.
Monotonic protection system: destory나 delete 명령이 없는 시스템을 의미한다.
Monocondtional system: 각 명령의 조건 부분에 하나의 조건만 있는 시스템을 의미한다.
Finite number of subjects: subject의 개수가 finite한가?
Chinese Wall 모델에 대해 서술하시오.
Chinese Wall 모델은 HRU 모델이 더 발전된 형태이다. 접근권한이 사전에 세팅되고 요청이 있을 때마다 접근권한이 동적으로 변경되는 특징을 가진다. 또한 Chinese-Wall 모델은 subject의 접근권한이 바로 직전에 한 행동에 의해 다음 접근권한이 결정된다는 특징을 가지고 있다. 예를 들어 변호사가 CITI 은행의 변호를 맡는 순간 KB, NH, SH와 같은 다른 은행에 대한 접근권한이 차단된다. 하지만 S-OIL, GS 칼텍스와 같은 이해상충집단(COI, Conflict Of Interest)이 아닌 클래스의 데이터에는 접근할 수 있다. Brewer와 Nash가 Chinese-wall 모델을 정의할 때도 SS-property와 *-Property를 충족해야 한다고 하였다.
SS-Property: 데이터에 접근하는 동시에 이해상충집단에 해당하는 데이터의 접근하지 못함을 의미한다. 하지만 만약 이해상충되더라도 접근을 계속 유지하고 있거나 완전히 COI Class에 속한다면 접근 가능하다.
*-Property: Information flow에 있어 이해상충집단간의 un-sanitised information이 흐르지 못하도록 하는 것이다. 또한 write access는 이해상충집단에 속해있는 object가 현재 읽혀지지 않고 있거나, 또는 un-sanitised information을 가지고 있을때만 허용된다.
RBAC에 대해 서술하시오
RBAC은 역할기반접근통제정책이다. 기존의 DAC, MAC에서의 접근권한이 사람에게 부여되지만 실제 세상에서의 접근권한은 사람에게 부여되는 것이 아닌 그 사람의 역할에 부여된다는 점에 기반하였다. (그림 그리기) User와 Role사이에 Session이 있고, 이는 동시에 여러 개의 역할을 할당받기 위해 필요한 개념으로, 윈도우에서 창을 여러개 띄워 놓는 것과 같다. RBAC에서 role이 분리되어야할 경우가 2가지가 존재하는데 첫 번째로는 static seperation of Duty로 예를 들어 한 사람이 총무의 역할을 맡으면서 동시에 감사의 역할을 맡을 수 없음을 의미한다. 두 번째로는 dynamic seperation of Duty로 예를 들어 은행 업무를 하고 있는 직원의 역할을 가진 동시에 고객의 역할을 할 수없음을 의미한다.
우리나라의 리스크 관리에 있어 최대 문제점은 무엇인가?
데이터의 중요도에 따른 데이터의 등급화가 되어 있지 않다는 것이 핵심이다. 중국의 경우에도 의료, 금융, 개인정보 등을 Low, Medium, High, Very High와 같이 4단계로 나누나 우리나라의 경우 그렇지 않다. 또한 데이터의 중요도에 따라 데이터의 등급을 나눈 뒤 망분리와 망연계가 명확히 되어야 하지만 잘 이루어지지 않고 있는 것이 실태이다.
Covert Channel은 무엇이고 Side Channel과 어떻게 다르며 이 Covert Channel을 해결하기 위한 방안은 무엇인가?
Covert Channel은 설계자가 의도하지 않았던 방향으로 데이터를 유출하는 채널을 의미한다. Side Channel과의 차이점은 Covert Channel의 경우 송신자와 수신자간의 Covert Channel에 대한 약속이 필요하고, Side Channel의 경우 송신자가 필요하지 않고 수신자 입장에서 별도의 채널을 통해 정보를 추출하는 것이다. Covert Channel은 기본적으로 전부 막을 수는 없으나 이를 해결하기 위한 방안으로 Lattice Based 모델이 있다. Lattice Based 모델은 수학에서 이야기하는 Lattice 구조를 이용하여 정보가 흘러도되는 것과 흐르면 안되는 것을 포멀하게 정의하는 모델이다. Lattice 구조가 성립하는 조건으로는 GLB와 LUB가 있고, 모든 Subset에 대해서 GLB와 LUB가 존재할 경우에 해당한다. 하지만 현업에서 실제로 사용하기에는 복잡하다는 단점이 존재하고 이를 조금 더 적용하기 쉽고, 구현에 용이하게 만든 모델이 Non-Interference 모델이다. Non-Interference 모델은 covert-channel과 Inference attack을 주로 다룬다.
Execution Monitor의 개념과 특징을 서술하시오.
Execution Monitor는 이벤트가 발생할 때 시스템 정책들에 위반되는 사항이 있는지 확인하는 시스템이다. 구체적으로 어떤 함수가 error 상황을 야기하도록 하는 위험한 함수인지 아닌지를 검증하는 것으로, 그 함수 외부로 undesirable exception이 propagate 되지 않는지 또 그 결과에 대한 report가 제대로 되는지를 모니터링 한다.
Execution Monitor는 운영체제 안에서 동작하는 것으로 프로그램을 한 줄 한 줄 실행시켜보며 이벤트가 발생했을 때 EM 시스템이 괜찮은지 검증 후 괜찮다면 실행시키고 문제가 발생하면 빠져나오는 시스템이다. EM을 활용하면 DAC, MAC 정책에서 정책을 위반 여부를 관찰할 수 있는 것이 특징이다. 하지만 Information flow security 같이 정보가 제대로 흐르는지 아닌지는 EM으로 체크할 수 없다. 예를 들어 DDOS 같은 경우는 EM으로 체크할 수 없는데, 이는 EM이 항상 과거의 데이터를 보기 때문에 DDOS와 같이 미래를 보아야 하는 공격은 체크할 수 없는 단점이 있다. 즉 EM으로 모든 보안정책을 제어하기에 한계가 있고 불충분하기에 RM에 다른 요구사항이 추가되어야해서 복잡한 구조를 가지게 된다.
Liveness property와 Safety property에 대해 서술하시오.
Liveness property는 프로그램은 언젠가 종료될 것이지만 언제인지 알 수 없다는 의미를 가지며, Safety property는 나쁜일은 생기지 않는다는 것을 의미한다. Liveness property는 미래를 보아야 하기 때문에 어렵고 safety property는 과거를 보기 때문에 비교적 쉽다. Execution Monitor는 safety property에 속하는 것은 전부 측정할 수 있다. 하지만 EM으로는 모든 보안정책을 제어하기엔 한계가 있고, 불충분하기에 Reference Monitor에 다른 것이 추가되어야 해서 복잡한 구조를 가지게 된다.
Reference Monitor의 세 가지 기본원칙을 설명하시오
Reference Monitor: 감시 프로그램인 Reference Monitor는 운영체제에서 발생하는 모든 이벤트를 감시할 수 있어야 하고 정책에 위반되는 것을 차단해야 한다.
Simplicity & Assurance: RM이 중요하기 떄문에 수학적으로 증명해야 한다. 하지만 RM이 복잡하다면 수학적 증명이 어려워진다. 따라서 RM을 단순하게 만들고 이를 통해 Assurance를 높여야 한다.
Evaluation & Certification: 평가제도를 운영하여 정부가 이를 받아들이도록 해야 한다.
Reference Monitor의 세 가지 요구조건을 더 명확히 표현하여 설명하시오
Complete Mediation: RVM이 있어서 운영체제에서 발생하는 모든 이벤트를 통제할 수 있어야 한다. (Reference Validation Mechanism)
Tamper-Proof: RVM은 해커가 리버싱할 수 없어야 하고 non-bypassible하여 해커가 우회할 수 없어야 한다.
Verifiable: RVM은 충분히 작아서 수학적으로 검증 가능해야 한다.
Trusted Computing Base (TCB)를 설명하시오.
Security Kernel과 다른 보호메커니즘을 결합한 것으로, TCB는 신뢰가 필요한 모든 H/W와 S/W가 포함된다. (Security kernel: Reference Monitor를 실제로 구현해둔 것을 의미한다.)
Authentication vs Identification을 설명하시오.
Authentication은 사용자 인증을 의미하고, Identifiaction은 개인 식별을 의미한다. 예를 들어 네이버에 아이디와 비밀번호로 로그인하는 것은 사용자 인증에 해당하고 범죄현장에서 지문을 발견하여 데이터베이스에서 매칭하여 범인을 알아내는 것은 개인 식별에 해당한다. 내가 나임을 증명한다면 Authentication이고, 타인이 나를 식별한다면 Identification이다.
High Assurance Crypto Library란 무엇인가?
설계부터 구현까지 수학적으로 전부 증명된 것을 의미한다.
Secure Design Principle 12가지를 서술하시오
Least Privilege: 사람 또는 시스템이 필요로 하는 최소한의 권한만 부여하는 것을 의미한다.
Fail-Safe Defult: 명시적 허용이 아니면 거부를 의미한다. 예를 들어 방화벽 룰셋에 설정되어 있지 않다면 패킷을 drop하는 것과 같다.
Economy of mechanism: H/W나 S/W를 만들 때 설계를 심플하고 작게 만들어야 함을 의미한다.
Complete Mediation: 중요 자원에 접근하려는 것을 모두 통제할 수 있어야 함을 의미한다.
Design by Contract: 정해진 인터페이스나 프로토콜로만 중요 자원에 접근할 수 있어야 함을 의미한다.
Open Design: 설계도의 소스코드가 공개되더라도 안전도를 유지할 수 있어야 할 수 있어야 함을 의미한다.
Seperation of Privilege: 중요 권한은 분리되어야 함을 의미한다.
Least Common Mechanism: 공통 모듈 사용 최소화를 의미하는 것으로, Economy of mechanism과 정면으로 위배되는 특징이 있다.
Psychological Acceptability: 심리적으로 사용하기 좋아야함을 의미하는 것으로 Usable security라고도 불린다.
Defense In Dept: 보안 시스템을 둘 때 계층적으로 구성해야함을 의미한다.
Effective Logging: 효율적인 로깅이 가능해야 함을 의미한다. 최근 개인정보보호법으로 인해 무엇을 기록하지 말아야 할지도 고려해야 하는 것이 특징이다.
Built In, Not Bolt on: 시스템을 만들고 나서 보안을 고려하는 것이 아니라 시스템을 만들때 함께 보안을 고려하는 것을 의미한다.
Design Assurance를 쉽게 달성하는 방법은?
Design Assurance를 쉽게 달성하기 위해서는 전제조건을 맞추어 두면 된다. 또한 가정(Assumption)이 많으면 쉽게 달성할 수 있다.
Design Assurance를 입증하는 방법에 대해 서술하시오
크게 2가지로 나뉘며 Symbolic method와 Confidential method로 나뉜다.
Symbolic Method: 수학적 증명을 자동화하는데 사용하는 방법으로, 주로 리플레이 공격을 분석하는데 사용된다. 하지만 confidential method와 달리 복잡한 공격에 대해서는 증명이 어렵다는 단점을 가진다.
Computational Method: 정교한 공격에 대해 수학적 증명이 가능한 방법으로 골드아서와 미칼리가 주로 기여한 분야이다. Symbolic method와 달리 자동화시키기 어렵기 때문에 대부분 manual하게 증명하는 것이 특징이다.
SPN (Substitution-Permutation Network)의 특징을 서술하시오.
주로 대칭키인 AES 암호화에 사용되는 네트워크로, 네트워크 내부적으로 크게 Diffusion과 Confusion이 있다. Diffusion은 확산으로 암호문과 평문사이의 관계를 알아낼 수 없도록 복잡하게 섞어주는 것을 의미한다. 주로 permutation을 통해 데이터의 순서를 바꾸는 방법(P-Box)을 사용한다. Confusion은 혼돈으로 키와 암호문간의 관계를 알아낼 수 없도록 복잡하게 섞는 것을 의미한다. 주로 Substituion을 통해 다른 symbol로 바꾸는 방법(S-box)을 사용한다. 이러한 Diffusion과 Confusion을 극대화하기 위해서는 permutation과 substitution을 반복적으로 하면된다. 이러한 대칭키 암호에서 Design Assurance를 입증하기 위한 전제조건으로는 S-box와 P-box는 안전한 것으로, 특히 S-Box는 랜덤하다는 전제가 필요하다.
RSA 암호의 특징에 대해 설명하시오
디피와 헬만이 공개키 암호를 정의하였고 이러한 정의를 충족하여 만들어진 최초의 공개키 암호가 RSA 암호이다. RSA 암호의 안전성은 소인수분해에 기반한다. 하지만 RSA 암호의 해독방법은 소인수분해 말고도 존재하여 안전성은 증명되지 않았다. 대신 소인수분해 문제를 제외하고 RSA 암호에 대한 공격기법이 개발되면 그에 맞추어 업그레이드 시키는 것이 특징이다.
레빈암호 시스템에 대해 설명하시오
레빈암호시스템은 RSA 암호시스템과 달리 수학적구조가 아름답다. RSA 암호시스템은 기본적으로 안전성은 소인수분해 문제의 어려움에 기반하지만 소인수분해이외에도 암호를 해독할 수 있는 방법이 존재한다. 따라서 RSA 암호를 해독할 수 있는 공격 방법이 만들어질 때 마다 암호시스템을 업그레이드한다. 이와는 달리 레빈암호시스템은 해독가능한 방법이 소인수분해 밖에 없다는 것을 수학적으로 증명되어 있다. 이러한 레빈암호시스템은 Design Assurance를 만족하는 최초의 공개키 암호라는 것에 의의가 있다.
Random Oracle Model이란 무엇인가?
전제조건이 해쉬암호는 안전하다는 것으로, 정확히는 해시암호의 출력은 랜덤함을 전제하는 것을 의미한다. 이를 통해 기존의 theoretical한 암호시스템과 practical한 암호시스템이 결합되기 시작되었다는 점에서 의의가 있는 것이 특징이다.
Perfect Secrecy의 특징을 서술하시오.
Perfect secrecy는 샤논이 만든 개념으로 passive 공격자가 무한한 컴퓨팅 파워가 있더라도 암호문으로부터 어떠한 정보도 얻어낼 수 없는 것을 의미한다. 하지만 이는 대칭키에서는 성립하지만 공개키암호에는 적용할 수 없다는 단점을 가진다. 이는 공개키가 있기 때문에 전수조사로 비밀키를 찾을 수 있기 때문이다.
Semantic Security의 특징을 서술하시오
기존의 샤논이 만든 개념인 perfect secrecy의 단점인 공개키에서는 적용할 수 없다는 단점을 보완하기 위해 골드아서 박사가 정의한 개념으로 "유한한 컴퓨팅 파워를 가진 공격자가 암호시스템으로부터 그 어떠한 1비트의 정보도 알아낼 수 없음"을 의미한다. design assurance의 관점에서 요구사항이 한 단계 진화할 수 있었고 이후에는 이러한 정의를 충족하는 암호 알고리즘이 만들어지게 되었다는점에서 의의가 있다.
공개키암호의 message space가 작으면 발생할 수 있는 문제는 무엇이고 해결방법은 무엇인가?
공개키 암호에서 message space가 작다면 대칭키 암호와 달리 전수조사를 통해 해독이 가능하다는 문제점이 있다. 이를 해결하기 위한 방안으로는 같은 메시지더라도 출력값이 달라지게 하기 위해 랜덤패딩을 붙이는 방법이 있다. 이러한 랜덤패딩을 붙이는 방법이 Polynomial Security(IND-CPA)이다. 즉, 암호알고리즘이 polynomial security를 만족하려면 랜덤패딩이 필요하다.
Polynomial security (IND-CPA)의 특징을 서술하시오.
기존의 공개키암호시스템에서 message space가 작다면 대칭키암호시스템과 달리 전수조사를 통해 알아낼 수 있다는 단점을 보완하기 위해 나온 개념으로, 동일한 평문이 동일한 암호문을 출력하지 않도록 랜덤패딩을 붙이는 방법을 의미한다. 즉, polynomial security를 만족하려면 랜덤패딩이 필요하다. polynomial security는 semantic security와 다르게 표현되었지만 동치라는 특징을 가진다. 즉 암호알고리즘에 랜덤패딩을 추가하면 암호문으로부터 그 어떠한 정보도 노출되지 않는다.
암호문을 위/변조하는 Active Attacker를 막는 설계 방법은 무엇인가?
크게 3가지 방법이 있다. 첫 번째는 전자서명을 사용하는 것이다. 암호문에 전자서명을 붙여서 보내는 방식으로 가능하다. 하지만 공개키 암호문을 설계하는데 전자서명도 사용해야하기 때문에 비효율적인 방법에 해당한다. 두 번째는 Message Authentication Code를 붙이는 방법이 있다. 하지만 이 또한 MAC 알고리즘의 안전성에 대해 증명해야한다는 단점이 있다. 세 번째는 고정된 형태의 패딩을 추가하는 것이다. 하지만 semantic security를 만족하려면 랜덤한 패딩을 추가해야한다. 이러한 문제점을 해결하기 위한 방법이 OAEP이다.
OAEP(IND-CCA)의 특징을 서술하시오.
IND-CCA의 경우 기존의 골드아서와 미칼리의 semantic security가 passive한 공격자로 전제한다는 단점을 보완하기 위해 나온 개념으로 active한 공격자에서도 암호시스템을 안전하게 만들기 위한 방법이다. 이는 고정된 형태의 패딩을 추가하는 방식으로 충족시킬 수 있다. 하지만 semantic security를 만족하기 위해서는 랜덤패딩을 추가하여야 한다. OAEP는 이러한 고정패딩과 랜덤패딩을 함께 추가하는 방법으로 Chosen Cipher Attack에 안전하다는 특징을 가진다.
Non-malleability (NM-CCA)의 특징을 서술하시오.
전통적으로 암호문을 해독하거나 부분정보를 끄집어내는 방법과 달리 암호문을 해독하지 않고 암호문에 변조를 가하는 것을 의미한다. 이를 통해 암호문이 갖추어야 할 requirement가 semantic security와 non-malleability가 되었다. 하지만 후에 이는 다르게 표현되었으나 동치임이 확인되었고 결국 semantic security, polynomial security, non-malleability는 다르게 표현되었지만 하나라는 요구조건임을 확인하였다는 점에서 의의가 있다.
암호에서 Active 공격을 방어하기 위해 사용하는 방법은 무엇인가?
암호에서 active 공격이 많이 발생하기 때문에 암호알고리즘만 사용하지 않고 MAC과 함께 사용되는 경우가 많다. 크게 3가지 방법이 있다.
Encrypt-and-MAC: 메시지에 대해 암호화시키고 그것과 별개로 메시지에 대해 MAC 코드를 만드는 방법이다.
MAC-then-Encrypt: 메시지에 대해 MAC을 만들고 원래 메시지 뒤에 붙인 뒤 전체를 암호화시키는 방법이다.
Encrypt-then-MAC: 메시지를 먼저 암호화시키고 그 암호문에 대해 MAC을 붙이는 방법이다.
여기서 주요 쟁점은 설계방법에 따른 안전도 문제(합성보안 문제)가 제기되는데 통상적으로 Encrypt-then-MAC이 가장 안전하다고 알려져있다.
Compositional Security란 무엇인가?
합성보안문제로 예를 들어 블록체인에서 떠오르는 분야인 DeFi에서도 사용되는 개념이다. DeFi는 머니레고시스템이라고도 부르는데 이는 소스코드가 공개되어 있어 자신들이 만들고자하는 서비스를 만들어 DeFi 시스템에 붙이는게 가능하다. 이 때 공개된 소스코드에 취약점이 있다면 DeFi 전체시스템에 대해 합성보안 문제가 야기된다. 또한 BlackHat 2017에서 발표되었던 WPA2의 사례와 같다. 유닛테스트에서는 안전함이 증명되었지만 통합테스트(합성)에서는 안전하지 않았다.
Zero-knowledge 시스템의 특징을 서술하시오.
암호화 알고리즘과 전자서명은 단방향으로 보내면 되는 1-way 형식이지만 세상에는 interactive하게 동작하는 것이 많다는 점에 착안하여 어떤 client, server, verifier가 interactive하게 동작했을 때 안전하다는 것은 어떻게 입증하는가와 같은 문제가 대두되면서 도입된 개념이다. 영지식 증명의 개념은 3가지 조건을 만족해야 한다.
완전성(Completeness): 어떠한 정보가 참일 경우에 정직한 증명자는 정직한 검증자에게 그것을 납득시킬 수 있어야 한다.
건전성(Soundness): 어떤 정보가 거짓일 경우에 부정직한 증명자는 거짓말을 통해 정직한 검증자에게 그것이 ‘참’임을 납득시킬 수 없어야 한다.
영지식성(Zero-Knowledge): 검증자는 어떤 정보가 참 혹은 거짓이라는 사실 이외에는 아무것도 알 수 없어야 한다.
CC와 EAL7에서 소프트웨어 검증보다 소프트웨어 테스팅에 의존하는가? or Code Assurance의 한계는 무엇인가?
Software Fault, Error, Failure를 설명하고 왜 구분해야 하는지에 대한 이유를 서술하시오.
Software Fault: 소프트웨어 자체가 가지고 있는 결함을 의미하는 것으로 문제가 발생하는 근본 원인이다.
Software Error: 불안정한 프로그램 상태를 의미하는 것으로 어떤 값을 넣어 software의 문제가 있는 Falut까지 도달하면 내부적으로 이상상태가 발생하는 것을 의미한다.
Software Failure: Fault까지 도달하여 내부적으로 불안정한 프로그램 상태가 외부로 표출되는 것을 의미한다.
구분 없이 모두 합쳐서 bug라 부르면 안된다. 명확히 구분해야 test case가 제대로 되었는지 아닌지 구분할 수 있기 때문이다. 만약 모두 합쳐 bug라 부른다면 test case를 설명할 방법이 없어진다.
Software Fault의 종류는 무엇이 있는가?
Random Fault: 사람의 실수에 의해 발생하는 Fault를 의미한다.
Intentional Fault: 의도성을 가지고 발생시킨 Fault를 의미한다.
Software Testing과 Debugging의 차이점을 서술하시오.
Software testing은 소프트웨어를 체크할 수 있는 test value인 input값을 뽑아내는 것을 의미한다. 반면 debugging은 외부로 표출된 failure를 보고 결함이 있는, 문제의 원인이 되는 fault부분을 찾아가는 것을 의미한다.
Static testing과 Dynamic testing의 차이점을 서술하시오
Static testing은 프로그램을 실행시키지 않고 테스팅하는 것을 의미하는 것으로 소스코드, 바이너리, 중간언어가 될 수 있다. 반면 Dynamic testing은 프로그램을 실행시키면서 테스팅하는 것을 의미하는 것으로 체계적인 테스팅을 위해 DART라는 프로그램을 사용하기도 한다.
Black box testing이 먼저인가 White box testing이 먼저인가 그리고 이유를 설명하시오.
black box testing이 먼저이다. 개발공정상 개발단계 전까지 코드가 없기 때문에 white box testing을 할 수 없다. black box testing은 바이너리가 아닌 코드가 없이 테스팅하는 것을 의미한다. 때문에 설계문서와 같은 모든 것들이 black box testing의 대상이 된다. 이후 코드가 완성되면 white box testing까지 하여 정교한 테스팅이 가능해진다.
Validation과 Verification의 차이점을 서술하시오
Validation은 사용자의 마음에 맞도록 만들어졌는가를 의미하는 것으로 Verification보다 어려운 것이 특징이다. 여기에는 사용자의 요구를 전부 분석하여 requirement를 제대로 도출하였는지까지가 들어간다. Verification은 specification이 있고 이를 통해 requirement가 제대로 도출되었다고 전제하고 requirement가 specification대로 만들었는지 검증하는 것으로 validation보다 쉽다는 것이 특징이다.
test case 선정 시 잘 도출하였는지 평가하기 위해 네 요소를 사용하는데 이 네 요소와 특징에 대해 서술하시오.
4가지 요소는 RIPR이다.
Reachability: test input 값이 문제의 근원인 소프트웨어 fault가 있는 지점까지 도달해야 함을 의미한다.
Infection: test input 값이 문제의 근원인 소프트웨어 fault까지 있는 지점까지 도달하여 프로그램 내부 상태가 불완전한 상태(error state)로 만드는 것을 의미한다.
Propagation: 불완전한 상태가(erorr state)가 전이되어 최종적으로 Incorrect한 final state로 가는 것을 의미한다.
Revealability: 프로그램의 Incorrect한 final state가 실제로 외부로 드러나는 것을 의미한다.
Test requirement와 Coverage Criteria의 관계는 무엇인가?
test case → test set → test requirement → coverage criterion → coverage criteria의 단계를 가지는 구조이다. 둘 간의 관계를 예시를 들면 다음과 같다. 예를 들어 젤리의 맛이 6가지와 색이 4가지가 있을 때 Coverage Criteria는 두개가 될 수 있다. 젤리봉투를 뜯었을 때 맛이 6가지가 있어야 한다는 C1의 Criterion과 색이 4가지가 있어야 한다는 C2의 Criterion이다. C1과 C2를 합쳐 Coverage Criteria라고 하며, 이를 통해 test requirement를 도출할 수 있다.
소프트웨어를 모델링하는 대표적인 방법을 서술하시오. (Coverage Criteria를 줄 때 사용하는 방법)
소프트웨어를 모델링하기 위해 사용하는 방법은 크게 4가지로 Input domain, Graph, Logical Expression, Syntax Structure 방식이 있다. 어떤 방법론을 사용하느냐에 따라 coverage criteria는 다른 형태로 주어진다.
Input Domain model based testing: 함수에 들어가는 입력 값만보고 테스트케이스를 만드는 계획을 세우는 방법을 의미한다.
Graph model based testing: 소스코드를 그래프의 형태로 바꾸어 모델링하는 방법으로 소프트웨어 테스팅에 가장 많이 사용되는 기법이다.
Logical Expression model base testing: 조건문만 가지고 test case를 도출하는 모델링 방법으로, predicates라고도 부른다.
Syntax Structure model based testing: 문법 규칙을 주고 문법 규칙에 따라 test case를 생성하는 모델링 방법이다. 그래프만큼 모델링에 많이 사용되며 grammar-based modeling이라고도 한다.
Generator와 Recognizer를 설명하시오.
Generator는 coverage criteria를 주면 알아서 test case를 만들어주는 것을 의미하며, Recognizer는 test case가 주어지면 어느 coverage까지 달성하는지를 분석해주는 것이다.
Graph model based testing의 특징을 서술하시오.
소스코드를 그래프의 형태로 바꾸어 모델링하는 방법으로 소프트웨어 테스팅에서 가장 많이 사용되는 기법이다. 크게 2가지 기법으로 Structural coverage criteria와 Data flow coverage criteria로 분류 된다. (분류 특징 서술하기). 그래프 모델링 기법은 소스코드에 사용하는 것이 주로 일반적이나 설계단계의 문서와 더불어 제품을 개발하는 여러 단계에 테스팅하는데 활용할 수 있다. 그래프 모델링에서 test case 도출을 어렵게하는 요소로는 루프가 있다. 기존에는 루프를 만나면 사이클을 한 번만 돈다고 가정하였으나 이는 abstraction gap이 크다는 단점이 존재한다. 따라서 이를 해결하기 위한 방안으로 touring, sidetrips, detours라는 prime path 를 사용하여 abstraction gap을 줄이려는 노력을 하고 있다.
Call-Graph를 설명 하시오
Control Flow Graph, Data Flow Graph 이외에 Call Graph가 있는데 이는 어떤 모듈이 어떤 모듈을 부르는가에 대한 호출 관계를 표시하는 그래프이다. 모듈을 어떻게 분배시킬까에 대한 sub-system level에서 사용되며, 결과적으로 design integration test에 활용한다. (좀더 포멀하게 바꿀 수 있으면 좋겠습니다.)
Logical Expression Model based testing에 대해 서술하시오.
조건문만 가지고 test case를 도출해내는 모델링 방법으로 이를 predicates라고도 한다. logic expression은 소스코드에서 발견되는 predicates와 clause에 따라 이를 테스트할 수 있는 test case를 도출하는 것이 특징이다. clause에는 major clause와 minor clause가 있다. major clause는 predicates를 결정짓는 핵심이되는 것을 의미하며, minor clause는 그 이외의 것을 의미한다. 효율적인 test case 도출을 위해서는 major clause를 도출해내는 것이 중요하다. 하지만 logical expression 모델링 방법은 프로그램을 실행시키전까지는 파악하기 어렵다는 단점을 가진다. 예를 들어 어떤 값에 n을 나누거나 y를 나눌 때 어떤 값이 나올지 알기 어려운 것과 같다.
Syntax Structure Based Testing에 대해 서술하시오.
문법 규칙에 따라 test case를 생성하는 모델링 방법이다. Graph-based 모델링 방법만큼 많이 사용되며 Grammar-based modeling이라고도 한다. grmmar가 구성되면 두 가지 목적으로 사용가능하다. 첫 번째는 grammar에 맞춰 여러 test case를 생성할 수 있고, 두 번째로는 어떤 값이 grammar를 충족하는지에 대한 여부를 확인할 수 있다.
Structural Coverage Criteria과 Data Flow Coverage Criteria의 특징을 서술하시오.
Control Flow는 structural coverage criteria와 연계되고 Data Flow는 data flow coverage criteria로 연계된다. structural coverage criteria는 노드와 엣지로 그래프를 정의하고 분기(e.g. if)를 통해 프로그램이 실행되는 코드가 달라지는 것을 기준으로 하는 방법이다. 대표적으로 node coverage, edge coverage, edge-pair coverage, complete path coverage, specified path coverage 등이 있다. data flow coverage criteria는 프로그램이 어떻게 변수가 정의되고 사용되는지를 기반하여 커버리지 기준을 적용하는 방법을 의미한다. 즉, 데이터 흐름 그래프상에서 각 변수의 def-use-pair가 다양한 방식으로 실행되도록 하는 기준이다. 대표적으로 all-defs coverage, all-uses coverage, all-du-paths coverage이 있다.
mutant에 대해 설명하시오
mutant는 원본 프로그램이 있고 일부를 바꾸었을 때를 의미한다. mutant는 크게 valid mutant와 Invalid mutant로 나뉜다. valid mutant는 시드값을 바꾸었을 때 그래머를 만족하는 mutant를 의미하며, Invalid mutant는 시드값을 바꾸었을 때 그래머를 만족하지 않는 mutant를 의미한다. 주로 mutation testing에 사용 된다.
mutation testing을 설명하시오.
grammar(subject)로부터 ground string(seed) 값을 뽑아낸다. 이후 ground string(seed)에서 일부를 바꾸면 mutant가 생성된다. 이 때 test case를 generate하여 ground string와 mutant에 각각 넣고 같은지를 비교하며 이를 mutation testing이라 한다. 쉽게 말해 원본 프로그램은 run tests on subject에 들어가고 변형된 프로그램은 run tests on mutant에 들어간다. 이후 test case를 생성하여 각각의 프로그램에 넣었을 때 원본 프로그램과 변형된 프로그램을 구분할 수 있으면 이를 mutant를 죽였다 표현하고 이를 mutation testing이라 한다.
program-based mutation testing에 대해 서술하시오.
test case가 제대로 만들어졌는지 test할 때 주로 사용되는 testing 기법이다. coverage 개념과는 다르며, 얼마나 많은 mutant를 제거하였는지가 핵심이다. 즉, grammar를 따르지 않은 mutant와 grammar를 제대로 따른 원본을 test case가 구별해낼 수 있는 가이다.
여러 소프트웨어 테스팅 기법 중 grammar-based mutation testing이 가지는 특징은 무엇인가?
Input domain, graph, logical expression 등의 테스팅 기법과 달리 grammar-based mutation testing은 test case를 test 할 수 있다는 것이 가장 큰 특징이다. 또한 기본적인 grmmar를 정해두고 조금씩 변형해가며 input을 넣어보는 퍼징에도 효과적으로 사용할 수 있다.
Software verification의 특징을 서술하시오
software testing의 한계인 실제로 버그가 없음을 입증하기 위해 모든 가능한 인풋값에 대해 전부 테스트해보아야 한다는 것을 보완하기 위해 나온 것으로, software가 requirement를 충족하는지 충족하지 않는지를 수학적으로 증명하는 방법이다. 하지만 문제점은 어떤 software가 requirement를 충족하는지 하지 않는지를 증명하는 것은 undecidable problem에 속하기 때문에 이론적으로 software verification이 불가능하다고 입증되었다. 하지만 현실에서 마주하는 것은 모든 software가 아닌 특정 타입의 software이기 때문에 범위를 줄이게 되면 불가능하지 않다. software verification에서 사용되는 요소 기술의 종류는 symbolic execution, automatic theorem prover, model checker 등이 있다.
Concrete Execution이란 무엇인가?
프로그램을 실행시키면서 변수 값이 어떻게 변형되어 가는지 확인하며 프로그램이 제대로 동작하는지 하지 않는지를 검증하는 것이다.
Symbolic Execution에 대해 서술하시오.
기호실행은 프로그램에 구체적인 값을 넣지 않고 모든 것을 기호로 바꾸어 전개시키고, 실제 테스팅하고자 하는 영역의 방정식을 충족하는 값을 구하는 방식이다. 전개된 상태에서 방정식만 풀면 어떤 경로를 테스트할지 test case를 자동으로 뽑아낼 수 있다. 즉 testing input generation이 가능하여 어떤 경로로 갈지 바로 뽑아낼 수 있다는 것이 장점이다. 반대로 path explosion 때문에 적용이 쉽지 않은 것이 단점인데 이는 구체적인 값이 아니라 기호를 넣으면 길이가 긴 경로가 나올 수 있기 때문이다. 이에 대한 대안으로는 pre-conditioned symbolic execution으로, 이는 프로그래밍할 때 BOF와 같이 에러가 많이 발생할 수 있는 조건에 사용할 수 있다. 보안관점에서는 buggy path만 체크하면 경우의 수가 줄어 Exploitable한 path에 대해 symbolic execution하여 효과적인 test case 도출이 가능하다.
Automatic Theorem Prover에 대해 서술하시오.
software verification에서 자주 사용되는 요소 기술 중 하나이다. 프로그램을 정형명세로 바꾸어 표현하는 것이 특징이다. 구성요소는 3가지로 variable, precondition, postcondition이 있다. 만약 a와 b를 더한 결과인 result를 출력해주는 프로그램이 있다 가정할 경우 a,b,result는 variable에 해당하고 이에 할당된 초기값은 precondition에 해당한다. 마지막으로 a, b, result에 대한 관계는 postcondition에 해당한다. 프로그램이 전부 수행되었을 때 Automatic Theorem Prover가 자동으로 정형명세를 충족하였는지 검증하며, 이를 Floyd-Hoare Triple이라고도 한다.
Floyd-Hoare Triple에 대해 서술하시오.
Variable, Precondition, Postcondition으로 구성되는 것으로, Precondition {P}가 주어졌을 때 논리적 흐름에 따라 전개되면 반드시 Postcondition {Q}에 도달한다. 따라서 프로그램에 Precondition과 Postcondition을 정형명세로 바꾸어 중간 중간 끊어서 주게되면 실제 프로그램이 제대로된 논리 흐름을 따르는지 검증할 수 있는 것이 특징이다. 이러한 Precondition과 Postcondition을 정형명세로 표현하면 Theorem Prover가 정형명세를 지키고 있는지를 검증한다.
(Automatic) Theorem Prover와 Model Checker의 차이를 서술하시오.
Model Checker는 기본적으로 automatic theorem prover에서 확장된 개념이다. 둘간의 차이점은 크게 자동화 여부, 적용 범위, requirement 개수로 3가지다. 자동화여부: theorem prover의 경우 프로그램 중간중간에 precondition과 postcondition을 정형명세로 다 입력해주어야 하는 반자동이다. 반면 model checker는 프로그램을 모델로 바꾸고 모델이 도달해야할 요구사항을 준 뒤 충족했는지의 여부를 yes or no로 출력 가능한 것으로 완전 자동에 해당한다. 적용범위: theorem prover의 경우 반자동이기에 적용 범위가 넓어 많은 프로그램에 적용할 수 있다 반면 model checker는 적용할 수 있는 프로그램이 theorem prover 보다는 적다는 단점을 가진다. requirement 개수: theorem prover는 반자동인 대신 체크할 수 있는 (security) requirement개수가 많고, model checker는 완전자동이지만 적용할 수 있는 (security) requirement 개수가 적다.
Model Chcker에 대해 서술하시오.
모델 체커는 프로그램을 모델링하여 모델체커에 넣고 도달해야할 requirement를 주어 도달여부를 검증하는 것으로, 관점을 조금 바꾸면 exploit을 자동 생성하는 도구를 만들어 counter example을 뽑을 수 있는게 특징이다. 아래와 같이 아키텍처가 구성된다(그림 그리기). 이를 활용하여 cyber grand challenge에서 취약점 탐지 자동화 도구가 나왔었다. 하지만 이는 모든 가능한 exploit 코드를 만들어지는 것은 아닌데 이는 취약 가능성이 높은 buggy path만 보기 때문이다.
최단 거리 알고리즘이란 그래프 상에서 노드 간의 탐색 비용을 최소화하는 알고리즘이다. 일반적으로 네비게이션과 같은 길찾기에 적용된다. 최단 거리 알고리즘 종류는 크게 3가지가 있다. 1. 다익스트라(Dijkstra) 2. 플로이드 워셜(Floyd Warshall) 3. 벨만 포드(Bellman Ford)이다.
1. 다익스트라 (Dijkstra) 알고리즘
다익스트라 알고리즘은 그래프 상에서 특정 한 노드에서 다른 모든 노드까지의 최단거리를 구하는 알고리즘이다. 다르게 표현하면 가중 그래프에서 간선 가중치의 합이 최소가 되는 경로를 찾는 알고리즘 중 하나이다.
다익스트라는 그리디와 동적 계획법이 합쳐진 형태이다. 현재 위치한 노드에서 최선의 경로를 반복적으로 찾으면서도 계산 해둔 경로를 활용해 중복된 하위 문제를 풀기 때문이다. 다익스트라는 만약 그래프에 음의 가중치가 있다면 사용할 수 없다. 그 이유는 그리디를 통해 최단 경로라고 여겨진 경로 비용을 DP 테이블에 저장한 뒤, 재방문하지 않는데, 만약 음의 가중치가 있다면 이러한 규칙이 어긋날 수 있기 때문이다. 음의 가중치가 포함된다면 플로이드 워셜이나 벨만 포드 알고리즘을 사용해 최단 경로를 구할 수 있다. 다만 시간 복잡도가 늘어나는 단점이 있기에 해결하고자 하는 문제에 맞게 사용해야 한다.
만약 아래와 같은 그래프가 있다 가정하고 동작 원리를 확인해보자.
위와 같은 초기 노드와 간선을 테이블에 나타내보자면 다음과 같다. 예를 들자면 1행 4열은 1번 노드에서 4번 노드로 가는 것을 나타내며 비용은 8이 든다.
0
3
INF
8
9
3
0
2
INF
INF
INF
2
0
1
3
8
INF
1
0
INF
9
INF
3
INF
0
다익스트라 알고리즘은 특정 한 노드에서 다른 모든 노드까지의 최단 거리를 구하는 알고리즘이라 했다. 예를 들어 특정 한 노드를 1이라 가정하면 [0, 3, INF, 8, 9]는 다음과 같은 과정을 통해 업데이트 된다.
아래와 같이 노드 1을 선택하게 되면 1과 연결된 3개의 간선을 확인한다.
이 중에서 다른 정점으로 가는 최소 비용이 2번 노드가 가장 작기 때문에 2번 노드로 이동하고, 노드 1번은 방문 처리한다. 이 때 테이블 값 변화는 없다.
0
3
INF
8
9
2번 노드에 연결된 노드는 1번과 3번이다. 하지만 1번의 경우 이미 방문했고, 비용이 크므로 볼 필요 없다. 2와 최소비용으로 연결된 노드는 3이기 때문에 노드 3으로 이동하고, 2를 방문처리 한다. 이 때 테이블 값 변화가 발생한다. 1과 3은 연결되지 않았었다. 하지만 그리디와 같이 계속해서 최적의 상태를 업데이트 하므로 다른 노드를 탐색하다 3을 방문할 수 있기 때문에 1 → 2 → 3으로 이동하는 동안의 비용인 5로 업데이트 해준다.
0
3
5
8
9
다음으로 3번 노드에 연결된 간선은 총 3개이다. 하지만 2의 경우 방문처리 되었으니 노드 4, 5번 두 개만 고려하면 된다.
노드 4, 5번 중 더 비용이 적은 것은 4번 노드이므로, 4번 노드로 이동하고 3번 노드는 방문처리 해준다. 마찬가지로 테이블 값 변화가 발생한다. 기존에는 1 → 4로 가는 비용이 8이었지만 1 → 2 → 3 → 4를 거치는 것이 6이 들기에 테이블 값을 6으로 업데이트 시켜준다.
0
3
5
6
9
다음으로 4번 노드에 연결된 간선은 총 2개이다. 하지만 두 개 모두 방문처리 되었고 5로 가는 간선이 없다.
따라서 테이블 값 업데이트는 없다. 또 알고리즘은 여기서 끝이 난다. 최종적으로 1에서 다른 모든 노드까지의 비용은 아래 테이블이 된다.
0
3
5
6
9
이를 코드로 구현하기 위해서는 가중치에 중요도가 있으므로 자료구조 힙을 사용해 표현해준다. 전체 코드는 다음과 같다.
""" This is input value. you can just copy and paste it.
5 6 1
1 2 3
1 4 8
1 5 9
2 1 2
2 3 2
3 2 2
3 4 1
3 5 3
4 1 8
4 3 1
5 1 9
"""
import heapq
def dijkstra(start):
heap = []
heapq.heappush(heap, [0, start]) # 최소힙은 배열의 첫 번째 값을 기준으로 배열을 정렬.
INF = float('inf')
weights = [INF] * (vertex+1) # DP에 활용할 memoization 테이블 생성
weights[start] = 0 # 자기 자신으로 가는 사이클은 없으므로.
while heap:
weight, node = heapq.heappop(heap)
if weight > weights[node]: # 비용 최적화 전부터 큰 비용일 경우 고려할 필요 없음.
continue
for n, w in graph[node]: # 최소 비용을 가진 노드를 그리디하게 방문한 경우 연결된 간선 모두 확인
W = weight + w
if weights[n] > W: # 여러 경로를 방문해 합쳐진 가중치 W가 더 비용이 적다면
weights[n] = W # 업데이트
heapq.heappush(heap, (W, n)) # 최소 비용을 가진 노드와 합쳐진 가중치 추가
return weights
vertex, edge, start = map(int, input().split())
graph = [[] for _ in range(vertex+1)]
for i in range(vertex+edge):
src, dst, weight = map(int, input().split())
graph[src].append([dst, weight])
weights = dijkstra(start)
print (weights) # [inf, 0, 3, 5, 6, 8]
최종 출력되는 최소 비용 중 1에서 1로 가는 사이클은 없으므로 0이 된다. 또한 만약 주어진 문제가 1에서 3으로 가는 최소비용을 구하는 것이라면 5가 되고, 1에서 4로가는 최소 비용을 구하는 것이라면 6이 된다.
벨만 포드 알고리즘은 가중 유향 그래프 상에서 특정 한 노드로 부터 다른 노드까지의 최단 경로를 구하는 알고리즘이다. 다익스트라 알고리즘의 한계점을 보완하기 위해 나왔다. 그 한계점이란 간선이 음수일 때 최단 경로를 구할 수 없다는 것이다. 사실 정확히는 음의 가중치 자체가 문제가 되진 않는다. 문제는 사이클 형성 여부에 따라 달렸다. 만약 사이클을 형성하면 문제가 된다. 아래 그림을 보자.
만약 다익스트라 알고리즘을 통해 특정 한 노드(1)에서 다른 노드(2)로의 최소 거리를 구하는 문제를 해결하려 한다면 가중치 3 → 4 → 5를 거쳐 비용이 12가 된다. 하지만 중간에 사이클이 있기 때문에 3 → 4 → -6 → 4 → -6 → 4 → -6 ...이 되어 비용이 무한히 작아지게 된다.
이러한 문제점을 해결하기 위해 나온 알고리즘이 벨만 포드이다. 기본적으로 다익스트라와 동일하지만 핵심 차이점은 간선의 가중치가 음일 때도 최소 비용을 구할 수 있다. 다만 시간복잡도가 늘어나기 때문에 가중치가 모두 양수일 경우 다익스트라를 사용하는 것이 좋다. 시간 복잡도가 늘어나는 이유는 그리디하게 최소 비용 경로를 찾아가는 다익스트라와 달리, 벨만 포드는 모든 경우의 수를 고려하는 동적 계획법이 사용되기 때문이다.
그렇다면 모든 경우의 수를 어떻게 고려할까? 그 방법은 매 단계 마다 모든 간선을 전부 확인하는 것이다. 다익스트라는 출발 노드에서만 연결된 노드를 반복적으로 탐색하며 다른 모든 노드까지의 최소 거리를 구했다. 하지만 벨만 포드는 모든 노드가 한번씩 출발점이 되어 다른 노드까지의 최소 비용을 구한다.
아직 조금 추상적이니 구체적인 아래 그림을 보며 동작 과정을 알아보자.
위와 같은 그래프가 있다고 할 때 모든 노드가 한 번씩 출발 노드가 될 것이다. 복잡하지 않다. Itertation 1회, 2회일 때를 이해하면 귀납적으로 적용하여 이해할 수 있기 때문이다.
위와 같은 초기 상태의 그래프가 있을 때, 가중치를 담을 DP 테이블 값은 아래와 같이 모두 INF가 된다.
INF
INF
INF
INF
INF
[Iteration 1] 첫 번째로 노드 1번을 먼저 탐색해보자.
1번 노드에 연결된 인접노드에 해당하는 간선의 가중치를 업데이트 해준다.
0
3
5
6
9
가중치 업데이트에 있어 시작 노드는 사이클이 없으므로 0이 되고, 2~5모두 연결된 간선이 있으므로 해당 가중치 값을 업데이트 해준다.
[Iteration 1] 이제 2번 노드를 보자. 2번 노드는 3번과 연결되어 있다.
1 → 3 경로 비용인 3보다 1 → 2 → 3 경로 비용인 -8이 더 작으므로 DP 테이블 값을 3에서 -8로 업데이트 해준다.
0
-6
-8
9
8
[Iteration 1] 이제 3번 노드를 보자. 4번과 5번 노드에 연결되어 있다.
1 → 4 비용인 9보다 1 → 2 → 3 → 4 비용인 -3이 작으므로 9를 -3으로 업데이트 해준다.
0
-6
-8
-3
8
또 1 → 5 비용인 8보다 1 → 2 → 3 → 5 비용인 -15가 작으므로 8을 -15로 업데이트 해준다.
0
-6
-8
-3
-15
[Iteration 1] 이제 4번 노드를 보자. 3번 노드와 연결되어 있다.
DP 테이블의 3번에 담긴 비용인 -8이 1 → 4 → 3 비용인 5보다 작으므로 업데이트 하지 않는다.
0
-6
-8
-3
-15
[Iteration 1] 이제 5번 노드를 보자. 3번 노드와 연결되어 있다.
DP 테이블 3번의 -8이 1 → 5 → 3의 비용 -5보다 더 작으므로 업데이트 하지 않는다.
0
-6
-8
-3
-15
이를 노드 개수(V) - 1까지 반복 진행한다. 그리고 추가적으로 음의 사이클의 존재 여부를 파악하고 싶다면 마지막으로 1번더 반복하여 총 V번의 반복 했을 때 V-1번 했을 때와 값이 달라진다면 음의 사이클이 있는 것이라 판별할 수 있다. 음의 사이클이 있다면 반복시 무한히 작아지기 때문이다.
Iteration1 종료시 [inf, 0, -6, -8, -3, -15]
Iterataion2 종료시 [inf, 0, -6, -28, -23, -35]
Iteration3 종료시 [inf, 0, -6, -48, -43, -55]
Iteration4 종료시 [inf, 0, -6, -68, -63, -75]
가되며 마지막으로 여기서 한 번더 수행했을 때 값이 바뀐다면 음의 사이클이 존재하는 것이다.
Iteration5 종료시 [inf, 0, -6, -88, -63, -75]
이를 코드로 구현하면 다음과 같다.
"""
5 9
1 2 -6
1 3 3
1 4 9
1 5 8
2 3 -2
3 4 5
3 5 -7
4 3 -4
5 3 -13
"""
import sys
input = sys.stdin.readline
def bellman_ford(start):
weights[start] = 0
for i in range(V):
for src, dst, weight in graph:
W = weights[src] + weight
if weights[src] != INF and weights[dst] > W:
weights[dst] = W
if i == V -1:
return False # negative cycle exists
return True # there is no cycle
V, E = map(int, input().split())
graph = []
for _ in range(E):
src, dst, weight = map(int, input().split())
graph.append([src, dst, weight])
INF = float('inf')
weights = [INF] * (V+1)
if bellman_ford(1): # 출발 노드를 인자 값으로 넣어줄 것
for i in range(2, V+1): # 출발 노드인 1을 제외하고 다른 모든 노드로 가기 위한 최단 거리 출력
print (weights[i], end = ' ')
else:
print ("There is negative cycle.")
플로이드 워셜 알고리즘은 모든 노드 간의 최단거리를 구할 수 있다. 한 노드에서 다른 모든 노드까지의 최단 거리를 구하는 다익스트라와 벨만포드 알고리즘과 대조된다. 플로이드 워셜 알고리즘은 그래프 상에서 음의 가중치가 있더라도 최단 경로를 구할 수 있다. 하지만 음의 가중치와 별개로 음의 사이클이 존재한다면 벨만 포드 알고리즘을 사용해야 한다.
플로이드 워셜 알고리즘은 모든 노드 간의 최단거리를 구하고 이 때, 점화식이 사용되기에 동적 계획법에 해당한다. 동적 계획법에 해당하므로 최단 거리를 업데이트할 테이블이 필요하다. 이 때 모든 노드간의 최단 거리이므로 2차원 배열이 사용된다. 특정 한 노드에서 출발하는 다익스트라가 1차원 배열을 사용하는 것과 차이점이 있다.
플로이드 워셜 알고리즘의 핵심은 각 단계마다 특정한 노드 k를 거쳐 가는 경우를 확인한다. 아래 점화식을 살펴보면 다음과 같다.
$D_{ij} = min(D_{ij}, D_{ik} + D_{kj})$
$i$에서 $j$로 가는 것과 $i$에서 $k$를 거쳐 $j$로 가는 것 중 어느 것이 최소 비용인지를 찾는 것이다.
구현은 매우 간단하여 3중 for문이 사용된다. 아래 코드는 위 점화식을 기반으로 코드화 시킨 것이다.
for k in range(1, V+1): # via
graph[k][k] = 0 # 사이클 없으므로 자기 자신 0
for i in range(1, V+1): # src
for j in range(1, V+1): # dst
graph[i][j] = min(graph[i][j], graph[i][k]+graph[k][j])
코드와 함께 동작 과정을 아래 그래프를 통해 살펴보자.
노드 4개와 간선 7개로 구성된 그래프다. 이를 바탕으로 DP 테이블 초기 상태를 만들면 다음과 같다. 하나의 노드에서 다른 노드로 바로 갈 수 있다면 가중치를, 없다면 INF를 저장해준다.
INF
5
INF
7
4
INF
-3
INF
6
INF
INF
4
INF
INF
2
INF
이제 3중 for문을 사용해 거쳐가는 노드를 설정 후 해당 노드를 거쳐갈 때 비용이 줄어드는 경우 값을 업데이트 시켜줄 것이다. 먼저 거쳐가는(k) 노드가 1일 때의 경우를 살펴보자
[Iteration 1] 거쳐가는 노드 K = 1
Iteration 1의 테이블 첫 번째 행을 업데이트 해보자. 노드 1에서 노드 1을 거쳐 노드 1~4까지 탐색하는 경우이다.
graph[1][2] = min(graph[1][2], graph[1][1]+graph[1][2]) : 5와 0+5를 비교하는 것이므로 업데이트 X
graph[1][3] = min(graph[1][3], graph[1][1]+graph[1][3]): INF와 0+INF를 비교하는 것이므로 업데이트 X
graph[1][4] = min(graph[1][4], graph[1][1]+graph[1][4]): 7과 0+7을 비교하는 것이므로 업데이트 X
Iteration 1의 테이블 첫 번째 행을 업데이트 한 결과는 다음과 같다. 업데이트는 없었으므로 전과 동일하다. 다만 graph[k][k] = 0에 의해 첫번째 값만 INF에서 0으로 바뀌었다.
0
5
INF
7
4
INF
-3
INF
6
INF
INF
4
INF
INF
2
INF
Iteration 1의 테이블 두 번째 행을 업데이트 해보자. 노드 2에서 노드 1을 거쳐 노드 1~4까지 탐색하는 경우이다.
graph[2][1] = min(graph[2][1], graph[2][1]+graph[1][1]): 4와 4+0을 비교하는 것이므로 업데이트 X
graph[2][2] = min(graph[2][2], graph[2][1]+graph[1][2]): INF와 4+9를 비교하는 것이므로 업데이트 O
graph[2][3] = min(graph[2][3], graph[2][1]+graph[1][3]): -3과 4+INF를 비교하는 것이므로 업데이트 X
graph[2][4] = min(graph[2][4], graph[2][1]+graph[1][4]): INF와 4+7을 비교하는 것이므로 업데이트 O
Itertaion 1의 테이블 두 번째 행을 업데이트 한 결과는 다음과 같다. 업데이트는 두 번 이뤄졌다.
0
5
INF
7
4
INF → 9
-3
INF → 11
6
INF
INF
4
INF
INF
2
INF
Iteration 1의 테이블 세 번째 행을 업데이트 해보자. 노드 3에서 노드 1을 거쳐 노드 1~4까지 탐색하는 경우이다.
graph[3][1] = min(graph[3][1], graph[3][1]+graph[1][1]): 6과 6+0을 비교하는 것이므로 업데이트 X
graph[3][2] = min(graph[3][2], graph[3][1]+graph[1][2]): INF와 11을 비교하는 것이므로 업데이트 O
graph[3][3] = min(graph[3][3], graph[3][1]+graph[1][3]): INF와 6+INF를 비교하는 것이므로 업데이트 X
graph[3][4] = min(graph[3][4], graph[3][1]+graph[1][4]): 4와 13을 비교하고 원래 4였으므로 업데이트 X
Itertaion 1의 테이블 세 번째 행을 업데이트 한 결과는 다음과 같다. 업데이트는 한 번 이뤄졌다.
0
5
INF
7
4
9
-3
11
6
INF → 11
INF
4
INF
INF
2
INF
Iteration 1의 테이블 네 번째 행을 업데이트 해보자. 노드 4에서 노드 1을 거쳐 노드 1~4까지 탐색하는 경우이다.
graph[4][1] = min(graph[4][1], graph[4][1]+graph[1][1]): INF와 INF+0을 비교하므로 업데이트 X
graph[4][2] = min(graph[4][2], graph[4][1]+graph[1][2]):INF와 INF+5를 를 비교하므로 업데이트 X
graph[4][3] = min(graph[4][3], graph[4][1]+graph[1][3]): 2와 INF+INF를 비교하고 원래 2였으므로 업데이트 X
graph[4][4] = min(graph[4][4], graph[4][1]+graph[1][4]): INF와 INF+7을 비교하므로 업데이트 X
Itertaion 1의 테이블 네 번째 행을 업데이트 한 결과는 다음과 같다. 업데이트는 이뤄지지 않았다.
0
5
INF
7
4
9
-3
11
6
11
INF
4
INF
INF
2
INF
이러한 과정을 노드의 수만큼 반복해주면 된다. 이를 요약하면 다음과 같다.
Iteration2는 노드 1~4에서 노드2를 거쳐 노드 1~4를 탐색하는 경우가 될 것이다.
Iteration3은 노드 1~4에서 노드3을 거쳐 노드 1~4를 탐색하는 경우가 될 것이다.
Iteration4는 노드 1~4에서 노드4를 거쳐 노드 1~4를 탐색하는 경우가 될 것이다.
이를 코드로 나타내면 앞서 본 것과 동일하다. 중요한 것은 거쳐서 노드 k를 거쳐갈때 다이렉트로 가는 것보다 비용이 적어지는가를 판단하는 것이다.
for k in range(1, V+1): # via
graph[k][k] = 0 # 사이클 없으므로 자기 자신 0
for i in range(1, V+1): # src
for j in range(1, V+1): # dst
graph[i][j] = min(graph[i][j], graph[i][k]+graph[k][j])
이러한 플로이드 워셜 알고리즘을 구현하는 전체 코드는 다음과 같다.
""" This is input value. you can just copy and paste it.
4 7
1 2 5
1 4 7
2 1 4
2 3 -3
3 1 6
3 4 4
4 3 2
"""
import sys
input = sys.stdin.readline
V, E = map(int, input().split())
INF = float('inf')
graph = [[INF] * (V+1) for _ in range(V+1)]
for _ in range(E):
src, dst, weight = map(int, input().split())
graph[src][dst] = weight
for k in range(1, V+1): # via
graph[k][k] = 0
for i in range(1, V+1): # src
for j in range(1, V+1): # dst
graph[i][j] = min(graph[i][j], graph[i][k]+graph[k][j])
for i in range(1, V+1):
for j in range(1, V+1):
print (graph[i][j], end= ' ')
print()
링크드 리스트란 데이터와 포인터를 담은 노드를 연결시킨, 연결 자료구조다. 다음 노드만 가리키는 포인터만 있다면 단순 연결 리스트(Single Linked List)라 하고, 다음 노드와 이전 노드를 가리키는 포인터 두 개가 있다면 이중 연결 리스트(Doubly Linked List)라고 한다. 만약 두 링크드 리스트에서 head와 tail이 서로 앞 뒤로 연결되어 있다면 환형 연결 리스트(Circular Linked List)이다.
링크드리스트는 순차 자료구조인 배열과 달리 포인터를 사용하기에 삽입과 삭제가 용이하다. 또한 배열과 달리 크기를 동적으로 조절할 수 있는 것도 장점이다. 반면 링크드 리스트는 특정 노드를 바로 접근할 수 없는 것이 단점이다. 링크드 리스트를 전부를 탐색해야 할 수 있도 있다. 따라서 링크드 리스트와 배열은 경우에 따라 나누어 사용해야 한다. 데이터가 빈번히 추가되거나 삭제될 경우 링크드리스트를 쓰는 것이 적합하고, 데이터 탐색과 정렬이 위주라면 배열을 쓰는 것이 적합하다. 참고로 윈도우 작업 관리자가 대표적인 링크드 리스트를 사용한 구현물이다. 하나의 프로세스는 앞 뒤로 다른 프로세스들과 연결되어 있는 Circular Linked List 구조로 되어 있다. 첫 번째 프로세스부터 다음 포인터를 계속 탐색하면 모든 프로세스 리스트를 가져올 수 있다.
단순 연결 리스트의 경우 기능은 크게 삽입/삭제/조회/탐색으로 구성된다. 이를 구현하기 위해 노드에 정보를 담을 Node 클래스와 기능을 구현할 SinglyLinkedList 클래스가 필요하다. 구현물은 다음과 같다.
class Node:
def __init__(self, data, next = None) -> None:
self.data = data
self.next = next
class SinglyLinkedList:
def __init__(self) -> None:
self.head = None
self.size = 0
def size(self):
return self.size
def is_empty(self):
return self.size == 0
def insert_front(self, data):
if self.is_empty():
self.head = Node(data, None)
else:
self.head = Node(data, self.head)
self.size += 1
def insert_back(self, data, current):
current.next = Node(data, current.next)
self.size += 1
def delete_front(self):
if self.is_empty():
raise LookupError("There is no node in the linked list")
self.head = self.head.next
self.size -= 1
def delete_back(self, current):
if self.is_empty():
raise LookupError("There is no node in the linked list")
temp = current.next
current.next = temp.next
self.size -= 1
def traverse(self):
array = []
current = self.head
while current:
array.append(current.data)
current = current.next
return array
def search(self, target):
current = self.head
for i in range(self.size):
if current.data == target:
return i
current = current.next
return None
def print_list(self):
current = self.head
while current:
if current.next != None:
print (current.data, '→ ', end='')
else:
print (current.data)
current = current.next
if __name__ == "__main__":
S = SinglyLinkedList()
# Insert
S.insert_front('apple')
S.insert_front('bear')
S.insert_front('cat')
S.insert_back('dog', S.head.next)
S.insert_front('egg')
S.insert_front('fish')
# Search
S.print_list() # fish → egg → cat → bear → dog → apple
print(f"Index: {S.search('dog')}") # Index: 4
# Delete
S.delete_front()
S.print_list() # egg → cat → bear → dog → apple
S.delete_back(S.head)
S.print_list() # egg → bear → dog → apple
# Traverse
print (S.traverse()) # ['egg', 'bear', 'dog', 'apple']
더블 링크드 리스트 또한 구현을 위해 노드에 정보를 담을 Node 클래스와 기능을 구현할 SinglyLinkedList 클래스가 필요하다. 구현물은 다음과 같다.
class Node:
def __init__(self, data=None, prev=None, next=None):
self.data = data
self.prev = prev
self.next = next
class DoublyLinkedList:
def __init__(self):
self.head = Node()
self.tail = Node(prev=self.head)
self.head.next = self.tail
self.size = 0
def size(self):
return self.size
def is_empty(self):
return self.size == 0
def insert_front(self, current, data):
temp = current.prev
next = Node(data, temp, current)
current.prev = next
temp.next = next
self.size += 1
def insert_back(self, current, data):
temp = current.next
next = Node(data, current, temp)
temp.prev = next
current.next = next
self.size += 1
def delete(self, current):
front = current.prev
back = current.next
front.next = back
front.prev = back
self.size -= 1
return current.data
def print_list(self):
if self.is_empty():
raise LookupError('There is no node in the linked list')
else:
current = self.head.next
while current != self.tail:
if current.next != self.tail:
print(current.data, '←→ ', end='')
else:
print(current.data)
current = current.next
D = DoublyLinkedList()
D.insert_back(D.head, 'apple')
D.insert_front(D.tail, 'bear')
D.insert_front(D.tail, 'cat')
D.insert_back(D.head.next, 'dog')
D.print_list() # apple ←→ dog ←→ bear ←→ cat
D.delete(D.tail.prev)
D.print_list() # apple ←→ dog ←→ bear
D.insert_front(D.tail.prev, 'fish') # apple ←→ dog ←→ bear ←→ fish ←→ cat
D.print_list()
D.delete(D.head.next) # dog ←→ bear ←→ fish ←→ cat
D.print_list()
D.delete(D.tail.prev) # dog ←→ bear ←→ fish
D.print_list()
이진 탐색 알고리즘은 탐색 알고리즘 종류 중 하나로, 이름 그대로 절반씩 나누어 원하는 값을 알고리즘이다. 이진 탐색을 위한 전제 조건으로 배열이 오름차순 또는 내림차순으로 정렬되어 있어야 한다. 동작 방식은 간단하다. 배열의 중앙을 기준으로 원하는 값이 작은지 큰지 비교하여 한 쪽을 배제하고 나머지 부분을 반복해서 탐색하는 방식이다.
가령 예를 들어 아래와 같이 찾고자 하는 값이 5일 경우, 배열의 가운데인 4를 기준으로 삼은 다음 오른쪽에 있다는 것을 알 수 있다. 이후 왼쪽 배열 0~4를 배제하고 오른쪽 배열 5~9 부분을 탐색한다. 찾고자 하는 값이 5~9 부분의 중앙인 7을 기준으로 왼쪽에 있으므로 다시 오른쪽 배열을 배제하고 왼쪽 배열 5~7을 탐색한다. 6을 기준으로 왼쪽에 있으므로 오른쪽 7을 배제하고 왼쪽 5를 찾으며 탐색이 완료되는 방식으로 동작한다.
원하는 값을 찾기 위해 배열의 모든 원소를 탐색하는 순차 탐색의 경우 시간복잡도가 $O(n)$이다. 하지만 이진 탐색의 경우 시간복잡도가 이보다 작은 $O(logN)$이 된다는 것이 특징이다. 조금 덧붙이자면 시간복잡도 $O(logN)$는 배열이 정렬되고 고정된 상태에서 가능하다. 만약 배열에 삽입, 제거, 탐색과 같은 연산이 함께 이뤄진다면 시간복잡도가 $O(n)$까지 떨어질 수 있다. 때문에 삽입, 제거, 탐색과 같은 연산이 함께 이뤄지는 경우 이진탐색 트리를 자료구조로서 사용해야 한다. 이진탐색트리의 경우 삽입, 제거, 탐색을 해도 시간복잡도가 $O(logN)$이 보장되는 특징이 있기 때문이다.
이진 탐색 알고리즘 구현은 크게 두 가지 방법이 있다. 첫 번째는 재귀를 사용하지 않는 방식이고, 두 번째는 재귀를 사용하는 방식이다. 두 구현 방법 모두 공통적으로 세 종류의 변수들이 필요하다.
버블정렬은 서로 인접해 있는 요소 간의 대소 비교를 통해 정렬한다. 버블 정렬은 정렬 알고리즘 중 가장 단순한 알고리즘으로, 단순한 만큼 비효율적이다. 시간 복잡도가 최고, 평균, 최악 모두 $O(n^2)$이며 공간복잡도는 하나의 배열만 사용하므로 $O(n)$을 가진다. 동작 방식은 인접한 두 요소간의 대소 비교를 진행한다.
만약 배열에 n개의 요소가 있을 경우 1번째 원소 vs 2번째 원소를 비교하고 2번째 원소 vs 3번째 원소를 비교하고, ... n-1번째 원소 vs n번째 요소를 비교하면 1회전 비교가 끝난다. 1회전이 끝나면 가장 큰 원소는 맨 뒤에 위치하게 되므로 2회전 비교에서는 제외된다. 마찬가지로 두 번째로 큰 원소는 가장 큰 원소 앞에 위치하게 되므로 3회전 비교에서는 제외된다. 즉 버블 정렬을 1회 수행할 때 마다 정렬해야 할 원소가 하나씩 줄어든다. 이를 코드로 구현하면 아래와 같다.
def bubble_sort(array):
""" Best: O(n^2) Average: O(n^2) Worst: O(n^2) | O(n) """
for i in range(len(array)):
for j in range(len(array)-i-1):
if array[j] > array[j+1]:
array[j], array[j+1] = array[j+1], array[j]
return array
2. 삽입 정렬 (Insert Sort)
삽입 정렬이란 정렬을 진행할 원소의 index보다 낮은 곳에 있는 원소들을 탐색하며 알맞은 위치에 삽입해주는 정렬 알고리즘이다. 동작 방식은 두 번째 index부터 시작한다. 그 이유는 첫 번째 index는 비교할 원소가 없기 때문이다. 알고리즘이 동작하는 동안 계속해서 정렬이 진행되므로 반드시 맨 왼쪽 index까지 탐색하지 않아도 된다는 장점이 있다. 모두 정렬되어 있는 Optimal한 경우 모든 원소가 한 번씩만 비교되므로 $O(n)$의 시간 복잡도를 가진다. 또한 공간복잡도는, 하나의 배열에서 정렬이 이루어지므로 $O(n)$이다.
삽입 정렬을 코드로 구현하면 아래와 같다. 첫 번째 for문은 정렬할 원소를 차례대로 선택하는 것이며, 두 번째 for문은 정렬할 원소보다 아래 인덱스에 있는 요소와 비교하기 위함이다.
def insert_sort(array):
""" Best: O(n) Average: O(n^2) Worst: O(n^2) | O(n) """
for i in range(1, len(array)):
for j in range(i, 0, -1):
if array[j-1] > array[j]:
array[j-1], array[j] = array[j], array[j-1]
return array
삽입 정렬을 최적화할 경우 아래 코드와 같다.
def insert_sort(array):
for i in range(1, len(array)):
j = i
while j > 0 and array[j-1] > array[j]:
array[j-1], array[j] = array[j], array[j-1]
j -= 1
return array
3. 선택 정렬 (Selection Sort)
선택 정렬이란 배열에서 최소값을 반복적으로 찾아 정렬하는 알고리즘이다.
시간복잡도 최선, 평균, 최악 모두 $O(n^2)$에 해당하는 비효율적인 알고리즘으로 정렬 여부와 상관없이 모든 경우의 수를 전부 확인한다. 동작방식 3단계로 구성된다. 첫 번째는 주어진 배열에서 최소값을 찾는다. 두 번째는 최소값을 맨 앞의 값과 바꾼다. 세 번째는 바꿔준 맨 앞 값을 제외한 나머지 원소를 동일한 방법으로 바꿔준다. 이를 알고리즘으로 나타내면 다음과 같다.
def selection_sort(array):
""" Best: O(n^2) Average: O(n^2) Worst: O(n^2) | O(N^2) """
for i in range(len(array)):
idx = i
for j in range(i+1, len(array)):
if array[idx] > array[j]:
idx = j
array[idx], array[i] = array[i], array[idx]
return array
덧붙여 선택 정렬은 크게 2가지로 최소 선택 정렬과, 최대 선택 정렬이 있다. 최소는 위와 같이 오름차순으로 정렬하는 것이고 최대는 위와 반대로 내림차순으로 정렬하는 것이다.
4. 퀵 정렬 (Quick Sort)
퀵 정렬은 분할정복법과 재귀를 사용해 정렬하는 알고리즘이다.
퀵 정렬에는 피봇(Pivot)이라는 개념이 사용된다. 피봇은 한 마디로 정렬 될 기준 원소를 뜻한다. 피봇 선택 방법에 따라 퀵 정렬의 성능이 달라질 수 있다. 최적의 피봇 선택이 어려우므로 임의 선택을 해야 한다. 보통 배열의 첫 번째 값이나 중앙 값을 선택한다. 퀵 정렬의 동작방식은 다음과 같다. 가령 예를 들어 배열 [5, 6, 1, 4, 2, 3, 7]이 있고, 피봇을 임의로 4를 선택했다 가정하자. 이후 4를 기준으로 작은 것은 왼쪽으로 큰 것은 오른쪽으로 보내 [1, 2, 3] < 4 < [5, 6, 7]를 생성한다. 다시 왼쪽에서부터 임의의 피봇 2를 설정하여 [1] < 2 < [3]을 생성하고 오른쪽에선 임의의 피봇 6를 설정하여 [5] < 6 < [7]로 나눈다. 만약 배열 길이가 1이 된다면 가장 정렬 완료된 것이므로 분할된 배열을 합쳐 줌으로써 정렬을 마친다. 이를 알고리즘으로 구현하면 다음 코드와 같다.
def quick_sort(array : list) -> list:
""" Best: O(nlogn) Average: O(nlogn) Worst: O(n^2) | O(nlogn) """
if len(array) <= 1:
return array
pivot = array[len(array) // 2]
small, equal, big = [], [], []
for num in array:
if num < pivot:
small.append(num)
elif num > pivot:
big.append(num)
else:
equal.append(num)
return quick_sort(small) + equal + quick_sort(big)
5. 병합 정렬 (Merge Sort)
병합 정렬은 분할정복과 재귀 알고리즘을 사용하는 정렬 알고리즘이다.
퀵 정렬과 함께 두 개의 알고리즘이 사용된다는 측면에서 공통점을 가진다. 하지만 차이점은 퀵 정렬이 피봇 선택 이후 피봇 기준으로 대소를 비교하는 반면, 병합 정렬은 배열을 원소가 하나만 남을 때 까지 계속 이분할 한 다음, 대소관계를 고려하여 다시 재배열 하며 원래 크기의 배열로 병합한다. 예를 들어 배열 [6, 5, 1, 4, 3, 2, 8, 7]이 있을 때, 첫 번째로 [6, 5, 1, 4]와 [3, 2, 8, 7]로 분리한다. 두 번째로 [6, 5], [1, 4], [3, 2], [8, 7]로 나눈다. 세 번째로 [6], [5], [1], [4], [3], [2], [8], [7]로 나눈다. 이렇게 모든 원소가 분리되면 대소 관계를 고려하여 병합 과정을 거친다. 첫 번째로 [5, 6], [1, 4], [2, 3], [7, 8]이 되며, 두 번째는 [1, 4, 5, 6], [2, 3, 7, 8]이 된다. 마지막으로 하나의 배열로 병합되면서 [1, 2, 3, 4, 5, 6, 7, 8]와 같이 정렬이 완료되면서 알고리즘이 종료된다. 이를 코드로 나타내면 아래 코드와 같다.
def merge_sort(array: list) -> list:
""" Best: O(nlogn) Average: O(nlogn) Worst: O(nlogn) | O(n) """
if len(array) < 2:
return array
mid = len(array)//2
low = merge_sort(array[:mid])
high = merge_sort(array[mid:])
merged_array = []
l, h = 0, 0
while l < len(low) and h < len(high):
if low[l] < high[h]:
merged_array.append(low[l])
l += 1
else:
merged_array.append(high[h])
h += 1
merged_array += low[l:]
merged_array += high[h:]
return merged_array
시간 복잡도의 경우 최선, 평균, 최악 모두 $O(nlogn)$이며 공간 복잡도의 경우 정렬된 원소를 담을 배열이 하나 필요로 하므로 $O(n)$.
6. 힙 정렬 (Heap Sort)
힙이란 트리 기반의 자료구조로서, 두 개의 노드를 가진 완전 이진 트리를 의미한다. 따라서 힙 정렬이란 완전 이진 트리를 기반으로 하는 정렬 알고리즘이다. 힙의 분류는 크게 최대 힙과 최소 힙 두 가지로 나뉜다. 최대 힙은 내림차순 정렬에 사용하며, 최소 힙은 오름차순 정렬에 사용한다.
최대힙의 경우 부모 노드가 항상 자식노드 보다 크다는 특징을 가진다. 반대로 최소힙의 경우 부모 노드가 항상 자식노드 보다 작다는 특징을 가진다. 이러한 힙에서 오해할 수 있는 특징은 힙은 정렬된 구조가 아니다. 부모 자식 간의 대소 관계만 나타내며 좌우 관계는 나타내지 않기 때문이다. 예를 들어 최소 힙에서 대부분 왼쪽 노드가 오른쪽 노드보다 작지만 4의 자식 노드인 7과 5는 왼쪽이 오른쪽보다 크다.
힙은 완전 이진 트리기 때문에 적절히 중간 레벨의 노드를 추출하면 중앙값에 가까운 값을 근사치로 빠르게 추출할 수 있다는 장점을 갖고 있다. 때문에 힙은 배열에 순서대로 표현하기 적합하다. 또한 균형을 유지하려는 특징 때문에 힙은 우선순위 큐, 다익스트라, 힙 정렬, 프림 알고리즘에 활용된다. 특히 힙 덕분에 다익스트라 알고리즘의 시간 복잡도는 $O(V^2)$에서 O(ElogV)로 줄어들 수 있었다.
힙 정렬 과정을 최대힙을 기준으로 우선 간략히 보자면 아래 GIF와 같다.
최대힙 정렬 동작 과정
최대 힙의 동작을 코드로 작성하면 아래와 같다.
def heap_sort(array : list) -> list:
""" Best: O(nlogn) Average: O(nlogn) Worst: O(nlogn) | O(nlogn) """
n = len(array)
for i in range(n//2-1, -1, -1):
heapify(array, i, n)
for i in range(n-1, 0, -1):
array[0], array[i] = array[i], array[0]
heapify(array, 0, i)
return array
def heapify(array : list, index : int, heap_size : int) -> None:
smallest = index
left = (2 * index) + 1
right = (2 * index) + 2
if left < heap_size and array[left] < array[smallest]:
smallest = left
if right < heap_size and array[right] < array[smallest]:
smallest = right
if smallest != index:
array[smallest], array[index] = array[index], array[smallest]
heapify(array, smallest, heap_size)
if __name__ == "__main__":
array = [1, 10, 5, 5, 2, 9, 8, 7, 6, 4, 0, 3, 2, 9]
print (heap_sort(array)) # [10, 9, 9, 8, 7, 6, 5, 5, 4, 3, 2, 2, 1, 0]
먼저 heapify 함수의 역할은 부모와 자식의 대소 관계를 확인해 자리를 바꿔주는 동작을 한다. 예를 들어 위 같이 최대힙을 구현할 때 부모 노드가 자식 노드보다 작다면 상호 간의 자리를 바꿔주는 것이다. left, right는 비교가 진행 될 노드의 인덱스를 의미한다. 초기 값은 루트 노드의 바로 아래 두 자식 노드이다. 첫 번째 조건문은 왼쪽 자식이 부모보다 작은지 확인한다. 두 번째 조건문은 오른쪽 자식이 부모보다작은지 확인한다. 세 번째 조건문은 초기 index와 동일하지 않다면 부모 자식간의 상호 위치를 변경한 뒤 재귀를 통해 반복한다.
7. 셸 정렬 (Shell Sort)
셸 정렬이란 삽입 정렬의 단점을 보완하고자 도입되었다. 삽입 정렬은 주어진 정렬 상태가 역순으로 배열되어 있을수록 비교횟수가 늘어나고, 최선의 경우 $O(N)$이지만 최악의 경우 $O(N^2)$으로 성능 차이가 크다. 셸 정렬은 이러한 시간복잡도를 평균적으로 $O(N^{1.25})$ 또는 $O(N^{1.5})$ 수준으로 낮추고자 도입된 알고리즘이다. 셸 정렬에 사용되는 핵심 개념은 interval (간격)이다. interval은 비교할 원소 간의 간격을 의미한다. 셸 정렬에서는 비교 횟수를 줄이기 위해 interval은 큰 값에서 낮은 값으로 낮춰간다. 동작 방식은 배열에서 interval 만큼 떨어진 원소들을 부분집합으로 구성한 뒤 삽입 정렬을 진행하는 방식으로 진행된다. 초기 interval 값은 len(array) // 2로 설정하며 계속 2로 나누어준다. 예를 들어 아래와 같이 배열 크기가 8이라면 초기 interval = 4가 되어 아래와 같이 비교가 진행 된다.
interval이 4인 경우 거리가 4만큼 떨어져 있는 원소끼리 부분집합을 이루어 비교대상이 된다. 위 그림에선 (35, 14), (33, 19), (42, 27), (10, 44)이 서로 비교 대상이 된다. 비교 진행한 뒤 interval을 2로 나누어주어 4에서 2가 된다. 이후 다시 interval만큼 떨어진 원소를 부분집합화하여 비교한다.
interval이 2인 경우 거리가 2만큼 떨어져 있는 원소끼리 부분집합을 이뤄 비교한다. (14, 27, 35, 42), (19, 10, 33, 34)가 부분집합이 되어 정렬이 진행된다. 이후 다시 interval을 2로 나눠주어 1이 되면 아래와 같이 삽입 정렬이 진행된다.
이를 코드로 구현하여 나타내면 다음과 같다. 주로 가독성을 위해 변수명을 interval을 h로 표현하기도 한다.
def shell_sort(array : list) -> list:
""" Best: O(n) Average: O(n^1.25,1.5) Worst: O(n^2) | O(n) """
n = len(array)
interval = n // 2
while interval > 0:
for i in range(interval, n):
j = i - interval
temp = array[i]
while j >= 0 and array[j] > temp:
array[j+interval] = array[j]
j -= interval
array[j+interval] = temp
interval //= 2
return array
8. 기수 정렬 (Radix Sort)
기수 정렬은 non-comparison 알고리즘으로 원소간의 대소 비교를 하지 않고 정렬하는 알고리즘이다. 대신 기수 정렬은 정렬하고자 하는 수의 낮은 자리 수를 차례대로 확인하여 정렬하는 방식이다. 정렬을 위해 총 10개의 queue를 사용한다.
첫 번째로, 1의 자리 수를 확인하여 각 원소의 1의 자리에 해당하는 queue에 쌓아준다. 이후 0~9의 queue를 순회하며 차례대로 가져온다. 두 번째로, 10의 자리 수를 확인하여 각 원소의 10의 자리에 해당하는 queue에 쌓아준다. 이후 0~9의 queue를 순회하며 차례대로 가져온다. 세 번째가 진행되기 위해서는 100의 자리수를 가진 값이 있어야 하며, n번째가 진행되기 위해서는 $10^{(n-1)}$의 자리수를 가진 수가 있어야 한다.
이를 코드로 구현하면 다음과 같다.
from collections import deque
def radix_sort(array : list) -> list:
""" Best: O(n) Average: O(n) Worst: O(n)"""
buckets = [deque() for _ in range(10)]
MAX = max(array)
queue = deque(array)
radix = 1
while MAX >= radix:
while queue:
num = queue.popleft()
buckets[(num // radix) % 10].append(num)
for bucket in buckets:
while bucket:
queue.append(bucket.popleft())
radix *= 10
return queue
자리수를 담을 bucket을 총 10개 생성해준다. 이후 가장 큰 자리 수 만큼 반복해야 하므로 max(array)를 통해 가져온다. 알고리즘은 크게 두 단계로 나눠서 보면 간단하다. 첫 번째는 queue에 있는 배열을 각 자리수에 해당하는 bucket에 담아주는 과정이다. 두 번째는 bucket에 담은 원소들을 다시 queue에 담아주는 과정이다. 다만 이 두 과정을 반복하되 배열 최대값이 가지는 최대 자리수까지는 비교해주어야 하므로 radix에 10을 곱해줘서 반복하며, 배열 최대값의 자리수보다 넘어가면 끝나는 것이다.
9. 카운팅 정렬 (Counting Sort)
카운팅 정렬(계수 정렬)은 non-comparison sort 알고리즘에 해당하는 알고리즘으로 comparison sort에 해당하는 버블, 선택, 힙, 병합, 퀵, 삽입이 기껏해야 평균적으로 $O(nlogn)$이나 $O(n^2)$의 시간복잡도를 갖기에 이를 $O(n)$ 수준으로 낮추고자 도입된 알고리즘이다. 카운팅 정렬의 동작은 이름 그대로 배열에 존재하는 원소 별 개수를 세어 정렬하는 방식으로 간단히 나타내보이자면 아래 GIF와 같다.
배열에 담긴 요소의 개수를 count라는 배열에 담아 넣은 뒤 차례대로 개수만큼 출력해준다. 우선, 결과적으로 코드를 구현해보자면 아래와 같이 간단한 코드로 나타낼 수 있으며 크게 5단계로 이뤄진다.
def counting_sort(array : list) -> list:
""" Best: O(n) Average: O(n+k) Worst: O(n+k) | O(n+k) """
count = [0] * (max(array) + 1) # 1. create a count array to check how many numbers each have.
for num in array: # 2. check how many numbers each have.
count[num] += 1
for i in range(1, len(count)): # 3. do cumulative sum
count[i] += count[i-1]
arr = [0] * len(array) # 4. create a new array to contain the numbers to be sorted.
for num in array: # 5. sort.
idx = count[num]
arr[idx-1] = num
count[num] -= 1
return arr
1. 배열에 있는 원소 개수를 담을 count 배열을 생성한다. 배열 크기는 원소 값 그대로를 인덱스로 사용하기 위해 max(array)+1로 해준다.
2. 배열에 있는 원소 개수를 count 해준다.
3. 누적합을 진행한다. 그 이유는 누적합을 진행하게 되면 앞 뒤 원소 간의 개수 차이가 곧 몇 칸을 차지할지 알 수 있기 때문이다. 이 부분이 제일 처음 잘 이해가 되지 않는 부분이었다. 예를 들어 설명하기 위해 임의의 배열 [2, 5, 3, 2, 1, 4, 4, 2]라는 배열이 있다 하자. 그러면 count 배열이 [0, 1, 3, 1, 2, 1]가 된다. 이후 count 배열에 누적합을 진행하면 [0, 1, 4, 5, 7, 8]이 된다. 이 누적합을 통해 아래와 같은 사실을 알 수 있다.
count[0] = 0: count 배열의 0번째 인덱스인 값 0은 (0-0)칸을 차지하고, 위치하게 되는 인덱스는 [0:0]이 된다. count[1] = 1: count 배열의 1번째 인덱스인 값 1은 (1-0)칸을 차지하고, 위치하게 되는 인덱스는 [0:1]이 된다. count[2] = 4: count 배열의 2번째 인덱스인 값 2는 (4-1)칸을 차지하고, 위치하게 되는 인덱스는 [1:4]가 된다. count[3] = 5: count 배열의 3번째 인덱스인 값 3은 (5-4)칸을 차지하고, 위치하게 되는 인덱스는 [4:5]가 된다. count[4] = 7: count 배열의 4번째 인덱스인 값 4는 (7-5)칸을 차지하고, 위치하게 되는 인덱스는 [5:7]이 된다. count[5] = 8: count 배열의 5번째 인덱스인 값 5는 (8-7)칸을 차지하고, 위치하게 되는 인덱스는 [7:8]이 된다.
즉, 누적합 해준 배열을 통해 원소 개수 만큼 도출된 인덱스에 넣어주면 자연스럽게 정렬 되는 것이다. 이러한 과정을 거치기 위해 다음 2단계를 더 진행 한다.
4. 정렬 된 원소를 담고자하는 새로운 배열을 생성해준다. 새 배열 크기는 원래 배열 크기와 동일하다.
5. 정렬하고자 하는 배열의 원소를 순회하며 count[원소]의 위치에서 누적합 되어 있는 값을 index로 지정해준다. 이후 새로 생성한 배열 result에 그 값을 넣어주고 누적합된 값을 -1을 해준다. 여기서 누적합 값에 -1을 해주는 것은 result의 index에 차례대로 같은 수를 담는 것이 아니라 역순으로 담아야 하기 때문이다. 역순으로 값을 담는 이유는 현재 알고리즘 구조상 역순으로 담아야 하기 때문이다. 이중 루프를 통해서 차례대로 값을 담을 수 있지만 코드 가독성과 동작 효율성을 고려하면 위와 같이 작성하는 것이 더 좋다.
마지막으로 시간복잡도는 $O(n+k)$가 된다. k가 상수이긴 하지만 생략되지 못하는 것은 그 만큼 영향을 미칠 수 있기 때문이다. 1~4번 과정 모두 $O(n)$에 해당한다. 하지만 5번에서 count 배열을 업데이트 하는 과정에서 원소 중 max 값인 k를 k만큼 반복하게 되므로 $O(n+k)$가 된다. 만약 정렬하고자 하는 배열의 max 값이 배열의 개수보다 작다면 $O(n)$이 된다. 하지만 배열의 개수보다 커지면 커질수록 배열 공간만 차지하고 값이 들어있지 않는 sprase한 배열이 될 수 있고, 무의미한 공간도 탐색해야 하므로 시간 복잡도가 높아질 수 있는 것이다.
10. Tim Sort
Tim Sort는 삽입정렬과 병합정렬이 결합된 정렬 알고리즘이다. Tim Peter라는 자에게 의해 고안된 알고리즘으로 파이썬 내장 정렬 알고리즘으로 채택되어 있다. Tim Sort는 왜 다른 알고리즘에 비해 상대적으로 느린 삽입정렬을 사용할까? 삽입정렬의 경우 앞서 기술한 바와 같이 평균과 최악의 경우 $O(n^2)$로 다른 알고리즘에 비해 시간복잡도가 높아 잘 사용되지 않는다. 하지만 이러한 단점에도 불구하고 삽입정렬에는 참조 지역성이라는 주요한 성질이 있다. 운영체제 시간에 배우거나 신입 개발자 인터뷰에 때때로 물어보는 내용이다.
CPU가 빠른 연산을 위해 사용하는 캐시 메모리에 데이터를 담을 때 적중률을 높이기 위해 사용하는 원리다. 쉽게 말해 최근 참조했던 메모리와 인접한 메모리를 참조할 확률이 높으니 이들을 캐시 메모리에 미리 담아두는 것이며, 삽입정렬은 인접한 메모리와 비교를 반복하기에 참조 지역성의 원리를 잘 만족하고 있다고 할 수 있다. 또 삽입정렬은 원소가 많아질수록 느려지는 단점이 있지만 정렬 수가 적당히 작은 수라면 퀵정렬보다 빨라지는 장점이 있다. Tim Sort는이러한 삽입정렬의 특성을 활용하여 전체 정렬 대상 원소들을 부분부분(divide)으로 작게 나눈 다음 삽입정렬을 수행하고 병합(conqure)을 수행하면 정렬이 조금 더 빠르지 않을까 하는 아이디어를 기반으로 만들어졌다. 이러한 Tim Sort는 실제로 시간복잡도를 최선의 경우 $O(n)$, 평균은 $O(n\log n)$, 최악의 경우 $O(n\log n)$를 갖는다.
Tim Sort에서는 이러한 삽입정렬을 그대로 사용하진 않고 속도를 개선한 이진삽입정렬을 사용한다. 이진삽입정렬을 사용하면 앞서 말한 참조 지역성이 떨어지게 되나 적당히 작은 수의 원소를 정렬한다면 참조 지역성이 크게 문제가 되지 않으면서 시간복잡도를 개선할 수 있게 된다.
RUN = 32
def insert_sort(array, left, right):
for i in range(left + 1, right + 1):
key = array[i]
j = i - 1
while j >= left and array[j] > key:
array[j + 1] = array[j]
j -= 1
array[j + 1] = key
def merge(array, left, mid, right):
len1 = mid - left + 1,
len2 = right - mid
left_array, right_array = [], []
for i in range(0, len1):
left_array.append(array[left + i])
for i in range(0, len2):
right_array.append(array[mid + 1 + i])
i, j, k = 0, 0, left
while i < len1 and j < len2:
if left_array[i] <= right_array[j]:
array[k] = left_array[i]
i += 1
else:
array[k] = right_array[j]
j += 1
k += 1
while i < len1:
array[k] = left_array[i]
k += 1
i += 1
while j < len2:
array[k] = right_array[j]
k += 1
j += 1
def tim_sort(array):
""" Best: O(n) Average: O(nlogn) Worst: O(nlogn) | O(n) """
n = len(array)
for i in range(0, n, RUN):
insert_sort(array, i, min((i + RUN - 1), n - 1))
size = RUN
while size < n:
for left in range(0, n, size * 2):
mid = left + size - 1
right = min((left + size * 2 - 1), (n - 1))
merge(array, left, mid, right)
size = size * 2
return array
if __name__ == "__main__":
array = [5, 2, 8, 4, 1, 9, 6, 3, 7]
sorted_array = tim_sort(array)
print(sorted_array)
