[논문 리뷰/요약] REDQT: a method for automatedmobile application GUI testing basedon deep reinforcement learning algorithms

 

REDQT: a method for automated mobile application GUI testing based on deep reinforcement learning algorithms

---

Abstract

• 이 논문은 심층 강화 학습을 기반으로 자동화된 어플리케이션 테스터를 제안한다.
• 먼저, 기존 모바일 어플리케이션 테스팅 방법들의 한계를 제시하고
• 해당 논문의 제안 방법인 ReqdT를 소개한다.

---

1. Introduction

• 어플리케이션이 진화하면서 GUI도 마찬가지로 복잡해졌다.
• 기존에 제시된 방법들과 그에 따른 한계를 알아보자.

---

• Monkey - Randomly strategized testing tool
  • 랜덤 상호작용을 통해 어플리케이션의 오류를 발견한다.
  • 과한 무작위성 때문에 시간 소비가 크다.
• Model-based testing methods
  • 모델로부터 테스트 시나리오를 생성하는 방법.
  • 특정 시나리오에서 효과적일 수 있으나 포괄적이지 못하다.
• Search-based testing methods
  • 검색 알고리즘을 사용하여 커버리지 등을 평가하는 목표함수를 최적화한다.
• Reinforcement learning models
  • 대부분 강화학습 알고리즘으로 Q-learning 사용.
  • 기존의 Q-table을 DNN으로 교체하면 성능이 더 좋다는 연구 결과를 토대로 Deep reinforcement learning, DRL을
    적용, Q-table은 상당한 양의 메모리 차지하기 때문
  • 하지만 기존에 제안된 DRL기반 방법들은 Overestimation - 특정 행동에 대해 지나치게 높은 보상, 샘플 활용 효율성, 수렴 속도와 같은 문제가 있다.
  • 해당 논문은 Randomized ensembled double Q-learning을 적용한 REDQT를 소개한다.

---

• Major contributions
  • REDQ 알고리즘을 GUI testing에 적용함.
  • 특수한 보상 함수를 구현하여 특정 행동만을 반복하는 현상을 줄임.
  • 가장 높은 coverage rate 달성

---

3. Approach

Workflow of REDQT

• 위 그림은 REDQT의 전체적인 Workflow를 도식화한 것이다.
• Appium으로부터 GUI정보를 습득한 후 현재 환경-Environemt을 구성한다.
• Agent의 Action에 의해 Status가 변하거나 Anomalies가 발견되면 보상을 업데이한다.

---

3.1 Problem formulation

• REDQT는 Markov decision process를 따른다.
  • $Pr(S_{t+1}=s'|S_0, S_1, \cdots,S_{t-1}, S_{t}) =Pr(S_{t+1}=s'|S_t)$
• 이 Framework의 핵심은 상태 가치 함수-state value function $V(s)$ 이다.
  • 주어진 상태 $s$ 에서 특정 정책 $\pi$ 를 수행했을 때 기대되는 누적 보상을 예측하는 함수.
  • $V(s)$ 를 정확하게 추정하는 것이 목표

---

3.1.1 Markov decision process

Markov decision process

 

• 에이전트의 목표는 상호작용으로부터의 학습을 통해 보상을 최대화한다거나, 특정한 작업을 수행하는 것이다.
• MDP에 의해, $t$ 시점의 상태 $S_t$ 와 보상 $R_t$은 $t-1$ 시점의 상태 $S_{t-1}$와 행동 $A_{t-1}$ 에만 영향을 받는다.
• MDP는 튜플 $\langle S, A, P, R \rangle$ 로 표현할 수 있다.
  • $S$ : 모든 가능한 상태-status의 집합
  • $A$ : 에이전트가 선택할 수 있는 모든 가능한 행동-action의 집합
  • $P$ : $\mathit P(s' | s, a)$, 에이전트가 상태 $s$ 에서 행동 $a$ 를 취했을 때 상태 $s'$ 으로 바뀔 확률
  • $R$ : 보상 함수 $R(s, a, s')$, 행동 $a$ 를 통해 상태 $s$ 에서 $s'$ 으로 바뀌었을 때 에이전트가 받는 보상
• 정책($\pi$)이란, 상태 $s$를 행동 $a$로 매핑하는 함수
• 강화학습의 목표는 기대 보상-Expected return을 최대화하는 정책 $\pi$ 를 발견하거나 학습하는 것이다.
  • 기대 보상이란 에이전트가 현재부터 미래까지 일련의 행동을 취했을 때 얻을 수 있는 총 보상을 예측한 값.
  • $G(\tau) = \sum_{t=0}^{\infty} \gamma^tr_t$,
  • $\gamma$ 는 discount facor로, 1이면 expected return은 수렴하지않음
• Application testing task는 다단계 탐색 작업이기 때문에 Q function인 행동 가치 함수:Action-value function와 상태 가치 함수:State-value function로 주어진 상태에서 특정 행동을 하는 것의 장점을 추정한다.
  • Action-value function $Q^{\pi}(s,a)$ : 특정 상태 $s$에서 특정 행동 $a$을 했을 때의 기대 보상
  • State-value function $V^\pi(s)$ : 특정 상태 $s$ 에서 시작해서 정책 $\pi$ 를 따랐을 때의 기대 보상
  • 최적화된 행동 가치 함수와 상태 가치 함수는 다음과 같이 정의된다.
    • $Q^*(s) = E[G_t|s,a]$
    • $V^*(s) = E[G_t|s_0=s]$

---

3.1.2 REDQ based testing

• AC : Actor-Critic 알고리즘
  • Actor Network : 주어진 상태에서 취할 행동의 확률 분포를 출력한다.
  • Critic Network : 가치 함수로부터 주어진 상태와 행동의 가치를 평가하고 최적화한다.
• REDQ : Randomized Ensembled Double Q-learning 알고리즘
  • 다중 Q-function 추정 : 여러개의 Critic Network를 사용해 무작위로 초기화된 여러개의 Q-function을 추정한다.
  • 앙상블-Ensemble : 추정된 여러개의 Q-function을 앙상블하여 학습한다.
  • 여러개의 Q 함수를 추정해서 앙상블하기 때문에 과대편향을 줄일 수 있다.

---

3.2 Representation of stated and actions

• GUI에서 상호작용 가능한 element들을 벡터로 ont-hot encoding한다.
• 현재 인터페이스의 상태 : 상호작용 가능한 위젯들의 집합
  • $s_t = (w_1, w_2,w_3, \cdots, w_n)$
  • $w_i$ 는 클릭, 스크롤, 드래그, 줌, 더블클릭, 엣지 스와이프 등

---

3.3 Reward function

Reward function in REDQT

• $R_1$ : 1000 : 새로운 상태에 도달하거나 crash가 발생했을 때 부여하는 보상
• $R_2$ : 500 : 이미 도달한 상태이나 새로운 위젯과 상호작용 했을 때 부여하는 보상
• $k\ tanh(x-n)$, $k=-500,n=3$ : stagnant-정체된 경우 음의 보상, 탈출한 경우 양의 보상 부여
• $-R_3$ : -50 : 이미 방문한 상태에서 이전에 사용했던 위젯과 상호작용했을 때 부여하는 보상
• $-R_4$ : -100 : 어플리케이션에서 벗어난 상태일 경우 부여하는 보상

3.3 보상 기능