CodeQL 사용법 (이론편)

[ 들어가기에 앞서.. ]

CodeQL 사용법에 대한 적절한 레퍼런스가 따로 없어, 익히는 데에 애를 많이 먹었다. 남들은 삽질을 덜 했으면 좋겠다는 생각에 정리한다.

[ Intro ]

CodeQL은 Variant Analysis를 수행하는 정적 분석 도구이다. CodeQL에서는 code를 데이터 취급하며, 취약점을 포함한 버그 채턴들을 code로부터 만들어낸 DB에서 실행할 수 있는 쿼리로 정형화해서 이용한다.

Variant Analysis란 알려진 취약점을 기준 삼아 비슷한 유형의 취약점을 찾아내는 분석 방법이다. CodeQL은 취약점을 쿼리화할 수 있어 Variant Analysis 분석에 효율적이다. 또한 새로운 유형의 취약점을 찾기 위해 직접 쿼리화할 수 있다.

[ Internal ]

CodeQL이 내부적으로 동작하는 과정을 보면 아래와 같다.

대상 code를 데이터화하여 CodeQL Database를 생성
만들어진 CodeQL Database를 대상으로 CodeQL 쿼리로 질의
쿼리 결과 분석

[ Create CodeQL Database ]

CodeQL Database 생성 과정은 아래와 같다.

Init : CodeQL Database 디렉토리 구조를 생성
- codeql database init
Extraction : Target Code로부터 관계를 추출
- codeql database trace-command
Finalize : 생성된 모든 관계 표현들을 import하여 하나의 Database로 만듬
- codeql database finalize

위 과정은 codeql database create 명령어를 통해 한번에 수행 가능하다.

CodeQL이 Database를 생성할 때, 제일 먼저 하는 일은 code 파일들로부터 관계를 추출하는 것이다. class, function, params, variable, expression, statement 등 다양한 정보들이 추출되고 관계 표현으로 만들어 저장된다. 이러한 과정을 수행하는 프로세서를 extractor라 하며, CodeQL에서 지원하는 각자 언어마다 하나의 extactor를 가지고 있다.

CodeQL을 실행했을 때 볼 수 있는 빌드 모니터링 과정이다. 리눅스 커널을 예시로 CodeQL Database를 만드는 과정이 아래와 같다.

# codeql database creating history
...
[2021-04-30 10:17:24] [build-stdout]   CC      arch/x86/entry/syscall_32.o
[2021-04-30 10:17:25] [build-stdout]   AR      arch/x86/entry/built-in.a
[2021-04-30 10:17:25] [build-stdout]   CC      arch/x86/events/amd/core.o
[2021-04-30 10:17:26] [build-stdout]   CC      arch/x86/events/amd/uncore.o
[2021-04-30 10:17:27] [build-stdout]   CC      arch/x86/events/amd/ibs.o
[2021-04-30 10:17:28] [build-stdout]   CC      arch/x86/events/amd/iommu.o
[2021-04-30 10:17:29] [build-stdout]   AR      arch/x86/events/amd/built-in.a
[2021-04-30 10:17:29] [build-stdout]   CC      arch/x86/events/intel/core.o
[2021-04-30 10:17:31] [build-stdout]   CC      arch/x86/events/intel/bts.o
...

모니터링으로 수집된 code들은 AST로 표현되며, 관계 정보로 전환되어 저장된다. 이때 관계 정보들이 저장된 파일을 trap이라고 하며, 나중에 Finalize 과정에서 이 정보들을 병합하는 과정을 거치게 된다.

trap에 저장된 관계 정보는 아래와 같이 key-data의 튜플 형태로 정의되어 있다. 각 관계 정보 속에서 상속과 참조를 모두 표현할 수 있다.

#key=information
data(key, ...)

아래 튜플은 tty_buffer_cancel_work()에서 추출한 관계 정보들을 표현한 것이다.

핵심만 말하면 #17f에 해당하는 키 정보가 functions(#17f, "tty_bufffer_cancel_work", 1)을 통해 함수라는 것을 알 수 있다. function_return_type(#17f, #122)을 가지고 해당 함수의 return type이 boolean형이라는 것을 추측할 수 있다.

...
#122=@"type_def_bool_{#123}"
...
function_entry_point(#169, #16e)
.pop
numlines(#169, 4, 4, 0)
#17f=@"fun_decl_tty_buffer_cancel_work(?)"
 .implementation ".../linux-5.11.11/drivers/tty/tty_buffer.c[00000000];lib_linux_x86_64"
.push *
functions(#17f, "tty_buffer_cancel_work", 1)
link_parent(#17f, #11d)
function_return_type(#17f, #122)
#17f_180=@"{#17f}_0_par"
params(#17f_180, #17f, 0, #16c)
...

추출 이후 Finalize 과정에서 trap 정보들을 모두 병합(import)함으로써 하나의 Database로 만들게 된다. 그리고 생성된 database, code, database schema를 한 디렉토리에 넣는다. 이를 Snapshot이라 하며 CodeQL Query를 통해 질의를 할 수 있다.

codeql-database.yml  db-cpp  log  src.zip

database schema는 관계들의 스키마 타입을 정의하며 extractor가 이를 바탕으로 관계를 생성하고 올바르지 않은 관계 타입이 있는 지 검증하는 과정을 거친다. 또한 Query 과정에서 CodeQL이 가지고 있는 Schema와 Snapshot 안 Schema가 동일한 지 검증한다. 이는 대게 CodeQL이 업데이트 되면서 Snapshot을 만들어낼 때의 CodeQL 버전과 쿼리를 실행하는 CodeQL 버전의 스키마가 업데이트 되면서 발생하는 불일치를 방지한다. 아래는 semmlecode.cpp.dbscheme의 일부이다. trap의 튜플 구조에 대한 정의, 정보 간 상속이 정의되어 있으며 추후 이 데이터를 쿼리에 이용하게 된다.

...
/*
  case @function.kind of
    1 = normal
  | 2 = constructor
  | 3 = destructor
  | 4 = conversion
  | 5 = operator
  | 6 = builtin     // GCC built-in functions, e.g. __builtin___memcpy_chk
  ;
*/
functions(
    unique int id: @function,
    string name: string ref,
    int kind: int ref
);
...
function_return_type(int id: @function ref, int return_type: @type ref);
...
// each function has an ordered list of parameters
#keyset[id, type_id]
#keyset[function, index, type_id]
params(
    int id: @parameter,
    int function: @functionorblock ref,
    int index: int ref,
    int type_id: @type ref
);
...
@localscopevariable = @localvariable | @parameter;
...

[ Querying ]

QL은 CodeQL에서 사용하는 객체 지향형 쿼리 언어로 구문은 SQL과 유사하다. 다만 QL의 모든 연산은 논리 연산으로 취급된다. QL의 기본적인 구조는 다음과 같다.

/**
 *
 * Query metadata
 *
 */

import /* ... CodeQL libraries or modules ... */

/* ... Optional, define CodeQL classes and predicates ... */

from /* ... variable declarations ... */
where /* ... logical formula ... */
select /* ... expressions ... */

예시로 QL 라이브러리에서 제공하는 ExecTainted.ql을 이용하여 QL 구조 분석을 해보겠다.

/**
 * @name Uncontrolled data used in OS command
 * @description Using user-supplied data in an OS command, without
 *              neutralizing special elements, can make code vulnerable
 *              to command injection.
 * @kind problem
 * @problem.severity error
 * @precision low
 * @id cpp/command-line-injection
 * @tags security
 *       external/cwe/cwe-078
 *       external/cwe/cwe-088
 */

import cpp
import semmle.code.cpp.security.CommandExecution
import semmle.code.cpp.security.Security
import semmle.code.cpp.security.TaintTracking

from Expr taintedArg, Expr taintSource, string taintCause, string callChain
where
  shellCommand(taintedArg, callChain) and
  tainted(taintSource, taintedArg) and
  isUserInput(taintSource, taintCause)
select taintedArg,
  "This argument to an OS command is derived from $@ and then passed to " + callChain, taintSource,
  "user input (" + taintCause + ")"

가장 먼저 위치하는 구문은 metadata에 대한 정보다. metadata는 VSCode의 CodeQL Extension에서 결과를 표시할 때 사용되지만 없어도 무방한 데이터다.

/**
 * @name Uncontrolled data used in OS command
 * @description Using user-supplied data in an OS command, without
 *              neutralizing special elements, can make code vulnerable
 *              to command injection.
 * @kind problem
 * @problem.severity error
 * @precision low
 * @id cpp/command-line-injection
 * @tags security
 *       external/cwe/cwe-078
 *       external/cwe/cwe-088
 */

다음은 import에 관한 정보다. import는 대상이 되는 언어팩과 사용하려고 하는 모듈들을 import해서 사용합니다.

import cpp
import semmle.code.cpp.security.CommandExecution
import semmle.code.cpp.security.Security
import semmle.code.cpp.security.TaintTracking

import의 대상이 되는 파일들은 QL Library의 의미를 가지고 있는 QLL 확장자이다. QLL은 QL과 달리 연산 구문인 "from", "where", "select" 절이 존재하지 않고 오로지 "predicate", "module", "configuration", "class" 등을 정의하는 쿼리만 존재하고 이를 불러와 이용이 가능하다.

# semmle.code.cpp.security.CommandExecution
...
/**
 * A function for running a command using a command interpreter.
 */
class SystemFunction extends FunctionWithWrappers, ArrayFunction, AliasFunction, SideEffectFunction {
  SystemFunction() {
    hasGlobalOrStdName("system") or // system(command)
    hasGlobalName("popen") or // popen(command, mode)
    // Windows variants
    hasGlobalName("_popen") or // _popen(command, mode)
    hasGlobalName("_wpopen") or // _wpopen(command, mode)
    hasGlobalName("_wsystem") // _wsystem(command)
  }

  override predicate interestingArg(int arg) { arg = 0 }

  override predicate hasArrayWithNullTerminator(int bufParam) { bufParam = 0 or bufParam = 1 }

  override predicate hasArrayInput(int bufParam) { bufParam = 0 or bufParam = 1 }

  override predicate parameterNeverEscapes(int index) { index = 0 or index = 1 }

  override predicate parameterEscapesOnlyViaReturn(int index) { none() }

  override predicate parameterIsAlwaysReturned(int index) { none() }

  override predicate hasOnlySpecificReadSideEffects() { any() }

  override predicate hasOnlySpecificWriteSideEffects() {
    hasGlobalOrStdName("system") or
    hasGlobalName("_wsystem")
  }

  override predicate hasSpecificReadSideEffect(ParameterIndex i, boolean buffer) {
    (i = 0 or i = 1) and
    buffer = true
  }
}
...

# semmle.code.cpp.security.TaintTracking
...
/**
 * A predictable instruction is one where an external user can predict
 * the value. For example, a literal in the source code is considered
 * predictable.
 */
private predicate predictableInstruction(Instruction instr) {
  instr instanceof ConstantInstruction
  or
  instr instanceof StringConstantInstruction
  or
  // This could be a conversion on a string literal
  predictableInstruction(instr.(UnaryInstruction).getUnary())
}
...

다음 "from", "where", "select" 구문은 SQL 형태와 비슷하며, where 조건에서 정의된 표현식들을 결과로 출력하게 된다.

from Expr taintedArg, Expr taintSource, string taintCause, string callChain
where
  shellCommand(taintedArg, callChain) and
  tainted(taintSource, taintedArg) and
  isUserInput(taintSource, taintCause)
select taintedArg,
  "This argument to an OS command is derived from $@ and then passed to " + callChain, taintSource,
  "user input (" + taintCause + ")"

위 코드에서 Expr 말고도 Function, Functioncall, Variable 등 QL에서 사용 가능한 데이터 타입 클래스를 QL Class로 지칭한다. QL Class는 내부적으로 사용 가능한 멤버 함수들과 상속 정보를 가지고 있다.

class Expr extends StmtParent, @expr {
  /** Gets the nth child of this expression. */
  Expr getChild(int n) { exprparents(unresolveElement(result), n, underlyingElement(this)) }

  /** Gets the number of direct children of this expression. */
  int getNumChild() { result = count(this.getAChild()) }

  /** Holds if e is the nth child of this expression. */
  predicate hasChild(Expr e, int n) { e = this.getChild(n) }

  /** Gets the enclosing function of this expression, if any. */
  Function getEnclosingFunction() { result = exprEnclosingElement(this) }

  /** Gets the nearest enclosing set of curly braces around this expression in the source, if any. */
  BlockStmt getEnclosingBlock() { result = getEnclosingStmt().getEnclosingBlock() }

  override Stmt getEnclosingStmt() {
    result = this.getParent().(Expr).getEnclosingStmt()
    or
    result = this.getParent().(Stmt)
    or
    exists(Expr other | result = other.getEnclosingStmt() and other.getConversion() = this)
    or
    exists(DeclStmt d, LocalVariable v |
      d.getADeclaration() = v and v.getInitializer().getExpr() = this and result = d
    )
    or
    exists(ConditionDeclExpr cde, LocalVariable v |
      cde.getVariable() = v and
      v.getInitializer().getExpr() = this and
      result = cde.getEnclosingStmt()
    )
  }
	...

아래 예시의 Function QL Class를 살펴보게 되면 @function으로부터 상속된 것을 확인할 수 있다. 이는 @function id(key)를 가지고 있는 모든 데이터를 정의한다는 의미이며, getName() 함수에서 스키마에 정의된 functions() 튜플을 이용해 원하는 데이터를 반환하는 것을 볼 수 있다.

class Function extends Declaration, ControlFlowNode, AccessHolder, @function {
  override string getName() { functions(underlyingElement(this), result, _) }
...

functions(
    unique int id: @function,
    string name: string ref,
    int kind: int ref
);

결과적으로 QL Class를 데이터 타입으로 이용하기 때문에, 조건에 부합하는 데이터를 찾기 쉽고, 복잡한 조건 또한 연산을 통해 해결할 수 있다. 하지만, 조건이 복잡해질 수록 연산량이 많아져 분석 시간이 늘어난다. 또한 CodeQL에서 중요하게 이용되는 Taint의 경우 코드, 데이터 간 CFG, DF를 모두 연산하므로 속도가 느리다.

Reference

1. https://core-research-team.github.io/2021-05-01/Finding-bugs-with-CodeQL-Part-1#

2. https://github.blog/news-insights/product-news/the-next-step-for-lgtm-com-github-code-scanning/

3. https://codeql.github.com/docs/codeql-overview/about-codeql/

4. https://codeql.github.com/docs/ql-language-reference/about-the-ql-language/

5. https://codeql.github.com/docs/ql-language-reference/ql-language-specification/

저작자표시 비영리 변경금지

[ 들어가기에 앞서.. ]

[ Intro ]

[ Internal ]

[ Create CodeQL Database ]

[ Querying ]

티스토리툴바