<aside> 💡

State coverage가 무엇인지 작성해놓은 페이지

</aside>

State Coverage

• State Coverage는 소프트웨어 테스트, 특히 퍼징(fuzzing)과 같은 테스트 기법에서 시스템이나 프로토콜이 여러 상태로 전이하는 과정을 얼마나 탐색했는지를 측정하는 지표이다. 시스템의 상태는 특정 입력에 의해 달라질 수 있으며, State Coverage는 테스트 중에 얼마나 다양한 상태에 도달했는지, 즉 상태 전이 다이어그램에서 얼마나 많은 상태와 경로를 탐지했는지를 나타낸다. 이는 코드 커버리지와 유사하지만, 프로그램이 아닌 상태 머신의 다양한 상태를 탐색하는 것을 목표로 하여 더 많은 취약점을 발견하는 데 기여할 수 있다.

State Coverage 측정 방법 (AFLnet 기준)

1. 프로토콜 상태 추적 (Protocol State Tracking)

• AFLnet은 프로토콜의 상태 전이(protocol transition)를 추적하기 위해, 상태 머신 모델을 활용한다. 일반적으로 네트워크 프로토콜에는 특정 상태 전이 다이어그램(상태 머신)이 존재하며, 클라이언트와 서버 간의 통신 과정에서 다양한 상태로 전이한다. 예를 들어, 클라이언트가 연결을 요청하면 서버는 연결 상태로 전이하고, 이후 클라이언트의 요청에 따라 다른 상태로 넘어간다.

  AFLnet은 이러한 프로토콜 상태 전이를 추적하여, 각 상태에서 퍼저가 탐색한 상태 정보를 기록한다. 상태는 네트워크 메시지 흐름에 따라 변화하기 때문에, 각 메시지가 프로토콜의 어떤 상태에서 어떤 상태로 전이했는지 추적하는 방식이다.

2. 상태 ID 할당 (State ID Assignment)

• AFLnet은 각 프로토콜 상태에 고유한 ID를 부여한다. 퍼징 중에 클라이언트가 서버에 특정 메시지를 보낼 때, 이 메시지가 서버를 특정 상태로 전이시킬 수 있다. AFLnet은 이러한 상태 전이를 관찰하고, 전이된 상태에 고유한 ID를 할당한다. 이렇게 할당된 상태 ID는 프로토콜의 상태 커버리지 분석에 사용된다.
• 상세

  • AFLnet이 이전에 도달하지 않은 상태를 탐지하는 방법은 주로 상태의 고유 식별 정보를 추적하고, 이전에 기록된 상태들과 비교하는 방식으로 이루어진다. 구체적으로, AFLnet이 새로운 상태에 도달했는지 여부를 알 수 있는 방법은 다음과 같다:

    1. 상태 ID(State ID) 기반 비교

    • AFLnet은 각 상태에 **고유한 상태 ID(State ID)**를 부여합니다. 이 상태 ID는 서버가 클라이언트의 입력에 반응하여 전이한 상태를 나타내며, 상태를 구별하는 기준이 된다.
    • 클라이언트가 서버에 입력을 전송할 때 서버가 어떤 상태로 전이되었는지 확인한 후, 해당 상태의 ID를 AFLnet 내부에 저장된 이전 상태 ID 목록과 비교한다.
      • 만약 새로 도달한 상태의 ID가 목록에 존재하지 않는다면, 이는 이전에 탐색되지 않은 상태로 간주되고 새로운 상태로 기록된다.
      • 반면, 이미 존재하는 상태 ID일 경우 이는 이전에 도달한 상태로 간주되어 새로운 상태로 처리되지 않는다.

    2. 상태를 구별하는 방식

    상태를 구별하고 고유한 상태 ID를 부여하기 위해 AFLnet은 다양한 방법을 사용한다. 특히 네트워크 프로토콜의 특성에 맞춰 상태를 구별할 수 있는 정보를 추출한다. 예를 들어, FTP와 같은 프로토콜에서는 각 명령어가 서버를 서로 다른 상태로 전이시키는데, AFLnet은 다음과 같은 기준으로 상태를 구별할 수 있다:

    • 응답 메시지 또는 코드 기반 식별:
      • 많은 네트워크 프로토콜은 클라이언트가 명령어를 보낼 때, 서버가 응답 메시지 또는 상태 코드를 반환한다. 예를 들어, FTP에서는 USER 명령을 보내면 서버는 331 User name okay, need password.라는 응답을 반환하고, PASS 명령을 보낸 후에는 230 User logged in.이라는 응답을 반환할 수 있다.
      • AFLnet은 이러한 응답 메시지나 코드의 패턴을 분석하여 서버가 어떤 상태에 있는지를 파악한다. 만약 새로운 종류의 응답을 받았다면, 이는 새로운 상태로 간주될 수 있다.
    • 상태 전이 경로(State Transition Path):
      • 상태는 클라이언트가 보낸 입력의 순서와 서버가 도달한 상태에 따라 다를 수 있다. AFLnet은 클라이언트가 보낸 명령어들의 **전이 경로(Transition Path)**를 추적하여 상태를 구별한다.
      • 예를 들어, 클라이언트가 USER anonymous → PASS guest라는 순서로 명령어를 보냈을 때 서버가 도달한 상태와, USER admin → PASS admin 순서로 명령어를 보냈을 때 도달한 상태는 서로 다를 수 있다. AFLnet은 이러한 경로 정보를 기반으로 새로운 상태에 도달했는지 여부를 결정할 수 있다.
    • 프로그램의 실행 흐름 (Coverage-based Feedback):
      • 상태를 구별하는 또 다른 중요한 방법은 AFLnet이 프로그램의 코드 커버리지를 피드백으로 사용하는 것이다. 즉, 특정 입력이 서버 프로그램에서 새로운 코드 경로 또는 분기점을 탐색했는지 확인한다.
      • 만약 이전에 탐색되지 않은 코드 경로나 분기점을 실행했다면, 이는 새로운 상태로 이어질 가능성이 높기 때문에 새로운 상태로 기록될 수 있다.

    3. 상태 히스토리(State History) 추적

    • AFLnet은 퍼징 과정에서 상태 히스토리를 추적하여 각 상태 전이를 기록한다. 클라이언트가 서버에 어떤 입력을 보냈을 때, 서버가 어떻게 반응하고 어떤 상태로 전이되었는지를 기록하며, 이러한 기록은 퍼저의 내부에서 상태 전이 트리 또는 상태 그래프로 표현된다.
    • 새로운 테스트 케이스가 실행될 때, 현재 상태가 이전에 기록된 상태와 어떻게 다른지를 확인하고, 이 전이 경로에 없는 새로운 상태라면 이를 새로운 상태로 기록한다.

    4. 상태 전이 경로와 변이 전략

    • AFLnet은 상태 커버리지 외에도 **상태 전이 경로(State Transition Path)**를 추적한다. 클라이언트의 명령어 또는 입력 시퀀스가 서버를 어떻게 다양한 상태로 전이시켰는지에 대한 경로 정보를 저장하고, 이를 바탕으로 새롭게 탐색된 상태를 기록한다.
    • 이 과정에서, 이전에 도달한 상태로 이어지는 경로와 달리 새로운 경로를 통해 상태에 도달한 경우도 새로운 상태로 간주할 수 있다.

    예시: FTP 프로토콜에서 새로운 상태 탐지

    • Step 1: 클라이언트가 USER anonymous를 보내면, 서버는 "331 User name okay, need password."라는 응답을 반환하며 상태 2로 전이한다. 이 상태는 AFLnet이 처음으로 도달한 상태이므로 새로운 상태로 기록된다.
    • Step 2: 클라이언트가 PASS guest를 보내면, 서버는 "230 User logged in."이라는 응답을 반환하며 상태 3으로 전이한다. 이 상태도 새로운 상태로 기록된다.
    • Step 3: 클라이언트가 USER admin이라는 새로운 명령어를 보낸다. 서버가 예상치 못한 "530 Permission denied."라는 새로운 응답을 반환한다면, 이는 이전에 도달하지 않았던 상태로 간주되며 새로운 상태로 기록된다.

3. 상태 기반 커버리지 측정 (State-Based Coverage Measurement)

• AFLnet은 각 테스트 케이스가 서버를 어떤 상태로 전이시키는지 기록하고, 이 상태 정보(State ID)를 사용해 상태 커버리지를 계산한다. 상태 커버리지는 다음과 같은 방식으로 활용될 수 있다:

  • 새로운 상태 발견: 이전에 탐색되지 않은 새로운 상태를 발견했는지 여부.
  • 상태 전이 경로 커버리지: 특정 상태에서 다른 상태로 전이하는 다양한 경로를 얼마나 많이 탐색했는지 확인.

  이렇게 기록된 상태 커버리지는 AFLnet의 탐색 효율성을 높이는데 사용된다. 특히, 새롭게 탐색된 상태에 대해 우선순위를 높게 설정하여 해당 상태에서 더 많은 테스트 케이스를 생성하게 한다.

4. 상태 피드백 기반 퍼징 (State Feedback-Based Fuzzing)

• AFLnet은 상태 커버리지를 피드백으로 받아, 퍼징 과정을 최적화한다. 상태 전이 정보를 활용하여, 특정 상태에서 더 많은 테스트 케이스를 생성하거나, 특정 상태로 도달하기 어려운 입력 시퀀스를 우선시하는 방식으로 작동한다. 이를 통해 AFLnet은 단순히 코드 경로만을 탐색하는 것이 아니라, 상태 머신 전반을 깊이 있게 탐색할 수 있다.