# Homological Shift Ideals: Macaulay2 Package

Antonino Ficarra  Antonino Ficarra, Department of mathematics and computer
sciences, physics and earth sciences, University of Messina, Viale Ferdinando
Stagno d’Alcontres 31, 98166 Messina, Italy<EMAIL_ADDRESS>
###### Abstract.

We introduce the Macaulay2 package HomologicalShiftIdeals. It allows to
compute the homological shift ideals of a monomial ideal, and to check the
homological shift properties, including having linear resolution, having
linear quotients, or being polymatroidal. The theory behind these concepts is
explained and the main features of the package are presented.

###### Key words and phrases:

monomial ideals, homological shift ideals, linear quotients

###### 2020 Mathematics Subject Classification:

Primary 13F20; Secondary 13F55, 05C70, 05E40.

##  1\. Introduction

Let $S=K[x_{1},\dots,x_{n}]$ be the standard graded polynomial ring with
coefficients in a field $K$. Let $I$ be a monomial ideal of $S$. For a vector
${\bf a}=(a_{1},\dots,a_{n})\in{\mathbb{Z}}_{\geq 0}^{n}$, we set ${\bf
x^{a}}=x_{1}^{a_{1}}\cdots x_{n}^{a_{n}}$. Note that, as a $S$-module, $I$ is
multigraded. Hence, the minimal free resolution of $I$,
${\mathbb{F}}:\cdots\rightarrow F_{i}\rightarrow\cdots\rightarrow
F_{0}\rightarrow I\rightarrow 0$, is naturally multigraded. Thus,
$F_{i}=\bigoplus_{\bf a}S(-{\bf a})^{\beta_{i,{\bf a}}(I)}$ for all $i$, where
$\beta_{i,{\bf a}}(I)$ is a multigraded Betti number. The $i$th homological
shift ideal of $I$ is the monomial ideal defined as

$\textup{HS}_{i}(I)\ =\ ({\bf x^{a}}\ :\ \beta_{i,{\bf a}}(I)\neq 0).$

Homological shift ideals have been introduced in [11], and attracted the
interest of many researchers [1, 2, 3, 5, 6, 7, 8, 12]. The main purpose of
this theory is to understand those properties shared by all homological shift
ideals of a given monomial ideal. We call these properties, the homological
shift properties.

One of the driving motivation in this line of research is the Bandari-Bayati-
Herzog conjecture [11] which asserts that the homological shift ideals of a
polymatroidal are again polymatroidal. This conjecture is widely open.
However, the conjecture was proved by Bayati for squarefree polymatroidal
ideals [1], by Herzog, Moradi, Rahimbeigi and Zhu for polymatroidal ideals
that satisfy the strong exchange property [11], and by the author and Herzog
for polymatroidal ideals generated in degree 2 [8]. Furthermore, it was shown
by the author in [7, Theorem 2.2] that $\textup{HS}_{1}(I)$ is always
polymatroidal if $I$ is such, pointing towards the validity of the conjecture
in general. This latter result was also recently recovered by Bayati in [2,
Corollary 2.2].

Another interesting conjecture about the homological shifts of powers of the
cover ideals of Cohen–Macaulay very well-covered graphs was recently
formulated in [5, 6] and proved in some special cases, including bipartite and
whisker graphs.

In the present paper, we illustrate and explain how to use the Macaulay2 [9]
package HomologicalShiftIdeals. In Section 2 the mathematical background
needed to develop some of the algorithms of the package is explained. In
Section 3, some examples are presented, illustrating how to use the functions
of the package.

##  2\. Mathematical background

Let $S=K[x_{1},\dots,x_{n}]$ be the standard graded polynomial ring over a
field $K$. We set ${\bf x^{a}}=x_{1}^{a_{1}}\cdots x_{n}^{a_{n}}$ for ${\bf
a}=(a_{1},\dots,a_{n})\in{\mathbb{Z}}_{\geq 0}^{n}$. The vector ${\bf a}$ is
called the multidegree of ${\bf x^{a}}$, whereas $\deg({\bf
x^{a}})=a_{1}+a_{2}+\dots+a_{n}$ is its degree.

Let $I$ be a monomial ideal of $S$. Since $I$ is multigraded, the minimal free
resolution is multigraded as well, say

${\mathbb{F}}\ :\ \ \ \cdots\rightarrow F_{i}\rightarrow\cdots\rightarrow
F_{0}\rightarrow I\rightarrow 0,$

where $F_{i}=\bigoplus_{\bf a}S(-{\bf a})^{\beta_{i,{\bf a}}(I)}$ for all $i$,
and where $\beta_{i,{\bf a}}(I)$ is the $(i,{\bf a})$th multigraded Betti
number of $I$. The vectors ${\bf a}\in{\mathbb{Z}}^{n}_{\geq 0}$ such that
$\beta_{i,{\bf a}}(I)\neq 0$ are called the $i$th multigraded shifts of $I$.
The projective dimension of $I$ is defined as the integer
$\operatorname{pd}(I)=\max\\{i:\beta_{i}(I)\neq 0\\}$. Whereas, the
(Castelnuovo–Mumford) regularity of $I$ is the integer
$\operatorname{reg}(I)=\max\\{\deg({\bf x^{a}})-i:\beta_{i,{\bf a}}(I)\neq
0\\}$.

######  Definition 2.1.

The $i$th homological shift ideal of $I$ is the monomial ideal

$\textup{HS}_{i}(I)\ =\ ({\bf x}^{{\bf a}}\ :\ \beta_{i,{\bf a}}(I)\neq 0).$

Note that $\textup{HS}_{0}(I)=I$ and $\textup{HS}_{i}(I)=(0)$ for $i<0$ and
$i>\operatorname{pd}(I)$.

The main purpose of the theory is to determine those properties enjoyed by all
$\textup{HS}_{j}(I)$. We call these properties, the homological shift
properties of $I$.

Let $I\subset S$ be a monomial ideal, and let $G(I)$ be its unique minimal
monomial generating set. The initial degree of $I$ is
$\textup{indeg}(I)=\min\\{\deg(u):u\in G(I)\\}$.

######  Definition 2.2.

Let $I\subset S$ be a monomial ideal, and let $G(I)=\\{u_{1},\dots,u_{m}\\}$.

  1. (a)

$I$ has a linear resolution if $\textup{indeg}(I)=\operatorname{reg}(I)$.

  2. (b)

$I$ has linear quotients if there exists an order $u_{1},\dots,u_{m}$ of
$G(I)$ such that $(u_{1},\dots,u_{k-1}):u_{k}$ is generated by a subset of the
variables for $k=2,\dots,m$. In this case, $u_{1},\dots,u_{m}$ is called an
admissible order of $I$.

  3. (c)

Let $u={\bf x^{a}}=x_{1}^{a_{1}}\cdots x_{n}^{a_{n}}$. The $x_{i}$-degree of
$u$ is the integer $\deg_{x_{i}}(u)=a_{i}$. We say that $I$ is polymatroidal
if $I$ is equigenerated and the exchange property holds: for all $u,v\in G(I)$
and all $i$ with $\deg_{x_{i}}(u)>\deg_{x_{i}}(v)$ there exists $j$ such that
$\deg_{x_{j}}(u)<\deg_{x_{j}}(v)$ and $x_{j}(u/x_{i})\in G(I)$.

If (a), or (b), or (c), is an homological shift property, we say that $I$: has
homological linear resolution, respectively, homological linear quotients,
respectively, is homological polymatroidal.

For an equigenerated monomial ideal $I\subset S$, the following hierarchy
holds:

(c) $\Rightarrow$ (b) $\Rightarrow$ (a).

Before we proceed, we recall some other concepts. The support of a monomial
$u\in S$ is the set $\operatorname{supp}(u)=\\{x_{i}:\deg_{x_{i}}(u)>0\\}$.
Let $I\subset S$ be a monomial ideal. The support of $I$ is the set
$\operatorname{supp}(I)=\bigcup_{u\in G(I)}\operatorname{supp}(u)$. We say
that $I$ is fully supported (in $S$) if
$\operatorname{supp}(I)=\\{x_{1},\dots,x_{n}\\}$. The bounding multidegree of
$I$ is the vector
$\textbf{deg}(I)=(\deg_{x_{1}}(I),\dots,\deg_{x_{n}}(I))\in{\mathbb{Z}}^{n}$,
defined by

$\deg_{x_{i}}(I)\ =\ \max_{u\in G(I)}\deg_{x_{i}}(u).$

Furthermore, the socle $\textup{soc}(I)$ of a monomial ideal $I\subset S$ is
the set of monomials of $(I:\mathfrak{m})\setminus I$, where
$\mathfrak{m}=(x_{1},\dots,x_{n})$. In other words, $\textup{soc}(I)$ is the
set of all monomials $v$ such that $v\notin I$ and $x_{i}v\in I$, for
$i=1,\dots,n$.

The purpose of the package HomologicalShiftIdeals is to provide the tools to
manipulate and calculate the homological shift ideals of a monomial ideal $I$
and to determine the homological shift properties of $I$. The next table
collects the functions available in the package and their use. $I\subset S$
denotes a monomial ideal, ${\bf a}$ an integral vector, ${\bf x^{a}}$ a
monomial, $i$ an integer and $L$ a list of monomials.

Functions | Description
---|---
supportIdeal$(I)$ |  Computes $\operatorname{supp}(I)$
isFullySupported$(I)$ |  Checks whether $I$ is fully supported (in $S$)
toMonomial$(S,{\bf a})$ |  Computes the monomial ${\bf x^{a}}$ if ${\bf a}\in{\mathbb{Z}}^{n}_{\geq 0}$
toMultidegree$({\bf x^{a}})$ |  Computes the multidegree ${\bf a}$ of ${\bf x^{a}}$
boundingMultidegree$(I)$ |  Computes $\textbf{deg}(I)$
multigradedShifts$(I,i)$ |  Computes the $i$th multigraded shifts of $I$
HS$(I,i)$ |  Computes $\textup{HS}_{i}(I)$
socle$(I)$ |  Computes $\textup{soc}(I)$
hasLinearResolution$(I)$ |  Checks if $I$ has a linear resolution
hasHomologicalLinearResolution$(I)$ |  Checks if $I$ has homological linear resolution
hasLinearQuotients$(I)$ |  Checks if $I$ has linear quotients
hasHomologicalLinearQuotients$(I)$ |  Checks if $I$ has homological linear quotients
admissibleOrder$(I)$ |  Determines an admissible order of $I$
isAdmissibleOrder$(I,L)$ |  Checks if $L$ is an admissible order of $I$
isPolymatroidal$(I)$ |  Checks if $I$ is polymatroidal
isHomologicalPolymatroidal$(I)$ |  Checks if $I$ is homological polymatroidal
Table 1. List of the functions of HomologicalShiftIdeals.

In the remaining part of this section, we explain the theory behind some of
the algorithms used in the package. Given $n\in\mathbb{N}$, we set
$[n]=\\{1,\dots,n\\}$. For a nonempty subset $A$ of $[n]$, we set ${\bf
x}_{A}=\prod_{i\in A}x_{i}$.

We start with the function socle.

######  Proposition 2.3.

[11, Proposition 1.13] Let $I\subset S$ be a monomial ideal. Then

$\textup{soc}(I)\ =\ \\{{\bf x^{a}}\ :\ {\bf
x^{a}}\in(I:{\mathfrak{m}})\setminus I\\}.$

In particular, $\beta_{n-1,{\bf a}}(I)\neq 0$ if and only if ${\bf x^{a}}/{\bf
x}_{[n]}\in\textup{soc}(I)$.

The previous result justifies the following algorithm that calculates
socle$(I)$.

  1.     1. Step 1:

Compute $M=$ multigradedShifts$(I,n-1)$.

    2. Step 2:

Compute $\textup{soc}(I)=\\{w/(x_{1}x_{2}\cdots x_{n}):w\in M\\}$.

Next, we discuss the functions hasLinearQuotients and admissibleOrder. For
their implementations, we have imported the packages SimplicialComplexes, and
SimplicialDecomposability. These packages use the Alexander duality theory in
a fruitful way [4].

A simplicial complex on the vertex set $[n]$ is a family of subsets of $[n]$
such that

  1. -

$\\{i\\}\in\Delta$ for all $i\in[n]$, and

  2. -

if $F\subseteq[n]$ and $G\subseteq F$, we have $G\in\Delta$.

The dimension of $\Delta$ is the number $d=\max\\{|F|-1:F\in\Delta\\}$. Any
$F\in\Delta$ is called a face and $|F|-1$ is the dimension of $F$. A facet of
$\Delta$ is a maximal face with respect to the inclusion. The set of facets of
$\Delta$ is denoted by $\mathcal{F}(\Delta)=\\{F_{1},\dots,F_{m}\\}$. In this
case we write $\Delta=\langle F_{1},\dots,F_{m}\rangle$ and say that
$F_{1},\dots,F_{m}$ generates $\Delta$. We say that $\Delta$ is pure of
dimension $d$ if all facets of $\Delta$ have dimension $d$. The Alexander dual
of $\Delta$ is the simplicial complex (see [10, Lemma 1.5.2]) defined by

$\Delta^{\vee}\ =\ \\{[n]\setminus F\ :\ F\notin\Delta\\}.$

A monomial $u\in S$ is squarefree if $\deg_{x_{i}}(u)\leq 1$, for all
$i\in[n]$. A monomial ideal $I\subset S$ is squarefree if each $u\in G(I)$ is
squarefree. It is well known that for any squarefree ideal $I\subset S$ there
exists a unique simplicial complex $\Delta$ on $[n]$ such that $I=I_{\Delta}$,
where $I_{\Delta}=({\bf x}_{F}:F\subseteq[n],F\notin\Delta)$ is the
Stanley–Reisner ideal of $\Delta$ [10].

Now, we establish the connection between squarefree monomial ideals with
linear quotients and the shellability of simplicial complexes. Recall that
$\Delta$ is shellable if there exists an order $F_{1},F_{2},\dots,F_{m}$ of
its facets $\mathcal{F}(\Delta)$ such that

$\langle F_{1},\dots,F_{k-1}\rangle\cap\langle F_{k}\rangle$

is pure of dimension $\dim(F_{k})-1$ for $k=2,\dots,m$. Any order of the
facets of $\Delta$ satisfying the conditions above is called a shelling order
of $\Delta$. The following result shows that admissible orders and shelling
orders are essentially the same thing.

######  Theorem 2.4.

[10, Proposition 8.2.5] The following conditions are equivalent.

  1. (a)

$I_{\Delta}$ has linear quotients.

  2. (b)

The Alexander dual $\Delta^{\vee}$ of $\Delta$ is shellable.

Furthermore, $F_{1},\dots,F_{m}$ is a shelling order of the Alexander dual
$\Delta^{\vee}$ of $\Delta$, if and only if, ${\bf x}_{[n]\setminus
F_{1}},\dots,{\bf x}_{[n]\setminus F_{m}}$ is an admissible order of
$I_{\Delta}$.

The previous theorem provides an algorithm to determine an admissible order of
a squarefree monomial ideal with linear quotients. In order to extend the
above result to all (non necessarily squarefree) monomial ideals we use
polarization.

Let $u={\bf x^{a}}$ be a monomial of $S$. The polarization of $u$ is the
monomial

$u^{\wp}\ =\ \prod_{i=1}^{n}(\prod_{j=1}^{a_{i}}x_{i,j})\ =\
\prod\limits_{\begin{subarray}{c}i=1,\dots,n\\\
a_{i}>0\end{subarray}}x_{i,1}x_{i,2}\cdots x_{i,a_{i}}.$

Let $S^{\wp}=K[x_{i,j}:i\in[n],j\in[\deg_{x_{i}}(I)]]$. The polarization of
$I$ is the monomial ideal $I^{\wp}\subset S^{\wp}$ with minimal generating set
$G(I^{\wp})=\\{u^{\wp}:u\in G(I)\\}$.

The following lemma, taken from [5, Lemma 4.10], is pivotal.

######  Lemma 2.5.

Let $I\subset S$ be a monomial ideal with $G(I)=\\{u_{1},\dots,u_{m}\\}$ and
having linear quotients. Then, $u_{1},\dots,u_{m}$ is an admissible order of
$I$ if and only if $u_{1}^{\wp},\dots,u_{m}^{\wp}$ is an admissible order of
$I^{\wp}$. In particular, $I$ has linear quotients if and only if $I^{\wp}$
has linear quotients.

Theorem 2.4 and Lemma 2.5 justify the next algorithm for hasLinearQuotients,
that determines whether a monomial ideal has linear quotients or not.

  1.     1. Step 1:

Compute $I^{\wp}$.

    2. Step 2:

Using SimplicialComplexes compute the Alexander dual $\Delta^{\vee}$, where
$I^{\wp}=I_{\Delta}$.

    3. Step 3:

Using SimplicialDecomposability determine if $\Delta^{\vee}$ is shellable. If
the answer is yes then hasLinearQuotients$(I)=$ true, otherwise $=$ false.

For the function admissibleOrder as above we begin with Step 1, 2 and 3. If
hasLinearQuotients$(I)=$ false, then $I$ does not have linear quotients.
Otherwise, we complete our algorithm with the next two steps.

  1.     1. Step 4:

Using SimplicialDecomposability compute a shelling order $F_{1},\dots,F_{m}$
of the Alexander dual $\Delta^{\vee}$, where $I_{\Delta}=I^{\wp}$.

    2. Step 5:

Determine the associated admissible order $u_{1}^{\wp},\dots,u_{m}^{\wp}$ of
$I^{\wp}$ and depolarize it (by the substitutions $x_{i,j}\mapsto x_{i}$ for
all $i$ and $j$) to obtain an admissible order of $I$.

##  3\. Examples

In this final section, we present some examples to illustrate how to use the
package.

Let
$I=(abd,abf,ace,adc,aef,bde,bcf,bce,cdf,def)\subset{\mathbb{Q}}[a,\dots,f]$.
Using the package we can check that $I$ has linear resolution but not linear
quotients as follows.

ii1: S = QQ[a..f];

ii2: I = ideal(a*b*d, a*b*f, a*c*e, a*d*c, a*e*f, b*d*e, b*c*f,

ii2: b*c*e, c*d*f, d*e*f);

ii3: loadPackage "HomologicalShiftIdeals"

ii4: hasLinearResolution I

io4: true

ii5: hasLinearQuotients I

io5: false

In [8, Theorem 1.4] we proved that for any monomial ideal generated in a
single degree and having linear quotients, then $\textup{HS}_{1}(I)$ has
linear quotients as well. However, the higher homological shift ideals of $I$
may fail to have linear quotients.

Consider the ideal $J=(ab,ac,ad,de,df)$ of $S={\mathbb{Q}}[a,\dots,f]$. Then
$J$ has linear resolution, indeed it has linear quotients, and
$\textup{HS}_{1}(J)$ has linear quotients as well. However,
$\textup{HS}_{2}(J)$ does not have linear quotients, not even linear
resolution.

ii6: J = ideal(a*b, a*c, a*d, d*e, d*f);

ii7: HS(J,0)==J

io7: true

ii8: HS(J,1)

io8: ideal(a*b*c, a*b*d, a*c*d, a*d*e, a*d*f, d*e*f)

ii9: hasLinearQuotients HS(J,1)

io9: true

i10: HS(J,2)

o10: ideal(a*b*c*d, a*d*e*f)

i11: hasLinearResolution HS(J,2)

o11: false

Consider the principal Borel ideal $I=B(x_{2}^{2}x_{3})$ of
$S={\mathbb{Q}}[x_{1},x_{2},x_{3}]$. Then
$I=(x_{1}^{3},x_{1}^{2}x_{2},x_{1}^{2}x_{3},x_{1}x_{2}^{2},x_{1}x_{2}x_{3},x_{2}^{3},x_{2}^{2}x_{3})$
has homological linear quotients, indeed $I$ is even homological
polymatroidal, see [3, Theorem 3.4].

`i12: S = QQ[x_1..x_3];`

`i13: I = ideal(x_1^3, x_1^2*x_2, x_1^2*x_3, x_1*x_2^2, x_1*x_2*x_3, `

i13: ,,,,`x_2^3, x_2^2*x_3);`

`i14: hasHomologicalLinearQuotients I`

`o14: true`

`i15: admissibleOrder HS(I,2)`

`o15: {x_1^3*x_2*x_3, x_1^2*x_2^2*x_3, x_1*x_2^3*x_3}`

`i16: socle I`

`o16: {x_1^2, x_1*x_2, x_2^2}`

`i17: isHomologicalPolymatroidal I`

`o17: true`

## References

  * [1] S. Bayati, Multigraded shifts of matroidal ideals, Arch. Math., (Basel) 111 (2018), no. 3, 239–246.
  * [2] S. Bayati, A Quasi-additive Property of Homological Shift Ideals. Bulletin of the Malaysian Mathematical Sciences Society, 2023, 46(3), p.111.
  * [3] S. Bayati, I. Jahani, N. Taghipour, Linear quotients and multigraded shifts of Borel ideals, Bull. Aust. Math. Soc. 100 (2019), no. 1, 48–57.
  * [4] David Cook II, Simplicial decomposability, The Journal of Software for Algebra and Geometry 2 (2010), 20–23.
  * [5] M. Crupi, A. Ficarra, Very well–covered graphs by Betti splittings, J. Algebra 629(2023) 76–108. https://doi.org/10.1016/j.jalgebra.2023.03.033.
  * [6] M. Crupi, A. Ficarra, Very well-covered graphs via the Rees algebra, 2023, available at arXiv:2305.01448v3
  * [7] A. Ficarra. Homological shifts of polymatroidal ideals, available at arXiv preprint https://arxiv.org/abs/2205.04163[math.AC] (2022).
  * [8] A. Ficarra, J. Herzog, Dirac’s Theorem and Multigraded Syzygies. Mediterr. J. Math. 20, 134 (2023). https://doi.org/10.1007/s00009-023-02348-8
  * [9] D. R. Grayson, M. E. Stillman. Macaulay2, a software system for research in algebraic geometry. Available at http://www.math.uiuc.edu/Macaulay2.
  * [10] J. Herzog, T. Hibi. Monomial ideals, Graduate texts in Mathematics 260, Springer–Verlag, 2011.
  * [11] J. Herzog, S. Moradi, M. Rahimbeigi, G. Zhu, Homological shift ideals. Collect. Math. 72 (2021), 157–74.
  * [12] J. Herzog, S. Moradi, M. Rahimbeigi, G. Zhu, Some homological properties of borel type ideals, Comm. Algebra 51 (4) (2023) 1517–1531.


# Speculating Ineffective UI Exploration via Trace Analysis

Wenyu Wang  University of Illinois at Urbana-Champaign USA<EMAIL_ADDRESS>,  Wei Yang  University of Texas at Dallas USA<EMAIL_ADDRESS>,
Tianyin Xu  University of Illinois at Urbana-Champaign USA<EMAIL_ADDRESS>and  Tao Xie  Peking University China<EMAIL_ADDRESS>
(2020)

###### Abstract.

Mobile computing is powered by mobile applications (in short as mobile apps).
With the prosperity of mobile apps, especially their roles in people’s daily
life during pandemic (e.g., food ordering, grocery delivery, and social
networking), quality assurance of mobile apps becomes crucially important.
Automated mobile User Interface (UI) testing had arisen as a key technique for
app quality assurance. However, despite years of efforts, existing mobile UI
testing techniques still cannot achieve high code coverage, especially for
industrial-quality apps. A recent study reveals that the code coverage
achieved by mobile UI testing tools is about only 30%.

To substantially improve the efficacy of mobile UI testing, we investigate
state-of-the-art techniques and find a fundamental limitation—each testing
technique attempts to apply one predefined strategy to explore the UI space of
all mobile apps. However, we observe that different UI design characteristics
require customized UI exploration strategies in practice. With this finding in
mind, in this paper, we propose a new direction for mobile UI
testing—automatic customization of UI exploration strategies for each app
under test.

As a first step in this direction, we target ineffective exploration behavior,
which refers to cases where UI testing tools fail to make progress
effectively. Ineffective exploration behaviors can provide insights to (1)
limitation in a tool’s UI exploration strategies, (2) defects in a tool’s
implementation, or (3) an app’s usability issues. We present Vet as a general
framework for applying the idea of trace analysis on UI testing history to
identify ineffective exploration behavior for a given UI testing tool on a
given app. Vet embraces specialized algorithms for speculating subsequences in
the trace that manifest ineffective exploration behavior of UI space
exploration. Vet then enables enhancing the testing tool by guiding the
exploration to avoid ineffective exploration. We evaluate Vet by applying it
to three state-of-the-art Android UI testing tools. Vet locates ineffective
exploration behaviors that reveal various tool-app applicability issues
hindering testing efficacy. Vet automatically fixes the applicability issues
and achieves up to 46.8% code coverage relative improvements on 11 of 15
industrial-quality apps under evaluation.

††journalyear: 2020††price: 15.00

##  1\. Introduction

Mobile computing is powered by mobile applications (in short as mobile apps).
With the prosperity of mobile apps (android_market_share, ), especially their
roles in people’s daily life during pandemic (e.g., food ordering, grocery
delivery, and social networking), quality assurance of mobile apps becomes
crucially important. User Interfaces (UIs), as the primary interface of user-
app interactions, are natural entry points for app testing. While manual UI
testing is still a practice, automated UI testing is becoming more and more
widely used (ten_best_tools, ; how_to_perform_mobile_automation_testing, ;
How-to-Automate-Mobile-App-Testing, ; mastering_the_art_of_mobile_testing, ).
Automated UI testing mimics how human users interact with apps through the UIs
and detects reliability and usability issues (e.g., crashes) that appear
during the interaction. Automated UI testing complements manual testing with
greater timing flexibility and better code coverage, requiring no or little
human intervention.

While recent UI testing techniques (Mao:2016, ; su2017guided, ;
Gu:2019:PGT:3339505.3339542, ; yang13:grey, ) have reported promising results,
measurement studies on comprehensive app benchmarks (ChoudharyGO15, ;
Wang:2018:ESA:3238147.3240465, ) have drawn different conclusions. For
example, a recent study (Wang:2018:ESA:3238147.3240465, ) shows that state-of-
the-art mobile testing tools yield low code coverage (generally lower than 30%
in method coverage) after hours of testing on widely-used industrial-quality
apps. In short, state-of-the-art mobile UI testing tools cannot effectively
explore apps’ UI space, despite that they use advanced strategies for UI
exploration (such as evolutionary algorithms and UI modeling).

Our experience in experimenting with mobile UI testing techniques reveals a
fundamental limitation in the way how UI exploration strategies are
applied—each specific technique uses one predefined exploration strategy for
all different apps. In practice, it is prohibitively difficult to have one
“silver-bullet” exploration strategy that fits all apps, given the distinct
characteristics of different mobile apps. We show a real-world example in
Section 2 in which the exploration strategy used by a state-of-the-art Android
UI testing tool named Ape (Gu:2019:PGT:3339505.3339542, ) explores UIs
ineffectively—it logs itself out at a very early testing stage and loses the
opportunity to explore most of the app’s functionalities during the rest of
the testing time. A previous study (Wang:2018:ESA:3238147.3240465, ) also
shows similar observations that different tools have different efficacy on
different types of apps.

Acknowledging the fact that no single exploration strategy works well for all
apps, we propose a new direction to address the UI testing problem. We argue
that the UI testing problem requires customization from not only a testing
tool but also the app under test. As a first step in this direction, we focus
on addressing ineffective exploration behaviors, widely-existing behaviors
that the UI testing tool fails to make progress effectively (e.g., spending
unnecessary time repeatedly covering a small number of app functionalities).
Identifying ineffective exploration behaviors reveals the weaknesses of a
tool’s UI exploration strategies when targeting at specific apps, and pointing
to the direction of improving the tool. For example, simple UI alterations
(e.g., disabling a logout button) can prevent some instances of ineffective
exploration of UI testing tools (shown in Section 5.3).

Note: Colored bars on the top represent the progress of two 1-hour tests,
where green bars refer to normal exploration and red bars refer to ineffective
exploration. Dashed straight arrows indicate visiting the screen from other
the entry screen, and solid arrows show transitions between two screens after
clicking the red-boxed UI elements. The dashed curve arrow on Screen D depicts
that Ape cycled around D until the end of testing. The dashed curve arrow on
Screen F shows that Monkey stayed on F within the 22-minute ineffective
exploration window.  [¡short description¿]¡long description¿

Figure 1. Motivating examples of ineffective exploration behaviors described
in Section 2.

We propose Vet, a general framework that applies the idea of trace analysis on
UI testing history to identify ineffective exploration behavior for a given UI
testing tool on a given app. From the given trace, Vet embraces specialized
algorithms for speculating trace subsequences (termed regions) that manifest
ineffective exploration behavior of UI space exploration. We instantiate Vet
by designing algorithms to capture the effects of destructive factors (e.g.,
actions on a specific UI element controlling app settings, tool implementation
defects triggerable in certain conditions)—such factors either eliminate or
greatly impair the efficiency of further exploring the UI space. Our two
specialized algorithms correspond to the two variants of ineffective
exploration consequences: Exploration Space Partition and Excessive Local
Exploration (§4). We leverage fitness value optimization (whitley1994genetic,
) to realize our algorithms. Our experiments (§5.2) show that ineffective
exploration regions speculated by these two algorithms are sufficient to
reveal various issues of applying specific tools on specific apps, including
tool implementation defects as well as app usability issues.

After identifying the ineffective exploration behaviors and locating the
preceding UI action, Vet enhances the UI testing tool by customizing the UI
exploration strategy for each app under test. Specifically, Vet guides the
exploration to avoid the UI action that leads to ineffective exploration. This
guidance is done by altering the corresponding UI elements. Essentially, Vet
enables UI testing tools to circumvent their own weaknesses by transforming a
hard-to-explore app to a set of easy-to-explore sub-apps. Take the logout
example above: the app is conceptually transformed into a sub-app without the
logout button and a sub-app with UIs after logout.

To evaluate Vet in locating ineffective exploration behaviors, we apply Vet on
120 test traces collected using three state-of-the-art Android UI testing
tools (Monkey (AndroidMonkey, ), Ape (Gu:2019:PGT:3339505.3339542, ), and
WCTester (Zeng:2016, ; zheng17:automated, )) with 15 widely-used industrial-
quality apps. Our evaluation results show that 28 of 40 ineffective
exploration regions are successfully located by Vet; those regions are caused
by various tool-app applicability issues that hinder testing efficacy,
reflecting both tool defects and app usability issues. Vet automatically fixes
the applicability issues and achieves up to 46.8% code coverage relative
improvements on 11 of 15 apps under evaluation.

In summary, this paper makes the following main contributions:

  * •

A new perspective of improving automated mobile UI testing techniques by
customizing UI exploration strategies based on the target app;

  * •

Algorithms for effective localization of two manifestation patterns of
ineffective exploration behaviors from UI traces;

  * •

Exploration-aware UI testing that can substantially improve the efficacy of
Android UI testing;

  * •

Practical tooling that can be integrated with state-of-the-art Android UI
testing tools such as Monkey (AndroidMonkey, ), Ape
(Gu:2019:PGT:3339505.3339542, ), and WCTester (Zeng:2016, ; zheng17:automated,
).

  * •

Comprehensive evaluation of Vet, demonstrating that Vet reveals various tool
defects and app usability issues with few misses, and that Vet automatically
fixes the applicability issues and achieves up to 46.8% code coverage relative
improvements on 11 of 15 apps under evaluation.

##  2\. Motivating examples

We present two concrete examples from our experiments covering Exploration
Space Partition and Excessive Local Exploration. These examples provide
contexts for further discussions and help illustrate the motivations that
drive the design of Vet.

###  2.1. Exploration Space Partition

We run Ape (Gu:2019:PGT:3339505.3339542, ), a state-of-the-art Android UI
testing tool to test a popular app, Microsoft OneNote. The result is
illustrated in Figure 1(a). We manually setup the account to login in the
app’s main functionalities, and then start Ape. We run Ape without
interruptions for one hour and check the test results afterward.

In the one-hour testing period, Ape only explored 9% (7 out of 76) activities.
To understand the low testing effectiveness, we investigate into the UI trace
captured during testing and find the root cause to be ineffective exploration
behavior:

  1. (1)

Ape performs exploration around OneNote’s main functionalities for less than
one minute, which covers 4 (out of 7) of all the activities covered in the
entire one-hour test run. We omit this phase in Figure 1(a).

  2. (2)

About 1 minute after testing starts, Ape arrives at the “Settings” screen
(Screen A) and decides to click “Account” (the red-boxed UI element) for
further exploration.

  3. (3)

Ape arrives at the “Account” screen (Screen B) and clicks the “Sign Out”
button. The click triggers a window to pop up (Screen C) asking for
confirmation of getting logged out.

  4. (4)

Ape clicks “CANCEL” first, and the tool goes back to the “Account” screen.
However, Ape clicks the “Sign Out” button again, knowing that there is one
action not triggered yet in the confirmation dialog. Subsequently, Ape clicks
on the “OK” button (Screen C) and logs itself out.

  5. (5)

The logout leads to the entry screen (Screen D). From this point, Ape has
access to only a small number of functionalities (e.g., logging in). Ape
cannot login due to the difficulty of auto-generating the username/password of
the test account. In the remaining 59 minutes, Ape explores 3 activities in
total.

This example represents Exploration Space Partition (§1). The essential
problem is that Ape does not understand UI semantics—it does not know that the
majority of OneNote’s functionalities will be unreachable by clicking the “OK”
button at the time of action.

###  2.2. Excessive Local Exploration

Figure 1(b) presents another example in which we run Monkey (AndroidMonkey, ),
a widely-adopted tool, to test another popular industry-quality app, Nike Run
Club. In this example, Monkey spent about 22 minutes trying to saturate one of
the app’s functionalities. After investigating into the collected UI trace, we
find the following behavior when Monkey interacts with the app:

  1. (1)

Monkey explores other functionalities normally before entering Screen E which
allows the tool to enter the functionality where the tool later gets trapped.
We name the functionality the trapping functionality. Monkey clicks the
“START” button and enters the trapping functionality (Screen F).

  2. (2)

Monkey keeps clicking around in the trapping functionality. In order to escape
from the trapping functionality, Monkey first needs to press the Back button,
and a confirmation dialog (Screen G) will pop up. Monkey then has to click the
“OK” button to finish escaping. However, due to being widget-oblivion, Monkey
only clicks on randomly-chosen points on the screen, resulting in constant
failures to click “OK” when the confirmation dialog is shown. Furthermore, the
dialog disappears when Monkey clicks outside of its boundary, and Monkey needs
to press the Back button again to make the confirmation show up one more time.
It takes 22 minutes for Monkey to find and execute an effective escaping UI
event sequence and finally leave the trapping functionality.

  3. (3)

The aforementioned behaviors are repeatedly observed on the trace (with
different amount of time used for escaping).

This example represents Excessive Local Exploration behavior described in §1.
The essential problem is that Monkey is both widget- and state-oblivion, which
means that the tool is unable to locate actionable UI elements efficiently or
sense whether it has been trapped and react accordingly (e.g., by restarting
the target app).

###  2.3. Implications

To prevent such undesirable exploration behaviors, a conceptually simple idea
is to de-prioritize exploring the entries to aforementioned trapping states
(i.e., “OK” button in Screen C, and “START” button in Screen F). One potential
solution is to develop natural language processing (NLP) or image processing
based approaches that can infer the semantics of UI elements
(10.1145/3319535.3363193, ; 8812108, ; 10.1145/3242587.3242650, ;
Packevicius2018TextSA, ). While solutions based on understanding UI semantics
are revolutionary, they are challenging due to fundamental problems rooting in
NLP and image processing.

This paper explores a more practical and evolutionary solution based on
understanding ineffective exploration behavior by mining UI traces. We show
that it is feasible to speculate the existence and location of such behavior
through pattern analysis on interaction history. Given the location of
ineffective exploration behavior, we can further speculate which UI actions
might have led to such behavior. Taking the example of Figure 1, Ape starts to
visit a very different set of screens (e.g., the welcome screens in Screen D
in Figure 1(a)) after clicking “OK”, and the number of explored screens
dramatically decreases. Therefore, we can look at the screen history and find
the time point where the symptom starts to appear. The UI action located at
the aforementioned time point is then likely the cause of the symptom. Our
tool Vet uses a specialized algorithm (§4.2) to effectively locate the
starting time point of ineffective exploration behavior similar to the
aforementioned instance.

##  3\. Background

This section presents a portion of background knowledge that helps readers
understand our design of algorithms and implementations in the scope of
Android UI testing.

###  3.1. Android UI System

Figure 2 depicts a simplified overview of the Android GUI system
(android_graphics_path, ), showing only forward pass with one visible activity
(App Activity in the figure). Driven by the screen refresh signals, the
visible activity decides the content (i.e., concrete images) to show in its
own screen space (a Surface) with the help of 2D/3D Renderer, either software
libraries or hardware accelerators such as GPU. Generated screen images are
then queued and ready for Surface Flinger to consume. After gathering screen
images from visible activities (by consulting ActivityManager) and knowing how
these images should be stitched together (by consulting WindowManager),
SurfaceFlinger aggregates and sends the resulting full-screen images to
HardwareComposer for displaying on screen.

Figure 2. A simplified overview of the Android UI system.

[¡short description¿]¡long description¿

##### UI Hierarchy.

A UI hierarchy is used to represent contents of app UI shown on one screen
(thus corresponding to one UI screen). Each UI hierarchy consists of UI
properties (e.g., element type, location, and size) for individual UI elements
(e.g., buttons, text labels) and hierarchical relations among UI elements.
Each activity internally maintains the data structure for its current UI
hierarchy. After receiving rendering requests, an activity generally starts
from the root element of its UI element tree and recursively requests all
child elements to be rendered in their screen spaces based on their location
properties. The activity puts together rendered images according to the
positions and orderings of their respective child elements. A similar process
is also used for handling user events: the root element receives the event
details and iterates through immediate child elements that might be targeted
by the event to attempt dispatching the event. These child elements will
subsequently try dispatching the event to their child elements until some
inner element responds that the event has been consumed.

The internal data structure is usually built by standard Android UI elements
(e.g., TextView and EditText) and exposed to the Android framework, though
developers are allowed to define their own UI-related data structures without
using or inheriting standard UI element classes. In such case, apps need to
handle lower-level UI events and rendering works. Note that general-purpose UI
testing tools can only understand the data structures of standard Android UI
elements, given that there is no specification on what UI properties
developers must expose in their customized data structures other than those in
the generic View class.

###  3.2. Equivalence Check for UI hierarchies

A key component of UI testing is to identify the current app functionality,
and UI hierarchies are usually used as indicators of apps’ functionality
scenarios. Checking the equivalence between the current and past UI
hierarchies allows tools to speculate whether a new functionality is being
exercised. If the current functionality has been previously covered, the tool
can additionally leverage the knowledge associated with the functionality to
decide next actions. There are different existing ways of checking UI
hierarchy equivalence:

  * •

Strict comparison. A simple way to check equivalence of two UI hierarchies is
to compare their UI element trees and see whether they have identical
structure and UI properties at each node. In practice, such simple equivalence
checking is too strict. For example, on an app accepting text inputs, a tool
checking exact equivalence will count a new functionality every time one
character is typed. The tool subsequently believes that keeping inserting
characters will cover different app functionalities, which is not true in most
cases.

  * •

Checking similarity. A workaround to the aforementioned issue of strict
comparison is to check similarities of two UI hierarchies against a threshold.
However, ambiguity will become the new issue, given that the similarity
relation is not transitive: suppose that A is similar to both B and C, it is
still possible that B is not similar to C. Then if both B and C are in the
history (regarded as different functionalities), and A comes as a new UI
hierarchy, the tool will be unable to decide on which functionality to use the
associated knowledge from.

To fix the ambiguity issue, we can perform screen clustering, essentially
putting mutually-similar screens into individual groups and regarding each
group as representing one single functionality. The downside is that screen
clustering can be a computationally expensive operation, especially for traces
with many screens.

  * •

Comparing abstractions. A more advanced solution is to check the equivalence
at an abstraction level. In the previous example, one can leave out all user-
controlled textual UI properties from the hierarchy, and the equivalence check
can tell that the tool is staying on the same screen regardless of what has
been entered.

While abstracting UI hierarchies is conceptually effective, it is challenging
to design effective UI abstraction functions. The difficulty lies in
identifying UI properties or structural information to distinguish different
app functionalities, especially when screens have variants with relatively
subtle differences. For instance, many apps adopt the practice of showing tips
as users explore, and these tips do not affect how apps react to actions.
These tips, implemented using various UI elements across different apps,
become parts of app UI hierarchies. It is difficult to find a unified way for
identifying and removing these tips in UI hierarchies from various apps in
different contexts.

Ape (Gu:2019:PGT:3339505.3339542, ) proposes adaptive abstractions to address
the challenge of automatically finding proper UI abstraction functions in
different scenarios. The tool dynamically adjusts its abstraction strategy
(e.g., which UI property values should be preserved) during testing based on
feedbacks from strategy execution (e.g., whether invoking actions on UI
hierarchies with the same abstraction yields the same results). Unfortunately,
the adaptive abstraction idea assumes the availability of sufficiently
diversified execution history for feedbacks, which might not be always
available when analyzing given traces as in our situation.

Given the pros and cons of the aforementioned techniques, we empirically adopt
a hybrid approach for UI hierarchy equivalence check. Specifically, first, we
always abstract UI hierarchies: (1) we consider only visible UI elements
(i.e., View.getVisibility() == VISIBLE, and the element’s bounding box
intersects with its parent’s screen region), (2) we keep the original UI
structure and the activity name, and (3) we retain only UI element types and
IDs from UI properties. Second, we try to check similarities of abstract UI
hierarchies and cluster them into groups only when analysis is sensitive to
the absolute number of distinct screens. More details on how to achieve
clustering efficiently are elaborated in §4.3.

##  4\. The Vet Approach

###  4.1. Overview

We propose Vet, a general framework that applies the idea of trace analysis on
UI testing history to identify ineffective exploration behavior for a given UI
testing tool on a given app. Specifically, Vet analyzes a UI trace,
represented as a sequence of UI screens interleaving with actions on
respective screens, that is recorded when applying the given tool on the given
app. Vet embraces specialized algorithms for speculating subsequences in the
trace (termed regions) that manifest ineffective exploration behavior of UI
space exploration. The speculated regions can then be used for automatically
addressing ineffective exploration of UI testing (§5.3) or manual inspection
(§5.2). Vet aims to assist both app and testing tool developers/practitioners
to understand and improve the performance of testing when their tools and apps
are used together.

We instantiate Vet by designing algorithms to capture the effects of
destructive factors (e.g., actions on a specific UI element controlling app
settings, tool implementation defects triggerable in certain conditions)—such
factors either eliminate or greatly impair the efficiency of further exploring
the UI space. Our two specialized algorithms correspond to the two variants of
ineffective exploration consequences: Exploration Space Partition and
Excessive Local Exploration (§2). Characteristics of two algorithms’ targeted
variants are illustrated in Figure 3 and discussed as follows:

Note that each subgraph corresponds to an example trace, where each circle
represents a distinct screen in the trace (e.g., each subfigure in Figure 1),
each arrow indicates that action(s) is observed between two screens in the
trace, and each curved rectangle depicts a UI subspace. Red arrows denote
destructive actions (e.g., clicking “OK” in Figure 1C, “START” in Figure 1E)
while dashed arrows show where traces begin.  [¡short description¿]¡long
description¿

Figure 3. Illustration of the two variants of ineffective exploration
consequences.

  * •

Exploration Space Partition. As shown in Figure 3a, the UI testing tool
traverses through a UI subspace (Subspace 2) for a long time after the
execution of some action (the red arrow), and the tool is unable to return to
the previously visited UI subspace (Subspace 1). Furthermore, the tool visits
much fewer distinct screens after the action. Presence of the symptom suggests
that the tool has triggered a destructive action, effectively the partition
boundary of the entire trace, that prevents the tool from further exploring
the app’s major functionalities. The first motivating example from §2
corresponds to this symptom, where clicking the “OK” button is the destructive
action which gets Ape trapped in several screens related to logging in
(Subspace 2) and prevents Ape from further accessing OneNote’s main
functionalities (Subspace 1).

  * •

Excessive Local Exploration. As shown in Figure 3b, the UI testing tool is
trapped in a small UI subspace (Subspace 2) for an extended amount of time
after the execution of the corresponding destructive action (the red arrow).
However, the tool is capable of returning to the previously visited UI
subspace (Subspace 1) despite the difficulties. It is also likely that the
tool will get trapped again within Subspace 2 after returning to Subspace 1.
Consequently, the tool spends excessive amount of time in repetitively testing
limited functionalities in such hard-to-escape subspace. The second motivating
example from §2 corresponds to this symptom, where clicking the “START” button
gets Monkey trapped in Screen F and G (Subspace 2). Clicking “OK” helps Monkey
go back to Screen E (within Subspace 1) and other functionalities, but it does
not take a long time before the tool gets trapped again within Subspace 2.

It is possible for the regions reported by the two algorithms on the same
trace to overlap. For example, Excessive Local Exploration might also capture
instances of ineffective exploration behavior within Exploration Space
Partition’s trapped UI subspace (corresponding to Subspace 2 in Figure 3).
Such overlaps do not prevent us from finding meaningful targeted ineffective
exploration behavior: different instances of ineffective exploration behavior
revealed by regions of both algorithms suggest the existence of different
exploration difficulties.

In the remaining of this section, we describe the two algorithms for capturing
Exploration Space Partition and Excessive Local Exploration in §4.2 and §4.3,
respectively. We show that pattern capturing can be expressed as optimization
problems. Table 1 describes the notations which will be used to describe Vet’s
algorithms.

Table 1. Notations and descriptions used in the algorithms Notation | Description
---|---
$S_{i}$ |  Screen $\\#i$ in the trace identified by the screen’s UI hierarchy.
$t_{i}$ |  The timestamp of screen $S_{i}$ being observed.
$S[l,r]$ |  A region of screens starting at Screen $\\#l$ and ending at
|  Screen $\\#r$ (with both ends included).
$\\{S[l,r]\\}$ |  The set of distinct screens from $S[l,r]$ by de-duplicating
| their UI hierarchies.
$t_{\min}$ | A predefined threshold that decides the minimum time length
|  of any $S[l,r]$ (i.e., $t_{r}-t_{l}\geqslant t_{\min}$) that may be
included in
| algorithm outputs.

###  4.2. Capturing Exploration Space Partition

According to our introductions of Exploration Space Partition, we need to find
a destructive action exerted on screen $S_{n}$ as the partition boundary such
that the aforementioned characteristics from §4.1 can be best reflected. For
instance, considering our first motivating example in §2, we hope to pick up
the screen shown in Figure 1C as $S_{n}$. We optimize the following formula to
find the most desirable $S_{n}$ from a trace with $N$ screens:

$\operatorname*{\arg\min}_{1\leqslant
n<E_{p}}\frac{|\\{S[1,n]\\}\cap\\{S[n+1,N]\\}|}{N-n}+2\cdot\sigma(\frac{|\\{S[n+1,N]\\}|}{|\\{S[E_{p}+1,N]\\}|}-1)-1$

In the formula, $E_{p}$ is a pre-calculated limit indicating the upperbound of
$n$ during optimization, and $\sigma$ denotes the Sigmoid function. The
intuition of formula design is as follows:

  1. (1)

As part of the characteristics, the tool should ideally be able to visit few
to no screens that have appeared no later than $S_{n}$ after the tool passes
$S_{n}$. Correspondingly, in our motivating example, screens shown before
Figure 1C (depicting the app’s main functionalities) are dramatically
different from the screens afterward (logging in, ToS, etc.). In the formula,
$\\{S[1,n]\\}\cap\\{S[n+1,N]\\}$ indicates the set of distinct screens
appearing both before and after $S_{n}$, whose size is intended to be
minimized by being the nominator of the first term in the formula.

  2. (2)

As the denominator of the first term, $N-n$ essentially calculates how many
(non-distinct) screens the tool visits after $S_{n}$. There are two purposes
of such design. First, we hope to normalize the first term in the formula (so
that two terms can weigh the same). We know that
$|\\{S[1,n]\\}\cap\\{S[n+1,N]\\}|\leqslant|\\{S[n+1,N]\\}|\leqslant N-n$, thus
the first term is guaranteed to fall within $[0,1]$. Second, we want to push
$S_{n}$ backward (note that smaller $n$ makes the first term smaller) because
we assume that doing this makes $S_{n}$ closer to the root cause of
ineffective exploration, which should appear earlier than other causes.

  3. (3)

As another part of the characteristics, the tool stays within a certain UI
subspace for a long time, thus the tool will go through screens within the
subspace very often. If the tool generally uniformly visits most or all
distinct screens within the subspace, by observing a small period of
exploration (corresponding to $S[E_{p}+1,N]$ in the formula) we should have a
fairly precise estimation (i.e., $\\{S[E_{p}+1,N]\\}$) of the subspace
boundary, which is characterized by $\\{S[n+1,N]\\}$. The second term in the
formula corresponds to such intuition, where the closer $\\{S[E_{p}+1,N]\\}$
is to $\\{S[n+1,N]\\}$ (note that
$\\{S[E_{p}+1,N]\\}\subseteq\\{S[n+1,N]\\}$), the more favorable it becomes
during optimization. Note that it is theoretically possible for the formula to
miss a special case when the tool repeatedly visits only a few screens after
$S_{E_{p}}$ until end of the trace, where the second term will influence more
on the formula value. A more precise and computationally expensive way is to
try replacing $S[E_{p}+1,N]$ with each region within $S[n+1,N]$ that spans
$t_{\min}$. However, we regard the trade off acceptable because such case can
still be covered when handling Excessive Local Exploration.

  4. (4)

By setting an upperbound $E_{p}$ on $n$ and regularizing the ratio with
Sigmoid function and applying appropriate linear transformations, we can
guarantee that the second term in the formula always ranges from 0 to 1, being
the same as the first term. In the end, two terms in the formula contribute
equally to optimization choices.

To determine $E_{p}$ on each trace, because our optimization scope will not
include any interval shorter than $[E_{p},N]$, we choose a value such that
$t_{N}-t_{E_{p}}$ is closest to $t_{\min}$.

After obtaining a potentially suitable $S_{n}$ through optimizing the
aforementioned formula, we additionally check whether
$|\\{S[1,n]\\}|>|\\{S[n+1,N]\\}|$ is satisfied, essentially enforcing the
property that the exploration space should be smaller after the partition.
Finally the reported region would be $S[n+1,N]$.

###  4.3. Capturing Excessive Local Exploration

Based on the characteristics of Excessive Local Exploration from §4.1, we
should track the presence of a region which shows that the tool is trapped
within a small UI subspace for an extended amount of time. For our second
motivating example in §2, one valid choice is the 50-minute region starting
from the button click in Figure 1E. We accordingly optimize the following
formula to find the boundaries $S_{l}$ and $S_{r}$ of the most suitable region
on a given trace:

$\operatorname*{\arg\min}_{1\leqslant l\leqslant r\leqslant
N}\frac{|\textsc{Merge}(\\{S[l,r]\\})|}{r-l+1}$

In the formula, Merge denotes the operation of merging similar screens and
returning the groups of merged screens. As the optimization formula suggests,
we hope to find a suitable region such that it covers few distinct screen
groups despite that the tool tries to explore diligently (by injecting
numerous actions quantified by $r-l+1$). Then if $t_{r}-t_{l}\geqslant
t_{\min}$, we regard that the ineffective exploration region $S[l,r]$ can be
reported. Accordingly in our motivating example, the choice of $S_{l}$ would
be Figure 1F and $S_{r}$ would be the last instance of Figure 1G in the
50-minute region. $S_{l-1}$ corresponds to Figure 1E, and the destructive
action is reported.

Note that there can be more than one region exhibiting Excessive Local
Exploration behavior within a single trace, given the possibility for the tool
to escape the UI subspaces where Excessive Local Exploration behavior is
observed. In order to find all potential regions, we iterate the
aforementioned optimization process on remaining region(s) each time after one
region is chosen, until no more region can be divided.

Input: a set of abstract UI hierarchies $H$

Output: a mapping $R:H\mapsto R$, where $R\subseteq H$

Sort $h\in H$ by $|h|$ in ascending order

$R\leftarrow\\{\\}$

foreach  _$h\in H$_ do

$R[h]\leftarrow$ nil

end foreach

foreach  _$h\in H$_ do

if  _$R[h]=$ nil_ then

$R[h]\leftarrow h$

foreach  _$h^{\prime}\in H$_ do

if  _$R[h^{\prime}]=$ nil $\land$ SimCheck$(h,h^{\prime})$_ then

$R[h^{\prime}]\leftarrow h$

end if

end foreach

end if

end foreach

return $R$

Algorithm 1 Merge: Merging similar screens into groups (each group is
represented by its root screen in $R$)

Design of Merge. As mentioned in §3.2, involving screen merging is especially
useful for handling Excessive Local Exploration, given that the aforementioned
optimization formula is very sensitive to the absolute numbers of distinct
screens. Being part of the challenge, an efficient (and mostly effective)
screen merging algorithm requires careful design. Given a set of distinct
abstract screens (represented by UI hierarchies) to merge, a relatively
straightforward (and precise) approach is to first calculate the tree editing
distance (tree_edit_dist, ) for each pair of abstract UI hierarchies for
similarity check, and then use combinatorial optimization (wolsey1999integer,
) to decide the optimal grouping strategy (e.g., by converting to an Integer
Linear Programming problem), such that all screens within the same group are
mutually similar and the total number of groups is minimal. Unfortunately,
such algorithm will require exponential time in regards to the number of
distinct abstract screens to merge. The design will likely fall short on
traces collected using industrial-quality apps, from which we can easily
capture hundreds to thousands of distinct abstract screens.

Aiming to make the algorithm practically efficient, we relax the definition of
similarity and the goal of optimization from the aforementioned merging
algorithm based on insights from our observations. Specifically, we find that
in many cases, similar screens can be seen as screen variants derived from
base screens by inserting a small number of leaf nodes or subtrees into the
abstract UI hierarchy. Based on such assumption with some tolerance for
inaccuracy, we can (1) design a more efficient tree similarity checker
(Algorithm 2), which considers only node insertion distances and has
$\Theta(|h_{1}|\cdot|h_{2}|)$ time complexity (compared with
$O(|h_{1}|\cdot|h_{2}|\cdot\textsc{Height}(h_{1})\cdot\textsc{Height}(h_{2}))$
for full tree edit distance), and (2) replace the inefficient combinatorial
optimization with a highly efficient greedy algorithm (Algorithm 1), which
tries to find all the base screens with $O(|H|^{2})$ time complexity. In
practice, with several other optimizations that do not affect the level of
time complexity, it takes only several minutes for the Excessive Local
Exploration algorithm to process a long trace with about 2,000 distinct
abstract screens and tens of thousands of concrete screens in total.

Input: abstract UI hierarchies $h_{1},h_{2}$

Output: whether $h_{1},h_{2}$ are similar enough

Const: max allowed distance $d_{\text{max}}$, empirically set to $3$

$seq_{1}\leftarrow[]$

foreach  _$node\in$ DepthFirstTraverse$(h_{1})$_ do

$seq_{1}\leftarrow seq_{1}::(\textsc{Props}(node),\textsc{Depth}(node))$

// Props obtains the node’s UI properties that are preserved during
abstraction. See more details at §3.2.

end foreach

$seq_{2}\leftarrow[]$

foreach  _$node\in$ DepthFirstTraverse$(h_{2})$_ do

$seq_{2}\leftarrow seq_{2}::(\textsc{Props}(node),\textsc{Depth}(node))$

end foreach

$lcs\leftarrow\textsc{LongestCommonSequence}(seq_{1},seq_{2})$

if  _$|lcs| <\min(|h_{1}|,|h_{2}|)$_ then

return false

else

return $\max(|h_{1}|,|h_{2}|)-|lcs|\leqslant d_{\text{max}}$

end if

Algorithm 2 SimCheck: UI hierarchy similarity checker

###  4.4. Efficient UI Monitoring and Manipulation

We build our own Android UI monitoring and manipulation system, OurInfra
(anonymized for review), mainly to (1) efficiently monitor testing for
different Android UI testing tools and record UI traces for Vet to analyze
without noticeably slowing down the testing process, and (2) dynamically alter
app behavior for our integration evaluation (§5.3). We are not currently aware
of any existing tool/system capable of achieving these goals without modifying
our experiment apps, which will likely lead to undesirable consequences as
discussed later.

Figure 4 shows an overview of OurInfra’s design. OurInfra resides in the same
virtual machine as the app under testing, which gives OurInfra direct access
to the app’s runtime memory. OurInfra is thus able to (1) resolve the app’s
internal UI-related data structures to generate UI hierarchies, (2)
dynamically analyze, invoke, or alter UI event handlers to understand/control
app behaviors, perform UI events, or capture inputs, and (3) query the app
resource manager to provide additional UI-related information for human
investigation. After OurInfra is loaded together with the app under test, one
can establish Unix abstract socket connections to directly communicate with
OurInfra, making it handy for debugging and eliminating the need of any
special Android permission. We have also built a test controller (intended to
run on a computer) that works with OurInfra to conveniently record UI
interaction traces and apply any pre-defined app manipulation settings (e.g.,
disabling a specific UI element on a specific screen).

OurInfra aims to be both powerful and fast. It is currently capable of
capturing taps, long clicks, touches, and Back pressing. Thanks to the direct
runtime memory access, OurInfra additionally supports resolving events on
AdapterViews to pinpoint which list elements will the events be dispatched on.
In terms of speed, according to our experiences with OurInfra, it is usually
able to obtain the full UI hierarchy within only twenty milliseconds even on
screens with sophisticated structures. For comparison, the official
UIAutomator framework usually spends hundreds of milliseconds to several
seconds to capture just a single UI hierarchy. In general, we find OurInfra to
impose very low time overhead when performing different duties, enabling us to
apply our proposed techniques to any involved Android testing tool without
noticeably slowing down the testing process or interfering with the testing
tool.

OurInfra is also non-intrusive to the apps under test as well as existing
testing tools. Specifically, in our experiment environment, OurInfra is
bundled with app-space Android framework classes on the testing device,
eliminating the need to modify app installation packages or testing tool
logistics. The support for unmodified installation packages is particularly
useful for testing close-sourced industrial apps, main because (1) many apps
have imposed self-protection mechanism (which prevents unauthorized changes to
installation packages), and (2) manipulating large apps’ bytecode is more
error-prune (e.g., just adding a new class during instrumentation may cause
the app’s .dex file to exceed the 64K method limit (MultipleDex, )). We manage
to integrate OurInfra with the Android 6.0 framework on both emulators and
real devices. While having experienced no issue with the current way of
integration, we would still like to point out that it is possible to use
OurInfra without modifying the Android framework–in that case, add OurInfra to
the app’s codebase before building the installation packages.

Figure 4. Overview of OurInfra’s design

[¡short description¿]¡long description¿

##  5\. Evaluation

Our evaluation answers the following research questions:

  * •

RQ1: Can Vet help reveal tool-app applicability issues with speculated
ineffective exploration regions?

  * •

RQ2: Can Vet improve the effectiveness of existing Android UI testing tools
through automatic fixes?

  * •

RQ3: How likely do our algorithms miss tool-app applicability issues in their
speculated ineffective exploration regions?

###  5.1. Evaluation Setup

Android UI Testing Tools and Android Apps. We use three state-of-the-art or
state-of-the-practice Android UI testing tools: Monkey (AndroidMonkey, ), Ape
(Gu:2019:PGT:3339505.3339542, ), and WCTester (Zeng:2016, ; zheng17:automated,
). We select 15 popular industry-quality Android apps from the Google Play
Store, as shown in Table 5.1. These 15 apps are from a previous study
(Wang:2018:ESA:3238147.3240465, ), which picks the most popular apps from each
of the categories on Google Play and compares multiple testing tools with
these apps. The apps we choose need to work properly on our testing
infrastructure: (1) they need to provide x86/x64 variants of native libraries
(if they have any), (2) they do not constantly crash our emulators, and (3)
OurInfra is able to obtain UI hierarchies on most of the functionalities. Note
that we have also skipped 5 apps for WCTester (as shown in Table
LABEL:tbl:intg_test_results) because the tool keeps restarting these apps
during testing, preventing our code coverage collector, MiniTrace
(Gu:2019:PGT:3339505.3339542, ), from obtaining any coverage information.

Table 2. Overview of industrial apps for evaluation

App Name | Version | Category | #Inst | Login
---|---|---|---|---
AccuWeather | 5.3.5-free | Weather | 50m+ | ✗
AutoScout24 | 9.3.14 | Auto & Vehicles | 10m+ | ✗
Duolingo | 3.75.1 | Education | 100m+ | ✗
Flipboard | 4.1.1 | News & Magazines | 500m+ | ✓
Merriam-Webster | 4.1.2 | Books & Reference | 10m+ | ✗
Nike Run Club | 2.14.1 | Health & Fitness | 10m+ | ✓
OneNote | 16.0.9126 | Business | 100m+ | ✓
Quizlet | 3.15.2 | Education | 10m+ | ✓
Spotify | 8.4.48 | Music & Audio | 100m+ | ✓
TripAdvisor | 25.6.1 | Food & Drink | 100m+ | ✓
Wattpad | 6.82.0 | Books & Reference | 100m+ | ✓
WEBTOON | 2.4.3 | Comics | 10m+ | ✗
Wish | 4.16.5 | Shopping | 100m+ | ✓
YouTube | 15.35.42 | Video Player & Editor | 1b+ | ✗
Zedge | 6.8.4 | Personalization | 100m+ | ✗

  * •

Notes: ‘#Inst’ denotes the approximate number of downloads, ‘Login’ indicates
whether the app requires logging in to access most features.

##### Trace Collection.

We run each tool on every applicable app for three times to alleviate
potential impacts of non-determinism in testing. Each run lasts for one hour
without interruption. We record the UI traces using OurInfra (described in
§4.4), where each test run corresponds to one trace. While Vet runs separately
on each UI trace, results are grouped for each combination of tools and apps
as explained later. In the end, we manage to collect 120 one-hour UI testing
traces from 40 tool-app combinations.

##### Testing Platform.

All experiments are conducted on the official Android x86-64 emulators running
Android 6.0 on a server with Xeon E5-2650 v4 processors. Each emulator is
allocated with 4 dedicated CPUs cores, 2 GiB of RAM, and 2 GiB of internal
storage space. Emulators are stored on a RAM disk and backed by GeForce GTX
1080Ti graphics cards for minimal mutual influences caused by disk I/O
bottlenecks and CPU-intensive graphical rendering. We manually write auto
login scripts for apps with “Login” ticked in Table 5.1, and each of these
scripts is executed only once before the corresponding app starts to be tested
in each run.

##### Overall Statistics.

Vet reports 161 regions to exhibit ineffective exploration behaviors,
averaging 2.9 on each tool-app combination. Based on Vet’s reports, the
average amount of time involved in ineffective exploration behaviors is 23.5
minutes per region, with maximum being almost 1 hour and minimum being
slightly more than 10 minutes (given that we empirically set $t_{\min}=10$
minutes for all experiments).

###  5.2. Detected Tool-app Applicability Issues

####  5.2.1. Methodology

We evaluate the effectiveness of Vet in capturing ineffective exploration
behavior that reveals applicability issues over combinations of testing tools
and apps. Specifically, we first group ineffective exploration regions by the
pair of tool and app that these regions are observed on. Then, we rank the
regions within each pair of tool and app by their time lengths, where longer
traces receive higher ranks. The intuition of the ranking strategy is that
longer regions are likely to exhibit ineffective exploration behavior with
higher impacts. Finally, we manually investigate into each of the rank-1
region from all applicable combinations of testing tools and apps. We report
any tool-app applicability issue that we could identify for each of these
regions.

Note that we only count the applicability issue that we consider the most
specific cause to ineffective exploration behavior exhibited by each region:
if both issue A and B contribute to ineffective exploration on some region,
and A also contributes to other regions of the same tool or app, we will count
only B towards the statistics.

####  5.2.2. Results

We are able to determine tool-app applicability issues on 28 of 40 manually
investigated regions. The applicability issues can be traced to two root
reasons: apps under test require extra knowledge for effective testing, and
tool defects prevent themselves from progressing. We discuss specific
applicability issues with regards to these two root reasons:

  * •

App logout or equivalent accounts for ineffective exploration on 21% (6 out of
28) of investigated regions with identified issues. Some apps essentially
require login states for the majority of their functionalities to be
accessible. However, the tools used in our experiments have no knowledge about
the consequences of invoking the “logout” buttons in different apps before
they actually try them. Unfortunately, after tools try out such actions
(driven by their exploration strategies), the apps’ login states (both on-
device and on-server) have been destroyed. The tools then have to spend all
remaining time on limited numbers of functionalities, leading to ineffective
exploration. It reveals a common weakness of existing UI testing tools—they
have limited understanding of action semantics. According to our results on 28
regions, both Ape has 2 such regions, Monkey has 3, while WCTester has 1 such
region.

  * •

Unresponsive UIs are found in 18% (5 out of 28) of regions. We find that some
apps stop responding to UI actions after the advertisement banner is clicked
(likely due to the defects in Google AdMob SDKs). The app should be restarted
as soon as possible to resume access to its functionalities. According to our
results, Monkey is most vulnerable to this issue, with 4 regions revealing
unresponsive UIs. Additionally, WCTester has one such region. One interesting
finding is that Ape is actually also vulnerable to unresponsive UIs although
the tool is capable of identifying such situations. While Ape proceeds to
restart the app most of the times when the tool finds the app unresponsive,
the tool would fail to do so occasionally. Thus, we regard the Ape’s case as
rooting from tool defects instead of special app needs.

  * •

Network disconnections are found in 14% (4 out of 28) of regions. We find that
turning networking off is undesirable for some apps, especially when the
disconnection lasts for a long time. Consequently, these apps may only show
messages prompting users to check their networks, leaving nothing for
exploration. Tools such as Monkey can control network connections through
Android system UI (e.g., by clicking the “Airplane Mode” icon). While the
capability helps test app logistics in edge conditions in general, it might
hurt the tool’s performance on the apps heavily relying on network access. All
regions with the aforementioned issue come from Monkey’s traces.

  * •

Restart loops are found in 11% (3 out of 28) of regions. The tool essentially
keeps restarting the target app after some point, although the tool might
perform some shallow exploration on few functionalities. One potential cause
for such issues is that the tool thinks that all UI elements in the target
app’s main screen have been explored. The tool might need to revise its
exploration strategy for discovering more explorable UI subspaces. We observe
2 regions from WCTester and 1 region from Monkey.

  * •

Obscure escapes are found in 7% (2 out of 28) of regions. Defects in a tool’s
design or implementation can make it difficult for the tool to escape from
certain app functionalities, and consequently the tool loses opportunities to
explore other functionalities. For instance, Monkey will find it challenging
to escape a screen where the only exit is a tiny button on the screen (see the
second motivating example in §2), due to the tool’s lack of understanding of
UI hierarchies. All 2 regions with the aforementioned issue come from Monkey’s
traces.

  * •

UI abstraction defects are found in 7% (2 out of 28) of regions. Defects in a
tool’s UI abstraction strategies can trick the tool into incorrectly
understanding the testing progress. Seen from the three regions, WCTester
considers all texts as part of abstract UI hierarchies. While the strategy
works well in a wide range of testing scenarios, it keeps the tool
repetitively triggering actions on UI elements with changing texts (such as
countdown), because the tool incorrectly thinks that new functionalities are
being covered.

  * •

Miscellaneous tool implementation defects are found in 21% (6 out of 28) of
regions. In our case we find four potential implementation defects in Ape: (1)
the tool fails to handle unresponsive apps twice (as discussed in Unresponsive
UIs), (2) the tool hangs with no further outputs twice, (3) the tool keeps
logging “injection failed” without trying to fix the target app twice, and (4)
the tool keeps “waiting for app loading” once despite the fact that the target
app is already running and operational.

###  5.3. Improvement of Testing Performance

In this part of evaluation, we show that the speculated ineffective
exploration regions by Vet can be used to automatically fix the tool-app
applicability issues.

####  5.3.1. Automatic fix application

The essential idea is to prevent some applicability issues from happening
again by controlling the interactions between tools and apps. Specifically,
given an ineffective exploration region, we identify the UI element that the
tool fired action on right before the region begins, and use OurInfra to
disable the UI element during testing. Many applicability issues can be
targeted by this simple approach. For example, if we disable the advertisement
banners that lead to Unresponsive UIs in §5.2, tools will simply not run into
the undesirable situation, and they can focus on testing other more valuable
app functionalities.

We realize UI element disablement by relying on OurInfra to monitor screen
changes during testing and dynamically modify UI element properties. When a
target screen (i.e., a UI screen containing any target UI element, as
determined by UI hierarchy equivalence check) shows up, we pinpoint the target
UI element by matching with the path to each UI element from the root UI
element. Once we confirm that the target UI element exists on the current
screen, we tell OurInfra to disable the UI element so that it will not respond
to any action on itself. For the edge case that the tool’s action is not on
any UI element (e.g., pressing the Back button), we simply restart the target
app once we see the corresponding target screen. Note that there is no need to
modify the installation packages of apps given that we use dynamic UI
manipulation (see §4.4 for more details).

####  5.3.2. Methodology of experiments

For each pair of tool and app, in addition to the initial three runs for trace
collection, we perform the experiments for three runs in each of these three
settings: (1) we disable UI elements based on rank-1 regions (see §5.2.1 for
our ranking strategy), (2) we disable UI element based on rank-1, rank-2, and
rank-3 regions, and (3) keep the same settings as initial runs. Note that each
re-run is also one hour without interruption, and all experiments are
conducted in the same hardware and software environment regardless of
different settings.

We measure code coverage (specifically, numbers of uniquely covered methods in
the app’s bytecode) as the testing performance metric for all tests in our
experiments. Note that methods involved during app initialization (i.e.,
before tools start to test) are excluded for more precise comparison of code
coverage gain. Upon each pair of tool and app, we use the following test
groups for performance comparison:

  * •

Test Group 1 consists of the combined metrics of three initial runs and three
re-runs with the same settings as initial runs.

  * •

Test Group 2 consists of the combined metrics of three initial runs and three
re-runs with UI elements preceding rank-1 regions disabled.

  * •

Test Group 3 consists of the combined metrics of three initial runs and three
re-runs with UI elements preceding rank-1/2/3 regions disabled.

Each group consist of six 1-hour runs, intended for reducing random biases.
Test Group 1 serves as the baseline, while the other two test groups aim to
measure how much testing performance gain can Vet users expect. The main
reason for experimenting with ineffective exploration regions of different
ranks is that there could be more than one applicability issue for a
combination of tool and app, and addressing only one of them might not
suffice.

Note that we choose not to measure numbers of crashes on selected industrial-
quality apps, because we find that many of these app leverage JVM’s
setUncaughtExceptionHandler interface to intercept crashes and process
internally (likely using crash analysis services such as Crashlytics).
Consequently, we are unable to obtain the details of crashes for these apps by
monitoring Android system log (i.e., Logcat).

  * •

Notes: ‘#Mn’ shows the total number of covered methods in Test Group $n$.
$\Delta\text{M}_{n}=(\\#\text{M}_{n}-\\#\text{M}_{1})\div\\#\text{M}_{1}\times
100\%$. ‘¡±5%’ means that the corresponding $\Delta$M falls within (-5%,+5%).
‘-’ indicates that the corresponding tool is not run on the corresponding app.

####  5.3.3. Results

Table LABEL:tbl:intg_test_results shows the performance improvements by
comparing three test groups. As can be seen from the results, automatically
applying fixes based on Vet’s speculated ineffective exploration regions help
tools achieve up to 46.8% code coverage improvements on 11 of 15 apps using
the same amount of time. Also, all three tools benefit from Vet on different
sets of apps. It should be emphasized that our automatic fix approach does not
address all the applicability issues each combination of tool and app may
have—some issues, especially those rooting in tools’ implementations, are
likely only addressable by humans.

For most tool-app combinations with improvements, considering only rank-1
ineffective exploration regions is sufficient for code coverage gain. For
example, all three tools achieve better performance on app Merriam-Webster by
considering rank-1 regions, because these regions reveal the issue of
Unresponsive UI (see §5.2) and suggest that clicking the advertisement banner
located at the bottom of the app’s main screen to be the immediate cause.

However, there are cases where code coverage increases considerably when we
consider rank top-3 regions instead. One explanation is that there are
multiple applicability issues, or multiple instances of ineffective
exploration behavior corresponding to the same applicability issue. For
example, when applying Monkey on the app Nike Run Club, there are multiple
ways to enter hard-to-escape functionality as depicted by the motivating
example in §2. If we block only one entry, Monkey can still find other ways to
enter the functionality (although it would be more difficult) and waste time
there. Another explanation is that the rank-1 region might have revealed
issues that are not automatically fixable. Monkey on TripAdvisor falls in such
case: the rank-1 region reveals that network has been disconnected, but
OurInfra does not currently support addressing this issue automatically.
Meanwhile, the rank-2 region shows that Monkey finds it difficult to escape a
photo-viewing activity. Disabling entry to that activity helps Monkey focus on
more valuable functionalities.

There are also cases where code coverage decreases when we consider rank-3
ineffective exploration regions. The reason is that lower-ranked regions have
captured issues that are not automatically fixable, but we have tried to fix
them anyway, indeliberately interfering with normal functionalities. In the
case of applying Ape on Merriam-Webster, the rank-1 region reveals that the
advertisement banner should be blocked, helping the tool with coping
unresponsive UIs. However, a lower-ranked region shows that Ape restarts the
app frequently with few actions in between, and the corresponding “fix” is to
restart the app when one of the app’s main functionality shows up.
Consequently, Ape is unable to explore that functionality to achieve more
coverage in re-runs.

###  5.4. Missed Tool-app Applicability Issues

For this part of evaluation, we show our analysis of tool-app applicability
issues that are not revealed by any ineffective exploration regions (i.e.,
false negatives) reported by Vet.

####  5.4.1. Methodology

We propose using issue-specific detection tools to discover hidden
applicability issues in all collected traces, which can provide an estimation
of how likely any applicability issue is missed. Specifically, we summarize
the characteristics of two issues from §5.2, App logout and Unresponsive UIs,
to design two approaches specifically targeting these two issues. The reason
for choosing the aforementioned issues is that (1) they have substantial
appearance among all issues we have identified, and (2) their existence is
relatively more straightforward to be determined using our infrastructure. We
did not adopt manual inspection due to the subjectivity and the error-prune
nature of manual judgments, especially given that there are many more UI
traces to look into compared with those in §5.2.

Our issue-specific detection approaches work as follows:

  * •

App logout. We first manually look into the activity list of each app with
‘Login’ ticked in Table 5.1 and identify the subset of activities that are
used for logging in to the app. Then, when we analyze a given trace, we find
the first and the last occurrence of any activity that belongs to the
aforementioned list. If there is any occurrence, and the time distance between
the first and the last occurrence is at least $t_{\text{min}}$, we regard that
App logout is found on the trace.

  * •

Unresponsive UIs. In our manual investigation, we find only one case that
would lead to Unresponsive UIs: when the advertisement banner is clicked.
Consequently, a new activity can be observed, which belongs to Google AdMob
SDK and has the same activity ID across different apps. Thus, we simply look
for continuous appearance (i.e., there is no other activity in between) of the
aforementioned activity ID on a given trace. Note that we require the
appearance to be continuous so as to exclude the cases where the tool (such as
Ape) chooses to restart the app. If the appearance lasts for at least
$t_{\text{min}}$, we regard that Unresponsive UIs is found on the trace.

In order for a detected issue to be considered covered by our general-purpose
algorithms, we require that at least one algorithm-speculated ineffective
exploration region to cover at least 1/2 of the time length within which the
detected issue appears.

####  5.4.2. Results

We first apply the specialized algorithms on 40 traces covered by rank-1
regions, which we have already manually inspected. All the detected issues
have been covered by the speculated ineffective exploration regions by our
general-purpose algorithms. Reciprocally, all the manually-discovered App
logout and Unresponsive UIs issues are covered by the specialized algorithms.

We then apply the specialized algorithms on 110 traces not covered by rank-1
regions and compare the results against speculated regions from our general-
purpose algorithms. After manual confirmation, we find only two cases where
our general-purpose algorithms have indeed missed applicability issues,
discussed as follows:

  * •

Both missed cases of Unresponsive UIs are on two traces depicting Monkey and
WCTester interacting with Zedge. Our general-purpose algorithms report other
applicability issues, but not these two. After investigation, we find that the
miss roots in OurInfra, which currently does not support obtaining contents
from Android WebViews (i.e., embedded web browser widgets). As a result, our
Excessive Local Exploration algorithm is unable to differentiate several
screens and ultimately prioritizes the region with these screens over the
region showing Unresponsive UIs. The issue can be alleviated by further
enhancing OurInfra, which requires engineering efforts to be invested.

##  6\. Discussion and Limitation

We are mainly focusing on making Vet useful in the context of automated UI
testing. However, it should be noted that Vet’s potential usage scenarios are
beyond automated UI testing. One usage case is for app UI quality assurance,
where an app might have UI design issues with one or more functionalities. As
a result, human users will face difficulties locating their desired features.
When a human user runs into such situations, he/she will then likely search
for the desired features through repeated (and ineffective) exploration around
a few functionalities, which can be picked up from collected user behavior
statistics. By subsequently utilizing Vet’s ineffective exploration behavior
localization, we can quickly know which functionalities likely have the
aforementioned UI design issues and address these issues in a more timely
manner.

One question that might arise is whether Vet is capable of differentiating
testing scenarios (1) that a tool is supposed to handle, but does not (i.e.,
applicability issue), and (2) that a tool is not expected to handle (e.g.,
apps requiring special inputs). We would like to point out that it is
inherently difficult to differentiate these two kinds of scenarios due to
lacking specifications over tool capabilities. On the other hand, Vet can help
users identify (and mitigate) the scenarios outside of a tool’s capabilities,
which is already useful.

Last, we would like to acknowledge that OurInfra still has limitations. For
example, our current implementation does not capture text inputs. However,
adding support for text capturing is achievable with engineering efforts, and
it does not prevent Vet from being generalizable.

##  7\. Threats of validity

The major external threat to the validity of our work is the environmental
dependencies of our subject apps. More specifically, many of the industrial
apps in our experiments require networking for main functionalities to be
usable, and it is possible for such dependency to change the behaviors of
these apps despite our efforts to make our experimental environment consist
across different runs. In order to reduce the influences of environmental
dependencies in our experiments, we repeat each experimental setting (i.e.,
the combination of tools and apps) by three times and use the averaged metrics
in our paper. This threat could be reduced by involving more repetitions in
our experiments.

The major internal threat to the validity of our work comes from the manual
analysis of collected traces. We need to manually determine whether the
ineffective exploration regions reported by Vet indeed reveal any tool-app
applicability issue. Consequently, related evaluation results can be
influenced by subjective judgements. However, it should be noted that any work
involving manual judgements in the evaluation is vulnerable to this threat.
Moreover, we have shown our discoveries in details throughout evaluations,
providing chances for peer-reviews.

##  8\. Related work

Automated UI testing for Android. There have been various tools over years of
development. Earliest efforts include Monkey (AndroidMonkey, ), a randomized
tool from Google. The superior efficiency brings strong competitiveness to the
simple tool. Subsequent efforts result in tools mainly driven by
randomness/evolution (Mao:2016, ; Machiry:2013, ), UI modeling (su2017guided,
; DroidBot, ; Gu:2019:PGT:3339505.3339542, ), and systematic exploration
(Azim:2013, ). One recent work (10.1145/3377811.3380402, ) uses algorithms
with similar goals as Vet algorithms for Android UI testing. It should be
noted that Vet is intended to enhance these tools upon given apps without
needing to understand their internal design or implementation, as opposed to
building a tool that excels at all apps.

##### Trace Analysis.

Our work is related to log and trace analysis. Existing works have been
focusing on analyzing the logs generated by program code through techniques
including anomaly detection (10.1145/3338906.3338931, ; 8809512, ), cause
analysis (10.1145/3341301.3359650, ; 6606586, ), failure reproduction
(10.1145/3132747.3132768, ), and finding performance issues
(10.5555/2685048.2685099, ; 10.5555/3026877.3026924, ). Our work focuses on UI
traces with the goal of understanding ineffective exploration behavior, which
are different from logs produced by program code.

##### Parallel Testing.

Our work is also related to parallelizing the testing procedure in the sense
of producing multiple variants of the target program (i.e., customizing the
target app by manipulating the UI entries) for the testing tool to work on.
Existing works include parallelizing the testing methodology such as mutation
testing (doi:10.1002/stvr.1471, ) and symbolic execution
(10.1145/1966445.1966463, ; 10.1145/1831708.1831732, ), debugging process
(10.1145/1273463.1273468, ), and the software subject
(10.1016/j.infsof.2004.11.006, ).

##  9\. Conclusion

In this paper, we have exploited the opportunities of improving automated UI
testing via improving app-specific exploration strategies. Specifically, we
have presented Vet, a general solution for effective speculation of
ineffective exploration behaviors. We have designed specialized algorithms as
proof of Vet’s concepts. Our evaluation results have shown that Vet locates
ineffective exploration behaviors that reveal various tool-app applicability
issues hindering testing efficacy, and Vet automatically fixes the
applicability issues and achieves up to 46.8% code coverage relative
improvements on 11 of 15 apps under evaluation.

## References

  * [1] T. Azim and I. Neamtiu.  Targeted and depth-first exploration for systematic testing of android apps.  In Proceedings of the 2013 ACM SIGPLAN International Conference on Object Oriented Programming Systems Languages & Applications, OOPSLA ’13, 2013.
  * [2] S. Bucur, V. Ureche, C. Zamfir, and G. Candea.  Parallel Symbolic Execution for Automated Real-World Software Testing.  In Proceedings of the Sixth European Conference on Computer Systems, EuroSys ’11, 2011.
  * [3] S. R. Choudhary, A. Gorla, and A. Orso.  Automated test input generation for android: Are we there yet?  In Proceedings of the 2015 30th IEEE/ACM International Conference on Automated Software Engineering (ASE), ASE ’15, 2015.
  * [4] Z. Dong, M. Böhme, L. Cojocaru, and A. Roychoudhury.  Time-travel testing of android apps.  In Proceedings of the ACM/IEEE 42nd International Conference on Software Engineering, ICSE ’20, page 481–492, 2020.
  * [5] Google.  Android 64K method limit, 2018.
  * [6] Google.  Android Monkey, 2020.
  * [7] T. Gu, C. Sun, X. Ma, C. Cao, C. Xu, Y. Yao, Q. Zhang, J. Lu, and Z. Su.  Practical gui testing of android applications via model abstraction and refinement.  In Proceedings of the 41st International Conference on Software Engineering, ICSE ’19, pages 269–280, 2019.
  * [8] IDC and Gartner.  Share of Android Os of Global Smartphone Shipments from 1st Quarter 2011 to 2nd Quarter 2018.
  * [9] J. A. Jones, J. F. Bowring, and M. J. Harrold.  Debugging in parallel.  In Proceedings of the 2007 International Symposium on Software Testing and Analysis, ISSTA ’07, page 16–26, 2007.
  * [10] M. Labs.  10 best android & ios automation app testing tools, 2018.
  * [11] A. Lastovetsky.  Parallel testing of distributed software.  Inf. Softw. Technol., 47(10):657–662, July 2005.
  * [12] Y. Li, Z. Yang, Y. Guo, and X. Chen.  Droidbot: A lightweight ui-guided test input generator for android.  In Proceedings of the 39th International Conference on Software Engineering Companion, ICSE-C ’17, pages 23–26, 2017.
  * [13] T. F. Liu, M. Craft, J. Situ, E. Yumer, R. Mech, and R. Kumar.  Learning design semantics for mobile apps.  In Proceedings of the 31st Annual ACM Symposium on User Interface Software and Technology, UIST ’18, page 569–579, 2018.
  * [14] A. Machiry, R. Tahiliani, and M. Naik.  Dynodroid: An input generation system for android apps.  In Proceedings of the 2013 9th Joint Meeting on Foundations of Software Engineering, ESEC/FSE ’13, pages 224–234, 2013.
  * [15] K. Mao, M. Harman, and Y. Jia.  Sapienz: Multi-objective automated testing for android applications.  In Proceedings of the 25th International Symposium on Software Testing and Analysis, ISSTA ’16, pages 94–105, 2016.
  * [16] P. R. Mateo and M. P. Usaola.  Parallel mutation testing.  Software Testing, Verification and Reliability, 23(4):315–350, 2013\.
  * [17] MoQuality.  How to automate mobile app testing, 2020.
  * [18] S. Packevicius, D. Barisas, A. Usaniov, E. Guogis, and E. Bareisa.  Text semantics and layout defects detection in android apps using dynamic execution and screenshot analysis.  In ICIST, 2018.
  * [19] W. Shang, Z. M. Jiang, H. Hemmati, B. Adams, A. E. Hassan, and P. Martin.  Assisting developers of big data analytics applications when deploying on hadoop clouds.  In 2013 35th International Conference on Software Engineering (ICSE), pages 402–411, 2013.
  * [20] C. Simmonds.  The android graphics path, 2014.
  * [21] SmartBear.  Mastering the art of mobile testing, 2020.
  * [22] M. Staats and C. Pundefinedsundefinedreanu.  Parallel symbolic execution for structural test generation.  In Proceedings of the 19th International Symposium on Software Testing and Analysis, ISSTA ’10, page 183–194, 2010.
  * [23] T. Su, G. Meng, Y. Chen, K. Wu, W. Yang, Y. Yao, G. Pu, Y. Liu, and Z. Su.  Guided, stochastic model-based gui testing of android apps.  In Proceedings of the 2017 11th Joint Meeting on Foundations of Software Engineering, ESEC/FSE ’17, pages 245–256, 2017.
  * [24] Testsigma.  How to perform mobile automation testing of the ui?, 2020.
  * [25] W. Wang, D. Li, W. Yang, Y. Cao, Z. Zhang, Y. Deng, and T. Xie.  An Empirical Study of Android Test Generation Tools in Industrial Cases.  In Proceedings of the 33rd ACM/IEEE International Conference on Automated Software Engineering, ASE 2018, pages 738–748, 2018.
  * [26] D. Whitley.  A genetic algorithm tutorial.  Statistics and computing, 4(2):65–85, 1994.
  * [27] L. A. Wolsey and G. L. Nemhauser.  Integer and combinatorial optimization, volume 55.  John Wiley & Sons, 1999.
  * [28] S. Xi, S. Yang, X. Xiao, Y. Yao, Y. Xiong, F. Xu, H. Wang, P. Gao, Z. Liu, F. Xu, and J. Lu.  Deepintent: Deep icon-behavior learning for detecting intention-behavior discrepancy in mobile apps.  In Proceedings of the 2019 ACM SIGSAC Conference on Computer and Communications Security, CCS ’19, page 2421–2436, 2019.
  * [29] X. Xiao, X. Wang, Z. Cao, H. Wang, and P. Gao.  Iconintent: Automatic identification of sensitive ui widgets based on icon classification for android apps.  In 2019 IEEE/ACM 41st International Conference on Software Engineering (ICSE), pages 257–268, 2019.
  * [30] W. Yang, M. R. Prasad, and T. Xie.  A grey-box approach for automated gui-model generation of mobile applications.  In Proceedings of the 16th International Conference on Fundamental Approaches to Software Engineering, FASE ’13, pages 250–265, Berlin, Heidelberg, 2013. Springer-Verlag.
  * [31] X. Zeng, D. Li, W. Zheng, F. Xia, Y. Deng, W. Lam, W. Yang, and T. Xie.  Automated test input generation for android: Are we really there yet in an industrial case?  In Proceedings of the 2016 24th ACM SIGSOFT International Symposium on Foundations of Software Engineering, FSE ’16, pages 987–992, 2016\.
  * [32] K. Zhang and D. Shasha.  Simple fast algorithms for the editing distance between trees and related problems.  SIAM J. Comput., 18:1245–1262, 12 1989.
  * [33] X. Zhang, Y. Xu, Q. Lin, B. Qiao, H. Zhang, Y. Dang, C. Xie, X. Yang, Q. Cheng, Z. Li, J. Chen, X. He, R. Yao, J.-G. Lou, M. Chintalapati, F. Shen, and D. Zhang.  Robust log-based anomaly detection on unstable log data.  In Proceedings of the 2019 27th ACM Joint Meeting on European Software Engineering Conference and Symposium on the Foundations of Software Engineering, ESEC/FSE 2019, page 807–817, 2019.
  * [34] Y. Zhang, S. Makarov, X. Ren, D. Lion, and D. Yuan.  Pensieve: Non-intrusive failure reproduction for distributed systems using the event chaining approach.  In Proceedings of the 26th Symposium on Operating Systems Principles, SOSP ’17, page 19–33, 2017.
  * [35] Y. Zhang, K. Rodrigues, Y. Luo, M. Stumm, and D. Yuan.  The inflection point hypothesis: A principled debugging approach for locating the root cause of a failure.  In Proceedings of the 27th ACM Symposium on Operating Systems Principles, SOSP ’19, page 131–146, 2019.
  * [36] X. Zhao, K. Rodrigues, Y. Luo, D. Yuan, and M. Stumm.  Non-intrusive performance profiling for entire software stacks based on the flow reconstruction principle.  In Proceedings of the 12th USENIX Conference on Operating Systems Design and Implementation, OSDI’16, page 603–618, USA, 2016. USENIX Association.
  * [37] X. Zhao, Y. Zhang, D. Lion, M. F. Ullah, Y. Luo, D. Yuan, and M. Stumm.  Lprof: A non-intrusive request flow profiler for distributed systems.  In Proceedings of the 11th USENIX Conference on Operating Systems Design and Implementation, OSDI’14, page 629–644, USA, 2014. USENIX Association.
  * [38] Z. Zhao, S. Cerf, R. Birke, B. Robu, S. Bouchenak, S. Ben Mokhtar, and L. Y. Chen.  Robust anomaly detection on unreliable data.  In 2019 49th Annual IEEE/IFIP International Conference on Dependable Systems and Networks (DSN), pages 630–637, 2019.
  * [39] H. Zheng, D. Li, B. Liang, X. Zeng, W. Zheng, Y. Deng, W. Lam, W. Yang, and T. Xie.  Automated test input generation for android: Towards getting there in an industrial case.  In Proceedings of the 39th International Conference on Software Engineering: Software Engineering in Practice Track, ICSE-SEIP ’17, pages 253–262, 2017.