Recently, as cyber-attacks are getting more sophisticated and stealthier, doing good post-mortem analysis have also become important. Dependency graph, one of promising cyber incident analysis methods, is drawn to describe what acts were done on the target system by analyzing system audit logs. Since system audit logs are coarse-grained, we consider an event is relevant to all previous events. As a result, dependency graphs suffer from dependency explosion problem. Furthermore, since system audit logs do not log inter process communication (IPC), if information flows through an IPC, the actual dependency relation may be omitted. In this thesis, we attach information flow analysis results to corresponding dependency graph to solve these problems. Subgraph isomorphism algorithm is used to match the information flow analysis result with the dependency graph. This algorithm belongs to NP-complete and is well-known for its big time complexity. We present a typed subgraph isomorphic algorithm that is specialized for
dependency graphs. Experiments with one directly proposed scenario and two scenarios of the DARPA Transparent Computing program confirmed that our tool can draw more concise and accurate dependency graph compared to previous
studies.
최근 사이버 공격들이 고도화, 지능화되어감에 따라 기업이나 기관들은 모든 공격을 원천적으로 막아내기보다는 빠른 공격 탐지, 사후 분석을 잘하는 것을 주 목표로 삼게 되었다. 사후 분석을 위해 시스템 감시 로그를 이용해 대상 시스템에서 어떠한 일들이 있었는지를 분석해 그래프로 그린 것을 의존성 그래프라고 한다. 의존성 그래프는 시스템 감시 로그를 이용해 그리게 되는데, 이 로그가 세밀하지 못해 어떤 이벤트가 정확히 어떤 이벤트들과 의존 관계가 있는지 알지 못한다. 따라서 우리는 의존성 그래프를 그릴 때, 이벤트와 직접 연관이 있는 이벤트뿐만 아니라 같은 프로세스의 모든 이벤트를 탐색 큐에 추가하게 된다. 따라서 의존관계가 없는 파일도 의존성 그래프에 추가되고, 그 파일에 대한 탐색도 재귀적으로 진행하게 된다. 이러면 탐색을 거듭할수록 그래프의 크기가 기하급수적으로 커지는데, 이것을 의존성 폭발이라고 한다. 의존성 폭발 문제 때문에 공격 흐름을 묘사하려고 그린 의존성 그래프의 유용함이 떨어지게 된다. 또한, 감시 로그는 성능 저하를 최소화하기 위해 프로세스 간 통신 이벤트는 기록하지 않는데, 의존성 그래프가 그런 의존 관계를 나타내지 못해 중요한 공격 흐름을 놓칠 수도 있다. 본 학위논문에서는 프로그램의 정보흐름분석 결과를 의존성 그래프를 그릴 때 활용할 수 있게 그 결과를 실행 흐름에 따라 기술할 방법을 제안한 뒤, 의존성 그래프를 그릴 때 활용하여 의존성 그래프에서 필요
없는 부분은 제거하고, 프로세스 간 통신 때문에 의존성 그래프에서 빠진 부분은 복원하는 도구를 소개한다. 또한, 의존성 그래프와 프로그램 분석 정보를 대응시키기 위해 시간 복잡도가 큰 부분 그래프 동형 알고리즘을 사용하는데, 이를 의존성 그래프에 맞춰 최적화하는 형식있는 부분 그래프 동형 알고리즘을 제시한다. 직접 제안한 한 개의 시나리오와 DARPA Transparent Computing 프로그램의 두 시나리오를 대상으로 실험한 결과, 기존의 연구 결과보다 더 작고 정확한 의존성 그래프를 그릴 수 있음을 확인했다.
