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

[2021/09/06][짤막한 이야기 - 최대구간합(개선)] 앞선 포스트에서 최대구간합에 대한 이야기를 하였다. 구간의 길이로 취할 수 있는 모든 경우에서 구간합 배열을 구하고, 그 중에서의 "Max"값을 출력하는 방식이였다. 구간합 배열을 모든 길이에 대하여 비교하기 때문에 O(N^2)의 시간 복잡도를 가졌다. 그러나 지금 제시하는 알고리즘은 동일한 결과를 출력하면서 시간 복잡도가 O(N)으로 개선된다. 이를 "카데인(Kadane)" 알고리즘이라고 한다. 비교 횟수를 효과적으로 줄일 수 있는 아이디어는 "각각의 최대구간합은 이전 최대구간합이 반영되어 있음"을 기반으로 한다. 즉 이전 최대구간합을 알 수 있다면 현재 인덱스에서의 최대구간합은 현재 인덱스의 값을 더함으로써 구할 수 있는 것이다. 정확한 원..

[2021/09/03][짤막한 이야기 - 최대구간합] “최대 연속 부분합(Maximum Contiguous Subsequence Sum, MCSS)” 혹은 통칭 최대구간합은 자료구조 내의 구간합을 구하는 문제이다. 앞선 구간합(Prefix Sum)과는 조금 다르다. 최대구간합은 구간합처럼 “특정 범위의 합을 구하는 문제”가 아니라 “합이 최대가 되는 임의 범위의 합을 구하는 문제”라는 점이다. 따라서, 구간합과는 달리 최대구간합에서는 A배열 내 원소 변경이 없으며, 음수가 포함될 수 있다. 만약 양수만 포함된 배열이라면 전체 구간을 다 포함하는 것이 최대구간합이 될 것이다. 그림의 A배열에서는 A[2] ~ A[9]까지의 합이 14로 최대가 된다. 앞서 포스팅한 구간합 배열을 이용하여 최대구간합을 구할 수..

[2021/09/02][짤막한 이야기 - 인덱스 트리] “인덱스 트리(IndexTree)”는 이진 트리로 구성되는 연산 용이성을 목적으로 하는 자료구조이다. 앞선 포스트에서 구간합을 이야기하면서 구간합을 구하고 싶은 배열 A 내의 숫자가 변경될 수 있는 경우, 합배열을 모두 업데이트해야 할 수 있어 시간 복잡도가 크게 늘어날 수 있다고 하였다. 그러나 인덱스 트리로 부분합을 저장한다면 숫자가 변경되어도 부분합이 변경되어야 하는 횟수가 크게 줄어든다. 즉, 이진 트리(= 인덱스 트리) 내 부분합 업데이트는 O(logN)에 처리되기 때문에 합배열 업데이트가 O(N)으로 처리될 때보다 크게 시간복잡도가 줄어든다. 이 상태에서 A[3] ~ A[8]의 합을 물어보게 된다면 A[3] + A’’[1] + A[8]을 ..

[2021/09/01][짤막한 이야기 - 언패킹(필요성)] 앞서 “패킹된 코드”는 “언패킹 코드”에 의하여 “실행 직전”에 자동으로 언패킹된 후 실행된다고 하였다. 그럼에도 불구하고 미리 언패킹을 해서 파일 형태로 재구성하는 과정이 왜 필요할까? 분석을 용이하게 하는 과정의 목적은 단 하나이다. 악성코드에 해당 보호 기술이 적용될 경우를 우려하는 것이다. 즉, “악성코드”에 “코드 패킹”이 적용될 경우 이의 분석이 어려워지는 것이다. 이 경우 2가지 문제점이 발생한다. 첫번째는 시그니처 훼손에 의한 미탐이다. 악성코드는 특정 바이트열을 포함하거나 특정 해쉬값을 생성한다. 이를 시그니처라고 하는데, 패킹이 된 악성코드는 시그니처가 달라지므로 안티바이러스에서 탐지를 하지 못한다. 두번째는 기능성 은닉에 의한..

[2021/08/31][짤막한 이야기 - 코드 패킹(예시)] “코드 패킹(Code Packing)”이란 소프트웨어 보호 기술 중 하나이며, 코드를 알아볼 수 없도록 변형하는 것이라고 하였다. 그림의 왼쪽이 아벡스크랙미의 “원본 코드”이고 오른쪽이 “패킹된 코드”이다. 패킹은 여러 방식으로 수행될 수 있지만, 예시에서는 가장 단순하게 모든 바이트에 1을 더한다. 0x401000 ~ 0x401050까지의 어셈블리어가 모두 이상하게 해석되는 것을 볼 수 있다. 그러나 CPU에서는 패킹된 코드를 읽어들이면 잘못된 명령어로 강제종료될 가능성이 높다. 따라서 패킹된 코드는 반드시 실행 직전에는 원본 코드로 복원되어야 한다. 실행 직전 자동으로 원본 코드로 복원하는 과정이 “언패킹”이며, 0x401069 ~ 0x40..

[2021/08/30][짤막한 이야기 - 동형 검사] “동형 검사(Isomorphism Test)”란 두 대상의 구조 동일 여부를 검사하는 알고리즘이다. 앞서 동형 검사에는 "순회"가 필요하다고 하였다. 즉 양측 대상의 노드와 노드 속 데이터 값이 동일한지 확인 후 각각 다음 노드로 이동하는 과정이 필요하다. 예를 들어 이진 트리에서의 동형 검사는 다음과 같이 수행되며, 루트(Root) 노드를 시작으로 재귀적으로 들어간다. 1) 두 루트 노드가 둘 다 데이터가 없으면 동형임이 자명하다. 2) 두 루트 노드 중 하나만 데이터가 없으면 이형(Heteromorphism, 형태가 다름)임이 자명하다. 3) 두 루트 노드의 데이터 값이 다르면 이형이다. 4) 두 루트의 좌측 노드를 루트 노드로 가정하여 해당 알고..

[2021/08/29][짤막한 이야기 - 동형] “동형(Isomorphic)”이란 서로 구조가 동일한 두 대상을 의미한다. 즉 간단히 말하면 모양이 동일하다는 의미이다. 자료구조에서는 두 자료구조가 동형인지 판별하는 것도 중요한데, 예를 들어 임의의 두 그래프(Graph)가 동형인지 판별하는 것도 매우 중요하다. 프로그래밍을 접해본 바 있다면, "제어흐름 그래프(Control-Flow Graph)"를 알고 있을 것이다. 임의의 두 프로그램의 제어흐름 그래프가 동일한지 판단하는 것 또한 보안측면에서 중요하기 때문에 많이 연구되고 있다. 그러나 임의의 두 그래프의 동형 여부 판단 문제는 다항시간 내에 풀릴 수 있는지 증명된 것이 아니기 때문에, 무작정 동형 검사를 수행하는 것에는 주의하여야 한다. 그림에서의..

[2021/08/27][짤막한 이야기 - 좌측자식 우측형제] 시작부터 제목이 조금 우스꽝스럽다. “좌측자식 우측형제(Left-Child Right-Sibling)”란 K진 트리를 이진 트리로 변환하는 알고리즘이다. LCRS 이진 트리라고도 한다. K진 트리에서의 분석 방법과 이진 트리에서의 분석 방법이 약간 다르기 때문에 이진 트리로 선처리 후 분석을 진행하는 것이 더 나을 수 있다. 알고리즘 이름에서 알 수 있듯이, 자식 노드는 모두 부모 노드의 좌측에만 존재하기 때문에 얼핏 보면 “편향 트리(Skewed Tree)”와 유사하게 보일 수 있다. 이진 트리로 변환된 K진 트리는 이진 트리의 특성을 가지고 있긴 하지만, 약간의 편향성 때문에 이진 트리와는 조금 다른 특징도 가진다. 예를 들어, 부모 노드(..