Software testing

Black-box testing

• 내부 구조를 모르는 채 수행하는 방식
• 한계 : 내부 로직을 몰라 효율적으로 오류 찾기 어려움

Gray-box testing

• Black-box testing과 White-box testing의 장점을 섞은방식

Fuzzing

• 자동으로 입력값을 만들어 프로그램 테스트하는 방법
• 방식
  • 1) Mutation-based fuzzing : 이미 있는 입력값을 조금씩 바꿔 새로운 입력값을 만듦
    • 순서 : 1. Seed pool generation > 2. Seed Selection > 3. Seed Mutation(Deterministic stage : 규칙적으로 seed 변경, Havoc Stage : 무작위로 큰 변화를 줌)
  • 2) Generation-based fuzzing : 문법을 이용해 새로운 입력값을 만들어냄
• 발전 과정
  • Program-agnostic > Program-adaptive > Seed-adaptive
    • Program-agnostic : 프로그램의 특성 모르고 테스트, 무작위로 값 입력
      • Program-adaptive : 프로그램의 특성에 따라 테스트 전략을 바꾸는 방식(어떤 변형이 더 효과적인지 학습해 적용)
      • Seed-adaptive : 입력값(seed)마다 다르게 변형하는 방식(비슷한 특징 가진 seed끼리 클러스터로 묶고, 각각에 맞는 전략 사용)

APR(Automated Program Repair)

• 프로그램에서 발생한 오류를 자동으로 찾아 고쳐주는 기술
• APR이 필요한 이유
  1. 시간 문제 : 개발 중 50% 이상이 버그 수정에 사용됨
  2. 버그가 계속 증가 : 해마다 전세계 버그 수 증가중
  3. 수동 버그 수정 문제 : 사람이 직접 고치면 오래 걸리고, 실수도 있음
• APR 종류
  • General-Purpose APR
    • 모든 종류의 오류를 고칠 수 있음
      • 장점 : 다양한 종류의 오류를 고칠 수 있음
      • 단점 : 특정 종류의 오류에 대한 정확도가 낮음
  • Special-Purpose APR
    • 특정 오류(Null pointer Exception, 메모리 누수 등)를 전문적으로 고침
      • 장점 : 특정 종류의 오류를 잘 고침
      • 단점 : 특정 종류의 오류에만 사용 가능
• APR 한계
  • Null Pointer Exception(NPE)
    • "null"값을 잘못 처리해 발생하는 오류
      -> 개발자의 의도를 정확히 알기 어려워 자동으로 고치기 힘듦
  • 메모리 할당/해제 오류
    • Double-free : 같은 메모리를 2번 해제하는 경우
    • Memory-leak : 사용한 메모리를 해제하지 않아 자원이 낭비되는 경우
      -> ARP로 고치면 수정률이 낮음
• APR 주요 기술
  • MemFix
    • 메모리 할당/해제를 고치는 기술
    • 정적 분석 사용해 잘못된 메모리 해제 찾아내 고침
  • SAVER
    • 확장 가능한 방식으로 메모리 누수와 관련된 오류 고침
    • 대규모 코드에서도 잘 작동하도록 설계됨

Program Verification

• 프로그램이 정상적으로 작동하는지 수학적/논리적으로 증명하는 방법
• Program verification의 2가지 기본개념
  • Propositional Logic : 참/거짓으로만 표현할 수 있는 논리
  • First-Order Logic : 변수와 조건이 포함된 논리
• Specification
  • 프로그램이 어떻게 돌아가야 하는지 논리적으로 설명한 것
  • Pre-condition
    • 함수 실행 전, 만족해야 하는 조건
  • Post-condition
    • 함수 실행 후, 만족해야 하는 조건
  • Loop Invariant
    • 루프 실행 중 항상 참인 조건
• Partial Correctness & Total Correctness
  • Partial Correctness : 프로그램 종료 시, 결과가 올바른지 확인
  • Total Correctness : 프로그램 종료 하면서도 결과가 올바른지 확인
• Verification Condition(VC) 생성 과정
  (Pre-condition, Post-condition을 기반으로 만들어진 논리식)
  1. 프로그램의 실행경로를 나눔
  2. 각 경로마다 Pre/Post-condition을 계산
  3. SMT Solver를 사용해 모든 조건이 참인지 확인
• Loop Invariant
  • 루프를 분석할 때, 루프 안에서 항상 참이 되는 조건을 찾아야 함
• Linear Search의 Pre/post-condition
  • Pre-condition : 배열의 범위가 유효해야 함
  • Post-condition : 범위[l, u]에서 e가 존재한다면 true 반환