루니프의 짤막보안강의 루니프의 짤막보안강의

[2021/08/13][짤막한 이야기 - 구간합(응용)] 앞선 포스트에서 구간합에 대한 이야기를 했다. 구간합은 미리 합배열(SumA)을 생성하여 구간합 연산 속도를 O(N)에서 O(1)로 낮출 수 있다. 그러므로 기존에는 O(N*Q)(N은 데이터 개수, Q는 질문 개수)였던 시간복잡도가 O(Q) 수준으로 낮출 수 있었다. 그런데 만약 A 배열내의 숫자가 변경될 수 있다면 어떻게 될까? Q에 단순히 구간합을 묻는 질문의 개수가 아니라 A 배열내의 특정 위치의 숫자를 다른 값으로 바꾸는 연산도 포함되어 있다면 이야기가 달라진다. 예를 들어 A[1]의 값을 5에서 7로 바꾼다면 SumA를 모두 업데이트해야 하기 때문이다. A[1]을 업데이트하면 SumA는 1 ~ 9까지 모두 업데이트해야하기 때문에 최악의 경..

[2021/08/11][짤막한 이야기 - 구간합] “구간합(Prefix Sum)”이란 자료구조에 나열된 숫자들 중 일부 구간에 대하여 합을 구하는 방법이다. 예를 들어, 위 그림에서 A 배열의 2~4번째 구간합을 물어본다면 10(=7+2+1)을 답하면 되는 것이다. 최악의 경우에도 자료구조 내 모든 데이터를 1번씩만 확인하며 합을 더해나가면 되기 때문에 10의 시간을 초과하지 않는다. 그런데 질문의 개수가 많아지면 이야기는 달라진다. 자료구조의 데이터 개수(N)가 10개이지만 질문의 개수(Q)가 1억개가 주어진다면, 최악의 경우 10억(N*Q)만큼의 시간이 소요되는 것이다. 이 경우는 약 10초가 소요된다. 만약 데이터 개수가 최대 1만개이고 질문의 개수가 최대 10만개인 경우에도 10초보다 적게 소요될..

[2021/08/10][짤막한 이야기 - 영지식증명(응용)] “영지식증명”은 대화형(Interactive) 성질을 가지고 있으며, 이에 따라 많은 대화를 교환해야함을 한계점으로 지적한 바 있다(너무 오래전에 포스팅했지만..). 영지식증명에 "비대화형(Non-Interactive)" 성질을 추가하여야 한 쪽("증명자" 혹은 "검증자")의 연결이 끊어져도 증명 프로토콜의 수행이 가능하다. ”앨리스(Alice)”가 “밥(Bob)”에게 Y(=G^X)에서의 X값을 알고 있음을 증명하고 싶다. 1) 앨리스는 T (=G^V, V는 랜덤값)를 밥에게 송신한다. 2) 밥은 앨리스에게 랜덤값 C를 송신한다. 3) 앨리스는 C를 이용하여 R (=V-C*X)을 계산하여 밥에게 회신한다. 4) 밥은 T가 (G^R)*(Y^C)와..

[2021/08/09][짤막한 이야기 - 핀툴 생성] “핀툴(PinTool)”은 “핀(Pin)”을 이용하여 생성할 수 있는 DBI 도구이다. 핀은 구글에서 “Pin DBI”를 검색하여 공식 홈페이지에서 다운로드 받을 수 있다. 일부 핀툴과 관련된 블로그나 카페에서는 핀툴을 생성하기 위하여 “시그윈(CygWin)”을 설치하라는 안내가 많이 있지만, 실제로는 그럴 필요가 전혀 없다. 시그윈 자체가 10GB 이상이기 때문에 핀툴 생성을 위한 시그윈 설치는 매우 비추천하기 때문이다. 대신 “Microsoft Visual Studio 2019 Community(무료)”를 설치하여 핀툴을 생성하는 것을 추천한다. 다운로드 받은 핀 압축 파일을 압축해제한 후, “source/tools/MyPinTool”의 경로로 들..

[2021/08/05][짤막한 이야기 - 동적 바이너리 계측] “동적 바이너리 계측(Dynamic Binary Instumentation, 이하 DBI)”는 분석 대상 프로그램(=바이너리)이 실행되는 중(=동적)에 분석용 코드를 삽입하여 프로그램을 분석(=계측)하는 기술이다. 즉, DBI 기술은 “역공학” 중에서도 “동적 분석” 기술에 해당된다. 프로그램 실행 중 분석용 코드를 삽입하기 때문에 분석 대상의 소스코드가 필요하지 않다는 특징이 있다. 대표적으로는 핀툴(PinTool, 루니프[LootNiP]의 모티브)이 DBI 기술을 제공하며, 그 외에도 DynamoRIO, Valgrind, Dyninst 등의 DBI 제공 프레임워크들이 존재한다. 대다수의 소프트웨어 보안 및 소프트웨어 분석 관련 연구는 DB..

[2021/08/04][짤막한 이야기 - 시간 복잡도] “시간 복잡도(Time-Complexity)”란 어떠한 일을 수행하는데 소요되는 대략적인 시간을 의미한다. 그림에는 특정 자료구조(Data Structure, 이 경우에는 배열)에 데이터가 입력되어 있다. 위의 자료구조에는 10개의 데이터가 무작위로 입력되어 있고, 아래의 자료구조에는 10개의 데이터가 정렬된 상태로 입력되어 있다. 위의 자료구조에서 가장 큰 값(9)을 찾기 위해서는 배열을 순차적으로 탐색하게 된다. 최악의 경우 가장 큰 값이 자료구조 내 가장 뒤에 있는 경우 10개의 데이터를 모두 탐색한 후에야 찾을 수 있다. 데이터가 10개가 아닌 1,000,000개(1백만개)라면 그만큼 시간이 더 소요된다. 즉, 데이터의 개수 N만큼 시간이 소..

[2021/08/03][짤막한 이야기 - 유니온 파인드] “유니온 파인드(Union-Find)”이란 어떠한 그룹에서 여러 노드가 존재할 때 임의의 두 노드를 하나의 그룹으로 병합(Union)하고, 임의의 노드가 어떤 그룹에 속하는지 탐색(Find)하기 위한 알고리즘이다. 즉, 병합과 탐색을 주된 연산으로 하며 병합은 2개의 노드 X와 Y의 그룹명을 합치는 역할을, 탐색은 1개의 노드 Z의 그룹명을 출력하는 역할을 한다. 알고리즘 구현 문제에서는 주로 어떤 팀과 어떤 팀이 동맹관계인지 확인하거나 할 때에 응용할 수 있다. 특정 그룹을 탐색하기 위한 방법으로는 꼭 “유니온 파인드”를 적용하지 않아도 “전수 조사(Brute Force)”가 가능하지만, 이 경우 높은 확률로 많은 시간이 소요되게 된다. 그림의 ..

[2021/07/26][짤막한 이야기 - 이진 탐색] “이진 탐색(Binary Search)”이란 어떠한 그룹을 탐색할 때 절반으로 나누어가며 탐색하는 기법이다. 일반적으로 정렬이 적용된 자료구조에서 특정한 값을 탐색할 때에 적용하는 탐색 방법을 의미한다. “정렬”은 알고리즘에서도 매우 중요한 개념 중 하나로 다음에 소개할 주제이기도 하다. 예를 들어, 1 ~ 100,000까지의 공간에서 특정한 수(X)를 탐색할 때 중간에 해당하는 인덱스인 50,000번째부터 확인하게 된다. 50,000번째 공간에 저장된 수(Y)가 찾고자 하는 특정한 수와 같다(X = Y)면 정말 행운이지만, 일반적으로는 그렇지 않다. 만약 특정한 수보다 저장된 수가 작은 경우(X > Y)라면 그 공간의 오른쪽을, 반대(X < Y)라면..